[scudo] Use bytes-in-freelist as a hint of page release

[Chia-hungDuan]

Summary

Tracking the pushed bytes between to releaseToOSMaybe calls may lead to
a overestimated case that if we do malloc 2KB -> free 2KB -> malloc 2KB
-> free 2KB, we may think we have released 4KB but it only releases 2KB
actually. Switch to use bytes-in-freelist excludes more cases that can't
release the pages

[Chia-hungDuan]

Continue how we measure the efficiency of early-exit releaseToOS in D146312,

scudo   : -- Average Operation Time -- -- Name (# of Calls) --
scudo   :            264.4(ns)            releaseToOSMaybe (30981)
scudo   :             91.8(ns)              TryMarkingBlocks (7118)
scudo   :           7935.0(ns)              releaseFreeMemoryToOS (1)

(30981 - 7118) / 30981 ~= 77% of releaseToOSMaybe calls are excluded from trying of marking blocks. So far I didn't see the overall memory impact here thus I suppose we only exempt the cases that are supposed to release nothing.

[cferris]

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

741

Should this be skipped when force freeing everything?

846–848

updating

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

1046

updating

[Chia-hungDuan]

Address review comments

[cferris]

As mentioned, there is a difference between primary32 and primary64 that isn't clear.

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

832

This isn't in the primary32.h, is there a fundamental difference that means this isn't needed in that one?

[Chia-hungDuan]

Address review comment

[Chia-hungDuan]

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

741

You're right! Done.

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

832

A left over. Done!

[cferris]

LGTM

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

struct BatchGroup {
     BatchGroup *Next;
     // 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.
-    uptr PushedBlocksAtLastCheckpoint;
+    // This is used to track how many bytes are not in-use since last time we
+    // tried to release pages.
+    uptr BytesInBGAtLastCheckpoint;
     // 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) {

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

private:
   typedef FlatByteMap<NumRegions> ByteMap;
 
   struct SizeClassStats {
     uptr PoppedBlocks;
     uptr PushedBlocks;
   };
 
   struct ReleaseToOsInfo {
-    uptr PushedBlocksAtLastRelease;
+    uptr BytesInFreeListAtLastCheckpoint;
     uptr RangesReleased;
     uptr LastReleasedBytes;
     u64 LastReleaseAtNs;
   };
 
   struct alignas(SCUDO_CACHE_LINE_SIZE) SizeClassInfo {
     HybridMutex Mutex;
     SinglyLinkedList<BatchGroup> FreeList GUARDED_BY(Mutex);
auto CreateGroup = [&](uptr CompactPtrGroupBase) {
         TB = C->createBatch(ClassId, nullptr);
         TB->clear();
       }
 
       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->BytesInBGAtLastCheckpoint = 0;
       BG->MaxCachedPerBatch =
           TransferBatch::getMaxCached(getSizeByClassId(ClassId));
 
       return BG;
     };
 
     auto InsertBlocks = [&](BatchGroup *BG, CompactPtrT *Array, u32 Size) {
       SinglyLinkedList<TransferBatch> &Batches = BG->Batches;
NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
       REQUIRES(Sci->Mutex) {
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr PageSize = getPageSizeCached();
 
     DCHECK_GE(Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks);
     const uptr BytesInFreeList =
         Sci->AllocatedUser -
         (Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks) * BlockSize;
-    if (BytesInFreeList < PageSize)
-      return 0; // No chance to release anything.
-    const uptr BytesPushed =
-        (Sci->Stats.PushedBlocks - Sci->ReleaseInfo.PushedBlocksAtLastRelease) *
-        BlockSize;
-    if (BytesPushed < PageSize)
-      return 0; // Nothing new to release.
+
+    bool MaySkip = false;
+
+    if (BytesInFreeList <= Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint) {
+      Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;
+      MaySkip = true;
+    }
+
+    // Always update `BytesInFreeListAtLastCheckpoint` with the smallest value
+    // so that we won't underestimate the releasable pages. For example, the
+    // following is the region usage,
+    //
+    //  BytesInFreeListAtLastCheckpoint   AllocatedUser
+    //                v                         v
+    //  |--------------------------------------->
+    //         ^                   ^
+    //  BytesInFreeList     ReleaseThreshold
+    //
+    // In general, if we have collected enough bytes and the amount of free
+    // bytes meets the ReleaseThreshold, we will try to do page release. If we
+    // don't update `BytesInFreeListAtLastCheckpoint` when the current
+    // `BytesInFreeList` is smaller, we may take longer time to wait for enough
+    // freed blocks because we miss the bytes between
+    // (BytesInFreeListAtLastCheckpoint - BytesInFreeList).
+    const uptr PushedBytesDelta =
+        BytesInFreeList - Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint;
+    if (PushedBytesDelta < PageSize)
+      MaySkip = true;
 
     const bool CheckDensity =
         BlockSize < PageSize / 16U && ReleaseType != ReleaseToOS::ForceAll;
     // Releasing smaller blocks is expensive, so we want to make sure that a
     // significant amount of bytes are free, and that there has been a good
     // amount of batches pushed to the freelist before attempting to release.
     if (CheckDensity) {
       if (ReleaseType == ReleaseToOS::Normal &&
-          BytesPushed < Sci->AllocatedUser / 16U)
-        return 0;
+          PushedBytesDelta < Sci->AllocatedUser / 16U) {
+        MaySkip = true;
       }
+    }
+
+    if (MaySkip && ReleaseType != ReleaseToOS::ForceAll)
+      return 0;
 
     if (ReleaseType == ReleaseToOS::Normal) {
       const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs);
       if (IntervalMs < 0)
         return 0;
       if (Sci->ReleaseInfo.LastReleaseAtNs +
               static_cast<u64>(IntervalMs) * 1000000 >
           getMonotonicTimeFast()) {
NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
     ReleaseRecorder Recorder(Base);
     PageReleaseContext Context(BlockSize, 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;
-
       const uptr GroupBase = decompactGroupBase(BG.CompactPtrGroupBase);
       // The `GroupSize` may not be divided by `BlockSize`, which means there is
       // an unused space at the end of Region. Exclude that space to avoid
       // unused page map entry.
       uptr AllocatedGroupSize = GroupBase == CurGroupBase
                                     ? Sci->CurrentRegionAllocated
                                     : roundDownSlow(GroupSize, BlockSize);
       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;
+
+      if (ReleaseType != ReleaseToOS::ForceAll &&
+          BytesInBG <= BG.BytesInBGAtLastCheckpoint) {
+        BG.BytesInBGAtLastCheckpoint = BytesInBG;
+        continue;
+      }
+      const uptr PushedBytesDelta = BytesInBG - BG.BytesInBGAtLastCheckpoint;
+      if (PushedBytesDelta < PageSize)
+        continue;
+
       // 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;
       }
 
-      BG.PushedBlocksAtLastCheckpoint = BG.PushedBlocks;
+      // TODO: Consider updating this after page release if `ReleaseRecorder`
+      // can tell the releasd bytes in each group.
+      BG.BytesInBGAtLastCheckpoint = BytesInBG;
 
       const uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize;
       const uptr RegionIndex = (GroupBase - Base) / RegionSize;
 
       if (NumBlocks == MaxContainedBlocks) {
         for (const auto &It : BG.Batches)
           for (u16 I = 0; I < It.getCount(); ++I)
             DCHECK_EQ(compactPtrGroupBase(It.get(I)), BG.CompactPtrGroupBase);
NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
 
     auto SkipRegion = [this, First, ClassId](uptr RegionIndex) {
       ScopedLock L(ByteMapMutex);
       return (PossibleRegions[First + RegionIndex] - 1U) != ClassId;
     };
     releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
 
     if (Recorder.getReleasedRangesCount() > 0) {
-      Sci->ReleaseInfo.PushedBlocksAtLastRelease = Sci->Stats.PushedBlocks;
+      Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;
       Sci->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
       Sci->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
       TotalReleasedBytes += Sci->ReleaseInfo.LastReleasedBytes;
     }
     Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTimeFast();
 
     return TotalReleasedBytes;
   }

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

private:
   static const u32 MaxNumBatches = SCUDO_ANDROID ? 4U : 8U;
 
   struct RegionStats {
     uptr PoppedBlocks;
     uptr PushedBlocks;
   };
 
   struct ReleaseToOsInfo {
-    uptr PushedBlocksAtLastRelease;
+    uptr BytesInFreeListAtLastCheckpoint;
     uptr RangesReleased;
     uptr LastReleasedBytes;
     u64 LastReleaseAtNs;
   };
 
   struct UnpaddedRegionInfo {
     HybridMutex Mutex;
     SinglyLinkedList<BatchGroup> FreeList GUARDED_BY(Mutex);
auto CreateGroup = [&](uptr CompactPtrGroupBase) {
         TB = C->createBatch(ClassId, nullptr);
         TB->clear();
       }
 
       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->BytesInBGAtLastCheckpoint = 0;
       BG->MaxCachedPerBatch =
           TransferBatch::getMaxCached(getSizeByClassId(ClassId));
 
       return BG;
     };
 
     auto InsertBlocks = [&](BatchGroup *BG, CompactPtrT *Array, u32 Size) {
       SinglyLinkedList<TransferBatch> &Batches = BG->Batches;
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
       REQUIRES(Region->Mutex) {
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr PageSize = getPageSizeCached();
 
     DCHECK_GE(Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks);
     const uptr BytesInFreeList =
         Region->AllocatedUser -
         (Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks) * BlockSize;
-    if (BytesInFreeList < PageSize)
-      return 0; // No chance to release anything.
-    const uptr BytesPushed = (Region->Stats.PushedBlocks -
-                              Region->ReleaseInfo.PushedBlocksAtLastRelease) *
-                             BlockSize;
-    if (BytesPushed < PageSize)
-      return 0; // Nothing new to release.
 
-    const bool CheckDensity =
-        isSmallBlock(BlockSize) && ReleaseType != ReleaseToOS::ForceAll;
+    bool MaySkip = false;
+
+    // Always update `BytesInFreeListAtLastCheckpoint` with the smallest value
+    // so that we won't underestimate the releasable pages. For example, the
+    // following is the region usage,
+    //
+    //  BytesInFreeListAtLastCheckpoint   AllocatedUser
+    //                v                         v
+    //  |--------------------------------------->
+    //         ^                   ^
+    //  BytesInFreeList     ReleaseThreshold
+    //
+    // In general, if we have collected enough bytes and the amount of free
+    // bytes meets the ReleaseThreshold, we will try to do page release. If we
+    // don't update `BytesInFreeListAtLastCheckpoint` when the current
+    // `BytesInFreeList` is smaller, we may take longer time to wait for enough
+    // freed blocks because we miss the bytes between
+    // (BytesInFreeListAtLastCheckpoint - BytesInFreeList).
+    if (BytesInFreeList <=
+        Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint) {
+      Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;
+      MaySkip = true;
+    }
+
+    const uptr RegionPushedBytesDelta =
+        BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint;
+    if (RegionPushedBytesDelta < PageSize)
+      MaySkip = true;
+
+    const bool CheckDensity = isSmallBlock(BlockSize);
     // Releasing smaller blocks is expensive, so we want to make sure that a
     // significant amount of bytes are free, and that there has been a good
     // amount of batches pushed to the freelist before attempting to release.
     if (CheckDensity) {
       if (ReleaseType == ReleaseToOS::Normal &&
-          BytesPushed < Region->TryReleaseThreshold) {
-        return 0;
+          RegionPushedBytesDelta < Region->TryReleaseThreshold) {
+        MaySkip = true;
       }
     }
 
+    if (MaySkip && ReleaseType != ReleaseToOS::ForceAll)
+      return 0;
+
     if (ReleaseType == ReleaseToOS::Normal) {
       const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs);
       if (IntervalMs < 0)
         return 0;
       if (Region->ReleaseInfo.LastReleaseAtNs +
               static_cast<u64>(IntervalMs) * 1000000 >
           getMonotonicTimeFast()) {
         return 0; // Memory was returned recently.
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
     // release threshold as the next Region::TryReleaseThreshold(). Note that if
     // the size of free blocks has reached the release threshold, the distance
     // to the next release will be PageSize * SmallerBlockReleasePageDelta. See
     // the comment on `SmallerBlockReleasePageDelta` for more details.
     uptr MinDistToThreshold = GroupSize;
 
     for (BatchGroup *BG = Region->FreeList.front(), *Prev = nullptr;
          BG != nullptr;) {
-      const uptr PushedBytesDelta =
-          (BG->PushedBlocks - BG->PushedBlocksAtLastCheckpoint) * BlockSize;
-      if (PushedBytesDelta < PageSize) {
-        Prev = BG;
-        BG = BG->Next;
-        continue;
-      }
-
       // Group boundary is always GroupSize-aligned from CompactPtr base. The
       // layout of memory groups is like,
       //
       //     (CompactPtrBase)
       // #1 CompactPtrGroupBase   #2 CompactPtrGroupBase            ...
       //           |                       |                       |
       //           v                       v                       v
       //           +-----------------------+-----------------------+
for (BatchGroup *BG = Region->FreeList.front(), *Prev = nullptr;
         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;
+
+      if (ReleaseType != ReleaseToOS::ForceAll &&
+          BytesInBG <= BG->BytesInBGAtLastCheckpoint) {
+        BG->BytesInBGAtLastCheckpoint = BytesInBG;
+        Prev = BG;
+        BG = BG->Next;
+        continue;
+      }
+
+      const uptr PushedBytesDelta = BG->BytesInBGAtLastCheckpoint - BytesInBG;
+
       // 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) {
         const uptr ReleaseThreshold =
             (AllocatedGroupSize * (100 - 1U - BlockSize / 16U)) / 100U;
         const bool HighDensity = BytesInBG >= ReleaseThreshold;
for (BatchGroup *BG = Region->FreeList.front(), *Prev = nullptr;
       //       +--------+
       //
       // Note that we need to advance before pushing this BatchGroup to
       // GroupToRelease because it's a destructive operation.
 
       BatchGroup *Cur = BG;
       BG = BG->Next;
 
+      // Ideally, we may want to update this only after successful release.
+      // However, for smaller blocks, each block marking is a costly operation.
+      // Therefore, we update it earlier.
+      // TODO: Consider updating this after page release if `ReleaseRecorder`
+      // can tell the releasd bytes in each group.
+      Cur->BytesInBGAtLastCheckpoint = BytesInBG;
+
       if (Prev != nullptr)
         Region->FreeList.extract(Prev, Cur);
       else
         Region->FreeList.pop_front();
       GroupToRelease.push_back(Cur);
     }
 
     // Only small blocks have the adaptive `TryReleaseThreshold`.
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
     const uptr ReleaseRangeSize = ReleaseEnd - ReleaseBase;
     const uptr ReleaseOffset = ReleaseBase - Region->RegionBeg;
 
     ReleaseRecorder Recorder(Region->RegionBeg, ReleaseOffset, &Region->Data);
     PageReleaseContext Context(BlockSize, /*NumberOfRegions=*/1U,
                                ReleaseRangeSize, ReleaseOffset);
 
     for (BatchGroup &BG : GroupToRelease) {
-      BG.PushedBlocksAtLastCheckpoint = BG.PushedBlocks;
-
       const uptr BatchGroupBase =
           decompactGroupBase(CompactPtrBase, BG.CompactPtrGroupBase);
       const uptr BatchGroupEnd = BatchGroupBase + GroupSize;
       const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd
                                           ? GroupSize
                                           : AllocatedUserEnd - BatchGroupBase;
       const uptr BatchGroupUsedEnd = BatchGroupBase + AllocatedGroupSize;
       const bool MayContainLastBlockInRegion =
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
     }
 
     DCHECK(Context.hasBlockMarked());
 
     auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };
     releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
 
     if (Recorder.getReleasedRangesCount() > 0) {
-      Region->ReleaseInfo.PushedBlocksAtLastRelease =
-          Region->Stats.PushedBlocks;
+      Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;
       Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
       Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
     }
     Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTimeFast();
 
     // Merge GroupToRelease back to the Region::FreeList. Note that both
     // `Region->FreeList` and `GroupToRelease` are sorted.
     for (BatchGroup *BG = Region->FreeList.front(), *Prev = nullptr;;) {