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