From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8241 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: New optimized normal-type mutex? Date: Wed, 29 Jul 2015 20:10:14 -0400 Message-ID: <20150730001014.GA16376@brightrain.aerifal.cx> References: <20150521234402.GA25373@brightrain.aerifal.cx> <8c49d81e.dNq.dMV.21.hNiSfA@mailjet.com> <1438207875.10742.3.camel@inria.fr> <20150729233054.GZ16376@brightrain.aerifal.cx> <1438213760.10742.5.camel@inria.fr> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1438215033 17016 80.91.229.3 (30 Jul 2015 00:10:33 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 30 Jul 2015 00:10:33 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-8254-gllmg-musl=m.gmane.org@lists.openwall.com Thu Jul 30 02:10:32 2015 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1ZKbQe-0006DO-Gv for gllmg-musl@m.gmane.org; Thu, 30 Jul 2015 02:10:32 +0200 Original-Received: (qmail 29786 invoked by uid 550); 30 Jul 2015 00:10:29 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 29758 invoked from network); 30 Jul 2015 00:10:26 -0000 Content-Disposition: inline In-Reply-To: <1438213760.10742.5.camel@inria.fr> User-Agent: Mutt/1.5.21 (2010-09-15) Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:8241 Archived-At: On Thu, Jul 30, 2015 at 01:49:20AM +0200, Jens Gustedt wrote: > Am Mittwoch, den 29.07.2015, 19:30 -0400 schrieb Rich Felker: > > On Thu, Jul 30, 2015 at 12:11:15AM +0200, Jens Gustedt wrote: > > > Hello, > > > > > > Am Mittwoch, den 29.07.2015, 14:09 +0200 schrieb Joakim Sindholt: > > > > So he went on and suggested that a cas-less lock was possible with > > > > a_fetch_add however I can't make it work and I don't think he can > > > > either. His idea however is sound: the one who flips the sign bit takes > > > > the lock. Based on that I've cobbled together a different lock that will > > > > probably perform worse than this approach but none-the-less be correct > > > > as far as I can tell. > > > > > > > > The difference is that we consider the lock owner a waiter as well, thus > > > > requiring a cas loop in the unlock function to remove itself, so to > > > > speak, from the waiter count. a_fetch_and also turns into a cas loop so > > > > I consider this fairly minor. > > > > This makes the wait loop a little simpler while still maintaining a > > > > waiter count and still only using one int. > > > > > > Nice ideas! > > > > > > After the recent discussion about the problems on x86_64 I was trying > > > to come up with a simple lock for the atomics, and I came thinking > > > along the same lines. > > > > Unfortunately, discussion on IRC has revealed a potentially > > show-stopping issue for merging the waiter count into the futex word: > > arrival of new waiters causes EAGAIN from futex_wait. I don't know any > > good way around this, but it's probably the reason designs like this > > have not been popular before. > > Hm, could you be more specific about where this hurts? > > In the code I have there is > > for (;val & lockbit;) { > __syscall(SYS_futex, loc, FUTEX_WAIT, val, 0); > val = atomic_load_explicit(loc, memory_order_consume); > } > > so this should be robust against spurious wakeups, no? The problem is that futex_wait returns immediately with EAGAIN if *loc!=val, which happens very often if *loc is incremented or otherwise changed on each arriving waiter. Rich