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
scaledLog2(uptr Size,uptr ZeroLog,uptr LogBits)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 {
getMaxCachedHintSizeClassMapBase26 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
getSizeByClassId(uptr ClassId)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
getSizeLSBByClassId(uptr ClassId)86 static u8 getSizeLSBByClassId(uptr ClassId) {
87 return u8(getLeastSignificantSetBitIndex(getSizeByClassId(ClassId)));
88 }
89
usesCompressedLSBFormat()90 static constexpr bool usesCompressedLSBFormat() { return false; }
91
getClassIdBySize(uptr Size)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
getMaxCachedHint(uptr Size)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 {
SizeTableSizeTable118 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
computeClassIdSizeTable129 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
getTableSizeSizeTable137 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 {
LSBTableLSBTable147 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
getSizeByClassId(uptr ClassId)189 static uptr getSizeByClassId(uptr ClassId) {
190 return Config::Classes[ClassId - 1];
191 }
192
getSizeLSBByClassId(uptr ClassId)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
usesCompressedLSBFormat()201 static constexpr bool usesCompressedLSBFormat() {
202 return LTable.UseCompressedFormat;
203 }
204
getClassIdBySize(uptr Size)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
getMaxCachedHint(uptr Size)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
printMap()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: %zu %zu; id %zu\n",
339 I, 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
validateMap()348 template <typename SCMap> static 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