project-base/server-skynet-source-3rd-jemalloc
2
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
master
server-skynet-source-3rd-je.../test/unit/rtree.c

290 lines
9.8 KiB
C
Raw Permalink Normal View History

Add rtree unit tests.
2014-01-03 08:08:28 +08:00
#include "test/jemalloc_test.h"
Header refactoring: unify and de-catchall rtree module.
2017-05-24 05:26:31 +08:00
#include "jemalloc/internal/rtree.h"
Extents: Break extent-struct/arena interactions Specifically, the extent_arena_[g|s]et functions and the address randomization. These are the only things that tie the extent struct itself to the arena code.
2019-09-21 09:20:22 +08:00
#define INVALID_ARENA_IND ((1U << MALLOCX_ARENA_BITS) - 1)
Embed root node into rtree_t. This avoids one atomic operation per tree access.
2017-03-23 07:38:03 +08:00
/* Potentially too large to safely place on the stack. */
rtree_t test_rtree;
Refactor rtree to always use base_alloc() for node allocation.
2016-04-16 15:36:11 +08:00
Update brace style. Add braces around single-line blocks, and remove line breaks before function-opening braces. This resolves #537.
2017-01-16 08:56:30 +08:00
TEST_BEGIN(test_rtree_read_empty) {
Refactor rtree to always use base_alloc() for node allocation.
2016-04-16 15:36:11 +08:00
tsdn_t *tsdn;
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
Refactor rtree to always use base_alloc() for node allocation.
2016-04-16 15:36:11 +08:00
tsdn = tsdn_fetch();
Small refactors around 7bb05e0.
2021-09-28 04:43:24 +08:00
base_t *base = base_new(tsdn, 0, &ehooks_default_extent_hooks,
/* metadata_use_hooks */ true);
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_ptr_not_null(base, "Unexpected base_new failure");
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
Embed root node into rtree_t. This avoids one atomic operation per tree access.
2017-03-23 07:38:03 +08:00
rtree_t *rtree = &test_rtree;
Add init function support to tsd members. This will facilitate embedding tcache into tsd, which will require proper initialization cannot be done via the static initializer. Make tsd->rtree_ctx to be initialized via rtree_ctx_data_init().
2017-03-30 04:18:02 +08:00
rtree_ctx_t rtree_ctx;
rtree_ctx_data_init(&rtree_ctx);
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_false(rtree_new(rtree, base, false),
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
"Unexpected rtree_new() failure");
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
rtree_contents_t contents;
expect_true(rtree_read_independent(tsdn, rtree, &rtree_ctx, PAGE,
&contents), "rtree_read_independent() should fail on empty rtree.");
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
base_delete(tsdn, base);
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
}
TEST_END
Add element acquire/release capabilities to rtree. This makes it possible to acquire short-term "ownership" of rtree elements so that it is possible to read an extent pointer *and* read the extent's contents with a guarantee that the element will not be modified until the ownership is released. This is intended as a mechanism for resolving rtree read/write races rather than as a way to lock extents.
2016-03-28 18:06:35 +08:00
#undef NTHREADS
#undef NITERS
#undef SEED
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
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;
}
Update brace style. Add braces around single-line blocks, and remove line breaks before function-opening braces. This resolves #537.
2017-01-16 08:56:30 +08:00
TEST_BEGIN(test_rtree_extrema) {
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
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,
Extents: Break extent-struct/arena interactions Specifically, the extent_arena_[g|s]et functions and the address randomization. These are the only things that tie the extent struct itself to the arena code.
2019-09-21 09:20:22 +08:00
false, sz_size2index(SC_LARGE_MINCLASS), 0,
Edata: rename "ranged" bit to "pai". This better represents its intended purpose; the hugepage allocator design evolved away from needing contiguity of hugepage virtual address space.
2020-07-10 09:07:17 +08:00
extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD);
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
edata_init(edata_b, INVALID_ARENA_IND, NULL, 0, false, SC_NSIZES, 0,
Edata: rename "ranged" bit to "pai". This better represents its intended purpose; the hugepage allocator design evolved away from needing contiguity of hugepage virtual address space.
2020-07-10 09:07:17 +08:00
extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD);
Refactor rtree to always use base_alloc() for node allocation.
2016-04-16 15:36:11 +08:00
Incorporate szind/slab into rtree leaves. Expand and restructure the rtree API such that all common operations can be achieved with minimal work, regardless of whether the rtree leaf fields are independent versus packed into a single atomic pointer.
2017-03-17 08:57:52 +08:00
tsdn_t *tsdn = tsdn_fetch();
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
Small refactors around 7bb05e0.
2021-09-28 04:43:24 +08:00
base_t *base = base_new(tsdn, 0, &ehooks_default_extent_hooks,
/* metadata_use_hooks */ true);
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_ptr_not_null(base, "Unexpected base_new failure");
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
Embed root node into rtree_t. This avoids one atomic operation per tree access.
2017-03-23 07:38:03 +08:00
rtree_t *rtree = &test_rtree;
Add init function support to tsd members. This will facilitate embedding tcache into tsd, which will require proper initialization cannot be done via the static initializer. Make tsd->rtree_ctx to be initialized via rtree_ctx_data_init().
2017-03-30 04:18:02 +08:00
rtree_ctx_t rtree_ctx;
rtree_ctx_data_init(&rtree_ctx);
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_false(rtree_new(rtree, base, false),
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
"Unexpected rtree_new() failure");
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
rtree_contents_t contents_a;
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
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);
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
expect_false(rtree_write(tsdn, rtree, &rtree_ctx, PAGE, contents_a),
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
"Unexpected rtree_write() failure");
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
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
Track extent is_head state in rtree leaf.
2021-02-27 07:11:58 +08:00
&& contents_a.metadata.slab == read_contents_a.metadata.slab
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
&& contents_a.metadata.is_head == read_contents_a.metadata.is_head
&& contents_a.metadata.state == read_contents_a.metadata.state,
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
"rtree_read() should return previously set value");
rtree_contents_t contents_b;
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
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);
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_false(rtree_write(tsdn, rtree, &rtree_ctx, ~((uintptr_t)0),
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
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
Track extent is_head state in rtree leaf.
2021-02-27 07:11:58 +08:00
&& contents_b.metadata.slab == read_contents_b.metadata.slab
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
&& contents_b.metadata.is_head == read_contents_b.metadata.is_head
&& contents_b.metadata.state == read_contents_b.metadata.state,
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
"rtree_read() should return previously set value");
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
base_delete(tsdn, base);
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
}
TEST_END
Update brace style. Add braces around single-line blocks, and remove line breaks before function-opening braces. This resolves #537.
2017-01-16 08:56:30 +08:00
TEST_BEGIN(test_rtree_bits) {
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
tsdn_t *tsdn = tsdn_fetch();
Small refactors around 7bb05e0.
2021-09-28 04:43:24 +08:00
base_t *base = base_new(tsdn, 0, &ehooks_default_extent_hooks,
/* metadata_use_hooks */ true);
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_ptr_not_null(base, "Unexpected base_new failure");
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
Remove rtree support for 0 (NULL) keys. NULL can never actually be inserted in practice, and removing support allows a branch to be removed from the fast path.
2017-02-05 18:50:59 +08:00
uintptr_t keys[] = {PAGE, PAGE + 1,
PAGE + (((uintptr_t)1) << LG_PAGE) - 1};
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
edata_t *edata_c = alloc_edata();
edata_init(edata_c, INVALID_ARENA_IND, NULL, 0, false, SC_NSIZES, 0,
Edata: rename "ranged" bit to "pai". This better represents its intended purpose; the hugepage allocator design evolved away from needing contiguity of hugepage virtual address space.
2020-07-10 09:07:17 +08:00
extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD);
Incorporate szind/slab into rtree leaves. Expand and restructure the rtree API such that all common operations can be achieved with minimal work, regardless of whether the rtree leaf fields are independent versus packed into a single atomic pointer.
2017-03-17 08:57:52 +08:00
Embed root node into rtree_t. This avoids one atomic operation per tree access.
2017-03-23 07:38:03 +08:00
rtree_t *rtree = &test_rtree;
Add init function support to tsd members. This will facilitate embedding tcache into tsd, which will require proper initialization cannot be done via the static initializer. Make tsd->rtree_ctx to be initialized via rtree_ctx_data_init().
2017-03-30 04:18:02 +08:00
rtree_ctx_t rtree_ctx;
rtree_ctx_data_init(&rtree_ctx);
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_false(rtree_new(rtree, base, false),
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
"Unexpected rtree_new() failure");
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
for (unsigned i = 0; i < sizeof(keys)/sizeof(uintptr_t); i++) {
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
rtree_contents_t contents;
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
contents.edata = edata_c;
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
contents.metadata.szind = SC_NSIZES;
contents.metadata.slab = false;
Track extent is_head state in rtree leaf.
2021-02-27 07:11:58 +08:00
contents.metadata.is_head = false;
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
contents.metadata.state = extent_state_active;
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_false(rtree_write(tsdn, rtree, &rtree_ctx, keys[i],
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
contents), "Unexpected rtree_write() failure");
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
for (unsigned j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) {
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
expect_ptr_eq(rtree_read(tsdn, rtree, &rtree_ctx,
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
keys[j]).edata, edata_c,
Rename extent_t to edata_t. This frees us up from the unfortunate extent/extent2 naming collision.
2019-12-10 06:36:45 +08:00
"rtree_edata_read() should return previously set "
Embed root node into rtree_t. This avoids one atomic operation per tree access.
2017-03-23 07:38:03 +08:00
"value and ignore insignificant key bits; i=%u, "
"j=%u, set key=%#"FMTxPTR", get key=%#"FMTxPTR, i,
j, keys[i], keys[j]);
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
}
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
expect_ptr_null(rtree_read(tsdn, rtree, &rtree_ctx,
(((uintptr_t)2) << LG_PAGE)).edata,
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
"Only leftmost rtree leaf should be set; i=%u", i);
Embed root node into rtree_t. This avoids one atomic operation per tree access.
2017-03-23 07:38:03 +08:00
rtree_clear(tsdn, rtree, &rtree_ctx, keys[i]);
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
}
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
base_delete(tsdn, base);
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
}
TEST_END
Update brace style. Add braces around single-line blocks, and remove line breaks before function-opening braces. This resolves #537.
2017-01-16 08:56:30 +08:00
TEST_BEGIN(test_rtree_random) {
Replace tabs following #define with spaces. This resolves #564.
2017-01-20 13:41:41 +08:00
#define NSET 16
#define SEED 42
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
sfmt_t *sfmt = init_gen_rand(SEED);
tsdn_t *tsdn = tsdn_fetch();
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
Small refactors around 7bb05e0.
2021-09-28 04:43:24 +08:00
base_t *base = base_new(tsdn, 0, &ehooks_default_extent_hooks,
/* metadata_use_hooks */ true);
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_ptr_not_null(base, "Unexpected base_new failure");
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
uintptr_t keys[NSET];
Embed root node into rtree_t. This avoids one atomic operation per tree access.
2017-03-23 07:38:03 +08:00
rtree_t *rtree = &test_rtree;
Add init function support to tsd members. This will facilitate embedding tcache into tsd, which will require proper initialization cannot be done via the static initializer. Make tsd->rtree_ctx to be initialized via rtree_ctx_data_init().
2017-03-30 04:18:02 +08:00
rtree_ctx_t rtree_ctx;
rtree_ctx_data_init(&rtree_ctx);
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
edata_t *edata_d = alloc_edata();
edata_init(edata_d, INVALID_ARENA_IND, NULL, 0, false, SC_NSIZES, 0,
Edata: rename "ranged" bit to "pai". This better represents its intended purpose; the hugepage allocator design evolved away from needing contiguity of hugepage virtual address space.
2020-07-10 09:07:17 +08:00
extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD);
Incorporate szind/slab into rtree leaves. Expand and restructure the rtree API such that all common operations can be achieved with minimal work, regardless of whether the rtree leaf fields are independent versus packed into a single atomic pointer.
2017-03-17 08:57:52 +08:00
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_false(rtree_new(rtree, base, false),
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
"Unexpected rtree_new() failure");
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
for (unsigned i = 0; i < NSET; i++) {
keys[i] = (uintptr_t)gen_rand64(sfmt);
Protect the rtree/extent interactions with a mutex pool. Instead of embedding a lock bit in rtree leaf elements, we associate extents with a small set of mutexes. This gets us two things: - We can use the system mutexes. This (hypothetically) protects us from priority inversion, and lets us stop doing a backoff/sleep loop, instead opting for precise wakeups from the mutex. - Cuts down on the number of mutex acquisitions we have to do (from 4 in the worst case to two). We end up simplifying most of the rtree code (which no longer has to deal with locking or concurrency at all), at the cost of additional complexity in the extent code: since the mutex protecting the rtree leaf elements is determined by reading the extent out of those elements, the initial read is racy, so that we may acquire an out of date mutex. We re-check the extent in the leaf after acquiring the mutex to protect us from this race.
2017-05-16 05:23:51 +08:00
rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree,
Split rtree_elm_t into rtree_{node,leaf}_elm_t. This allows leaf elements to differ in size from internal node elements. In principle it would be more correct to use a different type for each level of the tree, but due to implementation details related to atomic operations, we use casts anyway, thus counteracting the value of additional type correctness. Furthermore, such a scheme would require function code generation (via cpp macros), as well as either unwieldy type names for leaves or type aliases, e.g. typedef struct rtree_elm_d2_s rtree_leaf_elm_t; This alternate strategy would be more correct, and with less code duplication, but probably not worth the complexity.
2017-03-17 00:46:42 +08:00
&rtree_ctx, keys[i], false, true);
Change assert_* to expect_* in tests ``` grep -Irl assert_ test/ | xargs sed -i \ 's/witness_assert/witness_do_not_replace/g'; grep -Irl assert_ test/ | xargs sed -i \ 's/malloc_mutex_assert_owner/malloc_mutex_do_not_replace_owner/g'; grep -Ir assert_ test/ | grep -o "[_a-zA-Z]*assert_[_a-zA-Z]*" | \ grep -v "^assert_"; # confirm no output grep -Irl assert_ test/ | xargs sed -i 's/assert_/expect_/g'; grep -Irl witness_do_not_replace test/ | xargs sed -i \ 's/witness_do_not_replace/witness_assert/g'; grep -Irl malloc_mutex_do_not_replace_owner test/ | xargs sed -i \ 's/malloc_mutex_do_not_replace_owner/malloc_mutex_assert_owner/g'; ```
2020-02-19 06:39:06 +08:00
expect_ptr_not_null(elm,
Protect the rtree/extent interactions with a mutex pool. Instead of embedding a lock bit in rtree leaf elements, we associate extents with a small set of mutexes. This gets us two things: - We can use the system mutexes. This (hypothetically) protects us from priority inversion, and lets us stop doing a backoff/sleep loop, instead opting for precise wakeups from the mutex. - Cuts down on the number of mutex acquisitions we have to do (from 4 in the worst case to two). We end up simplifying most of the rtree code (which no longer has to deal with locking or concurrency at all), at the cost of additional complexity in the extent code: since the mutex protecting the rtree leaf elements is determined by reading the extent out of those elements, the initial read is racy, so that we may acquire an out of date mutex. We re-check the extent in the leaf after acquiring the mutex to protect us from this race.
2017-05-16 05:23:51 +08:00
"Unexpected rtree_leaf_elm_lookup() failure");
Rtree: Clean up compact/non-compact split.
2020-03-16 06:49:42 +08:00
rtree_contents_t contents;
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
contents.edata = edata_d;
Rtree: Clean up compact/non-compact split.
2020-03-16 06:49:42 +08:00
contents.metadata.szind = SC_NSIZES;
contents.metadata.slab = false;
Track extent is_head state in rtree leaf.
2021-02-27 07:11:58 +08:00
contents.metadata.is_head = false;
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
contents.metadata.state = edata_state_get(edata_d);
Rtree: Pull leaf contents into their own struct.
2020-03-14 02:47:51 +08:00
rtree_leaf_elm_write(tsdn, rtree, elm, contents);
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
expect_ptr_eq(rtree_read(tsdn, rtree, &rtree_ctx,
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
keys[i]).edata, edata_d,
Rename extent_t to edata_t. This frees us up from the unfortunate extent/extent2 naming collision.
2019-12-10 06:36:45 +08:00
"rtree_edata_read() should return previously set value");
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
}
for (unsigned i = 0; i < NSET; i++) {
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
expect_ptr_eq(rtree_read(tsdn, rtree, &rtree_ctx,
Store edata->state in rtree leaf and make edata_t 128B aligned. Verified that this doesn't result in any real increase of edata_t bytes allocated.
2021-02-27 07:32:41 +08:00
keys[i]).edata, edata_d,
Rename extent_t to edata_t. This frees us up from the unfortunate extent/extent2 naming collision.
2019-12-10 06:36:45 +08:00
"rtree_edata_read() should return previously set value, "
Incorporate szind/slab into rtree leaves. Expand and restructure the rtree API such that all common operations can be achieved with minimal work, regardless of whether the rtree leaf fields are independent versus packed into a single atomic pointer.
2017-03-17 08:57:52 +08:00
"i=%u", i);
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
}
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
for (unsigned i = 0; i < NSET; i++) {
Embed root node into rtree_t. This avoids one atomic operation per tree access.
2017-03-23 07:38:03 +08:00
rtree_clear(tsdn, rtree, &rtree_ctx, keys[i]);
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
expect_ptr_null(rtree_read(tsdn, rtree, &rtree_ctx,
keys[i]).edata,
Rename extent_t to edata_t. This frees us up from the unfortunate extent/extent2 naming collision.
2019-12-10 06:36:45 +08:00
"rtree_edata_read() should return previously set value");
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
}
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
for (unsigned i = 0; i < NSET; i++) {
Rtree: Remove the per-field accessors. We instead split things into "edata" and "metadata".
2020-03-20 08:58:44 +08:00
expect_ptr_null(rtree_read(tsdn, rtree, &rtree_ctx,
keys[i]).edata,
Rename extent_t to edata_t. This frees us up from the unfortunate extent/extent2 naming collision.
2019-12-10 06:36:45 +08:00
"rtree_edata_read() should return previously set value");
Determine rtree levels at compile time. Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
2017-02-07 05:17:12 +08:00
}
Rtree: take the base allocator as a parameter. This facilitates better testing by avoiding mixing of the "real" base with the base used by the rtree under test.
2020-02-18 05:11:10 +08:00
base_delete(tsdn, base);
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
fini_gen_rand(sfmt);
#undef NSET
#undef SEED
}
TEST_END
Add rtree_write_range(): writing the same content to multiple leaf elements. Apply to emap_(de)register_interior which became noticeable in perf profiles.
2021-03-18 07:35:57 +08:00
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();
Small refactors around 7bb05e0.
2021-09-28 04:43:24 +08:00
base_t *base = base_new(tsdn, 0, &ehooks_default_extent_hooks,
/* metadata_use_hooks */ true);
Add rtree_write_range(): writing the same content to multiple leaf elements. Apply to emap_(de)register_interior which became noticeable in perf profiles.
2021-03-18 07:35:57 +08:00
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
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
int
Update brace style. Add braces around single-line blocks, and remove line breaks before function-opening braces. This resolves #537.
2017-01-16 08:56:30 +08:00
main(void) {
Remove extraneous parens around return arguments. This resolves #540.
2017-01-20 10:15:45 +08:00
return test(
Add element acquire/release capabilities to rtree. This makes it possible to acquire short-term "ownership" of rtree elements so that it is possible to read an extent pointer *and* read the extent's contents with a guarantee that the element will not be modified until the ownership is released. This is intended as a mechanism for resolving rtree read/write races rather than as a way to lock extents.
2016-03-28 18:06:35 +08:00
test_rtree_read_empty,
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
test_rtree_extrema,
test_rtree_bits,
Add rtree_write_range(): writing the same content to multiple leaf elements. Apply to emap_(de)register_interior which became noticeable in perf profiles.
2021-03-18 07:35:57 +08:00
test_rtree_random,
test_rtree_range);
Add rtree unit tests.
2014-01-03 08:08:28 +08:00
}
Reference in New Issue Copy Permalink