Re: New optimized normal-type mutex?

[Joakim Sindholt <opensource@zhasha.com>]

On Fri, May 22, 2015 at 1:44 AM, Rich Felker <dalias@libc.org> wrote:
> I realized (thanks to conversations with wm4) that it's possible to
> optimize normal-type mutexes a lot to eliminate spurious futex wakes
> and reduce the number of atomic ops/barriers under contention.
> 
> The concept is to store the full mutex state in a single int:
> 
> bits 0-29: waiter count
> bit 30: waiter flag
> bit 31: lock bit
> 
> Then unlock is:
> 
> old = a_fetch_and(p, 0x3fffffff); // new op
> if (old & 0x40000000) wake(p,1);
> 
> Trylock is:
> 
> old = *p;
> if (old < 0) {
> 	a_barrier();
> 	old = *p;
> }
> if (old >= 0 && a_cas(p, old, old|INT_MIN)) return 0;
> 
> Lock is:
> 
> while (spins--) {
> 	if (!trylock()) return 0;
> 	a_spin();
> }
> while ((old = *p) < 0) {
> 	new = old+1 | 0x40000000;
> 	if (a_cas(p, old, new)==old) break;
> }
> for(;;) {
> 	while ((old = *p) < 0) {
> 		futex_wait(p, old);
> 	}
> 	new = old-1;
> 	if (new) new |= 0x40000000; // set waiters flag if any other waiters
> 	new |= INT_MIN;
> 	if (a_cas(p, old, new)==old) return 0;
> }

I implemented this lock in my own library and I even did some
preliminary race tests. I couldn't find fault with it. However amonakov
did and made me aware of it on IRC.

Thread A takes the lock
Thread B tries to take the lock but ends up in futex_wait
Thread A unlocks the lock
Thread A futex_wakes Thread B
Thread A steals the lock
Thread B goes back into futex_wait
Thread A unlocks the lock
Thread B hangs
Because:
The first unlock clears the 0x40000000 flag and it does not get set
again at any point.

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.

void lock(volatile int *p)
{
    int val, spins = 200;

    while (spins--) {
        if (trylock(p)) { return; }
        spin();
    }

    while (1) {
        if ((val = a_load(p)) < 0) {
            if (a_cas(p, val, val - 1) == val) { break; }
        } else {
            if (a_cas(p, val, -val - 1) == val) { return; }
        }
    }

    while (1) {
        while ((val = a_load(p)) < 0) {
            futex_wait(p, val);
        }
        if (a_cas(p, val, -val) == val) { return; }
    }
}

int trylock(volatile int *p)
{
    int val = a_load(p);
    if (val < 0) {
        a_barrier();
        val = a_load(p);
    }
    return (val >= 0 && a_cas(p, val, -val - 1) == val);
}

void unlock(volatile int *p)
{
    int new, val = a_load(p);
    while ((new = a_cas(p, val, -(val + 1))) != val) { val = new; }
    if (val + 1 != 0) { futex_wake(p, 1); }
}

-- Joakim