1 //===-- tsan_dense_alloc.h --------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file is a part of ThreadSanitizer (TSan), a race detector. 10 // 11 // A DenseSlabAlloc is a freelist-based allocator of fixed-size objects. 12 // DenseSlabAllocCache is a thread-local cache for DenseSlabAlloc. 13 // The only difference with traditional slab allocators is that DenseSlabAlloc 14 // allocates/free indices of objects and provide a functionality to map 15 // the index onto the real pointer. The index is u32, that is, 2 times smaller 16 // than uptr (hense the Dense prefix). 17 //===----------------------------------------------------------------------===// 18 #ifndef TSAN_DENSE_ALLOC_H 19 #define TSAN_DENSE_ALLOC_H 20 21 #include "sanitizer_common/sanitizer_common.h" 22 #include "tsan_defs.h" 23 24 namespace __tsan { 25 26 class DenseSlabAllocCache { 27 static const uptr kSize = 128; 28 typedef u32 IndexT; 29 uptr pos; 30 IndexT cache[kSize]; 31 template <typename, uptr, uptr, u64> 32 friend class DenseSlabAlloc; 33 }; 34 35 template <typename T, uptr kL1Size, uptr kL2Size, u64 kReserved = 0> 36 class DenseSlabAlloc { 37 public: 38 typedef DenseSlabAllocCache Cache; 39 typedef typename Cache::IndexT IndexT; 40 41 static_assert((kL1Size & (kL1Size - 1)) == 0, 42 "kL1Size must be a power-of-two"); 43 static_assert((kL2Size & (kL2Size - 1)) == 0, 44 "kL2Size must be a power-of-two"); 45 static_assert((kL1Size * kL2Size) <= (1ull << (sizeof(IndexT) * 8)), 46 "kL1Size/kL2Size are too large"); 47 static_assert(((kL1Size * kL2Size - 1) & kReserved) == 0, 48 "reserved bits don't fit"); 49 static_assert(sizeof(T) > sizeof(IndexT), 50 "it doesn't make sense to use dense alloc"); 51 52 DenseSlabAlloc(LinkerInitialized, const char *name) : name_(name) {} 53 54 explicit DenseSlabAlloc(const char *name) 55 : DenseSlabAlloc(LINKER_INITIALIZED, name) { 56 // It can be very large. 57 // Don't page it in for linker initialized objects. 58 internal_memset(map_, 0, sizeof(map_)); 59 } 60 61 ~DenseSlabAlloc() { 62 for (uptr i = 0; i < kL1Size; i++) { 63 if (map_[i] != 0) 64 UnmapOrDie(map_[i], kL2Size * sizeof(T)); 65 } 66 } 67 68 IndexT Alloc(Cache *c) { 69 if (c->pos == 0) 70 Refill(c); 71 return c->cache[--c->pos]; 72 } 73 74 void Free(Cache *c, IndexT idx) { 75 DCHECK_NE(idx, 0); 76 if (c->pos == Cache::kSize) 77 Drain(c); 78 c->cache[c->pos++] = idx; 79 } 80 81 T *Map(IndexT idx) { 82 DCHECK_NE(idx, 0); 83 DCHECK_LE(idx, kL1Size * kL2Size); 84 return &map_[idx / kL2Size][idx % kL2Size]; 85 } 86 87 void FlushCache(Cache *c) { 88 if (!c->pos) 89 return; 90 SpinMutexLock lock(&mtx_); 91 while (c->pos) { 92 IndexT idx = c->cache[--c->pos]; 93 *(IndexT*)Map(idx) = freelist_; 94 freelist_ = idx; 95 } 96 } 97 98 void InitCache(Cache *c) { 99 c->pos = 0; 100 internal_memset(c->cache, 0, sizeof(c->cache)); 101 } 102 103 uptr AllocatedMemory() const { 104 return atomic_load_relaxed(&fillpos_) * kL2Size * sizeof(T); 105 } 106 107 template <typename Func> 108 void ForEach(Func func) { 109 SpinMutexLock lock(&mtx_); 110 uptr fillpos = atomic_load_relaxed(&fillpos_); 111 for (uptr l1 = 0; l1 < fillpos; l1++) { 112 for (IndexT l2 = l1 == 0 ? 1 : 0; l2 < kL2Size; l2++) func(&map_[l1][l2]); 113 } 114 } 115 116 private: 117 T *map_[kL1Size]; 118 SpinMutex mtx_; 119 IndexT freelist_ = {0}; 120 atomic_uintptr_t fillpos_ = {0}; 121 const char *const name_; 122 123 void Refill(Cache *c) { 124 SpinMutexLock lock(&mtx_); 125 if (freelist_ == 0) { 126 uptr fillpos = atomic_load_relaxed(&fillpos_); 127 if (fillpos == kL1Size) { 128 Printf("ThreadSanitizer: %s overflow (%zu*%zu). Dying.\n", 129 name_, kL1Size, kL2Size); 130 Die(); 131 } 132 VPrintf(2, "ThreadSanitizer: growing %s: %zu out of %zu*%zu\n", name_, 133 fillpos, kL1Size, kL2Size); 134 T *batch = (T*)MmapOrDie(kL2Size * sizeof(T), name_); 135 // Reserve 0 as invalid index. 136 IndexT start = fillpos == 0 ? 1 : 0; 137 for (IndexT i = start; i < kL2Size; i++) { 138 new(batch + i) T; 139 *(IndexT *)(batch + i) = i + 1 + fillpos * kL2Size; 140 } 141 *(IndexT*)(batch + kL2Size - 1) = 0; 142 freelist_ = fillpos * kL2Size + start; 143 map_[fillpos] = batch; 144 atomic_store_relaxed(&fillpos_, fillpos + 1); 145 } 146 for (uptr i = 0; i < Cache::kSize / 2 && freelist_ != 0; i++) { 147 IndexT idx = freelist_; 148 c->cache[c->pos++] = idx; 149 freelist_ = *(IndexT*)Map(idx); 150 } 151 } 152 153 void Drain(Cache *c) { 154 SpinMutexLock lock(&mtx_); 155 for (uptr i = 0; i < Cache::kSize / 2; i++) { 156 IndexT idx = c->cache[--c->pos]; 157 *(IndexT*)Map(idx) = freelist_; 158 freelist_ = idx; 159 } 160 } 161 }; 162 163 } // namespace __tsan 164 165 #endif // TSAN_DENSE_ALLOC_H 166