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