Re: Resuming work on new semaphore

[Alexander Monakov <amonakov@ispras.ru>]

So, your solution results in a simpler execution path for successful trywait,
but needs to undo semaphore adjustment to return EAGAIN (which I believe to
be relatively common).  Also, if a concurrent poster sees transient negative
val[0], it will proceed to slow sem_post path (val[1] increment and futex
wake), so if there's high activity on the semaphore, looks like this solution
may slow down posters.

My solution keeps trywait successful path as-is, and adds a test on val[1] in
EAGAIN case with a conditional branch that is normally not executed.
Semaphore's contents are not changed if returning EAGAIN.  I was about to say
that this leads to more preferable cache traffic on highly contended semaphore
(all calls to trywait returning EAGAIN simultaneously can work on shared
rather than exclusive cache lines), but unfortunately we need a read memory
barrier on the semaphore and the solution to that was to perform CAS on val[0]
unconditionally, which would cause each caller to make the cache line with the
semaphore exclusive anyway, IIUC.

Regarding the problem raised on IRC (that with 1 waiter, post-getvalue-trywait
can result in 0-0 return values rather than 0-EAGAIN, while previously it
could result in 1-EAGAIN rather that 1-0, with the explanation that the waiter
did not "become a waiter" so that post had to wake it, but suspended execution
and resumed only after semaphore value became positive, and now the surprising
behavior needs a different explanation): I think in the absence of a mechanism
to detect whether current waiters are still alive, that's the way it has to
be.  Either you pretend there are no waiters at any time, like today, or you
count dead waiters same as live waiters and report 0 semaphore value to the
caller, but then what do you do when caller invokes sem_wait and all other
waiters are dead?  Suspend the caller indefinitely, or let it proceed by
consuming a pending post and thus revealing an inconsistency?

Alexander