Prefer old/low extent_t structures during reuse.

Rather than using a LIFO queue to track available extent_t structures,
use a red-black tree, and always choose the oldest/lowest available
during reuse.

3 files changed, 19 insertions, 18 deletions

diff --git a/src/arena.c b/src/arena.c
index 5b540ce..7451140 100644
--- a/src/arena.c
+++ b/src/arena.c
@@ -314,8 +314,8 @@ arena_stats_merge(tsdn_t *tsdn, arena_t *arena, unsigned *nthreads,
 
 	/* Gather per arena mutex profiling data. */
 	READ_ARENA_MUTEX_PROF_DATA(large_mtx, arena_prof_mutex_large);
-	READ_ARENA_MUTEX_PROF_DATA(extent_freelist_mtx,
-	    arena_prof_mutex_extent_freelist)
+	READ_ARENA_MUTEX_PROF_DATA(extent_avail_mtx,
+	    arena_prof_mutex_extent_avail)
 	READ_ARENA_MUTEX_PROF_DATA(extents_dirty.mtx,
 	    arena_prof_mutex_extents_dirty)
 	READ_ARENA_MUTEX_PROF_DATA(extents_muzzy.mtx,
@@ -1937,8 +1937,8 @@ arena_new(tsdn_t *tsdn, unsigned ind, extent_hooks_t *extent_hooks) {
 		    ATOMIC_RELAXED);
 	}
 
-	extent_list_init(&arena->extent_freelist);
-	if (malloc_mutex_init(&arena->extent_freelist_mtx, "extent_freelist",
+	extent_avail_new(&arena->extent_avail);
+	if (malloc_mutex_init(&arena->extent_avail_mtx, "extent_avail",
 	    WITNESS_RANK_EXTENT_FREELIST)) {
 		goto label_error;
 	}
@@ -2007,7 +2007,7 @@ arena_prefork2(tsdn_t *tsdn, arena_t *arena) {
 
 void
 arena_prefork3(tsdn_t *tsdn, arena_t *arena) {
-	malloc_mutex_prefork(tsdn, &arena->extent_freelist_mtx);
+	malloc_mutex_prefork(tsdn, &arena->extent_avail_mtx);
 }
 
 void
@@ -2036,7 +2036,7 @@ arena_postfork_parent(tsdn_t *tsdn, arena_t *arena) {
 	}
 	malloc_mutex_postfork_parent(tsdn, &arena->large_mtx);
 	base_postfork_parent(tsdn, arena->base);
-	malloc_mutex_postfork_parent(tsdn, &arena->extent_freelist_mtx);
+	malloc_mutex_postfork_parent(tsdn, &arena->extent_avail_mtx);
 	extents_postfork_parent(tsdn, &arena->extents_dirty);
 	extents_postfork_parent(tsdn, &arena->extents_muzzy);
 	extents_postfork_parent(tsdn, &arena->extents_retained);
@@ -2056,7 +2056,7 @@ arena_postfork_child(tsdn_t *tsdn, arena_t *arena) {
 	}
 	malloc_mutex_postfork_child(tsdn, &arena->large_mtx);
 	base_postfork_child(tsdn, arena->base);
-	malloc_mutex_postfork_child(tsdn, &arena->extent_freelist_mtx);
+	malloc_mutex_postfork_child(tsdn, &arena->extent_avail_mtx);
 	extents_postfork_child(tsdn, &arena->extents_dirty);
 	extents_postfork_child(tsdn, &arena->extents_muzzy);
 	extents_postfork_child(tsdn, &arena->extents_retained);
diff --git a/src/ctl.c b/src/ctl.c
index 6d6fadc..7a1b03f 100644
--- a/src/ctl.c
+++ b/src/ctl.c
@@ -2475,7 +2475,7 @@ stats_mutexes_reset_ctl(tsd_t *tsd, const size_t *mib, size_t miblen,
 			continue;
 		}
 		MUTEX_PROF_RESET(arena->large_mtx);
-		MUTEX_PROF_RESET(arena->extent_freelist_mtx);
+		MUTEX_PROF_RESET(arena->extent_avail_mtx);
 		MUTEX_PROF_RESET(arena->extents_dirty.mtx);
 		MUTEX_PROF_RESET(arena->extents_muzzy.mtx);
 		MUTEX_PROF_RESET(arena->extents_retained.mtx);
diff --git a/src/extent.c b/src/extent.c
index c999ae6..0bfc555 100644
--- a/src/extent.c
+++ b/src/extent.c
@@ -88,20 +88,21 @@ static void extent_record(tsdn_t *tsdn, arena_t *arena,
 
 /******************************************************************************/
 
+rb_gen(UNUSED, extent_avail_, extent_tree_t, extent_t, rb_link,
+    extent_esnead_comp)
+
 extent_t *
 extent_alloc(tsdn_t *tsdn, arena_t *arena) {
-	extent_t *extent;
-
 	witness_assert_depth_to_rank(tsdn, WITNESS_RANK_CORE, 0);
 
-	malloc_mutex_lock(tsdn, &arena->extent_freelist_mtx);
-	extent = extent_list_last(&arena->extent_freelist);
+	malloc_mutex_lock(tsdn, &arena->extent_avail_mtx);
+	extent_t *extent = extent_avail_first(&arena->extent_avail);
 	if (extent == NULL) {
-		malloc_mutex_unlock(tsdn, &arena->extent_freelist_mtx);
+		malloc_mutex_unlock(tsdn, &arena->extent_avail_mtx);
 		return base_alloc_extent(tsdn, arena->base);
 	}
-	extent_list_remove(&arena->extent_freelist, extent);
-	malloc_mutex_unlock(tsdn, &arena->extent_freelist_mtx);
+	extent_avail_remove(&arena->extent_avail, extent);
+	malloc_mutex_unlock(tsdn, &arena->extent_avail_mtx);
 	return extent;
 }
 
@@ -109,9 +110,9 @@ void
 extent_dalloc(tsdn_t *tsdn, arena_t *arena, extent_t *extent) {
 	witness_assert_depth_to_rank(tsdn, WITNESS_RANK_CORE, 0);
 
-	malloc_mutex_lock(tsdn, &arena->extent_freelist_mtx);
-	extent_list_append(&arena->extent_freelist, extent);
-	malloc_mutex_unlock(tsdn, &arena->extent_freelist_mtx);
+	malloc_mutex_lock(tsdn, &arena->extent_avail_mtx);
+	extent_avail_insert(&arena->extent_avail, extent);
+	malloc_mutex_unlock(tsdn, &arena->extent_avail_mtx);
 }
 
 extent_hooks_t *