Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1314439 > unrolled thread

Re: Found a very little mistake in radix-tree.h(linux kernel 4.3)

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Found a very little mistake in radix-tree.h(linux kernel 4.3) Konstantin Khlebnikov <koct9i@gmail.com> - 2016-01-21 20:20 +0100
    Re: Found a very little mistake in radix-tree.h(linux kernel 4.3) Konstantin Khlebnikov <koct9i@gmail.com> - 2016-01-22 16:20 +0100

#1314439 — Re: Found a very little mistake in radix-tree.h(linux kernel 4.3)

On Thu, Jan 21, 2016 at 12:10 PM, Nemo Yu <mzer0.yu@gmail.com> wrote:
> I am sorry bothering you. It was the name in the header file
>>
>> Copyright (C) 2012 Konstantin Khlebnikov
>
>  made me sending this email to you.

I've added iterator routine here. That's all.

>
> On Thu, Jan 21, 2016 at 4:37 PM, Konstantin Khlebnikov <koct9i@gmail.com>
> wrote:
>>
>> On Thu, Jan 21, 2016 at 11:20 AM, Nemo Yu <mzer0.yu@gmail.com> wrote:
>> > Hello Khlebnikov, I am Nemo.
>> >
>> > I found a very little mistake in your radix-tree.h of linux kernel 4.3(I
>> > don't know how is it going in kernel 4.4), here is the code:
>> >
>> >> 80  #define RADIX_TREE_HEIGHT_SHIFT (RADIX_TREE_MAX_PATH + 1)
>> >
>> >
>> > I think it should be:
>> >
>> >> 80  #define RADIX_TREE_HEIGHT_SHIFT (log2(RADIX_TREE_MAX_PATH) + 1)
>> >
>> >
>> > where log2 is the binary logarithm.
>> >
>> > (read the kernel 4.3 online:
>> > http://lxr.free-electrons.com/source/include/linux/radix-tree.h)
>> >
>> > And, rename RADIX_TREE_MAX_PATH to RADIX_TREE_MAX_HEIGHT will be better
>> > to
>> > understand(just suggestions). I can do a patch if you agree.

Yep RADIX_TREE_HEIGHT_SHIFT -> count bits required for keeping height but
bigger value is ok.  It's used only once for splitting 32-bit node->path into
two numbers offset in parent node in higher bits and subtree height in lower.

This is relatively new code by Johannes Weiner,
see commit 449dd6984d0e47643c04c807f609dd56d48d5bcc

Probably it's easier to swap these parts - bit width of offset in node
already here
RADIX_TREE_MAP_SHIFT

All currenly used combinations are fine 32/64bit CONFIG_BASE_SMALL=y/n
and even debug mode RADIX_TREE_MAP_SHIFT=3 are fine.

But  64-bit with 2-bit per node will not work: max-path is 32 in this case.

>>
>> This isn't my code, but I'll check this later.
>> It would be better to add linux-kernel@vger.kernel.org into CC.
>> Maybe somebody who has more free time will answer you sooner.
>
>

send plain text mail, LKML forbids html.

[toc] | [next] | [standalone]

#1315068

On Fri, Jan 22, 2016 at 3:11 AM, Nemo Yu <mzer0.yu@gmail.com> wrote:
> Thank you for replying.
>
> 1) Where may I find the commit 449dd6984d0e47643c04c807f609dd56d48d5bcc ?

In linux git. See torvalds/linux.git at http://git.kernel.org
I think you should read this too http://kernelnewbies.org/

> 2) After a simple calculating, I think both "path" and "count" variable in
> radix_tree_node structure can be unsigned short type against unsigned int
> now, if you have the binary logarithm.

This migh have performance impact, not all achitectures have 16-bit operations.
And very unlinkely will save any memory.

> 3) There is another question that, radix_tree should not consider height ==
> 0 because we can make assumption height > 1, or force height > 1, then some
> unnecessary branches(if-else statement) can be removed.
>
> On Fri, Jan 22, 2016 at 3:15 AM, Konstantin Khlebnikov <koct9i@gmail.com>
> wrote:
>>
>> On Thu, Jan 21, 2016 at 12:10 PM, Nemo Yu <mzer0.yu@gmail.com> wrote:
>> > I am sorry bothering you. It was the name in the header file
>> >>
>> >> Copyright (C) 2012 Konstantin Khlebnikov
>> >
>> >  made me sending this email to you.
>>
>> I've added iterator routine here. That's all.
>>
>> >
>> > On Thu, Jan 21, 2016 at 4:37 PM, Konstantin Khlebnikov
>> > <koct9i@gmail.com>
>> > wrote:
>> >>
>> >> On Thu, Jan 21, 2016 at 11:20 AM, Nemo Yu <mzer0.yu@gmail.com> wrote:
>> >> > Hello Khlebnikov, I am Nemo.
>> >> >
>> >> > I found a very little mistake in your radix-tree.h of linux kernel
>> >> > 4.3(I
>> >> > don't know how is it going in kernel 4.4), here is the code:
>> >> >
>> >> >> 80  #define RADIX_TREE_HEIGHT_SHIFT (RADIX_TREE_MAX_PATH + 1)
>> >> >
>> >> >
>> >> > I think it should be:
>> >> >
>> >> >> 80  #define RADIX_TREE_HEIGHT_SHIFT (log2(RADIX_TREE_MAX_PATH) + 1)
>> >> >
>> >> >
>> >> > where log2 is the binary logarithm.
>> >> >
>> >> > (read the kernel 4.3 online:
>> >> > http://lxr.free-electrons.com/source/include/linux/radix-tree.h)
>> >> >
>> >> > And, rename RADIX_TREE_MAX_PATH to RADIX_TREE_MAX_HEIGHT will be
>> >> > better
>> >> > to
>> >> > understand(just suggestions). I can do a patch if you agree.
>>
>> Yep RADIX_TREE_HEIGHT_SHIFT -> count bits required for keeping height but
>> bigger value is ok.  It's used only once for splitting 32-bit node->path
>> into
>> two numbers offset in parent node in higher bits and subtree height in
>> lower.
>>
>> This is relatively new code by Johannes Weiner,
>> see commit 449dd6984d0e47643c04c807f609dd56d48d5bcc
>>
>> Probably it's easier to swap these parts - bit width of offset in node
>> already here
>> RADIX_TREE_MAP_SHIFT
>>
>> All currenly used combinations are fine 32/64bit CONFIG_BASE_SMALL=y/n
>> and even debug mode RADIX_TREE_MAP_SHIFT=3 are fine.
>>
>> But  64-bit with 2-bit per node will not work: max-path is 32 in this
>> case.
>>
>> >>
>> >> This isn't my code, but I'll check this later.
>> >> It would be better to add linux-kernel@vger.kernel.org into CC.
>> >> Maybe somebody who has more free time will answer you sooner.
>> >
>> >
>>
>> send plain text mail, LKML forbids html.
>
>

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web