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