[scudo][standalone] Secondary & general other improvements

[cryptoad]

Summary

This CL changes multiple things to improve performance (notably on
Android).We introduce a class that implements a cache for the Secondary.

The changes:

• change the Secondary "freelist" to an array. By keeping free secondary blocks linked together through their headers, we were keeping a page per block, which isn't great. Also we now touch less pages when walking the new "freelist".
• fix an issue with the freelist getting full: if the pattern is an ever increasing size malloc then free, the freelist would fill up and entries would not be used. So now we empty the list if we get to many "full" events;
• use the global release to os interval option for the secondary: it was too costly to release all the time, particularly for pattern that are malloc(X)/free(X)/malloc(X). Now the release will only occur after the selected interval, when going through the deallocate path;
• allow release of the BatchClassId class: it is releasable, we just have to make sure we don't mark the batches containing batches pointers as free.
• change the default release interval to 1s for Android to match the current Bionic allocator configuration. A patch is coming up to allow changing it through mallopt.
• lower the smallest class that can be released to PageSize/64.

[merge_guards_bot]

Unit tests: pass. 62246 tests passed, 0 failed and 816 were skipped.

clang-tidy: fail. clang-tidy found 7 errors and 0 warnings. 0 of them are added as review comments below (why?).

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[eugenis]

LGTM

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

125

Would it make sense to move the IsFullEvents check here?
I.e. instead of clearing the cache after 4 failures to push a new entry, do it if the cache is X% full but we fail to find a suitable entry.

Probably would not make a difference in practice...

[hctim]

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

48

Given that this might get very complicated if you wanted to introduce different defaults for different platforms - it may be worth adding a TODO to initialise Scudo as part of libc_init_malloc rather than rely on lazy-initialisation.

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

88

Might be worth considering

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

59

UNUSED uptr Size

146

Can you reuse code via. empty() { releaseOlderThan(UINT64_MAX) }?

193

Missing EntriesCount -= N?

294–296

Nit: Just canCache(RoundedSize)

387

Nit: just canCache(CommitSize)

[pcc]

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

48

I would prefer if we moved towards making these things static (e.g. part of AndroidConfig et al) rather than configurable via environment variables.

[cryptoad]

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

48

Ack. Technically a platform could also use the SCUDO_DEFAULT_OPTIONS define at compile time.

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

88

In the works with https://reviews.llvm.org/D72882. I'll come back to that after this lands as it's higher priority.

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

146

I looked into this, as the constructs are similar. One of the issues is that one works with Map* members, the other with Block* members.
In the end I decided against as it became ugly, but I can revisit this at a later point hopefully.

193

The entries are still usable, we released the memory but they can be reused at some point (unlike unmapping). It will incur faulting, which is slower, but has a positive impact on the RSS.

[hctim]

Acks, LGTM.

[cryptoad]

Marking a parameter unused.

[merge_guards_bot]

Unit tests: pass. 62248 tests passed, 0 failed and 816 were skipped.

clang-tidy: fail. clang-tidy found 7 errors and 0 warnings. 0 of them are added as review comments below (why?).

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[cryptoad]

Passing ReleaseToOsInterval from init to initLinkerInitialized in
the Secondary.

[cryptoad]

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

48

I think making it part of the configuration is a good idea once we get a way to change it at runtime which is coming up with the mallopt change.

[merge_guards_bot]

Unit tests: pass. 62248 tests passed, 0 failed and 816 were skipped.

clang-tidy: fail. clang-tidy found 7 errors and 0 warnings. 0 of them are added as review comments below (why?).

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

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

struct DefaultConfig {
   using SizeClassMap = DefaultSizeClassMap;
 #if SCUDO_CAN_USE_PRIMARY64
   // 1GB Regions
   typedef SizeClassAllocator64<SizeClassMap, 30U> Primary;
 #else
   // 512KB regions
   typedef SizeClassAllocator32<SizeClassMap, 19U> Primary;
 #endif
-  typedef MapAllocator<> Secondary;
+  typedef MapAllocator<MapAllocatorCache<>> Secondary;
   template <class A> using TSDRegistryT = TSDRegistryExT<A>; // Exclusive
 };
 
 struct AndroidConfig {
   using SizeClassMap = AndroidSizeClassMap;
 #if SCUDO_CAN_USE_PRIMARY64
   // 128MB regions
   typedef SizeClassAllocator64<SizeClassMap, 27U,
                                /*MaySupportMemoryTagging=*/true>
       Primary;
 #else
   // 512KB regions
   typedef SizeClassAllocator32<SizeClassMap, 19U> Primary;
 #endif
-  typedef MapAllocator<> Secondary;
+  typedef MapAllocator<MapAllocatorCache<>> Secondary;
   template <class A>
   using TSDRegistryT = TSDRegistrySharedT<A, 2U>; // Shared, max 2 TSDs.
 };
 
 struct AndroidSvelteConfig {
   using SizeClassMap = SvelteSizeClassMap;
 #if SCUDO_CAN_USE_PRIMARY64
   // 128MB regions
   typedef SizeClassAllocator64<SizeClassMap, 27U> Primary;
 #else
   // 64KB regions
   typedef SizeClassAllocator32<SizeClassMap, 16U> Primary;
 #endif
-  typedef MapAllocator<0U> Secondary;
+  typedef MapAllocator<MapAllocatorCache<4U, 1UL << 18>> Secondary;
   template <class A>
   using TSDRegistryT = TSDRegistrySharedT<A, 1U>; // Shared, only 1 TSD.
 };
 
 #if SCUDO_CAN_USE_PRIMARY64
 struct FuchsiaConfig {
   // 1GB Regions
   typedef SizeClassAllocator64<DefaultSizeClassMap, 30U> Primary;
-  typedef MapAllocator<0U> Secondary;
+  typedef MapAllocator<MapAllocatorNoCache> Secondary;
   template <class A>
   using TSDRegistryT = TSDRegistrySharedT<A, 8U>; // Shared, max 8 TSDs.
 };
 #endif
 
 #if SCUDO_ANDROID
 typedef AndroidConfig Config;
 #elif SCUDO_FUCHSIA
 typedef FuchsiaConfig Config;
 #else
 typedef DefaultConfig Config;
 #endif
 
 } // namespace scudo
 
 #endif // SCUDO_ALLOCATOR_CONFIG_H_

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

void initLinkerInitialized() {
     Options.MayReturnNull = getFlags()->may_return_null;
     Options.ZeroContents = getFlags()->zero_contents;
     Options.DeallocTypeMismatch = getFlags()->dealloc_type_mismatch;
     Options.DeleteSizeMismatch = getFlags()->delete_size_mismatch;
     Options.QuarantineMaxChunkSize =
         static_cast<u32>(getFlags()->quarantine_max_chunk_size);
 
     Stats.initLinkerInitialized();
-    Primary.initLinkerInitialized(getFlags()->release_to_os_interval_ms);
-    Secondary.initLinkerInitialized(&Stats);
+    const s32 ReleaseToOsIntervalMs = getFlags()->release_to_os_interval_ms;
+    Primary.initLinkerInitialized(ReleaseToOsIntervalMs);
+    Secondary.initLinkerInitialized(&Stats, ReleaseToOsIntervalMs);
 
     Quarantine.init(
         static_cast<uptr>(getFlags()->quarantine_size_kb << 10),
         static_cast<uptr>(getFlags()->thread_local_quarantine_size_kb << 10));
   }
 
   // Initialize the embedded GWP-ASan instance. Requires the main allocator to
   // be functional, best called from PostInitCallback.

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

SCUDO_FLAG(int, rss_limit_mb, -1,
            "attempted past that limit (depending on may_return_null). Negative "
            "values disable the feature.")
 
 SCUDO_FLAG(bool, may_return_null, true,
            "Indicate whether the allocator should terminate instead of "
            "returning NULL in otherwise non-fatal error scenarios, eg: OOM, "
            "invalid allocation alignments, etc.")
 
-SCUDO_FLAG(int, release_to_os_interval_ms, 5000,
+SCUDO_FLAG(int, release_to_os_interval_ms, SCUDO_ANDROID ? 1000 : 5000,
            "Interval (in milliseconds) at which to attempt release of unused "
            "memory to the OS. Negative values disable the feature.")

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

if (UNLIKELY(!getRandom(reinterpret_cast<void *>(&Seed), sizeof(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) &&
-                        (I != SizeClassMap::BatchClassId) &&
-                        (getSizeByClassId(I) >= (PageSize / 32));
+                        (getSizeByClassId(I) >= (PageSize / 64));
     }
     ReleaseToOsIntervalMs = ReleaseToOsInterval;
   }
   void init(s32 ReleaseToOsInterval) {
     memset(this, 0, sizeof(*this));
     initLinkerInitialized(ReleaseToOsInterval);
   }
 
if ((Sci->Stats.PushedBlocks - Sci->ReleaseInfo.PushedBlocksAtLastRelease) *
       return 0; // Nothing new to release.
     }
 
     if (!Force) {
       const s32 IntervalMs = ReleaseToOsIntervalMs;
       if (IntervalMs < 0)
         return 0;
       if (Sci->ReleaseInfo.LastReleaseAtNs +
-              static_cast<uptr>(IntervalMs) * 1000000ULL >
+              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.

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

for (uptr I = 0; I < NumClasses; I++) {
       Region->RegionBeg =
           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) &&
-                           (I != SizeClassMap::BatchClassId) &&
-                           (getSizeByClassId(I) >= (PageSize / 32));
+                           (getSizeByClassId(I) >= (PageSize / 64));
       Region->RandState = getRandomU32(&Seed);
     }
     ReleaseToOsIntervalMs = ReleaseToOsInterval;
 
     if (SupportsMemoryTagging)
       UseMemoryTagging = systemSupportsMemoryTagging();
   }
   void init(s32 ReleaseToOsInterval) {
if ((Region->Stats.PushedBlocks -
       return 0; // Nothing new to release.
     }
 
     if (!Force) {
       const s32 IntervalMs = ReleaseToOsIntervalMs;
       if (IntervalMs < 0)
         return 0;
       if (Region->ReleaseInfo.LastReleaseAtNs +
-              static_cast<uptr>(IntervalMs) * 1000000ULL >
+              static_cast<u64>(IntervalMs) * 1000000 >
           getMonotonicTime()) {
         return 0; // Memory was returned recently.
       }
     }
 
     ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data);
     releaseFreeMemoryToOS(Region->FreeList, Region->RegionBeg,
                           roundUpTo(Region->AllocatedUser, PageSize) / PageSize,

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

releaseFreeMemoryToOS(const IntrusiveList<TransferBatchT> &FreeList, uptr Base,
   const uptr PageSizeLog = getLog2(PageSize);
   const uptr End = Base + AllocatedPagesCount * PageSize;
 
   // 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) {
-      for (u32 I = 0; I < It.getCount(); I++) {
+      // 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));
         if (P >= Base && P < End)
           Counters.inc((P - Base) >> PageSizeLog);
       }
     }
   } else {
     // In all other cases chunks might affect more than one page.
     for (const auto &It : FreeList) {
-      for (u32 I = 0; I < It.getCount(); I++) {
+      // 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));
         if (P >= Base && P < End)
           Counters.incRange((P - Base) >> PageSizeLog,
                             (P - Base + BlockSize - 1) >> PageSizeLog);
       }
     }
   }
 

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

 }
 
 static Header *getHeader(const void *Ptr) {
   return getHeader(reinterpret_cast<uptr>(Ptr));
 }
 
 } // namespace LargeBlock
 
-template <uptr MaxFreeListSize = 32U> class MapAllocator {
+class MapAllocatorNoCache {
 public:
-  // Ensure the freelist is disabled on Fuchsia, since it doesn't support
-  // releasing Secondary blocks yet.
-  static_assert(!SCUDO_FUCHSIA || MaxFreeListSize == 0U, "");
+  void initLinkerInitialized(UNUSED s32 ReleaseToOsInterval) {}
+  void init(UNUSED s32 ReleaseToOsInterval) {}
+  bool retrieve(UNUSED uptr Size, UNUSED LargeBlock::Header **H) {
+    return false;
+  }
+  bool store(UNUSED LargeBlock::Header *H) { return false; }
+  static bool canCache(UNUSED uptr Size) { return false; }
+  void disable() {}
+  void enable() {}
+};
+
+template <uptr MaxEntriesCount = 32U, uptr MaxEntrySize = 1UL << 19>
+class MapAllocatorCache {
+public:
+  // Fuchsia doesn't allow releasing Secondary blocks yet. Note that 0 length
+  // arrays are an extension for some compilers.
+  // FIXME(kostyak): support (partially) the cache on Fuchsia.
+  static_assert(!SCUDO_FUCHSIA || MaxEntriesCount == 0U, "");
+
+  void initLinkerInitialized(s32 ReleaseToOsInterval) {
+    ReleaseToOsIntervalMs = ReleaseToOsInterval;
+  }
+  void init(s32 ReleaseToOsInterval) {
+    memset(this, 0, sizeof(*this));
+    initLinkerInitialized(ReleaseToOsInterval);
+  }
+
+  bool store(LargeBlock::Header *H) {
+    bool EntryCached = false;
+    bool EmptyCache = false;
+    const u64 Time = getMonotonicTime();
+    {
+      ScopedLock L(Mutex);
+      if (EntriesCount == MaxEntriesCount) {
+        if (IsFullEvents++ == 4U)
+          EmptyCache = true;
+      } else {
+        for (uptr I = 0; I < MaxEntriesCount; I++) {
+          if (Entries[I].Block)
+            continue;
+          if (I != 0)
+            Entries[I] = Entries[0];
+          Entries[0].Block = reinterpret_cast<uptr>(H);
+          Entries[0].BlockEnd = H->BlockEnd;
+          Entries[0].MapBase = H->MapBase;
+          Entries[0].MapSize = H->MapSize;
+          Entries[0].Time = Time;
+          EntriesCount++;
+          EntryCached = true;
+          break;
+        }
+      }
+    }
+    if (EmptyCache)
+      empty();
+    else if (ReleaseToOsIntervalMs >= 0)
+      releaseOlderThan(Time -
+                       static_cast<u64>(ReleaseToOsIntervalMs) * 1000000);
+    return EntryCached;
+  }
+
+  bool retrieve(uptr Size, LargeBlock::Header **H) {
+    ScopedLock L(Mutex);
+    if (EntriesCount == 0)
+      return false;
+    for (uptr I = 0; I < MaxEntriesCount; I++) {
+      if (!Entries[I].Block)
+        continue;
+      const uptr BlockSize = Entries[I].BlockEnd - Entries[I].Block;
+      if (Size > BlockSize)
+        continue;
+      if (Size < BlockSize - getPageSizeCached() * 4U)
+        continue;
+      *H = reinterpret_cast<LargeBlock::Header *>(Entries[I].Block);
+      Entries[I].Block = 0;
+      (*H)->BlockEnd = Entries[I].BlockEnd;
+      (*H)->MapBase = Entries[I].MapBase;
+      (*H)->MapSize = Entries[I].MapSize;
+      EntriesCount--;
+      return true;
+    }
+    return false;
+  }
+
+  static bool canCache(uptr Size) {
+    return MaxEntriesCount != 0U && Size <= MaxEntrySize;
+  }
+
+  void disable() { Mutex.lock(); }
+
+  void enable() { Mutex.unlock(); }
+
+private:
+  void empty() {
+    struct {
+      void *MapBase;
+      uptr MapSize;
+      MapPlatformData Data;
+    } MapInfo[MaxEntriesCount];
+    uptr N = 0;
+    {
+      ScopedLock L(Mutex);
+      for (uptr I = 0; I < MaxEntriesCount; I++) {
+        if (!Entries[I].Block)
+          continue;
+        MapInfo[N].MapBase = reinterpret_cast<void *>(Entries[I].MapBase);
+        MapInfo[N].MapSize = Entries[I].MapSize;
+        MapInfo[N].Data = Entries[I].Data;
+        Entries[I].Block = 0;
+        N++;
+      }
+      EntriesCount = 0;
+      IsFullEvents = 0;
+    }
+    for (uptr I = 0; I < N; I++)
+      unmap(MapInfo[I].MapBase, MapInfo[I].MapSize, UNMAP_ALL,
+            &MapInfo[I].Data);
+  }
+
+  void releaseOlderThan(u64 Time) {
+    struct {
+      uptr Block;
+      uptr BlockSize;
+      MapPlatformData Data;
+    } BlockInfo[MaxEntriesCount];
+    uptr N = 0;
+    {
+      ScopedLock L(Mutex);
+      if (!EntriesCount)
+        return;
+      for (uptr I = 0; I < MaxEntriesCount; I++) {
+        if (!Entries[I].Block || !Entries[I].Time)
+          continue;
+        if (Entries[I].Time > Time)
+          continue;
+        BlockInfo[N].Block = Entries[I].Block;
+        BlockInfo[N].BlockSize = Entries[I].BlockEnd - Entries[I].Block;
+        BlockInfo[N].Data = Entries[I].Data;
+        Entries[I].Time = 0;
+        N++;
+      }
+    }
+    for (uptr I = 0; I < N; I++)
+      releasePagesToOS(BlockInfo[I].Block, 0, BlockInfo[I].BlockSize,
+                       &BlockInfo[I].Data);
+  }
 
-  void initLinkerInitialized(GlobalStats *S) {
+  struct CachedBlock {
+    uptr Block;
+    uptr BlockEnd;
+    uptr MapBase;
+    uptr MapSize;
+    MapPlatformData Data;
+    u64 Time;
+  };
+
+  HybridMutex Mutex;
+  CachedBlock Entries[MaxEntriesCount];
+  u32 EntriesCount;
+  uptr LargestSize;
+  u32 IsFullEvents;
+  s32 ReleaseToOsIntervalMs;
+};
+
+template <class CacheT> class MapAllocator {
+public:
+  void initLinkerInitialized(GlobalStats *S, s32 ReleaseToOsInterval = -1) {
+    Cache.initLinkerInitialized(ReleaseToOsInterval);
     Stats.initLinkerInitialized();
     if (LIKELY(S))
       S->link(&Stats);
   }
-  void init(GlobalStats *S) {
+  void init(GlobalStats *S, s32 ReleaseToOsInterval = -1) {
     memset(this, 0, sizeof(*this));
-    initLinkerInitialized(S);
+    initLinkerInitialized(S, ReleaseToOsInterval);
   }
 
   void *allocate(uptr Size, uptr AlignmentHint = 0, uptr *BlockEnd = nullptr,
                  bool ZeroContents = false);
 
   void deallocate(void *Ptr);
 
   static uptr getBlockEnd(void *Ptr) {
     return LargeBlock::getHeader(Ptr)->BlockEnd;
   }
 
   static uptr getBlockSize(void *Ptr) {
     return getBlockEnd(Ptr) - reinterpret_cast<uptr>(Ptr);
   }
 
   void getStats(ScopedString *Str) const;
 
-  void disable() { Mutex.lock(); }
+  void disable() {
+    Mutex.lock();
+    Cache.disable();
+  }
 
-  void enable() { Mutex.unlock(); }
+  void enable() {
+    Cache.enable();
+    Mutex.unlock();
+  }
 
   template <typename F> void iterateOverBlocks(F Callback) const {
     for (const auto &H : InUseBlocks)
       Callback(reinterpret_cast<uptr>(&H) + LargeBlock::getHeaderSize());
   }
 
-  static uptr getMaxFreeListSize(void) { return MaxFreeListSize; }
+  static uptr canCache(uptr Size) { return CacheT::canCache(Size); }
 
 private:
+  CacheT Cache;
+
   HybridMutex Mutex;
   DoublyLinkedList<LargeBlock::Header> InUseBlocks;
-  // The free list is sorted based on the committed size of blocks.
-  DoublyLinkedList<LargeBlock::Header> FreeBlocks;
   uptr AllocatedBytes;
   uptr FreedBytes;
   uptr LargestSize;
   u32 NumberOfAllocs;
   u32 NumberOfFrees;
   LocalStats Stats;
 };
 
 // As with the Primary, the size passed to this function includes any desired
 // alignment, so that the frontend can align the user allocation. The hint
 // parameter allows us to unmap spurious memory when dealing with larger
 // (greater than a page) alignments on 32-bit platforms.
 // Due to the sparsity of address space available on those platforms, requesting
 // an allocation from the Secondary with a large alignment would end up wasting
 // VA space (even though we are not committing the whole thing), hence the need
 // to trim off some of the reserved space.
 // For allocations requested with an alignment greater than or equal to a page,
 // the committed memory will amount to something close to Size - AlignmentHint
 // (pending rounding and headers).
-template <uptr MaxFreeListSize>
-void *MapAllocator<MaxFreeListSize>::allocate(uptr Size, uptr AlignmentHint,
-                                              uptr *BlockEnd,
-                                              bool ZeroContents) {
+template <class CacheT>
+void *MapAllocator<CacheT>::allocate(uptr Size, uptr AlignmentHint,
+                                     uptr *BlockEnd, bool ZeroContents) {
   DCHECK_GE(Size, AlignmentHint);
   const uptr PageSize = getPageSizeCached();
   const uptr RoundedSize =
       roundUpTo(Size + LargeBlock::getHeaderSize(), PageSize);
 
-  if (MaxFreeListSize && AlignmentHint < PageSize) {
-    ScopedLock L(Mutex);
-    for (auto &H : FreeBlocks) {
-      const uptr FreeBlockSize = H.BlockEnd - reinterpret_cast<uptr>(&H);
-      if (FreeBlockSize < RoundedSize)
-        continue;
-      // Candidate free block should only be at most 4 pages larger.
-      if (FreeBlockSize > RoundedSize + 4 * PageSize)
-        break;
-      FreeBlocks.remove(&H);
-      InUseBlocks.push_back(&H);
-      AllocatedBytes += FreeBlockSize;
-      NumberOfAllocs++;
-      Stats.add(StatAllocated, FreeBlockSize);
+  if (AlignmentHint < PageSize && CacheT::canCache(RoundedSize)) {
+    LargeBlock::Header *H;
+    if (Cache.retrieve(RoundedSize, &H)) {
       if (BlockEnd)
-        *BlockEnd = H.BlockEnd;
-      void *Ptr = reinterpret_cast<void *>(reinterpret_cast<uptr>(&H) +
+        *BlockEnd = H->BlockEnd;
+      void *Ptr = reinterpret_cast<void *>(reinterpret_cast<uptr>(H) +
                                            LargeBlock::getHeaderSize());
       if (ZeroContents)
-        memset(Ptr, 0, H.BlockEnd - reinterpret_cast<uptr>(Ptr));
+        memset(Ptr, 0, H->BlockEnd - reinterpret_cast<uptr>(Ptr));
+      const uptr BlockSize = H->BlockEnd - reinterpret_cast<uptr>(H);
+      {
+        ScopedLock L(Mutex);
+        InUseBlocks.push_back(H);
+        AllocatedBytes += BlockSize;
+        NumberOfAllocs++;
+        Stats.add(StatAllocated, BlockSize);
+        Stats.add(StatMapped, H->MapSize);
+      }
       return Ptr;
     }
   }
 
   MapPlatformData Data = {};
   const uptr MapSize = RoundedSize + 2 * PageSize;
   uptr MapBase =
       reinterpret_cast<uptr>(map(nullptr, MapSize, "scudo:secondary",
void *MapAllocator<CacheT>::allocate(uptr Size, uptr AlignmentHint,
   const uptr Ptr =
       reinterpret_cast<uptr>(map(reinterpret_cast<void *>(CommitBase),
                                  CommitSize, "scudo:secondary", 0, &Data));
   LargeBlock::Header *H = reinterpret_cast<LargeBlock::Header *>(Ptr);
   H->MapBase = MapBase;
   H->MapSize = MapEnd - MapBase;
   H->BlockEnd = CommitBase + CommitSize;
   H->Data = Data;
+  if (BlockEnd)
+    *BlockEnd = CommitBase + CommitSize;
   {
     ScopedLock L(Mutex);
     InUseBlocks.push_back(H);
     AllocatedBytes += CommitSize;
     if (LargestSize < CommitSize)
       LargestSize = CommitSize;
     NumberOfAllocs++;
     Stats.add(StatAllocated, CommitSize);
     Stats.add(StatMapped, H->MapSize);
   }
-  if (BlockEnd)
-    *BlockEnd = CommitBase + CommitSize;
   return reinterpret_cast<void *>(Ptr + LargeBlock::getHeaderSize());
 }
 
-template <uptr MaxFreeListSize>
-void MapAllocator<MaxFreeListSize>::deallocate(void *Ptr) {
+template <class CacheT> void MapAllocator<CacheT>::deallocate(void *Ptr) {
   LargeBlock::Header *H = LargeBlock::getHeader(Ptr);
   const uptr Block = reinterpret_cast<uptr>(H);
+  const uptr CommitSize = H->BlockEnd - Block;
   {
     ScopedLock L(Mutex);
     InUseBlocks.remove(H);
-    const uptr CommitSize = H->BlockEnd - Block;
     FreedBytes += CommitSize;
     NumberOfFrees++;
     Stats.sub(StatAllocated, CommitSize);
-    if (MaxFreeListSize && FreeBlocks.size() < MaxFreeListSize) {
-      bool Inserted = false;
-      for (auto &F : FreeBlocks) {
-        const uptr FreeBlockSize = F.BlockEnd - reinterpret_cast<uptr>(&F);
-        if (FreeBlockSize >= CommitSize) {
-          FreeBlocks.insert(H, &F);
-          Inserted = true;
-          break;
-        }
-      }
-      if (!Inserted)
-        FreeBlocks.push_back(H);
-      const uptr RoundedAllocationStart =
-          roundUpTo(Block + LargeBlock::getHeaderSize(), getPageSizeCached());
-      MapPlatformData Data = H->Data;
-      // TODO(kostyak): use release_to_os_interval_ms
-      releasePagesToOS(Block, RoundedAllocationStart - Block,
-                       H->BlockEnd - RoundedAllocationStart, &Data);
-      return;
-    }
     Stats.sub(StatMapped, H->MapSize);
   }
+  if (CacheT::canCache(CommitSize) && Cache.store(H))
+    return;
   void *Addr = reinterpret_cast<void *>(H->MapBase);
   const uptr Size = H->MapSize;
   MapPlatformData Data = H->Data;
   unmap(Addr, Size, UNMAP_ALL, &Data);
 }
 
-template <uptr MaxFreeListSize>
-void MapAllocator<MaxFreeListSize>::getStats(ScopedString *Str) const {
+template <class CacheT>
+void MapAllocator<CacheT>::getStats(ScopedString *Str) const {
   Str->append(
       "Stats: MapAllocator: allocated %zu times (%zuK), freed %zu times "
       "(%zuK), remains %zu (%zuK) max %zuM\n",
       NumberOfAllocs, AllocatedBytes >> 10, NumberOfFrees, FreedBytes >> 10,
       NumberOfAllocs - NumberOfFrees, (AllocatedBytes - FreedBytes) >> 10,
       LargestSize >> 20);
 }
 
 } // namespace scudo
 
 #endif // SCUDO_SECONDARY_H_

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

#else
   testAllocatorThreaded<scudo::AndroidConfig>();
 #endif
 }
 
 struct DeathConfig {
   // Tiny allocator, its Primary only serves chunks of 1024 bytes.
   using DeathSizeClassMap = scudo::SizeClassMap<1U, 10U, 10U, 10U, 1U, 10U>;
   typedef scudo::SizeClassAllocator64<DeathSizeClassMap, 20U> Primary;
-  typedef scudo::MapAllocator<0U> Secondary;
+  typedef scudo::MapAllocator<scudo::MapAllocatorNoCache> Secondary;
   template <class A> using TSDRegistryT = scudo::TSDRegistrySharedT<A, 1U>;
 };
 
 TEST(ScudoCombinedTest, DeathCombined) {
   using AllocatorT = scudo::Allocator<DeathConfig>;
   auto Deleter = [](AllocatorT *A) {
     A->unmapTestOnly();
     delete A;

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

template <class SecondaryT> static void testSecondaryBasic(void) {
   SecondaryT *L = new SecondaryT;
   L->init(&S);
   const scudo::uptr Size = 1U << 16;
   void *P = L->allocate(Size);
   EXPECT_NE(P, nullptr);
   memset(P, 'A', Size);
   EXPECT_GE(SecondaryT::getBlockSize(P), Size);
   L->deallocate(P);
-  // If we are not using a free list, blocks are unmapped on deallocation.
-  if (SecondaryT::getMaxFreeListSize() == 0U)
+  // If the Secondary can't cache that pointer, it will be unmapped.
+  if (!SecondaryT::canCache(Size))
     EXPECT_DEATH(memset(P, 'A', Size), "");
 
   const scudo::uptr Align = 1U << 16;
   P = L->allocate(Size + Align, Align);
   EXPECT_NE(P, nullptr);
   void *AlignedP = reinterpret_cast<void *>(
       scudo::roundUpTo(reinterpret_cast<scudo::uptr>(P), Align));
   memset(AlignedP, 'A', Size);
   L->deallocate(P);
 
   std::vector<void *> V;
   for (scudo::uptr I = 0; I < 32U; I++)
     V.push_back(L->allocate(Size));
   std::shuffle(V.begin(), V.end(), std::mt19937(std::random_device()()));
   while (!V.empty()) {
     L->deallocate(V.back());
     V.pop_back();
   }
   scudo::ScopedString Str(1024);
   L->getStats(&Str);
   Str.output();
 }
 
 TEST(ScudoSecondaryTest, SecondaryBasic) {
-  testSecondaryBasic<scudo::MapAllocator<0U>>();
+  testSecondaryBasic<scudo::MapAllocator<scudo::MapAllocatorNoCache>>();
 #if !SCUDO_FUCHSIA
-  testSecondaryBasic<scudo::MapAllocator<>>();
-  testSecondaryBasic<scudo::MapAllocator<64U>>();
+  testSecondaryBasic<scudo::MapAllocator<scudo::MapAllocatorCache<>>>();
+  testSecondaryBasic<
+      scudo::MapAllocator<scudo::MapAllocatorCache<64U, 1UL << 20>>>();
 #endif
 }
 
 #if SCUDO_FUCHSIA
-using LargeAllocator = scudo::MapAllocator<0U>;
+using LargeAllocator = scudo::MapAllocator<scudo::MapAllocatorNoCache>;
 #else
-using LargeAllocator = scudo::MapAllocator<>;
+using LargeAllocator = scudo::MapAllocator<scudo::MapAllocatorCache<>>;
 #endif
 
 // This exercises a variety of combinations of size and alignment for the
 // MapAllocator. The size computation done here mimic the ones done by the
 // combined allocator.
 TEST(ScudoSecondaryTest, SecondaryCombinations) {
   constexpr scudo::uptr MinAlign = FIRST_32_SECOND_64(8, 16);
   constexpr scudo::uptr HeaderSize = scudo::roundUpTo(8, MinAlign);