semaphores: fix missed wakes from ABA bug in waiter count logic
authorRich Felker <dalias@aerifal.cx>
Tue, 13 Dec 2022 23:39:44 +0000 (18:39 -0500)
committerRich Felker <dalias@aerifal.cx>
Tue, 13 Dec 2022 23:39:44 +0000 (18:39 -0500)
commit159d1f6c02569091c7a48bdb2e2e824b844a1902
tree0b715a607d2eecce4c16b1dbd1a6cdbd0904099b
parentf47a8cdd250d9163fcfb39bf4e9d813957c0b187
semaphores: fix missed wakes from ABA bug in waiter count logic

because the has-waiters state in the semaphore value futex word is
only representable when the value is zero (the special value -1
represents "0 with potential new waiters"), it's lost if intervening
operations make the semaphore value positive again. this creates an
ABA issue in sem_post, whereby the post uses a stale waiters count
rather than re-evaluating it, skipping the futex wake if the stale
count was zero.

the fix here is based on a proposal by Alexey Izbyshev, with minor
changes to eliminate costly new spurious wake syscalls.

the basic idea is to replace the special value -1 with a sticky
waiters bit (repurposing the sign bit) preserved under both wait and
post. any post that takes place with the waiters bit set will perform
a futex wake.

to be useful, the waiters bit needs to be removable, and to remove it
safely, we perform a broadcast wake instead of a normal single-task
wake whenever removing the bit. this lets any un-accounted-for waiters
wake and re-add the waiters bit if they still need it.

there are multiple possible choices for when to perform this
broadcast, but the optimal choice seems to be doing it whenever the
observed waiters count is less than two (semantically, this means
exactly one, but we might see a stale count of zero). in this case,
the expected number of threads to be woken is one, with exactly the
same cost as a non-broadcast wake.
src/thread/sem_getvalue.c
src/thread/sem_post.c
src/thread/sem_timedwait.c
src/thread/sem_trywait.c