tsan: allocate vector clocks using slab allocator

Vector clocks is the most actively allocated object in tsan runtime.
Current internal allocator is not scalable enough to handle allocation
of clocks in scalable way (too small caches). This changes transforms
clocks to 2-level array with 512-byte blocks. Since all blocks are of
the same size, it's possible to cache them more efficiently in per-thread caches.

llvm-svn: 214912

1 files changed, 41 insertions, 13 deletions

diff --git a/compiler-rt/lib/tsan/rtl/tsan_clock.h b/compiler-rt/lib/tsan/rtl/tsan_clock.h
index f7ab69a3a81..7b4de555a87 100644
--- a/compiler-rt/lib/tsan/rtl/tsan_clock.h
+++ b/compiler-rt/lib/tsan/rtl/tsan_clock.h
@@ -14,7 +14,7 @@
 #define TSAN_CLOCK_H
 
 #include "tsan_defs.h"
-#include "tsan_vector.h"
+#include "tsan_dense_alloc.h"
 
 namespace __tsan {
 
@@ -23,37 +23,64 @@ struct ClockElem {
   u64 reused : 64 - kClkBits;
 };
 
+struct ClockBlock {
+  static const uptr kSize = 512;
+  static const uptr kTableSize = kSize / sizeof(u32);
+  static const uptr kClockCount = kSize / sizeof(ClockElem);
+
+  union {
+    u32       table[kTableSize];
+    ClockElem clock[kClockCount];
+  };
+
+  ClockBlock() {
+  }
+};
+
+typedef DenseSlabAlloc<ClockBlock, 1<<16, 1<<10> ClockAlloc;
+typedef DenseSlabAllocCache ClockCache;
+
 // The clock that lives in sync variables (mutexes, atomics, etc).
 class SyncClock {
  public:
   SyncClock();
+  ~SyncClock();
 
   uptr size() const {
-    return clk_.Size();
+    return size_;
   }
 
   u64 get(unsigned tid) const {
-    DCHECK_LT(tid, clk_.Size());
-    return clk_[tid].epoch;
+    return elem(tid).epoch;
   }
 
-  void Reset();
-  void Zero();
+  void Reset(ClockCache *c);
 
   void DebugDump(int(*printf)(const char *s, ...));
 
  private:
+  friend struct ThreadClock;
+  static const uptr kDirtyTids = 2;
+
   unsigned release_store_tid_;
   unsigned release_store_reused_;
-  static const uptr kDirtyTids = 2;
   unsigned dirty_tids_[kDirtyTids];
-  mutable Vector<ClockElem> clk_;
-  friend struct ThreadClock;
+  // tab_ contains indirect pointer to a 512b block using DenseSlabAlloc.
+  // If size_ <= 64, then tab_ points to an array with 64 ClockElem's.
+  // Otherwise, tab_ points to an array with 128 u32 elements,
+  // each pointing to the second-level 512b block with 64 ClockElem's.
+  ClockBlock *tab_;
+  u32 tab_idx_;
+  u32 size_;
+
+  ClockElem &elem(unsigned tid) const;
 };
 
 // The clock that lives in threads.
 struct ThreadClock {
  public:
+  typedef DenseSlabAllocCache Cache;
+
   explicit ThreadClock(unsigned tid, unsigned reused = 0);
 
   u64 get(unsigned tid) const {
@@ -76,10 +103,10 @@ struct ThreadClock {
     return nclk_;
   }
 
-  void acquire(const SyncClock *src);
-  void release(SyncClock *dst) const;
-  void acq_rel(SyncClock *dst);
-  void ReleaseStore(SyncClock *dst) const;
+  void acquire(ClockCache *c, const SyncClock *src);
+  void release(ClockCache *c, SyncClock *dst) const;
+  void acq_rel(ClockCache *c, SyncClock *dst);
+  void ReleaseStore(ClockCache *c, SyncClock *dst) const;
 
   void DebugReset();
   void DebugDump(int(*printf)(const char *s, ...));
@@ -94,6 +121,7 @@ struct ThreadClock {
 
   bool IsAlreadyAcquired(const SyncClock *src) const;
   void UpdateCurrentThread(SyncClock *dst) const;
+  void Resize(ClockCache *c, SyncClock *dst) const;
 };
 
 }  // namespace __tsan