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   explicit DenseSlabAlloc(const char *name) {
  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     name_ = name;
  51   }
  52
  53   ~DenseSlabAlloc() {
  54     for (uptr i = 0; i < kL1Size; i++) {
  55       if (map_[i] != 0)
  56         UnmapOrDie(map_[i], kL2Size * sizeof(T));
  57     }
  58   }
  59
  60   IndexT Alloc(Cache *c) {
  61     if (c->pos == 0)
  62       Refill(c);
  63     return c->cache[--c->pos];
  64   }
  65
  66   void Free(Cache *c, IndexT idx) {
  67     DCHECK_NE(idx, 0);
  68     if (c->pos == Cache::kSize)
  69       Drain(c);
  70     c->cache[c->pos++] = idx;
  71   }
  72
  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
  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
  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   const char *name_;
  99
 100   void Refill(Cache *c) {
 101     SpinMutexLock lock(&mtx_);
 102     if (freelist_ == 0) {
 103       if (fillpos_ == kL1Size) {
 104         Printf("ThreadSanitizer: %s overflow (%zu*%zu). Dying.\n",
 105             name_, kL1Size, kL2Size);
 106         Die();
 107       }
 108       VPrintf(2, "ThreadSanitizer: growing %s: %zu out of %zu*%zu\n",
 109           name_, fillpos_, kL1Size, kL2Size);
 110       T *batch = (T*)MmapOrDie(kL2Size * sizeof(T), name_);
 111       // Reserve 0 as invalid index.
 112       IndexT start = fillpos_ == 0 ? 1 : 0;
 113       for (IndexT i = start; i < kL2Size; i++) {
 114         new(batch + i) T;
 115         *(IndexT*)(batch + i) = i + 1 + fillpos_ * kL2Size;
 116       }
 117       *(IndexT*)(batch + kL2Size - 1) = 0;
 118       freelist_ = fillpos_ * kL2Size + start;
 119       map_[fillpos_++] = batch;
 120     }
 121     for (uptr i = 0; i < Cache::kSize / 2 && freelist_ != 0; i++) {
 122       IndexT idx = freelist_;
 123       c->cache[c->pos++] = idx;
 124       freelist_ = *(IndexT*)Map(idx);
 125     }
 126   }
 127
 128   void Drain(Cache *c) {
 129     SpinMutexLock lock(&mtx_);
 130     for (uptr i = 0; i < Cache::kSize / 2; i++) {
 131       IndexT idx = c->cache[--c->pos];
 132       *(IndexT*)Map(idx) = freelist_;
 133       freelist_ = idx;
 134     }
 135   }
 136 };
 137
 138 }  // namespace __tsan
 139
 140 #endif  // TSAN_DENSE_ALLOC_H