From owner-freebsd-arch@FreeBSD.ORG Sat Aug 16 21:47:46 2014 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 91D0A232; Sat, 16 Aug 2014 21:47:46 +0000 (UTC) Received: from mho-01-ewr.mailhop.org (mho-03-ewr.mailhop.org [204.13.248.66]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4F08E2040; Sat, 16 Aug 2014 21:47:45 +0000 (UTC) Received: from [73.34.117.227] (helo=ilsoft.org) by mho-01-ewr.mailhop.org with esmtpsa (TLSv1:AES256-SHA:256) (Exim 4.72) (envelope-from ) id 1XIlpA-000Mcz-BT; Sat, 16 Aug 2014 21:47:44 +0000 Received: from [172.22.42.240] (revolution.hippie.lan [172.22.42.240]) by ilsoft.org (8.14.9/8.14.9) with ESMTP id s7GLlgss045559; Sat, 16 Aug 2014 15:47:42 -0600 (MDT) (envelope-from ian@FreeBSD.org) X-Mail-Handler: Dyn Standard SMTP by Dyn X-Originating-IP: 73.34.117.227 X-Report-Abuse-To: abuse@dyndns.com (see http://www.dyndns.com/services/sendlabs/outbound_abuse.html for abuse reporting information) X-MHO-User: U2FsdGVkX1+wzOBUuwiyQpxhA0wS3vEp X-Authentication-Warning: paranoia.hippie.lan: Host revolution.hippie.lan [172.22.42.240] claimed to be [172.22.42.240] Subject: Re: [PATCH 1/2] Implement simple sequence counters with memory barriers. From: Ian Lepore To: alc@freebsd.org In-Reply-To: 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> Content-Type: text/plain; charset="us-ascii" Date: Sat, 16 Aug 2014 15:47:41 -0600 Message-ID: <1408225661.56408.598.camel@revolution.hippie.lan> Mime-Version: 1.0 X-Mailer: Evolution 2.32.1 FreeBSD GNOME Team Port Content-Transfer-Encoding: 7bit Cc: Konstantin Belousov , Mateusz Guzik , Johan Schuijt , FreeBSD Arch X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.18-1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 16 Aug 2014 21:47:46 -0000 On Sat, 2014-08-16 at 16:16 -0500, Alan Cox wrote: > On Sat, Aug 16, 2014 at 2:47 PM, Ian Lepore 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 > > > > > +#include > > > > > + > > > > > +#include > > > > > + > > > > > +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"