linux-kernel - Re: [PATCH RFC] extent mapped page cache

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: <20070724192509.5bc9b3fe@think.oraclecorp.com>
Date:	Tue, 24 Jul 2007 19:25:09 -0400
From:	Chris Mason <chris.mason@...cle.com>
To:	Peter Zijlstra <a.p.zijlstra@...llo.nl>
Cc:	Trond Myklebust <trond.myklebust@....uio.no>,
	Nick Piggin <npiggin@...e.de>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Linux Memory Management List <linux-mm@...ck.org>,
	linux-fsdevel@...r.kernel.org
Subject: Re: [PATCH RFC] extent mapped page cache

On Tue, 24 Jul 2007 23:25:43 +0200
Peter Zijlstra <a.p.zijlstra@...llo.nl> wrote:

> On Tue, 2007-07-24 at 16:13 -0400, Trond Myklebust wrote:
> > On Tue, 2007-07-24 at 16:00 -0400, Chris Mason wrote:
> > > On Tue, 10 Jul 2007 17:03:26 -0400
> > > Chris Mason <chris.mason@...cle.com> wrote:
> > > 
> > > > This patch aims to demonstrate one way to replace buffer heads
> > > > with a few extent trees.  Buffer heads provide a few different
> > > > features:
> > > > 
> > > > 1) Mapping of logical file offset to blocks on disk
> > > > 2) Recording state (dirty, locked etc)
> > > > 3) Providing a mechanism to access sub-page sized blocks.
> > > > 
> > > > This patch covers #1 and #2, I'll start on #3 a little later
> > > > next week.
> > > > 
> > > Well, almost.  I decided to try out an rbtree instead of the
> > > radix, which turned out to be much faster.  Even though
> > > individual operations are slower, the rbtree was able to do many
> > > fewer ops to accomplish the same thing, especially for merging
> > > extents together.  It also uses much less ram.
> > 
> > The problem with an rbtree is that you can't use it together with
> > RCU to do lockless lookups. You can probably modify it to allocate
> > nodes dynamically (like the radix tree does) and thus make it
> > RCU-compatible, but then you risk losing the two main benefits that
> > you list above.

The tree is a critical part of the patch, but it is also the easiest to
rip out and replace.  Basically the code stores a range by inserting
an object at an index corresponding to the end of the range.

Then it does searches by looking forward from the start of the range.
More or less any tree that can search and return the first key >=
than the requested key will work.

So, I'd be happy to rip out the tree and replace with something else.
Going completely lockless will be tricky, its something that will deep
thought once the rest of the interface is sane.

-chris
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/