[scudo] Mitigate page releasing thrashing

[Chia-hungDuan]

Summary

We have the heuristic to determine the threshold of doing page
releasing for smaller size classes. However, in a case that the
memory usage is bouncing between that threshold may result in
frequent try of page releasing but not returning much memory.

This CL add another heuristic to mitigate this problem by increasing
the minimum pages that potentially can be released. Note that this
heuristic is only applied on SizeClassAllocator64. SizeClassAllocator32
has a smaller group size so the overhead is smaller than 64-bit
platform.

[cferris]

Mostly nits, but do you have any numbers on the change to RSS usage? I wouldn't expect this to cause much change, but I always worry about some pathological case that results in no memory being released.

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

95

goes over

98

is greater

100

releases

102

reduces the frequency of these calls

121

is caused

122

the longest time to do the page release

913

a certain

[Chia-hungDuan]

Address review comment

So far, I didn't see memory usage increasing in many apps and boot. This tends
to address some extreme cases that do periodically a bunch of allocs/frees. From
some artificial scenarios, we can see the times of doing page release reduced.
Will keep an eye on the system health afterward

[cferris]

LGTM.

I had one small comment about a comment that is so small that I don't think it's worth holding up the CL.

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

122

There is an extra space in here. If you have another change already modifying this file, feel free to make it later or even in a follow-on if you want.

[Chia-hungDuan]

In D144768#4167951, @cferris wrote:

LGTM.

I had one small comment about a comment that is so small that I don't think it's worth holding up the CL.

Got it. I'll rebase this change up to the front of this chain and merge it by next Monday.

[Chia-hungDuan]

Remove extra space and rebase

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

for (uptr I = 0; I < NumClasses; I++) {
       Region->RegionBeg = getRegionBaseByClassId(I) +
                           (Config::PrimaryEnableRandomOffset
                                ? ((getRandomModN(&Seed, 16) + 1) * PageSize)
                                : 0);
       Region->RandState = getRandomU32(&Seed);
       Region->ReleaseInfo.LastReleaseAtNs = Time;
     }
     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 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
+    // greater than 97% of pages in a group. However, this may introduce another
+    // issue that if the number of free blocks is bouncing between 97% ~ 100%.
+    // Which means we may try many page releasing but only release very few of
+    // them (less than 3% in a group). Even though we have
+    // `&ReleaseToOsIntervalMs` which slightly reduce these the frequency but it
+    // will be better to have another guard to mitigate this issue.
+    //
+    // Here we add another constraint on the minimum size requirement. The
+    // constraint is determined by the size of in-use blocks in the minimal size
+    // class. Take size class 32 as an example,
+    //
+    //   +-     one memory group      -+
+    //   +----------------------+------+
+    //   |  97% of free blocks  |      |
+    //   +----------------------+------+
+    //                           \    /
+    //                      3% in-use blocks
+    //
+    //   * The release size threshold is 97%.
+    //
+    // 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 caused by memory usage bouncing around the threshold. The
+    // smallest size class takes longest time in page releasing so we use its
+    // size of in-use blocks as a heuristic.
+    SmallerBlockReleasePageDelta =
+        PagesInGroup * (1 + MinSizeClass / 16U) / 100;
   }
 
   void unmapTestOnly() NO_THREAD_SAFETY_ANALYSIS {
     for (uptr I = 0; I < NumClasses; I++) {
       RegionInfo *Region = getRegionInfo(I);
       *Region = {};
     }
     if (PrimaryBase)
private:
   };
   struct RegionInfo : UnpaddedRegionInfo {
     char Padding[SCUDO_CACHE_LINE_SIZE -
                  (sizeof(UnpaddedRegionInfo) % SCUDO_CACHE_LINE_SIZE)] = {};
   };
   static_assert(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");
 
   uptr PrimaryBase = 0;
+  // The minimum size of pushed blocks that we will try to release the pages in
+  // that size class.
+  uptr SmallerBlockReleasePageDelta = 1;
   MapPlatformData Data = {};
   atomic_s32 ReleaseToOsIntervalMs = {};
   alignas(SCUDO_CACHE_LINE_SIZE) RegionInfo RegionInfoArray[NumClasses];
 
   RegionInfo *getRegionInfo(uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     return &RegionInfoArray[ClassId];
   }
NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
     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.
 
-    bool CheckDensity = BlockSize < PageSize / 16U;
+    const bool CheckDensity = BlockSize < PageSize / 16U;
     // 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 (!Force && BytesPushed < Region->AllocatedUser / 16U)
         return 0;
     }
 
for (BatchGroup *BG = Region->FreeList.front(); BG != nullptr;) {
       // not have all caches used.
       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 && (BytesInBG * 100U) / AllocatedGroupSize <
-                              (100U - 1U - BlockSize / 16U)) {
+      if (CheckDensity) {
+        const bool HighDensity = (BytesInBG * 100U) / AllocatedGroupSize >=
+                                 (100U - 1U - BlockSize / 16U);
+        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
+        // certain amount of free memory.
+        const bool ReachReleaseDelta =
+            MayHaveReleasedAll ? true
+                               : PushedBytesDelta * BlockSize >=
+                                     PageSize * SmallerBlockReleasePageDelta;
+
+        if (!HighDensity || !ReachReleaseDelta) {
           Prev = BG;
           BG = BG->Next;
           continue;
         }
+      }
 
       // If `BG` is the first BatchGroup in the list, we only need to advance
       // `BG` and call FreeList::pop_front(). No update is needed for `Prev`.
       //
       //         (BG)   (BG->Next)
       // Prev     Cur      BG
       //   |       |       |
       //   v       v       v