1 //===-- tsan_dense_alloc.h --------------------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file is a part of ThreadSanitizer (TSan), a race detector. 11 // 12 // A DenseSlabAlloc is a freelist-based allocator of fixed-size objects. 13 // DenseSlabAllocCache is a thread-local cache for DenseSlabAlloc. 14 // The only difference with traditional slab allocators is that DenseSlabAlloc 15 // allocates/free indices of objects and provide a functionality to map 16 // the index onto the real pointer. The index is u32, that is, 2 times smaller 17 // than uptr (hense the Dense prefix). 18 //===----------------------------------------------------------------------===// 19 #ifndef TSAN_DENSE_ALLOC_H 20 #define TSAN_DENSE_ALLOC_H 21 22 #include "sanitizer_common/sanitizer_common.h" 23 #include "tsan_defs.h" 24 #include "tsan_mutex.h" 25 26 namespace __tsan { 27 28 class DenseSlabAllocCache { 29 static const uptr kSize = 128; 30 typedef u32 IndexT; 31 uptr pos; 32 IndexT cache[kSize]; 33 template<typename T, uptr kL1Size, uptr kL2Size> friend class DenseSlabAlloc; 34 }; 35 36 template<typename T, uptr kL1Size, uptr kL2Size> 37 class DenseSlabAlloc { 38 public: 39 typedef DenseSlabAllocCache Cache; 40 typedef typename Cache::IndexT IndexT; 41 DenseSlabAlloc()42 DenseSlabAlloc() { 43 // Check that kL1Size and kL2Size are sane. 44 CHECK_EQ(kL1Size & (kL1Size - 1), 0); 45 CHECK_EQ(kL2Size & (kL2Size - 1), 0); 46 CHECK_GE(1ull << (sizeof(IndexT) * 8), kL1Size * kL2Size); 47 // Check that it makes sense to use the dense alloc. 48 CHECK_GE(sizeof(T), sizeof(IndexT)); 49 internal_memset(map_, 0, sizeof(map_)); 50 freelist_ = 0; 51 fillpos_ = 0; 52 } 53 ~DenseSlabAlloc()54 ~DenseSlabAlloc() { 55 for (uptr i = 0; i < kL1Size; i++) { 56 if (map_[i] != 0) 57 UnmapOrDie(map_[i], kL2Size * sizeof(T)); 58 } 59 } 60 Alloc(Cache * c)61 IndexT Alloc(Cache *c) { 62 if (c->pos == 0) 63 Refill(c); 64 return c->cache[--c->pos]; 65 } 66 Free(Cache * c,IndexT idx)67 void Free(Cache *c, IndexT idx) { 68 if (c->pos == Cache::kSize) 69 Drain(c); 70 c->cache[c->pos++] = idx; 71 } 72 Map(IndexT idx)73 T *Map(IndexT idx) { 74 DCHECK_NE(idx, 0); 75 DCHECK_LE(idx, kL1Size * kL2Size); 76 return &map_[idx / kL2Size][idx % kL2Size]; 77 } 78 FlushCache(Cache * c)79 void FlushCache(Cache *c) { 80 SpinMutexLock lock(&mtx_); 81 while (c->pos) { 82 IndexT idx = c->cache[--c->pos]; 83 *(IndexT*)Map(idx) = freelist_; 84 freelist_ = idx; 85 } 86 } 87 InitCache(Cache * c)88 void InitCache(Cache *c) { 89 c->pos = 0; 90 internal_memset(c->cache, 0, sizeof(c->cache)); 91 } 92 93 private: 94 T *map_[kL1Size]; 95 SpinMutex mtx_; 96 IndexT freelist_; 97 uptr fillpos_; 98 Refill(Cache * c)99 void Refill(Cache *c) { 100 SpinMutexLock lock(&mtx_); 101 if (freelist_ == 0) { 102 if (fillpos_ == kL1Size) { 103 Printf("ThreadSanitizer: DenseSlabAllocator overflow. Dying.\n"); 104 Die(); 105 } 106 T *batch = (T*)MmapOrDie(kL2Size * sizeof(T), "DenseSlabAllocator"); 107 // Reserve 0 as invalid index. 108 IndexT start = fillpos_ == 0 ? 1 : 0; 109 for (IndexT i = start; i < kL2Size; i++) { 110 new(batch + i) T(); 111 *(IndexT*)(batch + i) = i + 1 + fillpos_ * kL2Size; 112 } 113 *(IndexT*)(batch + kL2Size - 1) = 0; 114 freelist_ = fillpos_ * kL2Size + start; 115 map_[fillpos_++] = batch; 116 } 117 for (uptr i = 0; i < Cache::kSize / 2 && freelist_ != 0; i++) { 118 IndexT idx = freelist_; 119 c->cache[c->pos++] = idx; 120 freelist_ = *(IndexT*)Map(idx); 121 } 122 } 123 Drain(Cache * c)124 void Drain(Cache *c) { 125 SpinMutexLock lock(&mtx_); 126 for (uptr i = 0; i < Cache::kSize / 2; i++) { 127 IndexT idx = c->cache[--c->pos]; 128 *(IndexT*)Map(idx) = freelist_; 129 freelist_ = idx; 130 } 131 } 132 }; 133 134 } // namespace __tsan 135 136 #endif // TSAN_DENSE_ALLOC_H 137