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@xxxxxxxxxx>
> >
> > 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@xxxxxxxxxx>
> > ---
> > 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
