On Tue, 24 Jul 2007 23:25:43 +0200 Peter Zijlstra <a.p.zijlstra@xxxxxxxxx> 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@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. 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-fsdevel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
