From 18d2c25b1a2bfe645cf04d80f3b419f183c8a5dd Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 5 Feb 2019 12:30:13 -0500 Subject: [PATCH] ma_xa_benchmark: Initial push Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 1 + lib/maple_tree.c | 6 ++ lib/test_maple_tree.c | 6 +- lib/xarray.c | 6 ++ tools/testing/radix-tree/.gitignore | 1 + tools/testing/radix-tree/Makefile | 6 +- tools/testing/radix-tree/linux.c | 4 + tools/testing/radix-tree/ma_xa_benchmark.c | 85 ++++++++++++++++++++++ 8 files changed, 113 insertions(+), 2 deletions(-) create mode 100644 tools/testing/radix-tree/ma_xa_benchmark.c diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 3de603ee8631..5481cf0186a7 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -240,4 +240,5 @@ void *mas_find(struct ma_state *, unsigned long max); bool mas_nomem(struct ma_state *, gfp_t); void mas_pause(struct ma_state *); +void maple_tree_init(void); #endif diff --git a/lib/maple_tree.c b/lib/maple_tree.c index bf062e01f4cd..83600a0ba7d3 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1294,4 +1294,10 @@ void mt_set_non_kernel(unsigned int val) { kmem_cache_set_non_kernel(maple_node_cache, val); } + +extern unsigned long kmem_cache_get_alloc(struct kmem_cache *); +unsigned long mt_get_alloc_size(void) +{ + return kmem_cache_get_alloc(maple_node_cache); +} #endif diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 418556a3976a..721087b9f8fd 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -207,8 +207,12 @@ static noinline void check_seq(struct maple_tree *mt, unsigned long max, } check_load(mt, i + 1, NULL); } - if (verbose) + if (verbose) { + rcu_barrier(); mt_dump(mt); + printk(" seq test of 0-%lu used %luK in %d allocations\n", + max, mt_get_alloc_size()/1024, nr_allocated); + } mtree_destroy(mt); } diff --git a/lib/xarray.c b/lib/xarray.c index 446b956c9188..999302144839 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -2057,4 +2057,10 @@ void xa_dump(const struct xarray *xa) shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT; xa_dump_entry(entry, 0, shift); } + +extern unsigned long kmem_cache_get_alloc(struct kmem_cache *); +unsigned long xa_get_alloc_size(void) +{ + return kmem_cache_get_alloc(radix_tree_node_cachep); +} #endif diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore index 0a26b3850a46..85216f7d7b15 100644 --- a/tools/testing/radix-tree/.gitignore +++ b/tools/testing/radix-tree/.gitignore @@ -6,3 +6,4 @@ multiorder radix-tree.c xarray maple +ma_xa_benchmark diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 0aad7e2ec4c9..018f7c3426fa 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 ma_xa_benchmark 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 \ @@ -30,6 +30,8 @@ xarray: $(CORE_OFILES) maple: $(CORE_OFILES) +ma_xa_benchmark: ma_xa_benchmark.o $(CORE_OFILES) + multiorder: multiorder.o $(CORE_OFILES) clean: @@ -55,6 +57,8 @@ xarray.o: ../../../lib/xarray.c ../../../lib/test_xarray.c maple.o: ../../../lib/maple_tree.c ../../../lib/test_maple_tree.c +ma_xa_benchmark.o: + generated/map-shift.h: @if ! grep -qws $(SHIFT) generated/map-shift.h; then \ echo "#define XA_CHUNK_SHIFT $(SHIFT)" > \ diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c index c9937c9f002e..54f3d6cea0eb 100644 --- a/tools/testing/radix-tree/linux.c +++ b/tools/testing/radix-tree/linux.c @@ -32,6 +32,10 @@ void kmem_cache_set_non_kernel(struct kmem_cache *cachep, unsigned int val) cachep->non_kernel = val; } +unsigned long kmem_cache_get_alloc(struct kmem_cache *cachep) +{ + return cachep->size * nr_allocated; +} void *kmem_cache_alloc(struct kmem_cache *cachep, int gfp) { void *p; diff --git a/tools/testing/radix-tree/ma_xa_benchmark.c b/tools/testing/radix-tree/ma_xa_benchmark.c new file mode 100644 index 000000000000..91f2ae7bec7b --- /dev/null +++ b/tools/testing/radix-tree/ma_xa_benchmark.c @@ -0,0 +1,85 @@ +// SPDX-License-Identifier: GPL-2.0+ +/* + * ma_rdx_time.c: userspace time test of maple tree and radix tree. + * Copyright (c) 2019 Liam R. Howlett + */ + +#define MT_DEBUG +#define XA_DEBUG +#include "test.h" +#include + +#define module_init(x) +#define module_exit(x) +#define MODULE_AUTHOR(x) +#define MODULE_LICENSE(x) +#define dump_stack() assert(0) + +#include +#include + + + +extern unsigned long xa_get_alloc_size(void); +extern unsigned long mt_get_alloc_size(void); + +int __weak main(void) +{ + clock_t start, end; + double xa_t, mt_t; + unsigned long xa_m, mt_m; + void *entry; + unsigned long i, max = 100000; + + + radix_tree_init(); + DEFINE_XARRAY(xa); + entry = &xa; + + start = clock(); + for (i = 0; i <= max; i++) { + xa_store(&xa, i, entry, GFP_KERNEL); + } + end = clock(); + + for (i = 0; i <= max; i++) { + BUG_ON(entry != xa_load(&xa, i)); + } + /* xarray first */ + xa_t = ((double) (end - start)) / CLOCKS_PER_SEC; + xa_m = xa_get_alloc_size(); + printk("xa %lu inserts: %fs using %luK in %d allocations\n", + max, xa_t, xa_m/1024, nr_allocated); + + + xa_destroy(&xa); + radix_tree_cpu_dead(1); + rcu_barrier(); + BUG_ON(nr_allocated); + + /* Maple Tree tests*/ + maple_tree_init(); + DEFINE_MTREE(mt); + + start = clock(); + for (i = 0; i <= max; i++) { + mtree_insert(&mt, i, entry, GFP_KERNEL); + } + end = clock(); + for (i = 0; i <= max; i++) { + BUG_ON(entry != mtree_load(&mt, i)); + } + + /* xarray first */ + mt_t = ((double) (end - start)) / CLOCKS_PER_SEC; + mt_m = mt_get_alloc_size(); + printk("mt %lu inserts: %fs using %luK in %d allocations\n", + max, mt_t, mt_m/1024, nr_allocated); + mtree_destroy(&mt); + printk(" Delta : %f (%f%%)\n", xa_t - mt_t, (xa_t - mt_t)/(xa_t + mt_t) * 100); + rcu_barrier(); + if (nr_allocated) + printf("nr_allocated = %d\n", nr_allocated); + printk("Done\n"); + return 0; +} -- 2.50.1