sys/vm/vm_map.c

1037 #define SPLAY_LEFT_STEP(root, y, llist, rlist, test) do {		\
1049 	    vm_map_entry_max_free_left(root, llist),			\
1052 	if (max_free - 1 < vm_map_entry_max_free_left(root, llist))	\
1054 	if (y != llist && (test)) {					\
1075 	root = y != llist ? y : NULL;					\
1078 #define SPLAY_RIGHT_STEP(root, y, llist, rlist, test) do {		\
1090 	    vm_map_entry_max_free_left(root, llist),			\
1094 		max_free = vm_map_entry_max_free_left(root, llist);	\
1110 	/* Copy left->max_free.  Put root on llist. */			\
1112 	KASSERT(max_free == vm_map_entry_max_free_left(root, llist),	\
1114 	root->right = llist;						\
1115 	llist = root;							\
1122  * subtrees with root->max_free < length as empty trees.  llist and rlist are
1123  * the two sides in reverse order (bottom-up), with llist linked by the right
1131     vm_map_entry_t *llist, vm_map_entry_t *rlist)
1150 	*llist = left;
1171 vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *llist)
1175 	left = *llist;
1182 	*llist = left;
1197  * subtrees of the root go at the bottom of llist and rlist.
1201     vm_map_entry_t tail, vm_size_t max_free, vm_map_entry_t llist)
1205 		 * The max_free values of the children of llist are in
1206 		 * llist->max_free and max_free.  Update with the
1209 		llist->max_free = max_free =
1210 		    vm_size_max(llist->max_free, max_free);
1211 		vm_map_entry_swap(&llist->right, &tail);
1212 		vm_map_entry_swap(&tail, &llist);
1213 	} while (llist != header);
1219  * When llist is known to be the predecessor of root.
1223     vm_map_entry_t llist)
1227 	max_free = root->start - llist->end;
1228 	if (llist != header) {
1230 		    root, max_free, llist);
1239  * When llist may or may not be the predecessor of root.
1243     vm_map_entry_t llist)
1247 	max_free = vm_map_entry_max_free_left(root, llist);
1248 	if (llist != header) {
1250 		    root->left == llist ? root : root->left,
1251 		    max_free, llist);
1341 	vm_map_entry_t header, llist, rlist, root;
1345 	root = vm_map_splay_split(map, addr, 0, &llist, &rlist);
1347 		max_free_left = vm_map_splay_merge_left(header, root, llist);
1349 	} else if (llist != header) {
1354 		root = llist;
1355 		llist = root->right;
1356 		max_free_left = vm_map_splay_merge_left(header, root, llist);
1365 		max_free_left = vm_map_splay_merge_pred(header, root, llist);
1389 	vm_map_entry_t header, llist, rlist, root;
1398 	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1404 		max_free_left = vm_map_splay_merge_pred(header, entry, llist);
1415 		vm_map_splay_findprev(root, &llist);
1418 		max_free_left = vm_map_splay_merge_pred(header, entry, llist);
1435 		    vm_map_splay_merge_left(header, root, llist),
1453 	vm_map_entry_t header, llist, rlist, root;
1458 	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1462 	vm_map_splay_findprev(root, &llist);
1468 	if (llist != header) {
1469 		root = llist;
1470 		llist = root->right;
1471 		max_free_left = vm_map_splay_merge_left(header, root, llist);
1476 		max_free_left = vm_map_splay_merge_pred(header, root, llist);
1502 	vm_map_entry_t header, llist, rlist, root;
1506 	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1511 	    vm_map_splay_merge_left(header, root, llist),
1855 	vm_map_entry_t header, llist, rlist, root, y;
1881 	root = vm_map_splay_split(map, start, length, &llist, &rlist);
1887 		max_free_left = vm_map_splay_merge_left(header, root, llist);
1892 		max_free_left = vm_map_splay_merge_pred(header, root, llist);
1895 		root = llist;
1896 		llist = root->right;
1897 		max_free_left = vm_map_splay_merge_left(header, root, llist);
1913 	llist = rlist = header;
1915 	    left_length = vm_map_entry_max_free_left(root, llist)) {
1917 			SPLAY_LEFT_STEP(root, y, llist, rlist,
1918 			    length <= vm_map_entry_max_free_left(y, llist));
1920 			SPLAY_RIGHT_STEP(root, y, llist, rlist,
1925 	root = llist;
1926 	llist = root->right;
1927 	max_free_left = vm_map_splay_merge_left(header, root, llist);