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 {
  41         u32                     limit;          /* HARD maximal queue length */
  42         unsigned char           flags;
  43         struct red_parms        parms;
  44         struct red_stats        stats;
  45         struct Qdisc            *qdisc;
  46 };
  47
  48 static inline int red_use_ecn(struct red_sched_data *q)
  49 {
  50         return q->flags & TC_RED_ECN;
  51 }
  52
  53 static inline int red_use_harddrop(struct red_sched_data *q)
  54 {
  55         return q->flags & TC_RED_HARDDROP;
  56 }
  57
  58 static int red_enqueue(struct sk_buff *skb, struct Qdisc* sch)
  59 {
  60         struct red_sched_data *q = qdisc_priv(sch);
  61         struct Qdisc *child = q->qdisc;
  62         int ret;
  63
  64         q->parms.qavg = red_calc_qavg(&q->parms, child->qstats.backlog);
  65
  66         if (red_is_idling(&q->parms))
  67                 red_end_of_idle_period(&q->parms);
  68
  69         switch (red_action(&q->parms, q->parms.qavg)) {
  70                 case RED_DONT_MARK:
  71                         break;
  72
  73                 case RED_PROB_MARK:
  74                         sch->qstats.overlimits++;
  75                         if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
  76                                 q->stats.prob_drop++;
  77                                 goto congestion_drop;
  78                         }
  79
  80                         q->stats.prob_mark++;
  81                         break;
  82
  83                 case RED_HARD_MARK:
  84                         sch->qstats.overlimits++;
  85                         if (red_use_harddrop(q) || !red_use_ecn(q) ||
  86                             !INET_ECN_set_ce(skb)) {
  87                                 q->stats.forced_drop++;
  88                                 goto congestion_drop;
  89                         }
  90
  91                         q->stats.forced_mark++;
  92                         break;
  93         }
  94
  95         ret = child->enqueue(skb, child);
  96         if (likely(ret == NET_XMIT_SUCCESS)) {
  97                 sch->bstats.bytes += skb->len;
  98                 sch->bstats.packets++;
  99                 sch->q.qlen++;
 100         } else {
 101                 q->stats.pdrop++;
 102                 sch->qstats.drops++;
 103         }
 104         return ret;
 105
 106 congestion_drop:
 107         qdisc_drop(skb, sch);
 108         return NET_XMIT_CN;
 109 }
 110
 111 static int red_requeue(struct sk_buff *skb, struct Qdisc* sch)
 112 {
 113         struct red_sched_data *q = qdisc_priv(sch);
 114         struct Qdisc *child = q->qdisc;
 115         int ret;
 116
 117         if (red_is_idling(&q->parms))
 118                 red_end_of_idle_period(&q->parms);
 119
 120         ret = child->ops->requeue(skb, child);
 121         if (likely(ret == NET_XMIT_SUCCESS)) {
 122                 sch->qstats.requeues++;
 123                 sch->q.qlen++;
 124         }
 125         return ret;
 126 }
 127
 128 static struct sk_buff * red_dequeue(struct Qdisc* sch)
 129 {
 130         struct sk_buff *skb;
 131         struct red_sched_data *q = qdisc_priv(sch);
 132         struct Qdisc *child = q->qdisc;
 133
 134         skb = child->dequeue(child);
 135         if (skb)
 136                 sch->q.qlen--;
 137         else if (!red_is_idling(&q->parms))
 138                 red_start_of_idle_period(&q->parms);
 139
 140         return skb;
 141 }
 142
 143 static unsigned int red_drop(struct Qdisc* sch)
 144 {
 145         struct red_sched_data *q = qdisc_priv(sch);
 146         struct Qdisc *child = q->qdisc;
 147         unsigned int len;
 148
 149         if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
 150                 q->stats.other++;
 151                 sch->qstats.drops++;
 152                 sch->q.qlen--;
 153                 return len;
 154         }
 155
 156         if (!red_is_idling(&q->parms))
 157                 red_start_of_idle_period(&q->parms);
 158
 159         return 0;
 160 }
 161
 162 static void red_reset(struct Qdisc* sch)
 163 {
 164         struct red_sched_data *q = qdisc_priv(sch);
 165
 166         qdisc_reset(q->qdisc);
 167         sch->q.qlen = 0;
 168         red_restart(&q->parms);
 169 }
 170
 171 static void red_destroy(struct Qdisc *sch)
 172 {
 173         struct red_sched_data *q = qdisc_priv(sch);
 174         qdisc_destroy(q->qdisc);
 175 }
 176
 177 static struct Qdisc *red_create_dflt(struct Qdisc *sch, u32 limit)
 178 {
 179         struct Qdisc *q;
 180         struct nlattr *nla;
 181         int ret;
 182
 183         q = qdisc_create_dflt(sch->dev, &bfifo_qdisc_ops,
 184                               TC_H_MAKE(sch->handle, 1));
 185         if (q) {
 186                 nla = kmalloc(nla_attr_size(sizeof(struct tc_fifo_qopt)),
 187                               GFP_KERNEL);
 188                 if (nla) {
 189                         nla->nla_type = RTM_NEWQDISC;
 190                         nla->nla_len = nla_attr_size(sizeof(struct tc_fifo_qopt));
 191                         ((struct tc_fifo_qopt *)nla_data(nla))->limit = limit;
 192
 193                         ret = q->ops->change(q, nla);
 194                         kfree(nla);
 195
 196                         if (ret == 0)
 197                                 return q;
 198                 }
 199                 qdisc_destroy(q);
 200         }
 201         return NULL;
 202 }
 203
 204 static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
 205         [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
 206         [TCA_RED_STAB]  = { .len = RED_STAB_SIZE },
 207 };
 208
 209 static int red_change(struct Qdisc *sch, struct nlattr *opt)
 210 {
 211         struct red_sched_data *q = qdisc_priv(sch);
 212         struct nlattr *tb[TCA_RED_MAX + 1];
 213         struct tc_red_qopt *ctl;
 214         struct Qdisc *child = NULL;
 215         int err;
 216
 217         if (opt == NULL)
 218                 return -EINVAL;
 219
 220         err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
 221         if (err < 0)
 222                 return err;
 223
 224         if (tb[TCA_RED_PARMS] == NULL ||
 225             tb[TCA_RED_STAB] == NULL)
 226                 return -EINVAL;
 227
 228         ctl = nla_data(tb[TCA_RED_PARMS]);
 229
 230         if (ctl->limit > 0) {
 231                 child = red_create_dflt(sch, ctl->limit);
 232                 if (child == NULL)
 233                         return -ENOMEM;
 234         }
 235
 236         sch_tree_lock(sch);
 237         q->flags = ctl->flags;
 238         q->limit = ctl->limit;
 239         if (child) {
 240                 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
 241                 qdisc_destroy(xchg(&q->qdisc, child));
 242         }
 243
 244         red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
 245                                  ctl->Plog, ctl->Scell_log,
 246                                  nla_data(tb[TCA_RED_STAB]));
 247
 248         if (skb_queue_empty(&sch->q))
 249                 red_end_of_idle_period(&q->parms);
 250
 251         sch_tree_unlock(sch);
 252         return 0;
 253 }
 254
 255 static int red_init(struct Qdisc* sch, struct nlattr *opt)
 256 {
 257         struct red_sched_data *q = qdisc_priv(sch);
 258
 259         q->qdisc = &noop_qdisc;
 260         return red_change(sch, opt);
 261 }
 262
 263 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
 264 {
 265         struct red_sched_data *q = qdisc_priv(sch);
 266         struct nlattr *opts = NULL;
 267         struct tc_red_qopt opt = {
 268                 .limit          = q->limit,
 269                 .flags          = q->flags,
 270                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
 271                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
 272                 .Wlog           = q->parms.Wlog,
 273                 .Plog           = q->parms.Plog,
 274                 .Scell_log      = q->parms.Scell_log,
 275         };
 276
 277         opts = nla_nest_start(skb, TCA_OPTIONS);
 278         if (opts == NULL)
 279                 goto nla_put_failure;
 280         NLA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
 281         return nla_nest_end(skb, opts);
 282
 283 nla_put_failure:
 284         nla_nest_cancel(skb, opts);
 285         return -EMSGSIZE;
 286 }
 287
 288 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 289 {
 290         struct red_sched_data *q = qdisc_priv(sch);
 291         struct tc_red_xstats st = {
 292                 .early  = q->stats.prob_drop + q->stats.forced_drop,
 293                 .pdrop  = q->stats.pdrop,
 294                 .other  = q->stats.other,
 295                 .marked = q->stats.prob_mark + q->stats.forced_mark,
 296         };
 297
 298         return gnet_stats_copy_app(d, &st, sizeof(st));
 299 }
 300
 301 static int red_dump_class(struct Qdisc *sch, unsigned long cl,
 302                           struct sk_buff *skb, struct tcmsg *tcm)
 303 {
 304         struct red_sched_data *q = qdisc_priv(sch);
 305
 306         if (cl != 1)
 307                 return -ENOENT;
 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         sch_tree_lock(sch);
 322         *old = xchg(&q->qdisc, new);
 323         qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 324         qdisc_reset(*old);
 325         sch_tree_unlock(sch);
 326         return 0;
 327 }
 328
 329 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
 330 {
 331         struct red_sched_data *q = qdisc_priv(sch);
 332         return q->qdisc;
 333 }
 334
 335 static unsigned long red_get(struct Qdisc *sch, u32 classid)
 336 {
 337         return 1;
 338 }
 339
 340 static void red_put(struct Qdisc *sch, unsigned long arg)
 341 {
 342         return;
 343 }
 344
 345 static int red_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
 346                             struct nlattr **tca, unsigned long *arg)
 347 {
 348         return -ENOSYS;
 349 }
 350
 351 static int red_delete(struct Qdisc *sch, unsigned long cl)
 352 {
 353         return -ENOSYS;
 354 }
 355
 356 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 357 {
 358         if (!walker->stop) {
 359                 if (walker->count >= walker->skip)
 360                         if (walker->fn(sch, 1, walker) < 0) {
 361                                 walker->stop = 1;
 362                                 return;
 363                         }
 364                 walker->count++;
 365         }
 366 }
 367
 368 static struct tcf_proto **red_find_tcf(struct Qdisc *sch, unsigned long cl)
 369 {
 370         return NULL;
 371 }
 372
 373 static const struct Qdisc_class_ops red_class_ops = {
 374         .graft          =       red_graft,
 375         .leaf           =       red_leaf,
 376         .get            =       red_get,
 377         .put            =       red_put,
 378         .change         =       red_change_class,
 379         .delete         =       red_delete,
 380         .walk           =       red_walk,
 381         .tcf_chain      =       red_find_tcf,
 382         .dump           =       red_dump_class,
 383 };
 384
 385 static struct Qdisc_ops red_qdisc_ops __read_mostly = {
 386         .id             =       "red",
 387         .priv_size      =       sizeof(struct red_sched_data),
 388         .cl_ops         =       &red_class_ops,
 389         .enqueue        =       red_enqueue,
 390         .dequeue        =       red_dequeue,
 391         .requeue        =       red_requeue,
 392         .drop           =       red_drop,
 393         .init           =       red_init,
 394         .reset          =       red_reset,
 395         .destroy        =       red_destroy,
 396         .change         =       red_change,
 397         .dump           =       red_dump,
 398         .dump_stats     =       red_dump_stats,
 399         .owner          =       THIS_MODULE,
 400 };
 401
 402 static int __init red_module_init(void)
 403 {
 404         return register_qdisc(&red_qdisc_ops);
 405 }
 406
 407 static void __exit red_module_exit(void)
 408 {
 409         unregister_qdisc(&red_qdisc_ops);
 410 }
 411
 412 module_init(red_module_init)
 413 module_exit(red_module_exit)
 414
 415 MODULE_LICENSE("GPL");