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 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 
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(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 
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 {
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(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 
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 
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 
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 struct TrustySizeClassConfig {
315   static const uptr NumBits = 1;
316   static const uptr MinSizeLog = 5;
317   static const uptr MidSizeLog = 5;
318   static const uptr MaxSizeLog = 15;
319   static const u16 MaxNumCachedHint = 12;
320   static const uptr MaxBytesCachedLog = 10;
321   static const uptr SizeDelta = 0;
322 };
323 
324 typedef FixedSizeClassMap<TrustySizeClassConfig> TrustySizeClassMap;
325 
326 template <typename SCMap> inline void printMap() {
327   ScopedString Buffer;
328   uptr PrevS = 0;
329   uptr TotalCached = 0;
330   for (uptr I = 0; I < SCMap::NumClasses; I++) {
331     if (I == SCMap::BatchClassId)
332       continue;
333     const uptr S = SCMap::getSizeByClassId(I);
334     const uptr D = S - PrevS;
335     const uptr P = PrevS ? (D * 100 / PrevS) : 0;
336     const uptr L = S ? getMostSignificantSetBitIndex(S) : 0;
337     const uptr Cached = SCMap::getMaxCachedHint(S) * S;
338     Buffer.append(
339         "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %u %zu; id %zu\n", I,
340         S, D, P, L, SCMap::getMaxCachedHint(S), Cached,
341         SCMap::getClassIdBySize(S));
342     TotalCached += Cached;
343     PrevS = S;
344   }
345   Buffer.append("Total Cached: %zu\n", TotalCached);
346   Buffer.output();
347 }
348 
349 template <typename SCMap> static UNUSED void validateMap() {
350   for (uptr C = 0; C < SCMap::NumClasses; C++) {
351     if (C == SCMap::BatchClassId)
352       continue;
353     const uptr S = SCMap::getSizeByClassId(C);
354     CHECK_NE(S, 0U);
355     CHECK_EQ(SCMap::getClassIdBySize(S), C);
356     if (C < SCMap::LargestClassId)
357       CHECK_EQ(SCMap::getClassIdBySize(S + 1), C + 1);
358     CHECK_EQ(SCMap::getClassIdBySize(S - 1), C);
359     if (C - 1 != SCMap::BatchClassId)
360       CHECK_GT(SCMap::getSizeByClassId(C), SCMap::getSizeByClassId(C - 1));
361   }
362   // Do not perform the loop if the maximum size is too large.
363   if (SCMap::MaxSize > (1 << 19))
364     return;
365   for (uptr S = 1; S <= SCMap::MaxSize; S++) {
366     const uptr C = SCMap::getClassIdBySize(S);
367     CHECK_LT(C, SCMap::NumClasses);
368     CHECK_GE(SCMap::getSizeByClassId(C), S);
369     if (C - 1 != SCMap::BatchClassId)
370       CHECK_LT(SCMap::getSizeByClassId(C - 1), S);
371   }
372 }
373 } // namespace scudo
374 
375 #endif // SCUDO_SIZE_CLASS_MAP_H_
376