summaryrefslogtreecommitdiffstats
path: root/src/extent.c
Commit message (Collapse)AuthorAgeFilesLines
* Trim before commit in extent_recycle().Jason Evans2017-04-201-2/+6
| | | | | | | | | | This avoids creating clean committed pages as a side effect of aligned allocation. For configurations that decommit memory, purged pages are decommitted, and decommitted extents cannot be coalesced with committed extents. Unless the clean committed pages happen to be selected during allocation, they cause unnecessary permanent extent fragmentation. This resolves #766.
* Header refactoring: move assert.h out of the catch-allDavid Goldblatt2017-04-191-1/+2
|
* Prefer old/low extent_t structures during reuse.Jason Evans2017-04-171-10/+11
| | | | | | Rather than using a LIFO queue to track available extent_t structures, use a red-black tree, and always choose the oldest/lowest available during reuse.
* Track extent structure serial number (esn) in extent_t.Jason Evans2017-04-171-2/+1
| | | | This enables stable sorting of extent_t structures.
* Header refactoring: Split up jemalloc_internal.hDavid Goldblatt2017-04-111-1/+3
| | | | | | | | | | | | | | This is a biggy. jemalloc_internal.h has been doing multiple jobs for a while now: - The source of system-wide definitions. - The catch-all include file. - The module header file for jemalloc.c This commit splits up this functionality. The system-wide definitions responsibility has moved to jemalloc_preamble.h. The catch-all include file is now jemalloc_internal_includes.h. The module headers for jemalloc.c are now in jemalloc_internal_[externs|inlines|types].h, just as they are for the other modules.
* Header refactoring: break out ph.h dependenciesDavid Goldblatt2017-04-111-0/+2
|
* Convert extent module to use C11-style atomcisDavid Goldblatt2017-04-051-8/+10
|
* Transition arena struct fields to C11 atomicsDavid Goldblatt2017-04-051-6/+9
|
* Move arena_slab_data_t's nfree into extent_t's e_bits.Jason Evans2017-03-281-1/+2
| | | | | | | | | | | | | | Compact extent_t to 128 bytes on 64-bit systems by moving arena_slab_data_t's nfree into extent_t's e_bits. Cacheline-align extent_t structures so that they always cross the minimum number of cacheline boundaries. Re-order extent_t fields such that all fields except the slab bitmap (and overlaid heap profiling context pointer) are in the first cacheline. This resolves #461.
* Use a bitmap in extents_t to speed up search.Jason Evans2017-03-251-11/+30
| | | | | Rather than iteratively checking all sufficiently large heaps during search, maintain and use a bitmap in order to skip empty heaps.
* Use first fit layout policy instead of best fit.Jason Evans2017-03-251-12/+42
| | | | | | | | | For extents which do not delay coalescing, use first fit layout policy rather than first-best fit layout policy. This packs extents toward older virtual memory mappings, but at the cost of higher search overhead in the common case. This resolves #711.
* Embed root node into rtree_t.Jason Evans2017-03-231-1/+1
| | | | This avoids one atomic operation per tree access.
* Incorporate szind/slab into rtree leaves.Jason Evans2017-03-231-48/+79
| | | | | | Expand and restructure the rtree API such that all common operations can be achieved with minimal work, regardless of whether the rtree leaf fields are independent versus packed into a single atomic pointer.
* Split rtree_elm_t into rtree_{node,leaf}_elm_t.Jason Evans2017-03-231-35/+39
| | | | | | | | | | | | | | | | This allows leaf elements to differ in size from internal node elements. In principle it would be more correct to use a different type for each level of the tree, but due to implementation details related to atomic operations, we use casts anyway, thus counteracting the value of additional type correctness. Furthermore, such a scheme would require function code generation (via cpp macros), as well as either unwieldy type names for leaves or type aliases, e.g. typedef struct rtree_elm_d2_s rtree_leaf_elm_t; This alternate strategy would be more correct, and with less code duplication, but probably not worth the complexity.
* Convert extent_t's usize to szind.Jason Evans2017-03-231-98/+89
| | | | | | | | Rather than storing usize only for large (and prof-promoted) allocations, store the size class index for allocations that reside within the extent, such that the size class index is valid for all extents that contain extant allocations, and invalid otherwise (mainly to make debugging simpler).
* Implement two-phase decay-based purging.Jason Evans2017-03-151-33/+40
| | | | | | | | | | | | | | | | | | | | Split decay-based purging into two phases, the first of which uses lazy purging to convert dirty pages to "muzzy", and the second of which uses forced purging, decommit, or unmapping to convert pages to clean or destroy them altogether. Not all operating systems support lazy purging, yet the application may provide extent hooks that implement lazy purging, so care must be taken to dynamically omit the first phase when necessary. The mallctl interfaces change as follows: - opt.decay_time --> opt.{dirty,muzzy}_decay_time - arena.<i>.decay_time --> arena.<i>.{dirty,muzzy}_decay_time - arenas.decay_time --> arenas.{dirty,muzzy}_decay_time - stats.arenas.<i>.pdirty --> stats.arenas.<i>.p{dirty,muzzy} - stats.arenas.<i>.{npurge,nmadvise,purged} --> stats.arenas.<i>.{dirty,muzzy}_{npurge,nmadvise,purged} This resolves #521.
* Prefer pages_purge_forced() over memset().Jason Evans2017-03-141-3/+10
| | | | | | This has the dual advantages of allowing for sparsely used large allocations, and relying on the kernel to supply zeroed pages, which tends to be very fast on modern systems.
* Convert extents_t's npages field to use C11-style atomicsDavid Goldblatt2017-03-091-6/+23
| | | | | | In the process, we can do some strength reduction, changing the fetch-adds and fetch-subs to be simple loads followed by stores, since the modifications all occur while holding the mutex.
* Use any-best-fit for cached extent allocation.Jason Evans2017-03-071-5/+8
| | | | | | This simplifies what would be pairing heap operations to the equivalent of LIFO queue operations. This is a complementary optimization in the context of delayed coalescing for cached extents.
* Perform delayed coalescing prior to purging.Jason Evans2017-03-071-38/+113
| | | | | | | | | Rather than purging uncoalesced extents, perform just enough incremental coalescing to purge only fully coalesced extents. In the absence of cached extent reuse, the immediate versus delayed incremental purging algorithms result in the same purge order. This resolves #655.
* Tidy up extent quantization.Jason Evans2017-02-271-21/+5
| | | | | | | Remove obsolete unit test scaffolding for extent quantization. Remove redundant assertions. Add an assertion to extents_first_best_fit_locked() that should help prevent aligned allocation regressions.
* Disable coalescing of cached extents.Jason Evans2017-02-171-21/+35
| | | | | | | | Extent splitting and coalescing is a major component of large allocation overhead, and disabling coalescing of cached extents provides a simple and effective hysteresis mechanism. Once two-phase purging is implemented, it will probably make sense to leave coalescing disabled for the first phase, but coalesce during the second phase.
* Optimize extent coalescing.Jason Evans2017-02-171-20/+23
| | | | | Refactor extent_can_coalesce(), extent_coalesce(), and extent_record() to avoid needlessly repeating extent [de]activation operations.
* Determine rtree levels at compile time.Jason Evans2017-02-091-2/+1
| | | | | | | Rather than dynamically building a table to aid per level computations, define a constant table at compile time. Omit both high and low insignificant bits. Use one to three tree levels, depending on the number of significant bits.
* Fix extent_record().Jason Evans2017-02-071-18/+33
| | | | | | | | | | | | | | Read adjacent rtree elements while holding element locks, since the extents mutex only protects against relevant like-state extent mutation. Fix management of the 'coalesced' loop state variable to merge forward/backward results, rather than overwriting the result of forward coalescing if attempting to coalesce backward. In practice this caused no correctness issues, but could cause extra iterations in rare cases. These regressions were introduced by d27f29b468ae3e9d2b1da4a9880351d76e5a1662 (Disentangle arena and extent locking.).
* Fix a race in extent_grow_retained().Jason Evans2017-02-041-9/+14
| | | | | | | | | | | | | Set extent as active prior to registration so that other threads can't modify it in the absence of locking. This regression was introduced by d27f29b468ae3e9d2b1da4a9880351d76e5a1662 (Disentangle arena and extent locking.), via non-obvious means. Removal of extents_mtx protection during extent_grow_retained() execution opened up the race, but in the presence of that locking, the code was safe. This resolves #599.
* Disentangle arena and extent locking.Jason Evans2017-02-021-251/+367
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Refactor arena and extent locking protocols such that arena and extent locks are never held when calling into the extent_*_wrapper() API. This requires extra care during purging since the arena lock no longer protects the inner purging logic. It also requires extra care to protect extents from being merged with adjacent extents. Convert extent_t's 'active' flag to an enumerated 'state', so that retained extents are explicitly marked as such, rather than depending on ring linkage state. Refactor the extent collections (and their synchronization) for cached and retained extents into extents_t. Incorporate LRU functionality to support purging. Incorporate page count accounting, which replaces arena->ndirty and arena->stats.retained. Assert that no core locks are held when entering any internal [de]allocation functions. This is in addition to existing assertions that no locks are held when entering external [de]allocation functions. Audit and document synchronization protocols for all arena_t fields. This fixes a potential deadlock due to recursive allocation during gdump, in a similar fashion to b49c649bc18fff4bd10a1c8adbaf1f25f6453cb6 (Fix lock order reversal during gdump.), but with a necessarily much broader code impact.
* Synchronize extent_grow_next accesses.Jason Evans2017-02-021-3/+15
| | | | | | This should have been part of 411697adcda2fd75e135cdcdafb95f2bd295dc7f (Use exponential series to size extents.), which introduced extent_grow_next.
* Replace tabs following #define with spaces.Jason Evans2017-01-211-5/+5
| | | | This resolves #564.
* Remove extraneous parens around return arguments.Jason Evans2017-01-211-82/+79
| | | | This resolves #540.
* Update brace style.Jason Evans2017-01-211-183/+192
| | | | | | | Add braces around single-line blocks, and remove line breaks before function-opening braces. This resolves #537.
* Fix --disable-stats support.Jason Evans2017-01-201-3/+5
| | | | | Fix numerous regressions that were exposed by --disable-stats, both in the core library and in the tests.
* Formatting/comment fixes.Jason Evans2017-01-171-1/+0
|
* Remove leading blank lines from function bodies.Jason Evans2017-01-131-28/+0
| | | | This resolves #535.
* Implement arena.<i>.destroy .Jason Evans2017-01-071-5/+16
| | | | | | | Add MALLCTL_ARENAS_DESTROYED for accessing destroyed arena stats as an analogue to MALLCTL_ARENAS_ALL. This resolves #382.
* Implement per arena base allocators.Jason Evans2016-12-271-21/+15
| | | | | | | | | | | | | Add/rename related mallctls: - Add stats.arenas.<i>.base . - Rename stats.arenas.<i>.metadata to stats.arenas.<i>.internal . - Add stats.arenas.<i>.resident . Modify the arenas.extend mallctl to take an optional (extent_hooks_t *) argument so that it is possible for all base allocations to be serviced by the specified extent hooks. This resolves #463.
* Refactor purging and splitting/merging.Jason Evans2016-12-271-25/+109
| | | | | | | | | | | | | | Split purging into lazy and forced variants. Use the forced variant for zeroing dss. Add support for NULL function pointers as an opt-out mechanism for the dalloc, commit, decommit, purge_lazy, purge_forced, split, and merge fields of extent_hooks_t. Add short-circuiting checks in large_ralloc_no_move_{shrink,expand}() so that no attempt is made if splitting/merging is not supported. This resolves #268.
* Use exponential series to size extents.Jason Evans2016-12-271-31/+186
| | | | | | | | | | If virtual memory is retained, allocate extents such that their sizes form an exponentially growing series. This limits the number of disjoint virtual memory ranges so that extent merging can be effective even if multiple arenas' extent allocation requests are highly interleaved. This resolves #462.
* Add extent serial numbers.Jason Evans2016-11-151-17/+11
| | | | | | | | Add extent serial numbers and use them where appropriate as a sort key that is higher priority than address, so that the allocation policy prefers older extents. This resolves #147.
* Rename atomic_*_{uint32,uint64,u}() to atomic_*_{u32,u64,zu}().Jason Evans2016-11-071-6/+6
| | | | This change conforms to naming conventions throughout the codebase.
* Fix/simplify extent_recycle() allocation size computations.Jason Evans2016-11-041-6/+5
| | | | | | | | | | | Do not call s2u() during alloc_size computation, since any necessary ceiling increase is taken care of later by extent_first_best_fit() --> extent_size_quantize_ceil(), and the s2u() call may erroneously cause a higher quantization result. Remove an overly strict overflow check that was added in 4a7852137d8b6598fdb90ea8e1fd3bc8a8b94a3a (Fix extent_recycle()'s cache-oblivious padding support.).
* Fix extent_recycle()'s cache-oblivious padding support.Jason Evans2016-11-041-5/+6
| | | | | | | Add padding *after* computing the size class, so that the optimal size class isn't skipped during search for a usable extent. This regression was caused by b46261d58b449cc4c099ed2384451a2499688f0e (Implement cache-oblivious support for huge size classes.).
* Fix psz/pind edge cases.Jason Evans2016-11-041-11/+10
| | | | | | | | | Add an "over-size" extent heap in which to store extents which exceed the maximum size class (plus cache-oblivious padding, if enabled). Remove psz2ind_clamp() and use psz2ind() instead so that trying to allocate the maximum size class can in principle succeed. In practice, this allows assertions to hold so that OOM errors can be successfully generated.
* Fix extent_alloc_cache[_locked]() to support decommitted allocation.Jason Evans2016-11-041-11/+9
| | | | | | | | | Fix extent_alloc_cache[_locked]() to support decommitted allocation, and use this ability in arena_stash_dirty(), so that decommitted extents are not needlessly committed during purging. In practice this does not happen on any currently supported systems, because both extent merging and decommit must be implemented; all supported systems implement one xor the other.
* Fix extent_rtree acquire() to release element on error.Jason Evans2016-10-311-1/+3
| | | | This resolves #480.
* Make dss operations lockless.Jason Evans2016-10-131-38/+10
| | | | | | | | | | | | | | Rather than protecting dss operations with a mutex, use atomic operations. This has negligible impact on synchronization overhead during typical dss allocation, but is a substantial improvement for extent_in_dss() and the newly added extent_dss_mergeable(), which can be called multiple times during extent deallocations. This change also has the advantage of avoiding tsd in deallocation paths associated with purging, which resolves potential deadlocks during thread exit due to attempted tsd resurrection. This resolves #425.
* Remove a size class assertion from extent_size_quantize_floor().Jason Evans2016-10-031-1/+0
| | | | | Extent coalescence can result in legitimate calls to extent_size_quantize_floor() with size larger than LARGE_MAXCLASS.
* Fix size class overflow bugs.Jason Evans2016-10-031-3/+7
| | | | | | | Avoid calling s2u() on raw extent sizes in extent_recycle(). Clamp psz2ind() (implemented as psz2ind_clamp()) when inserting/removing into/from size-segregated extent heaps.
* Add various mutex ownership assertions.Jason Evans2016-09-231-6/+10
|
* Add new_addr validation in extent_recycle().Jason Evans2016-09-231-6/+28
|
generated by cgit v0.12 at 2025-03-27 21:13:32 (GMT)