1 files changed, 315 insertions, 0 deletions
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.