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 = (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 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.
60template <typename Config>
61class 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
70public:
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(X: 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
111template <typename Config>
112class 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(Size: 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
183public:
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
224struct 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
234typedef FixedSizeClassMap<DefaultSizeClassConfig> DefaultSizeClassMap;
235
236struct 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
246typedef FixedSizeClassMap<FuchsiaSizeClassConfig> FuchsiaSizeClassMap;
247
248struct 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
286typedef TableSizeClassMap<AndroidSizeClassConfig> AndroidSizeClassMap;
287
288#if SCUDO_WORDSIZE == 64U && defined(__clang__)
289static_assert(AndroidSizeClassMap::usesCompressedLSBFormat(), "");
290#endif
291
292struct 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
302typedef FixedSizeClassMap<TrustySizeClassConfig> TrustySizeClassMap;
303
304template <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(X: S) : 0;
315 const uptr Cached = SCMap::getMaxCachedHint(S) * S;
316 Buffer.append(
317 Format: "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(Format: "Total Cached: %zu\n", TotalCached);
324 Buffer.output();
325}
326
327template <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

source code of compiler-rt/lib/scudo/standalone/size_class_map.h