[scudo][standalone] Add a free list to the Secondary

[cryptoad]

Summary

The secondary allocator is slow, because we map and unmap each block
on allocation and deallocation.

While I really like the security benefits of such a behavior, this
yields very disappointing performance numbers on Android for larger
allocation benchmarks.

So this change adds a free list to the secondary, that will hold
recently deallocated chunks, and (currently) release the extraneous
memory. This allows to save on some memory mapping operations on
allocation and deallocation. I do not think that this lowers the
security of the secondary, but can increase the memory footprint a
little bit (RSS & VA).

The maximum number of blocks the free list can hold is templatable,
0U meaning that we fallback to the old behavior. The higher that
number, the higher the extra memory footprint.

I added default configurations for all our platforms, but they are
likely to change in the near future based on needs and feedback.

[morehouse]

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

222

Nit: From is a bit ambiguous. Maybe AllocationStart is more precise?

228

This does not release the header page, but we still reduce StatAllocated by CommitSize, which includes the the header page. Is this intended?

[cryptoad]

Renaming the variable From to RoundedAllocationStart.

[cryptoad]

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

228

This is intended. I chose the value that would always be consistent between allocations & deallocations so that there is no discrepancy later one.
I initially used sizes that were closer to the actual user size but ended up with FreedBytes > AllocatedBytes and messed up stats.

compiler-rt/lib/scudo/standalone/CMakeLists.txt

set(SCUDO_SOURCES
   checksum.cpp
   crc32_hw.cpp
   common.cpp
   flags.cpp
   flags_parser.cpp
   fuchsia.cpp
   linux.cpp
   report.cpp
-  secondary.cpp
   string_utils.cpp
   )
 
 # Enable the SSE 4.2 instruction set for crc32_hw.cpp, if available.
 if (COMPILER_RT_HAS_MSSE4_2_FLAG)
   set_source_files_properties(crc32_hw.cpp PROPERTIES COMPILE_FLAGS -msse4.2)
 endif()
 

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

 //===-- allocator_config.h --------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SCUDO_ALLOCATOR_CONFIG_H_
 #define SCUDO_ALLOCATOR_CONFIG_H_
 
 #include "combined.h"
 #include "common.h"
 #include "flags.h"
 #include "primary32.h"
 #include "primary64.h"
+#include "secondary.h"
 #include "size_class_map.h"
 #include "tsd_exclusive.h"
 #include "tsd_shared.h"
 
 namespace scudo {
 
 // Default configurations for various platforms.
 
 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;
   template <class A> using TSDRegistryT = TSDRegistryExT<A>; // Exclusive
 };
 
 struct AndroidConfig {
   using SizeClassMap = AndroidSizeClassMap;
 #if SCUDO_CAN_USE_PRIMARY64
   // 1GB regions
   typedef SizeClassAllocator64<SizeClassMap, 30U> Primary;
 #else
   // 512KB regions
   typedef SizeClassAllocator32<SizeClassMap, 19U> Primary;
 #endif
+  typedef MapAllocator<> Secondary;
   template <class A>
   using TSDRegistryT = TSDRegistrySharedT<A, 2U>; // Shared, max 2 TSDs.
 };
 
 struct AndroidSvelteConfig {
   using SizeClassMap = SvelteSizeClassMap;
 #if SCUDO_CAN_USE_PRIMARY64
   // 512MB regions
   typedef SizeClassAllocator64<SizeClassMap, 29U> Primary;
 #else
   // 64KB regions
   typedef SizeClassAllocator32<SizeClassMap, 16U> Primary;
 #endif
+  typedef MapAllocator<0U> Secondary;
   template <class A>
   using TSDRegistryT = TSDRegistrySharedT<A, 1U>; // Shared, only 1 TSD.
 };
 
 struct FuchsiaConfig {
   // 1GB Regions
   typedef SizeClassAllocator64<DefaultSizeClassMap, 30U> Primary;
+  typedef MapAllocator<> Secondary;
   template <class A>
   using TSDRegistryT = TSDRegistrySharedT<A, 8U>; // Shared, max 8 TSDs.
 };
 
 #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

public:
   }
 
   void getStats(StatCounters S) {
     initThreadMaybe();
     Stats.get(S);
   }
 
 private:
-  typedef MapAllocator SecondaryT;
+  using SecondaryT = typename Params::Secondary;
   typedef typename PrimaryT::SizeClassMap SizeClassMap;
 
   static const uptr MinAlignmentLog = SCUDO_MIN_ALIGNMENT_LOG;
   static const uptr MaxAlignmentLog = 24U; // 16 MB seems reasonable.
   static const uptr MinAlignment = 1UL << MinAlignmentLog;
   static const uptr MaxAlignment = 1UL << MaxAlignmentLog;
   static const uptr MaxAllowedMallocSize =
       FIRST_32_SECOND_64(1UL << 31, 1ULL << 40);

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

 }
 
 static Header *getHeader(const void *Ptr) {
   return getHeader(reinterpret_cast<uptr>(Ptr));
 }
 
 } // namespace LargeBlock
 
-class MapAllocator {
+template <uptr MaxFreeListSize = 32U> class MapAllocator {
 public:
   void initLinkerInitialized(GlobalStats *S) {
     Stats.initLinkerInitialized();
     if (LIKELY(S))
       S->link(&Stats);
   }
   void init(GlobalStats *S) {
     memset(this, 0, sizeof(*this));
public:
 
   void 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; }
+
 private:
   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) {
+  DCHECK_GT(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 (BlockEnd)
+        *BlockEnd = H.BlockEnd;
+      return reinterpret_cast<void *>(reinterpret_cast<uptr>(&H) +
+                                      LargeBlock::getHeaderSize());
+    }
+  }
+
+  MapPlatformData Data = {};
+  const uptr MapSize = RoundedSize + 2 * PageSize;
+  uptr MapBase =
+      reinterpret_cast<uptr>(map(nullptr, MapSize, "scudo:secondary",
+                                 MAP_NOACCESS | MAP_ALLOWNOMEM, &Data));
+  if (UNLIKELY(!MapBase))
+    return nullptr;
+  uptr CommitBase = MapBase + PageSize;
+  uptr MapEnd = MapBase + MapSize;
+
+  // In the unlikely event of alignments larger than a page, adjust the amount
+  // of memory we want to commit, and trim the extra memory.
+  if (UNLIKELY(AlignmentHint >= PageSize)) {
+    // For alignments greater than or equal to a page, the user pointer (eg: the
+    // pointer that is returned by the C or C++ allocation APIs) ends up on a
+    // page boundary , and our headers will live in the preceding page.
+    CommitBase = roundUpTo(MapBase + PageSize + 1, AlignmentHint) - PageSize;
+    const uptr NewMapBase = CommitBase - PageSize;
+    DCHECK_GE(NewMapBase, MapBase);
+    // We only trim the extra memory on 32-bit platforms: 64-bit platforms
+    // are less constrained memory wise, and that saves us two syscalls.
+    if (SCUDO_WORDSIZE == 32U && NewMapBase != MapBase) {
+      unmap(reinterpret_cast<void *>(MapBase), NewMapBase - MapBase, 0, &Data);
+      MapBase = NewMapBase;
+    }
+    const uptr NewMapEnd = CommitBase + PageSize +
+                           roundUpTo((Size - AlignmentHint), PageSize) +
+                           PageSize;
+    DCHECK_LE(NewMapEnd, MapEnd);
+    if (SCUDO_WORDSIZE == 32U && NewMapEnd != MapEnd) {
+      unmap(reinterpret_cast<void *>(NewMapEnd), MapEnd - NewMapEnd, 0, &Data);
+      MapEnd = NewMapEnd;
+    }
+  }
+
+  const uptr CommitSize = MapEnd - PageSize - CommitBase;
+  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;
+  {
+    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) {
+  LargeBlock::Header *H = LargeBlock::getHeader(Ptr);
+  {
+    ScopedLock L(Mutex);
+    InUseBlocks.remove(H);
+    const uptr CommitSize = H->BlockEnd - reinterpret_cast<uptr>(H);
+    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(reinterpret_cast<uptr>(H) + LargeBlock::getHeaderSize(),
+                    getPageSizeCached());
+      MapPlatformData Data = H->Data;
+      // TODO(kostyak): use release_to_os_interval_ms
+      releasePagesToOS(H->MapBase, RoundedAllocationStart - H->MapBase,
+                       H->BlockEnd - RoundedAllocationStart, &Data);
+      return;
+    }
+    Stats.sub(StatMapped, H->MapSize);
+  }
+  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 {
+  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/secondary.cpp

-//===-- secondary.cpp -------------------------------------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "secondary.h"
-
-#include "string_utils.h"
-
-namespace scudo {
-
-// 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).
-void *MapAllocator::allocate(uptr Size, uptr AlignmentHint, uptr *BlockEnd) {
-  DCHECK_GT(Size, AlignmentHint);
-  const uptr PageSize = getPageSizeCached();
-  const uptr MapSize =
-      roundUpTo(Size + LargeBlock::getHeaderSize(), PageSize) + 2 * PageSize;
-  MapPlatformData Data = {};
-  uptr MapBase =
-      reinterpret_cast<uptr>(map(nullptr, MapSize, "scudo:secondary",
-                                 MAP_NOACCESS | MAP_ALLOWNOMEM, &Data));
-  if (UNLIKELY(!MapBase))
-    return nullptr;
-  uptr CommitBase = MapBase + PageSize;
-  uptr MapEnd = MapBase + MapSize;
-
-  // In the unlikely event of alignments larger than a page, adjust the amount
-  // of memory we want to commit, and trim the extra memory.
-  if (UNLIKELY(AlignmentHint >= PageSize)) {
-    // For alignments greater than or equal to a page, the user pointer (eg: the
-    // pointer that is returned by the C or C++ allocation APIs) ends up on a
-    // page boundary , and our headers will live in the preceding page.
-    CommitBase = roundUpTo(MapBase + PageSize + 1, AlignmentHint) - PageSize;
-    const uptr NewMapBase = CommitBase - PageSize;
-    DCHECK_GE(NewMapBase, MapBase);
-    // We only trim the extra memory on 32-bit platforms: 64-bit platforms
-    // are less constrained memory wise, and that saves us two syscalls.
-    if (SCUDO_WORDSIZE == 32U && NewMapBase != MapBase) {
-      unmap(reinterpret_cast<void *>(MapBase), NewMapBase - MapBase, 0, &Data);
-      MapBase = NewMapBase;
-    }
-    const uptr NewMapEnd = CommitBase + PageSize +
-                           roundUpTo((Size - AlignmentHint), PageSize) +
-                           PageSize;
-    DCHECK_LE(NewMapEnd, MapEnd);
-    if (SCUDO_WORDSIZE == 32U && NewMapEnd != MapEnd) {
-      unmap(reinterpret_cast<void *>(NewMapEnd), MapEnd - NewMapEnd, 0, &Data);
-      MapEnd = NewMapEnd;
-    }
-  }
-
-  const uptr CommitSize = MapEnd - PageSize - CommitBase;
-  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;
-  {
-    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());
-}
-
-void MapAllocator::deallocate(void *Ptr) {
-  LargeBlock::Header *H = LargeBlock::getHeader(Ptr);
-  {
-    ScopedLock L(Mutex);
-    InUseBlocks.remove(H);
-    const uptr CommitSize = H->BlockEnd - reinterpret_cast<uptr>(H);
-    FreedBytes += CommitSize;
-    NumberOfFrees++;
-    Stats.sub(StatAllocated, CommitSize);
-    Stats.sub(StatMapped, H->MapSize);
-  }
-  void *Addr = reinterpret_cast<void *>(H->MapBase);
-  const uptr Size = H->MapSize;
-  MapPlatformData Data;
-  Data = H->Data;
-  unmap(Addr, Size, UNMAP_ALL, &Data);
-}
-
-void MapAllocator::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

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

#endif
   UseQuarantine = false;
   testAllocatorThreaded<scudo::AndroidSvelteConfig>();
 }
 
 struct DeathConfig {
   // Tiny allocator, its Primary only serves chunks of 1024 bytes.
   using DeathSizeClassMap = scudo::SizeClassMap<1U, 10U, 10U, 10U, 1U, 10U>;
   typedef scudo::SizeClassAllocator32<DeathSizeClassMap, 18U> Primary;
+  typedef scudo::MapAllocator<0U> 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

 #include "gtest/gtest.h"
 
 #include <stdio.h>
 
 #include <condition_variable>
 #include <mutex>
 #include <thread>
 
-TEST(ScudoSecondaryTest, SecondaryBasic) {
+template <class SecondaryT> static void testSecondaryBasic(void) {
   scudo::GlobalStats S;
   S.init();
-  scudo::MapAllocator *L = new scudo::MapAllocator;
+  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(scudo::MapAllocator::getBlockSize(P), 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)
     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::random_shuffle(V.begin(), V.end());
   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<>>();
+  testSecondaryBasic<scudo::MapAllocator<0U>>();
+  testSecondaryBasic<scudo::MapAllocator<64U>>();
+}
+
+using LargeAllocator = scudo::MapAllocator<>;
+
 // 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);
-  scudo::MapAllocator *L = new scudo::MapAllocator;
+  LargeAllocator *L = new LargeAllocator;
   L->init(nullptr);
   for (scudo::uptr SizeLog = 0; SizeLog <= 20; SizeLog++) {
     for (scudo::uptr AlignLog = FIRST_32_SECOND_64(3, 4); AlignLog <= 16;
          AlignLog++) {
       const scudo::uptr Align = 1U << AlignLog;
       for (scudo::sptr Delta = -128; Delta <= 128; Delta += 8) {
         if (static_cast<scudo::sptr>(1U << SizeLog) + Delta <= 0)
           continue;
for (scudo::uptr SizeLog = 0; SizeLog <= 20; SizeLog++) {
     }
   }
   scudo::ScopedString Str(1024);
   L->getStats(&Str);
   Str.output();
 }
 
 TEST(ScudoSecondaryTest, SecondaryIterate) {
-  scudo::MapAllocator *L = new scudo::MapAllocator;
+  LargeAllocator *L = new LargeAllocator;
   L->init(nullptr);
   std::vector<void *> V;
   const scudo::uptr PageSize = scudo::getPageSizeCached();
   for (scudo::uptr I = 0; I < 32U; I++)
     V.push_back(L->allocate((std::rand() % 16) * PageSize));
   auto Lambda = [V](scudo::uptr Block) {
     EXPECT_NE(std::find(V.begin(), V.end(), reinterpret_cast<void *>(Block)),
               V.end());
TEST(ScudoSecondaryTest, SecondaryIterate) {
   L->getStats(&Str);
   Str.output();
 }
 
 static std::mutex Mutex;
 static std::condition_variable Cv;
 static bool Ready = false;
 
-static void performAllocations(scudo::MapAllocator *L) {
+static void performAllocations(LargeAllocator *L) {
   std::vector<void *> V;
   const scudo::uptr PageSize = scudo::getPageSizeCached();
   {
     std::unique_lock<std::mutex> Lock(Mutex);
     while (!Ready)
       Cv.wait(Lock);
   }
   for (scudo::uptr I = 0; I < 32U; I++)
     V.push_back(L->allocate((std::rand() % 16) * PageSize));
   while (!V.empty()) {
     L->deallocate(V.back());
     V.pop_back();
   }
 }
 
 TEST(ScudoSecondaryTest, SecondaryThreadsRace) {
-  scudo::MapAllocator *L = new scudo::MapAllocator;
+  LargeAllocator *L = new LargeAllocator;
   L->init(nullptr);
   std::thread Threads[10];
   for (scudo::uptr I = 0; I < 10U; I++)
     Threads[I] = std::thread(performAllocations, L);
   {
     std::unique_lock<std::mutex> Lock(Mutex);
     Ready = true;
     Cv.notify_all();
   }
   for (auto &T : Threads)
     T.join();
   scudo::ScopedString Str(1024);
   L->getStats(&Str);
   Str.output();
 }