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 unsigned int red_drop(struct Qdisc *sch)
 140 {
 141         struct red_sched_data *q = qdisc_priv(sch);
 142         struct Qdisc *child = q->qdisc;
 143         unsigned int len;
 144
 145         if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
 146                 q->stats.other++;
 147                 qdisc_qstats_drop(sch);
 148                 sch->qstats.backlog -= len;
 149                 sch->q.qlen--;
 150                 return len;
 151         }
 152
 153         if (!red_is_idling(&q->vars))
 154                 red_start_of_idle_period(&q->vars);
 155
 156         return 0;
 157 }
 158
 159 static void red_reset(struct Qdisc *sch)
 160 {
 161         struct red_sched_data *q = qdisc_priv(sch);
 162
 163         qdisc_reset(q->qdisc);
 164         sch->qstats.backlog = 0;
 165         sch->q.qlen = 0;
 166         red_restart(&q->vars);
 167 }
 168
 169 static void red_destroy(struct Qdisc *sch)
 170 {
 171         struct red_sched_data *q = qdisc_priv(sch);
 172
 173         del_timer_sync(&q->adapt_timer);
 174         qdisc_destroy(q->qdisc);
 175 }
 176
 177 static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
 178         [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
 179         [TCA_RED_STAB]  = { .len = RED_STAB_SIZE },
 180         [TCA_RED_MAX_P] = { .type = NLA_U32 },
 181 };
 182
 183 static int red_change(struct Qdisc *sch, struct nlattr *opt)
 184 {
 185         struct red_sched_data *q = qdisc_priv(sch);
 186         struct nlattr *tb[TCA_RED_MAX + 1];
 187         struct tc_red_qopt *ctl;
 188         struct Qdisc *child = NULL;
 189         int err;
 190         u32 max_P;
 191
 192         if (opt == NULL)
 193                 return -EINVAL;
 194
 195         err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
 196         if (err < 0)
 197                 return err;
 198
 199         if (tb[TCA_RED_PARMS] == NULL ||
 200             tb[TCA_RED_STAB] == NULL)
 201                 return -EINVAL;
 202
 203         max_P = tb[TCA_RED_MAX_P] ? nla_get_u32(tb[TCA_RED_MAX_P]) : 0;
 204
 205         ctl = nla_data(tb[TCA_RED_PARMS]);
 206
 207         if (ctl->limit > 0) {
 208                 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
 209                 if (IS_ERR(child))
 210                         return PTR_ERR(child);
 211         }
 212
 213         sch_tree_lock(sch);
 214         q->flags = ctl->flags;
 215         q->limit = ctl->limit;
 216         if (child) {
 217                 qdisc_tree_reduce_backlog(q->qdisc, q->qdisc->q.qlen,
 218                                           q->qdisc->qstats.backlog);
 219                 qdisc_destroy(q->qdisc);
 220                 q->qdisc = child;
 221         }
 222
 223         red_set_parms(&q->parms,
 224                       ctl->qth_min, ctl->qth_max, ctl->Wlog,
 225                       ctl->Plog, ctl->Scell_log,
 226                       nla_data(tb[TCA_RED_STAB]),
 227                       max_P);
 228         red_set_vars(&q->vars);
 229
 230         del_timer(&q->adapt_timer);
 231         if (ctl->flags & TC_RED_ADAPTATIVE)
 232                 mod_timer(&q->adapt_timer, jiffies + HZ/2);
 233
 234         if (!q->qdisc->q.qlen)
 235                 red_start_of_idle_period(&q->vars);
 236
 237         sch_tree_unlock(sch);
 238         return 0;
 239 }
 240
 241 static inline void red_adaptative_timer(unsigned long arg)
 242 {
 243         struct Qdisc *sch = (struct Qdisc *)arg;
 244         struct red_sched_data *q = qdisc_priv(sch);
 245         spinlock_t *root_lock = qdisc_lock(qdisc_root_sleeping(sch));
 246
 247         spin_lock(root_lock);
 248         red_adaptative_algo(&q->parms, &q->vars);
 249         mod_timer(&q->adapt_timer, jiffies + HZ/2);
 250         spin_unlock(root_lock);
 251 }
 252
 253 static int red_init(struct Qdisc *sch, struct nlattr *opt)
 254 {
 255         struct red_sched_data *q = qdisc_priv(sch);
 256
 257         q->qdisc = &noop_qdisc;
 258         setup_timer(&q->adapt_timer, red_adaptative_timer, (unsigned long)sch);
 259         return red_change(sch, opt);
 260 }
 261
 262 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
 263 {
 264         struct red_sched_data *q = qdisc_priv(sch);
 265         struct nlattr *opts = NULL;
 266         struct tc_red_qopt opt = {
 267                 .limit          = q->limit,
 268                 .flags          = q->flags,
 269                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
 270                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
 271                 .Wlog           = q->parms.Wlog,
 272                 .Plog           = q->parms.Plog,
 273                 .Scell_log      = q->parms.Scell_log,
 274         };
 275
 276         sch->qstats.backlog = q->qdisc->qstats.backlog;
 277         opts = nla_nest_start(skb, TCA_OPTIONS);
 278         if (opts == NULL)
 279                 goto nla_put_failure;
 280         if (nla_put(skb, TCA_RED_PARMS, sizeof(opt), &opt) ||
 281             nla_put_u32(skb, TCA_RED_MAX_P, q->parms.max_P))
 282                 goto nla_put_failure;
 283         return nla_nest_end(skb, opts);
 284
 285 nla_put_failure:
 286         nla_nest_cancel(skb, opts);
 287         return -EMSGSIZE;
 288 }
 289
 290 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 291 {
 292         struct red_sched_data *q = qdisc_priv(sch);
 293         struct tc_red_xstats st = {
 294                 .early  = q->stats.prob_drop + q->stats.forced_drop,
 295                 .pdrop  = q->stats.pdrop,
 296                 .other  = q->stats.other,
 297                 .marked = q->stats.prob_mark + q->stats.forced_mark,
 298         };
 299
 300         return gnet_stats_copy_app(d, &st, sizeof(st));
 301 }
 302
 303 static int red_dump_class(struct Qdisc *sch, unsigned long cl,
 304                           struct sk_buff *skb, struct tcmsg *tcm)
 305 {
 306         struct red_sched_data *q = qdisc_priv(sch);
 307
 308         tcm->tcm_handle |= TC_H_MIN(1);
 309         tcm->tcm_info = q->qdisc->handle;
 310         return 0;
 311 }
 312
 313 static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 314                      struct Qdisc **old)
 315 {
 316         struct red_sched_data *q = qdisc_priv(sch);
 317
 318         if (new == NULL)
 319                 new = &noop_qdisc;
 320
 321         *old = qdisc_replace(sch, new, &q->qdisc);
 322         return 0;
 323 }
 324
 325 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
 326 {
 327         struct red_sched_data *q = qdisc_priv(sch);
 328         return q->qdisc;
 329 }
 330
 331 static unsigned long red_get(struct Qdisc *sch, u32 classid)
 332 {
 333         return 1;
 334 }
 335
 336 static void red_put(struct Qdisc *sch, unsigned long arg)
 337 {
 338 }
 339
 340 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 341 {
 342         if (!walker->stop) {
 343                 if (walker->count >= walker->skip)
 344                         if (walker->fn(sch, 1, walker) < 0) {
 345                                 walker->stop = 1;
 346                                 return;
 347                         }
 348                 walker->count++;
 349         }
 350 }
 351
 352 static const struct Qdisc_class_ops red_class_ops = {
 353         .graft          =       red_graft,
 354         .leaf           =       red_leaf,
 355         .get            =       red_get,
 356         .put            =       red_put,
 357         .walk           =       red_walk,
 358         .dump           =       red_dump_class,
 359 };
 360
 361 static struct Qdisc_ops red_qdisc_ops __read_mostly = {
 362         .id             =       "red",
 363         .priv_size      =       sizeof(struct red_sched_data),
 364         .cl_ops         =       &red_class_ops,
 365         .enqueue        =       red_enqueue,
 366         .dequeue        =       red_dequeue,
 367         .peek           =       red_peek,
 368         .drop           =       red_drop,
 369         .init           =       red_init,
 370         .reset          =       red_reset,
 371         .destroy        =       red_destroy,
 372         .change         =       red_change,
 373         .dump           =       red_dump,
 374         .dump_stats     =       red_dump_stats,
 375         .owner          =       THIS_MODULE,
 376 };
 377
 378 static int __init red_module_init(void)
 379 {
 380         return register_qdisc(&red_qdisc_ops);
 381 }
 382
 383 static void __exit red_module_exit(void)
 384 {
 385         unregister_qdisc(&red_qdisc_ops);
 386 }
 387
 388 module_init(red_module_init)
 389 module_exit(red_module_exit)
 390
 391 MODULE_LICENSE("GPL");