Add meta alloc docs, do code and doc cleanup.

1 files changed, 36 insertions, 31 deletions

diff --git a/src/zisp/gc/meta_alloc.zig b/src/zisp/gc/meta_alloc.zig
index 3138891..5e58b7b 100644
--- a/src/zisp/gc/meta_alloc.zig
+++ b/src/zisp/gc/meta_alloc.zig
@@ -2,7 +2,7 @@
 // = 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-memory.html
+// what's going on here at a high level: /doc/0/A-meta_alloc.html
 //
 // That said, a few quick implementation notes follow.
 //
@@ -90,15 +90,25 @@ const SIZES: [16]comptime_int = .{
 /// Gets the index [0,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 {
-    const min: u32 = SIZES[0];
+    // 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]);
+
+    const min: usize = SIZES[0];
     return @ctz(size >> @ctz(min));
 }
 
 /// 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: *[SIZES.len][SLAB_LEN]u64 = undefined;
+var slabs: *Slabs = undefined;
 
 /// Free-list head pointer with ABA counter.
 const FlHead = packed struct(u64) {
@@ -121,7 +131,11 @@ const SlabInfo = struct {
 /// Global shared metadata per slab / size class.
 var slab_infos: [SIZES.len]SlabInfo = @splat(.{});
 
-/// Maximum number of slots reserved for a thread.
+/// 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
@@ -171,12 +185,6 @@ export fn init() void {
 /// than or equal to the smallest size class.  If it's greater than the largest
 /// size class, this will fall back to an mmap() syscall.
 export fn alloc(size: usize) [*]u8 {
-    // Can't allocate size that isn't power of two.
-    std.debug.assert(@popCount(size) == 1);
-
-    // Can't allocate below smallest size class.
-    std.debug.assert(size >= SIZES[0]);
-
     const sci = getSizeClassIndex(size);
     if (sci < SIZES.len) {
         @branchHint(.likely);
@@ -189,9 +197,6 @@ export fn alloc(size: usize) [*]u8 {
 
 /// Free memory that was returned by alloc().
 export fn free(size: usize, ptr: [*]u8) void {
-    std.debug.assert(@popCount(size) == 1);
-    std.debug.assert(size >= SIZES[0]);
-
     const sci = getSizeClassIndex(size);
     if (sci < SIZES.len) {
         @branchHint(.likely);
@@ -201,17 +206,17 @@ export fn free(size: usize, ptr: [*]u8) void {
     }
 }
 
-fn alloc_size_class(sci: u8, size: usize) [*]u64 {
+fn alloc_size_class(sci: u8, size: usize) SlotPtr {
     std.debug.assert(sci < SIZES.len);
 
     const tl = &tl_slab_infos[sci];
-    const slab: [*]u64 = &slabs[sci];
+    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];
-        return slab[idx..];
+        return slab[idx..].ptr;
     }
 
     // The size in 8-byte slab/watermark units.
@@ -221,7 +226,7 @@ fn alloc_size_class(sci: u8, size: usize) [*]u64 {
     if (tl.wm_lo < tl.wm_hi) {
         const idx = tl.wm_lo;
         tl.wm_lo += wm_units;
-        return slab[idx..];
+        return slab[idx..].ptr;
     }
 
     // Try to transfer a chunk from the global free-list.
@@ -233,11 +238,11 @@ fn alloc_size_class(sci: u8, size: usize) [*]u64 {
 }
 
 fn alloc_from_fl(
-    slab: [*]u64,
+    slab: *Slab,
     info: *SlabInfo,
     tl: *TlSlabInfo,
-) ?[*]u64 {
-    var ptr: [*]u64 = undefined;
+) ?SlotPtr {
+    var ptr: SlotPtr = undefined;
     var arr: [*]u32 = undefined;
 
     var fl_head = @atomicLoad(FlHead, &info.free_list, .acquire);
@@ -245,7 +250,7 @@ fn alloc_from_fl(
         // Checking for >= SLAB_LEN is optimal; it'll just test the sign bit.
         if (fl_head.idx >= SLAB_LEN) return null;
 
-        ptr = slab[fl_head.idx..];
+        ptr = slab[fl_head.idx..].ptr;
         arr = @ptrCast(ptr);
 
         // Load this atomically since it's still globally accessible memory;
@@ -274,12 +279,12 @@ fn alloc_from_fl(
 
 fn alloc_fresh(
     size: usize,
-    slab: [*]u64,
+    slab: *Slab,
     info: *SlabInfo,
     tl: *TlSlabInfo,
     wm_units: u32,
     res_n: u32,
-) [*]u64 {
+) 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;
@@ -295,14 +300,14 @@ fn alloc_fresh(
 
     tl.wm_hi = new_wm;
     tl.wm_lo = old_wm + wm_units;
-    return slab[old_wm..];
+    return slab[old_wm..].ptr;
 }
 
-fn free_size_class(sci: u8, ptr: [*]u64) void {
+fn free_size_class(sci: u8, ptr: SlotPtr) void {
     std.debug.assert(sci < SIZES.len);
 
     const tl = &tl_slab_infos[sci];
-    const slab: [*]u64 = &slabs[sci];
+    const slab: *Slab = &slabs[sci];
     const idx: u32 = @intCast(ptr - slab);
     const res_n = reserveCountForSizeClassIndex(sci);
 
@@ -321,7 +326,7 @@ fn free_size_class(sci: u8, ptr: [*]u64) void {
 fn free_into_fl(
     info: *SlabInfo,
     tl: *TlSlabInfo,
-    ptr: [*]u64,
+    ptr: SlotPtr,
     idx: u32,
     n: u32,
 ) void {
@@ -370,7 +375,7 @@ export fn flush_thread_reserves() void {
     }) {
         const info = &slab_infos[sci];
         const tl = &tl_slab_infos[sci];
-        const slab: [*]u64 = &slabs[sci];
+        const slab: *Slab = &slabs[sci];
 
         flush_thread_fc(info, tl, slab);
 
@@ -391,18 +396,18 @@ export fn flush_thread_reserves() void {
     }
 }
 
-fn flush_thread_fc(info: *SlabInfo, tl: *TlSlabInfo, slab: [*]u64) void {
+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: [*]u64 = slab[idx..];
+        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: [*]u64 = slab[idx..];
+        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);
     }