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/*
26 * sz_pind2sz_tab encodes the same information as could be computed by
27 * sz_pind2sz_compute().
28 */
29extern size_t sz_pind2sz_tab[SC_NPSIZES + 1];
30/*
31 * sz_index2size_tab encodes the same information as could be computed (at
32 * unacceptable cost in some code paths) by sz_index2size_compute().
33 */
34extern size_t sz_index2size_tab[SC_NSIZES];
35/*
36 * sz_size2index_tab is a compact lookup table that rounds request sizes up to
37 * size classes.  In order to reduce cache footprint, the table is compressed,
38 * and all accesses are via sz_size2index().
39 */
40extern uint8_t sz_size2index_tab[];
41
42static const size_t sz_large_pad =
43#ifdef JEMALLOC_CACHE_OBLIVIOUS
44    PAGE
45#else
46    0
47#endif
48    ;
49
50extern void sz_boot(const sc_data_t *sc_data);
51
52JEMALLOC_ALWAYS_INLINE pszind_t
53sz_psz2ind(size_t psz) {
54	if (unlikely(psz > SC_LARGE_MAXCLASS)) {
55		return SC_NPSIZES;
56	}
57	pszind_t x = lg_floor((psz<<1)-1);
58	pszind_t shift = (x < SC_LG_NGROUP + LG_PAGE) ?
59	    0 : x - (SC_LG_NGROUP + LG_PAGE);
60	pszind_t grp = shift << SC_LG_NGROUP;
61
62	pszind_t lg_delta = (x < SC_LG_NGROUP + LG_PAGE + 1) ?
63	    LG_PAGE : x - SC_LG_NGROUP - 1;
64
65	size_t delta_inverse_mask = ZU(-1) << lg_delta;
66	pszind_t mod = ((((psz-1) & delta_inverse_mask) >> lg_delta)) &
67	    ((ZU(1) << SC_LG_NGROUP) - 1);
68
69	pszind_t ind = grp + mod;
70	return ind;
71}
72
73static inline size_t
74sz_pind2sz_compute(pszind_t pind) {
75	if (unlikely(pind == SC_NPSIZES)) {
76		return SC_LARGE_MAXCLASS + PAGE;
77	}
78	size_t grp = pind >> SC_LG_NGROUP;
79	size_t mod = pind & ((ZU(1) << SC_LG_NGROUP) - 1);
80
81	size_t grp_size_mask = ~((!!grp)-1);
82	size_t grp_size = ((ZU(1) << (LG_PAGE + (SC_LG_NGROUP-1))) << grp)
83	    & grp_size_mask;
84
85	size_t shift = (grp == 0) ? 1 : grp;
86	size_t lg_delta = shift + (LG_PAGE-1);
87	size_t mod_size = (mod+1) << lg_delta;
88
89	size_t sz = grp_size + mod_size;
90	return sz;
91}
92
93static inline size_t
94sz_pind2sz_lookup(pszind_t pind) {
95	size_t ret = (size_t)sz_pind2sz_tab[pind];
96	assert(ret == sz_pind2sz_compute(pind));
97	return ret;
98}
99
100static inline size_t
101sz_pind2sz(pszind_t pind) {
102	assert(pind < SC_NPSIZES + 1);
103	return sz_pind2sz_lookup(pind);
104}
105
106static inline size_t
107sz_psz2u(size_t psz) {
108	if (unlikely(psz > SC_LARGE_MAXCLASS)) {
109		return SC_LARGE_MAXCLASS + PAGE;
110	}
111	size_t x = lg_floor((psz<<1)-1);
112	size_t lg_delta = (x < SC_LG_NGROUP + LG_PAGE + 1) ?
113	    LG_PAGE : x - SC_LG_NGROUP - 1;
114	size_t delta = ZU(1) << lg_delta;
115	size_t delta_mask = delta - 1;
116	size_t usize = (psz + delta_mask) & ~delta_mask;
117	return usize;
118}
119
120static inline szind_t
121sz_size2index_compute(size_t size) {
122	if (unlikely(size > SC_LARGE_MAXCLASS)) {
123		return SC_NSIZES;
124	}
125
126	if (size == 0) {
127		return 0;
128	}
129#if (SC_NTINY != 0)
130	if (size <= (ZU(1) << SC_LG_TINY_MAXCLASS)) {
131		szind_t lg_tmin = SC_LG_TINY_MAXCLASS - SC_NTINY + 1;
132		szind_t lg_ceil = lg_floor(pow2_ceil_zu(size));
133		return (lg_ceil < lg_tmin ? 0 : lg_ceil - lg_tmin);
134	}
135#endif
136	{
137		szind_t x = lg_floor((size<<1)-1);
138		szind_t shift = (x < SC_LG_NGROUP + LG_QUANTUM) ? 0 :
139		    x - (SC_LG_NGROUP + LG_QUANTUM);
140		szind_t grp = shift << SC_LG_NGROUP;
141
142		szind_t lg_delta = (x < SC_LG_NGROUP + LG_QUANTUM + 1)
143		    ? LG_QUANTUM : x - SC_LG_NGROUP - 1;
144
145		size_t delta_inverse_mask = ZU(-1) << lg_delta;
146		szind_t mod = ((((size-1) & delta_inverse_mask) >> lg_delta)) &
147		    ((ZU(1) << SC_LG_NGROUP) - 1);
148
149		szind_t index = SC_NTINY + grp + mod;
150		return index;
151	}
152}
153
154JEMALLOC_ALWAYS_INLINE szind_t
155sz_size2index_lookup(size_t size) {
156	assert(size <= SC_LOOKUP_MAXCLASS);
157	szind_t ret = (sz_size2index_tab[(size + (ZU(1) << SC_LG_TINY_MIN) - 1)
158					 >> SC_LG_TINY_MIN]);
159	assert(ret == sz_size2index_compute(size));
160	return ret;
161}
162
163JEMALLOC_ALWAYS_INLINE szind_t
164sz_size2index(size_t size) {
165	if (likely(size <= SC_LOOKUP_MAXCLASS)) {
166		return sz_size2index_lookup(size);
167	}
168	return sz_size2index_compute(size);
169}
170
171static inline size_t
172sz_index2size_compute(szind_t index) {
173#if (SC_NTINY > 0)
174	if (index < SC_NTINY) {
175		return (ZU(1) << (SC_LG_TINY_MAXCLASS - SC_NTINY + 1 + index));
176	}
177#endif
178	{
179		size_t reduced_index = index - SC_NTINY;
180		size_t grp = reduced_index >> SC_LG_NGROUP;
181		size_t mod = reduced_index & ((ZU(1) << SC_LG_NGROUP) -
182		    1);
183
184		size_t grp_size_mask = ~((!!grp)-1);
185		size_t grp_size = ((ZU(1) << (LG_QUANTUM +
186		    (SC_LG_NGROUP-1))) << grp) & grp_size_mask;
187
188		size_t shift = (grp == 0) ? 1 : grp;
189		size_t lg_delta = shift + (LG_QUANTUM-1);
190		size_t mod_size = (mod+1) << lg_delta;
191
192		size_t usize = grp_size + mod_size;
193		return usize;
194	}
195}
196
197JEMALLOC_ALWAYS_INLINE size_t
198sz_index2size_lookup(szind_t index) {
199	size_t ret = (size_t)sz_index2size_tab[index];
200	assert(ret == sz_index2size_compute(index));
201	return ret;
202}
203
204JEMALLOC_ALWAYS_INLINE size_t
205sz_index2size(szind_t index) {
206	assert(index < SC_NSIZES);
207	return sz_index2size_lookup(index);
208}
209
210JEMALLOC_ALWAYS_INLINE size_t
211sz_s2u_compute(size_t size) {
212	if (unlikely(size > SC_LARGE_MAXCLASS)) {
213		return 0;
214	}
215
216	if (size == 0) {
217		size++;
218	}
219#if (SC_NTINY > 0)
220	if (size <= (ZU(1) << SC_LG_TINY_MAXCLASS)) {
221		size_t lg_tmin = SC_LG_TINY_MAXCLASS - SC_NTINY + 1;
222		size_t lg_ceil = lg_floor(pow2_ceil_zu(size));
223		return (lg_ceil < lg_tmin ? (ZU(1) << lg_tmin) :
224		    (ZU(1) << lg_ceil));
225	}
226#endif
227	{
228		size_t x = lg_floor((size<<1)-1);
229		size_t lg_delta = (x < SC_LG_NGROUP + LG_QUANTUM + 1)
230		    ?  LG_QUANTUM : x - SC_LG_NGROUP - 1;
231		size_t delta = ZU(1) << lg_delta;
232		size_t delta_mask = delta - 1;
233		size_t usize = (size + delta_mask) & ~delta_mask;
234		return usize;
235	}
236}
237
238JEMALLOC_ALWAYS_INLINE size_t
239sz_s2u_lookup(size_t size) {
240	size_t ret = sz_index2size_lookup(sz_size2index_lookup(size));
241
242	assert(ret == sz_s2u_compute(size));
243	return ret;
244}
245
246/*
247 * Compute usable size that would result from allocating an object with the
248 * specified size.
249 */
250JEMALLOC_ALWAYS_INLINE size_t
251sz_s2u(size_t size) {
252	if (likely(size <= SC_LOOKUP_MAXCLASS)) {
253		return sz_s2u_lookup(size);
254	}
255	return sz_s2u_compute(size);
256}
257
258/*
259 * Compute usable size that would result from allocating an object with the
260 * specified size and alignment.
261 */
262JEMALLOC_ALWAYS_INLINE size_t
263sz_sa2u(size_t size, size_t alignment) {
264	size_t usize;
265
266	assert(alignment != 0 && ((alignment - 1) & alignment) == 0);
267
268	/* Try for a small size class. */
269	if (size <= SC_SMALL_MAXCLASS && alignment < PAGE) {
270		/*
271		 * Round size up to the nearest multiple of alignment.
272		 *
273		 * This done, we can take advantage of the fact that for each
274		 * small size class, every object is aligned at the smallest
275		 * power of two that is non-zero in the base two representation
276		 * of the size.  For example:
277		 *
278		 *   Size |   Base 2 | Minimum alignment
279		 *   -----+----------+------------------
280		 *     96 |  1100000 |  32
281		 *    144 | 10100000 |  32
282		 *    192 | 11000000 |  64
283		 */
284		usize = sz_s2u(ALIGNMENT_CEILING(size, alignment));
285		if (usize < SC_LARGE_MINCLASS) {
286			return usize;
287		}
288	}
289
290	/* Large size class.  Beware of overflow. */
291
292	if (unlikely(alignment > SC_LARGE_MAXCLASS)) {
293		return 0;
294	}
295
296	/* Make sure result is a large size class. */
297	if (size <= SC_LARGE_MINCLASS) {
298		usize = SC_LARGE_MINCLASS;
299	} else {
300		usize = sz_s2u(size);
301		if (usize < size) {
302			/* size_t overflow. */
303			return 0;
304		}
305	}
306
307	/*
308	 * Calculate the multi-page mapping that large_palloc() would need in
309	 * order to guarantee the alignment.
310	 */
311	if (usize + sz_large_pad + PAGE_CEILING(alignment) - PAGE < usize) {
312		/* size_t overflow. */
313		return 0;
314	}
315	return usize;
316}
317
318#endif /* JEMALLOC_INTERNAL_SIZE_H */
319