contrib/jemalloc/include/jemalloc/internal/sz.h

   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 */