1 files changed, 44 insertions, 116 deletions

diff --git a/deps/jemalloc/include/jemalloc/internal/rtree.h b/deps/jemalloc/include/jemalloc/internal/rtree.h
index 8d0c584da..28ae9d1dd 100644
--- a/deps/jemalloc/include/jemalloc/internal/rtree.h
+++ b/deps/jemalloc/include/jemalloc/internal/rtree.h
@@ -15,10 +15,9 @@ typedef struct rtree_s rtree_t;
  * machine address width.
  */
 #define	LG_RTREE_BITS_PER_LEVEL	4
-#define	RTREE_BITS_PER_LEVEL	(1U << LG_RTREE_BITS_PER_LEVEL)
-/* Maximum rtree height. */
+#define	RTREE_BITS_PER_LEVEL	(ZU(1) << LG_RTREE_BITS_PER_LEVEL)
 #define	RTREE_HEIGHT_MAX						\
-    ((1U << (LG_SIZEOF_PTR+3)) / RTREE_BITS_PER_LEVEL)
+    ((ZU(1) << (LG_SIZEOF_PTR+3)) / RTREE_BITS_PER_LEVEL)
 
 /* Used for two-stage lock-free node initialization. */
 #define	RTREE_NODE_INITIALIZING	((rtree_node_elm_t *)0x1)
@@ -112,25 +111,22 @@ unsigned	rtree_start_level(rtree_t *rtree, uintptr_t key);
 uintptr_t	rtree_subkey(rtree_t *rtree, uintptr_t key, unsigned level);
 
 bool	rtree_node_valid(rtree_node_elm_t *node);
-rtree_node_elm_t	*rtree_child_tryread(rtree_node_elm_t *elm,
-    bool dependent);
+rtree_node_elm_t	*rtree_child_tryread(rtree_node_elm_t *elm);
 rtree_node_elm_t	*rtree_child_read(rtree_t *rtree, rtree_node_elm_t *elm,
-    unsigned level, bool dependent);
+    unsigned level);
 extent_node_t	*rtree_val_read(rtree_t *rtree, rtree_node_elm_t *elm,
     bool dependent);
 void	rtree_val_write(rtree_t *rtree, rtree_node_elm_t *elm,
     const extent_node_t *val);
-rtree_node_elm_t	*rtree_subtree_tryread(rtree_t *rtree, unsigned level,
-    bool dependent);
-rtree_node_elm_t	*rtree_subtree_read(rtree_t *rtree, unsigned level,
-    bool dependent);
+rtree_node_elm_t	*rtree_subtree_tryread(rtree_t *rtree, unsigned level);
+rtree_node_elm_t	*rtree_subtree_read(rtree_t *rtree, unsigned level);
 
 extent_node_t	*rtree_get(rtree_t *rtree, uintptr_t key, bool dependent);
 bool	rtree_set(rtree_t *rtree, uintptr_t key, const extent_node_t *val);
 #endif
 
 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_RTREE_C_))
-JEMALLOC_ALWAYS_INLINE unsigned
+JEMALLOC_INLINE unsigned
 rtree_start_level(rtree_t *rtree, uintptr_t key)
 {
 	unsigned start_level;
@@ -144,7 +140,7 @@ rtree_start_level(rtree_t *rtree, uintptr_t key)
 	return (start_level);
 }
 
-JEMALLOC_ALWAYS_INLINE uintptr_t
+JEMALLOC_INLINE uintptr_t
 rtree_subkey(rtree_t *rtree, uintptr_t key, unsigned level)
 {
 
@@ -153,40 +149,37 @@ rtree_subkey(rtree_t *rtree, uintptr_t key, unsigned level)
 	    rtree->levels[level].bits) - 1));
 }
 
-JEMALLOC_ALWAYS_INLINE bool
+JEMALLOC_INLINE bool
 rtree_node_valid(rtree_node_elm_t *node)
 {
 
 	return ((uintptr_t)node > (uintptr_t)RTREE_NODE_INITIALIZING);
 }
 
-JEMALLOC_ALWAYS_INLINE rtree_node_elm_t *
-rtree_child_tryread(rtree_node_elm_t *elm, bool dependent)
+JEMALLOC_INLINE rtree_node_elm_t *
+rtree_child_tryread(rtree_node_elm_t *elm)
 {
 	rtree_node_elm_t *child;
 
 	/* Double-checked read (first read may be stale. */
 	child = elm->child;
-	if (!dependent && !rtree_node_valid(child))
+	if (!rtree_node_valid(child))
 		child = atomic_read_p(&elm->pun);
-	assert(!dependent || child != NULL);
 	return (child);
 }
 
-JEMALLOC_ALWAYS_INLINE rtree_node_elm_t *
-rtree_child_read(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level,
-    bool dependent)
+JEMALLOC_INLINE rtree_node_elm_t *
+rtree_child_read(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level)
 {
 	rtree_node_elm_t *child;
 
-	child = rtree_child_tryread(elm, dependent);
-	if (!dependent && unlikely(!rtree_node_valid(child)))
+	child = rtree_child_tryread(elm);
+	if (unlikely(!rtree_node_valid(child)))
 		child = rtree_child_read_hard(rtree, elm, level);
-	assert(!dependent || child != NULL);
 	return (child);
 }
 
-JEMALLOC_ALWAYS_INLINE extent_node_t *
+JEMALLOC_INLINE extent_node_t *
 rtree_val_read(rtree_t *rtree, rtree_node_elm_t *elm, bool dependent)
 {
 
@@ -215,119 +208,54 @@ rtree_val_write(rtree_t *rtree, rtree_node_elm_t *elm, const extent_node_t *val)
 	atomic_write_p(&elm->pun, val);
 }
 
-JEMALLOC_ALWAYS_INLINE rtree_node_elm_t *
-rtree_subtree_tryread(rtree_t *rtree, unsigned level, bool dependent)
+JEMALLOC_INLINE rtree_node_elm_t *
+rtree_subtree_tryread(rtree_t *rtree, unsigned level)
 {
 	rtree_node_elm_t *subtree;
 
 	/* Double-checked read (first read may be stale. */
 	subtree = rtree->levels[level].subtree;
-	if (!dependent && unlikely(!rtree_node_valid(subtree)))
+	if (!rtree_node_valid(subtree))
 		subtree = atomic_read_p(&rtree->levels[level].subtree_pun);
-	assert(!dependent || subtree != NULL);
 	return (subtree);
 }
 
-JEMALLOC_ALWAYS_INLINE rtree_node_elm_t *
-rtree_subtree_read(rtree_t *rtree, unsigned level, bool dependent)
+JEMALLOC_INLINE rtree_node_elm_t *
+rtree_subtree_read(rtree_t *rtree, unsigned level)
 {
 	rtree_node_elm_t *subtree;
 
-	subtree = rtree_subtree_tryread(rtree, level, dependent);
-	if (!dependent && unlikely(!rtree_node_valid(subtree)))
+	subtree = rtree_subtree_tryread(rtree, level);
+	if (unlikely(!rtree_node_valid(subtree)))
 		subtree = rtree_subtree_read_hard(rtree, level);
-	assert(!dependent || subtree != NULL);
 	return (subtree);
 }
 
-JEMALLOC_ALWAYS_INLINE extent_node_t *
+JEMALLOC_INLINE extent_node_t *
 rtree_get(rtree_t *rtree, uintptr_t key, bool dependent)
 {
 	uintptr_t subkey;
-	unsigned start_level;
-	rtree_node_elm_t *node;
+	unsigned i, start_level;
+	rtree_node_elm_t *node, *child;
 
 	start_level = rtree_start_level(rtree, key);
 
-	node = rtree_subtree_tryread(rtree, start_level, dependent);
-#define	RTREE_GET_BIAS	(RTREE_HEIGHT_MAX - rtree->height)
-	switch (start_level + RTREE_GET_BIAS) {
-#define	RTREE_GET_SUBTREE(level)					\
-	case level:							\
-		assert(level < (RTREE_HEIGHT_MAX-1));			\
-		if (!dependent && unlikely(!rtree_node_valid(node)))	\
-			return (NULL);					\
-		subkey = rtree_subkey(rtree, key, level -		\
-		    RTREE_GET_BIAS);					\
-		node = rtree_child_tryread(&node[subkey], dependent);	\
-		/* Fall through. */
-#define	RTREE_GET_LEAF(level)						\
-	case level:							\
-		assert(level == (RTREE_HEIGHT_MAX-1));			\
-		if (!dependent && unlikely(!rtree_node_valid(node)))	\
-			return (NULL);					\
-		subkey = rtree_subkey(rtree, key, level -		\
-		    RTREE_GET_BIAS);					\
-		/*							\
-		 * node is a leaf, so it contains values rather than	\
-		 * child pointers.					\
-		 */							\
-		return (rtree_val_read(rtree, &node[subkey],		\
-		    dependent));
-#if RTREE_HEIGHT_MAX > 1
-	RTREE_GET_SUBTREE(0)
-#endif
-#if RTREE_HEIGHT_MAX > 2
-	RTREE_GET_SUBTREE(1)
-#endif
-#if RTREE_HEIGHT_MAX > 3
-	RTREE_GET_SUBTREE(2)
-#endif
-#if RTREE_HEIGHT_MAX > 4
-	RTREE_GET_SUBTREE(3)
-#endif
-#if RTREE_HEIGHT_MAX > 5
-	RTREE_GET_SUBTREE(4)
-#endif
-#if RTREE_HEIGHT_MAX > 6
-	RTREE_GET_SUBTREE(5)
-#endif
-#if RTREE_HEIGHT_MAX > 7
-	RTREE_GET_SUBTREE(6)
-#endif
-#if RTREE_HEIGHT_MAX > 8
-	RTREE_GET_SUBTREE(7)
-#endif
-#if RTREE_HEIGHT_MAX > 9
-	RTREE_GET_SUBTREE(8)
-#endif
-#if RTREE_HEIGHT_MAX > 10
-	RTREE_GET_SUBTREE(9)
-#endif
-#if RTREE_HEIGHT_MAX > 11
-	RTREE_GET_SUBTREE(10)
-#endif
-#if RTREE_HEIGHT_MAX > 12
-	RTREE_GET_SUBTREE(11)
-#endif
-#if RTREE_HEIGHT_MAX > 13
-	RTREE_GET_SUBTREE(12)
-#endif
-#if RTREE_HEIGHT_MAX > 14
-	RTREE_GET_SUBTREE(13)
-#endif
-#if RTREE_HEIGHT_MAX > 15
-	RTREE_GET_SUBTREE(14)
-#endif
-#if RTREE_HEIGHT_MAX > 16
-#  error Unsupported RTREE_HEIGHT_MAX
-#endif
-	RTREE_GET_LEAF(RTREE_HEIGHT_MAX-1)
-#undef RTREE_GET_SUBTREE
-#undef RTREE_GET_LEAF
-	default: not_reached();
+	for (i = start_level, node = rtree_subtree_tryread(rtree, start_level);
+	    /**/; i++, node = child) {
+		if (!dependent && unlikely(!rtree_node_valid(node)))
+			return (NULL);
+		subkey = rtree_subkey(rtree, key, i);
+		if (i == rtree->height - 1) {
+			/*
+			 * node is a leaf, so it contains values rather than
+			 * child pointers.
+			 */
+			return (rtree_val_read(rtree, &node[subkey],
+			    dependent));
+		}
+		assert(i < rtree->height - 1);
+		child = rtree_child_tryread(&node[subkey]);
 	}
-#undef RTREE_GET_BIAS
 	not_reached();
 }
 
@@ -340,7 +268,7 @@ rtree_set(rtree_t *rtree, uintptr_t key, const extent_node_t *val)
 
 	start_level = rtree_start_level(rtree, key);
 
-	node = rtree_subtree_read(rtree, start_level, false);
+	node = rtree_subtree_read(rtree, start_level);
 	if (node == NULL)
 		return (true);
 	for (i = start_level; /**/; i++, node = child) {
@@ -354,7 +282,7 @@ rtree_set(rtree_t *rtree, uintptr_t key, const extent_node_t *val)
 			return (false);
 		}
 		assert(i + 1 < rtree->height);
-		child = rtree_child_read(rtree, &node[subkey], i, false);
+		child = rtree_child_read(rtree, &node[subkey], i);
 		if (child == NULL)
 			return (true);
 	}