1 files changed, 2166 insertions, 1224 deletions

diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c
index c8a22773b985..85d2901e8106 100644
--- a/lib/libc/stdlib/malloc.c
+++ b/lib/libc/stdlib/malloc.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (C) 2006,2007 Jason Evans <jasone@FreeBSD.org>.
+ * Copyright (C) 2006-2008 Jason Evans <jasone@FreeBSD.org>.
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -45,7 +45,8 @@
  * Allocation requests are rounded up to the nearest size class, and no record
  * of the original request size is maintained.  Allocations are broken into
  * categories according to size class.  Assuming runtime defaults, 4 kB pages
- * and a 16 byte quantum, the size classes in each category are as follows:
+ * and a 16 byte quantum on a 32-bit system, the size classes in each category
+ * are as follows:
  *
  *   |=====================================|
  *   | Category | Subcategory    |    Size |
@@ -69,9 +70,9 @@
  *   |                           |    8 kB |
  *   |                           |   12 kB |
  *   |                           |     ... |
+ *   |                           | 1004 kB |
+ *   |                           | 1008 kB |
  *   |                           | 1012 kB |
- *   |                           | 1016 kB |
- *   |                           | 1020 kB |
  *   |=====================================|
  *   | Huge                      |    1 MB |
  *   |                           |    2 MB |
@@ -98,12 +99,34 @@
  * defaults the A and J runtime options to off.  These settings are appropriate
  * for production systems.
  */
-#define MALLOC_PRODUCTION
+#define	MALLOC_PRODUCTION
 
 #ifndef MALLOC_PRODUCTION
+   /*
+    * MALLOC_DEBUG enables assertions and other sanity checks, and disables
+    * inline functions.
+    */
 #  define MALLOC_DEBUG
+
+   /* MALLOC_STATS enables statistics calculation. */
+#  define MALLOC_STATS
 #endif
 
+/*
+ * MALLOC_BALANCE enables monitoring of arena lock contention and dynamically
+ * re-balances arena load if exponentially averaged contention exceeds a
+ * certain threshold.
+ */
+#define	MALLOC_BALANCE
+
+/*
+ * MALLOC_DSS enables use of sbrk(2) to allocate chunks from the data storage
+ * segment (DSS).  In an ideal world, this functionality would be completely
+ * unnecessary, but we are burdened by history and the lack of resource limits
+ * for anonymous mapped memory.
+ */
+#define	MALLOC_DSS
+
 #include <sys/cdefs.h>
 __FBSDID("$FreeBSD$");
 
@@ -123,7 +146,6 @@ __FBSDID("$FreeBSD$");
 #include <sys/uio.h>
 #include <sys/ktrace.h> /* Must come after several other sys/ includes. */
 
-#include <machine/atomic.h>
 #include <machine/cpufunc.h>
 #include <machine/vmparam.h>
 
@@ -142,11 +164,6 @@ __FBSDID("$FreeBSD$");
 
 #include "un-namespace.h"
 
-/* MALLOC_STATS enables statistics calculation. */
-#ifndef MALLOC_PRODUCTION
-#  define MALLOC_STATS
-#endif
-
 #ifdef MALLOC_DEBUG
 #  ifdef NDEBUG
 #    undef NDEBUG
@@ -170,7 +187,7 @@ __FBSDID("$FreeBSD$");
 #ifdef __i386__
 #  define QUANTUM_2POW_MIN	4
 #  define SIZEOF_PTR_2POW	2
-#  define USE_BRK
+#  define CPU_SPINWAIT		__asm__ volatile("pause")
 #endif
 #ifdef __ia64__
 #  define QUANTUM_2POW_MIN	4
@@ -189,22 +206,21 @@ __FBSDID("$FreeBSD$");
 #ifdef __amd64__
 #  define QUANTUM_2POW_MIN	4
 #  define SIZEOF_PTR_2POW	3
+#  define CPU_SPINWAIT		__asm__ volatile("pause")
 #endif
 #ifdef __arm__
 #  define QUANTUM_2POW_MIN	3
 #  define SIZEOF_PTR_2POW	2
-#  define USE_BRK
 #  define NO_TLS
 #endif
 #ifdef __powerpc__
 #  define QUANTUM_2POW_MIN	4
 #  define SIZEOF_PTR_2POW	2
-#  define USE_BRK
 #endif
 
-#define	SIZEOF_PTR		(1 << SIZEOF_PTR_2POW)
+#define	SIZEOF_PTR		(1U << SIZEOF_PTR_2POW)
 
-/* sizeof(int) == (1 << SIZEOF_INT_2POW). */
+/* sizeof(int) == (1U << SIZEOF_INT_2POW). */
 #ifndef SIZEOF_INT_2POW
 #  define SIZEOF_INT_2POW	2
 #endif
@@ -214,19 +230,29 @@ __FBSDID("$FreeBSD$");
 #  define NO_TLS
 #endif
 
+#ifdef NO_TLS
+   /* MALLOC_BALANCE requires TLS. */
+#  ifdef MALLOC_BALANCE
+#    undef MALLOC_BALANCE
+#  endif
+#endif
+
 /*
  * Size and alignment of memory chunks that are allocated by the OS's virtual
  * memory system.
  */
 #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
  * negatively affect performance.
  */
 #define	CACHELINE_2POW		6
-#define	CACHELINE		((size_t)(1 << CACHELINE_2POW))
+#define	CACHELINE		((size_t)(1U << CACHELINE_2POW))
 
 /* Smallest size class to support. */
 #define	TINY_MIN_2POW		1
@@ -237,33 +263,84 @@ __FBSDID("$FreeBSD$");
  * power of 2.
  */
 #define	SMALL_MAX_2POW_DEFAULT	9
-#define	SMALL_MAX_DEFAULT	(1 << SMALL_MAX_2POW_DEFAULT)
+#define	SMALL_MAX_DEFAULT	(1U << SMALL_MAX_2POW_DEFAULT)
 
 /*
- * Maximum desired run header overhead.  Runs are sized as small as possible
- * such that this setting is still honored, without violating other constraints.
- * The goal is to make runs as small as possible without exceeding a per run
- * external fragmentation threshold.
+ * RUN_MAX_OVRHD indicates maximum desired run header overhead.  Runs are sized
+ * as small as possible such that this setting is still honored, without
+ * violating other constraints.  The goal is to make runs as small as possible
+ * without exceeding a per run external fragmentation threshold.
+ *
+ * We use binary fixed point math for overhead computations, where the binary
+ * point is implicitly RUN_BFP bits to the left.
  *
- * Note that it is possible to set this low enough that it cannot be honored
- * for some/all object sizes, since there is one bit of header overhead per
- * object (plus a constant).  In such cases, this constraint is relaxed.
+ * Note that it is possible to set RUN_MAX_OVRHD low enough that it cannot be
+ * honored for some/all object sizes, since there is one bit of header overhead
+ * per object (plus a constant).  This constraint is relaxed (ignored) for runs
+ * that are so small that the per-region overhead is greater than:
  *
- * RUN_MAX_OVRHD_RELAX specifies the maximum number of bits per region of
- * overhead for which RUN_MAX_OVRHD is relaxed.
+ *   (RUN_MAX_OVRHD / (reg_size << (3+RUN_BFP))
  */
-#define RUN_MAX_OVRHD		0.015
-#define RUN_MAX_OVRHD_RELAX	1.5
+#define	RUN_BFP			12
+/*                                    \/   Implicit binary fixed point. */
+#define	RUN_MAX_OVRHD		0x0000003dU
+#define	RUN_MAX_OVRHD_RELAX	0x00001800U
 
-/* Put a cap on small object run size.  This overrides RUN_MAX_OVRHD. */
-#define RUN_MAX_SMALL_2POW	15
-#define RUN_MAX_SMALL		(1 << RUN_MAX_SMALL_2POW)
+/*
+ * 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)
+
+/*
+ * Hyper-threaded CPUs may need a special instruction inside spin loops in
+ * order to yield to another virtual CPU.  If no such instruction is defined
+ * above, make CPU_SPINWAIT a no-op.
+ */
+#ifndef CPU_SPINWAIT
+#  define CPU_SPINWAIT
+#endif
+
+/*
+ * Adaptive spinning must eventually switch to blocking, in order to avoid the
+ * potential for priority inversion deadlock.  Backing off past a certain point
+ * can actually waste time.
+ */
+#define	SPIN_LIMIT_2POW		11
+
+/*
+ * Conversion from spinning to blocking is expensive; we use (1U <<
+ * BLOCK_COST_2POW) to estimate how many more times costly blocking is than
+ * worst-case spinning.
+ */
+#define	BLOCK_COST_2POW		4
+
+#ifdef MALLOC_BALANCE
+   /*
+    * We use an exponential moving average to track recent lock contention,
+    * where the size of the history window is N, and alpha=2/(N+1).
+    *
+    * Due to integer math rounding, very small values here can cause
+    * substantial degradation in accuracy, thus making the moving average decay
+    * faster than it would with precise calculation.
+    */
+#  define BALANCE_ALPHA_INV_2POW	9
+
+   /*
+    * Threshold value for the exponential moving contention average at which to
+    * re-assign a thread.
+    */
+#  define BALANCE_THRESHOLD_DEFAULT	(1U << (SPIN_LIMIT_2POW-4))
+#endif
 
 /******************************************************************************/
 
 /*
- * Mutexes based on spinlocks.  We can't use normal pthread mutexes, because
- * they require malloc()ed memory.
+ * Mutexes based on spinlocks.  We can't use normal pthread spinlocks in all
+ * places, because they require malloc()ed memory, which causes bootstrapping
+ * issues in some cases.
  */
 typedef struct {
 	spinlock_t	lock;
@@ -311,6 +388,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;
@@ -319,6 +405,11 @@ struct arena_stats_s {
 	size_t		allocated_large;
 	uint64_t	nmalloc_large;
 	uint64_t	ndalloc_large;
+
+#ifdef MALLOC_BALANCE
+	/* Number of times this arena reassigned a thread due to contention. */
+	uint64_t	nbalance;
+#endif
 };
 
 typedef struct chunk_stats_s chunk_stats_t;
@@ -341,28 +432,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 chunk tree. */
-	RB_ENTRY(chunk_node_s) link;
+/* 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;
 
-	/*
-	 * 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;
+	/* Linkage for the address-ordered tree. */
+	RB_ENTRY(extent_node_s) link_ad;
+
+	/* 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_s chunk_tree_t;
-RB_HEAD(chunk_tree_s, chunk_node_s);
+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);
 
 /******************************************************************************/
 /*
@@ -372,27 +463,21 @@ RB_HEAD(chunk_tree_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. */
-	uint32_t	npages;
-	/*
-	 * Position within run.  For a free run, this is POS_FREE for the first
-	 * and last pages.  The POS_FREE special value makes it possible to
-	 * quickly coalesce free runs.
-	 *
-	 * This is the limiting factor for chunksize; there can be at most 2^31
-	 * pages in a run.
-	 */
-#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;
@@ -401,22 +486,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
@@ -496,8 +576,8 @@ struct arena_s {
 #  define ARENA_MAGIC 0x947d3d24
 #endif
 
-	/* All operations on this arena require that mtx be locked. */
-	malloc_mutex_t		mtx;
+	/* All operations on this arena require that lock be locked. */
+	pthread_mutex_t		lock;
 
 #ifdef MALLOC_STATS
 	arena_stats_t		stats;
@@ -511,13 +591,41 @@ 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
 	 * a single spare inadequate.
 	 */
-	arena_chunk_t *spare;
+	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
+	 * lock contention there is.  This value is exponentially averaged.
+	 */
+	uint32_t		contention;
+#endif
 
 	/*
 	 * bins is used to store rings of free regions of the following sizes,
@@ -573,8 +681,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. */
 
 /********/
@@ -583,27 +691,32 @@ static size_t		arena_maxclass; /* Max size class for arenas. */
  */
 
 /* Protects chunk-related data structures. */
-static malloc_mutex_t	chunks_mtx;
+static malloc_mutex_t	huge_mtx;
 
 /* Tree of chunks that are stand-alone huge allocations. */
-static chunk_tree_t	huge;
+static extent_tree_ad_t	huge;
 
-#ifdef USE_BRK
+#ifdef MALLOC_DSS
 /*
- * Try to use brk for chunk-size allocations, due to address space constraints.
+ * Protects sbrk() calls.  This avoids malloc races among threads, though it
+ * does not protect against races with threads that call sbrk() directly.
  */
+static malloc_mutex_t	dss_mtx;
+/* Base address of the DSS. */
+static void		*dss_base;
+/* Current end of the DSS, or ((void *)-1) if the DSS is exhausted. */
+static void		*dss_prev;
+/* Current upper limit on DSS addresses. */
+static void		*dss_max;
+
 /*
- * Protects sbrk() calls.  This must be separate from chunks_mtx, since
- * base_pages_alloc() also uses sbrk(), but cannot lock chunks_mtx (doing so
- * could cause recursive lock acquisition).
+ * 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 function, different tree orderings are needed,
+ * which is why there are two trees with the same contents.
  */
-static malloc_mutex_t	brk_mtx;
-/* Result of first sbrk(0) call. */
-static void		*brk_base;
-/* Current end of brk, or ((void *)-1) if brk is exhausted. */
-static void		*brk_prev;
-/* Current upper limit on brk addresses. */
-static void		*brk_max;
+static extent_tree_szad_t dss_chunks_szad;
+static extent_tree_ad_t	dss_chunks_ad;
 #endif
 
 #ifdef MALLOC_STATS
@@ -613,12 +726,6 @@ static uint64_t		huge_ndalloc;
 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.
- */
-static chunk_tree_t	old_chunks;
-
 /****************************/
 /*
  * base (internal allocation).
@@ -632,7 +739,7 @@ static chunk_tree_t	old_chunks;
 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;
@@ -650,9 +757,13 @@ static size_t		base_mapped;
 static arena_t		**arenas;
 static unsigned		narenas;
 #ifndef NO_TLS
+#  ifdef MALLOC_BALANCE
+static unsigned		narenas_2pow;
+#  else
 static unsigned		next_arena;
+#  endif
 #endif
-static malloc_mutex_t	arenas_mtx; /* Protects arenas initialization. */
+static pthread_mutex_t	arenas_lock; /* Protects arenas initialization. */
 
 #ifndef NO_TLS
 /*
@@ -680,7 +791,14 @@ static bool	opt_junk = true;
 static bool	opt_abort = false;
 static bool	opt_junk = false;
 #endif
-static bool	opt_hint = false;
+#ifdef MALLOC_DSS
+static bool	opt_dss = true;
+static bool	opt_mmap = true;
+#endif
+static size_t	opt_dirty_max = DIRTY_MAX_DEFAULT;
+#ifdef MALLOC_BALANCE
+static uint64_t	opt_balance_threshold = BALANCE_THRESHOLD_DEFAULT;
+#endif
 static bool	opt_print_stats = false;
 static size_t	opt_quantum_2pow = QUANTUM_2POW_MIN;
 static size_t	opt_small_max_2pow = SMALL_MAX_2POW_DEFAULT;
@@ -689,7 +807,7 @@ static bool	opt_utrace = false;
 static bool	opt_sysv = false;
 static bool	opt_xmalloc = false;
 static bool	opt_zero = false;
-static int32_t	opt_narenas_lshift = 0;
+static int	opt_narenas_lshift = 0;
 
 typedef struct {
 	void	*p;
@@ -699,7 +817,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));				\
 	}
 
@@ -708,53 +829,83 @@ typedef struct {
  * Begin function prototypes for non-inline static functions.
  */
 
-static void	malloc_mutex_init(malloc_mutex_t *a_mutex);
+static void	malloc_mutex_init(malloc_mutex_t *mutex);
+static bool	malloc_spin_init(pthread_mutex_t *lock);
 static void	wrtmessage(const char *p1, const char *p2, const char *p3,
 		const char *p4);
 #ifdef MALLOC_STATS
 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 chunk_node_t *base_chunk_node_alloc(void);
-static void	base_chunk_node_dealloc(chunk_node_t *node);
+static void	*base_calloc(size_t number, size_t size);
+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);
-static void	*chunk_alloc(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 void	arena_run_split(arena_t *arena, arena_run_t *run, size_t size);
+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 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);
-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);
+#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_dalloc_large(arena_t *arena, arena_chunk_t *chunk,
+    void *ptr);
+static void	arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk,
+    void *ptr, size_t size, size_t oldsize);
+static bool	arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk,
+    void *ptr, size_t size, size_t oldsize);
+static bool	arena_ralloc_large(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);
 static bool	arena_new(arena_t *arena);
 static arena_t	*arenas_extend(unsigned ind);
-static void	*huge_malloc(size_t size);
+static void	*huge_malloc(size_t size, bool zero);
 static void	*huge_palloc(size_t alignment, size_t size);
 static void	*huge_ralloc(void *ptr, size_t size, size_t oldsize);
 static void	huge_dalloc(void *ptr);
-static void	*imalloc(size_t size);
-static void	*ipalloc(size_t alignment, size_t size);
-static void	*icalloc(size_t size);
-static size_t	isalloc(const void *ptr);
-static void	*iralloc(void *ptr, size_t size);
-static void	idalloc(void *ptr);
 static void	malloc_print_stats(void);
 static bool	malloc_init_hard(void);
 
@@ -763,31 +914,33 @@ static bool	malloc_init_hard(void);
  */
 /******************************************************************************/
 /*
- * Begin mutex.
+ * Begin mutex.  We can't use normal pthread mutexes in all places, because
+ * they require malloc()ed memory, which causes bootstrapping issues in some
+ * cases.
  */
 
 static void
-malloc_mutex_init(malloc_mutex_t *a_mutex)
+malloc_mutex_init(malloc_mutex_t *mutex)
 {
 	static const spinlock_t lock = _SPINLOCK_INITIALIZER;
 
-	a_mutex->lock = lock;
+	mutex->lock = lock;
 }
 
 static inline void
-malloc_mutex_lock(malloc_mutex_t *a_mutex)
+malloc_mutex_lock(malloc_mutex_t *mutex)
 {
 
 	if (__isthreaded)
-		_SPINLOCK(&a_mutex->lock);
+		_SPINLOCK(&mutex->lock);
 }
 
 static inline void
-malloc_mutex_unlock(malloc_mutex_t *a_mutex)
+malloc_mutex_unlock(malloc_mutex_t *mutex)
 {
 
 	if (__isthreaded)
-		_SPINUNLOCK(&a_mutex->lock);
+		_SPINUNLOCK(&mutex->lock);
 }
 
 /*
@@ -795,6 +948,86 @@ malloc_mutex_unlock(malloc_mutex_t *a_mutex)
  */
 /******************************************************************************/
 /*
+ * Begin spin lock.  Spin locks here are actually adaptive mutexes that block
+ * after a period of spinning, because unbounded spinning would allow for
+ * priority inversion.
+ */
+
+/*
+ * We use an unpublished interface to initialize pthread mutexes with an
+ * allocation callback, in order to avoid infinite recursion.
+ */
+int	_pthread_mutex_init_calloc_cb(pthread_mutex_t *mutex,
+    void *(calloc_cb)(size_t, size_t));
+
+__weak_reference(_pthread_mutex_init_calloc_cb_stub,
+    _pthread_mutex_init_calloc_cb);
+
+int
+_pthread_mutex_init_calloc_cb_stub(pthread_mutex_t *mutex,
+    void *(calloc_cb)(size_t, size_t))
+{
+
+	return (0);
+}
+
+static bool
+malloc_spin_init(pthread_mutex_t *lock)
+{
+
+	if (_pthread_mutex_init_calloc_cb(lock, base_calloc) != 0)
+		return (true);
+
+	return (false);
+}
+
+static inline unsigned
+malloc_spin_lock(pthread_mutex_t *lock)
+{
+	unsigned ret = 0;
+
+	if (__isthreaded) {
+		if (_pthread_mutex_trylock(lock) != 0) {
+			unsigned i;
+			volatile unsigned j;
+
+			/* Exponentially back off. */
+			for (i = 1; i <= SPIN_LIMIT_2POW; i++) {
+				for (j = 0; j < (1U << i); j++)
+					ret++;
+
+				CPU_SPINWAIT;
+				if (_pthread_mutex_trylock(lock) == 0)
+					return (ret);
+			}
+
+			/*
+			 * Spinning failed.  Block until the lock becomes
+			 * available, in order to avoid indefinite priority
+			 * inversion.
+			 */
+			_pthread_mutex_lock(lock);
+			assert((ret << BLOCK_COST_2POW) != 0);
+			return (ret << BLOCK_COST_2POW);
+		}
+	}
+
+	return (ret);
+}
+
+static inline void
+malloc_spin_unlock(pthread_mutex_t *lock)
+{
+
+	if (__isthreaded)
+		_pthread_mutex_unlock(lock);
+}
+
+/*
+ * End spin lock.
+ */
+/******************************************************************************/
+/*
  * Begin Utility functions/macros.
  */
 
@@ -840,6 +1073,56 @@ pow2_ceil(size_t x)
 	return (x);
 }
 
+#ifdef MALLOC_BALANCE
+/*
+ * Use a simple linear congruential pseudo-random number generator:
+ *
+ *   prn(y) = (a*x + c) % m
+ *
+ * where the following constants ensure maximal period:
+ *
+ *   a == Odd number (relatively prime to 2^n), and (a-1) is a multiple of 4.
+ *   c == Odd number (relatively prime to 2^n).
+ *   m == 2^32
+ *
+ * See Knuth's TAOCP 3rd Ed., Vol. 2, pg. 17 for details on these constraints.
+ *
+ * This choice of m has the disadvantage that the quality of the bits is
+ * proportional to bit position.  For example. the lowest bit has a cycle of 2,
+ * the next has a cycle of 4, etc.  For this reason, we prefer to use the upper
+ * bits.
+ */
+#  define PRN_DEFINE(suffix, var, a, c)					\
+static inline void							\
+sprn_##suffix(uint32_t seed)						\
+{									\
+	var = seed;							\
+}									\
+									\
+static inline uint32_t							\
+prn_##suffix(uint32_t lg_range)						\
+{									\
+	uint32_t ret, x;						\
+									\
+	assert(lg_range > 0);						\
+	assert(lg_range <= 32);						\
+									\
+	x = (var * (a)) + (c);						\
+	var = x;							\
+	ret = x >> (32 - lg_range);					\
+									\
+	return (ret);							\
+}
+#  define SPRN(suffix, seed)	sprn_##suffix(seed)
+#  define PRN(suffix, lg_range)	prn_##suffix(lg_range)
+#endif
+
+#ifdef MALLOC_BALANCE
+/* Define the PRNG used for arena assignment. */
+static __thread uint32_t balance_x;
+PRN_DEFINE(balance, balance_x, 1297, 1301)
+#endif
+
 static void
 wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4)
 {
@@ -876,7 +1159,7 @@ malloc_printf(const char *format, ...)
  * integer printing functionality, so that malloc_printf() use can be limited to
  * MALLOC_STATS code.
  */
-#define UMAX2S_BUFSIZE	21
+#define	UMAX2S_BUFSIZE	21
 static char *
 umax2s(uintmax_t x, char *s)
 {
@@ -898,62 +1181,61 @@ umax2s(uintmax_t x, char *s)
 
 /******************************************************************************/
 
+#ifdef MALLOC_DSS
 static bool
-base_pages_alloc(size_t minsize)
+base_pages_alloc_dss(size_t minsize)
 {
-	size_t csize;
 
-#ifdef USE_BRK
 	/*
-	 * Do special brk allocation here, since base allocations don't need to
+	 * Do special DSS allocation here, since base allocations don't need to
 	 * be chunk-aligned.
 	 */
-	if (brk_prev != (void *)-1) {
-		void *brk_cur;
+	malloc_mutex_lock(&dss_mtx);
+	if (dss_prev != (void *)-1) {
 		intptr_t incr;
+		size_t csize = CHUNK_CEILING(minsize);
 
-		if (minsize != 0)
-			csize = CHUNK_CEILING(minsize);
-
-		malloc_mutex_lock(&brk_mtx);
 		do {
-			/* Get the current end of brk. */
-			brk_cur = sbrk(0);
+			/* Get the current end of the DSS. */
+			dss_max = sbrk(0);
 
 			/*
 			 * Calculate how much padding is necessary to
-			 * chunk-align the end of brk.  Don't worry about
-			 * brk_cur not being chunk-aligned though.
+			 * chunk-align the end of the DSS.  Don't worry about
+			 * dss_max not being chunk-aligned though.
 			 */
 			incr = (intptr_t)chunksize
-			    - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur);
-			if (incr < minsize)
+			    - (intptr_t)CHUNK_ADDR2OFFSET(dss_max);
+			assert(incr >= 0);
+			if ((size_t)incr < minsize)
 				incr += csize;
 
-			brk_prev = sbrk(incr);
-			if (brk_prev == brk_cur) {
+			dss_prev = sbrk(incr);
+			if (dss_prev == dss_max) {
 				/* Success. */
-				malloc_mutex_unlock(&brk_mtx);
-				base_pages = brk_cur;
+				dss_max = (void *)((intptr_t)dss_prev + incr);
+				base_pages = dss_prev;
 				base_next_addr = base_pages;
-				base_past_addr = (void *)((uintptr_t)base_pages
-				    + incr);
+				base_past_addr = dss_max;
 #ifdef MALLOC_STATS
 				base_mapped += incr;
 #endif
+				malloc_mutex_unlock(&dss_mtx);
 				return (false);
 			}
-		} while (brk_prev != (void *)-1);
-		malloc_mutex_unlock(&brk_mtx);
-	}
-	if (minsize == 0) {
-		/*
-		 * Failure during initialization doesn't matter, so avoid
-		 * falling through to the mmap-based page mapping code.
-		 */
-		return (true);
+		} while (dss_prev != (void *)-1);
 	}
+	malloc_mutex_unlock(&dss_mtx);
+
+	return (true);
+}
 #endif
+
+static bool
+base_pages_alloc_mmap(size_t minsize)
+{
+	size_t csize;
+
 	assert(minsize != 0);
 	csize = PAGE_CEILING(minsize);
 	base_pages = pages_map(NULL, csize);
@@ -964,9 +1246,30 @@ base_pages_alloc(size_t minsize)
 #ifdef MALLOC_STATS
 	base_mapped += csize;
 #endif
+
 	return (false);
 }
 
+static bool
+base_pages_alloc(size_t minsize)
+{
+
+#ifdef MALLOC_DSS
+	if (opt_dss) {
+		if (base_pages_alloc_dss(minsize) == false)
+			return (false);
+	}
+
+	if (opt_mmap && minsize != 0)
+#endif
+	{
+		if (base_pages_alloc_mmap(minsize) == false)
+			return (false);
+	}
+
+	return (true);
+}
+
 static void *
 base_alloc(size_t size)
 {
@@ -977,49 +1280,55 @@ 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);
+}
+
+static void *
+base_calloc(size_t number, size_t size)
+{
+	void *ret;
+
+	ret = base_alloc(number * size);
+	memset(ret, 0, number * 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);
 }
 
@@ -1029,31 +1338,36 @@ base_chunk_node_dealloc(chunk_node_t *node)
 static void
 stats_print(arena_t *arena)
 {
-	unsigned i;
-	int 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,
+	unsigned i, gap_start;
+
+	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");
-	for (i = 0, gap_start = -1; i < ntbins + nqbins + nsbins; i++) {
+	for (i = 0, gap_start = UINT_MAX; i < ntbins + nqbins + nsbins; i++) {
 		if (arena->bins[i].stats.nrequests == 0) {
-			if (gap_start == -1)
+			if (gap_start == UINT_MAX)
 				gap_start = i;
 		} else {
-			if (gap_start != -1) {
+			if (gap_start != UINT_MAX) {
 				if (i > gap_start + 1) {
 					/* Gap of more than one size class. */
 					malloc_printf("[%u..%u]\n",
@@ -1062,7 +1376,7 @@ stats_print(arena_t *arena)
 					/* Gap of one size class. */
 					malloc_printf("[%u]\n", gap_start);
 				}
-				gap_start = -1;
+				gap_start = UINT_MAX;
 			}
 			malloc_printf(
 			    "%13u %1s %4u %4u %3u %9llu %9llu"
@@ -1079,7 +1393,7 @@ stats_print(arena_t *arena)
 			    arena->bins[i].stats.curruns);
 		}
 	}
-	if (gap_start != -1) {
+	if (gap_start != UINT_MAX) {
 		if (i > gap_start + 1) {
 			/* Gap of more than one size class. */
 			malloc_printf("[%u..%u]\n", gap_start, i - 1);
@@ -1096,26 +1410,50 @@ stats_print(arena_t *arena)
  */
 /******************************************************************************/
 /*
- * Begin chunk management functions.
+ * Begin extent tree code.
  */
 
 static inline int
-chunk_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;
+	size_t b_size = b->size;
 
-	assert(a != NULL);
-	assert(b != NULL);
+	ret = (a_size > b_size) - (a_size < b_size);
+	if (ret == 0) {
+		uintptr_t a_addr = (uintptr_t)a->addr;
+		uintptr_t b_addr = (uintptr_t)b->addr;
 
-	if ((uintptr_t)a->chunk < (uintptr_t)b->chunk)
-		return (-1);
-	else if (a->chunk == b->chunk)
-		return (0);
-	else
-		return (1);
+		ret = (a_addr > b_addr) - (a_addr < b_addr);
+	}
+
+	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 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)
@@ -1168,67 +1506,149 @@ pages_unmap(void *addr, size_t size)
 	}
 }
 
+#ifdef MALLOC_DSS
 static void *
-chunk_alloc(size_t size)
+chunk_alloc_dss(size_t size)
 {
-	void *ret, *chunk;
-	chunk_node_t *tchunk, *delchunk;
 
-	assert(size != 0);
-	assert((size & chunksize_mask) == 0);
-
-	malloc_mutex_lock(&chunks_mtx);
+	malloc_mutex_lock(&dss_mtx);
+	if (dss_prev != (void *)-1) {
+		intptr_t incr;
 
-	if (size == chunksize) {
 		/*
-		 * Check for address ranges that were previously chunks and try
-		 * to use them.
+		 * The loop is necessary to recover from races with other
+		 * threads that are using the DSS for something other than
+		 * malloc.
 		 */
+		do {
+			void *ret;
 
-		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);
-			base_chunk_node_dealloc(delchunk);
+			/* Get the current end of the DSS. */
+			dss_max = sbrk(0);
 
-#ifdef USE_BRK
-			if ((uintptr_t)chunk >= (uintptr_t)brk_base
-			    && (uintptr_t)chunk < (uintptr_t)brk_max) {
-				/* Re-use a previously freed brk chunk. */
-				ret = chunk;
-				goto RETURN;
+			/*
+			 * Calculate how much padding is necessary to
+			 * chunk-align the end of the DSS.
+			 */
+			incr = (intptr_t)size
+			    - (intptr_t)CHUNK_ADDR2OFFSET(dss_max);
+			if (incr == (intptr_t)size)
+				ret = dss_max;
+			else {
+				ret = (void *)((intptr_t)dss_max + incr);
+				incr += size;
 			}
-#endif
-			if ((ret = pages_map(chunk, size)) != NULL) {
+
+			dss_prev = sbrk(incr);
+			if (dss_prev == dss_max) {
 				/* Success. */
-				goto RETURN;
+				dss_max = (void *)((intptr_t)dss_prev + incr);
+				malloc_mutex_unlock(&dss_mtx);
+				return (ret);
 			}
+		} while (dss_prev != (void *)-1);
+	}
+	malloc_mutex_unlock(&dss_mtx);
+
+	return (NULL);
+}
+
+static void *
+chunk_recycle_dss(size_t size, bool zero)
+{
+	extent_node_t *node, key;
+
+	key.addr = NULL;
+	key.size = size;
+	malloc_mutex_lock(&dss_mtx);
+	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(extent_tree_szad_s, &dss_chunks_szad, node);
+		if (node->size == size) {
+			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
+			 * smaller chunk.  Its position within dss_chunks_ad
+			 * does not change.
+			 */
+			assert(node->size > size);
+			node->addr = (void *)((uintptr_t)node->addr + size);
+			node->size -= size;
+			RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
 		}
+		malloc_mutex_unlock(&dss_mtx);
+
+		if (zero)
+			memset(ret, 0, size);
+		return (ret);
 	}
+	malloc_mutex_unlock(&dss_mtx);
+
+	return (NULL);
+}
+#endif
+
+static void *
+chunk_alloc_mmap(size_t size)
+{
+	void *ret;
+	size_t offset;
 
 	/*
-	 * Try to over-allocate, but allow the OS to place the allocation
-	 * anywhere.  Beware of size_t wrap-around.
+	 * Ideally, there would be a way to specify alignment to mmap() (like
+	 * NetBSD has), but in the absence of such a feature, we have to work
+	 * hard to efficiently create aligned mappings.  The reliable, but
+	 * expensive method is to create a mapping that is over-sized, then
+	 * trim the excess.  However, that always results in at least one call
+	 * to pages_unmap().
+	 *
+	 * A more optimistic approach is to try mapping precisely the right
+	 * amount, then try to append another mapping if alignment is off.  In
+	 * practice, this works out well as long as the application is not
+	 * interleaving mappings via direct mmap() calls.  If we do run into a
+	 * situation where there is an interleaved mapping and we are unable to
+	 * extend an unaligned mapping, our best option is to momentarily
+	 * revert to the reliable-but-expensive method.  This will tend to
+	 * leave a gap in the memory map that is too small to cause later
+	 * problems for the optimistic method.
 	 */
-	if (size + chunksize > size) {
-		if ((ret = pages_map(NULL, size + chunksize)) != NULL) {
-			size_t offset = CHUNK_ADDR2OFFSET(ret);
 
+	ret = pages_map(NULL, size);
+	if (ret == NULL)
+		return (NULL);
+
+	offset = CHUNK_ADDR2OFFSET(ret);
+	if (offset != 0) {
+		/* Try to extend chunk boundary. */
+		if (pages_map((void *)((uintptr_t)ret + size),
+		    chunksize - offset) == NULL) {
 			/*
-			 * Success.  Clean up unneeded leading/trailing space.
+			 * Extension failed.  Clean up, then revert to the
+			 * reliable-but-expensive method.
 			 */
+			pages_unmap(ret, size);
+
+			/* Beware size_t wrap-around. */
+			if (size + chunksize <= size)
+				return NULL;
+
+			ret = pages_map(NULL, size + chunksize);
+			if (ret == NULL)
+				return (NULL);
+
+			/* Clean up unneeded leading/trailing space. */
+			offset = CHUNK_ADDR2OFFSET(ret);
 			if (offset != 0) {
 				/* Leading space. */
 				pages_unmap(ret, chunksize - offset);
 
-				ret = (void *)((uintptr_t)ret + (chunksize -
-				    offset));
+				ret = (void *)((uintptr_t)ret +
+				    (chunksize - offset));
 
 				/* Trailing space. */
 				pages_unmap((void *)((uintptr_t)ret + size),
@@ -1238,74 +1658,47 @@ chunk_alloc(size_t size)
 				pages_unmap((void *)((uintptr_t)ret + size),
 				    chunksize);
 			}
-			goto RETURN;
+		} else {
+			/* Clean up unneeded leading space. */
+			pages_unmap(ret, chunksize - offset);
+			ret = (void *)((uintptr_t)ret + (chunksize - offset));
 		}
 	}
 
-#ifdef USE_BRK
-	/*
-	 * Try to create allocations in brk, in order to make full use of
-	 * limited address space.
-	 */
-	if (brk_prev != (void *)-1) {
-		void *brk_cur;
-		intptr_t incr;
+	return (ret);
+}
 
-		/*
-		 * The loop is necessary to recover from races with other
-		 * threads that are using brk for something other than malloc.
-		 */
-		malloc_mutex_lock(&brk_mtx);
-		do {
-			/* Get the current end of brk. */
-			brk_cur = sbrk(0);
+static void *
+chunk_alloc(size_t size, bool zero)
+{
+	void *ret;
 
-			/*
-			 * Calculate how much padding is necessary to
-			 * chunk-align the end of brk.
-			 */
-			incr = (intptr_t)size
-			    - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur);
-			if (incr == size) {
-				ret = brk_cur;
-			} else {
-				ret = (void *)((intptr_t)brk_cur + incr);
-				incr += size;
-			}
+	assert(size != 0);
+	assert((size & chunksize_mask) == 0);
 
-			brk_prev = sbrk(incr);
-			if (brk_prev == brk_cur) {
-				/* Success. */
-				malloc_mutex_unlock(&brk_mtx);
-				brk_max = (void *)((intptr_t)ret + size);
-				goto RETURN;
-			}
-		} while (brk_prev != (void *)-1);
-		malloc_mutex_unlock(&brk_mtx);
+#ifdef MALLOC_DSS
+	if (opt_dss) {
+		ret = chunk_recycle_dss(size, zero);
+		if (ret != NULL) {
+			goto RETURN;
+		}
+
+		ret = chunk_alloc_dss(size);
+		if (ret != NULL)
+			goto RETURN;
 	}
+
+	if (opt_mmap)
 #endif
+	{
+		ret = chunk_alloc_mmap(size);
+		if (ret != NULL)
+			goto RETURN;
+	}
 
 	/* All strategies for allocation failed. */
 	ret = NULL;
 RETURN:
-	if (ret != NULL) {
-		chunk_node_t key;
-		/*
-		 * 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);
-		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);
-			base_chunk_node_dealloc(delchunk);
-		}
-
-	}
 #ifdef MALLOC_STATS
 	if (ret != NULL) {
 		stats_chunks.nchunks += (size / chunksize);
@@ -1314,100 +1707,151 @@ RETURN:
 	if (stats_chunks.curchunks > stats_chunks.highchunks)
 		stats_chunks.highchunks = stats_chunks.curchunks;
 #endif
-	malloc_mutex_unlock(&chunks_mtx);
 
 	assert(CHUNK_ADDR2BASE(ret) == ret);
 	return (ret);
 }
 
-static void
-chunk_dealloc(void *chunk, size_t size)
+#ifdef MALLOC_DSS
+static extent_node_t *
+chunk_dealloc_dss_record(void *chunk, size_t size)
 {
-	chunk_node_t *node;
+	extent_node_t *node, *prev, key;
 
-	assert(chunk != NULL);
-	assert(CHUNK_ADDR2BASE(chunk) == chunk);
-	assert(size != 0);
-	assert((size & chunksize_mask) == 0);
+	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->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(extent_tree_szad_s, &dss_chunks_szad, node);
+		node->addr = chunk;
+		node->size += size;
+		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.
+		 */
+		malloc_mutex_unlock(&dss_mtx);
+		node = base_node_alloc();
+		malloc_mutex_lock(&dss_mtx);
+		if (node == NULL)
+			return (NULL);
+		node->addr = chunk;
+		node->size = size;
+		RB_INSERT(extent_tree_ad_s, &dss_chunks_ad, node);
+		RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
+	}
 
-	malloc_mutex_lock(&chunks_mtx);
+	/* Try to coalesce backward. */
+	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(extent_tree_szad_s, &dss_chunks_szad, prev);
+		RB_REMOVE(extent_tree_ad_s, &dss_chunks_ad, prev);
 
-#ifdef USE_BRK
-	if ((uintptr_t)chunk >= (uintptr_t)brk_base
-	    && (uintptr_t)chunk < (uintptr_t)brk_max) {
-		void *brk_cur;
+		RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad, node);
+		node->addr = prev->addr;
+		node->size += prev->size;
+		RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
 
-		malloc_mutex_lock(&brk_mtx);
-		/* Get the current end of brk. */
-		brk_cur = sbrk(0);
+		base_node_dealloc(prev);
+	}
 
-		/*
-		 * Try to shrink the data segment if this chunk is at the end
-		 * of the data segment.  The sbrk() call here is subject to a
-		 * race condition with threads that use brk(2) or sbrk(2)
-		 * directly, but the alternative would be to leak memory for
-		 * the sake of poorly designed multi-threaded programs.
-		 */
-		if (brk_cur == brk_max
-		    && (void *)((uintptr_t)chunk + size) == brk_max
-		    && sbrk(-(intptr_t)size) == brk_max) {
-			malloc_mutex_unlock(&brk_mtx);
-			if (brk_prev == brk_max) {
-				/* Success. */
-				brk_prev = (void *)((intptr_t)brk_max
-				    - (intptr_t)size);
-				brk_max = brk_prev;
-			}
-		} else {
-			size_t offset;
+	return (node);
+}
 
-			malloc_mutex_unlock(&brk_mtx);
-			madvise(chunk, size, MADV_FREE);
+static bool
+chunk_dealloc_dss(void *chunk, size_t size)
+{
 
-			/*
-			 * 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;
+	malloc_mutex_lock(&dss_mtx);
+	if ((uintptr_t)chunk >= (uintptr_t)dss_base
+	    && (uintptr_t)chunk < (uintptr_t)dss_max) {
+		extent_node_t *node;
 
-				node->chunk = (void *)((uintptr_t)chunk
-				    + (uintptr_t)offset);
-				node->size = chunksize;
-				RB_INSERT(chunk_tree_s, &old_chunks, node);
-			}
+		/* Try to coalesce with other unused chunks. */
+		node = chunk_dealloc_dss_record(chunk, size);
+		if (node != NULL) {
+			chunk = node->addr;
+			size = node->size;
 		}
-	} else {
-#endif
-		pages_unmap(chunk, size);
+
+		/* Get the current end of the DSS. */
+		dss_max = sbrk(0);
 
 		/*
-		 * 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).
+		 * Try to shrink the DSS if this chunk is at the end of the
+		 * DSS.  The sbrk() call here is subject to a race condition
+		 * with threads that use brk(2) or sbrk(2) directly, but the
+		 * alternative would be to leak memory for the sake of poorly
+		 * designed multi-threaded programs.
 		 */
-		if (size == chunksize) {
-			node = base_chunk_node_alloc();
+		if ((void *)((uintptr_t)chunk + size) == dss_max
+		    && (dss_prev = sbrk(-(intptr_t)size)) == dss_max) {
+			/* Success. */
+			dss_max = (void *)((intptr_t)dss_prev - (intptr_t)size);
+
 			if (node != NULL) {
-				node->chunk = (void *)(uintptr_t)chunk;
-				node->size = chunksize;
-				RB_INSERT(chunk_tree_s, &old_chunks, node);
+				RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad,
+				    node);
+				RB_REMOVE(extent_tree_ad_s, &dss_chunks_ad,
+				    node);
+				base_node_dealloc(node);
 			}
+			malloc_mutex_unlock(&dss_mtx);
+		} else {
+			malloc_mutex_unlock(&dss_mtx);
+			madvise(chunk, size, MADV_FREE);
 		}
-#ifdef USE_BRK
+
+		return (false);
 	}
+	malloc_mutex_unlock(&dss_mtx);
+
+	return (true);
+}
 #endif
 
+static void
+chunk_dealloc_mmap(void *chunk, size_t size)
+{
+
+	pages_unmap(chunk, size);
+}
+
+static void
+chunk_dealloc(void *chunk, size_t size)
+{
+
+	assert(chunk != NULL);
+	assert(CHUNK_ADDR2BASE(chunk) == chunk);
+	assert(size != 0);
+	assert((size & chunksize_mask) == 0);
+
 #ifdef MALLOC_STATS
 	stats_chunks.curchunks -= (size / chunksize);
 #endif
-	malloc_mutex_unlock(&chunks_mtx);
+
+#ifdef MALLOC_DSS
+	if (opt_dss) {
+		if (chunk_dealloc_dss(chunk, size) == false)
+			return;
+	}
+
+	if (opt_mmap)
+#endif
+		chunk_dealloc_mmap(chunk, size);
 }
 
 /*
@@ -1434,20 +1878,17 @@ 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]);
 	}
 
 	ret = arenas_map;
-	if (ret == NULL)
+	if (ret == NULL) {
 		ret = choose_arena_hard();
+		assert(ret != NULL);
+	}
 #else
-	if (__isthreaded) {
+	if (__isthreaded && narenas > 1) {
 		unsigned long ind;
 
 		/*
@@ -1479,12 +1920,12 @@ choose_arena(void)
 			 * Avoid races with another thread that may have already
 			 * initialized arenas[ind].
 			 */
-			malloc_mutex_lock(&arenas_mtx);
+			malloc_spin_lock(&arenas_lock);
 			if (arenas[ind] == NULL)
 				ret = arenas_extend((unsigned)ind);
 			else
 				ret = arenas[ind];
-			malloc_mutex_unlock(&arenas_mtx);
+			malloc_spin_unlock(&arenas_lock);
 		}
 	} else
 		ret = arenas[0];
@@ -1506,21 +1947,32 @@ choose_arena_hard(void)
 
 	assert(__isthreaded);
 
-	/* Assign one of the arenas to this thread, in a round-robin fashion. */
-	malloc_mutex_lock(&arenas_mtx);
-	ret = arenas[next_arena];
-	if (ret == NULL)
-		ret = arenas_extend(next_arena);
-	if (ret == NULL) {
-		/*
-		 * Make sure that this function never returns NULL, so that
-		 * choose_arena() doesn't have to check for a NULL return
-		 * value.
-		 */
+#ifdef MALLOC_BALANCE
+	/* Seed the PRNG used for arena load balancing. */
+	SPRN(balance, (uint32_t)(uintptr_t)(_pthread_self()));
+#endif
+
+	if (narenas > 1) {
+#ifdef MALLOC_BALANCE
+		unsigned ind;
+
+		ind = PRN(balance, narenas_2pow);
+		if ((ret = arenas[ind]) == NULL) {
+			malloc_spin_lock(&arenas_lock);
+			if ((ret = arenas[ind]) == NULL)
+				ret = arenas_extend(ind);
+			malloc_spin_unlock(&arenas_lock);
+		}
+#else
+		malloc_spin_lock(&arenas_lock);
+		if ((ret = arenas[next_arena]) == NULL)
+			ret = arenas_extend(next_arena);
+		next_arena = (next_arena + 1) % narenas;
+		malloc_spin_unlock(&arenas_lock);
+#endif
+	} else
 		ret = arenas[0];
-	}
-	next_arena = (next_arena + 1) % narenas;
-	malloc_mutex_unlock(&arenas_mtx);
+
 	arenas_map = ret;
 
 	return (ret);
@@ -1530,38 +1982,60 @@ 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. */
-RB_GENERATE_STATIC(arena_chunk_tree_s, arena_chunk_s, link, arena_chunk_comp);
+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. */
-RB_GENERATE_STATIC(arena_run_tree_s, arena_run_s, link, arena_run_comp);
+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)
@@ -1584,11 +2058,12 @@ 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));
 
 		/* Clear bit. */
-		mask ^= (1 << bit);
+		mask ^= (1U << bit);
 		run->regs_mask[i] = mask;
 
 		return (ret);
@@ -1601,11 +2076,12 @@ 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));
 
 			/* Clear bit. */
-			mask ^= (1 << bit);
+			mask ^= (1U << bit);
 			run->regs_mask[i] = mask;
 
 			/*
@@ -1635,8 +2111,8 @@ arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
 	 *
 	 *   (X * size_invs[(D >> QUANTUM_2POW_MIN) - 3]) >> SIZE_INV_SHIFT
 	 */
-#define SIZE_INV_SHIFT 21
-#define SIZE_INV(s) (((1 << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1)
+#define	SIZE_INV_SHIFT 21
+#define	SIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1)
 	static const unsigned size_invs[] = {
 	    SIZE_INV(3),
 	    SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7),
@@ -1693,7 +2169,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;
@@ -1718,42 +2194,78 @@ arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
 	if (elm < run->regs_minelm)
 		run->regs_minelm = elm;
 	bit = regind - (elm << (SIZEOF_INT_2POW + 3));
-	assert((run->regs_mask[elm] & (1 << bit)) == 0);
-	run->regs_mask[elm] |= (1 << bit);
+	assert((run->regs_mask[elm] & (1U << bit)) == 0);
+	run->regs_mask[elm] |= (1U << bit);
 #undef SIZE_INV
 #undef SIZE_INV_SHIFT
 }
 
 static void
-arena_run_split(arena_t *arena, arena_run_t *run, size_t size)
+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;
+	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;
 	for (i = 0; i < need_pages; i++) {
-		chunk->map[map_offset + i].npages = need_pages;
-		chunk->map[map_offset + i].pos = 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_UNTOUCHED is cleared below. */
+			}
+		}
+
+		/* 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_FREE;
-		chunk->map[map_offset + rem_pages - 1].npages = rem_pages;
-		chunk->map[map_offset + rem_pages - 1].pos = POS_FREE;
+		/*
+		 * 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;
@@ -1763,14 +2275,13 @@ 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 {
-		chunk = (arena_chunk_t *)chunk_alloc(chunksize);
+		chunk = (arena_chunk_t *)chunk_alloc(chunksize, true);
 		if (chunk == NULL)
 			return (NULL);
 #ifdef MALLOC_STATS
@@ -1786,117 +2297,86 @@ 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.
 		 */
-		chunk->map[arena_chunk_header_npages].npages = chunk_npages -
-		    arena_chunk_header_npages;
-		chunk->map[arena_chunk_header_npages].pos = POS_FREE;
-		chunk->map[chunk_npages - 1].npages = chunk_npages -
-		    arena_chunk_header_npages;
-		chunk->map[chunk_npages - 1].pos = POS_FREE;
+		memset(chunk->map, (CHUNK_MAP_LARGE | CHUNK_MAP_POS_MASK),
+		    arena_chunk_header_npages);
+		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)
+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_FREE) {
-					if (mapelm->npages >= need_npages) {
-						run = (arena_run_t *)
-						    ((uintptr_t)chunk + (i <<
-						    pagesize_2pow));
-						/* Update page map. */
-						arena_run_split(arena, run,
-						    size);
-						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);
 	}
 
 	/*
@@ -1908,84 +2388,229 @@ arena_run_alloc(arena_t *arena, size_t size)
 	run = (arena_run_t *)((uintptr_t)chunk + (arena_chunk_header_npages <<
 	    pagesize_2pow));
 	/* Update page map. */
-	arena_run_split(arena, run, size);
+	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] = (CHUNK_MAP_LARGE |
+					    CHUNK_MAP_POS_MASK);
+					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] = (CHUNK_MAP_LARGE
+						    | CHUNK_MAP_POS_MASK);
+						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);
-
-	/* Try to coalesce with neighboring runs. */
-	if (run_ind > arena_chunk_header_npages &&
-	    chunk->map[run_ind - 1].pos == POS_FREE) {
-		unsigned prev_npages;
+		for (i = 0; i < run_pages; i++) {
+			assert((chunk->map[run_ind + i] & CHUNK_MAP_DIRTY) ==
+			    0);
+			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;
 
-		/* Coalesce with previous run. */
-		prev_npages = chunk->map[run_ind - 1].npages;
-		run_ind -= prev_npages;
-		assert(chunk->map[run_ind].npages == prev_npages);
-		assert(chunk->map[run_ind].pos == POS_FREE);
-		run_pages += prev_npages;
+		for (i = 0; i < run_pages; i++) {
+			chunk->map[run_ind + i] |= (CHUNK_MAP_LARGE |
+			    CHUNK_MAP_POS_MASK);
+		}
+	}
+#endif
 
-		chunk->map[run_ind].npages = run_pages;
-		assert(chunk->map[run_ind].pos == POS_FREE);
-		chunk->map[run_ind + run_pages - 1].npages = run_pages;
-		assert(chunk->map[run_ind + run_pages - 1].pos == POS_FREE);
+	/* 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 {
+		/*
+		 * Coalescing forward failed, so insert nodeB into runs_avail_*.
+		 */
+		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_FREE) {
-		unsigned next_npages;
+	/* 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);
 
-		/* Coalesce with next run. */
-		next_npages = chunk->map[run_ind + run_pages].npages;
-		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_FREE);
+		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);
 
-		chunk->map[run_ind].npages = run_pages;
-		chunk->map[run_ind].pos = POS_FREE;
-		chunk->map[run_ind + run_pages - 1].npages = run_pages;
-		assert(chunk->map[run_ind + run_pages - 1].pos == POS_FREE);
+		arena_chunk_node_dealloc(chunk, 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;
-
 	/* 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 *
@@ -2006,7 +2631,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);
+	run = arena_run_alloc(arena, bin->run_size, true, false);
 	if (run == NULL)
 		return (NULL);
 
@@ -2015,10 +2640,10 @@ arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
 
 	for (i = 0; i < bin->regs_mask_nelms; i++)
 		run->regs_mask[i] = UINT_MAX;
-	remainder = bin->nregs & ((1 << (SIZEOF_INT_2POW + 3)) - 1);
+	remainder = bin->nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1);
 	if (remainder != 0) {
 		/* The last element has spare bits that need to be unset. */
-		run->regs_mask[i] = (UINT_MAX >> ((1 << (SIZEOF_INT_2POW + 3))
+		run->regs_mask[i] = (UINT_MAX >> ((1U << (SIZEOF_INT_2POW + 3))
 		    - remainder));
 	}
 
@@ -2085,7 +2710,6 @@ arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size)
 	size_t try_run_size, good_run_size;
 	unsigned good_nregs, good_mask_nelms, good_reg0_offset;
 	unsigned try_nregs, try_mask_nelms, try_reg0_offset;
-	float max_ovrhd = RUN_MAX_OVRHD;
 
 	assert(min_run_size >= pagesize);
 	assert(min_run_size <= arena_maxclass);
@@ -2103,11 +2727,11 @@ arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size)
 	 */
 	try_run_size = min_run_size;
 	try_nregs = ((try_run_size - sizeof(arena_run_t)) / bin->reg_size)
-	    + 1; /* Counter-act the first line of the loop. */
+	    + 1; /* Counter-act try_nregs-- in loop. */
 	do {
 		try_nregs--;
 		try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) +
-		    ((try_nregs & ((1 << (SIZEOF_INT_2POW + 3)) - 1)) ? 1 : 0);
+		    ((try_nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1)) ? 1 : 0);
 		try_reg0_offset = try_run_size - (try_nregs * bin->reg_size);
 	} while (sizeof(arena_run_t) + (sizeof(unsigned) * (try_mask_nelms - 1))
 	    > try_reg0_offset);
@@ -2129,16 +2753,15 @@ arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size)
 		do {
 			try_nregs--;
 			try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) +
-			    ((try_nregs & ((1 << (SIZEOF_INT_2POW + 3)) - 1)) ?
+			    ((try_nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1)) ?
 			    1 : 0);
 			try_reg0_offset = try_run_size - (try_nregs *
 			    bin->reg_size);
 		} while (sizeof(arena_run_t) + (sizeof(unsigned) *
 		    (try_mask_nelms - 1)) > try_reg0_offset);
 	} while (try_run_size <= arena_maxclass && try_run_size <= RUN_MAX_SMALL
-	    && max_ovrhd > RUN_MAX_OVRHD_RELAX / ((float)(bin->reg_size << 3))
-	    && ((float)(try_reg0_offset)) / ((float)(try_run_size)) >
-	    max_ovrhd);
+	    && RUN_MAX_OVRHD * (bin->reg_size << 3) > RUN_MAX_OVRHD_RELAX
+	    && (try_reg0_offset << RUN_BFP) > RUN_MAX_OVRHD * try_run_size);
 
 	assert(sizeof(arena_run_t) + (sizeof(unsigned) * (good_mask_nelms - 1))
 	    <= good_reg0_offset);
@@ -2153,107 +2776,185 @@ arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size)
 	return (good_run_size);
 }
 
-static void *
-arena_malloc(arena_t *arena, size_t size)
+#ifdef MALLOC_BALANCE
+static inline void
+arena_lock_balance(arena_t *arena)
 {
-	void *ret;
-
-	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;
+	unsigned contention;
 
-		/* Small allocation. */
+	contention = malloc_spin_lock(&arena->lock);
+	if (narenas > 1) {
+		/*
+		 * Calculate the exponentially averaged contention for this
+		 * arena.  Due to integer math always rounding down, this value
+		 * decays somewhat faster then normal.
+		 */
+		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)
+			arena_lock_balance_hard(arena);
+	}
+}
 
-		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 < (1 << TINY_MIN_2POW))
-				size = (1 << 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);
+static void
+arena_lock_balance_hard(arena_t *arena)
+{
+	uint32_t ind;
 
-		malloc_mutex_lock(&arena->mtx);
-		if ((run = bin->runcur) != NULL && run->nfree > 0)
-			ret = arena_bin_malloc_easy(arena, bin, run);
+	arena->contention = 0;
+#ifdef MALLOC_STATS
+	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
-			ret = arena_bin_malloc_hard(arena, bin);
+			arenas_map = arenas_extend(ind);
+		malloc_spin_unlock(&arenas_lock);
+	}
+}
+#endif
 
-		if (ret == NULL) {
-			malloc_mutex_unlock(&arena->mtx);
-			return (NULL);
-		}
+static inline void *
+arena_malloc_small(arena_t *arena, size_t size, bool zero)
+{
+	void *ret;
+	arena_bin_t *bin;
+	arena_run_t *run;
 
-#ifdef MALLOC_STATS
-		bin->stats.nrequests++;
-		arena->stats.nmalloc_small++;
-		arena->stats.allocated_small += size;
+	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 {
-		/* Large allocation. */
-		size = PAGE_CEILING(size);
-		malloc_mutex_lock(&arena->mtx);
-		ret = (void *)arena_run_alloc(arena, size);
-		if (ret == NULL) {
-			malloc_mutex_unlock(&arena->mtx);
-			return (NULL);
-		}
-#ifdef MALLOC_STATS
-		arena->stats.nmalloc_large++;
-		arena->stats.allocated_large += size;
+		/* 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);
+#else
+	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 (ret == NULL) {
+		malloc_spin_unlock(&arena->lock);
+		return (NULL);
 	}
 
-	malloc_mutex_unlock(&arena->mtx);
+#ifdef MALLOC_STATS
+	bin->stats.nrequests++;
+	arena->stats.nmalloc_small++;
+	arena->stats.allocated_small += size;
+#endif
+	malloc_spin_unlock(&arena->lock);
 
-	if (opt_junk)
-		memset(ret, 0xa5, size);
-	else if (opt_zero)
+	if (zero == false) {
+		if (opt_junk)
+			memset(ret, 0xa5, size);
+		else if (opt_zero)
+			memset(ret, 0, size);
+	} else
 		memset(ret, 0, size);
+
 	return (ret);
 }
 
-static inline void
-arena_palloc_trim(arena_t *arena, arena_chunk_t *chunk, unsigned pageind,
-    unsigned npages)
+static void *
+arena_malloc_large(arena_t *arena, size_t size, bool zero)
 {
-	unsigned i;
+	void *ret;
 
-	assert(npages > 0);
+	/* Large allocation. */
+	size = PAGE_CEILING(size);
+#ifdef MALLOC_BALANCE
+	arena_lock_balance(arena);
+#else
+	malloc_spin_lock(&arena->lock);
+#endif
+	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;
+#endif
+	malloc_spin_unlock(&arena->lock);
 
-	/*
-	 * 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;
+	if (zero == false) {
+		if (opt_junk)
+			memset(ret, 0xa5, size);
+		else if (opt_zero)
+			memset(ret, 0, size);
 	}
-	arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)chunk + (pageind <<
-	    pagesize_2pow)), npages << pagesize_2pow);
+
+	return (ret);
+}
+
+static inline void *
+arena_malloc(arena_t *arena, size_t size, bool zero)
+{
+
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+	assert(size != 0);
+	assert(QUANTUM_CEILING(size) <= arena_maxclass);
+
+	if (size <= bin_maxclass) {
+		return (arena_malloc_small(arena, size, zero));
+	} else
+		return (arena_malloc_large(arena, size, zero));
+}
+
+static inline void *
+imalloc(size_t size)
+{
+
+	assert(size != 0);
+
+	if (size <= arena_maxclass)
+		return (arena_malloc(choose_arena(), size, false));
+	else
+		return (huge_malloc(size, false));
+}
+
+static inline void *
+icalloc(size_t size)
+{
+
+	if (size <= arena_maxclass)
+		return (arena_malloc(choose_arena(), size, true));
+	else
+		return (huge_malloc(size, true));
 }
 
 /* Only handles large allocations that require more than page alignment. */
@@ -2263,17 +2964,19 @@ 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;
-
-	malloc_mutex_lock(&arena->mtx);
-	ret = (void *)arena_run_alloc(arena, alloc_size);
+#ifdef MALLOC_BALANCE
+	arena_lock_balance(arena);
+#else
+	malloc_spin_lock(&arena->lock);
+#endif
+	ret = (void *)arena_run_alloc(arena, alloc_size, false, false);
 	if (ret == NULL) {
-		malloc_mutex_unlock(&arena->mtx);
+		malloc_spin_unlock(&arena->lock);
 		return (NULL);
 	}
 
@@ -2283,42 +2986,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;
 
+		/*
+		 * 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);
+
 		leadsize = alignment - offset;
-		ret = (void *)((uintptr_t)ret + leadsize);
-		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;
-			chunk->map[pageind + i].pos = i;
+		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);
 		}
 	}
 
@@ -2326,7 +3027,7 @@ arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size)
 	arena->stats.nmalloc_large++;
 	arena->stats.allocated_large += size;
 #endif
-	malloc_mutex_unlock(&arena->mtx);
+	malloc_spin_unlock(&arena->lock);
 
 	if (opt_junk)
 		memset(ret, 0xa5, size);
@@ -2335,96 +3036,280 @@ arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size)
 	return (ret);
 }
 
+static inline void *
+ipalloc(size_t alignment, size_t size)
+{
+	void *ret;
+	size_t ceil_size;
+
+	/*
+	 * Round size up to the nearest multiple of alignment.
+	 *
+	 * This done, we can take advantage of the fact that for each small
+	 * size class, every object is aligned at the smallest power of two
+	 * that is non-zero in the base two representation of the size.  For
+	 * example:
+	 *
+	 *   Size |   Base 2 | Minimum alignment
+	 *   -----+----------+------------------
+	 *     96 |  1100000 |  32
+	 *    144 | 10100000 |  32
+	 *    192 | 11000000 |  64
+	 *
+	 * Depending on runtime settings, it is possible that arena_malloc()
+	 * will further round up to a power of two, but that never causes
+	 * correctness issues.
+	 */
+	ceil_size = (size + (alignment - 1)) & (-alignment);
+	/*
+	 * (ceil_size < size) protects against the combination of maximal
+	 * alignment and size greater than maximal alignment.
+	 */
+	if (ceil_size < size) {
+		/* size_t overflow. */
+		return (NULL);
+	}
+
+	if (ceil_size <= pagesize || (alignment <= pagesize
+	    && ceil_size <= arena_maxclass))
+		ret = arena_malloc(choose_arena(), ceil_size, false);
+	else {
+		size_t run_size;
+
+		/*
+		 * We can't achieve sub-page alignment, so round up alignment
+		 * permanently; it makes later calculations simpler.
+		 */
+		alignment = PAGE_CEILING(alignment);
+		ceil_size = PAGE_CEILING(size);
+		/*
+		 * (ceil_size < size) protects against very large sizes within
+		 * pagesize of SIZE_T_MAX.
+		 *
+		 * (ceil_size + alignment < ceil_size) protects against the
+		 * combination of maximal alignment and ceil_size large enough
+		 * to cause overflow.  This is similar to the first overflow
+		 * check above, but it needs to be repeated due to the new
+		 * ceil_size value, which may now be *equal* to maximal
+		 * alignment, whereas before we only detected overflow if the
+		 * original size was *greater* than maximal alignment.
+		 */
+		if (ceil_size < size || ceil_size + alignment < ceil_size) {
+			/* size_t overflow. */
+			return (NULL);
+		}
+
+		/*
+		 * Calculate the size of the over-size run that arena_palloc()
+		 * would need to allocate in order to guarantee the alignment.
+		 */
+		if (ceil_size >= alignment)
+			run_size = ceil_size + alignment - pagesize;
+		else {
+			/*
+			 * It is possible that (alignment << 1) will cause
+			 * overflow, but it doesn't matter because we also
+			 * subtract pagesize, which in the case of overflow
+			 * leaves us with a very large run_size.  That causes
+			 * the first conditional below to fail, which means
+			 * that the bogus run_size value never gets used for
+			 * anything important.
+			 */
+			run_size = (alignment << 1) - pagesize;
+		}
+
+		if (run_size <= arena_maxclass) {
+			ret = arena_palloc(choose_arena(), alignment, ceil_size,
+			    run_size);
+		} else if (alignment <= chunksize)
+			ret = huge_malloc(ceil_size, false);
+		else
+			ret = huge_palloc(alignment, ceil_size);
+	}
+
+	assert(((uintptr_t)ret & (alignment - 1)) == 0);
+	return (ret);
+}
+
 /* Return the size of the allocation pointed to by ptr. */
 static size_t
 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) == 0) {
 		arena_run_t *run;
 
-		pageind -= mapelm->pos;
-
+		/* Small allocation size is in the run header. */
+		pageind -= (mapelm & CHUNK_MAP_POS_MASK);
 		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(void *ptr, size_t size, size_t oldsize)
+static inline size_t
+isalloc(const void *ptr)
 {
-	void *ret;
+	size_t ret;
+	arena_chunk_t *chunk;
 
-	/* Avoid moving the allocation if the size class would not change. */
-	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;
-	} 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;
+	assert(ptr != NULL);
+
+	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
+	if (chunk != ptr) {
+		/* Region. */
+		assert(chunk->arena->magic == ARENA_MAGIC);
+
+		ret = arena_salloc(ptr);
 	} else {
+		extent_node_t *node, key;
+
+		/* Chunk (huge allocation). */
+
+		malloc_mutex_lock(&huge_mtx);
+
+		/* Extract from tree of huge allocations. */
+		key.addr = __DECONST(void *, ptr);
+		node = RB_FIND(extent_tree_ad_s, &huge, &key);
+		assert(node != NULL);
+
+		ret = node->size;
+
+		malloc_mutex_unlock(&huge_mtx);
+	}
+
+	return (ret);
+}
+
+static inline void
+arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
+    size_t pageind, arena_chunk_map_t mapelm)
+{
+	arena_run_t *run;
+	arena_bin_t *bin;
+	size_t size;
+
+	pageind -= (mapelm & CHUNK_MAP_POS_MASK);
+
+	run = (arena_run_t *)((uintptr_t)chunk + (pageind << pagesize_2pow));
+	assert(run->magic == ARENA_RUN_MAGIC);
+	bin = run->bin;
+	size = bin->reg_size;
+
+	if (opt_junk)
+		memset(ptr, 0x5a, size);
+
+	arena_run_reg_dalloc(run, bin, ptr, size);
+	run->nfree++;
+
+	if (run->nfree == bin->nregs) {
+		/* Deallocate run. */
+		if (run == bin->runcur)
+			bin->runcur = NULL;
+		else if (bin->nregs != 1) {
+			/*
+			 * This block's conditional is necessary because if the
+			 * run only contains one region, then it never gets
+			 * inserted into the non-full runs tree.
+			 */
+			RB_REMOVE(arena_run_tree_s, &bin->runs, run);
+		}
+#ifdef MALLOC_DEBUG
+		run->magic = 0;
+#endif
+		arena_run_dalloc(arena, run, true);
+#ifdef MALLOC_STATS
+		bin->stats.curruns--;
+#endif
+	} else if (run->nfree == 1 && run != bin->runcur) {
 		/*
-		 * We make no attempt to resize runs here, though it would be
-		 * possible to do so.
+		 * Make sure that bin->runcur always refers to the lowest
+		 * non-full run, if one exists.
 		 */
-		if (oldsize > small_max && PAGE_CEILING(size) == oldsize)
-			goto IN_PLACE;
+		if (bin->runcur == NULL)
+			bin->runcur = run;
+		else if ((uintptr_t)run < (uintptr_t)bin->runcur) {
+			/* Switch runcur. */
+			if (bin->runcur->nfree > 0) {
+				/* Insert runcur. */
+				RB_INSERT(arena_run_tree_s, &bin->runs,
+				    bin->runcur);
+			}
+			bin->runcur = run;
+		} else
+			RB_INSERT(arena_run_tree_s, &bin->runs, run);
 	}
+#ifdef MALLOC_STATS
+	arena->stats.allocated_small -= size;
+	arena->stats.ndalloc_small++;
+#endif
+}
 
-	/*
-	 * 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.
-	 */
-	ret = arena_malloc(choose_arena(), size);
-	if (ret == NULL)
-		return (NULL);
+static void
+arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr)
+{
+	/* Large allocation. */
+	malloc_spin_lock(&arena->lock);
 
-	/* Junk/zero-filling were already done by arena_malloc(). */
-	if (size < oldsize)
-		memcpy(ret, ptr, size);
-	else
-		memcpy(ret, ptr, oldsize);
-	idalloc(ptr);
-	return (ret);
-IN_PLACE:
-	if (opt_junk && size < oldsize)
-		memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size);
-	else if (opt_zero && size > oldsize)
-		memset((void *)((uintptr_t)ptr + oldsize), 0, size - oldsize);
-	return (ptr);
+#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 void
+static inline void
 arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
 {
-	unsigned pageind;
+	size_t pageind;
 	arena_chunk_map_t *mapelm;
-	size_t size;
 
 	assert(arena != NULL);
 	assert(arena->magic == ARENA_MAGIC);
@@ -2434,88 +3319,222 @@ 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)) {
-		arena_run_t *run;
-		arena_bin_t *bin;
-
+	if ((*mapelm & CHUNK_MAP_LARGE) == 0) {
 		/* Small allocation. */
+		malloc_spin_lock(&arena->lock);
+		arena_dalloc_small(arena, chunk, ptr, pageind, *mapelm);
+		malloc_spin_unlock(&arena->lock);
+	} else {
+		assert((*mapelm & CHUNK_MAP_POS_MASK) == 0);
+		arena_dalloc_large(arena, chunk, ptr);
+	}
+}
 
-		pageind -= mapelm->pos;
+static inline void
+idalloc(void *ptr)
+{
+	arena_chunk_t *chunk;
 
-		run = (arena_run_t *)((uintptr_t)chunk + (pageind <<
-		    pagesize_2pow));
-		assert(run->magic == ARENA_RUN_MAGIC);
-		bin = run->bin;
-		size = bin->reg_size;
+	assert(ptr != NULL);
 
-		if (opt_junk)
-			memset(ptr, 0x5a, size);
+	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
+	if (chunk != ptr)
+		arena_dalloc(chunk->arena, chunk, ptr);
+	else
+		huge_dalloc(ptr);
+}
 
-		malloc_mutex_lock(&arena->mtx);
-		arena_run_reg_dalloc(run, bin, ptr, size);
-		run->nfree++;
+static void
+arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr,
+    size_t size, size_t oldsize)
+{
+	extent_node_t *node, key;
 
-		if (run->nfree == bin->nregs) {
-			/* Deallocate run. */
-			if (run == bin->runcur)
-				bin->runcur = NULL;
-			else if (bin->nregs != 1) {
-				/*
-				 * This block's conditional is necessary because
-				 * if the run only contains one region, then it
-				 * never gets inserted into the non-full runs
-				 * tree.
-				 */
-				RB_REMOVE(arena_run_tree_s, &bin->runs, run);
-			}
-#ifdef MALLOC_DEBUG
-			run->magic = 0;
+	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
-			arena_run_dalloc(arena, run, bin->run_size);
+	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
-			bin->stats.curruns--;
+	arena->stats.allocated_large -= oldsize - size;
 #endif
-		} else if (run->nfree == 1 && run != bin->runcur) {
-			/*
-			 * Make sure that bin->runcur always refers to the
-			 * lowest non-full run, if one exists.
-			 */
-			if (bin->runcur == NULL)
-				bin->runcur = run;
-			else if ((uintptr_t)run < (uintptr_t)bin->runcur) {
-				/* Switch runcur. */
-				if (bin->runcur->nfree > 0) {
-					/* Insert runcur. */
-					RB_INSERT(arena_run_tree_s, &bin->runs,
-					    bin->runcur);
-				}
-				bin->runcur = run;
-			} else
-				RB_INSERT(arena_run_tree_s, &bin->runs, run);
-		}
-#ifdef MALLOC_STATS
-		arena->stats.allocated_small -= size;
-		arena->stats.ndalloc_small++;
+	malloc_spin_unlock(&arena->lock);
+}
+
+static bool
+arena_ralloc_large_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
-	} else {
-		/* Large allocation. */
+	nodeC = RB_FIND(extent_tree_ad_s, &arena->runs_avail_ad, &key);
+	if (nodeC != NULL && oldsize + nodeC->size >= size) {
+		extent_node_t *nodeA, *nodeB;
 
-		size = mapelm->npages << pagesize_2pow;
-		assert((((uintptr_t)ptr) & pagesize_mask) == 0);
+		/*
+		 * 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);
 
-		if (opt_junk)
-			memset(ptr, 0x5a, size);
+		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);
 
-		malloc_mutex_lock(&arena->mtx);
-		arena_run_dalloc(arena, (arena_run_t *)ptr, size);
 #ifdef MALLOC_STATS
-		arena->stats.allocated_large -= size;
-		arena->stats.ndalloc_large++;
+		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_large(void *ptr, size_t size, size_t oldsize)
+{
+	size_t psize;
+
+	psize = PAGE_CEILING(size);
+	if (psize == oldsize) {
+		/* Same size class. */
+		if (opt_junk && size < oldsize) {
+			memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize -
+			    size);
+		}
+		return (false);
+	} else {
+		arena_chunk_t *chunk;
+		arena_t *arena;
+
+		chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
+		arena = chunk->arena;
+		assert(arena->magic == ARENA_MAGIC);
+
+		if (psize < oldsize) {
+			/* Fill before shrinking in order avoid a race. */
+			if (opt_junk) {
+				memset((void *)((uintptr_t)ptr + size), 0x5a,
+				    oldsize - size);
+			}
+			arena_ralloc_large_shrink(arena, chunk, ptr, psize,
+			    oldsize);
+			return (false);
+		} else {
+			bool ret = arena_ralloc_large_grow(arena, chunk, ptr,
+			    psize, oldsize);
+			if (ret == false && opt_zero) {
+				memset((void *)((uintptr_t)ptr + oldsize), 0,
+				    size - oldsize);
+			}
+			return (ret);
+		}
+	}
+}
+
+static void *
+arena_ralloc(void *ptr, size_t size, size_t oldsize)
+{
+	void *ret;
+	size_t copysize;
+
+	/* 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; /* 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; /* 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) {
+		assert(size > bin_maxclass);
+		if (arena_ralloc_large(ptr, size, oldsize) == false)
+			return (ptr);
 	}
 
-	malloc_mutex_unlock(&arena->mtx);
+	/*
+	 * If we get here, then size and oldsize are different enough that we
+	 * 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)
+		return (NULL);
+
+	/* Junk/zero-filling were already done by arena_malloc(). */
+	copysize = (size < oldsize) ? size : oldsize;
+	memcpy(ret, ptr, copysize);
+	idalloc(ptr);
+	return (ret);
+IN_PLACE:
+	if (opt_junk && size < oldsize)
+		memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size);
+	else if (opt_zero && size > oldsize)
+		memset((void *)((uintptr_t)ptr + oldsize), 0, size - oldsize);
+	return (ptr);
+}
+
+static inline void *
+iralloc(void *ptr, size_t size)
+{
+	size_t oldsize;
+
+	assert(ptr != NULL);
+	assert(size != 0);
+
+	oldsize = isalloc(ptr);
+
+	if (size <= arena_maxclass)
+		return (arena_ralloc(ptr, size, oldsize));
+	else
+		return (huge_ralloc(ptr, size, oldsize));
 }
 
 static bool
@@ -2525,7 +3544,8 @@ arena_new(arena_t *arena)
 	arena_bin_t *bin;
 	size_t pow2_size, prev_run_size;
 
-	malloc_mutex_init(&arena->mtx);
+	if (malloc_spin_init(&arena->lock))
+		return (true);
 
 #ifdef MALLOC_STATS
 	memset(&arena->stats, 0, sizeof(arena_stats_t));
@@ -2535,6 +3555,16 @@ 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
+
 	/* Initialize bins. */
 	prev_run_size = pagesize;
 
@@ -2544,7 +3574,7 @@ arena_new(arena_t *arena)
 		bin->runcur = NULL;
 		RB_INIT(&bin->runs);
 
-		bin->reg_size = (1 << (TINY_MIN_2POW + i));
+		bin->reg_size = (1U << (TINY_MIN_2POW + i));
 
 		prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
 
@@ -2629,11 +3659,11 @@ arenas_extend(unsigned ind)
  */
 
 static void *
-huge_malloc(size_t size)
+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. */
 
@@ -2643,33 +3673,35 @@ huge_malloc(size_t size)
 		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);
+	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(&chunks_mtx);
-	RB_INSERT(chunk_tree_s, &huge, node);
+	malloc_mutex_lock(&huge_mtx);
+	RB_INSERT(extent_tree_ad_s, &huge, node);
 #ifdef MALLOC_STATS
 	huge_nmalloc++;
 	huge_allocated += csize;
 #endif
-	malloc_mutex_unlock(&chunks_mtx);
+	malloc_mutex_unlock(&huge_mtx);
 
-	if (opt_junk)
-		memset(ret, 0xa5, csize);
-	else if (opt_zero)
-		memset(ret, 0, csize);
+	if (zero == false) {
+		if (opt_junk)
+			memset(ret, 0xa5, csize);
+		else if (opt_zero)
+			memset(ret, 0, csize);
+	}
 
 	return (ret);
 }
@@ -2680,7 +3712,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
@@ -2699,14 +3731,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);
+	ret = chunk_alloc(alloc_size, false);
 	if (ret == NULL) {
-		base_chunk_node_dealloc(node);
+		base_node_dealloc(node);
 		return (NULL);
 	}
 
@@ -2735,16 +3767,16 @@ 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(&chunks_mtx);
-	RB_INSERT(chunk_tree_s, &huge, node);
+	malloc_mutex_lock(&huge_mtx);
+	RB_INSERT(extent_tree_ad_s, &huge, node);
 #ifdef MALLOC_STATS
 	huge_nmalloc++;
 	huge_allocated += chunk_size;
 #endif
-	malloc_mutex_unlock(&chunks_mtx);
+	malloc_mutex_unlock(&huge_mtx);
 
 	if (opt_junk)
 		memset(ret, 0xa5, chunk_size);
@@ -2758,6 +3790,7 @@ static void *
 huge_ralloc(void *ptr, size_t size, size_t oldsize)
 {
 	void *ret;
+	size_t copysize;
 
 	/* Avoid moving the allocation if the size class would not change. */
 	if (oldsize > arena_maxclass &&
@@ -2777,21 +3810,12 @@ huge_ralloc(void *ptr, size_t size, size_t oldsize)
 	 * need to use a different size class.  In that case, fall back to
 	 * allocating new space and copying.
 	 */
-	ret = huge_malloc(size);
+	ret = huge_malloc(size, false);
 	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);
-		memcpy(ret, ptr, oldsize);
-	}
+	copysize = (size < oldsize) ? size : oldsize;
+	memcpy(ret, ptr, copysize);
 	idalloc(ptr);
 	return (ret);
 }
@@ -2799,249 +3823,32 @@ 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(&chunks_mtx);
+	malloc_mutex_lock(&huge_mtx);
 
 	/* Extract from tree of huge allocations. */
-	key.chunk = ptr;
-	node = RB_FIND(chunk_tree_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_s, &huge, node);
+	assert(node->addr == ptr);
+	RB_REMOVE(extent_tree_ad_s, &huge, node);
 
 #ifdef MALLOC_STATS
 	huge_ndalloc++;
 	huge_allocated -= node->size;
 #endif
 
-	malloc_mutex_unlock(&chunks_mtx);
+	malloc_mutex_unlock(&huge_mtx);
 
 	/* Unmap chunk. */
-#ifdef USE_BRK
-	if (opt_junk)
-		memset(node->chunk, 0x5a, node->size);
-#endif
-	chunk_dealloc(node->chunk, node->size);
-
-	base_chunk_node_dealloc(node);
-}
-
-static void *
-imalloc(size_t size)
-{
-	void *ret;
-
-	assert(size != 0);
-
-	if (size <= arena_maxclass)
-		ret = arena_malloc(choose_arena(), size);
-	else
-		ret = huge_malloc(size);
-
-	return (ret);
-}
-
-static void *
-ipalloc(size_t alignment, size_t size)
-{
-	void *ret;
-	size_t ceil_size;
-
-	/*
-	 * Round size up to the nearest multiple of alignment.
-	 *
-	 * This done, we can take advantage of the fact that for each small
-	 * size class, every object is aligned at the smallest power of two
-	 * that is non-zero in the base two representation of the size.  For
-	 * example:
-	 *
-	 *   Size |   Base 2 | Minimum alignment
-	 *   -----+----------+------------------
-	 *     96 |  1100000 |  32
-	 *    144 | 10100000 |  32
-	 *    192 | 11000000 |  64
-	 *
-	 * Depending on runtime settings, it is possible that arena_malloc()
-	 * will further round up to a power of two, but that never causes
-	 * correctness issues.
-	 */
-	ceil_size = (size + (alignment - 1)) & (-alignment);
-	/*
-	 * (ceil_size < size) protects against the combination of maximal
-	 * alignment and size greater than maximal alignment.
-	 */
-	if (ceil_size < size) {
-		/* size_t overflow. */
-		return (NULL);
-	}
-
-	if (ceil_size <= pagesize || (alignment <= pagesize
-	    && ceil_size <= arena_maxclass))
-		ret = arena_malloc(choose_arena(), ceil_size);
-	else {
-		size_t run_size;
-
-		/*
-		 * We can't achieve sub-page alignment, so round up alignment
-		 * permanently; it makes later calculations simpler.
-		 */
-		alignment = PAGE_CEILING(alignment);
-		ceil_size = PAGE_CEILING(size);
-		/*
-		 * (ceil_size < size) protects against very large sizes within
-		 * pagesize of SIZE_T_MAX.
-		 *
-		 * (ceil_size + alignment < ceil_size) protects against the
-		 * combination of maximal alignment and ceil_size large enough
-		 * to cause overflow.  This is similar to the first overflow
-		 * check above, but it needs to be repeated due to the new
-		 * ceil_size value, which may now be *equal* to maximal
-		 * alignment, whereas before we only detected overflow if the
-		 * original size was *greater* than maximal alignment.
-		 */
-		if (ceil_size < size || ceil_size + alignment < ceil_size) {
-			/* size_t overflow. */
-			return (NULL);
-		}
-
-		/*
-		 * Calculate the size of the over-size run that arena_palloc()
-		 * would need to allocate in order to guarantee the alignment.
-		 */
-		if (ceil_size >= alignment)
-			run_size = ceil_size + alignment - pagesize;
-		else {
-			/*
-			 * It is possible that (alignment << 1) will cause
-			 * overflow, but it doesn't matter because we also
-			 * subtract pagesize, which in the case of overflow
-			 * leaves us with a very large run_size.  That causes
-			 * the first conditional below to fail, which means
-			 * that the bogus run_size value never gets used for
-			 * anything important.
-			 */
-			run_size = (alignment << 1) - pagesize;
-		}
-
-		if (run_size <= arena_maxclass) {
-			ret = arena_palloc(choose_arena(), alignment, ceil_size,
-			    run_size);
-		} else if (alignment <= chunksize)
-			ret = huge_malloc(ceil_size);
-		else
-			ret = huge_palloc(alignment, ceil_size);
-	}
-
-	assert(((uintptr_t)ret & (alignment - 1)) == 0);
-	return (ret);
-}
-
-static void *
-icalloc(size_t size)
-{
-	void *ret;
-
-	if (size <= arena_maxclass) {
-		ret = arena_malloc(choose_arena(), size);
-		if (ret == NULL)
-			return (NULL);
-		memset(ret, 0, size);
-	} else {
-		/*
-		 * The virtual memory system provides zero-filled pages, so
-		 * there is no need to do so manually, unless opt_junk is
-		 * enabled, in which case huge_malloc() fills huge allocations
-		 * with junk.
-		 */
-		ret = huge_malloc(size);
-		if (ret == NULL)
-			return (NULL);
-
-		if (opt_junk)
-			memset(ret, 0, size);
-#ifdef USE_BRK
-		else if ((uintptr_t)ret >= (uintptr_t)brk_base
-		    && (uintptr_t)ret < (uintptr_t)brk_max) {
-			/*
-			 * This may be a re-used brk chunk.  Therefore, zero
-			 * the memory.
-			 */
-			memset(ret, 0, size);
-		}
+#ifdef MALLOC_DSS
+	if (opt_dss && opt_junk)
+		memset(node->addr, 0x5a, node->size);
 #endif
-	}
+	chunk_dealloc(node->addr, node->size);
 
-	return (ret);
-}
-
-static size_t
-isalloc(const void *ptr)
-{
-	size_t ret;
-	arena_chunk_t *chunk;
-
-	assert(ptr != NULL);
-
-	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
-	if (chunk != ptr) {
-		/* Region. */
-		assert(chunk->arena->magic == ARENA_MAGIC);
-
-		ret = arena_salloc(ptr);
-	} else {
-		chunk_node_t *node, key;
-
-		/* Chunk (huge allocation). */
-
-		malloc_mutex_lock(&chunks_mtx);
-
-		/* Extract from tree of huge allocations. */
-		key.chunk = __DECONST(void *, ptr);
-		node = RB_FIND(chunk_tree_s, &huge, &key);
-		assert(node != NULL);
-
-		ret = node->size;
-
-		malloc_mutex_unlock(&chunks_mtx);
-	}
-
-	return (ret);
-}
-
-static void *
-iralloc(void *ptr, size_t size)
-{
-	void *ret;
-	size_t oldsize;
-
-	assert(ptr != NULL);
-	assert(size != 0);
-
-	oldsize = isalloc(ptr);
-
-	if (size <= arena_maxclass)
-		ret = arena_ralloc(ptr, size, oldsize);
-	else
-		ret = huge_ralloc(ptr, size, oldsize);
-
-	return (ret);
-}
-
-static void
-idalloc(void *ptr)
-{
-	arena_chunk_t *chunk;
-
-	assert(ptr != NULL);
-
-	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
-	if (chunk != ptr) {
-		/* Region. */
-		arena_dalloc(chunk->arena, chunk, ptr);
-	} else
-		huge_dalloc(ptr);
+	base_node_dealloc(node);
 }
 
 static void
@@ -3060,9 +3867,14 @@ malloc_print_stats(void)
 #endif
 		    "\n", "");
 		_malloc_message("Boolean MALLOC_OPTIONS: ",
-		    opt_abort ? "A" : "a",
-		    opt_junk ? "J" : "j",
-		    opt_hint ? "H" : "h");
+		    opt_abort ? "A" : "a", "", "");
+#ifdef MALLOC_DSS
+		_malloc_message(opt_dss ? "D" : "d", "", "", "");
+#endif
+		_malloc_message(opt_junk ? "J" : "j", "", "", "");
+#ifdef MALLOC_DSS
+		_malloc_message(opt_mmap ? "M" : "m", "", "", "");
+#endif
 		_malloc_message(opt_utrace ? "PU" : "Pu",
 		    opt_sysv ? "V" : "v",
 		    opt_xmalloc ? "X" : "x",
@@ -3070,11 +3882,17 @@ malloc_print_stats(void)
 
 		_malloc_message("CPUs: ", umax2s(ncpus, s), "\n", "");
 		_malloc_message("Max arenas: ", umax2s(narenas, s), "\n", "");
+#ifdef MALLOC_BALANCE
+		_malloc_message("Arena balance threshold: ",
+		    umax2s(opt_balance_threshold, s), "\n", "");
+#endif
 		_malloc_message("Pointer size: ", umax2s(sizeof(void *), s),
 		    "\n", "");
 		_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", "");
@@ -3082,6 +3900,9 @@ malloc_print_stats(void)
 #ifdef MALLOC_STATS
 		{
 			size_t allocated, mapped;
+#ifdef MALLOC_BALANCE
+			uint64_t nbalance = 0;
+#endif
 			unsigned i;
 			arena_t *arena;
 
@@ -3090,20 +3911,23 @@ malloc_print_stats(void)
 			/* arenas. */
 			for (i = 0, allocated = 0; i < narenas; i++) {
 				if (arenas[i] != NULL) {
-					malloc_mutex_lock(&arenas[i]->mtx);
+					malloc_spin_lock(&arenas[i]->lock);
 					allocated +=
 					    arenas[i]->stats.allocated_small;
 					allocated +=
 					    arenas[i]->stats.allocated_large;
-					malloc_mutex_unlock(&arenas[i]->mtx);
+#ifdef MALLOC_BALANCE
+					nbalance += arenas[i]->stats.nbalance;
+#endif
+					malloc_spin_unlock(&arenas[i]->lock);
 				}
 			}
 
 			/* huge/base. */
-			malloc_mutex_lock(&chunks_mtx);
+			malloc_mutex_lock(&huge_mtx);
 			allocated += huge_allocated;
 			mapped = stats_chunks.curchunks * chunksize;
-			malloc_mutex_unlock(&chunks_mtx);
+			malloc_mutex_unlock(&huge_mtx);
 
 			malloc_mutex_lock(&base_mtx);
 			mapped += base_mapped;
@@ -3112,13 +3936,18 @@ malloc_print_stats(void)
 			malloc_printf("Allocated: %zu, mapped: %zu\n",
 			    allocated, mapped);
 
+#ifdef MALLOC_BALANCE
+			malloc_printf("Arena balance reassignments: %llu\n",
+			    nbalance);
+#endif
+
 			/* Print chunk stats. */
 			{
 				chunk_stats_t chunks_stats;
 
-				malloc_mutex_lock(&chunks_mtx);
+				malloc_mutex_lock(&huge_mtx);
 				chunks_stats = stats_chunks;
-				malloc_mutex_unlock(&chunks_mtx);
+				malloc_mutex_unlock(&huge_mtx);
 
 				malloc_printf("chunks: nchunks   "
 				    "highchunks    curchunks\n");
@@ -3132,8 +3961,7 @@ malloc_print_stats(void)
 			malloc_printf(
 			    "huge: nmalloc      ndalloc    allocated\n");
 			malloc_printf(" %12llu %12llu %12zu\n",
-			    huge_nmalloc, huge_ndalloc, huge_allocated
-			    * chunksize);
+			    huge_nmalloc, huge_ndalloc, huge_allocated);
 
 			/* Print stats for each arena. */
 			for (i = 0; i < narenas; i++) {
@@ -3141,9 +3969,9 @@ malloc_print_stats(void)
 				if (arena != NULL) {
 					malloc_printf(
 					    "\narenas[%u]:\n", i);
-					malloc_mutex_lock(&arena->mtx);
+					malloc_spin_lock(&arena->lock);
 					stats_print(arena);
-					malloc_mutex_unlock(&arena->mtx);
+					malloc_spin_unlock(&arena->lock);
 				}
 			}
 		}
@@ -3170,7 +3998,7 @@ malloc_init(void)
 static bool
 malloc_init_hard(void)
 {
-	unsigned i, j;
+	unsigned i;
 	int linklen;
 	char buf[PATH_MAX + 1];
 	const char *opts;
@@ -3205,7 +4033,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
@@ -3217,6 +4045,8 @@ malloc_init_hard(void)
 	}
 
 	for (i = 0; i < 3; i++) {
+		unsigned j;
+
 		/* Get runtime configuration. */
 		switch (i) {
 		case 0:
@@ -3250,10 +4080,11 @@ malloc_init_hard(void)
 			break;
 		case 2:
 			if (_malloc_options != NULL) {
-			    /*
-			     * Use options that were compiled into the program.
-			     */
-			    opts = _malloc_options;
+				/*
+				 * Use options that were compiled into the
+				 * program.
+				 */
+				opts = _malloc_options;
 			} else {
 				/* No configuration specified. */
 				buf[0] = '\0';
@@ -3266,110 +4097,181 @@ malloc_init_hard(void)
 		}
 
 		for (j = 0; opts[j] != '\0'; j++) {
-			switch (opts[j]) {
-			case 'a':
-				opt_abort = false;
-				break;
-			case 'A':
-				opt_abort = true;
-				break;
-			case 'h':
-				opt_hint = false;
-				break;
-			case 'H':
-				opt_hint = true;
-				break;
-			case 'j':
-				opt_junk = false;
-				break;
-			case 'J':
-				opt_junk = true;
-				break;
-			case 'k':
-				/*
-				 * Chunks always require at least one header
-				 * page, so chunks can never be smaller than
-				 * two pages.
-				 */
-				if (opt_chunk_2pow > pagesize_2pow + 1)
-					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_FREE
-				 * special.
-				 */
-				if (opt_chunk_2pow - pagesize_2pow
-				    < (sizeof(uint32_t) << 3) - 1)
-					opt_chunk_2pow++;
-				break;
-			case 'n':
-				opt_narenas_lshift--;
-				break;
-			case 'N':
-				opt_narenas_lshift++;
-				break;
-			case 'p':
-				opt_print_stats = false;
-				break;
-			case 'P':
-				opt_print_stats = true;
-				break;
-			case 'q':
-				if (opt_quantum_2pow > QUANTUM_2POW_MIN)
-					opt_quantum_2pow--;
-				break;
-			case 'Q':
-				if (opt_quantum_2pow < pagesize_2pow - 1)
-					opt_quantum_2pow++;
-				break;
-			case 's':
-				if (opt_small_max_2pow > QUANTUM_2POW_MIN)
-					opt_small_max_2pow--;
-				break;
-			case 'S':
-				if (opt_small_max_2pow < pagesize_2pow - 1)
-					opt_small_max_2pow++;
-				break;
-			case 'u':
-				opt_utrace = false;
-				break;
-			case 'U':
-				opt_utrace = true;
-				break;
-			case 'v':
-				opt_sysv = false;
-				break;
-			case 'V':
-				opt_sysv = true;
-				break;
-			case 'x':
-				opt_xmalloc = false;
-				break;
-			case 'X':
-				opt_xmalloc = true;
-				break;
-			case 'z':
-				opt_zero = false;
-				break;
-			case 'Z':
-				opt_zero = true;
-				break;
-			default: {
-				char cbuf[2];
-				
-				cbuf[0] = opts[j];
-				cbuf[1] = '\0';
-				_malloc_message(_getprogname(),
-				    ": (malloc) Unsupported character in "
-				    "malloc options: '", cbuf, "'\n");
+			unsigned k, nreps;
+			bool nseen;
+
+			/* Parse repetition count, if any. */
+			for (nreps = 0, nseen = false;; j++, nseen = true) {
+				switch (opts[j]) {
+					case '0': case '1': case '2': case '3':
+					case '4': case '5': case '6': case '7':
+					case '8': case '9':
+						nreps *= 10;
+						nreps += opts[j] - '0';
+						break;
+					default:
+						goto MALLOC_OUT;
+				}
 			}
+MALLOC_OUT:
+			if (nseen == false)
+				nreps = 1;
+
+			for (k = 0; k < nreps; k++) {
+				switch (opts[j]) {
+				case 'a':
+					opt_abort = false;
+					break;
+				case 'A':
+					opt_abort = true;
+					break;
+				case 'b':
+#ifdef MALLOC_BALANCE
+					opt_balance_threshold >>= 1;
+#endif
+					break;
+				case 'B':
+#ifdef MALLOC_BALANCE
+					if (opt_balance_threshold == 0)
+						opt_balance_threshold = 1;
+					else if ((opt_balance_threshold << 1)
+					    > opt_balance_threshold)
+						opt_balance_threshold <<= 1;
+#endif
+					break;
+				case 'd':
+#ifdef MALLOC_DSS
+					opt_dss = false;
+#endif
+					break;
+				case 'D':
+#ifdef MALLOC_DSS
+					opt_dss = true;
+#endif
+					break;
+				case 'f':
+					opt_dirty_max >>= 1;
+					break;
+				case 'F':
+					if (opt_dirty_max == 0)
+						opt_dirty_max = 1;
+					else if ((opt_dirty_max << 1) != 0)
+						opt_dirty_max <<= 1;
+					break;
+				case 'h':
+					/* Compatibility hack for RELENG_7. */
+					opt_dirty_max = DIRTY_MAX_DEFAULT;
+					break;
+				case 'H':
+					/* Compatibility hack for RELENG_7. */
+					opt_dirty_max = 0;
+					break;
+				case 'j':
+					opt_junk = false;
+					break;
+				case 'J':
+					opt_junk = true;
+					break;
+				case 'k':
+					/*
+					 * Chunks always require at least one
+					 * header page, so chunks can never be
+					 * smaller than two pages.
+					 */
+					if (opt_chunk_2pow > pagesize_2pow + 1)
+						opt_chunk_2pow--;
+					break;
+				case 'K':
+					if (opt_chunk_2pow + 1 <
+					    (sizeof(size_t) << 3))
+						opt_chunk_2pow++;
+					break;
+				case 'm':
+#ifdef MALLOC_DSS
+					opt_mmap = false;
+#endif
+					break;
+				case 'M':
+#ifdef MALLOC_DSS
+					opt_mmap = true;
+#endif
+					break;
+				case 'n':
+					opt_narenas_lshift--;
+					break;
+				case 'N':
+					opt_narenas_lshift++;
+					break;
+				case 'p':
+					opt_print_stats = false;
+					break;
+				case 'P':
+					opt_print_stats = true;
+					break;
+				case 'q':
+					if (opt_quantum_2pow > QUANTUM_2POW_MIN)
+						opt_quantum_2pow--;
+					break;
+				case 'Q':
+					if (opt_quantum_2pow < pagesize_2pow -
+					    1)
+						opt_quantum_2pow++;
+					break;
+				case 's':
+					if (opt_small_max_2pow >
+					    QUANTUM_2POW_MIN)
+						opt_small_max_2pow--;
+					break;
+				case 'S':
+					if (opt_small_max_2pow < pagesize_2pow
+					    - 1)
+						opt_small_max_2pow++;
+					break;
+				case 'u':
+					opt_utrace = false;
+					break;
+				case 'U':
+					opt_utrace = true;
+					break;
+				case 'v':
+					opt_sysv = false;
+					break;
+				case 'V':
+					opt_sysv = true;
+					break;
+				case 'x':
+					opt_xmalloc = false;
+					break;
+				case 'X':
+					opt_xmalloc = true;
+					break;
+				case 'z':
+					opt_zero = false;
+					break;
+				case 'Z':
+					opt_zero = true;
+					break;
+				default: {
+					char cbuf[2];
+
+					cbuf[0] = opts[j];
+					cbuf[1] = '\0';
+					_malloc_message(_getprogname(),
+					    ": (malloc) Unsupported character "
+					    "in malloc options: '", cbuf,
+					    "'\n");
+				}
+				}
 			}
 		}
 	}
 
+#ifdef MALLOC_DSS
+	/* Make sure that there is some method for acquiring memory. */
+	if (opt_dss == false && opt_mmap == false)
+		opt_mmap = true;
+#endif
+
 	/* Take care to call atexit() only once. */
 	if (opt_print_stats) {
 		/* Print statistics at exit. */
@@ -3379,7 +4281,7 @@ malloc_init_hard(void)
 	/* Set variables according to the value of opt_small_max_2pow. */
 	if (opt_small_max_2pow < opt_quantum_2pow)
 		opt_small_max_2pow = opt_quantum_2pow;
-	small_max = (1 << opt_small_max_2pow);
+	small_max = (1U << opt_small_max_2pow);
 
 	/* Set bin-related variables. */
 	bin_maxclass = (pagesize >> 1);
@@ -3390,7 +4292,7 @@ malloc_init_hard(void)
 	nsbins = pagesize_2pow - opt_small_max_2pow - 1;
 
 	/* Set variables according to the value of opt_quantum_2pow. */
-	quantum = (1 << opt_quantum_2pow);
+	quantum = (1U << opt_quantum_2pow);
 	quantum_mask = quantum - 1;
 	if (ntbins > 0)
 		small_min = (quantum >> 1) + 1;
@@ -3403,13 +4305,20 @@ malloc_init_hard(void)
 	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);
@@ -3427,34 +4336,36 @@ malloc_init_hard(void)
 	assert(quantum * 4 <= chunksize);
 
 	/* Initialize chunks data. */
-	malloc_mutex_init(&chunks_mtx);
+	malloc_mutex_init(&huge_mtx);
 	RB_INIT(&huge);
-#ifdef USE_BRK
-	malloc_mutex_init(&brk_mtx);
-	brk_base = sbrk(0);
-	brk_prev = brk_base;
-	brk_max = brk_base;
+#ifdef MALLOC_DSS
+	malloc_mutex_init(&dss_mtx);
+	dss_base = sbrk(0);
+	dss_prev = dss_base;
+	dss_max = dss_base;
+	RB_INIT(&dss_chunks_szad);
+	RB_INIT(&dss_chunks_ad);
 #endif
 #ifdef MALLOC_STATS
 	huge_nmalloc = 0;
 	huge_ndalloc = 0;
 	huge_allocated = 0;
 #endif
-	RB_INIT(&old_chunks);
 
 	/* Initialize base allocation data structures. */
 #ifdef MALLOC_STATS
 	base_mapped = 0;
 #endif
-#ifdef USE_BRK
+#ifdef MALLOC_DSS
 	/*
 	 * Allocate a base chunk here, since it doesn't actually have to be
 	 * chunk-aligned.  Doing this before allocating any other chunks allows
 	 * the use of space that would otherwise be wasted.
 	 */
-	base_pages_alloc(0);
+	if (opt_dss)
+		base_pages_alloc(0);
 #endif
-	base_chunk_nodes = NULL;
+	base_nodes = NULL;
 	malloc_mutex_init(&base_mtx);
 
 	if (ncpus > 1) {
@@ -3471,18 +4382,24 @@ malloc_init_hard(void)
 		if ((narenas << opt_narenas_lshift) > narenas)
 			narenas <<= opt_narenas_lshift;
 		/*
-		 * Make sure not to exceed the limits of what base_malloc()
-		 * can handle.
+		 * Make sure not to exceed the limits of what base_alloc() can
+		 * handle.
 		 */
 		if (narenas * sizeof(arena_t *) > chunksize)
 			narenas = chunksize / sizeof(arena_t *);
 	} else if (opt_narenas_lshift < 0) {
-		if ((narenas << opt_narenas_lshift) < narenas)
-			narenas <<= opt_narenas_lshift;
+		if ((narenas >> -opt_narenas_lshift) < narenas)
+			narenas >>= -opt_narenas_lshift;
 		/* Make sure there is at least one arena. */
 		if (narenas == 0)
 			narenas = 1;
 	}
+#ifdef MALLOC_BALANCE
+	assert(narenas != 0);
+	for (narenas_2pow = 0;
+	     (narenas >> (narenas_2pow + 1)) != 0;
+	     narenas_2pow++);
+#endif
 
 #ifdef NO_TLS
 	if (narenas > 1) {
@@ -3512,7 +4429,9 @@ malloc_init_hard(void)
 #endif
 
 #ifndef NO_TLS
+#  ifndef MALLOC_BALANCE
 	next_arena = 0;
+#  endif
 #endif
 
 	/* Allocate and initialize arenas. */
@@ -3529,15 +4448,30 @@ malloc_init_hard(void)
 
 	/*
 	 * Initialize one arena here.  The rest are lazily created in
-	 * arena_choose_hard().
+	 * choose_arena_hard().
 	 */
 	arenas_extend(0);
 	if (arenas[0] == NULL) {
 		malloc_mutex_unlock(&init_lock);
 		return (true);
 	}
+#ifndef NO_TLS
+	/*
+	 * Assign the initial arena to the initial thread, in order to avoid
+	 * spurious creation of an extra arena if the application switches to
+	 * threaded mode.
+	 */
+	arenas_map = arenas[0];
+#endif
+	/*
+	 * Seed here for the initial thread, since choose_arena_hard() is only
+	 * called for other threads.  The seed value doesn't really matter.
+	 */
+#ifdef MALLOC_BALANCE
+	SPRN(balance, 42);
+#endif
 
-	malloc_mutex_init(&arenas_mtx);
+	malloc_spin_init(&arenas_lock);
 
 	malloc_initialized = true;
 	malloc_mutex_unlock(&init_lock);
@@ -3781,16 +4715,20 @@ _malloc_prefork(void)
 
 	/* Acquire all mutexes in a safe order. */
 
-	malloc_mutex_lock(&arenas_mtx);
+	malloc_spin_lock(&arenas_lock);
 	for (i = 0; i < narenas; i++) {
 		if (arenas[i] != NULL)
-			malloc_mutex_lock(&arenas[i]->mtx);
+			malloc_spin_lock(&arenas[i]->lock);
 	}
-	malloc_mutex_unlock(&arenas_mtx);
+	malloc_spin_unlock(&arenas_lock);
 
 	malloc_mutex_lock(&base_mtx);
 
-	malloc_mutex_lock(&chunks_mtx);
+	malloc_mutex_lock(&huge_mtx);
+
+#ifdef MALLOC_DSS
+	malloc_mutex_lock(&dss_mtx);
+#endif
 }
 
 void
@@ -3800,16 +4738,20 @@ _malloc_postfork(void)
 
 	/* Release all mutexes, now that fork() has completed. */
 
-	malloc_mutex_unlock(&chunks_mtx);
+#ifdef MALLOC_DSS
+	malloc_mutex_unlock(&dss_mtx);
+#endif
+
+	malloc_mutex_unlock(&huge_mtx);
 
 	malloc_mutex_unlock(&base_mtx);
 
-	malloc_mutex_lock(&arenas_mtx);
+	malloc_spin_lock(&arenas_lock);
 	for (i = 0; i < narenas; i++) {
 		if (arenas[i] != NULL)
-			malloc_mutex_unlock(&arenas[i]->mtx);
+			malloc_spin_unlock(&arenas[i]->lock);
 	}
-	malloc_mutex_unlock(&arenas_mtx);
+	malloc_spin_unlock(&arenas_lock);
 }
 
 /*