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  */
29 extern 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  */
34 extern 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  */
40 extern uint8_t 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 extern void sz_boot(const sc_data_t *sc_data);
51 
52 JEMALLOC_ALWAYS_INLINE pszind_t
53 sz_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 
73 static inline size_t
74 sz_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 
93 static inline size_t
94 sz_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 
100 static inline size_t
101 sz_pind2sz(pszind_t pind) {
102 	assert(pind < SC_NPSIZES + 1);
103 	return sz_pind2sz_lookup(pind);
104 }
105 
106 static inline size_t
107 sz_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 
120 static inline szind_t
121 sz_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 
154 JEMALLOC_ALWAYS_INLINE szind_t
155 sz_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 
163 JEMALLOC_ALWAYS_INLINE szind_t
164 sz_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 
171 static inline size_t
172 sz_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 
197 JEMALLOC_ALWAYS_INLINE size_t
198 sz_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 
204 JEMALLOC_ALWAYS_INLINE size_t
205 sz_index2size(szind_t index) {
206 	assert(index < SC_NSIZES);
207 	return sz_index2size_lookup(index);
208 }
209 
210 JEMALLOC_ALWAYS_INLINE size_t
211 sz_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 
238 JEMALLOC_ALWAYS_INLINE size_t
239 sz_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  */
250 JEMALLOC_ALWAYS_INLINE size_t
251 sz_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  */
262 JEMALLOC_ALWAYS_INLINE size_t
263 sz_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