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 26namespace __tsan { 27 28class 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 36template<typename T, uptr kL1Size, uptr kL2Size> 37class DenseSlabAlloc { 38 public: 39 typedef DenseSlabAllocCache Cache; 40 typedef typename Cache::IndexT IndexT; 41 42 explicit DenseSlabAlloc(const char *name) { 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 name_ = name; 53 } 54 55 ~DenseSlabAlloc() { 56 for (uptr i = 0; i < kL1Size; i++) { 57 if (map_[i] != 0) 58 UnmapOrDie(map_[i], kL2Size * sizeof(T)); 59 } 60 } 61 62 IndexT Alloc(Cache *c) { 63 if (c->pos == 0) 64 Refill(c); 65 return c->cache[--c->pos]; 66 } 67 68 void Free(Cache *c, IndexT idx) { 69 DCHECK_NE(idx, 0); 70 if (c->pos == Cache::kSize) 71 Drain(c); 72 c->cache[c->pos++] = idx; 73 } 74 75 T *Map(IndexT idx) { 76 DCHECK_NE(idx, 0); 77 DCHECK_LE(idx, kL1Size * kL2Size); 78 return &map_[idx / kL2Size][idx % kL2Size]; 79 } 80 81 void FlushCache(Cache *c) { 82 SpinMutexLock lock(&mtx_); 83 while (c->pos) { 84 IndexT idx = c->cache[--c->pos]; 85 *(IndexT*)Map(idx) = freelist_; 86 freelist_ = idx; 87 } 88 } 89 90 void InitCache(Cache *c) { 91 c->pos = 0; 92 internal_memset(c->cache, 0, sizeof(c->cache)); 93 } 94 95 private: 96 T *map_[kL1Size]; 97 SpinMutex mtx_; 98 IndexT freelist_; 99 uptr fillpos_; 100 const char *name_; 101 102 void Refill(Cache *c) { 103 SpinMutexLock lock(&mtx_); 104 if (freelist_ == 0) { 105 if (fillpos_ == kL1Size) { 106 Printf("ThreadSanitizer: %s overflow (%zu*%zu). Dying.\n", 107 name_, kL1Size, kL2Size); 108 Die(); 109 } 110 VPrintf(2, "ThreadSanitizer: growing %s: %zu out of %zu*%zu\n", 111 name_, fillpos_, kL1Size, kL2Size); 112 T *batch = (T*)MmapOrDie(kL2Size * sizeof(T), name_); 113 // Reserve 0 as invalid index. 114 IndexT start = fillpos_ == 0 ? 1 : 0; 115 for (IndexT i = start; i < kL2Size; i++) { 116 new(batch + i) T; 117 *(IndexT*)(batch + i) = i + 1 + fillpos_ * kL2Size; 118 } 119 *(IndexT*)(batch + kL2Size - 1) = 0; 120 freelist_ = fillpos_ * kL2Size + start; 121 map_[fillpos_++] = batch; 122 } 123 for (uptr i = 0; i < Cache::kSize / 2 && freelist_ != 0; i++) { 124 IndexT idx = freelist_; 125 c->cache[c->pos++] = idx; 126 freelist_ = *(IndexT*)Map(idx); 127 } 128 } 129 130 void Drain(Cache *c) { 131 SpinMutexLock lock(&mtx_); 132 for (uptr i = 0; i < Cache::kSize / 2; i++) { 133 IndexT idx = c->cache[--c->pos]; 134 *(IndexT*)Map(idx) = freelist_; 135 freelist_ = idx; 136 } 137 } 138}; 139 140} // namespace __tsan 141 142#endif // TSAN_DENSE_ALLOC_H 143