Test run quantization.
Also rename run_quantize_*() to improve clarity. These tests
demonstrate that run_quantize_ceil() is flawed.
diff --git a/Makefile.in b/Makefile.in
index a4555c0..f60823f 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -159,6 +159,7 @@
$(srcroot)test/unit/quarantine.c \
$(srcroot)test/unit/rb.c \
$(srcroot)test/unit/rtree.c \
+ $(srcroot)test/unit/run_quantize.c \
$(srcroot)test/unit/SFMT.c \
$(srcroot)test/unit/size_classes.c \
$(srcroot)test/unit/smoothstep.c \
diff --git a/include/jemalloc/internal/arena.h b/include/jemalloc/internal/arena.h
index 561b588..f98aeb8 100644
--- a/include/jemalloc/internal/arena.h
+++ b/include/jemalloc/internal/arena.h
@@ -494,9 +494,15 @@
extern size_t map_misc_offset;
extern size_t arena_maxrun; /* Max run size for arenas. */
extern size_t large_maxclass; /* Max large size class. */
+extern size_t small_maxrun; /* Max run size for small size classes. */
extern unsigned nlclasses; /* Number of large size classes. */
extern unsigned nhclasses; /* Number of huge size classes. */
+#ifdef JEMALLOC_JET
+typedef size_t (run_quantize_t)(size_t);
+extern run_quantize_t *run_quantize_floor;
+extern run_quantize_t *run_quantize_ceil;
+#endif
void arena_chunk_cache_maybe_insert(arena_t *arena, extent_node_t *node,
bool cache);
void arena_chunk_cache_maybe_remove(arena_t *arena, extent_node_t *node,
diff --git a/include/jemalloc/internal/private_symbols.txt b/include/jemalloc/internal/private_symbols.txt
index c12baad..3e37a61 100644
--- a/include/jemalloc/internal/private_symbols.txt
+++ b/include/jemalloc/internal/private_symbols.txt
@@ -445,6 +445,8 @@
rtree_subtree_tryread
rtree_val_read
rtree_val_write
+run_quantize_ceil
+run_quantize_floor
s2u
s2u_compute
s2u_lookup
diff --git a/src/arena.c b/src/arena.c
index 77c691a..ff5b5fb 100644
--- a/src/arena.c
+++ b/src/arena.c
@@ -21,7 +21,7 @@
size_t map_misc_offset;
size_t arena_maxrun; /* Max run size for arenas. */
size_t large_maxclass; /* Max large size class. */
-static size_t small_maxrun; /* Max run size used for small size classes. */
+size_t small_maxrun; /* Max run size for small size classes. */
static bool *small_run_tab; /* Valid small run page multiples. */
unsigned nlclasses; /* Number of large size classes. */
unsigned nhclasses; /* Number of huge size classes. */
@@ -100,8 +100,12 @@
rb_gen(static UNUSED, arena_run_tree_, arena_run_tree_t, arena_chunk_map_misc_t,
rb_link, arena_run_comp)
+#ifdef JEMALLOC_JET
+#undef run_quantize_floor
+#define run_quantize_floor JEMALLOC_N(run_quantize_floor_impl)
+#endif
static size_t
-run_quantize(size_t size)
+run_quantize_floor(size_t size)
{
size_t qsize;
@@ -119,13 +123,18 @@
*/
qsize = index2size(size2index(size - large_pad + 1) - 1) + large_pad;
if (qsize <= SMALL_MAXCLASS + large_pad)
- return (run_quantize(size - large_pad));
+ return (run_quantize_floor(size - large_pad));
assert(qsize <= size);
return (qsize);
}
+#ifdef JEMALLOC_JET
+#undef run_quantize_floor
+#define run_quantize_floor JEMALLOC_N(run_quantize_floor)
+run_quantize_t *run_quantize_floor = JEMALLOC_N(run_quantize_floor_impl);
+#endif
static size_t
-run_quantize_next(size_t size)
+run_quantize_ceil_hard(size_t size)
{
size_t large_run_size_next;
@@ -158,10 +167,14 @@
}
}
+#ifdef JEMALLOC_JET
+#undef run_quantize_ceil
+#define run_quantize_ceil JEMALLOC_N(run_quantize_ceil_impl)
+#endif
static size_t
-run_quantize_first(size_t size)
+run_quantize_ceil(size_t size)
{
- size_t qsize = run_quantize(size);
+ size_t qsize = run_quantize_floor(size);
if (qsize < size) {
/*
@@ -172,10 +185,15 @@
* search would potentially find sufficiently aligned available
* memory somewhere lower.
*/
- qsize = run_quantize_next(size);
+ qsize = run_quantize_ceil_hard(size);
}
return (qsize);
}
+#ifdef JEMALLOC_JET
+#undef run_quantize_ceil
+#define run_quantize_ceil JEMALLOC_N(run_quantize_ceil)
+run_quantize_t *run_quantize_ceil = JEMALLOC_N(run_quantize_ceil_impl);
+#endif
JEMALLOC_INLINE_C int
arena_avail_comp(const arena_chunk_map_misc_t *a,
@@ -183,9 +201,9 @@
{
int ret;
uintptr_t a_miscelm = (uintptr_t)a;
- size_t a_qsize = run_quantize(arena_miscelm_is_key(a) ?
+ size_t a_qsize = run_quantize_floor(arena_miscelm_is_key(a) ?
arena_miscelm_key_size_get(a) : arena_miscelm_size_get(a));
- size_t b_qsize = run_quantize(arena_miscelm_size_get(b));
+ size_t b_qsize = run_quantize_floor(arena_miscelm_size_get(b));
/*
* Compare based on quantized size rather than size, in order to sort
@@ -1081,7 +1099,7 @@
static arena_run_t *
arena_run_first_best_fit(arena_t *arena, size_t size)
{
- size_t search_size = run_quantize_first(size);
+ size_t search_size = run_quantize_ceil(size);
arena_chunk_map_misc_t *key = arena_miscelm_key_create(search_size);
arena_chunk_map_misc_t *miscelm =
arena_avail_tree_nsearch(&arena->runs_avail, key);
diff --git a/test/unit/run_quantize.c b/test/unit/run_quantize.c
new file mode 100644
index 0000000..aff4056
--- /dev/null
+++ b/test/unit/run_quantize.c
@@ -0,0 +1,157 @@
+#include "test/jemalloc_test.h"
+
+TEST_BEGIN(test_small_run_size)
+{
+ unsigned nbins, i;
+ size_t sz, run_size;
+ size_t mib[4];
+ size_t miblen = sizeof(mib) / sizeof(size_t);
+
+ /*
+ * Iterate over all small size classes, get their run sizes, and verify
+ * that the quantized size is the same as the run size.
+ */
+
+ sz = sizeof(unsigned);
+ assert_d_eq(mallctl("arenas.nbins", &nbins, &sz, NULL, 0), 0,
+ "Unexpected mallctl failure");
+
+ assert_d_eq(mallctlnametomib("arenas.bin.0.run_size", mib, &miblen), 0,
+ "Unexpected mallctlnametomib failure");
+ for (i = 0; i < nbins; i++) {
+ mib[2] = i;
+ sz = sizeof(size_t);
+ assert_d_eq(mallctlbymib(mib, miblen, &run_size, &sz, NULL, 0),
+ 0, "Unexpected mallctlbymib failure");
+ assert_zu_eq(run_size, run_quantize_floor(run_size),
+ "Small run quantization should be a no-op (run_size=%zu)",
+ run_size);
+ assert_zu_eq(run_size, run_quantize_ceil(run_size),
+ "Small run quantization should be a no-op (run_size=%zu)",
+ run_size);
+ }
+}
+TEST_END
+
+TEST_BEGIN(test_large_run_size)
+{
+ bool cache_oblivious;
+ unsigned nlruns, i;
+ size_t sz, run_size_prev, ceil_prev;
+ size_t mib[4];
+ size_t miblen = sizeof(mib) / sizeof(size_t);
+
+ /*
+ * Iterate over all large size classes, get their run sizes, and verify
+ * that the quantized size is the same as the run size.
+ */
+
+ sz = sizeof(bool);
+ assert_d_eq(mallctl("config.cache_oblivious", &cache_oblivious, &sz,
+ NULL, 0), 0, "Unexpected mallctl failure");
+
+ sz = sizeof(unsigned);
+ assert_d_eq(mallctl("arenas.nlruns", &nlruns, &sz, NULL, 0), 0,
+ "Unexpected mallctl failure");
+
+ assert_d_eq(mallctlnametomib("arenas.lrun.0.size", mib, &miblen), 0,
+ "Unexpected mallctlnametomib failure");
+ for (i = 0; i < nlruns; i++) {
+ size_t lrun_size, run_size, floor, ceil;
+
+ mib[2] = i;
+ sz = sizeof(size_t);
+ assert_d_eq(mallctlbymib(mib, miblen, &lrun_size, &sz, NULL, 0),
+ 0, "Unexpected mallctlbymib failure");
+ run_size = cache_oblivious ? lrun_size + PAGE : lrun_size;
+ floor = run_quantize_floor(run_size);
+ ceil = run_quantize_ceil(run_size);
+
+ assert_zu_eq(run_size, floor,
+ "Large run quantization should be a no-op for precise "
+ "size (lrun_size=%zu, run_size=%zu)", lrun_size, run_size);
+ assert_zu_eq(run_size, ceil,
+ "Large run quantization should be a no-op for precise "
+ "size (lrun_size=%zu, run_size=%zu)", lrun_size, run_size);
+
+ if (i > 0) {
+ assert_zu_eq(run_size_prev, run_quantize_floor(run_size
+ - PAGE), "Floor should be a precise size");
+ if (run_size_prev < ceil_prev) {
+ assert_zu_eq(ceil_prev, run_size,
+ "Ceiling should be a precise size "
+ "(run_size_prev=%zu, ceil_prev=%zu, "
+ "run_size=%zu)", run_size_prev, ceil_prev,
+ run_size);
+ }
+ }
+ run_size_prev = floor;
+ ceil_prev = run_quantize_ceil(run_size + PAGE);
+ }
+}
+TEST_END
+
+TEST_BEGIN(test_monotonic)
+{
+ bool cache_oblivious;
+ unsigned nbins, nlruns, i;
+ size_t sz, max_run_size, floor_prev, ceil_prev;
+
+ /*
+ * Iterate over all run sizes and verify that
+ * run_quantize_{floor,ceil}() are monotonic.
+ */
+
+ sz = sizeof(bool);
+ assert_d_eq(mallctl("config.cache_oblivious", &cache_oblivious, &sz,
+ NULL, 0), 0, "Unexpected mallctl failure");
+
+ sz = sizeof(unsigned);
+ assert_d_eq(mallctl("arenas.nbins", &nbins, &sz, NULL, 0), 0,
+ "Unexpected mallctl failure");
+
+ sz = sizeof(unsigned);
+ assert_d_eq(mallctl("arenas.nlruns", &nlruns, &sz, NULL, 0), 0,
+ "Unexpected mallctl failure");
+
+ max_run_size = (large_maxclass > small_maxrun) ? large_maxclass :
+ small_maxrun;
+
+ floor_prev = 0;
+ ceil_prev = 0;
+ for (i = 1; i < max_run_size >> LG_PAGE; i++) {
+ size_t run_size, floor, ceil;
+
+ run_size = i << LG_PAGE;
+ floor = run_quantize_floor(run_size);
+ ceil = run_quantize_ceil(run_size);
+
+ assert_zu_le(floor, run_size,
+ "Floor should be <= (floor=%zu, run_size=%zu, ceil=%zu)",
+ floor, run_size, ceil);
+ assert_zu_ge(ceil, run_size,
+ "Ceiling should be >= (floor=%zu, run_size=%zu, ceil=%zu)",
+ floor, run_size, ceil);
+
+ assert_zu_le(floor_prev, floor, "Floor should be monotonic "
+ "(floor_prev=%zu, floor=%zu, run_size=%zu, ceil=%zu)",
+ floor_prev, floor, run_size, ceil);
+ assert_zu_le(ceil_prev, ceil, "Ceiling should be monotonic "
+ "(floor=%zu, run_size=%zu, ceil_prev=%zu, ceil=%zu)",
+ floor, run_size, ceil_prev, ceil);
+
+ floor_prev = floor;
+ ceil_prev = ceil;
+ }
+}
+TEST_END
+
+int
+main(void)
+{
+
+ return (test(
+ test_small_run_size,
+ test_large_run_size,
+ test_monotonic));
+}