blob: 20ff7386b74bd89c00b50a8f0def91b6c5cce7f4 [file] [log] [blame]
// 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];
/* sch->limit can change under us from skbprio_change() */
if (sch->q.qlen < READ_ONCE(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);
if (opt->nla_len != nla_attr_size(sizeof(*ctl)))
return -EINVAL;
WRITE_ONCE(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 = READ_ONCE(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;
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 (!tc_qdisc_stats_dump(sch, i + 1, arg))
break;
}
}
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,
};
MODULE_ALIAS_NET_SCH("skbprio");
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");
MODULE_DESCRIPTION("SKB priority based scheduling qdisc");