sch_fq_pie.c

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