sys/vm/vm_map.c

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;