vendor/jemalloc-sys/rep/src/sc.c - toolchain/rustc - Git at Google

 #include "jemalloc/internal/jemalloc_preamble.h"

 #include "jemalloc/internal/assert.h"
 #include "jemalloc/internal/bit_util.h"
 #include "jemalloc/internal/bitmap.h"
 #include "jemalloc/internal/pages.h"
 #include "jemalloc/internal/sc.h"

 /*
  * This module computes the size classes used to satisfy allocations.  The logic
  * here was ported more or less line-by-line from a shell script, and because of
  * that is not the most idiomatic C.  Eventually we should fix this, but for now
  * at least the damage is compartmentalized to this file.
  */

 sc_data_t sc_data_global;

 static size_t
 reg_size_compute(int lg_base, int lg_delta, int ndelta) {
 	return (ZU(1) << lg_base) + (ZU(ndelta) << lg_delta);
 }

 /* Returns the number of pages in the slab. */
 static int
 slab_size(int lg_page, int lg_base, int lg_delta, int ndelta) {
 	size_t page = (ZU(1) << lg_page);
 	size_t reg_size = reg_size_compute(lg_base, lg_delta, ndelta);

 	size_t try_slab_size = page;
 	size_t try_nregs = try_slab_size / reg_size;
 	size_t perfect_slab_size = 0;
 	bool perfect = false;
 	/*
 	 * This loop continues until we find the least common multiple of the
 	 * page size and size class size.  Size classes are all of the form
 	 * base + ndelta * delta == (ndelta + base/ndelta) * delta, which is
 	 * (ndelta + ngroup) * delta.  The way we choose slabbing strategies
 	 * means that delta is at most the page size and ndelta < ngroup.  So
 	 * the loop executes for at most 2 * ngroup - 1 iterations, which is
 	 * also the bound on the number of pages in a slab chosen by default.
 	 * With the current default settings, this is at most 7.
 	 */
 	while (!perfect) {
 		perfect_slab_size = try_slab_size;
 		size_t perfect_nregs = try_nregs;
 		try_slab_size += page;
 		try_nregs = try_slab_size / reg_size;
 		if (perfect_slab_size == perfect_nregs * reg_size) {
 			perfect = true;
 		}
 	}
 	return (int)(perfect_slab_size / page);
 }

 static void
 size_class(
     /* Output. */
     sc_t *sc,
     /* Configuration decisions. */
     int lg_max_lookup, int lg_page, int lg_ngroup,
     /* Inputs specific to the size class. */
     int index, int lg_base, int lg_delta, int ndelta) {
 	sc->index = index;
 	sc->lg_base = lg_base;
 	sc->lg_delta = lg_delta;
 	sc->ndelta = ndelta;
 	sc->psz = (reg_size_compute(lg_base, lg_delta, ndelta)
 	    % (ZU(1) << lg_page) == 0);
 	size_t size = (ZU(1) << lg_base) + (ZU(ndelta) << lg_delta);
 	if (index == 0) {
 		assert(!sc->psz);
 	}
 	if (size < (ZU(1) << (lg_page + lg_ngroup))) {
 		sc->bin = true;
 		sc->pgs = slab_size(lg_page, lg_base, lg_delta, ndelta);
 	} else {
 		sc->bin = false;
 		sc->pgs = 0;
 	}
 	if (size <= (ZU(1) << lg_max_lookup)) {
 		sc->lg_delta_lookup = lg_delta;
 	} else {
 		sc->lg_delta_lookup = 0;
 	}
 }

 static void
 size_classes(
     /* Output. */
     sc_data_t *sc_data,
     /* Determined by the system. */
     size_t lg_ptr_size, int lg_quantum,
     /* Configuration decisions. */
     int lg_tiny_min, int lg_max_lookup, int lg_page, int lg_ngroup) {
 	int ptr_bits = (1 << lg_ptr_size) * 8;
 	int ngroup = (1 << lg_ngroup);
 	int ntiny = 0;
 	int nlbins = 0;
 	int lg_tiny_maxclass = (unsigned)-1;
 	int nbins = 0;
 	int npsizes = 0;

 	int index = 0;

 	int ndelta = 0;
 	int lg_base = lg_tiny_min;
 	int lg_delta = lg_base;

 	/* Outputs that we update as we go. */
 	size_t lookup_maxclass = 0;
 	size_t small_maxclass = 0;
 	int lg_large_minclass = 0;
 	size_t large_maxclass = 0;

 	/* Tiny size classes. */
 	while (lg_base < lg_quantum) {
 		sc_t *sc = &sc_data->sc[index];
 		size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index,
 		    lg_base, lg_delta, ndelta);
 		if (sc->lg_delta_lookup != 0) {
 			nlbins = index + 1;
 		}
 		if (sc->psz) {
 			npsizes++;
 		}
 		if (sc->bin) {
 			nbins++;
 		}
 		ntiny++;
 		/* Final written value is correct. */
 		lg_tiny_maxclass = lg_base;
 		index++;
 		lg_delta = lg_base;
 		lg_base++;
 	}

 	/* First non-tiny (pseudo) group. */
 	if (ntiny != 0) {
 		sc_t *sc = &sc_data->sc[index];
 		/*
 		 * See the note in sc.h; the first non-tiny size class has an
 		 * unusual encoding.
 		 */
 		lg_base--;
 		ndelta = 1;
 		size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index,
 		    lg_base, lg_delta, ndelta);
 		index++;
 		lg_base++;
 		lg_delta++;
 		if (sc->psz) {
 			npsizes++;
 		}
 		if (sc->bin) {
 			nbins++;
 		}
 	}
 	while (ndelta < ngroup) {
 		sc_t *sc = &sc_data->sc[index];
 		size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index,
 		    lg_base, lg_delta, ndelta);
 		index++;
 		ndelta++;
 		if (sc->psz) {
 			npsizes++;
 		}
 		if (sc->bin) {
 			nbins++;
 		}
 	}

 	/* All remaining groups. */
 	lg_base = lg_base + lg_ngroup;
 	while (lg_base < ptr_bits - 1) {
 		ndelta = 1;
 		int ndelta_limit;
 		if (lg_base == ptr_bits - 2) {
 			ndelta_limit = ngroup - 1;
 		} else {
 			ndelta_limit = ngroup;
 		}
 		while (ndelta <= ndelta_limit) {
 			sc_t *sc = &sc_data->sc[index];
 			size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index,
 			    lg_base, lg_delta, ndelta);
 			if (sc->lg_delta_lookup != 0) {
 				nlbins = index + 1;
 				/* Final written value is correct. */
 				lookup_maxclass = (ZU(1) << lg_base)
 				    + (ZU(ndelta) << lg_delta);
 			}
 			if (sc->psz) {
 				npsizes++;
 			}
 			if (sc->bin) {
 				nbins++;
 				/* Final written value is correct. */
 				small_maxclass = (ZU(1) << lg_base)
 				    + (ZU(ndelta) << lg_delta);
 				if (lg_ngroup > 0) {
 					lg_large_minclass = lg_base + 1;
 				} else {
 					lg_large_minclass = lg_base + 2;
 				}
 			}
 			large_maxclass = (ZU(1) << lg_base)
 			    + (ZU(ndelta) << lg_delta);
 			index++;
 			ndelta++;
 		}
 		lg_base++;
 		lg_delta++;
 	}
 	/* Additional outputs. */
 	int nsizes = index;
 	unsigned lg_ceil_nsizes = lg_ceil(nsizes);

 	/* Fill in the output data. */
 	sc_data->ntiny = ntiny;
 	sc_data->nlbins = nlbins;
 	sc_data->nbins = nbins;
 	sc_data->nsizes = nsizes;
 	sc_data->lg_ceil_nsizes = lg_ceil_nsizes;
 	sc_data->npsizes = npsizes;
 	sc_data->lg_tiny_maxclass = lg_tiny_maxclass;
 	sc_data->lookup_maxclass = lookup_maxclass;
 	sc_data->small_maxclass = small_maxclass;
 	sc_data->lg_large_minclass = lg_large_minclass;
 	sc_data->large_minclass = (ZU(1) << lg_large_minclass);
 	sc_data->large_maxclass = large_maxclass;

 	/*
 	 * We compute these values in two ways:
 	 *   - Incrementally, as above.
 	 *   - In macros, in sc.h.
 	 * The computation is easier when done incrementally, but putting it in
 	 * a constant makes it available to the fast paths without having to
 	 * touch the extra global cacheline.  We assert, however, that the two
 	 * computations are equivalent.
 	 */
 	assert(sc_data->npsizes == SC_NPSIZES);
 	assert(sc_data->lg_tiny_maxclass == SC_LG_TINY_MAXCLASS);
 	assert(sc_data->small_maxclass == SC_SMALL_MAXCLASS);
 	assert(sc_data->large_minclass == SC_LARGE_MINCLASS);
 	assert(sc_data->lg_large_minclass == SC_LG_LARGE_MINCLASS);
 	assert(sc_data->large_maxclass == SC_LARGE_MAXCLASS);

 	/*
 	 * In the allocation fastpath, we want to assume that we can
 	 * unconditionally subtract the requested allocation size from
 	 * a ssize_t, and detect passing through 0 correctly.  This
 	 * results in optimal generated code.  For this to work, the
 	 * maximum allocation size must be less than SSIZE_MAX.
 	 */
 	assert(SC_LARGE_MAXCLASS < SSIZE_MAX);
 }

 void
 sc_data_init(sc_data_t *sc_data) {
 	assert(!sc_data->initialized);

 	int lg_max_lookup = 12;

 	size_classes(sc_data, LG_SIZEOF_PTR, LG_QUANTUM, SC_LG_TINY_MIN,
 	    lg_max_lookup, LG_PAGE, 2);

 	sc_data->initialized = true;
 }

 static void
 sc_data_update_sc_slab_size(sc_t *sc, size_t reg_size, size_t pgs_guess) {
 	size_t min_pgs = reg_size / PAGE;
 	if (reg_size % PAGE != 0) {
 		min_pgs++;
 	}
 	/*
 	 * BITMAP_MAXBITS is actually determined by putting the smallest
 	 * possible size-class on one page, so this can never be 0.
 	 */
 	size_t max_pgs = BITMAP_MAXBITS * reg_size / PAGE;

 	assert(min_pgs <= max_pgs);
 	assert(min_pgs > 0);
 	assert(max_pgs >= 1);
 	if (pgs_guess < min_pgs) {
 		sc->pgs = (int)min_pgs;
 	} else if (pgs_guess > max_pgs) {
 		sc->pgs = (int)max_pgs;
 	} else {
 		sc->pgs = (int)pgs_guess;
 	}
 }

 void
 sc_data_update_slab_size(sc_data_t *data, size_t begin, size_t end, int pgs) {
 	assert(data->initialized);
 	for (int i = 0; i < data->nsizes; i++) {
 		sc_t *sc = &data->sc[i];
 		if (!sc->bin) {
 			break;
 		}
 		size_t reg_size = reg_size_compute(sc->lg_base, sc->lg_delta,
 		    sc->ndelta);
 		if (begin <= reg_size && reg_size <= end) {
 			sc_data_update_sc_slab_size(sc, reg_size, pgs);
 		}
 	}
 }

 void
 sc_boot(sc_data_t *data) {
 	sc_data_init(data);
 }
	#include "jemalloc/internal/jemalloc_preamble.h"

	#include "jemalloc/internal/assert.h"
	#include "jemalloc/internal/bit_util.h"
	#include "jemalloc/internal/bitmap.h"
	#include "jemalloc/internal/pages.h"
	#include "jemalloc/internal/sc.h"

	/*
	* This module computes the size classes used to satisfy allocations. The logic
	* here was ported more or less line-by-line from a shell script, and because of
	* that is not the most idiomatic C. Eventually we should fix this, but for now
	* at least the damage is compartmentalized to this file.
	*/

	sc_data_t sc_data_global;

	static size_t
	reg_size_compute(int lg_base, int lg_delta, int ndelta) {
	return (ZU(1) << lg_base) + (ZU(ndelta) << lg_delta);
	}

	/* Returns the number of pages in the slab. */
	static int
	slab_size(int lg_page, int lg_base, int lg_delta, int ndelta) {
	size_t page = (ZU(1) << lg_page);
	size_t reg_size = reg_size_compute(lg_base, lg_delta, ndelta);

	size_t try_slab_size = page;
	size_t try_nregs = try_slab_size / reg_size;
	size_t perfect_slab_size = 0;
	bool perfect = false;
	/*
	* This loop continues until we find the least common multiple of the
	* page size and size class size. Size classes are all of the form
	* base + ndelta * delta == (ndelta + base/ndelta) * delta, which is
	* (ndelta + ngroup) * delta. The way we choose slabbing strategies
	* means that delta is at most the page size and ndelta < ngroup. So
	* the loop executes for at most 2 * ngroup - 1 iterations, which is
	* also the bound on the number of pages in a slab chosen by default.
	* With the current default settings, this is at most 7.
	*/
	while (!perfect) {
	perfect_slab_size = try_slab_size;
	size_t perfect_nregs = try_nregs;
	try_slab_size += page;
	try_nregs = try_slab_size / reg_size;
	if (perfect_slab_size == perfect_nregs * reg_size) {
	perfect = true;
	}
	}
	return (int)(perfect_slab_size / page);
	}

	static void
	size_class(
	/* Output. */
	sc_t *sc,
	/* Configuration decisions. */
	int lg_max_lookup, int lg_page, int lg_ngroup,
	/* Inputs specific to the size class. */
	int index, int lg_base, int lg_delta, int ndelta) {
	sc->index = index;
	sc->lg_base = lg_base;
	sc->lg_delta = lg_delta;
	sc->ndelta = ndelta;
	sc->psz = (reg_size_compute(lg_base, lg_delta, ndelta)
	% (ZU(1) << lg_page) == 0);
	size_t size = (ZU(1) << lg_base) + (ZU(ndelta) << lg_delta);
	if (index == 0) {
	assert(!sc->psz);
	}
	if (size < (ZU(1) << (lg_page + lg_ngroup))) {
	sc->bin = true;
	sc->pgs = slab_size(lg_page, lg_base, lg_delta, ndelta);
	} else {
	sc->bin = false;
	sc->pgs = 0;
	}
	if (size <= (ZU(1) << lg_max_lookup)) {
	sc->lg_delta_lookup = lg_delta;
	} else {
	sc->lg_delta_lookup = 0;
	}
	}

	static void
	size_classes(
	/* Output. */
	sc_data_t *sc_data,
	/* Determined by the system. */
	size_t lg_ptr_size, int lg_quantum,
	/* Configuration decisions. */
	int lg_tiny_min, int lg_max_lookup, int lg_page, int lg_ngroup) {
	int ptr_bits = (1 << lg_ptr_size) * 8;
	int ngroup = (1 << lg_ngroup);
	int ntiny = 0;
	int nlbins = 0;
	int lg_tiny_maxclass = (unsigned)-1;
	int nbins = 0;
	int npsizes = 0;

	int index = 0;

	int ndelta = 0;
	int lg_base = lg_tiny_min;
	int lg_delta = lg_base;

	/* Outputs that we update as we go. */
	size_t lookup_maxclass = 0;
	size_t small_maxclass = 0;
	int lg_large_minclass = 0;
	size_t large_maxclass = 0;

	/* Tiny size classes. */
	while (lg_base < lg_quantum) {
	sc_t *sc = &sc_data->sc[index];
	size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index,
	lg_base, lg_delta, ndelta);
	if (sc->lg_delta_lookup != 0) {
	nlbins = index + 1;
	}
	if (sc->psz) {
	npsizes++;
	}
	if (sc->bin) {
	nbins++;
	}
	ntiny++;
	/* Final written value is correct. */
	lg_tiny_maxclass = lg_base;
	index++;
	lg_delta = lg_base;
	lg_base++;
	}

	/* First non-tiny (pseudo) group. */
	if (ntiny != 0) {
	sc_t *sc = &sc_data->sc[index];
	/*
	* See the note in sc.h; the first non-tiny size class has an
	* unusual encoding.
	*/
	lg_base--;
	ndelta = 1;
	size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index,
	lg_base, lg_delta, ndelta);
	index++;
	lg_base++;
	lg_delta++;
	if (sc->psz) {
	npsizes++;
	}
	if (sc->bin) {
	nbins++;
	}
	}
	while (ndelta < ngroup) {
	sc_t *sc = &sc_data->sc[index];
	size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index,
	lg_base, lg_delta, ndelta);
	index++;
	ndelta++;
	if (sc->psz) {
	npsizes++;
	}
	if (sc->bin) {
	nbins++;
	}
	}

	/* All remaining groups. */
	lg_base = lg_base + lg_ngroup;
	while (lg_base < ptr_bits - 1) {
	ndelta = 1;
	int ndelta_limit;
	if (lg_base == ptr_bits - 2) {
	ndelta_limit = ngroup - 1;
	} else {
	ndelta_limit = ngroup;
	}
	while (ndelta <= ndelta_limit) {
	sc_t *sc = &sc_data->sc[index];
	size_class(sc, lg_max_lookup, lg_page, lg_ngroup, index,
	lg_base, lg_delta, ndelta);
	if (sc->lg_delta_lookup != 0) {
	nlbins = index + 1;
	/* Final written value is correct. */
	lookup_maxclass = (ZU(1) << lg_base)
	+ (ZU(ndelta) << lg_delta);
	}
	if (sc->psz) {
	npsizes++;
	}
	if (sc->bin) {
	nbins++;
	/* Final written value is correct. */
	small_maxclass = (ZU(1) << lg_base)
	+ (ZU(ndelta) << lg_delta);
	if (lg_ngroup > 0) {
	lg_large_minclass = lg_base + 1;
	} else {
	lg_large_minclass = lg_base + 2;
	}
	}
	large_maxclass = (ZU(1) << lg_base)
	+ (ZU(ndelta) << lg_delta);
	index++;
	ndelta++;
	}
	lg_base++;
	lg_delta++;
	}
	/* Additional outputs. */
	int nsizes = index;
	unsigned lg_ceil_nsizes = lg_ceil(nsizes);

	/* Fill in the output data. */
	sc_data->ntiny = ntiny;
	sc_data->nlbins = nlbins;
	sc_data->nbins = nbins;
	sc_data->nsizes = nsizes;
	sc_data->lg_ceil_nsizes = lg_ceil_nsizes;
	sc_data->npsizes = npsizes;
	sc_data->lg_tiny_maxclass = lg_tiny_maxclass;
	sc_data->lookup_maxclass = lookup_maxclass;
	sc_data->small_maxclass = small_maxclass;
	sc_data->lg_large_minclass = lg_large_minclass;
	sc_data->large_minclass = (ZU(1) << lg_large_minclass);
	sc_data->large_maxclass = large_maxclass;

	/*
	* We compute these values in two ways:
	* - Incrementally, as above.
	* - In macros, in sc.h.
	* The computation is easier when done incrementally, but putting it in
	* a constant makes it available to the fast paths without having to
	* touch the extra global cacheline. We assert, however, that the two
	* computations are equivalent.
	*/
	assert(sc_data->npsizes == SC_NPSIZES);
	assert(sc_data->lg_tiny_maxclass == SC_LG_TINY_MAXCLASS);
	assert(sc_data->small_maxclass == SC_SMALL_MAXCLASS);
	assert(sc_data->large_minclass == SC_LARGE_MINCLASS);
	assert(sc_data->lg_large_minclass == SC_LG_LARGE_MINCLASS);
	assert(sc_data->large_maxclass == SC_LARGE_MAXCLASS);

	/*
	* In the allocation fastpath, we want to assume that we can
	* unconditionally subtract the requested allocation size from
	* a ssize_t, and detect passing through 0 correctly. This
	* results in optimal generated code. For this to work, the
	* maximum allocation size must be less than SSIZE_MAX.
	*/
	assert(SC_LARGE_MAXCLASS < SSIZE_MAX);
	}

	void
	sc_data_init(sc_data_t *sc_data) {
	assert(!sc_data->initialized);

	int lg_max_lookup = 12;

	size_classes(sc_data, LG_SIZEOF_PTR, LG_QUANTUM, SC_LG_TINY_MIN,
	lg_max_lookup, LG_PAGE, 2);

	sc_data->initialized = true;
	}

	static void
	sc_data_update_sc_slab_size(sc_t *sc, size_t reg_size, size_t pgs_guess) {
	size_t min_pgs = reg_size / PAGE;
	if (reg_size % PAGE != 0) {
	min_pgs++;
	}
	/*
	* BITMAP_MAXBITS is actually determined by putting the smallest
	* possible size-class on one page, so this can never be 0.
	*/
	size_t max_pgs = BITMAP_MAXBITS * reg_size / PAGE;

	assert(min_pgs <= max_pgs);
	assert(min_pgs > 0);
	assert(max_pgs >= 1);
	if (pgs_guess < min_pgs) {
	sc->pgs = (int)min_pgs;
	} else if (pgs_guess > max_pgs) {
	sc->pgs = (int)max_pgs;
	} else {
	sc->pgs = (int)pgs_guess;
	}
	}

	void
	sc_data_update_slab_size(sc_data_t *data, size_t begin, size_t end, int pgs) {
	assert(data->initialized);
	for (int i = 0; i < data->nsizes; i++) {
	sc_t *sc = &data->sc[i];
	if (!sc->bin) {
	break;
	}
	size_t reg_size = reg_size_compute(sc->lg_base, sc->lg_delta,
	sc->ndelta);
	if (begin <= reg_size && reg_size <= end) {
	sc_data_update_sc_slab_size(sc, reg_size, pgs);
	}
	}
	}

	void
	sc_boot(sc_data_t *data) {
	sc_data_init(data);
	}