Changeset View
Standalone View
sys/vm/vm_map.c
Show First 20 Lines • Show All 2,340 Lines • ▼ Show 20 Lines | |||||
/* | /* | ||||
* This routine is called only when it is known that | * This routine is called only when it is known that | ||||
* the entry must be split. | * the entry must be split. | ||||
*/ | */ | ||||
static void | static void | ||||
_vm_map_clip_start(vm_map_t map, vm_map_entry_t entry, vm_offset_t start) | _vm_map_clip_start(vm_map_t map, vm_map_entry_t entry, vm_offset_t start) | ||||
{ | { | ||||
vm_map_entry_t new_entry; | vm_map_entry_t new_entry, prev_entry; | ||||
VM_MAP_ASSERT_LOCKED(map); | VM_MAP_ASSERT_LOCKED(map); | ||||
KASSERT(entry->end > start && entry->start < start, | KASSERT(entry->end > start && entry->start < start, | ||||
("_vm_map_clip_start: invalid clip of entry %p", entry)); | ("_vm_map_clip_start: invalid clip of entry %p", entry)); | ||||
new_entry = vm_map_entry_clone(map, entry); | |||||
/* | /* | ||||
* Split off the front portion. Insert the new entry BEFORE this one, | * Split off the front portion. Insert the new entry BEFORE this one, | ||||
* so that this entry has the specified starting address. | * so that this entry has the specified starting address. | ||||
*/ | */ | ||||
new_entry->end = start; | new_entry = vm_map_entry_clone(map, entry); | ||||
entry->offset += (start - entry->start); | prev_entry = vm_map_entry_pred(entry); | ||||
entry->start = start; | if (prev_entry->right == entry) | ||||
vm_map_entry_link(map, new_entry); | prev_entry->right = new_entry; | ||||
if (entry->left == prev_entry) | |||||
entry->left = new_entry; | |||||
else | |||||
new_entry->left = prev_entry; | |||||
new_entry->right = entry; | |||||
entry->offset += start - entry->start; | |||||
new_entry->end = entry->start = start; | |||||
new_entry->max_free = new_entry->start - prev_entry->end; | |||||
markj: Is it true that repeated applications of this function can result in the tree being arbitrarily… | |||||
dougmAuthorUnsubmitted Done Inline ActionsYes. Yes. If you have a single entry with start==0 and end ==100, and clip at 1, 2, 3, ... 99, then you end up with a left-leaning linear list of 100 entries, before this change and after as well. Splaying doesn't guarantee a balanced tree, but only that an operation that takes more than log n work will improve the balance of the tree. These 99 operations would each take constant work, independent of tree size, and so could make the tree more unbalanced. dougm: Yes. Yes.
If you have a single entry with start==0 and end ==100, and clip at 1, 2, 3, ... 99… | |||||
dougmAuthorUnsubmitted Done Inline ActionsTo judge this change in the harshest possible light, I can see that in a series of clip_start operations, the time spend on looking up the predecessor of the same node over and over could grow linearly. [100:200] [0:1] [1:2] Clipping at 101, 102, ... would build a long chain of right children from [1:2], and each succeeding predecessor operation would have to walk the longer chain. So that might be a reason to reject this. I'll develop a version that avoids this with a splay and still achieves my purpose of not corrupting the splay tree (by changing values of start, end) before searching it. dougm: To judge this change in the harshest possible light, I can see that in a series of clip_start… | |||||
} | } | ||||
/* | /* | ||||
* vm_map_clip_end: [ internal use only ] | * vm_map_clip_end: [ internal use only ] | ||||
* | * | ||||
* Asserts that the given entry ends at or before | * Asserts that the given entry ends at or before | ||||
* the specified address; if necessary, | * the specified address; if necessary, | ||||
* it splits the entry into two. | * it splits the entry into two. | ||||
*/ | */ | ||||
#define vm_map_clip_end(map, entry, endaddr) \ | #define vm_map_clip_end(map, entry, endaddr) \ | ||||
{ \ | { \ | ||||
if ((endaddr) < (entry->end)) \ | if ((endaddr) < (entry->end)) \ | ||||
_vm_map_clip_end((map), (entry), (endaddr)); \ | _vm_map_clip_end((map), (entry), (endaddr)); \ | ||||
} | } | ||||
/* | /* | ||||
* This routine is called only when it is known that | * This routine is called only when it is known that | ||||
* the entry must be split. | * the entry must be split. | ||||
*/ | */ | ||||
static void | static void | ||||
_vm_map_clip_end(vm_map_t map, vm_map_entry_t entry, vm_offset_t end) | _vm_map_clip_end(vm_map_t map, vm_map_entry_t entry, vm_offset_t end) | ||||
{ | { | ||||
vm_map_entry_t new_entry; | vm_map_entry_t next_entry, new_entry; | ||||
VM_MAP_ASSERT_LOCKED(map); | VM_MAP_ASSERT_LOCKED(map); | ||||
KASSERT(entry->start < end && entry->end > end, | KASSERT(entry->start < end && entry->end > end, | ||||
("_vm_map_clip_end: invalid clip of entry %p", entry)); | ("_vm_map_clip_end: invalid clip of entry %p", entry)); | ||||
new_entry = vm_map_entry_clone(map, entry); | |||||
/* | /* | ||||
* Split off the back portion. Insert the new entry AFTER this one, | * Split off the back portion. Insert the new entry AFTER this one, | ||||
* so that this entry has the specified ending address. | * so that this entry has the specified ending address. | ||||
*/ | */ | ||||
new_entry = vm_map_entry_clone(map, entry); | |||||
next_entry = vm_map_entry_succ(entry); | |||||
if (next_entry->left == entry) | |||||
next_entry->left = new_entry; | |||||
if (entry->right == next_entry) | |||||
entry->right = new_entry; | |||||
else | |||||
new_entry->right = next_entry; | |||||
new_entry->left = entry; | |||||
new_entry->offset += end - entry->start; | |||||
new_entry->start = entry->end = end; | new_entry->start = entry->end = end; | ||||
new_entry->offset += (end - entry->start); | new_entry->max_free = next_entry->start - new_entry->end; | ||||
vm_map_entry_link(map, new_entry); | |||||
} | } | ||||
/* | /* | ||||
* vm_map_submap: [ kernel use only ] | * vm_map_submap: [ kernel use only ] | ||||
* | * | ||||
* Mark the given range as handled by a subordinate map. | * Mark the given range as handled by a subordinate map. | ||||
* | * | ||||
* This range must have been created with vm_map_find, | * This range must have been created with vm_map_find, | ||||
▲ Show 20 Lines • Show All 2,754 Lines • Show Last 20 Lines |
Is it true that repeated applications of this function can result in the tree being arbitrarily imbalanced? Was that true before?