VM_MAP_ENTRY_RESIZE_FREE(9freebsd)

💖 VM_MAP_ENTRY_RESIZE_FREE 💖

okay bestie, sit down, we're reading a Kernel Developer's Manual page for FreeBSD 9 and honestly? it's giving brainy. this is the vm_map_entry_resize_free situation, section 9, and it's all about the vm map free space algorithm. no cap. 🧚✨

---

🌸 NAME 🌸

vm_map_entry_resize_free — vm map free space algorithm

---

✨ SYNOPSIS ✨

like, include these first or nothing works, periodt:

#include <sys/param.h>
#include <vm/vm.h>
#include <vm/vm_map.h>

void
vm_map_entry_resize_free(vm_map_t map, vm_map_entry_t entry);

---

🦋 DESCRIPTION 🦋

so this page is doing three things: it explains the vm_map_entry fields that the VM map free space algorithm uses, how to keep those variables consistent (because inconsistency is not the vibe), and the vm_map_entry_resize_free() function itself. 💅

VM map entries are organized two ways at once — as a doubly-linked list (the prev and next pointers) and as a binary search tree (the left and right pointers). the search tree is organized as a Sleator and Tarjan splay tree, aka a "self-adjusting tree". main character tree energy fr.

struct vm_map_entry {
        struct vm_map_entry *prev;
        struct vm_map_entry *next;
        struct vm_map_entry *left;
        struct vm_map_entry *right;
        vm_offset_t start;
        vm_offset_t end;
        vm_offset_t avail_ssize;
        vm_size_t adj_free;
        vm_size_t max_free;
        ...
};

the free space algorithm adds two fields to struct vm_map_entry: adj_free and max_free.

• adj_free is the amount of free address space adjacent to and immediately following (higher address) the map entry. it's unused in the map header. note that adj_free depends on the linked list, not the splay tree, and it can be computed as:

entry->adj_free = (entry->next == &map->header ?
    map->max_offset : entry->next->start) - entry->end;

• max_free is the maximum amount of contiguous free space in the entry's subtree. note that max_free depends on the splay tree, not the linked list, and it's computed by taking the maximum of its own adj_free and the max_free of its left and right subtrees. again, max_free is unused in the map header.

these fields are what make an O(log n) implementation of vm_map_findspace() possible. using max_free, we can immediately test for a sufficiently large free region in an entire subtree. that means we can find a first-fit free region of a given size in one pass down the tree, so O(log n) amortized using splay trees. slay. 🔥

when a free region changes size, we gotta update adj_free and max_free in the preceding map entry and propagate max_free up the tree. this is handled in vm_map_entry_link() and vm_map_entry_unlink() for the cases of inserting and deleting an entry. heads up:

• vm_map_entry_link() updates both the new entry and the previous entry.
• vm_map_entry_unlink() updates the previous entry.

also note that max_free is not actually propagated up the tree. instead, that entry is first splayed to the root and then the change is made there. this is a common technique in splay trees, and it's also how map entries are linked and unlinked into the tree. iykyk. 🌈

the vm_map_entry_resize_free() function updates the free space variables in the given entry and propagates those values up the tree. call this function whenever a map entry is resized in-place — that is, by modifying its start or end values.

⚠️ okay this part matters: if you change end, then you should resize that entry. but if you change start, then you should resize the previous entry. 🫶

the map must be locked before calling this function. and again, propagating max_free is performed by splaying that entry to the root.

---

🎀 EXAMPLES 🎀

adding an entry

consider adding a map entry with vm_map_insert():

ret = vm_map_insert(map, object, offset, start, end, prot,
    max_prot, cow);

in this case, no further action is required to maintain consistency of the free space variables. vm_map_insert() calls vm_map_entry_link() which updates both the new entry and the previous entry. same deal would be true for vm_map_delete() and for calling vm_map_entry_link() or vm_map_entry_unlink() directly. ✨

resizing start

now consider resizing an entry in-place without a call to vm_map_entry_link() or vm_map_entry_unlink():

entry->start = new_start;
if (entry->prev != &map->header)
        vm_map_entry_resize_free(map, entry->prev);

in this case, resetting start changes the amount of free space following the previous entry, so we use vm_map_entry_resize_free() to update the previous entry. 👑

resizing end

finally, suppose we change an entry's end address:

entry->end = new_end;
vm_map_entry_resize_free(map, entry);

here, we call vm_map_entry_resize_free() on the entry itself.

---

🌟 SEE ALSO 🌟

• vm_map(9)
• vm_map_findspace(9)

Daniel D. Sleator and Robert E. Tarjan, "Self-Adjusting Binary Search Trees", JACM, vol. 32(3), pp. 652-686, July 1985.

---

💜 HISTORY 💜

Splay trees were added to the VM map in FreeBSD 5.0, and the O(log n) tree-based free space algorithm was added in FreeBSD 5.3. glow up era fr. 🌸

---

🫶 AUTHORS 🫶

the tree-based free space algorithm and this manual page were written by Mark W. Krentel <krentel@dreamscape.com>. king behavior. 👑

---

and that's the whole page bestie, you ate that 💅 this was the Debian build from August 17, 2004, VM_MAP_ENTRY_RESIZE_FREE(9) — go lock your map and resize responsibly 🎀✨