Revert "Revert "[scudo] Fix the calculating of memory group usage""

[Chia-hungDuan]

Summary

This reverts commit 69fe7abb393ba7d6ee9c8ff1429316845b5bad37.

[Chia-hungDuan]

Fix arguments order while calling batchGroupBase()

[Chia-hungDuan]

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

737

The arguments order was wrong in last CL

[Chia-hungDuan]

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

737

It was caught by the DCHECK_GE above but somehow I tested it on non-debug build.

[phosek]

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

372

This wasn't in rG69fe7abb393ba7d6ee9c8ff1429316845b5bad37, is it intended?

[Chia-hungDuan]

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

372

I just noticed that it will be better to align the style above (make the implicit casting explicitly) so I added it in this one (which is somehow related). It's not a fix of correctness.

[phosek]

LGTM

[Chia-hungDuan]

In D136995#3893835, @phosek wrote:

LGTM

Thanks

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

for (BatchGroup &BG : Sci->FreeList) {
         continue;
 
       uptr AllocatedGroupSize = BG.GroupId == CurRegionGroupId
                                     ? Sci->CurrentRegionAllocated
                                     : GroupSize;
       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.back()->getCount();
+                             BG.Batches.front()->getCount();
       const uptr BytesInBG = NumBlocks * BlockSize;
       // Given the randomness property, we try to release the pages only if the
       // bytes used by free blocks exceed certain proportion of allocated
       // spaces.
       if (CheckDensity && (BytesInBG * 100U) / AllocatedGroupSize <
                               (100U - 1U - BlockSize / 16U)) {
         continue;
       }

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

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 CompactPtr >> (GroupSizeLog - CompactPtrScale);
+    return static_cast<uptr>(CompactPtr) >> (GroupSizeLog - CompactPtrScale);
   }
   static uptr batchGroupBase(uptr Base, uptr GroupId) {
     return (GroupId << GroupSizeLog) + Base;
   }
 
   // Push the blocks to their batch group. The layout will be like,
   //
   // FreeList - > BG -> BG -> BG
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
     auto DecompactPtr = [CompactPtrBase](CompactPtrT CompactPtr) {
       return decompactPtrInternal(CompactPtrBase, CompactPtr);
     };
     for (BatchGroup &BG : Region->FreeList) {
       const uptr PushedBytesDelta =
           BG.PushedBlocks - BG.PushedBlocksAtLastCheckpoint;
       if (PushedBytesDelta * BlockSize < PageSize)
         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.
+      //
+      //                (BatchGroupBeg)
+      // batchGroupBase  RegionBeg       BatchGroupEnd
+      //        |            |                |
+      //        v            v                v
+      //        +------------+----------------+
+      //         \                           /
+      //          ------   GroupSize   ------
+      //
+      // 2. Group boundary sits after RegionBeg.
+      //
+      //               (BatchGroupBeg)
+      //    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.
+      const uptr BatchGroupBeg =
+          Max(batchGroupBase(CompactPtrBase, BG.GroupId), Region->RegionBeg);
+      DCHECK_GE(AllocatedUserEnd, BatchGroupBeg);
       const uptr BatchGroupEnd =
-          batchGroupBase(BG.GroupId, CompactPtrBase) + GroupSize;
+          batchGroupBase(CompactPtrBase, BG.GroupId) + GroupSize;
       const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd
-                                          ? GroupSize
-                                          : AllocatedUserEnd - BatchGroupEnd;
+                                          ? BatchGroupEnd - BatchGroupBeg
+                                          : AllocatedUserEnd - BatchGroupBeg;
       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.back()->getCount();
+                             BG.Batches.front()->getCount();
       const uptr BytesInBG = NumBlocks * BlockSize;
       // Given the randomness property, we try to release the pages only if the
       // bytes used by free blocks exceed certain proportion of group size. Note
       // that this heuristic only applies when all the spaces in a BatchGroup
       // are allocated.
       if (CheckDensity && (BytesInBG * 100U) / AllocatedGroupSize <
                               (100U - 1U - BlockSize / 16U)) {
         continue;