[TSAN] Honor failure memory orders in AtomicCAS

[bruno]

Summary

LLVM has lifted strong requirements for CAS failure memory orders in 431e3138a and 819e0d105e84.

Add support for honoring them in AtomicCAS.

https://github.com/google/sanitizers/issues/970

[bruno]

Ping.

[delcypher]

@bruno Thanks for the patch. TSan's runtime isn't my specialty so I've added other reviewers.

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

435

Is this something user facing code can set? If yes, then we might want to emit a warning rather than crashing the process.

[yln]

I am happy with the mechanics and quality of the patch. Ideally @dvyukov could give a final sign-off.

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

435

I think calls are generated by the compiler in ThreadSanitizer::instrumentAtomic():

Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
                 CmpOperand,
                 NewOperand,
                 createOrdering(&IRB, CASI->getSuccessOrdering()),
                 createOrdering(&IRB, CASI->getFailureOrdering())};
CallInst *C = IRB.CreateCall(TsanAtomicCAS[Idx], Args);

[bruno]

Thanks both of you for the review @delcypher and @yln, will wait for @dvyukov to sign-off!

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

435

Right, but before things are expanded for instrumentation, there's some sanitization of the failure memory order in emitAtomicCmpXchgFailureSet, so an invalid combination shouldn't get to this point.

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

436

Can't fmo be consume/acq_rel/seq_cst? If yes, please add a test.

438

I think we should not search the object and re-acquire the mutex second time for performance reasons and complexity (won't need to re-read the value).
Note that we may have already acquired due to mo. We should not acquire second time in that case.

445

I don't think this is correct. Can't this lead to false positives?
Consider that a thread does CAS-release to hand off the object to another thread, and that thread frees the object. I think this memory access can race with the free. It's generally not OK to touch memory after atomic operations.
If if leads to a false positive, please add a test that catches it.

compiler-rt/test/tsan/compare_exchange_release_relaxed.cpp

18 ↗

(On Diff #333603)

If this test differs only by memory order, it can make sense to use parametrized tests. It would also be good to test other mo combinations (e.g. that the CHECK(IsLoadOrder(fmo)) does not fail).
See e.g. test/tsan/ignore_lib0.cpp for an example.

[dvyukov]

Also I wonder if we could first evaluate CAS and then use either mo or fmo accordingly, so that we don't over-synchronize on failure if mo is stronger than fmo.

[dvyukov]

Not directly related to the change but we could also episodically fail weak CASes to test fmo case better.

[yln]

Unapprove until Dmitry's comments are addressed.

[bruno]

Address reviewer comments. To prevent false positive on release/consume, this now depends on https://reviews.llvm.org/D101501.

[bruno]

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

436

Added several variations. The consume failing order currently fallbacks to monotonic in LLVM, just opened https://reviews.llvm.org/D101501 to be consistent with success and fallback to acquire instead, without this change it leads to false positive, thanks for bringing this up.

445

Looks like I overthought the approach, thanks for pointing out.

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

413

I think it's better to avoid doing this if the CAS will fail and fmo == mo_relaxed. It will provide more precise race detection.
I think we could do something along the following lines:

• if either mo or fmo != relaxed, do GetOrCreateAndLock
• if either mo or fmo involves release, do a write lock
• evaluate cas
• respect mo or fmo based on the cas result

438

We did not create/obtain the sync object if mo == mo_relaxed. Is mo == mo_relaxed and fmo == mo_acquire possible? If yes, then we will fail to respect fmo.

440

We used a different condition to decide if we need to do read lock. Can't this deadlock? I think we need to check write_lock.

[bruno]

Apply review comments.

Note that we cannot test mo == relaxed and fmo == anything yet because LLVM fallbacks to relaxed/relaxed.

Remove the dep on https://reviews.llvm.org/D101501 for now, since there's even more stuff to improve in LLVM before we get this 100% right, at least we've got release/acquire working as of this patch. I'll come back to fix the other tests once LLVM is fixed.

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

413

Sounds good, minor correction on the fact that fmo cannot be release.

438

Right, will fix.

440

Yea, somehow it slipped, thanks!

[bruno]

Update broken comment in the testcase.

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

413

Do I wait for this in this change? I see we still acquire/release before evaluating CAS. Or you want to do it later with other improvements you mentioned?

433

Better to do in the beginning of the function.

440

With the current code it makes sense to do "IsAcquireOrder(fmo) && !IsAcquireOrder(mo)", because otherwise we already acquired.
But even better what's discussed above: first evaluate CAS, then decide what order to use.

[bruno]

Apply more reviewer suggested changes: first evaluate CAS, then decide what order to use.

Now that LLVM side of this is fixed, also cover all fmo's allowed, add more tests.

[bruno]

Cover more cases in atomic.ll.

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

405

Can it be seq_cst?
If yes, then I think write_lock below is incorrect and checking only IsAcquireOrder(fmo) is incorrect as well.

421

The CAS needs to be evaluated under the sync object mutex, otherwise we can get inconsistent value/memory visibility. If we are going to lock the mutex, we need to lock it before CAS.

[bruno]

Thank you @dvyukov for another round of reviews! A have more questions for you.

Yes, fmo can be seq_cst. Take mo == mo_release and fmo == mo_seq_cst, we'd be acquiring the mutex with write_lock, which is fine under success. However, during failure, I don't see another solution besides s->mtx.Unlock() before honoring and calling GetOrCreateAndLock again to obtain the lock with write_lock = false. Since you said in a previous review that it would be too expensive to lock again, what do you suggest as an alternative? I wonder whether my concern is even legit (?) given that the mo == mo_release and fmo == mo_seq_cst in the testcase works regardless of this lock/unlock dance.

It's also the case that the current added testcase takes ~20s on a fast linux machine, which seems way over the bar, I haven't tried to make it better yet, but (at least) diminishing the mo/fmo combinations should help, other ideas?

In the meantime, I've updated the patch with that approach.

[dvyukov]

In D99434#2748778, @bruno wrote:

Thank you @dvyukov for another round of reviews! A have more questions for you.

Yes, fmo can be seq_cst. Take mo == mo_release and fmo == mo_seq_cst, we'd be acquiring the mutex with write_lock, which is fine under success. However, during failure, I don't see another solution besides s->mtx.Unlock() before honoring and calling GetOrCreateAndLock again to obtain the lock with write_lock = false. Since you said in a previous review that it would be too expensive to lock again, what do you suggest as an alternative? I wonder whether my concern is even legit (?) given that the mo == mo_release and fmo == mo_seq_cst in the testcase works regardless of this lock/unlock dance.

We don't need to re-lock in read mode. We can lock in the strongest mode: write lock if either mo or fmo requires a release, and then do acquire under write if it turned out we need only acquire. It's fine to read a data structure under write lock.

[dvyukov]

In D99434#2748778, @bruno wrote:

Thank you @dvyukov for another round of reviews! A have more questions for you.

Yes, fmo can be seq_cst. Take mo == mo_release and fmo == mo_seq_cst, we'd be acquiring the mutex with write_lock, which is fine under success. However, during failure, I don't see another solution besides s->mtx.Unlock() before honoring and calling GetOrCreateAndLock again to obtain the lock with write_lock = false. Since you said in a previous review that it would be too expensive to lock again, what do you suggest as an alternative? I wonder whether my concern is even legit (?) given that the mo == mo_release and fmo == mo_seq_cst in the testcase works regardless of this lock/unlock dance.

It's also the case that the current added testcase takes ~20s on a fast linux machine, which seems way over the bar, I haven't tried to make it better yet, but (at least) diminishing the mo/fmo combinations should help, other ideas?

This is too long. But I think it's just to the "atexit sleep" in tsan. You can do this, and maybe even set atexit_sleep_ms to 0:

test/tsan/fork_atexit.cpp:// RUN: %clangxx_tsan -O1 %s -o %t && %env_tsan_opts=atexit_sleep_ms=50 %run %t 2>&1 | FileCheck %s

[bruno]

Cool, thanks for the input!

• Update the patch to prevent unnecessary lock/unlock dance.
• Changing atexit_sleep_ms didn't really changed the ballpark, rewrite test to include all checks in one run, this brings it down to 1.5-2s total time.

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

405

If I am not missing something, I think this comment still holds:

Can it be seq_cst?
If yes, then I think write_lock below is incorrect and checking only IsAcquireOrder(fmo) is incorrect as well.

443

There is some duplication here between handling of success case and failure case: adding to trace, acquire, unlock. And taking into account that fmo can be seq_cst, we will need even more duplication to fix this, e.g. we may need to do Release and WriteUnlock here.
I would structure it along the following lines (it should both handle all cases and avoid duplication at the same time):

SyncVar *s = 0;
bool write_lock = IsReleaseOrder(mo) || IsReleaseOrder(fmo);
if (mo != mo_relaxed || fmo != mo_relaxed)
  s = ctx->metamap.GetOrCreateAndLock(thr, pc, (uptr)a, write_lock);

T cc = *c;
T pr = func_cas(a, cc, v);
bool success = pr == cc;
if (!success) {
  *c = pr;
  mo = fmo;
}
if (s) {
  thr->fast_state.IncrementEpoch();
  // Can't increment epoch w/o writing to the trace as well.
  TraceAddEvent(thr, thr->fast_state, EventTypeMop, 0);
  if (IsAcqRelOrder(mo))
    AcquireReleaseImpl(thr, pc, &s->clock);
  else if (IsReleaseOrder(mo))
    ReleaseImpl(thr, pc, &s->clock);
  else if (IsAcquireOrder(mo))
    AcquireImpl(thr, pc, &s->clock);

  if (write_lock)
    s->mtx.Unlock();
  else
    s->mtx.ReadUnlock();
}
return success;

[bruno]

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

405

If I am not missing something, I think this comment still holds:

Can it be seq_cst?

Yes, I also added tests to cover that.

If yes, then I think write_lock below is incorrect and checking only IsAcquireOrder(fmo) is incorrect as well.

See my next comment.

443

fmo cannot be mo_release or mo_acq_rel, and when it's mo_seq_cst my understanding (which could be wrong) is that it has load semantics. @rjmccall @jfb does my understanding makes sense?

With that in mind, write_lock only needs to track IsReleaseOrder(mo), which is what the current patch does.

[bruno]

Update patch to reduce code dup as suggested by @dvyukov

[dvyukov]

I don't see any issues now. Thanks for bearing with me.

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

435

"success &&" is unnecessary here right?
I see it's not harmful, but it also makes me a but nervous because we used just the "write_lock" condition when locking, but we use a different one when unlocking. This is not symmetric and have some potential to get out of sync, so I would drop "success &&" part here.

443

I think you are right. This makes sense.

[bruno]

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

435

No problemo, will do. Thanks for the careful review!

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp

 static T NoTsanAtomicCAS(volatile T *a, T c, T v, morder mo, morder fmo) {
   NoTsanAtomicCAS(a, &c, v, mo, fmo);
   return c;
 }
 
 template<typename T>
 static bool AtomicCAS(ThreadState *thr, uptr pc,
     volatile T *a, T *c, T v, morder mo, morder fmo) {
-  (void)fmo;  // Unused because llvm does not pass it yet.
   MemoryWriteAtomic(thr, pc, (uptr)a, SizeLog<T>());
   SyncVar *s = 0;
   bool write_lock = mo != mo_acquire && mo != mo_consume;
   if (mo != mo_relaxed) {
     s = ctx->metamap.GetOrCreateAndLock(thr, pc, (uptr)a, write_lock);
     thr->fast_state.IncrementEpoch();
     // Can't increment epoch w/o writing to the trace as well.
     TraceAddEvent(thr, thr->fast_state, EventTypeMop, 0);
     if (IsAcqRelOrder(mo))
       AcquireReleaseImpl(thr, pc, &s->clock);
     else if (IsReleaseOrder(mo))
       ReleaseImpl(thr, pc, &s->clock);
     else if (IsAcquireOrder(mo))
       AcquireImpl(thr, pc, &s->clock);
   }
   T cc = *c;
   T pr = func_cas(a, cc, v);
-  if (s) {
+  if (pr == cc) {
+    if (!s) return true;
     if (write_lock)
       s->mtx.Unlock();
     else
       s->mtx.ReadUnlock();
-  }
-  if (pr == cc)
     return true;
+  }
+
+  // Honor failure memory order.
   *c = pr;
+  CHECK(IsLoadOrder(fmo));
+
+  // 31.7.2.18: "The failure argument shall not be memory_order_release
+  // nor memory_order_acq_rel". LLVM fallbacks to Monotonic (relaxed) when
+  // those are used.
+  if (IsAcquireOrder(fmo) && s) {
+    AcquireImpl(thr, pc, &s->clock);
+    s->mtx.ReadUnlock();
+  }
+
   return false;
 }
 
 template<typename T>
 static T AtomicCAS(ThreadState *thr, uptr pc,
     volatile T *a, T c, T v, morder mo, morder fmo) {
   AtomicCAS(thr, pc, a, &c, v, mo, fmo);
   return c;
 }
 
 #if !SANITIZER_GO

compiler-rt/test/tsan/compare_exchange.cpp

+// RUN: %clangxx_tsan -O1 %s %link_libcxx_tsan -DRELEASE_ACQUIRE -o %t && %run %t 2>&1 | FileCheck %s
+// RUN: %clangxx_tsan -O1 %s %link_libcxx_tsan -DRELEASE_RELAXED -o %t && %deflake %run %t 2>&1 | FileCheck --check-prefix=CHECK-RELEASE-RELAXED %s
+// RUN: %clangxx_tsan -O1 %s %link_libcxx_tsan -DRELACQ_ACQUIRE -o %t && %run %t 2>&1 | FileCheck %s
+// RUN: %clangxx_tsan -O1 %s %link_libcxx_tsan -DRELACQ_RELAXED -o %t && %run %t 2>&1 | FileCheck %s
+// RUN: %clangxx_tsan -O1 %s %link_libcxx_tsan -DRELEASE_CONSUME -o %t && %run %t 2>&1 | FileCheck %s
+// RUN: %clangxx_tsan -O1 %s %link_libcxx_tsan -DSEQ_CST_RELAX -o %t && %run %t 2>&1 | FileCheck %s
+// RUN: %clangxx_tsan -O1 %s %link_libcxx_tsan -DSEQ_CST_ACQUIRE -o %t && %run %t 2>&1 | FileCheck %s
+// RUN: %clangxx_tsan -O1 %s %link_libcxx_tsan -DSEQ_CST_CONSUME -o %t && %run %t 2>&1 | FileCheck %s
+#include <atomic>
+#include <cassert>
+#include <thread>
+#include <stdio.h>
+
+#ifdef RELEASE_ACQUIRE
+static constexpr auto SuccessOrder = std::memory_order_release;
+static constexpr auto FailureOrder = std::memory_order_acquire;
+#endif
+
+#ifdef RELEASE_RELAXED
+static constexpr auto SuccessOrder = std::memory_order_release;
+static constexpr auto FailureOrder = std::memory_order_relaxed;
+#endif
+
+#ifdef RELACQ_ACQUIRE
+static constexpr auto SuccessOrder = std::memory_order_acq_rel;
+static constexpr auto FailureOrder = std::memory_order_acquire;
+#endif
+
+#ifdef RELACQ_RELAXED
+static constexpr auto SuccessOrder = std::memory_order_acq_rel;
+static constexpr auto FailureOrder = std::memory_order_relaxed;
+#endif
+
+#ifdef RELEASE_CONSUME
+static constexpr auto SuccessOrder = std::memory_order_release;
+static constexpr auto FailureOrder = std::memory_order_consume;
+#endif
+
+#ifdef SEQ_CST_RELAX
+static constexpr auto SuccessOrder = std::memory_order_seq_cst;
+static constexpr auto FailureOrder = std::memory_order_relaxed;
+#endif
+
+#ifdef SEQ_CST_ACQUIRE
+static constexpr auto SuccessOrder = std::memory_order_seq_cst;
+static constexpr auto FailureOrder = std::memory_order_acquire;
+#endif
+
+#ifdef SEQ_CST_CONSUME
+static constexpr auto SuccessOrder = std::memory_order_seq_cst;
+static constexpr auto FailureOrder = std::memory_order_consume;
+#endif
+
+struct node { int val; };
+std::atomic<node*> _node{nullptr};
+
+void f1() {
+  auto n = new node();
+  n->val = 42;
+  _node.store(n, std::memory_order_release);
+}
+
+void f2() {
+  node* expected = nullptr;
+  while (expected == nullptr) {
+    _node.compare_exchange_weak(expected, nullptr, SuccessOrder,
+                                FailureOrder);
+  };
+
+  ++expected->val;
+  assert(expected->val == 43);
+}
+
+int main() {
+  std::thread t1(f1);
+  std::thread t2(f2);
+
+  t1.join();
+  t2.join();
+
+  fprintf(stderr, "DONE\n");
+  return 0;
+}
+
+// CHECK-NOT: WARNING: ThreadSanitizer: data race
+// CHECK: DONE
+
+// CHECK-RELEASE-RELAXED: WARNING: ThreadSanitizer: data race
 No newline at end of file

llvm/test/Instrumentation/ThreadSanitizer/atomic.ll

 define void @atomic8_cas_release(i8* %a) nounwind uwtable {
 entry:
   cmpxchg i8* %a, i8 0, i8 1 release monotonic, !dbg !7
   ret void, !dbg !7
 }
 ; CHECK-LABEL: atomic8_cas_release
 ; CHECK: call i8 @__tsan_atomic8_compare_exchange_val(i8* %a, i8 0, i8 1, i32 3, i32 0), !dbg
 
+define void @atomic8_cas_rel_acq(i8* %a) nounwind uwtable {
+entry:
+  cmpxchg i8* %a, i8 0, i8 1 release acquire, !dbg !7
+  ret void, !dbg !7
+}
+; CHECK-LABEL: atomic8_cas_rel_acq
+; CHECK: call i8 @__tsan_atomic8_compare_exchange_val(i8* %a, i8 0, i8 1, i32 3, i32 2), !dbg
+
 define void @atomic8_cas_acq_rel(i8* %a) nounwind uwtable {
 entry:
   cmpxchg i8* %a, i8 0, i8 1 acq_rel acquire, !dbg !7
   ret void, !dbg !7
 }
 ; CHECK-LABEL: atomic8_cas_acq_rel
 ; CHECK: call i8 @__tsan_atomic8_compare_exchange_val(i8* %a, i8 0, i8 1, i32 4, i32 2), !dbg