Re: sem_getvalue conformance considerations

[Alexander Monakov <amonakov@ispras.ru>]

On Wed, 27 Aug 2014, Alexander Monakov wrote:

> On IRC Rich noted that I've too conveniently elided cancellation, so here's how
> I think cancellation handler should look like:

s/cancellation handler/"unwait" procedure/: returning with EINTR is botched in
my earlier mail and should employ the same procedure to undo state change

>   val = sem->val[0];
>   while (val < 0) {
>     /* We believe we are a waiter that no sem_post has "seen".  */
>     oldval = val;
>     if ((val = a_cas(sem->val, val, val+1)) == oldval)
>       return;
>   }
>   /* We are a waiter, and a non-negative val[0] indicates that one sem_post
>    * noticed us.  Consume the corresponding wake count increment.  */
>   a_dec(sem->val+1);

A plain atomic decrement on wake count like above is not correct.  However:

1. I think it's correct as long as no new waiters appear while we are
performing unwait.  If new waiters are matched by new posts it's ok; we only
care if the amount of new waiters is higher than the amount of new posts, as
then we are risking to cause a missing wake for one of those, or setting wake
count to -1 if they all consume wakes before we do the increment.

2. Thus it needs a fancy atomic op: decrement val[1] if val[0] is still equal
to "val" we retrieved earlier.  Otherwise, retry from the beginning.

Futhermore, doing the above in a true atomic fashion might not be required!
Isn't it okay to decrement wake count, and if we observe new waiters,
increment it back and cause a futex wake?  Thus:

retry:
  val = sem->val[0];
  while (val < 0) {
    /* We believe we are a waiter that no sem_post has "seen".  */
    oldval = val;
    if ((val = a_cas(sem->val, val, val+1)) == oldval)
      return;
  }
  /* We are a waiter, and a non-negative val[0] indicates that one sem_post
   * noticed us.  Consume the corresponding wake count increment.  */
  a_dec(sem->val+1);
  if (val > sem->val[0]) {
    /* New waiters appeared.  Avoid causing a missing wake and restart.  We
     * don't enter here if more new posts are posted than new waiters come. */
    a_inc(sem->val+1);
    futex_wake(sem->val+1, 1);
    goto retry;
  }


Alexander