1 files changed, 4481 insertions, 927 deletions

diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c
index d279db6f8323..a3bc33511512 100644
--- a/lib/libc/stdlib/malloc.c
+++ b/lib/libc/stdlib/malloc.c
@@ -1,1214 +1,4739 @@
+/*-
+ * Copyright (C) 2006 Jason Evans <jasone@FreeBSD.org>.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice(s), this list of conditions and the following disclaimer as
+ *    the first lines of this file unmodified other than the possible
+ *    addition of one or more copyright notices.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice(s), this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+ * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
+ * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ *******************************************************************************
+ *
+ * Following is a brief list of features that distinguish this malloc
+ * implementation:
+ *
+ *   + Multiple arenas are used if there are multiple CPUs, which reduces lock
+ *     contention and cache sloshing.
+ *
+ *   + Cache line sharing between arenas is avoided for internal data
+ *     structures.
+ *
+ *   + Memory is managed in chunks, rather than as individual pages.
+ *
+ *   + Allocations are region-based; internal region size is a discrete
+ *     multiple of a quantum that is appropriate for alignment constraints.
+ *     This applies to allocations that are up to half the chunk size.
+ *
+ *   + Coalescence of regions is delayed in order to reduce overhead and
+ *     fragmentation.
+ *
+ *   + realloc() always moves data, in order to reduce fragmentation.
+ *
+ *   + Red-black trees are used to sort large regions.
+ *
+ *   + Data structures for huge allocations are stored separately from
+ *     allocations, which reduces thrashing during low memory conditions.
+ *
+ *******************************************************************************
+ */
+
 /*
- * ----------------------------------------------------------------------------
- * "THE BEER-WARE LICENSE" (Revision 42):
- * <phk@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
- * can do whatever you want with this stuff. If we meet some day, and you think
- * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
- * ----------------------------------------------------------------------------
+ *******************************************************************************
+ *
+ * Ring macros.
  *
+ *******************************************************************************
  */
 
+/* Ring definitions. */
+#define	qr(a_type) struct {						\
+	a_type *qre_next;						\
+	a_type *qre_prev;						\
+}
+
+#define	qr_initializer {NULL, NULL}
+
+/* Ring functions. */
+#define	qr_new(a_qr, a_field) do {					\
+	(a_qr)->a_field.qre_next = (a_qr);				\
+	(a_qr)->a_field.qre_prev = (a_qr);				\
+} while (0)
+
+#define	qr_next(a_qr, a_field) ((a_qr)->a_field.qre_next)
+
+#define	qr_prev(a_qr, a_field) ((a_qr)->a_field.qre_prev)
+
+#define	qr_before_insert(a_qrelm, a_qr, a_field) do {			\
+	(a_qr)->a_field.qre_prev = (a_qrelm)->a_field.qre_prev;		\
+	(a_qr)->a_field.qre_next = (a_qrelm);				\
+	(a_qr)->a_field.qre_prev->a_field.qre_next = (a_qr);		\
+	(a_qrelm)->a_field.qre_prev = (a_qr);				\
+} while (0)
+
+#define	qr_after_insert(a_qrelm, a_qr, a_field) do {			\
+	(a_qr)->a_field.qre_next = (a_qrelm)->a_field.qre_next;		\
+	(a_qr)->a_field.qre_prev = (a_qrelm);				\
+	(a_qr)->a_field.qre_next->a_field.qre_prev = (a_qr);		\
+	(a_qrelm)->a_field.qre_next = (a_qr);				\
+} while (0)
+
+#define	qr_meld(a_qr_a, a_qr_b, a_type, a_field) do {			\
+	a_type *t;							\
+	(a_qr_a)->a_field.qre_prev->a_field.qre_next = (a_qr_b);	\
+	(a_qr_b)->a_field.qre_prev->a_field.qre_next = (a_qr_a);	\
+	t = (a_qr_a)->a_field.qre_prev;					\
+	(a_qr_a)->a_field.qre_prev = (a_qr_b)->a_field.qre_prev;	\
+	(a_qr_b)->a_field.qre_prev = t;					\
+} while (0)
+
+/* qr_meld() and qr_split() are functionally equivalent, so there's no need to
+ * have two copies of the code. */
+#define	qr_split(a_qr_a, a_qr_b, a_type, a_field)			\
+	qr_meld((a_qr_a), (a_qr_b), a_type, a_field)
+
+#define	qr_remove(a_qr, a_field) do {					\
+	(a_qr)->a_field.qre_prev->a_field.qre_next			\
+	    = (a_qr)->a_field.qre_next;					\
+	(a_qr)->a_field.qre_next->a_field.qre_prev			\
+	    = (a_qr)->a_field.qre_prev;					\
+	(a_qr)->a_field.qre_next = (a_qr);				\
+	(a_qr)->a_field.qre_prev = (a_qr);				\
+} while (0)
+
+#define	qr_foreach(var, a_qr, a_field)					\
+	for ((var) = (a_qr);						\
+	    (var) != NULL;						\
+	    (var) = (((var)->a_field.qre_next != (a_qr))		\
+	    ? (var)->a_field.qre_next : NULL))
+
+#define	qr_reverse_foreach(var, a_qr, a_field)				\
+	for ((var) = ((a_qr) != NULL) ? qr_prev(a_qr, a_field) : NULL;	\
+	    (var) != NULL;						\
+	    (var) = (((var) != (a_qr))					\
+	    ? (var)->a_field.qre_prev : NULL))
+
+/******************************************************************************/
+
+#define	MALLOC_DEBUG
+
 #include <sys/cdefs.h>
 __FBSDID("$FreeBSD$");
 
+#include "libc_private.h"
+#ifdef MALLOC_DEBUG
+#  define _LOCK_DEBUG
+#endif
+#include "spinlock.h"
+#include "namespace.h"
+#include <sys/mman.h>
+#include <sys/param.h>
+#include <sys/stddef.h>
+#include <sys/time.h>
+#include <sys/types.h>
+#include <sys/sysctl.h>
+#include <sys/tree.h>
+#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>
+
+#include <errno.h>
+#include <limits.h>
+#include <pthread.h>
+#include <sched.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <strings.h>
+#include <unistd.h>
+
+#include "un-namespace.h"
+
 /*
- * Defining MALLOC_EXTRA_SANITY will enable extra checks which are related
- * to internal conditions and consistency in malloc.c. This has a
- * noticeable runtime performance hit, and generally will not do you
- * any good unless you fiddle with the internals of malloc or want
- * to catch random pointer corruption as early as possible.
+ * Calculate statistics that can be used to get an idea of how well caching is
+ * working.
  */
-#undef MALLOC_EXTRA_SANITY
+#define	MALLOC_STATS
+/* #define	MALLOC_STATS_BASE */
+#define	MALLOC_STATS_ARENAS
 
 /*
- * What to use for Junk.  This is the byte value we use to fill with
- * when the 'J' option is enabled.
+ * Include redzones before/after every region, and check for buffer overflows.
  */
-#define SOME_JUNK	0xd0		/* as in "Duh" :-) */
+#define MALLOC_REDZONES
+#ifdef MALLOC_REDZONES
+#  define MALLOC_RED_2POW	4
+#  define MALLOC_RED		((size_t)(1 << MALLOC_RED_2POW))
+#endif
+
+#ifndef MALLOC_DEBUG
+#  ifndef NDEBUG
+#    define NDEBUG
+#  endif
+#endif
+#include <assert.h>
+
+#ifdef MALLOC_DEBUG
+   /* Disable inlining to make debugging easier. */
+#  define __inline
+#endif
+
+/* Size of stack-allocated buffer passed to strerror_r(). */
+#define	STRERROR_BUF 64
+
+/* Number of quantum-spaced bins to store free regions in. */
+#define	NBINS 128
+
+/* Minimum alignment of allocations is 2^QUANTUM_2POW_MIN bytes. */
+#ifdef __i386__
+#  define QUANTUM_2POW_MIN	4
+#  define SIZEOF_PTR		4
+#  define USE_BRK
+#endif
+#ifdef __ia64__
+#  define QUANTUM_2POW_MIN	4
+#  define SIZEOF_PTR		8
+#endif
+#ifdef __alpha__
+#  define QUANTUM_2POW_MIN	4
+#  define SIZEOF_PTR		8
+#  define NO_TLS
+#endif
+#ifdef __sparc64__
+#  define QUANTUM_2POW_MIN	4
+#  define SIZEOF_PTR		8
+#  define NO_TLS
+#endif
+#ifdef __amd64__
+#  define QUANTUM_2POW_MIN	4
+#  define SIZEOF_PTR		8
+#endif
+#ifdef __arm__
+#  define QUANTUM_2POW_MIN	3
+#  define SIZEOF_PTR		4
+#  define USE_BRK
+#  define NO_TLS
+#endif
+#ifdef __powerpc__
+#  define QUANTUM_2POW_MIN	4
+#  define SIZEOF_PTR		4
+#  define USE_BRK
+#endif
+
+/* We can't use TLS in non-PIC programs, since TLS relies on loader magic. */
+#if (!defined(PIC) && !defined(NO_TLS))
+#  define NO_TLS
+#endif
 
 /*
- * The basic parameters you can tweak.
+ * Size and alignment of memory chunks that are allocated by the OS's virtual
+ * memory system.
  *
- * malloc_pageshift	pagesize = 1 << malloc_pageshift
- *			It's probably best if this is the native
- *			page size, but it doesn't have to be.
+ * chunk_size must be at least as large as the system page size.  In practice,
+ * it actually needs to be quite a bit larger (64 KB or so), because calling
+ * _pthread_self() can trigger a ~16 KB allocation due to libpthread
+ * initialization, and infinite recursion will occur if libpthread
+ * initialization requires a chunk allocation.
  *
- * malloc_minsize	minimum size of an allocation in bytes.
- *			If this is too small it's too much work
- *			to manage them.  This is also the smallest
- *			unit of alignment used for the storage
- *			returned by malloc/realloc.
+ * chunk_size must be <= 2^29.
+ */
+#define	CHUNK_2POW_MIN		16
+#define	CHUNK_2POW_DEFAULT	24
+#define	CHUNK_2POW_MAX		29
+
+/*
+ * 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.
  *
+ * Most allocations from base_arena use this, in order to avoid any false
+ * sharing.
  */
+#define	CACHELINE_2POW 6
+#define	CACHELINE ((size_t) (1 << CACHELINE_2POW))
 
-#include "namespace.h"
-#if defined(__FreeBSD__)
-#   if defined(__i386__)
-#       define malloc_pageshift		12U
-#       define malloc_minsize		16U
-#   endif
-#   if defined(__ia64__)
-#	define malloc_pageshift		13U
-#	define malloc_minsize		16U
-#   endif
-#   if defined(__alpha__)
-#       define malloc_pageshift		13U
-#       define malloc_minsize		16U
-#   endif
-#   if defined(__sparc64__)
-#       define malloc_pageshift		13U
-#       define malloc_minsize		16U
-#   endif
-#   if defined(__amd64__)
-#       define malloc_pageshift		12U
-#       define malloc_minsize		16U
-#   endif
-#   if defined(__arm__)
-#       define malloc_pageshift         12U
-#       define malloc_minsize           16U
-#   endif
-#   define HAS_UTRACE
-    /*
-     * Make malloc/free/realloc thread-safe in libc for use with
-     * kernel threads.
-     */
-#   include "libc_private.h"
-#   include "spinlock.h"
-    static spinlock_t thread_lock	= _SPINLOCK_INITIALIZER;
-    spinlock_t *__malloc_lock		= &thread_lock;
-#   define _MALLOC_LOCK()		if (__isthreaded) _SPINLOCK(&thread_lock);
-#   define _MALLOC_UNLOCK()		if (__isthreaded) _SPINUNLOCK(&thread_lock);
-#endif /* __FreeBSD__ */
-
-#if defined(__sparc__) && defined(sun)
-#   define malloc_pageshift		12U
-#   define malloc_minsize		16U
-#   define MAP_ANON			(0)
-    static int fdzero;
-#   define MMAP_FD	fdzero
-#   define INIT_MMAP() \
-	{ if ((fdzero = _open(_PATH_DEVZERO, O_RDWR, 0000)) == -1) \
-	    wrterror("open of /dev/zero"); }
-#   define MADV_FREE			MADV_DONTNEED
-#endif /* __sparc__ */
-
-/* Insert your combination here... */
-#if defined(__FOOCPU__) && defined(__BAROS__)
-#   define malloc_pageshift		12U
-#   define malloc_minsize		16U
-#endif /* __FOOCPU__ && __BAROS__ */
-
-#ifndef ZEROSIZEPTR
-#define ZEROSIZEPTR	((void *)(uintptr_t)(1 << (malloc_pageshift - 1)))
-#endif
+/* Default number of regions to delay coalescence for. */
+#define NDELAY 256
+
+/******************************************************************************/
 
 /*
- * No user serviceable parts behind this point.
+ * Mutexes based on spinlocks.  We can't use normal pthread mutexes, because
+ * they require malloc()ed memory.
  */
-#include <sys/types.h>
-#include <sys/mman.h>
-#include <errno.h>
-#include <fcntl.h>
-#include <paths.h>
-#include <stddef.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-#include "un-namespace.h"
+typedef struct {
+	spinlock_t	lock;
+	bool		recursive;
+	volatile int	val;
+} malloc_mutex_t;
+
+static bool malloc_initialized = false;
 
+/******************************************************************************/
 /*
- * This structure describes a page worth of chunks.
+ * Statistics data structures.
  */
 
-struct pginfo {
-    struct pginfo	*next;	/* next on the free list */
-    void		*page;	/* Pointer to the page */
-    u_short		size;	/* size of this page's chunks */
-    u_short		shift;	/* How far to shift for this size chunks */
-    u_short		free;	/* How many free chunks */
-    u_short		total;	/* How many chunk */
-    u_int		bits[1]; /* Which chunks are free */
+#ifdef MALLOC_STATS
+
+typedef struct malloc_bin_stats_s malloc_bin_stats_t;
+struct malloc_bin_stats_s {
+	/*
+	 * Number of allocation requests that corresponded to the size of this
+	 * bin.
+	 */
+	uint64_t	nrequests;
+
+	/*
+	 * Number of best-fit allocations that were successfully serviced by
+	 * this bin.
+	 */
+	uint64_t	nfit;
+
+	/*
+	 * Number of allocation requests that were successfully serviced by this
+	 * bin, but that a smaller bin could have serviced.
+	 */
+	uint64_t	noverfit;
+
+	/* High-water marks for this bin. */
+	unsigned long	highcached;
+
+	/*
+	 * Current number of regions in this bin.  This number isn't needed
+	 * during normal operation, so is maintained here in order to allow
+	 * calculating the high water mark.
+	 */
+	unsigned	nregions;
+};
+
+typedef struct arena_stats_s arena_stats_t;
+struct arena_stats_s {
+	/* Number of times each function was called. */
+	uint64_t	nmalloc;
+	uint64_t	npalloc;
+	uint64_t	ncalloc;
+	uint64_t	ndalloc;
+	uint64_t	nralloc;
+
+	/* Number of region splits. */
+	uint64_t	nsplit;
+
+	/* Number of region coalescences. */
+	uint64_t	ncoalesce;
+
+	/* Bin statistics. */
+	malloc_bin_stats_t bins[NBINS];
+
+	/* Split statistics. */
+	struct {
+		/*
+		 * Number of times a region is requested from the "split" field
+		 * of the arena.
+		 */
+		uint64_t	nrequests;
+
+		/*
+		 * Number of times the "split" field of the arena successfully
+		 * services requests.
+		 */
+		uint64_t	nserviced;
+	}	split;
+
+	/* Frag statistics. */
+	struct {
+		/*
+		 * Number of times a region is cached in the "frag" field of
+		 * the arena.
+		 */
+		uint64_t	ncached;
+
+		/*
+		 * Number of times a region is requested from the "frag" field
+		 * of the arena.
+		 */
+		uint64_t	nrequests;
+
+		/*
+		 * Number of times the "frag" field of the arena successfully
+		 * services requests.
+		 */
+		uint64_t	nserviced;
+	}	frag;
+
+	/* large and large_regions statistics. */
+	struct {
+		/*
+		 * Number of allocation requests that were too large for a bin,
+		 * but not large enough for a hugh allocation.
+		 */
+		uint64_t	nrequests;
+
+		/*
+		 * Number of best-fit allocations that were successfully
+		 * serviced by large_regions.
+		 */
+		uint64_t	nfit;
+
+		/*
+		 * Number of allocation requests that were successfully serviced
+		 * large_regions, but that a bin could have serviced.
+		 */
+		uint64_t	noverfit;
+
+		/*
+		 * High-water mark for large_regions (number of nodes in tree).
+		 */
+		unsigned long	highcached;
+
+		/*
+		 * Used only to store the current number of nodes, since this
+		 * number isn't maintained anywhere else.
+		 */
+		unsigned long	curcached;
+	}	large;
+
+	/* Huge allocation statistics. */
+	struct {
+		/* Number of huge allocation requests. */
+		uint64_t	nrequests;
+	}	huge;
+};
+
+typedef struct chunk_stats_s chunk_stats_t;
+struct chunk_stats_s {
+	/* Number of chunks that were allocated. */
+	uint64_t	nchunks;
+
+	/* High-water mark for number of chunks allocated. */
+	unsigned long	highchunks;
+
+	/*
+	 * Current number of chunks allocated.  This value isn't maintained for
+	 * any other purpose, so keep track of it in order to be able to set
+	 * highchunks.
+	 */
+	unsigned long	curchunks;
 };
 
+#endif /* #ifdef MALLOC_STATS */
+
+/******************************************************************************/
 /*
- * This structure describes a number of free pages.
+ * Chunk data structures.
  */
 
-struct pgfree {
-    struct pgfree	*next;	/* next run of free pages */
-    struct pgfree	*prev;	/* prev run of free pages */
-    void		*page;	/* pointer to free pages */
-    void		*end;	/* pointer to end of free pages */
-    size_t		size;	/* number of bytes free */
+/* Needed by chunk data structures. */
+typedef struct	arena_s arena_t;
+
+/* Tree of chunks. */
+typedef struct chunk_node_s chunk_node_t;
+struct chunk_node_s {
+	/*
+	 * For an active chunk that is currently carved into regions by an
+	 * arena allocator, this points to the arena that owns the chunk.  We
+	 * set this pointer even for huge allocations, so that it is possible
+	 * to tell whether a huge allocation was done on behalf of a user
+	 * allocation request, or on behalf of an internal allocation request.
+	 */
+	arena_t *arena;
+
+	/* Linkage for the chunk tree. */
+	RB_ENTRY(chunk_node_s) link;
+
+	/*
+	 * 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;
+
+	/* Total chunk size. */
+	size_t	size;
+
+	/* Number of trailing bytes that are not used. */
+	size_t	extra;
 };
+typedef struct chunk_tree_s chunk_tree_t;
+RB_HEAD(chunk_tree_s, chunk_node_s);
 
+/******************************************************************************/
 /*
- * How many bits per u_int in the bitmap.
- * Change only if not 8 bits/byte
+ * Region data structures.
  */
-#define	MALLOC_BITS	(8*sizeof(u_int))
+
+typedef struct region_s region_t;
 
 /*
- * Magic values to put in the page_directory
+ * Tree of region headers, used for free regions that don't fit in the arena
+ * bins.
  */
-#define MALLOC_NOT_MINE	((struct pginfo*) 0)
-#define MALLOC_FREE 	((struct pginfo*) 1)
-#define MALLOC_FIRST	((struct pginfo*) 2)
-#define MALLOC_FOLLOW	((struct pginfo*) 3)
-#define MALLOC_MAGIC	((struct pginfo*) 4)
+typedef struct region_node_s region_node_t;
+struct region_node_s {
+	RB_ENTRY(region_node_s)	link;
+	region_t		*reg;
+};
+typedef struct region_tree_s region_tree_t;
+RB_HEAD(region_tree_s, region_node_s);
 
-#ifndef malloc_pageshift
-#define malloc_pageshift		12U
-#endif
+typedef struct region_prev_s region_prev_t;
+struct region_prev_s {
+	uint32_t	size;
+};
 
-#ifndef malloc_minsize
-#define malloc_minsize			16U
+#define NEXT_SIZE_MASK 0x1fffffffU
+typedef struct {
+#ifdef MALLOC_REDZONES
+	char		prev_red[MALLOC_RED];
 #endif
+	/*
+	 * Typical bit pattern for bits:
+	 *
+	 *   pncsssss ssssssss ssssssss ssssssss
+	 *
+	 *   p : Previous free?
+	 *   n : Next free?
+	 *   c : Part of a range of contiguous allocations?
+	 *   s : Next size (number of quanta).
+	 *
+	 * It's tempting to use structure bitfields here, but the compiler has
+	 * to make assumptions that make the code slower than direct bit
+	 * manipulations, and these fields are manipulated a lot.
+	 */
+	uint32_t	bits;
 
-#if !defined(malloc_pagesize)
-#define malloc_pagesize			(1UL<<malloc_pageshift)
+#ifdef MALLOC_REDZONES
+	size_t		next_exact_size;
+	char		next_red[MALLOC_RED];
 #endif
+} region_sep_t;
 
-#if ((1<<malloc_pageshift) != malloc_pagesize)
-#error	"(1<<malloc_pageshift) != malloc_pagesize"
-#endif
+typedef struct region_next_small_sizer_s region_next_small_sizer_t;
+struct region_next_small_sizer_s
+{
+	qr(region_t)	link;
+};
 
-#ifndef malloc_maxsize
-#define malloc_maxsize			((malloc_pagesize)>>1)
-#endif
+typedef struct region_next_small_s region_next_small_t;
+struct region_next_small_s
+{
+	qr(region_t)	link;
 
-/* A mask for the offset inside a page.  */
-#define malloc_pagemask	((malloc_pagesize)-1)
+	/* Only accessed for delayed regions & footer invalid. */
+	uint32_t	slot;
+};
 
-#define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask)))
-#define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)-malloc_origo)
+typedef struct region_next_large_s region_next_large_t;
+struct region_next_large_s
+{
+	region_node_t	node;
 
-#ifndef _MALLOC_LOCK
-#define _MALLOC_LOCK()
-#endif
+	/* Use for LRU vs MRU tree ordering. */
+	bool		lru;
+};
 
-#ifndef _MALLOC_UNLOCK
-#define _MALLOC_UNLOCK()
+typedef struct region_next_s region_next_t;
+struct region_next_s {
+	union {
+		region_next_small_t	s;
+		region_next_large_t	l;
+	}	u;
+};
+
+/*
+ * Region separator, including prev/next fields that are only accessible when
+ * the neighboring regions are free.
+ */
+struct region_s {
+	/* This field must only be accessed if sep.prev_free is true. */
+	region_prev_t   prev;
+
+	/* Actual region separator that is always present between regions. */
+	region_sep_t    sep;
+
+	/*
+	 * These fields must only be accessed if sep.next_free or
+	 * sep.next_contig is true. 
+	 */
+	region_next_t   next;
+};
+
+/* Small variant of region separator, only used for size calculations. */
+typedef struct region_small_sizer_s region_small_sizer_t;
+struct region_small_sizer_s {
+	region_prev_t   prev;
+	region_sep_t    sep;
+	region_next_small_sizer_t   next;
+};
+
+/******************************************************************************/
+/*
+ * Arena data structures.
+ */
+
+typedef struct arena_bin_s arena_bin_t;
+struct arena_bin_s {
+	/*
+	 * Link into ring before the oldest free region and just after the
+	 * newest free region.
+	 */
+	region_t	regions;
+};
+
+struct arena_s {
+#ifdef MALLOC_DEBUG
+	uint32_t	magic;
+#  define ARENA_MAGIC 0x947d3d24
 #endif
 
-#ifndef MMAP_FD
-#define MMAP_FD (-1)
+	/* All operations on this arena require that mtx be locked. */
+	malloc_mutex_t	mtx;
+
+	/* True if this arena is allocated from base_arena. */
+	bool		malloced;
+
+	/*
+	 * bins is used to store rings of free regions of the following sizes,
+	 * assuming a 16-byte quantum (sizes include region separators):
+	 *
+	 *   bins[i] | size |
+	 *   --------+------+
+	 *        0  |   32 |
+	 *        1  |   48 |
+	 *        2  |   64 |
+	 *           :      :
+	 *           :      :
+	 *   --------+------+
+	 */
+	arena_bin_t	bins[NBINS];
+
+	/*
+	 * A bitmask that corresponds to which bins have elements in them.
+	 * This is used when searching for the first bin that contains a free
+	 * region that is large enough to service an allocation request.
+	 */
+#define	BINMASK_NELMS (NBINS / (sizeof(int) << 3))
+	int		bins_mask[BINMASK_NELMS];
+
+	/*
+	 * Tree of free regions of the size range [bin_maxsize..~chunk).  These
+	 * are sorted primarily by size, and secondarily by LRU.
+	 */
+	region_tree_t	large_regions;
+
+	/*
+	 * If not NULL, a region that is not stored in bins or large_regions.
+	 * If large enough, this region is used instead of any region stored in
+	 * bins or large_regions, in order to reduce the number of insert/remove
+	 * operations, and in order to increase locality of allocation in
+	 * common cases.
+	 */
+	region_t	*split;
+
+	/*
+	 * If not NULL, a region that is not stored in bins or large_regions.
+	 * If large enough, this region is preferentially used for small
+	 * allocations over any region in large_regions, split, or over-fit
+	 * small bins.
+	 */
+	region_t	*frag;
+
+	/* Tree of chunks that this arena currenly owns. */
+	chunk_tree_t	chunks;
+	unsigned	nchunks;
+
+	/*
+	 * FIFO ring of free regions for which coalescence is delayed.  A slot
+	 * that contains NULL is considered empty.  opt_ndelay stores how many
+	 * elements there are in the FIFO.
+	 */
+	region_t	**delayed;
+	uint32_t	next_delayed; /* Next slot in delayed to use. */
+
+#ifdef MALLOC_STATS
+	/* Total byte count of allocated memory, not including overhead. */
+	size_t		allocated;
+
+	arena_stats_t stats;
 #endif
+};
+
+/******************************************************************************/
+/*
+ * Data.
+ */
+
+/* Used as a special "nil" return value for malloc(0). */
+static int		nil;
+
+/* Number of CPUs. */
+static unsigned		ncpus;
+
+/* VM page size. */
+static unsigned		pagesize;
+
+/* Various quantum-related settings. */
+static size_t		quantum;
+static size_t		quantum_mask; /* (quantum - 1). */
+static size_t		bin_shift;
+static size_t		bin_maxsize;
+
+/* Various chunk-related settings. */
+static size_t		chunk_size;
+static size_t		chunk_size_mask; /* (chunk_size - 1). */
 
-#ifndef INIT_MMAP
-#define INIT_MMAP()
+/********/
+/*
+ * Chunks.
+ */
+
+/* Protects chunk-related data structures. */
+static malloc_mutex_t	chunks_mtx;
+
+/* Tree of chunks that are stand-alone huge allocations. */
+static chunk_tree_t	huge;
+
+#ifdef USE_BRK
+/*
+ * Try to use brk for chunk-size allocations, due to address space constraints.
+ */
+void *brk_base; /* Result of first sbrk(0) call. */
+void *brk_prev; /* Current end of brk, or ((void *)-1) if brk is exhausted. */
+void *brk_max; /* Upper limit on brk addresses (may be an over-estimate). */
 #endif
 
-/* Number of free pages we cache */
-static unsigned malloc_cache = 16;
+#ifdef MALLOC_STATS
+/*
+ * Byte counters for allocated/total space used by the chunks in the huge
+ * allocations tree.
+ */
+static size_t		huge_allocated;
+static size_t		huge_total;
+#endif
 
-/* The offset from pagenumber to index into the page directory */
-static u_long malloc_origo;
+/*
+ * 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;
 
-/* The last index in the page directory we care about */
-static u_long last_index;
+/********/
+/*
+ * Arenas.
+ */
 
-/* Pointer to page directory. Allocated "as if with" malloc */
-static struct	pginfo **page_dir;
+/* Arena that is used for internal memory allocations. */
+static arena_t		base_arena;
 
-/* How many slots in the page directory */
-static unsigned	malloc_ninfo;
+/* 
+ * Arenas that are used to service external requests.  Not all elements of the
+ * arenas array are necessarily used; arenas are created lazily as needed.
+ */
+static arena_t		**arenas;
+static unsigned		narenas;
+#ifndef NO_TLS
+static unsigned		next_arena;
+#endif
+static malloc_mutex_t	arenas_mtx; /* Protects arenas initialization. */
 
-/* Free pages line up here */
-static struct pgfree free_list;
+#ifndef NO_TLS
+/*
+ * Map of pthread_self() --> arenas[???], used for selecting an arena to use
+ * for allocations.
+ */
+static __thread arena_t *arenas_map;
+#endif
 
-/* Abort(), user doesn't handle problems.  */
-static int malloc_abort = 1;
+#ifdef MALLOC_STATS
+/* Chunk statistics. */
+chunk_stats_t		stats_chunks;
+#endif
 
-/* Are we trying to die ?  */
-static int suicide;
+/*******************************/
+/*
+ * Runtime configuration options.
+ */
+const char	*_malloc_options;
+
+static bool	opt_abort = true;
+static bool	opt_junk = true;
+static bool	opt_print_stats = false;
+static size_t	opt_quantum_2pow = QUANTUM_2POW_MIN;
+static size_t	opt_chunk_2pow = CHUNK_2POW_DEFAULT;
+static bool	opt_utrace = false;
+static bool	opt_sysv = false;
+static bool	opt_xmalloc = false;
+static bool	opt_zero = false;
+static uint32_t	opt_ndelay = NDELAY;
+static int32_t	opt_narenas_lshift = 0;
+
+typedef struct {
+	void	*p;
+	size_t	s;
+	void	*r;
+} malloc_utrace_t;
+
+#define	UTRACE(a, b, c)							\
+	if (opt_utrace) {						\
+		malloc_utrace_t ut = {a, b, c};				\
+		utrace(&ut, sizeof(ut));				\
+	}
 
-/* always realloc ?  */
-static int malloc_realloc;
+/******************************************************************************/
+/*
+ * Begin function prototypes for non-inline static functions.
+ */
 
-#if defined(MADV_FREE)
-/* pass the kernel a hint on free pages ?  */
-static int malloc_hint = 0;
+static void	malloc_mutex_init(malloc_mutex_t *a_mutex);
+static void	malloc_mutex_recursive_init(malloc_mutex_t *a_mutex);
+static void	wrtmessage(const char *p1, const char *p2, const char *p3,
+		const char *p4);
+static void	malloc_printf(const char *format, ...);
+#ifdef MALLOC_STATS
+static void	stats_merge(arena_t *arena, arena_stats_t *stats_arenas);
+static void	stats_print(arena_stats_t *stats_arenas);
+#endif
+static void	*pages_map(void *addr, size_t size);
+static void	pages_unmap(void *addr, size_t size);
+static void	*chunk_alloc(size_t size);
+static void	chunk_dealloc(void *chunk, size_t size);
+static unsigned	arena_bins_search(arena_t *arena, size_t size);
+static bool	arena_coalesce(arena_t *arena, region_t **reg, size_t size);
+static void	arena_coalesce_hard(arena_t *arena, region_t *reg,
+		region_t *next, size_t size, bool split_adjacent);
+static void	arena_large_insert(arena_t *arena, region_t *reg, bool lru);
+static void	arena_large_cache(arena_t *arena, region_t *reg, bool lru);
+static void	arena_lru_cache(arena_t *arena, region_t *reg);
+static void	arena_delay_cache(arena_t *arena, region_t *reg);
+static region_t	*arena_split_reg_alloc(arena_t *arena, size_t size, bool fit);
+static void	arena_reg_fit(arena_t *arena, size_t size, region_t *reg,
+		bool restore_split);
+static region_t	*arena_large_reg_alloc(arena_t *arena, size_t size, bool fit);
+static region_t	*arena_chunk_reg_alloc(arena_t *arena, size_t size, bool fit);
+static void	*arena_malloc(arena_t *arena, size_t size);
+static void	*arena_palloc(arena_t *arena, size_t alignment, size_t size);
+static void	*arena_calloc(arena_t *arena, size_t num, size_t size);
+static size_t	arena_salloc(arena_t *arena, void *ptr);
+#ifdef MALLOC_REDZONES
+static void	redzone_check(void *ptr);
+#endif
+static void	arena_dalloc(arena_t *arena, void *ptr);
+#ifdef NOT_YET
+static void	*arena_ralloc(arena_t *arena, void *ptr, size_t size);
+#endif
+#ifdef MALLOC_STATS
+static bool	arena_stats(arena_t *arena, size_t *allocated, size_t *total);
 #endif
+static void	arena_new(arena_t *arena, bool malloced, bool recursive);
+static arena_t	*arenas_extend(unsigned ind);
+#ifndef NO_TLS
+static arena_t	*choose_arena_hard(void);
+#endif
+static void	*huge_malloc(arena_t *arena, size_t size);
+static void	huge_dalloc(void *ptr);
+static void	*imalloc(arena_t *arena, size_t size);
+static void	*ipalloc(arena_t *arena, size_t alignment, size_t size);
+static void	*icalloc(arena_t *arena, size_t num, size_t size);
+static size_t	isalloc(void *ptr);
+static void	idalloc(void *ptr);
+static void	*iralloc(arena_t *arena, void *ptr, size_t size);
+#ifdef MALLOC_STATS
+static void	istats(size_t *allocated, size_t *total);
+#endif
+static void	malloc_print_stats(void);
+static void	malloc_init_hard(void);
 
-/* xmalloc behaviour ?  */
-static int malloc_xmalloc;
+/*
+ * End function prototypes.
+ */
+/******************************************************************************/
+/*
+ * Begin mutex.
+ */
 
-/* sysv behaviour for malloc(0) ?  */
-static int malloc_sysv;
+static void
+malloc_mutex_init(malloc_mutex_t *a_mutex)
+{
+	static const spinlock_t lock = _SPINLOCK_INITIALIZER;
 
-/* zero fill ?  */
-static int malloc_zero;
+	a_mutex->lock = lock;
+	a_mutex->recursive = false;
+	a_mutex->val = 0;
+}
 
-/* junk fill ?  */
-static int malloc_junk = 1;
+static void
+malloc_mutex_recursive_init(malloc_mutex_t *a_mutex)
+{
+	static const spinlock_t lock = _SPINLOCK_INITIALIZER;
 
-#ifdef HAS_UTRACE
+	a_mutex->lock = lock;
+	a_mutex->recursive = true;
+	a_mutex->val = 0;
+}
 
-/* utrace ?  */
-static int malloc_utrace;
+static __inline void
+malloc_mutex_lock(malloc_mutex_t *a_mutex)
+{
+#define	MAX_SPIN 1024
 
-struct ut { void *p; size_t s; void *r; };
+	if (__isthreaded) {
+		if (a_mutex->recursive == false)
+			_SPINLOCK(&a_mutex->lock);
+		else {
+			volatile long *owner = &a_mutex->lock.lock_owner;
+			long self;
 
-void utrace(struct ut *, int);
+			self = (long)_pthread_self();
 
-#define UTRACE(a, b, c) \
-	if (malloc_utrace) \
-		{struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
-#else /* !HAS_UTRACE */
-#define UTRACE(a,b,c)
-#endif /* HAS_UTRACE */
+			if (atomic_cmpset_acq_long(owner, self, self) == 0)
+				_SPINLOCK(&a_mutex->lock);
+			a_mutex->val++;
+		}
+	}
+}
 
-/* my last break. */
-static void *malloc_brk;
+static __inline void
+malloc_mutex_unlock(malloc_mutex_t *a_mutex)
+{
 
-/* one location cache for free-list holders */
-static struct pgfree *px;
+	if (__isthreaded) {
+		if (a_mutex->recursive == false) {
+			_SPINUNLOCK(&a_mutex->lock);
+		} else {
+			a_mutex->val--;
+			if (a_mutex->val == 0) {
+				_SPINUNLOCK(&a_mutex->lock);
+			}
+		}
+	}
+}
 
-/* compile-time options */
-const char *_malloc_options;
+/*
+ * End mutex.
+ */
+/******************************************************************************/
+/*
+ * Begin Utility functions/macros.
+ */
+
+/* Return the chunk address for allocation address a. */
+#define	CHUNK_ADDR2BASE(a)						\
+	((void *) ((size_t) (a) & ~chunk_size_mask))
 
-/* Name of the current public function */
-static const char *malloc_func;
+/* Return the chunk offset of address a. */
+#define	CHUNK_ADDR2OFFSET(a)						\
+	((size_t) (a) & chunk_size_mask)
 
-/* Macro for mmap */
-#define MMAP(size) \
-	mmap(NULL, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
-	    MMAP_FD, (off_t)0);
+/* Return the smallest chunk multiple that is >= s. */
+#define	CHUNK_CEILING(s)						\
+	(((s) + chunk_size_mask) & ~chunk_size_mask)
+
+/* Return the smallest quantum multiple that is >= a. */
+#define	QUANTUM_CEILING(a)						\
+	(((a) + quantum_mask) & ~quantum_mask)
+
+/* Return the offset within a chunk to the first region separator. */
+#define	CHUNK_REG_OFFSET						\
+	(QUANTUM_CEILING(sizeof(chunk_node_t) +				\
+	    sizeof(region_sep_t)) - offsetof(region_t, next))
 
 /*
- * Necessary function declarations
+ * Return how many bytes of usable space are needed for an allocation of size
+ * bytes.  This value is not a multiple of quantum, since it doesn't include
+ * the region separator.
  */
-static int extend_pgdir(u_long index);
-static void *imalloc(size_t size);
-static void ifree(void *ptr);
-static void *irealloc(void *ptr, size_t size);
+static __inline size_t
+region_ceiling(size_t size)
+{
+	size_t quantum_size, min_reg_quantum;
+
+	quantum_size = QUANTUM_CEILING(size + sizeof(region_sep_t));
+	min_reg_quantum = QUANTUM_CEILING(sizeof(region_small_sizer_t));
+	if (quantum_size >= min_reg_quantum)
+		return (quantum_size);
+	else
+		return (min_reg_quantum);
+}
 
 static void
 wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4)
 {
 
-    _write(STDERR_FILENO, p1, strlen(p1));
-    _write(STDERR_FILENO, p2, strlen(p2));
-    _write(STDERR_FILENO, p3, strlen(p3));
-    _write(STDERR_FILENO, p4, strlen(p4));
+	_write(STDERR_FILENO, p1, strlen(p1));
+	_write(STDERR_FILENO, p2, strlen(p2));
+	_write(STDERR_FILENO, p3, strlen(p3));
+	_write(STDERR_FILENO, p4, strlen(p4));
 }
 
-void (*_malloc_message)(const char *p1, const char *p2, const char *p3,
+void	(*_malloc_message)(const char *p1, const char *p2, const char *p3,
 	    const char *p4) = wrtmessage;
 
+/*
+ * Print to stderr in such a way as to (hopefully) avoid memory allocation.
+ */
+static void
+malloc_printf(const char *format, ...)
+{
+	char buf[4096];
+	va_list ap;
+
+	va_start(ap, format);
+	vsnprintf(buf, sizeof(buf), format, ap);
+	va_end(ap);
+	_malloc_message(buf, "", "", "");
+}
+
+/*
+ * Note that no bitshifting is done for booleans in any of the bitmask-based
+ * flag manipulation functions that follow; test for non-zero versus zero.
+ */
+
+/**********************/
+static __inline uint32_t
+region_prev_free_get(region_sep_t *sep)
+{
+
+	return ((sep->bits) & 0x80000000U);
+}
+
+static __inline void
+region_prev_free_set(region_sep_t *sep)
+{
+
+	sep->bits = ((sep->bits) | 0x80000000U);
+}
+
+static __inline void
+region_prev_free_unset(region_sep_t *sep)
+{
+
+	sep->bits = ((sep->bits) & 0x7fffffffU);
+}
+
+/**********************/
+static __inline uint32_t
+region_next_free_get(region_sep_t *sep)
+{
+
+	return ((sep->bits) & 0x40000000U);
+}
+
+static __inline void
+region_next_free_set(region_sep_t *sep)
+{
+
+	sep->bits = ((sep->bits) | 0x40000000U);
+}
+
+static __inline void
+region_next_free_unset(region_sep_t *sep)
+{
+
+	sep->bits = ((sep->bits) & 0xbfffffffU);
+}
+
+/**********************/
+static __inline uint32_t
+region_next_contig_get(region_sep_t *sep)
+{
+
+	return ((sep->bits) & 0x20000000U);
+}
+
+static __inline void
+region_next_contig_set(region_sep_t *sep)
+{
+
+	sep->bits = ((sep->bits) | 0x20000000U);
+}
+
+static __inline void
+region_next_contig_unset(region_sep_t *sep)
+{
+
+	sep->bits = ((sep->bits) & 0xdfffffffU);
+}
+
+/********************/
+static __inline size_t
+region_next_size_get(region_sep_t *sep)
+{
+
+	return ((size_t) (((sep->bits) & NEXT_SIZE_MASK) << opt_quantum_2pow));
+}
+
+static __inline void
+region_next_size_set(region_sep_t *sep, size_t size)
+{
+	uint32_t bits;
+
+	assert(size % quantum == 0);
+
+	bits = sep->bits;
+	bits &= ~NEXT_SIZE_MASK;
+	bits |= (((uint32_t) size) >> opt_quantum_2pow);
+
+	sep->bits = bits;
+}
+
+#ifdef MALLOC_STATS
 static void
-wrterror(char const *p)
+stats_merge(arena_t *arena, arena_stats_t *stats_arenas)
 {
+	unsigned i;
+
+	stats_arenas->nmalloc += arena->stats.nmalloc;
+	stats_arenas->npalloc += arena->stats.npalloc;
+	stats_arenas->ncalloc += arena->stats.ncalloc;
+	stats_arenas->ndalloc += arena->stats.ndalloc;
+	stats_arenas->nralloc += arena->stats.nralloc;
+
+	stats_arenas->nsplit += arena->stats.nsplit;
+	stats_arenas->ncoalesce += arena->stats.ncoalesce;
+
+	/* Split. */
+	stats_arenas->split.nrequests += arena->stats.split.nrequests;
+	stats_arenas->split.nserviced += arena->stats.split.nserviced;
+
+	/* Frag. */
+	stats_arenas->frag.ncached += arena->stats.frag.ncached;
+	stats_arenas->frag.nrequests += arena->stats.frag.nrequests;
+	stats_arenas->frag.nserviced += arena->stats.frag.nserviced;
+
+	/* Bins. */
+	for (i = 0; i < NBINS; i++) {
+		stats_arenas->bins[i].nrequests +=
+		    arena->stats.bins[i].nrequests;
+		stats_arenas->bins[i].nfit += arena->stats.bins[i].nfit;
+		stats_arenas->bins[i].noverfit += arena->stats.bins[i].noverfit;
+		if (arena->stats.bins[i].highcached
+		    > stats_arenas->bins[i].highcached) {
+		    stats_arenas->bins[i].highcached
+			= arena->stats.bins[i].highcached;
+		}
+	}
+
+	/* large and large_regions. */
+	stats_arenas->large.nrequests += arena->stats.large.nrequests;
+	stats_arenas->large.nfit += arena->stats.large.nfit;
+	stats_arenas->large.noverfit += arena->stats.large.noverfit;
+	if (arena->stats.large.highcached > stats_arenas->large.highcached)
+		stats_arenas->large.highcached = arena->stats.large.highcached;
+	stats_arenas->large.curcached += arena->stats.large.curcached;
 
-    suicide = 1;
-    _malloc_message(_getprogname(), malloc_func, " error: ", p);
-    abort();
+	/* Huge allocations. */
+	stats_arenas->huge.nrequests += arena->stats.huge.nrequests;
 }
 
 static void
-wrtwarning(char *p)
+stats_print(arena_stats_t *stats_arenas)
 {
+	unsigned i;
+
+	malloc_printf("calls:\n");
+	malloc_printf(" %13s%13s%13s%13s%13s\n", "nmalloc", "npalloc",
+	    "ncalloc", "ndalloc", "nralloc");
+	malloc_printf(" %13llu%13llu%13llu%13llu%13llu\n",
+	    stats_arenas->nmalloc, stats_arenas->npalloc, stats_arenas->ncalloc,
+	    stats_arenas->ndalloc, stats_arenas->nralloc);
+
+	malloc_printf("region events:\n");
+	malloc_printf(" %13s%13s\n", "nsplit", "ncoalesce");
+	malloc_printf(" %13llu%13llu\n", stats_arenas->nsplit,
+	    stats_arenas->ncoalesce);
+
+	malloc_printf("cached split usage:\n");
+	malloc_printf(" %13s%13s\n", "nrequests", "nserviced");
+	malloc_printf(" %13llu%13llu\n", stats_arenas->split.nrequests,
+	    stats_arenas->split.nserviced);
+
+	malloc_printf("cached frag usage:\n");
+	malloc_printf(" %13s%13s%13s\n", "ncached", "nrequests", "nserviced");
+	malloc_printf(" %13llu%13llu%13llu\n", stats_arenas->frag.ncached,
+	    stats_arenas->frag.nrequests, stats_arenas->frag.nserviced);
+
+	malloc_printf("bins:\n");
+	malloc_printf(" %4s%7s%13s%13s%13s%11s\n", "bin", 
+	    "size", "nrequests", "nfit", "noverfit", "highcached");
+	for (i = 0; i < NBINS; i++) {
+		malloc_printf(
+		    " %4u%7u%13llu%13llu%13llu%11lu\n",
+		    i, ((i + bin_shift) << opt_quantum_2pow),
+		    stats_arenas->bins[i].nrequests, stats_arenas->bins[i].nfit,
+		    stats_arenas->bins[i].noverfit,
+		    stats_arenas->bins[i].highcached);
+	}
 
-    /*
-     * Sensitive processes, somewhat arbitrarily defined here as setuid,
-     * setgid, root and wheel cannot afford to have malloc mistakes.
-     */
-    if (malloc_abort || issetugid() || getuid() == 0 || getgid() == 0)
-	wrterror(p);
-    _malloc_message(_getprogname(), malloc_func, " warning: ", p);
+	malloc_printf("large:\n");
+	malloc_printf(" %13s%13s%13s%13s%13s\n", "nrequests", "nfit",
+	    "noverfit", "highcached", "curcached");
+	malloc_printf(" %13llu%13llu%13llu%13lu%13lu\n",
+	    stats_arenas->large.nrequests, stats_arenas->large.nfit,
+	    stats_arenas->large.noverfit, stats_arenas->large.highcached,
+	    stats_arenas->large.curcached);
+
+	malloc_printf("huge\n");
+	malloc_printf(" %13s\n", "nrequests");
+	malloc_printf(" %13llu\n", stats_arenas->huge.nrequests);
 }
+#endif
 
 /*
- * Allocate a number of pages from the OS
+ * End Utility functions/macros.
+ */
+/******************************************************************************/
+/*
+ * Begin Mem.
  */
+
+static __inline int
+chunk_comp(chunk_node_t *a, chunk_node_t *b)
+{
+	int ret;
+
+	assert(a != NULL);
+	assert(b != NULL);
+
+	if ((size_t) a->chunk < (size_t) b->chunk)
+		ret = -1;
+	else if (a->chunk == b->chunk)
+		ret = 0;
+	else
+		ret = 1;
+
+	return (ret);
+}
+
+/* Generate red-black tree code for chunks. */
+RB_GENERATE(chunk_tree_s, chunk_node_s, link, chunk_comp);
+
+static __inline int
+region_comp(region_node_t *a, region_node_t *b)
+{
+	int ret;
+	size_t size_a, size_b;
+
+	assert(a != NULL);
+	assert(b != NULL);
+
+	size_a = region_next_size_get(&a->reg->sep);
+	size_b = region_next_size_get(&b->reg->sep);
+	if (size_a < size_b)
+		ret = -1;
+	else if (size_a == size_b) {
+		if (a == b) {
+			/* Regions are equal with themselves. */
+			ret = 0;
+		} else {
+			if (a->reg->next.u.l.lru) {
+				/*
+				 * Oldest region comes first (secondary LRU
+				 * ordering).  a is guaranteed to be the search
+				 * key, which is how we can enforce this
+				 * secondary ordering.
+				 */
+				ret = 1;
+			} else {
+				/*
+				 * Oldest region comes last (secondary MRU
+				 * ordering).  a is guaranteed to be the search
+				 * key, which is how we can enforce this
+				 * secondary ordering.
+				 */
+				ret = -1;
+			}
+		}
+	} else
+		ret = 1;
+
+	return (ret);
+}
+
+/* Generate red-black tree code for regions. */
+RB_GENERATE(region_tree_s, region_node_s, link, region_comp);
+
 static void *
-map_pages(size_t pages)
+pages_map(void *addr, size_t size)
 {
-    caddr_t result, tail;
+	void *ret;
 
-    result = (caddr_t)pageround((u_long)sbrk(0));
-    tail = result + (pages << malloc_pageshift);
-    if (tail < result)
-	return (NULL);
+#ifdef USE_BRK
+AGAIN:
+#endif
+	/*
+	 * We don't use MAP_FIXED here, because it can cause the *replacement*
+	 * of existing mappings, and we only want to create new mappings.
+	 */
+	ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON,
+	    -1, 0);
+	assert(ret != NULL);
+
+	if (ret == MAP_FAILED)
+		ret = NULL;
+	else if (addr != NULL && ret != addr) {
+		/*
+		 * We succeeded in mapping memory, but not in the right place.
+		 */
+		if (munmap(ret, size) == -1) {
+			char buf[STRERROR_BUF];
+
+			strerror_r(errno, buf, sizeof(buf));
+			malloc_printf("%s: (malloc) Error in munmap(): %s\n",
+			    _getprogname(), buf);
+			if (opt_abort)
+				abort();
+		}
+		ret = NULL;
+	}
+#ifdef USE_BRK
+	else if ((size_t)ret >= (size_t)brk_base
+	    && (size_t)ret < (size_t)brk_max) {
+		/*
+		 * We succeeded in mapping memory, but at a location that could
+		 * be confused with brk.  Leave the mapping intact so that this
+		 * won't ever happen again, then try again.
+		 */
+		assert(addr == NULL);
+		goto AGAIN;
+	}
+#endif
 
-    if (brk(tail)) {
-#ifdef MALLOC_EXTRA_SANITY
-	wrterror("(ES): map_pages fails\n");
-#endif /* MALLOC_EXTRA_SANITY */
-	return (NULL);
-    }
+	assert(ret == NULL || (addr == NULL && ret != addr)
+	    || (addr != NULL && ret == addr));
+	return (ret);
+}
 
-    last_index = ptr2index(tail) - 1;
-    malloc_brk = tail;
+static void
+pages_unmap(void *addr, size_t size)
+{
 
-    if ((last_index+1) >= malloc_ninfo && !extend_pgdir(last_index))
-	return (NULL);
+	if (munmap(addr, size) == -1) {
+		char buf[STRERROR_BUF];
 
-    return (result);
+		strerror_r(errno, buf, sizeof(buf));
+		malloc_printf("%s: (malloc) Error in munmap(): %s\n",
+		    _getprogname(), buf);
+		if (opt_abort)
+			abort();
+	}
 }
 
+static void *
+chunk_alloc(size_t size)
+{
+	void *ret, *chunk;
+	chunk_node_t *tchunk, *delchunk;
+	chunk_tree_t delchunks;
+
+	assert(size != 0);
+	assert(size % chunk_size == 0);
+
+	RB_INIT(&delchunks);
+
+	malloc_mutex_lock(&chunks_mtx);
+
+	if (size == chunk_size) {
+		/*
+		 * Check for address ranges that were previously chunks and try
+		 * to use them.
+		 */
+
+		tchunk = RB_MIN(chunk_tree_s, &old_chunks);
+		while (tchunk != NULL) {
+			/* Found an address range.  Try to recycle it. */
+
+			chunk = tchunk->chunk;
+			delchunk = tchunk;
+			tchunk = RB_NEXT(chunk_tree_s, &old_chunks, delchunk);
+
+			/*
+			 * Remove delchunk from the tree, but keep track of the
+			 * address.
+			 */
+			RB_REMOVE(chunk_tree_s, &old_chunks, delchunk);
+
+			/*
+			 * Keep track of the node so that it can be deallocated
+			 * after chunks_mtx is released.
+			 */
+			RB_INSERT(chunk_tree_s, &delchunks, delchunk);
+
+#ifdef USE_BRK
+			if ((size_t)chunk >= (size_t)brk_base
+			    && (size_t)chunk < (size_t)brk_max) {
+				/* Re-use a previously freed brk chunk. */
+				ret = chunk;
+				goto RETURN;
+			}
+#endif
+			if ((ret = pages_map(chunk, size)) != NULL) {
+				/* Success. */
+				goto RETURN;
+			}
+		}
+
+#ifdef USE_BRK
+		/*
+		 * Try to create chunk-size allocations in brk, in order to
+		 * make full use of limited address space.
+		 */
+		if (brk_prev != (void *)-1) {
+			void *brk_cur;
+			intptr_t incr;
+
+			/*
+			 * The loop is necessary to recover from races with
+			 * other threads that are using brk for something other
+			 * than malloc.
+			 */
+			do {
+				/* Get the current end of brk. */
+				brk_cur = sbrk(0);
+
+				/*
+				 * Calculate how much padding is necessary to
+				 * chunk-align the end of brk.
+				 */
+				incr = (char *)chunk_size
+				    - (char *)CHUNK_ADDR2OFFSET(brk_cur);
+				if (incr == chunk_size) {
+					ret = brk_cur;
+				} else {
+					ret = (char *)brk_cur + incr;
+					incr += chunk_size;
+				}
+
+				brk_prev = sbrk(incr);
+				if (brk_prev == brk_cur) {
+					/* Success. */
+					goto RETURN;
+				}
+			} while (brk_prev != (void *)-1);
+		}
+#endif
+	}
+
+	/*
+	 * Try to over-allocate, but allow the OS to place the allocation
+	 * anywhere.  Beware of size_t wrap-around.
+	 */
+	if (size + chunk_size > size) {
+		if ((ret = pages_map(NULL, size + chunk_size)) != NULL) {
+			size_t offset = CHUNK_ADDR2OFFSET(ret);
+
+			/*
+			 * Success.  Clean up unneeded leading/trailing space.
+			 */
+			if (offset != 0) {
+				/* Leading space. */
+				pages_unmap(ret, chunk_size - offset);
+
+				ret = (void *) ((size_t) ret + (chunk_size -
+				    offset));
+
+				/* Trailing space. */
+				pages_unmap((void *) ((size_t) ret + size),
+				    offset);
+			} else {
+				/* Trailing space only. */
+				pages_unmap((void *) ((size_t) ret + size),
+				    chunk_size);
+			}
+			goto RETURN;
+		}
+	}
+
+	/* All strategies for allocation failed. */
+	ret = NULL;
+RETURN:
+#ifdef MALLOC_STATS
+	if (ret != NULL) {
+		stats_chunks.nchunks += (size / chunk_size);
+		stats_chunks.curchunks += (size / chunk_size);
+	}
+	if (stats_chunks.curchunks > stats_chunks.highchunks)
+		stats_chunks.highchunks = stats_chunks.curchunks;
+#endif
+	malloc_mutex_unlock(&chunks_mtx);
+
+	/*
+	 * Deallocation of the chunk nodes must be done after releasing
+	 * chunks_mtx, in case deallocation causes a chunk to be unmapped.
+	 */
+	tchunk = RB_MIN(chunk_tree_s, &delchunks);
+	while (tchunk != NULL) {
+		delchunk = tchunk;
+		tchunk = RB_NEXT(chunk_tree_s, &delchunks, delchunk);
+		RB_REMOVE(chunk_tree_s, &delchunks, delchunk);
+		idalloc(delchunk);
+	}
+
+	assert(CHUNK_ADDR2BASE(ret) == ret);
+	return (ret);
+}
+
+static void
+chunk_dealloc(void *chunk, size_t size)
+{
+
+	assert(chunk != NULL);
+	assert(CHUNK_ADDR2BASE(chunk) == chunk);
+	assert(size != 0);
+	assert(size % chunk_size == 0);
+
+	if (size == chunk_size) {
+		chunk_node_t *node;
+
+		node = ipalloc(&base_arena, CACHELINE,
+		    sizeof(chunk_node_t) + CACHELINE);
+
+		malloc_mutex_lock(&chunks_mtx);
+		if (node != NULL) {
+			/*
+			 * Create a record of this chunk before deallocating
+			 * it, so that the address range can be recycled if
+			 * memory usage increases later on.
+			 */
+			node->arena = NULL;
+			node->chunk = chunk;
+			node->size = size;
+			node->extra = 0;
+
+			RB_INSERT(chunk_tree_s, &old_chunks, node);
+		}
+		malloc_mutex_unlock(&chunks_mtx);
+	}
+
+#ifdef USE_BRK
+	if ((size_t)chunk >= (size_t)brk_base
+	    && (size_t)chunk < (size_t)brk_max)
+		madvise(chunk, size, MADV_FREE);
+	else
+#endif
+		pages_unmap(chunk, size);
+
+#ifdef MALLOC_STATS
+	malloc_mutex_lock(&chunks_mtx);
+	stats_chunks.curchunks -= (size / chunk_size);
+	malloc_mutex_unlock(&chunks_mtx);
+#endif
+}
+
+/******************************************************************************/
 /*
- * Extend page directory
+ * arena.
  */
-static int
-extend_pgdir(u_long index)
-{
-    struct  pginfo **new, **old;
-    u_long i, oldlen;
-
-    /* Make it this many pages */
-    i = index * sizeof *page_dir;
-    i /= malloc_pagesize;
-    i += 2;
-
-    /* remember the old mapping size */
-    oldlen = malloc_ninfo * sizeof *page_dir;
-
-    /*
-     * NOTE: we allocate new pages and copy the directory rather than tempt
-     * fate by trying to "grow" the region.. There is nothing to prevent
-     * us from accidently re-mapping space that's been allocated by our caller
-     * via dlopen() or other mmap().
-     *
-     * The copy problem is not too bad, as there is 4K of page index per
-     * 4MB of malloc arena.
-     *
-     * We can totally avoid the copy if we open a file descriptor to associate
-     * the anon mappings with.  Then, when we remap the pages at the new
-     * address, the old pages will be "magically" remapped..  But this means
-     * keeping open a "secret" file descriptor.....
-     */
-
-    /* Get new pages */
-    new = (struct pginfo**) MMAP(i * malloc_pagesize);
-    if (new == MAP_FAILED)
-	return (0);
-
-    /* Copy the old stuff */
-    memcpy(new, page_dir,
-	    malloc_ninfo * sizeof *page_dir);
-
-    /* register the new size */
-    malloc_ninfo = i * malloc_pagesize / sizeof *page_dir;
-
-    /* swap the pointers */
-    old = page_dir;
-    page_dir = new;
-
-    /* Now free the old stuff */
-    munmap(old, oldlen);
-    return (1);
+
+static __inline void
+arena_mask_set(arena_t *arena, unsigned bin)
+{
+	unsigned elm, bit;
+
+	assert(bin < NBINS);
+
+	elm = bin / (sizeof(int) << 3);
+	bit = bin - (elm * (sizeof(int) << 3));
+	assert((arena->bins_mask[elm] & (1 << bit)) == 0);
+	arena->bins_mask[elm] |= (1 << bit);
+}
+
+static __inline void
+arena_mask_unset(arena_t *arena, unsigned bin)
+{
+	unsigned elm, bit;
+
+	assert(bin < NBINS);
+
+	elm = bin / (sizeof(int) << 3);
+	bit = bin - (elm * (sizeof(int) << 3));
+	assert((arena->bins_mask[elm] & (1 << bit)) != 0);
+	arena->bins_mask[elm] ^= (1 << bit);
+}
+
+static unsigned
+arena_bins_search(arena_t *arena, size_t size)
+{
+	unsigned ret, minbin, i;
+	int bit;
+
+	assert(QUANTUM_CEILING(size) == size);
+	assert((size >> opt_quantum_2pow) >= bin_shift);
+
+	if (size > bin_maxsize) {
+		ret = UINT_MAX;
+		goto RETURN;
+	}
+
+	minbin = (size >> opt_quantum_2pow) - bin_shift;
+	assert(minbin < NBINS);
+	for (i = minbin / (sizeof(int) << 3); i < BINMASK_NELMS; i++) {
+		bit = ffs(arena->bins_mask[i]
+		    & (UINT_MAX << (minbin % (sizeof(int) << 3))));
+		if (bit != 0) {
+			/* Usable allocation found. */
+			ret = (i * (sizeof(int) << 3)) + bit - 1;
+#ifdef MALLOC_STATS
+			if (ret == minbin)
+				arena->stats.bins[minbin].nfit++;
+			else
+				arena->stats.bins[ret].noverfit++;
+#endif
+			goto RETURN;
+		}
+	}
+
+	ret = UINT_MAX;
+RETURN:
+	return (ret);
+}
+
+static __inline void
+arena_delayed_extract(arena_t *arena, region_t *reg)
+{
+
+	if (region_next_contig_get(&reg->sep)) {
+		uint32_t slot;
+
+		/* Extract this region from the delayed FIFO. */
+		assert(region_next_free_get(&reg->sep) == false);
+
+		slot = reg->next.u.s.slot;
+		assert(arena->delayed[slot] == reg);
+		arena->delayed[slot] = NULL;
+	}
+#ifdef MALLOC_DEBUG
+	else {
+		region_t *next;
+
+		assert(region_next_free_get(&reg->sep));
+
+		next = (region_t *) &((char *) reg)
+		    [region_next_size_get(&reg->sep)];
+		assert(region_prev_free_get(&next->sep));
+	}
+#endif
+}
+
+static __inline void
+arena_bin_extract(arena_t *arena, unsigned bin, region_t *reg)
+{
+	arena_bin_t *tbin;
+
+	assert(bin < NBINS);
+
+	tbin = &arena->bins[bin];
+
+	assert(qr_next(&tbin->regions, next.u.s.link) != &tbin->regions);
+#ifdef MALLOC_DEBUG
+	{
+		region_t *next;
+
+		next = (region_t *) &((char *) reg)
+		    [region_next_size_get(&reg->sep)];
+		if (region_next_free_get(&reg->sep)) {
+			assert(region_prev_free_get(&next->sep));
+			assert(region_next_size_get(&reg->sep)
+			    == next->prev.size);
+		} else {
+			assert(region_prev_free_get(&next->sep) == false);
+		}
+	}
+#endif
+	assert(region_next_size_get(&reg->sep)
+	    == ((bin + bin_shift) << opt_quantum_2pow));
+
+	qr_remove(reg, next.u.s.link);
+#ifdef MALLOC_STATS
+	arena->stats.bins[bin].nregions--;
+#endif
+	if (qr_next(&tbin->regions, next.u.s.link) == &tbin->regions)
+		arena_mask_unset(arena, bin);
+
+	arena_delayed_extract(arena, reg);
+}
+
+static __inline void
+arena_extract(arena_t *arena, region_t *reg)
+{
+	size_t size;
+
+	assert(region_next_free_get(&reg->sep));
+#ifdef MALLOC_DEBUG
+	{
+		region_t *next;
+
+		next = (region_t *)&((char *)reg)
+		    [region_next_size_get(&reg->sep)];
+	}
+#endif
+
+	assert(reg != arena->split);
+	assert(reg != arena->frag);
+	if ((size = region_next_size_get(&reg->sep)) <= bin_maxsize) {
+		arena_bin_extract(arena, (size >> opt_quantum_2pow) - bin_shift,
+		    reg);
+	} else {
+		RB_REMOVE(region_tree_s, &arena->large_regions,
+		    &reg->next.u.l.node);
+#ifdef MALLOC_STATS
+		arena->stats.large.curcached--;
+#endif
+	}
+}
+
+/* Try to coalesce reg with its neighbors.  Return NULL if coalescing fails. */
+static bool
+arena_coalesce(arena_t *arena, region_t **reg, size_t size)
+{
+	bool ret;
+	region_t *prev, *treg, *next, *nextnext;
+	size_t tsize, prev_size, next_size;
+
+	ret = false;
+
+	treg = *reg;
+
+	/*
+	 * Keep track of the size while coalescing, then just set the size in
+	 * the header/footer once at the end of coalescing.
+	 */
+	assert(size == region_next_size_get(&(*reg)->sep));
+	tsize = size;
+
+	next = (region_t *)&((char *)treg)[tsize];
+	assert(region_next_free_get(&treg->sep));
+	assert(region_prev_free_get(&next->sep));
+	assert(region_next_size_get(&treg->sep) == next->prev.size);
+
+	while (region_prev_free_get(&treg->sep)) {
+		prev_size = treg->prev.size;
+		prev = (region_t *)&((char *)treg)[-prev_size];
+		assert(region_next_free_get(&prev->sep));
+
+		arena_extract(arena, prev);
+
+		tsize += prev_size;
+
+		treg = prev;
+
+#ifdef MALLOC_STATS
+		if (ret == false)
+			arena->stats.ncoalesce++;
+#endif
+		ret = true;
+	}
+
+	while (region_next_free_get(&next->sep)) {
+		next_size = region_next_size_get(&next->sep);
+		nextnext = (region_t *)&((char *)next)[next_size];
+		assert(region_prev_free_get(&nextnext->sep));
+
+		assert(region_next_size_get(&next->sep) == nextnext->prev.size);
+
+		arena_extract(arena, next);
+
+		assert(region_next_size_get(&next->sep) == nextnext->prev.size);
+
+		tsize += next_size;
+
+#ifdef MALLOC_STATS
+		if (ret == false)
+			arena->stats.ncoalesce++;
+#endif
+		ret = true;
+
+		next = (region_t *)&((char *)treg)[tsize];
+	}
+
+	/* Update header/footer. */
+	if (ret) {
+		region_next_size_set(&treg->sep, tsize);
+		next->prev.size = tsize;
+	}
+
+	/*
+	 * Now that coalescing with adjacent free regions is done, we need to
+	 * try to coalesce with "split" and "frag".  Those two regions are
+	 * marked as allocated, which is why this takes special effort.  There
+	 * are seven possible cases, but we want to make the (hopefully) common
+	 * case of no coalescence fast, so the checks are optimized for that
+	 * case.  The seven cases are:
+	 *
+	 *   /------\
+	 * 0 | treg | No coalescence needed.  Make this case fast.
+	 *   \------/
+	 *
+	 *   /------+------\
+	 * 1 | frag | treg |
+	 *   \------+------/
+	 *
+	 *   /------+------\
+	 * 2 | treg | frag |
+	 *   \------+------/
+	 *
+	 *   /-------+------\
+	 * 3 | split | treg |
+	 *   \-------+------/
+	 *
+	 *   /------+-------\
+	 * 4 | treg | split |
+	 *   \------+-------/
+	 *
+	 *   /------+------+-------\
+	 * 5 | frag | treg | split |
+	 *   \------+------+-------/
+	 *
+	 *   /-------+------+------\
+	 * 6 | split | treg | frag |
+	 *   \-------+------+------/
+	 */
+
+	if (arena->split == NULL) {
+		/* Cases 3-6 ruled out. */
+	} else if ((size_t)next < (size_t)arena->split) {
+		/* Cases 3-6 ruled out. */
+	} else {
+		region_t *split_next;
+		size_t split_size;
+
+		split_size = region_next_size_get(&arena->split->sep);
+		split_next = (region_t *)&((char *)arena->split)[split_size];
+
+		if ((size_t)split_next < (size_t)treg) {
+			/* Cases 3-6 ruled out. */
+		} else {
+			/*
+			 * Split is adjacent to treg.  Take the slow path and
+			 * coalesce.
+			 */
+
+			arena_coalesce_hard(arena, treg, next, tsize, true);
+
+			treg = NULL;
+#ifdef MALLOC_STATS
+			if (ret == false)
+				arena->stats.ncoalesce++;
+#endif
+			ret = true;
+			goto RETURN;
+		}
+	}
+
+	/* If we get here, then cases 3-6 have been ruled out. */
+	if (arena->frag == NULL) {
+		/* Cases 1-6 ruled out. */
+	} else if ((size_t)next < (size_t)arena->frag) {
+		/* Cases 1-6 ruled out. */
+	} else {
+		region_t *frag_next;
+		size_t frag_size;
+
+		frag_size = region_next_size_get(&arena->frag->sep);
+		frag_next = (region_t *)&((char *)arena->frag)[frag_size];
+
+		if ((size_t)frag_next < (size_t)treg) {
+			/* Cases 1-6 ruled out. */
+		} else {
+			/*
+			 * Frag is adjacent to treg.  Take the slow path and
+			 * coalesce.
+			 */
+
+			arena_coalesce_hard(arena, treg, next, tsize, false);
+
+			treg = NULL;
+#ifdef MALLOC_STATS
+			if (ret == false)
+				arena->stats.ncoalesce++;
+#endif
+			ret = true;
+			goto RETURN;
+		}
+	}
+
+	/* If we get here, no coalescence with "split" or "frag" was needed. */
+
+	/* Finish updating header. */
+	region_next_contig_unset(&treg->sep);
+
+	assert(region_next_free_get(&treg->sep));
+	assert(region_prev_free_get(&next->sep));
+	assert(region_prev_free_get(&treg->sep) == false);
+	assert(region_next_free_get(&next->sep) == false);
+
+RETURN:
+	if (ret)
+		*reg = treg;
+	return (ret);
 }
 
 /*
- * Initialize the world
+ * arena_coalesce() calls this function if it determines that a region needs to
+ * be coalesced with "split" and/or "frag".
  */
 static void
-malloc_init(void)
+arena_coalesce_hard(arena_t *arena, region_t *reg, region_t *next, size_t size,
+    bool split_adjacent)
 {
-    const char *p;
-    char b[64];
-    int i, j;
-    int save_errno = errno;
-
-    INIT_MMAP();
-
-#ifdef MALLOC_EXTRA_SANITY
-    malloc_junk = 1;
-#endif /* MALLOC_EXTRA_SANITY */
-
-    for (i = 0; i < 3; i++) {
-	if (i == 0) {
-	    j = readlink("/etc/malloc.conf", b, sizeof b - 1);
-	    if (j <= 0)
-		continue;
-	    b[j] = '\0';
-	    p = b;
-	} else if (i == 1 && issetugid() == 0) {
-	    p = getenv("MALLOC_OPTIONS");
-	} else if (i == 1) {
-	    continue;
+	bool frag_adjacent;
+
+	assert(next == (region_t *)&((char *)reg)[size]);
+	assert(region_next_free_get(&reg->sep));
+	assert(region_next_size_get(&reg->sep) == size);
+	assert(region_prev_free_get(&next->sep));
+	assert(next->prev.size == size);
+
+	if (split_adjacent == false)
+		frag_adjacent = true;
+	else if (arena->frag != NULL) {
+		/* Determine whether frag will be coalesced with. */
+
+		if ((size_t)next < (size_t)arena->frag)
+			frag_adjacent = false;
+		else {
+			region_t *frag_next;
+			size_t frag_size;
+
+			frag_size = region_next_size_get(&arena->frag->sep);
+			frag_next = (region_t *)&((char *)arena->frag)
+			    [frag_size];
+
+			if ((size_t)frag_next < (size_t)reg)
+				frag_adjacent = false;
+			else
+				frag_adjacent = true;
+		}
+	} else
+		frag_adjacent = false;
+
+	if (split_adjacent && frag_adjacent) {
+		region_t *a;
+		size_t a_size, b_size;
+
+		/* Coalesce all three regions. */
+
+		if (arena->frag == next)
+			a = arena->split;
+		else {
+			a = arena->frag;
+			arena->split = a;
+		}
+		arena->frag = NULL;
+
+		a_size = region_next_size_get(&a->sep);
+		assert(a_size == (size_t)reg - (size_t)a);
+
+		b_size = region_next_size_get(&next->sep);
+
+		region_next_size_set(&a->sep, a_size + size + b_size);
+		assert(region_next_free_get(&a->sep) == false);
 	} else {
-	    p = _malloc_options;
-	}
-	for (; p != NULL && *p != '\0'; p++) {
-	    switch (*p) {
-		case '>': malloc_cache   <<= 1; break;
-		case '<': malloc_cache   >>= 1; break;
-		case 'a': malloc_abort   = 0; break;
-		case 'A': malloc_abort   = 1; break;
-#if defined(MADV_FREE)
-		case 'h': malloc_hint    = 0; break;
-		case 'H': malloc_hint    = 1; break;
-#endif
-		case 'r': malloc_realloc = 0; break;
-		case 'R': malloc_realloc = 1; break;
-		case 'j': malloc_junk    = 0; break;
-		case 'J': malloc_junk    = 1; break;
-#ifdef HAS_UTRACE
-		case 'u': malloc_utrace  = 0; break;
-		case 'U': malloc_utrace  = 1; break;
-#endif
-		case 'v': malloc_sysv    = 0; break;
-		case 'V': malloc_sysv    = 1; break;
-		case 'x': malloc_xmalloc = 0; break;
-		case 'X': malloc_xmalloc = 1; break;
-		case 'z': malloc_zero    = 0; break;
-		case 'Z': malloc_zero    = 1; break;
-		default:
-		    _malloc_message(_getprogname(), malloc_func,
-			 " warning: ", "unknown char in MALLOC_OPTIONS\n");
-		    break;
-	    }
+		/* Coalesce two regions. */
+
+		if (split_adjacent) {
+			size += region_next_size_get(&arena->split->sep);
+			if (arena->split == next) {
+				/* reg comes before split. */
+				region_next_size_set(&reg->sep, size);
+				
+				assert(region_next_free_get(&reg->sep));
+				region_next_free_unset(&reg->sep);
+
+				arena->split = reg;
+			} else {
+				/* reg comes after split. */
+				region_next_size_set(&arena->split->sep, size);
+
+				assert(region_next_free_get(&arena->split->sep)
+				    == false);
+
+				assert(region_prev_free_get(&next->sep));
+				region_prev_free_unset(&next->sep);
+			}
+		} else {
+			assert(frag_adjacent);
+			size += region_next_size_get(&arena->frag->sep);
+			if (arena->frag == next) {
+				/* reg comes before frag. */
+				region_next_size_set(&reg->sep, size);
+
+				assert(region_next_free_get(&reg->sep));
+				region_next_free_unset(&reg->sep);
+
+				arena->frag = reg;
+			} else {
+				/* reg comes after frag. */
+				region_next_size_set(&arena->frag->sep, size);
+
+				assert(region_next_free_get(&arena->frag->sep)
+				    == false);
+
+				assert(region_prev_free_get(&next->sep));
+				region_prev_free_unset(&next->sep);
+			}
+		}
+	}
+}
+
+static __inline void
+arena_bin_append(arena_t *arena, unsigned bin, region_t *reg)
+{
+	arena_bin_t *tbin;
+
+	assert(bin < NBINS);
+	assert((region_next_size_get(&reg->sep) >> opt_quantum_2pow)
+	    >= bin_shift);
+	assert(region_next_size_get(&reg->sep)
+	    == ((bin + bin_shift) << opt_quantum_2pow));
+
+	tbin = &arena->bins[bin];
+
+	if (qr_next(&tbin->regions, next.u.s.link) == &tbin->regions)
+		arena_mask_set(arena, bin);
+
+	qr_new(reg, next.u.s.link);
+	qr_before_insert(&tbin->regions, reg, next.u.s.link);
+#ifdef MALLOC_STATS
+	arena->stats.bins[bin].nregions++;
+
+	if (arena->stats.bins[bin].nregions
+	    > arena->stats.bins[bin].highcached) {
+		arena->stats.bins[bin].highcached
+		    = arena->stats.bins[bin].nregions;
 	}
-    }
+#endif
+}
+
+static __inline void
+arena_bin_push(arena_t *arena, unsigned bin, region_t *reg)
+{
+	arena_bin_t *tbin;
 
+	assert(bin < NBINS);
+	assert((region_next_size_get(&reg->sep) >> opt_quantum_2pow)
+	    >= bin_shift);
+	assert(region_next_size_get(&reg->sep)
+	    == ((bin + bin_shift) << opt_quantum_2pow));
 
-    UTRACE(0, 0, 0);
+	tbin = &arena->bins[bin];
 
-    /*
-     * We want junk in the entire allocation, and zero only in the part
-     * the user asked for.
-     */
-    if (malloc_zero)
-	malloc_junk=1;
+	if (qr_next(&tbin->regions, next.u.s.link) == &tbin->regions)
+		arena_mask_set(arena, bin);
 
-    /* Allocate one page for the page directory */
-    page_dir = (struct pginfo **) MMAP(malloc_pagesize);
+	region_next_contig_unset(&reg->sep);
+	qr_new(reg, next.u.s.link);
+	qr_after_insert(&tbin->regions, reg, next.u.s.link);
+#ifdef MALLOC_STATS
+	arena->stats.bins[bin].nregions++;
 
-    if (page_dir == MAP_FAILED)
-	wrterror("mmap(2) failed, check limits\n");
+	if (arena->stats.bins[bin].nregions
+	    > arena->stats.bins[bin].highcached) {
+		arena->stats.bins[bin].highcached
+		    = arena->stats.bins[bin].nregions;
+	}
+#endif
+}
+
+static __inline region_t *
+arena_bin_pop(arena_t *arena, unsigned bin)
+{
+	region_t *ret;
+	arena_bin_t *tbin;
+
+	assert(bin < NBINS);
+
+	tbin = &arena->bins[bin];
 
-    /*
-     * We need a maximum of malloc_pageshift buckets, steal these from the
-     * front of the page_directory;
-     */
-    malloc_origo = ((u_long)pageround((u_long)sbrk(0))) >> malloc_pageshift;
-    malloc_origo -= malloc_pageshift;
+	assert(qr_next(&tbin->regions, next.u.s.link) != &tbin->regions);
 
-    malloc_ninfo = malloc_pagesize / sizeof *page_dir;
+	ret = qr_next(&tbin->regions, next.u.s.link);
+	assert(region_next_size_get(&ret->sep)
+	    == ((bin + bin_shift) << opt_quantum_2pow));
+	qr_remove(ret, next.u.s.link);
+#ifdef MALLOC_STATS
+	arena->stats.bins[bin].nregions--;
+#endif
+	if (qr_next(&tbin->regions, next.u.s.link) == &tbin->regions)
+		arena_mask_unset(arena, bin);
+
+	arena_delayed_extract(arena, ret);
 
-    /* Recalculate the cache size in bytes, and make sure it's nonzero */
+	if (region_next_free_get(&ret->sep)) {
+		region_t *next;
 
-    if (!malloc_cache)
-	malloc_cache++;
+		/* Non-delayed region. */
+		region_next_free_unset(&ret->sep);
 
-    malloc_cache <<= malloc_pageshift;
+		next = (region_t *)&((char *)ret)
+		    [(bin + bin_shift) << opt_quantum_2pow];
+		assert(next->prev.size == region_next_size_get(&ret->sep));
+		assert(region_prev_free_get(&next->sep));
+		region_prev_free_unset(&next->sep);
+	}
 
-    /*
-     * This is a nice hack from Kaleb Keithly (kaleb@x.org).
-     * We can sbrk(2) further back when we keep this on a low address.
-     */
-    px = (struct pgfree *) imalloc (sizeof *px);
-    errno = save_errno;
+	return (ret);
 }
 
-/*
- * Allocate a number of complete pages
- */
-static void *
-malloc_pages(size_t size)
-{
-    void *p, *delay_free = NULL;
-    size_t i;
-    struct pgfree *pf;
-    u_long index;
-
-    size = pageround(size);
-
-    p = NULL;
-
-    /* Look for free pages before asking for more */
-    for(pf = free_list.next; pf; pf = pf->next) {
-
-#ifdef MALLOC_EXTRA_SANITY
-	if (pf->size & malloc_pagemask)
-	    wrterror("(ES): junk length entry on free_list\n");
-	if (!pf->size)
-	    wrterror("(ES): zero length entry on free_list\n");
-	if (pf->page == pf->end)
-	    wrterror("(ES): zero entry on free_list\n");
-	if (pf->page > pf->end)
-	    wrterror("(ES): sick entry on free_list\n");
-	if ((void*)pf->page >= (void*)sbrk(0))
-	    wrterror("(ES): entry on free_list past brk\n");
-	if (page_dir[ptr2index(pf->page)] != MALLOC_FREE)
-	    wrterror("(ES): non-free first page on free-list\n");
-	if (page_dir[ptr2index(pf->end)-1] != MALLOC_FREE)
-	    wrterror("(ES): non-free last page on free-list\n");
-#endif /* MALLOC_EXTRA_SANITY */
-
-	if (pf->size < size)
-	    continue;
-
-	if (pf->size == size) {
-	    p = pf->page;
-	    if (pf->next != NULL)
-		    pf->next->prev = pf->prev;
-	    pf->prev->next = pf->next;
-	    delay_free = pf;
-	    break;
-	}
-
-	p = pf->page;
-	pf->page = (char *)pf->page + size;
-	pf->size -= size;
-	break;
-    }
-
-#ifdef MALLOC_EXTRA_SANITY
-    if (p != NULL && page_dir[ptr2index(p)] != MALLOC_FREE)
-	wrterror("(ES): allocated non-free page on free-list\n");
-#endif /* MALLOC_EXTRA_SANITY */
-
-    size >>= malloc_pageshift;
-
-    /* Map new pages */
-    if (p == NULL)
-	p = map_pages(size);
-
-    if (p != NULL) {
-
-	index = ptr2index(p);
-	page_dir[index] = MALLOC_FIRST;
-	for (i=1;i<size;i++)
-	    page_dir[index+i] = MALLOC_FOLLOW;
-
-	if (malloc_junk)
-	    memset(p, SOME_JUNK, size << malloc_pageshift);
-    }
-
-    if (delay_free) {
-	if (px == NULL)
-	    px = delay_free;
-	else
-	    ifree(delay_free);
-    }
+static void
+arena_large_insert(arena_t *arena, region_t *reg, bool lru)
+{
 
-    return (p);
+	assert(region_next_free_get(&reg->sep));
+#ifdef MALLOC_DEBUG
+	{
+		region_t *next;
+
+		next = (region_t *)&((char *)reg)
+		    [region_next_size_get(&reg->sep)];
+		assert(region_prev_free_get(&next->sep));
+		assert(next->prev.size == region_next_size_get(&reg->sep));
+	}
+#endif
+
+	/* Coalescing should have already been done. */
+	assert(arena_coalesce(arena, &reg, region_next_size_get(&reg->sep))
+	    == false);
+
+	if (region_next_size_get(&reg->sep) < chunk_size
+	    - (CHUNK_REG_OFFSET + offsetof(region_t, next))) {
+		/*
+		 * Make sure not to cache a large region with the nextContig
+		 * flag set, in order to simplify the logic that determines
+		 * whether a region needs to be extracted from "delayed".
+		 */
+		region_next_contig_unset(&reg->sep);
+
+		/* Store the region in the large_regions tree. */
+		reg->next.u.l.node.reg = reg;
+		reg->next.u.l.lru = lru;
+
+		RB_INSERT(region_tree_s, &arena->large_regions,
+		    &reg->next.u.l.node);
+#ifdef MALLOC_STATS
+		arena->stats.large.curcached++;
+		if (arena->stats.large.curcached
+		    > arena->stats.large.highcached) {
+			arena->stats.large.highcached
+			    = arena->stats.large.curcached;
+		}
+#endif
+	} else {
+		chunk_node_t *node;
+
+		/*
+		 * This region now spans an entire chunk. Deallocate the chunk.
+		 *
+		 * Note that it is possible for allocation of a large region
+		 * from a pristine chunk, followed by deallocation of the
+		 * region, can cause the chunk to immediately be unmapped.
+		 * This isn't ideal, but 1) such scenarios seem unlikely, and
+		 * 2) delaying coalescence for large regions could cause
+		 * excessive fragmentation for common scenarios.
+		 */
+
+		node = (chunk_node_t *)CHUNK_ADDR2BASE(reg);
+		RB_REMOVE(chunk_tree_s, &arena->chunks, node);
+		arena->nchunks--;
+		assert(node->chunk == (chunk_node_t *)node);
+		chunk_dealloc(node->chunk, chunk_size);
+	}
 }
 
-/*
- * Allocate a page of fragments
- */
+static void
+arena_large_cache(arena_t *arena, region_t *reg, bool lru)
+{
+	size_t size;
+
+	/* Try to coalesce before storing this region anywhere. */
+	size = region_next_size_get(&reg->sep);
+	if (arena_coalesce(arena, &reg, size)) {
+		if (reg == NULL) {
+			/* Region no longer needs cached. */
+			return;
+		}
+		size = region_next_size_get(&reg->sep);
+	}
 
-static __inline int
-malloc_make_chunks(int bits)
+	arena_large_insert(arena, reg, lru);
+}
+
+static void
+arena_lru_cache(arena_t *arena, region_t *reg)
+{
+	size_t size;
+
+	assert(region_next_free_get(&reg->sep));
+#ifdef MALLOC_DEBUG
+	{
+		region_t *next;
+
+		next = (region_t *)&((char *)reg)
+		    [region_next_size_get(&reg->sep)];
+		assert(region_prev_free_get(&next->sep));
+		assert(next->prev.size == region_next_size_get(&reg->sep));
+	}
+#endif
+	assert(region_next_size_get(&reg->sep) % quantum == 0);
+	assert(region_next_size_get(&reg->sep)
+	    >= QUANTUM_CEILING(sizeof(region_small_sizer_t)));
+
+	size = region_next_size_get(&reg->sep);
+	if (size <= bin_maxsize) {
+		arena_bin_append(arena, (size >> opt_quantum_2pow) - bin_shift,
+		    reg);
+	} else
+		arena_large_cache(arena, reg, true);
+}
+
+static __inline void
+arena_mru_cache(arena_t *arena, region_t *reg, size_t size)
+{
+
+	assert(region_next_free_get(&reg->sep));
+#ifdef MALLOC_DEBUG
+	{
+		region_t *next;
+
+		next = (region_t *)&((char *)reg)
+		    [region_next_size_get(&reg->sep)];
+		assert(region_prev_free_get(&next->sep));
+		assert(next->prev.size == region_next_size_get(&reg->sep));
+	}
+#endif
+	assert(region_next_size_get(&reg->sep) % quantum == 0);
+	assert(region_next_size_get(&reg->sep)
+	    >= QUANTUM_CEILING(sizeof(region_small_sizer_t)));
+	assert(size == region_next_size_get(&reg->sep));
+
+	if (size <= bin_maxsize) {
+		arena_bin_push(arena, (size >> opt_quantum_2pow) - bin_shift,
+		    reg);
+	} else
+		arena_large_cache(arena, reg, false);
+}
+
+static __inline void
+arena_undelay(arena_t *arena, uint32_t slot)
 {
-    struct  pginfo *bp;
-    void *pp;
-    int i, k, l;
+	region_t *reg, *next;
+	size_t size;
+
+	assert(slot == arena->next_delayed);
+	assert(arena->delayed[slot] != NULL);
+
+	/* Try to coalesce reg. */
+	reg = arena->delayed[slot];
+
+	size = region_next_size_get(&reg->sep);
+
+	assert(region_next_contig_get(&reg->sep));
+	assert(reg->next.u.s.slot == slot);
+
+	arena_bin_extract(arena, (size >> opt_quantum_2pow) - bin_shift, reg);
+
+	arena->delayed[slot] = NULL;
+
+	next = (region_t *) &((char *) reg)[size];
+
+	region_next_free_set(&reg->sep);
+	region_prev_free_set(&next->sep);
+	next->prev.size = size;
 
-    /* Allocate a new bucket */
-    pp = malloc_pages(malloc_pagesize);
-    if (pp == NULL)
-	return (0);
+	if (arena_coalesce(arena, &reg, size) == false) {
+		/* Coalescing failed.  Cache this region. */
+		arena_mru_cache(arena, reg, size);
+	} else {
+		/* Coalescing succeeded. */
+
+		if (reg == NULL) {
+			/* Region no longer needs undelayed. */
+			return;
+		}
+
+		if (region_next_size_get(&reg->sep) < chunk_size
+		    - (CHUNK_REG_OFFSET + offsetof(region_t, next))) {
+			/*
+			 * Insert coalesced region into appropriate bin (or
+			 * largeRegions).
+			 */
+			arena_lru_cache(arena, reg);
+		} else {
+			chunk_node_t *node;
+
+			/*
+			 * This region now spans an entire chunk.  Deallocate
+			 * the chunk.
+			 */
+
+			node = (chunk_node_t *) CHUNK_ADDR2BASE(reg);
+			RB_REMOVE(chunk_tree_s, &arena->chunks, node);
+			arena->nchunks--;
+			assert(node->chunk == (chunk_node_t *) node);
+			chunk_dealloc(node->chunk, chunk_size);
+		}
+	}
+}
 
-    /* Find length of admin structure */
-    l = offsetof(struct pginfo, bits[0]);
-    l += sizeof bp->bits[0] *
-	(((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
+static void
+arena_delay_cache(arena_t *arena, region_t *reg)
+{
+	region_t *next;
+	size_t size;
+
+	assert(region_next_free_get(&reg->sep) == false);
+	assert(region_next_size_get(&reg->sep) % quantum == 0);
+	assert(region_next_size_get(&reg->sep)
+	    >= QUANTUM_CEILING(sizeof(region_small_sizer_t)));
+
+	size = region_next_size_get(&reg->sep);
+	next = (region_t *)&((char *)reg)[size];
+	assert(region_prev_free_get(&next->sep) == false);
+
+	if (size <= bin_maxsize) {
+		if (region_next_contig_get(&reg->sep)) {
+			uint32_t slot;
+
+			/* Insert into delayed. */
+
+			/*
+			 * Clear a slot, then put reg in it.  We have to loop
+			 * here, because in the case of base_arena, it's
+			 * possible for this loop to cause deallocation if a
+			 * chunk is discarded.
+			 */
+			for (slot = arena->next_delayed;
+			    arena->delayed[slot] != NULL;
+			    slot = arena->next_delayed)
+				arena_undelay(arena, slot);
+
+			reg->next.u.s.slot = slot;
+
+			arena->delayed[slot] = reg;
+
+			/* Update next_delayed. */
+			slot++;
+			slot &= (opt_ndelay - 1); /* Handle wrap-around. */
+			arena->next_delayed = slot;
+
+			arena_bin_append(arena, (size >> opt_quantum_2pow)
+			    - bin_shift, reg);
+		} else {
+			/*
+			 * This region was a fragment when it was allocated, so
+			 * don't delay coalescence for it.
+			 */
+
+			region_next_free_set(&reg->sep);
+			region_prev_free_set(&next->sep);
+			next->prev.size = size;
+
+			if (arena_coalesce(arena, &reg, size)) {
+				/* Coalescing succeeded. */
+
+				if (reg == NULL) {
+					/* Region no longer needs cached. */
+					return;
+				}
+
+				size = region_next_size_get(&reg->sep);
+			}
+
+			arena_mru_cache(arena, reg, size);
+		}
+	} else {
+		region_next_free_set(&reg->sep);
+		region_prev_free_set(&next->sep);
+		region_next_contig_unset(&reg->sep);
+		next->prev.size = size;
 
-    /* Don't waste more than two chunks on this */
-    if ((1<<(bits)) <= l+l) {
-	bp = (struct  pginfo *)pp;
-    } else {
-	bp = (struct  pginfo *)imalloc(l);
-	if (bp == NULL) {
-	    ifree(pp);
-	    return (0);
+		arena_large_cache(arena, reg, true);
 	}
-    }
+}
 
-    bp->size = (1<<bits);
-    bp->shift = bits;
-    bp->total = bp->free = malloc_pagesize >> bits;
-    bp->page = pp;
+static __inline region_t *
+arena_frag_reg_alloc(arena_t *arena, size_t size, bool fit)
+{
+	region_t *ret;
 
-    /* set all valid bits in the bitmap */
-    k = bp->total;
-    i = 0;
+	/*
+	 * Try to fill frag if it's empty.  Frag needs to be marked as
+	 * allocated.
+	 */
+	if (arena->frag == NULL) {
+		region_node_t *node;
 
-    /* Do a bunch at a time */
-    for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
-	bp->bits[i / MALLOC_BITS] = ~0;
+		node = RB_MIN(region_tree_s, &arena->large_regions);
+		if (node != NULL) {
+			region_t *frag, *next;
 
-    for(; i < k; i++)
-        bp->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS);
+			RB_REMOVE(region_tree_s, &arena->large_regions, node);
 
-    if (bp == bp->page) {
-	/* Mark the ones we stole for ourselves */
-	for(i=0;l > 0;i++) {
-	    bp->bits[i/MALLOC_BITS] &= ~(1<<(i%MALLOC_BITS));
-	    bp->free--;
-	    bp->total--;
-	    l -= (1 << bits);
+			frag = node->reg;
+#ifdef MALLOC_STATS
+			arena->stats.frag.ncached++;
+#endif
+			assert(region_next_free_get(&frag->sep));
+			region_next_free_unset(&frag->sep);
+
+			next = (region_t *)&((char *)frag)[region_next_size_get(
+			    &frag->sep)];
+			assert(region_prev_free_get(&next->sep));
+			region_prev_free_unset(&next->sep);
+
+			arena->frag = frag;
+		}
 	}
-    }
 
-    /* MALLOC_LOCK */
+	if (arena->frag != NULL) {
+#ifdef MALLOC_STATS
+		arena->stats.frag.nrequests++;
+#endif
+
+		if (region_next_size_get(&arena->frag->sep) >= size) {
+			if (fit) {
+				size_t total_size;
+
+				/*
+				 * Use frag, but try to use the beginning for
+				 * smaller regions, and the end for larger
+				 * regions.  This reduces fragmentation in some
+				 * pathological use cases.  It tends to group
+				 * short-lived (smaller) regions, which
+				 * increases the effectiveness of coalescing.
+				 */
+
+				total_size =
+				    region_next_size_get(&arena->frag->sep);
+				assert(size % quantum == 0);
+
+				if (total_size - size >= QUANTUM_CEILING(
+				    sizeof(region_small_sizer_t))) {
+					if (size <= bin_maxsize) {
+						region_t *next;
+
+						/*
+						 * Carve space from the
+						 * beginning of frag.
+						 */
+
+						/* ret. */
+						ret = arena->frag;
+						region_next_size_set(&ret->sep,
+						    size);
+						assert(region_next_free_get(
+						    &ret->sep) == false);
+
+						/* next. */
+						next = (region_t *)&((char *)
+						    ret)[size];
+						region_next_size_set(&next->sep,
+						    total_size - size);
+						assert(size >=
+						    QUANTUM_CEILING(sizeof(
+						    region_small_sizer_t)));
+						region_prev_free_unset(
+						    &next->sep);
+						region_next_free_unset(
+						    &next->sep);
+
+						/* Update frag. */
+						arena->frag = next;
+					} else {
+						region_t *prev;
+						size_t prev_size;
+
+						/*
+						 * Carve space from the end of
+						 * frag.
+						 */
+
+						/* prev. */
+						prev_size = total_size - size;
+						prev = arena->frag;
+						region_next_size_set(&prev->sep,
+						    prev_size);
+						assert(prev_size >=
+						    QUANTUM_CEILING(sizeof(
+						    region_small_sizer_t)));
+						assert(region_next_free_get(
+						    &prev->sep) == false);
+
+						/* ret. */
+						ret = (region_t *)&((char *)
+						    prev)[prev_size];
+						region_next_size_set(&ret->sep,
+						    size);
+						region_prev_free_unset(
+						    &ret->sep);
+						region_next_free_unset(
+						    &ret->sep);
+
+#ifdef MALLOC_DEBUG
+						{
+					region_t *next;
+
+					/* next. */
+					next = (region_t *)&((char *) ret)
+					    [region_next_size_get(&ret->sep)];
+					assert(region_prev_free_get(&next->sep)
+					    == false);
+						}
+#endif
+					}
+#ifdef MALLOC_STATS
+					arena->stats.nsplit++;
+#endif
+				} else {
+					/*
+					 * frag is close enough to the right
+					 * size that there isn't enough room to
+					 * create a neighboring region.
+					 */
+
+					/* ret. */
+					ret = arena->frag;
+					arena->frag = NULL;
+					assert(region_next_free_get(&ret->sep)
+					    == false);
+
+#ifdef MALLOC_DEBUG
+					{
+						region_t *next;
+
+						/* next. */
+						next = (region_t *)&((char *)
+						    ret)[region_next_size_get(
+						    &ret->sep)];
+						assert(region_prev_free_get(
+						    &next->sep) == false);
+					}
+#endif
+				}
+#ifdef MALLOC_STATS
+				arena->stats.frag.nserviced++;
+#endif
+			} else {
+				/* Don't fit to the allocation size. */
+
+				/* ret. */
+				ret = arena->frag;
+				arena->frag = NULL;
+				assert(region_next_free_get(&ret->sep)
+				    == false);
+
+#ifdef MALLOC_DEBUG
+				{
+					region_t *next;
+
+					/* next. */
+					next = (region_t *) &((char *) ret)
+					   [region_next_size_get(&ret->sep)];
+					assert(region_prev_free_get(&next->sep)
+					    == false);
+				}
+#endif
+			}
+			region_next_contig_set(&ret->sep);
+			goto RETURN;
+		} else if (size <= bin_maxsize) {
+			region_t *reg;
+
+			/*
+			 * The frag region is too small to service a small
+			 * request.  Clear frag.
+			 */
 
-    page_dir[ptr2index(pp)] = bp;
+			reg = arena->frag;
+			region_next_contig_set(&reg->sep);
 
-    bp->next = page_dir[bits];
-    page_dir[bits] = bp;
+			arena->frag = NULL;
 
-    /* MALLOC_UNLOCK */
+			arena_delay_cache(arena, reg);
+		}
+	}
 
-    return (1);
+	ret = NULL;
+RETURN:
+	return (ret);
 }
 
-/*
- * Allocate a fragment
- */
-static void *
-malloc_bytes(size_t size)
-{
-    int i,j;
-    u_int u;
-    struct  pginfo *bp;
-    int k;
-    u_int *lp;
-
-    /* Don't bother with anything less than this */
-    if (size < malloc_minsize)
-	size = malloc_minsize;
-
-    /* Find the right bucket */
-    j = 1;
-    i = size-1;
-    while (i >>= 1)
-	j++;
-
-    /* If it's empty, make a page more of that size chunks */
-    if (page_dir[j] == NULL && !malloc_make_chunks(j))
-	return (NULL);
+static region_t *
+arena_split_reg_alloc(arena_t *arena, size_t size, bool fit)
+{
+	region_t *ret;
+
+	if (arena->split != NULL) {
+#ifdef MALLOC_STATS
+		arena->stats.split.nrequests++;
+#endif
 
-    bp = page_dir[j];
+		if (region_next_size_get(&arena->split->sep) >= size) {
+			if (fit) {
+				size_t total_size;
+
+				/*
+				 * Use split, but try to use the beginning for
+				 * smaller regions, and the end for larger
+				 * regions.  This reduces fragmentation in some
+				 * pathological use cases.  It tends to group
+				 * short-lived (smaller) regions, which
+				 * increases the effectiveness of coalescing.
+				 */
+
+				total_size =
+				    region_next_size_get(&arena->split->sep);
+				assert(size % quantum == 0);
+
+				if (total_size - size >= QUANTUM_CEILING(
+				    sizeof(region_small_sizer_t))) {
+					if (size <= bin_maxsize) {
+						region_t *next;
+
+						/*
+						 * Carve space from the
+						 * beginning of split.
+						 */
+
+						/* ret. */
+						ret = arena->split;
+						region_next_size_set(&ret->sep,
+						    size);
+						assert(region_next_free_get(
+						    &ret->sep) == false);
+
+						/* next. */
+						next = (region_t *)&((char *)
+						    ret)[size];
+						region_next_size_set(&next->sep,
+						    total_size - size);
+						assert(size >=
+						    QUANTUM_CEILING(sizeof(
+						    region_small_sizer_t)));
+						region_prev_free_unset(
+						    &next->sep);
+						region_next_free_unset(
+						    &next->sep);
+
+						/* Update split. */
+						arena->split = next;
+					} else {
+						region_t *prev;
+						size_t prev_size;
+
+						/*
+						 * Carve space from the end of
+						 * split.
+						 */
+
+						/* prev. */
+						prev_size = total_size - size;
+						prev = arena->split;
+						region_next_size_set(&prev->sep,
+						    prev_size);
+						assert(prev_size >=
+						    QUANTUM_CEILING(sizeof(
+						    region_small_sizer_t)));
+						assert(region_next_free_get(
+						    &prev->sep) == false);
+
+						/* ret. */
+						ret = (region_t *)&((char *)
+						    prev)[prev_size];
+						region_next_size_set(&ret->sep,
+						    size);
+						region_prev_free_unset(
+						    &ret->sep);
+						region_next_free_unset(
+						    &ret->sep);
+
+#ifdef MALLOC_DEBUG
+						{
+					region_t *next;
+
+					/* next. */
+					next = (region_t *)&((char *) ret)
+					    [region_next_size_get(&ret->sep)];
+					assert(region_prev_free_get(&next->sep)
+					    == false);
+						}
+#endif
+					}
+#ifdef MALLOC_STATS
+					arena->stats.nsplit++;
+#endif
+				} else {
+					/*
+					 * split is close enough to the right
+					 * size that there isn't enough room to
+					 * create a neighboring region.
+					 */
+
+					/* ret. */
+					ret = arena->split;
+					arena->split = NULL;
+					assert(region_next_free_get(&ret->sep)
+					    == false);
+
+#ifdef MALLOC_DEBUG
+					{
+						region_t *next;
+
+						/* next. */
+						next = (region_t *)&((char *)
+						    ret)[region_next_size_get(
+						    &ret->sep)];
+						assert(region_prev_free_get(
+						    &next->sep) == false);
+					}
+#endif
+				}
 
-    /* Find first word of bitmap which isn't empty */
-    for (lp = bp->bits; !*lp; lp++)
-	;
+#ifdef MALLOC_STATS
+				arena->stats.split.nserviced++;
+#endif
+			} else {
+				/* Don't fit to the allocation size. */
+
+				/* ret. */
+				ret = arena->split;
+				arena->split = NULL;
+				assert(region_next_free_get(&ret->sep)
+				    == false);
+
+#ifdef MALLOC_DEBUG
+				{
+					region_t *next;
+
+					/* next. */
+					next = (region_t *) &((char *) ret)
+					   [region_next_size_get(&ret->sep)];
+					assert(region_prev_free_get(&next->sep)
+					    == false);
+				}
+#endif
+			}
+			region_next_contig_set(&ret->sep);
+			goto RETURN;
+		} else if (size <= bin_maxsize) {
+			region_t *reg;
 
-    /* Find that bit, and tweak it */
-    u = 1;
-    k = 0;
-    while (!(*lp & u)) {
-	u += u;
-	k++;
-    }
-    *lp ^= u;
+			/*
+			 * The split region is too small to service a small
+			 * request.  Clear split.
+			 */
 
-    /* If there are no more free, remove from free-list */
-    if (!--bp->free) {
-	page_dir[j] = bp->next;
-	bp->next = NULL;
-    }
+			reg = arena->split;
+			region_next_contig_set(&reg->sep);
 
-    /* Adjust to the real offset of that chunk */
-    k += (lp-bp->bits)*MALLOC_BITS;
-    k <<= bp->shift;
+			arena->split = NULL;
 
-    if (malloc_junk)
-	memset((u_char *)bp->page + k, SOME_JUNK, bp->size);
+			arena_delay_cache(arena, reg);
+		}
+	}
 
-    return ((u_char *)bp->page + k);
+	ret = NULL;
+RETURN:
+	return (ret);
 }
 
 /*
- * Allocate a piece of memory
+ * Split reg if necessary.  The region must be overly large enough to be able
+ * to contain a trailing region.
  */
-static void *
-imalloc(size_t size)
+static void
+arena_reg_fit(arena_t *arena, size_t size, region_t *reg, bool restore_split)
 {
-    void *result;
+	assert(QUANTUM_CEILING(size) == size);
+	assert(region_next_free_get(&reg->sep) == 0);
+
+	if (region_next_size_get(&reg->sep)
+	    >= size + QUANTUM_CEILING(sizeof(region_small_sizer_t))) {
+		size_t total_size;
+		region_t *next;
+
+		total_size = region_next_size_get(&reg->sep);
+
+		region_next_size_set(&reg->sep, size);
+
+		next = (region_t *) &((char *) reg)[size];
+		region_next_size_set(&next->sep, total_size - size);
+		assert(region_next_size_get(&next->sep)
+		    >= QUANTUM_CEILING(sizeof(region_small_sizer_t)));
+		region_prev_free_unset(&next->sep);
+
+		if (restore_split) {
+			/* Restore what's left to "split". */
+			region_next_free_unset(&next->sep);
+			arena->split = next;
+		} else if (arena->frag == NULL && total_size - size
+		    > bin_maxsize) {
+			/* This region is large enough to use for "frag". */
+			region_next_free_unset(&next->sep);
+			arena->frag = next;
+		} else {
+			region_t *nextnext;
+			size_t next_size;
+
+			region_next_free_set(&next->sep);
+
+			assert(region_next_size_get(&next->sep) == total_size
+			    - size);
+			next_size = total_size - size;
+			nextnext = (region_t *) &((char *) next)[next_size];
+			nextnext->prev.size = next_size;
+			assert(region_prev_free_get(&nextnext->sep) == false);
+			region_prev_free_set(&nextnext->sep);
+
+			arena_mru_cache(arena, next, next_size);
+		}
+
+#ifdef MALLOC_STATS
+		arena->stats.nsplit++;
+#endif
+	}
+}
 
-    if (suicide)
-	abort();
+static __inline region_t *
+arena_bin_reg_alloc(arena_t *arena, size_t size, bool fit)
+{
+	region_t *ret, *header;
+	unsigned bin;
 
-    if ((size + malloc_pagesize) < size)	/* Check for overflow */
-	result = NULL;
-    else if ((size + malloc_pagesize) >= (uintptr_t)page_dir)
-	result = NULL;
-    else if (size <= malloc_maxsize)
-	result = malloc_bytes(size);
-    else
-	result = malloc_pages(size);
+	/*
+	 * Look for an exact fit in bins (region cached in smallest possible
+	 * bin).
+	 */
+	bin = (size >> opt_quantum_2pow) - bin_shift;
+#ifdef MALLOC_STATS
+	arena->stats.bins[bin].nrequests++;
+#endif
+	header = &arena->bins[bin].regions;
+	if (qr_next(header, next.u.s.link) != header) {
+		/* Exact fit. */
+		ret = arena_bin_pop(arena, bin);
+		assert(region_next_size_get(&ret->sep) >= size);
+#ifdef MALLOC_STATS
+		arena->stats.bins[bin].nfit++;
+#endif
+		goto RETURN;
+	}
+
+	/* Look at frag to see whether it's large enough. */
+	ret = arena_frag_reg_alloc(arena, size, fit);
+	if (ret != NULL)
+		goto RETURN;
+
+	/* Look in all bins for a large enough region. */
+	if ((bin = arena_bins_search(arena, size)) == (size >> opt_quantum_2pow)
+	    - bin_shift) {
+		/* Over-fit. */
+		ret = arena_bin_pop(arena, bin);
+		assert(region_next_size_get(&ret->sep) >= size);
+
+		if (fit)
+			arena_reg_fit(arena, size, ret, false);
+
+#ifdef MALLOC_STATS
+		arena->stats.bins[bin].noverfit++;
+#endif
+		goto RETURN;
+	}
+
+	ret = NULL;
+RETURN:
+	return (ret);
+}
+
+/* Look in large_regions for a large enough region. */
+static region_t *
+arena_large_reg_alloc(arena_t *arena, size_t size, bool fit)
+{
+	region_t *ret, *next;
+	region_node_t *node;
+	region_t key;
+
+#ifdef MALLOC_STATS
+	arena->stats.large.nrequests++;
+#endif
+
+	key.next.u.l.node.reg = &key;
+	key.next.u.l.lru = true;
+	region_next_size_set(&key.sep, size);
+	node = RB_NFIND(region_tree_s, &arena->large_regions,
+	    &key.next.u.l.node);
+	if (node == NULL) {
+		ret = NULL;
+		goto RETURN;
+	}
+
+	/* Cached large region found. */
+	ret = node->reg;
+	assert(region_next_free_get(&ret->sep));
+
+	RB_REMOVE(region_tree_s, &arena->large_regions, node);
+#ifdef MALLOC_STATS
+	arena->stats.large.curcached--;
+#endif
+
+	region_next_free_unset(&ret->sep);
+
+	next = (region_t *)&((char *)ret)[region_next_size_get(&ret->sep)];
+	assert(region_prev_free_get(&next->sep));
+	region_prev_free_unset(&next->sep);
+
+	if (fit)
+		arena_reg_fit(arena, size, ret, false);
+
+#ifdef MALLOC_STATS
+	if (size > bin_maxsize)
+		arena->stats.large.nfit++;
+	else
+		arena->stats.large.noverfit++;
+#endif
+
+RETURN:
+	return (ret);
+}
+
+/* Allocate a new chunk and create a single region from it. */
+static region_t *
+arena_chunk_reg_alloc(arena_t *arena, size_t size, bool fit)
+{
+	region_t *ret, *next;
+	chunk_node_t *chunk;
 
-    if (malloc_zero && result != NULL)
-	memset(result, 0, size);
+	chunk = chunk_alloc(chunk_size);
+	if (chunk == NULL) {
+		ret = NULL;
+		goto RETURN;
+	}
 
-    return (result);
+#ifdef MALLOC_DEBUG
+	{
+		chunk_node_t *tchunk;
+		chunk_node_t key;
+
+		key.chunk = chunk;
+		tchunk = RB_FIND(chunk_tree_s, &arena->chunks, &key);
+		assert(tchunk == NULL);
+	}
+#endif
+	chunk->arena = arena;
+	chunk->chunk = chunk;
+	chunk->size = chunk_size;
+	chunk->extra = 0;
+
+	RB_INSERT(chunk_tree_s, &arena->chunks, chunk);
+	arena->nchunks++;
+
+	/* Carve a region from the new chunk. */
+	ret = (region_t *) &((char *) chunk)[CHUNK_REG_OFFSET];
+	region_next_size_set(&ret->sep, chunk_size - (CHUNK_REG_OFFSET
+	    + offsetof(region_t, next)));
+	region_prev_free_unset(&ret->sep);
+	region_next_free_unset(&ret->sep);
+
+	/* Create a separator at the end of this new region. */
+	next = (region_t *)&((char *)ret)[region_next_size_get(&ret->sep)];
+	region_next_size_set(&next->sep, 0);
+	region_prev_free_unset(&next->sep);
+	region_next_free_unset(&next->sep);
+	region_next_contig_unset(&next->sep);
+
+	if (fit)
+		arena_reg_fit(arena, size, ret, (arena->split == NULL));
+
+RETURN:
+	return (ret);
 }
 
 /*
- * Change the size of an allocation.
+ * Find a region that is at least as large as aSize, and return a pointer to
+ * the separator that precedes the region.  The return value is ready for use,
+ * though it may be larger than is necessary if fit is false.
  */
+static __inline region_t *
+arena_reg_alloc(arena_t *arena, size_t size, bool fit)
+{
+	region_t *ret;
+
+	assert(QUANTUM_CEILING(size) == size);
+	assert(size >= QUANTUM_CEILING(sizeof(region_small_sizer_t)));
+	assert(size <= (chunk_size >> 1));
+
+	if (size <= bin_maxsize) {
+		ret = arena_bin_reg_alloc(arena, size, fit);
+		if (ret != NULL)
+			goto RETURN;
+	}
+
+	ret = arena_large_reg_alloc(arena, size, fit);
+	if (ret != NULL)
+		goto RETURN;
+
+	ret = arena_split_reg_alloc(arena, size, fit);
+	if (ret != NULL)
+		goto RETURN;
+
+	/*
+	 * Only try allocating from frag here if size is large, since
+	 * arena_bin_reg_alloc() already falls back to allocating from frag for
+	 * small regions.
+	 */
+	if (size > bin_maxsize) {
+		ret = arena_frag_reg_alloc(arena, size, fit);
+		if (ret != NULL)
+			goto RETURN;
+	}
+
+	ret = arena_chunk_reg_alloc(arena, size, fit);
+	if (ret != NULL)
+		goto RETURN;
+
+	ret = NULL;
+RETURN:
+	return (ret);
+}
+
 static void *
-irealloc(void *ptr, size_t size)
+arena_malloc(arena_t *arena, size_t size)
 {
-    void *p;
-    u_long osize, index;
-    struct pginfo **mp;
-    int i;
+	void *ret;
+	region_t *reg;
+	size_t quantum_size;
+
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+	assert(size != 0);
+	assert(region_ceiling(size) <= (chunk_size >> 1));
+
+	quantum_size = region_ceiling(size);
+	if (quantum_size < size) {
+		/* size is large enough to cause size_t wrap-around. */
+		ret = NULL;
+		goto RETURN;
+	}
+	assert(quantum_size >= QUANTUM_CEILING(sizeof(region_small_sizer_t)));
+
+	malloc_mutex_lock(&arena->mtx);
+	reg = arena_reg_alloc(arena, quantum_size, true);
+	if (reg == NULL) {
+		malloc_mutex_unlock(&arena->mtx);
+		ret = NULL;
+		goto RETURN;
+	}
 
-    if (suicide)
-	abort();
+#ifdef MALLOC_STATS
+	arena->allocated += quantum_size;
+#endif
 
-    index = ptr2index(ptr);
+	malloc_mutex_unlock(&arena->mtx);
 
-    if (index < malloc_pageshift) {
-	wrtwarning("junk pointer, too low to make sense\n");
-	return (NULL);
-    }
+	ret = (void *)&reg->next;
+#ifdef MALLOC_REDZONES
+	{
+		region_t *next;
+		size_t total_size;
 
-    if (index > last_index) {
-	wrtwarning("junk pointer, too high to make sense\n");
-	return (NULL);
-    }
+		memset(reg->sep.next_red, 0xa5, MALLOC_RED);
 
-    mp = &page_dir[index];
+		/*
+		 * Unused trailing space in the region is considered part of the
+		 * trailing redzone.
+		 */
+		total_size = region_next_size_get(&reg->sep);
+		assert(total_size >= size);
+		memset(&((char *)ret)[size], 0xa5,
+		    total_size - size - sizeof(region_sep_t));
 
-    if (*mp == MALLOC_FIRST) {			/* Page allocation */
+		reg->sep.next_exact_size = size;
 
-	/* Check the pointer */
-	if ((u_long)ptr & malloc_pagemask) {
-	    wrtwarning("modified (page-) pointer\n");
-	    return (NULL);
+		next = (region_t *)&((char *)reg)[total_size];
+		memset(next->sep.prev_red, 0xa5, MALLOC_RED);
 	}
+#endif
+RETURN:
+	return (ret);
+}
 
-	/* Find the size in bytes */
-	for (osize = malloc_pagesize; *(++mp) == MALLOC_FOLLOW;)
-	    osize += malloc_pagesize;
+static void *
+arena_palloc(arena_t *arena, size_t alignment, size_t size)
+{
+	void *ret;
+
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+
+	if (alignment <= quantum) {
+		/*
+		 * The requested alignment is always guaranteed, so use the
+		 * normal allocation function.
+		 */
+		ret = arena_malloc(arena, size);
+	} else {
+		region_t *reg, *old_split;
+		size_t quantum_size, alloc_size, offset, total_size;
+
+		/*
+		 * Allocate more space than necessary, then carve an aligned
+		 * region out of it.  The smallest allowable region is
+		 * potentially a multiple of the quantum size, so care must be
+		 * taken to carve things up such that all resulting regions are
+		 * large enough.
+		 */
+
+		quantum_size = region_ceiling(size);
+		if (quantum_size < size) {
+			/* size is large enough to cause size_t wrap-around. */
+			ret = NULL;
+			goto RETURN;
+		}
+
+		/*
+		 * Calculate how large of a region to allocate.  There must be
+		 * enough space to advance far enough to have at least
+		 * sizeof(region_small_sizer_t) leading bytes, yet also land at
+		 * an alignment boundary.
+		 */
+		if (alignment >= sizeof(region_small_sizer_t)) {
+			alloc_size =
+			    QUANTUM_CEILING(sizeof(region_small_sizer_t))
+			    + alignment + quantum_size;
+		} else {
+			alloc_size =
+			    (QUANTUM_CEILING(sizeof(region_small_sizer_t)) << 1)
+			    + quantum_size;
+		}
+
+		if (alloc_size < quantum_size) {
+			/* size_t wrap-around occurred. */
+			ret = NULL;
+			goto RETURN;
+		}
+
+		malloc_mutex_lock(&arena->mtx);
+		old_split = arena->split;
+		reg = arena_reg_alloc(arena, alloc_size, false);
+		if (reg == NULL) {
+			malloc_mutex_unlock(&arena->mtx);
+			ret = NULL;
+			goto RETURN;
+		}
+		if (reg == old_split) {
+			/*
+			 * We requested a non-fit allocation that was serviced
+			 * by split, which means that we need to take care to
+			 * restore split in the arena_reg_fit() call later on.
+			 *
+			 * Do nothing; a non-NULL old_split will be used as the
+			 * signal to restore split.
+			 */
+		} else
+			old_split = NULL;
+
+		total_size = region_next_size_get(&reg->sep);
+
+		if (alignment > bin_maxsize || size > bin_maxsize) {
+			size_t split_size, p;
+
+			/*
+			 * Put this allocation toward the end of reg, since
+			 * it is large, and we try to put all large regions at
+			 * the end of split regions.
+			 */
+			split_size = region_next_size_get(&reg->sep);
+			p = (size_t)&((char *)&reg->next)[split_size];
+			p -= offsetof(region_t, next);
+			p -= size;
+			p &= ~(alignment - 1);
+			p -= offsetof(region_t, next);
+
+			offset = p - (size_t)reg;
+		} else {
+			if ((((size_t)&reg->next) & (alignment - 1)) != 0) {
+				size_t p;
+
+				/*
+				 * reg is unaligned.  Calculate the offset into
+				 * reg to actually base the allocation at.
+				 */
+				p = ((size_t)&reg->next + alignment)
+				    & ~(alignment - 1);
+				while (p - (size_t)&reg->next
+				    < QUANTUM_CEILING(sizeof(
+				    region_small_sizer_t)))
+					p += alignment;
+				p -= offsetof(region_t, next);
+
+				offset = p - (size_t)reg;
+			} else
+				offset = 0;
+		}
+		assert(offset % quantum == 0);
+		assert(offset < total_size);
+
+		if (offset != 0) {
+			region_t *prev;
+
+			/*
+			 * Move ret to an alignment boundary that is far enough
+			 * past the beginning of the allocation to leave a
+			 * leading free region, then trim the leading space.
+			 */
+
+			assert(offset >= QUANTUM_CEILING(
+			    sizeof(region_small_sizer_t)));
+			assert(offset + size <= total_size);
+
+			prev = reg;
+			reg = (region_t *)&((char *)prev)[offset];
+			assert(((size_t)&reg->next & (alignment - 1)) == 0);
+
+			/* prev. */
+			region_next_size_set(&prev->sep, offset);
+			reg->prev.size = offset;
+
+			/* reg. */
+			region_next_size_set(&reg->sep, total_size - offset);
+			region_next_free_unset(&reg->sep);
+			if (region_next_contig_get(&prev->sep))
+				region_next_contig_set(&reg->sep);
+			else
+				region_next_contig_unset(&reg->sep);
+
+			if (old_split != NULL && (alignment > bin_maxsize
+			    || size > bin_maxsize)) {
+				/* Restore to split. */
+				region_prev_free_unset(&reg->sep);
+
+				arena->split = prev;
+				old_split = NULL;
+			} else {
+				region_next_free_set(&prev->sep);
+				region_prev_free_set(&reg->sep);
+
+				arena_mru_cache(arena, prev, offset);
+			}
+#ifdef MALLOC_STATS
+			arena->stats.nsplit++;
+#endif
+		}
+
+		arena_reg_fit(arena, quantum_size, reg, (old_split != NULL));
+
+#ifdef MALLOC_STATS
+		arena->allocated += quantum_size;
+#endif
+
+		malloc_mutex_unlock(&arena->mtx);
+
+		ret = (void *)&reg->next;
+#ifdef MALLOC_REDZONES
+		{
+			region_t *next;
+			size_t total_size;
+
+			memset(reg->sep.next_red, 0xa5, MALLOC_RED);
+
+			/*
+			 * Unused trailing space in the region is considered
+			 * part of the trailing redzone.
+			 */
+			total_size = region_next_size_get(&reg->sep);
+			assert(total_size >= size);
+			memset(&((char *)ret)[size], 0xa5,
+			    total_size - size - sizeof(region_sep_t));
+
+			reg->sep.next_exact_size = size;
 
-        if (!malloc_realloc && 			/* Unless we have to, */
-	  size <= osize && 			/* .. or are too small, */
-	  size > (osize - malloc_pagesize)) {	/* .. or can free a page, */
-	    if (malloc_junk)
-		memset((u_char *)ptr + size, SOME_JUNK, osize-size);
-	    return (ptr);			/* ..don't do anything else. */
+			next = (region_t *)&((char *)reg)[total_size];
+			memset(next->sep.prev_red, 0xa5, MALLOC_RED);
+		}
+#endif
 	}
 
-    } else if (*mp >= MALLOC_MAGIC) {		/* Chunk allocation */
+RETURN:
+	assert(((size_t)ret & (alignment - 1)) == 0);
+	return (ret);
+}
+
+static void *
+arena_calloc(arena_t *arena, size_t num, size_t size)
+{
+	void *ret;
+
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+	assert(num * size != 0);
+
+	ret = arena_malloc(arena, num * size);
+	if (ret == NULL)
+		goto RETURN;
+
+	memset(ret, 0, num * size);
+
+RETURN:
+	return (ret);
+}
+
+static size_t
+arena_salloc(arena_t *arena, void *ptr)
+{
+	size_t ret;
+	region_t *reg;
+
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+	assert(ptr != NULL);
+	assert(ptr != &nil);
+	assert(CHUNK_ADDR2BASE(ptr) != ptr);
 
-	/* Check the pointer for sane values */
-	if (((u_long)ptr & ((*mp)->size-1))) {
-	    wrtwarning("modified (chunk-) pointer\n");
-	    return (NULL);
+	reg = (region_t *)&((char *)ptr)[-offsetof(region_t, next)];
+
+	ret = region_next_size_get(&reg->sep);
+
+	return (ret);
+}
+
+#ifdef MALLOC_REDZONES
+static void
+redzone_check(void *ptr)
+{
+	region_t *reg, *next;
+	size_t size;
+	unsigned i, ncorruptions;
+
+	ncorruptions = 0;
+
+	reg = (region_t *)&((char *)ptr)[-offsetof(region_t, next)];
+	size = region_next_size_get(&reg->sep);
+	next = (region_t *)&((char *)reg)[size];
+
+	/* Leading redzone. */
+	for (i = 0; i < MALLOC_RED; i++) {
+		if ((unsigned char)reg->sep.next_red[i] != 0xa5) {
+			size_t offset = (size_t)MALLOC_RED - i;
+
+			ncorruptions++;
+			malloc_printf("%s: (malloc) Corrupted redzone %zu "
+			    "byte%s before %p (0x%x)\n", _getprogname(), 
+			    offset, offset > 1 ? "s" : "", ptr,
+			    (unsigned char)reg->sep.next_red[i]);
+		}
+	}
+	memset(&reg->sep.next_red, 0x5a, MALLOC_RED);
+
+	/* Bytes immediately trailing allocation. */
+	for (i = 0; i < size - reg->sep.next_exact_size - sizeof(region_sep_t);
+	    i++) {
+		if ((unsigned char)((char *)ptr)[reg->sep.next_exact_size + i]
+		    != 0xa5) {
+			size_t offset = (size_t)(i + 1);
+
+			ncorruptions++;
+			malloc_printf("%s: (malloc) Corrupted redzone %zu "
+			    "byte%s after %p (size %zu) (0x%x)\n",
+			    _getprogname(), offset, offset > 1 ? "s" : "", ptr,
+			    reg->sep.next_exact_size, (unsigned char)((char *)
+			    ptr)[reg->sep.next_exact_size + i]);
+		}
 	}
+	memset(&((char *)ptr)[reg->sep.next_exact_size], 0x5a,
+	    size - reg->sep.next_exact_size - sizeof(region_sep_t));
+
+	/* Trailing redzone. */
+	for (i = 0; i < MALLOC_RED; i++) {
+		if ((unsigned char)next->sep.prev_red[i] != 0xa5) {
+			size_t offset = (size_t)(size - reg->sep.next_exact_size
+			    - sizeof(region_sep_t) + i + 1);
+
+			ncorruptions++;
+			malloc_printf("%s: (malloc) Corrupted redzone %zu "
+			    "byte%s after %p (size %zu) (0x%x)\n",
+			    _getprogname(), offset, offset > 1 ? "s" : "", ptr,
+			    reg->sep.next_exact_size,
+			    (unsigned char)next->sep.prev_red[i]);
+		}
+	}
+	memset(&next->sep.prev_red, 0x5a, MALLOC_RED);
+
+	if (opt_abort && ncorruptions != 0)
+		abort();
 
-	/* Find the chunk index in the page */
-	i = ((u_long)ptr & malloc_pagemask) >> (*mp)->shift;
+	reg->sep.next_exact_size = 0;
+}
+#endif
+
+static void
+arena_dalloc(arena_t *arena, void *ptr)
+{
+	region_t *reg;
 
-	/* Verify that it isn't a free chunk already */
-        if ((*mp)->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) {
-	    wrtwarning("chunk is already free\n");
-	    return (NULL);
+	assert(arena != NULL);
+	assert(ptr != NULL);
+	assert(ptr != &nil);
+
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+	assert(CHUNK_ADDR2BASE(ptr) != ptr);
+
+	reg = (region_t *)&((char *)ptr)[-offsetof(region_t, next)];
+
+	malloc_mutex_lock(&arena->mtx);
+
+#ifdef MALLOC_DEBUG
+	{
+		chunk_node_t *chunk, *node;
+		chunk_node_t key;
+
+		chunk = CHUNK_ADDR2BASE(ptr);
+		assert(chunk->arena == arena);
+
+		key.chunk = chunk;
+		node = RB_FIND(chunk_tree_s, &arena->chunks, &key);
+		assert(node == chunk);
 	}
+#endif
+#ifdef MALLOC_REDZONES
+	redzone_check(ptr);
+#endif
 
-	osize = (*mp)->size;
+#ifdef MALLOC_STATS
+	arena->allocated -= region_next_size_get(&reg->sep);
+#endif
 
-	if (!malloc_realloc &&		/* Unless we have to, */
-	  size <= osize && 		/* ..or are too small, */
-	  (size > osize/2 ||	 	/* ..or could use a smaller size, */
-	  osize == malloc_minsize)) {	/* ..(if there is one) */
-	    if (malloc_junk)
-		memset((u_char *)ptr + size, SOME_JUNK, osize-size);
-	    return (ptr);		/* ..don't do anything else. */
+	if (opt_junk) {
+		memset(&reg->next, 0x5a,
+		    region_next_size_get(&reg->sep) - sizeof(region_sep_t));
 	}
 
-    } else {
-	wrtwarning("pointer to wrong page\n");
+	arena_delay_cache(arena, reg);
+
+	malloc_mutex_unlock(&arena->mtx);
+}
+
+#ifdef NOT_YET
+static void *
+arena_ralloc(arena_t *arena, void *ptr, size_t size)
+{
+
+	/*
+	 * Arenas don't need to support ralloc, since all reallocation is done
+	 * by allocating new space and copying.  This function should never be
+	 * called.
+	 */
+	/* NOTREACHED */
+	assert(false);
+
 	return (NULL);
-    }
+}
+#endif
+
+#ifdef MALLOC_STATS
+static bool
+arena_stats(arena_t *arena, size_t *allocated, size_t *total)
+{
+
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+	assert(allocated != NULL);
+	assert(total != NULL);
+
+	malloc_mutex_lock(&arena->mtx);
+	*allocated = arena->allocated;
+	*total = arena->nchunks * chunk_size;
+	malloc_mutex_unlock(&arena->mtx);
+
+	return (false);
+}
+#endif
 
-    p = imalloc(size);
+static void
+arena_new(arena_t *arena, bool malloced, bool recursive)
+{
+	unsigned i;
 
-    if (p != NULL) {
-	/* copy the lesser of the two sizes, and free the old one */
-	if (!size || !osize)
-	    ;
-	else if (osize < size)
-	    memcpy(p, ptr, osize);
+	arena->malloced = malloced;
+
+	if (recursive)
+		malloc_mutex_recursive_init(&arena->mtx);
 	else
-	    memcpy(p, ptr, size);
-	ifree(ptr);
-    }
-    return (p);
+		malloc_mutex_init(&arena->mtx);
+
+	for (i = 0; i < NBINS; i++)
+		qr_new(&arena->bins[i].regions, next.u.s.link);
+
+	for (i = 0; i < BINMASK_NELMS; i++)
+		arena->bins_mask[i] = 0;
+
+	arena->split = NULL;
+	arena->frag = NULL;
+	RB_INIT(&arena->large_regions);
+
+	RB_INIT(&arena->chunks);
+	arena->nchunks = 0;
+
+#ifdef MALLOC_STATS
+	arena->allocated = 0;
+
+	memset(&arena->stats, 0, sizeof(arena_stats_t));
+#endif
+
+#ifdef MALLOC_DEBUG
+	arena->magic = ARENA_MAGIC;
+#endif
+
+	/*
+	 * Do this last, since it involved recursing in the case of base_arena.
+	 *
+	 * Use page alignment for delayed, so that only one page must be kept
+	 * in RAM, rather than two (assuming a small enough array).  This seems
+	 * prudent, given that all of delayed is touched often.
+	 */
+	assert(opt_ndelay > 0);
+	arena->delayed = (region_t **)ipalloc(&base_arena, pagesize,
+	    (opt_ndelay * sizeof(region_t *)) + CACHELINE);
+	memset(arena->delayed, 0, opt_ndelay * sizeof(region_t *));
+	arena->next_delayed = 0;
 }
 
-/*
- * Free a sequence of pages
- */
+/* Create a new arena and insert it into the arenas array at index ind. */
+static arena_t *
+arenas_extend(unsigned ind)
+{
+	arena_t *ret;
 
-static __inline void
-free_pages(void *ptr, u_long index, struct pginfo const *info)
-{
-    u_long i;
-    struct pgfree *pf, *pt=NULL;
-    u_long l;
-    void *tail;
-
-    if (info == MALLOC_FREE) {
-	wrtwarning("page is already free\n");
-	return;
-    }
-
-    if (info != MALLOC_FIRST) {
-	wrtwarning("pointer to wrong page\n");
-	return;
-    }
-
-    if ((u_long)ptr & malloc_pagemask) {
-	wrtwarning("modified (page-) pointer\n");
-	return;
-    }
-
-    /* Count how many pages and mark them free at the same time */
-    page_dir[index] = MALLOC_FREE;
-    for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++)
-	page_dir[index + i] = MALLOC_FREE;
-
-    l = i << malloc_pageshift;
-
-    if (malloc_junk)
-	memset(ptr, SOME_JUNK, l);
-
-#if defined(MADV_FREE)
-    if (malloc_hint)
-	madvise(ptr, l, MADV_FREE);
-#endif
-
-    tail = (char *)ptr+l;
-
-    /* add to free-list */
-    if (px == NULL)
-	px = imalloc(sizeof *px);	/* This cannot fail... */
-    px->page = ptr;
-    px->end =  tail;
-    px->size = l;
-    if (free_list.next == NULL) {
-
-	/* Nothing on free list, put this at head */
-	px->next = free_list.next;
-	px->prev = &free_list;
-	free_list.next = px;
-	pf = px;
-	px = NULL;
-
-    } else {
-
-	/* Find the right spot, leave pf pointing to the modified entry. */
-	tail = (char *)ptr+l;
-
-	for(pf = free_list.next; pf->end < ptr && pf->next != NULL;
-	    pf = pf->next)
-	    ; /* Race ahead here */
-
-	if (pf->page > tail) {
-	    /* Insert before entry */
-	    px->next = pf;
-	    px->prev = pf->prev;
-	    pf->prev = px;
-	    px->prev->next = px;
-	    pf = px;
-	    px = NULL;
-	} else if (pf->end == ptr ) {
-	    /* Append to the previous entry */
-	    pf->end = (char *)pf->end + l;
-	    pf->size += l;
-	    if (pf->next != NULL && pf->end == pf->next->page ) {
-		/* And collapse the next too. */
-		pt = pf->next;
-		pf->end = pt->end;
-		pf->size += pt->size;
-		pf->next = pt->next;
-		if (pf->next != NULL)
-		    pf->next->prev = pf;
-	    }
-	} else if (pf->page == tail) {
-	    /* Prepend to entry */
-	    pf->size += l;
-	    pf->page = ptr;
-	} else if (pf->next == NULL) {
-	    /* Append at tail of chain */
-	    px->next = NULL;
-	    px->prev = pf;
-	    pf->next = px;
-	    pf = px;
-	    px = NULL;
+	ret = (arena_t *)ipalloc(&base_arena, CACHELINE,
+	    sizeof(arena_t) + CACHELINE);
+	if (ret != NULL) {
+		arena_new(ret, true, false);
+		arenas[ind] = ret;
 	} else {
-	    wrterror("freelist is destroyed\n");
+		/*
+		 * OOM here is quite inconvenient to propagate, since dealing
+		 * with it would require a check for failure in the fast path.
+		 * Instead, punt by using arenas[0].  In practice, this is an
+		 * extremely unlikely failure.
+		 */
+		malloc_printf("%s: (malloc) Error initializing arena\n",
+		    _getprogname());
+		if (opt_abort)
+			abort();
+
+		ret = arenas[0];
 	}
-    }
 
-    /* Return something to OS ? */
-    if (pf->next == NULL &&			/* If we're the last one, */
-      pf->size > malloc_cache &&		/* ..and the cache is full, */
-      pf->end == malloc_brk &&			/* ..and none behind us, */
-      malloc_brk == sbrk(0)) {			/* ..and it's OK to do... */
+	return (ret);
+}
+
+/*
+ * End arena.
+ */
+/******************************************************************************/
+/*
+ * Begin  general internal functions.
+ */
+
+/*
+ * Choose an arena based on a per-thread value (fast-path code, calls slow-path
+ * code if necessary.
+ */
+static __inline arena_t *
+choose_arena(void)
+{
+	arena_t *ret;
 
 	/*
-	 * Keep the cache intact.  Notice that the '>' above guarantees that
-	 * the pf will always have at least one page afterwards.
+	 * We can only use TLS if this is a PIC library, since for the static
+	 * library version, libc's malloc is used by TLS allocation, which
+	 * introduces a bootstrapping issue.
 	 */
-	pf->end = (char *)pf->page + malloc_cache;
-	pf->size = malloc_cache;
+#ifndef NO_TLS
+	ret = arenas_map;
+	if (ret == NULL)
+		ret = choose_arena_hard();
+#else
+	if (__isthreaded) {
+		unsigned long ind;
+		
+		/*
+		 * Hash _pthread_self() to one of the arenas.  There is a prime
+		 * number of arenas, so this has a reasonable chance of
+		 * working.  Even so, the hashing can be easily thwarted by
+		 * inconvenient _pthread_self() values.  Without specific
+		 * knowledge of how _pthread_self() calculates values, we can't
+		 * do much better than this.
+		 */
+		ind = (unsigned long) _pthread_self() % narenas;
+
+		/*
+		 * Optimistially assume that arenas[ind] has been initialized.
+		 * At worst, we find out that some other thread has already
+		 * done so, after acquiring the lock in preparation.  Note that
+		 * this lazy locking also has the effect of lazily forcing
+		 * cache coherency; without the lock acquisition, there's no
+		 * guarantee that modification of arenas[ind] by another thread
+		 * would be seen on this CPU for an arbitrary amount of time.
+		 *
+		 * In general, this approach to modifying a synchronized value
+		 * isn't a good idea, but in this case we only ever modify the
+		 * value once, so things work out well.
+		 */
+		ret = arenas[ind];
+		if (ret == NULL) {
+			/*
+			 * Avoid races with another thread that may have already
+			 * initialized arenas[ind].
+			 */
+			malloc_mutex_lock(&arenas_mtx);
+			if (arenas[ind] == NULL)
+				ret = arenas_extend((unsigned)ind);
+			else
+				ret = arenas[ind];
+			malloc_mutex_unlock(&arenas_mtx);
+		}
+	} else
+		ret = arenas[0];
+#endif
+
+	return (ret);
+}
+
+#ifndef NO_TLS
+/*
+ * Choose an arena based on a per-thread value (slow-path code only, called
+ * only by choose_arena()).
+ */
+static arena_t *
+choose_arena_hard(void)
+{
+	arena_t *ret;
+
+	/* Assign one of the arenas to this thread, in a round-robin fashion. */
+	if (__isthreaded) {
+		malloc_mutex_lock(&arenas_mtx);
+		ret = arenas[next_arena];
+		if (ret == NULL)
+			ret = arenas_extend(next_arena);
+		next_arena = (next_arena + 1) % narenas;
+		malloc_mutex_unlock(&arenas_mtx);
+	} else
+		ret = arenas[0];
+	arenas_map = ret;
+
+	return (ret);
+}
+#endif
+
+static void *
+huge_malloc(arena_t *arena, size_t size)
+{
+	void *ret;
+	size_t chunk_size;
+	chunk_node_t *node;
+
+	/* Allocate a chunk for this request. */
 
-	brk(pf->end);
-	malloc_brk = pf->end;
+#ifdef MALLOC_STATS
+	arena->stats.huge.nrequests++;
+#endif
 
-	index = ptr2index(pf->end);
+	chunk_size = CHUNK_CEILING(size);
+	if (chunk_size == 0) {
+		/* size is large enough to cause size_t wrap-around. */
+		ret = NULL;
+		goto RETURN;
+	}
 
-	for(i=index;i <= last_index;)
-	    page_dir[i++] = MALLOC_NOT_MINE;
+	/* Allocate a chunk node with which to track the chunk. */
+	node = ipalloc(&base_arena, CACHELINE,
+	    sizeof(chunk_node_t) + CACHELINE);
+	if (node == NULL) {
+		ret = NULL;
+		goto RETURN;
+	}
 
-	last_index = index - 1;
+	ret = chunk_alloc(chunk_size);
+	if (ret == NULL) {
+		idalloc(node);
+		ret = NULL;
+		goto RETURN;
+	}
 
-	/* XXX: We could realloc/shrink the pagedir here I guess. */
-    }
-    if (pt != NULL)
-	ifree(pt);
+	/* Insert node into chunks. */
+	node->arena = arena;
+	node->chunk = ret;
+	node->size = chunk_size;
+	node->extra = chunk_size - size;
+
+	malloc_mutex_lock(&chunks_mtx);
+	RB_INSERT(chunk_tree_s, &huge, node);
+#ifdef MALLOC_STATS
+	huge_allocated += size;
+	huge_total += chunk_size;
+#endif
+	malloc_mutex_unlock(&chunks_mtx);
+
+RETURN:
+	return (ret);
 }
 
-/*
- * Free a chunk, and possibly the page it's on, if the page becomes empty.
- */
+static void
+huge_dalloc(void *ptr)
+{
+	chunk_node_t key;
+	chunk_node_t *node;
+
+	malloc_mutex_lock(&chunks_mtx);
+
+	/* Extract from tree of huge allocations. */
+	key.chunk = ptr;
+	node = RB_FIND(chunk_tree_s, &huge, &key);
+	assert(node != NULL);
+	assert(node->chunk == ptr);
+	RB_REMOVE(chunk_tree_s, &huge, node);
+
+#ifdef MALLOC_STATS
+	malloc_mutex_lock(&node->arena->mtx);
+	node->arena->stats.ndalloc++;
+	malloc_mutex_unlock(&node->arena->mtx);
+
+	/* Update counters. */
+	huge_allocated -= (node->size - node->extra);
+	huge_total -= node->size;
+#endif
 
-static __inline void
-free_bytes(void *ptr, u_long index, struct pginfo *info)
+	malloc_mutex_unlock(&chunks_mtx);
+
+	/* Unmap chunk. */
+	chunk_dealloc(node->chunk, node->size);
+
+	idalloc(node);
+}
+
+static void *
+imalloc(arena_t *arena, size_t size)
 {
-    int i;
-    struct pginfo **mp;
-    void *vp;
+	void *ret;
 
-    /* Find the chunk number on the page */
-    i = ((u_long)ptr & malloc_pagemask) >> info->shift;
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+	assert(size != 0);
 
-    if (((u_long)ptr & (info->size-1))) {
-	wrtwarning("modified (chunk-) pointer\n");
-	return;
-    }
+	if (region_ceiling(size) <= (chunk_size >> 1))
+		ret = arena_malloc(arena, size);
+	else
+		ret = huge_malloc(arena, size);
 
-    if (info->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) {
-	wrtwarning("chunk is already free\n");
-	return;
-    }
+#ifdef MALLOC_STATS
+	malloc_mutex_lock(&arena->mtx);
+	arena->stats.nmalloc++;
+	malloc_mutex_unlock(&arena->mtx);
+#endif
 
-    if (malloc_junk)
-	memset(ptr, SOME_JUNK, info->size);
+	if (opt_junk) {
+		if (ret != NULL)
+			memset(ret, 0xa5, size);
+	}
+	return (ret);
+}
 
-    info->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS);
-    info->free++;
+static void *
+ipalloc(arena_t *arena, size_t alignment, size_t size)
+{
+	void *ret;
 
-    mp = page_dir + info->shift;
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
 
-    if (info->free == 1) {
+	/*
+	 * The conditions that disallow calling arena_palloc() are quite
+	 * tricky.
+	 *
+	 * The first main clause of the conditional mirrors that in imalloc(),
+	 * and is necesary because arena_palloc() may in turn call
+	 * arena_malloc().
+	 *
+	 * The second and third clauses are necessary because we want to be
+	 * sure that it will not be necessary to allocate more than a
+	 * half-chunk region at any point during the creation of the aligned
+	 * allocation.  These checks closely mirror the calculation of
+	 * alloc_size in arena_palloc().
+	 *
+	 * Finally, the fourth clause makes explicit the constraint on what
+	 * alignments will be attempted via regions.  At first glance, this
+	 * appears unnecessary, but in actuality, it protects against otherwise
+	 * difficult-to-detect size_t wrap-around cases.
+	 */
+	if (region_ceiling(size) <= (chunk_size >> 1)
+
+	    && (alignment < sizeof(region_small_sizer_t)
+	    || (QUANTUM_CEILING(sizeof(region_small_sizer_t)) + alignment
+	    + (region_ceiling(size))) <= (chunk_size >> 1))
+
+	    && (alignment >= sizeof(region_small_sizer_t)
+	    || ((QUANTUM_CEILING(sizeof(region_small_sizer_t)) << 1)
+	    + (region_ceiling(size))) <= (chunk_size >> 1))
+
+	    && alignment <= (chunk_size >> 2))
+		ret = arena_palloc(arena, alignment, size);
+	else {
+		if (alignment <= chunk_size)
+			ret = huge_malloc(arena, size);
+		else {
+			size_t chunksize, alloc_size, offset;
+			chunk_node_t *node;
+
+			/*
+			 * This allocation requires alignment that is even
+			 * larger than chunk alignment.  This means that
+			 * huge_malloc() isn't good enough.
+			 *
+			 * Allocate almost twice as many chunks as are demanded
+			 * by the size or alignment, in order to assure the
+			 * alignment can be achieved, then unmap leading and
+			 * trailing chunks.
+			 */
+
+			chunksize = CHUNK_CEILING(size);
+
+			if (size >= alignment)
+				alloc_size = chunksize + alignment - chunk_size;
+			else
+				alloc_size = (alignment << 1) - chunk_size;
+
+			/*
+			 * Allocate a chunk node with which to track the chunk.
+			 */
+			node = ipalloc(&base_arena, CACHELINE,
+			    sizeof(chunk_node_t) + CACHELINE);
+			if (node == NULL) {
+				ret = NULL;
+				goto RETURN;
+			}
+
+			ret = chunk_alloc(alloc_size);
+			if (ret == NULL) {
+				idalloc(node);
+				ret = NULL;
+				goto RETURN;
+			}
+
+			offset = (size_t)ret & (alignment - 1);
+			assert(offset % chunk_size == 0);
+			assert(offset < alloc_size);
+			if (offset == 0) {
+				/* Trim trailing space. */
+				chunk_dealloc((void *) ((size_t) ret
+				    + chunksize), alloc_size - chunksize);
+			} else {
+				size_t trailsize;
+
+				/* Trim leading space. */
+				chunk_dealloc(ret, alignment - offset);
+
+				ret = (void *) ((size_t) ret + (alignment
+				    - offset));
+
+				trailsize = alloc_size - (alignment - offset)
+				    - chunksize;
+				if (trailsize != 0) {
+				    /* Trim trailing space. */
+				    assert(trailsize < alloc_size);
+				    chunk_dealloc((void *) ((size_t) ret
+				        + chunksize), trailsize);
+				}
+			}
+
+			/* Insert node into chunks. */
+			node->arena = arena;
+			node->chunk = ret;
+			node->size = chunksize;
+			node->extra = node->size - size;
+
+			malloc_mutex_lock(&chunks_mtx);
+			RB_INSERT(chunk_tree_s, &huge, node);
+#ifdef MALLOC_STATS
+			huge_allocated += size;
+			huge_total += chunksize;
+#endif
+			malloc_mutex_unlock(&chunks_mtx);
+		}
+	}
 
-	/* Page became non-full */
+RETURN:
+#ifdef MALLOC_STATS
+	malloc_mutex_lock(&arena->mtx);
+	arena->stats.npalloc++;
+	malloc_mutex_unlock(&arena->mtx);
+#endif
 
-	mp = page_dir + info->shift;
-	/* Insert in address order */
-	while (*mp && (*mp)->next && (*mp)->next->page < info->page)
-	    mp = &(*mp)->next;
-	info->next = *mp;
-	*mp = info;
-	return;
-    }
+	if (opt_junk) {
+		if (ret != NULL)
+			memset(ret, 0xa5, size);
+	}
+	assert(((size_t)ret & (alignment - 1)) == 0);
+	return (ret);
+}
 
-    if (info->free != info->total)
-	return;
+static void *
+icalloc(arena_t *arena, size_t num, size_t size)
+{
+	void *ret;
+
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+	assert(num * size != 0);
+
+	if (region_ceiling(num * size) <= (chunk_size >> 1))
+		ret = arena_calloc(arena, num, size);
+	else {
+		/*
+		 * The virtual memory system provides zero-filled pages, so
+		 * there is no need to do so manually.
+		 */
+		ret = huge_malloc(arena, num * size);
+#ifdef USE_BRK
+		if ((size_t)ret >= (size_t)brk_base
+		    && (size_t)ret < (size_t)brk_max) {
+			/* 
+			 * This may be a re-used brk chunk.  Therefore, zero
+			 * the memory.
+			 */
+			memset(ret, 0, num * size);
+		}
+#endif
+	}
 
-    /* Find & remove this page in the queue */
-    while (*mp != info) {
-	mp = &((*mp)->next);
-#ifdef MALLOC_EXTRA_SANITY
-	if (!*mp)
-		wrterror("(ES): Not on queue\n");
-#endif /* MALLOC_EXTRA_SANITY */
-    }
-    *mp = info->next;
+#ifdef MALLOC_STATS
+	malloc_mutex_lock(&arena->mtx);
+	arena->stats.ncalloc++;
+	malloc_mutex_unlock(&arena->mtx);
+#endif
 
-    /* Free the page & the info structure if need be */
-    page_dir[ptr2index(info->page)] = MALLOC_FIRST;
-    vp = info->page;		/* Order is important ! */
-    if(vp != (void*)info)
-	ifree(info);
-    ifree(vp);
+	return (ret);
 }
 
-static void
-ifree(void *ptr)
+static size_t
+isalloc(void *ptr)
 {
-    struct pginfo *info;
-    u_long index;
+	size_t ret;
+	chunk_node_t *node;
+
+	assert(ptr != NULL);
+	assert(ptr != &nil);
 
-    /* This is legal */
-    if (ptr == NULL)
-	return;
+	node = CHUNK_ADDR2BASE(ptr);
+	if (node != ptr) {
+		/* Region. */
+		assert(node->arena->magic == ARENA_MAGIC);
+
+		ret = arena_salloc(node->arena, ptr);
+	} else {
+		chunk_node_t key;
 
-    /* If we're already sinking, don't make matters any worse. */
-    if (suicide)
-	return;
+		/* Chunk (huge allocation). */
 
-    index = ptr2index(ptr);
+		malloc_mutex_lock(&chunks_mtx);
 
-    if (index < malloc_pageshift) {
-	wrtwarning("junk pointer, too low to make sense\n");
-	return;
-    }
+		/* Extract from tree of huge allocations. */
+		key.chunk = ptr;
+		node = RB_FIND(chunk_tree_s, &huge, &key);
+		assert(node != NULL);
 
-    if (index > last_index) {
-	wrtwarning("junk pointer, too high to make sense\n");
-	return;
-    }
+		ret = node->size - node->extra;
 
-    info = page_dir[index];
+		malloc_mutex_unlock(&chunks_mtx);
+	}
+
+	return (ret);
+}
 
-    if (info < MALLOC_MAGIC)
-        free_pages(ptr, index, info);
-    else
-	free_bytes(ptr, index, info);
-    return;
+static void
+idalloc(void *ptr)
+{
+	chunk_node_t *node;
+
+	assert(ptr != NULL);
+	assert(ptr != &nil);
+
+	node = CHUNK_ADDR2BASE(ptr);
+	if (node != ptr) {
+		/* Region. */
+#ifdef MALLOC_STATS
+		malloc_mutex_lock(&node->arena->mtx);
+		node->arena->stats.ndalloc++;
+		malloc_mutex_unlock(&node->arena->mtx);
+#endif
+		arena_dalloc(node->arena, ptr);
+	} else
+		huge_dalloc(ptr);
 }
 
 static void *
-pubrealloc(void *ptr, size_t size, const char *func)
-{
-    void *r;
-    int err = 0;
-    static int malloc_active; /* Recusion flag for public interface. */
-    static unsigned malloc_started; /* Set when initialization has been done */
-
-    /*
-     * If a thread is inside our code with a functional lock held, and then
-     * catches a signal which calls us again, we would get a deadlock if the
-     * lock is not of a recursive type.
-     */
-    _MALLOC_LOCK();
-    malloc_func = func;
-    if (malloc_active > 0) {
-	if (malloc_active == 1) {
-	    wrtwarning("recursive call\n");
-	    malloc_active = 2;
-	}
-        _MALLOC_UNLOCK();
-	errno = EDOOFUS;
-	return (NULL);
-    } 
-    malloc_active = 1;
+iralloc(arena_t *arena, void *ptr, size_t size)
+{
+	void *ret;
+	size_t oldsize;
+
+	assert(arena != NULL);
+	assert(arena->magic == ARENA_MAGIC);
+	assert(ptr != NULL);
+	assert(ptr != &nil);
+	assert(size != 0);
+
+	oldsize = isalloc(ptr);
+
+	if (region_ceiling(size) <= (chunk_size >> 1)) {
+		ret = arena_malloc(arena, size);
+		if (ret == NULL)
+			goto RETURN;
+		if (opt_junk)
+			memset(ret, 0xa5, size);
+
+		if (size < oldsize)
+			memcpy(ret, ptr, size);
+		else
+			memcpy(ret, ptr, oldsize);
+	} else {
+		ret = huge_malloc(arena, size);
+		if (ret == NULL)
+			goto RETURN;
+		if (opt_junk)
+			memset(ret, 0xa5, size);
+
+		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);
+		}
+	}
+
+	idalloc(ptr);
+
+RETURN:
+#ifdef MALLOC_STATS
+	malloc_mutex_lock(&arena->mtx);
+	arena->stats.nralloc++;
+	malloc_mutex_unlock(&arena->mtx);
+#endif
+	return (ret);
+}
+
+#ifdef MALLOC_STATS
+static void
+istats(size_t *allocated, size_t *total)
+{
+	size_t tallocated, ttotal;
+	size_t rallocated, rtotal;
+	unsigned i;
 
-    if (!malloc_started) {
-        if (ptr != NULL) {
-	    wrtwarning("malloc() has never been called\n");
-	    malloc_active = 0;
-            _MALLOC_UNLOCK();
-	    errno = EDOOFUS;
-	    return (NULL);
+	tallocated = 0;
+	ttotal = 0;
+
+	/* base_arena. */
+	arena_stats(&base_arena, &rallocated, &rtotal);
+	/*
+	 * base_arena is all overhead, so pay no attention to to rallocated
+	 * here.
+	 */
+	tallocated = 0;
+	ttotal = rtotal;
+
+	/* arenas. */
+	for (i = 0; i < narenas; i++) {
+		if (arenas[i] != NULL) {
+			arena_stats(arenas[i], &rallocated, &rtotal);
+			tallocated += rallocated;
+			ttotal += rtotal;
+		}
+	}
+
+	/* huge. */
+	malloc_mutex_lock(&chunks_mtx);
+	tallocated += huge_allocated;
+	ttotal += huge_total;
+	malloc_mutex_unlock(&chunks_mtx);
+
+	/* Return results. */
+	*allocated = tallocated;
+	*total = ttotal;
+}
+#endif
+
+static void
+malloc_print_stats(void)
+{
+
+	if (opt_print_stats) {
+		malloc_printf("___ Begin malloc statistics ___\n");
+		malloc_printf("Number of CPUs: %u\n", ncpus);
+		malloc_printf("Number of arenas: %u\n", narenas);
+		malloc_printf("Cache slots: %u\n", opt_ndelay);
+		malloc_printf("Chunk size: %zu (2^%zu)\n", chunk_size,
+		    opt_chunk_2pow);
+		malloc_printf("Quantum size: %zu (2^%zu)\n", quantum, 
+		    opt_quantum_2pow);
+		malloc_printf("Pointer size: %u\n", sizeof(size_t));
+		malloc_printf("Number of bins: %u\n", NBINS);
+		malloc_printf("Maximum bin size: %u\n", bin_maxsize);
+		malloc_printf("Assertions %s\n",
+#ifdef NDEBUG
+		    "disabled"
+#else
+		    "enabled"
+#endif
+		    );
+		malloc_printf("Redzone size: %u\n", 
+#ifdef MALLOC_REDZONES
+				MALLOC_RED
+#else
+				0
+#endif
+				);
+
+#ifdef MALLOC_STATS
+		{
+			size_t a, b;
+
+			istats(&a, &b);
+			malloc_printf("Allocated: %zu, space used: %zu\n", a,
+			    b);
+		}
+
+		{
+			arena_stats_t stats_arenas;
+			arena_t *arena;
+			unsigned i;
+
+			/* Print chunk stats. */
+			{
+				chunk_stats_t chunks_stats;
+
+				malloc_mutex_lock(&chunks_mtx);
+				chunks_stats = stats_chunks;
+				malloc_mutex_unlock(&chunks_mtx);
+
+				malloc_printf("\nchunks:\n");
+				malloc_printf(" %13s%13s%13s\n", "nchunks",
+				    "highchunks", "curchunks");
+				malloc_printf(" %13llu%13lu%13lu\n",
+				    chunks_stats.nchunks, 
+				    chunks_stats.highchunks,
+				    chunks_stats.curchunks);
+			}
+
+#ifdef MALLOC_STATS_BASE
+			/*
+			 * Copy base_arena's stats out, so that they are
+			 * self-consistent, even if the process of printing
+			 * stats is causing additional allocation.
+			 */
+			memset(&stats_arenas, 0, sizeof(arena_stats_t));
+			malloc_mutex_lock(&base_arena.mtx);
+			stats_merge(&base_arena, &stats_arenas);
+			malloc_mutex_unlock(&base_arena.mtx);
+
+			/* Print base_arena stats. */
+			malloc_printf("\nbase_arena statistics:\n");
+			stats_print(&stats_arenas);
+#endif
+
+#ifdef MALLOC_STATS_ARENAS
+			/* Print stats for each arena. */
+			for (i = 0; i < narenas; i++) {
+				arena = arenas[i];
+				if (arena != NULL) {
+					malloc_printf(
+					    "\narenas[%u] statistics:\n", i);
+					malloc_mutex_lock(&arena->mtx);
+					stats_print(&arena->stats);
+					malloc_mutex_unlock(&arena->mtx);
+				} else {
+					malloc_printf("\narenas[%u] statistics:"
+					    " unused arena\n", i);
+				}
+			}
+#endif
+
+			/* 
+			 * Merge arena stats from arenas (leave out base_arena).
+			 */
+			memset(&stats_arenas, 0, sizeof(arena_stats_t));
+			for (i = 0; i < narenas; i++) {
+				arena = arenas[i];
+				if (arena != NULL) {
+					malloc_mutex_lock(&arena->mtx);
+					stats_merge(arena, &stats_arenas);
+					malloc_mutex_unlock(&arena->mtx);
+				}
+			}
+
+			/* Print arena stats. */
+			malloc_printf("\nMerged arena statistics:\n");
+			stats_print(&stats_arenas);
+		}
+#endif /* #ifdef MALLOC_STATS */
+		malloc_printf("--- End malloc statistics ---\n");
 	}
-	malloc_init();
-	malloc_started = 1;
-    }
-   
-    if (ptr == ZEROSIZEPTR)
-	ptr = NULL;
-    if (malloc_sysv && !size) {
-	if (ptr != NULL)
-	    ifree(ptr);
-	r = NULL;
-    } else if (!size) {
-	if (ptr != NULL)
-	    ifree(ptr);
-	r = ZEROSIZEPTR;
-    } else if (ptr == NULL) {
-	r = imalloc(size);
-	err = (r == NULL);
-    } else {
-        r = irealloc(ptr, size);
-	err = (r == NULL);
-    }
-    UTRACE(ptr, size, r);
-    malloc_active = 0;
-    _MALLOC_UNLOCK();
-    if (malloc_xmalloc && err)
-	wrterror("out of memory\n");
-    if (err)
-	errno = ENOMEM;
-    return (r);
 }
 
 /*
- * These are the public exported interface routines.
+ * FreeBSD's pthreads implementation calls malloc(3), so the malloc
+ * implementation has to take pains to avoid infinite recursion during
+ * initialization.
+ *
+ * atomic_init_start() returns true if it started initializing.  In that case,
+ * the caller must also call atomic_init_finish(), just before returning
+ * to its caller.  This delayed finalization of initialization is critical,
+ * since otherwise choose_arena() has no way to know whether it's safe
+ * to call _pthread_self().
+ */
+static __inline void
+malloc_init(void)
+{
+
+	/*
+	 * We always initialize before threads are created, since any thread
+	 * creation first triggers allocations.
+	 */
+	assert(__isthreaded == 0 || malloc_initialized);
+
+	if (malloc_initialized == false)
+		malloc_init_hard();
+}
+
+static void
+malloc_init_hard(void)
+{
+	unsigned i, j;
+	int linklen;
+	char buf[PATH_MAX + 1];
+	const char *opts;
+
+	/* Get number of CPUs. */
+	{
+		int mib[2];
+		size_t len;
+
+		mib[0] = CTL_HW;
+		mib[1] = HW_NCPU;
+		len = sizeof(ncpus);
+		if (sysctl(mib, 2, &ncpus, &len, (void *) 0, 0) == -1) {
+			/* Error. */
+			ncpus = 1;
+		}
+	}
+
+	/* Get page size. */
+	{
+		long result;
+
+		result = sysconf(_SC_PAGESIZE);
+		assert(result != -1);
+		pagesize = (unsigned) result;
+	}
+
+	for (i = 0; i < 3; i++) {
+		/* Get runtime configuration. */
+		switch (i) {
+		case 0:
+			if ((linklen = readlink("/etc/malloc.conf", buf,
+						sizeof(buf) - 1)) != -1) {
+				/*
+				 * Use the contents of the "/etc/malloc.conf"
+				 * symbolic link's name.
+				 */
+				buf[linklen] = '\0';
+				opts = buf;
+			} else {
+				/* No configuration specified. */
+				buf[0] = '\0';
+				opts = buf;
+			}
+			break;
+		case 1:
+			if (issetugid() == 0 && (opts =
+			    getenv("MALLOC_OPTIONS")) != NULL) {
+				/*
+				 * Do nothing; opts is already initialized to
+				 * the value of the MALLOC_OPTIONS environment
+				 * variable.
+				 */
+			} else {
+				/* No configuration specified. */
+				buf[0] = '\0';
+				opts = buf;
+			}
+			break;
+		case 2:
+			if (_malloc_options != NULL) {
+			    /*
+			     * Use options that were compiled into the program.
+			     */
+			    opts = _malloc_options;
+			} else {
+				/* No configuration specified. */
+				buf[0] = '\0';
+				opts = buf;
+			}
+			break;
+		default:
+			/* NOTREACHED */
+			assert(false);
+		}
+
+		for (j = 0; opts[j] != '\0'; j++) {
+			switch (opts[j]) {
+			case 'a':
+				opt_abort = false;
+				break;
+			case 'A':
+				opt_abort = true;
+				break;
+			case 'c':
+				opt_ndelay <<= 1;
+				if (opt_ndelay == 0)
+					opt_ndelay = 1;
+				break;
+			case 'C':
+				opt_ndelay >>= 1;
+				if (opt_ndelay == 0)
+					opt_ndelay = 1;
+				break;
+			case 'j':
+				opt_junk = false;
+				break;
+			case 'J':
+				opt_junk = true;
+				break;
+			case 'k':
+				if (opt_chunk_2pow > CHUNK_2POW_MIN)
+					opt_chunk_2pow--;
+				break;
+			case 'K':
+				if (opt_chunk_2pow < CHUNK_2POW_MAX)
+					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 ((1 << opt_quantum_2pow) < pagesize)
+					opt_quantum_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:
+				malloc_printf("%s: (malloc) Unsupported"
+				    " character in malloc options: '%c'\n",
+				    _getprogname(), opts[j]);
+			}
+		}
+	}
+
+	/* Take care to call atexit() only once. */
+	if (opt_print_stats) {
+		/* Print statistics at exit. */
+		atexit(malloc_print_stats);
+	}
+
+	/* Set variables according to the value of opt_quantum_2pow. */
+	quantum = (1 << opt_quantum_2pow);
+	quantum_mask = quantum - 1;
+	bin_shift = ((QUANTUM_CEILING(sizeof(region_small_sizer_t))
+	    >> opt_quantum_2pow));
+	bin_maxsize = ((NBINS + bin_shift - 1) * quantum);
+
+	/* Set variables according to the value of opt_chunk_2pow. */
+	chunk_size = (1 << opt_chunk_2pow);
+	chunk_size_mask = chunk_size - 1;
+
+	UTRACE(0, 0, 0);
+
+#ifdef MALLOC_STATS
+	memset(&stats_chunks, 0, sizeof(chunk_stats_t));
+#endif
+
+	/* Various sanity checks that regard configuration. */
+	assert(quantum >= 2 * sizeof(void *));
+	assert(quantum <= pagesize);
+	assert(chunk_size >= pagesize);
+	assert(quantum * 4 <= chunk_size);
+
+	/* Initialize chunks data. */
+	malloc_mutex_init(&chunks_mtx);
+	RB_INIT(&huge);
+#ifdef USE_BRK
+	brk_base = sbrk(0);
+	brk_prev = brk_base;
+	brk_max = (void *)((size_t)brk_base + MAXDSIZ);
+#endif
+#ifdef MALLOC_STATS
+	huge_allocated = 0;
+	huge_total = 0;
+#endif
+	RB_INIT(&old_chunks);
+
+	/* Create base arena. */
+	arena_new(&base_arena, false, true);
+
+	if (ncpus > 1) {
+		/* 
+		 * For SMP systems, create twice as many arenas as there are
+		 * CPUs by default.
+		 */
+		opt_narenas_lshift++;
+	}
+
+	/* Determine how many arenas to use. */
+	narenas = 1;
+	if (opt_narenas_lshift > 0)
+		narenas <<= opt_narenas_lshift;
+
+#ifdef NO_TLS
+	if (narenas > 1) {
+		static const unsigned primes[] = {1, 3, 5, 7, 11, 13, 17, 19,
+		    23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
+		    89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
+		    151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
+		    223, 227, 229, 233, 239, 241, 251, 257, 263};
+		unsigned i, nprimes, parenas;
+
+		/*
+		 * Pick a prime number of hash arenas that is more than narenas
+		 * so that direct hashing of pthread_self() pointers tends to
+		 * spread allocations evenly among the arenas.
+		 */
+		assert((narenas & 1) == 0); /* narenas must be even. */
+		nprimes = sizeof(primes) / sizeof(unsigned);
+		parenas = primes[nprimes - 1]; /* In case not enough primes. */
+		for (i = 1; i < nprimes; i++) {
+			if (primes[i] > narenas) {
+				parenas = primes[i];
+				break;
+			}
+		}
+		narenas = parenas;
+	}
+#endif
+
+#ifndef NO_TLS
+	next_arena = 0;
+#endif
+
+	/* Allocate and initialize arenas. */
+	arenas = (arena_t **)ipalloc(&base_arena, CACHELINE,
+	    (sizeof(arena_t *) * narenas) + CACHELINE);
+	/* OOM here is fatal. */
+	assert(arenas != NULL);
+	/*
+	 * Zero the array.  In practice, this should always be pre-zeroed,
+	 * since it was just mmap()ed, but let's be sure.
+	 */
+	memset(arenas, 0, sizeof(arena_t *) * narenas);
+
+	/*
+	 * Initialize one arena here.  The rest are lazily created in
+	 * arena_choose_hard().
+	 */
+	arenas_extend(0);
+	/* OOM here is fatal. */
+	assert(arenas[0] != NULL);
+
+	malloc_mutex_init(&arenas_mtx);
+
+	malloc_initialized = true;
+}
+
+/*
+ * End library-internal functions.
+ */
+/******************************************************************************/
+/*
+ * Begin malloc(3)-compatible functions.
  */
 
 void *
 malloc(size_t size)
 {
+	void *ret;
+	arena_t *arena;
 
-    return (pubrealloc(NULL, size, " in malloc():"));
+	malloc_init();
+
+	if (size == 0) {
+		if (opt_sysv == false)
+			ret = &nil;
+		else
+			ret = NULL;
+		goto RETURN;
+	}
+
+	arena = choose_arena();
+	if (arena != NULL)
+		ret = imalloc(arena, size);
+	else
+		ret = NULL;
+
+	if (ret == NULL) {
+		if (opt_xmalloc) {
+			malloc_printf("%s: (malloc) Error in malloc(%zu):"
+			    " out of memory\n", _getprogname(), size);
+			abort();
+		}
+		errno = ENOMEM;
+	} else if (opt_zero)
+		memset(ret, 0, size);
+
+RETURN:
+	UTRACE(0, size, ret);
+	return (ret);
 }
 
 int
 posix_memalign(void **memptr, size_t alignment, size_t size)
 {
-    int err;
-    void *result;
-
-    /* Make sure that alignment is a large enough power of 2. */
-    if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *))
-	    return (EINVAL);
+	int ret;
+	arena_t *arena;
+	void *result;
 
-    /* 
-     * (size | alignment) is enough to assure the requested alignment, since
-     * the allocator always allocates power-of-two blocks.
-     */
-    err = errno; /* Protect errno against changes in pubrealloc(). */
-    result = pubrealloc(NULL, (size | alignment), " in posix_memalign()");
-    errno = err;
+	malloc_init();
 
-    if (result == NULL)
-	return (ENOMEM);
+	/* Make sure that alignment is a large enough power of 2. */
+	if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *)) {
+		if (opt_xmalloc) {
+			malloc_printf("%s: (malloc) Error in"
+			    " posix_memalign(%zu, %zu): invalid alignment\n",
+			    _getprogname(), alignment, size);
+			abort();
+		}
+		result = NULL;
+		ret = EINVAL;
+		goto RETURN;
+	}
 
-    *memptr = result;
-    return (0);
+	arena = choose_arena();
+	if (arena != NULL)
+		result = ipalloc(arena, alignment, size);
+	else
+		result = NULL;
+
+	if (result == NULL) {
+		if (opt_xmalloc) {
+			malloc_printf("%s: (malloc) Error in"
+			    " posix_memalign(%zu, %zu): out of memory\n",
+			    _getprogname(), alignment, size);
+			abort();
+		}
+		ret = ENOMEM;
+		goto RETURN;
+	} else if (opt_zero)
+		memset(result, 0, size);
+
+	*memptr = result;
+	ret = 0;
+
+RETURN:
+	UTRACE(0, size, result);
+	return (ret);
 }
 
 void *
 calloc(size_t num, size_t size)
 {
-    void *ret;
+	void *ret;
+	arena_t *arena;
 
-    if (size != 0 && (num * size) / size != num) {
-	/* size_t overflow. */
-	errno = ENOMEM;
-	return (NULL);
-    }
+	malloc_init();
 
-    ret = pubrealloc(NULL, num * size, " in calloc():");
+	if (num * size == 0) {
+		if (opt_sysv == false)
+			ret = &nil;
+		else
+			ret = NULL;
+		goto RETURN;
+	} else if ((num * size) / size != num) {
+		/* size_t overflow. */
+		ret = NULL;
+		goto RETURN;
+	}
 
-    if (ret != NULL)
-	memset(ret, 0, num * size);
+	arena = choose_arena();
+	if (arena != NULL)
+		ret = icalloc(arena, num, size);
+	else
+		ret = NULL;
+
+RETURN:
+	if (ret == NULL) {
+		if (opt_xmalloc) {
+			malloc_printf("%s: (malloc) Error in"
+			    " calloc(%zu, %zu): out of memory\n", 
+			    _getprogname(), num, size);
+			abort();
+		}
+		errno = ENOMEM;
+	} else if (opt_zero) {
+		/*
+		 * This has the side effect of faulting pages in, even if the
+		 * pages are pre-zeroed by the kernel.
+		 */
+		memset(ret, 0, num * size);
+	}
 
-    return (ret);
+	UTRACE(0, num * size, ret);
+	return (ret);
 }
 
-void
-free(void *ptr)
+void *
+realloc(void *ptr, size_t size)
 {
+	void *ret;
+
+	if (size != 0) {
+		arena_t *arena;
+
+		if (ptr != &nil && ptr != NULL) {
+			assert(malloc_initialized);
+
+			arena = choose_arena();
+			if (arena != NULL)
+				ret = iralloc(arena, ptr, size);
+			else
+				ret = NULL;
+
+			if (ret == NULL) {
+				if (opt_xmalloc) {
+					malloc_printf("%s: (malloc) Error in"
+					    " ralloc(%p, %zu): out of memory\n",
+					    _getprogname(), ptr, size);
+					abort();
+				}
+				errno = ENOMEM;
+			} else if (opt_zero) {
+				size_t old_size;
+
+				old_size = isalloc(ptr);
+
+				if (old_size < size) {
+				    memset(&((char *)ret)[old_size], 0,
+					    size - old_size);
+				}
+			}
+		} else {
+			malloc_init();
+
+			arena = choose_arena();
+			if (arena != NULL)
+				ret = imalloc(arena, size);
+			else
+				ret = NULL;
+
+			if (ret == NULL) {
+				if (opt_xmalloc) {
+					malloc_printf("%s: (malloc) Error in"
+					    " ralloc(%p, %zu): out of memory\n",
+					    _getprogname(), ptr, size);
+					abort();
+				}
+				errno = ENOMEM;
+			} else if (opt_zero)
+				memset(ret, 0, size);
+		}
+	} else {
+		if (ptr != &nil && ptr != NULL)
+			idalloc(ptr);
+
+		ret = &nil;
+	}
 
-    pubrealloc(ptr, 0, " in free():");
+	UTRACE(ptr, size, ret);
+	return (ret);
 }
 
-void *
-realloc(void *ptr, size_t size)
+void
+free(void *ptr)
 {
 
-    return (pubrealloc(ptr, size, " in realloc():"));
+	UTRACE(ptr, 0, 0);
+	if (ptr != &nil && ptr != NULL) {
+		assert(malloc_initialized);
+
+		idalloc(ptr);
+	}
 }
 
 /*
+ * End malloc(3)-compatible functions.
+ */
+/******************************************************************************/
+/*
  * Begin library-private functions, used by threading libraries for protection
  * of malloc during fork().  These functions are only called if the program is
  * running in threaded mode, so there is no need to check whether the program
@@ -1218,13 +4743,42 @@ realloc(void *ptr, size_t size)
 void
 _malloc_prefork(void)
 {
+	unsigned i;
 
-	_spinlock(__malloc_lock);
+	/* Acquire all mutexes in a safe order. */
+
+	malloc_mutex_lock(&arenas_mtx);
+	for (i = 0; i < narenas; i++) {
+		if (arenas[i] != NULL)
+			malloc_mutex_lock(&arenas[i]->mtx);
+	}
+	malloc_mutex_unlock(&arenas_mtx);
+
+	malloc_mutex_lock(&base_arena.mtx);
+
+	malloc_mutex_lock(&chunks_mtx);
 }
 
 void
 _malloc_postfork(void)
 {
+	unsigned i;
+
+	/* Release all mutexes, now that fork() has completed. */
 
-	_spinunlock(__malloc_lock);
+	malloc_mutex_unlock(&chunks_mtx);
+
+	malloc_mutex_unlock(&base_arena.mtx);
+
+	malloc_mutex_lock(&arenas_mtx);
+	for (i = 0; i < narenas; i++) {
+		if (arenas[i] != NULL)
+			malloc_mutex_unlock(&arenas[i]->mtx);
+	}
+	malloc_mutex_unlock(&arenas_mtx);
 }
+
+/*
+ * End library-private functions.
+ */
+/******************************************************************************/