u3: adds new, page-oriented memory allocator#812
Merged
Conversation
Some stupid linux header was deprecated.
Based on the work in urbit/urbit#4675 with some upgrades. The structured exception handling code in the original is crazy. It was originally done because libsigsegv installs a top level structured exception handler which means that every time we fault we end up unwinding a potentially very deep stack. We (and most likely libsigsegv too) can instead install a [vectored exception handler ](https://learn.microsoft.com/en-us/windows/win32/debug/vectored-exception-handling) that functions exactly as we want without unwinding the stack. We still have cross-compilation from any of our supported targets to any of our supported targets. Current known limitations: Demand paging does not work. The spin hint does not work. JSON tracing does not work. The jump buffer in the road struct needs to be 16 byte aligned on windows, we'll fix when merging @joemfb:s allocator work. There are some strange padding zeroes at the end of south.bin breaking checkpoint version negotiation, fix same as above.
staging PR for accumulating and reviewing migrations, more to come.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This PR replaces the u3 allocator with a new, page-aware design (cribbed directly from phkmalloc). Opened as a draft for now pending a migration from the old allocator/snapshot.
The primary design consideration of phkmalloc is to minimize the number of pages that it touches. This aligns perfectly with the constraints of a persistent allocation arena, minimizing write-amplification when updating a snapshot. phkmalloc further ensures natural alignment at every allocation size up to the page size (all powers of two), and page alignment after that. These are stronger alignment guarantees than we require in any scenario, so all alignment is now implicit (other than the page-alignment of a new road), and all heap objects are aligned to at least 16 bytes (allowing an additional bit of pointer compression). All allocation metadata and freelists are stored out-of-band; allocated "as if" with the allocator itself. This shrinks our cells from 24 to 16 bytes and ensures that free pages are actually free, allowing us to store more data and further reducing churn in snapshot updates. Rounding small allocations up to power-of-two sizes reduces the overhead of searching free lists, allowing us to removing a performance hack from the old allocator that had significantly increased fragmentation. In practice, persistent state and snapshot have been observed to be roughly 20% smaller with this allocator.
The absence of extra space for inline metadata in our allocations (no more "boxes") dictates redesigns of our garbage collection mechanisms. Reference counts are now in "userspace": an ad-hoc part of the application data inside an allocation (conventionally, the first word) instead of allocator-level metadata. So our mark and sweep collector (actually two collectors, switched by
u3o_debug_ram) requires that extra space be allocated on the side to track mark bits or recalculated refcounts. This has the advantageous effect that|massno longer dirties clean, persisted pages on the home road, making it much faster and cheaper (and therefore practical to run automatically). Similarly, our mark/compact collector (|pack) requires out-of-band relocation state. To minimize overhead, those relocations are not stored, but calculated from compact bitmaps in a design cribbed from the Clozure Common Lisp compiler by way of Factor.