Unexpected behavior from xarray - Is it expected?

Unexpected behavior from xarray - Is it expected?

[Boaz Harrosh]

Matthew Hi

First I want to thank you for the great xarray tool. I use it heavily with great joy & ease

However I have encountered a bug in my code which I did not expect, as follows:

I need code in the very hot-path that is looping on the xarray in an unusual way.
What I need is to scan a range from x-x+l but I need to break on first "hole" ie.
first entry that was not __xa_store() to. So I am using this loop:
	rcu_read_lock();

	for (xae = xas_load(&xas); xae; xae = xas_next(&xas)) {
		...
	}

Every thing works fine and I usually get a NULL from xas_next() (or xas_load())
on first hole, And the loop exits.

But in the case that I have entered a *single* xa_store() *at index 0*, but then try
to GET a range 0-Y I get these unexpected results:
	xas_next() will return the same entry repeatedly
I have put some prints (see full code below):

zuf: pi_pr [zuf_pi_get_range:248] [5] [@x0] GET bn=0x11e8 xae=0x23d1 xa_index=0x0 xa_offset=0x0
zuf: pi_pr [zuf_pi_get_range:248] [5] [@x1] GET bn=0x11e8 xae=0x23d1 xa_index=0x1 xa_offset=0x0
zuf: pi_pr [zuf_pi_get_range:248] [5] [@x2] GET bn=0x11e8 xae=0x23d1 xa_index=0x2 xa_offset=0x0
zuf: pi_pr [zuf_pi_get_range:248] [5] [@x3] GET bn=0x11e8 xae=0x23d1 xa_index=0x3 xa_offset=0x0
zuf: pi_pr [zuf_pi_get_range:248] [5] [@x4] GET bn=0x11e8 xae=0x23d1 xa_index=0x4 xa_offset=0x0
zuf: pi_pr [zuf_pi_get_range:248] [5] [@x5] GET bn=0x11e8 xae=0x23d1 xa_index=0x5 xa_offset=0x0
zuf: pi_pr [zuf_pi_get_range:248] [5] [@x6] GET bn=0x11e8 xae=0x23d1 xa_index=0x6 xa_offset=0x0

The loop only stopped because of some other condition.

[Q] Is this expected from a single xa_store() at 0?

[I am not even sure how to safely check this because consecutive entries may have
 the same exact value.

 Should I check for xa_offset not changing or should I use something else other than
 xas_next()?

 Do I must use xa_load() and take/release the rcu_lock every iteration?
]

Here is the full code.

<pi.c>
#include <linux/xarray.h>

#define xa_2_bn(xae)	xa_to_value(xae)

struct _pi_info {
	/* IN */
	ulong start;	/* start index to get	*/
	uint requested;	/* Num bns requested	*/
	/* OUT */
	ulong *bns;	/* array of block-numbers */
	uint cached;	/* Number of bns filled from page-index */
};

void zuf_pi_get_range(struct inode *inode, struct _pi_info *pi)
{
	XA_STATE(xas, &inode->i_mapping->i_pages, pi->start);
	void *xae;

	rcu_read_lock();

	for (xae = xas_load(&xas); xae; xae = xas_next(&xas)) {
		ulong  bn;

		if (xas_retry(&xas, xae)) {
			zuf_warn("See this yet e=0x%lx" _FMT_XAS "\n",
				 (ulong)xae, _PR_XAS(xas));
			continue;
		}

		bn = xa_2_bn(xae);

		zuf_dbg_pi("[%ld] [@x%lx] GET bn=0x%lx xae=0x%lx xa_index=0x%lx xa_offset=0x%x\n",
			   inode->i_ino, pi->start + pi->cached, bn, (ulong)xae, xas.xa_index, xas.xa_offset);

		pi->bns[pi->cached++] = bn;
		if (pi->cached == pi->requested)
			break; /* ALL DONE */
	}

	rcu_read_unlock();
}
<pi.c>

Thank you for looking, good day
Boaz

Re: Unexpected behavior from xarray - Is it expected?

[Boaz Harrosh]

On 14/07/2020 14:24, Boaz Harrosh wrote:
> Matthew Hi
> 

The below patch will off course revert to the behavior I have expected from
single-entry-at-0 and the call to xas_next().

But not sure it is the fix you would like.

[An option-2 below also works]

Please advise

------
option-1
------
git diff --stat -p -M -W HEAD -- /net/Bfire/home/boaz/dev/zufs/zuf/lib/xarray.c
 lib/xarray.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 446b956c9188..1cebb148cae6 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -171,28 +171,28 @@ static void *set_bounds(struct xa_state *xas)
 /*
  * Starts a walk.  If the @xas is already valid, we assume that it's on
  * the right path and just return where we've got to.  If we're in an
  * error state, return NULL.  If the index is outside the current scope
  * of the xarray, return NULL without changing @xas->xa_node.  Otherwise
  * set @xas->xa_node to NULL and return the current head of the array.
  */
 static void *xas_start(struct xa_state *xas)
 {
 	void *entry;
 
-	if (xas_valid(xas))
+	if (xas_valid(xas) && (xas->xa_node || !xas->xa_index))
 		return xas_reload(xas);
 	if (xas_error(xas))
 		return NULL;
 
 	entry = xa_head(xas->xa);
 	if (!xa_is_node(entry)) {
 		if (xas->xa_index)
 			return set_bounds(xas);
 	} else {
 		if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)
 			return set_bounds(xas);
 	}
 
 	xas->xa_node = NULL;
 	return entry;
 }

------
option-2
------
git diff --stat -p -M lib/xarray.c
 lib/xarray.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 446b956c9188..a9576acd34ab 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -186,8 +186,9 @@ static void *xas_start(struct xa_state *xas)
 
 	entry = xa_head(xas->xa);
 	if (!xa_is_node(entry)) {
+		set_bounds(xas);
 		if (xas->xa_index)
-			return set_bounds(xas);
+			return NULL;
 	} else {
 		if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)
 			return set_bounds(xas);

> First I want to thank you for the great xarray tool. I use it heavily with great joy & ease
> 
> However I have encountered a bug in my code which I did not expect, as follows:
> 
> I need code in the very hot-path that is looping on the xarray in an unusual way.
> What I need is to scan a range from x-x+l but I need to break on first "hole" ie.
> first entry that was not __xa_store() to. So I am using this loop:
> 	rcu_read_lock();
> 
> 	for (xae = xas_load(&xas); xae; xae = xas_next(&xas)) {
> 		...
> 	}
> 
> Every thing works fine and I usually get a NULL from xas_next() (or xas_load())
> on first hole, And the loop exits.
> 
> But in the case that I have entered a *single* xa_store() *at index 0*, but then try
> to GET a range 0-Y I get these unexpected results:
> 	xas_next() will return the same entry repeatedly
> I have put some prints (see full code below):
> 
> zuf: pi_pr [zuf_pi_get_range:248] [5] [@x0] GET bn=0x11e8 xae=0x23d1 xa_index=0x0 xa_offset=0x0
> zuf: pi_pr [zuf_pi_get_range:248] [5] [@x1] GET bn=0x11e8 xae=0x23d1 xa_index=0x1 xa_offset=0x0
> zuf: pi_pr [zuf_pi_get_range:248] [5] [@x2] GET bn=0x11e8 xae=0x23d1 xa_index=0x2 xa_offset=0x0
> zuf: pi_pr [zuf_pi_get_range:248] [5] [@x3] GET bn=0x11e8 xae=0x23d1 xa_index=0x3 xa_offset=0x0
> zuf: pi_pr [zuf_pi_get_range:248] [5] [@x4] GET bn=0x11e8 xae=0x23d1 xa_index=0x4 xa_offset=0x0
> zuf: pi_pr [zuf_pi_get_range:248] [5] [@x5] GET bn=0x11e8 xae=0x23d1 xa_index=0x5 xa_offset=0x0
> zuf: pi_pr [zuf_pi_get_range:248] [5] [@x6] GET bn=0x11e8 xae=0x23d1 xa_index=0x6 xa_offset=0x0
> 
> The loop only stopped because of some other condition.
> 
> [Q] Is this expected from a single xa_store() at 0?
> 
> [I am not even sure how to safely check this because consecutive entries may have
>  the same exact value.
> 
>  Should I check for xa_offset not changing or should I use something else other than
>  xas_next()?
> 
>  Do I must use xa_load() and take/release the rcu_lock every iteration?
> ]
> 
> Here is the full code.
> 
> <pi.c>
> #include <linux/xarray.h>
> 
> #define xa_2_bn(xae)	xa_to_value(xae)
> 
> struct _pi_info {
> 	/* IN */
> 	ulong start;	/* start index to get	*/
> 	uint requested;	/* Num bns requested	*/
> 	/* OUT */
> 	ulong *bns;	/* array of block-numbers */
> 	uint cached;	/* Number of bns filled from page-index */
> };
> 
> void zuf_pi_get_range(struct inode *inode, struct _pi_info *pi)
> {
> 	XA_STATE(xas, &inode->i_mapping->i_pages, pi->start);
> 	void *xae;
> 
> 	rcu_read_lock();
> 
> 	for (xae = xas_load(&xas); xae; xae = xas_next(&xas)) {
> 		ulong  bn;
> 
> 		if (xas_retry(&xas, xae)) {
> 			zuf_warn("See this yet e=0x%lx" _FMT_XAS "\n",
> 				 (ulong)xae, _PR_XAS(xas));
> 			continue;
> 		}
> 
> 		bn = xa_2_bn(xae);
> 
> 		zuf_dbg_pi("[%ld] [@x%lx] GET bn=0x%lx xae=0x%lx xa_index=0x%lx xa_offset=0x%x\n",
> 			   inode->i_ino, pi->start + pi->cached, bn, (ulong)xae, xas.xa_index, xas.xa_offset);
> 
> 		pi->bns[pi->cached++] = bn;
> 		if (pi->cached == pi->requested)
> 			break; /* ALL DONE */
> 	}
> 
> 	rcu_read_unlock();
> }
> <pi.c>
> 
> Thank you for looking, good day
> Boaz
> 

Re: Unexpected behavior from xarray - Is it expected?

[Matthew Wilcox]

On Tue, Jul 14, 2020 at 02:24:18PM +0300, Boaz Harrosh wrote:
> Matthew Hi
> 
> First I want to thank you for the great xarray tool. I use it heavily with great joy & ease
> 
> However I have encountered a bug in my code which I did not expect, as follows:
> 
> I need code in the very hot-path that is looping on the xarray in an unusual way.
> What I need is to scan a range from x-x+l but I need to break on first "hole" ie.
> first entry that was not __xa_store() to. So I am using this loop:
> 	rcu_read_lock();
> 
> 	for (xae = xas_load(&xas); xae; xae = xas_next(&xas)) {
> 		...
> 	}
> 
> Every thing works fine and I usually get a NULL from xas_next() (or xas_load())
> on first hole, And the loop exits.
> 
> But in the case that I have entered a *single* xa_store() *at index 0*, but then try
> to GET a range 0-Y I get these unexpected results:
> 	xas_next() will return the same entry repeatedly

I thought this was fixed in commit 91abab83839aa2eba073e4a63c729832fdb27ea1
Do you have that commit in your tree?

Re: Unexpected behavior from xarray - Is it expected?

[Boaz Harrosh]

On 14/07/2020 16:46, Matthew Wilcox wrote:
> On Tue, Jul 14, 2020 at 02:24:18PM +0300, Boaz Harrosh wrote:
<>
>> But in the case that I have entered a *single* xa_store() *at index 0*, but then try
>> to GET a range 0-Y I get these unexpected results:
>> 	xas_next() will return the same entry repeatedly
> 
> I thought this was fixed in commit 91abab83839aa2eba073e4a63c729832fdb27ea1
> Do you have that commit in your tree?
> 

Haa! so so sorry. You are right I am on a Linux-v5.3 based tree and only
v5.4 contains this fix.

(I will carry the workaround for older Kernels on user-machines)

Sorry for the noise
Boaz