id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
4882,Win32 shared_mutex does not handle timeouts correctly,martin.jerabek@…,viboes,"I have identified two problems with the Win32 implementation of boost::shared_mutex in case of timeouts:

Imagine the following scenario:

1. Three threads A, B, C compete for a shared_mutex in exclusive mode with timeouts (timed_lock).
2. Thread A acquires the mutex. Thread B and C wait for it in WaitForMultipleObjects, so exclusive_waiting is 2.
3. Thread A decides to release the mutex at the same time that thread B returns from WaitForMultipleObjects with a timeout.
   a. Thread A still sees exclusive_waiting == 2 because thread B has not yet adjusted the mutex state.
      It releases the mutex (exclusive = false), decrements exclusive_waiting to 1 and releases the unlock_sem and exclusive_sem.
   b. Thread B sees that no threads own the mutex for shared access (shared_count == 0) and exclusive is false.
      So it sets exclusive to true and now owns the mutex. Notice that it does not do anything with exclusive_waiting, so it is still 1.
   c. Thread C is woken up due to thread A releasing the semaphores.
      It loops back to retry to get the mutex but this fails because the mutex is already owned by thread B.
      However, it still increments exclusive_waiting to 2.

After this process, exclusive_waiting is 2 although only one thread (C) is waiting for the mutex.
If this is repeated often enough, timed_lock() will throw a lock_error because exclusive_waiting reached 127 and wrapped to 0.
The attached program triggers this problem by simply starting 20 threads which compete for the shared_mutex with a timeout in a loop.
On my dual-core 3GHz PC, the exception is thrown in less than a minute.


There is another similar failure mode:

1. Two threads A and B compete for a shared_mutex in exclusive mode with timeouts (timed_lock).
2. Thread A owns the mutex and thread B waits for it in WaitForMultipleObjects (exclusive_waiting == 1).
3. Again thread A releases the mutex at the same time that thread B returns from WaitForMultipleObjects with a timeout.
   a. Thread A again still sees exclusive_waiting == 1, so it releases the mutex, decrements exclusive_waiting to zero,
      and releases the semaphores.
   b. Thread B again sees that the mutex is available and acquires it without waiting for the semaphores because
      it already returned from WaitForMultipleObjects with a timeout.
4. Thread A tries to acquire the mutex again in exclusive mode. It sees that the mutex is locked, increments exclusive_waiting
   to 1 and calls WaitForMultipleObjects to wait for thread B to release the mutex.
5. However, the semaphores are still released from the time thread A released the mutex before
   but thread B never decremented them because it has already returned from WaitForMultipleObjects with a timeout.
6. This means that thread A returns immediately from WaitForMultipleObjects without a timeout.
   It tries again to acquire the mutex which is still locked by thread B, and it increments again exclusive_waiting
   which is now 2.
   
This is again a bug because exclusive_waiting is 2 although only thread A waits for the mutex.


To be honest, I do not know how to fix this bug. I think the basic problem is that changing the mutex state and releasing the semaphores
is not a single atomic operation. A thread which returned from WaitForMultipleObjects with a timeout
cannot know whether another thread decremented exclusive_waiting for it, so it does not know whether or not it has to decrement
exclusive_waiting itself to restore the mutex state.
",Bugs,closed,Boost 1.54.0,thread,Boost 1.45.0,Problem,fixed,,