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