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 |