#include "test/jemalloc_test.h"

#include "jemalloc/internal/rtree.h"

#define INVALID_ARENA_IND ((1U << MALLOCX_ARENA_BITS) - 1)

/* Potentially too large to safely place on the stack. */
rtree_t test_rtree;

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);
       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

#undef NTHREADS
#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) {
       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);
       expect_false(rtree_new(rtree, base, false),
           "Unexpected rtree_new() failure");

       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_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");

       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");

       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};
       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);
       expect_false(rtree_new(rtree, base, false),
           "Unexpected rtree_new() failure");

       for (unsigned i = 0; i < sizeof(keys)/sizeof(uintptr_t); i++) {
               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++) {
                       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]);
               }
               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]);
       }

       base_delete(tsdn, base);
}
TEST_END

TEST_BEGIN(test_rtree_random) {
#define NSET 16
#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);

       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);

       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);
               expect_ptr_not_null(elm,
                   "Unexpected rtree_leaf_elm_lookup() failure");
               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++) {
               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]);
               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++) {
               expect_ptr_null(rtree_read(tsdn, rtree, &rtree_ctx,
                   keys[i]).edata,
                   "rtree_edata_read() should return previously set value");
       }

       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) {
       return test(
           test_rtree_read_empty,
           test_rtree_extrema,
           test_rtree_bits,
           test_rtree_random,
           test_rtree_range);
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.