]>
Commit | Line | Data |
---|---|---|
23e39437 | 1 | //===-- sanitizer_allocator_size_class_map.h --------------------*- C++ -*-===// |
2 | // | |
3 | // This file is distributed under the University of Illinois Open Source | |
4 | // License. See LICENSE.TXT for details. | |
5 | // | |
6 | //===----------------------------------------------------------------------===// | |
7 | // | |
8 | // Part of the Sanitizer Allocator. | |
9 | // | |
10 | //===----------------------------------------------------------------------===// | |
11 | #ifndef SANITIZER_ALLOCATOR_H | |
12 | #error This file must be included inside sanitizer_allocator.h | |
13 | #endif | |
14 | ||
15 | // SizeClassMap maps allocation sizes into size classes and back. | |
16 | // Class 0 always corresponds to size 0. | |
17 | // The other sizes are controlled by the template parameters: | |
18 | // kMinSizeLog: defines the class 1 as 2^kMinSizeLog. | |
19 | // kMaxSizeLog: defines the last class as 2^kMaxSizeLog. | |
20 | // kMidSizeLog: the classes starting from 1 increase with step | |
21 | // 2^kMinSizeLog until 2^kMidSizeLog. | |
22 | // kNumBits: the number of non-zero bits in sizes after 2^kMidSizeLog. | |
23 | // E.g. with kNumBits==3 all size classes after 2^kMidSizeLog | |
24 | // look like 0b1xx0..0, where x is either 0 or 1. | |
25 | // | |
26 | // Example: kNumBits=3, kMidSizeLog=4, kMidSizeLog=8, kMaxSizeLog=17: | |
27 | // | |
28 | // Classes 1 - 16 correspond to sizes 16 to 256 (size = class_id * 16). | |
29 | // Next 4 classes: 256 + i * 64 (i = 1 to 4). | |
30 | // Next 4 classes: 512 + i * 128 (i = 1 to 4). | |
31 | // ... | |
32 | // Next 4 classes: 2^k + i * 2^(k-2) (i = 1 to 4). | |
33 | // Last class corresponds to kMaxSize = 1 << kMaxSizeLog. | |
34 | // | |
35 | // This structure of the size class map gives us: | |
36 | // - Efficient table-free class-to-size and size-to-class functions. | |
37 | // - Difference between two consequent size classes is between 14% and 25% | |
38 | // | |
39 | // This class also gives a hint to a thread-caching allocator about the amount | |
40 | // of chunks that need to be cached per-thread: | |
41 | // - kMaxNumCachedHint is a hint for maximal number of chunks per size class. | |
42 | // The actual number is computed in TransferBatch. | |
43 | // - (1 << kMaxBytesCachedLog) is the maximal number of bytes per size class. | |
44 | // | |
45 | // Part of output of SizeClassMap::Print(): | |
46 | // c00 => s: 0 diff: +0 00% l 0 cached: 0 0; id 0 | |
47 | // c01 => s: 16 diff: +16 00% l 4 cached: 256 4096; id 1 | |
48 | // c02 => s: 32 diff: +16 100% l 5 cached: 256 8192; id 2 | |
49 | // c03 => s: 48 diff: +16 50% l 5 cached: 256 12288; id 3 | |
50 | // c04 => s: 64 diff: +16 33% l 6 cached: 256 16384; id 4 | |
51 | // c05 => s: 80 diff: +16 25% l 6 cached: 256 20480; id 5 | |
52 | // c06 => s: 96 diff: +16 20% l 6 cached: 256 24576; id 6 | |
53 | // c07 => s: 112 diff: +16 16% l 6 cached: 256 28672; id 7 | |
54 | // | |
55 | // c08 => s: 128 diff: +16 14% l 7 cached: 256 32768; id 8 | |
56 | // c09 => s: 144 diff: +16 12% l 7 cached: 256 36864; id 9 | |
57 | // c10 => s: 160 diff: +16 11% l 7 cached: 256 40960; id 10 | |
58 | // c11 => s: 176 diff: +16 10% l 7 cached: 256 45056; id 11 | |
59 | // c12 => s: 192 diff: +16 09% l 7 cached: 256 49152; id 12 | |
60 | // c13 => s: 208 diff: +16 08% l 7 cached: 256 53248; id 13 | |
61 | // c14 => s: 224 diff: +16 07% l 7 cached: 256 57344; id 14 | |
62 | // c15 => s: 240 diff: +16 07% l 7 cached: 256 61440; id 15 | |
63 | // | |
64 | // c16 => s: 256 diff: +16 06% l 8 cached: 256 65536; id 16 | |
65 | // c17 => s: 320 diff: +64 25% l 8 cached: 204 65280; id 17 | |
66 | // c18 => s: 384 diff: +64 20% l 8 cached: 170 65280; id 18 | |
67 | // c19 => s: 448 diff: +64 16% l 8 cached: 146 65408; id 19 | |
68 | // | |
69 | // c20 => s: 512 diff: +64 14% l 9 cached: 128 65536; id 20 | |
70 | // c21 => s: 640 diff: +128 25% l 9 cached: 102 65280; id 21 | |
71 | // c22 => s: 768 diff: +128 20% l 9 cached: 85 65280; id 22 | |
72 | // c23 => s: 896 diff: +128 16% l 9 cached: 73 65408; id 23 | |
73 | // | |
74 | // c24 => s: 1024 diff: +128 14% l 10 cached: 64 65536; id 24 | |
75 | // c25 => s: 1280 diff: +256 25% l 10 cached: 51 65280; id 25 | |
76 | // c26 => s: 1536 diff: +256 20% l 10 cached: 42 64512; id 26 | |
77 | // c27 => s: 1792 diff: +256 16% l 10 cached: 36 64512; id 27 | |
78 | // | |
79 | // ... | |
80 | // | |
81 | // c48 => s: 65536 diff: +8192 14% l 16 cached: 1 65536; id 48 | |
82 | // c49 => s: 81920 diff: +16384 25% l 16 cached: 1 81920; id 49 | |
83 | // c50 => s: 98304 diff: +16384 20% l 16 cached: 1 98304; id 50 | |
84 | // c51 => s: 114688 diff: +16384 16% l 16 cached: 1 114688; id 51 | |
85 | // | |
86 | // c52 => s: 131072 diff: +16384 14% l 17 cached: 1 131072; id 52 | |
87 | // | |
88 | // | |
89 | // Another example (kNumBits=2): | |
90 | // c00 => s: 0 diff: +0 00% l 0 cached: 0 0; id 0 | |
91 | // c01 => s: 32 diff: +32 00% l 5 cached: 64 2048; id 1 | |
92 | // c02 => s: 64 diff: +32 100% l 6 cached: 64 4096; id 2 | |
93 | // c03 => s: 96 diff: +32 50% l 6 cached: 64 6144; id 3 | |
94 | // c04 => s: 128 diff: +32 33% l 7 cached: 64 8192; id 4 | |
95 | // c05 => s: 160 diff: +32 25% l 7 cached: 64 10240; id 5 | |
96 | // c06 => s: 192 diff: +32 20% l 7 cached: 64 12288; id 6 | |
97 | // c07 => s: 224 diff: +32 16% l 7 cached: 64 14336; id 7 | |
98 | // c08 => s: 256 diff: +32 14% l 8 cached: 64 16384; id 8 | |
99 | // c09 => s: 384 diff: +128 50% l 8 cached: 42 16128; id 9 | |
100 | // c10 => s: 512 diff: +128 33% l 9 cached: 32 16384; id 10 | |
101 | // c11 => s: 768 diff: +256 50% l 9 cached: 21 16128; id 11 | |
102 | // c12 => s: 1024 diff: +256 33% l 10 cached: 16 16384; id 12 | |
103 | // c13 => s: 1536 diff: +512 50% l 10 cached: 10 15360; id 13 | |
104 | // c14 => s: 2048 diff: +512 33% l 11 cached: 8 16384; id 14 | |
105 | // c15 => s: 3072 diff: +1024 50% l 11 cached: 5 15360; id 15 | |
106 | // c16 => s: 4096 diff: +1024 33% l 12 cached: 4 16384; id 16 | |
107 | // c17 => s: 6144 diff: +2048 50% l 12 cached: 2 12288; id 17 | |
108 | // c18 => s: 8192 diff: +2048 33% l 13 cached: 2 16384; id 18 | |
109 | // c19 => s: 12288 diff: +4096 50% l 13 cached: 1 12288; id 19 | |
110 | // c20 => s: 16384 diff: +4096 33% l 14 cached: 1 16384; id 20 | |
111 | // c21 => s: 24576 diff: +8192 50% l 14 cached: 1 24576; id 21 | |
112 | // c22 => s: 32768 diff: +8192 33% l 15 cached: 1 32768; id 22 | |
113 | // c23 => s: 49152 diff: +16384 50% l 15 cached: 1 49152; id 23 | |
114 | // c24 => s: 65536 diff: +16384 33% l 16 cached: 1 65536; id 24 | |
115 | // c25 => s: 98304 diff: +32768 50% l 16 cached: 1 98304; id 25 | |
116 | // c26 => s: 131072 diff: +32768 33% l 17 cached: 1 131072; id 26 | |
117 | ||
118 | template <uptr kNumBits, uptr kMinSizeLog, uptr kMidSizeLog, uptr kMaxSizeLog, | |
119 | uptr kMaxNumCachedHintT, uptr kMaxBytesCachedLog> | |
120 | class SizeClassMap { | |
121 | static const uptr kMinSize = 1 << kMinSizeLog; | |
122 | static const uptr kMidSize = 1 << kMidSizeLog; | |
123 | static const uptr kMidClass = kMidSize / kMinSize; | |
124 | static const uptr S = kNumBits - 1; | |
125 | static const uptr M = (1 << S) - 1; | |
126 | ||
127 | public: | |
128 | // kMaxNumCachedHintT is a power of two. It serves as a hint | |
129 | // for the size of TransferBatch, the actual size could be a bit smaller. | |
130 | static const uptr kMaxNumCachedHint = kMaxNumCachedHintT; | |
131 | COMPILER_CHECK((kMaxNumCachedHint & (kMaxNumCachedHint - 1)) == 0); | |
132 | ||
133 | static const uptr kMaxSize = 1UL << kMaxSizeLog; | |
134 | static const uptr kNumClasses = | |
36093749 | 135 | kMidClass + ((kMaxSizeLog - kMidSizeLog) << S) + 1 + 1; |
23e39437 | 136 | static const uptr kLargestClassID = kNumClasses - 2; |
36093749 | 137 | static const uptr kBatchClassID = kNumClasses - 1; |
23e39437 | 138 | COMPILER_CHECK(kNumClasses >= 16 && kNumClasses <= 256); |
139 | static const uptr kNumClassesRounded = | |
140 | kNumClasses <= 32 ? 32 : | |
141 | kNumClasses <= 64 ? 64 : | |
142 | kNumClasses <= 128 ? 128 : 256; | |
143 | ||
144 | static uptr Size(uptr class_id) { | |
36093749 | 145 | // Estimate the result for kBatchClassID because this class does not know |
146 | // the exact size of TransferBatch. It's OK since we are using the actual | |
147 | // sizeof(TransferBatch) where it matters. | |
148 | if (UNLIKELY(class_id == kBatchClassID)) | |
149 | return kMaxNumCachedHint * sizeof(uptr); | |
23e39437 | 150 | if (class_id <= kMidClass) |
151 | return kMinSize * class_id; | |
152 | class_id -= kMidClass; | |
153 | uptr t = kMidSize << (class_id >> S); | |
154 | return t + (t >> S) * (class_id & M); | |
155 | } | |
156 | ||
157 | static uptr ClassID(uptr size) { | |
36093749 | 158 | if (UNLIKELY(size > kMaxSize)) |
159 | return 0; | |
23e39437 | 160 | if (size <= kMidSize) |
161 | return (size + kMinSize - 1) >> kMinSizeLog; | |
d2ef4bee | 162 | const uptr l = MostSignificantSetBitIndex(size); |
163 | const uptr hbits = (size >> (l - S)) & M; | |
164 | const uptr lbits = size & ((1U << (l - S)) - 1); | |
165 | const uptr l1 = l - kMidSizeLog; | |
23e39437 | 166 | return kMidClass + (l1 << S) + hbits + (lbits > 0); |
167 | } | |
168 | ||
d2ef4bee | 169 | static uptr MaxCachedHint(uptr size) { |
170 | DCHECK_LE(size, kMaxSize); | |
171 | if (UNLIKELY(size == 0)) | |
36093749 | 172 | return 0; |
d2ef4bee | 173 | uptr n; |
174 | // Force a 32-bit division if the template parameters allow for it. | |
175 | if (kMaxBytesCachedLog > 31 || kMaxSizeLog > 31) | |
176 | n = (1UL << kMaxBytesCachedLog) / size; | |
177 | else | |
178 | n = (1U << kMaxBytesCachedLog) / static_cast<u32>(size); | |
179 | return Max<uptr>(1U, Min(kMaxNumCachedHint, n)); | |
23e39437 | 180 | } |
181 | ||
182 | static void Print() { | |
183 | uptr prev_s = 0; | |
184 | uptr total_cached = 0; | |
185 | for (uptr i = 0; i < kNumClasses; i++) { | |
186 | uptr s = Size(i); | |
187 | if (s >= kMidSize / 2 && (s & (s - 1)) == 0) | |
188 | Printf("\n"); | |
189 | uptr d = s - prev_s; | |
190 | uptr p = prev_s ? (d * 100 / prev_s) : 0; | |
191 | uptr l = s ? MostSignificantSetBitIndex(s) : 0; | |
d2ef4bee | 192 | uptr cached = MaxCachedHint(s) * s; |
36093749 | 193 | if (i == kBatchClassID) |
194 | d = p = l = 0; | |
23e39437 | 195 | Printf("c%02zd => s: %zd diff: +%zd %02zd%% l %zd " |
196 | "cached: %zd %zd; id %zd\n", | |
d2ef4bee | 197 | i, Size(i), d, p, l, MaxCachedHint(s), cached, ClassID(s)); |
23e39437 | 198 | total_cached += cached; |
199 | prev_s = s; | |
200 | } | |
201 | Printf("Total cached: %zd\n", total_cached); | |
202 | } | |
203 | ||
204 | static void Validate() { | |
205 | for (uptr c = 1; c < kNumClasses; c++) { | |
206 | // Printf("Validate: c%zd\n", c); | |
207 | uptr s = Size(c); | |
208 | CHECK_NE(s, 0U); | |
36093749 | 209 | if (c == kBatchClassID) |
210 | continue; | |
23e39437 | 211 | CHECK_EQ(ClassID(s), c); |
36093749 | 212 | if (c < kLargestClassID) |
23e39437 | 213 | CHECK_EQ(ClassID(s + 1), c + 1); |
214 | CHECK_EQ(ClassID(s - 1), c); | |
36093749 | 215 | CHECK_GT(Size(c), Size(c - 1)); |
23e39437 | 216 | } |
217 | CHECK_EQ(ClassID(kMaxSize + 1), 0); | |
218 | ||
219 | for (uptr s = 1; s <= kMaxSize; s++) { | |
220 | uptr c = ClassID(s); | |
221 | // Printf("s%zd => c%zd\n", s, c); | |
222 | CHECK_LT(c, kNumClasses); | |
223 | CHECK_GE(Size(c), s); | |
224 | if (c > 0) | |
36093749 | 225 | CHECK_LT(Size(c - 1), s); |
23e39437 | 226 | } |
227 | } | |
228 | }; | |
229 | ||
230 | typedef SizeClassMap<3, 4, 8, 17, 128, 16> DefaultSizeClassMap; | |
231 | typedef SizeClassMap<3, 4, 8, 17, 64, 14> CompactSizeClassMap; | |
232 | typedef SizeClassMap<2, 5, 9, 16, 64, 14> VeryCompactSizeClassMap; | |
d2ef4bee | 233 | |
234 | // The following SizeClassMap only holds a way small number of cached entries, | |
235 | // allowing for denser per-class arrays, smaller memory footprint and usually | |
236 | // better performances in threaded environments. | |
237 | typedef SizeClassMap<3, 4, 8, 17, 8, 10> DenseSizeClassMap; |