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 static const uptr SizeDelta = Chunk::getHeaderSize();
68
69 public:
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
getSizeByClassId(uptr ClassId)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
getClassIdBySize(uptr Size)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
getMaxCachedHint(uptr Size)98 static u32 getMaxCachedHint(uptr Size) {
99 DCHECK_LE(Size, MaxSize);
100 return Base::getMaxCachedHint(Size);
101 }
102 };
103
104 template <typename Config>
105 class 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 {
SizeTableSizeTable114 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
computeClassIdSizeTable125 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
getTableSizeSizeTable133 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
142 public:
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
getSizeByClassId(uptr ClassId)151 static uptr getSizeByClassId(uptr ClassId) {
152 return Config::Classes[ClassId - 1];
153 }
154
getClassIdBySize(uptr Size)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
getMaxCachedHint(uptr Size)165 static u32 getMaxCachedHint(uptr Size) {
166 DCHECK_LE(Size, MaxSize);
167 return Base::getMaxCachedHint(Size);
168 }
169 };
170
171 struct 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
209 typedef TableSizeClassMap<AndroidSizeClassConfig> AndroidSizeClassMap;
210
211 struct 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
220 typedef FixedSizeClassMap<DefaultSizeClassConfig> DefaultSizeClassMap;
221
222 struct 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
240 typedef FixedSizeClassMap<SvelteSizeClassConfig> SvelteSizeClassMap;
241
printMap()242 template <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
validateMap()265 template <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