Meta Alloc: Implement flushing to vacancy-list.

1 files changed, 83 insertions, 37 deletions

diff --git a/src/zisp/gc/meta_alloc.zig b/src/zisp/gc/meta_alloc.zig
index f8c7e28..f8b9e92 100644
--- a/src/zisp/gc/meta_alloc.zig
+++ b/src/zisp/gc/meta_alloc.zig
@@ -57,14 +57,20 @@
 //
 // For each size class, there's a global vacancy-list, whose entries store
 // information about large contiguous segments of memory that are below the
-// watermark yet completely vacant.  Currently, the only purpose of this is
-// recording the region of memory that a thread had reserved by bumping the
-// global watermark, when the thread is terminated.
+// watermark yet completely vacant and need not be backed by physical memory.
 //
-// We could instead slice such regions into slots, and push them onto the size
-// class's global free-list, but that would be disadvantageous since, these
-// memory regions are untouched and thus not yet backed by physical memory;
-// keeping them stored away for as long as possible is best.
+// Currently, the only purpose of this is recording the region of memory a
+// thread had reserved by bumping the global watermark, when that thread is
+// terminated.  We only do this if the remaining reserved memory spans over
+// multiple pages of memory, since in that case it would need faulting in if
+// given out to application code.  The free-list represents slots that were
+// already given out and then freed, meaning they were probably faulted in
+// already when the application wrote data into them.
+//
+// In the future, we may also implement a method of finding contiguous slots
+// within the free-list that together span across pages, informing the kernel
+// about the fact that it's not needed right now, and recording it within the
+// vacancy-list.
 //
 // == Monomorphization (or lack thereof) over size class values ==
 //
@@ -460,10 +466,11 @@ fn free_into_fl(
     }
 }
 
-/// For every size class: Flushes this thread's free slot cache into the global
-/// free-list, and splits remaining reserved memory into slots which are also
-/// pushed onto the global free-list.  It's crucial for threads to call this
-/// function before terminating, or else memory is leaked.
+/// For every size class: Flushes the calling thread's free slot cache into the
+/// global free-list, and remaining reserved memory into the vacancy-list; some
+/// may be turned into slots in the free-list instead if the reserved memory is
+/// not worth creating a vacancy-list entry for.  A thread that intends to exit
+/// must call this function before doing so, or else memory may be leaked.
 export fn flush_thread_reserves() void {
     var sci: u8 = 0;
     var slot_len: UnitIdx = SIZES[0] / @sizeOf(Unit);
@@ -474,36 +481,75 @@ export fn flush_thread_reserves() void {
         const info = &slab_infos[sci];
         const tl = &tl_slab_infos[sci];
         const slab: *Slab = &slabs[sci];
+
+        // Just a rough check, assuming 4 KiB pages: If wm_hi - wm_lo >= 8 KiB,
+        // it means there's a minimum of one untouched page in between.
+        if (tl.wm_hi - tl.wm_lo > 8192 / @sizeOf(Unit)) {
+            flush_to_vl(info, tl, slab);
+        }
+
         const fsc_lim = maxFscCountForSizeClassIndex(sci);
         const flush_max = fsc_lim / 2;
 
-        // TODO: Create vacancy-list entries instead!
-
-        // We could first flush the current fsc and then move on to splitting
-        // reserved memory, but this could result in an "undersized" chunk from
-        // the current fsc and then a second undersized chunk when we reach the
-        // end of reserved memory.  A simple improvement is to do it this way
-        // around instead:
-
-        // Add remaining reserved memory to fsc in a loop, flushing every time
-        // we hit the fsc limit.
-        while (tl.wm_lo < tl.wm_hi) : (tl.wm_lo += slot_len) {
-            const idx = tl.wm_lo;
-            const ptr = slab[idx..].ptr;
-            if (tl.fsc_count == fsc_lim) {
-                free_into_fl(info, tl, ptr, idx, flush_max);
-            } else {
-                tl.fsc[tl.fsc_count] = idx;
-                tl.fsc_count += 1;
-            }
-        }
+        flush_to_fl(info, tl, slab, slot_len, fsc_lim, flush_max);
+    }
+}
+
+fn flush_to_vl(info: *SlabInfo, tl: *TlSlabInfo, slab: *Slab) void {
+    const idx = tl.wm_lo;
+    const ptr = slab[idx..].ptr;
+    const arr: [*]UnitIdx = @ptrCast(@alignCast(ptr));
 
-        // Now flush the rest, in two iterations if necessary.
-        while (tl.fsc_count != 0) {
-            tl.fsc_count -= 1;
-            const idx = tl.fsc[tl.fsc_count];
-            const ptr = slab[idx..].ptr;
-            free_into_fl(info, tl, ptr, idx, @min(flush_max, tl.fsc_count));
+    arr[1] = tl.wm_hi;
+
+    var vl_head = @atomicLoad(VlHead, &info.vacancy_list, .acquire);
+    while (true) : (std.atomic.spinLoopHint()) {
+        arr[0] = vl_head.idx;
+        vl_head = @cmpxchgWeak(
+            VlHead,
+            &info.vacancy_list,
+            vl_head,
+            .{ .aba = vl_head.aba +% 1, .idx = idx },
+            .release,
+            .acquire,
+        ) orelse break;
+    }
+
+    tl.wm_lo = tl.wm_hi;
+}
+
+fn flush_to_fl(
+    info: *SlabInfo,
+    tl: *TlSlabInfo,
+    slab: *Slab,
+    slot_len: UnitIdx,
+    fsc_lim: UnitIdx,
+    flush_max: UnitIdx,
+) void {
+    // We could first flush the current fsc and then move on to splitting
+    // reserved memory, but this could result in an "undersized" chunk from
+    // the current fsc and then a second undersized chunk when we reach the
+    // end of reserved memory.  A simple improvement is to do it this way
+    // around instead:
+
+    // Add remaining reserved memory to fsc in a loop, flushing every time
+    // we hit the fsc limit.
+    while (tl.wm_lo < tl.wm_hi) : (tl.wm_lo += slot_len) {
+        const idx = tl.wm_lo;
+        const ptr = slab[idx..].ptr;
+        if (tl.fsc_count == fsc_lim) {
+            free_into_fl(info, tl, ptr, idx, flush_max);
+        } else {
+            tl.fsc[tl.fsc_count] = idx;
+            tl.fsc_count += 1;
         }
     }
+
+    // Now flush the rest, in two iterations if necessary.
+    while (tl.fsc_count != 0) {
+        tl.fsc_count -= 1;
+        const idx = tl.fsc[tl.fsc_count];
+        const ptr = slab[idx..].ptr;
+        free_into_fl(info, tl, ptr, idx, @min(flush_max, tl.fsc_count));
+    }
 }