1 //===-- sanitizer_allocator_primary32.h -------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // Part of the Sanitizer Allocator.
11 //===----------------------------------------------------------------------===//
12 #ifndef SANITIZER_ALLOCATOR_H
13 #error This file must be included inside sanitizer_allocator.h
16 template<class SizeClassAllocator> struct SizeClassAllocator32LocalCache;
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.
22 // [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can
23 // be returned by MmapOrDie().
26 // a result of a single call to MmapAlignedOrDieOnFatalError(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.
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
37 // In order to avoid false sharing the objects of this class should be
38 // chache-line aligned.
40 struct SizeClassAllocator32FlagMasks { // Bit masks.
42 kRandomShuffleChunks = 1,
43 kUseSeparateSizeClassForBatch = 2,
47 template <class Params>
48 class SizeClassAllocator32 {
50 static const u64 kTwoLevelByteMapSize1 =
51 (Params::kSpaceSize >> Params::kRegionSizeLog) >> 12;
52 static const u64 kMinFirstMapSizeTwoLevelByteMap = 4;
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),
66 TwoLevelByteMap<kTwoLevelByteMapSize1, 1 << 12, AddressSpaceView>>::type;
68 COMPILER_CHECK(!SANITIZER_SIGN_EXTENDED_ADDRESSES ||
69 (kSpaceSize & (kSpaceSize - 1)) == 0);
71 static const bool kRandomShuffleChunks = Params::kFlags &
72 SizeClassAllocator32FlagMasks::kRandomShuffleChunks;
73 static const bool kUseSeparateSizeClassForBatch = Params::kFlags &
74 SizeClassAllocator32FlagMasks::kUseSeparateSizeClassForBatch;
76 struct TransferBatch {
77 static const uptr kMaxNumCached = SizeClassMap::kMaxNumCachedHint - 2;
78 void SetFromArray(void *batch[], uptr count) {
79 DCHECK_LE(count, kMaxNumCached);
81 for (uptr i = 0; i < count; i++)
84 uptr Count() const { return count_; }
85 void Clear() { count_ = 0; }
87 batch_[count_++] = ptr;
88 DCHECK_LE(count_, kMaxNumCached);
90 void CopyToArray(void *to_batch[]) const {
91 for (uptr i = 0, n = Count(); i < n; i++)
92 to_batch[i] = batch_[i];
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;
99 static uptr MaxCached(uptr size) {
100 return Min(kMaxNumCached, SizeClassMap::MaxCachedHint(size));
107 void *batch_[kMaxNumCached];
110 static const uptr kBatchSize = sizeof(TransferBatch);
111 COMPILER_CHECK((kBatchSize & (kBatchSize - 1)) == 0);
112 COMPILER_CHECK(kBatchSize == SizeClassMap::kMaxNumCachedHint * sizeof(uptr));
114 static uptr ClassIdToSize(uptr class_id) {
115 return (class_id == SizeClassMap::kBatchClassID) ?
116 kBatchSize : SizeClassMap::Size(class_id);
119 typedef SizeClassAllocator32<Params> ThisT;
120 typedef SizeClassAllocator32LocalCache<ThisT> AllocatorCache;
122 void Init(s32 release_to_os_interval_ms) {
123 possible_regions.Init();
124 internal_memset(size_class_info_array, 0, sizeof(size_class_info_array));
127 s32 ReleaseToOSIntervalMs() const {
128 return kReleaseToOSIntervalNever;
131 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
132 // This is empty here. Currently only implemented in 64-bit allocator.
135 void ForceReleaseToOS() {
136 // Currently implemented in 64-bit allocator only.
139 void *MapWithCallback(uptr size) {
140 void *res = MmapOrDie(size, PrimaryAllocatorName);
141 MapUnmapCallback().OnMap((uptr)res, size);
145 void UnmapWithCallback(uptr beg, uptr size) {
146 MapUnmapCallback().OnUnmap(beg, size);
147 UnmapOrDie(reinterpret_cast<void *>(beg), size);
150 static bool CanAllocate(uptr size, uptr alignment) {
151 return size <= SizeClassMap::kMaxSize &&
152 alignment <= SizeClassMap::kMaxSize;
155 void *GetMetaData(const void *p) {
156 CHECK(PointerIsMine(p));
157 uptr mem = reinterpret_cast<uptr>(p);
158 uptr beg = ComputeRegionBeg(mem);
159 uptr size = ClassIdToSize(GetSizeClass(p));
160 u32 offset = mem - beg;
161 uptr n = offset / (u32)size; // 32-bit division
162 uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize;
163 return reinterpret_cast<void*>(meta);
166 NOINLINE TransferBatch *AllocateBatch(AllocatorStats *stat, AllocatorCache *c,
168 DCHECK_LT(class_id, kNumClasses);
169 SizeClassInfo *sci = GetSizeClassInfo(class_id);
170 SpinMutexLock l(&sci->mutex);
171 if (sci->free_list.empty()) {
172 if (UNLIKELY(!PopulateFreeList(stat, c, sci, class_id)))
174 DCHECK(!sci->free_list.empty());
176 TransferBatch *b = sci->free_list.front();
177 sci->free_list.pop_front();
181 NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id,
183 DCHECK_LT(class_id, kNumClasses);
184 CHECK_GT(b->Count(), 0);
185 SizeClassInfo *sci = GetSizeClassInfo(class_id);
186 SpinMutexLock l(&sci->mutex);
187 sci->free_list.push_front(b);
190 bool PointerIsMine(const void *p) {
191 uptr mem = reinterpret_cast<uptr>(p);
192 if (SANITIZER_SIGN_EXTENDED_ADDRESSES)
193 mem &= (kSpaceSize - 1);
194 if (mem < kSpaceBeg || mem >= kSpaceBeg + kSpaceSize)
196 return GetSizeClass(p) != 0;
199 uptr GetSizeClass(const void *p) {
200 return possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))];
203 void *GetBlockBegin(const void *p) {
204 CHECK(PointerIsMine(p));
205 uptr mem = reinterpret_cast<uptr>(p);
206 uptr beg = ComputeRegionBeg(mem);
207 uptr size = ClassIdToSize(GetSizeClass(p));
208 u32 offset = mem - beg;
209 u32 n = offset / (u32)size; // 32-bit division
210 uptr res = beg + (n * (u32)size);
211 return reinterpret_cast<void*>(res);
214 uptr GetActuallyAllocatedSize(void *p) {
215 CHECK(PointerIsMine(p));
216 return ClassIdToSize(GetSizeClass(p));
219 static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
221 uptr TotalMemoryUsed() {
222 // No need to lock here.
224 for (uptr i = 0; i < kNumPossibleRegions; i++)
225 if (possible_regions[i])
230 void TestOnlyUnmap() {
231 for (uptr i = 0; i < kNumPossibleRegions; i++)
232 if (possible_regions[i])
233 UnmapWithCallback((i * kRegionSize), kRegionSize);
236 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
237 // introspection API.
239 for (uptr i = 0; i < kNumClasses; i++) {
240 GetSizeClassInfo(i)->mutex.Lock();
245 for (int i = kNumClasses - 1; i >= 0; i--) {
246 GetSizeClassInfo(i)->mutex.Unlock();
250 // Iterate over all existing chunks.
251 // The allocator must be locked when calling this function.
252 void ForEachChunk(ForEachChunkCallback callback, void *arg) {
253 for (uptr region = 0; region < kNumPossibleRegions; region++)
254 if (possible_regions[region]) {
255 uptr chunk_size = ClassIdToSize(possible_regions[region]);
256 uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize);
257 uptr region_beg = region * kRegionSize;
258 for (uptr chunk = region_beg;
259 chunk < region_beg + max_chunks_in_region * chunk_size;
260 chunk += chunk_size) {
261 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
262 callback(chunk, arg);
269 static uptr AdditionalSize() { return 0; }
271 typedef SizeClassMap SizeClassMapT;
272 static const uptr kNumClasses = SizeClassMap::kNumClasses;
275 static const uptr kRegionSize = 1 << kRegionSizeLog;
276 static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize;
278 struct ALIGNED(SANITIZER_CACHE_LINE_SIZE) SizeClassInfo {
279 StaticSpinMutex mutex;
280 IntrusiveList<TransferBatch> free_list;
283 COMPILER_CHECK(sizeof(SizeClassInfo) % kCacheLineSize == 0);
285 uptr ComputeRegionId(uptr mem) const {
286 if (SANITIZER_SIGN_EXTENDED_ADDRESSES)
287 mem &= (kSpaceSize - 1);
288 const uptr res = mem >> kRegionSizeLog;
289 CHECK_LT(res, kNumPossibleRegions);
293 uptr ComputeRegionBeg(uptr mem) {
294 return mem & ~(kRegionSize - 1);
297 uptr AllocateRegion(AllocatorStats *stat, uptr class_id) {
298 DCHECK_LT(class_id, kNumClasses);
299 const uptr res = reinterpret_cast<uptr>(MmapAlignedOrDieOnFatalError(
300 kRegionSize, kRegionSize, PrimaryAllocatorName));
303 MapUnmapCallback().OnMap(res, kRegionSize);
304 stat->Add(AllocatorStatMapped, kRegionSize);
305 CHECK(IsAligned(res, kRegionSize));
306 possible_regions.set(ComputeRegionId(res), static_cast<u8>(class_id));
310 SizeClassInfo *GetSizeClassInfo(uptr class_id) {
311 DCHECK_LT(class_id, kNumClasses);
312 return &size_class_info_array[class_id];
315 bool PopulateBatches(AllocatorCache *c, SizeClassInfo *sci, uptr class_id,
316 TransferBatch **current_batch, uptr max_count,
317 uptr *pointers_array, uptr count) {
318 // If using a separate class for batches, we do not need to shuffle it.
319 if (kRandomShuffleChunks && (!kUseSeparateSizeClassForBatch ||
320 class_id != SizeClassMap::kBatchClassID))
321 RandomShuffle(pointers_array, count, &sci->rand_state);
322 TransferBatch *b = *current_batch;
323 for (uptr i = 0; i < count; i++) {
325 b = c->CreateBatch(class_id, this, (TransferBatch*)pointers_array[i]);
330 b->Add((void*)pointers_array[i]);
331 if (b->Count() == max_count) {
332 sci->free_list.push_back(b);
340 bool PopulateFreeList(AllocatorStats *stat, AllocatorCache *c,
341 SizeClassInfo *sci, uptr class_id) {
342 const uptr region = AllocateRegion(stat, class_id);
343 if (UNLIKELY(!region))
345 if (kRandomShuffleChunks)
346 if (UNLIKELY(sci->rand_state == 0))
347 // The random state is initialized from ASLR (PIE) and time.
348 sci->rand_state = reinterpret_cast<uptr>(sci) ^ NanoTime();
349 const uptr size = ClassIdToSize(class_id);
350 const uptr n_chunks = kRegionSize / (size + kMetadataSize);
351 const uptr max_count = TransferBatch::MaxCached(size);
352 DCHECK_GT(max_count, 0);
353 TransferBatch *b = nullptr;
354 constexpr uptr kShuffleArraySize = 48;
355 uptr shuffle_array[kShuffleArraySize];
357 for (uptr i = region; i < region + n_chunks * size; i += size) {
358 shuffle_array[count++] = i;
359 if (count == kShuffleArraySize) {
360 if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,
361 shuffle_array, count)))
367 if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,
368 shuffle_array, count)))
372 CHECK_GT(b->Count(), 0);
373 sci->free_list.push_back(b);
378 ByteMap possible_regions;
379 SizeClassInfo size_class_info_array[kNumClasses];