Changeset View
Standalone View
sys/vm/vm_map.c
Context not available. | |||||
static inline void | static inline void | ||||
vm_map_entry_set_max_free(vm_map_entry_t entry) | vm_map_entry_set_max_free(vm_map_entry_t entry) | ||||
{ | { | ||||
vm_size_t max_left, max_right; | |||||
entry->max_free = entry->adj_free; | max_left = (entry->left != NULL) ? entry->left->max_free : | ||||
if (entry->left != NULL && entry->left->max_free > entry->max_free) | entry->start - entry->prev->end; | ||||
entry->max_free = entry->left->max_free; | max_right = (entry->right != NULL) ? entry->right->max_free : | ||||
if (entry->right != NULL && entry->right->max_free > entry->max_free) | entry->next->start - entry->end; | ||||
entry->max_free = entry->right->max_free; | entry->max_free = MAX(max_left, max_right); | ||||
} | } | ||||
/* | /* | ||||
kib: The split and merge in the name of this function and the function below refer to the llist and… | |||||
Done Inline ActionsThe split function divides the tree into an llist of nodes less than addr, an rlist of nodes greater than addr, and a root (possibly NULL) that contains addr, with left and right children less than and greater than addr. I'm trying to follow convention with the naming. I don't object to dropping 'entry' from the names of the new functions, if that's what people want. dougm: The split function divides the tree into an llist of nodes less than addr, an rlist of nodes… | |||||
Context not available. | |||||
entry->right = after_where->right; | entry->right = after_where->right; | ||||
entry->left = after_where; | entry->left = after_where; | ||||
after_where->right = NULL; | after_where->right = NULL; | ||||
after_where->adj_free = entry->start - after_where->end; | |||||
vm_map_entry_set_max_free(after_where); | vm_map_entry_set_max_free(after_where); | ||||
} else { | } else { | ||||
entry->right = map->root; | entry->right = map->root; | ||||
entry->left = NULL; | entry->left = NULL; | ||||
} | } | ||||
entry->adj_free = entry->next->start - entry->end; | |||||
vm_map_entry_set_max_free(entry); | vm_map_entry_set_max_free(entry); | ||||
map->root = entry; | map->root = entry; | ||||
} | } | ||||
Context not available. | |||||
else { | else { | ||||
root = vm_map_entry_splay(entry->start, entry->left); | root = vm_map_entry_splay(entry->start, entry->left); | ||||
root->right = entry->right; | root->right = entry->right; | ||||
root->adj_free = entry->next->start - root->end; | |||||
vm_map_entry_set_max_free(root); | vm_map_entry_set_max_free(root); | ||||
} | } | ||||
map->root = root; | map->root = root; | ||||
Context not available. | |||||
if (entry != map->root) | if (entry != map->root) | ||||
map->root = vm_map_entry_splay(entry->start, map->root); | map->root = vm_map_entry_splay(entry->start, map->root); | ||||
entry->adj_free = entry->next->start - entry->end; | |||||
vm_map_entry_set_max_free(entry); | vm_map_entry_set_max_free(entry); | ||||
} | } | ||||
Done Inline ActionsWhy do you need two switches ? I.e, why cannot the code from the second switch cases go straight into the cases of the first switch ? I understand that you do separate llist/rlists and root calculations, but I do not quite get the separation. kib: Why do you need two switches ? I.e, why cannot the code from the second switch cases go… | |||||
Done Inline ActionsI can get by with only one switch, but then a have to duplicate each of the three-line code snippets that start with resetting the new root value. Note that the NONE case in the first switch is likely to alter the value of 'op', so that some other case is taken in the second switch. dougm: I can get by with only one switch, but then a have to duplicate each of the three-line code… | |||||
Context not available. | |||||
* Find the first fit (lowest VM address) for "length" free bytes | * Find the first fit (lowest VM address) for "length" free bytes | ||||
* beginning at address >= start in the given map. | * beginning at address >= start in the given map. | ||||
* | * | ||||
* In a vm_map_entry, "adj_free" is the amount of free space | * In a vm_map_entry, "max_free" is the maximum amount of | ||||
* adjacent (higher address) to this entry, and "max_free" is the | * contiguous free space between an entry in its subtree and a | ||||
* maximum amount of contiguous free space in its subtree. This | * neighbor of that entry. This allows finding a free region in | ||||
* allows finding a free region in one path down the tree, so | * one path down the tree, so O(log n) amortized with splay | ||||
* O(log n) amortized with splay trees. | * trees. | ||||
* | * | ||||
* The map must be locked, and leaves it so. | * The map must be locked, and leaves it so. | ||||
* | * | ||||
Context not available. | |||||
* wrap might be a problem. | * wrap might be a problem. | ||||
*/ | */ | ||||
st = (start > map->root->end) ? start : map->root->end; | st = (start > map->root->end) ? start : map->root->end; | ||||
if (length <= map->root->end + map->root->adj_free - st) { | if (length <= map->root->next->start - st) { | ||||
*addr = st; | *addr = st; | ||||
return (0); | return (0); | ||||
} | } | ||||
Context not available. | |||||
while (entry != NULL) { | while (entry != NULL) { | ||||
if (entry->left != NULL && entry->left->max_free >= length) | if (entry->left != NULL && entry->left->max_free >= length) | ||||
entry = entry->left; | entry = entry->left; | ||||
else if (entry->adj_free >= length) { | else if (entry->left == NULL && | ||||
*addr = entry->end; | entry->start - entry->prev->end >= length) { | ||||
*addr = entry->prev->end; | |||||
return (0); | return (0); | ||||
} else | } else if (entry->right != NULL) | ||||
entry = entry->right; | entry = entry->right; | ||||
else { | |||||
*addr = entry->end; | |||||
return (0); | |||||
} | |||||
} | } | ||||
/* Can't get here, so panic if we do. */ | /* Can't get here, so panic if we do. */ | ||||
Context not available. | |||||
Done Inline ActionsPerhaps change the return type of the function to bool ? It got almost complete rewrite anyway. kib: Perhaps change the return type of the function to bool ? It got almost complete rewrite anyway. | |||||
Done Inline ActionsIf we're talking about changing the interface, how would you feel about changing the return type to vm_offset_t, eliminating the addr parameter, returning the addr, and returning the vm_map_max value for the failure case? dougm: If we're talking about changing the interface, how would you feel about changing the return… |
The split and merge in the name of this function and the function below refer to the llist and rlist, and not to the split of some entry ? It sounds strange to name them vm_map_entry_something.