Date: Sat, 16 Aug 2014 15:47:41 -0600 From: Ian Lepore <ian@FreeBSD.org> To: alc@freebsd.org Cc: Konstantin Belousov <kostikbel@gmail.com>, Mateusz Guzik <mjguzik@gmail.com>, Johan Schuijt <johan@transip.nl>, FreeBSD Arch <freebsd-arch@freebsd.org> Subject: Re: [PATCH 1/2] Implement simple sequence counters with memory barriers. Message-ID: <1408225661.56408.598.camel@revolution.hippie.lan> In-Reply-To: <CAJUyCcNVJCzgMhxpktDYe8wWkAUMsvthkt7n7Yph3Rsy6TS8UQ@mail.gmail.com> References: <1408064112-573-1-git-send-email-mjguzik@gmail.com> <1408064112-573-2-git-send-email-mjguzik@gmail.com> <20140816093811.GX2737@kib.kiev.ua> <20140816185406.GD2737@kib.kiev.ua> <1408218427.56408.593.camel@revolution.hippie.lan> <CAJUyCcNVJCzgMhxpktDYe8wWkAUMsvthkt7n7Yph3Rsy6TS8UQ@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sat, 2014-08-16 at 16:16 -0500, Alan Cox wrote:
> On Sat, Aug 16, 2014 at 2:47 PM, Ian Lepore <ian@freebsd.org> wrote:
>
> > On Sat, 2014-08-16 at 21:54 +0300, Konstantin Belousov wrote:
> > > 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.
> > >
> >
> > I'm curious why that's better than atomic_add_rel_int()? On ARM, I
> > think the atomic add would be better than fetch/add/atomic_store.
> >
> >
>
> That seems unlikely. atomic_add_rel_int() has to do two things: (1) a
> load-linked/store-conditional loop to perform the atomic add and (2) a
> memory barrier to implement the release semantics. In this case, he
> doesn't need the add to be atomic; he only needs the release semantics.
>
For some reason I was thinking the two operations were essentially
identical on armv6 except for an add instruction in the loop. That
turns out to be the case for 64-bit values, but not for 32; my bad.
-- Ian
>
>
> > > > 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.
> >
> > I thought the whole point of this is to avoid locks for reading and
> > optimize the case where there is lots of concurrent reading and
> > relatively infrequent writing.
> >
> > I notice that the size/duration of writing is unbounded (even by
> > recommendation in comments) and there is no option for a reader to sleep
> > until a write sequence is complete. It seems like that's an invitation
> > to do bad things like wrap long (even potentially blocking) things
> > inside some write begin/end points and leave readers spinning uselessly
> > for a long time. The same thing could happen with spinlocks, except you
> > know when you take a spinlock that you shouldn't be holding onto it for
> > a long time, and you definitely know not to sleep.
> >
> > -- Ian
> >
> > >
> > > >
> > > > > +}
> > > > > +
> > > > > +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
> > >
> > >
> >
> >
> > _______________________________________________
> > freebsd-arch@freebsd.org mailing list
> > http://lists.freebsd.org/mailman/listinfo/freebsd-arch
> > To unsubscribe, send any mail to "freebsd-arch-unsubscribe@freebsd.org"
> >
> _______________________________________________
> freebsd-arch@freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-arch
> To unsubscribe, send any mail to "freebsd-arch-unsubscribe@freebsd.org"
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?1408225661.56408.598.camel>