inaccurate packet scheduling

inaccurate packet scheduling

[Jiri Pirko]

Hi all.

Run one of the following 2 scripts on machine A:

#!/bin/bash
tc qdisc del dev eth0 root
sleep 1
tc -batch << EOF
qdisc add dev eth0 root handle 1: prio bands 2 priomap 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
qdisc add dev eth0 parent 1:1 handle 10: pfifo limit 50
qdisc add dev eth0 parent 1:2 handle 20 tbf latency 100ms rate 4mbit burst 2m
filter add dev eth0 parent 1: protocol ip u32 match ip dst $machineB_ip flowid 1:2
EOF

#!/bin/bash
tc qdisc del dev eth0 root
sleep 1
tc -batch << EOF
qdisc add dev eth0 root handle 1: prio bands 2 priomap 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
qdisc add dev eth0 parent 1:1 handle 10: pfifo limit 20
qdisc add dev eth0 parent 1:2 handle 20: pfifo limit 20
filter add dev eth0 parent 1: protocol ip pref 10 \
u32 match ip dst $machineB_ip \
flowid 1:2 \
police rate 4Mbit burst 2m conform-exceed drop
EOF

And run:
[machineB ~]# iperf -s
[machineA ~]# iperf -c machineB_ip -t 60

Expected results are: ~3.8-4.2 Mbits/s
But actual results are: ~130-170 Kbits/s with tbf, ~70-300 Kbits/s with policy rate

[machineA ~]# tc -s qdisc list dev eth0
qdisc prio 1: root refcnt 9 bands 2 priomap  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 Sent 1512384 bytes 1032 pkt (dropped 729, overlimits 0 requeues 0) 
 backlog 0b 0p requeues 0 
qdisc pfifo 10: parent 1:1 limit 50p
 Sent 4560 bytes 32 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 0p requeues 0 
qdisc tbf 20: parent 1:2 rate 4000Kbit burst 2Mb lat 100.0ms 
 Sent 1507824 bytes 1000 pkt (dropped 729, overlimits 0 requeues 0) 
 backlog 0b 0p requeues 0 


Tested with kernel pulled from linus's git today. This happens with older
kernels as well (I tried 2.6.32-based rhel6 kernels).

This happens to me on following machines:
HP DL360G8 (x86_64) http://people.redhat.com/jpirko/aThoo2Ei/dl380g8/
HP DL360G3 (i686) 
IBM JS22 (ppc64) http://people.redhat.com/jpirko/aThoo2Ei/ibmjs22/

On following machines, I do not observe this issue:
qemu kvm (x86_64)
IBM Zseries (s390x) http://people.redhat.com/jpirko/aThoo2Ei/ibmz/

Please ask in case you need me to provide any other details.

Thanks.

Jiri

Re: inaccurate packet scheduling

[Stephen Hemminger]

----- Original Message -----
> Hi all.
> 
> Run one of the following 2 scripts on machine A:
> 
> #!/bin/bash
> tc qdisc del dev eth0 root
> sleep 1
> tc -batch << EOF
> qdisc add dev eth0 root handle 1: prio bands 2 priomap 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> qdisc add dev eth0 parent 1:1 handle 10: pfifo limit 50
> qdisc add dev eth0 parent 1:2 handle 20 tbf latency 100ms rate 4mbit
> burst 2m
> filter add dev eth0 parent 1: protocol ip u32 match ip dst
> $machineB_ip flowid 1:2
> EOF
> 
> #!/bin/bash
> tc qdisc del dev eth0 root
> sleep 1
> tc -batch << EOF
> qdisc add dev eth0 root handle 1: prio bands 2 priomap 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> qdisc add dev eth0 parent 1:1 handle 10: pfifo limit 20
> qdisc add dev eth0 parent 1:2 handle 20: pfifo limit 20
> filter add dev eth0 parent 1: protocol ip pref 10 \
> u32 match ip dst $machineB_ip \
> flowid 1:2 \
> police rate 4Mbit burst 2m conform-exceed drop
> EOF
> 
> And run:
> [machineB ~]# iperf -s
> [machineA ~]# iperf -c machineB_ip -t 60
> 
> Expected results are: ~3.8-4.2 Mbits/s
> But actual results are: ~130-170 Kbits/s with tbf, ~70-300 Kbits/s
> with policy rate
> 
> [machineA ~]# tc -s qdisc list dev eth0
> qdisc prio 1: root refcnt 9 bands 2 priomap  0 0 0 0 0 0 0 0 0 0 0 0
> 0 0 0 0
>  Sent 1512384 bytes 1032 pkt (dropped 729, overlimits 0 requeues 0)
>  backlog 0b 0p requeues 0
> qdisc pfifo 10: parent 1:1 limit 50p
>  Sent 4560 bytes 32 pkt (dropped 0, overlimits 0 requeues 0)
>  backlog 0b 0p requeues 0
> qdisc tbf 20: parent 1:2 rate 4000Kbit burst 2Mb lat 100.0ms
>  Sent 1507824 bytes 1000 pkt (dropped 729, overlimits 0 requeues 0)
>  backlog 0b 0p requeues 0
> 
> 
> Tested with kernel pulled from linus's git today. This happens with
> older
> kernels as well (I tried 2.6.32-based rhel6 kernels).
> 
> This happens to me on following machines:
> HP DL360G8 (x86_64) http://people.redhat.com/jpirko/aThoo2Ei/dl380g8/
> HP DL360G3 (i686)
> IBM JS22 (ppc64) http://people.redhat.com/jpirko/aThoo2Ei/ibmjs22/
> 
> On following machines, I do not observe this issue:
> qemu kvm (x86_64)
> IBM Zseries (s390x) http://people.redhat.com/jpirko/aThoo2Ei/ibmz/
> 
> Please ask in case you need me to provide any other details.
> 
> Thanks.

Check kernel log for messages about clock. It could be that on the
machines with issues TSC is not usable for kernel clock.
Also turn off TSO since it screws up any form of rate control.

Re: inaccurate packet scheduling

[Eric Dumazet]

On Tue, 2012-12-18 at 08:26 -0800, Stephen Hemminger wrote:

> Check kernel log for messages about clock. It could be that on the
> machines with issues TSC is not usable for kernel clock.
> Also turn off TSO since it screws up any form of rate control.

Yes, but we should fix it eventually. I'll take a look.

Re: inaccurate packet scheduling

[Jiri Pirko]

Tue, Dec 18, 2012 at 05:51:43PM CET, erdnetdev@gmail.com wrote:
>On Tue, 2012-12-18 at 08:26 -0800, Stephen Hemminger wrote:
>
>> Check kernel log for messages about clock. It could be that on the
>> machines with issues TSC is not usable for kernel clock.
>> Also turn off TSO since it screws up any form of rate control.
>
>Yes, but we should fix it eventually. I'll take a look.

Hi Eric, did you have a chance to look at this? Or should I give it a try?

Thanks a lot.

Jiri

>
>
>

Re: inaccurate packet scheduling

[Eric Dumazet]

On Wed, 2013-01-02 at 16:26 +0100, Jiri Pirko wrote:
> Tue, Dec 18, 2012 at 05:51:43PM CET, erdnetdev@gmail.com wrote:
> >On Tue, 2012-12-18 at 08:26 -0800, Stephen Hemminger wrote:
> >
> >> Check kernel log for messages about clock. It could be that on the
> >> machines with issues TSC is not usable for kernel clock.
> >> Also turn off TSO since it screws up any form of rate control.
> >
> >Yes, but we should fix it eventually. I'll take a look.
> 
> Hi Eric, did you have a chance to look at this? Or should I give it a try?

I took a look, and TBF does :

if (qdisc_pkt_len(skb) > q->max_size)
    return qdisc_reshape_fail(skb, sch);

We have several choices :

1) Add a one time warning

2) cap dev->gso_max_size at Qdisc setup time

3) Re-segment the packet instead of dropping it (if GSO packet), and
call the expensive qdisc_tree_decrease_qlen() function.

4) remove max_size limitation 

Re: inaccurate packet scheduling

[Jiri Pirko]

Wed, Jan 02, 2013 at 05:34:42PM CET, eric.dumazet@gmail.com wrote:
>On Wed, 2013-01-02 at 16:26 +0100, Jiri Pirko wrote:
>> Tue, Dec 18, 2012 at 05:51:43PM CET, erdnetdev@gmail.com wrote:
>> >On Tue, 2012-12-18 at 08:26 -0800, Stephen Hemminger wrote:
>> >
>> >> Check kernel log for messages about clock. It could be that on the
>> >> machines with issues TSC is not usable for kernel clock.
>> >> Also turn off TSO since it screws up any form of rate control.
>> >
>> >Yes, but we should fix it eventually. I'll take a look.
>> 
>> Hi Eric, did you have a chance to look at this? Or should I give it a try?
>
>I took a look, and TBF does :
>
>if (qdisc_pkt_len(skb) > q->max_size)
>    return qdisc_reshape_fail(skb, sch);
>
>We have several choices :
>
>1) Add a one time warning
>
>2) cap dev->gso_max_size at Qdisc setup time
>
>3) Re-segment the packet instead of dropping it (if GSO packet), and
>call the expensive qdisc_tree_decrease_qlen() function.
>
>4) remove max_size limitation 
>

To my untrained eye, 2) or 4) look like a way to go. Not sure though.

Re: inaccurate packet scheduling

[Jiri Pirko]

Tue, Jan 08, 2013 at 02:30:38PM CET, jiri@resnulli.us wrote:
>Wed, Jan 02, 2013 at 05:34:42PM CET, eric.dumazet@gmail.com wrote:
>>On Wed, 2013-01-02 at 16:26 +0100, Jiri Pirko wrote:
>>> Tue, Dec 18, 2012 at 05:51:43PM CET, erdnetdev@gmail.com wrote:
>>> >On Tue, 2012-12-18 at 08:26 -0800, Stephen Hemminger wrote:
>>> >
>>> >> Check kernel log for messages about clock. It could be that on the
>>> >> machines with issues TSC is not usable for kernel clock.
>>> >> Also turn off TSO since it screws up any form of rate control.
>>> >
>>> >Yes, but we should fix it eventually. I'll take a look.
>>> 
>>> Hi Eric, did you have a chance to look at this? Or should I give it a try?
>>
>>I took a look, and TBF does :
>>
>>if (qdisc_pkt_len(skb) > q->max_size)
>>    return qdisc_reshape_fail(skb, sch);
>>
>>We have several choices :
>>
>>1) Add a one time warning
>>
>>2) cap dev->gso_max_size at Qdisc setup time
>>
>>3) Re-segment the packet instead of dropping it (if GSO packet), and
>>call the expensive qdisc_tree_decrease_qlen() function.
>>
>>4) remove max_size limitation 
>>
>
>To my untrained eye, 2) or 4) look like a way to go. Not sure though.

What do you think would be the best way Eric? Thanks.

Re: inaccurate packet scheduling

[Eric Dumazet]

On Thu, 2013-01-24 at 09:05 +0100, Jiri Pirko wrote:
> Tue, Jan 08, 2013 at 02:30:38PM CET, jiri@resnulli.us wrote:
> >Wed, Jan 02, 2013 at 05:34:42PM CET, eric.dumazet@gmail.com wrote:
> >>On Wed, 2013-01-02 at 16:26 +0100, Jiri Pirko wrote:
> >>> Tue, Dec 18, 2012 at 05:51:43PM CET, erdnetdev@gmail.com wrote:
> >>> >On Tue, 2012-12-18 at 08:26 -0800, Stephen Hemminger wrote:
> >>> >
> >>> >> Check kernel log for messages about clock. It could be that on the
> >>> >> machines with issues TSC is not usable for kernel clock.
> >>> >> Also turn off TSO since it screws up any form of rate control.
> >>> >
> >>> >Yes, but we should fix it eventually. I'll take a look.
> >>> 
> >>> Hi Eric, did you have a chance to look at this? Or should I give it a try?
> >>
> >>I took a look, and TBF does :
> >>
> >>if (qdisc_pkt_len(skb) > q->max_size)
> >>    return qdisc_reshape_fail(skb, sch);
> >>
> >>We have several choices :
> >>
> >>1) Add a one time warning
> >>
> >>2) cap dev->gso_max_size at Qdisc setup time
> >>
> >>3) Re-segment the packet instead of dropping it (if GSO packet), and
> >>call the expensive qdisc_tree_decrease_qlen() function.
> >>
> >>4) remove max_size limitation 
> >>
> >
> >To my untrained eye, 2) or 4) look like a way to go. Not sure though.
> 
> What do you think would be the best way Eric? Thanks.

Capping gso_max_size is a bit difficult after commit
1def9238d4aa2146924 (net_sched: more precise pkt_len computation)

If MSS is really small, we can easily get a lot of overhead

qdisc_skb_cb(skb)->pkt_len > 2 * skb->len

It looks like we need 4), maybe using same mechanism
than the one used in commit 56b765b79e9a78d
(htb: improved accuracy at high rates)

Re: inaccurate packet scheduling

[Jiri Pirko]

Thu, Jan 24, 2013 at 03:01:27PM CET, eric.dumazet@gmail.com wrote:
>On Thu, 2013-01-24 at 09:05 +0100, Jiri Pirko wrote:
>> Tue, Jan 08, 2013 at 02:30:38PM CET, jiri@resnulli.us wrote:
>> >Wed, Jan 02, 2013 at 05:34:42PM CET, eric.dumazet@gmail.com wrote:
>> >>On Wed, 2013-01-02 at 16:26 +0100, Jiri Pirko wrote:
>> >>> Tue, Dec 18, 2012 at 05:51:43PM CET, erdnetdev@gmail.com wrote:
>> >>> >On Tue, 2012-12-18 at 08:26 -0800, Stephen Hemminger wrote:
>> >>> >
>> >>> >> Check kernel log for messages about clock. It could be that on the
>> >>> >> machines with issues TSC is not usable for kernel clock.
>> >>> >> Also turn off TSO since it screws up any form of rate control.
>> >>> >
>> >>> >Yes, but we should fix it eventually. I'll take a look.
>> >>> 
>> >>> Hi Eric, did you have a chance to look at this? Or should I give it a try?
>> >>
>> >>I took a look, and TBF does :
>> >>
>> >>if (qdisc_pkt_len(skb) > q->max_size)
>> >>    return qdisc_reshape_fail(skb, sch);
>> >>
>> >>We have several choices :
>> >>
>> >>1) Add a one time warning
>> >>
>> >>2) cap dev->gso_max_size at Qdisc setup time
>> >>
>> >>3) Re-segment the packet instead of dropping it (if GSO packet), and
>> >>call the expensive qdisc_tree_decrease_qlen() function.
>> >>
>> >>4) remove max_size limitation 
>> >>
>> >
>> >To my untrained eye, 2) or 4) look like a way to go. Not sure though.
>> 
>> What do you think would be the best way Eric? Thanks.
>
>Capping gso_max_size is a bit difficult after commit
>1def9238d4aa2146924 (net_sched: more precise pkt_len computation)
>
>If MSS is really small, we can easily get a lot of overhead
>
>qdisc_skb_cb(skb)->pkt_len > 2 * skb->len
>
>It looks like we need 4), maybe using same mechanism
>than the one used in commit 56b765b79e9a78d
>(htb: improved accuracy at high rates)

part of the commit message says:
<quote>
The bits per second on the wire is still 5200Mb/s with new HTB
because qdisc accounts for packet length using skb->len, which
is smaller than total bytes on the wire if GSO is used.  But
that is for another patch regardless of how time is accounted.	
</quote>
I believe that is a similar problem like ours. But looks like this
"another patch" never got in.


>
>
>
>

Re: inaccurate packet scheduling

[Eric Dumazet]

On Tue, 2013-01-29 at 13:23 +0100, Jiri Pirko wrote:

> part of the commit message says:
> <quote>
> The bits per second on the wire is still 5200Mb/s with new HTB
> because qdisc accounts for packet length using skb->len, which
> is smaller than total bytes on the wire if GSO is used.  But
> that is for another patch regardless of how time is accounted.	
> </quote>
> I believe that is a similar problem like ours. But looks like this
> "another patch" never got in.
> 

Hmm, I thought I addressed this in 

commit 1def9238d4aa2146924994aa4b7dc861f03b9362
Author: Eric Dumazet <edumazet@google.com>
Date:   Thu Jan 10 12:36:42 2013 +0000

    net_sched: more precise pkt_len computation
    
    One long standing problem with TSO/GSO/GRO packets is that skb->len
    doesn't represent a precise amount of bytes on wire.
    
    Headers are only accounted for the first segment.
    For TCP, thats typically 66 bytes per 1448 bytes segment missing,
    an error of 4.5 % for normal MSS value.
    
    As consequences :
    
    1) TBF/CBQ/HTB/NETEM/... can send more bytes than the assigned limits.
    2) Device stats are slightly under estimated as well.
    
    Fix this by taking account of headers in qdisc_skb_cb(skb)->pkt_len
    computation.
    
    Packet schedulers should use qdisc pkt_len instead of skb->len for their
    bandwidth limitations, and TSO enabled devices drivers could use pkt_len
    if their statistics are not hardware assisted, and if they don't scratch
    skb->cb[] first word.
    
    Both egress and ingress paths work, thanks to commit fda55eca5a
    (net: introduce skb_transport_header_was_set()) : If GRO built
    a GSO packet, it also set the transport header for us.

Re: inaccurate packet scheduling

[Jiri Pirko]

Tue, Jan 29, 2013 at 05:13:03PM CET, eric.dumazet@gmail.com wrote:
>On Tue, 2013-01-29 at 13:23 +0100, Jiri Pirko wrote:
>
>> part of the commit message says:
>> <quote>
>> The bits per second on the wire is still 5200Mb/s with new HTB
>> because qdisc accounts for packet length using skb->len, which
>> is smaller than total bytes on the wire if GSO is used.  But
>> that is for another patch regardless of how time is accounted.	
>> </quote>
>> I believe that is a similar problem like ours. But looks like this
>> "another patch" never got in.
>> 
>
>Hmm, I thought I addressed this in 
>
>commit 1def9238d4aa2146924994aa4b7dc861f03b9362
>Author: Eric Dumazet <edumazet@google.com>
>Date:   Thu Jan 10 12:36:42 2013 +0000
>
>    net_sched: more precise pkt_len computation
>    
>    One long standing problem with TSO/GSO/GRO packets is that skb->len
>    doesn't represent a precise amount of bytes on wire.
>    
>    Headers are only accounted for the first segment.
>    For TCP, thats typically 66 bytes per 1448 bytes segment missing,
>    an error of 4.5 % for normal MSS value.
>    
>    As consequences :
>    
>    1) TBF/CBQ/HTB/NETEM/... can send more bytes than the assigned limits.
>    2) Device stats are slightly under estimated as well.
>    
>    Fix this by taking account of headers in qdisc_skb_cb(skb)->pkt_len
>    computation.
>    
>    Packet schedulers should use qdisc pkt_len instead of skb->len for their
>    bandwidth limitations, and TSO enabled devices drivers could use pkt_len
>    if their statistics are not hardware assisted, and if they don't scratch
>    skb->cb[] first word.
>    
>    Both egress and ingress paths work, thanks to commit fda55eca5a
>    (net: introduce skb_transport_header_was_set()) : If GRO built
>    a GSO packet, it also set the transport header for us.
>


I tried kernel with this patch in. I also ported
56b765b79e9a78dc7d3f8850ba5e5567205a3ecd to tbf. I'm getting always the
similar numbers with iperf. There must be something else needed :/

Thanks

Jiri

Re: inaccurate packet scheduling

[Jiri Pirko]

Wed, Jan 30, 2013 at 01:14:47PM CET, jiri@resnulli.us wrote:
>Tue, Jan 29, 2013 at 05:13:03PM CET, eric.dumazet@gmail.com wrote:
>>On Tue, 2013-01-29 at 13:23 +0100, Jiri Pirko wrote:
>>
>>> part of the commit message says:
>>> <quote>
>>> The bits per second on the wire is still 5200Mb/s with new HTB
>>> because qdisc accounts for packet length using skb->len, which
>>> is smaller than total bytes on the wire if GSO is used.  But
>>> that is for another patch regardless of how time is accounted.	
>>> </quote>
>>> I believe that is a similar problem like ours. But looks like this
>>> "another patch" never got in.
>>> 
>>
>>Hmm, I thought I addressed this in 
>>
>>commit 1def9238d4aa2146924994aa4b7dc861f03b9362
>>Author: Eric Dumazet <edumazet@google.com>
>>Date:   Thu Jan 10 12:36:42 2013 +0000
>>
>>    net_sched: more precise pkt_len computation
>>    
>>    One long standing problem with TSO/GSO/GRO packets is that skb->len
>>    doesn't represent a precise amount of bytes on wire.
>>    
>>    Headers are only accounted for the first segment.
>>    For TCP, thats typically 66 bytes per 1448 bytes segment missing,
>>    an error of 4.5 % for normal MSS value.
>>    
>>    As consequences :
>>    
>>    1) TBF/CBQ/HTB/NETEM/... can send more bytes than the assigned limits.
>>    2) Device stats are slightly under estimated as well.
>>    
>>    Fix this by taking account of headers in qdisc_skb_cb(skb)->pkt_len
>>    computation.
>>    
>>    Packet schedulers should use qdisc pkt_len instead of skb->len for their
>>    bandwidth limitations, and TSO enabled devices drivers could use pkt_len
>>    if their statistics are not hardware assisted, and if they don't scratch
>>    skb->cb[] first word.
>>    
>>    Both egress and ingress paths work, thanks to commit fda55eca5a
>>    (net: introduce skb_transport_header_was_set()) : If GRO built
>>    a GSO packet, it also set the transport header for us.
>>
>
>
>I tried kernel with this patch in. I also ported
>56b765b79e9a78dc7d3f8850ba5e5567205a3ecd to tbf. I'm getting always the
>similar numbers with iperf. There must be something else needed :/

Any other ideas?
							
>
>Thanks
>
>Jiri

Re: inaccurate packet scheduling

[Eric Dumazet]

On Thu, 2013-02-07 at 17:13 +0100, Jiri Pirko wrote:

> >I tried kernel with this patch in. I also ported
> >56b765b79e9a78dc7d3f8850ba5e5567205a3ecd to tbf. I'm getting always the
> >similar numbers with iperf. There must be something else needed :/
> 
> Any other ideas?

You didn't post any patch, how can I comment on them ?

Re: inaccurate packet scheduling

[Jiri Pirko]

Thu, Feb 07, 2013 at 05:39:35PM CET, eric.dumazet@gmail.com wrote:
>On Thu, 2013-02-07 at 17:13 +0100, Jiri Pirko wrote:
>
>> >I tried kernel with this patch in. I also ported
>> >56b765b79e9a78dc7d3f8850ba5e5567205a3ecd to tbf. I'm getting always the
>> >similar numbers with iperf. There must be something else needed :/
>> 
>> Any other ideas?
>
>You didn't post any patch, how can I comment on them ?

Okay, sorry, here it is. But as I said, it did not help.

Subject: [patch net-next RFC] tbf: improved accuracy at high rates

Current TBF uses rate table computed by the "tc" userspace program,
which has the following issue:

The rate table has 256 entries to map packet lengths to
token (time units).  With TSO sized packets, the 256 entry granularity
leads to loss/gain of rate, making the token bucket inaccurate.

Thus, instead of relying on rate table, this patch explicitly computes
the time and accounts for packet transmission times with nanosecond
granularity.

This is a followup to 56b765b79e9a78dc7d3f8850ba5e5567205a3ecd

Signed-off-by: Jiri Pirko <jiri@resnulli.us>
---
 net/sched/sch_tbf.c | 97 +++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 71 insertions(+), 26 deletions(-)

diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
index 4b056c15..fdec80b 100644
--- a/net/sched/sch_tbf.c
+++ b/net/sched/sch_tbf.c
@@ -97,25 +97,68 @@
 	changed the limit is not effective anymore.
 */
 
+struct tbf_rate_cfg {
+	u64 rate_bps;
+	u32 mult;
+	u32 shift;
+};
+
 struct tbf_sched_data {
 /* Parameters */
 	u32		limit;		/* Maximal length of backlog: bytes */
 	u32		buffer;		/* Token bucket depth/rate: MUST BE >= MTU/B */
 	u32		mtu;
 	u32		max_size;
-	struct qdisc_rate_table	*R_tab;
-	struct qdisc_rate_table	*P_tab;
+	struct tbf_rate_cfg rate;
+	struct tbf_rate_cfg peek;
+	bool peek_present;
 
 /* Variables */
-	long	tokens;			/* Current number of B tokens */
-	long	ptokens;		/* Current number of P tokens */
+	s64	tokens;			/* Current number of B tokens */
+	s64	ptokens;		/* Current number of P tokens */
 	psched_time_t	t_c;		/* Time check-point */
 	struct Qdisc	*qdisc;		/* Inner qdisc, default - bfifo queue */
 	struct qdisc_watchdog watchdog;	/* Watchdog timer */
 };
 
-#define L2T(q, L)   qdisc_l2t((q)->R_tab, L)
-#define L2T_P(q, L) qdisc_l2t((q)->P_tab, L)
+static u64 l2t_ns(struct tbf_rate_cfg *r, unsigned int len)
+{
+	return ((u64)len * r->mult) >> r->shift;
+}
+
+static void htb_precompute_ratedata(struct tbf_rate_cfg *r)
+{
+	u64 factor;
+	u64 mult;
+	int shift;
+
+	r->shift = 0;
+	r->mult = 1;
+	/*
+	 * Calibrate mult, shift so that token counting is accurate
+	 * for smallest packet size (64 bytes).  Token (time in ns) is
+	 * computed as (bytes * 8) * NSEC_PER_SEC / rate_bps.  It will
+	 * work as long as the smallest packet transfer time can be
+	 * accurately represented in nanosec.
+	 */
+	if (r->rate_bps > 0) {
+		/*
+		 * Higher shift gives better accuracy.  Find the largest
+		 * shift such that mult fits in 32 bits.
+		 */
+		for (shift = 0; shift < 16; shift++) {
+			r->shift = shift;
+			factor = 8LLU * NSEC_PER_SEC * (1 << r->shift);
+			mult = div64_u64(factor, r->rate_bps);
+			if (mult > UINT_MAX)
+				break;
+		}
+
+		r->shift = shift - 1;
+		factor = 8LLU * NSEC_PER_SEC * (1 << r->shift);
+		r->mult = div64_u64(factor, r->rate_bps);
+	}
+}
 
 static int tbf_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 {
@@ -157,23 +200,23 @@ static struct sk_buff *tbf_dequeue(struct Qdisc *sch)
 
 	if (skb) {
 		psched_time_t now;
-		long toks;
-		long ptoks = 0;
+		s64 toks;
+		s64 ptoks = 0;
 		unsigned int len = qdisc_pkt_len(skb);
 
-		now = psched_get_time();
-		toks = psched_tdiff_bounded(now, q->t_c, q->buffer);
+		now = ktime_to_ns(ktime_get());
+		toks = min_t(s64, now - q->t_c, q->buffer);
 
-		if (q->P_tab) {
+		if (q->peek_present) {
 			ptoks = toks + q->ptokens;
 			if (ptoks > (long)q->mtu)
 				ptoks = q->mtu;
-			ptoks -= L2T_P(q, len);
+			ptoks -= (s64) l2t_ns(&q->peek, len);
 		}
 		toks += q->tokens;
 		if (toks > (long)q->buffer)
 			toks = q->buffer;
-		toks -= L2T(q, len);
+		toks -= (s64) l2t_ns(&q->rate, len);
 
 		if ((toks|ptoks) >= 0) {
 			skb = qdisc_dequeue_peeked(q->qdisc);
@@ -214,7 +257,7 @@ static void tbf_reset(struct Qdisc *sch)
 
 	qdisc_reset(q->qdisc);
 	sch->q.qlen = 0;
-	q->t_c = psched_get_time();
+	q->t_c = ktime_to_ns(ktime_get());
 	q->tokens = q->buffer;
 	q->ptokens = q->mtu;
 	qdisc_watchdog_cancel(&q->watchdog);
@@ -299,8 +342,16 @@ static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
 	q->tokens = q->buffer;
 	q->ptokens = q->mtu;
 
-	swap(q->R_tab, rtab);
-	swap(q->P_tab, ptab);
+	q->rate.rate_bps = (u64) rtab->rate.rate << 3;
+	if (ptab) {
+		q->peek.rate_bps = (u64) ptab->rate.rate << 3;
+		q->peek_present = true;
+	} else {
+		q->peek_present = false;
+	}
+
+	htb_precompute_ratedata(&q->rate);
+	htb_precompute_ratedata(&q->peek);
 
 	sch_tree_unlock(sch);
 	err = 0;
@@ -319,7 +370,7 @@ static int tbf_init(struct Qdisc *sch, struct nlattr *opt)
 	if (opt == NULL)
 		return -EINVAL;
 
-	q->t_c = psched_get_time();
+	q->t_c = ktime_to_ns(ktime_get());
 	qdisc_watchdog_init(&q->watchdog, sch);
 	q->qdisc = &noop_qdisc;
 
@@ -331,12 +382,6 @@ static void tbf_destroy(struct Qdisc *sch)
 	struct tbf_sched_data *q = qdisc_priv(sch);
 
 	qdisc_watchdog_cancel(&q->watchdog);
-
-	if (q->P_tab)
-		qdisc_put_rtab(q->P_tab);
-	if (q->R_tab)
-		qdisc_put_rtab(q->R_tab);
-
 	qdisc_destroy(q->qdisc);
 }
 
@@ -352,9 +397,9 @@ static int tbf_dump(struct Qdisc *sch, struct sk_buff *skb)
 		goto nla_put_failure;
 
 	opt.limit = q->limit;
-	opt.rate = q->R_tab->rate;
-	if (q->P_tab)
-		opt.peakrate = q->P_tab->rate;
+	opt.rate.rate = q->rate.rate_bps >> 3;
+	if (q->peek_present)
+		opt.peakrate.rate = q->peek.rate_bps >> 3;
 	else
 		memset(&opt.peakrate, 0, sizeof(opt.peakrate));
 	opt.mtu = q->mtu;
-- 
1.8.1.2

Re: inaccurate packet scheduling

[Eric Dumazet]

On Thu, 2013-02-07 at 18:39 +0100, Jiri Pirko wrote:
> Thu, Feb 07, 2013 at 05:39:35PM CET, eric.dumazet@gmail.com wrote:
> >On Thu, 2013-02-07 at 17:13 +0100, Jiri Pirko wrote:
> >
> >> >I tried kernel with this patch in. I also ported
> >> >56b765b79e9a78dc7d3f8850ba5e5567205a3ecd to tbf. I'm getting always the
> >> >similar numbers with iperf. There must be something else needed :/
> >> 
> >> Any other ideas?
> >
> >You didn't post any patch, how can I comment on them ?
> 
> Okay, sorry, here it is. But as I said, it did not help.
> 
> Subject: [patch net-next RFC] tbf: improved accuracy at high rates
> 
> Current TBF uses rate table computed by the "tc" userspace program,
> which has the following issue:
> 
> The rate table has 256 entries to map packet lengths to
> token (time units).  With TSO sized packets, the 256 entry granularity
> leads to loss/gain of rate, making the token bucket inaccurate.
> 
> Thus, instead of relying on rate table, this patch explicitly computes
> the time and accounts for packet transmission times with nanosecond
> granularity.
> 
> This is a followup to 56b765b79e9a78dc7d3f8850ba5e5567205a3ecd
> 
> Signed-off-by: Jiri Pirko <jiri@resnulli.us>
> ---

This patch doesnt change  q->max_size

So you hit this :

if (qdisc_pkt_len(skb) > q->max_size)
    return qdisc_reshape_fail(skb, sch);

I thought this point was already mentioned in my previous mails.

Re: inaccurate packet scheduling

[Jiri Pirko]

Thu, Feb 07, 2013 at 06:47:38PM CET, eric.dumazet@gmail.com wrote:
>On Thu, 2013-02-07 at 18:39 +0100, Jiri Pirko wrote:
>> Thu, Feb 07, 2013 at 05:39:35PM CET, eric.dumazet@gmail.com wrote:
>> >On Thu, 2013-02-07 at 17:13 +0100, Jiri Pirko wrote:
>> >
>> >> >I tried kernel with this patch in. I also ported
>> >> >56b765b79e9a78dc7d3f8850ba5e5567205a3ecd to tbf. I'm getting always the
>> >> >similar numbers with iperf. There must be something else needed :/
>> >> 
>> >> Any other ideas?
>> >
>> >You didn't post any patch, how can I comment on them ?
>> 
>> Okay, sorry, here it is. But as I said, it did not help.
>> 
>> Subject: [patch net-next RFC] tbf: improved accuracy at high rates
>> 
>> Current TBF uses rate table computed by the "tc" userspace program,
>> which has the following issue:
>> 
>> The rate table has 256 entries to map packet lengths to
>> token (time units).  With TSO sized packets, the 256 entry granularity
>> leads to loss/gain of rate, making the token bucket inaccurate.
>> 
>> Thus, instead of relying on rate table, this patch explicitly computes
>> the time and accounts for packet transmission times with nanosecond
>> granularity.
>> 
>> This is a followup to 56b765b79e9a78dc7d3f8850ba5e5567205a3ecd
>> 
>> Signed-off-by: Jiri Pirko <jiri@resnulli.us>
>> ---
>
>This patch doesnt change  q->max_size
>
>So you hit this :
>
>if (qdisc_pkt_len(skb) > q->max_size)
>    return qdisc_reshape_fail(skb, sch);
>
>I thought this point was already mentioned in my previous mails.

Right. I think I get it now. the RFC patch I posted enables possibility
to remove the max_size limitation, right?

I'm not really familliar in this area so I had to stare at the code for
a while.

>
>
>

Re: inaccurate packet scheduling

[Jiri Pirko]

Tue, Dec 18, 2012 at 05:26:31PM CET, stephen.hemminger@vyatta.com wrote:
>
>
>----- Original Message -----
>> Hi all.
>> 
>> Run one of the following 2 scripts on machine A:
>> 
>> #!/bin/bash
>> tc qdisc del dev eth0 root
>> sleep 1
>> tc -batch << EOF
>> qdisc add dev eth0 root handle 1: prio bands 2 priomap 0 0 0 0 0 0 0
>> 0 0 0 0 0 0 0 0 0
>> qdisc add dev eth0 parent 1:1 handle 10: pfifo limit 50
>> qdisc add dev eth0 parent 1:2 handle 20 tbf latency 100ms rate 4mbit
>> burst 2m
>> filter add dev eth0 parent 1: protocol ip u32 match ip dst
>> $machineB_ip flowid 1:2
>> EOF
>> 
>> #!/bin/bash
>> tc qdisc del dev eth0 root
>> sleep 1
>> tc -batch << EOF
>> qdisc add dev eth0 root handle 1: prio bands 2 priomap 0 0 0 0 0 0 0
>> 0 0 0 0 0 0 0 0 0
>> qdisc add dev eth0 parent 1:1 handle 10: pfifo limit 20
>> qdisc add dev eth0 parent 1:2 handle 20: pfifo limit 20
>> filter add dev eth0 parent 1: protocol ip pref 10 \
>> u32 match ip dst $machineB_ip \
>> flowid 1:2 \
>> police rate 4Mbit burst 2m conform-exceed drop
>> EOF
>> 
>> And run:
>> [machineB ~]# iperf -s
>> [machineA ~]# iperf -c machineB_ip -t 60
>> 
>> Expected results are: ~3.8-4.2 Mbits/s
>> But actual results are: ~130-170 Kbits/s with tbf, ~70-300 Kbits/s
>> with policy rate
>> 
>> [machineA ~]# tc -s qdisc list dev eth0
>> qdisc prio 1: root refcnt 9 bands 2 priomap  0 0 0 0 0 0 0 0 0 0 0 0
>> 0 0 0 0
>>  Sent 1512384 bytes 1032 pkt (dropped 729, overlimits 0 requeues 0)
>>  backlog 0b 0p requeues 0
>> qdisc pfifo 10: parent 1:1 limit 50p
>>  Sent 4560 bytes 32 pkt (dropped 0, overlimits 0 requeues 0)
>>  backlog 0b 0p requeues 0
>> qdisc tbf 20: parent 1:2 rate 4000Kbit burst 2Mb lat 100.0ms
>>  Sent 1507824 bytes 1000 pkt (dropped 729, overlimits 0 requeues 0)
>>  backlog 0b 0p requeues 0
>> 
>> 
>> Tested with kernel pulled from linus's git today. This happens with
>> older
>> kernels as well (I tried 2.6.32-based rhel6 kernels).
>> 
>> This happens to me on following machines:
>> HP DL360G8 (x86_64) http://people.redhat.com/jpirko/aThoo2Ei/dl380g8/
>> HP DL360G3 (i686)
>> IBM JS22 (ppc64) http://people.redhat.com/jpirko/aThoo2Ei/ibmjs22/
>> 
>> On following machines, I do not observe this issue:
>> qemu kvm (x86_64)
>> IBM Zseries (s390x) http://people.redhat.com/jpirko/aThoo2Ei/ibmz/
>> 
>> Please ask in case you need me to provide any other details.
>> 
>> Thanks.
>
>Check kernel log for messages about clock. It could be that on the
>machines with issues TSC is not usable for kernel clock.

No such messages in log

>Also turn off TSO since it screws up any form of rate control.

Turning off TSO did not help. However, turning off scatter-gather
helped, on both HP DL360G8 (igb) and IBM JS22 (ehea).


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

Re: inaccurate packet scheduling

[Eric Dumazet]

> No such messages in log
>
>>Also turn off TSO since it screws up any form of rate control.
>
> Turning off TSO did not help. However, turning off scatter-gather
> helped, on both HP DL360G8 (igb) and IBM JS22 (ehea).
>

Think to also disable GSO

Alternatively, you can use "mtu 65536" to allow TBF to send packets
bigger than 2048 bytes

Re: inaccurate packet scheduling

[Jiri Pirko]

Tue, Dec 18, 2012 at 07:06:53PM CET, edumazet@google.com wrote:
>> No such messages in log
>>
>>>Also turn off TSO since it screws up any form of rate control.
>>
>> Turning off TSO did not help. However, turning off scatter-gather
>> helped, on both HP DL360G8 (igb) and IBM JS22 (ehea).
>>
>
>Think to also disable GSO

On rhel6 kernel (2.6.32-based) I have to disable GSO as well.

The question is: Is this a bug or is it mandatory to get this offload
disabled in order to TBF to be working correctly?

Thanks a bunch.

Jiri

>
>Alternatively, you can use "mtu 65536" to allow TBF to send packets
>bigger than 2048 bytes

Re: inaccurate packet scheduling

[Stephen Hemminger]

On Tue, 18 Dec 2012 19:40:36 +0100
Jiri Pirko <jiri@resnulli.us> wrote:

> Tue, Dec 18, 2012 at 07:06:53PM CET, edumazet@google.com wrote:
> >> No such messages in log
> >>
> >>>Also turn off TSO since it screws up any form of rate control.
> >>
> >> Turning off TSO did not help. However, turning off scatter-gather
> >> helped, on both HP DL360G8 (igb) and IBM JS22 (ehea).
> >>
> >
> >Think to also disable GSO
> 
> On rhel6 kernel (2.6.32-based) I have to disable GSO as well.
> 
> The question is: Is this a bug or is it mandatory to get this offload
> disabled in order to TBF to be working correctly?
> 
> Thanks a bunch.
> 
> Jiri
> 
> >
> >Alternatively, you can use "mtu 65536" to allow TBF to send packets
> >bigger than 2048 bytes

It is really a bug. The packet schedulers mostly assume that a single
skb results in a single packet, and that the skb->len equals the size
of the packet on the wire.