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 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
getSizeByClassId(uptr ClassId)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
getSizeLSBByClassId(uptr ClassId)89 static u8 getSizeLSBByClassId(uptr ClassId) {
90 return u8(getLeastSignificantSetBitIndex(getSizeByClassId(ClassId)));
91 }
92
usesCompressedLSBFormat()93 static constexpr bool usesCompressedLSBFormat() { return false; }
94
getClassIdBySize(uptr Size)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
getMaxCachedHint(uptr Size)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 {
SizeTableSizeTable121 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
computeClassIdSizeTable132 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
getTableSizeSizeTable140 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 {
LSBTableLSBTable150 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
getSizeByClassId(uptr ClassId)192 static uptr getSizeByClassId(uptr ClassId) {
193 return Config::Classes[ClassId - 1];
194 }
195
getSizeLSBByClassId(uptr ClassId)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
usesCompressedLSBFormat()204 static constexpr bool usesCompressedLSBFormat() {
205 return LTable.UseCompressedFormat;
206 }
207
getClassIdBySize(uptr Size)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
getMaxCachedHint(uptr Size)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 u32 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 u32 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 SvelteSizeClassConfig {
293 #if SCUDO_WORDSIZE == 64U
294 static const uptr NumBits = 4;
295 static const uptr MinSizeLog = 4;
296 static const uptr MidSizeLog = 8;
297 static const uptr MaxSizeLog = 14;
298 static const u16 MaxNumCachedHint = 13;
299 static const uptr MaxBytesCachedLog = 10;
300 static const uptr SizeDelta = Chunk::getHeaderSize();
301 #else
302 static const uptr NumBits = 4;
303 static const uptr MinSizeLog = 3;
304 static const uptr MidSizeLog = 7;
305 static const uptr MaxSizeLog = 14;
306 static const u16 MaxNumCachedHint = 14;
307 static const uptr MaxBytesCachedLog = 10;
308 static const uptr SizeDelta = Chunk::getHeaderSize();
309 #endif
310 };
311
312 typedef FixedSizeClassMap<SvelteSizeClassConfig> SvelteSizeClassMap;
313
314 // Trusty is configured to only have one region containing blocks of size
315 // 2^7 bytes.
316 struct TrustySizeClassConfig {
317 static const uptr NumBits = 1;
318 static const uptr MinSizeLog = 7;
319 static const uptr MidSizeLog = 7;
320 static const uptr MaxSizeLog = 7;
321 static const u16 MaxNumCachedHint = 12;
322 static const uptr MaxBytesCachedLog = 10;
323 static const uptr SizeDelta = 0;
324 };
325
326 typedef FixedSizeClassMap<TrustySizeClassConfig> TrustySizeClassMap;
327
printMap()328 template <typename SCMap> inline void printMap() {
329 ScopedString Buffer;
330 uptr PrevS = 0;
331 uptr TotalCached = 0;
332 for (uptr I = 0; I < SCMap::NumClasses; I++) {
333 if (I == SCMap::BatchClassId)
334 continue;
335 const uptr S = SCMap::getSizeByClassId(I);
336 const uptr D = S - PrevS;
337 const uptr P = PrevS ? (D * 100 / PrevS) : 0;
338 const uptr L = S ? getMostSignificantSetBitIndex(S) : 0;
339 const uptr Cached = SCMap::getMaxCachedHint(S) * S;
340 Buffer.append(
341 "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %u %zu; id %zu\n", I,
342 S, D, P, L, SCMap::getMaxCachedHint(S), Cached,
343 SCMap::getClassIdBySize(S));
344 TotalCached += Cached;
345 PrevS = S;
346 }
347 Buffer.append("Total Cached: %zu\n", TotalCached);
348 Buffer.output();
349 }
350
validateMap()351 template <typename SCMap> static UNUSED void validateMap() {
352 for (uptr C = 0; C < SCMap::NumClasses; C++) {
353 if (C == SCMap::BatchClassId)
354 continue;
355 const uptr S = SCMap::getSizeByClassId(C);
356 CHECK_NE(S, 0U);
357 CHECK_EQ(SCMap::getClassIdBySize(S), C);
358 if (C < SCMap::LargestClassId)
359 CHECK_EQ(SCMap::getClassIdBySize(S + 1), C + 1);
360 CHECK_EQ(SCMap::getClassIdBySize(S - 1), C);
361 if (C - 1 != SCMap::BatchClassId)
362 CHECK_GT(SCMap::getSizeByClassId(C), SCMap::getSizeByClassId(C - 1));
363 }
364 // Do not perform the loop if the maximum size is too large.
365 if (SCMap::MaxSize > (1 << 19))
366 return;
367 for (uptr S = 1; S <= SCMap::MaxSize; S++) {
368 const uptr C = SCMap::getClassIdBySize(S);
369 CHECK_LT(C, SCMap::NumClasses);
370 CHECK_GE(SCMap::getSizeByClassId(C), S);
371 if (C - 1 != SCMap::BatchClassId)
372 CHECK_LT(SCMap::getSizeByClassId(C - 1), S);
373 }
374 }
375 } // namespace scudo
376
377 #endif // SCUDO_SIZE_CLASS_MAP_H_
378