1 #include "jemalloc/internal/jemalloc_preamble.h" 2 3 #include "jemalloc/internal/assert.h" 4 #include "jemalloc/internal/bit_util.h" 5 #include "jemalloc/internal/bitmap.h" 6 #include "jemalloc/internal/pages.h" 7 #include "jemalloc/internal/sc.h" 8 9 /* 10 * This module computes the size classes used to satisfy allocations. The logic 11 * here was ported more or less line-by-line from a shell script, and because of 12 * that is not the most idiomatic C. Eventually we should fix this, but for now 13 * at least the damage is compartmentalized to this file. 14 */ 15 16 sc_data_t sc_data_global; 17 18 static size_t 19 reg_size_compute(int lg_base, int lg_delta, int ndelta) { 20 return (ZU(1) << lg_base) + (ZU(ndelta) << lg_delta); 21 } 22 23 /* Returns the number of pages in the slab. */ 24 static int 25 slab_size(int lg_page, int lg_base, int lg_delta, int ndelta) { 26 size_t page = (ZU(1) << lg_page); 27 size_t reg_size = reg_size_compute(lg_base, lg_delta, ndelta); 28 29 size_t try_slab_size = page; 30 size_t try_nregs = try_slab_size / reg_size; 31 size_t perfect_slab_size = 0; 32 bool perfect = false; 33 /* 34 * This loop continues until we find the least common multiple of the 35 * page size and size class size. Size classes are all of the form 36 * base + ndelta * delta == (ndelta + base/ndelta) * delta, which is 37 * (ndelta + ngroup) * delta. The way we choose slabbing strategies 38 * means that delta is at most the page size and ndelta < ngroup. So 39 * the loop executes for at most 2 * ngroup - 1 iterations, which is 40 * also the bound on the number of pages in a slab chosen by default. 41 * With the current default settings, this is at most 7. 42 */ 43 while (!perfect) { 44 perfect_slab_size = try_slab_size; 45 size_t perfect_nregs = try_nregs; 46 try_slab_size += page; 47 try_nregs = try_slab_size / reg_size; 48 if (perfect_slab_size == perfect_nregs * reg_size) { 49 perfect = true; 50 } 51 } 52 return (int)(perfect_slab_size / page); 53 } 54 55 static void 56 size_class( 57 /* Output. */ 58 sc_t *sc, 59 /* Configuration decisions. */ 60 int lg_max_lookup, int lg_page, int lg_ngroup, 61 /* Inputs specific to the size class. */ 62 int index, int lg_base, int lg_delta, int ndelta) { 63 sc->index = index; 64 sc->lg_base = lg_base; 65 sc->lg_delta = lg_delta; 66 sc->ndelta = ndelta; 67 sc->psz = (reg_size_compute(lg_base, lg_delta, ndelta) 68 % (ZU(1) << lg_page) == 0); 69 size_t size = (ZU(1) << lg_base) + (ZU(ndelta) << lg_delta); 70 if (index == 0) { 71 assert(!sc->psz); 72 } 73 if (size < (ZU(1) << (lg_page + lg_ngroup))) { 74 sc->bin = true; 75 sc->pgs = slab_size(lg_page, lg_base, lg_delta, ndelta); 76 } else { 77 sc->bin = false; 78 sc->pgs = 0; 79 } 80 if (size <= (ZU(1) << lg_max_lookup)) { 81 sc->lg_delta_lookup = lg_delta; 82 } else { 83 sc->lg_delta_lookup = 0; 84 } 85 } 86 87 static void 88 size_classes( 89 /* Output. */ 90 sc_data_t *sc_data, 91 /* Determined by the system. */ 92 size_t lg_ptr_size, int lg_quantum, 93 /* Configuration decisions. */ 94 int lg_tiny_min, int lg_max_lookup, int lg_page, int lg_ngroup) { 95 int ptr_bits = (1 << lg_ptr_size) * 8; 96 int ngroup = (1 << lg_ngroup); 97 int ntiny = 0; 98 int nlbins = 0; 99 int lg_tiny_maxclass = (unsigned)-1; 100 int nbins = 0; 101 int npsizes = 0; 102 103 int index = 0; 104 105 int ndelta = 0; 106 int lg_base = lg_tiny_min; 107 int lg_delta = lg_base; 108 109 /* Outputs that we update as we go. */ 110 size_t lookup_maxclass = 0; 111 size_t small_maxclass = 0; 112 int lg_large_minclass = 0; 113 size_t large_maxclass = 0; 114 115 /* Tiny size classes. */ 116 while (lg_base < lg_quantum) { 117 sc_t *sc = &sc_data->sc[index]; 118 size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index, 119 lg_base, lg_delta, ndelta); 120 if (sc->lg_delta_lookup != 0) { 121 nlbins = index + 1; 122 } 123 if (sc->psz) { 124 npsizes++; 125 } 126 if (sc->bin) { 127 nbins++; 128 } 129 ntiny++; 130 /* Final written value is correct. */ 131 lg_tiny_maxclass = lg_base; 132 index++; 133 lg_delta = lg_base; 134 lg_base++; 135 } 136 137 /* First non-tiny (pseudo) group. */ 138 if (ntiny != 0) { 139 sc_t *sc = &sc_data->sc[index]; 140 /* 141 * See the note in sc.h; the first non-tiny size class has an 142 * unusual encoding. 143 */ 144 lg_base--; 145 ndelta = 1; 146 size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index, 147 lg_base, lg_delta, ndelta); 148 index++; 149 lg_base++; 150 lg_delta++; 151 if (sc->psz) { 152 npsizes++; 153 } 154 if (sc->bin) { 155 nbins++; 156 } 157 } 158 while (ndelta < ngroup) { 159 sc_t *sc = &sc_data->sc[index]; 160 size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index, 161 lg_base, lg_delta, ndelta); 162 index++; 163 ndelta++; 164 if (sc->psz) { 165 npsizes++; 166 } 167 if (sc->bin) { 168 nbins++; 169 } 170 } 171 172 /* All remaining groups. */ 173 lg_base = lg_base + lg_ngroup; 174 while (lg_base < ptr_bits - 1) { 175 ndelta = 1; 176 int ndelta_limit; 177 if (lg_base == ptr_bits - 2) { 178 ndelta_limit = ngroup - 1; 179 } else { 180 ndelta_limit = ngroup; 181 } 182 while (ndelta <= ndelta_limit) { 183 sc_t *sc = &sc_data->sc[index]; 184 size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index, 185 lg_base, lg_delta, ndelta); 186 if (sc->lg_delta_lookup != 0) { 187 nlbins = index + 1; 188 /* Final written value is correct. */ 189 lookup_maxclass = (ZU(1) << lg_base) 190 + (ZU(ndelta) << lg_delta); 191 } 192 if (sc->psz) { 193 npsizes++; 194 } 195 if (sc->bin) { 196 nbins++; 197 /* Final written value is correct. */ 198 small_maxclass = (ZU(1) << lg_base) 199 + (ZU(ndelta) << lg_delta); 200 if (lg_ngroup > 0) { 201 lg_large_minclass = lg_base + 1; 202 } else { 203 lg_large_minclass = lg_base + 2; 204 } 205 } 206 large_maxclass = (ZU(1) << lg_base) 207 + (ZU(ndelta) << lg_delta); 208 index++; 209 ndelta++; 210 } 211 lg_base++; 212 lg_delta++; 213 } 214 /* Additional outputs. */ 215 int nsizes = index; 216 unsigned lg_ceil_nsizes = lg_ceil(nsizes); 217 218 /* Fill in the output data. */ 219 sc_data->ntiny = ntiny; 220 sc_data->nlbins = nlbins; 221 sc_data->nbins = nbins; 222 sc_data->nsizes = nsizes; 223 sc_data->lg_ceil_nsizes = lg_ceil_nsizes; 224 sc_data->npsizes = npsizes; 225 sc_data->lg_tiny_maxclass = lg_tiny_maxclass; 226 sc_data->lookup_maxclass = lookup_maxclass; 227 sc_data->small_maxclass = small_maxclass; 228 sc_data->lg_large_minclass = lg_large_minclass; 229 sc_data->large_minclass = (ZU(1) << lg_large_minclass); 230 sc_data->large_maxclass = large_maxclass; 231 232 /* 233 * We compute these values in two ways: 234 * - Incrementally, as above. 235 * - In macros, in sc.h. 236 * The computation is easier when done incrementally, but putting it in 237 * a constant makes it available to the fast paths without having to 238 * touch the extra global cacheline. We assert, however, that the two 239 * computations are equivalent. 240 */ 241 assert(sc_data->npsizes == SC_NPSIZES); 242 assert(sc_data->lg_tiny_maxclass == SC_LG_TINY_MAXCLASS); 243 assert(sc_data->small_maxclass == SC_SMALL_MAXCLASS); 244 assert(sc_data->large_minclass == SC_LARGE_MINCLASS); 245 assert(sc_data->lg_large_minclass == SC_LG_LARGE_MINCLASS); 246 assert(sc_data->large_maxclass == SC_LARGE_MAXCLASS); 247 248 /* 249 * In the allocation fastpath, we want to assume that we can 250 * unconditionally subtract the requested allocation size from 251 * a ssize_t, and detect passing through 0 correctly. This 252 * results in optimal generated code. For this to work, the 253 * maximum allocation size must be less than SSIZE_MAX. 254 */ 255 assert(SC_LARGE_MAXCLASS < SSIZE_MAX); 256 } 257 258 void 259 sc_data_init(sc_data_t *sc_data) { 260 assert(!sc_data->initialized); 261 262 int lg_max_lookup = 12; 263 264 size_classes(sc_data, LG_SIZEOF_PTR, LG_QUANTUM, SC_LG_TINY_MIN, 265 lg_max_lookup, LG_PAGE, 2); 266 267 sc_data->initialized = true; 268 } 269 270 static void 271 sc_data_update_sc_slab_size(sc_t *sc, size_t reg_size, size_t pgs_guess) { 272 size_t min_pgs = reg_size / PAGE; 273 if (reg_size % PAGE != 0) { 274 min_pgs++; 275 } 276 /* 277 * BITMAP_MAXBITS is actually determined by putting the smallest 278 * possible size-class on one page, so this can never be 0. 279 */ 280 size_t max_pgs = BITMAP_MAXBITS * reg_size / PAGE; 281 282 assert(min_pgs <= max_pgs); 283 assert(min_pgs > 0); 284 assert(max_pgs >= 1); 285 if (pgs_guess < min_pgs) { 286 sc->pgs = (int)min_pgs; 287 } else if (pgs_guess > max_pgs) { 288 sc->pgs = (int)max_pgs; 289 } else { 290 sc->pgs = (int)pgs_guess; 291 } 292 } 293 294 void 295 sc_data_update_slab_size(sc_data_t *data, size_t begin, size_t end, int pgs) { 296 assert(data->initialized); 297 for (int i = 0; i < data->nsizes; i++) { 298 sc_t *sc = &data->sc[i]; 299 if (!sc->bin) { 300 break; 301 } 302 size_t reg_size = reg_size_compute(sc->lg_base, sc->lg_delta, 303 sc->ndelta); 304 if (begin <= reg_size && reg_size <= end) { 305 sc_data_update_sc_slab_size(sc, reg_size, pgs); 306 } 307 } 308 } 309 310 void 311 sc_boot(sc_data_t *data) { 312 sc_data_init(data); 313 } 314