Skip site navigation (1)Skip section navigation (2)

FreeBSD Man Pages

Man Page or Keyword Search:
Man Architecture
Apropos Keyword Search (all sections) Output format
home | help
VM_MAP_ENTRY_RESIZE... FreeBSD Kernel Developer's ManualVM_MAP_ENTRY_RESIZE...

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)	amor-
     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 han-
     dled 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 func-
     tion 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_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.

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

FreeBSD	10.1			August 17, 2004			  FreeBSD 10.1

NAME | SYNOPSIS | DESCRIPTION | EXAMPLES | SEE ALSO | HISTORY | AUTHORS

Want to link to this manual page? Use this URL:
<http://www.freebsd.org/cgi/man.cgi?query=vm_map_entry_resize_free&sektion=9&manpath=FreeBSD+10.0-RELEASE>

home | help