[scudo] Early exit from the case can't do page release.

[Chia-hungDuan]

Summary

There are heuristics to avoid marking blocks if there's little chance
to release pages. So far, those logics only exist in block-marking
section and we didn't leverage the results of those logics. For example,
in a round of releaseToOS try, we know it's still 128 KB away from the
release threshold. In the next round of releaseToOS, we can early exit
if the number of pushed bytes is smaller than 128 KB without looping
each memory group. This CL adds this heuristic and has reduced amount of
time in checking the status of each memory group.

This CL only applies this heuristic on SizeClassAllocator64.
SizeClassAllocator32 has a smaller region/group size and has little
impact on the default value.

[Chia-hungDuan]

With this CL, the filtered try-marking-blocks is reduced ~1000 times (6000 vs 5000) in com.google.android.googlequicksearchbox:interactor on Android

[cferris]

Small comment nits.

You gathered data for the one process, but is there any other data worth gathering?

I did see some extra work going on in system_server, but I was using my test account so it might have a different set of apps that triggers a different allocation pattern. Let me know if you want me to gather anything on this device.

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

125

Releasing small blocks

126

page releases

[Chia-hungDuan]

Address review comment and fix a bug in keep the invariant that the TryReleaseThreshold.
It should be the minimum distance to the next page release. So if it has reached the high
density, then the next threshold will be the SmallerBlockReleasePageDelta (which we use for
mitigating thrashing)

[Chia-hungDuan]

In D146312#4203317, @cferris wrote:

Small comment nits.

You gathered data for the one process, but is there any other data worth gathering?

I did see some extra work going on in system_server, but I was using my test account so it might have a different set of apps that triggers a different allocation pattern. Let me know if you want me to gather anything on this device.

From my case, there are two processes fall into that condition very frequently. (the followings are copied from bug)

com.google.android.as
com.google.android.googlequicksearchbox:interactor

In general, this is supposed to be a quick check without visiting each memory group, it's conservative. Which means we are supposed to not miss any real release chance we had before but get exempted from visiting group. According to the data, each visiting group without marking blocks may take 309.6(ns) ~ 14732.2(ns). It's not a long operation but it may still be worth of saving.

Besides, we are more aggressive than before (the Region->AllocatedUser / 16U), we have more chances to release pages. Same cases I've observed are the two processes above, I see they release 500 KB ~ 1MB 30s after the device boot.

I was expecting system_server should be reporting most of this case. Maybe you can try this patch on your device and see if there's any different?

[Chia-hungDuan]

Slightly adjust the heuristic.
The new threshold should also consider PushedBytesDelta because we don't reset it after a failed page release

[Chia-hungDuan]

The evaluation is from the same scenario as above - reboot the phone and wait for 30s, then collect all the events of calling releaseToOS.

From the log, the new threshold is larger than the original one (AllocatedUser / 16U) in most of cases and therefore avoid more unsuccessful mark-block-attempt. When the threshold is smaller than the original one, I see some chances that we can release some pages there.

[Chia-hungDuan]

Add some number from system_server

Before:

Threshold: AllocatedUser / 16 U
scudo   : -- Average Operation Time -- -- Name (# of Calls) --
scudo   :           1850.9(ns)            releaseToOSMaybe (30907)
scudo   :            359.5(ns)              TryMarkingBlocks (28092)
scudo   :          44311.0(ns)              releaseFreeMemoryToOS (1)

After:

Threshold: Region->TryReleaseThreshold
scudo   : -- Average Operation Time -- -- Name (# of Calls) --
scudo   :           1056.2(ns)            releaseToOSMaybe (30857)
scudo   :            127.8(ns)              TryMarkingBlocks (22342)
scudo   :          15992.0(ns)              releaseFreeMemoryToOS (1)

# of releaseToOSMaybe - # of TryMarkingBlocks = # of cases which is early exit.

At before, (30907 − 28092) ÷ 30907 ~= 9.1% cases are excluded from trying of marking blocks
With this CL, (30857 − 22342)÷30857 ~= 27.5% cases are excluded from trying of marking blocks

Even with some improvement, the rate is still lower than I thought. Will try to dig more opportunity.

[cferris]

LGTM

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

return (ClassId == SizeClassMap::BatchClassId)
                ? roundUp(sizeof(TransferBatch), 1U << CompactPtrScale)
                : SizeClassMap::getSizeByClassId(ClassId);
   }
 
   static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }
 
   void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS {
     DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT)));
-    DCHECK_EQ(PrimaryBase, 0U);
-
-    // Reserve the space required for the Primary.
-    PrimaryBase = reinterpret_cast<uptr>(map(
-        nullptr, PrimarySize, "scudo:primary_reserve", MAP_NOACCESS, &Data));
 
-    u32 Seed;
-    const u64 Time = getMonotonicTimeFast();
-    if (!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed)))
-      Seed = static_cast<u32>(Time ^ (PrimaryBase >> 12));
     const uptr PageSize = getPageSizeCached();
-    for (uptr I = 0; I < NumClasses; I++) {
-      RegionInfo *Region = getRegionInfo(I);
-      // The actual start of a region is offset by a random number of pages
-      // when PrimaryEnableRandomOffset is set.
-      Region->RegionBeg = (PrimaryBase + (I << Config::PrimaryRegionSizeLog)) +
-                          (Config::PrimaryEnableRandomOffset
-                               ? ((getRandomModN(&Seed, 16) + 1) * PageSize)
-                               : 0);
-      Region->RandState = getRandomU32(&Seed);
-      Region->ReleaseInfo.LastReleaseAtNs = Time;
-    }
-    shuffle(RegionInfoArray, NumClasses, &Seed);
-
-    setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval));
-
     const uptr GroupSize = (1U << GroupSizeLog);
     const uptr PagesInGroup = GroupSize / PageSize;
     const uptr MinSizeClass = getSizeByClassId(1);
     // When trying to release pages back to memory, visiting smaller size
     // classes is expensive. Therefore, we only try to release smaller size
     // classes when the amount of free blocks goes over a certain threshold (See
     // the comment in releaseToOSMaybe() for more details). For example, for
     // size class 32, we only do the release when the size of free blocks is
void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS {
     // The 3% size in a group is about 7 pages. For two consecutive
     // releaseToOSMaybe(), we require the difference between `PushedBlocks`
     // should be greater than 7 pages. This mitigates the page releasing
     // thrashing which is caused by memory usage bouncing around the threshold.
     // The smallest size class takes longest time to do the page release so we
     // use its size of in-use blocks as a heuristic.
     SmallerBlockReleasePageDelta =
         PagesInGroup * (1 + MinSizeClass / 16U) / 100;
+
+    DCHECK_EQ(PrimaryBase, 0U);
+    // Reserve the space required for the Primary.
+    PrimaryBase = reinterpret_cast<uptr>(map(
+        nullptr, PrimarySize, "scudo:primary_reserve", MAP_NOACCESS, &Data));
+
+    u32 Seed;
+    const u64 Time = getMonotonicTimeFast();
+    if (!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed)))
+      Seed = static_cast<u32>(Time ^ (PrimaryBase >> 12));
+
+    for (uptr I = 0; I < NumClasses; I++) {
+      RegionInfo *Region = getRegionInfo(I);
+      // The actual start of a region is offset by a random number of pages
+      // when PrimaryEnableRandomOffset is set.
+      Region->RegionBeg = (PrimaryBase + (I << Config::PrimaryRegionSizeLog)) +
+                          (Config::PrimaryEnableRandomOffset
+                               ? ((getRandomModN(&Seed, 16) + 1) * PageSize)
+                               : 0);
+      Region->RandState = getRandomU32(&Seed);
+      // Releasing small blocks is expensive, set a higher threshold to avoid
+      // frequent page releases.
+      if (isSmallBlock(getSizeByClassId(I)))
+        Region->TryReleaseThreshold = PageSize * SmallerBlockReleasePageDelta;
+      else
+        Region->TryReleaseThreshold = PageSize;
+      Region->ReleaseInfo.LastReleaseAtNs = Time;
+    }
+    shuffle(RegionInfoArray, NumClasses, &Seed);
+
+    setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval));
   }
 
   void unmapTestOnly() NO_THREAD_SAFETY_ANALYSIS {
     for (uptr I = 0; I < NumClasses; I++) {
       RegionInfo *Region = getRegionInfo(I);
       *Region = {};
     }
     if (PrimaryBase)
struct UnpaddedRegionInfo {
     // This is initialized before thread creation.
     uptr RegionBeg = 0;
     RegionStats Stats GUARDED_BY(Mutex) = {};
     u32 RandState GUARDED_BY(Mutex) = 0;
     // Bytes mapped for user memory.
     uptr MappedUser GUARDED_BY(Mutex) = 0;
     // Bytes allocated for user memory.
     uptr AllocatedUser GUARDED_BY(Mutex) = 0;
+    // The minimum size of pushed blocks to trigger page release.
+    uptr TryReleaseThreshold GUARDED_BY(Mutex) = 0;
     MapPlatformData Data GUARDED_BY(Mutex) = {};
     ReleaseToOsInfo ReleaseInfo GUARDED_BY(Mutex) = {};
     bool Exhausted GUARDED_BY(Mutex) = false;
   };
   struct RegionInfo : UnpaddedRegionInfo {
     char Padding[SCUDO_CACHE_LINE_SIZE -
                  (sizeof(UnpaddedRegionInfo) % SCUDO_CACHE_LINE_SIZE)] = {};
   };
static uptr compactPtrGroup(CompactPtrT CompactPtr) {
     const uptr Mask = (static_cast<uptr>(1) << GroupScale) - 1;
     return static_cast<uptr>(CompactPtr) & ~Mask;
   }
   static uptr decompactGroupBase(uptr Base, uptr CompactPtrGroupBase) {
     DCHECK_EQ(CompactPtrGroupBase % (static_cast<uptr>(1) << (GroupScale)), 0U);
     return Base + (CompactPtrGroupBase << CompactPtrScale);
   }
 
+  ALWAYS_INLINE static bool isSmallBlock(uptr BlockSize) {
+    const uptr PageSize = getPageSizeCached();
+    return BlockSize < PageSize / 16U;
+  }
+
   // Push the blocks to their batch group. The layout will be like,
   //
   // FreeList - > BG -> BG -> BG
   //              |     |     |
   //              v     v     v
   //              TB    TB    TB
   //              |
   //              v
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 =
-        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 &&
-          BytesPushed < Region->AllocatedUser / 16U)
+          BytesPushed < Region->TryReleaseThreshold) {
         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()) {
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
     // `GroupToRelease`.
     SinglyLinkedList<BatchGroup> GroupToRelease;
     GroupToRelease.clear();
 
     // This is only used for debugging to ensure the consistency of the number
     // of groups.
     uptr NumberOfBatchGroups = Region->FreeList.size();
 
+    // We are examining each group and will take the minimum distance to the
+    // 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;
-      if (PushedBytesDelta * BlockSize < PageSize) {
+          (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,
       //
for (BatchGroup *BG = Region->FreeList.front(), *Prev = nullptr;
       const uptr NumBlocks = (BG->Batches.size() - 1) * BG->MaxCachedPerBatch +
                              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) {
-        const bool HighDensity = (BytesInBG * 100U) / AllocatedGroupSize >=
-                                 (100U - 1U - BlockSize / 16U);
+        const uptr ReleaseThreshold =
+            (AllocatedGroupSize * (100 - 1U - BlockSize / 16U)) / 100U;
+        const bool HighDensity = BytesInBG >= ReleaseThreshold;
         const bool MayHaveReleasedAll = NumBlocks >= (GroupSize / BlockSize);
         // If all blocks in the group are released, we will do range marking
         // which is fast. Otherwise, we will wait until we have accumulated
         // a certain amount of free memory.
         const bool ReachReleaseDelta =
-            MayHaveReleasedAll ? true
-                               : PushedBytesDelta * BlockSize >=
-                                     PageSize * SmallerBlockReleasePageDelta;
+            MayHaveReleasedAll
+                ? true
+                : PushedBytesDelta >= PageSize * SmallerBlockReleasePageDelta;
+
+        if (!HighDensity) {
+          DCHECK_LE(BytesInBG, ReleaseThreshold);
+          // The following is the usage of a memroy group,
+          //
+          //     BytesInBG             ReleaseThreshold
+          //  /             \                 v
+          //  +---+---------------------------+-----+
+          //  |   |         |                 |     |
+          //  +---+---------------------------+-----+
+          //       \        /                       ^
+          //    PushedBytesDelta                 GroupEnd
+          MinDistToThreshold =
+              Min(MinDistToThreshold,
+                  ReleaseThreshold - BytesInBG + PushedBytesDelta);
+        } else {
+          // If it reaches high density at this round, the next time we will try
+          // to release is based on SmallerBlockReleasePageDelta
+          MinDistToThreshold =
+              Min(MinDistToThreshold, PageSize * SmallerBlockReleasePageDelta);
+        }
 
         if (!HighDensity || !ReachReleaseDelta) {
           Prev = BG;
           BG = BG->Next;
           continue;
         }
       }
 
for (BatchGroup *BG = Region->FreeList.front(), *Prev = nullptr;
 
       if (Prev != nullptr)
         Region->FreeList.extract(Prev, Cur);
       else
         Region->FreeList.pop_front();
       GroupToRelease.push_back(Cur);
     }
 
+    // Only small blocks have the adaptive `TryReleaseThreshold`.
+    if (isSmallBlock(BlockSize)) {
+      // If the MinDistToThreshold is not updated, that means each memory group
+      // may have only pushed less than a page size. In that case, just set it
+      // back to normal.
+      if (MinDistToThreshold == GroupSize)
+        MinDistToThreshold = PageSize * SmallerBlockReleasePageDelta;
+      Region->TryReleaseThreshold = MinDistToThreshold;
+    }
+
     if (GroupToRelease.empty())
       return 0;
 
     const uptr ReleaseBase = decompactGroupBase(
         CompactPtrBase, GroupToRelease.front()->CompactPtrGroupBase);
     const uptr LastGroupEnd =
         Min(decompactGroupBase(CompactPtrBase,
                                GroupToRelease.back()->CompactPtrGroupBase) +