Fix storing in XArray check_split tests
Subsystems (4)
v3 cover Fix storing in XArray check_split tests
Hi,
I hit an assertion while making some modifications to lib/test_xarray.c [1] and I believe this is the fix.
In check_split, the tests split the XArray node and then store values after the split to verify that splitting worked. While storing and retrieval works as expected, the node's metadata, specifically node->nr_values, is not updated correctly.
This led to the assertion being hit in [1], since the storing process did not increment node->nr_values sufficiently, while the erasing process assumed the fully-incremented node->nr_values state.
Would like to check my understanding on these:
1. In the multi-index xarray world, is node->nr_values definitely the total number of values *and siblings* in the node?
2. IIUC xas_store() has significantly different behavior when entry is NULL vs non-NULL: when entry is NULL, xas_store() does not make assumptions on the number of siblings and erases all the way till the next non-sibling entry. This sounds fair to me, but it's also kind of surprising that it is differently handled when entry is non-NULL, where xas_store() respects xas->xa_sibs.
3. If xas_store() is dependent on its caller to set up xas correctly (also sounds fair), then there are places where xas_store() is used, like replace_page_cache_folio() or migrate_huge_page_move_mapping(), where xas is set up assuming 0 order pages. Are those buggy?
Previous versions:
+ RFC v3: Cleaned up commits and subject references (sorry for the noise!)
+ RFC v2: Rebased on Linux 7.0-rc1 (https://lore.kernel.org/all/[email protected]/T/)
+ RFC v1: https://lore.kernel.org/all/720e32d8e185d5c82659bbdede05e87b3318c413.1769818406.git.ackerleytng@google.com/
[1] https://lore.kernel.org/all/[email protected]/
Ackerley Tng (2):
XArray tests: Fix check_split tests to store correctly XArray tests: Verify xa_erase behavior in check_split
lib/test_xarray.c | 28 ++++++++++++++++++++++++---- 1 file changed, 24 insertions(+), 4 deletions(-)
base-commit: 6de23f81a5e08be8fbf5e8d7e9febc72a5b5f27f --
2.53.0.345.g96ddfc5eaa-goog
RFC PATCH v3 1/2 XArray tests: Fix check_split tests to store correctly
__xa_store() does not set up xas->xa_sibs, and when it calls xas_store(), xas_store() stops prematurely and does not update node->nr_values to count all values and siblings. Hence, when working with multi-index XArrays, __xa_store() cannot be used.
Fix tests by calling xas_store() directly with xas->xa_sibs correctly set up.
--- lib/test_xarray.c | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-)
lib/test_xarray.c +16 -4
@@ -1846,8 +1846,14 @@ static void check_split_1(struct xarray *xa, unsigned long index,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 ); +for (i =0 ; i < (1 << order); i += (1 << new_order)) { +xas_set_order (&xas, index + i, new_order); +/* +* Don't worry about -ENOMEM, xas_split_alloc() and +* xas_split() ensures that all nodes are allocated. +*/ +xas_store (&xas,xa_mk_index (index + i)); + }xas_unlock (&xas);for (i =0 ; i < (1 << order); i++) {
@@ -1893,8 +1899,14 @@ static void check_split_2(struct xarray *xa, unsigned long index,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 ); +for (i =0 ; i < (1 << order); i += (1 << new_order)) { +xas_set_order (&xas, index + i, new_order); +/* +* Don't worry about -ENOMEM, xas_split_alloc() and +* xas_split() ensures that all nodes are allocated. +*/ +xas_store (&xas,xa_mk_index (index + i)); + }xas_unlock (&xas);for (i =0 ; i < (1 << order); i++) {
Signature · 1 line
2.53.0.345.g96ddfc5eaa-goog
RFC PATCH v3 2/2 XArray tests: Verify xa_erase behavior in check_split
In reply to Ackerley TngBoth __xa_store() and xa_erase() use xas_store() under the hood, but when the entry being stored is NULL (as in the case of xa_erase()), xas->xa_sibs (and max) is only checked if the next entry is not a sibling, hence allowing xas_store() to keep iterating, hence updating node->nr_values correctly.
Add xa_erase() to check_split tests that verify functionality, with the added intent to illustrate the usage differences between __xa_store(), xas_store() and xa_erase() with regard to multi-index XArrays.
--- lib/test_xarray.c | 8 ++++++++ 1 file changed, 8 insertions(+)
lib/test_xarray.c +8 -0
@@ -1874,6 +1874,10 @@ static void check_split_1(struct xarray *xa, unsigned long index,rcu_read_unlock ();XA_BUG_ON (xa, found !=1 << (order - new_order)); +for (i =0 ; i < (1 << order); i += (1 << new_order)) +xa_erase (xa, index + i); +XA_BUG_ON (xa, !xa_empty (xa)); +xa_destroy (xa); }
@@ -1926,6 +1930,10 @@ static void check_split_2(struct xarray *xa, unsigned long index, }rcu_read_unlock ();XA_BUG_ON (xa, found !=1 << (order - new_order)); + +for (i =0 ; i < (1 << order); i += (1 << new_order)) +xa_erase (xa, index + i); +XA_BUG_ON (xa, !xa_empty (xa)); out:xas_destroy (&xas);xa_destroy (xa);
Signature · 1 line
2.53.0.345.g96ddfc5eaa-goog
Quoted 26 lines · Ackerley Tng
Hi,
I hit an assertion while making some modifications to
lib/test_xarray.c[1] and I believe this is the fix.In
check_split, the tests split the XArray node and then store values after the split to verify that splitting worked. While storing and retrieval works as expected, the node's metadata, specificallynode->nr_values, is not updated correctly.This led to the assertion being hit in [1], since the storing process did not increment
node->nr_valuessufficiently, while the erasing process assumed the fully-incrementednode->nr_valuesstate.Would like to check my understanding on these:
1. In the multi-index xarray world, is
node->nr_valuesdefinitely the total number of values *and siblings* in the node?2. IIUC
xas_store()has significantly different behavior when entry is NULL vs non-NULL: when entry is NULL,xas_store()does not make assumptions on the number of siblings and erases all the way till the next non-sibling entry. This sounds fair to me, but it's also kind of surprising that it is differently handled when entry is non-NULL, wherexas_store()respectsxas->xa_sibs.
Quoted 5 lines
3. If
xas_store()is dependent on its caller to set up xas correctly (also sounds fair), then there are places wherexas_store()is used, likereplace_page_cache_folio()ormigrate_huge_page_move_mapping(), where xas is set up assuming 0 order pages. Are those buggy?
Zi, do you have any familiarity with that code and could help?
Thanks!
Signature · 3 lines
Cheers, David
Quoted 27 lines · David Hildenbrand (Arm)
Quoted 26 lines · Ackerley Tng
Hi,
I hit an assertion while making some modifications to
lib/test_xarray.c[1] and I believe this is the fix.In
check_split, the tests split the XArray node and then store values after the split to verify that splitting worked. While storing and retrieval works as expected, the node's metadata, specificallynode->nr_values, is not updated correctly.This led to the assertion being hit in [1], since the storing process did not increment
node->nr_valuessufficiently, while the erasing process assumed the fully-incrementednode->nr_valuesstate.Would like to check my understanding on these:
1. In the multi-index xarray world, is
node->nr_valuesdefinitely the total number of values *and siblings* in the node?2. IIUC
xas_store()has significantly different behavior when entry is NULL vs non-NULL: when entry is NULL,xas_store()does not make assumptions on the number of siblings and erases all the way till the next non-sibling entry. This sounds fair to me, but it's also kind of surprising that it is differently handled when entry is non-NULL, wherexas_store()respectsxas->xa_sibs.
Quoted 7 lines
Quoted 5 lines
3. If
xas_store()is dependent on its caller to set up xas correctly (also sounds fair), then there are places wherexas_store()is used, likereplace_page_cache_folio()ormigrate_huge_page_move_mapping(), where xas is set up assuming 0 order pages. Are those buggy?Zi, do you have any familiarity with that code and could help?
Not much. But I used lib/test_xarray.c to did a test:
1. initialize an xarray with order 6 and set entry to 0,
2. add a new xas like XA_STATE(xas0, xa, 0);
3. xas_store(&xas0, xa_mk_value(32));
4. add a new xas like XA_STATE(xas0, xa, 16);
5. xas_store(&xas0, xa_mk_value(48));
The outcome is that xas_store() does not change xarray structure, namely the orders are preserved. No issue is present.
After 2 and 3, the xarray is still order 6, but its 0-63 entries (all order-6) are changed from 0 to 32.
After 4 and 5, the xarray is still order 6, but its 0-63 entries are changed from 32 to 48.
I will need to dig into the code more to explain how xas_store() works.
Best Regards,
Yan, Zi
Quoted 50 lines · Zi Yan
Quoted 27 lines · David Hildenbrand (Arm)
Quoted 26 lines · Ackerley Tng
Hi,
I hit an assertion while making some modifications to
lib/test_xarray.c[1] and I believe this is the fix.In
check_split, the tests split the XArray node and then store values after the split to verify that splitting worked. While storing and retrieval works as expected, the node's metadata, specificallynode->nr_values, is not updated correctly.This led to the assertion being hit in [1], since the storing process did not increment
node->nr_valuessufficiently, while the erasing process assumed the fully-incrementednode->nr_valuesstate.Would like to check my understanding on these:
1. In the multi-index xarray world, is
node->nr_valuesdefinitely the total number of values *and siblings* in the node?2. IIUC
xas_store()has significantly different behavior when entry is NULL vs non-NULL: when entry is NULL,xas_store()does not make assumptions on the number of siblings and erases all the way till the next non-sibling entry. This sounds fair to me, but it's also kind of surprising that it is differently handled when entry is non-NULL, wherexas_store()respectsxas->xa_sibs.Quoted 7 lines
Quoted 5 lines
3. If
xas_store()is dependent on its caller to set up xas correctly (also sounds fair), then there are places wherexas_store()is used, likereplace_page_cache_folio()ormigrate_huge_page_move_mapping(), where xas is set up assuming 0 order pages. Are those buggy?Zi, do you have any familiarity with that code and could help?
Not much. But I used
lib/test_xarray.cto did a test:1. initialize an xarray with order 6 and set entry to 0,
2. add a new xas like
XA_STATE(xas0, xa, 0);
3.xas_store(&xas0, xa_mk_value(32));4. add a new xas like
XA_STATE(xas0, xa, 16);
5.xas_store(&xas0, xa_mk_value(48));The outcome is that
xas_store()does not change xarray structure, namely the orders are preserved. No issue is present.
Quoted 6 lines
After 2 and 3, the xarray is still order 6, but its 0-63 entries (all order-6) are changed from 0 to 32.
After 4 and 5, the xarray is still order 6, but its 0-63 entries are changed from 32 to 48.I will need to dig into the code more to explain how
xas_store()works.
Zi,
we discussed this topic with Willy in the THP cabal call. I did not get all the details, do you remember our conclusion?
(I can try getting access to the recording)
Signature · 3 lines
Cheers, David
Quoted 56 lines · David Hildenbrand (Arm)
Quoted 55 lines · Zi Yan
Quoted 27 lines · David Hildenbrand (Arm)
Quoted 26 lines · Ackerley Tng
Hi,
I hit an assertion while making some modifications to
lib/test_xarray.c[1] and I believe this is the fix.In
check_split, the tests split the XArray node and then store values after the split to verify that splitting worked. While storing and retrieval works as expected, the node's metadata, specificallynode->nr_values, is not updated correctly.This led to the assertion being hit in [1], since the storing process did not increment
node->nr_valuessufficiently, while the erasing process assumed the fully-incrementednode->nr_valuesstate.Would like to check my understanding on these:
1. In the multi-index xarray world, is
node->nr_valuesdefinitely the total number of values *and siblings* in the node?2. IIUC
xas_store()has significantly different behavior when entry is NULL vs non-NULL: when entry is NULL,xas_store()does not make assumptions on the number of siblings and erases all the way till the next non-sibling entry. This sounds fair to me, but it's also kind of surprising that it is differently handled when entry is non-NULL, wherexas_store()respectsxas->xa_sibs.Quoted 7 lines
Quoted 5 lines
3. If
xas_store()is dependent on its caller to set up xas correctly (also sounds fair), then there are places wherexas_store()is used, likereplace_page_cache_folio()ormigrate_huge_page_move_mapping(), where xas is set up assuming 0 order pages. Are those buggy?Zi, do you have any familiarity with that code and could help?
Not much. But I used
lib/test_xarray.cto did a test:1. initialize an xarray with order 6 and set entry to 0,
2. add a new xas like
XA_STATE(xas0, xa, 0);
3.xas_store(&xas0, xa_mk_value(32));4. add a new xas like
XA_STATE(xas0, xa, 16);
5.xas_store(&xas0, xa_mk_value(48));The outcome is that
xas_store()does not change xarray structure, namely the orders are preserved. No issue is present.After 2 and 3, the xarray is still order 6, but its 0-63 entries (all order-6) are changed from 0 to 32.
After 4 and 5, the xarray is still order 6, but its 0-63 entries are changed from 32 to 48.
Quoted 6 lines
Quoted 1 line
I will need to dig into the code more to explain how
xas_store()works.Zi,
we discussed this topic with Willy in the THP cabal call. I did not get all the details, do you remember our conclusion?
The conclusion is that if user wants to erase (or xas_store(NULL)) an index that is in the middle of a multi-index entry, they need to split that multi-index first then do the erase (or xas_store(NULL)). Because it is documented in xa_erase() (or xas_store(NULL)) that it erases all indices of a multi-index entry[1] and requiring xa_erase() (or xas_store(NULL)) to split a multi-index entry and erase the specified index only is too much due to potential memory allocations during multi-index entry split process.
[1] https://elixir.bootlin.com/linux/v6.19.10/source/lib/xarray.c#L1640
Quoted 2 lines
(I can try getting access to the recording)
Best Regards,
Yan, Zi
Quoted 3 lines · David Hildenbrand (Arm)
Quoted 2 lines · Ackerley Tng
Hi,
Hi,
Hope I can help here.
Quoted 12 lines
Quoted 12 lines
I hit an assertion while making some modifications to
lib/test_xarray.c[1] and I believe this is the fix.In
check_split, the tests split the XArray node and then store values after the split to verify that splitting worked. While storing and retrieval works as expected, the node's metadata, specificallynode->nr_values, is not updated correctly.This led to the assertion being hit in [1], since the storing process did not increment
node->nr_valuessufficiently, while the erasing process assumed the fully-incrementednode->nr_valuesstate.
Quoted 5 lines
Quoted 5 lines
Would like to check my understanding on these:
1. In the multi-index xarray world, is
node->nr_valuesdefinitely the total number of values *and siblings* in the node?
I think so.
As the comment of struct xa_node says:
* @nr_values is the count of every element in ->slots which is
* either a value entry or a sibling of a value entry.
And I play with xas_store() and xas_split(), then dump the xarray, which shows nr_values counts value and its siblings.
Quoted 7 lines
Quoted 7 lines
2. IIUC
xas_store()has significantly different behavior when entry is NULL vs non-NULL: when entry is NULL,xas_store()does not make assumptions on the number of siblings and erases all the way till the next non-sibling entry. This sounds fair to me, but it's also kind of surprising that it is differently handled when entry is non-NULL, wherexas_store()respectsxas->xa_sibs.
Agree with your.
max = xas->xa_offset + xas->xa_sibs;
if (entry) { // non-NULL entry
if (offset == max) // respect xa_sibs
break;
if (!xa_is_sibling(entry))
entry = xa_mk_sibling(xas->xa_offset);
} else {
if (offset == XA_CHUNK_MASK) // NULL entry, run all way down..
break;
}
next = xa_entry_locked(xas->xa, node, ++offset);
if (!xa_is_sibling(next)) { // .. until a non-sibling entry
if (!entry && (offset > max)) // then respect xa_sibs
break;
first = next;
}This does has difference. Confused a little.
This is the reason why we see the nr_values is not updated as expected. When xas_store() an order 0 non-NULL entry, it just iterate once. Then count the difference as 1 instead of total counts it represents.
Quoted 5 lines
Quoted 5 lines
3. If
xas_store()is dependent on its caller to set up xas correctly (also sounds fair), then there are places wherexas_store()is used, likereplace_page_cache_folio()ormigrate_huge_page_move_mapping(), where xas is set up assuming 0 order pages. Are those buggy?
This is a good question.
When I look into these two places, I noticed the purpose here is to replace an existing folio in pagecache with another folio. This means the old data and new data are neither "value". So we don't expect nr_values would change.
One place we would store "value" into pagecache is swap, IIUC. Maybe we need to take a look into that place.
The rule seems to be not mixture store "value" and "non-value" into xarray, it is safe.
Quoted 9 lines
Zi, do you have any familiarity with that code and could help?
Thanks!
Signature · 3 lines
Cheers, David
Signature · 2 lines
Wei Yang Help you, Help me