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

   1 //===-- size_class_map.h ----------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef SCUDO_SIZE_CLASS_MAP_H_
  10 #define SCUDO_SIZE_CLASS_MAP_H_
  11
  12 #include "chunk.h"
  13 #include "common.h"
  14 #include "string_utils.h"
  15
  16 namespace scudo {
  17
  18 inline uptr scaledLog2(uptr Size, uptr ZeroLog, uptr LogBits) {
  19   const uptr L = getMostSignificantSetBitIndex(Size);
  20   const uptr LBits = (Size >> (L - LogBits)) - (1 << LogBits);
  21   const uptr HBits = (L - ZeroLog) << LogBits;
  22   return LBits + HBits;
  23 }
  24
  25 template <typename Config> struct SizeClassMapBase {
  26   static u16 getMaxCachedHint(uptr Size) {
  27     DCHECK_NE(Size, 0);
  28     u32 N;
  29     // Force a 32-bit division if the template parameters allow for it.
  30     if (Config::MaxBytesCachedLog > 31 || Config::MaxSizeLog > 31)
  31       N = static_cast<u32>((1UL << Config::MaxBytesCachedLog) / Size);
  32     else
  33       N = (1U << Config::MaxBytesCachedLog) / static_cast<u32>(Size);
  34
  35     // Note that Config::MaxNumCachedHint is u16 so the result is guaranteed to
  36     // fit in u16.
  37     return static_cast<u16>(Max(1U, Min<u32>(Config::MaxNumCachedHint, N)));
  38   }
  39 };
  40
  41 // SizeClassMap maps allocation sizes into size classes and back, in an
  42 // efficient table-free manner.
  43 //
  44 // Class 0 is a special class that doesn't abide by the same rules as other
  45 // classes. The allocator uses it to hold batches.
  46 //
  47 // The other sizes are controlled by the template parameters:
  48 // - MinSizeLog: defines the first class as 2^MinSizeLog bytes.
  49 // - MaxSizeLog: defines the last class as 2^MaxSizeLog bytes.
  50 // - MidSizeLog: classes increase with step 2^MinSizeLog from 2^MinSizeLog to
  51 //               2^MidSizeLog bytes.
  52 // - NumBits: the number of non-zero bits in sizes after 2^MidSizeLog.
  53 //            eg. with NumBits==3 all size classes after 2^MidSizeLog look like
  54 //            0b1xx0..0 (where x is either 0 or 1).
  55 //
  56 // This class also gives a hint to a thread-caching allocator about the amount
  57 // of chunks that can be cached per-thread:
  58 // - MaxNumCachedHint is a hint for the max number of chunks cached per class.
  59 // - 2^MaxBytesCachedLog is the max number of bytes cached per class.
  60 template <typename Config>
  61 class FixedSizeClassMap : public SizeClassMapBase<Config> {
  62   typedef SizeClassMapBase<Config> Base;
  63
  64   static const uptr MinSize = 1UL << Config::MinSizeLog;
  65   static const uptr MidSize = 1UL << Config::MidSizeLog;
  66   static const uptr MidClass = MidSize / MinSize;
  67   static const u8 S = Config::NumBits - 1;
  68   static const uptr M = (1UL << S) - 1;
  69
  70 public:
  71   static const u16 MaxNumCachedHint = Config::MaxNumCachedHint;
  72
  73   static const uptr MaxSize = (1UL << Config::MaxSizeLog) + Config::SizeDelta;
  74   static const uptr NumClasses =
  75       MidClass + ((Config::MaxSizeLog - Config::MidSizeLog) << S) + 1;
  76   static_assert(NumClasses <= 256, "");
  77   static const uptr LargestClassId = NumClasses - 1;
  78   static const uptr BatchClassId = 0;
  79
  80   static uptr getSizeByClassId(uptr ClassId) {
  81     DCHECK_NE(ClassId, BatchClassId);
  82     if (ClassId <= MidClass)
  83       return (ClassId << Config::MinSizeLog) + Config::SizeDelta;
  84     ClassId -= MidClass;
  85     const uptr T = MidSize << (ClassId >> S);
  86     return T + (T >> S) * (ClassId & M) + Config::SizeDelta;
  87   }
  88
  89   static u8 getSizeLSBByClassId(uptr ClassId) {
  90     return u8(getLeastSignificantSetBitIndex(getSizeByClassId(ClassId)));
  91   }
  92
  93   static constexpr bool usesCompressedLSBFormat() { return false; }
  94
  95   static uptr getClassIdBySize(uptr Size) {
  96     if (Size <= Config::SizeDelta + (1 << Config::MinSizeLog))
  97       return 1;
  98     Size -= Config::SizeDelta;
  99     DCHECK_LE(Size, MaxSize);
 100     if (Size <= MidSize)
 101       return (Size + MinSize - 1) >> Config::MinSizeLog;
 102     return MidClass + 1 + scaledLog2(Size - 1, Config::MidSizeLog, S);
 103   }
 104
 105   static u16 getMaxCachedHint(uptr Size) {
 106     DCHECK_LE(Size, MaxSize);
 107     return Base::getMaxCachedHint(Size);
 108   }
 109 };
 110
 111 template <typename Config>
 112 class TableSizeClassMap : public SizeClassMapBase<Config> {
 113   typedef SizeClassMapBase<Config> Base;
 114
 115   static const u8 S = Config::NumBits - 1;
 116   static const uptr M = (1UL << S) - 1;
 117   static const uptr ClassesSize =
 118       sizeof(Config::Classes) / sizeof(Config::Classes[0]);
 119
 120   struct SizeTable {
 121     constexpr SizeTable() {
 122       uptr Pos = 1 << Config::MidSizeLog;
 123       uptr Inc = 1 << (Config::MidSizeLog - S);
 124       for (uptr i = 0; i != getTableSize(); ++i) {
 125         Pos += Inc;
 126         if ((Pos & (Pos - 1)) == 0)
 127           Inc *= 2;
 128         Tab[i] = computeClassId(Pos + Config::SizeDelta);
 129       }
 130     }
 131
 132     constexpr static u8 computeClassId(uptr Size) {
 133       for (uptr i = 0; i != ClassesSize; ++i) {
 134         if (Size <= Config::Classes[i])
 135           return static_cast<u8>(i + 1);
 136       }
 137       return static_cast<u8>(-1);
 138     }
 139
 140     constexpr static uptr getTableSize() {
 141       return (Config::MaxSizeLog - Config::MidSizeLog) << S;
 142     }
 143
 144     u8 Tab[getTableSize()] = {};
 145   };
 146
 147   static constexpr SizeTable SzTable = {};
 148
 149   struct LSBTable {
 150     constexpr LSBTable() {
 151       u8 Min = 255, Max = 0;
 152       for (uptr I = 0; I != ClassesSize; ++I) {
 153         for (u8 Bit = 0; Bit != 64; ++Bit) {
 154           if (Config::Classes[I] & (1 << Bit)) {
 155             Tab[I] = Bit;
 156             if (Bit < Min)
 157               Min = Bit;
 158             if (Bit > Max)
 159               Max = Bit;
 160             break;
 161           }
 162         }
 163       }
 164
 165       if (Max - Min > 3 || ClassesSize > 32)
 166         return;
 167
 168       UseCompressedFormat = true;
 169       CompressedMin = Min;
 170       for (uptr I = 0; I != ClassesSize; ++I)
 171         CompressedValue |= u64(Tab[I] - Min) << (I * 2);
 172     }
 173
 174     u8 Tab[ClassesSize] = {};
 175
 176     bool UseCompressedFormat = false;
 177     u8 CompressedMin = 0;
 178     u64 CompressedValue = 0;
 179   };
 180
 181   static constexpr LSBTable LTable = {};
 182
 183 public:
 184   static const u16 MaxNumCachedHint = Config::MaxNumCachedHint;
 185
 186   static const uptr NumClasses = ClassesSize + 1;
 187   static_assert(NumClasses < 256, "");
 188   static const uptr LargestClassId = NumClasses - 1;
 189   static const uptr BatchClassId = 0;
 190   static const uptr MaxSize = Config::Classes[LargestClassId - 1];
 191
 192   static uptr getSizeByClassId(uptr ClassId) {
 193     return Config::Classes[ClassId - 1];
 194   }
 195
 196   static u8 getSizeLSBByClassId(uptr ClassId) {
 197     if (LTable.UseCompressedFormat)
 198       return ((LTable.CompressedValue >> ((ClassId - 1) * 2)) & 3) +
 199              LTable.CompressedMin;
 200     else
 201       return LTable.Tab[ClassId - 1];
 202   }
 203
 204   static constexpr bool usesCompressedLSBFormat() {
 205     return LTable.UseCompressedFormat;
 206   }
 207
 208   static uptr getClassIdBySize(uptr Size) {
 209     if (Size <= Config::Classes[0])
 210       return 1;
 211     Size -= Config::SizeDelta;
 212     DCHECK_LE(Size, MaxSize);
 213     if (Size <= (1 << Config::MidSizeLog))
 214       return ((Size - 1) >> Config::MinSizeLog) + 1;
 215     return SzTable.Tab[scaledLog2(Size - 1, Config::MidSizeLog, S)];
 216   }
 217
 218   static u16 getMaxCachedHint(uptr Size) {
 219     DCHECK_LE(Size, MaxSize);
 220     return Base::getMaxCachedHint(Size);
 221   }
 222 };
 223
 224 struct DefaultSizeClassConfig {
 225   static const uptr NumBits = 3;
 226   static const uptr MinSizeLog = 5;
 227   static const uptr MidSizeLog = 8;
 228   static const uptr MaxSizeLog = 17;
 229   static const u16 MaxNumCachedHint = 14;
 230   static const uptr MaxBytesCachedLog = 10;
 231   static const uptr SizeDelta = 0;
 232 };
 233
 234 typedef FixedSizeClassMap<DefaultSizeClassConfig> DefaultSizeClassMap;
 235
 236 struct FuchsiaSizeClassConfig {
 237   static const uptr NumBits = 3;
 238   static const uptr MinSizeLog = 5;
 239   static const uptr MidSizeLog = 8;
 240   static const uptr MaxSizeLog = 17;
 241   static const u16 MaxNumCachedHint = 12;
 242   static const uptr MaxBytesCachedLog = 10;
 243   static const uptr SizeDelta = Chunk::getHeaderSize();
 244 };
 245
 246 typedef FixedSizeClassMap<FuchsiaSizeClassConfig> FuchsiaSizeClassMap;
 247
 248 struct AndroidSizeClassConfig {
 249 #if SCUDO_WORDSIZE == 64U
 250   static const uptr NumBits = 7;
 251   static const uptr MinSizeLog = 4;
 252   static const uptr MidSizeLog = 6;
 253   static const uptr MaxSizeLog = 16;
 254   static const u16 MaxNumCachedHint = 13;
 255   static const uptr MaxBytesCachedLog = 13;
 256
 257   static constexpr uptr Classes[] = {
 258       0x00020, 0x00030, 0x00040, 0x00050, 0x00060, 0x00070, 0x00090, 0x000b0,
 259       0x000c0, 0x000e0, 0x00120, 0x00160, 0x001c0, 0x00250, 0x00320, 0x00450,
 260       0x00670, 0x00830, 0x00a10, 0x00c30, 0x01010, 0x01210, 0x01bd0, 0x02210,
 261       0x02d90, 0x03790, 0x04010, 0x04810, 0x05a10, 0x07310, 0x08210, 0x10010,
 262   };
 263   static const uptr SizeDelta = 16;
 264 #else
 265   static const uptr NumBits = 8;
 266   static const uptr MinSizeLog = 4;
 267   static const uptr MidSizeLog = 7;
 268   static const uptr MaxSizeLog = 16;
 269   static const u16 MaxNumCachedHint = 14;
 270   static const uptr MaxBytesCachedLog = 13;
 271
 272   static constexpr uptr Classes[] = {
 273       0x00020, 0x00030, 0x00040, 0x00050, 0x00060, 0x00070, 0x00080, 0x00090,
 274       0x000a0, 0x000b0, 0x000c0, 0x000e0, 0x000f0, 0x00110, 0x00120, 0x00130,
 275       0x00150, 0x00160, 0x00170, 0x00190, 0x001d0, 0x00210, 0x00240, 0x002a0,
 276       0x00330, 0x00370, 0x003a0, 0x00400, 0x00430, 0x004a0, 0x00530, 0x00610,
 277       0x00730, 0x00840, 0x00910, 0x009c0, 0x00a60, 0x00b10, 0x00ca0, 0x00e00,
 278       0x00fb0, 0x01030, 0x01130, 0x011f0, 0x01490, 0x01650, 0x01930, 0x02010,
 279       0x02190, 0x02490, 0x02850, 0x02d50, 0x03010, 0x03210, 0x03c90, 0x04090,
 280       0x04510, 0x04810, 0x05c10, 0x06f10, 0x07310, 0x08010, 0x0c010, 0x10010,
 281   };
 282   static const uptr SizeDelta = 16;
 283 #endif
 284 };
 285
 286 typedef TableSizeClassMap<AndroidSizeClassConfig> AndroidSizeClassMap;
 287
 288 #if SCUDO_WORDSIZE == 64U && defined(__clang__)
 289 static_assert(AndroidSizeClassMap::usesCompressedLSBFormat(), "");
 290 #endif
 291
 292 struct TrustySizeClassConfig {
 293   static const uptr NumBits = 1;
 294   static const uptr MinSizeLog = 5;
 295   static const uptr MidSizeLog = 5;
 296   static const uptr MaxSizeLog = 15;
 297   static const u16 MaxNumCachedHint = 12;
 298   static const uptr MaxBytesCachedLog = 10;
 299   static const uptr SizeDelta = 0;
 300 };
 301
 302 typedef FixedSizeClassMap<TrustySizeClassConfig> TrustySizeClassMap;
 303
 304 template <typename SCMap> inline void printMap() {
 305   ScopedString Buffer;
 306   uptr PrevS = 0;
 307   uptr TotalCached = 0;
 308   for (uptr I = 0; I < SCMap::NumClasses; I++) {
 309     if (I == SCMap::BatchClassId)
 310       continue;
 311     const uptr S = SCMap::getSizeByClassId(I);
 312     const uptr D = S - PrevS;
 313     const uptr P = PrevS ? (D * 100 / PrevS) : 0;
 314     const uptr L = S ? getMostSignificantSetBitIndex(S) : 0;
 315     const uptr Cached = SCMap::getMaxCachedHint(S) * S;
 316     Buffer.append(
 317         "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %u %zu; id %zu\n", I,
 318         S, D, P, L, SCMap::getMaxCachedHint(S), Cached,
 319         SCMap::getClassIdBySize(S));
 320     TotalCached += Cached;
 321     PrevS = S;
 322   }
 323   Buffer.append("Total Cached: %zu\n", TotalCached);
 324   Buffer.output();
 325 }
 326
 327 template <typename SCMap> static UNUSED void validateMap() {
 328   for (uptr C = 0; C < SCMap::NumClasses; C++) {
 329     if (C == SCMap::BatchClassId)
 330       continue;
 331     const uptr S = SCMap::getSizeByClassId(C);
 332     CHECK_NE(S, 0U);
 333     CHECK_EQ(SCMap::getClassIdBySize(S), C);
 334     if (C < SCMap::LargestClassId)
 335       CHECK_EQ(SCMap::getClassIdBySize(S + 1), C + 1);
 336     CHECK_EQ(SCMap::getClassIdBySize(S - 1), C);
 337     if (C - 1 != SCMap::BatchClassId)
 338       CHECK_GT(SCMap::getSizeByClassId(C), SCMap::getSizeByClassId(C - 1));
 339   }
 340   // Do not perform the loop if the maximum size is too large.
 341   if (SCMap::MaxSize > (1 << 19))
 342     return;
 343   for (uptr S = 1; S <= SCMap::MaxSize; S++) {
 344     const uptr C = SCMap::getClassIdBySize(S);
 345     CHECK_LT(C, SCMap::NumClasses);
 346     CHECK_GE(SCMap::getSizeByClassId(C), S);
 347     if (C - 1 != SCMap::BatchClassId)
 348       CHECK_LT(SCMap::getSizeByClassId(C - 1), S);
 349   }
 350 }
 351 } // namespace scudo
 352
 353 #endif // SCUDO_SIZE_CLASS_MAP_H_