Pileus Git - ~andy/linux/blob - 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/module.h>
  16 #include <linux/types.h>
  17 #include <linux/kernel.h>
  18 #include <linux/string.h>
  19 #include <linux/errno.h>
  20 #include <linux/skbuff.h>
  21 #include <net/netlink.h>
  22 #include <net/sch_generic.h>
  23 #include <net/pkt_sched.h>
  24
  25
  26 /*      Simple Token Bucket Filter.
  27         =======================================
  28
  29         SOURCE.
  30         -------
  31
  32         None.
  33
  34         Description.
  35         ------------
  36
  37         A data flow obeys TBF with rate R and depth B, if for any
  38         time interval t_i...t_f the number of transmitted bits
  39         does not exceed B + R*(t_f-t_i).
  40
  41         Packetized version of this definition:
  42         The sequence of packets of sizes s_i served at moments t_i
  43         obeys TBF, if for any i<=k:
  44
  45         s_i+....+s_k <= B + R*(t_k - t_i)
  46
  47         Algorithm.
  48         ----------
  49
  50         Let N(t_i) be B/R initially and N(t) grow continuously with time as:
  51
  52         N(t+delta) = min{B/R, N(t) + delta}
  53
  54         If the first packet in queue has length S, it may be
  55         transmitted only at the time t_* when S/R <= N(t_*),
  56         and in this case N(t) jumps:
  57
  58         N(t_* + 0) = N(t_* - 0) - S/R.
  59
  60
  61
  62         Actually, QoS requires two TBF to be applied to a data stream.
  63         One of them controls steady state burst size, another
  64         one with rate P (peak rate) and depth M (equal to link MTU)
  65         limits bursts at a smaller time scale.
  66
  67         It is easy to see that P>R, and B>M. If P is infinity, this double
  68         TBF is equivalent to a single one.
  69
  70         When TBF works in reshaping mode, latency is estimated as:
  71
  72         lat = max ((L-B)/R, (L-M)/P)
  73
  74
  75         NOTES.
  76         ------
  77
  78         If TBF throttles, it starts a watchdog timer, which will wake it up
  79         when it is ready to transmit.
  80         Note that the minimal timer resolution is 1/HZ.
  81         If no new packets arrive during this period,
  82         or if the device is not awaken by EOI for some previous packet,
  83         TBF can stop its activity for 1/HZ.
  84
  85
  86         This means, that with depth B, the maximal rate is
  87
  88         R_crit = B*HZ
  89
  90         F.e. for 10Mbit ethernet and HZ=100 the minimal allowed B is ~10Kbytes.
  91
  92         Note that the peak rate TBF is much more tough: with MTU 1500
  93         P_crit = 150Kbytes/sec. So, if you need greater peak
  94         rates, use alpha with HZ=1000 :-)
  95
  96         With classful TBF, limit is just kept for backwards compatibility.
  97         It is passed to the default bfifo qdisc - if the inner qdisc is
  98         changed the limit is not effective anymore.
  99 */
 100
 101 struct tbf_sched_data {
 102 /* Parameters */
 103         u32             limit;          /* Maximal length of backlog: bytes */
 104         s64             buffer;         /* Token bucket depth/rate: MUST BE >= MTU/B */
 105         s64             mtu;
 106         u32             max_size;
 107         struct psched_ratecfg rate;
 108         struct psched_ratecfg peak;
 109         bool peak_present;
 110
 111 /* Variables */
 112         s64     tokens;                 /* Current number of B tokens */
 113         s64     ptokens;                /* Current number of P tokens */
 114         s64     t_c;                    /* Time check-point */
 115         struct Qdisc    *qdisc;         /* Inner qdisc, default - bfifo queue */
 116         struct qdisc_watchdog watchdog; /* Watchdog timer */
 117 };
 118
 119
 120 /* Time to Length, convert time in ns to length in bytes
 121  * to determinate how many bytes can be sent in given time.
 122  */
 123 static u64 psched_ns_t2l(const struct psched_ratecfg *r,
 124                          u64 time_in_ns)
 125 {
 126         /* The formula is :
 127          * len = (time_in_ns * r->rate_bytes_ps) / NSEC_PER_SEC
 128          */
 129         u64 len = time_in_ns * r->rate_bytes_ps;
 130
 131         do_div(len, NSEC_PER_SEC);
 132
 133         if (unlikely(r->linklayer == TC_LINKLAYER_ATM)) {
 134                 do_div(len, 53);
 135                 len = len * 48;
 136         }
 137
 138         if (len > r->overhead)
 139                 len -= r->overhead;
 140         else
 141                 len = 0;
 142
 143         return len;
 144 }
 145
 146 /*
 147  * Return length of individual segments of a gso packet,
 148  * including all headers (MAC, IP, TCP/UDP)
 149  */
 150 static unsigned int skb_gso_mac_seglen(const struct sk_buff *skb)
 151 {
 152         unsigned int hdr_len = skb_transport_header(skb) - skb_mac_header(skb);
 153         return hdr_len + skb_gso_transport_seglen(skb);
 154 }
 155
 156 /* GSO packet is too big, segment it so that tbf can transmit
 157  * each segment in time
 158  */
 159 static int tbf_segment(struct sk_buff *skb, struct Qdisc *sch)
 160 {
 161         struct tbf_sched_data *q = qdisc_priv(sch);
 162         struct sk_buff *segs, *nskb;
 163         netdev_features_t features = netif_skb_features(skb);
 164         int ret, nb;
 165
 166         segs = skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK);
 167
 168         if (IS_ERR_OR_NULL(segs))
 169                 return qdisc_reshape_fail(skb, sch);
 170
 171         nb = 0;
 172         while (segs) {
 173                 nskb = segs->next;
 174                 segs->next = NULL;
 175                 qdisc_skb_cb(segs)->pkt_len = segs->len;
 176                 ret = qdisc_enqueue(segs, q->qdisc);
 177                 if (ret != NET_XMIT_SUCCESS) {
 178                         if (net_xmit_drop_count(ret))
 179                                 sch->qstats.drops++;
 180                 } else {
 181                         nb++;
 182                 }
 183                 segs = nskb;
 184         }
 185         sch->q.qlen += nb;
 186         if (nb > 1)
 187                 qdisc_tree_decrease_qlen(sch, 1 - nb);
 188         consume_skb(skb);
 189         return nb > 0 ? NET_XMIT_SUCCESS : NET_XMIT_DROP;
 190 }
 191
 192 static int tbf_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 193 {
 194         struct tbf_sched_data *q = qdisc_priv(sch);
 195         int ret;
 196
 197         if (qdisc_pkt_len(skb) > q->max_size) {
 198                 if (skb_is_gso(skb) && skb_gso_mac_seglen(skb) <= q->max_size)
 199                         return tbf_segment(skb, sch);
 200                 return qdisc_reshape_fail(skb, sch);
 201         }
 202         ret = qdisc_enqueue(skb, q->qdisc);
 203         if (ret != NET_XMIT_SUCCESS) {
 204                 if (net_xmit_drop_count(ret))
 205                         sch->qstats.drops++;
 206                 return ret;
 207         }
 208
 209         sch->q.qlen++;
 210         return NET_XMIT_SUCCESS;
 211 }
 212
 213 static unsigned int tbf_drop(struct Qdisc *sch)
 214 {
 215         struct tbf_sched_data *q = qdisc_priv(sch);
 216         unsigned int len = 0;
 217
 218         if (q->qdisc->ops->drop && (len = q->qdisc->ops->drop(q->qdisc)) != 0) {
 219                 sch->q.qlen--;
 220                 sch->qstats.drops++;
 221         }
 222         return len;
 223 }
 224
 225 static struct sk_buff *tbf_dequeue(struct Qdisc *sch)
 226 {
 227         struct tbf_sched_data *q = qdisc_priv(sch);
 228         struct sk_buff *skb;
 229
 230         skb = q->qdisc->ops->peek(q->qdisc);
 231
 232         if (skb) {
 233                 s64 now;
 234                 s64 toks;
 235                 s64 ptoks = 0;
 236                 unsigned int len = qdisc_pkt_len(skb);
 237
 238                 now = ktime_to_ns(ktime_get());
 239                 toks = min_t(s64, now - q->t_c, q->buffer);
 240
 241                 if (q->peak_present) {
 242                         ptoks = toks + q->ptokens;
 243                         if (ptoks > q->mtu)
 244                                 ptoks = q->mtu;
 245                         ptoks -= (s64) psched_l2t_ns(&q->peak, len);
 246                 }
 247                 toks += q->tokens;
 248                 if (toks > q->buffer)
 249                         toks = q->buffer;
 250                 toks -= (s64) psched_l2t_ns(&q->rate, len);
 251
 252                 if ((toks|ptoks) >= 0) {
 253                         skb = qdisc_dequeue_peeked(q->qdisc);
 254                         if (unlikely(!skb))
 255                                 return NULL;
 256
 257                         q->t_c = now;
 258                         q->tokens = toks;
 259                         q->ptokens = ptoks;
 260                         sch->q.qlen--;
 261                         qdisc_unthrottled(sch);
 262                         qdisc_bstats_update(sch, skb);
 263                         return skb;
 264                 }
 265
 266                 qdisc_watchdog_schedule_ns(&q->watchdog,
 267                                            now + max_t(long, -toks, -ptoks));
 268
 269                 /* Maybe we have a shorter packet in the queue,
 270                    which can be sent now. It sounds cool,
 271                    but, however, this is wrong in principle.
 272                    We MUST NOT reorder packets under these circumstances.
 273
 274                    Really, if we split the flow into independent
 275                    subflows, it would be a very good solution.
 276                    This is the main idea of all FQ algorithms
 277                    (cf. CSZ, HPFQ, HFSC)
 278                  */
 279
 280                 sch->qstats.overlimits++;
 281         }
 282         return NULL;
 283 }
 284
 285 static void tbf_reset(struct Qdisc *sch)
 286 {
 287         struct tbf_sched_data *q = qdisc_priv(sch);
 288
 289         qdisc_reset(q->qdisc);
 290         sch->q.qlen = 0;
 291         q->t_c = ktime_to_ns(ktime_get());
 292         q->tokens = q->buffer;
 293         q->ptokens = q->mtu;
 294         qdisc_watchdog_cancel(&q->watchdog);
 295 }
 296
 297 static const struct nla_policy tbf_policy[TCA_TBF_MAX + 1] = {
 298         [TCA_TBF_PARMS] = { .len = sizeof(struct tc_tbf_qopt) },
 299         [TCA_TBF_RTAB]  = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
 300         [TCA_TBF_PTAB]  = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
 301         [TCA_TBF_RATE64]        = { .type = NLA_U64 },
 302         [TCA_TBF_PRATE64]       = { .type = NLA_U64 },
 303         [TCA_TBF_BURST] = { .type = NLA_U32 },
 304         [TCA_TBF_PBURST] = { .type = NLA_U32 },
 305 };
 306
 307 static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
 308 {
 309         int err;
 310         struct tbf_sched_data *q = qdisc_priv(sch);
 311         struct nlattr *tb[TCA_TBF_MAX + 1];
 312         struct tc_tbf_qopt *qopt;
 313         struct Qdisc *child = NULL;
 314         struct psched_ratecfg rate;
 315         struct psched_ratecfg peak;
 316         u64 max_size;
 317         s64 buffer, mtu;
 318         u64 rate64 = 0, prate64 = 0;
 319
 320         err = nla_parse_nested(tb, TCA_TBF_MAX, opt, tbf_policy);
 321         if (err < 0)
 322                 return err;
 323
 324         err = -EINVAL;
 325         if (tb[TCA_TBF_PARMS] == NULL)
 326                 goto done;
 327
 328         qopt = nla_data(tb[TCA_TBF_PARMS]);
 329         if (qopt->rate.linklayer == TC_LINKLAYER_UNAWARE)
 330                 qdisc_put_rtab(qdisc_get_rtab(&qopt->rate,
 331                                               tb[TCA_TBF_RTAB]));
 332
 333         if (qopt->peakrate.linklayer == TC_LINKLAYER_UNAWARE)
 334                         qdisc_put_rtab(qdisc_get_rtab(&qopt->peakrate,
 335                                                       tb[TCA_TBF_PTAB]));
 336
 337         buffer = min_t(u64, PSCHED_TICKS2NS(qopt->buffer), ~0U);
 338         mtu = min_t(u64, PSCHED_TICKS2NS(qopt->mtu), ~0U);
 339
 340         if (tb[TCA_TBF_RATE64])
 341                 rate64 = nla_get_u64(tb[TCA_TBF_RATE64]);
 342         psched_ratecfg_precompute(&rate, &qopt->rate, rate64);
 343
 344         if (tb[TCA_TBF_BURST]) {
 345                 max_size = nla_get_u32(tb[TCA_TBF_BURST]);
 346                 buffer = psched_l2t_ns(&rate, max_size);
 347         } else {
 348                 max_size = min_t(u64, psched_ns_t2l(&rate, buffer), ~0U);
 349         }
 350
 351         if (qopt->peakrate.rate) {
 352                 if (tb[TCA_TBF_PRATE64])
 353                         prate64 = nla_get_u64(tb[TCA_TBF_PRATE64]);
 354                 psched_ratecfg_precompute(&peak, &qopt->peakrate, prate64);
 355                 if (peak.rate_bytes_ps <= rate.rate_bytes_ps) {
 356                         pr_warn_ratelimited("sch_tbf: peakrate %llu is lower than or equals to rate %llu !\n",
 357                                         peak.rate_bytes_ps, rate.rate_bytes_ps);
 358                         err = -EINVAL;
 359                         goto done;
 360                 }
 361
 362                 if (tb[TCA_TBF_PBURST]) {
 363                         u32 pburst = nla_get_u32(tb[TCA_TBF_PBURST]);
 364                         max_size = min_t(u32, max_size, pburst);
 365                         mtu = psched_l2t_ns(&peak, pburst);
 366                 } else {
 367                         max_size = min_t(u64, max_size, psched_ns_t2l(&peak, mtu));
 368                 }
 369         }
 370
 371         if (max_size < psched_mtu(qdisc_dev(sch)))
 372                 pr_warn_ratelimited("sch_tbf: burst %llu is lower than device %s mtu (%u) !\n",
 373                                     max_size, qdisc_dev(sch)->name,
 374                                     psched_mtu(qdisc_dev(sch)));
 375
 376         if (!max_size) {
 377                 err = -EINVAL;
 378                 goto done;
 379         }
 380
 381         if (q->qdisc != &noop_qdisc) {
 382                 err = fifo_set_limit(q->qdisc, qopt->limit);
 383                 if (err)
 384                         goto done;
 385         } else if (qopt->limit > 0) {
 386                 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, qopt->limit);
 387                 if (IS_ERR(child)) {
 388                         err = PTR_ERR(child);
 389                         goto done;
 390                 }
 391         }
 392
 393         sch_tree_lock(sch);
 394         if (child) {
 395                 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
 396                 qdisc_destroy(q->qdisc);
 397                 q->qdisc = child;
 398         }
 399         q->limit = qopt->limit;
 400         if (tb[TCA_TBF_PBURST])
 401                 q->mtu = mtu;
 402         else
 403                 q->mtu = PSCHED_TICKS2NS(qopt->mtu);
 404         q->max_size = max_size;
 405         if (tb[TCA_TBF_BURST])
 406                 q->buffer = buffer;
 407         else
 408                 q->buffer = PSCHED_TICKS2NS(qopt->buffer);
 409         q->tokens = q->buffer;
 410         q->ptokens = q->mtu;
 411
 412         memcpy(&q->rate, &rate, sizeof(struct psched_ratecfg));
 413         if (qopt->peakrate.rate) {
 414                 memcpy(&q->peak, &peak, sizeof(struct psched_ratecfg));
 415                 q->peak_present = true;
 416         } else {
 417                 q->peak_present = false;
 418         }
 419
 420         sch_tree_unlock(sch);
 421         err = 0;
 422 done:
 423         return err;
 424 }
 425
 426 static int tbf_init(struct Qdisc *sch, struct nlattr *opt)
 427 {
 428         struct tbf_sched_data *q = qdisc_priv(sch);
 429
 430         if (opt == NULL)
 431                 return -EINVAL;
 432
 433         q->t_c = ktime_to_ns(ktime_get());
 434         qdisc_watchdog_init(&q->watchdog, sch);
 435         q->qdisc = &noop_qdisc;
 436
 437         return tbf_change(sch, opt);
 438 }
 439
 440 static void tbf_destroy(struct Qdisc *sch)
 441 {
 442         struct tbf_sched_data *q = qdisc_priv(sch);
 443
 444         qdisc_watchdog_cancel(&q->watchdog);
 445         qdisc_destroy(q->qdisc);
 446 }
 447
 448 static int tbf_dump(struct Qdisc *sch, struct sk_buff *skb)
 449 {
 450         struct tbf_sched_data *q = qdisc_priv(sch);
 451         struct nlattr *nest;
 452         struct tc_tbf_qopt opt;
 453
 454         sch->qstats.backlog = q->qdisc->qstats.backlog;
 455         nest = nla_nest_start(skb, TCA_OPTIONS);
 456         if (nest == NULL)
 457                 goto nla_put_failure;
 458
 459         opt.limit = q->limit;
 460         psched_ratecfg_getrate(&opt.rate, &q->rate);
 461         if (q->peak_present)
 462                 psched_ratecfg_getrate(&opt.peakrate, &q->peak);
 463         else
 464                 memset(&opt.peakrate, 0, sizeof(opt.peakrate));
 465         opt.mtu = PSCHED_NS2TICKS(q->mtu);
 466         opt.buffer = PSCHED_NS2TICKS(q->buffer);
 467         if (nla_put(skb, TCA_TBF_PARMS, sizeof(opt), &opt))
 468                 goto nla_put_failure;
 469         if (q->rate.rate_bytes_ps >= (1ULL << 32) &&
 470             nla_put_u64(skb, TCA_TBF_RATE64, q->rate.rate_bytes_ps))
 471                 goto nla_put_failure;
 472         if (q->peak_present &&
 473             q->peak.rate_bytes_ps >= (1ULL << 32) &&
 474             nla_put_u64(skb, TCA_TBF_PRATE64, q->peak.rate_bytes_ps))
 475                 goto nla_put_failure;
 476
 477         nla_nest_end(skb, nest);
 478         return skb->len;
 479
 480 nla_put_failure:
 481         nla_nest_cancel(skb, nest);
 482         return -1;
 483 }
 484
 485 static int tbf_dump_class(struct Qdisc *sch, unsigned long cl,
 486                           struct sk_buff *skb, struct tcmsg *tcm)
 487 {
 488         struct tbf_sched_data *q = qdisc_priv(sch);
 489
 490         tcm->tcm_handle |= TC_H_MIN(1);
 491         tcm->tcm_info = q->qdisc->handle;
 492
 493         return 0;
 494 }
 495
 496 static int tbf_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 497                      struct Qdisc **old)
 498 {
 499         struct tbf_sched_data *q = qdisc_priv(sch);
 500
 501         if (new == NULL)
 502                 new = &noop_qdisc;
 503
 504         sch_tree_lock(sch);
 505         *old = q->qdisc;
 506         q->qdisc = new;
 507         qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 508         qdisc_reset(*old);
 509         sch_tree_unlock(sch);
 510
 511         return 0;
 512 }
 513
 514 static struct Qdisc *tbf_leaf(struct Qdisc *sch, unsigned long arg)
 515 {
 516         struct tbf_sched_data *q = qdisc_priv(sch);
 517         return q->qdisc;
 518 }
 519
 520 static unsigned long tbf_get(struct Qdisc *sch, u32 classid)
 521 {
 522         return 1;
 523 }
 524
 525 static void tbf_put(struct Qdisc *sch, unsigned long arg)
 526 {
 527 }
 528
 529 static void tbf_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 530 {
 531         if (!walker->stop) {
 532                 if (walker->count >= walker->skip)
 533                         if (walker->fn(sch, 1, walker) < 0) {
 534                                 walker->stop = 1;
 535                                 return;
 536                         }
 537                 walker->count++;
 538         }
 539 }
 540
 541 static const struct Qdisc_class_ops tbf_class_ops = {
 542         .graft          =       tbf_graft,
 543         .leaf           =       tbf_leaf,
 544         .get            =       tbf_get,
 545         .put            =       tbf_put,
 546         .walk           =       tbf_walk,
 547         .dump           =       tbf_dump_class,
 548 };
 549
 550 static struct Qdisc_ops tbf_qdisc_ops __read_mostly = {
 551         .next           =       NULL,
 552         .cl_ops         =       &tbf_class_ops,
 553         .id             =       "tbf",
 554         .priv_size      =       sizeof(struct tbf_sched_data),
 555         .enqueue        =       tbf_enqueue,
 556         .dequeue        =       tbf_dequeue,
 557         .peek           =       qdisc_peek_dequeued,
 558         .drop           =       tbf_drop,
 559         .init           =       tbf_init,
 560         .reset          =       tbf_reset,
 561         .destroy        =       tbf_destroy,
 562         .change         =       tbf_change,
 563         .dump           =       tbf_dump,
 564         .owner          =       THIS_MODULE,
 565 };
 566
 567 static int __init tbf_module_init(void)
 568 {
 569         return register_qdisc(&tbf_qdisc_ops);
 570 }
 571
 572 static void __exit tbf_module_exit(void)
 573 {
 574         unregister_qdisc(&tbf_qdisc_ops);
 575 }
 576 module_init(tbf_module_init)
 577 module_exit(tbf_module_exit)
 578 MODULE_LICENSE("GPL");