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