cbq: incorrectly low bandwidth blocks limited traffic

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

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

To compensate this boost we did not changed q->now until it will be synchronized with real time. Unfortunately it does not work in described
scenario: boost accumulated by non-limited traffic blocks processing of limited traffic.

Below you can found an example of this problem.

To fix the problem I propose the following path set:

Vasily Averin (2):
cbq: incorrectly low bandwidth setting blocks limited traffic
cbq: now_rt removal

 net/sched/sch_cbq.c |   48 ++++++++++++++----------------------------------
 1 files changed, 14 insertions(+), 34 deletions(-)

First patch prevents incorrect updates q->now in cbq_dequeue(), now it just saves real time on each function call.
q_now change required for cbg_update() was compensated inside this function.

Second patch removes q->now_rt because now it is identical to q->now.

My testing confirms that these patches fixes the problem, and do not affect

Thank you,
Vasily Averin

Node gigabit link, 100Mbit bandwidth in cbq, and 70 Mbit limit for some traffic

# tc qdisc del dev eth0 root
# tc qdisc add dev eth0 root handle 1: cbq avpkt 64kb bandwidth 100Mbit
# tc class add dev eth0 parent 1: classid 1:1 cbq rate 70Mbit bounded allot 64kb
# tc filter add dev eth0 parent 1: protocol ip u32 match ip dst 10.30.3.116 flowid 1:1 

Initially shaper works correctly

# netperf -H 10.30.3.116 -l5
MIGRATED TCP STREAM TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to 10.30.3.116 () port 0 AF_INET
Recv   Send    Send
Socket Socket  Message  Elapsed
Size   Size    Size     Time     Throughput
bytes  bytes   bytes    secs.    10^6bits/sec

87380 16384 16384 5.08 66.31

... then node generates some non-limited traffic...

# netperf -H ANOTHER_IP -l5
MIGRATED TCP STREAM TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to ANOTHER_IP () port 0 AF_INET
Recv   Send    Send
Socket Socket  Message  Elapsed
Size   Size    Size     Time     Throughput
bytes  bytes   bytes    secs.    10^6bits/sec

87380 16384 16384 5.02 818.12

... and it blocks limited traffic

# netperf -H 10.30.3.116 -l5
MIGRATED TCP STREAM TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to 10.30.3.116 () port 0 AF_INET
Recv   Send    Send
Socket Socket  Message  Elapsed
Size   Size    Size     Time     Throughput
bytes  bytes   bytes    secs.    10^6bits/sec

87380 16384 16384 9.00 0.10

Ping on neighbor console shows that traffic is not dropped but delayed

64 bytes from 10.30.3.116: icmp_seq=17 ttl=64 time=0.131 ms 64 bytes from 10.30.3.116: icmp_seq=18 ttl=64 time=0.161 ms
ping: sendmsg: No buffer space available
ping: sendmsg: No buffer space available
ping: sendmsg: No buffer space available
ping: sendmsg: No buffer space available
ping: sendmsg: No buffer space available
ping: sendmsg: No buffer space available
ping: sendmsg: No buffer space available
64 bytes from 10.30.3.116: icmp_seq=19 ttl=64 time=37568 ms 64 bytes from 10.30.3.116: icmp_seq=20 ttl=64 time=36568 ms 64 bytes from 10.30.3.116: icmp_seq=21 ttl=64 time=35568 ms 64 bytes from 10.30.3.116: icmp_seq=22 ttl=64 time=34568 ms 64 bytes from 10.30.3.116: icmp_seq=23 ttl=64 time=33568 ms 64 bytes from 10.30.3.116: icmp_seq=24 ttl=64 time=32568 ms 64 bytes from 10.30.3.116: icmp_seq=25 ttl=64 time=31569 ms 64 bytes from 10.30.3.116: icmp_seq=26 ttl=64 time=30569 ms 64 bytes from 10.30.3.116: icmp_seq=27 ttl=64 time=29569 ms 64 bytes from 10.30.3.116: icmp_seq=28 ttl=64 time=28569 ms 64 bytes from 10.30.3.116: icmp_seq=29 ttl=64 time=27570 ms 64 bytes from 10.30.3.116: icmp_seq=30 ttl=64 time=26570 ms 64 bytes from 10.30.3.116: icmp_seq=38 ttl=64 time=0.187 ms

tc -s -d class ls dev eth0 output taken while limited traffic was blocked is attached.

Wed Aug 13 15:29:20 MSD 2014
class cbq 1: root rate 100000Kbit cell 512b (bounded,isolated) prio no-transmit/8 weight 100000Kbit allot 1514b level 1 ewma 5 avpkt 65536b maxidle 163us
Sent 537611083 bytes 8058 pkt (dropped 0, overlimits 0 requeues 0)
backlog 0b 0p requeues 0
borrowed 0 overactions 0 avgidle 46245 undertime 0
class cbq 1:1 parent 1: rate 70000Kbit cell 512b (bounded) prio no-transmit/8 allot 65536b level 0 ewma 5 avpkt 65536b maxidle 163us
Sent 121396 bytes 23 pkt (dropped 0, overlimits 10147 requeues 0)
backlog 0b 6p requeues 0
borrowed 0 overactions 1 avgidle -2031 undertime 3875
Wed Aug 13 15:29:22 MSD 2014
class cbq 1: root rate 100000Kbit cell 512b (bounded,isolated) prio no-transmit/8 weight 100000Kbit allot 1514b level 1 ewma 5 avpkt 65536b maxidle 163us
Sent 537611489 bytes 8061 pkt (dropped 0, overlimits 0 requeues 0)
backlog 0b 0p requeues 0
borrowed 0 overactions 0 avgidle 42044 undertime 0
class cbq 1:1 parent 1: rate 70000Kbit cell 512b (bounded) prio no-transmit/8 allot 65536b level 0 ewma 5 avpkt 65536b maxidle 163us
Sent 121396 bytes 23 pkt (dropped 0, overlimits 21711 requeues 0)
backlog 0b 7p requeues 0
borrowed 0 overactions 1 avgidle -2031 undertime 2000
Wed Aug 13 15:29:24 MSD 2014
class cbq 1: root rate 100000Kbit cell 512b (bounded,isolated) prio no-transmit/8 weight 100000Kbit allot 1514b level 1 ewma 5 avpkt 65536b maxidle 163us
Sent 537611895 bytes 8064 pkt (dropped 0, overlimits 0 requeues 0)
backlog 0b 0p requeues 0
borrowed 0 overactions 0 avgidle 38226 undertime 0
class cbq 1:1 parent 1: rate 70000Kbit cell 512b (bounded) prio no-transmit/8 allot 65536b level 0 ewma 5 avpkt 65536b maxidle 163us
Sent 121396 bytes 23 pkt (dropped 0, overlimits 49964 requeues 0)
backlog 0b 7p requeues 0
borrowed 0 overactions 1 avgidle -2031 undertime 125
Wed Aug 13 15:29:26 MSD 2014
class cbq 1: root rate 100000Kbit cell 512b (bounded,isolated) prio no-transmit/8 weight 100000Kbit allot 1514b level 1 ewma 5 avpkt 65536b maxidle 163us
Sent 537624487 bytes 8070 pkt (dropped 0, overlimits 0 requeues 0)
backlog 0b 0p requeues 0
borrowed 0 overactions 0 avgidle 31597 undertime 0
class cbq 1:1 parent 1: rate 70000Kbit cell 512b (bounded) prio no-transmit/8 allot 65536b level 0 ewma 5 avpkt 65536b maxidle 163us
Sent 133508 bytes 25 pkt (dropped 0, overlimits 55966 requeues 0)
backlog 0b 7p requeues 0
borrowed 0 overactions 2 avgidle -2402 undertime 3875
Wed Aug 13 15:29:29 MSD 2014
class cbq 1: root rate 100000Kbit cell 512b (bounded,isolated) prio no-transmit/8 weight 100000Kbit allot 1514b level 1 ewma 5 avpkt 65536b maxidle 163us
Sent 537637360 bytes 8079 pkt (dropped 0, overlimits 0 requeues 0)
backlog 0b 0p requeues 0
borrowed 0 overactions 0 avgidle 23748 undertime 0
class cbq 1:1 parent 1: rate 70000Kbit cell 512b (bounded) prio no-transmit/8 allot 65536b level 0 ewma 5 avpkt 65536b maxidle 163us
Sent 145620 bytes 26 pkt (dropped 0, overlimits 153256 requeues 0)
backlog 0b 6p requeues 0
borrowed 0 overactions 3 avgidle -2654 undertime 5953
Wed Aug 13 15:29:33 MSD 2014
class cbq 1: root rate 100000Kbit cell 512b (bounded,isolated) prio no-transmit/8 weight 100000Kbit allot 1514b level 1 ewma 5 avpkt 65536b maxidle 163us
Sent 537637882 bytes 8084 pkt (dropped 0, overlimits 0 requeues 0)
backlog 0b 0p requeues 0
borrowed 0 overactions 0 avgidle 20265 undertime 0
class cbq 1:1 parent 1: rate 70000Kbit cell 512b (bounded) prio no-transmit/8 allot 65536b level 0 ewma 5 avpkt 65536b maxidle 163us
Sent 145620 bytes 26 pkt (dropped 0, overlimits 167079 requeues 0)
backlog 0b 7p requeues 0
borrowed 0 overactions 3 avgidle -2654 undertime 2828
Wed Aug 13 15:29:37 MSD 2014
class cbq 1: root rate 100000Kbit cell 512b (bounded,isolated) prio no-transmit/8 weight 100000Kbit allot 1514b level 1 ewma 5 avpkt 65536b maxidle 163us
Sent 537646469 bytes 8093 pkt (dropped 0, overlimits 0 requeues 0)
backlog 0b 0p requeues 0
borrowed 0 overactions 0 avgidle 15232 undertime 0
class cbq 1:1 parent 1: rate 70000Kbit cell 512b (bounded) prio no-transmit/8 allot 65536b level 0 ewma 5 avpkt 65536b maxidle 163us
Sent 153256 bytes 28 pkt (dropped 0, overlimits 203055 requeues 0)
backlog 0b 7p requeues 0
borrowed 0 overactions 4 avgidle -212 undertime 2860