Converting writeback linked lists to a tree based data structure

From: Michael Rubin <[email protected]>

For those of you who have waited so long. This is the third submission of the first attempt at this patch. It is a trilogy.

Just a quick question, how does this interact/depend-uppon etc.. with Fengguangs patches I still have in my mailbox? (Those from Dec 28th)

Quoted 2 lines · Peter Zijlstra

Just a quick question, how does this interact/depend-uppon etc.. with Fengguangs patches I still have in my mailbox? (Those from Dec 28th)

They don't. They apply to a 2.6.24rc7 tree. This is a candidte for 2.6.25.

This work was done before Fengguang's patches. I am trying to test Fengguang's for comparison but am having problems with getting mm1 to boot on my systems.

Quoted 9 lines · Michael Rubin

Quoted 2 lines · Peter Zijlstra

Just a quick question, how does this interact/depend-uppon etc.. with Fengguangs patches I still have in my mailbox? (Those from Dec 28th)

They don't. They apply to a 2.6.24rc7 tree. This is a candidte for 2.6.25.

This work was done before Fengguang's patches. I am trying to test Fengguang's for comparison but am having problems with getting mm1 to boot on my systems.

Yeah, they are independent ones. The initial motivation is to fix the bug "sluggish writeback on small+large files". Michael introduced a new rbtree, and me introduced a new list(s_more_io_wait).

Basically I think rbtree is an overkill to do time based ordering. Sorry, Michael. But s_dirty would be enough for that. Plus, s_more_io provides fair queuing between small/large files, and s_more_io_wait provides waiting mechanism for blocked inodes.

The time ordered rbtree may delay io for a blocked inode simply by modifying its dirtied_when and reinsert it. But it would no longer be that easy if it is to be ordered by location.

If we are going to do location based ordering in the future, the lists will continue to be useful. It would simply be a matter of switching from the s_dirty(order by time) to some rbtree or radix tree(order by location).

We can even provide both ordering at the same time to different fs/inodes which is configurable by the user. Because the s_dirty and/or rbtree would provide _only_ ordering(not faireness or waiting) and hence is interchangeable.

This patchset could be a good reference. It does location based ordering with radix tree:

[RFC][PATCH] clustered writeback <http://lkml.org/lkml/2007/8/27/45>

Quoted 20 lines · On Wed, 16 Jan 2008 11:01:08 +0800 Fengguang Wu <[email protected]> wrote:

Quoted 9 lines · Michael Rubin

Quoted 2 lines · Peter Zijlstra

Just a quick question, how does this interact/depend-uppon etc.. with Fengguangs patches I still have in my mailbox? (Those from Dec 28th)

They don't. They apply to a 2.6.24rc7 tree. This is a candidte for 2.6.25.

This work was done before Fengguang's patches. I am trying to test Fengguang's for comparison but am having problems with getting mm1 to boot on my systems.

Yeah, they are independent ones. The initial motivation is to fix the bug "sluggish writeback on small+large files". Michael introduced a new rbtree, and me introduced a new list(s_more_io_wait).

Basically I think rbtree is an overkill to do time based ordering. Sorry, Michael. But s_dirty would be enough for that. Plus, s_more_io provides fair queuing between small/large files, and s_more_io_wait provides waiting mechanism for blocked inodes.

Quoted 3 lines

The time ordered rbtree may delay io for a blocked inode simply by modifying its dirtied_when and reinsert it. But it would no longer be that easy if it is to be ordered by location.

What does the term "ordered by location" mean? Attemting to sort inodes by physical disk address? By using their i_ino as a key?

That sounds optimistic.

Quoted 10 lines

If we are going to do location based ordering in the future, the lists will continue to be useful. It would simply be a matter of switching from the s_dirty(order by time) to some rbtree or radix tree(order by location).

We can even provide both ordering at the same time to different fs/inodes which is configurable by the user. Because the s_dirty and/or rbtree would provide _only_ ordering(not faireness or waiting) and hence is interchangeable.

Quoted 4 lines

This patchset could be a good reference. It does location based ordering with radix tree:

[RFC][PATCH] clustered writeback <http://lkml.org/lkml/2007/8/27/45>

list_heads are just the wrong data structure for this function. Especially list_heads which are protected by a non-sleeping lock.

list_heads are OK if we use them for one and only function.

Quoted 1 line · On Wed, 16 Jan 2008 12:25:53 +0800 Fengguang Wu <[email protected]> wrote:

list_heads are OK if we use them for one and only function.

Not really. They're inappropriate when you wish to remember your position in the list while you dropped the lock (as we must do in writeback).

A data structure which permits us to interate across the search key rather than across the actual storage locations is more appropriate.

Quoted 8 lines · Andrew Morton

Quoted 1 line · On Wed, 16 Jan 2008 12:25:53 +0800 Fengguang Wu <[email protected]> wrote:

list_heads are OK if we use them for one and only function.

Not really. They're inappropriate when you wish to remember your position in the list while you dropped the lock (as we must do in writeback).

Quoted 2 lines

A data structure which permits us to interate across the search key rather than across the actual storage locations is more appropriate.

I totally agree with you. What I mean is to first do the split of functions - into three: ordering, starvation prevention, and blockade waiting.

Then to do better ordering by adopting radix tree(or rbtree if radix tree is not enough),

and lastly get rid of the list_heads to
avoid locking. Does it sound like a good path?

Quoted 9 lines · On Wed, 16 Jan 2008 12:55:07 +0800 Fengguang Wu <[email protected]> wrote:

Quoted 8 lines · Andrew Morton

Quoted 1 line · On Wed, 16 Jan 2008 12:25:53 +0800 Fengguang Wu <[email protected]> wrote:

list_heads are OK if we use them for one and only function.

Not really. They're inappropriate when you wish to remember your position in the list while you dropped the lock (as we must do in writeback).

Quoted 6 lines

Quoted 2 lines

A data structure which permits us to interate across the search key rather than across the actual storage locations is more appropriate.

I totally agree with you. What I mean is to first do the split of functions - into three: ordering, starvation prevention, and blockade waiting.

Does "ordering" here refer to ordering bt time-of-first-dirty?

What is "blockade waiting"?

Quoted 2 lines

Then to do better ordering by adopting radix tree(or rbtree if radix tree is not enough),

ordering of what?

Quoted 2 lines

and lastly get rid of the list_heads to
avoid locking. Does it sound like a good path?

I'd have thaought that replacing list_heads with another data structure would be a simgle commit.

Quoted 10 lines · Andrew Morton

Quoted 8 lines · On Wed, 16 Jan 2008 12:55:07 +0800 Fengguang Wu <[email protected]> wrote:

Quoted 7 lines · Andrew Morton

Quoted 1 line · On Wed, 16 Jan 2008 12:25:53 +0800 Fengguang Wu <[email protected]> wrote:

list_heads are OK if we use them for one and only function.

Not really. They're inappropriate when you wish to remember your position in the list while you dropped the lock (as we must do in writeback).

Quoted 6 lines

Quoted 5 lines

Quoted 2 lines

A data structure which permits us to interate across the search key rather than across the actual storage locations is more appropriate.

I totally agree with you. What I mean is to first do the split of functions - into three: ordering, starvation prevention, and blockade waiting.

Does "ordering" here refer to ordering bt time-of-first-dirty?

Ordering by dirtied_when or i_ino, either is OK.

Quoted 1 line

What is "blockade waiting"?

Some inodes/pages cannot be synced now for some reason and should be retried after a while.

Quoted 3 lines

Quoted 2 lines

Then to do better ordering by adopting radix tree(or rbtree if radix tree is not enough),

ordering of what?

Switch from time to location.

Quoted 4 lines

Quoted 2 lines

and lastly get rid of the list_heads to
avoid locking. Does it sound like a good path?

I'd have thaought that replacing list_heads with another data structure would be a simgle commit.

That would be easy. s_more_io and s_more_io_wait can all be converted to radix trees.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 4 lines · Andrew Morton

Quoted 2 lines

Then to do better ordering by adopting radix tree(or rbtree if radix tree is not enough),

ordering of what?

Switch from time to location.

Quoted 5 lines

Quoted 2 lines

and lastly get rid of the list_heads to
avoid locking. Does it sound like a good path?

I'd have thaought that replacing list_heads with another data structure would be a simgle commit.

That would be easy. s_more_io and s_more_io_wait can all be converted to radix trees.

Quoted 6 lines · Fengguang Wu

Quoted 4 lines · Andrew Morton

Quoted 2 lines

Then to do better ordering by adopting radix tree(or rbtree if radix tree is not enough),

ordering of what?

Quoted 1 line

Switch from time to location.

Note that data writeback may be adversely affected by location based writeback rather than time based writeback - think of the effect of location based data writeback on an app that creates lots of short term (<30s) temp files and then removes them before they are written back.

Also, data writeback locatio cannot be easily derived from the inode number in pretty much all cases. "near" in terms of XFS means the same AG which means the data could be up to a TB away from the inode, and if you have >1TB filesystems usingthe default inode32 allocator, file data is *never* placed near the inode - the inodes are in the first TB of the filesystem, the data is rotored around the rest of the filesystem.

And with delayed allocation, you don't know where the data is even going to be written ahead of the filesystem ->writepage call, so you can't do optimal location ordering for data in this case.

Hmmmm - I'm wondering if we'd do better to split data writeback from inode writeback. i.e. we do two passes. The first pass writes all the data back in time order, the second pass writes all the inodes back in location order.

Right now we interleave data and inode writeback, (i.e. we do data, inode, data, inode, data, inode, ....). I'd much prefer to see all data written out first, then the inodes. ->writepage often dirties the inode and hence if we need to do multiple do_writepages() calls on an inode to flush all the data (e.g. congestion, large amounts of data to be written, etc), we really shouldn't be calling write_inode() after every do_writepages() call. The inode should not be written until all the data is written....

Quoted 9 lines · David Chinner

Quoted 7 lines · Fengguang Wu

Quoted 4 lines · Andrew Morton

Quoted 2 lines

Then to do better ordering by adopting radix tree(or rbtree if radix tree is not enough),

ordering of what?

Switch from time to location.

Quoted 5 lines

Note that data writeback may be adversely affected by location based writeback rather than time based writeback - think of the effect of location based data writeback on an app that creates lots of short term (<30s) temp files and then removes them before they are written back.

A small(e.g. 5s) time window can still be enforced, but...

Quoted 5 lines

Hmmmm - I'm wondering if we'd do better to split data writeback from inode writeback. i.e. we do two passes. The first pass writes all the data back in time order, the second pass writes all the inodes back in location order.

Quoted 8 lines

Right now we interleave data and inode writeback, (i.e. we do data, inode, data, inode, data, inode, ....). I'd much prefer to see all data written out first, then the inodes. ->writepage often dirties the inode and hence if we need to do multiple do_writepages() calls on an inode to flush all the data (e.g. congestion, large amounts of data to be written, etc), we really shouldn't be calling write_inode() after every do_writepages() call. The inode should not be written until all the data is written....

That may do good to XFS. Another case is documented as follows:
"the write_inode() function of a typical fs will perform no I/O, but will mark buffers in the blockdev mapping as dirty."

Quoted 20 lines · On Wed, 16 Jan 2008 11:01:08 +0800 Fengguang Wu <[email protected]> wrote:

Quoted 9 lines · Michael Rubin

Quoted 2 lines · Peter Zijlstra

Just a quick question, how does this interact/depend-uppon etc.. with Fengguangs patches I still have in my mailbox? (Those from Dec 28th)

They don't. They apply to a 2.6.24rc7 tree. This is a candidte for 2.6.25.

This work was done before Fengguang's patches. I am trying to test Fengguang's for comparison but am having problems with getting mm1 to boot on my systems.

Yeah, they are independent ones. The initial motivation is to fix the bug "sluggish writeback on small+large files". Michael introduced a new rbtree, and me introduced a new list(s_more_io_wait).

Basically I think rbtree is an overkill to do time based ordering. Sorry, Michael. But s_dirty would be enough for that. Plus, s_more_io provides fair queuing between small/large files, and s_more_io_wait provides waiting mechanism for blocked inodes.

Quoted 3 lines

The time ordered rbtree may delay io for a blocked inode simply by modifying its dirtied_when and reinsert it. But it would no longer be that easy if it is to be ordered by location.

What does the term "ordered by location" mean? Attemting to sort inodes by physical disk address? By using their i_ino as a key?

That sounds optimistic.

Quoted 26 lines · Andrew Morton

Quoted 23 lines · On Wed, 16 Jan 2008 11:01:08 +0800 Fengguang Wu <[email protected]> wrote:

Quoted 9 lines · Michael Rubin

Quoted 2 lines · Peter Zijlstra

Just a quick question, how does this interact/depend-uppon etc.. with Fengguangs patches I still have in my mailbox? (Those from Dec 28th)

They don't. They apply to a 2.6.24rc7 tree. This is a candidte for 2.6.25.

This work was done before Fengguang's patches. I am trying to test Fengguang's for comparison but am having problems with getting mm1 to boot on my systems.

Yeah, they are independent ones. The initial motivation is to fix the bug "sluggish writeback on small+large files". Michael introduced a new rbtree, and me introduced a new list(s_more_io_wait).

Basically I think rbtree is an overkill to do time based ordering. Sorry, Michael. But s_dirty would be enough for that. Plus, s_more_io provides fair queuing between small/large files, and s_more_io_wait provides waiting mechanism for blocked inodes.

The time ordered rbtree may delay io for a blocked inode simply by modifying its dirtied_when and reinsert it. But it would no longer be that easy if it is to be ordered by location.

Quoted 4 lines

What does the term "ordered by location" mean? Attemting to sort inodes by physical disk address? By using their i_ino as a key?

That sounds optimistic.

In XFS, inode number is an encoding of it's location on disk, so ordering inode writeback by inode number *does* make sense.

Quoted 30 lines · On Wed, 16 Jan 2008 18:55:38 +1100 David Chinner <[email protected]> wrote:

Quoted 29 lines · Andrew Morton

Quoted 15 lines · On Wed, 16 Jan 2008 11:01:08 +0800 Fengguang Wu <[email protected]> wrote:

Quoted 9 lines · Michael Rubin

Quoted 2 lines · Peter Zijlstra

Just a quick question, how does this interact/depend-uppon etc.. with Fengguangs patches I still have in my mailbox? (Those from Dec 28th)

They don't. They apply to a 2.6.24rc7 tree. This is a candidte for 2.6.25.

This work was done before Fengguang's patches. I am trying to test Fengguang's for comparison but am having problems with getting mm1 to boot on my systems.

Yeah, they are independent ones. The initial motivation is to fix the bug "sluggish writeback on small+large files". Michael introduced a new rbtree, and me introduced a new list(s_more_io_wait).

Quoted 8 lines

Basically I think rbtree is an overkill to do time based ordering. Sorry, Michael. But s_dirty would be enough for that. Plus, s_more_io provides fair queuing between small/large files, and s_more_io_wait provides waiting mechanism for blocked inodes.

The time ordered rbtree may delay io for a blocked inode simply by modifying its dirtied_when and reinsert it. But it would no longer be that easy if it is to be ordered by location.

What does the term "ordered by location" mean? Attemting to sort inodes by physical disk address? By using their i_ino as a key?

Quoted 4 lines

Quoted 1 line

That sounds optimistic.

In XFS, inode number is an encoding of it's location on disk, so ordering inode writeback by inode number *does* make sense.

This code is mainly concerned with writing pagecache data, not inodes.

Basically I think rbtree is an overkill to do time based ordering. Sorry, Michael. But s_dirty would be enough for that. Plus, s_more_io provides fair queuing between small/large files, and s_more_io_wait provides waiting mechanism for blocked inodes.

Quoted 4 lines · Fengguang Wu

Basically I think rbtree is an overkill to do time based ordering. Sorry, Michael. But s_dirty would be enough for that. Plus, s_more_io provides fair queuing between small/large files, and s_more_io_wait provides waiting mechanism for blocked inodes.

I think the flush_tree (which is a little more than just an rbtree) provides the same queuing mechanisms that the three or four lists heads do and manages to do it in one structure. The i_flushed_when provides the ability to have blocked inodes wait their turn so to speak.

Another motivation behind the rbtree patch is to unify the data structure that handles the priority and mechanism of how we write out the pages of the inodes. There are some ideas about introducing priority schemes for QOS and such in the future. I am not saying this patch is about making that happen, but the idea is to if possible unify the four stages of lists into a single structure to facilitate efforts like that.

1) Adding a datastructure to guarantee fairness when writing inodes to disk and simplify the code base.

When inodes are parked for writeback they are parked in the flush_tree. The flush tree is a data structure based on an rb tree.

Duplicate keys are handled by making a list in the tree for each key value. The order of how we choose the next inode to flush is decided by two fields. First the earliest dirtied_when value. If there are duplicate dirtied_when values then the earliest i_flush_gen value determines who gets flushed next.

The flush tree organizes the dirtied_when keys with the rb_tree. Any inodes with a duplicate dirtied_when value are link listed together. This link list is sorted by the inode's i_flush_gen. When both the dirtied_when and the i_flush_gen are identical the order in the linked list determines the order we flush the inodes.

2) Added an inode flag to allow inodes to be marked so that they are never written back to disk.

The motivation behind this change is several fold. The first is to insure fairness in the writeback algorithm. The second is to

deal with a bug where the writing to large files concurrently to smaller ones creates a situation where writeback cannot keep up with traffic and memory baloons until the we hit the threshold watermark. This can result in surprising long latency with respect to disk traffic. This latency can take minutes. The

flush tree fixes this issue and fixes several other minor issues with fairness also.

On Tue, Jan 15, 2008 at 12:09:21AM -0800, Michael Rubin wrote:
The main benefit of rbtree is possibly better support of future policies. Can you demonstrate an example?

Bugs can only be avoided by good understanding of all possible cases.)

The most tricky writeback issues could be starvation prevention between

- small/large files
- new/old files
- superblocks

Some kind of limit should be applied for each. They used to be:
- requeue to s_more_io whenever MAX_WRITEBACK_PAGES is reached this preempts big files

- refill s_io iif it is drained this prevents promotion of big/old files

- return from sync_sb_inodes() after one go of s_io

Michael, could you sort out and document the new starvation prevention schemes?

Introduce i_flush_gen to help restarting from the last inode? Well, it's not as simple as list_heads.

Quoted 5 lines

2) Added an inode flag to allow inodes to be marked so that they are never written back to disk.

The motivation behind this change is several fold. The first is to insure fairness in the writeback algorithm. The second is to

What do you mean by fairness?

Why cannot I_WRITEBACK_NEVER be in a decoupled standalone patch?

More details about the fixings, please?

Quoted 3 lines · Fengguang Wu

On Tue, Jan 15, 2008 at 12:09:21AM -0800, Michael Rubin wrote:
The main benefit of rbtree is possibly better support of future policies. Can you demonstrate an example?

These are ill-formed thoughts as of now on my end but the idea was that keeping one tree sorted via a scheme might be simpler than multiple list_heads.

Quoted 7 lines

The most tricky writeback issues could be starvation prevention between

- small/large files
- new/old files
- superblocks

So I have written tests and believe I have covered these issues. If you are concerned in specific on any and have a test case please let me know.

Quoted 3 lines

Some kind of limit should be applied for each. They used to be:
- requeue to s_more_io whenever MAX_WRITEBACK_PAGES is reached this preempts big files

The patch uses th same limit.

Quoted 2 lines

- refill s_io iif it is drained this prevents promotion of big/old files

Once a big file gets its first do_writepages it is moved behind the other smaller files via i_flushed_when. And the same in reverse for big vs old.

Quoted 2 lines

- return from sync_sb_inodes() after one go of s_io

I am not sure how this limit helps things out. Is this for superblock starvation? Can you elaborate?

Quoted 1 line

Michael, could you sort out and document the new starvation prevention schemes?

The basic idea behind the writeback algorithm to handle starvation. The over arching idea is that we want to preserve order of writeback based on when an inode was dirtied and also preserve the dirtied_when contents until the inode has been written back (partially or fully)

Every sync_sb_inodes we find the least recent inodes dirtied. To deal with large or small starvation we have a s_flush_gen for each iteration of sync_sb_inodes every time we issue a writeback we mark that the inode cannot be processed until the next s_flush_gen. This way we don't process one get to the rest since we keep pushing them into subsequent s_fush_gen's.

Let me know if you want more detail or structured responses.

Quoted 2 lines

Introduce i_flush_gen to help restarting from the last inode? Well, it's not as simple as list_heads.

Quoted 6 lines

Quoted 5 lines

2) Added an inode flag to allow inodes to be marked so that they are never written back to disk.

The motivation behind this change is several fold. The first is to insure fairness in the writeback algorithm. The second is to

Quoted 1 line

What do you mean by fairness?

So originally this comment was written when I was trying to fix a bug in 2.6.23. The one where we were starving large files from being flushed. There was a fairness issue where small files were being flushed but the large ones were just ballooning in memory.

Quoted 1 line

Why cannot I_WRITEBACK_NEVER be in a decoupled standalone patch?

The WRITEBACK_NEVER could be in a previous patch to the rbtree. But not a subsequent patch to the rbtree. The rbtree depends on the WRITEBACK_NEVER patch otherwise we run in to problems in generic_delete_inode. Now that you point it out I think I can split this patch into two patches and make the WRITEBACK_NEVER in the first one.

Suppose we want to grant longer expiration window for temp files, adding a new list named s_dirty_tmpfile would be a handy solution.

So the question is: should we need more than 3 QoS classes?

Quoted 3 lines · Fengguang Wu

Suppose we want to grant longer expiration window for temp files, adding a new list named s_dirty_tmpfile would be a handy solution.

How would the kernel know that a file is a tmp file?

Quoted 1 line

So the question is: should we need more than 3 QoS classes?

[just a random idea; i have not worked out all the implications]

Would it be possible to derive a writeback apriority from the ionice level of the process originating the IO? e.g. we have long standing problems that background jobs even when niced and can cause significant slow downs to foreground processes by starving IO and pushing out pages. ionice was supposed to help with that but in practice it does not seem to have helped too much and I suspect it needs more prioritization higher up the VM food chain. Adding such priorities to writeback would seem like a step in the right direction, although it would of course not solve the problem completely.

Quoted 2 lines · Fengguang Wu

Suppose we want to grant longer expiration window for temp files, adding a new list named s_dirty_tmpfile would be a handy solution.

How would the kernel know that a file is a tmp file?

Quoted 1 line

So the question is: should we need more than 3 QoS classes?

[just a random idea; i have not worked out all the implications]

Would it be possible to derive a writeback apriority from the ionice
level of the process originating the IO? e.g. we have long standing
problems that background jobs even when niced and can cause
significant slow downs to foreground processes by starving IO and pushing out pages. ionice was supposed to help with that but in practice it does not seem to have helped too much and I suspect
it needs more prioritization higher up the VM food chain. Adding
such priorities to writeback would seem like a step in the right
direction, although it would of course not solve the problem
completely.

-Andi
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Suppose we want to grant longer expiration window for temp files, adding a new list named s_dirty_tmpfile would be a handy solution.

So the question is: should we need more than 3 QoS classes?

Quoted 11 lines

Quoted 7 lines

The most tricky writeback issues could be starvation prevention between

- small/large files
- new/old files
- superblocks

So I have written tests and believe I have covered these issues. If you are concerned in specific on any and have a test case please let me know.

OK.

Quoted 6 lines

Quoted 3 lines

Some kind of limit should be applied for each. They used to be:
- requeue to s_more_io whenever MAX_WRITEBACK_PAGES is reached this preempts big files

The patch uses th same limit.

Quoted 6 lines

Quoted 2 lines

- refill s_io iif it is drained this prevents promotion of big/old files

Once a big file gets its first do_writepages it is moved behind the other smaller files via i_flushed_when. And the same in reverse for big vs old.

You mean i_flush_gen?

No, sync_sb_inodes() will abort on every MAX_WRITEBACK_PAGES, and s_flush_gen will be updated accordingly. Hence the sync will restart from big/old files.

Quoted 4 lines

Quoted 1 line

- return from sync_sb_inodes() after one go of s_io

I am not sure how this limit helps things out. Is this for superblock starvation? Can you elaborate?

We should have a way to go to next superblock even if new dirty inodes or pages are emerging fast in this superblock. Fill and drain s_io only once and then abort helps.

s_io is a stable and bounded working set in one go of superblock.

Basically you make one list_head in each rbtree node.
That list_head is recycled cyclic, and is an analog to the old fashioned s_dirty. We need to know 'where we are' and 'where it ends'. So an extra indicator must be introduced - i_flush_gen. It's awkward. We are simply repeating the aged list_heads' problem.

Quoted 3 lines · Fengguang Wu

On Thu, Jan 17, 2008 at 01:07:05PM -0800, Michael Rubin wrote:
Suppose we want to grant longer expiration window for temp files, adding a new list named s_dirty_tmpfile would be a handy solution.

When you mean tmp do you mean files that eventually get written to

disk? If not I would just use the WRITEBACK_NEVER. If so I am not sure if that feature is worth making a special case. It seems like the location based ideas may be more useful.

Quoted 8 lines

Quoted 6 lines

Quoted 2 lines

- refill s_io iif it is drained this prevents promotion of big/old files

Once a big file gets its first do_writepages it is moved behind the other smaller files via i_flushed_when. And the same in reverse for big vs old.

You mean i_flush_gen?

Yeah sorry. It was once called i_flush_when. (sheepish)

Quoted 3 lines

No, sync_sb_inodes() will abort on every MAX_WRITEBACK_PAGES, and s_flush_gen will be updated accordingly. Hence the sync will restart from big/old files.

If I understand you correctly I am not sure I agree. Here is what I think happens in the patch:

1) pull big inode off of flush tree
2) sync big inode
3) Hit MAX_WRITEBACK_PAGES
4) Re-insert big inode (without modifying the dirtied_when)
5) update the i_flush_gen on big inode and re-insert behind small inodes we have not synced yet.

In a subsequent sync_sb_inode we end up retrieving the small inode we had not serviced yet.

Quoted 8 lines

Quoted 4 lines

Quoted 1 line

- return from sync_sb_inodes() after one go of s_io

I am not sure how this limit helps things out. Is this for superblock starvation? Can you elaborate?

We should have a way to go to next superblock even if new dirty inodes or pages are emerging fast in this superblock. Fill and drain s_io only once and then abort helps.

Got it.

Quoted 1 line

s_io is a stable and bounded working set in one go of superblock.

Is this necessary with MAX_WRITEBACK_PAGES? It feels like a double limit.

Quoted 5 lines

Basically you make one list_head in each rbtree node.
That list_head is recycled cyclic, and is an analog to the old fashioned s_dirty. We need to know 'where we are' and 'where it ends'. So an extra indicator must be introduced - i_flush_gen. It's awkward. We are simply repeating the aged list_heads' problem.

To me they both feel a little awkward. I feel like the original problem in 2.6.23 led to a lot of examination which is bringing new possibilities to light.

BTW the issue that started me on this whole path (starving large files) was still present in 2.6.23-rc8 but now looks fixed in 2.6.24-rc3.
Still no idea about your changes in 2.6.24-rc6-mm1. I have given up trying to get that thing to boot.

Quoted 1 line

Michael, could you sort out and document the new starvation prevention schemes?

The basic idea behind the writeback algorithm to handle starvation. The over arching idea is that we want to preserve order of writeback based on when an inode was dirtied and also preserve the dirtied_when contents until the inode has been written back (partially or fully)

Every sync_sb_inodes we find the least recent inodes dirtied. To deal with large or small starvation we have a s_flush_gen for each iteration of sync_sb_inodes every time we issue a writeback we mark that the inode cannot be processed until the next s_flush_gen. This way we don't process one get to the rest since we keep pushing them into subsequent s_fush_gen's.

This seems suboptimal for large files. If you keep feeding in new least recently dirtied files, the large files will never get an unimpeded go at the disk and hence we'll struggle to get decent bandwidth under anything but pure large file write loads.

Switching inodes during writeback implies a seek to the new write location, while continuing to write the same inode has no seek penalty because the writeback is sequential. It follows from this that allowing larges file a disproportionate amount of data writeback is desirable.

Also, cycling rapidly through all the large files to write 4MB to each is going to cause us to spend time seeking rather than writing compared to cycling slower and writing 40MB from each large file at a time.

i.e. servicing one large file for 100ms is going to result in higher writeback throughput than servicing 10 large files for 10ms each because there's going to be less seeking and more writing done by the disks.

That is, think of large file writes like process scheduler batch jobs - bulk throughput is what matters, so the larger the time slice you give them the higher the throughput.

IMO, the sort of result we should be looking at is a writeback design that results in cycling somewhat like:

slice 1: iterate over small files
slice 2: flush large file 1
slice 3: iterate over small files
slice 4: flush large file 2
......
slice n-1: flush large file N
slice n: iterate over small files
slice n+1: flush large file N+1

So that we keep the disk busy with a relatively fair mix of small and large I/Os while both are necessary.

The higher the bandwidth of the device, the more frequently we need to be servicing the inodes with large amounts of dirty data to be written to maintain write throughput at a significant percentage of the device capability.

BTW, it needs to be recognised that if we are under memory pressure we can clean much more memory in a short period of time by writing out all the large files first. This would clearly benefit the system as a whole as we'd get the most pages available for reclaim as possible in a short a time as possible. The writeback algorithm should really have a mode that allows this sort of flush ordering to occur....

On Jan 17, 2008 9:01 PM, David Chinner <[email protected]> wrote:

First off thank you for the very detailed reply. This rocks and gives me much to think about.

Quoted 6 lines · Michael Rubin

This seems suboptimal for large files. If you keep feeding in new least recently dirtied files, the large files will never get an unimpeded go at the disk and hence we'll struggle to get decent bandwidth under anything but pure large file write loads.

You're right. I understand now. I just changed a dial on my tests, ran it and found pdflush not keeping up like it should. I need to address this.

Quoted 31 lines

Switching inodes during writeback implies a seek to the new write location, while continuing to write the same inode has no seek penalty because the writeback is sequential. It follows from this that allowing larges file a disproportionate amount of data writeback is desirable.

Also, cycling rapidly through all the large files to write 4MB to each is going to cause us to spend time seeking rather than writing compared to cycling slower and writing 40MB from each large file at a time.

i.e. servicing one large file for 100ms is going to result in higher writeback throughput than servicing 10 large files for 10ms each because there's going to be less seeking and more writing done by the disks.

That is, think of large file writes like process scheduler batch jobs - bulk throughput is what matters, so the larger the time slice you give them the higher the throughput.

IMO, the sort of result we should be looking at is a writeback design that results in cycling somewhat like:

slice 1: iterate over small files
slice 2: flush large file 1
slice 3: iterate over small files
slice 4: flush large file 2
......
slice n-1: flush large file N
slice n: iterate over small files
slice n+1: flush large file N+1

Quoted 2 lines

So that we keep the disk busy with a relatively fair mix of small and large I/Os while both are necessary.

I am getting where you are coming from. But if we are going to make changes to optimize for seeks maybe we need to be more aggressive in write back in how we organize both time and location. Right now AFAIK there is no attention to location in the writeback path.

Quoted 5 lines

The higher the bandwidth of the device, the more frequently we need to be servicing the inodes with large amounts of dirty data to be written to maintain write throughput at a significant percentage of the device capability.

Could you expand that to say it's not the inodes of large files but the ones with data that we can exploit locality?

Often large files are fragmented.

Would it make more sense to pursue cracking the inodes and grouping their blocks's locations? Or is this all overkill and should be handled at a lower level like the elevator?

At this point, I'd say it is best to leave it to the filesystem and the elevator to do their jobs properly.

Fairness is a tradeoff between seeks and bandwidth. Ideally, we want to spend 50% of the *disk* time servicing sequential writes and 50% of the time servicing seeky writes - that way neither get penalised unfairly by the other type of workload.

Switching inodes during writeback implies a seek to the new write location, while continuing to write the same inode has no seek penalty because the writeback is sequential. It follows from this that allowing larges file a disproportionate amount of data writeback is desirable.

Also, cycling rapidly through all the large files to write 4MB to each is going to cause us to spend time seeking rather than writing compared to cycling slower and writing 40MB from each large file at a time.

i.e. servicing one large file for 100ms is going to result in higher writeback throughput than servicing 10 large files for 10ms each because there's going to be less seeking and more writing done by the disks.

That is, think of large file writes like process scheduler batch jobs - bulk throughput is what matters, so the larger the time slice you give them the higher the throughput.

IMO, the sort of result we should be looking at is a writeback design that results in cycling somewhat like:

slice 1: iterate over small files
slice 2: flush large file 1
slice 3: iterate over small files
slice 4: flush large file 2
......
slice n-1: flush large file N
slice n: iterate over small files
slice n+1: flush large file N+1

So that we keep the disk busy with a relatively fair mix of small and large I/Os while both are necessary.

Furthermore, as disk bandwidth goes up, the relationship between large file and small file writes changes if we want to maintain writeback at a significant percentage of the maximum bandwidth of the drive (which is extremely desirable). So if we take a 4k page machine and a 1024page writeback slice, for different disks, we get a bandwidth slice in terms of disk seeks like:

slow disk: 20MB/s, 10ms seek (say a laptop drive)
- 4MB write takes 200ms, or equivalent of 10 seeks

normal disk: 60MB/s, 8ms seek (desktop)
- 4MB write takes 66ms, or equivalent of 8 seeks

fast disk: 120MB/s, 5ms seek (15krpm SAS)
- 4MB write takes 33ms, or equivalent of 6 seeks

small RAID5 lun: 200MB/s, 4ms seek
- 4MB write takes 20ms, or equivalent of 5 seeks

Large RAID5 lun: 1GB/s, 2ms seek
- 4MB write takes 4ms, or equivalent of 2 seeks

Put simply:

The higher the bandwidth of the device, the more frequently we need to be servicing the inodes with large amounts of dirty data to be written to maintain write throughput at a significant percentage of the device capability.

The writeback algorithm needs to take this into account for it to be able to scale effectively for high throughput devices.

BTW, it needs to be recognised that if we are under memory pressure we can clean much more memory in a short period of time by writing out all the large files first. This would clearly benefit the system as a whole as we'd get the most pages available for reclaim as possible in a short a time as possible. The writeback algorithm should really have a mode that allows this sort of flush ordering to occur....

Quoted 16 lines

That is, think of large file writes like process scheduler batch jobs - bulk throughput is what matters, so the larger the time slice you give them the higher the throughput.

IMO, the sort of result we should be looking at is a writeback design that results in cycling somewhat like:

slice 1: iterate over small files
slice 2: flush large file 1
slice 3: iterate over small files
slice 4: flush large file 2
......
slice n-1: flush large file N
slice n: iterate over small files
slice n+1: flush large file N+1

Quoted 2 lines

So that we keep the disk busy with a relatively fair mix of small and large I/Os while both are necessary.

If we can sync fast enough, the lower layer would be able to merge those 4MB requests.

Quoted 7 lines

Put simply:

The higher the bandwidth of the device, the more frequently we need to be servicing the inodes with large amounts of dirty data to be written to maintain write throughput at a significant percentage of the device capability.

Quoted 2 lines

The writeback algorithm needs to take this into account for it to be able to scale effectively for high throughput devices.

Slow queues go full first. Currently the writeback code will skip _and_ congestion_wait() for congested filesystems. The better policy is to congestion_wait() _after_ all other writable pages have been synced.