|
111
|
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 =
|
|
|
135 kMidClass + ((kMaxSizeLog - kMidSizeLog) << S) + 1 + 1;
|
|
|
136 static const uptr kLargestClassID = kNumClasses - 2;
|
|
|
137 static const uptr kBatchClassID = kNumClasses - 1;
|
|
|
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) {
|
|
|
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);
|
|
|
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) {
|
|
|
158 if (UNLIKELY(size > kMaxSize))
|
|
|
159 return 0;
|
|
|
160 if (size <= kMidSize)
|
|
|
161 return (size + kMinSize - 1) >> kMinSizeLog;
|
|
|
162 uptr l = MostSignificantSetBitIndex(size);
|
|
|
163 uptr hbits = (size >> (l - S)) & M;
|
|
|
164 uptr lbits = size & ((1 << (l - S)) - 1);
|
|
|
165 uptr l1 = l - kMidSizeLog;
|
|
|
166 return kMidClass + (l1 << S) + hbits + (lbits > 0);
|
|
|
167 }
|
|
|
168
|
|
|
169 static uptr MaxCachedHint(uptr class_id) {
|
|
|
170 // Estimate the result for kBatchClassID because this class does not know
|
|
|
171 // the exact size of TransferBatch. We need to cache fewer batches than user
|
|
|
172 // chunks, so this number can be small.
|
|
|
173 if (UNLIKELY(class_id == kBatchClassID))
|
|
|
174 return 16;
|
|
|
175 if (UNLIKELY(class_id == 0))
|
|
|
176 return 0;
|
|
|
177 uptr n = (1UL << kMaxBytesCachedLog) / Size(class_id);
|
|
|
178 return Max<uptr>(1, Min(kMaxNumCachedHint, n));
|
|
|
179 }
|
|
|
180
|
|
|
181 static void Print() {
|
|
|
182 uptr prev_s = 0;
|
|
|
183 uptr total_cached = 0;
|
|
|
184 for (uptr i = 0; i < kNumClasses; i++) {
|
|
|
185 uptr s = Size(i);
|
|
|
186 if (s >= kMidSize / 2 && (s & (s - 1)) == 0)
|
|
|
187 Printf("\n");
|
|
|
188 uptr d = s - prev_s;
|
|
|
189 uptr p = prev_s ? (d * 100 / prev_s) : 0;
|
|
|
190 uptr l = s ? MostSignificantSetBitIndex(s) : 0;
|
|
|
191 uptr cached = MaxCachedHint(i) * s;
|
|
|
192 if (i == kBatchClassID)
|
|
|
193 d = p = l = 0;
|
|
|
194 Printf("c%02zd => s: %zd diff: +%zd %02zd%% l %zd "
|
|
|
195 "cached: %zd %zd; id %zd\n",
|
|
|
196 i, Size(i), d, p, l, MaxCachedHint(i), cached, ClassID(s));
|
|
|
197 total_cached += cached;
|
|
|
198 prev_s = s;
|
|
|
199 }
|
|
|
200 Printf("Total cached: %zd\n", total_cached);
|
|
|
201 }
|
|
|
202
|
|
|
203 static void Validate() {
|
|
|
204 for (uptr c = 1; c < kNumClasses; c++) {
|
|
|
205 // Printf("Validate: c%zd\n", c);
|
|
|
206 uptr s = Size(c);
|
|
|
207 CHECK_NE(s, 0U);
|
|
|
208 if (c == kBatchClassID)
|
|
|
209 continue;
|
|
|
210 CHECK_EQ(ClassID(s), c);
|
|
|
211 if (c < kLargestClassID)
|
|
|
212 CHECK_EQ(ClassID(s + 1), c + 1);
|
|
|
213 CHECK_EQ(ClassID(s - 1), c);
|
|
|
214 CHECK_GT(Size(c), Size(c - 1));
|
|
|
215 }
|
|
|
216 CHECK_EQ(ClassID(kMaxSize + 1), 0);
|
|
|
217
|
|
|
218 for (uptr s = 1; s <= kMaxSize; s++) {
|
|
|
219 uptr c = ClassID(s);
|
|
|
220 // Printf("s%zd => c%zd\n", s, c);
|
|
|
221 CHECK_LT(c, kNumClasses);
|
|
|
222 CHECK_GE(Size(c), s);
|
|
|
223 if (c > 0)
|
|
|
224 CHECK_LT(Size(c - 1), s);
|
|
|
225 }
|
|
|
226 }
|
|
|
227 };
|
|
|
228
|
|
|
229 typedef SizeClassMap<3, 4, 8, 17, 128, 16> DefaultSizeClassMap;
|
|
|
230 typedef SizeClassMap<3, 4, 8, 17, 64, 14> CompactSizeClassMap;
|
|
|
231 typedef SizeClassMap<2, 5, 9, 16, 64, 14> VeryCompactSizeClassMap;
|
