diff options
Diffstat (limited to 'tools/testing/radix-tree')
25 files changed, 377 insertions, 514 deletions
diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore index 49bccb90c35b..ce167a761981 100644 --- a/tools/testing/radix-tree/.gitignore +++ b/tools/testing/radix-tree/.gitignore @@ -1,4 +1,5 @@ # SPDX-License-Identifier: GPL-2.0-only +generated/autoconf.h generated/bit-length.h generated/map-shift.h idr.c diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 7527f738b4a1..b2a6660bbd92 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -1,77 +1,30 @@ # SPDX-License-Identifier: GPL-2.0 -CFLAGS += -I. -I../../include -I../../../lib -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 -CORE_OFILES := xarray.o radix-tree.o idr.o linux.o test.o find_bit.o bitmap.o \ - slab.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 \ - iteration_check_2.o benchmark.o - -ifndef SHIFT - SHIFT=3 -endif +.PHONY: clean -ifeq ($(BUILD), 32) - CFLAGS += -m32 - LDFLAGS += -m32 -LONG_BIT := 32 -endif - -ifndef LONG_BIT -LONG_BIT := $(shell getconf LONG_BIT) -endif +TARGETS = main idr-test multiorder xarray maple +CORE_OFILES = $(SHARED_OFILES) xarray.o maple.o test.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 iteration_check_2.o benchmark.o targets: generated/map-shift.h generated/bit-length.h $(TARGETS) +include ../shared/shared.mk + main: $(OFILES) +xarray.o: ../../../lib/test_xarray.c idr-test.o: ../../../lib/test_ida.c idr-test: idr-test.o $(CORE_OFILES) -xarray: $(CORE_OFILES) +xarray: $(CORE_OFILES) xarray.o -maple: $(CORE_OFILES) +maple: $(CORE_OFILES) maple.o multiorder: multiorder.o $(CORE_OFILES) clean: - $(RM) $(TARGETS) *.o radix-tree.c idr.c generated/map-shift.h generated/bit-length.h - -vpath %.c ../../lib - -$(OFILES): Makefile *.h */*.h generated/map-shift.h generated/bit-length.h \ - ../../include/linux/*.h \ - ../../include/asm/*.h \ - ../../../include/linux/xarray.h \ - ../../../include/linux/maple_tree.h \ - ../../../include/linux/radix-tree.h \ - ../../../lib/radix-tree.h \ - ../../../include/linux/idr.h - -radix-tree.c: ../../../lib/radix-tree.c - sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@ - -idr.c: ../../../lib/idr.c - sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@ - -xarray.o: ../../../lib/xarray.c ../../../lib/test_xarray.c - -maple.o: ../../../lib/maple_tree.c ../../../lib/test_maple_tree.c - -generated/map-shift.h: - @if ! grep -qws $(SHIFT) generated/map-shift.h; then \ - echo "#define XA_CHUNK_SHIFT $(SHIFT)" > \ - generated/map-shift.h; \ - fi - -generated/bit-length.h: FORCE - @if ! grep -qws CONFIG_$(LONG_BIT)BIT generated/bit-length.h; then \ - echo "Generating $@"; \ - echo "#define CONFIG_$(LONG_BIT)BIT 1" > $@; \ - fi + $(RM) $(TARGETS) *.o radix-tree.c idr.c generated/* -FORCE: ; +$(OFILES): $(SHARED_DEPS) *.h diff --git a/tools/testing/radix-tree/bitmap.c b/tools/testing/radix-tree/bitmap.c deleted file mode 100644 index 66ec4a24a203..000000000000 --- a/tools/testing/radix-tree/bitmap.c +++ /dev/null @@ -1,23 +0,0 @@ -/* lib/bitmap.c pulls in at least two other files. */ - -#include <linux/bitmap.h> - -void bitmap_clear(unsigned long *map, unsigned int start, int len) -{ - unsigned long *p = map + BIT_WORD(start); - const unsigned int size = start + len; - int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); - unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); - - while (len - bits_to_clear >= 0) { - *p &= ~mask_to_clear; - len -= bits_to_clear; - bits_to_clear = BITS_PER_LONG; - mask_to_clear = ~0UL; - p++; - } - if (len) { - mask_to_clear &= BITMAP_LAST_WORD_MASK(size); - *p &= ~mask_to_clear; - } -} diff --git a/tools/testing/radix-tree/generated/autoconf.h b/tools/testing/radix-tree/generated/autoconf.h deleted file mode 100644 index 92dc474c349b..000000000000 --- a/tools/testing/radix-tree/generated/autoconf.h +++ /dev/null @@ -1,2 +0,0 @@ -#include "bit-length.h" -#define CONFIG_XARRAY_MULTI 1 diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index ca24f6839d50..84b8c3c92c79 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -424,6 +424,7 @@ void idr_checks(void) #define module_init(x) #define module_exit(x) #define MODULE_AUTHOR(x) +#define MODULE_DESCRIPTION(X) #define MODULE_LICENSE(x) #define dump_stack() assert(0) void ida_dump(struct ida *); diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c deleted file mode 100644 index 4eb442206d01..000000000000 --- a/tools/testing/radix-tree/linux.c +++ /dev/null @@ -1,271 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0 -#include <stdlib.h> -#include <string.h> -#include <malloc.h> -#include <pthread.h> -#include <unistd.h> -#include <assert.h> - -#include <linux/gfp.h> -#include <linux/poison.h> -#include <linux/slab.h> -#include <linux/radix-tree.h> -#include <urcu/uatomic.h> - -int nr_allocated; -int preempt_count; -int test_verbose; - -struct kmem_cache { - pthread_mutex_t lock; - unsigned int size; - unsigned int align; - int nr_objs; - void *objs; - void (*ctor)(void *); - unsigned int non_kernel; - unsigned long nr_allocated; - unsigned long nr_tallocated; -}; - -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 * cachep->nr_allocated; -} - -unsigned long kmem_cache_nr_allocated(struct kmem_cache *cachep) -{ - return cachep->nr_allocated; -} - -unsigned long kmem_cache_nr_tallocated(struct kmem_cache *cachep) -{ - return cachep->nr_tallocated; -} - -void kmem_cache_zero_nr_tallocated(struct kmem_cache *cachep) -{ - cachep->nr_tallocated = 0; -} - -void *kmem_cache_alloc_lru(struct kmem_cache *cachep, struct list_lru *lru, - int gfp) -{ - void *p; - - if (!(gfp & __GFP_DIRECT_RECLAIM)) { - if (!cachep->non_kernel) - return NULL; - - cachep->non_kernel--; - } - - pthread_mutex_lock(&cachep->lock); - if (cachep->nr_objs) { - struct radix_tree_node *node = cachep->objs; - cachep->nr_objs--; - cachep->objs = node->parent; - pthread_mutex_unlock(&cachep->lock); - node->parent = NULL; - p = node; - } else { - pthread_mutex_unlock(&cachep->lock); - if (cachep->align) - posix_memalign(&p, cachep->align, cachep->size); - else - p = malloc(cachep->size); - if (cachep->ctor) - cachep->ctor(p); - else if (gfp & __GFP_ZERO) - memset(p, 0, cachep->size); - } - - uatomic_inc(&cachep->nr_allocated); - uatomic_inc(&nr_allocated); - uatomic_inc(&cachep->nr_tallocated); - if (kmalloc_verbose) - printf("Allocating %p from slab\n", p); - return p; -} - -void __kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) -{ - assert(objp); - if (cachep->nr_objs > 10 || cachep->align) { - memset(objp, POISON_FREE, cachep->size); - free(objp); - } else { - struct radix_tree_node *node = objp; - cachep->nr_objs++; - node->parent = cachep->objs; - cachep->objs = node; - } -} - -void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) -{ - uatomic_dec(&nr_allocated); - uatomic_dec(&cachep->nr_allocated); - if (kmalloc_verbose) - printf("Freeing %p to slab\n", objp); - __kmem_cache_free_locked(cachep, objp); -} - -void kmem_cache_free(struct kmem_cache *cachep, void *objp) -{ - pthread_mutex_lock(&cachep->lock); - kmem_cache_free_locked(cachep, objp); - pthread_mutex_unlock(&cachep->lock); -} - -void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list) -{ - if (kmalloc_verbose) - pr_debug("Bulk free %p[0-%lu]\n", list, size - 1); - - pthread_mutex_lock(&cachep->lock); - for (int i = 0; i < size; i++) - kmem_cache_free_locked(cachep, list[i]); - pthread_mutex_unlock(&cachep->lock); -} - -void kmem_cache_shrink(struct kmem_cache *cachep) -{ -} - -int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, - void **p) -{ - size_t i; - - if (kmalloc_verbose) - pr_debug("Bulk alloc %lu\n", size); - - pthread_mutex_lock(&cachep->lock); - if (cachep->nr_objs >= size) { - struct radix_tree_node *node; - - for (i = 0; i < size; i++) { - if (!(gfp & __GFP_DIRECT_RECLAIM)) { - if (!cachep->non_kernel) - break; - cachep->non_kernel--; - } - - node = cachep->objs; - cachep->nr_objs--; - cachep->objs = node->parent; - p[i] = node; - node->parent = NULL; - } - pthread_mutex_unlock(&cachep->lock); - } else { - pthread_mutex_unlock(&cachep->lock); - for (i = 0; i < size; i++) { - if (!(gfp & __GFP_DIRECT_RECLAIM)) { - if (!cachep->non_kernel) - break; - cachep->non_kernel--; - } - - if (cachep->align) { - posix_memalign(&p[i], cachep->align, - cachep->size); - } else { - p[i] = malloc(cachep->size); - if (!p[i]) - break; - } - if (cachep->ctor) - cachep->ctor(p[i]); - else if (gfp & __GFP_ZERO) - memset(p[i], 0, cachep->size); - } - } - - if (i < size) { - size = i; - pthread_mutex_lock(&cachep->lock); - for (i = 0; i < size; i++) - __kmem_cache_free_locked(cachep, p[i]); - pthread_mutex_unlock(&cachep->lock); - return 0; - } - - for (i = 0; i < size; i++) { - uatomic_inc(&nr_allocated); - uatomic_inc(&cachep->nr_allocated); - uatomic_inc(&cachep->nr_tallocated); - if (kmalloc_verbose) - printf("Allocating %p from slab\n", p[i]); - } - - return size; -} - -struct kmem_cache * -kmem_cache_create(const char *name, unsigned int size, unsigned int align, - unsigned int flags, void (*ctor)(void *)) -{ - struct kmem_cache *ret = malloc(sizeof(*ret)); - - pthread_mutex_init(&ret->lock, NULL); - ret->size = size; - ret->align = align; - ret->nr_objs = 0; - ret->nr_allocated = 0; - ret->nr_tallocated = 0; - ret->objs = NULL; - ret->ctor = ctor; - ret->non_kernel = 0; - return ret; -} - -/* - * Test the test infrastructure for kem_cache_alloc/free and bulk counterparts. - */ -void test_kmem_cache_bulk(void) -{ - int i; - void *list[12]; - static struct kmem_cache *test_cache, *test_cache2; - - /* - * Testing the bulk allocators without aligned kmem_cache to force the - * bulk alloc/free to reuse - */ - test_cache = kmem_cache_create("test_cache", 256, 0, SLAB_PANIC, NULL); - - for (i = 0; i < 5; i++) - list[i] = kmem_cache_alloc(test_cache, __GFP_DIRECT_RECLAIM); - - for (i = 0; i < 5; i++) - kmem_cache_free(test_cache, list[i]); - assert(test_cache->nr_objs == 5); - - kmem_cache_alloc_bulk(test_cache, __GFP_DIRECT_RECLAIM, 5, list); - kmem_cache_free_bulk(test_cache, 5, list); - - for (i = 0; i < 12 ; i++) - list[i] = kmem_cache_alloc(test_cache, __GFP_DIRECT_RECLAIM); - - for (i = 0; i < 12; i++) - kmem_cache_free(test_cache, list[i]); - - /* The last free will not be kept around */ - assert(test_cache->nr_objs == 11); - - /* Aligned caches will immediately free */ - test_cache2 = kmem_cache_create("test_cache2", 128, 128, SLAB_PANIC, NULL); - - kmem_cache_alloc_bulk(test_cache2, __GFP_DIRECT_RECLAIM, 10, list); - kmem_cache_free_bulk(test_cache2, 10, list); - assert(!test_cache2->nr_objs); - - -} diff --git a/tools/testing/radix-tree/linux/bug.h b/tools/testing/radix-tree/linux/bug.h deleted file mode 100644 index 03dc8a57eb99..000000000000 --- a/tools/testing/radix-tree/linux/bug.h +++ /dev/null @@ -1,2 +0,0 @@ -#include <stdio.h> -#include "asm/bug.h" diff --git a/tools/testing/radix-tree/linux/cpu.h b/tools/testing/radix-tree/linux/cpu.h deleted file mode 100644 index a45530d78107..000000000000 --- a/tools/testing/radix-tree/linux/cpu.h +++ /dev/null @@ -1 +0,0 @@ -#define cpuhp_setup_state_nocalls(a, b, c, d) (0) diff --git a/tools/testing/radix-tree/linux/idr.h b/tools/testing/radix-tree/linux/idr.h deleted file mode 100644 index 4e342f2e37cf..000000000000 --- a/tools/testing/radix-tree/linux/idr.h +++ /dev/null @@ -1 +0,0 @@ -#include "../../../../include/linux/idr.h" diff --git a/tools/testing/radix-tree/linux/init.h b/tools/testing/radix-tree/linux/init.h deleted file mode 100644 index 81563c3dfce7..000000000000 --- a/tools/testing/radix-tree/linux/init.h +++ /dev/null @@ -1,2 +0,0 @@ -#define __init -#define __exit diff --git a/tools/testing/radix-tree/linux/kconfig.h b/tools/testing/radix-tree/linux/kconfig.h deleted file mode 100644 index 6c8675859913..000000000000 --- a/tools/testing/radix-tree/linux/kconfig.h +++ /dev/null @@ -1 +0,0 @@ -#include "../../../../include/linux/kconfig.h" diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h deleted file mode 100644 index c5c9d05f29da..000000000000 --- a/tools/testing/radix-tree/linux/kernel.h +++ /dev/null @@ -1,27 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ -#ifndef _KERNEL_H -#define _KERNEL_H - -#include "../../include/linux/kernel.h" -#include <string.h> -#include <stdio.h> -#include <limits.h> - -#include <linux/compiler.h> -#include <linux/err.h> -#include <linux/bitops.h> -#include <linux/log2.h> -#include "../../../include/linux/kconfig.h" - -#define printk printf -#define pr_err printk -#define pr_info printk -#define pr_debug printk -#define pr_cont printk - -#define __acquires(x) -#define __releases(x) -#define __must_hold(x) - -#define EXPORT_PER_CPU_SYMBOL_GPL(x) -#endif /* _KERNEL_H */ diff --git a/tools/testing/radix-tree/linux/kmemleak.h b/tools/testing/radix-tree/linux/kmemleak.h deleted file mode 100644 index 155f112786c4..000000000000 --- a/tools/testing/radix-tree/linux/kmemleak.h +++ /dev/null @@ -1 +0,0 @@ -static inline void kmemleak_update_trace(const void *ptr) { } diff --git a/tools/testing/radix-tree/linux/local_lock.h b/tools/testing/radix-tree/linux/local_lock.h deleted file mode 100644 index b3cf8b233ca4..000000000000 --- a/tools/testing/radix-tree/linux/local_lock.h +++ /dev/null @@ -1,8 +0,0 @@ -#ifndef _LINUX_LOCAL_LOCK -#define _LINUX_LOCAL_LOCK -typedef struct { } local_lock_t; - -static inline void local_lock(local_lock_t *lock) { } -static inline void local_unlock(local_lock_t *lock) { } -#define INIT_LOCAL_LOCK(x) { } -#endif diff --git a/tools/testing/radix-tree/linux/lockdep.h b/tools/testing/radix-tree/linux/lockdep.h deleted file mode 100644 index 62473ab57f99..000000000000 --- a/tools/testing/radix-tree/linux/lockdep.h +++ /dev/null @@ -1,16 +0,0 @@ -#ifndef _LINUX_LOCKDEP_H -#define _LINUX_LOCKDEP_H - -#include <linux/spinlock.h> - -struct lock_class_key { - unsigned int a; -}; - -static inline void lockdep_set_class(spinlock_t *lock, - struct lock_class_key *key) -{ -} - -extern int lockdep_is_held(const void *); -#endif /* _LINUX_LOCKDEP_H */ diff --git a/tools/testing/radix-tree/linux/maple_tree.h b/tools/testing/radix-tree/linux/maple_tree.h deleted file mode 100644 index 06c89bdcc515..000000000000 --- a/tools/testing/radix-tree/linux/maple_tree.h +++ /dev/null @@ -1,7 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0+ */ -#define atomic_t int32_t -#define atomic_inc(x) uatomic_inc(x) -#define atomic_read(x) uatomic_read(x) -#define atomic_set(x, y) do {} while (0) -#define U8_MAX UCHAR_MAX -#include "../../../../include/linux/maple_tree.h" diff --git a/tools/testing/radix-tree/linux/percpu.h b/tools/testing/radix-tree/linux/percpu.h deleted file mode 100644 index b2403aa743b2..000000000000 --- a/tools/testing/radix-tree/linux/percpu.h +++ /dev/null @@ -1,11 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ -#define DECLARE_PER_CPU(type, val) extern type val -#define DEFINE_PER_CPU(type, val) type val - -#define __get_cpu_var(var) var -#define this_cpu_ptr(var) var -#define this_cpu_read(var) var -#define this_cpu_xchg(var, val) uatomic_xchg(&var, val) -#define this_cpu_cmpxchg(var, old, new) uatomic_cmpxchg(&var, old, new) -#define per_cpu_ptr(ptr, cpu) ({ (void)(cpu); (ptr); }) -#define per_cpu(var, cpu) (*per_cpu_ptr(&(var), cpu)) diff --git a/tools/testing/radix-tree/linux/preempt.h b/tools/testing/radix-tree/linux/preempt.h deleted file mode 100644 index edb10302b903..000000000000 --- a/tools/testing/radix-tree/linux/preempt.h +++ /dev/null @@ -1,15 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ -#ifndef __LINUX_PREEMPT_H -#define __LINUX_PREEMPT_H - -extern int preempt_count; - -#define preempt_disable() uatomic_inc(&preempt_count) -#define preempt_enable() uatomic_dec(&preempt_count) - -static inline int in_interrupt(void) -{ - return 0; -} - -#endif /* __LINUX_PREEMPT_H */ diff --git a/tools/testing/radix-tree/linux/radix-tree.h b/tools/testing/radix-tree/linux/radix-tree.h deleted file mode 100644 index d1635a5bef02..000000000000 --- a/tools/testing/radix-tree/linux/radix-tree.h +++ /dev/null @@ -1,26 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ -#ifndef _TEST_RADIX_TREE_H -#define _TEST_RADIX_TREE_H - -#include "../../../../include/linux/radix-tree.h" - -extern int kmalloc_verbose; -extern int test_verbose; - -static inline void trace_call_rcu(struct rcu_head *head, - void (*func)(struct rcu_head *head)) -{ - if (kmalloc_verbose) - printf("Delaying free of %p to slab\n", (char *)head - - offsetof(struct radix_tree_node, rcu_head)); - call_rcu(head, func); -} - -#define printv(verbosity_level, fmt, ...) \ - if(test_verbose >= verbosity_level) \ - printf(fmt, ##__VA_ARGS__) - -#undef call_rcu -#define call_rcu(x, y) trace_call_rcu(x, y) - -#endif /* _TEST_RADIX_TREE_H */ diff --git a/tools/testing/radix-tree/linux/rcupdate.h b/tools/testing/radix-tree/linux/rcupdate.h deleted file mode 100644 index fed468fb0c78..000000000000 --- a/tools/testing/radix-tree/linux/rcupdate.h +++ /dev/null @@ -1,12 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ -#ifndef _RCUPDATE_H -#define _RCUPDATE_H - -#include <urcu.h> - -#define rcu_dereference_raw(p) rcu_dereference(p) -#define rcu_dereference_protected(p, cond) rcu_dereference(p) -#define rcu_dereference_check(p, cond) rcu_dereference(p) -#define RCU_INIT_POINTER(p, v) do { (p) = (v); } while (0) - -#endif diff --git a/tools/testing/radix-tree/linux/xarray.h b/tools/testing/radix-tree/linux/xarray.h deleted file mode 100644 index df3812cda376..000000000000 --- a/tools/testing/radix-tree/linux/xarray.h +++ /dev/null @@ -1,2 +0,0 @@ -#include "generated/map-shift.h" -#include "../../../../include/linux/xarray.h" diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index f1caf4bcf937..2c0b38301253 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -14,11 +14,12 @@ #include "test.h" #include <stdlib.h> #include <time.h> -#include "linux/init.h" +#include <linux/init.h> #define module_init(x) #define module_exit(x) #define MODULE_AUTHOR(x) +#define MODULE_DESCRIPTION(X) #define MODULE_LICENSE(x) #define dump_stack() assert(0) @@ -119,7 +120,7 @@ static noinline void __init check_new_node(struct maple_tree *mt) MT_BUG_ON(mt, mas.alloc->slot[0] == NULL); mas_push_node(&mas, mn); mas_reset(&mas); - mas_nomem(&mas, GFP_KERNEL); /* free */ + mas_destroy(&mas); mtree_unlock(mt); @@ -143,7 +144,7 @@ static noinline void __init check_new_node(struct maple_tree *mt) mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); mas.status = ma_start; - mas_nomem(&mas, GFP_KERNEL); + mas_destroy(&mas); /* Allocate 3 nodes, will fail. */ mas_node_count(&mas, 3); /* Drop the lock and allocate 3 nodes. */ @@ -160,7 +161,7 @@ static noinline void __init check_new_node(struct maple_tree *mt) MT_BUG_ON(mt, mas_allocated(&mas) != 3); /* Free. */ mas_reset(&mas); - mas_nomem(&mas, GFP_KERNEL); + mas_destroy(&mas); /* Set allocation request to 1. */ mas_set_alloc_req(&mas, 1); @@ -276,6 +277,7 @@ static noinline void __init check_new_node(struct maple_tree *mt) } mas_reset(&mas); MT_BUG_ON(mt, mas_nomem(&mas, GFP_KERNEL)); + mas_destroy(&mas); } @@ -298,7 +300,7 @@ static noinline void __init check_new_node(struct maple_tree *mt) } MT_BUG_ON(mt, mas_allocated(&mas) != total); mas_reset(&mas); - mas_nomem(&mas, GFP_KERNEL); /* Free. */ + mas_destroy(&mas); /* Free. */ MT_BUG_ON(mt, mas_allocated(&mas) != 0); for (i = 1; i < 128; i++) { @@ -460,6 +462,28 @@ static noinline void __init check_new_node(struct maple_tree *mt) MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1); mas_destroy(&mas); + mas.node = MA_ERROR(-ENOMEM); + mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */ + mas_nomem(&mas, GFP_KERNEL); /* Fill request */ + MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1); + mas.node = MA_ERROR(-ENOMEM); + mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 2); /* Request */ + mas_nomem(&mas, GFP_KERNEL); /* Fill request */ + mas.status = ma_start; + MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 2); + mas_destroy(&mas); + + mas.node = MA_ERROR(-ENOMEM); + mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 1); /* Request */ + mas_nomem(&mas, GFP_KERNEL); /* Fill request */ + MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 1); + mas.node = MA_ERROR(-ENOMEM); + mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 3 + 2); /* Request */ + mas_nomem(&mas, GFP_KERNEL); /* Fill request */ + mas.status = ma_start; + MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 3 + 2); + mas_destroy(&mas); + mtree_unlock(mt); } @@ -35451,15 +35475,65 @@ static void check_dfs_preorder(struct maple_tree *mt) } /* End of depth first search tests */ +/* get height of the lowest non-leaf node with free space */ +static unsigned char get_vacant_height(struct ma_wr_state *wr_mas, void *entry) +{ + struct ma_state *mas = wr_mas->mas; + char vacant_height = 0; + enum maple_type type; + unsigned long *pivots; + unsigned long min = 0; + unsigned long max = ULONG_MAX; + unsigned char offset; + + /* start traversal */ + mas_reset(mas); + mas_start(mas); + if (!xa_is_node(mas_root(mas))) + return 0; + + type = mte_node_type(mas->node); + wr_mas->type = type; + while (!ma_is_leaf(type)) { + mas_node_walk(mas, mte_to_node(mas->node), type, &min, &max); + offset = mas->offset; + mas->end = mas_data_end(mas); + pivots = ma_pivots(mte_to_node(mas->node), type); + + if (pivots) { + if (offset) + min = pivots[mas->offset - 1]; + if (offset < mas->end) + max = pivots[mas->offset]; + } + wr_mas->r_max = offset < mas->end ? pivots[offset] : mas->max; + + /* detect spanning write */ + if (mas_is_span_wr(wr_mas)) + break; + + if (mas->end < mt_slot_count(mas->node) - 1) + vacant_height = mas->depth + 1; + + mas_descend(mas); + type = mte_node_type(mas->node); + mas->depth++; + } + + return vacant_height; +} + /* Preallocation testing */ static noinline void __init check_prealloc(struct maple_tree *mt) { unsigned long i, max = 100; unsigned long allocated; unsigned char height; + unsigned char vacant_height; struct maple_node *mn; void *ptr = check_prealloc; MA_STATE(mas, mt, 10, 20); + MA_WR_STATE(wr_mas, &mas, ptr); mt_set_non_kernel(1000); for (i = 0; i <= max; i++) @@ -35470,8 +35544,9 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); + vacant_height = get_vacant_height(&wr_mas, ptr); MT_BUG_ON(mt, allocated == 0); - MT_BUG_ON(mt, allocated != 1 + height * 3); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); mas_destroy(&mas); allocated = mas_allocated(&mas); MT_BUG_ON(mt, allocated != 0); @@ -35479,8 +35554,9 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); + vacant_height = get_vacant_height(&wr_mas, ptr); MT_BUG_ON(mt, allocated == 0); - MT_BUG_ON(mt, allocated != 1 + height * 3); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); mas_destroy(&mas); allocated = mas_allocated(&mas); @@ -35490,7 +35566,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); - MT_BUG_ON(mt, allocated != 1 + height * 3); + vacant_height = get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); mn = mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); mn->parent = ma_parent_ptr(mn); @@ -35503,7 +35580,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); - MT_BUG_ON(mt, allocated != 1 + height * 3); + vacant_height = get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); mn = mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); @@ -35516,7 +35594,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); - MT_BUG_ON(mt, allocated != 1 + height * 3); + vacant_height = get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); mn = mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); mas_push_node(&mas, mn); @@ -35529,7 +35608,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); - MT_BUG_ON(mt, allocated != 1 + height * 3); + vacant_height = get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); mas_store_prealloc(&mas, ptr); MT_BUG_ON(mt, mas_allocated(&mas) != 0); @@ -35554,7 +35634,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); - MT_BUG_ON(mt, allocated != 1 + height * 2); + vacant_height = get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 2); mas_store_prealloc(&mas, ptr); MT_BUG_ON(mt, mas_allocated(&mas) != 0); mt_set_non_kernel(1); @@ -35571,8 +35652,14 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); + vacant_height = get_vacant_height(&wr_mas, ptr); MT_BUG_ON(mt, allocated == 0); - MT_BUG_ON(mt, allocated != 1 + height * 3); + /* + * vacant height cannot be used to compute the number of nodes needed + * as the root contains two entries which means it is on the verge of + * insufficiency. The worst case full height of the tree is needed. + */ + MT_BUG_ON(mt, allocated != height * 3 + 1); mas_store_prealloc(&mas, ptr); MT_BUG_ON(mt, mas_allocated(&mas) != 0); mas_set_range(&mas, 0, 200); @@ -35846,6 +35933,7 @@ static noinline void __init check_nomem(struct maple_tree *mt) mas_store(&ms, &ms); /* insert 1 -> &ms */ mas_nomem(&ms, GFP_KERNEL); /* Node allocated in here. */ mtree_unlock(mt); + mas_destroy(&ms); mtree_destroy(mt); } @@ -36223,6 +36311,158 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt) extern void test_kmem_cache_bulk(void); +static inline void check_spanning_store_height(struct maple_tree *mt) +{ + int index = 0; + MA_STATE(mas, mt, 0, 0); + mas_lock(&mas); + while (mt_height(mt) != 3) { + mas_store_gfp(&mas, xa_mk_value(index), GFP_KERNEL); + mas_set(&mas, ++index); + } + mas_set_range(&mas, 90, 140); + mas_store_gfp(&mas, xa_mk_value(index), GFP_KERNEL); + MT_BUG_ON(mt, mas_mt_height(&mas) != 2); + mas_unlock(&mas); +} + +/* + * Test to check the path of a spanning rebalance which results in + * a collapse where the rebalancing of the child node leads to + * insufficieny in the parent node. + */ +static void check_collapsing_rebalance(struct maple_tree *mt) +{ + int i = 0; + MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); + + /* create a height 6 tree */ + while (mt_height(mt) < 6) { + mtree_store_range(mt, i, i + 10, xa_mk_value(i), GFP_KERNEL); + i += 9; + } + + /* delete all entries one at a time, starting from the right */ + do { + mas_erase(&mas); + } while (mas_prev(&mas, 0) != NULL); + + mtree_unlock(mt); +} + +/* callback function used for check_nomem_writer_race() */ +static void writer2(void *maple_tree) +{ + struct maple_tree *mt = (struct maple_tree *)maple_tree; + MA_STATE(mas, mt, 6, 10); + + mtree_lock(mas.tree); + mas_store(&mas, xa_mk_value(0xC)); + mas_destroy(&mas); + mtree_unlock(mas.tree); +} + +/* + * check_nomem_writer_race() - test a possible race in the mas_nomem() path + * @mt: The tree to build. + * + * There is a possible race condition in low memory conditions when mas_nomem() + * gives up its lock. A second writer can chagne the entry that the primary + * writer executing the mas_nomem() path is modifying. This test recreates this + * scenario to ensure we are handling it correctly. + */ +static void check_nomem_writer_race(struct maple_tree *mt) +{ + MA_STATE(mas, mt, 0, 5); + + mt_set_non_kernel(0); + /* setup root with 2 values with NULL in between */ + mtree_store_range(mt, 0, 5, xa_mk_value(0xA), GFP_KERNEL); + mtree_store_range(mt, 6, 10, NULL, GFP_KERNEL); + mtree_store_range(mt, 11, 15, xa_mk_value(0xB), GFP_KERNEL); + + /* setup writer 2 that will trigger the race condition */ + mt_set_private(mt); + mt_set_callback(writer2); + + mtree_lock(mt); + /* erase 0-5 */ + mas_erase(&mas); + + /* index 6-10 should retain the value from writer 2 */ + check_load(mt, 6, xa_mk_value(0xC)); + mtree_unlock(mt); + + /* test for the same race but with mas_store_gfp() */ + mtree_store_range(mt, 0, 5, xa_mk_value(0xA), GFP_KERNEL); + mtree_store_range(mt, 6, 10, NULL, GFP_KERNEL); + + mas_set_range(&mas, 0, 5); + mtree_lock(mt); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + + /* ensure write made by writer 2 is retained */ + check_load(mt, 6, xa_mk_value(0xC)); + + mt_set_private(NULL); + mt_set_callback(NULL); + mtree_unlock(mt); +} + + /* test to simulate expanding a vma from [0x7fffffffe000, 0x7ffffffff000) + * to [0x7ffde4ca1000, 0x7ffffffff000) and then shrinking the vma to + * [0x7ffde4ca1000, 0x7ffde4ca2000) + */ +static inline int check_vma_modification(struct maple_tree *mt) +{ + MA_STATE(mas, mt, 0, 0); + + mtree_lock(mt); + /* vma with old start and old end */ + __mas_set_range(&mas, 0x7fffffffe000, 0x7ffffffff000 - 1); + mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL); + mas_store_prealloc(&mas, xa_mk_value(1)); + + /* next write occurs partly in previous range [0, 0x7fffffffe000)*/ + mas_prev_range(&mas, 0); + /* expand vma to {0x7ffde4ca1000, 0x7ffffffff000) */ + __mas_set_range(&mas, 0x7ffde4ca1000, 0x7ffffffff000 - 1); + mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL); + mas_store_prealloc(&mas, xa_mk_value(1)); + + /* shrink vma to [0x7ffde4ca1000, 7ffde4ca2000) */ + __mas_set_range(&mas, 0x7ffde4ca2000, 0x7ffffffff000 - 1); + mas_preallocate(&mas, NULL, GFP_KERNEL); + mas_store_prealloc(&mas, NULL); + mt_dump(mt, mt_dump_hex); + + mas_destroy(&mas); + mtree_unlock(mt); + return 0; +} + +/* + * test to check that bulk stores do not use wr_rebalance as the store + * type. + */ +static inline void check_bulk_rebalance(struct maple_tree *mt) +{ + MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); + int max = 10; + + build_full_tree(mt, 0, 2); + + /* erase every entry in the tree */ + do { + /* set up bulk store mode */ + mas_expected_entries(&mas, max); + mas_erase(&mas); + MT_BUG_ON(mt, mas.store_type == wr_rebalance); + } while (mas_prev(&mas, 0) != NULL); + + mas_destroy(&mas); +} + void farmer_tests(void) { struct maple_node *node; @@ -36230,6 +36470,14 @@ void farmer_tests(void) mt_dump(&tree, mt_dump_dec); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN | MT_FLAGS_USE_RCU); + check_vma_modification(&tree); + mtree_destroy(&tree); + + mt_init(&tree); + check_bulk_rebalance(&tree); + mtree_destroy(&tree); + tree.ma_root = xa_mk_value(0); mt_dump(&tree, mt_dump_dec); @@ -36256,6 +36504,10 @@ void farmer_tests(void) check_dfs_preorder(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_USE_RCU); + check_nomem_writer_race(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_prealloc(&tree); mtree_destroy(&tree); @@ -36265,6 +36517,14 @@ void farmer_tests(void) mtree_destroy(&tree); mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_spanning_store_height(&tree); + mtree_destroy(&tree); + + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_collapsing_rebalance(&tree); + mtree_destroy(&tree); + + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_null_expand(&tree); mtree_destroy(&tree); @@ -36304,9 +36564,93 @@ void farmer_tests(void) check_nomem(&tree); } +static unsigned long get_last_index(struct ma_state *mas) +{ + struct maple_node *node = mas_mn(mas); + enum maple_type mt = mte_node_type(mas->node); + unsigned long *pivots = ma_pivots(node, mt); + unsigned long last_index = mas_data_end(mas); + + BUG_ON(last_index == 0); + + return pivots[last_index - 1] + 1; +} + +/* + * Assert that we handle spanning stores that consume the entirety of the right + * leaf node correctly. + */ +static void test_spanning_store_regression(void) +{ + unsigned long from = 0, to = 0; + DEFINE_MTREE(tree); + MA_STATE(mas, &tree, 0, 0); + + /* + * Build a 3-level tree. We require a parent node below the root node + * and 2 leaf nodes under it, so we can span the entirety of the right + * hand node. + */ + build_full_tree(&tree, 0, 3); + + /* Descend into position at depth 2. */ + mas_reset(&mas); + mas_start(&mas); + mas_descend(&mas); + mas_descend(&mas); + + /* + * We need to establish a tree like the below. + * + * Then we can try a store in [from, to] which results in a spanned + * store across nodes B and C, with the maple state at the time of the + * write being such that only the subtree at A and below is considered. + * + * Height + * 0 Root Node + * / \ + * pivot = to / \ pivot = ULONG_MAX + * / \ + * 1 A [-----] ... + * / \ + * pivot = from / \ pivot = to + * / \ + * 2 (LEAVES) B [-----] [-----] C + * ^--- Last pivot to. + */ + while (true) { + unsigned long tmp = get_last_index(&mas); + + if (mas_next_sibling(&mas)) { + from = tmp; + to = mas.max; + } else { + break; + } + } + + BUG_ON(from == 0 && to == 0); + + /* Perform the store. */ + mas_set_range(&mas, from, to); + mas_store_gfp(&mas, xa_mk_value(0xdead), GFP_KERNEL); + + /* If the regression occurs, the validation will fail. */ + mt_validate(&tree); + + /* Cleanup. */ + __mt_destroy(&tree); +} + +static void regression_tests(void) +{ + test_spanning_store_regression(); +} + void maple_tree_tests(void) { #if !defined(BENCH) + regression_tests(); farmer_tests(); #endif maple_tree_seed(); diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c index cffaf2245d4f..eaff1b036989 100644 --- a/tools/testing/radix-tree/multiorder.c +++ b/tools/testing/radix-tree/multiorder.c @@ -227,6 +227,7 @@ static void *load_creator(void *ptr) unsigned long index = (3 << RADIX_TREE_MAP_SHIFT) - (1 << order); item_insert_order(tree, index, order); + xa_set_mark(tree, index, XA_MARK_1); item_delete_rcu(tree, index); } } @@ -242,8 +243,11 @@ static void *load_worker(void *ptr) rcu_register_thread(); while (!stop_iteration) { + unsigned long find_index = (2 << RADIX_TREE_MAP_SHIFT) + 1; struct item *item = xa_load(ptr, index); assert(!xa_is_internal(item)); + item = xa_find(ptr, &find_index, index, XA_MARK_1); + assert(!xa_is_internal(item)); } rcu_unregister_thread(); diff --git a/tools/testing/radix-tree/trace/events/maple_tree.h b/tools/testing/radix-tree/trace/events/maple_tree.h deleted file mode 100644 index 97d0e1ddcf08..000000000000 --- a/tools/testing/radix-tree/trace/events/maple_tree.h +++ /dev/null @@ -1,5 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0+ */ - -#define trace_ma_op(a, b) do {} while (0) -#define trace_ma_read(a, b) do {} while (0) -#define trace_ma_write(a, b, c, d) do {} while (0) diff --git a/tools/testing/radix-tree/xarray.c b/tools/testing/radix-tree/xarray.c index f20e12cbbfd4..253208a8541b 100644 --- a/tools/testing/radix-tree/xarray.c +++ b/tools/testing/radix-tree/xarray.c @@ -4,16 +4,9 @@ * Copyright (c) 2018 Matthew Wilcox <willy@infradead.org> */ -#define XA_DEBUG +#include "xarray-shared.h" #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/xarray.c" #undef XA_DEBUG #include "../../../lib/test_xarray.c" |