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