[Boost-bugs] [Boost C++ Libraries] #4882: Win32 shared_mutex does not handle timeouts correctly

Subject: [Boost-bugs] [Boost C++ Libraries] #4882: Win32 shared_mutex does not handle timeouts correctly
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-11-22 17:42:09

#4882: Win32 shared_mutex does not handle timeouts correctly
---------------------------------------------+------------------------------
 Reporter:  martin.jerabek@…                 |       Owner:  anthonyw
     Type:  Bugs                             |      Status:  new     
Milestone:  To Be Determined                 |   Component:  thread  
  Version:  Boost 1.45.0                     |    Severity:  Problem 
 Keywords:                                   |  
---------------------------------------------+------------------------------
 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.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/4882>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.