1 | #ifndef JEMALLOC_INTERNAL_SC_H |
2 | #define JEMALLOC_INTERNAL_SC_H |
3 | |
4 | #include "jemalloc/internal/jemalloc_internal_types.h" |
5 | |
6 | /* |
7 | * Size class computations: |
8 | * |
9 | * These are a little tricky; we'll first start by describing how things |
10 | * generally work, and then describe some of the details. |
11 | * |
12 | * Ignore the first few size classes for a moment. We can then split all the |
13 | * remaining size classes into groups. The size classes in a group are spaced |
14 | * such that they cover allocation request sizes in a power-of-2 range. The |
15 | * power of two is called the base of the group, and the size classes in it |
16 | * satisfy allocations in the half-open range (base, base * 2]. There are |
17 | * SC_NGROUP size classes in each group, equally spaced in the range, so that |
18 | * each one covers allocations for base / SC_NGROUP possible allocation sizes. |
19 | * We call that value (base / SC_NGROUP) the delta of the group. Each size class |
20 | * is delta larger than the one before it (including the initial size class in a |
21 | * group, which is delta larger than base, the largest size class in the |
22 | * previous group). |
23 | * To make the math all work out nicely, we require that SC_NGROUP is a power of |
24 | * two, and define it in terms of SC_LG_NGROUP. We'll often talk in terms of |
25 | * lg_base and lg_delta. For each of these groups then, we have that |
26 | * lg_delta == lg_base - SC_LG_NGROUP. |
27 | * The size classes in a group with a given lg_base and lg_delta (which, recall, |
28 | * can be computed from lg_base for these groups) are therefore: |
29 | * base + 1 * delta |
30 | * which covers allocations in (base, base + 1 * delta] |
31 | * base + 2 * delta |
32 | * which covers allocations in (base + 1 * delta, base + 2 * delta]. |
33 | * base + 3 * delta |
34 | * which covers allocations in (base + 2 * delta, base + 3 * delta]. |
35 | * ... |
36 | * base + SC_NGROUP * delta ( == 2 * base) |
37 | * which covers allocations in (base + (SC_NGROUP - 1) * delta, 2 * base]. |
38 | * (Note that currently SC_NGROUP is always 4, so the "..." is empty in |
39 | * practice.) |
40 | * Note that the last size class in the group is the next power of two (after |
41 | * base), so that we've set up the induction correctly for the next group's |
42 | * selection of delta. |
43 | * |
44 | * Now, let's start considering the first few size classes. Two extra constants |
45 | * come into play here: LG_QUANTUM and SC_LG_TINY_MIN. LG_QUANTUM ensures |
46 | * correct platform alignment; all objects of size (1 << LG_QUANTUM) or larger |
47 | * are at least (1 << LG_QUANTUM) aligned; this can be used to ensure that we |
48 | * never return improperly aligned memory, by making (1 << LG_QUANTUM) equal the |
49 | * highest required alignment of a platform. For allocation sizes smaller than |
50 | * (1 << LG_QUANTUM) though, we can be more relaxed (since we don't support |
51 | * platforms with types with alignment larger than their size). To allow such |
52 | * allocations (without wasting space unnecessarily), we introduce tiny size |
53 | * classes; one per power of two, up until we hit the quantum size. There are |
54 | * therefore LG_QUANTUM - SC_LG_TINY_MIN such size classes. |
55 | * |
56 | * Next, we have a size class of size (1 << LG_QUANTUM). This can't be the |
57 | * start of a group in the sense we described above (covering a power of two |
58 | * range) since, if we divided into it to pick a value of delta, we'd get a |
59 | * delta smaller than (1 << LG_QUANTUM) for sizes >= (1 << LG_QUANTUM), which |
60 | * is against the rules. |
61 | * |
62 | * The first base we can divide by SC_NGROUP while still being at least |
63 | * (1 << LG_QUANTUM) is SC_NGROUP * (1 << LG_QUANTUM). We can get there by |
64 | * having SC_NGROUP size classes, spaced (1 << LG_QUANTUM) apart. These size |
65 | * classes are: |
66 | * 1 * (1 << LG_QUANTUM) |
67 | * 2 * (1 << LG_QUANTUM) |
68 | * 3 * (1 << LG_QUANTUM) |
69 | * ... (although, as above, this "..." is empty in practice) |
70 | * SC_NGROUP * (1 << LG_QUANTUM). |
71 | * |
72 | * There are SC_NGROUP of these size classes, so we can regard it as a sort of |
73 | * pseudo-group, even though it spans multiple powers of 2, is divided |
74 | * differently, and both starts and ends on a power of 2 (as opposed to just |
75 | * ending). SC_NGROUP is itself a power of two, so the first group after the |
76 | * pseudo-group has the power-of-two base SC_NGROUP * (1 << LG_QUANTUM), for a |
77 | * lg_base of LG_QUANTUM + SC_LG_NGROUP. We can divide this base into SC_NGROUP |
78 | * sizes without violating our LG_QUANTUM requirements, so we can safely set |
79 | * lg_delta = lg_base - SC_LG_GROUP (== LG_QUANTUM). |
80 | * |
81 | * So, in order, the size classes are: |
82 | * |
83 | * Tiny size classes: |
84 | * - Count: LG_QUANTUM - SC_LG_TINY_MIN. |
85 | * - Sizes: |
86 | * 1 << SC_LG_TINY_MIN |
87 | * 1 << (SC_LG_TINY_MIN + 1) |
88 | * 1 << (SC_LG_TINY_MIN + 2) |
89 | * ... |
90 | * 1 << (LG_QUANTUM - 1) |
91 | * |
92 | * Initial pseudo-group: |
93 | * - Count: SC_NGROUP |
94 | * - Sizes: |
95 | * 1 * (1 << LG_QUANTUM) |
96 | * 2 * (1 << LG_QUANTUM) |
97 | * 3 * (1 << LG_QUANTUM) |
98 | * ... |
99 | * SC_NGROUP * (1 << LG_QUANTUM) |
100 | * |
101 | * Regular group 0: |
102 | * - Count: SC_NGROUP |
103 | * - Sizes: |
104 | * (relative to lg_base of LG_QUANTUM + SC_LG_NGROUP and lg_delta of |
105 | * lg_base - SC_LG_NGROUP) |
106 | * (1 << lg_base) + 1 * (1 << lg_delta) |
107 | * (1 << lg_base) + 2 * (1 << lg_delta) |
108 | * (1 << lg_base) + 3 * (1 << lg_delta) |
109 | * ... |
110 | * (1 << lg_base) + SC_NGROUP * (1 << lg_delta) [ == (1 << (lg_base + 1)) ] |
111 | * |
112 | * Regular group 1: |
113 | * - Count: SC_NGROUP |
114 | * - Sizes: |
115 | * (relative to lg_base of LG_QUANTUM + SC_LG_NGROUP + 1 and lg_delta of |
116 | * lg_base - SC_LG_NGROUP) |
117 | * (1 << lg_base) + 1 * (1 << lg_delta) |
118 | * (1 << lg_base) + 2 * (1 << lg_delta) |
119 | * (1 << lg_base) + 3 * (1 << lg_delta) |
120 | * ... |
121 | * (1 << lg_base) + SC_NGROUP * (1 << lg_delta) [ == (1 << (lg_base + 1)) ] |
122 | * |
123 | * ... |
124 | * |
125 | * Regular group N: |
126 | * - Count: SC_NGROUP |
127 | * - Sizes: |
128 | * (relative to lg_base of LG_QUANTUM + SC_LG_NGROUP + N and lg_delta of |
129 | * lg_base - SC_LG_NGROUP) |
130 | * (1 << lg_base) + 1 * (1 << lg_delta) |
131 | * (1 << lg_base) + 2 * (1 << lg_delta) |
132 | * (1 << lg_base) + 3 * (1 << lg_delta) |
133 | * ... |
134 | * (1 << lg_base) + SC_NGROUP * (1 << lg_delta) [ == (1 << (lg_base + 1)) ] |
135 | * |
136 | * |
137 | * Representation of metadata: |
138 | * To make the math easy, we'll mostly work in lg quantities. We record lg_base, |
139 | * lg_delta, and ndelta (i.e. number of deltas above the base) on a |
140 | * per-size-class basis, and maintain the invariant that, across all size |
141 | * classes, size == (1 << lg_base) + ndelta * (1 << lg_delta). |
142 | * |
143 | * For regular groups (i.e. those with lg_base >= LG_QUANTUM + SC_LG_NGROUP), |
144 | * lg_delta is lg_base - SC_LG_NGROUP, and ndelta goes from 1 to SC_NGROUP. |
145 | * |
146 | * For the initial tiny size classes (if any), lg_base is lg(size class size). |
147 | * lg_delta is lg_base for the first size class, and lg_base - 1 for all |
148 | * subsequent ones. ndelta is always 0. |
149 | * |
150 | * For the pseudo-group, if there are no tiny size classes, then we set |
151 | * lg_base == LG_QUANTUM, lg_delta == LG_QUANTUM, and have ndelta range from 0 |
152 | * to SC_NGROUP - 1. (Note that delta == base, so base + (SC_NGROUP - 1) * delta |
153 | * is just SC_NGROUP * base, or (1 << (SC_LG_NGROUP + LG_QUANTUM)), so we do |
154 | * indeed get a power of two that way). If there *are* tiny size classes, then |
155 | * the first size class needs to have lg_delta relative to the largest tiny size |
156 | * class. We therefore set lg_base == LG_QUANTUM - 1, |
157 | * lg_delta == LG_QUANTUM - 1, and ndelta == 1, keeping the rest of the |
158 | * pseudo-group the same. |
159 | * |
160 | * |
161 | * Other terminology: |
162 | * "Small" size classes mean those that are allocated out of bins, which is the |
163 | * same as those that are slab allocated. |
164 | * "Large" size classes are those that are not small. The cutoff for counting as |
165 | * large is page size * group size. |
166 | */ |
167 | |
168 | /* |
169 | * Size class N + (1 << SC_LG_NGROUP) twice the size of size class N. |
170 | */ |
171 | #define SC_LG_NGROUP 2 |
172 | #define SC_LG_TINY_MIN 3 |
173 | |
174 | #if SC_LG_TINY_MIN == 0 |
175 | /* The div module doesn't support division by 1, which this would require. */ |
176 | #error "Unsupported LG_TINY_MIN" |
177 | #endif |
178 | |
179 | /* |
180 | * The definitions below are all determined by the above settings and system |
181 | * characteristics. |
182 | */ |
183 | #define SC_NGROUP (1ULL << SC_LG_NGROUP) |
184 | #define SC_PTR_BITS ((1ULL << LG_SIZEOF_PTR) * 8) |
185 | #define SC_NTINY (LG_QUANTUM - SC_LG_TINY_MIN) |
186 | #define SC_LG_TINY_MAXCLASS (LG_QUANTUM > SC_LG_TINY_MIN ? LG_QUANTUM - 1 : -1) |
187 | #define SC_NPSEUDO SC_NGROUP |
188 | #define SC_LG_FIRST_REGULAR_BASE (LG_QUANTUM + SC_LG_NGROUP) |
189 | /* |
190 | * We cap allocations to be less than 2 ** (ptr_bits - 1), so the highest base |
191 | * we need is 2 ** (ptr_bits - 2). (This also means that the last group is 1 |
192 | * size class shorter than the others). |
193 | * We could probably save some space in arenas by capping this at LG_VADDR size. |
194 | */ |
195 | #define SC_LG_BASE_MAX (SC_PTR_BITS - 2) |
196 | #define SC_NREGULAR (SC_NGROUP * \ |
197 | (SC_LG_BASE_MAX - SC_LG_FIRST_REGULAR_BASE + 1) - 1) |
198 | #define SC_NSIZES (SC_NTINY + SC_NPSEUDO + SC_NREGULAR) |
199 | |
200 | /* |
201 | * The number of size classes that are a multiple of the page size. |
202 | * |
203 | * Here are the first few bases that have a page-sized SC. |
204 | * |
205 | * lg(base) | base | highest SC | page-multiple SCs |
206 | * --------------|------------------------------------------ |
207 | * LG_PAGE - 1 | PAGE / 2 | PAGE | 1 |
208 | * LG_PAGE | PAGE | 2 * PAGE | 1 |
209 | * LG_PAGE + 1 | 2 * PAGE | 4 * PAGE | 2 |
210 | * LG_PAGE + 2 | 4 * PAGE | 8 * PAGE | 4 |
211 | * |
212 | * The number of page-multiple SCs continues to grow in powers of two, up until |
213 | * lg_delta == lg_page, which corresponds to setting lg_base to lg_page + |
214 | * SC_LG_NGROUP. So, then, the number of size classes that are multiples of the |
215 | * page size whose lg_delta is less than the page size are |
216 | * is 1 + (2**0 + 2**1 + ... + 2**(lg_ngroup - 1) == 2**lg_ngroup. |
217 | * |
218 | * For each base with lg_base in [lg_page + lg_ngroup, lg_base_max), there are |
219 | * NGROUP page-sized size classes, and when lg_base == lg_base_max, there are |
220 | * NGROUP - 1. |
221 | * |
222 | * This gives us the quantity we seek. |
223 | */ |
224 | #define SC_NPSIZES ( \ |
225 | SC_NGROUP \ |
226 | + (SC_LG_BASE_MAX - (LG_PAGE + SC_LG_NGROUP)) * SC_NGROUP \ |
227 | + SC_NGROUP - 1) |
228 | |
229 | /* |
230 | * We declare a size class is binnable if size < page size * group. Or, in other |
231 | * words, lg(size) < lg(page size) + lg(group size). |
232 | */ |
233 | #define SC_NBINS ( \ |
234 | /* Sub-regular size classes. */ \ |
235 | SC_NTINY + SC_NPSEUDO \ |
236 | /* Groups with lg_regular_min_base <= lg_base <= lg_base_max */ \ |
237 | + SC_NGROUP * (LG_PAGE + SC_LG_NGROUP - SC_LG_FIRST_REGULAR_BASE) \ |
238 | /* Last SC of the last group hits the bound exactly; exclude it. */ \ |
239 | - 1) |
240 | |
241 | /* |
242 | * The size2index_tab lookup table uses uint8_t to encode each bin index, so we |
243 | * cannot support more than 256 small size classes. |
244 | */ |
245 | #if (SC_NBINS > 256) |
246 | # error "Too many small size classes" |
247 | #endif |
248 | |
249 | /* The largest size class in the lookup table, and its binary log. */ |
250 | #define SC_LG_MAX_LOOKUP 12 |
251 | #define SC_LOOKUP_MAXCLASS (1 << SC_LG_MAX_LOOKUP) |
252 | |
253 | /* Internal, only used for the definition of SC_SMALL_MAXCLASS. */ |
254 | #define SC_SMALL_MAX_BASE (1 << (LG_PAGE + SC_LG_NGROUP - 1)) |
255 | #define SC_SMALL_MAX_DELTA (1 << (LG_PAGE - 1)) |
256 | |
257 | /* The largest size class allocated out of a slab. */ |
258 | #define SC_SMALL_MAXCLASS (SC_SMALL_MAX_BASE \ |
259 | + (SC_NGROUP - 1) * SC_SMALL_MAX_DELTA) |
260 | |
261 | /* The fastpath assumes all lookup-able sizes are small. */ |
262 | #if (SC_SMALL_MAXCLASS < SC_LOOKUP_MAXCLASS) |
263 | # error "Lookup table sizes must be small" |
264 | #endif |
265 | |
266 | /* The smallest size class not allocated out of a slab. */ |
267 | #define SC_LARGE_MINCLASS ((size_t)1ULL << (LG_PAGE + SC_LG_NGROUP)) |
268 | #define SC_LG_LARGE_MINCLASS (LG_PAGE + SC_LG_NGROUP) |
269 | |
270 | /* Internal; only used for the definition of SC_LARGE_MAXCLASS. */ |
271 | #define SC_MAX_BASE ((size_t)1 << (SC_PTR_BITS - 2)) |
272 | #define SC_MAX_DELTA ((size_t)1 << (SC_PTR_BITS - 2 - SC_LG_NGROUP)) |
273 | |
274 | /* The largest size class supported. */ |
275 | #define SC_LARGE_MAXCLASS (SC_MAX_BASE + (SC_NGROUP - 1) * SC_MAX_DELTA) |
276 | |
277 | /* Maximum number of regions in one slab. */ |
278 | #ifndef CONFIG_LG_SLAB_MAXREGS |
279 | # define SC_LG_SLAB_MAXREGS (LG_PAGE - SC_LG_TINY_MIN) |
280 | #else |
281 | # if CONFIG_LG_SLAB_MAXREGS < (LG_PAGE - SC_LG_TINY_MIN) |
282 | # error "Unsupported SC_LG_SLAB_MAXREGS" |
283 | # else |
284 | # define SC_LG_SLAB_MAXREGS CONFIG_LG_SLAB_MAXREGS |
285 | # endif |
286 | #endif |
287 | |
288 | #define SC_SLAB_MAXREGS (1U << SC_LG_SLAB_MAXREGS) |
289 | |
290 | typedef struct sc_s sc_t; |
291 | struct sc_s { |
292 | /* Size class index, or -1 if not a valid size class. */ |
293 | int index; |
294 | /* Lg group base size (no deltas added). */ |
295 | int lg_base; |
296 | /* Lg delta to previous size class. */ |
297 | int lg_delta; |
298 | /* Delta multiplier. size == 1<<lg_base + ndelta<<lg_delta */ |
299 | int ndelta; |
300 | /* |
301 | * True if the size class is a multiple of the page size, false |
302 | * otherwise. |
303 | */ |
304 | bool psz; |
305 | /* |
306 | * True if the size class is a small, bin, size class. False otherwise. |
307 | */ |
308 | bool bin; |
309 | /* The slab page count if a small bin size class, 0 otherwise. */ |
310 | int pgs; |
311 | /* Same as lg_delta if a lookup table size class, 0 otherwise. */ |
312 | int lg_delta_lookup; |
313 | }; |
314 | |
315 | typedef struct sc_data_s sc_data_t; |
316 | struct sc_data_s { |
317 | /* Number of tiny size classes. */ |
318 | unsigned ntiny; |
319 | /* Number of bins supported by the lookup table. */ |
320 | int nlbins; |
321 | /* Number of small size class bins. */ |
322 | int nbins; |
323 | /* Number of size classes. */ |
324 | int nsizes; |
325 | /* Number of bits required to store NSIZES. */ |
326 | int lg_ceil_nsizes; |
327 | /* Number of size classes that are a multiple of (1U << LG_PAGE). */ |
328 | unsigned npsizes; |
329 | /* Lg of maximum tiny size class (or -1, if none). */ |
330 | int lg_tiny_maxclass; |
331 | /* Maximum size class included in lookup table. */ |
332 | size_t lookup_maxclass; |
333 | /* Maximum small size class. */ |
334 | size_t small_maxclass; |
335 | /* Lg of minimum large size class. */ |
336 | int lg_large_minclass; |
337 | /* The minimum large size class. */ |
338 | size_t large_minclass; |
339 | /* Maximum (large) size class. */ |
340 | size_t large_maxclass; |
341 | /* True if the sc_data_t has been initialized (for debugging only). */ |
342 | bool initialized; |
343 | |
344 | sc_t sc[SC_NSIZES]; |
345 | }; |
346 | |
347 | size_t reg_size_compute(int lg_base, int lg_delta, int ndelta); |
348 | void sc_data_init(sc_data_t *data); |
349 | /* |
350 | * Updates slab sizes in [begin, end] to be pgs pages in length, if possible. |
351 | * Otherwise, does its best to accommodate the request. |
352 | */ |
353 | void sc_data_update_slab_size(sc_data_t *data, size_t begin, size_t end, |
354 | int pgs); |
355 | void sc_boot(sc_data_t *data); |
356 | |
357 | #endif /* JEMALLOC_INTERNAL_SC_H */ |
358 | |