177 static struct ibv_mem_node *__mm_prev(struct ibv_mem_node *node)  in __mm_prev()  argument
179 	if (node->left) {  in __mm_prev()
180 		node = node->left;  in __mm_prev()
181 		while (node->right)  in __mm_prev()
182 			node = node->right;  in __mm_prev()
184 		while (node->parent && node == node->parent->left)  in __mm_prev()
185 			node = node->parent;  in __mm_prev()
187 		node = node->parent;  in __mm_prev()
190 	return node;  in __mm_prev()
193 static struct ibv_mem_node *__mm_next(struct ibv_mem_node *node)  in __mm_next()  argument
195 	if (node->right) {  in __mm_next()
196 		node = node->right;  in __mm_next()
197 		while (node->left)  in __mm_next()
198 			node = node->left;  in __mm_next()
200 		while (node->parent && node == node->parent->right)  in __mm_next()
201 			node = node->parent;  in __mm_next()
203 		node = node->parent;  in __mm_next()
206 	return node;  in __mm_next()
209 static void __mm_rotate_right(struct ibv_mem_node *node)  in __mm_rotate_right()  argument
213 	tmp = node->left;  in __mm_rotate_right()
215 	node->left = tmp->right;  in __mm_rotate_right()
216 	if (node->left)  in __mm_rotate_right()
217 		node->left->parent = node;  in __mm_rotate_right()
219 	if (node->parent) {  in __mm_rotate_right()
220 		if (node->parent->right == node)  in __mm_rotate_right()
221 			node->parent->right = tmp;  in __mm_rotate_right()
223 			node->parent->left = tmp;  in __mm_rotate_right()
227 	tmp->parent = node->parent;  in __mm_rotate_right()
229 	tmp->right = node;  in __mm_rotate_right()
230 	node->parent = tmp;  in __mm_rotate_right()
233 static void __mm_rotate_left(struct ibv_mem_node *node)  in __mm_rotate_left()  argument
237 	tmp = node->right;  in __mm_rotate_left()
239 	node->right = tmp->left;  in __mm_rotate_left()
240 	if (node->right)  in __mm_rotate_left()
241 		node->right->parent = node;  in __mm_rotate_left()
243 	if (node->parent) {  in __mm_rotate_left()
244 		if (node->parent->right == node)  in __mm_rotate_left()
245 			node->parent->right = tmp;  in __mm_rotate_left()
247 			node->parent->left = tmp;  in __mm_rotate_left()
251 	tmp->parent = node->parent;  in __mm_rotate_left()
253 	tmp->left = node;  in __mm_rotate_left()
254 	node->parent = tmp;  in __mm_rotate_left()
258 static int verify(struct ibv_mem_node *node)
262 	if (!node)
265 	hl = verify(node->left);
266 	hr = verify(node->left);
273 	if (node->color == IBV_RED) {
274 		if (node->left && node->left->color != IBV_BLACK)
276 		if (node->right && node->right->color != IBV_BLACK)
285 static void __mm_add_rebalance(struct ibv_mem_node *node)  in __mm_add_rebalance()  argument
289 	while (node->parent && node->parent->color == IBV_RED) {  in __mm_add_rebalance()
290 		parent = node->parent;  in __mm_add_rebalance()
291 		gp     = node->parent->parent;  in __mm_add_rebalance()
301 				node = gp;  in __mm_add_rebalance()
303 				if (node == parent->right) {  in __mm_add_rebalance()
305 					node   = parent;  in __mm_add_rebalance()
306 					parent = node->parent;  in __mm_add_rebalance()
322 				node = gp;  in __mm_add_rebalance()
324 				if (node == parent->left) {  in __mm_add_rebalance()
326 					node   = parent;  in __mm_add_rebalance()
327 					parent = node->parent;  in __mm_add_rebalance()
343 	struct ibv_mem_node *node, *parent = NULL;  in __mm_add()  local
345 	node = mm_root;  in __mm_add()
346 	while (node) {  in __mm_add()
347 		parent = node;  in __mm_add()
348 		if (node->start < new->start)  in __mm_add()
349 			node = node->right;  in __mm_add()
351 			node = node->left;  in __mm_add()
367 static void __mm_remove(struct ibv_mem_node *node)  in __mm_remove()  argument
372 	if (node->left && node->right) {  in __mm_remove()
373 		tmp = node->left;  in __mm_remove()
379 		tmp->color = node->color;  in __mm_remove()
381 		if (tmp->parent != node) {  in __mm_remove()
387 			tmp->left   	   = node->left;  in __mm_remove()
388 			node->left->parent = tmp;  in __mm_remove()
392 		tmp->right          = node->right;  in __mm_remove()
393 		node->right->parent = tmp;  in __mm_remove()
395 		tmp->parent = node->parent;  in __mm_remove()
396 		if (node->parent) {  in __mm_remove()
397 			if (node->parent->left == node)  in __mm_remove()
398 				node->parent->left = tmp;  in __mm_remove()
400 				node->parent->right = tmp;  in __mm_remove()
404 		nodecol = node->color;  in __mm_remove()
406 		child  = node->left ? node->left : node->right;  in __mm_remove()
407 		parent = node->parent;  in __mm_remove()
412 			if (parent->left == node)  in __mm_remove()
420 	free(node);  in __mm_remove()
499 	struct ibv_mem_node *node = mm_root;  in __mm_find_start()  local
501 	while (node) {  in __mm_find_start()
502 		if (node->start <= start && node->end >= start)  in __mm_find_start()
505 		if (node->start < start)  in __mm_find_start()
506 			node = node->right;  in __mm_find_start()
508 			node = node->left;  in __mm_find_start()
511 	return node;  in __mm_find_start()
514 static struct ibv_mem_node *merge_ranges(struct ibv_mem_node *node,  in merge_ranges()  argument
517 	prev->end = node->end;  in merge_ranges()
518 	prev->refcnt = node->refcnt;  in merge_ranges()
519 	__mm_remove(node);  in merge_ranges()
524 static struct ibv_mem_node *split_range(struct ibv_mem_node *node,  in split_range()  argument
533 	new_node->end    = node->end;  in split_range()
534 	new_node->refcnt = node->refcnt;  in split_range()
535 	node->end  = cut_line - 1;  in split_range()
544 	struct ibv_mem_node *node, *tmp = NULL;  in get_start_node()  local
546 	node = __mm_find_start(start, end);  in get_start_node()
547 	if (node->start < start)  in get_start_node()
548 		node = split_range(node, start);  in get_start_node()
550 		tmp = __mm_prev(node);  in get_start_node()
551 		if (tmp && tmp->refcnt == node->refcnt + inc)  in get_start_node()
552 			node = merge_ranges(node, tmp);  in get_start_node()
554 	return node;  in get_start_node()
561 static struct ibv_mem_node *undo_node(struct ibv_mem_node *node,  in undo_node()  argument
570 	if (start > node->start) {  in undo_node()
571 		tmp = split_range(node, start);  in undo_node()
573 			node->refcnt += inc;  in undo_node()
574 			node = tmp;  in undo_node()
579 	tmp  =  __mm_prev(node);  in undo_node()
580 	if (tmp && tmp->refcnt == node->refcnt)  in undo_node()
581 		node = merge_ranges(node, tmp);  in undo_node()
583 	tmp  =  __mm_next(node);  in undo_node()
584 	if (tmp && tmp->refcnt == node->refcnt)  in undo_node()
585 		node = merge_ranges(tmp, node);  in undo_node()
587 	return node;  in undo_node()
593 	struct ibv_mem_node *node, *tmp;  in ibv_madvise_range()  local
615 	node = get_start_node(start, end, inc);  in ibv_madvise_range()
616 	if (!node) {  in ibv_madvise_range()
621 	while (node && node->start <= end) {  in ibv_madvise_range()
622 		if (node->end > end) {  in ibv_madvise_range()
623 			if (!split_range(node, end + 1)) {  in ibv_madvise_range()
629 		if ((inc == -1 && node->refcnt == 1) ||  in ibv_madvise_range()
630 		    (inc ==  1 && node->refcnt == 0)) {  in ibv_madvise_range()
642 			if (start > node->start)  in ibv_madvise_range()
643 				ret = madvise((void *) start, node->end - start + 1,  in ibv_madvise_range()
646 				ret = madvise((void *) node->start,  in ibv_madvise_range()
647 					      node->end - node->start + 1,  in ibv_madvise_range()
650 				node = undo_node(node, start, inc);  in ibv_madvise_range()
652 				if (rolling_back || !node)  in ibv_madvise_range()
659 				tmp = __mm_prev(node);  in ibv_madvise_range()
667 		node->refcnt += inc;  in ibv_madvise_range()
668 		node = __mm_next(node);  in ibv_madvise_range()
671 	if (node) {  in ibv_madvise_range()
672 		tmp = __mm_prev(node);  in ibv_madvise_range()
673 		if (tmp && node->refcnt == tmp->refcnt)  in ibv_madvise_range()
674 			node = merge_ranges(node, tmp);  in ibv_madvise_range()