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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Date:	Fri, 22 Jan 2016 18:14:48 +0300
From:	Konstantin Khlebnikov <koct9i@...il.com>
To:	Nemo Yu <mzer0.yu@...il.com>
Cc:	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: Found a very little mistake in radix-tree.h(linux kernel 4.3)

On Fri, Jan 22, 2016 at 3:11 AM, Nemo Yu <mzer0.yu@...il.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@...il.com>
> wrote:
>>
>> On Thu, Jan 21, 2016 at 12:10 PM, Nemo Yu <mzer0.yu@...il.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@...il.com>
>> > wrote:
>> >>
>> >> On Thu, Jan 21, 2016 at 11:20 AM, Nemo Yu <mzer0.yu@...il.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@...r.kernel.org into CC.
>> >> Maybe somebody who has more free time will answer you sooner.
>> >
>> >
>>
>> send plain text mail, LKML forbids html.
>
>