123 static struct ibv_mem_node *__mm_prev(struct ibv_mem_node *node)  in __mm_prev()  argument
125 	if (node->left) {  in __mm_prev()
126 		node = node->left;  in __mm_prev()
127 		while (node->right)  in __mm_prev()
128 			node = node->right;  in __mm_prev()
130 		while (node->parent && node == node->parent->left)  in __mm_prev()
131 			node = node->parent;  in __mm_prev()
133 		node = node->parent;  in __mm_prev()
136 	return node;  in __mm_prev()
139 static struct ibv_mem_node *__mm_next(struct ibv_mem_node *node)  in __mm_next()  argument
141 	if (node->right) {  in __mm_next()
142 		node = node->right;  in __mm_next()
143 		while (node->left)  in __mm_next()
144 			node = node->left;  in __mm_next()
146 		while (node->parent && node == node->parent->right)  in __mm_next()
147 			node = node->parent;  in __mm_next()
149 		node = node->parent;  in __mm_next()
152 	return node;  in __mm_next()
155 static void __mm_rotate_right(struct ibv_mem_node *node)  in __mm_rotate_right()  argument
159 	tmp = node->left;  in __mm_rotate_right()
161 	node->left = tmp->right;  in __mm_rotate_right()
162 	if (node->left)  in __mm_rotate_right()
163 		node->left->parent = node;  in __mm_rotate_right()
165 	if (node->parent) {  in __mm_rotate_right()
166 		if (node->parent->right == node)  in __mm_rotate_right()
167 			node->parent->right = tmp;  in __mm_rotate_right()
169 			node->parent->left = tmp;  in __mm_rotate_right()
173 	tmp->parent = node->parent;  in __mm_rotate_right()
175 	tmp->right = node;  in __mm_rotate_right()
176 	node->parent = tmp;  in __mm_rotate_right()
179 static void __mm_rotate_left(struct ibv_mem_node *node)  in __mm_rotate_left()  argument
183 	tmp = node->right;  in __mm_rotate_left()
185 	node->right = tmp->left;  in __mm_rotate_left()
186 	if (node->right)  in __mm_rotate_left()
187 		node->right->parent = node;  in __mm_rotate_left()
189 	if (node->parent) {  in __mm_rotate_left()
190 		if (node->parent->right == node)  in __mm_rotate_left()
191 			node->parent->right = tmp;  in __mm_rotate_left()
193 			node->parent->left = tmp;  in __mm_rotate_left()
197 	tmp->parent = node->parent;  in __mm_rotate_left()
199 	tmp->left = node;  in __mm_rotate_left()
200 	node->parent = tmp;  in __mm_rotate_left()
203 static int verify(struct ibv_mem_node *node)  in verify()  argument
207 	if (!node)  in verify()
210 	hl = verify(node->left);  in verify()
211 	hr = verify(node->left);  in verify()
218 	if (node->color == IBV_RED) {  in verify()
219 		if (node->left && node->left->color != IBV_BLACK)  in verify()
221 		if (node->right && node->right->color != IBV_BLACK)  in verify()
229 static void __mm_add_rebalance(struct ibv_mem_node *node)  in __mm_add_rebalance()  argument
233 	while (node->parent && node->parent->color == IBV_RED) {  in __mm_add_rebalance()
234 		parent = node->parent;  in __mm_add_rebalance()
235 		gp     = node->parent->parent;  in __mm_add_rebalance()
245 				node = gp;  in __mm_add_rebalance()
247 				if (node == parent->right) {  in __mm_add_rebalance()
249 					node   = parent;  in __mm_add_rebalance()
250 					parent = node->parent;  in __mm_add_rebalance()
266 				node = gp;  in __mm_add_rebalance()
268 				if (node == parent->left) {  in __mm_add_rebalance()
270 					node   = parent;  in __mm_add_rebalance()
271 					parent = node->parent;  in __mm_add_rebalance()
287 	struct ibv_mem_node *node, *parent = NULL;  in __mm_add()  local
289 	node = mm_root;  in __mm_add()
290 	while (node) {  in __mm_add()
291 		parent = node;  in __mm_add()
292 		if (node->start < new->start)  in __mm_add()
293 			node = node->right;  in __mm_add()
295 			node = node->left;  in __mm_add()
311 static void __mm_remove(struct ibv_mem_node *node)  in __mm_remove()  argument
316 	if (node->left && node->right) {  in __mm_remove()
317 		tmp = node->left;  in __mm_remove()
323 		tmp->color = node->color;  in __mm_remove()
325 		if (tmp->parent != node) {  in __mm_remove()
331 			tmp->left   	   = node->left;  in __mm_remove()
332 			node->left->parent = tmp;  in __mm_remove()
336 		tmp->right          = node->right;  in __mm_remove()
337 		node->right->parent = tmp;  in __mm_remove()
339 		tmp->parent = node->parent;  in __mm_remove()
340 		if (node->parent) {  in __mm_remove()
341 			if (node->parent->left == node)  in __mm_remove()
342 				node->parent->left = tmp;  in __mm_remove()
344 				node->parent->right = tmp;  in __mm_remove()
348 		nodecol = node->color;  in __mm_remove()
350 		child  = node->left ? node->left : node->right;  in __mm_remove()
351 		parent = node->parent;  in __mm_remove()
356 			if (parent->left == node)  in __mm_remove()
364 	free(node);  in __mm_remove()
443 	struct ibv_mem_node *node = mm_root;  in __mm_find_start()  local
445 	while (node) {  in __mm_find_start()
446 		if (node->start <= start && node->end >= start)  in __mm_find_start()
449 		if (node->start < start)  in __mm_find_start()
450 			node = node->right;  in __mm_find_start()
452 			node = node->left;  in __mm_find_start()
455 	return node;  in __mm_find_start()
458 static struct ibv_mem_node *merge_ranges(struct ibv_mem_node *node,  in merge_ranges()  argument
461 	prev->end = node->end;  in merge_ranges()
462 	prev->refcnt = node->refcnt;  in merge_ranges()
463 	__mm_remove(node);  in merge_ranges()
468 static struct ibv_mem_node *split_range(struct ibv_mem_node *node,  in split_range()  argument
477 	new_node->end    = node->end;  in split_range()
478 	new_node->refcnt = node->refcnt;  in split_range()
479 	node->end  = cut_line - 1;  in split_range()
488 	struct ibv_mem_node *node, *tmp = NULL;  in get_start_node()  local
490 	node = __mm_find_start(start, end);  in get_start_node()
491 	if (node->start < start)  in get_start_node()
492 		node = split_range(node, start);  in get_start_node()
494 		tmp = __mm_prev(node);  in get_start_node()
495 		if (tmp && tmp->refcnt == node->refcnt + inc)  in get_start_node()
496 			node = merge_ranges(node, tmp);  in get_start_node()
498 	return node;  in get_start_node()
505 static struct ibv_mem_node *undo_node(struct ibv_mem_node *node,  in undo_node()  argument
514 	if (start > node->start) {  in undo_node()
515 		tmp = split_range(node, start);  in undo_node()
517 			node->refcnt += inc;  in undo_node()
518 			node = tmp;  in undo_node()
523 	tmp  =  __mm_prev(node);  in undo_node()
524 	if (tmp && tmp->refcnt == node->refcnt)  in undo_node()
525 		node = merge_ranges(node, tmp);  in undo_node()
527 	tmp  =  __mm_next(node);  in undo_node()
528 	if (tmp && tmp->refcnt == node->refcnt)  in undo_node()
529 		node = merge_ranges(tmp, node);  in undo_node()
531 	return node;  in undo_node()
537 	struct ibv_mem_node *node, *tmp;  in ibv_madvise_range()  local
553 	node = get_start_node(start, end, inc);  in ibv_madvise_range()
554 	if (!node) {  in ibv_madvise_range()
559 	while (node && node->start <= end) {  in ibv_madvise_range()
560 		if (node->end > end) {  in ibv_madvise_range()
561 			if (!split_range(node, end + 1)) {  in ibv_madvise_range()
567 		if ((inc == -1 && node->refcnt == 1) ||  in ibv_madvise_range()
568 		    (inc ==  1 && node->refcnt == 0)) {  in ibv_madvise_range()
580 			if (start > node->start)  in ibv_madvise_range()
581 				ret = minherit((void *) start, node->end - start + 1,  in ibv_madvise_range()
584 				ret = minherit((void *) node->start,  in ibv_madvise_range()
585 					      node->end - node->start + 1,  in ibv_madvise_range()
588 				node = undo_node(node, start, inc);  in ibv_madvise_range()
590 				if (rolling_back || !node)  in ibv_madvise_range()
597 				tmp = __mm_prev(node);  in ibv_madvise_range()
605 		node->refcnt += inc;  in ibv_madvise_range()
606 		node = __mm_next(node);  in ibv_madvise_range()
609 	if (node) {  in ibv_madvise_range()
610 		tmp = __mm_prev(node);  in ibv_madvise_range()
611 		if (tmp && node->refcnt == tmp->refcnt)  in ibv_madvise_range()
612 			node = merge_ranges(node, tmp);  in ibv_madvise_range()