#define JEMALLOC_ARENA_C_ #include "jemalloc/internal/jemalloc_internal.h" /******************************************************************************/ /* Data. */ size_t opt_lg_qspace_max = LG_QSPACE_MAX_DEFAULT; size_t opt_lg_cspace_max = LG_CSPACE_MAX_DEFAULT; ssize_t opt_lg_dirty_mult = LG_DIRTY_MULT_DEFAULT; uint8_t const *small_size2bin; arena_bin_info_t *arena_bin_info; /* Various bin-related settings. */ unsigned nqbins; unsigned ncbins; unsigned nsbins; unsigned nbins; size_t qspace_max; size_t cspace_min; size_t cspace_max; size_t sspace_min; size_t sspace_max; size_t lg_mspace; size_t mspace_mask; /* * const_small_size2bin is a static constant lookup table that in the common * case can be used as-is for small_size2bin. */ #if (LG_TINY_MIN == 2) #define S2B_4(i) i, #define S2B_8(i) S2B_4(i) S2B_4(i) #elif (LG_TINY_MIN == 3) #define S2B_8(i) i, #else # error "Unsupported LG_TINY_MIN" #endif #define S2B_16(i) S2B_8(i) S2B_8(i) #define S2B_32(i) S2B_16(i) S2B_16(i) #define S2B_64(i) S2B_32(i) S2B_32(i) #define S2B_128(i) S2B_64(i) S2B_64(i) #define S2B_256(i) S2B_128(i) S2B_128(i) /* * The number of elements in const_small_size2bin is dependent on the * definition for SUBPAGE. */ static JEMALLOC_ATTR(aligned(CACHELINE)) const uint8_t const_small_size2bin[] = { #if (LG_QUANTUM == 4) /* 16-byte quantum **********************/ # ifdef JEMALLOC_TINY # if (LG_TINY_MIN == 2) S2B_4(0) /* 4 */ S2B_4(1) /* 8 */ S2B_8(2) /* 16 */ # define S2B_QMIN 2 # elif (LG_TINY_MIN == 3) S2B_8(0) /* 8 */ S2B_8(1) /* 16 */ # define S2B_QMIN 1 # else # error "Unsupported LG_TINY_MIN" # endif # else S2B_16(0) /* 16 */ # define S2B_QMIN 0 # endif S2B_16(S2B_QMIN + 1) /* 32 */ S2B_16(S2B_QMIN + 2) /* 48 */ S2B_16(S2B_QMIN + 3) /* 64 */ S2B_16(S2B_QMIN + 4) /* 80 */ S2B_16(S2B_QMIN + 5) /* 96 */ S2B_16(S2B_QMIN + 6) /* 112 */ S2B_16(S2B_QMIN + 7) /* 128 */ # define S2B_CMIN (S2B_QMIN + 8) #else /* 8-byte quantum ***********************/ # ifdef JEMALLOC_TINY # if (LG_TINY_MIN == 2) S2B_4(0) /* 4 */ S2B_4(1) /* 8 */ # define S2B_QMIN 1 # else # error "Unsupported LG_TINY_MIN" # endif # else S2B_8(0) /* 8 */ # define S2B_QMIN 0 # endif S2B_8(S2B_QMIN + 1) /* 16 */ S2B_8(S2B_QMIN + 2) /* 24 */ S2B_8(S2B_QMIN + 3) /* 32 */ S2B_8(S2B_QMIN + 4) /* 40 */ S2B_8(S2B_QMIN + 5) /* 48 */ S2B_8(S2B_QMIN + 6) /* 56 */ S2B_8(S2B_QMIN + 7) /* 64 */ S2B_8(S2B_QMIN + 8) /* 72 */ S2B_8(S2B_QMIN + 9) /* 80 */ S2B_8(S2B_QMIN + 10) /* 88 */ S2B_8(S2B_QMIN + 11) /* 96 */ S2B_8(S2B_QMIN + 12) /* 104 */ S2B_8(S2B_QMIN + 13) /* 112 */ S2B_8(S2B_QMIN + 14) /* 120 */ S2B_8(S2B_QMIN + 15) /* 128 */ # define S2B_CMIN (S2B_QMIN + 16) #endif /****************************************/ S2B_64(S2B_CMIN + 0) /* 192 */ S2B_64(S2B_CMIN + 1) /* 256 */ S2B_64(S2B_CMIN + 2) /* 320 */ S2B_64(S2B_CMIN + 3) /* 384 */ S2B_64(S2B_CMIN + 4) /* 448 */ S2B_64(S2B_CMIN + 5) /* 512 */ # define S2B_SMIN (S2B_CMIN + 6) S2B_256(S2B_SMIN + 0) /* 768 */ S2B_256(S2B_SMIN + 1) /* 1024 */ S2B_256(S2B_SMIN + 2) /* 1280 */ S2B_256(S2B_SMIN + 3) /* 1536 */ S2B_256(S2B_SMIN + 4) /* 1792 */ S2B_256(S2B_SMIN + 5) /* 2048 */ S2B_256(S2B_SMIN + 6) /* 2304 */ S2B_256(S2B_SMIN + 7) /* 2560 */ S2B_256(S2B_SMIN + 8) /* 2816 */ S2B_256(S2B_SMIN + 9) /* 3072 */ S2B_256(S2B_SMIN + 10) /* 3328 */ S2B_256(S2B_SMIN + 11) /* 3584 */ S2B_256(S2B_SMIN + 12) /* 3840 */ #if (STATIC_PAGE_SHIFT == 13) S2B_256(S2B_SMIN + 13) /* 4096 */ S2B_256(S2B_SMIN + 14) /* 4352 */ S2B_256(S2B_SMIN + 15) /* 4608 */ S2B_256(S2B_SMIN + 16) /* 4864 */ S2B_256(S2B_SMIN + 17) /* 5120 */ S2B_256(S2B_SMIN + 18) /* 5376 */ S2B_256(S2B_SMIN + 19) /* 5632 */ S2B_256(S2B_SMIN + 20) /* 5888 */ S2B_256(S2B_SMIN + 21) /* 6144 */ S2B_256(S2B_SMIN + 22) /* 6400 */ S2B_256(S2B_SMIN + 23) /* 6656 */ S2B_256(S2B_SMIN + 24) /* 6912 */ S2B_256(S2B_SMIN + 25) /* 7168 */ S2B_256(S2B_SMIN + 26) /* 7424 */ S2B_256(S2B_SMIN + 27) /* 7680 */ S2B_256(S2B_SMIN + 28) /* 7936 */ #endif }; #undef S2B_1 #undef S2B_2 #undef S2B_4 #undef S2B_8 #undef S2B_16 #undef S2B_32 #undef S2B_64 #undef S2B_128 #undef S2B_256 #undef S2B_QMIN #undef S2B_CMIN #undef S2B_SMIN /******************************************************************************/ /* Function prototypes for non-inline static functions. */ static void arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool large, bool zero); static arena_chunk_t *arena_chunk_alloc(arena_t *arena); static void arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk); static arena_run_t *arena_run_alloc(arena_t *arena, size_t size, bool large, bool zero); static void arena_purge(arena_t *arena, bool all); static void arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty); static void arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, size_t oldsize, size_t newsize); static void arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, size_t oldsize, size_t newsize, bool dirty); static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin); static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin); static void arena_dissociate_bin_run(arena_chunk_t *chunk, arena_run_t *run, arena_bin_t *bin); static void arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, arena_bin_t *bin); static void arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, arena_bin_t *bin); static void arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr, size_t oldsize, size_t size); static bool arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr, size_t oldsize, size_t size, size_t extra, bool zero); static bool arena_ralloc_large(void *ptr, size_t oldsize, size_t size, size_t extra, bool zero); static bool small_size2bin_init(void); #ifdef JEMALLOC_DEBUG static void small_size2bin_validate(void); #endif static bool small_size2bin_init_hard(void); static size_t bin_info_run_size_calc(arena_bin_info_t *bin_info, size_t min_run_size); static bool bin_info_init(void); /******************************************************************************/ static inline int arena_run_comp(arena_chunk_map_t *a, arena_chunk_map_t *b) { uintptr_t a_mapelm = (uintptr_t)a; uintptr_t b_mapelm = (uintptr_t)b; assert(a != NULL); assert(b != NULL); return ((a_mapelm > b_mapelm) - (a_mapelm < b_mapelm)); } /* Generate red-black tree functions. */ rb_gen(static JEMALLOC_ATTR(unused), arena_run_tree_, arena_run_tree_t, arena_chunk_map_t, u.rb_link, arena_run_comp) static inline int arena_avail_comp(arena_chunk_map_t *a, arena_chunk_map_t *b) { int ret; size_t a_size = a->bits & ~PAGE_MASK; size_t b_size = b->bits & ~PAGE_MASK; assert((a->bits & CHUNK_MAP_KEY) == CHUNK_MAP_KEY || (a->bits & CHUNK_MAP_DIRTY) == (b->bits & CHUNK_MAP_DIRTY)); ret = (a_size > b_size) - (a_size < b_size); if (ret == 0) { uintptr_t a_mapelm, b_mapelm; if ((a->bits & CHUNK_MAP_KEY) != CHUNK_MAP_KEY) a_mapelm = (uintptr_t)a; else { /* * Treat keys as though they are lower than anything * else. */ a_mapelm = 0; } b_mapelm = (uintptr_t)b; ret = (a_mapelm > b_mapelm) - (a_mapelm < b_mapelm); } return (ret); } /* Generate red-black tree functions. */ rb_gen(static JEMALLOC_ATTR(unused), arena_avail_tree_, arena_avail_tree_t, arena_chunk_map_t, u.rb_link, arena_avail_comp) static inline void * arena_run_reg_alloc(arena_run_t *run, arena_bin_info_t *bin_info) { void *ret; unsigned regind; bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run + (uintptr_t)bin_info->bitmap_offset); dassert(run->magic == ARENA_RUN_MAGIC); assert(run->nfree > 0); assert(bitmap_full(bitmap, &bin_info->bitmap_info) == false); regind = bitmap_sfu(bitmap, &bin_info->bitmap_info); ret = (void *)((uintptr_t)run + (uintptr_t)bin_info->reg0_offset + (uintptr_t)(bin_info->reg_size * regind)); run->nfree--; if (regind == run->nextind) run->nextind++; assert(regind < run->nextind); return (ret); } static inline void arena_run_reg_dalloc(arena_run_t *run, void *ptr) { arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); size_t binind = arena_bin_index(chunk->arena, run->bin); arena_bin_info_t *bin_info = &arena_bin_info[binind]; unsigned regind = arena_run_regind(run, bin_info, ptr); bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run + (uintptr_t)bin_info->bitmap_offset); assert(run->nfree < bin_info->nregs); /* Freeing an interior pointer can cause assertion failure. */ assert(((uintptr_t)ptr - ((uintptr_t)run + (uintptr_t)bin_info->reg0_offset)) % (uintptr_t)bin_info->reg_size == 0); assert((uintptr_t)ptr >= (uintptr_t)run + (uintptr_t)bin_info->reg0_offset); /* Freeing an unallocated pointer can cause assertion failure. */ assert(bitmap_get(bitmap, &bin_info->bitmap_info, regind)); bitmap_unset(bitmap, &bin_info->bitmap_info, regind); run->nfree++; } #ifdef JEMALLOC_DEBUG static inline void arena_chunk_validate_zeroed(arena_chunk_t *chunk, size_t run_ind) { size_t i; size_t *p = (size_t *)((uintptr_t)chunk + (run_ind << PAGE_SHIFT)); for (i = 0; i < PAGE_SIZE / sizeof(size_t); i++) assert(p[i] == 0); } #endif static void arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool large, bool zero) { arena_chunk_t *chunk; size_t old_ndirty, run_ind, total_pages, need_pages, rem_pages, i; size_t flag_dirty; arena_avail_tree_t *runs_avail; #ifdef JEMALLOC_STATS size_t cactive_diff; #endif chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); old_ndirty = chunk->ndirty; run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT); flag_dirty = chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY; runs_avail = (flag_dirty != 0) ? &arena->runs_avail_dirty : &arena->runs_avail_clean; total_pages = (chunk->map[run_ind-map_bias].bits & ~PAGE_MASK) >> PAGE_SHIFT; assert((chunk->map[run_ind+total_pages-1-map_bias].bits & CHUNK_MAP_DIRTY) == flag_dirty); need_pages = (size >> PAGE_SHIFT); assert(need_pages > 0); assert(need_pages <= total_pages); rem_pages = total_pages - need_pages; arena_avail_tree_remove(runs_avail, &chunk->map[run_ind-map_bias]); #ifdef JEMALLOC_STATS /* Update stats_cactive if nactive is crossing a chunk multiple. */ cactive_diff = CHUNK_CEILING((arena->nactive + need_pages) << PAGE_SHIFT) - CHUNK_CEILING(arena->nactive << PAGE_SHIFT); if (cactive_diff != 0) stats_cactive_add(cactive_diff); #endif arena->nactive += need_pages; /* Keep track of trailing unused pages for later use. */ if (rem_pages > 0) { if (flag_dirty != 0) { chunk->map[run_ind+need_pages-map_bias].bits = (rem_pages << PAGE_SHIFT) | CHUNK_MAP_DIRTY; chunk->map[run_ind+total_pages-1-map_bias].bits = (rem_pages << PAGE_SHIFT) | CHUNK_MAP_DIRTY; } else { chunk->map[run_ind+need_pages-map_bias].bits = (rem_pages << PAGE_SHIFT) | (chunk->map[run_ind+need_pages-map_bias].bits & CHUNK_MAP_UNZEROED); chunk->map[run_ind+total_pages-1-map_bias].bits = (rem_pages << PAGE_SHIFT) | (chunk->map[run_ind+total_pages-1-map_bias].bits & CHUNK_MAP_UNZEROED); } arena_avail_tree_insert(runs_avail, &chunk->map[run_ind+need_pages-map_bias]); } /* Update dirty page accounting. */ if (flag_dirty != 0) { chunk->ndirty -= need_pages; arena->ndirty -= need_pages; } /* * Update the page map separately for large vs. small runs, since it is * possible to avoid iteration for large mallocs. */ if (large) { if (zero) { if (flag_dirty == 0) { /* * The run is clean, so some pages may be * zeroed (i.e. never before touched). */ for (i = 0; i < need_pages; i++) { if ((chunk->map[run_ind+i-map_bias].bits & CHUNK_MAP_UNZEROED) != 0) { memset((void *)((uintptr_t) chunk + ((run_ind+i) << PAGE_SHIFT)), 0, PAGE_SIZE); } #ifdef JEMALLOC_DEBUG else { arena_chunk_validate_zeroed( chunk, run_ind+i); } #endif } } else { /* * The run is dirty, so all pages must be * zeroed. */ memset((void *)((uintptr_t)chunk + (run_ind << PAGE_SHIFT)), 0, (need_pages << PAGE_SHIFT)); } } /* * Set the last element first, in case the run only contains one * page (i.e. both statements set the same element). */ chunk->map[run_ind+need_pages-1-map_bias].bits = CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED | flag_dirty; chunk->map[run_ind-map_bias].bits = size | flag_dirty | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; } else { assert(zero == false); /* * Propagate the dirty and unzeroed flags to the allocated * small run, so that arena_dalloc_bin_run() has the ability to * conditionally trim clean pages. */ chunk->map[run_ind-map_bias].bits = (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_UNZEROED) | CHUNK_MAP_ALLOCATED | flag_dirty; #ifdef JEMALLOC_DEBUG /* * The first page will always be dirtied during small run * initialization, so a validation failure here would not * actually cause an observable failure. */ if (flag_dirty == 0 && (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_UNZEROED) == 0) arena_chunk_validate_zeroed(chunk, run_ind); #endif for (i = 1; i < need_pages - 1; i++) { chunk->map[run_ind+i-map_bias].bits = (i << PAGE_SHIFT) | (chunk->map[run_ind+i-map_bias].bits & CHUNK_MAP_UNZEROED) | CHUNK_MAP_ALLOCATED; #ifdef JEMALLOC_DEBUG if (flag_dirty == 0 && (chunk->map[run_ind+i-map_bias].bits & CHUNK_MAP_UNZEROED) == 0) arena_chunk_validate_zeroed(chunk, run_ind+i); #endif } chunk->map[run_ind+need_pages-1-map_bias].bits = ((need_pages - 1) << PAGE_SHIFT) | (chunk->map[run_ind+need_pages-1-map_bias].bits & CHUNK_MAP_UNZEROED) | CHUNK_MAP_ALLOCATED | flag_dirty; #ifdef JEMALLOC_DEBUG if (flag_dirty == 0 && (chunk->map[run_ind+need_pages-1-map_bias].bits & CHUNK_MAP_UNZEROED) == 0) { arena_chunk_validate_zeroed(chunk, run_ind+need_pages-1); } #endif } } static arena_chunk_t * arena_chunk_alloc(arena_t *arena) { arena_chunk_t *chunk; size_t i; if (arena->spare != NULL) { arena_avail_tree_t *runs_avail; chunk = arena->spare; arena->spare = NULL; /* Insert the run into the appropriate runs_avail_* tree. */ if ((chunk->map[0].bits & CHUNK_MAP_DIRTY) == 0) runs_avail = &arena->runs_avail_clean; else runs_avail = &arena->runs_avail_dirty; assert((chunk->map[0].bits & ~PAGE_MASK) == arena_maxclass); assert((chunk->map[chunk_npages-1-map_bias].bits & ~PAGE_MASK) == arena_maxclass); assert((chunk->map[0].bits & CHUNK_MAP_DIRTY) == (chunk->map[chunk_npages-1-map_bias].bits & CHUNK_MAP_DIRTY)); arena_avail_tree_insert(runs_avail, &chunk->map[0]); } else { bool zero; size_t unzeroed; zero = false; malloc_mutex_unlock(&arena->lock); chunk = (arena_chunk_t *)chunk_alloc(chunksize, false, &zero); malloc_mutex_lock(&arena->lock); if (chunk == NULL) return (NULL); #ifdef JEMALLOC_STATS arena->stats.mapped += chunksize; #endif chunk->arena = arena; ql_elm_new(chunk, link_dirty); chunk->dirtied = false; /* * Claim that no pages are in use, since the header is merely * overhead. */ chunk->ndirty = 0; /* * Initialize the map to contain one maximal free untouched run. * Mark the pages as zeroed iff chunk_alloc() returned a zeroed * chunk. */ unzeroed = zero ? 0 : CHUNK_MAP_UNZEROED; chunk->map[0].bits = arena_maxclass | unzeroed; /* * There is no need to initialize the internal page map entries * unless the chunk is not zeroed. */ if (zero == false) { for (i = map_bias+1; i < chunk_npages-1; i++) chunk->map[i-map_bias].bits = unzeroed; } #ifdef JEMALLOC_DEBUG else { for (i = map_bias+1; i < chunk_npages-1; i++) assert(chunk->map[i-map_bias].bits == unzeroed); } #endif chunk->map[chunk_npages-1-map_bias].bits = arena_maxclass | unzeroed; /* Insert the run into the runs_avail_clean tree. */ arena_avail_tree_insert(&arena->runs_avail_clean, &chunk->map[0]); } return (chunk); } static void arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk) { arena_avail_tree_t *runs_avail; /* * Remove run from the appropriate runs_avail_* tree, so that the arena * does not use it. */ if ((chunk->map[0].bits & CHUNK_MAP_DIRTY) == 0) runs_avail = &arena->runs_avail_clean; else runs_avail = &arena->runs_avail_dirty; arena_avail_tree_remove(runs_avail, &chunk->map[0]); if (arena->spare != NULL) { arena_chunk_t *spare = arena->spare; arena->spare = chunk; if (spare->dirtied) { ql_remove(&chunk->arena->chunks_dirty, spare, link_dirty); arena->ndirty -= spare->ndirty; } malloc_mutex_unlock(&arena->lock); chunk_dealloc((void *)spare, chunksize, true); malloc_mutex_lock(&arena->lock); #ifdef JEMALLOC_STATS arena->stats.mapped -= chunksize; #endif } else arena->spare = chunk; } static arena_run_t * arena_run_alloc(arena_t *arena, size_t size, bool large, bool zero) { arena_chunk_t *chunk; arena_run_t *run; arena_chunk_map_t *mapelm, key; assert(size <= arena_maxclass); assert((size & PAGE_MASK) == 0); /* Search the arena's chunks for the lowest best fit. */ key.bits = size | CHUNK_MAP_KEY; mapelm = arena_avail_tree_nsearch(&arena->runs_avail_dirty, &key); if (mapelm != NULL) { arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm); size_t pageind = (((uintptr_t)mapelm - (uintptr_t)run_chunk->map) / sizeof(arena_chunk_map_t)) + map_bias; run = (arena_run_t *)((uintptr_t)run_chunk + (pageind << PAGE_SHIFT)); arena_run_split(arena, run, size, large, zero); return (run); } mapelm = arena_avail_tree_nsearch(&arena->runs_avail_clean, &key); if (mapelm != NULL) { arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm); size_t pageind = (((uintptr_t)mapelm - (uintptr_t)run_chunk->map) / sizeof(arena_chunk_map_t)) + map_bias; run = (arena_run_t *)((uintptr_t)run_chunk + (pageind << PAGE_SHIFT)); arena_run_split(arena, run, size, large, zero); return (run); } /* * No usable runs. Create a new chunk from which to allocate the run. */ chunk = arena_chunk_alloc(arena); if (chunk != NULL) { run = (arena_run_t *)((uintptr_t)chunk + (map_bias << PAGE_SHIFT)); arena_run_split(arena, run, size, large, zero); return (run); } /* * arena_chunk_alloc() failed, but another thread may have made * sufficient memory available while this one dropped arena->lock in * arena_chunk_alloc(), so search one more time. */ mapelm = arena_avail_tree_nsearch(&arena->runs_avail_dirty, &key); if (mapelm != NULL) { arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm); size_t pageind = (((uintptr_t)mapelm - (uintptr_t)run_chunk->map) / sizeof(arena_chunk_map_t)) + map_bias; run = (arena_run_t *)((uintptr_t)run_chunk + (pageind << PAGE_SHIFT)); arena_run_split(arena, run, size, large, zero); return (run); } mapelm = arena_avail_tree_nsearch(&arena->runs_avail_clean, &key); if (mapelm != NULL) { arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm); size_t pageind = (((uintptr_t)mapelm - (uintptr_t)run_chunk->map) / sizeof(arena_chunk_map_t)) + map_bias; run = (arena_run_t *)((uintptr_t)run_chunk + (pageind << PAGE_SHIFT)); arena_run_split(arena, run, size, large, zero); return (run); } return (NULL); } static inline void arena_maybe_purge(arena_t *arena) { /* Enforce opt_lg_dirty_mult. */ if (opt_lg_dirty_mult >= 0 && arena->ndirty > arena->npurgatory && (arena->ndirty - arena->npurgatory) > chunk_npages && (arena->nactive >> opt_lg_dirty_mult) < (arena->ndirty - arena->npurgatory)) arena_purge(arena, false); } static inline void arena_chunk_purge(arena_t *arena, arena_chunk_t *chunk) { ql_head(arena_chunk_map_t) mapelms; arena_chunk_map_t *mapelm; size_t pageind, flag_unzeroed; #ifdef JEMALLOC_DEBUG size_t ndirty; #endif #ifdef JEMALLOC_STATS size_t nmadvise; #endif ql_new(&mapelms); flag_unzeroed = #ifdef JEMALLOC_PURGE_MADVISE_DONTNEED /* * madvise(..., MADV_DONTNEED) results in zero-filled pages for anonymous * mappings, but not for file-backed mappings. */ # ifdef JEMALLOC_SWAP swap_enabled ? CHUNK_MAP_UNZEROED : # endif 0; #else CHUNK_MAP_UNZEROED; #endif /* * If chunk is the spare, temporarily re-allocate it, 1) so that its * run is reinserted into runs_avail_dirty, and 2) so that it cannot be * completely discarded by another thread while arena->lock is dropped * by this thread. Note that the arena_run_dalloc() call will * implicitly deallocate the chunk, so no explicit action is required * in this function to deallocate the chunk. * * Note that once a chunk contains dirty pages, it cannot again contain * a single run unless 1) it is a dirty run, or 2) this function purges * dirty pages and causes the transition to a single clean run. Thus * (chunk == arena->spare) is possible, but it is not possible for * this function to be called on the spare unless it contains a dirty * run. */ if (chunk == arena->spare) { assert((chunk->map[0].bits & CHUNK_MAP_DIRTY) != 0); arena_chunk_alloc(arena); } /* Temporarily allocate all free dirty runs within chunk. */ for (pageind = map_bias; pageind < chunk_npages;) { mapelm = &chunk->map[pageind-map_bias]; if ((mapelm->bits & CHUNK_MAP_ALLOCATED) == 0) { size_t npages; npages = mapelm->bits >> PAGE_SHIFT; assert(pageind + npages <= chunk_npages); if (mapelm->bits & CHUNK_MAP_DIRTY) { size_t i; #ifdef JEMALLOC_STATS size_t cactive_diff; #endif arena_avail_tree_remove( &arena->runs_avail_dirty, mapelm); mapelm->bits = (npages << PAGE_SHIFT) | flag_unzeroed | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; /* * Update internal elements in the page map, so * that CHUNK_MAP_UNZEROED is properly set. */ for (i = 1; i < npages - 1; i++) { chunk->map[pageind+i-map_bias].bits = flag_unzeroed; } if (npages > 1) { chunk->map[ pageind+npages-1-map_bias].bits = flag_unzeroed | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; } #ifdef JEMALLOC_STATS /* * Update stats_cactive if nactive is crossing a * chunk multiple. */ cactive_diff = CHUNK_CEILING((arena->nactive + npages) << PAGE_SHIFT) - CHUNK_CEILING(arena->nactive << PAGE_SHIFT); if (cactive_diff != 0) stats_cactive_add(cactive_diff); #endif arena->nactive += npages; /* Append to list for later processing. */ ql_elm_new(mapelm, u.ql_link); ql_tail_insert(&mapelms, mapelm, u.ql_link); } pageind += npages; } else { /* Skip allocated run. */ if (mapelm->bits & CHUNK_MAP_LARGE) pageind += mapelm->bits >> PAGE_SHIFT; else { arena_run_t *run = (arena_run_t *)((uintptr_t) chunk + (uintptr_t)(pageind << PAGE_SHIFT)); assert((mapelm->bits >> PAGE_SHIFT) == 0); dassert(run->magic == ARENA_RUN_MAGIC); size_t binind = arena_bin_index(arena, run->bin); arena_bin_info_t *bin_info = &arena_bin_info[binind]; pageind += bin_info->run_size >> PAGE_SHIFT; } } } assert(pageind == chunk_npages); #ifdef JEMALLOC_DEBUG ndirty = chunk->ndirty; #endif #ifdef JEMALLOC_STATS arena->stats.purged += chunk->ndirty; #endif arena->ndirty -= chunk->ndirty; chunk->ndirty = 0; ql_remove(&arena->chunks_dirty, chunk, link_dirty); chunk->dirtied = false; malloc_mutex_unlock(&arena->lock); #ifdef JEMALLOC_STATS nmadvise = 0; #endif ql_foreach(mapelm, &mapelms, u.ql_link) { size_t pageind = (((uintptr_t)mapelm - (uintptr_t)chunk->map) / sizeof(arena_chunk_map_t)) + map_bias; size_t npages = mapelm->bits >> PAGE_SHIFT; assert(pageind + npages <= chunk_npages); #ifdef JEMALLOC_DEBUG assert(ndirty >= npages); ndirty -= npages; #endif #ifdef JEMALLOC_PURGE_MADVISE_DONTNEED madvise((void *)((uintptr_t)chunk + (pageind << PAGE_SHIFT)), (npages << PAGE_SHIFT), MADV_DONTNEED); #elif defined(JEMALLOC_PURGE_MADVISE_FREE) madvise((void *)((uintptr_t)chunk + (pageind << PAGE_SHIFT)), (npages << PAGE_SHIFT), MADV_FREE); #else # error "No method defined for purging unused dirty pages." #endif #ifdef JEMALLOC_STATS nmadvise++; #endif } #ifdef JEMALLOC_DEBUG assert(ndirty == 0); #endif malloc_mutex_lock(&arena->lock); #ifdef JEMALLOC_STATS arena->stats.nmadvise += nmadvise; #endif /* Deallocate runs. */ for (mapelm = ql_first(&mapelms); mapelm != NULL; mapelm = ql_first(&mapelms)) { size_t pageind = (((uintptr_t)mapelm - (uintptr_t)chunk->map) / sizeof(arena_chunk_map_t)) + map_bias; arena_run_t *run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)(pageind << PAGE_SHIFT)); ql_remove(&mapelms, mapelm, u.ql_link); arena_run_dalloc(arena, run, false); } } static void arena_purge(arena_t *arena, bool all) { arena_chunk_t *chunk; size_t npurgatory; #ifdef JEMALLOC_DEBUG size_t ndirty = 0; ql_foreach(chunk, &arena->chunks_dirty, link_dirty) { assert(chunk->dirtied); ndirty += chunk->ndirty; } assert(ndirty == arena->ndirty); #endif assert(arena->ndirty > arena->npurgatory || all); assert(arena->ndirty - arena->npurgatory > chunk_npages || all); assert((arena->nactive >> opt_lg_dirty_mult) < (arena->ndirty - arena->npurgatory) || all); #ifdef JEMALLOC_STATS arena->stats.npurge++; #endif /* * Compute the minimum number of pages that this thread should try to * purge, and add the result to arena->npurgatory. This will keep * multiple threads from racing to reduce ndirty below the threshold. */ npurgatory = arena->ndirty - arena->npurgatory; if (all == false) { assert(npurgatory >= arena->nactive >> opt_lg_dirty_mult); npurgatory -= arena->nactive >> opt_lg_dirty_mult; } arena->npurgatory += npurgatory; while (npurgatory > 0) { /* Get next chunk with dirty pages. */ chunk = ql_first(&arena->chunks_dirty); if (chunk == NULL) { /* * This thread was unable to purge as many pages as * originally intended, due to races with other threads * that either did some of the purging work, or re-used * dirty pages. */ arena->npurgatory -= npurgatory; return; } while (chunk->ndirty == 0) { ql_remove(&arena->chunks_dirty, chunk, link_dirty); chunk->dirtied = false; chunk = ql_first(&arena->chunks_dirty); if (chunk == NULL) { /* Same logic as for above. */ arena->npurgatory -= npurgatory; return; } } if (chunk->ndirty > npurgatory) { /* * This thread will, at a minimum, purge all the dirty * pages in chunk, so set npurgatory to reflect this * thread's commitment to purge the pages. This tends * to reduce the chances of the following scenario: * * 1) This thread sets arena->npurgatory such that * (arena->ndirty - arena->npurgatory) is at the * threshold. * 2) This thread drops arena->lock. * 3) Another thread causes one or more pages to be * dirtied, and immediately determines that it must * purge dirty pages. * * If this scenario *does* play out, that's okay, * because all of the purging work being done really * needs to happen. */ arena->npurgatory += chunk->ndirty - npurgatory; npurgatory = chunk->ndirty; } arena->npurgatory -= chunk->ndirty; npurgatory -= chunk->ndirty; arena_chunk_purge(arena, chunk); } } void arena_purge_all(arena_t *arena) { malloc_mutex_lock(&arena->lock); arena_purge(arena, true); malloc_mutex_unlock(&arena->lock); } static void arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty) { arena_chunk_t *chunk; size_t size, run_ind, run_pages, flag_dirty; arena_avail_tree_t *runs_avail; #ifdef JEMALLOC_STATS size_t cactive_diff; #endif chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT); assert(run_ind >= map_bias); assert(run_ind < chunk_npages); if ((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_LARGE) != 0) { size = chunk->map[run_ind-map_bias].bits & ~PAGE_MASK; assert(size == PAGE_SIZE || (chunk->map[run_ind+(size>>PAGE_SHIFT)-1-map_bias].bits & ~PAGE_MASK) == 0); assert((chunk->map[run_ind+(size>>PAGE_SHIFT)-1-map_bias].bits & CHUNK_MAP_LARGE) != 0); assert((chunk->map[run_ind+(size>>PAGE_SHIFT)-1-map_bias].bits & CHUNK_MAP_ALLOCATED) != 0); } else { size_t binind = arena_bin_index(arena, run->bin); arena_bin_info_t *bin_info = &arena_bin_info[binind]; size = bin_info->run_size; } run_pages = (size >> PAGE_SHIFT); #ifdef JEMALLOC_STATS /* Update stats_cactive if nactive is crossing a chunk multiple. */ cactive_diff = CHUNK_CEILING(arena->nactive << PAGE_SHIFT) - CHUNK_CEILING((arena->nactive - run_pages) << PAGE_SHIFT); if (cactive_diff != 0) stats_cactive_sub(cactive_diff); #endif arena->nactive -= run_pages; /* * The run is dirty if the caller claims to have dirtied it, as well as * if it was already dirty before being allocated. */ if ((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY) != 0) dirty = true; flag_dirty = dirty ? CHUNK_MAP_DIRTY : 0; runs_avail = dirty ? &arena->runs_avail_dirty : &arena->runs_avail_clean; /* Mark pages as unallocated in the chunk map. */ if (dirty) { chunk->map[run_ind-map_bias].bits = size | CHUNK_MAP_DIRTY; chunk->map[run_ind+run_pages-1-map_bias].bits = size | CHUNK_MAP_DIRTY; chunk->ndirty += run_pages; arena->ndirty += run_pages; } else { chunk->map[run_ind-map_bias].bits = size | (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_UNZEROED); chunk->map[run_ind+run_pages-1-map_bias].bits = size | (chunk->map[run_ind+run_pages-1-map_bias].bits & CHUNK_MAP_UNZEROED); } /* Try to coalesce forward. */ if (run_ind + run_pages < chunk_npages && (chunk->map[run_ind+run_pages-map_bias].bits & CHUNK_MAP_ALLOCATED) == 0 && (chunk->map[run_ind+run_pages-map_bias].bits & CHUNK_MAP_DIRTY) == flag_dirty) { size_t nrun_size = chunk->map[run_ind+run_pages-map_bias].bits & ~PAGE_MASK; size_t nrun_pages = nrun_size >> PAGE_SHIFT; /* * Remove successor from runs_avail; the coalesced run is * inserted later. */ assert((chunk->map[run_ind+run_pages+nrun_pages-1-map_bias].bits & ~PAGE_MASK) == nrun_size); assert((chunk->map[run_ind+run_pages+nrun_pages-1-map_bias].bits & CHUNK_MAP_ALLOCATED) == 0); assert((chunk->map[run_ind+run_pages+nrun_pages-1-map_bias].bits & CHUNK_MAP_DIRTY) == flag_dirty); arena_avail_tree_remove(runs_avail, &chunk->map[run_ind+run_pages-map_bias]); size += nrun_size; run_pages += nrun_pages; chunk->map[run_ind-map_bias].bits = size | (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_FLAGS_MASK); chunk->map[run_ind+run_pages-1-map_bias].bits = size | (chunk->map[run_ind+run_pages-1-map_bias].bits & CHUNK_MAP_FLAGS_MASK); } /* Try to coalesce backward. */ if (run_ind > map_bias && (chunk->map[run_ind-1-map_bias].bits & CHUNK_MAP_ALLOCATED) == 0 && (chunk->map[run_ind-1-map_bias].bits & CHUNK_MAP_DIRTY) == flag_dirty) { size_t prun_size = chunk->map[run_ind-1-map_bias].bits & ~PAGE_MASK; size_t prun_pages = prun_size >> PAGE_SHIFT; run_ind -= prun_pages; /* * Remove predecessor from runs_avail; the coalesced run is * inserted later. */ assert((chunk->map[run_ind-map_bias].bits & ~PAGE_MASK) == prun_size); assert((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_ALLOCATED) == 0); assert((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY) == flag_dirty); arena_avail_tree_remove(runs_avail, &chunk->map[run_ind-map_bias]); size += prun_size; run_pages += prun_pages; chunk->map[run_ind-map_bias].bits = size | (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_FLAGS_MASK); chunk->map[run_ind+run_pages-1-map_bias].bits = size | (chunk->map[run_ind+run_pages-1-map_bias].bits & CHUNK_MAP_FLAGS_MASK); } /* Insert into runs_avail, now that coalescing is complete. */ assert((chunk->map[run_ind-map_bias].bits & ~PAGE_MASK) == (chunk->map[run_ind+run_pages-1-map_bias].bits & ~PAGE_MASK)); assert((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY) == (chunk->map[run_ind+run_pages-1-map_bias].bits & CHUNK_MAP_DIRTY)); arena_avail_tree_insert(runs_avail, &chunk->map[run_ind-map_bias]); if (dirty) { /* * Insert into chunks_dirty before potentially calling * arena_chunk_dealloc(), so that chunks_dirty and * arena->ndirty are consistent. */ if (chunk->dirtied == false) { ql_tail_insert(&arena->chunks_dirty, chunk, link_dirty); chunk->dirtied = true; } } /* * Deallocate chunk if it is now completely unused. The bit * manipulation checks whether the first run is unallocated and extends * to the end of the chunk. */ if ((chunk->map[0].bits & (~PAGE_MASK | CHUNK_MAP_ALLOCATED)) == arena_maxclass) arena_chunk_dealloc(arena, chunk); /* * It is okay to do dirty page processing here even if the chunk was * deallocated above, since in that case it is the spare. Waiting * until after possible chunk deallocation to do dirty processing * allows for an old spare to be fully deallocated, thus decreasing the * chances of spuriously crossing the dirty page purging threshold. */ if (dirty) arena_maybe_purge(arena); } static void arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, size_t oldsize, size_t newsize) { size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT; size_t head_npages = (oldsize - newsize) >> PAGE_SHIFT; size_t flag_dirty = chunk->map[pageind-map_bias].bits & CHUNK_MAP_DIRTY; assert(oldsize > newsize); /* * Update the chunk map so that arena_run_dalloc() can treat the * leading run as separately allocated. Set the last element of each * run first, in case of single-page runs. */ assert((chunk->map[pageind-map_bias].bits & CHUNK_MAP_LARGE) != 0); assert((chunk->map[pageind-map_bias].bits & CHUNK_MAP_ALLOCATED) != 0); chunk->map[pageind+head_npages-1-map_bias].bits = flag_dirty | (chunk->map[pageind+head_npages-1-map_bias].bits & CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; chunk->map[pageind-map_bias].bits = (oldsize - newsize) | flag_dirty | (chunk->map[pageind-map_bias].bits & CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; #ifdef JEMALLOC_DEBUG { size_t tail_npages = newsize >> PAGE_SHIFT; assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias] .bits & ~PAGE_MASK) == 0); assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias] .bits & CHUNK_MAP_DIRTY) == flag_dirty); assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias] .bits & CHUNK_MAP_LARGE) != 0); assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias] .bits & CHUNK_MAP_ALLOCATED) != 0); } #endif chunk->map[pageind+head_npages-map_bias].bits = newsize | flag_dirty | (chunk->map[pageind+head_npages-map_bias].bits & CHUNK_MAP_FLAGS_MASK) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; arena_run_dalloc(arena, run, false); } static void arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, size_t oldsize, size_t newsize, bool dirty) { size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT; size_t head_npages = newsize >> PAGE_SHIFT; size_t tail_npages = (oldsize - newsize) >> PAGE_SHIFT; size_t flag_dirty = chunk->map[pageind-map_bias].bits & CHUNK_MAP_DIRTY; assert(oldsize > newsize); /* * Update the chunk map so that arena_run_dalloc() can treat the * trailing run as separately allocated. Set the last element of each * run first, in case of single-page runs. */ assert((chunk->map[pageind-map_bias].bits & CHUNK_MAP_LARGE) != 0); assert((chunk->map[pageind-map_bias].bits & CHUNK_MAP_ALLOCATED) != 0); chunk->map[pageind+head_npages-1-map_bias].bits = flag_dirty | (chunk->map[pageind+head_npages-1-map_bias].bits & CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; chunk->map[pageind-map_bias].bits = newsize | flag_dirty | (chunk->map[pageind-map_bias].bits & CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias].bits & ~PAGE_MASK) == 0); assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias].bits & CHUNK_MAP_LARGE) != 0); assert((chunk->map[pageind+head_npages+tail_npages-1-map_bias].bits & CHUNK_MAP_ALLOCATED) != 0); chunk->map[pageind+head_npages+tail_npages-1-map_bias].bits = flag_dirty | (chunk->map[pageind+head_npages+tail_npages-1-map_bias].bits & CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; chunk->map[pageind+head_npages-map_bias].bits = (oldsize - newsize) | flag_dirty | (chunk->map[pageind+head_npages-map_bias].bits & CHUNK_MAP_UNZEROED) | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)run + newsize), dirty); } static arena_run_t * arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin) { arena_chunk_map_t *mapelm; arena_run_t *run; size_t binind; arena_bin_info_t *bin_info; /* Look for a usable run. */ mapelm = arena_run_tree_first(&bin->runs); if (mapelm != NULL) { arena_chunk_t *chunk; size_t pageind; /* run is guaranteed to have available space. */ arena_run_tree_remove(&bin->runs, mapelm); chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(mapelm); pageind = ((((uintptr_t)mapelm - (uintptr_t)chunk->map) / sizeof(arena_chunk_map_t))) + map_bias; run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind - (mapelm->bits >> PAGE_SHIFT)) << PAGE_SHIFT)); #ifdef JEMALLOC_STATS bin->stats.reruns++; #endif return (run); } /* No existing runs have any space available. */ binind = arena_bin_index(arena, bin); bin_info = &arena_bin_info[binind]; /* Allocate a new run. */ malloc_mutex_unlock(&bin->lock); /******************************/ malloc_mutex_lock(&arena->lock); run = arena_run_alloc(arena, bin_info->run_size, false, false); if (run != NULL) { bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run + (uintptr_t)bin_info->bitmap_offset); /* Initialize run internals. */ run->bin = bin; run->nextind = 0; run->nfree = bin_info->nregs; bitmap_init(bitmap, &bin_info->bitmap_info); #ifdef JEMALLOC_DEBUG run->magic = ARENA_RUN_MAGIC; #endif } malloc_mutex_unlock(&arena->lock); /********************************/ malloc_mutex_lock(&bin->lock); if (run != NULL) { #ifdef JEMALLOC_STATS bin->stats.nruns++; bin->stats.curruns++; if (bin->stats.curruns > bin->stats.highruns) bin->stats.highruns = bin->stats.curruns; #endif return (run); } /* * arena_run_alloc() failed, but another thread may have made * sufficient memory available while this one dropped bin->lock above, * so search one more time. */ mapelm = arena_run_tree_first(&bin->runs); if (mapelm != NULL) { arena_chunk_t *chunk; size_t pageind; /* run is guaranteed to have available space. */ arena_run_tree_remove(&bin->runs, mapelm); chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(mapelm); pageind = ((((uintptr_t)mapelm - (uintptr_t)chunk->map) / sizeof(arena_chunk_map_t))) + map_bias; run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind - (mapelm->bits >> PAGE_SHIFT)) << PAGE_SHIFT)); #ifdef JEMALLOC_STATS bin->stats.reruns++; #endif return (run); } return (NULL); } /* Re-fill bin->runcur, then call arena_run_reg_alloc(). */ static void * arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin) { void *ret; size_t binind; arena_bin_info_t *bin_info; arena_run_t *run; binind = arena_bin_index(arena, bin); bin_info = &arena_bin_info[binind]; bin->runcur = NULL; run = arena_bin_nonfull_run_get(arena, bin); if (bin->runcur != NULL && bin->runcur->nfree > 0) { /* * Another thread updated runcur while this one ran without the * bin lock in arena_bin_nonfull_run_get(). */ dassert(bin->runcur->magic == ARENA_RUN_MAGIC); assert(bin->runcur->nfree > 0); ret = arena_run_reg_alloc(bin->runcur, bin_info); if (run != NULL) { arena_chunk_t *chunk; /* * arena_run_alloc() may have allocated run, or it may * have pulled run from the bin's run tree. Therefore * it is unsafe to make any assumptions about how run * has previously been used, and arena_bin_lower_run() * must be called, as if a region were just deallocated * from the run. */ chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); if (run->nfree == bin_info->nregs) arena_dalloc_bin_run(arena, chunk, run, bin); else arena_bin_lower_run(arena, chunk, run, bin); } return (ret); } if (run == NULL) return (NULL); bin->runcur = run; dassert(bin->runcur->magic == ARENA_RUN_MAGIC); assert(bin->runcur->nfree > 0); return (arena_run_reg_alloc(bin->runcur, bin_info)); } #ifdef JEMALLOC_PROF void arena_prof_accum(arena_t *arena, uint64_t accumbytes) { if (prof_interval != 0) { arena->prof_accumbytes += accumbytes; if (arena->prof_accumbytes >= prof_interval) { prof_idump(); arena->prof_accumbytes -= prof_interval; } } } #endif #ifdef JEMALLOC_TCACHE void arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin, size_t binind # ifdef JEMALLOC_PROF , uint64_t prof_accumbytes # endif ) { unsigned i, nfill; arena_bin_t *bin; arena_run_t *run; void *ptr; assert(tbin->ncached == 0); #ifdef JEMALLOC_PROF malloc_mutex_lock(&arena->lock); arena_prof_accum(arena, prof_accumbytes); malloc_mutex_unlock(&arena->lock); #endif bin = &arena->bins[binind]; malloc_mutex_lock(&bin->lock); for (i = 0, nfill = (tcache_bin_info[binind].ncached_max >> tbin->lg_fill_div); i < nfill; i++) { if ((run = bin->runcur) != NULL && run->nfree > 0) ptr = arena_run_reg_alloc(run, &arena_bin_info[binind]); else ptr = arena_bin_malloc_hard(arena, bin); if (ptr == NULL) break; /* Insert such that low regions get used first. */ tbin->avail[nfill - 1 - i] = ptr; } #ifdef JEMALLOC_STATS bin->stats.allocated += i * arena_bin_info[binind].reg_size; bin->stats.nmalloc += i; bin->stats.nrequests += tbin->tstats.nrequests; bin->stats.nfills++; tbin->tstats.nrequests = 0; #endif malloc_mutex_unlock(&bin->lock); tbin->ncached = i; } #endif void * arena_malloc_small(arena_t *arena, size_t size, bool zero) { void *ret; arena_bin_t *bin; arena_run_t *run; size_t binind; binind = SMALL_SIZE2BIN(size); assert(binind < nbins); bin = &arena->bins[binind]; size = arena_bin_info[binind].reg_size; malloc_mutex_lock(&bin->lock); if ((run = bin->runcur) != NULL && run->nfree > 0) ret = arena_run_reg_alloc(run, &arena_bin_info[binind]); else ret = arena_bin_malloc_hard(arena, bin); if (ret == NULL) { malloc_mutex_unlock(&bin->lock); return (NULL); } #ifdef JEMALLOC_STATS bin->stats.allocated += size; bin->stats.nmalloc++; bin->stats.nrequests++; #endif malloc_mutex_unlock(&bin->lock); #ifdef JEMALLOC_PROF if (isthreaded == false) { malloc_mutex_lock(&arena->lock); arena_prof_accum(arena, size); malloc_mutex_unlock(&arena->lock); } #endif if (zero == false) { #ifdef JEMALLOC_FILL if (opt_junk) memset(ret, 0xa5, size); else if (opt_zero) memset(ret, 0, size); #endif } else memset(ret, 0, size); return (ret); } void * arena_malloc_large(arena_t *arena, size_t size, bool zero) { void *ret; /* Large allocation. */ size = PAGE_CEILING(size); malloc_mutex_lock(&arena->lock); ret = (void *)arena_run_alloc(arena, size, true, zero); if (ret == NULL) { malloc_mutex_unlock(&arena->lock); return (NULL); } #ifdef JEMALLOC_STATS arena->stats.nmalloc_large++; arena->stats.nrequests_large++; arena->stats.allocated_large += size; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nmalloc++; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nrequests++; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns++; if (arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns > arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns) { arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns = arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns; } #endif #ifdef JEMALLOC_PROF arena_prof_accum(arena, size); #endif malloc_mutex_unlock(&arena->lock); if (zero == false) { #ifdef JEMALLOC_FILL if (opt_junk) memset(ret, 0xa5, size); else if (opt_zero) memset(ret, 0, size); #endif } return (ret); } void * arena_malloc(size_t size, bool zero) { assert(size != 0); assert(QUANTUM_CEILING(size) <= arena_maxclass); if (size <= small_maxclass) { #ifdef JEMALLOC_TCACHE tcache_t *tcache; if ((tcache = tcache_get()) != NULL) return (tcache_alloc_small(tcache, size, zero)); else #endif return (arena_malloc_small(choose_arena(), size, zero)); } else { #ifdef JEMALLOC_TCACHE if (size <= tcache_maxclass) { tcache_t *tcache; if ((tcache = tcache_get()) != NULL) return (tcache_alloc_large(tcache, size, zero)); else { return (arena_malloc_large(choose_arena(), size, zero)); } } else #endif return (arena_malloc_large(choose_arena(), size, zero)); } } /* Only handles large allocations that require more than page alignment. */ void * arena_palloc(arena_t *arena, size_t size, size_t alloc_size, size_t alignment, bool zero) { void *ret; size_t offset; arena_chunk_t *chunk; assert((size & PAGE_MASK) == 0); alignment = PAGE_CEILING(alignment); malloc_mutex_lock(&arena->lock); ret = (void *)arena_run_alloc(arena, alloc_size, true, zero); if (ret == NULL) { malloc_mutex_unlock(&arena->lock); return (NULL); } chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ret); offset = (uintptr_t)ret & (alignment - 1); assert((offset & PAGE_MASK) == 0); assert(offset < alloc_size); if (offset == 0) arena_run_trim_tail(arena, chunk, ret, alloc_size, size, false); else { size_t leadsize, trailsize; leadsize = alignment - offset; if (leadsize > 0) { arena_run_trim_head(arena, chunk, ret, alloc_size, alloc_size - leadsize); ret = (void *)((uintptr_t)ret + leadsize); } trailsize = alloc_size - leadsize - size; if (trailsize != 0) { /* Trim trailing space. */ assert(trailsize < alloc_size); arena_run_trim_tail(arena, chunk, ret, size + trailsize, size, false); } } #ifdef JEMALLOC_STATS arena->stats.nmalloc_large++; arena->stats.nrequests_large++; arena->stats.allocated_large += size; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nmalloc++; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nrequests++; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns++; if (arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns > arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns) { arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns = arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns; } #endif malloc_mutex_unlock(&arena->lock); #ifdef JEMALLOC_FILL if (zero == false) { if (opt_junk) memset(ret, 0xa5, size); else if (opt_zero) memset(ret, 0, size); } #endif return (ret); } /* Return the size of the allocation pointed to by ptr. */ size_t arena_salloc(const void *ptr) { size_t ret; arena_chunk_t *chunk; size_t pageind, mapbits; assert(ptr != NULL); assert(CHUNK_ADDR2BASE(ptr) != ptr); chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; mapbits = chunk->map[pageind-map_bias].bits; assert((mapbits & CHUNK_MAP_ALLOCATED) != 0); if ((mapbits & CHUNK_MAP_LARGE) == 0) { arena_run_t *run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind - (mapbits >> PAGE_SHIFT)) << PAGE_SHIFT)); dassert(run->magic == ARENA_RUN_MAGIC); size_t binind = arena_bin_index(chunk->arena, run->bin); arena_bin_info_t *bin_info = &arena_bin_info[binind]; assert(((uintptr_t)ptr - ((uintptr_t)run + (uintptr_t)bin_info->reg0_offset)) % bin_info->reg_size == 0); ret = bin_info->reg_size; } else { assert(((uintptr_t)ptr & PAGE_MASK) == 0); ret = mapbits & ~PAGE_MASK; assert(ret != 0); } return (ret); } #ifdef JEMALLOC_PROF void arena_prof_promoted(const void *ptr, size_t size) { arena_chunk_t *chunk; size_t pageind, binind; assert(ptr != NULL); assert(CHUNK_ADDR2BASE(ptr) != ptr); assert(isalloc(ptr) == PAGE_SIZE); assert(size <= small_maxclass); chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; binind = SMALL_SIZE2BIN(size); assert(binind < nbins); chunk->map[pageind-map_bias].bits = (chunk->map[pageind-map_bias].bits & ~CHUNK_MAP_CLASS_MASK) | ((binind+1) << CHUNK_MAP_CLASS_SHIFT); } size_t arena_salloc_demote(const void *ptr) { size_t ret; arena_chunk_t *chunk; size_t pageind, mapbits; assert(ptr != NULL); assert(CHUNK_ADDR2BASE(ptr) != ptr); chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; mapbits = chunk->map[pageind-map_bias].bits; assert((mapbits & CHUNK_MAP_ALLOCATED) != 0); if ((mapbits & CHUNK_MAP_LARGE) == 0) { arena_run_t *run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind - (mapbits >> PAGE_SHIFT)) << PAGE_SHIFT)); dassert(run->magic == ARENA_RUN_MAGIC); size_t binind = arena_bin_index(chunk->arena, run->bin); arena_bin_info_t *bin_info = &arena_bin_info[binind]; assert(((uintptr_t)ptr - ((uintptr_t)run + (uintptr_t)bin_info->reg0_offset)) % bin_info->reg_size == 0); ret = bin_info->reg_size; } else { assert(((uintptr_t)ptr & PAGE_MASK) == 0); ret = mapbits & ~PAGE_MASK; if (prof_promote && ret == PAGE_SIZE && (mapbits & CHUNK_MAP_CLASS_MASK) != 0) { size_t binind = ((mapbits & CHUNK_MAP_CLASS_MASK) >> CHUNK_MAP_CLASS_SHIFT) - 1; assert(binind < nbins); ret = arena_bin_info[binind].reg_size; } assert(ret != 0); } return (ret); } #endif static void arena_dissociate_bin_run(arena_chunk_t *chunk, arena_run_t *run, arena_bin_t *bin) { /* Dissociate run from bin. */ if (run == bin->runcur) bin->runcur = NULL; else { size_t binind = arena_bin_index(chunk->arena, bin); arena_bin_info_t *bin_info = &arena_bin_info[binind]; if (bin_info->nregs != 1) { size_t run_pageind = (((uintptr_t)run - (uintptr_t)chunk)) >> PAGE_SHIFT; arena_chunk_map_t *run_mapelm = &chunk->map[run_pageind-map_bias]; /* * 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_run_tree_remove(&bin->runs, run_mapelm); } } } static void arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, arena_bin_t *bin) { size_t binind; arena_bin_info_t *bin_info; size_t npages, run_ind, past; assert(run != bin->runcur); assert(arena_run_tree_search(&bin->runs, &chunk->map[ (((uintptr_t)run-(uintptr_t)chunk)>>PAGE_SHIFT)-map_bias]) == NULL); binind = arena_bin_index(chunk->arena, run->bin); bin_info = &arena_bin_info[binind]; malloc_mutex_unlock(&bin->lock); /******************************/ npages = bin_info->run_size >> PAGE_SHIFT; run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT); past = (size_t)(PAGE_CEILING((uintptr_t)run + (uintptr_t)bin_info->reg0_offset + (uintptr_t)(run->nextind * bin_info->reg_size) - (uintptr_t)chunk) >> PAGE_SHIFT); malloc_mutex_lock(&arena->lock); /* * If the run was originally clean, and some pages were never touched, * trim the clean pages before deallocating the dirty portion of the * run. */ if ((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY) == 0 && past - run_ind < npages) { /* * Trim clean pages. Convert to large run beforehand. Set the * last map element first, in case this is a one-page run. */ chunk->map[run_ind+npages-1-map_bias].bits = CHUNK_MAP_LARGE | (chunk->map[run_ind+npages-1-map_bias].bits & CHUNK_MAP_FLAGS_MASK); chunk->map[run_ind-map_bias].bits = bin_info->run_size | CHUNK_MAP_LARGE | (chunk->map[run_ind-map_bias].bits & CHUNK_MAP_FLAGS_MASK); arena_run_trim_tail(arena, chunk, run, (npages << PAGE_SHIFT), ((past - run_ind) << PAGE_SHIFT), false); /* npages = past - run_ind; */ } #ifdef JEMALLOC_DEBUG run->magic = 0; #endif arena_run_dalloc(arena, run, true); malloc_mutex_unlock(&arena->lock); /****************************/ malloc_mutex_lock(&bin->lock); #ifdef JEMALLOC_STATS bin->stats.curruns--; #endif } static void arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, arena_bin_t *bin) { /* * Make sure that bin->runcur always refers to the lowest non-full run, * if one exists. */ if (bin->runcur == NULL) bin->runcur = run; else if ((uintptr_t)run < (uintptr_t)bin->runcur) { /* Switch runcur. */ if (bin->runcur->nfree > 0) { arena_chunk_t *runcur_chunk = CHUNK_ADDR2BASE(bin->runcur); size_t runcur_pageind = (((uintptr_t)bin->runcur - (uintptr_t)runcur_chunk)) >> PAGE_SHIFT; arena_chunk_map_t *runcur_mapelm = &runcur_chunk->map[runcur_pageind-map_bias]; /* Insert runcur. */ arena_run_tree_insert(&bin->runs, runcur_mapelm); } bin->runcur = run; } else { size_t run_pageind = (((uintptr_t)run - (uintptr_t)chunk)) >> PAGE_SHIFT; arena_chunk_map_t *run_mapelm = &chunk->map[run_pageind-map_bias]; assert(arena_run_tree_search(&bin->runs, run_mapelm) == NULL); arena_run_tree_insert(&bin->runs, run_mapelm); } } void arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr, arena_chunk_map_t *mapelm) { size_t pageind; arena_run_t *run; arena_bin_t *bin; #if (defined(JEMALLOC_FILL) || defined(JEMALLOC_STATS)) size_t size; #endif pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind - (mapelm->bits >> PAGE_SHIFT)) << PAGE_SHIFT)); dassert(run->magic == ARENA_RUN_MAGIC); bin = run->bin; size_t binind = arena_bin_index(arena, bin); arena_bin_info_t *bin_info = &arena_bin_info[binind]; #if (defined(JEMALLOC_FILL) || defined(JEMALLOC_STATS)) size = bin_info->reg_size; #endif #ifdef JEMALLOC_FILL if (opt_junk) memset(ptr, 0x5a, size); #endif 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); #ifdef JEMALLOC_STATS bin->stats.allocated -= size; bin->stats.ndalloc++; #endif } #ifdef JEMALLOC_STATS void arena_stats_merge(arena_t *arena, size_t *nactive, size_t *ndirty, arena_stats_t *astats, malloc_bin_stats_t *bstats, malloc_large_stats_t *lstats) { unsigned i; malloc_mutex_lock(&arena->lock); *nactive += arena->nactive; *ndirty += arena->ndirty; astats->mapped += arena->stats.mapped; astats->npurge += arena->stats.npurge; astats->nmadvise += arena->stats.nmadvise; astats->purged += arena->stats.purged; astats->allocated_large += arena->stats.allocated_large; astats->nmalloc_large += arena->stats.nmalloc_large; astats->ndalloc_large += arena->stats.ndalloc_large; astats->nrequests_large += arena->stats.nrequests_large; for (i = 0; i < nlclasses; i++) { lstats[i].nmalloc += arena->stats.lstats[i].nmalloc; lstats[i].ndalloc += arena->stats.lstats[i].ndalloc; lstats[i].nrequests += arena->stats.lstats[i].nrequests; lstats[i].highruns += arena->stats.lstats[i].highruns; lstats[i].curruns += arena->stats.lstats[i].curruns; } malloc_mutex_unlock(&arena->lock); for (i = 0; i < nbins; i++) { arena_bin_t *bin = &arena->bins[i]; malloc_mutex_lock(&bin->lock); bstats[i].allocated += bin->stats.allocated; bstats[i].nmalloc += bin->stats.nmalloc; bstats[i].ndalloc += bin->stats.ndalloc; bstats[i].nrequests += bin->stats.nrequests; #ifdef JEMALLOC_TCACHE bstats[i].nfills += bin->stats.nfills; bstats[i].nflushes += bin->stats.nflushes; #endif bstats[i].nruns += bin->stats.nruns; bstats[i].reruns += bin->stats.reruns; bstats[i].highruns += bin->stats.highruns; bstats[i].curruns += bin->stats.curruns; malloc_mutex_unlock(&bin->lock); } } #endif void arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr) { /* Large allocation. */ #ifdef JEMALLOC_FILL # ifndef JEMALLOC_STATS if (opt_junk) # endif #endif { #if (defined(JEMALLOC_FILL) || defined(JEMALLOC_STATS)) size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; size_t size = chunk->map[pageind-map_bias].bits & ~PAGE_MASK; #endif #ifdef JEMALLOC_FILL # ifdef JEMALLOC_STATS if (opt_junk) # endif memset(ptr, 0x5a, size); #endif #ifdef JEMALLOC_STATS arena->stats.ndalloc_large++; arena->stats.allocated_large -= size; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].ndalloc++; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns--; #endif } arena_run_dalloc(arena, (arena_run_t *)ptr, true); } static void arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr, size_t oldsize, size_t size) { assert(size < oldsize); /* * Shrink the run, and make trailing pages available for other * allocations. */ malloc_mutex_lock(&arena->lock); arena_run_trim_tail(arena, chunk, (arena_run_t *)ptr, oldsize, size, true); #ifdef JEMALLOC_STATS arena->stats.ndalloc_large++; arena->stats.allocated_large -= oldsize; arena->stats.lstats[(oldsize >> PAGE_SHIFT) - 1].ndalloc++; arena->stats.lstats[(oldsize >> PAGE_SHIFT) - 1].curruns--; arena->stats.nmalloc_large++; arena->stats.nrequests_large++; arena->stats.allocated_large += size; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nmalloc++; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nrequests++; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns++; if (arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns > arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns) { arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns = arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns; } #endif malloc_mutex_unlock(&arena->lock); } static bool arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr, size_t oldsize, size_t size, size_t extra, bool zero) { size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; size_t npages = oldsize >> PAGE_SHIFT; size_t followsize; assert(oldsize == (chunk->map[pageind-map_bias].bits & ~PAGE_MASK)); /* Try to extend the run. */ assert(size + extra > oldsize); malloc_mutex_lock(&arena->lock); if (pageind + npages < chunk_npages && (chunk->map[pageind+npages-map_bias].bits & CHUNK_MAP_ALLOCATED) == 0 && (followsize = chunk->map[pageind+npages-map_bias].bits & ~PAGE_MASK) >= size - oldsize) { /* * The next run is available and sufficiently large. Split the * following run, then merge the first part with the existing * allocation. */ size_t flag_dirty; size_t splitsize = (oldsize + followsize <= size + extra) ? followsize : size + extra - oldsize; arena_run_split(arena, (arena_run_t *)((uintptr_t)chunk + ((pageind+npages) << PAGE_SHIFT)), splitsize, true, zero); size = oldsize + splitsize; npages = size >> PAGE_SHIFT; /* * Mark the extended run as dirty if either portion of the run * was dirty before allocation. This is rather pedantic, * because there's not actually any sequence of events that * could cause the resulting run to be passed to * arena_run_dalloc() with the dirty argument set to false * (which is when dirty flag consistency would really matter). */ flag_dirty = (chunk->map[pageind-map_bias].bits & CHUNK_MAP_DIRTY) | (chunk->map[pageind+npages-1-map_bias].bits & CHUNK_MAP_DIRTY); chunk->map[pageind-map_bias].bits = size | flag_dirty | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; chunk->map[pageind+npages-1-map_bias].bits = flag_dirty | CHUNK_MAP_LARGE | CHUNK_MAP_ALLOCATED; #ifdef JEMALLOC_STATS arena->stats.ndalloc_large++; arena->stats.allocated_large -= oldsize; arena->stats.lstats[(oldsize >> PAGE_SHIFT) - 1].ndalloc++; arena->stats.lstats[(oldsize >> PAGE_SHIFT) - 1].curruns--; arena->stats.nmalloc_large++; arena->stats.nrequests_large++; arena->stats.allocated_large += size; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nmalloc++; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nrequests++; arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns++; if (arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns > arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns) { arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns = arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns; } #endif malloc_mutex_unlock(&arena->lock); return (false); } malloc_mutex_unlock(&arena->lock); return (true); } /* * Try to resize a large allocation, in order to avoid copying. This will * always fail if growing an object, and the following run is already in use. */ static bool arena_ralloc_large(void *ptr, size_t oldsize, size_t size, size_t extra, bool zero) { size_t psize; psize = PAGE_CEILING(size + extra); if (psize == oldsize) { /* Same size class. */ #ifdef JEMALLOC_FILL if (opt_junk && size < oldsize) { memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size); } #endif return (false); } else { arena_chunk_t *chunk; arena_t *arena; chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); arena = chunk->arena; dassert(arena->magic == ARENA_MAGIC); if (psize < oldsize) { #ifdef JEMALLOC_FILL /* Fill before shrinking in order avoid a race. */ if (opt_junk) { memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size); } #endif arena_ralloc_large_shrink(arena, chunk, ptr, oldsize, psize); return (false); } else { bool ret = arena_ralloc_large_grow(arena, chunk, ptr, oldsize, PAGE_CEILING(size), psize - PAGE_CEILING(size), zero); #ifdef JEMALLOC_FILL if (ret == false && zero == false && opt_zero) { memset((void *)((uintptr_t)ptr + oldsize), 0, size - oldsize); } #endif return (ret); } } } void * arena_ralloc_no_move(void *ptr, size_t oldsize, size_t size, size_t extra, bool zero) { /* * Avoid moving the allocation if the size class can be left the same. */ if (oldsize <= arena_maxclass) { if (oldsize <= small_maxclass) { assert(arena_bin_info[SMALL_SIZE2BIN(oldsize)].reg_size == oldsize); if ((size + extra <= small_maxclass && SMALL_SIZE2BIN(size + extra) == SMALL_SIZE2BIN(oldsize)) || (size <= oldsize && size + extra >= oldsize)) { #ifdef JEMALLOC_FILL if (opt_junk && size < oldsize) { memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size); } #endif return (ptr); } } else { assert(size <= arena_maxclass); if (size + extra > small_maxclass) { if (arena_ralloc_large(ptr, oldsize, size, extra, zero) == false) return (ptr); } } } /* Reallocation would require a move. */ return (NULL); } void * arena_ralloc(void *ptr, size_t oldsize, size_t size, size_t extra, size_t alignment, bool zero) { void *ret; size_t copysize; /* Try to avoid moving the allocation. */ ret = arena_ralloc_no_move(ptr, oldsize, size, extra, zero); if (ret != NULL) return (ret); /* * size and oldsize are different enough that we need to move the * object. In that case, fall back to allocating new space and * copying. */ if (alignment != 0) { size_t usize = sa2u(size + extra, alignment, NULL); if (usize == 0) return (NULL); ret = ipalloc(usize, alignment, zero); } else ret = arena_malloc(size + extra, zero); if (ret == NULL) { if (extra == 0) return (NULL); /* Try again, this time without extra. */ if (alignment != 0) { size_t usize = sa2u(size, alignment, NULL); if (usize == 0) return (NULL); ret = ipalloc(usize, alignment, zero); } else ret = arena_malloc(size, zero); if (ret == NULL) return (NULL); } /* Junk/zero-filling were already done by ipalloc()/arena_malloc(). */ /* * Copy at most size bytes (not size+extra), since the caller has no * expectation that the extra bytes will be reliably preserved. */ copysize = (size < oldsize) ? size : oldsize; memcpy(ret, ptr, copysize); idalloc(ptr); return (ret); } bool arena_new(arena_t *arena, unsigned ind) { unsigned i; arena_bin_t *bin; arena->ind = ind; arena->nthreads = 0; if (malloc_mutex_init(&arena->lock)) return (true); #ifdef JEMALLOC_STATS memset(&arena->stats, 0, sizeof(arena_stats_t)); arena->stats.lstats = (malloc_large_stats_t *)base_alloc(nlclasses * sizeof(malloc_large_stats_t)); if (arena->stats.lstats == NULL) return (true); memset(arena->stats.lstats, 0, nlclasses * sizeof(malloc_large_stats_t)); # ifdef JEMALLOC_TCACHE ql_new(&arena->tcache_ql); # endif #endif #ifdef JEMALLOC_PROF arena->prof_accumbytes = 0; #endif /* Initialize chunks. */ ql_new(&arena->chunks_dirty); arena->spare = NULL; arena->nactive = 0; arena->ndirty = 0; arena->npurgatory = 0; arena_avail_tree_new(&arena->runs_avail_clean); arena_avail_tree_new(&arena->runs_avail_dirty); /* Initialize bins. */ i = 0; #ifdef JEMALLOC_TINY /* (2^n)-spaced tiny bins. */ for (; i < ntbins; i++) { bin = &arena->bins[i]; if (malloc_mutex_init(&bin->lock)) return (true); bin->runcur = NULL; arena_run_tree_new(&bin->runs); #ifdef JEMALLOC_STATS memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); #endif } #endif /* Quantum-spaced bins. */ for (; i < ntbins + nqbins; i++) { bin = &arena->bins[i]; if (malloc_mutex_init(&bin->lock)) return (true); bin->runcur = NULL; arena_run_tree_new(&bin->runs); #ifdef JEMALLOC_STATS memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); #endif } /* Cacheline-spaced bins. */ for (; i < ntbins + nqbins + ncbins; i++) { bin = &arena->bins[i]; if (malloc_mutex_init(&bin->lock)) return (true); bin->runcur = NULL; arena_run_tree_new(&bin->runs); #ifdef JEMALLOC_STATS memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); #endif } /* Subpage-spaced bins. */ for (; i < nbins; i++) { bin = &arena->bins[i]; if (malloc_mutex_init(&bin->lock)) return (true); bin->runcur = NULL; arena_run_tree_new(&bin->runs); #ifdef JEMALLOC_STATS memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); #endif } #ifdef JEMALLOC_DEBUG arena->magic = ARENA_MAGIC; #endif return (false); } #ifdef JEMALLOC_DEBUG static void small_size2bin_validate(void) { size_t i, size, binind; i = 1; # ifdef JEMALLOC_TINY /* Tiny. */ for (; i < (1U << LG_TINY_MIN); i++) { size = pow2_ceil(1U << LG_TINY_MIN); binind = ffs((int)(size >> (LG_TINY_MIN + 1))); assert(SMALL_SIZE2BIN(i) == binind); } for (; i < qspace_min; i++) { size = pow2_ceil(i); binind = ffs((int)(size >> (LG_TINY_MIN + 1))); assert(SMALL_SIZE2BIN(i) == binind); } # endif /* Quantum-spaced. */ for (; i <= qspace_max; i++) { size = QUANTUM_CEILING(i); binind = ntbins + (size >> LG_QUANTUM) - 1; assert(SMALL_SIZE2BIN(i) == binind); } /* Cacheline-spaced. */ for (; i <= cspace_max; i++) { size = CACHELINE_CEILING(i); binind = ntbins + nqbins + ((size - cspace_min) >> LG_CACHELINE); assert(SMALL_SIZE2BIN(i) == binind); } /* Sub-page. */ for (; i <= sspace_max; i++) { size = SUBPAGE_CEILING(i); binind = ntbins + nqbins + ncbins + ((size - sspace_min) >> LG_SUBPAGE); assert(SMALL_SIZE2BIN(i) == binind); } } #endif static bool small_size2bin_init(void) { if (opt_lg_qspace_max != LG_QSPACE_MAX_DEFAULT || opt_lg_cspace_max != LG_CSPACE_MAX_DEFAULT || (sizeof(const_small_size2bin) != ((small_maxclass-1) >> LG_TINY_MIN) + 1)) return (small_size2bin_init_hard()); small_size2bin = const_small_size2bin; #ifdef JEMALLOC_DEBUG small_size2bin_validate(); #endif return (false); } static bool small_size2bin_init_hard(void) { size_t i, size, binind; uint8_t *custom_small_size2bin; #define CUSTOM_SMALL_SIZE2BIN(s) \ custom_small_size2bin[(s-1) >> LG_TINY_MIN] assert(opt_lg_qspace_max != LG_QSPACE_MAX_DEFAULT || opt_lg_cspace_max != LG_CSPACE_MAX_DEFAULT || (sizeof(const_small_size2bin) != ((small_maxclass-1) >> LG_TINY_MIN) + 1)); custom_small_size2bin = (uint8_t *) base_alloc(small_maxclass >> LG_TINY_MIN); if (custom_small_size2bin == NULL) return (true); i = 1; #ifdef JEMALLOC_TINY /* Tiny. */ for (; i < (1U << LG_TINY_MIN); i += TINY_MIN) { size = pow2_ceil(1U << LG_TINY_MIN); binind = ffs((int)(size >> (LG_TINY_MIN + 1))); CUSTOM_SMALL_SIZE2BIN(i) = binind; } for (; i < qspace_min; i += TINY_MIN) { size = pow2_ceil(i); binind = ffs((int)(size >> (LG_TINY_MIN + 1))); CUSTOM_SMALL_SIZE2BIN(i) = binind; } #endif /* Quantum-spaced. */ for (; i <= qspace_max; i += TINY_MIN) { size = QUANTUM_CEILING(i); binind = ntbins + (size >> LG_QUANTUM) - 1; CUSTOM_SMALL_SIZE2BIN(i) = binind; } /* Cacheline-spaced. */ for (; i <= cspace_max; i += TINY_MIN) { size = CACHELINE_CEILING(i); binind = ntbins + nqbins + ((size - cspace_min) >> LG_CACHELINE); CUSTOM_SMALL_SIZE2BIN(i) = binind; } /* Sub-page. */ for (; i <= sspace_max; i += TINY_MIN) { size = SUBPAGE_CEILING(i); binind = ntbins + nqbins + ncbins + ((size - sspace_min) >> LG_SUBPAGE); CUSTOM_SMALL_SIZE2BIN(i) = binind; } small_size2bin = custom_small_size2bin; #ifdef JEMALLOC_DEBUG small_size2bin_validate(); #endif return (false); #undef CUSTOM_SMALL_SIZE2BIN } /* * Calculate bin_info->run_size such that it meets the following constraints: * * *) bin_info->run_size >= min_run_size * *) bin_info->run_size <= arena_maxclass * *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed). * *) bin_info->nregs <= RUN_MAXREGS * * bin_info->nregs, bin_info->bitmap_offset, and bin_info->reg0_offset are also * calculated here, since these settings are all interdependent. */ static size_t bin_info_run_size_calc(arena_bin_info_t *bin_info, size_t min_run_size) { size_t try_run_size, good_run_size; uint32_t try_nregs, good_nregs; uint32_t try_hdr_size, good_hdr_size; uint32_t try_bitmap_offset, good_bitmap_offset; #ifdef JEMALLOC_PROF uint32_t try_ctx0_offset, good_ctx0_offset; #endif uint32_t try_reg0_offset, good_reg0_offset; assert(min_run_size >= PAGE_SIZE); assert(min_run_size <= arena_maxclass); /* * Calculate known-valid settings before entering the run_size * expansion loop, so that the first part of the loop always copies * valid settings. * * The do..while loop iteratively reduces the number of regions until * the run header and the regions no longer overlap. A closed formula * would be quite messy, since there is an interdependency between the * header's mask length and the number of regions. */ try_run_size = min_run_size; try_nregs = ((try_run_size - sizeof(arena_run_t)) / bin_info->reg_size) + 1; /* Counter-act try_nregs-- in loop. */ if (try_nregs > RUN_MAXREGS) { try_nregs = RUN_MAXREGS + 1; /* Counter-act try_nregs-- in loop. */ } do { try_nregs--; try_hdr_size = sizeof(arena_run_t); /* Pad to a long boundary. */ try_hdr_size = LONG_CEILING(try_hdr_size); try_bitmap_offset = try_hdr_size; /* Add space for bitmap. */ try_hdr_size += bitmap_size(try_nregs); #ifdef JEMALLOC_PROF if (opt_prof && prof_promote == false) { /* Pad to a quantum boundary. */ try_hdr_size = QUANTUM_CEILING(try_hdr_size); try_ctx0_offset = try_hdr_size; /* Add space for one (prof_ctx_t *) per region. */ try_hdr_size += try_nregs * sizeof(prof_ctx_t *); } else try_ctx0_offset = 0; #endif try_reg0_offset = try_run_size - (try_nregs * bin_info->reg_size); } while (try_hdr_size > try_reg0_offset); /* run_size expansion loop. */ do { /* * Copy valid settings before trying more aggressive settings. */ good_run_size = try_run_size; good_nregs = try_nregs; good_hdr_size = try_hdr_size; good_bitmap_offset = try_bitmap_offset; #ifdef JEMALLOC_PROF good_ctx0_offset = try_ctx0_offset; #endif good_reg0_offset = try_reg0_offset; /* Try more aggressive settings. */ try_run_size += PAGE_SIZE; try_nregs = ((try_run_size - sizeof(arena_run_t)) / bin_info->reg_size) + 1; /* Counter-act try_nregs-- in loop. */ if (try_nregs > RUN_MAXREGS) { try_nregs = RUN_MAXREGS + 1; /* Counter-act try_nregs-- in loop. */ } do { try_nregs--; try_hdr_size = sizeof(arena_run_t); /* Pad to a long boundary. */ try_hdr_size = LONG_CEILING(try_hdr_size); try_bitmap_offset = try_hdr_size; /* Add space for bitmap. */ try_hdr_size += bitmap_size(try_nregs); #ifdef JEMALLOC_PROF if (opt_prof && prof_promote == false) { /* Pad to a quantum boundary. */ try_hdr_size = QUANTUM_CEILING(try_hdr_size); try_ctx0_offset = try_hdr_size; /* * Add space for one (prof_ctx_t *) per region. */ try_hdr_size += try_nregs * sizeof(prof_ctx_t *); } #endif try_reg0_offset = try_run_size - (try_nregs * bin_info->reg_size); } while (try_hdr_size > try_reg0_offset); } while (try_run_size <= arena_maxclass && try_run_size <= arena_maxclass && RUN_MAX_OVRHD * (bin_info->reg_size << 3) > RUN_MAX_OVRHD_RELAX && (try_reg0_offset << RUN_BFP) > RUN_MAX_OVRHD * try_run_size && try_nregs < RUN_MAXREGS); assert(good_hdr_size <= good_reg0_offset); /* Copy final settings. */ bin_info->run_size = good_run_size; bin_info->nregs = good_nregs; bin_info->bitmap_offset = good_bitmap_offset; #ifdef JEMALLOC_PROF bin_info->ctx0_offset = good_ctx0_offset; #endif bin_info->reg0_offset = good_reg0_offset; return (good_run_size); } static bool bin_info_init(void) { arena_bin_info_t *bin_info; unsigned i; size_t prev_run_size; arena_bin_info = base_alloc(sizeof(arena_bin_info_t) * nbins); if (arena_bin_info == NULL) return (true); prev_run_size = PAGE_SIZE; i = 0; #ifdef JEMALLOC_TINY /* (2^n)-spaced tiny bins. */ for (; i < ntbins; i++) { bin_info = &arena_bin_info[i]; bin_info->reg_size = (1U << (LG_TINY_MIN + i)); prev_run_size = bin_info_run_size_calc(bin_info, prev_run_size); bitmap_info_init(&bin_info->bitmap_info, bin_info->nregs); } #endif /* Quantum-spaced bins. */ for (; i < ntbins + nqbins; i++) { bin_info = &arena_bin_info[i]; bin_info->reg_size = (i - ntbins + 1) << LG_QUANTUM; prev_run_size = bin_info_run_size_calc(bin_info, prev_run_size); bitmap_info_init(&bin_info->bitmap_info, bin_info->nregs); } /* Cacheline-spaced bins. */ for (; i < ntbins + nqbins + ncbins; i++) { bin_info = &arena_bin_info[i]; bin_info->reg_size = cspace_min + ((i - (ntbins + nqbins)) << LG_CACHELINE); prev_run_size = bin_info_run_size_calc(bin_info, prev_run_size); bitmap_info_init(&bin_info->bitmap_info, bin_info->nregs); } /* Subpage-spaced bins. */ for (; i < nbins; i++) { bin_info = &arena_bin_info[i]; bin_info->reg_size = sspace_min + ((i - (ntbins + nqbins + ncbins)) << LG_SUBPAGE); prev_run_size = bin_info_run_size_calc(bin_info, prev_run_size); bitmap_info_init(&bin_info->bitmap_info, bin_info->nregs); } return (false); } bool arena_boot(void) { size_t header_size; unsigned i; /* Set variables according to the value of opt_lg_[qc]space_max. */ qspace_max = (1U << opt_lg_qspace_max); cspace_min = CACHELINE_CEILING(qspace_max); if (cspace_min == qspace_max) cspace_min += CACHELINE; cspace_max = (1U << opt_lg_cspace_max); sspace_min = SUBPAGE_CEILING(cspace_max); if (sspace_min == cspace_max) sspace_min += SUBPAGE; assert(sspace_min < PAGE_SIZE); sspace_max = PAGE_SIZE - SUBPAGE; #ifdef JEMALLOC_TINY assert(LG_QUANTUM >= LG_TINY_MIN); #endif assert(ntbins <= LG_QUANTUM); nqbins = qspace_max >> LG_QUANTUM; ncbins = ((cspace_max - cspace_min) >> LG_CACHELINE) + 1; nsbins = ((sspace_max - sspace_min) >> LG_SUBPAGE) + 1; nbins = ntbins + nqbins + ncbins + nsbins; /* * The small_size2bin lookup table uses uint8_t to encode each bin * index, so we cannot support more than 256 small size classes. This * limit is difficult to exceed (not even possible with 16B quantum and * 4KiB pages), and such configurations are impractical, but * nonetheless we need to protect against this case in order to avoid * undefined behavior. * * Further constrain nbins to 255 if prof_promote is true, since all * small size classes, plus a "not small" size class must be stored in * 8 bits of arena_chunk_map_t's bits field. */ #ifdef JEMALLOC_PROF if (opt_prof && prof_promote) { if (nbins > 255) { char line_buf[UMAX2S_BUFSIZE]; malloc_write(": Too many small size classes ("); malloc_write(u2s(nbins, 10, line_buf)); malloc_write(" > max 255)\n"); abort(); } } else #endif if (nbins > 256) { char line_buf[UMAX2S_BUFSIZE]; malloc_write(": Too many small size classes ("); malloc_write(u2s(nbins, 10, line_buf)); malloc_write(" > max 256)\n"); abort(); } /* * Compute the header size such that it is large enough to contain the * page map. The page map is biased to omit entries for the header * itself, so some iteration is necessary to compute the map bias. * * 1) Compute safe header_size and map_bias values that include enough * space for an unbiased page map. * 2) Refine map_bias based on (1) to omit the header pages in the page * map. The resulting map_bias may be one too small. * 3) Refine map_bias based on (2). The result will be >= the result * from (2), and will always be correct. */ map_bias = 0; for (i = 0; i < 3; i++) { header_size = offsetof(arena_chunk_t, map) + (sizeof(arena_chunk_map_t) * (chunk_npages-map_bias)); map_bias = (header_size >> PAGE_SHIFT) + ((header_size & PAGE_MASK) != 0); } assert(map_bias > 0); arena_maxclass = chunksize - (map_bias << PAGE_SHIFT); if (small_size2bin_init()) return (true); if (bin_info_init()) return (true); return (false); }