diff options
Diffstat (limited to 'lib/libc/stdlib')
| -rw-r--r-- | lib/libc/stdlib/malloc.c | 290 |
1 files changed, 133 insertions, 157 deletions
diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c index 502c3f9..01160f4 100644 --- a/lib/libc/stdlib/malloc.c +++ b/lib/libc/stdlib/malloc.c @@ -70,9 +70,9 @@ * | | 8 kB | * | | 12 kB | * | | ... | - * | | 1004 kB | * | | 1008 kB | * | | 1012 kB | + * | | 1016 kB | * |=====================================| * | Huge | 1 MB | * | | 2 MB | @@ -482,8 +482,11 @@ struct arena_chunk_s { /* Arena that owns the chunk. */ arena_t *arena; - /* Linkage for the arena's chunk tree. */ - rb_node(arena_chunk_t) link; + /* Linkage for the arena's chunks_all tree. */ + rb_node(arena_chunk_t) link_all; + + /* Linkage for the arena's chunks_dirty tree. */ + rb_node(arena_chunk_t) link_dirty; /* * Number of pages in use. This is maintained in order to make @@ -584,15 +587,25 @@ struct arena_s { arena_stats_t stats; #endif + /* Tree of all chunks this arena manages. */ + arena_chunk_tree_t chunks_all; + /* - * Tree of chunks this arena manages. + * Tree of dirty-page-containing chunks this arena manages. This tree + * is maintained in addition to chunks_all in order to make + * deallocation O(lg d), where 'd' is the size of chunks_dirty. + * + * Without this tree, deallocation would be O(a), where 'a' is the size + * of chunks_all. Since dirty pages are purged in descending memory + * order, it would not be difficult to trigger something approaching + * worst case behavior with a series of large deallocations. */ - arena_chunk_tree_t chunks; + arena_chunk_tree_t chunks_dirty; /* * In order to avoid rapid chunk allocation/deallocation when an arena * oscillates right on the cusp of needing a new chunk, cache the most - * recently freed chunk. The spare is left in the arena's chunk tree + * recently freed chunk. The spare is left in the arena's chunk trees * until it is deleted. * * There is one spare chunk per arena, rather than one spare total, in @@ -1432,20 +1445,9 @@ extent_szad_comp(extent_node_t *a, extent_node_t *b) return (ret); } -/* Wrap large red-black tree macros in functions. */ -static void -extent_tree_szad_insert(extent_tree_t *tree, extent_node_t *extent) -{ - - rb_insert(extent_node_t, link_szad, extent_szad_comp, tree, extent); -} - -static void -extent_tree_szad_remove(extent_tree_t *tree, extent_node_t *extent) -{ - - rb_remove(extent_node_t, link_szad, extent_szad_comp, tree, extent); -} +/* Wrap red-black tree macros in functions. */ +rb_wrap(__unused static, extent_tree_szad_, extent_tree_t, extent_node_t, + link_szad, extent_szad_comp) static inline int extent_ad_comp(extent_node_t *a, extent_node_t *b) @@ -1456,20 +1458,9 @@ extent_ad_comp(extent_node_t *a, extent_node_t *b) return ((a_addr > b_addr) - (a_addr < b_addr)); } -/* Wrap large red-black tree macros in functions. */ -static void -extent_tree_ad_insert(extent_tree_t *tree, extent_node_t *extent) -{ - - rb_insert(extent_node_t, link_ad, extent_ad_comp, tree, extent); -} - -static void -extent_tree_ad_remove(extent_tree_t *tree, extent_node_t *extent) -{ - - rb_remove(extent_node_t, link_ad, extent_ad_comp, tree, extent); -} +/* Wrap red-black tree macros in functions. */ +rb_wrap(__unused static, extent_tree_ad_, extent_tree_t, extent_node_t, link_ad, + extent_ad_comp) /* * End extent tree code. @@ -1592,8 +1583,7 @@ chunk_recycle_dss(size_t size, bool zero) key.addr = NULL; key.size = size; malloc_mutex_lock(&dss_mtx); - rb_nsearch(extent_node_t, link_szad, extent_szad_comp, &dss_chunks_szad, - &key, node); + node = extent_tree_szad_nsearch(&dss_chunks_szad, &key); if (node != NULL) { void *ret = node->addr; @@ -1751,8 +1741,7 @@ chunk_dealloc_dss_record(void *chunk, size_t size) extent_node_t *node, *prev, key; key.addr = (void *)((uintptr_t)chunk + size); - rb_nsearch(extent_node_t, link_ad, extent_ad_comp, &dss_chunks_ad, - &key, node); + node = extent_tree_ad_nsearch(&dss_chunks_ad, &key); /* Try to coalesce forward. */ if (node != NULL && node->addr == key.addr) { /* @@ -1782,8 +1771,7 @@ chunk_dealloc_dss_record(void *chunk, size_t size) } /* Try to coalesce backward. */ - rb_prev(extent_node_t, link_ad, extent_ad_comp, &dss_chunks_ad, node, - prev); + prev = extent_tree_ad_prev(&dss_chunks_ad, node); if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) == chunk) { /* @@ -2023,20 +2011,11 @@ arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b) return ((a_chunk > b_chunk) - (a_chunk < b_chunk)); } -/* Wrap large red-black tree macros in functions. */ -static void -arena_chunk_tree_insert(arena_chunk_tree_t *tree, arena_chunk_t *chunk) -{ - - rb_insert(arena_chunk_t, link, arena_chunk_comp, tree, chunk); -} - -static void -arena_chunk_tree_remove(arena_chunk_tree_t *tree, arena_chunk_t *chunk) -{ - - rb_remove(arena_chunk_t, link, arena_chunk_comp, tree, chunk); -} +/* Wrap red-black tree macros in functions. */ +rb_wrap(__unused static, arena_chunk_tree_all_, arena_chunk_tree_t, + arena_chunk_t, link_all, arena_chunk_comp) +rb_wrap(__unused static, arena_chunk_tree_dirty_, arena_chunk_tree_t, + arena_chunk_t, link_dirty, arena_chunk_comp) static inline int arena_run_comp(arena_run_t *a, arena_run_t *b) @@ -2050,27 +2029,16 @@ arena_run_comp(arena_run_t *a, arena_run_t *b) return ((a_run > b_run) - (a_run < b_run)); } -/* Wrap large red-black tree macros in functions. */ -static void -arena_run_tree_insert(arena_run_tree_t *tree, arena_run_t *run) -{ - - rb_insert(arena_run_t, link, arena_run_comp, tree, run); -} - -static void -arena_run_tree_remove(arena_run_tree_t *tree, arena_run_t *run) -{ - - rb_remove(arena_run_t, link, arena_run_comp, tree, run); -} +/* Wrap red-black tree macros in functions. */ +rb_wrap(__unused static, arena_run_tree_, arena_run_tree_t, arena_run_t, link, + arena_run_comp) static extent_node_t * arena_chunk_node_alloc(arena_chunk_t *chunk) { extent_node_t *ret; - rb_first(extent_node_t, link_ad, &chunk->nodes, ret); + ret = extent_tree_ad_first(&chunk->nodes); if (ret != NULL) extent_tree_ad_remove(&chunk->nodes, ret); else { @@ -2261,19 +2229,19 @@ arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool small, bool zero) { arena_chunk_t *chunk; - size_t run_ind, total_pages, need_pages, rem_pages, i; + size_t old_ndirty, run_ind, total_pages, need_pages, rem_pages, i; extent_node_t *nodeA, *nodeB, key; /* Insert a node into runs_alloced_ad for the first part of the run. */ chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); + old_ndirty = chunk->ndirty; nodeA = arena_chunk_node_alloc(chunk); nodeA->addr = run; nodeA->size = size; extent_tree_ad_insert(&arena->runs_alloced_ad, nodeA); key.addr = run; - rb_search(extent_node_t, link_ad, extent_ad_comp, &arena->runs_avail_ad, - &key, nodeB); + nodeB = extent_tree_ad_search(&arena->runs_avail_ad, &key); assert(nodeB != NULL); run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) @@ -2326,6 +2294,8 @@ arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool small, } chunk->pages_used += need_pages; + if (chunk->ndirty == 0 && old_ndirty > 0) + arena_chunk_tree_dirty_remove(&arena->chunks_dirty, chunk); } static arena_chunk_t * @@ -2347,7 +2317,7 @@ arena_chunk_alloc(arena_t *arena) chunk->arena = arena; - arena_chunk_tree_insert(&arena->chunks, chunk); + arena_chunk_tree_all_insert(&arena->chunks_all, chunk); /* * Claim that no pages are in use, since the header is merely @@ -2367,7 +2337,7 @@ arena_chunk_alloc(arena_t *arena) arena_chunk_header_npages)); /* Initialize the tree of unused extent nodes. */ - rb_tree_new(extent_node_t, link_ad, &chunk->nodes); + extent_tree_ad_new(&chunk->nodes); chunk->nodes_past = (extent_node_t *)QUANTUM_CEILING( (uintptr_t)&chunk->map[chunk_npages]); } @@ -2389,8 +2359,13 @@ arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk) extent_node_t *node, key; if (arena->spare != NULL) { - arena_chunk_tree_remove(&chunk->arena->chunks, arena->spare); - arena->ndirty -= arena->spare->ndirty; + arena_chunk_tree_all_remove(&chunk->arena->chunks_all, + arena->spare); + if (arena->spare->ndirty > 0) { + arena_chunk_tree_dirty_remove( + &chunk->arena->chunks_dirty, arena->spare); + arena->ndirty -= arena->spare->ndirty; + } chunk_dealloc((void *)arena->spare, chunksize); #ifdef MALLOC_STATS arena->stats.mapped -= chunksize; @@ -2400,13 +2375,12 @@ arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk) /* * Remove run from the runs trees, regardless of whether this chunk * will be cached, so that the arena does not use it. Dirty page - * flushing only uses the chunks tree, so leaving this chunk in that - * tree is sufficient for that purpose. + * flushing only uses the chunks_dirty tree, so leaving this chunk in + * the chunks_* trees is sufficient for that purpose. */ key.addr = (void *)((uintptr_t)chunk + (arena_chunk_header_npages << pagesize_2pow)); - rb_search(extent_node_t, link_ad, extent_ad_comp, &arena->runs_avail_ad, - &key, node); + node = extent_tree_ad_search(&arena->runs_avail_ad, &key); assert(node != NULL); extent_tree_szad_remove(&arena->runs_avail_szad, node); extent_tree_ad_remove(&arena->runs_avail_ad, node); @@ -2429,8 +2403,7 @@ arena_run_alloc(arena_t *arena, size_t size, bool small, bool zero) /* Search the arena's chunks for the lowest best fit. */ key.addr = NULL; key.size = size; - rb_nsearch(extent_node_t, link_szad, extent_szad_comp, - &arena->runs_avail_szad, &key, node); + node = extent_tree_szad_nsearch(&arena->runs_avail_szad, &key); if (node != NULL) { run = (arena_run_t *)node->addr; arena_run_split(arena, run, size, small, zero); @@ -2454,13 +2427,21 @@ static void arena_purge(arena_t *arena) { arena_chunk_t *chunk; + size_t i, npages; #ifdef MALLOC_DEBUG size_t ndirty; ndirty = 0; - rb_foreach_begin(arena_chunk_t, link, &arena->chunks, chunk) { + rb_foreach_begin(arena_chunk_t, link_all, &arena->chunks_all, chunk) { ndirty += chunk->ndirty; - } rb_foreach_end(arena_chunk_t, link, &arena->chunks, chunk) + } rb_foreach_end(arena_chunk_t, link_all, &arena->chunks_all, chunk) + assert(ndirty == arena->ndirty); + + ndirty = 0; + rb_foreach_begin(arena_chunk_t, link_dirty, &arena->chunks_dirty, + chunk) { + ndirty += chunk->ndirty; + } rb_foreach_end(arena_chunk_t, link_dirty, &arena->chunks_dirty, chunk) assert(ndirty == arena->ndirty); #endif assert(arena->ndirty > opt_dirty_max); @@ -2471,47 +2452,48 @@ arena_purge(arena_t *arena) /* * Iterate downward through chunks until enough dirty memory has been + * purged. Terminate as soon as possible in order to minimize the + * number of system calls, even if a chunk has only been partially * purged. */ - rb_foreach_reverse_begin(arena_chunk_t, link, &arena->chunks, chunk) { - if (chunk->ndirty > 0) { - size_t i; - - for (i = chunk_npages - 1; i >= - arena_chunk_header_npages; i--) { - if (chunk->map[i] & CHUNK_MAP_DIRTY) { - size_t npages; - - chunk->map[i] = (CHUNK_MAP_LARGE | - CHUNK_MAP_POS_MASK); - chunk->ndirty--; - arena->ndirty--; - /* Find adjacent dirty run(s). */ - for (npages = 1; i > - arena_chunk_header_npages && - (chunk->map[i - 1] & - CHUNK_MAP_DIRTY); npages++) { - i--; - chunk->map[i] = (CHUNK_MAP_LARGE - | CHUNK_MAP_POS_MASK); - chunk->ndirty--; - arena->ndirty--; - } - - madvise((void *)((uintptr_t)chunk + (i - << pagesize_2pow)), pagesize * - npages, MADV_FREE); + while (arena->ndirty > (opt_dirty_max >> 1)) { + chunk = arena_chunk_tree_dirty_last(&arena->chunks_dirty); + assert(chunk != NULL); + + for (i = chunk_npages - 1; chunk->ndirty > 0; i--) { + assert(i >= arena_chunk_header_npages); + + if (chunk->map[i] & CHUNK_MAP_DIRTY) { + chunk->map[i] = (CHUNK_MAP_LARGE | + CHUNK_MAP_POS_MASK); + /* Find adjacent dirty run(s). */ + for (npages = 1; i > arena_chunk_header_npages + && (chunk->map[i - 1] & CHUNK_MAP_DIRTY); + npages++) { + i--; + chunk->map[i] = (CHUNK_MAP_LARGE + | CHUNK_MAP_POS_MASK); + } + chunk->ndirty -= npages; + arena->ndirty -= npages; + + madvise((void *)((uintptr_t)chunk + (i << + pagesize_2pow)), pagesize * npages, + MADV_FREE); #ifdef MALLOC_STATS - arena->stats.nmadvise++; - arena->stats.purged += npages; + arena->stats.nmadvise++; + arena->stats.purged += npages; #endif - if (arena->ndirty <= (opt_dirty_max >> - 1)) - return; - } + if (arena->ndirty <= (opt_dirty_max >> 1)) + break; } } - } rb_foreach_reverse_end(arena_chunk_t, link, &arena->chunks, chunk) + + if (chunk->ndirty == 0) { + arena_chunk_tree_dirty_remove(&arena->chunks_dirty, + chunk); + } + } } static void @@ -2523,8 +2505,7 @@ arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty) /* Remove run from runs_alloced_ad. */ key.addr = run; - rb_search(extent_node_t, link_ad, extent_ad_comp, - &arena->runs_alloced_ad, &key, nodeB); + nodeB = extent_tree_ad_search(&arena->runs_alloced_ad, &key); assert(nodeB != NULL); extent_tree_ad_remove(&arena->runs_alloced_ad, nodeB); size = nodeB->size; @@ -2546,9 +2527,14 @@ arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty) assert((chunk->map[run_ind + i] & CHUNK_MAP_DIRTY) == 0); chunk->map[run_ind + i] |= CHUNK_MAP_DIRTY; - chunk->ndirty++; - arena->ndirty++; } + + if (chunk->ndirty == 0) { + arena_chunk_tree_dirty_insert(&arena->chunks_dirty, + chunk); + } + chunk->ndirty += run_pages; + arena->ndirty += run_pages; } #ifdef MALLOC_DEBUG /* Set map elements to a bogus value in order to aid error detection. */ @@ -2564,8 +2550,7 @@ arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty) /* Try to coalesce forward. */ key.addr = (void *)((uintptr_t)run + size); - rb_nsearch(extent_node_t, link_ad, extent_ad_comp, - &arena->runs_avail_ad, &key, nodeC); + nodeC = extent_tree_ad_nsearch(&arena->runs_avail_ad, &key); if (nodeC != NULL && nodeC->addr == key.addr) { /* * Coalesce forward. This does not change the position within @@ -2587,8 +2572,7 @@ arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty) } /* Try to coalesce backward. */ - rb_prev(extent_node_t, link_ad, extent_ad_comp, &arena->runs_avail_ad, - nodeB, nodeA); + nodeA = extent_tree_ad_prev(&arena->runs_avail_ad, nodeB); if (nodeA != NULL && (void *)((uintptr_t)nodeA->addr + nodeA->size) == (void *)run) { /* @@ -2681,7 +2665,7 @@ arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin) unsigned i, remainder; /* Look for a usable run. */ - rb_first(arena_run_t, link, &bin->runs, run); + run = arena_run_tree_first(&bin->runs); if (run != NULL) { /* run is guaranteed to have available space. */ arena_run_tree_remove(&bin->runs, run); @@ -3053,8 +3037,7 @@ arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size) * does not change. */ key.addr = ret; - rb_search(extent_node_t, link_ad, extent_ad_comp, - &arena->runs_alloced_ad, &key, node); + node = extent_tree_ad_search(&arena->runs_alloced_ad, &key); assert(node != NULL); arena_run_trim_tail(arena, chunk, node, ret, alloc_size, size, @@ -3067,8 +3050,7 @@ arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size) * does not change. */ key.addr = ret; - rb_search(extent_node_t, link_ad, extent_ad_comp, - &arena->runs_alloced_ad, &key, node); + node = extent_tree_ad_search(&arena->runs_alloced_ad, &key); assert(node != NULL); leadsize = alignment - offset; @@ -3228,8 +3210,7 @@ arena_salloc(const void *ptr) arena = chunk->arena; malloc_spin_lock(&arena->lock); key.addr = (void *)ptr; - rb_search(extent_node_t, link_ad, extent_ad_comp, - &arena->runs_alloced_ad, &key, node); + node = extent_tree_ad_search(&arena->runs_alloced_ad, &key); assert(node != NULL); ret = node->size; malloc_spin_unlock(&arena->lock); @@ -3261,8 +3242,7 @@ isalloc(const void *ptr) /* Extract from tree of huge allocations. */ key.addr = __DECONST(void *, ptr); - rb_search(extent_node_t, link_ad, extent_ad_comp, &huge, &key, - node); + node = extent_tree_ad_search(&huge, &key); assert(node != NULL); ret = node->size; @@ -3350,8 +3330,7 @@ arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr) size_t size; key.addr = ptr; - rb_search(extent_node_t, link_ad, extent_ad_comp, - &arena->runs_alloced_ad, &key, node); + node = extent_tree_ad_search(&arena->runs_alloced_ad, &key); assert(node != NULL); size = node->size; #ifdef MALLOC_STATS @@ -3427,8 +3406,7 @@ arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr, #else malloc_spin_lock(&arena->lock); #endif - rb_search(extent_node_t, link_ad, extent_ad_comp, - &arena->runs_alloced_ad, &key, node); + node = extent_tree_ad_search(&arena->runs_alloced_ad, &key); assert(node != NULL); arena_run_trim_tail(arena, chunk, node, (arena_run_t *)ptr, oldsize, size, true); @@ -3452,8 +3430,7 @@ arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr, #else malloc_spin_lock(&arena->lock); #endif - rb_search(extent_node_t, link_ad, extent_ad_comp, &arena->runs_avail_ad, - &key, nodeC); + nodeC = extent_tree_ad_search(&arena->runs_avail_ad, &key); if (nodeC != NULL && oldsize + nodeC->size >= size) { extent_node_t *nodeA, *nodeB; @@ -3468,13 +3445,11 @@ arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr, oldsize, false, false); key.addr = ptr; - rb_search(extent_node_t, link_ad, extent_ad_comp, - &arena->runs_alloced_ad, &key, nodeA); + nodeA = extent_tree_ad_search(&arena->runs_alloced_ad, &key); assert(nodeA != NULL); key.addr = (void *)((uintptr_t)ptr + oldsize); - rb_search(extent_node_t, link_ad, extent_ad_comp, - &arena->runs_alloced_ad, &key, nodeB); + nodeB = extent_tree_ad_search(&arena->runs_alloced_ad, &key); assert(nodeB != NULL); nodeA->size += nodeB->size; @@ -3619,14 +3594,15 @@ arena_new(arena_t *arena) #endif /* Initialize chunks. */ - rb_tree_new(arena_chunk_t, link, &arena->chunks); + arena_chunk_tree_all_new(&arena->chunks_all); + arena_chunk_tree_dirty_new(&arena->chunks_dirty); arena->spare = NULL; arena->ndirty = 0; - rb_tree_new(extent_node_t, link_szad, &arena->runs_avail_szad); - rb_tree_new(extent_node_t, link_ad, &arena->runs_avail_ad); - rb_tree_new(extent_node_t, link_ad, &arena->runs_alloced_ad); + extent_tree_szad_new(&arena->runs_avail_szad); + extent_tree_ad_new(&arena->runs_avail_ad); + extent_tree_ad_new(&arena->runs_alloced_ad); #ifdef MALLOC_BALANCE arena->contention = 0; @@ -3639,7 +3615,7 @@ arena_new(arena_t *arena) for (i = 0; i < ntbins; i++) { bin = &arena->bins[i]; bin->runcur = NULL; - rb_tree_new(arena_run_t, link, &bin->runs); + arena_run_tree_new(&bin->runs); bin->reg_size = (1U << (TINY_MIN_2POW + i)); @@ -3654,7 +3630,7 @@ arena_new(arena_t *arena) for (; i < ntbins + nqbins; i++) { bin = &arena->bins[i]; bin->runcur = NULL; - rb_tree_new(arena_run_t, link, &bin->runs); + arena_run_tree_new(&bin->runs); bin->reg_size = quantum * (i - ntbins + 1); @@ -3670,7 +3646,7 @@ arena_new(arena_t *arena) for (; i < ntbins + nqbins + nsbins; i++) { bin = &arena->bins[i]; bin->runcur = NULL; - rb_tree_new(arena_run_t, link, &bin->runs); + arena_run_tree_new(&bin->runs); bin->reg_size = (small_max << (i - (ntbins + nqbins) + 1)); @@ -3896,7 +3872,7 @@ huge_dalloc(void *ptr) /* Extract from tree of huge allocations. */ key.addr = ptr; - rb_search(extent_node_t, link_ad, extent_ad_comp, &huge, &key, node); + node = extent_tree_ad_search(&huge, &key); assert(node != NULL); assert(node->addr == ptr); extent_tree_ad_remove(&huge, node); @@ -4396,14 +4372,14 @@ MALLOC_OUT: /* Initialize chunks data. */ malloc_mutex_init(&huge_mtx); - rb_tree_new(extent_node_t, link_ad, &huge); + extent_tree_ad_new(&huge); #ifdef MALLOC_DSS malloc_mutex_init(&dss_mtx); dss_base = sbrk(0); dss_prev = dss_base; dss_max = dss_base; - rb_tree_new(extent_node_t, link_szad, &dss_chunks_szad); - rb_tree_new(extent_node_t, link_ad, &dss_chunks_ad); + extent_tree_szad_new(&dss_chunks_szad); + extent_tree_ad_new(&dss_chunks_ad); #endif #ifdef MALLOC_STATS huge_nmalloc = 0; |
