diff options
Diffstat (limited to 'static/freebsd/man9/vm_map_entry_resize_free.9 3.html')
| -rw-r--r-- | static/freebsd/man9/vm_map_entry_resize_free.9 3.html | 176 |
1 files changed, 0 insertions, 176 deletions
diff --git a/static/freebsd/man9/vm_map_entry_resize_free.9 3.html b/static/freebsd/man9/vm_map_entry_resize_free.9 3.html deleted file mode 100644 index 11a88d84..00000000 --- a/static/freebsd/man9/vm_map_entry_resize_free.9 3.html +++ /dev/null @@ -1,176 +0,0 @@ -<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> |