path: root/contrib/libs/jemalloc/src/rtree.c

#define JEMALLOC_RTREE_C_ 
#include "jemalloc/internal/jemalloc_preamble.h" 
#include "jemalloc/internal/jemalloc_internal_includes.h" 

#include "jemalloc/internal/assert.h" 
#include "jemalloc/internal/mutex.h" 

/* 
 * Only the most significant bits of keys passed to rtree_{read,write}() are 
 * used. 
 */ 
bool 
rtree_new(rtree_t *rtree, bool zeroed) { 
#ifdef JEMALLOC_JET 
	if (!zeroed) { 
		memset(rtree, 0, sizeof(rtree_t)); /* Clear root. */ 
	} 
#else 
	assert(zeroed); 
#endif 

	if (malloc_mutex_init(&rtree->init_lock, "rtree", WITNESS_RANK_RTREE, 
	    malloc_mutex_rank_exclusive)) { 
		return true; 
	}

	return false; 
} 

static rtree_node_elm_t * 
rtree_node_alloc_impl(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) { 
	return (rtree_node_elm_t *)base_alloc(tsdn, b0get(), nelms * 
	    sizeof(rtree_node_elm_t), CACHELINE); 
} 
rtree_node_alloc_t *JET_MUTABLE rtree_node_alloc = rtree_node_alloc_impl; 
 
static void 
rtree_node_dalloc_impl(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *node) { 
	/* Nodes are never deleted during normal operation. */ 
	not_reached(); 
} 
rtree_node_dalloc_t *JET_MUTABLE rtree_node_dalloc = 
    rtree_node_dalloc_impl; 
 
static rtree_leaf_elm_t * 
rtree_leaf_alloc_impl(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) { 
	return (rtree_leaf_elm_t *)base_alloc(tsdn, b0get(), nelms * 
	    sizeof(rtree_leaf_elm_t), CACHELINE); 
} 
rtree_leaf_alloc_t *JET_MUTABLE rtree_leaf_alloc = rtree_leaf_alloc_impl; 
 
static void 
rtree_leaf_dalloc_impl(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *leaf) { 
	/* Leaves are never deleted during normal operation. */ 
	not_reached(); 
} 
rtree_leaf_dalloc_t *JET_MUTABLE rtree_leaf_dalloc = 
    rtree_leaf_dalloc_impl; 
 
#ifdef JEMALLOC_JET 
#  if RTREE_HEIGHT > 1 
static void 
rtree_delete_subtree(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *subtree, 
    unsigned level) { 
	size_t nchildren = ZU(1) << rtree_levels[level].bits; 
	if (level + 2 < RTREE_HEIGHT) { 
		for (size_t i = 0; i < nchildren; i++) { 
			rtree_node_elm_t *node = 
			    (rtree_node_elm_t *)atomic_load_p(&subtree[i].child, 
			    ATOMIC_RELAXED); 
			if (node != NULL) { 
				rtree_delete_subtree(tsdn, rtree, node, level + 
				    1); 
			} 
		} 
	} else { 
		for (size_t i = 0; i < nchildren; i++) { 
			rtree_leaf_elm_t *leaf = 
			    (rtree_leaf_elm_t *)atomic_load_p(&subtree[i].child, 
			    ATOMIC_RELAXED); 
			if (leaf != NULL) { 
				rtree_leaf_dalloc(tsdn, rtree, leaf); 
			} 
		} 
	}

	if (subtree != rtree->root) { 
		rtree_node_dalloc(tsdn, rtree, subtree); 
	}
} 
#  endif 

void 
rtree_delete(tsdn_t *tsdn, rtree_t *rtree) { 
#  if RTREE_HEIGHT > 1 
	rtree_delete_subtree(tsdn, rtree, rtree->root, 0); 
#  endif 
}
#endif 

static rtree_node_elm_t * 
rtree_node_init(tsdn_t *tsdn, rtree_t *rtree, unsigned level, 
    atomic_p_t *elmp) { 
	malloc_mutex_lock(tsdn, &rtree->init_lock); 
	/* 
	 * If *elmp is non-null, then it was initialized with the init lock 
	 * held, so we can get by with 'relaxed' here. 
	 */ 
	rtree_node_elm_t *node = atomic_load_p(elmp, ATOMIC_RELAXED); 
	if (node == NULL) { 
		node = rtree_node_alloc(tsdn, rtree, ZU(1) << 
		    rtree_levels[level].bits); 
		if (node == NULL) { 
			malloc_mutex_unlock(tsdn, &rtree->init_lock); 
			return NULL; 
		} 
		/* 
		 * Even though we hold the lock, a later reader might not; we 
		 * need release semantics. 
		 */ 
		atomic_store_p(elmp, node, ATOMIC_RELEASE); 
	} 
	malloc_mutex_unlock(tsdn, &rtree->init_lock); 

	return node; 
} 

static rtree_leaf_elm_t * 
rtree_leaf_init(tsdn_t *tsdn, rtree_t *rtree, atomic_p_t *elmp) { 
	malloc_mutex_lock(tsdn, &rtree->init_lock); 
	/* 
	 * If *elmp is non-null, then it was initialized with the init lock 
	 * held, so we can get by with 'relaxed' here. 
	 */ 
	rtree_leaf_elm_t *leaf = atomic_load_p(elmp, ATOMIC_RELAXED); 
	if (leaf == NULL) { 
		leaf = rtree_leaf_alloc(tsdn, rtree, ZU(1) << 
		    rtree_levels[RTREE_HEIGHT-1].bits); 
		if (leaf == NULL) { 
			malloc_mutex_unlock(tsdn, &rtree->init_lock); 
			return NULL; 
		}
		/* 
		 * Even though we hold the lock, a later reader might not; we 
		 * need release semantics. 
		 */ 
		atomic_store_p(elmp, leaf, ATOMIC_RELEASE); 
	}
	malloc_mutex_unlock(tsdn, &rtree->init_lock); 
 
	return leaf; 
}

static bool 
rtree_node_valid(rtree_node_elm_t *node) { 
	return ((uintptr_t)node != (uintptr_t)0); 
} 

static bool 
rtree_leaf_valid(rtree_leaf_elm_t *leaf) { 
	return ((uintptr_t)leaf != (uintptr_t)0); 
}

static rtree_node_elm_t * 
rtree_child_node_tryread(rtree_node_elm_t *elm, bool dependent) { 
	rtree_node_elm_t *node; 

	if (dependent) { 
		node = (rtree_node_elm_t *)atomic_load_p(&elm->child, 
		    ATOMIC_RELAXED); 
	} else { 
		node = (rtree_node_elm_t *)atomic_load_p(&elm->child, 
		    ATOMIC_ACQUIRE); 
	} 
 
	assert(!dependent || node != NULL); 
	return node; 
}

static rtree_node_elm_t * 
rtree_child_node_read(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *elm, 
    unsigned level, bool dependent) { 
	rtree_node_elm_t *node; 

	node = rtree_child_node_tryread(elm, dependent); 
	if (!dependent && unlikely(!rtree_node_valid(node))) { 
		node = rtree_node_init(tsdn, rtree, level + 1, &elm->child); 
	} 
	assert(!dependent || node != NULL); 
	return node; 
}

static rtree_leaf_elm_t * 
rtree_child_leaf_tryread(rtree_node_elm_t *elm, bool dependent) { 
	rtree_leaf_elm_t *leaf; 

	if (dependent) { 
		leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child, 
		    ATOMIC_RELAXED); 
	} else { 
		leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child, 
		    ATOMIC_ACQUIRE); 
	} 
 
	assert(!dependent || leaf != NULL); 
	return leaf; 
}
 
static rtree_leaf_elm_t * 
rtree_child_leaf_read(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *elm, 
    unsigned level, bool dependent) { 
	rtree_leaf_elm_t *leaf; 
 
	leaf = rtree_child_leaf_tryread(elm, dependent); 
	if (!dependent && unlikely(!rtree_leaf_valid(leaf))) { 
		leaf = rtree_leaf_init(tsdn, rtree, &elm->child); 
	} 
	assert(!dependent || leaf != NULL); 
	return leaf; 
} 
 
rtree_leaf_elm_t * 
rtree_leaf_elm_lookup_hard(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 
    uintptr_t key, bool dependent, bool init_missing) { 
	rtree_node_elm_t *node; 
	rtree_leaf_elm_t *leaf; 
#if RTREE_HEIGHT > 1 
	node = rtree->root; 
#else 
	leaf = rtree->root; 
#endif 
 
	if (config_debug) { 
		uintptr_t leafkey = rtree_leafkey(key); 
		for (unsigned i = 0; i < RTREE_CTX_NCACHE; i++) { 
			assert(rtree_ctx->cache[i].leafkey != leafkey); 
		} 
		for (unsigned i = 0; i < RTREE_CTX_NCACHE_L2; i++) { 
			assert(rtree_ctx->l2_cache[i].leafkey != leafkey); 
		} 
	} 
 
#define RTREE_GET_CHILD(level) {					\ 
		assert(level < RTREE_HEIGHT-1);				\ 
		if (level != 0 && !dependent &&				\ 
		    unlikely(!rtree_node_valid(node))) {		\ 
			return NULL;					\ 
		}							\ 
		uintptr_t subkey = rtree_subkey(key, level);		\ 
		if (level + 2 < RTREE_HEIGHT) {				\ 
			node = init_missing ?				\ 
			    rtree_child_node_read(tsdn, rtree,		\ 
			    &node[subkey], level, dependent) :		\ 
			    rtree_child_node_tryread(&node[subkey],	\ 
			    dependent);					\ 
		} else {						\ 
			leaf = init_missing ?				\ 
			    rtree_child_leaf_read(tsdn, rtree,		\ 
			    &node[subkey], level, dependent) :		\ 
			    rtree_child_leaf_tryread(&node[subkey],	\ 
			    dependent);					\ 
		}							\ 
	} 
	/* 
	 * Cache replacement upon hard lookup (i.e. L1 & L2 rtree cache miss): 
	 * (1) evict last entry in L2 cache; (2) move the collision slot from L1 
	 * cache down to L2; and 3) fill L1. 
	 */ 
#define RTREE_GET_LEAF(level) {						\ 
		assert(level == RTREE_HEIGHT-1);			\ 
		if (!dependent && unlikely(!rtree_leaf_valid(leaf))) {	\ 
			return NULL;					\ 
		}							\ 
		if (RTREE_CTX_NCACHE_L2 > 1) {				\ 
			memmove(&rtree_ctx->l2_cache[1],		\ 
			    &rtree_ctx->l2_cache[0],			\ 
			    sizeof(rtree_ctx_cache_elm_t) *		\ 
			    (RTREE_CTX_NCACHE_L2 - 1));			\ 
		}							\ 
		size_t slot = rtree_cache_direct_map(key);		\ 
		rtree_ctx->l2_cache[0].leafkey =			\ 
		    rtree_ctx->cache[slot].leafkey;			\ 
		rtree_ctx->l2_cache[0].leaf =				\ 
		    rtree_ctx->cache[slot].leaf;			\ 
		uintptr_t leafkey = rtree_leafkey(key);			\ 
		rtree_ctx->cache[slot].leafkey = leafkey;		\ 
		rtree_ctx->cache[slot].leaf = leaf;			\ 
		uintptr_t subkey = rtree_subkey(key, level);		\ 
		return &leaf[subkey];					\ 
	} 
	if (RTREE_HEIGHT > 1) { 
		RTREE_GET_CHILD(0) 
	} 
	if (RTREE_HEIGHT > 2) { 
		RTREE_GET_CHILD(1) 
	} 
	if (RTREE_HEIGHT > 3) { 
		for (unsigned i = 2; i < RTREE_HEIGHT-1; i++) { 
			RTREE_GET_CHILD(i) 
		} 
	} 
	RTREE_GET_LEAF(RTREE_HEIGHT-1) 
#undef RTREE_GET_CHILD 
#undef RTREE_GET_LEAF 
	not_reached(); 
} 
 
void 
rtree_ctx_data_init(rtree_ctx_t *ctx) { 
	for (unsigned i = 0; i < RTREE_CTX_NCACHE; i++) { 
		rtree_ctx_cache_elm_t *cache = &ctx->cache[i]; 
		cache->leafkey = RTREE_LEAFKEY_INVALID; 
		cache->leaf = NULL; 
	} 
	for (unsigned i = 0; i < RTREE_CTX_NCACHE_L2; i++) { 
		rtree_ctx_cache_elm_t *cache = &ctx->l2_cache[i]; 
		cache->leafkey = RTREE_LEAFKEY_INVALID; 
		cache->leaf = NULL; 
	} 
}