Messages in this thread Patch in this message | | | From | Heiher <> | Subject | [RFC PATCH 1/3] selftests: add rbtree selftests | Date | Tue, 24 Dec 2019 20:12:08 +0800 |
| |
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
| |