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 1/3] selftests: add rbtree selftests
Date:   Tue, 24 Dec 2019 20:12:08 +0800
Message-Id: <20191224121210.29713-1-r@hev.cc>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

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