tsan: extend MutexSet to memorize mutex address/stack_id

[dvyukov]

Summary

We currently memorize u64 id + epoch for each mutex.
The new tsan runtime will memorize address + stack_id instead.
But switching to address + stack_id requires new trace,
which in turn requires new MutexSet and some other changes.
Extend MutexSet to support both new and old info to break
the dependency cycles. The plan is to remove the old
info/methods after switching to the new runtime.

[vitalybuka]

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

20

memset(this...)?

86–93

Does min_seq makes a difference from:

uptr min_index = 0;
for (uptr i = 1; i < size_; i++)
  if (descs_[i].seq < descs_[min_index].seq)
    min_index = i;

[vitalybuka]

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

86–93

hm, it does for clang, but not gcc
https://godbolt.org/z/vW9EEzKW8

[dvyukov]

removed min_seq variable

[dvyukov]

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

20

memset(this) is somewhat ugly hack (technically UB and can break if we add virtual functions):
https://stackoverflow.com/questions/53339268/what-trait-concept-can-guarantee-memsetting-an-object-is-well-defined

The current memset avoids a very specific problem with compiler-emitted memset. It's not that we generally want these C hacks to save few lines. So I would prefer to initialize normal variables as one would do it normally.

[melver]

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

20

These could actually be initialized inline at definition.

[dvyukov]

initialize seq_/size_ fields inline at declaration

compiler-rt/lib/tsan/rtl/tsan_mutexset.h

 namespace __tsan {
 
 class MutexSet {
  public:
   // Holds limited number of mutexes.
   // The oldest mutexes are discarded on overflow.
   static const uptr kMaxSize = 16;
   struct Desc {
+    uptr addr;
+    StackID stack_id;
     u64 id;
     u64 epoch;
-    int count;
+    u32 seq;
+    u32 count;
     bool write;
   };
 
   MutexSet();
   // The 'id' is obtained from SyncVar::GetId().
   void Add(u64 id, bool write, u64 epoch);
   void Del(u64 id, bool write);
   void Remove(u64 id);  // Removes the mutex completely (if it's destroyed).
+  void AddAddr(uptr addr, StackID stack_id, bool write);
+  void DelAddr(uptr addr, bool destroy = false);
   uptr Size() const;
   Desc Get(uptr i) const;
 
+  MutexSet(const MutexSet& other) { *this = other; }
   void operator=(const MutexSet &other) {
     internal_memcpy(this, &other, sizeof(*this));
   }
 
  private:
 #if !SANITIZER_GO
-  uptr size_;
+  u32 seq_ = 0;
+  uptr size_ = 0;
   Desc descs_[kMaxSize];
-#endif
 
   void RemovePos(uptr i);
-  MutexSet(const MutexSet&);
+#endif
 };
 
 // Go does not have mutexes, so do not spend memory and time.
 // (Go sync.Mutex is actually a semaphore -- can be unlocked
 // in different goroutine).
 #if SANITIZER_GO
 MutexSet::MutexSet() {}
 void MutexSet::Add(u64 id, bool write, u64 epoch) {}
 void MutexSet::Del(u64 id, bool write) {}
 void MutexSet::Remove(u64 id) {}
-void MutexSet::RemovePos(uptr i) {}
+void MutexSet::AddAddr(uptr addr, StackID stack_id, bool write) {}
+void MutexSet::DelAddr(uptr addr, bool destroy) {}
 uptr MutexSet::Size() const { return 0; }
 MutexSet::Desc MutexSet::Get(uptr i) const { return Desc(); }
 #endif
 
 }  // namespace __tsan
 
 #endif  // TSAN_MUTEXSET_H

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

 #include "tsan_mutexset.h"
 #include "tsan_rtl.h"
 
 namespace __tsan {
 
 const uptr MutexSet::kMaxSize;
 
 MutexSet::MutexSet() {
-  size_ = 0;
   internal_memset(&descs_, 0, sizeof(descs_));
 }
 
 void MutexSet::Add(u64 id, bool write, u64 epoch) {
   // Look up existing mutex with the same id.
   for (uptr i = 0; i < size_; i++) {
     if (descs_[i].id == id) {
       descs_[i].count++;
       descs_[i].epoch = epoch;
for (uptr i = 0; i < size_; i++) {
         minepoch = descs_[i].epoch;
         mini = i;
       }
     }
     RemovePos(mini);
     CHECK_EQ(size_, kMaxSize - 1);
   }
   // Add new mutex descriptor.
+  descs_[size_].addr = 0;
+  descs_[size_].stack_id = kInvalidStackID;
   descs_[size_].id = id;
   descs_[size_].write = write;
   descs_[size_].epoch = epoch;
+  descs_[size_].seq = seq_++;
   descs_[size_].count = 1;
   size_++;
 }
 
 void MutexSet::Del(u64 id, bool write) {
   for (uptr i = 0; i < size_; i++) {
     if (descs_[i].id == id) {
       if (--descs_[i].count == 0)
         RemovePos(i);
       return;
     }
   }
 }
 
 void MutexSet::Remove(u64 id) {
   for (uptr i = 0; i < size_; i++) {
     if (descs_[i].id == id) {
       RemovePos(i);
       return;
     }
   }
 }
 
+void MutexSet::AddAddr(uptr addr, StackID stack_id, bool write) {
+  // Look up existing mutex with the same id.
+  for (uptr i = 0; i < size_; i++) {
+    if (descs_[i].addr == addr) {
+      descs_[i].count++;
+      descs_[i].seq = seq_++;
+      return;
+    }
+  }
+  // On overflow, find the oldest mutex and drop it.
+  if (size_ == kMaxSize) {
+    uptr min = 0;
+    for (uptr i = 0; i < size_; i++) {
+      if (descs_[i].seq < descs_[min].seq)
+        min = i;
+    }
+    RemovePos(min);
+    CHECK_EQ(size_, kMaxSize - 1);
+  }
+  // Add new mutex descriptor.
+  descs_[size_].addr = addr;
+  descs_[size_].stack_id = stack_id;
+  descs_[size_].id = 0;
+  descs_[size_].write = write;
+  descs_[size_].epoch = 0;
+  descs_[size_].seq = seq_++;
+  descs_[size_].count = 1;
+  size_++;
+}
+
+void MutexSet::DelAddr(uptr addr, bool destroy) {
+  for (uptr i = 0; i < size_; i++) {
+    if (descs_[i].addr == addr) {
+      if (destroy || --descs_[i].count == 0)
+        RemovePos(i);
+      return;
+    }
+  }
+}
+
 void MutexSet::RemovePos(uptr i) {
   CHECK_LT(i, size_);
   descs_[i] = descs_[size_ - 1];
   size_--;
 }
 
 uptr MutexSet::Size() const {
   return size_;
 }
 
 MutexSet::Desc MutexSet::Get(uptr i) const {
   CHECK_LT(i, size_);
   return descs_[i];
 }
 
 }  // namespace __tsan