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