---
name: "vm_map_entry_resize_free"
section: "9"
platform: "linux"
package: "freebsd-manpages"
version: "6.0-5"
release: "Debian 4.0 (Etch)"
platforms: ["linux", "freebsd"]
url: "https://new.carta.tech/vm_map_entry_resize_free"
---

# vm\_map\_entry\_resize\_free(9)

vm map free space algorithm

## NAME

**vm\_map\_entry\_resize\_free** – vm map free space algorithm

## SYNOPSIS

**#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

This manual page describes the *vm\_map\_entry* fields used in the VM map free space algorithm, how to maintain consistency of these variables, and the **vm\_map\_entry\_resize\_free**() function.

VM map entries are organized as both a doubly-linked list (*prev* and *next* pointers) and as a binary search tree (*left* and *right* pointers). The search tree is organized as a Sleator and Tarjan splay tree, also known as a “self-adjusting tree”.

```
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*. The *adj\_free* field is the amount of free address space adjacent to and immediately following (higher address) the map entry. This field is unused in the map header. Note that *adj\_free* depends on the linked list, not the splay tree and that *adj\_free* can be computed as:

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

The *max\_free* field 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 that *max\_free* is 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 allow for an **O**(*log n*) implementation of **vm\_map\_findspace**(). Using *max\_free*, we can immediately test for a sufficiently large free region in an entire subtree. This makes it possible to find a first-fit free region of a given size in one pass down the tree, so **O**(*log n*) amortized using splay trees.

When a free region changes size, we must 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. Note that **vm\_map\_entry\_link**() updates both the new entry and the previous entry, and that **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 is also how map entries are linked and unlinked into the tree.

The **vm\_map\_entry\_resize\_free**() function updates the free space variables in the given *entry* and propagates those values up the tree. This function should be called whenever a map entry is resized in-place, that is, by modifying its *start* or *end* values. Note that 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

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. The **vm\_map\_insert**() function calls **vm\_map\_entry\_link**() which updates both the new entry and the previous entry. The same would be true for **vm\_map\_delete**() and for calling **vm\_map\_entry\_link**() or **vm\_map\_entry\_unlink**() directly.

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.

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/9.md), [vm\_map\_findspace(9)](/vm_map_findspace/9.md) 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.

## AUTHORS

The tree-based free space algorithm and this manual page were written by Mark W. Krentel ⟨krentel@dreamscape.com⟩.