1//===-- sanitizer_allocator_primary32.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// Part of the Sanitizer Allocator.
10//
11//===----------------------------------------------------------------------===//
12#ifndef SANITIZER_ALLOCATOR_H
13#error This file must be included inside sanitizer_allocator.h
14#endif
15
16template<class SizeClassAllocator> struct SizeClassAllocator32LocalCache;
17
18// SizeClassAllocator32 -- allocator for 32-bit address space.
19// This allocator can theoretically be used on 64-bit arch, but there it is less
20// efficient than SizeClassAllocator64.
21//
22// [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can
23// be returned by MmapOrDie().
24//
25// Region:
26// a result of a single call to MmapAlignedOrDieOnFatalError(kRegionSize,
27// kRegionSize).
28// Since the regions are aligned by kRegionSize, there are exactly
29// kNumPossibleRegions possible regions in the address space and so we keep
30// a ByteMap possible_regions to store the size classes of each Region.
31// 0 size class means the region is not used by the allocator.
32//
33// One Region is used to allocate chunks of a single size class.
34// A Region looks like this:
35// UserChunk1 .. UserChunkN <gap> MetaChunkN .. MetaChunk1
36//
37// In order to avoid false sharing the objects of this class should be
38// chache-line aligned.
39
40struct SizeClassAllocator32FlagMasks { // Bit masks.
41 enum {
42 kRandomShuffleChunks = 1,
43 kUseSeparateSizeClassForBatch = 2,
44 };
45};
46
47template <class Params>
48class SizeClassAllocator32 {
49 private:
50 static const u64 kTwoLevelByteMapSize1 =
51 (Params::kSpaceSize >> Params::kRegionSizeLog) >> 12;
52 static const u64 kMinFirstMapSizeTwoLevelByteMap = 4;
53
54 public:
55 using AddressSpaceView = typename Params::AddressSpaceView;
56 static const uptr kSpaceBeg = Params::kSpaceBeg;
57 static const u64 kSpaceSize = Params::kSpaceSize;
58 static const uptr kMetadataSize = Params::kMetadataSize;
59 typedef typename Params::SizeClassMap SizeClassMap;
60 static const uptr kRegionSizeLog = Params::kRegionSizeLog;
61 typedef typename Params::MapUnmapCallback MapUnmapCallback;
62 using ByteMap = typename conditional<
63 (kTwoLevelByteMapSize1 < kMinFirstMapSizeTwoLevelByteMap),
64 FlatByteMap<(Params::kSpaceSize >> Params::kRegionSizeLog),
65 AddressSpaceView>,
66 TwoLevelByteMap<kTwoLevelByteMapSize1, 1 << 12, AddressSpaceView>>::type;
67
68 COMPILER_CHECK(!SANITIZER_SIGN_EXTENDED_ADDRESSES ||
69 (kSpaceSize & (kSpaceSize - 1)) == 0);
70
71 static const bool kRandomShuffleChunks = Params::kFlags &
72 SizeClassAllocator32FlagMasks::kRandomShuffleChunks;
73 static const bool kUseSeparateSizeClassForBatch = Params::kFlags &
74 SizeClassAllocator32FlagMasks::kUseSeparateSizeClassForBatch;
75
76 struct TransferBatch {
77 static const uptr kMaxNumCached = SizeClassMap::kMaxNumCachedHint - 2;
78 void SetFromArray(void *batch[], uptr count) {
79 DCHECK_LE(count, kMaxNumCached);
80 count_ = count;
81 for (uptr i = 0; i < count; i++)
82 batch_[i] = batch[i];
83 }
84 uptr Count() const { return count_; }
85 void Clear() { count_ = 0; }
86 void Add(void *ptr) {
87 batch_[count_++] = ptr;
88 DCHECK_LE(count_, kMaxNumCached);
89 }
90 void CopyToArray(void *to_batch[]) const {
91 for (uptr i = 0, n = Count(); i < n; i++)
92 to_batch[i] = batch_[i];
93 }
94
95 // How much memory do we need for a batch containing n elements.
96 static uptr AllocationSizeRequiredForNElements(uptr n) {
97 return sizeof(uptr) * 2 + sizeof(void *) * n;
98 }
99 static uptr MaxCached(uptr size) {
100 return Min(kMaxNumCached, SizeClassMap::MaxCachedHint(size));
101 }
102
103 TransferBatch *next;
104
105 private:
106 uptr count_;
107 void *batch_[kMaxNumCached];
108 };
109
110 static const uptr kBatchSize = sizeof(TransferBatch);
111 COMPILER_CHECK((kBatchSize & (kBatchSize - 1)) == 0);
112 COMPILER_CHECK(kBatchSize == SizeClassMap::kMaxNumCachedHint * sizeof(uptr));
113
114 static uptr ClassIdToSize(uptr class_id) {
115 return (class_id == SizeClassMap::kBatchClassID) ?
116 kBatchSize : SizeClassMap::Size(class_id);
117 }
118
119 typedef SizeClassAllocator32<Params> ThisT;
120 typedef SizeClassAllocator32LocalCache<ThisT> AllocatorCache;
121
122 void Init(s32 release_to_os_interval_ms, uptr heap_start = 0) {
123 CHECK(!heap_start);
124 possible_regions.Init();
125 internal_memset(size_class_info_array, 0, sizeof(size_class_info_array));
126 }
127
128 s32 ReleaseToOSIntervalMs() const {
129 return kReleaseToOSIntervalNever;
130 }
131
132 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
133 // This is empty here. Currently only implemented in 64-bit allocator.
134 }
135
136 void ForceReleaseToOS() {
137 // Currently implemented in 64-bit allocator only.
138 }
139
140 void *MapWithCallback(uptr size) {
141 void *res = MmapOrDie(size, mem_type: PrimaryAllocatorName);
142 MapUnmapCallback().OnMap((uptr)res, size);
143 return res;
144 }
145
146 void UnmapWithCallback(uptr beg, uptr size) {
147 MapUnmapCallback().OnUnmap(beg, size);
148 UnmapOrDie(addr: reinterpret_cast<void *>(beg), size);
149 }
150
151 static bool CanAllocate(uptr size, uptr alignment) {
152 return size <= SizeClassMap::kMaxSize &&
153 alignment <= SizeClassMap::kMaxSize;
154 }
155
156 void *GetMetaData(const void *p) {
157 CHECK(kMetadataSize);
158 CHECK(PointerIsMine(p));
159 uptr mem = reinterpret_cast<uptr>(p);
160 uptr beg = ComputeRegionBeg(mem);
161 uptr size = ClassIdToSize(class_id: GetSizeClass(p));
162 u32 offset = mem - beg;
163 uptr n = offset / (u32)size; // 32-bit division
164 uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize;
165 return reinterpret_cast<void*>(meta);
166 }
167
168 NOINLINE TransferBatch *AllocateBatch(AllocatorStats *stat, AllocatorCache *c,
169 uptr class_id) {
170 DCHECK_LT(class_id, kNumClasses);
171 SizeClassInfo *sci = GetSizeClassInfo(class_id);
172 SpinMutexLock l(&sci->mutex);
173 if (sci->free_list.empty()) {
174 if (UNLIKELY(!PopulateFreeList(stat, c, sci, class_id)))
175 return nullptr;
176 DCHECK(!sci->free_list.empty());
177 }
178 TransferBatch *b = sci->free_list.front();
179 sci->free_list.pop_front();
180 return b;
181 }
182
183 NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id,
184 TransferBatch *b) {
185 DCHECK_LT(class_id, kNumClasses);
186 CHECK_GT(b->Count(), 0);
187 SizeClassInfo *sci = GetSizeClassInfo(class_id);
188 SpinMutexLock l(&sci->mutex);
189 sci->free_list.push_front(b);
190 }
191
192 bool PointerIsMine(const void *p) const {
193 uptr mem = reinterpret_cast<uptr>(p);
194 if (SANITIZER_SIGN_EXTENDED_ADDRESSES)
195 mem &= (kSpaceSize - 1);
196 if (mem < kSpaceBeg || mem >= kSpaceBeg + kSpaceSize)
197 return false;
198 return GetSizeClass(p) != 0;
199 }
200
201 uptr GetSizeClass(const void *p) const {
202 uptr id = ComputeRegionId(mem: reinterpret_cast<uptr>(p));
203 return possible_regions.contains(id) ? possible_regions[id] : 0;
204 }
205
206 void *GetBlockBegin(const void *p) {
207 CHECK(PointerIsMine(p));
208 uptr mem = reinterpret_cast<uptr>(p);
209 uptr beg = ComputeRegionBeg(mem);
210 uptr size = ClassIdToSize(class_id: GetSizeClass(p));
211 u32 offset = mem - beg;
212 u32 n = offset / (u32)size; // 32-bit division
213 uptr res = beg + (n * (u32)size);
214 return reinterpret_cast<void*>(res);
215 }
216
217 uptr GetActuallyAllocatedSize(void *p) {
218 CHECK(PointerIsMine(p));
219 return ClassIdToSize(class_id: GetSizeClass(p));
220 }
221
222 static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
223
224 uptr TotalMemoryUsed() {
225 // No need to lock here.
226 uptr res = 0;
227 for (uptr i = 0; i < kNumPossibleRegions; i++)
228 if (possible_regions[i])
229 res += kRegionSize;
230 return res;
231 }
232
233 void TestOnlyUnmap() {
234 for (uptr i = 0; i < kNumPossibleRegions; i++)
235 if (possible_regions[i])
236 UnmapWithCallback(beg: (i * kRegionSize), size: kRegionSize);
237 }
238
239 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
240 // introspection API.
241 void ForceLock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS {
242 for (uptr i = 0; i < kNumClasses; i++) {
243 GetSizeClassInfo(class_id: i)->mutex.Lock();
244 }
245 }
246
247 void ForceUnlock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS {
248 for (int i = kNumClasses - 1; i >= 0; i--) {
249 GetSizeClassInfo(class_id: i)->mutex.Unlock();
250 }
251 }
252
253 // Iterate over all existing chunks.
254 // The allocator must be locked when calling this function.
255 void ForEachChunk(ForEachChunkCallback callback, void *arg) const {
256 for (uptr region = 0; region < kNumPossibleRegions; region++)
257 if (possible_regions.contains(region) && possible_regions[region]) {
258 uptr chunk_size = ClassIdToSize(class_id: possible_regions[region]);
259 uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize);
260 uptr region_beg = region * kRegionSize;
261 for (uptr chunk = region_beg;
262 chunk < region_beg + max_chunks_in_region * chunk_size;
263 chunk += chunk_size) {
264 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
265 callback(chunk, arg);
266 }
267 }
268 }
269
270 void PrintStats() {}
271
272 static uptr AdditionalSize() { return 0; }
273
274 typedef SizeClassMap SizeClassMapT;
275 static const uptr kNumClasses = SizeClassMap::kNumClasses;
276
277 private:
278 static const uptr kRegionSize = 1 << kRegionSizeLog;
279 static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize;
280
281 struct alignas(SANITIZER_CACHE_LINE_SIZE) SizeClassInfo {
282 StaticSpinMutex mutex;
283 IntrusiveList<TransferBatch> free_list;
284 u32 rand_state;
285 };
286 COMPILER_CHECK(sizeof(SizeClassInfo) % kCacheLineSize == 0);
287
288 uptr ComputeRegionId(uptr mem) const {
289 if (SANITIZER_SIGN_EXTENDED_ADDRESSES)
290 mem &= (kSpaceSize - 1);
291 const uptr res = mem >> kRegionSizeLog;
292 CHECK_LT(res, kNumPossibleRegions);
293 return res;
294 }
295
296 uptr ComputeRegionBeg(uptr mem) const { return mem & ~(kRegionSize - 1); }
297
298 uptr AllocateRegion(AllocatorStats *stat, uptr class_id) {
299 DCHECK_LT(class_id, kNumClasses);
300 const uptr res = reinterpret_cast<uptr>(MmapAlignedOrDieOnFatalError(
301 size: kRegionSize, alignment: kRegionSize, mem_type: PrimaryAllocatorName));
302 if (UNLIKELY(!res))
303 return 0;
304 MapUnmapCallback().OnMap(res, kRegionSize);
305 stat->Add(i: AllocatorStatMapped, v: kRegionSize);
306 CHECK(IsAligned(res, kRegionSize));
307 possible_regions[ComputeRegionId(mem: res)] = class_id;
308 return res;
309 }
310
311 SizeClassInfo *GetSizeClassInfo(uptr class_id) {
312 DCHECK_LT(class_id, kNumClasses);
313 return &size_class_info_array[class_id];
314 }
315
316 bool PopulateBatches(AllocatorCache *c, SizeClassInfo *sci, uptr class_id,
317 TransferBatch **current_batch, uptr max_count,
318 uptr *pointers_array, uptr count) {
319 // If using a separate class for batches, we do not need to shuffle it.
320 if (kRandomShuffleChunks && (!kUseSeparateSizeClassForBatch ||
321 class_id != SizeClassMap::kBatchClassID))
322 RandomShuffle(pointers_array, count, &sci->rand_state);
323 TransferBatch *b = *current_batch;
324 for (uptr i = 0; i < count; i++) {
325 if (!b) {
326 b = c->CreateBatch(class_id, this, (TransferBatch*)pointers_array[i]);
327 if (UNLIKELY(!b))
328 return false;
329 b->Clear();
330 }
331 b->Add((void*)pointers_array[i]);
332 if (b->Count() == max_count) {
333 sci->free_list.push_back(b);
334 b = nullptr;
335 }
336 }
337 *current_batch = b;
338 return true;
339 }
340
341 bool PopulateFreeList(AllocatorStats *stat, AllocatorCache *c,
342 SizeClassInfo *sci, uptr class_id) {
343 const uptr region = AllocateRegion(stat, class_id);
344 if (UNLIKELY(!region))
345 return false;
346 if (kRandomShuffleChunks)
347 if (UNLIKELY(sci->rand_state == 0))
348 // The random state is initialized from ASLR (PIE) and time.
349 sci->rand_state = reinterpret_cast<uptr>(sci) ^ NanoTime();
350 const uptr size = ClassIdToSize(class_id);
351 const uptr n_chunks = kRegionSize / (size + kMetadataSize);
352 const uptr max_count = TransferBatch::MaxCached(size);
353 DCHECK_GT(max_count, 0);
354 TransferBatch *b = nullptr;
355 constexpr uptr kShuffleArraySize = 48;
356 UNINITIALIZED uptr shuffle_array[kShuffleArraySize];
357 uptr count = 0;
358 for (uptr i = region; i < region + n_chunks * size; i += size) {
359 shuffle_array[count++] = i;
360 if (count == kShuffleArraySize) {
361 if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,
362 shuffle_array, count)))
363 return false;
364 count = 0;
365 }
366 }
367 if (count) {
368 if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,
369 shuffle_array, count)))
370 return false;
371 }
372 if (b) {
373 CHECK_GT(b->Count(), 0);
374 sci->free_list.push_back(b);
375 }
376 return true;
377 }
378
379 ByteMap possible_regions;
380 SizeClassInfo size_class_info_array[kNumClasses];
381};
382