blob: b7df54cf80982a4a83c45593edc99f1360ed61b2 [file] [log] [blame]
Kostya Kortchinsky1ea33a72019-04-25 15:49:34 +00001//===-- 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 "common.h"
13#include "string_utils.h"
14
15namespace scudo {
16
17// SizeClassMap maps allocation sizes into size classes and back, in an
18// efficient table-free manner.
19//
20// Class 0 is a special class that doesn't abide by the same rules as other
21// classes. The allocator uses it to hold batches.
22//
23// The other sizes are controlled by the template parameters:
24// - MinSizeLog: defines the first class as 2^MinSizeLog bytes.
25// - MaxSizeLog: defines the last class as 2^MaxSizeLog bytes.
26// - MidSizeLog: classes increase with step 2^MinSizeLog from 2^MinSizeLog to
27// 2^MidSizeLog bytes.
28// - NumBits: the number of non-zero bits in sizes after 2^MidSizeLog.
29// eg. with NumBits==3 all size classes after 2^MidSizeLog look like
30// 0b1xx0..0 (where x is either 0 or 1).
31//
32// This class also gives a hint to a thread-caching allocator about the amount
33// of chunks that can be cached per-thread:
Kostya Kortchinsky070d0782019-04-30 14:56:18 +000034// - MaxNumCachedHint is a hint for the max number of chunks cached per class.
35// - 2^MaxBytesCachedLog is the max number of bytes cached per class.
Kostya Kortchinsky1ea33a72019-04-25 15:49:34 +000036
37template <u8 NumBits, u8 MinSizeLog, u8 MidSizeLog, u8 MaxSizeLog,
38 u32 MaxNumCachedHintT, u8 MaxBytesCachedLog>
39class SizeClassMap {
40 static const uptr MinSize = 1UL << MinSizeLog;
41 static const uptr MidSize = 1UL << MidSizeLog;
42 static const uptr MidClass = MidSize / MinSize;
43 static const u8 S = NumBits - 1;
44 static const uptr M = (1UL << S) - 1;
45
46public:
47 static const u32 MaxNumCachedHint = MaxNumCachedHintT;
48
49 static const uptr MaxSize = 1UL << MaxSizeLog;
50 static const uptr NumClasses =
51 MidClass + ((MaxSizeLog - MidSizeLog) << S) + 1;
52 COMPILER_CHECK(NumClasses <= 256);
53 static const uptr LargestClassId = NumClasses - 1;
54 static const uptr BatchClassId = 0;
55
56 static uptr getSizeByClassId(uptr ClassId) {
57 DCHECK_NE(ClassId, BatchClassId);
58 if (ClassId <= MidClass)
59 return ClassId << MinSizeLog;
60 ClassId -= MidClass;
61 const uptr T = MidSize << (ClassId >> S);
62 return T + (T >> S) * (ClassId & M);
63 }
64
65 static uptr getClassIdBySize(uptr Size) {
66 DCHECK_LE(Size, MaxSize);
67 if (Size <= MidSize)
68 return (Size + MinSize - 1) >> MinSizeLog;
69 const uptr L = getMostSignificantSetBitIndex(Size);
70 const uptr HBits = (Size >> (L - S)) & M;
71 const uptr LBits = Size & ((1UL << (L - S)) - 1);
72 const uptr L1 = L - MidSizeLog;
73 return MidClass + (L1 << S) + HBits + (LBits > 0);
74 }
75
76 static u32 getMaxCachedHint(uptr Size) {
77 DCHECK_LE(Size, MaxSize);
78 DCHECK_NE(Size, 0);
79 u32 N;
80 // Force a 32-bit division if the template parameters allow for it.
81 if (MaxBytesCachedLog > 31 || MaxSizeLog > 31)
82 N = static_cast<u32>((1UL << MaxBytesCachedLog) / Size);
83 else
84 N = (1U << MaxBytesCachedLog) / static_cast<u32>(Size);
85 return Max(1U, Min(MaxNumCachedHint, N));
86 }
87
88 static void print() {
89 uptr PrevS = 0;
90 uptr TotalCached = 0;
91 for (uptr I = 0; I < NumClasses; I++) {
92 if (I == BatchClassId)
93 continue;
94 const uptr S = getSizeByClassId(I);
95 if (S >= MidSize / 2 && (S & (S - 1)) == 0)
96 Printf("\n");
97 const uptr D = S - PrevS;
98 const uptr P = PrevS ? (D * 100 / PrevS) : 0;
99 const uptr L = S ? getMostSignificantSetBitIndex(S) : 0;
100 const uptr Cached = getMaxCachedHint(S) * S;
101 Printf(
102 "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %zu %zu; id %zu\n",
103 I, getSizeByClassId(I), D, P, L, getMaxCachedHint(S), Cached,
104 getClassIdBySize(S));
105 TotalCached += Cached;
106 PrevS = S;
107 }
108 Printf("Total Cached: %zu\n", TotalCached);
109 }
110
111 static void validate() {
112 for (uptr C = 0; C < NumClasses; C++) {
113 if (C == BatchClassId)
114 continue;
115 const uptr S = getSizeByClassId(C);
116 CHECK_NE(S, 0U);
117 CHECK_EQ(getClassIdBySize(S), C);
118 if (C < LargestClassId)
119 CHECK_EQ(getClassIdBySize(S + 1), C + 1);
120 CHECK_EQ(getClassIdBySize(S - 1), C);
121 CHECK_GT(getSizeByClassId(C), getSizeByClassId(C - 1));
122 }
123 // Do not perform the loop if the maximum size is too large.
124 if (MaxSizeLog > 19)
125 return;
126 for (uptr S = 1; S <= MaxSize; S++) {
127 const uptr C = getClassIdBySize(S);
128 CHECK_LT(C, NumClasses);
129 CHECK_GE(getSizeByClassId(C), S);
130 if (C > 0)
131 CHECK_LT(getSizeByClassId(C - 1), S);
132 }
133 }
134};
135
136typedef SizeClassMap<3, 5, 8, 17, 8, 10> DefaultSizeClassMap;
137
138// TODO(kostyak): further tune class maps for Android & Fuchsia.
139#if SCUDO_WORDSIZE == 64U
140typedef SizeClassMap<3, 5, 8, 15, 8, 10> SvelteSizeClassMap;
141typedef SizeClassMap<3, 5, 8, 16, 14, 12> AndroidSizeClassMap;
142#else
143typedef SizeClassMap<3, 4, 7, 15, 8, 10> SvelteSizeClassMap;
144typedef SizeClassMap<3, 4, 7, 16, 14, 12> AndroidSizeClassMap;
145#endif
146
147} // namespace scudo
148
149#endif // SCUDO_SIZE_CLASS_MAP_H_