#define JEMALLOC_EXTENT_C_

#include "jemalloc/internal/jemalloc_preamble.h"

#include "jemalloc/internal/jemalloc_internal_includes.h"

#include "jemalloc/internal/assert.h"

#include "jemalloc/internal/extent_dss.h"

#include "jemalloc/internal/extent_mmap.h"

#include "jemalloc/internal/ph.h"

#include "jemalloc/internal/rtree.h"

#include "jemalloc/internal/mutex.h"

#include "jemalloc/internal/mutex_pool.h"

/******************************************************************************/

/* Data. */

rtree_t		extents_rtree;

/* Keyed by the address of the extent_t being protected. */

mutex_pool_t	extent_mutex_pool;

size_t opt_lg_extent_max_active_fit = LG_EXTENT_MAX_ACTIVE_FIT_DEFAULT;

static const bitmap_info_t extents_bitmap_info =

    BITMAP_INFO_INITIALIZER(SC_NPSIZES+1);

static void *extent_alloc_default(extent_hooks_t *extent_hooks, void *new_addr,

    size_t size, size_t alignment, bool *zero, bool *commit,

    unsigned arena_ind);

static bool extent_dalloc_default(extent_hooks_t *extent_hooks, void *addr,

    size_t size, bool committed, unsigned arena_ind);

static void extent_destroy_default(extent_hooks_t *extent_hooks, void *addr,

    size_t size, bool committed, unsigned arena_ind);

static bool extent_commit_default(extent_hooks_t *extent_hooks, void *addr,

    size_t size, size_t offset, size_t length, unsigned arena_ind);

static bool extent_commit_impl(tsdn_t *tsdn, arena_t *arena,

    extent_hooks_t **r_extent_hooks, extent_t *extent, size_t offset,

    size_t length, bool growing_retained);

static bool extent_decommit_default(extent_hooks_t *extent_hooks,

    void *addr, size_t size, size_t offset, size_t length, unsigned arena_ind);

#ifdef PAGES_CAN_PURGE_LAZY

static bool extent_purge_lazy_default(extent_hooks_t *extent_hooks, void *addr,

    size_t size, size_t offset, size_t length, unsigned arena_ind);

#endif

static bool extent_purge_lazy_impl(tsdn_t *tsdn, arena_t *arena,

    extent_hooks_t **r_extent_hooks, extent_t *extent, size_t offset,

    size_t length, bool growing_retained);

#ifdef PAGES_CAN_PURGE_FORCED

static bool extent_purge_forced_default(extent_hooks_t *extent_hooks,

    void *addr, size_t size, size_t offset, size_t length, unsigned arena_ind);

#endif

static bool extent_purge_forced_impl(tsdn_t *tsdn, arena_t *arena,

    extent_hooks_t **r_extent_hooks, extent_t *extent, size_t offset,

    size_t length, bool growing_retained);

static bool extent_split_default(extent_hooks_t *extent_hooks, void *addr,

    size_t size, size_t size_a, size_t size_b, bool committed,

    unsigned arena_ind);

static extent_t *extent_split_impl(tsdn_t *tsdn, arena_t *arena,

    extent_hooks_t **r_extent_hooks, extent_t *extent, size_t size_a,

    szind_t szind_a, bool slab_a, size_t size_b, szind_t szind_b, bool slab_b,

    bool growing_retained);

static bool extent_merge_default(extent_hooks_t *extent_hooks, void *addr_a,

    size_t size_a, void *addr_b, size_t size_b, bool committed,

    unsigned arena_ind);

static bool extent_merge_impl(tsdn_t *tsdn, arena_t *arena,

    extent_hooks_t **r_extent_hooks, extent_t *a, extent_t *b,

    bool growing_retained);

const extent_hooks_t	extent_hooks_default = {

	extent_alloc_default,

	extent_dalloc_default,

	extent_destroy_default,

	extent_commit_default,

	extent_decommit_default

#ifdef PAGES_CAN_PURGE_LAZY

	,

	extent_purge_lazy_default

#else

	,

	NULL

#endif

#ifdef PAGES_CAN_PURGE_FORCED

	,

	extent_purge_forced_default

#else

	,

	NULL

#endif

	,

	extent_split_default,

	extent_merge_default

};

/* Used exclusively for gdump triggering. */

static atomic_zu_t curpages;

static atomic_zu_t highpages;

/******************************************************************************/

/*

 * Function prototypes for static functions that are referenced prior to

 * definition.

 */

static void extent_deregister(tsdn_t *tsdn, extent_t *extent);

static extent_t *extent_recycle(tsdn_t *tsdn, arena_t *arena,

    extent_hooks_t **r_extent_hooks, extents_t *extents, void *new_addr,

    size_t usize, size_t pad, size_t alignment, bool slab, szind_t szind,

    bool *zero, bool *commit, bool growing_retained);

static extent_t *extent_try_coalesce(tsdn_t *tsdn, arena_t *arena,

    extent_hooks_t **r_extent_hooks, rtree_ctx_t *rtree_ctx, extents_t *extents,

    extent_t *extent, bool *coalesced, bool growing_retained);

static void extent_record(tsdn_t *tsdn, arena_t *arena,

    extent_hooks_t **r_extent_hooks, extents_t *extents, extent_t *extent,

    bool growing_retained);

/******************************************************************************/

#define ATTR_NONE /* does nothing */

ph_gen(ATTR_NONE, extent_avail_, extent_tree_t, extent_t, ph_link,

    extent_esnead_comp)

#undef ATTR_NONE

typedef enum {

	lock_result_success,

	lock_result_failure,

	lock_result_no_extent

} lock_result_t;

static lock_result_t

extent_rtree_leaf_elm_try_lock(tsdn_t *tsdn, rtree_leaf_elm_t *elm,

    extent_t **result, bool inactive_only) {

	extent_t *extent1 = rtree_leaf_elm_extent_read(tsdn, &extents_rtree,

	    elm, true);

	/* Slab implies active extents and should be skipped. */

	if (extent1 == NULL || (inactive_only && rtree_leaf_elm_slab_read(tsdn,

	    &extents_rtree, elm, true))) {

		return lock_result_no_extent;

	}

	/*

	 * It's possible that the extent changed out from under us, and with it

	 * the leaf->extent mapping.  We have to recheck while holding the lock.

	 */

	extent_lock(tsdn, extent1);

	extent_t *extent2 = rtree_leaf_elm_extent_read(tsdn,

	    &extents_rtree, elm, true);

	if (extent1 == extent2) {

		*result = extent1;

		return lock_result_success;

	} else {

		extent_unlock(tsdn, extent1);

		return lock_result_failure;

	}

}

/*

 * Returns a pool-locked extent_t * if there's one associated with the given

 * address, and NULL otherwise.

 */

static extent_t *

extent_lock_from_addr(tsdn_t *tsdn, rtree_ctx_t *rtree_ctx, void *addr,

    bool inactive_only) {

	extent_t *ret = NULL;

	rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, &extents_rtree,

	    rtree_ctx, (uintptr_t)addr, false, false);

	if (elm == NULL) {

		return NULL;

	}

	lock_result_t lock_result;

	do {

		lock_result = extent_rtree_leaf_elm_try_lock(tsdn, elm, &ret,

		    inactive_only);

	} while (lock_result == lock_result_failure);

	return ret;

}

extent_t *

extent_alloc(tsdn_t *tsdn, arena_t *arena) {

	malloc_mutex_lock(tsdn, &arena->extent_avail_mtx);

	extent_t *extent = extent_avail_first(&arena->extent_avail);

	if (extent == NULL) {

		malloc_mutex_unlock(tsdn, &arena->extent_avail_mtx);

		return base_alloc_extent(tsdn, arena->base);

	}

	extent_avail_remove(&arena->extent_avail, extent);

	atomic_fetch_sub_zu(&arena->extent_avail_cnt, 1, ATOMIC_RELAXED);

	malloc_mutex_unlock(tsdn, &arena->extent_avail_mtx);

	return extent;

}

void

extent_dalloc(tsdn_t *tsdn, arena_t *arena, extent_t *extent) {

	malloc_mutex_lock(tsdn, &arena->extent_avail_mtx);

	extent_avail_insert(&arena->extent_avail, extent);

	atomic_fetch_add_zu(&arena->extent_avail_cnt, 1, ATOMIC_RELAXED);

	malloc_mutex_unlock(tsdn, &arena->extent_avail_mtx);

}

extent_hooks_t *

extent_hooks_get(arena_t *arena) {

	return base_extent_hooks_get(arena->base);

}

extent_hooks_t *

extent_hooks_set(tsd_t *tsd, arena_t *arena, extent_hooks_t *extent_hooks) {

	background_thread_info_t *info;

	if (have_background_thread) {

		info = arena_background_thread_info_get(arena);

		malloc_mutex_lock(tsd_tsdn(tsd), &info->mtx);

	}

	extent_hooks_t *ret = base_extent_hooks_set(arena->base, extent_hooks);

	if (have_background_thread) {

		malloc_mutex_unlock(tsd_tsdn(tsd), &info->mtx);

	}

	return ret;

}

static void

extent_hooks_assure_initialized(arena_t *arena,

    extent_hooks_t **r_extent_hooks) {

	if (*r_extent_hooks == EXTENT_HOOKS_INITIALIZER) {

		*r_extent_hooks = extent_hooks_get(arena);

	}

}

#ifndef JEMALLOC_JET

static

#endif

size_t

extent_size_quantize_floor(size_t size) {

	size_t ret;

	pszind_t pind;

	assert(size > 0);

	assert((size & PAGE_MASK) == 0);

	pind = sz_psz2ind(size - sz_large_pad + 1);

	if (pind == 0) {

		/*

		 * Avoid underflow.  This short-circuit would also do the right

		 * thing for all sizes in the range for which there are

		 * PAGE-spaced size classes, but it's simplest to just handle

		 * the one case that would cause erroneous results.

		 */

		return size;

	}

	ret = sz_pind2sz(pind - 1) + sz_large_pad;

	assert(ret <= size);

	return ret;

}

#ifndef JEMALLOC_JET

static

#endif

size_t

extent_size_quantize_ceil(size_t size) {

	size_t ret;

	assert(size > 0);

	assert(size - sz_large_pad <= SC_LARGE_MAXCLASS);

	assert((size & PAGE_MASK) == 0);

	ret = extent_size_quantize_floor(size);

	if (ret < size) {

		/*

		 * Skip a quantization that may have an adequately large extent,

		 * because under-sized extents may be mixed in.  This only

		 * happens when an unusual size is requested, i.e. for aligned

		 * allocation, and is just one of several places where linear

		 * search would potentially find sufficiently aligned available

		 * memory somewhere lower.

		 */

		ret = sz_pind2sz(sz_psz2ind(ret - sz_large_pad + 1)) +

		    sz_large_pad;

	}

	return ret;

}

/* Generate pairing heap functions. */

ph_gen(, extent_heap_, extent_heap_t, extent_t, ph_link, extent_snad_comp)

bool

extents_init(tsdn_t *tsdn, extents_t *extents, extent_state_t state,

    bool delay_coalesce) {

	if (malloc_mutex_init(&extents->mtx, "extents", WITNESS_RANK_EXTENTS,

	    malloc_mutex_rank_exclusive)) {

		return true;

	}

	for (unsigned i = 0; i < SC_NPSIZES + 1; i++) {

		extent_heap_new(&extents->heaps[i]);

	}

	bitmap_init(extents->bitmap, &extents_bitmap_info, true);

	extent_list_init(&extents->lru);

	atomic_store_zu(&extents->npages, 0, ATOMIC_RELAXED);

	extents->state = state;

	extents->delay_coalesce = delay_coalesce;

	return false;

}

extent_state_t

extents_state_get(const extents_t *extents) {

	return extents->state;

}

size_t

extents_npages_get(extents_t *extents) {

	return atomic_load_zu(&extents->npages, ATOMIC_RELAXED);

}

size_t

extents_nextents_get(extents_t *extents, pszind_t pind) {

	return atomic_load_zu(&extents->nextents[pind], ATOMIC_RELAXED);

}

size_t

extents_nbytes_get(extents_t *extents, pszind_t pind) {

	return atomic_load_zu(&extents->nbytes[pind], ATOMIC_RELAXED);

}

static void

extents_stats_add(extents_t *extent, pszind_t pind, size_t sz) {

	size_t cur = atomic_load_zu(&extent->nextents[pind], ATOMIC_RELAXED);

	atomic_store_zu(&extent->nextents[pind], cur + 1, ATOMIC_RELAXED);

	cur = atomic_load_zu(&extent->nbytes[pind], ATOMIC_RELAXED);

	atomic_store_zu(&extent->nbytes[pind], cur + sz, ATOMIC_RELAXED);

}

static void

extents_stats_sub(extents_t *extent, pszind_t pind, size_t sz) {

	size_t cur = atomic_load_zu(&extent->nextents[pind], ATOMIC_RELAXED);

	atomic_store_zu(&extent->nextents[pind], cur - 1, ATOMIC_RELAXED);

	cur = atomic_load_zu(&extent->nbytes[pind], ATOMIC_RELAXED);

	atomic_store_zu(&extent->nbytes[pind], cur - sz, ATOMIC_RELAXED);

}

static void

extents_insert_locked(tsdn_t *tsdn, extents_t *extents, extent_t *extent) {

	malloc_mutex_assert_owner(tsdn, &extents->mtx);

	assert(extent_state_get(extent) == extents->state);

	size_t size = extent_size_get(extent);

	size_t psz = extent_size_quantize_floor(size);

	pszind_t pind = sz_psz2ind(psz);

	if (extent_heap_empty(&extents->heaps[pind])) {

		bitmap_unset(extents->bitmap, &extents_bitmap_info,

		    (size_t)pind);

	}

	extent_heap_insert(&extents->heaps[pind], extent);

	if (config_stats) {

		extents_stats_add(extents, pind, size);

	}

	extent_list_append(&extents->lru, extent);

	size_t npages = size >> LG_PAGE;

	/*

	 * All modifications to npages hold the mutex (as asserted above), so we

	 * don't need an atomic fetch-add; we can get by with a load followed by

	 * a store.

	 */

	size_t cur_extents_npages =

	    atomic_load_zu(&extents->npages, ATOMIC_RELAXED);

	atomic_store_zu(&extents->npages, cur_extents_npages + npages,

	    ATOMIC_RELAXED);

}

static void

extents_remove_locked(tsdn_t *tsdn, extents_t *extents, extent_t *extent) {

	malloc_mutex_assert_owner(tsdn, &extents->mtx);

	assert(extent_state_get(extent) == extents->state);

	size_t size = extent_size_get(extent);

	size_t psz = extent_size_quantize_floor(size);

	pszind_t pind = sz_psz2ind(psz);

	extent_heap_remove(&extents->heaps[pind], extent);

	if (config_stats) {

		extents_stats_sub(extents, pind, size);

	}

	if (extent_heap_empty(&extents->heaps[pind])) {

		bitmap_set(extents->bitmap, &extents_bitmap_info,

		    (size_t)pind);

	}

	extent_list_remove(&extents->lru, extent);

	size_t npages = size >> LG_PAGE;

	/*

	 * As in extents_insert_locked, we hold extents->mtx and so don't need

	 * atomic operations for updating extents->npages.

	 */

	size_t cur_extents_npages =

	    atomic_load_zu(&extents->npages, ATOMIC_RELAXED);

	assert(cur_extents_npages >= npages);

	atomic_store_zu(&extents->npages,

	    cur_extents_npages - (size >> LG_PAGE), ATOMIC_RELAXED);

}

/*

 * Find an extent with size [min_size, max_size) to satisfy the alignment

 * requirement.  For each size, try only the first extent in the heap.

 */

static extent_t *

extents_fit_alignment(extents_t *extents, size_t min_size, size_t max_size,

    size_t alignment) {

        pszind_t pind = sz_psz2ind(extent_size_quantize_ceil(min_size));

        pszind_t pind_max = sz_psz2ind(extent_size_quantize_ceil(max_size));

	for (pszind_t i = (pszind_t)bitmap_ffu(extents->bitmap,

	    &extents_bitmap_info, (size_t)pind); i < pind_max; i =

	    (pszind_t)bitmap_ffu(extents->bitmap, &extents_bitmap_info,

	    (size_t)i+1)) {

		assert(i < SC_NPSIZES);

		assert(!extent_heap_empty(&extents->heaps[i]));

		extent_t *extent = extent_heap_first(&extents->heaps[i]);

		uintptr_t base = (uintptr_t)extent_base_get(extent);

		size_t candidate_size = extent_size_get(extent);

		assert(candidate_size >= min_size);

		uintptr_t next_align = ALIGNMENT_CEILING((uintptr_t)base,

		    PAGE_CEILING(alignment));

		if (base > next_align || base + candidate_size <= next_align) {

			/* Overflow or not crossing the next alignment. */

			continue;

		}

		size_t leadsize = next_align - base;

		if (candidate_size - leadsize >= min_size) {

			return extent;

		}

	}

	return NULL;

}

/*

 * Do first-fit extent selection, i.e. select the oldest/lowest extent that is

 * large enough.

 */

static extent_t *

extents_first_fit_locked(tsdn_t *tsdn, arena_t *arena, extents_t *extents,

    size_t size) {

	extent_t *ret = NULL;

	pszind_t pind = sz_psz2ind(extent_size_quantize_ceil(size));

	if (!maps_coalesce && !opt_retain) {

		/*

		 * No split / merge allowed (Windows w/o retain). Try exact fit

		 * only.

		 */

		return extent_heap_empty(&extents->heaps[pind]) ? NULL :

		    extent_heap_first(&extents->heaps[pind]);

	}

	for (pszind_t i = (pszind_t)bitmap_ffu(extents->bitmap,

	    &extents_bitmap_info, (size_t)pind);

	    i < SC_NPSIZES + 1;

	    i = (pszind_t)bitmap_ffu(extents->bitmap, &extents_bitmap_info,

	    (size_t)i+1)) {

		assert(!extent_heap_empty(&extents->heaps[i]));

		extent_t *extent = extent_heap_first(&extents->heaps[i]);

		assert(extent_size_get(extent) >= size);

		/*

		 * In order to reduce fragmentation, avoid reusing and splitting

		 * large extents for much smaller sizes.

		 *

		 * Only do check for dirty extents (delay_coalesce).

		 */

		if (extents->delay_coalesce &&

		    (sz_pind2sz(i) >> opt_lg_extent_max_active_fit) > size) {

			break;

		}

		if (ret == NULL || extent_snad_comp(extent, ret) < 0) {

			ret = extent;

		}

		if (i == SC_NPSIZES) {

			break;

		}

		assert(i < SC_NPSIZES);

	}

	return ret;

}

/*

 * Do first-fit extent selection, where the selection policy choice is

 * based on extents->delay_coalesce.

 */

static extent_t *

extents_fit_locked(tsdn_t *tsdn, arena_t *arena, extents_t *extents,

    size_t esize, size_t alignment) {

	malloc_mutex_assert_owner(tsdn, &extents->mtx);

	size_t max_size = esize + PAGE_CEILING(alignment) - PAGE;

	/* Beware size_t wrap-around. */

	if (max_size < esize) {

		return NULL;

	}

	extent_t *extent =

	    extents_first_fit_locked(tsdn, arena, extents, max_size);

	if (alignment > PAGE && extent == NULL) {

		/*

		 * max_size guarantees the alignment requirement but is rather

		 * pessimistic.  Next we try to satisfy the aligned allocation

		 * with sizes in [esize, max_size).

		 */

		extent = extents_fit_alignment(extents, esize, max_size,

		    alignment);

	}

	return extent;

}

static bool

extent_try_delayed_coalesce(tsdn_t *tsdn, arena_t *arena,

    extent_hooks_t **r_extent_hooks, rtree_ctx_t *rtree_ctx, extents_t *extents,

    extent_t *extent) {

	extent_state_set(extent, extent_state_active);

	bool coalesced;

	extent = extent_try_coalesce(tsdn, arena, r_extent_hooks, rtree_ctx,

	    extents, extent, &coalesced, false);

	extent_state_set(extent, extents_state_get(extents));

	if (!coalesced) {

		return true;

	}

	extents_insert_locked(tsdn, extents, extent);

	return false;

}

extent_t *

extents_alloc(tsdn_t *tsdn, arena_t *arena, extent_hooks_t **r_extent_hooks,

    extents_t *extents, void *new_addr, size_t size, size_t pad,

    size_t alignment, bool slab, szind_t szind, bool *zero, bool *commit) {

	assert(size + pad != 0);

	assert(alignment != 0);

	witness_assert_depth_to_rank(tsdn_witness_tsdp_get(tsdn),

	    WITNESS_RANK_CORE, 0);

	extent_t *extent = extent_recycle(tsdn, arena, r_extent_hooks, extents,

	    new_addr, size, pad, alignment, slab, szind, zero, commit, false);

	assert(extent == NULL || extent_dumpable_get(extent));

	return extent;

}

void

extents_dalloc(tsdn_t *tsdn, arena_t *arena, extent_hooks_t **r_extent_hooks,

    extents_t *extents, extent_t *extent) {

	assert(extent_base_get(extent) != NULL);

	assert(extent_size_get(extent) != 0);

	assert(extent_dumpable_get(extent));

	witness_assert_depth_to_rank(tsdn_witness_tsdp_get(tsdn),

	    WITNESS_RANK_CORE, 0);

	extent_addr_set(extent, extent_base_get(extent));

	extent_zeroed_set(extent, false);

	extent_record(tsdn, arena, r_extent_hooks, extents, extent, false);

}

extent_t *

extents_evict(tsdn_t *tsdn, arena_t *arena, extent_hooks_t **r_extent_hooks,

    extents_t *extents, size_t npages_min) {

	rtree_ctx_t rtree_ctx_fallback;

	rtree_ctx_t *rtree_ctx = tsdn_rtree_ctx(tsdn, &rtree_ctx_fallback);

	malloc_mutex_lock(tsdn, &extents->mtx);

	/*

	 * Get the LRU coalesced extent, if any.  If coalescing was delayed,

	 * the loop will iterate until the LRU extent is fully coalesced.

	 */

	extent_t *extent;

	while (true) {

		/* Get the LRU extent, if any. */

		extent = extent_list_first(&extents->lru);

		if (extent == NULL) {

			goto label_return;

		}

		/* Check the eviction limit. */

		size_t extents_npages = atomic_load_zu(&extents->npages,

		    ATOMIC_RELAXED);

		if (extents_npages <= npages_min) {

			extent = NULL;

			goto label_return;

		}

		extents_remove_locked(tsdn, extents, extent);

		if (!extents->delay_coalesce) {

			break;

		}

		/* Try to coalesce. */

		if (extent_try_delayed_coalesce(tsdn, arena, r_extent_hooks,

		    rtree_ctx, extents, extent)) {

			break;

		}

		/*

		 * The LRU extent was just coalesced and the result placed in

		 * the LRU at its neighbor's position.  Start over.

		 */

	}

	/*

	 * Either mark the extent active or deregister it to protect against

	 * concurrent operations.

	 */

	switch (extents_state_get(extents)) {

	case extent_state_active:

		not_reached();

	case extent_state_dirty:

	case extent_state_muzzy:

		extent_state_set(extent, extent_state_active);

		break;

	case extent_state_retained:

		extent_deregister(tsdn, extent);

		break;

	default:

		not_reached();

	}

label_return:

	malloc_mutex_unlock(tsdn, &extents->mtx);

	return extent;

}

/*

 * This can only happen when we fail to allocate a new extent struct (which

 * indicates OOM), e.g. when trying to split an existing extent.

 */

static void

extents_abandon_vm(tsdn_t *tsdn, arena_t *arena, extent_hooks_t **r_extent_hooks,

    extents_t *extents, extent_t *extent, bool growing_retained) {

	size_t sz = extent_size_get(extent);

	if (config_stats) {

		arena_stats_accum_zu(&arena->stats.abandoned_vm, sz);

	}

	/*

	 * Leak extent after making sure its pages have already been purged, so

	 * that this is only a virtual memory leak.

	 */

	if (extents_state_get(extents) == extent_state_dirty) {

		if (extent_purge_lazy_impl(tsdn, arena, r_extent_hooks,

		    extent, 0, sz, growing_retained)) {

			extent_purge_forced_impl(tsdn, arena, r_extent_hooks,

			    extent, 0, extent_size_get(extent),

			    growing_retained);

		}

	}

	extent_dalloc(tsdn, arena, extent);

}

void

extents_prefork(tsdn_t *tsdn, extents_t *extents) {

	malloc_mutex_prefork(tsdn, &extents->mtx);

}

void

extents_postfork_parent(tsdn_t *tsdn, extents_t *extents) {

	malloc_mutex_postfork_parent(tsdn, &extents->mtx);

}

void

extents_postfork_child(tsdn_t *tsdn, extents_t *extents) {

	malloc_mutex_postfork_child(tsdn, &extents->mtx);

}

static void

extent_deactivate_locked(tsdn_t *tsdn, arena_t *arena, extents_t *extents,

    extent_t *extent) {

	assert(extent_arena_get(extent) == arena);

	assert(extent_state_get(extent) == extent_state_active);

	extent_state_set(extent, extents_state_get(extents));

	extents_insert_locked(tsdn, extents, extent);

}

static void

extent_deactivate(tsdn_t *tsdn, arena_t *arena, extents_t *extents,

    extent_t *extent) {

	malloc_mutex_lock(tsdn, &extents->mtx);

	extent_deactivate_locked(tsdn, arena, extents, extent);

	malloc_mutex_unlock(tsdn, &extents->mtx);

}

static void

extent_activate_locked(tsdn_t *tsdn, arena_t *arena, extents_t *extents,

    extent_t *extent) {

	assert(extent_arena_get(extent) == arena);

	assert(extent_state_get(extent) == extents_state_get(extents));

	extents_remove_locked(tsdn, extents, extent);

	extent_state_set(extent, extent_state_active);

}

static bool

extent_rtree_leaf_elms_lookup(tsdn_t *tsdn, rtree_ctx_t *rtree_ctx,

    const extent_t *extent, 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, &extents_rtree, rtree_ctx,

	    (uintptr_t)extent_base_get(extent), dependent, init_missing);

	if (!dependent && *r_elm_a == NULL) {

		return true;

	}

	assert(*r_elm_a != NULL);

	*r_elm_b = rtree_leaf_elm_lookup(tsdn, &extents_rtree, rtree_ctx,

	    (uintptr_t)extent_last_get(extent), dependent, init_missing);

	if (!dependent && *r_elm_b == NULL) {

		return true;

	}

	assert(*r_elm_b != NULL);

	return false;

}

static void

extent_rtree_write_acquired(tsdn_t *tsdn, rtree_leaf_elm_t *elm_a,

    rtree_leaf_elm_t *elm_b, extent_t *extent, szind_t szind, bool slab) {

	rtree_leaf_elm_write(tsdn, &extents_rtree, elm_a, extent, szind, slab);

	if (elm_b != NULL) {

		rtree_leaf_elm_write(tsdn, &extents_rtree, elm_b, extent, szind,

		    slab);

	}

}

static void

extent_interior_register(tsdn_t *tsdn, rtree_ctx_t *rtree_ctx, extent_t *extent,

    szind_t szind) {

	assert(extent_slab_get(extent));

	/* Register interior. */

	for (size_t i = 1; i < (extent_size_get(extent) >> LG_PAGE) - 1; i++) {

		rtree_write(tsdn, &extents_rtree, rtree_ctx,

		    (uintptr_t)extent_base_get(extent) + (uintptr_t)(i <<

		    LG_PAGE), extent, szind, true);

	}

}

static void

extent_gdump_add(tsdn_t *tsdn, const extent_t *extent) {

	cassert(config_prof);

	/* prof_gdump() requirement. */

	witness_assert_depth_to_rank(tsdn_witness_tsdp_get(tsdn),

	    WITNESS_RANK_CORE, 0);

	if (opt_prof && extent_state_get(extent) == extent_state_active) {

		size_t nadd = extent_size_get(extent) >> LG_PAGE;

		size_t cur = atomic_fetch_add_zu(&curpages, nadd,

		    ATOMIC_RELAXED) + nadd;

		size_t high = atomic_load_zu(&highpages, ATOMIC_RELAXED);

		while (cur > high && !atomic_compare_exchange_weak_zu(

		    &highpages, &high, cur, ATOMIC_RELAXED, ATOMIC_RELAXED)) {

			/*

			 * Don't refresh cur, because it may have decreased

			 * since this thread lost the highpages update race.

			 * Note that high is updated in case of CAS failure.

			 */

		}

		if (cur > high && prof_gdump_get_unlocked()) {

			prof_gdump(tsdn);

		}

	}

}

static void

extent_gdump_sub(tsdn_t *tsdn, const extent_t *extent) {

	cassert(config_prof);

	if (opt_prof && extent_state_get(extent) == extent_state_active) {

		size_t nsub = extent_size_get(extent) >> LG_PAGE;

		assert(atomic_load_zu(&curpages, ATOMIC_RELAXED) >= nsub);

		atomic_fetch_sub_zu(&curpages, nsub, ATOMIC_RELAXED);

	}

}

static bool

extent_register_impl(tsdn_t *tsdn, extent_t *extent, bool gdump_add) {

	rtree_ctx_t rtree_ctx_fallback;

	rtree_ctx_t *rtree_ctx = tsdn_rtree_ctx(tsdn, &rtree_ctx_fallback);

	rtree_leaf_elm_t *elm_a, *elm_b;

	/*

	 * We need to hold the lock to protect against a concurrent coalesce

	 * operation that sees us in a partial state.

	 */

	extent_lock(tsdn, extent);

	if (extent_rtree_leaf_elms_lookup(tsdn, rtree_ctx, extent, false, true,

	    &elm_a, &elm_b)) {

		extent_unlock(tsdn, extent);

		return true;

	}

	szind_t szind = extent_szind_get_maybe_invalid(extent);

	bool slab = extent_slab_get(extent);

	extent_rtree_write_acquired(tsdn, elm_a, elm_b, extent, szind, slab);

	if (slab) {

		extent_interior_register(tsdn, rtree_ctx, extent, szind);

	}

	extent_unlock(tsdn, extent);

	if (config_prof && gdump_add) {

		extent_gdump_add(tsdn, extent);

	}

	return false;

}

static bool

extent_register(tsdn_t *tsdn, extent_t *extent) {

	return extent_register_impl(tsdn, extent, true);

}

static bool

extent_register_no_gdump_add(tsdn_t *tsdn, extent_t *extent) {

	return extent_register_impl(tsdn, extent, false);

}

static void

extent_reregister(tsdn_t *tsdn, extent_t *extent) {

	bool err = extent_register(tsdn, extent);

	assert(!err);

}

/*

 * Removes all pointers to the given extent from the global rtree indices for

 * its interior.  This is relevant for slab extents, for which we need to do

 * metadata lookups at places other than the head of the extent.  We deregister

 * on the interior, then, when an extent moves from being an active slab to an

 * inactive state.

 */

static void

extent_interior_deregister(tsdn_t *tsdn, rtree_ctx_t *rtree_ctx,

    extent_t *extent) {

	size_t i;

	assert(extent_slab_get(extent));

	for (i = 1; i < (extent_size_get(extent) >> LG_PAGE) - 1; i++) {

		rtree_clear(tsdn, &extents_rtree, rtree_ctx,

		    (uintptr_t)extent_base_get(extent) + (uintptr_t)(i <<

		    LG_PAGE));

	}

}

/*

 * Removes all pointers to the given extent from the global rtree.

 */

static void

extent_deregister_impl(tsdn_t *tsdn, extent_t *extent, bool gdump) {

	rtree_ctx_t rtree_ctx_fallback;

	rtree_ctx_t *rtree_ctx = tsdn_rtree_ctx(tsdn, &rtree_ctx_fallback);

	rtree_leaf_elm_t *elm_a, *elm_b;

	extent_rtree_leaf_elms_lookup(tsdn, rtree_ctx, extent, true, false,

	    &elm_a, &elm_b);

	extent_lock(tsdn, extent);

	extent_rtree_write_acquired(tsdn, elm_a, elm_b, NULL, SC_NSIZES, false);

	if (extent_slab_get(extent)) {

		extent_interior_deregister(tsdn, rtree_ctx, extent);

		extent_slab_set(extent, false);

	}

	extent_unlock(tsdn, extent);

	if (config_prof && gdump) {

		extent_gdump_sub(tsdn, extent);

	}

}

static void

extent_deregister(tsdn_t *tsdn, extent_t *extent) {

	extent_deregister_impl(tsdn, extent, true);

}