[scudo][standalone] Change the release loop for efficiency purposes

[cryptoad]

Summary

On 32-b, the release algo loops multiple times over the freelist for a size
class, which lead to a decrease in performance when there were a lot of free
blocks.

This changes the release functions to loop only once over the freelist, at the
cost of using a little bit more memory for the release process: instead of
working on one region at a time, we pass the whole memory area covered by all
the regions for a given size class, and work on sub-areas of RegionSize in
this large area. For 64-b, we just have 1 sub-area encompassing the whole
region. Of course, not all the sub-areas within that large memory area will
belong to the class id we are working on, but those will just be left untouched
(which will not add to the RSS during the release process).

[cryptoad]

I didn't merge properly, updating the CL.

[cryptoad]

With proper merge of the primary*.h.

[cryptoad]

With proper merge of the primary*.h.

[cryptoad]

Corrected a bunch of things as apparently getting right into things
post vacation yielded a bunch of errors.

[cferris]

I verified that this does not result in any loss in performance or RSS on Android. I also verified that this fixes the slow run of the test suite and that none of the tests cause a long os release.

[pcc]

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

270

I guess this is equivalent to the code previously on lines 252-253. But I'm confused about why we would have more than one of these. In my mind these blocks would consume as much of the region as possible, which means that at the end we would just have a fraction of a block at most. Is that not the case?

[cryptoad]

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

270

I went for something generic, and I think you are right in the sense that the loop will only iterate once. I will verify it and update it if it's the case.

[cryptoad]

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

270

I ran some tests, and I was wrong. There cases where there is more than 1 block.
This is because we use AllocatedUser as the region size, which might not be a multiple of a page (it's bound by a maximum # of batches we want to allocate at a time), so there are several circumstances where there would be more than one block in the last page. Here are some examples that got logged on Android:
block size, last block, region size, rounded region size
320, 173e0, 17700, 18000
1c0, 5e800, 5e9c0, 5f000
120, baf60, bb080, bc000

So the loop ends up necessary.

[pcc]

LGTM

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

270

I see. This is fine then, but I wonder whether there's some way that we can avoid wasting space at the end of the region like this. This is follow-up territory of course though.

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

if (!Force) {
         return 0;
       if (Sci->ReleaseInfo.LastReleaseAtNs +
               static_cast<u64>(IntervalMs) * 1000000 >
           getMonotonicTime()) {
         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;
-    const uptr MaxSize = (RegionSize / BlockSize) * BlockSize;
+    DCHECK_GT(MinRegionIndex, 0U);
+    uptr First = 0;
     for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) {
       if (PossibleRegions[I] - 1U == ClassId) {
-        const uptr Region = I * RegionSize;
-        // If the region is the one currently associated to the size-class, we
-        // 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;
-        }
-      }
-    }
+        First = I;
+        break;
+      }
+    }
+    uptr Last = 0;
+    for (uptr I = MaxRegionIndex; I >= MinRegionIndex; I--) {
+      if (PossibleRegions[I] - 1U == ClassId) {
+        Last = I;
+        break;
+      }
+    }
+    uptr TotalReleasedBytes = 0;
+    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);
     Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
     return TotalReleasedBytes;
   }
 
   SizeClassInfo SizeClassInfoArray[NumClasses];
 
   // Track the regions in use, 0 is unused, otherwise store ClassId + 1.
   ByteMap PossibleRegions;

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

if (!Force) {
               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);
+                          Region->AllocatedUser, 1U, 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_

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

 // fails (the buffer is too small or already locked), will allocate the
 // required Buffer via map(). The caller is expected to check whether the
 // initialization was successful by checking isAllocated() result. For
 // performance sake, none of the accessors check the validity of the arguments,
 // It is assumed that Index is always in [0, N) range and the value is not
 // incremented past MaxValue.
 class PackedCounterArray {
 public:
-  PackedCounterArray(uptr NumCounters, uptr MaxValue) : N(NumCounters) {
+  PackedCounterArray(uptr NumberOfRegions, uptr CountersPerRegion,
+                     uptr MaxValue)
+      : Regions(NumberOfRegions), NumCounters(CountersPerRegion) {
+    CHECK_GT(Regions, 0);
     CHECK_GT(NumCounters, 0);
     CHECK_GT(MaxValue, 0);
     constexpr uptr MaxCounterBits = sizeof(*Buffer) * 8UL;
     // Rounding counter storage size up to the power of two allows for using
     // bit shifts calculating particular counter's Index and offset.
     const uptr CounterSizeBits =
         roundUpToPowerOfTwo(getMostSignificantSetBitIndex(MaxValue) + 1);
     CHECK_LE(CounterSizeBits, MaxCounterBits);
     CounterSizeBitsLog = getLog2(CounterSizeBits);
     CounterMask = ~(static_cast<uptr>(0)) >> (MaxCounterBits - CounterSizeBits);
 
     const uptr PackingRatio = MaxCounterBits >> CounterSizeBitsLog;
     CHECK_GT(PackingRatio, 0);
     PackingRatioLog = getLog2(PackingRatio);
     BitOffsetMask = PackingRatio - 1;
 
-    BufferSize = (roundUpTo(N, static_cast<uptr>(1U) << PackingRatioLog) >>
-                  PackingRatioLog) *
-                 sizeof(*Buffer);
+    SizePerRegion =
+        roundUpTo(NumCounters, static_cast<uptr>(1U) << PackingRatioLog) >>
+        PackingRatioLog;
+    BufferSize = SizePerRegion * sizeof(*Buffer) * Regions;
     if (BufferSize <= (StaticBufferCount * sizeof(Buffer[0])) &&
         Mutex.tryLock()) {
       Buffer = &StaticBuffer[0];
       memset(Buffer, 0, BufferSize);
     } else {
       Buffer = reinterpret_cast<uptr *>(
           map(nullptr, BufferSize, "scudo:counters", MAP_ALLOWNOMEM));
     }
   }
   ~PackedCounterArray() {
     if (!isAllocated())
       return;
     if (Buffer == &StaticBuffer[0])
       Mutex.unlock();
     else
       unmap(reinterpret_cast<void *>(Buffer), BufferSize);
   }
 
   bool isAllocated() const { return !!Buffer; }
 
-  uptr getCount() const { return N; }
+  uptr getCount() const { return NumCounters; }
 
-  uptr get(uptr I) const {
-    DCHECK_LT(I, N);
+  uptr get(uptr Region, uptr I) const {
+    DCHECK_LT(Region, Regions);
+    DCHECK_LT(I, NumCounters);
     const uptr Index = I >> PackingRatioLog;
     const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
-    return (Buffer[Index] >> BitOffset) & CounterMask;
+    return (Buffer[Region * SizePerRegion + Index] >> BitOffset) & CounterMask;
   }
 
-  void inc(uptr I) const {
-    DCHECK_LT(get(I), CounterMask);
+  void inc(uptr Region, uptr I) const {
+    DCHECK_LT(get(Region, I), CounterMask);
     const uptr Index = I >> PackingRatioLog;
     const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
     DCHECK_LT(BitOffset, SCUDO_WORDSIZE);
-    Buffer[Index] += static_cast<uptr>(1U) << BitOffset;
+    Buffer[Region * SizePerRegion + Index] += static_cast<uptr>(1U)
+                                              << BitOffset;
   }
 
-  void incRange(uptr From, uptr To) const {
+  void incRange(uptr Region, uptr From, uptr To) const {
     DCHECK_LE(From, To);
-    const uptr Top = Min(To + 1, N);
+    const uptr Top = Min(To + 1, NumCounters);
     for (uptr I = From; I < Top; I++)
-      inc(I);
+      inc(Region, I);
   }
 
   uptr getBufferSize() const { return BufferSize; }
 
-  static const uptr StaticBufferCount = 1024U;
+  static const uptr StaticBufferCount = 2048U;
 
 private:
-  const uptr N;
+  const uptr Regions;
+  const uptr NumCounters;
   uptr CounterSizeBitsLog;
   uptr CounterMask;
   uptr PackingRatioLog;
   uptr BitOffsetMask;
 
+  uptr SizePerRegion;
   uptr BufferSize;
   uptr *Buffer;
 
   static HybridMutex Mutex;
   static uptr StaticBuffer[StaticBufferCount];
 };
 
 template <class ReleaseRecorderT> class FreePagesRangeTracker {
private:
   bool InRange = false;
   uptr CurrentPage = 0;
   uptr CurrentRangeStatePage = 0;
 };
 
 template <class TransferBatchT, class ReleaseRecorderT>
 NOINLINE void
 releaseFreeMemoryToOS(const IntrusiveList<TransferBatchT> &FreeList, uptr Base,
-                      uptr Size, uptr BlockSize, ReleaseRecorderT *Recorder) {
+                      uptr RegionSize, uptr NumberOfRegions, uptr BlockSize,
+                      ReleaseRecorderT *Recorder) {
   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) {
     } else {
       // One chunk covers multiple pages, Some chunks are crossing page
       // boundaries. Some pages contain one chunk, some contain two.
       FullPagesBlockCountMax = 2;
       SameBlockCountPerPage = false;
     }
   }
 
-  const uptr PagesCount = roundUpTo(Size, PageSize) / PageSize;
-  PackedCounterArray Counters(PagesCount, FullPagesBlockCountMax);
+  const uptr PagesCount = roundUpTo(RegionSize, PageSize) / PageSize;
+  PackedCounterArray Counters(NumberOfRegions, PagesCount,
+                              FullPagesBlockCountMax);
   if (!Counters.isAllocated())
     return;
 
   const uptr PageSizeLog = getLog2(PageSize);
-  const uptr RoundedSize = PagesCount << PageSizeLog;
+  const uptr RoundedRegionSize = PagesCount << PageSizeLog;
+  const uptr RoundedSize = NumberOfRegions * RoundedRegionSize;
 
   // Iterate over free chunks and count how many free chunks affect each
   // allocated page.
   if (BlockSize <= PageSize && PageSize % BlockSize == 0) {
     // Each chunk affects one page only.
     for (const auto &It : FreeList) {
       // If dealing with a TransferBatch, the first pointer of the batch will
       // point to the batch itself, we do not want to mark this for release as
       // the batch is in use, so skip the first entry.
       const bool IsTransferBatch =
           (It.getCount() != 0) &&
           (reinterpret_cast<uptr>(It.get(0)) == reinterpret_cast<uptr>(&It));
       for (u32 I = IsTransferBatch ? 1 : 0; I < It.getCount(); I++) {
         const uptr P = reinterpret_cast<uptr>(It.get(I)) - Base;
         // This takes care of P < Base and P >= Base + RoundedSize.
-        if (P < RoundedSize)
-          Counters.inc(P >> PageSizeLog);
+        if (P < RoundedSize) {
+          const uptr RegionIndex = NumberOfRegions == 1U ? 0 : P / RegionSize;
+          const uptr PInRegion = P - RegionIndex * RegionSize;
+          Counters.inc(RegionIndex, PInRegion >> PageSizeLog);
+        }
       }
     }
-    for (uptr P = Size; P < RoundedSize; P += BlockSize)
-      Counters.inc(P >> PageSizeLog);
   } else {
     // In all other cases chunks might affect more than one page.
+    DCHECK_GE(RegionSize, BlockSize);
+    const uptr LastBlockInRegion = ((RegionSize / BlockSize) - 1U) * BlockSize;
     for (const auto &It : FreeList) {
       // See TransferBatch comment above.
       const bool IsTransferBatch =
           (It.getCount() != 0) &&
           (reinterpret_cast<uptr>(It.get(0)) == reinterpret_cast<uptr>(&It));
       for (u32 I = IsTransferBatch ? 1 : 0; I < It.getCount(); I++) {
         const uptr P = reinterpret_cast<uptr>(It.get(I)) - Base;
         // This takes care of P < Base and P >= Base + RoundedSize.
-        if (P < RoundedSize)
-          Counters.incRange(P >> PageSizeLog,
-                            (P + BlockSize - 1) >> PageSizeLog);
+        if (P < RoundedSize) {
+          const uptr RegionIndex = NumberOfRegions == 1U ? 0 : P / RegionSize;
+          uptr PInRegion = P - RegionIndex * RegionSize;
+          Counters.incRange(RegionIndex, PInRegion >> PageSizeLog,
+                            (PInRegion + BlockSize - 1) >> PageSizeLog);
+          // The last block in a region might straddle a page, so if it's
+          // free, we mark the following "pretend" memory block(s) as free.
+          if (PInRegion == LastBlockInRegion) {
+            PInRegion += BlockSize;
+            while (PInRegion < RoundedRegionSize) {
+              Counters.incRange(RegionIndex, PInRegion >> PageSizeLog,
+                                (PInRegion + BlockSize - 1) >> PageSizeLog);
+              PInRegion += BlockSize;
+            }
+          }
+        }
       }
     }
-    for (uptr P = Size; P < RoundedSize; P += BlockSize)
-      Counters.incRange(P >> PageSizeLog, (P + BlockSize - 1) >> PageSizeLog);
   }
 
   // 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 < Counters.getCount(); I++)
-      RangeTracker.processNextPage(Counters.get(I) == FullPagesBlockCountMax);
+    for (uptr I = 0; I < NumberOfRegions; I++)
+      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++) {
       uptr PrevPageBoundary = 0;
       uptr CurrentBoundary = 0;
-    for (uptr I = 0; I < Counters.getCount(); I++) {
+      for (uptr J = 0; J < PagesCount; J++) {
         const uptr PageBoundary = PrevPageBoundary + PageSize;
         uptr BlocksPerPage = Pn;
         if (CurrentBoundary < PageBoundary) {
           if (CurrentBoundary > PrevPageBoundary)
             BlocksPerPage++;
           CurrentBoundary += Pnc;
           if (CurrentBoundary < PageBoundary) {
             BlocksPerPage++;
             CurrentBoundary += BlockSize;
           }
         }
         PrevPageBoundary = PageBoundary;
 
-      RangeTracker.processNextPage(Counters.get(I) == BlocksPerPage);
+        RangeTracker.processNextPage(Counters.get(I, J) == BlocksPerPage);
+      }
     }
   }
   RangeTracker.finish();
 }
 
 } // namespace scudo
 
 #endif // SCUDO_RELEASE_H_

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

 
 #include <algorithm>
 #include <random>
 #include <set>
 
 TEST(ScudoReleaseTest, PackedCounterArray) {
   for (scudo::uptr I = 0; I < SCUDO_WORDSIZE; I++) {
     // Various valid counter's max values packed into one word.
-    scudo::PackedCounterArray Counters2N(1, 1UL << I);
+    scudo::PackedCounterArray Counters2N(1U, 1U, 1UL << I);
     EXPECT_EQ(sizeof(scudo::uptr), Counters2N.getBufferSize());
     // Check the "all bit set" values too.
-    scudo::PackedCounterArray Counters2N1_1(1, ~0UL >> I);
+    scudo::PackedCounterArray Counters2N1_1(1U, 1U, ~0UL >> I);
     EXPECT_EQ(sizeof(scudo::uptr), Counters2N1_1.getBufferSize());
     // Verify the packing ratio, the counter is Expected to be packed into the
     // closest power of 2 bits.
-    scudo::PackedCounterArray Counters(SCUDO_WORDSIZE, 1UL << I);
+    scudo::PackedCounterArray Counters(1U, SCUDO_WORDSIZE, 1UL << I);
     EXPECT_EQ(sizeof(scudo::uptr) * scudo::roundUpToPowerOfTwo(I + 1),
               Counters.getBufferSize());
   }
 
   // Go through 1, 2, 4, 8, .. {32,64} bits per counter.
   for (scudo::uptr I = 0; (SCUDO_WORDSIZE >> I) != 0; I++) {
     // Make sure counters request one memory page for the buffer.
     const scudo::uptr NumCounters =
         (scudo::getPageSizeCached() / 8) * (SCUDO_WORDSIZE >> I);
-    scudo::PackedCounterArray Counters(NumCounters, 1UL << ((1UL << I) - 1));
-    Counters.inc(0);
+    scudo::PackedCounterArray Counters(1U, NumCounters,
+                                       1UL << ((1UL << I) - 1));
+    Counters.inc(0U, 0U);
     for (scudo::uptr C = 1; C < NumCounters - 1; C++) {
-      EXPECT_EQ(0UL, Counters.get(C));
-      Counters.inc(C);
-      EXPECT_EQ(1UL, Counters.get(C - 1));
+      EXPECT_EQ(0UL, Counters.get(0U, C));
+      Counters.inc(0U, C);
+      EXPECT_EQ(1UL, Counters.get(0U, C - 1));
     }
-    EXPECT_EQ(0UL, Counters.get(NumCounters - 1));
-    Counters.inc(NumCounters - 1);
+    EXPECT_EQ(0UL, Counters.get(0U, NumCounters - 1));
+    Counters.inc(0U, NumCounters - 1);
     if (I > 0) {
-      Counters.incRange(0, NumCounters - 1);
+      Counters.incRange(0u, 0U, NumCounters - 1);
       for (scudo::uptr C = 0; C < NumCounters; C++)
-        EXPECT_EQ(2UL, Counters.get(C));
+        EXPECT_EQ(2UL, Counters.get(0U, C));
     }
   }
 }
 
 class StringRangeRecorder {
 public:
   std::string ReportedPages;
 
for (auto const &Block : FreeArray) {
       }
       CurrentBatch->add(Block);
       if (CurrentBatch->getCount() == Batch::MaxCount)
         CurrentBatch = nullptr;
     }
 
     // Release the memory.
     ReleasedPagesRecorder Recorder;
-    releaseFreeMemoryToOS(FreeList, 0, MaxBlocks * BlockSize, BlockSize,
+    releaseFreeMemoryToOS(FreeList, 0, MaxBlocks * BlockSize, 1U, BlockSize,
                           &Recorder);
 
     // 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());