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