XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);	XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, XA_ZERO_ENTRY,				xa_mk_value(12345678), GFP_NOWAIT) != NULL);	xa_release(xa, 12345678);	xa_erase_index(xa, 12345678);	XA_BUG_ON(xa, !xa_empty(xa)); 	/* xa_insert treats it as busy */	XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);	XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) !=			-EBUSY);	XA_BUG_ON(xa, xa_empty(xa));	XA_BUG_ON(xa, xa_erase(xa, 12345678) != NULL);	XA_BUG_ON(xa, !xa_empty(xa)); 	/* Can iterate through a reserved entry */	xa_store_index(xa, 5, GFP_KERNEL);	XA_BUG_ON(xa, xa_reserve(xa, 6, GFP_KERNEL) != 0);	xa_store_index(xa, 7, GFP_KERNEL); 	count = 0;	xa_for_each(xa, index, entry) {		XA_BUG_ON(xa, index != 5 && index != 7);		count++;	}	XA_BUG_ON(xa, count != 2); 	/* If we free a reserved entry, we should be able to allocate it */	if (xa->xa_flags & XA_FLAGS_ALLOC) {		u32 id; 		XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(8),					XA_LIMIT(5, 10), GFP_KERNEL) != 0);		XA_BUG_ON(xa, id != 8); 		xa_release(xa, 6);		XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(6),					XA_LIMIT(5, 10), GFP_KERNEL) != 0);		XA_BUG_ON(xa, id != 6);	} 	xa_destroy(xa);} static noinline void check_xas_erase(struct xarray *xa){	XA_STATE(xas, xa, 0);	void *entry;	unsigned long i, j; 	for (i = 0; i < 200; i++) {		for (j = i; j < 2 * i + 17; j++) {			xas_set(&xas, j);			do {				xas_lock(&xas);				xas_store(&xas, xa_mk_index(j));				xas_unlock(&xas);			} while (xas_nomem(&xas, GFP_KERNEL));		} 		xas_set(&xas, ULONG_MAX);		do {			xas_lock(&xas);			xas_store(&xas, xa_mk_value(0));			xas_unlock(&xas);		} while (xas_nomem(&xas, GFP_KERNEL)); 		xas_lock(&xas);		xas_store(&xas, NULL); 		xas_set(&xas, 0);		j = i;		xas_for_each(&xas, entry, ULONG_MAX) {			XA_BUG_ON(xa, entry != xa_mk_index(j));			xas_store(&xas, NULL);			j++;		}		xas_unlock(&xas);		XA_BUG_ON(xa, !xa_empty(xa));	}} #ifdef CONFIG_XARRAY_MULTIstatic noinline void check_multi_store_1(struct xarray *xa, unsigned long index,		unsigned int order){	XA_STATE(xas, xa, index);	unsigned long min = index & ~((1UL << order) - 1);	unsigned long max = min + (1UL << order); 	xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);	XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(index));	XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(index));	XA_BUG_ON(xa, xa_load(xa, max) != NULL);	XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL); 	xas_lock(&xas);	XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(min)) != xa_mk_index(index));	xas_unlock(&xas);	XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(min));	XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(min));	XA_BUG_ON(xa, xa_load(xa, max) != NULL);	XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL); 	xa_erase_index(xa, min);	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_multi_store_2(struct xarray *xa, unsigned long index,		unsigned int order){	XA_STATE(xas, xa, index);	xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL); 	xas_lock(&xas);	XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0));	XA_BUG_ON(xa, xas.xa_index != index);	XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));	xas_unlock(&xas);	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_multi_store_3(struct xarray *xa, unsigned long index,		unsigned int order){	XA_STATE(xas, xa, 0);	void *entry;	int n = 0; 	xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL); 	xas_lock(&xas);	xas_for_each(&xas, entry, ULONG_MAX) {		XA_BUG_ON(xa, entry != xa_mk_index(index));		n++;	}	XA_BUG_ON(xa, n != 1);	xas_set(&xas, index + 1);	xas_for_each(&xas, entry, ULONG_MAX) {		XA_BUG_ON(xa, entry != xa_mk_index(index));		n++;	}	XA_BUG_ON(xa, n != 2);	xas_unlock(&xas); 	xa_destroy(xa);}#endif static noinline void check_multi_store(struct xarray *xa){#ifdef CONFIG_XARRAY_MULTI	unsigned long i, j, k;	unsigned int max_order = (sizeof(long) == 4) ? 30 : 60; 	/* Loading from any position returns the same value */	xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL);	XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));	XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));	XA_BUG_ON(xa, xa_load(xa, 2) != NULL);	rcu_read_lock();	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2);	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);	rcu_read_unlock(); 	/* Storing adjacent to the value does not alter the value */	xa_store(xa, 3, xa, GFP_KERNEL);	XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));	XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));	XA_BUG_ON(xa, xa_load(xa, 2) != NULL);	rcu_read_lock();	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3);	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);	rcu_read_unlock(); 	/* Overwriting multiple indexes works */	xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL);	XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1));	XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1));	XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1));	XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1));	XA_BUG_ON(xa, xa_load(xa, 4) != NULL);	rcu_read_lock();	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4);	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4);	rcu_read_unlock(); 	/* We can erase multiple values with a single store */	xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL);	XA_BUG_ON(xa, !xa_empty(xa)); 	/* Even when the first slot is empty but the others aren't */	xa_store_index(xa, 1, GFP_KERNEL);	xa_store_index(xa, 2, GFP_KERNEL);	xa_store_order(xa, 0, 2, NULL, GFP_KERNEL);	XA_BUG_ON(xa, !xa_empty(xa)); 	for (i = 0; i < max_order; i++) {		for (j = 0; j < max_order; j++) {			xa_store_order(xa, 0, i, xa_mk_index(i), GFP_KERNEL);			xa_store_order(xa, 0, j, xa_mk_index(j), GFP_KERNEL); 			for (k = 0; k < max_order; k++) {				void *entry = xa_load(xa, (1UL << k) - 1);				if ((i < k) && (j < k))					XA_BUG_ON(xa, entry != NULL);				else					XA_BUG_ON(xa, entry != xa_mk_index(j));			} 			xa_erase(xa, 0);			XA_BUG_ON(xa, !xa_empty(xa));		}	} 	for (i = 0; i < 20; i++) {		check_multi_store_1(xa, 200, i);		check_multi_store_1(xa, 0, i);		check_multi_store_1(xa, (1UL << i) + 1, i);	}	check_multi_store_2(xa, 4095, 9); 	for (i = 1; i < 20; i++) {		check_multi_store_3(xa, 0, i);		check_multi_store_3(xa, 1UL << i, i);	}#endif} #ifdef CONFIG_XARRAY_MULTI/* mimics page cache __filemap_add_folio() */static noinline void check_xa_multi_store_adv_add(struct xarray *xa,						  unsigned long index,						  unsigned int order,						  void *p){	XA_STATE(xas, xa, index);	unsigned int nrpages = 1UL << order; 	/* users are responsible for index alignemnt to the order when adding */	XA_BUG_ON(xa, index & (nrpages - 1)); 	xas_set_order(&xas, index, order); 	do {		xas_lock_irq(&xas);		xas_store(&xas, p);		xas_unlock_irq(&xas);		/*		 * In our selftest case the only failure we can expect is for		 * there not to be enough memory as we're not mimicking the		 * entire page cache, so verify that's the only error we can run		 * into here. The xas_nomem() which follows will ensure to fix		 * that condition for us so to chug on on the loop.		 */		XA_BUG_ON(xa, xas_error(&xas) && xas_error(&xas) != -ENOMEM);	} while (xas_nomem(&xas, GFP_KERNEL)); 	XA_BUG_ON(xa, xas_error(&xas));	XA_BUG_ON(xa, xa_load(xa, index) != p);} /* mimics page_cache_delete() */static noinline void check_xa_multi_store_adv_del_entry(struct xarray *xa,							unsigned long index,							unsigned int order){	XA_STATE(xas, xa, index); 	xas_set_order(&xas, index, order);	xas_store(&xas, NULL);	xas_init_marks(&xas);} static noinline void check_xa_multi_store_adv_delete(struct xarray *xa,						     unsigned long index,						     unsigned int order){	xa_lock_irq(xa);	check_xa_multi_store_adv_del_entry(xa, index, order);	xa_unlock_irq(xa);} /* mimics page cache filemap_get_entry() */static noinline void *test_get_entry(struct xarray *xa, unsigned long index){	XA_STATE(xas, xa, index);	void *p;	static unsigned int loops = 0; 	rcu_read_lock();repeat:	xas_reset(&xas);	p = xas_load(&xas);	if (xas_retry(&xas, p))		goto repeat;	rcu_read_unlock(); 	/*	 * This is not part of the page cache, this selftest is pretty	 * aggressive and does not want to trust the xarray API but rather	 * test it, and for order 20 (4 GiB block size) we can loop over	 * over a million entries which can cause a soft lockup. Page cache	 * APIs won't be stupid, proper page cache APIs loop over the proper	 * order so when using a larger order we skip shared entries.	 */	if (++loops % XA_CHECK_SCHED == 0)		schedule(); 	return p;} static unsigned long some_val = 0xdeadbeef;static unsigned long some_val_2 = 0xdeaddead; /* mimics the page cache usage */static noinline void check_xa_multi_store_adv(struct xarray *xa,					      unsigned long pos,					      unsigned int order){	unsigned int nrpages = 1UL << order;	unsigned long index, base, next_index, next_next_index;	unsigned int i; 	index = pos >> PAGE_SHIFT;	base = round_down(index, nrpages);	next_index = round_down(base + nrpages, nrpages);	next_next_index = round_down(next_index + nrpages, nrpages); 	check_xa_multi_store_adv_add(xa, base, order, &some_val); 	for (i = 0; i < nrpages; i++)		XA_BUG_ON(xa, test_get_entry(xa, base + i) != &some_val); 	XA_BUG_ON(xa, test_get_entry(xa, next_index) != NULL); 	/* Use order 0 for the next item */	check_xa_multi_store_adv_add(xa, next_index, 0, &some_val_2);	XA_BUG_ON(xa, test_get_entry(xa, next_index) != &some_val_2); 	/* Remove the next item */	check_xa_multi_store_adv_delete(xa, next_index, 0); 	/* Now use order for a new pointer */	check_xa_multi_store_adv_add(xa, next_index, order, &some_val_2); 	for (i = 0; i < nrpages; i++)		XA_BUG_ON(xa, test_get_entry(xa, next_index + i) != &some_val_2); 	check_xa_multi_store_adv_delete(xa, next_index, order);	check_xa_multi_store_adv_delete(xa, base, order);	XA_BUG_ON(xa, !xa_empty(xa)); 	/* starting fresh again */ 	/* let's test some holes now */ 	/* hole at base and next_next */	check_xa_multi_store_adv_add(xa, next_index, order, &some_val_2); 	for (i = 0; i < nrpages; i++)		XA_BUG_ON(xa, test_get_entry(xa, base + i) != NULL); 	for (i = 0; i < nrpages; i++)		XA_BUG_ON(xa, test_get_entry(xa, next_index + i) != &some_val_2); 	for (i = 0; i < nrpages; i++)		XA_BUG_ON(xa, test_get_entry(xa, next_next_index + i) != NULL); 	check_xa_multi_store_adv_delete(xa, next_index, order);	XA_BUG_ON(xa, !xa_empty(xa)); 	/* hole at base and next */ 	check_xa_multi_store_adv_add(xa, next_next_index, order, &some_val_2); 	for (i = 0; i < nrpages; i++)		XA_BUG_ON(xa, test_get_entry(xa, base + i) != NULL); 	for (i = 0; i < nrpages; i++)		XA_BUG_ON(xa, test_get_entry(xa, next_index + i) != NULL); 	for (i = 0; i < nrpages; i++)		XA_BUG_ON(xa, test_get_entry(xa, next_next_index + i) != &some_val_2); 	check_xa_multi_store_adv_delete(xa, next_next_index, order);	XA_BUG_ON(xa, !xa_empty(xa));}#endif static noinline void check_multi_store_advanced(struct xarray *xa){#ifdef CONFIG_XARRAY_MULTI	unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;	unsigned long end = ULONG_MAX/2;	unsigned long pos, i; 	/*	 * About 117 million tests below.	 */	for (pos = 7; pos < end; pos = (pos * pos) + 564) {		for (i = 0; i < max_order; i++) {			check_xa_multi_store_adv(xa, pos, i);			check_xa_multi_store_adv(xa, pos + 157, i);		}	}#endif} static noinline void check_xa_alloc_1(struct xarray *xa, unsigned int base){	int i;	u32 id; 	XA_BUG_ON(xa, !xa_empty(xa));	/* An empty array should assign %base to the first alloc */	xa_alloc_index(xa, base, GFP_KERNEL); 	/* Erasing it should make the array empty again */	xa_erase_index(xa, base);	XA_BUG_ON(xa, !xa_empty(xa)); 	/* And it should assign %base again */	xa_alloc_index(xa, base, GFP_KERNEL); 	/* Allocating and then erasing a lot should not lose base */	for (i = base + 1; i < 2 * XA_CHUNK_SIZE; i++)		xa_alloc_index(xa, i, GFP_KERNEL);	for (i = base; i < 2 * XA_CHUNK_SIZE; i++)		xa_erase_index(xa, i);	xa_alloc_index(xa, base, GFP_KERNEL); 	/* Destroying the array should do the same as erasing */	xa_destroy(xa); 	/* And it should assign %base again */	xa_alloc_index(xa, base, GFP_KERNEL); 	/* The next assigned ID should be base+1 */	xa_alloc_index(xa, base + 1, GFP_KERNEL);	xa_erase_index(xa, base + 1); 	/* Storing a value should mark it used */	xa_store_index(xa, base + 1, GFP_KERNEL);	xa_alloc_index(xa, base + 2, GFP_KERNEL); 	/* If we then erase base, it should be free */	xa_erase_index(xa, base);	xa_alloc_index(xa, base, GFP_KERNEL); 	xa_erase_index(xa, base + 1);	xa_erase_index(xa, base + 2); 	for (i = 1; i < 5000; i++) {		xa_alloc_index(xa, base + i, GFP_KERNEL);	} 	xa_destroy(xa); 	/* Check that we fail properly at the limit of allocation */	XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX - 1),				XA_LIMIT(UINT_MAX - 1, UINT_MAX),				GFP_KERNEL) != 0);	XA_BUG_ON(xa, id != 0xfffffffeU);	XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX),				XA_LIMIT(UINT_MAX - 1, UINT_MAX),				GFP_KERNEL) != 0);	XA_BUG_ON(xa, id != 0xffffffffU);	id = 3;	XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(0),				XA_LIMIT(UINT_MAX - 1, UINT_MAX),				GFP_KERNEL) != -EBUSY);	XA_BUG_ON(xa, id != 3);	xa_destroy(xa); 	XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),				GFP_KERNEL) != -EBUSY);	XA_BUG_ON(xa, xa_store_index(xa, 3, GFP_KERNEL) != 0);	XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),				GFP_KERNEL) != -EBUSY);	xa_erase_index(xa, 3);	XA_BUG_ON(xa, !xa_empty(xa));} static noinline void check_xa_alloc_2(struct xarray *xa, unsigned int base){	unsigned int i, id;	unsigned long index;	void *entry; 	/* Allocate and free a NULL and check xa_empty() behaves */	XA_BUG_ON(xa, !xa_empty(xa));	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_BUG_ON(xa, xa_erase(xa, id) != NULL);	XA_BUG_ON(xa, !xa_empty(xa)); 	/* Ditto, but check destroy instead of erase */	XA_BUG_ON(xa, !xa_empty(xa));

Lines 501–1000 of 2278. Previous lines Load more