xfs: fix diff_two_keys calculation for cnt btree

[PATCH] xfs: fix diff_two_keys calculation for cnt btree

Posted by Fedor Pchelkin 9 months, 2 weeks ago

Currently the difference is computed on 32-bit unsigned values although
eventually it is stored in a variable of int64_t type. This gives awkward
results, e.g. when the diff _should_ be negative, it is represented as
some large positive int64_t value.

Perform the calculations directly in int64_t as all other diff_two_keys
routines actually do.

Found by Linux Verification Center (linuxtesting.org) with Svace static
analysis tool.

Fixes: 08438b1e386b ("xfs: plumb in needed functions for range querying of the freespace btrees")
Cc: stable@vger.kernel.org
Signed-off-by: Fedor Pchelkin <pchelkin@ispras.ru>
---
 fs/xfs/libxfs/xfs_alloc_btree.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_alloc_btree.c b/fs/xfs/libxfs/xfs_alloc_btree.c
index a4ac37ba5d51..b3c54ae90e25 100644
--- a/fs/xfs/libxfs/xfs_alloc_btree.c
+++ b/fs/xfs/libxfs/xfs_alloc_btree.c
@@ -238,13 +238,13 @@ xfs_cntbt_diff_two_keys(
 	ASSERT(!mask || (mask->alloc.ar_blockcount &&
 			 mask->alloc.ar_startblock));
 
-	diff =  be32_to_cpu(k1->alloc.ar_blockcount) -
-		be32_to_cpu(k2->alloc.ar_blockcount);
+	diff = (int64_t)be32_to_cpu(k1->alloc.ar_blockcount) -
+			be32_to_cpu(k2->alloc.ar_blockcount);
 	if (diff)
 		return diff;
 
-	return  be32_to_cpu(k1->alloc.ar_startblock) -
-		be32_to_cpu(k2->alloc.ar_startblock);
+	return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) -
+			be32_to_cpu(k2->alloc.ar_startblock);
 }
 
 static xfs_failaddr_t
-- 
2.49.0

Re: [PATCH] xfs: fix diff_two_keys calculation for cnt btree

Posted by Darrick J. Wong 9 months, 2 weeks ago

On Sat, Apr 26, 2025 at 04:42:31PM +0300, Fedor Pchelkin wrote:
> Currently the difference is computed on 32-bit unsigned values although
> eventually it is stored in a variable of int64_t type. This gives awkward
> results, e.g. when the diff _should_ be negative, it is represented as
> some large positive int64_t value.
> 
> Perform the calculations directly in int64_t as all other diff_two_keys
> routines actually do.
> 
> Found by Linux Verification Center (linuxtesting.org) with Svace static
> analysis tool.
> 
> Fixes: 08438b1e386b ("xfs: plumb in needed functions for range querying of the freespace btrees")
> Cc: stable@vger.kernel.org
> Signed-off-by: Fedor Pchelkin <pchelkin@ispras.ru>
> ---
>  fs/xfs/libxfs/xfs_alloc_btree.c | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
> 
> diff --git a/fs/xfs/libxfs/xfs_alloc_btree.c b/fs/xfs/libxfs/xfs_alloc_btree.c
> index a4ac37ba5d51..b3c54ae90e25 100644
> --- a/fs/xfs/libxfs/xfs_alloc_btree.c
> +++ b/fs/xfs/libxfs/xfs_alloc_btree.c
> @@ -238,13 +238,13 @@ xfs_cntbt_diff_two_keys(
>  	ASSERT(!mask || (mask->alloc.ar_blockcount &&
>  			 mask->alloc.ar_startblock));
>  
> -	diff =  be32_to_cpu(k1->alloc.ar_blockcount) -
> -		be32_to_cpu(k2->alloc.ar_blockcount);
> +	diff = (int64_t)be32_to_cpu(k1->alloc.ar_blockcount) -
> +			be32_to_cpu(k2->alloc.ar_blockcount);

Perhaps it's time to hoist cmp_int to include/ and refactor all these
things to use it?

#define cmp_int(l, r)          ((l > r) - (l < r))

--D

>  	if (diff)
>  		return diff;
>  
> -	return  be32_to_cpu(k1->alloc.ar_startblock) -
> -		be32_to_cpu(k2->alloc.ar_startblock);
> +	return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) -
> +			be32_to_cpu(k2->alloc.ar_startblock);
>  }
>  
>  static xfs_failaddr_t
> -- 
> 2.49.0
> 
>

Re: [PATCH] xfs: fix diff_two_keys calculation for cnt btree

Posted by Fedor Pchelkin 9 months, 1 week ago

On Sat, 26. Apr 08:03, Darrick J. Wong wrote:
> On Sat, Apr 26, 2025 at 04:42:31PM +0300, Fedor Pchelkin wrote:
> > Currently the difference is computed on 32-bit unsigned values although
> > eventually it is stored in a variable of int64_t type. This gives awkward
> > results, e.g. when the diff _should_ be negative, it is represented as
> > some large positive int64_t value.
> > 
> > Perform the calculations directly in int64_t as all other diff_two_keys
> > routines actually do.
> > 
> > Found by Linux Verification Center (linuxtesting.org) with Svace static
> > analysis tool.
> > 
> > Fixes: 08438b1e386b ("xfs: plumb in needed functions for range querying of the freespace btrees")
> > Cc: stable@vger.kernel.org
> > Signed-off-by: Fedor Pchelkin <pchelkin@ispras.ru>
> > ---
> >  fs/xfs/libxfs/xfs_alloc_btree.c | 8 ++++----
> >  1 file changed, 4 insertions(+), 4 deletions(-)
> > 
> > diff --git a/fs/xfs/libxfs/xfs_alloc_btree.c b/fs/xfs/libxfs/xfs_alloc_btree.c
> > index a4ac37ba5d51..b3c54ae90e25 100644
> > --- a/fs/xfs/libxfs/xfs_alloc_btree.c
> > +++ b/fs/xfs/libxfs/xfs_alloc_btree.c
> > @@ -238,13 +238,13 @@ xfs_cntbt_diff_two_keys(
> >  	ASSERT(!mask || (mask->alloc.ar_blockcount &&
> >  			 mask->alloc.ar_startblock));
> >  
> > -	diff =  be32_to_cpu(k1->alloc.ar_blockcount) -
> > -		be32_to_cpu(k2->alloc.ar_blockcount);
> > +	diff = (int64_t)be32_to_cpu(k1->alloc.ar_blockcount) -
> > +			be32_to_cpu(k2->alloc.ar_blockcount);
> 
> Perhaps it's time to hoist cmp_int to include/ and refactor all these
> things to use it?
> 
> #define cmp_int(l, r)          ((l > r) - (l < r))
> 
> --D

No need to apply this one as a fix (e.g. for further inclusion into stable
releases) ?

I'll send out the refactoring patches for review when the cmp_int()-moving
one hits Linus' tree - it's currently in mm-nonmm-unstable branch of
akpm/mm.git and in linux-next repo. Though I'm not aware of how xfs trees
interact with linux-next.

Re: [PATCH] xfs: fix diff_two_keys calculation for cnt btree

Posted by Fedor Pchelkin 9 months, 2 weeks ago

Hi,

On Sat, 26. Apr 08:03, Darrick J. Wong wrote:
> On Sat, Apr 26, 2025 at 04:42:31PM +0300, Fedor Pchelkin wrote:
> > Currently the difference is computed on 32-bit unsigned values although
> > eventually it is stored in a variable of int64_t type. This gives awkward
> > results, e.g. when the diff _should_ be negative, it is represented as
> > some large positive int64_t value.
> > 
> > Perform the calculations directly in int64_t as all other diff_two_keys
> > routines actually do.
> > 
> > Found by Linux Verification Center (linuxtesting.org) with Svace static
> > analysis tool.
> > 
> > Fixes: 08438b1e386b ("xfs: plumb in needed functions for range querying of the freespace btrees")
> > Cc: stable@vger.kernel.org
> > Signed-off-by: Fedor Pchelkin <pchelkin@ispras.ru>
> > ---
> >  fs/xfs/libxfs/xfs_alloc_btree.c | 8 ++++----
> >  1 file changed, 4 insertions(+), 4 deletions(-)
> > 
> > diff --git a/fs/xfs/libxfs/xfs_alloc_btree.c b/fs/xfs/libxfs/xfs_alloc_btree.c
> > index a4ac37ba5d51..b3c54ae90e25 100644
> > --- a/fs/xfs/libxfs/xfs_alloc_btree.c
> > +++ b/fs/xfs/libxfs/xfs_alloc_btree.c
> > @@ -238,13 +238,13 @@ xfs_cntbt_diff_two_keys(
> >  	ASSERT(!mask || (mask->alloc.ar_blockcount &&
> >  			 mask->alloc.ar_startblock));
> >  
> > -	diff =  be32_to_cpu(k1->alloc.ar_blockcount) -
> > -		be32_to_cpu(k2->alloc.ar_blockcount);
> > +	diff = (int64_t)be32_to_cpu(k1->alloc.ar_blockcount) -
> > +			be32_to_cpu(k2->alloc.ar_blockcount);
> 
> Perhaps it's time to hoist cmp_int to include/ and refactor all these
> things to use it?
> 
> #define cmp_int(l, r)          ((l > r) - (l < r))
> 
> --D
> 

Thanks, that would be worth it, I think. Though the current xfs
***diff_two_keys() implementations try to compute and return the actual
difference between two values, not the result of their comparison. Now
looking at diff_two_keys() use cases, I see only the latter one is needed
anyway so a good bit to refactor.

The thing I'm pondering over now is whether the macro in its current
form is okay to move up to include/. There is no argument restrictions and
typechecking intended to catch up obviously misleading usage patterns
though we'd need some if this is hoisted to a generic header and exported
for potential use by others?

There are four places where cmp_int is defined at the moment:
- bcachefs
- md/bcache
- xfs_zone_gc
- pipe.c

bcachefs is the largest user having all kinds of different arguments
providing to the macro, bitfields included. It also has several rather
generic wrappers, like u64_cmp, unsigned_cmp, u8_cmp, cmp_le32 and
others..

AF_UNIX code even has

	#define cmp_ptr(l, r)	(((l) > (r)) - ((l) < (r)))

for pointer comparisons.

So in my opinion we'd probably need to come up with something like a new
include/linux/cmp.h header where all this stuff will be gathered in a
generic way.

Any objections/suggestions on that? Or just moving

	#define cmp_int(l, r)          ((l > r) - (l < r))

to a generic header and dropping the corresponding defines from the
separate in-kernel users would be enough in this case?

--
Thanks,
Fedor

> >  	if (diff)
> >  		return diff;
> >  
> > -	return  be32_to_cpu(k1->alloc.ar_startblock) -
> > -		be32_to_cpu(k2->alloc.ar_startblock);
> > +	return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) -
> > +			be32_to_cpu(k2->alloc.ar_startblock);
> >  }
> >  
> >  static xfs_failaddr_t
> > -- 
> > 2.49.0
> > 
> >

Re: [PATCH] xfs: fix diff_two_keys calculation for cnt btree

Posted by Kent Overstreet 9 months, 2 weeks ago

On Sun, Apr 27, 2025 at 02:56:39PM +0300, Fedor Pchelkin wrote:
> Hi,
> 
> On Sat, 26. Apr 08:03, Darrick J. Wong wrote:
> > On Sat, Apr 26, 2025 at 04:42:31PM +0300, Fedor Pchelkin wrote:
> > > Currently the difference is computed on 32-bit unsigned values although
> > > eventually it is stored in a variable of int64_t type. This gives awkward
> > > results, e.g. when the diff _should_ be negative, it is represented as
> > > some large positive int64_t value.
> > > 
> > > Perform the calculations directly in int64_t as all other diff_two_keys
> > > routines actually do.
> > > 
> > > Found by Linux Verification Center (linuxtesting.org) with Svace static
> > > analysis tool.
> > > 
> > > Fixes: 08438b1e386b ("xfs: plumb in needed functions for range querying of the freespace btrees")
> > > Cc: stable@vger.kernel.org
> > > Signed-off-by: Fedor Pchelkin <pchelkin@ispras.ru>
> > > ---
> > >  fs/xfs/libxfs/xfs_alloc_btree.c | 8 ++++----
> > >  1 file changed, 4 insertions(+), 4 deletions(-)
> > > 
> > > diff --git a/fs/xfs/libxfs/xfs_alloc_btree.c b/fs/xfs/libxfs/xfs_alloc_btree.c
> > > index a4ac37ba5d51..b3c54ae90e25 100644
> > > --- a/fs/xfs/libxfs/xfs_alloc_btree.c
> > > +++ b/fs/xfs/libxfs/xfs_alloc_btree.c
> > > @@ -238,13 +238,13 @@ xfs_cntbt_diff_two_keys(
> > >  	ASSERT(!mask || (mask->alloc.ar_blockcount &&
> > >  			 mask->alloc.ar_startblock));
> > >  
> > > -	diff =  be32_to_cpu(k1->alloc.ar_blockcount) -
> > > -		be32_to_cpu(k2->alloc.ar_blockcount);
> > > +	diff = (int64_t)be32_to_cpu(k1->alloc.ar_blockcount) -
> > > +			be32_to_cpu(k2->alloc.ar_blockcount);
> > 
> > Perhaps it's time to hoist cmp_int to include/ and refactor all these
> > things to use it?
> > 
> > #define cmp_int(l, r)          ((l > r) - (l < r))
> > 
> > --D
> > 
> 
> Thanks, that would be worth it, I think. Though the current xfs
> ***diff_two_keys() implementations try to compute and return the actual
> difference between two values, not the result of their comparison. Now
> looking at diff_two_keys() use cases, I see only the latter one is needed
> anyway so a good bit to refactor.
> 
> 
> The thing I'm pondering over now is whether the macro in its current
> form is okay to move up to include/. There is no argument restrictions and
> typechecking intended to catch up obviously misleading usage patterns
> though we'd need some if this is hoisted to a generic header and exported
> for potential use by others?
> 
> There are four places where cmp_int is defined at the moment:
> - bcachefs
> - md/bcache
> - xfs_zone_gc
> - pipe.c
> 
> bcachefs is the largest user having all kinds of different arguments
> providing to the macro, bitfields included. It also has several rather
> generic wrappers, like u64_cmp, unsigned_cmp, u8_cmp, cmp_le32 and
> others..
> 
> AF_UNIX code even has
> 
> 	#define cmp_ptr(l, r)	(((l) > (r)) - ((l) < (r)))
> 
> for pointer comparisons.
> 
> 
> So in my opinion we'd probably need to come up with something like a new
> include/linux/cmp.h header where all this stuff will be gathered in a
> generic way.
> 
> Any objections/suggestions on that? Or just moving
> 
> 	#define cmp_int(l, r)          ((l > r) - (l < r))

Ack. It avoids underflow issues when using a subtract and gcc generates
good code for it.