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