Re: [PATCH net-next v8 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc
On Mon, May 7, 2018 at 11:37 AM, Toke Høiland-Jørgensenwrote: > 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().
Re: [PATCH net-next v8 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc
Cong Wangwrites: > 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
Re: [PATCH net-next v8 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc
On Fri, May 4, 2018 at 12:10 PM, Toke Høiland-Jørgensenwrote: > 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.
Re: [PATCH net-next v8 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc
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
Re: [PATCH net-next v8 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc
On Fri, May 4, 2018 at 7:02 AM, Toke Høiland-Jørgensenwrote: > +struct cake_sched_data { > + struct cake_tin_data *tins; > + > + struct cake_heap_entry overflow_heap[CAKE_QUEUES * CAKE_MAX_TINS]; > + u16 overflow_timeout; > + > + u16 tin_cnt; > + u8 tin_mode; > + u8 flow_mode; > + u8 ack_filter; > + u8 atm_mode; > + > + /* time_next = time_this + ((len * rate_ns) >> rate_shft) */ > + u16 rate_shft; > + u64 time_next_packet; > + u64 failsafe_next_packet; > + u32 rate_ns; > + u32 rate_bps; > + u16 rate_flags; > + s16 rate_overhead; > + u16 rate_mpu; > + u32 interval; > + u32 target; > + > + /* resource tracking */ > + u32 buffer_used; > + u32 buffer_max_used; > + u32 buffer_limit; > + u32 buffer_config_limit; > + > + /* indices for dequeue */ > + u16 cur_tin; > + u16 cur_flow; > + > + struct qdisc_watchdog watchdog; > + const u8*tin_index; > + const u8*tin_order; > + > + /* bandwidth capacity estimate */ > + u64 last_packet_time; > + u64 avg_packet_interval; > + u64 avg_window_begin; > + u32 avg_window_bytes; > + u32 avg_peak_bandwidth; > + u64 last_reconfig_time; > + > + /* packet length stats */ > + u32 avg_netoff; > + u16 max_netlen; > + u16 max_adjlen; > + u16 min_netlen; > + u16 min_adjlen; > +}; So sch_cake doesn't accept normal tc filters? Is this intentional? If so, why? > +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... > + > +/* There is a big difference in timing between the accurate values placed in > + * the cache and the approximations given by a single Newton step for small > + * count values, particularly when stepping from count 1 to 2 or vice versa. > + * Above 16, a single Newton step gives sufficient accuracy in either > + * direction, given the precision stored. > + * > + * The magnitude of the error when stepping up to count 2 is such as to give > + * the value that *should* have been produced at count 4. > + */ > + > +static void cobalt_cache_init(void) > +{ > + struct cobalt_vars v; > + > + memset(, 0, sizeof(v)); > + v.rec_inv_sqrt = ~0U; > + cobalt_rec_inv_sqrt_cache[0] = v.rec_inv_sqrt; > + > + for (v.count = 1; v.count < REC_INV_SQRT_CACHE; v.count++) { > + cobalt_newton_step(); > + cobalt_newton_step(); > + cobalt_newton_step(); > + cobalt_newton_step(); > + > + cobalt_rec_inv_sqrt_cache[v.count] = v.rec_inv_sqrt; > + } > +} > + > +static void cobalt_vars_init(struct cobalt_vars *vars) > +{ > + memset(vars, 0, sizeof(*vars)); > + > + if (!cobalt_rec_inv_sqrt_cache[0]) { > + cobalt_cache_init(); > + cobalt_rec_inv_sqrt_cache[0] = ~0; > + } > +} > + > +/* CoDel control_law is t + interval/sqrt(count) > + * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to avoid > + * both sqrt() and divide operation. > + */ > +static cobalt_time_t cobalt_control(cobalt_time_t t, > + cobalt_time_t interval, > + u32 rec_inv_sqrt) > +{ > + return t + reciprocal_scale(interval, rec_inv_sqrt); > +} > + > +/* Call this when a packet had to be dropped due to queue overflow. Returns > + * true if the BLUE state was quiescent before but active after this call. > + */ > +static bool cobalt_queue_full(struct cobalt_vars *vars, > +
[PATCH net-next v8 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc
sch_cake targets the home router use case and is intended to squeeze the most bandwidth and latency out of even the slowest ISP links and routers, while presenting an API simple enough that even an ISP can configure it. Example of use on a cable ISP uplink: tc qdisc add dev eth0 cake bandwidth 20Mbit nat docsis ack-filter To shape a cable download link (ifb and tc-mirred setup elided) tc qdisc add dev ifb0 cake bandwidth 200mbit nat docsis ingress wash CAKE is filled with: * A hybrid Codel/Blue AQM algorithm, "Cobalt", tied to an FQ_Codel derived Flow Queuing system, which autoconfigures based on the bandwidth. * A novel "triple-isolate" mode (the default) which balances per-host and per-flow FQ even through NAT. * An deficit based shaper, that can also be used in an unlimited mode. * 8 way set associative hashing to reduce flow collisions to a minimum. * A reasonable interpretation of various diffserv latency/loss tradeoffs. * Support for zeroing diffserv markings for entering and exiting traffic. * Support for interacting well with Docsis 3.0 shaper framing. * Extensive support for DSL framing types. * Support for ack filtering. * Extensive statistics for measuring, loss, ecn markings, latency variation. A paper describing the design of CAKE is available at https://arxiv.org/abs/1804.07617 This patch adds the base shaper and packet scheduler, while subsequent commits add the optional (configurable) features. The full userspace API and most data structures are included in this commit, but options not understood in the base version will be ignored. Various versions baking have been available as an out of tree build for kernel versions going back to 3.10, as the embedded router world has been running a few years behind mainline Linux. A stable version has been generally available on lede-17.01 and later. sch_cake replaces a combination of iptables, tc filter, htb and fq_codel in the sqm-scripts, with sane defaults and vastly simpler configuration. CAKE's principal author is Jonathan Morton, with contributions from Kevin Darbyshire-Bryant, Toke Høiland-Jørgensen, Sebastian Moeller, Ryan Mounce, Guido Sarducci, Dean Scarff, Nils Andreas Svee, Dave Täht, and Loganaden Velvindron. Testing from Pete Heist, Georgios Amanakis, and the many other members of the c...@lists.bufferbloat.net mailing list. tc -s qdisc show dev eth2 qdisc cake 1: root refcnt 2 bandwidth 100Mbit diffserv3 triple-isolate rtt 100.0ms raw overhead 0 Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0) backlog 0b 0p requeues 0 memory used: 0b of 500b capacity estimate: 100Mbit min/max network layer size:65535 / 0 min/max overhead-adjusted size:65535 / 0 average network hdr offset:0 Bulk Best EffortVoice thresh 6250Kbit 100Mbit 25Mbit target 5.0ms5.0ms5.0ms interval 100.0ms 100.0ms 100.0ms pk_delay 0us 0us 0us av_delay 0us 0us 0us sp_delay 0us 0us 0us pkts000 bytes 000 way_inds000 way_miss000 way_cols000 drops 000 marks 000 ack_drop000 sp_flows000 bk_flows000 un_flows000 max_len 000 quantum 300 1514 762 Tested-by: Pete HeistTested-by: Georgios Amanakis Signed-off-by: Dave Taht Signed-off-by: Toke Høiland-Jørgensen --- include/uapi/linux/pkt_sched.h | 105 ++ net/sched/Kconfig | 11 net/sched/Makefile |1 net/sched/sch_cake.c | 1683 4 files changed, 1800 insertions(+) create mode 100644 net/sched/sch_cake.c diff --git a/include/uapi/linux/pkt_sched.h b/include/uapi/linux/pkt_sched.h index 37b5096ae97b..bc581473c0b0 100644 --- a/include/uapi/linux/pkt_sched.h +++ b/include/uapi/linux/pkt_sched.h @@ -934,4 +934,109 @@ enum { #define TCA_CBS_MAX (__TCA_CBS_MAX - 1) +/* CAKE */ +enum { + TCA_CAKE_UNSPEC, + TCA_CAKE_BASE_RATE, + TCA_CAKE_DIFFSERV_MODE, + TCA_CAKE_ATM, + TCA_CAKE_FLOW_MODE, + TCA_CAKE_OVERHEAD, + TCA_CAKE_RTT, + TCA_CAKE_TARGET, + TCA_CAKE_AUTORATE, + TCA_CAKE_MEMORY, + TCA_CAKE_NAT, + TCA_CAKE_RAW, + TCA_CAKE_WASH, + TCA_CAKE_MPU, + TCA_CAKE_INGRESS, + TCA_CAKE_ACK_FILTER, + TCA_CAKE_SPLIT_GSO, + __TCA_CAKE_MAX +};