diff options
Diffstat (limited to 'dep/jemalloc/src/arena.c')
| -rw-r--r-- | dep/jemalloc/src/arena.c | 4419 |
1 files changed, 1637 insertions, 2782 deletions
diff --git a/dep/jemalloc/src/arena.c b/dep/jemalloc/src/arena.c index 43733cc1572..632fce5233e 100644 --- a/dep/jemalloc/src/arena.c +++ b/dep/jemalloc/src/arena.c @@ -1,21 +1,58 @@ -#define JEMALLOC_ARENA_C_ -#include "jemalloc/internal/jemalloc_internal.h" +#define JEMALLOC_ARENA_C_ +#include "jemalloc/internal/jemalloc_preamble.h" +#include "jemalloc/internal/jemalloc_internal_includes.h" + +#include "jemalloc/internal/assert.h" +#include "jemalloc/internal/extent_dss.h" +#include "jemalloc/internal/extent_mmap.h" +#include "jemalloc/internal/mutex.h" +#include "jemalloc/internal/rtree.h" +#include "jemalloc/internal/size_classes.h" +#include "jemalloc/internal/util.h" /******************************************************************************/ /* Data. */ -ssize_t opt_lg_dirty_mult = LG_DIRTY_MULT_DEFAULT; -static ssize_t lg_dirty_mult_default; -arena_bin_info_t arena_bin_info[NBINS]; +/* + * Define names for both unininitialized and initialized phases, so that + * options and mallctl processing are straightforward. + */ +const char *percpu_arena_mode_names[] = { + "percpu", + "phycpu", + "disabled", + "percpu", + "phycpu" +}; +percpu_arena_mode_t opt_percpu_arena = PERCPU_ARENA_DEFAULT; + +ssize_t opt_dirty_decay_ms = DIRTY_DECAY_MS_DEFAULT; +ssize_t opt_muzzy_decay_ms = MUZZY_DECAY_MS_DEFAULT; + +static atomic_zd_t dirty_decay_ms_default; +static atomic_zd_t muzzy_decay_ms_default; + +const arena_bin_info_t arena_bin_info[NBINS] = { +#define BIN_INFO_bin_yes(reg_size, slab_size, nregs) \ + {reg_size, slab_size, nregs, BITMAP_INFO_INITIALIZER(nregs)}, +#define BIN_INFO_bin_no(reg_size, slab_size, nregs) +#define SC(index, lg_grp, lg_delta, ndelta, psz, bin, pgs, \ + lg_delta_lookup) \ + BIN_INFO_bin_##bin((1U<<lg_grp) + (ndelta<<lg_delta), \ + (pgs << LG_PAGE), (pgs << LG_PAGE) / ((1U<<lg_grp) + \ + (ndelta<<lg_delta))) + SIZE_CLASSES +#undef BIN_INFO_bin_yes +#undef BIN_INFO_bin_no +#undef SC +}; -size_t map_bias; -size_t map_misc_offset; -size_t arena_maxrun; /* Max run size for arenas. */ -size_t large_maxclass; /* Max large size class. */ -static size_t small_maxrun; /* Max run size used for small size classes. */ -static bool *small_run_tab; /* Valid small run page multiples. */ -unsigned nlclasses; /* Number of large size classes. */ -unsigned nhclasses; /* Number of huge size classes. */ +const uint64_t h_steps[SMOOTHSTEP_NSTEPS] = { +#define STEP(step, h, x, y) \ + h, + SMOOTHSTEP +#undef STEP +}; /******************************************************************************/ /* @@ -23,1998 +60,1396 @@ unsigned nhclasses; /* Number of huge size classes. */ * definition. */ -static void arena_purge(arena_t *arena, bool all); -static void arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty, - bool cleaned, bool decommitted); -static void arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, - arena_run_t *run, arena_bin_t *bin); -static void arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, - arena_run_t *run, arena_bin_t *bin); +static void arena_decay_to_limit(tsdn_t *tsdn, arena_t *arena, + arena_decay_t *decay, extents_t *extents, bool all, size_t npages_limit, + bool is_background_thread); +static bool arena_decay_dirty(tsdn_t *tsdn, arena_t *arena, + bool is_background_thread, bool all); +static void arena_dalloc_bin_slab(tsdn_t *tsdn, arena_t *arena, extent_t *slab, + arena_bin_t *bin); +static void arena_bin_lower_slab(tsdn_t *tsdn, arena_t *arena, extent_t *slab, + arena_bin_t *bin); /******************************************************************************/ -#define CHUNK_MAP_KEY ((uintptr_t)0x1U) - -JEMALLOC_INLINE_C arena_chunk_map_misc_t * -arena_miscelm_key_create(size_t size) -{ - - return ((arena_chunk_map_misc_t *)(arena_mapbits_size_encode(size) | - CHUNK_MAP_KEY)); +static bool +arena_stats_init(tsdn_t *tsdn, arena_stats_t *arena_stats) { + if (config_debug) { + for (size_t i = 0; i < sizeof(arena_stats_t); i++) { + assert(((char *)arena_stats)[i] == 0); + } + } +#ifndef JEMALLOC_ATOMIC_U64 + if (malloc_mutex_init(&arena_stats->mtx, "arena_stats", + WITNESS_RANK_ARENA_STATS, malloc_mutex_rank_exclusive)) { + return true; + } +#endif + /* Memory is zeroed, so there is no need to clear stats. */ + return false; } -JEMALLOC_INLINE_C bool -arena_miscelm_is_key(const arena_chunk_map_misc_t *miscelm) -{ - - return (((uintptr_t)miscelm & CHUNK_MAP_KEY) != 0); +static void +arena_stats_lock(tsdn_t *tsdn, arena_stats_t *arena_stats) { +#ifndef JEMALLOC_ATOMIC_U64 + malloc_mutex_lock(tsdn, &arena_stats->mtx); +#endif } -#undef CHUNK_MAP_KEY - -JEMALLOC_INLINE_C size_t -arena_miscelm_key_size_get(const arena_chunk_map_misc_t *miscelm) -{ - - assert(arena_miscelm_is_key(miscelm)); - - return (arena_mapbits_size_decode((uintptr_t)miscelm)); +static void +arena_stats_unlock(tsdn_t *tsdn, arena_stats_t *arena_stats) { +#ifndef JEMALLOC_ATOMIC_U64 + malloc_mutex_unlock(tsdn, &arena_stats->mtx); +#endif } -JEMALLOC_INLINE_C size_t -arena_miscelm_size_get(arena_chunk_map_misc_t *miscelm) -{ - arena_chunk_t *chunk; - size_t pageind, mapbits; - - assert(!arena_miscelm_is_key(miscelm)); - - chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(miscelm); - pageind = arena_miscelm_to_pageind(miscelm); - mapbits = arena_mapbits_get(chunk, pageind); - return (arena_mapbits_size_decode(mapbits)); +static uint64_t +arena_stats_read_u64(tsdn_t *tsdn, arena_stats_t *arena_stats, + arena_stats_u64_t *p) { +#ifdef JEMALLOC_ATOMIC_U64 + return atomic_load_u64(p, ATOMIC_RELAXED); +#else + malloc_mutex_assert_owner(tsdn, &arena_stats->mtx); + return *p; +#endif } -JEMALLOC_INLINE_C int -arena_run_comp(arena_chunk_map_misc_t *a, arena_chunk_map_misc_t *b) -{ - uintptr_t a_miscelm = (uintptr_t)a; - uintptr_t b_miscelm = (uintptr_t)b; - - assert(a != NULL); - assert(b != NULL); - - return ((a_miscelm > b_miscelm) - (a_miscelm < b_miscelm)); +static void +arena_stats_add_u64(tsdn_t *tsdn, arena_stats_t *arena_stats, + arena_stats_u64_t *p, uint64_t x) { +#ifdef JEMALLOC_ATOMIC_U64 + atomic_fetch_add_u64(p, x, ATOMIC_RELAXED); +#else + malloc_mutex_assert_owner(tsdn, &arena_stats->mtx); + *p += x; +#endif } -/* Generate red-black tree functions. */ -rb_gen(static UNUSED, arena_run_tree_, arena_run_tree_t, arena_chunk_map_misc_t, - rb_link, arena_run_comp) - -static size_t -run_quantize(size_t size) -{ - size_t qsize; - - assert(size != 0); - assert(size == PAGE_CEILING(size)); - - /* Don't change sizes that are valid small run sizes. */ - if (size <= small_maxrun && small_run_tab[size >> LG_PAGE]) - return (size); - - /* - * Round down to the nearest run size that can actually be requested - * during normal large allocation. Add large_pad so that cache index - * randomization can offset the allocation from the page boundary. - */ - qsize = index2size(size2index(size - large_pad + 1) - 1) + large_pad; - if (qsize <= SMALL_MAXCLASS + large_pad) - return (run_quantize(size - large_pad)); - assert(qsize <= size); - return (qsize); +UNUSED static void +arena_stats_sub_u64(tsdn_t *tsdn, arena_stats_t *arena_stats, + arena_stats_u64_t *p, uint64_t x) { +#ifdef JEMALLOC_ATOMIC_U64 + UNUSED uint64_t r = atomic_fetch_sub_u64(p, x, ATOMIC_RELAXED); + assert(r - x <= r); +#else + malloc_mutex_assert_owner(tsdn, &arena_stats->mtx); + *p -= x; + assert(*p + x >= *p); +#endif } -static size_t -run_quantize_next(size_t size) -{ - size_t large_run_size_next; - - assert(size != 0); - assert(size == PAGE_CEILING(size)); - - /* - * Return the next quantized size greater than the input size. - * Quantized sizes comprise the union of run sizes that back small - * region runs, and run sizes that back large regions with no explicit - * alignment constraints. - */ - - if (size > SMALL_MAXCLASS) { - large_run_size_next = PAGE_CEILING(index2size(size2index(size - - large_pad) + 1) + large_pad); - } else - large_run_size_next = SIZE_T_MAX; - if (size >= small_maxrun) - return (large_run_size_next); - - while (true) { - size += PAGE; - assert(size <= small_maxrun); - if (small_run_tab[size >> LG_PAGE]) { - if (large_run_size_next < size) - return (large_run_size_next); - return (size); - } - } +/* + * Non-atomically sets *dst += src. *dst needs external synchronization. + * This lets us avoid the cost of a fetch_add when its unnecessary (note that + * the types here are atomic). + */ +static void +arena_stats_accum_u64(arena_stats_u64_t *dst, uint64_t src) { +#ifdef JEMALLOC_ATOMIC_U64 + uint64_t cur_dst = atomic_load_u64(dst, ATOMIC_RELAXED); + atomic_store_u64(dst, src + cur_dst, ATOMIC_RELAXED); +#else + *dst += src; +#endif } static size_t -run_quantize_first(size_t size) -{ - size_t qsize = run_quantize(size); - - if (qsize < size) { - /* - * Skip a quantization that may have an adequately large run, - * because under-sized runs may be mixed in. This only happens - * when an unusual size is requested, i.e. for aligned - * allocation, and is just one of several places where linear - * search would potentially find sufficiently aligned available - * memory somewhere lower. - */ - qsize = run_quantize_next(size); - } - return (qsize); -} - -JEMALLOC_INLINE_C int -arena_avail_comp(arena_chunk_map_misc_t *a, arena_chunk_map_misc_t *b) -{ - int ret; - uintptr_t a_miscelm = (uintptr_t)a; - size_t a_qsize = run_quantize(arena_miscelm_is_key(a) ? - arena_miscelm_key_size_get(a) : arena_miscelm_size_get(a)); - size_t b_qsize = run_quantize(arena_miscelm_size_get(b)); - - /* - * Compare based on quantized size rather than size, in order to sort - * equally useful runs only by address. - */ - ret = (a_qsize > b_qsize) - (a_qsize < b_qsize); - if (ret == 0) { - if (!arena_miscelm_is_key(a)) { - uintptr_t b_miscelm = (uintptr_t)b; - - ret = (a_miscelm > b_miscelm) - (a_miscelm < b_miscelm); - } else { - /* - * Treat keys as if they are lower than anything else. - */ - ret = -1; - } - } - - return (ret); +arena_stats_read_zu(tsdn_t *tsdn, arena_stats_t *arena_stats, atomic_zu_t *p) { +#ifdef JEMALLOC_ATOMIC_U64 + return atomic_load_zu(p, ATOMIC_RELAXED); +#else + malloc_mutex_assert_owner(tsdn, &arena_stats->mtx); + return atomic_load_zu(p, ATOMIC_RELAXED); +#endif } -/* Generate red-black tree functions. */ -rb_gen(static UNUSED, arena_avail_tree_, arena_avail_tree_t, - arena_chunk_map_misc_t, rb_link, arena_avail_comp) - static void -arena_avail_insert(arena_t *arena, arena_chunk_t *chunk, size_t pageind, - size_t npages) -{ - - assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >> - LG_PAGE)); - arena_avail_tree_insert(&arena->runs_avail, arena_miscelm_get(chunk, - pageind)); +arena_stats_add_zu(tsdn_t *tsdn, arena_stats_t *arena_stats, atomic_zu_t *p, + size_t x) { +#ifdef JEMALLOC_ATOMIC_U64 + atomic_fetch_add_zu(p, x, ATOMIC_RELAXED); +#else + malloc_mutex_assert_owner(tsdn, &arena_stats->mtx); + size_t cur = atomic_load_zu(p, ATOMIC_RELAXED); + atomic_store_zu(p, cur + x, ATOMIC_RELAXED); +#endif } static void -arena_avail_remove(arena_t *arena, arena_chunk_t *chunk, size_t pageind, - size_t npages) -{ - - assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >> - LG_PAGE)); - arena_avail_tree_remove(&arena->runs_avail, arena_miscelm_get(chunk, - pageind)); +arena_stats_sub_zu(tsdn_t *tsdn, arena_stats_t *arena_stats, atomic_zu_t *p, + size_t x) { +#ifdef JEMALLOC_ATOMIC_U64 + UNUSED size_t r = atomic_fetch_sub_zu(p, x, ATOMIC_RELAXED); + assert(r - x <= r); +#else + malloc_mutex_assert_owner(tsdn, &arena_stats->mtx); + size_t cur = atomic_load_zu(p, ATOMIC_RELAXED); + atomic_store_zu(p, cur - x, ATOMIC_RELAXED); +#endif } +/* Like the _u64 variant, needs an externally synchronized *dst. */ static void -arena_run_dirty_insert(arena_t *arena, arena_chunk_t *chunk, size_t pageind, - size_t npages) -{ - arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind); - - assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >> - LG_PAGE)); - assert(arena_mapbits_dirty_get(chunk, pageind) == CHUNK_MAP_DIRTY); - assert(arena_mapbits_dirty_get(chunk, pageind+npages-1) == - CHUNK_MAP_DIRTY); - - qr_new(&miscelm->rd, rd_link); - qr_meld(&arena->runs_dirty, &miscelm->rd, rd_link); - arena->ndirty += npages; +arena_stats_accum_zu(atomic_zu_t *dst, size_t src) { + size_t cur_dst = atomic_load_zu(dst, ATOMIC_RELAXED); + atomic_store_zu(dst, src + cur_dst, ATOMIC_RELAXED); } -static void -arena_run_dirty_remove(arena_t *arena, arena_chunk_t *chunk, size_t pageind, - size_t npages) -{ - arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind); - - assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >> - LG_PAGE)); - assert(arena_mapbits_dirty_get(chunk, pageind) == CHUNK_MAP_DIRTY); - assert(arena_mapbits_dirty_get(chunk, pageind+npages-1) == - CHUNK_MAP_DIRTY); - - qr_remove(&miscelm->rd, rd_link); - assert(arena->ndirty >= npages); - arena->ndirty -= npages; +void +arena_stats_large_nrequests_add(tsdn_t *tsdn, arena_stats_t *arena_stats, + szind_t szind, uint64_t nrequests) { + arena_stats_lock(tsdn, arena_stats); + arena_stats_add_u64(tsdn, arena_stats, &arena_stats->lstats[szind - + NBINS].nrequests, nrequests); + arena_stats_unlock(tsdn, arena_stats); } -static size_t -arena_chunk_dirty_npages(const extent_node_t *node) -{ +void +arena_stats_mapped_add(tsdn_t *tsdn, arena_stats_t *arena_stats, size_t size) { + arena_stats_lock(tsdn, arena_stats); + arena_stats_add_zu(tsdn, arena_stats, &arena_stats->mapped, size); + arena_stats_unlock(tsdn, arena_stats); +} - return (extent_node_size_get(node) >> LG_PAGE); +void +arena_basic_stats_merge(tsdn_t *tsdn, arena_t *arena, unsigned *nthreads, + const char **dss, ssize_t *dirty_decay_ms, ssize_t *muzzy_decay_ms, + size_t *nactive, size_t *ndirty, size_t *nmuzzy) { + *nthreads += arena_nthreads_get(arena, false); + *dss = dss_prec_names[arena_dss_prec_get(arena)]; + *dirty_decay_ms = arena_dirty_decay_ms_get(arena); + *muzzy_decay_ms = arena_muzzy_decay_ms_get(arena); + *nactive += atomic_load_zu(&arena->nactive, ATOMIC_RELAXED); + *ndirty += extents_npages_get(&arena->extents_dirty); + *nmuzzy += extents_npages_get(&arena->extents_muzzy); } void -arena_chunk_cache_maybe_insert(arena_t *arena, extent_node_t *node, bool cache) -{ +arena_stats_merge(tsdn_t *tsdn, arena_t *arena, unsigned *nthreads, + const char **dss, ssize_t *dirty_decay_ms, ssize_t *muzzy_decay_ms, + size_t *nactive, size_t *ndirty, size_t *nmuzzy, arena_stats_t *astats, + malloc_bin_stats_t *bstats, malloc_large_stats_t *lstats) { + cassert(config_stats); - if (cache) { - extent_node_dirty_linkage_init(node); - extent_node_dirty_insert(node, &arena->runs_dirty, - &arena->chunks_cache); - arena->ndirty += arena_chunk_dirty_npages(node); + arena_basic_stats_merge(tsdn, arena, nthreads, dss, dirty_decay_ms, + muzzy_decay_ms, nactive, ndirty, nmuzzy); + + size_t base_allocated, base_resident, base_mapped; + base_stats_get(tsdn, arena->base, &base_allocated, &base_resident, + &base_mapped); + + arena_stats_lock(tsdn, &arena->stats); + + arena_stats_accum_zu(&astats->mapped, base_mapped + + arena_stats_read_zu(tsdn, &arena->stats, &arena->stats.mapped)); + arena_stats_accum_zu(&astats->retained, + extents_npages_get(&arena->extents_retained) << LG_PAGE); + + arena_stats_accum_u64(&astats->decay_dirty.npurge, + arena_stats_read_u64(tsdn, &arena->stats, + &arena->stats.decay_dirty.npurge)); + arena_stats_accum_u64(&astats->decay_dirty.nmadvise, + arena_stats_read_u64(tsdn, &arena->stats, + &arena->stats.decay_dirty.nmadvise)); + arena_stats_accum_u64(&astats->decay_dirty.purged, + arena_stats_read_u64(tsdn, &arena->stats, + &arena->stats.decay_dirty.purged)); + + arena_stats_accum_u64(&astats->decay_muzzy.npurge, + arena_stats_read_u64(tsdn, &arena->stats, + &arena->stats.decay_muzzy.npurge)); + arena_stats_accum_u64(&astats->decay_muzzy.nmadvise, + arena_stats_read_u64(tsdn, &arena->stats, + &arena->stats.decay_muzzy.nmadvise)); + arena_stats_accum_u64(&astats->decay_muzzy.purged, + arena_stats_read_u64(tsdn, &arena->stats, + &arena->stats.decay_muzzy.purged)); + + arena_stats_accum_zu(&astats->base, base_allocated); + arena_stats_accum_zu(&astats->internal, arena_internal_get(arena)); + arena_stats_accum_zu(&astats->resident, base_resident + + (((atomic_load_zu(&arena->nactive, ATOMIC_RELAXED) + + extents_npages_get(&arena->extents_dirty) + + extents_npages_get(&arena->extents_muzzy)) << LG_PAGE))); + + for (szind_t i = 0; i < NSIZES - NBINS; i++) { + uint64_t nmalloc = arena_stats_read_u64(tsdn, &arena->stats, + &arena->stats.lstats[i].nmalloc); + arena_stats_accum_u64(&lstats[i].nmalloc, nmalloc); + arena_stats_accum_u64(&astats->nmalloc_large, nmalloc); + + uint64_t ndalloc = arena_stats_read_u64(tsdn, &arena->stats, + &arena->stats.lstats[i].ndalloc); + arena_stats_accum_u64(&lstats[i].ndalloc, ndalloc); + arena_stats_accum_u64(&astats->ndalloc_large, ndalloc); + + uint64_t nrequests = arena_stats_read_u64(tsdn, &arena->stats, + &arena->stats.lstats[i].nrequests); + arena_stats_accum_u64(&lstats[i].nrequests, + nmalloc + nrequests); + arena_stats_accum_u64(&astats->nrequests_large, + nmalloc + nrequests); + + assert(nmalloc >= ndalloc); + assert(nmalloc - ndalloc <= SIZE_T_MAX); + size_t curlextents = (size_t)(nmalloc - ndalloc); + lstats[i].curlextents += curlextents; + arena_stats_accum_zu(&astats->allocated_large, + curlextents * sz_index2size(NBINS + i)); + } + + arena_stats_unlock(tsdn, &arena->stats); + + /* tcache_bytes counts currently cached bytes. */ + atomic_store_zu(&astats->tcache_bytes, 0, ATOMIC_RELAXED); + malloc_mutex_lock(tsdn, &arena->tcache_ql_mtx); + tcache_t *tcache; + ql_foreach(tcache, &arena->tcache_ql, link) { + szind_t i = 0; + for (; i < NBINS; i++) { + tcache_bin_t *tbin = tcache_small_bin_get(tcache, i); + arena_stats_accum_zu(&astats->tcache_bytes, + tbin->ncached * sz_index2size(i)); + } + for (; i < nhbins; i++) { + tcache_bin_t *tbin = tcache_large_bin_get(tcache, i); + arena_stats_accum_zu(&astats->tcache_bytes, + tbin->ncached * sz_index2size(i)); + } + } + malloc_mutex_prof_read(tsdn, + &astats->mutex_prof_data[arena_prof_mutex_tcache_list], + &arena->tcache_ql_mtx); + malloc_mutex_unlock(tsdn, &arena->tcache_ql_mtx); + +#define READ_ARENA_MUTEX_PROF_DATA(mtx, ind) \ + malloc_mutex_lock(tsdn, &arena->mtx); \ + malloc_mutex_prof_read(tsdn, &astats->mutex_prof_data[ind], \ + &arena->mtx); \ + malloc_mutex_unlock(tsdn, &arena->mtx); + + /* Gather per arena mutex profiling data. */ + READ_ARENA_MUTEX_PROF_DATA(large_mtx, arena_prof_mutex_large); + READ_ARENA_MUTEX_PROF_DATA(extent_avail_mtx, + arena_prof_mutex_extent_avail) + READ_ARENA_MUTEX_PROF_DATA(extents_dirty.mtx, + arena_prof_mutex_extents_dirty) + READ_ARENA_MUTEX_PROF_DATA(extents_muzzy.mtx, + arena_prof_mutex_extents_muzzy) + READ_ARENA_MUTEX_PROF_DATA(extents_retained.mtx, + arena_prof_mutex_extents_retained) + READ_ARENA_MUTEX_PROF_DATA(decay_dirty.mtx, + arena_prof_mutex_decay_dirty) + READ_ARENA_MUTEX_PROF_DATA(decay_muzzy.mtx, + arena_prof_mutex_decay_muzzy) + READ_ARENA_MUTEX_PROF_DATA(base->mtx, + arena_prof_mutex_base) +#undef READ_ARENA_MUTEX_PROF_DATA + + nstime_copy(&astats->uptime, &arena->create_time); + nstime_update(&astats->uptime); + nstime_subtract(&astats->uptime, &arena->create_time); + + for (szind_t i = 0; i < NBINS; i++) { + arena_bin_t *bin = &arena->bins[i]; + + malloc_mutex_lock(tsdn, &bin->lock); + malloc_mutex_prof_read(tsdn, &bstats[i].mutex_data, &bin->lock); + bstats[i].nmalloc += bin->stats.nmalloc; + bstats[i].ndalloc += bin->stats.ndalloc; + bstats[i].nrequests += bin->stats.nrequests; + bstats[i].curregs += bin->stats.curregs; + bstats[i].nfills += bin->stats.nfills; + bstats[i].nflushes += bin->stats.nflushes; + bstats[i].nslabs += bin->stats.nslabs; + bstats[i].reslabs += bin->stats.reslabs; + bstats[i].curslabs += bin->stats.curslabs; + malloc_mutex_unlock(tsdn, &bin->lock); } } void -arena_chunk_cache_maybe_remove(arena_t *arena, extent_node_t *node, bool dirty) -{ - - if (dirty) { - extent_node_dirty_remove(node); - assert(arena->ndirty >= arena_chunk_dirty_npages(node)); - arena->ndirty -= arena_chunk_dirty_npages(node); +arena_extents_dirty_dalloc(tsdn_t *tsdn, arena_t *arena, + extent_hooks_t **r_extent_hooks, extent_t *extent) { + witness_assert_depth_to_rank(tsdn_witness_tsdp_get(tsdn), + WITNESS_RANK_CORE, 0); + + extents_dalloc(tsdn, arena, r_extent_hooks, &arena->extents_dirty, + extent); + if (arena_dirty_decay_ms_get(arena) == 0) { + arena_decay_dirty(tsdn, arena, false, true); + } else { + arena_background_thread_inactivity_check(tsdn, arena, false); } } -JEMALLOC_INLINE_C void * -arena_run_reg_alloc(arena_run_t *run, arena_bin_info_t *bin_info) -{ +static void * +arena_slab_reg_alloc(tsdn_t *tsdn, extent_t *slab, + const arena_bin_info_t *bin_info) { void *ret; - unsigned regind; - arena_chunk_map_misc_t *miscelm; - void *rpages; - - assert(run->nfree > 0); - assert(!bitmap_full(run->bitmap, &bin_info->bitmap_info)); - - regind = bitmap_sfu(run->bitmap, &bin_info->bitmap_info); - miscelm = arena_run_to_miscelm(run); - rpages = arena_miscelm_to_rpages(miscelm); - ret = (void *)((uintptr_t)rpages + (uintptr_t)bin_info->reg0_offset + - (uintptr_t)(bin_info->reg_interval * regind)); - run->nfree--; - return (ret); -} - -JEMALLOC_INLINE_C void -arena_run_reg_dalloc(arena_run_t *run, void *ptr) -{ - arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); - size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; - size_t mapbits = arena_mapbits_get(chunk, pageind); - szind_t binind = arena_ptr_small_binind_get(ptr, mapbits); - arena_bin_info_t *bin_info = &arena_bin_info[binind]; - unsigned regind = arena_run_regind(run, bin_info, ptr); - - assert(run->nfree < bin_info->nregs); - /* Freeing an interior pointer can cause assertion failure. */ - assert(((uintptr_t)ptr - - ((uintptr_t)arena_miscelm_to_rpages(arena_run_to_miscelm(run)) + - (uintptr_t)bin_info->reg0_offset)) % - (uintptr_t)bin_info->reg_interval == 0); - assert((uintptr_t)ptr >= - (uintptr_t)arena_miscelm_to_rpages(arena_run_to_miscelm(run)) + - (uintptr_t)bin_info->reg0_offset); - /* Freeing an unallocated pointer can cause assertion failure. */ - assert(bitmap_get(run->bitmap, &bin_info->bitmap_info, regind)); + arena_slab_data_t *slab_data = extent_slab_data_get(slab); + size_t regind; - bitmap_unset(run->bitmap, &bin_info->bitmap_info, regind); - run->nfree++; -} - -JEMALLOC_INLINE_C void -arena_run_zero(arena_chunk_t *chunk, size_t run_ind, size_t npages) -{ + assert(extent_nfree_get(slab) > 0); + assert(!bitmap_full(slab_data->bitmap, &bin_info->bitmap_info)); - JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk + - (run_ind << LG_PAGE)), (npages << LG_PAGE)); - memset((void *)((uintptr_t)chunk + (run_ind << LG_PAGE)), 0, - (npages << LG_PAGE)); + regind = bitmap_sfu(slab_data->bitmap, &bin_info->bitmap_info); + ret = (void *)((uintptr_t)extent_addr_get(slab) + + (uintptr_t)(bin_info->reg_size * regind)); + extent_nfree_dec(slab); + return ret; } -JEMALLOC_INLINE_C void -arena_run_page_mark_zeroed(arena_chunk_t *chunk, size_t run_ind) -{ +#ifndef JEMALLOC_JET +static +#endif +size_t +arena_slab_regind(extent_t *slab, szind_t binind, const void *ptr) { + size_t diff, regind; - JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void *)((uintptr_t)chunk + (run_ind - << LG_PAGE)), PAGE); -} + /* Freeing a pointer outside the slab can cause assertion failure. */ + assert((uintptr_t)ptr >= (uintptr_t)extent_addr_get(slab)); + assert((uintptr_t)ptr < (uintptr_t)extent_past_get(slab)); + /* Freeing an interior pointer can cause assertion failure. */ + assert(((uintptr_t)ptr - (uintptr_t)extent_addr_get(slab)) % + (uintptr_t)arena_bin_info[binind].reg_size == 0); + + /* Avoid doing division with a variable divisor. */ + diff = (size_t)((uintptr_t)ptr - (uintptr_t)extent_addr_get(slab)); + switch (binind) { +#define REGIND_bin_yes(index, reg_size) \ + case index: \ + regind = diff / (reg_size); \ + assert(diff == regind * (reg_size)); \ + break; +#define REGIND_bin_no(index, reg_size) +#define SC(index, lg_grp, lg_delta, ndelta, psz, bin, pgs, \ + lg_delta_lookup) \ + REGIND_bin_##bin(index, (1U<<lg_grp) + (ndelta<<lg_delta)) + SIZE_CLASSES +#undef REGIND_bin_yes +#undef REGIND_bin_no +#undef SC + default: not_reached(); + } -JEMALLOC_INLINE_C void -arena_run_page_validate_zeroed(arena_chunk_t *chunk, size_t run_ind) -{ - size_t i; - UNUSED size_t *p = (size_t *)((uintptr_t)chunk + (run_ind << LG_PAGE)); + assert(regind < arena_bin_info[binind].nregs); - arena_run_page_mark_zeroed(chunk, run_ind); - for (i = 0; i < PAGE / sizeof(size_t); i++) - assert(p[i] == 0); + return regind; } static void -arena_cactive_update(arena_t *arena, size_t add_pages, size_t sub_pages) -{ +arena_slab_reg_dalloc(tsdn_t *tsdn, extent_t *slab, + arena_slab_data_t *slab_data, void *ptr) { + szind_t binind = extent_szind_get(slab); + const arena_bin_info_t *bin_info = &arena_bin_info[binind]; + size_t regind = arena_slab_regind(slab, binind, ptr); - if (config_stats) { - ssize_t cactive_diff = CHUNK_CEILING((arena->nactive + add_pages - - sub_pages) << LG_PAGE) - CHUNK_CEILING(arena->nactive << - LG_PAGE); - if (cactive_diff != 0) - stats_cactive_add(cactive_diff); - } + assert(extent_nfree_get(slab) < bin_info->nregs); + /* Freeing an unallocated pointer can cause assertion failure. */ + assert(bitmap_get(slab_data->bitmap, &bin_info->bitmap_info, regind)); + + bitmap_unset(slab_data->bitmap, &bin_info->bitmap_info, regind); + extent_nfree_inc(slab); } static void -arena_run_split_remove(arena_t *arena, arena_chunk_t *chunk, size_t run_ind, - size_t flag_dirty, size_t flag_decommitted, size_t need_pages) -{ - size_t total_pages, rem_pages; - - assert(flag_dirty == 0 || flag_decommitted == 0); - - total_pages = arena_mapbits_unallocated_size_get(chunk, run_ind) >> - LG_PAGE; - assert(arena_mapbits_dirty_get(chunk, run_ind+total_pages-1) == - flag_dirty); - assert(need_pages <= total_pages); - rem_pages = total_pages - need_pages; - - arena_avail_remove(arena, chunk, run_ind, total_pages); - if (flag_dirty != 0) - arena_run_dirty_remove(arena, chunk, run_ind, total_pages); - arena_cactive_update(arena, need_pages, 0); - arena->nactive += need_pages; - - /* Keep track of trailing unused pages for later use. */ - if (rem_pages > 0) { - size_t flags = flag_dirty | flag_decommitted; - size_t flag_unzeroed_mask = (flags == 0) ? CHUNK_MAP_UNZEROED : - 0; - - arena_mapbits_unallocated_set(chunk, run_ind+need_pages, - (rem_pages << LG_PAGE), flags | - (arena_mapbits_unzeroed_get(chunk, run_ind+need_pages) & - flag_unzeroed_mask)); - arena_mapbits_unallocated_set(chunk, run_ind+total_pages-1, - (rem_pages << LG_PAGE), flags | - (arena_mapbits_unzeroed_get(chunk, run_ind+total_pages-1) & - flag_unzeroed_mask)); - if (flag_dirty != 0) { - arena_run_dirty_insert(arena, chunk, run_ind+need_pages, - rem_pages); - } - arena_avail_insert(arena, chunk, run_ind+need_pages, rem_pages); - } +arena_nactive_add(arena_t *arena, size_t add_pages) { + atomic_fetch_add_zu(&arena->nactive, add_pages, ATOMIC_RELAXED); } -static bool -arena_run_split_large_helper(arena_t *arena, arena_run_t *run, size_t size, - bool remove, bool zero) -{ - arena_chunk_t *chunk; - arena_chunk_map_misc_t *miscelm; - size_t flag_dirty, flag_decommitted, run_ind, need_pages; - size_t flag_unzeroed_mask; - - chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); - miscelm = arena_run_to_miscelm(run); - run_ind = arena_miscelm_to_pageind(miscelm); - flag_dirty = arena_mapbits_dirty_get(chunk, run_ind); - flag_decommitted = arena_mapbits_decommitted_get(chunk, run_ind); - need_pages = (size >> LG_PAGE); - assert(need_pages > 0); - - if (flag_decommitted != 0 && arena->chunk_hooks.commit(chunk, chunksize, - run_ind << LG_PAGE, size, arena->ind)) - return (true); - - if (remove) { - arena_run_split_remove(arena, chunk, run_ind, flag_dirty, - flag_decommitted, need_pages); - } - - if (zero) { - if (flag_decommitted != 0) { - /* The run is untouched, and therefore zeroed. */ - JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void - *)((uintptr_t)chunk + (run_ind << LG_PAGE)), - (need_pages << LG_PAGE)); - } else if (flag_dirty != 0) { - /* The run is dirty, so all pages must be zeroed. */ - arena_run_zero(chunk, run_ind, need_pages); - } else { - /* - * The run is clean, so some pages may be zeroed (i.e. - * never before touched). - */ - size_t i; - for (i = 0; i < need_pages; i++) { - if (arena_mapbits_unzeroed_get(chunk, run_ind+i) - != 0) - arena_run_zero(chunk, run_ind+i, 1); - else if (config_debug) { - arena_run_page_validate_zeroed(chunk, - run_ind+i); - } else { - arena_run_page_mark_zeroed(chunk, - run_ind+i); - } - } - } - } else { - JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk + - (run_ind << LG_PAGE)), (need_pages << LG_PAGE)); - } - - /* - * Set the last element first, in case the run only contains one page - * (i.e. both statements set the same element). - */ - flag_unzeroed_mask = (flag_dirty | flag_decommitted) == 0 ? - CHUNK_MAP_UNZEROED : 0; - arena_mapbits_large_set(chunk, run_ind+need_pages-1, 0, flag_dirty | - (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, - run_ind+need_pages-1))); - arena_mapbits_large_set(chunk, run_ind, size, flag_dirty | - (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, run_ind))); - return (false); +static void +arena_nactive_sub(arena_t *arena, size_t sub_pages) { + assert(atomic_load_zu(&arena->nactive, ATOMIC_RELAXED) >= sub_pages); + atomic_fetch_sub_zu(&arena->nactive, sub_pages, ATOMIC_RELAXED); } -static bool -arena_run_split_large(arena_t *arena, arena_run_t *run, size_t size, bool zero) -{ +static void +arena_large_malloc_stats_update(tsdn_t *tsdn, arena_t *arena, size_t usize) { + szind_t index, hindex; - return (arena_run_split_large_helper(arena, run, size, true, zero)); -} + cassert(config_stats); -static bool -arena_run_init_large(arena_t *arena, arena_run_t *run, size_t size, bool zero) -{ + if (usize < LARGE_MINCLASS) { + usize = LARGE_MINCLASS; + } + index = sz_size2index(usize); + hindex = (index >= NBINS) ? index - NBINS : 0; - return (arena_run_split_large_helper(arena, run, size, false, zero)); + arena_stats_add_u64(tsdn, &arena->stats, + &arena->stats.lstats[hindex].nmalloc, 1); } -static bool -arena_run_split_small(arena_t *arena, arena_run_t *run, size_t size, - szind_t binind) -{ - arena_chunk_t *chunk; - arena_chunk_map_misc_t *miscelm; - size_t flag_dirty, flag_decommitted, run_ind, need_pages, i; - - assert(binind != BININD_INVALID); - - chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); - miscelm = arena_run_to_miscelm(run); - run_ind = arena_miscelm_to_pageind(miscelm); - flag_dirty = arena_mapbits_dirty_get(chunk, run_ind); - flag_decommitted = arena_mapbits_decommitted_get(chunk, run_ind); - need_pages = (size >> LG_PAGE); - assert(need_pages > 0); - - if (flag_decommitted != 0 && arena->chunk_hooks.commit(chunk, chunksize, - run_ind << LG_PAGE, size, arena->ind)) - return (true); +static void +arena_large_dalloc_stats_update(tsdn_t *tsdn, arena_t *arena, size_t usize) { + szind_t index, hindex; - arena_run_split_remove(arena, chunk, run_ind, flag_dirty, - flag_decommitted, need_pages); + cassert(config_stats); - for (i = 0; i < need_pages; i++) { - size_t flag_unzeroed = arena_mapbits_unzeroed_get(chunk, - run_ind+i); - arena_mapbits_small_set(chunk, run_ind+i, i, binind, - flag_unzeroed); - if (config_debug && flag_dirty == 0 && flag_unzeroed == 0) - arena_run_page_validate_zeroed(chunk, run_ind+i); + if (usize < LARGE_MINCLASS) { + usize = LARGE_MINCLASS; } - JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk + - (run_ind << LG_PAGE)), (need_pages << LG_PAGE)); - return (false); -} - -static arena_chunk_t * -arena_chunk_init_spare(arena_t *arena) -{ - arena_chunk_t *chunk; - - assert(arena->spare != NULL); - - chunk = arena->spare; - arena->spare = NULL; + index = sz_size2index(usize); + hindex = (index >= NBINS) ? index - NBINS : 0; - assert(arena_mapbits_allocated_get(chunk, map_bias) == 0); - assert(arena_mapbits_allocated_get(chunk, chunk_npages-1) == 0); - assert(arena_mapbits_unallocated_size_get(chunk, map_bias) == - arena_maxrun); - assert(arena_mapbits_unallocated_size_get(chunk, chunk_npages-1) == - arena_maxrun); - assert(arena_mapbits_dirty_get(chunk, map_bias) == - arena_mapbits_dirty_get(chunk, chunk_npages-1)); + arena_stats_add_u64(tsdn, &arena->stats, + &arena->stats.lstats[hindex].ndalloc, 1); +} - return (chunk); +static void +arena_large_ralloc_stats_update(tsdn_t *tsdn, arena_t *arena, size_t oldusize, + size_t usize) { + arena_large_dalloc_stats_update(tsdn, arena, oldusize); + arena_large_malloc_stats_update(tsdn, arena, usize); } -static bool -arena_chunk_register(arena_t *arena, arena_chunk_t *chunk, bool zero) -{ +extent_t * +arena_extent_alloc_large(tsdn_t *tsdn, arena_t *arena, size_t usize, + size_t alignment, bool *zero) { + extent_hooks_t *extent_hooks = EXTENT_HOOKS_INITIALIZER; - /* - * The extent node notion of "committed" doesn't directly apply to - * arena chunks. Arbitrarily mark them as committed. The commit state - * of runs is tracked individually, and upon chunk deallocation the - * entire chunk is in a consistent commit state. - */ - extent_node_init(&chunk->node, arena, chunk, chunksize, zero, true); - extent_node_achunk_set(&chunk->node, true); - return (chunk_register(chunk, &chunk->node)); -} - -static arena_chunk_t * -arena_chunk_alloc_internal_hard(arena_t *arena, chunk_hooks_t *chunk_hooks, - bool *zero, bool *commit) -{ - arena_chunk_t *chunk; - - malloc_mutex_unlock(&arena->lock); - - chunk = (arena_chunk_t *)chunk_alloc_wrapper(arena, chunk_hooks, NULL, - chunksize, chunksize, zero, commit); - if (chunk != NULL && !*commit) { - /* Commit header. */ - if (chunk_hooks->commit(chunk, chunksize, 0, map_bias << - LG_PAGE, arena->ind)) { - chunk_dalloc_wrapper(arena, chunk_hooks, - (void *)chunk, chunksize, *commit); - chunk = NULL; + witness_assert_depth_to_rank(tsdn_witness_tsdp_get(tsdn), + WITNESS_RANK_CORE, 0); + + szind_t szind = sz_size2index(usize); + size_t mapped_add; + bool commit = true; + extent_t *extent = extents_alloc(tsdn, arena, &extent_hooks, + &arena->extents_dirty, NULL, usize, sz_large_pad, alignment, false, + szind, zero, &commit); + if (extent == NULL) { + extent = extents_alloc(tsdn, arena, &extent_hooks, + &arena->extents_muzzy, NULL, usize, sz_large_pad, alignment, + false, szind, zero, &commit); + } + size_t size = usize + sz_large_pad; + if (extent == NULL) { + extent = extent_alloc_wrapper(tsdn, arena, &extent_hooks, NULL, + usize, sz_large_pad, alignment, false, szind, zero, + &commit); + if (config_stats) { + /* + * extent may be NULL on OOM, but in that case + * mapped_add isn't used below, so there's no need to + * conditionlly set it to 0 here. + */ + mapped_add = size; } + } else if (config_stats) { + mapped_add = 0; } - if (chunk != NULL && arena_chunk_register(arena, chunk, *zero)) { - if (!*commit) { - /* Undo commit of header. */ - chunk_hooks->decommit(chunk, chunksize, 0, map_bias << - LG_PAGE, arena->ind); + + if (extent != NULL) { + if (config_stats) { + arena_stats_lock(tsdn, &arena->stats); + arena_large_malloc_stats_update(tsdn, arena, usize); + if (mapped_add != 0) { + arena_stats_add_zu(tsdn, &arena->stats, + &arena->stats.mapped, mapped_add); + } + arena_stats_unlock(tsdn, &arena->stats); } - chunk_dalloc_wrapper(arena, chunk_hooks, (void *)chunk, - chunksize, *commit); - chunk = NULL; + arena_nactive_add(arena, size >> LG_PAGE); } - malloc_mutex_lock(&arena->lock); - return (chunk); + return extent; } -static arena_chunk_t * -arena_chunk_alloc_internal(arena_t *arena, bool *zero, bool *commit) -{ - arena_chunk_t *chunk; - chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER; - - chunk = chunk_alloc_cache(arena, &chunk_hooks, NULL, chunksize, - chunksize, zero, true); - if (chunk != NULL) { - if (arena_chunk_register(arena, chunk, *zero)) { - chunk_dalloc_cache(arena, &chunk_hooks, chunk, - chunksize, true); - return (NULL); - } - *commit = true; - } - if (chunk == NULL) { - chunk = arena_chunk_alloc_internal_hard(arena, &chunk_hooks, - zero, commit); - } - - if (config_stats && chunk != NULL) { - arena->stats.mapped += chunksize; - arena->stats.metadata_mapped += (map_bias << LG_PAGE); +void +arena_extent_dalloc_large_prep(tsdn_t *tsdn, arena_t *arena, extent_t *extent) { + if (config_stats) { + arena_stats_lock(tsdn, &arena->stats); + arena_large_dalloc_stats_update(tsdn, arena, + extent_usize_get(extent)); + arena_stats_unlock(tsdn, &arena->stats); } - - return (chunk); + arena_nactive_sub(arena, extent_size_get(extent) >> LG_PAGE); } -static arena_chunk_t * -arena_chunk_init_hard(arena_t *arena) -{ - arena_chunk_t *chunk; - bool zero, commit; - size_t flag_unzeroed, flag_decommitted, i; - - assert(arena->spare == NULL); - - zero = false; - commit = false; - chunk = arena_chunk_alloc_internal(arena, &zero, &commit); - if (chunk == NULL) - return (NULL); +void +arena_extent_ralloc_large_shrink(tsdn_t *tsdn, arena_t *arena, extent_t *extent, + size_t oldusize) { + size_t usize = extent_usize_get(extent); + size_t udiff = oldusize - usize; - /* - * Initialize the map to contain one maximal free untouched run. Mark - * the pages as zeroed if chunk_alloc() returned a zeroed or decommitted - * chunk. - */ - flag_unzeroed = (zero || !commit) ? 0 : CHUNK_MAP_UNZEROED; - flag_decommitted = commit ? 0 : CHUNK_MAP_DECOMMITTED; - arena_mapbits_unallocated_set(chunk, map_bias, arena_maxrun, - flag_unzeroed | flag_decommitted); - /* - * There is no need to initialize the internal page map entries unless - * the chunk is not zeroed. - */ - if (!zero) { - JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED( - (void *)arena_bitselm_get(chunk, map_bias+1), - (size_t)((uintptr_t) arena_bitselm_get(chunk, - chunk_npages-1) - (uintptr_t)arena_bitselm_get(chunk, - map_bias+1))); - for (i = map_bias+1; i < chunk_npages-1; i++) - arena_mapbits_internal_set(chunk, i, flag_unzeroed); - } else { - JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void - *)arena_bitselm_get(chunk, map_bias+1), (size_t)((uintptr_t) - arena_bitselm_get(chunk, chunk_npages-1) - - (uintptr_t)arena_bitselm_get(chunk, map_bias+1))); - if (config_debug) { - for (i = map_bias+1; i < chunk_npages-1; i++) { - assert(arena_mapbits_unzeroed_get(chunk, i) == - flag_unzeroed); - } - } + if (config_stats) { + arena_stats_lock(tsdn, &arena->stats); + arena_large_ralloc_stats_update(tsdn, arena, oldusize, usize); + arena_stats_unlock(tsdn, &arena->stats); } - arena_mapbits_unallocated_set(chunk, chunk_npages-1, arena_maxrun, - flag_unzeroed); - - return (chunk); + arena_nactive_sub(arena, udiff >> LG_PAGE); } -static arena_chunk_t * -arena_chunk_alloc(arena_t *arena) -{ - arena_chunk_t *chunk; +void +arena_extent_ralloc_large_expand(tsdn_t *tsdn, arena_t *arena, extent_t *extent, + size_t oldusize) { + size_t usize = extent_usize_get(extent); + size_t udiff = usize - oldusize; - if (arena->spare != NULL) - chunk = arena_chunk_init_spare(arena); - else { - chunk = arena_chunk_init_hard(arena); - if (chunk == NULL) - return (NULL); + if (config_stats) { + arena_stats_lock(tsdn, &arena->stats); + arena_large_ralloc_stats_update(tsdn, arena, oldusize, usize); + arena_stats_unlock(tsdn, &arena->stats); } + arena_nactive_add(arena, udiff >> LG_PAGE); +} - /* Insert the run into the runs_avail tree. */ - arena_avail_insert(arena, chunk, map_bias, chunk_npages-map_bias); - - return (chunk); +static ssize_t +arena_decay_ms_read(arena_decay_t *decay) { + return atomic_load_zd(&decay->time_ms, ATOMIC_RELAXED); } static void -arena_chunk_dalloc(arena_t *arena, arena_chunk_t *chunk) -{ - - assert(arena_mapbits_allocated_get(chunk, map_bias) == 0); - assert(arena_mapbits_allocated_get(chunk, chunk_npages-1) == 0); - assert(arena_mapbits_unallocated_size_get(chunk, map_bias) == - arena_maxrun); - assert(arena_mapbits_unallocated_size_get(chunk, chunk_npages-1) == - arena_maxrun); - assert(arena_mapbits_dirty_get(chunk, map_bias) == - arena_mapbits_dirty_get(chunk, chunk_npages-1)); - assert(arena_mapbits_decommitted_get(chunk, map_bias) == - arena_mapbits_decommitted_get(chunk, chunk_npages-1)); +arena_decay_ms_write(arena_decay_t *decay, ssize_t decay_ms) { + atomic_store_zd(&decay->time_ms, decay_ms, ATOMIC_RELAXED); +} +static void +arena_decay_deadline_init(arena_decay_t *decay) { /* - * Remove run from the runs_avail tree, so that the arena does not use - * it. + * Generate a new deadline that is uniformly random within the next + * epoch after the current one. */ - arena_avail_remove(arena, chunk, map_bias, chunk_npages-map_bias); - - if (arena->spare != NULL) { - arena_chunk_t *spare = arena->spare; - chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER; - bool committed; + nstime_copy(&decay->deadline, &decay->epoch); + nstime_add(&decay->deadline, &decay->interval); + if (arena_decay_ms_read(decay) > 0) { + nstime_t jitter; - arena->spare = chunk; - if (arena_mapbits_dirty_get(spare, map_bias) != 0) { - arena_run_dirty_remove(arena, spare, map_bias, - chunk_npages-map_bias); - } + nstime_init(&jitter, prng_range_u64(&decay->jitter_state, + nstime_ns(&decay->interval))); + nstime_add(&decay->deadline, &jitter); + } +} - chunk_deregister(spare, &spare->node); +static bool +arena_decay_deadline_reached(const arena_decay_t *decay, const nstime_t *time) { + return (nstime_compare(&decay->deadline, time) <= 0); +} - committed = (arena_mapbits_decommitted_get(spare, map_bias) == - 0); - if (!committed) { - /* - * Decommit the header. Mark the chunk as decommitted - * even if header decommit fails, since treating a - * partially committed chunk as committed has a high - * potential for causing later access of decommitted - * memory. - */ - chunk_hooks = chunk_hooks_get(arena); - chunk_hooks.decommit(spare, chunksize, 0, map_bias << - LG_PAGE, arena->ind); - } +static size_t +arena_decay_backlog_npages_limit(const arena_decay_t *decay) { + uint64_t sum; + size_t npages_limit_backlog; + unsigned i; - chunk_dalloc_cache(arena, &chunk_hooks, (void *)spare, - chunksize, committed); + /* + * For each element of decay_backlog, multiply by the corresponding + * fixed-point smoothstep decay factor. Sum the products, then divide + * to round down to the nearest whole number of pages. + */ + sum = 0; + for (i = 0; i < SMOOTHSTEP_NSTEPS; i++) { + sum += decay->backlog[i] * h_steps[i]; + } + npages_limit_backlog = (size_t)(sum >> SMOOTHSTEP_BFP); - if (config_stats) { - arena->stats.mapped -= chunksize; - arena->stats.metadata_mapped -= (map_bias << LG_PAGE); - } - } else - arena->spare = chunk; + return npages_limit_backlog; } static void -arena_huge_malloc_stats_update(arena_t *arena, size_t usize) -{ - szind_t index = size2index(usize) - nlclasses - NBINS; - - cassert(config_stats); +arena_decay_backlog_update_last(arena_decay_t *decay, size_t current_npages) { + size_t npages_delta = (current_npages > decay->nunpurged) ? + current_npages - decay->nunpurged : 0; + decay->backlog[SMOOTHSTEP_NSTEPS-1] = npages_delta; - arena->stats.nmalloc_huge++; - arena->stats.allocated_huge += usize; - arena->stats.hstats[index].nmalloc++; - arena->stats.hstats[index].curhchunks++; + if (config_debug) { + if (current_npages > decay->ceil_npages) { + decay->ceil_npages = current_npages; + } + size_t npages_limit = arena_decay_backlog_npages_limit(decay); + assert(decay->ceil_npages >= npages_limit); + if (decay->ceil_npages > npages_limit) { + decay->ceil_npages = npages_limit; + } + } } static void -arena_huge_malloc_stats_update_undo(arena_t *arena, size_t usize) -{ - szind_t index = size2index(usize) - nlclasses - NBINS; +arena_decay_backlog_update(arena_decay_t *decay, uint64_t nadvance_u64, + size_t current_npages) { + if (nadvance_u64 >= SMOOTHSTEP_NSTEPS) { + memset(decay->backlog, 0, (SMOOTHSTEP_NSTEPS-1) * + sizeof(size_t)); + } else { + size_t nadvance_z = (size_t)nadvance_u64; - cassert(config_stats); + assert((uint64_t)nadvance_z == nadvance_u64); + + memmove(decay->backlog, &decay->backlog[nadvance_z], + (SMOOTHSTEP_NSTEPS - nadvance_z) * sizeof(size_t)); + if (nadvance_z > 1) { + memset(&decay->backlog[SMOOTHSTEP_NSTEPS - + nadvance_z], 0, (nadvance_z-1) * sizeof(size_t)); + } + } - arena->stats.nmalloc_huge--; - arena->stats.allocated_huge -= usize; - arena->stats.hstats[index].nmalloc--; - arena->stats.hstats[index].curhchunks--; + arena_decay_backlog_update_last(decay, current_npages); } static void -arena_huge_dalloc_stats_update(arena_t *arena, size_t usize) -{ - szind_t index = size2index(usize) - nlclasses - NBINS; - - cassert(config_stats); - - arena->stats.ndalloc_huge++; - arena->stats.allocated_huge -= usize; - arena->stats.hstats[index].ndalloc++; - arena->stats.hstats[index].curhchunks--; +arena_decay_try_purge(tsdn_t *tsdn, arena_t *arena, arena_decay_t *decay, + extents_t *extents, size_t current_npages, size_t npages_limit, + bool is_background_thread) { + if (current_npages > npages_limit) { + arena_decay_to_limit(tsdn, arena, decay, extents, false, + npages_limit, is_background_thread); + } } static void -arena_huge_dalloc_stats_update_undo(arena_t *arena, size_t usize) -{ - szind_t index = size2index(usize) - nlclasses - NBINS; +arena_decay_epoch_advance_helper(arena_decay_t *decay, const nstime_t *time, + size_t current_npages) { + assert(arena_decay_deadline_reached(decay, time)); - cassert(config_stats); + nstime_t delta; + nstime_copy(&delta, time); + nstime_subtract(&delta, &decay->epoch); - arena->stats.ndalloc_huge--; - arena->stats.allocated_huge += usize; - arena->stats.hstats[index].ndalloc--; - arena->stats.hstats[index].curhchunks++; -} + uint64_t nadvance_u64 = nstime_divide(&delta, &decay->interval); + assert(nadvance_u64 > 0); -static void -arena_huge_ralloc_stats_update(arena_t *arena, size_t oldsize, size_t usize) -{ + /* Add nadvance_u64 decay intervals to epoch. */ + nstime_copy(&delta, &decay->interval); + nstime_imultiply(&delta, nadvance_u64); + nstime_add(&decay->epoch, &delta); + + /* Set a new deadline. */ + arena_decay_deadline_init(decay); - arena_huge_dalloc_stats_update(arena, oldsize); - arena_huge_malloc_stats_update(arena, usize); + /* Update the backlog. */ + arena_decay_backlog_update(decay, nadvance_u64, current_npages); } static void -arena_huge_ralloc_stats_update_undo(arena_t *arena, size_t oldsize, - size_t usize) -{ - - arena_huge_dalloc_stats_update_undo(arena, oldsize); - arena_huge_malloc_stats_update_undo(arena, usize); -} +arena_decay_epoch_advance(tsdn_t *tsdn, arena_t *arena, arena_decay_t *decay, + extents_t *extents, const nstime_t *time, bool is_background_thread) { + size_t current_npages = extents_npages_get(extents); + arena_decay_epoch_advance_helper(decay, time, current_npages); -extent_node_t * -arena_node_alloc(arena_t *arena) -{ - extent_node_t *node; + size_t npages_limit = arena_decay_backlog_npages_limit(decay); + /* We may unlock decay->mtx when try_purge(). Finish logging first. */ + decay->nunpurged = (npages_limit > current_npages) ? npages_limit : + current_npages; - malloc_mutex_lock(&arena->node_cache_mtx); - node = ql_last(&arena->node_cache, ql_link); - if (node == NULL) { - malloc_mutex_unlock(&arena->node_cache_mtx); - return (base_alloc(sizeof(extent_node_t))); + if (!background_thread_enabled() || is_background_thread) { + arena_decay_try_purge(tsdn, arena, decay, extents, + current_npages, npages_limit, is_background_thread); } - ql_tail_remove(&arena->node_cache, extent_node_t, ql_link); - malloc_mutex_unlock(&arena->node_cache_mtx); - return (node); -} - -void -arena_node_dalloc(arena_t *arena, extent_node_t *node) -{ - - malloc_mutex_lock(&arena->node_cache_mtx); - ql_elm_new(node, ql_link); - ql_tail_insert(&arena->node_cache, node, ql_link); - malloc_mutex_unlock(&arena->node_cache_mtx); } -static void * -arena_chunk_alloc_huge_hard(arena_t *arena, chunk_hooks_t *chunk_hooks, - size_t usize, size_t alignment, bool *zero, size_t csize) -{ - void *ret; - bool commit = true; - - ret = chunk_alloc_wrapper(arena, chunk_hooks, NULL, csize, alignment, - zero, &commit); - if (ret == NULL) { - /* Revert optimistic stats updates. */ - malloc_mutex_lock(&arena->lock); - if (config_stats) { - arena_huge_malloc_stats_update_undo(arena, usize); - arena->stats.mapped -= usize; - } - arena->nactive -= (usize >> LG_PAGE); - malloc_mutex_unlock(&arena->lock); +static void +arena_decay_reinit(arena_decay_t *decay, extents_t *extents, ssize_t decay_ms) { + arena_decay_ms_write(decay, decay_ms); + if (decay_ms > 0) { + nstime_init(&decay->interval, (uint64_t)decay_ms * + KQU(1000000)); + nstime_idivide(&decay->interval, SMOOTHSTEP_NSTEPS); } - return (ret); + nstime_init(&decay->epoch, 0); + nstime_update(&decay->epoch); + decay->jitter_state = (uint64_t)(uintptr_t)decay; + arena_decay_deadline_init(decay); + decay->nunpurged = 0; + memset(decay->backlog, 0, SMOOTHSTEP_NSTEPS * sizeof(size_t)); } -void * -arena_chunk_alloc_huge(arena_t *arena, size_t usize, size_t alignment, - bool *zero) -{ - void *ret; - chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER; - size_t csize = CHUNK_CEILING(usize); - - malloc_mutex_lock(&arena->lock); - - /* Optimistically update stats. */ - if (config_stats) { - arena_huge_malloc_stats_update(arena, usize); - arena->stats.mapped += usize; +static bool +arena_decay_init(arena_decay_t *decay, extents_t *extents, ssize_t decay_ms, + decay_stats_t *stats) { + if (config_debug) { + for (size_t i = 0; i < sizeof(arena_decay_t); i++) { + assert(((char *)decay)[i] == 0); + } + decay->ceil_npages = 0; } - arena->nactive += (usize >> LG_PAGE); - - ret = chunk_alloc_cache(arena, &chunk_hooks, NULL, csize, alignment, - zero, true); - malloc_mutex_unlock(&arena->lock); - if (ret == NULL) { - ret = arena_chunk_alloc_huge_hard(arena, &chunk_hooks, usize, - alignment, zero, csize); + if (malloc_mutex_init(&decay->mtx, "decay", WITNESS_RANK_DECAY, + malloc_mutex_rank_exclusive)) { + return true; } - - if (config_stats && ret != NULL) - stats_cactive_add(usize); - return (ret); -} - -void -arena_chunk_dalloc_huge(arena_t *arena, void *chunk, size_t usize) -{ - chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER; - size_t csize; - - csize = CHUNK_CEILING(usize); - malloc_mutex_lock(&arena->lock); + decay->purging = false; + arena_decay_reinit(decay, extents, decay_ms); + /* Memory is zeroed, so there is no need to clear stats. */ if (config_stats) { - arena_huge_dalloc_stats_update(arena, usize); - arena->stats.mapped -= usize; - stats_cactive_sub(usize); - } - arena->nactive -= (usize >> LG_PAGE); - - chunk_dalloc_cache(arena, &chunk_hooks, chunk, csize, true); - malloc_mutex_unlock(&arena->lock); -} - -void -arena_chunk_ralloc_huge_similar(arena_t *arena, void *chunk, size_t oldsize, - size_t usize) -{ - - assert(CHUNK_CEILING(oldsize) == CHUNK_CEILING(usize)); - assert(oldsize != usize); - - malloc_mutex_lock(&arena->lock); - if (config_stats) - arena_huge_ralloc_stats_update(arena, oldsize, usize); - if (oldsize < usize) { - size_t udiff = usize - oldsize; - arena->nactive += udiff >> LG_PAGE; - if (config_stats) - stats_cactive_add(udiff); - } else { - size_t udiff = oldsize - usize; - arena->nactive -= udiff >> LG_PAGE; - if (config_stats) - stats_cactive_sub(udiff); + decay->stats = stats; } - malloc_mutex_unlock(&arena->lock); + return false; } -void -arena_chunk_ralloc_huge_shrink(arena_t *arena, void *chunk, size_t oldsize, - size_t usize) -{ - size_t udiff = oldsize - usize; - size_t cdiff = CHUNK_CEILING(oldsize) - CHUNK_CEILING(usize); - - malloc_mutex_lock(&arena->lock); - if (config_stats) { - arena_huge_ralloc_stats_update(arena, oldsize, usize); - if (cdiff != 0) { - arena->stats.mapped -= cdiff; - stats_cactive_sub(udiff); - } +static bool +arena_decay_ms_valid(ssize_t decay_ms) { + if (decay_ms < -1) { + return false; } - arena->nactive -= udiff >> LG_PAGE; - - if (cdiff != 0) { - chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER; - void *nchunk = (void *)((uintptr_t)chunk + - CHUNK_CEILING(usize)); - - chunk_dalloc_cache(arena, &chunk_hooks, nchunk, cdiff, true); + if (decay_ms == -1 || (uint64_t)decay_ms <= NSTIME_SEC_MAX * + KQU(1000)) { + return true; } - malloc_mutex_unlock(&arena->lock); + return false; } static bool -arena_chunk_ralloc_huge_expand_hard(arena_t *arena, chunk_hooks_t *chunk_hooks, - void *chunk, size_t oldsize, size_t usize, bool *zero, void *nchunk, - size_t udiff, size_t cdiff) -{ - bool err; - bool commit = true; - - err = (chunk_alloc_wrapper(arena, chunk_hooks, nchunk, cdiff, chunksize, - zero, &commit) == NULL); - if (err) { - /* Revert optimistic stats updates. */ - malloc_mutex_lock(&arena->lock); - if (config_stats) { - arena_huge_ralloc_stats_update_undo(arena, oldsize, - usize); - arena->stats.mapped -= cdiff; +arena_maybe_decay(tsdn_t *tsdn, arena_t *arena, arena_decay_t *decay, + extents_t *extents, bool is_background_thread) { + malloc_mutex_assert_owner(tsdn, &decay->mtx); + + /* Purge all or nothing if the option is disabled. */ + ssize_t decay_ms = arena_decay_ms_read(decay); + if (decay_ms <= 0) { + if (decay_ms == 0) { + arena_decay_to_limit(tsdn, arena, decay, extents, false, + 0, is_background_thread); } - arena->nactive -= (udiff >> LG_PAGE); - malloc_mutex_unlock(&arena->lock); - } else if (chunk_hooks->merge(chunk, CHUNK_CEILING(oldsize), nchunk, - cdiff, true, arena->ind)) { - chunk_dalloc_arena(arena, chunk_hooks, nchunk, cdiff, *zero, - true); - err = true; + return false; } - return (err); -} -bool -arena_chunk_ralloc_huge_expand(arena_t *arena, void *chunk, size_t oldsize, - size_t usize, bool *zero) -{ - bool err; - chunk_hooks_t chunk_hooks = chunk_hooks_get(arena); - void *nchunk = (void *)((uintptr_t)chunk + CHUNK_CEILING(oldsize)); - size_t udiff = usize - oldsize; - size_t cdiff = CHUNK_CEILING(usize) - CHUNK_CEILING(oldsize); - - malloc_mutex_lock(&arena->lock); - - /* Optimistically update stats. */ - if (config_stats) { - arena_huge_ralloc_stats_update(arena, oldsize, usize); - arena->stats.mapped += cdiff; - } - arena->nactive += (udiff >> LG_PAGE); - - err = (chunk_alloc_cache(arena, &arena->chunk_hooks, nchunk, cdiff, - chunksize, zero, true) == NULL); - malloc_mutex_unlock(&arena->lock); - if (err) { - err = arena_chunk_ralloc_huge_expand_hard(arena, &chunk_hooks, - chunk, oldsize, usize, zero, nchunk, udiff, - cdiff); - } else if (chunk_hooks.merge(chunk, CHUNK_CEILING(oldsize), nchunk, - cdiff, true, arena->ind)) { - chunk_dalloc_arena(arena, &chunk_hooks, nchunk, cdiff, *zero, - true); - err = true; + nstime_t time; + nstime_init(&time, 0); + nstime_update(&time); + if (unlikely(!nstime_monotonic() && nstime_compare(&decay->epoch, &time) + > 0)) { + /* + * Time went backwards. Move the epoch back in time and + * generate a new deadline, with the expectation that time + * typically flows forward for long enough periods of time that + * epochs complete. Unfortunately, this strategy is susceptible + * to clock jitter triggering premature epoch advances, but + * clock jitter estimation and compensation isn't feasible here + * because calls into this code are event-driven. + */ + nstime_copy(&decay->epoch, &time); + arena_decay_deadline_init(decay); + } else { + /* Verify that time does not go backwards. */ + assert(nstime_compare(&decay->epoch, &time) <= 0); } - if (config_stats && !err) - stats_cactive_add(udiff); - return (err); -} - -/* - * Do first-best-fit run selection, i.e. select the lowest run that best fits. - * Run sizes are quantized, so not all candidate runs are necessarily exactly - * the same size. - */ -static arena_run_t * -arena_run_first_best_fit(arena_t *arena, size_t size) -{ - size_t search_size = run_quantize_first(size); - arena_chunk_map_misc_t *key = arena_miscelm_key_create(search_size); - arena_chunk_map_misc_t *miscelm = - arena_avail_tree_nsearch(&arena->runs_avail, key); - if (miscelm == NULL) - return (NULL); - return (&miscelm->run); -} - -static arena_run_t * -arena_run_alloc_large_helper(arena_t *arena, size_t size, bool zero) -{ - arena_run_t *run = arena_run_first_best_fit(arena, s2u(size)); - if (run != NULL) { - if (arena_run_split_large(arena, run, size, zero)) - run = NULL; - } - return (run); -} - -static arena_run_t * -arena_run_alloc_large(arena_t *arena, size_t size, bool zero) -{ - arena_chunk_t *chunk; - arena_run_t *run; - - assert(size <= arena_maxrun); - assert(size == PAGE_CEILING(size)); - - /* Search the arena's chunks for the lowest best fit. */ - run = arena_run_alloc_large_helper(arena, size, zero); - if (run != NULL) - return (run); - /* - * No usable runs. Create a new chunk from which to allocate the run. + * If the deadline has been reached, advance to the current epoch and + * purge to the new limit if necessary. Note that dirty pages created + * during the current epoch are not subject to purge until a future + * epoch, so as a result purging only happens during epoch advances, or + * being triggered by background threads (scheduled event). */ - chunk = arena_chunk_alloc(arena); - if (chunk != NULL) { - run = &arena_miscelm_get(chunk, map_bias)->run; - if (arena_run_split_large(arena, run, size, zero)) - run = NULL; - return (run); + bool advance_epoch = arena_decay_deadline_reached(decay, &time); + if (advance_epoch) { + arena_decay_epoch_advance(tsdn, arena, decay, extents, &time, + is_background_thread); + } else if (is_background_thread) { + arena_decay_try_purge(tsdn, arena, decay, extents, + extents_npages_get(extents), + arena_decay_backlog_npages_limit(decay), + is_background_thread); } - /* - * arena_chunk_alloc() failed, but another thread may have made - * sufficient memory available while this one dropped arena->lock in - * arena_chunk_alloc(), so search one more time. - */ - return (arena_run_alloc_large_helper(arena, size, zero)); + return advance_epoch; } -static arena_run_t * -arena_run_alloc_small_helper(arena_t *arena, size_t size, szind_t binind) -{ - arena_run_t *run = arena_run_first_best_fit(arena, size); - if (run != NULL) { - if (arena_run_split_small(arena, run, size, binind)) - run = NULL; - } - return (run); +static ssize_t +arena_decay_ms_get(arena_decay_t *decay) { + return arena_decay_ms_read(decay); } -static arena_run_t * -arena_run_alloc_small(arena_t *arena, size_t size, szind_t binind) -{ - arena_chunk_t *chunk; - arena_run_t *run; - - assert(size <= arena_maxrun); - assert(size == PAGE_CEILING(size)); - assert(binind != BININD_INVALID); +ssize_t +arena_dirty_decay_ms_get(arena_t *arena) { + return arena_decay_ms_get(&arena->decay_dirty); +} - /* Search the arena's chunks for the lowest best fit. */ - run = arena_run_alloc_small_helper(arena, size, binind); - if (run != NULL) - return (run); +ssize_t +arena_muzzy_decay_ms_get(arena_t *arena) { + return arena_decay_ms_get(&arena->decay_muzzy); +} - /* - * No usable runs. Create a new chunk from which to allocate the run. - */ - chunk = arena_chunk_alloc(arena); - if (chunk != NULL) { - run = &arena_miscelm_get(chunk, map_bias)->run; - if (arena_run_split_small(arena, run, size, binind)) - run = NULL; - return (run); +static bool +arena_decay_ms_set(tsdn_t *tsdn, arena_t *arena, arena_decay_t *decay, + extents_t *extents, ssize_t decay_ms) { + if (!arena_decay_ms_valid(decay_ms)) { + return true; } + malloc_mutex_lock(tsdn, &decay->mtx); /* - * arena_chunk_alloc() failed, but another thread may have made - * sufficient memory available while this one dropped arena->lock in - * arena_chunk_alloc(), so search one more time. + * Restart decay backlog from scratch, which may cause many dirty pages + * to be immediately purged. It would conceptually be possible to map + * the old backlog onto the new backlog, but there is no justification + * for such complexity since decay_ms changes are intended to be + * infrequent, either between the {-1, 0, >0} states, or a one-time + * arbitrary change during initial arena configuration. */ - return (arena_run_alloc_small_helper(arena, size, binind)); -} + arena_decay_reinit(decay, extents, decay_ms); + arena_maybe_decay(tsdn, arena, decay, extents, false); + malloc_mutex_unlock(tsdn, &decay->mtx); -static bool -arena_lg_dirty_mult_valid(ssize_t lg_dirty_mult) -{ - - return (lg_dirty_mult >= -1 && lg_dirty_mult < (ssize_t)(sizeof(size_t) - << 3)); -} - -ssize_t -arena_lg_dirty_mult_get(arena_t *arena) -{ - ssize_t lg_dirty_mult; - - malloc_mutex_lock(&arena->lock); - lg_dirty_mult = arena->lg_dirty_mult; - malloc_mutex_unlock(&arena->lock); - - return (lg_dirty_mult); + return false; } bool -arena_lg_dirty_mult_set(arena_t *arena, ssize_t lg_dirty_mult) -{ - - if (!arena_lg_dirty_mult_valid(lg_dirty_mult)) - return (true); - - malloc_mutex_lock(&arena->lock); - arena->lg_dirty_mult = lg_dirty_mult; - arena_maybe_purge(arena); - malloc_mutex_unlock(&arena->lock); - - return (false); +arena_dirty_decay_ms_set(tsdn_t *tsdn, arena_t *arena, + ssize_t decay_ms) { + return arena_decay_ms_set(tsdn, arena, &arena->decay_dirty, + &arena->extents_dirty, decay_ms); } -void -arena_maybe_purge(arena_t *arena) -{ - - /* Don't purge if the option is disabled. */ - if (arena->lg_dirty_mult < 0) - return; - /* Don't recursively purge. */ - if (arena->purging) - return; - /* - * Iterate, since preventing recursive purging could otherwise leave too - * many dirty pages. - */ - while (true) { - size_t threshold = (arena->nactive >> arena->lg_dirty_mult); - if (threshold < chunk_npages) - threshold = chunk_npages; - /* - * Don't purge unless the number of purgeable pages exceeds the - * threshold. - */ - if (arena->ndirty <= threshold) - return; - arena_purge(arena, false); - } -} - -static size_t -arena_dirty_count(arena_t *arena) -{ - size_t ndirty = 0; - arena_runs_dirty_link_t *rdelm; - extent_node_t *chunkselm; - - for (rdelm = qr_next(&arena->runs_dirty, rd_link), - chunkselm = qr_next(&arena->chunks_cache, cc_link); - rdelm != &arena->runs_dirty; rdelm = qr_next(rdelm, rd_link)) { - size_t npages; - - if (rdelm == &chunkselm->rd) { - npages = extent_node_size_get(chunkselm) >> LG_PAGE; - chunkselm = qr_next(chunkselm, cc_link); - } else { - arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE( - rdelm); - arena_chunk_map_misc_t *miscelm = - arena_rd_to_miscelm(rdelm); - size_t pageind = arena_miscelm_to_pageind(miscelm); - assert(arena_mapbits_allocated_get(chunk, pageind) == - 0); - assert(arena_mapbits_large_get(chunk, pageind) == 0); - assert(arena_mapbits_dirty_get(chunk, pageind) != 0); - npages = arena_mapbits_unallocated_size_get(chunk, - pageind) >> LG_PAGE; - } - ndirty += npages; - } - - return (ndirty); +bool +arena_muzzy_decay_ms_set(tsdn_t *tsdn, arena_t *arena, + ssize_t decay_ms) { + return arena_decay_ms_set(tsdn, arena, &arena->decay_muzzy, + &arena->extents_muzzy, decay_ms); } static size_t -arena_compute_npurge(arena_t *arena, bool all) -{ - size_t npurge; +arena_stash_decayed(tsdn_t *tsdn, arena_t *arena, + extent_hooks_t **r_extent_hooks, extents_t *extents, size_t npages_limit, + extent_list_t *decay_extents) { + witness_assert_depth_to_rank(tsdn_witness_tsdp_get(tsdn), + WITNESS_RANK_CORE, 0); - /* - * Compute the minimum number of pages that this thread should try to - * purge. - */ - if (!all) { - size_t threshold = (arena->nactive >> arena->lg_dirty_mult); - threshold = threshold < chunk_npages ? chunk_npages : threshold; - - npurge = arena->ndirty - threshold; - } else - npurge = arena->ndirty; - - return (npurge); -} - -static size_t -arena_stash_dirty(arena_t *arena, chunk_hooks_t *chunk_hooks, bool all, - size_t npurge, arena_runs_dirty_link_t *purge_runs_sentinel, - extent_node_t *purge_chunks_sentinel) -{ - arena_runs_dirty_link_t *rdelm, *rdelm_next; - extent_node_t *chunkselm; + /* Stash extents according to npages_limit. */ size_t nstashed = 0; - - /* Stash at least npurge pages. */ - for (rdelm = qr_next(&arena->runs_dirty, rd_link), - chunkselm = qr_next(&arena->chunks_cache, cc_link); - rdelm != &arena->runs_dirty; rdelm = rdelm_next) { - size_t npages; - rdelm_next = qr_next(rdelm, rd_link); - - if (rdelm == &chunkselm->rd) { - extent_node_t *chunkselm_next; - bool zero; - UNUSED void *chunk; - - chunkselm_next = qr_next(chunkselm, cc_link); - /* - * Allocate. chunkselm remains valid due to the - * dalloc_node=false argument to chunk_alloc_cache(). - */ - zero = false; - chunk = chunk_alloc_cache(arena, chunk_hooks, - extent_node_addr_get(chunkselm), - extent_node_size_get(chunkselm), chunksize, &zero, - false); - assert(chunk == extent_node_addr_get(chunkselm)); - assert(zero == extent_node_zeroed_get(chunkselm)); - extent_node_dirty_insert(chunkselm, purge_runs_sentinel, - purge_chunks_sentinel); - npages = extent_node_size_get(chunkselm) >> LG_PAGE; - chunkselm = chunkselm_next; - } else { - arena_chunk_t *chunk = - (arena_chunk_t *)CHUNK_ADDR2BASE(rdelm); - arena_chunk_map_misc_t *miscelm = - arena_rd_to_miscelm(rdelm); - size_t pageind = arena_miscelm_to_pageind(miscelm); - arena_run_t *run = &miscelm->run; - size_t run_size = - arena_mapbits_unallocated_size_get(chunk, pageind); - - npages = run_size >> LG_PAGE; - - assert(pageind + npages <= chunk_npages); - assert(arena_mapbits_dirty_get(chunk, pageind) == - arena_mapbits_dirty_get(chunk, pageind+npages-1)); - - /* - * If purging the spare chunk's run, make it available - * prior to allocation. - */ - if (chunk == arena->spare) - arena_chunk_alloc(arena); - - /* Temporarily allocate the free dirty run. */ - arena_run_split_large(arena, run, run_size, false); - /* Stash. */ - if (false) - qr_new(rdelm, rd_link); /* Redundant. */ - else { - assert(qr_next(rdelm, rd_link) == rdelm); - assert(qr_prev(rdelm, rd_link) == rdelm); - } - qr_meld(purge_runs_sentinel, rdelm, rd_link); - } - - nstashed += npages; - if (!all && nstashed >= npurge) - break; + extent_t *extent; + while ((extent = extents_evict(tsdn, arena, r_extent_hooks, extents, + npages_limit)) != NULL) { + extent_list_append(decay_extents, extent); + nstashed += extent_size_get(extent) >> LG_PAGE; } - - return (nstashed); + return nstashed; } static size_t -arena_purge_stashed(arena_t *arena, chunk_hooks_t *chunk_hooks, - arena_runs_dirty_link_t *purge_runs_sentinel, - extent_node_t *purge_chunks_sentinel) -{ - size_t npurged, nmadvise; - arena_runs_dirty_link_t *rdelm; - extent_node_t *chunkselm; - - if (config_stats) +arena_decay_stashed(tsdn_t *tsdn, arena_t *arena, + extent_hooks_t **r_extent_hooks, arena_decay_t *decay, extents_t *extents, + bool all, extent_list_t *decay_extents, bool is_background_thread) { + UNUSED size_t nmadvise, nunmapped; + size_t npurged; + + if (config_stats) { nmadvise = 0; + nunmapped = 0; + } npurged = 0; - malloc_mutex_unlock(&arena->lock); - for (rdelm = qr_next(purge_runs_sentinel, rd_link), - chunkselm = qr_next(purge_chunks_sentinel, cc_link); - rdelm != purge_runs_sentinel; rdelm = qr_next(rdelm, rd_link)) { - size_t npages; - - if (rdelm == &chunkselm->rd) { - /* - * Don't actually purge the chunk here because 1) - * chunkselm is embedded in the chunk and must remain - * valid, and 2) we deallocate the chunk in - * arena_unstash_purged(), where it is destroyed, - * decommitted, or purged, depending on chunk - * deallocation policy. - */ - size_t size = extent_node_size_get(chunkselm); - npages = size >> LG_PAGE; - chunkselm = qr_next(chunkselm, cc_link); - } else { - size_t pageind, run_size, flag_unzeroed, flags, i; - bool decommitted; - arena_chunk_t *chunk = - (arena_chunk_t *)CHUNK_ADDR2BASE(rdelm); - arena_chunk_map_misc_t *miscelm = - arena_rd_to_miscelm(rdelm); - pageind = arena_miscelm_to_pageind(miscelm); - run_size = arena_mapbits_large_size_get(chunk, pageind); - npages = run_size >> LG_PAGE; - - assert(pageind + npages <= chunk_npages); - assert(!arena_mapbits_decommitted_get(chunk, pageind)); - assert(!arena_mapbits_decommitted_get(chunk, - pageind+npages-1)); - decommitted = !chunk_hooks->decommit(chunk, chunksize, - pageind << LG_PAGE, npages << LG_PAGE, arena->ind); - if (decommitted) { - flag_unzeroed = 0; - flags = CHUNK_MAP_DECOMMITTED; - } else { - flag_unzeroed = chunk_purge_wrapper(arena, - chunk_hooks, chunk, chunksize, pageind << - LG_PAGE, run_size) ? CHUNK_MAP_UNZEROED : 0; - flags = flag_unzeroed; + ssize_t muzzy_decay_ms = arena_muzzy_decay_ms_get(arena); + for (extent_t *extent = extent_list_first(decay_extents); extent != + NULL; extent = extent_list_first(decay_extents)) { + if (config_stats) { + nmadvise++; + } + size_t npages = extent_size_get(extent) >> LG_PAGE; + npurged += npages; + extent_list_remove(decay_extents, extent); + switch (extents_state_get(extents)) { + case extent_state_active: + not_reached(); + case extent_state_dirty: + if (!all && muzzy_decay_ms != 0 && + !extent_purge_lazy_wrapper(tsdn, arena, + r_extent_hooks, extent, 0, + extent_size_get(extent))) { + extents_dalloc(tsdn, arena, r_extent_hooks, + &arena->extents_muzzy, extent); + arena_background_thread_inactivity_check(tsdn, + arena, is_background_thread); + break; } - arena_mapbits_large_set(chunk, pageind+npages-1, 0, - flags); - arena_mapbits_large_set(chunk, pageind, run_size, - flags); - - /* - * Set the unzeroed flag for internal pages, now that - * chunk_purge_wrapper() has returned whether the pages - * were zeroed as a side effect of purging. This chunk - * map modification is safe even though the arena mutex - * isn't currently owned by this thread, because the run - * is marked as allocated, thus protecting it from being - * modified by any other thread. As long as these - * writes don't perturb the first and last elements' - * CHUNK_MAP_ALLOCATED bits, behavior is well defined. - */ - for (i = 1; i < npages-1; i++) { - arena_mapbits_internal_set(chunk, pageind+i, - flag_unzeroed); + /* Fall through. */ + case extent_state_muzzy: + extent_dalloc_wrapper(tsdn, arena, r_extent_hooks, + extent); + if (config_stats) { + nunmapped += npages; } + break; + case extent_state_retained: + default: + not_reached(); } - - npurged += npages; - if (config_stats) - nmadvise++; } - malloc_mutex_lock(&arena->lock); if (config_stats) { - arena->stats.nmadvise += nmadvise; - arena->stats.purged += npurged; + arena_stats_lock(tsdn, &arena->stats); + arena_stats_add_u64(tsdn, &arena->stats, &decay->stats->npurge, + 1); + arena_stats_add_u64(tsdn, &arena->stats, + &decay->stats->nmadvise, nmadvise); + arena_stats_add_u64(tsdn, &arena->stats, &decay->stats->purged, + npurged); + arena_stats_sub_zu(tsdn, &arena->stats, &arena->stats.mapped, + nunmapped << LG_PAGE); + arena_stats_unlock(tsdn, &arena->stats); } - return (npurged); + return npurged; } +/* + * npages_limit: Decay as many dirty extents as possible without violating the + * invariant: (extents_npages_get(extents) >= npages_limit) + */ static void -arena_unstash_purged(arena_t *arena, chunk_hooks_t *chunk_hooks, - arena_runs_dirty_link_t *purge_runs_sentinel, - extent_node_t *purge_chunks_sentinel) -{ - arena_runs_dirty_link_t *rdelm, *rdelm_next; - extent_node_t *chunkselm; - - /* Deallocate chunks/runs. */ - for (rdelm = qr_next(purge_runs_sentinel, rd_link), - chunkselm = qr_next(purge_chunks_sentinel, cc_link); - rdelm != purge_runs_sentinel; rdelm = rdelm_next) { - rdelm_next = qr_next(rdelm, rd_link); - if (rdelm == &chunkselm->rd) { - extent_node_t *chunkselm_next = qr_next(chunkselm, - cc_link); - void *addr = extent_node_addr_get(chunkselm); - size_t size = extent_node_size_get(chunkselm); - bool zeroed = extent_node_zeroed_get(chunkselm); - bool committed = extent_node_committed_get(chunkselm); - extent_node_dirty_remove(chunkselm); - arena_node_dalloc(arena, chunkselm); - chunkselm = chunkselm_next; - chunk_dalloc_arena(arena, chunk_hooks, addr, size, - zeroed, committed); - } else { - arena_chunk_t *chunk = - (arena_chunk_t *)CHUNK_ADDR2BASE(rdelm); - arena_chunk_map_misc_t *miscelm = - arena_rd_to_miscelm(rdelm); - size_t pageind = arena_miscelm_to_pageind(miscelm); - bool decommitted = (arena_mapbits_decommitted_get(chunk, - pageind) != 0); - arena_run_t *run = &miscelm->run; - qr_remove(rdelm, rd_link); - arena_run_dalloc(arena, run, false, true, decommitted); - } +arena_decay_to_limit(tsdn_t *tsdn, arena_t *arena, arena_decay_t *decay, + extents_t *extents, bool all, size_t npages_limit, + bool is_background_thread) { + witness_assert_depth_to_rank(tsdn_witness_tsdp_get(tsdn), + WITNESS_RANK_CORE, 1); + malloc_mutex_assert_owner(tsdn, &decay->mtx); + + if (decay->purging) { + return; } -} + decay->purging = true; + malloc_mutex_unlock(tsdn, &decay->mtx); -static void -arena_purge(arena_t *arena, bool all) -{ - chunk_hooks_t chunk_hooks = chunk_hooks_get(arena); - size_t npurge, npurgeable, npurged; - arena_runs_dirty_link_t purge_runs_sentinel; - extent_node_t purge_chunks_sentinel; + extent_hooks_t *extent_hooks = extent_hooks_get(arena); - arena->purging = true; + extent_list_t decay_extents; + extent_list_init(&decay_extents); - /* - * Calls to arena_dirty_count() are disabled even for debug builds - * because overhead grows nonlinearly as memory usage increases. - */ - if (false && config_debug) { - size_t ndirty = arena_dirty_count(arena); - assert(ndirty == arena->ndirty); + size_t npurge = arena_stash_decayed(tsdn, arena, &extent_hooks, extents, + npages_limit, &decay_extents); + if (npurge != 0) { + UNUSED size_t npurged = arena_decay_stashed(tsdn, arena, + &extent_hooks, decay, extents, all, &decay_extents, + is_background_thread); + assert(npurged == npurge); } - assert((arena->nactive >> arena->lg_dirty_mult) < arena->ndirty || all); - if (config_stats) - arena->stats.npurge++; - - npurge = arena_compute_npurge(arena, all); - qr_new(&purge_runs_sentinel, rd_link); - extent_node_dirty_linkage_init(&purge_chunks_sentinel); - - npurgeable = arena_stash_dirty(arena, &chunk_hooks, all, npurge, - &purge_runs_sentinel, &purge_chunks_sentinel); - assert(npurgeable >= npurge); - npurged = arena_purge_stashed(arena, &chunk_hooks, &purge_runs_sentinel, - &purge_chunks_sentinel); - assert(npurged == npurgeable); - arena_unstash_purged(arena, &chunk_hooks, &purge_runs_sentinel, - &purge_chunks_sentinel); - - arena->purging = false; -} - -void -arena_purge_all(arena_t *arena) -{ - - malloc_mutex_lock(&arena->lock); - arena_purge(arena, true); - malloc_mutex_unlock(&arena->lock); + malloc_mutex_lock(tsdn, &decay->mtx); + decay->purging = false; } -static void -arena_run_coalesce(arena_t *arena, arena_chunk_t *chunk, size_t *p_size, - size_t *p_run_ind, size_t *p_run_pages, size_t flag_dirty, - size_t flag_decommitted) -{ - size_t size = *p_size; - size_t run_ind = *p_run_ind; - size_t run_pages = *p_run_pages; - - /* Try to coalesce forward. */ - if (run_ind + run_pages < chunk_npages && - arena_mapbits_allocated_get(chunk, run_ind+run_pages) == 0 && - arena_mapbits_dirty_get(chunk, run_ind+run_pages) == flag_dirty && - arena_mapbits_decommitted_get(chunk, run_ind+run_pages) == - flag_decommitted) { - size_t nrun_size = arena_mapbits_unallocated_size_get(chunk, - run_ind+run_pages); - size_t nrun_pages = nrun_size >> LG_PAGE; - - /* - * Remove successor from runs_avail; the coalesced run is - * inserted later. - */ - assert(arena_mapbits_unallocated_size_get(chunk, - run_ind+run_pages+nrun_pages-1) == nrun_size); - assert(arena_mapbits_dirty_get(chunk, - run_ind+run_pages+nrun_pages-1) == flag_dirty); - assert(arena_mapbits_decommitted_get(chunk, - run_ind+run_pages+nrun_pages-1) == flag_decommitted); - arena_avail_remove(arena, chunk, run_ind+run_pages, nrun_pages); - - /* - * If the successor is dirty, remove it from the set of dirty - * pages. - */ - if (flag_dirty != 0) { - arena_run_dirty_remove(arena, chunk, run_ind+run_pages, - nrun_pages); - } +static bool +arena_decay_impl(tsdn_t *tsdn, arena_t *arena, arena_decay_t *decay, + extents_t *extents, bool is_background_thread, bool all) { + if (all) { + malloc_mutex_lock(tsdn, &decay->mtx); + arena_decay_to_limit(tsdn, arena, decay, extents, all, 0, + is_background_thread); + malloc_mutex_unlock(tsdn, &decay->mtx); - size += nrun_size; - run_pages += nrun_pages; + return false; + } - arena_mapbits_unallocated_size_set(chunk, run_ind, size); - arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1, - size); + if (malloc_mutex_trylock(tsdn, &decay->mtx)) { + /* No need to wait if another thread is in progress. */ + return true; } - /* Try to coalesce backward. */ - if (run_ind > map_bias && arena_mapbits_allocated_get(chunk, - run_ind-1) == 0 && arena_mapbits_dirty_get(chunk, run_ind-1) == - flag_dirty && arena_mapbits_decommitted_get(chunk, run_ind-1) == - flag_decommitted) { - size_t prun_size = arena_mapbits_unallocated_size_get(chunk, - run_ind-1); - size_t prun_pages = prun_size >> LG_PAGE; + bool epoch_advanced = arena_maybe_decay(tsdn, arena, decay, extents, + is_background_thread); + size_t npages_new; + if (epoch_advanced) { + /* Backlog is updated on epoch advance. */ + npages_new = decay->backlog[SMOOTHSTEP_NSTEPS-1]; + } + malloc_mutex_unlock(tsdn, &decay->mtx); - run_ind -= prun_pages; + if (have_background_thread && background_thread_enabled() && + epoch_advanced && !is_background_thread) { + background_thread_interval_check(tsdn, arena, decay, npages_new); + } - /* - * Remove predecessor from runs_avail; the coalesced run is - * inserted later. - */ - assert(arena_mapbits_unallocated_size_get(chunk, run_ind) == - prun_size); - assert(arena_mapbits_dirty_get(chunk, run_ind) == flag_dirty); - assert(arena_mapbits_decommitted_get(chunk, run_ind) == - flag_decommitted); - arena_avail_remove(arena, chunk, run_ind, prun_pages); + return false; +} - /* - * If the predecessor is dirty, remove it from the set of dirty - * pages. - */ - if (flag_dirty != 0) { - arena_run_dirty_remove(arena, chunk, run_ind, - prun_pages); - } +static bool +arena_decay_dirty(tsdn_t *tsdn, arena_t *arena, bool is_background_thread, + bool all) { + return arena_decay_impl(tsdn, arena, &arena->decay_dirty, + &arena->extents_dirty, is_background_thread, all); +} - size += prun_size; - run_pages += prun_pages; +static bool +arena_decay_muzzy(tsdn_t *tsdn, arena_t *arena, bool is_background_thread, + bool all) { + return arena_decay_impl(tsdn, arena, &arena->decay_muzzy, + &arena->extents_muzzy, is_background_thread, all); +} - arena_mapbits_unallocated_size_set(chunk, run_ind, size); - arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1, - size); +void +arena_decay(tsdn_t *tsdn, arena_t *arena, bool is_background_thread, bool all) { + if (arena_decay_dirty(tsdn, arena, is_background_thread, all)) { + return; } + arena_decay_muzzy(tsdn, arena, is_background_thread, all); +} + +static void +arena_slab_dalloc(tsdn_t *tsdn, arena_t *arena, extent_t *slab) { + arena_nactive_sub(arena, extent_size_get(slab) >> LG_PAGE); - *p_size = size; - *p_run_ind = run_ind; - *p_run_pages = run_pages; + extent_hooks_t *extent_hooks = EXTENT_HOOKS_INITIALIZER; + arena_extents_dirty_dalloc(tsdn, arena, &extent_hooks, slab); } -static size_t -arena_run_size_get(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, - size_t run_ind) -{ - size_t size; - - assert(run_ind >= map_bias); - assert(run_ind < chunk_npages); - - if (arena_mapbits_large_get(chunk, run_ind) != 0) { - size = arena_mapbits_large_size_get(chunk, run_ind); - assert(size == PAGE || arena_mapbits_large_size_get(chunk, - run_ind+(size>>LG_PAGE)-1) == 0); - } else { - arena_bin_info_t *bin_info = &arena_bin_info[run->binind]; - size = bin_info->run_size; - } +static void +arena_bin_slabs_nonfull_insert(arena_bin_t *bin, extent_t *slab) { + assert(extent_nfree_get(slab) > 0); + extent_heap_insert(&bin->slabs_nonfull, slab); +} - return (size); +static void +arena_bin_slabs_nonfull_remove(arena_bin_t *bin, extent_t *slab) { + extent_heap_remove(&bin->slabs_nonfull, slab); } -static bool -arena_run_decommit(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run) -{ - arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run); - size_t run_ind = arena_miscelm_to_pageind(miscelm); - size_t offset = run_ind << LG_PAGE; - size_t length = arena_run_size_get(arena, chunk, run, run_ind); +static extent_t * +arena_bin_slabs_nonfull_tryget(arena_bin_t *bin) { + extent_t *slab = extent_heap_remove_first(&bin->slabs_nonfull); + if (slab == NULL) { + return NULL; + } + if (config_stats) { + bin->stats.reslabs++; + } + return slab; +} - return (arena->chunk_hooks.decommit(chunk, chunksize, offset, length, - arena->ind)); +static void +arena_bin_slabs_full_insert(arena_t *arena, arena_bin_t *bin, extent_t *slab) { + assert(extent_nfree_get(slab) == 0); + /* + * Tracking extents is required by arena_reset, which is not allowed + * for auto arenas. Bypass this step to avoid touching the extent + * linkage (often results in cache misses) for auto arenas. + */ + if (arena_is_auto(arena)) { + return; + } + extent_list_append(&bin->slabs_full, slab); } static void -arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty, bool cleaned, - bool decommitted) -{ - arena_chunk_t *chunk; - arena_chunk_map_misc_t *miscelm; - size_t size, run_ind, run_pages, flag_dirty, flag_decommitted; - - chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); - miscelm = arena_run_to_miscelm(run); - run_ind = arena_miscelm_to_pageind(miscelm); - assert(run_ind >= map_bias); - assert(run_ind < chunk_npages); - size = arena_run_size_get(arena, chunk, run, run_ind); - run_pages = (size >> LG_PAGE); - arena_cactive_update(arena, 0, run_pages); - arena->nactive -= run_pages; +arena_bin_slabs_full_remove(arena_t *arena, arena_bin_t *bin, extent_t *slab) { + if (arena_is_auto(arena)) { + return; + } + extent_list_remove(&bin->slabs_full, slab); +} +void +arena_reset(tsd_t *tsd, arena_t *arena) { /* - * The run is dirty if the caller claims to have dirtied it, as well as - * if it was already dirty before being allocated and the caller - * doesn't claim to have cleaned it. + * Locking in this function is unintuitive. The caller guarantees that + * no concurrent operations are happening in this arena, but there are + * still reasons that some locking is necessary: + * + * - Some of the functions in the transitive closure of calls assume + * appropriate locks are held, and in some cases these locks are + * temporarily dropped to avoid lock order reversal or deadlock due to + * reentry. + * - mallctl("epoch", ...) may concurrently refresh stats. While + * strictly speaking this is a "concurrent operation", disallowing + * stats refreshes would impose an inconvenient burden. */ - assert(arena_mapbits_dirty_get(chunk, run_ind) == - arena_mapbits_dirty_get(chunk, run_ind+run_pages-1)); - if (!cleaned && !decommitted && arena_mapbits_dirty_get(chunk, run_ind) - != 0) - dirty = true; - flag_dirty = dirty ? CHUNK_MAP_DIRTY : 0; - flag_decommitted = decommitted ? CHUNK_MAP_DECOMMITTED : 0; - - /* Mark pages as unallocated in the chunk map. */ - if (dirty || decommitted) { - size_t flags = flag_dirty | flag_decommitted; - arena_mapbits_unallocated_set(chunk, run_ind, size, flags); - arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size, - flags); - } else { - arena_mapbits_unallocated_set(chunk, run_ind, size, - arena_mapbits_unzeroed_get(chunk, run_ind)); - arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size, - arena_mapbits_unzeroed_get(chunk, run_ind+run_pages-1)); - } - arena_run_coalesce(arena, chunk, &size, &run_ind, &run_pages, - flag_dirty, flag_decommitted); + /* Large allocations. */ + malloc_mutex_lock(tsd_tsdn(tsd), &arena->large_mtx); - /* Insert into runs_avail, now that coalescing is complete. */ - assert(arena_mapbits_unallocated_size_get(chunk, run_ind) == - arena_mapbits_unallocated_size_get(chunk, run_ind+run_pages-1)); - assert(arena_mapbits_dirty_get(chunk, run_ind) == - arena_mapbits_dirty_get(chunk, run_ind+run_pages-1)); - assert(arena_mapbits_decommitted_get(chunk, run_ind) == - arena_mapbits_decommitted_get(chunk, run_ind+run_pages-1)); - arena_avail_insert(arena, chunk, run_ind, run_pages); + for (extent_t *extent = extent_list_first(&arena->large); extent != + NULL; extent = extent_list_first(&arena->large)) { + void *ptr = extent_base_get(extent); + size_t usize; - if (dirty) - arena_run_dirty_insert(arena, chunk, run_ind, run_pages); + malloc_mutex_unlock(tsd_tsdn(tsd), &arena->large_mtx); + alloc_ctx_t alloc_ctx; + rtree_ctx_t *rtree_ctx = tsd_rtree_ctx(tsd); + rtree_szind_slab_read(tsd_tsdn(tsd), &extents_rtree, rtree_ctx, + (uintptr_t)ptr, true, &alloc_ctx.szind, &alloc_ctx.slab); + assert(alloc_ctx.szind != NSIZES); - /* Deallocate chunk if it is now completely unused. */ - if (size == arena_maxrun) { - assert(run_ind == map_bias); - assert(run_pages == (arena_maxrun >> LG_PAGE)); - arena_chunk_dalloc(arena, chunk); + if (config_stats || (config_prof && opt_prof)) { + usize = sz_index2size(alloc_ctx.szind); + assert(usize == isalloc(tsd_tsdn(tsd), ptr)); + } + /* Remove large allocation from prof sample set. */ + if (config_prof && opt_prof) { + prof_free(tsd, ptr, usize, &alloc_ctx); + } + large_dalloc(tsd_tsdn(tsd), extent); + malloc_mutex_lock(tsd_tsdn(tsd), &arena->large_mtx); } + malloc_mutex_unlock(tsd_tsdn(tsd), &arena->large_mtx); - /* - * It is okay to do dirty page processing here even if the chunk was - * deallocated above, since in that case it is the spare. Waiting - * until after possible chunk deallocation to do dirty processing - * allows for an old spare to be fully deallocated, thus decreasing the - * chances of spuriously crossing the dirty page purging threshold. - */ - if (dirty) - arena_maybe_purge(arena); -} - -static void -arena_run_dalloc_decommit(arena_t *arena, arena_chunk_t *chunk, - arena_run_t *run) -{ - bool committed = arena_run_decommit(arena, chunk, run); + /* Bins. */ + for (unsigned i = 0; i < NBINS; i++) { + extent_t *slab; + arena_bin_t *bin = &arena->bins[i]; + malloc_mutex_lock(tsd_tsdn(tsd), &bin->lock); + if (bin->slabcur != NULL) { + slab = bin->slabcur; + bin->slabcur = NULL; + malloc_mutex_unlock(tsd_tsdn(tsd), &bin->lock); + arena_slab_dalloc(tsd_tsdn(tsd), arena, slab); + malloc_mutex_lock(tsd_tsdn(tsd), &bin->lock); + } + while ((slab = extent_heap_remove_first(&bin->slabs_nonfull)) != + NULL) { + malloc_mutex_unlock(tsd_tsdn(tsd), &bin->lock); + arena_slab_dalloc(tsd_tsdn(tsd), arena, slab); + malloc_mutex_lock(tsd_tsdn(tsd), &bin->lock); + } + for (slab = extent_list_first(&bin->slabs_full); slab != NULL; + slab = extent_list_first(&bin->slabs_full)) { + arena_bin_slabs_full_remove(arena, bin, slab); + malloc_mutex_unlock(tsd_tsdn(tsd), &bin->lock); + arena_slab_dalloc(tsd_tsdn(tsd), arena, slab); + malloc_mutex_lock(tsd_tsdn(tsd), &bin->lock); + } + if (config_stats) { + bin->stats.curregs = 0; + bin->stats.curslabs = 0; + } + malloc_mutex_unlock(tsd_tsdn(tsd), &bin->lock); + } - arena_run_dalloc(arena, run, committed, false, !committed); + atomic_store_zu(&arena->nactive, 0, ATOMIC_RELAXED); } static void -arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, - size_t oldsize, size_t newsize) -{ - arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run); - size_t pageind = arena_miscelm_to_pageind(miscelm); - size_t head_npages = (oldsize - newsize) >> LG_PAGE; - size_t flag_dirty = arena_mapbits_dirty_get(chunk, pageind); - size_t flag_decommitted = arena_mapbits_decommitted_get(chunk, pageind); - size_t flag_unzeroed_mask = (flag_dirty | flag_decommitted) == 0 ? - CHUNK_MAP_UNZEROED : 0; - - assert(oldsize > newsize); - +arena_destroy_retained(tsdn_t *tsdn, arena_t *arena) { /* - * Update the chunk map so that arena_run_dalloc() can treat the - * leading run as separately allocated. Set the last element of each - * run first, in case of single-page runs. + * Iterate over the retained extents and destroy them. This gives the + * extent allocator underlying the extent hooks an opportunity to unmap + * all retained memory without having to keep its own metadata + * structures. In practice, virtual memory for dss-allocated extents is + * leaked here, so best practice is to avoid dss for arenas to be + * destroyed, or provide custom extent hooks that track retained + * dss-based extents for later reuse. */ - assert(arena_mapbits_large_size_get(chunk, pageind) == oldsize); - arena_mapbits_large_set(chunk, pageind+head_npages-1, 0, flag_dirty | - (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, - pageind+head_npages-1))); - arena_mapbits_large_set(chunk, pageind, oldsize-newsize, flag_dirty | - (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, pageind))); - - if (config_debug) { - UNUSED size_t tail_npages = newsize >> LG_PAGE; - assert(arena_mapbits_large_size_get(chunk, - pageind+head_npages+tail_npages-1) == 0); - assert(arena_mapbits_dirty_get(chunk, - pageind+head_npages+tail_npages-1) == flag_dirty); + extent_hooks_t *extent_hooks = extent_hooks_get(arena); + extent_t *extent; + while ((extent = extents_evict(tsdn, arena, &extent_hooks, + &arena->extents_retained, 0)) != NULL) { + extent_destroy_wrapper(tsdn, arena, &extent_hooks, extent); } - arena_mapbits_large_set(chunk, pageind+head_npages, newsize, - flag_dirty | (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, - pageind+head_npages))); - - arena_run_dalloc(arena, run, false, false, (flag_decommitted != 0)); } -static void -arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, - size_t oldsize, size_t newsize, bool dirty) -{ - arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run); - size_t pageind = arena_miscelm_to_pageind(miscelm); - size_t head_npages = newsize >> LG_PAGE; - size_t flag_dirty = arena_mapbits_dirty_get(chunk, pageind); - size_t flag_decommitted = arena_mapbits_decommitted_get(chunk, pageind); - size_t flag_unzeroed_mask = (flag_dirty | flag_decommitted) == 0 ? - CHUNK_MAP_UNZEROED : 0; - arena_chunk_map_misc_t *tail_miscelm; - arena_run_t *tail_run; - - assert(oldsize > newsize); +void +arena_destroy(tsd_t *tsd, arena_t *arena) { + assert(base_ind_get(arena->base) >= narenas_auto); + assert(arena_nthreads_get(arena, false) == 0); + assert(arena_nthreads_get(arena, true) == 0); /* - * Update the chunk map so that arena_run_dalloc() can treat the - * trailing run as separately allocated. Set the last element of each - * run first, in case of single-page runs. + * No allocations have occurred since arena_reset() was called. + * Furthermore, the caller (arena_i_destroy_ctl()) purged all cached + * extents, so only retained extents may remain. */ - assert(arena_mapbits_large_size_get(chunk, pageind) == oldsize); - arena_mapbits_large_set(chunk, pageind+head_npages-1, 0, flag_dirty | - (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, - pageind+head_npages-1))); - arena_mapbits_large_set(chunk, pageind, newsize, flag_dirty | - (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, pageind))); + assert(extents_npages_get(&arena->extents_dirty) == 0); + assert(extents_npages_get(&arena->extents_muzzy) == 0); - if (config_debug) { - UNUSED size_t tail_npages = (oldsize - newsize) >> LG_PAGE; - assert(arena_mapbits_large_size_get(chunk, - pageind+head_npages+tail_npages-1) == 0); - assert(arena_mapbits_dirty_get(chunk, - pageind+head_npages+tail_npages-1) == flag_dirty); - } - arena_mapbits_large_set(chunk, pageind+head_npages, oldsize-newsize, - flag_dirty | (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, - pageind+head_npages))); + /* Deallocate retained memory. */ + arena_destroy_retained(tsd_tsdn(tsd), arena); + + /* + * Remove the arena pointer from the arenas array. We rely on the fact + * that there is no way for the application to get a dirty read from the + * arenas array unless there is an inherent race in the application + * involving access of an arena being concurrently destroyed. The + * application must synchronize knowledge of the arena's validity, so as + * long as we use an atomic write to update the arenas array, the + * application will get a clean read any time after it synchronizes + * knowledge that the arena is no longer valid. + */ + arena_set(base_ind_get(arena->base), NULL); - tail_miscelm = arena_miscelm_get(chunk, pageind + head_npages); - tail_run = &tail_miscelm->run; - arena_run_dalloc(arena, tail_run, dirty, false, (flag_decommitted != - 0)); + /* + * Destroy the base allocator, which manages all metadata ever mapped by + * this arena. + */ + base_delete(tsd_tsdn(tsd), arena->base); } -static arena_run_t * -arena_bin_runs_first(arena_bin_t *bin) -{ - arena_chunk_map_misc_t *miscelm = arena_run_tree_first(&bin->runs); - if (miscelm != NULL) - return (&miscelm->run); +static extent_t * +arena_slab_alloc_hard(tsdn_t *tsdn, arena_t *arena, + extent_hooks_t **r_extent_hooks, const arena_bin_info_t *bin_info, + szind_t szind) { + extent_t *slab; + bool zero, commit; - return (NULL); -} + witness_assert_depth_to_rank(tsdn_witness_tsdp_get(tsdn), + WITNESS_RANK_CORE, 0); -static void -arena_bin_runs_insert(arena_bin_t *bin, arena_run_t *run) -{ - arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run); + zero = false; + commit = true; + slab = extent_alloc_wrapper(tsdn, arena, r_extent_hooks, NULL, + bin_info->slab_size, 0, PAGE, true, szind, &zero, &commit); - assert(arena_run_tree_search(&bin->runs, miscelm) == NULL); + if (config_stats && slab != NULL) { + arena_stats_mapped_add(tsdn, &arena->stats, + bin_info->slab_size); + } - arena_run_tree_insert(&bin->runs, miscelm); + return slab; } -static void -arena_bin_runs_remove(arena_bin_t *bin, arena_run_t *run) -{ - arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run); +static extent_t * +arena_slab_alloc(tsdn_t *tsdn, arena_t *arena, szind_t binind, + const arena_bin_info_t *bin_info) { + witness_assert_depth_to_rank(tsdn_witness_tsdp_get(tsdn), + WITNESS_RANK_CORE, 0); - assert(arena_run_tree_search(&bin->runs, miscelm) != NULL); + extent_hooks_t *extent_hooks = EXTENT_HOOKS_INITIALIZER; + szind_t szind = sz_size2index(bin_info->reg_size); + bool zero = false; + bool commit = true; + extent_t *slab = extents_alloc(tsdn, arena, &extent_hooks, + &arena->extents_dirty, NULL, bin_info->slab_size, 0, PAGE, true, + binind, &zero, &commit); + if (slab == NULL) { + slab = extents_alloc(tsdn, arena, &extent_hooks, + &arena->extents_muzzy, NULL, bin_info->slab_size, 0, PAGE, + true, binind, &zero, &commit); + } + if (slab == NULL) { + slab = arena_slab_alloc_hard(tsdn, arena, &extent_hooks, + bin_info, szind); + if (slab == NULL) { + return NULL; + } + } + assert(extent_slab_get(slab)); - arena_run_tree_remove(&bin->runs, miscelm); -} + /* Initialize slab internals. */ + arena_slab_data_t *slab_data = extent_slab_data_get(slab); + extent_nfree_set(slab, bin_info->nregs); + bitmap_init(slab_data->bitmap, &bin_info->bitmap_info, false); -static arena_run_t * -arena_bin_nonfull_run_tryget(arena_bin_t *bin) -{ - arena_run_t *run = arena_bin_runs_first(bin); - if (run != NULL) { - arena_bin_runs_remove(bin, run); - if (config_stats) - bin->stats.reruns++; - } - return (run); + arena_nactive_add(arena, extent_size_get(slab) >> LG_PAGE); + + return slab; } -static arena_run_t * -arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin) -{ - arena_run_t *run; - szind_t binind; - arena_bin_info_t *bin_info; +static extent_t * +arena_bin_nonfull_slab_get(tsdn_t *tsdn, arena_t *arena, arena_bin_t *bin, + szind_t binind) { + extent_t *slab; + const arena_bin_info_t *bin_info; - /* Look for a usable run. */ - run = arena_bin_nonfull_run_tryget(bin); - if (run != NULL) - return (run); - /* No existing runs have any space available. */ + /* Look for a usable slab. */ + slab = arena_bin_slabs_nonfull_tryget(bin); + if (slab != NULL) { + return slab; + } + /* No existing slabs have any space available. */ - binind = arena_bin_index(arena, bin); bin_info = &arena_bin_info[binind]; - /* Allocate a new run. */ - malloc_mutex_unlock(&bin->lock); + /* Allocate a new slab. */ + malloc_mutex_unlock(tsdn, &bin->lock); /******************************/ - malloc_mutex_lock(&arena->lock); - run = arena_run_alloc_small(arena, bin_info->run_size, binind); - if (run != NULL) { - /* Initialize run internals. */ - run->binind = binind; - run->nfree = bin_info->nregs; - bitmap_init(run->bitmap, &bin_info->bitmap_info); - } - malloc_mutex_unlock(&arena->lock); + slab = arena_slab_alloc(tsdn, arena, binind, bin_info); /********************************/ - malloc_mutex_lock(&bin->lock); - if (run != NULL) { + malloc_mutex_lock(tsdn, &bin->lock); + if (slab != NULL) { if (config_stats) { - bin->stats.nruns++; - bin->stats.curruns++; + bin->stats.nslabs++; + bin->stats.curslabs++; } - return (run); + return slab; } /* - * arena_run_alloc_small() failed, but another thread may have made + * arena_slab_alloc() failed, but another thread may have made * sufficient memory available while this one dropped bin->lock above, * so search one more time. */ - run = arena_bin_nonfull_run_tryget(bin); - if (run != NULL) - return (run); + slab = arena_bin_slabs_nonfull_tryget(bin); + if (slab != NULL) { + return slab; + } - return (NULL); + return NULL; } -/* Re-fill bin->runcur, then call arena_run_reg_alloc(). */ +/* Re-fill bin->slabcur, then call arena_slab_reg_alloc(). */ static void * -arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin) -{ - szind_t binind; - arena_bin_info_t *bin_info; - arena_run_t *run; +arena_bin_malloc_hard(tsdn_t *tsdn, arena_t *arena, arena_bin_t *bin, + szind_t binind) { + const arena_bin_info_t *bin_info; + extent_t *slab; - binind = arena_bin_index(arena, bin); bin_info = &arena_bin_info[binind]; - bin->runcur = NULL; - run = arena_bin_nonfull_run_get(arena, bin); - if (bin->runcur != NULL && bin->runcur->nfree > 0) { + if (!arena_is_auto(arena) && bin->slabcur != NULL) { + arena_bin_slabs_full_insert(arena, bin, bin->slabcur); + bin->slabcur = NULL; + } + slab = arena_bin_nonfull_slab_get(tsdn, arena, bin, binind); + if (bin->slabcur != NULL) { /* - * Another thread updated runcur while this one ran without the - * bin lock in arena_bin_nonfull_run_get(). + * Another thread updated slabcur while this one ran without the + * bin lock in arena_bin_nonfull_slab_get(). */ - void *ret; - assert(bin->runcur->nfree > 0); - ret = arena_run_reg_alloc(bin->runcur, bin_info); - if (run != NULL) { - arena_chunk_t *chunk; - - /* - * arena_run_alloc_small() may have allocated run, or - * it may have pulled run from the bin's run tree. - * Therefore it is unsafe to make any assumptions about - * how run has previously been used, and - * arena_bin_lower_run() must be called, as if a region - * were just deallocated from the run. - */ - chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); - if (run->nfree == bin_info->nregs) - arena_dalloc_bin_run(arena, chunk, run, bin); - else - arena_bin_lower_run(arena, chunk, run, bin); + if (extent_nfree_get(bin->slabcur) > 0) { + void *ret = arena_slab_reg_alloc(tsdn, bin->slabcur, + bin_info); + if (slab != NULL) { + /* + * arena_slab_alloc() may have allocated slab, + * or it may have been pulled from + * slabs_nonfull. Therefore it is unsafe to + * make any assumptions about how slab has + * previously been used, and + * arena_bin_lower_slab() must be called, as if + * a region were just deallocated from the slab. + */ + if (extent_nfree_get(slab) == bin_info->nregs) { + arena_dalloc_bin_slab(tsdn, arena, slab, + bin); + } else { + arena_bin_lower_slab(tsdn, arena, slab, + bin); + } + } + return ret; } - return (ret); - } - if (run == NULL) - return (NULL); + arena_bin_slabs_full_insert(arena, bin, bin->slabcur); + bin->slabcur = NULL; + } - bin->runcur = run; + if (slab == NULL) { + return NULL; + } + bin->slabcur = slab; - assert(bin->runcur->nfree > 0); + assert(extent_nfree_get(bin->slabcur) > 0); - return (arena_run_reg_alloc(bin->runcur, bin_info)); + return arena_slab_reg_alloc(tsdn, slab, bin_info); } void -arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin, szind_t binind, - uint64_t prof_accumbytes) -{ +arena_tcache_fill_small(tsdn_t *tsdn, arena_t *arena, tcache_t *tcache, + tcache_bin_t *tbin, szind_t binind, uint64_t prof_accumbytes) { unsigned i, nfill; arena_bin_t *bin; assert(tbin->ncached == 0); - if (config_prof && arena_prof_accum(arena, prof_accumbytes)) - prof_idump(); + if (config_prof && arena_prof_accum(tsdn, arena, prof_accumbytes)) { + prof_idump(tsdn); + } bin = &arena->bins[binind]; - malloc_mutex_lock(&bin->lock); + malloc_mutex_lock(tsdn, &bin->lock); for (i = 0, nfill = (tcache_bin_info[binind].ncached_max >> - tbin->lg_fill_div); i < nfill; i++) { - arena_run_t *run; + tcache->lg_fill_div[binind]); i < nfill; i++) { + extent_t *slab; void *ptr; - if ((run = bin->runcur) != NULL && run->nfree > 0) - ptr = arena_run_reg_alloc(run, &arena_bin_info[binind]); - else - ptr = arena_bin_malloc_hard(arena, bin); + if ((slab = bin->slabcur) != NULL && extent_nfree_get(slab) > + 0) { + ptr = arena_slab_reg_alloc(tsdn, slab, + &arena_bin_info[binind]); + } else { + ptr = arena_bin_malloc_hard(tsdn, arena, bin, binind); + } if (ptr == NULL) { /* * OOM. tbin->avail isn't yet filled down to its first * element, so the successful allocations (if any) must - * be moved to the base of tbin->avail before bailing - * out. + * be moved just before tbin->avail before bailing out. */ if (i > 0) { - memmove(tbin->avail, &tbin->avail[nfill - i], + memmove(tbin->avail - i, tbin->avail - nfill, i * sizeof(void *)); } break; @@ -2024,7 +1459,7 @@ arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin, szind_t binind, true); } /* Insert such that low regions get used first. */ - tbin->avail[nfill - 1 - i] = ptr; + *(tbin->avail - nfill + i) = ptr; } if (config_stats) { bin->stats.nmalloc += i; @@ -2033,139 +1468,46 @@ arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin, szind_t binind, bin->stats.nfills++; tbin->tstats.nrequests = 0; } - malloc_mutex_unlock(&bin->lock); + malloc_mutex_unlock(tsdn, &bin->lock); tbin->ncached = i; + arena_decay_tick(tsdn, arena); } void -arena_alloc_junk_small(void *ptr, arena_bin_info_t *bin_info, bool zero) -{ - - if (zero) { - size_t redzone_size = bin_info->redzone_size; - memset((void *)((uintptr_t)ptr - redzone_size), 0xa5, - redzone_size); - memset((void *)((uintptr_t)ptr + bin_info->reg_size), 0xa5, - redzone_size); - } else { - memset((void *)((uintptr_t)ptr - bin_info->redzone_size), 0xa5, - bin_info->reg_interval); +arena_alloc_junk_small(void *ptr, const arena_bin_info_t *bin_info, bool zero) { + if (!zero) { + memset(ptr, JEMALLOC_ALLOC_JUNK, bin_info->reg_size); } } -#ifdef JEMALLOC_JET -#undef arena_redzone_corruption -#define arena_redzone_corruption JEMALLOC_N(arena_redzone_corruption_impl) -#endif static void -arena_redzone_corruption(void *ptr, size_t usize, bool after, - size_t offset, uint8_t byte) -{ - - malloc_printf("<jemalloc>: Corrupt redzone %zu byte%s %s %p " - "(size %zu), byte=%#x\n", offset, (offset == 1) ? "" : "s", - after ? "after" : "before", ptr, usize, byte); -} -#ifdef JEMALLOC_JET -#undef arena_redzone_corruption -#define arena_redzone_corruption JEMALLOC_N(arena_redzone_corruption) -arena_redzone_corruption_t *arena_redzone_corruption = - JEMALLOC_N(arena_redzone_corruption_impl); -#endif - -static void -arena_redzones_validate(void *ptr, arena_bin_info_t *bin_info, bool reset) -{ - bool error = false; - - if (opt_junk_alloc) { - size_t size = bin_info->reg_size; - size_t redzone_size = bin_info->redzone_size; - size_t i; - - for (i = 1; i <= redzone_size; i++) { - uint8_t *byte = (uint8_t *)((uintptr_t)ptr - i); - if (*byte != 0xa5) { - error = true; - arena_redzone_corruption(ptr, size, false, i, - *byte); - if (reset) - *byte = 0xa5; - } - } - for (i = 0; i < redzone_size; i++) { - uint8_t *byte = (uint8_t *)((uintptr_t)ptr + size + i); - if (*byte != 0xa5) { - error = true; - arena_redzone_corruption(ptr, size, true, i, - *byte); - if (reset) - *byte = 0xa5; - } - } - } - - if (opt_abort && error) - abort(); +arena_dalloc_junk_small_impl(void *ptr, const arena_bin_info_t *bin_info) { + memset(ptr, JEMALLOC_FREE_JUNK, bin_info->reg_size); } +arena_dalloc_junk_small_t *JET_MUTABLE arena_dalloc_junk_small = + arena_dalloc_junk_small_impl; -#ifdef JEMALLOC_JET -#undef arena_dalloc_junk_small -#define arena_dalloc_junk_small JEMALLOC_N(arena_dalloc_junk_small_impl) -#endif -void -arena_dalloc_junk_small(void *ptr, arena_bin_info_t *bin_info) -{ - size_t redzone_size = bin_info->redzone_size; - - arena_redzones_validate(ptr, bin_info, false); - memset((void *)((uintptr_t)ptr - redzone_size), 0x5a, - bin_info->reg_interval); -} -#ifdef JEMALLOC_JET -#undef arena_dalloc_junk_small -#define arena_dalloc_junk_small JEMALLOC_N(arena_dalloc_junk_small) -arena_dalloc_junk_small_t *arena_dalloc_junk_small = - JEMALLOC_N(arena_dalloc_junk_small_impl); -#endif - -void -arena_quarantine_junk_small(void *ptr, size_t usize) -{ - szind_t binind; - arena_bin_info_t *bin_info; - cassert(config_fill); - assert(opt_junk_free); - assert(opt_quarantine); - assert(usize <= SMALL_MAXCLASS); - - binind = size2index(usize); - bin_info = &arena_bin_info[binind]; - arena_redzones_validate(ptr, bin_info, true); -} - -void * -arena_malloc_small(arena_t *arena, size_t size, bool zero) -{ +static void * +arena_malloc_small(tsdn_t *tsdn, arena_t *arena, szind_t binind, bool zero) { void *ret; arena_bin_t *bin; - arena_run_t *run; - szind_t binind; + size_t usize; + extent_t *slab; - binind = size2index(size); assert(binind < NBINS); bin = &arena->bins[binind]; - size = index2size(binind); + usize = sz_index2size(binind); - malloc_mutex_lock(&bin->lock); - if ((run = bin->runcur) != NULL && run->nfree > 0) - ret = arena_run_reg_alloc(run, &arena_bin_info[binind]); - else - ret = arena_bin_malloc_hard(arena, bin); + malloc_mutex_lock(tsdn, &bin->lock); + if ((slab = bin->slabcur) != NULL && extent_nfree_get(slab) > 0) { + ret = arena_slab_reg_alloc(tsdn, slab, &arena_bin_info[binind]); + } else { + ret = arena_bin_malloc_hard(tsdn, arena, bin, binind); + } if (ret == NULL) { - malloc_mutex_unlock(&bin->lock); - return (NULL); + malloc_mutex_unlock(tsdn, &bin->lock); + return NULL; } if (config_stats) { @@ -2173,870 +1515,437 @@ arena_malloc_small(arena_t *arena, size_t size, bool zero) bin->stats.nrequests++; bin->stats.curregs++; } - malloc_mutex_unlock(&bin->lock); - if (config_prof && !isthreaded && arena_prof_accum(arena, size)) - prof_idump(); + malloc_mutex_unlock(tsdn, &bin->lock); + if (config_prof && arena_prof_accum(tsdn, arena, usize)) { + prof_idump(tsdn); + } if (!zero) { if (config_fill) { if (unlikely(opt_junk_alloc)) { arena_alloc_junk_small(ret, &arena_bin_info[binind], false); - } else if (unlikely(opt_zero)) - memset(ret, 0, size); + } else if (unlikely(opt_zero)) { + memset(ret, 0, usize); + } } - JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, size); } else { if (config_fill && unlikely(opt_junk_alloc)) { arena_alloc_junk_small(ret, &arena_bin_info[binind], true); } - JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, size); - memset(ret, 0, size); + memset(ret, 0, usize); } - return (ret); + arena_decay_tick(tsdn, arena); + return ret; } void * -arena_malloc_large(arena_t *arena, size_t size, bool zero) -{ - void *ret; - size_t usize; - uintptr_t random_offset; - arena_run_t *run; - arena_chunk_map_misc_t *miscelm; - UNUSED bool idump; - - /* Large allocation. */ - usize = s2u(size); - malloc_mutex_lock(&arena->lock); - if (config_cache_oblivious) { - uint64_t r; - - /* - * Compute a uniformly distributed offset within the first page - * that is a multiple of the cacheline size, e.g. [0 .. 63) * 64 - * for 4 KiB pages and 64-byte cachelines. - */ - prng64(r, LG_PAGE - LG_CACHELINE, arena->offset_state, - UINT64_C(6364136223846793009), - UINT64_C(1442695040888963409)); - random_offset = ((uintptr_t)r) << LG_CACHELINE; - } else - random_offset = 0; - run = arena_run_alloc_large(arena, usize + large_pad, zero); - if (run == NULL) { - malloc_mutex_unlock(&arena->lock); - return (NULL); - } - miscelm = arena_run_to_miscelm(run); - ret = (void *)((uintptr_t)arena_miscelm_to_rpages(miscelm) + - random_offset); - if (config_stats) { - szind_t index = size2index(usize) - NBINS; +arena_malloc_hard(tsdn_t *tsdn, arena_t *arena, size_t size, szind_t ind, + bool zero) { + assert(!tsdn_null(tsdn) || arena != NULL); - arena->stats.nmalloc_large++; - arena->stats.nrequests_large++; - arena->stats.allocated_large += usize; - arena->stats.lstats[index].nmalloc++; - arena->stats.lstats[index].nrequests++; - arena->stats.lstats[index].curruns++; + if (likely(!tsdn_null(tsdn))) { + arena = arena_choose(tsdn_tsd(tsdn), arena); } - if (config_prof) - idump = arena_prof_accum_locked(arena, usize); - malloc_mutex_unlock(&arena->lock); - if (config_prof && idump) - prof_idump(); - - if (!zero) { - if (config_fill) { - if (unlikely(opt_junk_alloc)) - memset(ret, 0xa5, usize); - else if (unlikely(opt_zero)) - memset(ret, 0, usize); - } - } - - return (ret); -} - -/* Only handles large allocations that require more than page alignment. */ -static void * -arena_palloc_large(tsd_t *tsd, arena_t *arena, size_t usize, size_t alignment, - bool zero) -{ - void *ret; - size_t alloc_size, leadsize, trailsize; - arena_run_t *run; - arena_chunk_t *chunk; - arena_chunk_map_misc_t *miscelm; - void *rpages; - - assert(usize == PAGE_CEILING(usize)); - - arena = arena_choose(tsd, arena); - if (unlikely(arena == NULL)) - return (NULL); - - alignment = PAGE_CEILING(alignment); - alloc_size = usize + large_pad + alignment - PAGE; - - malloc_mutex_lock(&arena->lock); - run = arena_run_alloc_large(arena, alloc_size, false); - if (run == NULL) { - malloc_mutex_unlock(&arena->lock); - return (NULL); - } - chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); - miscelm = arena_run_to_miscelm(run); - rpages = arena_miscelm_to_rpages(miscelm); - - leadsize = ALIGNMENT_CEILING((uintptr_t)rpages, alignment) - - (uintptr_t)rpages; - assert(alloc_size >= leadsize + usize); - trailsize = alloc_size - leadsize - usize - large_pad; - if (leadsize != 0) { - arena_chunk_map_misc_t *head_miscelm = miscelm; - arena_run_t *head_run = run; - - miscelm = arena_miscelm_get(chunk, - arena_miscelm_to_pageind(head_miscelm) + (leadsize >> - LG_PAGE)); - run = &miscelm->run; - - arena_run_trim_head(arena, chunk, head_run, alloc_size, - alloc_size - leadsize); - } - if (trailsize != 0) { - arena_run_trim_tail(arena, chunk, run, usize + large_pad + - trailsize, usize + large_pad, false); - } - if (arena_run_init_large(arena, run, usize + large_pad, zero)) { - size_t run_ind = - arena_miscelm_to_pageind(arena_run_to_miscelm(run)); - bool dirty = (arena_mapbits_dirty_get(chunk, run_ind) != 0); - bool decommitted = (arena_mapbits_decommitted_get(chunk, - run_ind) != 0); - - assert(decommitted); /* Cause of OOM. */ - arena_run_dalloc(arena, run, dirty, false, decommitted); - malloc_mutex_unlock(&arena->lock); - return (NULL); - } - ret = arena_miscelm_to_rpages(miscelm); - - if (config_stats) { - szind_t index = size2index(usize) - NBINS; - - arena->stats.nmalloc_large++; - arena->stats.nrequests_large++; - arena->stats.allocated_large += usize; - arena->stats.lstats[index].nmalloc++; - arena->stats.lstats[index].nrequests++; - arena->stats.lstats[index].curruns++; + if (unlikely(arena == NULL)) { + return NULL; } - malloc_mutex_unlock(&arena->lock); - if (config_fill && !zero) { - if (unlikely(opt_junk_alloc)) - memset(ret, 0xa5, usize); - else if (unlikely(opt_zero)) - memset(ret, 0, usize); + if (likely(size <= SMALL_MAXCLASS)) { + return arena_malloc_small(tsdn, arena, ind, zero); } - return (ret); + return large_malloc(tsdn, arena, sz_index2size(ind), zero); } void * -arena_palloc(tsd_t *tsd, arena_t *arena, size_t usize, size_t alignment, - bool zero, tcache_t *tcache) -{ +arena_palloc(tsdn_t *tsdn, arena_t *arena, size_t usize, size_t alignment, + bool zero, tcache_t *tcache) { void *ret; if (usize <= SMALL_MAXCLASS && (alignment < PAGE || (alignment == PAGE && (usize & PAGE_MASK) == 0))) { - /* Small; alignment doesn't require special run placement. */ - ret = arena_malloc(tsd, arena, usize, zero, tcache); - } else if (usize <= large_maxclass && alignment <= PAGE) { - /* - * Large; alignment doesn't require special run placement. - * However, the cached pointer may be at a random offset from - * the base of the run, so do some bit manipulation to retrieve - * the base. - */ - ret = arena_malloc(tsd, arena, usize, zero, tcache); - if (config_cache_oblivious) - ret = (void *)((uintptr_t)ret & ~PAGE_MASK); + /* Small; alignment doesn't require special slab placement. */ + ret = arena_malloc(tsdn, arena, usize, sz_size2index(usize), + zero, tcache, true); } else { - if (likely(usize <= large_maxclass)) { - ret = arena_palloc_large(tsd, arena, usize, alignment, - zero); - } else if (likely(alignment <= chunksize)) - ret = huge_malloc(tsd, arena, usize, zero, tcache); - else { - ret = huge_palloc(tsd, arena, usize, alignment, zero, - tcache); + if (likely(alignment <= CACHELINE)) { + ret = large_malloc(tsdn, arena, usize, zero); + } else { + ret = large_palloc(tsdn, arena, usize, alignment, zero); } } - return (ret); + return ret; } void -arena_prof_promoted(const void *ptr, size_t size) -{ - arena_chunk_t *chunk; - size_t pageind; - szind_t binind; - +arena_prof_promote(tsdn_t *tsdn, const void *ptr, size_t usize) { cassert(config_prof); assert(ptr != NULL); - assert(CHUNK_ADDR2BASE(ptr) != ptr); - assert(isalloc(ptr, false) == LARGE_MINCLASS); - assert(isalloc(ptr, true) == LARGE_MINCLASS); - assert(size <= SMALL_MAXCLASS); - - chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); - pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; - binind = size2index(size); - assert(binind < NBINS); - arena_mapbits_large_binind_set(chunk, pageind, binind); - - assert(isalloc(ptr, false) == LARGE_MINCLASS); - assert(isalloc(ptr, true) == size); -} - -static void -arena_dissociate_bin_run(arena_chunk_t *chunk, arena_run_t *run, - arena_bin_t *bin) -{ - - /* Dissociate run from bin. */ - if (run == bin->runcur) - bin->runcur = NULL; - else { - szind_t binind = arena_bin_index(extent_node_arena_get( - &chunk->node), bin); - arena_bin_info_t *bin_info = &arena_bin_info[binind]; - - if (bin_info->nregs != 1) { - /* - * This block's conditional is necessary because if the - * run only contains one region, then it never gets - * inserted into the non-full runs tree. - */ - arena_bin_runs_remove(bin, run); - } - } -} - -static void -arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, - arena_bin_t *bin) -{ - - assert(run != bin->runcur); - assert(arena_run_tree_search(&bin->runs, arena_run_to_miscelm(run)) == - NULL); - - malloc_mutex_unlock(&bin->lock); - /******************************/ - malloc_mutex_lock(&arena->lock); - arena_run_dalloc_decommit(arena, chunk, run); - malloc_mutex_unlock(&arena->lock); - /****************************/ - malloc_mutex_lock(&bin->lock); - if (config_stats) - bin->stats.curruns--; -} - -static void -arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, - arena_bin_t *bin) -{ + assert(isalloc(tsdn, ptr) == LARGE_MINCLASS); + assert(usize <= SMALL_MAXCLASS); - /* - * Make sure that if bin->runcur is non-NULL, it refers to the lowest - * non-full run. It is okay to NULL runcur out rather than proactively - * keeping it pointing at the lowest non-full run. - */ - if ((uintptr_t)run < (uintptr_t)bin->runcur) { - /* Switch runcur. */ - if (bin->runcur->nfree > 0) - arena_bin_runs_insert(bin, bin->runcur); - bin->runcur = run; - if (config_stats) - bin->stats.reruns++; - } else - arena_bin_runs_insert(bin, run); -} + rtree_ctx_t rtree_ctx_fallback; + rtree_ctx_t *rtree_ctx = tsdn_rtree_ctx(tsdn, &rtree_ctx_fallback); -static void -arena_dalloc_bin_locked_impl(arena_t *arena, arena_chunk_t *chunk, void *ptr, - arena_chunk_map_bits_t *bitselm, bool junked) -{ - size_t pageind, rpages_ind; - arena_run_t *run; - arena_bin_t *bin; - arena_bin_info_t *bin_info; - szind_t binind; + extent_t *extent = rtree_extent_read(tsdn, &extents_rtree, rtree_ctx, + (uintptr_t)ptr, true); + arena_t *arena = extent_arena_get(extent); - pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; - rpages_ind = pageind - arena_mapbits_small_runind_get(chunk, pageind); - run = &arena_miscelm_get(chunk, rpages_ind)->run; - binind = run->binind; - bin = &arena->bins[binind]; - bin_info = &arena_bin_info[binind]; - - if (!junked && config_fill && unlikely(opt_junk_free)) - arena_dalloc_junk_small(ptr, bin_info); + szind_t szind = sz_size2index(usize); + extent_szind_set(extent, szind); + rtree_szind_slab_update(tsdn, &extents_rtree, rtree_ctx, (uintptr_t)ptr, + szind, false); - arena_run_reg_dalloc(run, ptr); - if (run->nfree == bin_info->nregs) { - arena_dissociate_bin_run(chunk, run, bin); - arena_dalloc_bin_run(arena, chunk, run, bin); - } else if (run->nfree == 1 && run != bin->runcur) - arena_bin_lower_run(arena, chunk, run, bin); + prof_accum_cancel(tsdn, &arena->prof_accum, usize); - if (config_stats) { - bin->stats.ndalloc++; - bin->stats.curregs--; - } + assert(isalloc(tsdn, ptr) == usize); } -void -arena_dalloc_bin_junked_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr, - arena_chunk_map_bits_t *bitselm) -{ +static size_t +arena_prof_demote(tsdn_t *tsdn, extent_t *extent, const void *ptr) { + cassert(config_prof); + assert(ptr != NULL); - arena_dalloc_bin_locked_impl(arena, chunk, ptr, bitselm, true); -} + extent_szind_set(extent, NBINS); + rtree_ctx_t rtree_ctx_fallback; + rtree_ctx_t *rtree_ctx = tsdn_rtree_ctx(tsdn, &rtree_ctx_fallback); + rtree_szind_slab_update(tsdn, &extents_rtree, rtree_ctx, (uintptr_t)ptr, + NBINS, false); -void -arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr, - size_t pageind, arena_chunk_map_bits_t *bitselm) -{ - arena_run_t *run; - arena_bin_t *bin; - size_t rpages_ind; + assert(isalloc(tsdn, ptr) == LARGE_MINCLASS); - rpages_ind = pageind - arena_mapbits_small_runind_get(chunk, pageind); - run = &arena_miscelm_get(chunk, rpages_ind)->run; - bin = &arena->bins[run->binind]; - malloc_mutex_lock(&bin->lock); - arena_dalloc_bin_locked_impl(arena, chunk, ptr, bitselm, false); - malloc_mutex_unlock(&bin->lock); + return LARGE_MINCLASS; } void -arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr, - size_t pageind) -{ - arena_chunk_map_bits_t *bitselm; +arena_dalloc_promoted(tsdn_t *tsdn, void *ptr, tcache_t *tcache, + bool slow_path) { + cassert(config_prof); + assert(opt_prof); - if (config_debug) { - /* arena_ptr_small_binind_get() does extra sanity checking. */ - assert(arena_ptr_small_binind_get(ptr, arena_mapbits_get(chunk, - pageind)) != BININD_INVALID); + extent_t *extent = iealloc(tsdn, ptr); + size_t usize = arena_prof_demote(tsdn, extent, ptr); + if (usize <= tcache_maxclass) { + tcache_dalloc_large(tsdn_tsd(tsdn), tcache, ptr, + sz_size2index(usize), slow_path); + } else { + large_dalloc(tsdn, extent); } - bitselm = arena_bitselm_get(chunk, pageind); - arena_dalloc_bin(arena, chunk, ptr, pageind, bitselm); -} - -#ifdef JEMALLOC_JET -#undef arena_dalloc_junk_large -#define arena_dalloc_junk_large JEMALLOC_N(arena_dalloc_junk_large_impl) -#endif -void -arena_dalloc_junk_large(void *ptr, size_t usize) -{ - - if (config_fill && unlikely(opt_junk_free)) - memset(ptr, 0x5a, usize); } -#ifdef JEMALLOC_JET -#undef arena_dalloc_junk_large -#define arena_dalloc_junk_large JEMALLOC_N(arena_dalloc_junk_large) -arena_dalloc_junk_large_t *arena_dalloc_junk_large = - JEMALLOC_N(arena_dalloc_junk_large_impl); -#endif static void -arena_dalloc_large_locked_impl(arena_t *arena, arena_chunk_t *chunk, - void *ptr, bool junked) -{ - size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; - arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind); - arena_run_t *run = &miscelm->run; - - if (config_fill || config_stats) { - size_t usize = arena_mapbits_large_size_get(chunk, pageind) - - large_pad; - - if (!junked) - arena_dalloc_junk_large(ptr, usize); - if (config_stats) { - szind_t index = size2index(usize) - NBINS; +arena_dissociate_bin_slab(arena_t *arena, extent_t *slab, arena_bin_t *bin) { + /* Dissociate slab from bin. */ + if (slab == bin->slabcur) { + bin->slabcur = NULL; + } else { + szind_t binind = extent_szind_get(slab); + const arena_bin_info_t *bin_info = &arena_bin_info[binind]; - arena->stats.ndalloc_large++; - arena->stats.allocated_large -= usize; - arena->stats.lstats[index].ndalloc++; - arena->stats.lstats[index].curruns--; + /* + * The following block's conditional is necessary because if the + * slab only contains one region, then it never gets inserted + * into the non-full slabs heap. + */ + if (bin_info->nregs == 1) { + arena_bin_slabs_full_remove(arena, bin, slab); + } else { + arena_bin_slabs_nonfull_remove(bin, slab); } } - - arena_run_dalloc_decommit(arena, chunk, run); } -void -arena_dalloc_large_junked_locked(arena_t *arena, arena_chunk_t *chunk, - void *ptr) -{ - - arena_dalloc_large_locked_impl(arena, chunk, ptr, true); -} - -void -arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr) -{ +static void +arena_dalloc_bin_slab(tsdn_t *tsdn, arena_t *arena, extent_t *slab, + arena_bin_t *bin) { + assert(slab != bin->slabcur); - malloc_mutex_lock(&arena->lock); - arena_dalloc_large_locked_impl(arena, chunk, ptr, false); - malloc_mutex_unlock(&arena->lock); + malloc_mutex_unlock(tsdn, &bin->lock); + /******************************/ + arena_slab_dalloc(tsdn, arena, slab); + /****************************/ + malloc_mutex_lock(tsdn, &bin->lock); + if (config_stats) { + bin->stats.curslabs--; + } } static void -arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr, - size_t oldsize, size_t size) -{ - size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; - arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind); - arena_run_t *run = &miscelm->run; - - assert(size < oldsize); +arena_bin_lower_slab(tsdn_t *tsdn, arena_t *arena, extent_t *slab, + arena_bin_t *bin) { + assert(extent_nfree_get(slab) > 0); /* - * Shrink the run, and make trailing pages available for other - * allocations. + * Make sure that if bin->slabcur is non-NULL, it refers to the + * oldest/lowest non-full slab. It is okay to NULL slabcur out rather + * than proactively keeping it pointing at the oldest/lowest non-full + * slab. */ - malloc_mutex_lock(&arena->lock); - arena_run_trim_tail(arena, chunk, run, oldsize + large_pad, size + - large_pad, true); - if (config_stats) { - szind_t oldindex = size2index(oldsize) - NBINS; - szind_t index = size2index(size) - NBINS; - - arena->stats.ndalloc_large++; - arena->stats.allocated_large -= oldsize; - arena->stats.lstats[oldindex].ndalloc++; - arena->stats.lstats[oldindex].curruns--; - - arena->stats.nmalloc_large++; - arena->stats.nrequests_large++; - arena->stats.allocated_large += size; - arena->stats.lstats[index].nmalloc++; - arena->stats.lstats[index].nrequests++; - arena->stats.lstats[index].curruns++; - } - malloc_mutex_unlock(&arena->lock); -} - -static bool -arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr, - size_t oldsize, size_t usize_min, size_t usize_max, bool zero) -{ - size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; - size_t npages = (oldsize + large_pad) >> LG_PAGE; - size_t followsize; - - assert(oldsize == arena_mapbits_large_size_get(chunk, pageind) - - large_pad); - - /* Try to extend the run. */ - malloc_mutex_lock(&arena->lock); - if (pageind+npages >= chunk_npages || arena_mapbits_allocated_get(chunk, - pageind+npages) != 0) - goto label_fail; - followsize = arena_mapbits_unallocated_size_get(chunk, pageind+npages); - if (oldsize + followsize >= usize_min) { - /* - * The next run is available and sufficiently large. Split the - * following run, then merge the first part with the existing - * allocation. - */ - arena_run_t *run; - size_t usize, splitsize, size, flag_dirty, flag_unzeroed_mask; - - usize = usize_max; - while (oldsize + followsize < usize) - usize = index2size(size2index(usize)-1); - assert(usize >= usize_min); - assert(usize >= oldsize); - splitsize = usize - oldsize; - if (splitsize == 0) - goto label_fail; - - run = &arena_miscelm_get(chunk, pageind+npages)->run; - if (arena_run_split_large(arena, run, splitsize, zero)) - goto label_fail; - - if (config_cache_oblivious && zero) { - /* - * Zero the trailing bytes of the original allocation's - * last page, since they are in an indeterminate state. - * There will always be trailing bytes, because ptr's - * offset from the beginning of the run is a multiple of - * CACHELINE in [0 .. PAGE). - */ - void *zbase = (void *)((uintptr_t)ptr + oldsize); - void *zpast = PAGE_ADDR2BASE((void *)((uintptr_t)zbase + - PAGE)); - size_t nzero = (uintptr_t)zpast - (uintptr_t)zbase; - assert(nzero > 0); - memset(zbase, 0, nzero); + if (bin->slabcur != NULL && extent_snad_comp(bin->slabcur, slab) > 0) { + /* Switch slabcur. */ + if (extent_nfree_get(bin->slabcur) > 0) { + arena_bin_slabs_nonfull_insert(bin, bin->slabcur); + } else { + arena_bin_slabs_full_insert(arena, bin, bin->slabcur); } - - size = oldsize + splitsize; - npages = (size + large_pad) >> LG_PAGE; - - /* - * Mark the extended run as dirty if either portion of the run - * was dirty before allocation. This is rather pedantic, - * because there's not actually any sequence of events that - * could cause the resulting run to be passed to - * arena_run_dalloc() with the dirty argument set to false - * (which is when dirty flag consistency would really matter). - */ - flag_dirty = arena_mapbits_dirty_get(chunk, pageind) | - arena_mapbits_dirty_get(chunk, pageind+npages-1); - flag_unzeroed_mask = flag_dirty == 0 ? CHUNK_MAP_UNZEROED : 0; - arena_mapbits_large_set(chunk, pageind, size + large_pad, - flag_dirty | (flag_unzeroed_mask & - arena_mapbits_unzeroed_get(chunk, pageind))); - arena_mapbits_large_set(chunk, pageind+npages-1, 0, flag_dirty | - (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, - pageind+npages-1))); - + bin->slabcur = slab; if (config_stats) { - szind_t oldindex = size2index(oldsize) - NBINS; - szind_t index = size2index(size) - NBINS; - - arena->stats.ndalloc_large++; - arena->stats.allocated_large -= oldsize; - arena->stats.lstats[oldindex].ndalloc++; - arena->stats.lstats[oldindex].curruns--; - - arena->stats.nmalloc_large++; - arena->stats.nrequests_large++; - arena->stats.allocated_large += size; - arena->stats.lstats[index].nmalloc++; - arena->stats.lstats[index].nrequests++; - arena->stats.lstats[index].curruns++; + bin->stats.reslabs++; } - malloc_mutex_unlock(&arena->lock); - return (false); + } else { + arena_bin_slabs_nonfull_insert(bin, slab); } -label_fail: - malloc_mutex_unlock(&arena->lock); - return (true); } -#ifdef JEMALLOC_JET -#undef arena_ralloc_junk_large -#define arena_ralloc_junk_large JEMALLOC_N(arena_ralloc_junk_large_impl) -#endif static void -arena_ralloc_junk_large(void *ptr, size_t old_usize, size_t usize) -{ +arena_dalloc_bin_locked_impl(tsdn_t *tsdn, arena_t *arena, extent_t *slab, + void *ptr, bool junked) { + arena_slab_data_t *slab_data = extent_slab_data_get(slab); + szind_t binind = extent_szind_get(slab); + arena_bin_t *bin = &arena->bins[binind]; + const arena_bin_info_t *bin_info = &arena_bin_info[binind]; + + if (!junked && config_fill && unlikely(opt_junk_free)) { + arena_dalloc_junk_small(ptr, bin_info); + } + + arena_slab_reg_dalloc(tsdn, slab, slab_data, ptr); + unsigned nfree = extent_nfree_get(slab); + if (nfree == bin_info->nregs) { + arena_dissociate_bin_slab(arena, slab, bin); + arena_dalloc_bin_slab(tsdn, arena, slab, bin); + } else if (nfree == 1 && slab != bin->slabcur) { + arena_bin_slabs_full_remove(arena, bin, slab); + arena_bin_lower_slab(tsdn, arena, slab, bin); + } - if (config_fill && unlikely(opt_junk_free)) { - memset((void *)((uintptr_t)ptr + usize), 0x5a, - old_usize - usize); + if (config_stats) { + bin->stats.ndalloc++; + bin->stats.curregs--; } } -#ifdef JEMALLOC_JET -#undef arena_ralloc_junk_large -#define arena_ralloc_junk_large JEMALLOC_N(arena_ralloc_junk_large) -arena_ralloc_junk_large_t *arena_ralloc_junk_large = - JEMALLOC_N(arena_ralloc_junk_large_impl); -#endif -/* - * Try to resize a large allocation, in order to avoid copying. This will - * always fail if growing an object, and the following run is already in use. - */ -static bool -arena_ralloc_large(void *ptr, size_t oldsize, size_t usize_min, - size_t usize_max, bool zero) -{ - arena_chunk_t *chunk; - arena_t *arena; +void +arena_dalloc_bin_junked_locked(tsdn_t *tsdn, arena_t *arena, extent_t *extent, + void *ptr) { + arena_dalloc_bin_locked_impl(tsdn, arena, extent, ptr, true); +} - if (oldsize == usize_max) { - /* Current size class is compatible and maximal. */ - return (false); - } +static void +arena_dalloc_bin(tsdn_t *tsdn, arena_t *arena, extent_t *extent, void *ptr) { + szind_t binind = extent_szind_get(extent); + arena_bin_t *bin = &arena->bins[binind]; - chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); - arena = extent_node_arena_get(&chunk->node); + malloc_mutex_lock(tsdn, &bin->lock); + arena_dalloc_bin_locked_impl(tsdn, arena, extent, ptr, false); + malloc_mutex_unlock(tsdn, &bin->lock); +} - if (oldsize < usize_max) { - bool ret = arena_ralloc_large_grow(arena, chunk, ptr, oldsize, - usize_min, usize_max, zero); - if (config_fill && !ret && !zero) { - if (unlikely(opt_junk_alloc)) { - memset((void *)((uintptr_t)ptr + oldsize), 0xa5, - isalloc(ptr, config_prof) - oldsize); - } else if (unlikely(opt_zero)) { - memset((void *)((uintptr_t)ptr + oldsize), 0, - isalloc(ptr, config_prof) - oldsize); - } - } - return (ret); - } +void +arena_dalloc_small(tsdn_t *tsdn, void *ptr) { + extent_t *extent = iealloc(tsdn, ptr); + arena_t *arena = extent_arena_get(extent); - assert(oldsize > usize_max); - /* Fill before shrinking in order avoid a race. */ - arena_ralloc_junk_large(ptr, oldsize, usize_max); - arena_ralloc_large_shrink(arena, chunk, ptr, oldsize, usize_max); - return (false); + arena_dalloc_bin(tsdn, arena, extent, ptr); + arena_decay_tick(tsdn, arena); } bool -arena_ralloc_no_move(void *ptr, size_t oldsize, size_t size, size_t extra, - bool zero) -{ - size_t usize_min, usize_max; - - usize_min = s2u(size); - usize_max = s2u(size + extra); - if (likely(oldsize <= large_maxclass && usize_min <= large_maxclass)) { +arena_ralloc_no_move(tsdn_t *tsdn, void *ptr, size_t oldsize, size_t size, + size_t extra, bool zero) { + /* Calls with non-zero extra had to clamp extra. */ + assert(extra == 0 || size + extra <= LARGE_MAXCLASS); + + if (unlikely(size > LARGE_MAXCLASS)) { + return true; + } + + extent_t *extent = iealloc(tsdn, ptr); + size_t usize_min = sz_s2u(size); + size_t usize_max = sz_s2u(size + extra); + if (likely(oldsize <= SMALL_MAXCLASS && usize_min <= SMALL_MAXCLASS)) { /* * Avoid moving the allocation if the size class can be left the * same. */ - if (oldsize <= SMALL_MAXCLASS) { - assert(arena_bin_info[size2index(oldsize)].reg_size == - oldsize); - if ((usize_max <= SMALL_MAXCLASS && - size2index(usize_max) == size2index(oldsize)) || - (size <= oldsize && usize_max >= oldsize)) - return (false); - } else { - if (usize_max > SMALL_MAXCLASS) { - if (!arena_ralloc_large(ptr, oldsize, usize_min, - usize_max, zero)) - return (false); - } + assert(arena_bin_info[sz_size2index(oldsize)].reg_size == + oldsize); + if ((usize_max > SMALL_MAXCLASS || sz_size2index(usize_max) != + sz_size2index(oldsize)) && (size > oldsize || usize_max < + oldsize)) { + return true; } - /* Reallocation would require a move. */ - return (true); - } else { - return (huge_ralloc_no_move(ptr, oldsize, usize_min, usize_max, - zero)); + arena_decay_tick(tsdn, extent_arena_get(extent)); + return false; + } else if (oldsize >= LARGE_MINCLASS && usize_max >= LARGE_MINCLASS) { + return large_ralloc_no_move(tsdn, extent, usize_min, usize_max, + zero); } + + return true; } static void * -arena_ralloc_move_helper(tsd_t *tsd, arena_t *arena, size_t usize, - size_t alignment, bool zero, tcache_t *tcache) -{ - - if (alignment == 0) - return (arena_malloc(tsd, arena, usize, zero, tcache)); - usize = sa2u(usize, alignment); - if (usize == 0) - return (NULL); - return (ipalloct(tsd, usize, alignment, zero, tcache, arena)); +arena_ralloc_move_helper(tsdn_t *tsdn, arena_t *arena, size_t usize, + size_t alignment, bool zero, tcache_t *tcache) { + if (alignment == 0) { + return arena_malloc(tsdn, arena, usize, sz_size2index(usize), + zero, tcache, true); + } + usize = sz_sa2u(usize, alignment); + if (unlikely(usize == 0 || usize > LARGE_MAXCLASS)) { + return NULL; + } + return ipalloct(tsdn, usize, alignment, zero, tcache, arena); } void * -arena_ralloc(tsd_t *tsd, arena_t *arena, void *ptr, size_t oldsize, size_t size, - size_t alignment, bool zero, tcache_t *tcache) -{ - void *ret; - size_t usize; - - usize = s2u(size); - if (usize == 0) - return (NULL); - - if (likely(usize <= large_maxclass)) { - size_t copysize; +arena_ralloc(tsdn_t *tsdn, arena_t *arena, void *ptr, size_t oldsize, + size_t size, size_t alignment, bool zero, tcache_t *tcache) { + size_t usize = sz_s2u(size); + if (unlikely(usize == 0 || size > LARGE_MAXCLASS)) { + return NULL; + } + if (likely(usize <= SMALL_MAXCLASS)) { /* Try to avoid moving the allocation. */ - if (!arena_ralloc_no_move(ptr, oldsize, usize, 0, zero)) - return (ptr); - - /* - * size and oldsize are different enough that we need to move - * the object. In that case, fall back to allocating new space - * and copying. - */ - ret = arena_ralloc_move_helper(tsd, arena, usize, alignment, - zero, tcache); - if (ret == NULL) - return (NULL); + if (!arena_ralloc_no_move(tsdn, ptr, oldsize, usize, 0, zero)) { + return ptr; + } + } - /* - * Junk/zero-filling were already done by - * ipalloc()/arena_malloc(). - */ + if (oldsize >= LARGE_MINCLASS && usize >= LARGE_MINCLASS) { + return large_ralloc(tsdn, arena, iealloc(tsdn, ptr), usize, + alignment, zero, tcache); + } - copysize = (usize < oldsize) ? usize : oldsize; - JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, copysize); - memcpy(ret, ptr, copysize); - isqalloc(tsd, ptr, oldsize, tcache); - } else { - ret = huge_ralloc(tsd, arena, ptr, oldsize, usize, alignment, - zero, tcache); + /* + * size and oldsize are different enough that we need to move the + * object. In that case, fall back to allocating new space and copying. + */ + void *ret = arena_ralloc_move_helper(tsdn, arena, usize, alignment, + zero, tcache); + if (ret == NULL) { + return NULL; } - return (ret); + + /* + * Junk/zero-filling were already done by + * ipalloc()/arena_malloc(). + */ + + size_t copysize = (usize < oldsize) ? usize : oldsize; + memcpy(ret, ptr, copysize); + isdalloct(tsdn, ptr, oldsize, tcache, NULL, true); + return ret; } dss_prec_t -arena_dss_prec_get(arena_t *arena) -{ - dss_prec_t ret; - - malloc_mutex_lock(&arena->lock); - ret = arena->dss_prec; - malloc_mutex_unlock(&arena->lock); - return (ret); +arena_dss_prec_get(arena_t *arena) { + return (dss_prec_t)atomic_load_u(&arena->dss_prec, ATOMIC_ACQUIRE); } bool -arena_dss_prec_set(arena_t *arena, dss_prec_t dss_prec) -{ - - if (!have_dss) +arena_dss_prec_set(arena_t *arena, dss_prec_t dss_prec) { + if (!have_dss) { return (dss_prec != dss_prec_disabled); - malloc_mutex_lock(&arena->lock); - arena->dss_prec = dss_prec; - malloc_mutex_unlock(&arena->lock); - return (false); + } + atomic_store_u(&arena->dss_prec, (unsigned)dss_prec, ATOMIC_RELEASE); + return false; } ssize_t -arena_lg_dirty_mult_default_get(void) -{ +arena_dirty_decay_ms_default_get(void) { + return atomic_load_zd(&dirty_decay_ms_default, ATOMIC_RELAXED); +} + +bool +arena_dirty_decay_ms_default_set(ssize_t decay_ms) { + if (!arena_decay_ms_valid(decay_ms)) { + return true; + } + atomic_store_zd(&dirty_decay_ms_default, decay_ms, ATOMIC_RELAXED); + return false; +} - return ((ssize_t)atomic_read_z((size_t *)&lg_dirty_mult_default)); +ssize_t +arena_muzzy_decay_ms_default_get(void) { + return atomic_load_zd(&muzzy_decay_ms_default, ATOMIC_RELAXED); } bool -arena_lg_dirty_mult_default_set(ssize_t lg_dirty_mult) -{ +arena_muzzy_decay_ms_default_set(ssize_t decay_ms) { + if (!arena_decay_ms_valid(decay_ms)) { + return true; + } + atomic_store_zd(&muzzy_decay_ms_default, decay_ms, ATOMIC_RELAXED); + return false; +} - if (!arena_lg_dirty_mult_valid(lg_dirty_mult)) - return (true); - atomic_write_z((size_t *)&lg_dirty_mult_default, (size_t)lg_dirty_mult); - return (false); +unsigned +arena_nthreads_get(arena_t *arena, bool internal) { + return atomic_load_u(&arena->nthreads[internal], ATOMIC_RELAXED); } void -arena_stats_merge(arena_t *arena, const char **dss, ssize_t *lg_dirty_mult, - size_t *nactive, size_t *ndirty, arena_stats_t *astats, - malloc_bin_stats_t *bstats, malloc_large_stats_t *lstats, - malloc_huge_stats_t *hstats) -{ - unsigned i; - - malloc_mutex_lock(&arena->lock); - *dss = dss_prec_names[arena->dss_prec]; - *lg_dirty_mult = arena->lg_dirty_mult; - *nactive += arena->nactive; - *ndirty += arena->ndirty; - - astats->mapped += arena->stats.mapped; - astats->npurge += arena->stats.npurge; - astats->nmadvise += arena->stats.nmadvise; - astats->purged += arena->stats.purged; - astats->metadata_mapped += arena->stats.metadata_mapped; - astats->metadata_allocated += arena_metadata_allocated_get(arena); - astats->allocated_large += arena->stats.allocated_large; - astats->nmalloc_large += arena->stats.nmalloc_large; - astats->ndalloc_large += arena->stats.ndalloc_large; - astats->nrequests_large += arena->stats.nrequests_large; - astats->allocated_huge += arena->stats.allocated_huge; - astats->nmalloc_huge += arena->stats.nmalloc_huge; - astats->ndalloc_huge += arena->stats.ndalloc_huge; - - for (i = 0; i < nlclasses; i++) { - lstats[i].nmalloc += arena->stats.lstats[i].nmalloc; - lstats[i].ndalloc += arena->stats.lstats[i].ndalloc; - lstats[i].nrequests += arena->stats.lstats[i].nrequests; - lstats[i].curruns += arena->stats.lstats[i].curruns; - } - - for (i = 0; i < nhclasses; i++) { - hstats[i].nmalloc += arena->stats.hstats[i].nmalloc; - hstats[i].ndalloc += arena->stats.hstats[i].ndalloc; - hstats[i].curhchunks += arena->stats.hstats[i].curhchunks; - } - malloc_mutex_unlock(&arena->lock); +arena_nthreads_inc(arena_t *arena, bool internal) { + atomic_fetch_add_u(&arena->nthreads[internal], 1, ATOMIC_RELAXED); +} - for (i = 0; i < NBINS; i++) { - arena_bin_t *bin = &arena->bins[i]; +void +arena_nthreads_dec(arena_t *arena, bool internal) { + atomic_fetch_sub_u(&arena->nthreads[internal], 1, ATOMIC_RELAXED); +} - malloc_mutex_lock(&bin->lock); - bstats[i].nmalloc += bin->stats.nmalloc; - bstats[i].ndalloc += bin->stats.ndalloc; - bstats[i].nrequests += bin->stats.nrequests; - bstats[i].curregs += bin->stats.curregs; - if (config_tcache) { - bstats[i].nfills += bin->stats.nfills; - bstats[i].nflushes += bin->stats.nflushes; - } - bstats[i].nruns += bin->stats.nruns; - bstats[i].reruns += bin->stats.reruns; - bstats[i].curruns += bin->stats.curruns; - malloc_mutex_unlock(&bin->lock); - } +size_t +arena_extent_sn_next(arena_t *arena) { + return atomic_fetch_add_zu(&arena->extent_sn_next, 1, ATOMIC_RELAXED); } arena_t * -arena_new(unsigned ind) -{ +arena_new(tsdn_t *tsdn, unsigned ind, extent_hooks_t *extent_hooks) { arena_t *arena; + base_t *base; unsigned i; - arena_bin_t *bin; - /* - * Allocate arena, arena->lstats, and arena->hstats contiguously, mainly - * because there is no way to clean up if base_alloc() OOMs. - */ - if (config_stats) { - arena = (arena_t *)base_alloc(CACHELINE_CEILING(sizeof(arena_t)) - + QUANTUM_CEILING(nlclasses * sizeof(malloc_large_stats_t) + - nhclasses) * sizeof(malloc_huge_stats_t)); - } else - arena = (arena_t *)base_alloc(sizeof(arena_t)); - if (arena == NULL) - return (NULL); - - arena->ind = ind; - arena->nthreads = 0; - if (malloc_mutex_init(&arena->lock)) - return (NULL); + if (ind == 0) { + base = b0get(); + } else { + base = base_new(tsdn, ind, extent_hooks); + if (base == NULL) { + return NULL; + } + } + + arena = (arena_t *)base_alloc(tsdn, base, sizeof(arena_t), CACHELINE); + if (arena == NULL) { + goto label_error; + } + + atomic_store_u(&arena->nthreads[0], 0, ATOMIC_RELAXED); + atomic_store_u(&arena->nthreads[1], 0, ATOMIC_RELAXED); + arena->last_thd = NULL; if (config_stats) { - memset(&arena->stats, 0, sizeof(arena_stats_t)); - arena->stats.lstats = (malloc_large_stats_t *)((uintptr_t)arena - + CACHELINE_CEILING(sizeof(arena_t))); - memset(arena->stats.lstats, 0, nlclasses * - sizeof(malloc_large_stats_t)); - arena->stats.hstats = (malloc_huge_stats_t *)((uintptr_t)arena - + CACHELINE_CEILING(sizeof(arena_t)) + - QUANTUM_CEILING(nlclasses * sizeof(malloc_large_stats_t))); - memset(arena->stats.hstats, 0, nhclasses * - sizeof(malloc_huge_stats_t)); - if (config_tcache) - ql_new(&arena->tcache_ql); - } - - if (config_prof) - arena->prof_accumbytes = 0; + if (arena_stats_init(tsdn, &arena->stats)) { + goto label_error; + } + + ql_new(&arena->tcache_ql); + if (malloc_mutex_init(&arena->tcache_ql_mtx, "tcache_ql", + WITNESS_RANK_TCACHE_QL, malloc_mutex_rank_exclusive)) { + goto label_error; + } + } + + if (config_prof) { + if (prof_accum_init(tsdn, &arena->prof_accum)) { + goto label_error; + } + } if (config_cache_oblivious) { /* @@ -3046,279 +1955,225 @@ arena_new(unsigned ind) * cost of test repeatability. For debug builds, instead use a * deterministic seed. */ - arena->offset_state = config_debug ? ind : - (uint64_t)(uintptr_t)arena; + atomic_store_zu(&arena->offset_state, config_debug ? ind : + (size_t)(uintptr_t)arena, ATOMIC_RELAXED); } - arena->dss_prec = chunk_dss_prec_get(); - - arena->spare = NULL; - - arena->lg_dirty_mult = arena_lg_dirty_mult_default_get(); - arena->purging = false; - arena->nactive = 0; - arena->ndirty = 0; + atomic_store_zu(&arena->extent_sn_next, 0, ATOMIC_RELAXED); - arena_avail_tree_new(&arena->runs_avail); - qr_new(&arena->runs_dirty, rd_link); - qr_new(&arena->chunks_cache, cc_link); + atomic_store_u(&arena->dss_prec, (unsigned)extent_dss_prec_get(), + ATOMIC_RELAXED); - ql_new(&arena->huge); - if (malloc_mutex_init(&arena->huge_mtx)) - return (NULL); + atomic_store_zu(&arena->nactive, 0, ATOMIC_RELAXED); - extent_tree_szad_new(&arena->chunks_szad_cached); - extent_tree_ad_new(&arena->chunks_ad_cached); - extent_tree_szad_new(&arena->chunks_szad_retained); - extent_tree_ad_new(&arena->chunks_ad_retained); - if (malloc_mutex_init(&arena->chunks_mtx)) - return (NULL); - ql_new(&arena->node_cache); - if (malloc_mutex_init(&arena->node_cache_mtx)) - return (NULL); - - arena->chunk_hooks = chunk_hooks_default; - - /* Initialize bins. */ - for (i = 0; i < NBINS; i++) { - bin = &arena->bins[i]; - if (malloc_mutex_init(&bin->lock)) - return (NULL); - bin->runcur = NULL; - arena_run_tree_new(&bin->runs); - if (config_stats) - memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); + extent_list_init(&arena->large); + if (malloc_mutex_init(&arena->large_mtx, "arena_large", + WITNESS_RANK_ARENA_LARGE, malloc_mutex_rank_exclusive)) { + goto label_error; } - return (arena); -} - -/* - * Calculate bin_info->run_size such that it meets the following constraints: - * - * *) bin_info->run_size <= arena_maxrun - * *) bin_info->nregs <= RUN_MAXREGS - * - * bin_info->nregs and bin_info->reg0_offset are also calculated here, since - * these settings are all interdependent. - */ -static void -bin_info_run_size_calc(arena_bin_info_t *bin_info) -{ - size_t pad_size; - size_t try_run_size, perfect_run_size, actual_run_size; - uint32_t try_nregs, perfect_nregs, actual_nregs; - /* - * Determine redzone size based on minimum alignment and minimum - * redzone size. Add padding to the end of the run if it is needed to - * align the regions. The padding allows each redzone to be half the - * minimum alignment; without the padding, each redzone would have to - * be twice as large in order to maintain alignment. + * Delay coalescing for dirty extents despite the disruptive effect on + * memory layout for best-fit extent allocation, since cached extents + * are likely to be reused soon after deallocation, and the cost of + * merging/splitting extents is non-trivial. */ - if (config_fill && unlikely(opt_redzone)) { - size_t align_min = ZU(1) << (jemalloc_ffs(bin_info->reg_size) - - 1); - if (align_min <= REDZONE_MINSIZE) { - bin_info->redzone_size = REDZONE_MINSIZE; - pad_size = 0; - } else { - bin_info->redzone_size = align_min >> 1; - pad_size = bin_info->redzone_size; - } - } else { - bin_info->redzone_size = 0; - pad_size = 0; + if (extents_init(tsdn, &arena->extents_dirty, extent_state_dirty, + true)) { + goto label_error; } - bin_info->reg_interval = bin_info->reg_size + - (bin_info->redzone_size << 1); - /* - * Compute run size under ideal conditions (no redzones, no limit on run - * size). + * Coalesce muzzy extents immediately, because operations on them are in + * the critical path much less often than for dirty extents. */ - try_run_size = PAGE; - try_nregs = try_run_size / bin_info->reg_size; - do { - perfect_run_size = try_run_size; - perfect_nregs = try_nregs; - - try_run_size += PAGE; - try_nregs = try_run_size / bin_info->reg_size; - } while (perfect_run_size != perfect_nregs * bin_info->reg_size); - assert(perfect_nregs <= RUN_MAXREGS); - - actual_run_size = perfect_run_size; - actual_nregs = (actual_run_size - pad_size) / bin_info->reg_interval; - + if (extents_init(tsdn, &arena->extents_muzzy, extent_state_muzzy, + false)) { + goto label_error; + } /* - * Redzones can require enough padding that not even a single region can - * fit within the number of pages that would normally be dedicated to a - * run for this size class. Increase the run size until at least one - * region fits. + * Coalesce retained extents immediately, in part because they will + * never be evicted (and therefore there's no opportunity for delayed + * coalescing), but also because operations on retained extents are not + * in the critical path. */ - while (actual_nregs == 0) { - assert(config_fill && unlikely(opt_redzone)); + if (extents_init(tsdn, &arena->extents_retained, extent_state_retained, + false)) { + goto label_error; + } - actual_run_size += PAGE; - actual_nregs = (actual_run_size - pad_size) / - bin_info->reg_interval; + if (arena_decay_init(&arena->decay_dirty, &arena->extents_dirty, + arena_dirty_decay_ms_default_get(), &arena->stats.decay_dirty)) { + goto label_error; + } + if (arena_decay_init(&arena->decay_muzzy, &arena->extents_muzzy, + arena_muzzy_decay_ms_default_get(), &arena->stats.decay_muzzy)) { + goto label_error; } - /* - * Make sure that the run will fit within an arena chunk. - */ - while (actual_run_size > arena_maxrun) { - actual_run_size -= PAGE; - actual_nregs = (actual_run_size - pad_size) / - bin_info->reg_interval; + arena->extent_grow_next = sz_psz2ind(HUGEPAGE); + if (malloc_mutex_init(&arena->extent_grow_mtx, "extent_grow", + WITNESS_RANK_EXTENT_GROW, malloc_mutex_rank_exclusive)) { + goto label_error; } - assert(actual_nregs > 0); - assert(actual_run_size == s2u(actual_run_size)); - /* Copy final settings. */ - bin_info->run_size = actual_run_size; - bin_info->nregs = actual_nregs; - bin_info->reg0_offset = actual_run_size - (actual_nregs * - bin_info->reg_interval) - pad_size + bin_info->redzone_size; + extent_avail_new(&arena->extent_avail); + if (malloc_mutex_init(&arena->extent_avail_mtx, "extent_avail", + WITNESS_RANK_EXTENT_AVAIL, malloc_mutex_rank_exclusive)) { + goto label_error; + } - if (actual_run_size > small_maxrun) - small_maxrun = actual_run_size; + /* Initialize bins. */ + for (i = 0; i < NBINS; i++) { + arena_bin_t *bin = &arena->bins[i]; + if (malloc_mutex_init(&bin->lock, "arena_bin", + WITNESS_RANK_ARENA_BIN, malloc_mutex_rank_exclusive)) { + goto label_error; + } + bin->slabcur = NULL; + extent_heap_new(&bin->slabs_nonfull); + extent_list_init(&bin->slabs_full); + if (config_stats) { + memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); + } + } - assert(bin_info->reg0_offset - bin_info->redzone_size + (bin_info->nregs - * bin_info->reg_interval) + pad_size == bin_info->run_size); -} + arena->base = base; + /* Set arena before creating background threads. */ + arena_set(ind, arena); -static void -bin_info_init(void) -{ - arena_bin_info_t *bin_info; - -#define BIN_INFO_INIT_bin_yes(index, size) \ - bin_info = &arena_bin_info[index]; \ - bin_info->reg_size = size; \ - bin_info_run_size_calc(bin_info); \ - bitmap_info_init(&bin_info->bitmap_info, bin_info->nregs); -#define BIN_INFO_INIT_bin_no(index, size) -#define SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup) \ - BIN_INFO_INIT_bin_##bin(index, (ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta)) - SIZE_CLASSES -#undef BIN_INFO_INIT_bin_yes -#undef BIN_INFO_INIT_bin_no -#undef SC -} + nstime_init(&arena->create_time, 0); + nstime_update(&arena->create_time); -static bool -small_run_size_init(void) -{ + /* We don't support reentrancy for arena 0 bootstrapping. */ + if (ind != 0) { + /* + * If we're here, then arena 0 already exists, so bootstrapping + * is done enough that we should have tsd. + */ + assert(!tsdn_null(tsdn)); + pre_reentrancy(tsdn_tsd(tsdn), arena); + if (hooks_arena_new_hook) { + hooks_arena_new_hook(); + } + post_reentrancy(tsdn_tsd(tsdn)); + } - assert(small_maxrun != 0); + return arena; +label_error: + if (ind != 0) { + base_delete(tsdn, base); + } + return NULL; +} - small_run_tab = (bool *)base_alloc(sizeof(bool) * (small_maxrun >> - LG_PAGE)); - if (small_run_tab == NULL) - return (true); +void +arena_boot(void) { + arena_dirty_decay_ms_default_set(opt_dirty_decay_ms); + arena_muzzy_decay_ms_default_set(opt_muzzy_decay_ms); +} -#define TAB_INIT_bin_yes(index, size) { \ - arena_bin_info_t *bin_info = &arena_bin_info[index]; \ - small_run_tab[bin_info->run_size >> LG_PAGE] = true; \ - } -#define TAB_INIT_bin_no(index, size) -#define SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup) \ - TAB_INIT_bin_##bin(index, (ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta)) - SIZE_CLASSES -#undef TAB_INIT_bin_yes -#undef TAB_INIT_bin_no -#undef SC +void +arena_prefork0(tsdn_t *tsdn, arena_t *arena) { + malloc_mutex_prefork(tsdn, &arena->decay_dirty.mtx); + malloc_mutex_prefork(tsdn, &arena->decay_muzzy.mtx); +} - return (false); +void +arena_prefork1(tsdn_t *tsdn, arena_t *arena) { + if (config_stats) { + malloc_mutex_prefork(tsdn, &arena->tcache_ql_mtx); + } } -bool -arena_boot(void) -{ - unsigned i; +void +arena_prefork2(tsdn_t *tsdn, arena_t *arena) { + malloc_mutex_prefork(tsdn, &arena->extent_grow_mtx); +} - arena_lg_dirty_mult_default_set(opt_lg_dirty_mult); +void +arena_prefork3(tsdn_t *tsdn, arena_t *arena) { + extents_prefork(tsdn, &arena->extents_dirty); + extents_prefork(tsdn, &arena->extents_muzzy); + extents_prefork(tsdn, &arena->extents_retained); +} - /* - * Compute the header size such that it is large enough to contain the - * page map. The page map is biased to omit entries for the header - * itself, so some iteration is necessary to compute the map bias. - * - * 1) Compute safe header_size and map_bias values that include enough - * space for an unbiased page map. - * 2) Refine map_bias based on (1) to omit the header pages in the page - * map. The resulting map_bias may be one too small. - * 3) Refine map_bias based on (2). The result will be >= the result - * from (2), and will always be correct. - */ - map_bias = 0; - for (i = 0; i < 3; i++) { - size_t header_size = offsetof(arena_chunk_t, map_bits) + - ((sizeof(arena_chunk_map_bits_t) + - sizeof(arena_chunk_map_misc_t)) * (chunk_npages-map_bias)); - map_bias = (header_size + PAGE_MASK) >> LG_PAGE; - } - assert(map_bias > 0); - - map_misc_offset = offsetof(arena_chunk_t, map_bits) + - sizeof(arena_chunk_map_bits_t) * (chunk_npages-map_bias); - - arena_maxrun = chunksize - (map_bias << LG_PAGE); - assert(arena_maxrun > 0); - large_maxclass = index2size(size2index(chunksize)-1); - if (large_maxclass > arena_maxrun) { - /* - * For small chunk sizes it's possible for there to be fewer - * non-header pages available than are necessary to serve the - * size classes just below chunksize. - */ - large_maxclass = arena_maxrun; - } - assert(large_maxclass > 0); - nlclasses = size2index(large_maxclass) - size2index(SMALL_MAXCLASS); - nhclasses = NSIZES - nlclasses - NBINS; +void +arena_prefork4(tsdn_t *tsdn, arena_t *arena) { + malloc_mutex_prefork(tsdn, &arena->extent_avail_mtx); +} - bin_info_init(); - return (small_run_size_init()); +void +arena_prefork5(tsdn_t *tsdn, arena_t *arena) { + base_prefork(tsdn, arena->base); } void -arena_prefork(arena_t *arena) -{ - unsigned i; +arena_prefork6(tsdn_t *tsdn, arena_t *arena) { + malloc_mutex_prefork(tsdn, &arena->large_mtx); +} - malloc_mutex_prefork(&arena->lock); - malloc_mutex_prefork(&arena->huge_mtx); - malloc_mutex_prefork(&arena->chunks_mtx); - malloc_mutex_prefork(&arena->node_cache_mtx); - for (i = 0; i < NBINS; i++) - malloc_mutex_prefork(&arena->bins[i].lock); +void +arena_prefork7(tsdn_t *tsdn, arena_t *arena) { + for (unsigned i = 0; i < NBINS; i++) { + malloc_mutex_prefork(tsdn, &arena->bins[i].lock); + } } void -arena_postfork_parent(arena_t *arena) -{ +arena_postfork_parent(tsdn_t *tsdn, arena_t *arena) { unsigned i; - for (i = 0; i < NBINS; i++) - malloc_mutex_postfork_parent(&arena->bins[i].lock); - malloc_mutex_postfork_parent(&arena->node_cache_mtx); - malloc_mutex_postfork_parent(&arena->chunks_mtx); - malloc_mutex_postfork_parent(&arena->huge_mtx); - malloc_mutex_postfork_parent(&arena->lock); + for (i = 0; i < NBINS; i++) { + malloc_mutex_postfork_parent(tsdn, &arena->bins[i].lock); + } + malloc_mutex_postfork_parent(tsdn, &arena->large_mtx); + base_postfork_parent(tsdn, arena->base); + malloc_mutex_postfork_parent(tsdn, &arena->extent_avail_mtx); + extents_postfork_parent(tsdn, &arena->extents_dirty); + extents_postfork_parent(tsdn, &arena->extents_muzzy); + extents_postfork_parent(tsdn, &arena->extents_retained); + malloc_mutex_postfork_parent(tsdn, &arena->extent_grow_mtx); + malloc_mutex_postfork_parent(tsdn, &arena->decay_dirty.mtx); + malloc_mutex_postfork_parent(tsdn, &arena->decay_muzzy.mtx); + if (config_stats) { + malloc_mutex_postfork_parent(tsdn, &arena->tcache_ql_mtx); + } } void -arena_postfork_child(arena_t *arena) -{ +arena_postfork_child(tsdn_t *tsdn, arena_t *arena) { unsigned i; - for (i = 0; i < NBINS; i++) - malloc_mutex_postfork_child(&arena->bins[i].lock); - malloc_mutex_postfork_child(&arena->node_cache_mtx); - malloc_mutex_postfork_child(&arena->chunks_mtx); - malloc_mutex_postfork_child(&arena->huge_mtx); - malloc_mutex_postfork_child(&arena->lock); + atomic_store_u(&arena->nthreads[0], 0, ATOMIC_RELAXED); + atomic_store_u(&arena->nthreads[1], 0, ATOMIC_RELAXED); + if (tsd_arena_get(tsdn_tsd(tsdn)) == arena) { + arena_nthreads_inc(arena, false); + } + if (tsd_iarena_get(tsdn_tsd(tsdn)) == arena) { + arena_nthreads_inc(arena, true); + } + if (config_stats) { + ql_new(&arena->tcache_ql); + tcache_t *tcache = tcache_get(tsdn_tsd(tsdn)); + if (tcache != NULL && tcache->arena == arena) { + ql_elm_new(tcache, link); + ql_tail_insert(&arena->tcache_ql, tcache, link); + } + } + + for (i = 0; i < NBINS; i++) { + malloc_mutex_postfork_child(tsdn, &arena->bins[i].lock); + } + malloc_mutex_postfork_child(tsdn, &arena->large_mtx); + base_postfork_child(tsdn, arena->base); + malloc_mutex_postfork_child(tsdn, &arena->extent_avail_mtx); + extents_postfork_child(tsdn, &arena->extents_dirty); + extents_postfork_child(tsdn, &arena->extents_muzzy); + extents_postfork_child(tsdn, &arena->extents_retained); + malloc_mutex_postfork_child(tsdn, &arena->extent_grow_mtx); + malloc_mutex_postfork_child(tsdn, &arena->decay_dirty.mtx); + malloc_mutex_postfork_child(tsdn, &arena->decay_muzzy.mtx); + if (config_stats) { + malloc_mutex_postfork_child(tsdn, &arena->tcache_ql_mtx); + } } |