| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <20191224121210.29713-2-r@hev.cc>
Date: Tue, 24 Dec 2019 20:12:09 +0800
From: Heiher <r@....cc>
To: linux-kernel@...r.kernel.org
Cc: Heiher <r@....cc>, Andrew Morton <akpm@...ux-foundation.org>,
Michel Lespinasse <walken@...gle.com>,
Peter Zijlstra <peterz@...radead.org>
Subject: [RFC PATCH 2/3] lib/rbtree: fix null pointer dereference in erase
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@....cc>
Cc: Andrew Morton <akpm@...ux-foundation.org>
Cc: Michel Lespinasse <walken@...gle.com>
Cc: Peter Zijlstra <peterz@...radead.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
Powered by blists - more mailing lists