Maintain two trees instead of one (old_chunks --> old_chunks_{ad,szad}) in

order to support re-use of multi-chunk unused regions within the DSS for
huge allocations.  This generalization is important to correct function
when mmap-based allocation is disabled.

Avoid zeroing re-used memory in the DSS unless it really needs to be
zeroed.

1 files changed, 183 insertions, 113 deletions

diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c
index 79ceb4b..28b2f4a 100644
--- a/lib/libc/stdlib/malloc.c
+++ b/lib/libc/stdlib/malloc.c
@@ -447,7 +447,10 @@ struct chunk_stats_s {
 typedef struct chunk_node_s chunk_node_t;
 struct chunk_node_s {
 	/* Linkage for the chunk tree. */
-	RB_ENTRY(chunk_node_s) link;
+	RB_ENTRY(chunk_node_s) link_ad;
+
+	/* Linkage for the chunk tree. */
+	RB_ENTRY(chunk_node_s) link_szad;
 
 	/*
 	 * Pointer to the chunk that this tree node is responsible for.  In some
@@ -460,8 +463,10 @@ struct chunk_node_s {
 	/* Total chunk size. */
 	size_t	size;
 };
-typedef struct chunk_tree_s chunk_tree_t;
-RB_HEAD(chunk_tree_s, chunk_node_s);
+typedef struct chunk_tree_ad_s chunk_tree_ad_t;
+RB_HEAD(chunk_tree_ad_s, chunk_node_s);
+typedef struct chunk_tree_szad_s chunk_tree_szad_t;
+RB_HEAD(chunk_tree_szad_s, chunk_node_s);
 
 /******************************************************************************/
 /*
@@ -713,7 +718,7 @@ static size_t		arena_maxclass; /* Max size class for arenas. */
 static malloc_mutex_t	chunks_mtx;
 
 /* Tree of chunks that are stand-alone huge allocations. */
-static chunk_tree_t	huge;
+static chunk_tree_ad_t	huge;
 
 #ifdef MALLOC_DSS
 /*
@@ -738,10 +743,13 @@ static size_t		huge_allocated;
 #endif
 
 /*
- * Tree of chunks that were previously allocated.  This is used when allocating
- * chunks, in an attempt to re-use address space.
+ * Trees of chunks that were previously allocated (trees differ only in node
+ * ordering).  These are used when allocating chunks, in an attempt to re-use
+ * address space.  Depending on funcition, different tree orderings are needed,
+ * which is why there are two trees with the same contents.
  */
-static chunk_tree_t	old_chunks;
+static chunk_tree_ad_t	old_chunks_ad;
+static chunk_tree_szad_t old_chunks_szad;
 
 /****************************/
 /*
@@ -864,7 +872,7 @@ static void	stats_print(arena_t *arena);
 #endif
 static void	*pages_map(void *addr, size_t size);
 static void	pages_unmap(void *addr, size_t size);
-static void	*chunk_alloc(size_t size);
+static void	*chunk_alloc(size_t size, bool zero);
 static void	chunk_dealloc(void *chunk, size_t size);
 #ifndef NO_TLS
 static arena_t	*choose_arena_hard(void);
@@ -1414,22 +1422,37 @@ stats_print(arena_t *arena)
  */
 
 static inline int
-chunk_comp(chunk_node_t *a, chunk_node_t *b)
+chunk_ad_comp(chunk_node_t *a, chunk_node_t *b)
 {
+	uintptr_t a_chunk = (uintptr_t)a->chunk;
+	uintptr_t b_chunk = (uintptr_t)b->chunk;
 
-	assert(a != NULL);
-	assert(b != NULL);
+	return ((a_chunk > b_chunk) - (a_chunk < b_chunk));
+}
 
-	if ((uintptr_t)a->chunk < (uintptr_t)b->chunk)
-		return (-1);
-	else if (a->chunk == b->chunk)
-		return (0);
-	else
-		return (1);
+/* Generate red-black tree code for address-ordered chunks. */
+RB_GENERATE_STATIC(chunk_tree_ad_s, chunk_node_s, link_ad, chunk_ad_comp)
+
+static inline int
+chunk_szad_comp(chunk_node_t *a, chunk_node_t *b)
+{
+	int ret;
+	size_t a_size = a->size;
+	size_t b_size = b->size;
+
+	ret = (a_size > b_size) - (a_size < b_size);
+	if (ret == 0) {
+		uintptr_t a_chunk = (uintptr_t)a->chunk;
+		uintptr_t b_chunk = (uintptr_t)b->chunk;
+
+		ret = (a_chunk > b_chunk) - (a_chunk < b_chunk);
+	}
+
+	return (ret);
 }
 
-/* Generate red-black tree code for chunks. */
-RB_GENERATE_STATIC(chunk_tree_s, chunk_node_s, link, chunk_comp)
+/* Generate red-black tree code for size/address-ordered chunks. */
+RB_GENERATE_STATIC(chunk_tree_szad_s, chunk_node_s, link_szad, chunk_szad_comp)
 
 static void *
 pages_map(void *addr, size_t size)
@@ -1575,51 +1598,62 @@ chunk_alloc_mmap(size_t size)
 }
 
 static void *
-chunk_alloc(size_t size)
+chunk_alloc(size_t size, bool zero)
 {
 	void *ret, *chunk;
 	chunk_node_t *tchunk, *delchunk;
+	chunk_node_t key;
 
 	assert(size != 0);
 	assert((size & chunksize_mask) == 0);
 
 	malloc_mutex_lock(&chunks_mtx);
 
-	if (size == chunksize) {
-		/*
-		 * Check for address ranges that were previously chunks and try
-		 * to use them.
-		 */
-
-		tchunk = RB_MIN(chunk_tree_s, &old_chunks);
-		while (tchunk != NULL) {
-			/* Found an address range.  Try to recycle it. */
-
-			chunk = tchunk->chunk;
-			delchunk = tchunk;
-			tchunk = RB_NEXT(chunk_tree_s, &old_chunks, delchunk);
-
-			/* Remove delchunk from the tree. */
-			RB_REMOVE(chunk_tree_s, &old_chunks, delchunk);
+	/*
+	 * Check for address ranges that were previously chunks and try
+	 * to use them.
+	 */
+	key.chunk = NULL;
+	key.size = size;
+	tchunk = RB_NFIND(chunk_tree_szad_s, &old_chunks_szad, &key);
+	while (tchunk != NULL) {
+		/* Found an address range.  Try to recycle it. */
+
+		chunk = tchunk->chunk;
+		delchunk = tchunk;
+		tchunk = RB_NEXT(chunk_tree_szad_s, &old_chunks_szad, delchunk);
+
+		/* Remove delchunk from the tree. */
+		RB_REMOVE(chunk_tree_szad_s, &old_chunks_szad, delchunk);
+		if (delchunk->size == size) {
+			RB_REMOVE(chunk_tree_ad_s, &old_chunks_ad, delchunk);
 			base_chunk_node_dealloc(delchunk);
+		} else {
+			/*
+			 * Insert the remainder of delchunk's address
+			 * range as a smaller chunk.  Its position within
+			 * old_chunks_ad does not change.
+			 */
+			delchunk->chunk =
+			    (void *)((uintptr_t)delchunk->chunk + size);
+			delchunk->size -= size;
+			RB_INSERT(chunk_tree_szad_s, &old_chunks_szad,
+			    delchunk);
+		}
 
 #ifdef MALLOC_DSS
-			if (opt_dss && (uintptr_t)chunk >= (uintptr_t)dss_base
-			    && (uintptr_t)chunk < (uintptr_t)dss_max) {
-				/* Re-use a previously freed DSS chunk. */
-				ret = chunk;
-				/*
-				 * Maintain invariant that all newly allocated
-				 * chunks are untouched or zero-filled.
-				 */
+		if (opt_dss && (uintptr_t)chunk >= (uintptr_t)dss_base
+		    && (uintptr_t)chunk < (uintptr_t)dss_max) {
+			/* Re-use a previously freed DSS chunk. */
+			ret = chunk;
+			if (zero)
 				memset(ret, 0, size);
-				goto RETURN;
-			}
+			goto RETURN;
+		}
 #endif
-			if ((ret = pages_map(chunk, size)) != NULL) {
-				/* Success. */
-				goto RETURN;
-			}
+		if ((ret = pages_map(chunk, size)) != NULL) {
+			/* Success. */
+			goto RETURN;
 		}
 	}
 
@@ -1642,19 +1676,21 @@ chunk_alloc(size_t size)
 	ret = NULL;
 RETURN:
 	if (ret != NULL) {
-		chunk_node_t key;
 		/*
-		 * Clean out any entries in old_chunks that overlap with the
+		 * Clean out any entries in old_chunks_* that overlap with the
 		 * memory we just allocated.
 		 */
 		key.chunk = ret;
-		tchunk = RB_NFIND(chunk_tree_s, &old_chunks, &key);
+		tchunk = RB_NFIND(chunk_tree_ad_s, &old_chunks_ad, &key);
 		while (tchunk != NULL
 		    && (uintptr_t)tchunk->chunk >= (uintptr_t)ret
 		    && (uintptr_t)tchunk->chunk < (uintptr_t)ret + size) {
 			delchunk = tchunk;
-			tchunk = RB_NEXT(chunk_tree_s, &old_chunks, delchunk);
-			RB_REMOVE(chunk_tree_s, &old_chunks, delchunk);
+			tchunk = RB_NEXT(chunk_tree_ad_s, &old_chunks_ad,
+			    delchunk);
+			RB_REMOVE(chunk_tree_ad_s, &old_chunks_ad, delchunk);
+			RB_REMOVE(chunk_tree_szad_s, &old_chunks_szad,
+			    delchunk);
 			base_chunk_node_dealloc(delchunk);
 		}
 
@@ -1673,11 +1709,62 @@ RETURN:
 	return (ret);
 }
 
+static inline void
+chunk_dealloc_record(void *chunk, size_t size)
+{
+	chunk_node_t *node, *prev;
+	chunk_node_t key;
+
+	key.chunk = (void *)((uintptr_t)chunk + size);
+	node = RB_NFIND(chunk_tree_ad_s, &old_chunks_ad, &key);
+	/* Try to coalesce forward. */
+	if (node != NULL) {
+		if (node->chunk == key.chunk) {
+			/*
+			 * Coalesce chunk with the following address range.
+			 * This does not change the position within
+			 * old_chunks_ad, so only remove/insert from/into
+			 * old_chunks_szad.
+			 */
+			RB_REMOVE(chunk_tree_szad_s, &old_chunks_szad, node);
+			node->chunk = chunk;
+			node->size += size;
+			RB_INSERT(chunk_tree_szad_s, &old_chunks_szad, node);
+		}
+	} else {
+		/* Coalescing forward failed, so insert a new node. */
+		node = base_chunk_node_alloc();
+		node->chunk = chunk;
+		node->size = size;
+		RB_INSERT(chunk_tree_ad_s, &old_chunks_ad, node);
+		RB_INSERT(chunk_tree_szad_s, &old_chunks_szad, node);
+	}
+
+	/* Try to coalesce backward. */
+	prev = RB_PREV(chunk_tree_ad_s, &old_chunks_ad, node);
+	if (prev != NULL && (void *)((uintptr_t)prev->chunk + prev->size) ==
+	    chunk) {
+		/*
+		 * Coalesce chunk with the previous address range.  This does
+		 * not change the position within old_chunks_ad, so only
+		 * remove/insert node from/into old_chunks_szad.
+		 */
+		RB_REMOVE(chunk_tree_ad_s, &old_chunks_ad, prev);
+		RB_REMOVE(chunk_tree_szad_s, &old_chunks_szad, prev);
+
+		RB_REMOVE(chunk_tree_szad_s, &old_chunks_szad, node);
+		node->chunk = prev->chunk;
+		node->size += prev->size;
+		RB_INSERT(chunk_tree_szad_s, &old_chunks_szad, node);
+
+		base_chunk_node_dealloc(prev);
+	}
+}
+
 #ifdef MALLOC_DSS
 static inline bool
 chunk_dealloc_dss(void *chunk, size_t size)
 {
-	chunk_node_t *node;
 
 	if ((uintptr_t)chunk >= (uintptr_t)dss_base
 	    && (uintptr_t)chunk < (uintptr_t)dss_max) {
@@ -1699,33 +1786,37 @@ chunk_dealloc_dss(void *chunk, size_t size)
 		    && sbrk(-(intptr_t)size) == dss_max) {
 			malloc_mutex_unlock(&dss_mtx);
 			if (dss_prev == dss_max) {
+				chunk_node_t *node;
+
 				/* Success. */
 				dss_prev = (void *)((intptr_t)dss_max
 				    - (intptr_t)size);
 				dss_max = dss_prev;
+
+				/*
+				 * There may now be an unused region at the top
+				 * of the DSS.  If so, recursively deallocate
+				 * it here.  This can cause at most one
+				 * recursion step, since the the chunk tree
+				 * entries are kept coalesced.
+				 */
+				node = RB_MAX(chunk_tree_ad_s, &old_chunks_ad);
+				if (node != NULL &&
+				    (void *)((uintptr_t)node->chunk +
+				    node->size) == dss_max) {
+					RB_REMOVE(chunk_tree_ad_s,
+					    &old_chunks_ad, node);
+					RB_REMOVE(chunk_tree_szad_s,
+					    &old_chunks_szad, node);
+					chunk_dealloc_dss(node->chunk,
+					    node->size);
+					base_chunk_node_dealloc(node);
+				}
 			}
 		} else {
-			size_t offset;
-
 			malloc_mutex_unlock(&dss_mtx);
 			madvise(chunk, size, MADV_FREE);
-
-			/*
-			 * Iteratively create records of each chunk-sized
-			 * memory region that 'chunk' is comprised of, so that
-			 * the address range can be recycled if memory usage
-			 * increases later on.
-			 */
-			for (offset = 0; offset < size; offset += chunksize) {
-				node = base_chunk_node_alloc();
-				if (node == NULL)
-					break;
-
-				node->chunk = (void *)((uintptr_t)chunk
-				    + (uintptr_t)offset);
-				node->size = chunksize;
-				RB_INSERT(chunk_tree_s, &old_chunks, node);
-			}
+			chunk_dealloc_record(chunk, size);
 		}
 
 		return (false);
@@ -1738,25 +1829,9 @@ chunk_dealloc_dss(void *chunk, size_t size)
 static inline void
 chunk_dealloc_mmap(void *chunk, size_t size)
 {
-	chunk_node_t *node;
 
 	pages_unmap(chunk, size);
-
-	/*
-	 * Make a record of the chunk's address, so that the address
-	 * range can be recycled if memory usage increases later on.
-	 * Don't bother to create entries if (size > chunksize), since
-	 * doing so could cause scalability issues for truly gargantuan
-	 * objects (many gigabytes or larger).
-	 */
-	if (size == chunksize) {
-		node = base_chunk_node_alloc();
-		if (node != NULL) {
-			node->chunk = (void *)(uintptr_t)chunk;
-			node->size = chunksize;
-			RB_INSERT(chunk_tree_s, &old_chunks, node);
-		}
-	}
+	chunk_dealloc_record(chunk, size);
 }
 
 static void
@@ -1941,16 +2016,13 @@ choose_arena_hard(void)
 static inline int
 arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b)
 {
+	uintptr_t a_chunk = (uintptr_t)a;
+	uintptr_t b_chunk = (uintptr_t)b;
 
 	assert(a != NULL);
 	assert(b != NULL);
 
-	if ((uintptr_t)a < (uintptr_t)b)
-		return (-1);
-	else if (a == b)
-		return (0);
-	else
-		return (1);
+	return ((a_chunk > b_chunk) - (a_chunk < b_chunk));
 }
 
 /* Generate red-black tree code for arena chunks. */
@@ -1959,16 +2031,13 @@ RB_GENERATE_STATIC(arena_chunk_tree_s, arena_chunk_s, link, arena_chunk_comp)
 static inline int
 arena_run_comp(arena_run_t *a, arena_run_t *b)
 {
+	uintptr_t a_run = (uintptr_t)a;
+	uintptr_t b_run = (uintptr_t)b;
 
 	assert(a != NULL);
 	assert(b != NULL);
 
-	if ((uintptr_t)a < (uintptr_t)b)
-		return (-1);
-	else if (a == b)
-		return (0);
-	else
-		return (1);
+	return ((a_run > b_run) - (a_run < b_run));
 }
 
 /* Generate red-black tree code for arena runs. */
@@ -2224,7 +2293,7 @@ arena_chunk_alloc(arena_t *arena)
 	} else {
 		unsigned i;
 
-		chunk = (arena_chunk_t *)chunk_alloc(chunksize);
+		chunk = (arena_chunk_t *)chunk_alloc(chunksize, true);
 		if (chunk == NULL)
 			return (NULL);
 #ifdef MALLOC_STATS
@@ -3284,7 +3353,7 @@ huge_malloc(size_t size, bool zero)
 	if (node == NULL)
 		return (NULL);
 
-	ret = chunk_alloc(csize);
+	ret = chunk_alloc(csize, zero);
 	if (ret == NULL) {
 		base_chunk_node_dealloc(node);
 		return (NULL);
@@ -3295,7 +3364,7 @@ huge_malloc(size_t size, bool zero)
 	node->size = csize;
 
 	malloc_mutex_lock(&chunks_mtx);
-	RB_INSERT(chunk_tree_s, &huge, node);
+	RB_INSERT(chunk_tree_ad_s, &huge, node);
 #ifdef MALLOC_STATS
 	huge_nmalloc++;
 	huge_allocated += csize;
@@ -3342,7 +3411,7 @@ huge_palloc(size_t alignment, size_t size)
 	if (node == NULL)
 		return (NULL);
 
-	ret = chunk_alloc(alloc_size);
+	ret = chunk_alloc(alloc_size, false);
 	if (ret == NULL) {
 		base_chunk_node_dealloc(node);
 		return (NULL);
@@ -3377,7 +3446,7 @@ huge_palloc(size_t alignment, size_t size)
 	node->size = chunk_size;
 
 	malloc_mutex_lock(&chunks_mtx);
-	RB_INSERT(chunk_tree_s, &huge, node);
+	RB_INSERT(chunk_tree_ad_s, &huge, node);
 #ifdef MALLOC_STATS
 	huge_nmalloc++;
 	huge_allocated += chunk_size;
@@ -3444,10 +3513,10 @@ huge_dalloc(void *ptr)
 
 	/* Extract from tree of huge allocations. */
 	key.chunk = ptr;
-	node = RB_FIND(chunk_tree_s, &huge, &key);
+	node = RB_FIND(chunk_tree_ad_s, &huge, &key);
 	assert(node != NULL);
 	assert(node->chunk == ptr);
-	RB_REMOVE(chunk_tree_s, &huge, node);
+	RB_REMOVE(chunk_tree_ad_s, &huge, node);
 
 #ifdef MALLOC_STATS
 	huge_ndalloc++;
@@ -3612,7 +3681,7 @@ isalloc(const void *ptr)
 
 		/* Extract from tree of huge allocations. */
 		key.chunk = __DECONST(void *, ptr);
-		node = RB_FIND(chunk_tree_s, &huge, &key);
+		node = RB_FIND(chunk_tree_ad_s, &huge, &key);
 		assert(node != NULL);
 
 		ret = node->size;
@@ -4173,7 +4242,8 @@ OUT:
 	huge_ndalloc = 0;
 	huge_allocated = 0;
 #endif
-	RB_INIT(&old_chunks);
+	RB_INIT(&old_chunks_ad);
+	RB_INIT(&old_chunks_szad);
 
 	/* Initialize base allocation data structures. */
 #ifdef MALLOC_STATS