Changeset View
Standalone View
sys/vm/vm_map.c
Show First 20 Lines • Show All 1,005 Lines • ▼ Show 20 Lines | if (prior->right->start < entry->start) { | ||||
do | do | ||||
prior = prior->right; | prior = prior->right; | ||||
while (prior->right != entry); | while (prior->right != entry); | ||||
} | } | ||||
return (prior); | return (prior); | ||||
} | } | ||||
static inline vm_size_t | static inline vm_size_t | ||||
vm_size_min(vm_size_t a, vm_size_t b) | |||||
{ | |||||
return (a < b ? a : b); | |||||
} | |||||
static inline vm_size_t | |||||
vm_size_max(vm_size_t a, vm_size_t b) | vm_size_max(vm_size_t a, vm_size_t b) | ||||
{ | { | ||||
return (a > b ? a : b); | return (a > b ? a : b); | ||||
} | } | ||||
#define SPLAY_LEFT_STEP(root, y, llist, rlist, test) do { \ | #define SPLAY_LEFT_STEP(root, y, llist, rlist, test) do { \ | ||||
vm_map_entry_t z; \ | vm_map_entry_t z; \ | ||||
▲ Show 20 Lines • Show All 1,319 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 llist, new_entry, prev_entry, y; | ||||
vm_size_t max_free; | |||||
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 = entry->left; | ||||
entry->start = start; | if (prev_entry->right->start < entry->start) { | ||||
vm_map_entry_link(map, new_entry); | llist = &map->header; | ||||
do | |||||
SPLAY_RIGHT_STEP(prev_entry, y, llist, entry, true); | |||||
while (prev_entry != NULL); | |||||
vm_map_splay_merge_pred(&map->header, entry, llist); | |||||
new_entry->left = prev_entry = llist; | |||||
max_free = entry->start - prev_entry->end; | |||||
prev_entry->right = new_entry; | |||||
} else { | |||||
markj: Is it true that repeated applications of this function can result in the tree being arbitrarily… | |||||
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… | |||||
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… | |||||
entry->left = new_entry; | |||||
max_free = entry->start - prev_entry->end; | |||||
if (prev_entry->right == entry) { | |||||
max_free = vm_size_max(max_free, | |||||
vm_size_min(entry->max_free, prev_entry->max_free)); | |||||
prev_entry->right = new_entry; | |||||
} | } | ||||
} | |||||
new_entry->max_free = max_free; | |||||
new_entry->right = entry; | |||||
entry->offset += start - entry->start; | |||||
new_entry->end = entry->start = start; | |||||
map->nentries++; | |||||
} | |||||
/* | /* | ||||
* 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, rlist, y; | ||||
vm_size_t max_free; | |||||
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 = entry->right; | |||||
if (next_entry->left->start > entry->start) { | |||||
rlist = &map->header; | |||||
do | |||||
SPLAY_LEFT_STEP(next_entry, y, entry, rlist, true); | |||||
while (next_entry != NULL); | |||||
vm_map_splay_merge_succ(&map->header, entry, rlist); | |||||
new_entry->right = next_entry = rlist; | |||||
max_free = next_entry->start - entry->end; | |||||
next_entry->left = new_entry; | |||||
} else { | |||||
entry->right = new_entry; | |||||
max_free = next_entry->start - entry->end; | |||||
if (next_entry->left == entry) { | |||||
max_free = vm_size_max(max_free, | |||||
vm_size_min(entry->max_free, next_entry->max_free)); | |||||
next_entry->left = new_entry; | |||||
} | |||||
} | |||||
new_entry->max_free = max_free; | |||||
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); | map->nentries++; | ||||
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?