path: root/doc/0/A-meta_alloc.md

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