[PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys

[PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys

[Darrick J. Wong]

From: Darrick J. Wong <darrick.wong@oracle.com>

In xfs_bmbt_diff_two_keys, we perform a signed int64_t subtraction with
two unsigned 64-bit quantities.  If the second quantity is actually the
"maximum" key (all ones) as used in _query_all, the subtraction
effectively becomes addition of two positive numbers and the function
returns incorrect results.  Fix this with explicit comparisons of the
unsigned values.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
 fs/xfs/libxfs/xfs_bmap_btree.c |   16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_bmap_btree.c b/fs/xfs/libxfs/xfs_bmap_btree.c
index fbb18ba5d905..3c1a805b3775 100644
--- a/fs/xfs/libxfs/xfs_bmap_btree.c
+++ b/fs/xfs/libxfs/xfs_bmap_btree.c
@@ -400,8 +400,20 @@ xfs_bmbt_diff_two_keys(
 	union xfs_btree_key	*k1,
 	union xfs_btree_key	*k2)
 {
-	return (int64_t)be64_to_cpu(k1->bmbt.br_startoff) -
-			  be64_to_cpu(k2->bmbt.br_startoff);
+	uint64_t		a = be64_to_cpu(k1->bmbt.br_startoff);
+	uint64_t		b = be64_to_cpu(k2->bmbt.br_startoff);
+
+	/*
+	 * Note: This routine previously casted a and b to int64 and subtracted
+	 * them to generate a result.  This lead to problems if b was the
+	 * "maximum" key value (all ones) being signed incorrectly, hence this
+	 * somewhat less efficient version.
+	 */
+	if (a > b)
+		return 1;
+	else if (b > a)
+		return -1;
+	return 0;
 }
 
 static xfs_failaddr_t

Re: [PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys

[Christoph Hellwig]

On Mon, Aug 26, 2019 at 11:38:03AM -0700, Darrick J. Wong wrote:
> From: Darrick J. Wong <darrick.wong@oracle.com>
> 
> In xfs_bmbt_diff_two_keys, we perform a signed int64_t subtraction with
> two unsigned 64-bit quantities.  If the second quantity is actually the
> "maximum" key (all ones) as used in _query_all, the subtraction
> effectively becomes addition of two positive numbers and the function
> returns incorrect results.  Fix this with explicit comparisons of the
> unsigned values.
> 
> Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
> ---
>  fs/xfs/libxfs/xfs_bmap_btree.c |   16 ++++++++++++++--
>  1 file changed, 14 insertions(+), 2 deletions(-)
> 
> diff --git a/fs/xfs/libxfs/xfs_bmap_btree.c b/fs/xfs/libxfs/xfs_bmap_btree.c
> index fbb18ba5d905..3c1a805b3775 100644
> --- a/fs/xfs/libxfs/xfs_bmap_btree.c
> +++ b/fs/xfs/libxfs/xfs_bmap_btree.c
> @@ -400,8 +400,20 @@ xfs_bmbt_diff_two_keys(
>  	union xfs_btree_key	*k1,
>  	union xfs_btree_key	*k2)
>  {
> -	return (int64_t)be64_to_cpu(k1->bmbt.br_startoff) -
> -			  be64_to_cpu(k2->bmbt.br_startoff);
> +	uint64_t		a = be64_to_cpu(k1->bmbt.br_startoff);
> +	uint64_t		b = be64_to_cpu(k2->bmbt.br_startoff);
> +
> +	/*
> +	 * Note: This routine previously casted a and b to int64 and subtracted
> +	 * them to generate a result.  This lead to problems if b was the
> +	 * "maximum" key value (all ones) being signed incorrectly, hence this
> +	 * somewhat less efficient version.

Comments documenting what was done previously are a bit of a weird
style, as the reader generally could not care less what there was
previously.

> +	 */
> +	if (a > b)
> +		return 1;
> +	else if (b > a)
> +		return -1;
> +	return 0;

Looks good.  I wonder if we should have a helper for this through,
as basically any compare function taking 64-bit values will have the
same boilerplate.

I suggest to add a helper like:

/*
 * Compare to signed 64-bit values and return an signed 32-bit integer
 * value that is 1, -1 or 0 for various compare callbacks.
 */
static inline int cmp_s64(s64 a, s64 b)
{
	if (a > b)
		return 1;
	else if (b > a)
		return -1;
	return 0;
}

and then the above just comes:

	return cmp_s64(be64_to_cpu(k1->bmbt.br_startoff),
		       be64_to_cpu(k2->bmbt.br_startof));

and we can probably clean up various other places inside (and outside,
but we can leave that for others) as well.  I'll cook up a patch if
you feel this is not worth your time.

Re: [PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys

[Darrick J. Wong]

On Thu, Aug 29, 2019 at 12:23:18AM -0700, Christoph Hellwig wrote:
> On Mon, Aug 26, 2019 at 11:38:03AM -0700, Darrick J. Wong wrote:
> > From: Darrick J. Wong <darrick.wong@oracle.com>
> > 
> > In xfs_bmbt_diff_two_keys, we perform a signed int64_t subtraction with
> > two unsigned 64-bit quantities.  If the second quantity is actually the
> > "maximum" key (all ones) as used in _query_all, the subtraction
> > effectively becomes addition of two positive numbers and the function
> > returns incorrect results.  Fix this with explicit comparisons of the
> > unsigned values.
> > 
> > Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
> > ---
> >  fs/xfs/libxfs/xfs_bmap_btree.c |   16 ++++++++++++++--
> >  1 file changed, 14 insertions(+), 2 deletions(-)
> > 
> > diff --git a/fs/xfs/libxfs/xfs_bmap_btree.c b/fs/xfs/libxfs/xfs_bmap_btree.c
> > index fbb18ba5d905..3c1a805b3775 100644
> > --- a/fs/xfs/libxfs/xfs_bmap_btree.c
> > +++ b/fs/xfs/libxfs/xfs_bmap_btree.c
> > @@ -400,8 +400,20 @@ xfs_bmbt_diff_two_keys(
> >  	union xfs_btree_key	*k1,
> >  	union xfs_btree_key	*k2)
> >  {
> > -	return (int64_t)be64_to_cpu(k1->bmbt.br_startoff) -
> > -			  be64_to_cpu(k2->bmbt.br_startoff);
> > +	uint64_t		a = be64_to_cpu(k1->bmbt.br_startoff);
> > +	uint64_t		b = be64_to_cpu(k2->bmbt.br_startoff);
> > +
> > +	/*
> > +	 * Note: This routine previously casted a and b to int64 and subtracted
> > +	 * them to generate a result.  This lead to problems if b was the
> > +	 * "maximum" key value (all ones) being signed incorrectly, hence this
> > +	 * somewhat less efficient version.
> 
> Comments documenting what was done previously are a bit of a weird
> style, as the reader generally could not care less what there was
> previously.
> 
> > +	 */
> > +	if (a > b)
> > +		return 1;
> > +	else if (b > a)
> > +		return -1;
> > +	return 0;
> 
> Looks good.  I wonder if we should have a helper for this through,
> as basically any compare function taking 64-bit values will have the
> same boilerplate.
> 
> I suggest to add a helper like:
> 
> /*
>  * Compare to signed 64-bit values and return an signed 32-bit integer
>  * value that is 1, -1 or 0 for various compare callbacks.
>  */
> static inline int cmp_s64(s64 a, s64 b)
> {
> 	if (a > b)
> 		return 1;
> 	else if (b > a)
> 		return -1;
> 	return 0;
> }

A signed s64 comparison would just break the diff_two_keys function
again.  The reason for the big dorky comment is to point out that the
signed comparison doesn't work for xfs_btree_query_all, because it does:

	union xfs_btree_key		low_key;
	union xfs_btree_key		high_key;

	memset(&cur->bc_rec, 0, sizeof(cur->bc_rec));
	memset(&low_key, 0, sizeof(low_key));
	memset(&high_key, 0xFF, sizeof(high_key));

	return xfs_btree_simple_query_range(cur, &low_key, &high_key, fn, priv);

The query range function compares each record's key against high_key to
decide if it's time to stop.  Since br_startoff is set to all 1s, if you
force a unsigned 64-bit comparison then you'll correctly iterate all the
records because all records in the bmbt will have:

	br_startoff < 18446744073709551615ULL

and it'll iterate until there are no more bmbt records.  If you do a
signed 64-bit comparison, however, it'll gate its comparison on this:

	br_startoff < -1LL

which is always false, so _query_range exits without iterating
anything.

> and then the above just comes:
> 
> 	return cmp_s64(be64_to_cpu(k1->bmbt.br_startoff),
> 		       be64_to_cpu(k2->bmbt.br_startof));
> 
> and we can probably clean up various other places inside (and outside,
> but we can leave that for others) as well.  I'll cook up a patch if
> you feel this is not worth your time.

I wouldn't mind you cooking up a patch (I think I'm going to be busy
for a few hours digging through all of Dave's patches) but the helper
needs to be cmp_u64.  Though ... I also think the logic in the patched
bmbt diff_two_keys is easy enough to follow along.

(Personally I find the subtraction logic harder to follow, though it
generates less asm code on x64...)

--D

Re: [PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys

[Christoph Hellwig]

On Thu, Aug 29, 2019 at 08:41:58AM -0700, Darrick J. Wong wrote:
> A signed s64 comparison would just break the diff_two_keys function
> again.  The reason for the big dorky comment is to point out that the
> signed comparison doesn't work for xfs_btree_query_all, because it does:

Even more reason to have a good helper encapsulating and documenting
all the caveats :)

> I wouldn't mind you cooking up a patch (I think I'm going to be busy
> for a few hours digging through all of Dave's patches) but the helper
> needs to be cmp_u64.  Though ... I also think the logic in the patched
> bmbt diff_two_keys is easy enough to follow along.
> 
> (Personally I find the subtraction logic harder to follow, though it
> generates less asm code on x64...)

The subtraction is a little weird, but very efficient if it works.
I'm not sure any of our users is worth the micro-optimization, though.

I'll cook up a series over the weekend.