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 16namespace scudo { 17 18inline 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 25template <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. 57template <typename Config> 58class 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 static const uptr SizeDelta = Chunk::getHeaderSize(); 68 69public: 70 static const u32 MaxNumCachedHint = Config::MaxNumCachedHint; 71 72 static const uptr MaxSize = (1UL << Config::MaxSizeLog) + SizeDelta; 73 static const uptr NumClasses = 74 MidClass + ((Config::MaxSizeLog - Config::MidSizeLog) << S) + 1; 75 static_assert(NumClasses <= 256, ""); 76 static const uptr LargestClassId = NumClasses - 1; 77 static const uptr BatchClassId = 0; 78 79 static uptr getSizeByClassId(uptr ClassId) { 80 DCHECK_NE(ClassId, BatchClassId); 81 if (ClassId <= MidClass) 82 return (ClassId << Config::MinSizeLog) + SizeDelta; 83 ClassId -= MidClass; 84 const uptr T = MidSize << (ClassId >> S); 85 return T + (T >> S) * (ClassId & M) + SizeDelta; 86 } 87 88 static uptr getClassIdBySize(uptr Size) { 89 if (Size <= SizeDelta + (1 << Config::MinSizeLog)) 90 return 1; 91 Size -= SizeDelta; 92 DCHECK_LE(Size, MaxSize); 93 if (Size <= MidSize) 94 return (Size + MinSize - 1) >> Config::MinSizeLog; 95 return MidClass + 1 + scaledLog2(Size - 1, Config::MidSizeLog, S); 96 } 97 98 static u32 getMaxCachedHint(uptr Size) { 99 DCHECK_LE(Size, MaxSize); 100 return Base::getMaxCachedHint(Size); 101 } 102}; 103 104template <typename Config> 105class TableSizeClassMap : public SizeClassMapBase<Config> { 106 typedef SizeClassMapBase<Config> Base; 107 108 static const u8 S = Config::NumBits - 1; 109 static const uptr M = (1UL << S) - 1; 110 static const uptr ClassesSize = 111 sizeof(Config::Classes) / sizeof(Config::Classes[0]); 112 113 struct SizeTable { 114 constexpr SizeTable() { 115 uptr Pos = 1 << Config::MidSizeLog; 116 uptr Inc = 1 << (Config::MidSizeLog - S); 117 for (uptr i = 0; i != getTableSize(); ++i) { 118 Pos += Inc; 119 if ((Pos & (Pos - 1)) == 0) 120 Inc *= 2; 121 Tab[i] = computeClassId(Pos + Config::SizeDelta); 122 } 123 } 124 125 constexpr static u8 computeClassId(uptr Size) { 126 for (uptr i = 0; i != ClassesSize; ++i) { 127 if (Size <= Config::Classes[i]) 128 return static_cast<u8>(i + 1); 129 } 130 return static_cast<u8>(-1); 131 } 132 133 constexpr static uptr getTableSize() { 134 return (Config::MaxSizeLog - Config::MidSizeLog) << S; 135 } 136 137 u8 Tab[getTableSize()] = {}; 138 }; 139 140 static constexpr SizeTable Table = {}; 141 142public: 143 static const u32 MaxNumCachedHint = Config::MaxNumCachedHint; 144 145 static const uptr NumClasses = ClassesSize + 1; 146 static_assert(NumClasses < 256, ""); 147 static const uptr LargestClassId = NumClasses - 1; 148 static const uptr BatchClassId = 0; 149 static const uptr MaxSize = Config::Classes[LargestClassId - 1]; 150 151 static uptr getSizeByClassId(uptr ClassId) { 152 return Config::Classes[ClassId - 1]; 153 } 154 155 static uptr getClassIdBySize(uptr Size) { 156 if (Size <= Config::Classes[0]) 157 return 1; 158 Size -= Config::SizeDelta; 159 DCHECK_LE(Size, MaxSize); 160 if (Size <= (1 << Config::MidSizeLog)) 161 return ((Size - 1) >> Config::MinSizeLog) + 1; 162 return Table.Tab[scaledLog2(Size - 1, Config::MidSizeLog, S)]; 163 } 164 165 static u32 getMaxCachedHint(uptr Size) { 166 DCHECK_LE(Size, MaxSize); 167 return Base::getMaxCachedHint(Size); 168 } 169}; 170 171struct AndroidSizeClassConfig { 172#if SCUDO_WORDSIZE == 64U 173 static const uptr NumBits = 7; 174 static const uptr MinSizeLog = 4; 175 static const uptr MidSizeLog = 6; 176 static const uptr MaxSizeLog = 16; 177 static const u32 MaxNumCachedHint = 14; 178 static const uptr MaxBytesCachedLog = 13; 179 180 static constexpr u32 Classes[] = { 181 0x00020, 0x00030, 0x00040, 0x00050, 0x00060, 0x00070, 0x00090, 0x000b0, 182 0x000c0, 0x000e0, 0x00120, 0x00160, 0x001c0, 0x00250, 0x00320, 0x00450, 183 0x00670, 0x00830, 0x00a10, 0x00c30, 0x01010, 0x01210, 0x01bd0, 0x02210, 184 0x02d90, 0x03790, 0x04010, 0x04810, 0x05a10, 0x07310, 0x08210, 0x10010, 185 }; 186 static const uptr SizeDelta = 16; 187#else 188 static const uptr NumBits = 8; 189 static const uptr MinSizeLog = 4; 190 static const uptr MidSizeLog = 7; 191 static const uptr MaxSizeLog = 16; 192 static const u32 MaxNumCachedHint = 14; 193 static const uptr MaxBytesCachedLog = 13; 194 195 static constexpr u32 Classes[] = { 196 0x00020, 0x00030, 0x00040, 0x00050, 0x00060, 0x00070, 0x00080, 0x00090, 197 0x000a0, 0x000b0, 0x000c0, 0x000e0, 0x000f0, 0x00110, 0x00120, 0x00130, 198 0x00150, 0x00160, 0x00170, 0x00190, 0x001d0, 0x00210, 0x00240, 0x002a0, 199 0x00330, 0x00370, 0x003a0, 0x00400, 0x00430, 0x004a0, 0x00530, 0x00610, 200 0x00730, 0x00840, 0x00910, 0x009c0, 0x00a60, 0x00b10, 0x00ca0, 0x00e00, 201 0x00fb0, 0x01030, 0x01130, 0x011f0, 0x01490, 0x01650, 0x01930, 0x02010, 202 0x02190, 0x02490, 0x02850, 0x02d50, 0x03010, 0x03210, 0x03c90, 0x04090, 203 0x04510, 0x04810, 0x05c10, 0x06f10, 0x07310, 0x08010, 0x0c010, 0x10010, 204 }; 205 static const uptr SizeDelta = 16; 206#endif 207}; 208 209typedef TableSizeClassMap<AndroidSizeClassConfig> AndroidSizeClassMap; 210 211struct DefaultSizeClassConfig { 212 static const uptr NumBits = 3; 213 static const uptr MinSizeLog = 5; 214 static const uptr MidSizeLog = 8; 215 static const uptr MaxSizeLog = 17; 216 static const u32 MaxNumCachedHint = 8; 217 static const uptr MaxBytesCachedLog = 10; 218}; 219 220typedef FixedSizeClassMap<DefaultSizeClassConfig> DefaultSizeClassMap; 221 222struct SvelteSizeClassConfig { 223#if SCUDO_WORDSIZE == 64U 224 static const uptr NumBits = 4; 225 static const uptr MinSizeLog = 4; 226 static const uptr MidSizeLog = 8; 227 static const uptr MaxSizeLog = 14; 228 static const u32 MaxNumCachedHint = 4; 229 static const uptr MaxBytesCachedLog = 10; 230#else 231 static const uptr NumBits = 4; 232 static const uptr MinSizeLog = 3; 233 static const uptr MidSizeLog = 7; 234 static const uptr MaxSizeLog = 14; 235 static const u32 MaxNumCachedHint = 5; 236 static const uptr MaxBytesCachedLog = 10; 237#endif 238}; 239 240typedef FixedSizeClassMap<SvelteSizeClassConfig> SvelteSizeClassMap; 241 242template <typename SCMap> inline void printMap() { 243 ScopedString Buffer(1024); 244 uptr PrevS = 0; 245 uptr TotalCached = 0; 246 for (uptr I = 0; I < SCMap::NumClasses; I++) { 247 if (I == SCMap::BatchClassId) 248 continue; 249 const uptr S = SCMap::getSizeByClassId(I); 250 const uptr D = S - PrevS; 251 const uptr P = PrevS ? (D * 100 / PrevS) : 0; 252 const uptr L = S ? getMostSignificantSetBitIndex(S) : 0; 253 const uptr Cached = SCMap::getMaxCachedHint(S) * S; 254 Buffer.append( 255 "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %zu %zu; id %zu\n", 256 I, S, D, P, L, SCMap::getMaxCachedHint(S), Cached, 257 SCMap::getClassIdBySize(S)); 258 TotalCached += Cached; 259 PrevS = S; 260 } 261 Buffer.append("Total Cached: %zu\n", TotalCached); 262 Buffer.output(); 263} 264 265template <typename SCMap> static void validateMap() { 266 for (uptr C = 0; C < SCMap::NumClasses; C++) { 267 if (C == SCMap::BatchClassId) 268 continue; 269 const uptr S = SCMap::getSizeByClassId(C); 270 CHECK_NE(S, 0U); 271 CHECK_EQ(SCMap::getClassIdBySize(S), C); 272 if (C < SCMap::LargestClassId) 273 CHECK_EQ(SCMap::getClassIdBySize(S + 1), C + 1); 274 CHECK_EQ(SCMap::getClassIdBySize(S - 1), C); 275 if (C - 1 != SCMap::BatchClassId) 276 CHECK_GT(SCMap::getSizeByClassId(C), SCMap::getSizeByClassId(C - 1)); 277 } 278 // Do not perform the loop if the maximum size is too large. 279 if (SCMap::MaxSize > (1 << 19)) 280 return; 281 for (uptr S = 1; S <= SCMap::MaxSize; S++) { 282 const uptr C = SCMap::getClassIdBySize(S); 283 CHECK_LT(C, SCMap::NumClasses); 284 CHECK_GE(SCMap::getSizeByClassId(C), S); 285 if (C - 1 != SCMap::BatchClassId) 286 CHECK_LT(SCMap::getSizeByClassId(C - 1), S); 287 } 288} 289} // namespace scudo 290 291#endif // SCUDO_SIZE_CLASS_MAP_H_ 292