[PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Dev Jain]

Suppose xas is pointing somewhere near the end of the multi-entry batch.
Then it may happen that the computed slot already falls beyond the batch,
thus breaking the loop due to !xa_is_sibling(), and computing the wrong
order. Thus ensure that the caller is aware of this by triggering a BUG
when the entry is a sibling entry.

This patch is motivated by code inspection and not a real bug report.

Signed-off-by: Dev Jain <dev.jain@arm.com>
---
The patch applies on 6.15 kernel.

 lib/xarray.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/lib/xarray.c b/lib/xarray.c
index 9644b18af18d..0f699766c24f 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -1917,6 +1917,8 @@ int xas_get_order(struct xa_state *xas)
 	if (!xas->xa_node)
 		return 0;
 
+	XA_NODE_BUG_ON(xas->xa_node, xa_is_sibling(xa_entry(xas->xa,
+		       xas->xa_node, xas->xa_offset)));
 	for (;;) {
 		unsigned int slot = xas->xa_offset + (1 << order);
 
-- 
2.30.2

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Zi Yan]

On 28 May 2025, at 7:31, Dev Jain wrote:

> Suppose xas is pointing somewhere near the end of the multi-entry batch.
> Then it may happen that the computed slot already falls beyond the batch,
> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
> order. Thus ensure that the caller is aware of this by triggering a BUG
> when the entry is a sibling entry.

Is it possible to add a test case in lib/test_xarray.c for this?
You can compile the tests with “make -C tools/testing/radix-tree”
and run “./tools/testing/radix-tree/xarray”.

>
> This patch is motivated by code inspection and not a real bug report.
>
> Signed-off-by: Dev Jain <dev.jain@arm.com>
> ---
> The patch applies on 6.15 kernel.
>
>  lib/xarray.c | 2 ++
>  1 file changed, 2 insertions(+)
>
> diff --git a/lib/xarray.c b/lib/xarray.c
> index 9644b18af18d..0f699766c24f 100644
> --- a/lib/xarray.c
> +++ b/lib/xarray.c
> @@ -1917,6 +1917,8 @@ int xas_get_order(struct xa_state *xas)
>  	if (!xas->xa_node)
>  		return 0;
>
> +	XA_NODE_BUG_ON(xas->xa_node, xa_is_sibling(xa_entry(xas->xa,
> +		       xas->xa_node, xas->xa_offset)));
>  	for (;;) {
>  		unsigned int slot = xas->xa_offset + (1 << order);
>
> -- 
> 2.30.2


Best Regards,
Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Dev Jain]

On 28/05/25 10:42 pm, Zi Yan wrote:
> On 28 May 2025, at 7:31, Dev Jain wrote:
>
>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>> Then it may happen that the computed slot already falls beyond the batch,
>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>> order. Thus ensure that the caller is aware of this by triggering a BUG
>> when the entry is a sibling entry.
> Is it possible to add a test case in lib/test_xarray.c for this?
> You can compile the tests with “make -C tools/testing/radix-tree”
> and run “./tools/testing/radix-tree/xarray”.


Sorry forgot to Cc you.
I can surely do that later, but does this patch look fine?


>
>> This patch is motivated by code inspection and not a real bug report.
>>
>> Signed-off-by: Dev Jain <dev.jain@arm.com>
>> ---
>> The patch applies on 6.15 kernel.
>>
>>   lib/xarray.c | 2 ++
>>   1 file changed, 2 insertions(+)
>>
>> diff --git a/lib/xarray.c b/lib/xarray.c
>> index 9644b18af18d..0f699766c24f 100644
>> --- a/lib/xarray.c
>> +++ b/lib/xarray.c
>> @@ -1917,6 +1917,8 @@ int xas_get_order(struct xa_state *xas)
>>   	if (!xas->xa_node)
>>   		return 0;
>>
>> +	XA_NODE_BUG_ON(xas->xa_node, xa_is_sibling(xa_entry(xas->xa,
>> +		       xas->xa_node, xas->xa_offset)));
>>   	for (;;) {
>>   		unsigned int slot = xas->xa_offset + (1 << order);
>>
>> -- 
>> 2.30.2
>
> Best Regards,
> Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Zi Yan]

On 28 May 2025, at 23:17, Dev Jain wrote:

> On 28/05/25 10:42 pm, Zi Yan wrote:
>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>
>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>> Then it may happen that the computed slot already falls beyond the batch,
>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>> when the entry is a sibling entry.
>> Is it possible to add a test case in lib/test_xarray.c for this?
>> You can compile the tests with “make -C tools/testing/radix-tree”
>> and run “./tools/testing/radix-tree/xarray”.
>
>
> Sorry forgot to Cc you.
> I can surely do that later, but does this patch look fine?

I am not sure the exact situation you are describing, so I asked you
to write a test case to demonstrate the issue. :)

>
>
>>
>>> This patch is motivated by code inspection and not a real bug report.
>>>
>>> Signed-off-by: Dev Jain <dev.jain@arm.com>
>>> ---
>>> The patch applies on 6.15 kernel.
>>>
>>>   lib/xarray.c | 2 ++
>>>   1 file changed, 2 insertions(+)
>>>
>>> diff --git a/lib/xarray.c b/lib/xarray.c
>>> index 9644b18af18d..0f699766c24f 100644
>>> --- a/lib/xarray.c
>>> +++ b/lib/xarray.c
>>> @@ -1917,6 +1917,8 @@ int xas_get_order(struct xa_state *xas)
>>>   	if (!xas->xa_node)
>>>   		return 0;
>>>
>>> +	XA_NODE_BUG_ON(xas->xa_node, xa_is_sibling(xa_entry(xas->xa,
>>> +		       xas->xa_node, xas->xa_offset)));
>>>   	for (;;) {
>>>   		unsigned int slot = xas->xa_offset + (1 << order);
>>>
>>> -- 
>>> 2.30.2
>>
>> Best Regards,
>> Yan, Zi


Best Regards,
Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Zi Yan]

On 29 May 2025, at 18:47, Zi Yan wrote:

> On 28 May 2025, at 23:17, Dev Jain wrote:
>
>> On 28/05/25 10:42 pm, Zi Yan wrote:
>>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>>
>>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>>> Then it may happen that the computed slot already falls beyond the batch,
>>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>>> when the entry is a sibling entry.
>>> Is it possible to add a test case in lib/test_xarray.c for this?
>>> You can compile the tests with “make -C tools/testing/radix-tree”
>>> and run “./tools/testing/radix-tree/xarray”.
>>
>>
>> Sorry forgot to Cc you.
>> I can surely do that later, but does this patch look fine?
>
> I am not sure the exact situation you are describing, so I asked you
> to write a test case to demonstrate the issue. :)
>

IIUC, you mean xas needs to be a non sibling to make xas_get_order()
work? I wonder if you can use xas_prev() to find the first entry
in the multi-index batch then get the right order.

>>
>>
>>>
>>>> This patch is motivated by code inspection and not a real bug report.
>>>>
>>>> Signed-off-by: Dev Jain <dev.jain@arm.com>
>>>> ---
>>>> The patch applies on 6.15 kernel.
>>>>
>>>>   lib/xarray.c | 2 ++
>>>>   1 file changed, 2 insertions(+)
>>>>
>>>> diff --git a/lib/xarray.c b/lib/xarray.c
>>>> index 9644b18af18d..0f699766c24f 100644
>>>> --- a/lib/xarray.c
>>>> +++ b/lib/xarray.c
>>>> @@ -1917,6 +1917,8 @@ int xas_get_order(struct xa_state *xas)
>>>>   	if (!xas->xa_node)
>>>>   		return 0;
>>>>
>>>> +	XA_NODE_BUG_ON(xas->xa_node, xa_is_sibling(xa_entry(xas->xa,
>>>> +		       xas->xa_node, xas->xa_offset)));
>>>>   	for (;;) {
>>>>   		unsigned int slot = xas->xa_offset + (1 << order);
>>>>
>>>> -- 
>>>> 2.30.2
>>>
>>> Best Regards,
>>> Yan, Zi
>
>
> Best Regards,
> Yan, Zi


Best Regards,
Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Dev Jain]

On 30/05/25 4:17 am, Zi Yan wrote:
> On 28 May 2025, at 23:17, Dev Jain wrote:
>
>> On 28/05/25 10:42 pm, Zi Yan wrote:
>>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>>
>>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>>> Then it may happen that the computed slot already falls beyond the batch,
>>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>>> when the entry is a sibling entry.
>>> Is it possible to add a test case in lib/test_xarray.c for this?
>>> You can compile the tests with “make -C tools/testing/radix-tree”
>>> and run “./tools/testing/radix-tree/xarray”.
>>
>> Sorry forgot to Cc you.
>> I can surely do that later, but does this patch look fine?
> I am not sure the exact situation you are describing, so I asked you
> to write a test case to demonstrate the issue. :)


Suppose we have a shift-6 node having an order-9 entry => 8 - 1 = 7 siblings,
so assume the slots are at offset 0 till 7 in this node. If xas->xa_offset is 6,
then the code will compute order as 1 + xas->xa_node->shift = 7. So I mean to
say that the order computation must start from the beginning of the multi-slot
entries, that is, the non-sibling entry.


>
>>
>>>> This patch is motivated by code inspection and not a real bug report.
>>>>
>>>> Signed-off-by: Dev Jain <dev.jain@arm.com>
>>>> ---
>>>> The patch applies on 6.15 kernel.
>>>>
>>>>    lib/xarray.c | 2 ++
>>>>    1 file changed, 2 insertions(+)
>>>>
>>>> diff --git a/lib/xarray.c b/lib/xarray.c
>>>> index 9644b18af18d..0f699766c24f 100644
>>>> --- a/lib/xarray.c
>>>> +++ b/lib/xarray.c
>>>> @@ -1917,6 +1917,8 @@ int xas_get_order(struct xa_state *xas)
>>>>    	if (!xas->xa_node)
>>>>    		return 0;
>>>>
>>>> +	XA_NODE_BUG_ON(xas->xa_node, xa_is_sibling(xa_entry(xas->xa,
>>>> +		       xas->xa_node, xas->xa_offset)));
>>>>    	for (;;) {
>>>>    		unsigned int slot = xas->xa_offset + (1 << order);
>>>>
>>>> -- 
>>>> 2.30.2
>>> Best Regards,
>>> Yan, Zi
>
> Best Regards,
> Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Zi Yan]

On 29 May 2025, at 23:44, Dev Jain wrote:

> On 30/05/25 4:17 am, Zi Yan wrote:
>> On 28 May 2025, at 23:17, Dev Jain wrote:
>>
>>> On 28/05/25 10:42 pm, Zi Yan wrote:
>>>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>>>
>>>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>>>> Then it may happen that the computed slot already falls beyond the batch,
>>>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>>>> when the entry is a sibling entry.
>>>> Is it possible to add a test case in lib/test_xarray.c for this?
>>>> You can compile the tests with “make -C tools/testing/radix-tree”
>>>> and run “./tools/testing/radix-tree/xarray”.
>>>
>>> Sorry forgot to Cc you.
>>> I can surely do that later, but does this patch look fine?
>> I am not sure the exact situation you are describing, so I asked you
>> to write a test case to demonstrate the issue. :)
>
>
> Suppose we have a shift-6 node having an order-9 entry => 8 - 1 = 7 siblings,
> so assume the slots are at offset 0 till 7 in this node. If xas->xa_offset is 6,
> then the code will compute order as 1 + xas->xa_node->shift = 7. So I mean to
> say that the order computation must start from the beginning of the multi-slot
> entries, that is, the non-sibling entry.

Got it. Thanks for the explanation. It will be great to add this explanation
to the commit log.

I also notice that in the comment of xas_get_order() it says
“Called after xas_load()” and xas_load() returns NULL or an internal
entry for a sibling. So caller is responsible to make sure xas is not pointing
to a sibling entry. It is good to have a check here.

In terms of the patch, we are moving away from BUG()/BUG_ON(), so I wonder
if there is a less disruptive way of handling this. Something like return
-EINVAL instead with modified function comments and adding a comment
at the return -EIVAL saying something like caller needs to pass
a non-sibling entry.

Best Regards,
Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Dev Jain]

On 02/06/25 8:33 pm, Zi Yan wrote:
> On 29 May 2025, at 23:44, Dev Jain wrote:
>
>> On 30/05/25 4:17 am, Zi Yan wrote:
>>> On 28 May 2025, at 23:17, Dev Jain wrote:
>>>
>>>> On 28/05/25 10:42 pm, Zi Yan wrote:
>>>>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>>>>
>>>>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>>>>> Then it may happen that the computed slot already falls beyond the batch,
>>>>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>>>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>>>>> when the entry is a sibling entry.
>>>>> Is it possible to add a test case in lib/test_xarray.c for this?
>>>>> You can compile the tests with “make -C tools/testing/radix-tree”
>>>>> and run “./tools/testing/radix-tree/xarray”.
>>>> Sorry forgot to Cc you.
>>>> I can surely do that later, but does this patch look fine?
>>> I am not sure the exact situation you are describing, so I asked you
>>> to write a test case to demonstrate the issue. :)
>>
>> Suppose we have a shift-6 node having an order-9 entry => 8 - 1 = 7 siblings,
>> so assume the slots are at offset 0 till 7 in this node. If xas->xa_offset is 6,
>> then the code will compute order as 1 + xas->xa_node->shift = 7. So I mean to
>> say that the order computation must start from the beginning of the multi-slot
>> entries, that is, the non-sibling entry.
> Got it. Thanks for the explanation. It will be great to add this explanation
> to the commit log.
>
> I also notice that in the comment of xas_get_order() it says
> “Called after xas_load()” and xas_load() returns NULL or an internal
> entry for a sibling. So caller is responsible to make sure xas is not pointing
> to a sibling entry. It is good to have a check here.
>
> In terms of the patch, we are moving away from BUG()/BUG_ON(), so I wonder
> if there is a less disruptive way of handling this. Something like return
> -EINVAL instead with modified function comments and adding a comment
> at the return -EIVAL saying something like caller needs to pass
> a non-sibling entry.

What's the reason for moving away from BUG_ON()? I would think that it is
better that we don't have any overhead without the relevant debug config.
Also, returning any negative return value seems more disruptive :) we will
have to change all the callers to handle that, and in turn, handle that
for their callers, and so on.

>
> Best Regards,
> Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[David Hildenbrand]

On 03.06.25 07:23, Dev Jain wrote:
> 
> On 02/06/25 8:33 pm, Zi Yan wrote:
>> On 29 May 2025, at 23:44, Dev Jain wrote:
>>
>>> On 30/05/25 4:17 am, Zi Yan wrote:
>>>> On 28 May 2025, at 23:17, Dev Jain wrote:
>>>>
>>>>> On 28/05/25 10:42 pm, Zi Yan wrote:
>>>>>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>>>>>
>>>>>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>>>>>> Then it may happen that the computed slot already falls beyond the batch,
>>>>>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>>>>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>>>>>> when the entry is a sibling entry.
>>>>>> Is it possible to add a test case in lib/test_xarray.c for this?
>>>>>> You can compile the tests with “make -C tools/testing/radix-tree”
>>>>>> and run “./tools/testing/radix-tree/xarray”.
>>>>> Sorry forgot to Cc you.
>>>>> I can surely do that later, but does this patch look fine?
>>>> I am not sure the exact situation you are describing, so I asked you
>>>> to write a test case to demonstrate the issue. :)
>>>
>>> Suppose we have a shift-6 node having an order-9 entry => 8 - 1 = 7 siblings,
>>> so assume the slots are at offset 0 till 7 in this node. If xas->xa_offset is 6,
>>> then the code will compute order as 1 + xas->xa_node->shift = 7. So I mean to
>>> say that the order computation must start from the beginning of the multi-slot
>>> entries, that is, the non-sibling entry.
>> Got it. Thanks for the explanation. It will be great to add this explanation
>> to the commit log.
>>
>> I also notice that in the comment of xas_get_order() it says
>> “Called after xas_load()” and xas_load() returns NULL or an internal
>> entry for a sibling. So caller is responsible to make sure xas is not pointing
>> to a sibling entry. It is good to have a check here.
>>
>> In terms of the patch, we are moving away from BUG()/BUG_ON(), so I wonder
>> if there is a less disruptive way of handling this. Something like return
>> -EINVAL instead with modified function comments and adding a comment
>> at the return -EIVAL saying something like caller needs to pass
>> a non-sibling entry.
> 
> What's the reason for moving away from BUG_ON()?

BUG_ON is in general a bad thing. See 
Documentation/process/coding-style.rst and the history on the related 
changes for details.

Here, it is less critical than it looks.

XA_NODE_BUG_ON is only active with XA_DEBUG.

And XA_DEBUG is only defined in

tools/testing/shared/xarray-shared.h:#define XA_DEBUG

So IIUC, it's only active in selftests, and completely inactive in any 
kernel builds.

-- 
Cheers,

David / dhildenb

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Zi Yan]

On 3 Jun 2025, at 3:58, David Hildenbrand wrote:

> On 03.06.25 07:23, Dev Jain wrote:
>>
>> On 02/06/25 8:33 pm, Zi Yan wrote:
>>> On 29 May 2025, at 23:44, Dev Jain wrote:
>>>
>>>> On 30/05/25 4:17 am, Zi Yan wrote:
>>>>> On 28 May 2025, at 23:17, Dev Jain wrote:
>>>>>
>>>>>> On 28/05/25 10:42 pm, Zi Yan wrote:
>>>>>>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>>>>>>
>>>>>>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>>>>>>> Then it may happen that the computed slot already falls beyond the batch,
>>>>>>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>>>>>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>>>>>>> when the entry is a sibling entry.
>>>>>>> Is it possible to add a test case in lib/test_xarray.c for this?
>>>>>>> You can compile the tests with “make -C tools/testing/radix-tree”
>>>>>>> and run “./tools/testing/radix-tree/xarray”.
>>>>>> Sorry forgot to Cc you.
>>>>>> I can surely do that later, but does this patch look fine?
>>>>> I am not sure the exact situation you are describing, so I asked you
>>>>> to write a test case to demonstrate the issue. :)
>>>>
>>>> Suppose we have a shift-6 node having an order-9 entry => 8 - 1 = 7 siblings,
>>>> so assume the slots are at offset 0 till 7 in this node. If xas->xa_offset is 6,
>>>> then the code will compute order as 1 + xas->xa_node->shift = 7. So I mean to
>>>> say that the order computation must start from the beginning of the multi-slot
>>>> entries, that is, the non-sibling entry.
>>> Got it. Thanks for the explanation. It will be great to add this explanation
>>> to the commit log.
>>>
>>> I also notice that in the comment of xas_get_order() it says
>>> “Called after xas_load()” and xas_load() returns NULL or an internal
>>> entry for a sibling. So caller is responsible to make sure xas is not pointing
>>> to a sibling entry. It is good to have a check here.
>>>
>>> In terms of the patch, we are moving away from BUG()/BUG_ON(), so I wonder
>>> if there is a less disruptive way of handling this. Something like return
>>> -EINVAL instead with modified function comments and adding a comment
>>> at the return -EIVAL saying something like caller needs to pass
>>> a non-sibling entry.
>>
>> What's the reason for moving away from BUG_ON()?
>
> BUG_ON is in general a bad thing. See Documentation/process/coding-style.rst and the history on the related changes for details.
>
> Here, it is less critical than it looks.
>
> XA_NODE_BUG_ON is only active with XA_DEBUG.
>
> And XA_DEBUG is only defined in
>
> tools/testing/shared/xarray-shared.h:#define XA_DEBUG
>
> So IIUC, it's only active in selftests, and completely inactive in any kernel builds.

Oh, I missed that. But that also means this patch becomes a nop in kernel
builds.

Best Regards,
Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Dev Jain]

On 03/06/25 5:47 pm, Zi Yan wrote:
> On 3 Jun 2025, at 3:58, David Hildenbrand wrote:
>
>> On 03.06.25 07:23, Dev Jain wrote:
>>> On 02/06/25 8:33 pm, Zi Yan wrote:
>>>> On 29 May 2025, at 23:44, Dev Jain wrote:
>>>>
>>>>> On 30/05/25 4:17 am, Zi Yan wrote:
>>>>>> On 28 May 2025, at 23:17, Dev Jain wrote:
>>>>>>
>>>>>>> On 28/05/25 10:42 pm, Zi Yan wrote:
>>>>>>>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>>>>>>>
>>>>>>>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>>>>>>>> Then it may happen that the computed slot already falls beyond the batch,
>>>>>>>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>>>>>>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>>>>>>>> when the entry is a sibling entry.
>>>>>>>> Is it possible to add a test case in lib/test_xarray.c for this?
>>>>>>>> You can compile the tests with “make -C tools/testing/radix-tree”
>>>>>>>> and run “./tools/testing/radix-tree/xarray”.
>>>>>>> Sorry forgot to Cc you.
>>>>>>> I can surely do that later, but does this patch look fine?
>>>>>> I am not sure the exact situation you are describing, so I asked you
>>>>>> to write a test case to demonstrate the issue. :)
>>>>> Suppose we have a shift-6 node having an order-9 entry => 8 - 1 = 7 siblings,
>>>>> so assume the slots are at offset 0 till 7 in this node. If xas->xa_offset is 6,
>>>>> then the code will compute order as 1 + xas->xa_node->shift = 7. So I mean to
>>>>> say that the order computation must start from the beginning of the multi-slot
>>>>> entries, that is, the non-sibling entry.
>>>> Got it. Thanks for the explanation. It will be great to add this explanation
>>>> to the commit log.
>>>>
>>>> I also notice that in the comment of xas_get_order() it says
>>>> “Called after xas_load()” and xas_load() returns NULL or an internal
>>>> entry for a sibling. So caller is responsible to make sure xas is not pointing
>>>> to a sibling entry. It is good to have a check here.
>>>>
>>>> In terms of the patch, we are moving away from BUG()/BUG_ON(), so I wonder
>>>> if there is a less disruptive way of handling this. Something like return
>>>> -EINVAL instead with modified function comments and adding a comment
>>>> at the return -EIVAL saying something like caller needs to pass
>>>> a non-sibling entry.
>>> What's the reason for moving away from BUG_ON()?
>> BUG_ON is in general a bad thing. See Documentation/process/coding-style.rst and the history on the related changes for details.
>>
>> Here, it is less critical than it looks.
>>
>> XA_NODE_BUG_ON is only active with XA_DEBUG.
>>
>> And XA_DEBUG is only defined in
>>
>> tools/testing/shared/xarray-shared.h:#define XA_DEBUG
>>
>> So IIUC, it's only active in selftests, and completely inactive in any kernel builds.
> Oh, I missed that. But that also means this patch becomes a nop in kernel

Yes, but given other places are there with XA_NODE_BUG_ON(), I believe
this patch has some value :)

> builds.
>
> Best Regards,
> Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Zi Yan]

On 3 Jun 2025, at 8:59, Dev Jain wrote:

> On 03/06/25 5:47 pm, Zi Yan wrote:
>> On 3 Jun 2025, at 3:58, David Hildenbrand wrote:
>>
>>> On 03.06.25 07:23, Dev Jain wrote:
>>>> On 02/06/25 8:33 pm, Zi Yan wrote:
>>>>> On 29 May 2025, at 23:44, Dev Jain wrote:
>>>>>
>>>>>> On 30/05/25 4:17 am, Zi Yan wrote:
>>>>>>> On 28 May 2025, at 23:17, Dev Jain wrote:
>>>>>>>
>>>>>>>> On 28/05/25 10:42 pm, Zi Yan wrote:
>>>>>>>>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>>>>>>>>
>>>>>>>>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>>>>>>>>> Then it may happen that the computed slot already falls beyond the batch,
>>>>>>>>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>>>>>>>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>>>>>>>>> when the entry is a sibling entry.
>>>>>>>>> Is it possible to add a test case in lib/test_xarray.c for this?
>>>>>>>>> You can compile the tests with “make -C tools/testing/radix-tree”
>>>>>>>>> and run “./tools/testing/radix-tree/xarray”.
>>>>>>>> Sorry forgot to Cc you.
>>>>>>>> I can surely do that later, but does this patch look fine?
>>>>>>> I am not sure the exact situation you are describing, so I asked you
>>>>>>> to write a test case to demonstrate the issue. :)
>>>>>> Suppose we have a shift-6 node having an order-9 entry => 8 - 1 = 7 siblings,
>>>>>> so assume the slots are at offset 0 till 7 in this node. If xas->xa_offset is 6,
>>>>>> then the code will compute order as 1 + xas->xa_node->shift = 7. So I mean to
>>>>>> say that the order computation must start from the beginning of the multi-slot
>>>>>> entries, that is, the non-sibling entry.
>>>>> Got it. Thanks for the explanation. It will be great to add this explanation
>>>>> to the commit log.
>>>>>
>>>>> I also notice that in the comment of xas_get_order() it says
>>>>> “Called after xas_load()” and xas_load() returns NULL or an internal
>>>>> entry for a sibling. So caller is responsible to make sure xas is not pointing
>>>>> to a sibling entry. It is good to have a check here.
>>>>>
>>>>> In terms of the patch, we are moving away from BUG()/BUG_ON(), so I wonder
>>>>> if there is a less disruptive way of handling this. Something like return
>>>>> -EINVAL instead with modified function comments and adding a comment
>>>>> at the return -EIVAL saying something like caller needs to pass
>>>>> a non-sibling entry.
>>>> What's the reason for moving away from BUG_ON()?
>>> BUG_ON is in general a bad thing. See Documentation/process/coding-style.rst and the history on the related changes for details.
>>>
>>> Here, it is less critical than it looks.
>>>
>>> XA_NODE_BUG_ON is only active with XA_DEBUG.
>>>
>>> And XA_DEBUG is only defined in
>>>
>>> tools/testing/shared/xarray-shared.h:#define XA_DEBUG
>>>
>>> So IIUC, it's only active in selftests, and completely inactive in any kernel builds.
>> Oh, I missed that. But that also means this patch becomes a nop in kernel
>
> Yes, but given other places are there with XA_NODE_BUG_ON(), I believe
> this patch has some value :)

Sure. Can you please also add something like below to the function comment?
“The xas cannot be a sibling entry, otherwise the result will be wrong”
It saves other’s time to infer it from the added XA_NODE_BUG_ON().

Thanks.

Best Regards,
Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Dev Jain]

On 03/06/25 7:27 pm, Zi Yan wrote:
> On 3 Jun 2025, at 8:59, Dev Jain wrote:
>
>> On 03/06/25 5:47 pm, Zi Yan wrote:
>>> On 3 Jun 2025, at 3:58, David Hildenbrand wrote:
>>>
>>>> On 03.06.25 07:23, Dev Jain wrote:
>>>>> On 02/06/25 8:33 pm, Zi Yan wrote:
>>>>>> On 29 May 2025, at 23:44, Dev Jain wrote:
>>>>>>
>>>>>>> On 30/05/25 4:17 am, Zi Yan wrote:
>>>>>>>> On 28 May 2025, at 23:17, Dev Jain wrote:
>>>>>>>>
>>>>>>>>> On 28/05/25 10:42 pm, Zi Yan wrote:
>>>>>>>>>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>>>>>>>>>
>>>>>>>>>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>>>>>>>>>> Then it may happen that the computed slot already falls beyond the batch,
>>>>>>>>>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>>>>>>>>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>>>>>>>>>> when the entry is a sibling entry.
>>>>>>>>>> Is it possible to add a test case in lib/test_xarray.c for this?
>>>>>>>>>> You can compile the tests with “make -C tools/testing/radix-tree”
>>>>>>>>>> and run “./tools/testing/radix-tree/xarray”.
>>>>>>>>> Sorry forgot to Cc you.
>>>>>>>>> I can surely do that later, but does this patch look fine?
>>>>>>>> I am not sure the exact situation you are describing, so I asked you
>>>>>>>> to write a test case to demonstrate the issue. :)
>>>>>>> Suppose we have a shift-6 node having an order-9 entry => 8 - 1 = 7 siblings,
>>>>>>> so assume the slots are at offset 0 till 7 in this node. If xas->xa_offset is 6,
>>>>>>> then the code will compute order as 1 + xas->xa_node->shift = 7. So I mean to
>>>>>>> say that the order computation must start from the beginning of the multi-slot
>>>>>>> entries, that is, the non-sibling entry.
>>>>>> Got it. Thanks for the explanation. It will be great to add this explanation
>>>>>> to the commit log.
>>>>>>
>>>>>> I also notice that in the comment of xas_get_order() it says
>>>>>> “Called after xas_load()” and xas_load() returns NULL or an internal
>>>>>> entry for a sibling. So caller is responsible to make sure xas is not pointing
>>>>>> to a sibling entry. It is good to have a check here.
>>>>>>
>>>>>> In terms of the patch, we are moving away from BUG()/BUG_ON(), so I wonder
>>>>>> if there is a less disruptive way of handling this. Something like return
>>>>>> -EINVAL instead with modified function comments and adding a comment
>>>>>> at the return -EIVAL saying something like caller needs to pass
>>>>>> a non-sibling entry.
>>>>> What's the reason for moving away from BUG_ON()?
>>>> BUG_ON is in general a bad thing. See Documentation/process/coding-style.rst and the history on the related changes for details.
>>>>
>>>> Here, it is less critical than it looks.
>>>>
>>>> XA_NODE_BUG_ON is only active with XA_DEBUG.
>>>>
>>>> And XA_DEBUG is only defined in
>>>>
>>>> tools/testing/shared/xarray-shared.h:#define XA_DEBUG
>>>>
>>>> So IIUC, it's only active in selftests, and completely inactive in any kernel builds.
>>> Oh, I missed that. But that also means this patch becomes a nop in kernel
>> Yes, but given other places are there with XA_NODE_BUG_ON(), I believe
>> this patch has some value :)
> Sure. Can you please also add something like below to the function comment?
> “The xas cannot be a sibling entry, otherwise the result will be wrong”
> It saves other’s time to infer it from the added XA_NODE_BUG_ON().

Sure.

>
> Thanks.
>
> Best Regards,
> Yan, Zi

Re: [PATCH] xarray: Add a BUG_ON() to ensure caller is not sibling

[Dev Jain]

[-- Attachment #1: Type: text/plain, Size: 2187 bytes --]


On 30/05/25 4:17 am, Zi Yan wrote:
> On 28 May 2025, at 23:17, Dev Jain wrote:
>
>> On 28/05/25 10:42 pm, Zi Yan wrote:
>>> On 28 May 2025, at 7:31, Dev Jain wrote:
>>>
>>>> Suppose xas is pointing somewhere near the end of the multi-entry batch.
>>>> Then it may happen that the computed slot already falls beyond the batch,
>>>> thus breaking the loop due to !xa_is_sibling(), and computing the wrong
>>>> order. Thus ensure that the caller is aware of this by triggering a BUG
>>>> when the entry is a sibling entry.
>>> Is it possible to add a test case in lib/test_xarray.c for this?
>>> You can compile the tests with “make -C tools/testing/radix-tree”
>>> and run “./tools/testing/radix-tree/xarray”.
>>
>> Sorry forgot to Cc you.
>> I can surely do that later, but does this patch look fine?
> I am not sure the exact situation you are describing, so I asked you
> to write a test case to demonstrate the issue. :)

I added the following:

diff--git a/lib/test_xarray.c b/lib/test_xarray.c
index 080a39d22e73..44fcc947a5b6100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -2111,6+2111,8@@ staticnoinline voidcheck_xas_get_order(structxarray *xa)
rcu_read_lock();
xas_load(&xas);
XA_BUG_ON(xa, xas_get_order(&xas) != order);
+ if(xas.xa_node)
+ XA_BUG_ON(xa, xa_is_sibling(xa_entry(xas.xa, xas.xa_node, 
xas.xa_offset)));
rcu_read_unlock();
}
and the test passes.


>
>>
>>>> This patch is motivated by code inspection and not a real bug report.
>>>>
>>>> Signed-off-by: Dev Jain<dev.jain@arm.com>
>>>> ---
>>>> The patch applies on 6.15 kernel.
>>>>
>>>>    lib/xarray.c | 2 ++
>>>>    1 file changed, 2 insertions(+)
>>>>
>>>> diff --git a/lib/xarray.c b/lib/xarray.c
>>>> index 9644b18af18d..0f699766c24f 100644
>>>> --- a/lib/xarray.c
>>>> +++ b/lib/xarray.c
>>>> @@ -1917,6 +1917,8 @@ int xas_get_order(struct xa_state *xas)
>>>>    	if (!xas->xa_node)
>>>>    		return 0;
>>>>
>>>> +	XA_NODE_BUG_ON(xas->xa_node, xa_is_sibling(xa_entry(xas->xa,
>>>> +		       xas->xa_node, xas->xa_offset)));
>>>>    	for (;;) {
>>>>    		unsigned int slot = xas->xa_offset + (1 << order);
>>>>
>>>> -- 
>>>> 2.30.2
>>> Best Regards,
>>> Yan, Zi
>
> Best Regards,
> Yan, Zi

[-- Attachment #2: Type: text/html, Size: 6358 bytes --]