[LLVMbugs] [Bug 23616] New: TSAN incorrectly model condition variable semantics

[bugzilla-daemon at llvm.org]

https://llvm.org/bugs/show_bug.cgi?id=23616

            Bug ID: 23616
           Summary: TSAN incorrectly model condition variable semantics
           Product: compiler-rt
           Version: unspecified
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: compiler-rt
          Assignee: unassignedbugs at nondot.org
          Reporter: eric at efcs.ca
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

The example execution should be well formed but it currently causes TSAN to
incorrectly report a data race.

Step   Thread A                    Thread B
1.     ...                        lk.lock()
2.     ...                        cv.wait(lk)
3.    lk.lock()                      ...
4.    cv.notify_one()                ...
5.    cv.~condition_variable()       ...
6.    lk.unlock()                    ...
7.      ...                       finally exits cv.wait  // ok, not a data race

For this execution TSAN will report something akin to:

1. In step 5 thread A writes to cv while holding lk.
2. Previous read of cv by thread B in step 2.

Note that when TSAN intercepts cv.wait(lk) it unlocks lk before annotating the
read. This is what leads to the incorrect behaviour.


To restate C++14 [thread.condition]p3 the call to `wait(lock)` has three atomic
steps (denoted Wait.X)
Wait.1: Enter the waiting queue and release the lock.
Wait.2: Become unblocked in wait().
Wait.3: Reacquire the mutex.

In order to show that there is no data race I will demonstrate that Thread A
cannot reach step 5 until thread B completes Wait.2. This condition is
sufficient because once thread B completes Wait.2 the condition variable can be
safely destroyed according to the wording in 30.5.1 p5.

Obviously thread A cannot proceed past step 3 until thread B completes Wait.1
and releases the mutex.

Thread B cannot complete Wait.2 until it is notified by thread A. The effects
of notify_all() say that the unblocking of thread B "happens before" thread A
returns from the notify_all().

Therefore thread B must reach Wait.3 before thread A can reach step 5

Below are the relevant clauses from the C++14 standard regarding condition
variable.

30.5 [thread.condition]p3:
>p3 The execution of notify_one and notify_all shall be atomic. The execution 
>    of wait, wait_for, and
>    wait_until shall be performed in three atomic parts:
>    1. the release of the mutex and entry into the waiting state;
>    2. the unblocking of the wait; and
>    3. the reacquisition of the lock.
>p4 The implementation shall behave as if all executions of notify_one,
>   notify_all, and each part of the wait,
>   wait_for, and wait_until executions are executed in a single unspecified 
>   total order consistent with the "happens before" order.

30.5.1 [thread.condition.condvar]p5
> ~ condition_variable();
> Requires: There shall be no thread blocked on *this. [ Note: That is, all 
>     threads shall have been notified; they may subsequently block on the
>     lock specified in the wait. This relaxes the usual rules, which would 
>     have required all wait calls to happen before destruction. Only the 
>     notification to unblock the wait must happen before destruction. The user 
>     must take care to ensure that no threads wait on
>     *this once the destructor has been started, especially when the waiting 
>     threads are calling the wait

30.5.1 [thread.condition.condvar]p8
> void notify_all() noexcept;
> Effects: Unblocks all threads that are blocked waiting for *this.


The following libc++ test serves as a minimal reproducer.
https://github.com/llvm-mirror/libcxx/blob/master/test/std/thread/thread.condition/thread.condition.condvar/destructor.pass.cpp

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20150521/a5d11932/attachment.html>