xref: /openbmc/linux/net/sched/sch_skbprio.c (revision b868a02e)
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3  * net/sched/sch_skbprio.c  SKB Priority Queue.
4  *
5  * Authors:	Nishanth Devarajan, <ndev2021@gmail.com>
6  *		Cody Doucette, <doucette@bu.edu>
7  *	        original idea by Michel Machado, Cody Doucette, and Qiaobin Fu
8  */
9 
10 #include <linux/string.h>
11 #include <linux/module.h>
12 #include <linux/slab.h>
13 #include <linux/types.h>
14 #include <linux/kernel.h>
15 #include <linux/errno.h>
16 #include <linux/skbuff.h>
17 #include <net/pkt_sched.h>
18 #include <net/sch_generic.h>
19 #include <net/inet_ecn.h>
20 
21 /*		SKB Priority Queue
22  *	=================================
23  *
24  * Skbprio (SKB Priority Queue) is a queueing discipline that prioritizes
25  * packets according to their skb->priority field. Under congestion,
26  * Skbprio drops already-enqueued lower priority packets to make space
27  * available for higher priority packets; it was conceived as a solution
28  * for denial-of-service defenses that need to route packets with different
29  * priorities as a mean to overcome DoS attacks.
30  */
31 
32 struct skbprio_sched_data {
33 	/* Queue state. */
34 	struct sk_buff_head qdiscs[SKBPRIO_MAX_PRIORITY];
35 	struct gnet_stats_queue qstats[SKBPRIO_MAX_PRIORITY];
36 	u16 highest_prio;
37 	u16 lowest_prio;
38 };
39 
40 static u16 calc_new_high_prio(const struct skbprio_sched_data *q)
41 {
42 	int prio;
43 
44 	for (prio = q->highest_prio - 1; prio >= q->lowest_prio; prio--) {
45 		if (!skb_queue_empty(&q->qdiscs[prio]))
46 			return prio;
47 	}
48 
49 	/* SKB queue is empty, return 0 (default highest priority setting). */
50 	return 0;
51 }
52 
53 static u16 calc_new_low_prio(const struct skbprio_sched_data *q)
54 {
55 	int prio;
56 
57 	for (prio = q->lowest_prio + 1; prio <= q->highest_prio; prio++) {
58 		if (!skb_queue_empty(&q->qdiscs[prio]))
59 			return prio;
60 	}
61 
62 	/* SKB queue is empty, return SKBPRIO_MAX_PRIORITY - 1
63 	 * (default lowest priority setting).
64 	 */
65 	return SKBPRIO_MAX_PRIORITY - 1;
66 }
67 
68 static int skbprio_enqueue(struct sk_buff *skb, struct Qdisc *sch,
69 			  struct sk_buff **to_free)
70 {
71 	const unsigned int max_priority = SKBPRIO_MAX_PRIORITY - 1;
72 	struct skbprio_sched_data *q = qdisc_priv(sch);
73 	struct sk_buff_head *qdisc;
74 	struct sk_buff_head *lp_qdisc;
75 	struct sk_buff *to_drop;
76 	u16 prio, lp;
77 
78 	/* Obtain the priority of @skb. */
79 	prio = min(skb->priority, max_priority);
80 
81 	qdisc = &q->qdiscs[prio];
82 	if (sch->q.qlen < sch->limit) {
83 		__skb_queue_tail(qdisc, skb);
84 		qdisc_qstats_backlog_inc(sch, skb);
85 		q->qstats[prio].backlog += qdisc_pkt_len(skb);
86 
87 		/* Check to update highest and lowest priorities. */
88 		if (prio > q->highest_prio)
89 			q->highest_prio = prio;
90 
91 		if (prio < q->lowest_prio)
92 			q->lowest_prio = prio;
93 
94 		sch->q.qlen++;
95 		return NET_XMIT_SUCCESS;
96 	}
97 
98 	/* If this packet has the lowest priority, drop it. */
99 	lp = q->lowest_prio;
100 	if (prio <= lp) {
101 		q->qstats[prio].drops++;
102 		q->qstats[prio].overlimits++;
103 		return qdisc_drop(skb, sch, to_free);
104 	}
105 
106 	__skb_queue_tail(qdisc, skb);
107 	qdisc_qstats_backlog_inc(sch, skb);
108 	q->qstats[prio].backlog += qdisc_pkt_len(skb);
109 
110 	/* Drop the packet at the tail of the lowest priority qdisc. */
111 	lp_qdisc = &q->qdiscs[lp];
112 	to_drop = __skb_dequeue_tail(lp_qdisc);
113 	BUG_ON(!to_drop);
114 	qdisc_qstats_backlog_dec(sch, to_drop);
115 	qdisc_drop(to_drop, sch, to_free);
116 
117 	q->qstats[lp].backlog -= qdisc_pkt_len(to_drop);
118 	q->qstats[lp].drops++;
119 	q->qstats[lp].overlimits++;
120 
121 	/* Check to update highest and lowest priorities. */
122 	if (skb_queue_empty(lp_qdisc)) {
123 		if (q->lowest_prio == q->highest_prio) {
124 			/* The incoming packet is the only packet in queue. */
125 			BUG_ON(sch->q.qlen != 1);
126 			q->lowest_prio = prio;
127 			q->highest_prio = prio;
128 		} else {
129 			q->lowest_prio = calc_new_low_prio(q);
130 		}
131 	}
132 
133 	if (prio > q->highest_prio)
134 		q->highest_prio = prio;
135 
136 	return NET_XMIT_CN;
137 }
138 
139 static struct sk_buff *skbprio_dequeue(struct Qdisc *sch)
140 {
141 	struct skbprio_sched_data *q = qdisc_priv(sch);
142 	struct sk_buff_head *hpq = &q->qdiscs[q->highest_prio];
143 	struct sk_buff *skb = __skb_dequeue(hpq);
144 
145 	if (unlikely(!skb))
146 		return NULL;
147 
148 	sch->q.qlen--;
149 	qdisc_qstats_backlog_dec(sch, skb);
150 	qdisc_bstats_update(sch, skb);
151 
152 	q->qstats[q->highest_prio].backlog -= qdisc_pkt_len(skb);
153 
154 	/* Update highest priority field. */
155 	if (skb_queue_empty(hpq)) {
156 		if (q->lowest_prio == q->highest_prio) {
157 			BUG_ON(sch->q.qlen);
158 			q->highest_prio = 0;
159 			q->lowest_prio = SKBPRIO_MAX_PRIORITY - 1;
160 		} else {
161 			q->highest_prio = calc_new_high_prio(q);
162 		}
163 	}
164 	return skb;
165 }
166 
167 static int skbprio_change(struct Qdisc *sch, struct nlattr *opt,
168 			struct netlink_ext_ack *extack)
169 {
170 	struct tc_skbprio_qopt *ctl = nla_data(opt);
171 
172 	if (opt->nla_len != nla_attr_size(sizeof(*ctl)))
173 		return -EINVAL;
174 
175 	sch->limit = ctl->limit;
176 	return 0;
177 }
178 
179 static int skbprio_init(struct Qdisc *sch, struct nlattr *opt,
180 			struct netlink_ext_ack *extack)
181 {
182 	struct skbprio_sched_data *q = qdisc_priv(sch);
183 	int prio;
184 
185 	/* Initialise all queues, one for each possible priority. */
186 	for (prio = 0; prio < SKBPRIO_MAX_PRIORITY; prio++)
187 		__skb_queue_head_init(&q->qdiscs[prio]);
188 
189 	memset(&q->qstats, 0, sizeof(q->qstats));
190 	q->highest_prio = 0;
191 	q->lowest_prio = SKBPRIO_MAX_PRIORITY - 1;
192 	sch->limit = 64;
193 	if (!opt)
194 		return 0;
195 
196 	return skbprio_change(sch, opt, extack);
197 }
198 
199 static int skbprio_dump(struct Qdisc *sch, struct sk_buff *skb)
200 {
201 	struct tc_skbprio_qopt opt;
202 
203 	opt.limit = sch->limit;
204 
205 	if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt))
206 		return -1;
207 
208 	return skb->len;
209 }
210 
211 static void skbprio_reset(struct Qdisc *sch)
212 {
213 	struct skbprio_sched_data *q = qdisc_priv(sch);
214 	int prio;
215 
216 	for (prio = 0; prio < SKBPRIO_MAX_PRIORITY; prio++)
217 		__skb_queue_purge(&q->qdiscs[prio]);
218 
219 	memset(&q->qstats, 0, sizeof(q->qstats));
220 	q->highest_prio = 0;
221 	q->lowest_prio = SKBPRIO_MAX_PRIORITY - 1;
222 }
223 
224 static void skbprio_destroy(struct Qdisc *sch)
225 {
226 	struct skbprio_sched_data *q = qdisc_priv(sch);
227 	int prio;
228 
229 	for (prio = 0; prio < SKBPRIO_MAX_PRIORITY; prio++)
230 		__skb_queue_purge(&q->qdiscs[prio]);
231 }
232 
233 static struct Qdisc *skbprio_leaf(struct Qdisc *sch, unsigned long arg)
234 {
235 	return NULL;
236 }
237 
238 static unsigned long skbprio_find(struct Qdisc *sch, u32 classid)
239 {
240 	return 0;
241 }
242 
243 static int skbprio_dump_class(struct Qdisc *sch, unsigned long cl,
244 			     struct sk_buff *skb, struct tcmsg *tcm)
245 {
246 	tcm->tcm_handle |= TC_H_MIN(cl);
247 	return 0;
248 }
249 
250 static int skbprio_dump_class_stats(struct Qdisc *sch, unsigned long cl,
251 				   struct gnet_dump *d)
252 {
253 	struct skbprio_sched_data *q = qdisc_priv(sch);
254 	if (gnet_stats_copy_queue(d, NULL, &q->qstats[cl - 1],
255 		q->qstats[cl - 1].qlen) < 0)
256 		return -1;
257 	return 0;
258 }
259 
260 static void skbprio_walk(struct Qdisc *sch, struct qdisc_walker *arg)
261 {
262 	unsigned int i;
263 
264 	if (arg->stop)
265 		return;
266 
267 	for (i = 0; i < SKBPRIO_MAX_PRIORITY; i++) {
268 		if (!tc_qdisc_stats_dump(sch, i + 1, arg))
269 			break;
270 	}
271 }
272 
273 static const struct Qdisc_class_ops skbprio_class_ops = {
274 	.leaf		=	skbprio_leaf,
275 	.find		=	skbprio_find,
276 	.dump		=	skbprio_dump_class,
277 	.dump_stats	=	skbprio_dump_class_stats,
278 	.walk		=	skbprio_walk,
279 };
280 
281 static struct Qdisc_ops skbprio_qdisc_ops __read_mostly = {
282 	.cl_ops		=	&skbprio_class_ops,
283 	.id		=	"skbprio",
284 	.priv_size	=	sizeof(struct skbprio_sched_data),
285 	.enqueue	=	skbprio_enqueue,
286 	.dequeue	=	skbprio_dequeue,
287 	.peek		=	qdisc_peek_dequeued,
288 	.init		=	skbprio_init,
289 	.reset		=	skbprio_reset,
290 	.change		=	skbprio_change,
291 	.dump		=	skbprio_dump,
292 	.destroy	=	skbprio_destroy,
293 	.owner		=	THIS_MODULE,
294 };
295 
296 static int __init skbprio_module_init(void)
297 {
298 	return register_qdisc(&skbprio_qdisc_ops);
299 }
300 
301 static void __exit skbprio_module_exit(void)
302 {
303 	unregister_qdisc(&skbprio_qdisc_ops);
304 }
305 
306 module_init(skbprio_module_init)
307 module_exit(skbprio_module_exit)
308 
309 MODULE_LICENSE("GPL");
310