1//===-- primary64.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_PRIMARY64_H_
10#define SCUDO_PRIMARY64_H_
11
12#include "allocator_common.h"
13#include "bytemap.h"
14#include "common.h"
15#include "condition_variable.h"
16#include "list.h"
17#include "mem_map.h"
18#include "memtag.h"
19#include "options.h"
20#include "release.h"
21#include "size_class_allocator.h"
22#include "stats.h"
23#include "string_utils.h"
24#include "thread_annotations.h"
25#include "tracing.h"
26
27#include <inttypes.h>
28
29namespace scudo {
30
31// SizeClassAllocator64 is an allocator tuned for 64-bit address space.
32//
33// It starts by reserving NumClasses * 2^RegionSizeLog bytes, equally divided in
34// Regions, specific to each size class. Note that the base of that mapping is
35// random (based to the platform specific map() capabilities). If
36// PrimaryEnableRandomOffset is set, each Region actually starts at a random
37// offset from its base.
38//
39// Regions are mapped incrementally on demand to fulfill allocation requests,
40// those mappings being split into equally sized Blocks based on the size class
41// they belong to. The Blocks created are shuffled to prevent predictable
42// address patterns (the predictability increases with the size of the Blocks).
43//
44// The 1st Region (for size class 0) holds the Batches. This is a
45// structure used to transfer arrays of available pointers from the class size
46// freelist to the thread specific freelist, and back.
47//
48// The memory used by this allocator is never unmapped, but can be partially
49// released if the platform allows for it.
50
51template <typename Config> class SizeClassAllocator64 {
52public:
53 typedef typename Config::CompactPtrT CompactPtrT;
54 typedef typename Config::SizeClassMap SizeClassMap;
55 typedef typename Config::ConditionVariableT ConditionVariableT;
56 static const uptr CompactPtrScale = Config::getCompactPtrScale();
57 static const uptr RegionSizeLog = Config::getRegionSizeLog();
58 static const uptr GroupSizeLog = Config::getGroupSizeLog();
59 static_assert(RegionSizeLog >= GroupSizeLog,
60 "Group size shouldn't be greater than the region size");
61 static const uptr GroupScale = GroupSizeLog - CompactPtrScale;
62 typedef SizeClassAllocator64<Config> ThisT;
63 typedef Batch<ThisT> BatchT;
64 typedef BatchGroup<ThisT> BatchGroupT;
65 using SizeClassAllocatorT =
66 typename Conditional<Config::getEnableBlockCache(),
67 SizeClassAllocatorLocalCache<ThisT>,
68 SizeClassAllocatorNoCache<ThisT>>::type;
69 static const u16 MaxNumBlocksInBatch = SizeClassMap::MaxNumCachedHint;
70
71 static constexpr uptr getSizeOfBatchClass() {
72 const uptr HeaderSize = sizeof(BatchT);
73 return roundUp(X: HeaderSize + sizeof(CompactPtrT) * MaxNumBlocksInBatch,
74 Boundary: 1 << CompactPtrScale);
75 }
76
77 static_assert(sizeof(BatchGroupT) <= getSizeOfBatchClass(),
78 "BatchGroupT also uses BatchClass");
79
80 // BachClass is used to store internal metadata so it needs to be at least as
81 // large as the largest data structure.
82 static uptr getSizeByClassId(uptr ClassId) {
83 return (ClassId == SizeClassMap::BatchClassId)
84 ? getSizeOfBatchClass()
85 : SizeClassMap::getSizeByClassId(ClassId);
86 }
87
88 static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }
89 static bool conditionVariableEnabled() {
90 return Config::hasConditionVariableT();
91 }
92 static uptr getRegionInfoArraySize() { return sizeof(RegionInfoArray); }
93 static BlockInfo findNearestBlock(const char *RegionInfoData,
94 uptr Ptr) NO_THREAD_SAFETY_ANALYSIS;
95
96 void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS;
97
98 void unmapTestOnly();
99
100 // When all blocks are freed, it has to be the same size as `AllocatedUser`.
101 void verifyAllBlocksAreReleasedTestOnly();
102
103 u16 popBlocks(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,
104 CompactPtrT *ToArray, const u16 MaxBlockCount);
105
106 // Push the array of free blocks to the designated batch group.
107 void pushBlocks(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,
108 CompactPtrT *Array, u32 Size);
109
110 void disable() NO_THREAD_SAFETY_ANALYSIS;
111 void enable() NO_THREAD_SAFETY_ANALYSIS;
112
113 template <typename F> void iterateOverBlocks(F Callback);
114
115 void getStats(ScopedString *Str);
116 void getFragmentationInfo(ScopedString *Str);
117 void getMemoryGroupFragmentationInfo(ScopedString *Str);
118
119 bool setOption(Option O, sptr Value);
120
121 // These are used for returning unused pages. Note that it doesn't unmap the
122 // pages, it only suggests that the physical pages can be released.
123 uptr tryReleaseToOS(uptr ClassId, ReleaseToOS ReleaseType);
124 uptr releaseToOS(ReleaseToOS ReleaseType);
125
126 const char *getRegionInfoArrayAddress() const {
127 return reinterpret_cast<const char *>(RegionInfoArray);
128 }
129
130 uptr getCompactPtrBaseByClassId(uptr ClassId) {
131 return getRegionInfo(ClassId)->RegionBeg;
132 }
133 CompactPtrT compactPtr(uptr ClassId, uptr Ptr) {
134 DCHECK_LE(ClassId, SizeClassMap::LargestClassId);
135 return compactPtrInternal(Base: getCompactPtrBaseByClassId(ClassId), Ptr);
136 }
137 void *decompactPtr(uptr ClassId, CompactPtrT CompactPtr) {
138 DCHECK_LE(ClassId, SizeClassMap::LargestClassId);
139 return reinterpret_cast<void *>(
140 decompactPtrInternal(Base: getCompactPtrBaseByClassId(ClassId), CompactPtr));
141 }
142
143 AtomicOptions Options;
144
145private:
146 static const uptr RegionSize = 1UL << RegionSizeLog;
147 static const uptr NumClasses = SizeClassMap::NumClasses;
148 static const uptr MapSizeIncrement = Config::getMapSizeIncrement();
149 // Fill at most this number of batches from the newly map'd memory.
150 static const u32 MaxNumBatches = SCUDO_ANDROID ? 4U : 8U;
151
152 struct ReleaseToOsInfo {
153 uptr BytesInFreeListAtLastCheckpoint;
154 uptr NumReleasesAttempted;
155 uptr LastReleasedBytes;
156 // The minimum size of pushed blocks to trigger page release.
157 uptr TryReleaseThreshold;
158 // The number of bytes not triggering `releaseToOSMaybe()` because of
159 // the length of release interval.
160 uptr PendingPushedBytesDelta;
161 u64 LastReleaseAtNs;
162 };
163
164 struct BlocksInfo {
165 SinglyLinkedList<BatchGroupT> BlockList = {};
166 uptr PoppedBlocks = 0;
167 uptr PushedBlocks = 0;
168 };
169
170 struct PagesInfo {
171 MemMapT MemMap = {};
172 // Bytes mapped for user memory.
173 uptr MappedUser = 0;
174 // Bytes allocated for user memory.
175 uptr AllocatedUser = 0;
176 };
177
178 struct UnpaddedRegionInfo {
179 // Mutex for operations on freelist
180 HybridMutex FLLock;
181 ConditionVariableT FLLockCV GUARDED_BY(FLLock);
182 // Mutex for memmap operations
183 HybridMutex MMLock ACQUIRED_BEFORE(FLLock);
184 // `RegionBeg` is initialized before thread creation and won't be changed.
185 uptr RegionBeg = 0;
186 u32 RandState GUARDED_BY(MMLock) = 0;
187 BlocksInfo FreeListInfo GUARDED_BY(FLLock);
188 PagesInfo MemMapInfo GUARDED_BY(MMLock);
189 ReleaseToOsInfo ReleaseInfo GUARDED_BY(MMLock) = {};
190 bool Exhausted GUARDED_BY(MMLock) = false;
191 bool isPopulatingFreeList GUARDED_BY(FLLock) = false;
192 };
193 struct RegionInfo : UnpaddedRegionInfo {
194 char Padding[SCUDO_CACHE_LINE_SIZE -
195 (sizeof(UnpaddedRegionInfo) % SCUDO_CACHE_LINE_SIZE)] = {};
196 };
197 static_assert(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");
198
199 RegionInfo *getRegionInfo(uptr ClassId) {
200 DCHECK_LT(ClassId, NumClasses);
201 return &RegionInfoArray[ClassId];
202 }
203
204 uptr getRegionBaseByClassId(uptr ClassId) {
205 RegionInfo *Region = getRegionInfo(ClassId);
206 Region->MMLock.assertHeld();
207
208 if (!Config::getEnableContiguousRegions() &&
209 !Region->MemMapInfo.MemMap.isAllocated()) {
210 return 0U;
211 }
212 return Region->MemMapInfo.MemMap.getBase();
213 }
214
215 CompactPtrT compactPtrInternal(uptr Base, uptr Ptr) const {
216 return static_cast<CompactPtrT>((Ptr - Base) >> CompactPtrScale);
217 }
218 uptr decompactPtrInternal(uptr Base, CompactPtrT CompactPtr) const {
219 return Base + (static_cast<uptr>(CompactPtr) << CompactPtrScale);
220 }
221 uptr compactPtrGroup(CompactPtrT CompactPtr) const {
222 const uptr Mask = (static_cast<uptr>(1) << GroupScale) - 1;
223 return static_cast<uptr>(CompactPtr) & ~Mask;
224 }
225 uptr decompactGroupBase(uptr Base, uptr CompactPtrGroupBase) const {
226 DCHECK_EQ(CompactPtrGroupBase % (static_cast<uptr>(1) << (GroupScale)), 0U);
227 return Base + (CompactPtrGroupBase << CompactPtrScale);
228 }
229 ALWAYS_INLINE bool isSmallBlock(uptr BlockSize) const {
230 const uptr PageSize = getPageSizeCached();
231 return BlockSize < PageSize / 16U;
232 }
233 ALWAYS_INLINE uptr getMinReleaseAttemptSize(uptr BlockSize) {
234 return roundUp(X: BlockSize, Boundary: getPageSizeCached());
235 }
236
237 ALWAYS_INLINE void initRegion(RegionInfo *Region, uptr ClassId,
238 MemMapT MemMap, bool EnableRandomOffset)
239 REQUIRES(Region->MMLock);
240
241 void pushBlocksImpl(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,
242 RegionInfo *Region, CompactPtrT *Array, u32 Size,
243 bool SameGroup = false) REQUIRES(Region->FLLock);
244
245 // Similar to `pushBlocksImpl` but has some logics specific to BatchClass.
246 void pushBatchClassBlocks(RegionInfo *Region, CompactPtrT *Array, u32 Size)
247 REQUIRES(Region->FLLock);
248
249 // Pop at most `MaxBlockCount` from the freelist of the given region.
250 u16 popBlocksImpl(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,
251 RegionInfo *Region, CompactPtrT *ToArray,
252 const u16 MaxBlockCount) REQUIRES(Region->FLLock);
253 // Same as `popBlocksImpl` but is used when conditional variable is enabled.
254 u16 popBlocksWithCV(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,
255 RegionInfo *Region, CompactPtrT *ToArray,
256 const u16 MaxBlockCount, bool &ReportRegionExhausted);
257
258 // When there's no blocks available in the freelist, it tries to prepare more
259 // blocks by mapping more pages.
260 NOINLINE u16 populateFreeListAndPopBlocks(
261 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, RegionInfo *Region,
262 CompactPtrT *ToArray, const u16 MaxBlockCount) REQUIRES(Region->MMLock)
263 EXCLUDES(Region->FLLock);
264
265 void getStats(ScopedString *Str, uptr ClassId, RegionInfo *Region)
266 REQUIRES(Region->MMLock, Region->FLLock);
267 void getRegionFragmentationInfo(RegionInfo *Region, uptr ClassId,
268 ScopedString *Str) REQUIRES(Region->MMLock);
269 void getMemoryGroupFragmentationInfoInRegion(RegionInfo *Region, uptr ClassId,
270 ScopedString *Str)
271 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock);
272
273 NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
274 ReleaseToOS ReleaseType = ReleaseToOS::Normal)
275 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock);
276 bool hasChanceToReleasePages(RegionInfo *Region, uptr BlockSize,
277 uptr BytesInFreeList, ReleaseToOS ReleaseType)
278 REQUIRES(Region->MMLock, Region->FLLock);
279 SinglyLinkedList<BatchGroupT>
280 collectGroupsToRelease(RegionInfo *Region, const uptr BlockSize,
281 const uptr AllocatedUserEnd, const uptr CompactPtrBase)
282 REQUIRES(Region->MMLock, Region->FLLock);
283 PageReleaseContext
284 markFreeBlocks(RegionInfo *Region, const uptr BlockSize,
285 const uptr AllocatedUserEnd, const uptr CompactPtrBase,
286 SinglyLinkedList<BatchGroupT> &GroupsToRelease)
287 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock);
288
289 void mergeGroupsToReleaseBack(RegionInfo *Region,
290 SinglyLinkedList<BatchGroupT> &GroupsToRelease)
291 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock);
292
293 // The minimum size of pushed blocks that we will try to release the pages in
294 // that size class.
295 uptr SmallerBlockReleasePageDelta = 0;
296 atomic_s32 ReleaseToOsIntervalMs = {};
297 alignas(SCUDO_CACHE_LINE_SIZE) RegionInfo RegionInfoArray[NumClasses];
298};
299
300template <typename Config>
301void SizeClassAllocator64<Config>::init(s32 ReleaseToOsInterval)
302 NO_THREAD_SAFETY_ANALYSIS {
303 DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT)));
304
305 const uptr PageSize = getPageSizeCached();
306 const uptr GroupSize = (1UL << GroupSizeLog);
307 const uptr PagesInGroup = GroupSize / PageSize;
308 const uptr MinSizeClass = getSizeByClassId(ClassId: 1);
309 // When trying to release pages back to memory, visiting smaller size
310 // classes is expensive. Therefore, we only try to release smaller size
311 // classes when the amount of free blocks goes over a certain threshold (See
312 // the comment in releaseToOSMaybe() for more details). For example, for
313 // size class 32, we only do the release when the size of free blocks is
314 // greater than 97% of pages in a group. However, this may introduce another
315 // issue that if the number of free blocks is bouncing between 97% ~ 100%.
316 // Which means we may try many page releases but only release very few of
317 // them (less than 3% in a group). Even though we have
318 // `&ReleaseToOsIntervalMs` which slightly reduce the frequency of these
319 // calls but it will be better to have another guard to mitigate this issue.
320 //
321 // Here we add another constraint on the minimum size requirement. The
322 // constraint is determined by the size of in-use blocks in the minimal size
323 // class. Take size class 32 as an example,
324 //
325 // +- one memory group -+
326 // +----------------------+------+
327 // | 97% of free blocks | |
328 // +----------------------+------+
329 // \ /
330 // 3% in-use blocks
331 //
332 // * The release size threshold is 97%.
333 //
334 // The 3% size in a group is about 7 pages. For two consecutive
335 // releaseToOSMaybe(), we require the difference between `PushedBlocks`
336 // should be greater than 7 pages. This mitigates the page releasing
337 // thrashing which is caused by memory usage bouncing around the threshold.
338 // The smallest size class takes longest time to do the page release so we
339 // use its size of in-use blocks as a heuristic.
340 SmallerBlockReleasePageDelta = PagesInGroup * (1 + MinSizeClass / 16U) / 100;
341
342 u32 Seed;
343 const u64 Time = getMonotonicTimeFast();
344 if (!getRandom(Buffer: reinterpret_cast<void *>(&Seed), Length: sizeof(Seed)))
345 Seed = static_cast<u32>(Time ^ (reinterpret_cast<uptr>(&Seed) >> 12));
346
347 for (uptr I = 0; I < NumClasses; I++)
348 getRegionInfo(ClassId: I)->RandState = getRandomU32(State: &Seed);
349
350 if (Config::getEnableContiguousRegions()) {
351 ReservedMemoryT ReservedMemory = {};
352 // Reserve the space required for the Primary.
353 CHECK(ReservedMemory.create(/*Addr=*/0U, RegionSize * NumClasses,
354 "scudo:primary_reserve"));
355 const uptr PrimaryBase = ReservedMemory.getBase();
356
357 for (uptr I = 0; I < NumClasses; I++) {
358 MemMapT RegionMemMap = ReservedMemory.dispatch(
359 Addr: PrimaryBase + (I << RegionSizeLog), Size: RegionSize);
360 RegionInfo *Region = getRegionInfo(ClassId: I);
361
362 initRegion(Region, ClassId: I, MemMap: RegionMemMap, EnableRandomOffset: Config::getEnableRandomOffset());
363 }
364 shuffle(RegionInfoArray, NumClasses, &Seed);
365 }
366
367 // The binding should be done after region shuffling so that it won't bind
368 // the FLLock from the wrong region.
369 for (uptr I = 0; I < NumClasses; I++)
370 getRegionInfo(ClassId: I)->FLLockCV.bindTestOnly(getRegionInfo(ClassId: I)->FLLock);
371
372 // The default value in the primary config has the higher priority.
373 if (Config::getDefaultReleaseToOsIntervalMs() != INT32_MIN)
374 ReleaseToOsInterval = Config::getDefaultReleaseToOsIntervalMs();
375 setOption(O: Option::ReleaseInterval, Value: static_cast<sptr>(ReleaseToOsInterval));
376}
377
378template <typename Config>
379void SizeClassAllocator64<Config>::initRegion(RegionInfo *Region, uptr ClassId,
380 MemMapT MemMap,
381 bool EnableRandomOffset)
382 REQUIRES(Region->MMLock) {
383 DCHECK(!Region->MemMapInfo.MemMap.isAllocated());
384 DCHECK(MemMap.isAllocated());
385
386 const uptr PageSize = getPageSizeCached();
387
388 Region->MemMapInfo.MemMap = MemMap;
389
390 Region->RegionBeg = MemMap.getBase();
391 if (EnableRandomOffset) {
392 Region->RegionBeg += (getRandomModN(&Region->RandState, 16) + 1) * PageSize;
393 }
394
395 const uptr BlockSize = getSizeByClassId(ClassId);
396 // Releasing small blocks is expensive, set a higher threshold to avoid
397 // frequent page releases.
398 if (isSmallBlock(BlockSize)) {
399 Region->ReleaseInfo.TryReleaseThreshold =
400 PageSize * SmallerBlockReleasePageDelta;
401 } else {
402 Region->ReleaseInfo.TryReleaseThreshold =
403 getMinReleaseAttemptSize(BlockSize);
404 }
405}
406
407template <typename Config> void SizeClassAllocator64<Config>::unmapTestOnly() {
408 for (uptr I = 0; I < NumClasses; I++) {
409 RegionInfo *Region = getRegionInfo(ClassId: I);
410 {
411 ScopedLock ML(Region->MMLock);
412 MemMapT MemMap = Region->MemMapInfo.MemMap;
413 if (MemMap.isAllocated())
414 MemMap.unmap();
415 }
416 *Region = {};
417 }
418}
419
420template <typename Config>
421void SizeClassAllocator64<Config>::verifyAllBlocksAreReleasedTestOnly() {
422 // `BatchGroup` and `Batch` also use the blocks from BatchClass.
423 uptr BatchClassUsedInFreeLists = 0;
424 for (uptr I = 0; I < NumClasses; I++) {
425 // We have to count BatchClassUsedInFreeLists in other regions first.
426 if (I == SizeClassMap::BatchClassId)
427 continue;
428 RegionInfo *Region = getRegionInfo(ClassId: I);
429 ScopedLock ML(Region->MMLock);
430 ScopedLock FL(Region->FLLock);
431 const uptr BlockSize = getSizeByClassId(ClassId: I);
432 uptr TotalBlocks = 0;
433 for (BatchGroupT &BG : Region->FreeListInfo.BlockList) {
434 // `BG::Batches` are `Batches`. +1 for `BatchGroup`.
435 BatchClassUsedInFreeLists += BG.Batches.size() + 1;
436 for (const auto &It : BG.Batches)
437 TotalBlocks += It.getCount();
438 }
439
440 DCHECK_EQ(TotalBlocks, Region->MemMapInfo.AllocatedUser / BlockSize);
441 DCHECK_EQ(Region->FreeListInfo.PushedBlocks,
442 Region->FreeListInfo.PoppedBlocks);
443 }
444
445 RegionInfo *Region = getRegionInfo(ClassId: SizeClassMap::BatchClassId);
446 ScopedLock ML(Region->MMLock);
447 ScopedLock FL(Region->FLLock);
448 const uptr BlockSize = getSizeByClassId(ClassId: SizeClassMap::BatchClassId);
449 uptr TotalBlocks = 0;
450 for (BatchGroupT &BG : Region->FreeListInfo.BlockList) {
451 if (LIKELY(!BG.Batches.empty())) {
452 for (const auto &It : BG.Batches)
453 TotalBlocks += It.getCount();
454 } else {
455 // `BatchGroup` with empty freelist doesn't have `Batch` record
456 // itself.
457 ++TotalBlocks;
458 }
459 }
460 DCHECK_EQ(TotalBlocks + BatchClassUsedInFreeLists,
461 Region->MemMapInfo.AllocatedUser / BlockSize);
462 DCHECK_GE(Region->FreeListInfo.PoppedBlocks,
463 Region->FreeListInfo.PushedBlocks);
464 const uptr BlocksInUse =
465 Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks;
466 DCHECK_EQ(BlocksInUse, BatchClassUsedInFreeLists);
467}
468
469template <typename Config>
470u16 SizeClassAllocator64<Config>::popBlocks(
471 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, CompactPtrT *ToArray,
472 const u16 MaxBlockCount) {
473 DCHECK_LT(ClassId, NumClasses);
474 RegionInfo *Region = getRegionInfo(ClassId);
475 u16 PopCount = 0;
476
477 {
478 ScopedLock L(Region->FLLock);
479 PopCount = popBlocksImpl(SizeClassAllocator, ClassId, Region, ToArray,
480 MaxBlockCount);
481 if (PopCount != 0U)
482 return PopCount;
483 }
484
485 bool ReportRegionExhausted = false;
486
487 if (conditionVariableEnabled()) {
488 PopCount = popBlocksWithCV(SizeClassAllocator, ClassId, Region, ToArray,
489 MaxBlockCount, ReportRegionExhausted);
490 } else {
491 while (true) {
492 // When two threads compete for `Region->MMLock`, we only want one of
493 // them to call populateFreeListAndPopBlocks(). To avoid both of them
494 // doing that, always check the freelist before mapping new pages.
495 ScopedLock ML(Region->MMLock);
496 {
497 ScopedLock FL(Region->FLLock);
498 PopCount = popBlocksImpl(SizeClassAllocator, ClassId, Region, ToArray,
499 MaxBlockCount);
500 if (PopCount != 0U)
501 return PopCount;
502 }
503
504 const bool RegionIsExhausted = Region->Exhausted;
505 if (!RegionIsExhausted) {
506 PopCount = populateFreeListAndPopBlocks(SizeClassAllocator, ClassId,
507 Region, ToArray, MaxBlockCount);
508 }
509 ReportRegionExhausted = !RegionIsExhausted && Region->Exhausted;
510 break;
511 }
512 }
513
514 if (UNLIKELY(ReportRegionExhausted)) {
515 Printf(Format: "Can't populate more pages for size class %zu.\n",
516 getSizeByClassId(ClassId));
517
518 // Theoretically, BatchClass shouldn't be used up. Abort immediately when
519 // it happens.
520 if (ClassId == SizeClassMap::BatchClassId)
521 reportOutOfBatchClass();
522 }
523
524 return PopCount;
525}
526
527template <typename Config>
528u16 SizeClassAllocator64<Config>::popBlocksWithCV(
529 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, RegionInfo *Region,
530 CompactPtrT *ToArray, const u16 MaxBlockCount,
531 bool &ReportRegionExhausted) {
532 u16 PopCount = 0;
533
534 while (true) {
535 // We only expect one thread doing the freelist refillment and other
536 // threads will be waiting for either the completion of the
537 // `populateFreeListAndPopBlocks()` or `pushBlocks()` called by other
538 // threads.
539 bool PopulateFreeList = false;
540 {
541 ScopedLock FL(Region->FLLock);
542 if (!Region->isPopulatingFreeList) {
543 Region->isPopulatingFreeList = true;
544 PopulateFreeList = true;
545 }
546 }
547
548 if (PopulateFreeList) {
549 ScopedLock ML(Region->MMLock);
550
551 const bool RegionIsExhausted = Region->Exhausted;
552 if (!RegionIsExhausted) {
553 PopCount = populateFreeListAndPopBlocks(SizeClassAllocator, ClassId,
554 Region, ToArray, MaxBlockCount);
555 }
556 ReportRegionExhausted = !RegionIsExhausted && Region->Exhausted;
557
558 {
559 // Before reacquiring the `FLLock`, the freelist may be used up again
560 // and some threads are waiting for the freelist refillment by the
561 // current thread. It's important to set
562 // `Region->isPopulatingFreeList` to false so the threads about to
563 // sleep will notice the status change.
564 ScopedLock FL(Region->FLLock);
565 Region->isPopulatingFreeList = false;
566 Region->FLLockCV.notifyAll(Region->FLLock);
567 }
568
569 break;
570 }
571
572 // At here, there are two preconditions to be met before waiting,
573 // 1. The freelist is empty.
574 // 2. Region->isPopulatingFreeList == true, i.e, someone is still doing
575 // `populateFreeListAndPopBlocks()`.
576 //
577 // Note that it has the chance that freelist is empty but
578 // Region->isPopulatingFreeList == false because all the new populated
579 // blocks were used up right after the refillment. Therefore, we have to
580 // check if someone is still populating the freelist.
581 ScopedLock FL(Region->FLLock);
582 PopCount = popBlocksImpl(SizeClassAllocator, ClassId, Region, ToArray,
583 MaxBlockCount);
584 if (PopCount != 0U)
585 break;
586
587 if (!Region->isPopulatingFreeList)
588 continue;
589
590 // Now the freelist is empty and someone's doing the refillment. We will
591 // wait until anyone refills the freelist or someone finishes doing
592 // `populateFreeListAndPopBlocks()`. The refillment can be done by
593 // `populateFreeListAndPopBlocks()`, `pushBlocks()`,
594 // `pushBatchClassBlocks()` and `mergeGroupsToReleaseBack()`.
595 Region->FLLockCV.wait(Region->FLLock);
596
597 PopCount = popBlocksImpl(SizeClassAllocator, ClassId, Region, ToArray,
598 MaxBlockCount);
599 if (PopCount != 0U)
600 break;
601 }
602
603 return PopCount;
604}
605
606template <typename Config>
607u16 SizeClassAllocator64<Config>::popBlocksImpl(
608 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, RegionInfo *Region,
609 CompactPtrT *ToArray, const u16 MaxBlockCount) REQUIRES(Region->FLLock) {
610 if (Region->FreeListInfo.BlockList.empty())
611 return 0U;
612
613 SinglyLinkedList<BatchT> &Batches =
614 Region->FreeListInfo.BlockList.front()->Batches;
615
616 if (Batches.empty()) {
617 DCHECK_EQ(ClassId, SizeClassMap::BatchClassId);
618 BatchGroupT *BG = Region->FreeListInfo.BlockList.front();
619 Region->FreeListInfo.BlockList.pop_front();
620
621 // Block used by `BatchGroup` is from BatchClassId. Turn the block into
622 // `Batch` with single block.
623 BatchT *TB = reinterpret_cast<BatchT *>(BG);
624 ToArray[0] =
625 compactPtr(ClassId: SizeClassMap::BatchClassId, Ptr: reinterpret_cast<uptr>(TB));
626 Region->FreeListInfo.PoppedBlocks += 1;
627 return 1U;
628 }
629
630 // So far, instead of always filling blocks to `MaxBlockCount`, we only
631 // examine single `Batch` to minimize the time spent in the primary
632 // allocator. Besides, the sizes of `Batch` and
633 // `SizeClassAllocatorT::getMaxCached()` may also impact the time spent on
634 // accessing the primary allocator.
635 // TODO(chiahungduan): Evaluate if we want to always prepare `MaxBlockCount`
636 // blocks and/or adjust the size of `Batch` according to
637 // `SizeClassAllocatorT::getMaxCached()`.
638 BatchT *B = Batches.front();
639 DCHECK_NE(B, nullptr);
640 DCHECK_GT(B->getCount(), 0U);
641
642 // BachClassId should always take all blocks in the Batch. Read the
643 // comment in `pushBatchClassBlocks()` for more details.
644 const u16 PopCount = ClassId == SizeClassMap::BatchClassId
645 ? B->getCount()
646 : Min(MaxBlockCount, B->getCount());
647 B->moveNToArray(ToArray, PopCount);
648
649 // TODO(chiahungduan): The deallocation of unused BatchClassId blocks can be
650 // done without holding `FLLock`.
651 if (B->empty()) {
652 Batches.pop_front();
653 // `Batch` of BatchClassId is self-contained, no need to
654 // deallocate. Read the comment in `pushBatchClassBlocks()` for more
655 // details.
656 if (ClassId != SizeClassMap::BatchClassId)
657 SizeClassAllocator->deallocate(SizeClassMap::BatchClassId, B);
658
659 if (Batches.empty()) {
660 BatchGroupT *BG = Region->FreeListInfo.BlockList.front();
661 Region->FreeListInfo.BlockList.pop_front();
662
663 // We don't keep BatchGroup with zero blocks to avoid empty-checking
664 // while allocating. Note that block used for constructing BatchGroup is
665 // recorded as free blocks in the last element of BatchGroup::Batches.
666 // Which means, once we pop the last Batch, the block is
667 // implicitly deallocated.
668 if (ClassId != SizeClassMap::BatchClassId)
669 SizeClassAllocator->deallocate(SizeClassMap::BatchClassId, BG);
670 }
671 }
672
673 Region->FreeListInfo.PoppedBlocks += PopCount;
674
675 return PopCount;
676}
677
678template <typename Config>
679u16 SizeClassAllocator64<Config>::populateFreeListAndPopBlocks(
680 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, RegionInfo *Region,
681 CompactPtrT *ToArray, const u16 MaxBlockCount) REQUIRES(Region->MMLock)
682 EXCLUDES(Region->FLLock) {
683 if (!Config::getEnableContiguousRegions() &&
684 !Region->MemMapInfo.MemMap.isAllocated()) {
685 ReservedMemoryT ReservedMemory;
686 if (UNLIKELY(!ReservedMemory.create(/*Addr=*/0U, RegionSize,
687 "scudo:primary_reserve",
688 MAP_ALLOWNOMEM))) {
689 Printf(Format: "Can't reserve pages for size class %zu.\n",
690 getSizeByClassId(ClassId));
691 return 0U;
692 }
693 initRegion(Region, ClassId,
694 MemMap: ReservedMemory.dispatch(Addr: ReservedMemory.getBase(),
695 Size: ReservedMemory.getCapacity()),
696 /*EnableRandomOffset=*/EnableRandomOffset: false);
697 }
698
699 DCHECK(Region->MemMapInfo.MemMap.isAllocated());
700 const uptr Size = getSizeByClassId(ClassId);
701 const u16 MaxCount = SizeClassAllocatorT::getMaxCached(Size);
702 const uptr RegionBeg = Region->RegionBeg;
703 const uptr MappedUser = Region->MemMapInfo.MappedUser;
704 const uptr TotalUserBytes =
705 Region->MemMapInfo.AllocatedUser + MaxCount * Size;
706 // Map more space for blocks, if necessary.
707 if (TotalUserBytes > MappedUser) {
708 // Do the mmap for the user memory.
709 const uptr MapSize = roundUp(X: TotalUserBytes - MappedUser, Boundary: MapSizeIncrement);
710 const uptr RegionBase = RegionBeg - getRegionBaseByClassId(ClassId);
711 if (UNLIKELY(RegionBase + MappedUser + MapSize > RegionSize)) {
712 Region->Exhausted = true;
713 return 0U;
714 }
715
716 if (UNLIKELY(!Region->MemMapInfo.MemMap.remap(
717 RegionBeg + MappedUser, MapSize, "scudo:primary",
718 MAP_ALLOWNOMEM | MAP_RESIZABLE |
719 (useMemoryTagging<Config>(Options.load()) ? MAP_MEMTAG : 0)))) {
720 return 0U;
721 }
722 Region->MemMapInfo.MappedUser += MapSize;
723 SizeClassAllocator->getStats().add(StatMapped, MapSize);
724 }
725
726 const u32 NumberOfBlocks =
727 Min(A: MaxNumBatches * MaxCount,
728 B: static_cast<u32>((Region->MemMapInfo.MappedUser -
729 Region->MemMapInfo.AllocatedUser) /
730 Size));
731 DCHECK_GT(NumberOfBlocks, 0);
732
733 constexpr u32 ShuffleArraySize = MaxNumBatches * MaxNumBlocksInBatch;
734 CompactPtrT ShuffleArray[ShuffleArraySize];
735 DCHECK_LE(NumberOfBlocks, ShuffleArraySize);
736
737 const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId);
738 uptr P = RegionBeg + Region->MemMapInfo.AllocatedUser;
739 for (u32 I = 0; I < NumberOfBlocks; I++, P += Size)
740 ShuffleArray[I] = compactPtrInternal(Base: CompactPtrBase, Ptr: P);
741
742 ScopedLock L(Region->FLLock);
743
744 if (ClassId != SizeClassMap::BatchClassId) {
745 u32 N = 1;
746 uptr CurGroup = compactPtrGroup(CompactPtr: ShuffleArray[0]);
747 for (u32 I = 1; I < NumberOfBlocks; I++) {
748 if (UNLIKELY(compactPtrGroup(ShuffleArray[I]) != CurGroup)) {
749 shuffle(ShuffleArray + I - N, N, &Region->RandState);
750 pushBlocksImpl(SizeClassAllocator, ClassId, Region,
751 Array: ShuffleArray + I - N, Size: N,
752 /*SameGroup=*/SameGroup: true);
753 N = 1;
754 CurGroup = compactPtrGroup(CompactPtr: ShuffleArray[I]);
755 } else {
756 ++N;
757 }
758 }
759
760 shuffle(ShuffleArray + NumberOfBlocks - N, N, &Region->RandState);
761 pushBlocksImpl(SizeClassAllocator, ClassId, Region,
762 Array: &ShuffleArray[NumberOfBlocks - N], Size: N,
763 /*SameGroup=*/SameGroup: true);
764 } else {
765 pushBatchClassBlocks(Region, Array: ShuffleArray, Size: NumberOfBlocks);
766 }
767
768 const u16 PopCount = popBlocksImpl(SizeClassAllocator, ClassId, Region,
769 ToArray, MaxBlockCount);
770 DCHECK_NE(PopCount, 0U);
771
772 // Note that `PushedBlocks` and `PoppedBlocks` are supposed to only record
773 // the requests from `PushBlocks` and `PopBatch` which are external
774 // interfaces. `populateFreeListAndPopBlocks` is the internal interface so
775 // we should set the values back to avoid incorrectly setting the stats.
776 Region->FreeListInfo.PushedBlocks -= NumberOfBlocks;
777
778 const uptr AllocatedUser = Size * NumberOfBlocks;
779 SizeClassAllocator->getStats().add(StatFree, AllocatedUser);
780 Region->MemMapInfo.AllocatedUser += AllocatedUser;
781
782 return PopCount;
783}
784
785template <typename Config>
786void SizeClassAllocator64<Config>::pushBlocks(
787 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, CompactPtrT *Array,
788 u32 Size) {
789 DCHECK_LT(ClassId, NumClasses);
790 DCHECK_GT(Size, 0);
791
792 RegionInfo *Region = getRegionInfo(ClassId);
793 if (ClassId == SizeClassMap::BatchClassId) {
794 ScopedLock L(Region->FLLock);
795 pushBatchClassBlocks(Region, Array, Size);
796 if (conditionVariableEnabled())
797 Region->FLLockCV.notifyAll(Region->FLLock);
798 return;
799 }
800
801 // TODO(chiahungduan): Consider not doing grouping if the group size is not
802 // greater than the block size with a certain scale.
803
804 bool SameGroup = true;
805 if (GroupSizeLog < RegionSizeLog) {
806 // Sort the blocks so that blocks belonging to the same group can be
807 // pushed together.
808 for (u32 I = 1; I < Size; ++I) {
809 if (compactPtrGroup(CompactPtr: Array[I - 1]) != compactPtrGroup(CompactPtr: Array[I]))
810 SameGroup = false;
811 CompactPtrT Cur = Array[I];
812 u32 J = I;
813 while (J > 0 && compactPtrGroup(CompactPtr: Cur) < compactPtrGroup(CompactPtr: Array[J - 1])) {
814 Array[J] = Array[J - 1];
815 --J;
816 }
817 Array[J] = Cur;
818 }
819 }
820
821 {
822 ScopedLock L(Region->FLLock);
823 pushBlocksImpl(SizeClassAllocator, ClassId, Region, Array, Size, SameGroup);
824 if (conditionVariableEnabled())
825 Region->FLLockCV.notifyAll(Region->FLLock);
826 }
827}
828
829// Push the blocks to their batch group. The layout will be like,
830//
831// FreeListInfo.BlockList - > BG -> BG -> BG
832// | | |
833// v v v
834// TB TB TB
835// |
836// v
837// TB
838//
839// Each BlockGroup(BG) will associate with unique group id and the free blocks
840// are managed by a list of Batch(TB). To reduce the time of inserting blocks,
841// BGs are sorted and the input `Array` are supposed to be sorted so that we can
842// get better performance of maintaining sorted property. Use `SameGroup=true`
843// to indicate that all blocks in the array are from the same group then we will
844// skip checking the group id of each block.
845template <typename Config>
846void SizeClassAllocator64<Config>::pushBlocksImpl(
847 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, RegionInfo *Region,
848 CompactPtrT *Array, u32 Size, bool SameGroup) REQUIRES(Region->FLLock) {
849 DCHECK_NE(ClassId, SizeClassMap::BatchClassId);
850 DCHECK_GT(Size, 0U);
851
852 auto CreateGroup = [&](uptr CompactPtrGroupBase) {
853 BatchGroupT *BG = reinterpret_cast<BatchGroupT *>(
854 SizeClassAllocator->getBatchClassBlock());
855 BG->Batches.clear();
856 BatchT *TB =
857 reinterpret_cast<BatchT *>(SizeClassAllocator->getBatchClassBlock());
858 TB->clear();
859
860 BG->CompactPtrGroupBase = CompactPtrGroupBase;
861 BG->Batches.push_front(TB);
862 BG->BytesInBGAtLastCheckpoint = 0;
863 BG->MaxCachedPerBatch = MaxNumBlocksInBatch;
864
865 return BG;
866 };
867
868 auto InsertBlocks = [&](BatchGroupT *BG, CompactPtrT *Array, u32 Size) {
869 SinglyLinkedList<BatchT> &Batches = BG->Batches;
870 BatchT *CurBatch = Batches.front();
871 DCHECK_NE(CurBatch, nullptr);
872
873 for (u32 I = 0; I < Size;) {
874 DCHECK_GE(BG->MaxCachedPerBatch, CurBatch->getCount());
875 u16 UnusedSlots =
876 static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount());
877 if (UnusedSlots == 0) {
878 CurBatch = reinterpret_cast<BatchT *>(
879 SizeClassAllocator->getBatchClassBlock());
880 CurBatch->clear();
881 Batches.push_front(CurBatch);
882 UnusedSlots = BG->MaxCachedPerBatch;
883 }
884 // `UnusedSlots` is u16 so the result will be also fit in u16.
885 u16 AppendSize = static_cast<u16>(Min<u32>(A: UnusedSlots, B: Size - I));
886 CurBatch->appendFromArray(&Array[I], AppendSize);
887 I += AppendSize;
888 }
889 };
890
891 Region->FreeListInfo.PushedBlocks += Size;
892 BatchGroupT *Cur = Region->FreeListInfo.BlockList.front();
893
894 // In the following, `Cur` always points to the BatchGroup for blocks that
895 // will be pushed next. `Prev` is the element right before `Cur`.
896 BatchGroupT *Prev = nullptr;
897
898 while (Cur != nullptr &&
899 compactPtrGroup(CompactPtr: Array[0]) > Cur->CompactPtrGroupBase) {
900 Prev = Cur;
901 Cur = Cur->Next;
902 }
903
904 if (Cur == nullptr || compactPtrGroup(CompactPtr: Array[0]) != Cur->CompactPtrGroupBase) {
905 Cur = CreateGroup(compactPtrGroup(CompactPtr: Array[0]));
906 if (Prev == nullptr)
907 Region->FreeListInfo.BlockList.push_front(Cur);
908 else
909 Region->FreeListInfo.BlockList.insert(Prev, Cur);
910 }
911
912 // All the blocks are from the same group, just push without checking group
913 // id.
914 if (SameGroup) {
915 for (u32 I = 0; I < Size; ++I)
916 DCHECK_EQ(compactPtrGroup(Array[I]), Cur->CompactPtrGroupBase);
917
918 InsertBlocks(Cur, Array, Size);
919 return;
920 }
921
922 // The blocks are sorted by group id. Determine the segment of group and
923 // push them to their group together.
924 u32 Count = 1;
925 for (u32 I = 1; I < Size; ++I) {
926 if (compactPtrGroup(CompactPtr: Array[I - 1]) != compactPtrGroup(CompactPtr: Array[I])) {
927 DCHECK_EQ(compactPtrGroup(Array[I - 1]), Cur->CompactPtrGroupBase);
928 InsertBlocks(Cur, Array + I - Count, Count);
929
930 while (Cur != nullptr &&
931 compactPtrGroup(CompactPtr: Array[I]) > Cur->CompactPtrGroupBase) {
932 Prev = Cur;
933 Cur = Cur->Next;
934 }
935
936 if (Cur == nullptr ||
937 compactPtrGroup(CompactPtr: Array[I]) != Cur->CompactPtrGroupBase) {
938 Cur = CreateGroup(compactPtrGroup(CompactPtr: Array[I]));
939 DCHECK_NE(Prev, nullptr);
940 Region->FreeListInfo.BlockList.insert(Prev, Cur);
941 }
942
943 Count = 1;
944 } else {
945 ++Count;
946 }
947 }
948
949 InsertBlocks(Cur, Array + Size - Count, Count);
950}
951
952template <typename Config>
953void SizeClassAllocator64<Config>::pushBatchClassBlocks(RegionInfo *Region,
954 CompactPtrT *Array,
955 u32 Size)
956 REQUIRES(Region->FLLock) {
957 DCHECK_EQ(Region, getRegionInfo(SizeClassMap::BatchClassId));
958
959 // Free blocks are recorded by Batch in freelist for all
960 // size-classes. In addition, Batch is allocated from BatchClassId.
961 // In order not to use additional block to record the free blocks in
962 // BatchClassId, they are self-contained. I.e., A Batch records the
963 // block address of itself. See the figure below:
964 //
965 // Batch at 0xABCD
966 // +----------------------------+
967 // | Free blocks' addr |
968 // | +------+------+------+ |
969 // | |0xABCD|... |... | |
970 // | +------+------+------+ |
971 // +----------------------------+
972 //
973 // When we allocate all the free blocks in the Batch, the block used
974 // by Batch is also free for use. We don't need to recycle the
975 // Batch. Note that the correctness is maintained by the invariant,
976 //
977 // Each popBlocks() request returns the entire Batch. Returning
978 // part of the blocks in a Batch is invalid.
979 //
980 // This ensures that Batch won't leak the address itself while it's
981 // still holding other valid data.
982 //
983 // Besides, BatchGroup is also allocated from BatchClassId and has its
984 // address recorded in the Batch too. To maintain the correctness,
985 //
986 // The address of BatchGroup is always recorded in the last Batch
987 // in the freelist (also imply that the freelist should only be
988 // updated with push_front). Once the last Batch is popped,
989 // the block used by BatchGroup is also free for use.
990 //
991 // With this approach, the blocks used by BatchGroup and Batch are
992 // reusable and don't need additional space for them.
993
994 Region->FreeListInfo.PushedBlocks += Size;
995 BatchGroupT *BG = Region->FreeListInfo.BlockList.front();
996
997 if (BG == nullptr) {
998 // Construct `BatchGroup` on the last element.
999 BG = reinterpret_cast<BatchGroupT *>(
1000 decompactPtr(ClassId: SizeClassMap::BatchClassId, CompactPtr: Array[Size - 1]));
1001 --Size;
1002 BG->Batches.clear();
1003 // BatchClass hasn't enabled memory group. Use `0` to indicate there's no
1004 // memory group here.
1005 BG->CompactPtrGroupBase = 0;
1006 BG->BytesInBGAtLastCheckpoint = 0;
1007 BG->MaxCachedPerBatch = SizeClassAllocatorT::getMaxCached(
1008 getSizeByClassId(ClassId: SizeClassMap::BatchClassId));
1009
1010 Region->FreeListInfo.BlockList.push_front(BG);
1011 }
1012
1013 if (UNLIKELY(Size == 0))
1014 return;
1015
1016 // This happens under 2 cases.
1017 // 1. just allocated a new `BatchGroup`.
1018 // 2. Only 1 block is pushed when the freelist is empty.
1019 if (BG->Batches.empty()) {
1020 // Construct the `Batch` on the last element.
1021 BatchT *TB = reinterpret_cast<BatchT *>(
1022 decompactPtr(ClassId: SizeClassMap::BatchClassId, CompactPtr: Array[Size - 1]));
1023 TB->clear();
1024 // As mentioned above, addresses of `Batch` and `BatchGroup` are
1025 // recorded in the Batch.
1026 TB->add(Array[Size - 1]);
1027 TB->add(compactPtr(ClassId: SizeClassMap::BatchClassId, Ptr: reinterpret_cast<uptr>(BG)));
1028 --Size;
1029 BG->Batches.push_front(TB);
1030 }
1031
1032 BatchT *CurBatch = BG->Batches.front();
1033 DCHECK_NE(CurBatch, nullptr);
1034
1035 for (u32 I = 0; I < Size;) {
1036 u16 UnusedSlots =
1037 static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount());
1038 if (UnusedSlots == 0) {
1039 CurBatch = reinterpret_cast<BatchT *>(
1040 decompactPtr(ClassId: SizeClassMap::BatchClassId, CompactPtr: Array[I]));
1041 CurBatch->clear();
1042 // Self-contained
1043 CurBatch->add(Array[I]);
1044 ++I;
1045 // TODO(chiahungduan): Avoid the use of push_back() in `Batches` of
1046 // BatchClassId.
1047 BG->Batches.push_front(CurBatch);
1048 UnusedSlots = static_cast<u16>(BG->MaxCachedPerBatch - 1);
1049 }
1050 // `UnusedSlots` is u16 so the result will be also fit in u16.
1051 const u16 AppendSize = static_cast<u16>(Min<u32>(A: UnusedSlots, B: Size - I));
1052 CurBatch->appendFromArray(&Array[I], AppendSize);
1053 I += AppendSize;
1054 }
1055}
1056
1057template <typename Config>
1058void SizeClassAllocator64<Config>::disable() NO_THREAD_SAFETY_ANALYSIS {
1059 // The BatchClassId must be locked last since other classes can use it.
1060 for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {
1061 if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)
1062 continue;
1063 getRegionInfo(ClassId: static_cast<uptr>(I))->MMLock.lock();
1064 getRegionInfo(ClassId: static_cast<uptr>(I))->FLLock.lock();
1065 }
1066 getRegionInfo(ClassId: SizeClassMap::BatchClassId)->MMLock.lock();
1067 getRegionInfo(ClassId: SizeClassMap::BatchClassId)->FLLock.lock();
1068}
1069
1070template <typename Config>
1071void SizeClassAllocator64<Config>::enable() NO_THREAD_SAFETY_ANALYSIS {
1072 getRegionInfo(ClassId: SizeClassMap::BatchClassId)->FLLock.unlock();
1073 getRegionInfo(ClassId: SizeClassMap::BatchClassId)->MMLock.unlock();
1074 for (uptr I = 0; I < NumClasses; I++) {
1075 if (I == SizeClassMap::BatchClassId)
1076 continue;
1077 getRegionInfo(ClassId: I)->FLLock.unlock();
1078 getRegionInfo(ClassId: I)->MMLock.unlock();
1079 }
1080}
1081
1082template <typename Config>
1083template <typename F>
1084void SizeClassAllocator64<Config>::iterateOverBlocks(F Callback) {
1085 for (uptr I = 0; I < NumClasses; I++) {
1086 if (I == SizeClassMap::BatchClassId)
1087 continue;
1088 RegionInfo *Region = getRegionInfo(ClassId: I);
1089 // TODO: The call of `iterateOverBlocks` requires disabling
1090 // SizeClassAllocator64. We may consider locking each region on demand
1091 // only.
1092 Region->FLLock.assertHeld();
1093 Region->MMLock.assertHeld();
1094 const uptr BlockSize = getSizeByClassId(ClassId: I);
1095 const uptr From = Region->RegionBeg;
1096 const uptr To = From + Region->MemMapInfo.AllocatedUser;
1097 for (uptr Block = From; Block < To; Block += BlockSize)
1098 Callback(Block);
1099 }
1100}
1101
1102template <typename Config>
1103void SizeClassAllocator64<Config>::getStats(ScopedString *Str) {
1104 // TODO(kostyak): get the RSS per region.
1105 uptr TotalMapped = 0;
1106 uptr PoppedBlocks = 0;
1107 uptr PushedBlocks = 0;
1108 for (uptr I = 0; I < NumClasses; I++) {
1109 RegionInfo *Region = getRegionInfo(ClassId: I);
1110 {
1111 ScopedLock L(Region->MMLock);
1112 TotalMapped += Region->MemMapInfo.MappedUser;
1113 }
1114 {
1115 ScopedLock L(Region->FLLock);
1116 PoppedBlocks += Region->FreeListInfo.PoppedBlocks;
1117 PushedBlocks += Region->FreeListInfo.PushedBlocks;
1118 }
1119 }
1120 const s32 IntervalMs = atomic_load_relaxed(A: &ReleaseToOsIntervalMs);
1121 Str->append(Format: "Stats: SizeClassAllocator64: %zuM mapped (%uM rss) in %zu "
1122 "allocations; remains %zu; ReleaseToOsIntervalMs = %d\n",
1123 TotalMapped >> 20, 0U, PoppedBlocks, PoppedBlocks - PushedBlocks,
1124 IntervalMs >= 0 ? IntervalMs : -1);
1125
1126 for (uptr I = 0; I < NumClasses; I++) {
1127 RegionInfo *Region = getRegionInfo(ClassId: I);
1128 ScopedLock L1(Region->MMLock);
1129 ScopedLock L2(Region->FLLock);
1130 getStats(Str, I, Region);
1131 }
1132}
1133
1134template <typename Config>
1135void SizeClassAllocator64<Config>::getStats(ScopedString *Str, uptr ClassId,
1136 RegionInfo *Region)
1137 REQUIRES(Region->MMLock, Region->FLLock) {
1138 if (Region->MemMapInfo.MappedUser == 0)
1139 return;
1140 const uptr BlockSize = getSizeByClassId(ClassId);
1141 const uptr InUseBlocks =
1142 Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks;
1143 const uptr BytesInFreeList =
1144 Region->MemMapInfo.AllocatedUser - InUseBlocks * BlockSize;
1145 uptr RegionPushedBytesDelta = 0;
1146 if (BytesInFreeList >= Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint) {
1147 RegionPushedBytesDelta =
1148 BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint;
1149 }
1150 const uptr TotalChunks = Region->MemMapInfo.AllocatedUser / BlockSize;
1151 Str->append(
1152 Format: "%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
1153 "inuse: %6zu total: %6zu releases attempted: %6zu last "
1154 "released: %6zuK latest pushed bytes: %6zuK region: 0x%zx "
1155 "(0x%zx)",
1156 Region->Exhausted ? "E" : " ", ClassId, getSizeByClassId(ClassId),
1157 Region->MemMapInfo.MappedUser >> 10, Region->FreeListInfo.PoppedBlocks,
1158 Region->FreeListInfo.PushedBlocks, InUseBlocks, TotalChunks,
1159 Region->ReleaseInfo.NumReleasesAttempted,
1160 Region->ReleaseInfo.LastReleasedBytes >> 10, RegionPushedBytesDelta >> 10,
1161 Region->RegionBeg, getRegionBaseByClassId(ClassId));
1162 const u64 CurTimeNs = getMonotonicTimeFast();
1163 const u64 LastReleaseAtNs = Region->ReleaseInfo.LastReleaseAtNs;
1164 if (LastReleaseAtNs != 0 && CurTimeNs != LastReleaseAtNs) {
1165 const u64 DiffSinceLastReleaseNs =
1166 CurTimeNs - Region->ReleaseInfo.LastReleaseAtNs;
1167 const u64 LastReleaseSecAgo = DiffSinceLastReleaseNs / 1000000000;
1168 const u64 LastReleaseMsAgo =
1169 (DiffSinceLastReleaseNs % 1000000000) / 1000000;
1170 Str->append(Format: " Latest release: %6" PRIu64 ":%03" PRIu64 " seconds ago",
1171 LastReleaseSecAgo, LastReleaseMsAgo);
1172 }
1173 const s64 ResidentPages = Region->MemMapInfo.MemMap.getResidentPages();
1174 if (ResidentPages >= 0) {
1175 Str->append(Format: " Resident Pages: %6" PRIu64, ResidentPages);
1176 }
1177 Str->append(Format: "\n");
1178}
1179
1180template <typename Config>
1181void SizeClassAllocator64<Config>::getFragmentationInfo(ScopedString *Str) {
1182 Str->append(
1183 Format: "Fragmentation Stats: SizeClassAllocator64: page size = %zu bytes\n",
1184 getPageSizeCached());
1185
1186 for (uptr I = 1; I < NumClasses; I++) {
1187 RegionInfo *Region = getRegionInfo(ClassId: I);
1188 ScopedLock L(Region->MMLock);
1189 getRegionFragmentationInfo(Region, ClassId: I, Str);
1190 }
1191}
1192
1193template <typename Config>
1194void SizeClassAllocator64<Config>::getRegionFragmentationInfo(
1195 RegionInfo *Region, uptr ClassId, ScopedString *Str)
1196 REQUIRES(Region->MMLock) {
1197 const uptr BlockSize = getSizeByClassId(ClassId);
1198 const uptr AllocatedUserEnd =
1199 Region->MemMapInfo.AllocatedUser + Region->RegionBeg;
1200
1201 SinglyLinkedList<BatchGroupT> GroupsToRelease;
1202 {
1203 ScopedLock L(Region->FLLock);
1204 GroupsToRelease = Region->FreeListInfo.BlockList;
1205 Region->FreeListInfo.BlockList.clear();
1206 }
1207
1208 FragmentationRecorder Recorder;
1209 if (!GroupsToRelease.empty()) {
1210 PageReleaseContext Context =
1211 markFreeBlocks(Region, BlockSize, AllocatedUserEnd,
1212 CompactPtrBase: getCompactPtrBaseByClassId(ClassId), GroupsToRelease);
1213 auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };
1214 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
1215
1216 mergeGroupsToReleaseBack(Region, GroupsToRelease);
1217 }
1218
1219 ScopedLock L(Region->FLLock);
1220 const uptr PageSize = getPageSizeCached();
1221 const uptr TotalBlocks = Region->MemMapInfo.AllocatedUser / BlockSize;
1222 const uptr InUseBlocks =
1223 Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks;
1224 const uptr AllocatedPagesCount =
1225 roundUp(Region->MemMapInfo.AllocatedUser, PageSize) / PageSize;
1226 DCHECK_GE(AllocatedPagesCount, Recorder.getReleasedPagesCount());
1227 const uptr InUsePages =
1228 AllocatedPagesCount - Recorder.getReleasedPagesCount();
1229 const uptr InUseBytes = InUsePages * PageSize;
1230
1231 uptr Integral;
1232 uptr Fractional;
1233 computePercentage(Numerator: BlockSize * InUseBlocks, Denominator: InUseBytes, Integral: &Integral,
1234 Fractional: &Fractional);
1235 Str->append(Format: " %02zu (%6zu): inuse/total blocks: %6zu/%6zu inuse/total "
1236 "pages: %6zu/%6zu inuse bytes: %6zuK util: %3zu.%02zu%%\n",
1237 ClassId, BlockSize, InUseBlocks, TotalBlocks, InUsePages,
1238 AllocatedPagesCount, InUseBytes >> 10, Integral, Fractional);
1239}
1240
1241template <typename Config>
1242void SizeClassAllocator64<Config>::getMemoryGroupFragmentationInfoInRegion(
1243 RegionInfo *Region, uptr ClassId, ScopedString *Str)
1244 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {
1245 const uptr BlockSize = getSizeByClassId(ClassId);
1246 const uptr AllocatedUserEnd =
1247 Region->MemMapInfo.AllocatedUser + Region->RegionBeg;
1248
1249 SinglyLinkedList<BatchGroupT> GroupsToRelease;
1250 {
1251 ScopedLock L(Region->FLLock);
1252 GroupsToRelease = Region->FreeListInfo.BlockList;
1253 Region->FreeListInfo.BlockList.clear();
1254 }
1255
1256 constexpr uptr GroupSize = (1UL << GroupSizeLog);
1257 constexpr uptr MaxNumGroups = RegionSize / GroupSize;
1258
1259 MemoryGroupFragmentationRecorder<GroupSize, MaxNumGroups> Recorder;
1260 if (!GroupsToRelease.empty()) {
1261 PageReleaseContext Context =
1262 markFreeBlocks(Region, BlockSize, AllocatedUserEnd,
1263 CompactPtrBase: getCompactPtrBaseByClassId(ClassId), GroupsToRelease);
1264 auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };
1265 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
1266
1267 mergeGroupsToReleaseBack(Region, GroupsToRelease);
1268 }
1269
1270 Str->append(Format: "MemoryGroupFragmentationInfo in Region %zu (%zu)\n", ClassId,
1271 BlockSize);
1272
1273 const uptr MaxNumGroupsInUse =
1274 roundUp(Region->MemMapInfo.AllocatedUser, GroupSize) / GroupSize;
1275 for (uptr I = 0; I < MaxNumGroupsInUse; ++I) {
1276 uptr Integral;
1277 uptr Fractional;
1278 computePercentage(Recorder.NumPagesInOneGroup - Recorder.getNumFreePages(I),
1279 Recorder.NumPagesInOneGroup, &Integral, &Fractional);
1280 Str->append(Format: "MemoryGroup #%zu (0x%zx): util: %3zu.%02zu%%\n", I,
1281 Region->RegionBeg + I * GroupSize, Integral, Fractional);
1282 }
1283}
1284
1285template <typename Config>
1286void SizeClassAllocator64<Config>::getMemoryGroupFragmentationInfo(
1287 ScopedString *Str) {
1288 Str->append(
1289 Format: "Fragmentation Stats: SizeClassAllocator64: page size = %zu bytes\n",
1290 getPageSizeCached());
1291
1292 for (uptr I = 1; I < NumClasses; I++) {
1293 RegionInfo *Region = getRegionInfo(ClassId: I);
1294 ScopedLock L(Region->MMLock);
1295 getMemoryGroupFragmentationInfoInRegion(Region, ClassId: I, Str);
1296 }
1297}
1298
1299template <typename Config>
1300bool SizeClassAllocator64<Config>::setOption(Option O, sptr Value) {
1301 if (O == Option::ReleaseInterval) {
1302 const s32 Interval =
1303 Max(Min(static_cast<s32>(Value), Config::getMaxReleaseToOsIntervalMs()),
1304 Config::getMinReleaseToOsIntervalMs());
1305 atomic_store_relaxed(A: &ReleaseToOsIntervalMs, V: Interval);
1306 return true;
1307 }
1308 // Not supported by the Primary, but not an error either.
1309 return true;
1310}
1311
1312template <typename Config>
1313uptr SizeClassAllocator64<Config>::tryReleaseToOS(uptr ClassId,
1314 ReleaseToOS ReleaseType) {
1315 RegionInfo *Region = getRegionInfo(ClassId);
1316 // Note that the tryLock() may fail spuriously, given that it should rarely
1317 // happen and page releasing is fine to skip, we don't take certain
1318 // approaches to ensure one page release is done.
1319 if (Region->MMLock.tryLock()) {
1320 uptr BytesReleased = releaseToOSMaybe(Region, ClassId, ReleaseType);
1321 Region->MMLock.unlock();
1322 return BytesReleased;
1323 }
1324 return 0;
1325}
1326
1327template <typename Config>
1328uptr SizeClassAllocator64<Config>::releaseToOS(ReleaseToOS ReleaseType) {
1329 SCUDO_SCOPED_TRACE(GetPrimaryReleaseToOSTraceName(ReleaseType));
1330
1331 uptr TotalReleasedBytes = 0;
1332 for (uptr I = 0; I < NumClasses; I++) {
1333 if (I == SizeClassMap::BatchClassId)
1334 continue;
1335 RegionInfo *Region = getRegionInfo(ClassId: I);
1336 if (ReleaseType == ReleaseToOS::ForceFast) {
1337 // Never wait for the lock, always move on if there is already
1338 // a release operation in progress.
1339 if (Region->MMLock.tryLock()) {
1340 TotalReleasedBytes += releaseToOSMaybe(Region, ClassId: I, ReleaseType);
1341 Region->MMLock.unlock();
1342 }
1343 } else {
1344 ScopedLock L(Region->MMLock);
1345 TotalReleasedBytes += releaseToOSMaybe(Region, ClassId: I, ReleaseType);
1346 }
1347 }
1348 return TotalReleasedBytes;
1349}
1350
1351template <typename Config>
1352/* static */ BlockInfo SizeClassAllocator64<Config>::findNearestBlock(
1353 const char *RegionInfoData, uptr Ptr) NO_THREAD_SAFETY_ANALYSIS {
1354 const RegionInfo *RegionInfoArray =
1355 reinterpret_cast<const RegionInfo *>(RegionInfoData);
1356
1357 uptr ClassId;
1358 uptr MinDistance = -1UL;
1359 for (uptr I = 0; I != NumClasses; ++I) {
1360 if (I == SizeClassMap::BatchClassId)
1361 continue;
1362 uptr Begin = RegionInfoArray[I].RegionBeg;
1363 // TODO(chiahungduan): In fact, We need to lock the RegionInfo::MMLock.
1364 // However, the RegionInfoData is passed with const qualifier and lock the
1365 // mutex requires modifying RegionInfoData, which means we need to remove
1366 // the const qualifier. This may lead to another undefined behavior (The
1367 // first one is accessing `AllocatedUser` without locking. It's better to
1368 // pass `RegionInfoData` as `void *` then we can lock the mutex properly.
1369 uptr End = Begin + RegionInfoArray[I].MemMapInfo.AllocatedUser;
1370 if (Begin > End || End - Begin < SizeClassMap::getSizeByClassId(I))
1371 continue;
1372 uptr RegionDistance;
1373 if (Begin <= Ptr) {
1374 if (Ptr < End)
1375 RegionDistance = 0;
1376 else
1377 RegionDistance = Ptr - End;
1378 } else {
1379 RegionDistance = Begin - Ptr;
1380 }
1381
1382 if (RegionDistance < MinDistance) {
1383 MinDistance = RegionDistance;
1384 ClassId = I;
1385 }
1386 }
1387
1388 BlockInfo B = {};
1389 if (MinDistance <= 8192) {
1390 B.RegionBegin = RegionInfoArray[ClassId].RegionBeg;
1391 B.RegionEnd =
1392 B.RegionBegin + RegionInfoArray[ClassId].MemMapInfo.AllocatedUser;
1393 B.BlockSize = SizeClassMap::getSizeByClassId(ClassId);
1394 B.BlockBegin = B.RegionBegin + uptr(sptr(Ptr - B.RegionBegin) /
1395 sptr(B.BlockSize) * sptr(B.BlockSize));
1396 while (B.BlockBegin < B.RegionBegin)
1397 B.BlockBegin += B.BlockSize;
1398 while (B.RegionEnd < B.BlockBegin + B.BlockSize)
1399 B.BlockBegin -= B.BlockSize;
1400 }
1401 return B;
1402}
1403
1404template <typename Config>
1405uptr SizeClassAllocator64<Config>::releaseToOSMaybe(RegionInfo *Region,
1406 uptr ClassId,
1407 ReleaseToOS ReleaseType)
1408 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {
1409 const uptr BlockSize = getSizeByClassId(ClassId);
1410 uptr BytesInFreeList;
1411 const uptr AllocatedUserEnd =
1412 Region->MemMapInfo.AllocatedUser + Region->RegionBeg;
1413 uptr RegionPushedBytesDelta = 0;
1414 SinglyLinkedList<BatchGroupT> GroupsToRelease;
1415
1416 {
1417 ScopedLock L(Region->FLLock);
1418
1419 BytesInFreeList =
1420 Region->MemMapInfo.AllocatedUser - (Region->FreeListInfo.PoppedBlocks -
1421 Region->FreeListInfo.PushedBlocks) *
1422 BlockSize;
1423 if (UNLIKELY(BytesInFreeList == 0))
1424 return 0;
1425
1426 // ==================================================================== //
1427 // 1. Check if we have enough free blocks and if it's worth doing a page
1428 // release.
1429 // ==================================================================== //
1430 if (ReleaseType != ReleaseToOS::ForceAll &&
1431 !hasChanceToReleasePages(Region, BlockSize, BytesInFreeList,
1432 ReleaseType)) {
1433 return 0;
1434 }
1435
1436 // Given that we will unlock the freelist for block operations, cache the
1437 // value here so that when we are adapting the `TryReleaseThreshold`
1438 // later, we are using the right metric.
1439 RegionPushedBytesDelta =
1440 BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint;
1441
1442 // ==================================================================== //
1443 // 2. Determine which groups can release the pages. Use a heuristic to
1444 // gather groups that are candidates for doing a release.
1445 // ==================================================================== //
1446 if (ReleaseType == ReleaseToOS::ForceAll) {
1447 GroupsToRelease = Region->FreeListInfo.BlockList;
1448 Region->FreeListInfo.BlockList.clear();
1449 } else {
1450 GroupsToRelease =
1451 collectGroupsToRelease(Region, BlockSize, AllocatedUserEnd,
1452 CompactPtrBase: getCompactPtrBaseByClassId(ClassId));
1453 }
1454 if (GroupsToRelease.empty())
1455 return 0;
1456 }
1457
1458 // The following steps contribute to the majority time spent in page
1459 // releasing thus we increment the counter here.
1460 ++Region->ReleaseInfo.NumReleasesAttempted;
1461
1462 // Note that we have extracted the `GroupsToRelease` from region freelist.
1463 // It's safe to let pushBlocks()/popBlocks() access the remaining region
1464 // freelist. In the steps 3 and 4, we will temporarily release the FLLock
1465 // and lock it again before step 5.
1466
1467 // ==================================================================== //
1468 // 3. Mark the free blocks in `GroupsToRelease` in the `PageReleaseContext`.
1469 // Then we can tell which pages are in-use by querying
1470 // `PageReleaseContext`.
1471 // ==================================================================== //
1472
1473 // Only add trace point after the quick returns have occurred to avoid
1474 // incurring performance penalties. Most of the time in this function
1475 // will be the mark free blocks call and the actual release to OS call.
1476 SCUDO_SCOPED_TRACE(GetPrimaryReleaseToOSMaybeTraceName(ReleaseType));
1477
1478 PageReleaseContext Context =
1479 markFreeBlocks(Region, BlockSize, AllocatedUserEnd,
1480 CompactPtrBase: getCompactPtrBaseByClassId(ClassId), GroupsToRelease);
1481 if (UNLIKELY(!Context.hasBlockMarked())) {
1482 mergeGroupsToReleaseBack(Region, GroupsToRelease);
1483 return 0;
1484 }
1485
1486 // ==================================================================== //
1487 // 4. Release the unused physical pages back to the OS.
1488 // ==================================================================== //
1489 RegionReleaseRecorder<MemMapT> Recorder(&Region->MemMapInfo.MemMap,
1490 Region->RegionBeg,
1491 Context.getReleaseOffset());
1492 auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };
1493 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
1494 if (Recorder.getReleasedBytes() > 0) {
1495 // This is the case that we didn't hit the release threshold but it has
1496 // been past a certain period of time. Thus we try to release some pages
1497 // and if it does release some additional pages, it's hint that we are
1498 // able to lower the threshold. Currently, this case happens when the
1499 // `RegionPushedBytesDelta` is over half of the `TryReleaseThreshold`. As
1500 // a result, we shrink the threshold to half accordingly.
1501 // TODO(chiahungduan): Apply the same adjustment strategy to small blocks.
1502 if (!isSmallBlock(BlockSize)) {
1503 if (RegionPushedBytesDelta < Region->ReleaseInfo.TryReleaseThreshold &&
1504 Recorder.getReleasedBytes() >
1505 Region->ReleaseInfo.LastReleasedBytes +
1506 getMinReleaseAttemptSize(BlockSize)) {
1507 Region->ReleaseInfo.TryReleaseThreshold =
1508 Max(Region->ReleaseInfo.TryReleaseThreshold / 2,
1509 getMinReleaseAttemptSize(BlockSize));
1510 }
1511 }
1512
1513 Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;
1514 Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
1515 }
1516 Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTimeFast();
1517
1518 if (Region->ReleaseInfo.PendingPushedBytesDelta > 0) {
1519 // Instead of increasing the threshold by the amount of
1520 // `PendingPushedBytesDelta`, we only increase half of the amount so that
1521 // it won't be a leap (which may lead to higher memory pressure) because
1522 // of certain memory usage bursts which don't happen frequently.
1523 Region->ReleaseInfo.TryReleaseThreshold +=
1524 Region->ReleaseInfo.PendingPushedBytesDelta / 2;
1525 // This is another guard of avoiding the growth of threshold indefinitely.
1526 // Note that we may consider to make this configurable if we have a better
1527 // way to model this.
1528 Region->ReleaseInfo.TryReleaseThreshold = Min<uptr>(
1529 Region->ReleaseInfo.TryReleaseThreshold, (1UL << GroupSizeLog) / 2);
1530 Region->ReleaseInfo.PendingPushedBytesDelta = 0;
1531 }
1532
1533 // ====================================================================== //
1534 // 5. Merge the `GroupsToRelease` back to the freelist.
1535 // ====================================================================== //
1536 mergeGroupsToReleaseBack(Region, GroupsToRelease);
1537
1538 return Recorder.getReleasedBytes();
1539}
1540
1541template <typename Config>
1542bool SizeClassAllocator64<Config>::hasChanceToReleasePages(
1543 RegionInfo *Region, uptr BlockSize, uptr BytesInFreeList,
1544 ReleaseToOS ReleaseType) REQUIRES(Region->MMLock, Region->FLLock) {
1545 DCHECK_GE(Region->FreeListInfo.PoppedBlocks,
1546 Region->FreeListInfo.PushedBlocks);
1547 // Always update `BytesInFreeListAtLastCheckpoint` with the smallest value
1548 // so that we won't underestimate the releasable pages. For example, the
1549 // following is the region usage,
1550 //
1551 // BytesInFreeListAtLastCheckpoint AllocatedUser
1552 // v v
1553 // |--------------------------------------->
1554 // ^ ^
1555 // BytesInFreeList ReleaseThreshold
1556 //
1557 // In general, if we have collected enough bytes and the amount of free
1558 // bytes meets the ReleaseThreshold, we will try to do page release. If we
1559 // don't update `BytesInFreeListAtLastCheckpoint` when the current
1560 // `BytesInFreeList` is smaller, we may take longer time to wait for enough
1561 // freed blocks because we miss the bytes between
1562 // (BytesInFreeListAtLastCheckpoint - BytesInFreeList).
1563 if (BytesInFreeList <= Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint) {
1564 Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;
1565 }
1566
1567 const uptr RegionPushedBytesDelta =
1568 BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint;
1569
1570 if (ReleaseType == ReleaseToOS::Normal) {
1571 if (RegionPushedBytesDelta < Region->ReleaseInfo.TryReleaseThreshold / 2)
1572 return false;
1573
1574 const s64 IntervalMs = atomic_load_relaxed(A: &ReleaseToOsIntervalMs);
1575 if (IntervalMs < 0)
1576 return false;
1577
1578 const u64 IntervalNs = static_cast<u64>(IntervalMs) * 1000000;
1579 const u64 CurTimeNs = getMonotonicTimeFast();
1580 const u64 DiffSinceLastReleaseNs =
1581 CurTimeNs - Region->ReleaseInfo.LastReleaseAtNs;
1582
1583 // At here, `RegionPushedBytesDelta` is more than half of
1584 // `TryReleaseThreshold`. If the last release happened 2 release interval
1585 // before, we will still try to see if there's any chance to release some
1586 // memory even it doesn't exceed the threshold.
1587 if (RegionPushedBytesDelta < Region->ReleaseInfo.TryReleaseThreshold) {
1588 // We want the threshold to have a shorter response time to the variant
1589 // memory usage patterns. According to data collected during experiments
1590 // (which were done with 1, 2, 4, 8 intervals), `2` strikes the better
1591 // balance between the memory usage and number of page release attempts.
1592 if (DiffSinceLastReleaseNs < 2 * IntervalNs)
1593 return false;
1594 } else if (DiffSinceLastReleaseNs < IntervalNs) {
1595 // `TryReleaseThreshold` is capped by (1UL << GroupSizeLog) / 2). If
1596 // RegionPushedBytesDelta grows to twice the threshold, it implies some
1597 // huge deallocations have happened so we better try to release some
1598 // pages. Note this tends to happen for larger block sizes.
1599 if (RegionPushedBytesDelta > (1ULL << GroupSizeLog))
1600 return true;
1601
1602 // In this case, we are over the threshold but we just did some page
1603 // release in the same release interval. This is a hint that we may want
1604 // a higher threshold so that we can release more memory at once.
1605 // `TryReleaseThreshold` will be adjusted according to how many bytes
1606 // are not released, i.e., the `PendingPushedBytesdelta` here.
1607 // TODO(chiahungduan): Apply the same adjustment strategy to small
1608 // blocks.
1609 if (!isSmallBlock(BlockSize))
1610 Region->ReleaseInfo.PendingPushedBytesDelta = RegionPushedBytesDelta;
1611
1612 // Memory was returned recently.
1613 return false;
1614 }
1615 } // if (ReleaseType == ReleaseToOS::Normal)
1616
1617 return true;
1618}
1619
1620template <typename Config>
1621SinglyLinkedList<typename SizeClassAllocator64<Config>::BatchGroupT>
1622SizeClassAllocator64<Config>::collectGroupsToRelease(
1623 RegionInfo *Region, const uptr BlockSize, const uptr AllocatedUserEnd,
1624 const uptr CompactPtrBase) REQUIRES(Region->MMLock, Region->FLLock) {
1625 const uptr GroupSize = (1UL << GroupSizeLog);
1626 const uptr PageSize = getPageSizeCached();
1627 SinglyLinkedList<BatchGroupT> GroupsToRelease;
1628
1629 // We are examining each group and will take the minimum distance to the
1630 // release threshold as the next `TryReleaseThreshold`. Note that if the
1631 // size of free blocks has reached the release threshold, the distance to
1632 // the next release will be PageSize * SmallerBlockReleasePageDelta. See the
1633 // comment on `SmallerBlockReleasePageDelta` for more details.
1634 uptr MinDistToThreshold = GroupSize;
1635
1636 for (BatchGroupT *BG = Region->FreeListInfo.BlockList.front(),
1637 *Prev = nullptr;
1638 BG != nullptr;) {
1639 // Group boundary is always GroupSize-aligned from CompactPtr base. The
1640 // layout of memory groups is like,
1641 //
1642 // (CompactPtrBase)
1643 // #1 CompactPtrGroupBase #2 CompactPtrGroupBase ...
1644 // | | |
1645 // v v v
1646 // +-----------------------+-----------------------+
1647 // \ / \ /
1648 // --- GroupSize --- --- GroupSize ---
1649 //
1650 // After decompacting the CompactPtrGroupBase, we expect the alignment
1651 // property is held as well.
1652 const uptr BatchGroupBase =
1653 decompactGroupBase(Base: CompactPtrBase, CompactPtrGroupBase: BG->CompactPtrGroupBase);
1654 DCHECK_LE(Region->RegionBeg, BatchGroupBase);
1655 DCHECK_GE(AllocatedUserEnd, BatchGroupBase);
1656 DCHECK_EQ((Region->RegionBeg - BatchGroupBase) % GroupSize, 0U);
1657 // Batches are pushed in front of BG.Batches. The first one may
1658 // not have all caches used.
1659 const uptr NumBlocks = (BG->Batches.size() - 1) * BG->MaxCachedPerBatch +
1660 BG->Batches.front()->getCount();
1661 const uptr BytesInBG = NumBlocks * BlockSize;
1662
1663 if (BytesInBG <= BG->BytesInBGAtLastCheckpoint) {
1664 BG->BytesInBGAtLastCheckpoint = BytesInBG;
1665 Prev = BG;
1666 BG = BG->Next;
1667 continue;
1668 }
1669
1670 const uptr PushedBytesDelta = BytesInBG - BG->BytesInBGAtLastCheckpoint;
1671 if (PushedBytesDelta < getMinReleaseAttemptSize(BlockSize)) {
1672 Prev = BG;
1673 BG = BG->Next;
1674 continue;
1675 }
1676
1677 // Given the randomness property, we try to release the pages only if the
1678 // bytes used by free blocks exceed certain proportion of group size. Note
1679 // that this heuristic only applies when all the spaces in a BatchGroup
1680 // are allocated.
1681 if (isSmallBlock(BlockSize)) {
1682 const uptr BatchGroupEnd = BatchGroupBase + GroupSize;
1683 const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd
1684 ? GroupSize
1685 : AllocatedUserEnd - BatchGroupBase;
1686 const uptr ReleaseThreshold =
1687 (AllocatedGroupSize * (100 - 1U - BlockSize / 16U)) / 100U;
1688 const bool HighDensity = BytesInBG >= ReleaseThreshold;
1689 const bool MayHaveReleasedAll = NumBlocks >= (GroupSize / BlockSize);
1690 // If all blocks in the group are released, we will do range marking
1691 // which is fast. Otherwise, we will wait until we have accumulated
1692 // a certain amount of free memory.
1693 const bool ReachReleaseDelta =
1694 MayHaveReleasedAll
1695 ? true
1696 : PushedBytesDelta >= PageSize * SmallerBlockReleasePageDelta;
1697
1698 if (!HighDensity) {
1699 DCHECK_LE(BytesInBG, ReleaseThreshold);
1700 // The following is the usage of a memory group,
1701 //
1702 // BytesInBG ReleaseThreshold
1703 // / \ v
1704 // +---+---------------------------+-----+
1705 // | | | | |
1706 // +---+---------------------------+-----+
1707 // \ / ^
1708 // PushedBytesDelta GroupEnd
1709 MinDistToThreshold =
1710 Min(A: MinDistToThreshold,
1711 B: ReleaseThreshold - BytesInBG + PushedBytesDelta);
1712 } else {
1713 // If it reaches high density at this round, the next time we will try
1714 // to release is based on SmallerBlockReleasePageDelta
1715 MinDistToThreshold =
1716 Min(A: MinDistToThreshold, B: PageSize * SmallerBlockReleasePageDelta);
1717 }
1718
1719 if (!HighDensity || !ReachReleaseDelta) {
1720 Prev = BG;
1721 BG = BG->Next;
1722 continue;
1723 }
1724 }
1725
1726 // If `BG` is the first BatchGroupT in the list, we only need to advance
1727 // `BG` and call FreeListInfo.BlockList::pop_front(). No update is needed
1728 // for `Prev`.
1729 //
1730 // (BG) (BG->Next)
1731 // Prev Cur BG
1732 // | | |
1733 // v v v
1734 // nil +--+ +--+
1735 // |X | -> | | -> ...
1736 // +--+ +--+
1737 //
1738 // Otherwise, `Prev` will be used to extract the `Cur` from the
1739 // `FreeListInfo.BlockList`.
1740 //
1741 // (BG) (BG->Next)
1742 // Prev Cur BG
1743 // | | |
1744 // v v v
1745 // +--+ +--+ +--+
1746 // | | -> |X | -> | | -> ...
1747 // +--+ +--+ +--+
1748 //
1749 // After FreeListInfo.BlockList::extract(),
1750 //
1751 // Prev Cur BG
1752 // | | |
1753 // v v v
1754 // +--+ +--+ +--+
1755 // | |-+ |X | +->| | -> ...
1756 // +--+ | +--+ | +--+
1757 // +--------+
1758 //
1759 // Note that we need to advance before pushing this BatchGroup to
1760 // GroupsToRelease because it's a destructive operation.
1761
1762 BatchGroupT *Cur = BG;
1763 BG = BG->Next;
1764
1765 // Ideally, we may want to update this only after successful release.
1766 // However, for smaller blocks, each block marking is a costly operation.
1767 // Therefore, we update it earlier.
1768 // TODO: Consider updating this after releasing pages if `ReleaseRecorder`
1769 // can tell the released bytes in each group.
1770 Cur->BytesInBGAtLastCheckpoint = BytesInBG;
1771
1772 if (Prev != nullptr)
1773 Region->FreeListInfo.BlockList.extract(Prev, Cur);
1774 else
1775 Region->FreeListInfo.BlockList.pop_front();
1776 GroupsToRelease.push_back(Cur);
1777 }
1778
1779 // Only small blocks have the adaptive `TryReleaseThreshold`.
1780 if (isSmallBlock(BlockSize)) {
1781 // If the MinDistToThreshold is not updated, that means each memory group
1782 // may have only pushed less than a page size. In that case, just set it
1783 // back to normal.
1784 if (MinDistToThreshold == GroupSize)
1785 MinDistToThreshold = PageSize * SmallerBlockReleasePageDelta;
1786 Region->ReleaseInfo.TryReleaseThreshold = MinDistToThreshold;
1787 }
1788
1789 return GroupsToRelease;
1790}
1791
1792template <typename Config>
1793PageReleaseContext SizeClassAllocator64<Config>::markFreeBlocks(
1794 RegionInfo *Region, const uptr BlockSize, const uptr AllocatedUserEnd,
1795 const uptr CompactPtrBase, SinglyLinkedList<BatchGroupT> &GroupsToRelease)
1796 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {
1797 const uptr GroupSize = (1UL << GroupSizeLog);
1798 auto DecompactPtr = [CompactPtrBase, this](CompactPtrT CompactPtr) {
1799 return decompactPtrInternal(Base: CompactPtrBase, CompactPtr);
1800 };
1801
1802 const uptr ReleaseBase = decompactGroupBase(
1803 Base: CompactPtrBase, CompactPtrGroupBase: GroupsToRelease.front()->CompactPtrGroupBase);
1804 const uptr LastGroupEnd =
1805 Min(decompactGroupBase(Base: CompactPtrBase,
1806 CompactPtrGroupBase: GroupsToRelease.back()->CompactPtrGroupBase) +
1807 GroupSize,
1808 AllocatedUserEnd);
1809 // The last block may straddle the group boundary. Rounding up to BlockSize
1810 // to get the exact range.
1811 const uptr ReleaseEnd =
1812 roundUpSlow(LastGroupEnd - Region->RegionBeg, BlockSize) +
1813 Region->RegionBeg;
1814 const uptr ReleaseRangeSize = ReleaseEnd - ReleaseBase;
1815 const uptr ReleaseOffset = ReleaseBase - Region->RegionBeg;
1816
1817 PageReleaseContext Context(BlockSize, /*NumberOfRegions=*/1U,
1818 ReleaseRangeSize, ReleaseOffset);
1819 // We may not be able to do the page release in a rare case that we may
1820 // fail on PageMap allocation.
1821 if (UNLIKELY(!Context.ensurePageMapAllocated()))
1822 return Context;
1823
1824 for (BatchGroupT &BG : GroupsToRelease) {
1825 const uptr BatchGroupBase =
1826 decompactGroupBase(Base: CompactPtrBase, CompactPtrGroupBase: BG.CompactPtrGroupBase);
1827 const uptr BatchGroupEnd = BatchGroupBase + GroupSize;
1828 const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd
1829 ? GroupSize
1830 : AllocatedUserEnd - BatchGroupBase;
1831 const uptr BatchGroupUsedEnd = BatchGroupBase + AllocatedGroupSize;
1832 const bool MayContainLastBlockInRegion =
1833 BatchGroupUsedEnd == AllocatedUserEnd;
1834 const bool BlockAlignedWithUsedEnd =
1835 (BatchGroupUsedEnd - Region->RegionBeg) % BlockSize == 0;
1836
1837 uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize;
1838 if (!BlockAlignedWithUsedEnd)
1839 ++MaxContainedBlocks;
1840
1841 const uptr NumBlocks = (BG.Batches.size() - 1) * BG.MaxCachedPerBatch +
1842 BG.Batches.front()->getCount();
1843
1844 if (NumBlocks == MaxContainedBlocks) {
1845 for (const auto &It : BG.Batches) {
1846 if (&It != BG.Batches.front())
1847 DCHECK_EQ(It.getCount(), BG.MaxCachedPerBatch);
1848 for (u16 I = 0; I < It.getCount(); ++I)
1849 DCHECK_EQ(compactPtrGroup(It.get(I)), BG.CompactPtrGroupBase);
1850 }
1851
1852 Context.markRangeAsAllCounted(From: BatchGroupBase, To: BatchGroupUsedEnd,
1853 Base: Region->RegionBeg, /*RegionIndex=*/RegionIndex: 0,
1854 RegionSize: Region->MemMapInfo.AllocatedUser);
1855 } else {
1856 DCHECK_LT(NumBlocks, MaxContainedBlocks);
1857 // Note that we don't always visit blocks in each BatchGroup so that we
1858 // may miss the chance of releasing certain pages that cross
1859 // BatchGroups.
1860 Context.markFreeBlocksInRegion(
1861 BG.Batches, DecompactPtr, Region->RegionBeg, /*RegionIndex=*/0,
1862 Region->MemMapInfo.AllocatedUser, MayContainLastBlockInRegion);
1863 }
1864 }
1865
1866 DCHECK(Context.hasBlockMarked());
1867
1868 return Context;
1869}
1870
1871template <typename Config>
1872void SizeClassAllocator64<Config>::mergeGroupsToReleaseBack(
1873 RegionInfo *Region, SinglyLinkedList<BatchGroupT> &GroupsToRelease)
1874 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {
1875 ScopedLock L(Region->FLLock);
1876
1877 // After merging two freelists, we may have redundant `BatchGroup`s that
1878 // need to be recycled. The number of unused `BatchGroup`s is expected to be
1879 // small. Pick a constant which is inferred from real programs.
1880 constexpr uptr MaxUnusedSize = 8;
1881 CompactPtrT Blocks[MaxUnusedSize];
1882 u32 Idx = 0;
1883 RegionInfo *BatchClassRegion = getRegionInfo(ClassId: SizeClassMap::BatchClassId);
1884 // We can't call pushBatchClassBlocks() to recycle the unused `BatchGroup`s
1885 // when we are manipulating the freelist of `BatchClassRegion`. Instead, we
1886 // should just push it back to the freelist when we merge two `BatchGroup`s.
1887 // This logic hasn't been implemented because we haven't supported releasing
1888 // pages in `BatchClassRegion`.
1889 DCHECK_NE(BatchClassRegion, Region);
1890
1891 // Merge GroupsToRelease back to the Region::FreeListInfo.BlockList. Note
1892 // that both `Region->FreeListInfo.BlockList` and `GroupsToRelease` are
1893 // sorted.
1894 for (BatchGroupT *BG = Region->FreeListInfo.BlockList.front(),
1895 *Prev = nullptr;
1896 ;) {
1897 if (BG == nullptr || GroupsToRelease.empty()) {
1898 if (!GroupsToRelease.empty())
1899 Region->FreeListInfo.BlockList.append_back(&GroupsToRelease);
1900 break;
1901 }
1902
1903 DCHECK(!BG->Batches.empty());
1904
1905 if (BG->CompactPtrGroupBase <
1906 GroupsToRelease.front()->CompactPtrGroupBase) {
1907 Prev = BG;
1908 BG = BG->Next;
1909 continue;
1910 }
1911
1912 BatchGroupT *Cur = GroupsToRelease.front();
1913 BatchT *UnusedBatch = nullptr;
1914 GroupsToRelease.pop_front();
1915
1916 if (BG->CompactPtrGroupBase == Cur->CompactPtrGroupBase) {
1917 // We have updated `BatchGroup::BytesInBGAtLastCheckpoint` while
1918 // collecting the `GroupsToRelease`.
1919 BG->BytesInBGAtLastCheckpoint = Cur->BytesInBGAtLastCheckpoint;
1920 const uptr MaxCachedPerBatch = BG->MaxCachedPerBatch;
1921
1922 // Note that the first Batches in both `Batches` may not be
1923 // full and only the first Batch can have non-full blocks. Thus
1924 // we have to merge them before appending one to another.
1925 if (Cur->Batches.front()->getCount() == MaxCachedPerBatch) {
1926 BG->Batches.append_back(&Cur->Batches);
1927 } else {
1928 BatchT *NonFullBatch = Cur->Batches.front();
1929 Cur->Batches.pop_front();
1930 const u16 NonFullBatchCount = NonFullBatch->getCount();
1931 // The remaining Batches in `Cur` are full.
1932 BG->Batches.append_back(&Cur->Batches);
1933
1934 if (BG->Batches.front()->getCount() == MaxCachedPerBatch) {
1935 // Only 1 non-full Batch, push it to the front.
1936 BG->Batches.push_front(NonFullBatch);
1937 } else {
1938 const u16 NumBlocksToMove = static_cast<u16>(
1939 Min(A: static_cast<u16>(MaxCachedPerBatch -
1940 BG->Batches.front()->getCount()),
1941 B: NonFullBatchCount));
1942 BG->Batches.front()->appendFromBatch(NonFullBatch, NumBlocksToMove);
1943 if (NonFullBatch->isEmpty())
1944 UnusedBatch = NonFullBatch;
1945 else
1946 BG->Batches.push_front(NonFullBatch);
1947 }
1948 }
1949
1950 const u32 NeededSlots = UnusedBatch == nullptr ? 1U : 2U;
1951 if (UNLIKELY(Idx + NeededSlots > MaxUnusedSize)) {
1952 ScopedLock L(BatchClassRegion->FLLock);
1953 pushBatchClassBlocks(Region: BatchClassRegion, Array: Blocks, Size: Idx);
1954 if (conditionVariableEnabled())
1955 BatchClassRegion->FLLockCV.notifyAll(BatchClassRegion->FLLock);
1956 Idx = 0;
1957 }
1958 Blocks[Idx++] =
1959 compactPtr(ClassId: SizeClassMap::BatchClassId, Ptr: reinterpret_cast<uptr>(Cur));
1960 if (UnusedBatch) {
1961 Blocks[Idx++] = compactPtr(ClassId: SizeClassMap::BatchClassId,
1962 Ptr: reinterpret_cast<uptr>(UnusedBatch));
1963 }
1964 Prev = BG;
1965 BG = BG->Next;
1966 continue;
1967 }
1968
1969 // At here, the `BG` is the first BatchGroup with CompactPtrGroupBase
1970 // larger than the first element in `GroupsToRelease`. We need to insert
1971 // `GroupsToRelease::front()` (which is `Cur` below) before `BG`.
1972 //
1973 // 1. If `Prev` is nullptr, we simply push `Cur` to the front of
1974 // FreeListInfo.BlockList.
1975 // 2. Otherwise, use `insert()` which inserts an element next to `Prev`.
1976 //
1977 // Afterwards, we don't need to advance `BG` because the order between
1978 // `BG` and the new `GroupsToRelease::front()` hasn't been checked.
1979 if (Prev == nullptr)
1980 Region->FreeListInfo.BlockList.push_front(Cur);
1981 else
1982 Region->FreeListInfo.BlockList.insert(Prev, Cur);
1983 DCHECK_EQ(Cur->Next, BG);
1984 Prev = Cur;
1985 }
1986
1987 if (Idx != 0) {
1988 ScopedLock L(BatchClassRegion->FLLock);
1989 pushBatchClassBlocks(Region: BatchClassRegion, Array: Blocks, Size: Idx);
1990 if (conditionVariableEnabled())
1991 BatchClassRegion->FLLockCV.notifyAll(BatchClassRegion->FLLock);
1992 }
1993
1994 if (SCUDO_DEBUG) {
1995 BatchGroupT *Prev = Region->FreeListInfo.BlockList.front();
1996 for (BatchGroupT *Cur = Prev->Next; Cur != nullptr;
1997 Prev = Cur, Cur = Cur->Next) {
1998 CHECK_LT(Prev->CompactPtrGroupBase, Cur->CompactPtrGroupBase);
1999 }
2000 }
2001
2002 if (conditionVariableEnabled())
2003 Region->FLLockCV.notifyAll(Region->FLLock);
2004}
2005} // namespace scudo
2006
2007#endif // SCUDO_PRIMARY64_H_
2008