1//===-- 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#ifndef SCUDO_PRIMARY32_H_
10#define SCUDO_PRIMARY32_H_
11
12#include "allocator_common.h"
13#include "bytemap.h"
14#include "common.h"
15#include "list.h"
16#include "options.h"
17#include "release.h"
18#include "report.h"
19#include "size_class_allocator.h"
20#include "stats.h"
21#include "string_utils.h"
22#include "thread_annotations.h"
23
24namespace scudo {
25
26// SizeClassAllocator32 is an allocator for 32 or 64-bit address space.
27//
28// It maps Regions of 2^RegionSizeLog bytes aligned on a 2^RegionSizeLog bytes
29// boundary, and keeps a bytemap of the mappable address space to track the size
30// class they are associated with.
31//
32// Mapped regions are split into equally sized Blocks according to the size
33// class they belong to, and the associated pointers are shuffled to prevent any
34// predictable address pattern (the predictability increases with the block
35// size).
36//
37// Regions for size class 0 are special and used to hold Batches, which
38// allow to transfer arrays of pointers from the global size class freelist to
39// the thread specific freelist for said class, and back.
40//
41// Memory used by this allocator is never unmapped but can be partially
42// reclaimed if the platform allows for it.
43
44template <typename Config> class SizeClassAllocator32 {
45public:
46 typedef typename Config::CompactPtrT CompactPtrT;
47 typedef typename Config::SizeClassMap SizeClassMap;
48 static const uptr GroupSizeLog = Config::getGroupSizeLog();
49 // The bytemap can only track UINT8_MAX - 1 classes.
50 static_assert(SizeClassMap::LargestClassId <= (UINT8_MAX - 1), "");
51 // Regions should be large enough to hold the largest Block.
52 static_assert((1UL << Config::getRegionSizeLog()) >= SizeClassMap::MaxSize,
53 "");
54 typedef SizeClassAllocator32<Config> ThisT;
55 using SizeClassAllocatorT =
56 typename Conditional<Config::getEnableBlockCache(),
57 SizeClassAllocatorLocalCache<ThisT>,
58 SizeClassAllocatorNoCache<ThisT>>::type;
59 typedef Batch<ThisT> BatchT;
60 typedef BatchGroup<ThisT> BatchGroupT;
61 static const u16 MaxNumBlocksInBatch = SizeClassMap::MaxNumCachedHint;
62
63 static constexpr uptr getSizeOfBatchClass() {
64 const uptr HeaderSize = sizeof(BatchT);
65 return HeaderSize + sizeof(CompactPtrT) * MaxNumBlocksInBatch;
66 }
67
68 static_assert(sizeof(BatchGroupT) <= getSizeOfBatchClass(),
69 "BatchGroupT also uses BatchClass");
70
71 static uptr getSizeByClassId(uptr ClassId) {
72 return (ClassId == SizeClassMap::BatchClassId)
73 ? getSizeOfBatchClass()
74 : SizeClassMap::getSizeByClassId(ClassId);
75 }
76
77 static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }
78
79 void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS;
80
81 void unmapTestOnly();
82
83 // When all blocks are freed, it has to be the same size as `AllocatedUser`.
84 void verifyAllBlocksAreReleasedTestOnly();
85
86 CompactPtrT compactPtr(UNUSED uptr ClassId, uptr Ptr) const {
87 return static_cast<CompactPtrT>(Ptr);
88 }
89 void *decompactPtr(UNUSED uptr ClassId, CompactPtrT CompactPtr) const {
90 return reinterpret_cast<void *>(static_cast<uptr>(CompactPtr));
91 }
92 uptr compactPtrGroupBase(CompactPtrT CompactPtr) {
93 const uptr Mask = (static_cast<uptr>(1) << GroupSizeLog) - 1;
94 return CompactPtr & ~Mask;
95 }
96 uptr decompactGroupBase(uptr CompactPtrGroupBase) {
97 return CompactPtrGroupBase;
98 }
99 ALWAYS_INLINE bool isSmallBlock(uptr BlockSize) {
100 const uptr PageSize = getPageSizeCached();
101 return BlockSize < PageSize / 16U;
102 }
103 ALWAYS_INLINE bool isLargeBlock(uptr BlockSize) {
104 const uptr PageSize = getPageSizeCached();
105 return BlockSize > PageSize;
106 }
107
108 u16 popBlocks(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,
109 CompactPtrT *ToArray, const u16 MaxBlockCount);
110
111 // Push the array of free blocks to the designated batch group.
112 void pushBlocks(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,
113 CompactPtrT *Array, u32 Size);
114
115 void disable() NO_THREAD_SAFETY_ANALYSIS;
116 void enable() NO_THREAD_SAFETY_ANALYSIS;
117
118 template <typename F> void iterateOverBlocks(F Callback);
119
120 void getStats(ScopedString *Str);
121 void getFragmentationInfo(ScopedString *Str);
122 void getMemoryGroupFragmentationInfo(ScopedString *Str) {
123 // Each region is also a memory group because region size is the same as
124 // group size.
125 getFragmentationInfo(Str);
126 }
127
128 bool setOption(Option O, sptr Value);
129
130 uptr tryReleaseToOS(uptr ClassId, ReleaseToOS ReleaseType);
131 uptr releaseToOS(ReleaseToOS ReleaseType);
132
133 const char *getRegionInfoArrayAddress() const { return nullptr; }
134 static uptr getRegionInfoArraySize() { return 0; }
135
136 // Not supported in SizeClassAllocator32.
137 static BlockInfo findNearestBlock(UNUSED const char *RegionInfoData,
138 UNUSED uptr Ptr) {
139 return {};
140 }
141
142 AtomicOptions Options;
143
144private:
145 static const uptr NumClasses = SizeClassMap::NumClasses;
146 static const uptr RegionSize = 1UL << Config::getRegionSizeLog();
147 static const uptr NumRegions = SCUDO_MMAP_RANGE_SIZE >>
148 Config::getRegionSizeLog();
149 static const u32 MaxNumBatches = SCUDO_ANDROID ? 4U : 8U;
150 typedef FlatByteMap<NumRegions> ByteMap;
151
152 struct ReleaseToOsInfo {
153 uptr BytesInFreeListAtLastCheckpoint;
154 uptr NumReleasesAttempted;
155 uptr LastReleasedBytes;
156 u64 LastReleaseAtNs;
157 };
158
159 struct BlocksInfo {
160 SinglyLinkedList<BatchGroupT> BlockList = {};
161 uptr PoppedBlocks = 0;
162 uptr PushedBlocks = 0;
163 };
164
165 struct alignas(SCUDO_CACHE_LINE_SIZE) SizeClassInfo {
166 HybridMutex Mutex;
167 BlocksInfo FreeListInfo GUARDED_BY(Mutex);
168 uptr CurrentRegion GUARDED_BY(Mutex);
169 uptr CurrentRegionAllocated GUARDED_BY(Mutex);
170 u32 RandState;
171 uptr AllocatedUser GUARDED_BY(Mutex);
172 // Lowest & highest region index allocated for this size class, to avoid
173 // looping through the whole NumRegions.
174 uptr MinRegionIndex GUARDED_BY(Mutex);
175 uptr MaxRegionIndex GUARDED_BY(Mutex);
176 ReleaseToOsInfo ReleaseInfo GUARDED_BY(Mutex);
177 };
178 static_assert(sizeof(SizeClassInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");
179
180 uptr computeRegionId(uptr Mem) {
181 const uptr Id = Mem >> Config::getRegionSizeLog();
182 CHECK_LT(Id, NumRegions);
183 return Id;
184 }
185
186 uptr allocateRegion(SizeClassInfo *Sci, uptr ClassId) REQUIRES(Sci->Mutex);
187 uptr allocateRegionSlow();
188
189 SizeClassInfo *getSizeClassInfo(uptr ClassId) {
190 DCHECK_LT(ClassId, NumClasses);
191 return &SizeClassInfoArray[ClassId];
192 }
193
194 void pushBatchClassBlocks(SizeClassInfo *Sci, CompactPtrT *Array, u32 Size)
195 REQUIRES(Sci->Mutex);
196
197 void pushBlocksImpl(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,
198 SizeClassInfo *Sci, CompactPtrT *Array, u32 Size,
199 bool SameGroup = false) REQUIRES(Sci->Mutex);
200 u16 popBlocksImpl(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,
201 SizeClassInfo *Sci, CompactPtrT *ToArray,
202 const u16 MaxBlockCount) REQUIRES(Sci->Mutex);
203 NOINLINE bool populateFreeList(SizeClassAllocatorT *SizeClassAllocator,
204 uptr ClassId, SizeClassInfo *Sci)
205 REQUIRES(Sci->Mutex);
206
207 void getStats(ScopedString *Str, uptr ClassId, SizeClassInfo *Sci)
208 REQUIRES(Sci->Mutex);
209 void getSizeClassFragmentationInfo(SizeClassInfo *Sci, uptr ClassId,
210 ScopedString *Str) REQUIRES(Sci->Mutex);
211
212 NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
213 ReleaseToOS ReleaseType = ReleaseToOS::Normal)
214 REQUIRES(Sci->Mutex);
215 bool hasChanceToReleasePages(SizeClassInfo *Sci, uptr BlockSize,
216 uptr BytesInFreeList, ReleaseToOS ReleaseType)
217 REQUIRES(Sci->Mutex);
218 PageReleaseContext markFreeBlocks(SizeClassInfo *Sci, const uptr ClassId,
219 const uptr BlockSize, const uptr Base,
220 const uptr NumberOfRegions,
221 ReleaseToOS ReleaseType)
222 REQUIRES(Sci->Mutex);
223
224 SizeClassInfo SizeClassInfoArray[NumClasses] = {};
225 HybridMutex ByteMapMutex;
226 // Track the regions in use, 0 is unused, otherwise store ClassId + 1.
227 ByteMap PossibleRegions GUARDED_BY(ByteMapMutex) = {};
228 atomic_s32 ReleaseToOsIntervalMs = {};
229 // Unless several threads request regions simultaneously from different size
230 // classes, the stash rarely contains more than 1 entry.
231 static constexpr uptr MaxStashedRegions = 4;
232 HybridMutex RegionsStashMutex;
233 uptr NumberOfStashedRegions GUARDED_BY(RegionsStashMutex) = 0;
234 uptr RegionsStash[MaxStashedRegions] GUARDED_BY(RegionsStashMutex) = {};
235};
236
237template <typename Config>
238void SizeClassAllocator32<Config>::init(s32 ReleaseToOsInterval)
239 NO_THREAD_SAFETY_ANALYSIS {
240 if (SCUDO_FUCHSIA)
241 reportError(Message: "SizeClassAllocator32 is not supported on Fuchsia");
242
243 if (SCUDO_TRUSTY)
244 reportError(Message: "SizeClassAllocator32 is not supported on Trusty");
245
246 DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT)));
247 PossibleRegions.init();
248 u32 Seed;
249 const u64 Time = getMonotonicTimeFast();
250 if (!getRandom(Buffer: reinterpret_cast<void *>(&Seed), Length: sizeof(Seed)))
251 Seed = static_cast<u32>(Time ^
252 (reinterpret_cast<uptr>(SizeClassInfoArray) >> 6));
253 for (uptr I = 0; I < NumClasses; I++) {
254 SizeClassInfo *Sci = getSizeClassInfo(ClassId: I);
255 Sci->RandState = getRandomU32(State: &Seed);
256 // Sci->MaxRegionIndex is already initialized to 0.
257 Sci->MinRegionIndex = NumRegions;
258 Sci->ReleaseInfo.LastReleaseAtNs = Time;
259 }
260
261 // The default value in the primary config has the higher priority.
262 if (Config::getDefaultReleaseToOsIntervalMs() != INT32_MIN)
263 ReleaseToOsInterval = Config::getDefaultReleaseToOsIntervalMs();
264 setOption(O: Option::ReleaseInterval, Value: static_cast<sptr>(ReleaseToOsInterval));
265}
266
267template <typename Config> void SizeClassAllocator32<Config>::unmapTestOnly() {
268 {
269 ScopedLock L(RegionsStashMutex);
270 while (NumberOfStashedRegions > 0) {
271 unmap(Addr: reinterpret_cast<void *>(RegionsStash[--NumberOfStashedRegions]),
272 Size: RegionSize);
273 }
274 }
275
276 uptr MinRegionIndex = NumRegions, MaxRegionIndex = 0;
277 for (uptr I = 0; I < NumClasses; I++) {
278 SizeClassInfo *Sci = getSizeClassInfo(ClassId: I);
279 ScopedLock L(Sci->Mutex);
280 if (Sci->MinRegionIndex < MinRegionIndex)
281 MinRegionIndex = Sci->MinRegionIndex;
282 if (Sci->MaxRegionIndex > MaxRegionIndex)
283 MaxRegionIndex = Sci->MaxRegionIndex;
284 *Sci = {};
285 }
286
287 ScopedLock L(ByteMapMutex);
288 for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++)
289 if (PossibleRegions[I])
290 unmap(Addr: reinterpret_cast<void *>(I * RegionSize), Size: RegionSize);
291 PossibleRegions.unmapTestOnly();
292}
293
294template <typename Config>
295void SizeClassAllocator32<Config>::verifyAllBlocksAreReleasedTestOnly() {
296 // `BatchGroup` and `Batch` also use the blocks from BatchClass.
297 uptr BatchClassUsedInFreeLists = 0;
298 for (uptr I = 0; I < NumClasses; I++) {
299 // We have to count BatchClassUsedInFreeLists in other regions first.
300 if (I == SizeClassMap::BatchClassId)
301 continue;
302 SizeClassInfo *Sci = getSizeClassInfo(ClassId: I);
303 ScopedLock L1(Sci->Mutex);
304 uptr TotalBlocks = 0;
305 for (BatchGroupT &BG : Sci->FreeListInfo.BlockList) {
306 // `BG::Batches` are `Batches`. +1 for `BatchGroup`.
307 BatchClassUsedInFreeLists += BG.Batches.size() + 1;
308 for (const auto &It : BG.Batches)
309 TotalBlocks += It.getCount();
310 }
311
312 const uptr BlockSize = getSizeByClassId(ClassId: I);
313 DCHECK_EQ(TotalBlocks, Sci->AllocatedUser / BlockSize);
314 DCHECK_EQ(Sci->FreeListInfo.PushedBlocks, Sci->FreeListInfo.PoppedBlocks);
315 }
316
317 SizeClassInfo *Sci = getSizeClassInfo(ClassId: SizeClassMap::BatchClassId);
318 ScopedLock L1(Sci->Mutex);
319 uptr TotalBlocks = 0;
320 for (BatchGroupT &BG : Sci->FreeListInfo.BlockList) {
321 if (LIKELY(!BG.Batches.empty())) {
322 for (const auto &It : BG.Batches)
323 TotalBlocks += It.getCount();
324 } else {
325 // `BatchGroup` with empty freelist doesn't have `Batch` record
326 // itself.
327 ++TotalBlocks;
328 }
329 }
330
331 const uptr BlockSize = getSizeByClassId(ClassId: SizeClassMap::BatchClassId);
332 DCHECK_EQ(TotalBlocks + BatchClassUsedInFreeLists,
333 Sci->AllocatedUser / BlockSize);
334 const uptr BlocksInUse =
335 Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks;
336 DCHECK_EQ(BlocksInUse, BatchClassUsedInFreeLists);
337}
338
339template <typename Config>
340u16 SizeClassAllocator32<Config>::popBlocks(
341 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, CompactPtrT *ToArray,
342 const u16 MaxBlockCount) {
343 DCHECK_LT(ClassId, NumClasses);
344 SizeClassInfo *Sci = getSizeClassInfo(ClassId);
345 ScopedLock L(Sci->Mutex);
346
347 u16 PopCount =
348 popBlocksImpl(SizeClassAllocator, ClassId, Sci, ToArray, MaxBlockCount);
349 if (UNLIKELY(PopCount == 0)) {
350 if (UNLIKELY(!populateFreeList(SizeClassAllocator, ClassId, Sci)))
351 return 0U;
352 PopCount =
353 popBlocksImpl(SizeClassAllocator, ClassId, Sci, ToArray, MaxBlockCount);
354 DCHECK_NE(PopCount, 0U);
355 }
356
357 return PopCount;
358}
359
360template <typename Config>
361void SizeClassAllocator32<Config>::pushBlocks(
362 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, CompactPtrT *Array,
363 u32 Size) {
364 DCHECK_LT(ClassId, NumClasses);
365 DCHECK_GT(Size, 0);
366
367 SizeClassInfo *Sci = getSizeClassInfo(ClassId);
368 if (ClassId == SizeClassMap::BatchClassId) {
369 ScopedLock L(Sci->Mutex);
370 pushBatchClassBlocks(Sci, Array, Size);
371 return;
372 }
373
374 // TODO(chiahungduan): Consider not doing grouping if the group size is not
375 // greater than the block size with a certain scale.
376
377 // Sort the blocks so that blocks belonging to the same group can be pushed
378 // together.
379 bool SameGroup = true;
380 for (u32 I = 1; I < Size; ++I) {
381 if (compactPtrGroupBase(CompactPtr: Array[I - 1]) != compactPtrGroupBase(CompactPtr: Array[I]))
382 SameGroup = false;
383 CompactPtrT Cur = Array[I];
384 u32 J = I;
385 while (J > 0 &&
386 compactPtrGroupBase(CompactPtr: Cur) < compactPtrGroupBase(CompactPtr: Array[J - 1])) {
387 Array[J] = Array[J - 1];
388 --J;
389 }
390 Array[J] = Cur;
391 }
392
393 ScopedLock L(Sci->Mutex);
394 pushBlocksImpl(SizeClassAllocator, ClassId, Sci, Array, Size, SameGroup);
395}
396
397template <typename Config>
398void SizeClassAllocator32<Config>::disable() NO_THREAD_SAFETY_ANALYSIS {
399 // The BatchClassId must be locked last since other classes can use it.
400 for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {
401 if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)
402 continue;
403 getSizeClassInfo(ClassId: static_cast<uptr>(I))->Mutex.lock();
404 }
405 getSizeClassInfo(ClassId: SizeClassMap::BatchClassId)->Mutex.lock();
406 RegionsStashMutex.lock();
407 ByteMapMutex.lock();
408}
409
410template <typename Config>
411void SizeClassAllocator32<Config>::enable() NO_THREAD_SAFETY_ANALYSIS {
412 ByteMapMutex.unlock();
413 RegionsStashMutex.unlock();
414 getSizeClassInfo(ClassId: SizeClassMap::BatchClassId)->Mutex.unlock();
415 for (uptr I = 0; I < NumClasses; I++) {
416 if (I == SizeClassMap::BatchClassId)
417 continue;
418 getSizeClassInfo(ClassId: I)->Mutex.unlock();
419 }
420}
421
422template <typename Config>
423template <typename F>
424void SizeClassAllocator32<Config>::iterateOverBlocks(F Callback) {
425 uptr MinRegionIndex = NumRegions, MaxRegionIndex = 0;
426 for (uptr I = 0; I < NumClasses; I++) {
427 SizeClassInfo *Sci = getSizeClassInfo(ClassId: I);
428 // TODO: The call of `iterateOverBlocks` requires disabling
429 // SizeClassAllocator32. We may consider locking each region on demand
430 // only.
431 Sci->Mutex.assertHeld();
432 if (Sci->MinRegionIndex < MinRegionIndex)
433 MinRegionIndex = Sci->MinRegionIndex;
434 if (Sci->MaxRegionIndex > MaxRegionIndex)
435 MaxRegionIndex = Sci->MaxRegionIndex;
436 }
437
438 // SizeClassAllocator32 is disabled, i.e., ByteMapMutex is held.
439 ByteMapMutex.assertHeld();
440
441 for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) {
442 if (PossibleRegions[I] &&
443 (PossibleRegions[I] - 1U) != SizeClassMap::BatchClassId) {
444 const uptr BlockSize = getSizeByClassId(ClassId: PossibleRegions[I] - 1U);
445 const uptr From = I * RegionSize;
446 const uptr To = From + (RegionSize / BlockSize) * BlockSize;
447 for (uptr Block = From; Block < To; Block += BlockSize)
448 Callback(Block);
449 }
450 }
451}
452
453template <typename Config>
454void SizeClassAllocator32<Config>::getStats(ScopedString *Str) {
455 // TODO(kostyak): get the RSS per region.
456 uptr TotalMapped = 0;
457 uptr PoppedBlocks = 0;
458 uptr PushedBlocks = 0;
459 for (uptr I = 0; I < NumClasses; I++) {
460 SizeClassInfo *Sci = getSizeClassInfo(ClassId: I);
461 ScopedLock L(Sci->Mutex);
462 TotalMapped += Sci->AllocatedUser;
463 PoppedBlocks += Sci->FreeListInfo.PoppedBlocks;
464 PushedBlocks += Sci->FreeListInfo.PushedBlocks;
465 }
466 Str->append(Format: "Stats: SizeClassAllocator32: %zuM mapped in %zu allocations; "
467 "remains %zu\n",
468 TotalMapped >> 20, PoppedBlocks, PoppedBlocks - PushedBlocks);
469 for (uptr I = 0; I < NumClasses; I++) {
470 SizeClassInfo *Sci = getSizeClassInfo(ClassId: I);
471 ScopedLock L(Sci->Mutex);
472 getStats(Str, I, Sci);
473 }
474}
475
476template <typename Config>
477void SizeClassAllocator32<Config>::getFragmentationInfo(ScopedString *Str) {
478 Str->append(
479 Format: "Fragmentation Stats: SizeClassAllocator32: page size = %zu bytes\n",
480 getPageSizeCached());
481
482 for (uptr I = 1; I < NumClasses; I++) {
483 SizeClassInfo *Sci = getSizeClassInfo(ClassId: I);
484 ScopedLock L(Sci->Mutex);
485 getSizeClassFragmentationInfo(Sci, ClassId: I, Str);
486 }
487}
488
489template <typename Config>
490bool SizeClassAllocator32<Config>::setOption(Option O, sptr Value) {
491 if (O == Option::ReleaseInterval) {
492 const s32 Interval =
493 Max(Min(static_cast<s32>(Value), Config::getMaxReleaseToOsIntervalMs()),
494 Config::getMinReleaseToOsIntervalMs());
495 atomic_store_relaxed(A: &ReleaseToOsIntervalMs, V: Interval);
496 return true;
497 }
498 // Not supported by the Primary, but not an error either.
499 return true;
500}
501
502template <typename Config>
503uptr SizeClassAllocator32<Config>::tryReleaseToOS(uptr ClassId,
504 ReleaseToOS ReleaseType) {
505 SizeClassInfo *Sci = getSizeClassInfo(ClassId);
506 // TODO: Once we have separate locks like primary64, we may consider using
507 // tryLock() as well.
508 ScopedLock L(Sci->Mutex);
509 return releaseToOSMaybe(Sci, ClassId, ReleaseType);
510}
511
512template <typename Config>
513uptr SizeClassAllocator32<Config>::releaseToOS(ReleaseToOS ReleaseType) {
514 uptr TotalReleasedBytes = 0;
515 for (uptr I = 0; I < NumClasses; I++) {
516 if (I == SizeClassMap::BatchClassId)
517 continue;
518 SizeClassInfo *Sci = getSizeClassInfo(ClassId: I);
519 ScopedLock L(Sci->Mutex);
520 TotalReleasedBytes += releaseToOSMaybe(Sci, ClassId: I, ReleaseType);
521 }
522 return TotalReleasedBytes;
523}
524
525template <typename Config>
526uptr SizeClassAllocator32<Config>::allocateRegion(SizeClassInfo *Sci,
527 uptr ClassId)
528 REQUIRES(Sci->Mutex) {
529 DCHECK_LT(ClassId, NumClasses);
530 uptr Region = 0;
531 {
532 ScopedLock L(RegionsStashMutex);
533 if (NumberOfStashedRegions > 0)
534 Region = RegionsStash[--NumberOfStashedRegions];
535 }
536 if (!Region)
537 Region = allocateRegionSlow();
538 if (LIKELY(Region)) {
539 // Sci->Mutex is held by the caller, updating the Min/Max is safe.
540 const uptr RegionIndex = computeRegionId(Mem: Region);
541 if (RegionIndex < Sci->MinRegionIndex)
542 Sci->MinRegionIndex = RegionIndex;
543 if (RegionIndex > Sci->MaxRegionIndex)
544 Sci->MaxRegionIndex = RegionIndex;
545 ScopedLock L(ByteMapMutex);
546 PossibleRegions.set(RegionIndex, static_cast<u8>(ClassId + 1U));
547 }
548 return Region;
549}
550
551template <typename Config>
552uptr SizeClassAllocator32<Config>::allocateRegionSlow() {
553 uptr MapSize = 2 * RegionSize;
554 const uptr MapBase = reinterpret_cast<uptr>(
555 map(Addr: nullptr, Size: MapSize, Name: "scudo:primary", MAP_ALLOWNOMEM));
556 if (!MapBase)
557 return 0;
558 const uptr MapEnd = MapBase + MapSize;
559 uptr Region = MapBase;
560 if (isAligned(X: Region, Alignment: RegionSize)) {
561 ScopedLock L(RegionsStashMutex);
562 if (NumberOfStashedRegions < MaxStashedRegions)
563 RegionsStash[NumberOfStashedRegions++] = MapBase + RegionSize;
564 else
565 MapSize = RegionSize;
566 } else {
567 Region = roundUp(X: MapBase, Boundary: RegionSize);
568 unmap(Addr: reinterpret_cast<void *>(MapBase), Size: Region - MapBase);
569 MapSize = RegionSize;
570 }
571 const uptr End = Region + MapSize;
572 if (End != MapEnd)
573 unmap(Addr: reinterpret_cast<void *>(End), Size: MapEnd - End);
574
575 DCHECK_EQ(Region % RegionSize, 0U);
576 static_assert(Config::getRegionSizeLog() == GroupSizeLog,
577 "Memory group should be the same size as Region");
578
579 return Region;
580}
581
582template <typename Config>
583void SizeClassAllocator32<Config>::pushBatchClassBlocks(SizeClassInfo *Sci,
584 CompactPtrT *Array,
585 u32 Size)
586 REQUIRES(Sci->Mutex) {
587 DCHECK_EQ(Sci, getSizeClassInfo(SizeClassMap::BatchClassId));
588
589 // Free blocks are recorded by Batch in freelist for all
590 // size-classes. In addition, Batch is allocated from BatchClassId.
591 // In order not to use additional block to record the free blocks in
592 // BatchClassId, they are self-contained. I.e., A Batch records the
593 // block address of itself. See the figure below:
594 //
595 // Batch at 0xABCD
596 // +----------------------------+
597 // | Free blocks' addr |
598 // | +------+------+------+ |
599 // | |0xABCD|... |... | |
600 // | +------+------+------+ |
601 // +----------------------------+
602 //
603 // When we allocate all the free blocks in the Batch, the block used
604 // by Batch is also free for use. We don't need to recycle the
605 // Batch. Note that the correctness is maintained by the invariant,
606 //
607 // Each popBlocks() request returns the entire Batch. Returning
608 // part of the blocks in a Batch is invalid.
609 //
610 // This ensures that Batch won't leak the address itself while it's
611 // still holding other valid data.
612 //
613 // Besides, BatchGroup is also allocated from BatchClassId and has its
614 // address recorded in the Batch too. To maintain the correctness,
615 //
616 // The address of BatchGroup is always recorded in the last Batch
617 // in the freelist (also imply that the freelist should only be
618 // updated with push_front). Once the last Batch is popped,
619 // the block used by BatchGroup is also free for use.
620 //
621 // With this approach, the blocks used by BatchGroup and Batch are
622 // reusable and don't need additional space for them.
623
624 Sci->FreeListInfo.PushedBlocks += Size;
625 BatchGroupT *BG = Sci->FreeListInfo.BlockList.front();
626
627 if (BG == nullptr) {
628 // Construct `BatchGroup` on the last element.
629 BG = reinterpret_cast<BatchGroupT *>(
630 decompactPtr(ClassId: SizeClassMap::BatchClassId, CompactPtr: Array[Size - 1]));
631 --Size;
632 BG->Batches.clear();
633 // BatchClass hasn't enabled memory group. Use `0` to indicate there's no
634 // memory group here.
635 BG->CompactPtrGroupBase = 0;
636 BG->BytesInBGAtLastCheckpoint = 0;
637 BG->MaxCachedPerBatch = SizeClassAllocatorT::getMaxCached(
638 getSizeByClassId(ClassId: SizeClassMap::BatchClassId));
639
640 Sci->FreeListInfo.BlockList.push_front(BG);
641 }
642
643 if (UNLIKELY(Size == 0))
644 return;
645
646 // This happens under 2 cases.
647 // 1. just allocated a new `BatchGroup`.
648 // 2. Only 1 block is pushed when the freelist is empty.
649 if (BG->Batches.empty()) {
650 // Construct the `Batch` on the last element.
651 BatchT *TB = reinterpret_cast<BatchT *>(
652 decompactPtr(ClassId: SizeClassMap::BatchClassId, CompactPtr: Array[Size - 1]));
653 TB->clear();
654 // As mentioned above, addresses of `Batch` and `BatchGroup` are
655 // recorded in the Batch.
656 TB->add(Array[Size - 1]);
657 TB->add(compactPtr(ClassId: SizeClassMap::BatchClassId, Ptr: reinterpret_cast<uptr>(BG)));
658 --Size;
659 BG->Batches.push_front(TB);
660 }
661
662 BatchT *CurBatch = BG->Batches.front();
663 DCHECK_NE(CurBatch, nullptr);
664
665 for (u32 I = 0; I < Size;) {
666 u16 UnusedSlots =
667 static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount());
668 if (UnusedSlots == 0) {
669 CurBatch = reinterpret_cast<BatchT *>(
670 decompactPtr(ClassId: SizeClassMap::BatchClassId, CompactPtr: Array[I]));
671 CurBatch->clear();
672 // Self-contained
673 CurBatch->add(Array[I]);
674 ++I;
675 // TODO(chiahungduan): Avoid the use of push_back() in `Batches` of
676 // BatchClassId.
677 BG->Batches.push_front(CurBatch);
678 UnusedSlots = static_cast<u16>(BG->MaxCachedPerBatch - 1);
679 }
680 // `UnusedSlots` is u16 so the result will be also fit in u16.
681 const u16 AppendSize = static_cast<u16>(Min<u32>(A: UnusedSlots, B: Size - I));
682 CurBatch->appendFromArray(&Array[I], AppendSize);
683 I += AppendSize;
684 }
685}
686
687// Push the blocks to their batch group. The layout will be like,
688//
689// FreeListInfo.BlockList - > BG -> BG -> BG
690// | | |
691// v v v
692// TB TB TB
693// |
694// v
695// TB
696//
697// Each BlockGroup(BG) will associate with unique group id and the free blocks
698// are managed by a list of Batch(TB). To reduce the time of inserting blocks,
699// BGs are sorted and the input `Array` are supposed to be sorted so that we can
700// get better performance of maintaining sorted property. Use `SameGroup=true`
701// to indicate that all blocks in the array are from the same group then we will
702// skip checking the group id of each block.
703//
704// The region mutex needs to be held while calling this method.
705template <typename Config>
706void SizeClassAllocator32<Config>::pushBlocksImpl(
707 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, SizeClassInfo *Sci,
708 CompactPtrT *Array, u32 Size, bool SameGroup) REQUIRES(Sci->Mutex) {
709 DCHECK_NE(ClassId, SizeClassMap::BatchClassId);
710 DCHECK_GT(Size, 0U);
711
712 auto CreateGroup = [&](uptr CompactPtrGroupBase) {
713 BatchGroupT *BG = reinterpret_cast<BatchGroupT *>(
714 SizeClassAllocator->getBatchClassBlock());
715 BG->Batches.clear();
716 BatchT *TB =
717 reinterpret_cast<BatchT *>(SizeClassAllocator->getBatchClassBlock());
718 TB->clear();
719
720 BG->CompactPtrGroupBase = CompactPtrGroupBase;
721 BG->Batches.push_front(TB);
722 BG->BytesInBGAtLastCheckpoint = 0;
723 BG->MaxCachedPerBatch = MaxNumBlocksInBatch;
724
725 return BG;
726 };
727
728 auto InsertBlocks = [&](BatchGroupT *BG, CompactPtrT *Array, u32 Size) {
729 SinglyLinkedList<BatchT> &Batches = BG->Batches;
730 BatchT *CurBatch = Batches.front();
731 DCHECK_NE(CurBatch, nullptr);
732
733 for (u32 I = 0; I < Size;) {
734 DCHECK_GE(BG->MaxCachedPerBatch, CurBatch->getCount());
735 u16 UnusedSlots =
736 static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount());
737 if (UnusedSlots == 0) {
738 CurBatch = reinterpret_cast<BatchT *>(
739 SizeClassAllocator->getBatchClassBlock());
740 CurBatch->clear();
741 Batches.push_front(CurBatch);
742 UnusedSlots = BG->MaxCachedPerBatch;
743 }
744 // `UnusedSlots` is u16 so the result will be also fit in u16.
745 u16 AppendSize = static_cast<u16>(Min<u32>(A: UnusedSlots, B: Size - I));
746 CurBatch->appendFromArray(&Array[I], AppendSize);
747 I += AppendSize;
748 }
749 };
750
751 Sci->FreeListInfo.PushedBlocks += Size;
752 BatchGroupT *Cur = Sci->FreeListInfo.BlockList.front();
753
754 // In the following, `Cur` always points to the BatchGroup for blocks that
755 // will be pushed next. `Prev` is the element right before `Cur`.
756 BatchGroupT *Prev = nullptr;
757
758 while (Cur != nullptr &&
759 compactPtrGroupBase(CompactPtr: Array[0]) > Cur->CompactPtrGroupBase) {
760 Prev = Cur;
761 Cur = Cur->Next;
762 }
763
764 if (Cur == nullptr ||
765 compactPtrGroupBase(CompactPtr: Array[0]) != Cur->CompactPtrGroupBase) {
766 Cur = CreateGroup(compactPtrGroupBase(CompactPtr: Array[0]));
767 if (Prev == nullptr)
768 Sci->FreeListInfo.BlockList.push_front(Cur);
769 else
770 Sci->FreeListInfo.BlockList.insert(Prev, Cur);
771 }
772
773 // All the blocks are from the same group, just push without checking group
774 // id.
775 if (SameGroup) {
776 for (u32 I = 0; I < Size; ++I)
777 DCHECK_EQ(compactPtrGroupBase(Array[I]), Cur->CompactPtrGroupBase);
778
779 InsertBlocks(Cur, Array, Size);
780 return;
781 }
782
783 // The blocks are sorted by group id. Determine the segment of group and
784 // push them to their group together.
785 u32 Count = 1;
786 for (u32 I = 1; I < Size; ++I) {
787 if (compactPtrGroupBase(CompactPtr: Array[I - 1]) != compactPtrGroupBase(CompactPtr: Array[I])) {
788 DCHECK_EQ(compactPtrGroupBase(Array[I - 1]), Cur->CompactPtrGroupBase);
789 InsertBlocks(Cur, Array + I - Count, Count);
790
791 while (Cur != nullptr &&
792 compactPtrGroupBase(CompactPtr: Array[I]) > Cur->CompactPtrGroupBase) {
793 Prev = Cur;
794 Cur = Cur->Next;
795 }
796
797 if (Cur == nullptr ||
798 compactPtrGroupBase(CompactPtr: Array[I]) != Cur->CompactPtrGroupBase) {
799 Cur = CreateGroup(compactPtrGroupBase(CompactPtr: Array[I]));
800 DCHECK_NE(Prev, nullptr);
801 Sci->FreeListInfo.BlockList.insert(Prev, Cur);
802 }
803
804 Count = 1;
805 } else {
806 ++Count;
807 }
808 }
809
810 InsertBlocks(Cur, Array + Size - Count, Count);
811}
812
813template <typename Config>
814u16 SizeClassAllocator32<Config>::popBlocksImpl(
815 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, SizeClassInfo *Sci,
816 CompactPtrT *ToArray, const u16 MaxBlockCount) REQUIRES(Sci->Mutex) {
817 if (Sci->FreeListInfo.BlockList.empty())
818 return 0U;
819
820 SinglyLinkedList<BatchT> &Batches =
821 Sci->FreeListInfo.BlockList.front()->Batches;
822
823 if (Batches.empty()) {
824 DCHECK_EQ(ClassId, SizeClassMap::BatchClassId);
825 BatchGroupT *BG = Sci->FreeListInfo.BlockList.front();
826 Sci->FreeListInfo.BlockList.pop_front();
827
828 // Block used by `BatchGroup` is from BatchClassId. Turn the block into
829 // `Batch` with single block.
830 BatchT *TB = reinterpret_cast<BatchT *>(BG);
831 ToArray[0] =
832 compactPtr(ClassId: SizeClassMap::BatchClassId, Ptr: reinterpret_cast<uptr>(TB));
833 Sci->FreeListInfo.PoppedBlocks += 1;
834 return 1U;
835 }
836
837 // So far, instead of always filling the blocks to `MaxBlockCount`, we only
838 // examine single `Batch` to minimize the time spent on the primary
839 // allocator. Besides, the sizes of `Batch` and
840 // `SizeClassAllocatorT::getMaxCached()` may also impact the time spent on
841 // accessing the primary allocator.
842 // TODO(chiahungduan): Evaluate if we want to always prepare `MaxBlockCount`
843 // blocks and/or adjust the size of `Batch` according to
844 // `SizeClassAllocatorT::getMaxCached()`.
845 BatchT *B = Batches.front();
846 DCHECK_NE(B, nullptr);
847 DCHECK_GT(B->getCount(), 0U);
848
849 // BachClassId should always take all blocks in the Batch. Read the
850 // comment in `pushBatchClassBlocks()` for more details.
851 const u16 PopCount = ClassId == SizeClassMap::BatchClassId
852 ? B->getCount()
853 : Min(MaxBlockCount, B->getCount());
854 B->moveNToArray(ToArray, PopCount);
855
856 // TODO(chiahungduan): The deallocation of unused BatchClassId blocks can be
857 // done without holding `Mutex`.
858 if (B->empty()) {
859 Batches.pop_front();
860 // `Batch` of BatchClassId is self-contained, no need to
861 // deallocate. Read the comment in `pushBatchClassBlocks()` for more
862 // details.
863 if (ClassId != SizeClassMap::BatchClassId)
864 SizeClassAllocator->deallocate(SizeClassMap::BatchClassId, B);
865
866 if (Batches.empty()) {
867 BatchGroupT *BG = Sci->FreeListInfo.BlockList.front();
868 Sci->FreeListInfo.BlockList.pop_front();
869
870 // We don't keep BatchGroup with zero blocks to avoid empty-checking
871 // while allocating. Note that block used for constructing BatchGroup is
872 // recorded as free blocks in the last element of BatchGroup::Batches.
873 // Which means, once we pop the last Batch, the block is
874 // implicitly deallocated.
875 if (ClassId != SizeClassMap::BatchClassId)
876 SizeClassAllocator->deallocate(SizeClassMap::BatchClassId, BG);
877 }
878 }
879
880 Sci->FreeListInfo.PoppedBlocks += PopCount;
881 return PopCount;
882}
883
884template <typename Config>
885bool SizeClassAllocator32<Config>::populateFreeList(
886 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, SizeClassInfo *Sci)
887 REQUIRES(Sci->Mutex) {
888 uptr Region;
889 uptr Offset;
890 // If the size-class currently has a region associated to it, use it. The
891 // newly created blocks will be located after the currently allocated memory
892 // for that region (up to RegionSize). Otherwise, create a new region, where
893 // the new blocks will be carved from the beginning.
894 if (Sci->CurrentRegion) {
895 Region = Sci->CurrentRegion;
896 DCHECK_GT(Sci->CurrentRegionAllocated, 0U);
897 Offset = Sci->CurrentRegionAllocated;
898 } else {
899 DCHECK_EQ(Sci->CurrentRegionAllocated, 0U);
900 Region = allocateRegion(Sci, ClassId);
901 if (UNLIKELY(!Region))
902 return false;
903 SizeClassAllocator->getStats().add(StatMapped, RegionSize);
904 Sci->CurrentRegion = Region;
905 Offset = 0;
906 }
907
908 const uptr Size = getSizeByClassId(ClassId);
909 const u16 MaxCount = SizeClassAllocatorT::getMaxCached(Size);
910 DCHECK_GT(MaxCount, 0U);
911 // The maximum number of blocks we should carve in the region is dictated
912 // by the maximum number of batches we want to fill, and the amount of
913 // memory left in the current region (we use the lowest of the two). This
914 // will not be 0 as we ensure that a region can at least hold one block (via
915 // static_assert and at the end of this function).
916 const u32 NumberOfBlocks = Min(
917 A: MaxNumBatches * MaxCount, B: static_cast<u32>((RegionSize - Offset) / Size));
918 DCHECK_GT(NumberOfBlocks, 0U);
919
920 constexpr u32 ShuffleArraySize = MaxNumBatches * MaxNumBlocksInBatch;
921 // Fill the transfer batches and put them in the size-class freelist. We
922 // need to randomize the blocks for security purposes, so we first fill a
923 // local array that we then shuffle before populating the batches.
924 CompactPtrT ShuffleArray[ShuffleArraySize];
925 DCHECK_LE(NumberOfBlocks, ShuffleArraySize);
926
927 uptr P = Region + Offset;
928 for (u32 I = 0; I < NumberOfBlocks; I++, P += Size)
929 ShuffleArray[I] = reinterpret_cast<CompactPtrT>(P);
930
931 if (ClassId != SizeClassMap::BatchClassId) {
932 u32 N = 1;
933 uptr CurGroup = compactPtrGroupBase(CompactPtr: ShuffleArray[0]);
934 for (u32 I = 1; I < NumberOfBlocks; I++) {
935 if (UNLIKELY(compactPtrGroupBase(ShuffleArray[I]) != CurGroup)) {
936 shuffle(ShuffleArray + I - N, N, &Sci->RandState);
937 pushBlocksImpl(SizeClassAllocator, ClassId, Sci, Array: ShuffleArray + I - N,
938 Size: N,
939 /*SameGroup=*/SameGroup: true);
940 N = 1;
941 CurGroup = compactPtrGroupBase(CompactPtr: ShuffleArray[I]);
942 } else {
943 ++N;
944 }
945 }
946
947 shuffle(ShuffleArray + NumberOfBlocks - N, N, &Sci->RandState);
948 pushBlocksImpl(SizeClassAllocator, ClassId, Sci,
949 Array: &ShuffleArray[NumberOfBlocks - N], Size: N,
950 /*SameGroup=*/SameGroup: true);
951 } else {
952 pushBatchClassBlocks(Sci, Array: ShuffleArray, Size: NumberOfBlocks);
953 }
954
955 // Note that `pushedBlocks` and `poppedBlocks` are supposed to only record
956 // the requests from `pushBlocks` and `PopBatch` which are external
957 // interfaces. `populateFreeList` is the internal interface so we should set
958 // the values back to avoid incorrectly setting the stats.
959 Sci->FreeListInfo.PushedBlocks -= NumberOfBlocks;
960
961 const uptr AllocatedUser = Size * NumberOfBlocks;
962 SizeClassAllocator->getStats().add(StatFree, AllocatedUser);
963 DCHECK_LE(Sci->CurrentRegionAllocated + AllocatedUser, RegionSize);
964 // If there is not enough room in the region currently associated to fit
965 // more blocks, we deassociate the region by resetting CurrentRegion and
966 // CurrentRegionAllocated. Otherwise, update the allocated amount.
967 if (RegionSize - (Sci->CurrentRegionAllocated + AllocatedUser) < Size) {
968 Sci->CurrentRegion = 0;
969 Sci->CurrentRegionAllocated = 0;
970 } else {
971 Sci->CurrentRegionAllocated += AllocatedUser;
972 }
973 Sci->AllocatedUser += AllocatedUser;
974
975 return true;
976}
977
978template <typename Config>
979void SizeClassAllocator32<Config>::getStats(ScopedString *Str, uptr ClassId,
980 SizeClassInfo *Sci)
981 REQUIRES(Sci->Mutex) {
982 if (Sci->AllocatedUser == 0)
983 return;
984 const uptr BlockSize = getSizeByClassId(ClassId);
985 const uptr InUse =
986 Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks;
987 const uptr BytesInFreeList = Sci->AllocatedUser - InUse * BlockSize;
988 uptr PushedBytesDelta = 0;
989 if (BytesInFreeList >= Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint) {
990 PushedBytesDelta =
991 BytesInFreeList - Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint;
992 }
993 const uptr AvailableChunks = Sci->AllocatedUser / BlockSize;
994 Str->append(
995 Format: " %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
996 "inuse: %6zu avail: %6zu releases attempted: %6zu last released: %6zuK "
997 "latest pushed bytes: %6zuK\n",
998 ClassId, getSizeByClassId(ClassId), Sci->AllocatedUser >> 10,
999 Sci->FreeListInfo.PoppedBlocks, Sci->FreeListInfo.PushedBlocks, InUse,
1000 AvailableChunks, Sci->ReleaseInfo.NumReleasesAttempted,
1001 Sci->ReleaseInfo.LastReleasedBytes >> 10, PushedBytesDelta >> 10);
1002}
1003
1004template <typename Config>
1005void SizeClassAllocator32<Config>::getSizeClassFragmentationInfo(
1006 SizeClassInfo *Sci, uptr ClassId, ScopedString *Str) REQUIRES(Sci->Mutex) {
1007 const uptr BlockSize = getSizeByClassId(ClassId);
1008 const uptr First = Sci->MinRegionIndex;
1009 const uptr Last = Sci->MaxRegionIndex;
1010 const uptr Base = First * RegionSize;
1011 const uptr NumberOfRegions = Last - First + 1U;
1012 auto SkipRegion = [this, First, ClassId](uptr RegionIndex) {
1013 ScopedLock L(ByteMapMutex);
1014 return (PossibleRegions[First + RegionIndex] - 1U) != ClassId;
1015 };
1016
1017 FragmentationRecorder Recorder;
1018 if (!Sci->FreeListInfo.BlockList.empty()) {
1019 PageReleaseContext Context = markFreeBlocks(
1020 Sci, ClassId, BlockSize, Base, NumberOfRegions, ReleaseType: ReleaseToOS::ForceAll);
1021 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
1022 }
1023
1024 const uptr PageSize = getPageSizeCached();
1025 const uptr TotalBlocks = Sci->AllocatedUser / BlockSize;
1026 const uptr InUseBlocks =
1027 Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks;
1028 uptr AllocatedPagesCount = 0;
1029 if (TotalBlocks != 0U) {
1030 for (uptr I = 0; I < NumberOfRegions; ++I) {
1031 if (SkipRegion(I))
1032 continue;
1033 AllocatedPagesCount += RegionSize / PageSize;
1034 }
1035
1036 DCHECK_NE(AllocatedPagesCount, 0U);
1037 }
1038
1039 DCHECK_GE(AllocatedPagesCount, Recorder.getReleasedPagesCount());
1040 const uptr InUsePages =
1041 AllocatedPagesCount - Recorder.getReleasedPagesCount();
1042 const uptr InUseBytes = InUsePages * PageSize;
1043
1044 uptr Integral;
1045 uptr Fractional;
1046 computePercentage(Numerator: BlockSize * InUseBlocks, Denominator: InUseBytes, Integral: &Integral,
1047 Fractional: &Fractional);
1048 Str->append(Format: " %02zu (%6zu): inuse/total blocks: %6zu/%6zu inuse/total "
1049 "pages: %6zu/%6zu inuse bytes: %6zuK util: %3zu.%02zu%%\n",
1050 ClassId, BlockSize, InUseBlocks, TotalBlocks, InUsePages,
1051 AllocatedPagesCount, InUseBytes >> 10, Integral, Fractional);
1052}
1053
1054template <typename Config>
1055uptr SizeClassAllocator32<Config>::releaseToOSMaybe(SizeClassInfo *Sci,
1056 uptr ClassId,
1057 ReleaseToOS ReleaseType)
1058 REQUIRES(Sci->Mutex) {
1059 const uptr BlockSize = getSizeByClassId(ClassId);
1060
1061 DCHECK_GE(Sci->FreeListInfo.PoppedBlocks, Sci->FreeListInfo.PushedBlocks);
1062 const uptr BytesInFreeList =
1063 Sci->AllocatedUser -
1064 (Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks) *
1065 BlockSize;
1066
1067 if (UNLIKELY(BytesInFreeList == 0))
1068 return 0;
1069
1070 // ====================================================================== //
1071 // 1. Check if we have enough free blocks and if it's worth doing a page
1072 // release.
1073 // ====================================================================== //
1074 if (ReleaseType != ReleaseToOS::ForceAll &&
1075 !hasChanceToReleasePages(Sci, BlockSize, BytesInFreeList, ReleaseType)) {
1076 return 0;
1077 }
1078
1079 const uptr First = Sci->MinRegionIndex;
1080 const uptr Last = Sci->MaxRegionIndex;
1081 DCHECK_NE(Last, 0U);
1082 DCHECK_LE(First, Last);
1083 uptr TotalReleasedBytes = 0;
1084 const uptr Base = First * RegionSize;
1085 const uptr NumberOfRegions = Last - First + 1U;
1086
1087 // The following steps contribute to the majority time spent in page
1088 // releasing thus we increment the counter here.
1089 ++Sci->ReleaseInfo.NumReleasesAttempted;
1090
1091 // ==================================================================== //
1092 // 2. Mark the free blocks and we can tell which pages are in-use by
1093 // querying `PageReleaseContext`.
1094 // ==================================================================== //
1095 PageReleaseContext Context = markFreeBlocks(Sci, ClassId, BlockSize, Base,
1096 NumberOfRegions, ReleaseType);
1097 if (!Context.hasBlockMarked())
1098 return 0;
1099
1100 // ==================================================================== //
1101 // 3. Release the unused physical pages back to the OS.
1102 // ==================================================================== //
1103 ReleaseRecorder Recorder(Base);
1104 auto SkipRegion = [this, First, ClassId](uptr RegionIndex) {
1105 ScopedLock L(ByteMapMutex);
1106 return (PossibleRegions[First + RegionIndex] - 1U) != ClassId;
1107 };
1108 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
1109
1110 if (Recorder.getReleasedBytes() > 0) {
1111 Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;
1112 Sci->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
1113 TotalReleasedBytes += Sci->ReleaseInfo.LastReleasedBytes;
1114 }
1115 Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTimeFast();
1116
1117 return TotalReleasedBytes;
1118}
1119
1120template <typename Config>
1121bool SizeClassAllocator32<Config>::hasChanceToReleasePages(
1122 SizeClassInfo *Sci, uptr BlockSize, uptr BytesInFreeList,
1123 ReleaseToOS ReleaseType) REQUIRES(Sci->Mutex) {
1124 DCHECK_GE(Sci->FreeListInfo.PoppedBlocks, Sci->FreeListInfo.PushedBlocks);
1125 const uptr PageSize = getPageSizeCached();
1126
1127 if (BytesInFreeList <= Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint)
1128 Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;
1129
1130 // Always update `BytesInFreeListAtLastCheckpoint` with the smallest value
1131 // so that we won't underestimate the releasable pages. For example, the
1132 // following is the region usage,
1133 //
1134 // BytesInFreeListAtLastCheckpoint AllocatedUser
1135 // v v
1136 // |--------------------------------------->
1137 // ^ ^
1138 // BytesInFreeList ReleaseThreshold
1139 //
1140 // In general, if we have collected enough bytes and the amount of free
1141 // bytes meets the ReleaseThreshold, we will try to do page release. If we
1142 // don't update `BytesInFreeListAtLastCheckpoint` when the current
1143 // `BytesInFreeList` is smaller, we may take longer time to wait for enough
1144 // freed blocks because we miss the bytes between
1145 // (BytesInFreeListAtLastCheckpoint - BytesInFreeList).
1146 const uptr PushedBytesDelta =
1147 BytesInFreeList - Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint;
1148 if (PushedBytesDelta < PageSize)
1149 return false;
1150
1151 // Releasing smaller blocks is expensive, so we want to make sure that a
1152 // significant amount of bytes are free, and that there has been a good
1153 // amount of batches pushed to the freelist before attempting to release.
1154 if (isSmallBlock(BlockSize) && ReleaseType == ReleaseToOS::Normal)
1155 if (PushedBytesDelta < Sci->AllocatedUser / 16U)
1156 return false;
1157
1158 if (ReleaseType == ReleaseToOS::Normal) {
1159 const s32 IntervalMs = atomic_load_relaxed(A: &ReleaseToOsIntervalMs);
1160 if (IntervalMs < 0)
1161 return false;
1162
1163 // The constant 8 here is selected from profiling some apps and the number
1164 // of unreleased pages in the large size classes is around 16 pages or
1165 // more. Choose half of it as a heuristic and which also avoids page
1166 // release every time for every pushBlocks() attempt by large blocks.
1167 const bool ByPassReleaseInterval =
1168 isLargeBlock(BlockSize) && PushedBytesDelta > 8 * PageSize;
1169 if (!ByPassReleaseInterval) {
1170 if (Sci->ReleaseInfo.LastReleaseAtNs +
1171 static_cast<u64>(IntervalMs) * 1000000 >
1172 getMonotonicTimeFast()) {
1173 // Memory was returned recently.
1174 return false;
1175 }
1176 }
1177 } // if (ReleaseType == ReleaseToOS::Normal)
1178
1179 return true;
1180}
1181
1182template <typename Config>
1183PageReleaseContext SizeClassAllocator32<Config>::markFreeBlocks(
1184 SizeClassInfo *Sci, const uptr ClassId, const uptr BlockSize,
1185 const uptr Base, const uptr NumberOfRegions, ReleaseToOS ReleaseType)
1186 REQUIRES(Sci->Mutex) {
1187 const uptr PageSize = getPageSizeCached();
1188 const uptr GroupSize = (1UL << GroupSizeLog);
1189 const uptr CurGroupBase =
1190 compactPtrGroupBase(CompactPtr: compactPtr(ClassId, Ptr: Sci->CurrentRegion));
1191
1192 PageReleaseContext Context(BlockSize, NumberOfRegions,
1193 /*ReleaseSize=*/RegionSize);
1194
1195 auto DecompactPtr = [](CompactPtrT CompactPtr) {
1196 return reinterpret_cast<uptr>(CompactPtr);
1197 };
1198 for (BatchGroupT &BG : Sci->FreeListInfo.BlockList) {
1199 const uptr GroupBase = decompactGroupBase(CompactPtrGroupBase: BG.CompactPtrGroupBase);
1200 // The `GroupSize` may not be divided by `BlockSize`, which means there is
1201 // an unused space at the end of Region. Exclude that space to avoid
1202 // unused page map entry.
1203 uptr AllocatedGroupSize = GroupBase == CurGroupBase
1204 ? Sci->CurrentRegionAllocated
1205 : roundDownSlow(X: GroupSize, Boundary: BlockSize);
1206 if (AllocatedGroupSize == 0)
1207 continue;
1208
1209 // Batches are pushed in front of BG.Batches. The first one may
1210 // not have all caches used.
1211 const uptr NumBlocks = (BG.Batches.size() - 1) * BG.MaxCachedPerBatch +
1212 BG.Batches.front()->getCount();
1213 const uptr BytesInBG = NumBlocks * BlockSize;
1214
1215 if (ReleaseType != ReleaseToOS::ForceAll) {
1216 if (BytesInBG <= BG.BytesInBGAtLastCheckpoint) {
1217 BG.BytesInBGAtLastCheckpoint = BytesInBG;
1218 continue;
1219 }
1220
1221 const uptr PushedBytesDelta = BytesInBG - BG.BytesInBGAtLastCheckpoint;
1222 if (PushedBytesDelta < PageSize)
1223 continue;
1224
1225 // Given the randomness property, we try to release the pages only if
1226 // the bytes used by free blocks exceed certain proportion of allocated
1227 // spaces.
1228 if (isSmallBlock(BlockSize) && (BytesInBG * 100U) / AllocatedGroupSize <
1229 (100U - 1U - BlockSize / 16U)) {
1230 continue;
1231 }
1232 }
1233
1234 // TODO: Consider updating this after page release if `ReleaseRecorder`
1235 // can tell the released bytes in each group.
1236 BG.BytesInBGAtLastCheckpoint = BytesInBG;
1237
1238 const uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize;
1239 const uptr RegionIndex = (GroupBase - Base) / RegionSize;
1240
1241 if (NumBlocks == MaxContainedBlocks) {
1242 for (const auto &It : BG.Batches)
1243 for (u16 I = 0; I < It.getCount(); ++I)
1244 DCHECK_EQ(compactPtrGroupBase(It.get(I)), BG.CompactPtrGroupBase);
1245
1246 const uptr To = GroupBase + AllocatedGroupSize;
1247 Context.markRangeAsAllCounted(From: GroupBase, To, Base: GroupBase, RegionIndex,
1248 RegionSize: AllocatedGroupSize);
1249 } else {
1250 DCHECK_LT(NumBlocks, MaxContainedBlocks);
1251
1252 // Note that we don't always visit blocks in each BatchGroup so that we
1253 // may miss the chance of releasing certain pages that cross
1254 // BatchGroups.
1255 Context.markFreeBlocksInRegion(BG.Batches, DecompactPtr, GroupBase,
1256 RegionIndex, AllocatedGroupSize,
1257 /*MayContainLastBlockInRegion=*/true);
1258 }
1259
1260 // We may not be able to do the page release In a rare case that we may
1261 // fail on PageMap allocation.
1262 if (UNLIKELY(!Context.hasBlockMarked()))
1263 break;
1264 }
1265
1266 return Context;
1267}
1268
1269} // namespace scudo
1270
1271#endif // SCUDO_PRIMARY32_H_
1272

source code of compiler-rt/lib/scudo/standalone/primary32.h