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/module.h>
  18 #include <linux/types.h>
  19 #include <linux/kernel.h>
  20 #include <linux/skbuff.h>
  21 #include <net/pkt_sched.h>
  22 #include <net/inet_ecn.h>
  23 #include <net/red.h>
  24
  25
  26 /*      Parameters, settable by user:
  27         -----------------------------
  28
  29         limit           - bytes (must be > qth_max + burst)
  30
  31         Hard limit on queue length, should be chosen >qth_max
  32         to allow packet bursts. This parameter does not
  33         affect the algorithms behaviour and can be chosen
  34         arbitrarily high (well, less than ram size)
  35         Really, this limit will never be reached
  36         if RED works correctly.
  37  */
  38
  39 struct red_sched_data {
  40         u32                     limit;          /* HARD maximal queue length */
  41         unsigned char           flags;
  42         struct red_parms        parms;
  43         struct red_stats        stats;
  44         struct Qdisc            *qdisc;
  45 };
  46
  47 static inline int red_use_ecn(struct red_sched_data *q)
  48 {
  49         return q->flags & TC_RED_ECN;
  50 }
  51
  52 static inline int red_use_harddrop(struct red_sched_data *q)
  53 {
  54         return q->flags & TC_RED_HARDDROP;
  55 }
  56
  57 static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch)
  58 {
  59         struct red_sched_data *q = qdisc_priv(sch);
  60         struct Qdisc *child = q->qdisc;
  61         int ret;
  62
  63         q->parms.qavg = red_calc_qavg(&q->parms, child->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         ret = qdisc_enqueue(skb, child);
  95         if (likely(ret == NET_XMIT_SUCCESS)) {
  96                 qdisc_bstats_update(sch, skb);
  97                 sch->q.qlen++;
  98         } else if (net_xmit_drop_count(ret)) {
  99                 q->stats.pdrop++;
 100                 sch->qstats.drops++;
 101         }
 102         return ret;
 103
 104 congestion_drop:
 105         qdisc_drop(skb, sch);
 106         return NET_XMIT_CN;
 107 }
 108
 109 static struct sk_buff *red_dequeue(struct Qdisc *sch)
 110 {
 111         struct sk_buff *skb;
 112         struct red_sched_data *q = qdisc_priv(sch);
 113         struct Qdisc *child = q->qdisc;
 114
 115         skb = child->dequeue(child);
 116         if (skb)
 117                 sch->q.qlen--;
 118         else if (!red_is_idling(&q->parms))
 119                 red_start_of_idle_period(&q->parms);
 120
 121         return skb;
 122 }
 123
 124 static struct sk_buff *red_peek(struct Qdisc *sch)
 125 {
 126         struct red_sched_data *q = qdisc_priv(sch);
 127         struct Qdisc *child = q->qdisc;
 128
 129         return child->ops->peek(child);
 130 }
 131
 132 static unsigned int red_drop(struct Qdisc *sch)
 133 {
 134         struct red_sched_data *q = qdisc_priv(sch);
 135         struct Qdisc *child = q->qdisc;
 136         unsigned int len;
 137
 138         if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
 139                 q->stats.other++;
 140                 sch->qstats.drops++;
 141                 sch->q.qlen--;
 142                 return len;
 143         }
 144
 145         if (!red_is_idling(&q->parms))
 146                 red_start_of_idle_period(&q->parms);
 147
 148         return 0;
 149 }
 150
 151 static void red_reset(struct Qdisc *sch)
 152 {
 153         struct red_sched_data *q = qdisc_priv(sch);
 154
 155         qdisc_reset(q->qdisc);
 156         sch->q.qlen = 0;
 157         red_restart(&q->parms);
 158 }
 159
 160 static void red_destroy(struct Qdisc *sch)
 161 {
 162         struct red_sched_data *q = qdisc_priv(sch);
 163         qdisc_destroy(q->qdisc);
 164 }
 165
 166 static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
 167         [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
 168         [TCA_RED_STAB]  = { .len = RED_STAB_SIZE },
 169 };
 170
 171 static int red_change(struct Qdisc *sch, struct nlattr *opt)
 172 {
 173         struct red_sched_data *q = qdisc_priv(sch);
 174         struct nlattr *tb[TCA_RED_MAX + 1];
 175         struct tc_red_qopt *ctl;
 176         struct Qdisc *child = NULL;
 177         int err;
 178
 179         if (opt == NULL)
 180                 return -EINVAL;
 181
 182         err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
 183         if (err < 0)
 184                 return err;
 185
 186         if (tb[TCA_RED_PARMS] == NULL ||
 187             tb[TCA_RED_STAB] == NULL)
 188                 return -EINVAL;
 189
 190         ctl = nla_data(tb[TCA_RED_PARMS]);
 191
 192         if (ctl->limit > 0) {
 193                 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
 194                 if (IS_ERR(child))
 195                         return PTR_ERR(child);
 196         }
 197
 198         sch_tree_lock(sch);
 199         q->flags = ctl->flags;
 200         q->limit = ctl->limit;
 201         if (child) {
 202                 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
 203                 qdisc_destroy(q->qdisc);
 204                 q->qdisc = child;
 205         }
 206
 207         red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
 208                                  ctl->Plog, ctl->Scell_log,
 209                                  nla_data(tb[TCA_RED_STAB]));
 210
 211         if (skb_queue_empty(&sch->q))
 212                 red_end_of_idle_period(&q->parms);
 213
 214         sch_tree_unlock(sch);
 215         return 0;
 216 }
 217
 218 static int red_init(struct Qdisc *sch, struct nlattr *opt)
 219 {
 220         struct red_sched_data *q = qdisc_priv(sch);
 221
 222         q->qdisc = &noop_qdisc;
 223         return red_change(sch, opt);
 224 }
 225
 226 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
 227 {
 228         struct red_sched_data *q = qdisc_priv(sch);
 229         struct nlattr *opts = NULL;
 230         struct tc_red_qopt opt = {
 231                 .limit          = q->limit,
 232                 .flags          = q->flags,
 233                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
 234                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
 235                 .Wlog           = q->parms.Wlog,
 236                 .Plog           = q->parms.Plog,
 237                 .Scell_log      = q->parms.Scell_log,
 238         };
 239
 240         sch->qstats.backlog = q->qdisc->qstats.backlog;
 241         opts = nla_nest_start(skb, TCA_OPTIONS);
 242         if (opts == NULL)
 243                 goto nla_put_failure;
 244         NLA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
 245         return nla_nest_end(skb, opts);
 246
 247 nla_put_failure:
 248         nla_nest_cancel(skb, opts);
 249         return -EMSGSIZE;
 250 }
 251
 252 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 253 {
 254         struct red_sched_data *q = qdisc_priv(sch);
 255         struct tc_red_xstats st = {
 256                 .early  = q->stats.prob_drop + q->stats.forced_drop,
 257                 .pdrop  = q->stats.pdrop,
 258                 .other  = q->stats.other,
 259                 .marked = q->stats.prob_mark + q->stats.forced_mark,
 260         };
 261
 262         return gnet_stats_copy_app(d, &st, sizeof(st));
 263 }
 264
 265 static int red_dump_class(struct Qdisc *sch, unsigned long cl,
 266                           struct sk_buff *skb, struct tcmsg *tcm)
 267 {
 268         struct red_sched_data *q = qdisc_priv(sch);
 269
 270         tcm->tcm_handle |= TC_H_MIN(1);
 271         tcm->tcm_info = q->qdisc->handle;
 272         return 0;
 273 }
 274
 275 static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 276                      struct Qdisc **old)
 277 {
 278         struct red_sched_data *q = qdisc_priv(sch);
 279
 280         if (new == NULL)
 281                 new = &noop_qdisc;
 282
 283         sch_tree_lock(sch);
 284         *old = q->qdisc;
 285         q->qdisc = new;
 286         qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 287         qdisc_reset(*old);
 288         sch_tree_unlock(sch);
 289         return 0;
 290 }
 291
 292 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
 293 {
 294         struct red_sched_data *q = qdisc_priv(sch);
 295         return q->qdisc;
 296 }
 297
 298 static unsigned long red_get(struct Qdisc *sch, u32 classid)
 299 {
 300         return 1;
 301 }
 302
 303 static void red_put(struct Qdisc *sch, unsigned long arg)
 304 {
 305 }
 306
 307 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 308 {
 309         if (!walker->stop) {
 310                 if (walker->count >= walker->skip)
 311                         if (walker->fn(sch, 1, walker) < 0) {
 312                                 walker->stop = 1;
 313                                 return;
 314                         }
 315                 walker->count++;
 316         }
 317 }
 318
 319 static const struct Qdisc_class_ops red_class_ops = {
 320         .graft          =       red_graft,
 321         .leaf           =       red_leaf,
 322         .get            =       red_get,
 323         .put            =       red_put,
 324         .walk           =       red_walk,
 325         .dump           =       red_dump_class,
 326 };
 327
 328 static struct Qdisc_ops red_qdisc_ops __read_mostly = {
 329         .id             =       "red",
 330         .priv_size      =       sizeof(struct red_sched_data),
 331         .cl_ops         =       &red_class_ops,
 332         .enqueue        =       red_enqueue,
 333         .dequeue        =       red_dequeue,
 334         .peek           =       red_peek,
 335         .drop           =       red_drop,
 336         .init           =       red_init,
 337         .reset          =       red_reset,
 338         .destroy        =       red_destroy,
 339         .change         =       red_change,
 340         .dump           =       red_dump,
 341         .dump_stats     =       red_dump_stats,
 342         .owner          =       THIS_MODULE,
 343 };
 344
 345 static int __init red_module_init(void)
 346 {
 347         return register_qdisc(&red_qdisc_ops);
 348 }
 349
 350 static void __exit red_module_exit(void)
 351 {
 352         unregister_qdisc(&red_qdisc_ops);
 353 }
 354
 355 module_init(red_module_init)
 356 module_exit(red_module_exit)
 357
 358 MODULE_LICENSE("GPL");