From 7d114373beb185a8fb52f3748137d10a4ba2aa34 Mon Sep 17 00:00:00 2001 From: Taylan Kammer Date: Mon, 17 Aug 2026 14:39:14 +0200 Subject: Add a note. --- notes/260817-release.md | 169 ++++++++++++++++++++++++++++++++++++++++++++++++ notes/index.md | 1 + 2 files changed, 170 insertions(+) create mode 100644 notes/260817-release.md 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) -- cgit v1.2.3