selftests: add rbtree selftests
Subsystems (2)
RFC PATCH 1/3 selftests: add rbtree selftests
This adds the selftest for rbtree. It will reproduce the crash at earsing.
Signed-off-by hev <[email protected]>
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
@@ -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
@@ -0,0 +1 @@ +rbtree_test
tools/testing/selftests/lib/rbtree/Makefile new file +29 -0
@@ -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
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 <[email protected]>
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
@@ -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
RFC PATCH 3/3 tools/rbtree: fix null pointer dereference in erase
In reply to Heihera 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 <[email protected]>
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
@@ -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
Hi,
Quoted 148 lines · Heiher
This adds the selftest for rbtree. It will reproduce the crash at earsing.
Signed-off-by hev <[email protected]>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.ctools/testing/selftests/Makefile +1
-0@@ -25,6 +25,7 @@ TARGETS += kcmp TARGETS += kexec TARGETS += kvm TARGETS += lib +TARGETS += lib/rbtree TARGETS += livepatch TARGETS += membarrier TARGETS += memfdtools/testing/selftests/lib/rbtree/.gitignore new file +1
-0@@ -0,0 +1 @@ +rbtree_testtools/testing/selftests/lib/rbtree/Makefile new file +29
-0@@ -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@@ -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