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