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 | /* The number of size classes that are a multiple of the page size. */ |
201 | #define SC_NPSIZES ( \ |
202 | /* Start with all the size classes. */ \ |
203 | SC_NSIZES \ |
204 | /* Subtract out those groups with too small a base. */ \ |
205 | - (LG_PAGE - 1 - SC_LG_FIRST_REGULAR_BASE) * SC_NGROUP \ |
206 | /* And the pseudo-group. */ \ |
207 | - SC_NPSEUDO \ |
208 | /* And the tiny group. */ \ |
209 | - SC_NTINY \ |
210 | /* Sizes where ndelta*delta is not a multiple of the page size. */ \ |
211 | - (SC_LG_NGROUP * SC_NGROUP)) |
212 | /* |
213 | * Note that the last line is computed as the sum of the second column in the |
214 | * following table: |
215 | * lg(base) | count of sizes to exclude |
216 | * ------------------------------|----------------------------- |
217 | * LG_PAGE - 1 | SC_NGROUP - 1 |
218 | * LG_PAGE | SC_NGROUP - 1 |
219 | * LG_PAGE + 1 | SC_NGROUP - 2 |
220 | * LG_PAGE + 2 | SC_NGROUP - 4 |
221 | * ... | ... |
222 | * LG_PAGE + (SC_LG_NGROUP - 1) | SC_NGROUP - (SC_NGROUP / 2) |
223 | */ |
224 | |
225 | /* |
226 | * We declare a size class is binnable if size < page size * group. Or, in other |
227 | * words, lg(size) < lg(page size) + lg(group size). |
228 | */ |
229 | #define SC_NBINS ( \ |
230 | /* Sub-regular size classes. */ \ |
231 | SC_NTINY + SC_NPSEUDO \ |
232 | /* Groups with lg_regular_min_base <= lg_base <= lg_base_max */ \ |
233 | + SC_NGROUP * (LG_PAGE + SC_LG_NGROUP - SC_LG_FIRST_REGULAR_BASE) \ |
234 | /* Last SC of the last group hits the bound exactly; exclude it. */ \ |
235 | - 1) |
236 | |
237 | /* |
238 | * The size2index_tab lookup table uses uint8_t to encode each bin index, so we |
239 | * cannot support more than 256 small size classes. |
240 | */ |
241 | #if (SC_NBINS > 256) |
242 | # error "Too many small size classes" |
243 | #endif |
244 | |
245 | /* The largest size class in the lookup table. */ |
246 | #define SC_LOOKUP_MAXCLASS ((size_t)1 << 12) |
247 | |
248 | /* Internal, only used for the definition of SC_SMALL_MAXCLASS. */ |
249 | #define SC_SMALL_MAX_BASE ((size_t)1 << (LG_PAGE + SC_LG_NGROUP - 1)) |
250 | #define SC_SMALL_MAX_DELTA ((size_t)1 << (LG_PAGE - 1)) |
251 | |
252 | /* The largest size class allocated out of a slab. */ |
253 | #define SC_SMALL_MAXCLASS (SC_SMALL_MAX_BASE \ |
254 | + (SC_NGROUP - 1) * SC_SMALL_MAX_DELTA) |
255 | |
256 | /* The smallest size class not allocated out of a slab. */ |
257 | #define SC_LARGE_MINCLASS ((size_t)1ULL << (LG_PAGE + SC_LG_NGROUP)) |
258 | #define SC_LG_LARGE_MINCLASS (LG_PAGE + SC_LG_NGROUP) |
259 | |
260 | /* Internal; only used for the definition of SC_LARGE_MAXCLASS. */ |
261 | #define SC_MAX_BASE ((size_t)1 << (SC_PTR_BITS - 2)) |
262 | #define SC_MAX_DELTA ((size_t)1 << (SC_PTR_BITS - 2 - SC_LG_NGROUP)) |
263 | |
264 | /* The largest size class supported. */ |
265 | #define SC_LARGE_MAXCLASS (SC_MAX_BASE + (SC_NGROUP - 1) * SC_MAX_DELTA) |
266 | |
267 | typedef struct sc_s sc_t; |
268 | struct sc_s { |
269 | /* Size class index, or -1 if not a valid size class. */ |
270 | int index; |
271 | /* Lg group base size (no deltas added). */ |
272 | int lg_base; |
273 | /* Lg delta to previous size class. */ |
274 | int lg_delta; |
275 | /* Delta multiplier. size == 1<<lg_base + ndelta<<lg_delta */ |
276 | int ndelta; |
277 | /* |
278 | * True if the size class is a multiple of the page size, false |
279 | * otherwise. |
280 | */ |
281 | bool psz; |
282 | /* |
283 | * True if the size class is a small, bin, size class. False otherwise. |
284 | */ |
285 | bool bin; |
286 | /* The slab page count if a small bin size class, 0 otherwise. */ |
287 | int pgs; |
288 | /* Same as lg_delta if a lookup table size class, 0 otherwise. */ |
289 | int lg_delta_lookup; |
290 | }; |
291 | |
292 | typedef struct sc_data_s sc_data_t; |
293 | struct sc_data_s { |
294 | /* Number of tiny size classes. */ |
295 | unsigned ntiny; |
296 | /* Number of bins supported by the lookup table. */ |
297 | int nlbins; |
298 | /* Number of small size class bins. */ |
299 | int nbins; |
300 | /* Number of size classes. */ |
301 | int nsizes; |
302 | /* Number of bits required to store NSIZES. */ |
303 | int lg_ceil_nsizes; |
304 | /* Number of size classes that are a multiple of (1U << LG_PAGE). */ |
305 | unsigned npsizes; |
306 | /* Lg of maximum tiny size class (or -1, if none). */ |
307 | int lg_tiny_maxclass; |
308 | /* Maximum size class included in lookup table. */ |
309 | size_t lookup_maxclass; |
310 | /* Maximum small size class. */ |
311 | size_t small_maxclass; |
312 | /* Lg of minimum large size class. */ |
313 | int lg_large_minclass; |
314 | /* The minimum large size class. */ |
315 | size_t large_minclass; |
316 | /* Maximum (large) size class. */ |
317 | size_t large_maxclass; |
318 | /* True if the sc_data_t has been initialized (for debugging only). */ |
319 | bool initialized; |
320 | |
321 | sc_t sc[SC_NSIZES]; |
322 | }; |
323 | |
324 | void sc_data_init(sc_data_t *data); |
325 | /* |
326 | * Updates slab sizes in [begin, end] to be pgs pages in length, if possible. |
327 | * Otherwise, does its best to accomodate the request. |
328 | */ |
329 | void sc_data_update_slab_size(sc_data_t *data, size_t begin, size_t end, |
330 | int pgs); |
331 | void sc_boot(sc_data_t *data); |
332 | |
333 | #endif /* JEMALLOC_INTERNAL_SC_H */ |
334 | |