summaryrefslogtreecommitdiffstats
path: root/src/extent.c
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
|
* Protect extents_dirty access with extents_mtx.Jason Evans2016-09-221-38/+78
| | | | This fixes race conditions during purging.
* Fix extent_recycle() to exclude other arenas' extents.Jason Evans2016-09-221-1/+2
| | | | | When attempting to recycle an extent at a specified address, check that the extent belongs to the correct arena.
* Propagate tsdn to default extent hooks.Jason Evans2016-06-071-25/+78
| | | | | | | This avoids bootstrapping issues for configurations that require allocation during tsd initialization. This resolves #390.
* Use extent_commit_wrapper() rather than directly calling commit hook.Jason Evans2016-06-061-3/+2
| | | | | As a side effect this causes the extent's 'committed' flag to be updated.
* Set 'committed' in extent_[de]commit_wrapper().Jason Evans2016-06-061-8/+13
|
* Fix regressions related extent splitting failures.Jason Evans2016-06-061-1/+3
| | | | | | | | | | Fix a fundamental extent_split_wrapper() bug in an error path. Fix extent_recycle() to deregister unsplittable extents before leaking them. Relax xallocx() test assertions so that unsplittable extents don't cause test failures.
* Fix an extent [de]allocation/[de]registration race.Jason Evans2016-06-061-4/+17
| | | | | Deregister extents before deallocation, so that subsequent reallocation/registration doesn't race with deregistration.
* Fix extent_alloc_dss() regressions.Jason Evans2016-06-061-0/+12
| | | | | Page-align the gap, if any, and add/use extent_dalloc_gap(), which registers the gap extent before deallocation.
* Fix gdump triggering regression.Jason Evans2016-06-061-13/+11
| | | | | Now that extents are not multiples of chunksize, it's necessary to track pages rather than chunks.
* Modify extent hook functions to take an (extent_t *) argument.Jason Evans2016-06-061-169/+138
| | | | | | | This facilitates the application accessing its own extent allocator metadata during hook invocations. This resolves #259.
* Add rtree lookup path caching.Jason Evans2016-06-061-23/+42
| | | | | | | | | rtree-based extent lookups remain more expensive than chunk-based run lookups, but with this optimization the fast path slowdown is ~3 CPU cycles per metadata lookup (on Intel Core i7-4980HQ), versus ~11 cycles prior. The path caching speedup tends to degrade gracefully unless allocated memory is spread far apart (as is the case when using a mixture of sbrk() and mmap()).
* Rename most remaining *chunk* APIs to *extent*.Jason Evans2016-06-061-0/+929
|
* s/chunk_lookup/extent_lookup/g, s/chunks_rtree/extents_rtree/gJason Evans2016-06-061-0/+16
|
generated by cgit v0.12 at 2025-04-08 09:36:16 (GMT)