Meta Alloc improvements.

1 files changed, 103 insertions, 98 deletions

diff --git a/src/zisp/gc/meta_alloc.zig b/src/zisp/gc/meta_alloc.zig
index 5e58b7b..8e22abe 100644
--- a/src/zisp/gc/meta_alloc.zig
+++ b/src/zisp/gc/meta_alloc.zig
@@ -1,8 +1,8 @@
 //
 // = Meta Allocator =
 //
-// Please read the full documentation of the allocation strategy to understand
-// what's going on here at a high level: /doc/0/A-meta_alloc.html
+// Read the full documentation of the allocation strategy to understand what's
+// going on here at a high level: Chapter 0, Appendix A
 //
 // That said, a few quick implementation notes follow.
 //
@@ -36,8 +36,8 @@
 //     {
 //       next_head_idx:   u32,
 //       extra_idx_count: u32,
-//       pad_to_64_bytes: [7]u64,
-//       extra_idx_array: [32]u32,
+//       pad_to_64_bytes: [15]u32,
+//       extra_idx_array: [16]u32,
 //     }
 //
 // So, it's not a typical free-list where each node simply points to the next
@@ -64,11 +64,26 @@
 
 const std = @import("std");
 
+/// The units of memory in which slabs are addressed.
+const Unit = u64;
+
+/// Integer that can hold a slab/unit index, plus one overflow bit.
+const UnitIdx = u32;
+
+/// Length of each slab, as in Unit count.
+const SLAB_LEN: u32 = 1 << 31;
+
+/// A slab of memory.
+const Slab = [SLAB_LEN]Unit;
+
+/// A pointer to a slot of allocated memory; N units depenging on size class.
+const SlotPtr = [*]Unit;
+
 /// Size classes.
-const SIZES: [16]comptime_int = .{
+const SIZES: [16]usize = .{
     // Important: Ensure the smallest size class is inherently immune to false
-    // sharing, and no smaller than: 64 + 4 * ( RESERVE_MAX / 2 ) many bytes.
-    // That's 192 bytes assuming RESERVE_MAX = 64 (see below).
+    // sharing, and no smaller than: 64 + @sizeOf(UnitIdx) * ( FSC_MAX / 2 ).
+    // That's 128 bytes assuming FSC_MAX = 32 (see below).
     256,
     512,
     1024,
@@ -87,34 +102,24 @@ const SIZES: [16]comptime_int = .{
     1024 * 1024 * 8,
 };
 
-/// Gets the index [0,15] of a size class, from the size value, returning a
+/// Gets the index 0 to 15 of a size class, from the size value, returning a
 /// value greater than 15 if the size is beyond the largest size class.
 inline fn getSizeClassIndex(size: usize) u8 {
     // Can't handle size that isn't power of two or below smallest size class.
-    std.debug.assert(@popCount(size) == 1);
-    std.debug.assert(size >= SIZES[0]);
+    if (@popCount(size) != 1) @panic("Only powers of two supported.");
+    if (size < SIZES[0]) @panic("Can't alloc below smallest size.");
 
-    const min: usize = SIZES[0];
-    return @ctz(size >> @ctz(min));
+    return @ctz(size >> @ctz(SIZES[0]));
 }
 
-/// The length of each slab in 8-byte units.
-const SLAB_LEN: u32 = 0x8000_0000;
-
-// For convenience:
-const Unit = u64;
-const SlotPtr = [*]Unit;
-const Slab = [SLAB_LEN]Unit;
-const Slabs = [SIZES.len]Slab;
-
 /// Pointer to start of all 16 slabs as a contiguous vmem block.
-var slabs: *Slabs = undefined;
+var slabs: *[SIZES.len]Slab = undefined;
 
 /// Free-list head pointer with ABA counter.
 const FlHead = packed struct(u64) {
     // Putting aba first leads to slightly better codegen.
     aba: u32,
-    idx: u32,
+    idx: UnitIdx,
 };
 
 /// Global shared metadata per slab / size class.
@@ -125,40 +130,45 @@ const SlabInfo = struct {
     /// used to mean NULL, since it's an invalid slab index.
     free_list: FlHead = .{ .aba = 0, .idx = SLAB_LEN },
     /// Global slab watermark: Start address of unused vmem, as 8-byte index.
-    watermark: u32 = 0,
+    watermark: UnitIdx = 0,
 };
 
 /// Global shared metadata per slab / size class.
 var slab_infos: [SIZES.len]SlabInfo = @splat(.{});
 
-/// Maximum number of slots reserved for a thread, both when bumping the global
-/// watermark, and by holding entries in its free slot cache.  Note that this
-/// means the real number of slots currently reserved by each thread may reach
-/// twice this number.  (Minus one, since the global watermark is only bumped
-/// when an allocation is requested, so one slot is used immediately.)
-const RESERVE_MAX = 64;
-
-/// Given a size class index 0 to 15, returns the number of slots that threads
-/// should keep in reserve for that size class.  This starts at RESERVE_MAX for
-/// the smallest class, and is halved every four size classes.  This number is
-/// used both for deciding how much to bump the global watermark of a slab to
-/// reserve memory for a thread, and to determine the maximum count of entries
-/// stored in the thread's free slot cache for that size class.
+/// Maximum number of slots reserved by a thread when bumping a slab watermark.
+/// Halved after every two size classes, so make sure it's >= 128.
+const RESERVE_MAX: u32 = 512;
+
+/// Maximum number of free slot cache entries before half of them are flushed.
+/// Halved after every four size classes, so make sure it's >= 8.
+const FSC_MAX: u32 = 32;
+
+/// Given a size class index 0 to 15, returns the number of slots that a thread
+/// should reserve every time it needs to bump the global watermark.  Starts at
+/// RESERVE_MAX and is halved after every two size classes.
 inline fn reserveCountForSizeClassIndex(sci: u8) u32 {
-    return @as(u8, RESERVE_MAX) >> @intCast(sci / 4);
+    return RESERVE_MAX >> @intCast(sci / 2);
+}
+
+/// Given a size class index 0 to 15, returns the maximum number of entries in
+/// the free slot cache of a thread before half of them are flushed.  Starts at
+/// FSC_MAX and is halved after every four size classes.
+inline fn maxFscCountForSizeClassIndex(sci: u8) u32 {
+    return FSC_MAX >> @intCast(sci / 4);
 }
 
 /// Thread-local metadata per slab / size class.
 const TlSlabInfo = struct {
     /// Free slot cache; align to cache line to prevent false sharing and for
     /// possible SIMD related benefits.
-    fc: [RESERVE_MAX]u32 align(std.atomic.cache_line) = @splat(0),
+    fsc: [FSC_MAX]UnitIdx align(std.atomic.cache_line) = @splat(0),
     /// Current count of entries in free slot cache.
-    fc_count: u32 = 0,
+    fsc_count: u32 = 0,
     /// Start point of memory reserved for this thread.
-    wm_lo: u32 = 0,
+    wm_lo: UnitIdx = 0,
     /// End point of memory reserved for this thread.
-    wm_hi: u32 = 0,
+    wm_hi: UnitIdx = 0,
 };
 
 /// Thread-local metadata per slab / size class.
@@ -213,14 +223,14 @@ fn alloc_size_class(sci: u8, size: usize) SlotPtr {
     const slab: *Slab = &slabs[sci];
 
     // Reuse from thread-local free cache.
-    if (tl.fc_count > 0) {
-        tl.fc_count -= 1;
-        const idx = tl.fc[tl.fc_count];
+    if (tl.fsc_count > 0) {
+        tl.fsc_count -= 1;
+        const idx = tl.fsc[tl.fsc_count];
         return slab[idx..].ptr;
     }
 
     // The size in 8-byte slab/watermark units.
-    const wm_units: u32 = @intCast(size / 8);
+    const wm_units: UnitIdx = @intCast(size / 8);
 
     // Use part of the reserved memory for this thread.
     if (tl.wm_lo < tl.wm_hi) {
@@ -243,7 +253,7 @@ fn alloc_from_fl(
     tl: *TlSlabInfo,
 ) ?SlotPtr {
     var ptr: SlotPtr = undefined;
-    var arr: [*]u32 = undefined;
+    var arr: [*]UnitIdx = undefined;
 
     var fl_head = @atomicLoad(FlHead, &info.free_list, .acquire);
     while (true) : (std.atomic.spinLoopHint()) {
@@ -255,7 +265,7 @@ fn alloc_from_fl(
 
         // Load this atomically since it's still globally accessible memory;
         // unordered is fine since we discard it if the following CAS fails.
-        const next_head = @atomicLoad(u32, &arr[0], .unordered);
+        const next_head = @atomicLoad(UnitIdx, &arr[0], .unordered);
 
         fl_head = @cmpxchgWeak(
             FlHead,
@@ -268,11 +278,11 @@ fn alloc_from_fl(
     }
 
     // Now detached from global; no need for atomics anymore.
-    tl.fc_count = arr[1];
+    tl.fsc_count = arr[1];
 
-    // We can safely copy more than needed since we set fc_count.
-    const half_max = RESERVE_MAX / 2;
-    @memcpy(tl.fc[0..half_max], arr[8 .. 8 + half_max]);
+    // We can safely copy more than needed since we set fsc_count.
+    const half_max = FSC_MAX / 2;
+    @memcpy(tl.fsc[0..half_max], arr[16 .. 16 + half_max]);
 
     return ptr;
 }
@@ -282,13 +292,13 @@ fn alloc_fresh(
     slab: *Slab,
     info: *SlabInfo,
     tl: *TlSlabInfo,
-    wm_units: u32,
+    wm_units: UnitIdx,
     res_n: u32,
 ) SlotPtr {
     // Have to use fresh memory from the top of the slab; bump it by a chunk,
     // atomically, to reserve memory for this thread.
     const bump = res_n * wm_units;
-    const old_wm = @atomicRmw(u32, &info.watermark, .Add, bump, .monotonic);
+    const old_wm = @atomicRmw(UnitIdx, &info.watermark, .Add, bump, .monotonic);
     const new_wm = old_wm + bump;
 
     // Check only if the old WM was already overflown; chunk count is such that
@@ -308,43 +318,43 @@ fn free_size_class(sci: u8, ptr: SlotPtr) void {
 
     const tl = &tl_slab_infos[sci];
     const slab: *Slab = &slabs[sci];
-    const idx: u32 = @intCast(ptr - slab);
-    const res_n = reserveCountForSizeClassIndex(sci);
+    const idx: UnitIdx = @intCast(ptr - slab);
+    const fsc_lim = maxFscCountForSizeClassIndex(sci);
 
-    // Still some space in the local free slot cache.
-    if (tl.fc_count != res_n) {
-        tl.fc[tl.fc_count] = idx;
-        tl.fc_count += 1;
+    // Still some space in the local free slot cache?
+    if (tl.fsc_count != fsc_lim) {
+        tl.fsc[tl.fsc_count] = idx;
+        tl.fsc_count += 1;
         return;
     }
 
     // Local cache full; need to flush some to global free-list.
     const info = &slab_infos[sci];
-    free_into_fl(info, tl, ptr, idx, res_n / 2);
+    free_into_fl(info, tl, ptr, idx, fsc_lim / 2);
 }
 
 fn free_into_fl(
     info: *SlabInfo,
     tl: *TlSlabInfo,
     ptr: SlotPtr,
-    idx: u32,
+    idx: UnitIdx,
     n: u32,
 ) void {
     // Note: n = 0 is valid and must work.
-    std.debug.assert(n <= RESERVE_MAX / 2);
+    std.debug.assert(n <= FSC_MAX / 2);
 
-    const arr: [*]u32 = @ptrCast(ptr);
-    const split = tl.fc_count - n;
+    const arr: [*]UnitIdx = @ptrCast(ptr);
+    const split = tl.fsc_count - n;
 
-    tl.fc_count = split;
+    tl.fsc_count = split;
 
     // No need for atomic stores; we own this memory exclusively right now,
     // unless another thread calls free() on the same slot which is a bug.
     arr[1] = n;
 
     // Safe to copy more than needed.
-    const max = RESERVE_MAX / 2;
-    @memcpy(arr[8 .. 8 + max], tl.fc[split .. split + max]);
+    const max = FSC_MAX / 2;
+    @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);
@@ -368,47 +378,42 @@ fn free_into_fl(
 /// this function before terminating, or else memory is leaked.
 export fn flush_thread_reserves() void {
     var sci: u8 = 0;
-    var wm_units: u32 = SIZES[0] / 8;
+    var units: UnitIdx = SIZES[0] / 8;
     while (sci < SIZES.len) : ({
         sci += 1;
-        wm_units *= 2;
+        units *= 2;
     }) {
         const info = &slab_infos[sci];
         const tl = &tl_slab_infos[sci];
         const slab: *Slab = &slabs[sci];
+        const fsc_lim = maxFscCountForSizeClassIndex(sci);
 
-        flush_thread_fc(info, tl, slab);
+        const chunk_max = fsc_lim / 2;
+
+        // Up to two iterations to flush the entire fsc.
+        while (tl.fsc_count != 0) {
+            flush_fsc(info, tl, slab, @min(chunk_max, tl.fsc_count));
+        }
 
         // Now turn slots between wm_lo and wm_hi into free-list entries; most
-        // easily done by writing them into tl.fc and reusing the function to
-        // flush the fc entries.
-        var i: u32 = 0;
-        var wm = tl.wm_lo;
-        while (wm < tl.wm_hi) : ({
-            i += 1;
-            wm += wm_units;
-        }) {
-            tl.fc[i] = wm;
+        // easily done by writing them into tl.fsc and reusing the function to
+        // flush the fsc entries every time chunk_max + 1 is hit.
+        while (tl.wm_lo < tl.wm_hi) : (tl.wm_lo += units) {
+            if (tl.fsc_count > chunk_max) {
+                flush_fsc(info, tl, slab, chunk_max);
+            }
+            tl.fsc[tl.fsc_count] = tl.wm_lo;
+            tl.fsc_count += 1;
+        }
+        if (tl.fsc_count != 0) {
+            flush_fsc(info, tl, slab, tl.fsc_count - 1);
         }
-        tl.fc_count = i;
-        tl.wm_lo = wm;
-        flush_thread_fc(info, tl, slab);
     }
 }
 
-fn flush_thread_fc(info: *SlabInfo, tl: *TlSlabInfo, slab: *Slab) void {
-    // Do in two steps if there's too many for a single free-list node.
-    if (tl.fc_count > RESERVE_MAX / 2) {
-        tl.fc_count -= 1;
-        const idx = tl.fc[tl.fc_count];
-        const ptr: SlotPtr = slab[idx..].ptr;
-        free_into_fl(info, tl, ptr, idx, RESERVE_MAX / 2);
-    }
-    if (tl.fc_count != 0) {
-        tl.fc_count -= 1;
-        const idx = tl.fc[tl.fc_count];
-        const ptr: SlotPtr = slab[idx..].ptr;
-        // Remaining fl_count may be 0; that's fine.
-        free_into_fl(info, tl, ptr, idx, tl.fc_count);
-    }
+fn flush_fsc(info: *SlabInfo, tl: *TlSlabInfo, slab: *Slab, extras: u32) void {
+    tl.fsc_count -= 1;
+    const idx = tl.fsc[tl.fsc_count];
+    const ptr: SlotPtr = slab[idx..].ptr;
+    free_into_fl(info, tl, ptr, idx, extras);
 }