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 
DenseSlabAlloc(const char * name)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 
~DenseSlabAlloc()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 
Alloc(Cache * c)60   IndexT Alloc(Cache *c) {
61     if (c->pos == 0)
62       Refill(c);
63     return c->cache[--c->pos];
64   }
65 
Free(Cache * c,IndexT idx)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 
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   const char *name_;
99 
Refill(Cache * c)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 
Drain(Cache * c)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
141