Skip to contentSkip to conversation

net: sched: fix some issues

PATCH Superseded Yang Yingliang 7 participants 19 messages Nov 19, 2013 – Dec 3, 2013

Subsystems (3)

v3 of 7 Superseded Latest is v7 →

lore
Share & tools
lore
#0 lore raw

v3 cover net: sched: fix some issues

fix a regression introduced by commit b757c9336d63f94c6b57532 (tbf: improved accuracy at high rates).
fix quantum calculation introduced by 64bit rates.

v2
patch 1/2: redescribe the regression.
patch 2/2: add Eric's ack.

v3
patch 1/2: use psched_l2t_ns to calculate max_size and cleanup exit/done section suggested by Jesper.

Yang Yingliang (2):
net: sched: tbf: fix calculation of max_size
net: sched: htb: fix calculation of quantum

 net/sched/sch_htb.c | 18 ++++++++------
 net/sched/sch_tbf.c | 71 ++++++++++++++++++++++++++++-------------------------
 2 files changed, 47 insertions(+), 42 deletions(-)
Signature · 1 line
1.8.0
#1 lore raw

PATCH v3 1/2 net: sched: tbf: fix calculation of max_size

commit b757c9336d63f94c6b57532(tbf: improved accuracy at high rates) introduce a regression.

With the follow command:
tc qdisc add dev eth1 root handle 1: tbf latency 50ms burst 10KB rate 30gbit mtu 64k

Without this patch, the max_size value is 10751(bytes).
But, in fact, the real max_size value should be smaller than 7440(bytes). Or a packet whose length is bigger than 7440 will cause network congestion. Because the packet is so big that can't get enough tokens. Even all the tokens in the buffer is given to the packet.

With this patch, the max_size value is 7440(bytes).
The packets whose length is bigger than 7440(bytes) will be dropped or reshape in tbf_enqueue().

---
 net/sched/sch_tbf.c | 71 ++++++++++++++++++++++++++++-------------------------
 1 file changed, 37 insertions(+), 34 deletions(-)
net/sched/sch_tbf.c +37 -34
index 68f9859..c194129 100644
@@ -291,33 +291,20 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
 		goto done;
 
 	qopt = nla_data(tb[TCA_TBF_PARMS]);
-	rtab = qdisc_get_rtab(&qopt->rate, tb[TCA_TBF_RTAB]);
-	if (rtab == NULL)
-		goto done;
-
-	if (qopt->peakrate.rate) {
-		if (qopt->peakrate.rate > qopt->rate.rate)
-			ptab = qdisc_get_rtab(&qopt->peakrate, tb[TCA_TBF_PTAB]);
-		if (ptab == NULL)
-			goto done;
+	if (qopt->rate.linklayer == TC_LINKLAYER_UNAWARE) {
+		rtab = qdisc_get_rtab(&qopt->rate, tb[TCA_TBF_RTAB]);
+		if (rtab) {
+			qdisc_put_rtab(rtab);
+			rtab = NULL;
+		}
 	}
-
-	for (n = 0; n < 256; n++)
-		if (rtab->data[n] > qopt->buffer)
-			break;
-	max_size = (n << qopt->rate.cell_log) - 1;
-	if (ptab) {
-		int size;
-
-		for (n = 0; n < 256; n++)
-			if (ptab->data[n] > qopt->mtu)
-				break;
-		size = (n << qopt->peakrate.cell_log) - 1;
-		if (size < max_size)
-			max_size = size;
+	if (qopt->peakrate.linklayer == TC_LINKLAYER_UNAWARE) {
+		ptab = qdisc_get_rtab(&qopt->peakrate, tb[TCA_TBF_PTAB]);
+		if (ptab) {
+			qdisc_put_rtab(ptab);
+			ptab = NULL;
+		}
 	}
-	if (max_size < 0)
-		goto done;
 
 	if (q->qdisc != &noop_qdisc) {
 		err = fifo_set_limit(q->qdisc, qopt->limit);
@@ -339,30 +326,46 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
 	}
 	q->limit = qopt->limit;
 	q->mtu = PSCHED_TICKS2NS(qopt->mtu);
-	q->max_size = max_size;
 	q->buffer = PSCHED_TICKS2NS(qopt->buffer);
 	q->tokens = q->buffer;
 	q->ptokens = q->mtu;
 
 	if (tb[TCA_TBF_RATE64])
 		rate64 = nla_get_u64(tb[TCA_TBF_RATE64]);
-	psched_ratecfg_precompute(&q->rate, &rtab->rate, rate64);
-	if (ptab) {
+	psched_ratecfg_precompute(&q->rate, &qopt->rate, rate64);
+	if (!q->rate.rate_bytes_ps)
+		goto unlock_done;
+	for (n = 0; n < 65536; n++)
+		if (psched_l2t_ns(&q->rate, n) > q->buffer)
+			break;
+	max_size = min_t(u32, n, (256ULL << qopt->rate.cell_log) - 1);
+
+	if (qopt->peakrate.rate) {
+		int size = 0;
 		if (tb[TCA_TBF_PRATE64])
 			prate64 = nla_get_u64(tb[TCA_TBF_PRATE64]);
-		psched_ratecfg_precompute(&q->peak, &ptab->rate, prate64);
+		psched_ratecfg_precompute(&q->peak, &qopt->peakrate, prate64);
+		for (n = 0; n < 65536; n++)
+			if (psched_l2t_ns(&q->peak, n) > q->mtu)
+				break;
+		size = min_t(u32, n, (256ULL << qopt->rate.cell_log) - 1);
+		max_size = min_t(u32, max_size, size);
 		q->peak_present = true;
 	} else {
 		q->peak_present = false;
 	}
 
+	if (!max_size)
+		goto unlock_done;
+	q->max_size = max_size;
+
 	sch_tree_unlock(sch);
-	err = 0;
+	return 0;
+
+unlock_done:
+	sch_tree_unlock(sch);
+	err = -EINVAL;
 done:
-	if (rtab)
-		qdisc_put_rtab(rtab);
-	if (ptab)
-		qdisc_put_rtab(ptab);
 	return err;
 }
 
Signature · 1 line
1.8.0
#2 lore raw

Re: [PATCH net v3 1/2] net: sched: tbf: fix calculation of max_size

Quoted 11 lines · On Tue, 19 Nov 2013 15:25:38 +0800 Yang Yingliang <[email protected]>…

commit b757c9336d63f94c6b57532(tbf: improved accuracy at high rates) introduce a regression.

With the follow command:
tc qdisc add dev eth1 root handle 1: tbf latency 50ms burst 10KB rate 30gbit mtu 64k

Without this patch, the max_size value is 10751(bytes).
But, in fact, the real max_size value should be smaller than 7440(bytes). Or a packet whose length is bigger than 7440 will cause network congestion. Because the packet is so big that can't get enough tokens. Even all the tokens in the buffer is given to the packet.

Sorry, but I don't like the commit message. The real problem is the value in q->buffer, and that the userspace rate table cannot handle these high rates, which you don't mention.

I would write something like:

The kernel no longer uses the userspace provided rate table. Thus, it is wrong to calculate max_size based on this rate table. At high rates this rate table gets very inaccurate, which can lead wrong calculation of max_size.

Consequence of max_size being too large is severe, and cause packets being stalled in tbf_dequeue() because it cannot get enough tokens. The max_size guards against enqueuing packet sizes above q->buffer "time" in tbf_enqueue().

This patch fixes the calculation of max_size. By ... add desc ... perhaps also mention how it is connected to p->mtu (with is also a "time" value).

The rest of the patch looks okay now, one point below though.

Quoted 4 lines
net/sched/sch_tbf.c +0 -0
index 68f9859..c194129 100644

[...]

Quoted 1 line
net/sched/sch_tbf.c +0 -0
@@ -339,30 +326,46 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)

[...]

net/sched/sch_tbf.c static int tbf_change(struct Qdisc *sch, struct nlattr *opt) · line 341

Quoted 4 lines
net/sched/sch_tbf.c +4 -0
+	for (n = 0; n < 65536; n++)
+		if (psched_l2t_ns(&q->rate, n) > q->buffer)
+			break;
+	max_size = min_t(u32, n, (256ULL << qopt->rate.cell_log) - 1);

I'm a little uncertain about, if using the 65536 constant is okay, or considered "bad style".

I'm still a little confused/uncertain why we need the "qopt->rate.cell_log".

Signature · 5 lines
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Sr. Network Kernel Developer at Red Hat
  Author of http://www.iptv-analyzer.org
  LinkedIn: http://www.linkedin.com/in/brouer
#3 lore raw

Re: [PATCH net v3 1/2] net: sched: tbf: fix calculation of max_size

Quoted 31 lines · Jesper Dangaard Brouer
Quoted 11 lines · On Tue, 19 Nov 2013 15:25:38 +0800 Yang Yingliang <[email protected]>…

commit b757c9336d63f94c6b57532(tbf: improved accuracy at high rates) introduce a regression.

With the follow command:
tc qdisc add dev eth1 root handle 1: tbf latency 50ms burst 10KB rate 30gbit mtu 64k

Without this patch, the max_size value is 10751(bytes).
But, in fact, the real max_size value should be smaller than 7440(bytes). Or a packet whose length is bigger than 7440 will cause network congestion. Because the packet is so big that can't get enough tokens. Even all the tokens in the buffer is given to the packet.

Sorry, but I don't like the commit message. The real problem is the value in q->buffer, and that the userspace rate table cannot handle these high rates, which you don't mention.

I would write something like:

The kernel no longer uses the userspace provided rate table. Thus, it is wrong to calculate max_size based on this rate table. At high rates this rate table gets very inaccurate, which can lead wrong calculation of max_size.

Consequence of max_size being too large is severe, and cause packets being stalled in tbf_dequeue() because it cannot get enough tokens. The max_size guards against enqueuing packet sizes above q->buffer "time" in tbf_enqueue().

Quoted 6 lines

This patch fixes the calculation of max_size. By ... add desc ... perhaps also mention how it is connected to p->mtu (with is also a "time" value).

The rest of the patch looks okay now, one point below though.

OK, change it in v4.
Thanks!

Quoted 9 lines
Quoted 6 lines
net/sched/sch_tbf.c +0 -0
index 68f9859..c194129 100644

[...]

Quoted 1 line
net/sched/sch_tbf.c +0 -0
@@ -339,30 +326,46 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)

[...]

Quoted 7 lines

net/sched/sch_tbf.c static int tbf_change(struct Qdisc *sch, struct nlattr *opt) · line 341

Quoted 4 lines
net/sched/sch_tbf.c +4 -0
+	for (n = 0; n < 65536; n++)
+		if (psched_l2t_ns(&q->rate, n) > q->buffer)
+			break;
+	max_size = min_t(u32, n, (256ULL << qopt->rate.cell_log) - 1);

I'm a little uncertain about, if using the 65536 constant is okay, or considered "bad style".

I'll use a MACRO to instead of this constant in v4. Thanks!

Quoted 3 lines

I'm still a little confused/uncertain why we need the "qopt->rate.cell_log".

Because we need max_size be smaller than mtu(user input in bytes). E.g. if user inputs like this "... burst 100KB rate 100mbit mtu 4095", without this patch, max_size is 4095.
But with this patch, if don't use cell_log, max_size is 102400. I think it's not correct, so I used cell_log here.

#4 lore raw

Re: [PATCH net v3 1/2] net: sched: tbf: fix calculation of max_size

Quoted 4 lines · On Wed, 20 Nov 2013 10:14:43 +0800 Yang Yingliang <[email protected]>…
Quoted 3 lines · Jesper Dangaard Brouer

On Tue, 19 Nov 2013 15:25:38 +0800
Yang Yingliang <[email protected]> wrote:

[...]

Quoted 16 lines
Quoted 8 lines
Quoted 5 lines
net/sched/sch_tbf.c +0 -0
index 68f9859..c194129 100644

[...]

Quoted 1 line
net/sched/sch_tbf.c +0 -0
@@ -339,30 +326,46 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)

[...]

Quoted 7 lines

net/sched/sch_tbf.c static int tbf_change(struct Qdisc *sch, struct nlattr *opt) · line 341

Quoted 4 lines
net/sched/sch_tbf.c +4 -0
+	for (n = 0; n < 65536; n++)
+		if (psched_l2t_ns(&q->rate, n) > q->buffer)
+			break;
+	max_size = min_t(u32, n, (256ULL << qopt->rate.cell_log) - 1);

I'm a little uncertain about, if using the 65536 constant is okay, or considered "bad style".

Quoted 1 line

I'll use a MACRO to instead of this constant in v4.

I'm not saying you have to use a macro for this. I'm fine with using 65536 here, some other developers might have stronger opinions on this?

Quoted 8 lines
Quoted 2 lines

I'm still a little confused/uncertain why we need the "qopt->rate.cell_log".

Because we need max_size be smaller than mtu(user input in bytes). E.g. if user inputs like this "... burst 100KB rate 100mbit mtu 4095", without this patch, max_size is 4095.
But with this patch, if don't use cell_log, max_size is 102400. I think it's not correct, so I used cell_log here.

Hmmmm... so you are using cell_log to approximate the MTU size, because struct tc_ratespec, does not contain the a mtu parameter. You do realize this is only an approximation. (This also smells like a bad transition away from the userspace rate tables)

What about the p->mtu parameter from struct tc_tbf_qopt. I know it is in a "time" format... but hey, you are already using this parameter requoting your patch:

Quoted 4 lines · On Tue, 19 Nov 2013 15:25:38 +0800 Yang Yingliang <[email protected]>…
net/sched/sch_tbf.c +0 -0
index 68f9859..c194129 100644

[... cut ...]

Quoted 19 lines
net/sched/sch_tbf.c +6 -3
@@ -339,30 +326,46 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
 	}
 	q->limit = qopt->limit;
 	q->mtu = PSCHED_TICKS2NS(qopt->mtu);
-	q->max_size = max_size;
 	q->buffer = PSCHED_TICKS2NS(qopt->buffer);
 	q->tokens = q->buffer;
 	q->ptokens = q->mtu;
 
 	if (tb[TCA_TBF_RATE64])
 		rate64 = nla_get_u64(tb[TCA_TBF_RATE64]);
-	psched_ratecfg_precompute(&q->rate, &rtab->rate, rate64);
-	if (ptab) {
+	psched_ratecfg_precompute(&q->rate, &qopt->rate, rate64);
+	if (!q->rate.rate_bytes_ps)
+		goto unlock_done;
+	for (n = 0; n < 65536; n++)
+		if (psched_l2t_ns(&q->rate, n) > q->buffer)
+			break;

net/sched/sch_tbf.c static int tbf_change(struct Qdisc *sch, struct nlattr *opt) · line 349

Quoted 10 lines
net/sched/sch_tbf.c +7 -1
+	max_size = min_t(u32, n, (256ULL << qopt->rate.cell_log) - 1);
+
+	if (qopt->peakrate.rate) {
+		int size = 0;
 		if (tb[TCA_TBF_PRATE64])
 			prate64 = nla_get_u64(tb[TCA_TBF_PRATE64]);
-		psched_ratecfg_precompute(&q->peak, &ptab->rate, prate64);
+		psched_ratecfg_precompute(&q->peak, &qopt->peakrate, prate64);
+		for (n = 0; n < 65536; n++)
+			if (psched_l2t_ns(&q->peak, n) > q->mtu)

You are using q->mtu here, BUT why are you only doing this, when there is a qopt->peakrate.rate, set??? (I might have missed something)

Quoted 7 lines
net/sched/sch_tbf.c +3 -0
+				break;
+		size = min_t(u32, n, (256ULL << qopt->rate.cell_log) - 1);
+		max_size = min_t(u32, max_size, size);
 		q->peak_present = true;
 	} else {
 		q->peak_present = false;
 	}
Signature · 25 lines
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Sr. Network Kernel Developer at Red Hat
  Author of http://www.iptv-analyzer.org
  LinkedIn: http://www.linkedin.com/in/brouer

For easy reference
------------------
(include/uapi/linux/pkt_sched.h)
struct tc_ratespec {
	unsigned char	cell_log;
	__u8		linklayer; /* lower 4 bits */
	unsigned short	overhead;
	short		cell_align;
	unsigned short	mpu;
	__u32		rate;
};

struct tc_tbf_qopt {
	struct tc_ratespec rate;
	struct tc_ratespec peakrate;
	__u32		limit;
	__u32		buffer;
	__u32		mtu;
};
#5 lore raw

Re: [PATCH net v3 1/2] net: sched: tbf: fix calculation of max_size

Quoted 33 lines · Jesper Dangaard Brouer
Quoted 4 lines · On Wed, 20 Nov 2013 10:14:43 +0800 Yang Yingliang <[email protected]>…
Quoted 3 lines · Jesper Dangaard Brouer

On Tue, 19 Nov 2013 15:25:38 +0800
Yang Yingliang <[email protected]> wrote:

[...]

Quoted 7 lines
Quoted 7 lines
Quoted 4 lines
net/sched/sch_tbf.c +0 -0
index 68f9859..c194129 100644

[...]

Quoted 1 line
net/sched/sch_tbf.c +0 -0
@@ -339,30 +326,46 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)

[...]

Quoted 7 lines
Quoted 6 lines

net/sched/sch_tbf.c static int tbf_change(struct Qdisc *sch, struct nlattr *opt) · line 341

Quoted 4 lines
net/sched/sch_tbf.c +4 -0
+	for (n = 0; n < 65536; n++)
+		if (psched_l2t_ns(&q->rate, n) > q->buffer)
+			break;
+	max_size = min_t(u32, n, (256ULL << qopt->rate.cell_log) - 1);

I'm a little uncertain about, if using the 65536 constant is okay, or considered "bad style".

I'll use a MACRO to instead of this constant in v4.

I'm not saying you have to use a macro for this. I'm fine with using 65536 here, some other developers might have stronger opinions on this?

Quoted 7 lines
Quoted 2 lines

I'm still a little confused/uncertain why we need the "qopt->rate.cell_log".

Because we need max_size be smaller than mtu(user input in bytes). E.g. if user inputs like this "... burst 100KB rate 100mbit mtu 4095", without this patch, max_size is 4095.
But with this patch, if don't use cell_log, max_size is 102400. I think it's not correct, so I used cell_log here.

Quoted 4 lines

Hmmmm... so you are using cell_log to approximate the MTU size, because struct tc_ratespec, does not contain the a mtu parameter. You do realize this is only an approximation. (This also smells like a bad transition away from the userspace rate tables)

Hmmm... not exactly, cell_log can be input by user, if input like this "... burst 100KB/4 rate 100mbit mtu 4095", with old calculation method, max_size would be 1023, but with new calculation method, it's 65536. I use cell_log here make it be same as before.
Maybe don't need be same, what's your opinion? Thanks!

Quoted 37 lines

What about the p->mtu parameter from struct tc_tbf_qopt. I know it is in a "time" format... but hey, you are already using this parameter requoting your patch:

Quoted 4 lines · On Tue, 19 Nov 2013 15:25:38 +0800 Yang Yingliang <[email protected]>…
net/sched/sch_tbf.c +0 -0
index 68f9859..c194129 100644

[... cut ...]

Quoted 23 lines
net/sched/sch_tbf.c +10 -3
@@ -339,30 +326,46 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
  	}
  	q->limit = qopt->limit;
  	q->mtu = PSCHED_TICKS2NS(qopt->mtu);
-	q->max_size = max_size;
  	q->buffer = PSCHED_TICKS2NS(qopt->buffer);
  	q->tokens = q->buffer;
  	q->ptokens = q->mtu;
 
  	if (tb[TCA_TBF_RATE64])
  		rate64 = nla_get_u64(tb[TCA_TBF_RATE64]);
-	psched_ratecfg_precompute(&q->rate, &rtab->rate, rate64);
-	if (ptab) {
+	psched_ratecfg_precompute(&q->rate, &qopt->rate, rate64);
+	if (!q->rate.rate_bytes_ps)
+		goto unlock_done;
+	for (n = 0; n < 65536; n++)
+		if (psched_l2t_ns(&q->rate, n) > q->buffer)
+			break;
+	max_size = min_t(u32, n, (256ULL << qopt->rate.cell_log) - 1);
+
+	if (qopt->peakrate.rate) {
+		int size = 0;
Quoted 9 lines

net/sched/sch_tbf.c static int tbf_change(struct Qdisc *sch, struct nlattr *opt) · line 349

Quoted 6 lines
net/sched/sch_tbf.c +3 -1
  		if (tb[TCA_TBF_PRATE64])
  			prate64 = nla_get_u64(tb[TCA_TBF_PRATE64]);
-		psched_ratecfg_precompute(&q->peak, &ptab->rate, prate64);
+		psched_ratecfg_precompute(&q->peak, &qopt->peakrate, prate64);
+		for (n = 0; n < 65536; n++)
+			if (psched_l2t_ns(&q->peak, n) > q->mtu)

You are using q->mtu here, BUT why are you only doing this, when there is a qopt->peakrate.rate, set??? (I might have missed something)

When qopt->peakrate.rate is not set, q->mtu is 0.

Regards,
Yang

Quoted 8 lines
Quoted 7 lines
net/sched/sch_tbf.c +3 -0
+				break;
+		size = min_t(u32, n, (256ULL << qopt->rate.cell_log) - 1);
+		max_size = min_t(u32, max_size, size);
  		q->peak_present = true;
  	} else {
  		q->peak_present = false;
  	}
#6 lore raw

Re: [PATCH net v3 1/2] net: sched: tbf: fix calculation of max_size

In reply to Yang Yingliang
Quoted 12 lines · Yang Yingliang

commit b757c9336d63f94c6b57532(tbf: improved accuracy at high rates) introduce a regression.

With the follow command:
tc qdisc add dev eth1 root handle 1: tbf latency 50ms burst 10KB rate 30gbit mtu 64k

Without this patch, the max_size value is 10751(bytes).
But, in fact, the real max_size value should be smaller than 7440(bytes). Or a packet whose length is bigger than 7440 will cause network congestion. Because the packet is so big that can't get enough tokens. Even all the tokens in the buffer is given to the packet.

Quoted 3 lines

With this patch, the max_size value is 7440(bytes).
The packets whose length is bigger than 7440(bytes) will be dropped or reshape in tbf_enqueue().

This changelog makes no sense.

If userland asks 'burst 10KB', then burst is 10KB, not 7440.

#7 lore raw

Re: [PATCH net v3 1/2] net: sched: tbf: fix calculation of max_size

Quoted 13 lines · Eric Dumazet
Quoted 12 lines · Yang Yingliang

commit b757c9336d63f94c6b57532(tbf: improved accuracy at high rates) introduce a regression.

With the follow command:
tc qdisc add dev eth1 root handle 1: tbf latency 50ms burst 10KB rate 30gbit mtu 64k

Without this patch, the max_size value is 10751(bytes).
But, in fact, the real max_size value should be smaller than 7440(bytes). Or a packet whose length is bigger than 7440 will cause network congestion. Because the packet is so big that can't get enough tokens. Even all the tokens in the buffer is given to the packet.

Quoted 7 lines
Quoted 3 lines

With this patch, the max_size value is 7440(bytes).
The packets whose length is bigger than 7440(bytes) will be dropped or reshape in tbf_enqueue().

This changelog makes no sense.

If userland asks 'burst 10KB', then burst is 10KB, not 7440.

Ideally burst should be 10KB in kernel space. But at hight rates, when burst is converted to time in tick in userland, it gets much more loss than low rates. So the burst can't actually reach 10KB in kernel.

Quoted 7 lines

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

#8 lore raw

Re: [PATCH net v3 1/2] net: sched: tbf: fix calculation of max_size

Quoted 10 lines · Yang Yingliang

O>

Quoted 4 lines
Quoted 3 lines

With the follow command:
tc qdisc add dev eth1 root handle 1: tbf latency 50ms burst 10KB rate 30gbit mtu 64k

Ideally burst should be 10KB in kernel space. But at hight rates, when burst is converted to time in tick in userland, it gets much more loss than low rates. So the burst can't actually reach 10KB in kernel.

If you think tc can help to fix user choices, please provide an iproute2 patch.

Quite frankly, using a burst of 10KB and a rate of 30gbit is simply a user error. It cannot possibly work. At all.

As stated in many tbf docs, burst must be larger than device mtu (1514)

By extension, with GRO/GSO, burst should be larger than 68130, otherwise we need to segment the packets, and this is horribly expensive for high rates.

I personally tc/tbf needs some changes, because the logical way would be to use the 1514 value for low rates, but if we use this value, the kernel gets a value of 1511, which doesn't work.

#9 lore raw

Re: [PATCH net v3 1/2] net: sched: tbf: fix calculation of max_size

Quoted 6 lines · Eric Dumazet
Quoted 5 lines · Yang Yingliang

O>

Quoted 4 lines
Quoted 3 lines

With the follow command:
tc qdisc add dev eth1 root handle 1: tbf latency 50ms burst 10KB rate 30gbit mtu 64k

Quoted 8 lines
Quoted 5 lines

Ideally burst should be 10KB in kernel space. But at hight rates, when burst is converted to time in tick in userland, it gets much more loss than low rates. So the burst can't actually reach 10KB in kernel.

If you think tc can help to fix user choices, please provide an iproute2 patch.

Unfortunately, it can't. It always has some loss when burst in bytes is converted to buffer in ticks, we cannot avoid it, except we send burst to kernel directly, this need to modify the code both in iproute2 and kernel.

Quoted 3 lines

Quite frankly, using a burst of 10KB and a rate of 30gbit is simply a user error. It cannot possibly work. At all.

Yep, I agree it's a user error. But the error may cause network down, and we have a way to avoid it, I think we should fix it. :)

Quoted 10 lines

As stated in many tbf docs, burst must be larger than device mtu (1514)

By extension, with GRO/GSO, burst should be larger than 68130, otherwise we need to segment the packets, and this is horribly expensive for high rates.

I personally tc/tbf needs some changes, because the logical way would be to use the 1514 value for low rates, but if we use this value, the kernel gets a value of 1511, which doesn't work.

Yep, I agree with your logical way. But I think current logic in kernel cannot support to only do some changes in tc/tbf. We need changes both in tc and kernel. I'll post a patch which uses TCA_TBF_BURST to get burst from tc directly and this patch also need to keep backward compatible with old tc.

Regards,
Yang

#10 lore raw

PATCH 1/1 net: sched: tbf: fix calculation of max_size

From: Yang Yingliang <[email protected]>

Current max_size is caluated from rate table. Now, the rate table has been replaced and it's wrong to caculate max_size based on this rate table. It can lead wrong calculation of max_size.

The burst in kernel may be lower than user asked, because burst may gets some loss when transform it to buffer(E.g. "burst 40kb rate 30mbit/s") and it seems we cannot avoid this loss. And burst's value(max_size) based on rate table may be equal user asked. If a packet's length is max_size, this packet will be stalled in tbf_dequeue() because its length is above the burst in kernel so that it cannot get enough tokens. The max_size guards against enqueuing packet sizes above q->buffer "time" in tbf_enqueue().

This patch fixes the calculation of max_size by using psched_l2t_ns() and q->buffer to recalculate burst(max_size).

Also, add support to get burst from userland directly. We can avoid loss in byte-to-time transform by using burst directly. Iproute2 will need a patch to send burst to kernel.

---
 include/uapi/linux/pkt_sched.h |   2 +
 net/sched/sch_tbf.c            | 110 ++++++++++++++++++++++++++---------------
 2 files changed, 72 insertions(+), 40 deletions(-)
include/uapi/linux/pkt_sched.h +2 -0
index 307f293..b5a0976 100644
@@ -173,6 +173,8 @@ enum {
 	TCA_TBF_PTAB,
 	TCA_TBF_RATE64,
 	TCA_TBF_PRATE64,
+	TCA_TBF_BURST,
+	TCA_TBF_PBURST,
 	__TCA_TBF_MAX,
 };
 
net/sched/sch_tbf.c +70 -40

153 lines not on this page · raw message

-- 1.8.0

#11 lore raw

RE: [PATCH] net: sched: tbf: fix calculation of max_size

Quoted 6 lines

From: Yang Yingliang <[email protected]>

Current max_size is caluated from rate table. Now, the rate table has been replaced and it's wrong to caculate max_size based on this rate table. It can lead wrong calculation of max_size.

Quoted 7 lines

The burst in kernel may be lower than user asked, because burst may gets some loss when transform it to buffer(E.g. "burst 40kb rate 30mbit/s") and it seems we cannot avoid this loss. And burst's value(max_size) based on rate table may be equal user asked. If a packet's length is max_size, this packet will be stalled in tbf_dequeue() because its length is above the burst in kernel so that it cannot get enough tokens. The max_size guards against enqueuing packet sizes above q->buffer "time" in tbf_enqueue().

Why not adjust the calculations so that the number of allocated tokens can go negative?

So allow the transfer if the number of tokens is +ve and then subtract the number needed for the message itself.

I think this would change the semantics of the configured 'burst' value very slightly (to 'at least' from 'at most') but the average would still be correct.

FWIW I've done similar rate limiters that run directly in units of 'time'. The fact that system time advances automatically generates credit.

David

#12 lore raw

Re: [PATCH] net: sched: tbf: fix calculation of max_size

Quoted 14 lines · David Laight
Quoted 6 lines

From: Yang Yingliang <[email protected]>

Current max_size is caluated from rate table. Now, the rate table has been replaced and it's wrong to caculate max_size based on this rate table. It can lead wrong calculation of max_size.

Quoted 7 lines

The burst in kernel may be lower than user asked, because burst may gets some loss when transform it to buffer(E.g. "burst 40kb rate 30mbit/s") and it seems we cannot avoid this loss. And burst's value(max_size) based on rate table may be equal user asked. If a packet's length is max_size, this packet will be stalled in tbf_dequeue() because its length is above the burst in kernel so that it cannot get enough tokens. The max_size guards against enqueuing packet sizes above q->buffer "time" in tbf_enqueue().

Quoted 5 lines

Why not adjust the calculations so that the number of allocated tokens can go negative?

So allow the transfer if the number of tokens is +ve and then subtract the number needed for the message itself.

Thanks for your advice!
I had considered it before. But, I think that we calculate tokens from ns but max_size is calculated based on rate table causes the problem. I think we should make them consistent.

Quoted 4 lines

I think this would change the semantics of the configured 'burst' value very slightly (to 'at least' from 'at most') but the average would still be correct.

Hmm, I'm not sure it is 'at least'. Maybe it could be lower.

Regards,
Yang

Quoted 7 lines

FWIW I've done similar rate limiters that run directly in units of 'time'. The fact that system time advances automatically generates credit.

David

#13 lore raw

Re: [PATCH] net: sched: tbf: fix calculation of max_size

Quoted 18 lines · Yang Yingliang
Quoted 17 lines · David Laight
Quoted 6 lines

From: Yang Yingliang <[email protected]>

Current max_size is caluated from rate table. Now, the rate table has been replaced and it's wrong to caculate max_size based on this rate table. It can lead wrong calculation of max_size.

Quoted 7 lines

The burst in kernel may be lower than user asked, because burst may gets some loss when transform it to buffer(E.g. "burst 40kb rate 30mbit/s") and it seems we cannot avoid this loss. And burst's value(max_size) based on rate table may be equal user asked. If a packet's length is max_size, this packet will be stalled in tbf_dequeue() because its length is above the burst in kernel so that it cannot get enough tokens. The max_size guards against enqueuing packet sizes above q->buffer "time" in tbf_enqueue().

Why not adjust the calculations so that the number of allocated tokens can go negative?

Quoted 8 lines
Quoted 2 lines

So allow the transfer if the number of tokens is +ve and then subtract the number needed for the message itself.

Thanks for your advice!
I had considered it before. But, I think that we calculate tokens from ns but max_size is calculated based on rate table causes the problem. I think we should make them consistent.

Forgot to say, fixing calculation of max_size is also needed by 64bit rates.

Regards,
Yang

maintainer
#14 lore raw

Re: [PATCH] net: sched: tbf: fix calculation of max_size

In reply to David Laight

From: "David Laight" <[email protected]>
Date: Mon, 25 Nov 2013 12:22:30 -0000

Quoted 20 lines
Quoted 6 lines

From: Yang Yingliang <[email protected]>

Current max_size is caluated from rate table. Now, the rate table has been replaced and it's wrong to caculate max_size based on this rate table. It can lead wrong calculation of max_size.

Quoted 7 lines

The burst in kernel may be lower than user asked, because burst may gets some loss when transform it to buffer(E.g. "burst 40kb rate 30mbit/s") and it seems we cannot avoid this loss. And burst's value(max_size) based on rate table may be equal user asked. If a packet's length is max_size, this packet will be stalled in tbf_dequeue() because its length is above the burst in kernel so that it cannot get enough tokens. The max_size guards against enqueuing packet sizes above q->buffer "time" in tbf_enqueue().

Why not adjust the calculations so that the number of allocated tokens can go negative?

So allow the transfer if the number of tokens is +ve and then subtract the number needed for the message itself.

Quoted 6 lines

I think this would change the semantics of the configured 'burst' value very slightly (to 'at least' from 'at most') but the average would still be correct.

FWIW I've done similar rate limiters that run directly in units of 'time'. The fact that system time advances automatically generates credit.

Yang has responded to your concerns, are they addressed?

#15 lore raw

RE: [PATCH] net: sched: tbf: fix calculation of max_size

Quoted 33 lines

-----Original Message-----
From: [email protected] [mailto:[email protected]] On Behalf Of David Miller
Sent: 02 December 2013 01:11
To: David Laight
Cc: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]
Subject: Re: [PATCH] net: sched: tbf: fix calculation of max_size

From: "David Laight" <[email protected]>
Date: Mon, 25 Nov 2013 12:22:30 -0000

Quoted 20 lines
Quoted 6 lines

From: Yang Yingliang <[email protected]>

Current max_size is caluated from rate table. Now, the rate table has been replaced and it's wrong to caculate max_size based on this rate table. It can lead wrong calculation of max_size.

Quoted 7 lines

The burst in kernel may be lower than user asked, because burst may gets some loss when transform it to buffer(E.g. "burst 40kb rate 30mbit/s") and it seems we cannot avoid this loss. And burst's value(max_size) based on rate table may be equal user asked. If a packet's length is max_size, this packet will be stalled in tbf_dequeue() because its length is above the burst in kernel so that it cannot get enough tokens. The max_size guards against enqueuing packet sizes above q->buffer "time" in tbf_enqueue().

Why not adjust the calculations so that the number of allocated tokens can go negative?

So allow the transfer if the number of tokens is +ve and then subtract the number needed for the message itself.

Quoted 8 lines
Quoted 6 lines

I think this would change the semantics of the configured 'burst' value very slightly (to 'at least' from 'at most') but the average would still be correct.

FWIW I've done similar rate limiters that run directly in units of 'time'. The fact that system time advances automatically generates credit.

Yang has responded to your concerns, are they addressed?

I was mostly making some suggestions that might have made fixing it easier. So I'm not really worried.

David

maintainer
#16 lore raw

Re: [PATCH] net: sched: tbf: fix calculation of max_size

In reply to Yang Yingliang

From: Yang Yingliang <[email protected]>
Date: Mon, 25 Nov 2013 20:04:23 +0800

Quoted 17 lines

From: Yang Yingliang <[email protected]>

Current max_size is caluated from rate table. Now, the rate table has been replaced and it's wrong to caculate max_size based on this rate table. It can lead wrong calculation of max_size.

The burst in kernel may be lower than user asked, because burst may gets some loss when transform it to buffer(E.g. "burst 40kb rate 30mbit/s") and it seems we cannot avoid this loss. And burst's value(max_size) based on rate table may be equal user asked. If a packet's length is max_size, this packet will be stalled in tbf_dequeue() because its length is above the burst in kernel so that it cannot get enough tokens. The max_size guards against enqueuing packet sizes above q->buffer "time" in tbf_enqueue().

This patch fixes the calculation of max_size by using psched_l2t_ns() and q->buffer to recalculate burst(max_size).

Quoted 6 lines

Also, add support to get burst from userland directly. We can avoid loss in byte-to-time transform by using burst directly. Iproute2 will need a patch to send burst to kernel.

I don't see why you need to add the userland explicit burst capability to fix the calculation of max_size.

These two things are separate, the new netlink attributes are a new feature.

Therefore, please submit these two things separately. First, submit the pure max_size bug fix for 'net'. Then when I open 'net-next' back up you can submit the support for the new netlink attributes.

Thanks.

#17 lore raw

Re: [PATCH] net: sched: tbf: fix calculation of max_size

Quoted 30 lines · David Miller

From: Yang Yingliang <[email protected]>
Date: Mon, 25 Nov 2013 20:04:23 +0800

Quoted 17 lines

From: Yang Yingliang <[email protected]>

Current max_size is caluated from rate table. Now, the rate table has been replaced and it's wrong to caculate max_size based on this rate table. It can lead wrong calculation of max_size.

The burst in kernel may be lower than user asked, because burst may gets some loss when transform it to buffer(E.g. "burst 40kb rate 30mbit/s") and it seems we cannot avoid this loss. And burst's value(max_size) based on rate table may be equal user asked. If a packet's length is max_size, this packet will be stalled in tbf_dequeue() because its length is above the burst in kernel so that it cannot get enough tokens. The max_size guards against enqueuing packet sizes above q->buffer "time" in tbf_enqueue().

This patch fixes the calculation of max_size by using psched_l2t_ns() and q->buffer to recalculate burst(max_size).

Quoted 6 lines

Also, add support to get burst from userland directly. We can avoid loss in byte-to-time transform by using burst directly. Iproute2 will need a patch to send burst to kernel.

I don't see why you need to add the userland explicit burst capability to fix the calculation of max_size.

Quoted 9 lines

These two things are separate, the new netlink attributes are a new feature.

Therefore, please submit these two things separately. First, submit the pure max_size bug fix for 'net'. Then when I open 'net-next' back up you can submit the support for the new netlink attributes.

Thanks.

OK, I'll send a v4.

Regards,
Yang

Quoted 3 lines

.

#18 lore raw

PATCH v3 2/2 net: sched: htb: fix calculation of quantum

In reply to Yang Yingliang

Now, 32bit rates may be not the true rate.
So use rate_bytes_ps which is from
max(rate32, rate64) to calcualte quantum.

---
 net/sched/sch_htb.c | 18 ++++++++++--------
 1 file changed, 10 insertions(+), 8 deletions(-)
net/sched/sch_htb.c +10 -8
index 0e1e38b..57c6678 100644
@@ -1477,11 +1477,20 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 		sch_tree_lock(sch);
 	}
 
+	rate64 = tb[TCA_HTB_RATE64] ? nla_get_u64(tb[TCA_HTB_RATE64]) : 0;
+
+	ceil64 = tb[TCA_HTB_CEIL64] ? nla_get_u64(tb[TCA_HTB_CEIL64]) : 0;
+
+	psched_ratecfg_precompute(&cl->rate, &hopt->rate, rate64);
+	psched_ratecfg_precompute(&cl->ceil, &hopt->ceil, ceil64);
+
 	/* it used to be a nasty bug here, we have to check that node
 	 * is really leaf before changing cl->un.leaf !
 	 */
 	if (!cl->level) {
-		cl->quantum = hopt->rate.rate / q->rate2quantum;
+		u64 quantum = div64_u64(cl->rate.rate_bytes_ps,
+					q->rate2quantum);
+		cl->quantum = min_t(u64, quantum, INT_MAX);
 		if (!hopt->quantum && cl->quantum < 1000) {
 			pr_warning(
 			       "HTB: quantum of class %X is small. Consider r2q change.\n",
@@ -1500,13 +1509,6 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 			cl->prio = TC_HTB_NUMPRIO - 1;
 	}
 
-	rate64 = tb[TCA_HTB_RATE64] ? nla_get_u64(tb[TCA_HTB_RATE64]) : 0;
-
-	ceil64 = tb[TCA_HTB_CEIL64] ? nla_get_u64(tb[TCA_HTB_CEIL64]) : 0;
-
-	psched_ratecfg_precompute(&cl->rate, &hopt->rate, rate64);
-	psched_ratecfg_precompute(&cl->ceil, &hopt->ceil, ceil64);
-
 	cl->buffer = PSCHED_TICKS2NS(hopt->buffer);
 	cl->cbuffer = PSCHED_TICKS2NS(hopt->cbuffer);
 
Signature · 1 line
1.8.0