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