libsanitizer/tsan/tsan_dense_alloc.h

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