[scudo][standalone] Shift some data from dynamic to static

[cryptoad]

Summary

Most of our larger data is dynamically allocated (via map) but it
became an hindrance with regard to init time, for a cost to benefit
ratio that is not great. So change the TSDs, RegionInfo, ByteMap
to be static.

Additionally, for reclaiming, we used mapped & unmapped a buffer each
time, which is costly. It turns out that we can have a static buffer,
and that there isn't much contention on it.

One of the other things changed here, is that we hard set the number
of TSDs on Android to the maximum number, as there could be a
situation where cores are put to sleep and we could miss some.

[cryptoad]

Correcting a comment.

[hctim]

LGTM w/ nits

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

22

Nit: remove

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

42–43

Update?

72–78

nit: sizeof(StaticBuffer) should be a constant somewhere

[cryptoad]

Addressing the Mitch's comments.

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
+  release.cpp
   report.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/bytemap.h

 #include "atomic_helpers.h"
 #include "common.h"
 #include "mutex.h"
 
 namespace scudo {
 
 template <uptr Size> class FlatByteMap {
 public:
-  void initLinkerInitialized() {
-    Map = reinterpret_cast<u8 *>(map(nullptr, Size, "scudo:bytemap"));
-  }
-  void init() { initLinkerInitialized(); }
+  void initLinkerInitialized() {}
+  void init() { memset(Map, 0, sizeof(Map)); }
 
-  void unmapTestOnly() { unmap(reinterpret_cast<void *>(Map), Size); }
+  void unmapTestOnly() {}
 
   void set(uptr Index, u8 Value) {
     DCHECK_LT(Index, Size);
     DCHECK_EQ(0U, Map[Index]);
     Map[Index] = Value;
   }
   u8 operator[](uptr Index) {
     DCHECK_LT(Index, Size);
     return Map[Index];
   }
 
   void disable() {}
   void enable() {}
 
 private:
-  u8 *Map;
+  u8 Map[Size];
 };
 
 } // namespace scudo
 
 #endif // SCUDO_BYTEMAP_H_

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

 // allow to transfer arrays of pointers from the global size class freelist to
 // the thread specific freelist for said class, and back.
 //
 // Memory used by this allocator is never unmapped but can be partially
 // reclaimed if the platform allows for it.
 
 template <class SizeClassMapT, uptr RegionSizeLog,
           s32 MinReleaseToOsIntervalMs = INT32_MIN,
-          s32 MaxReleaseToOsIntervalMs = INT32_MAX> class SizeClassAllocator32 {
+          s32 MaxReleaseToOsIntervalMs = INT32_MAX>
+class SizeClassAllocator32 {
 public:
   typedef SizeClassMapT SizeClassMap;
   // The bytemap can only track UINT8_MAX - 1 classes.
   static_assert(SizeClassMap::LargestClassId <= (UINT8_MAX - 1), "");
   // Regions should be large enough to hold the largest Block.
   static_assert((1UL << RegionSizeLog) >= SizeClassMap::MaxSize, "");
   typedef SizeClassAllocator32<SizeClassMapT, RegionSizeLog,
                                MinReleaseToOsIntervalMs,
-                               MaxReleaseToOsIntervalMs> ThisT;
+                               MaxReleaseToOsIntervalMs>
+      ThisT;
   typedef SizeClassAllocatorLocalCache<ThisT> CacheT;
   typedef typename CacheT::TransferBatch TransferBatch;
   static const bool SupportsMemoryTagging = false;
 
   static uptr getSizeByClassId(uptr ClassId) {
     return (ClassId == SizeClassMap::BatchClassId)
                ? sizeof(TransferBatch)
                : SizeClassMap::getSizeByClassId(ClassId);

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

 
 template <class SizeClassMapT, uptr RegionSizeLog,
           s32 MinReleaseToOsIntervalMs = INT32_MIN,
           s32 MaxReleaseToOsIntervalMs = INT32_MAX,
           bool MaySupportMemoryTagging = false>
 class SizeClassAllocator64 {
 public:
   typedef SizeClassMapT SizeClassMap;
-  typedef SizeClassAllocator64<SizeClassMap, RegionSizeLog,
-                               MinReleaseToOsIntervalMs,
-                               MaxReleaseToOsIntervalMs,
-                               MaySupportMemoryTagging>
+  typedef SizeClassAllocator64<
+      SizeClassMap, RegionSizeLog, MinReleaseToOsIntervalMs,
+      MaxReleaseToOsIntervalMs, MaySupportMemoryTagging>
       ThisT;
   typedef SizeClassAllocatorLocalCache<ThisT> CacheT;
   typedef typename CacheT::TransferBatch TransferBatch;
   static const bool SupportsMemoryTagging =
       MaySupportMemoryTagging && archSupportsMemoryTagging();
 
   static uptr getSizeByClassId(uptr ClassId) {
     return (ClassId == SizeClassMap::BatchClassId)
                ? sizeof(TransferBatch)
                : SizeClassMap::getSizeByClassId(ClassId);
   }
 
   static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }
 
   void initLinkerInitialized(s32 ReleaseToOsInterval) {
     // Reserve the space required for the Primary.
     PrimaryBase = reinterpret_cast<uptr>(
         map(nullptr, PrimarySize, "scudo:primary", MAP_NOACCESS, &Data));
 
-    RegionInfoArray = reinterpret_cast<RegionInfo *>(
-        map(nullptr, sizeof(RegionInfo) * NumClasses, "scudo:regioninfo"));
-    DCHECK_EQ(reinterpret_cast<uptr>(RegionInfoArray) % SCUDO_CACHE_LINE_SIZE,
-              0);
-
     u32 Seed;
     if (UNLIKELY(!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed))))
       Seed = static_cast<u32>(getMonotonicTime() ^ (PrimaryBase >> 12));
     const uptr PageSize = getPageSizeCached();
     for (uptr I = 0; I < NumClasses; I++) {
       RegionInfo *Region = getRegionInfo(I);
       // The actual start of a region is offseted by a random number of pages.
       Region->RegionBeg =
public:
   }
   void init(s32 ReleaseToOsInterval) {
     memset(this, 0, sizeof(*this));
     initLinkerInitialized(ReleaseToOsInterval);
   }
 
   void unmapTestOnly() {
     unmap(reinterpret_cast<void *>(PrimaryBase), PrimarySize, UNMAP_ALL, &Data);
-    unmap(reinterpret_cast<void *>(RegionInfoArray),
-          sizeof(RegionInfo) * NumClasses);
   }
 
   TransferBatch *popBatch(CacheT *C, uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     RegionInfo *Region = getRegionInfo(ClassId);
     ScopedLock L(Region->Mutex);
     TransferBatch *B = Region->FreeList.front();
     if (B) {
void enable() {
     getRegionInfo(SizeClassMap::BatchClassId)->Mutex.unlock();
     for (uptr I = 0; I < NumClasses; I++) {
       if (I == SizeClassMap::BatchClassId)
         continue;
       getRegionInfo(I)->Mutex.unlock();
     }
   }
 
-  template <typename F> void iterateOverBlocks(F Callback) const {
+  template <typename F> void iterateOverBlocks(F Callback) {
     for (uptr I = 0; I < NumClasses; I++) {
       if (I == SizeClassMap::BatchClassId)
         continue;
       const RegionInfo *Region = getRegionInfo(I);
       const uptr BlockSize = getSizeByClassId(I);
       const uptr From = Region->RegionBeg;
       const uptr To = From + Region->AllocatedUser;
       for (uptr Block = From; Block < To; Block += BlockSize)
         Callback(Block);
     }
   }
 
-  void getStats(ScopedString *Str) const {
+  void getStats(ScopedString *Str) {
     // TODO(kostyak): get the RSS per region.
     uptr TotalMapped = 0;
     uptr PoppedBlocks = 0;
     uptr PushedBlocks = 0;
     for (uptr I = 0; I < NumClasses; I++) {
       RegionInfo *Region = getRegionInfo(I);
       if (Region->MappedUser)
         TotalMapped += Region->MappedUser;
struct ALIGNED(SCUDO_CACHE_LINE_SIZE) RegionInfo {
     uptr MappedUser;    // Bytes mapped for user memory.
     uptr AllocatedUser; // Bytes allocated for user memory.
     MapPlatformData Data;
     ReleaseToOsInfo ReleaseInfo;
   };
   static_assert(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");
 
   uptr PrimaryBase;
-  RegionInfo *RegionInfoArray;
   MapPlatformData Data;
   atomic_s32 ReleaseToOsIntervalMs;
   bool UseMemoryTagging;
+  RegionInfo RegionInfoArray[NumClasses];
 
-  RegionInfo *getRegionInfo(uptr ClassId) const {
+  RegionInfo *getRegionInfo(uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     return &RegionInfoArray[ClassId];
   }
 
   uptr getRegionBaseByClassId(uptr ClassId) const {
     return PrimaryBase + (ClassId << RegionSizeLog);
   }
 
NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId,
     Region->AllocatedUser += AllocatedUser;
     Region->Exhausted = false;
     if (Region->CanRelease)
       Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
 
     return B;
   }
 
-  void getStats(ScopedString *Str, uptr ClassId, uptr Rss) const {
+  void getStats(ScopedString *Str, uptr ClassId, uptr Rss) {
     RegionInfo *Region = getRegionInfo(ClassId);
     if (Region->MappedUser == 0)
       return;
     const uptr InUse = Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks;
     const uptr TotalChunks = Region->AllocatedUser / getSizeByClassId(ClassId);
     Str->append("%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
                 "inuse: %6zu total: %6zu rss: %6zuK releases: %6zu last "
                 "released: %6zuK region: 0x%zx (0x%zx)\n",

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

 //===-- release.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_RELEASE_H_
 #define SCUDO_RELEASE_H_
 
 #include "common.h"
 #include "list.h"
+#include "mutex.h"
 
 namespace scudo {
 
 class ReleaseRecorder {
 public:
   ReleaseRecorder(uptr BaseAddress, MapPlatformData *Data = nullptr)
       : BaseAddress(BaseAddress), Data(Data) {}
 

 
 private:
   uptr ReleasedRangesCount = 0;
   uptr ReleasedBytes = 0;
   uptr BaseAddress = 0;
   MapPlatformData *Data = nullptr;
 };
 
 // A packed array of Counters. Each counter occupies 2^N bits, enough to store
-// counter's MaxValue. Ctor will try to allocate the required Buffer via map()
-// and the caller is expected to check whether the initialization was successful
-// by checking isAllocated() result. For the 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.
+// counter's MaxValue. Ctor will try to use a static buffer first, and if that
+// 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) {
     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);
+    if (BufferSize <= StaticBufferSize && Mutex.tryLock()) {
+      Buffer = &StaticBuffer[0];
+      memset(Buffer, 0, BufferSize);
+    } else {
       Buffer = reinterpret_cast<uptr *>(
           map(nullptr, BufferSize, "scudo:counters", MAP_ALLOWNOMEM));
     }
+  }
   ~PackedCounterArray() {
-    if (isAllocated())
+    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 get(uptr I) const {
private:
   const uptr N;
   uptr CounterSizeBitsLog;
   uptr CounterMask;
   uptr PackingRatioLog;
   uptr BitOffsetMask;
 
   uptr BufferSize;
   uptr *Buffer;
+
+  static HybridMutex Mutex;
+  static const uptr StaticBufferSize = 1024U;
+  static uptr StaticBuffer[StaticBufferSize];
 };
 
 template <class ReleaseRecorderT> class FreePagesRangeTracker {
 public:
   explicit FreePagesRangeTracker(ReleaseRecorderT *Recorder)
       : Recorder(Recorder), PageSizeLog(getLog2(getPageSizeCached())) {}
 
   void processNextPage(bool Freed) {

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

+//===-- release.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 "release.h"
+
+namespace scudo {
+
+HybridMutex PackedCounterArray::Mutex = {};
+uptr PackedCounterArray::StaticBuffer[1024];
+
+} // namespace scudo

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

 };
 
 template <class Allocator> void teardownThread(void *Ptr);
 
 template <class Allocator> struct TSDRegistryExT {
   void initLinkerInitialized(Allocator *Instance) {
     Instance->initLinkerInitialized();
     CHECK_EQ(pthread_key_create(&PThreadKey, teardownThread<Allocator>), 0);
-    FallbackTSD = reinterpret_cast<TSD<Allocator> *>(
-        map(nullptr, sizeof(TSD<Allocator>), "scudo:tsd"));
-    FallbackTSD->initLinkerInitialized(Instance);
+    FallbackTSD.initLinkerInitialized(Instance);
     Initialized = true;
   }
   void init(Allocator *Instance) {
     memset(this, 0, sizeof(*this));
     initLinkerInitialized(Instance);
   }
 
-  void unmapTestOnly() {
-    unmap(reinterpret_cast<void *>(FallbackTSD), sizeof(TSD<Allocator>));
-  }
+  void unmapTestOnly() {}
 
   ALWAYS_INLINE void initThreadMaybe(Allocator *Instance, bool MinimalInit) {
     if (LIKELY(State != ThreadState::NotInitialized))
       return;
     initThread(Instance, MinimalInit);
   }
 
   ALWAYS_INLINE TSD<Allocator> *getTSDAndLock(bool *UnlockRequired) {
     if (LIKELY(State == ThreadState::Initialized &&
                !atomic_load(&Disabled, memory_order_acquire))) {
       *UnlockRequired = false;
       return &ThreadTSD;
     }
-    DCHECK(FallbackTSD);
-    FallbackTSD->lock();
+    FallbackTSD.lock();
     *UnlockRequired = true;
-    return FallbackTSD;
+    return &FallbackTSD;
   }
 
   // To disable the exclusive TSD registry, we effectively lock the fallback TSD
   // and force all threads to attempt to use it instead of their local one.
   void disable() {
     Mutex.lock();
-    FallbackTSD->lock();
+    FallbackTSD.lock();
     atomic_store(&Disabled, 1U, memory_order_release);
   }
 
   void enable() {
     atomic_store(&Disabled, 0U, memory_order_release);
-    FallbackTSD->unlock();
+    FallbackTSD.unlock();
     Mutex.unlock();
   }
 
 private:
   void initOnceMaybe(Allocator *Instance) {
     ScopedLock L(Mutex);
     if (LIKELY(Initialized))
       return;
NOINLINE void initThread(Allocator *Instance, bool MinimalInit) {
     ThreadTSD.initLinkerInitialized(Instance);
     State = ThreadState::Initialized;
     Instance->callPostInitCallback();
   }
 
   pthread_key_t PThreadKey;
   bool Initialized;
   atomic_u8 Disabled;
-  TSD<Allocator> *FallbackTSD;
+  TSD<Allocator> FallbackTSD;
   HybridMutex Mutex;
   static THREADLOCAL ThreadState State;
   static THREADLOCAL TSD<Allocator> ThreadTSD;
 
   friend void teardownThread<Allocator>(void *Ptr);
 };
 
 template <class Allocator>

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

 
 namespace scudo {
 
 template <class Allocator, u32 MaxTSDCount> struct TSDRegistrySharedT {
   void initLinkerInitialized(Allocator *Instance) {
     Instance->initLinkerInitialized();
     CHECK_EQ(pthread_key_create(&PThreadKey, nullptr), 0); // For non-TLS
     const u32 NumberOfCPUs = getNumberOfCPUs();
-    NumberOfTSDs =
-        (NumberOfCPUs == 0) ? MaxTSDCount : Min(NumberOfCPUs, MaxTSDCount);
-    TSDs = reinterpret_cast<TSD<Allocator> *>(
-        map(nullptr, sizeof(TSD<Allocator>) * NumberOfTSDs, "scudo:tsd"));
+    NumberOfTSDs = (SCUDO_ANDROID || NumberOfCPUs == 0)
+                       ? MaxTSDCount
+                       : Min(NumberOfCPUs, MaxTSDCount);
     for (u32 I = 0; I < NumberOfTSDs; I++)
       TSDs[I].initLinkerInitialized(Instance);
     // Compute all the coprimes of NumberOfTSDs. This will be used to walk the
     // array of TSDs in a random order. For details, see:
     // https://lemire.me/blog/2017/09/18/visiting-all-values-in-an-array-exactly-once-in-random-order/
     for (u32 I = 0; I < NumberOfTSDs; I++) {
       u32 A = I + 1;
       u32 B = NumberOfTSDs;
void initLinkerInitialized(Allocator *Instance) {
     Initialized = true;
   }
   void init(Allocator *Instance) {
     memset(this, 0, sizeof(*this));
     initLinkerInitialized(Instance);
   }
 
   void unmapTestOnly() {
-    unmap(reinterpret_cast<void *>(TSDs),
-          sizeof(TSD<Allocator>) * NumberOfTSDs);
     setCurrentTSD(nullptr);
     pthread_key_delete(PThreadKey);
   }
 
   ALWAYS_INLINE void initThreadMaybe(Allocator *Instance,
                                      UNUSED bool MinimalInit) {
     if (LIKELY(getCurrentTSD()))
       return;
NOINLINE TSD<Allocator> *getTSDAndLockSlow(TSD<Allocator> *CurrentTSD) {
     // Last resort, stick with the current one.
     CurrentTSD->lock();
     return CurrentTSD;
   }
 
   pthread_key_t PThreadKey;
   atomic_u32 CurrentIndex;
   u32 NumberOfTSDs;
-  TSD<Allocator> *TSDs;
   u32 NumberOfCoPrimes;
   u32 CoPrimes[MaxTSDCount];
   bool Initialized;
   HybridMutex Mutex;
+  TSD<Allocator> TSDs[MaxTSDCount];
 #if SCUDO_LINUX && !_BIONIC
   static THREADLOCAL TSD<Allocator> *ThreadTSD;
 #endif
 };
 
 #if SCUDO_LINUX && !_BIONIC
 template <class Allocator, u32 MaxTSDCount>
 THREADLOCAL TSD<Allocator>
     *TSDRegistrySharedT<Allocator, MaxTSDCount>::ThreadTSD;
 #endif
 
 } // namespace scudo
 
 #endif // SCUDO_TSD_SHARED_H_

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

return scudo::setErrnoOnNull(
       SCUDO_ALLOCATOR.allocate(size, scudo::Chunk::Origin::Malloc, alignment));
 }
 
 INTERFACE WEAK int SCUDO_PREFIX(malloc_info)(UNUSED int options, FILE *stream) {
   const scudo::uptr max_size =
       decltype(SCUDO_ALLOCATOR)::PrimaryT::SizeClassMap::MaxSize;
   auto *sizes = static_cast<scudo::uptr *>(
       SCUDO_PREFIX(calloc)(max_size, sizeof(scudo::uptr)));
-  auto callback = [](uintptr_t, size_t size, void* arg) {
+  auto callback = [](uintptr_t, size_t size, void *arg) {
     auto *sizes = reinterpret_cast<scudo::uptr *>(arg);
     if (size < max_size)
       sizes[size]++;
   };
   SCUDO_ALLOCATOR.iterateOverChunks(0, -1ul, callback, sizes);
 
   fputs("<malloc version=\"scudo-1\">\n", stream);
   for (scudo::uptr i = 0; i != max_size; ++i)