[Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Kevin Darbyshire-Bryant]

Hi All,

I was nosing through linux-netdev last night when I saw this fix for 
qdisc backlog reporting issues with NET_XMIT_CN in fq_codel: 
http://marc.info/?l=linux-netdev&m=146506223800713&w=2

I had a nose at CAKE but couldn't quit work out if a similar issue is 
present but I suspect it is. Certainly if Eric can't get it right "My 
prior attempt to fix the backlogs of parents failed." then it's not an 
'obvious to solve' problem :-)

Adult needed :-)


Cheers,

Kevin

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Jonathan Morton]

> On 7 Jun, 2016, at 14:20, Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk> wrote:
> 
> I had a nose at CAKE but couldn't quit work out if a similar issue is present but I suspect it is. Certainly if Eric can't get it right "My prior attempt to fix the backlogs of parents failed." then it's not an 'obvious to solve' problem :-)

It appears my code already handles it correctly.  This is most likely because it inherited the analogous handling from the old function called here.

 - Jonathan Morton

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Kevin Darbyshire-Bryant]

On 07/06/16 15:50, Jonathan Morton wrote:
>> On 7 Jun, 2016, at 14:20, Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk> wrote:
>>
>> I had a nose at CAKE but couldn't quit work out if a similar issue is present but I suspect it is. Certainly if Eric can't get it right "My prior attempt to fix the backlogs of parents failed." then it's not an 'obvious to solve' problem :-)
> It appears my code already handles it correctly.  This is most likely because it inherited the analogous handling from the old function called here.

I was intrigued by how in the case of XMIT_CN he reports the backlog 
without the packet just dropped 'cos the parent qdisc won't include that 
length in its calculations because we reported we dropped the packet.  
Preventing double accounting.

+	/* As we dropped packet(s), better let upper stack know this.
+	 * If we dropped a packet for this flow, return NET_XMIT_CN,
+	 * but in this case, our parents wont increase their backlogs.
+	 */
+	prev_qlen -= sch->q.qlen;
+	prev_backlog -= sch->qstats.backlog;
+	if (ret == idx) {
+		qdisc_tree_reduce_backlog(sch, prev_qlen - 1,
+					  prev_backlog - qdisc_pkt_len(skb));   <<<<here
+		return NET_XMIT_CN;
+	}
+	qdisc_tree_reduce_backlog(sch, prev_qlen, prev_backlog);
+	return NET_XMIT_SUCCESS;




I'm not sure that cake behaves the same way:


                 u32 old_backlog = q->buffer_used;

                 while (q->buffer_used > q->buffer_limit) {
                         dropped++;
                         if (cake_drop(sch) == idx + (tin << 16))
                                 same_flow = 1;
                 }
                 b->drop_overlimit += dropped;
                 qdisc_tree_reduce_backlog(sch, dropped - same_flow, old_backlog - q->buffer_used);
                 return same_flow ? NET_XMIT_CN : NET_XMIT_SUCCESS;

It looks to me that we always report what was dropped in terms of length irrespective of whether it was from the same flow.  The number of packets *does* change, correctly.


>
>   - Jonathan Morton
>

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Kevin Darbyshire-Bryant]

On 07/06/16 16:05, Kevin Darbyshire-Bryant wrote:
>
>
> On 07/06/16 15:50, Jonathan Morton wrote:
>>> On 7 Jun, 2016, at 14:20, Kevin Darbyshire-Bryant 
>>> <kevin@darbyshire-bryant.me.uk> wrote:
>>>
>>> I had a nose at CAKE but couldn't quit work out if a similar issue 
>>> is present but I suspect it is. Certainly if Eric can't get it right 
>>> "My prior attempt to fix the backlogs of parents failed." then it's 
>>> not an 'obvious to solve' problem :-)
>> It appears my code already handles it correctly.  This is most likely 
>> because it inherited the analogous handling from the old function 
>> called here.
>
> I was intrigued by how in the case of XMIT_CN he reports the backlog 
> without the packet just dropped 'cos the parent qdisc won't include 
> that length in its calculations because we reported we dropped the 
> packet.  Preventing double accounting.
>
> +    /* As we dropped packet(s), better let upper stack know this.
> +     * If we dropped a packet for this flow, return NET_XMIT_CN,
> +     * but in this case, our parents wont increase their backlogs.
> +     */
> +    prev_qlen -= sch->q.qlen;
> +    prev_backlog -= sch->qstats.backlog;
> +    if (ret == idx) {
> +        qdisc_tree_reduce_backlog(sch, prev_qlen - 1,
> +                      prev_backlog - qdisc_pkt_len(skb)); <<<<here
> +        return NET_XMIT_CN;
> +    }
> +    qdisc_tree_reduce_backlog(sch, prev_qlen, prev_backlog);
> +    return NET_XMIT_SUCCESS;

And now there's a version 2 of Eric's fix: 
http://marc.info/?l=linux-netdev&m=146507012302643&w=2

Does this change apply to cake?

Cheers,

Kevin

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Jonathan Morton]

> On 11 Jun, 2016, at 12:11, Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk> wrote:
> 
> And now there's a version 2 of Eric's fix: http://marc.info/?l=linux-netdev&m=146507012302643&w=2
> 
> Does this change apply to cake?

I suppose this answers the question of which packet’s size should be used in the correction factor.  Of course, by this time in the enqueue process, the original packet length has been replaced by the overhead-corrected one in Cake, though I can save a copy for this purpose.

And there’s also the problem that we might not need to drop packets as large as the incoming packet in order to fit the latter into the queue - so this corrected correction may be *negative* (the queue is longer than before) - but qdisc_tree_reduce_backlog() only takes an unsigned parameter here.

IMHO the NET_XMIT_CN semantics are broken.  It might be better to drop support for it, since it should rarely be triggered.

 - Jonathan Morton

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Eric Dumazet]

On Sat, 2016-06-11 at 19:41 +0300, Jonathan Morton wrote:
> > On 11 Jun, 2016, at 12:11, Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk> wrote:
> > 
> > And now there's a version 2 of Eric's fix: http://marc.info/?l=linux-netdev&m=146507012302643&w=2
> > 
> > Does this change apply to cake?
> 
> I suppose this answers the question of which packet’s size should be
> used in the correction factor.  Of course, by this time in the enqueue
> process, the original packet length has been replaced by the
> overhead-corrected one in Cake, though I can save a copy for this
> purpose.
> 
> And there’s also the problem that we might not need to drop packets as
> large as the incoming packet in order to fit the latter into the queue
> - so this corrected correction may be *negative* (the queue is longer
> than before) - but qdisc_tree_reduce_backlog() only takes an unsigned
> parameter here.

That's a very minor detail.

If the code does :

reduce_backlog(unsigned quantity)
{
	q->backlog -= quantity;
}

Then the fact that @quantity is signed or unsigned is irrelevant.

You can submit a patch if you want ;)
> 


> IMHO the NET_XMIT_CN semantics are broken.  It might be better to drop
> support for it, since it should rarely be triggered.

What exact part is broken ?
Semantic looks good to me.

Implementations might be broken after recent Cong Wang patches.

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Dave Taht]

Eric:

Quick side question (from trying to understand the qdisc locking fixes
you recently landed in net-next)

In the sqm-scripts, we are usually in a position where we are doing
both inbound and outbound rate limiting (htb + fq_codel or cake). We
typically run out of cpu or have mis-behavior on the inbound side, and
the cpu bottleneck appears to be in ksoftirqd.

A) In my failing to make sense of all the dialog around these patches
( https://lwn.net/Articles/687617/  ), it sounds like this (inbound
and outbound) processing are still locked to a single thread,
essentially?

B) But you have eliminated lot of overhead in basic qdisc processing
to much cpu benefit and we should consider backporting these changes
to lede/openwrt (4.4)?

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Eric Dumazet]

On Sun, 2016-06-12 at 09:40 -0700, Dave Taht wrote:
> Eric:
> 
> Quick side question (from trying to understand the qdisc locking fixes
> you recently landed in net-next)
> 
> In the sqm-scripts, we are usually in a position where we are doing
> both inbound and outbound rate limiting (htb + fq_codel or cake). We
> typically run out of cpu or have mis-behavior on the inbound side, and
> the cpu bottleneck appears to be in ksoftirqd.
> 
> A) In my failing to make sense of all the dialog around these patches
> ( https://lwn.net/Articles/687617/  ), it sounds like this (inbound
> and outbound) processing are still locked to a single thread,
> essentially?

Om a router, these discussions should not matter really, since the
workload is about receiving/sending packets without user space
intervention (well... I do hope this !)

> 
> B) But you have eliminated lot of overhead in basic qdisc processing
> to much cpu benefit and we should consider backporting these changes
> to lede/openwrt (4.4)?

It is possible that my recent patches avoiding the throttled bit
manipulation might help. I measured between 7% and 8% change in my tests
on x86 with HTB qdisc.

e69f73bfecb0178ae6bd20eb778211739cd71fab Merge branch 'remove-qdisc-throttle'
45f50bed1d808794e514e9eed0e579a8756ce2ba net_sched: remove generic throttled management
42117927cab5a13192ecc227bea19da5059ffc6c net_sched: netem: remove qdisc_is_throttled() use
cca605dd4b3b2bfa381250b7dbbe16b124916f24 net_sched: cbq: remove a flaky use of qdisc_is_throttled()
8fe6a79fb8088a759b3dc57eb641fc3183ad72b8 net_sched: sch_plug: use a private throttled status

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Jonathan Morton]

> On 12 Jun, 2016, at 20:48, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> 
>> A) In my failing to make sense of all the dialog around these patches
>> ( https://lwn.net/Articles/687617/  ), it sounds like this (inbound
>> and outbound) processing are still locked to a single thread,
>> essentially?
> 
> Om a router, these discussions should not matter really, since the
> workload is about receiving/sending packets without user space
> intervention (well... I do hope this !)

Dave’s point is that inbound and outbound processing could in principle be on *two* distinct threads, potentially doubling aggregate throughput in a CPU-limited environment.

 - Jonathan Morton

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Eric Dumazet]

On Sun, 2016-06-12 at 20:51 +0300, Jonathan Morton wrote:
> > On 12 Jun, 2016, at 20:48, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > 
> >> A) In my failing to make sense of all the dialog around these patches
> >> ( https://lwn.net/Articles/687617/  ), it sounds like this (inbound
> >> and outbound) processing are still locked to a single thread,
> >> essentially?
> > 
> > Om a router, these discussions should not matter really, since the
> > workload is about receiving/sending packets without user space
> > intervention (well... I do hope this !)
> 
> Dave’s point is that inbound and outbound processing could in
> principle be on *two* distinct threads, potentially doubling aggregate
> throughput in a CPU-limited environment.

Only if IRQ were not properly tuned (smp_affinity) on SMP host.

If you have one CPU, having two threads wont help, it will actually slow
down a bit things.

NAPI model already handles the 'one cpu, multiple queues/devices' quite
well.

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Jonathan Morton]

>> And there’s also the problem that we might not need to drop packets as
>> large as the incoming packet in order to fit the latter into the queue
>> - so this corrected correction may be *negative* (the queue is longer
>> than before) - but qdisc_tree_reduce_backlog() only takes an unsigned
>> parameter here.
> 
> That's a very minor detail.
> 
> If the code does :
> 
> reduce_backlog(unsigned quantity)
> {
> 	q->backlog -= quantity;
> }
> 
> Then the fact that @quantity is signed or unsigned is irrelevant.

Not so - unless you are very sure that q->backlog is the same size as quantity.  In an increasingly 64-bit world, that is by no means assured in the future.  I don’t like relying on wraparound behaviour without making that assumption explicit, which is precisely what the signed types in C are for.

>> IMHO the NET_XMIT_CN semantics are broken.  It might be better to drop
>> support for it, since it should rarely be triggered.
> 
> What exact part is broken ?
> Semantic looks good to me.

It’s broken in that a negative correction may be required in the first place.  It places additional burden on every producer of the CN signal who isn’t a tail-dropper.  I can only assume that the behaviour was designed with only tail-drop in mind - and as we both know, that is not the only option any more.

It appears to me that there are four things than enqueue() may want to tell its caller:

1: That the packet was enqueued successfully (NET_XMIT_SUCCESS).

2: That the packet was enqueued successfully, but some other relevant packet had to be dropped due to link congestion.

3: That the packet was *not* enqueued, and this was due to link congestion.  This is potentially useful for tail-dropping queues, including AQMs.

4: That the packet was *not* enqueued, for some reason other than link congestion; the “error case".

Currently NET_XMIT_CN appears to cover case 3, whereas Cake normally wants cases 1 & 2 (and will only signal case 4 if a GSO aggregate couldn’t be segmented).

For the time being, I have changed my development branch of Cake to always signal case 1 except for the error case.

 - Jonathan Morton

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Eric Dumazet]

On Sun, 2016-06-12 at 20:59 +0300, Jonathan Morton wrote:

> Not so - unless you are very sure that q->backlog is the same size as
> quantity.

Obviously this is the case in all linux kernels so far.

If someone plans to change this at one point, then yes, he/she has to
fix this.

>   In an increasingly 64-bit world, that is by no means assured in the
> future.  I don’t like relying on wraparound behaviour without making
> that assumption explicit, which is precisely what the signed types in
> C are for.

So why don't you send an official patch, since apparently you plan to
extend a qdisc backlog beyond 4,294,967,296 bytes ?

I am puzzled you have this idea, but why not, some people thought "640KB
out to be enough for anybody" ...
> 
> >> IMHO the NET_XMIT_CN semantics are broken.  It might be better to
> drop
> >> support for it, since it should rarely be triggered.
> > 
> > What exact part is broken ?
> > Semantic looks good to me.
> 
> It’s broken in that a negative correction may be required in the first
> place.

But you do realize NET_XMIT_CN was there _before_ Cong Wang added
backlog tracking in 2ccccf5fb43f ("net_sched: update hierarchical
backlog too")

The fact that Cong used a 'unsigned' instead of a 'signed' here is a
very minor 'bug', since generated code is exactly the _same_.

Claiming the 'semantics' are broken, while the reality is that the
'implementation has a potential bug _if_ we extend to 64bit' is quite
different.

>   It places additional burden on every producer of the CN signal who
> isn’t a tail-dropper.  I can only assume that the behaviour was
> designed with only tail-drop in mind - and as we both know, that is
> not the only option any more.
> 
Nothing implied that only tail drops could happen.

Where have you seen this in the code exactly ?


> It appears to me that there are four things than enqueue() may want to
> tell its caller:
> 
> 1: That the packet was enqueued successfully (NET_XMIT_SUCCESS).
> 
> 2: That the packet was enqueued successfully, but some other relevant
> packet had to be dropped due to link congestion.
> 
> 3: That the packet was *not* enqueued, and this was due to link
> congestion.  This is potentially useful for tail-dropping queues,
> including AQMs.
> 
> 4: That the packet was *not* enqueued, for some reason other than link
> congestion; the “error case".
> 
> Currently NET_XMIT_CN appears to cover case 3, whereas Cake normally
> wants cases 1 & 2 (and will only signal case 4 if a GSO aggregate
> couldn’t be segmented).
> 
Not true. NET_XMIT_CN also covers 2. (not sure what 'relevant' means for
you)

> For the time being, I have changed my development branch of Cake to
> always signal case 1 except for the error case.

Feel free to change it, it is your code.

But do not claim NET_XMIT_CN should be removed, just because you missed
the point (being focused on router workloads I guess)

It can be used by higher level protocol, even if TCP with Small Queues
no longer can hit it with normal settings.

We have per socket counter of dropped rx packets (sk->sk_drops), we
could very easily add a counter of drops or congestions at tx.
This might allow UDP applications to reduce their rate or 'fast'
retransmit without waiting an extra RTT.

Re: [Cake] Possible BUG - parent backlog incorrectly updated in case of NET_XMIT_CN

[Benjamin Cronce]

[-- Attachment #1: Type: text/plain, Size: 3909 bytes --]

4GiB back log is several orders of magnitude more than what you want for a
100Gb link. Unless you think this algorithm will be used for 1Zb/s links.
64bit is a bit overkill
On Jun 12, 2016 2:04 PM, "Eric Dumazet" <eric.dumazet@gmail.com> wrote:

> On Sun, 2016-06-12 at 20:59 +0300, Jonathan Morton wrote:
>
> > Not so - unless you are very sure that q->backlog is the same size as
> > quantity.
>
> Obviously this is the case in all linux kernels so far.
>
> If someone plans to change this at one point, then yes, he/she has to
> fix this.
>
> >   In an increasingly 64-bit world, that is by no means assured in the
> > future.  I don’t like relying on wraparound behaviour without making
> > that assumption explicit, which is precisely what the signed types in
> > C are for.
>
> So why don't you send an official patch, since apparently you plan to
> extend a qdisc backlog beyond 4,294,967,296 bytes ?
>
> I am puzzled you have this idea, but why not, some people thought "640KB
> out to be enough for anybody" ...
> >
> > >> IMHO the NET_XMIT_CN semantics are broken.  It might be better to
> > drop
> > >> support for it, since it should rarely be triggered.
> > >
> > > What exact part is broken ?
> > > Semantic looks good to me.
> >
> > It’s broken in that a negative correction may be required in the first
> > place.
>
> But you do realize NET_XMIT_CN was there _before_ Cong Wang added
> backlog tracking in 2ccccf5fb43f ("net_sched: update hierarchical
> backlog too")
>
> The fact that Cong used a 'unsigned' instead of a 'signed' here is a
> very minor 'bug', since generated code is exactly the _same_.
>
> Claiming the 'semantics' are broken, while the reality is that the
> 'implementation has a potential bug _if_ we extend to 64bit' is quite
> different.
>
> >   It places additional burden on every producer of the CN signal who
> > isn’t a tail-dropper.  I can only assume that the behaviour was
> > designed with only tail-drop in mind - and as we both know, that is
> > not the only option any more.
> >
> Nothing implied that only tail drops could happen.
>
> Where have you seen this in the code exactly ?
>
>
> > It appears to me that there are four things than enqueue() may want to
> > tell its caller:
> >
> > 1: That the packet was enqueued successfully (NET_XMIT_SUCCESS).
> >
> > 2: That the packet was enqueued successfully, but some other relevant
> > packet had to be dropped due to link congestion.
> >
> > 3: That the packet was *not* enqueued, and this was due to link
> > congestion.  This is potentially useful for tail-dropping queues,
> > including AQMs.
> >
> > 4: That the packet was *not* enqueued, for some reason other than link
> > congestion; the “error case".
> >
> > Currently NET_XMIT_CN appears to cover case 3, whereas Cake normally
> > wants cases 1 & 2 (and will only signal case 4 if a GSO aggregate
> > couldn’t be segmented).
> >
> Not true. NET_XMIT_CN also covers 2. (not sure what 'relevant' means for
> you)
>
> > For the time being, I have changed my development branch of Cake to
> > always signal case 1 except for the error case.
>
> Feel free to change it, it is your code.
>
> But do not claim NET_XMIT_CN should be removed, just because you missed
> the point (being focused on router workloads I guess)
>
> It can be used by higher level protocol, even if TCP with Small Queues
> no longer can hit it with normal settings.
>
> We have per socket counter of dropped rx packets (sk->sk_drops), we
> could very easily add a counter of drops or congestions at tx.
> This might allow UDP applications to reduce their rate or 'fast'
> retransmit without waiting an extra RTT.
>
>
>
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake
>

[-- Attachment #2: Type: text/html, Size: 4750 bytes --]