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

["Darrick J. Wong" <darrick.wong@oracle.com>]

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