test_xarray: advanced API multi-index tests
Subsystems (4)
v2 cover test_xarray: advanced API multi-index tests
This is a respin of the test_xarray multi-index tests [0] which use and demonstrate the advanced API which is used by the page cache. This should let folks more easily follow how we use multi-index to support for example a min order later in the page cache. It also lets us grow the selftests to mimic more of what we do in the page cache.
Changes since v1:
- Fixed RCU stall, the issue was the misssing RCU locks when fetching an entry, so we now add test_get_entry() which mimics filemap_get_entry()
- Provide a bit more comments
- Check for alignment on the index to the order on check_xa_multi_store_adv_add()
- Use a helper check_xa_multi_store_adv_del_entry() to mimic what we do in page_cache_delete()
Changes since RFC:
- Moved out from tmpfs large folio patches [1] so to keep these patches separate
- Update cmpxchg test to include another entry at 1 << order that 'keeps' the node around and order information.
- Update cmpxchg test to verify the entries and order in all tied indexes.
- Drop previous Luis Chamberlain's review as changes are significant from the RFC.
[0] https://lkml.kernel.org/r/[email protected]
[1] https://lore.kernel.org/all/[email protected]/
Daniel Gomez (1):
XArray: add cmpxchg order test
Luis Chamberlain (1):
test_xarray: add tests for advanced multi-index use
lib/test_xarray.c | 218 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 218 insertions(+)
Signature · 1 line
2.43.0
PATCH v2 1/2 test_xarray: add tests for advanced multi-index use
The multi index selftests are great but they don't replicate how we deal with the page cache exactly, which makes it a bit hard to follow as the page cache uses the advanced API.
Add tests which use the advanced API, mimicking what we do in the page cache, while at it, extend the example to do what is needed for min order support.
--- lib/test_xarray.c | 164 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 164 insertions(+)
lib/test_xarray.c +164 -0
@@ -674,6 +674,169 @@ static noinline void check_multi_store(struct xarray *xa)#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); +XA_BUG_ON (xa,xas_error (&xas)); +XA_BUG_ON (xa,xa_load (xa, index) != p); + +xas_unlock_irq (&xas); + }while (xas_nomem (&xas,GFP_KERNEL )); + +XA_BUG_ON (xa,xas_error (&xas)); +} + +/* 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; + +rcu_read_lock (); +repeat: +xas_reset (&xas); + p =xas_load (&xas); +if (xas_retry (&xas, p)) + goto repeat; +rcu_read_unlock (); + +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;
@@ -1804,6 +1967,7 @@ static int xarray_checks(void)check_reserve (&array);check_reserve (&xa0);check_multi_store (&array); +check_multi_store_advanced (&array);check_get_order (&array);check_xa_alloc ();check_find (&array);
Signature · 1 line
2.43.0
PATCH v2 2/2 XArray: add cmpxchg order test
In reply to Luis ChamberlainFrom: Daniel Gomez <[email protected]>
XArray multi-index entries do not keep track of the order stored once the entry is being marked as used with cmpxchg (conditionally replaced with NULL). Add a test to check the order is actually lost. The test also verifies the order and entries for all the tied indexes before and after the NULL replacement with xa_cmpxchg.
Add another entry at 1 << order that keeps the node around and the order information for the NULL-entry after xa_cmpxchg.
--- lib/test_xarray.c | 54 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+)
lib/test_xarray.c +54 -0
@@ -423,6 +423,59 @@ static noinline void check_cmpxchg(struct xarray *xa)XA_BUG_ON (xa, !xa_empty (xa)); } +static noinline void check_cmpxchg_order(struct xarray *xa) +{ +#ifdef CONFIG_XARRAY_MULTI +void *FIVE =xa_mk_value (5 ); +unsigned int i, order =3 ; + +XA_BUG_ON (xa,xa_store_order (xa,0 , order,FIVE ,GFP_KERNEL )); + +/* Check entry FIVE has the order saved */ +XA_BUG_ON (xa,xa_get_order (xa,xa_to_value (FIVE )) != order); + +/* Check all the tied indexes have the same entry and order */ +for (i =0 ; i < (1 << order); i++) { +XA_BUG_ON (xa,xa_load (xa, i) !=FIVE ); +XA_BUG_ON (xa,xa_get_order (xa, i) != order); + } + +/* Ensure that nothing is stored at index '1 << order' */ +XA_BUG_ON (xa,xa_load (xa,1 << order) !=NULL ); + +/* +* Additionally, keep the node information and the order at +* '1 << order' +*/ +XA_BUG_ON (xa,xa_store_order (xa,1 << order, order,FIVE ,GFP_KERNEL )); +for (i = (1 << order); i < (1 << order) + (1 << order) -1 ; i++) { +XA_BUG_ON (xa,xa_load (xa, i) !=FIVE ); +XA_BUG_ON (xa,xa_get_order (xa, i) != order); + } + +/* Conditionally replace FIVE entry at index '0' with NULL */ +XA_BUG_ON (xa,xa_cmpxchg (xa,0 ,FIVE ,NULL ,GFP_KERNEL ) !=FIVE ); + +/* Verify the order is lost at FIVE (and old) entries */ +XA_BUG_ON (xa,xa_get_order (xa,xa_to_value (FIVE )) !=0 ); + +/* Verify the order and entries are lost in all the tied indexes */ +for (i =0 ; i < (1 << order); i++) { +XA_BUG_ON (xa,xa_load (xa, i) !=NULL ); +XA_BUG_ON (xa,xa_get_order (xa, i) !=0 ); + } + +/* Verify node and order are kept at '1 << order' */ +for (i = (1 << order); i < (1 << order) + (1 << order) -1 ; i++) { +XA_BUG_ON (xa,xa_load (xa, i) !=FIVE ); +XA_BUG_ON (xa,xa_get_order (xa, i) != order); + } + +xa_store_order (xa,0 ,BITS_PER_LONG -1 ,NULL ,GFP_KERNEL ); +XA_BUG_ON (xa, !xa_empty (xa)); +#endif +} + static noinline void check_reserve(struct xarray *xa) {void *entry;
@@ -1964,6 +2017,7 @@ static int xarray_checks(void)check_xas_erase (&array);check_insert (&array);check_cmpxchg (&array); +check_cmpxchg_order (&array);check_reserve (&array);check_reserve (&xa0);check_multi_store (&array);
Signature · 1 line
2.43.0