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: <20190213161258.GS12668@bombadil.infradead.org>
Date:   Wed, 13 Feb 2019 08:12:58 -0800
From:   Matthew Wilcox <willy@...radead.org>
To:     Wei Yang <richard.weiyang@...il.com>
Cc:     "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 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.

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).

> 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.