linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Heiher <r@hev.cc>
To: linux-kernel@vger.kernel.org
Cc: Heiher <r@hev.cc>, Andrew Morton <akpm@linux-foundation.org>,
	Michel Lespinasse <walken@google.com>,
	Peter Zijlstra <peterz@infradead.org>
Subject: [RFC PATCH 3/3] tools/rbtree: fix null pointer dereference in erase
Date: Tue, 24 Dec 2019 20:12:10 +0800	[thread overview]
Message-ID: <20191224121210.29713-3-r@hev.cc> (raw)
In-Reply-To: <20191224121210.29713-1-r@hev.cc>

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>
---
 tools/lib/rbtree.c | 94 +++++++++++++++++++++++-----------------------
 1 file changed, 48 insertions(+), 46 deletions(-)

diff --git a/tools/lib/rbtree.c b/tools/lib/rbtree.c
index 2548ff8c4d9c..8eb88439af57 100644
--- a/tools/lib/rbtree.c
+++ b/tools/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


  parent reply	other threads:[~2019-12-24 12:12 UTC|newest]

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-12-24 12:12 [RFC PATCH 1/3] selftests: add rbtree selftests Heiher
2019-12-24 12:12 ` [RFC PATCH 2/3] lib/rbtree: fix null pointer dereference in erase Heiher
2019-12-24 12:12 ` Heiher [this message]
2019-12-24 17:00 ` [RFC PATCH 1/3] selftests: add rbtree selftests Hev

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20191224121210.29713-3-r@hev.cc \
    --to=r@hev.cc \
    --cc=akpm@linux-foundation.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=peterz@infradead.org \
    --cc=walken@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).