tsan: increase dense slab alloc capacity

[dvyukov]

Summary

We've got a user report about heap block allocator overflow.
Bump the L1 capacity of all dense slab allocators to maximum
and be careful to not page the whole L1 array in from .bss.
If OS uses huge pages, this still may cause a limited RSS increase
due to boundary huge pages, but avoiding that looks hard.

[vitalybuka]

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

41–42

checks can be replaced with static_asserts

63

freelist_ = 0;     fillpos_ = 0; should be moved here?

[vitalybuka]

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

63

nevermind, either way is fine, it's just internal_memset which must be here

[dvyukov]

Changed CHECK's to static_assert's.

[dvyukov]

PTAL

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

63

Yes, that was the intention. Not sure what option is better.
memset needs to be here, for other fields I decided to be more explicit and safe.

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

 #ifndef TSAN_CLOCK_H
 #define TSAN_CLOCK_H
 
 #include "tsan_defs.h"
 #include "tsan_dense_alloc.h"
 
 namespace __tsan {
 
-typedef DenseSlabAlloc<ClockBlock, 1<<16, 1<<10> ClockAlloc;
+typedef DenseSlabAlloc<ClockBlock, 1 << 22, 1 << 10> ClockAlloc;
 typedef DenseSlabAllocCache ClockCache;
 
 // The clock that lives in sync variables (mutexes, atomics, etc).
 class SyncClock {
  public:
   SyncClock();
   ~SyncClock();
 

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

 
 namespace __tsan {
 
 class DenseSlabAllocCache {
   static const uptr kSize = 128;
   typedef u32 IndexT;
   uptr pos;
   IndexT cache[kSize];
-  template<typename T, uptr kL1Size, uptr kL2Size> friend class DenseSlabAlloc;
+  template <typename, uptr, uptr, u64>
+  friend class DenseSlabAlloc;
 };
 
-template<typename T, uptr kL1Size, uptr kL2Size>
+template <typename T, uptr kL1Size, uptr kL2Size, u64 kReserved = 0>
 class DenseSlabAlloc {
  public:
   typedef DenseSlabAllocCache Cache;
   typedef typename Cache::IndexT IndexT;
 
-  explicit DenseSlabAlloc(const char *name) {
-    // Check that kL1Size and kL2Size are sane.
-    CHECK_EQ(kL1Size & (kL1Size - 1), 0);
-    CHECK_EQ(kL2Size & (kL2Size - 1), 0);
-    CHECK_GE(1ull << (sizeof(IndexT) * 8), kL1Size * kL2Size);
-    // Check that it makes sense to use the dense alloc.
-    CHECK_GE(sizeof(T), sizeof(IndexT));
-    internal_memset(map_, 0, sizeof(map_));
+  static_assert((kL1Size & (kL1Size - 1)) == 0,
+                "kL1Size must be a power-of-two");
+  static_assert((kL2Size & (kL2Size - 1)) == 0,
+                "kL2Size must be a power-of-two");
+  static_assert((kL1Size * kL2Size) <= (1ull << (sizeof(IndexT) * 8)),
+                "kL1Size/kL2Size are too large");
+  static_assert(((kL1Size * kL2Size - 1) & kReserved) == 0,
+                "reserved bits don't fit");
+  static_assert(sizeof(T) > sizeof(IndexT),
+                "it doesn't make sense to use dense alloc");
+
+  explicit DenseSlabAlloc(LinkerInitialized, const char *name) {
     freelist_ = 0;
     fillpos_ = 0;
     name_ = name;
   }
 
+  explicit DenseSlabAlloc(const char *name)
+      : DenseSlabAlloc(LINKER_INITIALIZED, name) {
+    // It can be very large.
+    // Don't page it in for linker initialized objects.
+    internal_memset(map_, 0, sizeof(map_));
+  }
+
   ~DenseSlabAlloc() {
     for (uptr i = 0; i < kL1Size; i++) {
       if (map_[i] != 0)
         UnmapOrDie(map_[i], kL2Size * sizeof(T));
     }
   }
 
   IndexT Alloc(Cache *c) {

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

 
 #if !SANITIZER_GO
 static const u32 kThreadQuarantineSize = 16;
 #else
 static const u32 kThreadQuarantineSize = 64;
 #endif
 
 Context::Context()
-  : initialized()
-  , report_mtx(MutexTypeReport, StatMtxReport)
-  , nreported()
-  , nmissed_expected()
-  , thread_registry(new(thread_registry_placeholder) ThreadRegistry(
-      CreateThreadContext, kMaxTid, kThreadQuarantineSize, kMaxTidReuse))
-  , racy_mtx(MutexTypeRacy, StatMtxRacy)
-  , racy_stacks()
-  , racy_addresses()
-  , fired_suppressions_mtx(MutexTypeFired, StatMtxFired)
-  , clock_alloc("clock allocator") {
+    : initialized(),
+      report_mtx(MutexTypeReport, StatMtxReport),
+      nreported(),
+      nmissed_expected(),
+      thread_registry(new (thread_registry_placeholder) ThreadRegistry(
+          CreateThreadContext, kMaxTid, kThreadQuarantineSize, kMaxTidReuse)),
+      racy_mtx(MutexTypeRacy, StatMtxRacy),
+      racy_stacks(),
+      racy_addresses(),
+      fired_suppressions_mtx(MutexTypeFired, StatMtxFired),
+      clock_alloc(LINKER_INITIALIZED, "clock allocator") {
   fired_suppressions.reserve(8);
 }
 
 // The objects are allocated in TLS, so one may rely on zero-initialization.
 ThreadState::ThreadState(Context *ctx, int tid, int unique_id, u64 epoch,
                          unsigned reuse_count,
                          uptr stk_addr, uptr stk_size,
                          uptr tls_addr, uptr tls_size)

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

public:
   void MoveMemory(uptr src, uptr dst, uptr sz);
 
   void OnProcIdle(Processor *proc);
 
  private:
   static const u32 kFlagMask  = 3u << 30;
   static const u32 kFlagBlock = 1u << 30;
   static const u32 kFlagSync  = 2u << 30;
-  typedef DenseSlabAlloc<MBlock, 1<<16, 1<<12> BlockAlloc;
-  typedef DenseSlabAlloc<SyncVar, 1<<16, 1<<10> SyncAlloc;
+  typedef DenseSlabAlloc<MBlock, 1 << 18, 1 << 12, kFlagMask> BlockAlloc;
+  typedef DenseSlabAlloc<SyncVar, 1 << 20, 1 << 10, kFlagMask> SyncAlloc;
   BlockAlloc block_alloc_;
   SyncAlloc sync_alloc_;
   atomic_uint64_t uid_gen_;
 
   SyncVar* GetAndLock(ThreadState *thr, uptr pc, uptr addr, bool write_lock,
                       bool create);
 };
 
 }  // namespace __tsan
 
 #endif  // TSAN_SYNC_H

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

if (proc == 0) {
     CHECK_EQ(read_clock.size(), 0);
   } else {
     clock.Reset(&proc->clock_cache);
     read_clock.Reset(&proc->clock_cache);
   }
 }
 
 MetaMap::MetaMap()
-    : block_alloc_("heap block allocator")
-    , sync_alloc_("sync allocator") {
+    : block_alloc_(LINKER_INITIALIZED, "heap block allocator"),
+      sync_alloc_(LINKER_INITIALIZED, "sync allocator") {
   atomic_store(&uid_gen_, 0, memory_order_relaxed);
 }
 
 void MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) {
   u32 idx = block_alloc_.Alloc(&thr->proc()->block_cache);
   MBlock *b = block_alloc_.Map(idx);
   b->siz = sz;
   b->tag = 0;

compiler-rt/lib/tsan/tests/unit/CMakeLists.txt

 set(TSAN_UNIT_TEST_SOURCES
   tsan_clock_test.cpp
+  tsan_dense_alloc_test.cpp
   tsan_flags_test.cpp
   tsan_mman_test.cpp
   tsan_mutex_test.cpp
   tsan_shadow_test.cpp
   tsan_stack_test.cpp
   tsan_sync_test.cpp
   tsan_unit_test_main.cpp
   )
 
 add_tsan_unittest(TsanUnitTest
   SOURCES ${TSAN_UNIT_TEST_SOURCES})

compiler-rt/lib/tsan/tests/unit/tsan_dense_alloc_test.cpp

 
 #include <stdlib.h>
 #include <stdint.h>
 #include <map>
 
 namespace __tsan {
 
 TEST(DenseSlabAlloc, Basic) {
-  typedef DenseSlabAlloc<int, 128, 128> Alloc;
+  typedef u64 T;
+  typedef DenseSlabAlloc<T, 128, 128> Alloc;
   typedef Alloc::Cache Cache;
   typedef Alloc::IndexT IndexT;
-  const int N = 1000;
+  const T N = 1000;
 
-  Alloc alloc;
+  Alloc alloc("test");
   Cache cache;
   alloc.InitCache(&cache);
 
   IndexT blocks[N];
   for (int ntry = 0; ntry < 3; ntry++) {
-    for (int i = 0; i < N; i++) {
+    for (T i = 0; i < N; i++) {
       IndexT idx = alloc.Alloc(&cache);
       blocks[i] = idx;
       EXPECT_NE(idx, 0U);
-      int *v = alloc.Map(idx);
+      T *v = alloc.Map(idx);
       *v = i;
     }
 
-    for (int i = 0; i < N; i++) {
+    for (T i = 0; i < N; i++) {
       IndexT idx = blocks[i];
-      int *v = alloc.Map(idx);
+      T *v = alloc.Map(idx);
       EXPECT_EQ(*v, i);
       alloc.Free(&cache, idx);
     }
 
     alloc.FlushCache(&cache);
   }
 }
 
 }  // namespace __tsan