Blame jemalloc/include/jemalloc/internal/rtree.h

Packit Service 724aca
#ifndef JEMALLOC_INTERNAL_RTREE_H
Packit Service 724aca
#define JEMALLOC_INTERNAL_RTREE_H
Packit Service 724aca
Packit Service 724aca
#include "jemalloc/internal/atomic.h"
Packit Service 724aca
#include "jemalloc/internal/mutex.h"
Packit Service 724aca
#include "jemalloc/internal/rtree_tsd.h"
Packit Service 724aca
#include "jemalloc/internal/sc.h"
Packit Service 724aca
#include "jemalloc/internal/tsd.h"
Packit Service 724aca
Packit Service 724aca
/*
Packit Service 724aca
 * This radix tree implementation is tailored to the singular purpose of
Packit Service 724aca
 * associating metadata with extents that are currently owned by jemalloc.
Packit Service 724aca
 *
Packit Service 724aca
 *******************************************************************************
Packit Service 724aca
 */
Packit Service 724aca
Packit Service 724aca
/* Number of high insignificant bits. */
Packit Service 724aca
#define RTREE_NHIB ((1U << (LG_SIZEOF_PTR+3)) - LG_VADDR)
Packit Service 724aca
/* Number of low insigificant bits. */
Packit Service 724aca
#define RTREE_NLIB LG_PAGE
Packit Service 724aca
/* Number of significant bits. */
Packit Service 724aca
#define RTREE_NSB (LG_VADDR - RTREE_NLIB)
Packit Service 724aca
/* Number of levels in radix tree. */
Packit Service 724aca
#if RTREE_NSB <= 10
Packit Service 724aca
#  define RTREE_HEIGHT 1
Packit Service 724aca
#elif RTREE_NSB <= 36
Packit Service 724aca
#  define RTREE_HEIGHT 2
Packit Service 724aca
#elif RTREE_NSB <= 52
Packit Service 724aca
#  define RTREE_HEIGHT 3
Packit Service 724aca
#else
Packit Service 724aca
#  error Unsupported number of significant virtual address bits
Packit Service 724aca
#endif
Packit Service 724aca
/* Use compact leaf representation if virtual address encoding allows. */
Packit Service 724aca
#if RTREE_NHIB >= LG_CEIL(SC_NSIZES)
Packit Service 724aca
#  define RTREE_LEAF_COMPACT
Packit Service 724aca
#endif
Packit Service 724aca
Packit Service 724aca
/* Needed for initialization only. */
Packit Service 724aca
#define RTREE_LEAFKEY_INVALID ((uintptr_t)1)
Packit Service 724aca
Packit Service 724aca
typedef struct rtree_node_elm_s rtree_node_elm_t;
Packit Service 724aca
struct rtree_node_elm_s {
Packit Service 724aca
	atomic_p_t	child; /* (rtree_{node,leaf}_elm_t *) */
Packit Service 724aca
};
Packit Service 724aca
Packit Service 724aca
struct rtree_leaf_elm_s {
Packit Service 724aca
#ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
	/*
Packit Service 724aca
	 * Single pointer-width field containing all three leaf element fields.
Packit Service 724aca
	 * For example, on a 64-bit x64 system with 48 significant virtual
Packit Service 724aca
	 * memory address bits, the index, extent, and slab fields are packed as
Packit Service 724aca
	 * such:
Packit Service 724aca
	 *
Packit Service 724aca
	 * x: index
Packit Service 724aca
	 * e: extent
Packit Service 724aca
	 * b: slab
Packit Service 724aca
	 *
Packit Service 724aca
	 *   00000000 xxxxxxxx eeeeeeee [...] eeeeeeee eeee000b
Packit Service 724aca
	 */
Packit Service 724aca
	atomic_p_t	le_bits;
Packit Service 724aca
#else
Packit Service 724aca
	atomic_p_t	le_extent; /* (extent_t *) */
Packit Service 724aca
	atomic_u_t	le_szind; /* (szind_t) */
Packit Service 724aca
	atomic_b_t	le_slab; /* (bool) */
Packit Service 724aca
#endif
Packit Service 724aca
};
Packit Service 724aca
Packit Service 724aca
typedef struct rtree_level_s rtree_level_t;
Packit Service 724aca
struct rtree_level_s {
Packit Service 724aca
	/* Number of key bits distinguished by this level. */
Packit Service 724aca
	unsigned		bits;
Packit Service 724aca
	/*
Packit Service 724aca
	 * Cumulative number of key bits distinguished by traversing to
Packit Service 724aca
	 * corresponding tree level.
Packit Service 724aca
	 */
Packit Service 724aca
	unsigned		cumbits;
Packit Service 724aca
};
Packit Service 724aca
Packit Service 724aca
typedef struct rtree_s rtree_t;
Packit Service 724aca
struct rtree_s {
Packit Service 724aca
	malloc_mutex_t		init_lock;
Packit Service 724aca
	/* Number of elements based on rtree_levels[0].bits. */
Packit Service 724aca
#if RTREE_HEIGHT > 1
Packit Service 724aca
	rtree_node_elm_t	root[1U << (RTREE_NSB/RTREE_HEIGHT)];
Packit Service 724aca
#else
Packit Service 724aca
	rtree_leaf_elm_t	root[1U << (RTREE_NSB/RTREE_HEIGHT)];
Packit Service 724aca
#endif
Packit Service 724aca
};
Packit Service 724aca
Packit Service 724aca
/*
Packit Service 724aca
 * Split the bits into one to three partitions depending on number of
Packit Service 724aca
 * significant bits.  It the number of bits does not divide evenly into the
Packit Service 724aca
 * number of levels, place one remainder bit per level starting at the leaf
Packit Service 724aca
 * level.
Packit Service 724aca
 */
Packit Service 724aca
static const rtree_level_t rtree_levels[] = {
Packit Service 724aca
#if RTREE_HEIGHT == 1
Packit Service 724aca
	{RTREE_NSB, RTREE_NHIB + RTREE_NSB}
Packit Service 724aca
#elif RTREE_HEIGHT == 2
Packit Service 724aca
	{RTREE_NSB/2, RTREE_NHIB + RTREE_NSB/2},
Packit Service 724aca
	{RTREE_NSB/2 + RTREE_NSB%2, RTREE_NHIB + RTREE_NSB}
Packit Service 724aca
#elif RTREE_HEIGHT == 3
Packit Service 724aca
	{RTREE_NSB/3, RTREE_NHIB + RTREE_NSB/3},
Packit Service 724aca
	{RTREE_NSB/3 + RTREE_NSB%3/2,
Packit Service 724aca
	    RTREE_NHIB + RTREE_NSB/3*2 + RTREE_NSB%3/2},
Packit Service 724aca
	{RTREE_NSB/3 + RTREE_NSB%3 - RTREE_NSB%3/2, RTREE_NHIB + RTREE_NSB}
Packit Service 724aca
#else
Packit Service 724aca
#  error Unsupported rtree height
Packit Service 724aca
#endif
Packit Service 724aca
};
Packit Service 724aca
Packit Service 724aca
bool rtree_new(rtree_t *rtree, bool zeroed);
Packit Service 724aca
Packit Service 724aca
typedef rtree_node_elm_t *(rtree_node_alloc_t)(tsdn_t *, rtree_t *, size_t);
Packit Service 724aca
extern rtree_node_alloc_t *JET_MUTABLE rtree_node_alloc;
Packit Service 724aca
Packit Service 724aca
typedef rtree_leaf_elm_t *(rtree_leaf_alloc_t)(tsdn_t *, rtree_t *, size_t);
Packit Service 724aca
extern rtree_leaf_alloc_t *JET_MUTABLE rtree_leaf_alloc;
Packit Service 724aca
Packit Service 724aca
typedef void (rtree_node_dalloc_t)(tsdn_t *, rtree_t *, rtree_node_elm_t *);
Packit Service 724aca
extern rtree_node_dalloc_t *JET_MUTABLE rtree_node_dalloc;
Packit Service 724aca
Packit Service 724aca
typedef void (rtree_leaf_dalloc_t)(tsdn_t *, rtree_t *, rtree_leaf_elm_t *);
Packit Service 724aca
extern rtree_leaf_dalloc_t *JET_MUTABLE rtree_leaf_dalloc;
Packit Service 724aca
#ifdef JEMALLOC_JET
Packit Service 724aca
void rtree_delete(tsdn_t *tsdn, rtree_t *rtree);
Packit Service 724aca
#endif
Packit Service 724aca
rtree_leaf_elm_t *rtree_leaf_elm_lookup_hard(tsdn_t *tsdn, rtree_t *rtree,
Packit Service 724aca
    rtree_ctx_t *rtree_ctx, uintptr_t key, bool dependent, bool init_missing);
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE uintptr_t
Packit Service 724aca
rtree_leafkey(uintptr_t key) {
Packit Service 724aca
	unsigned ptrbits = ZU(1) << (LG_SIZEOF_PTR+3);
Packit Service 724aca
	unsigned cumbits = (rtree_levels[RTREE_HEIGHT-1].cumbits -
Packit Service 724aca
	    rtree_levels[RTREE_HEIGHT-1].bits);
Packit Service 724aca
	unsigned maskbits = ptrbits - cumbits;
Packit Service 724aca
	uintptr_t mask = ~((ZU(1) << maskbits) - 1);
Packit Service 724aca
	return (key & mask);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE size_t
Packit Service 724aca
rtree_cache_direct_map(uintptr_t key) {
Packit Service 724aca
	unsigned ptrbits = ZU(1) << (LG_SIZEOF_PTR+3);
Packit Service 724aca
	unsigned cumbits = (rtree_levels[RTREE_HEIGHT-1].cumbits -
Packit Service 724aca
	    rtree_levels[RTREE_HEIGHT-1].bits);
Packit Service 724aca
	unsigned maskbits = ptrbits - cumbits;
Packit Service 724aca
	return (size_t)((key >> maskbits) & (RTREE_CTX_NCACHE - 1));
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE uintptr_t
Packit Service 724aca
rtree_subkey(uintptr_t key, unsigned level) {
Packit Service 724aca
	unsigned ptrbits = ZU(1) << (LG_SIZEOF_PTR+3);
Packit Service 724aca
	unsigned cumbits = rtree_levels[level].cumbits;
Packit Service 724aca
	unsigned shiftbits = ptrbits - cumbits;
Packit Service 724aca
	unsigned maskbits = rtree_levels[level].bits;
Packit Service 724aca
	uintptr_t mask = (ZU(1) << maskbits) - 1;
Packit Service 724aca
	return ((key >> shiftbits) & mask);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
/*
Packit Service 724aca
 * Atomic getters.
Packit Service 724aca
 *
Packit Service 724aca
 * dependent: Reading a value on behalf of a pointer to a valid allocation
Packit Service 724aca
 *            is guaranteed to be a clean read even without synchronization,
Packit Service 724aca
 *            because the rtree update became visible in memory before the
Packit Service 724aca
 *            pointer came into existence.
Packit Service 724aca
 * !dependent: An arbitrary read, e.g. on behalf of ivsalloc(), may not be
Packit Service 724aca
 *             dependent on a previous rtree write, which means a stale read
Packit Service 724aca
 *             could result if synchronization were omitted here.
Packit Service 724aca
 */
Packit Service 724aca
#  ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE uintptr_t
Packit Service 724aca
rtree_leaf_elm_bits_read(tsdn_t *tsdn, rtree_t *rtree,
Packit Service 724aca
    rtree_leaf_elm_t *elm, bool dependent) {
Packit Service 724aca
	return (uintptr_t)atomic_load_p(&elm->le_bits, dependent
Packit Service 724aca
	    ? ATOMIC_RELAXED : ATOMIC_ACQUIRE);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE extent_t *
Packit Service 724aca
rtree_leaf_elm_bits_extent_get(uintptr_t bits) {
Packit Service 724aca
#    ifdef __aarch64__
Packit Service 724aca
	/*
Packit Service 724aca
	 * aarch64 doesn't sign extend the highest virtual address bit to set
Packit Service 724aca
	 * the higher ones.  Instead, the high bits gets zeroed.
Packit Service 724aca
	 */
Packit Service 724aca
	uintptr_t high_bit_mask = ((uintptr_t)1 << LG_VADDR) - 1;
Packit Service 724aca
	/* Mask off the slab bit. */
Packit Service 724aca
	uintptr_t low_bit_mask = ~(uintptr_t)1;
Packit Service 724aca
	uintptr_t mask = high_bit_mask & low_bit_mask;
Packit Service 724aca
	return (extent_t *)(bits & mask);
Packit Service 724aca
#    else
Packit Service 724aca
	/* Restore sign-extended high bits, mask slab bit. */
Packit Service 724aca
	return (extent_t *)((uintptr_t)((intptr_t)(bits << RTREE_NHIB) >>
Packit Service 724aca
	    RTREE_NHIB) & ~((uintptr_t)0x1));
Packit Service 724aca
#    endif
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE szind_t
Packit Service 724aca
rtree_leaf_elm_bits_szind_get(uintptr_t bits) {
Packit Service 724aca
	return (szind_t)(bits >> LG_VADDR);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE bool
Packit Service 724aca
rtree_leaf_elm_bits_slab_get(uintptr_t bits) {
Packit Service 724aca
	return (bool)(bits & (uintptr_t)0x1);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
#  endif
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE extent_t *
Packit Service 724aca
rtree_leaf_elm_extent_read(tsdn_t *tsdn, rtree_t *rtree,
Packit Service 724aca
    rtree_leaf_elm_t *elm, bool dependent) {
Packit Service 724aca
#ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
	uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent);
Packit Service 724aca
	return rtree_leaf_elm_bits_extent_get(bits);
Packit Service 724aca
#else
Packit Service 724aca
	extent_t *extent = (extent_t *)atomic_load_p(&elm->le_extent, dependent
Packit Service 724aca
	    ? ATOMIC_RELAXED : ATOMIC_ACQUIRE);
Packit Service 724aca
	return extent;
Packit Service 724aca
#endif
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE szind_t
Packit Service 724aca
rtree_leaf_elm_szind_read(tsdn_t *tsdn, rtree_t *rtree,
Packit Service 724aca
    rtree_leaf_elm_t *elm, bool dependent) {
Packit Service 724aca
#ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
	uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent);
Packit Service 724aca
	return rtree_leaf_elm_bits_szind_get(bits);
Packit Service 724aca
#else
Packit Service 724aca
	return (szind_t)atomic_load_u(&elm->le_szind, dependent ? ATOMIC_RELAXED
Packit Service 724aca
	    : ATOMIC_ACQUIRE);
Packit Service 724aca
#endif
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE bool
Packit Service 724aca
rtree_leaf_elm_slab_read(tsdn_t *tsdn, rtree_t *rtree,
Packit Service 724aca
    rtree_leaf_elm_t *elm, bool dependent) {
Packit Service 724aca
#ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
	uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent);
Packit Service 724aca
	return rtree_leaf_elm_bits_slab_get(bits);
Packit Service 724aca
#else
Packit Service 724aca
	return atomic_load_b(&elm->le_slab, dependent ? ATOMIC_RELAXED :
Packit Service 724aca
	    ATOMIC_ACQUIRE);
Packit Service 724aca
#endif
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
static inline void
Packit Service 724aca
rtree_leaf_elm_extent_write(tsdn_t *tsdn, rtree_t *rtree,
Packit Service 724aca
    rtree_leaf_elm_t *elm, extent_t *extent) {
Packit Service 724aca
#ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
	uintptr_t old_bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, true);
Packit Service 724aca
	uintptr_t bits = ((uintptr_t)rtree_leaf_elm_bits_szind_get(old_bits) <<
Packit Service 724aca
	    LG_VADDR) | ((uintptr_t)extent & (((uintptr_t)0x1 << LG_VADDR) - 1))
Packit Service 724aca
	    | ((uintptr_t)rtree_leaf_elm_bits_slab_get(old_bits));
Packit Service 724aca
	atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE);
Packit Service 724aca
#else
Packit Service 724aca
	atomic_store_p(&elm->le_extent, extent, ATOMIC_RELEASE);
Packit Service 724aca
#endif
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
static inline void
Packit Service 724aca
rtree_leaf_elm_szind_write(tsdn_t *tsdn, rtree_t *rtree,
Packit Service 724aca
    rtree_leaf_elm_t *elm, szind_t szind) {
Packit Service 724aca
	assert(szind <= SC_NSIZES);
Packit Service 724aca
Packit Service 724aca
#ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
	uintptr_t old_bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm,
Packit Service 724aca
	    true);
Packit Service 724aca
	uintptr_t bits = ((uintptr_t)szind << LG_VADDR) |
Packit Service 724aca
	    ((uintptr_t)rtree_leaf_elm_bits_extent_get(old_bits) &
Packit Service 724aca
	    (((uintptr_t)0x1 << LG_VADDR) - 1)) |
Packit Service 724aca
	    ((uintptr_t)rtree_leaf_elm_bits_slab_get(old_bits));
Packit Service 724aca
	atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE);
Packit Service 724aca
#else
Packit Service 724aca
	atomic_store_u(&elm->le_szind, szind, ATOMIC_RELEASE);
Packit Service 724aca
#endif
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
static inline void
Packit Service 724aca
rtree_leaf_elm_slab_write(tsdn_t *tsdn, rtree_t *rtree,
Packit Service 724aca
    rtree_leaf_elm_t *elm, bool slab) {
Packit Service 724aca
#ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
	uintptr_t old_bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm,
Packit Service 724aca
	    true);
Packit Service 724aca
	uintptr_t bits = ((uintptr_t)rtree_leaf_elm_bits_szind_get(old_bits) <<
Packit Service 724aca
	    LG_VADDR) | ((uintptr_t)rtree_leaf_elm_bits_extent_get(old_bits) &
Packit Service 724aca
	    (((uintptr_t)0x1 << LG_VADDR) - 1)) | ((uintptr_t)slab);
Packit Service 724aca
	atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE);
Packit Service 724aca
#else
Packit Service 724aca
	atomic_store_b(&elm->le_slab, slab, ATOMIC_RELEASE);
Packit Service 724aca
#endif
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
static inline void
Packit Service 724aca
rtree_leaf_elm_write(tsdn_t *tsdn, rtree_t *rtree,
Packit Service 724aca
    rtree_leaf_elm_t *elm, extent_t *extent, szind_t szind, bool slab) {
Packit Service 724aca
#ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
	uintptr_t bits = ((uintptr_t)szind << LG_VADDR) |
Packit Service 724aca
	    ((uintptr_t)extent & (((uintptr_t)0x1 << LG_VADDR) - 1)) |
Packit Service 724aca
	    ((uintptr_t)slab);
Packit Service 724aca
	atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE);
Packit Service 724aca
#else
Packit Service 724aca
	rtree_leaf_elm_slab_write(tsdn, rtree, elm, slab);
Packit Service 724aca
	rtree_leaf_elm_szind_write(tsdn, rtree, elm, szind);
Packit Service 724aca
	/*
Packit Service 724aca
	 * Write extent last, since the element is atomically considered valid
Packit Service 724aca
	 * as soon as the extent field is non-NULL.
Packit Service 724aca
	 */
Packit Service 724aca
	rtree_leaf_elm_extent_write(tsdn, rtree, elm, extent);
Packit Service 724aca
#endif
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
static inline void
Packit Service 724aca
rtree_leaf_elm_szind_slab_update(tsdn_t *tsdn, rtree_t *rtree,
Packit Service 724aca
    rtree_leaf_elm_t *elm, szind_t szind, bool slab) {
Packit Service 724aca
	assert(!slab || szind < SC_NBINS);
Packit Service 724aca
Packit Service 724aca
	/*
Packit Service 724aca
	 * The caller implicitly assures that it is the only writer to the szind
Packit Service 724aca
	 * and slab fields, and that the extent field cannot currently change.
Packit Service 724aca
	 */
Packit Service 724aca
	rtree_leaf_elm_slab_write(tsdn, rtree, elm, slab);
Packit Service 724aca
	rtree_leaf_elm_szind_write(tsdn, rtree, elm, szind);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE rtree_leaf_elm_t *
Packit Service 724aca
rtree_leaf_elm_lookup(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
Packit Service 724aca
    uintptr_t key, bool dependent, bool init_missing) {
Packit Service 724aca
	assert(key != 0);
Packit Service 724aca
	assert(!dependent || !init_missing);
Packit Service 724aca
Packit Service 724aca
	size_t slot = rtree_cache_direct_map(key);
Packit Service 724aca
	uintptr_t leafkey = rtree_leafkey(key);
Packit Service 724aca
	assert(leafkey != RTREE_LEAFKEY_INVALID);
Packit Service 724aca
Packit Service 724aca
	/* Fast path: L1 direct mapped cache. */
Packit Service 724aca
	if (likely(rtree_ctx->cache[slot].leafkey == leafkey)) {
Packit Service 724aca
		rtree_leaf_elm_t *leaf = rtree_ctx->cache[slot].leaf;
Packit Service 724aca
		assert(leaf != NULL);
Packit Service 724aca
		uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1);
Packit Service 724aca
		return &leaf[subkey];
Packit Service 724aca
	}
Packit Service 724aca
	/*
Packit Service 724aca
	 * Search the L2 LRU cache.  On hit, swap the matching element into the
Packit Service 724aca
	 * slot in L1 cache, and move the position in L2 up by 1.
Packit Service 724aca
	 */
Packit Service 724aca
#define RTREE_CACHE_CHECK_L2(i) do {					\
Packit Service 724aca
	if (likely(rtree_ctx->l2_cache[i].leafkey == leafkey)) {	\
Packit Service 724aca
		rtree_leaf_elm_t *leaf = rtree_ctx->l2_cache[i].leaf;	\
Packit Service 724aca
		assert(leaf != NULL);					\
Packit Service 724aca
		if (i > 0) {						\
Packit Service 724aca
			/* Bubble up by one. */				\
Packit Service 724aca
			rtree_ctx->l2_cache[i].leafkey =		\
Packit Service 724aca
				rtree_ctx->l2_cache[i - 1].leafkey;	\
Packit Service 724aca
			rtree_ctx->l2_cache[i].leaf =			\
Packit Service 724aca
				rtree_ctx->l2_cache[i - 1].leaf;	\
Packit Service 724aca
			rtree_ctx->l2_cache[i - 1].leafkey =		\
Packit Service 724aca
			    rtree_ctx->cache[slot].leafkey;		\
Packit Service 724aca
			rtree_ctx->l2_cache[i - 1].leaf =		\
Packit Service 724aca
			    rtree_ctx->cache[slot].leaf;		\
Packit Service 724aca
		} else {						\
Packit Service 724aca
			rtree_ctx->l2_cache[0].leafkey =		\
Packit Service 724aca
			    rtree_ctx->cache[slot].leafkey;		\
Packit Service 724aca
			rtree_ctx->l2_cache[0].leaf =			\
Packit Service 724aca
			    rtree_ctx->cache[slot].leaf;		\
Packit Service 724aca
		}							\
Packit Service 724aca
		rtree_ctx->cache[slot].leafkey = leafkey;		\
Packit Service 724aca
		rtree_ctx->cache[slot].leaf = leaf;			\
Packit Service 724aca
		uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1);	\
Packit Service 724aca
		return &leaf[subkey];					\
Packit Service 724aca
	}								\
Packit Service 724aca
} while (0)
Packit Service 724aca
	/* Check the first cache entry. */
Packit Service 724aca
	RTREE_CACHE_CHECK_L2(0);
Packit Service 724aca
	/* Search the remaining cache elements. */
Packit Service 724aca
	for (unsigned i = 1; i < RTREE_CTX_NCACHE_L2; i++) {
Packit Service 724aca
		RTREE_CACHE_CHECK_L2(i);
Packit Service 724aca
	}
Packit Service 724aca
#undef RTREE_CACHE_CHECK_L2
Packit Service 724aca
Packit Service 724aca
	return rtree_leaf_elm_lookup_hard(tsdn, rtree, rtree_ctx, key,
Packit Service 724aca
	    dependent, init_missing);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
static inline bool
Packit Service 724aca
rtree_write(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key,
Packit Service 724aca
    extent_t *extent, szind_t szind, bool slab) {
Packit Service 724aca
	/* Use rtree_clear() to set the extent to NULL. */
Packit Service 724aca
	assert(extent != NULL);
Packit Service 724aca
Packit Service 724aca
	rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx,
Packit Service 724aca
	    key, false, true);
Packit Service 724aca
	if (elm == NULL) {
Packit Service 724aca
		return true;
Packit Service 724aca
	}
Packit Service 724aca
Packit Service 724aca
	assert(rtree_leaf_elm_extent_read(tsdn, rtree, elm, false) == NULL);
Packit Service 724aca
	rtree_leaf_elm_write(tsdn, rtree, elm, extent, szind, slab);
Packit Service 724aca
Packit Service 724aca
	return false;
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE rtree_leaf_elm_t *
Packit Service 724aca
rtree_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key,
Packit Service 724aca
    bool dependent) {
Packit Service 724aca
	rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx,
Packit Service 724aca
	    key, dependent, false);
Packit Service 724aca
	if (!dependent && elm == NULL) {
Packit Service 724aca
		return NULL;
Packit Service 724aca
	}
Packit Service 724aca
	assert(elm != NULL);
Packit Service 724aca
	return elm;
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE extent_t *
Packit Service 724aca
rtree_extent_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
Packit Service 724aca
    uintptr_t key, bool dependent) {
Packit Service 724aca
	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
Packit Service 724aca
	    dependent);
Packit Service 724aca
	if (!dependent && elm == NULL) {
Packit Service 724aca
		return NULL;
Packit Service 724aca
	}
Packit Service 724aca
	return rtree_leaf_elm_extent_read(tsdn, rtree, elm, dependent);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE szind_t
Packit Service 724aca
rtree_szind_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
Packit Service 724aca
    uintptr_t key, bool dependent) {
Packit Service 724aca
	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
Packit Service 724aca
	    dependent);
Packit Service 724aca
	if (!dependent && elm == NULL) {
Packit Service 724aca
		return SC_NSIZES;
Packit Service 724aca
	}
Packit Service 724aca
	return rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
/*
Packit Service 724aca
 * rtree_slab_read() is intentionally omitted because slab is always read in
Packit Service 724aca
 * conjunction with szind, which makes rtree_szind_slab_read() a better choice.
Packit Service 724aca
 */
Packit Service 724aca
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE bool
Packit Service 724aca
rtree_extent_szind_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
Packit Service 724aca
    uintptr_t key, bool dependent, extent_t **r_extent, szind_t *r_szind) {
Packit Service 724aca
	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
Packit Service 724aca
	    dependent);
Packit Service 724aca
	if (!dependent && elm == NULL) {
Packit Service 724aca
		return true;
Packit Service 724aca
	}
Packit Service 724aca
	*r_extent = rtree_leaf_elm_extent_read(tsdn, rtree, elm, dependent);
Packit Service 724aca
	*r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent);
Packit Service 724aca
	return false;
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
/*
Packit Service 724aca
 * Try to read szind_slab from the L1 cache.  Returns true on a hit,
Packit Service 724aca
 * and fills in r_szind and r_slab.  Otherwise returns false.
Packit Service 724aca
 *
Packit Service 724aca
 * Key is allowed to be NULL in order to save an extra branch on the
Packit Service 724aca
 * fastpath.  returns false in this case.
Packit Service 724aca
 */
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE bool
Packit Service 724aca
rtree_szind_slab_read_fast(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
Packit Service 724aca
			    uintptr_t key, szind_t *r_szind, bool *r_slab) {
Packit Service 724aca
	rtree_leaf_elm_t *elm;
Packit Service 724aca
Packit Service 724aca
	size_t slot = rtree_cache_direct_map(key);
Packit Service 724aca
	uintptr_t leafkey = rtree_leafkey(key);
Packit Service 724aca
	assert(leafkey != RTREE_LEAFKEY_INVALID);
Packit Service 724aca
Packit Service 724aca
	if (likely(rtree_ctx->cache[slot].leafkey == leafkey)) {
Packit Service 724aca
		rtree_leaf_elm_t *leaf = rtree_ctx->cache[slot].leaf;
Packit Service 724aca
		assert(leaf != NULL);
Packit Service 724aca
		uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1);
Packit Service 724aca
		elm = &leaf[subkey];
Packit Service 724aca
Packit Service 724aca
#ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
		uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree,
Packit Service 724aca
							  elm, true);
Packit Service 724aca
		*r_szind = rtree_leaf_elm_bits_szind_get(bits);
Packit Service 724aca
		*r_slab = rtree_leaf_elm_bits_slab_get(bits);
Packit Service 724aca
#else
Packit Service 724aca
		*r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, true);
Packit Service 724aca
		*r_slab = rtree_leaf_elm_slab_read(tsdn, rtree, elm, true);
Packit Service 724aca
#endif
Packit Service 724aca
		return true;
Packit Service 724aca
	} else {
Packit Service 724aca
		return false;
Packit Service 724aca
	}
Packit Service 724aca
}
Packit Service 724aca
JEMALLOC_ALWAYS_INLINE bool
Packit Service 724aca
rtree_szind_slab_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
Packit Service 724aca
    uintptr_t key, bool dependent, szind_t *r_szind, bool *r_slab) {
Packit Service 724aca
	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
Packit Service 724aca
	    dependent);
Packit Service 724aca
	if (!dependent && elm == NULL) {
Packit Service 724aca
		return true;
Packit Service 724aca
	}
Packit Service 724aca
#ifdef RTREE_LEAF_COMPACT
Packit Service 724aca
	uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent);
Packit Service 724aca
	*r_szind = rtree_leaf_elm_bits_szind_get(bits);
Packit Service 724aca
	*r_slab = rtree_leaf_elm_bits_slab_get(bits);
Packit Service 724aca
#else
Packit Service 724aca
	*r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent);
Packit Service 724aca
	*r_slab = rtree_leaf_elm_slab_read(tsdn, rtree, elm, dependent);
Packit Service 724aca
#endif
Packit Service 724aca
	return false;
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
static inline void
Packit Service 724aca
rtree_szind_slab_update(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
Packit Service 724aca
    uintptr_t key, szind_t szind, bool slab) {
Packit Service 724aca
	assert(!slab || szind < SC_NBINS);
Packit Service 724aca
Packit Service 724aca
	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, true);
Packit Service 724aca
	rtree_leaf_elm_szind_slab_update(tsdn, rtree, elm, szind, slab);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
static inline void
Packit Service 724aca
rtree_clear(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
Packit Service 724aca
    uintptr_t key) {
Packit Service 724aca
	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, true);
Packit Service 724aca
	assert(rtree_leaf_elm_extent_read(tsdn, rtree, elm, false) !=
Packit Service 724aca
	    NULL);
Packit Service 724aca
	rtree_leaf_elm_write(tsdn, rtree, elm, NULL, SC_NSIZES, false);
Packit Service 724aca
}
Packit Service 724aca
Packit Service 724aca
#endif /* JEMALLOC_INTERNAL_RTREE_H */