Use rtree rather than [sz]ad trees for chunk split/coalesce operations.

3 files changed, 12 insertions, 31 deletions

diff --git a/include/jemalloc/internal/arena.h b/include/jemalloc/internal/arena.h
index 52e7197..97b5329 100644
--- a/include/jemalloc/internal/arena.h
+++ b/include/jemalloc/internal/arena.h
@@ -418,16 +418,11 @@ struct arena_s {
 	malloc_mutex_t		huge_mtx;
 
 	/*
-	 * Trees of chunks that were previously allocated (trees differ only in
-	 * extent ordering).  These are used when allocating chunks, in an
-	 * attempt to re-use address space.  Depending on function, different
-	 * tree orderings are needed, which is why there are two trees with the
-	 * same contents.
+	 * Trees of chunks that were previously allocated.  These are used when
+	 * allocating chunks, in an attempt to re-use address space.
 	 */
 	extent_tree_t		chunks_szad_cached;
-	extent_tree_t		chunks_ad_cached;
 	extent_tree_t		chunks_szad_retained;
-	extent_tree_t		chunks_ad_retained;
 
 	malloc_mutex_t		chunks_mtx;
 	/* Cache of extent structures that were allocated via base_alloc(). */
diff --git a/include/jemalloc/internal/extent.h b/include/jemalloc/internal/extent.h
index d6376d5..f067a29 100644
--- a/include/jemalloc/internal/extent.h
+++ b/include/jemalloc/internal/extent.h
@@ -55,9 +55,6 @@ struct extent_s {
 		/* Linkage for arena's achunks, huge, and node_cache lists. */
 		ql_elm(extent_t)	ql_link;
 	};
-
-	/* Linkage for the address-ordered tree. */
-	rb_node(extent_t)	ad_link;
 };
 typedef rb_tree(extent_t) extent_tree_t;
 
@@ -67,8 +64,6 @@ typedef rb_tree(extent_t) extent_tree_t;
 
 rb_proto(, extent_tree_szad_, extent_tree_t, extent_t)
 
-rb_proto(, extent_tree_ad_, extent_tree_t, extent_t)
-
 #endif /* JEMALLOC_H_EXTERNS */
 /******************************************************************************/
 #ifdef JEMALLOC_H_INLINES
@@ -79,6 +74,7 @@ void	*extent_addr_get(const extent_t *extent);
 size_t	extent_size_get(const extent_t *extent);
 void	*extent_past_get(const extent_t *extent);
 bool	extent_active_get(const extent_t *extent);
+bool	extent_retained_get(const extent_t *extent);
 bool	extent_zeroed_get(const extent_t *extent);
 bool	extent_committed_get(const extent_t *extent);
 bool	extent_slab_get(const extent_t *extent);
@@ -135,6 +131,14 @@ extent_active_get(const extent_t *extent)
 }
 
 JEMALLOC_INLINE bool
+extent_retained_get(const extent_t *extent)
+{
+
+	assert(!extent->e_slab);
+	return (qr_next(&extent->rd, rd_link) == &extent->rd);
+}
+
+JEMALLOC_INLINE bool
 extent_zeroed_get(const extent_t *extent)
 {
 
diff --git a/include/jemalloc/internal/private_symbols.txt b/include/jemalloc/internal/private_symbols.txt
index f81cecc..247b873 100644
--- a/include/jemalloc/internal/private_symbols.txt
+++ b/include/jemalloc/internal/private_symbols.txt
@@ -219,29 +219,11 @@ extent_init
 extent_past_get
 extent_prof_tctx_get
 extent_prof_tctx_set
+extent_retained_get
 extent_size_get
 extent_size_set
 extent_slab_get
 extent_slab_set
-extent_tree_ad_destroy
-extent_tree_ad_destroy_recurse
-extent_tree_ad_empty
-extent_tree_ad_first
-extent_tree_ad_insert
-extent_tree_ad_iter
-extent_tree_ad_iter_recurse
-extent_tree_ad_iter_start
-extent_tree_ad_last
-extent_tree_ad_new
-extent_tree_ad_next
-extent_tree_ad_nsearch
-extent_tree_ad_prev
-extent_tree_ad_psearch
-extent_tree_ad_remove
-extent_tree_ad_reverse_iter
-extent_tree_ad_reverse_iter_recurse
-extent_tree_ad_reverse_iter_start
-extent_tree_ad_search
 extent_tree_szad_destroy
 extent_tree_szad_destroy_recurse
 extent_tree_szad_empty