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