[scudo][standalone] Correct releaseToOS behavior

[cryptoad]

Summary

There was an issue in releaseToOSMaybe: one of the criteria to
decide if we should proceed with the release was wrong. Namely:

const uptr N = Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks;
if (N * BlockSize < PageSize)
  return; // No chance to release anything.

I meant to check if the amount of bytes in the free list was lower
than a page, but this actually checks if the amount of in use bytes
was lower than a page.

The correct code is:

const uptr BytesInFreeList =
  Region->AllocatedUser -
  (Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks) * BlockSize;
if (BytesInFreeList < PageSize)
  return 0; // No chance to release anything.

Consequences of the bug:

• if a class size has less than a page worth of in-use bytes (allocated or in a cache), reclaiming would not occur, whatever the amount of blocks in the free list; in real world scenarios this is unlikely to happen and be impactful;
• if a class size had less than a page worth of free bytes (and enough in-use bytes, etc), then reclaiming would be attempted, with likely no result. This means the reclaiming was overzealous at times.

I didn't have a good way to test for this, so I changed the prototype
of the function to return the number of bytes released, allowing to
get the information needed. The test added fails with the initial
criteria.

Another issue is that ReleaseToOsInterval can actually be 0, meaning
we always try to release (side note: it's terrible for performances).
so change a > 0 check to >= 0.

Additionally, decrease the CanRelease threshold to PageSize / 32.
I still have to make that configurable but I will do it at another time.

Finally, rename some variables in printStats: I feel like "available"
was too ambiguous, so change it to "total".

[cryptoad]

Add a couple of EXPECT to the test.

[morehouse]

lib/scudo/standalone/tests/primary_test.cpp

195

Does this test the two cases mentioned in the description?

• < 1 page in use, > 1 page in free list (should release)
• < 1 page in free list (shouldn't release)

[cryptoad]

lib/scudo/standalone/tests/primary_test.cpp

195

Indeed, this tests the aforementioned first case, not the second one.
I don't think I have a way to test that from here. One of the indicators being LastReleaseAtNs being updated (without released bytes), and it's not accessible.
I'll see if I can toy with the prototype some more to bubble the information up the chain, unless you have an idea.

[morehouse]

lib/scudo/standalone/tests/primary_test.cpp

195

Is there a way to glean unmapped/released bytes from GlobalStats? If not, it seems like something worth adding to Scudo's telemetry.

I also see there's already a printStats method. Perhaps we could modify it to print into a buffer where we could extract the released metadata.

[cryptoad]

lib/scudo/standalone/tests/primary_test.cpp

195

So the plan of record on my side:

• Landing this as is, fixing the issue at hand takes precedence
• I am going to have to revisit how to fit the release stats in the mix: the primary's releaseToOS doesn't grab a cache, so we can't fit the stats in there; We could put the total of released bytes in regions data, but that departs from the model of all the other stats being the caches. Maybe do that globally indeed, that will require more thought.
• for the printStats suggestion: it is something I have to do as well, for mallocz purposes for example. Technically this could be leveraged through a lit test in it's current form I think, but right now I only have unit tests. So lit tests is also on my plate.

lib/scudo/standalone/primary32.h

if (UNLIKELY(!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed))))
       Seed =
           static_cast<u32>(getMonotonicTime() ^
                            (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 = (ReleaseToOsInterval > 0) &&
+      Sci->CanRelease = (ReleaseToOsInterval >= 0) &&
                         (I != SizeClassMap::BatchClassId) &&
-                        (getSizeByClassId(I) >= (PageSize / 16));
+                        (getSizeByClassId(I) >= (PageSize / 32));
     }
     ReleaseToOsIntervalMs = ReleaseToOsInterval;
   }
   void init(s32 ReleaseToOsInterval) {
     memset(this, 0, sizeof(*this));
     initLinkerInitialized(ReleaseToOsInterval);
   }
 
void printStats() {
     }
     Printf("Stats: SizeClassAllocator32: %zuM mapped in %zu allocations; "
            "remains %zu\n",
            TotalMapped >> 20, PoppedBlocks, PoppedBlocks - PushedBlocks);
     for (uptr I = 0; I < NumClasses; I++)
       printStats(I, 0);
   }
 
-  void releaseToOS() {
+  uptr releaseToOS() {
+    uptr TotalReleasedBytes = 0;
     for (uptr I = 0; I < NumClasses; I++) {
       if (I == SizeClassMap::BatchClassId)
         continue;
       SizeClassInfo *Sci = getSizeClassInfo(I);
       ScopedLock L(Sci->Mutex);
-      releaseToOSMaybe(Sci, I, /*Force=*/true);
+      TotalReleasedBytes += releaseToOSMaybe(Sci, I, /*Force=*/true);
     }
+    return TotalReleasedBytes;
   }
 
 private:
   static const uptr NumClasses = SizeClassMap::NumClasses;
   static const uptr RegionSize = 1UL << RegionSizeLog;
   static const uptr NumRegions = SCUDO_MMAP_RANGE_SIZE >> RegionSizeLog;
 #if SCUDO_WORDSIZE == 32U
   typedef FlatByteMap<NumRegions> ByteMap;
void printStats(uptr ClassId, uptr Rss) {
     const uptr AvailableChunks = Sci->AllocatedUser / getSizeByClassId(ClassId);
     Printf("  %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu inuse: %6zu"
            " avail: %6zu rss: %6zuK\n",
            ClassId, getSizeByClassId(ClassId), Sci->AllocatedUser >> 10,
            Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks, InUse,
            AvailableChunks, Rss >> 10);
   }
 
-  NOINLINE void releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
+  NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
                                  bool Force = false) {
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr PageSize = getPageSizeCached();
 
     CHECK_GE(Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks);
-    const uptr N = Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks;
-    if (N * BlockSize < PageSize)
-      return; // No chance to release anything.
+    const uptr BytesInFreeList =
+        Sci->AllocatedUser -
+        (Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks) * BlockSize;
+    if (BytesInFreeList < PageSize)
+      return 0; // No chance to release anything.
     if ((Sci->Stats.PushedBlocks - Sci->ReleaseInfo.PushedBlocksAtLastRelease) *
             BlockSize <
         PageSize) {
-      return; // Nothing new to release.
+      return 0; // Nothing new to release.
     }
 
     if (!Force) {
       const s32 IntervalMs = ReleaseToOsIntervalMs;
       if (IntervalMs < 0)
-        return;
+        return 0;
       if (Sci->ReleaseInfo.LastReleaseAtNs +
               static_cast<uptr>(IntervalMs) * 1000000ULL >
           getMonotonicTime()) {
-        return; // Memory was returned recently.
+        return 0; // Memory was returned recently.
       }
     }
 
     // TODO(kostyak): currently not ideal as we loop over all regions and
     // iterate multiple times over the same freelist if a ClassId spans multiple
     // regions. But it will have to do for now.
+    uptr TotalReleasedBytes = 0;
     for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) {
       if (PossibleRegions[I] == ClassId) {
         ReleaseRecorder Recorder(I * RegionSize);
         releaseFreeMemoryToOS(&Sci->FreeList, I * RegionSize,
                               RegionSize / PageSize, 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.LastReleaseAtNs = getMonotonicTime();
+    return TotalReleasedBytes;
   }
 
   SizeClassInfo SizeClassInfoArray[NumClasses];
 
   ByteMap PossibleRegions;
   // Keep track of the lowest & highest regions allocated to avoid looping
   // through the whole NumRegions.
   uptr MinRegionIndex;

lib/scudo/standalone/primary64.h

for (uptr I = 0; I < NumClasses; I++) {
           getRegionBaseByClassId(I) + (getRandomModN(&Seed, 16) + 1) * PageSize;
       // 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 = (ReleaseToOsInterval > 0) &&
+      Region->CanRelease = (ReleaseToOsInterval >= 0) &&
                            (I != SizeClassMap::BatchClassId) &&
-                           (getSizeByClassId(I) >= (PageSize / 16));
+                           (getSizeByClassId(I) >= (PageSize / 32));
       Region->RandState = getRandomU32(&Seed);
     }
     ReleaseToOsIntervalMs = ReleaseToOsInterval;
   }
   void init(s32 ReleaseToOsInterval) {
     memset(this, 0, sizeof(*this));
     initLinkerInitialized(ReleaseToOsInterval);
   }
void printStats() const {
     Printf("Stats: Primary64: %zuM mapped (%zuM rss) in %zu allocations; "
            "remains %zu\n",
            TotalMapped >> 20, 0, PoppedBlocks, PoppedBlocks - PushedBlocks);
 
     for (uptr I = 0; I < NumClasses; I++)
       printStats(I, 0);
   }
 
-  void releaseToOS() {
+  uptr releaseToOS() {
+    uptr TotalReleasedBytes = 0;
     for (uptr I = 0; I < NumClasses; I++) {
       if (I == SizeClassMap::BatchClassId)
         continue;
       RegionInfo *Region = getRegionInfo(I);
       ScopedLock L(Region->Mutex);
-      releaseToOSMaybe(Region, I, /*Force=*/true);
+      TotalReleasedBytes += releaseToOSMaybe(Region, I, /*Force=*/true);
     }
+    return TotalReleasedBytes;
   }
 
 private:
   static const uptr RegionSize = 1UL << RegionSizeLog;
   static const uptr NumClasses = SizeClassMap::NumClasses;
   static const uptr PrimarySize = RegionSize * NumClasses;
 
   // Call map for user memory with at least this size.
NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId,
                                            RegionInfo *Region) {
     const uptr Size = getSizeByClassId(ClassId);
     const u32 MaxCount = TransferBatch::getMaxCached(Size);
 
     const uptr RegionBeg = Region->RegionBeg;
     const uptr MappedUser = Region->MappedUser;
     const uptr TotalUserBytes = Region->AllocatedUser + MaxCount * Size;
     // Map more space for blocks, if necessary.
-    if (LIKELY(TotalUserBytes > MappedUser)) {
+    if (TotalUserBytes > MappedUser) {
       // Do the mmap for the user memory.
       const uptr UserMapSize =
           roundUpTo(TotalUserBytes - MappedUser, MapSizeIncrement);
       const uptr RegionBase = RegionBeg - getRegionBaseByClassId(ClassId);
       if (UNLIKELY(RegionBase + MappedUser + UserMapSize > RegionSize)) {
         if (!Region->Exhausted) {
           Region->Exhausted = true;
           printStats();
NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId,
     return B;
   }
 
   void printStats(uptr ClassId, uptr Rss) const {
     RegionInfo *Region = getRegionInfo(ClassId);
     if (Region->MappedUser == 0)
       return;
     const uptr InUse = Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks;
-    const uptr AvailableChunks =
-        Region->AllocatedUser / getSizeByClassId(ClassId);
+    const uptr TotalChunks = Region->AllocatedUser / getSizeByClassId(ClassId);
     Printf("%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu inuse: "
-           "%6zu avail: %6zu rss: %6zuK releases: %6zu last released: %6zuK "
+           "%6zu total: %6zu rss: %6zuK releases: %6zu last released: %6zuK "
            "region: 0x%zx (0x%zx)\n",
            Region->Exhausted ? "F" : " ", ClassId, getSizeByClassId(ClassId),
            Region->MappedUser >> 10, Region->Stats.PoppedBlocks,
-           Region->Stats.PushedBlocks, InUse, AvailableChunks, Rss >> 10,
+           Region->Stats.PushedBlocks, InUse, TotalChunks, Rss >> 10,
            Region->ReleaseInfo.RangesReleased,
            Region->ReleaseInfo.LastReleasedBytes >> 10, Region->RegionBeg,
            getRegionBaseByClassId(ClassId));
   }
 
-  NOINLINE void releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
+  NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
                                  bool Force = false) {
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr PageSize = getPageSizeCached();
 
     CHECK_GE(Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks);
-    const uptr N = Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks;
-    if (N * BlockSize < PageSize)
-      return; // No chance to release anything.
+    const uptr BytesInFreeList =
+        Region->AllocatedUser -
+        (Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks) * BlockSize;
+    if (BytesInFreeList < PageSize)
+      return 0; // No chance to release anything.
     if ((Region->Stats.PushedBlocks -
          Region->ReleaseInfo.PushedBlocksAtLastRelease) *
             BlockSize <
         PageSize) {
-      return; // Nothing new to release.
+      return 0; // Nothing new to release.
     }
 
     if (!Force) {
       const s32 IntervalMs = ReleaseToOsIntervalMs;
       if (IntervalMs < 0)
-        return;
+        return 0;
       if (Region->ReleaseInfo.LastReleaseAtNs +
               static_cast<uptr>(IntervalMs) * 1000000ULL >
           getMonotonicTime()) {
-        return; // Memory was returned recently.
+        return 0; // Memory was returned recently.
       }
     }
 
     ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data);
     releaseFreeMemoryToOS(&Region->FreeList, Region->RegionBeg,
                           roundUpTo(Region->AllocatedUser, PageSize) / PageSize,
                           BlockSize, &Recorder);
 
     if (Recorder.getReleasedRangesCount() > 0) {
       Region->ReleaseInfo.PushedBlocksAtLastRelease =
           Region->Stats.PushedBlocks;
       Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
       Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
     }
     Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
+    return Recorder.getReleasedBytes();
   }
 };
 
 } // namespace scudo
 
 #endif // SCUDO_PRIMARY64_H_

lib/scudo/standalone/tests/primary_test.cpp

template <typename Primary> static void testPrimaryThreaded() {
   Allocator->printStats();
 }
 
 TEST(ScudoPrimaryTest, PrimaryThreaded) {
   using SizeClassMap = scudo::SvelteSizeClassMap;
   testPrimaryThreaded<scudo::SizeClassAllocator32<SizeClassMap, 18U>>();
   testPrimaryThreaded<scudo::SizeClassAllocator64<SizeClassMap, 24U>>();
 }
+
+// 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.
+template <typename Primary> static void testReleaseToOS() {
+  auto Deleter = [](Primary *P) {
+    P->unmapTestOnly();
+    delete P;
+  };
+  std::unique_ptr<Primary, decltype(Deleter)> Allocator(new Primary, Deleter);
+  Allocator->init(/*ReleaseToOsInterval=*/-1);
+  typename Primary::CacheT Cache;
+  Cache.init(nullptr, Allocator.get());
+  const scudo::uptr PageSize = scudo::getPageSizeCached();
+  const scudo::uptr ClassId =
+      Primary::SizeClassMap::getClassIdBySize(PageSize * 2);
+  void *P = Cache.allocate(ClassId);
+  Cache.deallocate(ClassId, P);
+  Cache.destroy(nullptr);
+  EXPECT_GT(Allocator->releaseToOS(), 0U);
+}
+
+TEST(ScudoPrimaryTest, ReleaseToOS) {
+  using SizeClassMap = scudo::DefaultSizeClassMap;
+  testReleaseToOS<scudo::SizeClassAllocator32<SizeClassMap, 18U>>();
+  testReleaseToOS<scudo::SizeClassAllocator64<SizeClassMap, 24U>>();
+}