[tsan] Intercept libcxx __release_shared to avoid false positive with weak_ptrs and destructors in C++

[kubamracek]

Summary

There is a “well-known” TSan false positive when using C++ weak_ptr/shared_ptr and code in destructors, e.g. described at https://llvm.org/bugs/show_bug.cgi?id=22324. The “standard" solution is to build and use a TSan-instrumented version of libcxx, which is not trivial for end-users. This patch tries a different approach (on OS X): It adds an interceptor for the specific function in libc++.dylib, which implements the atomic operation that needs to be visible to TSan.

The API/ABI of libc++.dylib is stable on OS X, so adding this interceptor is compatible with all OS versions. I went through the sources of libcxx and this seems to be the only function that needs to be intercepted.

[dvyukov]

lib/tsan/rtl/tsan_interceptors_mac.cc

286 ↗

(On Diff #61547)

Why we don't need to intercept release of weak references?
Is it that last shared references releases weak, or vice versa?

289 ↗

(On Diff #61547)

I think Acquire should happen _after_ the actual release to synchronize with all preceding Release's.
Normally, you can't touch the object after release in all but the last thread, because the object can already be freed (unmapped). So ideally we need to determine the last thread and do Acquire only in it.
But I wonder if tsan Release is OK -- it won't touch object memory.

[kubamracek]

lib/tsan/rtl/tsan_interceptors_mac.cc

286 ↗

(On Diff #61547)

As far as I know, the destructor of the object is only called when the last shared reference is destroyed. Weak references don’t matter, as they don’t run the destructor. The only issue I’m trying to solve here is a false positive when the destructor of a user’s object is called when the last shared reference is freed. I’m not aware of other false positives with C++ shared/weak pointers.

289 ↗

(On Diff #61547)

I’m not sure what you’re suggesting here -- are you saying that Acquire should be at the end of the interceptor? Note that o here isn’t the user’s object, nor the shared_ptr, it’s the control block, which is heap-allocated. I actually think that even in the last thread (last shared reference is destroyed), o is already destroyed when the REAL() call finishes (the object destroys itself).

Secondly, I remember accidentally calling Release() on just-freed memory, which resulted in subtle crashes and many wasted hours of debugging. I was actually thinking of implementing a DCHECK that would trigger whenever Release or Acquire is called on a deallocated heap object.

What is the problem you’re seeing here with this patch? Is it about two threads doing Acquires first and only then doing Releases, in which case we’d still report a false positive? Then it sounds we need an atomic Acquire+Release, which we could solve with some atomic CAS loop or, worst case, a spinlock.

Suggestions?

[dvyukov]

lib/tsan/rtl/tsan_interceptors_mac.cc

289 ↗

(On Diff #61547)

Is it about two threads doing Acquires first and only then doing Releases, in which case we’d still report a false positive?

Yes.
I see there are some other helper functions that return true/false and don't destroy the object. Is it possible to intercept any of them?

[kubamracek]

lib/tsan/rtl/tsan_interceptors_mac.cc

289 ↗

(On Diff #61547)

I don’t think so, unfortunately. The other functions get inlined into __shared_weak_count::__release_shared and they’re not called directly.

[dvyukov]

lib/tsan/rtl/tsan_interceptors_mac.cc

289 ↗

(On Diff #61547)

The simplest and the most reliable thing would be:

u64 shared_ptr_sync[kSomePrime];

uptr sync = (uptr)&shared_ptr_sync[hash(o) % kSomePrime];
Release(thr, pc, sync);
SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();
REAL(_ZNSt3__119__shared_weak_count16__release_sharedEv)(o);
SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();
Acquire(thr, pc, sync);

Note that kSomePrime should not be too large, because eventually every slot will contain maximally-sized vector clock which takes 8*num_threads bytes.

Also comment it all.

[kubamracek]

lib/tsan/rtl/tsan_interceptors_mac.cc

289 ↗

(On Diff #61547)

I’m probably missing some point. This doesn’t work in the case when two threads release a shared ptr: T1 calls Release(), T2 calls Release(), T1 calls REAL(), T2 calls REAL(), which is the last reference, it gets destroyed, the user’s object destructor is called and we report a false positive (because there hasn’t been any acquires at all). If I put a Sleep(1) before Acquire(), the test case I provided reports the false positive reliably.

[dvyukov]

You are right.

Then we can try:

Mutex shared_ptr_sync[kSomePrime];

Mutex *mtx = &shared_ptr_sync[hash(o) % kSomePrime];
mtx.Lock();
Acquire(thr, pc, o);
Release(thr, pc, o);
SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();
REAL(_ZNSt3__119__shared_weak_count16__release_sharedEv)(o);
SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();
mtx.Unlock();

But I am scared by potential consequences of running user code under internal mutex...

[kubamracek]

In D21609#465566, @dvyukov wrote:

You are right.

Then we can try:

Mutex shared_ptr_sync[kSomePrime];

Mutex *mtx = &shared_ptr_sync[hash(o) % kSomePrime];
mtx.Lock();
Acquire(thr, pc, o);
Release(thr, pc, o);
SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();
REAL(_ZNSt3__119__shared_weak_count16__release_sharedEv)(o);
SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();
mtx.Unlock();

But I am scared by potential consequences of running user code under internal mutex...

Can we unlock before calling the user code? It sounds to me we just need the Acquire+Release to be atomic.

[dvyukov]

No, we need them to be atomic with free.
Consider:
T1 does Acq+Rel
T2 does Acq+Rel
T2 releases reference
T1 releases reference and frees the object
free is not synchronized with T2

[kubamracek]

In D21609#465569, @dvyukov wrote:

No, we need them to be atomic with free.
Consider:
T1 does Acq+Rel
T2 does Acq+Rel
T2 releases reference
T1 releases reference and frees the object
free is not synchronized with T2

Ah, you’re right.

Do we have a recursive mutex in the runtime? I’m afraid destroying another shared_ptr from the destructor is quite likely.

[dvyukov]

Uh, if destructor is called there, then it won't work. Recursive mutexes won't help. A destructor can spawn another thread and wait for its completion, while the other thread can destroy other shared_ptr's which in turn will try to acquire the same mutex.

[kubamracek]

In D21609#465611, @dvyukov wrote:

Uh, if destructor is called there, then it won't work. Recursive mutexes won't help. A destructor can spawn another thread and wait for its completion, while the other thread can destroy other shared_ptr's which in turn will try to acquire the same mutex.

:(

Okay, another option: Reimplementing the __release_shared method without calling REAL(). Either we could cast it to a carefully-crafted C++ class that’s set up in the same way as __shared_weak_count is, or we could do some extremely ugly pointer arithmetics & vtable magic. But it should work, because the ABI is (and needs to be) stable. Opinions?

[dvyukov]

I can only think of other ugly solutions.
But first I need to ask: have you considered bundling tsan-instrumented libc++ with clang? It would benefit asan/tsan, and is a requirement for msan.

[kubamracek]

In D21609#465655, @dvyukov wrote:

I can only think of other ugly solutions.
But first I need to ask: have you considered bundling tsan-instrumented libc++ with clang? It would benefit asan/tsan, and is a requirement for msan.

Yes. I'm able to build it and use it. But distributing it to users is logistically extremely problematic. The original library ships with the OS, but we cannot ship an instrumented version as well, because that depends on the version of the instrumentation. Having the dylib in the toolchain would yet again complicate a lot of use cases, like deploying to different machines (e.g. for testing).

Having an interceptor (or a few of them), even when it's ugly and complex, is by far the easiest option for us.

[kubamracek]

Updating the patch to re-implement the whole method using.

[dvyukov]

I can't make my mind. I well understand that saying users "build your own tsan-instrumented libcxx" is close to having no answer at all. So I guess if that's the solution you want to maintain, I am OK with it.

Does it make sense to add a runtime flag that turns the interceptor off for emergency cases?

Also please document all alternatives that we've considered and why they don't work.

I would also write some kind of a stress test that creates/destroys shared_ptrs from different threads and takes/releases strong/weak references.

One other alternative is to insert empty non-inlinable hook functions into libcxx so that tsan can intercept them. But that will slow down normal execution, so I guess people will complain.

[kubamracek]

Updating patch, adding comment, adding a flag to disable the interceptor, adding a test for recursive shared_ptr destruction, adding a stress test.

[dvyukov]

LGTM if you agree to change acq_rel to release

lib/tsan/rtl/tsan_interceptors_mac.cc

309 ↗

(On Diff #61771)

Since we are reimplementing the whole function we can actually do better than the original. The problem (for tsan) with mo_acq_rel is that all threads synchronize with each other, while only the last thread needs to synchronize with all other threads. So I would suggest to do:

if (__tsan_atomic64_fetch_add(&o->shared_owners, -1, mo_release) == 0) {
  Acquire(thr, pc, &o->shared_owners);
  o->on_zero_shared();
  if (__tsan_atomic64_fetch_add(&o->shared_weak_owners, -1, mo_release) == 0)
    Acquire(thr, pc, &o->shared_weak_owners);
    o->on_zero_shared_weak();
  }
}

[dvyukov]

... and tests pass after that

compiler-rt/trunk/lib/tsan/rtl/tsan_flags.inc

TSAN_FLAG(int, io_sync, 1,
           "0 - no synchronization "
           "1 - reasonable level of synchronization (write->read)"
           "2 - global synchronization of all IO operations.")
 TSAN_FLAG(bool, die_after_fork, true,
           "Die after multi-threaded fork if the child creates new threads.")
 TSAN_FLAG(const char *, suppressions, "", "Suppressions file name.")
 TSAN_FLAG(bool, ignore_interceptors_accesses, false,
           "Ignore reads and writes from all interceptors.")
+TSAN_FLAG(bool, shared_ptr_interceptor, true,
+          "Track atomic reference counting in libc++ shared_ptr and weak_ptr.")

compiler-rt/trunk/lib/tsan/rtl/tsan_interceptors_mac.cc

xpc_handler_t new_handler = ^(xpc_object_t object) {
       Acquire(thr, pc, (uptr)connection);
     }
     handler(object);
   };
   REAL(xpc_connection_send_message_with_reply)
   (connection, message, replyq, new_handler);
 }
 
+// On macOS, libc++ is always linked dynamically, so intercepting works the
+// usual way.
+#define STDCXX_INTERCEPTOR TSAN_INTERCEPTOR
+
+namespace {
+struct fake_shared_weak_count {
+  volatile a64 shared_owners;
+  volatile a64 shared_weak_owners;
+  virtual void _unused_0x0() = 0;
+  virtual void _unused_0x8() = 0;
+  virtual void on_zero_shared() = 0;
+  virtual void _unused_0x18() = 0;
+  virtual void on_zero_shared_weak() = 0;
+};
+}  // namespace
+
+// This adds a libc++ interceptor for:
+//     void __shared_weak_count::__release_shared() _NOEXCEPT;
+// Shared and weak pointers in C++ maintain reference counts via atomics in
+// libc++.dylib, which are TSan-invisible, and this leads to false positives in
+// destructor code.  This interceptor re-implements the whole function so that
+// the mo_acq_rel semantics of the atomic decrement are visible.
+//
+// Unfortunately, this interceptor cannot simply Acquire/Release some sync
+// object and call the original function, because it would have a race between
+// the sync and the destruction of the object.  Calling both under a lock will
+// not work because the destructor can invoke this interceptor again (and even
+// in a different thread, so recursive locks don't help).
+STDCXX_INTERCEPTOR(void, _ZNSt3__119__shared_weak_count16__release_sharedEv,
+                   fake_shared_weak_count *o) {
+  if (!flags()->shared_ptr_interceptor)
+    return REAL(_ZNSt3__119__shared_weak_count16__release_sharedEv)(o);
+
+  SCOPED_TSAN_INTERCEPTOR(_ZNSt3__119__shared_weak_count16__release_sharedEv,
+                          o);
+  if (__tsan_atomic64_fetch_add(&o->shared_owners, -1, mo_release) == 0) {
+    Acquire(thr, pc, (uptr)&o->shared_owners);
+    o->on_zero_shared();
+    if (__tsan_atomic64_fetch_add(&o->shared_weak_owners, -1, mo_release) ==
+        0) {
+      Acquire(thr, pc, (uptr)&o->shared_weak_owners);
+      o->on_zero_shared_weak();
+    }
+  }
+}
+
 }  // namespace __tsan
 
 #endif  // SANITIZER_MAC

compiler-rt/trunk/test/tsan/Darwin/libcxx-shared-ptr-recursive.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation
+// RUN: %env_tsan_opts=ignore_interceptors_accesses=1 %run %t 2>&1 | FileCheck %s
+
+#import <Foundation/Foundation.h>
+
+#import <memory>
+
+struct InnerStruct {
+  ~InnerStruct() {
+    fprintf(stderr, "~InnerStruct\n");
+  }
+};
+
+struct MyStruct {
+  std::shared_ptr<InnerStruct> inner_object;
+  ~MyStruct() {
+    fprintf(stderr, "~MyStruct\n");
+  }
+};
+
+int main(int argc, const char *argv[]) {
+  fprintf(stderr, "Hello world.\n");
+
+  {
+    std::shared_ptr<MyStruct> shared(new MyStruct());
+    shared->inner_object = std::shared_ptr<InnerStruct>(new InnerStruct());
+  }
+
+  fprintf(stderr, "Done.\n");
+}
+
+// CHECK: Hello world.
+// CHECK: ~MyStruct
+// CHECK: ~InnerStruct
+// CHECK: Done.
+// CHECK-NOT: WARNING: ThreadSanitizer

compiler-rt/trunk/test/tsan/Darwin/libcxx-shared-ptr-stress.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation
+// RUN: %env_tsan_opts=ignore_interceptors_accesses=1 %run %t 2>&1 | FileCheck %s
+
+#import <Foundation/Foundation.h>
+
+#import <assert.h>
+#import <memory>
+#import <stdatomic.h>
+
+_Atomic(long) shared_call_counter = 0;
+_Atomic(long) weak_call_counter = 0;
+_Atomic(long) destructor_counter = 0;
+_Atomic(long) weak_destroyed_counter = 0;
+
+struct MyStruct {
+  _Atomic(long) self_counter = 0;
+  virtual void shared_call() {
+    atomic_fetch_add_explicit(&self_counter, 1, memory_order_relaxed);
+    atomic_fetch_add_explicit(&shared_call_counter, 1, memory_order_relaxed);
+  }
+  virtual void weak_call() {
+    atomic_fetch_add_explicit(&weak_call_counter, 1, memory_order_relaxed);
+  }
+  virtual ~MyStruct() {
+    long n = self_counter;
+    assert(n == 1000);
+    atomic_fetch_add_explicit(&destructor_counter, 1, memory_order_relaxed);
+  }
+};
+
+int main(int argc, const char *argv[]) {
+  fprintf(stderr, "Hello world.\n");
+
+  dispatch_queue_t q = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
+
+  dispatch_group_t g = dispatch_group_create();
+
+  for (int i = 0; i < 1000; i++) {
+    std::shared_ptr<MyStruct> shared(new MyStruct());
+    std::weak_ptr<MyStruct> weak(shared);
+
+    dispatch_group_async(g, q, ^{
+      for (int j = 0; j < 1000; j++) {
+        std::shared_ptr<MyStruct> shared_copy(shared);
+        shared_copy->shared_call();
+      }
+    });
+    dispatch_group_async(g, q, ^{
+      for (int j = 0; j < 1000; j++) {
+        std::shared_ptr<MyStruct> weak_copy = weak.lock();
+        if (weak_copy) {
+          weak_copy->weak_call();
+        } else {
+          atomic_fetch_add_explicit(&weak_destroyed_counter, 1, memory_order_relaxed);
+          break;
+        }
+      }
+    });
+  }
+
+  dispatch_group_wait(g, DISPATCH_TIME_FOREVER);
+
+  fprintf(stderr, "shared_call_counter = %ld\n", shared_call_counter);
+  fprintf(stderr, "weak_call_counter = %ld\n", weak_call_counter);
+  fprintf(stderr, "destructor_counter = %ld\n", destructor_counter);
+  fprintf(stderr, "weak_destroyed_counter = %ld\n", weak_destroyed_counter);
+
+  fprintf(stderr, "Done.\n");
+}
+
+// CHECK: Hello world.
+// CHECK: shared_call_counter = 1000000
+// CHECK: destructor_counter = 1000
+// CHECK: Done.
+// CHECK-NOT: WARNING: ThreadSanitizer

compiler-rt/trunk/test/tsan/Darwin/libcxx-shared-ptr.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation
+// RUN: %env_tsan_opts=ignore_interceptors_accesses=1 %run %t 2>&1 | FileCheck %s
+
+#import <Foundation/Foundation.h>
+
+#import <memory>
+
+#import "../test.h"
+
+long my_global;
+
+struct MyStruct {
+  void setGlobal() {
+    my_global = 42;
+  }
+  ~MyStruct() {
+    my_global = 43;
+  }
+};
+
+int main(int argc, const char *argv[]) {
+  fprintf(stderr, "Hello world.\n");
+  print_address("addr=", 1, &my_global);
+  barrier_init(&barrier, 2);
+
+  std::shared_ptr<MyStruct> shared(new MyStruct());
+
+  dispatch_queue_t q = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
+
+  std::weak_ptr<MyStruct> weak(shared);
+  
+  dispatch_async(q, ^{
+    {
+      std::shared_ptr<MyStruct> strong = weak.lock();
+      if (!strong) exit(1);
+
+      strong->setGlobal();
+    }
+    barrier_wait(&barrier);
+  });
+
+  barrier_wait(&barrier);
+  shared.reset();
+
+  fprintf(stderr, "Done.\n");
+}
+
+// CHECK: Hello world.
+// CHECK: Done.
+// CHECK-NOT: WARNING: ThreadSanitizer