lib/test_xarray.c | 28 ++++++++++++++++++++++++---- 1 file changed, 24 insertions(+), 4 deletions(-)
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/cover.1771831180.git.ackerleytng@google.com/T/) + RFC v1: https://lore.kernel.org/all/720e32d8e185d5c82659bbdede05e87b3318c413.1769818406.git.ackerleytng@google.com/ [1] https://lore.kernel.org/all/20251028223414.299268-1-ackerleytng@google.com/ 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
On 2/23/26 08:34, Ackerley Tng wrote: > 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? Zi, do you have any familiarity with that code and could help? Thanks! -- Cheers, David
On Mon, Mar 16, 2026 at 05:23:17PM +0100, David Hildenbrand (Arm) wrote:
>On 2/23/26 08:34, Ackerley Tng wrote:
>> Hi,
>>
Hi,
Hope I can help here.
>> 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?
>>
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.
>> 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.
>>
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.
>> 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?
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.
>
>Zi, do you have any familiarity with that code and could help?
>
>Thanks!
>
>--
>Cheers,
>
>David
--
Wei Yang
Help you, Help me
On 16 Mar 2026, at 12:23, David Hildenbrand (Arm) wrote: > On 2/23/26 08:34, Ackerley Tng wrote: >> 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? > > 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
On 3/16/26 17:49, Zi Yan wrote: > On 16 Mar 2026, at 12:23, David Hildenbrand (Arm) wrote: > >> On 2/23/26 08:34, Ackerley Tng wrote: >>> 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? >> >> 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. 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) -- Cheers, David
On 1 Apr 2026, at 3:32, David Hildenbrand (Arm) wrote: > On 3/16/26 17:49, Zi Yan wrote: >> On 16 Mar 2026, at 12:23, David Hildenbrand (Arm) wrote: >> >>> On 2/23/26 08:34, Ackerley Tng wrote: >>>> 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? >>> >>> 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. > > 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 > > (I can try getting access to the recording) Best Regards, Yan, Zi
© 2016 - 2026 Red Hat, Inc.