Re: [PATCH] radix-tree: get_slot_offset() returns invalid offset when parent is NULL

[Wei Yang]

On Tue, Oct 10, 2017 at 01:53:11PM -0700, Andrew Morton wrote:
>On Tue, 10 Oct 2017 10:52:01 +0800 Wei Yang <richard.weiyang@xxxxxxxxx> wrote:
>
>> When parent is NULL, get_slot_offset() returns almost the address of slot.
>> This is an invalid value for offset.
>> 
>> One possible scenario happens on deleting #0 index, when it is the only one
>> in tree.
>> 
>> Current behavior doesn't harm the system, because the offset will not be
>> used when parent is NULL in the following procedure or parent is checked
>> before get_slot_offset() called. While it is still not safe to return an
>> invalid offset.
>> 
>> This patch returns 0 when parent is NULL in get_slot_offset().
>> 
>
>I'm confused.  If parent=NULL, get_slot_offset() will crash the kernel.
>So why "Current behavior doesn't harm the system"?
>

Andrew,

I am confused at first glace too, while this may be a feature of the compiler.

For example, the definition of offsetof(), which leverage the trick of the
compiler.

    #define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)

BTW, I have another question on the implementation of radix tree.

#Question: why 6 is one of the choice of RADIX_TREE_MAP_SHIFT

Currently, the shift of the tree is defined as below.

    #define RADIX_TREE_MAP_SHIFT	(CONFIG_BASE_SMALL ? 4 : 6)

The index in the tree is with type unsigned long, which means the size is 
32bits or 64bits.

    32 % 4 = 0, 64 % 4 = 0

    32 % 6 = 2, 64 % 6 = 4

This means when the tree shift is 6 and represents the max index, there would
be some unused slots at the top level.

So why we chose 6 instead of a 2^N?

The original commit is 139e561660fe11e0fc35e142a800df3dd7d03e9d, which I don't
see some reason for this choice.

If possible, I suggest to change this value to a power of 2. Or maybe I missed
some critical reason behind this.

Thanks for your time and review.

>> --- a/lib/radix-tree.c
>> +++ b/lib/radix-tree.c
>> @@ -119,7 +119,7 @@ bool is_sibling_entry(const struct radix_tree_node *parent, void *node)
>>  static inline unsigned long
>>  get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot)
>>  {
>> -	return slot - parent->slots;
>> +	return parent ? (slot - parent->slots):0;
>>  }
>>  
>>  static unsigned int radix_tree_descend(const struct radix_tree_node *parent,

-- 
Wei Yang
Help you, Help me