[PATCH 1/2] cbq: incorrectly low bandwidth setting blocks limited traffic

[PATCH 1/2] cbq: incorrectly low bandwidth setting blocks limited traffic

[Vasily Averin]

Mainstream commit f0f6ee1f70c4eaab9d52cf7d255df4bd89f8d1c2 have side effect:
if cbq bandwidth setting is less than real interface throughput
non-limited traffic can delay limited traffic for a very long time.

This happen because of q->now changes incorrectly in cbq_dequeue():
in described scenario L2T is much greater than real time delay,
and q->now gets an extra boost for each transmitted packet.

Accumulated boost prevents update q->now, and blocked class can wait
very long time until (q->now >= cl->undertime) will be true again.

To fix the problem the patch updates q->now on each cbq_update() call.
L2T-related pre-modification q->now was moved to cbq_update().

My testing confirmed that it fixes the problem and did not discovered
any side-effects.

Signed-off-by: Vasily Averin <vvs@openvz.org>
---
 net/sched/sch_cbq.c |   37 +++++++++++++------------------------
 1 files changed, 13 insertions(+), 24 deletions(-)

diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
index ead5264..550be95 100644
--- a/net/sched/sch_cbq.c
+++ b/net/sched/sch_cbq.c
@@ -700,8 +700,13 @@ cbq_update(struct cbq_sched_data *q)
 	struct cbq_class *this = q->tx_class;
 	struct cbq_class *cl = this;
 	int len = q->tx_len;
+	psched_time_t now;
 
 	q->tx_class = NULL;
+	/* Time integrator. We calculate EOS time
+	 * by adding expected packet transmission time.
+	 */
+	now = q->now + L2T(&q->link, len);
 
 	for ( ; cl; cl = cl->share) {
 		long avgidle = cl->avgidle;
@@ -717,7 +722,7 @@ cbq_update(struct cbq_sched_data *q)
 		 *	idle = (now - last) - last_pktlen/rate
 		 */
 
-		idle = q->now - cl->last;
+		idle = now - cl->last;
 		if ((unsigned long)idle > 128*1024*1024) {
 			avgidle = cl->maxidle;
 		} else {
@@ -761,7 +766,7 @@ cbq_update(struct cbq_sched_data *q)
 			idle -= L2T(&q->link, len);
 			idle += L2T(cl, len);
 
-			cl->undertime = q->now + idle;
+			cl->undertime = now + idle;
 		} else {
 			/* Underlimit */
 
@@ -771,7 +776,8 @@ cbq_update(struct cbq_sched_data *q)
 			else
 				cl->avgidle = avgidle;
 		}
-		cl->last = q->now;
+		if ((s64)(now - cl->last) > 0)
+			cl->last = now;
 	}
 
 	cbq_update_toplevel(q, this, q->tx_borrowed);
@@ -943,30 +949,13 @@ cbq_dequeue(struct Qdisc *sch)
 	struct sk_buff *skb;
 	struct cbq_sched_data *q = qdisc_priv(sch);
 	psched_time_t now;
-	psched_tdiff_t incr;
 
 	now = psched_get_time();
-	incr = now - q->now_rt;
-
-	if (q->tx_class) {
-		psched_tdiff_t incr2;
-		/* Time integrator. We calculate EOS time
-		 * by adding expected packet transmission time.
-		 * If real time is greater, we warp artificial clock,
-		 * so that:
-		 *
-		 * cbq_time = max(real_time, work);
-		 */
-		incr2 = L2T(&q->link, q->tx_len);
-		q->now += incr2;
+
+	if (q->tx_class)
 		cbq_update(q);
-		if ((incr -= incr2) < 0)
-			incr = 0;
-		q->now += incr;
-	} else {
-		if (now > q->now)
-			q->now = now;
-	}
+
+	q->now = now;
 	q->now_rt = now;
 
 	for (;;) {
-- 
1.7.1

Re: [PATCH 1/2] cbq: incorrectly low bandwidth setting blocks limited traffic

[Sergei Shtylyov]

Hello.

On 8/13/2014 4:38 PM, Vasily Averin wrote:

> Mainstream commit f0f6ee1f70c4eaab9d52cf7d255df4bd89f8d1c2 have side effect:

    Please also specify that commit's summary line in parens.

> if cbq bandwidth setting is less than real interface throughput
> non-limited traffic can delay limited traffic for a very long time.

> This happen because of q->now changes incorrectly in cbq_dequeue():
> in described scenario L2T is much greater than real time delay,
> and q->now gets an extra boost for each transmitted packet.

> Accumulated boost prevents update q->now, and blocked class can wait
> very long time until (q->now >= cl->undertime) will be true again.

> To fix the problem the patch updates q->now on each cbq_update() call.
> L2T-related pre-modification q->now was moved to cbq_update().

> My testing confirmed that it fixes the problem and did not discovered

   Discover.

> any side-effects.

> Signed-off-by: Vasily Averin <vvs@openvz.org>

WBR, Sergei

Re: [PATCH 1/2] cbq: incorrectly low bandwidth setting blocks limited traffic

[Vasily Averin]

On 08/13/2014 04:45 PM, Sergei Shtylyov wrote:
> Hello.
> 
> On 8/13/2014 4:38 PM, Vasily Averin wrote:
> 
>> Mainstream commit f0f6ee1f70c4eaab9d52cf7d255df4bd89f8d1c2 have side effect:
> 
>    Please also specify that commit's summary line in parens.
cbq: incorrect processing of high limits

>> if cbq bandwidth setting is less than real interface throughput
>> non-limited traffic can delay limited traffic for a very long time.
> 
>> This happen because of q->now changes incorrectly in cbq_dequeue():
>> in described scenario L2T is much greater than real time delay,
>> and q->now gets an extra boost for each transmitted packet.
> 
>> Accumulated boost prevents update q->now, and blocked class can wait
>> very long time until (q->now >= cl->undertime) will be true again.
> 
>> To fix the problem the patch updates q->now on each cbq_update() call.
>> L2T-related pre-modification q->now was moved to cbq_update().
> 
>> My testing confirmed that it fixes the problem and did not discovered
> 
>   Discover.
> 
>> any side-effects.
> 
>> Signed-off-by: Vasily Averin <vvs@openvz.org>
> 
> WBR, Sergei
> 
> 

Re: [PATCH 1/2] cbq: incorrectly low bandwidth setting blocks limited traffic

[Eric Dumazet]

On Wed, 2014-08-13 at 16:54 +0400, Vasily Averin wrote:
> On 08/13/2014 04:45 PM, Sergei Shtylyov wrote:
> > Hello.
> > 
> > On 8/13/2014 4:38 PM, Vasily Averin wrote:
> > 
> >> Mainstream commit f0f6ee1f70c4eaab9d52cf7d255df4bd89f8d1c2 have side effect:
> > 
> >    Please also specify that commit's summary line in parens.
> cbq: incorrect processing of high limits

So a more useful way to include the information is to add :

Fixes: f0f6ee1f70c4 ("cbq: incorrect processing of high limits")

Because it will help automatic tools to decide if this fix needs to be
backported to old stable kernels.

Thanks.

[PATCH 1/2 v2] cbq: incorrectly low bandwidth setting blocks limited traffic

[Vasily Averin]

v2: comment cleanup

Fixes: f0f6ee1f70c4 ("cbq: incorrect processing of high limits")

Mainstream commit f0f6ee1f70c4 have side effect:
if cbq bandwidth setting is less than real interface throughput
non-limited traffic can delay limited traffic for a very long time.

This happen because of q->now changes incorrectly in cbq_dequeue():
in described scenario L2T is much greater than real time delay,
and q->now gets an extra boost for each transmitted packet.

Accumulated boost prevents update q->now, and blocked class can wait
very long time until (q->now >= cl->undertime) will be true again.

To fix the problem the patch updates q->now on each cbq_update() call.
L2T-related pre-modification q->now was moved to cbq_update().

My testing confirmed that it fixes the problem and did not discover
any side-effects

Signed-off-by: Vasily Averin <vvs@openvz.org>
---
 net/sched/sch_cbq.c |   37 +++++++++++++------------------------
 1 files changed, 13 insertions(+), 24 deletions(-)

diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
index ead5264..550be95 100644
--- a/net/sched/sch_cbq.c
+++ b/net/sched/sch_cbq.c
@@ -700,8 +700,13 @@ cbq_update(struct cbq_sched_data *q)
 	struct cbq_class *this = q->tx_class;
 	struct cbq_class *cl = this;
 	int len = q->tx_len;
+	psched_time_t now;
 
 	q->tx_class = NULL;
+	/* Time integrator. We calculate EOS time
+	 * by adding expected packet transmission time.
+	 */
+	now = q->now + L2T(&q->link, len);
 
 	for ( ; cl; cl = cl->share) {
 		long avgidle = cl->avgidle;
@@ -717,7 +722,7 @@ cbq_update(struct cbq_sched_data *q)
 		 *	idle = (now - last) - last_pktlen/rate
 		 */
 
-		idle = q->now - cl->last;
+		idle = now - cl->last;
 		if ((unsigned long)idle > 128*1024*1024) {
 			avgidle = cl->maxidle;
 		} else {
@@ -761,7 +766,7 @@ cbq_update(struct cbq_sched_data *q)
 			idle -= L2T(&q->link, len);
 			idle += L2T(cl, len);
 
-			cl->undertime = q->now + idle;
+			cl->undertime = now + idle;
 		} else {
 			/* Underlimit */
 
@@ -771,7 +776,8 @@ cbq_update(struct cbq_sched_data *q)
 			else
 				cl->avgidle = avgidle;
 		}
-		cl->last = q->now;
+		if ((s64)(now - cl->last) > 0)
+			cl->last = now;
 	}
 
 	cbq_update_toplevel(q, this, q->tx_borrowed);
@@ -943,30 +949,13 @@ cbq_dequeue(struct Qdisc *sch)
 	struct sk_buff *skb;
 	struct cbq_sched_data *q = qdisc_priv(sch);
 	psched_time_t now;
-	psched_tdiff_t incr;
 
 	now = psched_get_time();
-	incr = now - q->now_rt;
-
-	if (q->tx_class) {
-		psched_tdiff_t incr2;
-		/* Time integrator. We calculate EOS time
-		 * by adding expected packet transmission time.
-		 * If real time is greater, we warp artificial clock,
-		 * so that:
-		 *
-		 * cbq_time = max(real_time, work);
-		 */
-		incr2 = L2T(&q->link, q->tx_len);
-		q->now += incr2;
+
+	if (q->tx_class)
 		cbq_update(q);
-		if ((incr -= incr2) < 0)
-			incr = 0;
-		q->now += incr;
-	} else {
-		if (now > q->now)
-			q->now = now;
-	}
+
+	q->now = now;
 	q->now_rt = now;
 
 	for (;;) {
-- 
1.7.1

Re: [PATCH 1/2 v2] cbq: incorrectly low bandwidth setting blocks limited traffic

[David Miller]

When you need to resubmit a patch in response to feedback, you cannot
just send that one patch again if it's part of a series.

Instead, you must freshly resubmit the entire series.

Thanks.

[PATCH 2/2] cbq: now_rt removal

[Vasily Averin]

Now q->now_rt is identical to q->now and is not required anymore.

Signed-off-by: Vasily Averin <vvs@openvz.org>
---
 net/sched/sch_cbq.c |   11 +----------
 1 files changed, 1 insertions(+), 10 deletions(-)

diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
index 550be95..762a04b 100644
--- a/net/sched/sch_cbq.c
+++ b/net/sched/sch_cbq.c
@@ -159,7 +159,6 @@ struct cbq_sched_data {
 	struct cbq_class	*tx_borrowed;
 	int			tx_len;
 	psched_time_t		now;		/* Cached timestamp */
-	psched_time_t		now_rt;		/* Cached real time */
 	unsigned int		pmask;
 
 	struct hrtimer		delay_timer;
@@ -353,12 +352,7 @@ cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
 	int toplevel = q->toplevel;
 
 	if (toplevel > cl->level && !(qdisc_is_throttled(cl->q))) {
-		psched_time_t now;
-		psched_tdiff_t incr;
-
-		now = psched_get_time();
-		incr = now - q->now_rt;
-		now = q->now + incr;
+		psched_time_t now = psched_get_time();
 
 		do {
 			if (cl->undertime < now) {
@@ -956,7 +950,6 @@ cbq_dequeue(struct Qdisc *sch)
 		cbq_update(q);
 
 	q->now = now;
-	q->now_rt = now;
 
 	for (;;) {
 		q->wd_expires = 0;
@@ -1212,7 +1205,6 @@ cbq_reset(struct Qdisc *sch)
 	hrtimer_cancel(&q->delay_timer);
 	q->toplevel = TC_CBQ_MAXLEVEL;
 	q->now = psched_get_time();
-	q->now_rt = q->now;
 
 	for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
 		q->active[prio] = NULL;
@@ -1396,7 +1388,6 @@ static int cbq_init(struct Qdisc *sch, struct nlattr *opt)
 	q->delay_timer.function = cbq_undelay;
 	q->toplevel = TC_CBQ_MAXLEVEL;
 	q->now = psched_get_time();
-	q->now_rt = q->now;
 
 	cbq_link_class(&q->link);
 
-- 
1.7.1