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