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
|
<table class="head">
<tr>
<td class="head-ltitle">VM_MAP_ENTRY_RESIZE_FREE(9)</td>
<td class="head-vol">Kernel Developer's Manual</td>
<td class="head-rtitle">VM_MAP_ENTRY_RESIZE_FREE(9)</td>
</tr>
</table>
<div class="manual-text">
<section class="Sh">
<h1 class="Sh" id="NAME"><a class="permalink" href="#NAME">NAME</a></h1>
<p class="Pp"><code class="Nm">vm_map_entry_resize_free</code> —
<span class="Nd">vm map free space algorithm</span></p>
</section>
<section class="Sh">
<h1 class="Sh" id="SYNOPSIS"><a class="permalink" href="#SYNOPSIS">SYNOPSIS</a></h1>
<p class="Pp"><code class="In">#include
<<a class="In">sys/param.h</a>></code>
<br/>
<code class="In">#include <<a class="In">vm/vm.h</a>></code>
<br/>
<code class="In">#include <<a class="In">vm/vm_map.h</a>></code></p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">vm_map_entry_resize_free</code>(<var class="Fa" style="white-space: nowrap;">vm_map_t
map</var>, <var class="Fa" style="white-space: nowrap;">vm_map_entry_t
entry</var>);</p>
</section>
<section class="Sh">
<h1 class="Sh" id="DESCRIPTION"><a class="permalink" href="#DESCRIPTION">DESCRIPTION</a></h1>
<p class="Pp">This manual page describes the <var class="Vt">vm_map_entry</var>
fields used in the VM map free space algorithm, how to maintain consistency
of these variables, and the
<a class="permalink" href="#vm_map_entry_resize_free"><code class="Fn" id="vm_map_entry_resize_free">vm_map_entry_resize_free</code></a>()
function.</p>
<p class="Pp">VM map entries are organized as both a doubly-linked list
(<var class="Va">prev</var> and <var class="Va">next</var> pointers) and as
a binary search tree (<var class="Va">left</var> and
<var class="Va">right</var> pointers). The search tree is organized as a
Sleator and Tarjan splay tree, also known as a “self-adjusting
tree”.</p>
<div class="Bd Pp Bd-indent Li">
<pre>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;
...
};</pre>
</div>
<p class="Pp">The free space algorithm adds two fields to <var class="Vt">struct
vm_map_entry</var>: <var class="Va">adj_free</var> and
<var class="Va">max_free</var>. The <var class="Va">adj_free</var> 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 <var class="Va">adj_free</var> depends on the linked list, not the
splay tree and that <var class="Va">adj_free</var> can be computed as:</p>
<div class="Bd Pp Bd-indent Li">
<pre>entry->adj_free = (entry->next == &map->header ?
map->max_offset : entry->next->start) - entry->end;</pre>
</div>
<p class="Pp">The <var class="Va">max_free</var> field is the maximum amount of
contiguous free space in the entry's subtree. Note that
<var class="Va">max_free</var> depends on the splay tree, not the linked
list and that <var class="Va">max_free</var> is computed by taking the
maximum of its own <var class="Va">adj_free</var> and the
<var class="Va">max_free</var> of its left and right subtrees. Again,
<var class="Va">max_free</var> is unused in the map header.</p>
<p class="Pp" id="O">These fields allow for an
<a class="permalink" href="#O"><code class="Fn">O</code></a>(<var class="Fa">log
n</var>) implementation of
<a class="permalink" href="#vm_map_findspace"><code class="Fn" id="vm_map_findspace">vm_map_findspace</code></a>().
Using <var class="Va">max_free</var>, 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 <code class="Fn">O</code>(<var class="Fa">log n</var>) amortized using
splay trees.</p>
<p class="Pp" id="vm_map_entry_link">When a free region changes size, we must
update <var class="Va">adj_free</var> and <var class="Va">max_free</var> in
the preceding map entry and propagate <var class="Va">max_free</var> up the
tree. This is handled in
<a class="permalink" href="#vm_map_entry_link"><code class="Fn">vm_map_entry_link</code></a>()
and
<a class="permalink" href="#vm_map_entry_unlink"><code class="Fn" id="vm_map_entry_unlink">vm_map_entry_unlink</code></a>()
for the cases of inserting and deleting an entry. Note that
<code class="Fn">vm_map_entry_link</code>() updates both the new entry and
the previous entry, and that <code class="Fn">vm_map_entry_unlink</code>()
updates the previous entry. Also note that <var class="Va">max_free</var> 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.</p>
<p class="Pp" id="vm_map_entry_resize_free~2">The
<a class="permalink" href="#vm_map_entry_resize_free~2"><code class="Fn">vm_map_entry_resize_free</code></a>()
function updates the free space variables in the given
<var class="Fa">entry</var> 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 <var class="Va">start</var> or <var class="Va">end</var>
values. Note that if you change <var class="Va">end</var>, then you should
resize that entry, but if you change <var class="Va">start</var>, then you
should resize the previous entry. The map must be locked before calling this
function, and again, propagating <var class="Va">max_free</var> is performed
by splaying that entry to the root.</p>
</section>
<section class="Sh">
<h1 class="Sh" id="EXAMPLES"><a class="permalink" href="#EXAMPLES">EXAMPLES</a></h1>
<p class="Pp">Consider adding a map entry with
<code class="Fn">vm_map_insert</code>().</p>
<div class="Bd Pp Bd-indent Li">
<pre>ret = vm_map_insert(map, object, offset, start, end, prot,
max_prot, cow);</pre>
</div>
<p class="Pp">In this case, no further action is required to maintain
consistency of the free space variables. The
<code class="Fn">vm_map_insert</code>() function calls
<code class="Fn">vm_map_entry_link</code>() which updates both the new entry
and the previous entry. The same would be true for
<code class="Fn">vm_map_delete</code>() and for calling
<code class="Fn">vm_map_entry_link</code>() or
<code class="Fn">vm_map_entry_unlink</code>() directly.</p>
<p class="Pp">Now consider resizing an entry in-place without a call to
<code class="Fn">vm_map_entry_link</code>() or
<code class="Fn">vm_map_entry_unlink</code>().</p>
<div class="Bd Pp Bd-indent Li">
<pre>entry->start = new_start;
if (entry->prev != &map->header)
vm_map_entry_resize_free(map, entry->prev);</pre>
</div>
<p class="Pp">In this case, resetting <var class="Va">start</var> changes the
amount of free space following the previous entry, so we use
<code class="Fn">vm_map_entry_resize_free</code>() to update the previous
entry.</p>
<p class="Pp">Finally, suppose we change an entry's <var class="Va">end</var>
address.</p>
<div class="Bd Pp Bd-indent Li">
<pre>entry->end = new_end;
vm_map_entry_resize_free(map, entry);</pre>
</div>
<p class="Pp">Here, we call <code class="Fn">vm_map_entry_resize_free</code>()
on the entry itself.</p>
</section>
<section class="Sh">
<h1 class="Sh" id="SEE_ALSO"><a class="permalink" href="#SEE_ALSO">SEE
ALSO</a></h1>
<p class="Pp"><a class="Xr">vm_map(9)</a>,
<a class="Xr">vm_map_findspace(9)</a></p>
<p class="Pp"><cite class="Rs"><span class="RsA">Daniel D. Sleator</span> and
<span class="RsA">Robert E. Tarjan</span>, <span class="RsT">Self-Adjusting
Binary Search Trees</span>, <i class="RsJ">JACM</i>, <span class="RsV">vol.
32(3)</span>, <span class="RsP">pp. 652-686</span>, <span class="RsD">July
1985</span>.</cite></p>
</section>
<section class="Sh">
<h1 class="Sh" id="HISTORY"><a class="permalink" href="#HISTORY">HISTORY</a></h1>
<p class="Pp">Splay trees were added to the VM map in <span class="Ux">FreeBSD
5.0</span>, and the <code class="Fn">O</code>(<var class="Fa">log n</var>)
tree-based free space algorithm was added in <span class="Ux">FreeBSD
5.3</span>.</p>
</section>
<section class="Sh">
<h1 class="Sh" id="AUTHORS"><a class="permalink" href="#AUTHORS">AUTHORS</a></h1>
<p class="Pp">The tree-based free space algorithm and this manual page were
written by <span class="An">Mark W. Krentel</span>
<<a class="Mt" href="mailto:krentel@dreamscape.com">krentel@dreamscape.com</a>>.</p>
</section>
</div>
<table class="foot">
<tr>
<td class="foot-date">August 17, 2004</td>
<td class="foot-os">FreeBSD 15.0</td>
</tr>
</table>
|
