]> git.proxmox.com Git - rustc.git/blob - src/jemalloc/src/arena.c
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / jemalloc / src / arena.c
1 #define JEMALLOC_ARENA_C_
2 #include "jemalloc/internal/jemalloc_internal.h"
3
4 /******************************************************************************/
5 /* Data. */
6
7 purge_mode_t opt_purge = PURGE_DEFAULT;
8 const char *purge_mode_names[] = {
9 "ratio",
10 "decay",
11 "N/A"
12 };
13 ssize_t opt_lg_dirty_mult = LG_DIRTY_MULT_DEFAULT;
14 static ssize_t lg_dirty_mult_default;
15 ssize_t opt_decay_time = DECAY_TIME_DEFAULT;
16 static ssize_t decay_time_default;
17
18 arena_bin_info_t arena_bin_info[NBINS];
19
20 size_t map_bias;
21 size_t map_misc_offset;
22 size_t arena_maxrun; /* Max run size for arenas. */
23 size_t large_maxclass; /* Max large size class. */
24 size_t run_quantize_max; /* Max run_quantize_*() input. */
25 static size_t small_maxrun; /* Max run size for small size classes. */
26 static bool *small_run_tab; /* Valid small run page multiples. */
27 static size_t *run_quantize_floor_tab; /* run_quantize_floor() memoization. */
28 static size_t *run_quantize_ceil_tab; /* run_quantize_ceil() memoization. */
29 unsigned nlclasses; /* Number of large size classes. */
30 unsigned nhclasses; /* Number of huge size classes. */
31 static szind_t runs_avail_bias; /* Size index for first runs_avail tree. */
32 static szind_t runs_avail_nclasses; /* Number of runs_avail trees. */
33
34 /******************************************************************************/
35 /*
36 * Function prototypes for static functions that are referenced prior to
37 * definition.
38 */
39
40 static void arena_purge_to_limit(arena_t *arena, size_t ndirty_limit);
41 static void arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty,
42 bool cleaned, bool decommitted);
43 static void arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk,
44 arena_run_t *run, arena_bin_t *bin);
45 static void arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk,
46 arena_run_t *run, arena_bin_t *bin);
47
48 /******************************************************************************/
49
50 JEMALLOC_INLINE_C size_t
51 arena_miscelm_size_get(const arena_chunk_map_misc_t *miscelm)
52 {
53 arena_chunk_t *chunk;
54 size_t pageind, mapbits;
55
56 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(miscelm);
57 pageind = arena_miscelm_to_pageind(miscelm);
58 mapbits = arena_mapbits_get(chunk, pageind);
59 return (arena_mapbits_size_decode(mapbits));
60 }
61
62 JEMALLOC_INLINE_C int
63 arena_run_addr_comp(const arena_chunk_map_misc_t *a,
64 const arena_chunk_map_misc_t *b)
65 {
66 uintptr_t a_miscelm = (uintptr_t)a;
67 uintptr_t b_miscelm = (uintptr_t)b;
68
69 assert(a != NULL);
70 assert(b != NULL);
71
72 return ((a_miscelm > b_miscelm) - (a_miscelm < b_miscelm));
73 }
74
75 /* Generate red-black tree functions. */
76 rb_gen(static UNUSED, arena_run_tree_, arena_run_tree_t, arena_chunk_map_misc_t,
77 rb_link, arena_run_addr_comp)
78
79 static size_t
80 run_quantize_floor_compute(size_t size)
81 {
82 size_t qsize;
83
84 assert(size != 0);
85 assert(size == PAGE_CEILING(size));
86
87 /* Don't change sizes that are valid small run sizes. */
88 if (size <= small_maxrun && small_run_tab[size >> LG_PAGE])
89 return (size);
90
91 /*
92 * Round down to the nearest run size that can actually be requested
93 * during normal large allocation. Add large_pad so that cache index
94 * randomization can offset the allocation from the page boundary.
95 */
96 qsize = index2size(size2index(size - large_pad + 1) - 1) + large_pad;
97 if (qsize <= SMALL_MAXCLASS + large_pad)
98 return (run_quantize_floor_compute(size - large_pad));
99 assert(qsize <= size);
100 return (qsize);
101 }
102
103 static size_t
104 run_quantize_ceil_compute_hard(size_t size)
105 {
106 size_t large_run_size_next;
107
108 assert(size != 0);
109 assert(size == PAGE_CEILING(size));
110
111 /*
112 * Return the next quantized size greater than the input size.
113 * Quantized sizes comprise the union of run sizes that back small
114 * region runs, and run sizes that back large regions with no explicit
115 * alignment constraints.
116 */
117
118 if (size > SMALL_MAXCLASS) {
119 large_run_size_next = PAGE_CEILING(index2size(size2index(size -
120 large_pad) + 1) + large_pad);
121 } else
122 large_run_size_next = SIZE_T_MAX;
123 if (size >= small_maxrun)
124 return (large_run_size_next);
125
126 while (true) {
127 size += PAGE;
128 assert(size <= small_maxrun);
129 if (small_run_tab[size >> LG_PAGE]) {
130 if (large_run_size_next < size)
131 return (large_run_size_next);
132 return (size);
133 }
134 }
135 }
136
137 static size_t
138 run_quantize_ceil_compute(size_t size)
139 {
140 size_t qsize = run_quantize_floor_compute(size);
141
142 if (qsize < size) {
143 /*
144 * Skip a quantization that may have an adequately large run,
145 * because under-sized runs may be mixed in. This only happens
146 * when an unusual size is requested, i.e. for aligned
147 * allocation, and is just one of several places where linear
148 * search would potentially find sufficiently aligned available
149 * memory somewhere lower.
150 */
151 qsize = run_quantize_ceil_compute_hard(qsize);
152 }
153 return (qsize);
154 }
155
156 #ifdef JEMALLOC_JET
157 #undef run_quantize_floor
158 #define run_quantize_floor JEMALLOC_N(run_quantize_floor_impl)
159 #endif
160 static size_t
161 run_quantize_floor(size_t size)
162 {
163 size_t ret;
164
165 assert(size > 0);
166 assert(size <= run_quantize_max);
167 assert((size & PAGE_MASK) == 0);
168
169 ret = run_quantize_floor_tab[(size >> LG_PAGE) - 1];
170 assert(ret == run_quantize_floor_compute(size));
171 return (ret);
172 }
173 #ifdef JEMALLOC_JET
174 #undef run_quantize_floor
175 #define run_quantize_floor JEMALLOC_N(run_quantize_floor)
176 run_quantize_t *run_quantize_floor = JEMALLOC_N(run_quantize_floor_impl);
177 #endif
178
179 #ifdef JEMALLOC_JET
180 #undef run_quantize_ceil
181 #define run_quantize_ceil JEMALLOC_N(run_quantize_ceil_impl)
182 #endif
183 static size_t
184 run_quantize_ceil(size_t size)
185 {
186 size_t ret;
187
188 assert(size > 0);
189 assert(size <= run_quantize_max);
190 assert((size & PAGE_MASK) == 0);
191
192 ret = run_quantize_ceil_tab[(size >> LG_PAGE) - 1];
193 assert(ret == run_quantize_ceil_compute(size));
194 return (ret);
195 }
196 #ifdef JEMALLOC_JET
197 #undef run_quantize_ceil
198 #define run_quantize_ceil JEMALLOC_N(run_quantize_ceil)
199 run_quantize_t *run_quantize_ceil = JEMALLOC_N(run_quantize_ceil_impl);
200 #endif
201
202 static arena_run_tree_t *
203 arena_runs_avail_get(arena_t *arena, szind_t ind)
204 {
205
206 assert(ind >= runs_avail_bias);
207 assert(ind - runs_avail_bias < runs_avail_nclasses);
208
209 return (&arena->runs_avail[ind - runs_avail_bias]);
210 }
211
212 static void
213 arena_avail_insert(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
214 size_t npages)
215 {
216 szind_t ind = size2index(run_quantize_floor(arena_miscelm_size_get(
217 arena_miscelm_get(chunk, pageind))));
218 assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
219 LG_PAGE));
220 arena_run_tree_insert(arena_runs_avail_get(arena, ind),
221 arena_miscelm_get(chunk, pageind));
222 }
223
224 static void
225 arena_avail_remove(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
226 size_t npages)
227 {
228 szind_t ind = size2index(run_quantize_floor(arena_miscelm_size_get(
229 arena_miscelm_get(chunk, pageind))));
230 assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
231 LG_PAGE));
232 arena_run_tree_remove(arena_runs_avail_get(arena, ind),
233 arena_miscelm_get(chunk, pageind));
234 }
235
236 static void
237 arena_run_dirty_insert(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
238 size_t npages)
239 {
240 arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind);
241
242 assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
243 LG_PAGE));
244 assert(arena_mapbits_dirty_get(chunk, pageind) == CHUNK_MAP_DIRTY);
245 assert(arena_mapbits_dirty_get(chunk, pageind+npages-1) ==
246 CHUNK_MAP_DIRTY);
247
248 qr_new(&miscelm->rd, rd_link);
249 qr_meld(&arena->runs_dirty, &miscelm->rd, rd_link);
250 arena->ndirty += npages;
251 }
252
253 static void
254 arena_run_dirty_remove(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
255 size_t npages)
256 {
257 arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind);
258
259 assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
260 LG_PAGE));
261 assert(arena_mapbits_dirty_get(chunk, pageind) == CHUNK_MAP_DIRTY);
262 assert(arena_mapbits_dirty_get(chunk, pageind+npages-1) ==
263 CHUNK_MAP_DIRTY);
264
265 qr_remove(&miscelm->rd, rd_link);
266 assert(arena->ndirty >= npages);
267 arena->ndirty -= npages;
268 }
269
270 static size_t
271 arena_chunk_dirty_npages(const extent_node_t *node)
272 {
273
274 return (extent_node_size_get(node) >> LG_PAGE);
275 }
276
277 void
278 arena_chunk_cache_maybe_insert(arena_t *arena, extent_node_t *node, bool cache)
279 {
280
281 if (cache) {
282 extent_node_dirty_linkage_init(node);
283 extent_node_dirty_insert(node, &arena->runs_dirty,
284 &arena->chunks_cache);
285 arena->ndirty += arena_chunk_dirty_npages(node);
286 }
287 }
288
289 void
290 arena_chunk_cache_maybe_remove(arena_t *arena, extent_node_t *node, bool dirty)
291 {
292
293 if (dirty) {
294 extent_node_dirty_remove(node);
295 assert(arena->ndirty >= arena_chunk_dirty_npages(node));
296 arena->ndirty -= arena_chunk_dirty_npages(node);
297 }
298 }
299
300 JEMALLOC_INLINE_C void *
301 arena_run_reg_alloc(arena_run_t *run, arena_bin_info_t *bin_info)
302 {
303 void *ret;
304 size_t regind;
305 arena_chunk_map_misc_t *miscelm;
306 void *rpages;
307
308 assert(run->nfree > 0);
309 assert(!bitmap_full(run->bitmap, &bin_info->bitmap_info));
310
311 regind = (unsigned)bitmap_sfu(run->bitmap, &bin_info->bitmap_info);
312 miscelm = arena_run_to_miscelm(run);
313 rpages = arena_miscelm_to_rpages(miscelm);
314 ret = (void *)((uintptr_t)rpages + (uintptr_t)bin_info->reg0_offset +
315 (uintptr_t)(bin_info->reg_interval * regind));
316 run->nfree--;
317 return (ret);
318 }
319
320 JEMALLOC_INLINE_C void
321 arena_run_reg_dalloc(arena_run_t *run, void *ptr)
322 {
323 arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
324 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
325 size_t mapbits = arena_mapbits_get(chunk, pageind);
326 szind_t binind = arena_ptr_small_binind_get(ptr, mapbits);
327 arena_bin_info_t *bin_info = &arena_bin_info[binind];
328 size_t regind = arena_run_regind(run, bin_info, ptr);
329
330 assert(run->nfree < bin_info->nregs);
331 /* Freeing an interior pointer can cause assertion failure. */
332 assert(((uintptr_t)ptr -
333 ((uintptr_t)arena_miscelm_to_rpages(arena_run_to_miscelm(run)) +
334 (uintptr_t)bin_info->reg0_offset)) %
335 (uintptr_t)bin_info->reg_interval == 0);
336 assert((uintptr_t)ptr >=
337 (uintptr_t)arena_miscelm_to_rpages(arena_run_to_miscelm(run)) +
338 (uintptr_t)bin_info->reg0_offset);
339 /* Freeing an unallocated pointer can cause assertion failure. */
340 assert(bitmap_get(run->bitmap, &bin_info->bitmap_info, regind));
341
342 bitmap_unset(run->bitmap, &bin_info->bitmap_info, regind);
343 run->nfree++;
344 }
345
346 JEMALLOC_INLINE_C void
347 arena_run_zero(arena_chunk_t *chunk, size_t run_ind, size_t npages)
348 {
349
350 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk +
351 (run_ind << LG_PAGE)), (npages << LG_PAGE));
352 memset((void *)((uintptr_t)chunk + (run_ind << LG_PAGE)), 0,
353 (npages << LG_PAGE));
354 }
355
356 JEMALLOC_INLINE_C void
357 arena_run_page_mark_zeroed(arena_chunk_t *chunk, size_t run_ind)
358 {
359
360 JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void *)((uintptr_t)chunk + (run_ind
361 << LG_PAGE)), PAGE);
362 }
363
364 JEMALLOC_INLINE_C void
365 arena_run_page_validate_zeroed(arena_chunk_t *chunk, size_t run_ind)
366 {
367 size_t i;
368 UNUSED size_t *p = (size_t *)((uintptr_t)chunk + (run_ind << LG_PAGE));
369
370 arena_run_page_mark_zeroed(chunk, run_ind);
371 for (i = 0; i < PAGE / sizeof(size_t); i++)
372 assert(p[i] == 0);
373 }
374
375 static void
376 arena_nactive_add(arena_t *arena, size_t add_pages)
377 {
378
379 if (config_stats) {
380 size_t cactive_add = CHUNK_CEILING((arena->nactive +
381 add_pages) << LG_PAGE) - CHUNK_CEILING(arena->nactive <<
382 LG_PAGE);
383 if (cactive_add != 0)
384 stats_cactive_add(cactive_add);
385 }
386 arena->nactive += add_pages;
387 }
388
389 static void
390 arena_nactive_sub(arena_t *arena, size_t sub_pages)
391 {
392
393 if (config_stats) {
394 size_t cactive_sub = CHUNK_CEILING(arena->nactive << LG_PAGE) -
395 CHUNK_CEILING((arena->nactive - sub_pages) << LG_PAGE);
396 if (cactive_sub != 0)
397 stats_cactive_sub(cactive_sub);
398 }
399 arena->nactive -= sub_pages;
400 }
401
402 static void
403 arena_run_split_remove(arena_t *arena, arena_chunk_t *chunk, size_t run_ind,
404 size_t flag_dirty, size_t flag_decommitted, size_t need_pages)
405 {
406 size_t total_pages, rem_pages;
407
408 assert(flag_dirty == 0 || flag_decommitted == 0);
409
410 total_pages = arena_mapbits_unallocated_size_get(chunk, run_ind) >>
411 LG_PAGE;
412 assert(arena_mapbits_dirty_get(chunk, run_ind+total_pages-1) ==
413 flag_dirty);
414 assert(need_pages <= total_pages);
415 rem_pages = total_pages - need_pages;
416
417 arena_avail_remove(arena, chunk, run_ind, total_pages);
418 if (flag_dirty != 0)
419 arena_run_dirty_remove(arena, chunk, run_ind, total_pages);
420 arena_nactive_add(arena, need_pages);
421
422 /* Keep track of trailing unused pages for later use. */
423 if (rem_pages > 0) {
424 size_t flags = flag_dirty | flag_decommitted;
425 size_t flag_unzeroed_mask = (flags == 0) ? CHUNK_MAP_UNZEROED :
426 0;
427
428 arena_mapbits_unallocated_set(chunk, run_ind+need_pages,
429 (rem_pages << LG_PAGE), flags |
430 (arena_mapbits_unzeroed_get(chunk, run_ind+need_pages) &
431 flag_unzeroed_mask));
432 arena_mapbits_unallocated_set(chunk, run_ind+total_pages-1,
433 (rem_pages << LG_PAGE), flags |
434 (arena_mapbits_unzeroed_get(chunk, run_ind+total_pages-1) &
435 flag_unzeroed_mask));
436 if (flag_dirty != 0) {
437 arena_run_dirty_insert(arena, chunk, run_ind+need_pages,
438 rem_pages);
439 }
440 arena_avail_insert(arena, chunk, run_ind+need_pages, rem_pages);
441 }
442 }
443
444 static bool
445 arena_run_split_large_helper(arena_t *arena, arena_run_t *run, size_t size,
446 bool remove, bool zero)
447 {
448 arena_chunk_t *chunk;
449 arena_chunk_map_misc_t *miscelm;
450 size_t flag_dirty, flag_decommitted, run_ind, need_pages;
451 size_t flag_unzeroed_mask;
452
453 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
454 miscelm = arena_run_to_miscelm(run);
455 run_ind = arena_miscelm_to_pageind(miscelm);
456 flag_dirty = arena_mapbits_dirty_get(chunk, run_ind);
457 flag_decommitted = arena_mapbits_decommitted_get(chunk, run_ind);
458 need_pages = (size >> LG_PAGE);
459 assert(need_pages > 0);
460
461 if (flag_decommitted != 0 && arena->chunk_hooks.commit(chunk, chunksize,
462 run_ind << LG_PAGE, size, arena->ind))
463 return (true);
464
465 if (remove) {
466 arena_run_split_remove(arena, chunk, run_ind, flag_dirty,
467 flag_decommitted, need_pages);
468 }
469
470 if (zero) {
471 if (flag_decommitted != 0) {
472 /* The run is untouched, and therefore zeroed. */
473 JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void
474 *)((uintptr_t)chunk + (run_ind << LG_PAGE)),
475 (need_pages << LG_PAGE));
476 } else if (flag_dirty != 0) {
477 /* The run is dirty, so all pages must be zeroed. */
478 arena_run_zero(chunk, run_ind, need_pages);
479 } else {
480 /*
481 * The run is clean, so some pages may be zeroed (i.e.
482 * never before touched).
483 */
484 size_t i;
485 for (i = 0; i < need_pages; i++) {
486 if (arena_mapbits_unzeroed_get(chunk, run_ind+i)
487 != 0)
488 arena_run_zero(chunk, run_ind+i, 1);
489 else if (config_debug) {
490 arena_run_page_validate_zeroed(chunk,
491 run_ind+i);
492 } else {
493 arena_run_page_mark_zeroed(chunk,
494 run_ind+i);
495 }
496 }
497 }
498 } else {
499 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk +
500 (run_ind << LG_PAGE)), (need_pages << LG_PAGE));
501 }
502
503 /*
504 * Set the last element first, in case the run only contains one page
505 * (i.e. both statements set the same element).
506 */
507 flag_unzeroed_mask = (flag_dirty | flag_decommitted) == 0 ?
508 CHUNK_MAP_UNZEROED : 0;
509 arena_mapbits_large_set(chunk, run_ind+need_pages-1, 0, flag_dirty |
510 (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
511 run_ind+need_pages-1)));
512 arena_mapbits_large_set(chunk, run_ind, size, flag_dirty |
513 (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, run_ind)));
514 return (false);
515 }
516
517 static bool
518 arena_run_split_large(arena_t *arena, arena_run_t *run, size_t size, bool zero)
519 {
520
521 return (arena_run_split_large_helper(arena, run, size, true, zero));
522 }
523
524 static bool
525 arena_run_init_large(arena_t *arena, arena_run_t *run, size_t size, bool zero)
526 {
527
528 return (arena_run_split_large_helper(arena, run, size, false, zero));
529 }
530
531 static bool
532 arena_run_split_small(arena_t *arena, arena_run_t *run, size_t size,
533 szind_t binind)
534 {
535 arena_chunk_t *chunk;
536 arena_chunk_map_misc_t *miscelm;
537 size_t flag_dirty, flag_decommitted, run_ind, need_pages, i;
538
539 assert(binind != BININD_INVALID);
540
541 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
542 miscelm = arena_run_to_miscelm(run);
543 run_ind = arena_miscelm_to_pageind(miscelm);
544 flag_dirty = arena_mapbits_dirty_get(chunk, run_ind);
545 flag_decommitted = arena_mapbits_decommitted_get(chunk, run_ind);
546 need_pages = (size >> LG_PAGE);
547 assert(need_pages > 0);
548
549 if (flag_decommitted != 0 && arena->chunk_hooks.commit(chunk, chunksize,
550 run_ind << LG_PAGE, size, arena->ind))
551 return (true);
552
553 arena_run_split_remove(arena, chunk, run_ind, flag_dirty,
554 flag_decommitted, need_pages);
555
556 for (i = 0; i < need_pages; i++) {
557 size_t flag_unzeroed = arena_mapbits_unzeroed_get(chunk,
558 run_ind+i);
559 arena_mapbits_small_set(chunk, run_ind+i, i, binind,
560 flag_unzeroed);
561 if (config_debug && flag_dirty == 0 && flag_unzeroed == 0)
562 arena_run_page_validate_zeroed(chunk, run_ind+i);
563 }
564 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk +
565 (run_ind << LG_PAGE)), (need_pages << LG_PAGE));
566 return (false);
567 }
568
569 static arena_chunk_t *
570 arena_chunk_init_spare(arena_t *arena)
571 {
572 arena_chunk_t *chunk;
573
574 assert(arena->spare != NULL);
575
576 chunk = arena->spare;
577 arena->spare = NULL;
578
579 assert(arena_mapbits_allocated_get(chunk, map_bias) == 0);
580 assert(arena_mapbits_allocated_get(chunk, chunk_npages-1) == 0);
581 assert(arena_mapbits_unallocated_size_get(chunk, map_bias) ==
582 arena_maxrun);
583 assert(arena_mapbits_unallocated_size_get(chunk, chunk_npages-1) ==
584 arena_maxrun);
585 assert(arena_mapbits_dirty_get(chunk, map_bias) ==
586 arena_mapbits_dirty_get(chunk, chunk_npages-1));
587
588 return (chunk);
589 }
590
591 static bool
592 arena_chunk_register(arena_t *arena, arena_chunk_t *chunk, bool zero)
593 {
594
595 /*
596 * The extent node notion of "committed" doesn't directly apply to
597 * arena chunks. Arbitrarily mark them as committed. The commit state
598 * of runs is tracked individually, and upon chunk deallocation the
599 * entire chunk is in a consistent commit state.
600 */
601 extent_node_init(&chunk->node, arena, chunk, chunksize, zero, true);
602 extent_node_achunk_set(&chunk->node, true);
603 return (chunk_register(chunk, &chunk->node));
604 }
605
606 static arena_chunk_t *
607 arena_chunk_alloc_internal_hard(arena_t *arena, chunk_hooks_t *chunk_hooks,
608 bool *zero, bool *commit)
609 {
610 arena_chunk_t *chunk;
611
612 malloc_mutex_unlock(&arena->lock);
613
614 chunk = (arena_chunk_t *)chunk_alloc_wrapper(arena, chunk_hooks, NULL,
615 chunksize, chunksize, zero, commit);
616 if (chunk != NULL && !*commit) {
617 /* Commit header. */
618 if (chunk_hooks->commit(chunk, chunksize, 0, map_bias <<
619 LG_PAGE, arena->ind)) {
620 chunk_dalloc_wrapper(arena, chunk_hooks,
621 (void *)chunk, chunksize, *commit);
622 chunk = NULL;
623 }
624 }
625 if (chunk != NULL && arena_chunk_register(arena, chunk, *zero)) {
626 if (!*commit) {
627 /* Undo commit of header. */
628 chunk_hooks->decommit(chunk, chunksize, 0, map_bias <<
629 LG_PAGE, arena->ind);
630 }
631 chunk_dalloc_wrapper(arena, chunk_hooks, (void *)chunk,
632 chunksize, *commit);
633 chunk = NULL;
634 }
635
636 malloc_mutex_lock(&arena->lock);
637 return (chunk);
638 }
639
640 static arena_chunk_t *
641 arena_chunk_alloc_internal(arena_t *arena, bool *zero, bool *commit)
642 {
643 arena_chunk_t *chunk;
644 chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;
645
646 chunk = chunk_alloc_cache(arena, &chunk_hooks, NULL, chunksize,
647 chunksize, zero, true);
648 if (chunk != NULL) {
649 if (arena_chunk_register(arena, chunk, *zero)) {
650 chunk_dalloc_cache(arena, &chunk_hooks, chunk,
651 chunksize, true);
652 return (NULL);
653 }
654 *commit = true;
655 }
656 if (chunk == NULL) {
657 chunk = arena_chunk_alloc_internal_hard(arena, &chunk_hooks,
658 zero, commit);
659 }
660
661 if (config_stats && chunk != NULL) {
662 arena->stats.mapped += chunksize;
663 arena->stats.metadata_mapped += (map_bias << LG_PAGE);
664 }
665
666 return (chunk);
667 }
668
669 static arena_chunk_t *
670 arena_chunk_init_hard(arena_t *arena)
671 {
672 arena_chunk_t *chunk;
673 bool zero, commit;
674 size_t flag_unzeroed, flag_decommitted, i;
675
676 assert(arena->spare == NULL);
677
678 zero = false;
679 commit = false;
680 chunk = arena_chunk_alloc_internal(arena, &zero, &commit);
681 if (chunk == NULL)
682 return (NULL);
683
684 /*
685 * Initialize the map to contain one maximal free untouched run. Mark
686 * the pages as zeroed if chunk_alloc() returned a zeroed or decommitted
687 * chunk.
688 */
689 flag_unzeroed = (zero || !commit) ? 0 : CHUNK_MAP_UNZEROED;
690 flag_decommitted = commit ? 0 : CHUNK_MAP_DECOMMITTED;
691 arena_mapbits_unallocated_set(chunk, map_bias, arena_maxrun,
692 flag_unzeroed | flag_decommitted);
693 /*
694 * There is no need to initialize the internal page map entries unless
695 * the chunk is not zeroed.
696 */
697 if (!zero) {
698 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(
699 (void *)arena_bitselm_get(chunk, map_bias+1),
700 (size_t)((uintptr_t) arena_bitselm_get(chunk,
701 chunk_npages-1) - (uintptr_t)arena_bitselm_get(chunk,
702 map_bias+1)));
703 for (i = map_bias+1; i < chunk_npages-1; i++)
704 arena_mapbits_internal_set(chunk, i, flag_unzeroed);
705 } else {
706 JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void
707 *)arena_bitselm_get(chunk, map_bias+1), (size_t)((uintptr_t)
708 arena_bitselm_get(chunk, chunk_npages-1) -
709 (uintptr_t)arena_bitselm_get(chunk, map_bias+1)));
710 if (config_debug) {
711 for (i = map_bias+1; i < chunk_npages-1; i++) {
712 assert(arena_mapbits_unzeroed_get(chunk, i) ==
713 flag_unzeroed);
714 }
715 }
716 }
717 arena_mapbits_unallocated_set(chunk, chunk_npages-1, arena_maxrun,
718 flag_unzeroed);
719
720 return (chunk);
721 }
722
723 static arena_chunk_t *
724 arena_chunk_alloc(arena_t *arena)
725 {
726 arena_chunk_t *chunk;
727
728 if (arena->spare != NULL)
729 chunk = arena_chunk_init_spare(arena);
730 else {
731 chunk = arena_chunk_init_hard(arena);
732 if (chunk == NULL)
733 return (NULL);
734 }
735
736 arena_avail_insert(arena, chunk, map_bias, chunk_npages-map_bias);
737
738 return (chunk);
739 }
740
741 static void
742 arena_chunk_dalloc(arena_t *arena, arena_chunk_t *chunk)
743 {
744
745 assert(arena_mapbits_allocated_get(chunk, map_bias) == 0);
746 assert(arena_mapbits_allocated_get(chunk, chunk_npages-1) == 0);
747 assert(arena_mapbits_unallocated_size_get(chunk, map_bias) ==
748 arena_maxrun);
749 assert(arena_mapbits_unallocated_size_get(chunk, chunk_npages-1) ==
750 arena_maxrun);
751 assert(arena_mapbits_dirty_get(chunk, map_bias) ==
752 arena_mapbits_dirty_get(chunk, chunk_npages-1));
753 assert(arena_mapbits_decommitted_get(chunk, map_bias) ==
754 arena_mapbits_decommitted_get(chunk, chunk_npages-1));
755
756 /* Remove run from runs_avail, so that the arena does not use it. */
757 arena_avail_remove(arena, chunk, map_bias, chunk_npages-map_bias);
758
759 if (arena->spare != NULL) {
760 arena_chunk_t *spare = arena->spare;
761 chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;
762 bool committed;
763
764 arena->spare = chunk;
765 if (arena_mapbits_dirty_get(spare, map_bias) != 0) {
766 arena_run_dirty_remove(arena, spare, map_bias,
767 chunk_npages-map_bias);
768 }
769
770 chunk_deregister(spare, &spare->node);
771
772 committed = (arena_mapbits_decommitted_get(spare, map_bias) ==
773 0);
774 if (!committed) {
775 /*
776 * Decommit the header. Mark the chunk as decommitted
777 * even if header decommit fails, since treating a
778 * partially committed chunk as committed has a high
779 * potential for causing later access of decommitted
780 * memory.
781 */
782 chunk_hooks = chunk_hooks_get(arena);
783 chunk_hooks.decommit(spare, chunksize, 0, map_bias <<
784 LG_PAGE, arena->ind);
785 }
786
787 chunk_dalloc_cache(arena, &chunk_hooks, (void *)spare,
788 chunksize, committed);
789
790 if (config_stats) {
791 arena->stats.mapped -= chunksize;
792 arena->stats.metadata_mapped -= (map_bias << LG_PAGE);
793 }
794 } else
795 arena->spare = chunk;
796 }
797
798 static void
799 arena_huge_malloc_stats_update(arena_t *arena, size_t usize)
800 {
801 szind_t index = size2index(usize) - nlclasses - NBINS;
802
803 cassert(config_stats);
804
805 arena->stats.nmalloc_huge++;
806 arena->stats.allocated_huge += usize;
807 arena->stats.hstats[index].nmalloc++;
808 arena->stats.hstats[index].curhchunks++;
809 }
810
811 static void
812 arena_huge_malloc_stats_update_undo(arena_t *arena, size_t usize)
813 {
814 szind_t index = size2index(usize) - nlclasses - NBINS;
815
816 cassert(config_stats);
817
818 arena->stats.nmalloc_huge--;
819 arena->stats.allocated_huge -= usize;
820 arena->stats.hstats[index].nmalloc--;
821 arena->stats.hstats[index].curhchunks--;
822 }
823
824 static void
825 arena_huge_dalloc_stats_update(arena_t *arena, size_t usize)
826 {
827 szind_t index = size2index(usize) - nlclasses - NBINS;
828
829 cassert(config_stats);
830
831 arena->stats.ndalloc_huge++;
832 arena->stats.allocated_huge -= usize;
833 arena->stats.hstats[index].ndalloc++;
834 arena->stats.hstats[index].curhchunks--;
835 }
836
837 static void
838 arena_huge_dalloc_stats_update_undo(arena_t *arena, size_t usize)
839 {
840 szind_t index = size2index(usize) - nlclasses - NBINS;
841
842 cassert(config_stats);
843
844 arena->stats.ndalloc_huge--;
845 arena->stats.allocated_huge += usize;
846 arena->stats.hstats[index].ndalloc--;
847 arena->stats.hstats[index].curhchunks++;
848 }
849
850 static void
851 arena_huge_ralloc_stats_update(arena_t *arena, size_t oldsize, size_t usize)
852 {
853
854 arena_huge_dalloc_stats_update(arena, oldsize);
855 arena_huge_malloc_stats_update(arena, usize);
856 }
857
858 static void
859 arena_huge_ralloc_stats_update_undo(arena_t *arena, size_t oldsize,
860 size_t usize)
861 {
862
863 arena_huge_dalloc_stats_update_undo(arena, oldsize);
864 arena_huge_malloc_stats_update_undo(arena, usize);
865 }
866
867 extent_node_t *
868 arena_node_alloc(arena_t *arena)
869 {
870 extent_node_t *node;
871
872 malloc_mutex_lock(&arena->node_cache_mtx);
873 node = ql_last(&arena->node_cache, ql_link);
874 if (node == NULL) {
875 malloc_mutex_unlock(&arena->node_cache_mtx);
876 return (base_alloc(sizeof(extent_node_t)));
877 }
878 ql_tail_remove(&arena->node_cache, extent_node_t, ql_link);
879 malloc_mutex_unlock(&arena->node_cache_mtx);
880 return (node);
881 }
882
883 void
884 arena_node_dalloc(arena_t *arena, extent_node_t *node)
885 {
886
887 malloc_mutex_lock(&arena->node_cache_mtx);
888 ql_elm_new(node, ql_link);
889 ql_tail_insert(&arena->node_cache, node, ql_link);
890 malloc_mutex_unlock(&arena->node_cache_mtx);
891 }
892
893 static void *
894 arena_chunk_alloc_huge_hard(arena_t *arena, chunk_hooks_t *chunk_hooks,
895 size_t usize, size_t alignment, bool *zero, size_t csize)
896 {
897 void *ret;
898 bool commit = true;
899
900 ret = chunk_alloc_wrapper(arena, chunk_hooks, NULL, csize, alignment,
901 zero, &commit);
902 if (ret == NULL) {
903 /* Revert optimistic stats updates. */
904 malloc_mutex_lock(&arena->lock);
905 if (config_stats) {
906 arena_huge_malloc_stats_update_undo(arena, usize);
907 arena->stats.mapped -= usize;
908 }
909 arena_nactive_sub(arena, usize >> LG_PAGE);
910 malloc_mutex_unlock(&arena->lock);
911 }
912
913 return (ret);
914 }
915
916 void *
917 arena_chunk_alloc_huge(arena_t *arena, size_t usize, size_t alignment,
918 bool *zero)
919 {
920 void *ret;
921 chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;
922 size_t csize = CHUNK_CEILING(usize);
923
924 malloc_mutex_lock(&arena->lock);
925
926 /* Optimistically update stats. */
927 if (config_stats) {
928 arena_huge_malloc_stats_update(arena, usize);
929 arena->stats.mapped += usize;
930 }
931 arena_nactive_add(arena, usize >> LG_PAGE);
932
933 ret = chunk_alloc_cache(arena, &chunk_hooks, NULL, csize, alignment,
934 zero, true);
935 malloc_mutex_unlock(&arena->lock);
936 if (ret == NULL) {
937 ret = arena_chunk_alloc_huge_hard(arena, &chunk_hooks, usize,
938 alignment, zero, csize);
939 }
940
941 return (ret);
942 }
943
944 void
945 arena_chunk_dalloc_huge(arena_t *arena, void *chunk, size_t usize)
946 {
947 chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;
948 size_t csize;
949
950 csize = CHUNK_CEILING(usize);
951 malloc_mutex_lock(&arena->lock);
952 if (config_stats) {
953 arena_huge_dalloc_stats_update(arena, usize);
954 arena->stats.mapped -= usize;
955 }
956 arena_nactive_sub(arena, usize >> LG_PAGE);
957
958 chunk_dalloc_cache(arena, &chunk_hooks, chunk, csize, true);
959 malloc_mutex_unlock(&arena->lock);
960 }
961
962 void
963 arena_chunk_ralloc_huge_similar(arena_t *arena, void *chunk, size_t oldsize,
964 size_t usize)
965 {
966
967 assert(CHUNK_CEILING(oldsize) == CHUNK_CEILING(usize));
968 assert(oldsize != usize);
969
970 malloc_mutex_lock(&arena->lock);
971 if (config_stats)
972 arena_huge_ralloc_stats_update(arena, oldsize, usize);
973 if (oldsize < usize)
974 arena_nactive_add(arena, (usize - oldsize) >> LG_PAGE);
975 else
976 arena_nactive_sub(arena, (oldsize - usize) >> LG_PAGE);
977 malloc_mutex_unlock(&arena->lock);
978 }
979
980 void
981 arena_chunk_ralloc_huge_shrink(arena_t *arena, void *chunk, size_t oldsize,
982 size_t usize)
983 {
984 size_t udiff = oldsize - usize;
985 size_t cdiff = CHUNK_CEILING(oldsize) - CHUNK_CEILING(usize);
986
987 malloc_mutex_lock(&arena->lock);
988 if (config_stats) {
989 arena_huge_ralloc_stats_update(arena, oldsize, usize);
990 if (cdiff != 0)
991 arena->stats.mapped -= cdiff;
992 }
993 arena_nactive_sub(arena, udiff >> LG_PAGE);
994
995 if (cdiff != 0) {
996 chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;
997 void *nchunk = (void *)((uintptr_t)chunk +
998 CHUNK_CEILING(usize));
999
1000 chunk_dalloc_cache(arena, &chunk_hooks, nchunk, cdiff, true);
1001 }
1002 malloc_mutex_unlock(&arena->lock);
1003 }
1004
1005 static bool
1006 arena_chunk_ralloc_huge_expand_hard(arena_t *arena, chunk_hooks_t *chunk_hooks,
1007 void *chunk, size_t oldsize, size_t usize, bool *zero, void *nchunk,
1008 size_t udiff, size_t cdiff)
1009 {
1010 bool err;
1011 bool commit = true;
1012
1013 err = (chunk_alloc_wrapper(arena, chunk_hooks, nchunk, cdiff, chunksize,
1014 zero, &commit) == NULL);
1015 if (err) {
1016 /* Revert optimistic stats updates. */
1017 malloc_mutex_lock(&arena->lock);
1018 if (config_stats) {
1019 arena_huge_ralloc_stats_update_undo(arena, oldsize,
1020 usize);
1021 arena->stats.mapped -= cdiff;
1022 }
1023 arena_nactive_sub(arena, udiff >> LG_PAGE);
1024 malloc_mutex_unlock(&arena->lock);
1025 } else if (chunk_hooks->merge(chunk, CHUNK_CEILING(oldsize), nchunk,
1026 cdiff, true, arena->ind)) {
1027 chunk_dalloc_arena(arena, chunk_hooks, nchunk, cdiff, *zero,
1028 true);
1029 err = true;
1030 }
1031 return (err);
1032 }
1033
1034 bool
1035 arena_chunk_ralloc_huge_expand(arena_t *arena, void *chunk, size_t oldsize,
1036 size_t usize, bool *zero)
1037 {
1038 bool err;
1039 chunk_hooks_t chunk_hooks = chunk_hooks_get(arena);
1040 void *nchunk = (void *)((uintptr_t)chunk + CHUNK_CEILING(oldsize));
1041 size_t udiff = usize - oldsize;
1042 size_t cdiff = CHUNK_CEILING(usize) - CHUNK_CEILING(oldsize);
1043
1044 malloc_mutex_lock(&arena->lock);
1045
1046 /* Optimistically update stats. */
1047 if (config_stats) {
1048 arena_huge_ralloc_stats_update(arena, oldsize, usize);
1049 arena->stats.mapped += cdiff;
1050 }
1051 arena_nactive_add(arena, udiff >> LG_PAGE);
1052
1053 err = (chunk_alloc_cache(arena, &arena->chunk_hooks, nchunk, cdiff,
1054 chunksize, zero, true) == NULL);
1055 malloc_mutex_unlock(&arena->lock);
1056 if (err) {
1057 err = arena_chunk_ralloc_huge_expand_hard(arena, &chunk_hooks,
1058 chunk, oldsize, usize, zero, nchunk, udiff,
1059 cdiff);
1060 } else if (chunk_hooks.merge(chunk, CHUNK_CEILING(oldsize), nchunk,
1061 cdiff, true, arena->ind)) {
1062 chunk_dalloc_arena(arena, &chunk_hooks, nchunk, cdiff, *zero,
1063 true);
1064 err = true;
1065 }
1066
1067 return (err);
1068 }
1069
1070 /*
1071 * Do first-best-fit run selection, i.e. select the lowest run that best fits.
1072 * Run sizes are indexed, so not all candidate runs are necessarily exactly the
1073 * same size.
1074 */
1075 static arena_run_t *
1076 arena_run_first_best_fit(arena_t *arena, size_t size)
1077 {
1078 szind_t ind, i;
1079
1080 ind = size2index(run_quantize_ceil(size));
1081 for (i = ind; i < runs_avail_nclasses + runs_avail_bias; i++) {
1082 arena_chunk_map_misc_t *miscelm = arena_run_tree_first(
1083 arena_runs_avail_get(arena, i));
1084 if (miscelm != NULL)
1085 return (&miscelm->run);
1086 }
1087
1088 return (NULL);
1089 }
1090
1091 static arena_run_t *
1092 arena_run_alloc_large_helper(arena_t *arena, size_t size, bool zero)
1093 {
1094 arena_run_t *run = arena_run_first_best_fit(arena, s2u(size));
1095 if (run != NULL) {
1096 if (arena_run_split_large(arena, run, size, zero))
1097 run = NULL;
1098 }
1099 return (run);
1100 }
1101
1102 static arena_run_t *
1103 arena_run_alloc_large(arena_t *arena, size_t size, bool zero)
1104 {
1105 arena_chunk_t *chunk;
1106 arena_run_t *run;
1107
1108 assert(size <= arena_maxrun);
1109 assert(size == PAGE_CEILING(size));
1110
1111 /* Search the arena's chunks for the lowest best fit. */
1112 run = arena_run_alloc_large_helper(arena, size, zero);
1113 if (run != NULL)
1114 return (run);
1115
1116 /*
1117 * No usable runs. Create a new chunk from which to allocate the run.
1118 */
1119 chunk = arena_chunk_alloc(arena);
1120 if (chunk != NULL) {
1121 run = &arena_miscelm_get(chunk, map_bias)->run;
1122 if (arena_run_split_large(arena, run, size, zero))
1123 run = NULL;
1124 return (run);
1125 }
1126
1127 /*
1128 * arena_chunk_alloc() failed, but another thread may have made
1129 * sufficient memory available while this one dropped arena->lock in
1130 * arena_chunk_alloc(), so search one more time.
1131 */
1132 return (arena_run_alloc_large_helper(arena, size, zero));
1133 }
1134
1135 static arena_run_t *
1136 arena_run_alloc_small_helper(arena_t *arena, size_t size, szind_t binind)
1137 {
1138 arena_run_t *run = arena_run_first_best_fit(arena, size);
1139 if (run != NULL) {
1140 if (arena_run_split_small(arena, run, size, binind))
1141 run = NULL;
1142 }
1143 return (run);
1144 }
1145
1146 static arena_run_t *
1147 arena_run_alloc_small(arena_t *arena, size_t size, szind_t binind)
1148 {
1149 arena_chunk_t *chunk;
1150 arena_run_t *run;
1151
1152 assert(size <= arena_maxrun);
1153 assert(size == PAGE_CEILING(size));
1154 assert(binind != BININD_INVALID);
1155
1156 /* Search the arena's chunks for the lowest best fit. */
1157 run = arena_run_alloc_small_helper(arena, size, binind);
1158 if (run != NULL)
1159 return (run);
1160
1161 /*
1162 * No usable runs. Create a new chunk from which to allocate the run.
1163 */
1164 chunk = arena_chunk_alloc(arena);
1165 if (chunk != NULL) {
1166 run = &arena_miscelm_get(chunk, map_bias)->run;
1167 if (arena_run_split_small(arena, run, size, binind))
1168 run = NULL;
1169 return (run);
1170 }
1171
1172 /*
1173 * arena_chunk_alloc() failed, but another thread may have made
1174 * sufficient memory available while this one dropped arena->lock in
1175 * arena_chunk_alloc(), so search one more time.
1176 */
1177 return (arena_run_alloc_small_helper(arena, size, binind));
1178 }
1179
1180 static bool
1181 arena_lg_dirty_mult_valid(ssize_t lg_dirty_mult)
1182 {
1183
1184 return (lg_dirty_mult >= -1 && lg_dirty_mult < (ssize_t)(sizeof(size_t)
1185 << 3));
1186 }
1187
1188 ssize_t
1189 arena_lg_dirty_mult_get(arena_t *arena)
1190 {
1191 ssize_t lg_dirty_mult;
1192
1193 malloc_mutex_lock(&arena->lock);
1194 lg_dirty_mult = arena->lg_dirty_mult;
1195 malloc_mutex_unlock(&arena->lock);
1196
1197 return (lg_dirty_mult);
1198 }
1199
1200 bool
1201 arena_lg_dirty_mult_set(arena_t *arena, ssize_t lg_dirty_mult)
1202 {
1203
1204 if (!arena_lg_dirty_mult_valid(lg_dirty_mult))
1205 return (true);
1206
1207 malloc_mutex_lock(&arena->lock);
1208 arena->lg_dirty_mult = lg_dirty_mult;
1209 arena_maybe_purge(arena);
1210 malloc_mutex_unlock(&arena->lock);
1211
1212 return (false);
1213 }
1214
1215 static void
1216 arena_decay_deadline_init(arena_t *arena)
1217 {
1218
1219 assert(opt_purge == purge_mode_decay);
1220
1221 /*
1222 * Generate a new deadline that is uniformly random within the next
1223 * epoch after the current one.
1224 */
1225 nstime_copy(&arena->decay_deadline, &arena->decay_epoch);
1226 nstime_add(&arena->decay_deadline, &arena->decay_interval);
1227 if (arena->decay_time > 0) {
1228 nstime_t jitter;
1229
1230 nstime_init(&jitter, prng_range(&arena->decay_jitter_state,
1231 nstime_ns(&arena->decay_interval)));
1232 nstime_add(&arena->decay_deadline, &jitter);
1233 }
1234 }
1235
1236 static bool
1237 arena_decay_deadline_reached(const arena_t *arena, const nstime_t *time)
1238 {
1239
1240 assert(opt_purge == purge_mode_decay);
1241
1242 return (nstime_compare(&arena->decay_deadline, time) <= 0);
1243 }
1244
1245 static size_t
1246 arena_decay_backlog_npages_limit(const arena_t *arena)
1247 {
1248 static const uint64_t h_steps[] = {
1249 #define STEP(step, h, x, y) \
1250 h,
1251 SMOOTHSTEP
1252 #undef STEP
1253 };
1254 uint64_t sum;
1255 size_t npages_limit_backlog;
1256 unsigned i;
1257
1258 assert(opt_purge == purge_mode_decay);
1259
1260 /*
1261 * For each element of decay_backlog, multiply by the corresponding
1262 * fixed-point smoothstep decay factor. Sum the products, then divide
1263 * to round down to the nearest whole number of pages.
1264 */
1265 sum = 0;
1266 for (i = 0; i < SMOOTHSTEP_NSTEPS; i++)
1267 sum += arena->decay_backlog[i] * h_steps[i];
1268 npages_limit_backlog = (sum >> SMOOTHSTEP_BFP);
1269
1270 return (npages_limit_backlog);
1271 }
1272
1273 static void
1274 arena_decay_epoch_advance(arena_t *arena, const nstime_t *time)
1275 {
1276 uint64_t nadvance;
1277 nstime_t delta;
1278 size_t ndirty_delta;
1279
1280 assert(opt_purge == purge_mode_decay);
1281 assert(arena_decay_deadline_reached(arena, time));
1282
1283 nstime_copy(&delta, time);
1284 nstime_subtract(&delta, &arena->decay_epoch);
1285 nadvance = nstime_divide(&delta, &arena->decay_interval);
1286 assert(nadvance > 0);
1287
1288 /* Add nadvance decay intervals to epoch. */
1289 nstime_copy(&delta, &arena->decay_interval);
1290 nstime_imultiply(&delta, nadvance);
1291 nstime_add(&arena->decay_epoch, &delta);
1292
1293 /* Set a new deadline. */
1294 arena_decay_deadline_init(arena);
1295
1296 /* Update the backlog. */
1297 if (nadvance >= SMOOTHSTEP_NSTEPS) {
1298 memset(arena->decay_backlog, 0, (SMOOTHSTEP_NSTEPS-1) *
1299 sizeof(size_t));
1300 } else {
1301 memmove(arena->decay_backlog, &arena->decay_backlog[nadvance],
1302 (SMOOTHSTEP_NSTEPS - nadvance) * sizeof(size_t));
1303 if (nadvance > 1) {
1304 memset(&arena->decay_backlog[SMOOTHSTEP_NSTEPS -
1305 nadvance], 0, (nadvance-1) * sizeof(size_t));
1306 }
1307 }
1308 ndirty_delta = (arena->ndirty > arena->decay_ndirty) ? arena->ndirty -
1309 arena->decay_ndirty : 0;
1310 arena->decay_ndirty = arena->ndirty;
1311 arena->decay_backlog[SMOOTHSTEP_NSTEPS-1] = ndirty_delta;
1312 arena->decay_backlog_npages_limit =
1313 arena_decay_backlog_npages_limit(arena);
1314 }
1315
1316 static size_t
1317 arena_decay_npages_limit(arena_t *arena)
1318 {
1319 size_t npages_limit;
1320
1321 assert(opt_purge == purge_mode_decay);
1322
1323 npages_limit = arena->decay_backlog_npages_limit;
1324
1325 /* Add in any dirty pages created during the current epoch. */
1326 if (arena->ndirty > arena->decay_ndirty)
1327 npages_limit += arena->ndirty - arena->decay_ndirty;
1328
1329 return (npages_limit);
1330 }
1331
1332 static void
1333 arena_decay_init(arena_t *arena, ssize_t decay_time)
1334 {
1335
1336 arena->decay_time = decay_time;
1337 if (decay_time > 0) {
1338 nstime_init2(&arena->decay_interval, decay_time, 0);
1339 nstime_idivide(&arena->decay_interval, SMOOTHSTEP_NSTEPS);
1340 }
1341
1342 nstime_init(&arena->decay_epoch, 0);
1343 nstime_update(&arena->decay_epoch);
1344 arena->decay_jitter_state = (uint64_t)(uintptr_t)arena;
1345 arena_decay_deadline_init(arena);
1346 arena->decay_ndirty = arena->ndirty;
1347 arena->decay_backlog_npages_limit = 0;
1348 memset(arena->decay_backlog, 0, SMOOTHSTEP_NSTEPS * sizeof(size_t));
1349 }
1350
1351 static bool
1352 arena_decay_time_valid(ssize_t decay_time)
1353 {
1354
1355 return (decay_time >= -1 && decay_time <= NSTIME_SEC_MAX);
1356 }
1357
1358 ssize_t
1359 arena_decay_time_get(arena_t *arena)
1360 {
1361 ssize_t decay_time;
1362
1363 malloc_mutex_lock(&arena->lock);
1364 decay_time = arena->decay_time;
1365 malloc_mutex_unlock(&arena->lock);
1366
1367 return (decay_time);
1368 }
1369
1370 bool
1371 arena_decay_time_set(arena_t *arena, ssize_t decay_time)
1372 {
1373
1374 if (!arena_decay_time_valid(decay_time))
1375 return (true);
1376
1377 malloc_mutex_lock(&arena->lock);
1378 /*
1379 * Restart decay backlog from scratch, which may cause many dirty pages
1380 * to be immediately purged. It would conceptually be possible to map
1381 * the old backlog onto the new backlog, but there is no justification
1382 * for such complexity since decay_time changes are intended to be
1383 * infrequent, either between the {-1, 0, >0} states, or a one-time
1384 * arbitrary change during initial arena configuration.
1385 */
1386 arena_decay_init(arena, decay_time);
1387 arena_maybe_purge(arena);
1388 malloc_mutex_unlock(&arena->lock);
1389
1390 return (false);
1391 }
1392
1393 static void
1394 arena_maybe_purge_ratio(arena_t *arena)
1395 {
1396
1397 assert(opt_purge == purge_mode_ratio);
1398
1399 /* Don't purge if the option is disabled. */
1400 if (arena->lg_dirty_mult < 0)
1401 return;
1402
1403 /*
1404 * Iterate, since preventing recursive purging could otherwise leave too
1405 * many dirty pages.
1406 */
1407 while (true) {
1408 size_t threshold = (arena->nactive >> arena->lg_dirty_mult);
1409 if (threshold < chunk_npages)
1410 threshold = chunk_npages;
1411 /*
1412 * Don't purge unless the number of purgeable pages exceeds the
1413 * threshold.
1414 */
1415 if (arena->ndirty <= threshold)
1416 return;
1417 arena_purge_to_limit(arena, threshold);
1418 }
1419 }
1420
1421 static void
1422 arena_maybe_purge_decay(arena_t *arena)
1423 {
1424 nstime_t time;
1425 size_t ndirty_limit;
1426
1427 assert(opt_purge == purge_mode_decay);
1428
1429 /* Purge all or nothing if the option is disabled. */
1430 if (arena->decay_time <= 0) {
1431 if (arena->decay_time == 0)
1432 arena_purge_to_limit(arena, 0);
1433 return;
1434 }
1435
1436 nstime_copy(&time, &arena->decay_epoch);
1437 if (unlikely(nstime_update(&time))) {
1438 /* Time went backwards. Force an epoch advance. */
1439 nstime_copy(&time, &arena->decay_deadline);
1440 }
1441
1442 if (arena_decay_deadline_reached(arena, &time))
1443 arena_decay_epoch_advance(arena, &time);
1444
1445 ndirty_limit = arena_decay_npages_limit(arena);
1446
1447 /*
1448 * Don't try to purge unless the number of purgeable pages exceeds the
1449 * current limit.
1450 */
1451 if (arena->ndirty <= ndirty_limit)
1452 return;
1453 arena_purge_to_limit(arena, ndirty_limit);
1454 }
1455
1456 void
1457 arena_maybe_purge(arena_t *arena)
1458 {
1459
1460 /* Don't recursively purge. */
1461 if (arena->purging)
1462 return;
1463
1464 if (opt_purge == purge_mode_ratio)
1465 arena_maybe_purge_ratio(arena);
1466 else
1467 arena_maybe_purge_decay(arena);
1468 }
1469
1470 static size_t
1471 arena_dirty_count(arena_t *arena)
1472 {
1473 size_t ndirty = 0;
1474 arena_runs_dirty_link_t *rdelm;
1475 extent_node_t *chunkselm;
1476
1477 for (rdelm = qr_next(&arena->runs_dirty, rd_link),
1478 chunkselm = qr_next(&arena->chunks_cache, cc_link);
1479 rdelm != &arena->runs_dirty; rdelm = qr_next(rdelm, rd_link)) {
1480 size_t npages;
1481
1482 if (rdelm == &chunkselm->rd) {
1483 npages = extent_node_size_get(chunkselm) >> LG_PAGE;
1484 chunkselm = qr_next(chunkselm, cc_link);
1485 } else {
1486 arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(
1487 rdelm);
1488 arena_chunk_map_misc_t *miscelm =
1489 arena_rd_to_miscelm(rdelm);
1490 size_t pageind = arena_miscelm_to_pageind(miscelm);
1491 assert(arena_mapbits_allocated_get(chunk, pageind) ==
1492 0);
1493 assert(arena_mapbits_large_get(chunk, pageind) == 0);
1494 assert(arena_mapbits_dirty_get(chunk, pageind) != 0);
1495 npages = arena_mapbits_unallocated_size_get(chunk,
1496 pageind) >> LG_PAGE;
1497 }
1498 ndirty += npages;
1499 }
1500
1501 return (ndirty);
1502 }
1503
1504 static size_t
1505 arena_stash_dirty(arena_t *arena, chunk_hooks_t *chunk_hooks,
1506 size_t ndirty_limit, arena_runs_dirty_link_t *purge_runs_sentinel,
1507 extent_node_t *purge_chunks_sentinel)
1508 {
1509 arena_runs_dirty_link_t *rdelm, *rdelm_next;
1510 extent_node_t *chunkselm;
1511 size_t nstashed = 0;
1512
1513 /* Stash runs/chunks according to ndirty_limit. */
1514 for (rdelm = qr_next(&arena->runs_dirty, rd_link),
1515 chunkselm = qr_next(&arena->chunks_cache, cc_link);
1516 rdelm != &arena->runs_dirty; rdelm = rdelm_next) {
1517 size_t npages;
1518 rdelm_next = qr_next(rdelm, rd_link);
1519
1520 if (rdelm == &chunkselm->rd) {
1521 extent_node_t *chunkselm_next;
1522 bool zero;
1523 UNUSED void *chunk;
1524
1525 npages = extent_node_size_get(chunkselm) >> LG_PAGE;
1526 if (opt_purge == purge_mode_decay && arena->ndirty -
1527 (nstashed + npages) < ndirty_limit)
1528 break;
1529
1530 chunkselm_next = qr_next(chunkselm, cc_link);
1531 /*
1532 * Allocate. chunkselm remains valid due to the
1533 * dalloc_node=false argument to chunk_alloc_cache().
1534 */
1535 zero = false;
1536 chunk = chunk_alloc_cache(arena, chunk_hooks,
1537 extent_node_addr_get(chunkselm),
1538 extent_node_size_get(chunkselm), chunksize, &zero,
1539 false);
1540 assert(chunk == extent_node_addr_get(chunkselm));
1541 assert(zero == extent_node_zeroed_get(chunkselm));
1542 extent_node_dirty_insert(chunkselm, purge_runs_sentinel,
1543 purge_chunks_sentinel);
1544 assert(npages == (extent_node_size_get(chunkselm) >>
1545 LG_PAGE));
1546 chunkselm = chunkselm_next;
1547 } else {
1548 arena_chunk_t *chunk =
1549 (arena_chunk_t *)CHUNK_ADDR2BASE(rdelm);
1550 arena_chunk_map_misc_t *miscelm =
1551 arena_rd_to_miscelm(rdelm);
1552 size_t pageind = arena_miscelm_to_pageind(miscelm);
1553 arena_run_t *run = &miscelm->run;
1554 size_t run_size =
1555 arena_mapbits_unallocated_size_get(chunk, pageind);
1556
1557 npages = run_size >> LG_PAGE;
1558 if (opt_purge == purge_mode_decay && arena->ndirty -
1559 (nstashed + npages) < ndirty_limit)
1560 break;
1561
1562 assert(pageind + npages <= chunk_npages);
1563 assert(arena_mapbits_dirty_get(chunk, pageind) ==
1564 arena_mapbits_dirty_get(chunk, pageind+npages-1));
1565
1566 /*
1567 * If purging the spare chunk's run, make it available
1568 * prior to allocation.
1569 */
1570 if (chunk == arena->spare)
1571 arena_chunk_alloc(arena);
1572
1573 /* Temporarily allocate the free dirty run. */
1574 arena_run_split_large(arena, run, run_size, false);
1575 /* Stash. */
1576 if (false)
1577 qr_new(rdelm, rd_link); /* Redundant. */
1578 else {
1579 assert(qr_next(rdelm, rd_link) == rdelm);
1580 assert(qr_prev(rdelm, rd_link) == rdelm);
1581 }
1582 qr_meld(purge_runs_sentinel, rdelm, rd_link);
1583 }
1584
1585 nstashed += npages;
1586 if (opt_purge == purge_mode_ratio && arena->ndirty - nstashed <=
1587 ndirty_limit)
1588 break;
1589 }
1590
1591 return (nstashed);
1592 }
1593
1594 static size_t
1595 arena_purge_stashed(arena_t *arena, chunk_hooks_t *chunk_hooks,
1596 arena_runs_dirty_link_t *purge_runs_sentinel,
1597 extent_node_t *purge_chunks_sentinel)
1598 {
1599 size_t npurged, nmadvise;
1600 arena_runs_dirty_link_t *rdelm;
1601 extent_node_t *chunkselm;
1602
1603 if (config_stats)
1604 nmadvise = 0;
1605 npurged = 0;
1606
1607 malloc_mutex_unlock(&arena->lock);
1608 for (rdelm = qr_next(purge_runs_sentinel, rd_link),
1609 chunkselm = qr_next(purge_chunks_sentinel, cc_link);
1610 rdelm != purge_runs_sentinel; rdelm = qr_next(rdelm, rd_link)) {
1611 size_t npages;
1612
1613 if (rdelm == &chunkselm->rd) {
1614 /*
1615 * Don't actually purge the chunk here because 1)
1616 * chunkselm is embedded in the chunk and must remain
1617 * valid, and 2) we deallocate the chunk in
1618 * arena_unstash_purged(), where it is destroyed,
1619 * decommitted, or purged, depending on chunk
1620 * deallocation policy.
1621 */
1622 size_t size = extent_node_size_get(chunkselm);
1623 npages = size >> LG_PAGE;
1624 chunkselm = qr_next(chunkselm, cc_link);
1625 } else {
1626 size_t pageind, run_size, flag_unzeroed, flags, i;
1627 bool decommitted;
1628 arena_chunk_t *chunk =
1629 (arena_chunk_t *)CHUNK_ADDR2BASE(rdelm);
1630 arena_chunk_map_misc_t *miscelm =
1631 arena_rd_to_miscelm(rdelm);
1632 pageind = arena_miscelm_to_pageind(miscelm);
1633 run_size = arena_mapbits_large_size_get(chunk, pageind);
1634 npages = run_size >> LG_PAGE;
1635
1636 assert(pageind + npages <= chunk_npages);
1637 assert(!arena_mapbits_decommitted_get(chunk, pageind));
1638 assert(!arena_mapbits_decommitted_get(chunk,
1639 pageind+npages-1));
1640 decommitted = !chunk_hooks->decommit(chunk, chunksize,
1641 pageind << LG_PAGE, npages << LG_PAGE, arena->ind);
1642 if (decommitted) {
1643 flag_unzeroed = 0;
1644 flags = CHUNK_MAP_DECOMMITTED;
1645 } else {
1646 flag_unzeroed = chunk_purge_wrapper(arena,
1647 chunk_hooks, chunk, chunksize, pageind <<
1648 LG_PAGE, run_size) ? CHUNK_MAP_UNZEROED : 0;
1649 flags = flag_unzeroed;
1650 }
1651 arena_mapbits_large_set(chunk, pageind+npages-1, 0,
1652 flags);
1653 arena_mapbits_large_set(chunk, pageind, run_size,
1654 flags);
1655
1656 /*
1657 * Set the unzeroed flag for internal pages, now that
1658 * chunk_purge_wrapper() has returned whether the pages
1659 * were zeroed as a side effect of purging. This chunk
1660 * map modification is safe even though the arena mutex
1661 * isn't currently owned by this thread, because the run
1662 * is marked as allocated, thus protecting it from being
1663 * modified by any other thread. As long as these
1664 * writes don't perturb the first and last elements'
1665 * CHUNK_MAP_ALLOCATED bits, behavior is well defined.
1666 */
1667 for (i = 1; i < npages-1; i++) {
1668 arena_mapbits_internal_set(chunk, pageind+i,
1669 flag_unzeroed);
1670 }
1671 }
1672
1673 npurged += npages;
1674 if (config_stats)
1675 nmadvise++;
1676 }
1677 malloc_mutex_lock(&arena->lock);
1678
1679 if (config_stats) {
1680 arena->stats.nmadvise += nmadvise;
1681 arena->stats.purged += npurged;
1682 }
1683
1684 return (npurged);
1685 }
1686
1687 static void
1688 arena_unstash_purged(arena_t *arena, chunk_hooks_t *chunk_hooks,
1689 arena_runs_dirty_link_t *purge_runs_sentinel,
1690 extent_node_t *purge_chunks_sentinel)
1691 {
1692 arena_runs_dirty_link_t *rdelm, *rdelm_next;
1693 extent_node_t *chunkselm;
1694
1695 /* Deallocate chunks/runs. */
1696 for (rdelm = qr_next(purge_runs_sentinel, rd_link),
1697 chunkselm = qr_next(purge_chunks_sentinel, cc_link);
1698 rdelm != purge_runs_sentinel; rdelm = rdelm_next) {
1699 rdelm_next = qr_next(rdelm, rd_link);
1700 if (rdelm == &chunkselm->rd) {
1701 extent_node_t *chunkselm_next = qr_next(chunkselm,
1702 cc_link);
1703 void *addr = extent_node_addr_get(chunkselm);
1704 size_t size = extent_node_size_get(chunkselm);
1705 bool zeroed = extent_node_zeroed_get(chunkselm);
1706 bool committed = extent_node_committed_get(chunkselm);
1707 extent_node_dirty_remove(chunkselm);
1708 arena_node_dalloc(arena, chunkselm);
1709 chunkselm = chunkselm_next;
1710 chunk_dalloc_arena(arena, chunk_hooks, addr, size,
1711 zeroed, committed);
1712 } else {
1713 arena_chunk_t *chunk =
1714 (arena_chunk_t *)CHUNK_ADDR2BASE(rdelm);
1715 arena_chunk_map_misc_t *miscelm =
1716 arena_rd_to_miscelm(rdelm);
1717 size_t pageind = arena_miscelm_to_pageind(miscelm);
1718 bool decommitted = (arena_mapbits_decommitted_get(chunk,
1719 pageind) != 0);
1720 arena_run_t *run = &miscelm->run;
1721 qr_remove(rdelm, rd_link);
1722 arena_run_dalloc(arena, run, false, true, decommitted);
1723 }
1724 }
1725 }
1726
1727 /*
1728 * NB: ndirty_limit is interpreted differently depending on opt_purge:
1729 * - purge_mode_ratio: Purge as few dirty run/chunks as possible to reach the
1730 * desired state:
1731 * (arena->ndirty <= ndirty_limit)
1732 * - purge_mode_decay: Purge as many dirty runs/chunks as possible without
1733 * violating the invariant:
1734 * (arena->ndirty >= ndirty_limit)
1735 */
1736 static void
1737 arena_purge_to_limit(arena_t *arena, size_t ndirty_limit)
1738 {
1739 chunk_hooks_t chunk_hooks = chunk_hooks_get(arena);
1740 size_t npurge, npurged;
1741 arena_runs_dirty_link_t purge_runs_sentinel;
1742 extent_node_t purge_chunks_sentinel;
1743
1744 arena->purging = true;
1745
1746 /*
1747 * Calls to arena_dirty_count() are disabled even for debug builds
1748 * because overhead grows nonlinearly as memory usage increases.
1749 */
1750 if (false && config_debug) {
1751 size_t ndirty = arena_dirty_count(arena);
1752 assert(ndirty == arena->ndirty);
1753 }
1754 assert(opt_purge != purge_mode_ratio || (arena->nactive >>
1755 arena->lg_dirty_mult) < arena->ndirty || ndirty_limit == 0);
1756
1757 qr_new(&purge_runs_sentinel, rd_link);
1758 extent_node_dirty_linkage_init(&purge_chunks_sentinel);
1759
1760 npurge = arena_stash_dirty(arena, &chunk_hooks, ndirty_limit,
1761 &purge_runs_sentinel, &purge_chunks_sentinel);
1762 if (npurge == 0)
1763 goto label_return;
1764 npurged = arena_purge_stashed(arena, &chunk_hooks, &purge_runs_sentinel,
1765 &purge_chunks_sentinel);
1766 assert(npurged == npurge);
1767 arena_unstash_purged(arena, &chunk_hooks, &purge_runs_sentinel,
1768 &purge_chunks_sentinel);
1769
1770 if (config_stats)
1771 arena->stats.npurge++;
1772
1773 label_return:
1774 arena->purging = false;
1775 }
1776
1777 void
1778 arena_purge(arena_t *arena, bool all)
1779 {
1780
1781 malloc_mutex_lock(&arena->lock);
1782 if (all)
1783 arena_purge_to_limit(arena, 0);
1784 else
1785 arena_maybe_purge(arena);
1786 malloc_mutex_unlock(&arena->lock);
1787 }
1788
1789 static void
1790 arena_run_coalesce(arena_t *arena, arena_chunk_t *chunk, size_t *p_size,
1791 size_t *p_run_ind, size_t *p_run_pages, size_t flag_dirty,
1792 size_t flag_decommitted)
1793 {
1794 size_t size = *p_size;
1795 size_t run_ind = *p_run_ind;
1796 size_t run_pages = *p_run_pages;
1797
1798 /* Try to coalesce forward. */
1799 if (run_ind + run_pages < chunk_npages &&
1800 arena_mapbits_allocated_get(chunk, run_ind+run_pages) == 0 &&
1801 arena_mapbits_dirty_get(chunk, run_ind+run_pages) == flag_dirty &&
1802 arena_mapbits_decommitted_get(chunk, run_ind+run_pages) ==
1803 flag_decommitted) {
1804 size_t nrun_size = arena_mapbits_unallocated_size_get(chunk,
1805 run_ind+run_pages);
1806 size_t nrun_pages = nrun_size >> LG_PAGE;
1807
1808 /*
1809 * Remove successor from runs_avail; the coalesced run is
1810 * inserted later.
1811 */
1812 assert(arena_mapbits_unallocated_size_get(chunk,
1813 run_ind+run_pages+nrun_pages-1) == nrun_size);
1814 assert(arena_mapbits_dirty_get(chunk,
1815 run_ind+run_pages+nrun_pages-1) == flag_dirty);
1816 assert(arena_mapbits_decommitted_get(chunk,
1817 run_ind+run_pages+nrun_pages-1) == flag_decommitted);
1818 arena_avail_remove(arena, chunk, run_ind+run_pages, nrun_pages);
1819
1820 /*
1821 * If the successor is dirty, remove it from the set of dirty
1822 * pages.
1823 */
1824 if (flag_dirty != 0) {
1825 arena_run_dirty_remove(arena, chunk, run_ind+run_pages,
1826 nrun_pages);
1827 }
1828
1829 size += nrun_size;
1830 run_pages += nrun_pages;
1831
1832 arena_mapbits_unallocated_size_set(chunk, run_ind, size);
1833 arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1,
1834 size);
1835 }
1836
1837 /* Try to coalesce backward. */
1838 if (run_ind > map_bias && arena_mapbits_allocated_get(chunk,
1839 run_ind-1) == 0 && arena_mapbits_dirty_get(chunk, run_ind-1) ==
1840 flag_dirty && arena_mapbits_decommitted_get(chunk, run_ind-1) ==
1841 flag_decommitted) {
1842 size_t prun_size = arena_mapbits_unallocated_size_get(chunk,
1843 run_ind-1);
1844 size_t prun_pages = prun_size >> LG_PAGE;
1845
1846 run_ind -= prun_pages;
1847
1848 /*
1849 * Remove predecessor from runs_avail; the coalesced run is
1850 * inserted later.
1851 */
1852 assert(arena_mapbits_unallocated_size_get(chunk, run_ind) ==
1853 prun_size);
1854 assert(arena_mapbits_dirty_get(chunk, run_ind) == flag_dirty);
1855 assert(arena_mapbits_decommitted_get(chunk, run_ind) ==
1856 flag_decommitted);
1857 arena_avail_remove(arena, chunk, run_ind, prun_pages);
1858
1859 /*
1860 * If the predecessor is dirty, remove it from the set of dirty
1861 * pages.
1862 */
1863 if (flag_dirty != 0) {
1864 arena_run_dirty_remove(arena, chunk, run_ind,
1865 prun_pages);
1866 }
1867
1868 size += prun_size;
1869 run_pages += prun_pages;
1870
1871 arena_mapbits_unallocated_size_set(chunk, run_ind, size);
1872 arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1,
1873 size);
1874 }
1875
1876 *p_size = size;
1877 *p_run_ind = run_ind;
1878 *p_run_pages = run_pages;
1879 }
1880
1881 static size_t
1882 arena_run_size_get(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
1883 size_t run_ind)
1884 {
1885 size_t size;
1886
1887 assert(run_ind >= map_bias);
1888 assert(run_ind < chunk_npages);
1889
1890 if (arena_mapbits_large_get(chunk, run_ind) != 0) {
1891 size = arena_mapbits_large_size_get(chunk, run_ind);
1892 assert(size == PAGE || arena_mapbits_large_size_get(chunk,
1893 run_ind+(size>>LG_PAGE)-1) == 0);
1894 } else {
1895 arena_bin_info_t *bin_info = &arena_bin_info[run->binind];
1896 size = bin_info->run_size;
1897 }
1898
1899 return (size);
1900 }
1901
1902 static void
1903 arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty, bool cleaned,
1904 bool decommitted)
1905 {
1906 arena_chunk_t *chunk;
1907 arena_chunk_map_misc_t *miscelm;
1908 size_t size, run_ind, run_pages, flag_dirty, flag_decommitted;
1909
1910 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1911 miscelm = arena_run_to_miscelm(run);
1912 run_ind = arena_miscelm_to_pageind(miscelm);
1913 assert(run_ind >= map_bias);
1914 assert(run_ind < chunk_npages);
1915 size = arena_run_size_get(arena, chunk, run, run_ind);
1916 run_pages = (size >> LG_PAGE);
1917 arena_nactive_sub(arena, run_pages);
1918
1919 /*
1920 * The run is dirty if the caller claims to have dirtied it, as well as
1921 * if it was already dirty before being allocated and the caller
1922 * doesn't claim to have cleaned it.
1923 */
1924 assert(arena_mapbits_dirty_get(chunk, run_ind) ==
1925 arena_mapbits_dirty_get(chunk, run_ind+run_pages-1));
1926 if (!cleaned && !decommitted && arena_mapbits_dirty_get(chunk, run_ind)
1927 != 0)
1928 dirty = true;
1929 flag_dirty = dirty ? CHUNK_MAP_DIRTY : 0;
1930 flag_decommitted = decommitted ? CHUNK_MAP_DECOMMITTED : 0;
1931
1932 /* Mark pages as unallocated in the chunk map. */
1933 if (dirty || decommitted) {
1934 size_t flags = flag_dirty | flag_decommitted;
1935 arena_mapbits_unallocated_set(chunk, run_ind, size, flags);
1936 arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size,
1937 flags);
1938 } else {
1939 arena_mapbits_unallocated_set(chunk, run_ind, size,
1940 arena_mapbits_unzeroed_get(chunk, run_ind));
1941 arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size,
1942 arena_mapbits_unzeroed_get(chunk, run_ind+run_pages-1));
1943 }
1944
1945 arena_run_coalesce(arena, chunk, &size, &run_ind, &run_pages,
1946 flag_dirty, flag_decommitted);
1947
1948 /* Insert into runs_avail, now that coalescing is complete. */
1949 assert(arena_mapbits_unallocated_size_get(chunk, run_ind) ==
1950 arena_mapbits_unallocated_size_get(chunk, run_ind+run_pages-1));
1951 assert(arena_mapbits_dirty_get(chunk, run_ind) ==
1952 arena_mapbits_dirty_get(chunk, run_ind+run_pages-1));
1953 assert(arena_mapbits_decommitted_get(chunk, run_ind) ==
1954 arena_mapbits_decommitted_get(chunk, run_ind+run_pages-1));
1955 arena_avail_insert(arena, chunk, run_ind, run_pages);
1956
1957 if (dirty)
1958 arena_run_dirty_insert(arena, chunk, run_ind, run_pages);
1959
1960 /* Deallocate chunk if it is now completely unused. */
1961 if (size == arena_maxrun) {
1962 assert(run_ind == map_bias);
1963 assert(run_pages == (arena_maxrun >> LG_PAGE));
1964 arena_chunk_dalloc(arena, chunk);
1965 }
1966
1967 /*
1968 * It is okay to do dirty page processing here even if the chunk was
1969 * deallocated above, since in that case it is the spare. Waiting
1970 * until after possible chunk deallocation to do dirty processing
1971 * allows for an old spare to be fully deallocated, thus decreasing the
1972 * chances of spuriously crossing the dirty page purging threshold.
1973 */
1974 if (dirty)
1975 arena_maybe_purge(arena);
1976 }
1977
1978 static void
1979 arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
1980 size_t oldsize, size_t newsize)
1981 {
1982 arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run);
1983 size_t pageind = arena_miscelm_to_pageind(miscelm);
1984 size_t head_npages = (oldsize - newsize) >> LG_PAGE;
1985 size_t flag_dirty = arena_mapbits_dirty_get(chunk, pageind);
1986 size_t flag_decommitted = arena_mapbits_decommitted_get(chunk, pageind);
1987 size_t flag_unzeroed_mask = (flag_dirty | flag_decommitted) == 0 ?
1988 CHUNK_MAP_UNZEROED : 0;
1989
1990 assert(oldsize > newsize);
1991
1992 /*
1993 * Update the chunk map so that arena_run_dalloc() can treat the
1994 * leading run as separately allocated. Set the last element of each
1995 * run first, in case of single-page runs.
1996 */
1997 assert(arena_mapbits_large_size_get(chunk, pageind) == oldsize);
1998 arena_mapbits_large_set(chunk, pageind+head_npages-1, 0, flag_dirty |
1999 (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
2000 pageind+head_npages-1)));
2001 arena_mapbits_large_set(chunk, pageind, oldsize-newsize, flag_dirty |
2002 (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, pageind)));
2003
2004 if (config_debug) {
2005 UNUSED size_t tail_npages = newsize >> LG_PAGE;
2006 assert(arena_mapbits_large_size_get(chunk,
2007 pageind+head_npages+tail_npages-1) == 0);
2008 assert(arena_mapbits_dirty_get(chunk,
2009 pageind+head_npages+tail_npages-1) == flag_dirty);
2010 }
2011 arena_mapbits_large_set(chunk, pageind+head_npages, newsize,
2012 flag_dirty | (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
2013 pageind+head_npages)));
2014
2015 arena_run_dalloc(arena, run, false, false, (flag_decommitted != 0));
2016 }
2017
2018 static void
2019 arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
2020 size_t oldsize, size_t newsize, bool dirty)
2021 {
2022 arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run);
2023 size_t pageind = arena_miscelm_to_pageind(miscelm);
2024 size_t head_npages = newsize >> LG_PAGE;
2025 size_t flag_dirty = arena_mapbits_dirty_get(chunk, pageind);
2026 size_t flag_decommitted = arena_mapbits_decommitted_get(chunk, pageind);
2027 size_t flag_unzeroed_mask = (flag_dirty | flag_decommitted) == 0 ?
2028 CHUNK_MAP_UNZEROED : 0;
2029 arena_chunk_map_misc_t *tail_miscelm;
2030 arena_run_t *tail_run;
2031
2032 assert(oldsize > newsize);
2033
2034 /*
2035 * Update the chunk map so that arena_run_dalloc() can treat the
2036 * trailing run as separately allocated. Set the last element of each
2037 * run first, in case of single-page runs.
2038 */
2039 assert(arena_mapbits_large_size_get(chunk, pageind) == oldsize);
2040 arena_mapbits_large_set(chunk, pageind+head_npages-1, 0, flag_dirty |
2041 (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
2042 pageind+head_npages-1)));
2043 arena_mapbits_large_set(chunk, pageind, newsize, flag_dirty |
2044 (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, pageind)));
2045
2046 if (config_debug) {
2047 UNUSED size_t tail_npages = (oldsize - newsize) >> LG_PAGE;
2048 assert(arena_mapbits_large_size_get(chunk,
2049 pageind+head_npages+tail_npages-1) == 0);
2050 assert(arena_mapbits_dirty_get(chunk,
2051 pageind+head_npages+tail_npages-1) == flag_dirty);
2052 }
2053 arena_mapbits_large_set(chunk, pageind+head_npages, oldsize-newsize,
2054 flag_dirty | (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
2055 pageind+head_npages)));
2056
2057 tail_miscelm = arena_miscelm_get(chunk, pageind + head_npages);
2058 tail_run = &tail_miscelm->run;
2059 arena_run_dalloc(arena, tail_run, dirty, false, (flag_decommitted !=
2060 0));
2061 }
2062
2063 static arena_run_t *
2064 arena_bin_runs_first(arena_bin_t *bin)
2065 {
2066 arena_chunk_map_misc_t *miscelm = arena_run_tree_first(&bin->runs);
2067 if (miscelm != NULL)
2068 return (&miscelm->run);
2069
2070 return (NULL);
2071 }
2072
2073 static void
2074 arena_bin_runs_insert(arena_bin_t *bin, arena_run_t *run)
2075 {
2076 arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run);
2077
2078 assert(arena_run_tree_search(&bin->runs, miscelm) == NULL);
2079
2080 arena_run_tree_insert(&bin->runs, miscelm);
2081 }
2082
2083 static void
2084 arena_bin_runs_remove(arena_bin_t *bin, arena_run_t *run)
2085 {
2086 arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run);
2087
2088 assert(arena_run_tree_search(&bin->runs, miscelm) != NULL);
2089
2090 arena_run_tree_remove(&bin->runs, miscelm);
2091 }
2092
2093 static arena_run_t *
2094 arena_bin_nonfull_run_tryget(arena_bin_t *bin)
2095 {
2096 arena_run_t *run = arena_bin_runs_first(bin);
2097 if (run != NULL) {
2098 arena_bin_runs_remove(bin, run);
2099 if (config_stats)
2100 bin->stats.reruns++;
2101 }
2102 return (run);
2103 }
2104
2105 static arena_run_t *
2106 arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
2107 {
2108 arena_run_t *run;
2109 szind_t binind;
2110 arena_bin_info_t *bin_info;
2111
2112 /* Look for a usable run. */
2113 run = arena_bin_nonfull_run_tryget(bin);
2114 if (run != NULL)
2115 return (run);
2116 /* No existing runs have any space available. */
2117
2118 binind = arena_bin_index(arena, bin);
2119 bin_info = &arena_bin_info[binind];
2120
2121 /* Allocate a new run. */
2122 malloc_mutex_unlock(&bin->lock);
2123 /******************************/
2124 malloc_mutex_lock(&arena->lock);
2125 run = arena_run_alloc_small(arena, bin_info->run_size, binind);
2126 if (run != NULL) {
2127 /* Initialize run internals. */
2128 run->binind = binind;
2129 run->nfree = bin_info->nregs;
2130 bitmap_init(run->bitmap, &bin_info->bitmap_info);
2131 }
2132 malloc_mutex_unlock(&arena->lock);
2133 /********************************/
2134 malloc_mutex_lock(&bin->lock);
2135 if (run != NULL) {
2136 if (config_stats) {
2137 bin->stats.nruns++;
2138 bin->stats.curruns++;
2139 }
2140 return (run);
2141 }
2142
2143 /*
2144 * arena_run_alloc_small() failed, but another thread may have made
2145 * sufficient memory available while this one dropped bin->lock above,
2146 * so search one more time.
2147 */
2148 run = arena_bin_nonfull_run_tryget(bin);
2149 if (run != NULL)
2150 return (run);
2151
2152 return (NULL);
2153 }
2154
2155 /* Re-fill bin->runcur, then call arena_run_reg_alloc(). */
2156 static void *
2157 arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
2158 {
2159 szind_t binind;
2160 arena_bin_info_t *bin_info;
2161 arena_run_t *run;
2162
2163 binind = arena_bin_index(arena, bin);
2164 bin_info = &arena_bin_info[binind];
2165 bin->runcur = NULL;
2166 run = arena_bin_nonfull_run_get(arena, bin);
2167 if (bin->runcur != NULL && bin->runcur->nfree > 0) {
2168 /*
2169 * Another thread updated runcur while this one ran without the
2170 * bin lock in arena_bin_nonfull_run_get().
2171 */
2172 void *ret;
2173 assert(bin->runcur->nfree > 0);
2174 ret = arena_run_reg_alloc(bin->runcur, bin_info);
2175 if (run != NULL) {
2176 arena_chunk_t *chunk;
2177
2178 /*
2179 * arena_run_alloc_small() may have allocated run, or
2180 * it may have pulled run from the bin's run tree.
2181 * Therefore it is unsafe to make any assumptions about
2182 * how run has previously been used, and
2183 * arena_bin_lower_run() must be called, as if a region
2184 * were just deallocated from the run.
2185 */
2186 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
2187 if (run->nfree == bin_info->nregs)
2188 arena_dalloc_bin_run(arena, chunk, run, bin);
2189 else
2190 arena_bin_lower_run(arena, chunk, run, bin);
2191 }
2192 return (ret);
2193 }
2194
2195 if (run == NULL)
2196 return (NULL);
2197
2198 bin->runcur = run;
2199
2200 assert(bin->runcur->nfree > 0);
2201
2202 return (arena_run_reg_alloc(bin->runcur, bin_info));
2203 }
2204
2205 void
2206 arena_tcache_fill_small(tsd_t *tsd, arena_t *arena, tcache_bin_t *tbin,
2207 szind_t binind, uint64_t prof_accumbytes)
2208 {
2209 unsigned i, nfill;
2210 arena_bin_t *bin;
2211
2212 assert(tbin->ncached == 0);
2213
2214 if (config_prof && arena_prof_accum(arena, prof_accumbytes))
2215 prof_idump();
2216 bin = &arena->bins[binind];
2217 malloc_mutex_lock(&bin->lock);
2218 for (i = 0, nfill = (tcache_bin_info[binind].ncached_max >>
2219 tbin->lg_fill_div); i < nfill; i++) {
2220 arena_run_t *run;
2221 void *ptr;
2222 if ((run = bin->runcur) != NULL && run->nfree > 0)
2223 ptr = arena_run_reg_alloc(run, &arena_bin_info[binind]);
2224 else
2225 ptr = arena_bin_malloc_hard(arena, bin);
2226 if (ptr == NULL) {
2227 /*
2228 * OOM. tbin->avail isn't yet filled down to its first
2229 * element, so the successful allocations (if any) must
2230 * be moved just before tbin->avail before bailing out.
2231 */
2232 if (i > 0) {
2233 memmove(tbin->avail - i, tbin->avail - nfill,
2234 i * sizeof(void *));
2235 }
2236 break;
2237 }
2238 if (config_fill && unlikely(opt_junk_alloc)) {
2239 arena_alloc_junk_small(ptr, &arena_bin_info[binind],
2240 true);
2241 }
2242 /* Insert such that low regions get used first. */
2243 *(tbin->avail - nfill + i) = ptr;
2244 }
2245 if (config_stats) {
2246 bin->stats.nmalloc += i;
2247 bin->stats.nrequests += tbin->tstats.nrequests;
2248 bin->stats.curregs += i;
2249 bin->stats.nfills++;
2250 tbin->tstats.nrequests = 0;
2251 }
2252 malloc_mutex_unlock(&bin->lock);
2253 tbin->ncached = i;
2254 arena_decay_tick(tsd, arena);
2255 }
2256
2257 void
2258 arena_alloc_junk_small(void *ptr, arena_bin_info_t *bin_info, bool zero)
2259 {
2260
2261 if (zero) {
2262 size_t redzone_size = bin_info->redzone_size;
2263 memset((void *)((uintptr_t)ptr - redzone_size), 0xa5,
2264 redzone_size);
2265 memset((void *)((uintptr_t)ptr + bin_info->reg_size), 0xa5,
2266 redzone_size);
2267 } else {
2268 memset((void *)((uintptr_t)ptr - bin_info->redzone_size), 0xa5,
2269 bin_info->reg_interval);
2270 }
2271 }
2272
2273 #ifdef JEMALLOC_JET
2274 #undef arena_redzone_corruption
2275 #define arena_redzone_corruption JEMALLOC_N(arena_redzone_corruption_impl)
2276 #endif
2277 static void
2278 arena_redzone_corruption(void *ptr, size_t usize, bool after,
2279 size_t offset, uint8_t byte)
2280 {
2281
2282 malloc_printf("<jemalloc>: Corrupt redzone %zu byte%s %s %p "
2283 "(size %zu), byte=%#x\n", offset, (offset == 1) ? "" : "s",
2284 after ? "after" : "before", ptr, usize, byte);
2285 }
2286 #ifdef JEMALLOC_JET
2287 #undef arena_redzone_corruption
2288 #define arena_redzone_corruption JEMALLOC_N(arena_redzone_corruption)
2289 arena_redzone_corruption_t *arena_redzone_corruption =
2290 JEMALLOC_N(arena_redzone_corruption_impl);
2291 #endif
2292
2293 static void
2294 arena_redzones_validate(void *ptr, arena_bin_info_t *bin_info, bool reset)
2295 {
2296 bool error = false;
2297
2298 if (opt_junk_alloc) {
2299 size_t size = bin_info->reg_size;
2300 size_t redzone_size = bin_info->redzone_size;
2301 size_t i;
2302
2303 for (i = 1; i <= redzone_size; i++) {
2304 uint8_t *byte = (uint8_t *)((uintptr_t)ptr - i);
2305 if (*byte != 0xa5) {
2306 error = true;
2307 arena_redzone_corruption(ptr, size, false, i,
2308 *byte);
2309 if (reset)
2310 *byte = 0xa5;
2311 }
2312 }
2313 for (i = 0; i < redzone_size; i++) {
2314 uint8_t *byte = (uint8_t *)((uintptr_t)ptr + size + i);
2315 if (*byte != 0xa5) {
2316 error = true;
2317 arena_redzone_corruption(ptr, size, true, i,
2318 *byte);
2319 if (reset)
2320 *byte = 0xa5;
2321 }
2322 }
2323 }
2324
2325 if (opt_abort && error)
2326 abort();
2327 }
2328
2329 #ifdef JEMALLOC_JET
2330 #undef arena_dalloc_junk_small
2331 #define arena_dalloc_junk_small JEMALLOC_N(arena_dalloc_junk_small_impl)
2332 #endif
2333 void
2334 arena_dalloc_junk_small(void *ptr, arena_bin_info_t *bin_info)
2335 {
2336 size_t redzone_size = bin_info->redzone_size;
2337
2338 arena_redzones_validate(ptr, bin_info, false);
2339 memset((void *)((uintptr_t)ptr - redzone_size), 0x5a,
2340 bin_info->reg_interval);
2341 }
2342 #ifdef JEMALLOC_JET
2343 #undef arena_dalloc_junk_small
2344 #define arena_dalloc_junk_small JEMALLOC_N(arena_dalloc_junk_small)
2345 arena_dalloc_junk_small_t *arena_dalloc_junk_small =
2346 JEMALLOC_N(arena_dalloc_junk_small_impl);
2347 #endif
2348
2349 void
2350 arena_quarantine_junk_small(void *ptr, size_t usize)
2351 {
2352 szind_t binind;
2353 arena_bin_info_t *bin_info;
2354 cassert(config_fill);
2355 assert(opt_junk_free);
2356 assert(opt_quarantine);
2357 assert(usize <= SMALL_MAXCLASS);
2358
2359 binind = size2index(usize);
2360 bin_info = &arena_bin_info[binind];
2361 arena_redzones_validate(ptr, bin_info, true);
2362 }
2363
2364 static void *
2365 arena_malloc_small(tsd_t *tsd, arena_t *arena, szind_t binind, bool zero)
2366 {
2367 void *ret;
2368 arena_bin_t *bin;
2369 size_t usize;
2370 arena_run_t *run;
2371
2372 assert(binind < NBINS);
2373 bin = &arena->bins[binind];
2374 usize = index2size(binind);
2375
2376 malloc_mutex_lock(&bin->lock);
2377 if ((run = bin->runcur) != NULL && run->nfree > 0)
2378 ret = arena_run_reg_alloc(run, &arena_bin_info[binind]);
2379 else
2380 ret = arena_bin_malloc_hard(arena, bin);
2381
2382 if (ret == NULL) {
2383 malloc_mutex_unlock(&bin->lock);
2384 return (NULL);
2385 }
2386
2387 if (config_stats) {
2388 bin->stats.nmalloc++;
2389 bin->stats.nrequests++;
2390 bin->stats.curregs++;
2391 }
2392 malloc_mutex_unlock(&bin->lock);
2393 if (config_prof && !isthreaded && arena_prof_accum(arena, usize))
2394 prof_idump();
2395
2396 if (!zero) {
2397 if (config_fill) {
2398 if (unlikely(opt_junk_alloc)) {
2399 arena_alloc_junk_small(ret,
2400 &arena_bin_info[binind], false);
2401 } else if (unlikely(opt_zero))
2402 memset(ret, 0, usize);
2403 }
2404 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, usize);
2405 } else {
2406 if (config_fill && unlikely(opt_junk_alloc)) {
2407 arena_alloc_junk_small(ret, &arena_bin_info[binind],
2408 true);
2409 }
2410 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, usize);
2411 memset(ret, 0, usize);
2412 }
2413
2414 arena_decay_tick(tsd, arena);
2415 return (ret);
2416 }
2417
2418 void *
2419 arena_malloc_large(tsd_t *tsd, arena_t *arena, szind_t binind, bool zero)
2420 {
2421 void *ret;
2422 size_t usize;
2423 uintptr_t random_offset;
2424 arena_run_t *run;
2425 arena_chunk_map_misc_t *miscelm;
2426 UNUSED bool idump JEMALLOC_CC_SILENCE_INIT(false);
2427
2428 /* Large allocation. */
2429 usize = index2size(binind);
2430 malloc_mutex_lock(&arena->lock);
2431 if (config_cache_oblivious) {
2432 uint64_t r;
2433
2434 /*
2435 * Compute a uniformly distributed offset within the first page
2436 * that is a multiple of the cacheline size, e.g. [0 .. 63) * 64
2437 * for 4 KiB pages and 64-byte cachelines.
2438 */
2439 r = prng_lg_range(&arena->offset_state, LG_PAGE - LG_CACHELINE);
2440 random_offset = ((uintptr_t)r) << LG_CACHELINE;
2441 } else
2442 random_offset = 0;
2443 run = arena_run_alloc_large(arena, usize + large_pad, zero);
2444 if (run == NULL) {
2445 malloc_mutex_unlock(&arena->lock);
2446 return (NULL);
2447 }
2448 miscelm = arena_run_to_miscelm(run);
2449 ret = (void *)((uintptr_t)arena_miscelm_to_rpages(miscelm) +
2450 random_offset);
2451 if (config_stats) {
2452 szind_t index = binind - NBINS;
2453
2454 arena->stats.nmalloc_large++;
2455 arena->stats.nrequests_large++;
2456 arena->stats.allocated_large += usize;
2457 arena->stats.lstats[index].nmalloc++;
2458 arena->stats.lstats[index].nrequests++;
2459 arena->stats.lstats[index].curruns++;
2460 }
2461 if (config_prof)
2462 idump = arena_prof_accum_locked(arena, usize);
2463 malloc_mutex_unlock(&arena->lock);
2464 if (config_prof && idump)
2465 prof_idump();
2466
2467 if (!zero) {
2468 if (config_fill) {
2469 if (unlikely(opt_junk_alloc))
2470 memset(ret, 0xa5, usize);
2471 else if (unlikely(opt_zero))
2472 memset(ret, 0, usize);
2473 }
2474 }
2475
2476 arena_decay_tick(tsd, arena);
2477 return (ret);
2478 }
2479
2480 void *
2481 arena_malloc_hard(tsd_t *tsd, arena_t *arena, size_t size, szind_t ind,
2482 bool zero, tcache_t *tcache)
2483 {
2484
2485 arena = arena_choose(tsd, arena);
2486 if (unlikely(arena == NULL))
2487 return (NULL);
2488
2489 if (likely(size <= SMALL_MAXCLASS))
2490 return (arena_malloc_small(tsd, arena, ind, zero));
2491 if (likely(size <= large_maxclass))
2492 return (arena_malloc_large(tsd, arena, ind, zero));
2493 return (huge_malloc(tsd, arena, index2size(ind), zero, tcache));
2494 }
2495
2496 /* Only handles large allocations that require more than page alignment. */
2497 static void *
2498 arena_palloc_large(tsd_t *tsd, arena_t *arena, size_t usize, size_t alignment,
2499 bool zero)
2500 {
2501 void *ret;
2502 size_t alloc_size, leadsize, trailsize;
2503 arena_run_t *run;
2504 arena_chunk_t *chunk;
2505 arena_chunk_map_misc_t *miscelm;
2506 void *rpages;
2507
2508 assert(usize == PAGE_CEILING(usize));
2509
2510 arena = arena_choose(tsd, arena);
2511 if (unlikely(arena == NULL))
2512 return (NULL);
2513
2514 alignment = PAGE_CEILING(alignment);
2515 alloc_size = usize + large_pad + alignment - PAGE;
2516
2517 malloc_mutex_lock(&arena->lock);
2518 run = arena_run_alloc_large(arena, alloc_size, false);
2519 if (run == NULL) {
2520 malloc_mutex_unlock(&arena->lock);
2521 return (NULL);
2522 }
2523 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
2524 miscelm = arena_run_to_miscelm(run);
2525 rpages = arena_miscelm_to_rpages(miscelm);
2526
2527 leadsize = ALIGNMENT_CEILING((uintptr_t)rpages, alignment) -
2528 (uintptr_t)rpages;
2529 assert(alloc_size >= leadsize + usize);
2530 trailsize = alloc_size - leadsize - usize - large_pad;
2531 if (leadsize != 0) {
2532 arena_chunk_map_misc_t *head_miscelm = miscelm;
2533 arena_run_t *head_run = run;
2534
2535 miscelm = arena_miscelm_get(chunk,
2536 arena_miscelm_to_pageind(head_miscelm) + (leadsize >>
2537 LG_PAGE));
2538 run = &miscelm->run;
2539
2540 arena_run_trim_head(arena, chunk, head_run, alloc_size,
2541 alloc_size - leadsize);
2542 }
2543 if (trailsize != 0) {
2544 arena_run_trim_tail(arena, chunk, run, usize + large_pad +
2545 trailsize, usize + large_pad, false);
2546 }
2547 if (arena_run_init_large(arena, run, usize + large_pad, zero)) {
2548 size_t run_ind =
2549 arena_miscelm_to_pageind(arena_run_to_miscelm(run));
2550 bool dirty = (arena_mapbits_dirty_get(chunk, run_ind) != 0);
2551 bool decommitted = (arena_mapbits_decommitted_get(chunk,
2552 run_ind) != 0);
2553
2554 assert(decommitted); /* Cause of OOM. */
2555 arena_run_dalloc(arena, run, dirty, false, decommitted);
2556 malloc_mutex_unlock(&arena->lock);
2557 return (NULL);
2558 }
2559 ret = arena_miscelm_to_rpages(miscelm);
2560
2561 if (config_stats) {
2562 szind_t index = size2index(usize) - NBINS;
2563
2564 arena->stats.nmalloc_large++;
2565 arena->stats.nrequests_large++;
2566 arena->stats.allocated_large += usize;
2567 arena->stats.lstats[index].nmalloc++;
2568 arena->stats.lstats[index].nrequests++;
2569 arena->stats.lstats[index].curruns++;
2570 }
2571 malloc_mutex_unlock(&arena->lock);
2572
2573 if (config_fill && !zero) {
2574 if (unlikely(opt_junk_alloc))
2575 memset(ret, 0xa5, usize);
2576 else if (unlikely(opt_zero))
2577 memset(ret, 0, usize);
2578 }
2579 arena_decay_tick(tsd, arena);
2580 return (ret);
2581 }
2582
2583 void *
2584 arena_palloc(tsd_t *tsd, arena_t *arena, size_t usize, size_t alignment,
2585 bool zero, tcache_t *tcache)
2586 {
2587 void *ret;
2588
2589 if (usize <= SMALL_MAXCLASS && (alignment < PAGE || (alignment == PAGE
2590 && (usize & PAGE_MASK) == 0))) {
2591 /* Small; alignment doesn't require special run placement. */
2592 ret = arena_malloc(tsd, arena, usize, size2index(usize), zero,
2593 tcache, true);
2594 } else if (usize <= large_maxclass && alignment <= PAGE) {
2595 /*
2596 * Large; alignment doesn't require special run placement.
2597 * However, the cached pointer may be at a random offset from
2598 * the base of the run, so do some bit manipulation to retrieve
2599 * the base.
2600 */
2601 ret = arena_malloc(tsd, arena, usize, size2index(usize), zero,
2602 tcache, true);
2603 if (config_cache_oblivious)
2604 ret = (void *)((uintptr_t)ret & ~PAGE_MASK);
2605 } else {
2606 if (likely(usize <= large_maxclass)) {
2607 ret = arena_palloc_large(tsd, arena, usize, alignment,
2608 zero);
2609 } else if (likely(alignment <= chunksize))
2610 ret = huge_malloc(tsd, arena, usize, zero, tcache);
2611 else {
2612 ret = huge_palloc(tsd, arena, usize, alignment, zero,
2613 tcache);
2614 }
2615 }
2616 return (ret);
2617 }
2618
2619 void
2620 arena_prof_promoted(const void *ptr, size_t size)
2621 {
2622 arena_chunk_t *chunk;
2623 size_t pageind;
2624 szind_t binind;
2625
2626 cassert(config_prof);
2627 assert(ptr != NULL);
2628 assert(CHUNK_ADDR2BASE(ptr) != ptr);
2629 assert(isalloc(ptr, false) == LARGE_MINCLASS);
2630 assert(isalloc(ptr, true) == LARGE_MINCLASS);
2631 assert(size <= SMALL_MAXCLASS);
2632
2633 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2634 pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
2635 binind = size2index(size);
2636 assert(binind < NBINS);
2637 arena_mapbits_large_binind_set(chunk, pageind, binind);
2638
2639 assert(isalloc(ptr, false) == LARGE_MINCLASS);
2640 assert(isalloc(ptr, true) == size);
2641 }
2642
2643 static void
2644 arena_dissociate_bin_run(arena_chunk_t *chunk, arena_run_t *run,
2645 arena_bin_t *bin)
2646 {
2647
2648 /* Dissociate run from bin. */
2649 if (run == bin->runcur)
2650 bin->runcur = NULL;
2651 else {
2652 szind_t binind = arena_bin_index(extent_node_arena_get(
2653 &chunk->node), bin);
2654 arena_bin_info_t *bin_info = &arena_bin_info[binind];
2655
2656 if (bin_info->nregs != 1) {
2657 /*
2658 * This block's conditional is necessary because if the
2659 * run only contains one region, then it never gets
2660 * inserted into the non-full runs tree.
2661 */
2662 arena_bin_runs_remove(bin, run);
2663 }
2664 }
2665 }
2666
2667 static void
2668 arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
2669 arena_bin_t *bin)
2670 {
2671
2672 assert(run != bin->runcur);
2673 assert(arena_run_tree_search(&bin->runs, arena_run_to_miscelm(run)) ==
2674 NULL);
2675
2676 malloc_mutex_unlock(&bin->lock);
2677 /******************************/
2678 malloc_mutex_lock(&arena->lock);
2679 arena_run_dalloc(arena, run, true, false, false);
2680 malloc_mutex_unlock(&arena->lock);
2681 /****************************/
2682 malloc_mutex_lock(&bin->lock);
2683 if (config_stats)
2684 bin->stats.curruns--;
2685 }
2686
2687 static void
2688 arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
2689 arena_bin_t *bin)
2690 {
2691
2692 /*
2693 * Make sure that if bin->runcur is non-NULL, it refers to the lowest
2694 * non-full run. It is okay to NULL runcur out rather than proactively
2695 * keeping it pointing at the lowest non-full run.
2696 */
2697 if ((uintptr_t)run < (uintptr_t)bin->runcur) {
2698 /* Switch runcur. */
2699 if (bin->runcur->nfree > 0)
2700 arena_bin_runs_insert(bin, bin->runcur);
2701 bin->runcur = run;
2702 if (config_stats)
2703 bin->stats.reruns++;
2704 } else
2705 arena_bin_runs_insert(bin, run);
2706 }
2707
2708 static void
2709 arena_dalloc_bin_locked_impl(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2710 arena_chunk_map_bits_t *bitselm, bool junked)
2711 {
2712 size_t pageind, rpages_ind;
2713 arena_run_t *run;
2714 arena_bin_t *bin;
2715 arena_bin_info_t *bin_info;
2716 szind_t binind;
2717
2718 pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
2719 rpages_ind = pageind - arena_mapbits_small_runind_get(chunk, pageind);
2720 run = &arena_miscelm_get(chunk, rpages_ind)->run;
2721 binind = run->binind;
2722 bin = &arena->bins[binind];
2723 bin_info = &arena_bin_info[binind];
2724
2725 if (!junked && config_fill && unlikely(opt_junk_free))
2726 arena_dalloc_junk_small(ptr, bin_info);
2727
2728 arena_run_reg_dalloc(run, ptr);
2729 if (run->nfree == bin_info->nregs) {
2730 arena_dissociate_bin_run(chunk, run, bin);
2731 arena_dalloc_bin_run(arena, chunk, run, bin);
2732 } else if (run->nfree == 1 && run != bin->runcur)
2733 arena_bin_lower_run(arena, chunk, run, bin);
2734
2735 if (config_stats) {
2736 bin->stats.ndalloc++;
2737 bin->stats.curregs--;
2738 }
2739 }
2740
2741 void
2742 arena_dalloc_bin_junked_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2743 arena_chunk_map_bits_t *bitselm)
2744 {
2745
2746 arena_dalloc_bin_locked_impl(arena, chunk, ptr, bitselm, true);
2747 }
2748
2749 void
2750 arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2751 size_t pageind, arena_chunk_map_bits_t *bitselm)
2752 {
2753 arena_run_t *run;
2754 arena_bin_t *bin;
2755 size_t rpages_ind;
2756
2757 rpages_ind = pageind - arena_mapbits_small_runind_get(chunk, pageind);
2758 run = &arena_miscelm_get(chunk, rpages_ind)->run;
2759 bin = &arena->bins[run->binind];
2760 malloc_mutex_lock(&bin->lock);
2761 arena_dalloc_bin_locked_impl(arena, chunk, ptr, bitselm, false);
2762 malloc_mutex_unlock(&bin->lock);
2763 }
2764
2765 void
2766 arena_dalloc_small(tsd_t *tsd, arena_t *arena, arena_chunk_t *chunk, void *ptr,
2767 size_t pageind)
2768 {
2769 arena_chunk_map_bits_t *bitselm;
2770
2771 if (config_debug) {
2772 /* arena_ptr_small_binind_get() does extra sanity checking. */
2773 assert(arena_ptr_small_binind_get(ptr, arena_mapbits_get(chunk,
2774 pageind)) != BININD_INVALID);
2775 }
2776 bitselm = arena_bitselm_get(chunk, pageind);
2777 arena_dalloc_bin(arena, chunk, ptr, pageind, bitselm);
2778 arena_decay_tick(tsd, arena);
2779 }
2780
2781 #ifdef JEMALLOC_JET
2782 #undef arena_dalloc_junk_large
2783 #define arena_dalloc_junk_large JEMALLOC_N(arena_dalloc_junk_large_impl)
2784 #endif
2785 void
2786 arena_dalloc_junk_large(void *ptr, size_t usize)
2787 {
2788
2789 if (config_fill && unlikely(opt_junk_free))
2790 memset(ptr, 0x5a, usize);
2791 }
2792 #ifdef JEMALLOC_JET
2793 #undef arena_dalloc_junk_large
2794 #define arena_dalloc_junk_large JEMALLOC_N(arena_dalloc_junk_large)
2795 arena_dalloc_junk_large_t *arena_dalloc_junk_large =
2796 JEMALLOC_N(arena_dalloc_junk_large_impl);
2797 #endif
2798
2799 static void
2800 arena_dalloc_large_locked_impl(arena_t *arena, arena_chunk_t *chunk,
2801 void *ptr, bool junked)
2802 {
2803 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
2804 arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind);
2805 arena_run_t *run = &miscelm->run;
2806
2807 if (config_fill || config_stats) {
2808 size_t usize = arena_mapbits_large_size_get(chunk, pageind) -
2809 large_pad;
2810
2811 if (!junked)
2812 arena_dalloc_junk_large(ptr, usize);
2813 if (config_stats) {
2814 szind_t index = size2index(usize) - NBINS;
2815
2816 arena->stats.ndalloc_large++;
2817 arena->stats.allocated_large -= usize;
2818 arena->stats.lstats[index].ndalloc++;
2819 arena->stats.lstats[index].curruns--;
2820 }
2821 }
2822
2823 arena_run_dalloc(arena, run, true, false, false);
2824 }
2825
2826 void
2827 arena_dalloc_large_junked_locked(arena_t *arena, arena_chunk_t *chunk,
2828 void *ptr)
2829 {
2830
2831 arena_dalloc_large_locked_impl(arena, chunk, ptr, true);
2832 }
2833
2834 void
2835 arena_dalloc_large(tsd_t *tsd, arena_t *arena, arena_chunk_t *chunk, void *ptr)
2836 {
2837
2838 malloc_mutex_lock(&arena->lock);
2839 arena_dalloc_large_locked_impl(arena, chunk, ptr, false);
2840 malloc_mutex_unlock(&arena->lock);
2841 arena_decay_tick(tsd, arena);
2842 }
2843
2844 static void
2845 arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2846 size_t oldsize, size_t size)
2847 {
2848 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
2849 arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind);
2850 arena_run_t *run = &miscelm->run;
2851
2852 assert(size < oldsize);
2853
2854 /*
2855 * Shrink the run, and make trailing pages available for other
2856 * allocations.
2857 */
2858 malloc_mutex_lock(&arena->lock);
2859 arena_run_trim_tail(arena, chunk, run, oldsize + large_pad, size +
2860 large_pad, true);
2861 if (config_stats) {
2862 szind_t oldindex = size2index(oldsize) - NBINS;
2863 szind_t index = size2index(size) - NBINS;
2864
2865 arena->stats.ndalloc_large++;
2866 arena->stats.allocated_large -= oldsize;
2867 arena->stats.lstats[oldindex].ndalloc++;
2868 arena->stats.lstats[oldindex].curruns--;
2869
2870 arena->stats.nmalloc_large++;
2871 arena->stats.nrequests_large++;
2872 arena->stats.allocated_large += size;
2873 arena->stats.lstats[index].nmalloc++;
2874 arena->stats.lstats[index].nrequests++;
2875 arena->stats.lstats[index].curruns++;
2876 }
2877 malloc_mutex_unlock(&arena->lock);
2878 }
2879
2880 static bool
2881 arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2882 size_t oldsize, size_t usize_min, size_t usize_max, bool zero)
2883 {
2884 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
2885 size_t npages = (oldsize + large_pad) >> LG_PAGE;
2886 size_t followsize;
2887
2888 assert(oldsize == arena_mapbits_large_size_get(chunk, pageind) -
2889 large_pad);
2890
2891 /* Try to extend the run. */
2892 malloc_mutex_lock(&arena->lock);
2893 if (pageind+npages >= chunk_npages || arena_mapbits_allocated_get(chunk,
2894 pageind+npages) != 0)
2895 goto label_fail;
2896 followsize = arena_mapbits_unallocated_size_get(chunk, pageind+npages);
2897 if (oldsize + followsize >= usize_min) {
2898 /*
2899 * The next run is available and sufficiently large. Split the
2900 * following run, then merge the first part with the existing
2901 * allocation.
2902 */
2903 arena_run_t *run;
2904 size_t usize, splitsize, size, flag_dirty, flag_unzeroed_mask;
2905
2906 usize = usize_max;
2907 while (oldsize + followsize < usize)
2908 usize = index2size(size2index(usize)-1);
2909 assert(usize >= usize_min);
2910 assert(usize >= oldsize);
2911 splitsize = usize - oldsize;
2912 if (splitsize == 0)
2913 goto label_fail;
2914
2915 run = &arena_miscelm_get(chunk, pageind+npages)->run;
2916 if (arena_run_split_large(arena, run, splitsize, zero))
2917 goto label_fail;
2918
2919 if (config_cache_oblivious && zero) {
2920 /*
2921 * Zero the trailing bytes of the original allocation's
2922 * last page, since they are in an indeterminate state.
2923 * There will always be trailing bytes, because ptr's
2924 * offset from the beginning of the run is a multiple of
2925 * CACHELINE in [0 .. PAGE).
2926 */
2927 void *zbase = (void *)((uintptr_t)ptr + oldsize);
2928 void *zpast = PAGE_ADDR2BASE((void *)((uintptr_t)zbase +
2929 PAGE));
2930 size_t nzero = (uintptr_t)zpast - (uintptr_t)zbase;
2931 assert(nzero > 0);
2932 memset(zbase, 0, nzero);
2933 }
2934
2935 size = oldsize + splitsize;
2936 npages = (size + large_pad) >> LG_PAGE;
2937
2938 /*
2939 * Mark the extended run as dirty if either portion of the run
2940 * was dirty before allocation. This is rather pedantic,
2941 * because there's not actually any sequence of events that
2942 * could cause the resulting run to be passed to
2943 * arena_run_dalloc() with the dirty argument set to false
2944 * (which is when dirty flag consistency would really matter).
2945 */
2946 flag_dirty = arena_mapbits_dirty_get(chunk, pageind) |
2947 arena_mapbits_dirty_get(chunk, pageind+npages-1);
2948 flag_unzeroed_mask = flag_dirty == 0 ? CHUNK_MAP_UNZEROED : 0;
2949 arena_mapbits_large_set(chunk, pageind, size + large_pad,
2950 flag_dirty | (flag_unzeroed_mask &
2951 arena_mapbits_unzeroed_get(chunk, pageind)));
2952 arena_mapbits_large_set(chunk, pageind+npages-1, 0, flag_dirty |
2953 (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
2954 pageind+npages-1)));
2955
2956 if (config_stats) {
2957 szind_t oldindex = size2index(oldsize) - NBINS;
2958 szind_t index = size2index(size) - NBINS;
2959
2960 arena->stats.ndalloc_large++;
2961 arena->stats.allocated_large -= oldsize;
2962 arena->stats.lstats[oldindex].ndalloc++;
2963 arena->stats.lstats[oldindex].curruns--;
2964
2965 arena->stats.nmalloc_large++;
2966 arena->stats.nrequests_large++;
2967 arena->stats.allocated_large += size;
2968 arena->stats.lstats[index].nmalloc++;
2969 arena->stats.lstats[index].nrequests++;
2970 arena->stats.lstats[index].curruns++;
2971 }
2972 malloc_mutex_unlock(&arena->lock);
2973 return (false);
2974 }
2975 label_fail:
2976 malloc_mutex_unlock(&arena->lock);
2977 return (true);
2978 }
2979
2980 #ifdef JEMALLOC_JET
2981 #undef arena_ralloc_junk_large
2982 #define arena_ralloc_junk_large JEMALLOC_N(arena_ralloc_junk_large_impl)
2983 #endif
2984 static void
2985 arena_ralloc_junk_large(void *ptr, size_t old_usize, size_t usize)
2986 {
2987
2988 if (config_fill && unlikely(opt_junk_free)) {
2989 memset((void *)((uintptr_t)ptr + usize), 0x5a,
2990 old_usize - usize);
2991 }
2992 }
2993 #ifdef JEMALLOC_JET
2994 #undef arena_ralloc_junk_large
2995 #define arena_ralloc_junk_large JEMALLOC_N(arena_ralloc_junk_large)
2996 arena_ralloc_junk_large_t *arena_ralloc_junk_large =
2997 JEMALLOC_N(arena_ralloc_junk_large_impl);
2998 #endif
2999
3000 /*
3001 * Try to resize a large allocation, in order to avoid copying. This will
3002 * always fail if growing an object, and the following run is already in use.
3003 */
3004 static bool
3005 arena_ralloc_large(void *ptr, size_t oldsize, size_t usize_min,
3006 size_t usize_max, bool zero)
3007 {
3008 arena_chunk_t *chunk;
3009 arena_t *arena;
3010
3011 if (oldsize == usize_max) {
3012 /* Current size class is compatible and maximal. */
3013 return (false);
3014 }
3015
3016 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
3017 arena = extent_node_arena_get(&chunk->node);
3018
3019 if (oldsize < usize_max) {
3020 bool ret = arena_ralloc_large_grow(arena, chunk, ptr, oldsize,
3021 usize_min, usize_max, zero);
3022 if (config_fill && !ret && !zero) {
3023 if (unlikely(opt_junk_alloc)) {
3024 memset((void *)((uintptr_t)ptr + oldsize), 0xa5,
3025 isalloc(ptr, config_prof) - oldsize);
3026 } else if (unlikely(opt_zero)) {
3027 memset((void *)((uintptr_t)ptr + oldsize), 0,
3028 isalloc(ptr, config_prof) - oldsize);
3029 }
3030 }
3031 return (ret);
3032 }
3033
3034 assert(oldsize > usize_max);
3035 /* Fill before shrinking in order avoid a race. */
3036 arena_ralloc_junk_large(ptr, oldsize, usize_max);
3037 arena_ralloc_large_shrink(arena, chunk, ptr, oldsize, usize_max);
3038 return (false);
3039 }
3040
3041 bool
3042 arena_ralloc_no_move(tsd_t *tsd, void *ptr, size_t oldsize, size_t size,
3043 size_t extra, bool zero)
3044 {
3045 size_t usize_min, usize_max;
3046
3047 /* Calls with non-zero extra had to clamp extra. */
3048 assert(extra == 0 || size + extra <= HUGE_MAXCLASS);
3049
3050 if (unlikely(size > HUGE_MAXCLASS))
3051 return (true);
3052
3053 usize_min = s2u(size);
3054 usize_max = s2u(size + extra);
3055 if (likely(oldsize <= large_maxclass && usize_min <= large_maxclass)) {
3056 arena_chunk_t *chunk;
3057
3058 /*
3059 * Avoid moving the allocation if the size class can be left the
3060 * same.
3061 */
3062 if (oldsize <= SMALL_MAXCLASS) {
3063 assert(arena_bin_info[size2index(oldsize)].reg_size ==
3064 oldsize);
3065 if ((usize_max > SMALL_MAXCLASS ||
3066 size2index(usize_max) != size2index(oldsize)) &&
3067 (size > oldsize || usize_max < oldsize))
3068 return (true);
3069 } else {
3070 if (usize_max <= SMALL_MAXCLASS)
3071 return (true);
3072 if (arena_ralloc_large(ptr, oldsize, usize_min,
3073 usize_max, zero))
3074 return (true);
3075 }
3076
3077 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
3078 arena_decay_tick(tsd, extent_node_arena_get(&chunk->node));
3079 return (false);
3080 } else {
3081 return (huge_ralloc_no_move(tsd, ptr, oldsize, usize_min,
3082 usize_max, zero));
3083 }
3084 }
3085
3086 static void *
3087 arena_ralloc_move_helper(tsd_t *tsd, arena_t *arena, size_t usize,
3088 size_t alignment, bool zero, tcache_t *tcache)
3089 {
3090
3091 if (alignment == 0)
3092 return (arena_malloc(tsd, arena, usize, size2index(usize), zero,
3093 tcache, true));
3094 usize = sa2u(usize, alignment);
3095 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS))
3096 return (NULL);
3097 return (ipalloct(tsd, usize, alignment, zero, tcache, arena));
3098 }
3099
3100 void *
3101 arena_ralloc(tsd_t *tsd, arena_t *arena, void *ptr, size_t oldsize, size_t size,
3102 size_t alignment, bool zero, tcache_t *tcache)
3103 {
3104 void *ret;
3105 size_t usize;
3106
3107 usize = s2u(size);
3108 if (unlikely(usize == 0 || size > HUGE_MAXCLASS))
3109 return (NULL);
3110
3111 if (likely(usize <= large_maxclass)) {
3112 size_t copysize;
3113
3114 /* Try to avoid moving the allocation. */
3115 if (!arena_ralloc_no_move(tsd, ptr, oldsize, usize, 0, zero))
3116 return (ptr);
3117
3118 /*
3119 * size and oldsize are different enough that we need to move
3120 * the object. In that case, fall back to allocating new space
3121 * and copying.
3122 */
3123 ret = arena_ralloc_move_helper(tsd, arena, usize, alignment,
3124 zero, tcache);
3125 if (ret == NULL)
3126 return (NULL);
3127
3128 /*
3129 * Junk/zero-filling were already done by
3130 * ipalloc()/arena_malloc().
3131 */
3132
3133 copysize = (usize < oldsize) ? usize : oldsize;
3134 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, copysize);
3135 memcpy(ret, ptr, copysize);
3136 isqalloc(tsd, ptr, oldsize, tcache);
3137 } else {
3138 ret = huge_ralloc(tsd, arena, ptr, oldsize, usize, alignment,
3139 zero, tcache);
3140 }
3141 return (ret);
3142 }
3143
3144 dss_prec_t
3145 arena_dss_prec_get(arena_t *arena)
3146 {
3147 dss_prec_t ret;
3148
3149 malloc_mutex_lock(&arena->lock);
3150 ret = arena->dss_prec;
3151 malloc_mutex_unlock(&arena->lock);
3152 return (ret);
3153 }
3154
3155 bool
3156 arena_dss_prec_set(arena_t *arena, dss_prec_t dss_prec)
3157 {
3158
3159 if (!have_dss)
3160 return (dss_prec != dss_prec_disabled);
3161 malloc_mutex_lock(&arena->lock);
3162 arena->dss_prec = dss_prec;
3163 malloc_mutex_unlock(&arena->lock);
3164 return (false);
3165 }
3166
3167 ssize_t
3168 arena_lg_dirty_mult_default_get(void)
3169 {
3170
3171 return ((ssize_t)atomic_read_z((size_t *)&lg_dirty_mult_default));
3172 }
3173
3174 bool
3175 arena_lg_dirty_mult_default_set(ssize_t lg_dirty_mult)
3176 {
3177
3178 if (opt_purge != purge_mode_ratio)
3179 return (true);
3180 if (!arena_lg_dirty_mult_valid(lg_dirty_mult))
3181 return (true);
3182 atomic_write_z((size_t *)&lg_dirty_mult_default, (size_t)lg_dirty_mult);
3183 return (false);
3184 }
3185
3186 ssize_t
3187 arena_decay_time_default_get(void)
3188 {
3189
3190 return ((ssize_t)atomic_read_z((size_t *)&decay_time_default));
3191 }
3192
3193 bool
3194 arena_decay_time_default_set(ssize_t decay_time)
3195 {
3196
3197 if (opt_purge != purge_mode_decay)
3198 return (true);
3199 if (!arena_decay_time_valid(decay_time))
3200 return (true);
3201 atomic_write_z((size_t *)&decay_time_default, (size_t)decay_time);
3202 return (false);
3203 }
3204
3205 static void
3206 arena_basic_stats_merge_locked(arena_t *arena, unsigned *nthreads,
3207 const char **dss, ssize_t *lg_dirty_mult, ssize_t *decay_time,
3208 size_t *nactive, size_t *ndirty)
3209 {
3210
3211 *nthreads += arena_nthreads_get(arena);
3212 *dss = dss_prec_names[arena->dss_prec];
3213 *lg_dirty_mult = arena->lg_dirty_mult;
3214 *decay_time = arena->decay_time;
3215 *nactive += arena->nactive;
3216 *ndirty += arena->ndirty;
3217 }
3218
3219 void
3220 arena_basic_stats_merge(arena_t *arena, unsigned *nthreads, const char **dss,
3221 ssize_t *lg_dirty_mult, ssize_t *decay_time, size_t *nactive,
3222 size_t *ndirty)
3223 {
3224
3225 malloc_mutex_lock(&arena->lock);
3226 arena_basic_stats_merge_locked(arena, nthreads, dss, lg_dirty_mult,
3227 decay_time, nactive, ndirty);
3228 malloc_mutex_unlock(&arena->lock);
3229 }
3230
3231 void
3232 arena_stats_merge(arena_t *arena, unsigned *nthreads, const char **dss,
3233 ssize_t *lg_dirty_mult, ssize_t *decay_time, size_t *nactive,
3234 size_t *ndirty, arena_stats_t *astats, malloc_bin_stats_t *bstats,
3235 malloc_large_stats_t *lstats, malloc_huge_stats_t *hstats)
3236 {
3237 unsigned i;
3238
3239 cassert(config_stats);
3240
3241 malloc_mutex_lock(&arena->lock);
3242 arena_basic_stats_merge_locked(arena, nthreads, dss, lg_dirty_mult,
3243 decay_time, nactive, ndirty);
3244
3245 astats->mapped += arena->stats.mapped;
3246 astats->npurge += arena->stats.npurge;
3247 astats->nmadvise += arena->stats.nmadvise;
3248 astats->purged += arena->stats.purged;
3249 astats->metadata_mapped += arena->stats.metadata_mapped;
3250 astats->metadata_allocated += arena_metadata_allocated_get(arena);
3251 astats->allocated_large += arena->stats.allocated_large;
3252 astats->nmalloc_large += arena->stats.nmalloc_large;
3253 astats->ndalloc_large += arena->stats.ndalloc_large;
3254 astats->nrequests_large += arena->stats.nrequests_large;
3255 astats->allocated_huge += arena->stats.allocated_huge;
3256 astats->nmalloc_huge += arena->stats.nmalloc_huge;
3257 astats->ndalloc_huge += arena->stats.ndalloc_huge;
3258
3259 for (i = 0; i < nlclasses; i++) {
3260 lstats[i].nmalloc += arena->stats.lstats[i].nmalloc;
3261 lstats[i].ndalloc += arena->stats.lstats[i].ndalloc;
3262 lstats[i].nrequests += arena->stats.lstats[i].nrequests;
3263 lstats[i].curruns += arena->stats.lstats[i].curruns;
3264 }
3265
3266 for (i = 0; i < nhclasses; i++) {
3267 hstats[i].nmalloc += arena->stats.hstats[i].nmalloc;
3268 hstats[i].ndalloc += arena->stats.hstats[i].ndalloc;
3269 hstats[i].curhchunks += arena->stats.hstats[i].curhchunks;
3270 }
3271 malloc_mutex_unlock(&arena->lock);
3272
3273 for (i = 0; i < NBINS; i++) {
3274 arena_bin_t *bin = &arena->bins[i];
3275
3276 malloc_mutex_lock(&bin->lock);
3277 bstats[i].nmalloc += bin->stats.nmalloc;
3278 bstats[i].ndalloc += bin->stats.ndalloc;
3279 bstats[i].nrequests += bin->stats.nrequests;
3280 bstats[i].curregs += bin->stats.curregs;
3281 if (config_tcache) {
3282 bstats[i].nfills += bin->stats.nfills;
3283 bstats[i].nflushes += bin->stats.nflushes;
3284 }
3285 bstats[i].nruns += bin->stats.nruns;
3286 bstats[i].reruns += bin->stats.reruns;
3287 bstats[i].curruns += bin->stats.curruns;
3288 malloc_mutex_unlock(&bin->lock);
3289 }
3290 }
3291
3292 unsigned
3293 arena_nthreads_get(arena_t *arena)
3294 {
3295
3296 return (atomic_read_u(&arena->nthreads));
3297 }
3298
3299 void
3300 arena_nthreads_inc(arena_t *arena)
3301 {
3302
3303 atomic_add_u(&arena->nthreads, 1);
3304 }
3305
3306 void
3307 arena_nthreads_dec(arena_t *arena)
3308 {
3309
3310 atomic_sub_u(&arena->nthreads, 1);
3311 }
3312
3313 arena_t *
3314 arena_new(unsigned ind)
3315 {
3316 arena_t *arena;
3317 size_t arena_size;
3318 unsigned i;
3319 arena_bin_t *bin;
3320
3321 /* Compute arena size to incorporate sufficient runs_avail elements. */
3322 arena_size = offsetof(arena_t, runs_avail) + (sizeof(arena_run_tree_t) *
3323 runs_avail_nclasses);
3324 /*
3325 * Allocate arena, arena->lstats, and arena->hstats contiguously, mainly
3326 * because there is no way to clean up if base_alloc() OOMs.
3327 */
3328 if (config_stats) {
3329 arena = (arena_t *)base_alloc(CACHELINE_CEILING(arena_size) +
3330 QUANTUM_CEILING(nlclasses * sizeof(malloc_large_stats_t) +
3331 nhclasses) * sizeof(malloc_huge_stats_t));
3332 } else
3333 arena = (arena_t *)base_alloc(arena_size);
3334 if (arena == NULL)
3335 return (NULL);
3336
3337 arena->ind = ind;
3338 arena->nthreads = 0;
3339 if (malloc_mutex_init(&arena->lock))
3340 return (NULL);
3341
3342 if (config_stats) {
3343 memset(&arena->stats, 0, sizeof(arena_stats_t));
3344 arena->stats.lstats = (malloc_large_stats_t *)((uintptr_t)arena
3345 + CACHELINE_CEILING(arena_size));
3346 memset(arena->stats.lstats, 0, nlclasses *
3347 sizeof(malloc_large_stats_t));
3348 arena->stats.hstats = (malloc_huge_stats_t *)((uintptr_t)arena
3349 + CACHELINE_CEILING(arena_size) +
3350 QUANTUM_CEILING(nlclasses * sizeof(malloc_large_stats_t)));
3351 memset(arena->stats.hstats, 0, nhclasses *
3352 sizeof(malloc_huge_stats_t));
3353 if (config_tcache)
3354 ql_new(&arena->tcache_ql);
3355 }
3356
3357 if (config_prof)
3358 arena->prof_accumbytes = 0;
3359
3360 if (config_cache_oblivious) {
3361 /*
3362 * A nondeterministic seed based on the address of arena reduces
3363 * the likelihood of lockstep non-uniform cache index
3364 * utilization among identical concurrent processes, but at the
3365 * cost of test repeatability. For debug builds, instead use a
3366 * deterministic seed.
3367 */
3368 arena->offset_state = config_debug ? ind :
3369 (uint64_t)(uintptr_t)arena;
3370 }
3371
3372 arena->dss_prec = chunk_dss_prec_get();
3373
3374 arena->spare = NULL;
3375
3376 arena->lg_dirty_mult = arena_lg_dirty_mult_default_get();
3377 arena->purging = false;
3378 arena->nactive = 0;
3379 arena->ndirty = 0;
3380
3381 for(i = 0; i < runs_avail_nclasses; i++)
3382 arena_run_tree_new(&arena->runs_avail[i]);
3383 qr_new(&arena->runs_dirty, rd_link);
3384 qr_new(&arena->chunks_cache, cc_link);
3385
3386 if (opt_purge == purge_mode_decay)
3387 arena_decay_init(arena, arena_decay_time_default_get());
3388
3389 ql_new(&arena->huge);
3390 if (malloc_mutex_init(&arena->huge_mtx))
3391 return (NULL);
3392
3393 extent_tree_szad_new(&arena->chunks_szad_cached);
3394 extent_tree_ad_new(&arena->chunks_ad_cached);
3395 extent_tree_szad_new(&arena->chunks_szad_retained);
3396 extent_tree_ad_new(&arena->chunks_ad_retained);
3397 if (malloc_mutex_init(&arena->chunks_mtx))
3398 return (NULL);
3399 ql_new(&arena->node_cache);
3400 if (malloc_mutex_init(&arena->node_cache_mtx))
3401 return (NULL);
3402
3403 arena->chunk_hooks = chunk_hooks_default;
3404
3405 /* Initialize bins. */
3406 for (i = 0; i < NBINS; i++) {
3407 bin = &arena->bins[i];
3408 if (malloc_mutex_init(&bin->lock))
3409 return (NULL);
3410 bin->runcur = NULL;
3411 arena_run_tree_new(&bin->runs);
3412 if (config_stats)
3413 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
3414 }
3415
3416 return (arena);
3417 }
3418
3419 /*
3420 * Calculate bin_info->run_size such that it meets the following constraints:
3421 *
3422 * *) bin_info->run_size <= arena_maxrun
3423 * *) bin_info->nregs <= RUN_MAXREGS
3424 *
3425 * bin_info->nregs and bin_info->reg0_offset are also calculated here, since
3426 * these settings are all interdependent.
3427 */
3428 static void
3429 bin_info_run_size_calc(arena_bin_info_t *bin_info)
3430 {
3431 size_t pad_size;
3432 size_t try_run_size, perfect_run_size, actual_run_size;
3433 uint32_t try_nregs, perfect_nregs, actual_nregs;
3434
3435 /*
3436 * Determine redzone size based on minimum alignment and minimum
3437 * redzone size. Add padding to the end of the run if it is needed to
3438 * align the regions. The padding allows each redzone to be half the
3439 * minimum alignment; without the padding, each redzone would have to
3440 * be twice as large in order to maintain alignment.
3441 */
3442 if (config_fill && unlikely(opt_redzone)) {
3443 size_t align_min = ZU(1) << (ffs_zu(bin_info->reg_size) - 1);
3444 if (align_min <= REDZONE_MINSIZE) {
3445 bin_info->redzone_size = REDZONE_MINSIZE;
3446 pad_size = 0;
3447 } else {
3448 bin_info->redzone_size = align_min >> 1;
3449 pad_size = bin_info->redzone_size;
3450 }
3451 } else {
3452 bin_info->redzone_size = 0;
3453 pad_size = 0;
3454 }
3455 bin_info->reg_interval = bin_info->reg_size +
3456 (bin_info->redzone_size << 1);
3457
3458 /*
3459 * Compute run size under ideal conditions (no redzones, no limit on run
3460 * size).
3461 */
3462 try_run_size = PAGE;
3463 try_nregs = (uint32_t)(try_run_size / bin_info->reg_size);
3464 do {
3465 perfect_run_size = try_run_size;
3466 perfect_nregs = try_nregs;
3467
3468 try_run_size += PAGE;
3469 try_nregs = (uint32_t)(try_run_size / bin_info->reg_size);
3470 } while (perfect_run_size != perfect_nregs * bin_info->reg_size);
3471 assert(perfect_nregs <= RUN_MAXREGS);
3472
3473 actual_run_size = perfect_run_size;
3474 actual_nregs = (uint32_t)((actual_run_size - pad_size) /
3475 bin_info->reg_interval);
3476
3477 /*
3478 * Redzones can require enough padding that not even a single region can
3479 * fit within the number of pages that would normally be dedicated to a
3480 * run for this size class. Increase the run size until at least one
3481 * region fits.
3482 */
3483 while (actual_nregs == 0) {
3484 assert(config_fill && unlikely(opt_redzone));
3485
3486 actual_run_size += PAGE;
3487 actual_nregs = (uint32_t)((actual_run_size - pad_size) /
3488 bin_info->reg_interval);
3489 }
3490
3491 /*
3492 * Make sure that the run will fit within an arena chunk.
3493 */
3494 while (actual_run_size > arena_maxrun) {
3495 actual_run_size -= PAGE;
3496 actual_nregs = (uint32_t)((actual_run_size - pad_size) /
3497 bin_info->reg_interval);
3498 }
3499 assert(actual_nregs > 0);
3500 assert(actual_run_size == s2u(actual_run_size));
3501
3502 /* Copy final settings. */
3503 bin_info->run_size = actual_run_size;
3504 bin_info->nregs = actual_nregs;
3505 bin_info->reg0_offset = (uint32_t)(actual_run_size - (actual_nregs *
3506 bin_info->reg_interval) - pad_size + bin_info->redzone_size);
3507
3508 if (actual_run_size > small_maxrun)
3509 small_maxrun = actual_run_size;
3510
3511 assert(bin_info->reg0_offset - bin_info->redzone_size + (bin_info->nregs
3512 * bin_info->reg_interval) + pad_size == bin_info->run_size);
3513 }
3514
3515 static void
3516 bin_info_init(void)
3517 {
3518 arena_bin_info_t *bin_info;
3519
3520 #define BIN_INFO_INIT_bin_yes(index, size) \
3521 bin_info = &arena_bin_info[index]; \
3522 bin_info->reg_size = size; \
3523 bin_info_run_size_calc(bin_info); \
3524 bitmap_info_init(&bin_info->bitmap_info, bin_info->nregs);
3525 #define BIN_INFO_INIT_bin_no(index, size)
3526 #define SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup) \
3527 BIN_INFO_INIT_bin_##bin(index, (ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta))
3528 SIZE_CLASSES
3529 #undef BIN_INFO_INIT_bin_yes
3530 #undef BIN_INFO_INIT_bin_no
3531 #undef SC
3532 }
3533
3534 static bool
3535 small_run_size_init(void)
3536 {
3537
3538 assert(small_maxrun != 0);
3539
3540 small_run_tab = (bool *)base_alloc(sizeof(bool) * (small_maxrun >>
3541 LG_PAGE));
3542 if (small_run_tab == NULL)
3543 return (true);
3544
3545 #define TAB_INIT_bin_yes(index, size) { \
3546 arena_bin_info_t *bin_info = &arena_bin_info[index]; \
3547 small_run_tab[bin_info->run_size >> LG_PAGE] = true; \
3548 }
3549 #define TAB_INIT_bin_no(index, size)
3550 #define SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup) \
3551 TAB_INIT_bin_##bin(index, (ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta))
3552 SIZE_CLASSES
3553 #undef TAB_INIT_bin_yes
3554 #undef TAB_INIT_bin_no
3555 #undef SC
3556
3557 return (false);
3558 }
3559
3560 static bool
3561 run_quantize_init(void)
3562 {
3563 unsigned i;
3564
3565 run_quantize_max = chunksize + large_pad;
3566
3567 run_quantize_floor_tab = (size_t *)base_alloc(sizeof(size_t) *
3568 (run_quantize_max >> LG_PAGE));
3569 if (run_quantize_floor_tab == NULL)
3570 return (true);
3571
3572 run_quantize_ceil_tab = (size_t *)base_alloc(sizeof(size_t) *
3573 (run_quantize_max >> LG_PAGE));
3574 if (run_quantize_ceil_tab == NULL)
3575 return (true);
3576
3577 for (i = 1; i <= run_quantize_max >> LG_PAGE; i++) {
3578 size_t run_size = i << LG_PAGE;
3579
3580 run_quantize_floor_tab[i-1] =
3581 run_quantize_floor_compute(run_size);
3582 run_quantize_ceil_tab[i-1] =
3583 run_quantize_ceil_compute(run_size);
3584 }
3585
3586 return (false);
3587 }
3588
3589 bool
3590 arena_boot(void)
3591 {
3592 unsigned i;
3593
3594 arena_lg_dirty_mult_default_set(opt_lg_dirty_mult);
3595 arena_decay_time_default_set(opt_decay_time);
3596
3597 /*
3598 * Compute the header size such that it is large enough to contain the
3599 * page map. The page map is biased to omit entries for the header
3600 * itself, so some iteration is necessary to compute the map bias.
3601 *
3602 * 1) Compute safe header_size and map_bias values that include enough
3603 * space for an unbiased page map.
3604 * 2) Refine map_bias based on (1) to omit the header pages in the page
3605 * map. The resulting map_bias may be one too small.
3606 * 3) Refine map_bias based on (2). The result will be >= the result
3607 * from (2), and will always be correct.
3608 */
3609 map_bias = 0;
3610 for (i = 0; i < 3; i++) {
3611 size_t header_size = offsetof(arena_chunk_t, map_bits) +
3612 ((sizeof(arena_chunk_map_bits_t) +
3613 sizeof(arena_chunk_map_misc_t)) * (chunk_npages-map_bias));
3614 map_bias = (header_size + PAGE_MASK) >> LG_PAGE;
3615 }
3616 assert(map_bias > 0);
3617
3618 map_misc_offset = offsetof(arena_chunk_t, map_bits) +
3619 sizeof(arena_chunk_map_bits_t) * (chunk_npages-map_bias);
3620
3621 arena_maxrun = chunksize - (map_bias << LG_PAGE);
3622 assert(arena_maxrun > 0);
3623 large_maxclass = index2size(size2index(chunksize)-1);
3624 if (large_maxclass > arena_maxrun) {
3625 /*
3626 * For small chunk sizes it's possible for there to be fewer
3627 * non-header pages available than are necessary to serve the
3628 * size classes just below chunksize.
3629 */
3630 large_maxclass = arena_maxrun;
3631 }
3632 assert(large_maxclass > 0);
3633 nlclasses = size2index(large_maxclass) - size2index(SMALL_MAXCLASS);
3634 nhclasses = NSIZES - nlclasses - NBINS;
3635
3636 bin_info_init();
3637 if (small_run_size_init())
3638 return (true);
3639 if (run_quantize_init())
3640 return (true);
3641
3642 runs_avail_bias = size2index(PAGE);
3643 runs_avail_nclasses = size2index(run_quantize_max)+1 - runs_avail_bias;
3644
3645 return (false);
3646 }
3647
3648 void
3649 arena_prefork(arena_t *arena)
3650 {
3651 unsigned i;
3652
3653 malloc_mutex_prefork(&arena->lock);
3654 malloc_mutex_prefork(&arena->huge_mtx);
3655 malloc_mutex_prefork(&arena->chunks_mtx);
3656 malloc_mutex_prefork(&arena->node_cache_mtx);
3657 for (i = 0; i < NBINS; i++)
3658 malloc_mutex_prefork(&arena->bins[i].lock);
3659 }
3660
3661 void
3662 arena_postfork_parent(arena_t *arena)
3663 {
3664 unsigned i;
3665
3666 for (i = 0; i < NBINS; i++)
3667 malloc_mutex_postfork_parent(&arena->bins[i].lock);
3668 malloc_mutex_postfork_parent(&arena->node_cache_mtx);
3669 malloc_mutex_postfork_parent(&arena->chunks_mtx);
3670 malloc_mutex_postfork_parent(&arena->huge_mtx);
3671 malloc_mutex_postfork_parent(&arena->lock);
3672 }
3673
3674 void
3675 arena_postfork_child(arena_t *arena)
3676 {
3677 unsigned i;
3678
3679 for (i = 0; i < NBINS; i++)
3680 malloc_mutex_postfork_child(&arena->bins[i].lock);
3681 malloc_mutex_postfork_child(&arena->node_cache_mtx);
3682 malloc_mutex_postfork_child(&arena->chunks_mtx);
3683 malloc_mutex_postfork_child(&arena->huge_mtx);
3684 malloc_mutex_postfork_child(&arena->lock);
3685 }