Livelock avoidance for data integrity writeback
Subsystems (4)
Jan Kara
maintainerv3 cover Livelock avoidance for data integrity writeback
Hi,
I've revived my patches to implement livelock avoidance for data integrity
writes. Due to some concerns whether tagging of pages before writeout cannot be too costly to use for WB_SYNC_NONE mode (where we stop after nr_to_write pages) I've changed the patch to use page tagging only in WB_SYNC_ALL mode where we are sure that we write out all the tagged pages. Later, we can think about using tagging for livelock avoidance for WB_SYNC_NONE mode as well...
As always comments are welcome.
Honza
PS: I'm sorry for sending this twice. I've screwed up the list address in the first posting.
Jan Kara
maintainerPATCH v3 1/2 radix-tree: Implement function radix_tree_gang_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 | 3 ++ lib/radix-tree.c | 82 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 85 insertions(+), 0 deletions(-)
include/linux/radix-tree.h +3 -0
@@ -192,6 +192,9 @@ 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_gang_tag_if_tagged (struct radix_tree_root *root, +unsigned long first_index,unsigned long last_index, +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 +82 -0
88 lines not on this page · raw message
Signature · 1 line
1.6.4.2
Jan Kara
maintainerPATCH v3 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.
--- include/linux/fs.h | 1 + include/linux/radix-tree.h | 2 +- mm/page-writeback.c | 44 ++++++++++++++++++++++++++++++++++++++++++-- 3 files changed, 44 insertions(+), 3 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 +42 -2
79 lines not on this page · raw message
Signature · 1 line
1.6.4.2
Re: [PATCH 2/2] mm: Implement writeback livelock avoidance using page tagging
Quoted 102 lines · 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_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.
Signed-off-by Jan Kara <[email protected]>--- include/linux/fs.h | 1 + include/linux/radix-tree.h | 2 +- mm/page-writeback.c | 44 ++++++++++++++++++++++++++++++++++++++++++-- 3 files changed, 44 insertions(+), 3 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 +32
-0@@ -807,6 +807,30 @@ void __init page_writeback_init(void) }/** +* tag_pages_for_writeback - tag pages to be written by write_cache_pages +* @mapping: address space structure to write +* @start: starting page index +* @end: ending page index (inclusive) +* +* This function scans the page range from @start to @end and tags all pages +* that have DIRTY tag set with a special TOWRITE tag. The idea is that +* write_cache_pages (or whoever calls this function) will then use TOWRITE tag +* to identify pages eligible for writeback. This mechanism is used to avoid +* livelocking of writeback by a process steadily creating new dirty pages in +* the file (thus it is important for this function to be damn quick so that it +* can tag pages faster than a dirtying process can create them). +*/ +void tag_pages_for_writeback (struct address_space *mapping, +pgoff_t start,pgoff_t end) +{ +spin_lock_irq (&mapping->tree_lock); +radix_tree_gang_tag_if_tagged (&mapping->page_tree, start, end, +PAGECACHE_TAG_DIRTY ,PAGECACHE_TAG_TOWRITE ); +spin_unlock_irq (&mapping->tree_lock); +} +EXPORT_SYMBOL (tag_pages_for_writeback); + +/** * write_cache_pages - walk the list of dirty pages of the given address space and write all of them. * @mapping: address space structure to write * @wbc: subtract the number of written pages from *@wbc->nr_to_write @@ -820,6 +844,13 @@ void __init page_writeback_init(void)* the call was made get new I/O started against them. If wbc->sync_mode is * WB_SYNC_ALL then we were called for data integrity and we must wait for * existing IO to complete. +* +* To avoid livelocks (when other process dirties new pages), we first tag +* pages which should be written back with TOWRITE tag and only then start +* writing them. For data-integrity sync we have to be careful so that we do +* not miss some pages (e.g., because some other process has cleared TOWRITE +* tag we set). The rule we follow is that TOWRITE tag can be cleared only +* by the process clearing the DIRTY tag (and submitting the page for IO). */ int write_cache_pages(struct address_space *mapping, struct writeback_control *wbc, writepage_t writepage,@@ -836,6 +867,7 @@ int write_cache_pages(struct address_space *mapping,int cycled;int range_whole =0 ;long nr_to_write = wbc->nr_to_write; +int tag;pagevec_init (&pvec,0 );if (wbc->range_cyclic) {
mm/page-writeback.c int write_cache_pages(struct address_space *mapping, · line 894
Quoted 10 lines
mm/page-writeback.c +6
-0@@ -853,13 +885,18 @@ int write_cache_pages(struct address_space *mapping, range_whole =1 ; cycled =1 ;/* ignore range_cyclic tests */ } +if (wbc->sync_mode ==WB_SYNC_ALL ) + tag =PAGECACHE_TAG_TOWRITE ; +else + tag =PAGECACHE_TAG_DIRTY ; retry: +if (wbc->sync_mode ==WB_SYNC_ALL ) +tag_pages_for_writeback (mapping, index, end);
I wonder if this is too much spinlock latency in a huge dirty file? Some kid of batching of the operation perhaps would be good?
mm/page-writeback.c int write_cache_pages(struct address_space *mapping, · line 902
Quoted 10 lines
mm/page-writeback.c +1
-2done_index = index;while (!done && (index <= end)) {int i; - nr_pages =pagevec_lookup_tag (&pvec, mapping, &index, -PAGECACHE_TAG_DIRTY , + nr_pages =pagevec_lookup_tag (&pvec, mapping, &index, tag,min (end - index, (pgoff_t )PAGEVEC_SIZE -1 ) +1 );if (nr_pages ==0 )break ;
Would it be neat to clear the tag even if we didn't set page to writeback? It should be uncommon case.
mm/page-writeback.c int test_set_page_writeback(struct page *page) · line 1364
Quoted 10 lines
mm/page-writeback.c +3
-0@@ -1319,6 +1356,9 @@ int test_set_page_writeback(struct page *page)radix_tree_tag_clear (&mapping->page_tree,page_index (page),PAGECACHE_TAG_DIRTY ); +radix_tree_tag_clear (&mapping->page_tree, +page_index (page), +PAGECACHE_TAG_TOWRITE );spin_unlock_irqrestore (&mapping->tree_lock, flags); }else { ret =TestSetPageWriteback (page);
It would be nice to have bitwise tag clearing so we can clear multiple at once. Then
clear_tag = PAGECACHE_TAG_TOWRITE;
if (!PageDirty(page))
clear_tag |= PAGECACHE_TAG_DIRTY;
That could reduce overhead a bit more.
Jan Kara
maintainerRe: [PATCH 2/2] mm: Implement writeback livelock avoidance using page tagging
Quoted 19 lines · Nick Piggin
Quoted 18 lines · 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_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.
Signed-off-by Jan Kara <[email protected]>--- include/linux/fs.h | 1 + include/linux/radix-tree.h | 2 +- mm/page-writeback.c | 44 ++++++++++++++++++++++++++++++++++++++++++-- 3 files changed, 44 insertions(+), 3 deletions(-)
...
Quoted 55 lines
Quoted 55 lines
mm/page-writeback.c +32
-0@@ -807,6 +807,30 @@ void __init page_writeback_init(void) }/** +* tag_pages_for_writeback - tag pages to be written by write_cache_pages +* @mapping: address space structure to write +* @start: starting page index +* @end: ending page index (inclusive) +* +* This function scans the page range from @start to @end and tags all pages +* that have DIRTY tag set with a special TOWRITE tag. The idea is that +* write_cache_pages (or whoever calls this function) will then use TOWRITE tag +* to identify pages eligible for writeback. This mechanism is used to avoid +* livelocking of writeback by a process steadily creating new dirty pages in +* the file (thus it is important for this function to be damn quick so that it +* can tag pages faster than a dirtying process can create them). +*/ +void tag_pages_for_writeback (struct address_space *mapping, +pgoff_t start,pgoff_t end) +{ +spin_lock_irq (&mapping->tree_lock); +radix_tree_gang_tag_if_tagged (&mapping->page_tree, start, end, +PAGECACHE_TAG_DIRTY ,PAGECACHE_TAG_TOWRITE ); +spin_unlock_irq (&mapping->tree_lock); +} +EXPORT_SYMBOL (tag_pages_for_writeback); + +/** * write_cache_pages - walk the list of dirty pages of the given address space and write all of them. * @mapping: address space structure to write * @wbc: subtract the number of written pages from *@wbc->nr_to_write @@ -820,6 +844,13 @@ void __init page_writeback_init(void)* the call was made get new I/O started against them. If wbc->sync_mode is * WB_SYNC_ALL then we were called for data integrity and we must wait for * existing IO to complete. +* +* To avoid livelocks (when other process dirties new pages), we first tag +* pages which should be written back with TOWRITE tag and only then start +* writing them. For data-integrity sync we have to be careful so that we do +* not miss some pages (e.g., because some other process has cleared TOWRITE +* tag we set). The rule we follow is that TOWRITE tag can be cleared only +* by the process clearing the DIRTY tag (and submitting the page for IO). */ int write_cache_pages(struct address_space *mapping, struct writeback_control *wbc, writepage_t writepage,@@ -836,6 +867,7 @@ int write_cache_pages(struct address_space *mapping,int cycled;int range_whole =0 ;long nr_to_write = wbc->nr_to_write; +int tag;
Quoted 16 lines
mm/page-writeback.c int write_cache_pages(struct address_space *mapping, · line 894
Quoted 13 lines
mm/page-writeback.c +6
-0pagevec_init (&pvec,0 );if (wbc->range_cyclic) {@@ -853,13 +885,18 @@ int write_cache_pages(struct address_space *mapping, range_whole =1 ; cycled =1 ;/* ignore range_cyclic tests */ } +if (wbc->sync_mode ==WB_SYNC_ALL ) + tag =PAGECACHE_TAG_TOWRITE ; +else + tag =PAGECACHE_TAG_DIRTY ; retry: +if (wbc->sync_mode ==WB_SYNC_ALL ) +tag_pages_for_writeback (mapping, index, end);I wonder if this is too much spinlock latency in a huge dirty file? Some kid of batching of the operation perhaps would be good?
You mean like copy tags for 4096 pages, then cond_resched the spin lock
and continue? That should be doable but it will give tasks that try to livelock us more time (i.e. if there were 4096 tasks creating dirty pages than probably they would be able to livelock us, won't they? Maybe we don't care?).
Quoted 4 lines
Quoted 4 lines
mm/page-writeback.c +0
-0done_index = index;while (!done && (index <= end)) {int i;
Quoted 9 lines
mm/page-writeback.c int write_cache_pages(struct address_space *mapping, · line 902
Quoted 6 lines
mm/page-writeback.c +1
-2- nr_pages =pagevec_lookup_tag (&pvec, mapping, &index, -PAGECACHE_TAG_DIRTY , + nr_pages =pagevec_lookup_tag (&pvec, mapping, &index, tag,min (end - index, (pgoff_t )PAGEVEC_SIZE -1 ) +1 );if (nr_pages ==0 )break ;Would it be neat to clear the tag even if we didn't set page to writeback? It should be uncommon case.
Yeah, why not.
Quoted 14 lines
mm/page-writeback.c int test_set_page_writeback(struct page *page) · line 1364
Quoted 10 lines
mm/page-writeback.c +3
-0@@ -1319,6 +1356,9 @@ int test_set_page_writeback(struct page *page)radix_tree_tag_clear (&mapping->page_tree,page_index (page),PAGECACHE_TAG_DIRTY ); +radix_tree_tag_clear (&mapping->page_tree, +page_index (page), +PAGECACHE_TAG_TOWRITE );spin_unlock_irqrestore (&mapping->tree_lock, flags); }else { ret =TestSetPageWriteback (page);It would be nice to have bitwise tag clearing so we can clear multiple at once. Then
Quoted 5 lines
clear_tag=PAGECACHE_TAG_TOWRITE;
if (!PageDirty(page))
clear_tag|=PAGECACHE_TAG_DIRTY;That could reduce overhead a bit more.
Good idea. Will do.
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Re: [PATCH 2/2] mm: Implement writeback livelock avoidance using page tagging
Quoted 7 lines · Jan Kara
Quoted 6 lines · Nick Piggin
Review
Quoted 2 lines · Jan Kara
(quoted diff) +2
-0+ if (wbc->sync_mode == WB_SYNC_ALL) + tag_pages_for_writeback(mapping, index, end);I wonder if this is too much spinlock latency in a huge dirty file? Some kid of batching of the operation perhaps would be good?
Quoted 5 lines
You mean like copy tags for 4096 pages, then
cond_reschedthe spin lock
and continue? That should be doable but it will give tasks that try to livelock us more time (i.e. if there were 4096 tasks creating dirty pages than probably they would be able to livelock us, won't they? Maybe we don't care?).
Not 100% sure. I think that if we've got the inode in I_SYNC state, it should stop cleaning and dirtiers will get throttled.
Even if writeback was able to continue on that inode, it would be a big achievement to dirty then clean pages as fast as we are able to tag them in batches of 4096 :)
--
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 14 lines · Nick Piggin
Quoted 7 lines · Jan Kara
Quoted 6 lines · Nick Piggin
Review
Quoted 2 lines · Jan Kara
(quoted diff) +2
-0+ if (wbc->sync_mode == WB_SYNC_ALL) + tag_pages_for_writeback(mapping, index, end);I wonder if this is too much spinlock latency in a huge dirty file? Some kid of batching of the operation perhaps would be good?
Quoted 5 lines
You mean like copy tags for 4096 pages, then
cond_reschedthe spin lock
and continue? That should be doable but it will give tasks that try to livelock us more time (i.e. if there were 4096 tasks creating dirty pages than probably they would be able to livelock us, won't they? Maybe we don't care?).
Quoted 6 lines
Not 100% sure. I think that if we've got the inode in
I_SYNCstate, it should stop cleaning and dirtiers will get throttled.Even if writeback was able to continue on that inode, it would be a big achievement to dirty then clean pages as fast as we are able to tag them in batches of 4096 :)
In practice, you are probably right that the writers will eventually get
throttled if they were aggressive enough to dirty lots of pages while we cond_resched the lock...
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Jan Kara
maintainerRe: [PATCH 2/2] mm: Implement writeback livelock avoidance using page tagging
In reply to Jan KaraQuoted 15 lines · Jan Kara
Quoted 5 lines · Nick Piggin
Quoted 4 lines · Jan Kara
mm/page-writeback.c +0
-0done_index = index;while (!done && (index <= end)) {int i;Quoted 9 lines
mm/page-writeback.c int write_cache_pages(struct address_space *mapping, · line 902
Quoted 6 lines
mm/page-writeback.c +1
-2- nr_pages =pagevec_lookup_tag (&pvec, mapping, &index, -PAGECACHE_TAG_DIRTY , + nr_pages =pagevec_lookup_tag (&pvec, mapping, &index, tag,min (end - index, (pgoff_t )PAGEVEC_SIZE -1 ) +1 );if (nr_pages ==0 )break ;Would it be neat to clear the tag even if we didn't set page to writeback? It should be uncommon case.
Quoted 1 line
Yeah, why not.
Looking at this more, we shouldn't leave any TOWRITE tags dangling inWB_SYNC_ALL mode - as soon as someone writes the page, he does set_page_writeback() which clears the tag. Similarly if the page is removed from the mapping, the tag is cleared. Or am I missing something?
Quoted 14 lines
Quoted 14 lines
mm/page-writeback.c int test_set_page_writeback(struct page *page) · line 1364
Quoted 10 lines
mm/page-writeback.c +3
-0@@ -1319,6 +1356,9 @@ int test_set_page_writeback(struct page *page)radix_tree_tag_clear (&mapping->page_tree,page_index (page),PAGECACHE_TAG_DIRTY ); +radix_tree_tag_clear (&mapping->page_tree, +page_index (page), +PAGECACHE_TAG_TOWRITE );spin_unlock_irqrestore (&mapping->tree_lock, flags); }else { ret =TestSetPageWriteback (page);It would be nice to have bitwise tag clearing so we can clear multiple at once. Then
Quoted 6 lines
Quoted 5 lines
clear_tag=PAGECACHE_TAG_TOWRITE;
if (!PageDirty(page))
clear_tag|=PAGECACHE_TAG_DIRTY;That could reduce overhead a bit more.
Good idea. Will do.
On a second thought, will it bring us enough to justify a new interface
(which will be inconsistent with all the other radix tree interfaces because they use tag numbers and not bitmaps)? Because looking at the code, all we could save is the transformation of page index into a radix tree path. We would have to do all the other work for each tag separately anyway and it won't probably have any great cache locality either because radix trees for different tags are separate.
Honza
Signature · 8 lines
Jan Kara <[email protected]> SUSE Labs, CR -- 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 2/2] mm: Implement writeback livelock avoidance using page tagging
In reply to Jan KaraI have an oops with current Linus' tree in xfstests 217 that looks like it was caused by this patch:
217 149s ...[ 5105.342605] XFS mounting filesystem vdb6
[ 5105.373481] Ending clean XFS mount for filesystem: vdb6 [ 5115.405061] XFS mounting filesystem loop0 [ 5115.548654] Ending clean XFS mount for filesystem: loop0 [ 5115.588067] BUG: unable to handle kernel paging request at f7f14000 [ 5115.588067] IP: [<c07224fd>] radix_tree_range_tag_if_tagged+0x15d/0x1c0 [ 5115.588067] *pde = 00007067 *pte = 00000000 [ 5115.588067] Oops: 0000 [#1] SMP [ 5115.588067] last sysfs file:
/sys/devices/virtual/block/loop0/removable
Entering kdb (current=0xf7868100, pid 15675) on processor 0 Oops: (null) due to oops @ 0xc07224fd <d>Modules linked in:
<c>
<d>Pid: 15675, comm: mkfs.xfs Not tainted 2.6.35+ #305 /Bochs
<d>EIP: 0060:[<c07224fd>] EFLAGS: 00010002 CPU: 0
EIP is at radix_tree_range_tag_if_tagged+0x15d/0x1c0
<d>EAX: f7f14000 EBX: 00000000 ECX: 482bb4f8 EDX: 0c0748d4
<d>ESI: 2031756d EDI: 00000000 EBP: c7d41d10 ESP: c7d41cb0
<d> DS: 007b ES: 007b FS: 00d8 GS: 0033 SS: 0068
<0>Process mkfs.xfs (pid: 15675, ti=c7d40000 task=f7868100
task.ti=c7d40000)
<0>Stack: ffffffff f774a1d8 f774a598 f774aa98 cfd9c598 e7c89458 00000001 00000000 <0> c01e0caf c01e0caf 00000046 00000010 00000000 e7c89568 c7d41d28 c355ad50
<0> ffffffff 00000208 00000007 c7d41cb0 00000003 ffffffff c355ad5c ffffffff <0>Call Trace:
<0> [<c01e0caf>] ? tag_pages_for_writeback+0x1f/0xc0
<0> [<c01e0caf>] ? tag_pages_for_writeback+0x1f/0xc0
<0> [<c01e0cd3>] ? tag_pages_for_writeback+0x43/0xc0
<0> [<c01e172b>] ? write_cache_pages+0x23b/0x370
<0> [<c01e0980>] ? __writepage+0x0/0x30
<0> [<c0528979>] ? xfs_vm_writepages+0x29/0x50
[0]more>
Only 'q' or 'Q' are processed at more prompt, input ignored
<0> [<c0528979>] ? xfs_vm_writepages+0x29/0x50
<0> [<c05296e0>] ? xfs_vm_writepage+0x0/0x630
<0> [<c01e187f>] ? generic_writepages+0x1f/0x30
<0> [<c0528992>] ? xfs_vm_writepages+0x42/0x50
<0> [<c01e18a7>] ? do_writepages+0x17/0x30
<0> [<c01da57c>] ? __filemap_fdatawrite_range+0x5c/0x70
<0> [<c01da8a6>] ? filemap_fdatawrite+0x26/0x30
<0> [<c01da8dd>] ? filemap_write_and_wait+0x2d/0x50
<0> [<c052e812>] ? xfs_flushinval_pages+0x72/0xe0
<0> [<c0506c9c>] ? xfs_ilock+0x7c/0xd0
<0> [<c052d7d7>] ? xfs_file_aio_read+0x307/0x340
<0> [<c020e69c>] ? do_sync_read+0x9c/0xd0
<0> [<c0189636>] ? up_read+0x16/0x30
<0> [<c020e957>] ? vfs_read+0x97/0x140
<0> [<c020e600>] ? do_sync_read+0x0/0xd0
<0> [<c0181c18>] ? __task_pid_nr_ns+0x88/0xd0
<0> [<c020f1c3>] ? sys_pread64+0x63/0x80
<0> [<c09cb7ed>] ? syscall_call+0x7/0xb
<0>Code: f0 83 c3 01 d3 e3 39 5d e0 72 51 8b 45 08 39 45 e4 73 49 89 d8
d3 e8 a8 3f 0f 85 47 ff ff ff 8b 75 ec 8d 04 96 90 83 c1 06 89 df <8b>
30 d3 ef 83 c2 01 83 c0 04 83 e7 3f 74 ec e9 27 ff ff ff 8b
Jan Kara
maintainerRe: [PATCH 2/2] mm: Implement writeback livelock avoidance using page tagging
Quoted 2 lines · Christoph Hellwig
I have an oops with current Linus' tree in xfstests 217 that looks like it was caused by this patch:
Thanks for report!
Quoted 10 lines
217 149s ...[ 5105.342605] XFS mounting filesystem vdb6
[ 5105.373481] Ending clean XFS mount for filesystem: vdb6 [ 5115.405061] XFS mounting filesystem loop0 [ 5115.548654] Ending clean XFS mount for filesystem: loop0 [ 5115.588067] BUG: unable to handle kernel paging request at f7f14000 [ 5115.588067] IP: [<c07224fd>] radix_tree_range_tag_if_tagged+0x15d/0x1c0 [ 5115.588067] *pde = 00007067 *pte = 00000000 [ 5115.588067] Oops: 0000 [#1] SMP [ 5115.588067] last sysfs file:
/sys/devices/virtual/block/loop0/removable
We seem to oops at:
while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) {
/*
* We've fully scanned this node. Go up. Because
* last_index is guaranteed to be in the tree, what
* we do below cannot wander astray.
*/
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
slot = open_slots[height];
height++;
shift += RADIX_TREE_MAP_SHIFT;
}Quoted 8 lines
Entering kdb (current=0xf7868100, pid 15675) on processor 0 Oops: (null) due to oops @
0xc07224fd<d>Modules linked in:
<c>
<d>Pid: 15675, comm: mkfs.xfs Not tainted 2.6.35+ #305 /Bochs
<d>EIP: 0060:[<c07224fd>] EFLAGS: 00010002 CPU: 0
EIP is atradix_tree_range_tag_if_tagged+0x15d/0x1c0
<d>EAX:f7f14000EBX: 00000000 ECX:482bb4f8EDX:0c0748d4
<d>ESI:2031756dEDI: 00000000 EBP:c7d41d10ESP:c7d41cb0
And from the values in registers the loop seems to have went astray
because "index" was zero at the point we entered the loop... looking around... Ah, I see, you create files with 16TB size which creates radix tree of such height that radix_tree_maxindex(height) == ~0UL and if write_cache_pages() passes in ~0UL as end, we can overflow the index. Hmm, I haven't realized that is possible.
OK, attached is a patch that should fix the issue. There is just still an
issue that *first_indexp will overflow in this case as well and thus we could in theory loop indefinitely. I'll have to think how to best handle this overflow - checking in caller is kind of prone to errors...
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Quoted 1 line
From
c2095a0047822139a7f72ba6e766e94acd4affafMon Sep 17 00:00:00 2001
From: Jan Kara <[email protected]>
Date: Fri, 13 Aug 2010 00:20:25 +0200
Subject: [PATCH] mm: Fix overflow in radix_tree_range_tag_if_tagged
When radix_tree_maxindex() is ~0UL, it can happen that scanning overflows index and tree traversal code goes astray reading memory until it hits unreadable memory. Check for overflow and exit in that case.
--- lib/radix-tree.c | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-)
lib/radix-tree.c +2 -1
@@ -673,7 +673,8 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, next:/* Go to next item at level determined by 'shift' */ index = ((index >> shift) +1 ) << shift; -if (index > last_index) +/* Overflow can happen when last_index is ~0UL... */ +if (index > last_index || !index)break ;if (tagged > nr_to_tag)break ;
Signature · 1 line
1.6.4.2
Re: [PATCH 2/2] mm: Implement writeback livelock avoidance using page tagging
Quoted 7 lines · Jan Kara
And from the values in registers the loop seems to have went astray
because "index" was zero at the point we entered the loop... looking around... Ah, I see, you create files with 16TB size which creates radix tree of such height thatradix_tree_maxindex(height)== ~0UL and ifwrite_cache_pages()passes in ~0UL as end, we can overflow the index. Hmm, I haven't realized that is possible.
OK, attached is a patch that should fix the issue.
This seems to fix the case for me.
Quoted 9 lines · Jan Kara
Hi,
I've revived my patches to implement livelock avoidance for data integrity
writes. Due to some concerns whether tagging of pages before writeout cannot be too costly to use forWB_SYNC_NONEmode (where we stop afternr_to_writepages) I've changed the patch to use page tagging only inWB_SYNC_ALLmode where we are sure that we write out all the tagged pages. Later, we can think about using tagging for livelock avoidance forWB_SYNC_NONEmode as well...
Hmm what concerns? Do you have any numbers?
--
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>
Quoted 4 lines · Nick Piggin
Quoted 3 lines · Jan Kara
Hi,
Quoted 8 lines
Quoted 6 lines
I've revived my patches to implement livelock avoidance for data integrity
writes. Due to some concerns whether tagging of pages before writeout cannot be too costly to use forWB_SYNC_NONEmode (where we stop afternr_to_writepages) I've changed the patch to use page tagging only inWB_SYNC_ALLmode where we are sure that we write out all the tagged pages. Later, we can think about using tagging for livelock avoidance forWB_SYNC_NONEmode as well...Hmm what concerns? Do you have any numbers?
sync() is performed in two stages: the WB_SYNC_NONE run and the WB_SYNC_ALL run. The WB_SYNC_NONE stage can still be livelocked.
We may switch to wbc.for_sync (instead of testing WB_SYNC_ALL only) provided by the following patch. Jan, would you add it to your series (with necessary improvements)?
Thanks,
Fengguang
---
introduce wbc.for_sync to cover the two sync() stages
The sync() is performed in two stages: the WB_SYNC_NONE sync and the WB_SYNC_ALL sync. It is necessary to tag both stages with wbc.for_sync, so as to prevent either of them being livelocked.
The next patch will utilize this flag to do the livelock prevention.
btw, the nr_pages param in bdi_start_writeback() is dropped:
1) better livelock prevention will be used. Limiting nr_to_write was inferior in that it may miss some pages to sync. And it does not really avoid livelock for single huge file: write_cache_pages() ignores nr_to_write for WB_SYNC_NONE at all.
2) It is very unlikely to impact some not-for-sync existing users. For example the ubifs call writeback_inodes_sb() to writeback some pages. And the ext4 also intents to write somehow enough pages with writeback_inodes_sb_if_idle(). However they seem not really care to write more pages.
--- fs/fs-writeback.c | 28 ++++++++-------------------- include/linux/backing-dev.h | 2 +- include/linux/writeback.h | 8 ++++++++ mm/page-writeback.c | 2 +- 4 files changed, 18 insertions(+), 22 deletions(-)
fs/fs-writeback.c +8 -20
@@ -42,6 +42,7 @@ struct wb_writeback_args {long nr_pages;struct super_block *sb;enum writeback_sync_modes sync_mode; + int for_sync:1; unsigned int for_kupdate:1; unsigned int range_cyclic:1; unsigned int for_background:1;
@@ -228,6 +229,7 @@ static void bdi_sync_writeback(struct bastruct wb_writeback_args args = { .sb = sb, .sync_mode =WB_SYNC_ALL , + .for_sync =1 , .nr_pages =LONG_MAX , .range_cyclic =0 , };
@@ -244,7 +246,6 @@ static void bdi_sync_writeback(struct ba* bdi_start_writeback - start writeback * @bdi: the backing device to write from * @sb: write inodes from this super_block -* @nr_pages: the number of pages to write * * Description: * This does WB_SYNC_NONE opportunistic writeback. The IO is only
@@ -253,24 +254,17 @@ static void bdi_sync_writeback(struct ba* */ void bdi_start_writeback (struct backing_dev_info *bdi,struct super_block *sb, -long nr_pages) +long mission) {struct wb_writeback_args args = { .sb = sb, .sync_mode =WB_SYNC_NONE , - .nr_pages = nr_pages, + .nr_pages =LONG_MAX , + .for_background = mission ==WB_FOR_BACKGROUND , + .for_sync = mission ==WB_FOR_SYNC , .range_cyclic =1 , }; -/* -* We treat @nr_pages=0 as the special case to do background writeback, -* ie. to sync pages until the background dirty threshold is reached. -*/ -if (!nr_pages) { - args.nr_pages =LONG_MAX ; - args.for_background =1 ; - } -bdi_alloc_queue_work (bdi, &args); }
@@ -757,6 +751,7 @@ static long wb_writeback(struct bdi_writ .older_than_this = NULL, .for_kupdate = args->for_kupdate, .for_background = args->for_background, + .for_sync = args->for_sync, .range_cyclic = args->range_cyclic, };unsigned long oldest_jif;
@@ -1216,14 +1211,7 @@ static void wait_sb_inodes(struct super_*/ void writeback_inodes_sb (struct super_block *sb) { -unsigned long nr_dirty =global_page_state (NR_FILE_DIRTY ); -unsigned long nr_unstable =global_page_state (NR_UNSTABLE_NFS ); -long nr_to_write; - - nr_to_write = nr_dirty + nr_unstable + - (inodes_stat.nr_inodes - inodes_stat.nr_unused); - -bdi_start_writeback (sb->s_bdi, sb, nr_to_write); +bdi_start_writeback (sb->s_bdi, sb,WB_FOR_SYNC ); }EXPORT_SYMBOL (writeback_inodes_sb);
include/linux/backing-dev.h +1 -1
@@ -106,7 +106,7 @@ int bdi_register_dev(struct backing_dev_void bdi_unregister (struct backing_dev_info *bdi);int bdi_setup_and_register (struct backing_dev_info *,char *,unsigned int );void bdi_start_writeback (struct backing_dev_info *bdi,struct super_block *sb, -long nr_pages); +long mission);int bdi_writeback_task (struct bdi_writeback *wb);int bdi_has_dirty_io (struct backing_dev_info *bdi);void bdi_arm_supers_timer (void );
include/linux/writeback.h +8 -0
@@ -21,6 +21,13 @@ enum writeback_sync_modes { WB_SYNC_ALL, /* Wait on every mapping */ }; +enum writeback_mission { +WB_FOR_BACKGROUND ,/* stop on hitting background threshold */ +WB_FOR_SYNC ,/* write all now-dirty inodes/pages, +* but take care not to live lock +*/ +}; +/* * A control structure which tells the writeback code what to do. These are * always on the stack, and hence need no locking. They are always initialised
@@ -53,6 +60,7 @@ struct writeback_control { unsigned encountered_congestion:1; /* An output: a queue is full */ unsigned for_kupdate:1; /* A kupdate writeback */ unsigned for_background:1; /* A background writeback */ + unsigned for_sync:1; /* A writeback for sync */ unsigned for_reclaim:1; /* Invoked from the page allocator */ unsigned range_cyclic:1; /* range_start is cyclic */ unsigned more_io:1; /* more io to be dispatched */
mm/page-writeback.c +1 -1
@@ -597,7 +597,7 @@ static void balance_dirty_pages(struct a (!laptop_mode && ((global_page_state(NR_FILE_DIRTY) + global_page_state(NR_UNSTABLE_NFS)) > background_thresh))) -bdi_start_writeback (bdi,NULL ,0 ); +bdi_start_writeback (bdi,NULL ,WB_FOR_BACKGROUND ); }void set_page_dirty_balance (struct page *page,int page_mkwrite)
Quoted 12 lines · Wu Fengguang
Quoted 11 lines · Nick Piggin
Quoted 9 lines · Jan Kara
Hi,
I've revived my patches to implement livelock avoidance for data integrity
writes. Due to some concerns whether tagging of pages before writeout cannot be too costly to use forWB_SYNC_NONEmode (where we stop afternr_to_writepages) I've changed the patch to use page tagging only inWB_SYNC_ALLmode where we are sure that we write out all the tagged pages. Later, we can think about using tagging for livelock avoidance forWB_SYNC_NONEmode as well...
Quoted 4 lines
Quoted 1 line
Hmm what concerns? Do you have any numbers?
sync()is performed in two stages: theWB_SYNC_NONErun and theWB_SYNC_ALLrun. TheWB_SYNC_NONEstage can still be livelocked.
By concerns, I mean Jan's _performance_ concerns. I would prefer to minimise them, and then try to get an idea of the performance impact of doing tagging unconditionally.