# 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` elements of memory, addressed through
*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 Units is simply to allow the expression of
addresses, offsets, etc. through an Index value, such as one fitting
into 32 bits, rather than full pointer-sized values.

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 variable number of Units, depending on the class.

For example, if the Unit size is 8 bytes, then a Slot of the 512-byte
class covers 64 Units.  Meaning: The Slab for the 512-byte class can
only offer up to `SLAB_LENGTH / 64` Slots.  If `alloc()` is called
repeatedly for 512 bytes without ever freeing, the allocator will
panic after that many calls.

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 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.

* The head of the global, shared *Vacancy-List* for this Slab.

Expressed in pseudo-code:

    struct SlabInfo {
      watermark: Integer,
      free_list: ListHead,
      vacancy_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, Free-List, and Vacancy-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 must record the 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: 16 Indexes

* Smallest size class: 128 bytes

The extra Index array starts after 64 bytes, and requires 64 bytes,
since it stores up to 16 32-bit integers; that's a total size of 128,
which fits exactly into the smallest size.

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 16 Index values will be explained
later, as we look into thread-local cache metadata.

### Vacancy-List

For reasons we will go into later, there may be memory regions below
the Watermark of a Slab that are completely vacant, span across pages
of memory, and need not be backed by physical memory.

Vacant, in this case, means no *meaningful* data is held; either the
memory has never been touched and is all zeros, or application code
has given it back for freeing and we decided not even to store any
meta-data in it, so we don't care if it's zeroed out.

Such memory regions are recorded in the Vacancy-List, which has the
following simple node structure:

    {
      next_vacancy_idx: Index,
      vacancy_end_idx: Index,
    }

These nodes themselves occupy the beginning of each such vacancy,
which means that the real vacancy only begins after two Indexes.
Starting from the next page boundary after that, writing any data
could lead to a page fault.

Slots in the Free-List, in contrast, are likely to have physical
memory backing them, which is why they're given out first.

The Vacancy-List is the penultimate choice to satisfy an allocation
request, before increasing the Watermark and giving out completely
fresh memory.


## 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.

When Meta Alloc decides to reach for Vacancy-List entries, it does
that by setting the calling thread's Low and High to the start and
ending point of the vacancy.

### 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.

Note: While the bumping of the global Watermark happens in massive
chunks for the smaller size classes, the Free Slot Cache has small
upper limits throughout all size classes.  This is because, while
reserving a big "hole" in a Slab is benign (since physical memory
won't be mapped until pages are touched), freed Slots have physical
memory backing them already, making it important not to keep around
too many of them in some thread's local cache without being reused.

### 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 entries into
the global Free-List, in multiple chunks if necessary; and creates a
Vacancy-List entry for leftover reserved memory (from the bumping of
the global Watermark) if the amount of reserved memory spans across
multiple pages.  Otherwise, it's simply split into Slots and also
pushed onto the Free-List.

## Releasing vmem

Though not currently implemented, Meta Alloc may be able to release
virtual memory back to the operating system by detecting that there
are Free-List entries corresponding to contiguous memory regions
spanning across pages of memory.

In this case, these Free-List entries may be removed, a Vacancy-List
entry created instead, and one or more pages of memory given back to
the operating system.