net/sched/sch_skbprio.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /*
0003  * net/sched/sch_skbprio.c  SKB Priority Queue.
0004  *
0005  * Authors: Nishanth Devarajan, <ndev2021@gmail.com>
0006  *      Cody Doucette, <doucette@bu.edu>
0007  *          original idea by Michel Machado, Cody Doucette, and Qiaobin Fu
0008  */
0009
0010 #include <linux/string.h>
0011 #include <linux/module.h>
0012 #include <linux/slab.h>
0013 #include <linux/types.h>
0014 #include <linux/kernel.h>
0015 #include <linux/errno.h>
0016 #include <linux/skbuff.h>
0017 #include <net/pkt_sched.h>
0018 #include <net/sch_generic.h>
0019 #include <net/inet_ecn.h>
0020
0021 /*      SKB Priority Queue
0022  *  =================================
0023  *
0024  * Skbprio (SKB Priority Queue) is a queueing discipline that prioritizes
0025  * packets according to their skb->priority field. Under congestion,
0026  * Skbprio drops already-enqueued lower priority packets to make space
0027  * available for higher priority packets; it was conceived as a solution
0028  * for denial-of-service defenses that need to route packets with different
0029  * priorities as a mean to overcome DoS attacks.
0030  */
0031
0032 struct skbprio_sched_data {
0033     /* Queue state. */
0034     struct sk_buff_head qdiscs[SKBPRIO_MAX_PRIORITY];
0035     struct gnet_stats_queue qstats[SKBPRIO_MAX_PRIORITY];
0036     u16 highest_prio;
0037     u16 lowest_prio;
0038 };
0039
0040 static u16 calc_new_high_prio(const struct skbprio_sched_data *q)
0041 {
0042     int prio;
0043
0044     for (prio = q->highest_prio - 1; prio >= q->lowest_prio; prio--) {
0045         if (!skb_queue_empty(&q->qdiscs[prio]))
0046             return prio;
0047     }
0048
0049     /* SKB queue is empty, return 0 (default highest priority setting). */
0050     return 0;
0051 }
0052
0053 static u16 calc_new_low_prio(const struct skbprio_sched_data *q)
0054 {
0055     int prio;
0056
0057     for (prio = q->lowest_prio + 1; prio <= q->highest_prio; prio++) {
0058         if (!skb_queue_empty(&q->qdiscs[prio]))
0059             return prio;
0060     }
0061
0062     /* SKB queue is empty, return SKBPRIO_MAX_PRIORITY - 1
0063      * (default lowest priority setting).
0064      */
0065     return SKBPRIO_MAX_PRIORITY - 1;
0066 }
0067
0068 static int skbprio_enqueue(struct sk_buff *skb, struct Qdisc *sch,
0069               struct sk_buff **to_free)
0070 {
0071     const unsigned int max_priority = SKBPRIO_MAX_PRIORITY - 1;
0072     struct skbprio_sched_data *q = qdisc_priv(sch);
0073     struct sk_buff_head *qdisc;
0074     struct sk_buff_head *lp_qdisc;
0075     struct sk_buff *to_drop;
0076     u16 prio, lp;
0077
0078     /* Obtain the priority of @skb. */
0079     prio = min(skb->priority, max_priority);
0080
0081     qdisc = &q->qdiscs[prio];
0082     if (sch->q.qlen < sch->limit) {
0083         __skb_queue_tail(qdisc, skb);
0084         qdisc_qstats_backlog_inc(sch, skb);
0085         q->qstats[prio].backlog += qdisc_pkt_len(skb);
0086
0087         /* Check to update highest and lowest priorities. */
0088         if (prio > q->highest_prio)
0089             q->highest_prio = prio;
0090
0091         if (prio < q->lowest_prio)
0092             q->lowest_prio = prio;
0093
0094         sch->q.qlen++;
0095         return NET_XMIT_SUCCESS;
0096     }
0097
0098     /* If this packet has the lowest priority, drop it. */
0099     lp = q->lowest_prio;
0100     if (prio <= lp) {
0101         q->qstats[prio].drops++;
0102         q->qstats[prio].overlimits++;
0103         return qdisc_drop(skb, sch, to_free);
0104     }
0105
0106     __skb_queue_tail(qdisc, skb);
0107     qdisc_qstats_backlog_inc(sch, skb);
0108     q->qstats[prio].backlog += qdisc_pkt_len(skb);
0109
0110     /* Drop the packet at the tail of the lowest priority qdisc. */
0111     lp_qdisc = &q->qdiscs[lp];
0112     to_drop = __skb_dequeue_tail(lp_qdisc);
0113     BUG_ON(!to_drop);
0114     qdisc_qstats_backlog_dec(sch, to_drop);
0115     qdisc_drop(to_drop, sch, to_free);
0116
0117     q->qstats[lp].backlog -= qdisc_pkt_len(to_drop);
0118     q->qstats[lp].drops++;
0119     q->qstats[lp].overlimits++;
0120
0121     /* Check to update highest and lowest priorities. */
0122     if (skb_queue_empty(lp_qdisc)) {
0123         if (q->lowest_prio == q->highest_prio) {
0124             /* The incoming packet is the only packet in queue. */
0125             BUG_ON(sch->q.qlen != 1);
0126             q->lowest_prio = prio;
0127             q->highest_prio = prio;
0128         } else {
0129             q->lowest_prio = calc_new_low_prio(q);
0130         }
0131     }
0132
0133     if (prio > q->highest_prio)
0134         q->highest_prio = prio;
0135
0136     return NET_XMIT_CN;
0137 }
0138
0139 static struct sk_buff *skbprio_dequeue(struct Qdisc *sch)
0140 {
0141     struct skbprio_sched_data *q = qdisc_priv(sch);
0142     struct sk_buff_head *hpq = &q->qdiscs[q->highest_prio];
0143     struct sk_buff *skb = __skb_dequeue(hpq);
0144
0145     if (unlikely(!skb))
0146         return NULL;
0147
0148     sch->q.qlen--;
0149     qdisc_qstats_backlog_dec(sch, skb);
0150     qdisc_bstats_update(sch, skb);
0151
0152     q->qstats[q->highest_prio].backlog -= qdisc_pkt_len(skb);
0153
0154     /* Update highest priority field. */
0155     if (skb_queue_empty(hpq)) {
0156         if (q->lowest_prio == q->highest_prio) {
0157             BUG_ON(sch->q.qlen);
0158             q->highest_prio = 0;
0159             q->lowest_prio = SKBPRIO_MAX_PRIORITY - 1;
0160         } else {
0161             q->highest_prio = calc_new_high_prio(q);
0162         }
0163     }
0164     return skb;
0165 }
0166
0167 static int skbprio_change(struct Qdisc *sch, struct nlattr *opt,
0168             struct netlink_ext_ack *extack)
0169 {
0170     struct tc_skbprio_qopt *ctl = nla_data(opt);
0171
0172     if (opt->nla_len != nla_attr_size(sizeof(*ctl)))
0173         return -EINVAL;
0174
0175     sch->limit = ctl->limit;
0176     return 0;
0177 }
0178
0179 static int skbprio_init(struct Qdisc *sch, struct nlattr *opt,
0180             struct netlink_ext_ack *extack)
0181 {
0182     struct skbprio_sched_data *q = qdisc_priv(sch);
0183     int prio;
0184
0185     /* Initialise all queues, one for each possible priority. */
0186     for (prio = 0; prio < SKBPRIO_MAX_PRIORITY; prio++)
0187         __skb_queue_head_init(&q->qdiscs[prio]);
0188
0189     memset(&q->qstats, 0, sizeof(q->qstats));
0190     q->highest_prio = 0;
0191     q->lowest_prio = SKBPRIO_MAX_PRIORITY - 1;
0192     sch->limit = 64;
0193     if (!opt)
0194         return 0;
0195
0196     return skbprio_change(sch, opt, extack);
0197 }
0198
0199 static int skbprio_dump(struct Qdisc *sch, struct sk_buff *skb)
0200 {
0201     struct tc_skbprio_qopt opt;
0202
0203     opt.limit = sch->limit;
0204
0205     if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt))
0206         return -1;
0207
0208     return skb->len;
0209 }
0210
0211 static void skbprio_reset(struct Qdisc *sch)
0212 {
0213     struct skbprio_sched_data *q = qdisc_priv(sch);
0214     int prio;
0215
0216     sch->qstats.backlog = 0;
0217     sch->q.qlen = 0;
0218
0219     for (prio = 0; prio < SKBPRIO_MAX_PRIORITY; prio++)
0220         __skb_queue_purge(&q->qdiscs[prio]);
0221
0222     memset(&q->qstats, 0, sizeof(q->qstats));
0223     q->highest_prio = 0;
0224     q->lowest_prio = SKBPRIO_MAX_PRIORITY - 1;
0225 }
0226
0227 static void skbprio_destroy(struct Qdisc *sch)
0228 {
0229     struct skbprio_sched_data *q = qdisc_priv(sch);
0230     int prio;
0231
0232     for (prio = 0; prio < SKBPRIO_MAX_PRIORITY; prio++)
0233         __skb_queue_purge(&q->qdiscs[prio]);
0234 }
0235
0236 static struct Qdisc *skbprio_leaf(struct Qdisc *sch, unsigned long arg)
0237 {
0238     return NULL;
0239 }
0240
0241 static unsigned long skbprio_find(struct Qdisc *sch, u32 classid)
0242 {
0243     return 0;
0244 }
0245
0246 static int skbprio_dump_class(struct Qdisc *sch, unsigned long cl,
0247                  struct sk_buff *skb, struct tcmsg *tcm)
0248 {
0249     tcm->tcm_handle |= TC_H_MIN(cl);
0250     return 0;
0251 }
0252
0253 static int skbprio_dump_class_stats(struct Qdisc *sch, unsigned long cl,
0254                    struct gnet_dump *d)
0255 {
0256     struct skbprio_sched_data *q = qdisc_priv(sch);
0257     if (gnet_stats_copy_queue(d, NULL, &q->qstats[cl - 1],
0258         q->qstats[cl - 1].qlen) < 0)
0259         return -1;
0260     return 0;
0261 }
0262
0263 static void skbprio_walk(struct Qdisc *sch, struct qdisc_walker *arg)
0264 {
0265     unsigned int i;
0266
0267     if (arg->stop)
0268         return;
0269
0270     for (i = 0; i < SKBPRIO_MAX_PRIORITY; i++) {
0271         if (arg->count < arg->skip) {
0272             arg->count++;
0273             continue;
0274         }
0275         if (arg->fn(sch, i + 1, arg) < 0) {
0276             arg->stop = 1;
0277             break;
0278         }
0279         arg->count++;
0280     }
0281 }
0282
0283 static const struct Qdisc_class_ops skbprio_class_ops = {
0284     .leaf       =   skbprio_leaf,
0285     .find       =   skbprio_find,
0286     .dump       =   skbprio_dump_class,
0287     .dump_stats =   skbprio_dump_class_stats,
0288     .walk       =   skbprio_walk,
0289 };
0290
0291 static struct Qdisc_ops skbprio_qdisc_ops __read_mostly = {
0292     .cl_ops     =   &skbprio_class_ops,
0293     .id     =   "skbprio",
0294     .priv_size  =   sizeof(struct skbprio_sched_data),
0295     .enqueue    =   skbprio_enqueue,
0296     .dequeue    =   skbprio_dequeue,
0297     .peek       =   qdisc_peek_dequeued,
0298     .init       =   skbprio_init,
0299     .reset      =   skbprio_reset,
0300     .change     =   skbprio_change,
0301     .dump       =   skbprio_dump,
0302     .destroy    =   skbprio_destroy,
0303     .owner      =   THIS_MODULE,
0304 };
0305
0306 static int __init skbprio_module_init(void)
0307 {
0308     return register_qdisc(&skbprio_qdisc_ops);
0309 }
0310
0311 static void __exit skbprio_module_exit(void)
0312 {
0313     unregister_qdisc(&skbprio_qdisc_ops);
0314 }
0315
0316 module_init(skbprio_module_init)
0317 module_exit(skbprio_module_exit)
0318
0319 MODULE_LICENSE("GPL");