Re: Thread Sanitizer additional tests
38 views
Skip to first unread message
Dmitry Vyukov
Aug 30, 2021, 2:27:08 AM8/30/21
to Alexey Katranov, thread-sanitizer
On Wed, 25 Aug 2021 at 15:10, Alexey Katranov <alexey....@gmail.com> wrote:
>
> Hi Dmitry,
>
> I hope you will not find it impolite to contact you personally via email. Some time ago, I promised to try to add some additional tests for Thread Sanitizer and disappeared due to pressure from the main job (Thread Sanitizer is some sort of my personal interest, so it is not always easy to find time for it).
>
> The good news is that we could add Thread Sanitizer as a part of the development process of oneTBB (formerly TBB), and found and fixed dozens of races.
+thread-sanitizer mailing list
[I am briefly back from a vacation, but will be OOO next 2 weeks
again, expect delays]
Hi Alexey,
That's great to hear!
> Thank you and your team for such a great tool. To tell the truth, about ten years ago we tried the Relacy Race Detector tool and while it showed good results we could not make it a part of the development process.
Yes, Relacy is somewhat hard to use, especially for continuous
testing. Based on experience with ThreadSanitizer I think Relacy
should be based on compiler instrumentation as well. But I don't have
time to reimplement it and the easier Relacy to use it, the closer it
is to ThreadSanitizer. So I think it's more promising to incrementally
add Relacy features to ThreadSanitizer instead. Namely, more precise
handling of atomic operations and memory fences, explicit control over
scheduling and support for repeated runs can be added to
ThreadSanitizer.
> As for the tests, I did not move forward to implement something but I thought about some approach. What do you think about the tests that check typical synchronization patterns and iterate over possible memory semantics? For example, the code below demonstrates usual concurrent list with "push" and "grab all" operations. In this example we can iterate over multiple memory semantics for memory barriers #2 and #4 to check that TSan does not produce false positives and negatives for all iterated pairs #2 in {relaxed, release, acq_rel, seq_cst} and #4 in {relaxed, acquire, acq_rel, seq_cst}. The reports are expected for "#2<release || #4<acquire" and reports are not expected for !(#2<release || #4<acquire). Do such tests make sense?
Yes, such tests make sense. I would not like them to be too large and
complex (e.g. something like a concurrent skip list), but something
like a lock-free stack looks fine.
It would be useful to have unit tests for all scenarios that your
proposed changes fix and that are currently broken.
There are 2 main possibilities to encode variations in a single test.
Either completely programmatically within a single test run:
https://github.com/llvm/llvm-project/blob/main/compiler-rt/test/tsan/atomic_race.cpp
https://github.com/llvm/llvm-project/blob/main/compiler-rt/test/tsan/atomic_norace.cpp
https://github.com/llvm/llvm-project/blob/main/compiler-rt/test/tsan/atomic_norace2.cpp
Or, using compiler defines and FileCheck --check-prefix flag:
https://github.com/llvm/llvm-project/blob/main/compiler-rt/test/tsan/ignore_lib0.cpp#L7-L11
The latter will run slower, but allows more precise checking or results.
> Additionally, we can iterate memory semantic for #1 and #3 when "#2<release || #4<acquire" is true to check that they do not hide reports.
>
> void test() {
> struct Node {
> int data{};
> Node* next;
> };
> std::atomic<Node*> head{ nullptr };
>
> auto concurrent_push = [&](Node* new_head) {
> auto expected = head.load(std::memory_order_relaxed /* 1 */);
> do {
> new_head->next = expected;
> } while (!head.compare_exchange_weak(expected, new_head, std::memory_order_release /* 2 */, std::memory_order_relaxed /* 3 */));
>
>
> };
> auto concurrent_grab_all = [&](Node* head) {
> auto h = head.exchange(nullptr, std::memory_order_acquire /* 4 */);
> while (h) {
> assert(h->data == 0);
> h = h->next;
> }
> };
> }
>
> Regards,
> Alex
>
> Hi Dmitry,
>
> I hope you will not find it impolite to contact you personally via email. Some time ago, I promised to try to add some additional tests for Thread Sanitizer and disappeared due to pressure from the main job (Thread Sanitizer is some sort of my personal interest, so it is not always easy to find time for it).
>
> The good news is that we could add Thread Sanitizer as a part of the development process of oneTBB (formerly TBB), and found and fixed dozens of races.
+thread-sanitizer mailing list
[I am briefly back from a vacation, but will be OOO next 2 weeks
again, expect delays]
Hi Alexey,
That's great to hear!
> Thank you and your team for such a great tool. To tell the truth, about ten years ago we tried the Relacy Race Detector tool and while it showed good results we could not make it a part of the development process.
Yes, Relacy is somewhat hard to use, especially for continuous
testing. Based on experience with ThreadSanitizer I think Relacy
should be based on compiler instrumentation as well. But I don't have
time to reimplement it and the easier Relacy to use it, the closer it
is to ThreadSanitizer. So I think it's more promising to incrementally
add Relacy features to ThreadSanitizer instead. Namely, more precise
handling of atomic operations and memory fences, explicit control over
scheduling and support for repeated runs can be added to
ThreadSanitizer.
> As for the tests, I did not move forward to implement something but I thought about some approach. What do you think about the tests that check typical synchronization patterns and iterate over possible memory semantics? For example, the code below demonstrates usual concurrent list with "push" and "grab all" operations. In this example we can iterate over multiple memory semantics for memory barriers #2 and #4 to check that TSan does not produce false positives and negatives for all iterated pairs #2 in {relaxed, release, acq_rel, seq_cst} and #4 in {relaxed, acquire, acq_rel, seq_cst}. The reports are expected for "#2<release || #4<acquire" and reports are not expected for !(#2<release || #4<acquire). Do such tests make sense?
Yes, such tests make sense. I would not like them to be too large and
complex (e.g. something like a concurrent skip list), but something
like a lock-free stack looks fine.
It would be useful to have unit tests for all scenarios that your
proposed changes fix and that are currently broken.
There are 2 main possibilities to encode variations in a single test.
Either completely programmatically within a single test run:
https://github.com/llvm/llvm-project/blob/main/compiler-rt/test/tsan/atomic_race.cpp
https://github.com/llvm/llvm-project/blob/main/compiler-rt/test/tsan/atomic_norace.cpp
https://github.com/llvm/llvm-project/blob/main/compiler-rt/test/tsan/atomic_norace2.cpp
Or, using compiler defines and FileCheck --check-prefix flag:
https://github.com/llvm/llvm-project/blob/main/compiler-rt/test/tsan/ignore_lib0.cpp#L7-L11
The latter will run slower, but allows more precise checking or results.
> Additionally, we can iterate memory semantic for #1 and #3 when "#2<release || #4<acquire" is true to check that they do not hide reports.
>
> void test() {
> struct Node {
> int data{};
> Node* next;
> };
> std::atomic<Node*> head{ nullptr };
>
> auto concurrent_push = [&](Node* new_head) {
> auto expected = head.load(std::memory_order_relaxed /* 1 */);
> do {
> new_head->next = expected;
> } while (!head.compare_exchange_weak(expected, new_head, std::memory_order_release /* 2 */, std::memory_order_relaxed /* 3 */));
>
>
> };
> auto concurrent_grab_all = [&](Node* head) {
> auto h = head.exchange(nullptr, std::memory_order_acquire /* 4 */);
> while (h) {
> assert(h->data == 0);
> h = h->next;
> }
> };
> }
>
> Regards,
> Alex
Dmitry Vyukov
Sep 17, 2021, 3:09:20 PM9/17/21
to Alexey Katranov, thread-sanitizer
n Wed, 1 Sept 2021 at 23:06, Alexey Katranov <alexey....@gmail.com> wrote:
>
> I prototyped the idea of variation tests: https://github.com/alexey-katranov/llvm-project/commit/fe373f14b8dc38e39c726b9605d3ec922f5fc0f1. Is the approach appropriate? Or does it make sense to reduce code duplication or rework it somehow?
>
> I am also thinking about adding lazy initialization and Peterson's algorithms if the approach is Ok.
Overall it looks fine. But it feels that it can be shortened somewhat.
I also found it somewhat hard to follow logic split over 3 files,
indirection, control inversions and test code intermixed with the
stack implementation.
Also if I am reading it correctly, it seems that only the main thread
prints "Test %d\n", but other threads can proceed to subsequent tests
and race. So that e.g. main thread only printed "Test 3", but other
threads already execute test 7 and produce a race on it. This will be
confusing to debug.
Also it seems that we don't check that all combinations of
mo1_arr/mo3_arr race, because there is only one "// CHECK:
ThreadSanitizer: data race" for all combinations. So if only 1 of them
races, the test will pass and we don't detect that other combinations
don't produce a race.
I am thinking about something along the following lines:
// RUN: %clangxx_tsan -O1 %s -o %t && %run %t 2>&1 | FileCheck %s
// RUN: %clangxx_tsan -O1 %s -DRACE -o %t && %deflake %run %t |
FileCheck %s --check-prefix=CHECK-RACE
#include "test.h"
struct Stack {
struct Node {
int data = 0;
Node *next;
};
Node* head = nullptr;
Stack(int mo1, int mo2, int mo3, int mo4) { ... }
void push(Node *n) { ... };
void grab_all() { ... }
};
void* Thread(Stack* s) {
s->push(new Stack::Node);
return 0;
}
int main() {
int test = 0;
#if RACE
for(auto& mo24 : {std::make_pair(__ATOMIC_RELAXED, __ATOMIC_RELAXED),
{__ATOMIC_RELAXED, __ATOMIC_ACQUIRE},
{__ATOMIC_RELAXED, __ATOMIC_RELEASE},
...
}) {
#else
for(auto& mo24 : {std::make_pair(__ATOMIC_RELEASE,__ATOMIC_ACQUIRE),
{__ATOMIC_RELEASE, __ATOMIC_ACQ_REL},
{__ATOMIC_RELEASE, __ATOMIC_SEQ_CST},
...
}) {
#endif
for (int mo1 : {__ATOMIC_RELAXED, __ATOMIC_ACQUIRE, __ATOMIC_SEQ_CST}) {
for (int mo3 : {__ATOMIC_RELAXED, __ATOMIC_ACQUIRE,
__ATOMIC_RELEASE, __ATOMIC_ACQ_REL, __ATOMIC_SEQ_CST}) {
printf(stderr, "TEST %d\n", test++);
Stack s(mo1, mo24.first, mo3, mo24.second);
pthread_t tt[3];
for (auto& t : tt)
pthread_create(&t, 0, Thread, &s);
s.grab_all();
for (auto t : tt)
pthread_join(t, 0);
s.grab_all();
}
}
}
}
}
// CHECK: TEST 0
// CHECK-NOT: ThreadSanitizer: data race
// CHECK: TEST 1
// CHECK-NOT: ThreadSanitizer: data race
...
// CHECK-RACE: TEST 0
// CHECK-RACE: ThreadSanitizer: data race
// CHECK-RACE: TEST 1
// CHECK-RACE: ThreadSanitizer: data race
...
> вт, 31 авг. 2021 г. в 14:22, Alexey Katranov <alexey....@gmail.com>:
>>
>> Thank you for your answer and advice. I'll come back if I make any progress.
>>
>> пн, 30 авг. 2021 г. в 09:27, Dmitry Vyukov <dvy...@google.com>:
>
> I prototyped the idea of variation tests: https://github.com/alexey-katranov/llvm-project/commit/fe373f14b8dc38e39c726b9605d3ec922f5fc0f1. Is the approach appropriate? Or does it make sense to reduce code duplication or rework it somehow?
>
> I am also thinking about adding lazy initialization and Peterson's algorithms if the approach is Ok.
Overall it looks fine. But it feels that it can be shortened somewhat.
I also found it somewhat hard to follow logic split over 3 files,
indirection, control inversions and test code intermixed with the
stack implementation.
Also if I am reading it correctly, it seems that only the main thread
prints "Test %d\n", but other threads can proceed to subsequent tests
and race. So that e.g. main thread only printed "Test 3", but other
threads already execute test 7 and produce a race on it. This will be
confusing to debug.
Also it seems that we don't check that all combinations of
mo1_arr/mo3_arr race, because there is only one "// CHECK:
ThreadSanitizer: data race" for all combinations. So if only 1 of them
races, the test will pass and we don't detect that other combinations
don't produce a race.
I am thinking about something along the following lines:
// RUN: %clangxx_tsan -O1 %s -o %t && %run %t 2>&1 | FileCheck %s
// RUN: %clangxx_tsan -O1 %s -DRACE -o %t && %deflake %run %t |
FileCheck %s --check-prefix=CHECK-RACE
#include "test.h"
struct Stack {
struct Node {
int data = 0;
Node *next;
};
Node* head = nullptr;
Stack(int mo1, int mo2, int mo3, int mo4) { ... }
void push(Node *n) { ... };
void grab_all() { ... }
};
void* Thread(Stack* s) {
s->push(new Stack::Node);
return 0;
}
int main() {
int test = 0;
#if RACE
for(auto& mo24 : {std::make_pair(__ATOMIC_RELAXED, __ATOMIC_RELAXED),
{__ATOMIC_RELAXED, __ATOMIC_ACQUIRE},
{__ATOMIC_RELAXED, __ATOMIC_RELEASE},
...
}) {
#else
for(auto& mo24 : {std::make_pair(__ATOMIC_RELEASE,__ATOMIC_ACQUIRE),
{__ATOMIC_RELEASE, __ATOMIC_ACQ_REL},
{__ATOMIC_RELEASE, __ATOMIC_SEQ_CST},
...
}) {
#endif
for (int mo1 : {__ATOMIC_RELAXED, __ATOMIC_ACQUIRE, __ATOMIC_SEQ_CST}) {
for (int mo3 : {__ATOMIC_RELAXED, __ATOMIC_ACQUIRE,
__ATOMIC_RELEASE, __ATOMIC_ACQ_REL, __ATOMIC_SEQ_CST}) {
printf(stderr, "TEST %d\n", test++);
Stack s(mo1, mo24.first, mo3, mo24.second);
pthread_t tt[3];
for (auto& t : tt)
pthread_create(&t, 0, Thread, &s);
s.grab_all();
for (auto t : tt)
pthread_join(t, 0);
s.grab_all();
}
}
}
}
}
// CHECK: TEST 0
// CHECK-NOT: ThreadSanitizer: data race
// CHECK: TEST 1
// CHECK-NOT: ThreadSanitizer: data race
...
// CHECK-RACE: TEST 0
// CHECK-RACE: ThreadSanitizer: data race
// CHECK-RACE: TEST 1
// CHECK-RACE: ThreadSanitizer: data race
...
> вт, 31 авг. 2021 г. в 14:22, Alexey Katranov <alexey....@gmail.com>:
>>
>> Thank you for your answer and advice. I'll come back if I make any progress.
>>
>> пн, 30 авг. 2021 г. в 09:27, Dmitry Vyukov <dvy...@google.com>:
Alexey Katranov
Sep 24, 2021, 4:31:13 AM9/24/21
to Dmitry Vyukov, thread-sanitizer
Thank you for the review. I agree that 3 file logic is complicated and your approach is much better (I did not figure out such trick with multiple "RUN"s)
As for output reordering, there are two barriers in LockFreeStack that should prevent reordering.
As for checking for all combinations, it is a really good catch. It turned out the tsan filtered out similar reports and the only one was reported. I added for_each_mo function instantiation for each combination to prevent filtering: https://github.com/alexey-katranov/llvm-project/commit/28f0a794d68137cec37bc20490cfce08c1537606#diff-77d52e39b237f5433a63eddaff81d8fcce23f3b495dfe258d143d3dda7e372c0R62-R71. Is it a reasonable approach?
The current patch (https://github.com/alexey-katranov/llvm-project/commit/28f0a794d68137cec37bc20490cfce08c1537606) contains the test only for fenced atomics. I will do the same for standalone fences if you are Ok with the current approach.
пт, 17 сент. 2021 г. в 22:09, Dmitry Vyukov <dvy...@google.com>:
Dmitry Vyukov
Sep 27, 2021, 5:56:58 AM9/27/21
to Alexey Katranov, thread-sanitizer
On Fri, 24 Sept 2021 at 10:26, Alexey Katranov
phabricator. We can shake out minor details there.
<alexey....@gmail.com> wrote:
>
> Thank you for the review. I agree that 3 file logic is complicated and your approach is much better (I did not figure out such trick with multiple "RUN"s)
>
> As for output reordering, there are two barriers in LockFreeStack that should prevent reordering.
>
> As for checking for all combinations, it is a really good catch. It turned out the tsan filtered out similar reports and the only one was reported. I added for_each_mo function instantiation for each combination to prevent filtering: https://github.com/alexey-katranov/llvm-project/commit/28f0a794d68137cec37bc20490cfce08c1537606#diff-77d52e39b237f5433a63eddaff81d8fcce23f3b495dfe258d143d3dda7e372c0R62-R71. Is it a reasonable approach?
>
> The current patch (https://github.com/alexey-katranov/llvm-project/commit/28f0a794d68137cec37bc20490cfce08c1537606) contains the test only for fenced atomics. I will do the same for standalone fences if you are Ok with the current approach.
Please send what you have now as a patch for llvm compiler-rt using
>
> Thank you for the review. I agree that 3 file logic is complicated and your approach is much better (I did not figure out such trick with multiple "RUN"s)
>
> As for output reordering, there are two barriers in LockFreeStack that should prevent reordering.
>
> As for checking for all combinations, it is a really good catch. It turned out the tsan filtered out similar reports and the only one was reported. I added for_each_mo function instantiation for each combination to prevent filtering: https://github.com/alexey-katranov/llvm-project/commit/28f0a794d68137cec37bc20490cfce08c1537606#diff-77d52e39b237f5433a63eddaff81d8fcce23f3b495dfe258d143d3dda7e372c0R62-R71. Is it a reasonable approach?
>
> The current patch (https://github.com/alexey-katranov/llvm-project/commit/28f0a794d68137cec37bc20490cfce08c1537606) contains the test only for fenced atomics. I will do the same for standalone fences if you are Ok with the current approach.
phabricator. We can shake out minor details there.
Alexey Katranov
Sep 27, 2021, 7:22:37 AM9/27/21
to Dmitry Vyukov, thread-sanitizer
I never contributed to llvm and do not know the process, can you please point me to some kind of "how to" or getting started guide?
пн, 27 сент. 2021 г. в 12:56, Dmitry Vyukov <dvy...@google.com>:
Alexey Katranov
Sep 27, 2021, 7:30:08 AM9/27/21
to Dmitry Vyukov, thread-sanitizer
Dmitry Vyukov
Sep 27, 2021, 7:32:57 AM9/27/21
to Alexey Katranov, thread-sanitizer
Yes, this is the correct guide.
If you manage to install arc command, it makes things easier.
On Mon, 27 Sept 2021 at 13:30, Alexey Katranov
If you manage to install arc command, it makes things easier.
On Mon, 27 Sept 2021 at 13:30, Alexey Katranov
Alexey Katranov
Sep 27, 2021, 10:59:34 AM9/27/21
to Dmitry Vyukov, thread-sanitizer
The patch in phabricator: https://reviews.llvm.org/D110552
пн, 27 сент. 2021 г. в 14:32, Dmitry Vyukov <dvy...@google.com>:
Reply all
Reply to author
Forward
0 new messages