Skip to contentSkip to conversation

net: sched: fix two issues

PATCH Superseded Yang Yingliang 3 participants 14 messages Dec 6, 2013 – Dec 10, 2013

Subsystems (3)

v6 of 7 Superseded Latest is v7 →

lore
Share & tools
lore
#0 lore raw

v6 cover net: sched: fix two issues

fix calculation of max_size in tbf
fix quantum calculation introduced by 64bit rates.

v6
patch 1/2:
1.Use a simpler and better way to calculate length in psched_ns_t2l(). 2.Replace pr_err() with pr_warn_ratelimited().

patch 2/2: Replace div64_u64() with do_div() suggested by Eric.

v5
patch 1/2:
1.Remove rtab and ptab use suggested by Eric. 2.Don't reduce max_size to 65536, as Eric suggested that
if a burst set to 200KB, we do not want tbf use 64KB or even less. So add a helper psched_ns_t2l to calculate max_size directly.

v4
patch 1/2:
1.Update commit message suggested by Jesper.
2.Use a macro to replace 65535 constant.
3.Add condition that when peakrate is lower than rate, return -EINVAL. 4.Don't use cell_log anymore.

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

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

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

 net/sched/sch_htb.c |  20 ++++++----
 net/sched/sch_tbf.c | 104 ++++++++++++++++++++++++++++++----------------------
 2 files changed, 73 insertions(+), 51 deletions(-)
Signature · 1 line
1.8.0
#1 lore raw

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

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. 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().

To make consistent with the calculation of tokens, this patch add a helper psched_ns_t2l() to calculate burst(max_size) directly to fix this problem.

After this fix, we can support to using 64bit rates to calculate burst as well.

---
 net/sched/sch_tbf.c | 104 ++++++++++++++++++++++++++++++----------------------
 1 file changed, 61 insertions(+), 43 deletions(-)
net/sched/sch_tbf.c +61 -43
index a609005..dd731f5 100644
@@ -118,6 +118,30 @@ struct tbf_sched_data {
 };
 
 
+/* Time to Length, convert time in ns to length in bytes
+ * to determinate how many bytes can be sent in given time.
+ */
+static u64 psched_ns_t2l(const struct psched_ratecfg *r,
+			 u64 time_in_ns)
+{
+	/* The formula is :
+	 * len = (time_in_ns * r->rate_bytes_ps) / NSEC_PER_SEC
+	 */
+	u64 len = time_in_ns * r->rate_bytes_ps;
+
+	do_div(len, NSEC_PER_SEC);
+
+	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
+		len = (len / 53) * 48;
+
+	if (len > r->overhead)
+		len -= r->overhead;
+	else
+		len = 0;
+
+	return len;
+}
+
 /*
  * Return length of individual segments of a gso packet,
  * including all headers (MAC, IP, TCP/UDP)
@@ -289,10 +313,8 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
 	struct tbf_sched_data *q = qdisc_priv(sch);
 	struct nlattr *tb[TCA_TBF_MAX + 1];
 	struct tc_tbf_qopt *qopt;
-	struct qdisc_rate_table *rtab = NULL;
-	struct qdisc_rate_table *ptab = NULL;
 	struct Qdisc *child = NULL;
-	int max_size, n;
+	u64 max_size;
 	u64 rate64 = 0, prate64 = 0;
 
 	err = nla_parse_nested(tb, TCA_TBF_MAX, opt, tbf_policy);
@@ -304,38 +326,13 @@ 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)
+		qdisc_put_rtab(qdisc_get_rtab(&qopt->rate,
+					      tb[TCA_TBF_RTAB]));
 
-	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 (max_size < 0)
-		goto done;
-
-	if (max_size < psched_mtu(qdisc_dev(sch)))
-		pr_warn_ratelimited("sch_tbf: burst %u is lower than device %s mtu (%u) !\n",
-				    max_size, qdisc_dev(sch)->name,
-				    psched_mtu(qdisc_dev(sch)));
+	if (qopt->peakrate.linklayer == TC_LINKLAYER_UNAWARE)
+			qdisc_put_rtab(qdisc_get_rtab(&qopt->peakrate,
+						      tb[TCA_TBF_PTAB]));
 
 	if (q->qdisc != &noop_qdisc) {
 		err = fifo_set_limit(q->qdisc, qopt->limit);
@@ -357,30 +354,51 @@ 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), ~0U);
+
+	if (qopt->peakrate.rate) {
 		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);
+		if (q->peak.rate_bytes_ps <= q->rate.rate_bytes_ps) {
+			pr_warn_ratelimited("sch_tbf: peakrate %llu is lower than or equals to rate %llu !\n",
+					    q->peak.rate_bytes_ps, q->rate.rate_bytes_ps);
+			goto unlock_done;
+		}
+
+		max_size = min_t(u64, max_size, psched_ns_t2l(&q->peak, q->mtu));
 		q->peak_present = true;
 	} else {
 		q->peak_present = false;
 	}
 
+	if (max_size < psched_mtu(qdisc_dev(sch)))
+		pr_warn_ratelimited("sch_tbf: burst %llu is lower than device %s mtu (%u) !\n",
+				    max_size, qdisc_dev(sch)->name,
+				    psched_mtu(qdisc_dev(sch)));
+
+	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 v6 1/2] net: sched: tbf: fix the calculation of max_size

Quoted 1 line

From: Yang Yingliang

...

net/sched/sch_tbf.c struct tbf_sched_data { · line 132

Quoted 13 lines
net/sched/sch_tbf.c +12 -0
+/* Time to Length, convert time in ns to length in bytes
+ * to determinate how many bytes can be sent in given time.
+ */
+static u64 psched_ns_t2l(const struct psched_ratecfg *r,
+			 u64 time_in_ns)
+{
+	/* The formula is :
+	 * len = (time_in_ns * r->rate_bytes_ps) / NSEC_PER_SEC
+	 */
+	u64 len = time_in_ns * r->rate_bytes_ps;
+
+	do_div(len, NSEC_PER_SEC);

You are multiplying two values then dividing by 10**9 I'd guess that the intermediate value might exceed 2**64.

net/sched/sch_tbf.c struct tbf_sched_data { · line 135

Quoted 2 lines
net/sched/sch_tbf.c +2 -0
+	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
+		len = (len / 53) * 48;

You probably want to do the multiply first.
But why not scale rate_bytes_ps instead.

net/sched/sch_tbf.c struct tbf_sched_data { · line 143

Quoted 7 lines
net/sched/sch_tbf.c +7 -0
+	if (len > r->overhead)
+		len -= r->overhead;
+	else
+		len = 0;
+
+	return len;
+}

Personally I'd work out how much time you have to send each byte. So if you want a rate of 1MB/sec you have a 'time cost' per byte of 1000ns. The cost of sending a packet is simply the length multiplied by this cost. To work out whether a packet can be sent you have a credit variable that tracks current time.
If 'credit > now' the packet can't be sent, queue and schedule a wakeup. if 'credit + backlog < now' set credit = now - backlog.
if 'credit <= now' send the packet and add the packet's 'cost' to 'credit'.

In the non-ratelimited case this is almost no work.

You'd probably need to work in 1/1024ns time units and/or blocks of 16 bytes.

David

#3 lore raw

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

Quoted 18 lines · David Laight
Quoted 1 line

From: Yang Yingliang

...

net/sched/sch_tbf.c struct tbf_sched_data { · line 132

Quoted 13 lines
net/sched/sch_tbf.c +12 -0
+/* Time to Length, convert time in ns to length in bytes
+ * to determinate how many bytes can be sent in given time.
+ */
+static u64 psched_ns_t2l(const struct psched_ratecfg *r,
+			 u64 time_in_ns)
+{
+	/* The formula is :
+	 * len = (time_in_ns * r->rate_bytes_ps) / NSEC_PER_SEC
+	 */
+	u64 len = time_in_ns * r->rate_bytes_ps;
+
+	do_div(len, NSEC_PER_SEC);

You are multiplying two values then dividing by 10**9 I'd guess that the intermediate value might exceed 2**64.

I thought the max value of len is burst which is a type of u32 sent userland, so the max value of (time_in_ns * r->rate_bytes_ps) should be 64K*(10**9).
Hmm, maybe I should do something in this helper to avoid overflow.

Quoted 35 lines

net/sched/sch_tbf.c struct tbf_sched_data { · line 135

Quoted 3 lines
net/sched/sch_tbf.c +2 -0
+	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
+		len = (len / 53) * 48;

You probably want to do the multiply first.
But why not scale rate_bytes_ps instead.

net/sched/sch_tbf.c struct tbf_sched_data { · line 143

Quoted 7 lines
net/sched/sch_tbf.c +7 -0
+	if (len > r->overhead)
+		len -= r->overhead;
+	else
+		len = 0;
+
+	return len;
+}

Personally I'd work out how much time you have to send each byte. So if you want a rate of 1MB/sec you have a 'time cost' per byte of 1000ns. The cost of sending a packet is simply the length multiplied by this cost. To work out whether a packet can be sent you have a credit variable that tracks current time.
If 'credit > now' the packet can't be sent, queue and schedule a wakeup. if 'credit + backlog < now' set credit = now - backlog.
if 'credit <= now' send the packet and add the packet's 'cost' to 'credit'.

In the non-ratelimited case this is almost no work.

You'd probably need to work in 1/1024ns time units and/or blocks of 16 bytes.

David

.

#4 lore raw

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

In reply to David Laight
Quoted 19 lines · David Laight
Quoted 1 line

From: Yang Yingliang

...

net/sched/sch_tbf.c struct tbf_sched_data { · line 132

Quoted 13 lines
net/sched/sch_tbf.c +12 -0
+/* Time to Length, convert time in ns to length in bytes
+ * to determinate how many bytes can be sent in given time.
+ */
+static u64 psched_ns_t2l(const struct psched_ratecfg *r,
+			 u64 time_in_ns)
+{
+	/* The formula is :
+	 * len = (time_in_ns * r->rate_bytes_ps) / NSEC_PER_SEC
+	 */
+	u64 len = time_in_ns * r->rate_bytes_ps;
+
+	do_div(len, NSEC_PER_SEC);

You are multiplying two values then dividing by 10**9 I'd guess that the intermediate value might exceed 2**64.

Quoted 6 lines

net/sched/sch_tbf.c struct tbf_sched_data { · line 135

Quoted 2 lines
net/sched/sch_tbf.c +2 -0
+	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
+		len = (len / 53) * 48;

You probably want to do the multiply first.
But why not scale rate_bytes_ps instead.

When the linklayer is ATM, the formula to calculate tokens is:

((u64)(DIV_ROUND_UP(len,48)*53) * r->mult) >> r->shift

So, I scale len here.

Regards,
Yang

#5 lore raw

RE: [PATCH net v6 1/2] net: sched: tbf: fix the calculation of max_size

Quoted 15 lines

From: Yang Yingliang

Quoted 12 lines · David Laight
Quoted 1 line

From: Yang Yingliang

...

You are multiplying two values then dividing by 10**9 I'd guess that the intermediate value might exceed 2**64.

net/sched/sch_tbf.c struct tbf_sched_data { · line 135

Quoted 2 lines
net/sched/sch_tbf.c +2 -0
+	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
+		len = (len / 53) * 48;

You probably want to do the multiply first.
But why not scale rate_bytes_ps instead.

Quoted 5 lines

When the linklayer is ATM, the formula to calculate tokens is:

((u64)(DIV_ROUND_UP(len,48)*53) * r->mult) >> r->shift

So, I scale len here.

Seems to me that there are a lot of unnecessary multiplies and divides going on here.
Looks to me like the code was originally written to require one multiply and one shift for each packet.

In any case the latter code is allowing for more of the ATM cell overhead. I'm not at all sure the intent is to remove that when setting up the constants.

OTOH should this code be worrying about the packet overheads at all? Does it add in the ethernet pre-emable, CRC and inter packet gap?

I'd guess that the most the ATM code should do it round the length up to a multiple of 48 (user payload in a cell).

David

#6 lore raw

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

Quoted 17 lines · David Laight
Quoted 17 lines

From: Yang Yingliang

Quoted 12 lines · David Laight
Quoted 1 line

From: Yang Yingliang

...

You are multiplying two values then dividing by 10**9 I'd guess that the intermediate value might exceed 2**64.

net/sched/sch_tbf.c struct tbf_sched_data { · line 135

Quoted 2 lines
net/sched/sch_tbf.c +2 -0
+	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
+		len = (len / 53) * 48;

You probably want to do the multiply first.
But why not scale rate_bytes_ps instead.

When the linklayer is ATM, the formula to calculate tokens is:

Quoted 8 lines
Quoted 3 lines

((u64)(DIV_ROUND_UP(len,48)*53) * r->mult) >> r->shift

So, I scale len here.

Seems to me that there are a lot of unnecessary multiplies and divides going on here.
Looks to me like the code was originally written to require one multiply and one shift for each packet.

The way to calc tokens in psched_l2t_ns() means:
we got a payload which length is 'len'. To get the actual size we need send, round len up to a multiple of 53. After getting the size, we do multiply and shift to calculate tokens that we need.

Quoted 7 lines

In any case the latter code is allowing for more of the ATM cell overhead. I'm not at all sure the intent is to remove that when setting up the constants.

OTOH should this code be worrying about the packet overheads at all? Does it add in the ethernet pre-emable, CRC and inter packet gap?

This overhead is sent from userspace by tc.

Quoted 3 lines

I'd guess that the most the ATM code should do it round the length up to a multiple of 48 (user payload in a cell).

53 is ATM cell size include header, sending a header needs tokens as well. I'd guess round the length up to a multiple of 53 in psched_l2t_ns() is necessary.

Regards,
Yang

#7 lore raw

RFC PATCH 1/1 net: sched: tbf: fix the 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. 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().

To make consistent with the calculation of tokens, this patch add a helper psched_ns_t2l() to calculate burst(max_size) directly to fix this problem.

After this fix, we can support to using 64bit rates to calculate burst as well.

---
 net/sched/sch_tbf.c | 203 +++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 155 insertions(+), 48 deletions(-)
net/sched/sch_tbf.c +155 -48
index a609005..b692d02 100644
@@ -117,6 +117,115 @@ struct tbf_sched_data {
 	struct qdisc_watchdog watchdog;	/* Watchdog timer */
 };
 
+/* do (u64 + u64) with checking if overflows */
+static u64 do_plus64(u64 a, u64 b)
+{
+
+	short shift = 0;
+
+	if (a == ULLONG_MAX || b == ULLONG_MAX)
+		return ULLONG_MAX;
+
+	while (shift <= 63) {
+		u64 _a = a << shift;
+		u64 _b = b << shift;
+		if (_a & _b & (1ULL << 63)) {
+			/* overflow happens */
+			return ULLONG_MAX;
+		} else if (!((_a | _b) & (1ULL << 63))) {
+			/* won't overflow*/
+			return a + b;
+		}
+		shift++;
+	}
+
+	return a + b;
+}
+
+
+/* Time to Length, convert time in ns to length in bytes
+ * to determinate how many bytes can be sent in given time.
+ */
+static u64 psched_ns_t2l(const struct psched_ratecfg *r,
+			 u64 time_in_ns)
+{
+	/* The original formula is :
+	 * len = (time_in_ns * rate_bytes_ps) / NSEC_PER_SEC =>
+	 *
+	 * len = time_in_ns * (rate_bytes_ps / NSEC_PER_SEC) +
+	 *	 time_in_ns * ((rate_bytes_ps % NSEC_PER_SEC) / NSEC_PER_SEC)
+	 *
+	 * time_in_ns * ((rate_bytes_ps % NSEC_PER_SEC) / NSEC_PER_SEC) =>
+	 * (rate_bytes_ps % NSEC_PER_SEC) * (time_in_ns / NSEC_PER_SEC +
+	 * 				     (time_in_ns % NSEC_PER_SEC) / NSEC_PER_SEC)
+	 *
+	 * The final formula is:
+	 * len = time_in_ns * (rate_bytes_ps / NSEC_PER_SEC) +
+	 *	 time_in_ns * ((rate_bytes_ps % NSEC_PER_SEC) / NSEC_PER_SEC) +
+	 *	 (time_in_ns % NSEC_PER_SEC) * (rate_bytes_ps % NSEC_PER_SEC) / NSEC_PER_SEC
+	 */
+	u64 r_integer = r->rate_bytes_ps / NSEC_PER_SEC;
+	u64 multi64 = 0;
+	u32 multi32 = 0;
+	u64 len = 0;
+
+	/* step1. calulate: time_in_ns * (rate_bytes_ps / NSEC_PER_SEC)
+	 *
+	 * u64 * u64, if both of them bigger than UINT_MAX, it will overflows,
+	 * so equals to u64 * u32 => (High1+Low1) * (0+Low2) =>
+	 * (H1*L2)<<32 + (L1*L2)
+	 */
+	if (time_in_ns >> 32 && r_integer >> 32) {
+		/* overflow happens */
+		len = ULLONG_MAX;
+	} else if (time_in_ns >> 32) {
+		multi64 = time_in_ns;
+		multi32 = r_integer;
+	} else if (r_integer >> 32) {
+		multi64 = r_integer;
+		multi32 = time_in_ns;
+	} else
+		len = r_integer * time_in_ns;
+
+	if (!len) {
+		/* len = H1 * L2 */
+		len = (multi64 >> 32) * multi32;
+		if (len > UINT_MAX) {
+			/* overflow happens */
+			len = ULLONG_MAX;
+		} else {
+			/* len = (H1 * L2) << 32 */
+			len <<= 32;
+
+			/* len = (H1 * L2) << 32 + (L1 * L2) */
+			len = do_plus64(len, (multi64 & ~0U) * multi32);
+		}
+	}
+
+	/* step2. calulate: len +
+	 * time_in_ns * ((rate_bytes_ps % NSEC_PER_SEC) / NSEC_PER_SEC)
+	 */
+	len = do_plus64(len,
+			time_in_ns *
+			((r->rate_bytes_ps % NSEC_PER_SEC) / NSEC_PER_SEC));
+
+	/* step3. calulate: len +
+	 * (time_in_ns % NSEC_PER_SEC) * (rate_bytes_ps % NSEC_PER_SEC) / NSEC_PER_SEC */
+	len = do_plus64(len,
+			(time_in_ns % NSEC_PER_SEC) *
+			(r->rate_bytes_ps % NSEC_PER_SEC) /
+			NSEC_PER_SEC);
+
+	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
+		len = (len / 53) * 48;
+
+	if (len > r->overhead)
+		len -= r->overhead;
+	else
+		len = 0;
+
+	return len;
+}
 
 /*
  * Return length of individual segments of a gso packet,
@@ -289,10 +398,9 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
 	struct tbf_sched_data *q = qdisc_priv(sch);
 	struct nlattr *tb[TCA_TBF_MAX + 1];
 	struct tc_tbf_qopt *qopt;
-	struct qdisc_rate_table *rtab = NULL;
-	struct qdisc_rate_table *ptab = NULL;
 	struct Qdisc *child = NULL;
-	int max_size, n;
+	u64 max_size;
+	s64 buffer, mtu;
 	u64 rate64 = 0, prate64 = 0;
 
 	err = nla_parse_nested(tb, TCA_TBF_MAX, opt, tbf_policy);
@@ -304,38 +412,13 @@ 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;
-	}
-
-	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 (max_size < 0)
-		goto done;
+	if (qopt->rate.linklayer == TC_LINKLAYER_UNAWARE)
+		qdisc_put_rtab(qdisc_get_rtab(&qopt->rate,
+					      tb[TCA_TBF_RTAB]));
 
-	if (max_size < psched_mtu(qdisc_dev(sch)))
-		pr_warn_ratelimited("sch_tbf: burst %u is lower than device %s mtu (%u) !\n",
-				    max_size, qdisc_dev(sch)->name,
-				    psched_mtu(qdisc_dev(sch)));
+	if (qopt->peakrate.linklayer == TC_LINKLAYER_UNAWARE)
+			qdisc_put_rtab(qdisc_get_rtab(&qopt->peakrate,
+						      tb[TCA_TBF_PTAB]));
 
 	if (q->qdisc != &noop_qdisc) {
 		err = fifo_set_limit(q->qdisc, qopt->limit);
@@ -349,38 +432,62 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
 		}
 	}
 
+	buffer = PSCHED_TICKS2NS(qopt->buffer);
+	mtu = PSCHED_TICKS2NS(qopt->mtu);
+
 	sch_tree_lock(sch);
 	if (child) {
 		qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
 		qdisc_destroy(q->qdisc);
 		q->qdisc = child;
 	}
-	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, buffer), ~0U);
+
+	if (qopt->peakrate.rate) {
 		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);
+		if (q->peak.rate_bytes_ps <= q->rate.rate_bytes_ps) {
+			pr_warn_ratelimited("sch_tbf: peakrate %llu is lower than or equals to rate %llu !\n",
+					    q->peak.rate_bytes_ps, q->rate.rate_bytes_ps);
+			goto unlock_done;
+		}
+
+		max_size = min_t(u64, max_size, psched_ns_t2l(&q->peak, mtu));
 		q->peak_present = true;
 	} else {
 		q->peak_present = false;
 	}
 
+	if (!max_size)
+		goto unlock_done;
+
+	if (max_size < psched_mtu(qdisc_dev(sch)))
+		pr_warn_ratelimited("sch_tbf: burst %llu is lower than device %s mtu (%u) !\n",
+				    max_size, qdisc_dev(sch)->name,
+				    psched_mtu(qdisc_dev(sch)));
+
+	q->limit = qopt->limit;
+	q->mtu = mtu;
+	q->max_size = max_size;
+	q->buffer = buffer;
+	q->tokens = q->buffer;
+	q->ptokens = q->mtu;
+
 	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;
 }
 

-- 1.8.0

#8 lore raw

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

Quoted 17 lines · Yang Yingliang

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. 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().

To make consistent with the calculation of tokens, this patch add a helper psched_ns_t2l() to calculate burst(max_size) directly to fix this problem.

Quoted 6 lines

After this fix, we can support to using 64bit rates to calculate burst as well.

---
 net/sched/sch_tbf.c | 203 +++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 155 insertions(+), 48 deletions(-)

There is no way I am going to study this patch.

There is no way 32bit * 32bit multiply can overflow 64bit.

If the user gave a stupid input, like a buffer bigger than 4 sec, just say no. Nobody ever did such stupid things in the past, and nobody will do in the future because it is so wrong and useless.

q->mtu = max_t(u64, ~0U, PSCHED_TICKS2NS(qopt->mtu));

q->buffer = max_t(u64, ~0U, PSCHED_TICKS2NS(qopt->buffer));

Could we keep this code understandable, please ?

#9 lore raw

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

Quoted 34 lines · Eric Dumazet
Quoted 17 lines · Yang Yingliang

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. 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().

To make consistent with the calculation of tokens, this patch add a helper psched_ns_t2l() to calculate burst(max_size) directly to fix this problem.

Quoted 6 lines

After this fix, we can support to using 64bit rates to calculate burst as well.

---
 net/sched/sch_tbf.c | 203 +++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 155 insertions(+), 48 deletions(-)

There is no way I am going to study this patch.

There is no way 32bit * 32bit multiply can overflow 64bit.

If the user gave a stupid input, like a buffer bigger than 4 sec, just say no. Nobody ever did such stupid things in the past, and nobody will do in the future because it is so wrong and useless.

Quoted 5 lines

q->mtu = max_t(u64, ~0U, PSCHED_TICKS2NS(qopt->mtu));

q->buffer = max_t(u64, ~0U, PSCHED_TICKS2NS(qopt->buffer));

Could we keep this code understandable, please ?

Hmm, I cannot figure out why max_t, did you mean min_t?

Quoted 5 lines
#10 lore raw

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

Quoted 1 line · Yang Yingliang

Hmm, I cannot figure out why max_t, did you mean min_t?

probably !

#11 lore raw

RE: [PATCH net v6 1/2] net: sched: tbf: fix the calculation of max_size

In reply to Yang Yingliang
Quoted 44 lines

From: Yang Yingliang [mailto:[email protected]]

Quoted 17 lines · David Laight
Quoted 17 lines

From: Yang Yingliang

Quoted 12 lines · David Laight
Quoted 1 line

From: Yang Yingliang

...

You are multiplying two values then dividing by 10**9 I'd guess that the intermediate value might exceed 2**64.

net/sched/sch_tbf.c struct tbf_sched_data { · line 135

Quoted 2 lines
net/sched/sch_tbf.c +2 -0
+	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
+		len = (len / 53) * 48;

You probably want to do the multiply first.
But why not scale rate_bytes_ps instead.

When the linklayer is ATM, the formula to calculate tokens is:

Quoted 8 lines
Quoted 3 lines

((u64)(DIV_ROUND_UP(len,48)*53) * r->mult) >> r->shift

So, I scale len here.

Seems to me that there are a lot of unnecessary multiplies and divides going on here.
Looks to me like the code was originally written to require one multiply and one shift for each packet.

The way to calc tokens in psched_l2t_ns() means:
we got a payload which length is 'len'. To get the actual size we need send, round len up to a multiple of 53. After getting the size, we do multiply and shift to calculate tokens that we need.

Quoted 7 lines

In any case the latter code is allowing for more of the ATM cell overhead. I'm not at all sure the intent is to remove that when setting up the constants.

OTOH should this code be worrying about the packet overheads at all? Does it add in the ethernet pre-emable, CRC and inter packet gap?

This overhead is sent from userspace by tc.

Quoted 1 line
Quoted 6 lines
Quoted 2 lines

I'd guess that the most the ATM code should do it round the length up to a multiple of 48 (user payload in a cell).

53 is ATM cell size include header, sending a header needs tokens as well. I'd guess round the length up to a multiple of 53 in psched_l2t_ns() is necessary.

The point I'm trying to make is that in one place you multiply by 53/48 and in the other you multiply be 48/53.
These two operations almost certainly cancel each other out. Or would modulo small rounding errors if you did the multiplies first. So why do either of them?

Whether you should be rounding up ATM data to a whole number of cells is a different question entirely.

David

#12 lore raw

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

Quoted 51 lines · David Laight
Quoted 44 lines

From: Yang Yingliang [mailto:[email protected]]

Quoted 17 lines · David Laight
Quoted 17 lines

From: Yang Yingliang

Quoted 12 lines · David Laight
Quoted 1 line

From: Yang Yingliang

...

You are multiplying two values then dividing by 10**9 I'd guess that the intermediate value might exceed 2**64.

net/sched/sch_tbf.c struct tbf_sched_data { · line 135

Quoted 2 lines
net/sched/sch_tbf.c +2 -0
+	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
+		len = (len / 53) * 48;

You probably want to do the multiply first.
But why not scale rate_bytes_ps instead.

When the linklayer is ATM, the formula to calculate tokens is:

Quoted 8 lines
Quoted 3 lines

((u64)(DIV_ROUND_UP(len,48)*53) * r->mult) >> r->shift

So, I scale len here.

Seems to me that there are a lot of unnecessary multiplies and divides going on here.
Looks to me like the code was originally written to require one multiply and one shift for each packet.

The way to calc tokens in psched_l2t_ns() means:
we got a payload which length is 'len'. To get the actual size we need send, round len up to a multiple of 53. After getting the size, we do multiply and shift to calculate tokens that we need.

Quoted 7 lines

In any case the latter code is allowing for more of the ATM cell overhead. I'm not at all sure the intent is to remove that when setting up the constants.

OTOH should this code be worrying about the packet overheads at all? Does it add in the ethernet pre-emable, CRC and inter packet gap?

This overhead is sent from userspace by tc.

Quoted 1 line
Quoted 6 lines
Quoted 2 lines

I'd guess that the most the ATM code should do it round the length up to a multiple of 48 (user payload in a cell).

53 is ATM cell size include header, sending a header needs tokens as well. I'd guess round the length up to a multiple of 53 in psched_l2t_ns() is necessary.

Quoted 5 lines

The point I'm trying to make is that in one place you multiply by 53/48 and in the other you multiply be 48/53.
These two operations almost certainly cancel each other out. Or would modulo small rounding errors if you did the multiplies first. So why do either of them?

Current kernel does multiplication by 53/48 to calculate tokens in psched_l2t_ns(). It expands a packet length. So I need reduce the length which is used as max_size in psched_ns_t2l(), or it will be too big to get enough tokens.

len = (len / 53) * 48;
Here I do division first, because the length to calculate tokens is 53bytes at least. If len < 53, means that no packet can pass, we should set len to 0.

Regards,
Yang

Quoted 11 lines

Whether you should be rounding up ATM data to a whole number of cells is a different question entirely.

David

.

#13 lore raw

PATCH v6 2/2 net: sched: htb: fix the 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 | 20 ++++++++++++--------
 1 file changed, 12 insertions(+), 8 deletions(-)
net/sched/sch_htb.c +12 -8
index 0e1e38b..717b210 100644
@@ -1477,11 +1477,22 @@ 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 = cl->rate.rate_bytes_ps;
+
+		do_div(quantum, 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 +1511,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