share/man/man9/vm_map_entry_resize_free.9

   1 .\"
   2 .\" Copyright (c) 2004 Mark W. Krentel <krentel@dreamscape.com>
   3 .\" All rights reserved.
   4 .\"
   5 .\" Redistribution and use in source and binary forms, with or without
   6 .\" modification, are permitted provided that the following conditions
   7 .\" are met:
   8 .\" 1. Redistributions of source code must retain the above copyright
   9 .\"    notice, this list of conditions and the following disclaimer.
  10 .\" 2. Redistributions in binary form must reproduce the above copyright
  11 .\"    notice, this list of conditions and the following disclaimer in the
  12 .\"    documentation and/or other materials provided with the distribution.
  13 .\"
  14 .\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24 .\" SUCH DAMAGE.
  25 .\"
  26 .\" $FreeBSD$
  27 .\"
  28 .Dd August 17, 2004
  29 .Os
  30 .Dt VM_MAP_ENTRY_RESIZE_FREE 9
  31 .Sh NAME
  32 .Nm vm_map_entry_resize_free
  33 .Nd vm map free space algorithm
  34 .Sh SYNOPSIS
  35 .In sys/param.h
  36 .In vm/vm.h
  37 .In vm/vm_map.h
  38 .Ft void
  39 .Fo vm_map_entry_resize_free
  40 .Fa "vm_map_t map" "vm_map_entry_t entry"
  41 .Fc
  42 .Sh DESCRIPTION
  43 This manual page describes the
  44 .Vt vm_map_entry
  45 fields used in the VM map free space algorithm, how to maintain
  46 consistency of these variables, and the
  47 .Fn vm_map_entry_resize_free
  48 function.
  49 .Pp
  50 VM map entries are organized as both a doubly-linked list
  51 .Va ( prev
  52 and
  53 .Va next
  54 pointers) and as a binary search tree
  55 .Va ( left
  56 and
  57 .Va right
  58 pointers).
  59 The search tree is organized as a Sleator and Tarjan splay tree,
  60 also known as a
  61 .Dq self-adjusting tree.
  62 .Bd -literal -offset indent
  63 struct vm_map_entry {
  64         struct vm_map_entry *prev;
  65         struct vm_map_entry *next;
  66         struct vm_map_entry *left;
  67         struct vm_map_entry *right;
  68         vm_offset_t start;
  69         vm_offset_t end;
  70         vm_offset_t avail_ssize;
  71         vm_size_t adj_free;
  72         vm_size_t max_free;
  73         ...
  74 };
  75 .Ed
  76 .Pp
  77 The free space algorithm adds two fields to
  78 .Vt struct vm_map_entry :
  79 .Va adj_free
  80 and
  81 .Va max_free .
  82 .Va adj_free
  83 is the amount of free address space adjacent to and immediately
  84 following (higher address) the map entry.
  85 This field is unused in the map header.
  86 Note that
  87 .Va adj_free
  88 depends on the linked list, not the splay tree and that
  89 .Va adj_free
  90 can be computed as:
  91 .Bd -literal -offset indent
  92 entry->adj_free = (entry->next == &map->header ?
  93     map->max_offset : entry->next->start) - entry->end;
  94 .Ed
  95 .Pp
  96 .Va max_free
  97 is the maximum amount of contiguous free space in the entry's subtree.
  98 Note that
  99 .Va max_free
 100 depends on the splay tree, not the linked list and that
 101 .Va max_free
 102 is computed by taking the maximum of its own
 103 .Va adj_free
 104 and the
 105 .Va max_free
 106 of its left and right subtrees.
 107 Again,
 108 .Va max_free
 109 is unused in the map header.
 110 .Pp
 111 These fields allow for an O(log\~n) implementation of
 112 .Fn vm_map_findspace .
 113 Using
 114 .Va max_free ,
 115 we can immediately test for a sufficiently large free region
 116 in an entire subtree.
 117 This makes it possible to find a first-fit free region of a given size
 118 in one pass down the tree, so O(log\~n) amortized using splay trees.
 119 .Pp
 120 When a free region changes size, we must update
 121 .Va adj_free
 122 and
 123 .Va max_free
 124 in the preceding map entry and propagate
 125 .Va max_free
 126 up the tree.
 127 This is handled in
 128 .Fn vm_map_entry_link
 129 and
 130 .Fn vm_map_entry_unlink
 131 for the cases of inserting and deleting an entry.
 132 Note that
 133 .Fn vm_map_entry_link
 134 updates both the new entry and the previous entry, and that
 135 .Fn vm_map_entry_unlink
 136 updates the previous entry.
 137 Also note that
 138 .Va max_free
 139 is not actually propagated up the tree.
 140 Instead, that entry is first splayed to the root and
 141 then the change is made there.
 142 This is a common technique in splay trees and is also
 143 how map entries are linked and unlinked into the tree.
 144 .Pp
 145 The
 146 .Fn vm_map_entry_resize_free
 147 function updates the free space variables in the given
 148 .Fa entry
 149 and propagates those values up the tree.
 150 This function should be called whenever a map entry is resized
 151 in-place, that is, by modifying its
 152 .Va start
 153 or
 154 .Va end
 155 values.
 156 Note that if you change
 157 .Va end ,
 158 then you should resize that entry, but if you change
 159 .Va start ,
 160 then you should resize the previous entry.
 161 The map must be locked before calling this function,
 162 and again, propagating
 163 .Va max_free
 164 is performed by splaying that entry to the root.
 165 .Sh EXAMPLES
 166 Consider adding a map entry with
 167 .Fn vm_map_insert .
 168 .Bd -literal -offset indent
 169 ret = vm_map_insert(map, object, offset, start, end, prot,
 170     max_prot, cow);
 171 .Ed
 172 .Pp
 173 In this case, no further action is required to maintain
 174 consistency of the free space variables.
 175 .Fn vm_map_insert
 176 calls
 177 .Fn vm_map_entry_link
 178 which updates both the new entry and the previous entry.
 179 The same would be true for
 180 .Fn vm_map_delete
 181 and for calling
 182 .Fn vm_map_entry_link
 183 or
 184 .Fn vm_map_entry_unlink
 185 directly.
 186 .Pp
 187 Now consider resizing an entry in-place without a call to
 188 .Fn vm_map_entry_link
 189 or
 190 .Fn vm_map_entry_unlink .
 191 .Bd -literal -offset indent
 192 entry->start = new_start;
 193 if (entry->prev != &map->header)
 194         vm_map_entry_resize_free(map, entry->prev);
 195 .Ed
 196 .Pp
 197 In this case, resetting
 198 .Va start
 199 changes the amount of free space following the previous entry,
 200 so we use
 201 .Fn vm_map_entry_resize_free
 202 to update the previous entry.
 203 .Pp
 204 Finally, suppose we change an entry's
 205 .Va end
 206 address.
 207 .Bd -literal -offset indent
 208 entry->end = new_end;
 209 vm_map_entry_resize_free(map, entry);
 210 .Ed
 211 .Pp
 212 Here, we call
 213 .Fn vm_map_entry_resize_free
 214 on the entry itself.
 215 .Sh SEE ALSO
 216 .Xr vm_map 9 ,
 217 .Xr vm_map_findspace 9
 218 .Rs
 219 .%A Daniel D. Sleator
 220 .%A Robert E. Tarjan
 221 .%T Self-Adjusting Binary Search Trees
 222 .%J JACM
 223 .%V vol. 32(3)
 224 .%P pp. 652-686
 225 .%D July 1985
 226 .Re
 227 .Sh HISTORY
 228 Splay trees were added to the VM map in FreeBSD 5.0, and the
 229 O(log\~n) tree-based free space algorithm was added in FreeBSD 5.3.
 230 .Sh AUTHORS
 231 The tree-based free space algorithm and this manual page were written by
 232 .An Mark W. Krentel
 233 .Aq krentel@dreamscape.com .