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 .Fn vm_map_entry_resize_free "vm_map_t map" "vm_map_entry_t entry"
  40 .Sh DESCRIPTION
  41 This manual page describes the
  42 .Vt vm_map_entry
  43 fields used in the VM map free space algorithm, how to maintain
  44 consistency of these variables, and the
  45 .Fn vm_map_entry_resize_free
  46 function.
  47 .Pp
  48 VM map entries are organized as both a doubly-linked list
  49 .Va ( prev
  50 and
  51 .Va next
  52 pointers) and as a binary search tree
  53 .Va ( left
  54 and
  55 .Va right
  56 pointers).
  57 The search tree is organized as a Sleator and Tarjan splay tree,
  58 also known as a
  59 .Dq "self-adjusting tree" .
  60 .Bd -literal -offset indent
  61 struct vm_map_entry {
  62         struct vm_map_entry *prev;
  63         struct vm_map_entry *next;
  64         struct vm_map_entry *left;
  65         struct vm_map_entry *right;
  66         vm_offset_t start;
  67         vm_offset_t end;
  68         vm_offset_t avail_ssize;
  69         vm_size_t adj_free;
  70         vm_size_t max_free;
  71         ...
  72 };
  73 .Ed
  74 .Pp
  75 The free space algorithm adds two fields to
  76 .Vt "struct vm_map_entry" :
  77 .Va adj_free
  78 and
  79 .Va max_free .
  80 The
  81 .Va adj_free
  82 field
  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 The
  97 .Va max_free
  98 field
  99 is the maximum amount of contiguous free space in the entry's subtree.
 100 Note that
 101 .Va max_free
 102 depends on the splay tree, not the linked list and that
 103 .Va max_free
 104 is computed by taking the maximum of its own
 105 .Va adj_free
 106 and the
 107 .Va max_free
 108 of its left and right subtrees.
 109 Again,
 110 .Va max_free
 111 is unused in the map header.
 112 .Pp
 113 These fields allow for an
 114 .Fn O "log n"
 115 implementation of
 116 .Fn vm_map_findspace .
 117 Using
 118 .Va max_free ,
 119 we can immediately test for a sufficiently large free region
 120 in an entire subtree.
 121 This makes it possible to find a first-fit free region of a given size
 122 in one pass down the tree, so
 123 .Fn O "log n"
 124 amortized using splay trees.
 125 .Pp
 126 When a free region changes size, we must update
 127 .Va adj_free
 128 and
 129 .Va max_free
 130 in the preceding map entry and propagate
 131 .Va max_free
 132 up the tree.
 133 This is handled in
 134 .Fn vm_map_entry_link
 135 and
 136 .Fn vm_map_entry_unlink
 137 for the cases of inserting and deleting an entry.
 138 Note that
 139 .Fn vm_map_entry_link
 140 updates both the new entry and the previous entry, and that
 141 .Fn vm_map_entry_unlink
 142 updates the previous entry.
 143 Also note that
 144 .Va max_free
 145 is not actually propagated up the tree.
 146 Instead, that entry is first splayed to the root and
 147 then the change is made there.
 148 This is a common technique in splay trees and is also
 149 how map entries are linked and unlinked into the tree.
 150 .Pp
 151 The
 152 .Fn vm_map_entry_resize_free
 153 function updates the free space variables in the given
 154 .Fa entry
 155 and propagates those values up the tree.
 156 This function should be called whenever a map entry is resized
 157 in-place, that is, by modifying its
 158 .Va start
 159 or
 160 .Va end
 161 values.
 162 Note that if you change
 163 .Va end ,
 164 then you should resize that entry, but if you change
 165 .Va start ,
 166 then you should resize the previous entry.
 167 The map must be locked before calling this function,
 168 and again, propagating
 169 .Va max_free
 170 is performed by splaying that entry to the root.
 171 .Sh EXAMPLES
 172 Consider adding a map entry with
 173 .Fn vm_map_insert .
 174 .Bd -literal -offset indent
 175 ret = vm_map_insert(map, object, offset, start, end, prot,
 176     max_prot, cow);
 177 .Ed
 178 .Pp
 179 In this case, no further action is required to maintain
 180 consistency of the free space variables.
 181 The
 182 .Fn vm_map_insert
 183 function calls
 184 .Fn vm_map_entry_link
 185 which updates both the new entry and the previous entry.
 186 The same would be true for
 187 .Fn vm_map_delete
 188 and for calling
 189 .Fn vm_map_entry_link
 190 or
 191 .Fn vm_map_entry_unlink
 192 directly.
 193 .Pp
 194 Now consider resizing an entry in-place without a call to
 195 .Fn vm_map_entry_link
 196 or
 197 .Fn vm_map_entry_unlink .
 198 .Bd -literal -offset indent
 199 entry->start = new_start;
 200 if (entry->prev != &map->header)
 201         vm_map_entry_resize_free(map, entry->prev);
 202 .Ed
 203 .Pp
 204 In this case, resetting
 205 .Va start
 206 changes the amount of free space following the previous entry,
 207 so we use
 208 .Fn vm_map_entry_resize_free
 209 to update the previous entry.
 210 .Pp
 211 Finally, suppose we change an entry's
 212 .Va end
 213 address.
 214 .Bd -literal -offset indent
 215 entry->end = new_end;
 216 vm_map_entry_resize_free(map, entry);
 217 .Ed
 218 .Pp
 219 Here, we call
 220 .Fn vm_map_entry_resize_free
 221 on the entry itself.
 222 .Sh SEE ALSO
 223 .Xr vm_map 9 ,
 224 .Xr vm_map_findspace 9
 225 .Rs
 226 .%A Daniel D. Sleator
 227 .%A Robert E. Tarjan
 228 .%T Self-Adjusting Binary Search Trees
 229 .%J JACM
 230 .%V vol. 32(3)
 231 .%P pp. 652-686
 232 .%D July 1985
 233 .Re
 234 .Sh HISTORY
 235 Splay trees were added to the VM map in
 236 .Fx 5.0 ,
 237 and the
 238 .Fn O "log n"
 239 tree-based free space algorithm was added in
 240 .Fx 5.3 .
 241 .Sh AUTHORS
 242 The tree-based free space algorithm and this manual page were written by
 243 .An Mark W. Krentel
 244 .Aq krentel@dreamscape.com .