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. */ |
26 | typedef unsigned pszind_t; |
27 | |
28 | /* Size class index type. */ |
29 | typedef unsigned szind_t; |
30 | |
31 | /* |
32 | * sz_pind2sz_tab encodes the same information as could be computed by |
33 | * sz_pind2sz_compute(). |
34 | */ |
35 | extern 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 | */ |
40 | extern 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 | */ |
46 | extern 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 | */ |
52 | extern size_t sz_large_pad; |
53 | |
54 | extern void sz_boot(const sc_data_t *sc_data, bool cache_oblivious); |
55 | |
56 | JEMALLOC_ALWAYS_INLINE pszind_t |
57 | sz_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 | |
107 | static inline size_t |
108 | sz_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 | |
127 | static inline size_t |
128 | sz_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 | |
134 | static inline size_t |
135 | sz_pind2sz(pszind_t pind) { |
136 | assert(pind < SC_NPSIZES + 1); |
137 | return sz_pind2sz_lookup(pind); |
138 | } |
139 | |
140 | static inline size_t |
141 | sz_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 | |
154 | static inline szind_t |
155 | sz_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 | |
188 | JEMALLOC_ALWAYS_INLINE szind_t |
189 | sz_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 | |
195 | JEMALLOC_ALWAYS_INLINE szind_t |
196 | sz_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 | |
202 | JEMALLOC_ALWAYS_INLINE szind_t |
203 | sz_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 | |
210 | static inline size_t |
211 | sz_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 | |
236 | JEMALLOC_ALWAYS_INLINE size_t |
237 | sz_index2size_lookup_impl(szind_t index) { |
238 | return sz_index2size_tab[index]; |
239 | } |
240 | |
241 | JEMALLOC_ALWAYS_INLINE size_t |
242 | sz_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 | |
248 | JEMALLOC_ALWAYS_INLINE size_t |
249 | sz_index2size(szind_t index) { |
250 | assert(index < SC_NSIZES); |
251 | return sz_index2size_lookup(index); |
252 | } |
253 | |
254 | JEMALLOC_ALWAYS_INLINE void |
255 | sz_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 | |
260 | JEMALLOC_ALWAYS_INLINE size_t |
261 | sz_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 | |
288 | JEMALLOC_ALWAYS_INLINE size_t |
289 | sz_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 | */ |
300 | JEMALLOC_ALWAYS_INLINE size_t |
301 | sz_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 | */ |
312 | JEMALLOC_ALWAYS_INLINE size_t |
313 | sz_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 | |
368 | size_t sz_psz_quantize_floor(size_t size); |
369 | size_t sz_psz_quantize_ceil(size_t size); |
370 | |
371 | #endif /* JEMALLOC_INTERNAL_SIZE_H */ |
372 | |