net/sched/sch_red.c

   1 /*
   2  * net/sched/sch_red.c  Random Early Detection 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:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  10  *
  11  * Changes:
  12  * J Hadi Salim <hadi@nortel.com> 980914:       computation fixes
  13  * Alexey Makarenko <makar@phoenix.kharkov.ua> 990814: qave on idle link was calculated incorrectly.
  14  * J Hadi Salim <hadi@nortelnetworks.com> 980816:  ECN support
  15  */
  16
  17 #include <linux/config.h>
  18 #include <linux/module.h>
  19 #include <asm/uaccess.h>
  20 #include <asm/system.h>
  21 #include <linux/bitops.h>
  22 #include <linux/types.h>
  23 #include <linux/kernel.h>
  24 #include <linux/sched.h>
  25 #include <linux/string.h>
  26 #include <linux/mm.h>
  27 #include <linux/socket.h>
  28 #include <linux/sockios.h>
  29 #include <linux/in.h>
  30 #include <linux/errno.h>
  31 #include <linux/interrupt.h>
  32 #include <linux/if_ether.h>
  33 #include <linux/inet.h>
  34 #include <linux/netdevice.h>
  35 #include <linux/etherdevice.h>
  36 #include <linux/notifier.h>
  37 #include <net/ip.h>
  38 #include <net/route.h>
  39 #include <linux/skbuff.h>
  40 #include <net/sock.h>
  41 #include <net/pkt_sched.h>
  42 #include <net/inet_ecn.h>
  43 #include <net/dsfield.h>
  44 #include <net/red.h>
  45
  46
  47 /*      Parameters, settable by user:
  48         -----------------------------
  49
  50         limit           - bytes (must be > qth_max + burst)
  51
  52         Hard limit on queue length, should be chosen >qth_max
  53         to allow packet bursts. This parameter does not
  54         affect the algorithms behaviour and can be chosen
  55         arbitrarily high (well, less than ram size)
  56         Really, this limit will never be reached
  57         if RED works correctly.
  58  */
  59
  60 struct red_sched_data
  61 {
  62         u32                     limit;          /* HARD maximal queue length */
  63         unsigned char           flags;
  64         struct red_parms        parms;
  65         struct red_stats        stats;
  66 };
  67
  68 static inline int red_use_ecn(struct red_sched_data *q)
  69 {
  70         return q->flags & TC_RED_ECN;
  71 }
  72
  73 static int
  74 red_enqueue(struct sk_buff *skb, struct Qdisc* sch)
  75 {
  76         struct red_sched_data *q = qdisc_priv(sch);
  77
  78         q->parms.qavg = red_calc_qavg(&q->parms, sch->qstats.backlog);
  79
  80         if (red_is_idling(&q->parms))
  81                 red_end_of_idle_period(&q->parms);
  82
  83         switch (red_action(&q->parms, q->parms.qavg)) {
  84                 case RED_DONT_MARK:
  85                         break;
  86
  87                 case RED_PROB_MARK:
  88                         sch->qstats.overlimits++;
  89                         if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
  90                                 q->stats.prob_drop++;
  91                                 goto congestion_drop;
  92                         }
  93
  94                         q->stats.prob_mark++;
  95                         break;
  96
  97                 case RED_HARD_MARK:
  98                         sch->qstats.overlimits++;
  99                         if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
 100                                 q->stats.forced_drop++;
 101                                 goto congestion_drop;
 102                         }
 103
 104                         q->stats.forced_mark++;
 105                         break;
 106         }
 107
 108         if (sch->qstats.backlog + skb->len <= q->limit)
 109                 return qdisc_enqueue_tail(skb, sch);
 110
 111         q->stats.pdrop++;
 112         return qdisc_drop(skb, sch);
 113
 114 congestion_drop:
 115         qdisc_drop(skb, sch);
 116         return NET_XMIT_CN;
 117 }
 118
 119 static int
 120 red_requeue(struct sk_buff *skb, struct Qdisc* sch)
 121 {
 122         struct red_sched_data *q = qdisc_priv(sch);
 123
 124         if (red_is_idling(&q->parms))
 125                 red_end_of_idle_period(&q->parms);
 126
 127         return qdisc_requeue(skb, sch);
 128 }
 129
 130 static struct sk_buff *
 131 red_dequeue(struct Qdisc* sch)
 132 {
 133         struct sk_buff *skb;
 134         struct red_sched_data *q = qdisc_priv(sch);
 135
 136         skb = qdisc_dequeue_head(sch);
 137
 138         if (skb == NULL && !red_is_idling(&q->parms))
 139                 red_start_of_idle_period(&q->parms);
 140
 141         return skb;
 142 }
 143
 144 static unsigned int red_drop(struct Qdisc* sch)
 145 {
 146         struct sk_buff *skb;
 147         struct red_sched_data *q = qdisc_priv(sch);
 148
 149         skb = qdisc_dequeue_tail(sch);
 150         if (skb) {
 151                 unsigned int len = skb->len;
 152                 q->stats.other++;
 153                 qdisc_drop(skb, sch);
 154                 return len;
 155         }
 156
 157         if (!red_is_idling(&q->parms))
 158                 red_start_of_idle_period(&q->parms);
 159
 160         return 0;
 161 }
 162
 163 static void red_reset(struct Qdisc* sch)
 164 {
 165         struct red_sched_data *q = qdisc_priv(sch);
 166
 167         qdisc_reset_queue(sch);
 168         red_restart(&q->parms);
 169 }
 170
 171 static int red_change(struct Qdisc *sch, struct rtattr *opt)
 172 {
 173         struct red_sched_data *q = qdisc_priv(sch);
 174         struct rtattr *tb[TCA_RED_STAB];
 175         struct tc_red_qopt *ctl;
 176
 177         if (opt == NULL ||
 178             rtattr_parse_nested(tb, TCA_RED_STAB, opt) ||
 179             tb[TCA_RED_PARMS-1] == 0 || tb[TCA_RED_STAB-1] == 0 ||
 180             RTA_PAYLOAD(tb[TCA_RED_PARMS-1]) < sizeof(*ctl) ||
 181             RTA_PAYLOAD(tb[TCA_RED_STAB-1]) < 256)
 182                 return -EINVAL;
 183
 184         ctl = RTA_DATA(tb[TCA_RED_PARMS-1]);
 185
 186         sch_tree_lock(sch);
 187         q->flags = ctl->flags;
 188         q->limit = ctl->limit;
 189
 190         red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
 191                                  ctl->Plog, ctl->Scell_log,
 192                                  RTA_DATA(tb[TCA_RED_STAB-1]));
 193
 194         if (skb_queue_empty(&sch->q))
 195                 red_end_of_idle_period(&q->parms);
 196         sch_tree_unlock(sch);
 197         return 0;
 198 }
 199
 200 static int red_init(struct Qdisc* sch, struct rtattr *opt)
 201 {
 202         return red_change(sch, opt);
 203 }
 204
 205 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
 206 {
 207         struct red_sched_data *q = qdisc_priv(sch);
 208         unsigned char    *b = skb->tail;
 209         struct rtattr *rta;
 210         struct tc_red_qopt opt = {
 211                 .limit          = q->limit,
 212                 .flags          = q->flags,
 213                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
 214                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
 215                 .Wlog           = q->parms.Wlog,
 216                 .Plog           = q->parms.Plog,
 217                 .Scell_log      = q->parms.Scell_log,
 218         };
 219
 220         rta = (struct rtattr*)b;
 221         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
 222         RTA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
 223         rta->rta_len = skb->tail - b;
 224
 225         return skb->len;
 226
 227 rtattr_failure:
 228         skb_trim(skb, b - skb->data);
 229         return -1;
 230 }
 231
 232 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 233 {
 234         struct red_sched_data *q = qdisc_priv(sch);
 235         struct tc_red_xstats st = {
 236                 .early  = q->stats.prob_drop + q->stats.forced_drop,
 237                 .pdrop  = q->stats.pdrop,
 238                 .other  = q->stats.other,
 239                 .marked = q->stats.prob_mark + q->stats.forced_mark,
 240         };
 241
 242         return gnet_stats_copy_app(d, &st, sizeof(st));
 243 }
 244
 245 static struct Qdisc_ops red_qdisc_ops = {
 246         .next           =       NULL,
 247         .cl_ops         =       NULL,
 248         .id             =       "red",
 249         .priv_size      =       sizeof(struct red_sched_data),
 250         .enqueue        =       red_enqueue,
 251         .dequeue        =       red_dequeue,
 252         .requeue        =       red_requeue,
 253         .drop           =       red_drop,
 254         .init           =       red_init,
 255         .reset          =       red_reset,
 256         .change         =       red_change,
 257         .dump           =       red_dump,
 258         .dump_stats     =       red_dump_stats,
 259         .owner          =       THIS_MODULE,
 260 };
 261
 262 static int __init red_module_init(void)
 263 {
 264         return register_qdisc(&red_qdisc_ops);
 265 }
 266 static void __exit red_module_exit(void)
 267 {
 268         unregister_qdisc(&red_qdisc_ops);
 269 }
 270 module_init(red_module_init)
 271 module_exit(red_module_exit)
 272 MODULE_LICENSE("GPL");