1#ifndef JEMALLOC_INTERNAL_SIZE_H
2#define JEMALLOC_INTERNAL_SIZE_H
3
4#include "jemalloc/internal/bit_util.h"
5#include "jemalloc/internal/pages.h"
6#include "jemalloc/internal/sc.h"
7#include "jemalloc/internal/util.h"
8
9/*
10 * sz module: Size computations.
11 *
12 * Some abbreviations used here:
13 * p: Page
14 * ind: Index
15 * s, sz: Size
16 * u: Usable size
17 * a: Aligned
18 *
19 * These are not always used completely consistently, but should be enough to
20 * interpret function names. E.g. sz_psz2ind converts page size to page size
21 * index; sz_sa2u converts a (size, alignment) allocation request to the usable
22 * size that would result from such an allocation.
23 */
24
25/* Page size index type. */
26typedef unsigned pszind_t;
27
28/* Size class index type. */
29typedef unsigned szind_t;
30
31/*
32 * sz_pind2sz_tab encodes the same information as could be computed by
33 * sz_pind2sz_compute().
34 */
35extern size_t sz_pind2sz_tab[SC_NPSIZES + 1];
36/*
37 * sz_index2size_tab encodes the same information as could be computed (at
38 * unacceptable cost in some code paths) by sz_index2size_compute().
39 */
40extern size_t sz_index2size_tab[SC_NSIZES];
41/*
42 * sz_size2index_tab is a compact lookup table that rounds request sizes up to
43 * size classes. In order to reduce cache footprint, the table is compressed,
44 * and all accesses are via sz_size2index().
45 */
46extern uint8_t sz_size2index_tab[];
47
48/*
49 * Padding for large allocations: PAGE when opt_cache_oblivious == true (to
50 * enable cache index randomization); 0 otherwise.
51 */
52extern size_t sz_large_pad;
53
54extern void sz_boot(const sc_data_t *sc_data, bool cache_oblivious);
55
56JEMALLOC_ALWAYS_INLINE pszind_t
57sz_psz2ind(size_t psz) {
58 assert(psz > 0);
59 if (unlikely(psz > SC_LARGE_MAXCLASS)) {
60 return SC_NPSIZES;
61 }
62 /* x is the lg of the first base >= psz. */
63 pszind_t x = lg_ceil(psz);
64 /*
65 * sc.h introduces a lot of size classes. These size classes are divided
66 * into different size class groups. There is a very special size class
67 * group, each size class in or after it is an integer multiple of PAGE.
68 * We call it first_ps_rg. It means first page size regular group. The
69 * range of first_ps_rg is (base, base * 2], and base == PAGE *
70 * SC_NGROUP. off_to_first_ps_rg begins from 1, instead of 0. e.g.
71 * off_to_first_ps_rg is 1 when psz is (PAGE * SC_NGROUP + 1).
72 */
73 pszind_t off_to_first_ps_rg = (x < SC_LG_NGROUP + LG_PAGE) ?
74 0 : x - (SC_LG_NGROUP + LG_PAGE);
75
76 /*
77 * Same as sc_s::lg_delta.
78 * Delta for off_to_first_ps_rg == 1 is PAGE,
79 * for each increase in offset, it's multiplied by two.
80 * Therefore, lg_delta = LG_PAGE + (off_to_first_ps_rg - 1).
81 */
82 pszind_t lg_delta = (off_to_first_ps_rg == 0) ?
83 LG_PAGE : LG_PAGE + (off_to_first_ps_rg - 1);
84
85 /*
86 * Let's write psz in binary, e.g. 0011 for 0x3, 0111 for 0x7.
87 * The leftmost bits whose len is lg_base decide the base of psz.
88 * The rightmost bits whose len is lg_delta decide (pgz % PAGE).
89 * The middle bits whose len is SC_LG_NGROUP decide ndelta.
90 * ndelta is offset to the first size class in the size class group,
91 * starts from 1.
92 * If you don't know lg_base, ndelta or lg_delta, see sc.h.
93 * |xxxxxxxxxxxxxxxxxxxx|------------------------|yyyyyyyyyyyyyyyyyyyyy|
94 * |<-- len: lg_base -->|<-- len: SC_LG_NGROUP-->|<-- len: lg_delta -->|
95 * |<-- ndelta -->|
96 * rg_inner_off = ndelta - 1
97 * Why use (psz - 1)?
98 * To handle case: psz % (1 << lg_delta) == 0.
99 */
100 pszind_t rg_inner_off = (((psz - 1)) >> lg_delta) & (SC_NGROUP - 1);
101
102 pszind_t base_ind = off_to_first_ps_rg << SC_LG_NGROUP;
103 pszind_t ind = base_ind + rg_inner_off;
104 return ind;
105}
106
107static inline size_t
108sz_pind2sz_compute(pszind_t pind) {
109 if (unlikely(pind == SC_NPSIZES)) {
110 return SC_LARGE_MAXCLASS + PAGE;
111 }
112 size_t grp = pind >> SC_LG_NGROUP;
113 size_t mod = pind & ((ZU(1) << SC_LG_NGROUP) - 1);
114
115 size_t grp_size_mask = ~((!!grp)-1);
116 size_t grp_size = ((ZU(1) << (LG_PAGE + (SC_LG_NGROUP-1))) << grp)
117 & grp_size_mask;
118
119 size_t shift = (grp == 0) ? 1 : grp;
120 size_t lg_delta = shift + (LG_PAGE-1);
121 size_t mod_size = (mod+1) << lg_delta;
122
123 size_t sz = grp_size + mod_size;
124 return sz;
125}
126
127static inline size_t
128sz_pind2sz_lookup(pszind_t pind) {
129 size_t ret = (size_t)sz_pind2sz_tab[pind];
130 assert(ret == sz_pind2sz_compute(pind));
131 return ret;
132}
133
134static inline size_t
135sz_pind2sz(pszind_t pind) {
136 assert(pind < SC_NPSIZES + 1);
137 return sz_pind2sz_lookup(pind);
138}
139
140static inline size_t
141sz_psz2u(size_t psz) {
142 if (unlikely(psz > SC_LARGE_MAXCLASS)) {
143 return SC_LARGE_MAXCLASS + PAGE;
144 }
145 size_t x = lg_floor((psz<<1)-1);
146 size_t lg_delta = (x < SC_LG_NGROUP + LG_PAGE + 1) ?
147 LG_PAGE : x - SC_LG_NGROUP - 1;
148 size_t delta = ZU(1) << lg_delta;
149 size_t delta_mask = delta - 1;
150 size_t usize = (psz + delta_mask) & ~delta_mask;
151 return usize;
152}
153
154static inline szind_t
155sz_size2index_compute(size_t size) {
156 if (unlikely(size > SC_LARGE_MAXCLASS)) {
157 return SC_NSIZES;
158 }
159
160 if (size == 0) {
161 return 0;
162 }
163#if (SC_NTINY != 0)
164 if (size <= (ZU(1) << SC_LG_TINY_MAXCLASS)) {
165 szind_t lg_tmin = SC_LG_TINY_MAXCLASS - SC_NTINY + 1;
166 szind_t lg_ceil = lg_floor(pow2_ceil_zu(size));
167 return (lg_ceil < lg_tmin ? 0 : lg_ceil - lg_tmin);
168 }
169#endif
170 {
171 szind_t x = lg_floor((size<<1)-1);
172 szind_t shift = (x < SC_LG_NGROUP + LG_QUANTUM) ? 0 :
173 x - (SC_LG_NGROUP + LG_QUANTUM);
174 szind_t grp = shift << SC_LG_NGROUP;
175
176 szind_t lg_delta = (x < SC_LG_NGROUP + LG_QUANTUM + 1)
177 ? LG_QUANTUM : x - SC_LG_NGROUP - 1;
178
179 size_t delta_inverse_mask = ZU(-1) << lg_delta;
180 szind_t mod = ((((size-1) & delta_inverse_mask) >> lg_delta)) &
181 ((ZU(1) << SC_LG_NGROUP) - 1);
182
183 szind_t index = SC_NTINY + grp + mod;
184 return index;
185 }
186}
187
188JEMALLOC_ALWAYS_INLINE szind_t
189sz_size2index_lookup_impl(size_t size) {
190 assert(size <= SC_LOOKUP_MAXCLASS);
191 return sz_size2index_tab[(size + (ZU(1) << SC_LG_TINY_MIN) - 1)
192 >> SC_LG_TINY_MIN];
193}
194
195JEMALLOC_ALWAYS_INLINE szind_t
196sz_size2index_lookup(size_t size) {
197 szind_t ret = sz_size2index_lookup_impl(size);
198 assert(ret == sz_size2index_compute(size));
199 return ret;
200}
201
202JEMALLOC_ALWAYS_INLINE szind_t
203sz_size2index(size_t size) {
204 if (likely(size <= SC_LOOKUP_MAXCLASS)) {
205 return sz_size2index_lookup(size);
206 }
207 return sz_size2index_compute(size);
208}
209
210static inline size_t
211sz_index2size_compute(szind_t index) {
212#if (SC_NTINY > 0)
213 if (index < SC_NTINY) {
214 return (ZU(1) << (SC_LG_TINY_MAXCLASS - SC_NTINY + 1 + index));
215 }
216#endif
217 {
218 size_t reduced_index = index - SC_NTINY;
219 size_t grp = reduced_index >> SC_LG_NGROUP;
220 size_t mod = reduced_index & ((ZU(1) << SC_LG_NGROUP) -
221 1);
222
223 size_t grp_size_mask = ~((!!grp)-1);
224 size_t grp_size = ((ZU(1) << (LG_QUANTUM +
225 (SC_LG_NGROUP-1))) << grp) & grp_size_mask;
226
227 size_t shift = (grp == 0) ? 1 : grp;
228 size_t lg_delta = shift + (LG_QUANTUM-1);
229 size_t mod_size = (mod+1) << lg_delta;
230
231 size_t usize = grp_size + mod_size;
232 return usize;
233 }
234}
235
236JEMALLOC_ALWAYS_INLINE size_t
237sz_index2size_lookup_impl(szind_t index) {
238 return sz_index2size_tab[index];
239}
240
241JEMALLOC_ALWAYS_INLINE size_t
242sz_index2size_lookup(szind_t index) {
243 size_t ret = sz_index2size_lookup_impl(index);
244 assert(ret == sz_index2size_compute(index));
245 return ret;
246}
247
248JEMALLOC_ALWAYS_INLINE size_t
249sz_index2size(szind_t index) {
250 assert(index < SC_NSIZES);
251 return sz_index2size_lookup(index);
252}
253
254JEMALLOC_ALWAYS_INLINE void
255sz_size2index_usize_fastpath(size_t size, szind_t *ind, size_t *usize) {
256 *ind = sz_size2index_lookup_impl(size);
257 *usize = sz_index2size_lookup_impl(*ind);
258}
259
260JEMALLOC_ALWAYS_INLINE size_t
261sz_s2u_compute(size_t size) {
262 if (unlikely(size > SC_LARGE_MAXCLASS)) {
263 return 0;
264 }
265
266 if (size == 0) {
267 size++;
268 }
269#if (SC_NTINY > 0)
270 if (size <= (ZU(1) << SC_LG_TINY_MAXCLASS)) {
271 size_t lg_tmin = SC_LG_TINY_MAXCLASS - SC_NTINY + 1;
272 size_t lg_ceil = lg_floor(pow2_ceil_zu(size));
273 return (lg_ceil < lg_tmin ? (ZU(1) << lg_tmin) :
274 (ZU(1) << lg_ceil));
275 }
276#endif
277 {
278 size_t x = lg_floor((size<<1)-1);
279 size_t lg_delta = (x < SC_LG_NGROUP + LG_QUANTUM + 1)
280 ? LG_QUANTUM : x - SC_LG_NGROUP - 1;
281 size_t delta = ZU(1) << lg_delta;
282 size_t delta_mask = delta - 1;
283 size_t usize = (size + delta_mask) & ~delta_mask;
284 return usize;
285 }
286}
287
288JEMALLOC_ALWAYS_INLINE size_t
289sz_s2u_lookup(size_t size) {
290 size_t ret = sz_index2size_lookup(sz_size2index_lookup(size));
291
292 assert(ret == sz_s2u_compute(size));
293 return ret;
294}
295
296/*
297 * Compute usable size that would result from allocating an object with the
298 * specified size.
299 */
300JEMALLOC_ALWAYS_INLINE size_t
301sz_s2u(size_t size) {
302 if (likely(size <= SC_LOOKUP_MAXCLASS)) {
303 return sz_s2u_lookup(size);
304 }
305 return sz_s2u_compute(size);
306}
307
308/*
309 * Compute usable size that would result from allocating an object with the
310 * specified size and alignment.
311 */
312JEMALLOC_ALWAYS_INLINE size_t
313sz_sa2u(size_t size, size_t alignment) {
314 size_t usize;
315
316 assert(alignment != 0 && ((alignment - 1) & alignment) == 0);
317
318 /* Try for a small size class. */
319 if (size <= SC_SMALL_MAXCLASS && alignment <= PAGE) {
320 /*
321 * Round size up to the nearest multiple of alignment.
322 *
323 * This done, we can take advantage of the fact that for each
324 * small size class, every object is aligned at the smallest
325 * power of two that is non-zero in the base two representation
326 * of the size. For example:
327 *
328 * Size | Base 2 | Minimum alignment
329 * -----+----------+------------------
330 * 96 | 1100000 | 32
331 * 144 | 10100000 | 32
332 * 192 | 11000000 | 64
333 */
334 usize = sz_s2u(ALIGNMENT_CEILING(size, alignment));
335 if (usize < SC_LARGE_MINCLASS) {
336 return usize;
337 }
338 }
339
340 /* Large size class. Beware of overflow. */
341
342 if (unlikely(alignment > SC_LARGE_MAXCLASS)) {
343 return 0;
344 }
345
346 /* Make sure result is a large size class. */
347 if (size <= SC_LARGE_MINCLASS) {
348 usize = SC_LARGE_MINCLASS;
349 } else {
350 usize = sz_s2u(size);
351 if (usize < size) {
352 /* size_t overflow. */
353 return 0;
354 }
355 }
356
357 /*
358 * Calculate the multi-page mapping that large_palloc() would need in
359 * order to guarantee the alignment.
360 */
361 if (usize + sz_large_pad + PAGE_CEILING(alignment) - PAGE < usize) {
362 /* size_t overflow. */
363 return 0;
364 }
365 return usize;
366}
367
368size_t sz_psz_quantize_floor(size_t size);
369size_t sz_psz_quantize_ceil(size_t size);
370
371#endif /* JEMALLOC_INTERNAL_SIZE_H */
372