[scudo] Make the boundary of memory group aligned with region begin

[Chia-hungDuan]

Summary

This alignment guarantee enables simpler group range check while page
releasing and a potential optimization which is, now all the pointers
from the same group are also inth same region, that means the complexity
in markFreeBlocks() can be reduced as well.

[Chia-hungDuan]

Add one more context, on SizeClassAllocator64, now the pointer always gets compacted at least by using the offset from the region begin. This means the PrimaryCompactPtrT is able to use u32 in DefaultConfig as well. This will be done in later metadata size reduction work.

[cferris]

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

124–125

Would it be better to name this compactPtrGroupBase? And use Base instead of Beg for all of the variable names?

You use base in a few other places, and I think it makes it easier to understand the code since you are currently using both beg and base and sometimes comparing the values.

129–133

Since this function doesn't do anything, do you need it any more? Or do you want to keep it so that the primary32 and primary64 are the same?

[Chia-hungDuan]

1. Address review comment
2. Restrict (GroupSize == RegionSize) in SizeClassAllocator32 so that the logic of page releasing will be easier

[Chia-hungDuan]

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

124–125

Agree, done!

129–133

Right, it tries to align the style with primary64

[cferris]

Only a couple of nits.

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

65–66

base

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

374

What is RegionBeg? I think the names have changed so I'm not sure if this should be RegionSize instead?

[Chia-hungDuan]

Address review comment

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

374

Oops, forgot to update the log. Done.

[cferris]

LGTM

[Chia-hungDuan]

Rebase only

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

private:
     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;
+    // The compact base address of each group
+    uptr CompactPtrGroupBase;
     // Cache value of TransferBatch::getMaxCached()
     u16 MaxCachedPerBatch;
     // Number of blocks pushed into this group. This is an increment-only
     // counter.
     uptr PushedBlocks;
     // This is used to track how many blocks are pushed since last time we
     // checked `PushedBlocks`. It's useful for page releasing to determine the
     // usage of a BatchGroup.

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

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;
+  uptr compactPtrGroupBase(CompactPtrT CompactPtr) {
+    const uptr Mask = (static_cast<uptr>(1) << GroupSizeLog) - 1;
+    return CompactPtr & ~Mask;
   }
 
-  uptr batchGroupBase(uptr GroupId) { return GroupId << GroupSizeLog; }
+  uptr decompactGroupBase(uptr CompactPtrGroupBase) {
+    return CompactPtrGroupBase;
+  }
 
   TransferBatch *popBatch(CacheT *C, uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     SizeClassInfo *Sci = getSizeClassInfo(ClassId);
     ScopedLock L(Sci->Mutex);
     TransferBatch *B = popBatchImpl(C, ClassId, Sci);
     if (UNLIKELY(!B)) {
       if (UNLIKELY(!populateFreeList(C, ClassId, Sci)))
         return nullptr;
void pushBlocks(CacheT *C, uptr ClassId, CompactPtrT *Array, u32 Size) {
 
     // 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 belonging to the same group can be pushed
     // together.
     bool SameGroup = true;
     for (u32 I = 1; I < Size; ++I) {
-      if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I]))
+      if (compactPtrGroupBase(Array[I - 1]) != compactPtrGroupBase(Array[I]))
         SameGroup = false;
       CompactPtrT Cur = Array[I];
       u32 J = I;
-      while (J > 0 && compactPtrGroup(Cur) < compactPtrGroup(Array[J - 1])) {
+      while (J > 0 &&
+             compactPtrGroupBase(Cur) < compactPtrGroupBase(Array[J - 1])) {
         Array[J] = Array[J - 1];
         --J;
       }
       Array[J] = Cur;
     }
 
     ScopedLock L(Sci->Mutex);
     pushBlocksImpl(C, ClassId, Sci, Array, Size, SameGroup);
uptr allocateRegionSlow() {
     } else {
       Region = roundUp(MapBase, RegionSize);
       unmap(reinterpret_cast<void *>(MapBase), Region - MapBase);
       MapSize = RegionSize;
     }
     const uptr End = Region + MapSize;
     if (End != MapEnd)
       unmap(reinterpret_cast<void *>(End), MapEnd - End);
+
+    DCHECK_EQ(Region % RegionSize, 0U);
+    static_assert(Config::PrimaryRegionSizeLog == GroupSizeLog,
+                  "Memory group should be the same size as Region");
+
     return Region;
   }
 
   uptr allocateRegion(SizeClassInfo *Sci, uptr ClassId) REQUIRES(Sci->Mutex) {
     DCHECK_LT(ClassId, NumClasses);
     uptr Region = 0;
     {
       ScopedLock L(RegionsStashMutex);
private:
   // same group then we will skip checking the group id of each block.
   //
   // The region mutex needs to be held while calling this method.
   void pushBlocksImpl(CacheT *C, uptr ClassId, SizeClassInfo *Sci,
                       CompactPtrT *Array, u32 Size, bool SameGroup = false)
       REQUIRES(Sci->Mutex) {
     DCHECK_GT(Size, 0U);
 
-    auto CreateGroup = [&](uptr GroupId) {
+    auto CreateGroup = [&](uptr CompactPtrGroupBase) {
       BatchGroup *BG = nullptr;
       TransferBatch *TB = nullptr;
       if (ClassId == SizeClassMap::BatchClassId) {
         DCHECK_GE(Size, 2U);
 
         // Free blocks are recorded by TransferBatch in freelist, blocks of
         // BatchClassId are included. In order not to use additional memory to
         // record blocks of BatchClassId, they are self-contained. I.e., A
auto CreateGroup = [&](uptr CompactPtrGroupBase) {
       } else {
         BG = C->createGroup();
         BG->Batches.clear();
 
         TB = C->createBatch(ClassId, nullptr);
         TB->clear();
       }
 
-      BG->GroupId = GroupId;
+      BG->CompactPtrGroupBase = CompactPtrGroupBase;
       // TODO(chiahungduan): Avoid the use of push_back() in `Batches`.
       BG->Batches.push_front(TB);
       BG->PushedBlocks = 0;
       BG->PushedBlocksAtLastCheckpoint = 0;
       BG->MaxCachedPerBatch =
           TransferBatch::getMaxCached(getSizeByClassId(ClassId));
 
       return BG;
auto InsertBlocks = [&](BatchGroup *BG, CompactPtrT *Array, u32 Size) {
       BG->PushedBlocks += Size;
     };
 
     BatchGroup *Cur = Sci->FreeList.front();
 
     if (ClassId == SizeClassMap::BatchClassId) {
       if (Cur == nullptr) {
         // Don't need to classify BatchClassId.
-        Cur = CreateGroup(/*GroupId=*/0);
+        Cur = CreateGroup(/*CompactPtrGroupBase=*/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) {
+    while (Cur != nullptr &&
+           compactPtrGroupBase(Array[0]) > Cur->CompactPtrGroupBase) {
       Prev = Cur;
       Cur = Cur->Next;
     }
 
-    if (Cur == nullptr || compactPtrGroup(Array[0]) != Cur->GroupId) {
-      Cur = CreateGroup(compactPtrGroup(Array[0]));
+    if (Cur == nullptr ||
+        compactPtrGroupBase(Array[0]) != Cur->CompactPtrGroupBase) {
+      Cur = CreateGroup(compactPtrGroupBase(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) {
       for (u32 I = 0; I < Size; ++I)
-        DCHECK_EQ(compactPtrGroup(Array[I]), Cur->GroupId);
+        DCHECK_EQ(compactPtrGroupBase(Array[I]), Cur->CompactPtrGroupBase);
 
       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);
+      if (compactPtrGroupBase(Array[I - 1]) != compactPtrGroupBase(Array[I])) {
+        DCHECK_EQ(compactPtrGroupBase(Array[I - 1]), Cur->CompactPtrGroupBase);
         InsertBlocks(Cur, Array + I - Count, Count);
 
-        while (Cur != nullptr && compactPtrGroup(Array[I]) > Cur->GroupId) {
+        while (Cur != nullptr &&
+               compactPtrGroupBase(Array[I]) > Cur->CompactPtrGroupBase) {
           Prev = Cur;
           Cur = Cur->Next;
         }
 
-        if (Cur == nullptr || compactPtrGroup(Array[I]) != Cur->GroupId) {
-          Cur = CreateGroup(compactPtrGroup(Array[I]));
+        if (Cur == nullptr ||
+            compactPtrGroupBase(Array[I]) != Cur->CompactPtrGroupBase) {
+          Cur = CreateGroup(compactPtrGroupBase(Array[I]));
           DCHECK_NE(Prev, nullptr);
           Sci->FreeList.insert(Prev, Cur);
         }
 
         Count = 1;
       } else {
         ++Count;
       }
NOINLINE bool populateFreeList(CacheT *C, uptr ClassId, SizeClassInfo *Sci)
     DCHECK_LE(NumberOfBlocks, ShuffleArraySize);
 
     uptr P = Region + Offset;
     for (u32 I = 0; I < NumberOfBlocks; I++, P += Size)
       ShuffleArray[I] = reinterpret_cast<CompactPtrT>(P);
 
     if (ClassId != SizeClassMap::BatchClassId) {
       u32 N = 1;
-      uptr CurGroup = compactPtrGroup(ShuffleArray[0]);
+      uptr CurGroup = compactPtrGroupBase(ShuffleArray[0]);
       for (u32 I = 1; I < NumberOfBlocks; I++) {
-        if (UNLIKELY(compactPtrGroup(ShuffleArray[I]) != CurGroup)) {
+        if (UNLIKELY(compactPtrGroupBase(ShuffleArray[I]) != CurGroup)) {
           shuffle(ShuffleArray + I - N, N, &Sci->RandState);
           pushBlocksImpl(C, ClassId, Sci, ShuffleArray + I - N, N,
                          /*SameGroup=*/true);
           N = 1;
-          CurGroup = compactPtrGroup(ShuffleArray[I]);
+          CurGroup = compactPtrGroupBase(ShuffleArray[I]);
         } else {
           ++N;
         }
       }
 
       shuffle(ShuffleArray + NumberOfBlocks - N, N, &Sci->RandState);
       pushBlocksImpl(C, ClassId, Sci, &ShuffleArray[NumberOfBlocks - N], N,
                      /*SameGroup=*/true);
NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
     const uptr First = Sci->MinRegionIndex;
     const uptr Last = Sci->MaxRegionIndex;
     DCHECK_NE(Last, 0U);
     DCHECK_LE(First, Last);
     uptr TotalReleasedBytes = 0;
     const uptr Base = First * RegionSize;
     const uptr NumberOfRegions = Last - First + 1U;
     const uptr GroupSize = (1U << GroupSizeLog);
-    const uptr CurRegionGroupId =
-        compactPtrGroup(compactPtr(ClassId, Sci->CurrentRegion));
+    const uptr CurGroupBase =
+        compactPtrGroupBase(compactPtr(ClassId, Sci->CurrentRegion));
 
     ReleaseRecorder Recorder(Base);
     PageReleaseContext Context(BlockSize, RegionSize, NumberOfRegions,
                                /*ReleaseSize=*/RegionSize);
 
     auto DecompactPtr = [](CompactPtrT CompactPtr) {
       return reinterpret_cast<uptr>(CompactPtr);
     };
     for (BatchGroup &BG : Sci->FreeList) {
       const uptr PushedBytesDelta =
           BG.PushedBlocks - BG.PushedBlocksAtLastCheckpoint;
       if (PushedBytesDelta * BlockSize < PageSize)
         continue;
 
-      uptr AllocatedGroupSize = BG.GroupId == CurRegionGroupId
-                                    ? Sci->CurrentRegionAllocated
-                                    : GroupSize;
+      uptr AllocatedGroupSize =
+          decompactGroupBase(BG.CompactPtrGroupBase) == CurGroupBase
       if (AllocatedGroupSize == 0)
         continue;
 
       // TransferBatches are pushed in front of BG.Batches. The first one may
       // not have all caches used.
       const uptr NumBlocks = (BG.Batches.size() - 1) * BG.MaxCachedPerBatch +
                              BG.Batches.front()->getCount();
       const uptr BytesInBG = NumBlocks * BlockSize;
for (BatchGroup &BG : Sci->FreeList) {
       // range need to be from the same region. In SizeClassAllocator32, this is
       // true when GroupSize and RegionSize are the same. Another tricky case,
       // while range marking, the last block in a region needs the logic to mark
       // the last page. However, in SizeClassAllocator32, the RegionSize
       // recorded in PageReleaseContext may be different from
       // `CurrentRegionAllocated` of the current region. This exception excludes
       // the chance of doing range marking for the current region.
       const bool CanDoRangeMark =
-          GroupSize == RegionSize && BG.GroupId != CurRegionGroupId;
+          GroupSize == RegionSize &&
+          decompactGroupBase(BG.CompactPtrGroupBase) != CurGroupBase;
 
       if (CanDoRangeMark && NumBlocks == MaxContainedBlocks) {
         for (const auto &It : BG.Batches)
           for (u16 I = 0; I < It.getCount(); ++I)
-            DCHECK_EQ(compactPtrGroup(It.get(I)), BG.GroupId);
+            DCHECK_EQ(compactPtrGroupBase(It.get(I)), BG.CompactPtrGroupBase);
 
-        const uptr From = batchGroupBase(BG.GroupId);
-        const uptr To = batchGroupBase(BG.GroupId) + AllocatedGroupSize;
+        const uptr From = decompactGroupBase(BG.CompactPtrGroupBase);
+        const uptr To = From + AllocatedGroupSize;
         Context.markRangeAsAllCounted(From, To, Base);
       } else {
         if (CanDoRangeMark)
           DCHECK_LT(NumBlocks, MaxContainedBlocks);
 
         // Note that we don't always visit blocks in each BatchGroup so that we
         // may miss the chance of releasing certain pages that cross
         // BatchGroups.

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;
+  static const uptr GroupScale = GroupSizeLog - CompactPtrScale;
   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)
public:
 
   const char *getRegionInfoArrayAddress() const {
     return reinterpret_cast<const char *>(RegionInfoArray);
   }
 
   static uptr getRegionInfoArraySize() { return sizeof(RegionInfoArray); }
 
   uptr getCompactPtrBaseByClassId(uptr ClassId) {
-    // If we are not compacting pointers, base everything off of 0.
-    if (sizeof(CompactPtrT) == sizeof(uptr) && CompactPtrScale == 0)
-      return 0;
     return getRegionInfo(ClassId)->RegionBeg;
   }
 
   CompactPtrT compactPtr(uptr ClassId, uptr Ptr) {
     DCHECK_LE(ClassId, SizeClassMap::LargestClassId);
     return compactPtrInternal(getCompactPtrBaseByClassId(ClassId), Ptr);
   }
 
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);
   }
 
   static uptr compactPtrGroup(CompactPtrT CompactPtr) {
-    return static_cast<uptr>(CompactPtr) >> (GroupSizeLog - CompactPtrScale);
+    const uptr Mask = (static_cast<uptr>(1) << GroupScale) - 1;
+    return static_cast<uptr>(CompactPtr) & ~Mask;
   }
-  static uptr batchGroupBase(uptr Base, uptr GroupId) {
-    return (GroupId << GroupSizeLog) + Base;
+  static uptr decompactGroupBase(uptr Base, uptr CompactPtrGroupBase) {
+    DCHECK_EQ(CompactPtrGroupBase % (static_cast<uptr>(1) << (GroupScale)), 0U);
+    return Base + (CompactPtrGroupBase << CompactPtrScale);
   }
 
   // Push the blocks to their batch group. The layout will be like,
   //
   // FreeList - > BG -> BG -> BG
   //              |     |     |
   //              v     v     v
   //              TB    TB    TB
private:
   // same group then we will skip checking the group id of each block.
   //
   // The region mutex needs to be held while calling this method.
   void pushBlocksImpl(CacheT *C, uptr ClassId, RegionInfo *Region,
                       CompactPtrT *Array, u32 Size, bool SameGroup = false)
       REQUIRES(Region->Mutex) {
     DCHECK_GT(Size, 0U);
 
-    auto CreateGroup = [&](uptr GroupId) {
+    auto CreateGroup = [&](uptr CompactPtrGroupBase) {
       BatchGroup *BG = nullptr;
       TransferBatch *TB = nullptr;
       if (ClassId == SizeClassMap::BatchClassId) {
         DCHECK_GE(Size, 2U);
 
         // Free blocks are recorded by TransferBatch in freelist, blocks of
         // BatchClassId are included. In order not to use additional memory to
         // record blocks of BatchClassId, they are self-contained. I.e., A
auto CreateGroup = [&](uptr CompactPtrGroupBase) {
       } else {
         BG = C->createGroup();
         BG->Batches.clear();
 
         TB = C->createBatch(ClassId, nullptr);
         TB->clear();
       }
 
-      BG->GroupId = GroupId;
+      BG->CompactPtrGroupBase = CompactPtrGroupBase;
       // TODO(chiahungduan): Avoid the use of push_back() in `Batches`.
       BG->Batches.push_front(TB);
       BG->PushedBlocks = 0;
       BG->PushedBlocksAtLastCheckpoint = 0;
       BG->MaxCachedPerBatch =
           TransferBatch::getMaxCached(getSizeByClassId(ClassId));
 
       return BG;
auto InsertBlocks = [&](BatchGroup *BG, CompactPtrT *Array, u32 Size) {
       BG->PushedBlocks += Size;
     };
 
     BatchGroup *Cur = Region->FreeList.front();
 
     if (ClassId == SizeClassMap::BatchClassId) {
       if (Cur == nullptr) {
         // Don't need to classify BatchClassId.
-        Cur = CreateGroup(/*GroupId=*/0);
+        Cur = CreateGroup(/*CompactPtrGroupBase=*/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) {
+    while (Cur != nullptr &&
+           compactPtrGroup(Array[0]) > Cur->CompactPtrGroupBase) {
       Prev = Cur;
       Cur = Cur->Next;
     }
 
-    if (Cur == nullptr || compactPtrGroup(Array[0]) != Cur->GroupId) {
+    if (Cur == nullptr ||
+        compactPtrGroup(Array[0]) != Cur->CompactPtrGroupBase) {
       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) {
       for (u32 I = 0; I < Size; ++I)
-        DCHECK_EQ(compactPtrGroup(Array[I]), Cur->GroupId);
+        DCHECK_EQ(compactPtrGroup(Array[I]), Cur->CompactPtrGroupBase);
 
       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);
+        DCHECK_EQ(compactPtrGroup(Array[I - 1]), Cur->CompactPtrGroupBase);
         InsertBlocks(Cur, Array + I - Count, Count);
 
-        while (Cur != nullptr && compactPtrGroup(Array[I]) > Cur->GroupId) {
+        while (Cur != nullptr &&
+               compactPtrGroup(Array[I]) > Cur->CompactPtrGroupBase) {
           Prev = Cur;
           Cur = Cur->Next;
         }
 
-        if (Cur == nullptr || compactPtrGroup(Array[I]) != Cur->GroupId) {
+        if (Cur == nullptr ||
+            compactPtrGroup(Array[I]) != Cur->CompactPtrGroupBase) {
           Cur = CreateGroup(compactPtrGroup(Array[I]));
           DCHECK_NE(Prev, nullptr);
           Region->FreeList.insert(Prev, Cur);
         }
 
         Count = 1;
       } else {
         ++Count;
for (BatchGroup *BG = Region->FreeList.front(), *Prev = nullptr;
       const uptr PushedBytesDelta =
           BG->PushedBlocks - BG->PushedBlocksAtLastCheckpoint;
       if (PushedBytesDelta * BlockSize < PageSize) {
         Prev = BG;
         BG = BG->Next;
         continue;
       }
 
-      // Group boundary does not necessarily have the same alignment as Region.
-      // It may sit across a Region boundary. Which means that we may have the
-      // following two cases,
-      //
-      // 1. Group boundary sits before RegionBeg.
+      // Group boundary is always GroupSize-aligned from CompactPtr base. The
+      // layout of memory groups is like,
       //
-      //                (BatchGroupBase)
-      // batchGroupBase  RegionBeg       BatchGroupEnd
-      //        |            |                |
-      //        v            v                v
-      //        +------------+----------------+
-      //         \                           /
-      //          ------   GroupSize   ------
-      //
-      // 2. Group boundary sits after RegionBeg.
+      //     (CompactPtrBase)
+      // #1 CompactPtrGroupBase   #2 CompactPtrGroupBase            ...
+      //           |                       |                       |
+      //           v                       v                       v
+      //           +-----------------------+-----------------------+
+      //            \                     / \                     /
+      //             ---   GroupSize   ---   ---   GroupSize   ---
       //
-      //               (BatchGroupBase)
-      //    RegionBeg  batchGroupBase               BatchGroupEnd
-      //        |           |                             |
-      //        v           v                             v
-      //        +-----------+-----------------------------+
-      //                     \                           /
-      //                      ------   GroupSize   ------
-      //
-      // Note that in the first case, the group range before RegionBeg is never
-      // used. Therefore, while calculating the used group size, we should
-      // exclude that part to get the correct size.
+      // After decompacting the CompactPtrGroupBase, we expect the alignment
+      // property is held as well.
       const uptr BatchGroupBase =
-          Max(batchGroupBase(CompactPtrBase, BG->GroupId), Region->RegionBeg);
+          decompactGroupBase(CompactPtrBase, BG->CompactPtrGroupBase);
+      DCHECK_LE(Region->RegionBeg, BatchGroupBase);
       DCHECK_GE(AllocatedUserEnd, BatchGroupBase);
-      const uptr BatchGroupEnd =
-          batchGroupBase(CompactPtrBase, BG->GroupId) + GroupSize;
+      DCHECK_EQ((Region->RegionBeg - BatchGroupBase) % GroupSize, 0U);
+      const uptr BatchGroupEnd = BatchGroupBase + GroupSize;
       const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd
-                                          ? BatchGroupEnd - BatchGroupBase
+                                          ? GroupSize
                                           : AllocatedUserEnd - BatchGroupBase;
       if (AllocatedGroupSize == 0) {
         Prev = BG;
         BG = BG->Next;
         continue;
       }
 
       // TransferBatches are pushed in front of BG.Batches. The first one may
for (BatchGroup *BG = Region->FreeList.front(), *Prev = nullptr;
       else
         Region->FreeList.pop_front();
       GroupToRelease.push_back(Cur);
     }
 
     if (GroupToRelease.empty())
       return 0;
 
-    const uptr ReleaseBase =
-        Max(batchGroupBase(CompactPtrBase, GroupToRelease.front()->GroupId),
-            Region->RegionBeg);
+    const uptr ReleaseBase = decompactGroupBase(
+        CompactPtrBase, GroupToRelease.front()->CompactPtrGroupBase);
     const uptr LastGroupEnd =
-        Min(batchGroupBase(CompactPtrBase, GroupToRelease.back()->GroupId) +
+        Min(decompactGroupBase(CompactPtrBase,
+                               GroupToRelease.back()->CompactPtrGroupBase) +
                 GroupSize,
             AllocatedUserEnd);
     // The last block may straddle the group boundary. Rounding up to BlockSize
     // to get the exact range.
     const uptr ReleaseEnd =
         roundUpSlow(LastGroupEnd - Region->RegionBeg, BlockSize) +
         Region->RegionBeg;
     const uptr ReleaseRangeSize = ReleaseEnd - ReleaseBase;
 
     ReleaseRecorder Recorder(ReleaseBase, &Region->Data);
     PageReleaseContext Context(
         BlockSize, Region->AllocatedUser, /*NumberOfRegions=*/1U,
         ReleaseRangeSize, /*ReleaseOffset=*/ReleaseBase - Region->RegionBeg);
 
     for (BatchGroup &BG : GroupToRelease) {
       BG.PushedBlocksAtLastCheckpoint = BG.PushedBlocks;
 
-      // TODO(chiahungduan): Replace GroupId with BatchGroupBase to simplify the
-      // calculation here and above (where we determine the set of groups to
-      // release).
       const uptr BatchGroupBase =
-          Max(batchGroupBase(CompactPtrBase, BG.GroupId), Region->RegionBeg);
-      const uptr BatchGroupEnd =
-          batchGroupBase(CompactPtrBase, BG.GroupId) + GroupSize;
+          decompactGroupBase(CompactPtrBase, BG.CompactPtrGroupBase);
+      const uptr BatchGroupEnd = BatchGroupBase + GroupSize;
       const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd
-                                          ? BatchGroupEnd - BatchGroupBase
+                                          ? GroupSize
                                           : AllocatedUserEnd - BatchGroupBase;
       const uptr BatchGroupUsedEnd = BatchGroupBase + AllocatedGroupSize;
       const bool BlockAlignedWithUsedEnd =
           (BatchGroupUsedEnd - Region->RegionBeg) % BlockSize == 0;
 
       uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize;
       if (!BlockAlignedWithUsedEnd)
         ++MaxContainedBlocks;
 
       const uptr NumBlocks = (BG.Batches.size() - 1) * BG.MaxCachedPerBatch +
                              BG.Batches.front()->getCount();
 
       if (NumBlocks == MaxContainedBlocks) {
         for (const auto &It : BG.Batches)
           for (u16 I = 0; I < It.getCount(); ++I)
-            DCHECK_EQ(compactPtrGroup(It.get(I)), BG.GroupId);
+            DCHECK_EQ(compactPtrGroup(It.get(I)), BG.CompactPtrGroupBase);
 
         Context.markRangeAsAllCounted(BatchGroupBase, BatchGroupUsedEnd,
                                       Region->RegionBeg);
       } else {
         DCHECK_LT(NumBlocks, MaxContainedBlocks);
         // Note that we don't always visit blocks in each BatchGroup so that we
         // may miss the chance of releasing certain pages that cross
         // BatchGroups.
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
     // `Region->FreeList` and `GroupToRelease` are sorted.
     for (BatchGroup *BG = Region->FreeList.front(), *Prev = nullptr;;) {
       if (BG == nullptr || GroupToRelease.empty()) {
         if (!GroupToRelease.empty())
           Region->FreeList.append_back(&GroupToRelease);
         break;
       }
 
-      DCHECK_NE(BG->GroupId, GroupToRelease.front()->GroupId);
+      DCHECK_NE(BG->CompactPtrGroupBase,
+                GroupToRelease.front()->CompactPtrGroupBase);
 
-      if (BG->GroupId < GroupToRelease.front()->GroupId) {
+      if (BG->CompactPtrGroupBase <
+          GroupToRelease.front()->CompactPtrGroupBase) {
         Prev = BG;
         BG = BG->Next;
         continue;
       }
 
-      // At here, the `BG` is the first BatchGroup with GroupId larger than the
-      // first element in `GroupToRelease`. We need to insert
+      // At here, the `BG` is the first BatchGroup with CompactPtrGroupBase
+      // larger than the first element in `GroupToRelease`. We need to insert
       // `GroupToRelease::front()` (which is `Cur` below)  before `BG`.
       //
       //   1. If `Prev` is nullptr, we simply push `Cur` to the front of
       //      FreeList.
       //   2. Otherwise, use `insert()` which inserts an element next to `Prev`.
       //
       // Afterwards, we don't need to advance `BG` because the order between
       // `BG` and the new `GroupToRelease::front()` hasn't been checked.
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
 
     DCHECK_EQ(Region->FreeList.size(), NumberOfBatchGroups);
     (void)NumberOfBatchGroups;
 
     if (SCUDO_DEBUG) {
       BatchGroup *Prev = Region->FreeList.front();
       for (BatchGroup *Cur = Prev->Next; Cur != nullptr;
            Prev = Cur, Cur = Cur->Next) {
-        CHECK_LT(Prev->GroupId, Cur->GroupId);
+        CHECK_LT(Prev->CompactPtrGroupBase, Cur->CompactPtrGroupBase);
       }
     }
 
     return Recorder.getReleasedBytes();
   }
 };
 
 } // namespace scudo
 
 #endif // SCUDO_PRIMARY64_H_