Skip to contentSkip to conversation

PATCH Superseded Jan Kara 5 participants 17 messages Jun 16, 2010 – Jun 23, 2010

Subsystems (4)

v4 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Jan Kara

author maintainer
#0 lore raw

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 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.

author maintainer
#1 lore raw

PATCH 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
index 55ca73c..a4b00e9 100644
@@ -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
maintainer
#2 lore raw

Re: [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>

#3 lore raw

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...

author maintainer
#4 lore raw

Re: [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
author maintainer
#5 lore raw

Re: [PATCH 1/2] radix-tree: Implement function radix_tree_range_tag_if_tagged

In reply to Nick Piggin
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...

Nick, any luck with finding updated tests?

Honza

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR
author maintainer
#6 lore raw

PATCH v4 2/2 mm: Implement writeback livelock avoidance using page tagging

In reply to Jan Kara

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_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
index 471e1ff..664674e 100644
@@ -685,6 +685,7 @@ struct block_device {
  */
 #define PAGECACHE_TAG_DIRTY	0
 #define PAGECACHE_TAG_WRITEBACK	1
+#define PAGECACHE_TAG_TOWRITE	2
 
 int mapping_tagged(struct address_space *mapping, int tag);
 
include/linux/radix-tree.h +1 -1
index a4b00e9..634b8e6 100644
@@ -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
maintainer
#7 lore raw

Re: [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_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).

...

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>

author maintainer
#8 lore raw

Re: [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_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).

...

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
#9 lore raw

Re: your mail

In reply to Jan Kara
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 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?

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>
author maintainer
#10 lore raw

Re: [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 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?

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
#11 lore raw

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 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?

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>
#12 lore raw

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 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?

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.

author maintainer
#13 lore raw

v4 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 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.
--
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
#14 lore raw

Re: your mail

In reply to Jan Kara
Quoted 6 lines

- 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

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_NONE writeback if we can get rid of nr_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

author maintainer
#15 lore raw

Re: your mail

Quoted 10 lines · Wu Fengguang
Quoted 6 lines

- 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

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.

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_NONE writeback if we can get rid of nr_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
#16 lore raw

Re: your mail

Quoted 8 lines · Jan Kara
Quoted 7 lines · Wu Fengguang
Quoted 6 lines

- 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

Quoted 5 lines
Quoted 3 lines

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.

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_NONE writeback if we can get rid of nr_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
checking nr_to_write limit...

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>