Add comments and use meaningful vars in sz_psz2ind.

5 files changed, 108 insertions, 10 deletions

diff --git a/Makefile.in b/Makefile.in
index 8e16982e..cf6d5687 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -278,6 +278,7 @@ TESTS_UNIT := \
 	$(srcroot)test/unit/spin.c \
 	$(srcroot)test/unit/stats.c \
 	$(srcroot)test/unit/stats_print.c \
+	$(srcroot)test/unit/sz.c \
 	$(srcroot)test/unit/tcache_max.c \
 	$(srcroot)test/unit/test_hooks.c \
 	$(srcroot)test/unit/thread_event.c \
diff --git a/include/jemalloc/internal/sc.h b/include/jemalloc/internal/sc.h
index 8efd3249..308985fa 100644
--- a/include/jemalloc/internal/sc.h
+++ b/include/jemalloc/internal/sc.h
@@ -344,6 +344,7 @@ struct sc_data_s {
 	sc_t sc[SC_NSIZES];
 };
 
+size_t reg_size_compute(int lg_base, int lg_delta, int ndelta);
 void sc_data_init(sc_data_t *data);
 /*
  * Updates slab sizes in [begin, end] to be pgs pages in length, if possible.
diff --git a/include/jemalloc/internal/sz.h b/include/jemalloc/internal/sz.h
index f2be6139..3c0fc1da 100644
--- a/include/jemalloc/internal/sz.h
+++ b/include/jemalloc/internal/sz.h
@@ -55,22 +55,52 @@ extern void sz_boot(const sc_data_t *sc_data, bool cache_oblivious);
 
 JEMALLOC_ALWAYS_INLINE pszind_t
 sz_psz2ind(size_t psz) {
+	assert(psz > 0);
 	if (unlikely(psz > SC_LARGE_MAXCLASS)) {
 		return SC_NPSIZES;
 	}
-	pszind_t x = lg_floor((psz<<1)-1);
-	pszind_t shift = (x < SC_LG_NGROUP + LG_PAGE) ?
+	/* x is the lg of the first base >= psz. */
+	pszind_t x = lg_ceil(psz);
+	/*
+	 * sc.h introduces a lot of size classes. These size classes are divided
+	 * into different size class groups. There is a very special size class
+	 * group, each size class in or after it is an integer multiple of PAGE.
+	 * We call it first_ps_rg. It means first page size regular group. The
+	 * range of first_ps_rg is (base, base * 2], and base == PAGE *
+	 * SC_NGROUP. off_to_first_ps_rg begins from 1, instead of 0. e.g.
+	 * off_to_first_ps_rg is 1 when psz is (PAGE * SC_NGROUP + 1).
+	 */
+	pszind_t off_to_first_ps_rg = (x < SC_LG_NGROUP + LG_PAGE) ?
 	    0 : x - (SC_LG_NGROUP + LG_PAGE);
-	pszind_t grp = shift << SC_LG_NGROUP;
 
-	pszind_t lg_delta = (x < SC_LG_NGROUP + LG_PAGE + 1) ?
-	    LG_PAGE : x - SC_LG_NGROUP - 1;
+	/*
+	 * Same as sc_s::lg_delta.
+	 * Delta for off_to_first_ps_rg == 1 is PAGE,
+	 * for each increase in offset, it's multiplied by two.
+	 * Therefore, lg_delta = LG_PAGE + (off_to_first_ps_rg - 1).
+	 */
+	pszind_t lg_delta = (off_to_first_ps_rg == 0) ?
+	    LG_PAGE : LG_PAGE + (off_to_first_ps_rg - 1);
 
-	size_t delta_inverse_mask = ZU(-1) << lg_delta;
-	pszind_t mod = ((((psz-1) & delta_inverse_mask) >> lg_delta)) &
-	    ((ZU(1) << SC_LG_NGROUP) - 1);
+	/*
+	 * Let's write psz in binary, e.g. 0011 for 0x3, 0111 for 0x7.
+	 * The leftmost bits whose len is lg_base decide the base of psz.
+	 * The rightmost bits whose len is lg_delta decide (pgz % PAGE).
+	 * The middle bits whose len is SC_LG_NGROUP decide ndelta.
+	 * ndelta is offset to the first size class in the size class group,
+	 * starts from 1.
+	 * If you don't know lg_base, ndelta or lg_delta, see sc.h.
+	 * |xxxxxxxxxxxxxxxxxxxx|------------------------|yyyyyyyyyyyyyyyyyyyyy|
+	 * |<-- len: lg_base -->|<-- len: SC_LG_NGROUP-->|<-- len: lg_delta -->|
+	 *                      |<--      ndelta      -->|
+	 * rg_inner_off = ndelta - 1
+	 * Why use (psz - 1)?
+	 * To handle case: psz % (1 << lg_delta) == 0.
+	 */
+	pszind_t rg_inner_off = (((psz - 1)) >> lg_delta) & (SC_NGROUP - 1);
 
-	pszind_t ind = grp + mod;
+	pszind_t base_ind = off_to_first_ps_rg << SC_LG_NGROUP;
+	pszind_t ind = base_ind + rg_inner_off;
 	return ind;
 }
 
diff --git a/src/sc.c b/src/sc.c
index 9a0f76d5..e4a94d89 100644
--- a/src/sc.c
+++ b/src/sc.c
@@ -13,7 +13,7 @@
  * at least the damage is compartmentalized to this file.
  */
 
-static size_t
+size_t
 reg_size_compute(int lg_base, int lg_delta, int ndelta) {
 	return (ZU(1) << lg_base) + (ZU(ndelta) << lg_delta);
 }
diff --git a/test/unit/sz.c b/test/unit/sz.c
new file mode 100644
index 00000000..be11aca4
--- /dev/null
+++ b/test/unit/sz.c
@@ -0,0 +1,66 @@
+#include "test/jemalloc_test.h"
+
+TEST_BEGIN(test_sz_psz2ind) {
+	/*
+	 * Testing page size classes which reside prior to the regular group
+	 * with all size classes divisible by page size.
+	 * For x86_64 Linux, it's 4096, 8192, 12288, 16384, with correponding
+	 * pszind 0, 1, 2 and 3.
+	 */
+	for (size_t i = 0; i < SC_NGROUP; i++) {
+		for (size_t psz = i * PAGE + 1; psz <= (i + 1) * PAGE; psz++) {
+			pszind_t ind = sz_psz2ind(psz);
+			expect_zu_eq(ind, i, "Got %u as sz_psz2ind of %zu", ind,
+			    psz);
+		}
+	}
+
+	sc_data_t data;
+	memset(&data, 0, sizeof(data));
+	sc_data_init(&data);
+	/*
+	 * 'base' is the base of the first regular group with all size classes
+	 * divisible by page size.
+	 * For x86_64 Linux, it's 16384, and base_ind is 36.
+	 */
+	size_t base_psz = 1 << (SC_LG_NGROUP + LG_PAGE);
+	size_t base_ind = 0;
+	while (base_ind < SC_NSIZES &&
+	    reg_size_compute(data.sc[base_ind].lg_base,
+		data.sc[base_ind].lg_delta,
+		data.sc[base_ind].ndelta) < base_psz) {
+		base_ind++;
+	}
+	expect_zu_eq(
+	    reg_size_compute(data.sc[base_ind].lg_base,
+		data.sc[base_ind].lg_delta, data.sc[base_ind].ndelta),
+	    base_psz, "Size class equal to %zu not found", base_psz);
+	/*
+	 * Test different sizes falling into groups after the 'base'. The
+	 * increment is PAGE / 3 for the execution speed purpose.
+	 */
+	base_ind -= SC_NGROUP;
+	for (size_t psz = base_psz; psz <= 64 * 1024 * 1024; psz += PAGE / 3) {
+		pszind_t ind = sz_psz2ind(psz);
+		sc_t gt_sc = data.sc[ind + base_ind];
+		expect_zu_gt(psz,
+		    reg_size_compute(gt_sc.lg_base, gt_sc.lg_delta,
+			gt_sc.ndelta),
+		    "Got %u as sz_psz2ind of %zu", ind, psz);
+		sc_t le_sc = data.sc[ind + base_ind + 1];
+		expect_zu_le(psz,
+		    reg_size_compute(le_sc.lg_base, le_sc.lg_delta,
+			le_sc.ndelta),
+		    "Got %u as sz_psz2ind of %zu", ind, psz);
+	}
+
+	pszind_t max_ind = sz_psz2ind(SC_LARGE_MAXCLASS + 1);
+	expect_lu_eq(max_ind, SC_NPSIZES,
+	    "Got %u as sz_psz2ind of %llu", max_ind, SC_LARGE_MAXCLASS);
+}
+TEST_END
+
+int
+main(void) {
+	return test(test_sz_psz2ind);
+}