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