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