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 timer_list       adapt_timer;
  43         struct red_parms        parms;
  44         struct red_vars         vars;
  45         struct red_stats        stats;
  46         struct Qdisc            *qdisc;
  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         struct Qdisc *child = q->qdisc;
  63         int ret;
  64
  65         q->vars.qavg = red_calc_qavg(&q->parms,
  66                                      &q->vars,
  67                                      child->qstats.backlog);
  68
  69         if (red_is_idling(&q->vars))
  70                 red_end_of_idle_period(&q->vars);
  71
  72         switch (red_action(&q->parms, &q->vars, q->vars.qavg)) {
  73         case RED_DONT_MARK:
  74                 break;
  75
  76         case RED_PROB_MARK:
  77                 qdisc_qstats_overlimit(sch);
  78                 if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
  79                         q->stats.prob_drop++;
  80                         goto congestion_drop;
  81                 }
  82
  83                 q->stats.prob_mark++;
  84                 break;
  85
  86         case RED_HARD_MARK:
  87                 qdisc_qstats_overlimit(sch);
  88                 if (red_use_harddrop(q) || !red_use_ecn(q) ||
  89                     !INET_ECN_set_ce(skb)) {
  90                         q->stats.forced_drop++;
  91                         goto congestion_drop;
  92                 }
  93
  94                 q->stats.forced_mark++;
  95                 break;
  96         }
  97
  98         ret = qdisc_enqueue(skb, child);
  99         if (likely(ret == NET_XMIT_SUCCESS)) {
 100                 qdisc_qstats_backlog_inc(sch, skb);
 101                 sch->q.qlen++;
 102         } else if (net_xmit_drop_count(ret)) {
 103                 q->stats.pdrop++;
 104                 qdisc_qstats_drop(sch);
 105         }
 106         return ret;
 107
 108 congestion_drop:
 109         qdisc_drop(skb, sch);
 110         return NET_XMIT_CN;
 111 }
 112
 113 static struct sk_buff *red_dequeue(struct Qdisc *sch)
 114 {
 115         struct sk_buff *skb;
 116         struct red_sched_data *q = qdisc_priv(sch);
 117         struct Qdisc *child = q->qdisc;
 118
 119         skb = child->dequeue(child);
 120         if (skb) {
 121                 qdisc_bstats_update(sch, skb);
 122                 qdisc_qstats_backlog_dec(sch, skb);
 123                 sch->q.qlen--;
 124         } else {
 125                 if (!red_is_idling(&q->vars))
 126                         red_start_of_idle_period(&q->vars);
 127         }
 128         return skb;
 129 }
 130
 131 static struct sk_buff *red_peek(struct Qdisc *sch)
 132 {
 133         struct red_sched_data *q = qdisc_priv(sch);
 134         struct Qdisc *child = q->qdisc;
 135
 136         return child->ops->peek(child);
 137 }
 138
 139 static void red_reset(struct Qdisc *sch)
 140 {
 141         struct red_sched_data *q = qdisc_priv(sch);
 142
 143         qdisc_reset(q->qdisc);
 144         sch->qstats.backlog = 0;
 145         sch->q.qlen = 0;
 146         red_restart(&q->vars);
 147 }
 148
 149 static void red_destroy(struct Qdisc *sch)
 150 {
 151         struct red_sched_data *q = qdisc_priv(sch);
 152
 153         del_timer_sync(&q->adapt_timer);
 154         qdisc_destroy(q->qdisc);
 155 }
 156
 157 static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
 158         [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
 159         [TCA_RED_STAB]  = { .len = RED_STAB_SIZE },
 160         [TCA_RED_MAX_P] = { .type = NLA_U32 },
 161 };
 162
 163 static int red_change(struct Qdisc *sch, struct nlattr *opt)
 164 {
 165         struct red_sched_data *q = qdisc_priv(sch);
 166         struct nlattr *tb[TCA_RED_MAX + 1];
 167         struct tc_red_qopt *ctl;
 168         struct Qdisc *child = NULL;
 169         int err;
 170         u32 max_P;
 171
 172         if (opt == NULL)
 173                 return -EINVAL;
 174
 175         err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
 176         if (err < 0)
 177                 return err;
 178
 179         if (tb[TCA_RED_PARMS] == NULL ||
 180             tb[TCA_RED_STAB] == NULL)
 181                 return -EINVAL;
 182
 183         max_P = tb[TCA_RED_MAX_P] ? nla_get_u32(tb[TCA_RED_MAX_P]) : 0;
 184
 185         ctl = nla_data(tb[TCA_RED_PARMS]);
 186
 187         if (ctl->limit > 0) {
 188                 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
 189                 if (IS_ERR(child))
 190                         return PTR_ERR(child);
 191         }
 192
 193         sch_tree_lock(sch);
 194         q->flags = ctl->flags;
 195         q->limit = ctl->limit;
 196         if (child) {
 197                 qdisc_tree_reduce_backlog(q->qdisc, q->qdisc->q.qlen,
 198                                           q->qdisc->qstats.backlog);
 199                 qdisc_destroy(q->qdisc);
 200                 q->qdisc = child;
 201         }
 202
 203         red_set_parms(&q->parms,
 204                       ctl->qth_min, ctl->qth_max, ctl->Wlog,
 205                       ctl->Plog, ctl->Scell_log,
 206                       nla_data(tb[TCA_RED_STAB]),
 207                       max_P);
 208         red_set_vars(&q->vars);
 209
 210         del_timer(&q->adapt_timer);
 211         if (ctl->flags & TC_RED_ADAPTATIVE)
 212                 mod_timer(&q->adapt_timer, jiffies + HZ/2);
 213
 214         if (!q->qdisc->q.qlen)
 215                 red_start_of_idle_period(&q->vars);
 216
 217         sch_tree_unlock(sch);
 218         return 0;
 219 }
 220
 221 static inline void red_adaptative_timer(unsigned long arg)
 222 {
 223         struct Qdisc *sch = (struct Qdisc *)arg;
 224         struct red_sched_data *q = qdisc_priv(sch);
 225         spinlock_t *root_lock = qdisc_lock(qdisc_root_sleeping(sch));
 226
 227         spin_lock(root_lock);
 228         red_adaptative_algo(&q->parms, &q->vars);
 229         mod_timer(&q->adapt_timer, jiffies + HZ/2);
 230         spin_unlock(root_lock);
 231 }
 232
 233 static int red_init(struct Qdisc *sch, struct nlattr *opt)
 234 {
 235         struct red_sched_data *q = qdisc_priv(sch);
 236
 237         q->qdisc = &noop_qdisc;
 238         setup_timer(&q->adapt_timer, red_adaptative_timer, (unsigned long)sch);
 239         return red_change(sch, opt);
 240 }
 241
 242 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
 243 {
 244         struct red_sched_data *q = qdisc_priv(sch);
 245         struct nlattr *opts = NULL;
 246         struct tc_red_qopt opt = {
 247                 .limit          = q->limit,
 248                 .flags          = q->flags,
 249                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
 250                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
 251                 .Wlog           = q->parms.Wlog,
 252                 .Plog           = q->parms.Plog,
 253                 .Scell_log      = q->parms.Scell_log,
 254         };
 255
 256         sch->qstats.backlog = q->qdisc->qstats.backlog;
 257         opts = nla_nest_start(skb, TCA_OPTIONS);
 258         if (opts == NULL)
 259                 goto nla_put_failure;
 260         if (nla_put(skb, TCA_RED_PARMS, sizeof(opt), &opt) ||
 261             nla_put_u32(skb, TCA_RED_MAX_P, q->parms.max_P))
 262                 goto nla_put_failure;
 263         return nla_nest_end(skb, opts);
 264
 265 nla_put_failure:
 266         nla_nest_cancel(skb, opts);
 267         return -EMSGSIZE;
 268 }
 269
 270 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 271 {
 272         struct red_sched_data *q = qdisc_priv(sch);
 273         struct tc_red_xstats st = {
 274                 .early  = q->stats.prob_drop + q->stats.forced_drop,
 275                 .pdrop  = q->stats.pdrop,
 276                 .other  = q->stats.other,
 277                 .marked = q->stats.prob_mark + q->stats.forced_mark,
 278         };
 279
 280         return gnet_stats_copy_app(d, &st, sizeof(st));
 281 }
 282
 283 static int red_dump_class(struct Qdisc *sch, unsigned long cl,
 284                           struct sk_buff *skb, struct tcmsg *tcm)
 285 {
 286         struct red_sched_data *q = qdisc_priv(sch);
 287
 288         tcm->tcm_handle |= TC_H_MIN(1);
 289         tcm->tcm_info = q->qdisc->handle;
 290         return 0;
 291 }
 292
 293 static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 294                      struct Qdisc **old)
 295 {
 296         struct red_sched_data *q = qdisc_priv(sch);
 297
 298         if (new == NULL)
 299                 new = &noop_qdisc;
 300
 301         *old = qdisc_replace(sch, new, &q->qdisc);
 302         return 0;
 303 }
 304
 305 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
 306 {
 307         struct red_sched_data *q = qdisc_priv(sch);
 308         return q->qdisc;
 309 }
 310
 311 static unsigned long red_get(struct Qdisc *sch, u32 classid)
 312 {
 313         return 1;
 314 }
 315
 316 static void red_put(struct Qdisc *sch, unsigned long arg)
 317 {
 318 }
 319
 320 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 321 {
 322         if (!walker->stop) {
 323                 if (walker->count >= walker->skip)
 324                         if (walker->fn(sch, 1, walker) < 0) {
 325                                 walker->stop = 1;
 326                                 return;
 327                         }
 328                 walker->count++;
 329         }
 330 }
 331
 332 static const struct Qdisc_class_ops red_class_ops = {
 333         .graft          =       red_graft,
 334         .leaf           =       red_leaf,
 335         .get            =       red_get,
 336         .put            =       red_put,
 337         .walk           =       red_walk,
 338         .dump           =       red_dump_class,
 339 };
 340
 341 static struct Qdisc_ops red_qdisc_ops __read_mostly = {
 342         .id             =       "red",
 343         .priv_size      =       sizeof(struct red_sched_data),
 344         .cl_ops         =       &red_class_ops,
 345         .enqueue        =       red_enqueue,
 346         .dequeue        =       red_dequeue,
 347         .peek           =       red_peek,
 348         .init           =       red_init,
 349         .reset          =       red_reset,
 350         .destroy        =       red_destroy,
 351         .change         =       red_change,
 352         .dump           =       red_dump,
 353         .dump_stats     =       red_dump_stats,
 354         .owner          =       THIS_MODULE,
 355 };
 356
 357 static int __init red_module_init(void)
 358 {
 359         return register_qdisc(&red_qdisc_ops);
 360 }
 361
 362 static void __exit red_module_exit(void)
 363 {
 364         unregister_qdisc(&red_qdisc_ops);
 365 }
 366
 367 module_init(red_module_init)
 368 module_exit(red_module_exit)
 369
 370 MODULE_LICENSE("GPL");