static noinline void check_move_tiny(struct xarray *xa){	XA_STATE(xas, xa, 0); 	XA_BUG_ON(xa, !xa_empty(xa));	rcu_read_lock();	XA_BUG_ON(xa, xas_next(&xas) != NULL);	XA_BUG_ON(xa, xas_next(&xas) != NULL);	rcu_read_unlock();	xa_store_index(xa, 0, GFP_KERNEL);	rcu_read_lock();	xas_set(&xas, 0);	XA_BUG_ON(xa, xas_next(&xas) != xa_mk_index(0));	XA_BUG_ON(xa, xas_next(&xas) != NULL);	xas_set(&xas, 0);	XA_BUG_ON(xa, xas_prev(&xas) != xa_mk_index(0));	XA_BUG_ON(xa, xas_prev(&xas) != NULL);	rcu_read_unlock();	xa_erase_index(xa, 0);	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_move_max(struct xarray *xa){	XA_STATE(xas, xa, 0); 	xa_store_index(xa, ULONG_MAX, GFP_KERNEL);	rcu_read_lock();	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);	rcu_read_unlock(); 	xas_set(&xas, 0);	rcu_read_lock();	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));	xas_pause(&xas);	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);	rcu_read_unlock(); 	xa_erase_index(xa, ULONG_MAX);	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_move_small(struct xarray *xa, unsigned long idx){	XA_STATE(xas, xa, 0);	unsigned long i; 	xa_store_index(xa, 0, GFP_KERNEL);	xa_store_index(xa, idx, GFP_KERNEL); 	rcu_read_lock();	for (i = 0; i < idx * 4; i++) {		void *entry = xas_next(&xas);		if (i <= idx)			XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);		XA_BUG_ON(xa, xas.xa_index != i);		if (i == 0 || i == idx)			XA_BUG_ON(xa, entry != xa_mk_index(i));		else			XA_BUG_ON(xa, entry != NULL);	}	xas_next(&xas);	XA_BUG_ON(xa, xas.xa_index != i); 	do {		void *entry = xas_prev(&xas);		i--;		if (i <= idx)			XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);		XA_BUG_ON(xa, xas.xa_index != i);		if (i == 0 || i == idx)			XA_BUG_ON(xa, entry != xa_mk_index(i));		else			XA_BUG_ON(xa, entry != NULL);	} while (i > 0); 	xas_set(&xas, ULONG_MAX);	XA_BUG_ON(xa, xas_next(&xas) != NULL);	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);	XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));	XA_BUG_ON(xa, xas.xa_index != 0);	XA_BUG_ON(xa, xas_prev(&xas) != NULL);	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);	rcu_read_unlock(); 	xa_erase_index(xa, 0);	xa_erase_index(xa, idx);	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_move(struct xarray *xa){	XA_STATE(xas, xa, (1 << 16) - 1);	unsigned long i; 	for (i = 0; i < (1 << 16); i++)		XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 	rcu_read_lock();	do {		void *entry = xas_prev(&xas);		i--;		XA_BUG_ON(xa, entry != xa_mk_index(i));		XA_BUG_ON(xa, i != xas.xa_index);	} while (i != 0); 	XA_BUG_ON(xa, xas_prev(&xas) != NULL);	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 	do {		void *entry = xas_next(&xas);		XA_BUG_ON(xa, entry != xa_mk_index(i));		XA_BUG_ON(xa, i != xas.xa_index);		i++;	} while (i < (1 << 16));	rcu_read_unlock(); 	for (i = (1 << 8); i < (1 << 15); i++)		xa_erase_index(xa, i); 	i = xas.xa_index; 	rcu_read_lock();	do {		void *entry = xas_prev(&xas);		i--;		if ((i < (1 << 8)) || (i >= (1 << 15)))			XA_BUG_ON(xa, entry != xa_mk_index(i));		else			XA_BUG_ON(xa, entry != NULL);		XA_BUG_ON(xa, i != xas.xa_index);	} while (i != 0); 	XA_BUG_ON(xa, xas_prev(&xas) != NULL);	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 	do {		void *entry = xas_next(&xas);		if ((i < (1 << 8)) || (i >= (1 << 15)))			XA_BUG_ON(xa, entry != xa_mk_index(i));		else			XA_BUG_ON(xa, entry != NULL);		XA_BUG_ON(xa, i != xas.xa_index);		i++;	} while (i < (1 << 16));	rcu_read_unlock(); 	xa_destroy(xa); 	check_move_tiny(xa);	check_move_max(xa); 	for (i = 0; i < 16; i++)		check_move_small(xa, 1UL << i); 	for (i = 2; i < 16; i++)		check_move_small(xa, (1UL << i) - 1);} static noinline void xa_store_many_order(struct xarray *xa,		unsigned long index, unsigned order){	XA_STATE_ORDER(xas, xa, index, order);	unsigned int i = 0; 	do {		xas_lock(&xas);		XA_BUG_ON(xa, xas_find_conflict(&xas));		xas_create_range(&xas);		if (xas_error(&xas))			goto unlock;		for (i = 0; i < (1U << order); i++) {			XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i)));			xas_next(&xas);		}unlock:		xas_unlock(&xas);	} while (xas_nomem(&xas, GFP_KERNEL)); 	XA_BUG_ON(xa, xas_error(&xas));} static noinline void check_create_range_1(struct xarray *xa,		unsigned long index, unsigned order){	unsigned long i; 	xa_store_many_order(xa, index, order);	for (i = index; i < index + (1UL << order); i++)		xa_erase_index(xa, i);	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_create_range_2(struct xarray *xa, unsigned order){	unsigned long i;	unsigned long nr = 1UL << order; 	for (i = 0; i < nr * nr; i += nr)		xa_store_many_order(xa, i, order);	for (i = 0; i < nr * nr; i++)		xa_erase_index(xa, i);	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_create_range_3(void){	XA_STATE(xas, NULL, 0);	xas_set_err(&xas, -EEXIST);	xas_create_range(&xas);	XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);} static noinline void check_create_range_4(struct xarray *xa,		unsigned long index, unsigned order){	XA_STATE_ORDER(xas, xa, index, order);	unsigned long base = xas.xa_index;	unsigned long i = 0; 	xa_store_index(xa, index, GFP_KERNEL);	do {		xas_lock(&xas);		xas_create_range(&xas);		if (xas_error(&xas))			goto unlock;		for (i = 0; i < (1UL << order); i++) {			void *old = xas_store(&xas, xa_mk_index(base + i));			if (xas.xa_index == index)				XA_BUG_ON(xa, old != xa_mk_index(base + i));			else				XA_BUG_ON(xa, old != NULL);			xas_next(&xas);		}unlock:		xas_unlock(&xas);	} while (xas_nomem(&xas, GFP_KERNEL)); 	XA_BUG_ON(xa, xas_error(&xas)); 	for (i = base; i < base + (1UL << order); i++)		xa_erase_index(xa, i);	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_create_range_5(struct xarray *xa,		unsigned long index, unsigned int order){	XA_STATE_ORDER(xas, xa, index, order);	unsigned int i; 	xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL); 	for (i = 0; i < order + 10; i++) {		do {			xas_lock(&xas);			xas_create_range(&xas);			xas_unlock(&xas);		} while (xas_nomem(&xas, GFP_KERNEL));	} 	xa_destroy(xa);} static noinline void check_create_range(struct xarray *xa){	unsigned int order;	unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1; 	for (order = 0; order < max_order; order++) {		check_create_range_1(xa, 0, order);		check_create_range_1(xa, 1U << order, order);		check_create_range_1(xa, 2U << order, order);		check_create_range_1(xa, 3U << order, order);		check_create_range_1(xa, 1U << 24, order);		if (order < 10)			check_create_range_2(xa, order); 		check_create_range_4(xa, 0, order);		check_create_range_4(xa, 1U << order, order);		check_create_range_4(xa, 2U << order, order);		check_create_range_4(xa, 3U << order, order);		check_create_range_4(xa, 1U << 24, order); 		check_create_range_4(xa, 1, order);		check_create_range_4(xa, (1U << order) + 1, order);		check_create_range_4(xa, (2U << order) + 1, order);		check_create_range_4(xa, (2U << order) - 1, order);		check_create_range_4(xa, (3U << order) + 1, order);		check_create_range_4(xa, (3U << order) - 1, order);		check_create_range_4(xa, (1U << 24) + 1, order); 		check_create_range_5(xa, 0, order);		check_create_range_5(xa, (1U << order), order);	} 	check_create_range_3();} static noinline void __check_store_range(struct xarray *xa, unsigned long first,		unsigned long last){#ifdef CONFIG_XARRAY_MULTI	xa_store_range(xa, first, last, xa_mk_index(first), GFP_KERNEL); 	XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_index(first));	XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_index(first));	XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL);	XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL); 	xa_store_range(xa, first, last, NULL, GFP_KERNEL);#endif 	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_store_range(struct xarray *xa){	unsigned long i, j; 	for (i = 0; i < 128; i++) {		for (j = i; j < 128; j++) {			__check_store_range(xa, i, j);			__check_store_range(xa, 128 + i, 128 + j);			__check_store_range(xa, 4095 + i, 4095 + j);			__check_store_range(xa, 4096 + i, 4096 + j);			__check_store_range(xa, 123456 + i, 123456 + j);			__check_store_range(xa, (1 << 24) + i, (1 << 24) + j);		}	}} #ifdef CONFIG_XARRAY_MULTIstatic void check_split_1(struct xarray *xa, unsigned long index,				unsigned int order, unsigned int new_order){	XA_STATE_ORDER(xas, xa, index, new_order);	unsigned int i, found;	void *entry; 	xa_store_order(xa, index, order, xa, GFP_KERNEL);	xa_set_mark(xa, index, XA_MARK_1); 	xas_split_alloc(&xas, xa, order, GFP_KERNEL);	xas_lock(&xas);	xas_split(&xas, xa, order);	for (i = 0; i < (1 << order); i += (1 << new_order))		__xa_store(xa, index + i, xa_mk_index(index + i), 0);	xas_unlock(&xas); 	for (i = 0; i < (1 << order); i++) {		unsigned int val = index + (i & ~((1 << new_order) - 1));		XA_BUG_ON(xa, xa_load(xa, index + i) != xa_mk_index(val));	} 	xa_set_mark(xa, index, XA_MARK_0);	XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0)); 	xas_set_order(&xas, index, 0);	found = 0;	rcu_read_lock();	xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_1) {		found++;		XA_BUG_ON(xa, xa_is_internal(entry));	}	rcu_read_unlock();	XA_BUG_ON(xa, found != 1 << (order - new_order)); 	xa_destroy(xa);} static void check_split_2(struct xarray *xa, unsigned long index,				unsigned int order, unsigned int new_order){	XA_STATE_ORDER(xas, xa, index, new_order);	unsigned int i, found;	void *entry; 	xa_store_order(xa, index, order, xa, GFP_KERNEL);	xa_set_mark(xa, index, XA_MARK_1); 	/* allocate a node for xas_try_split() */	xas_set_err(&xas, -ENOMEM);	XA_BUG_ON(xa, !xas_nomem(&xas, GFP_KERNEL)); 	xas_lock(&xas);	xas_try_split(&xas, xa, order);	if (((new_order / XA_CHUNK_SHIFT) < (order / XA_CHUNK_SHIFT)) &&	    new_order < order - 1) {		XA_BUG_ON(xa, !xas_error(&xas) || xas_error(&xas) != -EINVAL);		xas_unlock(&xas);		goto out;	}	for (i = 0; i < (1 << order); i += (1 << new_order))		__xa_store(xa, index + i, xa_mk_index(index + i), 0);	xas_unlock(&xas); 	for (i = 0; i < (1 << order); i++) {		unsigned int val = index + (i & ~((1 << new_order) - 1));		XA_BUG_ON(xa, xa_load(xa, index + i) != xa_mk_index(val));	} 	xa_set_mark(xa, index, XA_MARK_0);	XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0)); 	xas_set_order(&xas, index, 0);	found = 0;	rcu_read_lock();	xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_1) {		found++;		XA_BUG_ON(xa, xa_is_internal(entry));	}	rcu_read_unlock();	XA_BUG_ON(xa, found != 1 << (order - new_order));out:	xas_destroy(&xas);	xa_destroy(xa);} static noinline void check_split(struct xarray *xa){	unsigned int order, new_order; 	XA_BUG_ON(xa, !xa_empty(xa)); 	for (order = 1; order < 2 * XA_CHUNK_SHIFT; order++) {		for (new_order = 0; new_order < order; new_order++) {			check_split_1(xa, 0, order, new_order);			check_split_1(xa, 1UL << order, order, new_order);			check_split_1(xa, 3UL << order, order, new_order); 			check_split_2(xa, 0, order, new_order);			check_split_2(xa, 1UL << order, order, new_order);			check_split_2(xa, 3UL << order, order, new_order);		}	}}#elsestatic void check_split(struct xarray *xa) { }#endif static void check_align_1(struct xarray *xa, char *name){	int i;	unsigned int id;	unsigned long index;	void *entry; 	for (i = 0; i < 8; i++) {		XA_BUG_ON(xa, xa_alloc(xa, &id, name + i, xa_limit_32b,					GFP_KERNEL) != 0);		XA_BUG_ON(xa, id != i);	}	xa_for_each(xa, index, entry)		XA_BUG_ON(xa, xa_is_err(entry));	xa_destroy(xa);} /* * We should always be able to store without allocating memory after * reserving a slot. */static void check_align_2(struct xarray *xa, char *name){	int i; 	XA_BUG_ON(xa, !xa_empty(xa)); 	for (i = 0; i < 8; i++) {		XA_BUG_ON(xa, xa_store(xa, 0, name + i, GFP_KERNEL) != NULL);		xa_erase(xa, 0);	} 	for (i = 0; i < 8; i++) {		XA_BUG_ON(xa, xa_reserve(xa, 0, GFP_KERNEL) != 0);		XA_BUG_ON(xa, xa_store(xa, 0, name + i, 0) != NULL);		xa_erase(xa, 0);	} 	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_align(struct xarray *xa){	char name[] = "Motorola 68000"; 	check_align_1(xa, name);	check_align_1(xa, name + 1);	check_align_1(xa, name + 2);	check_align_1(xa, name + 3);	check_align_2(xa, name);} static LIST_HEAD(shadow_nodes); static void test_update_node(struct xa_node *node){	if (node->count && node->count == node->nr_values) {

Lines 1501–2000 of 2278. Previous lines Load more