[RFC PATCH v3 0/2] Fix storing in XArray check_split tests

[RFC PATCH v3 0/2] Fix storing in XArray check_split tests

[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, 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

[RFC PATCH v3 1/2] XArray tests: Fix check_split tests to store correctly

[Ackerley Tng]

__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.

Signed-off-by: Ackerley Tng <ackerleytng@google.com>
---
 lib/test_xarray.c | 20 ++++++++++++++++----
 1 file changed, 16 insertions(+), 4 deletions(-)

diff --git a/lib/test_xarray.c b/lib/test_xarray.c
index 5ca0aefee9aa5..e71e8ff76900b 100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -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++) {
-- 
2.53.0.345.g96ddfc5eaa-goog

[RFC PATCH v3 2/2] XArray tests: Verify xa_erase behavior in check_split

[Ackerley Tng]

Both __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.

Signed-off-by: Ackerley Tng <ackerleytng@google.com>
---
 lib/test_xarray.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/lib/test_xarray.c b/lib/test_xarray.c
index e71e8ff76900b..bb9471a3df65c 100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -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);
-- 
2.53.0.345.g96ddfc5eaa-goog

Re: [RFC PATCH v3 0/2] Fix storing in XArray check_split tests

[David Hildenbrand (Arm)]

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

Re: [RFC PATCH v3 0/2] Fix storing in XArray check_split tests

[Zi Yan]

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

Re: [RFC PATCH v3 0/2] Fix storing in XArray check_split tests

[Wei Yang]

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

Re: [RFC PATCH v3 0/2] Fix storing in XArray check_split tests

[David Hildenbrand (Arm)]

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

Re: [RFC PATCH v3 0/2] Fix storing in XArray check_split tests

[Zi Yan]

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