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, <[email protected]>
  10  *
  11  * Changes:
  12  * J Hadi Salim 980914: computation fixes
  13  * Alexey Makarenko <[email protected]> 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/pkt_cls.h>
  23 #include <net/inet_ecn.h>
  24 #include <net/red.h>
  25
  26
  27 /*      Parameters, settable by user:
  28         -----------------------------
  29
  30         limit           - bytes (must be > qth_max + burst)
  31
  32         Hard limit on queue length, should be chosen >qth_max
  33         to allow packet bursts. This parameter does not
  34         affect the algorithms behaviour and can be chosen
  35         arbitrarily high (well, less than ram size)
  36         Really, this limit will never be reached
  37         if RED works correctly.
  38  */
  39
  40 struct red_sched_data {
  41         u32                     limit;          /* HARD maximal queue length */
  42         unsigned char           flags;
  43         struct timer_list       adapt_timer;
  44         struct Qdisc            *sch;
  45         struct red_parms        parms;
  46         struct red_vars         vars;
  47         struct red_stats        stats;
  48         struct Qdisc            *qdisc;
  49 };
  50
  51 static inline int red_use_ecn(struct red_sched_data *q)
  52 {
  53         return q->flags & TC_RED_ECN;
  54 }
  55
  56 static inline int red_use_harddrop(struct red_sched_data *q)
  57 {
  58         return q->flags & TC_RED_HARDDROP;
  59 }
  60
  61 static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch,
  62                        struct sk_buff **to_free)
  63 {
  64         struct red_sched_data *q = qdisc_priv(sch);
  65         struct Qdisc *child = q->qdisc;
  66         int ret;
  67
  68         q->vars.qavg = red_calc_qavg(&q->parms,
  69                                      &q->vars,
  70                                      child->qstats.backlog);
  71
  72         if (red_is_idling(&q->vars))
  73                 red_end_of_idle_period(&q->vars);
  74
  75         switch (red_action(&q->parms, &q->vars, q->vars.qavg)) {
  76         case RED_DONT_MARK:
  77                 break;
  78
  79         case RED_PROB_MARK:
  80                 qdisc_qstats_overlimit(sch);
  81                 if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
  82                         q->stats.prob_drop++;
  83                         goto congestion_drop;
  84                 }
  85
  86                 q->stats.prob_mark++;
  87                 break;
  88
  89         case RED_HARD_MARK:
  90                 qdisc_qstats_overlimit(sch);
  91                 if (red_use_harddrop(q) || !red_use_ecn(q) ||
  92                     !INET_ECN_set_ce(skb)) {
  93                         q->stats.forced_drop++;
  94                         goto congestion_drop;
  95                 }
  96
  97                 q->stats.forced_mark++;
  98                 break;
  99         }
 100
 101         ret = qdisc_enqueue(skb, child, to_free);
 102         if (likely(ret == NET_XMIT_SUCCESS)) {
 103                 qdisc_qstats_backlog_inc(sch, skb);
 104                 sch->q.qlen++;
 105         } else if (net_xmit_drop_count(ret)) {
 106                 q->stats.pdrop++;
 107                 qdisc_qstats_drop(sch);
 108         }
 109         return ret;
 110
 111 congestion_drop:
 112         qdisc_drop(skb, sch, to_free);
 113         return NET_XMIT_CN;
 114 }
 115
 116 static struct sk_buff *red_dequeue(struct Qdisc *sch)
 117 {
 118         struct sk_buff *skb;
 119         struct red_sched_data *q = qdisc_priv(sch);
 120         struct Qdisc *child = q->qdisc;
 121
 122         skb = child->dequeue(child);
 123         if (skb) {
 124                 qdisc_bstats_update(sch, skb);
 125                 qdisc_qstats_backlog_dec(sch, skb);
 126                 sch->q.qlen--;
 127         } else {
 128                 if (!red_is_idling(&q->vars))
 129                         red_start_of_idle_period(&q->vars);
 130         }
 131         return skb;
 132 }
 133
 134 static struct sk_buff *red_peek(struct Qdisc *sch)
 135 {
 136         struct red_sched_data *q = qdisc_priv(sch);
 137         struct Qdisc *child = q->qdisc;
 138
 139         return child->ops->peek(child);
 140 }
 141
 142 static void red_reset(struct Qdisc *sch)
 143 {
 144         struct red_sched_data *q = qdisc_priv(sch);
 145
 146         qdisc_reset(q->qdisc);
 147         sch->qstats.backlog = 0;
 148         sch->q.qlen = 0;
 149         red_restart(&q->vars);
 150 }
 151
 152 static int red_offload(struct Qdisc *sch, bool enable)
 153 {
 154         struct red_sched_data *q = qdisc_priv(sch);
 155         struct net_device *dev = qdisc_dev(sch);
 156         struct tc_red_qopt_offload opt = {
 157                 .handle = sch->handle,
 158                 .parent = sch->parent,
 159         };
 160
 161         if (!tc_can_offload(dev) || !dev->netdev_ops->ndo_setup_tc)
 162                 return -EOPNOTSUPP;
 163
 164         if (enable) {
 165                 opt.command = TC_RED_REPLACE;
 166                 opt.set.min = q->parms.qth_min >> q->parms.Wlog;
 167                 opt.set.max = q->parms.qth_max >> q->parms.Wlog;
 168                 opt.set.probability = q->parms.max_P;
 169                 opt.set.is_ecn = red_use_ecn(q);
 170                 opt.set.qstats = &sch->qstats;
 171         } else {
 172                 opt.command = TC_RED_DESTROY;
 173         }
 174
 175         return dev->netdev_ops->ndo_setup_tc(dev, TC_SETUP_QDISC_RED, &opt);
 176 }
 177
 178 static void red_destroy(struct Qdisc *sch)
 179 {
 180         struct red_sched_data *q = qdisc_priv(sch);
 181
 182         del_timer_sync(&q->adapt_timer);
 183         red_offload(sch, false);
 184         qdisc_destroy(q->qdisc);
 185 }
 186
 187 static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
 188         [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
 189         [TCA_RED_STAB]  = { .len = RED_STAB_SIZE },
 190         [TCA_RED_MAX_P] = { .type = NLA_U32 },
 191 };
 192
 193 static int red_change(struct Qdisc *sch, struct nlattr *opt,
 194                       struct netlink_ext_ack *extack)
 195 {
 196         struct red_sched_data *q = qdisc_priv(sch);
 197         struct nlattr *tb[TCA_RED_MAX + 1];
 198         struct tc_red_qopt *ctl;
 199         struct Qdisc *child = NULL;
 200         int err;
 201         u32 max_P;
 202
 203         if (opt == NULL)
 204                 return -EINVAL;
 205
 206         err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy, NULL);
 207         if (err < 0)
 208                 return err;
 209
 210         if (tb[TCA_RED_PARMS] == NULL ||
 211             tb[TCA_RED_STAB] == NULL)
 212                 return -EINVAL;
 213
 214         max_P = tb[TCA_RED_MAX_P] ? nla_get_u32(tb[TCA_RED_MAX_P]) : 0;
 215
 216         ctl = nla_data(tb[TCA_RED_PARMS]);
 217         if (!red_check_params(ctl->qth_min, ctl->qth_max, ctl->Wlog))
 218                 return -EINVAL;
 219
 220         if (ctl->limit > 0) {
 221                 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit,
 222                                          extack);
 223                 if (IS_ERR(child))
 224                         return PTR_ERR(child);
 225         }
 226
 227         if (child != &noop_qdisc)
 228                 qdisc_hash_add(child, true);
 229         sch_tree_lock(sch);
 230         q->flags = ctl->flags;
 231         q->limit = ctl->limit;
 232         if (child) {
 233                 qdisc_tree_reduce_backlog(q->qdisc, q->qdisc->q.qlen,
 234                                           q->qdisc->qstats.backlog);
 235                 qdisc_destroy(q->qdisc);
 236                 q->qdisc = child;
 237         }
 238
 239         red_set_parms(&q->parms,
 240                       ctl->qth_min, ctl->qth_max, ctl->Wlog,
 241                       ctl->Plog, ctl->Scell_log,
 242                       nla_data(tb[TCA_RED_STAB]),
 243                       max_P);
 244         red_set_vars(&q->vars);
 245
 246         del_timer(&q->adapt_timer);
 247         if (ctl->flags & TC_RED_ADAPTATIVE)
 248                 mod_timer(&q->adapt_timer, jiffies + HZ/2);
 249
 250         if (!q->qdisc->q.qlen)
 251                 red_start_of_idle_period(&q->vars);
 252
 253         sch_tree_unlock(sch);
 254         red_offload(sch, true);
 255         return 0;
 256 }
 257
 258 static inline void red_adaptative_timer(struct timer_list *t)
 259 {
 260         struct red_sched_data *q = from_timer(q, t, adapt_timer);
 261         struct Qdisc *sch = q->sch;
 262         spinlock_t *root_lock = qdisc_lock(qdisc_root_sleeping(sch));
 263
 264         spin_lock(root_lock);
 265         red_adaptative_algo(&q->parms, &q->vars);
 266         mod_timer(&q->adapt_timer, jiffies + HZ/2);
 267         spin_unlock(root_lock);
 268 }
 269
 270 static int red_init(struct Qdisc *sch, struct nlattr *opt,
 271                     struct netlink_ext_ack *extack)
 272 {
 273         struct red_sched_data *q = qdisc_priv(sch);
 274
 275         q->qdisc = &noop_qdisc;
 276         q->sch = sch;
 277         timer_setup(&q->adapt_timer, red_adaptative_timer, 0);
 278         return red_change(sch, opt, extack);
 279 }
 280
 281 static int red_dump_offload_stats(struct Qdisc *sch, struct tc_red_qopt *opt)
 282 {
 283         struct net_device *dev = qdisc_dev(sch);
 284         struct tc_red_qopt_offload hw_stats = {
 285                 .command = TC_RED_STATS,
 286                 .handle = sch->handle,
 287                 .parent = sch->parent,
 288                 {
 289                         .stats.bstats = &sch->bstats,
 290                         .stats.qstats = &sch->qstats,
 291                 },
 292         };
 293         int err;
 294
 295         sch->flags &= ~TCQ_F_OFFLOADED;
 296
 297         if (!tc_can_offload(dev) || !dev->netdev_ops->ndo_setup_tc)
 298                 return 0;
 299
 300         err = dev->netdev_ops->ndo_setup_tc(dev, TC_SETUP_QDISC_RED,
 301                                             &hw_stats);
 302         if (err == -EOPNOTSUPP)
 303                 return 0;
 304
 305         if (!err)
 306                 sch->flags |= TCQ_F_OFFLOADED;
 307
 308         return err;
 309 }
 310
 311 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
 312 {
 313         struct red_sched_data *q = qdisc_priv(sch);
 314         struct nlattr *opts = NULL;
 315         struct tc_red_qopt opt = {
 316                 .limit          = q->limit,
 317                 .flags          = q->flags,
 318                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
 319                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
 320                 .Wlog           = q->parms.Wlog,
 321                 .Plog           = q->parms.Plog,
 322                 .Scell_log      = q->parms.Scell_log,
 323         };
 324         int err;
 325
 326         err = red_dump_offload_stats(sch, &opt);
 327         if (err)
 328                 goto nla_put_failure;
 329
 330         opts = nla_nest_start(skb, TCA_OPTIONS);
 331         if (opts == NULL)
 332                 goto nla_put_failure;
 333         if (nla_put(skb, TCA_RED_PARMS, sizeof(opt), &opt) ||
 334             nla_put_u32(skb, TCA_RED_MAX_P, q->parms.max_P))
 335                 goto nla_put_failure;
 336         return nla_nest_end(skb, opts);
 337
 338 nla_put_failure:
 339         nla_nest_cancel(skb, opts);
 340         return -EMSGSIZE;
 341 }
 342
 343 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 344 {
 345         struct red_sched_data *q = qdisc_priv(sch);
 346         struct net_device *dev = qdisc_dev(sch);
 347         struct tc_red_xstats st = {0};
 348
 349         if (sch->flags & TCQ_F_OFFLOADED) {
 350                 struct tc_red_qopt_offload hw_stats_request = {
 351                         .command = TC_RED_XSTATS,
 352                         .handle = sch->handle,
 353                         .parent = sch->parent,
 354                         {
 355                                 .xstats = &q->stats,
 356                         },
 357                 };
 358                 dev->netdev_ops->ndo_setup_tc(dev, TC_SETUP_QDISC_RED,
 359                                               &hw_stats_request);
 360         }
 361         st.early = q->stats.prob_drop + q->stats.forced_drop;
 362         st.pdrop = q->stats.pdrop;
 363         st.other = q->stats.other;
 364         st.marked = q->stats.prob_mark + q->stats.forced_mark;
 365
 366         return gnet_stats_copy_app(d, &st, sizeof(st));
 367 }
 368
 369 static int red_dump_class(struct Qdisc *sch, unsigned long cl,
 370                           struct sk_buff *skb, struct tcmsg *tcm)
 371 {
 372         struct red_sched_data *q = qdisc_priv(sch);
 373
 374         tcm->tcm_handle |= TC_H_MIN(1);
 375         tcm->tcm_info = q->qdisc->handle;
 376         return 0;
 377 }
 378
 379 static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 380                      struct Qdisc **old, struct netlink_ext_ack *extack)
 381 {
 382         struct red_sched_data *q = qdisc_priv(sch);
 383
 384         if (new == NULL)
 385                 new = &noop_qdisc;
 386
 387         *old = qdisc_replace(sch, new, &q->qdisc);
 388         return 0;
 389 }
 390
 391 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
 392 {
 393         struct red_sched_data *q = qdisc_priv(sch);
 394         return q->qdisc;
 395 }
 396
 397 static unsigned long red_find(struct Qdisc *sch, u32 classid)
 398 {
 399         return 1;
 400 }
 401
 402 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 403 {
 404         if (!walker->stop) {
 405                 if (walker->count >= walker->skip)
 406                         if (walker->fn(sch, 1, walker) < 0) {
 407                                 walker->stop = 1;
 408                                 return;
 409                         }
 410                 walker->count++;
 411         }
 412 }
 413
 414 static const struct Qdisc_class_ops red_class_ops = {
 415         .graft          =       red_graft,
 416         .leaf           =       red_leaf,
 417         .find           =       red_find,
 418         .walk           =       red_walk,
 419         .dump           =       red_dump_class,
 420 };
 421
 422 static struct Qdisc_ops red_qdisc_ops __read_mostly = {
 423         .id             =       "red",
 424         .priv_size      =       sizeof(struct red_sched_data),
 425         .cl_ops         =       &red_class_ops,
 426         .enqueue        =       red_enqueue,
 427         .dequeue        =       red_dequeue,
 428         .peek           =       red_peek,
 429         .init           =       red_init,
 430         .reset          =       red_reset,
 431         .destroy        =       red_destroy,
 432         .change         =       red_change,
 433         .dump           =       red_dump,
 434         .dump_stats     =       red_dump_stats,
 435         .owner          =       THIS_MODULE,
 436 };
 437
 438 static int __init red_module_init(void)
 439 {
 440         return register_qdisc(&red_qdisc_ops);
 441 }
 442
 443 static void __exit red_module_exit(void)
 444 {
 445         unregister_qdisc(&red_qdisc_ops);
 446 }
 447
 448 module_init(red_module_init)
 449 module_exit(red_module_exit)
 450
 451 MODULE_LICENSE("GPL");