[scudo][standalone] Implement batch sorting based on reclaiming

[cryptoad]

Summary

This introduces sorting of the batches of free pointers based on how
"reclaimed" they are. After reclaiming, we count how many blocks are
within reclaimed pages (weighed as well by the number of pages they
cover), and sort the free list to put the most reclaimed batches in the
back, since we are less likely to want to work with them as they would
dirty the released memory.

This basically means that we work with a reduced subset of the possible
pointers within a region, which in return might increase the
predictability of the allocation patterns. Currently it's only enabled
for Android as the RSS/PSS constraints are higher.

[cryptoad]

Fixing a conversion error, updating a test.

[cryptoad]

Rebased.

[cryptoad]

Only sort if a release occured.

[cryptoad]

Only sort batches when a release occured on 32-bit.

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

template <class T> struct IntrusiveList {
 
   Iterator begin() { return Iterator(First); }
   Iterator end() { return Iterator(nullptr); }
 
   ConstIterator begin() const { return ConstIterator(First); }
   ConstIterator end() const { return ConstIterator(nullptr); }
 
   void checkConsistency() const;
+  void sort(bool (*compare)(T *A, T *B));
 
 protected:
   uptr Size;
   T *First;
   T *Last;
 };
 
 template <class T> void IntrusiveList<T>::checkConsistency() const {
   if (Size == 0) {
     CHECK_EQ(First, nullptr);
     CHECK_EQ(Last, nullptr);
   } else {
     uptr Count = 0;
     for (T *I = First;; I = I->Next) {
       Count++;
       if (I == Last)
         break;
     }
     CHECK_EQ(this->size(), Count);
     CHECK_EQ(Last->Next, nullptr);
   }
 }
 
+// Standard bubble sort, pointers are swapped instead of the data.
+template <class T> void IntrusiveList<T>::sort(bool (*compare)(T *A, T *B)) {
+  bool Swapped;
+  T *I, *End = nullptr;
+  do {
+    Swapped = false;
+    I = First;
+    T *Before = nullptr;
+    while (I->Next != End) {
+      T *After = I->Next;
+      if (compare(I, After)) {
+        if (First == I) {
+          DCHECK_EQ(Before, nullptr);
+          First = After;
+        }
+        if (Last == After) {
+          DCHECK_EQ(After->Next, nullptr);
+          Last = I;
+        }
+        if (Before) {
+          DCHECK_EQ(Before->Next, I);
+          Before->Next = After;
+        }
+        I->Next = After->Next;
+        After->Next = I;
+        Before = After;
+        Swapped = true;
+      } else {
+        Before = I;
+        I = After;
+      }
+    }
+    End = I;
+  } while (Swapped);
+}
+
 template <class T> struct SinglyLinkedList : public IntrusiveList<T> {
   using IntrusiveList<T>::First;
   using IntrusiveList<T>::Last;
   using IntrusiveList<T>::Size;
   using IntrusiveList<T>::empty;
 
   void push_back(T *X) {
     X->Next = nullptr;

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

 template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache {
   typedef typename SizeClassAllocator::SizeClassMap SizeClassMap;
 
   struct TransferBatch {
     static const u32 MaxNumCached = SizeClassMap::MaxNumCachedHint;
     void setFromArray(void **Array, u32 N) {
       DCHECK_LE(N, MaxNumCached);
       Count = N;
+      ReleaseHint = 0;
       memcpy(Batch, Array, sizeof(void *) * Count);
     }
-    void clear() { Count = 0; }
+    void clear() { ReleaseHint = Count = 0; }
     void add(void *P) {
       DCHECK_LT(Count, MaxNumCached);
       Batch[Count++] = P;
     }
     void copyToArray(void **Array) const {
       memcpy(Array, Batch, sizeof(void *) * Count);
     }
     u32 getCount() const { return Count; }
     void *get(u32 I) const {
       DCHECK_LE(I, Count);
       return Batch[I];
     }
     static u32 getMaxCached(uptr Size) {
       return Min(MaxNumCached, SizeClassMap::getMaxCachedHint(Size));
     }
+    void incReleaseHint() {
+      ReleaseHint++;
+      DCHECK_LE(ReleaseHint, MaxNumCached);
+    }
+    u32 getReleaseHint() const { return ReleaseHint; }
+    void clearReleaseHint() { ReleaseHint = 0; }
+
     TransferBatch *Next;
 
   private:
     u32 Count;
+    u32 ReleaseHint;
     void *Batch[MaxNumCached];
   };
 
   void initLinkerInitialized(GlobalStats *S, SizeClassAllocator *A) {
     Stats.initLinkerInitialized();
     if (LIKELY(S))
       S->link(&Stats);
     Allocator = A;

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

private:
   s32 getReleaseToOsIntervalMs() {
     return atomic_load(&ReleaseToOsIntervalMs, memory_order_relaxed);
   }
 
   NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
                                  bool Force = false) {
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr PageSize = getPageSizeCached();
+    const bool SortBatches = static_cast<bool>(SCUDO_ANDROID);
 
     CHECK_GE(Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks);
     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 0; // Nothing new to release.
     }
 
     if (!Force) {
       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.
       }
     }
 
+    if (SortBatches) {
+      for (auto &It : Sci->FreeList)
+        It.clearReleaseHint();
+    }
+
     // 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] - 1U == ClassId) {
-        const uptr Region = I * RegionSize;
-        ReleaseRecorder Recorder(Region);
-        releaseFreeMemoryToOS(Sci->FreeList, Region, 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;
-        }
-      }
+      if (PossibleRegions[I] - 1U != ClassId)
+        continue;
+                            BlockSize, &Recorder, SortBatches);
+    if (SortBatches && TotalReleasedBytes > 0) {
+      Sci->FreeList.sort([](TransferBatch *A, TransferBatch *B) -> bool {
+        return A->getReleaseHint() > B->getReleaseHint();
+      });
     }
+
     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

private:
   s32 getReleaseToOsIntervalMs() {
     return atomic_load(&ReleaseToOsIntervalMs, memory_order_relaxed);
   }
 
   NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
                                  bool Force = false) {
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr PageSize = getPageSizeCached();
+    // TODO(kostyak): currently only enabled on Android, make it configurable.
+    // By sorting the batches based on how "reclaimed" they are, we basically
+    // reduce the range of memory we are working with, which will have
+    // consequences with regard to predictability of the allocation patterns.
+    const bool SortBatches = static_cast<bool>(SCUDO_ANDROID);
 
     CHECK_GE(Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks);
     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 -
if (!Force) {
         return 0;
       if (Region->ReleaseInfo.LastReleaseAtNs +
               static_cast<u64>(IntervalMs) * 1000000 >
           getMonotonicTime()) {
         return 0; // Memory was returned recently.
       }
     }
 
+    if (SortBatches) {
+      for (auto &It : Region->FreeList)
+        It.clearReleaseHint();
+    }
+
     ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data);
     releaseFreeMemoryToOS(Region->FreeList, Region->RegionBeg,
                           roundUpTo(Region->AllocatedUser, PageSize) / PageSize,
-                          BlockSize, &Recorder);
+                          BlockSize, &Recorder, SortBatches);
 
     if (Recorder.getReleasedRangesCount() > 0) {
       Region->ReleaseInfo.PushedBlocksAtLastRelease =
           Region->Stats.PushedBlocks;
       Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
       Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
+      if (SortBatches) {
+        Region->FreeList.sort([](TransferBatch *A, TransferBatch *B) -> bool {
+          return A->getReleaseHint() > B->getReleaseHint();
+        });
+      }
     }
     Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
     return Recorder.getReleasedBytes();
   }
 };
 
 } // namespace scudo
 
 #endif // SCUDO_PRIMARY64_H_

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

PackedCounterArray(uptr NumCounters, uptr MaxValue) : N(NumCounters) {
     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);
+    const uptr PackedCountersSize =
+        (roundUpTo(N, static_cast<uptr>(1U) << PackingRatioLog) >>
+    const uptr MetaDataSize = roundUpTo(N, 8U) / 8U;
+    BufferSize = PackedCountersSize + MetaDataSize;
     if (BufferSize <= StaticBufferSize && Mutex.tryLock()) {
       Buffer = &StaticBuffer[0];
       memset(Buffer, 0, BufferSize);
     } else {
       Buffer = reinterpret_cast<uptr *>(
           map(nullptr, BufferSize, "scudo:counters", MAP_ALLOWNOMEM));
     }
+    MetaData = reinterpret_cast<u8 *>(reinterpret_cast<uptr>(Buffer) +
+                                      PackedCountersSize);
   }
   ~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; }
 
+  void setMetaData(uptr I) {
+    DCHECK_LT(I, N);
+    DCHECK_EQ(MetaData[I / 8] & (1U << (I & 7)), 0U);
+    MetaData[I / 8] |= static_cast<u8>(1U << (I & 7));
+  }
+
+  u8 getMetaData(uptr I) {
+    DCHECK_LT(I, N);
+    return MetaData[I / 8] & (1U << (I & 7)) ? 1U : 0U;
+  }
+
   uptr get(uptr I) const {
     DCHECK_LT(I, N);
     const uptr Index = I >> PackingRatioLog;
     const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
     return (Buffer[Index] >> BitOffset) & CounterMask;
   }
 
   void inc(uptr I) const {
     DCHECK_LT(get(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;
   }
 
   void incRange(uptr From, uptr To) const {
     DCHECK_LE(From, To);
     for (uptr I = From; I <= To; I++)
       inc(I);
   }
 
-  uptr getBufferSize() const { return BufferSize; }
+  uptr getPackedCountersSize() const {
+    return BufferSize - roundUpTo(N, 8U) / 8U;
+  }
 
 private:
   const uptr N;
   uptr CounterSizeBitsLog;
   uptr CounterMask;
   uptr PackingRatioLog;
   uptr BitOffsetMask;
 
   uptr BufferSize;
   uptr *Buffer;
+  // MetaData holds an extra bit per counter;
+  u8 *MetaData;
 
   static HybridMutex Mutex;
   static const uptr StaticBufferSize = 1024U;
   static uptr StaticBuffer[StaticBufferSize];
 };
 
 template <class ReleaseRecorderT> class FreePagesRangeTracker {
 public:
private:
   uptr CurrentPage = 0;
   uptr CurrentRangeStatePage = 0;
 };
 
 template <class TransferBatchT, class ReleaseRecorderT>
 NOINLINE void
 releaseFreeMemoryToOS(const IntrusiveList<TransferBatchT> &FreeList, uptr Base,
                       uptr AllocatedPagesCount, uptr BlockSize,
-                      ReleaseRecorderT *Recorder) {
+                      ReleaseRecorderT *Recorder,
+                      bool UpdateReleaseHint = false) {
   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 < Counters.getCount(); I++)
-      RangeTracker.processNextPage(Counters.get(I) == FullPagesBlockCountMax);
+    for (uptr I = 0; I < Counters.getCount(); I++) {
+      const bool Freed = Counters.get(I) == FullPagesBlockCountMax;
+      if (UpdateReleaseHint && Freed)
+        Counters.setMetaData(I);
+      RangeTracker.processNextPage(Freed);
+    }
   } 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
for (uptr I = 0; I < Counters.getCount(); I++) {
         CurrentBoundary += Pnc;
         if (CurrentBoundary < PageBoundary) {
           BlocksPerPage++;
           CurrentBoundary += BlockSize;
         }
       }
       PrevPageBoundary = PageBoundary;
 
-      RangeTracker.processNextPage(Counters.get(I) == BlocksPerPage);
+      const bool Freed = Counters.get(I) == BlocksPerPage;
+      if (UpdateReleaseHint && Freed)
+        Counters.setMetaData(I);
+      RangeTracker.processNextPage(Freed);
     }
   }
   RangeTracker.finish();
+
+  if (!UpdateReleaseHint || Recorder->getReleasedRangesCount() == 0)
+    return;
+  for (auto &It : const_cast<IntrusiveList<TransferBatchT> &>(FreeList)) {
+    for (u32 I = 0; I < It.getCount(); I++) {
+      const uptr P = reinterpret_cast<uptr>(It.get(I));
+      if (P < Base || P >= End)
+        continue;
+      for (uptr J = P; J <= P + BlockSize - 1; J += PageSize)
+        if (Counters.getMetaData((J - Base) >> PageSizeLog))
+          It.incReleaseHint();
+    }
+  }
 }
 
 } // 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);
-    EXPECT_EQ(sizeof(scudo::uptr), Counters2N.getBufferSize());
+    EXPECT_EQ(sizeof(scudo::uptr), Counters2N.getPackedCountersSize());
     // Check the "all bit set" values too.
     scudo::PackedCounterArray Counters2N1_1(1, ~0UL >> I);
-    EXPECT_EQ(sizeof(scudo::uptr), Counters2N1_1.getBufferSize());
+    EXPECT_EQ(sizeof(scudo::uptr), Counters2N1_1.getPackedCountersSize());
     // 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);
     EXPECT_EQ(sizeof(scudo::uptr) * scudo::roundUpToPowerOfTwo(I + 1),
-              Counters.getBufferSize());
+              Counters.getPackedCountersSize());
   }
 
   // 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));

 public:
   std::set<scudo::uptr> ReportedPages;
 
   void releasePageRangeToOS(scudo::uptr From, scudo::uptr To) {
     const scudo::uptr PageSize = scudo::getPageSizeCached();
     for (scudo::uptr I = From; I < To; I += PageSize)
       ReportedPages.insert(I);
   }
+
+  scudo::uptr getReleasedRangesCount() const { return ReportedPages.size(); }
 };
 
 // Simplified version of a TransferBatch.
 template <class SizeClassMap> struct FreeBatch {
   static const scudo::u32 MaxCount = SizeClassMap::MaxNumCachedHint;
   void clear() { Count = 0; }
   void add(scudo::uptr P) {
     DCHECK_LT(Count, MaxCount);
     Batch[Count++] = P;
   }
   scudo::u32 getCount() const { return Count; }
   scudo::uptr get(scudo::u32 I) const {
     DCHECK_LE(I, Count);
     return Batch[I];
   }
+  void incReleaseHint() const {}
+  scudo::u32 getReleaseHint() const { return 0; }
+  void clearReleaseHint() const {}
+
   FreeBatch *Next;
 
 private:
   scudo::u32 Count;
   scudo::uptr Batch[MaxCount];
 };
 
 template <class SizeClassMap> void testReleaseFreeMemoryToOS() {

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

 TEST(ScudoSizeClassMapTest, SvelteSizeClassMap) {
   testSizeClassMap<scudo::SvelteSizeClassMap>();
 }
 
 TEST(ScudoSizeClassMapTest, AndroidSizeClassMap) {
   testSizeClassMap<scudo::AndroidSizeClassMap>();
 }
 
-
 struct OneClassSizeClassConfig {
   static const scudo::uptr NumBits = 1;
   static const scudo::uptr MinSizeLog = 5;
   static const scudo::uptr MidSizeLog = 5;
   static const scudo::uptr MaxSizeLog = 5;
   static const scudo::u32 MaxNumCachedHint = 0;
   static const scudo::uptr MaxBytesCachedLog = 0;
 };