contrib/compiler-rt/lib/sanitizer_common/sanitizer_allocator_size_class_map.h

   1 //===-- sanitizer_allocator_size_class_map.h --------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Part of the Sanitizer Allocator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #ifndef SANITIZER_ALLOCATOR_H
  14 #error This file must be included inside sanitizer_allocator.h
  15 #endif
  16
  17 // SizeClassMap maps allocation sizes into size classes and back.
  18 // Class 0 always corresponds to size 0.
  19 // The other sizes are controlled by the template parameters:
  20 //   kMinSizeLog: defines the class 1    as 2^kMinSizeLog.
  21 //   kMaxSizeLog: defines the last class as 2^kMaxSizeLog.
  22 //   kMidSizeLog: the classes starting from 1 increase with step
  23 //                2^kMinSizeLog until 2^kMidSizeLog.
  24 //   kNumBits: the number of non-zero bits in sizes after 2^kMidSizeLog.
  25 //             E.g. with kNumBits==3 all size classes after 2^kMidSizeLog
  26 //             look like 0b1xx0..0, where x is either 0 or 1.
  27 //
  28 // Example: kNumBits=3, kMidSizeLog=4, kMidSizeLog=8, kMaxSizeLog=17:
  29 //
  30 // Classes 1 - 16 correspond to sizes 16 to 256 (size = class_id * 16).
  31 // Next 4 classes: 256 + i * 64  (i = 1 to 4).
  32 // Next 4 classes: 512 + i * 128 (i = 1 to 4).
  33 // ...
  34 // Next 4 classes: 2^k + i * 2^(k-2) (i = 1 to 4).
  35 // Last class corresponds to kMaxSize = 1 << kMaxSizeLog.
  36 //
  37 // This structure of the size class map gives us:
  38 //   - Efficient table-free class-to-size and size-to-class functions.
  39 //   - Difference between two consequent size classes is between 14% and 25%
  40 //
  41 // This class also gives a hint to a thread-caching allocator about the amount
  42 // of chunks that need to be cached per-thread:
  43 //  - kMaxNumCachedHint is a hint for maximal number of chunks per size class.
  44 //    The actual number is computed in TransferBatch.
  45 //  - (1 << kMaxBytesCachedLog) is the maximal number of bytes per size class.
  46 //
  47 // Part of output of SizeClassMap::Print():
  48 // c00 => s: 0 diff: +0 00% l 0 cached: 0 0; id 0
  49 // c01 => s: 16 diff: +16 00% l 4 cached: 256 4096; id 1
  50 // c02 => s: 32 diff: +16 100% l 5 cached: 256 8192; id 2
  51 // c03 => s: 48 diff: +16 50% l 5 cached: 256 12288; id 3
  52 // c04 => s: 64 diff: +16 33% l 6 cached: 256 16384; id 4
  53 // c05 => s: 80 diff: +16 25% l 6 cached: 256 20480; id 5
  54 // c06 => s: 96 diff: +16 20% l 6 cached: 256 24576; id 6
  55 // c07 => s: 112 diff: +16 16% l 6 cached: 256 28672; id 7
  56 //
  57 // c08 => s: 128 diff: +16 14% l 7 cached: 256 32768; id 8
  58 // c09 => s: 144 diff: +16 12% l 7 cached: 256 36864; id 9
  59 // c10 => s: 160 diff: +16 11% l 7 cached: 256 40960; id 10
  60 // c11 => s: 176 diff: +16 10% l 7 cached: 256 45056; id 11
  61 // c12 => s: 192 diff: +16 09% l 7 cached: 256 49152; id 12
  62 // c13 => s: 208 diff: +16 08% l 7 cached: 256 53248; id 13
  63 // c14 => s: 224 diff: +16 07% l 7 cached: 256 57344; id 14
  64 // c15 => s: 240 diff: +16 07% l 7 cached: 256 61440; id 15
  65 //
  66 // c16 => s: 256 diff: +16 06% l 8 cached: 256 65536; id 16
  67 // c17 => s: 320 diff: +64 25% l 8 cached: 204 65280; id 17
  68 // c18 => s: 384 diff: +64 20% l 8 cached: 170 65280; id 18
  69 // c19 => s: 448 diff: +64 16% l 8 cached: 146 65408; id 19
  70 //
  71 // c20 => s: 512 diff: +64 14% l 9 cached: 128 65536; id 20
  72 // c21 => s: 640 diff: +128 25% l 9 cached: 102 65280; id 21
  73 // c22 => s: 768 diff: +128 20% l 9 cached: 85 65280; id 22
  74 // c23 => s: 896 diff: +128 16% l 9 cached: 73 65408; id 23
  75 //
  76 // c24 => s: 1024 diff: +128 14% l 10 cached: 64 65536; id 24
  77 // c25 => s: 1280 diff: +256 25% l 10 cached: 51 65280; id 25
  78 // c26 => s: 1536 diff: +256 20% l 10 cached: 42 64512; id 26
  79 // c27 => s: 1792 diff: +256 16% l 10 cached: 36 64512; id 27
  80 //
  81 // ...
  82 //
  83 // c48 => s: 65536 diff: +8192 14% l 16 cached: 1 65536; id 48
  84 // c49 => s: 81920 diff: +16384 25% l 16 cached: 1 81920; id 49
  85 // c50 => s: 98304 diff: +16384 20% l 16 cached: 1 98304; id 50
  86 // c51 => s: 114688 diff: +16384 16% l 16 cached: 1 114688; id 51
  87 //
  88 // c52 => s: 131072 diff: +16384 14% l 17 cached: 1 131072; id 52
  89 //
  90 //
  91 // Another example (kNumBits=2):
  92 // c00 => s: 0 diff: +0 00% l 0 cached: 0 0; id 0
  93 // c01 => s: 32 diff: +32 00% l 5 cached: 64 2048; id 1
  94 // c02 => s: 64 diff: +32 100% l 6 cached: 64 4096; id 2
  95 // c03 => s: 96 diff: +32 50% l 6 cached: 64 6144; id 3
  96 // c04 => s: 128 diff: +32 33% l 7 cached: 64 8192; id 4
  97 // c05 => s: 160 diff: +32 25% l 7 cached: 64 10240; id 5
  98 // c06 => s: 192 diff: +32 20% l 7 cached: 64 12288; id 6
  99 // c07 => s: 224 diff: +32 16% l 7 cached: 64 14336; id 7
 100 // c08 => s: 256 diff: +32 14% l 8 cached: 64 16384; id 8
 101 // c09 => s: 384 diff: +128 50% l 8 cached: 42 16128; id 9
 102 // c10 => s: 512 diff: +128 33% l 9 cached: 32 16384; id 10
 103 // c11 => s: 768 diff: +256 50% l 9 cached: 21 16128; id 11
 104 // c12 => s: 1024 diff: +256 33% l 10 cached: 16 16384; id 12
 105 // c13 => s: 1536 diff: +512 50% l 10 cached: 10 15360; id 13
 106 // c14 => s: 2048 diff: +512 33% l 11 cached: 8 16384; id 14
 107 // c15 => s: 3072 diff: +1024 50% l 11 cached: 5 15360; id 15
 108 // c16 => s: 4096 diff: +1024 33% l 12 cached: 4 16384; id 16
 109 // c17 => s: 6144 diff: +2048 50% l 12 cached: 2 12288; id 17
 110 // c18 => s: 8192 diff: +2048 33% l 13 cached: 2 16384; id 18
 111 // c19 => s: 12288 diff: +4096 50% l 13 cached: 1 12288; id 19
 112 // c20 => s: 16384 diff: +4096 33% l 14 cached: 1 16384; id 20
 113 // c21 => s: 24576 diff: +8192 50% l 14 cached: 1 24576; id 21
 114 // c22 => s: 32768 diff: +8192 33% l 15 cached: 1 32768; id 22
 115 // c23 => s: 49152 diff: +16384 50% l 15 cached: 1 49152; id 23
 116 // c24 => s: 65536 diff: +16384 33% l 16 cached: 1 65536; id 24
 117 // c25 => s: 98304 diff: +32768 50% l 16 cached: 1 98304; id 25
 118 // c26 => s: 131072 diff: +32768 33% l 17 cached: 1 131072; id 26
 119
 120 template <uptr kNumBits, uptr kMinSizeLog, uptr kMidSizeLog, uptr kMaxSizeLog,
 121           uptr kMaxNumCachedHintT, uptr kMaxBytesCachedLog>
 122 class SizeClassMap {
 123   static const uptr kMinSize = 1 << kMinSizeLog;
 124   static const uptr kMidSize = 1 << kMidSizeLog;
 125   static const uptr kMidClass = kMidSize / kMinSize;
 126   static const uptr S = kNumBits - 1;
 127   static const uptr M = (1 << S) - 1;
 128
 129  public:
 130   // kMaxNumCachedHintT is a power of two. It serves as a hint
 131   // for the size of TransferBatch, the actual size could be a bit smaller.
 132   static const uptr kMaxNumCachedHint = kMaxNumCachedHintT;
 133   COMPILER_CHECK((kMaxNumCachedHint & (kMaxNumCachedHint - 1)) == 0);
 134
 135   static const uptr kMaxSize = 1UL << kMaxSizeLog;
 136   static const uptr kNumClasses =
 137       kMidClass + ((kMaxSizeLog - kMidSizeLog) << S) + 1 + 1;
 138   static const uptr kLargestClassID = kNumClasses - 2;
 139   static const uptr kBatchClassID = kNumClasses - 1;
 140   COMPILER_CHECK(kNumClasses >= 16 && kNumClasses <= 256);
 141   static const uptr kNumClassesRounded =
 142       kNumClasses <= 32  ? 32 :
 143       kNumClasses <= 64  ? 64 :
 144       kNumClasses <= 128 ? 128 : 256;
 145
 146   static uptr Size(uptr class_id) {
 147     // Estimate the result for kBatchClassID because this class does not know
 148     // the exact size of TransferBatch. It's OK since we are using the actual
 149     // sizeof(TransferBatch) where it matters.
 150     if (UNLIKELY(class_id == kBatchClassID))
 151       return kMaxNumCachedHint * sizeof(uptr);
 152     if (class_id <= kMidClass)
 153       return kMinSize * class_id;
 154     class_id -= kMidClass;
 155     uptr t = kMidSize << (class_id >> S);
 156     return t + (t >> S) * (class_id & M);
 157   }
 158
 159   static uptr ClassID(uptr size) {
 160     if (UNLIKELY(size > kMaxSize))
 161       return 0;
 162     if (size <= kMidSize)
 163       return (size + kMinSize - 1) >> kMinSizeLog;
 164     const uptr l = MostSignificantSetBitIndex(size);
 165     const uptr hbits = (size >> (l - S)) & M;
 166     const uptr lbits = size & ((1U << (l - S)) - 1);
 167     const uptr l1 = l - kMidSizeLog;
 168     return kMidClass + (l1 << S) + hbits + (lbits > 0);
 169   }
 170
 171   static uptr MaxCachedHint(uptr size) {
 172     DCHECK_LE(size, kMaxSize);
 173     if (UNLIKELY(size == 0))
 174       return 0;
 175     uptr n;
 176     // Force a 32-bit division if the template parameters allow for it.
 177     if (kMaxBytesCachedLog > 31 || kMaxSizeLog > 31)
 178       n = (1UL << kMaxBytesCachedLog) / size;
 179     else
 180       n = (1U << kMaxBytesCachedLog) / static_cast<u32>(size);
 181     return Max<uptr>(1U, Min(kMaxNumCachedHint, n));
 182   }
 183
 184   static void Print() {
 185     uptr prev_s = 0;
 186     uptr total_cached = 0;
 187     for (uptr i = 0; i < kNumClasses; i++) {
 188       uptr s = Size(i);
 189       if (s >= kMidSize / 2 && (s & (s - 1)) == 0)
 190         Printf("\n");
 191       uptr d = s - prev_s;
 192       uptr p = prev_s ? (d * 100 / prev_s) : 0;
 193       uptr l = s ? MostSignificantSetBitIndex(s) : 0;
 194       uptr cached = MaxCachedHint(s) * s;
 195       if (i == kBatchClassID)
 196         d = p = l = 0;
 197       Printf("c%02zd => s: %zd diff: +%zd %02zd%% l %zd "
 198              "cached: %zd %zd; id %zd\n",
 199              i, Size(i), d, p, l, MaxCachedHint(s), cached, ClassID(s));
 200       total_cached += cached;
 201       prev_s = s;
 202     }
 203     Printf("Total cached: %zd\n", total_cached);
 204   }
 205
 206   static void Validate() {
 207     for (uptr c = 1; c < kNumClasses; c++) {
 208       // Printf("Validate: c%zd\n", c);
 209       uptr s = Size(c);
 210       CHECK_NE(s, 0U);
 211       if (c == kBatchClassID)
 212         continue;
 213       CHECK_EQ(ClassID(s), c);
 214       if (c < kLargestClassID)
 215         CHECK_EQ(ClassID(s + 1), c + 1);
 216       CHECK_EQ(ClassID(s - 1), c);
 217       CHECK_GT(Size(c), Size(c - 1));
 218     }
 219     CHECK_EQ(ClassID(kMaxSize + 1), 0);
 220
 221     for (uptr s = 1; s <= kMaxSize; s++) {
 222       uptr c = ClassID(s);
 223       // Printf("s%zd => c%zd\n", s, c);
 224       CHECK_LT(c, kNumClasses);
 225       CHECK_GE(Size(c), s);
 226       if (c > 0)
 227         CHECK_LT(Size(c - 1), s);
 228     }
 229   }
 230 };
 231
 232 typedef SizeClassMap<3, 4, 8, 17, 128, 16> DefaultSizeClassMap;
 233 typedef SizeClassMap<3, 4, 8, 17, 64, 14> CompactSizeClassMap;
 234 typedef SizeClassMap<2, 5, 9, 16, 64, 14> VeryCompactSizeClassMap;