Re: [PATCH v6 08/71] Maple Tree: Add new data structure

[Vasily Gorbik <gor@linux.ibm.com>]

On Tue, Mar 01, 2022 at 08:39:44PM +0000, Liam Howlett wrote:
> * Vasily Gorbik <gor@linux.ibm.com> [220228 21:01]:
> > This condition is not present in mas_dead_leaves() where we potentially
> > iterate over all 16 slots, simply checking that we have a "valid" node pointer
> > with:
> > 
> > entry & ~MAPLE_NODE_MASK != 0
> 
> I have fixed this and another issue that Hugh pointed out [1].  I have
> been working on an s390 VM since you reported your issue and have been
> getting strange behaviour and have been able to detect the bug reported
> by Hugh with the config KASAN option.  With the fix I described above
> and fixing the do_mas_align_munmap() splitting order I broken in my
> linked list removal, I am now able to boot my s390 VM and log in with
> KASAN, VM debug, maple tree debug, rbtree debug, debug page flags, and
> Poison pages after freeing all set in the config I use.  I've pushed the
> fix to a tag on my branch [2] and I'd appreciate it if you could test it
> on your side.

Great, I gave it a spin and it looks much better now! I'll go run some stress
tests.

BTW, since you've made efforts to isolate mapple tests in userspace I
wonder how much sense it would make to use libfuzzer to give API some good
coverage-guided exercise.

I've written a minimal libfuzzer test (just a hack) for the "Normal API" and got
couple of flavours of crashes. Just rebased onto your latest branch state
and still get them. Please have a look if those are valid findings.

I use it the following way:
$ ./fuzz-maple
$ ./fuzz-maple -minimize_crash=1 ./crash-abdc5d14045d52b920d17c6818db7383e1a3ac84
$ V= ./fuzz-maple ./minimized-from-351a4f19a3b166974009662f657daba183e1ff0e

V= or V=1 for API calls trace:
mt_init_flags(&tree, 0);
// mtree_insert(&tree, 88, 0xb1, GFP_KERNEL);
   mtree_insert(&tree, 88, 0xb1, GFP_KERNEL); // 0
// mtree_insert(&tree, 84, 0xa9, GFP_KERNEL);
   mtree_insert(&tree, 84, 0xa9, GFP_KERNEL); // 0
// mtree_insert(&tree, 2, 0x5, GFP_KERNEL);
   mtree_insert(&tree, 2, 0x5, GFP_KERNEL); // 0
// mtree_insert(&tree, 4, 0x9, GFP_KERNEL);
   mtree_insert(&tree, 4, 0x9, GFP_KERNEL); // 0
// mtree_insert(&tree, 14, 0x1d, GFP_KERNEL);
   mtree_insert(&tree, 14, 0x1d, GFP_KERNEL); // 0
// mtree_insert(&tree, 7, 0xf, GFP_KERNEL);
   mtree_insert(&tree, 7, 0xf, GFP_KERNEL); // 0
// mtree_insert(&tree, 12, 0x19, GFP_KERNEL);
   mtree_insert(&tree, 12, 0x19, GFP_KERNEL); // 0
// mtree_insert(&tree, 18, 0x25, GFP_KERNEL);
   mtree_insert(&tree, 18, 0x25, GFP_KERNEL); // 0
// mtree_store_range(&tree, 8, 18, 0x11, GFP_KERNEL);
../../../lib/maple_tree.c:518:25: runtime error: member access within null pointer of type 'struct maple_node'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../../../lib/maple_tree.c:518:25 in
../../../lib/maple_tree.c:518:25: runtime error: member access within null pointer of type 'union maple_node::(anonymous at ./linux/../../../../include/linux/m
aple_tree.h:273:2)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../../../lib/maple_tree.c:518:25 in
../../../lib/maple_tree.c:518:25: runtime error: member access within null pointer of type 'struct maple_node::(anonymous at ./linux/../../../../include/linux/
maple_tree.h:274:3)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../../../lib/maple_tree.c:518:25 in
../../../lib/maple_tree.c:518:25: runtime error: load of null pointer of type 'struct maple_pnode *'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../../../lib/maple_tree.c:518:25 in
AddressSanitizer:DEADLYSIGNAL
=================================================================
==2657920==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x0000005525c3 bp 0x7ffccbdd93c0 sp 0x7ffccbdd93a0 T0)
==2657984==Hint: address points to the zero page.
    #0 0x5525c3 in mte_parent /devel/src/kernel/tools/testing/radix-tree/./../../../lib/maple_tree.c:518:33
    #1 0x5809e6 in mas_new_child /devel/src/kernel/tools/testing/radix-tree/./../../../lib/maple_tree.c:1716:7
    #2 0x57e619 in mas_descend_adopt /devel/src/kernel/tools/testing/radix-tree/./../../../lib/maple_tree.c:2013:23
    #3 0x5776be in mas_wmb_replace /devel/src/kernel/tools/testing/radix-tree/./../../../lib/maple_tree.c:2627:3
    #4 0x56a63a in mas_spanning_rebalance /devel/src/kernel/tools/testing/radix-tree/./../../../lib/maple_tree.c:2966:2
    #5 0x55b328 in mas_wr_spanning_store /devel/src/kernel/tools/testing/radix-tree/./../../../lib/maple_tree.c:3920:9
    #6 0x542cca in mas_wr_store_entry /devel/src/kernel/tools/testing/radix-tree/./../../../lib/maple_tree.c:4251:3
    #7 0x54bda7 in mtree_store_range /devel/src/kernel/tools/testing/radix-tree/./../../../lib/maple_tree.c:6000:2
    #8 0x596ae8 in maple_tree_tests /devel/src/kernel/tools/testing/radix-tree/fuzz-maple.c:77:8
    #9 0x557907 in LLVMFuzzerTestOneInput /devel/src/kernel/tools/testing/radix-tree/fuzz-maple.c:122:2
    #10 0x444354 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) /devel/src/llvm-project/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:595:17  
    #11 0x42bf03 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) /devel/src/llvm-project/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:323:21
    #12 0x431972 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) /devel/src/llvm-project/compiler-rt/lib/fuzzer/FuzzerDriv
er.cpp:848:19
    #13 0x41eba2 in main /devel/src/llvm-project/compiler-rt/lib/fuzzer/FuzzerMain.cpp:20:30
    #14 0x7f057f5241e1 in __libc_start_main (/lib64/libc.so.6+0x281e1)
    #15 0x41ebfd in _start (/devel/src/kernel/tools/testing/radix-tree/fuzz-maple+0x41ebfd)

V=2 for API calls trace + tree dumps
   mtree_insert(&tree, 18, 0x25, GFP_KERNEL); // 0
 ------------------------------------------------
 maple_tree(0x7fff6d216160) flags 8, height 2 root 0x617000000116
 0-18446744073709551615: node 0x617000000100 depth 0 type 2 parent 0x7fff6d216161 contents: 0x61700000040c 14 0x61500000060c 18446744073709551615 (nil) 0 (nil)
 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x1
   0-14: node 0x617000000400 depth 1 type 1 parent 0x617000000106 contents: (nil) 1 0x5 2 (nil) 3 0x9 4 (nil) 6 0xf 7 (nil) 11 0x19 12 (nil) 13 0x1d 14 (nil) 0
 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x9
     0-1: (nil)
     2: value 2 (0x2) [0x5]
     3: (nil)
     4: value 4 (0x4) [0x9]
     5-6: (nil)
     7: value 7 (0x7) [0xf]
     8-11: (nil)
     12: value 12 (0xc) [0x19]
     13: (nil)
     14: value 14 (0xe) [0x1d]
   15-18446744073709551615: node 0x615000000600 depth 1 type 1 parent 0x61700000010e contents: (nil) 17 0x25 18 (nil) 83 0xa9 84 (nil) 87 0xb1 88 (nil) 0 (nil)
 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x6
     15-17: (nil)
     18: value 18 (0x12) [0x25]
     19-83: (nil)
     84: value 84 (0x54) [0xa9]
     85-87: (nil)
     88: value 88 (0x58) [0xb1]
 // mtree_store_range(&tree, 8, 18, 0x11, GFP_KERNEL);
 ../../../lib/maple_tree.c:518:25: runtime error: member access within null pointer of type 'struct maple_node'

---
 tools/testing/radix-tree/.gitignore   |   2 +
 tools/testing/radix-tree/Makefile     |  17 +++-
 tools/testing/radix-tree/fuzz-maple.c | 128 ++++++++++++++++++++++++++
 tools/testing/radix-tree/linux.c      |   7 ++
 tools/testing/radix-tree/linux/slab.h |   1 +
 5 files changed, 154 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/radix-tree/fuzz-maple.c

diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore
index c901d96dd013..6a1ff525bb8d 100644
--- a/tools/testing/radix-tree/.gitignore
+++ b/tools/testing/radix-tree/.gitignore
@@ -7,4 +7,6 @@ multiorder
 radix-tree.c
 xarray
 maple
+fuzz-maple
+crash-*
 ma_xa_benchmark
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 3e0fa6ae0e0a..c74e6422aff7 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -4,7 +4,7 @@ CFLAGS += -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address \
 	  -fsanitize=undefined
 LDFLAGS += -fsanitize=address -fsanitize=undefined
 LDLIBS+= -lpthread -lurcu
-TARGETS = main idr-test multiorder xarray maple
+TARGETS = main idr-test multiorder xarray maple fuzz-maple
 CORE_OFILES := xarray.o radix-tree.o idr.o linux.o test.o find_bit.o bitmap.o maple.o
 OFILES = main.o $(CORE_OFILES) regression1.o regression2.o regression3.o \
 	 regression4.o tag_check.o multiorder.o idr-test.o iteration_check.o \
@@ -30,6 +30,21 @@ xarray: $(CORE_OFILES)
 
 maple: $(CORE_OFILES)
 
+fuzz-maple: fuzz-maple.c linux.c ../../../lib/maple_tree.c
+	clang $(CFLAGS) -fsanitize=fuzzer $(LDLIBS) -o fuzz-maple fuzz-maple.c linux.c
+
+CFLAGS_AFL += -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE
+AFL_HOME = /devel/src/afl-2.52b/
+LLVM_HOME = /devel/src/llvm-project
+AFL_LLVM_RT = $(AFL_HOME)/llvm_mode/afl-llvm-rt.o.c
+LLVM_AFL_DRIVER = $(LLVM_HOME)/compiler-rt/lib/fuzzer/afl/afl_driver.cpp
+
+afl-maple: fuzz-maple.c linux.c ../../../lib/maple_tree.c $(AFL_LLVM_RT) $(LLVM_AFL_DRIVER) generated/map-shift.h
+	clang $(CFLAGS_AFL) -fsanitize-coverage=trace-pc-guard -c -o afl-maple.o fuzz-maple.c
+	clang $(CFLAGS_AFL) -fsanitize-coverage=trace-pc-guard -c -o afl-linux.o linux.c
+	clang -c -w $(AFL_LLVM_RT) -o afl-llvm-rt.o
+	clang++ $(LLVM_AFL_DRIVER) afl-maple.o afl-linux.o afl-llvm-rt.o $(LDLIBS) -o afl-maple
+
 multiorder: multiorder.o $(CORE_OFILES)
 
 clean:
diff --git a/tools/testing/radix-tree/fuzz-maple.c b/tools/testing/radix-tree/fuzz-maple.c
new file mode 100644
index 000000000000..f47ec5d3440f
--- /dev/null
+++ b/tools/testing/radix-tree/fuzz-maple.c
@@ -0,0 +1,128 @@
+// SPDX-License-Identifier: GPL-2.0+
+
+#define CONFIG_DEBUG_MAPLE_TREE
+#define CONFIG_MAPLE_SEARCH
+#include "test.h"
+
+#define module_init(x)
+#define module_exit(x)
+#define MODULE_AUTHOR(x)
+#define MODULE_LICENSE(x)
+#define dump_stack()	assert(0)
+
+#include "../../../lib/maple_tree.c"
+#undef CONFIG_DEBUG_MAPLE_TREE
+
+static int gotdata = 1;
+static char *buf, *p;
+
+static unsigned long getl()
+{
+	char *tok = strtok(p, " ");
+	p = NULL;
+
+	if (!tok) {
+		gotdata = 0;
+		return 0;
+	}
+
+	return atol(tok);
+}
+
+#define v(x) (xa_mk_value(x & LONG_MAX))
+
+#define trace(...) printv(1, __VA_ARGS__)
+
+static void maple_tree_tests()
+{
+	unsigned long l1, l2;
+	void *e, *rl;
+	int r;
+	DEFINE_MTREE(tree);
+	trace("mt_init_flags(&tree, 0);\n");
+	mt_init_flags(&tree, 0);
+
+	while (gotdata) {
+		if (test_verbose > 1) {
+			pr_info("------------------------------------------------\n");
+			mt_dump(&tree);
+		}
+		switch (getl() % 7) {
+		case 0:
+			l1 = getl();
+			trace("// mtree_load(&tree, %lu);\n", l1);
+			rl = mtree_load(&tree, l1);
+			trace("   mtree_load(&tree, %lu); // %p\n", l1, rl);
+			break;
+		case 1:
+			l1 = getl();
+			e = v(l1);
+			trace("// mtree_insert(&tree, %lu, %p, GFP_KERNEL);\n", l1, e);
+			r = mtree_insert(&tree, l1, e, GFP_KERNEL);
+			trace("   mtree_insert(&tree, %lu, %p, GFP_KERNEL); // %d\n", l1, e, r);
+			break;
+		case 2:
+			l1 = getl();
+			l2 = getl();
+			e = v(l1);
+			trace("// mtree_insert_range(&tree, %lu, %lu, %p, GFP_KERNEL);\n", l1, l2, e);
+			r = mtree_insert_range(&tree, l1, l2, e, GFP_KERNEL);
+			trace("   mtree_insert_range(&tree, %lu, %lu, %p, GFP_KERNEL); // %d\n", l1, l2, e, r);
+			break;
+		case 3:
+			l1 = getl();
+			l2 = getl();
+			e = v(l1);
+			trace("// mtree_store_range(&tree, %lu, %lu, %p, GFP_KERNEL);\n", l1, l2, e);
+			r = mtree_store_range(&tree, l1, l2, e, GFP_KERNEL);
+			trace("   mtree_store_range(&tree, %lu, %lu, %p, GFP_KERNEL); // %d\n", l1, l2, e, r);
+			break;
+		case 4:
+			l1 = getl();
+			e = v(l1);
+			trace("// mtree_store(&tree, %lu, %p, GFP_KERNEL);\n", l1, e);
+			r = mtree_store(&tree, l1, e, GFP_KERNEL);
+			trace("   mtree_store(&tree, %lu, %p, GFP_KERNEL); // %d\n", l1, e, r);
+			break;
+		case 5:
+			l1 = getl();
+			trace("// mtree_erase(&tree, %lu);\n", l1);
+			rl = mtree_erase(&tree, l1);
+			trace("   mtree_erase(&tree, %lu); // %p\n", l1, rl);
+			break;
+		case 6:
+			trace("mtree_destroy(&tree);\n");
+			trace("mt_init_flags(&tree, 0);\n");
+			mtree_destroy(&tree);
+			mt_init_flags(&tree, 0);
+			break;
+		default:
+			break;
+		}
+	}
+
+	trace("mtree_destroy(&tree);\n");
+	mtree_destroy(&tree);
+}
+
+extern int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
+	char *v = getenv("V");
+	if (v)
+		test_verbose = atoi(v) ?: 1;
+	if (!size)
+		return 0;
+	buf = p = malloc(size + 1);
+	if (!buf)
+		return 0;
+	buf[size] = 0;
+	memcpy(buf, data, size);
+	gotdata = 1;
+	maple_tree_init();
+	maple_tree_tests();
+	rcu_barrier();
+	if (nr_allocated)
+		printf("nr_allocated = %d\n", nr_allocated);
+	kmem_cache_destroy(maple_node_cache);
+	free(buf);
+	return 0;
+}
diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c
index 3383d748c650..8d28f09caa8d 100644
--- a/tools/testing/radix-tree/linux.c
+++ b/tools/testing/radix-tree/linux.c
@@ -227,6 +227,13 @@ kmem_cache_create(const char *name, unsigned int size, unsigned int align,
 	return ret;
 }
 
+void kmem_cache_destroy(struct kmem_cache *s)
+{
+	if (!s)
+		return;
+	free(s);
+}
+
 /*
  * Test the test infrastructure for kem_cache_alloc/free and bulk counterparts.
  */
diff --git a/tools/testing/radix-tree/linux/slab.h b/tools/testing/radix-tree/linux/slab.h
index d7aed1cc6978..f440658b34cb 100644
--- a/tools/testing/radix-tree/linux/slab.h
+++ b/tools/testing/radix-tree/linux/slab.h
@@ -23,6 +23,7 @@ void kmem_cache_free(struct kmem_cache *cachep, void *objp);
 struct kmem_cache *kmem_cache_create(const char *name, unsigned int size,
 			unsigned int align, unsigned int flags,
 			void (*ctor)(void *));
+void kmem_cache_destroy(struct kmem_cache *s);
 
 void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list);
 int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,
-- 
2.35.1