1 // SPDX-License-Identifier: GPL-2.0-only
2 /* Flow Queue PIE discipline
3 *
4 * Copyright (C) 2019 Mohit P. Tahiliani <tahiliani@nitk.edu.in>
5 * Copyright (C) 2019 Sachin D. Patil <sdp.sachin@gmail.com>
6 * Copyright (C) 2019 V. Saicharan <vsaicharan1998@gmail.com>
7 * Copyright (C) 2019 Mohit Bhasi <mohitbhasi1998@gmail.com>
8 * Copyright (C) 2019 Leslie Monis <lesliemonis@gmail.com>
9 * Copyright (C) 2019 Gautam Ramakrishnan <gautamramk@gmail.com>
10 */
11
12 #include <linux/jhash.h>
13 #include <linux/sizes.h>
14 #include <linux/vmalloc.h>
15 #include <net/pkt_cls.h>
16 #include <net/pie.h>
17
18 /* Flow Queue PIE
19 *
20 * Principles:
21 * - Packets are classified on flows.
22 * - This is a Stochastic model (as we use a hash, several flows might
23 * be hashed to the same slot)
24 * - Each flow has a PIE managed queue.
25 * - Flows are linked onto two (Round Robin) lists,
26 * so that new flows have priority on old ones.
27 * - For a given flow, packets are not reordered.
28 * - Drops during enqueue only.
29 * - ECN capability is off by default.
30 * - ECN threshold (if ECN is enabled) is at 10% by default.
31 * - Uses timestamps to calculate queue delay by default.
32 */
33
34 /**
35 * struct fq_pie_flow - contains data for each flow
36 * @vars: pie vars associated with the flow
37 * @deficit: number of remaining byte credits
38 * @backlog: size of data in the flow
39 * @qlen: number of packets in the flow
40 * @flowchain: flowchain for the flow
41 * @head: first packet in the flow
42 * @tail: last packet in the flow
43 */
44 struct fq_pie_flow {
45 struct pie_vars vars;
46 s32 deficit;
47 u32 backlog;
48 u32 qlen;
49 struct list_head flowchain;
50 struct sk_buff *head;
51 struct sk_buff *tail;
52 };
53
54 struct fq_pie_sched_data {
55 struct tcf_proto __rcu *filter_list; /* optional external classifier */
56 struct tcf_block *block;
57 struct fq_pie_flow *flows;
58 struct Qdisc *sch;
59 struct list_head old_flows;
60 struct list_head new_flows;
61 struct pie_params p_params;
62 u32 ecn_prob;
63 u32 flows_cnt;
64 u32 flows_cursor;
65 u32 quantum;
66 u32 memory_limit;
67 u32 new_flow_count;
68 u32 memory_usage;
69 u32 overmemory;
70 struct pie_stats stats;
71 struct timer_list adapt_timer;
72 };
73
fq_pie_hash(const struct fq_pie_sched_data * q,struct sk_buff * skb)74 static unsigned int fq_pie_hash(const struct fq_pie_sched_data *q,
75 struct sk_buff *skb)
76 {
77 return reciprocal_scale(skb_get_hash(skb), q->flows_cnt);
78 }
79
fq_pie_classify(struct sk_buff * skb,struct Qdisc * sch,int * qerr)80 static unsigned int fq_pie_classify(struct sk_buff *skb, struct Qdisc *sch,
81 int *qerr)
82 {
83 struct fq_pie_sched_data *q = qdisc_priv(sch);
84 struct tcf_proto *filter;
85 struct tcf_result res;
86 int result;
87
88 if (TC_H_MAJ(skb->priority) == sch->handle &&
89 TC_H_MIN(skb->priority) > 0 &&
90 TC_H_MIN(skb->priority) <= q->flows_cnt)
91 return TC_H_MIN(skb->priority);
92
93 filter = rcu_dereference_bh(q->filter_list);
94 if (!filter)
95 return fq_pie_hash(q, skb) + 1;
96
97 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
98 result = tcf_classify(skb, NULL, filter, &res, false);
99 if (result >= 0) {
100 #ifdef CONFIG_NET_CLS_ACT
101 switch (result) {
102 case TC_ACT_STOLEN:
103 case TC_ACT_QUEUED:
104 case TC_ACT_TRAP:
105 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
106 fallthrough;
107 case TC_ACT_SHOT:
108 return 0;
109 }
110 #endif
111 if (TC_H_MIN(res.classid) <= q->flows_cnt)
112 return TC_H_MIN(res.classid);
113 }
114 return 0;
115 }
116
117 /* add skb to flow queue (tail add) */
flow_queue_add(struct fq_pie_flow * flow,struct sk_buff * skb)118 static inline void flow_queue_add(struct fq_pie_flow *flow,
119 struct sk_buff *skb)
120 {
121 if (!flow->head)
122 flow->head = skb;
123 else
124 flow->tail->next = skb;
125 flow->tail = skb;
126 skb->next = NULL;
127 }
128
fq_pie_qdisc_enqueue(struct sk_buff * skb,struct Qdisc * sch,struct sk_buff ** to_free)129 static int fq_pie_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch,
130 struct sk_buff **to_free)
131 {
132 struct fq_pie_sched_data *q = qdisc_priv(sch);
133 struct fq_pie_flow *sel_flow;
134 int ret;
135 u8 memory_limited = false;
136 u8 enqueue = false;
137 u32 pkt_len;
138 u32 idx;
139
140 /* Classifies packet into corresponding flow */
141 idx = fq_pie_classify(skb, sch, &ret);
142 if (idx == 0) {
143 if (ret & __NET_XMIT_BYPASS)
144 qdisc_qstats_drop(sch);
145 __qdisc_drop(skb, to_free);
146 return ret;
147 }
148 idx--;
149
150 sel_flow = &q->flows[idx];
151 /* Checks whether adding a new packet would exceed memory limit */
152 get_pie_cb(skb)->mem_usage = skb->truesize;
153 memory_limited = q->memory_usage > q->memory_limit + skb->truesize;
154
155 /* Checks if the qdisc is full */
156 if (unlikely(qdisc_qlen(sch) >= sch->limit)) {
157 q->stats.overlimit++;
158 goto out;
159 } else if (unlikely(memory_limited)) {
160 q->overmemory++;
161 }
162
163 if (!pie_drop_early(sch, &q->p_params, &sel_flow->vars,
164 sel_flow->backlog, skb->len)) {
165 enqueue = true;
166 } else if (q->p_params.ecn &&
167 sel_flow->vars.prob <= (MAX_PROB / 100) * q->ecn_prob &&
168 INET_ECN_set_ce(skb)) {
169 /* If packet is ecn capable, mark it if drop probability
170 * is lower than the parameter ecn_prob, else drop it.
171 */
172 q->stats.ecn_mark++;
173 enqueue = true;
174 }
175 if (enqueue) {
176 /* Set enqueue time only when dq_rate_estimator is disabled. */
177 if (!q->p_params.dq_rate_estimator)
178 pie_set_enqueue_time(skb);
179
180 pkt_len = qdisc_pkt_len(skb);
181 q->stats.packets_in++;
182 q->memory_usage += skb->truesize;
183 sch->qstats.backlog += pkt_len;
184 sch->q.qlen++;
185 flow_queue_add(sel_flow, skb);
186 if (list_empty(&sel_flow->flowchain)) {
187 list_add_tail(&sel_flow->flowchain, &q->new_flows);
188 q->new_flow_count++;
189 sel_flow->deficit = q->quantum;
190 sel_flow->qlen = 0;
191 sel_flow->backlog = 0;
192 }
193 sel_flow->qlen++;
194 sel_flow->backlog += pkt_len;
195 return NET_XMIT_SUCCESS;
196 }
197 out:
198 q->stats.dropped++;
199 sel_flow->vars.accu_prob = 0;
200 __qdisc_drop(skb, to_free);
201 qdisc_qstats_drop(sch);
202 return NET_XMIT_CN;
203 }
204
205 static struct netlink_range_validation fq_pie_q_range = {
206 .min = 1,
207 .max = 1 << 20,
208 };
209
210 static const struct nla_policy fq_pie_policy[TCA_FQ_PIE_MAX + 1] = {
211 [TCA_FQ_PIE_LIMIT] = {.type = NLA_U32},
212 [TCA_FQ_PIE_FLOWS] = {.type = NLA_U32},
213 [TCA_FQ_PIE_TARGET] = {.type = NLA_U32},
214 [TCA_FQ_PIE_TUPDATE] = {.type = NLA_U32},
215 [TCA_FQ_PIE_ALPHA] = {.type = NLA_U32},
216 [TCA_FQ_PIE_BETA] = {.type = NLA_U32},
217 [TCA_FQ_PIE_QUANTUM] =
218 NLA_POLICY_FULL_RANGE(NLA_U32, &fq_pie_q_range),
219 [TCA_FQ_PIE_MEMORY_LIMIT] = {.type = NLA_U32},
220 [TCA_FQ_PIE_ECN_PROB] = {.type = NLA_U32},
221 [TCA_FQ_PIE_ECN] = {.type = NLA_U32},
222 [TCA_FQ_PIE_BYTEMODE] = {.type = NLA_U32},
223 [TCA_FQ_PIE_DQ_RATE_ESTIMATOR] = {.type = NLA_U32},
224 };
225
dequeue_head(struct fq_pie_flow * flow)226 static inline struct sk_buff *dequeue_head(struct fq_pie_flow *flow)
227 {
228 struct sk_buff *skb = flow->head;
229
230 flow->head = skb->next;
231 skb->next = NULL;
232 return skb;
233 }
234
fq_pie_qdisc_dequeue(struct Qdisc * sch)235 static struct sk_buff *fq_pie_qdisc_dequeue(struct Qdisc *sch)
236 {
237 struct fq_pie_sched_data *q = qdisc_priv(sch);
238 struct sk_buff *skb = NULL;
239 struct fq_pie_flow *flow;
240 struct list_head *head;
241 u32 pkt_len;
242
243 begin:
244 head = &q->new_flows;
245 if (list_empty(head)) {
246 head = &q->old_flows;
247 if (list_empty(head))
248 return NULL;
249 }
250
251 flow = list_first_entry(head, struct fq_pie_flow, flowchain);
252 /* Flow has exhausted all its credits */
253 if (flow->deficit <= 0) {
254 flow->deficit += q->quantum;
255 list_move_tail(&flow->flowchain, &q->old_flows);
256 goto begin;
257 }
258
259 if (flow->head) {
260 skb = dequeue_head(flow);
261 pkt_len = qdisc_pkt_len(skb);
262 sch->qstats.backlog -= pkt_len;
263 sch->q.qlen--;
264 qdisc_bstats_update(sch, skb);
265 }
266
267 if (!skb) {
268 /* force a pass through old_flows to prevent starvation */
269 if (head == &q->new_flows && !list_empty(&q->old_flows))
270 list_move_tail(&flow->flowchain, &q->old_flows);
271 else
272 list_del_init(&flow->flowchain);
273 goto begin;
274 }
275
276 flow->qlen--;
277 flow->deficit -= pkt_len;
278 flow->backlog -= pkt_len;
279 q->memory_usage -= get_pie_cb(skb)->mem_usage;
280 pie_process_dequeue(skb, &q->p_params, &flow->vars, flow->backlog);
281 return skb;
282 }
283
fq_pie_change(struct Qdisc * sch,struct nlattr * opt,struct netlink_ext_ack * extack)284 static int fq_pie_change(struct Qdisc *sch, struct nlattr *opt,
285 struct netlink_ext_ack *extack)
286 {
287 struct fq_pie_sched_data *q = qdisc_priv(sch);
288 struct nlattr *tb[TCA_FQ_PIE_MAX + 1];
289 unsigned int len_dropped = 0;
290 unsigned int num_dropped = 0;
291 int err;
292
293 if (!opt)
294 return -EINVAL;
295
296 err = nla_parse_nested(tb, TCA_FQ_PIE_MAX, opt, fq_pie_policy, extack);
297 if (err < 0)
298 return err;
299
300 sch_tree_lock(sch);
301 if (tb[TCA_FQ_PIE_LIMIT]) {
302 u32 limit = nla_get_u32(tb[TCA_FQ_PIE_LIMIT]);
303
304 q->p_params.limit = limit;
305 sch->limit = limit;
306 }
307 if (tb[TCA_FQ_PIE_FLOWS]) {
308 if (q->flows) {
309 NL_SET_ERR_MSG_MOD(extack,
310 "Number of flows cannot be changed");
311 goto flow_error;
312 }
313 q->flows_cnt = nla_get_u32(tb[TCA_FQ_PIE_FLOWS]);
314 if (!q->flows_cnt || q->flows_cnt > 65536) {
315 NL_SET_ERR_MSG_MOD(extack,
316 "Number of flows must range in [1..65536]");
317 goto flow_error;
318 }
319 }
320
321 /* convert from microseconds to pschedtime */
322 if (tb[TCA_FQ_PIE_TARGET]) {
323 /* target is in us */
324 u32 target = nla_get_u32(tb[TCA_FQ_PIE_TARGET]);
325
326 /* convert to pschedtime */
327 q->p_params.target =
328 PSCHED_NS2TICKS((u64)target * NSEC_PER_USEC);
329 }
330
331 /* tupdate is in jiffies */
332 if (tb[TCA_FQ_PIE_TUPDATE])
333 q->p_params.tupdate =
334 usecs_to_jiffies(nla_get_u32(tb[TCA_FQ_PIE_TUPDATE]));
335
336 if (tb[TCA_FQ_PIE_ALPHA])
337 q->p_params.alpha = nla_get_u32(tb[TCA_FQ_PIE_ALPHA]);
338
339 if (tb[TCA_FQ_PIE_BETA])
340 q->p_params.beta = nla_get_u32(tb[TCA_FQ_PIE_BETA]);
341
342 if (tb[TCA_FQ_PIE_QUANTUM])
343 q->quantum = nla_get_u32(tb[TCA_FQ_PIE_QUANTUM]);
344
345 if (tb[TCA_FQ_PIE_MEMORY_LIMIT])
346 q->memory_limit = nla_get_u32(tb[TCA_FQ_PIE_MEMORY_LIMIT]);
347
348 if (tb[TCA_FQ_PIE_ECN_PROB])
349 q->ecn_prob = nla_get_u32(tb[TCA_FQ_PIE_ECN_PROB]);
350
351 if (tb[TCA_FQ_PIE_ECN])
352 q->p_params.ecn = nla_get_u32(tb[TCA_FQ_PIE_ECN]);
353
354 if (tb[TCA_FQ_PIE_BYTEMODE])
355 q->p_params.bytemode = nla_get_u32(tb[TCA_FQ_PIE_BYTEMODE]);
356
357 if (tb[TCA_FQ_PIE_DQ_RATE_ESTIMATOR])
358 q->p_params.dq_rate_estimator =
359 nla_get_u32(tb[TCA_FQ_PIE_DQ_RATE_ESTIMATOR]);
360
361 /* Drop excess packets if new limit is lower */
362 while (sch->q.qlen > sch->limit) {
363 struct sk_buff *skb = fq_pie_qdisc_dequeue(sch);
364
365 len_dropped += qdisc_pkt_len(skb);
366 num_dropped += 1;
367 rtnl_kfree_skbs(skb, skb);
368 }
369 qdisc_tree_reduce_backlog(sch, num_dropped, len_dropped);
370
371 sch_tree_unlock(sch);
372 return 0;
373
374 flow_error:
375 sch_tree_unlock(sch);
376 return -EINVAL;
377 }
378
fq_pie_timer(struct timer_list * t)379 static void fq_pie_timer(struct timer_list *t)
380 {
381 struct fq_pie_sched_data *q = from_timer(q, t, adapt_timer);
382 unsigned long next, tupdate;
383 struct Qdisc *sch = q->sch;
384 spinlock_t *root_lock; /* to lock qdisc for probability calculations */
385 int max_cnt, i;
386
387 root_lock = qdisc_lock(qdisc_root_sleeping(sch));
388 spin_lock(root_lock);
389
390 /* Limit this expensive loop to 2048 flows per round. */
391 max_cnt = min_t(int, q->flows_cnt - q->flows_cursor, 2048);
392 for (i = 0; i < max_cnt; i++) {
393 pie_calculate_probability(&q->p_params,
394 &q->flows[q->flows_cursor].vars,
395 q->flows[q->flows_cursor].backlog);
396 q->flows_cursor++;
397 }
398
399 tupdate = q->p_params.tupdate;
400 next = 0;
401 if (q->flows_cursor >= q->flows_cnt) {
402 q->flows_cursor = 0;
403 next = tupdate;
404 }
405 if (tupdate)
406 mod_timer(&q->adapt_timer, jiffies + next);
407 spin_unlock(root_lock);
408 }
409
fq_pie_init(struct Qdisc * sch,struct nlattr * opt,struct netlink_ext_ack * extack)410 static int fq_pie_init(struct Qdisc *sch, struct nlattr *opt,
411 struct netlink_ext_ack *extack)
412 {
413 struct fq_pie_sched_data *q = qdisc_priv(sch);
414 int err;
415 u32 idx;
416
417 pie_params_init(&q->p_params);
418 sch->limit = 10 * 1024;
419 q->p_params.limit = sch->limit;
420 q->quantum = psched_mtu(qdisc_dev(sch));
421 q->sch = sch;
422 q->ecn_prob = 10;
423 q->flows_cnt = 1024;
424 q->memory_limit = SZ_32M;
425
426 INIT_LIST_HEAD(&q->new_flows);
427 INIT_LIST_HEAD(&q->old_flows);
428 timer_setup(&q->adapt_timer, fq_pie_timer, 0);
429
430 if (opt) {
431 err = fq_pie_change(sch, opt, extack);
432
433 if (err)
434 return err;
435 }
436
437 err = tcf_block_get(&q->block, &q->filter_list, sch, extack);
438 if (err)
439 goto init_failure;
440
441 q->flows = kvcalloc(q->flows_cnt, sizeof(struct fq_pie_flow),
442 GFP_KERNEL);
443 if (!q->flows) {
444 err = -ENOMEM;
445 goto init_failure;
446 }
447 for (idx = 0; idx < q->flows_cnt; idx++) {
448 struct fq_pie_flow *flow = q->flows + idx;
449
450 INIT_LIST_HEAD(&flow->flowchain);
451 pie_vars_init(&flow->vars);
452 }
453
454 mod_timer(&q->adapt_timer, jiffies + HZ / 2);
455
456 return 0;
457
458 init_failure:
459 q->flows_cnt = 0;
460
461 return err;
462 }
463
fq_pie_dump(struct Qdisc * sch,struct sk_buff * skb)464 static int fq_pie_dump(struct Qdisc *sch, struct sk_buff *skb)
465 {
466 struct fq_pie_sched_data *q = qdisc_priv(sch);
467 struct nlattr *opts;
468
469 opts = nla_nest_start(skb, TCA_OPTIONS);
470 if (!opts)
471 return -EMSGSIZE;
472
473 /* convert target from pschedtime to us */
474 if (nla_put_u32(skb, TCA_FQ_PIE_LIMIT, sch->limit) ||
475 nla_put_u32(skb, TCA_FQ_PIE_FLOWS, q->flows_cnt) ||
476 nla_put_u32(skb, TCA_FQ_PIE_TARGET,
477 ((u32)PSCHED_TICKS2NS(q->p_params.target)) /
478 NSEC_PER_USEC) ||
479 nla_put_u32(skb, TCA_FQ_PIE_TUPDATE,
480 jiffies_to_usecs(q->p_params.tupdate)) ||
481 nla_put_u32(skb, TCA_FQ_PIE_ALPHA, q->p_params.alpha) ||
482 nla_put_u32(skb, TCA_FQ_PIE_BETA, q->p_params.beta) ||
483 nla_put_u32(skb, TCA_FQ_PIE_QUANTUM, q->quantum) ||
484 nla_put_u32(skb, TCA_FQ_PIE_MEMORY_LIMIT, q->memory_limit) ||
485 nla_put_u32(skb, TCA_FQ_PIE_ECN_PROB, q->ecn_prob) ||
486 nla_put_u32(skb, TCA_FQ_PIE_ECN, q->p_params.ecn) ||
487 nla_put_u32(skb, TCA_FQ_PIE_BYTEMODE, q->p_params.bytemode) ||
488 nla_put_u32(skb, TCA_FQ_PIE_DQ_RATE_ESTIMATOR,
489 q->p_params.dq_rate_estimator))
490 goto nla_put_failure;
491
492 return nla_nest_end(skb, opts);
493
494 nla_put_failure:
495 nla_nest_cancel(skb, opts);
496 return -EMSGSIZE;
497 }
498
fq_pie_dump_stats(struct Qdisc * sch,struct gnet_dump * d)499 static int fq_pie_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
500 {
501 struct fq_pie_sched_data *q = qdisc_priv(sch);
502 struct tc_fq_pie_xstats st = {
503 .packets_in = q->stats.packets_in,
504 .overlimit = q->stats.overlimit,
505 .overmemory = q->overmemory,
506 .dropped = q->stats.dropped,
507 .ecn_mark = q->stats.ecn_mark,
508 .new_flow_count = q->new_flow_count,
509 .memory_usage = q->memory_usage,
510 };
511 struct list_head *pos;
512
513 sch_tree_lock(sch);
514 list_for_each(pos, &q->new_flows)
515 st.new_flows_len++;
516
517 list_for_each(pos, &q->old_flows)
518 st.old_flows_len++;
519 sch_tree_unlock(sch);
520
521 return gnet_stats_copy_app(d, &st, sizeof(st));
522 }
523
fq_pie_reset(struct Qdisc * sch)524 static void fq_pie_reset(struct Qdisc *sch)
525 {
526 struct fq_pie_sched_data *q = qdisc_priv(sch);
527 u32 idx;
528
529 INIT_LIST_HEAD(&q->new_flows);
530 INIT_LIST_HEAD(&q->old_flows);
531 for (idx = 0; idx < q->flows_cnt; idx++) {
532 struct fq_pie_flow *flow = q->flows + idx;
533
534 /* Removes all packets from flow */
535 rtnl_kfree_skbs(flow->head, flow->tail);
536 flow->head = NULL;
537
538 INIT_LIST_HEAD(&flow->flowchain);
539 pie_vars_init(&flow->vars);
540 }
541 }
542
fq_pie_destroy(struct Qdisc * sch)543 static void fq_pie_destroy(struct Qdisc *sch)
544 {
545 struct fq_pie_sched_data *q = qdisc_priv(sch);
546
547 tcf_block_put(q->block);
548 q->p_params.tupdate = 0;
549 del_timer_sync(&q->adapt_timer);
550 kvfree(q->flows);
551 }
552
553 static struct Qdisc_ops fq_pie_qdisc_ops __read_mostly = {
554 .id = "fq_pie",
555 .priv_size = sizeof(struct fq_pie_sched_data),
556 .enqueue = fq_pie_qdisc_enqueue,
557 .dequeue = fq_pie_qdisc_dequeue,
558 .peek = qdisc_peek_dequeued,
559 .init = fq_pie_init,
560 .destroy = fq_pie_destroy,
561 .reset = fq_pie_reset,
562 .change = fq_pie_change,
563 .dump = fq_pie_dump,
564 .dump_stats = fq_pie_dump_stats,
565 .owner = THIS_MODULE,
566 };
567
fq_pie_module_init(void)568 static int __init fq_pie_module_init(void)
569 {
570 return register_qdisc(&fq_pie_qdisc_ops);
571 }
572
fq_pie_module_exit(void)573 static void __exit fq_pie_module_exit(void)
574 {
575 unregister_qdisc(&fq_pie_qdisc_ops);
576 }
577
578 module_init(fq_pie_module_init);
579 module_exit(fq_pie_module_exit);
580
581 MODULE_DESCRIPTION("Flow Queue Proportional Integral controller Enhanced (FQ-PIE)");
582 MODULE_AUTHOR("Mohit P. Tahiliani");
583 MODULE_LICENSE("GPL");
584