xref: /external/jemalloc/src/arena.c

#define	JEMALLOC_ARENA_C_
#include "jemalloc/internal/jemalloc_internal.h"

/******************************************************************************/
/* Data. */

ssize_t		opt_lg_dirty_mult = LG_DIRTY_MULT_DEFAULT;
arena_bin_info_t	arena_bin_info[NBINS];

JEMALLOC_ATTR(aligned(CACHELINE))
const uint8_t	small_size2bin[] = {
#define	S2B_8(i)	i,
#define	S2B_16(i)	S2B_8(i) S2B_8(i)
#define	S2B_32(i)	S2B_16(i) S2B_16(i)
#define	S2B_64(i)	S2B_32(i) S2B_32(i)
#define	S2B_128(i)	S2B_64(i) S2B_64(i)
#define	S2B_256(i)	S2B_128(i) S2B_128(i)
#define	S2B_512(i)	S2B_256(i) S2B_256(i)
#define	S2B_1024(i)	S2B_512(i) S2B_512(i)
#define	S2B_2048(i)	S2B_1024(i) S2B_1024(i)
#define	S2B_4096(i)	S2B_2048(i) S2B_2048(i)
#define	S2B_8192(i)	S2B_4096(i) S2B_4096(i)
#define	SIZE_CLASS(bin, delta, size)					\
	S2B_##delta(bin)
	SIZE_CLASSES
#undef S2B_8
#undef S2B_16
#undef S2B_32
#undef S2B_64
#undef S2B_128
#undef S2B_256
#undef S2B_512
#undef S2B_1024
#undef S2B_2048
#undef S2B_4096
#undef S2B_8192
#undef SIZE_CLASS
};

/******************************************************************************/
/* Function prototypes for non-inline static functions. */

static void	arena_run_split(arena_t *arena, arena_run_t *run, size_t size,
    bool large, bool zero);
static arena_chunk_t *arena_chunk_alloc(arena_t *arena);
static void	arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk);
static arena_run_t *arena_run_alloc(arena_t *arena, size_t size, bool large,
    bool zero);
static void	arena_purge(arena_t *arena, bool all);
static void	arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty);
static void	arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk,
    arena_run_t *run, size_t oldsize, size_t newsize);
static void	arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk,
    arena_run_t *run, size_t oldsize, size_t newsize, bool dirty);
static arena_run_t	*arena_bin_runs_first(arena_bin_t *bin);
static void	arena_bin_runs_insert(arena_bin_t *bin, arena_run_t *run);
static void	arena_bin_runs_remove(arena_bin_t *bin, arena_run_t *run);
static arena_run_t *arena_bin_nonfull_run_tryget(arena_bin_t *bin);
static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin);
static void	*arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin);
static void	arena_dissociate_bin_run(arena_chunk_t *chunk, arena_run_t *run,
    arena_bin_t *bin);
static void	arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk,
    arena_run_t *run, arena_bin_t *bin);
static void	arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk,
    arena_run_t *run, arena_bin_t *bin);
static void	arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk,
    void *ptr, size_t oldsize, size_t size);
static bool	arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk,
    void *ptr, size_t oldsize, size_t size, size_t extra, bool zero);
static bool	arena_ralloc_large(void *ptr, size_t oldsize, size_t size,
    size_t extra, bool zero);
static size_t	bin_info_run_size_calc(arena_bin_info_t *bin_info,
    size_t min_run_size);
static void	bin_info_init(void);

/******************************************************************************/

static inline int
arena_run_comp(arena_chunk_map_t *a, arena_chunk_map_t *b)
{
	uintptr_t a_mapelm = (uintptr_t)a;
	uintptr_t b_mapelm = (uintptr_t)b;

	assert(a != NULL);
	assert(b != NULL);

	return ((a_mapelm > b_mapelm) - (a_mapelm < b_mapelm));
}

/* Generate red-black tree functions. */
rb_gen(static UNUSED, arena_run_tree_, arena_run_tree_t, arena_chunk_map_t,
    u.rb_link, arena_run_comp)

static inline int
arena_avail_comp(arena_chunk_map_t *a, arena_chunk_map_t *b)
{
	int ret;
	size_t a_size = a->bits & ~PAGE_MASK;
	size_t b_size = b->bits & ~PAGE_MASK;

	assert((a->bits & CHUNK_MAP_KEY) == CHUNK_MAP_KEY || (a->bits &
	    CHUNK_MAP_DIRTY) == (b->bits & CHUNK_MAP_DIRTY));

	ret = (a_size > b_size) - (a_size < b_size);
	if (ret == 0) {
		uintptr_t a_mapelm, b_mapelm;

		if ((a->bits & CHUNK_MAP_KEY) != CHUNK_MAP_KEY)
			a_mapelm = (uintptr_t)a;
		else {
			/*
			 * Treat keys as though they are lower than anything
			 * else.
			 */
			a_mapelm = 0;
		}
		b_mapelm = (uintptr_t)b;

		ret = (a_mapelm > b_mapelm) - (a_mapelm < b_mapelm);
	}

	return (ret);
}

/* Generate red-black tree functions. */
rb_gen(static UNUSED, arena_avail_tree_, arena_avail_tree_t, arena_chunk_map_t,
    u.rb_link, arena_avail_comp)

static inline void *
arena_run_reg_alloc(arena_run_t *run, arena_bin_info_t *bin_info)
{
	void *ret;
	unsigned regind;
	bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run +
	    (uintptr_t)bin_info->bitmap_offset);

	assert(run->nfree > 0);
	assert(bitmap_full(bitmap, &bin_info->bitmap_info) == false);

	regind = bitmap_sfu(bitmap, &bin_info->bitmap_info);
	ret = (void *)((uintptr_t)run + (uintptr_t)bin_info->reg0_offset +
	    (uintptr_t)(bin_info->reg_size * regind));
	run->nfree--;
	if (regind == run->nextind)
		run->nextind++;
	assert(regind < run->nextind);
	return (ret);
}

static inline void
arena_run_reg_dalloc(arena_run_t *run, void *ptr)
{
	arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
	size_t binind = arena_bin_index(chunk->arena, run->bin);
	arena_bin_info_t *bin_info = &arena_bin_info[binind];
	unsigned regind = arena_run_regind(run, bin_info, ptr);
	bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run +
	    (uintptr_t)bin_info->bitmap_offset);

	assert(run->nfree < bin_info->nregs);
	/* Freeing an interior pointer can cause assertion failure. */
	assert(((uintptr_t)ptr - ((uintptr_t)run +
	    (uintptr_t)bin_info->reg0_offset)) % (uintptr_t)bin_info->reg_size
	    == 0);
	assert((uintptr_t)ptr >= (uintptr_t)run +
	    (uintptr_t)bin_info->reg0_offset);
	/* Freeing an unallocated pointer can cause assertion failure. */
	assert(bitmap_get(bitmap, &bin_info->bitmap_info, regind));

	bitmap_unset(bitmap, &bin_info->bitmap_info, regind);
	run->nfree++;
}

static inline void
arena_chunk_validate_zeroed(arena_chunk_t *chunk, size_t run_ind)
{
	size_t i;
	UNUSED size_t *p = (size_t *)((uintptr_t)chunk + (run_ind <<
	    PAGE_SHIFT));

	for (i = 0; i < PAGE_SIZE / sizeof(size_t); i++)
		assert(p[i] == 0);
}

static void
arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool large,
    bool zero)
{
	arena_chunk_t *chunk;
	size_t run_ind, total_pages, need_pages, rem_pages, i;
	size_t flag_dirty;
	arena_avail_tree_t *runs_avail;

	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
	run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
	    >> PAGE_SHIFT);
	flag_dirty = chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY;
	runs_avail = (flag_dirty != 0) ? &arena->runs_avail_dirty :
	    &arena->runs_avail_clean;
	total_pages = (chunk->map[run_ind-map_bias].bits & ~PAGE_MASK) >>
	    PAGE_SHIFT;
	assert((chunk->map[run_ind+total_pages-1-map_bias].bits &
	    CHUNK_MAP_DIRTY) == flag_dirty);
	need_pages = (size >> PAGE_SHIFT);
	assert(need_pages > 0);
	assert(need_pages <= total_pages);
	rem_pages = total_pages - need_pages;

	arena_avail_tree_remove(runs_avail, &chunk->map[run_ind-map_bias]);
	if (config_stats) {
		/*
		 * Update stats_cactive if nactive is crossing a chunk
		 * multiple.
		 */
		size_t cactive_diff = CHUNK_CEILING((arena->nactive +
		    need_pages) << PAGE_SHIFT) - CHUNK_CEILING(arena->nactive <<
		    PAGE_SHIFT);
		if (cactive_diff != 0)
			stats_cactive_add(cactive_diff);
	}
	arena->nactive += need_pages;

	/* Keep track of trailing unused pages for later use. */
	if (rem_pages > 0) {
		if (flag_dirty != 0) {
			chunk->map[run_ind+need_pages-map_bias].bits =
			    (rem_pages << PAGE_SHIFT) | CHUNK_MAP_DIRTY;
			chunk->map[run_ind+total_pages-1-map_bias].bits =
			    (rem_pages << PAGE_SHIFT) | CHUNK_MAP_DIRTY;
		} else {
			chunk->map[run_ind+need_pages-map_bias].bits =
			    (rem_pages << PAGE_SHIFT) |
			    (chunk->map[run_ind+need_pages-map_bias].bits &
			    CHUNK_MAP_UNZEROED);
			chunk->map[run_ind+total_pages-1-map_bias].bits =
			    (rem_pages << PAGE_SHIFT) |
			    (chunk->map[run_ind+total_pages-1-map_bias].bits &
			    CHUNK_MAP_UNZEROED);
		}
		arena_avail_tree_insert(runs_avail,
		    &chunk->map[run_ind+need_pages-map_bias]);
	}

	/* Update dirty page accounting. */
	if (flag_dirty != 0) {
		chunk->ndirty -= need_pages;
		arena->ndirty -= need_pages;
	}

	/*
	 * Update the page map separately for large vs. small runs, since it is
	 * possible to avoid iteration for large mallocs.
	 */
	if (large) {
		if (zero) {
			if (flag_dirty == 0) {
				/*
				 * The run is clean, so some pages may be
				 * zeroed (i.e. never before touched).
				 */
				for (i = 0; i < need_pages; i++) {
					if ((chunk->map[run_ind+i-map_bias].bits
					    & CHUNK_MAP_UNZEROED) != 0) {
						memset((void *)((uintptr_t)
						    chunk + ((run_ind+i) <<
						    PAGE_SHIFT)), 0,
						    PAGE_SIZE);
					} else if (config_debug) {
						arena_chunk_validate_zeroed(
						    chunk, run_ind+i);
					}
				}
			} else {
				/*
				 * The run is dirty, so all pages must be
				 * zeroed.
				 */
				memset((void *)((uintptr_t)chunk + (run_ind <<
				    PAGE_SHIFT)), 0, (need_pages <<
				    PAGE_SHIFT));
			}
		}

		/*
		 * Set the last element first, in case the run only contains one
		 * page (i.e. both statements set the same element).
		 */
		chunk->map[run_ind+need_pages-1-map_bias].bits =
		    CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED | flag_dirty;
		chunk->map[run_ind-map_bias].bits = size | flag_dirty |
		    CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED;
	} else {
		assert(zero == false);
		/*
		 * Propagate the dirty and unzeroed flags to the allocated
		 * small run, so that arena_dalloc_bin_run() has the ability to
		 * conditionally trim clean pages.
		 */
		chunk->map[run_ind-map_bias].bits =
		    (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_UNZEROED) |
		    CHUNK_MAP_ALLOCATED | flag_dirty;
		/*
		 * The first page will always be dirtied during small run
		 * initialization, so a validation failure here would not
		 * actually cause an observable failure.
		 */
		if (config_debug && flag_dirty == 0 &&
		    (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_UNZEROED)
		    == 0)
			arena_chunk_validate_zeroed(chunk, run_ind);
		for (i = 1; i < need_pages - 1; i++) {
			chunk->map[run_ind+i-map_bias].bits = (i << PAGE_SHIFT)
			    | (chunk->map[run_ind+i-map_bias].bits &
			    CHUNK_MAP_UNZEROED) | CHUNK_MAP_ALLOCATED;
			if (config_debug && flag_dirty == 0 &&
			    (chunk->map[run_ind+i-map_bias].bits &
			    CHUNK_MAP_UNZEROED) == 0)
				arena_chunk_validate_zeroed(chunk, run_ind+i);
		}
		chunk->map[run_ind+need_pages-1-map_bias].bits = ((need_pages
		    - 1) << PAGE_SHIFT) |
		    (chunk->map[run_ind+need_pages-1-map_bias].bits &
		    CHUNK_MAP_UNZEROED) | CHUNK_MAP_ALLOCATED | flag_dirty;
		if (config_debug && flag_dirty == 0 &&
		    (chunk->map[run_ind+need_pages-1-map_bias].bits &
		    CHUNK_MAP_UNZEROED) == 0) {
			arena_chunk_validate_zeroed(chunk,
			    run_ind+need_pages-1);
		}
	}
}

static arena_chunk_t *
arena_chunk_alloc(arena_t *arena)
{
	arena_chunk_t *chunk;
	size_t i;

	if (arena->spare != NULL) {
		arena_avail_tree_t *runs_avail;

		chunk = arena->spare;
		arena->spare = NULL;

		/* Insert the run into the appropriate runs_avail_* tree. */
		if ((chunk->map[0].bits & CHUNK_MAP_DIRTY) == 0)
			runs_avail = &arena->runs_avail_clean;
		else
			runs_avail = &arena->runs_avail_dirty;
		assert((chunk->map[0].bits & ~PAGE_MASK) == arena_maxclass);
		assert((chunk->map[chunk_npages-1-map_bias].bits & ~PAGE_MASK)
		    == arena_maxclass);
		assert((chunk->map[0].bits & CHUNK_MAP_DIRTY) ==
		    (chunk->map[chunk_npages-1-map_bias].bits &
		    CHUNK_MAP_DIRTY));
		arena_avail_tree_insert(runs_avail, &chunk->map[0]);
	} else {
		bool zero;
		size_t unzeroed;

		zero = false;
		malloc_mutex_unlock(&arena->lock);
		chunk = (arena_chunk_t *)chunk_alloc(chunksize, false, &zero);
		malloc_mutex_lock(&arena->lock);
		if (chunk == NULL)
			return (NULL);
		if (config_stats)
			arena->stats.mapped += chunksize;

		chunk->arena = arena;
		ql_elm_new(chunk, link_dirty);
		chunk->dirtied = false;

		/*
		 * Claim that no pages are in use, since the header is merely
		 * overhead.
		 */
		chunk->ndirty = 0;

		/*
		 * Initialize the map to contain one maximal free untouched run.
		 * Mark the pages as zeroed iff chunk_alloc() returned a zeroed
		 * chunk.
		 */
		unzeroed = zero ? 0 : CHUNK_MAP_UNZEROED;
		chunk->map[0].bits = arena_maxclass | unzeroed;
		/*
		 * There is no need to initialize the internal page map entries
		 * unless the chunk is not zeroed.
		 */
		if (zero == false) {
			for (i = map_bias+1; i < chunk_npages-1; i++)
				chunk->map[i-map_bias].bits = unzeroed;
		} else if (config_debug) {
			for (i = map_bias+1; i < chunk_npages-1; i++)
				assert(chunk->map[i-map_bias].bits == unzeroed);
		}
		chunk->map[chunk_npages-1-map_bias].bits = arena_maxclass |
		    unzeroed;

		/* Insert the run into the runs_avail_clean tree. */
		arena_avail_tree_insert(&arena->runs_avail_clean,
		    &chunk->map[0]);
	}

	return (chunk);
}

static void
arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk)
{
	arena_avail_tree_t *runs_avail;

	/*
	 * Remove run from the appropriate runs_avail_* tree, so that the arena
	 * does not use it.
	 */
	if ((chunk->map[0].bits & CHUNK_MAP_DIRTY) == 0)
		runs_avail = &arena->runs_avail_clean;
	else
		runs_avail = &arena->runs_avail_dirty;
	arena_avail_tree_remove(runs_avail, &chunk->map[0]);

	if (arena->spare != NULL) {
		arena_chunk_t *spare = arena->spare;

		arena->spare = chunk;
		if (spare->dirtied) {
			ql_remove(&chunk->arena->chunks_dirty, spare,
			    link_dirty);
			arena->ndirty -= spare->ndirty;
		}
		malloc_mutex_unlock(&arena->lock);
		chunk_dealloc((void *)spare, chunksize, true);
		malloc_mutex_lock(&arena->lock);
		if (config_stats)
			arena->stats.mapped -= chunksize;
	} else
		arena->spare = chunk;
}

static arena_run_t *
arena_run_alloc(arena_t *arena, size_t size, bool large, bool zero)
{
	arena_chunk_t *chunk;
	arena_run_t *run;
	arena_chunk_map_t *mapelm, key;

	assert(size <= arena_maxclass);
	assert((size & PAGE_MASK) == 0);

	/* Search the arena's chunks for the lowest best fit. */
	key.bits = size | CHUNK_MAP_KEY;
	mapelm = arena_avail_tree_nsearch(&arena->runs_avail_dirty, &key);
	if (mapelm != NULL) {
		arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm);
		size_t pageind = (((uintptr_t)mapelm -
		    (uintptr_t)run_chunk->map) / sizeof(arena_chunk_map_t))
		    + map_bias;

		run = (arena_run_t *)((uintptr_t)run_chunk + (pageind <<
		    PAGE_SHIFT));
		arena_run_split(arena, run, size, large, zero);
		return (run);
	}
	mapelm = arena_avail_tree_nsearch(&arena->runs_avail_clean, &key);
	if (mapelm != NULL) {
		arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm);
		size_t pageind = (((uintptr_t)mapelm -
		    (uintptr_t)run_chunk->map) / sizeof(arena_chunk_map_t))
		    + map_bias;

		run = (arena_run_t *)((uintptr_t)run_chunk + (pageind <<
		    PAGE_SHIFT));
		arena_run_split(arena, run, size, large, zero);
		return (run);
	}

	/*
	 * No usable runs.  Create a new chunk from which to allocate the run.
	 */
	chunk = arena_chunk_alloc(arena);
	if (chunk != NULL) {
		run = (arena_run_t *)((uintptr_t)chunk + (map_bias <<
		    PAGE_SHIFT));
		arena_run_split(arena, run, size, large, zero);
		return (run);
	}

	/*
	 * arena_chunk_alloc() failed, but another thread may have made
	 * sufficient memory available while this one dropped arena->lock in
	 * arena_chunk_alloc(), so search one more time.
	 */
	mapelm = arena_avail_tree_nsearch(&arena->runs_avail_dirty, &key);
	if (mapelm != NULL) {
		arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm);
		size_t pageind = (((uintptr_t)mapelm -
		    (uintptr_t)run_chunk->map) / sizeof(arena_chunk_map_t))
		    + map_bias;

		run = (arena_run_t *)((uintptr_t)run_chunk + (pageind <<
		    PAGE_SHIFT));
		arena_run_split(arena, run, size, large, zero);
		return (run);
	}
	mapelm = arena_avail_tree_nsearch(&arena->runs_avail_clean, &key);
	if (mapelm != NULL) {
		arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm);
		size_t pageind = (((uintptr_t)mapelm -
		    (uintptr_t)run_chunk->map) / sizeof(arena_chunk_map_t))
		    + map_bias;

		run = (arena_run_t *)((uintptr_t)run_chunk + (pageind <<
		    PAGE_SHIFT));
		arena_run_split(arena, run, size, large, zero);
		return (run);
	}

	return (NULL);
}

static inline void
arena_maybe_purge(arena_t *arena)
{

	/* Enforce opt_lg_dirty_mult. */
	if (opt_lg_dirty_mult >= 0 && arena->ndirty > arena->npurgatory &&
	    (arena->ndirty - arena->npurgatory) > chunk_npages &&
	    (arena->nactive >> opt_lg_dirty_mult) < (arena->ndirty -
	    arena->npurgatory))
		arena_purge(arena, false);
}

static inline void
arena_chunk_purge(arena_t *arena, arena_chunk_t *chunk)
{
	ql_head(arena_chunk_map_t) mapelms;
	arena_chunk_map_t *mapelm;
	size_t pageind, flag_unzeroed;
	size_t ndirty;
	size_t nmadvise;

	ql_new(&mapelms);

	flag_unzeroed =
#ifdef JEMALLOC_PURGE_MADVISE_DONTNEED
   /*
    * madvise(..., MADV_DONTNEED) results in zero-filled pages for anonymous
    * mappings, but not for file-backed mappings.
    */
	    0
#else
	    CHUNK_MAP_UNZEROED
#endif
	    ;

	/*
	 * If chunk is the spare, temporarily re-allocate it, 1) so that its
	 * run is reinserted into runs_avail_dirty, and 2) so that it cannot be
	 * completely discarded by another thread while arena->lock is dropped
	 * by this thread.  Note that the arena_run_dalloc() call will
	 * implicitly deallocate the chunk, so no explicit action is required
	 * in this function to deallocate the chunk.
	 *
	 * Note that once a chunk contains dirty pages, it cannot again contain
	 * a single run unless 1) it is a dirty run, or 2) this function purges
	 * dirty pages and causes the transition to a single clean run.  Thus
	 * (chunk == arena->spare) is possible, but it is not possible for
	 * this function to be called on the spare unless it contains a dirty
	 * run.
	 */
	if (chunk == arena->spare) {
		assert((chunk->map[0].bits & CHUNK_MAP_DIRTY) != 0);
		arena_chunk_alloc(arena);
	}

	/* Temporarily allocate all free dirty runs within chunk. */
	for (pageind = map_bias; pageind < chunk_npages;) {
		mapelm = &chunk->map[pageind-map_bias];
		if ((mapelm->bits & CHUNK_MAP_ALLOCATED) == 0) {
			size_t npages;

			npages = mapelm->bits >> PAGE_SHIFT;
			assert(pageind + npages <= chunk_npages);
			if (mapelm->bits & CHUNK_MAP_DIRTY) {
				size_t i;

				arena_avail_tree_remove(
				    &arena->runs_avail_dirty, mapelm);

				mapelm->bits = (npages << PAGE_SHIFT) |
				    flag_unzeroed | CHUNK_MAP_LARGE |
				    CHUNK_MAP_ALLOCATED;
				/*
				 * Update internal elements in the page map, so
				 * that CHUNK_MAP_UNZEROED is properly set.
				 */
				for (i = 1; i < npages - 1; i++) {
					chunk->map[pageind+i-map_bias].bits =
					    flag_unzeroed;
				}
				if (npages > 1) {
					chunk->map[
					    pageind+npages-1-map_bias].bits =
					    flag_unzeroed | CHUNK_MAP_LARGE |
					    CHUNK_MAP_ALLOCATED;
				}

				if (config_stats) {
					/*
					 * Update stats_cactive if nactive is
					 * crossing a chunk multiple.
					 */
					size_t cactive_diff =
					    CHUNK_CEILING((arena->nactive +
					    npages) << PAGE_SHIFT) -
					    CHUNK_CEILING(arena->nactive <<
					    PAGE_SHIFT);
					if (cactive_diff != 0)
						stats_cactive_add(cactive_diff);
				}
				arena->nactive += npages;
				/* Append to list for later processing. */
				ql_elm_new(mapelm, u.ql_link);
				ql_tail_insert(&mapelms, mapelm, u.ql_link);
			}

			pageind += npages;
		} else {
			/* Skip allocated run. */
			if (mapelm->bits & CHUNK_MAP_LARGE)
				pageind += mapelm->bits >> PAGE_SHIFT;
			else {
				arena_run_t *run = (arena_run_t *)((uintptr_t)
				    chunk + (uintptr_t)(pageind << PAGE_SHIFT));

				assert((mapelm->bits >> PAGE_SHIFT) == 0);
				size_t binind = arena_bin_index(arena,
				    run->bin);
				arena_bin_info_t *bin_info =
				    &arena_bin_info[binind];
				pageind += bin_info->run_size >> PAGE_SHIFT;
			}
		}
	}
	assert(pageind == chunk_npages);

	if (config_debug)
		ndirty = chunk->ndirty;
	if (config_stats)
		arena->stats.purged += chunk->ndirty;
	arena->ndirty -= chunk->ndirty;
	chunk->ndirty = 0;
	ql_remove(&arena->chunks_dirty, chunk, link_dirty);
	chunk->dirtied = false;

	malloc_mutex_unlock(&arena->lock);
	if (config_stats)
		nmadvise = 0;
	ql_foreach(mapelm, &mapelms, u.ql_link) {
		size_t pageind = (((uintptr_t)mapelm - (uintptr_t)chunk->map) /
		    sizeof(arena_chunk_map_t)) + map_bias;
		size_t npages = mapelm->bits >> PAGE_SHIFT;

		assert(pageind + npages <= chunk_npages);
		assert(ndirty >= npages);
		if (config_debug)
			ndirty -= npages;

#ifdef JEMALLOC_PURGE_MADVISE_DONTNEED
#  define MADV_PURGE MADV_DONTNEED
#elif defined(JEMALLOC_PURGE_MADVISE_FREE)
#  define MADV_PURGE MADV_FREE
#else
#  error "No method defined for purging unused dirty pages."
#endif
		madvise((void *)((uintptr_t)chunk + (pageind << PAGE_SHIFT)),
		    (npages << PAGE_SHIFT), MADV_PURGE);
#undef MADV_PURGE
		if (config_stats)
			nmadvise++;
	}
	assert(ndirty == 0);
	malloc_mutex_lock(&arena->lock);
	if (config_stats)
		arena->stats.nmadvise += nmadvise;

	/* Deallocate runs. */
	for (mapelm = ql_first(&mapelms); mapelm != NULL;
	    mapelm = ql_first(&mapelms)) {
		size_t pageind = (((uintptr_t)mapelm - (uintptr_t)chunk->map) /
		    sizeof(arena_chunk_map_t)) + map_bias;
		arena_run_t *run = (arena_run_t *)((uintptr_t)chunk +
		    (uintptr_t)(pageind << PAGE_SHIFT));

		ql_remove(&mapelms, mapelm, u.ql_link);
		arena_run_dalloc(arena, run, false);
	}
}

static void
arena_purge(arena_t *arena, bool all)
{
	arena_chunk_t *chunk;
	size_t npurgatory;
	if (config_debug) {
		size_t ndirty = 0;

		ql_foreach(chunk, &arena->chunks_dirty, link_dirty) {
		    assert(chunk->dirtied);
		    ndirty += chunk->ndirty;
		}
		assert(ndirty == arena->ndirty);
	}
	assert(arena->ndirty > arena->npurgatory || all);
	assert(arena->ndirty - arena->npurgatory > chunk_npages || all);
	assert((arena->nactive >> opt_lg_dirty_mult) < (arena->ndirty -
	    arena->npurgatory) || all);

	if (config_stats)
		arena->stats.npurge++;

	/*
	 * Compute the minimum number of pages that this thread should try to
	 * purge, and add the result to arena->npurgatory.  This will keep
	 * multiple threads from racing to reduce ndirty below the threshold.
	 */
	npurgatory = arena->ndirty - arena->npurgatory;
	if (all == false) {
		assert(npurgatory >= arena->nactive >> opt_lg_dirty_mult);
		npurgatory -= arena->nactive >> opt_lg_dirty_mult;
	}
	arena->npurgatory += npurgatory;

	while (npurgatory > 0) {
		/* Get next chunk with dirty pages. */
		chunk = ql_first(&arena->chunks_dirty);
		if (chunk == NULL) {
			/*
			 * This thread was unable to purge as many pages as
			 * originally intended, due to races with other threads
			 * that either did some of the purging work, or re-used
			 * dirty pages.
			 */
			arena->npurgatory -= npurgatory;
			return;
		}
		while (chunk->ndirty == 0) {
			ql_remove(&arena->chunks_dirty, chunk, link_dirty);
			chunk->dirtied = false;
			chunk = ql_first(&arena->chunks_dirty);
			if (chunk == NULL) {
				/* Same logic as for above. */
				arena->npurgatory -= npurgatory;
				return;
			}
		}

		if (chunk->ndirty > npurgatory) {
			/*
			 * This thread will, at a minimum, purge all the dirty
			 * pages in chunk, so set npurgatory to reflect this
			 * thread's commitment to purge the pages.  This tends
			 * to reduce the chances of the following scenario:
			 *
			 * 1) This thread sets arena->npurgatory such that
			 *    (arena->ndirty - arena->npurgatory) is at the
			 *    threshold.
			 * 2) This thread drops arena->lock.
			 * 3) Another thread causes one or more pages to be
			 *    dirtied, and immediately determines that it must
			 *    purge dirty pages.
			 *
			 * If this scenario *does* play out, that's okay,
			 * because all of the purging work being done really
			 * needs to happen.
			 */
			arena->npurgatory += chunk->ndirty - npurgatory;
			npurgatory = chunk->ndirty;
		}

		arena->npurgatory -= chunk->ndirty;
		npurgatory -= chunk->ndirty;
		arena_chunk_purge(arena, chunk);
	}
}

void
arena_purge_all(arena_t *arena)
{

	malloc_mutex_lock(&arena->lock);
	arena_purge(arena, true);
	malloc_mutex_unlock(&arena->lock);
}

static void
arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty)
{
	arena_chunk_t *chunk;
	size_t size, run_ind, run_pages, flag_dirty;
	arena_avail_tree_t *runs_avail;

	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
	run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk)
	    >> PAGE_SHIFT);
	assert(run_ind >= map_bias);
	assert(run_ind < chunk_npages);
	if ((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_LARGE) != 0) {
		size = chunk->map[run_ind-map_bias].bits & ~PAGE_MASK;
		assert(size == PAGE_SIZE ||
		    (chunk->map[run_ind+(size>>PAGE_SHIFT)-1-map_bias].bits &
		    ~PAGE_MASK) == 0);
		assert((chunk->map[run_ind+(size>>PAGE_SHIFT)-1-map_bias].bits &
		    CHUNK_MAP_LARGE) != 0);
		assert((chunk->map[run_ind+(size>>PAGE_SHIFT)-1-map_bias].bits &
		    CHUNK_MAP_ALLOCATED) != 0);
	} else {
		size_t binind = arena_bin_index(arena, run->bin);
		arena_bin_info_t *bin_info = &arena_bin_info[binind];
		size = bin_info->run_size;
	}
	run_pages = (size >> PAGE_SHIFT);
	if (config_stats) {
		/*
		 * Update stats_cactive if nactive is crossing a chunk
		 * multiple.
		 */
		size_t cactive_diff = CHUNK_CEILING(arena->nactive <<
		    PAGE_SHIFT) - CHUNK_CEILING((arena->nactive - run_pages) <<
		    PAGE_SHIFT);
		if (cactive_diff != 0)
			stats_cactive_sub(cactive_diff);
	}
	arena->nactive -= run_pages;

	/*
	 * The run is dirty if the caller claims to have dirtied it, as well as
	 * if it was already dirty before being allocated.
	 */
	if ((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY) != 0)
		dirty = true;
	flag_dirty = dirty ? CHUNK_MAP_DIRTY : 0;
	runs_avail = dirty ? &arena->runs_avail_dirty :
	    &arena->runs_avail_clean;

	/* Mark pages as unallocated in the chunk map. */
	if (dirty) {
		chunk->map[run_ind-map_bias].bits = size | CHUNK_MAP_DIRTY;
		chunk->map[run_ind+run_pages-1-map_bias].bits = size |
		    CHUNK_MAP_DIRTY;

		chunk->ndirty += run_pages;
		arena->ndirty += run_pages;
	} else {
		chunk->map[run_ind-map_bias].bits = size |
		    (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_UNZEROED);
		chunk->map[run_ind+run_pages-1-map_bias].bits = size |
		    (chunk->map[run_ind+run_pages-1-map_bias].bits &
		    CHUNK_MAP_UNZEROED);
	}

	/* Try to coalesce forward. */
	if (run_ind + run_pages < chunk_npages &&
	    (chunk->map[run_ind+run_pages-map_bias].bits & CHUNK_MAP_ALLOCATED)
	    == 0 && (chunk->map[run_ind+run_pages-map_bias].bits &
	    CHUNK_MAP_DIRTY) == flag_dirty) {
		size_t nrun_size = chunk->map[run_ind+run_pages-map_bias].bits &
		    ~PAGE_MASK;
		size_t nrun_pages = nrun_size >> PAGE_SHIFT;

		/*
		 * Remove successor from runs_avail; the coalesced run is
		 * inserted later.
		 */
		assert((chunk->map[run_ind+run_pages+nrun_pages-1-map_bias].bits
		    & ~PAGE_MASK) == nrun_size);
		assert((chunk->map[run_ind+run_pages+nrun_pages-1-map_bias].bits
		    & CHUNK_MAP_ALLOCATED) == 0);
		assert((chunk->map[run_ind+run_pages+nrun_pages-1-map_bias].bits
		    & CHUNK_MAP_DIRTY) == flag_dirty);
		arena_avail_tree_remove(runs_avail,
		    &chunk->map[run_ind+run_pages-map_bias]);

		size += nrun_size;
		run_pages += nrun_pages;

		chunk->map[run_ind-map_bias].bits = size |
		    (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_FLAGS_MASK);
		chunk->map[run_ind+run_pages-1-map_bias].bits = size |
		    (chunk->map[run_ind+run_pages-1-map_bias].bits &
		    CHUNK_MAP_FLAGS_MASK);
	}

	/* Try to coalesce backward. */
	if (run_ind > map_bias && (chunk->map[run_ind-1-map_bias].bits &
	    CHUNK_MAP_ALLOCATED) == 0 && (chunk->map[run_ind-1-map_bias].bits &
	    CHUNK_MAP_DIRTY) == flag_dirty) {
		size_t prun_size = chunk->map[run_ind-1-map_bias].bits &
		    ~PAGE_MASK;
		size_t prun_pages = prun_size >> PAGE_SHIFT;

		run_ind -= prun_pages;

		/*
		 * Remove predecessor from runs_avail; the coalesced run is
		 * inserted later.
		 */
		assert((chunk->map[run_ind-map_bias].bits & ~PAGE_MASK)
		    == prun_size);
		assert((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_ALLOCATED)
		    == 0);
		assert((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY)
		    == flag_dirty);
		arena_avail_tree_remove(runs_avail,
		    &chunk->map[run_ind-map_bias]);

		size += prun_size;
		run_pages += prun_pages;

		chunk->map[run_ind-map_bias].bits = size |
		    (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_FLAGS_MASK);
		chunk->map[run_ind+run_pages-1-map_bias].bits = size |
		    (chunk->map[run_ind+run_pages-1-map_bias].bits &
		    CHUNK_MAP_FLAGS_MASK);
	}

	/* Insert into runs_avail, now that coalescing is complete. */
	assert((chunk->map[run_ind-map_bias].bits & ~PAGE_MASK) ==
	    (chunk->map[run_ind+run_pages-1-map_bias].bits & ~PAGE_MASK));
	assert((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY) ==
	    (chunk->map[run_ind+run_pages-1-map_bias].bits & CHUNK_MAP_DIRTY));
	arena_avail_tree_insert(runs_avail, &chunk->map[run_ind-map_bias]);

	if (dirty) {
		/*
		 * Insert into chunks_dirty before potentially calling
		 * arena_chunk_dealloc(), so that chunks_dirty and
		 * arena->ndirty are consistent.
		 */
		if (chunk->dirtied == false) {
			ql_tail_insert(&arena->chunks_dirty, chunk, link_dirty);
			chunk->dirtied = true;
		}
	}

	/*
	 * Deallocate chunk if it is now completely unused.  The bit
	 * manipulation checks whether the first run is unallocated and extends
	 * to the end of the chunk.
	 */
	if ((chunk->map[0].bits & (~PAGE_MASK | CHUNK_MAP_ALLOCATED)) ==
	    arena_maxclass)
		arena_chunk_dealloc(arena, chunk);

	/*
	 * It is okay to do dirty page processing here even if the chunk was
	 * deallocated above, since in that case it is the spare.  Waiting
	 * until after possible chunk deallocation to do dirty processing
	 * allows for an old spare to be fully deallocated, thus decreasing the
	 * chances of spuriously crossing the dirty page purging threshold.
	 */
	if (dirty)
		arena_maybe_purge(arena);
}

static void
arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
    size_t oldsize, size_t newsize)
{
	size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT;
	size_t head_npages = (oldsize - newsize) >> PAGE_SHIFT;
	size_t flag_dirty = chunk->map[pageind-map_bias].bits & CHUNK_MAP_DIRTY;

	assert(oldsize > newsize);

	/*
	 * Update the chunk map so that arena_run_dalloc() can treat the
	 * leading run as separately allocated.  Set the last element of each
	 * run first, in case of single-page runs.
	 */
	assert((chunk->map[pageind-map_bias].bits & CHUNK_MAP_LARGE) != 0);
	assert((chunk->map[pageind-map_bias].bits & CHUNK_MAP_ALLOCATED) != 0);
	chunk->map[pageind+head_npages-1-map_bias].bits = flag_dirty |
	    (chunk->map[pageind+head_npages-1-map_bias].bits &
	    CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED;
	chunk->map[pageind-map_bias].bits = (oldsize - newsize)
	    | flag_dirty | (chunk->map[pageind-map_bias].bits &
	    CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED;

	if (config_debug) {
		UNUSED size_t tail_npages = newsize >> PAGE_SHIFT;
		assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias]
		    .bits & ~PAGE_MASK) == 0);
		assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias]
		    .bits & CHUNK_MAP_DIRTY) == flag_dirty);
		assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias]
		    .bits & CHUNK_MAP_LARGE) != 0);
		assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias]
		    .bits & CHUNK_MAP_ALLOCATED) != 0);
	}
	chunk->map[pageind+head_npages-map_bias].bits = newsize | flag_dirty |
	    (chunk->map[pageind+head_npages-map_bias].bits &
	    CHUNK_MAP_FLAGS_MASK) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED;

	arena_run_dalloc(arena, run, false);
}

static void
arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
    size_t oldsize, size_t newsize, bool dirty)
{
	size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT;
	size_t head_npages = newsize >> PAGE_SHIFT;
	size_t tail_npages = (oldsize - newsize) >> PAGE_SHIFT;
	size_t flag_dirty = chunk->map[pageind-map_bias].bits &
	    CHUNK_MAP_DIRTY;

	assert(oldsize > newsize);

	/*
	 * Update the chunk map so that arena_run_dalloc() can treat the
	 * trailing run as separately allocated.  Set the last element of each
	 * run first, in case of single-page runs.
	 */
	assert((chunk->map[pageind-map_bias].bits & CHUNK_MAP_LARGE) != 0);
	assert((chunk->map[pageind-map_bias].bits & CHUNK_MAP_ALLOCATED) != 0);
	chunk->map[pageind+head_npages-1-map_bias].bits = flag_dirty |
	    (chunk->map[pageind+head_npages-1-map_bias].bits &
	    CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED;
	chunk->map[pageind-map_bias].bits = newsize | flag_dirty |
	    (chunk->map[pageind-map_bias].bits & CHUNK_MAP_UNZEROED) |
	    CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED;

	assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias].bits &
	    ~PAGE_MASK) == 0);
	assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias].bits &
	    CHUNK_MAP_LARGE) != 0);
	assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias].bits &
	    CHUNK_MAP_ALLOCATED) != 0);
	chunk->map[pageind+head_npages+tail_npages-1-map_bias].bits =
	    flag_dirty |
	    (chunk->map[pageind+head_npages+tail_npages-1-map_bias].bits &
	    CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED;
	chunk->map[pageind+head_npages-map_bias].bits = (oldsize - newsize) |
	    flag_dirty | (chunk->map[pageind+head_npages-map_bias].bits &
	    CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED;

	arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)run + newsize),
	    dirty);
}

static arena_run_t *
arena_bin_runs_first(arena_bin_t *bin)
{
	arena_chunk_map_t *mapelm = arena_run_tree_first(&bin->runs);
	if (mapelm != NULL) {
		arena_chunk_t *chunk;
		size_t pageind;

		chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(mapelm);
		pageind = ((((uintptr_t)mapelm - (uintptr_t)chunk->map) /
		    sizeof(arena_chunk_map_t))) + map_bias;
		arena_run_t *run = (arena_run_t *)((uintptr_t)chunk +
		    (uintptr_t)((pageind - (mapelm->bits >> PAGE_SHIFT)) <<
		    PAGE_SHIFT));
		return (run);
	}

	return (NULL);
}

static void
arena_bin_runs_insert(arena_bin_t *bin, arena_run_t *run)
{
	arena_chunk_t *chunk = CHUNK_ADDR2BASE(run);
	size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT;
	arena_chunk_map_t *mapelm = &chunk->map[pageind-map_bias];

	assert(arena_run_tree_search(&bin->runs, mapelm) == NULL);

	arena_run_tree_insert(&bin->runs, mapelm);
}

static void
arena_bin_runs_remove(arena_bin_t *bin, arena_run_t *run)
{
	arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
	size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT;
	arena_chunk_map_t *mapelm = &chunk->map[pageind-map_bias];

	assert(arena_run_tree_search(&bin->runs, mapelm) != NULL);

	arena_run_tree_remove(&bin->runs, mapelm);
}

static arena_run_t *
arena_bin_nonfull_run_tryget(arena_bin_t *bin)
{
	arena_run_t *run = arena_bin_runs_first(bin);
	if (run != NULL) {
		arena_bin_runs_remove(bin, run);
		if (config_stats)
			bin->stats.reruns++;
	}
	return (run);
}

static arena_run_t *
arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
{
	arena_run_t *run;
	size_t binind;
	arena_bin_info_t *bin_info;

	/* Look for a usable run. */
	run = arena_bin_nonfull_run_tryget(bin);
	if (run != NULL)
		return (run);
	/* No existing runs have any space available. */

	binind = arena_bin_index(arena, bin);
	bin_info = &arena_bin_info[binind];

	/* Allocate a new run. */
	malloc_mutex_unlock(&bin->lock);
	/******************************/
	malloc_mutex_lock(&arena->lock);
	run = arena_run_alloc(arena, bin_info->run_size, false, false);
	if (run != NULL) {
		bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run +
		    (uintptr_t)bin_info->bitmap_offset);

		/* Initialize run internals. */
		run->bin = bin;
		run->nextind = 0;
		run->nfree = bin_info->nregs;
		bitmap_init(bitmap, &bin_info->bitmap_info);
	}
	malloc_mutex_unlock(&arena->lock);
	/********************************/
	malloc_mutex_lock(&bin->lock);
	if (run != NULL) {
		if (config_stats) {
			bin->stats.nruns++;
			bin->stats.curruns++;
		}
		return (run);
	}

	/*
	 * arena_run_alloc() failed, but another thread may have made
	 * sufficient memory available while this one dropped bin->lock above,
	 * so search one more time.
	 */
	run = arena_bin_nonfull_run_tryget(bin);
	if (run != NULL)
		return (run);

	return (NULL);
}

/* Re-fill bin->runcur, then call arena_run_reg_alloc(). */
static void *
arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
{
	void *ret;
	size_t binind;
	arena_bin_info_t *bin_info;
	arena_run_t *run;

	binind = arena_bin_index(arena, bin);
	bin_info = &arena_bin_info[binind];
	bin->runcur = NULL;
	run = arena_bin_nonfull_run_get(arena, bin);
	if (bin->runcur != NULL && bin->runcur->nfree > 0) {
		/*
		 * Another thread updated runcur while this one ran without the
		 * bin lock in arena_bin_nonfull_run_get().
		 */
		assert(bin->runcur->nfree > 0);
		ret = arena_run_reg_alloc(bin->runcur, bin_info);
		if (run != NULL) {
			arena_chunk_t *chunk;

			/*
			 * arena_run_alloc() may have allocated run, or it may
			 * have pulled run from the bin's run tree.  Therefore
			 * it is unsafe to make any assumptions about how run
			 * has previously been used, and arena_bin_lower_run()
			 * must be called, as if a region were just deallocated
			 * from the run.
			 */
			chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
			if (run->nfree == bin_info->nregs)
				arena_dalloc_bin_run(arena, chunk, run, bin);
			else
				arena_bin_lower_run(arena, chunk, run, bin);
		}
		return (ret);
	}

	if (run == NULL)
		return (NULL);

	bin->runcur = run;

	assert(bin->runcur->nfree > 0);

	return (arena_run_reg_alloc(bin->runcur, bin_info));
}

void
arena_prof_accum(arena_t *arena, uint64_t accumbytes)
{

	if (prof_interval != 0) {
		arena->prof_accumbytes += accumbytes;
		if (arena->prof_accumbytes >= prof_interval) {
			prof_idump();
			arena->prof_accumbytes -= prof_interval;
		}
	}
}

void
arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin, size_t binind,
    uint64_t prof_accumbytes)
{
	unsigned i, nfill;
	arena_bin_t *bin;
	arena_run_t *run;
	void *ptr;

	assert(tbin->ncached == 0);

	if (config_prof) {
		malloc_mutex_lock(&arena->lock);
		arena_prof_accum(arena, prof_accumbytes);
		malloc_mutex_unlock(&arena->lock);
	}
	bin = &arena->bins[binind];
	malloc_mutex_lock(&bin->lock);
	for (i = 0, nfill = (tcache_bin_info[binind].ncached_max >>
	    tbin->lg_fill_div); i < nfill; i++) {
		if ((run = bin->runcur) != NULL && run->nfree > 0)
			ptr = arena_run_reg_alloc(run, &arena_bin_info[binind]);
		else
			ptr = arena_bin_malloc_hard(arena, bin);
		if (ptr == NULL)
			break;
		/* Insert such that low regions get used first. */
		tbin->avail[nfill - 1 - i] = ptr;
	}
	if (config_stats) {
		bin->stats.allocated += i * arena_bin_info[binind].reg_size;
		bin->stats.nmalloc += i;
		bin->stats.nrequests += tbin->tstats.nrequests;
		bin->stats.nfills++;
		tbin->tstats.nrequests = 0;
	}
	malloc_mutex_unlock(&bin->lock);
	tbin->ncached = i;
}

void *
arena_malloc_small(arena_t *arena, size_t size, bool zero)
{
	void *ret;
	arena_bin_t *bin;
	arena_run_t *run;
	size_t binind;

	binind = SMALL_SIZE2BIN(size);
	assert(binind < NBINS);
	bin = &arena->bins[binind];
	size = arena_bin_info[binind].reg_size;

	malloc_mutex_lock(&bin->lock);
	if ((run = bin->runcur) != NULL && run->nfree > 0)
		ret = arena_run_reg_alloc(run, &arena_bin_info[binind]);
	else
		ret = arena_bin_malloc_hard(arena, bin);

	if (ret == NULL) {
		malloc_mutex_unlock(&bin->lock);
		return (NULL);
	}

	if (config_stats) {
		bin->stats.allocated += size;
		bin->stats.nmalloc++;
		bin->stats.nrequests++;
	}
	malloc_mutex_unlock(&bin->lock);
	if (config_prof && isthreaded == false) {
		malloc_mutex_lock(&arena->lock);
		arena_prof_accum(arena, size);
		malloc_mutex_unlock(&arena->lock);
	}

	if (zero == false) {
		if (config_fill) {
			if (opt_junk)
				memset(ret, 0xa5, size);
			else if (opt_zero)
				memset(ret, 0, size);
		}
	} else
		memset(ret, 0, size);

	return (ret);
}

void *
arena_malloc_large(arena_t *arena, size_t size, bool zero)
{
	void *ret;

	/* Large allocation. */
	size = PAGE_CEILING(size);
	malloc_mutex_lock(&arena->lock);
	ret = (void *)arena_run_alloc(arena, size, true, zero);
	if (ret == NULL) {
		malloc_mutex_unlock(&arena->lock);
		return (NULL);
	}
	if (config_stats) {
		arena->stats.nmalloc_large++;
		arena->stats.nrequests_large++;
		arena->stats.allocated_large += size;
		arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nmalloc++;
		arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nrequests++;
		arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns++;
	}
	if (config_prof)
		arena_prof_accum(arena, size);
	malloc_mutex_unlock(&arena->lock);

	if (zero == false) {
		if (config_fill) {
			if (opt_junk)
				memset(ret, 0xa5, size);
			else if (opt_zero)
				memset(ret, 0, size);
		}
	}

	return (ret);
}

/* Only handles large allocations that require more than page alignment. */
void *
arena_palloc(arena_t *arena, size_t size, size_t alloc_size, size_t alignment,
    bool zero)
{
	void *ret;
	size_t offset;
	arena_chunk_t *chunk;

	assert((size & PAGE_MASK) == 0);

	alignment = PAGE_CEILING(alignment);

	malloc_mutex_lock(&arena->lock);
	ret = (void *)arena_run_alloc(arena, alloc_size, true, zero);
	if (ret == NULL) {
		malloc_mutex_unlock(&arena->lock);
		return (NULL);
	}

	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ret);

	offset = (uintptr_t)ret & (alignment - 1);
	assert((offset & PAGE_MASK) == 0);
	assert(offset < alloc_size);
	if (offset == 0)
		arena_run_trim_tail(arena, chunk, ret, alloc_size, size, false);
	else {
		size_t leadsize, trailsize;

		leadsize = alignment - offset;
		if (leadsize > 0) {
			arena_run_trim_head(arena, chunk, ret, alloc_size,
			    alloc_size - leadsize);
			ret = (void *)((uintptr_t)ret + leadsize);
		}

		trailsize = alloc_size - leadsize - size;
		if (trailsize != 0) {
			/* Trim trailing space. */
			assert(trailsize < alloc_size);
			arena_run_trim_tail(arena, chunk, ret, size + trailsize,
			    size, false);
		}
	}

	if (config_stats) {
		arena->stats.nmalloc_large++;
		arena->stats.nrequests_large++;
		arena->stats.allocated_large += size;
		arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nmalloc++;
		arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nrequests++;
		arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns++;
	}
	malloc_mutex_unlock(&arena->lock);

	if (config_fill && zero == false) {
		if (opt_junk)
			memset(ret, 0xa5, size);
		else if (opt_zero)
			memset(ret, 0, size);
	}
	return (ret);
}

/* Return the size of the allocation pointed to by ptr. */
size_t
arena_salloc(const void *ptr)
{
	size_t ret;
	arena_chunk_t *chunk;
	size_t pageind, mapbits;

	assert(ptr != NULL);
	assert(CHUNK_ADDR2BASE(ptr) != ptr);

	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
	pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT;
	mapbits = chunk->map[pageind-map_bias].bits;
	assert((mapbits & CHUNK_MAP_ALLOCATED) != 0);
	if ((mapbits & CHUNK_MAP_LARGE) == 0) {
		arena_run_t *run = (arena_run_t *)((uintptr_t)chunk +
		    (uintptr_t)((pageind - (mapbits >> PAGE_SHIFT)) <<
		    PAGE_SHIFT));
		size_t binind = arena_bin_index(chunk->arena, run->bin);
		arena_bin_info_t *bin_info = &arena_bin_info[binind];
		assert(((uintptr_t)ptr - ((uintptr_t)run +
		    (uintptr_t)bin_info->reg0_offset)) % bin_info->reg_size ==
		    0);
		ret = bin_info->reg_size;
	} else {
		assert(((uintptr_t)ptr & PAGE_MASK) == 0);
		ret = mapbits & ~PAGE_MASK;
		assert(ret != 0);
	}

	return (ret);
}

void
arena_prof_promoted(const void *ptr, size_t size)
{
	arena_chunk_t *chunk;
	size_t pageind, binind;

	assert(ptr != NULL);
	assert(CHUNK_ADDR2BASE(ptr) != ptr);
	assert(isalloc(ptr) == PAGE_SIZE);
	assert(size <= SMALL_MAXCLASS);

	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
	pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT;
	binind = SMALL_SIZE2BIN(size);
	assert(binind < NBINS);
	chunk->map[pageind-map_bias].bits = (chunk->map[pageind-map_bias].bits &
	    ~CHUNK_MAP_CLASS_MASK) | ((binind+1) << CHUNK_MAP_CLASS_SHIFT);
}

size_t
arena_salloc_demote(const void *ptr)
{
	size_t ret;
	arena_chunk_t *chunk;
	size_t pageind, mapbits;

	assert(ptr != NULL);
	assert(CHUNK_ADDR2BASE(ptr) != ptr);

	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
	pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT;
	mapbits = chunk->map[pageind-map_bias].bits;
	assert((mapbits & CHUNK_MAP_ALLOCATED) != 0);
	if ((mapbits & CHUNK_MAP_LARGE) == 0) {
		arena_run_t *run = (arena_run_t *)((uintptr_t)chunk +
		    (uintptr_t)((pageind - (mapbits >> PAGE_SHIFT)) <<
		    PAGE_SHIFT));
		size_t binind = arena_bin_index(chunk->arena, run->bin);
		arena_bin_info_t *bin_info = &arena_bin_info[binind];
		assert(((uintptr_t)ptr - ((uintptr_t)run +
		    (uintptr_t)bin_info->reg0_offset)) % bin_info->reg_size ==
		    0);
		ret = bin_info->reg_size;
	} else {
		assert(((uintptr_t)ptr & PAGE_MASK) == 0);
		ret = mapbits & ~PAGE_MASK;
		if (prof_promote && ret == PAGE_SIZE && (mapbits &
		    CHUNK_MAP_CLASS_MASK) != 0) {
			size_t binind = ((mapbits & CHUNK_MAP_CLASS_MASK) >>
			    CHUNK_MAP_CLASS_SHIFT) - 1;
			assert(binind < NBINS);
			ret = arena_bin_info[binind].reg_size;
		}
		assert(ret != 0);
	}

	return (ret);
}

static void
arena_dissociate_bin_run(arena_chunk_t *chunk, arena_run_t *run,
    arena_bin_t *bin)
{

	/* Dissociate run from bin. */
	if (run == bin->runcur)
		bin->runcur = NULL;
	else {
		size_t binind = arena_bin_index(chunk->arena, bin);
		arena_bin_info_t *bin_info = &arena_bin_info[binind];

		if (bin_info->nregs != 1) {
			/*
			 * This block's conditional is necessary because if the
			 * run only contains one region, then it never gets
			 * inserted into the non-full runs tree.
			 */
			arena_bin_runs_remove(bin, run);
		}
	}
}

static void
arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
    arena_bin_t *bin)
{
	size_t binind;
	arena_bin_info_t *bin_info;
	size_t npages, run_ind, past;

	assert(run != bin->runcur);
	assert(arena_run_tree_search(&bin->runs, &chunk->map[
	    (((uintptr_t)run-(uintptr_t)chunk)>>PAGE_SHIFT)-map_bias]) == NULL);

	binind = arena_bin_index(chunk->arena, run->bin);
	bin_info = &arena_bin_info[binind];

	malloc_mutex_unlock(&bin->lock);
	/******************************/
	npages = bin_info->run_size >> PAGE_SHIFT;
	run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT);
	past = (size_t)(PAGE_CEILING((uintptr_t)run +
	    (uintptr_t)bin_info->reg0_offset + (uintptr_t)(run->nextind *
	    bin_info->reg_size) - (uintptr_t)chunk) >> PAGE_SHIFT);
	malloc_mutex_lock(&arena->lock);

	/*
	 * If the run was originally clean, and some pages were never touched,
	 * trim the clean pages before deallocating the dirty portion of the
	 * run.
	 */
	if ((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY) == 0 && past
	    - run_ind < npages) {
		/*
		 * Trim clean pages.  Convert to large run beforehand.  Set the
		 * last map element first, in case this is a one-page run.
		 */
		chunk->map[run_ind+npages-1-map_bias].bits = CHUNK_MAP_LARGE |
		    (chunk->map[run_ind+npages-1-map_bias].bits &
		    CHUNK_MAP_FLAGS_MASK);
		chunk->map[run_ind-map_bias].bits = bin_info->run_size |
		    CHUNK_MAP_LARGE | (chunk->map[run_ind-map_bias].bits &
		    CHUNK_MAP_FLAGS_MASK);
		arena_run_trim_tail(arena, chunk, run, (npages << PAGE_SHIFT),
		    ((past - run_ind) << PAGE_SHIFT), false);
		/* npages = past - run_ind; */
	}
	arena_run_dalloc(arena, run, true);
	malloc_mutex_unlock(&arena->lock);
	/****************************/
	malloc_mutex_lock(&bin->lock);
	if (config_stats)
		bin->stats.curruns--;
}

static void
arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
    arena_bin_t *bin)
{

	/*
	 * Make sure that if bin->runcur is non-NULL, it refers to the lowest
	 * non-full run.  It is okay to NULL runcur out rather than proactively
	 * keeping it pointing at the lowest non-full run.
	 */
	if ((uintptr_t)run < (uintptr_t)bin->runcur) {
		/* Switch runcur. */
		if (bin->runcur->nfree > 0)
			arena_bin_runs_insert(bin, bin->runcur);
		bin->runcur = run;
		if (config_stats)
			bin->stats.reruns++;
	} else
		arena_bin_runs_insert(bin, run);
}

void
arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr,
    arena_chunk_map_t *mapelm)
{
	size_t pageind;
	arena_run_t *run;
	arena_bin_t *bin;
	size_t size;

	pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT;
	run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind -
	    (mapelm->bits >> PAGE_SHIFT)) << PAGE_SHIFT));
	bin = run->bin;
	size_t binind = arena_bin_index(arena, bin);
	arena_bin_info_t *bin_info = &arena_bin_info[binind];
	if (config_fill || config_stats)
		size = bin_info->reg_size;

	if (config_fill && opt_junk)
		memset(ptr, 0x5a, size);

	arena_run_reg_dalloc(run, ptr);
	if (run->nfree == bin_info->nregs) {
		arena_dissociate_bin_run(chunk, run, bin);
		arena_dalloc_bin_run(arena, chunk, run, bin);
	} else if (run->nfree == 1 && run != bin->runcur)
		arena_bin_lower_run(arena, chunk, run, bin);

	if (config_stats) {
		bin->stats.allocated -= size;
		bin->stats.ndalloc++;
	}
}

void
arena_stats_merge(arena_t *arena, size_t *nactive, size_t *ndirty,
    arena_stats_t *astats, malloc_bin_stats_t *bstats,
    malloc_large_stats_t *lstats)
{
	unsigned i;

	malloc_mutex_lock(&arena->lock);
	*nactive += arena->nactive;
	*ndirty += arena->ndirty;

	astats->mapped += arena->stats.mapped;
	astats->npurge += arena->stats.npurge;
	astats->nmadvise += arena->stats.nmadvise;
	astats->purged += arena->stats.purged;
	astats->allocated_large += arena->stats.allocated_large;
	astats->nmalloc_large += arena->stats.nmalloc_large;
	astats->ndalloc_large += arena->stats.ndalloc_large;
	astats->nrequests_large += arena->stats.nrequests_large;

	for (i = 0; i < nlclasses; i++) {
		lstats[i].nmalloc += arena->stats.lstats[i].nmalloc;
		lstats[i].ndalloc += arena->stats.lstats[i].ndalloc;
		lstats[i].nrequests += arena->stats.lstats[i].nrequests;
		lstats[i].curruns += arena->stats.lstats[i].curruns;
	}
	malloc_mutex_unlock(&arena->lock);

	for (i = 0; i < NBINS; i++) {
		arena_bin_t *bin = &arena->bins[i];

		malloc_mutex_lock(&bin->lock);
		bstats[i].allocated += bin->stats.allocated;
		bstats[i].nmalloc += bin->stats.nmalloc;
		bstats[i].ndalloc += bin->stats.ndalloc;
		bstats[i].nrequests += bin->stats.nrequests;
		if (config_tcache) {
			bstats[i].nfills += bin->stats.nfills;
			bstats[i].nflushes += bin->stats.nflushes;
		}
		bstats[i].nruns += bin->stats.nruns;
		bstats[i].reruns += bin->stats.reruns;
		bstats[i].curruns += bin->stats.curruns;
		malloc_mutex_unlock(&bin->lock);
	}
}

void
arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr)
{

	if (config_fill || config_stats) {
		size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >>
		    PAGE_SHIFT;
		size_t size = chunk->map[pageind-map_bias].bits & ~PAGE_MASK;

		if (config_fill && config_stats && opt_junk)
			memset(ptr, 0x5a, size);
		if (config_stats) {
			arena->stats.ndalloc_large++;
			arena->stats.allocated_large -= size;
			arena->stats.lstats[(size >> PAGE_SHIFT) - 1].ndalloc++;
			arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns--;
		}
	}

	arena_run_dalloc(arena, (arena_run_t *)ptr, true);
}

static void
arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr,
    size_t oldsize, size_t size)
{

	assert(size < oldsize);

	/*
	 * Shrink the run, and make trailing pages available for other
	 * allocations.
	 */
	malloc_mutex_lock(&arena->lock);
	arena_run_trim_tail(arena, chunk, (arena_run_t *)ptr, oldsize, size,
	    true);
	if (config_stats) {
		arena->stats.ndalloc_large++;
		arena->stats.allocated_large -= oldsize;
		arena->stats.lstats[(oldsize >> PAGE_SHIFT) - 1].ndalloc++;
		arena->stats.lstats[(oldsize >> PAGE_SHIFT) - 1].curruns--;

		arena->stats.nmalloc_large++;
		arena->stats.nrequests_large++;
		arena->stats.allocated_large += size;
		arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nmalloc++;
		arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nrequests++;
		arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns++;
	}
	malloc_mutex_unlock(&arena->lock);
}

static bool
arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr,
    size_t oldsize, size_t size, size_t extra, bool zero)
{
	size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT;
	size_t npages = oldsize >> PAGE_SHIFT;
	size_t followsize;

	assert(oldsize == (chunk->map[pageind-map_bias].bits & ~PAGE_MASK));

	/* Try to extend the run. */
	assert(size + extra > oldsize);
	malloc_mutex_lock(&arena->lock);
	if (pageind + npages < chunk_npages &&
	    (chunk->map[pageind+npages-map_bias].bits
	    & CHUNK_MAP_ALLOCATED) == 0 && (followsize =
	    chunk->map[pageind+npages-map_bias].bits & ~PAGE_MASK) >= size -
	    oldsize) {
		/*
		 * The next run is available and sufficiently large.  Split the
		 * following run, then merge the first part with the existing
		 * allocation.
		 */
		size_t flag_dirty;
		size_t splitsize = (oldsize + followsize <= size + extra)
		    ? followsize : size + extra - oldsize;
		arena_run_split(arena, (arena_run_t *)((uintptr_t)chunk +
		    ((pageind+npages) << PAGE_SHIFT)), splitsize, true, zero);

		size = oldsize + splitsize;
		npages = size >> PAGE_SHIFT;

		/*
		 * Mark the extended run as dirty if either portion of the run
		 * was dirty before allocation.  This is rather pedantic,
		 * because there's not actually any sequence of events that
		 * could cause the resulting run to be passed to
		 * arena_run_dalloc() with the dirty argument set to false
		 * (which is when dirty flag consistency would really matter).
		 */
		flag_dirty = (chunk->map[pageind-map_bias].bits &
		    CHUNK_MAP_DIRTY) |
		    (chunk->map[pageind+npages-1-map_bias].bits &
		    CHUNK_MAP_DIRTY);
		chunk->map[pageind-map_bias].bits = size | flag_dirty
		    | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED;
		chunk->map[pageind+npages-1-map_bias].bits = flag_dirty |
		    CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED;

		if (config_stats) {
			arena->stats.ndalloc_large++;
			arena->stats.allocated_large -= oldsize;
			arena->stats.lstats[(oldsize >> PAGE_SHIFT)
			    - 1].ndalloc++;
			arena->stats.lstats[(oldsize >> PAGE_SHIFT)
			    - 1].curruns--;

			arena->stats.nmalloc_large++;
			arena->stats.nrequests_large++;
			arena->stats.allocated_large += size;
			arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nmalloc++;
			arena->stats.lstats[(size >> PAGE_SHIFT)
			    - 1].nrequests++;
			arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns++;
		}
		malloc_mutex_unlock(&arena->lock);
		return (false);
	}
	malloc_mutex_unlock(&arena->lock);

	return (true);
}

/*
 * Try to resize a large allocation, in order to avoid copying.  This will
 * always fail if growing an object, and the following run is already in use.
 */
static bool
arena_ralloc_large(void *ptr, size_t oldsize, size_t size, size_t extra,
    bool zero)
{
	size_t psize;

	psize = PAGE_CEILING(size + extra);
	if (psize == oldsize) {
		/* Same size class. */
		if (config_fill && opt_junk && size < oldsize) {
			memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize -
			    size);
		}
		return (false);
	} else {
		arena_chunk_t *chunk;
		arena_t *arena;

		chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
		arena = chunk->arena;

		if (psize < oldsize) {
			/* Fill before shrinking in order avoid a race. */
			if (config_fill && opt_junk) {
				memset((void *)((uintptr_t)ptr + size), 0x5a,
				    oldsize - size);
			}
			arena_ralloc_large_shrink(arena, chunk, ptr, oldsize,
			    psize);
			return (false);
		} else {
			bool ret = arena_ralloc_large_grow(arena, chunk, ptr,
			    oldsize, PAGE_CEILING(size),
			    psize - PAGE_CEILING(size), zero);
			if (config_fill && ret == false && zero == false &&
			    opt_zero) {
				memset((void *)((uintptr_t)ptr + oldsize), 0,
				    size - oldsize);
			}
			return (ret);
		}
	}
}

void *
arena_ralloc_no_move(void *ptr, size_t oldsize, size_t size, size_t extra,
    bool zero)
{

	/*
	 * Avoid moving the allocation if the size class can be left the same.
	 */
	if (oldsize <= arena_maxclass) {
		if (oldsize <= SMALL_MAXCLASS) {
			assert(arena_bin_info[SMALL_SIZE2BIN(oldsize)].reg_size
			    == oldsize);
			if ((size + extra <= SMALL_MAXCLASS &&
			    SMALL_SIZE2BIN(size + extra) ==
			    SMALL_SIZE2BIN(oldsize)) || (size <= oldsize &&
			    size + extra >= oldsize)) {
				if (config_fill && opt_junk && size < oldsize) {
					memset((void *)((uintptr_t)ptr + size),
					    0x5a, oldsize - size);
				}
				return (ptr);
			}
		} else {
			assert(size <= arena_maxclass);
			if (size + extra > SMALL_MAXCLASS) {
				if (arena_ralloc_large(ptr, oldsize, size,
				    extra, zero) == false)
					return (ptr);
			}
		}
	}

	/* Reallocation would require a move. */
	return (NULL);
}

void *
arena_ralloc(void *ptr, size_t oldsize, size_t size, size_t extra,
    size_t alignment, bool zero)
{
	void *ret;
	size_t copysize;

	/* Try to avoid moving the allocation. */
	ret = arena_ralloc_no_move(ptr, oldsize, size, extra, zero);
	if (ret != NULL)
		return (ret);

	/*
	 * size and oldsize are different enough that we need to move the
	 * object.  In that case, fall back to allocating new space and
	 * copying.
	 */
	if (alignment != 0) {
		size_t usize = sa2u(size + extra, alignment, NULL);
		if (usize == 0)
			return (NULL);
		ret = ipalloc(usize, alignment, zero);
	} else
		ret = arena_malloc(size + extra, zero);

	if (ret == NULL) {
		if (extra == 0)
			return (NULL);
		/* Try again, this time without extra. */
		if (alignment != 0) {
			size_t usize = sa2u(size, alignment, NULL);
			if (usize == 0)
				return (NULL);
			ret = ipalloc(usize, alignment, zero);
		} else
			ret = arena_malloc(size, zero);

		if (ret == NULL)
			return (NULL);
	}

	/* Junk/zero-filling were already done by ipalloc()/arena_malloc(). */

	/*
	 * Copy at most size bytes (not size+extra), since the caller has no
	 * expectation that the extra bytes will be reliably preserved.
	 */
	copysize = (size < oldsize) ? size : oldsize;
	memcpy(ret, ptr, copysize);
	idalloc(ptr);
	return (ret);
}

bool
arena_new(arena_t *arena, unsigned ind)
{
	unsigned i;
	arena_bin_t *bin;

	arena->ind = ind;
	arena->nthreads = 0;

	if (malloc_mutex_init(&arena->lock))
		return (true);

	if (config_stats) {
		memset(&arena->stats, 0, sizeof(arena_stats_t));
		arena->stats.lstats =
		    (malloc_large_stats_t *)base_alloc(nlclasses *
		    sizeof(malloc_large_stats_t));
		if (arena->stats.lstats == NULL)
			return (true);
		memset(arena->stats.lstats, 0, nlclasses *
		    sizeof(malloc_large_stats_t));
		if (config_tcache)
			ql_new(&arena->tcache_ql);
	}

	if (config_prof)
		arena->prof_accumbytes = 0;

	/* Initialize chunks. */
	ql_new(&arena->chunks_dirty);
	arena->spare = NULL;

	arena->nactive = 0;
	arena->ndirty = 0;
	arena->npurgatory = 0;

	arena_avail_tree_new(&arena->runs_avail_clean);
	arena_avail_tree_new(&arena->runs_avail_dirty);

	/* Initialize bins. */
	for (i = 0; i < NBINS; i++) {
		bin = &arena->bins[i];
		if (malloc_mutex_init(&bin->lock))
			return (true);
		bin->runcur = NULL;
		arena_run_tree_new(&bin->runs);
		if (config_stats)
			memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
	}

	return (false);
}

/*
 * Calculate bin_info->run_size such that it meets the following constraints:
 *
 *   *) bin_info->run_size >= min_run_size
 *   *) bin_info->run_size <= arena_maxclass
 *   *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed).
 *   *) bin_info->nregs <= RUN_MAXREGS
 *
 * bin_info->nregs, bin_info->bitmap_offset, and bin_info->reg0_offset are also
 * calculated here, since these settings are all interdependent.
 */
static size_t
bin_info_run_size_calc(arena_bin_info_t *bin_info, size_t min_run_size)
{
	size_t try_run_size, good_run_size;
	uint32_t try_nregs, good_nregs;
	uint32_t try_hdr_size, good_hdr_size;
	uint32_t try_bitmap_offset, good_bitmap_offset;
	uint32_t try_ctx0_offset, good_ctx0_offset;
	uint32_t try_reg0_offset, good_reg0_offset;

	assert(min_run_size >= PAGE_SIZE);
	assert(min_run_size <= arena_maxclass);

	/*
	 * Calculate known-valid settings before entering the run_size
	 * expansion loop, so that the first part of the loop always copies
	 * valid settings.
	 *
	 * The do..while loop iteratively reduces the number of regions until
	 * the run header and the regions no longer overlap.  A closed formula
	 * would be quite messy, since there is an interdependency between the
	 * header's mask length and the number of regions.
	 */
	try_run_size = min_run_size;
	try_nregs = ((try_run_size - sizeof(arena_run_t)) / bin_info->reg_size)
	    + 1; /* Counter-act try_nregs-- in loop. */
	if (try_nregs > RUN_MAXREGS) {
		try_nregs = RUN_MAXREGS
		    + 1; /* Counter-act try_nregs-- in loop. */
	}
	do {
		try_nregs--;
		try_hdr_size = sizeof(arena_run_t);
		/* Pad to a long boundary. */
		try_hdr_size = LONG_CEILING(try_hdr_size);
		try_bitmap_offset = try_hdr_size;
		/* Add space for bitmap. */
		try_hdr_size += bitmap_size(try_nregs);
		if (config_prof && opt_prof && prof_promote == false) {
			/* Pad to a quantum boundary. */
			try_hdr_size = QUANTUM_CEILING(try_hdr_size);
			try_ctx0_offset = try_hdr_size;
			/* Add space for one (prof_ctx_t *) per region. */
			try_hdr_size += try_nregs * sizeof(prof_ctx_t *);
		} else
			try_ctx0_offset = 0;
		try_reg0_offset = try_run_size - (try_nregs *
		    bin_info->reg_size);
	} while (try_hdr_size > try_reg0_offset);

	/* run_size expansion loop. */
	do {
		/*
		 * Copy valid settings before trying more aggressive settings.
		 */
		good_run_size = try_run_size;
		good_nregs = try_nregs;
		good_hdr_size = try_hdr_size;
		good_bitmap_offset = try_bitmap_offset;
		good_ctx0_offset = try_ctx0_offset;
		good_reg0_offset = try_reg0_offset;

		/* Try more aggressive settings. */
		try_run_size += PAGE_SIZE;
		try_nregs = ((try_run_size - sizeof(arena_run_t)) /
		    bin_info->reg_size)
		    + 1; /* Counter-act try_nregs-- in loop. */
		if (try_nregs > RUN_MAXREGS) {
			try_nregs = RUN_MAXREGS
			    + 1; /* Counter-act try_nregs-- in loop. */
		}
		do {
			try_nregs--;
			try_hdr_size = sizeof(arena_run_t);
			/* Pad to a long boundary. */
			try_hdr_size = LONG_CEILING(try_hdr_size);
			try_bitmap_offset = try_hdr_size;
			/* Add space for bitmap. */
			try_hdr_size += bitmap_size(try_nregs);
			if (config_prof && opt_prof && prof_promote == false) {
				/* Pad to a quantum boundary. */
				try_hdr_size = QUANTUM_CEILING(try_hdr_size);
				try_ctx0_offset = try_hdr_size;
				/*
				 * Add space for one (prof_ctx_t *) per region.
				 */
				try_hdr_size += try_nregs *
				    sizeof(prof_ctx_t *);
			}
			try_reg0_offset = try_run_size - (try_nregs *
			    bin_info->reg_size);
		} while (try_hdr_size > try_reg0_offset);
	} while (try_run_size <= arena_maxclass
	    && try_run_size <= arena_maxclass
	    && RUN_MAX_OVRHD * (bin_info->reg_size << 3) > RUN_MAX_OVRHD_RELAX
	    && (try_reg0_offset << RUN_BFP) > RUN_MAX_OVRHD * try_run_size
	    && try_nregs < RUN_MAXREGS);

	assert(good_hdr_size <= good_reg0_offset);

	/* Copy final settings. */
	bin_info->run_size = good_run_size;
	bin_info->nregs = good_nregs;
	bin_info->bitmap_offset = good_bitmap_offset;
	bin_info->ctx0_offset = good_ctx0_offset;
	bin_info->reg0_offset = good_reg0_offset;

	return (good_run_size);
}

static void
bin_info_init(void)
{
	arena_bin_info_t *bin_info;
	size_t prev_run_size = PAGE_SIZE;

#define	SIZE_CLASS(bin, delta, size)					\
	bin_info = &arena_bin_info[bin];				\
	bin_info->reg_size = size;					\
	prev_run_size = bin_info_run_size_calc(bin_info, prev_run_size);\
	bitmap_info_init(&bin_info->bitmap_info, bin_info->nregs);
	SIZE_CLASSES
#undef SIZE_CLASS
}

void
arena_boot(void)
{
	size_t header_size;
	unsigned i;

	/*
	 * Compute the header size such that it is large enough to contain the
	 * page map.  The page map is biased to omit entries for the header
	 * itself, so some iteration is necessary to compute the map bias.
	 *
	 * 1) Compute safe header_size and map_bias values that include enough
	 *    space for an unbiased page map.
	 * 2) Refine map_bias based on (1) to omit the header pages in the page
	 *    map.  The resulting map_bias may be one too small.
	 * 3) Refine map_bias based on (2).  The result will be >= the result
	 *    from (2), and will always be correct.
	 */
	map_bias = 0;
	for (i = 0; i < 3; i++) {
		header_size = offsetof(arena_chunk_t, map)
			+ (sizeof(arena_chunk_map_t) * (chunk_npages-map_bias));
		map_bias = (header_size >> PAGE_SHIFT) + ((header_size &
		    PAGE_MASK) != 0);
	}
	assert(map_bias > 0);

	arena_maxclass = chunksize - (map_bias << PAGE_SHIFT);

	bin_info_init();
}