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

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