sync::Semaphore needs to require nonnegative initial resource count

[bblum]

https://github.com/rust-lang/rust/blob/master/src/libsync/raw.rs#L153

if state.count <= 0 {

should be

if state.count >= 0 {

@alexcrichton, please confirm

it looks like i introduced this by accident in 604e4ad? No idea what i was thinking.

edit: changed title; see below

[bblum]

to clarify: with semaphores initialized to 1, and used like mutexes (i.e. never signalled up to 2 or more), the behaviour is correct; all that would be required for that case is state.count == 0. so it will behave correctly when used as a mutex (as it is in Mutex and RWLock), but it will signal too soon if you initialize negative, and it will fail to signal when it should if you initialize it to 2 or more.

Dr-Emann found this bug on irc.

[alexcrichton]

Something a little tricky is going on here, I remember thinking about this last time I was looking at this code.

The check I believe is correct in some situations, however. If you start out with a count of 1 and then immediately get 10 waiters, the count will be -9. When one of them releases a resource, the count is still negative after the bump (-8), but it definitely needs to signal someone.

I think that negative initialization is indeed broken, however.

[bblum]

Oh yes, now I remember. The implementation is correct but doesn't support negative initialization, but it fails to assert nonnegative (or require uint) in the constructor. What's going on is the waiters subtract from count unconditionally, so count actually represents the number of resources not already "spoken for" by existing waiters. The reason I chose this implementation is that it avoids needing to use while instead of if in the wait path to prevent the paradise lost race:

waiter 1                waiter 2                signaller
if count <= 0 { 
    enqueue self;
}
                                                count++;
                                                signal waiter 1;
                        if count <= 0 { 
                            // count == 1
                        }   
                        // have the lock
// wakes up
// have the lock

However even if you use while to solve this, you don't get bounded waiting since waiter 2 can still cut in line by racing this way. Subtracting from count before going to sleep "claims your spot in line" since it will force waiter 2 to also use the wait queue.

Not to mention that since all this logic is interleaved with a raw pthread mutex with() access, doing a while-style implementation would require repeated calls to the mutex instead of just 1.

I think the appropriate solution is just to assert in the constructor that the initial value is nonnegative -- the speed + bounded waiting benefits outweigh the obscure use case of negative initialization, since this is used as the building block for Mutex and RWLock more often than it is used directly.