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