vm_map_entry_resize_free — vm map free space algorithm

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

Debian                                           August 17, 2004                     VM_MAP_ENTRY_RESIZE_FREE(9)

       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 structvm_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(logn)  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(logn) 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.

       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.

       Splay trees were added to the VM map in FreeBSD 5.0, and the O(logn) tree-based free space algorithm was
       added in FreeBSD 5.3.

       vm_map_entry_resize_free — vm map free space algorithm

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.

#include<sys/param.h>#include<vm/vm.h>#include<vm/vm_map.h>voidvm_map_entry_resize_free(vm_map_tmap, vm_map_entry_tentry);