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