[scudo] Manage free blocks in BatchGroup.

[Chia-hungDuan]

Summary

Scudo is supposed to allocate any blocks across the entired mapped
pages and each page is equally likely to be selected. Which means Scudo
is leaning to touch as many pages as possible. This brings better
security but it also sacrifices the chance of releasing dirty pages.

To alleviate the unmanagable footprint growing, this CL introduces the
BatchGroup concept. Each blocks will be classified into a BatchGroup
according to its address. While allocation, we are leaning to allocate
blocks in the same group first. Note that the blocks selected from a
group is still random over several pages. At the same time, we have
better prediction of dirty page growing speed. Besides, we are able to
do partial page releasing by examing part of BatchGroups.

[cryptoad]

Do we have rough numbers as to how this lowers the "randomness" of the pool of blocks to be chosen for various classes?

[Chia-hungDuan]

In D133897#3796176, @cryptoad wrote:

Do we have rough numbers as to how this lowers the "randomness" of the pool of blocks to be chosen for various classes?

AFK, I'll update the numbers later

[Chia-hungDuan]

I did the evaluation with these steps,

In each round,

1. It will do certain size allocation and have total 1 MB. (For example, for 128 size, it'll do 1 MB / 128 allocations)
2. Count the address difference between two consecutive allocations
3. Put the block to a set to keep track of number of different pointers
4. Release the blocks randomly

It does total 10 rounds and it has 6 threads run in parallel. The tables down below compare the "block-group" and "original".

1. There is almost the equivalent values in 64 bits configuration.
2. There's a little difference in number of difference pointers. The "original" has a little higher number of different pointers. This is expected because of in 32 bits config, the group size is the same as region size, which is 256 KB (it's 1 MB in 64 bits config). The address difference is almost the same

64 bits config
Size (block-group)	32	128	512	4096	16384	65536
# of diff ptrs	130289	29492	4794	677	140	61
# of allocs	327680	81920	20480	2560	640	160
Avg ptr diff	2615320	2178030	2244120	1587870	1653970	2276290
Size (original)	32	128	512	4096	16384	65536
# of diff ptrs	132252	30392	5667	565	150	51
# of allocs	327680	81920	20480	2560	640	160
Avg ptr diff	3537950	2336040	2516820	1797440	1658760	1283180

32 bits config
Size (block-group)	32	128	512	4096	16384	65536
# of diff ptrs	240012	22691	4108	548	146	50
# of allocs	327680	81920	20480	2560	640	160
Avg ptr diff	39993400	7481220	11188800	3472800	3500410	4181950
Size(original)	32	128	512	4096	16384	65536
# of diff ptrs	273159	23260	5239	792	172	57
# of allocs	327680	81920	20480	2560	640	160
Avg ptr diff	47288200	9131300	4941100	2481670	3232640	2864730

[cryptoad]

compiler-rt/lib/scudo/standalone/local_cache.h

32

Add a DCHECK that Count + N doesn't overflow a u16

compiler-rt/lib/scudo/standalone/primary32.h

445

AppendSize is a u32 while the argument to appendFromArray is a u16.
We might want to make sure it fits prior to truncating it.

compiler-rt/lib/scudo/standalone/primary64.h

449

Same u16 vs u32 comment

[Chia-hungDuan]

Fix type truncation error

compiler-rt/lib/scudo/standalone/local_cache.h

32

Use

DCHECK_LE(N, MaxNumCached - Count);

Count has been checked to be smaller or equal to MaxNumCached.

compiler-rt/lib/scudo/standalone/primary32.h

445

Sorry, my bad. Didn't include the fix in this CL.
AppendSize and Unused are u16, did the required static_cast here.

[abrachet]

compiler-rt/lib/scudo/standalone/local_cache.h

72

This fails on Fuchsia because TransferBatch::MaxNumCached = SizeClassMap::MaxNumCachedHint which on Fuchsia is 10, if I switch it to 13, like Android this passes. Is this static_assert necessary or alternatively is there a downside to moving up Fuchsia's MaxNumCachedHint?

[Chia-hungDuan]

compiler-rt/lib/scudo/standalone/local_cache.h

72

To reduce the complexity of support block grouping, BatchGroup and TransferBatch are using the same block so this static_assert is ensuring they can be put in the same block.

The impact of increasing the MaxNumCachedHint is
(1. it will slightly increase the memory used by TransferBatch (TransferBatch is used to record the free blocks in the free list), In general, this won't bring huge impact on memory usage and
(2. it may cache a little more free blocks in thread local.

Given that we don't change the number a lot. I think the impact will be very small. On Fuchsia, I think set it to 12 will pass the assertion.

I'll review the size used by TransferBatch and BatchGroup later and maybe we will find some savings.

Do you think it's fine for Fuchsia to set it as 12?

[abrachet]

compiler-rt/lib/scudo/standalone/local_cache.h

72

Do you think it's fine for Fuchsia to set it as 12?

Sure, done in rG2449f42427481518e3ca072d7d8db26c7020c3ce

[cferris]

Mostly a lot of small things.

There are some times I gave suggestions for wording changes in comments, so whatever you do, make sure it matches the same/similar comment in primary32.h and primary64.h.

compiler-rt/lib/scudo/standalone/allocator_config.h

38

addresses

compiler-rt/lib/scudo/standalone/local_cache.h

146

Probably worth wrapping in an UNLIKELY().

153

Same as above, wrap in UNLIKELY()

compiler-rt/lib/scudo/standalone/primary32.h

125

Wrap in UNLIKELY()

143

Looks like a tab snuck in here.

157

Make sure to file a bug for this.

160

belonging

163

Should this be u16? Same for J? I don't think it really matters since you are only using them as array indices, so feel free to ignore.

385

from the same

391

most cases will fall

392

Did you mean "sooner or later"?

392

In that case,

393

worth sorting the array with the

396

Slightly awkward, maybe better as:

The region mutex needs to be held while calling this method.

435

Should this be u16?

437

This is a slightly confusing name since unused can mean the variable is unused. Would it be better to call it UnusedBatches?

456

Can this return nullptr?

489

As before, should these be u16? Same for the loop variable below?

518

As above, might be better worded as:

The region mutex needs to be held while calling this method.

But this is more of an opinion, so take it or leave it.

537

allocating

599–604

Given that it only happens

601

"treat" might be a better wording of this.

compiler-rt/lib/scudo/standalone/primary64.h

105

Add UNLIKELY

106

Another candidate for UNLIKELY.

124

Constructing

127

a recursive

I believe this is a duplicate comment, so make sure the two locations are the same.

140

belonging

438

As above, should this be u16?

440

As above, maybe "UnusedBlocks" to be clear about what this variable represents.

494

u16? As well as the I variable below?

520

the smallest

543

allocating

614

it only happens

615

treat

compiler-rt/lib/scudo/standalone/tests/combined_test.cpp

551

Extra line.

compiler-rt/lib/scudo/standalone/tests/primary_test.cpp

337

times the

340

the

341

isn't

344

cross

350

This is going to cause the test to run slightly different every time. I don't know if that matters too much, but sometimes we use a known seed so the test always runs the same.

I'm not sure if that's necessary here, but something to think about.

357

including

[Chia-hungDuan]

Address review comment

compiler-rt/lib/scudo/standalone/primary32.h

163

This is for pushing blocks, so theoretically we accept a larger number of blocks to be reported at once and we will split them out into different TransferBatch according to the size of TransferBatch.

So I don't use u16 which is specific to mean size in TransferBatch.

392

Sorry I wanted to say "later soon". We call popBlocks right after populateFreeList, so the blocks are supposed to be popped soon

435

Same reason as above. u16 is only used by TransferBatch. We can push a number of blocks which exceed u16 and we will handle it properly. In reality, we don't.

437

Use "UnusedSlots" instead. It means the unused slots in a batch.

456

If it's supposed to return nullptr, then the oom execption will have thrown. Do you think we need to add any comment here?

489

Same as above. The size for TransferBatch and "Array of blocks" can have different scale.

compiler-rt/lib/scudo/standalone/primary64.h

438

Same as above

440

Changed to UnusedSlots

494

Same as above

compiler-rt/lib/scudo/standalone/tests/primary_test.cpp

350

Got it. I follow the usage as in release_test and secondary_test. For our case, we expect the different seed should still give the expected result. So I think it's fine here.

[Chia-hungDuan]

compiler-rt/lib/scudo/standalone/primary32.h

157

Done. Filed in internal

[cferris]

Just a few more suggestions.

compiler-rt/lib/scudo/standalone/primary32.h

392

Probably better to remove the later, and leave it as "to be popped soon."

393

I think this nit got missed.

456

No, if this aborts, then leaving it like this is fine.

[Chia-hungDuan]

Address review comment

[Chia-hungDuan]

Mark comments as done.

[cferris]

LGTM

Any other reviewers, please take a quick look to make everything looks okay. If you feel that you might not understand all of the deeper changes, we'd still appreciate a higher level review to make sure there are no obvious errors.

[nemanjai]

It would seem that either this commit or the commit for https://reviews.llvm.org/D134226 has caused terrible instability on a number of PPC bots:
https://lab.llvm.org/buildbot/#/builders/231/builds/3768
https://lab.llvm.org/buildbot/#/builders/230/builds/3987
https://lab.llvm.org/buildbot/#/builders/121/builds/24139

Do you know what the issue might be? It doesn't seem consistent on all the bots.

compiler-rt/lib/scudo/standalone/allocator_config.h

 //   // SizeClasMmap to use with the Primary.
 //   using SizeClassMap = DefaultSizeClassMap;
 //   // Indicates possible support for Memory Tagging.
 //   static const bool MaySupportMemoryTagging = false;
 //   // Defines the Primary allocator to use.
 //   typedef SizeClassAllocator64<ExampleConfig> Primary;
 //   // Log2 of the size of a size class region, as used by the Primary.
 //   static const uptr PrimaryRegionSizeLog = 30U;
+//   // Log2 of the size of block group, as used by the Primary. Each group
+//   // contains a range of memory address, blocks in the range will belong to
+//   // the same group. In general, single region may have 1 or 2MB group size.
+//   // Multiple regions will have the group size equal to the region size
+//   // because the region size is usually smaller than 1 MB.
+//   // Smaller value gives fine-grained control of memory usage but the trade
+//   // off is that it may take longer time of deallocation.
+//   static const uptr PrimaryGroupSizeLog = 20U;
 //   // Defines the type and scale of a compact pointer. A compact pointer can
 //   // be understood as the offset of a pointer within the region it belongs
 //   // to, in increments of a power-of-2 scale.
 //   // eg: Ptr = Base + (CompactPtr << Scale).
 //   typedef u32 PrimaryCompactPtrT;
 //   static const uptr PrimaryCompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG;
 //   // Indicates support for offsetting the start of a region by
 //   // a random number of pages. Only used with primary64.

 
 struct DefaultConfig {
   using SizeClassMap = DefaultSizeClassMap;
   static const bool MaySupportMemoryTagging = true;
 
 #if SCUDO_CAN_USE_PRIMARY64
   typedef SizeClassAllocator64<DefaultConfig> Primary;
   static const uptr PrimaryRegionSizeLog = 32U;
+  static const uptr PrimaryGroupSizeLog = 21U;
   typedef uptr PrimaryCompactPtrT;
   static const uptr PrimaryCompactPtrScale = 0;
   static const bool PrimaryEnableRandomOffset = true;
   static const uptr PrimaryMapSizeIncrement = 1UL << 18;
 #else
   typedef SizeClassAllocator32<DefaultConfig> Primary;
   static const uptr PrimaryRegionSizeLog = 19U;
+  static const uptr PrimaryGroupSizeLog = 19U;
   typedef uptr PrimaryCompactPtrT;
 #endif
   static const s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
   static const s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
 
   typedef MapAllocatorCache<DefaultConfig> SecondaryCache;
   static const u32 SecondaryCacheEntriesArraySize = 32U;
   static const u32 SecondaryCacheQuarantineSize = 0U;
   static const u32 SecondaryCacheDefaultMaxEntriesCount = 32U;
   static const uptr SecondaryCacheDefaultMaxEntrySize = 1UL << 19;
   static const s32 SecondaryCacheMinReleaseToOsIntervalMs = INT32_MIN;
   static const s32 SecondaryCacheMaxReleaseToOsIntervalMs = INT32_MAX;
 
   template <class A> using TSDRegistryT = TSDRegistryExT<A>; // Exclusive
 };
 struct AndroidConfig {
   using SizeClassMap = AndroidSizeClassMap;
   static const bool MaySupportMemoryTagging = true;
 
 #if SCUDO_CAN_USE_PRIMARY64
   typedef SizeClassAllocator64<AndroidConfig> Primary;
   static const uptr PrimaryRegionSizeLog = 28U;
   typedef u32 PrimaryCompactPtrT;
   static const uptr PrimaryCompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG;
+  static const uptr PrimaryGroupSizeLog = 20U;
   static const bool PrimaryEnableRandomOffset = true;
   static const uptr PrimaryMapSizeIncrement = 1UL << 18;
 #else
   typedef SizeClassAllocator32<AndroidConfig> Primary;
   static const uptr PrimaryRegionSizeLog = 18U;
+  static const uptr PrimaryGroupSizeLog = 18U;
   typedef uptr PrimaryCompactPtrT;
 #endif
   static const s32 PrimaryMinReleaseToOsIntervalMs = 1000;
   static const s32 PrimaryMaxReleaseToOsIntervalMs = 1000;
 
   typedef MapAllocatorCache<AndroidConfig> SecondaryCache;
   static const u32 SecondaryCacheEntriesArraySize = 256U;
   static const u32 SecondaryCacheQuarantineSize = 32U;
struct AndroidSvelteConfig {
   using SizeClassMap = SvelteSizeClassMap;
   static const bool MaySupportMemoryTagging = false;
 
 #if SCUDO_CAN_USE_PRIMARY64
   typedef SizeClassAllocator64<AndroidSvelteConfig> Primary;
   static const uptr PrimaryRegionSizeLog = 27U;
   typedef u32 PrimaryCompactPtrT;
   static const uptr PrimaryCompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG;
+  static const uptr PrimaryGroupSizeLog = 18U;
   static const bool PrimaryEnableRandomOffset = true;
   static const uptr PrimaryMapSizeIncrement = 1UL << 18;
 #else
   typedef SizeClassAllocator32<AndroidSvelteConfig> Primary;
   static const uptr PrimaryRegionSizeLog = 16U;
+  static const uptr PrimaryGroupSizeLog = 16U;
   typedef uptr PrimaryCompactPtrT;
 #endif
   static const s32 PrimaryMinReleaseToOsIntervalMs = 1000;
   static const s32 PrimaryMaxReleaseToOsIntervalMs = 1000;
 
   typedef MapAllocatorCache<AndroidSvelteConfig> SecondaryCache;
   static const u32 SecondaryCacheEntriesArraySize = 16U;
   static const u32 SecondaryCacheQuarantineSize = 32U;
   static const u32 SecondaryCacheDefaultMaxEntriesCount = 4U;
   static const uptr SecondaryCacheDefaultMaxEntrySize = 1UL << 18;
   static const s32 SecondaryCacheMinReleaseToOsIntervalMs = 0;
   static const s32 SecondaryCacheMaxReleaseToOsIntervalMs = 0;
 
   template <class A>
   using TSDRegistryT = TSDRegistrySharedT<A, 2U, 1U>; // Shared, max 2 TSDs.
 };
 
 #if SCUDO_CAN_USE_PRIMARY64
 struct FuchsiaConfig {
   using SizeClassMap = FuchsiaSizeClassMap;
   static const bool MaySupportMemoryTagging = false;
 
   typedef SizeClassAllocator64<FuchsiaConfig> Primary;
   static const uptr PrimaryRegionSizeLog = 30U;
+  static const uptr PrimaryGroupSizeLog = 30U;
   typedef u32 PrimaryCompactPtrT;
   static const bool PrimaryEnableRandomOffset = true;
   static const uptr PrimaryMapSizeIncrement = 1UL << 18;
   static const uptr PrimaryCompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG;
   static const s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
   static const s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
 
   typedef MapAllocatorNoCache SecondaryCache;
   template <class A>
   using TSDRegistryT = TSDRegistrySharedT<A, 8U, 4U>; // Shared, max 8 TSDs.
 };
 
 struct TrustyConfig {
   using SizeClassMap = TrustySizeClassMap;
   static const bool MaySupportMemoryTagging = false;
 
   typedef SizeClassAllocator64<TrustyConfig> Primary;
   // Some apps have 1 page of heap total so small regions are necessary.
   static const uptr PrimaryRegionSizeLog = 10U;
+  static const uptr PrimaryGroupSizeLog = 10U;
   typedef u32 PrimaryCompactPtrT;
   static const bool PrimaryEnableRandomOffset = false;
   // Trusty is extremely memory-constrained so minimally round up map calls.
   static const uptr PrimaryMapSizeIncrement = 1UL << 4;
   static const uptr PrimaryCompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG;
   static const s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
   static const s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
 

compiler-rt/lib/scudo/standalone/list.h

template <class T> struct SinglyLinkedList : public IntrusiveList<T> {
   void pop_front() {
     DCHECK(!empty());
     First = First->Next;
     if (!First)
       Last = nullptr;
     Size--;
   }
 
+  // Insert X next to Prev
+  void insert(T *Prev, T *X) {
+    DCHECK(!empty());
+    DCHECK_NE(Prev, nullptr);
+    DCHECK_NE(X, nullptr);
+    X->Next = Prev->Next;
+    Prev->Next = X;
+    if (Last == Prev)
+      Last = X;
+    ++Size;
+  }
+
   void extract(T *Prev, T *X) {
     DCHECK(!empty());
     DCHECK_NE(Prev, nullptr);
     DCHECK_NE(X, nullptr);
     DCHECK_EQ(Prev->Next, X);
     Prev->Next = X->Next;
     if (Last == X)
       Last = Prev;

compiler-rt/lib/scudo/standalone/local_cache.h

 //===-- local_cache.h -------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SCUDO_LOCAL_CACHE_H_
 #define SCUDO_LOCAL_CACHE_H_
 
 #include "internal_defs.h"
+#include "list.h"
 #include "platform.h"
 #include "report.h"
 #include "stats.h"
 
 namespace scudo {
 
 template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache {
   typedef typename SizeClassAllocator::SizeClassMap SizeClassMap;
   typedef typename SizeClassAllocator::CompactPtrT CompactPtrT;
 
   struct TransferBatch {
     static const u16 MaxNumCached = SizeClassMap::MaxNumCachedHint;
     void setFromArray(CompactPtrT *Array, u16 N) {
       DCHECK_LE(N, MaxNumCached);
       Count = N;
       memcpy(Batch, Array, sizeof(Batch[0]) * Count);
     }
+    void appendFromArray(CompactPtrT *Array, u16 N) {
+      DCHECK_LE(Count + N, MaxNumCached);
+      memcpy(Batch + Count, Array, sizeof(Batch[0]) * N);
+      Count += N;
+    }
     void clear() { Count = 0; }
     void add(CompactPtrT P) {
       DCHECK_LT(Count, MaxNumCached);
       Batch[Count++] = P;
     }
     void copyToArray(CompactPtrT *Array) const {
       memcpy(Array, Batch, sizeof(Batch[0]) * Count);
     }
     u16 getCount() const { return Count; }
     CompactPtrT get(u16 I) const {
       DCHECK_LE(I, Count);
       return Batch[I];
     }
     static u16 getMaxCached(uptr Size) {
       return Min(MaxNumCached, SizeClassMap::getMaxCachedHint(Size));
     }
     TransferBatch *Next;
 
   private:
     CompactPtrT Batch[MaxNumCached];
     u16 Count;
   };
 
+  // A BatchGroup is used to collect blocks. Each group has a group id to
+  // identify the group kind of contained blocks.
+  struct BatchGroup {
+    // `Next` is used by IntrusiveList.
+    BatchGroup *Next;
+    // The identifier of each group
+    uptr GroupId;
+    // Cache value of TransferBatch::getMaxCached()
+    u16 MaxCachedPerBatch;
+    // Blocks are managed by TransferBatch in a list.
+    SinglyLinkedList<TransferBatch> Batches;
+  };
+
+  static_assert(sizeof(BatchGroup) <= sizeof(TransferBatch),
+                "BatchGroup uses the same class size as TransferBatch");
+
   void init(GlobalStats *S, SizeClassAllocator *A) {
     DCHECK(isEmpty());
     Stats.init();
     if (LIKELY(S))
       S->link(&Stats);
     Allocator = A;
   }
 
void drain() {
     while (PerClassArray[BatchClassId].Count > 0)
       drain(&PerClassArray[BatchClassId], BatchClassId);
     DCHECK(isEmpty());
   }
 
   TransferBatch *createBatch(uptr ClassId, void *B) {
     if (ClassId != BatchClassId)
       B = allocate(BatchClassId);
+    if (!B)
+      reportOutOfMemory(SizeClassAllocator::getSizeByClassId(BatchClassId));
     return reinterpret_cast<TransferBatch *>(B);
   }
 
+  BatchGroup *createGroup() {
+    void *Ptr = allocate(BatchClassId);
+    if (!Ptr)
+      reportOutOfMemory(SizeClassAllocator::getSizeByClassId(BatchClassId));
+    return reinterpret_cast<BatchGroup *>(Ptr);
+  }
+
   LocalStats &getStats() { return Stats; }
 
 private:
   static const uptr NumClasses = SizeClassMap::NumClasses;
   static const uptr BatchClassId = SizeClassMap::BatchClassId;
   struct alignas(SCUDO_CACHE_LINE_SIZE) PerClass {
     u16 Count;
     u16 MaxCount;
NOINLINE bool refill(PerClass *C, uptr ClassId) {
     B->copyToArray(C->Chunks);
     B->clear();
     destroyBatch(ClassId, B);
     return true;
   }
 
   NOINLINE void drain(PerClass *C, uptr ClassId) {
     const u16 Count = Min(static_cast<u16>(C->MaxCount / 2), C->Count);
-    TransferBatch *B =
-        createBatch(ClassId, Allocator->decompactPtr(ClassId, C->Chunks[0]));
-    if (UNLIKELY(!B))
-      reportOutOfMemory(SizeClassAllocator::getSizeByClassId(BatchClassId));
-    B->setFromArray(&C->Chunks[0], Count);
+    Allocator->pushBlocks(this, ClassId, &C->Chunks[0], Count);
     C->Count -= Count;
-    for (uptr I = 0; I < C->Count; I++)
+    for (u16 I = 0; I < C->Count; I++)
       C->Chunks[I] = C->Chunks[I + Count];
-    Allocator->pushBatch(ClassId, B);
   }
 };
 
 } // namespace scudo
 
 #endif // SCUDO_LOCAL_CACHE_H_

compiler-rt/lib/scudo/standalone/primary32.h

 //
 // Memory used by this allocator is never unmapped but can be partially
 // reclaimed if the platform allows for it.
 
 template <typename Config> class SizeClassAllocator32 {
 public:
   typedef typename Config::PrimaryCompactPtrT CompactPtrT;
   typedef typename Config::SizeClassMap SizeClassMap;
+  static const uptr GroupSizeLog = Config::PrimaryGroupSizeLog;
   // The bytemap can only track UINT8_MAX - 1 classes.
   static_assert(SizeClassMap::LargestClassId <= (UINT8_MAX - 1), "");
   // Regions should be large enough to hold the largest Block.
   static_assert((1UL << Config::PrimaryRegionSizeLog) >= SizeClassMap::MaxSize,
                 "");
   typedef SizeClassAllocator32<Config> ThisT;
   typedef SizeClassAllocatorLocalCache<ThisT> CacheT;
   typedef typename CacheT::TransferBatch TransferBatch;
+  typedef typename CacheT::BatchGroup BatchGroup;
 
   static uptr getSizeByClassId(uptr ClassId) {
     return (ClassId == SizeClassMap::BatchClassId)
                ? sizeof(TransferBatch)
                : SizeClassMap::getSizeByClassId(ClassId);
   }
 
   static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }
public:
   CompactPtrT compactPtr(UNUSED uptr ClassId, uptr Ptr) const {
     return static_cast<CompactPtrT>(Ptr);
   }
 
   void *decompactPtr(UNUSED uptr ClassId, CompactPtrT CompactPtr) const {
     return reinterpret_cast<void *>(static_cast<uptr>(CompactPtr));
   }
 
+  uptr compactPtrGroup(CompactPtrT CompactPtr) {
+    return CompactPtr >> GroupSizeLog;
+  }
+
   TransferBatch *popBatch(CacheT *C, uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     SizeClassInfo *Sci = getSizeClassInfo(ClassId);
     ScopedLock L(Sci->Mutex);
-    TransferBatch *B = Sci->FreeList.front();
-    if (B) {
-      Sci->FreeList.pop_front();
-    } else {
-      B = populateFreeList(C, ClassId, Sci);
-      if (UNLIKELY(!B))
+    TransferBatch *B = popBatchImpl(C, ClassId);
+    if (!B) {
+      if (!populateFreeList(C, ClassId, Sci))
         return nullptr;
+      B = popBatchImpl(C, ClassId);
+      // if `populateFreeList` succeeded, we are supposed to get free blocks.
+      DCHECK_NE(B, nullptr);
     }
-    DCHECK_GT(B->getCount(), 0);
     Sci->Stats.PoppedBlocks += B->getCount();
     return B;
   }
 
-  void pushBatch(uptr ClassId, TransferBatch *B) {
+  // Push the array of free blocks to the designated batch group.
+  void pushBlocks(CacheT *C, uptr ClassId, CompactPtrT *Array, u32 Size) {
     DCHECK_LT(ClassId, NumClasses);
-    DCHECK_GT(B->getCount(), 0);
+    DCHECK_GT(Size, 0);
+
     SizeClassInfo *Sci = getSizeClassInfo(ClassId);
+    if (ClassId == SizeClassMap::BatchClassId) {
       ScopedLock L(Sci->Mutex);
-    Sci->FreeList.push_front(B);
-    Sci->Stats.PushedBlocks += B->getCount();
+      // Construct a batch group in the free list will use two blocks in
+      // BatchClassId. If we are pushing BatchClassId blocks, we will use the
+      // blocks in the array directly (can't delegate local cache which will
+      // cause recursively allocation). However, The number of free blocks may
+      // be less than two. Therefore, populate the free list before inserting
+      // the blocks.
+      if (Size == 1 && !populateFreeList(C, ClassId, Sci))
+          return;
+      pushBlocksImpl(C, ClassId, Array, Size);
+      Sci->Stats.PushedBlocks += Size;
+      return;
+    }
+
+    // TODO(chiahungduan): Consider not doing grouping if the group size is not
+    // greater than the block size with a certain scale.
+
+    // Sort the blocks so that blocks belong to the same group can be pushed
+    // together.
+    bool SameGroup = true;
+    for (u32 I = 1; I < Size; ++I) {
+      CompactPtrT Cur = Array[I];
+      u32 J = I;
+      while (J > 0 && compactPtrGroup(Cur) < compactPtrGroup(Array[J - 1])) {
+        SameGroup = false;
+        Array[J] = Array[J - 1];
+        --J;
+      }
+      Array[J] = Cur;
+    }
+
+    ScopedLock L(Sci->Mutex);
+    pushBlocksImpl(C, ClassId, Array, Size, SameGroup);
+
+    Sci->Stats.PushedBlocks += Size;
     if (ClassId != SizeClassMap::BatchClassId)
       releaseToOSMaybe(Sci, ClassId);
   }
 
   void disable() {
     // The BatchClassId must be locked last since other classes can use it.
     for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {
       if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)
struct ReleaseToOsInfo {
     uptr PushedBlocksAtLastRelease;
     uptr RangesReleased;
     uptr LastReleasedBytes;
     u64 LastReleaseAtNs;
   };
 
   struct alignas(SCUDO_CACHE_LINE_SIZE) SizeClassInfo {
     HybridMutex Mutex;
-    SinglyLinkedList<TransferBatch> FreeList;
+    SinglyLinkedList<BatchGroup> FreeList;
     uptr CurrentRegion;
     uptr CurrentRegionAllocated;
     SizeClassStats Stats;
     u32 RandState;
     uptr AllocatedUser;
     // Lowest & highest region index allocated for this size class, to avoid
     // looping through the whole NumRegions.
     uptr MinRegionIndex;
uptr allocateRegion(SizeClassInfo *Sci, uptr ClassId) {
     return Region;
   }
 
   SizeClassInfo *getSizeClassInfo(uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     return &SizeClassInfoArray[ClassId];
   }
 
-  NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId,
-                                           SizeClassInfo *Sci) {
+  // Push the blocks to their batch group. The layout will be like,
+  //
+  // FreeList - > BG -> BG -> BG
+  //              |     |     |
+  //              v     v     v
+  //              TB    TB    TB
+  //              |
+  //              v
+  //              TB
+  //
+  // Each BlockGroup(BG) will associate with unique group id and the free blocks
+  // are managed by a list of TransferBatch(TB). To reduce the time of inserting
+  // blocks, BGs are sorted and the input `Array` are supposed to be sorted so
+  // that we can get better performance of maintaining sorted property.
+  // Use `SameGroup=true` to indicate that all blocks in the array are from same
+  // group then we will skip checking the group id of each block.
+  //
+  // Note that this aims to have a better management of dirty pages, i.e., the
+  // RSS usage won't grow indefinitely. There's an exception that we may not put
+  // a block to its associated group. While populating new blocks, we may have
+  // blocks cross different groups. However, most cases they fall into same
+  // group and they are supposed to be popped soon later. In such case, it's not
+  // worth to sort the array with almost-sorted property. Therefore, we use
+  // `SameGroup=true` instead.
+  //
+  // Calling this method needs to hold the region mutex.
+  void pushBlocksImpl(CacheT *C, uptr ClassId, CompactPtrT *Array, u32 Size,
+                      bool SameGroup = false) {
+    DCHECK_GT(Size, 0U);
+    SizeClassInfo *Sci = getSizeClassInfo(ClassId);
+
+    auto CreateGroup = [&](uptr GroupId) {
+      BatchGroup *BG = nullptr;
+      TransferBatch *TB = nullptr;
+      if (ClassId == SizeClassMap::BatchClassId) {
+        DCHECK_GE(Size, 2U);
+        BG = reinterpret_cast<BatchGroup *>(
+            decompactPtr(ClassId, Array[Size - 1]));
+        BG->Batches.clear();
+
+        TB = reinterpret_cast<TransferBatch *>(
+            decompactPtr(ClassId, Array[Size - 2]));
+        TB->clear();
+      } else {
+        BG = C->createGroup();
+        BG->Batches.clear();
+
+        TB = C->createBatch(ClassId, nullptr);
+        TB->clear();
+      }
+
+      BG->GroupId = GroupId;
+      BG->Batches.push_front(TB);
+      BG->MaxCachedPerBatch =
+          TransferBatch::getMaxCached(getSizeByClassId(ClassId));
+
+      return BG;
+    };
+
+    auto InsertBlocks = [&](BatchGroup *BG, CompactPtrT *Array, u32 Size) {
+      SinglyLinkedList<TransferBatch> &Batches = BG->Batches;
+      TransferBatch *CurBatch = Batches.front();
+      DCHECK_NE(CurBatch, nullptr);
+
+      for (u32 I = 0; I < Size;) {
+        DCHECK_GE(BG->MaxCachedPerBatch, CurBatch->getCount());
+        u32 Unused = BG->MaxCachedPerBatch - CurBatch->getCount();
+        if (Unused == 0) {
+          CurBatch = C->createBatch(ClassId, reinterpret_cast<void *>(
+              decompactPtr(ClassId, Array[I])));
+          CurBatch->clear();
+          Batches.push_front(CurBatch);
+          Unused = BG->MaxCachedPerBatch;
+        }
+        u32 AppendSize = Min(Unused, Size - I);
+        CurBatch->appendFromArray(&Array[I], AppendSize);
+        I += AppendSize;
+      }
+    };
+
+    BatchGroup *Cur = Sci->FreeList.front();
+
+    if (ClassId == SizeClassMap::BatchClassId) {
+      if (Cur == nullptr) {
+        // Don't need to classify BatchClassId.
+        Cur = CreateGroup(/*GroupId=*/0);
+        Sci->FreeList.push_front(Cur);
+      }
+      InsertBlocks(Cur, Array, Size);
+      return;
+    }
+
+    // In the following, `Cur` always points to the BatchGroup for blocks that
+    // will be pushed next. `Prev` is the element right before `Cur`.
+    BatchGroup *Prev = nullptr;
+
+    while (Cur != nullptr && compactPtrGroup(Array[0]) > Cur->GroupId) {
+      Prev = Cur;
+      Cur = Cur->Next;
+    }
+
+    if (Cur == nullptr || compactPtrGroup(Array[0]) != Cur->GroupId) {
+      Cur = CreateGroup(compactPtrGroup(Array[0]));
+      if (Prev == nullptr)
+        Sci->FreeList.push_front(Cur);
+      else
+        Sci->FreeList.insert(Prev, Cur);
+    }
+
+    // All the blocks are from the same group, just push without checking group
+    // id.
+    if (SameGroup) {
+      InsertBlocks(Cur, Array, Size);
+      return;
+    }
+
+    // The blocks are sorted by group id. Determine the segment of group and
+    // push them to their group together.
+    u32 Count = 1;
+    for (u32 I = 1; I < Size; ++I) {
+      if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I])) {
+        DCHECK_EQ(compactPtrGroup(Array[I - 1]), Cur->GroupId);
+        InsertBlocks(Cur, Array + I - Count, Count);
+
+        while (Cur != nullptr && compactPtrGroup(Array[I]) > Cur->GroupId) {
+          Prev = Cur;
+          Cur = Cur->Next;
+        }
+
+        if (Cur == nullptr || compactPtrGroup(Array[I]) != Cur->GroupId) {
+          Cur = CreateGroup(compactPtrGroup(Array[I]));
+          DCHECK_NE(Prev, nullptr);
+          Sci->FreeList.insert(Prev, Cur);
+        }
+
+        Count = 1;
+      } else {
+        ++Count;
+      }
+    }
+
+    InsertBlocks(Cur, Array + Size - Count, Count);
+  }
+
+  // Pop one TransferBatch from a BatchGroup. The BatchGroup with smallest group
+  // id will be considered first.
+  //
+  // Calling this method needs to hold the region mutex.
+  TransferBatch *popBatchImpl(CacheT *C, uptr ClassId) {
+    SizeClassInfo *Sci = getSizeClassInfo(ClassId);
+    if (Sci->FreeList.empty())
+      return nullptr;
+
+    SinglyLinkedList<TransferBatch> &Batches = Sci->FreeList.front()->Batches;
+    DCHECK(!Batches.empty());
+
+    TransferBatch *B = Batches.front();
+    Batches.pop_front();
+    DCHECK_NE(B, nullptr);
+    DCHECK_GT(B->getCount(), 0U);
+
+    if (Batches.empty()) {
+      BatchGroup *BG = Sci->FreeList.front();
+      Sci->FreeList.pop_front();
+
+      // We don't keep BatchGroup with zero blocks to avoid empty-checking while
+      // allocation. Note that block used by constructing BatchGroup is recorded
+      // as free blocks in the last element of BatchGroup::Batches. Which means,
+      // once we pop the last TransferBatch, the block is implicitly
+      // deallocated.
+      if (ClassId != SizeClassMap::BatchClassId)
+        C->deallocate(SizeClassMap::BatchClassId, BG);
+    }
+
+    return B;
+  }
+
+  NOINLINE bool populateFreeList(CacheT *C, uptr ClassId,
     uptr Region;
     uptr Offset;
     // If the size-class currently has a region associated to it, use it. The
     // newly created blocks will be located after the currently allocated memory
     // for that region (up to RegionSize). Otherwise, create a new region, where
     // the new blocks will be carved from the beginning.
     if (Sci->CurrentRegion) {
       Region = Sci->CurrentRegion;
       DCHECK_GT(Sci->CurrentRegionAllocated, 0U);
       Offset = Sci->CurrentRegionAllocated;
     } else {
       DCHECK_EQ(Sci->CurrentRegionAllocated, 0U);
       Region = allocateRegion(Sci, ClassId);
       if (UNLIKELY(!Region))
-        return nullptr;
+        return false;
       C->getStats().add(StatMapped, RegionSize);
       Sci->CurrentRegion = Region;
       Offset = 0;
     }
 
     const uptr Size = getSizeByClassId(ClassId);
     const u32 MaxCount = TransferBatch::getMaxCached(Size);
     DCHECK_GT(MaxCount, 0U);
NOINLINE bool populateFreeList(CacheT *C, uptr ClassId,
 
     uptr P = Region + Offset;
     for (u32 I = 0; I < NumberOfBlocks; I++, P += Size)
       ShuffleArray[I] = reinterpret_cast<CompactPtrT>(P);
     // No need to shuffle the batches size class.
     if (ClassId != SizeClassMap::BatchClassId)
       shuffle(ShuffleArray, NumberOfBlocks, &Sci->RandState);
     for (u32 I = 0; I < NumberOfBlocks;) {
-      TransferBatch *B =
-          C->createBatch(ClassId, reinterpret_cast<void *>(ShuffleArray[I]));
-      if (UNLIKELY(!B))
-        return nullptr;
       const u32 N = Min(MaxCount, NumberOfBlocks - I);
-      B->setFromArray(&ShuffleArray[I], N);
-      Sci->FreeList.push_back(B);
+      // Note that the N blocks here may have different group ids. Given that
+      // it's only happened when it crosses the group size boundary. Instead of
+      // sorting them, take them as same group here to avoid sorting the
+      // almost-sorted blocks.
+      pushBlocksImpl(C, ClassId, &ShuffleArray[I], N, /*SameGroup=*/true);
       I += N;
     }
-    TransferBatch *B = Sci->FreeList.front();
-    Sci->FreeList.pop_front();
-    DCHECK(B);
-    DCHECK_GT(B->getCount(), 0);
 
     const uptr AllocatedUser = Size * NumberOfBlocks;
     C->getStats().add(StatFree, AllocatedUser);
     DCHECK_LE(Sci->CurrentRegionAllocated + AllocatedUser, RegionSize);
     // If there is not enough room in the region currently associated to fit
     // more blocks, we deassociate the region by resetting CurrentRegion and
     // CurrentRegionAllocated. Otherwise, update the allocated amount.
     if (RegionSize - (Sci->CurrentRegionAllocated + AllocatedUser) < Size) {
       Sci->CurrentRegion = 0;
       Sci->CurrentRegionAllocated = 0;
     } else {
       Sci->CurrentRegionAllocated += AllocatedUser;
     }
     Sci->AllocatedUser += AllocatedUser;
 
-    return B;
+    return true;
   }
 
   void getStats(ScopedString *Str, uptr ClassId, uptr Rss) {
     SizeClassInfo *Sci = getSizeClassInfo(ClassId);
     if (Sci->AllocatedUser == 0)
       return;
     const uptr InUse = Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks;
     const uptr AvailableChunks = Sci->AllocatedUser / getSizeByClassId(ClassId);
NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
     const uptr NumberOfRegions = Last - First + 1U;
     ReleaseRecorder Recorder(Base);
     auto SkipRegion = [this, First, ClassId](uptr RegionIndex) {
       return (PossibleRegions[First + RegionIndex] - 1U) != ClassId;
     };
     auto DecompactPtr = [](CompactPtrT CompactPtr) {
       return reinterpret_cast<uptr>(CompactPtr);
     };
-    releaseFreeMemoryToOS(Sci->FreeList, RegionSize, NumberOfRegions, BlockSize,
-                          Recorder, DecompactPtr, SkipRegion);
+    PageReleaseContext Context(BlockSize, RegionSize, NumberOfRegions);
+    for (BatchGroup &BG : Sci->FreeList)
+      Context.markFreeBlocks(BG.Batches, DecompactPtr, Base);
+
+    releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
+
     if (Recorder.getReleasedRangesCount() > 0) {
       Sci->ReleaseInfo.PushedBlocksAtLastRelease = Sci->Stats.PushedBlocks;
       Sci->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
       Sci->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
       TotalReleasedBytes += Sci->ReleaseInfo.LastReleasedBytes;
     }
     Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
 

compiler-rt/lib/scudo/standalone/primary64.h

 //
 // The memory used by this allocator is never unmapped, but can be partially
 // released if the platform allows for it.
 
 template <typename Config> class SizeClassAllocator64 {
 public:
   typedef typename Config::PrimaryCompactPtrT CompactPtrT;
   static const uptr CompactPtrScale = Config::PrimaryCompactPtrScale;
+  static const uptr GroupSizeLog = Config::PrimaryGroupSizeLog;
   typedef typename Config::SizeClassMap SizeClassMap;
   typedef SizeClassAllocator64<Config> ThisT;
   typedef SizeClassAllocatorLocalCache<ThisT> CacheT;
   typedef typename CacheT::TransferBatch TransferBatch;
+  typedef typename CacheT::BatchGroup BatchGroup;
 
   static uptr getSizeByClassId(uptr ClassId) {
     return (ClassId == SizeClassMap::BatchClassId)
                ? roundUpTo(sizeof(TransferBatch), 1U << CompactPtrScale)
                : SizeClassMap::getSizeByClassId(ClassId);
   }
 
   static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }
if (PrimaryBase)
             &Data);
     PrimaryBase = 0U;
   }
 
   TransferBatch *popBatch(CacheT *C, uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     RegionInfo *Region = getRegionInfo(ClassId);
     ScopedLock L(Region->Mutex);
-    TransferBatch *B = Region->FreeList.front();
-    if (B) {
-      Region->FreeList.pop_front();
-    } else {
-      B = populateFreeList(C, ClassId, Region);
-      if (UNLIKELY(!B))
+    TransferBatch *B = popBatchImpl(C, ClassId);
+    if (!B) {
+      if (!populateFreeList(C, ClassId, Region))
         return nullptr;
+      B = popBatchImpl(C, ClassId);
+      // if `populateFreeList` succeeded, we are supposed to get free blocks.
+      DCHECK_NE(B, nullptr);
     }
-    DCHECK_GT(B->getCount(), 0);
     Region->Stats.PoppedBlocks += B->getCount();
     return B;
   }
 
-  void pushBatch(uptr ClassId, TransferBatch *B) {
-    DCHECK_GT(B->getCount(), 0);
+  // Push the array of free blocks to the designated batch group.
+  void pushBlocks(CacheT *C, uptr ClassId, CompactPtrT *Array, u32 Size) {
+    DCHECK_LT(ClassId, NumClasses);
+    DCHECK_GT(Size, 0);
+
     RegionInfo *Region = getRegionInfo(ClassId);
+    if (ClassId == SizeClassMap::BatchClassId) {
       ScopedLock L(Region->Mutex);
-    Region->FreeList.push_front(B);
-    Region->Stats.PushedBlocks += B->getCount();
+      // Construct a batch group in the free list will use two blocks in
+      // BatchClassId. If we are pushing BatchClassId blocks, we will use the
+      // blocks in the array directly (can't delegate local cache which will
+      // cause recursively allocation). However, The number of free blocks may
+      // be less than two. Therefore, populate the free list before inserting
+      // the blocks.
+      if (Size == 1 && UNLIKELY(!populateFreeList(C, ClassId, Region)))
+          return;
+      pushBlocksImpl(C, ClassId, Array, Size);
+      Region->Stats.PushedBlocks += Size;
+      return;
+    }
+
+    // TODO(chiahungduan): Consider not doing grouping if the group size is not
+    // greater than the block size with a certain scale.
+
+    // Sort the blocks so that blocks belong to the same group can be pushed
+    // together.
+    bool SameGroup = true;
+    for (u32 I = 1; I < Size; ++I) {
+      CompactPtrT Cur = Array[I];
+      u32 J = I;
+      while (J > 0 && compactPtrGroup(Cur) < compactPtrGroup(Array[J - 1])) {
+        SameGroup = false;
+        Array[J] = Array[J - 1];
+        --J;
+      }
+      Array[J] = Cur;
+    }
+
+    ScopedLock L(Region->Mutex);
+    pushBlocksImpl(C, ClassId, Array, Size, SameGroup);
+
+    Region->Stats.PushedBlocks += Size;
     if (ClassId != SizeClassMap::BatchClassId)
       releaseToOSMaybe(Region, ClassId);
   }
 
   void disable() {
     // The BatchClassId must be locked last since other classes can use it.
     for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {
       if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)
struct ReleaseToOsInfo {
     uptr PushedBlocksAtLastRelease;
     uptr RangesReleased;
     uptr LastReleasedBytes;
     u64 LastReleaseAtNs;
   };
 
   struct UnpaddedRegionInfo {
     HybridMutex Mutex;
-    SinglyLinkedList<TransferBatch> FreeList;
+    SinglyLinkedList<BatchGroup> FreeList;
     uptr RegionBeg = 0;
     RegionStats Stats = {};
     u32 RandState = 0;
     uptr MappedUser = 0;    // Bytes mapped for user memory.
     uptr AllocatedUser = 0; // Bytes allocated for user memory.
     MapPlatformData Data = {};
     ReleaseToOsInfo ReleaseInfo = {};
     bool Exhausted = false;
private:
   static CompactPtrT compactPtrInternal(uptr Base, uptr Ptr) {
     return static_cast<CompactPtrT>((Ptr - Base) >> CompactPtrScale);
   }
 
   static uptr decompactPtrInternal(uptr Base, CompactPtrT CompactPtr) {
     return Base + (static_cast<uptr>(CompactPtr) << CompactPtrScale);
   }
 
-  NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId,
+  static uptr compactPtrGroup(CompactPtrT CompactPtr) {
+    return CompactPtr >> (GroupSizeLog - CompactPtrScale);
+  }
+
+  // Push the blocks to their batch group. The layout will be like,
+  //
+  // FreeList - > BG -> BG -> BG
+  //              |     |     |
+  //              v     v     v
+  //              TB    TB    TB
+  //              |
+  //              v
+  //              TB
+  //
+  // Each BlockGroup(BG) will associate with unique group id and the free blocks
+  // are managed by a list of TransferBatch(TB). To reduce the time of inserting
+  // blocks, BGs are sorted and the input `Array` are supposed to be sorted so
+  // that we can get better performance of maintaining sorted property.
+  // Use `SameGroup=true` to indicate that all blocks in the array are from same
+  // group then we will skip checking the group id of each block.
+  //
+  // Note that this aims to have a better management of dirty pages, i.e., the
+  // RSS usage won't grow indefinitely. There's an exception that we may not put
+  // a block to its associated group. While populating new blocks, we may have
+  // blocks cross different groups. However, most cases they fall into same
+  // group and they are supposed to be popped soon later. In such case, it's not
+  // worth to sort the array with almost-sorted property. Therefore, we use
+  // `SameGroup=true` instead.
+  //
+  // Calling this method needs to hold the region mutex.
+  void pushBlocksImpl(CacheT *C, uptr ClassId, CompactPtrT *Array, u32 Size,
+                      bool SameGroup = false) {
+    DCHECK_GT(Size, 0U);
+    RegionInfo *Region = getRegionInfo(ClassId);
+
+    auto CreateGroup = [&](uptr GroupId) {
+      BatchGroup *BG = nullptr;
+      TransferBatch *TB = nullptr;
+      if (ClassId == SizeClassMap::BatchClassId) {
+        DCHECK_GE(Size, 2U);
+        BG = reinterpret_cast<BatchGroup *>(
+            decompactPtr(ClassId, Array[Size - 1]));
+        BG->Batches.clear();
+
+        TB = reinterpret_cast<TransferBatch *>(
+            decompactPtr(ClassId, Array[Size - 2]));
+        TB->clear();
+      } else {
+        BG = C->createGroup();
+        BG->Batches.clear();
+
+        TB = C->createBatch(ClassId, nullptr);
+        TB->clear();
+      }
+
+      BG->GroupId = GroupId;
+      BG->Batches.push_front(TB);
+      BG->MaxCachedPerBatch =
+          TransferBatch::getMaxCached(getSizeByClassId(ClassId));
+
+      return BG;
+    };
+
+    auto InsertBlocks = [&](BatchGroup *BG, CompactPtrT *Array, u32 Size) {
+      SinglyLinkedList<TransferBatch> &Batches = BG->Batches;
+      TransferBatch *CurBatch = Batches.front();
+      DCHECK_NE(CurBatch, nullptr);
+
+      for (u32 I = 0; I < Size;) {
+        DCHECK_GE(BG->MaxCachedPerBatch, CurBatch->getCount());
+        u32 Unused = BG->MaxCachedPerBatch - CurBatch->getCount();
+        if (Unused == 0) {
+          CurBatch = C->createBatch(ClassId, reinterpret_cast<void *>(
+              decompactPtr(ClassId, Array[I])));
+          CurBatch->clear();
+          Batches.push_front(CurBatch);
+          Unused = BG->MaxCachedPerBatch;
+        }
+        u32 AppendSize = Min(Unused, Size - I);
+        CurBatch->appendFromArray(&Array[I], AppendSize);
+        I += AppendSize;
+      }
+    };
+
+    BatchGroup *Cur = Region->FreeList.front();
+
+    if (ClassId == SizeClassMap::BatchClassId) {
+      if (Cur == nullptr) {
+        // Don't need to classify BatchClassId.
+        Cur = CreateGroup(/*GroupId=*/0);
+        Region->FreeList.push_front(Cur);
+      }
+      InsertBlocks(Cur, Array, Size);
+      return;
+    }
+
+    // In the following, `Cur` always points to the BatchGroup for blocks that
+    // will be pushed next. `Prev` is the element right before `Cur`.
+    BatchGroup *Prev = nullptr;
+
+    while (Cur != nullptr && compactPtrGroup(Array[0]) > Cur->GroupId) {
+      Prev = Cur;
+      Cur = Cur->Next;
+    }
+
+    if (Cur == nullptr || compactPtrGroup(Array[0]) != Cur->GroupId) {
+      Cur = CreateGroup(compactPtrGroup(Array[0]));
+      if (Prev == nullptr)
+        Region->FreeList.push_front(Cur);
+      else
+        Region->FreeList.insert(Prev, Cur);
+    }
+
+
+    // All the blocks are from the same group, just push without checking group
+    // id.
+    if (SameGroup) {
+      InsertBlocks(Cur, Array, Size);
+      return;
+    }
+
+    // The blocks are sorted by group id. Determine the segment of group and
+    // push them to their group together.
+    u32 Count = 1;
+    for (u32 I = 1; I < Size; ++I) {
+      if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I])) {
+        DCHECK_EQ(compactPtrGroup(Array[I - 1]), Cur->GroupId);
+        InsertBlocks(Cur, Array + I - Count, Count);
+
+        while (Cur != nullptr && compactPtrGroup(Array[I]) > Cur->GroupId) {
+          Prev = Cur;
+          Cur = Cur->Next;
+        }
+
+        if (Cur == nullptr || compactPtrGroup(Array[I]) != Cur->GroupId) {
+          Cur = CreateGroup(compactPtrGroup(Array[I]));
+          DCHECK_NE(Prev, nullptr);
+          Region->FreeList.insert(Prev, Cur);
+        }
+
+        Count = 1;
+      } else {
+        ++Count;
+      }
+    }
+
+    InsertBlocks(Cur, Array + Size - Count, Count);
+  }
+
+  // Pop one TransferBatch from a BatchGroup. The BatchGroup with smallest group
+  // id will be considered first.
+  //
+  // Calling this method needs to hold the region mutex.
+  TransferBatch *popBatchImpl(CacheT *C, uptr ClassId) {
+    RegionInfo *Region = getRegionInfo(ClassId);
+    if (Region->FreeList.empty())
+      return nullptr;
+
+    SinglyLinkedList<TransferBatch> &Batches =
+        Region->FreeList.front()->Batches;
+    DCHECK(!Batches.empty());
+
+    TransferBatch *B = Batches.front();
+    Batches.pop_front();
+    DCHECK_NE(B, nullptr);
+    DCHECK_GT(B->getCount(), 0U);
+
+    if (Batches.empty()) {
+      BatchGroup *BG = Region->FreeList.front();
+      Region->FreeList.pop_front();
+
+      // We don't keep BatchGroup with zero blocks to avoid empty-checking while
+      // allocation. Note that block used by constructing BatchGroup is recorded
+      // as free blocks in the last element of BatchGroup::Batches. Which means,
+      // once we pop the last TransferBatch, the block is implicitly
+      // deallocated.
+      if (ClassId != SizeClassMap::BatchClassId)
+        C->deallocate(SizeClassMap::BatchClassId, BG);
+    }
+
+    return B;
+  }
+
+
+  NOINLINE bool populateFreeList(CacheT *C, uptr ClassId,
                                            RegionInfo *Region) {
     const uptr Size = getSizeByClassId(ClassId);
     const u32 MaxCount = TransferBatch::getMaxCached(Size);
 
     const uptr RegionBeg = Region->RegionBeg;
     const uptr MappedUser = Region->MappedUser;
     const uptr TotalUserBytes = Region->AllocatedUser + MaxCount * Size;
     // Map more space for blocks, if necessary.
     if (TotalUserBytes > MappedUser) {
       // Do the mmap for the user memory.
       const uptr MapSize =
           roundUpTo(TotalUserBytes - MappedUser, MapSizeIncrement);
       const uptr RegionBase = RegionBeg - getRegionBaseByClassId(ClassId);
       if (UNLIKELY(RegionBase + MappedUser + MapSize > RegionSize)) {
         if (!Region->Exhausted) {
           Region->Exhausted = true;
           ScopedString Str;
           getStats(&Str);
           Str.append(
               "Scudo OOM: The process has exhausted %zuM for size class %zu.\n",
               RegionSize >> 20, Size);
           Str.output();
         }
-        return nullptr;
+        return false;
       }
       if (MappedUser == 0)
         Region->Data = Data;
       if (UNLIKELY(!map(
               reinterpret_cast<void *>(RegionBeg + MappedUser), MapSize,
               "scudo:primary",
               MAP_ALLOWNOMEM | MAP_RESIZABLE |
                   (useMemoryTagging<Config>(Options.load()) ? MAP_MEMTAG : 0),
-              &Region->Data)))
-        return nullptr;
+              &Region->Data))) {
+        return false;
+      }
       Region->MappedUser += MapSize;
       C->getStats().add(StatMapped, MapSize);
     }
 
     const u32 NumberOfBlocks = Min(
         MaxNumBatches * MaxCount,
         static_cast<u32>((Region->MappedUser - Region->AllocatedUser) / Size));
     DCHECK_GT(NumberOfBlocks, 0);
 
     constexpr u32 ShuffleArraySize =
         MaxNumBatches * TransferBatch::MaxNumCached;
     CompactPtrT ShuffleArray[ShuffleArraySize];
     DCHECK_LE(NumberOfBlocks, ShuffleArraySize);
 
     const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId);
     uptr P = RegionBeg + Region->AllocatedUser;
     for (u32 I = 0; I < NumberOfBlocks; I++, P += Size)
       ShuffleArray[I] = compactPtrInternal(CompactPtrBase, P);
     // No need to shuffle the batches size class.
     if (ClassId != SizeClassMap::BatchClassId)
       shuffle(ShuffleArray, NumberOfBlocks, &Region->RandState);
     for (u32 I = 0; I < NumberOfBlocks;) {
-      TransferBatch *B =
-          C->createBatch(ClassId, reinterpret_cast<void *>(decompactPtrInternal(
-                                      CompactPtrBase, ShuffleArray[I])));
-      if (UNLIKELY(!B))
-        return nullptr;
       const u32 N = Min(MaxCount, NumberOfBlocks - I);
-      B->setFromArray(&ShuffleArray[I], N);
-      Region->FreeList.push_back(B);
+      // Note that the N blocks here may have different group ids. Given that
+      // it's only happened when it crosses the group size boundary. Instead of
+      // sorting them, take them as same group here to avoid sorting the
+      // almost-sorted blocks.
+      pushBlocksImpl(C, ClassId, &ShuffleArray[I], N, /*SameGroup=*/true);
       I += N;
     }
-    TransferBatch *B = Region->FreeList.front();
-    Region->FreeList.pop_front();
-    DCHECK(B);
-    DCHECK_GT(B->getCount(), 0);
 
     const uptr AllocatedUser = Size * NumberOfBlocks;
     C->getStats().add(StatFree, AllocatedUser);
     Region->AllocatedUser += AllocatedUser;
 
-    return B;
+    return true;
   }
 
   void getStats(ScopedString *Str, uptr ClassId, uptr Rss) {
     RegionInfo *Region = getRegionInfo(ClassId);
     if (Region->MappedUser == 0)
       return;
     const uptr InUse = Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks;
     const uptr TotalChunks = Region->AllocatedUser / getSizeByClassId(ClassId);
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
     }
 
     ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data);
     const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId);
     auto DecompactPtr = [CompactPtrBase](CompactPtrT CompactPtr) {
       return decompactPtrInternal(CompactPtrBase, CompactPtr);
     };
     auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };
-    releaseFreeMemoryToOS(Region->FreeList, Region->AllocatedUser, 1U,
-                          BlockSize, Recorder, DecompactPtr, SkipRegion);
+    PageReleaseContext Context(BlockSize, RegionSize, /*NumberOfRegions=*/1U);
+    for (BatchGroup &BG : Region->FreeList)
+      Context.markFreeBlocks(BG.Batches, DecompactPtr, Region->RegionBeg);
+
+    releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
 
     if (Recorder.getReleasedRangesCount() > 0) {
       Region->ReleaseInfo.PushedBlocksAtLastRelease =
           Region->Stats.PushedBlocks;
       Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
       Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
     }
     Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
     return Recorder.getReleasedBytes();
   }
 };
 
 } // namespace scudo
 
 #endif // SCUDO_PRIMARY64_H_

compiler-rt/lib/scudo/standalone/tests/combined_test.cpp

struct DeathConfig {
   typedef scudo::SizeClassAllocator64<DeathConfig> Primary;
   static const scudo::uptr PrimaryRegionSizeLog = DeathRegionSizeLog;
   static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
   static const scudo::s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
   typedef scudo::uptr PrimaryCompactPtrT;
   static const scudo::uptr PrimaryCompactPtrScale = 0;
   static const bool PrimaryEnableRandomOffset = true;
   static const scudo::uptr PrimaryMapSizeIncrement = 1UL << 18;
+  static const scudo::uptr PrimaryGroupSizeLog = 18;
 
   typedef scudo::MapAllocatorNoCache SecondaryCache;
   template <class A> using TSDRegistryT = scudo::TSDRegistrySharedT<A, 1U, 1U>;
 };
 
 TEST(ScudoCombinedDeathTest, DeathCombined) {
   using AllocatorT = TestAllocator<DeathConfig>;
   auto Allocator = std::unique_ptr<AllocatorT>(new AllocatorT());
 
   const scudo::uptr Size = 1000U;
   void *P = Allocator->allocate(Size, Origin);
   EXPECT_NE(P, nullptr);
 
   // Invalid sized deallocation.
   EXPECT_DEATH(Allocator->deallocate(P, Origin, Size + 8U), "");
 
   // Misaligned pointer. Potentially unused if EXPECT_DEATH isn't available.
   UNUSED void *MisalignedP =
       reinterpret_cast<void *>(reinterpret_cast<scudo::uptr>(P) | 1U);
   EXPECT_DEATH(Allocator->deallocate(MisalignedP, Origin, Size), "");
   EXPECT_DEATH(Allocator->reallocate(MisalignedP, Size * 2U), "");
 
+
   // Header corruption.
   scudo::u64 *H =
       reinterpret_cast<scudo::u64 *>(scudo::Chunk::getAtomicHeader(P));
   *H ^= 0x42U;
   EXPECT_DEATH(Allocator->deallocate(P, Origin, Size), "");
   *H ^= 0x420042U;
   EXPECT_DEATH(Allocator->deallocate(P, Origin, Size), "");
   *H ^= 0x420000U;

compiler-rt/lib/scudo/standalone/tests/list_test.cpp

TEST(ScudoListTest, SinglyLinkedList) {
 
   L1.append_back(&L2);
   EXPECT_TRUE(L1.empty());
   EXPECT_TRUE(L2.empty());
 
   setList(&L1, X);
   checkList(&L1, X);
 
+  setList(&L1, X, Y);
+  L1.insert(X, Z);
+  checkList(&L1, X, Z, Y);
+
   setList(&L1, X, Y, Z);
   setList(&L2, A, B, C);
   L1.append_back(&L2);
   checkList(&L1, X, Y, Z, A, B, C);
   EXPECT_TRUE(L2.empty());
 
   L1.clear();
   L2.clear();

compiler-rt/lib/scudo/standalone/tests/primary_test.cpp

 //===-- primary_test.cpp ----------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "tests/scudo_unit_test.h"
 
 #include "primary32.h"
 #include "primary64.h"
 #include "size_class_map.h"
 
+#include <algorithm>
+#include <chrono>
 #include <condition_variable>
 #include <mutex>
+#include <random>
 #include <stdlib.h>
 #include <thread>
 #include <vector>
 
 // Note that with small enough regions, the SizeClassAllocator64 also works on
 // 32-bit architectures. It's not something we want to encourage, but we still
 // should ensure the tests pass.
 
 struct TestConfig1 {
   static const scudo::uptr PrimaryRegionSizeLog = 18U;
+  static const scudo::uptr PrimaryGroupSizeLog = 18U;
   static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
   static const scudo::s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
   static const bool MaySupportMemoryTagging = false;
   typedef scudo::uptr PrimaryCompactPtrT;
   static const scudo::uptr PrimaryCompactPtrScale = 0;
   static const bool PrimaryEnableRandomOffset = true;
   static const scudo::uptr PrimaryMapSizeIncrement = 1UL << 18;
 };
 
 struct TestConfig2 {
 #if defined(__mips__)
   // Unable to allocate greater size on QEMU-user.
   static const scudo::uptr PrimaryRegionSizeLog = 23U;
 #else
   static const scudo::uptr PrimaryRegionSizeLog = 24U;
 #endif
+  static const scudo::uptr PrimaryGroupSizeLog = 20U;
   static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
   static const scudo::s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
   static const bool MaySupportMemoryTagging = false;
   typedef scudo::uptr PrimaryCompactPtrT;
   static const scudo::uptr PrimaryCompactPtrScale = 0;
   static const bool PrimaryEnableRandomOffset = true;
   static const scudo::uptr PrimaryMapSizeIncrement = 1UL << 18;
 };
 
 struct TestConfig3 {
 #if defined(__mips__)
   // Unable to allocate greater size on QEMU-user.
   static const scudo::uptr PrimaryRegionSizeLog = 23U;
 #else
   static const scudo::uptr PrimaryRegionSizeLog = 24U;
 #endif
+  static const scudo::uptr PrimaryGroupSizeLog = 20U;
   static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
   static const scudo::s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
   static const bool MaySupportMemoryTagging = true;
   typedef scudo::uptr PrimaryCompactPtrT;
   static const scudo::uptr PrimaryCompactPtrScale = 0;
   static const bool PrimaryEnableRandomOffset = true;
   static const scudo::uptr PrimaryMapSizeIncrement = 1UL << 18;
 };
 
+struct TestConfig4 {
+#if defined(__mips__)
+  // Unable to allocate greater size on QEMU-user.
+  static const scudo::uptr PrimaryRegionSizeLog = 23U;
+#else
+  static const scudo::uptr PrimaryRegionSizeLog = 24U;
+#endif
+  static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
+  static const scudo::s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
+  static const bool MaySupportMemoryTagging = true;
+  static const scudo::uptr PrimaryCompactPtrScale = 3U;
+  static const scudo::uptr PrimaryGroupSizeLog = 20U;
+  typedef scudo::u32 PrimaryCompactPtrT;
+  static const bool PrimaryEnableRandomOffset = true;
+  static const scudo::uptr PrimaryMapSizeIncrement = 1UL << 18;
+};
+
 template <typename BaseConfig, typename SizeClassMapT>
 struct Config : public BaseConfig {
   using SizeClassMap = SizeClassMapT;
 };
 
 template <typename BaseConfig, typename SizeClassMapT>
 struct SizeClassAllocator
     : public scudo::SizeClassAllocator64<Config<BaseConfig, SizeClassMapT>> {};

 #if SCUDO_FUCHSIA
 #define SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME)                              \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig2)                            \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig3)
 #else
 #define SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME)                              \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig1)                            \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig2)                            \
-  SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig3)
+  SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig3)                            \
+  SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig4)
 #endif
 
 #define SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TYPE)                             \
   using FIXTURE##NAME##_##TYPE = FIXTURE##NAME<TYPE>;                          \
   TEST_F(FIXTURE##NAME##_##TYPE, NAME) { FIXTURE##NAME<TYPE>::Run(); }
 
 #define SCUDO_TYPED_TEST(FIXTURE, NAME)                                        \
   template <class TypeParam>                                                   \
struct SmallRegionsConfig {
   static const scudo::uptr PrimaryRegionSizeLog = 20U;
   static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
   static const scudo::s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
   static const bool MaySupportMemoryTagging = false;
   typedef scudo::uptr PrimaryCompactPtrT;
   static const scudo::uptr PrimaryCompactPtrScale = 0;
   static const bool PrimaryEnableRandomOffset = true;
   static const scudo::uptr PrimaryMapSizeIncrement = 1UL << 18;
+  static const scudo::uptr PrimaryGroupSizeLog = 20U;
 };
 
 // The 64-bit SizeClassAllocator can be easily OOM'd with small region sizes.
 // For the 32-bit one, it requires actually exhausting memory, so we skip it.
 TEST(ScudoPrimaryTest, Primary64OOM) {
   using Primary = scudo::SizeClassAllocator64<SmallRegionsConfig>;
   using TransferBatch = Primary::CacheT::TransferBatch;
   Primary Allocator;
   Allocator.init(/*ReleaseToOsInterval=*/-1);
   typename Primary::CacheT Cache;
   scudo::GlobalStats Stats;
   Stats.init();
   Cache.init(&Stats, &Allocator);
   bool AllocationFailed = false;
   std::vector<TransferBatch *> Batches;
   const scudo::uptr ClassId = Primary::SizeClassMap::LargestClassId;
   const scudo::uptr Size = Primary::getSizeByClassId(ClassId);
+  typename Primary::CacheT::CompactPtrT Blocks[TransferBatch::MaxNumCached];
+
   for (scudo::uptr I = 0; I < 10000U; I++) {
     TransferBatch *B = Allocator.popBatch(&Cache, ClassId);
     if (!B) {
       AllocationFailed = true;
       break;
     }
     for (scudo::u16 J = 0; J < B->getCount(); J++)
       memset(Allocator.decompactPtr(ClassId, B->get(J)), 'B', Size);
     Batches.push_back(B);
   }
   while (!Batches.empty()) {
-    Allocator.pushBatch(ClassId, Batches.back());
+    TransferBatch *B = Batches.back();
     Batches.pop_back();
+    B->copyToArray(Blocks);
+    Allocator.pushBlocks(&Cache, ClassId, Blocks, B->getCount());
+    Cache.deallocate(Primary::SizeClassMap::BatchClassId, B);
   }
   Cache.destroy(nullptr);
   Allocator.releaseToOS();
   scudo::ScopedString Str;
   Allocator.getStats(&Str);
   Str.output();
   EXPECT_EQ(AllocationFailed, true);
   Allocator.unmapTestOnly();
SCUDO_TYPED_TEST(ScudoPrimaryTest, ReleaseToOS) {
   EXPECT_TRUE(Primary::canAllocate(Size));
   const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
   void *P = Cache.allocate(ClassId);
   EXPECT_NE(P, nullptr);
   Cache.deallocate(ClassId, P);
   Cache.destroy(nullptr);
   EXPECT_GT(Allocator->releaseToOS(), 0U);
 }
+
+SCUDO_TYPED_TEST(ScudoPrimaryTest, MemoryGroup) {
+  using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;
+  std::unique_ptr<Primary> Allocator(new Primary);
+  Allocator->init(/*ReleaseToOsInterval=*/-1);
+  typename Primary::CacheT Cache;
+  Cache.init(nullptr, Allocator.get());
+  const scudo::uptr Size = 32U;
+  const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
+
+  // We will allocate 4 tims of group size memory and release all of them. We
+  // expect the free blocks will be classified with groups. Then we will
+  // allocate the same amount of memory as group size and expect the blocks will
+  // have the max address difference smaller or equal to 2 times of group size.
+  // Note that it doesn't necessary to be in the range of single group size
+  // because the way we get the group id is doing compact pointer shifting.
+  // According to configuration, the compact pointer may not align to group
+  // size. As a result, the blocks can across two groups at most.
+  const scudo::uptr GroupSizeMem = (1ULL << Primary::GroupSizeLog);
+  const scudo::uptr PeakAllocationMem = 4 * GroupSizeMem;
+  const scudo::uptr PeakNumberOfAllocations = PeakAllocationMem / Size;
+  const scudo::uptr FinalNumberOfAllocations = GroupSizeMem / Size;
+  std::vector<scudo::uptr> Blocks;
+  std::mt19937 R;
+
+  for (scudo::uptr I = 0; I < PeakNumberOfAllocations; ++I)
+    Blocks.push_back(reinterpret_cast<scudo::uptr>(Cache.allocate(ClassId)));
+
+  std::shuffle(Blocks.begin(), Blocks.end(), R);
+
+  // Release all the allocated blocks, include those held by local cache.
+  while (!Blocks.empty()) {
+    Cache.deallocate(ClassId, reinterpret_cast<void *>(Blocks.back()));
+    Blocks.pop_back();
+  }
+  Cache.drain();
+
+  for (scudo::uptr I = 0; I < FinalNumberOfAllocations; ++I)
+    Blocks.push_back(reinterpret_cast<scudo::uptr>(Cache.allocate(ClassId)));
+
+  EXPECT_LE(*std::max_element(Blocks.begin(), Blocks.end()) -
+            *std::min_element(Blocks.begin(), Blocks.end()), GroupSizeMem * 2);
+}