Skip to contentSkip to conversation

selftests: add rbtree selftests

RFC PATCH In review Heiher 1 participant 4 messages Dec 24, 2019

Subsystems (2)
lore
Share & tools
lore

Heiher

author
#0 lore raw

RFC PATCH 1/3 selftests: add rbtree selftests

This adds the selftest for rbtree. It will reproduce the crash at earsing.

Cc Andrew Morton <[email protected]>
Cc Michel Lespinasse <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 tools/testing/selftests/Makefile              |  1 +
 tools/testing/selftests/lib/rbtree/.gitignore |  1 +
 tools/testing/selftests/lib/rbtree/Makefile   | 29 ++++++++
 .../selftests/lib/rbtree/rbtree_test.c        | 70 +++++++++++++++++++
 4 files changed, 101 insertions(+)
 create mode 100644 tools/testing/selftests/lib/rbtree/.gitignore
 create mode 100644 tools/testing/selftests/lib/rbtree/Makefile
 create mode 100644 tools/testing/selftests/lib/rbtree/rbtree_test.c
tools/testing/selftests/Makefile +1 -0
index b001c602414b..0e84ca3f207f 100644
@@ -25,6 +25,7 @@ TARGETS += kcmp
 TARGETS += kexec
 TARGETS += kvm
 TARGETS += lib
+TARGETS += lib/rbtree
 TARGETS += livepatch
 TARGETS += membarrier
 TARGETS += memfd
tools/testing/selftests/lib/rbtree/.gitignore new file +1 -0
new file mode 100644
index 000000000000..4c9f82761fad
@@ -0,0 +1 @@
+rbtree_test
tools/testing/selftests/lib/rbtree/Makefile new file +29 -0
new file mode 100644
index 000000000000..68fa9dad24a1
@@ -0,0 +1,29 @@
+# SPDX-License-Identifier: GPL-2.0
+
+CFLAGS += -I../../../../include/
+
+include ../../lib.mk
+
+# lib.mk TEST_CUSTOM_PROGS var is for custom tests that need special
+# build rules. lib.mk will run and install them.
+
+TEST_CUSTOM_PROGS := $(OUTPUT)/rbtree_test
+all: $(TEST_CUSTOM_PROGS)
+
+OBJS = rbtree_test.o
+
+LIBS = ../../../../lib/rbtree.o
+
+OBJS := $(patsubst %,$(OUTPUT)/%,$(OBJS))
+LIBS := $(patsubst %,$(OUTPUT)/%,$(LIBS))
+
+$(TEST_CUSTOM_PROGS): $(LIBS) $(OBJS)
+	$(CC) -o $(TEST_CUSTOM_PROGS) $(OBJS) $(LIBS) $(CFLAGS) $(LDFLAGS)
+
+$(OBJS): $(OUTPUT)/%.o: %.c
+	$(CC) -c $^ -o $@ $(CFLAGS)
+
+$(LIBS): $(OUTPUT)/%.o: %.c
+	$(CC) -c $^ -o $@ $(CFLAGS)
+
+EXTRA_CLEAN := $(TEST_CUSTOM_PROGS) $(OBJS) $(LIBS)
tools/testing/selftests/lib/rbtree/rbtree_test.c new file +70 -0

70 lines not on this page · raw message

Signature · 1 line
2.24.1
author
#1 lore raw

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

Cc Andrew Morton <[email protected]>
Cc Michel Lespinasse <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 lib/rbtree.c | 94 +++++++++++++++++++++++++++-------------------------
 1 file changed, 48 insertions(+), 46 deletions(-)
lib/rbtree.c +48 -46
index abc86c6a3177..a710c21f7be6 100644
@@ -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;
 		}
 	}
Signature · 1 line
2.24.1
author
#2 lore raw

RFC PATCH 3/3 tools/rbtree: fix null pointer dereference in erase

In reply to Heiher

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

Cc Andrew Morton <[email protected]>
Cc Michel Lespinasse <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 tools/lib/rbtree.c | 94 +++++++++++++++++++++++-----------------------
 1 file changed, 48 insertions(+), 46 deletions(-)
tools/lib/rbtree.c +48 -46
index 2548ff8c4d9c..8eb88439af57 100644
@@ -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;
 		}
 	}
Signature · 1 line
2.24.1
author
#3 lore raw
In reply to Heiher

Hi,

Quoted 148 lines · Heiher

This adds the selftest for rbtree. It will reproduce the crash at earsing.

Cc Andrew Morton <[email protected]>
Cc Michel Lespinasse <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 tools/testing/selftests/Makefile              |  1 +
 tools/testing/selftests/lib/rbtree/.gitignore |  1 +
 tools/testing/selftests/lib/rbtree/Makefile   | 29 ++++++++
 .../selftests/lib/rbtree/rbtree_test.c        | 70 +++++++++++++++++++
 4 files changed, 101 insertions(+)
 create mode 100644 tools/testing/selftests/lib/rbtree/.gitignore
 create mode 100644 tools/testing/selftests/lib/rbtree/Makefile
 create mode 100644 tools/testing/selftests/lib/rbtree/rbtree_test.c
tools/testing/selftests/Makefile +1 -0
index b001c602414b..0e84ca3f207f 100644
@@ -25,6 +25,7 @@ TARGETS += kcmp
 TARGETS += kexec
 TARGETS += kvm
 TARGETS += lib
+TARGETS += lib/rbtree
 TARGETS += livepatch
 TARGETS += membarrier
 TARGETS += memfd
tools/testing/selftests/lib/rbtree/.gitignore new file +1 -0
new file mode 100644
index 000000000000..4c9f82761fad
@@ -0,0 +1 @@
+rbtree_test
tools/testing/selftests/lib/rbtree/Makefile new file +29 -0
new file mode 100644
index 000000000000..68fa9dad24a1
@@ -0,0 +1,29 @@
+# SPDX-License-Identifier: GPL-2.0
+
+CFLAGS += -I../../../../include/
+
+include ../../lib.mk
+
+# lib.mk TEST_CUSTOM_PROGS var is for custom tests that need special
+# build rules. lib.mk will run and install them.
+
+TEST_CUSTOM_PROGS := $(OUTPUT)/rbtree_test
+all: $(TEST_CUSTOM_PROGS)
+
+OBJS = rbtree_test.o
+
+LIBS = ../../../../lib/rbtree.o
+
+OBJS := $(patsubst %,$(OUTPUT)/%,$(OBJS))
+LIBS := $(patsubst %,$(OUTPUT)/%,$(LIBS))
+
+$(TEST_CUSTOM_PROGS): $(LIBS) $(OBJS)
+       $(CC) -o $(TEST_CUSTOM_PROGS) $(OBJS) $(LIBS) $(CFLAGS) $(LDFLAGS)
+
+$(OBJS): $(OUTPUT)/%.o: %.c
+       $(CC) -c $^ -o $@ $(CFLAGS)
+
+$(LIBS): $(OUTPUT)/%.o: %.c
+       $(CC) -c $^ -o $@ $(CFLAGS)
+
+EXTRA_CLEAN := $(TEST_CUSTOM_PROGS) $(OBJS) $(LIBS)
tools/testing/selftests/lib/rbtree/rbtree_test.c new file +70 -1
new file mode 100644
index 000000000000..11420541071a
@@ -0,0 +1,70 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <stdlib.h>
+#include <linux/rbtree.h>
+#include "../../kselftest_harness.h"
+
+struct node {
+       struct rb_node node;
+       int key;
+};
+
+static int _insert(struct rb_root *tree, int key)
+{
+       struct rb_node **new = &tree->rb_node, *parent = NULL;
+       struct node *node;
+
+       while (*new) {
+               struct node *this = container_of(*new, struct node, node);
+
+               if (key < this->key)
+                       new = &((*new)->rb_left);
+               else if (key > this->key)
+                       new = &((*new)->rb_right);
+               else
+                       return 0;
+       }
+
+       node = malloc(sizeof(struct node));
+       if (!node)
+               return 0;
+
+       node->key = key;
+       rb_link_node(&node->node, parent, new);
+       rb_insert_color(&node->node, tree);
+
+       return 1;
+}
+
+static void _remove(struct rb_root *tree, int key)
+{
+       struct rb_node **node = &tree->rb_node;
+
+       while (*node) {
+               struct node *this = container_of(*node, struct node, node);
+
+               if (key < this->key) {
+                       node = &((*node)->rb_left);
+               } else if (key > this->key) {
+                       node = &((*node)->rb_right);
+               } else {
+                       rb_erase(&this->node, tree);
+                       free(this);
+                       return;
+               }
+       }
+}
+
+TEST(rbtree)
+{
+       struct rb_root tree = { 0 };
+
+       _insert(&tree, 2);
+       _insert(&tree, 1);
+       _insert(&tree, 4);
+       _insert(&tree, 3);
+
+       _remove(&tree, 2);
+}
+
+TEST_HARNESS_MAIN
--
Quoted 2 lines

2.24.1

Sorry, recall these patches.
It was my mistake. I forget to update the parent pointer at inserting. :(

Signature · 3 lines
Best regards!
Hev
https://hev.cc