Re: [musl] sem_post() can miss waiters

[Rich Felker <dalias@libc.org>]

On Wed, Dec 14, 2022 at 01:29:54PM +0300, Alexey Izbyshev wrote:
> On 2022-12-14 04:48, Rich Felker wrote:
> >On Tue, Nov 22, 2022 at 08:41:44AM +0300, Alexey Izbyshev wrote:
> >>On 2022-11-22 03:09, Rich Felker wrote:
> >>>If I understand correctly, the cost of the first option is generally
> >>>an extra "last" broadcast wake that shouldn't be needed. Is that
> >>>right?
> >>>
> >>>For example, if sem starts with count 0 and thread A calls wait, then
> >>>thread B calls post twice, both posts make a syscall even though only
> >>>the first one should have.
> >>>
> >>Yes, exactly.
> >>
> >>>What if you instead perform the broadcast wake when the observed
> >>>waiters count is <=1 rather than ==0? This should have no cost in the
> >>>common case, but in the race case, I think it forces any hiding
> >>>(just-arrived) extra waiters to wake, fail, and re-publish their
> >>>waiting status to the waiters bit.
> >>>
> >>Indeed, I think this solves the overhead issue quite nicely, thanks.
> >>So sem_post wake up logic would basically boil down to this:
> >>
> >>* WAITERS_BIT is set and waiters > 1: don't reset WAITERS_BIT since
> >>it's likely that some waiters will remain (and it's always fine to
> >>err on the side of preserving the WAITERS_BIT); wake a single
> >>waiter.
> >>
> >>* WAITERS_BIT is set and waiters <= 1: reset WAITERS_BIT and wake
> >>all waiters. In non-racy cases only a single waiter will be woken.
> >>
> >>* WAITERS_BIT is unset: don't wake anybody. Even if there are some
> >>waiters, another sem_post (that reset the WAITERS_BIT) is
> >>responsible for waking them.
> >>
> >>In code:
> >>
> >>int val, new, waiters, priv = sem->__val[2];
> >>do {
> >>    val = sem->__val[0];
> >>    waiters = sem->__val[1];
> >>    if ((val & SEM_VALUE_MAX) == SEM_VALUE_MAX) {
> >>        errno = EOVERFLOW;
> >>        return -1;
> >>    }
> >>    new = val + 1;
> >>    if (waiters <= 1)
> >>        new &= ~0x80000000;
> >>} while (a_cas(sem->__val, val, new) != val);
> >>if (val<0) __wake(sem->__val, waiters <= 1 ? -1 : 1, priv);
> >
> >Yes, this looks good to me. How is the attached patch?
> >
> The patch looks good to me.

Just a heads-up: this patch is in my big queue of stuff to push, and
should be upstream soon now.

Rich