linux-kernel - Re: [PATCH] xarray: Document erasing entries during iteration

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]

Message-ID: <20190214221652.rwctk7wrocpojtfy@master>
Date:   Thu, 14 Feb 2019 22:16:52 +0000
From:   Wei Yang <richard.weiyang@...il.com>
To:     Matthew Wilcox <willy@...radead.org>
Cc:     Wei Yang <richard.weiyang@...il.com>,
        "Tobin C. Harding" <tobin@...nel.org>,
        linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] xarray: Document erasing entries during iteration

On Wed, Feb 13, 2019 at 08:12:58AM -0800, Matthew Wilcox wrote:
>On Wed, Feb 13, 2019 at 02:47:44PM +0000, Wei Yang wrote:
>> On Tue, Feb 12, 2019 at 05:51:29AM -0800, Matthew Wilcox wrote:
>> >That is _fine_.  As you know I hope to get rid of the radix tree soon ;-)
>> 
>> You mean replace radix tree in whole kernel? That would be a big effort.
>
>Already mostly done.
>
>http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray-conv
>
>The only remaining user of the radix tree in that tree is the IDR.  So
>now I'm converting the IDR users over to the XArray as well.
>

Wow, really a HUGE work.

>
>But that isn't what I was talking about.  At the moment, the radix
>tree and the XArray use the same data structure.  It has good best-case
>performance, but shockingly bad worst-case performance.  So we're looking
>at replacing the data structure, which won't require changing any of the
>users (maybe the page cache ... that has some pretty intimate knowledge
>of exactly how the radix tree works).
>

Two questions from my curiosity:

1. Why you come up the idea to replace radix tree with XArray even they
   use the same data structure?
2. The worst-case performance is related to the data structure itself?

>> BTW, have we compared the performance difference?
>
>It's in the noise.  Sometimes the XArray does a little better because
>the APIs encourage the user to do things in a more efficient way.
>Some of the users are improved just because the original author didn't
>know about a more efficient way of doing what they wanted to do.
>

So sometimes XArray does a little worse?

Why this happens whey XArray and radix tree has the same data structure?

Interesting.

-- 
Wei Yang
Help you, Help me