Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Tue, 26 Aug 2014 22:33:38 -0400
From: Rich Felker <>
Subject: sem_getvalue conformance considerations

POSIX says:

"The sem_getvalue() function shall update the location referenced by
the sval argument to have the value of the semaphore referenced by sem
without affecting the state of the semaphore. The updated value
represents an actual semaphore value that occurred at some unspecified
time during the call, but it need not be the actual value of the
semaphore when it is returned to the calling process."

musl currently implements this as:

	int val = sem->__val[0];
	*valp = val < 0 ? 0 : val;

However, I don't think this is correct. The "semaphore value" read
from __val[0] is not the formal semaphore value, but an implementation
detail: while there are waiters, after a post there is a window where
__val[0] is positive (to allow a waiter to take the semaphore) despite
the formal value never becoming positive. sem_post is documented as:

"If the semaphore value resulting from this operation is positive,
then no threads were blocked waiting for the semaphore to become
unlocked; the semaphore value is simply incremented."

"If the value of the semaphore resulting from this operation is zero,
then one of the threads blocked waiting for the semaphore shall be
allowed to return successfully from its call to sem_wait()."

So the formal "semaphore value" should always be zero while there are
more waiters than posts, even if those waiters have not yet woken to
take the semaphore.

It seems at least semi-possible to observe incorrect behavior with the
current implementation:

Example 1: Initially two waiters. One call to sem_post followed by
sem_getvalue should read a value of 0, not 1.

In principle we could compensate for this by declaring the value zero
if there are any waiters. But then:

Example 2: Initially one waiter. Two calls to sem_post followed by
sem_getvalue should read a value of 1, not 0.

What if we try to get fancy and subtract waiters from __val[0]?
Unfortunately we can't necessarily read __val[0] and waiters
(__val[1]) atomically together, so it's possible that one is outdated
by the time we read the other, such that the resulting difference is
not the correct formal semaphore value at any time during the
sem_getvalue call.

The one easy cop-out: We could claim the current behavior is
conforming anyway, since there is no way to prove that a thread is
actually blocked on a semaphore. (This is in contrast to cond vars,
where having unlocked the mutex proves they've formally become
waiters.) The state "blocked on semaphore" is fundamentally
indistinguishable from the state of "about to enter sem_wait". Thus,
we could say that, formally, there are never any waiters; sem_post
always makes the semaphore value positive, and a would-be waiter
formally arrives and decrements the semaphore value at some time after
the post makes the value positive.

Of course this is a really pathetic solution, but is there any way we
can provide real, consistent, meaningful results from sem_getvalue? Or
is the whole concept of sem_getvalue just so messed up that this is
the best possible way to handle it?


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.