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