From mboxrd@z Thu Jan 1 00:00:00 1970 From: Peter Zijlstra Subject: Re: [PATCH RFC] extent mapped page cache Date: Tue, 24 Jul 2007 23:25:43 +0200 Message-ID: <1185312343.5535.5.camel@lappy> References: <20070710210326.GA29963@think.oraclecorp.com> <20070724160032.7a7097db@think.oraclecorp.com> <1185307985.6586.50.camel@localhost> Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit Cc: Chris Mason , Nick Piggin , Linux Kernel Mailing List , Linux Memory Management List , linux-fsdevel@vger.kernel.org To: Trond Myklebust Return-path: Received: from pentafluge.infradead.org ([213.146.154.40]:56268 "EHLO pentafluge.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752540AbXGXV0D (ORCPT ); Tue, 24 Jul 2007 17:26:03 -0400 In-Reply-To: <1185307985.6586.50.camel@localhost> Sender: linux-fsdevel-owner@vger.kernel.org List-Id: linux-fsdevel.vger.kernel.org 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 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. I thought on this, and I came to the conclusion that the tree rotations used to balance binary trees are incompatible with RCU. The rotation can hide one branch. Hence I started writing a B+tree that is RCU compatible much like the Radix tree. Current code here: http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch Still needs some work, but is usable.