path: root/notes/260822-release3.md

# Releasing vmem, again

_2026 August_

Finding contiguous spans of freed memory is difficult when all you
have is a free-list in arbitrary order.

It's especially difficult if you don't want to allocate auxiliary
memory, which is crucial if you're trying to free memory to the OS
because it's signaling memory pressure or declining an allocation.

Below are two ways to achieve this.  The first is almost trivial in
both complexity and CPU cost.  The second is highly complex and may
incur significant CPU cost, but should still be quite reasonable to
employ if there is a need for aggressively releasing memory back to
the kernel due to pressure or because the application just finished
some extremely memory-intensive subroutine and wishes to release it
back to the rest of the system.


## Locking

Before going into the actual algorithms that will achieve our goal,
let's consider their thread safety.

Meta Alloc uses a lock-free Treiber stack for the free-list, which
only works when threads contend for the top node of the linked list,
trying to push and pop in parallel.

Any subroutine that wants to walk through the whole list will need
some other safety strategy.  Here are some choices:

1. Some way to communicate to the relevant portions of `alloc()` and
   `free()` that the free-list is locked.  Not sure how to best do
   this in a way that doesn't defeat the purpose of the lock-free
   strategy, but there are ways.

2. Atomically swap out the entire free-list (replace head with NULL
   through a CAS) and swap it back in when we're done.  This would
   mean that threads simply go on to allocate fresh memory, while
   we're busy releasing memory.  Probably not great.

3. Atomically swap out the entire free-list, but also use some global
   flag that says "fresh allocations banned."  The benefit of this is
   that you don't *have* to set that flag; you can decide it based on
   whether memory pressure is severe.  This way, our free-list sweep
   algorithms can run without stalling allocations, when there's no
   such dire pressure.

I think I like the third.  It means that, when fresh alloc is banned,
threads will stall after they've found the free-list to be empty, but
can just check it again once they continue.  Pseudo-code:

    if (check_free_list()) |ptr|
      return ptr;

    if (fresh_alloc_banned()) {
      sleep_until_unbanned();
      if (check_free_list()) |ptr|
        return ptr;
    }

    if (check_vacancy_list()) |ptr|
      return ptr;

    return alloc_fresh_memory();

And if the ban isn't put in place, threads don't stall at all, which
seems ideal.  The fact that they'll bump the slab watermark when it
isn't truly needed is benign; we just end up with some holes in our
slab, recorded in the vacancy-list, so they'll be reused if needed.


## The obvious

Before doing anything more complicated:

For each size class greater than or equal to page size, use the above
strategy to hide the free-list, go through it and `madvise(DONTNEED)`
every non-chunk-head slot, then put the free-list back in place.

For example, if the 64 KiB size class uses free-list chunk nodes that
carry 4 extra slot indexes, it means 4 out of every 5 slots can be
released back to the OS.

Oh, actually, chunk heads never use more than the first 128 bytes of
the slot.  (Subject to change by tweaking constants, but it'll surely
never reach 4 KiB.)  So, we can also safely release every non-first
page of every chunk head slot.  Taking the 64 KiB size class as an
example again, where each slot is 16 pages (assuming 4 KiB), we can
release `4*16+15` out of `5*16` pages.  That's 79/80, or 98.75% of
memory held by the free-list, that we can release.  Very good!

I think the worst-case is the 4 KiB size class, and even there, the
free-list chunks store 8 other slots, so we release 8 out of every 9
pages back to the OS.  That's ~88.89% which isn't too bad.  The next
is the 8 KiB class where it comes out to 17/18 i.e. ~94.44%.


## The tedious

The challenge is size classes under 4 KiB.  Or if we want something
better than ~88% release efficiency for 4 KiB / better than ~94% for
the 8 KiB size class.  (Beyond that, it seems stupid to worry about,
as we surpass 95% release efficiency.)

So let's see what we can do if individual slots are under a page,
meaning we have to find contiguous sequences of them across the
free-list to be able to consolidate and release them.

The consolidation in question could happen in two ways:

* Transform the free-list such that contiguous slots are, as much as
  possible, not used as chunk heads, so the pages of memory they make
  up can be released.  This works, for example, if we have four 1 KiB
  slots that form a contiguous span of memory, i.e. a page, so we can
  release that page and make sure to store these four indexes within
  some chunk header, not using any of them as a header that needs to
  hold data.

* Just turn the contiguous spans of memory we find into vacancy-list
  entries instead.

The second option is simpler and simply better.  I don't know why I
even bothered to write out the first option.

The only question, then, is how to identify such contiguous slots in
the free-list, which carries indexes in arbitrary order.


### Self-Reflecting Pointer Trie

I don't know if this is a new invention, or if I'm reinventing some
idea others came up with before:

The Self-Reflecting Pointer Trie is a trie of pointers in which the
pointers making up the structure of the trie also happen to be the
pointers stored as data in the trie.

The pointers must be cut up into units we will call "words" for the
sake of simplicity.  Let's demonstrate this with 16-bit pointers cut
into 4-bit words, so it fits in a small graphic.

Given that each word (4 bits) can have 16 different values, nodes of
the trie must be able to hold arrays of 16 pointers.  In other words,
every pointer leads to a memory location large enough to store at
least 16 other pointers.

We will use hexadecimal to represent pointers and array indexes; one
hexadecimal digit 0 to F represents a 4-bit word / array position.

The following graphic shows a Self-Reflecting Pointer Trie that has
the pointers 1234, 1256, 7800, and 7855 stored in it:

    Root -> [  // Level 1: Sorts by first word.

      [0]   [1]   [2]   ...  [6]   [7]   [8]   ...
      null  1234  null  ...  null  7800  null  ...

    ]

    1234 -> [  // Level 2: Sorts by second word.

      ...   [1]   [2]   [3]   ...
      ...   null  1256  null  ...

    ]

    7800 -> [  // Level 2: Sorts by second word.

      ...   [7]   [8]   [9]   ...
      ...   null  7855  null  ...

    ]

    1256 -> [ <empty> ]  // Level 3

    7855 -> [ <empty> ]  // Level 3

As you can see, the pointer 1234 is both stored in the root node as
data, and happens to point to a node which can hold further pointers
sharing the same first word with it.

The pointer 1256 is stored as data at the second level, and points to
a node that would store further pointers sharing the first and second
word with it.

The maximum level (height) would be 4, corresponding to the number of
words a pointer is made of.

In this example, the trie is already "sorted" in the sense that the
pointer 1234, stored in the root, is less than 1256, stored in the
node 1234.  What if we insert 1200?  Keeping it sorted is easy:

If a pointer to be stored has a value less than a parent under which
it would be stored, then move the contents of the parent into it, put
it in place of the parent, and continue the insertion procedure with
the parent pointer's value.  I believe this is similar to rotation of
an AVL tree, though I've never worked with them.

By the way, pointers most commonly have more variance in their least
significant bits.  That is, you are more likely to encounter pointer
groups like 0001, 0003, 0012, etc. that have equal higher bits, than
pointer groups like 1000, 3000, 1200, etc. which vary in their high
bits while having equal low bits.  For this reason, after splitting
pointers into words, it's best to order them low to high when using
them to navigate.  Otherwise, the trie will quickly become tall and
narrow; pessimal for efficiency.

Of course, 16-bit pointers are easy.  Let's see how we can actually
implement this strategy in Meta Alloc.


### Actual implementation

Based on the current implementation details of Meta Alloc, we can use
the following schema in practice:

* Our "pointers" (indexes) are 32 bits including the highest bit that
  signals NULL.  But given that the smallest size class is 128 bytes,
  which is 16 "units" in terms of index values, the lowest four bits
  are always zero, so there are only up to 28 meaningful bits.

* Our smallest size class being 128 means that every slot (trie node)
  can store up to 32 indexes, which allows splitting our indexes into
  5-bit words.

* That means we have a maximum trie height of 6, with 2 spare bits.

The need to move entire node contents to keep the trie sorted worries
me a little, but I think it should be fine.  Just make sure to sort
the indexes within each free-list chunk in-place before iterating
through them to insert them into the trie.

I'm not going to implement this yet.  It's way too much complexity,
only to offer a feature that may hardly ever be needed.

But it was fun to come up with, and good to know that it's possible.