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