[linux-2.6-block.git] / net / sched / sch_skbprio.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * net/sched/sch_skbprio.c  SKB Priority Queue.
 *
 * Authors:	Nishanth Devarajan, <ndev2021@gmail.com>
 *		Cody Doucette, <doucette@bu.edu>
 *	        original idea by Michel Machado, Cody Doucette, and Qiaobin Fu
 */

#include <linux/string.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/errno.h>
#include <linux/skbuff.h>
#include <net/pkt_sched.h>
#include <net/sch_generic.h>
#include <net/inet_ecn.h>

/*		SKB Priority Queue
 *	=================================
 *
 * Skbprio (SKB Priority Queue) is a queueing discipline that prioritizes
 * packets according to their skb->priority field. Under congestion,
 * Skbprio drops already-enqueued lower priority packets to make space
 * available for higher priority packets; it was conceived as a solution
 * for denial-of-service defenses that need to route packets with different
 * priorities as a mean to overcome DoS attacks.
 */

struct skbprio_sched_data {
	/* Queue state. */
	struct sk_buff_head qdiscs[SKBPRIO_MAX_PRIORITY];
	struct gnet_stats_queue qstats[SKBPRIO_MAX_PRIORITY];
	u16 highest_prio;
	u16 lowest_prio;
};

static u16 calc_new_high_prio(const struct skbprio_sched_data *q)
{
	int prio;

	for (prio = q->highest_prio - 1; prio >= q->lowest_prio; prio--) {
		if (!skb_queue_empty(&q->qdiscs[prio]))
			return prio;
	}

	/* SKB queue is empty, return 0 (default highest priority setting). */
	return 0;
}

static u16 calc_new_low_prio(const struct skbprio_sched_data *q)
{
	int prio;

	for (prio = q->lowest_prio + 1; prio <= q->highest_prio; prio++) {
		if (!skb_queue_empty(&q->qdiscs[prio]))
			return prio;
	}

	/* SKB queue is empty, return SKBPRIO_MAX_PRIORITY - 1
	 * (default lowest priority setting).
	 */
	return SKBPRIO_MAX_PRIORITY - 1;
}

static int skbprio_enqueue(struct sk_buff *skb, struct Qdisc *sch,
			  struct sk_buff **to_free)
{
	const unsigned int max_priority = SKBPRIO_MAX_PRIORITY - 1;
	struct skbprio_sched_data *q = qdisc_priv(sch);
	struct sk_buff_head *qdisc;
	struct sk_buff_head *lp_qdisc;
	struct sk_buff *to_drop;
	u16 prio, lp;

	/* Obtain the priority of @skb. */
	prio = min(skb->priority, max_priority);

	qdisc = &q->qdiscs[prio];
	if (sch->q.qlen < sch->limit) {
		__skb_queue_tail(qdisc, skb);
		qdisc_qstats_backlog_inc(sch, skb);
		q->qstats[prio].backlog += qdisc_pkt_len(skb);

		/* Check to update highest and lowest priorities. */
		if (prio > q->highest_prio)
			q->highest_prio = prio;

		if (prio < q->lowest_prio)
			q->lowest_prio = prio;

		sch->q.qlen++;
		return NET_XMIT_SUCCESS;
	}

	/* If this packet has the lowest priority, drop it. */
	lp = q->lowest_prio;
	if (prio <= lp) {
		q->qstats[prio].drops++;
		q->qstats[prio].overlimits++;
		return qdisc_drop(skb, sch, to_free);
	}

	__skb_queue_tail(qdisc, skb);
	qdisc_qstats_backlog_inc(sch, skb);
	q->qstats[prio].backlog += qdisc_pkt_len(skb);

	/* Drop the packet at the tail of the lowest priority qdisc. */
	lp_qdisc = &q->qdiscs[lp];
	to_drop = __skb_dequeue_tail(lp_qdisc);
	BUG_ON(!to_drop);
	qdisc_qstats_backlog_dec(sch, to_drop);
	qdisc_drop(to_drop, sch, to_free);

	q->qstats[lp].backlog -= qdisc_pkt_len(to_drop);
	q->qstats[lp].drops++;
	q->qstats[lp].overlimits++;

	/* Check to update highest and lowest priorities. */
	if (skb_queue_empty(lp_qdisc)) {
		if (q->lowest_prio == q->highest_prio) {
			/* The incoming packet is the only packet in queue. */
			BUG_ON(sch->q.qlen != 1);
			q->lowest_prio = prio;
			q->highest_prio = prio;
		} else {
			q->lowest_prio = calc_new_low_prio(q);
		}
	}

	if (prio > q->highest_prio)
		q->highest_prio = prio;

	return NET_XMIT_CN;
}

static struct sk_buff *skbprio_dequeue(struct Qdisc *sch)
{
	struct skbprio_sched_data *q = qdisc_priv(sch);
	struct sk_buff_head *hpq = &q->qdiscs[q->highest_prio];
	struct sk_buff *skb = __skb_dequeue(hpq);

	if (unlikely(!skb))
		return NULL;

	sch->q.qlen--;
	qdisc_qstats_backlog_dec(sch, skb);
	qdisc_bstats_update(sch, skb);

	q->qstats[q->highest_prio].backlog -= qdisc_pkt_len(skb);

	/* Update highest priority field. */
	if (skb_queue_empty(hpq)) {
		if (q->lowest_prio == q->highest_prio) {
			BUG_ON(sch->q.qlen);
			q->highest_prio = 0;
			q->lowest_prio = SKBPRIO_MAX_PRIORITY - 1;
		} else {
			q->highest_prio = calc_new_high_prio(q);
		}
	}
	return skb;
}

static int skbprio_change(struct Qdisc *sch, struct nlattr *opt,
			struct netlink_ext_ack *extack)
{
	struct tc_skbprio_qopt *ctl = nla_data(opt);

	sch->limit = ctl->limit;
	return 0;
}

static int skbprio_init(struct Qdisc *sch, struct nlattr *opt,
			struct netlink_ext_ack *extack)
{
	struct skbprio_sched_data *q = qdisc_priv(sch);
	int prio;

	/* Initialise all queues, one for each possible priority. */
	for (prio = 0; prio < SKBPRIO_MAX_PRIORITY; prio++)
		__skb_queue_head_init(&q->qdiscs[prio]);

	memset(&q->qstats, 0, sizeof(q->qstats));
	q->highest_prio = 0;
	q->lowest_prio = SKBPRIO_MAX_PRIORITY - 1;
	sch->limit = 64;
	if (!opt)
		return 0;

	return skbprio_change(sch, opt, extack);
}

static int skbprio_dump(struct Qdisc *sch, struct sk_buff *skb)
{
	struct tc_skbprio_qopt opt;

	opt.limit = sch->limit;

	if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt))
		return -1;

	return skb->len;
}

static void skbprio_reset(struct Qdisc *sch)
{
	struct skbprio_sched_data *q = qdisc_priv(sch);
	int prio;

	sch->qstats.backlog = 0;
	sch->q.qlen = 0;

	for (prio = 0; prio < SKBPRIO_MAX_PRIORITY; prio++)
		__skb_queue_purge(&q->qdiscs[prio]);

	memset(&q->qstats, 0, sizeof(q->qstats));
	q->highest_prio = 0;
	q->lowest_prio = SKBPRIO_MAX_PRIORITY - 1;
}

static void skbprio_destroy(struct Qdisc *sch)
{
	struct skbprio_sched_data *q = qdisc_priv(sch);
	int prio;

	for (prio = 0; prio < SKBPRIO_MAX_PRIORITY; prio++)
		__skb_queue_purge(&q->qdiscs[prio]);
}

static struct Qdisc *skbprio_leaf(struct Qdisc *sch, unsigned long arg)
{
	return NULL;
}

static unsigned long skbprio_find(struct Qdisc *sch, u32 classid)
{
	return 0;
}

static int skbprio_dump_class(struct Qdisc *sch, unsigned long cl,
			     struct sk_buff *skb, struct tcmsg *tcm)
{
	tcm->tcm_handle |= TC_H_MIN(cl);
	return 0;
}

static int skbprio_dump_class_stats(struct Qdisc *sch, unsigned long cl,
				   struct gnet_dump *d)
{
	struct skbprio_sched_data *q = qdisc_priv(sch);
	if (gnet_stats_copy_queue(d, NULL, &q->qstats[cl - 1],
		q->qstats[cl - 1].qlen) < 0)
		return -1;
	return 0;
}

static void skbprio_walk(struct Qdisc *sch, struct qdisc_walker *arg)
{
	unsigned int i;

	if (arg->stop)
		return;

	for (i = 0; i < SKBPRIO_MAX_PRIORITY; i++) {
		if (arg->count < arg->skip) {
			arg->count++;
			continue;
		}
		if (arg->fn(sch, i + 1, arg) < 0) {
			arg->stop = 1;
			break;
		}
		arg->count++;
	}
}

static const struct Qdisc_class_ops skbprio_class_ops = {
	.leaf		=	skbprio_leaf,
	.find		=	skbprio_find,
	.dump		=	skbprio_dump_class,
	.dump_stats	=	skbprio_dump_class_stats,
	.walk		=	skbprio_walk,
};

static struct Qdisc_ops skbprio_qdisc_ops __read_mostly = {
	.cl_ops		=	&skbprio_class_ops,
	.id		=	"skbprio",
	.priv_size	=	sizeof(struct skbprio_sched_data),
	.enqueue	=	skbprio_enqueue,
	.dequeue	=	skbprio_dequeue,
	.peek		=	qdisc_peek_dequeued,
	.init		=	skbprio_init,
	.reset		=	skbprio_reset,
	.change		=	skbprio_change,
	.dump		=	skbprio_dump,
	.destroy	=	skbprio_destroy,
	.owner		=	THIS_MODULE,
};

static int __init skbprio_module_init(void)
{
	return register_qdisc(&skbprio_qdisc_ops);
}

static void __exit skbprio_module_exit(void)
{
	unregister_qdisc(&skbprio_qdisc_ops);
}

module_init(skbprio_module_init)
module_exit(skbprio_module_exit)

MODULE_LICENSE("GPL");
Commit	Line	Data
2874c5fd	1	// SPDX-License-Identifier: GPL-2.0-or-later
aea5f654 ND	2	/*
	3	* net/sched/sch_skbprio.c SKB Priority Queue.
	4	*
aea5f654 ND	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	sch->limit = ctl->limit;
173	return 0;
174	}
175
176	static int skbprio_init(struct Qdisc sch, struct nlattr opt,
177	struct netlink_ext_ack *extack)
178	{
179	struct skbprio_sched_data *q = qdisc_priv(sch);
180	int prio;
181
182	/* Initialise all queues, one for each possible priority. */
183	for (prio = 0; prio < SKBPRIO_MAX_PRIORITY; prio++)
184	__skb_queue_head_init(&q->qdiscs[prio]);
185
186	memset(&q->qstats, 0, sizeof(q->qstats));
187	q->highest_prio = 0;
188	q->lowest_prio = SKBPRIO_MAX_PRIORITY - 1;
189	sch->limit = 64;
190	if (!opt)
191	return 0;
192
193	return skbprio_change(sch, opt, extack);
194	}
195
196	static int skbprio_dump(struct Qdisc sch, struct sk_buff skb)
197	{
198	struct tc_skbprio_qopt opt;
199
200	opt.limit = sch->limit;
201
202	if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt))
203	return -1;
204
205	return skb->len;
206	}
207
208	static void skbprio_reset(struct Qdisc *sch)
209	{
210	struct skbprio_sched_data *q = qdisc_priv(sch);
211	int prio;
212
213	sch->qstats.backlog = 0;
214	sch->q.qlen = 0;
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 (arg->count < arg->skip) {
269	arg->count++;
270	continue;
271	}
272	if (arg->fn(sch, i + 1, arg) < 0) {
273	arg->stop = 1;
274	break;
275	}
276	arg->count++;
277	}
278	}
279
280	static const struct Qdisc_class_ops skbprio_class_ops = {
281	.leaf = skbprio_leaf,
282	.find = skbprio_find,
283	.dump = skbprio_dump_class,
284	.dump_stats = skbprio_dump_class_stats,
285	.walk = skbprio_walk,
286	};
287
288	static struct Qdisc_ops skbprio_qdisc_ops __read_mostly = {
289	.cl_ops = &skbprio_class_ops,
290	.id = "skbprio",
291	.priv_size = sizeof(struct skbprio_sched_data),
292	.enqueue = skbprio_enqueue,
293	.dequeue = skbprio_dequeue,
294	.peek = qdisc_peek_dequeued,
295	.init = skbprio_init,
296	.reset = skbprio_reset,
297	.change = skbprio_change,
298	.dump = skbprio_dump,
299	.destroy = skbprio_destroy,
300	.owner = THIS_MODULE,
301	};
302
303	static int __init skbprio_module_init(void)
304	{
305	return register_qdisc(&skbprio_qdisc_ops);
306	}
307
308	static void __exit skbprio_module_exit(void)
309	{
310	unregister_qdisc(&skbprio_qdisc_ops);
311	}
312
313	module_init(skbprio_module_init)
314	module_exit(skbprio_module_exit)
315
316	MODULE_LICENSE("GPL");