diff options
| -rw-r--r-- | doc/0/A-meta_alloc.md | 79 | ||||
| -rw-r--r-- | src/zisp/gc/meta_alloc.zig | 30 |
2 files changed, 74 insertions, 35 deletions
diff --git a/doc/0/A-meta_alloc.md b/doc/0/A-meta_alloc.md index 51f3ff7..3ac005a 100644 --- a/doc/0/A-meta_alloc.md +++ b/doc/0/A-meta_alloc.md @@ -29,6 +29,7 @@ This is not directly related to garbage collection, though a GC may use Meta Alloc to manage auxiliary metadata, or even for the actual heap memory returned to application code; it's up to the GC. + ## Overview The entire architecture is built on three pillars: @@ -48,6 +49,7 @@ in advance and letting the operating system automatically handle the actual mapping to physical memory provides an immense simplification of the allocator implementation. + ## Slabs and Size Classes A single global pointer in static memory is initialized to point to @@ -121,6 +123,7 @@ If a size greater than the largest size class is requested, then Meta Alloc simply forwards this to an `mmap()` call, acting as a mere thin wrapper around mmap, calling `munmap()` on `free()`. + ## Global metadata The static array `slab_infos` holds `N_SLABS` many structures which @@ -130,11 +133,14 @@ record just two pieces of information associated with each Slab: * The head of the global, shared *Free-List* for this Slab. +* The head of the global, shared *Vacancy-List* for this Slab. + Expressed in pseudo-code: struct SlabInfo { watermark: Integer, free_list: ListHead, + vacancy_list: ListHead, } var slab_infos: [N_SLABS]SlabInfo; @@ -152,7 +158,8 @@ In other words, it may be implemented as a Treiber stack: The initial value of the `free_list` head is of course some sort of null indicator so we can know it's empty. -Detailed explanations of the Watermark and Free-List follow. +Detailed explanations of the Watermark, Free-List, and Vacancy-List +follow. ### Slab Watermark @@ -223,6 +230,38 @@ using up to 512-bit SIMD instructions on modern processors. Why we would need to bulk-transfer 16 Index values will be explained later, as we look into thread-local cache metadata. +### Vacancy-List + +For reasons we will go into later, there may be memory regions below +the Watermark of a Slab that are completely vacant, span across pages +of memory, and need not be backed by physical memory. + +Vacant, in this case, means no *meaningful* data is held; either the +memory has never been touched and is all zeros, or application code +has given it back for freeing and we decided not even to store any +meta-data in it, so we don't care if it's zeroed out. + +Such memory regions are recorded in the Vacancy-List, which has the +following simple node structure: + + { + next_vacancy_idx: Index, + vacancy_end_idx: Index, + } + +These nodes themselves occupy the beginning of each such vacancy, +which means that the real vacancy only begins after two Indexes. +Starting from the next page boundary after that, writing any data +could lead to a page fault. + +Slots in the Free-List, in contrast, are likely to have physical +memory backing them, which is why they're given out first. + +The Vacancy-List is the penultimate choice to satisfy an allocation +request, before increasing the Watermark and giving out completely +fresh memory. + + ## Per-thread metadata We don't want to burden code using Meta Alloc with concerns about @@ -261,6 +300,10 @@ we need to check the global Watermark again (it may have been bumped by another thread) to set our new Low, and bump the global, to which we set our new High. +When Meta Alloc decides to reach for Vacancy-List entries, it does +that by setting the calling thread's Low and High to the start and +ending point of the vacancy. + ### Free Slot Cache When `free()` is called in a thread, it checks whether there's still @@ -290,14 +333,13 @@ Slots as a reserve. For this reason, although the Free Slot Cache array has a static maximum size, larger size classes have a lower maximum element count that they enforce. -Note: While the bumping of the global Watermark happens in fairly -massive chunks for the smaller size classes, the Free Slot Cache -instead has fairly small upper limits throughout all size classes. -This is because reserving a big "hole" in a Slab is totally benign, -since the operating system won't map any physical memory to it until -it's actually used; whereas freed Slots already have physical memory -backing them, making it important not to let too many of them linger -around in some thread's local cache without being reused. +Note: While the bumping of the global Watermark happens in massive +chunks for the smaller size classes, the Free Slot Cache has small +upper limits throughout all size classes. This is because, while +reserving a big "hole" in a Slab is benign (since physical memory +won't be mapped until pages are touched), freed Slots have physical +memory backing them already, making it important not to keep around +too many of them in some thread's local cache without being reused. ### Thread destruction @@ -310,16 +352,19 @@ without any other subsequent calls to `alloc()` or `free()` before exiting. This immediately transfers the thread's Free Slot Cache entries into -the global Free-List, in multiple chunks if necessary, then creates -Free-List entries (also in chunks) for any leftover memory that was -reserved from bumping the global Watermark by a chunk. +the global Free-List, in multiple chunks if necessary; and creates a +Vacancy-List entry for leftover reserved memory (from the bumping of +the global Watermark) if the amount of reserved memory spans across +multiple pages. Otherwise, it's simply split into Slots and also +pushed onto the Free-List. ## Releasing vmem Though not currently implemented, Meta Alloc may be able to release -virtual memory back to the operating system via strategies explained -in the following Zisp Note: - -* [Releasing virtual memory](../../notes/260817-release.html) +virtual memory back to the operating system by detecting that there +are Free-List entries corresponding to contiguous memory regions +spanning across pages of memory. -End. +In this case, these Free-List entries may be removed, a Vacancy-List +entry created instead, and one or more pages of memory given back to +the operating system. diff --git a/src/zisp/gc/meta_alloc.zig b/src/zisp/gc/meta_alloc.zig index f8b9e92..4dec92d 100644 --- a/src/zisp/gc/meta_alloc.zig +++ b/src/zisp/gc/meta_alloc.zig @@ -138,29 +138,23 @@ inline fn getSizeClassIndex(size: usize) u8 { /// Pointer to start of all slabs as a contiguous array. var slabs: *[SIZES.len]Slab = undefined; -/// Free-list head pointer with ABA counter. -const FlHead = packed struct(u64) { +/// Linked-list head pointer with ABA counter. +const ListHead = packed struct(u64) { // Putting aba first leads to slightly better codegen. aba: UnitIdx, idx: UnitIdx, }; -/// Vacancy-list head pointer with ABA counter. -const VlHead = packed struct(u64) { - aba: UnitIdx, - idx: UnitIdx, -}; - /// Global shared metadata per slab / size class. const SlabInfo = struct { /// Force cache line alignment to prevent false sharing. _: void align(std.atomic.cache_line) = {}, /// Head of shared free-list for the size class; index value SLAB_LEN is /// used to mean NULL, since it's an invalid slab index. - free_list: FlHead = .{ .aba = 0, .idx = SLAB_LEN }, + free_list: ListHead = .{ .aba = 0, .idx = SLAB_LEN }, /// Head of shared vacancy-list for the size class; index value SLAB_LEN /// used to mean NULL, since it's an invalid slab index. - vacancy_list: VlHead = .{ .aba = 0, .idx = SLAB_LEN }, + vacancy_list: ListHead = .{ .aba = 0, .idx = SLAB_LEN }, /// Global slab watermark: Start address of unused vmem, as 8-byte index. watermark: UnitIdx = 0, }; @@ -311,7 +305,7 @@ fn alloc_from_fl( var ptr: SlotPtr = undefined; var arr: [*]UnitIdx = undefined; - var fl_head = @atomicLoad(FlHead, &info.free_list, .acquire); + var fl_head = @atomicLoad(ListHead, &info.free_list, .acquire); while (true) : (std.atomic.spinLoopHint()) { // Checking for >= SLAB_LEN is optimal; it'll just test the sign bit. if (fl_head.idx >= SLAB_LEN) return null; @@ -324,7 +318,7 @@ fn alloc_from_fl( const next_head = @atomicLoad(UnitIdx, &arr[0], .unordered); fl_head = @cmpxchgWeak( - FlHead, + ListHead, &info.free_list, fl_head, .{ .aba = fl_head.aba +% 1, .idx = next_head }, @@ -355,7 +349,7 @@ fn alloc_from_vl( var ptr: SlotPtr = undefined; var arr: [*]UnitIdx = undefined; - var vl_head = @atomicLoad(VlHead, &info.vacancy_list, .acquire); + var vl_head = @atomicLoad(ListHead, &info.vacancy_list, .acquire); while (true) : (std.atomic.spinLoopHint()) { if (vl_head.idx >= SLAB_LEN) return null; @@ -366,7 +360,7 @@ fn alloc_from_vl( const next_head = @atomicLoad(UnitIdx, &arr[0], .unordered); vl_head = @cmpxchgWeak( - VlHead, + ListHead, &info.vacancy_list, vl_head, .{ .aba = vl_head.aba +% 1, .idx = next_head }, @@ -451,12 +445,12 @@ fn free_into_fl( @memcpy(arr[16 .. 16 + max], tl.fsc[split .. split + max]); // Now atomically announce the new free-list head to global visibility. - var fl_head = @atomicLoad(FlHead, &info.free_list, .acquire); + var fl_head = @atomicLoad(ListHead, &info.free_list, .acquire); while (true) : (std.atomic.spinLoopHint()) { // Still owned exclusively; no need for atomic store. arr[0] = fl_head.idx; fl_head = @cmpxchgWeak( - FlHead, + ListHead, &info.free_list, fl_head, .{ .aba = fl_head.aba +% 1, .idx = idx }, @@ -502,11 +496,11 @@ fn flush_to_vl(info: *SlabInfo, tl: *TlSlabInfo, slab: *Slab) void { arr[1] = tl.wm_hi; - var vl_head = @atomicLoad(VlHead, &info.vacancy_list, .acquire); + var vl_head = @atomicLoad(ListHead, &info.vacancy_list, .acquire); while (true) : (std.atomic.spinLoopHint()) { arr[0] = vl_head.idx; vl_head = @cmpxchgWeak( - VlHead, + ListHead, &info.vacancy_list, vl_head, .{ .aba = vl_head.aba +% 1, .idx = idx }, |