Add meta alloc docs, do code and doc cleanup.

5 files changed, 369 insertions, 44 deletions

diff --git a/doc/0/0-value.md b/doc/0/0-value.md
index b84a528..61d01d9 100644
--- a/doc/0/0-value.md
+++ b/doc/0/0-value.md
@@ -135,6 +135,13 @@ different unit sizes.  For instance, `istr` (interned string) pointers may use
 byte-addressing, meaning the 32-bit index limits the `istr` heap to 4 GiB only,
 while list pointers use 64-bit (8-byte) addressing, allowing for a 32 GiB heap.
 
+Note: The separation of heaps is a possibility, not a guarantee.  In practice,
+the various 32-bit indexes may share a single value domain, in which case list
+pointers, heap pointers, etc. would never have equal 32-bit index values; they
+may or may not, depending on current implementation details.  The unit size of
+each type of 32-bit index is also not guaranteed, but is at least 8 bytes for
+list pointers, since a list must contain at least one 64-bit Zisp Value.
+
 ### List pointers
 
 In Zisp, a list is a contiguous array of a fixed number of Values.  To improve
@@ -156,12 +163,12 @@ lists can't needlessly trigger the code branch that handles list pointers.
 Note that "list pointer" and "list heap" are slightly misleading terms, since
 arbitrary-length lists can be allocated on the main heap as Array objects with
 element type Value.  In this case, they are represented by a main heap pointer,
-and the generic list API hides the difference.
+and a generic list API may hide the difference.
 
 ### Heap pointers
 
 Regular heap objects are represented by this pointer type, which uses a 32-bit
-index into the main heap, in the lower portion of the 48-bit payload.
+heap index in the lower portion of the 48-bit payload.
 
 Of the 16 high bits of the payload, the upper 8 are used to immediately encode
 the type of the heap object, and the remaining 8 are used for internal metadata
@@ -171,8 +178,10 @@ This means our 64-bit Values can be checked against heap types by comparing the
 24 high bits to a combined constant: the 16 high bits that indicate it's a main
 heap index, plus 8 more bits encoding a specific heap type.
 
-Some heap types may actually reside in their own separate heap, meaning the
-32-bit index may refer to yet another memory region rather than the main heap.
+Different types may reside in different heaps, meaning the 32-bit index values
+of different heap types may or may not share value domains.  The index value of
+two heap pointers, of different types, being equal, is neither a guarantee that
+they share a memory location, nor is it ruled out.
 
 ### String pointers
 
@@ -180,13 +189,9 @@ An `istr` is a string of up to 255 arbitrary bytes, that is typically interned,
 fulfilling a similar purpose to symbols in Lisp and Scheme.  If uninterned, we
 could consider the 'i' to mean *intermediate* length string instead.
 
-Of the 48-bit payload value, the lower 32 bits are an offset into a dedicated
-virtual memory region for this type only, bounding total memory use to 4 GiB,
-which should be more than enough.
-
-The higher 16 bits of the payload are divided in two halves.  The upper 8 bits
-directly encode the length, which cannot be zero; the lower 8 bits are used for
-garbage collection metadata.
+Of the 48-bit payload value, the low 32 bits are a heap index, while the higher
+16 bits are divided into 8 high bits for a non-zero length, and 8 low bits for
+internal metadata such as for garbage collection.
 
 The empty string is represented as a *short string* instead; see below.
 
diff --git a/doc/0/A-meta_alloc.md b/doc/0/A-meta_alloc.md
new file mode 100644
index 0000000..45d851a
--- /dev/null
+++ b/doc/0/A-meta_alloc.md
@@ -0,0 +1,315 @@
+# Meta Allocator
+
+<!--TOC-->
+
+The Zisp runtime aims to offer peak performance.  Although Zisp also
+aims to offer a capability to generate optimal binaries with native
+compiled code, performing its own memory management, with no runtime
+dependencies, it is expected that many programs will simply opt for
+interpreted code, or at least automatic memory management and other
+runtime features like dynamically resizing collection objects.
+
+If we manage to offer a runtime whose performance is already within
+reasonable proximity to fine-tuned C code, then the number of times
+programmers find themselves reaching for more complex code, such as
+manual memory management, can be minimized.
+
+To this end, Zisp entirely foregoes general-purpose heap allocators
+offered by the platforms it runs on, or the standard library of the
+language it's implemented in, and instead implements its own memory
+allocator based directly on `mmap()` and equivalents.
+
+This is called the Meta Allocator, because various parts of the Zisp
+runtime are expected to implement their own local memory management
+strategies, such as arena allocators or object pools, while still
+relying on Meta Alloc so that they don't need to individually deal
+with expensive `mmap()` calls.
+
+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:
+
+1. The actual heap memory acquired through `mmap()` which is a single
+   contiguous block divided into N equally sized slabs; one per size
+   class.
+
+2. A global array of N metadata structures residing in static memory.
+
+3. A per-thread array of N metadata structures in TLS memory.
+
+Note that the slab array is a *virtual memory* block.  The operating
+system automatically maps physical memory to it as application code
+writes data into it.  Allocating one massive block of virtual memory
+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
+the massive block of slab virtual memory.
+
+This initialization happens by calling the `init()` function once.
+This must be done before any additional threads are spawned that
+intend to interact with Meta Alloc.
+
+The vmem block is divided in `N_SLABS` equal slabs, each divided into
+`SLAB_LENGTH` many equal `Unit`s of memory, which are addressed via
+*indexes* into slabs.  Expressed in pseudo-code:
+
+    var slabs: *[N_SLABS][SLAB_LENGTH]Unit = undefined;
+
+    export fn init() void {
+      slabs = mmap(N_SLABS * SLAB_LENGTH * sizeof(Unit));
+    }
+
+The division of slabs into `Unit`s is simply to allow expressing the
+address of an allocation through an index value, such as one fitting
+into 32 bits, rather than a full pointer value.
+
+Every slab is for a specific *size class*.  Since the slabs are equal
+sized, this means that for larger size classes there is a lower bound
+of the maximum number of allocations that can be made of that class.
+The actual blocks of memory returned are called *slots* which consist
+of a multiple of `Unit`s depending on the size class.
+
+For example, if the unit size is 8 bytes, then a slot of the 512-byte
+size class covers 64 units.  Meaning: The slab for the size class 512
+allows up to `SLAB_LEN / 64` calls to `alloc()` before panicking, if
+no slot of this size class is ever freed.
+
+Current implementation details:
+
+* `N_SLABS`: 16
+
+* `SLAB_LENGTH`: 2^31
+
+* `Unit` size: 8 bytes
+
+Therefore:
+
+* Size of each slab: `2^31 * 8 = 16 GiB`
+
+* Total slab virtual memory: `16 GiB * 16 = 256 GiB`
+
+If you notice, after launching the Zisp REPL or a program using the
+Zisp runtime, that the operating system reports that the process is
+using hundreds of gigabytes of virtual memory, do not panic; it's a
+feature, not a bug, and completely benign.
+
+As for the size classes: They simply go from 256 bytes to 8 MiB in
+perfect powers of two; in other words, from 2^8 to 2^23.  There are
+certain benefits to using exact powers of two, and 256 bytes to 8M
+seems like a reasonable range.  Code using Meta Alloc must be aware
+that only these size classes are supported, and try to make optimal
+use of them.
+
+**WARNING:** Calling `alloc()` with a size smaller than 256 or one
+that is not a perfect power of two will lead to catastrophic bugs
+under optimized builds of Zisp.
+
+Generally, Zisp application code will have no direct access to this
+function, so this should not be a big deal so long as Zisp's runtime
+implementation is thoroughly tested.
+
+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
+record just two pieces of information associated with each slab:
+
+* The current *watermark* of the slab.
+
+* The head of the global, shared *free-list* for this slab.
+
+Expressed in pseudo-code:
+
+    struct SlabInfo {
+      watermark: Integer,
+      free_list: ListHead,
+    }
+
+    var slab_infos: [N_SLABS]SlabInfo;
+
+The `ListHead` need not be a direct pointer nor plain slot index; it
+may be a composite value including an ABA counter to help against the
+ABA problem:
+
+* [https://en.wikipedia.org/wiki/ABA_problem](ABA problem)
+
+In other words, it may be implemented as a Treiber stack:
+
+* [https://en.wikipedia.org/wiki/Treiber_stack](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.
+
+### Slab watermark
+
+The watermark represents the point above which, within the slab, the
+memory has not yet been touched at all, or has been explicitly given
+back to the operating with a call to `madvise()` or similar so the
+physically backing memory can be released.
+
+Below the watermark is memory which is either currently in use by the
+application, or has been marked for reuse by a `free()` call but is
+still backed by physical memory.  In some circumstances, Meta Alloc
+may use `madvise()` to tell the operating system that some regions
+below the watermark can actually be reclaimed, because they are not
+currently needed; in other circumstances, otherwise unused (freed)
+memory below the watermark may actually hold metadata used by Meta
+Alloc itself; this is where the free-list comes into play.
+
+### Free-lists
+
+Given that the allocator cannot trust the user to always free memory
+in reverse order to which it was acquired, it cannot simply decrease
+the watermark when `free()` is called.  It has to record that memory
+slot for reuse somehow, even if it's deep below the watermark.
+
+This introduces a little chicken-and-egg problem: Since we are the
+allocator, who allocates the dynamic memory required to record the
+pointers to these freed slots, of which there could be plenty?
+
+Thankfully, a very elegant solution exists: Use the memory of the
+freed slots themselves to form a linked list of free slots; where
+within each freed slot, we store a pointer to the next.
+
+Meta Alloc implements an improvement over this common strategy:
+
+Given that even the smallest size class is fairly large, and given
+that we can use small index values, rather than full pointers, to
+represent addresses of slots, each node in the free-list actually
+contains the following structure:
+
+    {
+      next_head_idx:   Index,
+      extra_idx_count: Count,
+      pad_to_64_bytes: Padding,
+      extra_idx_array: [MaxCount]Index,
+    }
+
+The bit-size of indexes, the maximum allowed count, and the smallest
+size class, must all be defined such that this works.  The current
+values used by the implementation are as follows:
+
+* Index: 32-bit integer
+
+* Count: 32-bit integer
+
+* Padding: 56 bytes
+
+* Maximum count: 32 indexes
+
+* Smallest size class: 256 bytes
+
+The extra index array starts after 64 bytes, and requires 128 bytes,
+since it stores up to 32 4-byte integers; that gives us a total size
+of 192, which fits in under 256 bytes.
+
+The 64-byte padding is to allow for efficient bulk memory transfer
+using up to 512-bit SIMD instructions on modern processors.
+
+Why we would need to bulk-transfer 32 index values will be explained
+later, as we look into thread-local cache metadata.
+
+## Per-thread metadata
+
+We don't want to burden code using Meta Alloc with concerns about
+thread safety; `alloc()` and `free()` should be inherently safe.
+
+If each call to these functions needed to touch the global watermark
+or free-list of a size class, it could lead to contention.  As such,
+threads use two tricks to decrease their need to access the global,
+shared metadata:
+
+* Bumping the slab's watermark in chunks to reserve a number of slots
+  for the current thread every time the global watermark needs to be
+  increased.
+
+* Using a free slot cache of static size within TLS memory, which is
+  emptied into the global free-list in chunks when full, and fed from
+  the global free-list in chunks when empty.
+
+Pseudo-code follows; detailed explanations are further below:
+
+    struct ThreadInfo {
+      watermark_low: Integer,
+      watermark_high: Integer,
+      free_cache_count: Integer,
+      free_cache_array: [FC_MAX]Index,
+    }
+
+    thread_local tl_info: [N_SLABS]ThreadInfo;
+
+### Reserved memory
+
+The reservation of slots is done simply by keeping a thread-local low
+and high watermark value: Low is the starting point of reserved but
+not yet used memory, and high is the endpoint.  When low meets high,
+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.
+
+### Free slot cache
+
+When `free()` is called in a thread, it checks whether there's still
+room in its local free slot cache.  If it's full, it instead moves an
+entire chunk into the global free-list.  When `alloc()` is called, it
+checks if there's slots in its local cache; if not, it checks if the
+global free-list has anything, and transfers a chunk from there to
+feed some entries into the local cache.
+
+This emptying and freeing is done in halves.  If the entire cache was
+emptied when full, or filled when empty, it could cause "thrashing"
+when a thread is repeatedly alternating between `alloc` and `free`
+calls while just at the boundary: The alloc call fills the whole
+cache, the free call empties it again, and so on.
+
+For this reason, the maximum size of the free slot cache per thread
+can be twice as large as the maximum chunk size in the slab's global
+free-list.
+
+There is one more nuance to be aware of:
+
+Consider a free slot cache of 64 entries.  And remember that slabs
+have equal size, meaning larger size classes allow for fewer total
+numbers of allocations.  For very large size classes, we don't want
+every thread that ever called `alloc()` once to immediately hog 64
+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.
+
+### Thread destruction
+
+When a thread that used Meta Alloc is going to exit, it must flush
+whatever reserves it holds so as to prevent leaks.  This is done via
+the function `flush_thread_reserves()` which is also safe to call at
+any other point, though this is typically pointless.  One must only
+ensure that it's called at least once by a thread, before it exits,
+without any other subsequent calls to `alloc()` or `free()` before
+exiting.
+
+This immediately transfers the thread's free slot cache into the
+global free-list, in multiple chunks if necessary, and also creates
+free-list chunks for memory it had reserved by bumping the global
+watermark.
+
+## 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)
+
+End.
diff --git a/doc/0/index.md b/doc/0/index.md
index da707d2..77a6a4c 100644
--- a/doc/0/index.md
+++ b/doc/0/index.md
@@ -35,7 +35,7 @@ compiling code.
 
 ## Appendices
 
-+ Appendix A: [Memory](A-memory.html)
++ Appendix A: [Meta Allocator](A-meta_alloc.html)
 
   Zisp foregoes use of a platform-provided heap allocator as much as
   possible, in favor of an efficient heap allocator specialized for
diff --git a/doc/index.md b/doc/index.md
index 4087078..3aebb55 100644
--- a/doc/index.md
+++ b/doc/index.md
@@ -23,7 +23,7 @@ as a language reference.
 
    Appendices:
 
-   + A. [Memory](./0/A-memory.html)
+   + A. [Meta Allocator](./0/A-meta_alloc.html)
 
 1. [Chapter 1: Taxonomy](./1/)
 
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);
     }