[Cake] cake review comments cake_drop

[Cake] cake review comments cake_drop

[Kevin Darbyshire-Bryant]

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

Hello All,

On 18th Aug (before I'd subscribed to the list), Dave posted a message
about reviewing cake
https://lists.bufferbloat.net/pipermail/cake/2015-August/000364.html

In it he mentioned a change to cake_drop:

"

I would like cake_drop to be evaluated with some less exaustive
search. It also looks wrong

      for(j=0; j < CAKE_MAX_CLASSES; j++) {
                fqcd = &q->classes[j];

CAKE_MAX_CLASSES should actually be q->class_cnt here; I think. I am
unsure if other references to it are correct in face of changes, on
cleanup"


After making the change and nearly submitting a pull request I've
thought about this some more and to be blunt it makes me nervous.  My
concern is what happens if cake is changed from say a diffserv8 config
to a single class(bin) config and for whatever reason 'cake_drop' is
called.  with diffserv8 the fat flow is likely to be in a class(bin)
higher than the first....cake_drop would now only check the first class
for the fat flow and possibly not find anything to drop....  I fear what
happens next!

Kevin


[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 4816 bytes --]

Re: [Cake] cake review comments cake_drop

[Jonathan Morton]

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

I remember changing cake_drop so that it iterated over the list of active
flows rather than the whole potential array. Hence an inactive class, which
has no active queues, costs nothing to iterate over.  Usually the total
number of active queues is tolerably small.

Conversely I don't precisely remember the sequence of events for reducing
the class count, so this change might well break it.

- Jonathan Morton

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

Re: [Cake] cake review comments cake_drop

[Sebastian Moeller]

Hi Jonathan, hi Kevin,


On Oct 4, 2015, at 11:03 , Jonathan Morton <chromatix99@gmail.com> wrote:

> I remember changing cake_drop so that it iterated over the list of active flows rather than the whole potential array. Hence an inactive class, which has no active queues, costs nothing to iterate over.  Usually the total number of active queues is tolerably small.

	Ah, so there is the answer to my question ;) Jonathan, which of the public repositories is the closest to your internal version, so which is the semi-official one?

Best Regards
	Sebastian

> 
> Conversely I don't precisely remember the sequence of events for reducing the class count, so this change might well break it.
> 
> - Jonathan Morton
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] cake review comments cake_drop

[Kevin Darbyshire-Bryant]

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

On 04/10/15 11:56, Sebastian Moeller wrote:
> Hi Jonathan, hi Kevin,
>
>
> On Oct 4, 2015, at 11:03 , Jonathan Morton <chromatix99@gmail.com> wrote:
>
>> I remember changing cake_drop so that it iterated over the list of active flows rather than the whole potential array. Hence an inactive class, which has no active queues, costs nothing to iterate over.  Usually the total number of active queues is tolerably small.
> 	Ah, so there is the answer to my question ;) Jonathan, which of the public repositories is the closest to your internal version, so which is the semi-official one?
It is exists in Dave's repo.  It iterates over the 'old_flows' and
'new_flows' lists for each class looking for the one in most 'distress',
inherently if there's active data to be found it should be on one of
those lists.

In cpu cycle pedant mode, checking for a null list on a set of classes
we know are going to be empty is unnecessary, in a single class config
that's 7 (actually 14) null list searches we don't have to do.  I'm sure
it's not much of a saving but every cycle helps.



[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 4816 bytes --]

Re: [Cake] cake review comments cake_drop

[Sebastian Moeller]

Hi Kevin,

On Oct 4, 2015, at 19:46 , Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk> wrote:

> On 04/10/15 11:56, Sebastian Moeller wrote:
>> Hi Jonathan, hi Kevin,
>> 
>> 
>> On Oct 4, 2015, at 11:03 , Jonathan Morton <chromatix99@gmail.com> wrote:
>> 
>>> I remember changing cake_drop so that it iterated over the list of active flows rather than the whole potential array. Hence an inactive class, which has no active queues, costs nothing to iterate over.  Usually the total number of active queues is tolerably small.
>> 	Ah, so there is the answer to my question ;) Jonathan, which of the public repositories is the closest to your internal version, so which is the semi-official one?
> It is exists in Dave's repo.  It iterates over the 'old_flows' and
> 'new_flows' lists for each class looking for the one in most 'distress',
> inherently if there's active data to be found it should be on one of
> those lists.

	Ah, that is what list_for_each_entry() does… Thanks for spelling it out for me…

Best Regards
	sebastian

> 
> In cpu cycle pedant mode, checking for a null list on a set of classes
> we know are going to be empty is unnecessary, in a single class config
> that's 7 (actually 14) null list searches we don't have to do.  I'm sure
> it's not much of a saving but every cycle helps.
> 
> 

Re: [Cake] cake review comments cake_drop

[Sebastian Moeller]

Hi Kevin,


On Oct 3, 2015, at 21:42 , Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk> wrote:

> Hello All,
> 
> On 18th Aug (before I'd subscribed to the list), Dave posted a message
> about reviewing cake
> https://lists.bufferbloat.net/pipermail/cake/2015-August/000364.html
> 
> In it he mentioned a change to cake_drop:
> 
> "
> 
> I would like cake_drop to be evaluated with some less exaustive
> search. It also looks wrong
> 
>      for(j=0; j < CAKE_MAX_CLASSES; j++) {
>                fqcd = &q->classes[j];
> 
> CAKE_MAX_CLASSES should actually be q->class_cnt here; I think. I am
> unsure if other references to it are correct in face of changes, on
> cleanup"
> 
> 
> After making the change and nearly submitting a pull request I've
> thought about this some more and to be blunt it makes me nervous.  My
> concern is what happens if cake is changed from say a diffserv8 config
> to a single class(bin) config and for whatever reason 'cake_drop' is
> called.  with diffserv8 the fat flow is likely to be in a class(bin)
> higher than the first....cake_drop would now only check the first class
> for the fat flow and possibly not find anything to drop....  I fear what
> happens next!


I thought the following takes care of that (called from cake_reconfigure() ):

/* Discard leftover packets from a class no longer in use. */
static void cake_clear_class(struct Qdisc *sch, u16 class)
{       
        struct cake_sched_data *q = qdisc_priv(sch);
        struct cake_fqcd_sched_data *fqcd = &q->classes[class];
        
        q->cur_class = class;
        for(q->cur_flow = 0; q->cur_flow < fqcd->flows_cnt; q->cur_flow++)
                while(custom_dequeue(NULL, sch))
                        ;
}

I probably do no understand things fully enough, but to me this seems to take care of your concern. Especially since cake_reconfigure will only touch classes from q->class_cnt up to CAKE_MAX_CLASSES. Since I am not very fluent in C I might have missed things… That means that exchanging CAKE_MAX_CLASSES with q->class_cnt in cake_drop() should be safe. The question left is then how costly is it to search empty classes? I guess, cake_drop is the slow path and hence could afford to search them all, then again cake_drop probably tests called most under heavy traffic conditions, so even the slow path performance might be noticeable to the user…

Best Regards
	Sebastian


> 
> Kevin
> 
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] cake review comments cake_drop

[Kevin Darbyshire-Bryant]

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

On 04/10/15 11:50, Sebastian Moeller wrote:
> Hi Kevin,
>
>
> On Oct 3, 2015, at 21:42 , Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk> wrote:
>
>> Hello All,
>>
>> On 18th Aug (before I'd subscribed to the list), Dave posted a message
>> about reviewing cake
>> https://lists.bufferbloat.net/pipermail/cake/2015-August/000364.html
>>
>> In it he mentioned a change to cake_drop:
>>
>> "
>>
>> I would like cake_drop to be evaluated with some less exaustive
>> search. It also looks wrong
>>
>>      for(j=0; j < CAKE_MAX_CLASSES; j++) {
>>                fqcd = &q->classes[j];
>>
>> CAKE_MAX_CLASSES should actually be q->class_cnt here; I think. I am
>> unsure if other references to it are correct in face of changes, on
>> cleanup"
>>
>>
>> After making the change and nearly submitting a pull request I've
>> thought about this some more and to be blunt it makes me nervous.  My
>> concern is what happens if cake is changed from say a diffserv8 config
>> to a single class(bin) config and for whatever reason 'cake_drop' is
>> called.  with diffserv8 the fat flow is likely to be in a class(bin)
>> higher than the first....cake_drop would now only check the first class
>> for the fat flow and possibly not find anything to drop....  I fear what
>> happens next!
>
> I thought the following takes care of that (called from cake_reconfigure() ):
>
> /* Discard leftover packets from a class no longer in use. */
> static void cake_clear_class(struct Qdisc *sch, u16 class)
> {       
>         struct cake_sched_data *q = qdisc_priv(sch);
>         struct cake_fqcd_sched_data *fqcd = &q->classes[class];
>         
>         q->cur_class = class;
>         for(q->cur_flow = 0; q->cur_flow < fqcd->flows_cnt; q->cur_flow++)
>                 while(custom_dequeue(NULL, sch))
>                         ;
> }
>
> I probably do no understand things fully enough, but to me this seems to take care of your concern. Especially since cake_reconfigure will only touch classes from q->class_cnt up to CAKE_MAX_CLASSES. Since I am not very fluent in C I might have missed things… That means that exchanging CAKE_MAX_CLASSES with q->class_cnt in cake_drop() should be safe. The question left is then how costly is it to search empty classes? I guess, cake_drop is the slow path and hence could afford to search them all, then again cake_drop probably tests called most under heavy traffic conditions, so even the slow path performance might be noticeable to the user…
Good spot Sebastian!  I agree that looking through the code would
indicate that a reconfigure from say 'diffserv8' to 'besteffort' would
actually cause cake to drop all the packets in the now redundant
classes, therefore my worry is solved.  I've re-submitted the pull
request.  I may even merge it as it has been running on my router for a
couple of days without actually blowing up :-)





[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 4816 bytes --]