iproute2 / tbf with large burst seems broken again

iproute2 / tbf with large burst seems broken again

[Denys Fedoryschenko]

Found issue, it seems tc_core_time2tick will overflow with increased 
resolution on large bucket values. But no idea how to fix it :-(

I add a warning, something like
 unsigned tc_core_time2tick(unsigned time)
 {
+       long long temp = time*tick_in_usec;
+       if (temp > INT_MAX)
+           printf("tc_core_time2tick() overflow!\n");
        return time*tick_in_usec;
 }

Maybe it is good to add in iproute2 mainstream, so user will be warned if 
buffer set too large? (and it will not set incorrect values, that lead to 
unpredictable results.

Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

On 25-08-2009 01:37, Denys Fedoryschenko wrote:
> Found issue, it seems tc_core_time2tick will overflow with increased 
> resolution on large bucket values. But no idea how to fix it :-(
> 
> I add a warning, something like
>  unsigned tc_core_time2tick(unsigned time)
>  {
> +       long long temp = time*tick_in_usec;
> +       if (temp > INT_MAX)
> +           printf("tc_core_time2tick() overflow!\n");
>         return time*tick_in_usec;
>  }
> 
> Maybe it is good to add in iproute2 mainstream, so user will be warned if 
> buffer set too large? (and it will not set incorrect values, that lead to 
> unpredictable results.

Right, it's about an overflow and it was expected (theoretically) for
very low rates (as for current times) while doing this resolution
change. Probably this kind of warning should be useful if we expect
there're more people who can actually use something like this yet ;-)

Alas INT_MAX could still be not enough to prevent similar issues
because in tbf_dequeue such a value (buffer) is increased with tokens.
I guess we could try to change some variables to 64 bits there, but
the main question is why anybody needs such strange settings today?
Did you try e.g. to browse Internet with that rate and the buffer
e.g. 1500kb or you punish some users only? ;-) Btw, why do you think
'buffer 2000kb' is better "for you" with that rate than e.g. 20kb?

Thanks,
Jarek P.

Re: iproute2 / tbf with large burst seems broken again

[Denys Fedoryschenko]

On Tuesday 25 August 2009 09:22:03 Jarek Poplawski wrote:

>
> Right, it's about an overflow and it was expected (theoretically) for
> very low rates (as for current times) while doing this resolution
> change. Probably this kind of warning should be useful if we expect
> there're more people who can actually use something like this yet ;-)
>
> Alas INT_MAX could still be not enough to prevent similar issues
> because in tbf_dequeue such a value (buffer) is increased with tokens.
> I guess we could try to change some variables to 64 bits there, but
> the main question is why anybody needs such strange settings today?
> Did you try e.g. to browse Internet with that rate and the buffer
> e.g. 1500kb or you punish some users only? ;-) Btw, why do you think
> 'buffer 2000kb' is better "for you" with that rate than e.g. 20kb?
>
> Thanks,
> Jarek P.
Life in Lebanon:
Backbone for ISP - $2200 per Mbit and higher.

Accounts 256Kbit/s cost $66/month in some areas.
96 Kbits/s for people with low income costs cheaper.

>From government "alternative" solution - pay $20 for 2GB, but they charge 
(without any understandable notice for non-tech end-user) extra traffic :-) 
Some people ending month with bills $200/month. Surprise!

Try to browse with 96Kbit/s? U can't actually on this days, with pages that 
weight up to 5-10Mbyte...

The only solution - first 2-10Mbyte, for example, for user will be transferred 
on high speed, let's say 512Kbit/s, but if he put downloads - he will have 
his 96Kbit/s. If he just browse occasionally, his large bucket will 
be "recharged" with 96 Kbit/s, and next page will open again fast.

That's how this TBF configuration that i show works. But sure if it is 
difficult to solve i will implement something similar in userspace, that will 
track user consumption, and just change discipline settings... but sure it 
will be different thing. Actually because there is noone else complained 
about this except me, i guess i have to solve it by myself. Because better 
resolution for high bandwidth traffic shaping much more important even for 
me :-)

Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

On Tue, Aug 25, 2009 at 10:34:09AM +0300, Denys Fedoryschenko wrote:
> On Tuesday 25 August 2009 09:22:03 Jarek Poplawski wrote:
> 
> >
> > Right, it's about an overflow and it was expected (theoretically) for
> > very low rates (as for current times) while doing this resolution
> > change. Probably this kind of warning should be useful if we expect
> > there're more people who can actually use something like this yet ;-)
> >
> > Alas INT_MAX could still be not enough to prevent similar issues
> > because in tbf_dequeue such a value (buffer) is increased with tokens.
> > I guess we could try to change some variables to 64 bits there, but
> > the main question is why anybody needs such strange settings today?
> > Did you try e.g. to browse Internet with that rate and the buffer
> > e.g. 1500kb or you punish some users only? ;-) Btw, why do you think
> > 'buffer 2000kb' is better "for you" with that rate than e.g. 20kb?
> >
> > Thanks,
> > Jarek P.
> Life in Lebanon:
> Backbone for ISP - $2200 per Mbit and higher.
> 
> Accounts 256Kbit/s cost $66/month in some areas.
> 96 Kbits/s for people with low income costs cheaper.
> 
> From government "alternative" solution - pay $20 for 2GB, but they charge 
> (without any understandable notice for non-tech end-user) extra traffic :-) 
> Some people ending month with bills $200/month. Surprise!
> 
> Try to browse with 96Kbit/s? U can't actually on this days, with pages that 
> weight up to 5-10Mbyte...
> 
> The only solution - first 2-10Mbyte, for example, for user will be transferred 
> on high speed, let's say 512Kbit/s, but if he put downloads - he will have 
> his 96Kbit/s. If he just browse occasionally, his large bucket will 
> be "recharged" with 96 Kbit/s, and next page will open again fast.

To make it clear: I didn't wonder about using 96Kbit rate nowdays
(I'm not that modern at all ;-), but 96Kbit with such a big buffer.
I didn't try this but I can imagine the burstiness; but maybe I still
need to figure out your trick...

> That's how this TBF configuration that i show works. But sure if it is 
> difficult to solve i will implement something similar in userspace, that will 
> track user consumption, and just change discipline settings... but sure it 
> will be different thing. Actually because there is noone else complained 
> about this except me, i guess i have to solve it by myself. Because better 
> resolution for high bandwidth traffic shaping much more important even for 
> me :-)

It shouldn't be so difficult just for 2000kb buffer here, but of course
there're some limits. "Noone else" doesn't matter here, because I know
there are not so much -rc networking testers beside you ;-)

There is some inconsistency in schedulers e.g. with using u32 buffers
in configs and 'long' variables to process them. Maybe there should
be some warnings in iproute like you suggested: feel free to send some
patch if you like (I still can't see my 'resolution' patches merged,
btw :-( ). Probably tc_core_time2big might be used for this. But,
since these 64 bits will be needed soon for higher rates anyway, I
guess we could try some change like the patch below, if you find it
works for you (I didn't test it yet.)

Jarek P.
---

 net/sched/sch_tbf.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
index e22dfe8..2c74450 100644
--- a/net/sched/sch_tbf.c
+++ b/net/sched/sch_tbf.c
@@ -160,8 +160,8 @@ static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
 
 	if (skb) {
 		psched_time_t now;
-		long toks;
-		long ptoks = 0;
+		long long toks;
+		long long ptoks = 0;
 		unsigned int len = qdisc_pkt_len(skb);
 
 		now = psched_get_time();

Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

On Tue, Aug 25, 2009 at 08:43:06AM +0000, Jarek Poplawski wrote:
...
> since these 64 bits will be needed soon for higher rates anyway, I
> guess we could try some change like the patch below, if you find it
> works for you (I didn't test it yet.)

Hmm... Don't bother testing it! There is needed something more...

Jarek P.

> ---
> 
>  net/sched/sch_tbf.c |    4 ++--
>  1 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
> index e22dfe8..2c74450 100644
> --- a/net/sched/sch_tbf.c
> +++ b/net/sched/sch_tbf.c
> @@ -160,8 +160,8 @@ static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
>  
>  	if (skb) {
>  		psched_time_t now;
> -		long toks;
> -		long ptoks = 0;
> +		long long toks;
> +		long long ptoks = 0;
>  		unsigned int len = qdisc_pkt_len(skb);
>  
>  		now = psched_get_time();
> 
> 

Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

On Tue, Aug 25, 2009 at 09:00:35AM +0000, Jarek Poplawski wrote:
> On Tue, Aug 25, 2009 at 08:43:06AM +0000, Jarek Poplawski wrote:
> ...
> > since these 64 bits will be needed soon for higher rates anyway, I
> > guess we could try some change like the patch below, if you find it
> > works for you (I didn't test it yet.)

I hope this time it works...

Jarek P.

--- (take 2)

 net/sched/sch_tbf.c |   14 +++++++-------
 1 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
index e22dfe8..7d0fe69 100644
--- a/net/sched/sch_tbf.c
+++ b/net/sched/sch_tbf.c
@@ -108,8 +108,8 @@ struct tbf_sched_data
 	struct qdisc_rate_table	*P_tab;
 
 /* Variables */
-	long	tokens;			/* Current number of B tokens */
-	long	ptokens;		/* Current number of P tokens */
+	u32	tokens;			/* Current number of B tokens */
+	u32	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 */
@@ -160,21 +160,21 @@ static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
 
 	if (skb) {
 		psched_time_t now;
-		long toks;
-		long ptoks = 0;
+		long long toks;
+		long long ptoks = 0;
 		unsigned int len = qdisc_pkt_len(skb);
 
 		now = psched_get_time();
-		toks = psched_tdiff_bounded(now, q->t_c, q->buffer);
+		toks = min_t(u32, now - q->t_c, q->buffer);
 
 		if (q->P_tab) {
 			ptoks = toks + q->ptokens;
-			if (ptoks > (long)q->mtu)
+			if (ptoks > q->mtu)
 				ptoks = q->mtu;
 			ptoks -= L2T_P(q, len);
 		}
 		toks += q->tokens;
-		if (toks > (long)q->buffer)
+		if (toks > q->buffer)
 			toks = q->buffer;
 		toks -= L2T(q, len);
 

Re: iproute2 / tbf with large burst seems broken again

[Denys Fedoryschenko]

Thanks a lot for your help! 
I will try now.

On Tuesday 25 August 2009 12:41:20 Jarek Poplawski wrote:
> On Tue, Aug 25, 2009 at 09:00:35AM +0000, Jarek Poplawski wrote:
> > On Tue, Aug 25, 2009 at 08:43:06AM +0000, Jarek Poplawski wrote:
> > ...
> >
> > > since these 64 bits will be needed soon for higher rates anyway, I
> > > guess we could try some change like the patch below, if you find it
> > > works for you (I didn't test it yet.)
>
> I hope this time it works...
>
> Jarek P.
>
> --- (take 2)
>
>  net/sched/sch_tbf.c |   14 +++++++-------
>  1 files changed, 7 insertions(+), 7 deletions(-)
>
> diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
> index e22dfe8..7d0fe69 100644
> --- a/net/sched/sch_tbf.c
> +++ b/net/sched/sch_tbf.c
> @@ -108,8 +108,8 @@ struct tbf_sched_data
>  	struct qdisc_rate_table	*P_tab;
>
>  /* Variables */
> -	long	tokens;			/* Current number of B tokens */
> -	long	ptokens;		/* Current number of P tokens */
> +	u32	tokens;			/* Current number of B tokens */
> +	u32	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 */
> @@ -160,21 +160,21 @@ static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
>
>  	if (skb) {
>  		psched_time_t now;
> -		long toks;
> -		long ptoks = 0;
> +		long long toks;
> +		long long ptoks = 0;
>  		unsigned int len = qdisc_pkt_len(skb);
>
>  		now = psched_get_time();
> -		toks = psched_tdiff_bounded(now, q->t_c, q->buffer);
> +		toks = min_t(u32, now - q->t_c, q->buffer);
>
>  		if (q->P_tab) {
>  			ptoks = toks + q->ptokens;
> -			if (ptoks > (long)q->mtu)
> +			if (ptoks > q->mtu)
>  				ptoks = q->mtu;
>  			ptoks -= L2T_P(q, len);
>  		}
>  		toks += q->tokens;
> -		if (toks > (long)q->buffer)
> +		if (toks > q->buffer)
>  			toks = q->buffer;
>  		toks -= L2T(q, len);

Re: iproute2 / tbf with large burst seems broken again

[Denys Fedoryschenko]

Done, tested, it doesn't stale and fix the issue but:

PPPoE_146 ~ # ./tc qdisc del dev ppp13 root;./tc qdisc add dev ppp13 root tbf 
rate 96000 burst 2048000 latency 500ms                                               

This one is ok
PPPoE_146 ~ # ./tc -s -d qdisc show dev ppp13
qdisc tbf 8005: root rate 96000bit burst 2000Kb/8 mpu 0b lat 500.0ms
 Sent 55260 bytes 65 pkt (dropped 0, overlimits 0 requeues 0)
 rate 0bit 0pps backlog 0b 0p requeues 0
qdisc ingress ffff: parent ffff:fff1 ----------------
 Sent 641055 bytes 2485 pkt (dropped 0, overlimits 0 requeues 0)
 rate 0bit 0pps backlog 0b 0p requeues 0

PPPoE_146 ~ # ./tc qdisc del dev ppp13 root;./tc qdisc add dev ppp13 root tbf 
rate 96000 burst 4096000 latency 500ms                                               

But this one maybe will overflow because of limitations in iproute2.

PPoE_146 ~ # ./tc -s -d qdisc show dev ppp13
qdisc tbf 8004: root rate 96000bit burst 797465b/8 mpu 0b lat 275.4s
 Sent 82867 bytes 123 pkt (dropped 0, overlimits 0 requeues 0)
 rate 0bit 0pps backlog 0b 0p requeues 0
qdisc ingress ffff: parent ffff:fff1 ----------------
 Sent 506821 bytes 1916 pkt (dropped 0, overlimits 0 requeues 0)
 rate 0bit 0pps backlog 0b 0p requeues 0

So maybe all of that just wrong way of using TBF.
At same time this means, if HTB and policers in filters done same way, that 
QoS in Linux cannot do similar to squid delay pools feature:

First 10Mb give with 1Mbit/s, then slow 64Kbit/s. If user use less than 64K - 
recharge with that unused bandwidth a "10 Mb / 1Mbit bucket".

On Tuesday 25 August 2009 12:41:20 Jarek Poplawski wrote:
> On Tue, Aug 25, 2009 at 09:00:35AM +0000, Jarek Poplawski wrote:
> > On Tue, Aug 25, 2009 at 08:43:06AM +0000, Jarek Poplawski wrote:
> > ...
> >
> > > since these 64 bits will be needed soon for higher rates anyway, I
> > > guess we could try some change like the patch below, if you find it
> > > works for you (I didn't test it yet.)
>
> I hope this time it works...
>
> Jarek P.
>
> --- (take 2)
>
>  net/sched/sch_tbf.c |   14 +++++++-------
>  1 files changed, 7 insertions(+), 7 deletions(-)
>
> diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
> index e22dfe8..7d0fe69 100644
> --- a/net/sched/sch_tbf.c
> +++ b/net/sched/sch_tbf.c
> @@ -108,8 +108,8 @@ struct tbf_sched_data
>  	struct qdisc_rate_table	*P_tab;
>
>  /* Variables */
> -	long	tokens;			/* Current number of B tokens */
> -	long	ptokens;		/* Current number of P tokens */
> +	u32	tokens;			/* Current number of B tokens */
> +	u32	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 */
> @@ -160,21 +160,21 @@ static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
>
>  	if (skb) {
>  		psched_time_t now;
> -		long toks;
> -		long ptoks = 0;
> +		long long toks;
> +		long long ptoks = 0;
>  		unsigned int len = qdisc_pkt_len(skb);
>
>  		now = psched_get_time();
> -		toks = psched_tdiff_bounded(now, q->t_c, q->buffer);
> +		toks = min_t(u32, now - q->t_c, q->buffer);
>
>  		if (q->P_tab) {
>  			ptoks = toks + q->ptokens;
> -			if (ptoks > (long)q->mtu)
> +			if (ptoks > q->mtu)
>  				ptoks = q->mtu;
>  			ptoks -= L2T_P(q, len);
>  		}
>  		toks += q->tokens;
> -		if (toks > (long)q->buffer)
> +		if (toks > q->buffer)
>  			toks = q->buffer;
>  		toks -= L2T(q, len);

Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

On Tue, Aug 25, 2009 at 02:16:13PM +0300, Denys Fedoryschenko wrote:
> Done, tested, it doesn't stale and fix the issue but:
> 
> PPPoE_146 ~ # ./tc qdisc del dev ppp13 root;./tc qdisc add dev ppp13 root tbf 
> rate 96000 burst 2048000 latency 500ms                                               
> 
> This one is ok
> PPPoE_146 ~ # ./tc -s -d qdisc show dev ppp13
> qdisc tbf 8005: root rate 96000bit burst 2000Kb/8 mpu 0b lat 500.0ms
>  Sent 55260 bytes 65 pkt (dropped 0, overlimits 0 requeues 0)
>  rate 0bit 0pps backlog 0b 0p requeues 0
> qdisc ingress ffff: parent ffff:fff1 ----------------
>  Sent 641055 bytes 2485 pkt (dropped 0, overlimits 0 requeues 0)
>  rate 0bit 0pps backlog 0b 0p requeues 0
> 
> PPPoE_146 ~ # ./tc qdisc del dev ppp13 root;./tc qdisc add dev ppp13 root tbf 
> rate 96000 burst 4096000 latency 500ms                                               
> 
> But this one maybe will overflow because of limitations in iproute2.

Sure, as I wrote before:
"It shouldn't be so difficult just for 2000kb buffer here, but of course
there're some limits."
I tried to optimize sch_tbf variables usage only, but this is still
mostly within 32 bits.

> 
> PPoE_146 ~ # ./tc -s -d qdisc show dev ppp13
> qdisc tbf 8004: root rate 96000bit burst 797465b/8 mpu 0b lat 275.4s
>  Sent 82867 bytes 123 pkt (dropped 0, overlimits 0 requeues 0)
>  rate 0bit 0pps backlog 0b 0p requeues 0
> qdisc ingress ffff: parent ffff:fff1 ----------------
>  Sent 506821 bytes 1916 pkt (dropped 0, overlimits 0 requeues 0)
>  rate 0bit 0pps backlog 0b 0p requeues 0
> 
> So maybe all of that just wrong way of using TBF.
> At same time this means, if HTB and policers in filters done same way, that 
> QoS in Linux cannot do similar to squid delay pools feature:
> 
> First 10Mb give with 1Mbit/s, then slow 64Kbit/s. If user use less than 64K - 
> recharge with that unused bandwidth a "10 Mb / 1Mbit bucket".

I'll need to find more time to rethink your problem (and this patch),
because it really looks like your tbf usage is very uncommon. Anyway,
I guess these changes aren't for 2.6.31, unless there're similar
requests from other users soon.

Thanks for testing,
Jarek P.

> 
> On Tuesday 25 August 2009 12:41:20 Jarek Poplawski wrote:
> > On Tue, Aug 25, 2009 at 09:00:35AM +0000, Jarek Poplawski wrote:
> > > On Tue, Aug 25, 2009 at 08:43:06AM +0000, Jarek Poplawski wrote:
> > > ...
> > >
> > > > since these 64 bits will be needed soon for higher rates anyway, I
> > > > guess we could try some change like the patch below, if you find it
> > > > works for you (I didn't test it yet.)
> >
> > I hope this time it works...
> >
> > Jarek P.
> >
> > --- (take 2)
> >
> >  net/sched/sch_tbf.c |   14 +++++++-------
> >  1 files changed, 7 insertions(+), 7 deletions(-)
> >
> > diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
> > index e22dfe8..7d0fe69 100644
> > --- a/net/sched/sch_tbf.c
> > +++ b/net/sched/sch_tbf.c
> > @@ -108,8 +108,8 @@ struct tbf_sched_data
> >  	struct qdisc_rate_table	*P_tab;
> >
> >  /* Variables */
> > -	long	tokens;			/* Current number of B tokens */
> > -	long	ptokens;		/* Current number of P tokens */
> > +	u32	tokens;			/* Current number of B tokens */
> > +	u32	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 */
> > @@ -160,21 +160,21 @@ static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
> >
> >  	if (skb) {
> >  		psched_time_t now;
> > -		long toks;
> > -		long ptoks = 0;
> > +		long long toks;
> > +		long long ptoks = 0;
> >  		unsigned int len = qdisc_pkt_len(skb);
> >
> >  		now = psched_get_time();
> > -		toks = psched_tdiff_bounded(now, q->t_c, q->buffer);
> > +		toks = min_t(u32, now - q->t_c, q->buffer);
> >
> >  		if (q->P_tab) {
> >  			ptoks = toks + q->ptokens;
> > -			if (ptoks > (long)q->mtu)
> > +			if (ptoks > q->mtu)
> >  				ptoks = q->mtu;
> >  			ptoks -= L2T_P(q, len);
> >  		}
> >  		toks += q->tokens;
> > -		if (toks > (long)q->buffer)
> > +		if (toks > q->buffer)
> >  			toks = q->buffer;
> >  		toks -= L2T(q, len);
> 
> 

Re: iproute2 / tbf with large burst seems broken again

[Denys Fedoryschenko]

On Tuesday 25 August 2009 15:13:44 Jarek Poplawski wrote:
> I'll need to find more time to rethink your problem (and this patch),
> because it really looks like your tbf usage is very uncommon. Anyway,
> I guess these changes aren't for 2.6.31, unless there're similar
> requests from other users soon.
>
>Thanks for testing,
>Jarek P.
I guess even no need for any kernel :-)

Just maybe good idea in next kernels to document this or handle overflow, that 
it will give warning in kernel. Otherwise user will have non-functional qdisc 
that will not pass traffic.

[PATCH] Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

Denys Fedoryschenko wrote, On 08/25/2009 02:18 PM:
...
> Just maybe good idea in next kernels to document this or handle overflow, that 
> it will give warning in kernel. Otherwise user will have non-functional qdisc 
> that will not pass traffic.

OK, if this patch works for you send your Tested-by, please.

Thanks,
Jarek P.
---------------->
pkt_sched: Warn on tokens overflow in tbf_dequeue

After recent change of scheduling resolution some "extreme" configs
can cause token overflows with stalls. This patch warns when tokens
were negative before accounting for a packet length.

Reported-by: Denys Fedoryschenko <denys@visp.net.lb>
Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>
---

 net/sched/sch_tbf.c |    6 ++++++
 1 files changed, 6 insertions(+), 0 deletions(-)

diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
index e22dfe8..ef191c4 100644
--- a/net/sched/sch_tbf.c
+++ b/net/sched/sch_tbf.c
@@ -191,6 +191,12 @@ static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
 			return skb;
 		}
 
+		if (unlikely((long)(toks + L2T(q, len)) < 0 ||
+			     (long)(ptoks + L2T_P(q, len) < 0)))
+			if (net_ratelimit())
+				pr_warning("tbf: tokens overflow;"
+					   " fix limits.\n");
+
 		qdisc_watchdog_schedule(&q->watchdog,
 					now + max_t(long, -toks, -ptoks));
 

Re: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[David Miller]

From: Jarek Poplawski <jarkao2@gmail.com>
Date: Wed, 26 Aug 2009 23:59:56 +0200

> Denys Fedoryschenko wrote, On 08/25/2009 02:18 PM:
> ...
>> Just maybe good idea in next kernels to document this or handle overflow, that 
>> it will give warning in kernel. Otherwise user will have non-functional qdisc 
>> that will not pass traffic.
> 
> OK, if this patch works for you send your Tested-by, please.

Denys, please give Jarek's patch some testing and let us know
if it triggers properly for you.

> Thanks,
> Jarek P.
> ---------------->
> pkt_sched: Warn on tokens overflow in tbf_dequeue
> 
> After recent change of scheduling resolution some "extreme" configs
> can cause token overflows with stalls. This patch warns when tokens
> were negative before accounting for a packet length.
> 
> Reported-by: Denys Fedoryschenko <denys@visp.net.lb>
> Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>
> ---
> 
>  net/sched/sch_tbf.c |    6 ++++++
>  1 files changed, 6 insertions(+), 0 deletions(-)
> 
> diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
> index e22dfe8..ef191c4 100644
> --- a/net/sched/sch_tbf.c
> +++ b/net/sched/sch_tbf.c
> @@ -191,6 +191,12 @@ static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
>  			return skb;
>  		}
>  
> +		if (unlikely((long)(toks + L2T(q, len)) < 0 ||
> +			     (long)(ptoks + L2T_P(q, len) < 0)))
> +			if (net_ratelimit())
> +				pr_warning("tbf: tokens overflow;"
> +					   " fix limits.\n");
> +
>  		qdisc_watchdog_schedule(&q->watchdog,
>  					now + max_t(long, -toks, -ptoks));
>  
> --
> 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: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

On Sun, Aug 30, 2009 at 10:05:59PM -0700, David Miller wrote:
> From: Jarek Poplawski <jarkao2@gmail.com>
> Date: Wed, 26 Aug 2009 23:59:56 +0200
> 
> > Denys Fedoryschenko wrote, On 08/25/2009 02:18 PM:
> > ...
> >> Just maybe good idea in next kernels to document this or handle overflow, that 
> >> it will give warning in kernel. Otherwise user will have non-functional qdisc 
> >> that will not pass traffic.
> > 
> > OK, if this patch works for you send your Tested-by, please.
> 
> Denys, please give Jarek's patch some testing and let us know
> if it triggers properly for you.

Actually, I think now, after 2.6.31, this patch might be a bit too
late. If people hit this problem they probably should've fixed it
until -next already, so let's forget about this patch until there are
more such reports.

Btw, I guess, Denys could submit some warnings into iproute's code
and/or documentation, as he proposed earlier.

Thanks,
Jarek P.

> > ---------------->
> > pkt_sched: Warn on tokens overflow in tbf_dequeue
> > 
> > After recent change of scheduling resolution some "extreme" configs
> > can cause token overflows with stalls. This patch warns when tokens
> > were negative before accounting for a packet length.
> > 
> > Reported-by: Denys Fedoryschenko <denys@visp.net.lb>
> > Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>
> > ---
> > 
> >  net/sched/sch_tbf.c |    6 ++++++
> >  1 files changed, 6 insertions(+), 0 deletions(-)
> > 
> > diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
> > index e22dfe8..ef191c4 100644
> > --- a/net/sched/sch_tbf.c
> > +++ b/net/sched/sch_tbf.c
> > @@ -191,6 +191,12 @@ static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
> >  			return skb;
> >  		}
> >  
> > +		if (unlikely((long)(toks + L2T(q, len)) < 0 ||
> > +			     (long)(ptoks + L2T_P(q, len) < 0)))
> > +			if (net_ratelimit())
> > +				pr_warning("tbf: tokens overflow;"
> > +					   " fix limits.\n");
> > +
> >  		qdisc_watchdog_schedule(&q->watchdog,
> >  					now + max_t(long, -toks, -ptoks));
> >  
> > --
> > 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: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[David Miller]

From: Jarek Poplawski <jarkao2@gmail.com>
Date: Mon, 31 Aug 2009 05:30:27 +0000

> Actually, I think now, after 2.6.31, this patch might be a bit too
> late. If people hit this problem they probably should've fixed it
> until -next already, so let's forget about this patch until there are
> more such reports.

Ok.

> Btw, I guess, Denys could submit some warnings into iproute's code
> and/or documentation, as he proposed earlier.

Yeah sounds like a good idea.

Re: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[Denys Fedoryschenko]

On Monday 31 August 2009 08:32:39 David Miller wrote:
> From: Jarek Poplawski <jarkao2@gmail.com>
> Date: Mon, 31 Aug 2009 05:30:27 +0000
>
> > Actually, I think now, after 2.6.31, this patch might be a bit too
> > late. If people hit this problem they probably should've fixed it
> > until -next already, so let's forget about this patch until there are
> > more such reports.
>
> Ok.
>
> > Btw, I guess, Denys could submit some warnings into iproute's code
> > and/or documentation, as he proposed earlier.
>
> Yeah sounds like a good idea.
Sorry, just was busy with network overload on ramadan.
I will test now.

Re: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[Denys Fedoryschenko]

On Monday 31 August 2009 08:32:39 David Miller wrote:
> From: Jarek Poplawski <jarkao2@gmail.com>
> Date: Mon, 31 Aug 2009 05:30:27 +0000
>
> > Actually, I think now, after 2.6.31, this patch might be a bit too
> > late. If people hit this problem they probably should've fixed it
> > until -next already, so let's forget about this patch until there are
> > more such reports.
>
> Ok.
>
> > Btw, I guess, Denys could submit some warnings into iproute's code
> > and/or documentation, as he proposed earlier.
>
> Yeah sounds like a good idea.

2.6.31-rc8 i got dmesg flooded. First message appearing even without patch, i 
will make sure now what is a reason of that (i have HTB classes on ifb0, and 
TBF on pppX).

[  155.199923] Attempt to kill tasklet from interrupt
[  158.425096] Attempt to kill tasklet from interrupt
[  158.425176] Attempt to kill tasklet from interrupt
[  162.549083] Attempt to kill tasklet from interrupt
[  162.549159] Attempt to kill tasklet from interrupt
[  162.601892] Attempt to kill tasklet from interrupt
[  162.601968] Attempt to kill tasklet from interrupt
[  183.719070] Attempt to kill tasklet from interrupt
[  183.719146] Attempt to kill tasklet from interrupt
[  192.147105] Attempt to kill tasklet from interrupt
[  192.147181] Attempt to kill tasklet from interrupt
[  192.604718] tbf: tokens overflow; fix limits.
[  193.085459] tbf: tokens overflow; fix limits.
[  193.102169] tbf: tokens overflow; fix limits.
[  194.100395] tbf: tokens overflow; fix limits.
[  196.010286] tbf: tokens overflow; fix limits.
[  196.014330] tbf: tokens overflow; fix limits.
[  196.100723] tbf: tokens overflow; fix limits.
[  196.104619] tbf: tokens overflow; fix limits.
[  196.998374] tbf: tokens overflow; fix limits.
[  197.854766] tbf: tokens overflow; fix limits.
[  198.676258] tbf: tokens overflow; fix limits.
[  198.676564] tbf: tokens overflow; fix limits.
[  198.984620] tbf: tokens overflow; fix limits.
[  199.599671] tbf: tokens overflow; fix limits.
[  200.101338] tbf: tokens overflow; fix limits.                                                                                                                                                          

Re: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[David Miller]

From: Denys Fedoryschenko <denys@visp.net.lb>
Date: Mon, 31 Aug 2009 11:18:42 +0300

> 2.6.31-rc8 i got dmesg flooded. First message appearing even without patch, i 
> will make sure now what is a reason of that (i have HTB classes on ifb0, and 
> TBF on pppX).
> 
> [  155.199923] Attempt to kill tasklet from interrupt

We know the reasons for this message, it's an HTB regression and we're
working on it.

Re: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[Denys Fedoryschenko]

On Monday 31 August 2009 11:37:38 David Miller wrote:
> From: Denys Fedoryschenko <denys@visp.net.lb>
> Date: Mon, 31 Aug 2009 11:18:42 +0300
>
> > 2.6.31-rc8 i got dmesg flooded. First message appearing even without
> > patch, i will make sure now what is a reason of that (i have HTB classes
> > on ifb0, and TBF on pppX).
> >
> > [  155.199923] Attempt to kill tasklet from interrupt
>
> We know the reasons for this message, it's an HTB regression and we're
> working on it.

Well, those TBF warning seems works fine, i even found one missing shaper that 
was overflowing. Thanks to Jarek.
For now no false positives. Message is appearing only when real overflow 
happen.

Re: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

On Mon, Aug 31, 2009 at 11:51:22AM +0300, Denys Fedoryschenko wrote:
> On Monday 31 August 2009 11:37:38 David Miller wrote:
> > From: Denys Fedoryschenko <denys@visp.net.lb>
> > Date: Mon, 31 Aug 2009 11:18:42 +0300
> >
> > > 2.6.31-rc8 i got dmesg flooded. First message appearing even without
> > > patch, i will make sure now what is a reason of that (i have HTB classes
> > > on ifb0, and TBF on pppX).
> > >
> > > [  155.199923] Attempt to kill tasklet from interrupt
> >
> > We know the reasons for this message, it's an HTB regression and we're
> > working on it.
> 
> Well, those TBF warning seems works fine, i even found one missing shaper that 
> was overflowing. Thanks to Jarek.
> For now no false positives. Message is appearing only when real overflow 
> happen.

I'm glad it helps. On the other hand, I doubt you'll have such configs
until 2.6.32 where this patch was intended. (It's a pity you didn't
report it a bit earlier.) So, let David decide...

Jarek P.

Re: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

On Mon, Aug 31, 2009 at 01:37:38AM -0700, David Miller wrote:
> From: Denys Fedoryschenko <denys@visp.net.lb>
> Date: Mon, 31 Aug 2009 11:18:42 +0300
> 
> > 2.6.31-rc8 i got dmesg flooded. First message appearing even without patch, i 
> > will make sure now what is a reason of that (i have HTB classes on ifb0, and 
> > TBF on pppX).
> > 
> > [  155.199923] Attempt to kill tasklet from interrupt
> 
> We know the reasons for this message, it's an HTB regression and we're
> working on it.

There is a few more than HTB. Btw, IMHO, we don't risk much (if at
all) if we revert this qdisc_watchdog change. There is still CBQ
problem, where we could probably reconsider Thomas Gleixner's first
attempt with additional locking and irq disabling as a temporary
solution?

Jarek P.

Re: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[David Miller]

From: Jarek Poplawski <jarkao2@gmail.com>
Date: Mon, 31 Aug 2009 08:58:49 +0000

> On Mon, Aug 31, 2009 at 01:37:38AM -0700, David Miller wrote:
>> From: Denys Fedoryschenko <denys@visp.net.lb>
>> Date: Mon, 31 Aug 2009 11:18:42 +0300
>> 
>> > 2.6.31-rc8 i got dmesg flooded. First message appearing even without patch, i 
>> > will make sure now what is a reason of that (i have HTB classes on ifb0, and 
>> > TBF on pppX).
>> > 
>> > [  155.199923] Attempt to kill tasklet from interrupt
>> 
>> We know the reasons for this message, it's an HTB regression and we're
>> working on it.
> 
> There is a few more than HTB. Btw, IMHO, we don't risk much (if at
> all) if we revert this qdisc_watchdog change. There is still CBQ
> problem, where we could probably reconsider Thomas Gleixner's first
> attempt with additional locking and irq disabling as a temporary
> solution?

As I stated in another email, I think my plan is going to be to
revert both tasklet_hrtimer changes and try to deal with this in
net-next-2.6 instead.

Re: [PATCH] Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

On Mon, Aug 31, 2009 at 11:18:42AM +0300, Denys Fedoryschenko wrote:
> On Monday 31 August 2009 08:32:39 David Miller wrote:
> > From: Jarek Poplawski <jarkao2@gmail.com>
> > Date: Mon, 31 Aug 2009 05:30:27 +0000
> >
> > > Actually, I think now, after 2.6.31, this patch might be a bit too
> > > late. If people hit this problem they probably should've fixed it
> > > until -next already, so let's forget about this patch until there are
> > > more such reports.
> >
> > Ok.
> >
> > > Btw, I guess, Denys could submit some warnings into iproute's code
> > > and/or documentation, as he proposed earlier.
> >
> > Yeah sounds like a good idea.
> 
> 2.6.31-rc8 i got dmesg flooded. First message appearing even without patch, i 
> will make sure now what is a reason of that (i have HTB classes on ifb0, and 
> TBF on pppX).
> 
> [  155.199923] Attempt to kill tasklet from interrupt
> [  158.425096] Attempt to kill tasklet from interrupt
> [  158.425176] Attempt to kill tasklet from interrupt
> [  162.549083] Attempt to kill tasklet from interrupt
> [  162.549159] Attempt to kill tasklet from interrupt
> [  162.601892] Attempt to kill tasklet from interrupt
> [  162.601968] Attempt to kill tasklet from interrupt
> [  183.719070] Attempt to kill tasklet from interrupt
> [  183.719146] Attempt to kill tasklet from interrupt
> [  192.147105] Attempt to kill tasklet from interrupt
> [  192.147181] Attempt to kill tasklet from interrupt
> [  192.604718] tbf: tokens overflow; fix limits.
> [  193.085459] tbf: tokens overflow; fix limits.
> [  193.102169] tbf: tokens overflow; fix limits.
> [  194.100395] tbf: tokens overflow; fix limits.
> [  196.010286] tbf: tokens overflow; fix limits.
> [  196.014330] tbf: tokens overflow; fix limits.
> [  196.100723] tbf: tokens overflow; fix limits.
> [  196.104619] tbf: tokens overflow; fix limits.
> [  196.998374] tbf: tokens overflow; fix limits.
> [  197.854766] tbf: tokens overflow; fix limits.
> [  198.676258] tbf: tokens overflow; fix limits.
> [  198.676564] tbf: tokens overflow; fix limits.
> [  198.984620] tbf: tokens overflow; fix limits.
> [  199.599671] tbf: tokens overflow; fix limits.
> [  200.101338] tbf: tokens overflow; fix limits.                                                                                                                                                          

I guess it's with a very large (wrt. rate) tbf buffer setting?
Btw, of course testing it would be appreciated, but as I wrote
earlier we can probably wait with this patch for more reports.

Jarek P.

Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

Denys Fedoryschenko wrote, On 08/25/2009 01:16 PM:
...
> But this one maybe will overflow because of limitations in iproute2.
> 
> PPoE_146 ~ # ./tc -s -d qdisc show dev ppp13
> qdisc tbf 8004: root rate 96000bit burst 797465b/8 mpu 0b lat 275.4s
>  Sent 82867 bytes 123 pkt (dropped 0, overlimits 0 requeues 0)
>  rate 0bit 0pps backlog 0b 0p requeues 0
> qdisc ingress ffff: parent ffff:fff1 ----------------
>  Sent 506821 bytes 1916 pkt (dropped 0, overlimits 0 requeues 0)
>  rate 0bit 0pps backlog 0b 0p requeues 0
> 
> So maybe all of that just wrong way of using TBF.

I guess so; I've just recollected you described it some time ago. If
it were done only with TBF it would mean very large surges with line
speed and probably a lot of drops by ISP. Since you're ISP, you
probably drop this with HTB or something (then you should mention it
describing the problem) or keep very long queues which means great
latencies. Probably there is a lot of TCP resending btw. Using TBF
with HTB etc. is considered wrong idea anyway. (But if it works for
you shouldn't care.)

> At same time this means, if HTB and policers in filters done same way, that 
> QoS in Linux cannot do similar to squid delay pools feature:
> 
> First 10Mb give with 1Mbit/s, then slow 64Kbit/s. If user use less than 64K - 
> recharge with that unused bandwidth a "10 Mb / 1Mbit bucket".

Could you remind me why HFSC can't do something similar for you?

Jarek P.

Re: iproute2 / tbf with large burst seems broken again

[Jarek Poplawski]

On Tue, Aug 25, 2009 at 10:03:06PM +0200, Jarek Poplawski wrote:
> Denys Fedoryschenko wrote, On 08/25/2009 01:16 PM:
> ...
> > But this one maybe will overflow because of limitations in iproute2.
> > 
> > PPoE_146 ~ # ./tc -s -d qdisc show dev ppp13
> > qdisc tbf 8004: root rate 96000bit burst 797465b/8 mpu 0b lat 275.4s
> >  Sent 82867 bytes 123 pkt (dropped 0, overlimits 0 requeues 0)
> >  rate 0bit 0pps backlog 0b 0p requeues 0
> > qdisc ingress ffff: parent ffff:fff1 ----------------
> >  Sent 506821 bytes 1916 pkt (dropped 0, overlimits 0 requeues 0)
> >  rate 0bit 0pps backlog 0b 0p requeues 0
> > 
> > So maybe all of that just wrong way of using TBF.
> 
> I guess so; I've just recollected you described it some time ago. If
> it were done only with TBF it would mean very large surges with line
> speed and probably a lot of drops by ISP. Since you're ISP, you
> probably drop this with HTB or something (then you should mention it
> describing the problem) or keep very long queues which means great
> latencies. Probably there is a lot of TCP resending btw. Using TBF
> with HTB etc. is considered wrong idea anyway. (But if it works for
> you shouldn't care.)
> 
> > At same time this means, if HTB and policers in filters done same way, that 
> > QoS in Linux cannot do similar to squid delay pools feature:
> > 
> > First 10Mb give with 1Mbit/s, then slow 64Kbit/s. If user use less than 64K - 
> > recharge with that unused bandwidth a "10 Mb / 1Mbit bucket".

So I thought about it a little more and I'm quite sure this idea with
large buckets is wrong/ineffective. I guess you could "describe" it
in HTB something like this:

tc class add dev ppp0 parent 1:3 classid 1:4 htb rate 64kbit\
   burst 10mb cburst 10mb
tc class add dev ppp0 parent 1:4 classid 1:4 htb rate 64kbit ceil 1mbit\
   cburst 10mb

(Of course, there would be this overflow problem with 2.6.31-rc and
so big buffers.)

So, the main point is: if somebody didn't send his/her 64Kbits long
time ago it usually means it's lost and can't be shared later. You
could try your luck, but e.g. if at the moment all users use their
64Kbits plus one of them 'thinks' he/she can send "saved" bits, it
means some other guy doesn't get his/her minimum (they send together
but some bytes will be dropped or queued).

It would work OK if you've reserved 1mbit per 64Kbit user but I guess
it's not what you do. So, IMHO, it should be better to use classical
methods to guarantee these 64Kbit with reasonable latency, plus
additonal borrowing with ceil and reasonable (much smaller buffers)
yet.

Jarek P.

iproute2 / tbf with large burst seems broken again

[Denys Fedoryschenko]

Seems something related to the changes with resolution. I remember something 
like this happened before, and i report about it, but i am not able to find 
in mail archives. It seems packets queueing and not passing shaper, if burst 
is set to large value.

Kernel 2.6.30.4 was ok.

uname -a
Linux PPPoE_146 2.6.31-rc7-build-0046-32bit #6 SMP Sun Aug 23 03:51:14 EEST 
2009 i686 GNU/Linux

PPPoE_146 ~ # tc -s -d qdisc show dev ppp87;sleep 10;tc -s -d qdisc show dev 
ppp87
qdisc prio 1: root bands 3 priomap  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 Sent 47980 bytes 367 pkt (dropped 0, overlimits 0 requeues 0)
 rate 0bit 0pps backlog 0b 357p requeues 0
qdisc tbf 2: parent 1:1 rate 96000bit burst 2000Kb/8 mpu 0b lat 500.0ms
 Sent 47580 bytes 357 pkt (dropped 0, overlimits 376 requeues 0)
 rate 384bit 1pps backlog 0b 357p requeues 0
qdisc tbf 3: parent 1:2 rate 1024Kbit burst 2000Kb/8 mpu 0b lat 500.0ms
 Sent 400 bytes 10 pkt (dropped 0, overlimits 0 requeues 0)
 rate 0bit 0pps backlog 0b 0p requeues 0
qdisc ingress ffff: parent ffff:fff1 ----------------
 Sent 21342 bytes 347 pkt (dropped 0, overlimits 0 requeues 0)
 rate 0bit 0pps backlog 0b 0p requeues 0
qdisc prio 1: root bands 3 priomap  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 Sent 48410 bytes 372 pkt (dropped 0, overlimits 0 requeues 0)
 rate 0bit 0pps backlog 0b 362p requeues 0
qdisc tbf 2: parent 1:1 rate 96000bit burst 2000Kb/8 mpu 0b lat 500.0ms
 Sent 48010 bytes 362 pkt (dropped 0, overlimits 381 requeues 0)
 rate 448bit 1pps backlog 0b 362p requeues 0
qdisc tbf 3: parent 1:2 rate 1024Kbit burst 2000Kb/8 mpu 0b lat 500.0ms
 Sent 400 bytes 10 pkt (dropped 0, overlimits 0 requeues 0)
 rate 0bit 0pps backlog 0b 0p requeues 0
qdisc ingress ffff: parent ffff:fff1 ----------------
 Sent 21692 bytes 352 pkt (dropped 0, overlimits 0 requeues 0)
 rate 0bit 0pps backlog 0b 0p requeues 0

PPPoE_146 ~ # cat /proc/net/psched
000003e8 00000040 000f4240 3b9aca00