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

Here's a method that sacrifices CPU time, in exchange for locating
unused spans of memory from a free-list without extra allocation.


## Locking

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 strategy for synchronization.  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 that based
   on whether memory pressure is really that severe.  This way, the
   free-list pruning can be done 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()) // Reads atomic flag
      sleep_until_unbanned(); // Could just be a 10 ms sleep loop.

    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.

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

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

At this point I have to admit that the following is probably way too
much complication for a small benefit, and this is partly just a fun
mental exercise.

[TBC]