net/sched/sch_skbprio.c

   1 /*
   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
  36 struct 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
  44 static 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
  57 static 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
  72 static 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
 143 static 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
 171 static 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
 176         if (opt->nla_len != nla_attr_size(sizeof(*ctl)))
 177                 return -EINVAL;
 178
 179         sch->limit = ctl->limit;
 180         return 0;
 181 }
 182
 183 static 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
 203 static 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
 215 static 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
 231 static 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
 240 static struct Qdisc *skbprio_leaf(struct Qdisc *sch, unsigned long arg)
 241 {
 242         return NULL;
 243 }
 244
 245 static unsigned long skbprio_find(struct Qdisc *sch, u32 classid)
 246 {
 247         return 0;
 248 }
 249
 250 static 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
 257 static 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
 267 static 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
 287 static 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
 295 static 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
 310 static int __init skbprio_module_init(void)
 311 {
 312         return register_qdisc(&skbprio_qdisc_ops);
 313 }
 314
 315 static void __exit skbprio_module_exit(void)
 316 {
 317         unregister_qdisc(&skbprio_qdisc_ops);
 318 }
 319
 320 module_init(skbprio_module_init)
 321 module_exit(skbprio_module_exit)
 322
 323 MODULE_LICENSE("GPL");