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 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 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 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 103 sz_pind2sz(pszind_t pind) { 104 assert(pind < NPSIZES+1); 105 return sz_pind2sz_lookup(pind); 106 } 107 108 static inline size_t 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 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 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 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 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 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 207 sz_index2size(szind_t index) { 208 assert(index < NSIZES); 209 return sz_index2size_lookup(index); 210 } 211 212 JEMALLOC_ALWAYS_INLINE size_t 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 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 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 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
