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 
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 {
26   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 
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 
86   static u8 getSizeLSBByClassId(uptr ClassId) {
87     return u8(getLeastSignificantSetBitIndex(getSizeByClassId(ClassId)));
88   }
89 
90   static constexpr bool usesCompressedLSBFormat() { return false; }
91 
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 
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 {
118     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 
129     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 
137     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 {
147     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 
189   static uptr getSizeByClassId(uptr ClassId) {
190     return Config::Classes[ClassId - 1];
191   }
192 
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 
201   static constexpr bool usesCompressedLSBFormat() {
202     return LTable.UseCompressedFormat;
203   }
204 
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 
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 
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: %u %zu; id %zu\n", I,
339         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 
348 template <typename SCMap> static UNUSED 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