Use rw locks for sanitizer thread registry

[fjricci]

Summary

When StopTheWorld is used to checks for leaks, one thread acquires the
mutex on the thread registry in CheckForLeaks, but a newly spawned thread
accesses the registry in CheckForLeaksCallback. Sharing a mutex access
across threads like this is not supported by blocking mutex,
but is supported by read-only locks in rw mutexes.

In order to allow for read-only access by multiple threads, this patch
changes the lock on the thread registry to a rw mutex.

[kubamracek]

Please factor out the renaming of GetTid to internal_gettid into a separate patch.

[kubamracek]

And also please factor out the validation of tid. These 3 things are independent separate fixes and should be separate patches:

1. The extra validation in BlockingMutex and RWMutex.
2. Renaming of GetTid.
3. Changing the mutex of ThreadRegistry to be RWMutex.

[fjricci]

Will split.

[fjricci]

Splits out move to rw locks from related changes

[fjricci]

Accidentally removed a reviewer, re-adding.

[kcc]

This is a very invasive change with a potential to break lots of things in subtle ways.
It has more chances to get reviewed and accepted if you

a) test it on something very big (and tell us what you did) and
b) add a test that fails now and passes with this change.

Also, please make sure to have LGTM from dvyukov before committing.

[dvyukov]

Sharing a mutex access across threads like this is not supported by blocking mutex

Why?
I've checked BlockingMutex comments and linux/mac/win implementation. I don't see any indication that it's not supported.
How is RWMutex different?
How does the problem manifest? What is the scenario that demonstrated the problem?

[dvyukov]

Spin mutex can behave very poorly on contention, and thread registry can be contended. I suspect blocking mutex is there on purpose.

[fjricci]

In D29588#668828, @dvyukov wrote:

Sharing a mutex access across threads like this is not supported by blocking mutex

Why?

If a thread owns a mutex on the thread registry for writing (as with a blocking mutex), we can't really assume in another thread that the registry won't change. Since the thread accessing the data is actually in a separate process (the result of a clone() in StopTheWorld), I'm not sure that there's even a way to pass the blocking mutex around safely.

I've checked BlockingMutex comments and linux/mac/win implementation. I don't see any indication that it's not supported.
How is RWMutex different?

An RWMutex acquired for read-only use can be safely used for reads by multiple threads, as it guarantees the protected data won't change. A blocking mutex provides no guarantees that the protected state won't change (and in fact implies that it probably will).

How does the problem manifest? What is the scenario that demonstrated the problem?

There are two pieces to this. The primary bit is just that adding checks to ensure that CheckLocked() only succeeds if the calling thread is the thread that owns the mutex will fail, as demonstrated by a cherry-pick of D29594. The other bit is consistency. Since these checks already exist on darwin and windows, the existing code will fail if and when we decide to add support for lsan to those platforms. This gives essentially two options - one would be removing the validation checks from the darwin and windows blocking mutex implementations, so that they succeed in the same way that linux currently does, by no longer forcing CheckLocked() to fail if another thread owns the mutex. The other would be the current method of adding strict validation checks to the linux implementation, which requires moving away from a blocking mutex.

[fjricci]

In D29588#668840, @dvyukov wrote:

Spin mutex can behave very poorly on contention, and thread registry can be contended. I suspect blocking mutex is there on purpose.

In terms of improving on spin mutex, I had originally used the pthreads rw lock implementation. However, this adds some libc dependencies which I wasn't sure we wanted.

[dvyukov]

In D29588#669125, @fjricci wrote:

In D29588#668828, @dvyukov wrote:

Sharing a mutex access across threads like this is not supported by blocking mutex

Why?

If a thread owns a mutex on the thread registry for writing (as with a blocking mutex), we can't really assume in another thread that the registry won't change. Since the thread accessing the data is actually in a separate process (the result of a clone() in StopTheWorld), I'm not sure that there's even a way to pass the blocking mutex around safely.

I've checked BlockingMutex comments and linux/mac/win implementation. I don't see any indication that it's not supported.
How is RWMutex different?

An RWMutex acquired for read-only use can be safely used for reads by multiple threads, as it guarantees the protected data won't change. A blocking mutex provides no guarantees that the protected state won't change (and in fact implies that it probably will).

Sorry, I am not following you.
How can protected data change when a thread holds the mutex and is not changing the data? Who/how can change the data?
Whoever wants to change the data must acquire the mutex first, but it won't because the parent process holds the mutex.
What do you mean y "passing blocking mutex around"? And why do we need to do it?

The parent process holds the mutex thus ensuring that nobody else is changing the data.

[fjricci]

In D29588#669786, @dvyukov wrote:

In D29588#669125, @fjricci wrote:

In D29588#668828, @dvyukov wrote:

Sharing a mutex access across threads like this is not supported by blocking mutex

Why?

If a thread owns a mutex on the thread registry for writing (as with a blocking mutex), we can't really assume in another thread that the registry won't change. Since the thread accessing the data is actually in a separate process (the result of a clone() in StopTheWorld), I'm not sure that there's even a way to pass the blocking mutex around safely.

I've checked BlockingMutex comments and linux/mac/win implementation. I don't see any indication that it's not supported.
How is RWMutex different?

An RWMutex acquired for read-only use can be safely used for reads by multiple threads, as it guarantees the protected data won't change. A blocking mutex provides no guarantees that the protected state won't change (and in fact implies that it probably will).

Sorry, I am not following you.
How can protected data change when a thread holds the mutex and is not changing the data? Who/how can change the data?
Whoever wants to change the data must acquire the mutex first, but it won't because the parent process holds the mutex.
What do you mean y "passing blocking mutex around"? And why do we need to do it?

The parent process holds the mutex thus ensuring that nobody else is changing the data.

Correct. We know that the data won't change in this particular case, because we know the parent isn't changing the data, and we know that our parent is holding the lock. However, this isn't what CheckLocked() is checking. CheckLocked() checks that *any* thread holds the lock, it doesn't need to be our parent to pass the check. That thread which is holding the lock could very well be changing the data. Even our parent could, in theory, be changing the data.

[dvyukov]

In D29588#669813, @fjricci wrote:

Correct. We know that the data won't change in this particular case, because we know the parent isn't changing the data, and we know that our parent is holding the lock. However, this isn't what CheckLocked() is checking. CheckLocked() checks that *any* thread holds the lock, it doesn't need to be our parent to pass the check.

I still don't get the problem.
How is CheckLocked related? I don't see any CheckLocked calls in lsan code.

That thread which is holding the lock could very well be changing the data. Even our parent could, in theory, be changing the data.

Um... well, but even the current thread can, in theory, hold the mutex and still wrongly change the data when it should not.
The parent is holding the mutex preventing all other threads from changing the data, and it should not change the data itself and it is not changing the data. Looks good to me. If parent will start changing data, we are in trouble. But there are zillion of possibilities of how we can end up in trouble if people will start randomly changing correct code to incorrect code.

[fjricci]

In D29588#669898, @dvyukov wrote:

In D29588#669813, @fjricci wrote:

Correct. We know that the data won't change in this particular case, because we know the parent isn't changing the data, and we know that our parent is holding the lock. However, this isn't what CheckLocked() is checking. CheckLocked() checks that *any* thread holds the lock, it doesn't need to be our parent to pass the check.

I still don't get the problem.
How is CheckLocked related? I don't see any CheckLocked calls in lsan code.

CheckLocked() is called via: __lsan::CheckForLeaksCallback() -> __lsan::GetThreadRangesLocked() -> __sanitizer::ThreadRegistry::FindThreadContextByOsIDLocked() -> CheckLocked()

I think I should probably do a better job of explaining the motivations behind these two changes.

BlockingMutex::CheckLocked() is part of an OS-independent API, called primarily from OS-independent code. To me, this means that its behavior should be the same regardless of platform. Currently this is not the case. If a platform-independent function calls CheckLocked(), its behavior will be different depending on the OS. So in practice, when FindThreadContextByOsIDLocked() calls CheckLocked(), if the code is running on linux, the check will pass as long as *any thread* holds the mutex. On mac or windows, the check will only pass if the *calling thread* holds the mutex.

Essentially, the problem I'm trying to solve is solidifying the expected behavior of CheckLocked(). If we think that the mac and windows implementations are representative of the correct API, then we should also only pass the check if the calling thread holds the mutex on linux, which requires these two changes. If we think the linux implementation is representative, then on mac and windows, we should pass as long as any thread holds the mutex, and not fail if the current thread isn't the holder. I'm happy with either API, although the current stricter approach seemed more correct to me, due to the reasons I've attempted to outline in previous comments.

It would probably be productive to decide what we want the general behavior of CheckLocked() to be. From there, we can decide whether we want to use this patch or a different fix.

[dvyukov]

The contract for CheckLocked is: CheckLocked does nothing if the current thread holds the mutex, otherwise behavior is undefined.
And, yes, we are currently abusing the sloppy check in BlockingMutex on linux in CheckForLeaks.

However, your solution does not look right to me. There are several problems with it:

1. Besides ThreadRegistry mutex, CheckForLeaks also locks in a similar manner allocator mutexes and dl_iterate_phr mutex. They are no firing currently due to a number of coincidences (e.g. not calling CheckLocked where is should be called, using SpinMutex that has the same sloppy check).
2. StopTheWorld is also used in tsan and subject to all the same problems. We can't just start changing all mutexes to RWMutex to please the stricter check. And finally:
3. RWMutex has the same sloppy ownership check for readers as the one you are trying to eliminate in BlockingMutex. When/if we make the check in RWMutex strict (require the calling thread to hold read lock), it will all fall apart because you don't actually fix the problem, you just mask it again abusing the sloppy check in RWMutex.

The root problem here is that StopTheWorld does weird things with mutexes, clone and ptrace. But it does them for a reason. A proper solution to this problem would be: parent grabs all mutexes and starts the child process, child process stops all threads _besides_ the parent thread, child process instructs parent thread to unlock the mutexes, parent thread releases all mutexes and blocks on something, child process grabs all mutexes. But I don't think it's worth it.

I see 2 practical ways to resolve this:

1. Make all CheckLocked checks sloppy. It's actually not that bad, because we will catch any misuse eventually. It's also simple and fast.
2. Make all CheckLocked checks strict (including RWMutex and SpinMutex) but introduce a special global of per-thread flag for StopTheWorld that will say "back off, I am doing weird things here, so disable ownership checks for now".

[fjricci]

Ok, I think that makes a lot of sense. I did originally think about something similar to the "proper solution" you mentioned, but I came to a similar conclusion about its complexity vs value.

In terms of the 2 solutions you proposed, the first seems quite a bit cleaner, and mirrors the behavior we already have on Linux. I'll go ahead and put up a diff for that, providing nobody has a strong preference for the second.

[dvyukov]

SGTM

[fjricci]

Fixed via D29728

lib/asan/asan_thread.cc

 void LockThreadRegistry() {
   __asan::asanThreadRegistry().Lock();
 }
 
 void UnlockThreadRegistry() {
   __asan::asanThreadRegistry().Unlock();
 }
 
+void LockThreadRegistryRead() {
+  __asan::asanThreadRegistry().ReadLock();
+}
+
+void UnlockThreadRegistryRead() {
+  __asan::asanThreadRegistry().ReadUnlock();
+}
+
 void EnsureMainThreadIDIsCorrect() {
   __asan::EnsureMainThreadIDIsCorrect();
 }
 } // namespace __lsan
 
 // ---------------------- Interface ---------------- {{{1
 using namespace __asan;  // NOLINT
 

lib/lsan/lsan_common.h

 // Wrappers for allocator's ForceLock()/ForceUnlock().
 void LockAllocator();
 void UnlockAllocator();
 // Returns true if [addr, addr + sizeof(void *)) is poisoned.
 bool WordIsPoisoned(uptr addr);
 // Wrappers for ThreadRegistry access.
 void LockThreadRegistry();
 void UnlockThreadRegistry();
+void LockThreadRegistryRead();
+void UnlockThreadRegistryRead();
 bool GetThreadRangesLocked(uptr os_id, uptr *stack_begin, uptr *stack_end,
                            uptr *tls_begin, uptr *tls_end, uptr *cache_begin,
                            uptr *cache_end, DTLS **dtls);
 void ForEachExtraStackRange(uptr os_id, RangeIteratorCallback callback,
                             void *arg);
 // If called from the main thread, updates the main thread's TID in the thread
 // registry. We need this to handle processes that fork() without a subsequent
 // exec(), which invalidates the recorded TID. To update it, we must call

lib/lsan/lsan_common.cc

 }
 
 static bool CheckForLeaks() {
   if (&__lsan_is_turned_off && __lsan_is_turned_off())
       return false;
   EnsureMainThreadIDIsCorrect();
   CheckForLeaksParam param;
   param.success = false;
-  LockThreadRegistry();
+  LockThreadRegistryRead();
   LockAllocator();
   DoStopTheWorld(CheckForLeaksCallback, &param);
   UnlockAllocator();
-  UnlockThreadRegistry();
+  UnlockThreadRegistryRead();
 
   if (!param.success) {
     Report("LeakSanitizer has encountered a fatal error.\n");
     Report(
         "HINT: For debugging, try setting environment variable "
         "LSAN_OPTIONS=verbosity=1:log_threads=1\n");
     Report(
         "HINT: LeakSanitizer does not work under ptrace (strace, gdb, etc)\n");

lib/lsan/lsan_thread.cc

 void LockThreadRegistry() {
   thread_registry->Lock();
 }
 
 void UnlockThreadRegistry() {
   thread_registry->Unlock();
 }
 
+void LockThreadRegistryRead() {
+  thread_registry->ReadLock();
+}
+
+void UnlockThreadRegistryRead() {
+  thread_registry->ReadUnlock();
+}
+
 } // namespace __lsan

lib/sanitizer_common/sanitizer_thread_registry.h

ThreadRegistry(ThreadContextFactory factory, u32 max_threads,
                  u32 thread_quarantine_size, u32 max_reuse = 0);
   void GetNumberOfThreads(uptr *total = nullptr, uptr *running = nullptr,
                           uptr *alive = nullptr);
   uptr GetMaxAliveThreads();
 
   void Lock() { mtx_.Lock(); }
   void CheckLocked() { mtx_.CheckLocked(); }
   void Unlock() { mtx_.Unlock(); }
+  void ReadLock() { mtx_.ReadLock(); }
+  void ReadUnlock() { mtx_.ReadUnlock(); }
 
   // Should be guarded by ThreadRegistryLock.
   ThreadContextBase *GetThreadLocked(u32 tid) {
     DCHECK_LT(tid, n_contexts_);
     return threads_[tid];
   }
 
   u32 CreateThread(uptr user_id, bool detached, u32 parent_tid, void *arg);
public:
   void StartThread(u32 tid, uptr os_id, bool workerthread, void *arg);
 
  private:
   const ThreadContextFactory context_factory_;
   const u32 max_threads_;
   const u32 thread_quarantine_size_;
   const u32 max_reuse_;
 
-  BlockingMutex mtx_;
+  RWMutex mtx_;
 
   u32 n_contexts_;      // Number of created thread contexts,
                         // at most max_threads_.
   u64 total_threads_;   // Total number of created threads. May be greater than
                         // max_threads_ if contexts were reused.
   uptr alive_threads_;  // Created or running.
   uptr max_alive_threads_;
   uptr running_threads_;

lib/sanitizer_common/sanitizer_thread_registry.cc

ThreadRegistry::ThreadRegistry(ThreadContextFactory factory, u32 max_threads,
   threads_ = (ThreadContextBase **)MmapOrDie(max_threads_ * sizeof(threads_[0]),
                                              "ThreadRegistry");
   dead_threads_.clear();
   invalid_threads_.clear();
 }
 
 void ThreadRegistry::GetNumberOfThreads(uptr *total, uptr *running,
                                         uptr *alive) {
-  BlockingMutexLock l(&mtx_);
+  RWMutexReadLock l(&mtx_);
   if (total) *total = n_contexts_;
   if (running) *running = running_threads_;
   if (alive) *alive = alive_threads_;
 }
 
 uptr ThreadRegistry::GetMaxAliveThreads() {
-  BlockingMutexLock l(&mtx_);
+  RWMutexReadLock l(&mtx_);
   return max_alive_threads_;
 }
 
 u32 ThreadRegistry::CreateThread(uptr user_id, bool detached, u32 parent_tid,
                                  void *arg) {
-  BlockingMutexLock l(&mtx_);
+  RWMutexLock l(&mtx_);
   u32 tid = kUnknownTid;
   ThreadContextBase *tctx = QuarantinePop();
   if (tctx) {
     tid = tctx->tid;
   } else if (n_contexts_ < max_threads_) {
     // Allocate new thread context and tid.
     tid = n_contexts_++;
     tctx = context_factory_(tid);
for (u32 tid = 0; tid < n_contexts_; tid++) {
     ThreadContextBase *tctx = threads_[tid];
     if (tctx == 0)
       continue;
     cb(tctx, arg);
   }
 }
 
 u32 ThreadRegistry::FindThread(FindThreadCallback cb, void *arg) {
-  BlockingMutexLock l(&mtx_);
+  RWMutexLock l(&mtx_);
   for (u32 tid = 0; tid < n_contexts_; tid++) {
     ThreadContextBase *tctx = threads_[tid];
     if (tctx != 0 && cb(tctx, arg))
       return tctx->tid;
   }
   return kUnknownTid;
 }
 

 }
 
 ThreadContextBase *ThreadRegistry::FindThreadContextByOsIDLocked(uptr os_id) {
   return FindThreadContextLocked(FindThreadContextByOsIdCallback,
                                  (void *)os_id);
 }
 
 void ThreadRegistry::SetThreadName(u32 tid, const char *name) {
-  BlockingMutexLock l(&mtx_);
+  RWMutexLock l(&mtx_);
   CHECK_LT(tid, n_contexts_);
   ThreadContextBase *tctx = threads_[tid];
   CHECK_NE(tctx, 0);
   CHECK_EQ(ThreadStatusRunning, tctx->status);
   tctx->SetName(name);
 }
 
 void ThreadRegistry::SetThreadNameByUserId(uptr user_id, const char *name) {
-  BlockingMutexLock l(&mtx_);
+  RWMutexLock l(&mtx_);
   for (u32 tid = 0; tid < n_contexts_; tid++) {
     ThreadContextBase *tctx = threads_[tid];
     if (tctx != 0 && tctx->user_id == user_id &&
         tctx->status != ThreadStatusInvalid) {
       tctx->SetName(name);
       return;
     }
   }
 }
 
 void ThreadRegistry::DetachThread(u32 tid, void *arg) {
-  BlockingMutexLock l(&mtx_);
+  RWMutexLock l(&mtx_);
   CHECK_LT(tid, n_contexts_);
   ThreadContextBase *tctx = threads_[tid];
   CHECK_NE(tctx, 0);
   if (tctx->status == ThreadStatusInvalid) {
     Report("%s: Detach of non-existent thread\n", SanitizerToolName);
     return;
   }
   tctx->OnDetached(arg);
   if (tctx->status == ThreadStatusFinished) {
     tctx->SetDead();
     QuarantinePush(tctx);
   } else {
     tctx->detached = true;
   }
 }
 
 void ThreadRegistry::JoinThread(u32 tid, void *arg) {
-  BlockingMutexLock l(&mtx_);
+  RWMutexLock l(&mtx_);
   CHECK_LT(tid, n_contexts_);
   ThreadContextBase *tctx = threads_[tid];
   CHECK_NE(tctx, 0);
   if (tctx->status == ThreadStatusInvalid) {
     Report("%s: Join of non-existent thread\n", SanitizerToolName);
     return;
   }
   tctx->SetJoined(arg);
   QuarantinePush(tctx);
 }
 
 void ThreadRegistry::FinishThread(u32 tid) {
-  BlockingMutexLock l(&mtx_);
+  RWMutexLock l(&mtx_);
   CHECK_GT(alive_threads_, 0);
   alive_threads_--;
   CHECK_GT(running_threads_, 0);
   running_threads_--;
   CHECK_LT(tid, n_contexts_);
   ThreadContextBase *tctx = threads_[tid];
   CHECK_NE(tctx, 0);
   CHECK_EQ(ThreadStatusRunning, tctx->status);
   tctx->SetFinished();
   if (tctx->detached) {
     tctx->SetDead();
     QuarantinePush(tctx);
   }
 }
 
 void ThreadRegistry::StartThread(u32 tid, uptr os_id, bool workerthread,
                                  void *arg) {
-  BlockingMutexLock l(&mtx_);
+  RWMutexLock l(&mtx_);
   running_threads_++;
   CHECK_LT(tid, n_contexts_);
   ThreadContextBase *tctx = threads_[tid];
   CHECK_NE(tctx, 0);
   CHECK_EQ(ThreadStatusCreated, tctx->status);
   tctx->SetStarted(os_id, workerthread, arg);
 }
 

lib/tsan/rtl/tsan_rtl.cc

#if TSAN_COLLECT_STATS
   StatOutput(ctx->stat);
 #endif
 
   return failed ? common_flags()->exitcode : 0;
 }
 
 #if !SANITIZER_GO
 void ForkBefore(ThreadState *thr, uptr pc) {
-  ctx->thread_registry->Lock();
+  ctx->thread_registry->ReadLock();
   ctx->report_mtx.Lock();
 }
 
 void ForkParentAfter(ThreadState *thr, uptr pc) {
   ctx->report_mtx.Unlock();
-  ctx->thread_registry->Unlock();
+  ctx->thread_registry->ReadUnlock();
 }
 
 void ForkChildAfter(ThreadState *thr, uptr pc) {
   ctx->report_mtx.Unlock();
-  ctx->thread_registry->Unlock();
+  ctx->thread_registry->ReadUnlock();
 
   uptr nthread = 0;
   ctx->thread_registry->GetNumberOfThreads(0, 0, &nthread /* alive threads */);
   VPrintf(1, "ThreadSanitizer: forked new process with pid %d,"
       " parent had %d threads\n", (int)internal_getpid(), (int)nthread);
   if (nthread == 1) {
     StartBackgroundThread();
   } else {