XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);	XA_BUG_ON(xa, id != base);	XA_BUG_ON(xa, xa_empty(xa));	xa_destroy(xa);	XA_BUG_ON(xa, !xa_empty(xa)); 	for (i = base; i < base + 10; i++) {		XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b,					GFP_KERNEL) != 0);		XA_BUG_ON(xa, id != i);	} 	XA_BUG_ON(xa, xa_store(xa, 3, xa_mk_index(3), GFP_KERNEL) != NULL);	XA_BUG_ON(xa, xa_store(xa, 4, xa_mk_index(4), GFP_KERNEL) != NULL);	XA_BUG_ON(xa, xa_store(xa, 4, NULL, GFP_KERNEL) != xa_mk_index(4));	XA_BUG_ON(xa, xa_erase(xa, 5) != NULL);	XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);	XA_BUG_ON(xa, id != 5); 	xa_for_each(xa, index, entry) {		xa_erase_index(xa, index);	} 	for (i = base; i < base + 9; i++) {		XA_BUG_ON(xa, xa_erase(xa, i) != NULL);		XA_BUG_ON(xa, xa_empty(xa));	}	XA_BUG_ON(xa, xa_erase(xa, 8) != NULL);	XA_BUG_ON(xa, xa_empty(xa));	XA_BUG_ON(xa, xa_erase(xa, base + 9) != NULL);	XA_BUG_ON(xa, !xa_empty(xa)); 	xa_destroy(xa);} static noinline void check_xa_alloc_3(struct xarray *xa, unsigned int base){	struct xa_limit limit = XA_LIMIT(1, 0x3fff);	u32 next = 0;	unsigned int i, id;	unsigned long index;	void *entry;	int ret; 	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(1), limit,				&next, GFP_KERNEL) != 0);	XA_BUG_ON(xa, id != 1); 	next = 0x3ffd;	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(0x3ffd), limit,				&next, GFP_KERNEL) != 0);	XA_BUG_ON(xa, id != 0x3ffd);	xa_erase_index(xa, 0x3ffd);	xa_erase_index(xa, 1);	XA_BUG_ON(xa, !xa_empty(xa)); 	for (i = 0x3ffe; i < 0x4003; i++) {		if (i < 0x4000)			entry = xa_mk_index(i);		else			entry = xa_mk_index(i - 0x3fff);		XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, entry, limit,					&next, GFP_KERNEL) != 0);		XA_BUG_ON(xa, xa_mk_index(id) != entry);	} 	/* Check wrap-around is handled correctly */	if (base != 0)		xa_erase_index(xa, base);	xa_erase_index(xa, base + 1);	next = UINT_MAX;	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(UINT_MAX),				xa_limit_32b, &next, GFP_KERNEL) != 0);	XA_BUG_ON(xa, id != UINT_MAX);	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base),				xa_limit_32b, &next, GFP_KERNEL) != 0);	XA_BUG_ON(xa, id != base);	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base + 1),				xa_limit_32b, &next, GFP_KERNEL) != 0);	XA_BUG_ON(xa, id != base + 1); 	xa_for_each(xa, index, entry)		xa_erase_index(xa, index);	XA_BUG_ON(xa, !xa_empty(xa)); 	/* check wrap-around return of __xa_alloc_cyclic() */	next = UINT_MAX;	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(UINT_MAX),				      xa_limit_32b, &next, GFP_KERNEL) != 0);	xa_lock(xa);	ret = __xa_alloc_cyclic(xa, &id, xa_mk_index(base), xa_limit_32b,				&next, GFP_KERNEL);	xa_unlock(xa);	XA_BUG_ON(xa, ret != 1);	xa_for_each(xa, index, entry)		xa_erase_index(xa, index);	XA_BUG_ON(xa, !xa_empty(xa));} static DEFINE_XARRAY_ALLOC(xa0);static DEFINE_XARRAY_ALLOC1(xa1); static noinline void check_xa_alloc(void){	check_xa_alloc_1(&xa0, 0);	check_xa_alloc_1(&xa1, 1);	check_xa_alloc_2(&xa0, 0);	check_xa_alloc_2(&xa1, 1);	check_xa_alloc_3(&xa0, 0);	check_xa_alloc_3(&xa1, 1);} static noinline void __check_store_iter(struct xarray *xa, unsigned long start,			unsigned int order, unsigned int present){	XA_STATE_ORDER(xas, xa, start, order);	void *entry;	unsigned int count = 0; retry:	xas_lock(&xas);	xas_for_each_conflict(&xas, entry) {		XA_BUG_ON(xa, !xa_is_value(entry));		XA_BUG_ON(xa, entry < xa_mk_index(start));		XA_BUG_ON(xa, entry > xa_mk_index(start + (1UL << order) - 1));		count++;	}	xas_store(&xas, xa_mk_index(start));	xas_unlock(&xas);	if (xas_nomem(&xas, GFP_KERNEL)) {		count = 0;		goto retry;	}	XA_BUG_ON(xa, xas_error(&xas));	XA_BUG_ON(xa, count != present);	XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_index(start));	XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=			xa_mk_index(start));	xa_erase_index(xa, start);} static noinline void check_store_iter(struct xarray *xa){	unsigned int i, j;	unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; 	for (i = 0; i < max_order; i++) {		unsigned int min = 1 << i;		unsigned int max = (2 << i) - 1;		__check_store_iter(xa, 0, i, 0);		XA_BUG_ON(xa, !xa_empty(xa));		__check_store_iter(xa, min, i, 0);		XA_BUG_ON(xa, !xa_empty(xa)); 		xa_store_index(xa, min, GFP_KERNEL);		__check_store_iter(xa, min, i, 1);		XA_BUG_ON(xa, !xa_empty(xa));		xa_store_index(xa, max, GFP_KERNEL);		__check_store_iter(xa, min, i, 1);		XA_BUG_ON(xa, !xa_empty(xa)); 		for (j = 0; j < min; j++)			xa_store_index(xa, j, GFP_KERNEL);		__check_store_iter(xa, 0, i, min);		XA_BUG_ON(xa, !xa_empty(xa));		for (j = 0; j < min; j++)			xa_store_index(xa, min + j, GFP_KERNEL);		__check_store_iter(xa, min, i, min);		XA_BUG_ON(xa, !xa_empty(xa));	}#ifdef CONFIG_XARRAY_MULTI	xa_store_index(xa, 63, GFP_KERNEL);	xa_store_index(xa, 65, GFP_KERNEL);	__check_store_iter(xa, 64, 2, 1);	xa_erase_index(xa, 63);#endif	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_multi_find_1(struct xarray *xa, unsigned order){#ifdef CONFIG_XARRAY_MULTI	unsigned long multi = 3 << order;	unsigned long next = 4 << order;	unsigned long index; 	xa_store_order(xa, multi, order, xa_mk_value(multi), GFP_KERNEL);	XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL) != NULL);	XA_BUG_ON(xa, xa_store_index(xa, next + 1, GFP_KERNEL) != NULL); 	index = 0;	XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=			xa_mk_value(multi));	XA_BUG_ON(xa, index != multi);	index = multi + 1;	XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=			xa_mk_value(multi));	XA_BUG_ON(xa, (index < multi) || (index >= next));	XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) !=			xa_mk_value(next));	XA_BUG_ON(xa, index != next);	XA_BUG_ON(xa, xa_find_after(xa, &index, next, XA_PRESENT) != NULL);	XA_BUG_ON(xa, index != next); 	xa_erase_index(xa, multi);	xa_erase_index(xa, next);	xa_erase_index(xa, next + 1);	XA_BUG_ON(xa, !xa_empty(xa));#endif} static noinline void check_multi_find_2(struct xarray *xa){	unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1;	unsigned int i, j;	void *entry; 	for (i = 0; i < max_order; i++) {		unsigned long index = 1UL << i;		for (j = 0; j < index; j++) {			XA_STATE(xas, xa, j + index);			xa_store_index(xa, index - 1, GFP_KERNEL);			xa_store_order(xa, index, i, xa_mk_index(index),					GFP_KERNEL);			rcu_read_lock();			xas_for_each(&xas, entry, ULONG_MAX) {				xa_erase_index(xa, index);			}			rcu_read_unlock();			xa_erase_index(xa, index - 1);			XA_BUG_ON(xa, !xa_empty(xa));		}	}} static noinline void check_multi_find_3(struct xarray *xa){	unsigned int order; 	for (order = 5; order < order_limit; order++) {		unsigned long index = 1UL << (order - 5); 		XA_BUG_ON(xa, !xa_empty(xa));		xa_store_order(xa, 0, order - 4, xa_mk_index(0), GFP_KERNEL);		XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT));		xa_erase_index(xa, 0);	}} static noinline void check_find_1(struct xarray *xa){	unsigned long i, j, k; 	XA_BUG_ON(xa, !xa_empty(xa)); 	/*	 * Check xa_find with all pairs between 0 and 99 inclusive,	 * starting at every index between 0 and 99	 */	for (i = 0; i < 100; i++) {		XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);		xa_set_mark(xa, i, XA_MARK_0);		for (j = 0; j < i; j++) {			XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) !=					NULL);			xa_set_mark(xa, j, XA_MARK_0);			for (k = 0; k < 100; k++) {				unsigned long index = k;				void *entry = xa_find(xa, &index, ULONG_MAX,								XA_PRESENT);				if (k <= j)					XA_BUG_ON(xa, index != j);				else if (k <= i)					XA_BUG_ON(xa, index != i);				else					XA_BUG_ON(xa, entry != NULL); 				index = k;				entry = xa_find(xa, &index, ULONG_MAX,								XA_MARK_0);				if (k <= j)					XA_BUG_ON(xa, index != j);				else if (k <= i)					XA_BUG_ON(xa, index != i);				else					XA_BUG_ON(xa, entry != NULL);			}			xa_erase_index(xa, j);			XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0));			XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));		}		xa_erase_index(xa, i);		XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0));	}	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_find_2(struct xarray *xa){	void *entry;	unsigned long i, j, index; 	xa_for_each(xa, index, entry) {		XA_BUG_ON(xa, true);	} 	for (i = 0; i < 1024; i++) {		xa_store_index(xa, index, GFP_KERNEL);		j = 0;		xa_for_each(xa, index, entry) {			XA_BUG_ON(xa, xa_mk_index(index) != entry);			XA_BUG_ON(xa, index != j++);		}	} 	xa_destroy(xa);} static noinline void check_find_3(struct xarray *xa){	XA_STATE(xas, xa, 0);	unsigned long i, j, k;	void *entry; 	for (i = 0; i < 100; i++) {		for (j = 0; j < 100; j++) {			rcu_read_lock();			for (k = 0; k < 100; k++) {				xas_set(&xas, j);				xas_for_each_marked(&xas, entry, k, XA_MARK_0)					;				if (j > k)					XA_BUG_ON(xa,						xas.xa_node != XAS_RESTART);			}			rcu_read_unlock();		}		xa_store_index(xa, i, GFP_KERNEL);		xa_set_mark(xa, i, XA_MARK_0);	}	xa_destroy(xa);} static noinline void check_find_4(struct xarray *xa){	unsigned long index = 0;	void *entry; 	xa_store_index(xa, ULONG_MAX, GFP_KERNEL); 	entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);	XA_BUG_ON(xa, entry != xa_mk_index(ULONG_MAX)); 	entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);	XA_BUG_ON(xa, entry); 	xa_erase_index(xa, ULONG_MAX);} static noinline void check_find(struct xarray *xa){	unsigned i; 	check_find_1(xa);	check_find_2(xa);	check_find_3(xa);	check_find_4(xa); 	for (i = 2; i < 10; i++)		check_multi_find_1(xa, i);	check_multi_find_2(xa);	check_multi_find_3(xa);} /* See find_swap_entry() in mm/shmem.c */static noinline unsigned long xa_find_entry(struct xarray *xa, void *item){	XA_STATE(xas, xa, 0);	unsigned int checked = 0;	void *entry; 	rcu_read_lock();	xas_for_each(&xas, entry, ULONG_MAX) {		if (xas_retry(&xas, entry))			continue;		if (entry == item)			break;		checked++;		if ((checked % 4) != 0)			continue;		xas_pause(&xas);	}	rcu_read_unlock(); 	return entry ? xas.xa_index : -1;} static noinline void check_find_entry(struct xarray *xa){#ifdef CONFIG_XARRAY_MULTI	unsigned int order;	unsigned long offset, index; 	for (order = 0; order < 20; order++) {		for (offset = 0; offset < (1UL << (order + 3));		     offset += (1UL << order)) {			for (index = 0; index < (1UL << (order + 5));			     index += (1UL << order)) {				xa_store_order(xa, index, order,						xa_mk_index(index), GFP_KERNEL);				XA_BUG_ON(xa, xa_load(xa, index) !=						xa_mk_index(index));				XA_BUG_ON(xa, xa_find_entry(xa,						xa_mk_index(index)) != index);			}			XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);			xa_destroy(xa);		}	}#endif 	XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);	xa_store_index(xa, ULONG_MAX, GFP_KERNEL);	XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);	XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_index(ULONG_MAX)) != -1);	xa_erase_index(xa, ULONG_MAX);	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_pause(struct xarray *xa){	XA_STATE(xas, xa, 0);	void *entry;	int order;	unsigned long index = 1;	unsigned int count = 0; 	for (order = 0; order < order_limit; order++) {		XA_BUG_ON(xa, xa_store_order(xa, index, order,					xa_mk_index(index), GFP_KERNEL));		index += 1UL << order;	} 	rcu_read_lock();	xas_for_each(&xas, entry, ULONG_MAX) {		XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));		count++;	}	rcu_read_unlock();	XA_BUG_ON(xa, count != order_limit); 	count = 0;	xas_set(&xas, 0);	rcu_read_lock();	xas_for_each(&xas, entry, ULONG_MAX) {		XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));		count++;		xas_pause(&xas);	}	rcu_read_unlock();	XA_BUG_ON(xa, count != order_limit); 	xa_destroy(xa); 	index = 0;	for (order = order_limit - 1; order >= 0; order--) {		XA_BUG_ON(xa, xa_store_order(xa, index, order,					xa_mk_index(index), GFP_KERNEL));		index += 1UL << order;	} 	index = 0;	count = 0;	xas_set(&xas, 0);	rcu_read_lock();	xas_for_each(&xas, entry, ULONG_MAX) {		XA_BUG_ON(xa, entry != xa_mk_index(index));		index += 1UL << (order_limit - count - 1);		count++;	}	rcu_read_unlock();	XA_BUG_ON(xa, count != order_limit); 	index = 0;	count = 0;	/* test unaligned index */	xas_set(&xas, 1 % (1UL << (order_limit - 1)));	rcu_read_lock();	xas_for_each(&xas, entry, ULONG_MAX) {		XA_BUG_ON(xa, entry != xa_mk_index(index));		index += 1UL << (order_limit - count - 1);		count++;		xas_pause(&xas);	}	rcu_read_unlock();	XA_BUG_ON(xa, count != order_limit); 	xa_destroy(xa); }

Lines 1001–1500 of 2278. Previous lines Load more