linux-kernel - Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill

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>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Thu, 1 Sep 2016 09:16:44 +0300
From:   Konstantin Khlebnikov <koct9i@...il.com>
To:     Dan Williams <dan.j.williams@...el.com>
Cc:     Matthew Wilcox <mawilcox@...rosoft.com>,
        Ross Zwisler <ross.zwisler@...ux.intel.com>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range

On Wed, Aug 31, 2016 at 7:36 PM, Dan Williams <dan.j.williams@...el.com> wrote:
> On Wed, Aug 31, 2016 at 7:57 AM, Matthew Wilcox <mawilcox@...rosoft.com> wrote:
>> I'm not at all against the idea of having a tree which supports ranges, except that we already have one; the interval tree.  Did you investigate using the interval tree for your use case?
>
> I am continuing to investigate, but that is orthogonal to whether
> Konstantin's changes are an improvement for the radix implementation.
> Hmm, would we have ended up with two data-structures if a range-based
> radix was available?

Interval tree is a augmented rb-tree. AFAIK it doesn't support RCU lookup
without special dances with sequential counters - some branches disappears
from RCU readers during rebalance.

>
> The benefits I see is that it simplifies insertion as it no longer
> needs to explicitly manage the order of the entries, and, iiuc, let's
> the user skip the sibling-to-head conversion when it is not needed
> which simplifies lookups.