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