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  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:12:21 +0300
From:   Konstantin Khlebnikov <koct9i@...il.com>
To:     Ross Zwisler <ross.zwisler@...ux.intel.com>
Cc:     Dan Williams <dan.j.williams@...el.com>,
        Matthew Wilcox <mawilcox@...rosoft.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 1:53 AM, Ross Zwisler
<ross.zwisler@...ux.intel.com> wrote:
> On Tue, Aug 30, 2016 at 03:21:24PM -0700, Dan Williams wrote:
>> On Tue, Aug 30, 2016 at 3:03 PM, Ross Zwisler
>> <ross.zwisler@...ux.intel.com> wrote:
>> > On Tue, Aug 30, 2016 at 02:56:17PM -0700, Dan Williams wrote:
>> >> On Mon, Aug 29, 2016 at 11:52 AM, Matthew Wilcox <mawilcox@...rosoft.com> wrote:
>> >> > It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually.  No mapping lock, just like the page cache.
>> >> >
>> >> > Even if we can work around it, why do we want to?  What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range?  There are no in-kernel users right now; is there a performance reason to change?  We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it.
>> >>
>> >> I'd use a fill range api for the radix backing get_dev_pagemap() and
>> >> potentially another use in device-dax.  It centralizes the common
>> >> routine of breaking down a range into its constituent power-of-2
>> >> ranges.
>> >
>> > Does your usage not work with the current sibling & canonical entry model?
>>
>> It does, but I find myself writing code to walk a range and determine
>> the order of each entry as I insert them.  I can see other users
>> needing the same sort of insert helper and the aspect I like of
>> Konstantin's proposed change is that the functionality is part of the
>> core implementation rather than left to be duplicated in each user.
>
> Perhaps the answer is to have them both?  Matthew's multi-order radix
> functionality with siblings for those of us that really *want* a single
> canonical entry that we can look up, use tags on, etc.   And Konstantin's
> method where we insert a bunch of duplicate entries that don't have sibling
> pointers?  Is there a reason why they can't coexist?

I'm not all against "sibling" entries, I just don't want to mess them
into iterator and
common lookup routines. This is redundant.

Actually it's very easy to integrate similar "sibling" entries into my
filling function.

That will be yet another flag which tells to assign given entry only
to the first slot and
fill following tail with reference to that first slot. Just a pointer
with both lower bits set to
distinguish it from exceptional and internal pointers.

I think it's better to call them "indirect" entries because this will
work for arbitrary
ranges too where they are not siblings at all and may be located in
several nodes.

Powered by blists - more mailing lists