Home | History | Annotate | Download | only in src
      1 #define	JEMALLOC_ARENA_C_
      2 #include "jemalloc/internal/jemalloc_internal.h"
      3 
      4 /******************************************************************************/
      5 /* Data. */
      6 
      7 ssize_t		opt_lg_dirty_mult = LG_DIRTY_MULT_DEFAULT;
      8 arena_bin_info_t	arena_bin_info[NBINS];
      9 
     10 JEMALLOC_ALIGNED(CACHELINE)
     11 const uint32_t	small_bin2size_tab[NBINS] = {
     12 #define	B2S_bin_yes(size) \
     13 	size,
     14 #define	B2S_bin_no(size)
     15 #define	SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup) \
     16 	B2S_bin_##bin((ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta))
     17 	SIZE_CLASSES
     18 #undef B2S_bin_yes
     19 #undef B2S_bin_no
     20 #undef SC
     21 };
     22 
     23 JEMALLOC_ALIGNED(CACHELINE)
     24 const uint8_t	small_size2bin_tab[] = {
     25 #define	S2B_3(i)	i,
     26 #define	S2B_4(i)	S2B_3(i) S2B_3(i)
     27 #define	S2B_5(i)	S2B_4(i) S2B_4(i)
     28 #define	S2B_6(i)	S2B_5(i) S2B_5(i)
     29 #define	S2B_7(i)	S2B_6(i) S2B_6(i)
     30 #define	S2B_8(i)	S2B_7(i) S2B_7(i)
     31 #define	S2B_9(i)	S2B_8(i) S2B_8(i)
     32 #define	S2B_no(i)
     33 #define	SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup) \
     34 	S2B_##lg_delta_lookup(index)
     35 	SIZE_CLASSES
     36 #undef S2B_3
     37 #undef S2B_4
     38 #undef S2B_5
     39 #undef S2B_6
     40 #undef S2B_7
     41 #undef S2B_8
     42 #undef S2B_9
     43 #undef S2B_no
     44 #undef SC
     45 };
     46 
     47 /******************************************************************************/
     48 /*
     49  * Function prototypes for static functions that are referenced prior to
     50  * definition.
     51  */
     52 
     53 static void	arena_purge(arena_t *arena, bool all);
     54 static void	arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty,
     55     bool cleaned);
     56 static void	arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk,
     57     arena_run_t *run, arena_bin_t *bin);
     58 static void	arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk,
     59     arena_run_t *run, arena_bin_t *bin);
     60 
     61 /******************************************************************************/
     62 
     63 JEMALLOC_INLINE_C size_t
     64 arena_mapelm_to_pageind(arena_chunk_map_t *mapelm)
     65 {
     66 	uintptr_t map_offset =
     67 	    CHUNK_ADDR2OFFSET(mapelm) - offsetof(arena_chunk_t, map);
     68 
     69 	return ((map_offset / sizeof(arena_chunk_map_t)) + map_bias);
     70 }
     71 
     72 JEMALLOC_INLINE_C size_t
     73 arena_mapelm_to_bits(arena_chunk_map_t *mapelm)
     74 {
     75 
     76 	return (mapelm->bits);
     77 }
     78 
     79 static inline int
     80 arena_run_comp(arena_chunk_map_t *a, arena_chunk_map_t *b)
     81 {
     82 	uintptr_t a_mapelm = (uintptr_t)a;
     83 	uintptr_t b_mapelm = (uintptr_t)b;
     84 
     85 	assert(a != NULL);
     86 	assert(b != NULL);
     87 
     88 	return ((a_mapelm > b_mapelm) - (a_mapelm < b_mapelm));
     89 }
     90 
     91 /* Generate red-black tree functions. */
     92 rb_gen(static UNUSED, arena_run_tree_, arena_run_tree_t, arena_chunk_map_t,
     93     u.rb_link, arena_run_comp)
     94 
     95 static inline int
     96 arena_avail_comp(arena_chunk_map_t *a, arena_chunk_map_t *b)
     97 {
     98 	int ret;
     99 	size_t a_size;
    100 	size_t b_size = arena_mapelm_to_bits(b) & ~PAGE_MASK;
    101 	uintptr_t a_mapelm = (uintptr_t)a;
    102 	uintptr_t b_mapelm = (uintptr_t)b;
    103 
    104         if (a_mapelm & CHUNK_MAP_KEY)
    105 		a_size = a_mapelm & ~PAGE_MASK;
    106         else
    107 		a_size = arena_mapelm_to_bits(a) & ~PAGE_MASK;
    108 
    109 	ret = (a_size > b_size) - (a_size < b_size);
    110 	if (ret == 0 && (!(a_mapelm & CHUNK_MAP_KEY)))
    111 		ret = (a_mapelm > b_mapelm) - (a_mapelm < b_mapelm);
    112 
    113 	return (ret);
    114 }
    115 
    116 /* Generate red-black tree functions. */
    117 rb_gen(static UNUSED, arena_avail_tree_, arena_avail_tree_t, arena_chunk_map_t,
    118     u.rb_link, arena_avail_comp)
    119 
    120 static inline int
    121 arena_chunk_dirty_comp(arena_chunk_t *a, arena_chunk_t *b)
    122 {
    123 
    124 	assert(a != NULL);
    125 	assert(b != NULL);
    126 
    127 	/*
    128 	 * Short-circuit for self comparison.  The following comparison code
    129 	 * would come to the same result, but at the cost of executing the slow
    130 	 * path.
    131 	 */
    132 	if (a == b)
    133 		return (0);
    134 
    135 	/*
    136 	 * Order such that chunks with higher fragmentation are "less than"
    137 	 * those with lower fragmentation -- purging order is from "least" to
    138 	 * "greatest".  Fragmentation is measured as:
    139 	 *
    140 	 *     mean current avail run size
    141 	 *   --------------------------------
    142 	 *   mean defragmented avail run size
    143 	 *
    144 	 *            navail
    145 	 *         -----------
    146 	 *         nruns_avail           nruns_avail-nruns_adjac
    147 	 * = ========================= = -----------------------
    148 	 *            navail                  nruns_avail
    149 	 *    -----------------------
    150 	 *    nruns_avail-nruns_adjac
    151 	 *
    152 	 * The following code multiplies away the denominator prior to
    153 	 * comparison, in order to avoid division.
    154 	 *
    155 	 */
    156 	{
    157 		size_t a_val = (a->nruns_avail - a->nruns_adjac) *
    158 		    b->nruns_avail;
    159 		size_t b_val = (b->nruns_avail - b->nruns_adjac) *
    160 		    a->nruns_avail;
    161 
    162 		if (a_val < b_val)
    163 			return (1);
    164 		if (a_val > b_val)
    165 			return (-1);
    166 	}
    167 	/*
    168 	 * Break ties by chunk address.  For fragmented chunks, report lower
    169 	 * addresses as "lower", so that fragmentation reduction happens first
    170 	 * at lower addresses.  However, use the opposite ordering for
    171 	 * unfragmented chunks, in order to increase the chances of
    172 	 * re-allocating dirty runs.
    173 	 */
    174 	{
    175 		uintptr_t a_chunk = (uintptr_t)a;
    176 		uintptr_t b_chunk = (uintptr_t)b;
    177 		int ret = ((a_chunk > b_chunk) - (a_chunk < b_chunk));
    178 		if (a->nruns_adjac == 0) {
    179 			assert(b->nruns_adjac == 0);
    180 			ret = -ret;
    181 		}
    182 		return (ret);
    183 	}
    184 }
    185 
    186 /* Generate red-black tree functions. */
    187 rb_gen(static UNUSED, arena_chunk_dirty_, arena_chunk_tree_t, arena_chunk_t,
    188     dirty_link, arena_chunk_dirty_comp)
    189 
    190 static inline bool
    191 arena_avail_adjac_pred(arena_chunk_t *chunk, size_t pageind)
    192 {
    193 	bool ret;
    194 
    195 	if (pageind-1 < map_bias)
    196 		ret = false;
    197 	else {
    198 		ret = (arena_mapbits_allocated_get(chunk, pageind-1) == 0);
    199 		assert(ret == false || arena_mapbits_dirty_get(chunk,
    200 		    pageind-1) != arena_mapbits_dirty_get(chunk, pageind));
    201 	}
    202 	return (ret);
    203 }
    204 
    205 static inline bool
    206 arena_avail_adjac_succ(arena_chunk_t *chunk, size_t pageind, size_t npages)
    207 {
    208 	bool ret;
    209 
    210 	if (pageind+npages == chunk_npages)
    211 		ret = false;
    212 	else {
    213 		assert(pageind+npages < chunk_npages);
    214 		ret = (arena_mapbits_allocated_get(chunk, pageind+npages) == 0);
    215 		assert(ret == false || arena_mapbits_dirty_get(chunk, pageind)
    216 		    != arena_mapbits_dirty_get(chunk, pageind+npages));
    217 	}
    218 	return (ret);
    219 }
    220 
    221 static inline bool
    222 arena_avail_adjac(arena_chunk_t *chunk, size_t pageind, size_t npages)
    223 {
    224 
    225 	return (arena_avail_adjac_pred(chunk, pageind) ||
    226 	    arena_avail_adjac_succ(chunk, pageind, npages));
    227 }
    228 
    229 static void
    230 arena_avail_insert(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
    231     size_t npages, bool maybe_adjac_pred, bool maybe_adjac_succ)
    232 {
    233 
    234 	assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
    235 	    LG_PAGE));
    236 
    237 	/*
    238 	 * chunks_dirty is keyed by nruns_{avail,adjac}, so the chunk must be
    239 	 * removed and reinserted even if the run to be inserted is clean.
    240 	 */
    241 	if (chunk->ndirty != 0)
    242 		arena_chunk_dirty_remove(&arena->chunks_dirty, chunk);
    243 
    244 	if (maybe_adjac_pred && arena_avail_adjac_pred(chunk, pageind))
    245 		chunk->nruns_adjac++;
    246 	if (maybe_adjac_succ && arena_avail_adjac_succ(chunk, pageind, npages))
    247 		chunk->nruns_adjac++;
    248 	chunk->nruns_avail++;
    249 	assert(chunk->nruns_avail > chunk->nruns_adjac);
    250 
    251 	if (arena_mapbits_dirty_get(chunk, pageind) != 0) {
    252 		arena->ndirty += npages;
    253 		chunk->ndirty += npages;
    254 	}
    255 	if (chunk->ndirty != 0)
    256 		arena_chunk_dirty_insert(&arena->chunks_dirty, chunk);
    257 
    258 	arena_avail_tree_insert(&arena->runs_avail, arena_mapp_get(chunk,
    259 	    pageind));
    260 }
    261 
    262 static void
    263 arena_avail_remove(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
    264     size_t npages, bool maybe_adjac_pred, bool maybe_adjac_succ)
    265 {
    266 
    267 	assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
    268 	    LG_PAGE));
    269 
    270 	/*
    271 	 * chunks_dirty is keyed by nruns_{avail,adjac}, so the chunk must be
    272 	 * removed and reinserted even if the run to be removed is clean.
    273 	 */
    274 	if (chunk->ndirty != 0)
    275 		arena_chunk_dirty_remove(&arena->chunks_dirty, chunk);
    276 
    277 	if (maybe_adjac_pred && arena_avail_adjac_pred(chunk, pageind))
    278 		chunk->nruns_adjac--;
    279 	if (maybe_adjac_succ && arena_avail_adjac_succ(chunk, pageind, npages))
    280 		chunk->nruns_adjac--;
    281 	chunk->nruns_avail--;
    282 	assert(chunk->nruns_avail > chunk->nruns_adjac || (chunk->nruns_avail
    283 	    == 0 && chunk->nruns_adjac == 0));
    284 
    285 	if (arena_mapbits_dirty_get(chunk, pageind) != 0) {
    286 		arena->ndirty -= npages;
    287 		chunk->ndirty -= npages;
    288 	}
    289 	if (chunk->ndirty != 0)
    290 		arena_chunk_dirty_insert(&arena->chunks_dirty, chunk);
    291 
    292 	arena_avail_tree_remove(&arena->runs_avail, arena_mapp_get(chunk,
    293 	    pageind));
    294 }
    295 
    296 static inline void *
    297 arena_run_reg_alloc(arena_run_t *run, arena_bin_info_t *bin_info)
    298 {
    299 	void *ret;
    300 	unsigned regind;
    301 	bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run +
    302 	    (uintptr_t)bin_info->bitmap_offset);
    303 
    304 	assert(run->nfree > 0);
    305 	assert(bitmap_full(bitmap, &bin_info->bitmap_info) == false);
    306 
    307 	regind = bitmap_sfu(bitmap, &bin_info->bitmap_info);
    308 	ret = (void *)((uintptr_t)run + (uintptr_t)bin_info->reg0_offset +
    309 	    (uintptr_t)(bin_info->reg_interval * regind));
    310 	run->nfree--;
    311 	if (regind == run->nextind)
    312 		run->nextind++;
    313 	assert(regind < run->nextind);
    314 	return (ret);
    315 }
    316 
    317 static inline void
    318 arena_run_reg_dalloc(arena_run_t *run, void *ptr)
    319 {
    320 	arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
    321 	size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
    322 	size_t mapbits = arena_mapbits_get(chunk, pageind);
    323 	size_t binind = arena_ptr_small_binind_get(ptr, mapbits);
    324 	arena_bin_info_t *bin_info = &arena_bin_info[binind];
    325 	unsigned regind = arena_run_regind(run, bin_info, ptr);
    326 	bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run +
    327 	    (uintptr_t)bin_info->bitmap_offset);
    328 
    329 	assert(run->nfree < bin_info->nregs);
    330 	/* Freeing an interior pointer can cause assertion failure. */
    331 	assert(((uintptr_t)ptr - ((uintptr_t)run +
    332 	    (uintptr_t)bin_info->reg0_offset)) %
    333 	    (uintptr_t)bin_info->reg_interval == 0);
    334 	assert((uintptr_t)ptr >= (uintptr_t)run +
    335 	    (uintptr_t)bin_info->reg0_offset);
    336 	/* Freeing an unallocated pointer can cause assertion failure. */
    337 	assert(bitmap_get(bitmap, &bin_info->bitmap_info, regind));
    338 
    339 	bitmap_unset(bitmap, &bin_info->bitmap_info, regind);
    340 	run->nfree++;
    341 }
    342 
    343 static inline void
    344 arena_run_zero(arena_chunk_t *chunk, size_t run_ind, size_t npages)
    345 {
    346 
    347 	JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk +
    348 	    (run_ind << LG_PAGE)), (npages << LG_PAGE));
    349 	memset((void *)((uintptr_t)chunk + (run_ind << LG_PAGE)), 0,
    350 	    (npages << LG_PAGE));
    351 }
    352 
    353 static inline void
    354 arena_run_page_mark_zeroed(arena_chunk_t *chunk, size_t run_ind)
    355 {
    356 
    357 	JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void *)((uintptr_t)chunk + (run_ind
    358 	    << LG_PAGE)), PAGE);
    359 }
    360 
    361 static inline void
    362 arena_run_page_validate_zeroed(arena_chunk_t *chunk, size_t run_ind)
    363 {
    364 	size_t i;
    365 	UNUSED size_t *p = (size_t *)((uintptr_t)chunk + (run_ind << LG_PAGE));
    366 
    367 	arena_run_page_mark_zeroed(chunk, run_ind);
    368 	for (i = 0; i < PAGE / sizeof(size_t); i++)
    369 		assert(p[i] == 0);
    370 }
    371 
    372 static void
    373 arena_cactive_update(arena_t *arena, size_t add_pages, size_t sub_pages)
    374 {
    375 
    376 	if (config_stats) {
    377 		ssize_t cactive_diff = CHUNK_CEILING((arena->nactive +
    378 		    add_pages) << LG_PAGE) - CHUNK_CEILING((arena->nactive -
    379 		    sub_pages) << LG_PAGE);
    380 		if (cactive_diff != 0)
    381 			stats_cactive_add(cactive_diff);
    382 	}
    383 }
    384 
    385 static void
    386 arena_run_split_remove(arena_t *arena, arena_chunk_t *chunk, size_t run_ind,
    387     size_t flag_dirty, size_t need_pages)
    388 {
    389 	size_t total_pages, rem_pages;
    390 
    391 	total_pages = arena_mapbits_unallocated_size_get(chunk, run_ind) >>
    392 	    LG_PAGE;
    393 	assert(arena_mapbits_dirty_get(chunk, run_ind+total_pages-1) ==
    394 	    flag_dirty);
    395 	assert(need_pages <= total_pages);
    396 	rem_pages = total_pages - need_pages;
    397 
    398 	arena_avail_remove(arena, chunk, run_ind, total_pages, true, true);
    399 	arena_cactive_update(arena, need_pages, 0);
    400 	arena->nactive += need_pages;
    401 
    402 	/* Keep track of trailing unused pages for later use. */
    403 	if (rem_pages > 0) {
    404 		if (flag_dirty != 0) {
    405 			arena_mapbits_unallocated_set(chunk,
    406 			    run_ind+need_pages, (rem_pages << LG_PAGE),
    407 			    flag_dirty);
    408 			arena_mapbits_unallocated_set(chunk,
    409 			    run_ind+total_pages-1, (rem_pages << LG_PAGE),
    410 			    flag_dirty);
    411 		} else {
    412 			arena_mapbits_unallocated_set(chunk, run_ind+need_pages,
    413 			    (rem_pages << LG_PAGE),
    414 			    arena_mapbits_unzeroed_get(chunk,
    415 			    run_ind+need_pages));
    416 			arena_mapbits_unallocated_set(chunk,
    417 			    run_ind+total_pages-1, (rem_pages << LG_PAGE),
    418 			    arena_mapbits_unzeroed_get(chunk,
    419 			    run_ind+total_pages-1));
    420 		}
    421 		arena_avail_insert(arena, chunk, run_ind+need_pages, rem_pages,
    422 		    false, true);
    423 	}
    424 }
    425 
    426 static void
    427 arena_run_split_large_helper(arena_t *arena, arena_run_t *run, size_t size,
    428     bool remove, bool zero)
    429 {
    430 	arena_chunk_t *chunk;
    431 	size_t flag_dirty, run_ind, need_pages, i;
    432 
    433 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
    434 	run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE);
    435 	flag_dirty = arena_mapbits_dirty_get(chunk, run_ind);
    436 	need_pages = (size >> LG_PAGE);
    437 	assert(need_pages > 0);
    438 
    439 	if (remove) {
    440 		arena_run_split_remove(arena, chunk, run_ind, flag_dirty,
    441 		    need_pages);
    442 	}
    443 
    444 	if (zero) {
    445 		if (flag_dirty == 0) {
    446 			/*
    447 			 * The run is clean, so some pages may be zeroed (i.e.
    448 			 * never before touched).
    449 			 */
    450 			for (i = 0; i < need_pages; i++) {
    451 				if (arena_mapbits_unzeroed_get(chunk, run_ind+i)
    452 				    != 0)
    453 					arena_run_zero(chunk, run_ind+i, 1);
    454 				else if (config_debug) {
    455 					arena_run_page_validate_zeroed(chunk,
    456 					    run_ind+i);
    457 				} else {
    458 					arena_run_page_mark_zeroed(chunk,
    459 					    run_ind+i);
    460 				}
    461 			}
    462 		} else {
    463 			/* The run is dirty, so all pages must be zeroed. */
    464 			arena_run_zero(chunk, run_ind, need_pages);
    465 		}
    466 	} else {
    467 		JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk +
    468 		    (run_ind << LG_PAGE)), (need_pages << LG_PAGE));
    469 	}
    470 
    471 	/*
    472 	 * Set the last element first, in case the run only contains one page
    473 	 * (i.e. both statements set the same element).
    474 	 */
    475 	arena_mapbits_large_set(chunk, run_ind+need_pages-1, 0, flag_dirty);
    476 	arena_mapbits_large_set(chunk, run_ind, size, flag_dirty);
    477 }
    478 
    479 static void
    480 arena_run_split_large(arena_t *arena, arena_run_t *run, size_t size, bool zero)
    481 {
    482 
    483 	arena_run_split_large_helper(arena, run, size, true, zero);
    484 }
    485 
    486 static void
    487 arena_run_init_large(arena_t *arena, arena_run_t *run, size_t size, bool zero)
    488 {
    489 
    490 	arena_run_split_large_helper(arena, run, size, false, zero);
    491 }
    492 
    493 static void
    494 arena_run_split_small(arena_t *arena, arena_run_t *run, size_t size,
    495     size_t binind)
    496 {
    497 	arena_chunk_t *chunk;
    498 	size_t flag_dirty, run_ind, need_pages, i;
    499 
    500 	assert(binind != BININD_INVALID);
    501 
    502 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
    503 	run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE);
    504 	flag_dirty = arena_mapbits_dirty_get(chunk, run_ind);
    505 	need_pages = (size >> LG_PAGE);
    506 	assert(need_pages > 0);
    507 
    508 	arena_run_split_remove(arena, chunk, run_ind, flag_dirty, need_pages);
    509 
    510 	/*
    511 	 * Propagate the dirty and unzeroed flags to the allocated small run,
    512 	 * so that arena_dalloc_bin_run() has the ability to conditionally trim
    513 	 * clean pages.
    514 	 */
    515 	arena_mapbits_small_set(chunk, run_ind, 0, binind, flag_dirty);
    516 	/*
    517 	 * The first page will always be dirtied during small run
    518 	 * initialization, so a validation failure here would not actually
    519 	 * cause an observable failure.
    520 	 */
    521 	if (config_debug && flag_dirty == 0 && arena_mapbits_unzeroed_get(chunk,
    522 	    run_ind) == 0)
    523 		arena_run_page_validate_zeroed(chunk, run_ind);
    524 	for (i = 1; i < need_pages - 1; i++) {
    525 		arena_mapbits_small_set(chunk, run_ind+i, i, binind, 0);
    526 		if (config_debug && flag_dirty == 0 &&
    527 		    arena_mapbits_unzeroed_get(chunk, run_ind+i) == 0)
    528 			arena_run_page_validate_zeroed(chunk, run_ind+i);
    529 	}
    530 	arena_mapbits_small_set(chunk, run_ind+need_pages-1, need_pages-1,
    531 	    binind, flag_dirty);
    532 	if (config_debug && flag_dirty == 0 && arena_mapbits_unzeroed_get(chunk,
    533 	    run_ind+need_pages-1) == 0)
    534 		arena_run_page_validate_zeroed(chunk, run_ind+need_pages-1);
    535 	JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk +
    536 	    (run_ind << LG_PAGE)), (need_pages << LG_PAGE));
    537 }
    538 
    539 static arena_chunk_t *
    540 arena_chunk_init_spare(arena_t *arena)
    541 {
    542 	arena_chunk_t *chunk;
    543 
    544 	assert(arena->spare != NULL);
    545 
    546 	chunk = arena->spare;
    547 	arena->spare = NULL;
    548 
    549 	assert(arena_mapbits_allocated_get(chunk, map_bias) == 0);
    550 	assert(arena_mapbits_allocated_get(chunk, chunk_npages-1) == 0);
    551 	assert(arena_mapbits_unallocated_size_get(chunk, map_bias) ==
    552 	    arena_maxclass);
    553 	assert(arena_mapbits_unallocated_size_get(chunk, chunk_npages-1) ==
    554 	    arena_maxclass);
    555 	assert(arena_mapbits_dirty_get(chunk, map_bias) ==
    556 	    arena_mapbits_dirty_get(chunk, chunk_npages-1));
    557 
    558 	return (chunk);
    559 }
    560 
    561 static arena_chunk_t *
    562 arena_chunk_alloc_internal(arena_t *arena, size_t size, size_t alignment,
    563     bool *zero)
    564 {
    565 	arena_chunk_t *chunk;
    566 	chunk_alloc_t *chunk_alloc;
    567 	chunk_dalloc_t *chunk_dalloc;
    568 
    569 	chunk_alloc = arena->chunk_alloc;
    570 	chunk_dalloc = arena->chunk_dalloc;
    571 	malloc_mutex_unlock(&arena->lock);
    572 	chunk = (arena_chunk_t *)chunk_alloc_arena(chunk_alloc, chunk_dalloc,
    573 	    arena->ind, size, alignment, zero);
    574 	malloc_mutex_lock(&arena->lock);
    575 	if (config_stats && chunk != NULL)
    576 		arena->stats.mapped += chunksize;
    577 
    578 	return (chunk);
    579 }
    580 
    581 void *
    582 arena_chunk_alloc_huge(arena_t *arena, size_t size, size_t alignment,
    583     bool *zero)
    584 {
    585 	void *ret;
    586 	chunk_alloc_t *chunk_alloc;
    587 	chunk_dalloc_t *chunk_dalloc;
    588 
    589 	malloc_mutex_lock(&arena->lock);
    590 	chunk_alloc = arena->chunk_alloc;
    591 	chunk_dalloc = arena->chunk_dalloc;
    592 	if (config_stats) {
    593 		/* Optimistically update stats prior to unlocking. */
    594 		arena->stats.mapped += size;
    595 		arena->stats.allocated_huge += size;
    596 		arena->stats.nmalloc_huge++;
    597 		arena->stats.nrequests_huge++;
    598 	}
    599 	arena->nactive += (size >> LG_PAGE);
    600 	malloc_mutex_unlock(&arena->lock);
    601 
    602 	ret = chunk_alloc_arena(chunk_alloc, chunk_dalloc, arena->ind,
    603 	    size, alignment, zero);
    604 	if (config_stats) {
    605 		if (ret != NULL)
    606 			stats_cactive_add(size);
    607 		else {
    608 			/* Revert optimistic stats updates. */
    609 			malloc_mutex_lock(&arena->lock);
    610 			arena->stats.mapped -= size;
    611 			arena->stats.allocated_huge -= size;
    612 			arena->stats.nmalloc_huge--;
    613 			malloc_mutex_unlock(&arena->lock);
    614 		}
    615 	}
    616 
    617 	return (ret);
    618 }
    619 
    620 static arena_chunk_t *
    621 arena_chunk_init_hard(arena_t *arena)
    622 {
    623 	arena_chunk_t *chunk;
    624 	bool zero;
    625 	size_t unzeroed, i;
    626 
    627 	assert(arena->spare == NULL);
    628 
    629 	zero = false;
    630 	chunk = arena_chunk_alloc_internal(arena, chunksize, chunksize, &zero);
    631 	if (chunk == NULL)
    632 		return (NULL);
    633 
    634 	chunk->arena = arena;
    635 
    636 	/*
    637 	 * Claim that no pages are in use, since the header is merely overhead.
    638 	 */
    639 	chunk->ndirty = 0;
    640 
    641 	chunk->nruns_avail = 0;
    642 	chunk->nruns_adjac = 0;
    643 
    644 	/*
    645 	 * Initialize the map to contain one maximal free untouched run.  Mark
    646 	 * the pages as zeroed iff chunk_alloc() returned a zeroed chunk.
    647 	 */
    648 	unzeroed = zero ? 0 : CHUNK_MAP_UNZEROED;
    649 	arena_mapbits_unallocated_set(chunk, map_bias, arena_maxclass,
    650 	    unzeroed);
    651 	/*
    652 	 * There is no need to initialize the internal page map entries unless
    653 	 * the chunk is not zeroed.
    654 	 */
    655 	if (zero == false) {
    656 		JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(
    657 		    (void *)arena_mapp_get(chunk, map_bias+1),
    658 		    (size_t)((uintptr_t) arena_mapp_get(chunk, chunk_npages-1) -
    659 		    (uintptr_t)arena_mapp_get(chunk, map_bias+1)));
    660 		for (i = map_bias+1; i < chunk_npages-1; i++)
    661 			arena_mapbits_unzeroed_set(chunk, i, unzeroed);
    662 	} else {
    663 		JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void *)arena_mapp_get(chunk,
    664 		    map_bias+1), (size_t)((uintptr_t) arena_mapp_get(chunk,
    665 		    chunk_npages-1) - (uintptr_t)arena_mapp_get(chunk,
    666 		    map_bias+1)));
    667 		if (config_debug) {
    668 			for (i = map_bias+1; i < chunk_npages-1; i++) {
    669 				assert(arena_mapbits_unzeroed_get(chunk, i) ==
    670 				    unzeroed);
    671 			}
    672 		}
    673 	}
    674 	arena_mapbits_unallocated_set(chunk, chunk_npages-1, arena_maxclass,
    675 	    unzeroed);
    676 
    677 	return (chunk);
    678 }
    679 
    680 static arena_chunk_t *
    681 arena_chunk_alloc(arena_t *arena)
    682 {
    683 	arena_chunk_t *chunk;
    684 
    685 	if (arena->spare != NULL)
    686 		chunk = arena_chunk_init_spare(arena);
    687 	else {
    688 		chunk = arena_chunk_init_hard(arena);
    689 		if (chunk == NULL)
    690 			return (NULL);
    691 	}
    692 
    693 	/* Insert the run into the runs_avail tree. */
    694 	arena_avail_insert(arena, chunk, map_bias, chunk_npages-map_bias,
    695 	    false, false);
    696 
    697 	return (chunk);
    698 }
    699 
    700 static void
    701 arena_chunk_dalloc_internal(arena_t *arena, arena_chunk_t *chunk)
    702 {
    703 	chunk_dalloc_t *chunk_dalloc;
    704 
    705 	chunk_dalloc = arena->chunk_dalloc;
    706 	malloc_mutex_unlock(&arena->lock);
    707 	chunk_dalloc((void *)chunk, chunksize, arena->ind);
    708 	malloc_mutex_lock(&arena->lock);
    709 	if (config_stats)
    710 		arena->stats.mapped -= chunksize;
    711 }
    712 
    713 void
    714 arena_chunk_dalloc_huge(arena_t *arena, void *chunk, size_t size)
    715 {
    716 	chunk_dalloc_t *chunk_dalloc;
    717 
    718 	malloc_mutex_lock(&arena->lock);
    719 	chunk_dalloc = arena->chunk_dalloc;
    720 	if (config_stats) {
    721 		arena->stats.mapped -= size;
    722 		arena->stats.allocated_huge -= size;
    723 		arena->stats.ndalloc_huge++;
    724 		stats_cactive_sub(size);
    725 	}
    726 	arena->nactive -= (size >> LG_PAGE);
    727 	malloc_mutex_unlock(&arena->lock);
    728 	chunk_dalloc(chunk, size, arena->ind);
    729 }
    730 
    731 static void
    732 arena_chunk_dalloc(arena_t *arena, arena_chunk_t *chunk)
    733 {
    734 	assert(arena_mapbits_allocated_get(chunk, map_bias) == 0);
    735 	assert(arena_mapbits_allocated_get(chunk, chunk_npages-1) == 0);
    736 	assert(arena_mapbits_unallocated_size_get(chunk, map_bias) ==
    737 	    arena_maxclass);
    738 	assert(arena_mapbits_unallocated_size_get(chunk, chunk_npages-1) ==
    739 	    arena_maxclass);
    740 	assert(arena_mapbits_dirty_get(chunk, map_bias) ==
    741 	    arena_mapbits_dirty_get(chunk, chunk_npages-1));
    742 
    743 	/*
    744 	 * Remove run from the runs_avail tree, so that the arena does not use
    745 	 * it.
    746 	 */
    747 	arena_avail_remove(arena, chunk, map_bias, chunk_npages-map_bias,
    748 	    false, false);
    749 
    750 	if (arena->spare != NULL) {
    751 		arena_chunk_t *spare = arena->spare;
    752 
    753 		arena->spare = chunk;
    754 		arena_chunk_dalloc_internal(arena, spare);
    755 	} else
    756 		arena->spare = chunk;
    757 }
    758 
    759 static arena_run_t *
    760 arena_run_alloc_large_helper(arena_t *arena, size_t size, bool zero)
    761 {
    762 	arena_run_t *run;
    763 	arena_chunk_map_t *mapelm;
    764 	arena_chunk_map_t *key;
    765 
    766 	key = (arena_chunk_map_t *)(size | CHUNK_MAP_KEY);
    767 	mapelm = arena_avail_tree_nsearch(&arena->runs_avail, key);
    768 	if (mapelm != NULL) {
    769 		arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm);
    770 		size_t pageind = arena_mapelm_to_pageind(mapelm);
    771 
    772 		run = (arena_run_t *)((uintptr_t)run_chunk + (pageind <<
    773 		    LG_PAGE));
    774 		arena_run_split_large(arena, run, size, zero);
    775 		return (run);
    776 	}
    777 
    778 	return (NULL);
    779 }
    780 
    781 static arena_run_t *
    782 arena_run_alloc_large(arena_t *arena, size_t size, bool zero)
    783 {
    784 	arena_chunk_t *chunk;
    785 	arena_run_t *run;
    786 
    787 	assert(size <= arena_maxclass);
    788 	assert((size & PAGE_MASK) == 0);
    789 
    790 	/* Search the arena's chunks for the lowest best fit. */
    791 	run = arena_run_alloc_large_helper(arena, size, zero);
    792 	if (run != NULL)
    793 		return (run);
    794 
    795 	/*
    796 	 * No usable runs.  Create a new chunk from which to allocate the run.
    797 	 */
    798 	chunk = arena_chunk_alloc(arena);
    799 	if (chunk != NULL) {
    800 		run = (arena_run_t *)((uintptr_t)chunk + (map_bias << LG_PAGE));
    801 		arena_run_split_large(arena, run, size, zero);
    802 		return (run);
    803 	}
    804 
    805 	/*
    806 	 * arena_chunk_alloc() failed, but another thread may have made
    807 	 * sufficient memory available while this one dropped arena->lock in
    808 	 * arena_chunk_alloc(), so search one more time.
    809 	 */
    810 	return (arena_run_alloc_large_helper(arena, size, zero));
    811 }
    812 
    813 static arena_run_t *
    814 arena_run_alloc_small_helper(arena_t *arena, size_t size, size_t binind)
    815 {
    816 	arena_run_t *run;
    817 	arena_chunk_map_t *mapelm;
    818 	arena_chunk_map_t *key;
    819 
    820 	key = (arena_chunk_map_t *)(size | CHUNK_MAP_KEY);
    821 	mapelm = arena_avail_tree_nsearch(&arena->runs_avail, key);
    822 	if (mapelm != NULL) {
    823 		arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm);
    824 		size_t pageind = arena_mapelm_to_pageind(mapelm);
    825 
    826 		run = (arena_run_t *)((uintptr_t)run_chunk + (pageind <<
    827 		    LG_PAGE));
    828 		arena_run_split_small(arena, run, size, binind);
    829 		return (run);
    830 	}
    831 
    832 	return (NULL);
    833 }
    834 
    835 static arena_run_t *
    836 arena_run_alloc_small(arena_t *arena, size_t size, size_t binind)
    837 {
    838 	arena_chunk_t *chunk;
    839 	arena_run_t *run;
    840 
    841 	assert(size <= arena_maxclass);
    842 	assert((size & PAGE_MASK) == 0);
    843 	assert(binind != BININD_INVALID);
    844 
    845 	/* Search the arena's chunks for the lowest best fit. */
    846 	run = arena_run_alloc_small_helper(arena, size, binind);
    847 	if (run != NULL)
    848 		return (run);
    849 
    850 	/*
    851 	 * No usable runs.  Create a new chunk from which to allocate the run.
    852 	 */
    853 	chunk = arena_chunk_alloc(arena);
    854 	if (chunk != NULL) {
    855 		run = (arena_run_t *)((uintptr_t)chunk + (map_bias << LG_PAGE));
    856 		arena_run_split_small(arena, run, size, binind);
    857 		return (run);
    858 	}
    859 
    860 	/*
    861 	 * arena_chunk_alloc() failed, but another thread may have made
    862 	 * sufficient memory available while this one dropped arena->lock in
    863 	 * arena_chunk_alloc(), so search one more time.
    864 	 */
    865 	return (arena_run_alloc_small_helper(arena, size, binind));
    866 }
    867 
    868 static inline void
    869 arena_maybe_purge(arena_t *arena)
    870 {
    871 #if !defined(ANDROID_ALWAYS_PURGE)
    872 	size_t npurgeable, threshold;
    873 
    874 	/* Don't purge if the option is disabled. */
    875 	if (opt_lg_dirty_mult < 0)
    876 		return;
    877 #endif
    878 	/* Don't purge if all dirty pages are already being purged. */
    879 	if (arena->ndirty <= arena->npurgatory)
    880 		return;
    881 #if !defined(ANDROID_ALWAYS_PURGE)
    882 	npurgeable = arena->ndirty - arena->npurgatory;
    883 	threshold = (arena->nactive >> opt_lg_dirty_mult);
    884 	/*
    885 	 * Don't purge unless the number of purgeable pages exceeds the
    886 	 * threshold.
    887 	 */
    888 	if (npurgeable <= threshold)
    889 		return;
    890 #endif
    891 
    892 	arena_purge(arena, false);
    893 }
    894 
    895 static arena_chunk_t *
    896 chunks_dirty_iter_cb(arena_chunk_tree_t *tree, arena_chunk_t *chunk, void *arg)
    897 {
    898        size_t *ndirty = (size_t *)arg;
    899 
    900        assert(chunk->ndirty != 0);
    901        *ndirty += chunk->ndirty;
    902        return (NULL);
    903 }
    904 
    905 static size_t
    906 arena_compute_npurgatory(arena_t *arena, bool all)
    907 {
    908 	size_t npurgatory, npurgeable;
    909 
    910 	/*
    911 	 * Compute the minimum number of pages that this thread should try to
    912 	 * purge.
    913 	 */
    914 	npurgeable = arena->ndirty - arena->npurgatory;
    915 
    916 	if (all == false) {
    917 		size_t threshold = (arena->nactive >> opt_lg_dirty_mult);
    918 
    919 		npurgatory = npurgeable - threshold;
    920 	} else
    921 		npurgatory = npurgeable;
    922 
    923 	return (npurgatory);
    924 }
    925 
    926 static void
    927 arena_chunk_stash_dirty(arena_t *arena, arena_chunk_t *chunk, bool all,
    928     arena_chunk_mapelms_t *mapelms)
    929 {
    930 	size_t pageind, npages;
    931 
    932 	/*
    933 	 * Temporarily allocate free dirty runs within chunk.  If all is false,
    934 	 * only operate on dirty runs that are fragments; otherwise operate on
    935 	 * all dirty runs.
    936 	 */
    937 	for (pageind = map_bias; pageind < chunk_npages; pageind += npages) {
    938 		arena_chunk_map_t *mapelm = arena_mapp_get(chunk, pageind);
    939 		if (arena_mapbits_allocated_get(chunk, pageind) == 0) {
    940 			size_t run_size =
    941 			    arena_mapbits_unallocated_size_get(chunk, pageind);
    942 
    943 			npages = run_size >> LG_PAGE;
    944 			assert(pageind + npages <= chunk_npages);
    945 			assert(arena_mapbits_dirty_get(chunk, pageind) ==
    946 			    arena_mapbits_dirty_get(chunk, pageind+npages-1));
    947 
    948 			if (arena_mapbits_dirty_get(chunk, pageind) != 0 &&
    949 			    (all || arena_avail_adjac(chunk, pageind,
    950 			    npages))) {
    951 				arena_run_t *run = (arena_run_t *)((uintptr_t)
    952 				    chunk + (uintptr_t)(pageind << LG_PAGE));
    953 
    954 				arena_run_split_large(arena, run, run_size,
    955 				    false);
    956 				/* Append to list for later processing. */
    957 				ql_elm_new(mapelm, u.ql_link);
    958 				ql_tail_insert(mapelms, mapelm, u.ql_link);
    959 			}
    960 		} else {
    961 			/* Skip run. */
    962 			if (arena_mapbits_large_get(chunk, pageind) != 0) {
    963 				npages = arena_mapbits_large_size_get(chunk,
    964 				    pageind) >> LG_PAGE;
    965 			} else {
    966 				size_t binind;
    967 				arena_bin_info_t *bin_info;
    968 				arena_run_t *run = (arena_run_t *)((uintptr_t)
    969 				    chunk + (uintptr_t)(pageind << LG_PAGE));
    970 
    971 				assert(arena_mapbits_small_runind_get(chunk,
    972 				    pageind) == 0);
    973 				binind = arena_bin_index(arena, run->bin);
    974 				bin_info = &arena_bin_info[binind];
    975 				npages = bin_info->run_size >> LG_PAGE;
    976 			}
    977 		}
    978 	}
    979 	assert(pageind == chunk_npages);
    980 	assert(chunk->ndirty == 0 || all == false);
    981 	assert(chunk->nruns_adjac == 0);
    982 }
    983 
    984 static size_t
    985 arena_chunk_purge_stashed(arena_t *arena, arena_chunk_t *chunk,
    986     arena_chunk_mapelms_t *mapelms)
    987 {
    988 	size_t npurged, pageind, npages, nmadvise;
    989 	arena_chunk_map_t *mapelm;
    990 
    991 	malloc_mutex_unlock(&arena->lock);
    992 	if (config_stats)
    993 		nmadvise = 0;
    994 	npurged = 0;
    995 	ql_foreach(mapelm, mapelms, u.ql_link) {
    996 		bool unzeroed;
    997 		size_t flag_unzeroed, i;
    998 
    999 		pageind = arena_mapelm_to_pageind(mapelm);
   1000 		npages = arena_mapbits_large_size_get(chunk, pageind) >>
   1001 		    LG_PAGE;
   1002 		assert(pageind + npages <= chunk_npages);
   1003 		unzeroed = pages_purge((void *)((uintptr_t)chunk + (pageind <<
   1004 		    LG_PAGE)), (npages << LG_PAGE));
   1005 		flag_unzeroed = unzeroed ? CHUNK_MAP_UNZEROED : 0;
   1006 		/*
   1007 		 * Set the unzeroed flag for all pages, now that pages_purge()
   1008 		 * has returned whether the pages were zeroed as a side effect
   1009 		 * of purging.  This chunk map modification is safe even though
   1010 		 * the arena mutex isn't currently owned by this thread,
   1011 		 * because the run is marked as allocated, thus protecting it
   1012 		 * from being modified by any other thread.  As long as these
   1013 		 * writes don't perturb the first and last elements'
   1014 		 * CHUNK_MAP_ALLOCATED bits, behavior is well defined.
   1015 		 */
   1016 		for (i = 0; i < npages; i++) {
   1017 			arena_mapbits_unzeroed_set(chunk, pageind+i,
   1018 			    flag_unzeroed);
   1019 		}
   1020 		npurged += npages;
   1021 		if (config_stats)
   1022 			nmadvise++;
   1023 	}
   1024 	malloc_mutex_lock(&arena->lock);
   1025 	if (config_stats)
   1026 		arena->stats.nmadvise += nmadvise;
   1027 
   1028 	return (npurged);
   1029 }
   1030 
   1031 static void
   1032 arena_chunk_unstash_purged(arena_t *arena, arena_chunk_t *chunk,
   1033     arena_chunk_mapelms_t *mapelms)
   1034 {
   1035 	arena_chunk_map_t *mapelm;
   1036 	size_t pageind;
   1037 
   1038 	/* Deallocate runs. */
   1039 	for (mapelm = ql_first(mapelms); mapelm != NULL;
   1040 	    mapelm = ql_first(mapelms)) {
   1041 		arena_run_t *run;
   1042 
   1043 		pageind = arena_mapelm_to_pageind(mapelm);
   1044 		run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)(pageind <<
   1045 		    LG_PAGE));
   1046 		ql_remove(mapelms, mapelm, u.ql_link);
   1047 		arena_run_dalloc(arena, run, false, true);
   1048 	}
   1049 }
   1050 
   1051 static inline size_t
   1052 arena_chunk_purge(arena_t *arena, arena_chunk_t *chunk, bool all)
   1053 {
   1054 	size_t npurged;
   1055 	arena_chunk_mapelms_t mapelms;
   1056 
   1057 	ql_new(&mapelms);
   1058 
   1059 	/*
   1060 	 * If chunk is the spare, temporarily re-allocate it, 1) so that its
   1061 	 * run is reinserted into runs_avail, and 2) so that it cannot be
   1062 	 * completely discarded by another thread while arena->lock is dropped
   1063 	 * by this thread.  Note that the arena_run_dalloc() call will
   1064 	 * implicitly deallocate the chunk, so no explicit action is required
   1065 	 * in this function to deallocate the chunk.
   1066 	 *
   1067 	 * Note that once a chunk contains dirty pages, it cannot again contain
   1068 	 * a single run unless 1) it is a dirty run, or 2) this function purges
   1069 	 * dirty pages and causes the transition to a single clean run.  Thus
   1070 	 * (chunk == arena->spare) is possible, but it is not possible for
   1071 	 * this function to be called on the spare unless it contains a dirty
   1072 	 * run.
   1073 	 */
   1074 	if (chunk == arena->spare) {
   1075 		assert(arena_mapbits_dirty_get(chunk, map_bias) != 0);
   1076 		assert(arena_mapbits_dirty_get(chunk, chunk_npages-1) != 0);
   1077 
   1078 		arena_chunk_alloc(arena);
   1079 	}
   1080 
   1081 	if (config_stats)
   1082 		arena->stats.purged += chunk->ndirty;
   1083 
   1084 	/*
   1085 	 * Operate on all dirty runs if there is no clean/dirty run
   1086 	 * fragmentation.
   1087 	 */
   1088 	if (chunk->nruns_adjac == 0)
   1089 		all = true;
   1090 
   1091 	arena_chunk_stash_dirty(arena, chunk, all, &mapelms);
   1092 	npurged = arena_chunk_purge_stashed(arena, chunk, &mapelms);
   1093 	arena_chunk_unstash_purged(arena, chunk, &mapelms);
   1094 
   1095 	return (npurged);
   1096 }
   1097 
   1098 static void
   1099 arena_purge(arena_t *arena, bool all)
   1100 {
   1101 	arena_chunk_t *chunk;
   1102 	size_t npurgatory;
   1103 	if (config_debug) {
   1104 		size_t ndirty = 0;
   1105 
   1106 		arena_chunk_dirty_iter(&arena->chunks_dirty, NULL,
   1107 		    chunks_dirty_iter_cb, (void *)&ndirty);
   1108 		assert(ndirty == arena->ndirty);
   1109 	}
   1110 	assert(arena->ndirty > arena->npurgatory || all);
   1111 	assert((arena->nactive >> opt_lg_dirty_mult) < (arena->ndirty -
   1112 	    arena->npurgatory) || all);
   1113 
   1114 	if (config_stats)
   1115 		arena->stats.npurge++;
   1116 
   1117 	/*
   1118 	 * Add the minimum number of pages this thread should try to purge to
   1119 	 * arena->npurgatory.  This will keep multiple threads from racing to
   1120 	 * reduce ndirty below the threshold.
   1121 	 */
   1122 	npurgatory = arena_compute_npurgatory(arena, all);
   1123 	arena->npurgatory += npurgatory;
   1124 
   1125 	while (npurgatory > 0) {
   1126 		size_t npurgeable, npurged, nunpurged;
   1127 
   1128 		/* Get next chunk with dirty pages. */
   1129 		chunk = arena_chunk_dirty_first(&arena->chunks_dirty);
   1130 		if (chunk == NULL) {
   1131 			/*
   1132 			 * This thread was unable to purge as many pages as
   1133 			 * originally intended, due to races with other threads
   1134 			 * that either did some of the purging work, or re-used
   1135 			 * dirty pages.
   1136 			 */
   1137 			arena->npurgatory -= npurgatory;
   1138 			return;
   1139 		}
   1140 		npurgeable = chunk->ndirty;
   1141 		assert(npurgeable != 0);
   1142 
   1143 		if (npurgeable > npurgatory && chunk->nruns_adjac == 0) {
   1144 			/*
   1145 			 * This thread will purge all the dirty pages in chunk,
   1146 			 * so set npurgatory to reflect this thread's intent to
   1147 			 * purge the pages.  This tends to reduce the chances
   1148 			 * of the following scenario:
   1149 			 *
   1150 			 * 1) This thread sets arena->npurgatory such that
   1151 			 *    (arena->ndirty - arena->npurgatory) is at the
   1152 			 *    threshold.
   1153 			 * 2) This thread drops arena->lock.
   1154 			 * 3) Another thread causes one or more pages to be
   1155 			 *    dirtied, and immediately determines that it must
   1156 			 *    purge dirty pages.
   1157 			 *
   1158 			 * If this scenario *does* play out, that's okay,
   1159 			 * because all of the purging work being done really
   1160 			 * needs to happen.
   1161 			 */
   1162 			arena->npurgatory += npurgeable - npurgatory;
   1163 			npurgatory = npurgeable;
   1164 		}
   1165 
   1166 		/*
   1167 		 * Keep track of how many pages are purgeable, versus how many
   1168 		 * actually get purged, and adjust counters accordingly.
   1169 		 */
   1170 		arena->npurgatory -= npurgeable;
   1171 		npurgatory -= npurgeable;
   1172 		npurged = arena_chunk_purge(arena, chunk, all);
   1173 		nunpurged = npurgeable - npurged;
   1174 		arena->npurgatory += nunpurged;
   1175 		npurgatory += nunpurged;
   1176 	}
   1177 }
   1178 
   1179 void
   1180 arena_purge_all(arena_t *arena)
   1181 {
   1182 
   1183 	malloc_mutex_lock(&arena->lock);
   1184 	arena_purge(arena, true);
   1185 	malloc_mutex_unlock(&arena->lock);
   1186 }
   1187 
   1188 static void
   1189 arena_run_coalesce(arena_t *arena, arena_chunk_t *chunk, size_t *p_size,
   1190     size_t *p_run_ind, size_t *p_run_pages, size_t flag_dirty)
   1191 {
   1192 	size_t size = *p_size;
   1193 	size_t run_ind = *p_run_ind;
   1194 	size_t run_pages = *p_run_pages;
   1195 
   1196 	/* Try to coalesce forward. */
   1197 	if (run_ind + run_pages < chunk_npages &&
   1198 	    arena_mapbits_allocated_get(chunk, run_ind+run_pages) == 0 &&
   1199 	    arena_mapbits_dirty_get(chunk, run_ind+run_pages) == flag_dirty) {
   1200 		size_t nrun_size = arena_mapbits_unallocated_size_get(chunk,
   1201 		    run_ind+run_pages);
   1202 		size_t nrun_pages = nrun_size >> LG_PAGE;
   1203 
   1204 		/*
   1205 		 * Remove successor from runs_avail; the coalesced run is
   1206 		 * inserted later.
   1207 		 */
   1208 		assert(arena_mapbits_unallocated_size_get(chunk,
   1209 		    run_ind+run_pages+nrun_pages-1) == nrun_size);
   1210 		assert(arena_mapbits_dirty_get(chunk,
   1211 		    run_ind+run_pages+nrun_pages-1) == flag_dirty);
   1212 		arena_avail_remove(arena, chunk, run_ind+run_pages, nrun_pages,
   1213 		    false, true);
   1214 
   1215 		size += nrun_size;
   1216 		run_pages += nrun_pages;
   1217 
   1218 		arena_mapbits_unallocated_size_set(chunk, run_ind, size);
   1219 		arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1,
   1220 		    size);
   1221 	}
   1222 
   1223 	/* Try to coalesce backward. */
   1224 	if (run_ind > map_bias && arena_mapbits_allocated_get(chunk,
   1225 	    run_ind-1) == 0 && arena_mapbits_dirty_get(chunk, run_ind-1) ==
   1226 	    flag_dirty) {
   1227 		size_t prun_size = arena_mapbits_unallocated_size_get(chunk,
   1228 		    run_ind-1);
   1229 		size_t prun_pages = prun_size >> LG_PAGE;
   1230 
   1231 		run_ind -= prun_pages;
   1232 
   1233 		/*
   1234 		 * Remove predecessor from runs_avail; the coalesced run is
   1235 		 * inserted later.
   1236 		 */
   1237 		assert(arena_mapbits_unallocated_size_get(chunk, run_ind) ==
   1238 		    prun_size);
   1239 		assert(arena_mapbits_dirty_get(chunk, run_ind) == flag_dirty);
   1240 		arena_avail_remove(arena, chunk, run_ind, prun_pages, true,
   1241 		    false);
   1242 
   1243 		size += prun_size;
   1244 		run_pages += prun_pages;
   1245 
   1246 		arena_mapbits_unallocated_size_set(chunk, run_ind, size);
   1247 		arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1,
   1248 		    size);
   1249 	}
   1250 
   1251 	*p_size = size;
   1252 	*p_run_ind = run_ind;
   1253 	*p_run_pages = run_pages;
   1254 }
   1255 
   1256 static void
   1257 arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty, bool cleaned)
   1258 {
   1259 	arena_chunk_t *chunk;
   1260 	size_t size, run_ind, run_pages, flag_dirty;
   1261 
   1262 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
   1263 	run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE);
   1264 	assert(run_ind >= map_bias);
   1265 	assert(run_ind < chunk_npages);
   1266 	if (arena_mapbits_large_get(chunk, run_ind) != 0) {
   1267 		size = arena_mapbits_large_size_get(chunk, run_ind);
   1268 		assert(size == PAGE ||
   1269 		    arena_mapbits_large_size_get(chunk,
   1270 		    run_ind+(size>>LG_PAGE)-1) == 0);
   1271 	} else {
   1272 		size_t binind = arena_bin_index(arena, run->bin);
   1273 		arena_bin_info_t *bin_info = &arena_bin_info[binind];
   1274 		size = bin_info->run_size;
   1275 	}
   1276 	run_pages = (size >> LG_PAGE);
   1277 	arena_cactive_update(arena, 0, run_pages);
   1278 	arena->nactive -= run_pages;
   1279 
   1280 	/*
   1281 	 * The run is dirty if the caller claims to have dirtied it, as well as
   1282 	 * if it was already dirty before being allocated and the caller
   1283 	 * doesn't claim to have cleaned it.
   1284 	 */
   1285 	assert(arena_mapbits_dirty_get(chunk, run_ind) ==
   1286 	    arena_mapbits_dirty_get(chunk, run_ind+run_pages-1));
   1287 	if (cleaned == false && arena_mapbits_dirty_get(chunk, run_ind) != 0)
   1288 		dirty = true;
   1289 	flag_dirty = dirty ? CHUNK_MAP_DIRTY : 0;
   1290 
   1291 	/* Mark pages as unallocated in the chunk map. */
   1292 	if (dirty) {
   1293 		arena_mapbits_unallocated_set(chunk, run_ind, size,
   1294 		    CHUNK_MAP_DIRTY);
   1295 		arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size,
   1296 		    CHUNK_MAP_DIRTY);
   1297 	} else {
   1298 		arena_mapbits_unallocated_set(chunk, run_ind, size,
   1299 		    arena_mapbits_unzeroed_get(chunk, run_ind));
   1300 		arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size,
   1301 		    arena_mapbits_unzeroed_get(chunk, run_ind+run_pages-1));
   1302 	}
   1303 
   1304 	arena_run_coalesce(arena, chunk, &size, &run_ind, &run_pages,
   1305 	    flag_dirty);
   1306 
   1307 	/* Insert into runs_avail, now that coalescing is complete. */
   1308 	assert(arena_mapbits_unallocated_size_get(chunk, run_ind) ==
   1309 	    arena_mapbits_unallocated_size_get(chunk, run_ind+run_pages-1));
   1310 	assert(arena_mapbits_dirty_get(chunk, run_ind) ==
   1311 	    arena_mapbits_dirty_get(chunk, run_ind+run_pages-1));
   1312 	arena_avail_insert(arena, chunk, run_ind, run_pages, true, true);
   1313 
   1314 	/* Deallocate chunk if it is now completely unused. */
   1315 	if (size == arena_maxclass) {
   1316 		assert(run_ind == map_bias);
   1317 		assert(run_pages == (arena_maxclass >> LG_PAGE));
   1318 		arena_chunk_dalloc(arena, chunk);
   1319 	}
   1320 
   1321 	/*
   1322 	 * It is okay to do dirty page processing here even if the chunk was
   1323 	 * deallocated above, since in that case it is the spare.  Waiting
   1324 	 * until after possible chunk deallocation to do dirty processing
   1325 	 * allows for an old spare to be fully deallocated, thus decreasing the
   1326 	 * chances of spuriously crossing the dirty page purging threshold.
   1327 	 */
   1328 	if (dirty)
   1329 		arena_maybe_purge(arena);
   1330 }
   1331 
   1332 static void
   1333 arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
   1334     size_t oldsize, size_t newsize)
   1335 {
   1336 	size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE;
   1337 	size_t head_npages = (oldsize - newsize) >> LG_PAGE;
   1338 	size_t flag_dirty = arena_mapbits_dirty_get(chunk, pageind);
   1339 
   1340 	assert(oldsize > newsize);
   1341 
   1342 	/*
   1343 	 * Update the chunk map so that arena_run_dalloc() can treat the
   1344 	 * leading run as separately allocated.  Set the last element of each
   1345 	 * run first, in case of single-page runs.
   1346 	 */
   1347 	assert(arena_mapbits_large_size_get(chunk, pageind) == oldsize);
   1348 	arena_mapbits_large_set(chunk, pageind+head_npages-1, 0, flag_dirty);
   1349 	arena_mapbits_large_set(chunk, pageind, oldsize-newsize, flag_dirty);
   1350 
   1351 	if (config_debug) {
   1352 		UNUSED size_t tail_npages = newsize >> LG_PAGE;
   1353 		assert(arena_mapbits_large_size_get(chunk,
   1354 		    pageind+head_npages+tail_npages-1) == 0);
   1355 		assert(arena_mapbits_dirty_get(chunk,
   1356 		    pageind+head_npages+tail_npages-1) == flag_dirty);
   1357 	}
   1358 	arena_mapbits_large_set(chunk, pageind+head_npages, newsize,
   1359 	    flag_dirty);
   1360 
   1361 	arena_run_dalloc(arena, run, false, false);
   1362 }
   1363 
   1364 static void
   1365 arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
   1366     size_t oldsize, size_t newsize, bool dirty)
   1367 {
   1368 	size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE;
   1369 	size_t head_npages = newsize >> LG_PAGE;
   1370 	size_t flag_dirty = arena_mapbits_dirty_get(chunk, pageind);
   1371 
   1372 	assert(oldsize > newsize);
   1373 
   1374 	/*
   1375 	 * Update the chunk map so that arena_run_dalloc() can treat the
   1376 	 * trailing run as separately allocated.  Set the last element of each
   1377 	 * run first, in case of single-page runs.
   1378 	 */
   1379 	assert(arena_mapbits_large_size_get(chunk, pageind) == oldsize);
   1380 	arena_mapbits_large_set(chunk, pageind+head_npages-1, 0, flag_dirty);
   1381 	arena_mapbits_large_set(chunk, pageind, newsize, flag_dirty);
   1382 
   1383 	if (config_debug) {
   1384 		UNUSED size_t tail_npages = (oldsize - newsize) >> LG_PAGE;
   1385 		assert(arena_mapbits_large_size_get(chunk,
   1386 		    pageind+head_npages+tail_npages-1) == 0);
   1387 		assert(arena_mapbits_dirty_get(chunk,
   1388 		    pageind+head_npages+tail_npages-1) == flag_dirty);
   1389 	}
   1390 	arena_mapbits_large_set(chunk, pageind+head_npages, oldsize-newsize,
   1391 	    flag_dirty);
   1392 
   1393 	arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)run + newsize),
   1394 	    dirty, false);
   1395 }
   1396 
   1397 static arena_run_t *
   1398 arena_bin_runs_first(arena_bin_t *bin)
   1399 {
   1400 	arena_chunk_map_t *mapelm = arena_run_tree_first(&bin->runs);
   1401 	if (mapelm != NULL) {
   1402 		arena_chunk_t *chunk;
   1403 		size_t pageind;
   1404 		arena_run_t *run;
   1405 
   1406 		chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(mapelm);
   1407 		pageind = arena_mapelm_to_pageind(mapelm);
   1408 		run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind -
   1409 		    arena_mapbits_small_runind_get(chunk, pageind)) <<
   1410 		    LG_PAGE));
   1411 		return (run);
   1412 	}
   1413 
   1414 	return (NULL);
   1415 }
   1416 
   1417 static void
   1418 arena_bin_runs_insert(arena_bin_t *bin, arena_run_t *run)
   1419 {
   1420 	arena_chunk_t *chunk = CHUNK_ADDR2BASE(run);
   1421 	size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE;
   1422 	arena_chunk_map_t *mapelm = arena_mapp_get(chunk, pageind);
   1423 
   1424 	assert(arena_run_tree_search(&bin->runs, mapelm) == NULL);
   1425 
   1426 	arena_run_tree_insert(&bin->runs, mapelm);
   1427 }
   1428 
   1429 static void
   1430 arena_bin_runs_remove(arena_bin_t *bin, arena_run_t *run)
   1431 {
   1432 	arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
   1433 	size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE;
   1434 	arena_chunk_map_t *mapelm = arena_mapp_get(chunk, pageind);
   1435 
   1436 	assert(arena_run_tree_search(&bin->runs, mapelm) != NULL);
   1437 
   1438 	arena_run_tree_remove(&bin->runs, mapelm);
   1439 }
   1440 
   1441 static arena_run_t *
   1442 arena_bin_nonfull_run_tryget(arena_bin_t *bin)
   1443 {
   1444 	arena_run_t *run = arena_bin_runs_first(bin);
   1445 	if (run != NULL) {
   1446 		arena_bin_runs_remove(bin, run);
   1447 		if (config_stats)
   1448 			bin->stats.reruns++;
   1449 	}
   1450 	return (run);
   1451 }
   1452 
   1453 static arena_run_t *
   1454 arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
   1455 {
   1456 	arena_run_t *run;
   1457 	size_t binind;
   1458 	arena_bin_info_t *bin_info;
   1459 
   1460 	/* Look for a usable run. */
   1461 	run = arena_bin_nonfull_run_tryget(bin);
   1462 	if (run != NULL)
   1463 		return (run);
   1464 	/* No existing runs have any space available. */
   1465 
   1466 	binind = arena_bin_index(arena, bin);
   1467 	bin_info = &arena_bin_info[binind];
   1468 
   1469 	/* Allocate a new run. */
   1470 	malloc_mutex_unlock(&bin->lock);
   1471 	/******************************/
   1472 	malloc_mutex_lock(&arena->lock);
   1473 	run = arena_run_alloc_small(arena, bin_info->run_size, binind);
   1474 	if (run != NULL) {
   1475 		bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run +
   1476 		    (uintptr_t)bin_info->bitmap_offset);
   1477 
   1478 		/* Initialize run internals. */
   1479 		run->bin = bin;
   1480 		run->nextind = 0;
   1481 		run->nfree = bin_info->nregs;
   1482 		bitmap_init(bitmap, &bin_info->bitmap_info);
   1483 	}
   1484 	malloc_mutex_unlock(&arena->lock);
   1485 	/********************************/
   1486 	malloc_mutex_lock(&bin->lock);
   1487 	if (run != NULL) {
   1488 		if (config_stats) {
   1489 			bin->stats.nruns++;
   1490 			bin->stats.curruns++;
   1491 		}
   1492 		return (run);
   1493 	}
   1494 
   1495 	/*
   1496 	 * arena_run_alloc_small() failed, but another thread may have made
   1497 	 * sufficient memory available while this one dropped bin->lock above,
   1498 	 * so search one more time.
   1499 	 */
   1500 	run = arena_bin_nonfull_run_tryget(bin);
   1501 	if (run != NULL)
   1502 		return (run);
   1503 
   1504 	return (NULL);
   1505 }
   1506 
   1507 /* Re-fill bin->runcur, then call arena_run_reg_alloc(). */
   1508 static void *
   1509 arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
   1510 {
   1511 	void *ret;
   1512 	size_t binind;
   1513 	arena_bin_info_t *bin_info;
   1514 	arena_run_t *run;
   1515 
   1516 	binind = arena_bin_index(arena, bin);
   1517 	bin_info = &arena_bin_info[binind];
   1518 	bin->runcur = NULL;
   1519 	run = arena_bin_nonfull_run_get(arena, bin);
   1520 	if (bin->runcur != NULL && bin->runcur->nfree > 0) {
   1521 		/*
   1522 		 * Another thread updated runcur while this one ran without the
   1523 		 * bin lock in arena_bin_nonfull_run_get().
   1524 		 */
   1525 		assert(bin->runcur->nfree > 0);
   1526 		ret = arena_run_reg_alloc(bin->runcur, bin_info);
   1527 		if (run != NULL) {
   1528 			arena_chunk_t *chunk;
   1529 
   1530 			/*
   1531 			 * arena_run_alloc_small() may have allocated run, or
   1532 			 * it may have pulled run from the bin's run tree.
   1533 			 * Therefore it is unsafe to make any assumptions about
   1534 			 * how run has previously been used, and
   1535 			 * arena_bin_lower_run() must be called, as if a region
   1536 			 * were just deallocated from the run.
   1537 			 */
   1538 			chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
   1539 			if (run->nfree == bin_info->nregs)
   1540 				arena_dalloc_bin_run(arena, chunk, run, bin);
   1541 			else
   1542 				arena_bin_lower_run(arena, chunk, run, bin);
   1543 		}
   1544 		return (ret);
   1545 	}
   1546 
   1547 	if (run == NULL)
   1548 		return (NULL);
   1549 
   1550 	bin->runcur = run;
   1551 
   1552 	assert(bin->runcur->nfree > 0);
   1553 
   1554 	return (arena_run_reg_alloc(bin->runcur, bin_info));
   1555 }
   1556 
   1557 void
   1558 arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin, size_t binind,
   1559     uint64_t prof_accumbytes)
   1560 {
   1561 	unsigned i, nfill;
   1562 	arena_bin_t *bin;
   1563 	arena_run_t *run;
   1564 	void *ptr;
   1565 
   1566 	assert(tbin->ncached == 0);
   1567 
   1568 	if (config_prof && arena_prof_accum(arena, prof_accumbytes))
   1569 		prof_idump();
   1570 	bin = &arena->bins[binind];
   1571 	malloc_mutex_lock(&bin->lock);
   1572 	for (i = 0, nfill = (tcache_bin_info[binind].ncached_max >>
   1573 	    tbin->lg_fill_div); i < nfill; i++) {
   1574 		if ((run = bin->runcur) != NULL && run->nfree > 0)
   1575 			ptr = arena_run_reg_alloc(run, &arena_bin_info[binind]);
   1576 		else
   1577 			ptr = arena_bin_malloc_hard(arena, bin);
   1578 		if (ptr == NULL)
   1579 			break;
   1580 		if (config_fill && opt_junk) {
   1581 			arena_alloc_junk_small(ptr, &arena_bin_info[binind],
   1582 			    true);
   1583 		}
   1584 		/* Insert such that low regions get used first. */
   1585 		tbin->avail[nfill - 1 - i] = ptr;
   1586 	}
   1587 	if (config_stats) {
   1588 		bin->stats.allocated += i * arena_bin_info[binind].reg_size;
   1589 		bin->stats.nmalloc += i;
   1590 		bin->stats.nrequests += tbin->tstats.nrequests;
   1591 		bin->stats.nfills++;
   1592 		tbin->tstats.nrequests = 0;
   1593 	}
   1594 	malloc_mutex_unlock(&bin->lock);
   1595 	tbin->ncached = i;
   1596 }
   1597 
   1598 void
   1599 arena_alloc_junk_small(void *ptr, arena_bin_info_t *bin_info, bool zero)
   1600 {
   1601 
   1602 	if (zero) {
   1603 		size_t redzone_size = bin_info->redzone_size;
   1604 		memset((void *)((uintptr_t)ptr - redzone_size), 0xa5,
   1605 		    redzone_size);
   1606 		memset((void *)((uintptr_t)ptr + bin_info->reg_size), 0xa5,
   1607 		    redzone_size);
   1608 	} else {
   1609 		memset((void *)((uintptr_t)ptr - bin_info->redzone_size), 0xa5,
   1610 		    bin_info->reg_interval);
   1611 	}
   1612 }
   1613 
   1614 #ifdef JEMALLOC_JET
   1615 #undef arena_redzone_corruption
   1616 #define	arena_redzone_corruption JEMALLOC_N(arena_redzone_corruption_impl)
   1617 #endif
   1618 static void
   1619 arena_redzone_corruption(void *ptr, size_t usize, bool after,
   1620     size_t offset, uint8_t byte)
   1621 {
   1622 
   1623 	malloc_printf("<jemalloc>: Corrupt redzone %zu byte%s %s %p "
   1624 	    "(size %zu), byte=%#x\n", offset, (offset == 1) ? "" : "s",
   1625 	    after ? "after" : "before", ptr, usize, byte);
   1626 }
   1627 #ifdef JEMALLOC_JET
   1628 #undef arena_redzone_corruption
   1629 #define	arena_redzone_corruption JEMALLOC_N(arena_redzone_corruption)
   1630 arena_redzone_corruption_t *arena_redzone_corruption =
   1631     JEMALLOC_N(arena_redzone_corruption_impl);
   1632 #endif
   1633 
   1634 static void
   1635 arena_redzones_validate(void *ptr, arena_bin_info_t *bin_info, bool reset)
   1636 {
   1637 	size_t size = bin_info->reg_size;
   1638 	size_t redzone_size = bin_info->redzone_size;
   1639 	size_t i;
   1640 	bool error = false;
   1641 
   1642 	for (i = 1; i <= redzone_size; i++) {
   1643 		uint8_t *byte = (uint8_t *)((uintptr_t)ptr - i);
   1644 		if (*byte != 0xa5) {
   1645 			error = true;
   1646 			arena_redzone_corruption(ptr, size, false, i, *byte);
   1647 			if (reset)
   1648 				*byte = 0xa5;
   1649 		}
   1650 	}
   1651 	for (i = 0; i < redzone_size; i++) {
   1652 		uint8_t *byte = (uint8_t *)((uintptr_t)ptr + size + i);
   1653 		if (*byte != 0xa5) {
   1654 			error = true;
   1655 			arena_redzone_corruption(ptr, size, true, i, *byte);
   1656 			if (reset)
   1657 				*byte = 0xa5;
   1658 		}
   1659 	}
   1660 	if (opt_abort && error)
   1661 		abort();
   1662 }
   1663 
   1664 #ifdef JEMALLOC_JET
   1665 #undef arena_dalloc_junk_small
   1666 #define	arena_dalloc_junk_small JEMALLOC_N(arena_dalloc_junk_small_impl)
   1667 #endif
   1668 void
   1669 arena_dalloc_junk_small(void *ptr, arena_bin_info_t *bin_info)
   1670 {
   1671 	size_t redzone_size = bin_info->redzone_size;
   1672 
   1673 	arena_redzones_validate(ptr, bin_info, false);
   1674 	memset((void *)((uintptr_t)ptr - redzone_size), 0x5a,
   1675 	    bin_info->reg_interval);
   1676 }
   1677 #ifdef JEMALLOC_JET
   1678 #undef arena_dalloc_junk_small
   1679 #define	arena_dalloc_junk_small JEMALLOC_N(arena_dalloc_junk_small)
   1680 arena_dalloc_junk_small_t *arena_dalloc_junk_small =
   1681     JEMALLOC_N(arena_dalloc_junk_small_impl);
   1682 #endif
   1683 
   1684 void
   1685 arena_quarantine_junk_small(void *ptr, size_t usize)
   1686 {
   1687 	size_t binind;
   1688 	arena_bin_info_t *bin_info;
   1689 	cassert(config_fill);
   1690 	assert(opt_junk);
   1691 	assert(opt_quarantine);
   1692 	assert(usize <= SMALL_MAXCLASS);
   1693 
   1694 	binind = small_size2bin(usize);
   1695 	bin_info = &arena_bin_info[binind];
   1696 	arena_redzones_validate(ptr, bin_info, true);
   1697 }
   1698 
   1699 void *
   1700 arena_malloc_small(arena_t *arena, size_t size, bool zero)
   1701 {
   1702 	void *ret;
   1703 	arena_bin_t *bin;
   1704 	arena_run_t *run;
   1705 	size_t binind;
   1706 
   1707 	binind = small_size2bin(size);
   1708 	assert(binind < NBINS);
   1709 	bin = &arena->bins[binind];
   1710 	size = small_bin2size(binind);
   1711 
   1712 	malloc_mutex_lock(&bin->lock);
   1713 	if ((run = bin->runcur) != NULL && run->nfree > 0)
   1714 		ret = arena_run_reg_alloc(run, &arena_bin_info[binind]);
   1715 	else
   1716 		ret = arena_bin_malloc_hard(arena, bin);
   1717 
   1718 	if (ret == NULL) {
   1719 		malloc_mutex_unlock(&bin->lock);
   1720 		return (NULL);
   1721 	}
   1722 
   1723 	if (config_stats) {
   1724 		bin->stats.allocated += size;
   1725 		bin->stats.nmalloc++;
   1726 		bin->stats.nrequests++;
   1727 	}
   1728 	malloc_mutex_unlock(&bin->lock);
   1729 	if (config_prof && isthreaded == false && arena_prof_accum(arena, size))
   1730 		prof_idump();
   1731 
   1732 	if (zero == false) {
   1733 		if (config_fill) {
   1734 			if (opt_junk) {
   1735 				arena_alloc_junk_small(ret,
   1736 				    &arena_bin_info[binind], false);
   1737 			} else if (opt_zero)
   1738 				memset(ret, 0, size);
   1739 		}
   1740 		JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, size);
   1741 	} else {
   1742 		if (config_fill && opt_junk) {
   1743 			arena_alloc_junk_small(ret, &arena_bin_info[binind],
   1744 			    true);
   1745 		}
   1746 		JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, size);
   1747 		memset(ret, 0, size);
   1748 	}
   1749 
   1750 	return (ret);
   1751 }
   1752 
   1753 void *
   1754 arena_malloc_large(arena_t *arena, size_t size, bool zero)
   1755 {
   1756 	void *ret;
   1757 	UNUSED bool idump;
   1758 
   1759 	/* Large allocation. */
   1760 	size = PAGE_CEILING(size);
   1761 	malloc_mutex_lock(&arena->lock);
   1762 	ret = (void *)arena_run_alloc_large(arena, size, zero);
   1763 	if (ret == NULL) {
   1764 		malloc_mutex_unlock(&arena->lock);
   1765 		return (NULL);
   1766 	}
   1767 	if (config_stats) {
   1768 		arena->stats.nmalloc_large++;
   1769 		arena->stats.nrequests_large++;
   1770 		arena->stats.allocated_large += size;
   1771 		arena->stats.lstats[(size >> LG_PAGE) - 1].nmalloc++;
   1772 		arena->stats.lstats[(size >> LG_PAGE) - 1].nrequests++;
   1773 		arena->stats.lstats[(size >> LG_PAGE) - 1].curruns++;
   1774 	}
   1775 	if (config_prof)
   1776 		idump = arena_prof_accum_locked(arena, size);
   1777 	malloc_mutex_unlock(&arena->lock);
   1778 	if (config_prof && idump)
   1779 		prof_idump();
   1780 
   1781 	if (zero == false) {
   1782 		if (config_fill) {
   1783 			if (opt_junk)
   1784 				memset(ret, 0xa5, size);
   1785 			else if (opt_zero)
   1786 				memset(ret, 0, size);
   1787 		}
   1788 	}
   1789 
   1790 	return (ret);
   1791 }
   1792 
   1793 /* Only handles large allocations that require more than page alignment. */
   1794 void *
   1795 arena_palloc(arena_t *arena, size_t size, size_t alignment, bool zero)
   1796 {
   1797 	void *ret;
   1798 	size_t alloc_size, leadsize, trailsize;
   1799 	arena_run_t *run;
   1800 	arena_chunk_t *chunk;
   1801 
   1802 	assert((size & PAGE_MASK) == 0);
   1803 
   1804 	alignment = PAGE_CEILING(alignment);
   1805 	alloc_size = size + alignment - PAGE;
   1806 
   1807 	malloc_mutex_lock(&arena->lock);
   1808 	run = arena_run_alloc_large(arena, alloc_size, false);
   1809 	if (run == NULL) {
   1810 		malloc_mutex_unlock(&arena->lock);
   1811 		return (NULL);
   1812 	}
   1813 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
   1814 
   1815 	leadsize = ALIGNMENT_CEILING((uintptr_t)run, alignment) -
   1816 	    (uintptr_t)run;
   1817 	assert(alloc_size >= leadsize + size);
   1818 	trailsize = alloc_size - leadsize - size;
   1819 	ret = (void *)((uintptr_t)run + leadsize);
   1820 	if (leadsize != 0) {
   1821 		arena_run_trim_head(arena, chunk, run, alloc_size, alloc_size -
   1822 		    leadsize);
   1823 	}
   1824 	if (trailsize != 0) {
   1825 		arena_run_trim_tail(arena, chunk, ret, size + trailsize, size,
   1826 		    false);
   1827 	}
   1828 	arena_run_init_large(arena, (arena_run_t *)ret, size, zero);
   1829 
   1830 	if (config_stats) {
   1831 		arena->stats.nmalloc_large++;
   1832 		arena->stats.nrequests_large++;
   1833 		arena->stats.allocated_large += size;
   1834 		arena->stats.lstats[(size >> LG_PAGE) - 1].nmalloc++;
   1835 		arena->stats.lstats[(size >> LG_PAGE) - 1].nrequests++;
   1836 		arena->stats.lstats[(size >> LG_PAGE) - 1].curruns++;
   1837 	}
   1838 	malloc_mutex_unlock(&arena->lock);
   1839 
   1840 	if (config_fill && zero == false) {
   1841 		if (opt_junk)
   1842 			memset(ret, 0xa5, size);
   1843 		else if (opt_zero)
   1844 			memset(ret, 0, size);
   1845 	}
   1846 	return (ret);
   1847 }
   1848 
   1849 void
   1850 arena_prof_promoted(const void *ptr, size_t size)
   1851 {
   1852 	arena_chunk_t *chunk;
   1853 	size_t pageind, binind;
   1854 
   1855 	cassert(config_prof);
   1856 	assert(ptr != NULL);
   1857 	assert(CHUNK_ADDR2BASE(ptr) != ptr);
   1858 	assert(isalloc(ptr, false) == PAGE);
   1859 	assert(isalloc(ptr, true) == PAGE);
   1860 	assert(size <= SMALL_MAXCLASS);
   1861 
   1862 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
   1863 	pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
   1864 	binind = small_size2bin(size);
   1865 	assert(binind < NBINS);
   1866 	arena_mapbits_large_binind_set(chunk, pageind, binind);
   1867 
   1868 	assert(isalloc(ptr, false) == PAGE);
   1869 	assert(isalloc(ptr, true) == size);
   1870 }
   1871 
   1872 static void
   1873 arena_dissociate_bin_run(arena_chunk_t *chunk, arena_run_t *run,
   1874     arena_bin_t *bin)
   1875 {
   1876 
   1877 	/* Dissociate run from bin. */
   1878 	if (run == bin->runcur)
   1879 		bin->runcur = NULL;
   1880 	else {
   1881 		size_t binind = arena_bin_index(chunk->arena, bin);
   1882 		arena_bin_info_t *bin_info = &arena_bin_info[binind];
   1883 
   1884 		if (bin_info->nregs != 1) {
   1885 			/*
   1886 			 * This block's conditional is necessary because if the
   1887 			 * run only contains one region, then it never gets
   1888 			 * inserted into the non-full runs tree.
   1889 			 */
   1890 			arena_bin_runs_remove(bin, run);
   1891 		}
   1892 	}
   1893 }
   1894 
   1895 static void
   1896 arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
   1897     arena_bin_t *bin)
   1898 {
   1899 	size_t binind;
   1900 	arena_bin_info_t *bin_info;
   1901 	size_t npages, run_ind, past;
   1902 
   1903 	assert(run != bin->runcur);
   1904 	assert(arena_run_tree_search(&bin->runs,
   1905 	    arena_mapp_get(chunk, ((uintptr_t)run-(uintptr_t)chunk)>>LG_PAGE))
   1906 	    == NULL);
   1907 
   1908 	binind = arena_bin_index(chunk->arena, run->bin);
   1909 	bin_info = &arena_bin_info[binind];
   1910 
   1911 	malloc_mutex_unlock(&bin->lock);
   1912 	/******************************/
   1913 	npages = bin_info->run_size >> LG_PAGE;
   1914 	run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE);
   1915 	past = (size_t)(PAGE_CEILING((uintptr_t)run +
   1916 	    (uintptr_t)bin_info->reg0_offset + (uintptr_t)(run->nextind *
   1917 	    bin_info->reg_interval - bin_info->redzone_size) -
   1918 	    (uintptr_t)chunk) >> LG_PAGE);
   1919 	malloc_mutex_lock(&arena->lock);
   1920 
   1921 	/*
   1922 	 * If the run was originally clean, and some pages were never touched,
   1923 	 * trim the clean pages before deallocating the dirty portion of the
   1924 	 * run.
   1925 	 */
   1926 	assert(arena_mapbits_dirty_get(chunk, run_ind) ==
   1927 	    arena_mapbits_dirty_get(chunk, run_ind+npages-1));
   1928 	if (arena_mapbits_dirty_get(chunk, run_ind) == 0 && past - run_ind <
   1929 	    npages) {
   1930 		/* Trim clean pages.  Convert to large run beforehand. */
   1931 		assert(npages > 0);
   1932 		arena_mapbits_large_set(chunk, run_ind, bin_info->run_size, 0);
   1933 		arena_mapbits_large_set(chunk, run_ind+npages-1, 0, 0);
   1934 		arena_run_trim_tail(arena, chunk, run, (npages << LG_PAGE),
   1935 		    ((past - run_ind) << LG_PAGE), false);
   1936 		/* npages = past - run_ind; */
   1937 	}
   1938 	arena_run_dalloc(arena, run, true, false);
   1939 	malloc_mutex_unlock(&arena->lock);
   1940 	/****************************/
   1941 	malloc_mutex_lock(&bin->lock);
   1942 	if (config_stats)
   1943 		bin->stats.curruns--;
   1944 }
   1945 
   1946 static void
   1947 arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
   1948     arena_bin_t *bin)
   1949 {
   1950 
   1951 	/*
   1952 	 * Make sure that if bin->runcur is non-NULL, it refers to the lowest
   1953 	 * non-full run.  It is okay to NULL runcur out rather than proactively
   1954 	 * keeping it pointing at the lowest non-full run.
   1955 	 */
   1956 	if ((uintptr_t)run < (uintptr_t)bin->runcur) {
   1957 		/* Switch runcur. */
   1958 		if (bin->runcur->nfree > 0)
   1959 			arena_bin_runs_insert(bin, bin->runcur);
   1960 		bin->runcur = run;
   1961 		if (config_stats)
   1962 			bin->stats.reruns++;
   1963 	} else
   1964 		arena_bin_runs_insert(bin, run);
   1965 }
   1966 
   1967 void
   1968 arena_dalloc_bin_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr,
   1969     arena_chunk_map_t *mapelm)
   1970 {
   1971 	size_t pageind;
   1972 	arena_run_t *run;
   1973 	arena_bin_t *bin;
   1974 	arena_bin_info_t *bin_info;
   1975 	size_t size, binind;
   1976 
   1977 	pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
   1978 	run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind -
   1979 	    arena_mapbits_small_runind_get(chunk, pageind)) << LG_PAGE));
   1980 	bin = run->bin;
   1981 	binind = arena_ptr_small_binind_get(ptr, arena_mapbits_get(chunk, pageind));
   1982 	bin_info = &arena_bin_info[binind];
   1983 	if (config_fill || config_stats)
   1984 		size = bin_info->reg_size;
   1985 
   1986 	if (config_fill && opt_junk)
   1987 		arena_dalloc_junk_small(ptr, bin_info);
   1988 
   1989 	arena_run_reg_dalloc(run, ptr);
   1990 	if (run->nfree == bin_info->nregs) {
   1991 		arena_dissociate_bin_run(chunk, run, bin);
   1992 		arena_dalloc_bin_run(arena, chunk, run, bin);
   1993 	} else if (run->nfree == 1 && run != bin->runcur)
   1994 		arena_bin_lower_run(arena, chunk, run, bin);
   1995 
   1996 	if (config_stats) {
   1997 		bin->stats.allocated -= size;
   1998 		bin->stats.ndalloc++;
   1999 	}
   2000 }
   2001 
   2002 void
   2003 arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr,
   2004     size_t pageind, arena_chunk_map_t *mapelm)
   2005 {
   2006 	arena_run_t *run;
   2007 	arena_bin_t *bin;
   2008 
   2009 	run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind -
   2010 	    arena_mapbits_small_runind_get(chunk, pageind)) << LG_PAGE));
   2011 	bin = run->bin;
   2012 	malloc_mutex_lock(&bin->lock);
   2013 	arena_dalloc_bin_locked(arena, chunk, ptr, mapelm);
   2014 	malloc_mutex_unlock(&bin->lock);
   2015 }
   2016 
   2017 void
   2018 arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
   2019     size_t pageind)
   2020 {
   2021 	arena_chunk_map_t *mapelm;
   2022 
   2023 	if (config_debug) {
   2024 		/* arena_ptr_small_binind_get() does extra sanity checking. */
   2025 		assert(arena_ptr_small_binind_get(ptr, arena_mapbits_get(chunk,
   2026 		    pageind)) != BININD_INVALID);
   2027 	}
   2028 	mapelm = arena_mapp_get(chunk, pageind);
   2029 	arena_dalloc_bin(arena, chunk, ptr, pageind, mapelm);
   2030 }
   2031 
   2032 #ifdef JEMALLOC_JET
   2033 #undef arena_dalloc_junk_large
   2034 #define	arena_dalloc_junk_large JEMALLOC_N(arena_dalloc_junk_large_impl)
   2035 #endif
   2036 static void
   2037 arena_dalloc_junk_large(void *ptr, size_t usize)
   2038 {
   2039 
   2040 	if (config_fill && opt_junk)
   2041 		memset(ptr, 0x5a, usize);
   2042 }
   2043 #ifdef JEMALLOC_JET
   2044 #undef arena_dalloc_junk_large
   2045 #define	arena_dalloc_junk_large JEMALLOC_N(arena_dalloc_junk_large)
   2046 arena_dalloc_junk_large_t *arena_dalloc_junk_large =
   2047     JEMALLOC_N(arena_dalloc_junk_large_impl);
   2048 #endif
   2049 
   2050 void
   2051 arena_dalloc_large_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr)
   2052 {
   2053 
   2054 	if (config_fill || config_stats) {
   2055 		size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
   2056 		size_t usize = arena_mapbits_large_size_get(chunk, pageind);
   2057 
   2058 		arena_dalloc_junk_large(ptr, usize);
   2059 		if (config_stats) {
   2060 			arena->stats.ndalloc_large++;
   2061 			arena->stats.allocated_large -= usize;
   2062 			arena->stats.lstats[(usize >> LG_PAGE) - 1].ndalloc++;
   2063 			arena->stats.lstats[(usize >> LG_PAGE) - 1].curruns--;
   2064 		}
   2065 	}
   2066 
   2067 	arena_run_dalloc(arena, (arena_run_t *)ptr, true, false);
   2068 }
   2069 
   2070 void
   2071 arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr)
   2072 {
   2073 
   2074 	malloc_mutex_lock(&arena->lock);
   2075 	arena_dalloc_large_locked(arena, chunk, ptr);
   2076 	malloc_mutex_unlock(&arena->lock);
   2077 }
   2078 
   2079 static void
   2080 arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr,
   2081     size_t oldsize, size_t size)
   2082 {
   2083 
   2084 	assert(size < oldsize);
   2085 
   2086 	/*
   2087 	 * Shrink the run, and make trailing pages available for other
   2088 	 * allocations.
   2089 	 */
   2090 	malloc_mutex_lock(&arena->lock);
   2091 	arena_run_trim_tail(arena, chunk, (arena_run_t *)ptr, oldsize, size,
   2092 	    true);
   2093 	if (config_stats) {
   2094 		arena->stats.ndalloc_large++;
   2095 		arena->stats.allocated_large -= oldsize;
   2096 		arena->stats.lstats[(oldsize >> LG_PAGE) - 1].ndalloc++;
   2097 		arena->stats.lstats[(oldsize >> LG_PAGE) - 1].curruns--;
   2098 
   2099 		arena->stats.nmalloc_large++;
   2100 		arena->stats.nrequests_large++;
   2101 		arena->stats.allocated_large += size;
   2102 		arena->stats.lstats[(size >> LG_PAGE) - 1].nmalloc++;
   2103 		arena->stats.lstats[(size >> LG_PAGE) - 1].nrequests++;
   2104 		arena->stats.lstats[(size >> LG_PAGE) - 1].curruns++;
   2105 	}
   2106 	malloc_mutex_unlock(&arena->lock);
   2107 }
   2108 
   2109 static bool
   2110 arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr,
   2111     size_t oldsize, size_t size, size_t extra, bool zero)
   2112 {
   2113 	size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
   2114 	size_t npages = oldsize >> LG_PAGE;
   2115 	size_t followsize;
   2116 
   2117 	assert(oldsize == arena_mapbits_large_size_get(chunk, pageind));
   2118 
   2119 	/* Try to extend the run. */
   2120 	assert(size + extra > oldsize);
   2121 	malloc_mutex_lock(&arena->lock);
   2122 	if (pageind + npages < chunk_npages &&
   2123 	    arena_mapbits_allocated_get(chunk, pageind+npages) == 0 &&
   2124 	    (followsize = arena_mapbits_unallocated_size_get(chunk,
   2125 	    pageind+npages)) >= size - oldsize) {
   2126 		/*
   2127 		 * The next run is available and sufficiently large.  Split the
   2128 		 * following run, then merge the first part with the existing
   2129 		 * allocation.
   2130 		 */
   2131 		size_t flag_dirty;
   2132 		size_t splitsize = (oldsize + followsize <= size + extra)
   2133 		    ? followsize : size + extra - oldsize;
   2134 		arena_run_split_large(arena, (arena_run_t *)((uintptr_t)chunk +
   2135 		    ((pageind+npages) << LG_PAGE)), splitsize, zero);
   2136 
   2137 		size = oldsize + splitsize;
   2138 		npages = size >> LG_PAGE;
   2139 
   2140 		/*
   2141 		 * Mark the extended run as dirty if either portion of the run
   2142 		 * was dirty before allocation.  This is rather pedantic,
   2143 		 * because there's not actually any sequence of events that
   2144 		 * could cause the resulting run to be passed to
   2145 		 * arena_run_dalloc() with the dirty argument set to false
   2146 		 * (which is when dirty flag consistency would really matter).
   2147 		 */
   2148 		flag_dirty = arena_mapbits_dirty_get(chunk, pageind) |
   2149 		    arena_mapbits_dirty_get(chunk, pageind+npages-1);
   2150 		arena_mapbits_large_set(chunk, pageind, size, flag_dirty);
   2151 		arena_mapbits_large_set(chunk, pageind+npages-1, 0, flag_dirty);
   2152 
   2153 		if (config_stats) {
   2154 			arena->stats.ndalloc_large++;
   2155 			arena->stats.allocated_large -= oldsize;
   2156 			arena->stats.lstats[(oldsize >> LG_PAGE) - 1].ndalloc++;
   2157 			arena->stats.lstats[(oldsize >> LG_PAGE) - 1].curruns--;
   2158 
   2159 			arena->stats.nmalloc_large++;
   2160 			arena->stats.nrequests_large++;
   2161 			arena->stats.allocated_large += size;
   2162 			arena->stats.lstats[(size >> LG_PAGE) - 1].nmalloc++;
   2163 			arena->stats.lstats[(size >> LG_PAGE) - 1].nrequests++;
   2164 			arena->stats.lstats[(size >> LG_PAGE) - 1].curruns++;
   2165 		}
   2166 		malloc_mutex_unlock(&arena->lock);
   2167 		return (false);
   2168 	}
   2169 	malloc_mutex_unlock(&arena->lock);
   2170 
   2171 	return (true);
   2172 }
   2173 
   2174 #ifdef JEMALLOC_JET
   2175 #undef arena_ralloc_junk_large
   2176 #define	arena_ralloc_junk_large JEMALLOC_N(arena_ralloc_junk_large_impl)
   2177 #endif
   2178 static void
   2179 arena_ralloc_junk_large(void *ptr, size_t old_usize, size_t usize)
   2180 {
   2181 
   2182 	if (config_fill && opt_junk) {
   2183 		memset((void *)((uintptr_t)ptr + usize), 0x5a,
   2184 		    old_usize - usize);
   2185 	}
   2186 }
   2187 #ifdef JEMALLOC_JET
   2188 #undef arena_ralloc_junk_large
   2189 #define	arena_ralloc_junk_large JEMALLOC_N(arena_ralloc_junk_large)
   2190 arena_ralloc_junk_large_t *arena_ralloc_junk_large =
   2191     JEMALLOC_N(arena_ralloc_junk_large_impl);
   2192 #endif
   2193 
   2194 /*
   2195  * Try to resize a large allocation, in order to avoid copying.  This will
   2196  * always fail if growing an object, and the following run is already in use.
   2197  */
   2198 static bool
   2199 arena_ralloc_large(void *ptr, size_t oldsize, size_t size, size_t extra,
   2200     bool zero)
   2201 {
   2202 	size_t psize;
   2203 
   2204 	psize = PAGE_CEILING(size + extra);
   2205 	if (psize == oldsize) {
   2206 		/* Same size class. */
   2207 		return (false);
   2208 	} else {
   2209 		arena_chunk_t *chunk;
   2210 		arena_t *arena;
   2211 
   2212 		chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
   2213 		arena = chunk->arena;
   2214 
   2215 		if (psize < oldsize) {
   2216 			/* Fill before shrinking in order avoid a race. */
   2217 			arena_ralloc_junk_large(ptr, oldsize, psize);
   2218 			arena_ralloc_large_shrink(arena, chunk, ptr, oldsize,
   2219 			    psize);
   2220 			return (false);
   2221 		} else {
   2222 			bool ret = arena_ralloc_large_grow(arena, chunk, ptr,
   2223 			    oldsize, PAGE_CEILING(size),
   2224 			    psize - PAGE_CEILING(size), zero);
   2225 			if (config_fill && ret == false && zero == false) {
   2226 				if (opt_junk) {
   2227 					memset((void *)((uintptr_t)ptr +
   2228 					    oldsize), 0xa5, isalloc(ptr,
   2229 					    config_prof) - oldsize);
   2230 				} else if (opt_zero) {
   2231 					memset((void *)((uintptr_t)ptr +
   2232 					    oldsize), 0, isalloc(ptr,
   2233 					    config_prof) - oldsize);
   2234 				}
   2235 			}
   2236 			return (ret);
   2237 		}
   2238 	}
   2239 }
   2240 
   2241 bool
   2242 arena_ralloc_no_move(void *ptr, size_t oldsize, size_t size, size_t extra,
   2243     bool zero)
   2244 {
   2245 
   2246 	/*
   2247 	 * Avoid moving the allocation if the size class can be left the same.
   2248 	 */
   2249 	if (oldsize <= arena_maxclass) {
   2250 		if (oldsize <= SMALL_MAXCLASS) {
   2251 			assert(arena_bin_info[small_size2bin(oldsize)].reg_size
   2252 			    == oldsize);
   2253 			if ((size + extra <= SMALL_MAXCLASS &&
   2254 			    small_size2bin(size + extra) ==
   2255 			    small_size2bin(oldsize)) || (size <= oldsize &&
   2256 			    size + extra >= oldsize))
   2257 				return (false);
   2258 		} else {
   2259 			assert(size <= arena_maxclass);
   2260 			if (size + extra > SMALL_MAXCLASS) {
   2261 				if (arena_ralloc_large(ptr, oldsize, size,
   2262 				    extra, zero) == false)
   2263 					return (false);
   2264 			}
   2265 		}
   2266 	}
   2267 
   2268 	/* Reallocation would require a move. */
   2269 	return (true);
   2270 }
   2271 
   2272 void *
   2273 arena_ralloc(arena_t *arena, void *ptr, size_t oldsize, size_t size,
   2274     size_t extra, size_t alignment, bool zero, bool try_tcache_alloc,
   2275     bool try_tcache_dalloc)
   2276 {
   2277 	void *ret;
   2278 	size_t copysize;
   2279 
   2280 	/* Try to avoid moving the allocation. */
   2281 	if (arena_ralloc_no_move(ptr, oldsize, size, extra, zero) == false)
   2282 		return (ptr);
   2283 
   2284 	/*
   2285 	 * size and oldsize are different enough that we need to move the
   2286 	 * object.  In that case, fall back to allocating new space and
   2287 	 * copying.
   2288 	 */
   2289 	if (alignment != 0) {
   2290 		size_t usize = sa2u(size + extra, alignment);
   2291 		if (usize == 0)
   2292 			return (NULL);
   2293 		ret = ipalloct(usize, alignment, zero, try_tcache_alloc, arena);
   2294 	} else
   2295 		ret = arena_malloc(arena, size + extra, zero, try_tcache_alloc);
   2296 
   2297 	if (ret == NULL) {
   2298 		if (extra == 0)
   2299 			return (NULL);
   2300 		/* Try again, this time without extra. */
   2301 		if (alignment != 0) {
   2302 			size_t usize = sa2u(size, alignment);
   2303 			if (usize == 0)
   2304 				return (NULL);
   2305 			ret = ipalloct(usize, alignment, zero, try_tcache_alloc,
   2306 			    arena);
   2307 		} else
   2308 			ret = arena_malloc(arena, size, zero, try_tcache_alloc);
   2309 
   2310 		if (ret == NULL)
   2311 			return (NULL);
   2312 	}
   2313 
   2314 	/* Junk/zero-filling were already done by ipalloc()/arena_malloc(). */
   2315 
   2316 	/*
   2317 	 * Copy at most size bytes (not size+extra), since the caller has no
   2318 	 * expectation that the extra bytes will be reliably preserved.
   2319 	 */
   2320 	copysize = (size < oldsize) ? size : oldsize;
   2321 	JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, copysize);
   2322 	memcpy(ret, ptr, copysize);
   2323 	iqalloct(ptr, try_tcache_dalloc);
   2324 	return (ret);
   2325 }
   2326 
   2327 dss_prec_t
   2328 arena_dss_prec_get(arena_t *arena)
   2329 {
   2330 	dss_prec_t ret;
   2331 
   2332 	malloc_mutex_lock(&arena->lock);
   2333 	ret = arena->dss_prec;
   2334 	malloc_mutex_unlock(&arena->lock);
   2335 	return (ret);
   2336 }
   2337 
   2338 bool
   2339 arena_dss_prec_set(arena_t *arena, dss_prec_t dss_prec)
   2340 {
   2341 
   2342 	if (have_dss == false)
   2343 		return (dss_prec != dss_prec_disabled);
   2344 	malloc_mutex_lock(&arena->lock);
   2345 	arena->dss_prec = dss_prec;
   2346 	malloc_mutex_unlock(&arena->lock);
   2347 	return (false);
   2348 }
   2349 
   2350 void
   2351 arena_stats_merge(arena_t *arena, const char **dss, size_t *nactive,
   2352     size_t *ndirty, arena_stats_t *astats, malloc_bin_stats_t *bstats,
   2353     malloc_large_stats_t *lstats)
   2354 {
   2355 	unsigned i;
   2356 
   2357 	malloc_mutex_lock(&arena->lock);
   2358 	*dss = dss_prec_names[arena->dss_prec];
   2359 	*nactive += arena->nactive;
   2360 	*ndirty += arena->ndirty;
   2361 
   2362 	astats->mapped += arena->stats.mapped;
   2363 	astats->npurge += arena->stats.npurge;
   2364 	astats->nmadvise += arena->stats.nmadvise;
   2365 	astats->purged += arena->stats.purged;
   2366 	astats->allocated_large += arena->stats.allocated_large;
   2367 	astats->nmalloc_large += arena->stats.nmalloc_large;
   2368 	astats->ndalloc_large += arena->stats.ndalloc_large;
   2369 	astats->nrequests_large += arena->stats.nrequests_large;
   2370 	astats->allocated_huge += arena->stats.allocated_huge;
   2371 	astats->nmalloc_huge += arena->stats.nmalloc_huge;
   2372 	astats->ndalloc_huge += arena->stats.ndalloc_huge;
   2373 	astats->nrequests_huge += arena->stats.nrequests_huge;
   2374 
   2375 	for (i = 0; i < nlclasses; i++) {
   2376 		lstats[i].nmalloc += arena->stats.lstats[i].nmalloc;
   2377 		lstats[i].ndalloc += arena->stats.lstats[i].ndalloc;
   2378 		lstats[i].nrequests += arena->stats.lstats[i].nrequests;
   2379 		lstats[i].curruns += arena->stats.lstats[i].curruns;
   2380 	}
   2381 	malloc_mutex_unlock(&arena->lock);
   2382 
   2383 	for (i = 0; i < NBINS; i++) {
   2384 		arena_bin_t *bin = &arena->bins[i];
   2385 
   2386 		malloc_mutex_lock(&bin->lock);
   2387 		bstats[i].allocated += bin->stats.allocated;
   2388 		bstats[i].nmalloc += bin->stats.nmalloc;
   2389 		bstats[i].ndalloc += bin->stats.ndalloc;
   2390 		bstats[i].nrequests += bin->stats.nrequests;
   2391 		if (config_tcache) {
   2392 			bstats[i].nfills += bin->stats.nfills;
   2393 			bstats[i].nflushes += bin->stats.nflushes;
   2394 		}
   2395 		bstats[i].nruns += bin->stats.nruns;
   2396 		bstats[i].reruns += bin->stats.reruns;
   2397 		bstats[i].curruns += bin->stats.curruns;
   2398 		malloc_mutex_unlock(&bin->lock);
   2399 	}
   2400 }
   2401 
   2402 bool
   2403 arena_new(arena_t *arena, unsigned ind)
   2404 {
   2405 	unsigned i;
   2406 	arena_bin_t *bin;
   2407 
   2408 	arena->ind = ind;
   2409 	arena->nthreads = 0;
   2410 	arena->chunk_alloc = chunk_alloc_default;
   2411 	arena->chunk_dalloc = chunk_dalloc_default;
   2412 
   2413 	if (malloc_mutex_init(&arena->lock))
   2414 		return (true);
   2415 
   2416 	if (config_stats) {
   2417 		memset(&arena->stats, 0, sizeof(arena_stats_t));
   2418 		arena->stats.lstats =
   2419 		    (malloc_large_stats_t *)base_alloc(nlclasses *
   2420 		    sizeof(malloc_large_stats_t));
   2421 		if (arena->stats.lstats == NULL)
   2422 			return (true);
   2423 		memset(arena->stats.lstats, 0, nlclasses *
   2424 		    sizeof(malloc_large_stats_t));
   2425 		if (config_tcache)
   2426 			ql_new(&arena->tcache_ql);
   2427 	}
   2428 
   2429 	if (config_prof)
   2430 		arena->prof_accumbytes = 0;
   2431 
   2432 	arena->dss_prec = chunk_dss_prec_get();
   2433 
   2434 	/* Initialize chunks. */
   2435 	arena_chunk_dirty_new(&arena->chunks_dirty);
   2436 	arena->spare = NULL;
   2437 
   2438 	arena->nactive = 0;
   2439 	arena->ndirty = 0;
   2440 	arena->npurgatory = 0;
   2441 
   2442 	arena_avail_tree_new(&arena->runs_avail);
   2443 
   2444 	/* Initialize bins. */
   2445 	for (i = 0; i < NBINS; i++) {
   2446 		bin = &arena->bins[i];
   2447 		if (malloc_mutex_init(&bin->lock))
   2448 			return (true);
   2449 		bin->runcur = NULL;
   2450 		arena_run_tree_new(&bin->runs);
   2451 		if (config_stats)
   2452 			memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
   2453 	}
   2454 
   2455 	return (false);
   2456 }
   2457 
   2458 /*
   2459  * Calculate bin_info->run_size such that it meets the following constraints:
   2460  *
   2461  *   *) bin_info->run_size >= min_run_size
   2462  *   *) bin_info->run_size <= arena_maxclass
   2463  *   *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed).
   2464  *   *) bin_info->nregs <= RUN_MAXREGS
   2465  *
   2466  * bin_info->nregs, bin_info->bitmap_offset, and bin_info->reg0_offset are also
   2467  * calculated here, since these settings are all interdependent.
   2468  */
   2469 static size_t
   2470 bin_info_run_size_calc(arena_bin_info_t *bin_info, size_t min_run_size)
   2471 {
   2472 	size_t pad_size;
   2473 	size_t try_run_size, good_run_size;
   2474 	uint32_t try_nregs, good_nregs;
   2475 	uint32_t try_hdr_size, good_hdr_size;
   2476 	uint32_t try_bitmap_offset, good_bitmap_offset;
   2477 	uint32_t try_redzone0_offset, good_redzone0_offset;
   2478 
   2479 	assert(min_run_size >= PAGE);
   2480 	assert(min_run_size <= arena_maxclass);
   2481 
   2482 	/*
   2483 	 * Determine redzone size based on minimum alignment and minimum
   2484 	 * redzone size.  Add padding to the end of the run if it is needed to
   2485 	 * align the regions.  The padding allows each redzone to be half the
   2486 	 * minimum alignment; without the padding, each redzone would have to
   2487 	 * be twice as large in order to maintain alignment.
   2488 	 */
   2489 	if (config_fill && opt_redzone) {
   2490 		size_t align_min = ZU(1) << (jemalloc_ffs(bin_info->reg_size) - 1);
   2491 		if (align_min <= REDZONE_MINSIZE) {
   2492 			bin_info->redzone_size = REDZONE_MINSIZE;
   2493 			pad_size = 0;
   2494 		} else {
   2495 			bin_info->redzone_size = align_min >> 1;
   2496 			pad_size = bin_info->redzone_size;
   2497 		}
   2498 	} else {
   2499 		bin_info->redzone_size = 0;
   2500 		pad_size = 0;
   2501 	}
   2502 	bin_info->reg_interval = bin_info->reg_size +
   2503 	    (bin_info->redzone_size << 1);
   2504 
   2505 	/*
   2506 	 * Calculate known-valid settings before entering the run_size
   2507 	 * expansion loop, so that the first part of the loop always copies
   2508 	 * valid settings.
   2509 	 *
   2510 	 * The do..while loop iteratively reduces the number of regions until
   2511 	 * the run header and the regions no longer overlap.  A closed formula
   2512 	 * would be quite messy, since there is an interdependency between the
   2513 	 * header's mask length and the number of regions.
   2514 	 */
   2515 	try_run_size = min_run_size;
   2516 	try_nregs = ((try_run_size - sizeof(arena_run_t)) /
   2517 	    bin_info->reg_interval)
   2518 	    + 1; /* Counter-act try_nregs-- in loop. */
   2519 	if (try_nregs > RUN_MAXREGS) {
   2520 		try_nregs = RUN_MAXREGS
   2521 		    + 1; /* Counter-act try_nregs-- in loop. */
   2522 	}
   2523 	do {
   2524 		try_nregs--;
   2525 		try_hdr_size = sizeof(arena_run_t);
   2526 		/* Pad to a long boundary. */
   2527 		try_hdr_size = LONG_CEILING(try_hdr_size);
   2528 		try_bitmap_offset = try_hdr_size;
   2529 		/* Add space for bitmap. */
   2530 		try_hdr_size += bitmap_size(try_nregs);
   2531 		try_redzone0_offset = try_run_size - (try_nregs *
   2532 		    bin_info->reg_interval) - pad_size;
   2533 	} while (try_hdr_size > try_redzone0_offset);
   2534 
   2535 	/* run_size expansion loop. */
   2536 	do {
   2537 		/*
   2538 		 * Copy valid settings before trying more aggressive settings.
   2539 		 */
   2540 		good_run_size = try_run_size;
   2541 		good_nregs = try_nregs;
   2542 		good_hdr_size = try_hdr_size;
   2543 		good_bitmap_offset = try_bitmap_offset;
   2544 		good_redzone0_offset = try_redzone0_offset;
   2545 
   2546 		/* Try more aggressive settings. */
   2547 		try_run_size += PAGE;
   2548 		try_nregs = ((try_run_size - sizeof(arena_run_t) - pad_size) /
   2549 		    bin_info->reg_interval)
   2550 		    + 1; /* Counter-act try_nregs-- in loop. */
   2551 		if (try_nregs > RUN_MAXREGS) {
   2552 			try_nregs = RUN_MAXREGS
   2553 			    + 1; /* Counter-act try_nregs-- in loop. */
   2554 		}
   2555 		do {
   2556 			try_nregs--;
   2557 			try_hdr_size = sizeof(arena_run_t);
   2558 			/* Pad to a long boundary. */
   2559 			try_hdr_size = LONG_CEILING(try_hdr_size);
   2560 			try_bitmap_offset = try_hdr_size;
   2561 			/* Add space for bitmap. */
   2562 			try_hdr_size += bitmap_size(try_nregs);
   2563 			try_redzone0_offset = try_run_size - (try_nregs *
   2564 			    bin_info->reg_interval) - pad_size;
   2565 		} while (try_hdr_size > try_redzone0_offset);
   2566 	} while (try_run_size <= arena_maxclass
   2567 	    && RUN_MAX_OVRHD * (bin_info->reg_interval << 3) >
   2568 	    RUN_MAX_OVRHD_RELAX
   2569 	    && (try_redzone0_offset << RUN_BFP) > RUN_MAX_OVRHD * try_run_size
   2570 	    && try_nregs < RUN_MAXREGS);
   2571 
   2572 	assert(good_hdr_size <= good_redzone0_offset);
   2573 
   2574 	/* Copy final settings. */
   2575 	bin_info->run_size = good_run_size;
   2576 	bin_info->nregs = good_nregs;
   2577 	bin_info->bitmap_offset = good_bitmap_offset;
   2578 	bin_info->reg0_offset = good_redzone0_offset + bin_info->redzone_size;
   2579 
   2580 	assert(bin_info->reg0_offset - bin_info->redzone_size + (bin_info->nregs
   2581 	    * bin_info->reg_interval) + pad_size == bin_info->run_size);
   2582 
   2583 	return (good_run_size);
   2584 }
   2585 
   2586 static void
   2587 bin_info_init(void)
   2588 {
   2589 	arena_bin_info_t *bin_info;
   2590 	size_t prev_run_size = PAGE;
   2591 
   2592 #define	BIN_INFO_INIT_bin_yes(index, size) \
   2593 	bin_info = &arena_bin_info[index];				\
   2594 	bin_info->reg_size = size;					\
   2595 	prev_run_size = bin_info_run_size_calc(bin_info, prev_run_size);\
   2596 	bitmap_info_init(&bin_info->bitmap_info, bin_info->nregs);
   2597 #define	BIN_INFO_INIT_bin_no(index, size)
   2598 #define	SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup)	\
   2599 	BIN_INFO_INIT_bin_##bin(index, (ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta))
   2600 	SIZE_CLASSES
   2601 #undef BIN_INFO_INIT_bin_yes
   2602 #undef BIN_INFO_INIT_bin_no
   2603 #undef SC
   2604 }
   2605 
   2606 void
   2607 arena_boot(void)
   2608 {
   2609 	size_t header_size;
   2610 	unsigned i;
   2611 
   2612 	/*
   2613 	 * Compute the header size such that it is large enough to contain the
   2614 	 * page map.  The page map is biased to omit entries for the header
   2615 	 * itself, so some iteration is necessary to compute the map bias.
   2616 	 *
   2617 	 * 1) Compute safe header_size and map_bias values that include enough
   2618 	 *    space for an unbiased page map.
   2619 	 * 2) Refine map_bias based on (1) to omit the header pages in the page
   2620 	 *    map.  The resulting map_bias may be one too small.
   2621 	 * 3) Refine map_bias based on (2).  The result will be >= the result
   2622 	 *    from (2), and will always be correct.
   2623 	 */
   2624 	map_bias = 0;
   2625 	for (i = 0; i < 3; i++) {
   2626 		header_size = offsetof(arena_chunk_t, map) +
   2627 		    (sizeof(arena_chunk_map_t) * (chunk_npages-map_bias));
   2628 		map_bias = (header_size >> LG_PAGE) + ((header_size & PAGE_MASK)
   2629 		    != 0);
   2630 	}
   2631 	assert(map_bias > 0);
   2632 
   2633 	arena_maxclass = chunksize - (map_bias << LG_PAGE);
   2634 
   2635 	bin_info_init();
   2636 }
   2637 
   2638 void
   2639 arena_prefork(arena_t *arena)
   2640 {
   2641 	unsigned i;
   2642 
   2643 	malloc_mutex_prefork(&arena->lock);
   2644 	for (i = 0; i < NBINS; i++)
   2645 		malloc_mutex_prefork(&arena->bins[i].lock);
   2646 }
   2647 
   2648 void
   2649 arena_postfork_parent(arena_t *arena)
   2650 {
   2651 	unsigned i;
   2652 
   2653 	for (i = 0; i < NBINS; i++)
   2654 		malloc_mutex_postfork_parent(&arena->bins[i].lock);
   2655 	malloc_mutex_postfork_parent(&arena->lock);
   2656 }
   2657 
   2658 void
   2659 arena_postfork_child(arena_t *arena)
   2660 {
   2661 	unsigned i;
   2662 
   2663 	for (i = 0; i < NBINS; i++)
   2664 		malloc_mutex_postfork_child(&arena->bins[i].lock);
   2665 	malloc_mutex_postfork_child(&arena->lock);
   2666 }
   2667