[scudo] Release pages of larger block more frequently

[Chia-hungDuan]

Summary

Release pages for large block (size greater than a page) is faster than
the small blocks. Besides, larger blocks are supposed not to be used
so often like smaller blocks which means we may hold several pages used
by large block and rarely get chance to release them if there's no
explicit M_PURGE call. Therefore, relax the release-interval condition
for large block.

This also fixes the assumption that FORCE_ALL should always try page
release.

[Chia-hungDuan]

Will measure the performance under some scenarios to see if this brings huge impact and put the number here

[Chia-hungDuan]

Use ForceAll in test instead because ForceAll always visits all the free blocks
without applying any heuristics which may skip some blocks.

Also fix the ForceAll logic in primary32

[Chia-hungDuan]

[Chia-hungDuan]

Fix wrong logic

[Chia-hungDuan]

Adjust heuristics

[Chia-hungDuan]

If &ReleaseToOsIntervalMs == -1, still don't release large block

[Chia-hungDuan]

By some experiments,

The extra time for releasing large block more frequently is around tens of us to hundreds of us, e.g.,

scudo   : -- Average Operation Time -- -- Name (# of Calls) --
scudo   :          44426.1(ns)            releaseToOSMaybe (5284)
scudo   :          74355.5(ns)              releaseFreeMemoryToOS (2816)

scudo   : -- Average Operation Time -- -- Name (# of Calls) --
scudo   :          70457.8(ns)            releaseToOSMaybe (5219)
scudo   :          89452.3(ns)              releaseFreeMemoryToOS (3781)

scudo   : -- Average Operation Time -- -- Name (# of Calls) --
scudo   :         431321.0(ns)            releaseToOSMaybe (3398)
scudo   :         356707.4(ns)              releaseFreeMemoryToOS (3302)

The memory reduction for some apps like clash of clans, it reduces ~4% memory usage and it increases 100 MB available memory after boot. Both are measured on Android T

[cferris]

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

137

Should there be a line between the functions?

140

Should this be >=?

781–782

There is only one way that MaySkip can be set to true and ReleaseType is not Normal. Right now, some other code is actually doing some wasted computation and other wasted work if you are doing a normal release.

For example, this MaySkip would become:

if (ReleaseType != ReleaseToOS::ForceAll)

return 0;

And all other MaySkips would become return 0.

793

It's probably worth adding a comment about why this value is chosen.

854

Should the ReleaseType check be here too?

[Chia-hungDuan]

Address review comment

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

140

My intention is to set PageSize as a boundary so I'm thinking it as "larger than". No strong opinion here, do you want it to be ">="?

854

CheckDensity has covered the check of ForceAll. But I do want to revise the check of release type a little bit in a different CL

[cferris]

Small nit in comment.

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

140

I don't really care one way or another, so > is good to me too.

794

attempt

854

Sounds good to me.

[Chia-hungDuan]

Fix typo

[cferris]

One question left.

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

753

This check doesn't result in a skip any more. Does one of the other checks cover the case now?

[Chia-hungDuan]

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

753

This expression was mainly for avoiding overflow when calculating the PushedBytesDelta down below, which is

const uptr PushedBytesDelta =
    BytesInFreeList - Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint;

[cferris]

LGTM.

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

uptr compactPtrGroupBase(CompactPtrT CompactPtr) {
     const uptr Mask = (static_cast<uptr>(1) << GroupSizeLog) - 1;
     return CompactPtr & ~Mask;
   }
 
   uptr decompactGroupBase(uptr CompactPtrGroupBase) {
     return CompactPtrGroupBase;
   }
 
+  ALWAYS_INLINE static bool isSmallBlock(uptr BlockSize) {
+    const uptr PageSize = getPageSizeCached();
+    return BlockSize < PageSize / 16U;
+  }
+
+  ALWAYS_INLINE static bool isLargeBlock(uptr BlockSize) {
+    const uptr PageSize = getPageSizeCached();
+    return BlockSize > PageSize;
+  }
+
   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;
NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
     DCHECK_GE(Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks);
     const uptr BytesInFreeList =
         Sci->AllocatedUser -
         (Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks) * BlockSize;
 
     if (UNLIKELY(BytesInFreeList == 0))
       return 0;
 
-    bool MaySkip = false;
-
-    if (BytesInFreeList <= Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint) {
+    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;
+    if (PushedBytesDelta < PageSize && ReleaseType != ReleaseToOS::ForceAll)
+      return 0;
 
     const bool CheckDensity =
-        BlockSize < PageSize / 16U && ReleaseType != ReleaseToOS::ForceAll;
+        isSmallBlock(BlockSize) && 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 &&
-          PushedBytesDelta < Sci->AllocatedUser / 16U) {
-        MaySkip = true;
-      }
-    }
-
-    if (MaySkip && ReleaseType != ReleaseToOS::ForceAll)
+    if (CheckDensity && ReleaseType == ReleaseToOS::Normal)
+      if (PushedBytesDelta < Sci->AllocatedUser / 16U)
         return 0;
 
     if (ReleaseType == ReleaseToOS::Normal) {
       const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs);
       if (IntervalMs < 0)
         return 0;
+
+      // The constant 8 here is selected from profiling some apps and the number
+      // of unreleased pages in the large size classes is around 16 pages or
+      // more. Choose half of it as a heuristic and which also avoids page
+      // release every time for every pushBlocks() attempt by large blocks.
+      const bool ByPassReleaseInterval =
+          isLargeBlock(BlockSize) && PushedBytesDelta > 8 * PageSize;
+      if (!ByPassReleaseInterval) {
         if (Sci->ReleaseInfo.LastReleaseAtNs +
                 static_cast<u64>(IntervalMs) * 1000000 >
             getMonotonicTimeFast()) {
-        return 0; // Memory was returned recently.
+          // Memory was returned recently.
+          return 0;
         }
       }
+    } // if (ReleaseType == ReleaseToOS::Normal)
 
     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;
for (BatchGroup &BG : Sci->FreeList) {
       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)
+      if (ReleaseType != ReleaseToOS::ForceAll && 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;
       }
 
       // TODO: Consider updating this after page release if `ReleaseRecorder`
       // can tell the releasd bytes in each group.
       BG.BytesInBGAtLastCheckpoint = BytesInBG;
 

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

static uptr decompactGroupBase(uptr Base, uptr CompactPtrGroupBase) {
     return Base + (CompactPtrGroupBase << CompactPtrScale);
   }
 
   ALWAYS_INLINE static bool isSmallBlock(uptr BlockSize) {
     const uptr PageSize = getPageSizeCached();
     return BlockSize < PageSize / 16U;
   }
 
+  ALWAYS_INLINE static bool isLargeBlock(uptr BlockSize) {
+    const uptr PageSize = getPageSizeCached();
+    return BlockSize > PageSize;
+  }
+
   // Push the blocks to their batch group. The layout will be like,
   //
   // FreeList - > BG -> BG -> BG
   //              |     |     |
   //              v     v     v
   //              TB    TB    TB
   //              |
   //              v
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
     DCHECK_GE(Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks);
     const uptr BytesInFreeList =
         Region->AllocatedUser -
         (Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks) * BlockSize;
 
     if (UNLIKELY(BytesInFreeList == 0))
       return 0;
 
-    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;
+    if (RegionPushedBytesDelta < PageSize &&
+        ReleaseType != ReleaseToOS::ForceAll) {
+      return 0;
+    }
 
     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 &&
-          RegionPushedBytesDelta < Region->TryReleaseThreshold) {
-        MaySkip = true;
-      }
-    }
-
-    if (MaySkip && ReleaseType != ReleaseToOS::ForceAll)
+    if (CheckDensity && ReleaseType == ReleaseToOS::Normal)
+      if (RegionPushedBytesDelta < Region->TryReleaseThreshold)
         return 0;
 
     if (ReleaseType == ReleaseToOS::Normal) {
       const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs);
       if (IntervalMs < 0)
         return 0;
+
+      // The constant 8 here is selected from profiling some apps and the number
+      // of unreleased pages in the large size classes is around 16 pages or
+      // more. Choose half of it as a heuristic and which also avoids page
+      // release every time for every pushBlocks() attempt by large blocks.
+      const bool ByPassReleaseInterval =
+          isLargeBlock(BlockSize) && RegionPushedBytesDelta > 8 * PageSize;
+      if (!ByPassReleaseInterval) {
         if (Region->ReleaseInfo.LastReleaseAtNs +
                 static_cast<u64>(IntervalMs) * 1000000 >
             getMonotonicTimeFast()) {
-        return 0; // Memory was returned recently.
+          // Memory was returned recently.
+          return 0;
         }
       }
+    } // if (ReleaseType == ReleaseToOS::Normal)
 
     const uptr GroupSize = (1U << GroupSizeLog);
     const uptr AllocatedUserEnd = Region->AllocatedUser + Region->RegionBeg;
     const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId);
     auto DecompactPtr = [CompactPtrBase](CompactPtrT CompactPtr) {
       return decompactPtrInternal(CompactPtrBase, CompactPtr);
     };
 

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

SCUDO_TYPED_TEST(ScudoPrimaryTest, ReleaseToOS) {
   Cache.init(nullptr, Allocator.get());
   const scudo::uptr Size = scudo::getPageSizeCached() * 2;
   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(scudo::ReleaseToOS::Force), 0U);
+  EXPECT_GT(Allocator->releaseToOS(scudo::ReleaseToOS::ForceAll), 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());