Lines Matching refs:root
821 return (msleep(&map->root, &map_sleep_mtx, PDROP | PVM, "vmmaps",
842 wakeup(&map->root);
902 map->root = NULL;
990 * one the root of a tree and the other the ancestor of that root
994 vm_map_entry_max_free_left(vm_map_entry_t root, vm_map_entry_t left_ancestor)
997 return (root->left != left_ancestor ?
998 root->left->max_free : root->start - left_ancestor->end);
1002 vm_map_entry_max_free_right(vm_map_entry_t root, vm_map_entry_t right_ancestor)
1005 return (root->right != right_ancestor ?
1006 root->right->max_free : right_ancestor->start - root->end);
1037 #define SPLAY_LEFT_STEP(root, y, llist, rlist, test) do { \
1042 * Infer root->right->max_free == root->max_free when \
1043 * y->max_free < root->max_free || root->max_free == 0. \
1046 y = root->left; \
1047 max_free = root->max_free; \
1049 vm_map_entry_max_free_left(root, llist), \
1050 vm_map_entry_max_free_right(root, rlist)), \
1052 if (max_free - 1 < vm_map_entry_max_free_left(root, llist)) \
1053 max_free = vm_map_entry_max_free_right(root, rlist); \
1055 /* Rotate right and make y root. */ \
1057 if (z != root) { \
1058 root->left = z; \
1059 y->right = root; \
1061 root->max_free = max_free = \
1064 root->max_free = max_free = \
1065 vm_size_max(max_free, root->start - y->end);\
1066 root = y; \
1067 y = root->left; \
1069 /* Copy right->max_free. Put root on rlist. */ \
1070 root->max_free = max_free; \
1071 KASSERT(max_free == vm_map_entry_max_free_right(root, rlist), \
1073 root->left = rlist; \
1074 rlist = root; \
1075 root = y != llist ? y : NULL; \
1078 #define SPLAY_RIGHT_STEP(root, y, llist, rlist, test) do { \
1083 * Infer root->left->max_free == root->max_free when \
1084 * y->max_free < root->max_free || root->max_free == 0. \
1087 y = root->right; \
1088 max_free = root->max_free; \
1090 vm_map_entry_max_free_left(root, llist), \
1091 vm_map_entry_max_free_right(root, rlist)), \
1093 if (max_free - 1 < vm_map_entry_max_free_right(root, rlist)) \
1094 max_free = vm_map_entry_max_free_left(root, llist); \
1096 /* Rotate left and make y root. */ \
1098 if (z != root) { \
1099 root->right = z; \
1100 y->left = root; \
1102 root->max_free = max_free = \
1105 root->max_free = max_free = \
1106 vm_size_max(max_free, y->start - root->end);\
1107 root = y; \
1108 y = root->right; \
1110 /* Copy left->max_free. Put root on llist. */ \
1111 root->max_free = max_free; \
1112 KASSERT(max_free == vm_map_entry_max_free_left(root, llist), \
1114 root->right = llist; \
1115 llist = root; \
1116 root = y != rlist ? y : NULL; \
1122 * subtrees with root->max_free < length as empty trees. llist and rlist are
1133 vm_map_entry_t left, right, root, y;
1136 root = map->root;
1137 while (root != NULL && root->max_free >= length) {
1138 KASSERT(left->end <= root->start &&
1139 root->end <= right->start,
1140 ("%s: root not within tree bounds", __func__));
1141 if (addr < root->start) {
1142 SPLAY_LEFT_STEP(root, y, left, right,
1144 } else if (addr >= root->end) {
1145 SPLAY_RIGHT_STEP(root, y, left, right,
1152 return (root);
1156 vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *rlist)
1161 hi = root->right == right ? NULL : root->right;
1165 SPLAY_LEFT_STEP(hi, y, root, right, true);
1171 vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *llist)
1176 lo = root->left == left ? NULL : root->left;
1180 SPLAY_RIGHT_STEP(lo, y, left, root, true);
1197 * subtrees of the root go at the bottom of llist and rlist.
1200 vm_map_splay_merge_left_walk(vm_map_entry_t header, vm_map_entry_t root,
1214 root->left = tail;
1219 * When llist is known to be the predecessor of root.
1222 vm_map_splay_merge_pred(vm_map_entry_t header, vm_map_entry_t root,
1227 max_free = root->start - llist->end;
1229 max_free = vm_map_splay_merge_left_walk(header, root,
1230 root, max_free, llist);
1232 root->left = header;
1233 header->right = root;
1239 * When llist may or may not be the predecessor of root.
1242 vm_map_splay_merge_left(vm_map_entry_t header, vm_map_entry_t root,
1247 max_free = vm_map_entry_max_free_left(root, llist);
1249 max_free = vm_map_splay_merge_left_walk(header, root,
1250 root->left == llist ? root : root->left,
1257 vm_map_splay_merge_right_walk(vm_map_entry_t header, vm_map_entry_t root,
1271 root->right = tail;
1276 * When rlist is known to be the succecessor of root.
1279 vm_map_splay_merge_succ(vm_map_entry_t header, vm_map_entry_t root,
1284 max_free = rlist->start - root->end;
1286 max_free = vm_map_splay_merge_right_walk(header, root,
1287 root, max_free, rlist);
1289 root->right = header;
1290 header->left = root;
1296 * When rlist may or may not be the succecessor of root.
1299 vm_map_splay_merge_right(vm_map_entry_t header, vm_map_entry_t root,
1304 max_free = vm_map_entry_max_free_right(root, rlist);
1306 max_free = vm_map_splay_merge_right_walk(header, root,
1307 root->right == rlist ? root : root->right,
1325 * predecessor, which the last ancestor on the search path from the root
1331 * The new root is the vm_map_entry containing "addr", or else an
1336 * Returns: the new root.
1341 vm_map_entry_t header, llist, rlist, root;
1345 root = vm_map_splay_split(map, addr, 0, &llist, &rlist);
1346 if (root != NULL) {
1347 max_free_left = vm_map_splay_merge_left(header, root, llist);
1348 max_free_right = vm_map_splay_merge_right(header, root, rlist);
1352 * subtree and make it the root.
1354 root = llist;
1355 llist = root->right;
1356 max_free_left = vm_map_splay_merge_left(header, root, llist);
1357 max_free_right = vm_map_splay_merge_succ(header, root, rlist);
1361 * subtree and make it the root.
1363 root = rlist;
1364 rlist = root->left;
1365 max_free_left = vm_map_splay_merge_pred(header, root, llist);
1366 max_free_right = vm_map_splay_merge_right(header, root, rlist);
1368 /* There is no root. */
1371 root->max_free = vm_size_max(max_free_left, max_free_right);
1372 map->root = root;
1374 return (root);
1389 vm_map_entry_t header, llist, rlist, root;
1398 root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1399 if (root == NULL) {
1402 * map, so it becomes the new root of the map tree.
1406 } else if (entry->start == root->start) {
1408 * The new entry is a clone of root, with only the end field
1409 * changed. The root entry will be shrunk to abut the new
1410 * entry, and will be the right child of the new root entry in
1413 KASSERT(entry->end < root->end,
1415 vm_map_splay_findprev(root, &llist);
1416 root->offset += entry->end - root->start;
1417 root->start = entry->end;
1419 max_free_right = root->max_free = vm_size_max(
1420 vm_map_splay_merge_pred(entry, root, entry),
1421 vm_map_splay_merge_right(header, root, rlist));
1424 * The new entry is a clone of root, with only the start field
1425 * changed. The root entry will be shrunk to abut the new
1426 * entry, and will be the left child of the new root entry in
1429 KASSERT(entry->end == root->end,
1431 vm_map_splay_findnext(root, &rlist);
1432 entry->offset += entry->start - root->start;
1433 root->end = entry->start;
1434 max_free_left = root->max_free = vm_size_max(
1435 vm_map_splay_merge_left(header, root, llist),
1436 vm_map_splay_merge_succ(entry, root, entry));
1440 map->root = entry;
1453 vm_map_entry_t header, llist, rlist, root;
1458 root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1459 KASSERT(root != NULL,
1462 vm_map_splay_findprev(root, &llist);
1463 vm_map_splay_findnext(root, &rlist);
1465 rlist->start = root->start;
1466 rlist->offset = root->offset;
1469 root = llist;
1470 llist = root->right;
1471 max_free_left = vm_map_splay_merge_left(header, root, llist);
1472 max_free_right = vm_map_splay_merge_succ(header, root, rlist);
1474 root = rlist;
1475 rlist = root->left;
1476 max_free_left = vm_map_splay_merge_pred(header, root, llist);
1477 max_free_right = vm_map_splay_merge_right(header, root, rlist);
1480 root = NULL;
1482 if (root != NULL)
1483 root->max_free = vm_size_max(max_free_left, max_free_right);
1484 map->root = root;
1502 vm_map_entry_t header, llist, rlist, root;
1506 root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1507 KASSERT(root != NULL, ("%s: resize object not mapped", __func__));
1508 vm_map_splay_findnext(root, &rlist);
1510 root->max_free = vm_size_max(
1511 vm_map_splay_merge_left(header, root, llist),
1512 vm_map_splay_merge_succ(header, root, rlist));
1513 map->root = root;
1543 cur = map->root;
1567 * If "address" is contained within a map entry, the new root
1568 * is that map entry. Otherwise, the new root is a map entry
1855 vm_map_entry_t header, llist, rlist, root, y;
1870 if (map->root == NULL)
1881 root = vm_map_splay_split(map, start, length, &llist, &rlist);
1883 if (root != NULL) {
1884 start = root->end;
1885 if (root->right != rlist)
1887 max_free_left = vm_map_splay_merge_left(header, root, llist);
1888 max_free_right = vm_map_splay_merge_right(header, root, rlist);
1890 root = rlist;
1891 rlist = root->left;
1892 max_free_left = vm_map_splay_merge_pred(header, root, llist);
1893 max_free_right = vm_map_splay_merge_right(header, root, rlist);
1895 root = llist;
1896 llist = root->right;
1897 max_free_left = vm_map_splay_merge_left(header, root, llist);
1898 max_free_right = vm_map_splay_merge_succ(header, root, rlist);
1900 root->max_free = vm_size_max(max_free_left, max_free_right);
1901 map->root = root;
1907 if (root->right == header || length > root->right->max_free)
1915 left_length = vm_map_entry_max_free_left(root, llist)) {
1917 SPLAY_LEFT_STEP(root, y, llist, rlist,
1920 SPLAY_RIGHT_STEP(root, y, llist, rlist,
1921 length > vm_map_entry_max_free_left(y, root));
1922 if (root == NULL)
1925 root = llist;
1926 llist = root->right;
1927 max_free_left = vm_map_splay_merge_left(header, root, llist);
1929 root->max_free = vm_size_max(max_free_left,
1930 vm_map_splay_merge_succ(header, root, rlist));
1935 vm_map_splay_merge_pred(root, y, root),
1937 root->max_free = vm_size_max(max_free_left, y->max_free);
1939 map->root = root;
1941 return (root->end);
5234 cur = map->root;