1 files changed, 306 insertions, 0 deletions
diff --git a/examples/redis-unstable/deps/jemalloc/src/sc.c b/examples/redis-unstable/deps/jemalloc/src/sc.c
new file mode 100644
index 0000000..e4a94d8
--- /dev/null
+++ b/examples/redis-unstable/deps/jemalloc/src/sc.c
@@ -0,0 +1,306 @@
+#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.
+ */
+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;
+        size_t size = reg_size_compute(lg_base, lg_delta, ndelta);
+        sc->psz = (size % (ZU(1) << lg_page) == 0);
+        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) {
+        size_classes(sc_data, LG_SIZEOF_PTR, LG_QUANTUM, SC_LG_TINY_MIN,
+            SC_LG_MAX_LOOKUP, LG_PAGE, SC_LG_NGROUP);
+        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);
+}

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