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

[Satoru Takeuchi <takeuchi_satoru@jp.fujitsu.com>]

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
>