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@xxxxxxxxxx> 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. - To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
