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