Track dirty unused pages so that they can be purged if they exceed a

threshold, according to the 'F' MALLOC_OPTIONS flag.  This obsoletes the
'H' flag.

Try to realloc() large objects in place.  This substantially speeds up
incremental large reallocations in the common case.

Fix a bug in arena_ralloc() that caused relocation of sub-page objects
even if the old and new sizes were in the same size class.

Maintain trees of runs and simplify the per-chunk page map.  This allows
logarithmic-time searching for sufficiently large runs in
arena_run_alloc(), whereas the previous algorithm required linear time
in the worst case.

Break various large functions into smaller sub-functions, and inline
only the functions that are in the fast path for small object
allocation/deallocation.

Remove an unnecessary check in base_pages_alloc_mmap().

Avoid integer division in choose_arena() for the NO_TLS case on
single-CPU systems.

2 files changed, 973 insertions, 679 deletions

diff --git a/lib/libc/stdlib/malloc.3 b/lib/libc/stdlib/malloc.3
index 466accc..1d33e6a 100644
--- a/lib/libc/stdlib/malloc.3
+++ b/lib/libc/stdlib/malloc.3
@@ -32,7 +32,7 @@
 .\"     @(#)malloc.3	8.1 (Berkeley) 6/4/93
 .\" $FreeBSD$
 .\"
-.Dd January 3, 2008
+.Dd February 5, 2008
 .Dt MALLOC 3
 .Os
 .Sh NAME
@@ -95,7 +95,7 @@ bytes.
 The contents of the memory are unchanged up to the lesser of the new and
 old sizes.
 If the new size is larger,
-the value of the newly allocated portion of the memory is undefined.
+the contents of the newly allocated portion of the memory are undefined.
 Upon success, the memory referenced by
 .Fa ptr
 is freed and a pointer to the newly allocated memory is returned.
@@ -204,15 +204,16 @@ This option is enabled by default.
 See the
 .Dq M
 option for related information and interactions.
-.It H
-Use
-.Xr madvise 2
-when pages within a chunk are no longer in use, but the chunk as a whole cannot
-yet be deallocated.
-This is primarily of use when swapping is a real possibility, due to the high
-overhead of the
-.Fn madvise
-system call.
+.It F
+Double/halve the per-arena maximum number of dirty unused pages that are
+allowed to accumulate before informing the kernel about at least half of those
+pages via
+.Xr madvise 2 .
+This provides the kernel with sufficient information to recycle dirty pages if
+physical memory becomes scarce and the pages remain unused.
+The default is 512 pages per arena;
+.Ev MALLOC_OPTIONS=10f
+will prevent any dirty unused pages from accumulating.
 .It J
 Each byte of new memory allocated by
 .Fn malloc ,
@@ -384,11 +385,12 @@ separately in a single data structure that is shared by all threads.
 Huge objects are used by applications infrequently enough that this single
 data structure is not a scalability issue.
 .Pp
-Each chunk that is managed by an arena tracks its contents in a page map as
-runs of contiguous pages (unused, backing a set of small objects, or backing
-one large object).
+Each chunk that is managed by an arena tracks its contents as runs of
+contiguous pages (unused, backing a set of small objects, or backing one large
+object).
 The combination of chunk alignment and chunk page maps makes it possible to
-determine all metadata regarding small and large allocations in constant time.
+determine all metadata regarding small and large allocations in
+constant and logarithmic time, respectively.
 .Pp
 Small objects are managed in groups by page runs.
 Each run maintains a bitmap that tracks which regions are in use.
diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c
index abe367a..40a2805 100644
--- a/lib/libc/stdlib/malloc.c
+++ b/lib/libc/stdlib/malloc.c
@@ -254,6 +254,9 @@ __FBSDID("$FreeBSD$");
  */
 #define	CHUNK_2POW_DEFAULT	20
 
+/* Maximum number of dirty pages per arena. */
+#define	DIRTY_MAX_DEFAULT	(1U << 9)
+
 /*
  * Maximum size of L1 cache line.  This is used to avoid cache line aliasing,
  * so over-estimates are okay (up to a point), but under-estimates will
@@ -294,7 +297,11 @@ __FBSDID("$FreeBSD$");
 #define	RUN_MAX_OVRHD		0x0000003dU
 #define	RUN_MAX_OVRHD_RELAX	0x00001800U
 
-/* Put a cap on small object run size.  This overrides RUN_MAX_OVRHD. */
+/*
+ * Put a cap on small object run size.  This overrides RUN_MAX_OVRHD.  Note
+ * that small runs must be small enough that page offsets can fit within the
+ * CHUNK_MAP_POS_MASK bits.
+ */
 #define	RUN_MAX_SMALL_2POW	15
 #define	RUN_MAX_SMALL		(1U << RUN_MAX_SMALL_2POW)
 
@@ -405,6 +412,15 @@ struct arena_stats_s {
 	/* Number of bytes currently mapped. */
 	size_t		mapped;
 
+	/*
+	 * Total number of purge sweeps, total number of madvise calls made,
+	 * and total pages purged in order to keep dirty unused memory under
+	 * control.
+	 */
+	uint64_t	npurge;
+	uint64_t	nmadvise;
+	uint64_t	purged;
+
 	/* Per-size-category statistics. */
 	size_t		allocated_small;
 	uint64_t	nmalloc_small;
@@ -440,37 +456,28 @@ struct chunk_stats_s {
 
 /******************************************************************************/
 /*
- * Chunk data structures.
+ * Extent data structures.
  */
 
-/* Tree of chunks. */
-typedef struct chunk_node_s chunk_node_t;
-struct chunk_node_s {
-	/* Linkage for the address-ordered chunk tree. */
-	RB_ENTRY(chunk_node_s) link_ad;
+/* Tree of extents. */
+typedef struct extent_node_s extent_node_t;
+struct extent_node_s {
+	/* Linkage for the size/address-ordered tree. */
+	RB_ENTRY(extent_node_s) link_szad;
 
-#ifdef MALLOC_DSS
-	/* Linkage for the size/address-ordered chunk tree. */
-	RB_ENTRY(chunk_node_s) link_szad;
-#endif
+	/* Linkage for the address-ordered tree. */
+	RB_ENTRY(extent_node_s) link_ad;
 
-	/*
-	 * Pointer to the chunk that this tree node is responsible for.  In some
-	 * (but certainly not all) cases, this data structure is placed at the
-	 * beginning of the corresponding chunk, so this field may point to this
-	 * node.
-	 */
-	void	*chunk;
+	/* Pointer to the extent that this tree node is responsible for. */
+	void	*addr;
 
-	/* Total chunk size. */
+	/* Total region size. */
 	size_t	size;
 };
-typedef struct chunk_tree_ad_s chunk_tree_ad_t;
-RB_HEAD(chunk_tree_ad_s, chunk_node_s);
-#ifdef MALLOC_DSS
-typedef struct chunk_tree_szad_s chunk_tree_szad_t;
-RB_HEAD(chunk_tree_szad_s, chunk_node_s);
-#endif
+typedef struct extent_tree_szad_s extent_tree_szad_t;
+RB_HEAD(extent_tree_szad_s, extent_node_s);
+typedef struct extent_tree_ad_s extent_tree_ad_t;
+RB_HEAD(extent_tree_ad_s, extent_node_s);
 
 /******************************************************************************/
 /*
@@ -480,37 +487,21 @@ RB_HEAD(chunk_tree_szad_s, chunk_node_s);
 typedef struct arena_s arena_t;
 typedef struct arena_bin_s arena_bin_t;
 
-typedef struct arena_chunk_map_s arena_chunk_map_t;
-struct arena_chunk_map_s {
-	/*
-	 * Number of pages in run.  For a free run that has never been touched,
-	 * this is NPAGES_EMPTY for the central pages, which allows us to avoid
-	 * zero-filling untouched pages for calloc().
-	 */
-#define	NPAGES_EMPTY ((uint32_t)0x0U)
-	uint32_t	npages;
-	/*
-	 * Position within run.  For a free run, this is POS_EMPTY/POS_FREE for
-	 * the first and last pages.  The special values make it possible to
-	 * quickly coalesce free runs.  POS_EMPTY indicates that the run has
-	 * never been touched, which allows us to avoid zero-filling untouched
-	 * pages for calloc().
-	 *
-	 * This is the limiting factor for chunksize; there can be at most 2^31
-	 * pages in a run.
-	 *
-	 * POS_EMPTY is assumed by arena_run_dalloc() to be less than POS_FREE.
-	 */
-#define	POS_EMPTY ((uint32_t)0xfffffffeU)
-#define	POS_FREE ((uint32_t)0xffffffffU)
-	uint32_t	pos;
-};
+/*
+ * Each map element contains several flags, plus page position for runs that
+ * service small allocations.
+ */
+typedef uint8_t arena_chunk_map_t;
+#define	CHUNK_MAP_UNTOUCHED	0x80U
+#define	CHUNK_MAP_DIRTY		0x40U
+#define	CHUNK_MAP_LARGE		0x20U
+#define	CHUNK_MAP_POS_MASK	0x1fU
 
 /* Arena chunk header. */
 typedef struct arena_chunk_s arena_chunk_t;
 struct arena_chunk_s {
 	/* Arena that owns the chunk. */
-	arena_t *arena;
+	arena_t		*arena;
 
 	/* Linkage for the arena's chunk tree. */
 	RB_ENTRY(arena_chunk_s) link;
@@ -519,22 +510,17 @@ struct arena_chunk_s {
 	 * Number of pages in use.  This is maintained in order to make
 	 * detection of empty chunks fast.
 	 */
-	uint32_t pages_used;
+	size_t		pages_used;
 
-	/*
-	 * Every time a free run larger than this value is created/coalesced,
-	 * this value is increased.  The only way that the value decreases is if
-	 * arena_run_alloc() fails to find a free run as large as advertised by
-	 * this value.
-	 */
-	uint32_t max_frun_npages;
+	/* Number of dirty pages. */
+	size_t		ndirty;
 
 	/*
-	 * Every time a free run that starts at an earlier page than this value
-	 * is created/coalesced, this value is decreased.  It is reset in a
-	 * similar fashion to max_frun_npages.
+	 * Tree of extent nodes that are embedded in the arena chunk header
+	 * page(s).  These nodes are used by arena_chunk_node_alloc().
 	 */
-	uint32_t min_frun_ind;
+	extent_tree_ad_t nodes;
+	extent_node_t	*nodes_past;
 
 	/*
 	 * Map of pages within chunk that keeps track of free/large/small.  For
@@ -629,7 +615,8 @@ struct arena_s {
 	/*
 	 * In order to avoid rapid chunk allocation/deallocation when an arena
 	 * oscillates right on the cusp of needing a new chunk, cache the most
-	 * recently freed chunk.  This caching is disabled by opt_hint.
+	 * recently freed chunk.  The spare is left in the arena's chunk tree
+	 * until it is deleted.
 	 *
 	 * There is one spare chunk per arena, rather than one spare total, in
 	 * order to avoid interactions between multiple threads that could make
@@ -637,6 +624,25 @@ struct arena_s {
 	 */
 	arena_chunk_t		*spare;
 
+	/*
+	 * Current count of pages within unused runs that are potentially
+	 * dirty, and for which madvise(... MADV_FREE) has not been called.  By
+	 * tracking this, we can institute a limit on how much dirty unused
+	 * memory is mapped for each arena.
+	 */
+	size_t			ndirty;
+
+	/*
+	 * Trees of this arena's available runs.  Two trees are maintained
+	 * using one set of nodes, since one is needed for first-best-fit run
+	 * allocation, and the other is needed for coalescing.
+	 */
+	extent_tree_szad_t	runs_avail_szad;
+	extent_tree_ad_t	runs_avail_ad;
+
+	/* Tree of this arena's allocated (in-use) runs. */
+	extent_tree_ad_t	runs_alloced_ad;
+
 #ifdef MALLOC_BALANCE
 	/*
 	 * The arena load balancing machinery needs to keep track of how much
@@ -709,8 +715,8 @@ static size_t		quantum_mask; /* (quantum - 1). */
 /* Various chunk-related settings. */
 static size_t		chunksize;
 static size_t		chunksize_mask; /* (chunksize - 1). */
-static unsigned		chunk_npages;
-static unsigned		arena_chunk_header_npages;
+static size_t		chunk_npages;
+static size_t		arena_chunk_header_npages;
 static size_t		arena_maxclass; /* Max size class for arenas. */
 
 /********/
@@ -722,7 +728,7 @@ static size_t		arena_maxclass; /* Max size class for arenas. */
 static malloc_mutex_t	huge_mtx;
 
 /* Tree of chunks that are stand-alone huge allocations. */
-static chunk_tree_ad_t	huge;
+static extent_tree_ad_t	huge;
 
 #ifdef MALLOC_DSS
 /*
@@ -740,11 +746,11 @@ static void		*dss_max;
 /*
  * 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,
+ * address space.  Depending on function, different tree orderings are needed,
  * which is why there are two trees with the same contents.
  */
-static chunk_tree_ad_t	dss_chunks_ad;
-static chunk_tree_szad_t dss_chunks_szad;
+static extent_tree_szad_t dss_chunks_szad;
+static extent_tree_ad_t	dss_chunks_ad;
 #endif
 
 #ifdef MALLOC_STATS
@@ -767,7 +773,7 @@ static size_t		huge_allocated;
 static void		*base_pages;
 static void		*base_next_addr;
 static void		*base_past_addr; /* Addr immediately past base_pages. */
-static chunk_node_t	*base_chunk_nodes; /* LIFO cache of chunk nodes. */
+static extent_node_t	*base_nodes;
 static malloc_mutex_t	base_mtx;
 #ifdef MALLOC_STATS
 static size_t		base_mapped;
@@ -791,7 +797,7 @@ static unsigned		narenas_2pow;
 static unsigned		next_arena;
 #  endif
 #endif
-static pthread_mutex_t arenas_lock; /* Protects arenas initialization. */
+static pthread_mutex_t	arenas_lock; /* Protects arenas initialization. */
 
 #ifndef NO_TLS
 /*
@@ -823,7 +829,7 @@ static bool	opt_junk = false;
 static bool	opt_dss = true;
 static bool	opt_mmap = true;
 #endif
-static bool	opt_hint = false;
+static size_t	opt_dirty_max = DIRTY_MAX_DEFAULT;
 #ifdef MALLOC_LAZY_FREE
 static int	opt_lazy_free_2pow = LAZY_FREE_2POW_DEFAULT;
 #endif
@@ -848,7 +854,10 @@ typedef struct {
 
 #define	UTRACE(a, b, c)							\
 	if (opt_utrace) {						\
-		malloc_utrace_t ut = {a, b, c};				\
+		malloc_utrace_t ut;					\
+		ut.p = (a);						\
+		ut.s = (b);						\
+		ut.r = (c);						\
 		utrace(&ut, sizeof(ut));				\
 	}
 
@@ -865,36 +874,73 @@ static void	wrtmessage(const char *p1, const char *p2, const char *p3,
 static void	malloc_printf(const char *format, ...);
 #endif
 static char	*umax2s(uintmax_t x, char *s);
+#ifdef MALLOC_DSS
+static bool	base_pages_alloc_dss(size_t minsize);
+#endif
+static bool	base_pages_alloc_mmap(size_t minsize);
 static bool	base_pages_alloc(size_t minsize);
 static void	*base_alloc(size_t size);
 static void	*base_calloc(size_t number, size_t size);
-static chunk_node_t *base_chunk_node_alloc(void);
-static void	base_chunk_node_dealloc(chunk_node_t *node);
+static extent_node_t *base_node_alloc(void);
+static void	base_node_dealloc(extent_node_t *node);
 #ifdef MALLOC_STATS
 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);
+#ifdef MALLOC_DSS
+static void	*chunk_alloc_dss(size_t size);
+static void	*chunk_recycle_dss(size_t size, bool zero);
+#endif
+static void	*chunk_alloc_mmap(size_t size);
 static void	*chunk_alloc(size_t size, bool zero);
+#ifdef MALLOC_DSS
+static extent_node_t *chunk_dealloc_dss_record(void *chunk, size_t size);
+static bool	chunk_dealloc_dss(void *chunk, size_t size);
+#endif
+static void	chunk_dealloc_mmap(void *chunk, size_t size);
 static void	chunk_dealloc(void *chunk, size_t size);
 #ifndef NO_TLS
 static arena_t	*choose_arena_hard(void);
 #endif
+static extent_node_t *arena_chunk_node_alloc(arena_chunk_t *chunk);
+static void	arena_chunk_node_dealloc(arena_chunk_t *chunk,
+    extent_node_t *node);
 static void	arena_run_split(arena_t *arena, arena_run_t *run, size_t size,
-    bool zero);
+    bool small, bool zero);
 static arena_chunk_t *arena_chunk_alloc(arena_t *arena);
 static void	arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk);
-static arena_run_t *arena_run_alloc(arena_t *arena, size_t size, bool zero);
-static void	arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size);
+static arena_run_t *arena_run_alloc(arena_t *arena, size_t size, bool small,
+    bool zero);
+static void	arena_purge(arena_t *arena);
+static void	arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty);
+static void	arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk,
+    extent_node_t *nodeB, arena_run_t *run, size_t oldsize, size_t newsize);
+static void	arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk,
+    extent_node_t *nodeA, arena_run_t *run, size_t oldsize, size_t newsize,
+    bool dirty);
 static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin);
 static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin);
 static size_t arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size);
-static void	*arena_malloc(arena_t *arena, size_t size, bool zero);
+#ifdef MALLOC_BALANCE
+static void	arena_lock_balance_hard(arena_t *arena);
+#endif
+static void	*arena_malloc_large(arena_t *arena, size_t size, bool zero);
 static void	*arena_palloc(arena_t *arena, size_t alignment, size_t size,
     size_t alloc_size);
 static size_t	arena_salloc(const void *ptr);
+static void	arena_ralloc_resize_shrink(arena_t *arena, arena_chunk_t *chunk,
+    void *ptr, size_t size, size_t oldsize);
+static bool	arena_ralloc_resize_grow(arena_t *arena, arena_chunk_t *chunk,
+    void *ptr, size_t size, size_t oldsize);
+static bool	arena_ralloc_resize(void *ptr, size_t size, size_t oldsize);
 static void	*arena_ralloc(void *ptr, size_t size, size_t oldsize);
-static void	arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr);
+#ifdef MALLOC_LAZY_FREE
+static void	arena_dalloc_lazy_hard(arena_t *arena, arena_chunk_t *chunk,
+    void *ptr, size_t pageind, arena_chunk_map_t *mapelm);
+#endif
+static void	arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk,
+    void *ptr);
 static bool	arena_new(arena_t *arena);
 static arena_t	*arenas_extend(unsigned ind);
 static void	*huge_malloc(size_t size, bool zero);
@@ -1194,7 +1240,7 @@ umax2s(uintmax_t x, char *s)
 /******************************************************************************/
 
 #ifdef MALLOC_DSS
-static inline bool
+static bool
 base_pages_alloc_dss(size_t minsize)
 {
 
@@ -1218,7 +1264,8 @@ base_pages_alloc_dss(size_t minsize)
 			 */
 			incr = (intptr_t)chunksize
 			    - (intptr_t)CHUNK_ADDR2OFFSET(dss_max);
-			if (incr < minsize)
+			assert(incr >= 0);
+			if ((size_t)incr < minsize)
 				incr += csize;
 
 			dss_prev = sbrk(incr);
@@ -1242,7 +1289,7 @@ base_pages_alloc_dss(size_t minsize)
 }
 #endif
 
-static inline bool
+static bool
 base_pages_alloc_mmap(size_t minsize)
 {
 	size_t csize;
@@ -1291,21 +1338,16 @@ base_alloc(size_t size)
 	csize = CACHELINE_CEILING(size);
 
 	malloc_mutex_lock(&base_mtx);
-
 	/* Make sure there's enough space for the allocation. */
 	if ((uintptr_t)base_next_addr + csize > (uintptr_t)base_past_addr) {
-		if (base_pages_alloc(csize)) {
-			ret = NULL;
-			goto RETURN;
-		}
+		if (base_pages_alloc(csize))
+			return (NULL);
 	}
-
 	/* Allocate. */
 	ret = base_next_addr;
 	base_next_addr = (void *)((uintptr_t)base_next_addr + csize);
-
-RETURN:
 	malloc_mutex_unlock(&base_mtx);
+
 	return (ret);
 }
 
@@ -1320,31 +1362,31 @@ base_calloc(size_t number, size_t size)
 	return (ret);
 }
 
-static chunk_node_t *
-base_chunk_node_alloc(void)
+static extent_node_t *
+base_node_alloc(void)
 {
-	chunk_node_t *ret;
+	extent_node_t *ret;
 
 	malloc_mutex_lock(&base_mtx);
-	if (base_chunk_nodes != NULL) {
-		ret = base_chunk_nodes;
-		base_chunk_nodes = *(chunk_node_t **)ret;
+	if (base_nodes != NULL) {
+		ret = base_nodes;
+		base_nodes = *(extent_node_t **)ret;
 		malloc_mutex_unlock(&base_mtx);
 	} else {
 		malloc_mutex_unlock(&base_mtx);
-		ret = (chunk_node_t *)base_alloc(sizeof(chunk_node_t));
+		ret = (extent_node_t *)base_alloc(sizeof(extent_node_t));
 	}
 
 	return (ret);
 }
 
 static void
-base_chunk_node_dealloc(chunk_node_t *node)
+base_node_dealloc(extent_node_t *node)
 {
 
 	malloc_mutex_lock(&base_mtx);
-	*(chunk_node_t **)node = base_chunk_nodes;
-	base_chunk_nodes = node;
+	*(extent_node_t **)node = base_nodes;
+	base_nodes = node;
 	malloc_mutex_unlock(&base_mtx);
 }
 
@@ -1356,19 +1398,25 @@ stats_print(arena_t *arena)
 {
 	unsigned i, gap_start;
 
-	malloc_printf(
-	    "          allocated/mapped            nmalloc      ndalloc\n");
-	malloc_printf("small: %12llu %-12s %12llu %12llu\n",
-	    arena->stats.allocated_small, "", arena->stats.nmalloc_small,
+	malloc_printf("dirty: %zu page%s dirty, %llu sweep%s,"
+	    " %llu madvise%s, %llu page%s purged\n",
+	    arena->ndirty, arena->ndirty == 1 ? "" : "s",
+	    arena->stats.npurge, arena->stats.npurge == 1 ? "" : "s",
+	    arena->stats.nmadvise, arena->stats.nmadvise == 1 ? "" : "s",
+	    arena->stats.purged, arena->stats.purged == 1 ? "" : "s");
+
+	malloc_printf("            allocated      nmalloc      ndalloc\n");
+	malloc_printf("small:   %12zu %12llu %12llu\n",
+	    arena->stats.allocated_small, arena->stats.nmalloc_small,
 	    arena->stats.ndalloc_small);
-	malloc_printf("large: %12llu %-12s %12llu %12llu\n",
-	    arena->stats.allocated_large, "", arena->stats.nmalloc_large,
+	malloc_printf("large:   %12zu %12llu %12llu\n",
+	    arena->stats.allocated_large, arena->stats.nmalloc_large,
 	    arena->stats.ndalloc_large);
-	malloc_printf("total: %12llu/%-12llu %12llu %12llu\n",
+	malloc_printf("total:   %12zu %12llu %12llu\n",
 	    arena->stats.allocated_small + arena->stats.allocated_large,
-	    arena->stats.mapped,
 	    arena->stats.nmalloc_small + arena->stats.nmalloc_large,
 	    arena->stats.ndalloc_small + arena->stats.ndalloc_large);
+	malloc_printf("mapped:  %12zu\n", arena->stats.mapped);
 
 	malloc_printf("bins:     bin   size regs pgs  requests   newruns"
 	    "    reruns maxruns curruns\n");
@@ -1420,24 +1468,11 @@ stats_print(arena_t *arena)
  */
 /******************************************************************************/
 /*
- * Begin chunk management functions.
+ * Begin extent tree code.
  */
 
 static inline int
-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;
-
-	return ((a_chunk > b_chunk) - (a_chunk < b_chunk));
-}
-
-/* Generate red-black tree code for address-ordered chunks. */
-RB_GENERATE_STATIC(chunk_tree_ad_s, chunk_node_s, link_ad, chunk_ad_comp)
-
-#ifdef MALLOC_DSS
-static inline int
-chunk_szad_comp(chunk_node_t *a, chunk_node_t *b)
+extent_szad_comp(extent_node_t *a, extent_node_t *b)
 {
 	int ret;
 	size_t a_size = a->size;
@@ -1445,18 +1480,38 @@ chunk_szad_comp(chunk_node_t *a, chunk_node_t *b)
 
 	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;
+		uintptr_t a_addr = (uintptr_t)a->addr;
+		uintptr_t b_addr = (uintptr_t)b->addr;
 
-		ret = (a_chunk > b_chunk) - (a_chunk < b_chunk);
+		ret = (a_addr > b_addr) - (a_addr < b_addr);
 	}
 
 	return (ret);
 }
 
-/* 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)
-#endif
+/* Generate red-black tree code for size/address-ordered extents. */
+RB_GENERATE_STATIC(extent_tree_szad_s, extent_node_s, link_szad,
+    extent_szad_comp)
+
+static inline int
+extent_ad_comp(extent_node_t *a, extent_node_t *b)
+{
+	uintptr_t a_addr = (uintptr_t)a->addr;
+	uintptr_t b_addr = (uintptr_t)b->addr;
+
+	return ((a_addr > b_addr) - (a_addr < b_addr));
+}
+
+/* Generate red-black tree code for address-ordered extents. */
+RB_GENERATE_STATIC(extent_tree_ad_s, extent_node_s, link_ad, extent_ad_comp)
+
+/*
+ * End extent tree code.
+ */
+/******************************************************************************/
+/*
+ * Begin chunk management functions.
+ */
 
 static void *
 pages_map(void *addr, size_t size)
@@ -1510,7 +1565,7 @@ pages_unmap(void *addr, size_t size)
 }
 
 #ifdef MALLOC_DSS
-static inline void *
+static void *
 chunk_alloc_dss(size_t size)
 {
 
@@ -1535,7 +1590,7 @@ chunk_alloc_dss(size_t size)
 			 */
 			incr = (intptr_t)size
 			    - (intptr_t)CHUNK_ADDR2OFFSET(dss_max);
-			if (incr == size)
+			if (incr == (intptr_t)size)
 				ret = dss_max;
 			else {
 				ret = (void *)((intptr_t)dss_max + incr);
@@ -1556,24 +1611,23 @@ chunk_alloc_dss(size_t size)
 	return (NULL);
 }
 
-static inline void *
+static void *
 chunk_recycle_dss(size_t size, bool zero)
 {
-	chunk_node_t *node;
-	chunk_node_t key;
+	extent_node_t *node, key;
 
-	key.chunk = NULL;
+	key.addr = NULL;
 	key.size = size;
 	malloc_mutex_lock(&dss_mtx);
-	node = RB_NFIND(chunk_tree_szad_s, &dss_chunks_szad, &key);
-	if (node != NULL && (uintptr_t)node->chunk < (uintptr_t)dss_max) {
-		void *ret = node->chunk;
+	node = RB_NFIND(extent_tree_szad_s, &dss_chunks_szad, &key);
+	if (node != NULL) {
+		void *ret = node->addr;
 
 		/* Remove node from the tree. */
-		RB_REMOVE(chunk_tree_szad_s, &dss_chunks_szad, node);
+		RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad, node);
 		if (node->size == size) {
-			RB_REMOVE(chunk_tree_ad_s, &dss_chunks_ad, node);
-			base_chunk_node_dealloc(node);
+			RB_REMOVE(extent_tree_ad_s, &dss_chunks_ad, node);
+			base_node_dealloc(node);
 		} else {
 			/*
 			 * Insert the remainder of node's address range as a
@@ -1581,9 +1635,9 @@ chunk_recycle_dss(size_t size, bool zero)
 			 * does not change.
 			 */
 			assert(node->size > size);
-			node->chunk = (void *)((uintptr_t)node->chunk + size);
+			node->addr = (void *)((uintptr_t)node->addr + size);
 			node->size -= size;
-			RB_INSERT(chunk_tree_szad_s, &dss_chunks_szad, node);
+			RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
 		}
 		malloc_mutex_unlock(&dss_mtx);
 
@@ -1597,7 +1651,7 @@ chunk_recycle_dss(size_t size, bool zero)
 }
 #endif
 
-static inline void *
+static void *
 chunk_alloc_mmap(size_t size)
 {
 	void *ret;
@@ -1680,7 +1734,6 @@ chunk_alloc(size_t size, bool zero)
 	assert(size != 0);
 	assert((size & chunksize_mask) == 0);
 
-
 #ifdef MALLOC_DSS
 	if (opt_dss) {
 		ret = chunk_recycle_dss(size, zero);
@@ -1718,78 +1771,77 @@ RETURN:
 }
 
 #ifdef MALLOC_DSS
-static inline chunk_node_t *
+static extent_node_t *
 chunk_dealloc_dss_record(void *chunk, size_t size)
 {
-	chunk_node_t *node, *prev;
-	chunk_node_t key;
+	extent_node_t *node, *prev, key;
 
-	key.chunk = (void *)((uintptr_t)chunk + size);
-	node = RB_NFIND(chunk_tree_ad_s, &dss_chunks_ad, &key);
+	key.addr = (void *)((uintptr_t)chunk + size);
+	node = RB_NFIND(extent_tree_ad_s, &dss_chunks_ad, &key);
 	/* Try to coalesce forward. */
-	if (node != NULL && node->chunk == key.chunk) {
+	if (node != NULL && node->addr == key.addr) {
 		/*
 		 * Coalesce chunk with the following address range.  This does
 		 * not change the position within dss_chunks_ad, so only
 		 * remove/insert from/into dss_chunks_szad.
 		 */
-		RB_REMOVE(chunk_tree_szad_s, &dss_chunks_szad, node);
-		node->chunk = chunk;
+		RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad, node);
+		node->addr = chunk;
 		node->size += size;
-		RB_INSERT(chunk_tree_szad_s, &dss_chunks_szad, node);
+		RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
 	} else {
 		/*
-		 * Coalescing forward failed, so insert a new node.
-		 * Drop dss_mtx during node allocation, since it is possible
-		 * that a new base chunk will be allocated.
+		 * Coalescing forward failed, so insert a new node.  Drop
+		 * dss_mtx during node allocation, since it is possible that a
+		 * new base chunk will be allocated.
 		 */
 		malloc_mutex_unlock(&dss_mtx);
-		node = base_chunk_node_alloc();
+		node = base_node_alloc();
 		malloc_mutex_lock(&dss_mtx);
 		if (node == NULL)
 			return (NULL);
-		node->chunk = chunk;
+		node->addr = chunk;
 		node->size = size;
-		RB_INSERT(chunk_tree_ad_s, &dss_chunks_ad, node);
-		RB_INSERT(chunk_tree_szad_s, &dss_chunks_szad, node);
+		RB_INSERT(extent_tree_ad_s, &dss_chunks_ad, node);
+		RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
 	}
 
 	/* Try to coalesce backward. */
-	prev = RB_PREV(chunk_tree_ad_s, &dss_chunks_ad, node);
-	if (prev != NULL && (void *)((uintptr_t)prev->chunk + prev->size) ==
+	prev = RB_PREV(extent_tree_ad_s, &dss_chunks_ad, node);
+	if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) ==
 	    chunk) {
 		/*
 		 * Coalesce chunk with the previous address range.  This does
 		 * not change the position within dss_chunks_ad, so only
 		 * remove/insert node from/into dss_chunks_szad.
 		 */
-		RB_REMOVE(chunk_tree_ad_s, &dss_chunks_ad, prev);
-		RB_REMOVE(chunk_tree_szad_s, &dss_chunks_szad, prev);
+		RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad, prev);
+		RB_REMOVE(extent_tree_ad_s, &dss_chunks_ad, prev);
 
-		RB_REMOVE(chunk_tree_szad_s, &dss_chunks_szad, node);
-		node->chunk = prev->chunk;
+		RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad, node);
+		node->addr = prev->addr;
 		node->size += prev->size;
-		RB_INSERT(chunk_tree_szad_s, &dss_chunks_szad, node);
+		RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
 
-		base_chunk_node_dealloc(prev);
+		base_node_dealloc(prev);
 	}
 
 	return (node);
 }
 
-static inline bool
+static bool
 chunk_dealloc_dss(void *chunk, size_t size)
 {
 
 	malloc_mutex_lock(&dss_mtx);
 	if ((uintptr_t)chunk >= (uintptr_t)dss_base
 	    && (uintptr_t)chunk < (uintptr_t)dss_max) {
-		chunk_node_t *node;
+		extent_node_t *node;
 
 		/* Try to coalesce with other unused chunks. */
 		node = chunk_dealloc_dss_record(chunk, size);
 		if (node != NULL) {
-			chunk = node->chunk;
+			chunk = node->addr;
 			size = node->size;
 		}
 
@@ -1809,11 +1861,11 @@ chunk_dealloc_dss(void *chunk, size_t size)
 			dss_max = (void *)((intptr_t)dss_prev - (intptr_t)size);
 
 			if (node != NULL) {
-				RB_REMOVE(chunk_tree_ad_s, &dss_chunks_ad,
+				RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad,
 				    node);
-				RB_REMOVE(chunk_tree_szad_s, &dss_chunks_szad,
+				RB_REMOVE(extent_tree_ad_s, &dss_chunks_ad,
 				    node);
-				base_chunk_node_dealloc(node);
+				base_node_dealloc(node);
 			}
 			malloc_mutex_unlock(&dss_mtx);
 		} else {
@@ -1829,7 +1881,7 @@ chunk_dealloc_dss(void *chunk, size_t size)
 }
 #endif
 
-static inline void
+static void
 chunk_dealloc_mmap(void *chunk, size_t size)
 {
 
@@ -1884,12 +1936,7 @@ choose_arena(void)
 	 */
 #ifndef NO_TLS
 	if (__isthreaded == false) {
-	    /*
-	     * Avoid the overhead of TLS for single-threaded operation.  If the
-	     * app switches to threaded mode, the initial thread may end up
-	     * being assigned to some other arena, but this one-time switch
-	     * shouldn't cause significant issues.
-	     */
+	    /* Avoid the overhead of TLS for single-threaded operation. */
 	    return (arenas[0]);
 	}
 
@@ -1899,7 +1946,7 @@ choose_arena(void)
 		assert(ret != NULL);
 	}
 #else
-	if (__isthreaded) {
+	if (__isthreaded && narenas > 1) {
 		unsigned long ind;
 
 		/*
@@ -2039,6 +2086,34 @@ arena_run_comp(arena_run_t *a, arena_run_t *b)
 /* Generate red-black tree code for arena runs. */
 RB_GENERATE_STATIC(arena_run_tree_s, arena_run_s, link, arena_run_comp)
 
+static extent_node_t *
+arena_chunk_node_alloc(arena_chunk_t *chunk)
+{
+	extent_node_t *ret;
+
+	ret = RB_MIN(extent_tree_ad_s, &chunk->nodes);
+	if (ret != NULL)
+		RB_REMOVE(extent_tree_ad_s, &chunk->nodes, ret);
+	else {
+		ret = chunk->nodes_past;
+		chunk->nodes_past = (extent_node_t *)
+		    ((uintptr_t)chunk->nodes_past + sizeof(extent_node_t));
+		assert((uintptr_t)ret + sizeof(extent_node_t) <=
+		    (uintptr_t)chunk + (arena_chunk_header_npages <<
+		    pagesize_2pow));
+	}
+
+	return (ret);
+}
+
+static void
+arena_chunk_node_dealloc(arena_chunk_t *chunk, extent_node_t *node)
+{
+
+	node->addr = (void *)node;
+	RB_INSERT(extent_tree_ad_s, &chunk->nodes, node);
+}
+
 static inline void *
 arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin)
 {
@@ -2060,6 +2135,7 @@ arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin)
 		bit = ffs((int)mask) - 1;
 
 		regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
+		assert(regind < bin->nregs);
 		ret = (void *)(((uintptr_t)run) + bin->reg0_offset
 		    + (bin->reg_size * regind));
 
@@ -2077,6 +2153,7 @@ arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin)
 			bit = ffs((int)mask) - 1;
 
 			regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
+			assert(regind < bin->nregs);
 			ret = (void *)(((uintptr_t)run) + bin->reg0_offset
 			    + (bin->reg_size * regind));
 
@@ -2169,7 +2246,7 @@ arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
 			regind = diff >> (8 + log2_table[(size >> 8) - 1]);
 		else {
 			/*
-			 * The page size is too large for us to use the lookup
+			 * The run size is too large for us to use the lookup
 			 * table.  Use real division.
 			 */
 			regind = diff / size;
@@ -2201,76 +2278,70 @@ arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
 }
 
 static void
-arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool zero)
+arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool small,
+    bool zero)
 {
 	arena_chunk_t *chunk;
-	unsigned run_ind, map_offset, total_pages, need_pages, rem_pages;
-	unsigned i;
-	uint32_t pos_beg, pos_end;
+	size_t run_ind, total_pages, need_pages, rem_pages, i;
+	extent_node_t *nodeA, *nodeB, key;
 
+	/* Insert a node into runs_alloced_ad for the first part of the run. */
 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
+	nodeA = arena_chunk_node_alloc(chunk);
+	nodeA->addr = run;
+	nodeA->size = size;
+	RB_INSERT(extent_tree_ad_s, &arena->runs_alloced_ad, nodeA);
+
+	key.addr = run;
+	nodeB = RB_FIND(extent_tree_ad_s, &arena->runs_avail_ad, &key);
+	assert(nodeB != NULL);
+
 	run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
 	    >> pagesize_2pow);
-	total_pages = chunk->map[run_ind].npages;
+	total_pages = nodeB->size >> pagesize_2pow;
 	need_pages = (size >> pagesize_2pow);
 	assert(need_pages > 0);
 	assert(need_pages <= total_pages);
+	assert(need_pages <= CHUNK_MAP_POS_MASK || small == false);
 	rem_pages = total_pages - need_pages;
 
-	/* Split enough pages from the front of run to fit allocation size. */
-	map_offset = run_ind;
-	pos_beg = chunk->map[map_offset].pos;
-	pos_end = chunk->map[map_offset + total_pages - 1].pos;
-	if (zero == false) {
-		for (i = 0; i < need_pages; i++) {
-			chunk->map[map_offset + i].npages = need_pages;
-			chunk->map[map_offset + i].pos = i;
-		}
-	} else {
-		/*
-		 * Handle first page specially, since we need to look for
-		 * POS_EMPTY rather than NPAGES_EMPTY.
-		 */
-		i = 0;
-		if (chunk->map[map_offset + i].pos != POS_EMPTY) {
-			memset((void *)((uintptr_t)chunk + ((map_offset + i) <<
-			    pagesize_2pow)), 0, pagesize);
-		}
-		chunk->map[map_offset + i].npages = need_pages;
-		chunk->map[map_offset + i].pos = i;
-
-		/* Handle central pages. */
-		for (i++; i < need_pages - 1; i++) {
-			if (chunk->map[map_offset + i].npages != NPAGES_EMPTY) {
-				memset((void *)((uintptr_t)chunk + ((map_offset
+	for (i = 0; i < need_pages; i++) {
+		/* Zero if necessary. */
+		if (zero) {
+			if ((chunk->map[run_ind + i] & CHUNK_MAP_UNTOUCHED)
+			    == 0) {
+				memset((void *)((uintptr_t)chunk + ((run_ind
 				    + i) << pagesize_2pow)), 0, pagesize);
 			}
-			chunk->map[map_offset + i].npages = need_pages;
-			chunk->map[map_offset + i].pos = i;
 		}
 
-		/*
-		 * Handle last page specially, since we need to look for
-		 * POS_EMPTY rather than NPAGES_EMPTY.
-		 */
-		if (i < need_pages) {
-			if (chunk->map[map_offset + i].npages != POS_EMPTY) {
-				memset((void *)((uintptr_t)chunk + ((map_offset
-				    + i) << pagesize_2pow)), 0, pagesize);
-			}
-			chunk->map[map_offset + i].npages = need_pages;
-			chunk->map[map_offset + i].pos = i;
+		/* Update dirty page accounting. */
+		if (chunk->map[run_ind + i] & CHUNK_MAP_DIRTY) {
+			chunk->ndirty--;
+			arena->ndirty--;
 		}
+
+		/* Initialize the chunk map. */
+		if (small)
+			chunk->map[run_ind + i] = (uint8_t)i;
+		else
+			chunk->map[run_ind + i] = CHUNK_MAP_LARGE;
 	}
 
 	/* Keep track of trailing unused pages for later use. */
+	RB_REMOVE(extent_tree_szad_s, &arena->runs_avail_szad, nodeB);
 	if (rem_pages > 0) {
-		/* Update map for trailing pages. */
-		map_offset += need_pages;
-		chunk->map[map_offset].npages = rem_pages;
-		chunk->map[map_offset].pos = pos_beg;
-		chunk->map[map_offset + rem_pages - 1].npages = rem_pages;
-		chunk->map[map_offset + rem_pages - 1].pos = pos_end;
+		/*
+		 * Update nodeB in runs_avail_*.  Its position within
+		 * runs_avail_ad does not change.
+		 */
+		nodeB->addr = (void *)((uintptr_t)nodeB->addr + size);
+		nodeB->size -= size;
+		RB_INSERT(extent_tree_szad_s, &arena->runs_avail_szad, nodeB);
+	} else {
+		/* Remove nodeB from runs_avail_*. */
+		RB_REMOVE(extent_tree_ad_s, &arena->runs_avail_ad, nodeB);
+		arena_chunk_node_dealloc(chunk, nodeB);
 	}
 
 	chunk->pages_used += need_pages;
@@ -2280,15 +2351,12 @@ static arena_chunk_t *
 arena_chunk_alloc(arena_t *arena)
 {
 	arena_chunk_t *chunk;
+	extent_node_t *node;
 
 	if (arena->spare != NULL) {
 		chunk = arena->spare;
 		arena->spare = NULL;
-
-		RB_INSERT(arena_chunk_tree_s, &arena->chunks, chunk);
 	} else {
-		unsigned i;
-
 		chunk = (arena_chunk_t *)chunk_alloc(chunksize, true);
 		if (chunk == NULL)
 			return (NULL);
@@ -2305,125 +2373,84 @@ arena_chunk_alloc(arena_t *arena)
 		 * overhead.
 		 */
 		chunk->pages_used = 0;
-
-		chunk->max_frun_npages = chunk_npages -
-		    arena_chunk_header_npages;
-		chunk->min_frun_ind = arena_chunk_header_npages;
+		chunk->ndirty = 0;
 
 		/*
-		 * Initialize enough of the map to support one maximal free run.
+		 * Initialize the map to contain one maximal free untouched
+		 * run.
 		 */
-		i = arena_chunk_header_npages;
-		chunk->map[i].npages = chunk_npages - arena_chunk_header_npages;
-		chunk->map[i].pos = POS_EMPTY;
-
-		/* Mark the free run's central pages as untouched. */
-		for (i++; i < chunk_npages - 1; i++)
-			chunk->map[i].npages = NPAGES_EMPTY;
-
-		/* Take care when (chunk_npages == 2). */
-		if (i < chunk_npages) {
-			chunk->map[i].npages = chunk_npages -
-			    arena_chunk_header_npages;
-			chunk->map[i].pos = POS_EMPTY;
-		}
+		memset(&chunk->map[arena_chunk_header_npages],
+		    CHUNK_MAP_UNTOUCHED, (chunk_npages -
+		    arena_chunk_header_npages));
+
+		/* Initialize the tree of unused extent nodes. */
+		RB_INIT(&chunk->nodes);
+		chunk->nodes_past = (extent_node_t *)QUANTUM_CEILING(
+		    (uintptr_t)&chunk->map[chunk_npages]);
 	}
 
+	/* Insert the run into the runs_avail_* red-black trees. */
+	node = arena_chunk_node_alloc(chunk);
+	node->addr = (void *)((uintptr_t)chunk + (arena_chunk_header_npages <<
+	    pagesize_2pow));
+	node->size = chunksize - (arena_chunk_header_npages << pagesize_2pow);
+	RB_INSERT(extent_tree_szad_s, &arena->runs_avail_szad, node);
+	RB_INSERT(extent_tree_ad_s, &arena->runs_avail_ad, node);
+
 	return (chunk);
 }
 
 static void
 arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk)
 {
+	extent_node_t *node, key;
 
-	/*
-	 * Remove chunk from the chunk tree, regardless of whether this chunk
-	 * will be cached, so that the arena does not use it.
-	 */
-	RB_REMOVE(arena_chunk_tree_s, &chunk->arena->chunks, chunk);
-
-	if (opt_hint == false) {
-		if (arena->spare != NULL) {
-			chunk_dealloc((void *)arena->spare, chunksize);
-#ifdef MALLOC_STATS
-			arena->stats.mapped -= chunksize;
-#endif
-		}
-		arena->spare = chunk;
-	} else {
-		assert(arena->spare == NULL);
-		chunk_dealloc((void *)chunk, chunksize);
+	if (arena->spare != NULL) {
+		RB_REMOVE(arena_chunk_tree_s, &chunk->arena->chunks,
+		    arena->spare);
+		arena->ndirty -= arena->spare->ndirty;
+		chunk_dealloc((void *)arena->spare, chunksize);
 #ifdef MALLOC_STATS
 		arena->stats.mapped -= chunksize;
 #endif
 	}
+
+	/*
+	 * Remove run from the runs trees, regardless of whether this chunk
+	 * will be cached, so that the arena does not use it.  Dirty page
+	 * flushing only uses the chunks tree, so leaving this chunk in that
+	 * tree is sufficient for that purpose.
+	 */
+	key.addr = (void *)((uintptr_t)chunk + (arena_chunk_header_npages <<
+	    pagesize_2pow));
+	node = RB_FIND(extent_tree_ad_s, &arena->runs_avail_ad, &key);
+	assert(node != NULL);
+	RB_REMOVE(extent_tree_szad_s, &arena->runs_avail_szad, node);
+	RB_REMOVE(extent_tree_ad_s, &arena->runs_avail_ad, node);
+	arena_chunk_node_dealloc(chunk, node);
+
+	arena->spare = chunk;
 }
 
 static arena_run_t *
-arena_run_alloc(arena_t *arena, size_t size, bool zero)
+arena_run_alloc(arena_t *arena, size_t size, bool small, bool zero)
 {
 	arena_chunk_t *chunk;
 	arena_run_t *run;
-	unsigned need_npages, limit_pages, compl_need_npages;
+	extent_node_t *node, key;
 
 	assert(size <= (chunksize - (arena_chunk_header_npages <<
 	    pagesize_2pow)));
 	assert((size & pagesize_mask) == 0);
 
-	/*
-	 * Search through arena's chunks in address order for a free run that is
-	 * large enough.  Look for the first fit.
-	 */
-	need_npages = (size >> pagesize_2pow);
-	limit_pages = chunk_npages - arena_chunk_header_npages;
-	compl_need_npages = limit_pages - need_npages;
-	RB_FOREACH(chunk, arena_chunk_tree_s, &arena->chunks) {
-		/*
-		 * Avoid searching this chunk if there are not enough
-		 * contiguous free pages for there to possibly be a large
-		 * enough free run.
-		 */
-		if (chunk->pages_used <= compl_need_npages &&
-		    need_npages <= chunk->max_frun_npages) {
-			arena_chunk_map_t *mapelm;
-			unsigned i;
-			unsigned max_frun_npages = 0;
-			unsigned min_frun_ind = chunk_npages;
-
-			assert(chunk->min_frun_ind >=
-			    arena_chunk_header_npages);
-			for (i = chunk->min_frun_ind; i < chunk_npages;) {
-				mapelm = &chunk->map[i];
-				if (mapelm->pos >= POS_EMPTY) {
-					if (mapelm->npages >= need_npages) {
-						run = (arena_run_t *)
-						    ((uintptr_t)chunk + (i <<
-						    pagesize_2pow));
-						/* Update page map. */
-						arena_run_split(arena, run,
-						    size, zero);
-						return (run);
-					}
-					if (mapelm->npages >
-					    max_frun_npages) {
-						max_frun_npages =
-						    mapelm->npages;
-					}
-					if (i < min_frun_ind) {
-						min_frun_ind = i;
-						if (i < chunk->min_frun_ind)
-							chunk->min_frun_ind = i;
-					}
-				}
-				i += mapelm->npages;
-			}
-			/*
-			 * Search failure.  Reset cached chunk->max_frun_npages.
-			 * chunk->min_frun_ind was already reset above (if
-			 * necessary).
-			 */
-			chunk->max_frun_npages = max_frun_npages;
-		}
+	/* Search the arena's chunks for the lowest best fit. */
+	key.addr = NULL;
+	key.size = size;
+	node = RB_NFIND(extent_tree_szad_s, &arena->runs_avail_szad, &key);
+	if (node != NULL) {
+		run = (arena_run_t *)node->addr;
+		arena_run_split(arena, run, size, small, zero);
+		return (run);
 	}
 
 	/*
@@ -2435,98 +2462,225 @@ arena_run_alloc(arena_t *arena, size_t size, bool zero)
 	run = (arena_run_t *)((uintptr_t)chunk + (arena_chunk_header_npages <<
 	    pagesize_2pow));
 	/* Update page map. */
-	arena_run_split(arena, run, size, zero);
+	arena_run_split(arena, run, size, small, zero);
 	return (run);
 }
 
 static void
-arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size)
+arena_purge(arena_t *arena)
 {
 	arena_chunk_t *chunk;
-	unsigned run_ind, run_pages;
+#ifdef MALLOC_DEBUG
+	size_t ndirty;
 
-	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
+	ndirty = 0;
+	RB_FOREACH(chunk, arena_chunk_tree_s, &arena->chunks) {
+		ndirty += chunk->ndirty;
+	}
+	assert(ndirty == arena->ndirty);
+#endif
+	assert(arena->ndirty > opt_dirty_max);
+
+#ifdef MALLOC_STATS
+	arena->stats.npurge++;
+#endif
+
+	/*
+	 * Iterate downward through chunks until enough dirty memory has been
+	 * purged.
+	 */
+	RB_FOREACH_REVERSE(chunk, arena_chunk_tree_s, &arena->chunks) {
+		if (chunk->ndirty > 0) {
+			size_t i;
+
+			for (i = chunk_npages - 1; i >=
+			    arena_chunk_header_npages; i--) {
+				if (chunk->map[i] & CHUNK_MAP_DIRTY) {
+					size_t npages;
+
+					chunk->map[i] = 0;
+					chunk->ndirty--;
+					arena->ndirty--;
+					/* Find adjacent dirty run(s). */
+					for (npages = 1; i >
+					    arena_chunk_header_npages &&
+					    (chunk->map[i - 1] &
+					    CHUNK_MAP_DIRTY); npages++) {
+						i--;
+						chunk->map[i] = 0;
+						chunk->ndirty--;
+						arena->ndirty--;
+					}
 
+					madvise((void *)((uintptr_t)chunk + (i
+					    << pagesize_2pow)), pagesize *
+					    npages, MADV_FREE);
+#ifdef MALLOC_STATS
+					arena->stats.nmadvise++;
+					arena->stats.purged += npages;
+#endif
+					if (arena->ndirty <= (opt_dirty_max >>
+					    1))
+						return;
+				}
+			}
+		}
+	}
+}
+
+static void
+arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty)
+{
+	arena_chunk_t *chunk;
+	extent_node_t *nodeA, *nodeB, *nodeC, key;
+	size_t size, run_ind, run_pages;
+
+	/* Remove run from runs_alloced_ad. */
+	key.addr = run;
+	nodeB = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad, &key);
+	assert(nodeB != NULL);
+	RB_REMOVE(extent_tree_ad_s, &arena->runs_alloced_ad, nodeB);
+	size = nodeB->size;
+
+	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
 	run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
 	    >> pagesize_2pow);
 	assert(run_ind >= arena_chunk_header_npages);
 	assert(run_ind < (chunksize >> pagesize_2pow));
 	run_pages = (size >> pagesize_2pow);
-	assert(run_pages == chunk->map[run_ind].npages);
 
 	/* Subtract pages from count of pages used in chunk. */
 	chunk->pages_used -= run_pages;
 
-	/* Mark run as deallocated. */
-	assert(chunk->map[run_ind].npages == run_pages);
-	chunk->map[run_ind].pos = POS_FREE;
-	assert(chunk->map[run_ind + run_pages - 1].npages == run_pages);
-	chunk->map[run_ind + run_pages - 1].pos = POS_FREE;
+	if (dirty) {
+		size_t i;
 
-	/*
-	 * Tell the kernel that we don't need the data in this run, but only if
-	 * requested via runtime configuration.
-	 */
-	if (opt_hint)
-		madvise(run, size, MADV_FREE);
+		for (i = 0; i < run_pages; i++) {
+			chunk->map[run_ind + i] = CHUNK_MAP_DIRTY;
+			chunk->ndirty++;
+			arena->ndirty++;
+		}
+	}
+#ifdef MALLOC_DEBUG
+	/* Set map elements to a bogus value in order to aid error detection. */
+	{
+		size_t i;
 
-	/* Try to coalesce with neighboring runs. */
-	if (run_ind > arena_chunk_header_npages &&
-	    chunk->map[run_ind - 1].pos >= POS_EMPTY) {
-		unsigned prev_npages;
+		for (i = 0; i < run_pages; i++) {
+			chunk->map[run_ind + i] |= (CHUNK_MAP_LARGE |
+			    CHUNK_MAP_POS_MASK);
+		}
+	}
+#endif
 
-		/* Coalesce with previous run. */
-		prev_npages = chunk->map[run_ind - 1].npages;
+	/* Try to coalesce forward. */
+	key.addr = (void *)((uintptr_t)run + size);
+	nodeC = RB_NFIND(extent_tree_ad_s, &arena->runs_avail_ad, &key);
+	if (nodeC != NULL && nodeC->addr == key.addr) {
+		/*
+		 * Coalesce forward.  This does not change the position within
+		 * runs_avail_ad, so only remove/insert from/into
+		 * runs_avail_szad.
+		 */
+		RB_REMOVE(extent_tree_szad_s, &arena->runs_avail_szad, nodeC);
+		nodeC->addr = (void *)run;
+		nodeC->size += size;
+		RB_INSERT(extent_tree_szad_s, &arena->runs_avail_szad, nodeC);
+		arena_chunk_node_dealloc(chunk, nodeB);
+		nodeB = nodeC;
+	} else {
 		/*
-		 * The way run allocation currently works (lowest first fit),
-		 * it is impossible for a free run to have empty (untouched)
-		 * pages followed by dirty pages.  If the run allocation policy
-		 * changes, then we will need to account for it here.
+		 * Coalescing forward failed, so insert nodeB into runs_avail_*.
 		 */
-		assert(chunk->map[run_ind - 1].pos != POS_EMPTY);
-#if 0 /* Currently unnecessary. */
-		if (prev_npages > 1 && chunk->map[run_ind - 1].pos == POS_EMPTY)
-			chunk->map[run_ind - 1].npages = NPAGES_EMPTY;
-#endif
-		run_ind -= prev_npages;
-		assert(chunk->map[run_ind].npages == prev_npages);
-		assert(chunk->map[run_ind].pos >= POS_EMPTY);
-		run_pages += prev_npages;
-
-		chunk->map[run_ind].npages = run_pages;
-		assert(chunk->map[run_ind].pos >= POS_EMPTY);
-		chunk->map[run_ind + run_pages - 1].npages = run_pages;
-		assert(chunk->map[run_ind + run_pages - 1].pos >= POS_EMPTY);
+		RB_INSERT(extent_tree_szad_s, &arena->runs_avail_szad, nodeB);
+		RB_INSERT(extent_tree_ad_s, &arena->runs_avail_ad, nodeB);
 	}
 
-	if (run_ind + run_pages < chunk_npages &&
-	    chunk->map[run_ind + run_pages].pos >= POS_EMPTY) {
-		unsigned next_npages;
-
-		/* Coalesce with next run. */
-		next_npages = chunk->map[run_ind + run_pages].npages;
-		if (next_npages > 1 && chunk->map[run_ind + run_pages].pos ==
-		    POS_EMPTY)
-			chunk->map[run_ind + run_pages].npages = NPAGES_EMPTY;
-		run_pages += next_npages;
-		assert(chunk->map[run_ind + run_pages - 1].npages ==
-		    next_npages);
-		assert(chunk->map[run_ind + run_pages - 1].pos >= POS_EMPTY);
-
-		chunk->map[run_ind].npages = run_pages;
-		assert(chunk->map[run_ind].pos >= POS_EMPTY);
-		chunk->map[run_ind + run_pages - 1].npages = run_pages;
-		assert(chunk->map[run_ind + run_pages - 1].pos >= POS_EMPTY);
-	}
+	/* Try to coalesce backward. */
+	nodeA = RB_PREV(extent_tree_ad_s, &arena->runs_avail_ad, nodeB);
+	if (nodeA != NULL && (void *)((uintptr_t)nodeA->addr + nodeA->size) ==
+	    (void *)run) {
+		/*
+		 * Coalesce with previous run.  This does not change nodeB's
+		 * position within runs_avail_ad, so only remove/insert
+		 * from/into runs_avail_szad.
+		 */
+		RB_REMOVE(extent_tree_szad_s, &arena->runs_avail_szad, nodeA);
+		RB_REMOVE(extent_tree_ad_s, &arena->runs_avail_ad, nodeA);
 
-	if (chunk->map[run_ind].npages > chunk->max_frun_npages)
-		chunk->max_frun_npages = chunk->map[run_ind].npages;
-	if (run_ind < chunk->min_frun_ind)
-		chunk->min_frun_ind = run_ind;
+		RB_REMOVE(extent_tree_szad_s, &arena->runs_avail_szad, nodeB);
+		nodeB->addr = nodeA->addr;
+		nodeB->size += nodeA->size;
+		RB_INSERT(extent_tree_szad_s, &arena->runs_avail_szad, nodeB);
+
+		arena_chunk_node_dealloc(chunk, nodeA);
+	}
 
 	/* Deallocate chunk if it is now completely unused. */
 	if (chunk->pages_used == 0)
 		arena_chunk_dealloc(arena, chunk);
+
+	/* Enforce opt_dirty_max. */
+	if (arena->ndirty > opt_dirty_max)
+		arena_purge(arena);
+}
+
+static void
+arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, extent_node_t *nodeB,
+    arena_run_t *run, size_t oldsize, size_t newsize)
+{
+	extent_node_t *nodeA;
+
+	assert(nodeB->addr == run);
+	assert(nodeB->size == oldsize);
+	assert(oldsize > newsize);
+
+	/*
+	 * Update the run's node in runs_alloced_ad.  Its position does not
+	 * change.
+	 */
+	nodeB->addr = (void *)((uintptr_t)run + (oldsize - newsize));
+	nodeB->size = newsize;
+
+	/*
+	 * Insert a node into runs_alloced_ad so that arena_run_dalloc() can
+	 * treat the leading run as separately allocated.
+	 */
+	nodeA = arena_chunk_node_alloc(chunk);
+	nodeA->addr = (void *)run;
+	nodeA->size = oldsize - newsize;
+	RB_INSERT(extent_tree_ad_s, &arena->runs_alloced_ad, nodeA);
+
+	arena_run_dalloc(arena, (arena_run_t *)run, false);
+}
+
+static void
+arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, extent_node_t *nodeA,
+    arena_run_t *run, size_t oldsize, size_t newsize, bool dirty)
+{
+	extent_node_t *nodeB;
+
+	assert(nodeA->addr == run);
+	assert(nodeA->size == oldsize);
+	assert(oldsize > newsize);
+
+	/*
+	 * Update the run's node in runs_alloced_ad.  Its position does not
+	 * change.
+	 */
+	nodeA->size = newsize;
+
+	/*
+	 * Insert a node into runs_alloced_ad so that arena_run_dalloc() can
+	 * treat the trailing run as separately allocated.
+	 */
+	nodeB = arena_chunk_node_alloc(chunk);
+	nodeB->addr = (void *)((uintptr_t)run + newsize);
+	nodeB->size = oldsize - newsize;
+	RB_INSERT(extent_tree_ad_s, &arena->runs_alloced_ad, nodeB);
+
+	arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)run + newsize),
+	    dirty);
 }
 
 static arena_run_t *
@@ -2547,7 +2701,7 @@ arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
 	/* No existing runs have any space available. */
 
 	/* Allocate a new run. */
-	run = arena_run_alloc(arena, bin->run_size, false);
+	run = arena_run_alloc(arena, bin->run_size, true, false);
 	if (run == NULL)
 		return (NULL);
 
@@ -2708,149 +2862,147 @@ arena_lock_balance(arena_t *arena)
 		arena->contention = (((uint64_t)arena->contention
 		    * (uint64_t)((1U << BALANCE_ALPHA_INV_2POW)-1))
 		    + (uint64_t)contention) >> BALANCE_ALPHA_INV_2POW;
-		if (arena->contention >= opt_balance_threshold) {
-			uint32_t ind;
+		if (arena->contention >= opt_balance_threshold)
+			arena_lock_balance_hard(arena);
+	}
+}
 
-			arena->contention = 0;
+static void
+arena_lock_balance_hard(arena_t *arena)
+{
+	uint32_t ind;
+
+	arena->contention = 0;
 #ifdef MALLOC_STATS
-			arena->stats.nbalance++;
+	arena->stats.nbalance++;
 #endif
-			ind = PRN(balance, narenas_2pow);
-			if (arenas[ind] != NULL)
-				arenas_map = arenas[ind];
-			else {
-				malloc_spin_lock(&arenas_lock);
-				if (arenas[ind] != NULL)
-					arenas_map = arenas[ind];
-				else
-					arenas_map = arenas_extend(ind);
-				malloc_spin_unlock(&arenas_lock);
-			}
-		}
+	ind = PRN(balance, narenas_2pow);
+	if (arenas[ind] != NULL)
+		arenas_map = arenas[ind];
+	else {
+		malloc_spin_lock(&arenas_lock);
+		if (arenas[ind] != NULL)
+			arenas_map = arenas[ind];
+		else
+			arenas_map = arenas_extend(ind);
+		malloc_spin_unlock(&arenas_lock);
 	}
 }
 #endif
 
-static void *
-arena_malloc(arena_t *arena, size_t size, bool zero)
+static inline void *
+arena_malloc_small(arena_t *arena, size_t size, bool zero)
 {
 	void *ret;
+	arena_bin_t *bin;
+	arena_run_t *run;
 
-	assert(arena != NULL);
-	assert(arena->magic == ARENA_MAGIC);
-	assert(size != 0);
-	assert(QUANTUM_CEILING(size) <= arena_maxclass);
-
-	if (size <= bin_maxclass) {
-		arena_bin_t *bin;
-		arena_run_t *run;
-
-		/* Small allocation. */
-
-		if (size < small_min) {
-			/* Tiny. */
-			size = pow2_ceil(size);
-			bin = &arena->bins[ffs((int)(size >> (TINY_MIN_2POW +
-			    1)))];
+	if (size < small_min) {
+		/* Tiny. */
+		size = pow2_ceil(size);
+		bin = &arena->bins[ffs((int)(size >> (TINY_MIN_2POW +
+		    1)))];
 #if (!defined(NDEBUG) || defined(MALLOC_STATS))
-			/*
-			 * Bin calculation is always correct, but we may need
-			 * to fix size for the purposes of assertions and/or
-			 * stats accuracy.
-			 */
-			if (size < (1U << TINY_MIN_2POW))
-				size = (1U << TINY_MIN_2POW);
-#endif
-		} else if (size <= small_max) {
-			/* Quantum-spaced. */
-			size = QUANTUM_CEILING(size);
-			bin = &arena->bins[ntbins + (size >> opt_quantum_2pow)
-			    - 1];
-		} else {
-			/* Sub-page. */
-			size = pow2_ceil(size);
-			bin = &arena->bins[ntbins + nqbins
-			    + (ffs((int)(size >> opt_small_max_2pow)) - 2)];
-		}
-		assert(size == bin->reg_size);
+		/*
+		 * Bin calculation is always correct, but we may need
+		 * to fix size for the purposes of assertions and/or
+		 * stats accuracy.
+		 */
+		if (size < (1U << TINY_MIN_2POW))
+			size = (1U << TINY_MIN_2POW);
+#endif
+	} else if (size <= small_max) {
+		/* Quantum-spaced. */
+		size = QUANTUM_CEILING(size);
+		bin = &arena->bins[ntbins + (size >> opt_quantum_2pow)
+		    - 1];
+	} else {
+		/* Sub-page. */
+		size = pow2_ceil(size);
+		bin = &arena->bins[ntbins + nqbins
+		    + (ffs((int)(size >> opt_small_max_2pow)) - 2)];
+	}
+	assert(size == bin->reg_size);
 
 #ifdef MALLOC_BALANCE
-		arena_lock_balance(arena);
+	arena_lock_balance(arena);
 #else
-		malloc_spin_lock(&arena->lock);
+	malloc_spin_lock(&arena->lock);
 #endif
-		if ((run = bin->runcur) != NULL && run->nfree > 0)
-			ret = arena_bin_malloc_easy(arena, bin, run);
-		else
-			ret = arena_bin_malloc_hard(arena, bin);
+	if ((run = bin->runcur) != NULL && run->nfree > 0)
+		ret = arena_bin_malloc_easy(arena, bin, run);
+	else
+		ret = arena_bin_malloc_hard(arena, bin);
 
-		if (ret == NULL) {
-			malloc_spin_unlock(&arena->lock);
-			return (NULL);
-		}
+	if (ret == NULL) {
+		malloc_spin_unlock(&arena->lock);
+		return (NULL);
+	}
 
 #ifdef MALLOC_STATS
-		bin->stats.nrequests++;
-		arena->stats.nmalloc_small++;
-		arena->stats.allocated_small += size;
+	bin->stats.nrequests++;
+	arena->stats.nmalloc_small++;
+	arena->stats.allocated_small += size;
 #endif
-		malloc_spin_unlock(&arena->lock);
+	malloc_spin_unlock(&arena->lock);
 
-		if (zero == false) {
-			if (opt_junk)
-				memset(ret, 0xa5, size);
-			else if (opt_zero)
-				memset(ret, 0, size);
-		} else
+	if (zero == false) {
+		if (opt_junk)
+			memset(ret, 0xa5, size);
+		else if (opt_zero)
 			memset(ret, 0, size);
-	} else {
-		/* Large allocation. */
-		size = PAGE_CEILING(size);
+	} else
+		memset(ret, 0, size);
+
+	return (ret);
+}
+
+static void *
+arena_malloc_large(arena_t *arena, size_t size, bool zero)
+{
+	void *ret;
+
+	/* Large allocation. */
+	size = PAGE_CEILING(size);
 #ifdef MALLOC_BALANCE
-		arena_lock_balance(arena);
+	arena_lock_balance(arena);
 #else
-		malloc_spin_lock(&arena->lock);
+	malloc_spin_lock(&arena->lock);
 #endif
-		ret = (void *)arena_run_alloc(arena, size, zero);
-		if (ret == NULL) {
-			malloc_spin_unlock(&arena->lock);
-			return (NULL);
-		}
+	ret = (void *)arena_run_alloc(arena, size, false, zero);
+	if (ret == NULL) {
+		malloc_spin_unlock(&arena->lock);
+		return (NULL);
+	}
 #ifdef MALLOC_STATS
-		arena->stats.nmalloc_large++;
-		arena->stats.allocated_large += size;
+	arena->stats.nmalloc_large++;
+	arena->stats.allocated_large += size;
 #endif
-		malloc_spin_unlock(&arena->lock);
+	malloc_spin_unlock(&arena->lock);
 
-		if (zero == false) {
-			if (opt_junk)
-				memset(ret, 0xa5, size);
-			else if (opt_zero)
-				memset(ret, 0, size);
-		}
+	if (zero == false) {
+		if (opt_junk)
+			memset(ret, 0xa5, size);
+		else if (opt_zero)
+			memset(ret, 0, size);
 	}
 
 	return (ret);
 }
 
-static inline void
-arena_palloc_trim(arena_t *arena, arena_chunk_t *chunk, unsigned pageind,
-    unsigned npages)
+static inline void *
+arena_malloc(arena_t *arena, size_t size, bool zero)
 {
-	unsigned i;
 
-	assert(npages > 0);
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+	assert(size != 0);
+	assert(QUANTUM_CEILING(size) <= arena_maxclass);
 
-	/*
-	 * Modifiy the map such that arena_run_dalloc() sees the run as
-	 * separately allocated.
-	 */
-	for (i = 0; i < npages; i++) {
-		chunk->map[pageind + i].npages = npages;
-		chunk->map[pageind + i].pos = i;
-	}
-	arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)chunk + (pageind <<
-	    pagesize_2pow)), npages << pagesize_2pow);
+	if (size <= bin_maxclass) {
+		return (arena_malloc_small(arena, size, zero));
+	} else
+		return (arena_malloc_large(arena, size, zero));
 }
 
 /* Only handles large allocations that require more than page alignment. */
@@ -2860,19 +3012,17 @@ arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size)
 	void *ret;
 	size_t offset;
 	arena_chunk_t *chunk;
-	unsigned pageind, i, npages;
+	extent_node_t *node, key;
 
 	assert((size & pagesize_mask) == 0);
 	assert((alignment & pagesize_mask) == 0);
 
-	npages = size >> pagesize_2pow;
-
 #ifdef MALLOC_BALANCE
 	arena_lock_balance(arena);
 #else
 	malloc_spin_lock(&arena->lock);
 #endif
-	ret = (void *)arena_run_alloc(arena, alloc_size, false);
+	ret = (void *)arena_run_alloc(arena, alloc_size, false, false);
 	if (ret == NULL) {
 		malloc_spin_unlock(&arena->lock);
 		return (NULL);
@@ -2884,42 +3034,40 @@ arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size)
 	assert((offset & pagesize_mask) == 0);
 	assert(offset < alloc_size);
 	if (offset == 0) {
-		pageind = (((uintptr_t)ret - (uintptr_t)chunk) >>
-		    pagesize_2pow);
-
-		/* Update the map for the run to be kept. */
-		for (i = 0; i < npages; i++) {
-			chunk->map[pageind + i].npages = npages;
-			assert(chunk->map[pageind + i].pos == i);
-		}
+		/*
+		 * Update the run's node in runs_alloced_ad.  Its position
+		 * does not change.
+		 */
+		key.addr = ret;
+		node = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad, &key);
+		assert(node != NULL);
 
-		/* Trim trailing space. */
-		arena_palloc_trim(arena, chunk, pageind + npages,
-		    (alloc_size - size) >> pagesize_2pow);
+		arena_run_trim_tail(arena, chunk, node, ret, alloc_size, size,
+		    false);
 	} else {
 		size_t leadsize, trailsize;
 
-		leadsize = alignment - offset;
-		ret = (void *)((uintptr_t)ret + leadsize);
-		pageind = (((uintptr_t)ret - (uintptr_t)chunk) >>
-		    pagesize_2pow);
+		/*
+		 * Update the run's node in runs_alloced_ad.  Its position
+		 * does not change.
+		 */
+		key.addr = ret;
+		node = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad, &key);
+		assert(node != NULL);
 
-		/* Update the map for the run to be kept. */
-		for (i = 0; i < npages; i++) {
-			chunk->map[pageind + i].npages = npages;
-			chunk->map[pageind + i].pos = i;
+		leadsize = alignment - offset;
+		if (leadsize > 0) {
+			arena_run_trim_head(arena, chunk, node, ret, alloc_size,
+			    alloc_size - leadsize);
+			ret = (void *)((uintptr_t)ret + leadsize);
 		}
 
-		/* Trim leading space. */
-		arena_palloc_trim(arena, chunk, pageind - (leadsize >>
-		    pagesize_2pow), leadsize >> pagesize_2pow);
-
 		trailsize = alloc_size - leadsize - size;
 		if (trailsize != 0) {
 			/* Trim trailing space. */
 			assert(trailsize < alloc_size);
-			arena_palloc_trim(arena, chunk, pageind + npages,
-			    trailsize >> pagesize_2pow);
+			arena_run_trim_tail(arena, chunk, node, ret, size +
+			    trailsize, size, false);
 		}
 	}
 
@@ -2942,64 +3090,185 @@ arena_salloc(const void *ptr)
 {
 	size_t ret;
 	arena_chunk_t *chunk;
-	arena_chunk_map_t *mapelm;
-	unsigned pageind;
+	arena_chunk_map_t mapelm;
+	size_t pageind;
 
 	assert(ptr != NULL);
 	assert(CHUNK_ADDR2BASE(ptr) != ptr);
 
-	/*
-	 * No arena data structures that we query here can change in a way that
-	 * affects this function, so we don't need to lock.
-	 */
 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
 	pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
-	mapelm = &chunk->map[pageind];
-	if (mapelm->pos != 0 || ptr != (void *)(((uintptr_t)chunk) + (pageind <<
-	    pagesize_2pow))) {
+	mapelm = chunk->map[pageind];
+	if (mapelm != CHUNK_MAP_LARGE) {
 		arena_run_t *run;
 
-		pageind -= mapelm->pos;
-
+		/* Small allocation size is in the run header. */
+		assert(mapelm <= CHUNK_MAP_POS_MASK);
+		pageind -= mapelm;
 		run = (arena_run_t *)((uintptr_t)chunk + (pageind <<
 		    pagesize_2pow));
 		assert(run->magic == ARENA_RUN_MAGIC);
 		ret = run->bin->reg_size;
-	} else
-		ret = mapelm->npages << pagesize_2pow;
+	} else {
+		arena_t *arena = chunk->arena;
+		extent_node_t *node, key;
+
+		/* Large allocation size is in the extent tree. */
+		assert((mapelm & CHUNK_MAP_POS_MASK) == 0);
+		arena = chunk->arena;
+		malloc_spin_lock(&arena->lock);
+		key.addr = (void *)ptr;
+		node = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad, &key);
+		assert(node != NULL);
+		ret = node->size;
+		malloc_spin_unlock(&arena->lock);
+	}
 
 	return (ret);
 }
 
+static void
+arena_ralloc_resize_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr,
+    size_t size, size_t oldsize)
+{
+	extent_node_t *node, key;
+
+	assert(size < oldsize);
+
+	/*
+	 * Shrink the run, and make trailing pages available for other
+	 * allocations.
+	 */
+	key.addr = (void *)((uintptr_t)ptr);
+#ifdef MALLOC_BALANCE
+	arena_lock_balance(arena);
+#else
+	malloc_spin_lock(&arena->lock);
+#endif
+	node = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad, &key);
+	assert(node != NULL);
+	arena_run_trim_tail(arena, chunk, node, (arena_run_t *)ptr, oldsize,
+	    size, true);
+#ifdef MALLOC_STATS
+	arena->stats.allocated_large -= oldsize - size;
+#endif
+	malloc_spin_unlock(&arena->lock);
+}
+
+static bool
+arena_ralloc_resize_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr,
+    size_t size, size_t oldsize)
+{
+	extent_node_t *nodeC, key;
+
+	/* Try to extend the run. */
+	assert(size > oldsize);
+	key.addr = (void *)((uintptr_t)ptr + oldsize);
+#ifdef MALLOC_BALANCE
+	arena_lock_balance(arena);
+#else
+	malloc_spin_lock(&arena->lock);
+#endif
+	nodeC = RB_FIND(extent_tree_ad_s, &arena->runs_avail_ad, &key);
+	if (nodeC != NULL && oldsize + nodeC->size >= size) {
+		extent_node_t *nodeA, *nodeB;
+
+		/*
+		 * The next run is available and sufficiently large.  Split the
+		 * following run, then merge the first part with the existing
+		 * allocation.  This results in a bit more tree manipulation
+		 * than absolutely necessary, but it substantially simplifies
+		 * the code.
+		 */
+		arena_run_split(arena, (arena_run_t *)nodeC->addr, size -
+		    oldsize, false, false);
+
+		key.addr = ptr;
+		nodeA = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad,
+		    &key);
+		assert(nodeA != NULL);
+
+		key.addr = (void *)((uintptr_t)ptr + oldsize);
+		nodeB = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad,
+		    &key);
+		assert(nodeB != NULL);
+
+		nodeA->size += nodeB->size;
+
+		RB_REMOVE(extent_tree_ad_s, &arena->runs_alloced_ad, nodeB);
+		arena_chunk_node_dealloc(chunk, nodeB);
+
+#ifdef MALLOC_STATS
+		arena->stats.allocated_large += size - oldsize;
+#endif
+		malloc_spin_unlock(&arena->lock);
+		return (false);
+	}
+	malloc_spin_unlock(&arena->lock);
+
+	return (true);
+}
+
+/*
+ * Try to resize a large allocation, in order to avoid copying.  This will
+ * always fail if growing an object, and the following run is already in use.
+ */
+static bool
+arena_ralloc_resize(void *ptr, size_t size, size_t oldsize)
+{
+	arena_chunk_t *chunk;
+	arena_t *arena;
+
+	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
+	arena = chunk->arena;
+	assert(arena->magic == ARENA_MAGIC);
+
+	if (size < oldsize) {
+		arena_ralloc_resize_shrink(arena, chunk, ptr, size, oldsize);
+		return (false);
+	} else {
+		return (arena_ralloc_resize_grow(arena, chunk, ptr, size,
+		    oldsize));
+	}
+}
+
 static void *
 arena_ralloc(void *ptr, size_t size, size_t oldsize)
 {
 	void *ret;
 
-	/* Avoid moving the allocation if the size class would not change. */
+	/* Try to avoid moving the allocation. */
 	if (size < small_min) {
 		if (oldsize < small_min &&
 		    ffs((int)(pow2_ceil(size) >> (TINY_MIN_2POW + 1)))
 		    == ffs((int)(pow2_ceil(oldsize) >> (TINY_MIN_2POW + 1))))
-			goto IN_PLACE;
+			goto IN_PLACE; /* Same size class. */
 	} else if (size <= small_max) {
 		if (oldsize >= small_min && oldsize <= small_max &&
 		    (QUANTUM_CEILING(size) >> opt_quantum_2pow)
 		    == (QUANTUM_CEILING(oldsize) >> opt_quantum_2pow))
-			goto IN_PLACE;
-	} else {
-		/*
-		 * We make no attempt to resize runs here, though it would be
-		 * possible to do so.
-		 */
-		if (oldsize > small_max && PAGE_CEILING(size) == oldsize)
+			goto IN_PLACE; /* Same size class. */
+	} else if (size <= bin_maxclass) {
+		if (oldsize > small_max && oldsize <= bin_maxclass &&
+		    pow2_ceil(size) == pow2_ceil(oldsize))
+			goto IN_PLACE; /* Same size class. */
+	} else if (oldsize > bin_maxclass && oldsize <= arena_maxclass) {
+		size_t psize;
+
+		assert(size > bin_maxclass);
+		psize = PAGE_CEILING(size);
+
+		if (psize == oldsize)
+			goto IN_PLACE; /* Same size class. */
+
+		if (arena_ralloc_resize(ptr, psize, oldsize) == false)
 			goto IN_PLACE;
 	}
 
 	/*
 	 * If we get here, then size and oldsize are different enough that we
-	 * need to use a different size class.  In that case, fall back to
-	 * allocating new space and copying.
+	 * need to move the object.  In that case, fall back to allocating new
+	 * space and copying.
 	 */
 	ret = arena_malloc(choose_arena(), size, false);
 	if (ret == NULL)
@@ -3022,13 +3291,14 @@ IN_PLACE:
 
 static inline void
 arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
-    unsigned pageind, arena_chunk_map_t *mapelm)
+    size_t pageind, arena_chunk_map_t mapelm)
 {
 	arena_run_t *run;
 	arena_bin_t *bin;
 	size_t size;
 
-	pageind -= mapelm->pos;
+	assert(mapelm <= CHUNK_MAP_POS_MASK);
+	pageind -= mapelm;
 
 	run = (arena_run_t *)((uintptr_t)chunk + (pageind << pagesize_2pow));
 	assert(run->magic == ARENA_RUN_MAGIC);
@@ -3056,7 +3326,7 @@ arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 #ifdef MALLOC_DEBUG
 		run->magic = 0;
 #endif
-		arena_run_dalloc(arena, run, bin->run_size);
+		arena_run_dalloc(arena, run, true);
 #ifdef MALLOC_STATS
 		bin->stats.curruns--;
 #endif
@@ -3087,14 +3357,14 @@ arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 #ifdef MALLOC_LAZY_FREE
 static inline void
 arena_dalloc_lazy(arena_t *arena, arena_chunk_t *chunk, void *ptr,
-    unsigned pageind, arena_chunk_map_t *mapelm)
+    size_t pageind, arena_chunk_map_t *mapelm)
 {
 	void **free_cache = arena->free_cache;
 	unsigned i, slot;
 
-	if (!__isthreaded || opt_lazy_free_2pow < 0) {
+	if (__isthreaded == false || opt_lazy_free_2pow < 0) {
 		malloc_spin_lock(&arena->lock);
-		arena_dalloc_small(arena, chunk, ptr, pageind, mapelm);
+		arena_dalloc_small(arena, chunk, ptr, pageind, *mapelm);
 		malloc_spin_unlock(&arena->lock);
 		return;
 	}
@@ -3107,8 +3377,18 @@ arena_dalloc_lazy(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 		}
 	}
 
+	arena_dalloc_lazy_hard(arena, chunk, ptr, pageind, mapelm);
+}
+
+static void
+arena_dalloc_lazy_hard(arena_t *arena, arena_chunk_t *chunk, void *ptr,
+    size_t pageind, arena_chunk_map_t *mapelm)
+{
+	void **free_cache = arena->free_cache;
+	unsigned i, slot;
+
 	malloc_spin_lock(&arena->lock);
-	arena_dalloc_small(arena, chunk, ptr, pageind, mapelm);
+	arena_dalloc_small(arena, chunk, ptr, pageind, *mapelm);
 
 	/*
 	 * Check whether another thread already cleared the cache.  It is
@@ -3134,7 +3414,7 @@ arena_dalloc_lazy(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 		pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >>
 		    pagesize_2pow);
 		mapelm = &chunk->map[pageind];
-		arena_dalloc_small(arena, chunk, ptr, pageind, mapelm);
+		arena_dalloc_small(arena, chunk, ptr, pageind, *mapelm);
 
 		/* Sweep remainder of slots. */
 		lazy_free_mask = (1U << opt_lazy_free_2pow) - 1;
@@ -3149,7 +3429,7 @@ arena_dalloc_lazy(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 				    >> pagesize_2pow);
 				mapelm = &chunk->map[pageind];
 				arena_dalloc_small(arena, chunk, ptr, pageind,
-				    mapelm);
+				    *mapelm);
 			}
 		}
 	}
@@ -3159,9 +3439,43 @@ arena_dalloc_lazy(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 #endif
 
 static void
+arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr)
+{
+	/* Large allocation. */
+	malloc_spin_lock(&arena->lock);
+
+#ifndef MALLOC_STATS
+	if (opt_junk)
+#endif
+	{
+		extent_node_t *node, key;
+		size_t size;
+
+		key.addr = ptr;
+		node = RB_FIND(extent_tree_ad_s,
+		    &arena->runs_alloced_ad, &key);
+		assert(node != NULL);
+		size = node->size;
+#ifdef MALLOC_STATS
+		if (opt_junk)
+#endif
+			memset(ptr, 0x5a, size);
+#ifdef MALLOC_STATS
+		arena->stats.allocated_large -= size;
+#endif
+	}
+#ifdef MALLOC_STATS
+	arena->stats.ndalloc_large++;
+#endif
+
+	arena_run_dalloc(arena, (arena_run_t *)ptr, true);
+	malloc_spin_unlock(&arena->lock);
+}
+
+static inline void
 arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
 {
-	unsigned pageind;
+	size_t pageind;
 	arena_chunk_map_t *mapelm;
 
 	assert(arena != NULL);
@@ -3172,34 +3486,19 @@ arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
 
 	pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
 	mapelm = &chunk->map[pageind];
-	if (mapelm->pos != 0 || ptr != (void *)(((uintptr_t)chunk) + (pageind <<
-	    pagesize_2pow))) {
+	if (*mapelm != CHUNK_MAP_LARGE) {
 		/* Small allocation. */
+		assert(*mapelm <= CHUNK_MAP_POS_MASK);
 #ifdef MALLOC_LAZY_FREE
 		arena_dalloc_lazy(arena, chunk, ptr, pageind, mapelm);
 #else
 		malloc_spin_lock(&arena->lock);
-		arena_dalloc_small(arena, chunk, ptr, pageind, mapelm);
+		arena_dalloc_small(arena, chunk, ptr, pageind, *mapelm);
 		malloc_spin_unlock(&arena->lock);
 #endif
 	} else {
-		size_t size;
-
-		/* Large allocation. */
-
-		size = mapelm->npages << pagesize_2pow;
-		assert((((uintptr_t)ptr) & pagesize_mask) == 0);
-
-		if (opt_junk)
-			memset(ptr, 0x5a, size);
-
-		malloc_spin_lock(&arena->lock);
-		arena_run_dalloc(arena, (arena_run_t *)ptr, size);
-#ifdef MALLOC_STATS
-		arena->stats.allocated_large -= size;
-		arena->stats.ndalloc_large++;
-#endif
-		malloc_spin_unlock(&arena->lock);
+		assert((*mapelm & CHUNK_MAP_POS_MASK) == 0);
+		arena_dalloc_large(arena, chunk, ptr);
 	}
 }
 
@@ -3221,6 +3520,12 @@ arena_new(arena_t *arena)
 	RB_INIT(&arena->chunks);
 	arena->spare = NULL;
 
+	arena->ndirty = 0;
+
+	RB_INIT(&arena->runs_avail_szad);
+	RB_INIT(&arena->runs_avail_ad);
+	RB_INIT(&arena->runs_alloced_ad);
+
 #ifdef MALLOC_BALANCE
 	arena->contention = 0;
 #endif
@@ -3334,7 +3639,7 @@ huge_malloc(size_t size, bool zero)
 {
 	void *ret;
 	size_t csize;
-	chunk_node_t *node;
+	extent_node_t *node;
 
 	/* Allocate one or more contiguous chunks for this request. */
 
@@ -3344,23 +3649,23 @@ huge_malloc(size_t size, bool zero)
 		return (NULL);
 	}
 
-	/* Allocate a chunk node with which to track the chunk. */
-	node = base_chunk_node_alloc();
+	/* Allocate an extent node with which to track the chunk. */
+	node = base_node_alloc();
 	if (node == NULL)
 		return (NULL);
 
 	ret = chunk_alloc(csize, zero);
 	if (ret == NULL) {
-		base_chunk_node_dealloc(node);
+		base_node_dealloc(node);
 		return (NULL);
 	}
 
 	/* Insert node into huge. */
-	node->chunk = ret;
+	node->addr = ret;
 	node->size = csize;
 
 	malloc_mutex_lock(&huge_mtx);
-	RB_INSERT(chunk_tree_ad_s, &huge, node);
+	RB_INSERT(extent_tree_ad_s, &huge, node);
 #ifdef MALLOC_STATS
 	huge_nmalloc++;
 	huge_allocated += csize;
@@ -3383,7 +3688,7 @@ huge_palloc(size_t alignment, size_t size)
 {
 	void *ret;
 	size_t alloc_size, chunk_size, offset;
-	chunk_node_t *node;
+	extent_node_t *node;
 
 	/*
 	 * This allocation requires alignment that is even larger than chunk
@@ -3402,14 +3707,14 @@ huge_palloc(size_t alignment, size_t size)
 	else
 		alloc_size = (alignment << 1) - chunksize;
 
-	/* Allocate a chunk node with which to track the chunk. */
-	node = base_chunk_node_alloc();
+	/* Allocate an extent node with which to track the chunk. */
+	node = base_node_alloc();
 	if (node == NULL)
 		return (NULL);
 
 	ret = chunk_alloc(alloc_size, false);
 	if (ret == NULL) {
-		base_chunk_node_dealloc(node);
+		base_node_dealloc(node);
 		return (NULL);
 	}
 
@@ -3438,11 +3743,11 @@ huge_palloc(size_t alignment, size_t size)
 	}
 
 	/* Insert node into huge. */
-	node->chunk = ret;
+	node->addr = ret;
 	node->size = chunk_size;
 
 	malloc_mutex_lock(&huge_mtx);
-	RB_INSERT(chunk_tree_ad_s, &huge, node);
+	RB_INSERT(extent_tree_ad_s, &huge, node);
 #ifdef MALLOC_STATS
 	huge_nmalloc++;
 	huge_allocated += chunk_size;
@@ -3484,17 +3789,10 @@ huge_ralloc(void *ptr, size_t size, size_t oldsize)
 	if (ret == NULL)
 		return (NULL);
 
-	if (CHUNK_ADDR2BASE(ptr) == ptr) {
-		/* The old allocation is a chunk. */
-		if (size < oldsize)
-			memcpy(ret, ptr, size);
-		else
-			memcpy(ret, ptr, oldsize);
-	} else {
-		/* The old allocation is a region. */
-		assert(oldsize < size);
+	if (size < oldsize)
+		memcpy(ret, ptr, size);
+	else
 		memcpy(ret, ptr, oldsize);
-	}
 	idalloc(ptr);
 	return (ret);
 }
@@ -3502,17 +3800,16 @@ huge_ralloc(void *ptr, size_t size, size_t oldsize)
 static void
 huge_dalloc(void *ptr)
 {
-	chunk_node_t key;
-	chunk_node_t *node;
+	extent_node_t *node, key;
 
 	malloc_mutex_lock(&huge_mtx);
 
 	/* Extract from tree of huge allocations. */
-	key.chunk = ptr;
-	node = RB_FIND(chunk_tree_ad_s, &huge, &key);
+	key.addr = ptr;
+	node = RB_FIND(extent_tree_ad_s, &huge, &key);
 	assert(node != NULL);
-	assert(node->chunk == ptr);
-	RB_REMOVE(chunk_tree_ad_s, &huge, node);
+	assert(node->addr == ptr);
+	RB_REMOVE(extent_tree_ad_s, &huge, node);
 
 #ifdef MALLOC_STATS
 	huge_ndalloc++;
@@ -3524,26 +3821,23 @@ huge_dalloc(void *ptr)
 	/* Unmap chunk. */
 #ifdef MALLOC_DSS
 	if (opt_dss && opt_junk)
-		memset(node->chunk, 0x5a, node->size);
+		memset(node->addr, 0x5a, node->size);
 #endif
-	chunk_dealloc(node->chunk, node->size);
+	chunk_dealloc(node->addr, node->size);
 
-	base_chunk_node_dealloc(node);
+	base_node_dealloc(node);
 }
 
 static void *
 imalloc(size_t size)
 {
-	void *ret;
 
 	assert(size != 0);
 
 	if (size <= arena_maxclass)
-		ret = arena_malloc(choose_arena(), size, false);
+		return (arena_malloc(choose_arena(), size, false));
 	else
-		ret = huge_malloc(size, false);
-
-	return (ret);
+		return (huge_malloc(size, false));
 }
 
 static void *
@@ -3644,14 +3938,11 @@ ipalloc(size_t alignment, size_t size)
 static void *
 icalloc(size_t size)
 {
-	void *ret;
 
 	if (size <= arena_maxclass)
-		ret = arena_malloc(choose_arena(), size, true);
+		return (arena_malloc(choose_arena(), size, true));
 	else
-		ret = huge_malloc(size, true);
-
-	return (ret);
+		return (huge_malloc(size, true));
 }
 
 static size_t
@@ -3669,15 +3960,15 @@ isalloc(const void *ptr)
 
 		ret = arena_salloc(ptr);
 	} else {
-		chunk_node_t *node, key;
+		extent_node_t *node, key;
 
 		/* Chunk (huge allocation). */
 
 		malloc_mutex_lock(&huge_mtx);
 
 		/* Extract from tree of huge allocations. */
-		key.chunk = __DECONST(void *, ptr);
-		node = RB_FIND(chunk_tree_ad_s, &huge, &key);
+		key.addr = __DECONST(void *, ptr);
+		node = RB_FIND(extent_tree_ad_s, &huge, &key);
 		assert(node != NULL);
 
 		ret = node->size;
@@ -3691,7 +3982,6 @@ isalloc(const void *ptr)
 static void *
 iralloc(void *ptr, size_t size)
 {
-	void *ret;
 	size_t oldsize;
 
 	assert(ptr != NULL);
@@ -3700,11 +3990,9 @@ iralloc(void *ptr, size_t size)
 	oldsize = isalloc(ptr);
 
 	if (size <= arena_maxclass)
-		ret = arena_ralloc(ptr, size, oldsize);
+		return (arena_ralloc(ptr, size, oldsize));
 	else
-		ret = huge_ralloc(ptr, size, oldsize);
-
-	return (ret);
+		return (huge_ralloc(ptr, size, oldsize));
 }
 
 static void
@@ -3715,10 +4003,9 @@ idalloc(void *ptr)
 	assert(ptr != NULL);
 
 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
-	if (chunk != ptr) {
-		/* Region. */
+	if (chunk != ptr)
 		arena_dalloc(chunk->arena, chunk, ptr);
-	} else
+	else
 		huge_dalloc(ptr);
 }
 
@@ -3742,8 +4029,7 @@ malloc_print_stats(void)
 #ifdef MALLOC_DSS
 		_malloc_message(opt_dss ? "D" : "d", "", "", "");
 #endif
-		_malloc_message(opt_hint ? "H" : "h",
-		    opt_junk ? "J" : "j", "", "");
+		_malloc_message(opt_junk ? "J" : "j", "", "", "");
 #ifdef MALLOC_DSS
 		_malloc_message(opt_mmap ? "M" : "m", "", "", "");
 #endif
@@ -3770,6 +4056,8 @@ malloc_print_stats(void)
 		_malloc_message("Quantum size: ", umax2s(quantum, s), "\n", "");
 		_malloc_message("Max small size: ", umax2s(small_max, s), "\n",
 		    "");
+		_malloc_message("Max dirty pages per arena: ",
+		    umax2s(opt_dirty_max, s), "\n", "");
 
 		_malloc_message("Chunk size: ", umax2s(chunksize, s), "", "");
 		_malloc_message(" (2^", umax2s(opt_chunk_2pow, s), ")\n", "");
@@ -3915,7 +4203,7 @@ malloc_init_hard(void)
 
 		result = sysconf(_SC_PAGESIZE);
 		assert(result != -1);
-		pagesize = (unsigned) result;
+		pagesize = (unsigned)result;
 
 		/*
 		 * We assume that pagesize is a power of 2 when calculating
@@ -4030,11 +4318,14 @@ OUT:
 					opt_dss = true;
 #endif
 					break;
-				case 'h':
-					opt_hint = false;
+				case 'f':
+					opt_dirty_max >>= 1;
 					break;
-				case 'H':
-					opt_hint = true;
+				case 'F':
+					if (opt_dirty_max == 0)
+						opt_dirty_max = 1;
+					else if ((opt_dirty_max << 1) != 0)
+						opt_dirty_max <<= 1;
 					break;
 				case 'j':
 					opt_junk = false;
@@ -4052,14 +4343,8 @@ OUT:
 						opt_chunk_2pow--;
 					break;
 				case 'K':
-					/*
-					 * There must be fewer pages in a chunk
-					 * than can be recorded by the pos
-					 * field of arena_chunk_map_t, in order
-					 * to make POS_EMPTY/POS_FREE special.
-					 */
-					if (opt_chunk_2pow - pagesize_2pow
-					    < (sizeof(uint32_t) << 3) - 1)
+					if (opt_chunk_2pow + 1 <
+					    (sizeof(size_t) << 3))
 						opt_chunk_2pow++;
 					break;
 				case 'l':
@@ -4141,12 +4426,12 @@ OUT:
 					break;
 				default: {
 					char cbuf[2];
-					
+
 					cbuf[0] = opts[j];
 					cbuf[1] = '\0';
 					_malloc_message(_getprogname(),
 					    ": (malloc) Unsupported character "
-					    "in malloc options: '", cbuf, 
+					    "in malloc options: '", cbuf,
 					    "'\n");
 				}
 				}
@@ -4193,13 +4478,20 @@ OUT:
 	chunksize_mask = chunksize - 1;
 	chunk_npages = (chunksize >> pagesize_2pow);
 	{
-		unsigned header_size;
+		size_t header_size;
 
-		header_size = sizeof(arena_chunk_t) + (sizeof(arena_chunk_map_t)
-		    * (chunk_npages - 1));
-		arena_chunk_header_npages = (header_size >> pagesize_2pow);
-		if ((header_size & pagesize_mask) != 0)
-			arena_chunk_header_npages++;
+		/*
+		 * Compute the header size such that it is large
+		 * enough to contain the page map and enough nodes for the
+		 * worst case: one node per non-header page plus one extra for
+		 * situations where we briefly have one more node allocated
+		 * than we will need.
+		 */
+		header_size = sizeof(arena_chunk_t) +
+		    (sizeof(arena_chunk_map_t) * (chunk_npages - 1)) +
+		    (sizeof(extent_node_t) * chunk_npages);
+		arena_chunk_header_npages = (header_size >> pagesize_2pow) +
+		    ((header_size & pagesize_mask) != 0);
 	}
 	arena_maxclass = chunksize - (arena_chunk_header_npages <<
 	    pagesize_2pow);
@@ -4232,8 +4524,8 @@ OUT:
 	dss_base = sbrk(0);
 	dss_prev = dss_base;
 	dss_max = dss_base;
-	RB_INIT(&dss_chunks_ad);
 	RB_INIT(&dss_chunks_szad);
+	RB_INIT(&dss_chunks_ad);
 #endif
 #ifdef MALLOC_STATS
 	huge_nmalloc = 0;
@@ -4254,7 +4546,7 @@ OUT:
 	if (opt_dss)
 		base_pages_alloc(0);
 #endif
-	base_chunk_nodes = NULL;
+	base_nodes = NULL;
 	malloc_mutex_init(&base_mtx);
 
 	if (ncpus > 1) {