Skip to contentSkip to conversation

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

PATCH Superseded Dev Jain 3 participants 14 messages May 28, 2025 – Jun 3, 2025

Subsystems (4)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Dev Jain

author
#0 lore raw

PATCH 1/1 xarray: Add a BUG_ON() to ensure caller is not sibling

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.

---
The patch applies on 6.15 kernel.

 lib/xarray.c | 2 ++
 1 file changed, 2 insertions(+)
lib/xarray.c +2 -0
index 9644b18af18d..0f699766c24f 100644
@@ -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);
 
Signature · 1 line
2.30.2
#1 lore raw
Quoted 5 lines · 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.

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

Quoted 25 lines

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

---
The patch applies on 6.15 kernel.

 lib/xarray.c | 2 ++
 1 file changed, 2 insertions(+)
lib/xarray.c +2 -0
index 9644b18af18d..0f699766c24f 100644
@@ -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);
 
Signature · 1 line
2.30.2

Best Regards,
Yan, Zi

author
#2 lore raw
Quoted 10 lines · Zi Yan
Quoted 5 lines · 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.

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?

Quoted 28 lines
Quoted 25 lines

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

---
The patch applies on 6.15 kernel.

  lib/xarray.c | 2 ++
  1 file changed, 2 insertions(+)
lib/xarray.c +2 -0
index 9644b18af18d..0f699766c24f 100644
@@ -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);
 
Signature · 1 line
2.30.2

Best Regards,
Yan, Zi

#3 lore raw
Quoted 8 lines · Dev Jain
Quoted 7 lines · Zi Yan
Quoted 5 lines · 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.

Quoted 7 lines
Quoted 3 lines

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. :)

Quoted 25 lines
Quoted 25 lines
Quoted 25 lines

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

---
The patch applies on 6.15 kernel.

  lib/xarray.c | 2 ++
  1 file changed, 2 insertions(+)
lib/xarray.c +2 -0
index 9644b18af18d..0f699766c24f 100644
@@ -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);
 
Quoted 5 lines
Quoted 5 lines
Quoted 2 lines
Signature · 1 line
2.30.2

Best Regards,
Yan, Zi

Best Regards,
Yan, Zi

#4 lore raw
Quoted 15 lines · Zi Yan
Quoted 13 lines · Dev Jain
Quoted 10 lines · Zi Yan
Quoted 5 lines · 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.

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

Quoted 6 lines
Quoted 2 lines

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.

Quoted 32 lines
Quoted 25 lines
Quoted 25 lines
Quoted 25 lines

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

---
The patch applies on 6.15 kernel.

  lib/xarray.c | 2 ++
  1 file changed, 2 insertions(+)
lib/xarray.c +2 -0
index 9644b18af18d..0f699766c24f 100644
@@ -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);
 
Quoted 5 lines
Quoted 5 lines
Quoted 2 lines
Signature · 1 line
2.30.2

Best Regards,
Yan, Zi

Quoted 2 lines

Best Regards,
Yan, Zi

Best Regards,
Yan, Zi

author
#5 lore raw
In reply to Zi Yan
Quoted 10 lines · Zi Yan
Quoted 8 lines · Dev Jain
Quoted 7 lines · Zi Yan
Quoted 5 lines · 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.

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

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.

Quoted 31 lines
Quoted 24 lines
Quoted 24 lines
Quoted 24 lines

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

---
The patch applies on 6.15 kernel.

   lib/xarray.c | 2 ++
   1 file changed, 2 insertions(+)
lib/xarray.c +2 -0
index 9644b18af18d..0f699766c24f 100644
@@ -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);
 
Quoted 4 lines
Quoted 4 lines
Quoted 2 lines
Signature · 1 line
2.30.2

Best Regards,
Yan, Zi

Best Regards,
Yan, Zi

#6 lore raw
Quoted 21 lines · Dev Jain
Quoted 10 lines · Zi Yan
Quoted 8 lines · Dev Jain
Quoted 7 lines · Zi Yan
Quoted 5 lines · 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.

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

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. :)

Quoted 5 lines

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

author
#7 lore raw
Quoted 34 lines · Zi Yan
Quoted 16 lines · Dev Jain
Quoted 15 lines · Zi Yan
Quoted 13 lines · Dev Jain
Quoted 10 lines · Zi Yan
Quoted 5 lines · 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.

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?

Quoted 8 lines
Quoted 2 lines

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.

Quoted 5 lines

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.

Quoted 3 lines

Best Regards,
Yan, Zi

#8 lore raw
Quoted 36 lines · Dev Jain
Quoted 34 lines · Zi Yan
Quoted 16 lines · Dev Jain
Quoted 15 lines · Zi Yan
Quoted 13 lines · Dev Jain
Quoted 10 lines · Zi Yan
Quoted 5 lines · 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.

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?

Quoted 8 lines
Quoted 2 lines

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.

Quoted 7 lines
Quoted 5 lines

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.

Signature · 3 lines
Cheers,

David / dhildenb
#9 lore raw
Quoted 49 lines · David Hildenbrand
Quoted 36 lines · Dev Jain
Quoted 34 lines · Zi Yan
Quoted 16 lines · Dev Jain
Quoted 15 lines · Zi Yan
Quoted 13 lines · Dev Jain
Quoted 10 lines · Zi Yan
Quoted 5 lines · 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.

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?

Quoted 8 lines
Quoted 2 lines

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.

Quoted 7 lines
Quoted 5 lines

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.

Quoted 7 lines

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

author
#10 lore raw
Quoted 47 lines · Zi Yan
Quoted 45 lines · David Hildenbrand
Quoted 34 lines · Dev Jain
Quoted 33 lines · Zi Yan
Quoted 16 lines · Dev Jain
Quoted 15 lines · Zi Yan
Quoted 13 lines · Dev Jain
Quoted 10 lines · Zi Yan
Quoted 5 lines · 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.

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?

Quoted 7 lines
Quoted 2 lines

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.

Quoted 6 lines
Quoted 5 lines

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.

Quoted 8 lines
Quoted 7 lines

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 :)

Quoted 4 lines

builds.

Best Regards,
Yan, Zi

#11 lore raw
Quoted 52 lines · Dev Jain
Quoted 51 lines · Zi Yan
Quoted 49 lines · David Hildenbrand
Quoted 34 lines · Dev Jain
Quoted 33 lines · Zi Yan
Quoted 16 lines · Dev Jain
Quoted 15 lines · Zi Yan
Quoted 13 lines · Dev Jain
Quoted 10 lines · Zi Yan
Quoted 5 lines · 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.

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?

Quoted 7 lines
Quoted 2 lines

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.

Quoted 6 lines
Quoted 5 lines

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

Quoted 7 lines
Quoted 4 lines
Quoted 3 lines

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

author
#12 lore raw
Quoted 56 lines · Zi Yan
Quoted 54 lines · Dev Jain
Quoted 53 lines · Zi Yan
Quoted 51 lines · David Hildenbrand
Quoted 34 lines · Dev Jain
Quoted 33 lines · Zi Yan
Quoted 16 lines · Dev Jain
Quoted 15 lines · Zi Yan
Quoted 13 lines · Dev Jain
Quoted 10 lines · Zi Yan
Quoted 5 lines · 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.

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?

Quoted 7 lines
Quoted 2 lines

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.

Quoted 6 lines
Quoted 5 lines

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

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines
Quoted 1 line

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.

Quoted 5 lines

Thanks.

Best Regards,
Yan, Zi

author
#13 lore raw
In reply to Zi Yan
Quoted 10 lines · Zi Yan
Quoted 8 lines · Dev Jain
Quoted 7 lines · Zi Yan
Quoted 5 lines · 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.

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

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

lib/test_xarray.c +0 -0
@@ -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.

Quoted 31 lines
Quoted 24 lines
Quoted 24 lines
Quoted 24 lines

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

---
The patch applies on 6.15 kernel.

   lib/xarray.c | 2 ++
   1 file changed, 2 insertions(+)
lib/xarray.c +2 -0
index 9644b18af18d..0f699766c24f 100644
@@ -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);
 
Quoted 4 lines
Quoted 4 lines
Quoted 2 lines
Signature · 1 line
2.30.2

Best Regards,
Yan, Zi

Best Regards,
Yan, Zi