mailing list of musl libc
 help / color / mirror / code / Atom feed
From: Rich Felker <dalias@libc.org>
To: Alexey Izbyshev <izbyshev@ispras.ru>
Cc: musl@lists.openwall.com
Subject: Re: [musl] sem_post() can miss waiters
Date: Wed, 22 Feb 2023 13:12:17 -0500	[thread overview]
Message-ID: <20230222181217.GD4163@brightrain.aerifal.cx> (raw)
In-Reply-To: <583865e860854d059f50d23a9acd7a8f@ispras.ru>

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

      reply	other threads:[~2023-02-22 18:12 UTC|newest]

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-11-21  5:14 Alexey Izbyshev
2022-11-22  0:09 ` Rich Felker
2022-11-22  5:41   ` A. Wilcox
2022-11-22  5:41   ` Alexey Izbyshev
2022-12-14  1:48     ` Rich Felker
2022-12-14 10:29       ` Alexey Izbyshev
2023-02-22 18:12         ` Rich Felker [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20230222181217.GD4163@brightrain.aerifal.cx \
    --to=dalias@libc.org \
    --cc=izbyshev@ispras.ru \
    --cc=musl@lists.openwall.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://git.vuxu.org/mirror/musl/

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).