[tsan] Don't abort when a deadlock detector finds a mutex cycle longer than 10

[kubamracek]

Summary

In one of the already existing apps that I'm testing TSan on, I really see a mutex path that is longer than 10 (but not by much, something like 11-13 actually). Let's weaken the assertion and simply not report this deadlock.

[dvyukov]

lib/sanitizer_common/sanitizer_deadlock_detector1.cc

125 ↗

(On Diff #57773)

So, can we see it? :)
Maybe there is just some bug in logic, or a false deadlock report? Is it actually a legit report?
If it is a true report, then we should consider increasing the limit (and then we don't need to remove the CHECK). If it is a false report, then we need to fix something (and again no need to remove the CHECK, let it catch more bugs).

[kubamracek]

lib/sanitizer_common/sanitizer_deadlock_detector1.cc

125 ↗

(On Diff #57773)

It looks to me the report is correct (and it's really a long cycle). In this case it's a collection of Obj-C objects using @synchronized(self) while also referring to other objects. The same issue gets reported multiple times with different cycle lengths, so the report with extremely long cycle isn't really useful (it's already reported with simpler cases). Anyway, increasing the limit works for me as well.

[dvyukov]

lib/sanitizer_common/sanitizer_deadlock_detector1.cc

125 ↗

(On Diff #57773)

Let's increase the number to, say, 20 then.
As for the CHECK, we can leave it as is, or maybe replace with just Printf. If you get 13, I guess somebody can get 21. But I think it's better to have just a Printf, so that users see at least something.

[kubamracek]

Updating patch.

[dvyukov]

LGTM, but wait for Kostya to sign off.

[kcc]

A test maybe?

[kubamracek]

Adding a test case. Fixing another place where a hard limit for mutex cycle was.

[kcc]

LGTM with a nit

lib/sanitizer_common/sanitizer_deadlock_detector1.cc

122 ↗

(On Diff #57916)

can you use kMaxLoopSize here?

compiler-rt/trunk/lib/sanitizer_common/sanitizer_deadlock_detector1.cc

if (dd.onLockBefore(&lt->dd, m->id)) {
     // Actually add this edge now so that we have all the stack traces.
     dd.addEdges(&lt->dd, m->id, cb->Unwind(), cb->UniqueTid());
     ReportDeadlock(cb, m);
   }
 }
 
 void DD::ReportDeadlock(DDCallback *cb, DDMutex *m) {
   DDLogicalThread *lt = cb->lt;
-  uptr path[10];
+  uptr path[20];
   uptr len = dd.findPathToLock(&lt->dd, m->id, path, ARRAY_SIZE(path));
-  CHECK_GT(len, 0U);  // Hm.. cycle of 10 locks? I'd like to see that.
+  if (len == 0U) {
+    // A cycle of 20+ locks? Well, that's a bit odd...
+    Printf("WARNING: too long mutex cycle found\n");
+    return;
+  }
   CHECK_EQ(m->id, path[0]);
   lt->report_pending = true;
+  len = Min<uptr>(len, DDReport::kMaxLoopSize);
   DDReport *rep = &lt->rep;
   rep->n = len;
   for (uptr i = 0; i < len; i++) {
     uptr from = path[i];
     uptr to = path[(i + 1) % len];
     DDMutex *m0 = (DDMutex*)dd.getData(from);
     DDMutex *m1 = (DDMutex*)dd.getData(to);
 

compiler-rt/trunk/lib/sanitizer_common/sanitizer_deadlock_detector_interface.h

#endif
   u64  ctx;
 };
 
 struct DDFlags {
   bool second_deadlock_stack;
 };
 
 struct DDReport {
-  enum { kMaxLoopSize = 8 };
+  enum { kMaxLoopSize = 20 };
   int n;  // number of entries in loop
   struct {
     u64 thr_ctx;   // user thread context
     u64 mtx_ctx0;  // user mutex context, start of the edge
     u64 mtx_ctx1;  // user mutex context, end of the edge
     u32 stk[2];  // stack ids for the edge
   } loop[kMaxLoopSize];
 };

compiler-rt/trunk/test/tsan/mutex_cycle_long.c

+// RUN: %clangxx_tsan %s -o %t
+// RUN: not %run %t 5 2>&1 | FileCheck %s
+// RUN: not %run %t 10 2>&1 | FileCheck %s
+// RUN: not %run %t 15 2>&1 | FileCheck %s
+// RUN: not %run %t 20 2>&1 | FileCheck %s
+// RUN: %run %t 30 2>&1 | FileCheck %s --check-prefix=CHECK-TOO-LONG-CYCLE
+
+#include <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+int main(int argc, char *argv[]) {
+  int num_mutexes = 5;
+  if (argc > 1) num_mutexes = atoi(argv[1]);
+
+  pthread_mutex_t m[num_mutexes];
+  for (int i = 0; i < num_mutexes; ++i)
+    pthread_mutex_init(&m[i], NULL);
+  
+  for (int i = 0; i < num_mutexes - 1; ++i) {
+    pthread_mutex_lock(&m[i]);
+    pthread_mutex_lock(&m[i + 1]);
+
+    pthread_mutex_unlock(&m[i]);
+    pthread_mutex_unlock(&m[i + 1]);
+  }
+
+  pthread_mutex_lock(&m[num_mutexes - 1]);
+  pthread_mutex_lock(&m[0]);
+
+  pthread_mutex_unlock(&m[num_mutexes - 1]);
+  pthread_mutex_unlock(&m[0]);
+
+  for (int i = 0; i < num_mutexes; ++i)
+    pthread_mutex_destroy(&m[i]);
+
+  fprintf(stderr, "PASS\n");
+}
+
+// CHECK: ThreadSanitizer: lock-order-inversion (potential deadlock)
+// CHECK-TOO-LONG-CYCLE: WARNING: too long mutex cycle found
+// CHECK: PASS