extent mapped page cache

This patch aims to demonstrate one way to replace buffer heads with a few extent trees...

Quoted 2 lines · Chris Mason

This patch aims to demonstrate one way to replace buffer heads with a few extent trees...

Hi Chris,

Quite terse commentary on algorithms and data structures, but I suppose that is not a problem because Jon has a whole week to reverse engineer it for us.

What did you have in mind for subpages?

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.

Quoted 7 lines · On Tue, 10 Jul 2007 17:03:26 -0400 Chris Mason <[email protected]> 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.

Quoted 3 lines

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.

Quoted 10 lines · Chris Mason

Quoted 7 lines · On Tue, 10 Jul 2007 17:03:26 -0400 Chris Mason <[email protected]> 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.

Quoted 8 lines

Quoted 3 lines

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.

Quoted 21 lines · Trond Myklebust

Quoted 19 lines · Chris Mason

Quoted 11 lines · On Tue, 10 Jul 2007 17:03:26 -0400 Chris Mason <[email protected]> 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.

Quoted 5 lines

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.

On Tue, 24 Jul 2007 23:25:43 +0200
Peter Zijlstra <[email protected]> wrote:

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.

Quoted 8 lines · Chris Mason

On Tue, 24 Jul 2007 23:25:43 +0200
Peter Zijlstra <[email protected]> wrote:

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.

Quoted 7 lines

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.

Just having the other tree and managing it is what makes me a little less positive of this approach, especially using it to store pagecache state when we already have the pagecache tree.

Having another tree to store block state I think is a good idea as I said in the fsblock thread with Dave, but I haven't clicked as to why it is a big advantage to use it to manage pagecache state. (and I can see some possible disadvantages in locking and tree manipulation overhead).

Quoted 5 lines · On Wed, 25 Jul 2007 04:32:17 +0200 Nick Piggin <[email protected]> wrote:

Having another tree to store block state I think is a good idea as I said in the fsblock thread with Dave, but I haven't clicked as to why it is a big advantage to use it to manage pagecache state. (and I can see some possible disadvantages in locking and tree manipulation overhead).

Yes, there are definitely costs with the state tree, it will take some careful benchmarking to convince me it is a feasible solution. But, storing all the state in the pages themselves is impossible unless the block size equals the page size. So, we end up with something like fsblock/buffer heads or the state tree.

One advantage to the state tree is that it separates the state from the memory being described, allowing a simple kmap style interface that covers subpages, highmem and superpages.

It also more naturally matches the way we want to do IO, making for easy clustering.

O_DIRECT becomes a special case of readpages and writepages....the memory used for IO just comes from userland instead of the page cache.

The ability to put in additional tracking info like the process that first dirtied a range is also significant. So, I think it is worth trying.

Quoted 4 lines

One advantage to the state tree is that it separates the state from the memory being described, allowing a simple kmap style interface that covers subpages, highmem and superpages.

I suppose so, although we should have added those interfaces long ago ;) The variants in fsblock are pretty good, and you could always do an arbitrary extent (rather than block) based API using the pagecache tree if it would be helpful.

Quoted 4 lines

It also more naturally matches the way we want to do IO, making for easy clustering.

Well the pagecache tree is used to reasonable effect for that now. OK the code isn't beautiful ;). Granted, this might be an area where the seperate state tree ends up being better. We'll see.

Quoted 4 lines

O_DIRECT becomes a special case of readpages and writepages....the memory used for IO just comes from userland instead of the page cache.

Could be, although you'll probably also need to teach the mm about the state tree and/or still manipulate the pagecache tree to prevent concurrency?

But isn't the main aim of O_DIRECT to do as little locking and synchronisation with the pagecache as possible? I thought this is why your race fixing patches got put on the back burner (although they did look fairly nice from a correctness POV).

Well I'm kind of handwaving when it comes to O_DIRECT ;) It does look like this might be another advantage of the state tree (although you aren't allowed to slow down buffered IO to achieve the locking ;)).

Quoted 5 lines

The ability to put in additional tracking info like the process that first dirtied a range is also significant. So, I think it is worth trying.

Definitely, and I'm glad you are. You haven't converted me yet, but I look forward to finding the best ideas from our two approaches when the patches are further along (ext2 port of fsblock coming along, so we'll be able to have races soon :P).

Quoted 9 lines · On Thu, 26 Jul 2007 03:37:28 +0200 Nick Piggin <[email protected]> wrote:

Quoted 4 lines

One advantage to the state tree is that it separates the state from the memory being described, allowing a simple kmap style interface that covers subpages, highmem and superpages.

I suppose so, although we should have added those interfaces long ago ;) The variants in fsblock are pretty good, and you could always do an arbitrary extent (rather than block) based API using the pagecache tree if it would be helpful.

Yes, you could use fsblock for the state bits and make a separate API to map the actual pages.

Quoted 9 lines

Quoted 4 lines

It also more naturally matches the way we want to do IO, making for easy clustering.

Well the pagecache tree is used to reasonable effect for that now. OK the code isn't beautiful ;). Granted, this might be an area where the seperate state tree ends up being better. We'll see.

One thing it gains us is finding the start of the cluster. Even if called by kswapd, the state tree allows writepage to find the start of the cluster and send down a big bio (provided I implement trylock to avoid various deadlocks).

Quoted 7 lines

Quoted 3 lines

O_DIRECT becomes a special case of readpages and writepages....the memory used for IO just comes from userland instead of the page cache.

Could be, although you'll probably also need to teach the mm about the state tree and/or still manipulate the pagecache tree to prevent concurrency?

Well, it isn't coded yet, but I should be able to do it from the FS specific ops.

Quoted 4 lines

But isn't the main aim of O_DIRECT to do as little locking and synchronisation with the pagecache as possible? I thought this is why your race fixing patches got put on the back burner (although they did look fairly nice from a correctness POV).

I put the placeholder patches on hold because handling a corner case where userland did O_DIRECT from a mmap'd region of the same file (Linus pointed it out to me). Basically my patches had to work in 64k chunks to avoid a deadlock in get_user_pages. With the state tree, I can allow the page to be faulted in but still properly deal with it.

Quoted 3 lines

Well I'm kind of handwaving when it comes to O_DIRECT ;) It does look like this might be another advantage of the state tree (although you aren't allowed to slow down buffered IO to achieve the locking ;)).

;) The O_DIRECT benefit is a fringe thing. I've long wanted to help clean up that code, but the real point of the patch is to make general usage faster and less complex. If I can't get there, the O_DIRECT stuff doesn't matter.

Quoted 8 lines

Quoted 3 lines

The ability to put in additional tracking info like the process that first dirtied a range is also significant. So, I think it is worth trying.

Definitely, and I'm glad you are. You haven't converted me yet, but I look forward to finding the best ideas from our two approaches when the patches are further along (ext2 port of fsblock coming along, so we'll be able to have races soon :P).

I'm sure we can find some river in Cambridge, winner gets to throw Axboe in.

Quoted 26 lines · Chris Mason

Quoted 9 lines · On Thu, 26 Jul 2007 03:37:28 +0200 Nick Piggin <[email protected]> wrote:

Quoted 4 lines

One advantage to the state tree is that it separates the state from the memory being described, allowing a simple kmap style interface that covers subpages, highmem and superpages.

I suppose so, although we should have added those interfaces long ago ;) The variants in fsblock are pretty good, and you could always do an arbitrary extent (rather than block) based API using the pagecache tree if it would be helpful.

Yes, you could use fsblock for the state bits and make a separate API to map the actual pages.

Quoted 9 lines

Quoted 4 lines

It also more naturally matches the way we want to do IO, making for easy clustering.

Well the pagecache tree is used to reasonable effect for that now. OK the code isn't beautiful ;). Granted, this might be an area where the seperate state tree ends up being better. We'll see.

Quoted 4 lines

One thing it gains us is finding the start of the cluster. Even if called by kswapd, the state tree allows writepage to find the start of the cluster and send down a big bio (provided I implement trylock to avoid various deadlocks).

That's very true, we could potentially also do that with the block extent tree that I want to try with fsblock.

I'm looking at "cleaning up" some of these aops APIs so hopefully most of the deadlock problems go away. Should be useful to both our efforts. Will post patches hopefully when I get time to finish the draft this weekend.

Quoted 10 lines

Quoted 7 lines

Quoted 3 lines

O_DIRECT becomes a special case of readpages and writepages....the memory used for IO just comes from userland instead of the page cache.

Could be, although you'll probably also need to teach the mm about the state tree and/or still manipulate the pagecache tree to prevent concurrency?

Well, it isn't coded yet, but I should be able to do it from the FS specific ops.

Probably, if you invalidate all the pagecache in the range beforehand you should be able to do it (and I guess you want to do the invalidate anyway). Although, below deadlock issues might still bite somehwere...

Quoted 10 lines

Quoted 4 lines

But isn't the main aim of O_DIRECT to do as little locking and synchronisation with the pagecache as possible? I thought this is why your race fixing patches got put on the back burner (although they did look fairly nice from a correctness POV).

I put the placeholder patches on hold because handling a corner case where userland did O_DIRECT from a mmap'd region of the same file (Linus pointed it out to me). Basically my patches had to work in 64k chunks to avoid a deadlock in get_user_pages. With the state tree, I can allow the page to be faulted in but still properly deal with it.

Oh right, I didn't think of that one. Would you still have similar issues with the external state tree? I mean, the filesystem doesn't really know why the fault is taken. O_DIRECT read from a file into mmapped memory of the same block in the file is almost hopeless I think.

Quoted 8 lines

Quoted 3 lines

Well I'm kind of handwaving when it comes to O_DIRECT ;) It does look like this might be another advantage of the state tree (although you aren't allowed to slow down buffered IO to achieve the locking ;)).

;) The O_DIRECT benefit is a fringe thing. I've long wanted to help clean up that code, but the real point of the patch is to make general usage faster and less complex. If I can't get there, the O_DIRECT stuff doesn't matter.

Sure, although unifying code is always a plus so I like that you've got that in mind.

Quoted 9 lines

Quoted 8 lines

Quoted 3 lines

The ability to put in additional tracking info like the process that first dirtied a range is also significant. So, I think it is worth trying.

Definitely, and I'm glad you are. You haven't converted me yet, but I look forward to finding the best ideas from our two approaches when the patches are further along (ext2 port of fsblock coming along, so we'll be able to have races soon :P).

Quoted 2 lines

I'm sure we can find some river in Cambridge, winner gets to throw Axboe in.

Very noble of you to donate your colleage to such a worthy cause.

Quoted 4 lines

One thing it gains us is finding the start of the cluster. Even if called by kswapd, the state tree allows writepage to find the start of the cluster and send down a big bio (provided I implement trylock to avoid various deadlocks).

That's very true, we could potentially also do that with the block extent tree that I want to try with fsblock.

I'm looking at "cleaning up" some of these aops APIs so hopefully most of the deadlock problems go away. Should be useful to both our efforts. Will post patches hopefully when I get time to finish the draft this weekend.

Quoted 10 lines

Quoted 9 lines

Quoted 5 lines

O_DIRECT becomes a special case of readpages and writepages....the memory used for IO just comes from userland instead of the page cache.

Could be, although you'll probably also need to teach the mm about the state tree and/or still manipulate the pagecache tree to prevent concurrency?

Quoted 2 lines

Well, it isn't coded yet, but I should be able to do it from the FS specific ops.

Probably, if you invalidate all the pagecache in the range beforehand you should be able to do it (and I guess you want to do the invalidate anyway). Although, below deadlock issues might still bite somehwere...

Quoted 7 lines

Quoted 6 lines

But isn't the main aim of O_DIRECT to do as little locking and synchronisation with the pagecache as possible? I thought this is why your race fixing patches got put on the back burner (although they did look fairly nice from a correctness POV).

Quoted 6 lines

I put the placeholder patches on hold because handling a corner case where userland did O_DIRECT from a mmap'd region of the same file (Linus pointed it out to me). Basically my patches had to work in 64k chunks to avoid a deadlock in get_user_pages. With the state tree, I can allow the page to be faulted in but still properly deal with it.

Oh right, I didn't think of that one. Would you still have similar issues with the external state tree? I mean, the filesystem doesn't really know why the fault is taken. O_DIRECT read from a file into mmapped memory of the same block in the file is almost hopeless I think.

Quoted 9 lines

Quoted 8 lines

Quoted 3 lines

The ability to put in additional tracking info like the process that first dirtied a range is also significant. So, I think it is worth trying.

Definitely, and I'm glad you are. You haven't converted me yet, but I look forward to finding the best ideas from our two approaches when the patches are further along (ext2 port of fsblock coming along, so we'll be able to have races soon :P).

Quoted 2 lines

I'm sure we can find some river in Cambridge, winner gets to throw Axboe in.

Very noble of you to donate your colleage to such a worthy cause.

On Thu, 26 Jul 2007 04:36:39 +0200
Nick Piggin <[email protected]> wrote:

[ are state trees a good idea? ]

Quoted 5 lines

Quoted 4 lines

One thing it gains us is finding the start of the cluster. Even if called by kswapd, the state tree allows writepage to find the start of the cluster and send down a big bio (provided I implement trylock to avoid various deadlocks).

Quoted 2 lines

That's very true, we could potentially also do that with the block extent tree that I want to try with fsblock.

If fsblock records and extent of 200MB, and writepage is called on a page in the middle of the extent, how do you walk the radix backwards to find the first dirty & up to date page in the range?

Quoted 7 lines

Quoted 6 lines

I put the placeholder patches on hold because handling a corner case where userland did O_DIRECT from a mmap'd region of the same file (Linus pointed it out to me). Basically my patches had to work in 64k chunks to avoid a deadlock in get_user_pages. With the state tree, I can allow the page to be faulted in but still properly deal with it.

Quoted 5 lines

Oh right, I didn't think of that one. Would you still have similar issues with the external state tree? I mean, the filesystem doesn't really know why the fault is taken. O_DIRECT read from a file into mmapped memory of the same block in the file is almost hopeless I think.

Racing is fine as long as we don't deadlock or expose garbage from disk.

Quoted 4 lines

Quoted 2 lines

I'm sure we can find some river in Cambridge, winner gets to throw Axboe in.

Very noble of you to donate your colleage to such a worthy cause.

Jens is always interested in helping solve such debates. It's a fantastic service he provides to the community.