[scudo] Support dumping fragmentation data in SizeClassAllocator64

[Chia-hungDuan]

Summary

This tells the number of pages that still have blocks in-used, i.e.,
those pages can't do releaseToOSMaybe(). Along with the information of
getStats() and RSS usage from the system (like smaps), we can tell if
the heuristic in releaseToOSMaybe() works well in certain scenarios.

Here's the sample output:

Fragmentation Stats: SizeClassAllocator64: page size = 4096
  01 (    32): inuse/total blocks:    275/   416 inuse/total pages:      4/     4 inuse bytes:     16K
  02 (    48): inuse/total blocks:    182/   312 inuse/total pages:      4/     4 inuse bytes:     16K
  03 (    64): inuse/total blocks:    169/   312 inuse/total pages:      5/     5 inuse bytes:     20K
  ...
  32 (  1040): inuse/total blocks:     90/   152 inuse/total pages:     37/    39 inuse bytes:    148K
  33 (  1168): inuse/total blocks:    136/   232 inuse/total pages:     64/    67 inuse bytes:    256K
  34 (  1296): inuse/total blocks:    138/   226 inuse/total pages:     68/    72 inuse bytes:    272K
  35 (  1424): inuse/total blocks:    140/   232 inuse/total pages:     78/    81 inuse bytes:    312K
  36 (  1552): inuse/total blocks:    157/   248 inuse/total pages:     89/    94 inuse bytes:    356K
  ...

SizeClassAllocator32 requires further refactoring to support this.

[Chia-hungDuan]

Add in-used bytes data

[cferris]

One minor comment suggestion.

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

316

which

[Chia-hungDuan]

Address review comment

[Chia-hungDuan]

Also dump fragmentation data when calling mallopt(M_LOG_STATS)

[cferris]

LGTM.

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

#endif
   }
 
   void printStats() {
     ScopedString Str;
     getStats(&Str);
     Str.output();
   }
 
+  void printFragmentationInfo() {
+    ScopedString Str;
+    Primary.getFragmentationInfo(&Str);
+    // Secondary allocator dumps the fragmentation data in getStats().
+    Str.output();
+  }
+
   void releaseToOS(ReleaseToOS ReleaseType) {
     initThreadMaybe();
     if (ReleaseType == ReleaseToOS::ForceAll)
       drainCaches();
     Primary.releaseToOS(ReleaseType);
     Secondary.releaseToOS();
   }
 

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

Str->append("Stats: SizeClassAllocator32: %zuM mapped in %zu allocations; "
                 TotalMapped >> 20, PoppedBlocks, PoppedBlocks - PushedBlocks);
     for (uptr I = 0; I < NumClasses; I++) {
       SizeClassInfo *Sci = getSizeClassInfo(I);
       ScopedLock L(Sci->Mutex);
       getStats(Str, I, Sci);
     }
   }
 
+  void getFragmentationInfo(ScopedString *Str) {
+    // TODO(chiahungduan): Organize the steps in releaseToOSMaybe() into
+    // functions which make the collection of fragmentation data easier.
+    Str->append("Fragmentation Stats: SizeClassAllocator32: Unsupported yet\n");
+  }
+
   bool setOption(Option O, sptr Value) {
     if (O == Option::ReleaseInterval) {
       const s32 Interval = Max(Min(static_cast<s32>(Value),
                                    Config::Primary::MaxReleaseToOsIntervalMs),
                                Config::Primary::MinReleaseToOsIntervalMs);
       atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval);
       return true;
     }

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

void getStats(ScopedString *Str) {
     for (uptr I = 0; I < NumClasses; I++) {
       RegionInfo *Region = getRegionInfo(I);
       ScopedLock L1(Region->MMLock);
       ScopedLock L2(Region->FLLock);
       getStats(Str, I, Region);
     }
   }
 
+  void getFragmentationInfo(ScopedString *Str) {
+    Str->append(
+        "Fragmentation Stats: SizeClassAllocator64: page size = %zu bytes\n",
+        getPageSizeCached());
+
+    for (uptr I = 1; I < NumClasses; I++) {
+      RegionInfo *Region = getRegionInfo(I);
+      ScopedLock L(Region->MMLock);
+      getRegionFragmentationInfo(Region, I, Str);
+    }
+  }
+
   bool setOption(Option O, sptr Value) {
     if (O == Option::ReleaseInterval) {
       const s32 Interval = Max(Min(static_cast<s32>(Value),
                                    Config::Primary::MaxReleaseToOsIntervalMs),
                                Config::Primary::MinReleaseToOsIntervalMs);
       atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval);
       return true;
     }
NOINLINE TransferBatch *populateFreeListAndPopBatch(CacheT *C, uptr ClassId,
     return B;
   }
 
   void getStats(ScopedString *Str, uptr ClassId, RegionInfo *Region)
       REQUIRES(Region->MMLock, Region->FLLock) {
     if (Region->MemMapInfo.MappedUser == 0)
       return;
     const uptr BlockSize = getSizeByClassId(ClassId);
-    const uptr InUse =
+    const uptr InUseBlocks =
         Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks;
     const uptr BytesInFreeList =
-        Region->MemMapInfo.AllocatedUser - InUse * BlockSize;
+        Region->MemMapInfo.AllocatedUser - InUseBlocks * BlockSize;
     uptr RegionPushedBytesDelta = 0;
     if (BytesInFreeList >=
         Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint) {
       RegionPushedBytesDelta =
           BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint;
     }
     const uptr TotalChunks = Region->MemMapInfo.AllocatedUser / BlockSize;
     Str->append(
         "%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
         "inuse: %6zu total: %6zu releases: %6zu last "
         "released: %6zuK latest pushed bytes: %6zuK region: 0x%zx (0x%zx)\n",
         Region->Exhausted ? "F" : " ", ClassId, getSizeByClassId(ClassId),
         Region->MemMapInfo.MappedUser >> 10, Region->FreeListInfo.PoppedBlocks,
-        Region->FreeListInfo.PushedBlocks, InUse, TotalChunks,
+        Region->FreeListInfo.PushedBlocks, InUseBlocks, TotalChunks,
         Region->ReleaseInfo.RangesReleased,
         Region->ReleaseInfo.LastReleasedBytes >> 10,
         RegionPushedBytesDelta >> 10, Region->RegionBeg,
         getRegionBaseByClassId(ClassId));
   }
 
+  void getRegionFragmentationInfo(RegionInfo *Region, uptr ClassId,
+                                  ScopedString *Str) REQUIRES(Region->MMLock) {
+    const uptr BlockSize = getSizeByClassId(ClassId);
+    const uptr AllocatedUserEnd =
+        Region->MemMapInfo.AllocatedUser + Region->RegionBeg;
+
+    SinglyLinkedList<BatchGroup> GroupsToRelease;
+    {
+      ScopedLock L(Region->FLLock);
+      GroupsToRelease = Region->FreeListInfo.BlockList;
+      Region->FreeListInfo.BlockList.clear();
+    }
+
+    FragmentationRecorder Recorder;
+    if (!GroupsToRelease.empty()) {
+      PageReleaseContext Context =
+          markFreeBlocks(Region, BlockSize, AllocatedUserEnd,
+                         getCompactPtrBaseByClassId(ClassId), GroupsToRelease);
+      auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };
+      releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
+
+      mergeGroupsToReleaseBack(Region, GroupsToRelease);
+    }
+
+    ScopedLock L(Region->FLLock);
+    const uptr PageSize = getPageSizeCached();
+    const uptr TotalBlocks = Region->MemMapInfo.AllocatedUser / BlockSize;
+    const uptr InUseBlocks =
+        Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks;
+    const uptr AllocatedPagesCount =
+        roundUp(Region->MemMapInfo.AllocatedUser, PageSize) / PageSize;
+    const uptr InUsePages =
+        AllocatedPagesCount - Recorder.getReleasedPagesCount();
+    const uptr InUseBytes = InUsePages * PageSize;
+
+    Str->append("  %02zu (%6zu): inuse/total blocks: %6zu/%6zu inuse/total "
+                "pages: %6zu/%6zu inuse bytes: %6zuK\n",
+                ClassId, BlockSize, InUseBlocks, TotalBlocks, InUsePages,
+                AllocatedPagesCount, InUseBytes >> 10);
+  }
+
   NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
                                  ReleaseToOS ReleaseType = ReleaseToOS::Normal)
       REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {
     const uptr BlockSize = getSizeByClassId(ClassId);
     uptr BytesInFreeList;
     const uptr AllocatedUserEnd =
         Region->MemMapInfo.AllocatedUser + Region->RegionBeg;
     SinglyLinkedList<BatchGroup> GroupsToRelease;

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

private:
   // Therefore, store them separately to make it work on all the platforms.
   uptr Base = 0;
   // The release offset from Base. This is used when we know a given range after
   // Base will not be released.
   uptr Offset = 0;
   MapPlatformData *Data = nullptr;
 };
 
+class FragmentationRecorder {
+public:
+  FragmentationRecorder() = default;
+
+  uptr getReleasedPagesCount() const { return ReleasedPagesCount; }
+
+  void releasePageRangeToOS(uptr From, uptr To) {
+    DCHECK_EQ((To - From) % getPageSizeCached(), 0U);
+    ReleasedPagesCount += (To - From) / getPageSizeCached();
+  }
+
+private:
+  uptr ReleasedPagesCount = 0;
+};
+
 // A buffer pool which holds a fixed number of static buffers for fast buffer
 // allocation. If the request size is greater than `StaticBufferSize`, it'll
 // delegate the allocation to map().
 template <uptr StaticBufferCount, uptr StaticBufferSize> class BufferPool {
 public:
   // Preserve 1 bit in the `Mask` so that we don't need to do zero-check while
   // extracting the least significant bit from the `Mask`.
   static_assert(StaticBufferCount < SCUDO_WORDSIZE, "");

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

for (scudo::sptr Delta = -32; Delta <= 32; Delta++) {
       EXPECT_LE(Size, Allocator->getUsableSize(P));
       memset(P, 0xaa, Size);
       checkMemoryTaggingMaybe(Allocator, P, Size, Align);
       Allocator->deallocate(P, Origin, Size);
     }
   }
 
   Allocator->printStats();
+  Allocator->printFragmentationInfo();
 }
 
 #define SCUDO_MAKE_BASIC_TEST(SizeLog)                                         \
   SCUDO_TYPED_TEST(ScudoCombinedDeathTest, BasicCombined##SizeLog) {           \
     this->BasicTest(SizeLog);                                                  \
   }
 
 SCUDO_MAKE_BASIC_TEST(0)

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

for (scudo::uptr I = 0; I < ARRAY_SIZE(Threads); I++) {
     Ready = true;
     Cv.notify_all();
   }
   for (auto &T : Threads)
     T.join();
   Allocator->releaseToOS(scudo::ReleaseToOS::Force);
   scudo::ScopedString Str;
   Allocator->getStats(&Str);
+  Allocator->getFragmentationInfo(&Str);
   Str.output();
 }
 
 // Through a simple allocation that spans two pages, verify that releaseToOS
 // actually releases some bytes (at least one page worth). This is a regression
 // test for an error in how the release criteria were computed.
 SCUDO_TYPED_TEST(ScudoPrimaryTest, ReleaseToOS) {
   using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;

compiler-rt/lib/scudo/standalone/wrappers_c.inc

INTERFACE WEAK int SCUDO_PREFIX(mallopt)(int param, int value) {
   } else if (param == M_PURGE) {
     SCUDO_ALLOCATOR.releaseToOS(scudo::ReleaseToOS::Force);
     return 1;
   } else if (param == M_PURGE_ALL) {
     SCUDO_ALLOCATOR.releaseToOS(scudo::ReleaseToOS::ForceAll);
     return 1;
   } else if (param == M_LOG_STATS) {
     SCUDO_ALLOCATOR.printStats();
+    SCUDO_ALLOCATOR.printFragmentationInfo();
     return 1;
   } else {
     scudo::Option option;
     switch (param) {
     case M_MEMTAG_TUNING:
       option = scudo::Option::MemtagTuning;
       break;
     case M_THREAD_DISABLE_MEM_INIT: