Add a note.

2 files changed, 170 insertions, 0 deletions

diff --git a/notes/260817-release.md b/notes/260817-release.md
new file mode 100644
index 0000000..44429ab
--- /dev/null
+++ b/notes/260817-release.md
@@ -0,0 +1,169 @@
+# Releasing virtual memory
+
+_2026 August_
+
+Allocators often face the issue of not being able to release virtual
+memory back to the operating system.
+
+Here I describe a strategy through which Zisp's "Meta Allocator" as
+I've decided to name it can solve this.
+
+The strategy may be applicable to more general-purpose allocators as
+well; I've not thought much about it and don't currently care.  I'll
+simply describe this strategy in terms of how it applies to the Zisp
+Meta Allocator.
+
+## Recap of the relevant parts of Meta Alloc
+
+For each of the 16 size classes supported, there's a 16 GiB slab, a
+global (shared) free-list, and a watermark beyond which the slab's
+memory has not yet been touched.
+
+Above the watermark hasn't been paged in by the kernel anyway, since
+it's never been touched.  But the entire region below the watermark
+has physical RAM or swap space backing it.
+
+We need to find vacant spans of memory under the watermark, and tell
+the OS that we don't need them by calling `madvise(DONTNEED)` so the
+kernel can reclaim the backing physical memory.
+
+Let's focus on a single size class; the strategy I'll describe can
+then be applied iteratively to each one.  I'll be speaking of one
+global free-list from now on; what's meant is the global free-list
+belonging to the specific size class we're operating on.
+
+## The problem
+
+As many allocations and deallocations happen in chaotic order, the
+memory of a slab becomes filled with free-list entries all over the
+place, which hold metadata and thus aren't even truly unused.
+
+(Note on terminology: A slot is the size-class sized piece of memory
+the allocator returns to the user; the slot index is the position of
+the slot within the slab it belongs to, like a compressed pointer.)
+
+Although Meta Alloc puts entire inline arrays of free slot indexes
+into the nodes of the free-list, meaning that many freed slots are
+actually completely empty (not as in zero bytes but as in devoid of
+meaningful data; they just hold whatever bytes were put in by the
+application before freeing the slot) it's nevertheless not easy to
+find long spans of such free slot indexes, since the slots may be
+freed in any order.
+
+For example, you may look into the head node of the global free-list
+and find it to contain the indexes 13, 129, 73, 5, 36, ... which is
+pretty useless because we don't want to call `madvise()` in a loop;
+that would be very inefficient.  And even that extremely simplistic
+strategy would only work for size classes 4K and up.
+
+No, we need a way to actually find long spans of unneeded memory.
+
+## The process
+
+It's quite simple, really:
+
+* Allocate a reasonably large array, perhaps simply with `mmap()` or
+  using a slot from one of our own huge size classes; doesn't matter.
+
+* Optionally, call the function that flushes thread-local reserves,
+  which is normally meant for thread shutdown but it can be called
+  whenever you want because it doesn't destroy anything.
+
+* Iterate through the global free-list, putting all indexes into our
+  big array.  (Including indexes of the nodes themselves.)  Sort it
+  in-place.  Reset the global free-list.
+
+* Now iterate through the sorted array, identifying contiguous index
+  sequences, which represent uninterrupted spans of unneeded memory.
+
+* If the sequence represents a span of memory large enough to be worth
+  freeing back to the OS, transform it into a vacancy-list entry, and
+  call `madvise(DONTNEED)` on the sub-span starting at the next page
+  boundary, going up to the last page boundary within the span.
+
+* If the sequence is interrupted before a worthy size is reached, put
+  the indexes back into the global free-list.
+
+## What the fuck is a vacancy-list entry
+
+That's simple, too:
+
+It's just like the free-list, but instead of each node containing a
+bunch of freed slot indexes and the index of the next node, the nodes
+of the vacancy-list instead just contain the size of the vacancy, and
+a pointer to the next vacancy-list entry.
+
+Remember, the vacancy-list entries represent large spans of memory,
+since they were created from contiguous free slot indexes.  So you
+just need to record the size, and have a pointer to the next; the
+entire rest is a huge chunk of (now) completely unused memory.
+
+It's like a free-list for arbitrarily size holes in vmem.
+
+## How do I reuse the vacancies?
+
+A simplistic strategy --too simplistic-- would be to use the start of
+the vacancy as the new "low watermark" of a thread, setting the "high
+watermark" to the end of the vacancy, thus reserving the entire thing
+for a thread.
+
+(Threads have a low and high watermark to represent reserved regions
+of memory within a slab, so they don't need to update the global slab
+watermark too often, which requires an atomic operation.)
+
+(This would happen when a thread doesn't have any entries in its free
+slot cache, no reserved memory from the slab, and the global free-list
+is also empty.  Better to leave the vacancy vacant for as long as we
+don't absolutely need it, since using it means page faults.)
+
+The reason this is too simplistic is that the vacancy may be way too
+large to make sense to reserve for a single thread.
+
+Instead, the thread can set its low and high watermark to a sub-span
+of the vacancy, and update it accordingly.  Unless it's small enough
+to make sense to reserve entirely, in which case its used up and
+popped from the global vacancy-list.
+
+## That's all
+
+That's it.  That's the entire strategy.
+
+It requires a large amount of temporary memory and an in-place sort;
+performance won't exactly be great, so this operation should only be
+performed upon explicit request.  Also, the need for extra temporary
+memory means this is *not* intended for when memory is tight!
+
+For example, if an application using our Meta Alloc has an intensely
+memory hungry initialization process, but is then expected to run for
+hours or days with lower memory requirements, or if there's certain
+highly memory intensive subroutines that are only rarely performed,
+then the application code could explicitly request this vmem release
+operation after the memory intense section.
+
+I'm not actually planning to implement this yet, but it's good to
+document the idea for the future.
+
+Oh, actually, this could mostly happen in parallel in a background
+thread: The nodes of the global free-list could be popped one by one
+through atomic ops without the need for an entire mutex-guarded code
+section, and the vacancy-list entries later pushed one by one.  So,
+the time required may be mostly a non-issue.  Still, the issue with
+extra memory use remains.
+
+## So what if memory is tight?
+
+OK, there's an even simpler little strategy that doesn't require any
+extra temporary memory:
+
+Iterate through the free-list of a size class that's at least page
+sized (4K), and for each index that represents a completely unused
+slot (i.e., the indexes that are inlined within the free-list node)
+call `madvise(DONTNEED)` directly on the memory of the slot.
+
+This only works for sufficiently large size classes, but needs no
+sorting of indexes in extra memory.  How the execution time would
+compare depends on how costly `madvise()` is, and how many indexes
+you'd be sorting; I've no idea.
+
+This could save us from OOM in a pinch.  It should probably not be
+automated, except maybe for some humongous size classes.
diff --git a/notes/index.md b/notes/index.md
index 4db530a..7bdde42 100644
--- a/notes/index.md
+++ b/notes/index.md
@@ -36,3 +36,4 @@
 * [AST Optimizations](260625-optimize.html)
 * [Further list array optimization](260626-fastcons5.html)
 * [Allocation strategy](260727-alloc.html)
+* [Releasing virtual memory](260817-release.html)