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