| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <20211019091349.39788-2-metepolat2000@gmail.com>
Date: Tue, 19 Oct 2021 11:13:48 +0200
From: Mete Polat <metepolat2000@...il.com>
To: Lukas Bulwahn <lukas.bulwahn@...il.com>,
Shuah Khan <shuah@...nel.org>,
Michel Lespinasse <michel@...pinasse.org>
Cc: Andrii Nakryiko <andrii@...nel.org>,
Alexei Starovoitov <ast@...nel.org>,
"David S. Miller" <davem@...emloft.net>,
Paolo Bonzini <pbonzini@...hat.com>,
Daniel Borkmann <daniel@...earbox.net>,
"Paul E. McKenney" <paulmck@...nel.org>,
linux-kernel@...r.kernel.org, Mete Polat <metepolat2000@...il.com>
Subject: [PATCH 1/2] rbtree: Expose a test tree to userspace
Expose rbtree manipulation functions on debugfs. These can be used for
testing the core rbtree implementation from userspace against a verified
oracle (a mathematically proven correct Red-Black tree):
<debugfs>/rbt_if/cmd
write:
0 = Reset rbtree (remove all nodes).
1 = Insert key (see other file) into rbtree.
2 = Delete key (see other file) from rbtree.
read:
Print tree.
<debugfs>/rbt_if/key
Read or write the key used for cmds
---
lib/Kconfig.debug | 19 +++++
lib/Makefile | 1 +
lib/test_rbtree_interface.c | 161 ++++++++++++++++++++++++++++++++++++
3 files changed, 181 insertions(+)
create mode 100644 lib/test_rbtree_interface.c
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 3266fef7cb53..675c1a9fab67 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2623,6 +2623,25 @@ config TEST_CLOCKSOURCE_WATCHDOG
If unsure, say N.
+config TEST_RBTREE_INTERFACE
+ tristate "Expose an Red-Black tree instance to userspace for testing"
+ depends on DEBUG_FS
+ help
+ Exposes rbtree maniplation functions on debugfs. These can be used for
+ testing the core rbtree implementation from userspace against a
+ verified oracle (a mathematically proven correct Red-Black tree):
+ <debugfs>/rbt_if/cmd
+ write:
+ 0 = Reset rbtree (remove all nodes).
+ 1 = Insert key (see other file) into rbtree.
+ 2 = Delete key (see other file) from rbtree.
+ read:
+ Print tree.
+ <debugfs>/rbt_if/key
+ Read or write the key used for cmds
+
+ If unsure, say N.
+
endif # RUNTIME_TESTING_MENU
config ARCH_USE_MEMTEST
diff --git a/lib/Makefile b/lib/Makefile
index b0cb89451cd3..8e563b959c60 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -100,6 +100,7 @@ obj-$(CONFIG_TEST_MEMINIT) += test_meminit.o
obj-$(CONFIG_TEST_LOCKUP) += test_lockup.o
obj-$(CONFIG_TEST_HMM) += test_hmm.o
obj-$(CONFIG_TEST_FREE_PAGES) += test_free_pages.o
+obj-$(CONFIG_TEST_RBTREE_INTERFACE) += test_rbtree_interface.o
#
# CFLAGS for compiling floating point code inside the kernel. x86/Makefile turns
diff --git a/lib/test_rbtree_interface.c b/lib/test_rbtree_interface.c
new file mode 100644
index 000000000000..627c41c78a7a
--- /dev/null
+++ b/lib/test_rbtree_interface.c
@@ -0,0 +1,161 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#define pr_fmt(fmt) "%s:%s: " fmt, KBUILD_MODNAME, __func__
+
+#include <linux/debugfs.h>
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/rbtree_augmented.h>
+#include <linux/seq_file.h>
+#include <linux/slab.h>
+#include <linux/types.h>
+
+enum Cmd { RESET, INSERT, DELETE };
+
+static struct dentry *rbt_if_root;
+static struct rb_root rbt = RB_ROOT;
+static u64 input_key;
+
+struct data {
+ struct rb_node node;
+ u64 key;
+};
+
+#define data_from_node(from) (rb_entry(from, struct data, node))
+
+#define print(...) seq_printf(m, __VA_ARGS__)
+#define print_parent print(" (%llu,%s) ", \
+ data_from_node(parent)->key, rb_is_red(parent) ? "Red" : "Black")
+
+static int cmd_show(struct seq_file *m, void *p)
+{
+ struct rb_node *node = rbt.rb_node, *parent = NULL;
+ bool left = false;
+ while(true) {
+ if (!node) {
+ print("Leaf");
+
+ if (!parent)
+ break;
+
+ if (left) {
+ print_parent;
+ node = parent->rb_right;
+ left = false;
+ } else {
+ while (rb_parent(parent) && parent->rb_right == node) {
+ print(")");
+ node = parent;
+ parent = rb_parent(node);
+ }
+
+ if (parent->rb_right == node)
+ break;
+
+ print_parent;
+ node = parent->rb_right;
+ left = false;
+ }
+ } else {
+ if (parent)
+ print("(");
+
+ print("Node ");
+ parent = node;
+ node = node->rb_left;
+ left = true;
+ }
+
+ }
+ print("\n");
+ return 0;
+}
+
+static int key_cmp(const void *_a, const struct rb_node *_b)
+{
+ u64 a = *(typeof(a) *) _a;
+ u64 b = data_from_node(_b)->key;
+ if (a < b)
+ return -1;
+ if (a > b)
+ return 1;
+ else
+ return 0;
+}
+
+static int node_cmp(struct rb_node *a, const struct rb_node *b)
+{
+ return key_cmp(&data_from_node(a)->key, b);
+}
+
+ssize_t cmd_exec(struct file *file, const char __user *ubuf, size_t len, loff_t *offp)
+{
+ int cmd;
+ struct data *data, *_n;
+ struct rb_node *node;
+ int ret = kstrtoint_from_user(ubuf, len, 10, &cmd);
+ if (ret)
+ return ret;
+
+ switch (cmd) {
+ case RESET:
+ rbtree_postorder_for_each_entry_safe(data, _n, &rbt, node)
+ kfree(data);
+ rbt = RB_ROOT;
+ break;
+ case INSERT:
+ data = kzalloc(sizeof(*data), GFP_KERNEL);
+ data->key = input_key;
+ rb_find_add(&data->node, &rbt, node_cmp);
+ break;
+ case DELETE:
+ node = rb_find(&input_key, &rbt, key_cmp);
+ if (!node)
+ break;
+ rb_erase(node, &rbt);
+ kfree(data_from_node(node));
+ break;
+ default:
+ return -EINVAL;
+ }
+ return len;
+}
+
+static int cmd_open(struct inode *inode, struct file *file)
+{
+ return single_open(file, cmd_show, inode->i_private);
+}
+
+static const struct file_operations cmd_fops = {
+ .owner = THIS_MODULE,
+ .open = cmd_open,
+ .read = seq_read,
+ .write = cmd_exec,
+ .llseek = seq_lseek,
+ .release = single_release,
+};
+
+int __init rbt_if_init(void)
+{
+ rbt_if_root = debugfs_create_dir("rbt_if", NULL);
+ if (IS_ERR(rbt_if_root))
+ return PTR_ERR(rbt_if_root);
+
+ debugfs_create_file("cmd", 0644, rbt_if_root, NULL, &cmd_fops);
+ debugfs_create_u64("key", 0644, rbt_if_root, &input_key);
+ return 0;
+}
+
+void __exit rbt_if_exit(void)
+{
+ struct data *_n, *pos;
+ debugfs_remove_recursive(rbt_if_root);
+ rbtree_postorder_for_each_entry_safe(pos, _n, &rbt, node)
+ kfree(pos);
+
+}
+
+module_init(rbt_if_init);
+module_exit(rbt_if_exit);
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Mete Polat <metepolat2000@...il.com>");
--
2.33.1
Powered by blists - more mailing lists