new lock algorithm with state and congestion count in one atomic int
authorJens Gustedt <Jens.Gustedt@inria.fr>
Wed, 3 Jan 2018 13:17:12 +0000 (14:17 +0100)
committerRich Felker <dalias@aerifal.cx>
Tue, 9 Jan 2018 18:10:12 +0000 (13:10 -0500)
commit47d0bcd4762f223364e5b58d5a381aaa0cbd7c38
treee73dfc04306ff6f03f1e2712aa3c14321866df8a
parentb583c5d3b4cc2c54c68eef5eb7855ecfacee8bfc
new lock algorithm with state and congestion count in one atomic int

A variant of this new lock algorithm has been presented at SAC'16, see
https://hal.inria.fr/hal-01304108. A full version of that paper is
available at https://hal.inria.fr/hal-01236734.

The main motivation of this is to improve on the safety of the basic lock
implementation in musl. This is achieved by squeezing a lock flag and a
congestion count (= threads inside the critical section) into a single
int. Thereby an unlock operation does exactly one memory
transfer (a_fetch_add) and never touches the value again, but still
detects if a waiter has to be woken up.

This is a fix of a use-after-free bug in pthread_detach that had
temporarily been patched. Therefore this patch also reverts

         c1e27367a9b26b9baac0f37a12349fc36567c8b6

This is also the only place where internal knowledge of the lock
algorithm is used.

The main price for the improved safety is a little bit larger code.

Under high congestion, the scheduling behavior will be different
compared to the previous algorithm. In that case, a successful
put-to-sleep may appear out of order compared to the arrival in the
critical section.
src/internal/pthread_impl.h
src/thread/__lock.c
src/thread/pthread_detach.c