Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
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 2/3] lib/rbtree: fix null pointer dereference in erase
Date:   Tue, 24 Dec 2019 20:12:09 +0800
Message-Id: <20191224121210.29713-2-r@hev.cc>
In-Reply-To: <20191224121210.29713-1-r@hev.cc>
References: <20191224121210.29713-1-r@hev.cc>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

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