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