vm_map_entry_resize_free(9)

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 point

ers). 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 ad

dress 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) - en

try->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 max

imum of its
own adj_free and the max_free of its left and right sub

trees. 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

tized 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 tech

nique 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 con

sistency 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 it

self.

SEE ALSO

vm_map(9), vm_map_findspace(9)

Daniel D. Sleator and Robert E. Tarjan, "Self-Adjusting Bi

nary 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

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>.

BSD August 17, 2004

BSD