scudo: Table driven size classes for Android allocator.

[pcc]

Summary

Add an optional table lookup after the existing logarithm computation
for MidSize < Size <= MaxSize during size -> class lookups. The lookup is
O(1) due to indexing a precomputed (via constexpr) table based on a size
table. Switch to this approach for the Android size class maps.

Other approaches considered:

• Binary search was found to have an unacceptable (~30%) performance cost.
• An approach using NEON instructions (see older version of D73824) was found to be slightly slower than this approach on newer SoCs but significantly slower on older ones.

By selecting the values in the size tables to minimize wastage (for example,
by passing the malloc_info output of a target program to the included
compute_size_class_config program), we can increase the density of allocations
at a small (~0.5% on bionic malloc_sql_trace as measured using an identity
table) performance cost.

Reduces RSS on specific Android processes as follows (KB):

Before  After

zygote (median of 50 runs) 26836 26792 (-0.2%)
zygote64 (median of 50 runs) 30384 30076 (-1.0%)
dex2oat (median of 3 runs) 375792 372952 (-0.8%)

I also measured the amount of whole-system idle dirty heap on Android by
rebooting the system and then running the following script repeatedly until
the results were stable:

for i in $(seq 1 50); do grep -A5 scudo: /proc/*/smaps | grep Pss: | cut -d: -f2 | awk '{s+=$1} END {print s}' ; sleep 1; done

I did this 3 times both before and after this change and the results were:

Before: 365650, 356795, 372663
After: 344521, 356328, 342589

These results are noisy so it is hard to make a definite conclusion, but
there does appear to be a significant effect.

On other platforms, increase the sizes of all size classes by a fixed offset
equal to the size of the allocation header. This has also been found to improve
density, since it is likely for allocation sizes to be a power of 2, which
would otherwise waste space by pushing the allocation into the next size class.

[merge_guards_bot]

Unit tests: fail. 62377 tests passed, 1 failed and 839 were skipped.

failed: libc++.std/thread/thread_mutex/thread_mutex_requirements/thread_timedmutex_requirements/thread_timedmutex_recursive/try_lock_until.pass.cpp

clang-tidy: pass.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

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.

[pcc]

New approach

[merge_guards_bot]

Unit tests: unknown.

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

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

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

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

[pcc]

Finalize

[pcc]

PTAL

[cferris]

I do see RSS benefits in 32 bit, but the benefits are much larger in 64 bit runs. I see some performance fluctuations, but it looks like some got faster, some got slower, so probably in the noise.

On the whole, this does look like a net benefit.

[cryptoad]

I think this looks good.
I tried it on Android and it seems to be doing as advertised, have you tried this on Fuchsia/Linux? I'm currently giving it a go in g3.

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

90

Do we want to do this here or make sure that any call to this function will fall into the next if? I am not sure which one is better.

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

168

Why that line?

[pcc]

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

90

Hmm, it seems like we would need something like a conditional either way to make sure that getClassIdBySize(16) doesn't return an invalid class id. The way that I've done it seems more clear/explicit.

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

168

Sorry, this was just something that I added temporarily to keep the tests passing (because we're now moving between size classes in the test code here) and forgot to clean up. I'll fix this so that it's testing what is intended.

[pcc]

• Adjust the test to use MaxSize-64

[cryptoad]

Thank you Peter!

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

 //===-- size_class_map.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_SIZE_CLASS_MAP_H_
 #define SCUDO_SIZE_CLASS_MAP_H_
 
+#include "chunk.h"
 #include "common.h"
 #include "string_utils.h"
 
 namespace scudo {
 
+inline uptr scaledLog2(uptr Size, uptr ZeroLog, uptr LogBits) {
+  const uptr L = getMostSignificantSetBitIndex(Size);
+  const uptr LBits = (Size >> (L - LogBits)) - (1 << LogBits);
+  const uptr HBits = (L - ZeroLog) << LogBits;
+  return LBits + HBits;
+}
+
+template <typename Config> struct SizeClassMapBase {
+  static u32 getMaxCachedHint(uptr Size) {
+    DCHECK_LE(Size, MaxSize);
+    DCHECK_NE(Size, 0);
+    u32 N;
+    // Force a 32-bit division if the template parameters allow for it.
+    if (Config::MaxBytesCachedLog > 31 || Config::MaxSizeLog > 31)
+      N = static_cast<u32>((1UL << Config::MaxBytesCachedLog) / Size);
+    else
+      N = (1U << Config::MaxBytesCachedLog) / static_cast<u32>(Size);
+    return Max(1U, Min(Config::MaxNumCachedHint, N));
+  }
+};
+
 // SizeClassMap maps allocation sizes into size classes and back, in an
 // efficient table-free manner.
 //
 // Class 0 is a special class that doesn't abide by the same rules as other
 // classes. The allocator uses it to hold batches.
 //
 // The other sizes are controlled by the template parameters:
 // - MinSizeLog: defines the first class as 2^MinSizeLog bytes.
 // - MaxSizeLog: defines the last class as 2^MaxSizeLog bytes.
 // - MidSizeLog: classes increase with step 2^MinSizeLog from 2^MinSizeLog to
 //               2^MidSizeLog bytes.
 // - NumBits: the number of non-zero bits in sizes after 2^MidSizeLog.
 //            eg. with NumBits==3 all size classes after 2^MidSizeLog look like
 //            0b1xx0..0 (where x is either 0 or 1).
 //
 // This class also gives a hint to a thread-caching allocator about the amount
 // of chunks that can be cached per-thread:
 // - MaxNumCachedHint is a hint for the max number of chunks cached per class.
 // - 2^MaxBytesCachedLog is the max number of bytes cached per class.
+template <typename Config>
+class FixedSizeClassMap : public SizeClassMapBase<Config> {
+  typedef SizeClassMapBase<Config> Base;
 
-template <u8 NumBits, u8 MinSizeLog, u8 MidSizeLog, u8 MaxSizeLog,
-          u32 MaxNumCachedHintT, u8 MaxBytesCachedLog>
-class SizeClassMap {
-  static const uptr MinSize = 1UL << MinSizeLog;
-  static const uptr MidSize = 1UL << MidSizeLog;
+  static const uptr MinSize = 1UL << Config::MinSizeLog;
+  static const uptr MidSize = 1UL << Config::MidSizeLog;
   static const uptr MidClass = MidSize / MinSize;
-  static const u8 S = NumBits - 1;
+  static const u8 S = Config::NumBits - 1;
   static const uptr M = (1UL << S) - 1;
 
+  static const uptr SizeDelta = Chunk::getHeaderSize();
+
 public:
-  static const u32 MaxNumCachedHint = MaxNumCachedHintT;
+  static const u32 MaxNumCachedHint = Config::MaxNumCachedHint;
 
-  static const uptr MaxSize = 1UL << MaxSizeLog;
+  static const uptr MaxSize = (1UL << Config::MaxSizeLog) + SizeDelta;
   static const uptr NumClasses =
-      MidClass + ((MaxSizeLog - MidSizeLog) << S) + 1;
+      MidClass + ((Config::MaxSizeLog - Config::MidSizeLog) << S) + 1;
   static_assert(NumClasses <= 256, "");
   static const uptr LargestClassId = NumClasses - 1;
   static const uptr BatchClassId = 0;
 
   static uptr getSizeByClassId(uptr ClassId) {
     DCHECK_NE(ClassId, BatchClassId);
     if (ClassId <= MidClass)
-      return ClassId << MinSizeLog;
+      return (ClassId << Config::MinSizeLog) + SizeDelta;
     ClassId -= MidClass;
     const uptr T = MidSize << (ClassId >> S);
-    return T + (T >> S) * (ClassId & M);
+    return T + (T >> S) * (ClassId & M) + SizeDelta;
   }
 
   static uptr getClassIdBySize(uptr Size) {
+    if (Size <= SizeDelta + (1 << Config::MinSizeLog))
+      return 1;
+    Size -= SizeDelta;
     DCHECK_LE(Size, MaxSize);
     if (Size <= MidSize)
-      return (Size + MinSize - 1) >> MinSizeLog;
-    Size -= 1;
-    const uptr L = getMostSignificantSetBitIndex(Size);
-    const uptr LBits = (Size >> (L - S)) - (1 << S);
-    const uptr HBits = (L - MidSizeLog) << S;
-    return MidClass + 1 + HBits + LBits;
+      return (Size + MinSize - 1) >> Config::MinSizeLog;
+    return MidClass + 1 + scaledLog2(Size - 1, Config::MidSizeLog, S);
   }
+};
 
-  static u32 getMaxCachedHint(uptr Size) {
+template <typename Config>
+class TableSizeClassMap : public SizeClassMapBase<Config> {
+  static const u8 S = Config::NumBits - 1;
+  static const uptr M = (1UL << S) - 1;
+  static const uptr ClassesSize =
+      sizeof(Config::Classes) / sizeof(Config::Classes[0]);
+
+  struct SizeTable {
+    constexpr SizeTable() {
+      uptr Pos = 1 << Config::MidSizeLog;
+      uptr Inc = 1 << (Config::MidSizeLog - S);
+      for (uptr i = 0; i != getTableSize(); ++i) {
+        Pos += Inc;
+        if ((Pos & (Pos - 1)) == 0)
+          Inc *= 2;
+        Tab[i] = computeClassId(Pos + Config::SizeDelta);
+      }
+    }
+
+    constexpr static u8 computeClassId(uptr Size) {
+      for (uptr i = 0; i != ClassesSize; ++i) {
+        if (Size <= Config::Classes[i])
+          return i + 1;
+      }
+      return -1;
+    }
+
+    constexpr static uptr getTableSize() {
+      return (Config::MaxSizeLog - Config::MidSizeLog) << S;
+    }
+
+    u8 Tab[getTableSize()] = {};
+  };
+
+  static constexpr SizeTable Table = {};
+
+public:
+  static const u32 MaxNumCachedHint = Config::MaxNumCachedHint;
+
+  static const uptr NumClasses = ClassesSize + 1;
+  static_assert(NumClasses < 256, "");
+  static const uptr LargestClassId = NumClasses - 1;
+  static const uptr BatchClassId = 0;
+  static const uptr MaxSize = Config::Classes[LargestClassId - 1];
+
+  static uptr getSizeByClassId(uptr ClassId) {
+    return Config::Classes[ClassId - 1];
+  }
+
+  static uptr getClassIdBySize(uptr Size) {
+    if (Size <= Config::Classes[0])
+      return 1;
+    Size -= Config::SizeDelta;
     DCHECK_LE(Size, MaxSize);
-    DCHECK_NE(Size, 0);
-    u32 N;
-    // Force a 32-bit division if the template parameters allow for it.
-    if (MaxBytesCachedLog > 31 || MaxSizeLog > 31)
-      N = static_cast<u32>((1UL << MaxBytesCachedLog) / Size);
-    else
-      N = (1U << MaxBytesCachedLog) / static_cast<u32>(Size);
-    return Max(1U, Min(MaxNumCachedHint, N));
+    if (Size <= (1 << Config::MidSizeLog))
+      return ((Size - 1) >> Config::MinSizeLog) + 1;
+    return Table.Tab[scaledLog2(Size - 1, Config::MidSizeLog, S)];
   }
 
-  static void print() {
-    ScopedString Buffer(1024);
-    uptr PrevS = 0;
-    uptr TotalCached = 0;
-    for (uptr I = 0; I < NumClasses; I++) {
-      if (I == BatchClassId)
-        continue;
-      const uptr S = getSizeByClassId(I);
-      if (S >= MidSize / 2 && (S & (S - 1)) == 0)
-        Buffer.append("\n");
-      const uptr D = S - PrevS;
-      const uptr P = PrevS ? (D * 100 / PrevS) : 0;
-      const uptr L = S ? getMostSignificantSetBitIndex(S) : 0;
-      const uptr Cached = getMaxCachedHint(S) * S;
-      Buffer.append(
-          "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %zu %zu; id %zu\n",
-          I, getSizeByClassId(I), D, P, L, getMaxCachedHint(S), Cached,
-          getClassIdBySize(S));
-      TotalCached += Cached;
-      PrevS = S;
-    }
-    Buffer.append("Total Cached: %zu\n", TotalCached);
-    Buffer.output();
-  }
+  static void print() {}
+  static void validate() {}
+};
+
+struct AndroidSizeClassConfig {
+#if SCUDO_WORDSIZE == 64U
+  // Measured using a system_server profile.
+  static const uptr NumBits = 7;
+  static const uptr MinSizeLog = 4;
+  static const uptr MidSizeLog = 6;
+  static const uptr MaxSizeLog = 16;
+  static const u32 MaxNumCachedHint = 14;
+  static const uptr MaxBytesCachedLog = 14;
+
+  static constexpr u32 Classes[] = {
+      0x00020, 0x00030, 0x00040, 0x00050, 0x00060, 0x00070, 0x00090, 0x000a0,
+      0x000b0, 0x000e0, 0x00110, 0x00130, 0x001a0, 0x00240, 0x00320, 0x00430,
+      0x00640, 0x00830, 0x00a10, 0x00c30, 0x01010, 0x01150, 0x01ad0, 0x02190,
+      0x03610, 0x04010, 0x04510, 0x04d10, 0x05a10, 0x07310, 0x09610, 0x10010,
+  };
+  static const uptr SizeDelta = 16;
+#else
+  // Measured using a dex2oat profile.
+  static const uptr NumBits = 8;
+  static const uptr MinSizeLog = 4;
+  static const uptr MidSizeLog = 8;
+  static const uptr MaxSizeLog = 16;
+  static const u32 MaxNumCachedHint = 14;
+  static const uptr MaxBytesCachedLog = 14;
+
+  static constexpr u32 Classes[] = {
+      0x00020, 0x00030, 0x00040, 0x00050, 0x00060, 0x00070, 0x00080, 0x00090,
+      0x000a0, 0x000b0, 0x000c0, 0x000d0, 0x000e0, 0x000f0, 0x00100, 0x00110,
+      0x00120, 0x00140, 0x00150, 0x00170, 0x00190, 0x001c0, 0x001f0, 0x00220,
+      0x00240, 0x00260, 0x002a0, 0x002e0, 0x00310, 0x00340, 0x00380, 0x003b0,
+      0x003e0, 0x00430, 0x00490, 0x00500, 0x00570, 0x005f0, 0x00680, 0x00720,
+      0x007d0, 0x00890, 0x00970, 0x00a50, 0x00b80, 0x00cb0, 0x00e30, 0x00fb0,
+      0x011b0, 0x01310, 0x01470, 0x01790, 0x01b50, 0x01fd0, 0x02310, 0x02690,
+      0x02b10, 0x02fd0, 0x03610, 0x03e10, 0x04890, 0x05710, 0x06a90, 0x10010,
+  };
+  static const uptr SizeDelta = 16;
+#endif
+};
+
+typedef TableSizeClassMap<AndroidSizeClassConfig> AndroidSizeClassMap;
+
+struct DefaultSizeClassConfig {
+  static const uptr NumBits = 3;
+  static const uptr MinSizeLog = 5;
+  static const uptr MidSizeLog = 8;
+  static const uptr MaxSizeLog = 17;
+  static const u32 MaxNumCachedHint = 8;
+  static const uptr MaxBytesCachedLog = 10;
+};
+
+typedef FixedSizeClassMap<DefaultSizeClassConfig> DefaultSizeClassMap;
+
+struct SvelteSizeClassConfig {
+#if SCUDO_WORDSIZE == 64U
+  static const uptr NumBits = 4;
+  static const uptr MinSizeLog = 4;
+  static const uptr MidSizeLog = 8;
+  static const uptr MaxSizeLog = 14;
+  static const u32 MaxNumCachedHint = 4;
+  static const uptr MaxBytesCachedLog = 10;
+#else
+  static const uptr NumBits = 4;
+  static const uptr MinSizeLog = 3;
+  static const uptr MidSizeLog = 7;
+  static const uptr MaxSizeLog = 14;
+  static const u32 MaxNumCachedHint = 5;
+  static const uptr MaxBytesCachedLog = 10;
+#endif
+};
+
+typedef FixedSizeClassMap<SvelteSizeClassConfig> SvelteSizeClassMap;
+
+template <typename SCMap> inline void printMap() {
+  for (uptr I = 0; I < SCMap::NumClasses; I++) {
+    if (I == SCMap::BatchClassId)
+    const uptr S = SCMap::getSizeByClassId(I);
+    const uptr Cached = SCMap::getMaxCachedHint(S) * S;
+        I, S, D, P, L, SCMap::getMaxCachedHint(S), Cached,
+        SCMap::getClassIdBySize(S));
 
-  static void validate() {
-    for (uptr C = 0; C < NumClasses; C++) {
-      if (C == BatchClassId)
-        continue;
-      const uptr S = getSizeByClassId(C);
-      CHECK_NE(S, 0U);
-      CHECK_EQ(getClassIdBySize(S), C);
-      if (C < LargestClassId)
-        CHECK_EQ(getClassIdBySize(S + 1), C + 1);
-      CHECK_EQ(getClassIdBySize(S - 1), C);
-      if (C - 1 != BatchClassId)
-        CHECK_GT(getSizeByClassId(C), getSizeByClassId(C - 1));
-    }
-    // Do not perform the loop if the maximum size is too large.
-    if (MaxSizeLog > 19)
-      return;
-    for (uptr S = 1; S <= MaxSize; S++) {
-      const uptr C = getClassIdBySize(S);
-      CHECK_LT(C, NumClasses);
-      CHECK_GE(getSizeByClassId(C), S);
-      if (C - 1 != BatchClassId)
-        CHECK_LT(getSizeByClassId(C - 1), S);
-    }
-  }
-};
-
-typedef SizeClassMap<3, 5, 8, 17, 8, 10> DefaultSizeClassMap;
-
-// TODO(kostyak): further tune class maps for Android & Fuchsia.
-#if SCUDO_WORDSIZE == 64U
-typedef SizeClassMap<4, 4, 8, 14, 4, 10> SvelteSizeClassMap;
-typedef SizeClassMap<2, 5, 9, 16, 14, 14> AndroidSizeClassMap;
-#else
-typedef SizeClassMap<4, 3, 7, 14, 5, 10> SvelteSizeClassMap;
-typedef SizeClassMap<3, 4, 9, 16, 14, 14> AndroidSizeClassMap;
-#endif
-
+template <typename SCMap> static void validateMap() {
+  for (uptr C = 0; C < SCMap::NumClasses; C++) {
+    if (C == SCMap::BatchClassId)
+    const uptr S = SCMap::getSizeByClassId(C);
+    CHECK_EQ(SCMap::getClassIdBySize(S), C);
+    if (C < SCMap::LargestClassId)
+      CHECK_EQ(SCMap::getClassIdBySize(S + 1), C + 1);
+    CHECK_EQ(SCMap::getClassIdBySize(S - 1), C);
+    if (C - 1 != SCMap::BatchClassId)
+      CHECK_GT(SCMap::getSizeByClassId(C), SCMap::getSizeByClassId(C - 1));
+  if (SCMap::MaxSize > (1 << 19))
+  for (uptr S = 1; S <= SCMap::MaxSize; S++) {
+    const uptr C = SCMap::getClassIdBySize(S);
+    CHECK_LT(C, SCMap::NumClasses);
+    CHECK_GE(SCMap::getSizeByClassId(C), S);
+    if (C - 1 != SCMap::BatchClassId)
+      CHECK_LT(SCMap::getSizeByClassId(C - 1), S);
 } // namespace scudo
 
 #endif // SCUDO_SIZE_CLASS_MAP_H_

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

while (Size > 1U) {
     for (scudo::uptr J = 0; J < scudo::Min(Size, DataSize); J++)
       EXPECT_EQ((reinterpret_cast<char *>(NewP))[J], Marker);
     P = NewP;
   }
   Allocator->deallocate(P, Origin);
 
   // Check that reallocating a chunk to a slightly smaller or larger size
   // returns the same chunk. This requires that all the sizes we iterate on use
-  // the same block size, but that should be the case for 2048 with our default
-  // class size maps.
-  P = Allocator->allocate(DataSize, Origin);
-  memset(P, Marker, DataSize);
+  // the same block size, but that should be the case for MaxSize - 64 with our
+  // default class size maps.
+  constexpr scudo::uptr ReallocSize = MaxSize - 64;
+  P = Allocator->allocate(ReallocSize, Origin);
+  memset(P, Marker, ReallocSize);
   for (scudo::sptr Delta = -32; Delta < 32; Delta += 8) {
-    const scudo::uptr NewSize = DataSize + Delta;
+    const scudo::uptr NewSize = ReallocSize + Delta;
     void *NewP = Allocator->reallocate(P, NewSize);
     EXPECT_EQ(NewP, P);
-    for (scudo::uptr I = 0; I < DataSize - 32; I++)
+    for (scudo::uptr I = 0; I < ReallocSize - 32; I++)
       EXPECT_EQ((reinterpret_cast<char *>(NewP))[I], Marker);
     checkMemoryTaggingMaybe(Allocator.get(), NewP, NewSize, 0);
   }
   Allocator->deallocate(P, Origin);
 
   // Allocates a bunch of chunks, then iterate over all the chunks, ensuring
   // they are the ones we allocated. This requires the allocator to not have any
   // other allocated chunk at this point (eg: won't work with the Quarantine).
#if SCUDO_FUCHSIA
   testAllocatorThreaded<scudo::FuchsiaConfig>();
 #else
   testAllocatorThreaded<scudo::DefaultConfig>();
   UseQuarantine = true;
   testAllocatorThreaded<scudo::AndroidConfig>();
 #endif
 }
 
+
+struct DeathSizeClassConfig {
+  static const scudo::uptr NumBits = 1;
+  static const scudo::uptr MinSizeLog = 10;
+  static const scudo::uptr MidSizeLog = 10;
+  static const scudo::uptr MaxSizeLog = 10;
+  static const scudo::u32 MaxNumCachedHint = 1;
+  static const scudo::uptr MaxBytesCachedLog = 10;
+};
+
 struct DeathConfig {
   // Tiny allocator, its Primary only serves chunks of 1024 bytes.
-  using DeathSizeClassMap = scudo::SizeClassMap<1U, 10U, 10U, 10U, 1U, 10U>;
+  using DeathSizeClassMap = scudo::FixedSizeClassMap<DeathSizeClassConfig>;
   typedef scudo::SizeClassAllocator64<DeathSizeClassMap, 20U> Primary;
   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) {

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

 //===-- size_class_map_test.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 "tests/scudo_unit_test.h"
 
 #include "size_class_map.h"
 
 template <class SizeClassMap> void testSizeClassMap() {
   typedef SizeClassMap SCMap;
-  SCMap::print();
-  SCMap::validate();
+  scudo::printMap<SCMap>();
+  scudo::validateMap<SCMap>();
 }
 
 TEST(ScudoSizeClassMapTest, DefaultSizeClassMap) {
   testSizeClassMap<scudo::DefaultSizeClassMap>();
 }
 
 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;
+};
+
 TEST(ScudoSizeClassMapTest, OneClassSizeClassMap) {
-  testSizeClassMap<scudo::SizeClassMap<1, 5, 5, 5, 0, 0>>();
+  testSizeClassMap<scudo::FixedSizeClassMap<OneClassSizeClassConfig>>();
 }
 
 #if SCUDO_CAN_USE_PRIMARY64
+struct LargeMaxSizeClassConfig {
+  static const scudo::uptr NumBits = 3;
+  static const scudo::uptr MinSizeLog = 4;
+  static const scudo::uptr MidSizeLog = 8;
+  static const scudo::uptr MaxSizeLog = 63;
+  static const scudo::u32 MaxNumCachedHint = 128;
+  static const scudo::uptr MaxBytesCachedLog = 16;
+};
+
 TEST(ScudoSizeClassMapTest, LargeMaxSizeClassMap) {
-  testSizeClassMap<scudo::SizeClassMap<3, 4, 8, 63, 128, 16>>();
+  testSizeClassMap<scudo::FixedSizeClassMap<LargeMaxSizeClassConfig>>();
 }
 #endif

compiler-rt/lib/scudo/standalone/tools/compute_size_class_config.cpp

+//===-- compute_size_class_config.cpp -------------------------------------===//
+//
+// 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 <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <algorithm>
+#include <vector>
+
+struct Alloc {
+  size_t size, count;
+};
+
+size_t measureWastage(const std::vector<Alloc> &allocs,
+                       const std::vector<size_t> &classes,
+                       size_t pageSize,
+                       size_t headerSize) {
+  size_t totalWastage = 0;
+  for (auto &a : allocs) {
+    size_t sizePlusHeader = a.size + headerSize;
+    size_t wastage = -1ull;
+    for (auto c : classes)
+      if (c >= sizePlusHeader && c - sizePlusHeader < wastage)
+        wastage = c - sizePlusHeader;
+    if (wastage == -1ull)
+      continue;
+    if (wastage > 2 * pageSize)
+      wastage = 2 * pageSize;
+    totalWastage += wastage * a.count;
+  }
+  return totalWastage;
+}
+
+void readAllocs(std::vector<Alloc> &allocs, const char *path) {
+  FILE *f = fopen(path, "r");
+  if (!f) {
+    fprintf(stderr, "compute_size_class_config: could not open %s: %s\n", path,
+            strerror(errno));
+    exit(1);
+  }
+
+  const char header[] = "<malloc version=\"scudo-1\">\n";
+  char buf[sizeof(header) - 1];
+  if (fread(buf, 1, sizeof(header) - 1, f) != sizeof(header) - 1 ||
+      memcmp(buf, header, sizeof(header) - 1) != 0) {
+    fprintf(stderr, "compute_size_class_config: invalid input format\n");
+    exit(1);
+  }
+
+  Alloc a;
+  while (fscanf(f, "<alloc size=\"%zu\" count=\"%zu\"/>\n", &a.size, &a.count) == 2)
+    allocs.push_back(a);
+  fclose(f);
+}
+
+size_t log2Floor(size_t x) { return sizeof(long) * 8 - 1 - __builtin_clzl(x); }
+
+void usage() {
+  fprintf(stderr,
+          "usage: compute_size_class_config [-p pageSize] [-c largestClass] "
+          "[-h headerSize] [-n numClasses] [-b numBits] profile...\n");
+  exit(1);
+}
+
+int main(int argc, char **argv) {
+  size_t pageSize = 4096;
+  size_t largestClass = 65552;
+  size_t headerSize = 16;
+  size_t numClasses = 32;
+  size_t numBits = 5;
+
+  std::vector<Alloc> allocs;
+  for (size_t i = 1; i != argc;) {
+    auto matchArg = [&](size_t &arg, const char *name) {
+      if (strcmp(argv[i], name) == 0) {
+        if (i + 1 != argc) {
+          arg = atoi(argv[i + 1]);
+          i += 2;
+        } else {
+          usage();
+        }
+        return true;
+      }
+      return false;
+    };
+    if (matchArg(pageSize, "-p") || matchArg(largestClass, "-c") ||
+        matchArg(headerSize, "-h") || matchArg(numClasses, "-n") ||
+        matchArg(numBits, "-b"))
+      continue;
+    readAllocs(allocs, argv[i]);
+    ++i;
+  }
+
+  if (allocs.empty())
+    usage();
+
+  std::vector<size_t> classes;
+  classes.push_back(largestClass);
+  for (size_t i = 1; i != numClasses; ++i) {
+    size_t minWastage = -1ull;
+    size_t minWastageClass;
+    for (size_t newClass = 16; newClass != largestClass; newClass += 16) {
+      // Skip classes with more than numBits bits, ignoring leading or trailing
+      // zero bits.
+      if (__builtin_ctzl(newClass - headerSize) +
+              __builtin_clzl(newClass - headerSize) <
+          sizeof(long) * 8 - numBits)
+        continue;
+
+      classes.push_back(newClass);
+      size_t newWastage = measureWastage(allocs, classes, pageSize, headerSize);
+      classes.pop_back();
+      if (newWastage < minWastage) {
+        minWastage = newWastage;
+        minWastageClass = newClass;
+      }
+    }
+    classes.push_back(minWastageClass);
+  }
+
+  std::sort(classes.begin(), classes.end());
+  size_t minSizeLog = log2Floor(headerSize);
+  size_t midSizeIndex = 0;
+  while (classes[midSizeIndex + 1] - classes[midSizeIndex] == (1 << minSizeLog))
+    midSizeIndex++;
+  size_t midSizeLog = log2Floor(classes[midSizeIndex] - headerSize);
+  size_t maxSizeLog = log2Floor(classes.back() - headerSize - 1) + 1;
+
+  printf(R"(// wastage = %zu
+
+struct MySizeClassConfig {
+  static const uptr NumBits = %zu;
+  static const uptr MinSizeLog = %zu;
+  static const uptr MidSizeLog = %zu;
+  static const uptr MaxSizeLog = %zu;
+  static const u32 MaxNumCachedHint = 14;
+  static const uptr MaxBytesCachedLog = 14;
+
+  static constexpr u32 Classes[] = {)",
+         measureWastage(allocs, classes, pageSize, headerSize), numBits,
+         minSizeLog, midSizeLog, maxSizeLog);
+  for (size_t i = 0; i != classes.size(); ++i) {
+    if ((i % 8) == 0)
+      printf("\n      ");
+    else
+      printf(" ");
+    printf("0x%05zx,", classes[i]);
+  }
+  printf(R"(
+  };
+  static const uptr SizeDelta = %zu;
+};
+)", headerSize);
+}