Changeset View
Changeset View
Standalone View
Standalone View
sys/vm/vm_map.c
Show First 20 Lines • Show All 1,063 Lines • ▼ Show 20 Lines | |||||
* breaking off left and right subtrees of nodes less than, or greater than | * breaking off left and right subtrees of nodes less than, or greater than | ||||
* addr. Treat pointers to nodes with max_free < length as NULL pointers. | * addr. Treat pointers to nodes with max_free < length as NULL pointers. | ||||
* llist and rlist are the two sides in reverse order (bottom-up), with llist | * llist and rlist are the two sides in reverse order (bottom-up), with llist | ||||
* linked by the right pointer and rlist linked by the left pointer in the | * linked by the right pointer and rlist linked by the left pointer in the | ||||
* vm_map_entry, and both lists terminated by &map->header. This function, and | * vm_map_entry, and both lists terminated by &map->header. This function, and | ||||
* the subsequent call to vm_map_splay_merge, rely on the start and end address | * the subsequent call to vm_map_splay_merge, rely on the start and end address | ||||
* values in &map->header. | * values in &map->header. | ||||
*/ | */ | ||||
static vm_map_entry_t | static __always_inline vm_map_entry_t | ||||
vm_map_splay_split(vm_map_t map, vm_offset_t addr, vm_size_t length, | vm_map_splay_split(vm_map_t map, vm_offset_t addr, vm_size_t length, | ||||
vm_map_entry_t *out_llist, vm_map_entry_t *out_rlist) | vm_map_entry_t *llist, vm_map_entry_t *rlist) | ||||
{ | { | ||||
vm_map_entry_t llist, rlist, root, y; | vm_map_entry_t root, y; | ||||
llist = rlist = &map->header; | *llist = *rlist = &map->header; | ||||
root = map->root; | root = map->root; | ||||
while (root != NULL && root->max_free >= length) { | while (root != NULL && root->max_free >= length) { | ||||
KASSERT(llist->end <= root->start && root->end <= rlist->start, | KASSERT((*llist)->end <= root->start && | ||||
root->end <= (*rlist)->start, | |||||
("%s: root not within tree bounds", __func__)); | ("%s: root not within tree bounds", __func__)); | ||||
if (addr < root->start) { | if (addr < root->start) { | ||||
SPLAY_LEFT_STEP(root, y, rlist, | SPLAY_LEFT_STEP(root, y, *rlist, | ||||
y->max_free >= length && addr < y->start); | y->max_free >= length && addr < y->start); | ||||
} else if (addr >= root->end) { | } else if (addr >= root->end) { | ||||
SPLAY_RIGHT_STEP(root, y, llist, | SPLAY_RIGHT_STEP(root, y, *llist, | ||||
y->max_free >= length && addr >= y->end); | y->max_free >= length && addr >= y->end); | ||||
} else | } else | ||||
break; | break; | ||||
} | } | ||||
*out_llist = llist; | |||||
*out_rlist = rlist; | |||||
return (root); | return (root); | ||||
markj: Isn't `*found` true iff `root != NULL`? Why do we need `found` at all? | |||||
Done Inline ActionsI thought I was saving a root != NULL test and letting the break cases in LEFT_STEP/RIGHT_STEP go directly to handling the root!=NULL cases without testing. But I guess I was wrong. After stripping out 'found', I get: 17.482829 719261050 16.607015 704332901 which looks about the same. So I'll take it out. dougm: I thought I was saving a root != NULL test and letting the break cases in LEFT_STEP/RIGHT_STEP… | |||||
} | } | ||||
static void | static __always_inline void | ||||
vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *iolist) | vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *rlist) | ||||
{ | { | ||||
vm_map_entry_t rlist, y; | vm_map_entry_t hi, y; | ||||
root = root->right; | hi = root->right; | ||||
rlist = *iolist; | if (hi == NULL) | ||||
dougmAuthorUnsubmitted Done Inline ActionsI hear you ask - why not just keep this a simple while loop? Well, because it can't a simple while loop in the threaded tree, and I seek to make the final patch that switches from not-threaded to threaded to be one that can be easily understood, if I ever get there. dougm: I hear you ask - why not just keep this a simple while loop? Well, because it can't a simple… | |||||
while (root != NULL) | return; | ||||
SPLAY_LEFT_STEP(root, y, rlist, true); | do | ||||
*iolist = rlist; | SPLAY_LEFT_STEP(hi, y, *rlist, true); | ||||
while (hi != NULL); | |||||
} | } | ||||
static void | static __always_inline void | ||||
vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *iolist) | vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *llist) | ||||
{ | { | ||||
vm_map_entry_t llist, y; | vm_map_entry_t lo, y; | ||||
root = root->left; | lo = root->left; | ||||
llist = *iolist; | if (lo == NULL) | ||||
while (root != NULL) | return; | ||||
SPLAY_RIGHT_STEP(root, y, llist, true); | do | ||||
*iolist = llist; | SPLAY_RIGHT_STEP(lo, y, *llist, true); | ||||
while (lo != NULL); | |||||
} | } | ||||
static inline void | static inline void | ||||
vm_map_entry_swap(vm_map_entry_t *a, vm_map_entry_t *b) | vm_map_entry_swap(vm_map_entry_t *a, vm_map_entry_t *b) | ||||
{ | { | ||||
vm_map_entry_t tmp; | vm_map_entry_t tmp; | ||||
tmp = *b; | tmp = *b; | ||||
▲ Show 20 Lines • Show All 138 Lines • ▼ Show 20 Lines | |||||
{ | { | ||||
vm_map_entry_t llist, rlist, root, y; | vm_map_entry_t llist, rlist, root, y; | ||||
VM_MAP_ASSERT_LOCKED(map); | VM_MAP_ASSERT_LOCKED(map); | ||||
root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist); | root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist); | ||||
KASSERT(root != NULL, | KASSERT(root != NULL, | ||||
("vm_map_entry_unlink: unlink object not mapped")); | ("vm_map_entry_unlink: unlink object not mapped")); | ||||
vm_map_splay_findprev(root, &llist); | |||||
vm_map_splay_findnext(root, &rlist); | vm_map_splay_findnext(root, &rlist); | ||||
switch (op) { | if (op == UNLINK_MERGE_NEXT) { | ||||
case UNLINK_MERGE_NEXT: | |||||
rlist->start = root->start; | rlist->start = root->start; | ||||
rlist->offset = root->offset; | rlist->offset = root->offset; | ||||
y = root->left; | } | ||||
root = rlist; | |||||
rlist = root->left; | |||||
root->left = y; | |||||
break; | |||||
case UNLINK_MERGE_NONE: | |||||
vm_map_splay_findprev(root, &llist); | |||||
if (llist != &map->header) { | if (llist != &map->header) { | ||||
root = llist; | root = llist; | ||||
llist = root->right; | llist = root->right; | ||||
root->right = NULL; | root->right = NULL; | ||||
} else if (rlist != &map->header) { | } else if (rlist != &map->header) { | ||||
root = rlist; | root = rlist; | ||||
rlist = root->left; | rlist = root->left; | ||||
root->left = NULL; | root->left = NULL; | ||||
} else | } else | ||||
root = NULL; | root = NULL; | ||||
break; | |||||
} | |||||
y = entry->next; | y = entry->next; | ||||
y->prev = entry->prev; | y->prev = entry->prev; | ||||
y->prev->next = y; | y->prev->next = y; | ||||
if (root != NULL) | if (root != NULL) | ||||
vm_map_splay_merge(map, root, llist, rlist); | vm_map_splay_merge(map, root, llist, rlist); | ||||
else | else | ||||
map->root = NULL; | map->root = NULL; | ||||
VM_MAP_ASSERT_CONSISTENT(map); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
Show All 12 Lines | |||||
*/ | */ | ||||
static void | static void | ||||
vm_map_entry_resize(vm_map_t map, vm_map_entry_t entry, vm_size_t grow_amount) | vm_map_entry_resize(vm_map_t map, vm_map_entry_t entry, vm_size_t grow_amount) | ||||
{ | { | ||||
vm_map_entry_t llist, rlist, root; | vm_map_entry_t llist, rlist, root; | ||||
VM_MAP_ASSERT_LOCKED(map); | VM_MAP_ASSERT_LOCKED(map); | ||||
root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist); | root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist); | ||||
KASSERT(root != NULL, | KASSERT(root != NULL, ("%s: resize object not mapped", __func__)); | ||||
("%s: resize object not mapped", __func__)); | |||||
vm_map_splay_findnext(root, &rlist); | vm_map_splay_findnext(root, &rlist); | ||||
root->right = NULL; | root->right = NULL; | ||||
entry->end += grow_amount; | entry->end += grow_amount; | ||||
vm_map_splay_merge(map, root, llist, rlist); | vm_map_splay_merge(map, root, llist, rlist); | ||||
VM_MAP_ASSERT_CONSISTENT(map); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p", | CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p", | ||||
__func__, map, map->nentries, entry); | __func__, map, map->nentries, entry); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 3,681 Lines • Show Last 20 Lines |
Isn't *found true iff root != NULL? Why do we need found at all?