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
24namespace __tsan {
25
26class 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
35template <typename T, uptr kL1Size, uptr kL2Size, u64 kReserved = 0>
36class 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(s: c->cache, c: 0, n: sizeof(c->cache));
94 }
95
96 uptr AllocatedMemory() const {
97 return atomic_load_relaxed(a: &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(a: &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_ = {.val_dont_use: 0};
117 atomic_uintptr_t fillpos_ = {.val_dont_use: 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(a: &freelist_, mo: 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(a: &freelist_, cmp: &cmp, xchg,
142 mo: 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(idx: head_idx);
161 u64 xchg;
162 u64 cmp = atomic_load(a: &freelist_, mo: 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(a: &freelist_, cmp: &cmp, xchg,
167 mo: memory_order_acq_rel));
168 }
169
170 NOINLINE void AllocSuperBlock(Cache *c) {
171 Lock lock(&mtx_);
172 uptr fillpos = atomic_load_relaxed(a: &fillpos_);
173 if (fillpos == kL1Size) {
174 Printf(format: "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(size: kL2Size * sizeof(T), mem_type: 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(a: &fillpos_, v: fillpos + 1);
190 CHECK(c->pos);
191 }
192};
193
194} // namespace __tsan
195
196#endif // TSAN_DENSE_ALLOC_H
197