Meta alloc improvement (half complete).

2 files changed, 67 insertions, 1 deletions

diff --git a/MetaAlloc.ods b/MetaAlloc.ods
index 4da4cab..ebd1d39 100644
--- a/MetaAlloc.ods
+++ b/MetaAlloc.ods
diff --git a/src/zisp/gc/meta_alloc.zig b/src/zisp/gc/meta_alloc.zig
index 1fbe1ab..f8c7e28 100644
--- a/src/zisp/gc/meta_alloc.zig
+++ b/src/zisp/gc/meta_alloc.zig
@@ -53,6 +53,19 @@
 // cases.  We fill/empty half of this array from/to the global free-list when
 // it's empty/full; this is how the chunks in the global free-list are formed.
 //
+// == Vacancy-lists ==
+//
+// 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.
+//
+// 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.
+//
 // == Monomorphization (or lack thereof) over size class values ==
 //
 // Given that we have a small-ish static number of size classes, we could make
@@ -126,6 +139,12 @@ const FlHead = packed struct(u64) {
     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.
@@ -133,6 +152,9 @@ const SlabInfo = struct {
     /// 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 },
+    /// 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 },
     /// Global slab watermark: Start address of unused vmem, as 8-byte index.
     watermark: UnitIdx = 0,
 };
@@ -263,10 +285,14 @@ fn alloc_size_class(sci: u8, size: usize) SlotPtr {
         return slab[idx..].ptr;
     }
 
-    // Try to transfer a chunk from the global free-list.
     const info = &slab_infos[sci];
+
+    // Try to transfer a chunk from the global free-list.
     if (alloc_from_fl(slab, info, tl)) |p| return p;
 
+    // Check the vacancy-list.
+    if (alloc_from_vl(slab, info, tl, slot_len)) |p| return p;
+
     const res_n = reserveCountForSizeClassIndex(sci);
     return alloc_fresh(size, slab, info, tl, slot_len, res_n);
 }
@@ -311,6 +337,44 @@ fn alloc_from_fl(
     return ptr;
 }
 
+fn alloc_from_vl(
+    slab: *Slab,
+    info: *SlabInfo,
+    tl: *TlSlabInfo,
+    slot_len: UnitIdx,
+) ?SlotPtr {
+    // This is largely analogous to alloc_from_fl().
+
+    var idx: UnitIdx = undefined;
+    var ptr: SlotPtr = undefined;
+    var arr: [*]UnitIdx = undefined;
+
+    var vl_head = @atomicLoad(VlHead, &info.vacancy_list, .acquire);
+    while (true) : (std.atomic.spinLoopHint()) {
+        if (vl_head.idx >= SLAB_LEN) return null;
+
+        idx = vl_head.idx;
+        ptr = slab[idx..].ptr;
+        arr = @ptrCast(@alignCast(ptr));
+
+        const next_head = @atomicLoad(UnitIdx, &arr[0], .unordered);
+
+        vl_head = @cmpxchgWeak(
+            VlHead,
+            &info.vacancy_list,
+            vl_head,
+            .{ .aba = vl_head.aba +% 1, .idx = next_head },
+            .release,
+            .acquire,
+        ) orelse break;
+    }
+
+    tl.wm_lo = idx + slot_len;
+    tl.wm_hi = arr[1];
+
+    return ptr;
+}
+
 fn alloc_fresh(
     size: usize,
     slab: *Slab,
@@ -413,6 +477,8 @@ export fn flush_thread_reserves() void {
         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