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 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 
286 typedef TableSizeClassMap<AndroidSizeClassConfig> AndroidSizeClassMap;
287 
288 #if SCUDO_WORDSIZE == 64U && defined(__clang__)
289 static_assert(AndroidSizeClassMap::usesCompressedLSBFormat(), "");
290 #endif
291 
292 struct 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 
302 typedef FixedSizeClassMap<TrustySizeClassConfig> TrustySizeClassMap;
303 
304 template <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(S) : 0;
315     const uptr Cached = SCMap::getMaxCachedHint(S) * S;
316     Buffer.append(
317         "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("Total Cached: %zu\n", TotalCached);
324   Buffer.output();
325 }
326 
327 template <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