[scudo][standalone] Skip irrelevant regions during release

[cryptoad]

Summary

With the 'new' way of releasing on 32-bit, we iterate through all the
regions in between First and Last, which covers regions that do not
belong to the class size we are working with. This is effectively wasted
cycles.

With this change, we add a SkipRegion lambda to releaseFreeMemoryToOS
that will allow the release function to know when to skip a region.
For the 64-bit primary, since we are only working with 1 region, we never
skip.

[cryptoad]

I am unclear if there is a way for the lambda to be inlined in the callee.
If anyone has a suggestion, I'll gladly take it.

[cryptoad]

In D86399#2231990, @cryptoad wrote:

I am unclear if there is a way for the lambda to be inlined in the callee.
If anyone has a suggestion, I'll gladly take it.

Nevermind this, it is actually inlined.

[vitalybuka]

In D86399#2232555, @cryptoad wrote:

In D86399#2231990, @cryptoad wrote:

I am unclear if there is a way for the lambda to be inlined in the callee.
If anyone has a suggestion, I'll gladly take it.

Nevermind this, it is actually inlined.

Interesting that GCC does not inline capture by ref https://godbolt.org/z/exfP69

[cryptoad]

In D86399#2232864, @vitalybuka wrote:

Interesting that GCC does not inline capture by ref https://godbolt.org/z/exfP69

Would you recommend some change to ensure inlining?

[hctim]

LGTM.

In D86399#2233735, @cryptoad wrote:

In D86399#2232864, @vitalybuka wrote:

Interesting that GCC does not inline capture by ref https://godbolt.org/z/exfP69

Would you recommend some change to ensure inlining?

There's no capture by ref here - so not a problem?

[vitalybuka]

In D86399#2233735, @cryptoad wrote:

In D86399#2232864, @vitalybuka wrote:

Interesting that GCC does not inline capture by ref https://godbolt.org/z/exfP69

Would you recommend some change to ensure inlining?

LGTM. I was curious after your question and experimented a little.

[cferris]

I verified that this appears to fix the problem we've seen, the max release was about 6ms, and that was way larger than most of the other releases.

In addition, I ran the cts test that was a slowdown before, and that ran in about the same time frame as before the change. I ran the traces too, and all numbers stayed within normal operations. I didn't run all of the smaller benchmarks since it didn't seem necessary.

I also ran all of the android tests, and everything passed.

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

NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
     uptr Last = 0;
     for (uptr I = MaxRegionIndex; I >= MinRegionIndex; I--) {
       if (PossibleRegions[I] - 1U == ClassId) {
         Last = I;
         break;
       }
     }
     uptr TotalReleasedBytes = 0;
+    auto SkipRegion = [this, First, ClassId](uptr RegionIndex) {
+      return (PossibleRegions[First + RegionIndex] - 1U) != ClassId;
+    };
     if (First && Last) {
       const uptr Base = First * RegionSize;
       const uptr NumberOfRegions = Last - First + 1U;
       ReleaseRecorder Recorder(Base);
       releaseFreeMemoryToOS(Sci->FreeList, Base, RegionSize, NumberOfRegions,
-                            BlockSize, &Recorder);
+                            BlockSize, &Recorder, SkipRegion);
       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();

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

if (!Force) {
         return 0;
       if (Region->ReleaseInfo.LastReleaseAtNs +
               static_cast<u64>(IntervalMs) * 1000000 >
           getMonotonicTime()) {
         return 0; // Memory was returned recently.
       }
     }
 
+    auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };
     ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data);
     releaseFreeMemoryToOS(Region->FreeList, Region->RegionBeg,
-                          Region->AllocatedUser, 1U, BlockSize, &Recorder);
+                          Region->AllocatedUser, 1U, BlockSize, &Recorder,
+                          SkipRegion);
 
     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_

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

if (Freed) {
         InRange = true;
       }
     } else {
       closeOpenedRange();
     }
     CurrentPage++;
   }
 
+  void skipPages(uptr N) {
+    closeOpenedRange();
+    CurrentPage += N;
+  }
+
   void finish() { closeOpenedRange(); }
 
 private:
   void closeOpenedRange() {
     if (InRange) {
       Recorder->releasePageRangeToOS((CurrentRangeStatePage << PageSizeLog),
                                      (CurrentPage << PageSizeLog));
       InRange = false;
     }
   }
 
   ReleaseRecorderT *const Recorder;
   const uptr PageSizeLog;
   bool InRange = false;
   uptr CurrentPage = 0;
   uptr CurrentRangeStatePage = 0;
 };
 
-template <class TransferBatchT, class ReleaseRecorderT>
+template <class TransferBatchT, class ReleaseRecorderT, typename SkipRegionT>
 NOINLINE void
 releaseFreeMemoryToOS(const IntrusiveList<TransferBatchT> &FreeList, uptr Base,
                       uptr RegionSize, uptr NumberOfRegions, uptr BlockSize,
-                      ReleaseRecorderT *Recorder) {
+                      ReleaseRecorderT *Recorder, SkipRegionT SkipRegion) {
   const uptr PageSize = getPageSizeCached();
 
   // Figure out the number of chunks per page and whether we can take a fast
   // path (the number of chunks per page is the same for all pages).
   uptr FullPagesBlockCountMax;
   bool SameBlockCountPerPage;
   if (BlockSize <= PageSize) {
     if (PageSize % BlockSize == 0) {
if (BlockSize <= PageSize && PageSize % BlockSize == 0) {
     }
   }
 
   // Iterate over pages detecting ranges of pages with chunk Counters equal
   // to the expected number of chunks for the particular page.
   FreePagesRangeTracker<ReleaseRecorderT> RangeTracker(Recorder);
   if (SameBlockCountPerPage) {
     // Fast path, every page has the same number of chunks affecting it.
-    for (uptr I = 0; I < NumberOfRegions; I++)
+    for (uptr I = 0; I < NumberOfRegions; I++) {
+      if (SkipRegion(I)) {
+        RangeTracker.skipPages(PagesCount);
+        continue;
+      }
       for (uptr J = 0; J < PagesCount; J++)
         RangeTracker.processNextPage(Counters.get(I, J) ==
                                      FullPagesBlockCountMax);
+    }
   } else {
     // Slow path, go through the pages keeping count how many chunks affect
     // each page.
     const uptr Pn = BlockSize < PageSize ? PageSize / BlockSize : 1;
     const uptr Pnc = Pn * BlockSize;
     // The idea is to increment the current page pointer by the first chunk
     // size, middle portion size (the portion of the page covered by chunks
     // except the first and the last one) and then the last chunk size, adding
     // up the number of chunks on the current page and checking on every step
     // whether the page boundary was crossed.
     for (uptr I = 0; I < NumberOfRegions; I++) {
+      if (SkipRegion(I)) {
+        RangeTracker.skipPages(PagesCount);
+        continue;
+      }
       uptr PrevPageBoundary = 0;
       uptr CurrentBoundary = 0;
       for (uptr J = 0; J < PagesCount; J++) {
         const uptr PageBoundary = PrevPageBoundary + PageSize;
         uptr BlocksPerPage = Pn;
         if (CurrentBoundary < PageBoundary) {
           if (CurrentBoundary > PrevPageBoundary)
             BlocksPerPage++;

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

for (auto const &Block : FreeArray) {
         FreeList.push_back(CurrentBatch);
       }
       CurrentBatch->add(Block);
       if (CurrentBatch->getCount() == Batch::MaxCount)
         CurrentBatch = nullptr;
     }
 
     // Release the memory.
+    auto SkipRegion = [](UNUSED scudo::uptr RegionIndex) { return false; };
     ReleasedPagesRecorder Recorder;
     releaseFreeMemoryToOS(FreeList, 0, MaxBlocks * BlockSize, 1U, BlockSize,
-                          &Recorder);
+                          &Recorder, SkipRegion);
 
     // Verify that there are no released pages touched by used chunks and all
     // ranges of free chunks big enough to contain the entire memory pages had
     // these pages released.
     scudo::uptr VerifiedReleasedPages = 0;
     std::set<scudo::uptr> FreeBlocks(FreeArray.begin(), FreeArray.end());
 
     scudo::uptr CurrentBlock = 0;