Race unlocking-locking mutex

[David Ahern]

On 9/13/13 12:23 PM, Ángel González wrote:
> On 13/09/13 10:53, Carlos O'Donell wrote:
>> I expect that glibc will only be interested in an implementation if
>> you can show a considerable performance boost for having the library
>> implement the ticket lock.
> Even though "the scheduling policy shall determine which thread shall
> acquire the mutex", it seems weird that the thread which ends up
> acquiring the mutex is not one of the threads which were blocked waiting
> on it.

exactly.

> David problem should be solved if the unlock atomically assigned it to
> the waken thread (instead of waiting for it to reacquire the mutex).
> However, as it is a kernel decision, I think it would require a new
> futex operation, which stored in uaddr2 the waken tids. Then
> mutex->__data.__owner could be passed as uaddr2 and the mutex considered
> also locked if owner != 0.

Not necessarily proposing this for libc, but the product I work on needs 
a solution for this problem that invokes some kind of fairness -- and 
without adding too much complexity.

One option that comes to mind is adding a new element in the mutex -- a 
__prev_owner. On the unlock path set __prev_owner to thread id, release 
lock, awaken a waiter. If it is an uncontended lock (no tasks awakened 
or waiting), set __prev_owner to 0.

On the lock path check if __prev_owner is equal to thread id and if so 
take the slow path into the kernel.

Any particular worrisome race conditions to be wary of?

David

Carlos: I was careful not to use the word 'bug' in my responses. ;-)

>
> There's an interesting reading at https://lwn.net/Articles/267968/
> (Ticket spinlocks), including some impressive numbers. The kernel
> spinlocks were having pretty much the same problem, with the processor
> which released the spinlock reacquiring it before the waiters (probably
> due to owning the cache line).