net/sched/sch_tbf.c

   1 /*
   2  * net/sched/sch_tbf.c  Token Bucket Filter 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  *              Dmitry Torokhov <dtor@mail.ru> - allow attaching inner qdiscs -
  11  *                                               original idea by Martin Devera
  12  *
  13  */
  14
  15 #include <linux/config.h>
  16 #include <linux/module.h>
  17 #include <asm/uaccess.h>
  18 #include <asm/system.h>
  19 #include <asm/bitops.h>
  20 #include <linux/types.h>
  21 #include <linux/kernel.h>
  22 #include <linux/jiffies.h>
  23 #include <linux/string.h>
  24 #include <linux/mm.h>
  25 #include <linux/socket.h>
  26 #include <linux/sockios.h>
  27 #include <linux/in.h>
  28 #include <linux/errno.h>
  29 #include <linux/interrupt.h>
  30 #include <linux/if_ether.h>
  31 #include <linux/inet.h>
  32 #include <linux/netdevice.h>
  33 #include <linux/etherdevice.h>
  34 #include <linux/notifier.h>
  35 #include <net/ip.h>
  36 #include <net/route.h>
  37 #include <linux/skbuff.h>
  38 #include <net/sock.h>
  39 #include <net/pkt_sched.h>
  40
  41
  42 /*      Simple Token Bucket Filter.
  43         =======================================
  44
  45         SOURCE.
  46         -------
  47
  48         None.
  49
  50         Description.
  51         ------------
  52
  53         A data flow obeys TBF with rate R and depth B, if for any
  54         time interval t_i...t_f the number of transmitted bits
  55         does not exceed B + R*(t_f-t_i).
  56
  57         Packetized version of this definition:
  58         The sequence of packets of sizes s_i served at moments t_i
  59         obeys TBF, if for any i<=k:
  60
  61         s_i+....+s_k <= B + R*(t_k - t_i)
  62
  63         Algorithm.
  64         ----------
  65
  66         Let N(t_i) be B/R initially and N(t) grow continuously with time as:
  67
  68         N(t+delta) = min{B/R, N(t) + delta}
  69
  70         If the first packet in queue has length S, it may be
  71         transmitted only at the time t_* when S/R <= N(t_*),
  72         and in this case N(t) jumps:
  73
  74         N(t_* + 0) = N(t_* - 0) - S/R.
  75
  76
  77
  78         Actually, QoS requires two TBF to be applied to a data stream.
  79         One of them controls steady state burst size, another
  80         one with rate P (peak rate) and depth M (equal to link MTU)
  81         limits bursts at a smaller time scale.
  82
  83         It is easy to see that P>R, and B>M. If P is infinity, this double
  84         TBF is equivalent to a single one.
  85
  86         When TBF works in reshaping mode, latency is estimated as:
  87
  88         lat = max ((L-B)/R, (L-M)/P)
  89
  90
  91         NOTES.
  92         ------
  93
  94         If TBF throttles, it starts a watchdog timer, which will wake it up
  95         when it is ready to transmit.
  96         Note that the minimal timer resolution is 1/HZ.
  97         If no new packets arrive during this period,
  98         or if the device is not awaken by EOI for some previous packet,
  99         TBF can stop its activity for 1/HZ.
 100
 101
 102         This means, that with depth B, the maximal rate is
 103
 104         R_crit = B*HZ
 105
 106         F.e. for 10Mbit ethernet and HZ=100 the minimal allowed B is ~10Kbytes.
 107
 108         Note that the peak rate TBF is much more tough: with MTU 1500
 109         P_crit = 150Kbytes/sec. So, if you need greater peak
 110         rates, use alpha with HZ=1000 :-)
 111
 112         With classful TBF, limit is just kept for backwards compatibility.
 113         It is passed to the default bfifo qdisc - if the inner qdisc is
 114         changed the limit is not effective anymore.
 115 */
 116
 117 struct tbf_sched_data
 118 {
 119 /* Parameters */
 120         u32             limit;          /* Maximal length of backlog: bytes */
 121         u32             buffer;         /* Token bucket depth/rate: MUST BE >= MTU/B */
 122         u32             mtu;
 123         u32             max_size;
 124         struct qdisc_rate_table *R_tab;
 125         struct qdisc_rate_table *P_tab;
 126
 127 /* Variables */
 128         long    tokens;                 /* Current number of B tokens */
 129         long    ptokens;                /* Current number of P tokens */
 130         psched_time_t   t_c;            /* Time check-point */
 131         struct timer_list wd_timer;     /* Watchdog timer */
 132         struct Qdisc    *qdisc;         /* Inner qdisc, default - bfifo queue */
 133 };
 134
 135 #define L2T(q,L)   ((q)->R_tab->data[(L)>>(q)->R_tab->rate.cell_log])
 136 #define L2T_P(q,L) ((q)->P_tab->data[(L)>>(q)->P_tab->rate.cell_log])
 137
 138 static int tbf_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 139 {
 140         struct tbf_sched_data *q = qdisc_priv(sch);
 141         int ret;
 142
 143         if (skb->len > q->max_size) {
 144                 sch->stats.drops++;
 145 #ifdef CONFIG_NET_CLS_POLICE
 146                 if (sch->reshape_fail == NULL || sch->reshape_fail(skb, sch))
 147 #endif
 148                         kfree_skb(skb);
 149
 150                 return NET_XMIT_DROP;
 151         }
 152
 153         if ((ret = q->qdisc->enqueue(skb, q->qdisc)) != 0) {
 154                 sch->stats.drops++;
 155                 return ret;
 156         }
 157
 158         sch->q.qlen++;
 159         sch->stats.bytes += skb->len;
 160         sch->stats.packets++;
 161         return 0;
 162 }
 163
 164 static int tbf_requeue(struct sk_buff *skb, struct Qdisc* sch)
 165 {
 166         struct tbf_sched_data *q = qdisc_priv(sch);
 167         int ret;
 168
 169         if ((ret = q->qdisc->ops->requeue(skb, q->qdisc)) == 0)
 170                 sch->q.qlen++;
 171
 172         return ret;
 173 }
 174
 175 static unsigned int tbf_drop(struct Qdisc* sch)
 176 {
 177         struct tbf_sched_data *q = qdisc_priv(sch);
 178         unsigned int len;
 179
 180         if ((len = q->qdisc->ops->drop(q->qdisc)) != 0) {
 181                 sch->q.qlen--;
 182                 sch->stats.drops++;
 183         }
 184         return len;
 185 }
 186
 187 static void tbf_watchdog(unsigned long arg)
 188 {
 189         struct Qdisc *sch = (struct Qdisc*)arg;
 190
 191         sch->flags &= ~TCQ_F_THROTTLED;
 192         netif_schedule(sch->dev);
 193 }
 194
 195 static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
 196 {
 197         struct tbf_sched_data *q = qdisc_priv(sch);
 198         struct sk_buff *skb;
 199
 200         skb = q->qdisc->dequeue(q->qdisc);
 201
 202         if (skb) {
 203                 psched_time_t now;
 204                 long toks, delay;
 205                 long ptoks = 0;
 206                 unsigned int len = skb->len;
 207
 208                 PSCHED_GET_TIME(now);
 209
 210                 toks = PSCHED_TDIFF_SAFE(now, q->t_c, q->buffer);
 211
 212                 if (q->P_tab) {
 213                         ptoks = toks + q->ptokens;
 214                         if (ptoks > (long)q->mtu)
 215                                 ptoks = q->mtu;
 216                         ptoks -= L2T_P(q, len);
 217                 }
 218                 toks += q->tokens;
 219                 if (toks > (long)q->buffer)
 220                         toks = q->buffer;
 221                 toks -= L2T(q, len);
 222
 223                 if ((toks|ptoks) >= 0) {
 224                         q->t_c = now;
 225                         q->tokens = toks;
 226                         q->ptokens = ptoks;
 227                         sch->q.qlen--;
 228                         sch->flags &= ~TCQ_F_THROTTLED;
 229                         return skb;
 230                 }
 231
 232                 delay = PSCHED_US2JIFFIE(max_t(long, -toks, -ptoks));
 233
 234                 if (delay == 0)
 235                         delay = 1;
 236
 237                 mod_timer(&q->wd_timer, jiffies+delay);
 238
 239                 /* Maybe we have a shorter packet in the queue,
 240                    which can be sent now. It sounds cool,
 241                    but, however, this is wrong in principle.
 242                    We MUST NOT reorder packets under these circumstances.
 243
 244                    Really, if we split the flow into independent
 245                    subflows, it would be a very good solution.
 246                    This is the main idea of all FQ algorithms
 247                    (cf. CSZ, HPFQ, HFSC)
 248                  */
 249
 250                 if (q->qdisc->ops->requeue(skb, q->qdisc) != NET_XMIT_SUCCESS) {
 251                         /* When requeue fails skb is dropped */
 252                         sch->q.qlen--;
 253                         sch->stats.drops++;
 254                 }
 255
 256                 sch->flags |= TCQ_F_THROTTLED;
 257                 sch->stats.overlimits++;
 258         }
 259         return NULL;
 260 }
 261
 262 static void tbf_reset(struct Qdisc* sch)
 263 {
 264         struct tbf_sched_data *q = qdisc_priv(sch);
 265
 266         qdisc_reset(q->qdisc);
 267         sch->q.qlen = 0;
 268         PSCHED_GET_TIME(q->t_c);
 269         q->tokens = q->buffer;
 270         q->ptokens = q->mtu;
 271         sch->flags &= ~TCQ_F_THROTTLED;
 272         del_timer(&q->wd_timer);
 273 }
 274
 275 static struct Qdisc *tbf_create_dflt_qdisc(struct net_device *dev, u32 limit)
 276 {
 277         struct Qdisc *q = qdisc_create_dflt(dev, &bfifo_qdisc_ops);
 278         struct rtattr *rta;
 279         int ret;
 280
 281         if (q) {
 282                 rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)), GFP_KERNEL);
 283                 if (rta) {
 284                         rta->rta_type = RTM_NEWQDISC;
 285                         rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt));
 286                         ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;
 287
 288                         ret = q->ops->change(q, rta);
 289                         kfree(rta);
 290
 291                         if (ret == 0)
 292                                 return q;
 293                 }
 294                 qdisc_destroy(q);
 295         }
 296
 297         return NULL;
 298 }
 299
 300 static int tbf_change(struct Qdisc* sch, struct rtattr *opt)
 301 {
 302         int err = -EINVAL;
 303         struct tbf_sched_data *q = qdisc_priv(sch);
 304         struct rtattr *tb[TCA_TBF_PTAB];
 305         struct tc_tbf_qopt *qopt;
 306         struct qdisc_rate_table *rtab = NULL;
 307         struct qdisc_rate_table *ptab = NULL;
 308         struct Qdisc *child = NULL;
 309         int max_size,n;
 310
 311         if (rtattr_parse(tb, TCA_TBF_PTAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) ||
 312             tb[TCA_TBF_PARMS-1] == NULL ||
 313             RTA_PAYLOAD(tb[TCA_TBF_PARMS-1]) < sizeof(*qopt))
 314                 goto done;
 315
 316         qopt = RTA_DATA(tb[TCA_TBF_PARMS-1]);
 317         rtab = qdisc_get_rtab(&qopt->rate, tb[TCA_TBF_RTAB-1]);
 318         if (rtab == NULL)
 319                 goto done;
 320
 321         if (qopt->peakrate.rate) {
 322                 if (qopt->peakrate.rate > qopt->rate.rate)
 323                         ptab = qdisc_get_rtab(&qopt->peakrate, tb[TCA_TBF_PTAB-1]);
 324                 if (ptab == NULL)
 325                         goto done;
 326         }
 327
 328         for (n = 0; n < 256; n++)
 329                 if (rtab->data[n] > qopt->buffer) break;
 330         max_size = (n << qopt->rate.cell_log)-1;
 331         if (ptab) {
 332                 int size;
 333
 334                 for (n = 0; n < 256; n++)
 335                         if (ptab->data[n] > qopt->mtu) break;
 336                 size = (n << qopt->peakrate.cell_log)-1;
 337                 if (size < max_size) max_size = size;
 338         }
 339         if (max_size < 0)
 340                 goto done;
 341
 342         if (q->qdisc == &noop_qdisc) {
 343                 if ((child = tbf_create_dflt_qdisc(sch->dev, qopt->limit)) == NULL)
 344                         goto done;
 345         }
 346
 347         sch_tree_lock(sch);
 348         if (child) q->qdisc = child;
 349         q->limit = qopt->limit;
 350         q->mtu = qopt->mtu;
 351         q->max_size = max_size;
 352         q->buffer = qopt->buffer;
 353         q->tokens = q->buffer;
 354         q->ptokens = q->mtu;
 355         rtab = xchg(&q->R_tab, rtab);
 356         ptab = xchg(&q->P_tab, ptab);
 357         sch_tree_unlock(sch);
 358         err = 0;
 359 done:
 360         if (rtab)
 361                 qdisc_put_rtab(rtab);
 362         if (ptab)
 363                 qdisc_put_rtab(ptab);
 364         return err;
 365 }
 366
 367 static int tbf_init(struct Qdisc* sch, struct rtattr *opt)
 368 {
 369         struct tbf_sched_data *q = qdisc_priv(sch);
 370
 371         if (opt == NULL)
 372                 return -EINVAL;
 373
 374         PSCHED_GET_TIME(q->t_c);
 375         init_timer(&q->wd_timer);
 376         q->wd_timer.function = tbf_watchdog;
 377         q->wd_timer.data = (unsigned long)sch;
 378
 379         q->qdisc = &noop_qdisc;
 380
 381         return tbf_change(sch, opt);
 382 }
 383
 384 static void tbf_destroy(struct Qdisc *sch)
 385 {
 386         struct tbf_sched_data *q = qdisc_priv(sch);
 387
 388         del_timer(&q->wd_timer);
 389
 390         if (q->P_tab)
 391                 qdisc_put_rtab(q->P_tab);
 392         if (q->R_tab)
 393                 qdisc_put_rtab(q->R_tab);
 394
 395         qdisc_destroy(q->qdisc);
 396 }
 397
 398 static int tbf_dump(struct Qdisc *sch, struct sk_buff *skb)
 399 {
 400         struct tbf_sched_data *q = qdisc_priv(sch);
 401         unsigned char    *b = skb->tail;
 402         struct rtattr *rta;
 403         struct tc_tbf_qopt opt;
 404
 405         rta = (struct rtattr*)b;
 406         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
 407
 408         opt.limit = q->limit;
 409         opt.rate = q->R_tab->rate;
 410         if (q->P_tab)
 411                 opt.peakrate = q->P_tab->rate;
 412         else
 413                 memset(&opt.peakrate, 0, sizeof(opt.peakrate));
 414         opt.mtu = q->mtu;
 415         opt.buffer = q->buffer;
 416         RTA_PUT(skb, TCA_TBF_PARMS, sizeof(opt), &opt);
 417         rta->rta_len = skb->tail - b;
 418
 419         return skb->len;
 420
 421 rtattr_failure:
 422         skb_trim(skb, b - skb->data);
 423         return -1;
 424 }
 425
 426 static int tbf_dump_class(struct Qdisc *sch, unsigned long cl,
 427                           struct sk_buff *skb, struct tcmsg *tcm)
 428 {
 429         struct tbf_sched_data *q = qdisc_priv(sch);
 430
 431         if (cl != 1)    /* only one class */
 432                 return -ENOENT;
 433
 434         tcm->tcm_handle |= TC_H_MIN(1);
 435         tcm->tcm_info = q->qdisc->handle;
 436
 437         return 0;
 438 }
 439
 440 static int tbf_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 441                      struct Qdisc **old)
 442 {
 443         struct tbf_sched_data *q = qdisc_priv(sch);
 444
 445         if (new == NULL)
 446                 new = &noop_qdisc;
 447
 448         sch_tree_lock(sch);
 449         *old = xchg(&q->qdisc, new);
 450         qdisc_reset(*old);
 451         sch->q.qlen = 0;
 452         sch_tree_unlock(sch);
 453
 454         return 0;
 455 }
 456
 457 static struct Qdisc *tbf_leaf(struct Qdisc *sch, unsigned long arg)
 458 {
 459         struct tbf_sched_data *q = qdisc_priv(sch);
 460         return q->qdisc;
 461 }
 462
 463 static unsigned long tbf_get(struct Qdisc *sch, u32 classid)
 464 {
 465         return 1;
 466 }
 467
 468 static void tbf_put(struct Qdisc *sch, unsigned long arg)
 469 {
 470 }
 471
 472 static int tbf_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
 473                             struct rtattr **tca, unsigned long *arg)
 474 {
 475         return -ENOSYS;
 476 }
 477
 478 static int tbf_delete(struct Qdisc *sch, unsigned long arg)
 479 {
 480         return -ENOSYS;
 481 }
 482
 483 static void tbf_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 484 {
 485         if (!walker->stop) {
 486                 if (walker->count >= walker->skip)
 487                         if (walker->fn(sch, 1, walker) < 0) {
 488                                 walker->stop = 1;
 489                                 return;
 490                         }
 491                 walker->count++;
 492         }
 493 }
 494
 495 static struct tcf_proto **tbf_find_tcf(struct Qdisc *sch, unsigned long cl)
 496 {
 497         return NULL;
 498 }
 499
 500 static struct Qdisc_class_ops tbf_class_ops =
 501 {
 502         .graft          =       tbf_graft,
 503         .leaf           =       tbf_leaf,
 504         .get            =       tbf_get,
 505         .put            =       tbf_put,
 506         .change         =       tbf_change_class,
 507         .delete         =       tbf_delete,
 508         .walk           =       tbf_walk,
 509         .tcf_chain      =       tbf_find_tcf,
 510         .dump           =       tbf_dump_class,
 511 };
 512
 513 static struct Qdisc_ops tbf_qdisc_ops = {
 514         .next           =       NULL,
 515         .cl_ops         =       &tbf_class_ops,
 516         .id             =       "tbf",
 517         .priv_size      =       sizeof(struct tbf_sched_data),
 518         .enqueue        =       tbf_enqueue,
 519         .dequeue        =       tbf_dequeue,
 520         .requeue        =       tbf_requeue,
 521         .drop           =       tbf_drop,
 522         .init           =       tbf_init,
 523         .reset          =       tbf_reset,
 524         .destroy        =       tbf_destroy,
 525         .change         =       tbf_change,
 526         .dump           =       tbf_dump,
 527         .owner          =       THIS_MODULE,
 528 };
 529
 530 static int __init tbf_module_init(void)
 531 {
 532         return register_qdisc(&tbf_qdisc_ops);
 533 }
 534
 535 static void __exit tbf_module_exit(void)
 536 {
 537         unregister_qdisc(&tbf_qdisc_ops);
 538 }
 539 module_init(tbf_module_init)
 540 module_exit(tbf_module_exit)
 541 MODULE_LICENSE("GPL");