852 	return (msleep(&map->root, &map_sleep_mtx, PDROP | PVM, "vmmaps",  in _vm_map_unlock_and_wait()
873 	wakeup(&map->root);  in vm_map_wakeup()
933 	map->root = NULL;  in _vm_map_init()
1025 vm_map_entry_max_free_left(vm_map_entry_t root, vm_map_entry_t left_ancestor)  in vm_map_entry_max_free_left()  argument
1028 	return (root->left != left_ancestor ?  in vm_map_entry_max_free_left()
1029 	    root->left->max_free : root->start - left_ancestor->end);  in vm_map_entry_max_free_left()
1033 vm_map_entry_max_free_right(vm_map_entry_t root, vm_map_entry_t right_ancestor)  in vm_map_entry_max_free_right()  argument
1036 	return (root->right != right_ancestor ?  in vm_map_entry_max_free_right()
1037 	    root->right->max_free : right_ancestor->start - root->end);  in vm_map_entry_max_free_right()
1068 #define SPLAY_LEFT_STEP(root, y, llist, rlist, test) do {		\  argument
1077 	y = root->left;							\
1078 	max_free = root->max_free;					\
1080 	    vm_map_entry_max_free_left(root, llist),			\
1081 	    vm_map_entry_max_free_right(root, rlist)),			\
1083 	if (max_free - 1 < vm_map_entry_max_free_left(root, llist))	\
1084 		max_free = vm_map_entry_max_free_right(root, rlist);	\
1088 		if (z != root) {					\
1089 			root->left = z;					\
1090 			y->right = root;				\
1092 			    root->max_free = max_free =			\
1095 			root->max_free = max_free =			\
1096 			    vm_size_max(max_free, root->start - y->end);\
1097 		root = y;						\
1098 		y = root->left;						\
1101 	root->max_free = max_free;					\
1102 	KASSERT(max_free == vm_map_entry_max_free_right(root, rlist),	\
1104 	root->left = rlist;						\
1105 	rlist = root;							\
1106 	root = y != llist ? y : NULL;					\
1109 #define SPLAY_RIGHT_STEP(root, y, llist, rlist, test) do {		\  argument
1118 	y = root->right;						\
1119 	max_free = root->max_free;					\
1121 	    vm_map_entry_max_free_left(root, llist),			\
1122 	    vm_map_entry_max_free_right(root, rlist)),			\
1124 	if (max_free - 1 < vm_map_entry_max_free_right(root, rlist))	\
1125 		max_free = vm_map_entry_max_free_left(root, llist);	\
1129 		if (z != root) {					\
1130 			root->right = z;				\
1131 			y->left = root;					\
1133 			    root->max_free = max_free =			\
1136 			root->max_free = max_free =			\
1137 			    vm_size_max(max_free, y->start - root->end);\
1138 		root = y;						\
1139 		y = root->right;					\
1142 	root->max_free = max_free;					\
1143 	KASSERT(max_free == vm_map_entry_max_free_left(root, llist),	\
1145 	root->right = llist;						\
1146 	llist = root;							\
1147 	root = y != rlist ? y : NULL;					\
1164 	vm_map_entry_t left, right, root, y;  in vm_map_splay_split()  local
1167 	root = map->root;  in vm_map_splay_split()
1168 	while (root != NULL && root->max_free >= length) {  in vm_map_splay_split()
1169 		KASSERT(left->end <= root->start &&  in vm_map_splay_split()
1170 		    root->end <= right->start,  in vm_map_splay_split()
1172 		if (addr < root->start) {  in vm_map_splay_split()
1173 			SPLAY_LEFT_STEP(root, y, left, right,  in vm_map_splay_split()
1175 		} else if (addr >= root->end) {  in vm_map_splay_split()
1176 			SPLAY_RIGHT_STEP(root, y, left, right,  in vm_map_splay_split()
1183 	return (root);  in vm_map_splay_split()
1187 vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *rlist)  in vm_map_splay_findnext()  argument
1192 	hi = root->right == right ? NULL : root->right;  in vm_map_splay_findnext()
1196 		SPLAY_LEFT_STEP(hi, y, root, right, true);  in vm_map_splay_findnext()
1202 vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *llist)  in vm_map_splay_findprev()  argument
1207 	lo = root->left == left ? NULL : root->left;  in vm_map_splay_findprev()
1211 		SPLAY_RIGHT_STEP(lo, y, left, root, true);  in vm_map_splay_findprev()
1231 vm_map_splay_merge_left_walk(vm_map_entry_t header, vm_map_entry_t root,  in vm_map_splay_merge_left_walk()  argument
1245 	root->left = tail;  in vm_map_splay_merge_left_walk()
1253 vm_map_splay_merge_pred(vm_map_entry_t header, vm_map_entry_t root,  in vm_map_splay_merge_pred()  argument
1258 	max_free = root->start - llist->end;  in vm_map_splay_merge_pred()
1260 		max_free = vm_map_splay_merge_left_walk(header, root,  in vm_map_splay_merge_pred()
1261 		    root, max_free, llist);  in vm_map_splay_merge_pred()
1263 		root->left = header;  in vm_map_splay_merge_pred()
1264 		header->right = root;  in vm_map_splay_merge_pred()
1273 vm_map_splay_merge_left(vm_map_entry_t header, vm_map_entry_t root,  in vm_map_splay_merge_left()  argument
1278 	max_free = vm_map_entry_max_free_left(root, llist);  in vm_map_splay_merge_left()
1280 		max_free = vm_map_splay_merge_left_walk(header, root,  in vm_map_splay_merge_left()
1281 		    root->left == llist ? root : root->left,  in vm_map_splay_merge_left()
1288 vm_map_splay_merge_right_walk(vm_map_entry_t header, vm_map_entry_t root,  in vm_map_splay_merge_right_walk()  argument
1302 	root->right = tail;  in vm_map_splay_merge_right_walk()
1310 vm_map_splay_merge_succ(vm_map_entry_t header, vm_map_entry_t root,  in vm_map_splay_merge_succ()  argument
1315 	max_free = rlist->start - root->end;  in vm_map_splay_merge_succ()
1317 		max_free = vm_map_splay_merge_right_walk(header, root,  in vm_map_splay_merge_succ()
1318 		    root, max_free, rlist);  in vm_map_splay_merge_succ()
1320 		root->right = header;  in vm_map_splay_merge_succ()
1321 		header->left = root;  in vm_map_splay_merge_succ()
1330 vm_map_splay_merge_right(vm_map_entry_t header, vm_map_entry_t root,  in vm_map_splay_merge_right()  argument
1335 	max_free = vm_map_entry_max_free_right(root, rlist);  in vm_map_splay_merge_right()
1337 		max_free = vm_map_splay_merge_right_walk(header, root,  in vm_map_splay_merge_right()
1338 		    root->right == rlist ? root : root->right,  in vm_map_splay_merge_right()
1372 	vm_map_entry_t header, llist, rlist, root;  in vm_map_splay()  local
1376 	root = vm_map_splay_split(map, addr, 0, &llist, &rlist);  in vm_map_splay()
1377 	if (root != NULL) {  in vm_map_splay()
1378 		max_free_left = vm_map_splay_merge_left(header, root, llist);  in vm_map_splay()
1379 		max_free_right = vm_map_splay_merge_right(header, root, rlist);  in vm_map_splay()
1385 		root = llist;  in vm_map_splay()
1386 		llist = root->right;  in vm_map_splay()
1387 		max_free_left = vm_map_splay_merge_left(header, root, llist);  in vm_map_splay()
1388 		max_free_right = vm_map_splay_merge_succ(header, root, rlist);  in vm_map_splay()
1394 		root = rlist;  in vm_map_splay()
1395 		rlist = root->left;  in vm_map_splay()
1396 		max_free_left = vm_map_splay_merge_pred(header, root, llist);  in vm_map_splay()
1397 		max_free_right = vm_map_splay_merge_right(header, root, rlist);  in vm_map_splay()
1402 	root->max_free = vm_size_max(max_free_left, max_free_right);  in vm_map_splay()
1403 	map->root = root;  in vm_map_splay()
1405 	return (root);  in vm_map_splay()
1420 	vm_map_entry_t header, llist, rlist, root;  in vm_map_entry_link()  local
1429 	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);  in vm_map_entry_link()
1430 	if (root == NULL) {  in vm_map_entry_link()
1437 	} else if (entry->start == root->start) {  in vm_map_entry_link()
1444 		KASSERT(entry->end < root->end,  in vm_map_entry_link()
1446 		vm_map_splay_findprev(root, &llist);  in vm_map_entry_link()
1447 		root->offset += entry->end - root->start;  in vm_map_entry_link()
1448 		root->start = entry->end;  in vm_map_entry_link()
1450 		max_free_right = root->max_free = vm_size_max(  in vm_map_entry_link()
1451 		    vm_map_splay_merge_pred(entry, root, entry),  in vm_map_entry_link()
1452 		    vm_map_splay_merge_right(header, root, rlist));  in vm_map_entry_link()
1460 		KASSERT(entry->end == root->end,  in vm_map_entry_link()
1462 		vm_map_splay_findnext(root, &rlist);  in vm_map_entry_link()
1463 		entry->offset += entry->start - root->start;  in vm_map_entry_link()
1464 		root->end = entry->start;  in vm_map_entry_link()
1465 		max_free_left = root->max_free = vm_size_max(  in vm_map_entry_link()
1466 		    vm_map_splay_merge_left(header, root, llist),  in vm_map_entry_link()
1467 		    vm_map_splay_merge_succ(entry, root, entry));  in vm_map_entry_link()
1471 	map->root = entry;  in vm_map_entry_link()
1484 	vm_map_entry_t header, llist, rlist, root;  in vm_map_entry_unlink()  local
1489 	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);  in vm_map_entry_unlink()
1490 	KASSERT(root != NULL,  in vm_map_entry_unlink()
1493 	vm_map_splay_findprev(root, &llist);  in vm_map_entry_unlink()
1494 	vm_map_splay_findnext(root, &rlist);  in vm_map_entry_unlink()
1496 		rlist->start = root->start;  in vm_map_entry_unlink()
1497 		rlist->offset = root->offset;  in vm_map_entry_unlink()
1500 		root = llist;  in vm_map_entry_unlink()
1501 		llist = root->right;  in vm_map_entry_unlink()
1502 		max_free_left = vm_map_splay_merge_left(header, root, llist);  in vm_map_entry_unlink()
1503 		max_free_right = vm_map_splay_merge_succ(header, root, rlist);  in vm_map_entry_unlink()
1505 		root = rlist;  in vm_map_entry_unlink()
1506 		rlist = root->left;  in vm_map_entry_unlink()
1507 		max_free_left = vm_map_splay_merge_pred(header, root, llist);  in vm_map_entry_unlink()
1508 		max_free_right = vm_map_splay_merge_right(header, root, rlist);  in vm_map_entry_unlink()
1511 		root = NULL;  in vm_map_entry_unlink()
1513 	if (root != NULL)  in vm_map_entry_unlink()
1514 		root->max_free = vm_size_max(max_free_left, max_free_right);  in vm_map_entry_unlink()
1515 	map->root = root;  in vm_map_entry_unlink()
1533 	vm_map_entry_t header, llist, rlist, root;  in vm_map_entry_resize()  local
1537 	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);  in vm_map_entry_resize()
1538 	KASSERT(root != NULL, ("%s: resize object not mapped", __func__));  in vm_map_entry_resize()
1539 	vm_map_splay_findnext(root, &rlist);  in vm_map_entry_resize()
1541 	root->max_free = vm_size_max(  in vm_map_entry_resize()
1542 	    vm_map_splay_merge_left(header, root, llist),  in vm_map_entry_resize()
1543 	    vm_map_splay_merge_succ(header, root, rlist));  in vm_map_entry_resize()
1544 	map->root = root;  in vm_map_entry_resize()
1574 	cur = map->root;  in vm_map_lookup_entry()
1886 	vm_map_entry_t header, llist, rlist, root, y;  in vm_map_findspace()  local
1901 	if (map->root == NULL)  in vm_map_findspace()
1912 	root = vm_map_splay_split(map, start, length, &llist, &rlist);  in vm_map_findspace()
1914 	if (root != NULL) {  in vm_map_findspace()
1915 		start = root->end;  in vm_map_findspace()
1916 		if (root->right != rlist)  in vm_map_findspace()
1918 		max_free_left = vm_map_splay_merge_left(header, root, llist);  in vm_map_findspace()
1919 		max_free_right = vm_map_splay_merge_right(header, root, rlist);  in vm_map_findspace()
1921 		root = rlist;  in vm_map_findspace()
1922 		rlist = root->left;  in vm_map_findspace()
1923 		max_free_left = vm_map_splay_merge_pred(header, root, llist);  in vm_map_findspace()
1924 		max_free_right = vm_map_splay_merge_right(header, root, rlist);  in vm_map_findspace()
1926 		root = llist;  in vm_map_findspace()
1927 		llist = root->right;  in vm_map_findspace()
1928 		max_free_left = vm_map_splay_merge_left(header, root, llist);  in vm_map_findspace()
1929 		max_free_right = vm_map_splay_merge_succ(header, root, rlist);  in vm_map_findspace()
1931 	root->max_free = vm_size_max(max_free_left, max_free_right);  in vm_map_findspace()
1932 	map->root = root;  in vm_map_findspace()
1938 	if (root->right == header || length > root->right->max_free)  in vm_map_findspace()
1946 	    left_length = vm_map_entry_max_free_left(root, llist)) {  in vm_map_findspace()
1948 			SPLAY_LEFT_STEP(root, y, llist, rlist,  in vm_map_findspace()
1951 			SPLAY_RIGHT_STEP(root, y, llist, rlist,  in vm_map_findspace()
1952 			    length > vm_map_entry_max_free_left(y, root));  in vm_map_findspace()
1953 		if (root == NULL)  in vm_map_findspace()
1956 	root = llist;  in vm_map_findspace()
1957 	llist = root->right;  in vm_map_findspace()
1958 	max_free_left = vm_map_splay_merge_left(header, root, llist);  in vm_map_findspace()
1960 		root->max_free = vm_size_max(max_free_left,  in vm_map_findspace()
1961 		    vm_map_splay_merge_succ(header, root, rlist));  in vm_map_findspace()
1966 		    vm_map_splay_merge_pred(root, y, root),  in vm_map_findspace()
1968 		root->max_free = vm_size_max(max_free_left, y->max_free);  in vm_map_findspace()
1970 	map->root = root;  in vm_map_findspace()
1972 	return (root->end);  in vm_map_findspace()
5259 		cur = map->root;  in _vm_map_assert_consistent()