Unfinished note and a note correction.

1 files changed, 123 insertions, 0 deletions

diff --git a/notes/260822-release3.md b/notes/260822-release3.md
new file mode 100644
index 0000000..d4f0741
--- /dev/null
+++ b/notes/260822-release3.md
@@ -0,0 +1,123 @@
+# 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]