Re: [Cake] [PATCH net-next v8 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc

[Cong Wang]

On Mon, May 7, 2018 at 11:37 AM, Toke Høiland-Jørgensen  wrote:
> Cong Wang  writes:
>
>> On Fri, May 4, 2018 at 12:10 PM, Toke Høiland-Jørgensen  wrote:
>>> Thank you for the review! A few comments below, I'll fix the rest.
>>>
 [...]

 So sch_cake doesn't accept normal tc filters? Is this intentional?
 If so, why?
>>>
>>> For two reasons:
>>>
>>> - The two-level scheduling used in CAKE (tins / diffserv classes, and
>>>   flow hashing) does not map in an obvious way to the classification
>>>   index of tc filters.
>>
>> Sounds like you need to extend struct tcf_result?
>
> Well, the obvious way to support filters would be to have skb->priority
> override the diffserv mapping if set, and have the filter classification
> result select the queue within that tier. That would probably be doable,
> but see below.
>
>>> - No one has asked for it. We have done our best to accommodate the
>>>   features people want in a home router qdisc directly in CAKE, and the
>>>   ability to integrate tc filters has never been requested.
>>
>> It is not hard to integrate, basically you need to call
>> tcf_classify(). Although it is not mandatory, it is odd to merge a
>> qdisc doesn't work with existing tc filters (and actions too).
>
> I looked at the fq_codel code to do this. Is it possible to support
> filtering without implementing Qdisc_class_ops? If so, I'll give it a
> shot; but implementing the class ops is more than I can commit to...

Good question. The tc classes in flow-based qdisc's are actually
used as flows rather than a normal tc class in a hierarchy qdisc.
Like in fq_code, the classes are mapped to each flow and because
of that we can dump stats of each flow.

I am not sure if you can totally bypass class_ops, you need to look
into these API's. Most of them are easy to implement, probably
only except the ->dump_stats(), so I don't think it is a barrier here.


>
> +static int cake_init(struct Qdisc *sch, struct nlattr *opt,
> +struct netlink_ext_ack *extack)
> +{
> +   struct cake_sched_data *q = qdisc_priv(sch);
> +   int i, j;
> +
> +   sch->limit = 10240;
> +   q->tin_mode = CAKE_DIFFSERV_BESTEFFORT;
> +   q->flow_mode  = CAKE_FLOW_TRIPLE;
> +
> +   q->rate_bps = 0; /* unlimited by default */
> +
> +   q->interval = 10; /* 100ms default */
> +   q->target   =   5000; /* 5ms: codel RFC argues
> +  * for 5 to 10% of interval
> +  */
> +
> +   q->cur_tin = 0;
> +   q->cur_flow  = 0;
> +
> +   if (opt) {
> +   int err = cake_change(sch, opt, extack);
> +
> +   if (err)
> +   return err;


 Not sure if you really want to reallocate q->tines below for this
 case.
>>>
>>> I'm not sure what you mean here? If there's an error we return it and
>>> the qdisc is not created. If there's not, we allocate and on subsequent
>>> changes cake_change() will be called directly, or? Can the init function
>>> ever be called again during the lifetime of the qdisc?
>>>
>>
>> In non-error case, you call cake_change() first and then allocate
>> ->tins with kvzalloc() below. For me it looks like you don't need to
>> allocate it again when ->tins!=NULL.
>
> No, we definitely don't. It's just not clear to me how cake_init() could
> ever be called with q->tins already allocated?
>
> I can add a check in any case, though, I see that there is one in
> fq_codel as well...

Ah, that's right, you have a check in cake_change() before
cake_reconfigure().
___
Cake mailing list
Cake@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] [PATCH net-next v8 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc

[Toke Høiland-Jørgensen]

Cong Wang  writes:

> On Fri, May 4, 2018 at 12:10 PM, Toke Høiland-Jørgensen  wrote:
>> Thank you for the review! A few comments below, I'll fix the rest.
>>
>>> [...]
>>>
>>> So sch_cake doesn't accept normal tc filters? Is this intentional?
>>> If so, why?
>>
>> For two reasons:
>>
>> - The two-level scheduling used in CAKE (tins / diffserv classes, and
>>   flow hashing) does not map in an obvious way to the classification
>>   index of tc filters.
>
> Sounds like you need to extend struct tcf_result?

Well, the obvious way to support filters would be to have skb->priority
override the diffserv mapping if set, and have the filter classification
result select the queue within that tier. That would probably be doable,
but see below.

>> - No one has asked for it. We have done our best to accommodate the
>>   features people want in a home router qdisc directly in CAKE, and the
>>   ability to integrate tc filters has never been requested.
>
> It is not hard to integrate, basically you need to call
> tcf_classify(). Although it is not mandatory, it is odd to merge a
> qdisc doesn't work with existing tc filters (and actions too).

I looked at the fq_codel code to do this. Is it possible to support
filtering without implementing Qdisc_class_ops? If so, I'll give it a
shot; but implementing the class ops is more than I can commit to...

 +static int cake_init(struct Qdisc *sch, struct nlattr *opt,
 +struct netlink_ext_ack *extack)
 +{
 +   struct cake_sched_data *q = qdisc_priv(sch);
 +   int i, j;
 +
 +   sch->limit = 10240;
 +   q->tin_mode = CAKE_DIFFSERV_BESTEFFORT;
 +   q->flow_mode  = CAKE_FLOW_TRIPLE;
 +
 +   q->rate_bps = 0; /* unlimited by default */
 +
 +   q->interval = 10; /* 100ms default */
 +   q->target   =   5000; /* 5ms: codel RFC argues
 +  * for 5 to 10% of interval
 +  */
 +
 +   q->cur_tin = 0;
 +   q->cur_flow  = 0;
 +
 +   if (opt) {
 +   int err = cake_change(sch, opt, extack);
 +
 +   if (err)
 +   return err;
>>>
>>>
>>> Not sure if you really want to reallocate q->tines below for this
>>> case.
>>
>> I'm not sure what you mean here? If there's an error we return it and
>> the qdisc is not created. If there's not, we allocate and on subsequent
>> changes cake_change() will be called directly, or? Can the init function
>> ever be called again during the lifetime of the qdisc?
>>
>
> In non-error case, you call cake_change() first and then allocate
> ->tins with kvzalloc() below. For me it looks like you don't need to
> allocate it again when ->tins!=NULL.

No, we definitely don't. It's just not clear to me how cake_init() could
ever be called with q->tins already allocated?

I can add a check in any case, though, I see that there is one in
fq_codel as well...

-Toke
___
Cake mailing list
Cake@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] [PATCH net-next v8 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc

[Cong Wang]

On Fri, May 4, 2018 at 12:10 PM, Toke Høiland-Jørgensen  wrote:
> Thank you for the review! A few comments below, I'll fix the rest.
>
>> [...]
>>
>> So sch_cake doesn't accept normal tc filters? Is this intentional?
>> If so, why?
>
> For two reasons:
>
> - The two-level scheduling used in CAKE (tins / diffserv classes, and
>   flow hashing) does not map in an obvious way to the classification
>   index of tc filters.

Sounds like you need to extend struct tcf_result?

>
> - No one has asked for it. We have done our best to accommodate the
>   features people want in a home router qdisc directly in CAKE, and the
>   ability to integrate tc filters has never been requested.

It is not hard to integrate, basically you need to call tcf_classify().
Although it is not mandatory, it is odd to merge a qdisc doesn't work
with existing tc filters (and actions too).


>>> +static int cake_init(struct Qdisc *sch, struct nlattr *opt,
>>> +struct netlink_ext_ack *extack)
>>> +{
>>> +   struct cake_sched_data *q = qdisc_priv(sch);
>>> +   int i, j;
>>> +
>>> +   sch->limit = 10240;
>>> +   q->tin_mode = CAKE_DIFFSERV_BESTEFFORT;
>>> +   q->flow_mode  = CAKE_FLOW_TRIPLE;
>>> +
>>> +   q->rate_bps = 0; /* unlimited by default */
>>> +
>>> +   q->interval = 10; /* 100ms default */
>>> +   q->target   =   5000; /* 5ms: codel RFC argues
>>> +  * for 5 to 10% of interval
>>> +  */
>>> +
>>> +   q->cur_tin = 0;
>>> +   q->cur_flow  = 0;
>>> +
>>> +   if (opt) {
>>> +   int err = cake_change(sch, opt, extack);
>>> +
>>> +   if (err)
>>> +   return err;
>>
>>
>> Not sure if you really want to reallocate q->tines below for this
>> case.
>
> I'm not sure what you mean here? If there's an error we return it and
> the qdisc is not created. If there's not, we allocate and on subsequent
> changes cake_change() will be called directly, or? Can the init function
> ever be called again during the lifetime of the qdisc?
>

In non-error case, you call cake_change() first and then allocate ->tins
with kvzalloc() below. For me it looks like you don't need to allocate it
again when ->tins!=NULL.
___
Cake mailing list
Cake@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] [PATCH net-next v8 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc

[Toke Høiland-Jørgensen]

Thank you for the review! A few comments below, I'll fix the rest.

> [...]
> 
> So sch_cake doesn't accept normal tc filters? Is this intentional?
> If so, why?

For two reasons:

- The two-level scheduling used in CAKE (tins / diffserv classes, and
  flow hashing) does not map in an obvious way to the classification
  index of tc filters.

- No one has asked for it. We have done our best to accommodate the
  features people want in a home router qdisc directly in CAKE, and the
  ability to integrate tc filters has never been requested.

>> +static u16 quantum_div[CAKE_QUEUES + 1] = {0};
>> +
>> +#define REC_INV_SQRT_CACHE (16)
>> +static u32 cobalt_rec_inv_sqrt_cache[REC_INV_SQRT_CACHE] = {0};
>> +
>> +/* http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
>> + * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
>> + *
>> + * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32
>> + */
>> +
>> +static void cobalt_newton_step(struct cobalt_vars *vars)
>> +{
>> +   u32 invsqrt = vars->rec_inv_sqrt;
>> +   u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 32;
>> +   u64 val = (3LL << 32) - ((u64)vars->count * invsqrt2);
>> +
>> +   val >>= 2; /* avoid overflow in following multiply */
>> +   val = (val * invsqrt) >> (32 - 2 + 1);
>> +
>> +   vars->rec_inv_sqrt = val;
>> +}
>> +
>> +static void cobalt_invsqrt(struct cobalt_vars *vars)
>> +{
>> +   if (vars->count < REC_INV_SQRT_CACHE)
>> +   vars->rec_inv_sqrt = cobalt_rec_inv_sqrt_cache[vars->count];
>> +   else
>> +   cobalt_newton_step(vars);
>> +}
>
> Looks pretty much duplicated with codel...

Cobalt is derived from CoDel, and so naturally shares some features with
it. However, it is quite different in other respects, so we can't just
use the existing CoDel code for the parts that are similar. We don't
feel quite confident enough in Cobalt (yet) to propose it replace CoDel
everywhere else in the kernel; so we have elected to keep it internal to
CAKE instead.

>> [...]
>>
>> +static int cake_init(struct Qdisc *sch, struct nlattr *opt,
>> +struct netlink_ext_ack *extack)
>> +{
>> +   struct cake_sched_data *q = qdisc_priv(sch);
>> +   int i, j;
>> +
>> +   sch->limit = 10240;
>> +   q->tin_mode = CAKE_DIFFSERV_BESTEFFORT;
>> +   q->flow_mode  = CAKE_FLOW_TRIPLE;
>> +
>> +   q->rate_bps = 0; /* unlimited by default */
>> +
>> +   q->interval = 10; /* 100ms default */
>> +   q->target   =   5000; /* 5ms: codel RFC argues
>> +  * for 5 to 10% of interval
>> +  */
>> +
>> +   q->cur_tin = 0;
>> +   q->cur_flow  = 0;
>> +
>> +   if (opt) {
>> +   int err = cake_change(sch, opt, extack);
>> +
>> +   if (err)
>> +   return err;
>
>
> Not sure if you really want to reallocate q->tines below for this
> case.

I'm not sure what you mean here? If there's an error we return it and
the qdisc is not created. If there's not, we allocate and on subsequent
changes cake_change() will be called directly, or? Can the init function
ever be called again during the lifetime of the qdisc?

-Toke
___
Cake mailing list
Cake@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/cake