[PATCH] Fix undefined behavior in radix-tree.c.

[PATCH] Fix undefined behavior in radix-tree.c.

[Adam Buchbinder]

When running with UndefinedBehaviorSanitizer, the tests produce the following
error:

  radix-tree.c:836:30: runtime error: shift exponent 18446744073709551613
  is too large for 64-bit type 'unsigned long'

(That's a negative shift exponent represented as an unsigned long.)

Even though the value is discarded in those cases, it's still undefined
behavior; see the C99 standard, section 6.5.7, paragraph three: "If the
value of the right operand is negative [...] the behavior is undefined."

Signed-off-by: Adam Buchbinder <abuchbinder@google.com>
---
 radix-tree.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/radix-tree.c b/radix-tree.c
index 4f295fc..7457944 100644
--- a/radix-tree.c
+++ b/radix-tree.c
@@ -833,10 +833,10 @@ int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
 static unsigned long __maxindex(unsigned int height)
 {
 	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
-	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
+	unsigned long index = ~0UL;
 
-	if (tmp >= RADIX_TREE_INDEX_BITS)
-		index = ~0UL;
+	if (tmp < RADIX_TREE_INDEX_BITS)
+		index = (index >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
 	return index;
 }
 
-- 
2.0.0.526.g5318336

Re: [PATCH] Fix undefined behavior in radix-tree.c.

[Satoru Takeuchi]

Hi Adam,

(2014/06/14 6:18), Adam Buchbinder wrote:
> When running with UndefinedBehaviorSanitizer, the tests produce the following
> error:
> 
>    radix-tree.c:836:30: runtime error: shift exponent 18446744073709551613
>    is too large for 64-bit type 'unsigned long'
> 
> (That's a negative shift exponent represented as an unsigned long.)
> 
> Even though the value is discarded in those cases, it's still undefined
> behavior; see the C99 standard, section 6.5.7, paragraph three: "If the
> value of the right operand is negative [...] the behavior is undefined."
> 
> Signed-off-by: Adam Buchbinder <abuchbinder@google.com>

It looks good to me.

Reviewed-by: Satoru Takeuchi <takeuchi_satoru@jp.fujitsu.com>

Thanks,
Satoru

> ---
>   radix-tree.c | 6 +++---
>   1 file changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/radix-tree.c b/radix-tree.c
> index 4f295fc..7457944 100644
> --- a/radix-tree.c
> +++ b/radix-tree.c
> @@ -833,10 +833,10 @@ int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
>   static unsigned long __maxindex(unsigned int height)
>   {
>   	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
> -	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
> +	unsigned long index = ~0UL;
>   
> -	if (tmp >= RADIX_TREE_INDEX_BITS)
> -		index = ~0UL;
> +	if (tmp < RADIX_TREE_INDEX_BITS)
> +		index = (index >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
>   	return index;
>   }
>   
> 

Re: [PATCH] Fix undefined behavior in radix-tree.c.

[David Sterba]

On Wed, Jun 18, 2014 at 03:20:30PM +0900, Satoru Takeuchi wrote:
> Hi Adam,
> 
> (2014/06/14 6:18), Adam Buchbinder wrote:
> > When running with UndefinedBehaviorSanitizer, the tests produce the following
> > error:
> > 
> >    radix-tree.c:836:30: runtime error: shift exponent 18446744073709551613
> >    is too large for 64-bit type 'unsigned long'
> > 
> > (That's a negative shift exponent represented as an unsigned long.)
> > 
> > Even though the value is discarded in those cases, it's still undefined
> > behavior; see the C99 standard, section 6.5.7, paragraph three: "If the
> > value of the right operand is negative [...] the behavior is undefined."
> > 
> > Signed-off-by: Adam Buchbinder <abuchbinder@google.com>
> 
> It looks good to me.
> 
> Reviewed-by: Satoru Takeuchi <takeuchi_satoru@jp.fujitsu.com>

Thank you both.

The file is taken from kernel/lib/radix-tree.c and has diverged a bit so
it could be missing more bugfixes.

Re: [PATCH] Fix undefined behavior in radix-tree.c.

[Satoru Takeuchi]

Hi David, Adam,

(2014/06/18 23:43), David Sterba wrote:
> On Wed, Jun 18, 2014 at 03:20:30PM +0900, Satoru Takeuchi wrote:
>> Hi Adam,
>>
>> (2014/06/14 6:18), Adam Buchbinder wrote:
>>> When running with UndefinedBehaviorSanitizer, the tests produce the following
>>> error:
>>>
>>>     radix-tree.c:836:30: runtime error: shift exponent 18446744073709551613
>>>     is too large for 64-bit type 'unsigned long'
>>>
>>> (That's a negative shift exponent represented as an unsigned long.)
>>>
>>> Even though the value is discarded in those cases, it's still undefined
>>> behavior; see the C99 standard, section 6.5.7, paragraph three: "If the
>>> value of the right operand is negative [...] the behavior is undefined."
>>>
>>> Signed-off-by: Adam Buchbinder <abuchbinder@google.com>
>>
>> It looks good to me.
>>
>> Reviewed-by: Satoru Takeuchi <takeuchi_satoru@jp.fujitsu.com>
>
> Thank you both.
>
> The file is taken from kernel/lib/radix-tree.c and has diverged a bit so
> it could be missing more bugfixes.

I confirmed the kenel doesn't have such problem.

lib/radix-tree.c (kernel code):
===============================================================================
static __init unsigned long __maxindex(unsigned int height)
{
         unsigned int width = height * RADIX_TREE_MAP_SHIFT;
         int shift = RADIX_TREE_INDEX_BITS - width;

         if (shift < 0)
                 return ~0UL;
         if (shift >= BITS_PER_LONG)
                 return 0UL;
         return ~0UL >> shift;
}
===============================================================================

It's fixed at 430d275a399.

===============================================================================
commit 430d275a399175c7c0673459738979287ec1fd22
Author: Peter Lund <firefly@vax64.dk>
Date:   Tue Oct 16 23:29:35 2007 -0700

     avoid negative (and full-width) shifts in radix-tree.c
...
===============================================================================

Adam, David, how about import this patch from kernel, rather than
writing btrfs-progs's own patch?

P.S.
I consider It's better to regularly sync such utility code with
the newest kernel code for the long term...

Thanks,
Satoru

> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: [PATCH] Fix undefined behavior in radix-tree.c.

[David Sterba]

On Thu, Jun 19, 2014 at 10:10:55AM +0900, Satoru Takeuchi wrote:
> It's fixed at 430d275a399.
> 
> ===============================================================================
> commit 430d275a399175c7c0673459738979287ec1fd22
> Author: Peter Lund <firefly@vax64.dk>
> Date:   Tue Oct 16 23:29:35 2007 -0700
> 
>     avoid negative (and full-width) shifts in radix-tree.c
> ...
> ===============================================================================
> 
> Adam, David, how about import this patch from kernel, rather than
> writing btrfs-progs's own patch?

Well, I think there's non-trivial time spent by Adam on the patch so I'd
rather keep the credit, even if a patch that backports the fix from
kernel would look cleaner in git log. Such things happen, sometimes it
makes sense to replace patches or do changes inline.

The progs development is moving forward quickly, a clean patch history
is most useful when there is a separate stable branch that receives
bugfixes as it helps the backporters to identify complete fixes. Not the
case for progs right now.

> I consider It's better to regularly sync such utility code with
> the newest kernel code for the long term...

Yes. The radix- or rb- tree code does not change often though, we can do
a sync now and be fine for some time.

Re: [PATCH] Fix undefined behavior in radix-tree.c.

[Satoru Takeuchi]

Hi David,

(2014/06/19 22:28), David Sterba wrote:
> On Thu, Jun 19, 2014 at 10:10:55AM +0900, Satoru Takeuchi wrote:
>> It's fixed at 430d275a399.
>>
>> ===============================================================================
>> commit 430d275a399175c7c0673459738979287ec1fd22
>> Author: Peter Lund <firefly@vax64.dk>
>> Date:   Tue Oct 16 23:29:35 2007 -0700
>>
>>      avoid negative (and full-width) shifts in radix-tree.c
>> ...
>> ===============================================================================
>>
>> Adam, David, how about import this patch from kernel, rather than
>> writing btrfs-progs's own patch?
>
> Well, I think there's non-trivial time spent by Adam on the patch so I'd
> rather keep the credit, even if a patch that backports the fix from
> kernel would look cleaner in git log. Such things happen, sometimes it
> makes sense to replace patches or do changes inline.
>
> The progs development is moving forward quickly, a clean patch history
> is most useful when there is a separate stable branch that receives
> bugfixes as it helps the backporters to identify complete fixes. Not the
> case for progs right now.
>
>> I consider It's better to regularly sync such utility code with
>> the newest kernel code for the long term...
>
> Yes. The radix- or rb- tree code does not change often though, we can do
> a sync now and be fine for some time.

OK, I see. Thank you for your clear explanation.

Thanks,
Satoru