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