// SPDX-License-Identifier: GPL-2.0+/* * test_maple_tree.c: Test the maple tree API * Copyright (c) 2018-2022 Oracle Corporation * Author: Liam R. Howlett <liam@infradead.org> * * Any tests that only require the interface of the tree. */ #include <linux/maple_tree.h>#include <linux/module.h>#include <linux/rwsem.h> #define MTREE_ALLOC_MAX 0x2000000000000Ul#define CONFIG_MAPLE_SEARCH#define MAPLE_32BIT (MAPLE_NODE_SLOTS > 31) #ifndef CONFIG_DEBUG_MAPLE_TREE#define mt_dump(mt, fmt)		do {} while (0)#define mt_validate(mt)			do {} while (0)#define mt_cache_shrink()		do {} while (0)#define mas_dump(mas)			do {} while (0)#define mas_wr_dump(mas)		do {} while (0)atomic_t maple_tree_tests_run;atomic_t maple_tree_tests_passed;#undef MT_BUG_ON #define MT_BUG_ON(__tree, __x) do {					\	atomic_inc(&maple_tree_tests_run);				\	if (__x) {							\		pr_info("BUG at %s:%d (%u)\n",				\		__func__, __LINE__, __x);				\		pr_info("Pass: %u Run:%u\n",				\			atomic_read(&maple_tree_tests_passed),		\			atomic_read(&maple_tree_tests_run));		\	} else {							\		atomic_inc(&maple_tree_tests_passed);			\	}								\} while (0)#endif /* #define BENCH_SLOT_STORE *//* #define BENCH_NODE_STORE *//* #define BENCH_AWALK *//* #define BENCH_WALK *//* #define BENCH_LOAD *//* #define BENCH_MT_FOR_EACH *//* #define BENCH_FORK *//* #define BENCH_MAS_FOR_EACH *//* #define BENCH_MAS_PREV */ #ifdef __KERNEL__#define mt_set_non_kernel(x)		do {} while (0)#define mt_zero_nr_tallocated(x)	do {} while (0)#else#define cond_resched()			do {} while (0)#endif #define mas_is_none(x)		((x)->status == ma_none)#define mas_is_overflow(x)	((x)->status == ma_overflow)#define mas_is_underflow(x)	((x)->status == ma_underflow) static int __init mtree_insert_index(struct maple_tree *mt,				     unsigned long index, gfp_t gfp){	return mtree_insert(mt, index, xa_mk_value(index & LONG_MAX), gfp);} static void __init mtree_erase_index(struct maple_tree *mt, unsigned long index){	MT_BUG_ON(mt, mtree_erase(mt, index) != xa_mk_value(index & LONG_MAX));	MT_BUG_ON(mt, mtree_load(mt, index) != NULL);} static int __init mtree_test_insert(struct maple_tree *mt, unsigned long index,				void *ptr){	return mtree_insert(mt, index, ptr, GFP_KERNEL);} static int __init mtree_test_store_range(struct maple_tree *mt,			unsigned long start, unsigned long end, void *ptr){	return mtree_store_range(mt, start, end, ptr, GFP_KERNEL);} static int __init mtree_test_store(struct maple_tree *mt, unsigned long start,				void *ptr){	return mtree_test_store_range(mt, start, start, ptr);} static int __init mtree_test_insert_range(struct maple_tree *mt,			unsigned long start, unsigned long end, void *ptr){	return mtree_insert_range(mt, start, end, ptr, GFP_KERNEL);} static void __init *mtree_test_load(struct maple_tree *mt, unsigned long index){	return mtree_load(mt, index);} static void __init *mtree_test_erase(struct maple_tree *mt, unsigned long index){	return mtree_erase(mt, index);} #if defined(CONFIG_64BIT)static noinline void __init check_mtree_alloc_range(struct maple_tree *mt,		unsigned long start, unsigned long end, unsigned long size,		unsigned long expected, int eret, void *ptr){ 	unsigned long result = expected + 1;	int ret; 	ret = mtree_alloc_range(mt, &result, ptr, size, start, end,			GFP_KERNEL);	MT_BUG_ON(mt, ret != eret);	if (ret)		return; 	MT_BUG_ON(mt, result != expected);} static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt,		unsigned long start, unsigned long end, unsigned long size,		unsigned long expected, int eret, void *ptr){ 	unsigned long result = expected + 1;	int ret; 	ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end,			GFP_KERNEL);	MT_BUG_ON(mt, ret != eret);	if (ret)		return; 	MT_BUG_ON(mt, result != expected);}#endif static noinline void __init check_load(struct maple_tree *mt,				       unsigned long index, void *ptr){	void *ret = mtree_test_load(mt, index); 	if (ret != ptr)		pr_err("Load %lu returned %p expect %p\n", index, ret, ptr);	MT_BUG_ON(mt, ret != ptr);} static noinline void __init check_store_range(struct maple_tree *mt,		unsigned long start, unsigned long end, void *ptr, int expected){	int ret = -EINVAL;	unsigned long i; 	ret = mtree_test_store_range(mt, start, end, ptr);	MT_BUG_ON(mt, ret != expected); 	if (ret)		return; 	for (i = start; i <= end; i++)		check_load(mt, i, ptr);} static noinline void __init check_insert_range(struct maple_tree *mt,		unsigned long start, unsigned long end, void *ptr, int expected){	int ret = -EINVAL;	unsigned long i; 	ret = mtree_test_insert_range(mt, start, end, ptr);	MT_BUG_ON(mt, ret != expected); 	if (ret)		return; 	for (i = start; i <= end; i++)		check_load(mt, i, ptr);} static noinline void __init check_insert(struct maple_tree *mt,					 unsigned long index, void *ptr){	int ret = -EINVAL; 	ret = mtree_test_insert(mt, index, ptr);	MT_BUG_ON(mt, ret != 0);} static noinline void __init check_dup_insert(struct maple_tree *mt,				      unsigned long index, void *ptr){	int ret = -EINVAL; 	ret = mtree_test_insert(mt, index, ptr);	MT_BUG_ON(mt, ret != -EEXIST);}  static noinline void __init check_index_load(struct maple_tree *mt,					     unsigned long index){	return check_load(mt, index, xa_mk_value(index & LONG_MAX));} static inline __init int not_empty(struct maple_node *node){	int i; 	if (node->parent)		return 1; 	for (i = 0; i < ARRAY_SIZE(node->slot); i++)		if (node->slot[i])			return 1; 	return 0;}  static noinline void __init check_rev_seq(struct maple_tree *mt,					  unsigned long max, bool verbose){	unsigned long i = max, j; 	MT_BUG_ON(mt, !mtree_empty(mt)); 	mt_zero_nr_tallocated();	while (i) {		MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL));		for (j = i; j <= max; j++)			check_index_load(mt, j); 		check_load(mt, i - 1, NULL);		mt_set_in_rcu(mt);		MT_BUG_ON(mt, !mt_height(mt));		mt_clear_in_rcu(mt);		MT_BUG_ON(mt, !mt_height(mt));		i--;	}	check_load(mt, max + 1, NULL); #ifndef __KERNEL__	if (verbose) {		rcu_barrier();		mt_dump(mt, mt_dump_dec);		pr_info(" %s test of 0-%lu %luK in %d active (%d total)\n",			__func__, max, mt_get_alloc_size()/1024, mt_nr_allocated(),			mt_nr_tallocated());	}#endif} static noinline void __init check_seq(struct maple_tree *mt, unsigned long max,		bool verbose){	unsigned long i, j; 	MT_BUG_ON(mt, !mtree_empty(mt)); 	mt_zero_nr_tallocated();	for (i = 0; i <= max; i++) {		MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL));		for (j = 0; j <= i; j++)			check_index_load(mt, j); 		if (i)			MT_BUG_ON(mt, !mt_height(mt));		check_load(mt, i + 1, NULL);	} #ifndef __KERNEL__	if (verbose) {		rcu_barrier();		mt_dump(mt, mt_dump_dec);		pr_info(" seq test of 0-%lu %luK in %d active (%d total)\n",			max, mt_get_alloc_size()/1024, mt_nr_allocated(),			mt_nr_tallocated());	}#endif} static noinline void __init check_lb_not_empty(struct maple_tree *mt){	unsigned long i, j;	unsigned long huge = 4000UL * 1000 * 1000;  	i = huge;	while (i > 4096) {		check_insert(mt, i, (void *) i);		for (j = huge; j >= i; j /= 2) {			check_load(mt, j-1, NULL);			check_load(mt, j, (void *) j);			check_load(mt, j+1, NULL);		}		i /= 2;	}	mtree_destroy(mt);} static noinline void __init check_lower_bound_split(struct maple_tree *mt){	MT_BUG_ON(mt, !mtree_empty(mt));	check_lb_not_empty(mt);} static noinline void __init check_upper_bound_split(struct maple_tree *mt){	unsigned long i, j;	unsigned long huge; 	MT_BUG_ON(mt, !mtree_empty(mt)); 	if (MAPLE_32BIT)		huge = 2147483647UL;	else		huge = 4000UL * 1000 * 1000; 	i = 4096;	while (i < huge) {		check_insert(mt, i, (void *) i);		for (j = i; j >= huge; j *= 2) {			check_load(mt, j-1, NULL);			check_load(mt, j, (void *) j);			check_load(mt, j+1, NULL);		}		i *= 2;	}	mtree_destroy(mt);} static noinline void __init check_mid_split(struct maple_tree *mt){	unsigned long huge = 8000UL * 1000 * 1000; 	check_insert(mt, huge, (void *) huge);	check_insert(mt, 0, xa_mk_value(0));	check_lb_not_empty(mt);} static noinline void __init check_rev_find(struct maple_tree *mt){	int i, nr_entries = 200;	void *val;	MA_STATE(mas, mt, 0, 0); 	for (i = 0; i <= nr_entries; i++)		mtree_store_range(mt, i*10, i*10 + 5,				  xa_mk_value(i), GFP_KERNEL); 	rcu_read_lock();	mas_set(&mas, 1000);	val = mas_find_rev(&mas, 1000);	MT_BUG_ON(mt, val != xa_mk_value(100));	val = mas_find_rev(&mas, 1000);	MT_BUG_ON(mt, val != NULL); 	mas_set(&mas, 999);	val = mas_find_rev(&mas, 997);	MT_BUG_ON(mt, val != NULL); 	mas_set(&mas, 1000);	val = mas_find_rev(&mas, 900);	MT_BUG_ON(mt, val != xa_mk_value(100));	val = mas_find_rev(&mas, 900);	MT_BUG_ON(mt, val != xa_mk_value(99)); 	mas_set(&mas, 20);	val = mas_find_rev(&mas, 0);	MT_BUG_ON(mt, val != xa_mk_value(2));	val = mas_find_rev(&mas, 0);	MT_BUG_ON(mt, val != xa_mk_value(1));	val = mas_find_rev(&mas, 0);	MT_BUG_ON(mt, val != xa_mk_value(0));	val = mas_find_rev(&mas, 0);	MT_BUG_ON(mt, val != NULL);	rcu_read_unlock();} static noinline void __init check_find(struct maple_tree *mt){	unsigned long val = 0;	unsigned long count;	unsigned long max;	unsigned long top;	unsigned long last = 0, index = 0;	void *entry, *entry2; 	MA_STATE(mas, mt, 0, 0); 	/* Insert 0. */	MT_BUG_ON(mt, mtree_insert_index(mt, val++, GFP_KERNEL)); #if defined(CONFIG_64BIT)	top = 4398046511104UL;#else	top = ULONG_MAX;#endif 	if (MAPLE_32BIT) {		count = 15;	} else {		count = 20;	} 	for (int i = 0; i <= count; i++) {		if (val != 64)			MT_BUG_ON(mt, mtree_insert_index(mt, val, GFP_KERNEL));		else			MT_BUG_ON(mt, mtree_insert(mt, val,				XA_ZERO_ENTRY, GFP_KERNEL)); 		val <<= 2;	} 	val = 0;	mas_set(&mas, val);	mas_lock(&mas);	while ((entry = mas_find(&mas, 268435456)) != NULL) {		if (val != 64)			MT_BUG_ON(mt, xa_mk_value(val) != entry);		else			MT_BUG_ON(mt, entry != XA_ZERO_ENTRY); 		val <<= 2;		/* For zero check. */		if (!val)			val = 1;	}	mas_unlock(&mas); 	val = 0;	mas_set(&mas, val);	mas_lock(&mas);	mas_for_each(&mas, entry, ULONG_MAX) {		if (val != 64)			MT_BUG_ON(mt, xa_mk_value(val) != entry);		else			MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);		val <<= 2;		/* For zero check. */		if (!val)			val = 1;	}	mas_unlock(&mas); 	/* Test mas_pause */	val = 0;	mas_set(&mas, val);	mas_lock(&mas);	mas_for_each(&mas, entry, ULONG_MAX) {		if (val != 64)			MT_BUG_ON(mt, xa_mk_value(val) != entry);		else			MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);		val <<= 2;		/* For zero check. */		if (!val)			val = 1; 		mas_pause(&mas);		mas_unlock(&mas);		mas_lock(&mas);	}	mas_unlock(&mas); 	val = 0;	max = 300; /* A value big enough to include XA_ZERO_ENTRY at 64. */	mt_for_each(mt, entry, index, max) {		MT_BUG_ON(mt, xa_mk_value(val) != entry);		val <<= 2;		if (val == 64) /* Skip zero entry. */			val <<= 2;		/* For zero check. */		if (!val)			val = 1;	} 	val = 0;	max = 0;	index = 0;	MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL));	mt_for_each(mt, entry, index, ULONG_MAX) {		if (val == top)			MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX));		else			MT_BUG_ON(mt, xa_mk_value(val) != entry); 		/* Workaround for 32bit */		if ((val << 2) < val)			val = ULONG_MAX;		else			val <<= 2;

Lines 1–500 of 4026. Load more