[scudo][standalone] Force release after burst of deallocs

[cryptoad]

Summary

Some situations are fairly adversarial to Scudo, notably when there is
a lot of allocations in a small class size followed by deallocations.
Since we do not release those except on forced-release, we end up with
a higher RSS that's not going away.

Since releasing smaller classes is expensive (on 32-bit), I tried to
find the most balanced way to proceed. The point of this change is to
force-release classes when the % of freed chunks in a class size is very
high (in the 9x% area), and if the number of blocks pushed in the
freelist since last release is also high (I set that to 25%).

A very small size class (16 bytes) won't release significant memory
unless it's mostly empty (98-99%) due to randomization.

There is a small drawback when an application does an M_PURGE shortly
after a burst a deallocation, then we end up going through the release
code twice as we still want to fulfill the release request, and it turns
out to be a net slowdown on some 32-bit benchmarks.

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

private:
   NOINLINE bool refill(PerClass *C, uptr ClassId) {
     initCacheMaybe(C);
     TransferBatch *B = Allocator->popBatch(this, ClassId);
     if (UNLIKELY(!B))
       return false;
     DCHECK_GT(B->getCount(), 0);
     C->Count = B->getCount();
     B->copyToArray(C->Chunks);
+    B->clear();
     destroyBatch(ClassId, B);
     return true;
   }
 
   NOINLINE void drain(PerClass *C, uptr ClassId) {
     const u32 Count = Min(C->MaxCount / 2, C->Count);
     TransferBatch *B = createBatch(ClassId, C->Chunks[0]);
     if (UNLIKELY(!B))

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

void initLinkerInitialized(s32 ReleaseToOsInterval) {
     PossibleRegions.initLinkerInitialized();
     MinRegionIndex = NumRegions; // MaxRegionIndex is already initialized to 0.
 
     u32 Seed;
     const u64 Time = getMonotonicTime();
     if (UNLIKELY(!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed))))
       Seed = static_cast<u32>(
           Time ^ (reinterpret_cast<uptr>(SizeClassInfoArray) >> 6));
-    const uptr PageSize = getPageSizeCached();
     for (uptr I = 0; I < NumClasses; I++) {
       SizeClassInfo *Sci = getSizeClassInfo(I);
       Sci->RandState = getRandomU32(&Seed);
       // See comment in the 64-bit primary about releasing smaller size classes.
-      Sci->CanRelease = (I != SizeClassMap::BatchClassId) &&
-                        (getSizeByClassId(I) >= (PageSize / 32));
-      if (Sci->CanRelease)
+      Sci->UseInterval = (getSizeByClassId(I) >= 128U);
+      if (Sci->UseInterval)
         Sci->ReleaseInfo.LastReleaseAtNs = Time;
     }
     setReleaseToOsIntervalMs(ReleaseToOsInterval);
   }
   void init(s32 ReleaseToOsInterval) {
     memset(this, 0, sizeof(*this));
     initLinkerInitialized(ReleaseToOsInterval);
   }
public:
 
   void pushBatch(uptr ClassId, TransferBatch *B) {
     DCHECK_LT(ClassId, NumClasses);
     DCHECK_GT(B->getCount(), 0);
     SizeClassInfo *Sci = getSizeClassInfo(ClassId);
     ScopedLock L(Sci->Mutex);
     Sci->FreeList.push_front(B);
     Sci->Stats.PushedBlocks += B->getCount();
-    if (Sci->CanRelease)
+    if (ClassId != SizeClassMap::BatchClassId)
       releaseToOSMaybe(Sci, ClassId);
   }
 
   void disable() {
     // The BatchClassId must be locked last since other classes can use it.
     for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {
       if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)
         continue;
private:
   };
 
   struct alignas(SCUDO_CACHE_LINE_SIZE) SizeClassInfo {
     HybridMutex Mutex;
     SinglyLinkedList<TransferBatch> FreeList;
     uptr CurrentRegion;
     uptr CurrentRegionAllocated;
     SizeClassStats Stats;
-    bool CanRelease;
+    bool UseInterval;
     u32 RandState;
     uptr AllocatedUser;
     ReleaseToOsInfo ReleaseInfo;
   };
   static_assert(sizeof(SizeClassInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");
 
   uptr computeRegionId(uptr Mem) {
     const uptr Id = Mem >> RegionSizeLog;
NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
     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.
 
+    // Force a release if the number of bytes pushed since the last release and
+    // the number of bytes in the freelist are above given percentages of the
+    // allocated bytes for that class size, which usually indicates a burst in
+    // deallocation.
+    if (!Force && BytesPushed > (Sci->AllocatedUser / 4U) &&
+        (BytesInFreeList / (Sci->AllocatedUser / 100U)) >
+            (100U - getMostSignificantSetBitIndex(BlockSize)))
+      Force = true;
+
     if (!Force) {
+      if (!Sci->UseInterval)
+        return 0;
       const s32 IntervalMs = getReleaseToOsIntervalMs();
       if (IntervalMs < 0)
         return 0;
       if (Sci->ReleaseInfo.LastReleaseAtNs +
               static_cast<u64>(IntervalMs) * 1000000 >
           getMonotonicTime()) {
         return 0; // Memory was returned recently.
       }
for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) {
         // only need to release up to CurrentRegionAllocated, MaxSize otherwise.
         const uptr Size = (Region == Sci->CurrentRegion)
                               ? Sci->CurrentRegionAllocated
                               : MaxSize;
         ReleaseRecorder Recorder(Region);
         releaseFreeMemoryToOS(Sci->FreeList, Region, Size, BlockSize,
                               &Recorder);
         if (Recorder.getReleasedRangesCount() > 0) {
-          Sci->ReleaseInfo.PushedBlocksAtLastRelease = Sci->Stats.PushedBlocks;
           Sci->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
           Sci->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
           TotalReleasedBytes += Sci->ReleaseInfo.LastReleasedBytes;
         }
       }
     }
+    Sci->ReleaseInfo.PushedBlocksAtLastRelease = Sci->Stats.PushedBlocks;
+    if (Sci->UseInterval)
       Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
     return TotalReleasedBytes;
   }
 
   SizeClassInfo SizeClassInfoArray[NumClasses];
 
   // Track the regions in use, 0 is unused, otherwise store ClassId + 1.
   ByteMap PossibleRegions;
   // Keep track of the lowest & highest regions allocated to avoid looping

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

for (uptr I = 0; I < NumClasses; I++) {
       Region->RandState = getRandomU32(&Seed);
       // Releasing smaller size classes doesn't necessarily yield to a
       // meaningful RSS impact: there are more blocks per page, they are
       // randomized around, and thus pages are less likely to be entirely empty.
       // On top of this, attempting to release those require more iterations and
       // memory accesses which ends up being fairly costly. The current lower
       // limit is mostly arbitrary and based on empirical observations.
       // TODO(kostyak): make the lower limit a runtime option
-      Region->CanRelease = (I != SizeClassMap::BatchClassId) &&
-                           (getSizeByClassId(I) >= (PageSize / 32));
-      if (Region->CanRelease)
+      Region->UseInterval = (getSizeByClassId(I) >= 128U);
+      if (Region->UseInterval)
         Region->ReleaseInfo.LastReleaseAtNs = Time;
     }
     setReleaseToOsIntervalMs(ReleaseToOsInterval);
 
     if (SupportsMemoryTagging)
       UseMemoryTagging = systemSupportsMemoryTagging();
   }
   void init(s32 ReleaseToOsInterval) {
public:
   }
 
   void pushBatch(uptr ClassId, TransferBatch *B) {
     DCHECK_GT(B->getCount(), 0);
     RegionInfo *Region = getRegionInfo(ClassId);
     ScopedLock L(Region->Mutex);
     Region->FreeList.push_front(B);
     Region->Stats.PushedBlocks += B->getCount();
-    if (Region->CanRelease)
+    if (ClassId != SizeClassMap::BatchClassId)
       releaseToOSMaybe(Region, ClassId);
   }
 
   void disable() {
     // The BatchClassId must be locked last since other classes can use it.
     for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {
       if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)
         continue;
struct ReleaseToOsInfo {
     uptr LastReleasedBytes;
     u64 LastReleaseAtNs;
   };
 
   struct UnpaddedRegionInfo {
     HybridMutex Mutex;
     SinglyLinkedList<TransferBatch> FreeList;
     RegionStats Stats;
-    bool CanRelease;
+    bool UseInterval;
     bool Exhausted;
     u32 RandState;
     uptr RegionBeg;
     uptr MappedUser;    // Bytes mapped for user memory.
     uptr AllocatedUser; // Bytes allocated for user memory.
     MapPlatformData Data;
     ReleaseToOsInfo ReleaseInfo;
   };
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.
 
+    // Force a release if the number of bytes pushed since the last release and
+    // the number of bytes in the freelist are above given percentages of the
+    // allocated bytes for that class size, which usually indicates a burst in
+    // deallocation.
+    if (!Force && BytesPushed > (Region->AllocatedUser / 4U) &&
+        (BytesInFreeList / (Region->AllocatedUser / 100U)) >
+            (100U - getMostSignificantSetBitIndex(BlockSize)))
+      Force = true;
+
     if (!Force) {
+      if (!Region->UseInterval)
+        return 0;
       const s32 IntervalMs = getReleaseToOsIntervalMs();
       if (IntervalMs < 0)
         return 0;
       if (Region->ReleaseInfo.LastReleaseAtNs +
               static_cast<u64>(IntervalMs) * 1000000 >
           getMonotonicTime()) {
         return 0; // Memory was returned recently.
       }
     }
 
     ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data);
     releaseFreeMemoryToOS(Region->FreeList, Region->RegionBeg,
                           Region->AllocatedUser, BlockSize, &Recorder);
 
     if (Recorder.getReleasedRangesCount() > 0) {
-      Region->ReleaseInfo.PushedBlocksAtLastRelease =
-          Region->Stats.PushedBlocks;
       Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
       Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
     }
+    Region->ReleaseInfo.PushedBlocksAtLastRelease = Region->Stats.PushedBlocks;
+    if (Region->UseInterval)
       Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
     return Recorder.getReleasedBytes();
   }
 };
 
 } // namespace scudo
 
 #endif // SCUDO_PRIMARY64_H_