# 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. *Late addition: This would need to happen behind a lock, since other threads may otherwise acquire those slots and start writing data into them, after which we call `madvise()` and cause it to be erased.* 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.