Messages in this thread Patch in this message | | | From | Heiher <> | Subject | [RFC PATCH 2/3] lib/rbtree: fix null pointer dereference in erase | Date | Tue, 24 Dec 2019 20:12:09 +0800 |
| |
a null pointer dereference in erasing the root node of below tree.
Tree structure: (1)[2] / \ (2)[1] (3)[4] / (4)[3]
(n): Insert order [n]: Key value or key order
Signed-off-by: hev <r@hev.cc> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Michel Lespinasse <walken@google.com> Cc: Peter Zijlstra <peterz@infradead.org> --- lib/rbtree.c | 94 +++++++++++++++++++++++++++------------------------- 1 file changed, 48 insertions(+), 46 deletions(-)
diff --git a/lib/rbtree.c b/lib/rbtree.c index abc86c6a3177..a710c21f7be6 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -351,56 +351,58 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root, break; } else { sibling = parent->rb_left; - if (rb_is_red(sibling)) { - /* Case 1 - right rotate at parent */ - tmp1 = sibling->rb_right; - WRITE_ONCE(parent->rb_left, tmp1); - WRITE_ONCE(sibling->rb_right, parent); - rb_set_parent_color(tmp1, parent, RB_BLACK); - __rb_rotate_set_parents(parent, sibling, root, - RB_RED); - augment_rotate(parent, sibling); - sibling = tmp1; - } - tmp1 = sibling->rb_left; - if (!tmp1 || rb_is_black(tmp1)) { - tmp2 = sibling->rb_right; - if (!tmp2 || rb_is_black(tmp2)) { - /* Case 2 - sibling color flip */ - rb_set_parent_color(sibling, parent, - RB_RED); - if (rb_is_red(parent)) - rb_set_black(parent); - else { - node = parent; - parent = rb_parent(node); - if (parent) - continue; + if (sibling) { + if (rb_is_red(sibling)) { + /* Case 1 - right rotate at parent */ + tmp1 = sibling->rb_right; + WRITE_ONCE(parent->rb_left, tmp1); + WRITE_ONCE(sibling->rb_right, parent); + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, + RB_RED); + augment_rotate(parent, sibling); + sibling = tmp1; + } + tmp1 = sibling->rb_left; + if (!tmp1 || rb_is_black(tmp1)) { + tmp2 = sibling->rb_right; + if (!tmp2 || rb_is_black(tmp2)) { + /* Case 2 - sibling color flip */ + rb_set_parent_color(sibling, parent, + RB_RED); + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; } - break; + /* Case 3 - left rotate at sibling */ + tmp1 = tmp2->rb_left; + WRITE_ONCE(sibling->rb_right, tmp1); + WRITE_ONCE(tmp2->rb_left, sibling); + WRITE_ONCE(parent->rb_left, tmp2); + if (tmp1) + rb_set_parent_color(tmp1, sibling, + RB_BLACK); + augment_rotate(sibling, tmp2); + tmp1 = sibling; + sibling = tmp2; } - /* Case 3 - left rotate at sibling */ - tmp1 = tmp2->rb_left; - WRITE_ONCE(sibling->rb_right, tmp1); - WRITE_ONCE(tmp2->rb_left, sibling); + /* Case 4 - right rotate at parent + color flips */ + tmp2 = sibling->rb_right; WRITE_ONCE(parent->rb_left, tmp2); - if (tmp1) - rb_set_parent_color(tmp1, sibling, - RB_BLACK); - augment_rotate(sibling, tmp2); - tmp1 = sibling; - sibling = tmp2; + WRITE_ONCE(sibling->rb_right, parent); + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, + RB_BLACK); + augment_rotate(parent, sibling); } - /* Case 4 - right rotate at parent + color flips */ - tmp2 = sibling->rb_right; - WRITE_ONCE(parent->rb_left, tmp2); - WRITE_ONCE(sibling->rb_right, parent); - rb_set_parent_color(tmp1, sibling, RB_BLACK); - if (tmp2) - rb_set_parent(tmp2, parent); - __rb_rotate_set_parents(parent, sibling, root, - RB_BLACK); - augment_rotate(parent, sibling); break; } } -- 2.24.1
| |