diff options
Diffstat (limited to 'tools/testing/radix-tree')
22 files changed, 120 insertions, 486 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 d1acd7d58850..8b3591a51e1f 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -1,77 +1,29 @@ # 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 -LIBS := slab.o find_bit.o bitmap.o hweight.o vsprintf.o -CORE_OFILES := xarray.o radix-tree.o idr.o linux.o test.o maple.o $(LIBS) -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) 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/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/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 c0a2bb785b92..000000000000 --- a/tools/testing/radix-tree/linux/kernel.h +++ /dev/null @@ -1,29 +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 schedule() -#define PAGE_SHIFT 12 - -#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 cd1cf05503b4..1873ddbe16cc 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -14,7 +14,7 @@ #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) @@ -120,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); @@ -144,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. */ @@ -161,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); @@ -277,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); } @@ -299,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++) { @@ -35847,6 +35848,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); } @@ -36224,6 +36226,97 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt) extern void test_kmem_cache_bulk(void); +/* 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; +} + void farmer_tests(void) { struct maple_node *node; @@ -36231,6 +36324,10 @@ 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); + tree.ma_root = xa_mk_value(0); mt_dump(&tree, mt_dump_dec); @@ -36257,6 +36354,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); 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 d0e53bff1eb6..253208a8541b 100644 --- a/tools/testing/radix-tree/xarray.c +++ b/tools/testing/radix-tree/xarray.c @@ -4,17 +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_DESCRIPTION(X) -#define MODULE_LICENSE(x) -#define dump_stack() assert(0) - -#include "../../../lib/xarray.c" #undef XA_DEBUG #include "../../../lib/test_xarray.c" |