From owner-freebsd-arch@FreeBSD.ORG Sat Aug 16 19:47:17 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 171F6941 for ; Sat, 16 Aug 2014 19:47:17 +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 CA08E2132 for ; Sat, 16 Aug 2014 19:47:16 +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 1XIjwS-000Gbz-UI; Sat, 16 Aug 2014 19:47:09 +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 s7GJl7oc045347; Sat, 16 Aug 2014 13:47:07 -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+0K04+tFEl26pMCPHYeY7o 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: Konstantin Belousov In-Reply-To: <20140816185406.GD2737@kib.kiev.ua> 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> Content-Type: text/plain; charset="us-ascii" Date: Sat, 16 Aug 2014 13:47:07 -0600 Message-ID: <1408218427.56408.593.camel@revolution.hippie.lan> Mime-Version: 1.0 X-Mailer: Evolution 2.32.1 FreeBSD GNOME Team Port Content-Transfer-Encoding: 7bit Cc: Mateusz Guzik , Johan Schuijt , freebsd-arch@freebsd.org 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 19:47:17 -0000 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. > > 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 > >