[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20240810030216.GE10433@brightrain.aerifal.cx>
Date: Fri, 9 Aug 2024 23:02:17 -0400
From: Rich Felker <dalias@...c.org>
To: Markus Wichmann <nullplan@....net>
Cc: musl@...ts.openwall.com, Alexey Izbyshev <izbyshev@...ras.ru>
Subject: Re: Memory lock needed for semaphores?
On Wed, Aug 07, 2024 at 09:15:55AM +0200, Markus Wichmann wrote:
> Hi all,
>
> an idea I had in the shower just now: Why don't we set the number of
> threads to awaken equal to the new semaphore value? I mean, once we
> determine there may be waiters and we have to wake some of them, isn't
> that the natural number of threads to wake up?
If you do that, then performing N posts in a row will yield N*(N+1)/2
wakes, when you only wanted N wakes. Imagine a producer-consumer setup
with 100 consumers and a producer posting 10 new things to be
consumed. You get a thundering herd of waiters waking up vying for
significantly more slots than are actually available.
> The thing is, my example doesn't stop at two threads. There can be any
> number of threads stuck between the CAS and the wake in sem_post(). And
> yet, it might be only one sem_post() that gets to make a wake call, so
> that one call has to wake up all threads that might get the semaphore.
At least in the trivial extension of your example case to N threads
stuck posting, the unmapping is invalid and the whole example breaks
down. This is because the only way the unmapping is valid is by
the unmapping thread being able to know it's the last user of the
mapped semaphore. If you have other concurrent post operations, then
you haven't synchronized being the last user, and thus can't unmap.
In your original example, the unmapping thread synchronized knowing it
was the last user by virtue of its own wait succeeding, as a result of
post modifying the semaphore value.
You can probably modify the example by waiting N times rather than
just 1 time, so that you've consumed all N posts to conclude that no
additional users of the semaphore exist. But then the semaphore value
is back at 0, and with the proposed changes we discussed, you would
issue a futex wake correctly when posting it again.
> So if there are 100 waiters, and we just set the semaphore value to 3
> (OK, INT_MIN + 3), then we wake up 3 threads. Because we can get in this
> state only if there are another 2 threads that haven't awoken any of the
> waiters, or the waiters haven't decremented the semaphore yet. Of
> course, there might be another thread just chomping at the bit to wake
> up another 2 threads, but that thread also might not get to perform the
> wake at all.
>
> I know that currently we only set the val argument to __futexwake to 1
> or -1, but nothing in the interface says we have to.
Indeed, it just doesn't seem to be useful to set it to a different
value.
Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
