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

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

Message-ID: <DM2PR21MB0089A76C6ACE9299CFD37938CBE10@DM2PR21MB0089.namprd21.prod.outlook.com>
Date:   Mon, 29 Aug 2016 18:52:54 +0000
From:   Matthew Wilcox <mawilcox@...rosoft.com>
To:     Konstantin Khlebnikov <koct9i@...il.com>
CC:     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

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.

-----Original Message-----
From: Konstantin Khlebnikov [mailto:koct9i@...il.com] 
Sent: Monday, August 29, 2016 2:16 PM
To: Matthew Wilcox <mawilcox@...rosoft.com>
Cc: Ross Zwisler <ross.zwisler@...ux.intel.com>; linux-kernel@...r.kernel.org
Subject: Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range

On Mon, Aug 29, 2016 at 9:08 PM, Matthew Wilcox <mawilcox@...rosoft.com> wrote:
> The DAX lock bit is analogous to the PageLock.  You can't serialise on the mapping lock; the contention will be too high.

I mean DAX lock bit is protected by mapping lock thus we can set/clear it for all entries if needed.

>
> And the point of having the radix tree support the same entry for many indices is that we don't have to go and probe the radix tree multiple times looking for the first or last entry.  We just look up the index, then use the entry we got back.

Right, but lookup function can also return pointer for node -- fininding first or last entries is trivial here.
We could simply scan back/forward or if huge DAX order is known then just align slot pointer to first or last entry.

>
> -----Original Message-----
> From: Konstantin Khlebnikov [mailto:koct9i@...il.com]
> Sent: Monday, August 29, 2016 12:14 PM
> To: Matthew Wilcox <mawilcox@...rosoft.com>
> Cc: Ross Zwisler <ross.zwisler@...ux.intel.com>; 
> linux-kernel@...r.kernel.org
> Subject: Re: [PATCH RFC 1/4] lib/radix: add universal 
> radix_tree_fill_range
>
> On Mon, Aug 29, 2016 at 6:21 PM, Matthew Wilcox <mawilcox@...rosoft.com> wrote:
>> Thanks, Ross.
>>
>> Konstantin, I think there are problems with the concept behind this series.  You have multiple entries in the tree with the same value.  That works out fine when the entry is a pointer (eg to a struct page), but not so well when it's an exceptional entry (eg a swap cache entry or a DAX radix tree entry).  If you look at the recent DAX work, you'll see there's a lock bit, and having multiple lock bits is a recipe for disaster.
>>
>
> I see no problem here. They could use lock bit at first or last entry.
> Anyway all changes should be protecred by lock at mapping.
>
>