IO-less dirty throttling v9

mm/page-writeback.c +66 -0

+static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
+					unsigned long thresh,
+					unsigned long bg_thresh,
+					unsigned long dirty,
+					unsigned long bdi_thresh,
+					unsigned long bdi_dirty)
+{
+	unsigned long freerun = dirty_freerun_ceiling(thresh, bg_thresh);
+	unsigned long limit = hard_dirty_limit(thresh);
+	unsigned long x_intercept;
+	unsigned long setpoint;		/* the target balance point */
+	unsigned long span;
+	long long pos_ratio;		/* for scaling up/down the rate limit */
+	long x;
+
+	if (unlikely(dirty >= limit))
+		return 0;
+
+	/*
+	 * global setpoint
+	 *
+	 *                         setpoint - dirty 3
+	 *        f(dirty) := 1 + (----------------)
+	 *                         limit - setpoint
+	 *
+	 * it's a 3rd order polynomial that subjects to
+	 *
+	 * (1) f(freerun)  = 2.0 => rampup base_rate reasonably fast
+	 * (2) f(setpoint) = 1.0 => the balance point
+	 * (3) f(limit)    = 0   => the hard limit
+	 * (4) df/dx       < 0	 => negative feedback control
+	 * (5) the closer to setpoint, the smaller |df/dx| (and the reverse)
+	 *     => fast response on large errors; small oscillation near setpoint
+	 */
+	setpoint = (freerun + limit) / 2;
+	x = div_s64((setpoint - dirty) << RATELIMIT_CALC_SHIFT,
+		    limit - setpoint + 1);
+	pos_ratio = x;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio += 1 << RATELIMIT_CALC_SHIFT;
+
+	/*
+	 * bdi setpoint
+	 *
+	 *        f(dirty) := 1.0 + k * (dirty - setpoint)
+	 *
+	 * The main bdi control line is a linear function that subjects to
+	 *
+	 * (1) f(setpoint) = 1.0
+	 * (2) k = - 1 / (8 * write_bw)  (in single bdi case)
+	 *     or equally: x_intercept = setpoint + 8 * write_bw
+	 *
+	 * For single bdi case, the dirty pages are observed to fluctuate
+	 * regularly within range
+	 *        [setpoint - write_bw/2, setpoint + write_bw/2]
+	 * for various filesystems, where (2) can yield in a reasonable 12.5%
+	 * fluctuation range for pos_ratio.
+	 *
+	 * For JBOD case, bdi_thresh (not bdi_dirty!) could fluctuate up to its
+	 * own size, so move the slope over accordingly.
+	 */
+	if (unlikely(bdi_thresh > thresh))
+		bdi_thresh = thresh;
+	/*
+	 * scale global setpoint to bdi's:  setpoint *= bdi_thresh / thresh

Hello Fengguang,

this patch is much easier to read than in older versions! Good work!

Quoted 70 lines

(quoted diff) +70 -0

+static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
+					unsigned long thresh,
+					unsigned long bg_thresh,
+					unsigned long dirty,
+					unsigned long bdi_thresh,
+					unsigned long bdi_dirty)
+{
+	unsigned long freerun = dirty_freerun_ceiling(thresh, bg_thresh);
+	unsigned long limit = hard_dirty_limit(thresh);
+	unsigned long x_intercept;
+	unsigned long setpoint;		/* the target balance point */
+	unsigned long span;
+	long long pos_ratio;		/* for scaling up/down the rate limit */
+	long x;
+
+	if (unlikely(dirty >= limit))
+		return 0;
+
+	/*
+	 * global setpoint
+	 *
+	 *                         setpoint - dirty 3
+	 *        f(dirty) := 1 + (----------------)
+	 *                         limit - setpoint
+	 *
+	 * it's a 3rd order polynomial that subjects to
+	 *
+	 * (1) f(freerun)  = 2.0 => rampup base_rate reasonably fast
+	 * (2) f(setpoint) = 1.0 => the balance point
+	 * (3) f(limit)    = 0   => the hard limit
+	 * (4) df/dx       < 0	 => negative feedback control
+	 * (5) the closer to setpoint, the smaller |df/dx| (and the reverse)
+	 *     => fast response on large errors; small oscillation near setpoint
+	 */
+	setpoint = (freerun + limit) / 2;
+	x = div_s64((setpoint - dirty) << RATELIMIT_CALC_SHIFT,
+		    limit - setpoint + 1);
+	pos_ratio = x;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio += 1 << RATELIMIT_CALC_SHIFT;
+
+	/*
+	 * bdi setpoint
+	 *
+	 *        f(dirty) := 1.0 + k * (dirty - setpoint)
+	 *
+	 * The main bdi control line is a linear function that subjects to
+	 *
+	 * (1) f(setpoint) = 1.0
+	 * (2) k = - 1 / (8 * write_bw)  (in single bdi case)
+	 *     or equally: x_intercept = setpoint + 8 * write_bw
+	 *
+	 * For single bdi case, the dirty pages are observed to fluctuate
+	 * regularly within range
+	 *        [setpoint - write_bw/2, setpoint + write_bw/2]
+	 * for various filesystems, where (2) can yield in a reasonable 12.5%
+	 * fluctuation range for pos_ratio.
+	 *
+	 * For JBOD case, bdi_thresh (not bdi_dirty!) could fluctuate up to its
+	 * own size, so move the slope over accordingly.
+	 */
+	if (unlikely(bdi_thresh > thresh))
+		bdi_thresh = thresh;
+	/*
+	 * scale global setpoint to bdi's:  setpoint *= bdi_thresh / thresh
+	 */
+	x = div_u64((u64)bdi_thresh << 16, thresh | 1);
+	setpoint = setpoint * (u64)x >> 16;
+	/*

Review

Quoted 6 lines

(quoted diff) +6 -0

+	 * Use span=(4*write_bw) in single bdi case as indicated by
+	 * (thresh - bdi_thresh ~= 0) and transit to bdi_thresh in JBOD case.
+	 */
+	span = div_u64((u64)bdi_thresh * (thresh - bdi_thresh) +
+		       (u64)(4 * bdi->avg_write_bandwidth) * bdi_thresh,
+		       thresh + 1);

I think you can slightly simplify this to:
(thresh - bdi_thresh + 4 * bdi->avg_write_bandwidth) * (u64)x >> 16;

Review

Quoted 1 line

(quoted diff) +1 -0

+	x_intercept = setpoint + 2 * span;

What if x_intercept > bdi_thresh? Since 8*bdi->avg_write_bandwidth is
easily 500 MB, that happens quite often I imagine?

Review

Quoted 4 lines

(quoted diff) +4 -0

+
+	if (unlikely(bdi_dirty > setpoint + span)) {
+		if (unlikely(bdi_dirty > limit))
+			return 0;

Shouldn't this be bdi_thresh instead of limit? I understand this is a
hard limit but with more bdis this condition is rather weak and almost never true.

Quoted 4 lines

(quoted diff) +4 -0

+		if (x_intercept < limit) {
+			x_intercept = limit;	/* auxiliary control line */
+			setpoint += span;
+			pos_ratio >>= 1;

Review

Quoted 1 line

(quoted diff) +1 -0

+		}

And here you stretch the control area upto the global dirty limit. I
understand you maybe don't want to be really strict and cut control area at bdi_thresh but your choice looks like too benevolent - when you have several active bdi's with different speeds this will effectively erase difference between them, won't it? E.g. with 10 bdi's (x_intercept - bdi_dirty) / (x_intercept - setpoint) is going to be close to 1 unless bdi_dirty really heavily exceeds bdi_thresh.

So wouldn't it be better to
just make sure control area is reasonably large (e.g. at least 16 MB) to allow BDI to ramp up it's bdi_thresh but don't extend it upto global dirty limit?

Review

Quoted 7 lines

(quoted diff) +7 -0

+	}
+	pos_ratio *= x_intercept - bdi_dirty;
+	do_div(pos_ratio, x_intercept - setpoint + 1);
+
+	return pos_ratio;
+}
+

Honza

Signature · 2 lines

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

Quoted 4 lines

Quoted 4 lines

(quoted diff) +4 -0

+		if (x_intercept < limit) {
+			x_intercept = limit;	/* auxiliary control line */
+			setpoint += span;
+			pos_ratio >>= 1;

Quoted 8 lines

mm/page-writeback.c static unsigned long bdi_position_ratio( · line 594

Quoted 1 line

mm/page-writeback.c +1 -0

+		}

And here you stretch the control area upto the global dirty limit. I
understand you maybe don't want to be really strict and cut control area at bdi_thresh but your choice looks like too benevolent - when you have several active bdi's with different speeds this will effectively erase difference between them, won't it? E.g. with 10 bdi's (x_intercept - bdi_dirty) / (x_intercept - setpoint) is going to be close to 1 unless bdi_dirty really heavily exceeds bdi_thresh.

Yes the auxiliary control line could be very flat (small slope).

However it's not normal for the bdi dirty pages to fall into the range of auxiliary control line at all. And once it takes effect, the pos_ratio is at most 0.5 (which is the value at the connection point with the main bdi control line) which is strong enough to pull the dirty pages off the auxiliary bdi control line and into the scope of main bdi control line.

The auxiliary control line is intended for bringing down the bdi_dirty of the USB key before 250s (where the "pos bandwidth" line keeps low):

http://www.kernel.org/pub/linux/kernel/people/wfg/writeback/dirty-throttling-v6/1UKEY+1HDD-3G/ext4-4dd-1M-8p-2945M-20%25-2.6.38-rc5-dt6+-2011-02-22-09-46/balance_dirty_pages-pages.png

After that the bdi_dirty will fluctuate around bdi_thresh and won't grow high and step into the scope of the auxiliary control line.

Quoted 23 lines · Jan Kara

Quoted 23 lines

(quoted diff) +23 -0

+static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
+					unsigned long thresh,
+					unsigned long bg_thresh,
+					unsigned long dirty,
+					unsigned long bdi_thresh,
+					unsigned long bdi_dirty)
+{
+	unsigned long freerun = dirty_freerun_ceiling(thresh, bg_thresh);
+	unsigned long limit = hard_dirty_limit(thresh);
+	unsigned long x_intercept;
+	unsigned long setpoint;		/* the target balance point */
+	unsigned long span;
+	long long pos_ratio;		/* for scaling up/down the rate limit */
+	long x;
+
+	if (unlikely(dirty >= limit))
+		return 0;
+
+	/*
+	 * global setpoint
+	 *
+	 *                         setpoint - dirty 3
+	 *        f(dirty) := 1 + (----------------)

Quoted 8 lines

Review

Quoted 8 lines

(quoted diff) +8 -0

+	 *                         limit - setpoint
+	 *
+	 * it's a 3rd order polynomial that subjects to
+	 *
+	 * (1) f(freerun)  = 2.0 => rampup base_rate reasonably fast
+	 * (2) f(setpoint) = 1.0 => the balance point
+	 * (3) f(limit)    = 0   => the hard limit
+	 * (4) df/dx       < 0	 => negative feedback control

Quoted 5 lines

Quoted 5 lines

(quoted diff) +5 -0

+	 * (5) the closer to setpoint, the smaller |df/dx| (and the reverse)
+	 *     => fast response on large errors; small oscillation near setpoint
+	 */
+	setpoint = (freerun + limit) / 2;
+	x = div_s64((setpoint - dirty) << RATELIMIT_CALC_SHIFT,

Quoted 8 lines

Review

Quoted 8 lines

(quoted diff) +8 -0

+		    limit - setpoint + 1);
+	pos_ratio = x;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio += 1 << RATELIMIT_CALC_SHIFT;
+
+	/*
+	 * bdi setpoint

Quoted 2 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+	 *
+	 *        f(dirty) := 1.0 + k * (dirty - setpoint)

Quoted 24 lines

Quoted 24 lines

(quoted diff) +24 -0

+	 *
+	 * The main bdi control line is a linear function that subjects to
+	 *
+	 * (1) f(setpoint) = 1.0
+	 * (2) k = - 1 / (8 * write_bw)  (in single bdi case)
+	 *     or equally: x_intercept = setpoint + 8 * write_bw
+	 *
+	 * For single bdi case, the dirty pages are observed to fluctuate
+	 * regularly within range
+	 *        [setpoint - write_bw/2, setpoint + write_bw/2]
+	 * for various filesystems, where (2) can yield in a reasonable 12.5%
+	 * fluctuation range for pos_ratio.
+	 *
+	 * For JBOD case, bdi_thresh (not bdi_dirty!) could fluctuate up to its
+	 * own size, so move the slope over accordingly.
+	 */
+	if (unlikely(bdi_thresh > thresh))
+		bdi_thresh = thresh;
+	/*
+	 * scale global setpoint to bdi's:  setpoint *= bdi_thresh / thresh
+	 */
+	x = div_u64((u64)bdi_thresh << 16, thresh | 1);
+	setpoint = setpoint * (u64)x >> 16;
+	/*

Quoted 8 lines

Review

Quoted 6 lines

(quoted diff) +6 -0

+	 * Use span=(4*write_bw) in single bdi case as indicated by
+	 * (thresh - bdi_thresh ~= 0) and transit to bdi_thresh in JBOD case.
+	 */
+	span = div_u64((u64)bdi_thresh * (thresh - bdi_thresh) +
+		       (u64)(4 * bdi->avg_write_bandwidth) * bdi_thresh,
+		       thresh + 1);

I think you can slightly simplify this to:
(thresh - bdi_thresh + 4 * bdi->avg_write_bandwidth) * (u64)x >> 16;

Good idea!

Quoted 1 line

Review

Quoted 1 line

(quoted diff) +1 -0

+	x_intercept = setpoint + 2 * span;

Quoted 2 lines

What if x_intercept > bdi_thresh? Since 8*bdi->avg_write_bandwidth is
easily 500 MB, that happens quite often I imagine?

That's fine because I no longer target "bdi_thresh" as some limiting factor as the global "thresh". Due to it being unstable in small memory JBOD systems, which is the big and unique problem in JBOD.

Hi Fengguang,

Quoted 25 lines · Wu Fengguang

Quoted 24 lines · Jan Kara

Quoted 24 lines

(quoted diff) +24 -0

+static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
+					unsigned long thresh,
+					unsigned long bg_thresh,
+					unsigned long dirty,
+					unsigned long bdi_thresh,
+					unsigned long bdi_dirty)
+{
+	unsigned long freerun = dirty_freerun_ceiling(thresh, bg_thresh);
+	unsigned long limit = hard_dirty_limit(thresh);
+	unsigned long x_intercept;
+	unsigned long setpoint;		/* the target balance point */
+	unsigned long span;
+	long long pos_ratio;		/* for scaling up/down the rate limit */
+	long x;
+
+	if (unlikely(dirty >= limit))
+		return 0;
+
+	/*
+	 * global setpoint
+	 *
+	 *                         setpoint - dirty 3
+	 *        f(dirty) := 1 + (----------------)
+	 *                         limit - setpoint

Quoted 7 lines

Quoted 7 lines

Review

Quoted 7 lines

(quoted diff) +7 -0

+	 *
+	 * it's a 3rd order polynomial that subjects to
+	 *
+	 * (1) f(freerun)  = 2.0 => rampup base_rate reasonably fast
+	 * (2) f(setpoint) = 1.0 => the balance point
+	 * (3) f(limit)    = 0   => the hard limit
+	 * (4) df/dx       < 0	 => negative feedback control

^^^ Strictly speaking this is <= 0

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

(quoted diff) +8 -0

+	 * (5) the closer to setpoint, the smaller |df/dx| (and the reverse)
+	 *     => fast response on large errors; small oscillation near setpoint
+	 */
+	setpoint = (freerun + limit) / 2;
+	x = div_s64((setpoint - dirty) << RATELIMIT_CALC_SHIFT,
+		    limit - setpoint + 1);
+	pos_ratio = x;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;

Quoted 5 lines

Quoted 5 lines

Review

Quoted 5 lines

(quoted diff) +5 -0

+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio += 1 << RATELIMIT_CALC_SHIFT;
+
+	/*
+	 * bdi setpoint

OK, so if I understand the code right, we now have basic pos_ratio based
on global situation. Now, in the following code, we might scale pos_ratio further down, if bdi_dirty is too much over bdi's share, right?

Do we also want to scale pos_ratio up, if we are under bdi's share?

If yes, do we really want to do it even if global pos_ratio < 1 (i.e. we are over global setpoint)?

Maybe we could update the comment with something like:
* We have computed basic pos_ratio above based on global situation. If the
* bdi is over its share of dirty pages, we want to scale pos_ratio further
* down. That is done by the following mechanism:
and now describe how updating works.

Quoted 2 lines

Quoted 2 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+	 *
+	 *        f(dirty) := 1.0 + k * (dirty - setpoint)

^^^^^^^ bdi_dirty? ^^^ maybe I'd name it
bdi_setpoint to distinguish clearly from the global value.

Quoted 33 lines

Quoted 32 lines

Quoted 20 lines

(quoted diff) +20 -0

+	 *
+	 * The main bdi control line is a linear function that subjects to
+	 *
+	 * (1) f(setpoint) = 1.0
+	 * (2) k = - 1 / (8 * write_bw)  (in single bdi case)
+	 *     or equally: x_intercept = setpoint + 8 * write_bw
+	 *
+	 * For single bdi case, the dirty pages are observed to fluctuate
+	 * regularly within range
+	 *        [setpoint - write_bw/2, setpoint + write_bw/2]
+	 * for various filesystems, where (2) can yield in a reasonable 12.5%
+	 * fluctuation range for pos_ratio.
+	 *
+	 * For JBOD case, bdi_thresh (not bdi_dirty!) could fluctuate up to its
+	 * own size, so move the slope over accordingly.
+	 */
+	if (unlikely(bdi_thresh > thresh))
+		bdi_thresh = thresh;
+	/*
+	 * scale global setpoint to bdi's:  setpoint *= bdi_thresh / thresh

Review

Quoted 10 lines

(quoted diff) +10 -0

+	 */
+	x = div_u64((u64)bdi_thresh << 16, thresh | 1);
+	setpoint = setpoint * (u64)x >> 16;
+	/*
+	 * Use span=(4*write_bw) in single bdi case as indicated by
+	 * (thresh - bdi_thresh ~= 0) and transit to bdi_thresh in JBOD case.
+	 */
+	span = div_u64((u64)bdi_thresh * (thresh - bdi_thresh) +
+		       (u64)(4 * bdi->avg_write_bandwidth) * bdi_thresh,
+		       thresh + 1);

I think you can slightly simplify this to:
(thresh - bdi_thresh + 4 * bdi->avg_write_bandwidth) * (u64)x >> 16;

Quoted 3 lines

Good idea!

Quoted 1 line

Review

Quoted 1 line

(quoted diff) +1 -0

+	x_intercept = setpoint + 2 * span;

^^ BTW, why do you have 2*span here? It can result in x_intercept being
~3*bdi_thresh...

So maybe you should use bdi_thresh/2 in the computation of span?

Quoted 6 lines

Quoted 2 lines

What if x_intercept > bdi_thresh? Since 8*bdi->avg_write_bandwidth is
easily 500 MB, that happens quite often I imagine?

That's fine because I no longer target "bdi_thresh" as some limiting factor as the global "thresh". Due to it being unstable in small memory JBOD systems, which is the big and unique problem in JBOD.

I see. Given the control mechanism below, I think we can try this idea
and see whether it makes problems in practice or not. But the fact that bdi_thresh is no longer treated as limit should be noted in a changelog - probably of the last patch (although that is already too long for my taste so I'll look into how we could make it shorter so that average developer has enough patience to read it ;).

Quoted 6 lines

Quoted 6 lines

Quoted 2 lines

What if x_intercept > bdi_thresh? Since 8*bdi->avg_write_bandwidth is
easily 500 MB, that happens quite often I imagine?

That's fine because I no longer target "bdi_thresh" as some limiting factor as the global "thresh". Due to it being unstable in small memory JBOD systems, which is the big and unique problem in JBOD.

Quoted 6 lines

I see. Given the control mechanism below, I think we can try this idea
and see whether it makes problems in practice or not. But the fact that bdi_thresh is no longer treated as limit should be noted in a changelog - probably of the last patch (although that is already too long for my taste so I'll look into how we could make it shorter so that average developer has enough patience to read it ;).

Good point. I'll make it a comment in the last patch.

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

mm/page-writeback.c +8 -0

+	 * (5) the closer to setpoint, the smaller |df/dx| (and the reverse)
+	 *     => fast response on large errors; small oscillation near setpoint
+	 */
+	setpoint = (freerun + limit) / 2;
+	x = div_s64((setpoint - dirty) << RATELIMIT_CALC_SHIFT,
+		    limit - setpoint + 1);
+	pos_ratio = x;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;

Quoted 8 lines

Quoted 5 lines

Quoted 5 lines

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

Quoted 5 lines

mm/page-writeback.c +5 -0

+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio += 1 << RATELIMIT_CALC_SHIFT;
+
+	/*
+	 * bdi setpoint

OK, so if I understand the code right, we now have basic pos_ratio based
on global situation. Now, in the following code, we might scale pos_ratio further down, if bdi_dirty is too much over bdi's share, right?

Right.

Quoted 1 line

Do we also want to scale pos_ratio up, if we are under bdi's share?

Yes.

Quoted 2 lines

If yes, do we really want to do it even if global pos_ratio < 1 (i.e. we are over global setpoint)?

Yes. It's safe because the bdi pos_ratio scale is linear and the global pos_ratio scale will quickly drop to 0 near @limit, thus counter-acting any > 1 bdi pos_ratio.

Quoted 4 lines

Quoted 2 lines

Quoted 2 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+	 *
+	 *        f(dirty) := 1.0 + k * (dirty - setpoint)

^^^^^^^ bdi_dirty? ^^^ maybe I'd name it
bdi_setpoint to distinguish clearly from the global value.

OK. I'll add a new variable bdi_setpoint, too, to make it consistent all over the places.

Quoted 33 lines

Quoted 33 lines

Quoted 32 lines

Quoted 20 lines

mm/page-writeback.c +20 -0

+	 *
+	 * The main bdi control line is a linear function that subjects to
+	 *
+	 * (1) f(setpoint) = 1.0
+	 * (2) k = - 1 / (8 * write_bw)  (in single bdi case)
+	 *     or equally: x_intercept = setpoint + 8 * write_bw
+	 *
+	 * For single bdi case, the dirty pages are observed to fluctuate
+	 * regularly within range
+	 *        [setpoint - write_bw/2, setpoint + write_bw/2]
+	 * for various filesystems, where (2) can yield in a reasonable 12.5%
+	 * fluctuation range for pos_ratio.
+	 *
+	 * For JBOD case, bdi_thresh (not bdi_dirty!) could fluctuate up to its
+	 * own size, so move the slope over accordingly.
+	 */
+	if (unlikely(bdi_thresh > thresh))
+		bdi_thresh = thresh;
+	/*
+	 * scale global setpoint to bdi's:  setpoint *= bdi_thresh / thresh

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

Quoted 10 lines

mm/page-writeback.c +10 -0

+	 */
+	x = div_u64((u64)bdi_thresh << 16, thresh | 1);
+	setpoint = setpoint * (u64)x >> 16;
+	/*
+	 * Use span=(4*write_bw) in single bdi case as indicated by
+	 * (thresh - bdi_thresh ~= 0) and transit to bdi_thresh in JBOD case.
+	 */
+	span = div_u64((u64)bdi_thresh * (thresh - bdi_thresh) +
+		       (u64)(4 * bdi->avg_write_bandwidth) * bdi_thresh,
+		       thresh + 1);

I think you can slightly simplify this to:
(thresh - bdi_thresh + 4 * bdi->avg_write_bandwidth) * (u64)x >> 16;

Quoted 5 lines

Quoted 3 lines

Good idea!

Quoted 1 line

Review

Quoted 1 line

(quoted diff) +1 -0

+	x_intercept = setpoint + 2 * span;

^^ BTW, why do you have 2*span here? It can result in x_intercept being
~3*bdi_thresh...

Right.

Quoted 1 line

So maybe you should use bdi_thresh/2 in the computation of span?

Given that at some configurations bdi_thresh can fluctuate to its own size, I guess the current slope of control line is sharp enough.

Given equations

span = (x_intercept - bdi_setpoint) / 2
k = df/dx = -0.5 / span

and the values

span = bdi_thresh
dx = bdi_thresh

we get

        df = - dx / (2 * span) = - 1/2

That means, when bdi_dirty deviates bdi_thresh apart, pos_ratio and hence task ratelimit will fluctuate by -1/2. This is probably more than the users can tolerate already?

---
Subject: writeback: dirty position control
Date: Wed Mar 02 16:04:18 CST 2011

bdi_position_ratio() provides a scale factor to bdi->dirty_ratelimit, so that the resulted task rate limit can drive the dirty pages back to the global/bdi setpoints.

Old scheme is,
|
free run area | throttle area
----------------------------------------+---------------------------->
thresh^ dirty pages

New scheme is,

^ task rate limit

  |
  |            *
  |             *
  |              *
  |[free run]      *      [smooth throttled]
  |                  *
  |                     *
  |                         *
  ..bdi->dirty_ratelimit..........*
  |                               .     *
  |                               .          *
  |                               .              *
  |                               .                 *
  |                               .                    *
  +-------------------------------.-----------------------*------------>
                          setpoint^                  limit^  dirty pages

The slope of the bdi control line should be

1) large enough to pull the dirty pages to setpoint reasonably fast

2) small enough to avoid big fluctuations in the resulted pos_ratio and hence task ratelimit

Since the fluctuation range of the bdi dirty pages is typically observed to be within 1-second worth of data, the bdi control line's slope is selected to be a linear function of bdi write bandwidth, so that it can adapt to slow/fast storage devices well.

Assume the bdi control line

pos_ratio = 1.0 + k * (dirty - bdi_setpoint)

where k is the negative slope.

If targeting for 12.5% fluctuation range in pos_ratio when dirty pages are fluctuating in range

	[bdi_setpoint - write_bw/2, bdi_setpoint + write_bw/2],

we get slope

	k = - 1 / (8 * write_bw)

Let pos_ratio(x_intercept) = 0, we get the parameter used in code:

x_intercept = bdi_setpoint + 8 * write_bw

The global/bdi slopes are nicely complementing each other when the system has only one major bdi (indicated by bdi_thresh ~= thresh):

1) slope of global control line => scaling to the control scope size
2) slope of main bdi control line => scaling to the write bandwidth

so that

- in memory tight systems, (1) becomes strong enough to squeeze dirty pages inside the control scope

- in large memory systems where the "gravity" of (1) for pulling the dirty pages to setpoint is too weak, (2) can back (1) up and drive dirty pages to bdi_setpoint ~= setpoint reasonably fast.

Unfortunately in JBOD setups, the fluctuation range of bdi threshold is related to memory size due to the interferences between disks. In this case, the bdi slope will be weighted sum of write_bw and bdi_thresh.

peter: use 3rd order polynomial for the global control line

CC Peter Zijlstra <[email protected]>

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

---
 fs/fs-writeback.c         |    2 
 include/linux/writeback.h |    1 
 mm/page-writeback.c       |  212 +++++++++++++++++++++++++++++++++++-
 3 files changed, 209 insertions(+), 6 deletions(-)

mm/page-writeback.c +207 -5

@@ -46,6 +46,8 @@
  */
 #define BANDWIDTH_INTERVAL	max(HZ/5, 1)
 
+#define RATELIMIT_CALC_SHIFT	10
+
 /*
  * After a CPU has dirtied this many pages, balance_dirty_pages_ratelimited
  * will look to see if it needs to force writeback or throttling.

@@ -411,6 +413,12 @@ unsigned long determine_dirtyable_memory
 	return x + 1;	/* Ensure that we never return 0 */
 }
 
+static unsigned long dirty_freerun_ceiling(unsigned long thresh,
+					   unsigned long bg_thresh)
+{
+	return (thresh + bg_thresh) / 2;
+}
+
 static unsigned long hard_dirty_limit(unsigned long thresh)
 {
 	return max(thresh, global_dirty_limit);

@@ -495,6 +503,196 @@ unsigned long bdi_dirty_limit(struct bac
 	return bdi_dirty;
 }
 
+/*
+ * Dirty position control.
+ *
+ * (o) global/bdi setpoints
+ *
+ * We want the dirty pages be balanced around the global/bdi setpoints.
+ * When the number of dirty pages is higher/lower than the setpoint, the
+ * dirty position control ratio (and hence task dirty ratelimit) will be
+ * decreased/increased to bring the dirty pages back to the setpoint.
+ *
+ *     pos_ratio = 1 << RATELIMIT_CALC_SHIFT
+ *
+ *     if (dirty < setpoint) scale up   pos_ratio
+ *     if (dirty > setpoint) scale down pos_ratio
+ *
+ *     if (bdi_dirty < bdi_setpoint) scale up   pos_ratio
+ *     if (bdi_dirty > bdi_setpoint) scale down pos_ratio
+ *
+ *     task_ratelimit = balanced_rate * pos_ratio >> RATELIMIT_CALC_SHIFT
+ *
+ * (o) global control line
+ *
+ *     ^ pos_ratio
+ *     |
+ *     |            |<===== global dirty control scope ======>|
+ * 2.0 .............*
+ *     |            .*
+ *     |            . *
+ *     |            .   *
+ *     |            .     *
+ *     |            .        *
+ *     |            .            *
+ * 1.0 ................................*
+ *     |            .                  .     *
+ *     |            .                  .          *
+ *     |            .                  .              *
+ *     |            .                  .                 *
+ *     |            .                  .                    *
+ *   0 +------------.------------------.----------------------*------------->
+ *           freerun^          setpoint^                 limit^   dirty pages
+ *
+ * (o) bdi control lines
+ *
+ * The control lines for the global/bdi setpoints both stretch up to @limit.
+ * The below figure illustrates the main bdi control line with an auxiliary
+ * line extending it to @limit.
+ *
+ *   o
+ *     o
+ *       o                                      [o] main control line
+ *         o                                    [*] auxiliary control line
+ *           o
+ *             o
+ *               o
+ *                 o
+ *                   o
+ *                     o
+ *                       o--------------------- balance point, rate scale = 1
+ *                       | o
+ *                       |   o
+ *                       |     o
+ *                       |       o
+ *                       |         o
+ *                       |           o
+ *                       |             o------- connect point, rate scale = 1/2
+ *                       |<-- span --->| .*
+ *                       |                 .   *
+ *                       |                   .      *
+ *                       |                     .         *
+ *                       |                       .           *
+ *                       |                         .              *
+ *                       |                           .                 *
+ *  [--------------------+-----------------------------.--------------------*]
+ *  0              bdi_setpoint                    x_intercept           limit
+ *
+ * The auxiliary control line allows smoothly throttling bdi_dirty down to
+ * normal if it starts high in situations like
+ * - start writing to a slow SD card and a fast disk at the same time. The SD
+ *   card's bdi_dirty may rush to many times higher than bdi_setpoint.
+ * - the bdi dirty thresh drops quickly due to change of JBOD workload
+ */
+static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
+					unsigned long thresh,
+					unsigned long bg_thresh,
+					unsigned long dirty,
+					unsigned long bdi_thresh,
+					unsigned long bdi_dirty)
+{
+	unsigned long freerun = dirty_freerun_ceiling(thresh, bg_thresh);
+	unsigned long limit = hard_dirty_limit(thresh);
+	unsigned long x_intercept;
+	unsigned long setpoint;		/* dirty pages' target balance point */
+	unsigned long bdi_setpoint;
+	unsigned long span;
+	long long pos_ratio;		/* for scaling up/down the rate limit */
+	long x;
+
+	if (unlikely(dirty >= limit))
+		return 0;
+
+	/*
+	 * global setpoint
+	 *
+	 *                           setpoint - dirty 3
+	 *        f(dirty) := 1.0 + (----------------)
+	 *                           limit - setpoint
+	 *
+	 * it's a 3rd order polynomial that subjects to
+	 *
+	 * (1) f(freerun)  = 2.0 => rampup base_rate reasonably fast
+	 * (2) f(setpoint) = 1.0 => the balance point
+	 * (3) f(limit)    = 0   => the hard limit
+	 * (4) df/dx      <= 0	 => negative feedback control
+	 * (5) the closer to setpoint, the smaller |df/dx| (and the reverse)
+	 *     => fast response on large errors; small oscillation near setpoint
+	 */
+	setpoint = (freerun + limit) / 2;
+	x = div_s64((setpoint - dirty) << RATELIMIT_CALC_SHIFT,
+		    limit - setpoint + 1);
+	pos_ratio = x;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio += 1 << RATELIMIT_CALC_SHIFT;
+
+	/*
+	 * We have computed basic pos_ratio above based on global situation. If
+	 * the bdi is over/under its share of dirty pages, we want to scale
+	 * pos_ratio further down/up. That is done by the following policies:
+	 *
+	 * For single bdi case, the dirty pages are observed to fluctuate
+	 * regularly within range
+	 *        [bdi_setpoint - write_bw/2, bdi_setpoint + write_bw/2]
+	 * for various filesystems, so choose a slope that can yield in a
+	 * reasonable 12.5% fluctuation range for pos_ratio.
+	 *
+	 * For JBOD case, bdi_thresh (not bdi_dirty!) could fluctuate up to its
+	 * own size, so move the slope over accordingly and choose a slope that
+	 * yields 50% pos_ratio fluctuation when bdi_thresh is suddenly doubled.
+	 */
+
+	/*
+	 * bdi setpoint
+	 *
+	 *        f(bdi_dirty) := 1.0 + k * (bdi_dirty - bdi_setpoint)
+	 *
+	 *                        x_intercept - bdi_dirty
+	 *                     := --------------------------
+	 *                        x_intercept - bdi_setpoint
+	 *
+	 * The main bdi control line is a linear function that subjects to
+	 *
+	 * (1) f(bdi_setpoint) = 1.0
+	 * (2) k = - 1 / (8 * write_bw)  (in single bdi case)
+	 *     or equally: x_intercept = bdi_setpoint + 8 * write_bw
+	 */
+	if (unlikely(bdi_thresh > thresh))
+		bdi_thresh = thresh;
+	/*
+	 * scale global setpoint to bdi's:
+	 * 	bdi_setpoint = setpoint * bdi_thresh / thresh
+	 */
+	x = div_u64((u64)bdi_thresh << 16, thresh + 1);
+	bdi_setpoint = setpoint * (u64)x >> 16;
+	/*
+	 * Use span=(4*write_bw) in single bdi case as indicated by
+	 * (thresh - bdi_thresh ~= 0) and transit to bdi_thresh in JBOD case.
+	 *
+	 *        bdi_thresh                  thresh - bdi_thresh
+	 * span = ---------- * (4*write_bw) + ------------------- * bdi_thresh
+	 *          thresh                          thresh
+	 */
+	span = (thresh - bdi_thresh + 4 * bdi->avg_write_bandwidth) *
+								(u64)x >> 16;
+	x_intercept = bdi_setpoint + 2 * span;
+
+	if (unlikely(bdi_dirty > bdi_setpoint + span)) {
+		if (unlikely(bdi_dirty > limit))
+			return 0;
+		if (x_intercept < limit) {
+			x_intercept = limit;	/* auxiliary control line */
+			bdi_setpoint += span;
+			pos_ratio >>= 1;
+		}
+	}
+	pos_ratio *= x_intercept - bdi_dirty;
+	do_div(pos_ratio, x_intercept - bdi_setpoint + 1);
+
+	return pos_ratio;
+}
+
 static void bdi_update_write_bandwidth(struct backing_dev_info *bdi,
 				       unsigned long elapsed,
 				       unsigned long written)

@@ -593,6 +791,7 @@ static void global_update_bandwidth(unsi
 
 void __bdi_update_bandwidth(struct backing_dev_info *bdi,
 			    unsigned long thresh,
+			    unsigned long bg_thresh,
 			    unsigned long dirty,
 			    unsigned long bdi_thresh,
 			    unsigned long bdi_dirty,

@@ -629,6 +828,7 @@ snapshot:
 
 static void bdi_update_bandwidth(struct backing_dev_info *bdi,
 				 unsigned long thresh,
+				 unsigned long bg_thresh,
 				 unsigned long dirty,
 				 unsigned long bdi_thresh,
 				 unsigned long bdi_dirty,

@@ -637,8 +837,8 @@ static void bdi_update_bandwidth(struct 
 	if (time_is_after_eq_jiffies(bdi->bw_time_stamp + BANDWIDTH_INTERVAL))
 		return;
 	spin_lock(&bdi->wb.list_lock);
-	__bdi_update_bandwidth(bdi, thresh, dirty, bdi_thresh, bdi_dirty,
-			       start_time);
+	__bdi_update_bandwidth(bdi, thresh, bg_thresh, dirty,
+			       bdi_thresh, bdi_dirty, start_time);
 	spin_unlock(&bdi->wb.list_lock);
 }
 

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

@@ -723,8 +924,9 @@ static void balance_dirty_pages(struct a
 		if (!bdi->dirty_exceeded)
 			bdi->dirty_exceeded = 1;
 
-		bdi_update_bandwidth(bdi, dirty_thresh, nr_dirty,
-				     bdi_thresh, bdi_dirty, start_time);
+		bdi_update_bandwidth(bdi, dirty_thresh, background_thresh,
+				     nr_dirty, bdi_thresh, bdi_dirty,
+				     start_time);
 
 		/* Note: nr_reclaimable denotes nr_dirty + nr_unstable.
 		 * Unstable writes are a feature of certain networked

fs/fs-writeback.c +1 -1

@@ -670,7 +670,7 @@ static inline bool over_bground_thresh(v
 static void wb_update_bandwidth(struct bdi_writeback *wb,
 				unsigned long start_time)
 {
-	__bdi_update_bandwidth(wb->bdi, 0, 0, 0, 0, start_time);
+	__bdi_update_bandwidth(wb->bdi, 0, 0, 0, 0, 0, start_time);
 }
 
 /*

include/linux/writeback.h +1 -0

@@ -154,6 +154,7 @@ unsigned long bdi_dirty_limit(struct bac
 
 void __bdi_update_bandwidth(struct backing_dev_info *bdi,
 			    unsigned long thresh,
+			    unsigned long bg_thresh,
 			    unsigned long dirty,
 			    unsigned long bdi_thresh,
 			    unsigned long bdi_dirty,

Quoted 1 line

Quoted 1 line

Review

Quoted 1 line

(quoted diff) +1 -0

+	x_intercept = setpoint + 2 * span;

^^ BTW, why do you have 2*span here? It can result in x_intercept being
~3*bdi_thresh... So maybe you should use bdi_thresh/2 in the computation of span?

mm/page-writeback.c +149 -0

+/*
+ * Dirty position control.
+ *
+ * (o) global/bdi setpoints
+ *
+ * We want the dirty pages be balanced around the global/bdi setpoints.
+ * When the number of dirty pages is higher/lower than the setpoint, the
+ * dirty position control ratio (and hence task dirty ratelimit) will be
+ * decreased/increased to bring the dirty pages back to the setpoint.
+ *
+ *     pos_ratio = 1 << RATELIMIT_CALC_SHIFT
+ *
+ *     if (dirty < setpoint) scale up   pos_ratio
+ *     if (dirty > setpoint) scale down pos_ratio
+ *
+ *     if (bdi_dirty < bdi_setpoint) scale up   pos_ratio
+ *     if (bdi_dirty > bdi_setpoint) scale down pos_ratio
+ *
+ *     task_ratelimit = balanced_rate * pos_ratio >> RATELIMIT_CALC_SHIFT
+ *
+ * (o) global control line
+ *
+ *     ^ pos_ratio
+ *     |
+ *     |            |<===== global dirty control scope ======>|
+ * 2.0 .............*
+ *     |            .*
+ *     |            . *
+ *     |            .   *
+ *     |            .     *
+ *     |            .        *
+ *     |            .            *
+ * 1.0 ................................*
+ *     |            .                  .     *
+ *     |            .                  .          *
+ *     |            .                  .              *
+ *     |            .                  .                 *
+ *     |            .                  .                    *
+ *   0 +------------.------------------.----------------------*------------->
+ *           freerun^          setpoint^                 limit^   dirty pages
+ *
+ * (o) bdi control lines
+ *
+ * The control lines for the global/bdi setpoints both stretch up to @limit.
+ * The below figure illustrates the main bdi control line with an auxiliary
+ * line extending it to @limit.
+ *
+ *   o
+ *     o
+ *       o                                      [o] main control line
+ *         o                                    [*] auxiliary control line
+ *           o
+ *             o
+ *               o
+ *                 o
+ *                   o
+ *                     o
+ *                       o--------------------- balance point, rate scale = 1
+ *                       | o
+ *                       |   o
+ *                       |     o
+ *                       |       o
+ *                       |         o
+ *                       |           o
+ *                       |             o------- connect point, rate scale = 1/2
+ *                       |               .*
+ *                       |                 .   *
+ *                       |                   .      *
+ *                       |                     .         *
+ *                       |                       .           *
+ *                       |                         .              *
+ *                       |                           .                 *
+ *  [--------------------+-----------------------------.--------------------*]
+ *  0                 setpoint                     x_intercept           limit
+ *
+ * The auxiliary control line allows smoothly throttling bdi_dirty down to
+ * normal if it starts high in situations like
+ * - start writing to a slow SD card and a fast disk at the same time. The SD
+ *   card's bdi_dirty may rush to many times higher than bdi setpoint.
+ * - the bdi dirty thresh drops quickly due to change of JBOD workload
+ */
+static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
+					unsigned long thresh,
+					unsigned long bg_thresh,
+					unsigned long dirty,
+					unsigned long bdi_thresh,
+					unsigned long bdi_dirty)
+{
+	unsigned long freerun = dirty_freerun_ceiling(thresh, bg_thresh);
+	unsigned long limit = hard_dirty_limit(thresh);
+	unsigned long x_intercept;
+	unsigned long setpoint;		/* the target balance point */
+	unsigned long span;
+	long long pos_ratio;		/* for scaling up/down the rate limit */
+	long x;
+
+	if (unlikely(dirty >= limit))
+		return 0;
+
+	/*
+	 * global setpoint
+	 *
+	 *                         setpoint - dirty 3
+	 *        f(dirty) := 1 + (----------------)
+	 *                         limit - setpoint
+	 *
+	 * it's a 3rd order polynomial that subjects to
+	 *
+	 * (1) f(freerun)  = 2.0 => rampup base_rate reasonably fast
+	 * (2) f(setpoint) = 1.0 => the balance point
+	 * (3) f(limit)    = 0   => the hard limit
+	 * (4) df/dx       < 0	 => negative feedback control
+	 * (5) the closer to setpoint, the smaller |df/dx| (and the reverse)
+	 *     => fast response on large errors; small oscillation near setpoint
+	 */
+	setpoint = (freerun + limit) / 2;
+	x = div_s64((setpoint - dirty) << RATELIMIT_CALC_SHIFT,
+		    limit - setpoint + 1);
+	pos_ratio = x;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio += 1 << RATELIMIT_CALC_SHIFT;
+
+	/*
+	 * bdi setpoint
+	 *
+	 *        f(dirty) := 1.0 + k * (dirty - setpoint)
+	 *
+	 * The main bdi control line is a linear function that subjects to
+	 *
+	 * (1) f(setpoint) = 1.0
+	 * (2) k = - 1 / (8 * write_bw)  (in single bdi case)
+	 *     or equally: x_intercept = setpoint + 8 * write_bw
+	 *
+	 * For single bdi case, the dirty pages are observed to fluctuate
+	 * regularly within range
+	 *        [setpoint - write_bw/2, setpoint + write_bw/2]
+	 * for various filesystems, where (2) can yield in a reasonable 12.5%
+	 * fluctuation range for pos_ratio.
+	 *
+	 * For JBOD case, bdi_thresh (not bdi_dirty!) could fluctuate up to its
+	 * own size, so move the slope over accordingly.
+	 */
+	if (unlikely(bdi_thresh > thresh))
+		bdi_thresh = thresh;
+	/*
+	 * scale global setpoint to bdi's:  setpoint *= bdi_thresh / thresh
+	 */
+	x = div_u64((u64)bdi_thresh << 16, thresh | 1);

On Tue, Aug 16, 2011 at 10:20:08AM +0800, Wu Fengguang wrote:

[..]

Quoted 149 lines

mm/page-writeback.c +149 -0

+/*
+ * Dirty position control.
+ *
+ * (o) global/bdi setpoints
+ *
+ * We want the dirty pages be balanced around the global/bdi setpoints.
+ * When the number of dirty pages is higher/lower than the setpoint, the
+ * dirty position control ratio (and hence task dirty ratelimit) will be
+ * decreased/increased to bring the dirty pages back to the setpoint.
+ *
+ *     pos_ratio = 1 << RATELIMIT_CALC_SHIFT
+ *
+ *     if (dirty < setpoint) scale up   pos_ratio
+ *     if (dirty > setpoint) scale down pos_ratio
+ *
+ *     if (bdi_dirty < bdi_setpoint) scale up   pos_ratio
+ *     if (bdi_dirty > bdi_setpoint) scale down pos_ratio
+ *
+ *     task_ratelimit = balanced_rate * pos_ratio >> RATELIMIT_CALC_SHIFT
+ *
+ * (o) global control line
+ *
+ *     ^ pos_ratio
+ *     |
+ *     |            |<===== global dirty control scope ======>|
+ * 2.0 .............*
+ *     |            .*
+ *     |            . *
+ *     |            .   *
+ *     |            .     *
+ *     |            .        *
+ *     |            .            *
+ * 1.0 ................................*
+ *     |            .                  .     *
+ *     |            .                  .          *
+ *     |            .                  .              *
+ *     |            .                  .                 *
+ *     |            .                  .                    *
+ *   0 +------------.------------------.----------------------*------------->
+ *           freerun^          setpoint^                 limit^   dirty pages
+ *
+ * (o) bdi control lines
+ *
+ * The control lines for the global/bdi setpoints both stretch up to @limit.
+ * The below figure illustrates the main bdi control line with an auxiliary
+ * line extending it to @limit.
+ *
+ *   o
+ *     o
+ *       o                                      [o] main control line
+ *         o                                    [*] auxiliary control line
+ *           o
+ *             o
+ *               o
+ *                 o
+ *                   o
+ *                     o
+ *                       o--------------------- balance point, rate scale = 1
+ *                       | o
+ *                       |   o
+ *                       |     o
+ *                       |       o
+ *                       |         o
+ *                       |           o
+ *                       |             o------- connect point, rate scale = 1/2
+ *                       |               .*
+ *                       |                 .   *
+ *                       |                   .      *
+ *                       |                     .         *
+ *                       |                       .           *
+ *                       |                         .              *
+ *                       |                           .                 *
+ *  [--------------------+-----------------------------.--------------------*]
+ *  0                 setpoint                     x_intercept           limit
+ *
+ * The auxiliary control line allows smoothly throttling bdi_dirty down to
+ * normal if it starts high in situations like
+ * - start writing to a slow SD card and a fast disk at the same time. The SD
+ *   card's bdi_dirty may rush to many times higher than bdi setpoint.
+ * - the bdi dirty thresh drops quickly due to change of JBOD workload
+ */
+static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
+					unsigned long thresh,
+					unsigned long bg_thresh,
+					unsigned long dirty,
+					unsigned long bdi_thresh,
+					unsigned long bdi_dirty)
+{
+	unsigned long freerun = dirty_freerun_ceiling(thresh, bg_thresh);
+	unsigned long limit = hard_dirty_limit(thresh);
+	unsigned long x_intercept;
+	unsigned long setpoint;		/* the target balance point */
+	unsigned long span;
+	long long pos_ratio;		/* for scaling up/down the rate limit */
+	long x;
+
+	if (unlikely(dirty >= limit))
+		return 0;
+
+	/*
+	 * global setpoint
+	 *
+	 *                         setpoint - dirty 3
+	 *        f(dirty) := 1 + (----------------)
+	 *                         limit - setpoint
+	 *
+	 * it's a 3rd order polynomial that subjects to
+	 *
+	 * (1) f(freerun)  = 2.0 => rampup base_rate reasonably fast
+	 * (2) f(setpoint) = 1.0 => the balance point
+	 * (3) f(limit)    = 0   => the hard limit
+	 * (4) df/dx       < 0	 => negative feedback control
+	 * (5) the closer to setpoint, the smaller |df/dx| (and the reverse)
+	 *     => fast response on large errors; small oscillation near setpoint
+	 */
+	setpoint = (freerun + limit) / 2;
+	x = div_s64((setpoint - dirty) << RATELIMIT_CALC_SHIFT,
+		    limit - setpoint + 1);
+	pos_ratio = x;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
+	pos_ratio += 1 << RATELIMIT_CALC_SHIFT;
+
+	/*
+	 * bdi setpoint
+	 *
+	 *        f(dirty) := 1.0 + k * (dirty - setpoint)
+	 *
+	 * The main bdi control line is a linear function that subjects to
+	 *
+	 * (1) f(setpoint) = 1.0
+	 * (2) k = - 1 / (8 * write_bw)  (in single bdi case)
+	 *     or equally: x_intercept = setpoint + 8 * write_bw
+	 *
+	 * For single bdi case, the dirty pages are observed to fluctuate
+	 * regularly within range
+	 *        [setpoint - write_bw/2, setpoint + write_bw/2]
+	 * for various filesystems, where (2) can yield in a reasonable 12.5%
+	 * fluctuation range for pos_ratio.
+	 *
+	 * For JBOD case, bdi_thresh (not bdi_dirty!) could fluctuate up to its
+	 * own size, so move the slope over accordingly.
+	 */
+	if (unlikely(bdi_thresh > thresh))
+		bdi_thresh = thresh;
+	/*
+	 * scale global setpoint to bdi's:  setpoint *= bdi_thresh / thresh
+	 */
+	x = div_u64((u64)bdi_thresh << 16, thresh | 1);

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

Quoted 10 lines

mm/page-writeback.c +10 -0

+	setpoint = setpoint * (u64)x >> 16;
+	/*
+	 * Use span=(4*write_bw) in single bdi case as indicated by
+	 * (thresh - bdi_thresh ~= 0) and transit to bdi_thresh in JBOD case.
+	 */
+	span = div_u64((u64)bdi_thresh * (thresh - bdi_thresh) +
+		       (u64)(4 * bdi->avg_write_bandwidth) * bdi_thresh,
+		       thresh + 1);
+	x_intercept = setpoint + 2 * span;
+

Hi Fengguang,

Few very basic queries.

- Why can't we use the same formula for bdi position ratio as gloabl position ratio. Are you not looking for similar proporties. Near the set point variation is less and away from setup poing throttling is faster.

- In the bdi calculation, setpoint seems to be in number of pages and limit (x_intercept) seems to be a combination of nr pages + pages/sec. Why it is different from gloabl setpoint and limit. I mean could this not have been like global calculation where we try to keep bdi_dirty close to bdi_thresh and calculate pos_ratio.

- In global pos_ratio calculation terminology used is "limit" while the same thing seems be being meintioned as x_intercept in bdi position ratio calculation.

Add two fields to task_struct.

1) account dirtied pages in the individual tasks, for accuracy
2) per-task balance_dirty_pages() call intervals, for flexibility

The balance_dirty_pages() call interval (ie. nr_dirtied_pause) will scale near-sqrt to the safety gap between dirty pages and threshold.

The main problem of per-task nr_dirtied is, if 1k+ tasks start dirtying pages at exactly the same time, each task will be assigned a large initial nr_dirtied_pause, so that the dirty threshold will be exceeded long before each task reached its nr_dirtied_pause and hence call balance_dirty_pages().

The solution is to watch for the number of pages dirtied on each CPU in between the calls into balance_dirty_pages(). If it exceeds ratelimit_pages (3% dirty threshold), force call balance_dirty_pages() for a chance to set bdi->dirty_exceeded. In normal situations, this safeguarding condition is not expected to trigger at all.

peter: keep the per-CPU ratelimit for safeguarding the 1k+ tasks case

CC Peter Zijlstra <[email protected]>

Reviewed-by Andrea Righi <[email protected]>

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

---
 include/linux/sched.h |    7 +++
 kernel/fork.c         |    3 +
 mm/page-writeback.c   |   90 ++++++++++++++++++++++------------------
 3 files changed, 61 insertions(+), 39 deletions(-)

include/linux/sched.h +7 -0

@@ -1525,6 +1525,13 @@ struct task_struct {
 	int make_it_fail;
 #endif
 	struct prop_local_single dirties;
+	/*
+	 * when (nr_dirtied >= nr_dirtied_pause), it's time to call
+	 * balance_dirty_pages() for some dirty throttling pause
+	 */
+	int nr_dirtied;
+	int nr_dirtied_pause;
+
 #ifdef CONFIG_LATENCYTOP
 	int latency_record_count;
 	struct latency_record latency_record[LT_SAVECOUNT];

mm/page-writeback.c +25 -17

@@ -54,20 +54,6 @@
  */
 static long ratelimit_pages = 32;
 
-/*
- * When balance_dirty_pages decides that the caller needs to perform some
- * non-background writeback, this is how many pages it will attempt to write.
- * It should be somewhat larger than dirtied pages to ensure that reasonably
- * large amounts of I/O are submitted.
- */
-static inline long sync_writeback_pages(unsigned long dirtied)
-{
-	if (dirtied < ratelimit_pages)
-		dirtied = ratelimit_pages;
-
-	return dirtied + dirtied / 2;
-}
-
 /* The following parameters are exported via /proc/sys/vm */
 
 /*

@@ -169,6 +155,8 @@ static void update_completion_period(voi
 	int shift = calc_period_shift();
 	prop_change_shift(&vm_completions, shift);
 	prop_change_shift(&vm_dirties, shift);
+
+	writeback_set_ratelimit();
 }
 
 int dirty_background_ratio_handler(struct ctl_table *table, int write,

@@ -930,6 +918,23 @@ static void bdi_update_bandwidth(struct 
 }
 
 /*
+ * After a task dirtied this many pages, balance_dirty_pages_ratelimited_nr()
+ * will look to see if it needs to start dirty throttling.
+ *
+ * If dirty_poll_interval is too low, big NUMA machines will call the expensive
+ * global_page_state() too often. So scale it near-sqrt to the safety margin
+ * (the number of pages we may dirty without exceeding the dirty limits).
+ */
+static unsigned long dirty_poll_interval(unsigned long dirty,
+					 unsigned long thresh)
+{
+	if (thresh > dirty)
+		return 1UL << (ilog2(thresh - dirty) >> 1);
+
+	return 1;
+}
+
+/*
  * 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
  * the caller to perform writeback if the system is over `vm_dirty_ratio'.

@@ -1072,6 +1077,9 @@ static void balance_dirty_pages(struct a
 	if (clear_dirty_exceeded && bdi->dirty_exceeded)
 		bdi->dirty_exceeded = 0;
 
+	current->nr_dirtied = 0;
+	current->nr_dirtied_pause = dirty_poll_interval(nr_dirty, dirty_thresh);
+
 	if (writeback_in_progress(bdi))
 		return;
 

@@ -1098,7 +1106,7 @@ void set_page_dirty_balance(struct page 
 	}
 }
 
-static DEFINE_PER_CPU(unsigned long, bdp_ratelimits) = 0;
+static DEFINE_PER_CPU(int, bdp_ratelimits);
 
 /**
  * balance_dirty_pages_ratelimited_nr - balance dirty memory state

@@ -1118,31 +1126,40 @@ void balance_dirty_pages_ratelimited_nr(
 					unsigned long nr_pages_dirtied)
 {
 	struct backing_dev_info *bdi = mapping->backing_dev_info;
-	unsigned long ratelimit;
-	unsigned long *p;
+	int ratelimit;
+	int *p;
 

mm/page-writeback.c +22 -19

+
+	current->nr_dirtied += nr_pages_dirtied;
 
+	preempt_disable();
 	/*
-	 * Check the rate limiting. Also, we do not want to throttle real-time
-	 * tasks in balance_dirty_pages(). Period.
+	 * This prevents one CPU to accumulate too many dirtied pages without
+	 * calling into balance_dirty_pages(), which can happen when there are
+	 * 1000+ tasks, all of them start dirtying pages at exactly the same
+	 * time, hence all honoured too large initial task->nr_dirtied_pause.
 	 */
-	preempt_disable();
 	p =  &__get_cpu_var(bdp_ratelimits);
-	*p += nr_pages_dirtied;
-	if (unlikely(*p >= ratelimit)) {
-		ratelimit = sync_writeback_pages(*p);
+	if (unlikely(current->nr_dirtied >= ratelimit))
 		*p = 0;
-		preempt_enable();
-		balance_dirty_pages(mapping, ratelimit);
-		return;
+	else {
+		*p += nr_pages_dirtied;
+		if (unlikely(*p >= ratelimit_pages)) {
+			*p = 0;
+			ratelimit = 0;
+		}
 	}
 	preempt_enable();
+
+	if (unlikely(current->nr_dirtied >= ratelimit))
+		balance_dirty_pages(mapping, current->nr_dirtied);
 }
 EXPORT_SYMBOL(balance_dirty_pages_ratelimited_nr);
 

@@ -1237,22 +1254,17 @@ void laptop_sync_completion(void)
  *
  * Here we set ratelimit_pages to a level which ensures that when all CPUs are
  * dirtying in parallel, we cannot go more than 3% (1/32) over the dirty memory
- * thresholds before writeback cuts in.
- *
- * But the limit should not be set too high.  Because it also controls the
- * amount of memory which the balance_dirty_pages() caller has to write back.
- * If this is too large then the caller will block on the IO queue all the
- * time.  So limit it to four megabytes - the balance_dirty_pages() caller
- * will write six megabyte chunks, max.
+ * thresholds.
  */
 
 void writeback_set_ratelimit(void)
 {
-	ratelimit_pages = vm_total_pages / (num_online_cpus() * 32);
+	unsigned long background_thresh;
+	unsigned long dirty_thresh;
+	global_dirty_limits(&background_thresh, &dirty_thresh);
+	ratelimit_pages = dirty_thresh / (num_online_cpus() * 32);
 	if (ratelimit_pages < 16)
 		ratelimit_pages = 16;
-	if (ratelimit_pages * PAGE_CACHE_SIZE > 4096 * 1024)
-		ratelimit_pages = (4096 * 1024) / PAGE_CACHE_SIZE;
 }
 
 static int __cpuinit

mm/page-writeback.c void balance_dirty_pages_ratelimited_nr( · line 1138

Quoted 4 lines

mm/page-writeback.c +4 -0

+	if (!bdi->dirty_exceeded)
+		ratelimit = current->nr_dirtied_pause;
+	else
+		ratelimit = min(ratelimit, 32 >> (PAGE_SHIFT - 10));

Usage of ratelimit before init?

Maybe:

	ratelimit = current->nr_dirtied_pause;
	if (bdi->dirty_exceeded)
		ratelimit = min(ratelimit, 32 >> (PAGE_SHIFT - 10));

mm/page-writeback.c +4 -16

+		if (dirty_exceeded && !bdi->dirty_exceeded)
 			bdi->dirty_exceeded = 1;
 
 		bdi_update_bandwidth(bdi, dirty_thresh, background_thresh,
 				     nr_dirty, bdi_thresh, bdi_dirty,
 				     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
-		 * written to the server's write cache, but has not yet
-		 * been flushed to permanent storage.
-		 * Only move pages to writeback if this bdi is over its
-		 * threshold otherwise wait until the disk writes catch
-		 * up.
-		 */
-		trace_balance_dirty_start(bdi);
-		if (bdi_nr_reclaimable > task_bdi_thresh) {
-			pages_written += writeback_inodes_wb(&bdi->wb,
-							     write_chunk);
-			trace_balance_dirty_written(bdi, pages_written);
-			if (pages_written >= write_chunk)
-				break;		/* We've done our duty */
+		if (unlikely(!writeback_in_progress(bdi)))
+			bdi_start_background_writeback(bdi);
+

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

Quoted 10 lines

mm/page-writeback.c +9 -0

+		base_rate = bdi->dirty_ratelimit;
+		pos_ratio = bdi_position_ratio(bdi, dirty_thresh,
+					       background_thresh, nr_dirty,
+					       bdi_thresh, bdi_dirty);
+		if (unlikely(pos_ratio == 0)) {
+			pause = MAX_PAUSE;
+			goto pause;
 		}
+		task_ratelimit = (u64)base_rate *
+					pos_ratio >> RATELIMIT_CALC_SHIFT;

Hi Fenguaang,

I am little confused here. I see that you have already taken pos_ratio into account in bdi_update_dirty_ratelimit() and wondering why to take that into account again in balance_diry_pages().

We calculated the pos_rate and balanced_rate and adjusted the bdi->dirty_ratelimit accordingly in bdi_update_dirty_ratelimit().

Hi Vivek,

Quoted 13 lines

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

Quoted 10 lines

mm/page-writeback.c +9 -0

+		base_rate = bdi->dirty_ratelimit;
+		pos_ratio = bdi_position_ratio(bdi, dirty_thresh,
+					       background_thresh, nr_dirty,
+					       bdi_thresh, bdi_dirty);
+		if (unlikely(pos_ratio == 0)) {
+			pause = MAX_PAUSE;
+			goto pause;
 		}
+		task_ratelimit = (u64)base_rate *
+					pos_ratio >> RATELIMIT_CALC_SHIFT;

Hi Fenguaang,

Quoted 6 lines

I am little confused here. I see that you have already taken pos_ratio into account in bdi_update_dirty_ratelimit() and wondering why to take that into account again in balance_diry_pages().

We calculated the pos_rate and balanced_rate and adjusted the bdi->dirty_ratelimit accordingly in bdi_update_dirty_ratelimit().

Good question. There are some inter-dependencies in the calculation, and the dependency chain is the opposite to the one in your mind:
balance_dirty_pages() used pos_ratio in the first place, so that bdi_update_dirty_ratelimit() have to use pos_ratio in the calculation of the balanced dirty rate, too.

Let's return to how the balanced dirty rate is estimated. Please pay special attention to the last paragraphs below the "......" line.

Start by throttling each dd task at rate

task_ratelimit = task_ratelimit_0 (1)
(any non-zero initial value is OK)

After 200ms, we measured

dirty_rate = # of pages dirtied by all dd's / 200ms
write_bw = # of pages written to the disk / 200ms

For the aggressive dd dirtiers, the equality holds

        dirty_rate == N * task_rate
                   == N * task_ratelimit
                   == N * task_ratelimit_0                              (2)

Or
task_ratelimit_0 = dirty_rate / N (3)

Now we conclude that the balanced task ratelimit can be estimated by

balanced_rate = task_ratelimit_0 * (write_bw / dirty_rate) (4)

Because with (2) and (3), (4) yields the desired equality (1):

        balanced_rate == (dirty_rate / N) * (write_bw / dirty_rate)
                      == write_bw / N

.............................................................................

Now let's revisit (1). Since balance_dirty_pages() chooses to execute the ratelimit

task_ratelimit = task_ratelimit_0
= dirty_ratelimit * pos_ratio (5)

Put (5) into (4), we get the final form used in
bdi_update_dirty_ratelimit()

balanced_rate = (dirty_ratelimit * pos_ratio) * (write_bw / dirty_rate)

So you really need to take (dirty_ratelimit * pos_ratio) as a single entity.

Quoted 49 lines · Wu Fengguang

Hi Vivek,

Quoted 13 lines

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

Quoted 10 lines

mm/page-writeback.c +9 -0

+		base_rate = bdi->dirty_ratelimit;
+		pos_ratio = bdi_position_ratio(bdi, dirty_thresh,
+					       background_thresh, nr_dirty,
+					       bdi_thresh, bdi_dirty);
+		if (unlikely(pos_ratio == 0)) {
+			pause = MAX_PAUSE;
+			goto pause;
 		}
+		task_ratelimit = (u64)base_rate *
+					pos_ratio >> RATELIMIT_CALC_SHIFT;

Hi Fenguaang,

Quoted 6 lines

I am little confused here. I see that you have already taken pos_ratio into account in bdi_update_dirty_ratelimit() and wondering why to take that into account again in balance_diry_pages().

We calculated the pos_rate and balanced_rate and adjusted the bdi->dirty_ratelimit accordingly in bdi_update_dirty_ratelimit().

Good question. There are some inter-dependencies in the calculation, and the dependency chain is the opposite to the one in your mind:
balance_dirty_pages() used pos_ratio in the first place, so that bdi_update_dirty_ratelimit() have to use pos_ratio in the calculation of the balanced dirty rate, too.

Let's return to how the balanced dirty rate is estimated. Please pay special attention to the last paragraphs below the "......" line.

Start by throttling each dd task at rate

task_ratelimit = task_ratelimit_0 (1)
(any non-zero initial value is OK)

After 200ms, we measured

dirty_rate = # of pages dirtied by all dd's / 200ms
write_bw = # of pages written to the disk / 200ms

For the aggressive dd dirtiers, the equality holds

        dirty_rate == N * task_rate
                   == N * task_ratelimit
                   == N * task_ratelimit_0                              (2)

Or
task_ratelimit_0 = dirty_rate / N (3)

Quoted 8 lines

Now we conclude that the balanced task ratelimit can be estimated by

balanced_rate = task_ratelimit_0 * (write_bw / dirty_rate) (4)

Because with (2) and (3), (4) yields the desired equality (1):

        balanced_rate == (dirty_rate / N) * (write_bw / dirty_rate)
                      == write_bw / N

Hi Fengguang,

Following is my understanding. Please correct me where I got it wrong.

Ok, I think I follow till this point. I think what you are saying is that following is our goal in a stable system.

	task_ratelimit = write_bw/N				(6)

So we measure the write_bw of a bdi over a period of time and use that as feedback loop to modify bdi->dirty_ratelimit which inturn modifies task_ratelimit and hence we achieve the balance. So we will start with some arbitrary task limit say task_ratelimit_0, and modify that limit over a period of time based on our feedback loop to achieve a balanced system. And following seems to be the formula.

					    write_bw
	task_ratelimit = task_ratelimit_0 * ------- 		(7)
					    dirty_rate

Now I also understand that by using (2) and (3), you proved that how (7) will lead to (6) and that is our deisred goal.

Quoted 9 lines

.............................................................................

Now let's revisit (1). Since balance_dirty_pages() chooses to execute the ratelimit

task_ratelimit = task_ratelimit_0
= dirty_ratelimit * pos_ratio (5)

So balance_drity_pages() chose to take into account pos_ratio() also because for various reason like just taking into account only bandwidth variation as feedback was not sufficient. So we also took pos_ratio into account which in-trun is dependent on gloabal dirty pages and per bdi dirty_pages/rate.

So we refined the formula for calculating a tasks's effective rate over a period of time to following.

					    write_bw
	task_ratelimit = task_ratelimit_0 * ------- * pos_ratio		(9)
					    dirty_rate

Quoted 6 lines

Put (5) into (4), we get the final form used in
bdi_update_dirty_ratelimit()

balanced_rate = (dirty_ratelimit * pos_ratio) * (write_bw / dirty_rate)

So you really need to take (dirty_ratelimit * pos_ratio) as a single entity.

Now few questions.

- What is dirty_ratelimit in formula above?

- Is it wrong to understand the issue in following manner.

bdi->dirty_ratelimit is tracking write bandwidth variation on the bdi and effectively tracks write_bw/N.

bdi->dirty_ratelimit = write_bw/N

or

write_bw
bdi->dirty_ratelimit = previous_bdi->dirty_ratelimit * ------------- (10)
dirty_rate

Hence a tasks's balanced rate from (9) and (10) is.

task_ratelimit = bdi->dirty_ratelimit * pos_ratio (11)
So my understanding about (10) and (11) is wrong? if no, then question comes that

bdi->dirty_ratelimit is supposed to be keeping track of write bandwidth variations only.

And in turn task ratelimit will be
driven by both bandwidth varation as well as pos_ratio variation.

But you seem to be doing following.

bdi->dirty_ratelimit = adjust based on a cobination of bandwidth feedback
and pos_ratio feedback.

task_ratelimit = bdi->dirty_ratelimit * pos_ratio (12)

So my question is that when task_ratelimit is finally being adjusted based on pos_ratio feedback, why bdi->dirty_ratelimit also needs to take that into account.

I know you have tried explaining it, but sorry, I did not get it. May be give it another shot in a layman's terms and I might understand it.

Quoted 74 lines · Vivek Goyal

Quoted 49 lines · Wu Fengguang

Hi Vivek,

Quoted 13 lines

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

Quoted 10 lines

mm/page-writeback.c +9 -0

+		base_rate = bdi->dirty_ratelimit;
+		pos_ratio = bdi_position_ratio(bdi, dirty_thresh,
+					       background_thresh, nr_dirty,
+					       bdi_thresh, bdi_dirty);
+		if (unlikely(pos_ratio == 0)) {
+			pause = MAX_PAUSE;
+			goto pause;
 		}
+		task_ratelimit = (u64)base_rate *
+					pos_ratio >> RATELIMIT_CALC_SHIFT;

Hi Fenguaang,

Quoted 6 lines

I am little confused here. I see that you have already taken pos_ratio into account in bdi_update_dirty_ratelimit() and wondering why to take that into account again in balance_diry_pages().

We calculated the pos_rate and balanced_rate and adjusted the bdi->dirty_ratelimit accordingly in bdi_update_dirty_ratelimit().

Good question. There are some inter-dependencies in the calculation, and the dependency chain is the opposite to the one in your mind:
balance_dirty_pages() used pos_ratio in the first place, so that bdi_update_dirty_ratelimit() have to use pos_ratio in the calculation of the balanced dirty rate, too.

Let's return to how the balanced dirty rate is estimated. Please pay special attention to the last paragraphs below the "......" line.

Start by throttling each dd task at rate

task_ratelimit = task_ratelimit_0 (1)
(any non-zero initial value is OK)

After 200ms, we measured

dirty_rate = # of pages dirtied by all dd's / 200ms
write_bw = # of pages written to the disk / 200ms

For the aggressive dd dirtiers, the equality holds

        dirty_rate == N * task_rate
                   == N * task_ratelimit
                   == N * task_ratelimit_0                              (2)

Or
task_ratelimit_0 = dirty_rate / N (3)

Quoted 8 lines

Now we conclude that the balanced task ratelimit can be estimated by

balanced_rate = task_ratelimit_0 * (write_bw / dirty_rate) (4)

Because with (2) and (3), (4) yields the desired equality (1):

        balanced_rate == (dirty_rate / N) * (write_bw / dirty_rate)
                      == write_bw / N

Hi Fengguang,

Following is my understanding. Please correct me where I got it wrong.

Ok, I think I follow till this point. I think what you are saying is that following is our goal in a stable system.

	task_ratelimit = write_bw/N				(6)

So we measure the write_bw of a bdi over a period of time and use that as feedback loop to modify bdi->dirty_ratelimit which inturn modifies task_ratelimit and hence we achieve the balance. So we will start with some arbitrary task limit say task_ratelimit_0, and modify that limit over a period of time based on our feedback loop to achieve a balanced system. And following seems to be the formula.

Quoted 6 lines

					    write_bw
	task_ratelimit = task_ratelimit_0 * ------- 		(7)
					    dirty_rate

Now I also understand that by using (2) and (3), you proved that how (7) will lead to (6) and that is our deisred goal.

That's right.

Quoted 10 lines

Quoted 9 lines

.............................................................................

Now let's revisit (1). Since balance_dirty_pages() chooses to execute the ratelimit

task_ratelimit = task_ratelimit_0
= dirty_ratelimit * pos_ratio (5)

Quoted 5 lines

So balance_drity_pages() chose to take into account pos_ratio() also because for various reason like just taking into account only bandwidth variation as feedback was not sufficient. So we also took pos_ratio into account which in-trun is dependent on gloabal dirty pages and per bdi dirty_pages/rate.

That's right so far. balance_drity_pages() needs to do dirty position control, so used formula (5).

Quoted 6 lines

So we refined the formula for calculating a tasks's effective rate over a period of time to following.

					    write_bw
	task_ratelimit = task_ratelimit_0 * ------- * pos_ratio		(9)
					    dirty_rate

That's not true. It should still be formula (7) when balance_drity_pages() considers pos_ratio.

Quoted 110 lines · Wu Fengguang

Quoted 74 lines · Vivek Goyal

Quoted 49 lines · Wu Fengguang

Hi Vivek,

Quoted 13 lines

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

Quoted 10 lines

mm/page-writeback.c +9 -0

+		base_rate = bdi->dirty_ratelimit;
+		pos_ratio = bdi_position_ratio(bdi, dirty_thresh,
+					       background_thresh, nr_dirty,
+					       bdi_thresh, bdi_dirty);
+		if (unlikely(pos_ratio == 0)) {
+			pause = MAX_PAUSE;
+			goto pause;
 		}
+		task_ratelimit = (u64)base_rate *
+					pos_ratio >> RATELIMIT_CALC_SHIFT;

Hi Fenguaang,

Quoted 6 lines

I am little confused here. I see that you have already taken pos_ratio into account in bdi_update_dirty_ratelimit() and wondering why to take that into account again in balance_diry_pages().

We calculated the pos_rate and balanced_rate and adjusted the bdi->dirty_ratelimit accordingly in bdi_update_dirty_ratelimit().

Good question. There are some inter-dependencies in the calculation, and the dependency chain is the opposite to the one in your mind:
balance_dirty_pages() used pos_ratio in the first place, so that bdi_update_dirty_ratelimit() have to use pos_ratio in the calculation of the balanced dirty rate, too.

Let's return to how the balanced dirty rate is estimated. Please pay special attention to the last paragraphs below the "......" line.

Start by throttling each dd task at rate

task_ratelimit = task_ratelimit_0 (1)
(any non-zero initial value is OK)

After 200ms, we measured

dirty_rate = # of pages dirtied by all dd's / 200ms
write_bw = # of pages written to the disk / 200ms

For the aggressive dd dirtiers, the equality holds

        dirty_rate == N * task_rate
                   == N * task_ratelimit
                   == N * task_ratelimit_0                              (2)

Or
task_ratelimit_0 = dirty_rate / N (3)

Quoted 8 lines

Now we conclude that the balanced task ratelimit can be estimated by

balanced_rate = task_ratelimit_0 * (write_bw / dirty_rate) (4)

Because with (2) and (3), (4) yields the desired equality (1):

        balanced_rate == (dirty_rate / N) * (write_bw / dirty_rate)
                      == write_bw / N

Hi Fengguang,

Following is my understanding. Please correct me where I got it wrong.

Ok, I think I follow till this point. I think what you are saying is that following is our goal in a stable system.

	task_ratelimit = write_bw/N				(6)

So we measure the write_bw of a bdi over a period of time and use that as feedback loop to modify bdi->dirty_ratelimit which inturn modifies task_ratelimit and hence we achieve the balance. So we will start with some arbitrary task limit say task_ratelimit_0, and modify that limit over a period of time based on our feedback loop to achieve a balanced system. And following seems to be the formula.

Quoted 6 lines

					    write_bw
	task_ratelimit = task_ratelimit_0 * ------- 		(7)
					    dirty_rate

Now I also understand that by using (2) and (3), you proved that how (7) will lead to (6) and that is our deisred goal.

That's right.

Quoted 10 lines

Quoted 9 lines

.............................................................................

Now let's revisit (1). Since balance_dirty_pages() chooses to execute the ratelimit

task_ratelimit = task_ratelimit_0
= dirty_ratelimit * pos_ratio (5)

Quoted 5 lines

So balance_drity_pages() chose to take into account pos_ratio() also because for various reason like just taking into account only bandwidth variation as feedback was not sufficient. So we also took pos_ratio into account which in-trun is dependent on gloabal dirty pages and per bdi dirty_pages/rate.

That's right so far. balance_drity_pages() needs to do dirty position control, so used formula (5).

Quoted 6 lines

So we refined the formula for calculating a tasks's effective rate over a period of time to following.

					    write_bw
	task_ratelimit = task_ratelimit_0 * ------- * pos_ratio		(9)
					    dirty_rate

Quoted 2 lines

That's not true. It should still be formula (7) when balance_drity_pages() considers pos_ratio.

Why it is not true? If I do some math, it sounds right. Let me summarize my understanding again.

- In a steady state stable system, we want dirty_bw = write_bw, IOW.

dirty_bw/write_bw = 1 (1)

If we can achieve above then that means we are throttling tasks at just right rate.

Or
- dirty_bw == write_bw
N * task_ratelimit == write_bw
task_ratelimit = write_bw/N (2)

So as long as we can come up with a system where balance_dirty_pages() calculates task_ratelimit to be write_bw/N, we should be fine.

- But this does not take care of imbalances. So if system goes out of balance before feedback loop kicks in and dirty rate shoots up, then cache size will grow and number of dirty pages will shoot up. Hence we brought in the notion of position ratio where we also vary a tasks's dirty ratelimit based on number of dirty pages. So our effective formula became.

task_ratelimit = write_bw/N * pos_ratio (3)

So as long as we meet (3), we should reach to stable state.

- But here N is unknown in advance so balance_drity_pages() can not make use of this formula directly. But write_bw and dirty_bw from previous 200ms are known. So following can replace (3).

write_bw
task_ratelimit = task_ratelimit_0 * --------- * pos_ratio (4)
dirty_bw

dirty_bw = task_ratelimit_0 * N (5)

Substitute (5) in (4)

task_ratelimit = write_bw/N * pos_ratio (6)

(6) is same as (3) which has been derived from (4) and that means at any given point of time (4) can be used by balance_drity_pages() to calculate a tasks's throttling rate.

- Now going back to (4). Because we have a feedback loop where we continuously update a previous number based on feedback, we can track previous value in bdi->dirty_ratelimit.

write_bw
task_ratelimit = task_ratelimit_0 * --------- * pos_ratio
dirty_bw

   Or

   task_ratelimit = bdi->dirty_ratelimit * pos_ratio         (7)

   where
					    write_bw	

bdi->dirty_ratelimit = task_ratelimit_0 * ---------
dirty_bw

Because task_ratelimit_0 is initial value to begin with and we will keep on coming with new value every 200ms, we should be able to write above as follows.

write_bw
bdi->dirty_ratelimit_n = bdi->dirty_ratelimit_n-1 * -------- (8)
dirty_bw

Effectively we start with an initial value of task_ratelimit_0 and then keep on updating it based on rate change feedback every 200ms.

To summarize,

We need to achieve (3) for a balanced system. Because we don't know the value of N in advance, we can use (4) to achieve effect of (3). So we start with a default value of task_ratelimit_0 and update that every 200ms based on how write and dirty rate on device is changing (8). We also further refine that rate by pos_ratio so that any variations in number of dirty pages due to temporary imbalances in the system can be accounted for (7).

I see that you also use (7). I think only contention point is how
(8) is perceived. So can you please explain why do you think that above calculation or (9) is wrong.

I can kind of understand that you have done various adjustments to keep the task_ratelimit and bdi->dirty_ratelimit relatively stable. Just that I am not able to understand your calculations in updating bdi->dirty_ratelimit.

Quoted 10 lines

Because task_ratelimit_0 is initial value to begin with and we will keep on coming with new value every 200ms, we should be able to write above as follows.

write_bw
bdi->dirty_ratelimit_n = bdi->dirty_ratelimit_n-1 * -------- (8)
dirty_bw

Effectively we start with an initial value of task_ratelimit_0 and then keep on updating it based on rate change feedback every 200ms.

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

So we refined the formula for calculating a tasks's effective rate over a period of time to following.

					    write_bw
	task_ratelimit = task_ratelimit_0 * ------- * pos_ratio		(9)
					    dirty_rate

Quoted 5 lines

Quoted 2 lines

That's not true. It should still be formula (7) when balance_drity_pages() considers pos_ratio.

Why it is not true? If I do some math, it sounds right. Let me summarize my understanding again.

Ah sorry! (9) actually holds true, as made clear by your below reasoning.

Quoted 7 lines

- In a steady state stable system, we want dirty_bw = write_bw, IOW.

dirty_bw/write_bw = 1 (1)

If we can achieve above then that means we are throttling tasks at just right rate.

Quoted 7 lines

Or
- dirty_bw == write_bw
N * task_ratelimit == write_bw
task_ratelimit = write_bw/N (2)

So as long as we can come up with a system where balance_dirty_pages() calculates task_ratelimit to be write_bw/N, we should be fine.

Right.

Quoted 10 lines

- But this does not take care of imbalances. So if system goes out of balance before feedback loop kicks in and dirty rate shoots up, then cache size will grow and number of dirty pages will shoot up. Hence we brought in the notion of position ratio where we also vary a tasks's dirty ratelimit based on number of dirty pages. So our effective formula became.

task_ratelimit = write_bw/N * pos_ratio (3)

So as long as we meet (3), we should reach to stable state.

Right.

Quoted 10 lines

- But here N is unknown in advance so balance_drity_pages() can not make use of this formula directly. But write_bw and dirty_bw from previous 200ms are known. So following can replace (3).

write_bw
task_ratelimit = task_ratelimit_0 * --------- * pos_ratio (4)
dirty_bw

dirty_bw = task_ratelimit_0 * N (5)

Quoted 7 lines

Substitute (5) in (4)

task_ratelimit = write_bw/N * pos_ratio (6)

(6) is same as (3) which has been derived from (4) and that means at any given point of time (4) can be used by balance_drity_pages() to calculate a tasks's throttling rate.

Right. Sorry what's in my mind was

write_bw
balanced_rate = task_ratelimit_0 * --------
dirty_bw

task_ratelimit = balanced_rate * pos_ratio

which is effective the same to your combined equation (4).

Quoted 8 lines

- Now going back to (4). Because we have a feedback loop where we continuously update a previous number based on feedback, we can track previous value in bdi->dirty_ratelimit.

write_bw
task_ratelimit = task_ratelimit_0 * --------- * pos_ratio
dirty_bw

Quoted 8 lines

   Or

   task_ratelimit = bdi->dirty_ratelimit * pos_ratio         (7)

   where
					    write_bw	

bdi->dirty_ratelimit = task_ratelimit_0 * ---------
dirty_bw

Right.

Quoted 10 lines

Because task_ratelimit_0 is initial value to begin with and we will keep on coming with new value every 200ms, we should be able to write above as follows.

write_bw
bdi->dirty_ratelimit_n = bdi->dirty_ratelimit_n-1 * -------- (8)
dirty_bw

Effectively we start with an initial value of task_ratelimit_0 and then keep on updating it based on rate change feedback every 200ms.

Right.

Quoted 10 lines

To summarize,

We need to achieve (3) for a balanced system. Because we don't know the value of N in advance, we can use (4) to achieve effect of (3). So we start with a default value of task_ratelimit_0 and update that every 200ms based on how write and dirty rate on device is changing (8). We also further refine that rate by pos_ratio so that any variations in number of dirty pages due to temporary imbalances in the system can be accounted for (7).

Quoted 3 lines

I see that you also use (7). I think only contention point is how
(8) is perceived. So can you please explain why do you think that above calculation or (9) is wrong.

There is no contention point and (9) is right..Sorry it's my fault. We are well aligned in the above reasoning :)

Quoted 4 lines

I can kind of understand that you have done various adjustments to keep the task_ratelimit and bdi->dirty_ratelimit relatively stable. Just that I am not able to understand your calculations in updating bdi->dirty_ratelimit.