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