# 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. Below are two ways to achieve this. The first is almost trivial in both complexity and CPU cost. The second is highly complex and may incur significant CPU cost, but should still be quite reasonable to employ if there is a need for aggressively releasing memory back to the kernel due to pressure or because the application just finished some extremely memory-intensive subroutine and wishes to release it back to the rest of the system. ## Locking Before going into the actual algorithms that will achieve our goal, let's consider their thread safety. 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 safety strategy. 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 it based on whether memory pressure is severe. This way, our free-list sweep algorithms can run 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()) { sleep_until_unbanned(); if (check_free_list()) |ptr| return ptr; } 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. Very good! 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 first option. The only question, then, is how to identify such contiguous slots in the free-list, which carries indexes in arbitrary order. ### Self-Reflecting Pointer Trie I don't know if this is a new invention, or if I'm reinventing some idea others came up with before: The Self-Reflecting Pointer Trie is a trie of pointers in which the pointers making up the structure of the trie also happen to be the pointers stored as data in the trie. The pointers must be cut up into units we will call "words" for the sake of simplicity. Let's demonstrate this with 16-bit pointers cut into 4-bit words, so it fits in a small graphic. Given that each word (4 bits) can have 16 different values, nodes of the trie must be able to hold arrays of 16 pointers. In other words, every pointer leads to a memory location large enough to store at least 16 other pointers. We will use hexadecimal to represent pointers and array indexes; one hexadecimal digit 0 to F represents a 4-bit word / array position. The following graphic shows a Self-Reflecting Pointer Trie that has the pointers 1234, 1256, 7800, and 7855 stored in it: Root -> [ // Level 1: Sorts by first word. [0] [1] [2] ... [6] [7] [8] ... null 1234 null ... null 7800 null ... ] 1234 -> [ // Level 2: Sorts by second word. ... [1] [2] [3] ... ... null 1256 null ... ] 7800 -> [ // Level 2: Sorts by second word. ... [7] [8] [9] ... ... null 7855 null ... ] 1256 -> [ ] // Level 3 7855 -> [ ] // Level 3 As you can see, the pointer 1234 is both stored in the root node as data, and happens to point to a node which can hold further pointers sharing the same first word with it. The pointer 1256 is stored as data at the second level, and points to a node that would store further pointers sharing the first and second word with it. The maximum level (height) would be 4, corresponding to the number of words a pointer is made of. In this example, the trie is already "sorted" in the sense that the pointer 1234, stored in the root, is less than 1256, stored in the node 1234. What if we insert 1200? Keeping it sorted is easy: If a pointer to be stored has a value less than a parent under which it would be stored, then move the contents of the parent into it, put it in place of the parent, and continue the insertion procedure with the parent pointer's value. I believe this is similar to rotation of an AVL tree, though I've never worked with them. By the way, pointers most commonly have more variance in their least significant bits. That is, you are more likely to encounter pointer groups like 0001, 0003, 0012, etc. that have equal higher bits, than pointer groups like 1000, 3000, 1200, etc. which vary in their high bits while having equal low bits. For this reason, after splitting pointers into words, it's best to order them low to high when using them to navigate. Otherwise, the trie will quickly become tall and narrow; pessimal for efficiency. Of course, 16-bit pointers are easy. Let's see how we can actually implement this strategy in Meta Alloc. ### Actual implementation Based on the current implementation details of Meta Alloc, we can use the following schema in practice: * Our "pointers" (indexes) are 32 bits including the highest bit that signals NULL. But given that the smallest size class is 128 bytes, which is 16 "units" in terms of index values, the lowest four bits are always zero, so there are only up to 28 meaningful bits. * Our smallest size class being 128 means that every slot (trie node) can store up to 32 indexes, which allows splitting our indexes into 5-bit words. * That means we have a maximum trie height of 6, with 2 spare bits. For larger size classes, the meaningful bit-count goes down one by one, while the bit-count of words increases one by one: * 256-byte slots: 27 bits / 6-bit words: max height 5 * 512-byte slots: 26 bits / 7-bit words: max height 4 * 1 KiB slots: 25 bits / 8-bit words: max height 4 (ugh!) * 2 KiB slots: 24 bits / 9-bit words: max height 3 The need to move entire node contents to keep the trie sorted worries me a little, but I think it should be fine. Just make sure to sort the indexes within each free-list chunk in-place before iterating through them to insert them into the trie. ### How to traverse Now that we have a sorted trie of pointers, it's relatively easy to traverse it to find contiguous sequences. Remember that we shifted our pointer values down, to erase bits which are always zero. This means every array position within every node needs to be checked for an interruption, except in the deepest level where you have to be careful not to produce a false positive, since, for example, splitting 28 bits into 5-bit words means the last level can only ever have 8 array positions occupied (from the last 3 bits) rather than the full 32. So, we do the following loop: 1. Take the lowest pointer (index) in the trie, which is the first non-NULL at the highest level. It's the start of a memory span. Begin a depth-first search. 2. Continue the search until you hit an interruption. You found the end of the current span. 3. If the span is long enough, turn it into a vacancy-list entry; otherwise turn it into free-list chunks. 4. Continue the search to find the next non-NULL pointer; it's the start of the next span. Go to step 2. ### Will I add it to Meta Alloc? No, I'm not going to implement this yet. I think it's way too much complexity for a feature that may hardly ever be needed. But it was fun to come up with, and good to know that it's possible. ### Useful to others? Can any general-purpose allocator using free-lists make use of this strategy? Yes, provided that: * Each free-list entry points to a memory slot that can hold at least two references to other slots, but preferably many more. Only two pointers per level would mean you have to split pointers into individual bits to navigate. Given 48-bit pointers, that'd mean a maximum trie height of 48. * The slots are of a known equal size, or have enough extra room to also store a size header I guess? I've not thought much about unequal slot size, since it isn't relevant to Meta Alloc, but I think it would work.