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 an
excess of committed memory back to 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.

*Erratum: The previous paragraph is bogus, since this optimization
would break the sort order.  We must live with tall trees.*

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.

For larger size classes, the meaningful bit-count goes down one by
one, while the bit-count of words increases one by one:

* 256-byte slots: 27 bits / 6-bit words: max height 5

* 512-byte slots: 26 bits / 7-bit words: max height 4

* 1 KiB slots: 25 bits / 8-bit words: max height 4 (ugh!)

* 2 KiB slots: 24 bits / 9-bit words: max height 3

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.  Actually, I'm not sure
whether that would really be an optimization; may need a benchmark,
and may depend on size class.


### How to traverse

Now that we have a sorted trie of pointers, it's relatively easy to
traverse it to find contiguous sequences.

Remember that we shifted our pointer values down, to erase bits which
are always zero.  This means every array position within every node
needs to be checked for an interruption, except in the deepest level
where you have to be careful not to produce a false positive, since,
for example, splitting 28 bits into 5-bit words means the last level
can only ever have 8 array positions occupied (from the last 3 bits)
rather than the full 32.

So, we do the following loop:

1. Take the lowest pointer (index) in the trie, which is the first
   non-NULL at the highest level.  It's the start of a memory span.
   Begin a depth-first search.

2. Continue the search until you hit an interruption.  You found the
   end of the current span.

3. If the span is long enough, turn it into a vacancy-list entry;
   otherwise turn it into free-list chunks.

4. Continue the search to find the next non-NULL pointer; it's the
   start of the next span.  Go to step 2.


### Will I add it to Meta Alloc?

No, I'm not going to implement this yet.  I think it's way too much
complexity for a feature that may hardly ever be needed.

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


### Useful to others?

Can any general-purpose allocator using free-lists make use of this
strategy?  I think yes, provided that:

* Each free-list entry points to a memory slot that can hold at least
  two references to other slots, but preferably many more.

  Only two pointers per level would mean you have to split pointers
  into individual bits to navigate.  Given 48-bit pointers, that'd
  mean a maximum trie height of 48.

* The slots are of a known equal size, or have enough extra room to
  also store a size header I guess?

  I've not thought much about unequal slot size, since it isn't
  relevant to Meta Alloc, but I think it would work.

And, assuming that the "sort a chunk of indexes in-place first" idea
actually improves performance by decreasing the need to move around
too much data between nodes, then we can emulate that:

* Use a statically allocated "scratch-pad array" into which you load
  chunks of free-list entries, so you can sort them in-place before
  iteratively adding them to the trie.