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 Aq Mt krentel@dreamscape.com .
244