dirty throttling bits for 3.3

Add an upper limit to balanced_rate according to the below inequality. This filters out some rare but huge singular points, which at least enables more readable gnuplot figures.

When there are N dd dirtiers,

balanced_dirty_ratelimit = write_bw / N

So it holds that

balanced_dirty_ratelimit <= write_bw

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

---
 mm/page-writeback.c |    5 +++++
 1 file changed, 5 insertions(+)

mm/page-writeback.c +5 -0

@@ -804,6 +804,11 @@ static void bdi_update_dirty_ratelimit(s
 	 */
 	balanced_dirty_ratelimit = div_u64((u64)task_ratelimit * write_bw,
 					   dirty_rate | 1);
+	/*
+	 * balanced_dirty_ratelimit ~= (write_bw / N) <= write_bw
+	 */
+	if (unlikely(balanced_dirty_ratelimit > write_bw))
+		balanced_dirty_ratelimit = write_bw;
 
 	/*
 	 * We could safely do this and return immediately:

Quoted 8 lines · Wu Fengguang

Add an upper limit to balanced_rate according to the below inequality. This filters out some rare but huge singular points, which at least enables more readable gnuplot figures.

When there are N dd dirtiers,

balanced_dirty_ratelimit = write_bw / N

Quoted 3 lines

So it holds that

balanced_dirty_ratelimit <= write_bw

The change makes sense, but do we understand why there are such huge
singular points? Are they due to errors in estimation of bandwidth or due to errors in dirtying rate computations (e.g. due to truncates), or something else?

Quoted 9 lines · Jan Kara

Quoted 8 lines · Wu Fengguang

Add an upper limit to balanced_rate according to the below inequality. This filters out some rare but huge singular points, which at least enables more readable gnuplot figures.

When there are N dd dirtiers,

balanced_dirty_ratelimit = write_bw / N

Quoted 7 lines

Quoted 3 lines

So it holds that

balanced_dirty_ratelimit <= write_bw

The change makes sense, but do we understand why there are such huge
singular points? Are they due to errors in estimation of bandwidth or due to errors in dirtying rate computations (e.g. due to truncates), or something else?

Good point. I'll add this to the changelog:

The singular points originate from dirty_rate in the below formular:

balanced_dirty_ratelimit = task_ratelimit * write_bw / dirty_rate
where
dirty_rate = (number of page dirties in the past 200ms) / 200ms

In the extreme case, if all dd tasks suddenly get blocked on something else and hence no pages are dirtied at all, dirty_rate will be 0 and balanced_dirty_ratelimit will be inf. This could happen in reality.

There won't be tiny singular points though, as long as the dirty pages lie inside the dirty control area (above the freerun region). Because there the dd tasks will be throttled by balanced_dirty_pages() and won't be able to suddenly dirty much more pages than average.

Quoted 30 lines · Wu Fengguang

Quoted 9 lines · Jan Kara

Quoted 8 lines · Wu Fengguang

Add an upper limit to balanced_rate according to the below inequality. This filters out some rare but huge singular points, which at least enables more readable gnuplot figures.

When there are N dd dirtiers,

balanced_dirty_ratelimit = write_bw / N

Quoted 7 lines

Quoted 3 lines

So it holds that

balanced_dirty_ratelimit <= write_bw

The change makes sense, but do we understand why there are such huge
singular points? Are they due to errors in estimation of bandwidth or due to errors in dirtying rate computations (e.g. due to truncates), or something else?

Good point. I'll add this to the changelog:

The singular points originate from dirty_rate in the below formular:

balanced_dirty_ratelimit = task_ratelimit * write_bw / dirty_rate
where
dirty_rate = (number of page dirties in the past 200ms) / 200ms

In the extreme case, if all dd tasks suddenly get blocked on something else and hence no pages are dirtied at all, dirty_rate will be 0 and balanced_dirty_ratelimit will be inf. This could happen in reality.

Quoted 4 lines

There won't be tiny singular points though, as long as the dirty pages lie inside the dirty control area (above the freerun region). Because there the dd tasks will be throttled by balanced_dirty_pages() and won't be able to suddenly dirty much more pages than average.

OK, I see. Thanks for explanation.

It's a years long problem that a large number of short-lived dirtiers (eg. gcc instances in a fast kernel build) may starve long-run dirtiers (eg. dd) as well as pushing the dirty pages to the global hard limit.

The solution is to charge the pages dirtied by the exited gcc to the other random dirtying tasks. It sounds not perfect, however should behave good enough in practice, seeing as that throttled tasks aren't actually running so those that are running are more likely to pick it up and get throttled, therefore promoting an equal spread.

mm/page-writeback.c +11 -0

 /**
  * balance_dirty_pages_ratelimited_nr - balance dirty memory state

@@ -1242,6 +1243,17 @@ void balance_dirty_pages_ratelimited_nr(
 			ratelimit = 0;
 		}
 	}
+	/*
+	 * Pick up the dirtied pages by the exited tasks. This avoids lots of
+	 * short-lived tasks (eg. gcc invocations in a kernel build) escaping
+	 * the dirty throttling and livelock other long-run dirtiers.
+	 */
+	p = &__get_cpu_var(dirty_leaks);
+	if (*p > 0 && current->nr_dirtied < ratelimit) {
+		nr_pages_dirtied = min(*p, ratelimit - current->nr_dirtied);
+		*p -= nr_pages_dirtied;
+		current->nr_dirtied += nr_pages_dirtied;
+	}
 	preempt_enable();
 
 	if (unlikely(current->nr_dirtied >= ratelimit))

Quoted 13 lines · On Mon, 21 Nov 2011 21:03:44 +0800 Wu Fengguang <[email protected]> wrote:

It's a years long problem that a large number of short-lived dirtiers (eg. gcc instances in a fast kernel build) may starve long-run dirtiers (eg. dd) as well as pushing the dirty pages to the global hard limit.

The solution is to charge the pages dirtied by the exited gcc to the other random dirtying tasks. It sounds not perfect, however should behave good enough in practice, seeing as that throttled tasks aren't actually running so those that are running are more likely to pick it up and get throttled, therefore promoting an equal spread.

mm/page-writeback.c void set_page_dirty_balance(struct page · line 1197

Quoted 4 lines

mm/page-writeback.c +1 -0

@@ -1194,6 +1194,7 @@ void set_page_dirty_balance(struct page 
 }
 
 static DEFINE_PER_CPU(int, bdp_ratelimits);
+DEFINE_PER_CPU(int, dirty_leaks) = 0;

This is a poor identifier for a global symbol. Generally such symbols should at least identify what subsystem they belong to.

Also, this would be a good site at whcih to document the global symbol's role. The writeback code needs a lot of documentation. Of the design-level kind.

Quoted 25 lines

mm/page-writeback.c +11 -0

 /**
  * balance_dirty_pages_ratelimited_nr - balance dirty memory state

@@ -1242,6 +1243,17 @@ void balance_dirty_pages_ratelimited_nr(
 			ratelimit = 0;
 		}
 	}
+	/*
+	 * Pick up the dirtied pages by the exited tasks. This avoids lots of
+	 * short-lived tasks (eg. gcc invocations in a kernel build) escaping
+	 * the dirty throttling and livelock other long-run dirtiers.
+	 */
+	p = &__get_cpu_var(dirty_leaks);
+	if (*p > 0 && current->nr_dirtied < ratelimit) {
+		nr_pages_dirtied = min(*p, ratelimit - current->nr_dirtied);
+		*p -= nr_pages_dirtied;
+		current->nr_dirtied += nr_pages_dirtied;
+	}
 	preempt_enable();
 
 	if (unlikely(current->nr_dirtied >= ratelimit))

kernel/exit.c +0 -0

@@ -1037,6 +1037,8 @@ NORET_TYPE void do_exit(long code)
 	validate_creds_for_do_exit(tsk);
 

kernel/exit.c NORET_TYPE void do_exit(long code) · line 1041

Quoted 3 lines

kernel/exit.c +2 -0

 	preempt_disable();
+	if (tsk->nr_dirtied)
+		__this_cpu_add(dirty_leaks, tsk->nr_dirtied);

Whatever problem this code is solving, it only solved it in certain cases. For example, if tasks are forking, dirtying and exiting at a rapid rate on CPU 0 then all the other CPUs don't know anything about this and we didn't fix anything.

Quoted 15 lines · On Mon, 21 Nov 2011 21:03:44 +0800 Wu Fengguang <[email protected]> wrote:

It's a years long problem that a large number of short-lived dirtiers (eg. gcc instances in a fast kernel build) may starve long-run dirtiers (eg. dd) as well as pushing the dirty pages to the global hard limit.

The solution is to charge the pages dirtied by the exited gcc to the other random dirtying tasks. It sounds not perfect, however should behave good enough in practice, seeing as that throttled tasks aren't actually running so those that are running are more likely to pick it up and get throttled, therefore promoting an equal spread.

mm/page-writeback.c +0 -0

@@ -1194,6 +1194,7 @@ void set_page_dirty_balance(struct page 
 }
 

mm/page-writeback.c void set_page_dirty_balance(struct page · line 1197

Quoted 2 lines

mm/page-writeback.c +1 -0

 static DEFINE_PER_CPU(int, bdp_ratelimits);
+DEFINE_PER_CPU(int, dirty_leaks) = 0;

This is a poor identifier for a global symbol. Generally such symbols should at least identify what subsystem they belong to.

Also, this would be a good site at whcih to document the global symbol's role. The writeback code needs a lot of documentation. Of the design-level kind.

When dd in 512bytes, generic_perform_write() calls balance_dirty_pages_ratelimited() 8 times for the same page, but obviously the page is only dirtied once.

Fix it by accounting nr_dirtied at page dirty time.

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

---
 mm/page-writeback.c |    3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

mm/page-writeback.c +1 -2

@@ -1224,8 +1224,6 @@ void balance_dirty_pages_ratelimited_nr(
 	if (bdi->dirty_exceeded)
 		ratelimit = min(ratelimit, 32 >> (PAGE_SHIFT - 10));
 
-	current->nr_dirtied += nr_pages_dirtied;
-
 	preempt_disable();
 	/*
 	 * This prevents one CPU to accumulate too many dirtied pages without

@@ -1734,6 +1732,7 @@ void account_page_dirtied(struct page *p
 		__inc_bdi_stat(mapping->backing_dev_info, BDI_RECLAIMABLE);
 		__inc_bdi_stat(mapping->backing_dev_info, BDI_DIRTIED);
 		task_io_account_write(PAGE_CACHE_SIZE);
+		current->nr_dirtied++;
 	}
 }
 EXPORT_SYMBOL(account_page_dirtied);

Quoted 5 lines · Wu Fengguang

When dd in 512bytes, generic_perform_write() calls balance_dirty_pages_ratelimited() 8 times for the same page, but obviously the page is only dirtied once.

Fix it by accounting nr_dirtied at page dirty time.

Well, but after this change, the interface balance_dirty_ratelimited_nr()
is strange because the argument is only used for per-CPU ratelimiting and not for per-task ratelimiting...

So if you do this switch then I'd also
switch bdp_ratelimits to get consistent results and a clean interface and completely kill balance_dirty_pages_ratelimited_nr().

Quoted 9 lines · Jan Kara

Quoted 5 lines · Wu Fengguang

When dd in 512bytes, generic_perform_write() calls balance_dirty_pages_ratelimited() 8 times for the same page, but obviously the page is only dirtied once.

Fix it by accounting nr_dirtied at page dirty time.

Well, but after this change, the interface balance_dirty_ratelimited_nr()
is strange because the argument is only used for per-CPU ratelimiting and not for per-task ratelimiting...

Yeah I was vaguely aware of this... and still choose to ignore this since the patchset looked already forbiddingly large at the time ;)

Quoted 3 lines

So if you do this switch then I'd also
switch bdp_ratelimits to get consistent results and a clean interface and completely kill balance_dirty_pages_ratelimited_nr().

Following your suggestions to change ratelimiting as well :)

I'll do the interface change with a standalone patch.

---
Subject: writeback: fix dirtied pages accounting on sub-page writes
Date: Thu Apr 14 07:52:37 CST 2011

When dd in 512bytes, generic_perform_write() calls balance_dirty_pages_ratelimited() 8 times for the same page, but obviously the page is only dirtied once.

Fix it by accounting tsk->nr_dirtied and bdp_ratelimits at page dirty time.

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

---
 mm/page-writeback.c |   13 +++++--------
 1 file changed, 5 insertions(+), 8 deletions(-)

mm/page-writeback.c +3 -8

@@ -1231,8 +1231,6 @@ void balance_dirty_pages_ratelimited_nr(
 	if (bdi->dirty_exceeded)
 		ratelimit = min(ratelimit, 32 >> (PAGE_SHIFT - 10));
 
-	current->nr_dirtied += nr_pages_dirtied;
-
 	preempt_disable();
 	/*
 	 * This prevents one CPU to accumulate too many dirtied pages without

@@ -1243,12 +1241,9 @@ void balance_dirty_pages_ratelimited_nr(
 	p =  &__get_cpu_var(bdp_ratelimits);
 	if (unlikely(current->nr_dirtied >= ratelimit))
 		*p = 0;
-	else {
-		*p += nr_pages_dirtied;
-		if (unlikely(*p >= ratelimit_pages)) {
-			*p = 0;
-			ratelimit = 0;
-		}
+	else if (unlikely(*p >= ratelimit_pages)) {
+		*p = 0;
+		ratelimit = 0;
 	}
 	/*
 	 * Pick up the dirtied pages by the exited tasks. This avoids lots of

mm/page-writeback.c void account_page_dirtied(struct page *p · line 1742

Quoted 6 lines

mm/page-writeback.c +2 -0

@@ -1743,6 +1738,8 @@ void account_page_dirtied(struct page *p
 		__inc_bdi_stat(mapping->backing_dev_info, BDI_DIRTIED);
 		task_dirty_inc(current);
 		task_io_account_write(PAGE_CACHE_SIZE);
+		current->nr_dirtied++;
+		__get_cpu_var(bdp_ratelimits)++;

I think you need preempt_disable() and preempt_enable() pair around
__get_cpu_var(). Otherwise a process could get rescheduled in the middle of read-modify-write cycle...

Quoted 9 lines

mm/page-writeback.c void account_page_dirtied(struct page *p · line 1742

Quoted 6 lines

mm/page-writeback.c +2 -0

@@ -1743,6 +1738,8 @@ void account_page_dirtied(struct page *p
 		__inc_bdi_stat(mapping->backing_dev_info, BDI_DIRTIED);
 		task_dirty_inc(current);
 		task_io_account_write(PAGE_CACHE_SIZE);
+		current->nr_dirtied++;
+		__get_cpu_var(bdp_ratelimits)++;

I think you need preempt_disable() and preempt_enable() pair around
__get_cpu_var(). Otherwise a process could get rescheduled in the middle of read-modify-write cycle...

Hmm, I'm not worried about it at all, because bdp_ratelimits don't need to be accurate. In normal cases it won't even trigger one single call to balance_dirty_pages().

btw, account_page_dirtied() is called inside spinlock, will it be sufficient?

Quoted 10 lines · Wu Fengguang

Quoted 9 lines

mm/page-writeback.c void account_page_dirtied(struct page *p · line 1742

Quoted 6 lines

mm/page-writeback.c +2 -0

@@ -1743,6 +1738,8 @@ void account_page_dirtied(struct page *p
 		__inc_bdi_stat(mapping->backing_dev_info, BDI_DIRTIED);
 		task_dirty_inc(current);
 		task_io_account_write(PAGE_CACHE_SIZE);
+		current->nr_dirtied++;
+		__get_cpu_var(bdp_ratelimits)++;

I think you need preempt_disable() and preempt_enable() pair around
__get_cpu_var(). Otherwise a process could get rescheduled in the middle of read-modify-write cycle...

Quoted 3 lines

Hmm, I'm not worried about it at all, because bdp_ratelimits don't need to be accurate. In normal cases it won't even trigger one single call to balance_dirty_pages().

I agree regarding the accuracy. But the CPU can change when the process
is scheduled again. So you could modify counter of a CPU you are not running on. And that can cause bad things...

Quoted 2 lines

btw, account_page_dirtied() is called inside spinlock, will it be sufficient?

Currently it is not enough in real-time kernels and when sleeping
spinlocks work gets merged it won't be enough even in standard kernels... And in kernels where spinlock means preemption is disabled preempt_enable/disable will be almost for free...

Quoted 1 line

+ __get_cpu_var(bdp_ratelimits)++;

I think you need preempt_disable() and preempt_enable() pair around
__get_cpu_var(). Otherwise a process could get rescheduled in the middle of read-modify-write cycle...

Quoted 4 lines · Jan Kara

Quoted 1 line

+ __get_cpu_var(bdp_ratelimits)++;

I think you need preempt_disable() and preempt_enable() pair around
__get_cpu_var(). Otherwise a process could get rescheduled in the middle of read-modify-write cycle...

there's of course the this_cpu_inc(bdp_ratelimits); thing.

On x86 that'll turn into a single insn, on others it will add the required preempt_disable/enable bits.

Quoted 6 lines · Peter Zijlstra

Quoted 4 lines · Jan Kara

Quoted 1 line

+ __get_cpu_var(bdp_ratelimits)++;

I think you need preempt_disable() and preempt_enable() pair around
__get_cpu_var(). Otherwise a process could get rescheduled in the middle of read-modify-write cycle...

Quoted 4 lines

there's of course the this_cpu_inc(bdp_ratelimits); thing.

On x86 that'll turn into a single insn, on others it will add the required preempt_disable/enable bits.

It's good to know that. But what if we don't really care which CPU data it's increasing, and can accept losing some increases due to the resulted race condition?

Quoted 7 lines · Wu Fengguang

Quoted 6 lines · Peter Zijlstra

Quoted 4 lines · Jan Kara

Quoted 1 line

+ __get_cpu_var(bdp_ratelimits)++;

I think you need preempt_disable() and preempt_enable() pair around
__get_cpu_var(). Otherwise a process could get rescheduled in the middle of read-modify-write cycle...

Quoted 8 lines

Quoted 4 lines

there's of course the this_cpu_inc(bdp_ratelimits); thing.

On x86 that'll turn into a single insn, on others it will add the required preempt_disable/enable bits.

It's good to know that. But what if we don't really care which CPU data it's increasing, and can accept losing some increases due to the resulted race condition?

I just added a comment for it, hope it helps :)

/*
* This is racy, however bdp_ratelimits merely serves as a
* gross safeguard. We don't really care the exact CPU it's
* charging to and the resulted inaccuracy is acceptable. */
__get_cpu_var(bdp_ratelimits)++;

Quoted 17 lines · Wu Fengguang

Quoted 7 lines · Wu Fengguang

Quoted 6 lines · Peter Zijlstra

Quoted 4 lines · Jan Kara

Quoted 1 line

+ __get_cpu_var(bdp_ratelimits)++;

I think you need preempt_disable() and preempt_enable() pair around
__get_cpu_var(). Otherwise a process could get rescheduled in the middle of read-modify-write cycle...

Quoted 8 lines

Quoted 4 lines

there's of course the this_cpu_inc(bdp_ratelimits); thing.

On x86 that'll turn into a single insn, on others it will add the required preempt_disable/enable bits.

It's good to know that. But what if we don't really care which CPU data it's increasing, and can accept losing some increases due to the resulted race condition?

Quoted 8 lines

I just added a comment for it, hope it helps :)

/*
* This is racy, however bdp_ratelimits merely serves as a
* gross safeguard. We don't really care the exact CPU it's
* charging to and the resulted inaccuracy is acceptable. */
__get_cpu_var(bdp_ratelimits)++;

Thing is, I'm not sure how much update you can effectively wreck by interleaving the RmW cycles of two CPUs like this.

Simply loosing a few increments would be fine, but what are the practical implications of actually relying on this behaviour and how do various architectures cope.

Quoted 14 lines · Wu Fengguang

Quoted 9 lines · Jan Kara

Quoted 5 lines · Wu Fengguang

When dd in 512bytes, generic_perform_write() calls balance_dirty_pages_ratelimited() 8 times for the same page, but obviously the page is only dirtied once.

Fix it by accounting nr_dirtied at page dirty time.

Well, but after this change, the interface balance_dirty_ratelimited_nr()
is strange because the argument is only used for per-CPU ratelimiting and not for per-task ratelimiting...

Yeah I was vaguely aware of this... and still choose to ignore this since the patchset looked already forbiddingly large at the time ;)

Quoted 7 lines

Quoted 3 lines

So if you do this switch then I'd also
switch bdp_ratelimits to get consistent results and a clean interface and completely kill balance_dirty_pages_ratelimited_nr().

Following your suggestions to change ratelimiting as well :)

I'll do the interface change with a standalone patch.

OK.

De-account the accumulative dirty counters on page redirty.

Page redirties (very common in ext4) will introduce mismatch between counters (a) and (b)

a) NR_DIRTIED, BDI_DIRTIED, tsk->nr_dirtied
b) NR_WRITTEN, BDI_WRITTEN

This will introduce systematic errors in balanced_rate and result in dirty page position errors (ie. the dirty pages are no longer balanced around the global/bdi setpoints).

...

mm/page-writeback.c +0 -0

@@ -1792,6 +1792,17 @@ int __set_page_dirty_nobuffers(struct pa
 }
 EXPORT_SYMBOL(__set_page_dirty_nobuffers);

Quoted 20 lines · On Mon, 21 Nov 2011 21:03:46 +0800 Wu Fengguang <[email protected]> wrote:

De-account the accumulative dirty counters on page redirty.

Page redirties (very common in ext4) will introduce mismatch between counters (a) and (b)

a) NR_DIRTIED, BDI_DIRTIED, tsk->nr_dirtied
b) NR_WRITTEN, BDI_WRITTEN

This will introduce systematic errors in balanced_rate and result in dirty page position errors (ie. the dirty pages are no longer balanced around the global/bdi setpoints).

...

mm/page-writeback.c +0 -0

@@ -1792,6 +1792,17 @@ int __set_page_dirty_nobuffers(struct pa
 }
 EXPORT_SYMBOL(__set_page_dirty_nobuffers);
 

mm/page-writeback.c int __set_page_dirty_nobuffers(struct pa · line 1803

Quoted 9 lines

mm/page-writeback.c +9 -0

+void account_page_redirty(struct page *page)
+{
+	struct address_space *mapping = page->mapping;
+	if (mapping && mapping_cap_account_dirty(mapping)) {
+		current->nr_dirtied--;
+		dec_zone_page_state(page, NR_DIRTIED);
+		dec_bdi_stat(mapping->backing_dev_info, BDI_DIRTIED);
+	}
+}

Again, writeback doesn't seem to be the best place to be adding undocumented code.

mm/page-writeback.c int __set_page_dirty_nobuffers(struct pa · line 1804

Quoted 1 line

mm/page-writeback.c +1 -0

+EXPORT_SYMBOL(account_page_redirty);

The export is unneeded?

Hi,

I'd like to push these 5 dirty throttling improvements to linux-next, targeting for inclusion in Linux 3.3.

It's a comfortably small series for review ;) And there are no changes since the last v12 post. (I went through them once again but find nothing to change.)

[PATCH 1/5] writeback: balanced_rate cannot exceed write bandwidth [PATCH 2/5] writeback: charge leaked page dirties to active tasks [PATCH 3/5] writeback: fix dirtied pages accounting on sub-page writes [PATCH 4/5] writeback: fix dirtied pages accounting on redirty [PATCH 5/5] writeback: dirty ratelimit - think time compensation

Quoted 5 lines · Wu Fengguang

Hi,

I'd like to push these 5 dirty throttling improvements to linux-next, targeting for inclusion in Linux 3.3.

Quoted 8 lines

It's a comfortably small series for review ;) And there are no changes since the last v12 post. (I went through them once again but find nothing to change.)

[PATCH 1/5] writeback: balanced_rate cannot exceed write bandwidth [PATCH 2/5] writeback: charge leaked page dirties to active tasks [PATCH 3/5] writeback: fix dirtied pages accounting on sub-page writes [PATCH 4/5] writeback: fix dirtied pages accounting on redirty [PATCH 5/5] writeback: dirty ratelimit - think time compensation

Given the updates I'm ok with this series,

Acked-by Peter Zijlstra <[email protected]>

Thanks!