* [PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys
@ 2019-08-26 18:38 Darrick J. Wong
2019-08-29 7:23 ` Christoph Hellwig
0 siblings, 1 reply; 4+ messages in thread
From: Darrick J. Wong @ 2019-08-26 18:38 UTC (permalink / raw)
To: xfs
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
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys
2019-08-26 18:38 [PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys Darrick J. Wong
@ 2019-08-29 7:23 ` Christoph Hellwig
2019-08-29 15:41 ` Darrick J. Wong
0 siblings, 1 reply; 4+ messages in thread
From: Christoph Hellwig @ 2019-08-29 7:23 UTC (permalink / raw)
To: Darrick J. Wong; +Cc: xfs
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys
2019-08-29 7:23 ` Christoph Hellwig
@ 2019-08-29 15:41 ` Darrick J. Wong
2019-08-30 15:30 ` Christoph Hellwig
0 siblings, 1 reply; 4+ messages in thread
From: Darrick J. Wong @ 2019-08-29 15:41 UTC (permalink / raw)
To: Christoph Hellwig; +Cc: xfs
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys
2019-08-29 15:41 ` Darrick J. Wong
@ 2019-08-30 15:30 ` Christoph Hellwig
0 siblings, 0 replies; 4+ messages in thread
From: Christoph Hellwig @ 2019-08-30 15:30 UTC (permalink / raw)
To: Darrick J. Wong; +Cc: Christoph Hellwig, xfs
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2019-08-30 15:30 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-08-26 18:38 [PATCH] xfs: fix sign handling problem in xfs_bmbt_diff_two_keys Darrick J. Wong
2019-08-29 7:23 ` Christoph Hellwig
2019-08-29 15:41 ` Darrick J. Wong
2019-08-30 15:30 ` Christoph Hellwig
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).