Page MenuHomeFreeBSD
Files F153681006

D13999.id38360.diff
No OneTemporary
Actions

D13999.id38360.diff
View Options

Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -898,7 +898,7 @@
{
vm_map_entry_t llist, rlist;
vm_map_entry_t ltree, rtree;
- vm_map_entry_t y;
+ vm_map_entry_t x, y;
/* Special case of empty tree. */
if (root == NULL)
@@ -914,46 +914,81 @@
*/
llist = NULL;
rlist = NULL;
- for (;;) {
- /* root is never NULL in here. */
- if (addr < root->start) {
- y = root->left;
- if (y == NULL)
- break;
- if (addr < y->start && y->left != NULL) {
- /* Rotate right and put y on rlist. */
- root->left = y->right;
- y->right = root;
- vm_map_entry_set_max_free(root);
+ do {
+ x = root;
+ /* x is never NULL in here. */
+ if (addr >= x->end) {
+ y = x->right;
+ if (y != NULL && addr >= y->end) {
+ root = y->right;
+ /* Put y on llist. */
+ y->right = llist;
+ llist = y;
+ /* Rotate left. */
+ x->right = y->left;
+ y->left = x;
+ vm_map_entry_set_max_free(x);
+ } else if (y != NULL && addr < y->start) {
root = y->left;
+ /* Put y on rlist */
y->left = rlist;
rlist = y;
+ /* Put x on llist. */
+ x->right = llist;
+ llist = x;
} else {
- /* Put root on rlist. */
- root->left = rlist;
- rlist = root;
root = y;
- }
- } else if (addr >= root->end) {
- y = root->right;
- if (y == NULL)
+ /* Put x on llist. */
+ x->right = llist;
+ llist = x;
break;
- if (addr >= y->end && y->right != NULL) {
- /* Rotate left and put y on llist. */
- root->right = y->left;
- y->left = root;
- vm_map_entry_set_max_free(root);
+ }
+ } else if (addr < x->start) {
+ y = x->left;
+ if (y != NULL && addr >= y->end) {
root = y->right;
+ /* Put y on llist. */
y->right = llist;
llist = y;
+ /* Put x on rlist. */
+ x->left = rlist;
+ rlist = x;
+ } else if (y != NULL && addr < y->start) {
+ root = y->left;
+ /* Put y on rlist. */
+ y->left = rlist;
+ rlist = y;
+ /* Rotate right. */
+ x->left = y->right;
+ y->right = x;
+ vm_map_entry_set_max_free(x);
} else {
- /* Put root on llist. */
- root->right = llist;
- llist = root;
root = y;
+ /* Put x on rlist. */
+ x->left = rlist;
+ rlist = x;
+ break;
}
} else
break;
+ } while (root != NULL);
+
+ if (root == NULL) {
+ /*
+ * With no matching node found, recover the greatest
+ * node in the left subtree and make it the root.
+ * If there is no such node, recover the least node from
+ * the right subtree.
+ */
+ if (llist != NULL) {
+ root = llist;
+ llist = root->right;
+ root->right = NULL;
+ } else {
+ root = rlist;
+ rlist = root->left;
+ root->left = NULL;
+ }
}
/*
@@ -1139,29 +1174,24 @@
return (TRUE);
} else
*entry = cur->prev;
- } else
+ } else {
/*
* Since the map is only locked for read access, perform a
* standard binary search tree lookup for "address".
*/
- for (;;) {
- if (address < cur->start) {
- if (cur->left == NULL) {
- *entry = cur->prev;
- break;
- }
+ *entry = &map->header;
+ while (cur != NULL) {
+ if (cur->end <= address) {
+ *entry = cur;
+ cur = cur->right;
+ } else if (address < cur->start) {
cur = cur->left;
- } else if (cur->end > address) {
+ } else {
*entry = cur;
return (TRUE);
- } else {
- if (cur->right == NULL) {
- *entry = cur;
- break;
- }
- cur = cur->right;
}
}
+ }
return (FALSE);
}

File Metadata

Mime Type
text/plain
Expires
Thu, Apr 23, 9:26 PM (6 h, 29 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
32045622
Default Alt Text
D13999.id38360.diff (3 KB)

Event Timeline