[PATCH] netem: fix rate extension and drop accounting

From: Eric Dumazet <edumazet@google.com>

commit 7bc0f28c7a0c (netem: rate extension) did wrong maths when packet
is enqueued while queue is not empty.

Result is unexpected cumulative delays

# tc qd add dev eth0 root est 1sec 4sec netem delay 200ms rate 100kbit
# ping -i 0.1 172.30.42.18
PING 172.30.42.18 (172.30.42.18) 56(84) bytes of data.
64 bytes from 172.30.42.18: icmp_req=1 ttl=64 time=208 ms
64 bytes from 172.30.42.18: icmp_req=2 ttl=64 time=424 ms
64 bytes from 172.30.42.18: icmp_req=3 ttl=64 time=838 ms
64 bytes from 172.30.42.18: icmp_req=4 ttl=64 time=1142 ms
64 bytes from 172.30.42.18: icmp_req=5 ttl=64 time=1335 ms
64 bytes from 172.30.42.18: icmp_req=6 ttl=64 time=1949 ms
64 bytes from 172.30.42.18: icmp_req=7 ttl=64 time=2450 ms
64 bytes from 172.30.42.18: icmp_req=8 ttl=64 time=2840 ms
64 bytes from 172.30.42.18: icmp_req=9 ttl=64 time=3121 ms
64 bytes from 172.30.42.18: icmp_req=10 ttl=64 time=3291 ms
64 bytes from 172.30.42.18: icmp_req=11 ttl=64 time=3784 ms

This patch also fixes a double drop accounting in case packet is dropped
in tfifo_enqueue()

Signed-off-by: Eric Dumazet <edumazet@google.com>
Cc: Yuchung Cheng <redacted>
Cc: Andreas Terzis <redacted>
Cc: Mark Gordon <redacted>
Cc: Hagen Paul Pfeifer <redacted>
---
 net/sched/sch_netem.c |   14 ++------------
 1 file changed, 2 insertions(+), 12 deletions(-)

diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index a2a95aa..e8b5ac3 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c

@@ -368,7 +368,6 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 	/* We don't fill cb now as skb_unshare() may invalidate it */
 	struct netem_skb_cb *cb;
 	struct sk_buff *skb2;
-	int ret;
 	int count = 1;
 
 	/* Random duplication */

@@ -443,14 +442,14 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 				 * calculate this time bonus and substract
 				 * from delay.
 				 */
-				delay -= now - netem_skb_cb(skb_peek(list))->time_to_send;
+				delay -= netem_skb_cb(skb_peek(list))->time_to_send - now;
 				now = netem_skb_cb(skb_peek_tail(list))->time_to_send;
 			}
 		}
 
 		cb->time_to_send = now + delay;
 		++q->counter;
-		ret = tfifo_enqueue(skb, sch);
+		return tfifo_enqueue(skb, sch);
 	} else {
 		/*
 		 * Do re-ordering by putting one out of N packets at the front

@@ -462,16 +461,7 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 		__skb_queue_head(&sch->q, skb);
 		sch->qstats.backlog += qdisc_pkt_len(skb);
 		sch->qstats.requeues++;
-		ret = NET_XMIT_SUCCESS;
-	}
-
-	if (ret != NET_XMIT_SUCCESS) {
-		if (net_xmit_drop_count(ret)) {
-			sch->qstats.drops++;
-			return ret;
-		}
 	}
-
 	return NET_XMIT_SUCCESS;
 }
 

On Tue, 2012-07-03 at 11:25 +0200, Eric Dumazet wrote:

From: Eric Dumazet <edumazet@google.com>

commit 7bc0f28c7a0c (netem: rate extension) did wrong maths when packet
is enqueued while queue is not empty.

Result is unexpected cumulative delays

# tc qd add dev eth0 root est 1sec 4sec netem delay 200ms rate 100kbit
# ping -i 0.1 172.30.42.18
PING 172.30.42.18 (172.30.42.18) 56(84) bytes of data.
64 bytes from 172.30.42.18: icmp_req=1 ttl=64 time=208 ms
64 bytes from 172.30.42.18: icmp_req=2 ttl=64 time=424 ms
64 bytes from 172.30.42.18: icmp_req=3 ttl=64 time=838 ms
64 bytes from 172.30.42.18: icmp_req=4 ttl=64 time=1142 ms
64 bytes from 172.30.42.18: icmp_req=5 ttl=64 time=1335 ms
64 bytes from 172.30.42.18: icmp_req=6 ttl=64 time=1949 ms
64 bytes from 172.30.42.18: icmp_req=7 ttl=64 time=2450 ms
64 bytes from 172.30.42.18: icmp_req=8 ttl=64 time=2840 ms
64 bytes from 172.30.42.18: icmp_req=9 ttl=64 time=3121 ms
64 bytes from 172.30.42.18: icmp_req=10 ttl=64 time=3291 ms
64 bytes from 172.30.42.18: icmp_req=11 ttl=64 time=3784 ms

This patch also fixes a double drop accounting in case packet is dropped
in tfifo_enqueue()

Signed-off-by: Eric Dumazet <edumazet@google.com>
Cc: Yuchung Cheng <redacted>
Cc: Andreas Terzis <redacted>
Cc: Mark Gordon <redacted>
Cc: Hagen Paul Pfeifer <redacted>
---

Hmm, I'll send a v2

* Eric Dumazet | 2012-07-03 11:54:17 [+0200]:

quoted

commit 7bc0f28c7a0c (netem: rate extension) did wrong maths when packet
is enqueued while queue is not empty.

Result is unexpected cumulative delays

# tc qd add dev eth0 root est 1sec 4sec netem delay 200ms rate 100kbit
# ping -i 0.1 172.30.42.18
PING 172.30.42.18 (172.30.42.18) 56(84) bytes of data.
64 bytes from 172.30.42.18: icmp_req=1 ttl=64 time=208 ms
64 bytes from 172.30.42.18: icmp_req=2 ttl=64 time=424 ms
64 bytes from 172.30.42.18: icmp_req=3 ttl=64 time=838 ms
64 bytes from 172.30.42.18: icmp_req=4 ttl=64 time=1142 ms
64 bytes from 172.30.42.18: icmp_req=5 ttl=64 time=1335 ms
64 bytes from 172.30.42.18: icmp_req=6 ttl=64 time=1949 ms
64 bytes from 172.30.42.18: icmp_req=7 ttl=64 time=2450 ms
64 bytes from 172.30.42.18: icmp_req=8 ttl=64 time=2840 ms
64 bytes from 172.30.42.18: icmp_req=9 ttl=64 time=3121 ms
64 bytes from 172.30.42.18: icmp_req=10 ttl=64 time=3291 ms
64 bytes from 172.30.42.18: icmp_req=11 ttl=64 time=3784 ms

Strange, we test the patch in detail. I will take a look ...

On Wed, 2012-07-04 at 00:04 +0200, Hagen Paul Pfeifer wrote:

Strange, we test the patch in detail. I will take a look ...

I tried to fix the thing but lacked time yesterday.


I had to use the good old way for my tests.


DEV=eth0
tc qdisc del dev $DEV root
tc qdisc add dev $DEV root handle 30: est 1sec 4sec netem \
        delay 100ms 10ms reorder 3
tc qdisc add dev $DEV handle 40:0 parent 30:0 tbf \
        burst 5000 limit 10000 mtu 1514 rate 100kbit
tc qdisc add dev $DEV handle 50:00 parent 40:0 pfifo limit 200

fundamentally, mixing the TBF is going to be hard with "delay ..."
especially with jitter.

Same problem for reorder : since packets are put at head of queue,
they have no effect on the 'time_to_send' of packets already in queue
and netem use more bandwidth than allowed.

I'll send the patch on the double drop accounting problem because the
fix is easy enough, but fir the rate limiting, I prefer letting you work
on it if you dont mind ?

Thanks

* Eric Dumazet | 2012-07-04 07:58:08 [+0200]:

DEV=eth0
tc qdisc del dev $DEV root
tc qdisc add dev $DEV root handle 30: est 1sec 4sec netem \
       delay 100ms 10ms reorder 3
tc qdisc add dev $DEV handle 40:0 parent 30:0 tbf \
       burst 5000 limit 10000 mtu 1514 rate 100kbit
tc qdisc add dev $DEV handle 50:00 parent 40:0 pfifo limit 200

fundamentally, mixing the TBF is going to be hard with "delay ..."
especially with jitter.

Same problem for reorder : since packets are put at head of queue,
they have no effect on the 'time_to_send' of packets already in queue
and netem use more bandwidth than allowed.

I'll send the patch on the double drop accounting problem because the
fix is easy enough, but fir the rate limiting, I prefer letting you work
on it if you dont mind ?

OK, I will work on it tomorrow! But Eric, keep in mind that this accumulative
behavior is intended: think about a hypothetical satellite link with a
bandwidth (rate) of 1000 byte/s. If you send three 1000 byte consecutively
packets. The first packet is delayed for 1 second, the second then is
transmitted after 2 seconds, the third after three seconds and so on. So
_this_ accumulative behavior is correct. Anyway, I will look at this tomorrow!

Thanks Eric!

PS: one last question: what do you want to test? TBF and netem rate at the
same time looks, mmhh, special ... ;-) I ask myself what link exhibit this
characteristic?

On Wed, 2012-07-04 at 18:51 +0200, Hagen Paul Pfeifer wrote:

OK, I will work on it tomorrow! But Eric, keep in mind that this accumulative
behavior is intended: think about a hypothetical satellite link with a
bandwidth (rate) of 1000 byte/s. If you send three 1000 byte consecutively
packets. The first packet is delayed for 1 second, the second then is
transmitted after 2 seconds, the third after three seconds and so on. So
_this_ accumulative behavior is correct. Anyway, I will look at this tomorrow!

I fear you did your tests with no delay on netem.

Try to setup a rate of 100kbit and a delay of 100ms and to really get
full bandwith (100kbit), I am afraid it doesnt work.

Your algo is OK only if no packets are in queue (obviously)

But if you have 2 or 3 packets, the delay are cumulative,
but the delay should be a fixed bias for each packet.

Thanks Eric!

PS: one last question: what do you want to test? TBF and netem rate at the
same time looks, mmhh, special ... ;-) I ask myself what link exhibit this
characteristic?

TBF as a netem child was the usual way to have delay + rate before your
patch ?

Not sure why you find it special ?

* Eric Dumazet | 2012-07-04 19:23:21 [+0200]:

I fear you did your tests with no delay on netem.

Try to setup a rate of 100kbit and a delay of 100ms and to really get
full bandwith (100kbit), I am afraid it doesnt work.

Your algo is OK only if no packets are in queue (obviously)

But if you have 2 or 3 packets, the delay are cumulative,
but the delay should be a fixed bias for each packet.

Right, we did not test it with delay because we emulated satelite links.
Static delay was negligible. All delay was caused by a limited rate. ok, I
will look at this!