Партнёры:
Хостинг:
vm_map_entry_resize_free - vm map free space algorithm
VM map entries are organized as both a doubly-linked list ( prev and next pointers) and as a binary search tree ( left and right pointers). The search tree is organized as a Sleator and Tarjan splay tree, also known as a ``self-adjusting tree''
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;
...
};
The free space algorithm adds two fields to Vt struct vm_map_entry : adj_free and max_free The 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 adj_free depends on the linked list, not the splay tree and that adj_free can be computed as:
entry->adj_free = (entry->next == &map->header ?
map->max_offset : entry->next->start) - entry->end;
The max_free field is the maximum amount of contiguous free space in the entry's subtree. Note that max_free depends on the splay tree, not the linked list and that max_free is computed by taking the maximum of its own adj_free and the max_free of its left and right subtrees. Again, max_free is unused in the map header.
These fields allow for an
O (log n);
implementation of
vm_map_findspace (.);
Using
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
O (log n);
amortized using splay trees.
When a free region changes size, we must update
adj_free
and
max_free
in the preceding map entry and propagate
max_free
up the tree.
This is handled in
vm_map_entry_link ();
and
vm_map_entry_unlink ();
for the cases of inserting and deleting an entry.
Note that
vm_map_entry_link ();
updates both the new entry and the previous entry, and that
vm_map_entry_unlink ();
updates the previous entry.
Also note that
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.
The
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
start
or
end
values.
Note that if you change
end
then you should resize that entry, but if you change
start
then you should resize the previous entry.
The map must be locked before calling this function,
and again, propagating
max_free
is performed by splaying that entry to the root.
ret = vm_map_insert(map, object, offset, start, end, prot,
max_prot, cow);
In this case, no further action is required to maintain
consistency of the free space variables.
The
vm_map_insert ();
function calls
vm_map_entry_link ();
which updates both the new entry and the previous entry.
The same would be true for
vm_map_delete ();
and for calling
vm_map_entry_link ();
or
vm_map_entry_unlink ();
directly.
Now consider resizing an entry in-place without a call to
vm_map_entry_link ();
or
vm_map_entry_unlink (.);
entry->start = new_start;
if (entry->prev != &map->header)
vm_map_entry_resize_free(map, entry->prev);
In this case, resetting
start
changes the amount of free space following the previous entry,
so we use
vm_map_entry_resize_free ();
to update the previous entry.
Finally, suppose we change an entry's end address.
entry->end = new_end; vm_map_entry_resize_free(map, entry);
Here, we call
vm_map_entry_resize_free ();
on the entry itself.
|
Закладки на сайте Проследить за страницей |
Created 1996-2024 by Maxim Chirkov Добавить, Поддержать, Вебмастеру |