1 files changed, 289 insertions, 96 deletions

diff --git a/dep/jemalloc/src/rtree.c b/dep/jemalloc/src/rtree.c
index af0d97e7530..53702cf7236 100644
--- a/dep/jemalloc/src/rtree.c
+++ b/dep/jemalloc/src/rtree.c
@@ -1,127 +1,320 @@
-#define	JEMALLOC_RTREE_C_
-#include "jemalloc/internal/jemalloc_internal.h"
+#define JEMALLOC_RTREE_C_
+#include "jemalloc/internal/jemalloc_preamble.h"
+#include "jemalloc/internal/jemalloc_internal_includes.h"
 
-static unsigned
-hmin(unsigned ha, unsigned hb)
-{
+#include "jemalloc/internal/assert.h"
+#include "jemalloc/internal/mutex.h"
 
-	return (ha < hb ? ha : hb);
+/*
+ * 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;
 }
 
-/* Only the most significant bits of keys passed to rtree_[gs]et() are used. */
-bool
-rtree_new(rtree_t *rtree, unsigned bits, rtree_node_alloc_t *alloc,
-    rtree_node_dalloc_t *dalloc)
-{
-	unsigned bits_in_leaf, height, i;
-
-	assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3));
-
-	bits_in_leaf = (bits % RTREE_BITS_PER_LEVEL) == 0 ? RTREE_BITS_PER_LEVEL
-	    : (bits % RTREE_BITS_PER_LEVEL);
-	if (bits > bits_in_leaf) {
-		height = 1 + (bits - bits_in_leaf) / RTREE_BITS_PER_LEVEL;
-		if ((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf != bits)
-			height++;
-	} else
-		height = 1;
-	assert((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf == bits);
-
-	rtree->alloc = alloc;
-	rtree->dalloc = dalloc;
-	rtree->height = height;
-
-	/* Root level. */
-	rtree->levels[0].subtree = NULL;
-	rtree->levels[0].bits = (height > 1) ? RTREE_BITS_PER_LEVEL :
-	    bits_in_leaf;
-	rtree->levels[0].cumbits = rtree->levels[0].bits;
-	/* Interior levels. */
-	for (i = 1; i < height-1; i++) {
-		rtree->levels[i].subtree = NULL;
-		rtree->levels[i].bits = RTREE_BITS_PER_LEVEL;
-		rtree->levels[i].cumbits = rtree->levels[i-1].cumbits +
-		    RTREE_BITS_PER_LEVEL;
-	}
-	/* Leaf level. */
-	if (height > 1) {
-		rtree->levels[height-1].subtree = NULL;
-		rtree->levels[height-1].bits = bits_in_leaf;
-		rtree->levels[height-1].cumbits = bits;
-	}
-
-	/* Compute lookup table to be used by rtree_start_level(). */
-	for (i = 0; i < RTREE_HEIGHT_MAX; i++) {
-		rtree->start_level[i] = hmin(RTREE_HEIGHT_MAX - 1 - i, height -
-		    1);
-	}
-
-	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_delete_subtree(rtree_t *rtree, rtree_node_elm_t *node, unsigned level)
-{
+rtree_node_dalloc_impl(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *node) {
+	/* Nodes are never deleted during normal operation. */
+	not_reached();
+}
+UNUSED rtree_node_dalloc_t *JET_MUTABLE rtree_node_dalloc =
+    rtree_node_dalloc_impl;
 
-	if (level + 1 < rtree->height) {
-		size_t nchildren, i;
+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;
 
-		nchildren = ZU(1) << rtree->levels[level].bits;
-		for (i = 0; i < nchildren; i++) {
-			rtree_node_elm_t *child = node[i].child;
-			if (child != NULL)
-				rtree_delete_subtree(rtree, child, level + 1);
+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();
+}
+UNUSED 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);
 	}
-	rtree->dalloc(node);
 }
+#  endif
 
 void
-rtree_delete(rtree_t *rtree)
-{
-	unsigned i;
+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;
+}
 
-	for (i = 0; i < rtree->height; i++) {
-		rtree_node_elm_t *subtree = rtree->levels[i].subtree;
-		if (subtree != NULL)
-			rtree_delete_subtree(rtree, subtree, i);
+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_node_init(rtree_t *rtree, unsigned level, rtree_node_elm_t **elmp)
-{
+rtree_child_node_tryread(rtree_node_elm_t *elm, bool dependent) {
 	rtree_node_elm_t *node;
 
-	if (atomic_cas_p((void **)elmp, NULL, RTREE_NODE_INITIALIZING)) {
-		/*
-		 * Another thread is already in the process of initializing.
-		 * Spin-wait until initialization is complete.
-		 */
-		do {
-			CPU_SPINWAIT;
-			node = atomic_read_p((void **)elmp);
-		} while (node == RTREE_NODE_INITIALIZING);
+	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 {
-		node = rtree->alloc(ZU(1) << rtree->levels[level].bits);
-		if (node == NULL)
-			return (NULL);
-		atomic_write_p((void **)elmp, node);
+		leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child,
+		    ATOMIC_ACQUIRE);
 	}
 
-	return (node);
+	assert(!dependent || leaf != NULL);
+	return leaf;
 }
 
-rtree_node_elm_t *
-rtree_subtree_read_hard(rtree_t *rtree, unsigned level)
-{
+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;
 
-	return (rtree_node_init(rtree, level, &rtree->levels[level].subtree));
+	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_node_elm_t *
-rtree_child_read_hard(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level)
-{
+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();
+}
 
-	return (rtree_node_init(rtree, level, &elm->child));
+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;
+	}
 }