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