Subsystems (4)
Jan Kara
maintainerHello,
here is the fourth version of the writeback livelock avoidance patches
for data integrity writes. To quickly summarize the idea: we tag dirty pages at the beginning of write_cache_pages with a new TOWRITE tag and then write only tagged pages to avoid parallel writers to livelock us. See changelogs of the patches for more details.
I have tested the patches with fsx and a test program I wrote which
checks that if we crash after fsync, the data is indeed on disk.
If there are no more concerns, can these patches get merged?
Honza
Changes since last version:
- tagging function was changed to stop after given amount of pages to avoid keeping tree_lock and irqs disabled for too long
- changed names and updated comments as Andrew suggested
- measured memory impact and reported it in the changelog
Things suggested but not changed (I want to avoid going in circles ;):
- use tagging also for WB_SYNC_NONE writeback - there's problem with an interaction with wbc->nr_to_write. If we tag all dirty pages, we can spend too much time tagging when we write only a few pages in the end because of nr_to_write. If we tag only say nr_to_write pages, we may not have enough pages tagged because some pages are written out by someone else and so we would have to restart and tagging would become essentially useless. So my option is - switch to tagging for WB_SYNC_NONE writeback if we can get rid of nr_to_write. But that's a story for a different patch set.
- implement function for clearing several tags (TOWRITE, DIRTY) at once
- IMHO not worth it because we would save only conversion of page index to radix tree offsets. The rest would have to be separate anyways. And the interface would be incosistent as well...
- use __lookup_tag to implement radix_tree_range_tag_if_tagged - doesn't quite work because __lookup_tag returns only leaf nodes so we'd have to implement tree traversal anyways to tag also internal nodes.
Jan Kara
maintainerPATCH v4 1/2 radix-tree: Implement function radix_tree_range_tag_if_tagged
Implement function for setting one tag if another tag is set for each item in given range.
--- include/linux/radix-tree.h | 4 ++ lib/radix-tree.c | 92 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 96 insertions(+), 0 deletions(-)
include/linux/radix-tree.h +4 -0
@@ -192,6 +192,10 @@ unsigned int radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, unsigned long first_index, unsigned int max_items, unsigned int tag); +unsigned long radix_tree_range_tag_if_tagged (struct radix_tree_root *root, +unsigned long *first_indexp,unsigned long last_index, +unsigned long nr_to_tag, +unsigned int fromtag,unsigned int totag);int radix_tree_tagged (struct radix_tree_root *root,unsigned int tag);static inline void radix_tree_preload_end (void )
lib/radix-tree.c +92 -0
98 lines not on this page · raw message
Signature · 1 line
1.6.4.2
Andrew Morton
maintainerRe: [PATCH 1/2] radix-tree: Implement function radix_tree_range_tag_if_tagged
Quoted 3 lines · On Wed, 16 Jun 2010 18:33:50 +0200 Jan Kara <[email protected]> wrote:
Implement function for setting one tag if another tag is set for each item in given range.
These two patches look OK to me.
fwiw I have a userspace test harness for radix-tree.c:
http://userweb.kernel.org/~akpm/stuff/rtth.tar.gz. Nick used it for a while and updated it somewhat, but it's probably rather bitrotted and surely needs to be taught how to test the post-2006 additions.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH 1/2] radix-tree: Implement function radix_tree_range_tag_if_tagged
Quoted 7 lines · Andrew Morton
Quoted 3 lines · On Wed, 16 Jun 2010 18:33:50 +0200 Jan Kara <[email protected]> wrote:
Implement function for setting one tag if another tag is set for each item in given range.
Quoted 7 lines
These two patches look OK to me.
fwiw I have a userspace test harness for
radix-tree.c:
http://userweb.kernel.org/~akpm/stuff/rtth.tar.gz. Nick used it for a while and updated it somewhat, but it's probably rather bitrotted and surely needs to be taught how to test the post-2006 additions.
Main thing I did was add RCU support (pretty dumb RCU but it found a couple of bugs), and add some more tests. I'll try to find it...
Jan Kara
maintainerRe: [PATCH 1/2] radix-tree: Implement function radix_tree_range_tag_if_tagged
Quoted 10 lines · Nick Piggin
Quoted 9 lines · Andrew Morton
Quoted 3 lines · On Wed, 16 Jun 2010 18:33:50 +0200 Jan Kara <[email protected]> wrote:
Implement function for setting one tag if another tag is set for each item in given range.
These two patches look OK to me.
Quoted 8 lines
Quoted 5 lines
fwiw I have a userspace test harness for
radix-tree.c:
http://userweb.kernel.org/~akpm/stuff/rtth.tar.gz. Nick used it for a while and updated it somewhat, but it's probably rather bitrotted and surely needs to be taught how to test the post-2006 additions.Main thing I did was add RCU support (pretty dumb RCU but it found a couple of bugs), and add some more tests. I'll try to find it...
Please send them my way if you can find them. I'll gladly run those tests
(and extend them to check also my new function).
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Jan Kara
maintainerRe: [PATCH 1/2] radix-tree: Implement function radix_tree_range_tag_if_tagged
In reply to Nick PigginQuoted 10 lines · Nick Piggin
Quoted 9 lines · Andrew Morton
Quoted 3 lines · On Wed, 16 Jun 2010 18:33:50 +0200 Jan Kara <[email protected]> wrote:
Implement function for setting one tag if another tag is set for each item in given range.
These two patches look OK to me.
Quoted 8 lines
Quoted 5 lines
fwiw I have a userspace test harness for
radix-tree.c:
http://userweb.kernel.org/~akpm/stuff/rtth.tar.gz. Nick used it for a while and updated it somewhat, but it's probably rather bitrotted and surely needs to be taught how to test the post-2006 additions.Main thing I did was add RCU support (pretty dumb RCU but it found a couple of bugs), and add some more tests. I'll try to find it...
Nick, any luck with finding updated tests?
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Jan Kara
maintainerPATCH v4 2/2 mm: Implement writeback livelock avoidance using page tagging
In reply to Jan KaraWe try to avoid livelocks of writeback when some steadily creates dirty pages in a mapping we are writing out. For memory-cleaning writeback, using nr_to_write works reasonably well but we cannot really use it for data integrity writeback. This patch tries to solve the problem.
The idea is simple: Tag all pages that should be written back with a special tag (TOWRITE) in the radix tree. This can be done rather quickly and thus livelocks should not happen in practice. Then we start doing the hard work of locking pages and sending them to disk only for those pages that have TOWRITE tag set.
Note: Adding new radix tree tag grows radix tree node from 288 to 296 bytes for 32-bit archs and from 552 to 560 bytes for 64-bit archs. However, the number of slab/slub items per page remains the same (13 and 7 respectively).
--- include/linux/fs.h | 1 + include/linux/radix-tree.h | 2 +- mm/page-writeback.c | 69 +++++++++++++++++++++++++++++++++----------- 3 files changed, 54 insertions(+), 18 deletions(-)
include/linux/fs.h +1 -0
@@ -685,6 +685,7 @@ struct block_device {*/ #define PAGECACHE_TAG_DIRTY 0#define PAGECACHE_TAG_WRITEBACK 1 +#define PAGECACHE_TAG_TOWRITE 2int mapping_tagged (struct address_space *mapping,int tag);
include/linux/radix-tree.h +1 -1
@@ -55,7 +55,7 @@ static inline int radix_tree_is_indirect_ptr(void *ptr)/*** radix-tree API starts here ***/ -#define RADIX_TREE_MAX_TAGS 2 +#define RADIX_TREE_MAX_TAGS 3/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */ struct radix_tree_root {
mm/page-writeback.c +52 -17
105 lines not on this page · raw message
Signature · 1 line
1.6.4.2
Andrew Morton
maintainerRe: [PATCH 2/2] mm: Implement writeback livelock avoidance using page tagging
Quoted 24 lines · On Wed, 16 Jun 2010 18:33:51 +0200 Jan Kara <[email protected]> wrote:
We try to avoid livelocks of writeback when some steadily creates dirty pages in a mapping we are writing out. For memory-cleaning writeback, using
nr_to_writeworks reasonably well but we cannot really use it for data integrity writeback. This patch tries to solve the problem.The idea is simple: Tag all pages that should be written back with a special tag (TOWRITE) in the radix tree. This can be done rather quickly and thus livelocks should not happen in practice. Then we start doing the hard work of locking pages and sending them to disk only for those pages that have TOWRITE tag set.
Note: Adding new radix tree tag grows radix tree node from 288 to 296 bytes for 32-bit archs and from 552 to 560 bytes for 64-bit archs. However, the number of slab/slub items per page remains the same (13 and 7 respectively).
...
mm/page-writeback.c +4
-0+void tag_pages_for_writeback (struct address_space *mapping, +pgoff_t start,pgoff_t end) +{ +unsigned long tagged;
mm/page-writeback.c void __init page_writeback_init(void) · line 840
Quoted 10 lines
mm/page-writeback.c +10
-0+ +do { +spin_lock_irq (&mapping->tree_lock); + tagged =radix_tree_range_tag_if_tagged (&mapping->page_tree, + &start, end,WRITEBACK_TAG_BATCH , +PAGECACHE_TAG_DIRTY ,PAGECACHE_TAG_TOWRITE ); +spin_unlock_irq (&mapping->tree_lock); +cond_resched (); + }while (tagged >=WRITEBACK_TAG_BATCH ); +}
grumble. (tagged > WRITEBACK_TAG_BATCH) would be a bug, wouldn't it? So the ">=" is hiding a bug.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Jan Kara
maintainerRe: [PATCH 2/2] mm: Implement writeback livelock avoidance using page tagging
Quoted 32 lines · Andrew Morton
Quoted 29 lines · On Wed, 16 Jun 2010 18:33:51 +0200 Jan Kara <[email protected]> wrote:
We try to avoid livelocks of writeback when some steadily creates dirty pages in a mapping we are writing out. For memory-cleaning writeback, using
nr_to_writeworks reasonably well but we cannot really use it for data integrity writeback. This patch tries to solve the problem.The idea is simple: Tag all pages that should be written back with a special tag (TOWRITE) in the radix tree. This can be done rather quickly and thus livelocks should not happen in practice. Then we start doing the hard work of locking pages and sending them to disk only for those pages that have TOWRITE tag set.
Note: Adding new radix tree tag grows radix tree node from 288 to 296 bytes for 32-bit archs and from 552 to 560 bytes for 64-bit archs. However, the number of slab/slub items per page remains the same (13 and 7 respectively).
...
mm/page-writeback.c +9
-0+void tag_pages_for_writeback(struct address_space *mapping, + pgoff_t start, pgoff_t end) +{ + unsigned long tagged; + + do { + spin_lock_irq(&mapping->tree_lock); + tagged = radix_tree_range_tag_if_tagged(&mapping->page_tree, + &start, end, WRITEBACK_TAG_BATCH,
Quoted 8 lines
mm/page-writeback.c void __init page_writeback_init(void) · line 840
Quoted 5 lines
mm/page-writeback.c +5
-0+ PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE); +spin_unlock_irq (&mapping->tree_lock); +cond_resched (); + }while (tagged >=WRITEBACK_TAG_BATCH ); +}grumble. (tagged >
WRITEBACK_TAG_BATCH) would be a bug, wouldn't it? So the ">=" is hiding a bug.
Good point. I'll add WARN_ON_ONCE when tagged is > WRITEBACK_TAG_BATCH.
That will make the bug vissible while still continuing the writeback (because it's a situation in which we can still happily continue). Should I send you a new version of the patch or will you just fold that one line in?
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Re: your mail
In reply to Jan KaraQuoted 10 lines · Jan Kara
Hello,
here is the fourth version of the writeback livelock avoidance patches
for data integrity writes. To quickly summarize the idea: we tag dirty pages at the beginning ofwrite_cache_pageswith a new TOWRITE tag and then write only tagged pages to avoid parallel writers to livelock us. See changelogs of the patches for more details.
I have tested the patches with fsx and a test program I wrote which
checks that if we crash after fsync, the data is indeed on disk.
If there are no more concerns, can these patches get merged?
Has it been run through xfstests? I'd suggest doing that at least with XFS as there are several significant sync sanity tests for XFS in the suite...
Cheers,
Dave.
Signature · 8 lines
Dave Chinner [email protected] -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Jan Kara
maintainerRe: [PATCH 0/2 v4] Writeback livelock avoidance for data integrity writes
Quoted 12 lines · Dave Chinner
Quoted 10 lines · Jan Kara
Hello,
here is the fourth version of the writeback livelock avoidance patches
for data integrity writes. To quickly summarize the idea: we tag dirty pages at the beginning ofwrite_cache_pageswith a new TOWRITE tag and then write only tagged pages to avoid parallel writers to livelock us. See changelogs of the patches for more details.
I have tested the patches with fsx and a test program I wrote which
checks that if we crash after fsync, the data is indeed on disk.
If there are no more concerns, can these patches get merged?
Quoted 3 lines
Has it been run through xfstests? I'd suggest doing that at least with XFS as there are several significant sync sanity tests for XFS in the suite...
I've run it through XFSQA with ext3 & ext4 before submitting. I'm running
a test with xfs now.
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Re: [PATCH 0/2 v4] Writeback livelock avoidance for data integrity writes
Quoted 13 lines · Jan Kara
Quoted 12 lines · Dave Chinner
Quoted 10 lines · Jan Kara
Hello,
here is the fourth version of the writeback livelock avoidance patches
for data integrity writes. To quickly summarize the idea: we tag dirty pages at the beginning ofwrite_cache_pageswith a new TOWRITE tag and then write only tagged pages to avoid parallel writers to livelock us. See changelogs of the patches for more details.
I have tested the patches with fsx and a test program I wrote which
checks that if we crash after fsync, the data is indeed on disk.
If there are no more concerns, can these patches get merged?
Quoted 5 lines
Quoted 3 lines
Has it been run through xfstests? I'd suggest doing that at least with XFS as there are several significant sync sanity tests for XFS in the suite...
I've run it through XFSQA with ext3 & ext4 before submitting. I'm running
a test with xfs now.
Cool. if there are no problems then I'm happy with this ;)
Cheers,
Dave.
Signature · 8 lines
Dave Chinner [email protected] -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [PATCH 0/2 v4] Writeback livelock avoidance for data integrity writes
Quoted 14 lines · Dave Chinner
Quoted 13 lines · Jan Kara
Quoted 12 lines · Dave Chinner
Quoted 10 lines · Jan Kara
Hello,
here is the fourth version of the writeback livelock avoidance patches
for data integrity writes. To quickly summarize the idea: we tag dirty pages at the beginning ofwrite_cache_pageswith a new TOWRITE tag and then write only tagged pages to avoid parallel writers to livelock us. See changelogs of the patches for more details.
I have tested the patches with fsx and a test program I wrote which
checks that if we crash after fsync, the data is indeed on disk.
If there are no more concerns, can these patches get merged?
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
Has it been run through xfstests? I'd suggest doing that at least with XFS as there are several significant sync sanity tests for XFS in the suite...
I've run it through XFSQA with ext3 & ext4 before submitting. I'm running
a test with xfs now.Cool. if there are no problems then I'm happy with this ;)
Agreed.
Jan Kara
maintainerv4 cover Writeback livelock avoidance for data integrity writes
In reply to Jan Kara Sorry for replying to my email but I forgot to set a subject while doing
git send-email. So at least set it now.
Honza
Quoted 40 lines · Jan Kara
Hello,
here is the fourth version of the writeback livelock avoidance patches
for data integrity writes. To quickly summarize the idea: we tag dirty pages at the beginning ofwrite_cache_pageswith a new TOWRITE tag and then write only tagged pages to avoid parallel writers to livelock us. See changelogs of the patches for more details.
I have tested the patches with fsx and a test program I wrote which
checks that if we crash after fsync, the data is indeed on disk.
If there are no more concerns, can these patches get merged?Honza
Changes since last version:
- tagging function was changed to stop after given amount of pages to avoid keepingtree_lockand irqs disabled for too long
- changed names and updated comments as Andrew suggested
- measured memory impact and reported it in the changelogThings suggested but not changed (I want to avoid going in circles ;):
- use tagging also forWB_SYNC_NONEwriteback - there's problem with an interaction withwbc->nr_to_write. If we tag all dirty pages, we can spend too much time tagging when we write only a few pages in the end because ofnr_to_write. If we tag only saynr_to_writepages, we may not have enough pages tagged because some pages are written out by someone else and so we would have to restart and tagging would become essentially useless. So my option is - switch to tagging forWB_SYNC_NONEwriteback if we can get rid ofnr_to_write. But that's a story for a different patch set.
- implement function for clearing several tags (TOWRITE, DIRTY) at once
- IMHO not worth it because we would save only conversion of page index to radix tree offsets. The rest would have to be separate anyways. And the interface would be incosistent as well...
- use__lookup_tagto implementradix_tree_range_tag_if_tagged- doesn't quite work because__lookup_tagreturns only leaf nodes so we'd have to implement tree traversal anyways to tag also internal nodes.
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Re: your mail
In reply to Jan KaraQuoted 6 lines
- use tagging also for
WB_SYNC_NONEwriteback - there's problem with an interaction withwbc->nr_to_write. If we tag all dirty pages, we can spend too much time tagging when we write only a few pages in the end because ofnr_to_write. If we tag only saynr_to_writepages, we may not have enough pages tagged because some pages are written out by someone else and so we would have to restart and tagging would become
This could be addressed by ignoring nr_to_write for the WB_SYNC_NONE writeback triggered by sync(). write_cache_pages() already ignored nr_to_write for WB_SYNC_ALL.
Quoted 3 lines
essentially useless. So my option is - switch to tagging for
WB_SYNC_NONEwriteback if we can get rid ofnr_to_write. But that's a story for a different patch set.
Besides introducing overheads, it will be a policy change in which the system loses control to somehow "throttle" writeback of huge files.
So it may be safer to enlarge nr_to_write instead of canceling it totally.
Thanks,
Fengguang
Jan Kara
maintainerRe: your mail
Quoted 10 lines · Wu Fengguang
Quoted 6 lines
- use tagging also for
WB_SYNC_NONEwriteback - there's problem with an interaction withwbc->nr_to_write. If we tag all dirty pages, we can spend too much time tagging when we write only a few pages in the end because ofnr_to_write. If we tag only saynr_to_writepages, we may not have enough pages tagged because some pages are written out by someone else and so we would have to restart and tagging would becomeThis could be addressed by ignoring
nr_to_writefor theWB_SYNC_NONEwriteback triggered bysync().write_cache_pages()already ignorednr_to_writeforWB_SYNC_ALL.
We could do that but frankly, I'm not very fond of adding more special
cases to writeback code than strictly necessary...
Quoted 6 lines
Quoted 3 lines
essentially useless. So my option is - switch to tagging for
WB_SYNC_NONEwriteback if we can get rid ofnr_to_write. But that's a story for a different patch set.Besides introducing overheads, it will be a policy change in which the system loses control to somehow "throttle" writeback of huge files.
Yes, but if we guarantee we cannot livelock on a single file, do we care?
Memory management does not care because it's getting rid of dirty pages which is what it wants. User might care but actually writing out files in the order they were dirtied (i.e., the order user written them) is quite natural so it's not a "surprising" behavior. And I don't think we can assume that data in those small files are more valuable than data in the large file and thus should be written earlier...
With the overhead you are right that tagging is more expensive than
checking nr_to_write limit...
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Re: your mail
Quoted 8 lines · Jan Kara
Quoted 7 lines · Wu Fengguang
Quoted 6 lines
- use tagging also for
WB_SYNC_NONEwriteback - there's problem with an interaction withwbc->nr_to_write. If we tag all dirty pages, we can spend too much time tagging when we write only a few pages in the end because ofnr_to_write. If we tag only saynr_to_writepages, we may not have enough pages tagged because some pages are written out by someone else and so we would have to restart and tagging would become
Quoted 5 lines
Quoted 3 lines
This could be addressed by ignoring
nr_to_writefor theWB_SYNC_NONEwriteback triggered bysync().write_cache_pages()already ignorednr_to_writeforWB_SYNC_ALL.We could do that but frankly, I'm not very fond of adding more special
cases to writeback code than strictly necessary...
So do me. However for this case we only need to broaden the special case test:
if (nr_to_write > 0) {
nr_to_write--;
if (nr_to_write == 0 &&- wbc->sync_mode == WB_SYNC_NONE) {
+ !wbc->for_sync) {
Quoted 6 lines
Quoted 6 lines
Quoted 3 lines
essentially useless. So my option is - switch to tagging for
WB_SYNC_NONEwriteback if we can get rid ofnr_to_write. But that's a story for a different patch set.Besides introducing overheads, it will be a policy change in which the system loses control to somehow "throttle" writeback of huge files.
Quoted 7 lines
Yes, but if we guarantee we cannot livelock on a single file, do we care?
Memory management does not care because it's getting rid of dirty pages which is what it wants. User might care but actually writing out files in the order they were dirtied (i.e., the order user written them) is quite natural so it's not a "surprising" behavior. And I don't think we can assume that data in those small files are more valuable than data in the large file and thus should be written earlier...
It could be a surprising behavior when, there is a 4GB dirty file and 100 small dirty files. The user may expect the 100 small dirty files be synced to disk after 30s. However without nr_to_write, they could be delayed by the 4GB file for 40 more seconds. Now if something goes wrong in between and the small dirty files happen to include some .c/.tex/.txt/... files.
Small files are more likely your precious documents that are typed in word-by-word and perhaps the most important data you want to protect. Naturally you'll want them enjoy more priority than large files.
Quoted 2 lines
With the overhead you are right that tagging is more expensive than
checkingnr_to_writelimit...
Thanks,
Fengguang
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>