aboutsummaryrefslogtreecommitdiff
path: root/test/unit/rtree.c
diff options
context:
space:
mode:
authorWarner Losh <imp@FreeBSD.org>2025-02-05 23:20:13 +0000
committerWarner Losh <imp@FreeBSD.org>2025-02-05 23:20:13 +0000
commit48ec896efb0b78141df004eaa21288b84590c9da (patch)
tree33799792fd95c266d472ab1ae51d50ab4f942eb3 /test/unit/rtree.c
parentd28d7fbede216494aa3942af042cc084fcd6098a (diff)
jemalloc: Import 5.3.0 54eaed1d8b56b1aa528be3bdd1877e59c56fa90cvendor/jemalloc/5.3.0vendor/jemalloc
Import jemalloc 5.3.0. This import changes how manage the jemalloc vendor branch (which was just started anyway). Starting with 5.3.0, we import a clean tree from the upstream github, removing all the old files that are no longer upstream, or that we've kept around for some reason. We do this because we merge from this raw version of jemalloc into the FreeBSD contrib/jemalloc, then we run autogen stuff, generate all the generated .h files with gmake, then finally remove much of the generated files in contrib/jemalloc using an update script. Sponsored by: Netflix
Diffstat (limited to 'test/unit/rtree.c')
-rw-r--r--test/unit/rtree.c315
1 files changed, 188 insertions, 127 deletions
diff --git a/test/unit/rtree.c b/test/unit/rtree.c
index 90adca1346a5..4101b72be2e9 100644
--- a/test/unit/rtree.c
+++ b/test/unit/rtree.c
@@ -2,80 +2,30 @@
#include "jemalloc/internal/rtree.h"
-rtree_node_alloc_t *rtree_node_alloc_orig;
-rtree_node_dalloc_t *rtree_node_dalloc_orig;
-rtree_leaf_alloc_t *rtree_leaf_alloc_orig;
-rtree_leaf_dalloc_t *rtree_leaf_dalloc_orig;
+#define INVALID_ARENA_IND ((1U << MALLOCX_ARENA_BITS) - 1)
/* Potentially too large to safely place on the stack. */
rtree_t test_rtree;
-static rtree_node_elm_t *
-rtree_node_alloc_intercept(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) {
- rtree_node_elm_t *node;
-
- if (rtree != &test_rtree) {
- return rtree_node_alloc_orig(tsdn, rtree, nelms);
- }
-
- malloc_mutex_unlock(tsdn, &rtree->init_lock);
- node = (rtree_node_elm_t *)calloc(nelms, sizeof(rtree_node_elm_t));
- assert_ptr_not_null(node, "Unexpected calloc() failure");
- malloc_mutex_lock(tsdn, &rtree->init_lock);
-
- return node;
-}
-
-static void
-rtree_node_dalloc_intercept(tsdn_t *tsdn, rtree_t *rtree,
- rtree_node_elm_t *node) {
- if (rtree != &test_rtree) {
- rtree_node_dalloc_orig(tsdn, rtree, node);
- return;
- }
-
- free(node);
-}
-
-static rtree_leaf_elm_t *
-rtree_leaf_alloc_intercept(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) {
- rtree_leaf_elm_t *leaf;
-
- if (rtree != &test_rtree) {
- return rtree_leaf_alloc_orig(tsdn, rtree, nelms);
- }
-
- malloc_mutex_unlock(tsdn, &rtree->init_lock);
- leaf = (rtree_leaf_elm_t *)calloc(nelms, sizeof(rtree_leaf_elm_t));
- assert_ptr_not_null(leaf, "Unexpected calloc() failure");
- malloc_mutex_lock(tsdn, &rtree->init_lock);
-
- return leaf;
-}
-
-static void
-rtree_leaf_dalloc_intercept(tsdn_t *tsdn, rtree_t *rtree,
- rtree_leaf_elm_t *leaf) {
- if (rtree != &test_rtree) {
- rtree_leaf_dalloc_orig(tsdn, rtree, leaf);
- return;
- }
-
- free(leaf);
-}
-
TEST_BEGIN(test_rtree_read_empty) {
tsdn_t *tsdn;
tsdn = tsdn_fetch();
+ base_t *base = base_new(tsdn, 0, &ehooks_default_extent_hooks,
+ /* metadata_use_hooks */ true);
+ expect_ptr_not_null(base, "Unexpected base_new failure");
+
rtree_t *rtree = &test_rtree;
rtree_ctx_t rtree_ctx;
rtree_ctx_data_init(&rtree_ctx);
- assert_false(rtree_new(rtree, false), "Unexpected rtree_new() failure");
- assert_ptr_null(rtree_extent_read(tsdn, rtree, &rtree_ctx, PAGE,
- false), "rtree_extent_read() should return NULL for empty tree");
- rtree_delete(tsdn, rtree);
+ expect_false(rtree_new(rtree, base, false),
+ "Unexpected rtree_new() failure");
+ rtree_contents_t contents;
+ expect_true(rtree_read_independent(tsdn, rtree, &rtree_ctx, PAGE,
+ &contents), "rtree_read_independent() should fail on empty rtree.");
+
+ base_delete(tsdn, base);
}
TEST_END
@@ -83,75 +33,119 @@ TEST_END
#undef NITERS
#undef SEED
+static edata_t *
+alloc_edata(void) {
+ void *ret = mallocx(sizeof(edata_t), MALLOCX_ALIGN(EDATA_ALIGNMENT));
+ assert_ptr_not_null(ret, "Unexpected mallocx() failure");
+
+ return ret;
+}
+
TEST_BEGIN(test_rtree_extrema) {
- extent_t extent_a, extent_b;
- extent_init(&extent_a, NULL, NULL, SC_LARGE_MINCLASS, false,
- sz_size2index(SC_LARGE_MINCLASS), 0,
- extent_state_active, false, false, true, EXTENT_NOT_HEAD);
- extent_init(&extent_b, NULL, NULL, 0, false, SC_NSIZES, 0,
- extent_state_active, false, false, true, EXTENT_NOT_HEAD);
+ edata_t *edata_a, *edata_b;
+ edata_a = alloc_edata();
+ edata_b = alloc_edata();
+ edata_init(edata_a, INVALID_ARENA_IND, NULL, SC_LARGE_MINCLASS,
+ false, sz_size2index(SC_LARGE_MINCLASS), 0,
+ extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD);
+ edata_init(edata_b, INVALID_ARENA_IND, NULL, 0, false, SC_NSIZES, 0,
+ extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD);
tsdn_t *tsdn = tsdn_fetch();
+ base_t *base = base_new(tsdn, 0, &ehooks_default_extent_hooks,
+ /* metadata_use_hooks */ true);
+ expect_ptr_not_null(base, "Unexpected base_new failure");
+
rtree_t *rtree = &test_rtree;
rtree_ctx_t rtree_ctx;
rtree_ctx_data_init(&rtree_ctx);
- assert_false(rtree_new(rtree, false), "Unexpected rtree_new() failure");
+ expect_false(rtree_new(rtree, base, false),
+ "Unexpected rtree_new() failure");
- assert_false(rtree_write(tsdn, rtree, &rtree_ctx, PAGE, &extent_a,
- extent_szind_get(&extent_a), extent_slab_get(&extent_a)),
+ rtree_contents_t contents_a;
+ contents_a.edata = edata_a;
+ contents_a.metadata.szind = edata_szind_get(edata_a);
+ contents_a.metadata.slab = edata_slab_get(edata_a);
+ contents_a.metadata.is_head = edata_is_head_get(edata_a);
+ contents_a.metadata.state = edata_state_get(edata_a);
+ expect_false(rtree_write(tsdn, rtree, &rtree_ctx, PAGE, contents_a),
+ "Unexpected rtree_write() failure");
+ expect_false(rtree_write(tsdn, rtree, &rtree_ctx, PAGE, contents_a),
"Unexpected rtree_write() failure");
- rtree_szind_slab_update(tsdn, rtree, &rtree_ctx, PAGE,
- extent_szind_get(&extent_a), extent_slab_get(&extent_a));
- assert_ptr_eq(rtree_extent_read(tsdn, rtree, &rtree_ctx, PAGE, true),
- &extent_a,
- "rtree_extent_read() should return previously set value");
+ rtree_contents_t read_contents_a = rtree_read(tsdn, rtree, &rtree_ctx,
+ PAGE);
+ expect_true(contents_a.edata == read_contents_a.edata
+ && contents_a.metadata.szind == read_contents_a.metadata.szind
+ && contents_a.metadata.slab == read_contents_a.metadata.slab
+ && contents_a.metadata.is_head == read_contents_a.metadata.is_head
+ && contents_a.metadata.state == read_contents_a.metadata.state,
+ "rtree_read() should return previously set value");
- assert_false(rtree_write(tsdn, rtree, &rtree_ctx, ~((uintptr_t)0),
- &extent_b, extent_szind_get_maybe_invalid(&extent_b),
- extent_slab_get(&extent_b)), "Unexpected rtree_write() failure");
- assert_ptr_eq(rtree_extent_read(tsdn, rtree, &rtree_ctx,
- ~((uintptr_t)0), true), &extent_b,
- "rtree_extent_read() should return previously set value");
+ rtree_contents_t contents_b;
+ contents_b.edata = edata_b;
+ contents_b.metadata.szind = edata_szind_get_maybe_invalid(edata_b);
+ contents_b.metadata.slab = edata_slab_get(edata_b);
+ contents_b.metadata.is_head = edata_is_head_get(edata_b);
+ contents_b.metadata.state = edata_state_get(edata_b);
+ expect_false(rtree_write(tsdn, rtree, &rtree_ctx, ~((uintptr_t)0),
+ contents_b), "Unexpected rtree_write() failure");
+ rtree_contents_t read_contents_b = rtree_read(tsdn, rtree, &rtree_ctx,
+ ~((uintptr_t)0));
+ assert_true(contents_b.edata == read_contents_b.edata
+ && contents_b.metadata.szind == read_contents_b.metadata.szind
+ && contents_b.metadata.slab == read_contents_b.metadata.slab
+ && contents_b.metadata.is_head == read_contents_b.metadata.is_head
+ && contents_b.metadata.state == read_contents_b.metadata.state,
+ "rtree_read() should return previously set value");
- rtree_delete(tsdn, rtree);
+ base_delete(tsdn, base);
}
TEST_END
TEST_BEGIN(test_rtree_bits) {
tsdn_t *tsdn = tsdn_fetch();
+ base_t *base = base_new(tsdn, 0, &ehooks_default_extent_hooks,
+ /* metadata_use_hooks */ true);
+ expect_ptr_not_null(base, "Unexpected base_new failure");
uintptr_t keys[] = {PAGE, PAGE + 1,
PAGE + (((uintptr_t)1) << LG_PAGE) - 1};
-
- extent_t extent;
- extent_init(&extent, NULL, NULL, 0, false, SC_NSIZES, 0,
- extent_state_active, false, false, true, EXTENT_NOT_HEAD);
+ edata_t *edata_c = alloc_edata();
+ edata_init(edata_c, INVALID_ARENA_IND, NULL, 0, false, SC_NSIZES, 0,
+ extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD);
rtree_t *rtree = &test_rtree;
rtree_ctx_t rtree_ctx;
rtree_ctx_data_init(&rtree_ctx);
- assert_false(rtree_new(rtree, false), "Unexpected rtree_new() failure");
+ expect_false(rtree_new(rtree, base, false),
+ "Unexpected rtree_new() failure");
for (unsigned i = 0; i < sizeof(keys)/sizeof(uintptr_t); i++) {
- assert_false(rtree_write(tsdn, rtree, &rtree_ctx, keys[i],
- &extent, SC_NSIZES, false),
- "Unexpected rtree_write() failure");
+ rtree_contents_t contents;
+ contents.edata = edata_c;
+ contents.metadata.szind = SC_NSIZES;
+ contents.metadata.slab = false;
+ contents.metadata.is_head = false;
+ contents.metadata.state = extent_state_active;
+
+ expect_false(rtree_write(tsdn, rtree, &rtree_ctx, keys[i],
+ contents), "Unexpected rtree_write() failure");
for (unsigned j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) {
- assert_ptr_eq(rtree_extent_read(tsdn, rtree, &rtree_ctx,
- keys[j], true), &extent,
- "rtree_extent_read() should return previously set "
+ expect_ptr_eq(rtree_read(tsdn, rtree, &rtree_ctx,
+ keys[j]).edata, edata_c,
+ "rtree_edata_read() should return previously set "
"value and ignore insignificant key bits; i=%u, "
"j=%u, set key=%#"FMTxPTR", get key=%#"FMTxPTR, i,
j, keys[i], keys[j]);
}
- assert_ptr_null(rtree_extent_read(tsdn, rtree, &rtree_ctx,
- (((uintptr_t)2) << LG_PAGE), false),
+ expect_ptr_null(rtree_read(tsdn, rtree, &rtree_ctx,
+ (((uintptr_t)2) << LG_PAGE)).edata,
"Only leftmost rtree leaf should be set; i=%u", i);
rtree_clear(tsdn, rtree, &rtree_ctx, keys[i]);
}
- rtree_delete(tsdn, rtree);
+ base_delete(tsdn, base);
}
TEST_END
@@ -160,69 +154,136 @@ TEST_BEGIN(test_rtree_random) {
#define SEED 42
sfmt_t *sfmt = init_gen_rand(SEED);
tsdn_t *tsdn = tsdn_fetch();
+
+ base_t *base = base_new(tsdn, 0, &ehooks_default_extent_hooks,
+ /* metadata_use_hooks */ true);
+ expect_ptr_not_null(base, "Unexpected base_new failure");
+
uintptr_t keys[NSET];
rtree_t *rtree = &test_rtree;
rtree_ctx_t rtree_ctx;
rtree_ctx_data_init(&rtree_ctx);
- extent_t extent;
- extent_init(&extent, NULL, NULL, 0, false, SC_NSIZES, 0,
- extent_state_active, false, false, true, EXTENT_NOT_HEAD);
+ edata_t *edata_d = alloc_edata();
+ edata_init(edata_d, INVALID_ARENA_IND, NULL, 0, false, SC_NSIZES, 0,
+ extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD);
- assert_false(rtree_new(rtree, false), "Unexpected rtree_new() failure");
+ expect_false(rtree_new(rtree, base, false),
+ "Unexpected rtree_new() failure");
for (unsigned i = 0; i < NSET; i++) {
keys[i] = (uintptr_t)gen_rand64(sfmt);
rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree,
&rtree_ctx, keys[i], false, true);
- assert_ptr_not_null(elm,
+ expect_ptr_not_null(elm,
"Unexpected rtree_leaf_elm_lookup() failure");
- rtree_leaf_elm_write(tsdn, rtree, elm, &extent, SC_NSIZES,
- false);
- assert_ptr_eq(rtree_extent_read(tsdn, rtree, &rtree_ctx,
- keys[i], true), &extent,
- "rtree_extent_read() should return previously set value");
+ rtree_contents_t contents;
+ contents.edata = edata_d;
+ contents.metadata.szind = SC_NSIZES;
+ contents.metadata.slab = false;
+ contents.metadata.is_head = false;
+ contents.metadata.state = edata_state_get(edata_d);
+ rtree_leaf_elm_write(tsdn, rtree, elm, contents);
+ expect_ptr_eq(rtree_read(tsdn, rtree, &rtree_ctx,
+ keys[i]).edata, edata_d,
+ "rtree_edata_read() should return previously set value");
}
for (unsigned i = 0; i < NSET; i++) {
- assert_ptr_eq(rtree_extent_read(tsdn, rtree, &rtree_ctx,
- keys[i], true), &extent,
- "rtree_extent_read() should return previously set value, "
+ expect_ptr_eq(rtree_read(tsdn, rtree, &rtree_ctx,
+ keys[i]).edata, edata_d,
+ "rtree_edata_read() should return previously set value, "
"i=%u", i);
}
for (unsigned i = 0; i < NSET; i++) {
rtree_clear(tsdn, rtree, &rtree_ctx, keys[i]);
- assert_ptr_null(rtree_extent_read(tsdn, rtree, &rtree_ctx,
- keys[i], true),
- "rtree_extent_read() should return previously set value");
+ expect_ptr_null(rtree_read(tsdn, rtree, &rtree_ctx,
+ keys[i]).edata,
+ "rtree_edata_read() should return previously set value");
}
for (unsigned i = 0; i < NSET; i++) {
- assert_ptr_null(rtree_extent_read(tsdn, rtree, &rtree_ctx,
- keys[i], true),
- "rtree_extent_read() should return previously set value");
+ expect_ptr_null(rtree_read(tsdn, rtree, &rtree_ctx,
+ keys[i]).edata,
+ "rtree_edata_read() should return previously set value");
}
- rtree_delete(tsdn, rtree);
+ base_delete(tsdn, base);
fini_gen_rand(sfmt);
#undef NSET
#undef SEED
}
TEST_END
+static void
+test_rtree_range_write(tsdn_t *tsdn, rtree_t *rtree, uintptr_t start,
+ uintptr_t end) {
+ rtree_ctx_t rtree_ctx;
+ rtree_ctx_data_init(&rtree_ctx);
+
+ edata_t *edata_e = alloc_edata();
+ edata_init(edata_e, INVALID_ARENA_IND, NULL, 0, false, SC_NSIZES, 0,
+ extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD);
+ rtree_contents_t contents;
+ contents.edata = edata_e;
+ contents.metadata.szind = SC_NSIZES;
+ contents.metadata.slab = false;
+ contents.metadata.is_head = false;
+ contents.metadata.state = extent_state_active;
+
+ expect_false(rtree_write(tsdn, rtree, &rtree_ctx, start,
+ contents), "Unexpected rtree_write() failure");
+ expect_false(rtree_write(tsdn, rtree, &rtree_ctx, end,
+ contents), "Unexpected rtree_write() failure");
+
+ rtree_write_range(tsdn, rtree, &rtree_ctx, start, end, contents);
+ for (uintptr_t i = 0; i < ((end - start) >> LG_PAGE); i++) {
+ expect_ptr_eq(rtree_read(tsdn, rtree, &rtree_ctx,
+ start + (i << LG_PAGE)).edata, edata_e,
+ "rtree_edata_read() should return previously set value");
+ }
+ rtree_clear_range(tsdn, rtree, &rtree_ctx, start, end);
+ rtree_leaf_elm_t *elm;
+ for (uintptr_t i = 0; i < ((end - start) >> LG_PAGE); i++) {
+ elm = rtree_leaf_elm_lookup(tsdn, rtree, &rtree_ctx,
+ start + (i << LG_PAGE), false, false);
+ expect_ptr_not_null(elm, "Should have been initialized.");
+ expect_ptr_null(rtree_leaf_elm_read(tsdn, rtree, elm,
+ false).edata, "Should have been cleared.");
+ }
+}
+
+TEST_BEGIN(test_rtree_range) {
+ tsdn_t *tsdn = tsdn_fetch();
+ base_t *base = base_new(tsdn, 0, &ehooks_default_extent_hooks,
+ /* metadata_use_hooks */ true);
+ expect_ptr_not_null(base, "Unexpected base_new failure");
+
+ rtree_t *rtree = &test_rtree;
+ expect_false(rtree_new(rtree, base, false),
+ "Unexpected rtree_new() failure");
+
+ /* Not crossing rtree node boundary first. */
+ uintptr_t start = ZU(1) << rtree_leaf_maskbits();
+ uintptr_t end = start + (ZU(100) << LG_PAGE);
+ test_rtree_range_write(tsdn, rtree, start, end);
+
+ /* Crossing rtree node boundary. */
+ start = (ZU(1) << rtree_leaf_maskbits()) - (ZU(10) << LG_PAGE);
+ end = start + (ZU(100) << LG_PAGE);
+ assert_ptr_ne((void *)rtree_leafkey(start), (void *)rtree_leafkey(end),
+ "The range should span across two rtree nodes");
+ test_rtree_range_write(tsdn, rtree, start, end);
+
+ base_delete(tsdn, base);
+}
+TEST_END
+
int
main(void) {
- rtree_node_alloc_orig = rtree_node_alloc;
- rtree_node_alloc = rtree_node_alloc_intercept;
- rtree_node_dalloc_orig = rtree_node_dalloc;
- rtree_node_dalloc = rtree_node_dalloc_intercept;
- rtree_leaf_alloc_orig = rtree_leaf_alloc;
- rtree_leaf_alloc = rtree_leaf_alloc_intercept;
- rtree_leaf_dalloc_orig = rtree_leaf_dalloc;
- rtree_leaf_dalloc = rtree_leaf_dalloc_intercept;
-
return test(
test_rtree_read_empty,
test_rtree_extrema,
test_rtree_bits,
- test_rtree_random);
+ test_rtree_random,
+ test_rtree_range);
}
generated by cgit v1.3 (git 2.53.0) at 2026-09-07 16:22:52 +0000