1 //===-- tsan_dense_alloc.h --------------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file is a part of ThreadSanitizer (TSan), a race detector.
10 //
11 // A DenseSlabAlloc is a freelist-based allocator of fixed-size objects.
12 // DenseSlabAllocCache is a thread-local cache for DenseSlabAlloc.
13 // The only difference with traditional slab allocators is that DenseSlabAlloc
14 // allocates/free indices of objects and provide a functionality to map
15 // the index onto the real pointer. The index is u32, that is, 2 times smaller
16 // than uptr (hense the Dense prefix).
17 //===----------------------------------------------------------------------===//
18 #ifndef TSAN_DENSE_ALLOC_H
19 #define TSAN_DENSE_ALLOC_H
20 
21 #include "sanitizer_common/sanitizer_common.h"
22 #include "tsan_defs.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, uptr, uptr, u64>
32   friend class DenseSlabAlloc;
33 };
34 
35 template <typename T, uptr kL1Size, uptr kL2Size, u64 kReserved = 0>
36 class DenseSlabAlloc {
37  public:
38   typedef DenseSlabAllocCache Cache;
39   typedef typename Cache::IndexT IndexT;
40 
41   static_assert((kL1Size & (kL1Size - 1)) == 0,
42                 "kL1Size must be a power-of-two");
43   static_assert((kL2Size & (kL2Size - 1)) == 0,
44                 "kL2Size must be a power-of-two");
45   static_assert((kL1Size * kL2Size) <= (1ull << (sizeof(IndexT) * 8)),
46                 "kL1Size/kL2Size are too large");
47   static_assert(((kL1Size * kL2Size - 1) & kReserved) == 0,
48                 "reserved bits don't fit");
49   static_assert(sizeof(T) > sizeof(IndexT),
50                 "it doesn't make sense to use dense alloc");
51 
52   DenseSlabAlloc(LinkerInitialized, const char *name) : name_(name) {}
53 
54   explicit DenseSlabAlloc(const char *name)
55       : DenseSlabAlloc(LINKER_INITIALIZED, name) {
56     // It can be very large.
57     // Don't page it in for linker initialized objects.
58     internal_memset(map_, 0, sizeof(map_));
59   }
60 
61   ~DenseSlabAlloc() {
62     for (uptr i = 0; i < kL1Size; i++) {
63       if (map_[i] != 0)
64         UnmapOrDie(map_[i], kL2Size * sizeof(T));
65     }
66   }
67 
68   IndexT Alloc(Cache *c) {
69     if (c->pos == 0)
70       Refill(c);
71     return c->cache[--c->pos];
72   }
73 
74   void Free(Cache *c, IndexT idx) {
75     DCHECK_NE(idx, 0);
76     if (c->pos == Cache::kSize)
77       Drain(c);
78     c->cache[c->pos++] = idx;
79   }
80 
81   T *Map(IndexT idx) {
82     DCHECK_NE(idx, 0);
83     DCHECK_LE(idx, kL1Size * kL2Size);
84     return &map_[idx / kL2Size][idx % kL2Size];
85   }
86 
87   void FlushCache(Cache *c) {
88     while (c->pos) Drain(c);
89   }
90 
91   void InitCache(Cache *c) {
92     c->pos = 0;
93     internal_memset(c->cache, 0, sizeof(c->cache));
94   }
95 
96   uptr AllocatedMemory() const {
97     return atomic_load_relaxed(&fillpos_) * kL2Size * sizeof(T);
98   }
99 
100   template <typename Func>
101   void ForEach(Func func) {
102     Lock lock(&mtx_);
103     uptr fillpos = atomic_load_relaxed(&fillpos_);
104     for (uptr l1 = 0; l1 < fillpos; l1++) {
105       for (IndexT l2 = l1 == 0 ? 1 : 0; l2 < kL2Size; l2++) func(&map_[l1][l2]);
106     }
107   }
108 
109  private:
110   T *map_[kL1Size];
111   Mutex mtx_;
112   // The freelist is organized as a lock-free stack of batches of nodes.
113   // The stack itself uses Block::next links, while the batch within each
114   // stack node uses Block::batch links.
115   // Low 32-bits of freelist_ is the node index, top 32-bits is ABA-counter.
116   atomic_uint64_t freelist_ = {0};
117   atomic_uintptr_t fillpos_ = {0};
118   const char *const name_;
119 
120   struct Block {
121     IndexT next;
122     IndexT batch;
123   };
124 
125   Block *MapBlock(IndexT idx) { return reinterpret_cast<Block *>(Map(idx)); }
126 
127   static constexpr u64 kCounterInc = 1ull << 32;
128   static constexpr u64 kCounterMask = ~(kCounterInc - 1);
129 
130   NOINLINE void Refill(Cache *c) {
131     // Pop 1 batch of nodes from the freelist.
132     IndexT idx;
133     u64 xchg;
134     u64 cmp = atomic_load(&freelist_, memory_order_acquire);
135     do {
136       idx = static_cast<IndexT>(cmp);
137       if (!idx)
138         return AllocSuperBlock(c);
139       Block *ptr = MapBlock(idx);
140       xchg = ptr->next | (cmp & kCounterMask);
141     } while (!atomic_compare_exchange_weak(&freelist_, &cmp, xchg,
142                                            memory_order_acq_rel));
143     // Unpack it into c->cache.
144     while (idx) {
145       c->cache[c->pos++] = idx;
146       idx = MapBlock(idx)->batch;
147     }
148   }
149 
150   NOINLINE void Drain(Cache *c) {
151     // Build a batch of at most Cache::kSize / 2 nodes linked by Block::batch.
152     IndexT head_idx = 0;
153     for (uptr i = 0; i < Cache::kSize / 2 && c->pos; i++) {
154       IndexT idx = c->cache[--c->pos];
155       Block *ptr = MapBlock(idx);
156       ptr->batch = head_idx;
157       head_idx = idx;
158     }
159     // Push it onto the freelist stack.
160     Block *head = MapBlock(head_idx);
161     u64 xchg;
162     u64 cmp = atomic_load(&freelist_, memory_order_acquire);
163     do {
164       head->next = static_cast<IndexT>(cmp);
165       xchg = head_idx | (cmp & kCounterMask) + kCounterInc;
166     } while (!atomic_compare_exchange_weak(&freelist_, &cmp, xchg,
167                                            memory_order_acq_rel));
168   }
169 
170   NOINLINE void AllocSuperBlock(Cache *c) {
171     Lock lock(&mtx_);
172     uptr fillpos = atomic_load_relaxed(&fillpos_);
173     if (fillpos == kL1Size) {
174       Printf("ThreadSanitizer: %s overflow (%zu*%zu). Dying.\n", name_, kL1Size,
175              kL2Size);
176       Die();
177     }
178     VPrintf(2, "ThreadSanitizer: growing %s: %zu out of %zu*%zu\n", name_,
179             fillpos, kL1Size, kL2Size);
180     T *batch = (T *)MmapOrDie(kL2Size * sizeof(T), name_);
181     map_[fillpos] = batch;
182     // Reserve 0 as invalid index.
183     for (IndexT i = fillpos ? 0 : 1; i < kL2Size; i++) {
184       new (batch + i) T;
185       c->cache[c->pos++] = i + fillpos * kL2Size;
186       if (c->pos == Cache::kSize)
187         Drain(c);
188     }
189     atomic_store_relaxed(&fillpos_, fillpos + 1);
190     CHECK(c->pos);
191   }
192 };
193 
194 }  // namespace __tsan
195 
196 #endif  // TSAN_DENSE_ALLOC_H
197