[PATCH 0/3] net: sched: fix some issues introduced by 64bit rates

[PATCH 0/3] net: sched: fix some issues introduced by 64bit rates

[Yang Yingliang]

TBF and HTB support 64bit rates now.
But some parameters are calulated from 32bit rates.
So calculate these parameters with rate_bytes_ps which
is the true rates.

Fix the condition of failure when rate is 0.
Fix the caculations of max_size in tbf and quantum in htb.

Yang Yingliang (3):
  net_sched: tbf: fix calculation of max_size
  net_sched: htb: fix condition of failure when rate is 0
  net_sched: htb: fix calculation of quantum

 include/net/sch_generic.h | 46 ++++++++++++++++++++++++++++++++
 net/sched/sch_htb.c       | 21 ++++++++-------
 net/sched/sch_tbf.c       | 67 ++++++++++++++++++++++++++---------------------
 3 files changed, 95 insertions(+), 39 deletions(-)

-- 
1.7.12

[PATCH 1/3] net: sched: tbf: fix calculation of max_size

[Yang Yingliang]

Current max_size is caluated from rate table.
Now, the rate table has been replaced and it's
not proper to caculate max_size with rate64.
Use psched_ns_t2l to calculate the max_size.

psched_ns_t2l():convert time in ns to length in
bytes which to determinate how many bytes can be
sent in given time.

Signed-off-by: Yang Yingliang <yangyingliang@huawei.com>
---
 include/net/sch_generic.h | 46 ++++++++++++++++++++++++++++++++
 net/sched/sch_tbf.c       | 67 ++++++++++++++++++++++++++---------------------
 2 files changed, 83 insertions(+), 30 deletions(-)

diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index d0a6321..8da64f3 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -701,6 +701,52 @@ static inline u64 psched_l2t_ns(const struct psched_ratecfg *r,
 	return ((u64)len * r->mult) >> r->shift;
 }
 
+/* Time to Length, convert time in ns to length in bytes
+ * to determinate how many bytes can be sent in given time.
+ */
+static inline u64 psched_ns_t2l(const struct psched_ratecfg *r,
+				u64 time_in_ns)
+{
+	u64 len = time_in_ns;
+	u8 shift = r->shift;
+	bool is_div = false;
+
+	/* The formula is :
+	 * len = (time_in_ns << shift) / mult
+	 * when time_in_ns does shift, it would overflow.
+	 * If overflow happens first time, do division.
+	 * Then do shift. If it happens again,
+	 * set lenth to ~0ULL.
+	 */
+	while (shift) {
+		if (len & (1ULL << 63)) {
+			if (!is_div) {
+				len = div64_u64(len, r->mult);
+				is_div = true;
+			} else {
+				/* overflow happens */
+				len = ~0ULL;
+				is_div = true;
+				break;
+			}
+		}
+		len <<= 1;
+		shift--;
+	}
+	if (!is_div)
+		len = div64_u64(len, r->mult);
+
+	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
+		len = (len / 53) * 48;
+
+	if (len > r->overhead)
+		len -= r->overhead;
+	else
+		len = 0;
+
+	return len;
+}
+
 void psched_ratecfg_precompute(struct psched_ratecfg *r,
 			       const struct tc_ratespec *conf,
 			       u64 rate64);
diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
index 68f9859..eb9ce7b 100644
--- a/net/sched/sch_tbf.c
+++ b/net/sched/sch_tbf.c
@@ -279,7 +279,7 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
 	struct qdisc_rate_table *rtab = NULL;
 	struct qdisc_rate_table *ptab = NULL;
 	struct Qdisc *child = NULL;
-	int max_size, n;
+	u32 max_size = 0;
 	u64 rate64 = 0, prate64 = 0;
 
 	err = nla_parse_nested(tb, TCA_TBF_MAX, opt, tbf_policy);
@@ -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,25 +326,45 @@ 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;
+	max_size = min_t(u64, psched_ns_t2l(&q->rate, q->buffer), ~0);
+	max_size = min_t(u32, max_size, (256 << qopt->rate.cell_log) - 1);
+
+	if (qopt->peakrate.rate) {
+		u64 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);
+		size = psched_ns_t2l(&q->peak, q->mtu);
+		max_size = min_t(u64, max_size, size);
+		max_size = min_t(u32,
+				 max_size,
+				 (256 << qopt->peakrate.cell_log) - 1);
 		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;
+
+	if (0) {
+unlock_done:
+		sch_tree_unlock(sch);
+		err = -EINVAL;
+	}
 done:
 	if (rtab)
 		qdisc_put_rtab(rtab);
-- 
1.7.12

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

[Eric Dumazet]

On Thu, 2013-11-14 at 17:01 +0800, Yang Yingliang wrote:
> Current max_size is caluated from rate table.
> Now, the rate table has been replaced and it's
> not proper to caculate max_size with rate64.
> Use psched_ns_t2l to calculate the max_size.
> 
> psched_ns_t2l():convert time in ns to length in
> bytes which to determinate how many bytes can be
> sent in given time.

I have no evidence you fix a real bug.

Please provide a tc script and show us it breaks.

Also CC Jesper you wrote this code.

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

[Yang Yingliang]

On 2013/11/14 22:38, Eric Dumazet wrote:
> On Thu, 2013-11-14 at 17:01 +0800, Yang Yingliang wrote:
>> Current max_size is caluated from rate table.
>> Now, the rate table has been replaced and it's
>> not proper to caculate max_size with rate64.
>> Use psched_ns_t2l to calculate the max_size.
>>
>> psched_ns_t2l():convert time in ns to length in
>> bytes which to determinate how many bytes can be
>> sent in given time.
> 
> I have no evidence you fix a real bug.
> 
> Please provide a tc script and show us it breaks.
> 
> Also CC Jesper you wrote this code.

I'm sorry I made a mistake in my early description.

Here is the bug's description.
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().

Regards,
Yang

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

[PATCH 2/3] net: sched: htb: fix condition of failure when rate is 0

[Yang Yingliang]

When rate32 is 0, it doesn't means wrong.
Because htb support 64bit rates now, it
could use rate64.
So change the condition, when rate32 and
rate64 are both 0, it goes to failure.

Signed-off-by: Yang Yingliang <yangyingliang@huawei.com>
---
 net/sched/sch_htb.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 0e1e38b..f983803 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -1357,7 +1357,8 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 	parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
 
 	hopt = nla_data(tb[TCA_HTB_PARMS]);
-	if (!hopt->rate.rate || !hopt->ceil.rate)
+	if ((!hopt->rate.rate && !tb[TCA_HTB_RATE64]) ||
+	    (!hopt->ceil.rate && !tb[TCA_HTB_CEIL64]))
 		goto failure;
 
 	/* Keeping backward compatible with rate_table based iproute2 tc */
-- 
1.7.12

Re: [PATCH 2/3] net: sched: htb: fix condition of failure when rate is 0

[Eric Dumazet]

On Thu, 2013-11-14 at 17:01 +0800, Yang Yingliang wrote:
> When rate32 is 0, it doesn't means wrong.
> Because htb support 64bit rates now, it
> could use rate64.
> So change the condition, when rate32 and
> rate64 are both 0, it goes to failure.

This is not needed at all and buggy.

User land is supposed to provide a not zero 32bit rate.

If it does, too bad. We have to fail.

[PATCH 3/3] net: sched: htb: fix calculation of quantum

[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.

Signed-off-by: Yang Yingliang <yangyingliang@huawei.com>
---
 net/sched/sch_htb.c | 18 ++++++++++--------
 1 file changed, 10 insertions(+), 8 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index f983803..9474294 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -1478,11 +1478,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",
@@ -1501,13 +1510,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);
 
-- 
1.7.12

Re: [PATCH 3/3] net: sched: htb: fix calculation of quantum

[Eric Dumazet]

On Thu, 2013-11-14 at 17:01 +0800, Yang Yingliang wrote:
> Now, 32bit rates may be not the true rate.
> So use rate_bytes_ps which is from
> max(rate32, rate64) to calcualte quantum.
> 
> Signed-off-by: Yang Yingliang <yangyingliang@huawei.com>
> ---
>  net/sched/sch_htb.c | 18 ++++++++++--------
>  1 file changed, 10 insertions(+), 8 deletions(-)

Acked-by: Eric Dumazet <edumazet@google.com>