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
267typedef struct sc_s sc_t;
268struct 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
292typedef struct sc_data_s sc_data_t;
293struct 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
324void 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 */
329void sc_data_update_slab_size(sc_data_t *data, size_t begin, size_t end,
330 int pgs);
331void sc_boot(sc_data_t *data);
332
333#endif /* JEMALLOC_INTERNAL_SC_H */
334