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 for Android: free password hash cracker in your pocket

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

Message-ID: <CALYGNiMEoc0-YSVNsb_HBxhtArfGL8UjUegv0m0EVsqe+k_enw@mail.gmail.com>
Date:	Thu, 21 Jan 2016 22:15:34 +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 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.