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_ 354