write bandwidth estimation and writeback fixes v2

Pass struct wb_writeback_work all the way down to writeback_sb_inodes(), and initialize the struct writeback_control there.

struct writeback_control is basically designed to control writeback of a single file, but we keep abuse it for writing multiple files in writeback_sb_inodes() and its callers.

It immediately clean things up, e.g. suddenly wbc.nr_to_write vs work->nr_pages starts to make sense, and instead of saving and restoring pages_skipped in writeback_sb_inodes it can always start with a clean zero value.

It also makes a neat IO pattern change: large dirty files are now written in the full 4MB writeback chunk size, rather than whatever remained quota in wbc->nr_to_write.

Acked-by Jan Kara <[email protected]>

Proposed-by Christoph Hellwig <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

fs/fs-writeback.c +8 -5

+			if (work->nr_pages <= 0)
+				break;
+		}
 	}
-	/* b_io is empty */
-	return 1;
+	return wrote;
 }
 
-static void __writeback_inodes_wb(struct bdi_writeback *wb,
-				  struct writeback_control *wbc)
+static long __writeback_inodes_wb(struct bdi_writeback *wb,
+				  struct wb_writeback_work *work)
 {
-	int ret = 0;
+	unsigned long start_time = jiffies;
+	long wrote = 0;
 
 	while (!list_empty(&wb->b_io)) {
 		struct inode *inode = wb_inode(wb->b_io.prev);

@@ -590,33 +650,37 @@ static void __writeback_inodes_wb(struct
 			requeue_io(inode, wb);
 			continue;
 		}

Just one minor nit:

fs/fs-writeback.c static int writeback_sb_inodes(struct su · line 631

Quoted 13 lines

fs/fs-writeback.c +7 -2

@@ -570,17 +622,25 @@ static int writeback_sb_inodes(struct su
 		iput(inode);
 		cond_resched();
 		spin_lock(&wb->list_lock);
-		if (wbc->nr_to_write <= 0)
-			return 1;
+		/*
+		 * bail out to wb_writeback() often enough to check
+		 * background threshold and other termination conditions.
+		 */
+		if (wrote) {
+			if (jiffies - start_time > HZ / 10UL)
+				break;

I guess this comparison should use time_before() macro - or maybe even
time_is_before_jiffies().

Quoted 28 lines

fs/fs-writeback.c +9 -6

+			if (work->nr_pages <= 0)
+				break;
+		}
 	}
-	/* b_io is empty */
-	return 1;
+	return wrote;
 }
 
-static void __writeback_inodes_wb(struct bdi_writeback *wb,
-				  struct writeback_control *wbc)
+static long __writeback_inodes_wb(struct bdi_writeback *wb,
+				  struct wb_writeback_work *work)
 {
-	int ret = 0;
+	unsigned long start_time = jiffies;
+	long wrote = 0;
 
 	while (!list_empty(&wb->b_io)) {
 		struct inode *inode = wb_inode(wb->b_io.prev);

@@ -590,33 +650,37 @@ static void __writeback_inodes_wb(struct
 			requeue_io(inode, wb);
 			continue;
 		}
-		ret = writeback_sb_inodes(sb, wb, wbc, false);
+		wrote += writeback_sb_inodes(sb, wb, work);
 		drop_super(sb);
 

fs/fs-writeback.c static void __writeback_inodes_wb(struct · line 659

Quoted 6 lines

fs/fs-writeback.c +4 -2

-		if (ret)
-			break;
+		/* refer to the same tests at the end of writeback_sb_inodes */
+		if (wrote) {
+			if (jiffies - start_time > HZ / 10UL)
+				break;

And the same here.

The estimation value will start from 100MB/s and adapt to the real bandwidth in seconds.

It tries to update the bandwidth only when disk is fully utilized. Any inactive period of more than one second will be skipped.

The estimated bandwidth will be reflecting how fast the device can writeout when _fully utilized_, and won't drop to 0 when it goes idle. The value will remain constant at disk idle time. At busy write time, if not considering fluctuations, it will also remain high unless be knocked down by possible concurrent reads that compete for the disk time and bandwidth with async writes.

The estimation is not done purely in the flusher because there is no guarantee for write_cache_pages() to return timely to update bandwidth.

The bdi->avg_write_bandwidth smoothing is very effective for filtering out sudden spikes, however may be a little biased in long term.

The overheads are low because the bdi bandwidth update only occurs at 200ms intervals.

The 200ms update interval is suitable, becuase it's not possible to get the real bandwidth for the instance at all, due to large fluctuations.

The NFS commits can be as large as seconds worth of data. One XFS completion may be as large as half second worth of data if we are going to increase the write chunk to half second worth of data. In ext4, fluctuations with time period of around 5 seconds is observed. And there is another pattern of irregular periods of up to 20 seconds on SSD tests.

That's why we are not only doing the estimation at 200ms intervals, but also averaging them over a period of 3 seconds and then go further to do another level of smoothing in avg_write_bandwidth.

fs/fs-writeback.c +13 -0

@@ -693,6 +693,16 @@ static inline bool over_bground_thresh(v
 }
 
 /*
+ * Called under wb->list_lock. If there are multiple wb per bdi,
+ * only the flusher working on the first wb should do it.
+ */
+static void wb_update_bandwidth(struct bdi_writeback *wb,
+				unsigned long start_time)
+{
+	__bdi_update_bandwidth(wb->bdi, start_time);
+}
+
+/*
  * Explicit flushing or periodic writeback of "old" data.
  *
  * Define "old": the first time one of an inode's pages is dirtied, we mark the

@@ -710,6 +720,7 @@ static inline bool over_bground_thresh(v
 static long wb_writeback(struct bdi_writeback *wb,
 			 struct wb_writeback_work *work)
 {
+	unsigned long wb_start = jiffies;
 	long nr_pages = work->nr_pages;
 	unsigned long oldest_jif;
 	struct inode *inode;

@@ -758,6 +769,8 @@ static long wb_writeback(struct bdi_writ
 			progress = __writeback_inodes_wb(wb, work);
 		trace_writeback_written(wb->bdi, work);
 
+		wb_update_bandwidth(wb, wb_start);
+
 		/*
 		 * Did we write something? Try for more
 		 *

mm/page-writeback.c +7 -0

+static void bdi_update_write_bandwidth(struct backing_dev_info *bdi,
+				       unsigned long elapsed,
+				       unsigned long written)
+{
+	const unsigned long period = roundup_pow_of_two(3 * HZ);
+	unsigned long avg = bdi->avg_write_bandwidth;
+	unsigned long old = bdi->write_bandwidth;

mm/page-writeback.c +27 -0

+	bw += (u64)bdi->write_bandwidth * (period - elapsed);
+	cur = bw >> ilog2(period);
+
+	/*
+	 * one more level of smoothing, for filtering out sudden spikes
+	 */
+	if (avg > old && old > cur)
+		avg -= (avg - old) >> 3;
+
+	if (avg < old && old < cur)
+		avg += (old - avg) >> 3;
+
+	bdi->write_bandwidth = cur;
+	bdi->avg_write_bandwidth = avg;
+}
+
+void __bdi_update_bandwidth(struct backing_dev_info *bdi,
+			    unsigned long start_time)
+{
+	unsigned long now = jiffies;
+	unsigned long elapsed = now - bdi->bw_time_stamp;
+	unsigned long written;
+
+	/*
+	 * rate-limit, only update once every 200ms.
+	 */
+	if (elapsed < MAX_PAUSE)

mm/page-writeback.c +4 -0

+
+	bdi_update_write_bandwidth(bdi, elapsed, written);
+
+snapshot:

mm/page-writeback.c +6 -0

+		__bdi_update_bandwidth(bdi, start_time);
+		spin_unlock(&bdi->wb.list_lock);
+	}
+}
+
 /*
  * balance_dirty_pages() must be called by processes which are generating dirty
  * data.  It looks at the number of dirty pages in the machine and will force

@@ -491,6 +569,7 @@ static void balance_dirty_pages(struct a
 	unsigned long pause = 1;
 	bool dirty_exceeded = false;
 	struct backing_dev_info *bdi = mapping->backing_dev_info;
+	unsigned long start_time = jiffies;
 
 	for (;;) {
 		nr_reclaimable = global_page_state(NR_FILE_DIRTY) +

Hello,

Quoted 31 lines · Wu Fengguang

The estimation value will start from 100MB/s and adapt to the real bandwidth in seconds.

It tries to update the bandwidth only when disk is fully utilized. Any inactive period of more than one second will be skipped.

The estimated bandwidth will be reflecting how fast the device can writeout when _fully utilized_, and won't drop to 0 when it goes idle. The value will remain constant at disk idle time. At busy write time, if not considering fluctuations, it will also remain high unless be knocked down by possible concurrent reads that compete for the disk time and bandwidth with async writes.

The estimation is not done purely in the flusher because there is no guarantee for write_cache_pages() to return timely to update bandwidth.

The bdi->avg_write_bandwidth smoothing is very effective for filtering out sudden spikes, however may be a little biased in long term.

The overheads are low because the bdi bandwidth update only occurs at 200ms intervals.

The 200ms update interval is suitable, becuase it's not possible to get the real bandwidth for the instance at all, due to large fluctuations.

The NFS commits can be as large as seconds worth of data. One XFS completion may be as large as half second worth of data if we are going to increase the write chunk to half second worth of data. In ext4, fluctuations with time period of around 5 seconds is observed. And there is another pattern of irregular periods of up to 20 seconds on SSD tests.

Quoted 3 lines

That's why we are not only doing the estimation at 200ms intervals, but also averaging them over a period of 3 seconds and then go further to do another level of smoothing in avg_write_bandwidth.

I was thinking about your formulas and also observing how it behaves when
writeback happens while the disk is loaded with other load as well (e.g. grep -r of a large tree or cp from another partition).

I agree that some kind of averaging is needed. But how we average depends on what do we need the number for. My thoughts were that there is not such a thing as *the* write bandwidth since that depends on the background load on the disk and also type of writes we do (sequential, random) as you noted as well. What writeback needs to estimate in fact is "how fast can we write this bulk of data?". Since we should ultimately size dirty limits and other writeback tunables so that the bulk of data can be written in order of seconds (but maybe much slower because of background load) I agree with your first choice that we should measure written pages in a window of several seconds - so your choice of 3 seconds is OK - but this number should have a reasoning attached to it in a comment (something like my elaborate above ;)

Now to your second level of smoothing - is it really useful? We already

average over several second window so that should really eliminate big spikes comming from bumpy IO completion from storage (NFS might be a separate question but we talked about that already). Your second level of smoothing just spreads the window even further but if you find that necessary, why not make the window larger in the first place? Also my

observations of avg-bandwidth and bandwidth when there's some background read load (e.g. from grep) shows that in this case both bandwidth and avg-bandwidth fluctuate +-10%.

Finally, as I reasoned above, we are
interested in how much we can write in coming say 2 seconds so I don't see a big point smoothing the value too much (I'd even say it's undesirable). What do you think?

Some code related comments are below:

Quoted 40 lines

fs/fs-writeback.c +13 -0

@@ -693,6 +693,16 @@ static inline bool over_bground_thresh(v
 }
 
 /*
+ * Called under wb->list_lock. If there are multiple wb per bdi,
+ * only the flusher working on the first wb should do it.
+ */
+static void wb_update_bandwidth(struct bdi_writeback *wb,
+				unsigned long start_time)
+{
+	__bdi_update_bandwidth(wb->bdi, start_time);
+}
+
+/*
  * Explicit flushing or periodic writeback of "old" data.
  *
  * Define "old": the first time one of an inode's pages is dirtied, we mark the

@@ -710,6 +720,7 @@ static inline bool over_bground_thresh(v
 static long wb_writeback(struct bdi_writeback *wb,
 			 struct wb_writeback_work *work)
 {
+	unsigned long wb_start = jiffies;
 	long nr_pages = work->nr_pages;
 	unsigned long oldest_jif;
 	struct inode *inode;

@@ -758,6 +769,8 @@ static long wb_writeback(struct bdi_writ
 			progress = __writeback_inodes_wb(wb, work);
 		trace_writeback_written(wb->bdi, work);
 
+		wb_update_bandwidth(wb, wb_start);
+
 		/*
 		 * Did we write something? Try for more
 		 *

include/linux/backing-dev.h +0 -0

@@ -73,6 +73,11 @@ struct backing_dev_info {
 

include/linux/backing-dev.h struct backing_dev_info { · line 80

Quoted 7 lines

include/linux/backing-dev.h +5 -0

 	struct percpu_counter bdi_stat[NR_BDI_STAT_ITEMS];
 
+	unsigned long bw_time_stamp;
+	unsigned long written_stamp;
+	unsigned long write_bandwidth;
+	unsigned long avg_write_bandwidth;
+

Some comments on what these are would be useful.

Quoted 8 lines

include/linux/backing-dev.h +0 -0

 	struct prop_local_percpu completions;
 	int dirty_exceeded;
 

mm/page-writeback.c +0 -0

@@ -37,6 +37,11 @@
 #include <trace/events/writeback.h>
 

mm/page-writeback.c line 42

Quoted 4 lines

mm/page-writeback.c +3 -0

 /*
+ * Sleep at most 200ms at a time in balance_dirty_pages().
+ */
+#define MAX_PAUSE	max(HZ/5, 1)

You use this for ratelimiting updates of bdi bandwidth. So we should
really have a separate (and properly commented) constant for it.

Quoted 11 lines

mm/page-writeback.c +11 -0

+static void bdi_update_write_bandwidth(struct backing_dev_info *bdi,
+				       unsigned long elapsed,
+				       unsigned long written)
+{
+	const unsigned long period = roundup_pow_of_two(3 * HZ);
+	unsigned long avg = bdi->avg_write_bandwidth;
+	unsigned long old = bdi->write_bandwidth;
+	unsigned long cur;
+	u64 bw;
+
+	bw = written - bdi->written_stamp;

mm/page-writeback.c unsigned long bdi_dirty_limit(struct bac · line 496

Quoted 6 lines

mm/page-writeback.c +6 -0

+	bw *= HZ;
+	if (unlikely(elapsed > period / 2)) {
+		do_div(bw, elapsed);
+		elapsed = period / 2;
+		bw *= elapsed;
+	}

What is the rationale behind this condition? Why cannot we just use
written/elapsed when we have long enough period? Have you observed some

problems with it (I estimate bandwidth in my patches like:
static void update_bdi_throughput(struct backing_dev_info *bdi,
unsigned long written, unsigned long time)

{
       unsigned int deltams = jiffies_to_msecs(time - bdi->start_jiffies);

       written -= bdi->start_written;
       if (deltams > WINDOW_MS) {
               /* Add 1 to avoid 0 result */
               bdi->pages_per_s = 1 + ((u64)written) * MSEC_PER_SEC / deltams;
               return;
       }
       bdi->pages_per_s = 1 +
               (((u64)bdi->pages_per_s) * (WINDOW_MS - deltams) +
                ((u64)written) * MSEC_PER_SEC) / WINDOW_MS;
}

and I didn't observe any problems with it. Plus you need some comment explaining how you compute the throughput. I have something like:
/*
* When the throughput is computed, we consider an imaginary WINDOW_MS
* miliseconds long window. In this window, we know that it took 'deltams'
* miliseconds to write 'written' pages and for the rest of the window we
* assume number of pages corresponding to the throughput we previously
* computed to have been written. Thus we obtain total number of pages
* written in the imaginary window and from it new throughput. */

Quoted 33 lines

mm/page-writeback.c +33 -0

+	bw += (u64)bdi->write_bandwidth * (period - elapsed);
+	cur = bw >> ilog2(period);
+
+	/*
+	 * one more level of smoothing, for filtering out sudden spikes
+	 */
+	if (avg > old && old > cur)
+		avg -= (avg - old) >> 3;
+
+	if (avg < old && old < cur)
+		avg += (old - avg) >> 3;
+
+	bdi->write_bandwidth = cur;
+	bdi->avg_write_bandwidth = avg;
+}
+
+void __bdi_update_bandwidth(struct backing_dev_info *bdi,
+			    unsigned long start_time)
+{
+	unsigned long now = jiffies;
+	unsigned long elapsed = now - bdi->bw_time_stamp;
+	unsigned long written;
+
+	/*
+	 * rate-limit, only update once every 200ms.
+	 */
+	if (elapsed < MAX_PAUSE)
+		return;
+
+	written = percpu_counter_read(&bdi->bdi_stat[BDI_WRITTEN]);
+
+	/*
+	 * Skip quiet periods when disk bandwidth is under-utilized.

mm/page-writeback.c unsigned long bdi_dirty_limit(struct bac · line 533

Quoted 4 lines

mm/page-writeback.c +4 -0

+	 * (at least 1s idle time between two flusher runs)
+	 */
+	if (elapsed > HZ && time_before(bdi->bw_time_stamp, start_time))
+		goto snapshot;

Cannot we just explicitely stamp the written_stamp and bw_time_stamp at
the beginning of wb_writeback and be done with it? We wouldn't have to pass the time stamps, keep them in wb_writeback() and balance_dirty_pages() etc.

Quoted 9 lines

mm/page-writeback.c +9 -0

+
+	bdi_update_write_bandwidth(bdi, elapsed, written);
+
+snapshot:
+	bdi->written_stamp = written;
+	bdi->bw_time_stamp = now;
+}
+
+static void bdi_update_bandwidth(struct backing_dev_info *bdi,

mm/page-writeback.c unsigned long bdi_dirty_limit(struct bac · line 547

Quoted 5 lines

mm/page-writeback.c +5 -0

+				 unsigned long start_time)
+{
+	if (jiffies - bdi->bw_time_stamp <= MAX_PAUSE + MAX_PAUSE / 10)
+		return;
+	if (spin_trylock(&bdi->wb.list_lock)) {

I'm not sure this is a good idea - list_lock could be quite busy which
would possibly quite delay updates of bandwidth. I'd just unconditionally take it.

Quoted 18 lines

mm/page-writeback.c +6 -0

+		__bdi_update_bandwidth(bdi, start_time);
+		spin_unlock(&bdi->wb.list_lock);
+	}
+}
+
 /*
  * balance_dirty_pages() must be called by processes which are generating dirty
  * data.  It looks at the number of dirty pages in the machine and will force

@@ -491,6 +569,7 @@ static void balance_dirty_pages(struct a
 	unsigned long pause = 1;
 	bool dirty_exceeded = false;
 	struct backing_dev_info *bdi = mapping->backing_dev_info;
+	unsigned long start_time = jiffies;
 
 	for (;;) {
 		nr_reclaimable = global_page_state(NR_FILE_DIRTY) +

mm/page-writeback.c static void balance_dirty_pages(struct a · line 631

Quoted 8 lines

mm/page-writeback.c +2 -0

@@ -545,6 +624,8 @@ static void balance_dirty_pages(struct a
 		if (!bdi->dirty_exceeded)
 			bdi->dirty_exceeded = 1;
 
+		bdi_update_bandwidth(bdi, start_time);
+
 		/* Note: nr_reclaimable denotes nr_dirty + nr_unstable.
 		 * Unstable writes are a feature of certain networked
 		 * filesystems (i.e. NFS) in which data may have been

Honza

Signature · 2 lines

Jan Kara <[email protected]>
SUSE Labs, CR

Quoted 39 lines · Jan Kara

Quoted 31 lines · Wu Fengguang

The estimation value will start from 100MB/s and adapt to the real bandwidth in seconds.

It tries to update the bandwidth only when disk is fully utilized. Any inactive period of more than one second will be skipped.

The estimated bandwidth will be reflecting how fast the device can writeout when _fully utilized_, and won't drop to 0 when it goes idle. The value will remain constant at disk idle time. At busy write time, if not considering fluctuations, it will also remain high unless be knocked down by possible concurrent reads that compete for the disk time and bandwidth with async writes.

The estimation is not done purely in the flusher because there is no guarantee for write_cache_pages() to return timely to update bandwidth.

The bdi->avg_write_bandwidth smoothing is very effective for filtering out sudden spikes, however may be a little biased in long term.

The overheads are low because the bdi bandwidth update only occurs at 200ms intervals.

The 200ms update interval is suitable, becuase it's not possible to get the real bandwidth for the instance at all, due to large fluctuations.

The NFS commits can be as large as seconds worth of data. One XFS completion may be as large as half second worth of data if we are going to increase the write chunk to half second worth of data. In ext4, fluctuations with time period of around 5 seconds is observed. And there is another pattern of irregular periods of up to 20 seconds on SSD tests.

Quoted 3 lines

That's why we are not only doing the estimation at 200ms intervals, but also averaging them over a period of 3 seconds and then go further to do another level of smoothing in avg_write_bandwidth.

I was thinking about your formulas and also observing how it behaves when
writeback happens while the disk is loaded with other load as well (e.g. grep -r of a large tree or cp from another partition).

Quoted 12 lines

I agree that some kind of averaging is needed. But how we average depends on what do we need the number for. My thoughts were that there is not such a thing as *the* write bandwidth since that depends on the background load on the disk and also type of writes we do (sequential, random) as you noted as well. What writeback needs to estimate in fact is "how fast can we write this bulk of data?". Since we should ultimately size dirty limits and other writeback tunables so that the bulk of data can be written in order of seconds (but maybe much slower because of background load) I agree with your first choice that we should measure written pages in a window of several seconds - so your choice of 3 seconds is OK - but this number should have a reasoning attached to it in a comment (something like my elaborate above ;)

Agree totally and thanks for the reasoning in great details ;)

Quoted 1 line

Now to your second level of smoothing - is it really useful? We already

It's useful for filtering out sudden disturbances. Oh I forgot to show the SSD case which see sudden drops of throughput:

http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/dirty-throttling-v6/1SSD-64G/ext4-1dd-1M-64p-64288M-20%25-2.6.38-rc6-dt6+-2011-03-01-16-19/balance_dirty_pages-bandwidth.png

It's also very effective for XFS (see the below graph).

Quoted 5 lines

average over several second window so that should really eliminate big spikes comming from bumpy IO completion from storage (NFS might be a separate question but we talked about that already). Your second level of smoothing just spreads the window even further but if you find that necessary, why not make the window larger in the first place? Also my

Because they are two different type of smoothing. I employed the same smoothing as avg_write_bandwidth for bdi_dirty, where I wrote this comment to illustrate its unique usefulness:

(quoted diff) +23 -0

+       /*
+        * This ...
+        * ... is most effective on XFS,
+        * whose pattern is
+        *                                                             .
+        *      [.] dirty       [-] avg                       .       .
+        *                                                   .       .
+        *              .         .         .         .     .       .
+        *      ---------------------------------------    .       .
+        *            .         .         .         .     .       .
+        *           .         .         .         .     .       .
+        *          .         .         .         .     .       .
+        *         .         .         .         .     .       .
+        *        .         .         .         .
+        *       .         .         .         .      (fluctuated)
+        *      .         .         .         .
+        *     .         .         .         .
+        *
+        * @avg will remain flat at the cost of being biased towards high. In
+        * practice the error tend to be much smaller: thanks to more coarse
+        * grained fluctuations, @avg becomes the real average number for the
+        * last two rising lines of @dirty.
+        */

Quoted 4 lines

observations of avg-bandwidth and bandwidth when there's some background read load (e.g. from grep) shows that in this case both bandwidth and avg-bandwidth fluctuate +-10%.

You can more easily see their fluctuate ranges in my graphs :) For example,

(compare the YELLOW line to the RED dots)

NFS
http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/dirty-throttling-v6/NFS/nfs-1dd-1M-8p-2945M-20%25-2.6.38-rc6-dt6+-2011-02-22-21-09/balance_dirty_pages-bandwidth.png

XFS
http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/dirty-throttling-v6/4G/xfs-1dd-1M-8p-3927M-20%25-2.6.38-rc6-dt6+-2011-02-27-22-58/balance_dirty_pages-bandwidth.png

ext4
http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/dirty-throttling-v8/3G/ext4-1dd-4k-8p-2948M-20:10-3.0.0-rc2-next-20110610+-2011-06-12.21:57/balance_dirty_pages-bandwidth.png

Quoted 4 lines

Finally, as I reasoned above, we are
interested in how much we can write in coming say 2 seconds so I don't see a big point smoothing the value too much (I'd even say it's undesirable). What do you think?

Yeah we typically get 20% ->write_bandwidth fluctuation range in the above graphs (except for NFS), which seems reasonably good for guiding the write chunk size.

However I would still like to favor a more stable value and ->avg_write_bandwidth looks appealing with much smaller 3%-10% ranges in steady state. Because the fluctuations of estimated write bandwidth will directly become the fluctuations in write chunk sizes over time as well as the application throttled write speed in future IO-less balance_dirty_pages().

Oh I thought the code is clear enough because it's the standard running average technique... or let's write down the before-simplified formula?

/*
* bw = written * HZ / elapsed
*
* bw * elapsed + write_bandwidth * (period - elapsed)
* write_bandwidth = ---------------------------------------------------
* period
*/

Quoted 33 lines

Quoted 33 lines

mm/page-writeback.c +33 -0

+	bw += (u64)bdi->write_bandwidth * (period - elapsed);
+	cur = bw >> ilog2(period);
+
+	/*
+	 * one more level of smoothing, for filtering out sudden spikes
+	 */
+	if (avg > old && old > cur)
+		avg -= (avg - old) >> 3;
+
+	if (avg < old && old < cur)
+		avg += (old - avg) >> 3;
+
+	bdi->write_bandwidth = cur;
+	bdi->avg_write_bandwidth = avg;
+}
+
+void __bdi_update_bandwidth(struct backing_dev_info *bdi,
+			    unsigned long start_time)
+{
+	unsigned long now = jiffies;
+	unsigned long elapsed = now - bdi->bw_time_stamp;
+	unsigned long written;
+
+	/*
+	 * rate-limit, only update once every 200ms.
+	 */
+	if (elapsed < MAX_PAUSE)
+		return;
+
+	written = percpu_counter_read(&bdi->bdi_stat[BDI_WRITTEN]);
+
+	/*
+	 * Skip quiet periods when disk bandwidth is under-utilized.

Quoted 8 lines

mm/page-writeback.c unsigned long bdi_dirty_limit(struct bac · line 533

Quoted 4 lines

mm/page-writeback.c +4 -0

+	 * (at least 1s idle time between two flusher runs)
+	 */
+	if (elapsed > HZ && time_before(bdi->bw_time_stamp, start_time))
+		goto snapshot;

Cannot we just explicitely stamp the written_stamp and bw_time_stamp at
the beginning of wb_writeback and be done with it? We wouldn't have to pass the time stamps, keep them in wb_writeback() and balance_dirty_pages() etc.

I'm afraid that stamping may unnecessarily disturb/invalidate valid accounting periods. For example, if the flusher keeps working on tiny works, it will effectively disable bandwidth updates.

Hi Fengguang,

Quoted 62 lines · Wu Fengguang

Quoted 39 lines · Jan Kara

Quoted 31 lines · Wu Fengguang

The estimation value will start from 100MB/s and adapt to the real bandwidth in seconds.

It tries to update the bandwidth only when disk is fully utilized. Any inactive period of more than one second will be skipped.

The estimated bandwidth will be reflecting how fast the device can writeout when _fully utilized_, and won't drop to 0 when it goes idle. The value will remain constant at disk idle time. At busy write time, if not considering fluctuations, it will also remain high unless be knocked down by possible concurrent reads that compete for the disk time and bandwidth with async writes.

The estimation is not done purely in the flusher because there is no guarantee for write_cache_pages() to return timely to update bandwidth.

The bdi->avg_write_bandwidth smoothing is very effective for filtering out sudden spikes, however may be a little biased in long term.

The overheads are low because the bdi bandwidth update only occurs at 200ms intervals.

The 200ms update interval is suitable, becuase it's not possible to get the real bandwidth for the instance at all, due to large fluctuations.

The NFS commits can be as large as seconds worth of data. One XFS completion may be as large as half second worth of data if we are going to increase the write chunk to half second worth of data. In ext4, fluctuations with time period of around 5 seconds is observed. And there is another pattern of irregular periods of up to 20 seconds on SSD tests.

Quoted 3 lines

That's why we are not only doing the estimation at 200ms intervals, but also averaging them over a period of 3 seconds and then go further to do another level of smoothing in avg_write_bandwidth.

I was thinking about your formulas and also observing how it behaves when
writeback happens while the disk is loaded with other load as well (e.g. grep -r of a large tree or cp from another partition).

Quoted 12 lines

I agree that some kind of averaging is needed. But how we average depends on what do we need the number for. My thoughts were that there is not such a thing as *the* write bandwidth since that depends on the background load on the disk and also type of writes we do (sequential, random) as you noted as well. What writeback needs to estimate in fact is "how fast can we write this bulk of data?". Since we should ultimately size dirty limits and other writeback tunables so that the bulk of data can be written in order of seconds (but maybe much slower because of background load) I agree with your first choice that we should measure written pages in a window of several seconds - so your choice of 3 seconds is OK - but this number should have a reasoning attached to it in a comment (something like my elaborate above ;)

Agree totally and thanks for the reasoning in great details ;)

Quoted 1 line

Now to your second level of smoothing - is it really useful? We already

It's useful for filtering out sudden disturbances. Oh I forgot to show the SSD case which see sudden drops of throughput:

http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/dirty-throttling-v6/1SSD-64G/ext4-1dd-1M-64p-64288M-20%25-2.6.38-rc6-dt6+-2011-03-01-16-19/balance_dirty_pages-bandwidth.png

Quoted 1 line

It's also very effective for XFS (see the below graph).

I see. I think I finally understood what your second level of smoothing
does. When e.g. IO is stalled for some time and then is getting up to speed for a while your second level of smoothing erases this spike when the stall is shorter than twice update time of the bandwidth (if it is more, bandwidth will drop two times in a row and you start decreasing your smoothed bandwidth as well).

Quoted 6 lines

Quoted 5 lines

average over several second window so that should really eliminate big spikes comming from bumpy IO completion from storage (NFS might be a separate question but we talked about that already). Your second level of smoothing just spreads the window even further but if you find that necessary, why not make the window larger in the first place? Also my

Quoted 3 lines

Because they are two different type of smoothing. I employed the same smoothing as avg_write_bandwidth for bdi_dirty, where I wrote this comment to illustrate its unique usefulness:

But is your second level of smoothing really that much different from
making the window over which we average larger? E.g. if you have 3s window and the IO stalls 1s, you will see 33% variation in computed bandwidth. But if you had 10s window, you would see only 10% variation.

To get some real numbers I've run simple dd on XFS filesystem and plotted basic computed bandwidth and smoothed bandwidth with 3s and 10s window. The results are at:
http://beta.suse.com/private/jack/bandwidth-tests/fengguang-dd-write.png
http://beta.suse.com/private/jack/bandwidth-tests/fengguang-dd-write-10s.png

You can see that with 10s window basic bandwidth is (unsuprisingly) quite closer to your smoothed bandwidth than with 3s window. Of course if the variations in throughput are longer in time, the throughput will oscilate more even with larger window. But that is the case with your smoothed bandwidth as well and it is in fact desirable because as soon as amount of

data we can write per second is lower for several seconds, we have to really consider this and change writeback tunables accordingly. To demostrate the changes in smoothed bandwidth, I've run a test where we are writing lots of 10MB files to the filesystem and in paralel we read randomly 1-1000MB from the filesystem and then sleep for 1-15s. The results (with 3s and 10s window) are at:
http://beta.suse.com/private/jack/bandwidth-tests/fengguang-dd-read-dd-write.png
http://beta.suse.com/private/jack/bandwidth-tests/fengguang-dd-read-dd-write-10s.png

You can see that both basic and smoothed bandwidth are not that much different even with 3s window and with 10s window the differences are negligible I'd say.

So both from my understanding and my experiments, I'd say that the basic computation of bandwidth should be enough and if you want to be on a smoother side, you can just increase the window size and you will get rather similar results as with your second level of smoothing.

The estimation value will start from 100MB/s and adapt to the real bandwidth in seconds.

It tries to update the bandwidth only when disk is fully utilized. Any inactive period of more than one second will be skipped.

The estimated bandwidth will be reflecting how fast the device can writeout when _fully utilized_, and won't drop to 0 when it goes idle. The value will remain constant at disk idle time. At busy write time, if not considering fluctuations, it will also remain high unless be knocked down by possible concurrent reads that compete for the disk time and bandwidth with async writes.

The estimation is not done purely in the flusher because there is no guarantee for write_cache_pages() to return timely to update bandwidth.

The bdi->avg_write_bandwidth smoothing is very effective for filtering out sudden spikes, however may be a little biased in long term.

The overheads are low because the bdi bandwidth update only occurs at 200ms intervals.

The 200ms update interval is suitable, becuase it's not possible to get the real bandwidth for the instance at all, due to large fluctuations.

The NFS commits can be as large as seconds worth of data. One XFS completion may be as large as half second worth of data if we are going to increase the write chunk to half second worth of data. In ext4, fluctuations with time period of around 5 seconds is observed. And there is another pattern of irregular periods of up to 20 seconds on SSD tests.

That's why we are not only doing the estimation at 200ms intervals, but also averaging them over a period of 3 seconds and then go further to do another level of smoothing in avg_write_bandwidth.

CC Li Shaohua <[email protected]>

CC Peter Zijlstra <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

---

mm/page-writeback.c +8 -0

+		return;
+	if (spin_trylock(&bdi->wb.list_lock)) {
+		__bdi_update_bandwidth(bdi, start_time);
+		spin_unlock(&bdi->wb.list_lock);
+	}
+}
+
 /*
  * balance_dirty_pages() must be called by processes which are generating dirty
  * data.  It looks at the number of dirty pages in the machine and will force

@@ -491,6 +569,7 @@ static void balance_dirty_pages(struct a
 	unsigned long pause = 1;
 	bool dirty_exceeded = false;
 	struct backing_dev_info *bdi = mapping->backing_dev_info;
+	unsigned long start_time = jiffies;
 
 	for (;;) {
 		nr_reclaimable = global_page_state(NR_FILE_DIRTY) +

Another small time nitpick.

mm/page-writeback.c unsigned long bdi_dirty_limit(struct bac · line 545

Quoted 5 lines

mm/page-writeback.c +5 -0

+
+static void bdi_update_bandwidth(struct backing_dev_info *bdi,
+				 unsigned long start_time)
+{
+	if (jiffies - bdi->bw_time_stamp <= MAX_PAUSE + MAX_PAUSE / 10)

	if (time_is_after_eq_jiffies(bdi->bw_time_stamp + MAX_PAUSE +
						MAX_PAUSE / 10)

The estimation value will start from 100MB/s and adapt to the real bandwidth in seconds.

It tries to update the bandwidth only when disk is fully utilized. Any inactive period of more than one second will be skipped.

The estimated bandwidth will be reflecting how fast the device can writeout when _fully utilized_, and won't drop to 0 when it goes idle. The value will remain constant at disk idle time. At busy write time, if not considering fluctuations, it will also remain high unless be knocked down by possible concurrent reads that compete for the disk time and bandwidth with async writes.

The estimation is not done purely in the flusher because there is no guarantee for write_cache_pages() to return timely to update bandwidth.

The bdi->avg_write_bandwidth smoothing is very effective for filtering out sudden spikes, however may be a little biased in long term.

The overheads are low because the bdi bandwidth update only occurs at 200ms intervals.

The 200ms update interval is suitable, becuase it's not possible to get the real bandwidth for the instance at all, due to large fluctuations.

The NFS commits can be as large as seconds worth of data. One XFS completion may be as large as half second worth of data if we are going to increase the write chunk to half second worth of data. In ext4, fluctuations with time period of around 5 seconds is observed. And there is another pattern of irregular periods of up to 20 seconds on SSD tests.

That's why we are not only doing the estimation at 200ms intervals, but also averaging them over a period of 3 seconds and then go further to do another level of smoothing in avg_write_bandwidth.

Quoted 31 lines · Wu Fengguang

The estimation value will start from 100MB/s and adapt to the real bandwidth in seconds.

It tries to update the bandwidth only when disk is fully utilized. Any inactive period of more than one second will be skipped.

The estimated bandwidth will be reflecting how fast the device can writeout when _fully utilized_, and won't drop to 0 when it goes idle. The value will remain constant at disk idle time. At busy write time, if not considering fluctuations, it will also remain high unless be knocked down by possible concurrent reads that compete for the disk time and bandwidth with async writes.

The estimation is not done purely in the flusher because there is no guarantee for write_cache_pages() to return timely to update bandwidth.

The bdi->avg_write_bandwidth smoothing is very effective for filtering out sudden spikes, however may be a little biased in long term.

The overheads are low because the bdi bandwidth update only occurs at 200ms intervals.

The 200ms update interval is suitable, becuase it's not possible to get the real bandwidth for the instance at all, due to large fluctuations.

The NFS commits can be as large as seconds worth of data. One XFS completion may be as large as half second worth of data if we are going to increase the write chunk to half second worth of data. In ext4, fluctuations with time period of around 5 seconds is observed. And there is another pattern of irregular periods of up to 20 seconds on SSD tests.

Quoted 3 lines

That's why we are not only doing the estimation at 200ms intervals, but also averaging them over a period of 3 seconds and then go further to do another level of smoothing in avg_write_bandwidth.

What IO scheduler have you used for testing?

CFQ now a days almost chokes async requests in presence of lots of sync IO.

Have you done some testing with that scenario and see how quickly you adjust to that change.

/me is trying to wrap his head around all the smoothing and bandwidth calculation functions. Wished there was more explanation to it.

The estimation value will start from 100MB/s and adapt to the real bandwidth in seconds.

It tries to update the bandwidth only when disk is fully utilized. Any inactive period of more than one second will be skipped.

The estimated bandwidth will be reflecting how fast the device can writeout when _fully utilized_, and won't drop to 0 when it goes idle. The value will remain constant at disk idle time. At busy write time, if not considering fluctuations, it will also remain high unless be knocked down by possible concurrent reads that compete for the disk time and bandwidth with async writes.

The estimation is not done purely in the flusher because there is no guarantee for write_cache_pages() to return timely to update bandwidth.

The bdi->avg_write_bandwidth smoothing is very effective for filtering out sudden spikes, however may be a little biased in long term.

The overheads are low because the bdi bandwidth update only occurs at 200ms intervals.

The 200ms update interval is suitable, becuase it's not possible to get the real bandwidth for the instance at all, due to large fluctuations.

The NFS commits can be as large as seconds worth of data. One XFS completion may be as large as half second worth of data if we are going to increase the write chunk to half second worth of data. In ext4, fluctuations with time period of around 5 seconds is observed. And there is another pattern of irregular periods of up to 20 seconds on SSD tests.

That's why we are not only doing the estimation at 200ms intervals, but also averaging them over a period of 3 seconds and then go further to do another level of smoothing in avg_write_bandwidth.

CC Li Shaohua <[email protected]>

CC Peter Zijlstra <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

---
 fs/fs-writeback.c           |   13 +++++
 include/linux/backing-dev.h |    5 ++
 include/linux/writeback.h   |    3 +
 mm/backing-dev.c            |   12 +++++
 mm/page-writeback.c         |   81 ++++++++++++++++++++++++++++++++++
 5 files changed, 114 insertions(+)

To get an idea of the adaption speed and fluctuation range, here are some real examples (check the red dots and the yellow line):

http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/dirty-throttling-v8/3G/xfs-1dd-4k-8p-2948M-20:10-3.0.0-rc2-next-20110610+-2011-06-12.21:51/balance_dirty_pages-bandwidth.png
http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/dirty-throttling-v8/3G/ext3-1dd-4k-8p-2948M-20:10-3.0.0-rc2-next-20110610+-2011-06-12.22:02/balance_dirty_pages-bandwidth.png
http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/dirty-throttling-v8/3G/ext4-1dd-4k-8p-2948M-20:10-3.0.0-rc2-next-20110610+-2011-06-12.21:57/balance_dirty_pages-bandwidth.png
http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/dirty-throttling-v8/3G/btrfs-1dd-4k-8p-2948M-20:10-3.0.0-rc2-next-20110610+-2011-06-12.22:07/balance_dirty_pages-bandwidth.png

The estimation value will start from 100MB/s and adapt to the real bandwidth in seconds.

It tries to update the bandwidth only when disk is fully utilized. Any inactive period of more than one second will be skipped.

Quoted 5 lines · Wu Fengguang

The estimation value will start from 100MB/s and adapt to the real bandwidth in seconds.

It tries to update the bandwidth only when disk is fully utilized. Any inactive period of more than one second will be skipped.

Is this piece of code being tested in your graphs? Are there any inactive periods which get filtered out in your workload? I am assuming in a continuous dd, we will not have periods of inactivity 1 second long.

Introduce

nr_dirty = NR_FILE_DIRTY + NR_WRITEBACK + NR_UNSTABLE_NFS

in order to simplify many tests in the following patches.

balance_dirty_pages() will eventually care only about the dirty sums besides nr_writeback.

Signed-off-by Wu Fengguang <[email protected]>

---
 mm/page-writeback.c |   21 +++++++++++----------
 1 file changed, 11 insertions(+), 10 deletions(-)

mm/page-writeback.c +11 -10

@@ -560,8 +560,9 @@ static void bdi_update_bandwidth(struct 
 static void balance_dirty_pages(struct address_space *mapping,
 				unsigned long write_chunk)
 {
-	long nr_reclaimable, bdi_nr_reclaimable;
-	long nr_writeback, bdi_nr_writeback;
+	unsigned long nr_reclaimable, bdi_nr_reclaimable;
+	unsigned long nr_dirty;  /* = file_dirty + writeback + unstable_nfs */
+	unsigned long bdi_dirty;
 	unsigned long background_thresh;
 	unsigned long dirty_thresh;
 	unsigned long bdi_thresh;

@@ -574,7 +575,7 @@ static void balance_dirty_pages(struct a
 	for (;;) {
 		nr_reclaimable = global_page_state(NR_FILE_DIRTY) +
 					global_page_state(NR_UNSTABLE_NFS);
-		nr_writeback = global_page_state(NR_WRITEBACK);
+		nr_dirty = nr_reclaimable + global_page_state(NR_WRITEBACK);
 
 		global_dirty_limits(&background_thresh, &dirty_thresh);
 

@@ -583,8 +584,7 @@ static void balance_dirty_pages(struct a
 		 * catch-up. This avoids (excessively) small writeouts
 		 * when the bdi limits are ramping up.
 		 */
-		if (nr_reclaimable + nr_writeback <=
-				(background_thresh + dirty_thresh) / 2)
+		if (nr_dirty <= (background_thresh + dirty_thresh) / 2)
 			break;
 
 		bdi_thresh = bdi_dirty_limit(bdi, dirty_thresh);

@@ -602,10 +602,12 @@ static void balance_dirty_pages(struct a
 		 */
 		if (bdi_thresh < 2*bdi_stat_error(bdi)) {
 			bdi_nr_reclaimable = bdi_stat_sum(bdi, BDI_RECLAIMABLE);
-			bdi_nr_writeback = bdi_stat_sum(bdi, BDI_WRITEBACK);
+			bdi_dirty = bdi_nr_reclaimable +
+				    bdi_stat_sum(bdi, BDI_WRITEBACK);
 		} else {
 			bdi_nr_reclaimable = bdi_stat(bdi, BDI_RECLAIMABLE);
-			bdi_nr_writeback = bdi_stat(bdi, BDI_WRITEBACK);
+			bdi_dirty = bdi_nr_reclaimable +
+				    bdi_stat(bdi, BDI_WRITEBACK);
 		}
 
 		/*

@@ -614,9 +616,8 @@ static void balance_dirty_pages(struct a
 		 * bdi or process from holding back light ones; The latter is
 		 * the last resort safeguard.
 		 */
-		dirty_exceeded =
-			(bdi_nr_reclaimable + bdi_nr_writeback > bdi_thresh)
-			|| (nr_reclaimable + nr_writeback > dirty_thresh);
+		dirty_exceeded = (bdi_dirty > bdi_thresh) ||
+				  (nr_dirty > dirty_thresh);
 
 		if (!dirty_exceeded)
 			break;

The start of a heavy weight application (ie. KVM) may instantly knock down determine_dirtyable_memory() if the swap is not enabled or full. global_dirty_limits() and bdi_dirty_limit() will in turn get global/bdi dirty thresholds that are _much_ lower than the global/bdi dirty pages.

balance_dirty_pages() will then heavily throttle all dirtiers including the light ones, until the dirty pages drop below the new dirty thresholds. During this _deep_ dirty-exceeded state, the system may appear rather unresponsive to the users.

About "deep" dirty-exceeded: task_dirty_limit() assigns 1/8 lower dirty threshold to heavy dirtiers than light ones, and the dirty pages will be throttled around the heavy dirtiers' dirty threshold and reasonably below the light dirtiers' dirty threshold. In this state, only the heavy dirtiers will be throttled and the dirty pages are carefully controlled to not exceed the light dirtiers' dirty threshold. However if the threshold itself suddenly drops below the number of dirty pages, the light dirtiers will get heavily throttled.

So introduce global_dirty_limit for tracking the global dirty threshold with policies

- follow downwards slowly
- follow up in one shot

global_dirty_limit can effectively mask out the impact of sudden drop of dirtyable memory. It will be used in the next patch for two new type of dirty limits. Note that the new dirty limits are not going to avoid throttling the light dirtiers, but could limit their sleep time to 200ms.

Signed-off-by Wu Fengguang <[email protected]>

mm/page-writeback.c static void bdi_update_write_bandwidth(s · line 559

Quoted 1 line

mm/page-writeback.c +1 -0

+	if (now - update_time < MAX_PAUSE)

if (time_before(now, update_time + MAX_PAUSE))

mm/page-writeback.c static void bdi_update_write_bandwidth(s · line 563

Quoted 4 lines

mm/page-writeback.c +4 -0

+		return;
+
+	spin_lock(&dirty_lock);
+	if (now - update_time >= MAX_PAUSE) {

if (time_after_eq(now, update_time + MAX_PAUSE))

Add trace event balance_dirty_state for showing the global dirty page counts and thresholds at each global_dirty_limits() invocation. This will cover the callers throttle_vm_writeout(), over_bground_thresh() and each balance_dirty_pages() loop.

Quoted 4 lines · Wu Fengguang

Add trace event balance_dirty_state for showing the global dirty page counts and thresholds at each global_dirty_limits() invocation. This will cover the callers throttle_vm_writeout(), over_bground_thresh() and each balance_dirty_pages() loop.

Given that this is a rather uncontoversial diagnostics patch I'd move it to the front of the queue.