[PATCH 1/2] Implement simple sequence counters with memory barriers.

[Konstantin Belousov]

On Sat, Aug 16, 2014 at 12:38:11PM +0300, Konstantin Belousov wrote:
> On Fri, Aug 15, 2014 at 02:55:11AM +0200, Mateusz Guzik wrote:
> > ---
> >  sys/sys/seq.h | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 126 insertions(+)
> >  create mode 100644 sys/sys/seq.h
> > 
> > diff --git a/sys/sys/seq.h b/sys/sys/seq.h
> > new file mode 100644
> > index 0000000..0971aef
> > --- /dev/null
> > +++ b/sys/sys/seq.h
> > @@ -0,0 +1,126 @@
> > +/*-
> > + * Copyright (c) 2014 The FreeBSD Project
> > + *
> > + * Redistribution and use in source and binary forms, with or without
> > + * modification, are permitted provided that the following conditions
> > + * are met:
> > + * 1. Redistributions of source code must retain the above copyright
> > + *    notice, this list of conditions and the following disclaimer.
> > + * 2. Redistributions in binary form must reproduce the above copyright
> > + *    notice, this list of conditions and the following disclaimer in the
> > + *    documentation and/or other materials provided with the distribution.
> > + *
> > + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
> > + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
> > + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
> > + * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
> > + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
> > + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
> > + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
> > + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
> > + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
> > + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> > + * SUCH DAMAGE.
> > + *
> > + * $FreeBSD$
> > + */
> > +
> > +#ifndef _SYS_SEQ_H_
> > +#define _SYS_SEQ_H_
> > +
> > +#ifdef _KERNEL
> > +
> > +/*
> > + * Typical usage:
> > + *
> > + * writers:
> > + * 	lock_exclusive(&obj->lock);
> > + * 	seq_write_begin(&obj->seq);
> > + * 	.....
> > + * 	seq_write_end(&obj->seq);
> > + * 	unlock_exclusive(&obj->unlock);
> > + *
> > + * readers:
> > + * 	obj_t lobj;
> > + * 	seq_t seq;
> > + *
> > + * 	for (;;) {
> > + * 		seq = seq_read(&gobj->seq);
> > + * 		lobj = gobj;
> > + * 		if (seq_consistent(&gobj->seq, seq))
> > + * 			break;
> > + * 		cpu_spinwait();
> > + * 	}
> > + * 	foo(lobj);
> > + */		
> > +
> > +typedef uint32_t seq_t;
> > +
> > +/* A hack to get MPASS macro */
> > +#include <sys/systm.h>
> > +#include <sys/lock.h>
> > +
> > +#include <machine/cpu.h>
> > +
> > +static __inline bool
> > +seq_in_modify(seq_t seqp)
> > +{
> > +
> > +	return (seqp & 1);
> > +}
> > +
> > +static __inline void
> > +seq_write_begin(seq_t *seqp)
> > +{
> > +
> > +	MPASS(!seq_in_modify(*seqp));
> > +	(*seqp)++;
> > +	wmb();
> This probably ought to be written as atomic_add_rel_int(seqp, 1);
Alan Cox rightfully pointed out that better expression is
v = *seqp + 1;                                                                  
atomic_store_rel_int(seqp, v);
which also takes care of TSO on x86.

> Same note for all other linux-style barriers.  In fact, on x86
> wmb() is sfence and it serves no useful purpose in seq_write*.
> 
> Overall, it feels too alien and linux-ish for my taste.
> Since we have sequence bound to some lock anyway, could we introduce
> some sort of generation-aware locks variants, which extend existing
> locks, and where lock/unlock bump generation number ?
Still, merging it to the guts of lock implementation is right
approach, IMO.

> 
> > +}
> > +
> > +static __inline void
> > +seq_write_end(seq_t *seqp)
> > +{
> > +
> > +	wmb();
> > +	(*seqp)++;
> > +	MPASS(!seq_in_modify(*seqp));
> > +}
> > +
> > +static __inline seq_t
> > +seq_read(seq_t *seqp)
> > +{
> > +	seq_t ret;
> > +
> > +	for (;;) {
> > +		ret = READ_ONCE(*seqp);
> > +		if (seq_in_modify(ret)) {
> > +			cpu_spinwait();
> > +			continue;
> > +		}
> > +		break;
> > +	}
> > +
> > +	rmb();
> > +
> > +	return (ret);
> > +}
> > +
> > +static __inline seq_t
> > +seq_consistent_nomb(seq_t *seqp, seq_t oldseqp)
> > +{
> > +
> > +	MPASS(!seq_in_modify(oldseqp));
> > +	return (*seqp == oldseqp);
> > +}
> > +
> > +static __inline seq_t
> > +seq_consistent(seq_t *seqp, seq_t oldseqp)
> > +{
> > +
> > +	rmb();
> > +	return (seq_consistent_nomb(seqp, oldseqp));
> > +}
> > +
> > +#endif	/* _KERNEL */
> > +#endif	/* _SYS_SEQ_H_ */
> > -- 
> > 2.0.2


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.freebsd.org/pipermail/freebsd-arch/attachments/20140816/88e8f909/attachment.sig>