Re: New optimized normal-type mutex?

[Rich Felker <dalias@libc.org>]

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