* [RFC PATCH 1/3] selftests: add rbtree selftests
@ 2019-12-24 12:12 Heiher
2019-12-24 12:12 ` [RFC PATCH 2/3] lib/rbtree: fix null pointer dereference in erase Heiher
` (2 more replies)
0 siblings, 3 replies; 4+ messages in thread
From: Heiher @ 2019-12-24 12:12 UTC (permalink / raw)
To: linux-kernel; +Cc: Heiher, Andrew Morton, Michel Lespinasse, Peter Zijlstra
This adds the selftest for rbtree. It will reproduce the crash at earsing.
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/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
diff --git a/tools/testing/selftests/Makefile b/tools/testing/selftests/Makefile
index b001c602414b..0e84ca3f207f 100644
--- a/tools/testing/selftests/Makefile
+++ b/tools/testing/selftests/Makefile
@@ -25,6 +25,7 @@ TARGETS += kcmp
TARGETS += kexec
TARGETS += kvm
TARGETS += lib
+TARGETS += lib/rbtree
TARGETS += livepatch
TARGETS += membarrier
TARGETS += memfd
diff --git a/tools/testing/selftests/lib/rbtree/.gitignore b/tools/testing/selftests/lib/rbtree/.gitignore
new file mode 100644
index 000000000000..4c9f82761fad
--- /dev/null
+++ b/tools/testing/selftests/lib/rbtree/.gitignore
@@ -0,0 +1 @@
+rbtree_test
diff --git a/tools/testing/selftests/lib/rbtree/Makefile b/tools/testing/selftests/lib/rbtree/Makefile
new file mode 100644
index 000000000000..68fa9dad24a1
--- /dev/null
+++ b/tools/testing/selftests/lib/rbtree/Makefile
@@ -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)
diff --git a/tools/testing/selftests/lib/rbtree/rbtree_test.c b/tools/testing/selftests/lib/rbtree/rbtree_test.c
new file mode 100644
index 000000000000..11420541071a
--- /dev/null
+++ b/tools/testing/selftests/lib/rbtree/rbtree_test.c
@@ -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
--
2.24.1
^ permalink raw reply related [flat|nested] 4+ messages in thread
* [RFC PATCH 2/3] lib/rbtree: fix null pointer dereference in erase
2019-12-24 12:12 [RFC PATCH 1/3] selftests: add rbtree selftests Heiher
@ 2019-12-24 12:12 ` Heiher
2019-12-24 12:12 ` [RFC PATCH 3/3] tools/rbtree: " Heiher
2019-12-24 17:00 ` [RFC PATCH 1/3] selftests: add rbtree selftests Hev
2 siblings, 0 replies; 4+ messages in thread
From: Heiher @ 2019-12-24 12:12 UTC (permalink / raw)
To: linux-kernel; +Cc: Heiher, Andrew Morton, Michel Lespinasse, Peter Zijlstra
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
^ permalink raw reply related [flat|nested] 4+ messages in thread
* [RFC PATCH 3/3] tools/rbtree: fix null pointer dereference in erase
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
2019-12-24 17:00 ` [RFC PATCH 1/3] selftests: add rbtree selftests Hev
2 siblings, 0 replies; 4+ messages in thread
From: Heiher @ 2019-12-24 12:12 UTC (permalink / raw)
To: linux-kernel; +Cc: Heiher, Andrew Morton, Michel Lespinasse, Peter Zijlstra
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
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [RFC PATCH 1/3] selftests: add rbtree selftests
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 ` [RFC PATCH 3/3] tools/rbtree: " Heiher
@ 2019-12-24 17:00 ` Hev
2 siblings, 0 replies; 4+ messages in thread
From: Hev @ 2019-12-24 17:00 UTC (permalink / raw)
To: linux-kernel; +Cc: Andrew Morton, Michel Lespinasse, Peter Zijlstra
Hi,
On Tue, Dec 24, 2019 at 8:12 PM Heiher <r@hev.cc> wrote:
>
> This adds the selftest for rbtree. It will reproduce the crash at earsing.
>
> 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/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
>
> diff --git a/tools/testing/selftests/Makefile b/tools/testing/selftests/Makefile
> index b001c602414b..0e84ca3f207f 100644
> --- a/tools/testing/selftests/Makefile
> +++ b/tools/testing/selftests/Makefile
> @@ -25,6 +25,7 @@ TARGETS += kcmp
> TARGETS += kexec
> TARGETS += kvm
> TARGETS += lib
> +TARGETS += lib/rbtree
> TARGETS += livepatch
> TARGETS += membarrier
> TARGETS += memfd
> diff --git a/tools/testing/selftests/lib/rbtree/.gitignore b/tools/testing/selftests/lib/rbtree/.gitignore
> new file mode 100644
> index 000000000000..4c9f82761fad
> --- /dev/null
> +++ b/tools/testing/selftests/lib/rbtree/.gitignore
> @@ -0,0 +1 @@
> +rbtree_test
> diff --git a/tools/testing/selftests/lib/rbtree/Makefile b/tools/testing/selftests/lib/rbtree/Makefile
> new file mode 100644
> index 000000000000..68fa9dad24a1
> --- /dev/null
> +++ b/tools/testing/selftests/lib/rbtree/Makefile
> @@ -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)
> diff --git a/tools/testing/selftests/lib/rbtree/rbtree_test.c b/tools/testing/selftests/lib/rbtree/rbtree_test.c
> new file mode 100644
> index 000000000000..11420541071a
> --- /dev/null
> +++ b/tools/testing/selftests/lib/rbtree/rbtree_test.c
> @@ -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
> --
> 2.24.1
>
Sorry, recall these patches.
It was my mistake. I forget to update the parent pointer at inserting. :(
--
Best regards!
Hev
https://hev.cc
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2019-12-24 17:00 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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 ` [RFC PATCH 3/3] tools/rbtree: " Heiher
2019-12-24 17:00 ` [RFC PATCH 1/3] selftests: add rbtree selftests Hev
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).