Lines Matching +full:child +full:- +full:node
15 * - Redistributions of source code must retain the above
19 * - Redistributions in binary form must reproduce the above
107 n = sscanf(buf, "%" SCNxPTR "-%" SCNxPTR, &range_start, &range_end); in get_page_size()
148 tmp_aligned = (void *) ((uintptr_t) tmp & ~(size - 1)); in ibv_fork_init()
166 mm_root->parent = NULL; in ibv_fork_init()
167 mm_root->left = NULL; in ibv_fork_init()
168 mm_root->right = NULL; in ibv_fork_init()
169 mm_root->color = IBV_BLACK; in ibv_fork_init()
170 mm_root->start = 0; in ibv_fork_init()
171 mm_root->end = UINTPTR_MAX; in ibv_fork_init()
172 mm_root->refcnt = 0; in ibv_fork_init()
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()
293 if (parent == gp->left) { in __mm_add_rebalance()
294 uncle = gp->right; in __mm_add_rebalance()
296 if (uncle && uncle->color == IBV_RED) { in __mm_add_rebalance()
297 parent->color = IBV_BLACK; in __mm_add_rebalance()
298 uncle->color = IBV_BLACK; in __mm_add_rebalance()
299 gp->color = IBV_RED; 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()
309 parent->color = IBV_BLACK; in __mm_add_rebalance()
310 gp->color = IBV_RED; in __mm_add_rebalance()
315 uncle = gp->left; in __mm_add_rebalance()
317 if (uncle && uncle->color == IBV_RED) { in __mm_add_rebalance()
318 parent->color = IBV_BLACK; in __mm_add_rebalance()
319 uncle->color = IBV_BLACK; in __mm_add_rebalance()
320 gp->color = IBV_RED; 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()
330 parent->color = IBV_BLACK; in __mm_add_rebalance()
331 gp->color = IBV_RED; in __mm_add_rebalance()
338 mm_root->color = IBV_BLACK; 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()
354 if (parent->start < new->start) in __mm_add()
355 parent->right = new; in __mm_add()
357 parent->left = new; in __mm_add()
359 new->parent = parent; in __mm_add()
360 new->left = NULL; in __mm_add()
361 new->right = NULL; in __mm_add()
363 new->color = IBV_RED; in __mm_add()
367 static void __mm_remove(struct ibv_mem_node *node) in __mm_remove() argument
369 struct ibv_mem_node *child, *parent, *sib, *tmp; in __mm_remove() local
372 if (node->left && node->right) { in __mm_remove()
373 tmp = node->left; in __mm_remove()
374 while (tmp->right) in __mm_remove()
375 tmp = tmp->right; in __mm_remove()
377 nodecol = tmp->color; in __mm_remove()
378 child = tmp->left; in __mm_remove()
379 tmp->color = node->color; in __mm_remove()
381 if (tmp->parent != node) { in __mm_remove()
382 parent = tmp->parent; in __mm_remove()
383 parent->right = tmp->left; in __mm_remove()
384 if (tmp->left) in __mm_remove()
385 tmp->left->parent = parent; 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()
409 if (child) in __mm_remove()
410 child->parent = parent; in __mm_remove()
412 if (parent->left == node) in __mm_remove()
413 parent->left = child; in __mm_remove()
415 parent->right = child; in __mm_remove()
417 mm_root = child; in __mm_remove()
420 free(node); in __mm_remove()
425 while ((!child || child->color == IBV_BLACK) && child != mm_root) { in __mm_remove()
426 if (parent->left == child) { in __mm_remove()
427 sib = parent->right; in __mm_remove()
429 if (sib->color == IBV_RED) { in __mm_remove()
430 parent->color = IBV_RED; in __mm_remove()
431 sib->color = IBV_BLACK; in __mm_remove()
433 sib = parent->right; in __mm_remove()
436 if ((!sib->left || sib->left->color == IBV_BLACK) && in __mm_remove()
437 (!sib->right || sib->right->color == IBV_BLACK)) { in __mm_remove()
438 sib->color = IBV_RED; in __mm_remove()
439 child = parent; in __mm_remove()
440 parent = child->parent; in __mm_remove()
442 if (!sib->right || sib->right->color == IBV_BLACK) { in __mm_remove()
443 if (sib->left) in __mm_remove()
444 sib->left->color = IBV_BLACK; in __mm_remove()
445 sib->color = IBV_RED; in __mm_remove()
447 sib = parent->right; in __mm_remove()
450 sib->color = parent->color; in __mm_remove()
451 parent->color = IBV_BLACK; in __mm_remove()
452 if (sib->right) in __mm_remove()
453 sib->right->color = IBV_BLACK; in __mm_remove()
455 child = mm_root; in __mm_remove()
459 sib = parent->left; in __mm_remove()
461 if (sib->color == IBV_RED) { in __mm_remove()
462 parent->color = IBV_RED; in __mm_remove()
463 sib->color = IBV_BLACK; in __mm_remove()
465 sib = parent->left; in __mm_remove()
468 if ((!sib->left || sib->left->color == IBV_BLACK) && in __mm_remove()
469 (!sib->right || sib->right->color == IBV_BLACK)) { in __mm_remove()
470 sib->color = IBV_RED; in __mm_remove()
471 child = parent; in __mm_remove()
472 parent = child->parent; in __mm_remove()
474 if (!sib->left || sib->left->color == IBV_BLACK) { in __mm_remove()
475 if (sib->right) in __mm_remove()
476 sib->right->color = IBV_BLACK; in __mm_remove()
477 sib->color = IBV_RED; in __mm_remove()
479 sib = parent->left; in __mm_remove()
482 sib->color = parent->color; in __mm_remove()
483 parent->color = IBV_BLACK; in __mm_remove()
484 if (sib->left) in __mm_remove()
485 sib->left->color = IBV_BLACK; in __mm_remove()
487 child = mm_root; in __mm_remove()
493 if (child) in __mm_remove()
494 child->color = IBV_BLACK; 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
532 new_node->start = cut_line; in split_range()
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()
559 * operations performed on the node.
561 static struct ibv_mem_node *undo_node(struct ibv_mem_node *node, in undo_node() argument
568 * node with the previous one, so we need to split them. in undo_node()
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
607 start = (uintptr_t) base & ~(range_page_size - 1); in ibv_madvise_range()
608 end = ((uintptr_t) (base + size + range_page_size - 1) & in ibv_madvise_range()
609 ~(range_page_size - 1)) - 1; in ibv_madvise_range()
613 inc = advice == MADV_DONTFORK ? 1 : -1; in ibv_madvise_range()
615 node = get_start_node(start, end, inc); in ibv_madvise_range()
616 if (!node) { in ibv_madvise_range()
617 ret = -1; 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()
624 ret = -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()
633 * and we merged this node with the previous in ibv_madvise_range()
635 * on start ... node->end (rather than in ibv_madvise_range()
636 * starting at node->start). 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()
660 if (!tmp || start > tmp->end) in ibv_madvise_range()
662 end = tmp->end; 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()
679 ret = -1; in ibv_madvise_range()