diff options
Diffstat (limited to 'examples/redis-unstable/deps/jemalloc/src/emap.c')
| -rw-r--r-- | examples/redis-unstable/deps/jemalloc/src/emap.c | 386 |
1 files changed, 0 insertions, 386 deletions
diff --git a/examples/redis-unstable/deps/jemalloc/src/emap.c b/examples/redis-unstable/deps/jemalloc/src/emap.c deleted file mode 100644 index 9cc95a7..0000000 --- a/examples/redis-unstable/deps/jemalloc/src/emap.c +++ /dev/null @@ -1,386 +0,0 @@ -#include "jemalloc/internal/jemalloc_preamble.h" -#include "jemalloc/internal/jemalloc_internal_includes.h" - -#include "jemalloc/internal/emap.h" - -enum emap_lock_result_e { - emap_lock_result_success, - emap_lock_result_failure, - emap_lock_result_no_extent -}; -typedef enum emap_lock_result_e emap_lock_result_t; - -bool -emap_init(emap_t *emap, base_t *base, bool zeroed) { - return rtree_new(&emap->rtree, base, zeroed); -} - -void -emap_update_edata_state(tsdn_t *tsdn, emap_t *emap, edata_t *edata, - extent_state_t state) { - witness_assert_positive_depth_to_rank(tsdn_witness_tsdp_get(tsdn), - WITNESS_RANK_CORE); - - edata_state_set(edata, state); - - EMAP_DECLARE_RTREE_CTX; - rtree_leaf_elm_t *elm1 = rtree_leaf_elm_lookup(tsdn, &emap->rtree, - rtree_ctx, (uintptr_t)edata_base_get(edata), /* dependent */ true, - /* init_missing */ false); - assert(elm1 != NULL); - rtree_leaf_elm_t *elm2 = edata_size_get(edata) == PAGE ? NULL : - rtree_leaf_elm_lookup(tsdn, &emap->rtree, rtree_ctx, - (uintptr_t)edata_last_get(edata), /* dependent */ true, - /* init_missing */ false); - - rtree_leaf_elm_state_update(tsdn, &emap->rtree, elm1, elm2, state); - - emap_assert_mapped(tsdn, emap, edata); -} - -static inline edata_t * -emap_try_acquire_edata_neighbor_impl(tsdn_t *tsdn, emap_t *emap, edata_t *edata, - extent_pai_t pai, extent_state_t expected_state, bool forward, - bool expanding) { - witness_assert_positive_depth_to_rank(tsdn_witness_tsdp_get(tsdn), - WITNESS_RANK_CORE); - assert(!edata_guarded_get(edata)); - assert(!expanding || forward); - assert(!edata_state_in_transition(expected_state)); - assert(expected_state == extent_state_dirty || - expected_state == extent_state_muzzy || - expected_state == extent_state_retained); - - void *neighbor_addr = forward ? edata_past_get(edata) : - edata_before_get(edata); - /* - * This is subtle; the rtree code asserts that its input pointer is - * non-NULL, and this is a useful thing to check. But it's possible - * that edata corresponds to an address of (void *)PAGE (in practice, - * this has only been observed on FreeBSD when address-space - * randomization is on, but it could in principle happen anywhere). In - * this case, edata_before_get(edata) is NULL, triggering the assert. - */ - if (neighbor_addr == NULL) { - return NULL; - } - - EMAP_DECLARE_RTREE_CTX; - rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, &emap->rtree, - rtree_ctx, (uintptr_t)neighbor_addr, /* dependent*/ false, - /* init_missing */ false); - if (elm == NULL) { - return NULL; - } - - rtree_contents_t neighbor_contents = rtree_leaf_elm_read(tsdn, - &emap->rtree, elm, /* dependent */ true); - if (!extent_can_acquire_neighbor(edata, neighbor_contents, pai, - expected_state, forward, expanding)) { - return NULL; - } - - /* From this point, the neighbor edata can be safely acquired. */ - edata_t *neighbor = neighbor_contents.edata; - assert(edata_state_get(neighbor) == expected_state); - emap_update_edata_state(tsdn, emap, neighbor, extent_state_merging); - if (expanding) { - extent_assert_can_expand(edata, neighbor); - } else { - extent_assert_can_coalesce(edata, neighbor); - } - - return neighbor; -} - -edata_t * -emap_try_acquire_edata_neighbor(tsdn_t *tsdn, emap_t *emap, edata_t *edata, - extent_pai_t pai, extent_state_t expected_state, bool forward) { - return emap_try_acquire_edata_neighbor_impl(tsdn, emap, edata, pai, - expected_state, forward, /* expand */ false); -} - -edata_t * -emap_try_acquire_edata_neighbor_expand(tsdn_t *tsdn, emap_t *emap, - edata_t *edata, extent_pai_t pai, extent_state_t expected_state) { - /* Try expanding forward. */ - return emap_try_acquire_edata_neighbor_impl(tsdn, emap, edata, pai, - expected_state, /* forward */ true, /* expand */ true); -} - -void -emap_release_edata(tsdn_t *tsdn, emap_t *emap, edata_t *edata, - extent_state_t new_state) { - assert(emap_edata_in_transition(tsdn, emap, edata)); - assert(emap_edata_is_acquired(tsdn, emap, edata)); - - emap_update_edata_state(tsdn, emap, edata, new_state); -} - -static bool -emap_rtree_leaf_elms_lookup(tsdn_t *tsdn, emap_t *emap, rtree_ctx_t *rtree_ctx, - const edata_t *edata, bool dependent, bool init_missing, - rtree_leaf_elm_t **r_elm_a, rtree_leaf_elm_t **r_elm_b) { - *r_elm_a = rtree_leaf_elm_lookup(tsdn, &emap->rtree, rtree_ctx, - (uintptr_t)edata_base_get(edata), dependent, init_missing); - if (!dependent && *r_elm_a == NULL) { - return true; - } - assert(*r_elm_a != NULL); - - *r_elm_b = rtree_leaf_elm_lookup(tsdn, &emap->rtree, rtree_ctx, - (uintptr_t)edata_last_get(edata), dependent, init_missing); - if (!dependent && *r_elm_b == NULL) { - return true; - } - assert(*r_elm_b != NULL); - - return false; -} - -static void -emap_rtree_write_acquired(tsdn_t *tsdn, emap_t *emap, rtree_leaf_elm_t *elm_a, - rtree_leaf_elm_t *elm_b, edata_t *edata, szind_t szind, bool slab) { - rtree_contents_t contents; - contents.edata = edata; - contents.metadata.szind = szind; - contents.metadata.slab = slab; - contents.metadata.is_head = (edata == NULL) ? false : - edata_is_head_get(edata); - contents.metadata.state = (edata == NULL) ? 0 : edata_state_get(edata); - rtree_leaf_elm_write(tsdn, &emap->rtree, elm_a, contents); - if (elm_b != NULL) { - rtree_leaf_elm_write(tsdn, &emap->rtree, elm_b, contents); - } -} - -bool -emap_register_boundary(tsdn_t *tsdn, emap_t *emap, edata_t *edata, - szind_t szind, bool slab) { - assert(edata_state_get(edata) == extent_state_active); - EMAP_DECLARE_RTREE_CTX; - - rtree_leaf_elm_t *elm_a, *elm_b; - bool err = emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, edata, - false, true, &elm_a, &elm_b); - if (err) { - return true; - } - assert(rtree_leaf_elm_read(tsdn, &emap->rtree, elm_a, - /* dependent */ false).edata == NULL); - assert(rtree_leaf_elm_read(tsdn, &emap->rtree, elm_b, - /* dependent */ false).edata == NULL); - emap_rtree_write_acquired(tsdn, emap, elm_a, elm_b, edata, szind, slab); - return false; -} - -/* Invoked *after* emap_register_boundary. */ -void -emap_register_interior(tsdn_t *tsdn, emap_t *emap, edata_t *edata, - szind_t szind) { - EMAP_DECLARE_RTREE_CTX; - - assert(edata_slab_get(edata)); - assert(edata_state_get(edata) == extent_state_active); - - if (config_debug) { - /* Making sure the boundary is registered already. */ - rtree_leaf_elm_t *elm_a, *elm_b; - bool err = emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, - edata, /* dependent */ true, /* init_missing */ false, - &elm_a, &elm_b); - assert(!err); - rtree_contents_t contents_a, contents_b; - contents_a = rtree_leaf_elm_read(tsdn, &emap->rtree, elm_a, - /* dependent */ true); - contents_b = rtree_leaf_elm_read(tsdn, &emap->rtree, elm_b, - /* dependent */ true); - assert(contents_a.edata == edata && contents_b.edata == edata); - assert(contents_a.metadata.slab && contents_b.metadata.slab); - } - - rtree_contents_t contents; - contents.edata = edata; - contents.metadata.szind = szind; - contents.metadata.slab = true; - contents.metadata.state = extent_state_active; - contents.metadata.is_head = false; /* Not allowed to access. */ - - assert(edata_size_get(edata) > (2 << LG_PAGE)); - rtree_write_range(tsdn, &emap->rtree, rtree_ctx, - (uintptr_t)edata_base_get(edata) + PAGE, - (uintptr_t)edata_last_get(edata) - PAGE, contents); -} - -void -emap_deregister_boundary(tsdn_t *tsdn, emap_t *emap, edata_t *edata) { - /* - * The edata must be either in an acquired state, or protected by state - * based locks. - */ - if (!emap_edata_is_acquired(tsdn, emap, edata)) { - witness_assert_positive_depth_to_rank( - tsdn_witness_tsdp_get(tsdn), WITNESS_RANK_CORE); - } - - EMAP_DECLARE_RTREE_CTX; - rtree_leaf_elm_t *elm_a, *elm_b; - - emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, edata, - true, false, &elm_a, &elm_b); - emap_rtree_write_acquired(tsdn, emap, elm_a, elm_b, NULL, SC_NSIZES, - false); -} - -void -emap_deregister_interior(tsdn_t *tsdn, emap_t *emap, edata_t *edata) { - EMAP_DECLARE_RTREE_CTX; - - assert(edata_slab_get(edata)); - if (edata_size_get(edata) > (2 << LG_PAGE)) { - rtree_clear_range(tsdn, &emap->rtree, rtree_ctx, - (uintptr_t)edata_base_get(edata) + PAGE, - (uintptr_t)edata_last_get(edata) - PAGE); - } -} - -void -emap_remap(tsdn_t *tsdn, emap_t *emap, edata_t *edata, szind_t szind, - bool slab) { - EMAP_DECLARE_RTREE_CTX; - - if (szind != SC_NSIZES) { - rtree_contents_t contents; - contents.edata = edata; - contents.metadata.szind = szind; - contents.metadata.slab = slab; - contents.metadata.is_head = edata_is_head_get(edata); - contents.metadata.state = edata_state_get(edata); - - rtree_write(tsdn, &emap->rtree, rtree_ctx, - (uintptr_t)edata_addr_get(edata), contents); - /* - * Recall that this is called only for active->inactive and - * inactive->active transitions (since only active extents have - * meaningful values for szind and slab). Active, non-slab - * extents only need to handle lookups at their head (on - * deallocation), so we don't bother filling in the end - * boundary. - * - * For slab extents, we do the end-mapping change. This still - * leaves the interior unmodified; an emap_register_interior - * call is coming in those cases, though. - */ - if (slab && edata_size_get(edata) > PAGE) { - uintptr_t key = (uintptr_t)edata_past_get(edata) - - (uintptr_t)PAGE; - rtree_write(tsdn, &emap->rtree, rtree_ctx, key, - contents); - } - } -} - -bool -emap_split_prepare(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare, - edata_t *edata, size_t size_a, edata_t *trail, size_t size_b) { - EMAP_DECLARE_RTREE_CTX; - - /* - * We use incorrect constants for things like arena ind, zero, ranged, - * and commit state, and head status. This is a fake edata_t, used to - * facilitate a lookup. - */ - edata_t lead = {0}; - edata_init(&lead, 0U, edata_addr_get(edata), size_a, false, 0, 0, - extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD); - - emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, &lead, false, true, - &prepare->lead_elm_a, &prepare->lead_elm_b); - emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, trail, false, true, - &prepare->trail_elm_a, &prepare->trail_elm_b); - - if (prepare->lead_elm_a == NULL || prepare->lead_elm_b == NULL - || prepare->trail_elm_a == NULL || prepare->trail_elm_b == NULL) { - return true; - } - return false; -} - -void -emap_split_commit(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare, - edata_t *lead, size_t size_a, edata_t *trail, size_t size_b) { - /* - * We should think about not writing to the lead leaf element. We can - * get into situations where a racing realloc-like call can disagree - * with a size lookup request. I think it's fine to declare that these - * situations are race bugs, but there's an argument to be made that for - * things like xallocx, a size lookup call should return either the old - * size or the new size, but not anything else. - */ - emap_rtree_write_acquired(tsdn, emap, prepare->lead_elm_a, - prepare->lead_elm_b, lead, SC_NSIZES, /* slab */ false); - emap_rtree_write_acquired(tsdn, emap, prepare->trail_elm_a, - prepare->trail_elm_b, trail, SC_NSIZES, /* slab */ false); -} - -void -emap_merge_prepare(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare, - edata_t *lead, edata_t *trail) { - EMAP_DECLARE_RTREE_CTX; - emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, lead, true, false, - &prepare->lead_elm_a, &prepare->lead_elm_b); - emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, trail, true, false, - &prepare->trail_elm_a, &prepare->trail_elm_b); -} - -void -emap_merge_commit(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare, - edata_t *lead, edata_t *trail) { - rtree_contents_t clear_contents; - clear_contents.edata = NULL; - clear_contents.metadata.szind = SC_NSIZES; - clear_contents.metadata.slab = false; - clear_contents.metadata.is_head = false; - clear_contents.metadata.state = (extent_state_t)0; - - if (prepare->lead_elm_b != NULL) { - rtree_leaf_elm_write(tsdn, &emap->rtree, - prepare->lead_elm_b, clear_contents); - } - - rtree_leaf_elm_t *merged_b; - if (prepare->trail_elm_b != NULL) { - rtree_leaf_elm_write(tsdn, &emap->rtree, - prepare->trail_elm_a, clear_contents); - merged_b = prepare->trail_elm_b; - } else { - merged_b = prepare->trail_elm_a; - } - - emap_rtree_write_acquired(tsdn, emap, prepare->lead_elm_a, merged_b, - lead, SC_NSIZES, false); -} - -void -emap_do_assert_mapped(tsdn_t *tsdn, emap_t *emap, edata_t *edata) { - EMAP_DECLARE_RTREE_CTX; - - rtree_contents_t contents = rtree_read(tsdn, &emap->rtree, rtree_ctx, - (uintptr_t)edata_base_get(edata)); - assert(contents.edata == edata); - assert(contents.metadata.is_head == edata_is_head_get(edata)); - assert(contents.metadata.state == edata_state_get(edata)); -} - -void -emap_do_assert_not_mapped(tsdn_t *tsdn, emap_t *emap, edata_t *edata) { - emap_full_alloc_ctx_t context1 = {0}; - emap_full_alloc_ctx_try_lookup(tsdn, emap, edata_base_get(edata), - &context1); - assert(context1.edata == NULL); - - emap_full_alloc_ctx_t context2 = {0}; - emap_full_alloc_ctx_try_lookup(tsdn, emap, edata_last_get(edata), - &context2); - assert(context2.edata == NULL); -} |