kernel/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         u32             max_size;
 105         s64             buffer;         /* Token bucket depth/rate: MUST BE >= MTU/B */
 106         s64             mtu;
 107         struct psched_ratecfg rate;
 108         struct psched_ratecfg peak;
 109
 110 /* Variables */
 111         s64     tokens;                 /* Current number of B tokens */
 112         s64     ptokens;                /* Current number of P tokens */
 113         s64     t_c;                    /* Time check-point */
 114         struct Qdisc    *qdisc;         /* Inner qdisc, default - bfifo queue */
 115         struct qdisc_watchdog watchdog; /* Watchdog timer */
 116 };
 117
 118
 119 /* Time to Length, convert time in ns to length in bytes
 120  * to determinate how many bytes can be sent in given time.
 121  */
 122 static u64 psched_ns_t2l(const struct psched_ratecfg *r,
 123                          u64 time_in_ns)
 124 {
 125         /* The formula is :
 126          * len = (time_in_ns * r->rate_bytes_ps) / NSEC_PER_SEC
 127          */
 128         u64 len = time_in_ns * r->rate_bytes_ps;
 129
 130         do_div(len, NSEC_PER_SEC);
 131
 132         if (unlikely(r->linklayer == TC_LINKLAYER_ATM)) {
 133                 do_div(len, 53);
 134                 len = len * 48;
 135         }
 136
 137         if (len > r->overhead)
 138                 len -= r->overhead;
 139         else
 140                 len = 0;
 141
 142         return len;
 143 }
 144
 145 /*
 146  * Return length of individual segments of a gso packet,
 147  * including all headers (MAC, IP, TCP/UDP)
 148  */
 149 static unsigned int skb_gso_mac_seglen(const struct sk_buff *skb)
 150 {
 151         unsigned int hdr_len = skb_transport_header(skb) - skb_mac_header(skb);
 152         return hdr_len + skb_gso_transport_seglen(skb);
 153 }
 154
 155 /* GSO packet is too big, segment it so that tbf can transmit
 156  * each segment in time
 157  */
 158 static int tbf_segment(struct sk_buff *skb, struct Qdisc *sch)
 159 {
 160         struct tbf_sched_data *q = qdisc_priv(sch);
 161         struct sk_buff *segs, *nskb;
 162         netdev_features_t features = netif_skb_features(skb);
 163         unsigned int len = 0, prev_len = qdisc_pkt_len(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                 len += segs->len;
 177                 ret = qdisc_enqueue(segs, q->qdisc);
 178                 if (ret != NET_XMIT_SUCCESS) {
 179                         if (net_xmit_drop_count(ret))
 180                                 qdisc_qstats_drop(sch);
 181                 } else {
 182                         nb++;
 183                 }
 184                 segs = nskb;
 185         }
 186         sch->q.qlen += nb;
 187         if (nb > 1)
 188                 qdisc_tree_reduce_backlog(sch, 1 - nb, prev_len - len);
 189         consume_skb(skb);
 190         return nb > 0 ? NET_XMIT_SUCCESS : NET_XMIT_DROP;
 191 }
 192
 193 static int tbf_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 194 {
 195         struct tbf_sched_data *q = qdisc_priv(sch);
 196         int ret;
 197
 198         if (qdisc_pkt_len(skb) > q->max_size) {
 199                 if (skb_is_gso(skb) && skb_gso_mac_seglen(skb) <= q->max_size)
 200                         return tbf_segment(skb, sch);
 201                 return qdisc_reshape_fail(skb, sch);
 202         }
 203         ret = qdisc_enqueue(skb, q->qdisc);
 204         if (ret != NET_XMIT_SUCCESS) {
 205                 if (net_xmit_drop_count(ret))
 206                         qdisc_qstats_drop(sch);
 207                 return ret;
 208         }
 209
 210         sch->q.qlen++;
 211         return NET_XMIT_SUCCESS;
 212 }
 213
 214 static unsigned int tbf_drop(struct Qdisc *sch)
 215 {
 216         struct tbf_sched_data *q = qdisc_priv(sch);
 217         unsigned int len = 0;
 218
 219         if (q->qdisc->ops->drop && (len = q->qdisc->ops->drop(q->qdisc)) != 0) {
 220                 sch->q.qlen--;
 221                 qdisc_qstats_drop(sch);
 222         }
 223         return len;
 224 }
 225
 226 static bool tbf_peak_present(const struct tbf_sched_data *q)
 227 {
 228         return q->peak.rate_bytes_ps;
 229 }
 230
 231 static struct sk_buff *tbf_dequeue(struct Qdisc *sch)
 232 {
 233         struct tbf_sched_data *q = qdisc_priv(sch);
 234         struct sk_buff *skb;
 235
 236         skb = q->qdisc->ops->peek(q->qdisc);
 237
 238         if (skb) {
 239                 s64 now;
 240                 s64 toks;
 241                 s64 ptoks = 0;
 242                 unsigned int len = qdisc_pkt_len(skb);
 243
 244                 now = ktime_get_ns();
 245                 toks = min_t(s64, now - q->t_c, q->buffer);
 246
 247                 if (tbf_peak_present(q)) {
 248                         ptoks = toks + q->ptokens;
 249                         if (ptoks > q->mtu)
 250                                 ptoks = q->mtu;
 251                         ptoks -= (s64) psched_l2t_ns(&q->peak, len);
 252                 }
 253                 toks += q->tokens;
 254                 if (toks > q->buffer)
 255                         toks = q->buffer;
 256                 toks -= (s64) psched_l2t_ns(&q->rate, len);
 257
 258                 if ((toks|ptoks) >= 0) {
 259                         skb = qdisc_dequeue_peeked(q->qdisc);
 260                         if (unlikely(!skb))
 261                                 return NULL;
 262
 263                         q->t_c = now;
 264                         q->tokens = toks;
 265                         q->ptokens = ptoks;
 266                         sch->q.qlen--;
 267                         qdisc_unthrottled(sch);
 268                         qdisc_bstats_update(sch, skb);
 269                         return skb;
 270                 }
 271
 272                 qdisc_watchdog_schedule_ns(&q->watchdog,
 273                                            now + max_t(long, -toks, -ptoks),
 274                                            true);
 275
 276                 /* Maybe we have a shorter packet in the queue,
 277                    which can be sent now. It sounds cool,
 278                    but, however, this is wrong in principle.
 279                    We MUST NOT reorder packets under these circumstances.
 280
 281                    Really, if we split the flow into independent
 282                    subflows, it would be a very good solution.
 283                    This is the main idea of all FQ algorithms
 284                    (cf. CSZ, HPFQ, HFSC)
 285                  */
 286
 287                 qdisc_qstats_overlimit(sch);
 288         }
 289         return NULL;
 290 }
 291
 292 static void tbf_reset(struct Qdisc *sch)
 293 {
 294         struct tbf_sched_data *q = qdisc_priv(sch);
 295
 296         qdisc_reset(q->qdisc);
 297         sch->q.qlen = 0;
 298         q->t_c = ktime_get_ns();
 299         q->tokens = q->buffer;
 300         q->ptokens = q->mtu;
 301         qdisc_watchdog_cancel(&q->watchdog);
 302 }
 303
 304 static const struct nla_policy tbf_policy[TCA_TBF_MAX + 1] = {
 305         [TCA_TBF_PARMS] = { .len = sizeof(struct tc_tbf_qopt) },
 306         [TCA_TBF_RTAB]  = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
 307         [TCA_TBF_PTAB]  = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
 308         [TCA_TBF_RATE64]        = { .type = NLA_U64 },
 309         [TCA_TBF_PRATE64]       = { .type = NLA_U64 },
 310         [TCA_TBF_BURST] = { .type = NLA_U32 },
 311         [TCA_TBF_PBURST] = { .type = NLA_U32 },
 312 };
 313
 314 static int tbf_change(struct Qdisc *sch, struct nlattr *opt)
 315 {
 316         int err;
 317         struct tbf_sched_data *q = qdisc_priv(sch);
 318         struct nlattr *tb[TCA_TBF_MAX + 1];
 319         struct tc_tbf_qopt *qopt;
 320         struct Qdisc *child = NULL;
 321         struct psched_ratecfg rate;
 322         struct psched_ratecfg peak;
 323         u64 max_size;
 324         s64 buffer, mtu;
 325         u64 rate64 = 0, prate64 = 0;
 326
 327         err = nla_parse_nested(tb, TCA_TBF_MAX, opt, tbf_policy);
 328         if (err < 0)
 329                 return err;
 330
 331         err = -EINVAL;
 332         if (tb[TCA_TBF_PARMS] == NULL)
 333                 goto done;
 334
 335         qopt = nla_data(tb[TCA_TBF_PARMS]);
 336         if (qopt->rate.linklayer == TC_LINKLAYER_UNAWARE)
 337                 qdisc_put_rtab(qdisc_get_rtab(&qopt->rate,
 338                                               tb[TCA_TBF_RTAB]));
 339
 340         if (qopt->peakrate.linklayer == TC_LINKLAYER_UNAWARE)
 341                         qdisc_put_rtab(qdisc_get_rtab(&qopt->peakrate,
 342                                                       tb[TCA_TBF_PTAB]));
 343
 344         buffer = min_t(u64, PSCHED_TICKS2NS(qopt->buffer), ~0U);
 345         mtu = min_t(u64, PSCHED_TICKS2NS(qopt->mtu), ~0U);
 346
 347         if (tb[TCA_TBF_RATE64])
 348                 rate64 = nla_get_u64(tb[TCA_TBF_RATE64]);
 349         psched_ratecfg_precompute(&rate, &qopt->rate, rate64);
 350
 351         if (tb[TCA_TBF_BURST]) {
 352                 max_size = nla_get_u32(tb[TCA_TBF_BURST]);
 353                 buffer = psched_l2t_ns(&rate, max_size);
 354         } else {
 355                 max_size = min_t(u64, psched_ns_t2l(&rate, buffer), ~0U);
 356         }
 357
 358         if (qopt->peakrate.rate) {
 359                 if (tb[TCA_TBF_PRATE64])
 360                         prate64 = nla_get_u64(tb[TCA_TBF_PRATE64]);
 361                 psched_ratecfg_precompute(&peak, &qopt->peakrate, prate64);
 362                 if (peak.rate_bytes_ps <= rate.rate_bytes_ps) {
 363                         pr_warn_ratelimited("sch_tbf: peakrate %llu is lower than or equals to rate %llu !\n",
 364                                         peak.rate_bytes_ps, rate.rate_bytes_ps);
 365                         err = -EINVAL;
 366                         goto done;
 367                 }
 368
 369                 if (tb[TCA_TBF_PBURST]) {
 370                         u32 pburst = nla_get_u32(tb[TCA_TBF_PBURST]);
 371                         max_size = min_t(u32, max_size, pburst);
 372                         mtu = psched_l2t_ns(&peak, pburst);
 373                 } else {
 374                         max_size = min_t(u64, max_size, psched_ns_t2l(&peak, mtu));
 375                 }
 376         } else {
 377                 memset(&peak, 0, sizeof(peak));
 378         }
 379
 380         if (max_size < psched_mtu(qdisc_dev(sch)))
 381                 pr_warn_ratelimited("sch_tbf: burst %llu is lower than device %s mtu (%u) !\n",
 382                                     max_size, qdisc_dev(sch)->name,
 383                                     psched_mtu(qdisc_dev(sch)));
 384
 385         if (!max_size) {
 386                 err = -EINVAL;
 387                 goto done;
 388         }
 389
 390         if (q->qdisc != &noop_qdisc) {
 391                 err = fifo_set_limit(q->qdisc, qopt->limit);
 392                 if (err)
 393                         goto done;
 394         } else if (qopt->limit > 0) {
 395                 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, qopt->limit);
 396                 if (IS_ERR(child)) {
 397                         err = PTR_ERR(child);
 398                         goto done;
 399                 }
 400         }
 401
 402         sch_tree_lock(sch);
 403         if (child) {
 404                 qdisc_tree_reduce_backlog(q->qdisc, q->qdisc->q.qlen,
 405                                           q->qdisc->qstats.backlog);
 406                 qdisc_destroy(q->qdisc);
 407                 q->qdisc = child;
 408         }
 409         q->limit = qopt->limit;
 410         if (tb[TCA_TBF_PBURST])
 411                 q->mtu = mtu;
 412         else
 413                 q->mtu = PSCHED_TICKS2NS(qopt->mtu);
 414         q->max_size = max_size;
 415         if (tb[TCA_TBF_BURST])
 416                 q->buffer = buffer;
 417         else
 418                 q->buffer = PSCHED_TICKS2NS(qopt->buffer);
 419         q->tokens = q->buffer;
 420         q->ptokens = q->mtu;
 421
 422         memcpy(&q->rate, &rate, sizeof(struct psched_ratecfg));
 423         memcpy(&q->peak, &peak, sizeof(struct psched_ratecfg));
 424
 425         sch_tree_unlock(sch);
 426         err = 0;
 427 done:
 428         return err;
 429 }
 430
 431 static int tbf_init(struct Qdisc *sch, struct nlattr *opt)
 432 {
 433         struct tbf_sched_data *q = qdisc_priv(sch);
 434
 435         if (opt == NULL)
 436                 return -EINVAL;
 437
 438         q->t_c = ktime_get_ns();
 439         qdisc_watchdog_init(&q->watchdog, sch);
 440         q->qdisc = &noop_qdisc;
 441
 442         return tbf_change(sch, opt);
 443 }
 444
 445 static void tbf_destroy(struct Qdisc *sch)
 446 {
 447         struct tbf_sched_data *q = qdisc_priv(sch);
 448
 449         qdisc_watchdog_cancel(&q->watchdog);
 450         qdisc_destroy(q->qdisc);
 451 }
 452
 453 static int tbf_dump(struct Qdisc *sch, struct sk_buff *skb)
 454 {
 455         struct tbf_sched_data *q = qdisc_priv(sch);
 456         struct nlattr *nest;
 457         struct tc_tbf_qopt opt;
 458
 459         sch->qstats.backlog = q->qdisc->qstats.backlog;
 460         nest = nla_nest_start(skb, TCA_OPTIONS);
 461         if (nest == NULL)
 462                 goto nla_put_failure;
 463
 464         opt.limit = q->limit;
 465         psched_ratecfg_getrate(&opt.rate, &q->rate);
 466         if (tbf_peak_present(q))
 467                 psched_ratecfg_getrate(&opt.peakrate, &q->peak);
 468         else
 469                 memset(&opt.peakrate, 0, sizeof(opt.peakrate));
 470         opt.mtu = PSCHED_NS2TICKS(q->mtu);
 471         opt.buffer = PSCHED_NS2TICKS(q->buffer);
 472         if (nla_put(skb, TCA_TBF_PARMS, sizeof(opt), &opt))
 473                 goto nla_put_failure;
 474         if (q->rate.rate_bytes_ps >= (1ULL << 32) &&
 475             nla_put_u64(skb, TCA_TBF_RATE64, q->rate.rate_bytes_ps))
 476                 goto nla_put_failure;
 477         if (tbf_peak_present(q) &&
 478             q->peak.rate_bytes_ps >= (1ULL << 32) &&
 479             nla_put_u64(skb, TCA_TBF_PRATE64, q->peak.rate_bytes_ps))
 480                 goto nla_put_failure;
 481
 482         return nla_nest_end(skb, nest);
 483
 484 nla_put_failure:
 485         nla_nest_cancel(skb, nest);
 486         return -1;
 487 }
 488
 489 static int tbf_dump_class(struct Qdisc *sch, unsigned long cl,
 490                           struct sk_buff *skb, struct tcmsg *tcm)
 491 {
 492         struct tbf_sched_data *q = qdisc_priv(sch);
 493
 494         tcm->tcm_handle |= TC_H_MIN(1);
 495         tcm->tcm_info = q->qdisc->handle;
 496
 497         return 0;
 498 }
 499
 500 static int tbf_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 501                      struct Qdisc **old)
 502 {
 503         struct tbf_sched_data *q = qdisc_priv(sch);
 504
 505         if (new == NULL)
 506                 new = &noop_qdisc;
 507
 508         *old = qdisc_replace(sch, new, &q->qdisc);
 509         return 0;
 510 }
 511
 512 static struct Qdisc *tbf_leaf(struct Qdisc *sch, unsigned long arg)
 513 {
 514         struct tbf_sched_data *q = qdisc_priv(sch);
 515         return q->qdisc;
 516 }
 517
 518 static unsigned long tbf_get(struct Qdisc *sch, u32 classid)
 519 {
 520         return 1;
 521 }
 522
 523 static void tbf_put(struct Qdisc *sch, unsigned long arg)
 524 {
 525 }
 526
 527 static void tbf_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 528 {
 529         if (!walker->stop) {
 530                 if (walker->count >= walker->skip)
 531                         if (walker->fn(sch, 1, walker) < 0) {
 532                                 walker->stop = 1;
 533                                 return;
 534                         }
 535                 walker->count++;
 536         }
 537 }
 538
 539 static const struct Qdisc_class_ops tbf_class_ops = {
 540         .graft          =       tbf_graft,
 541         .leaf           =       tbf_leaf,
 542         .get            =       tbf_get,
 543         .put            =       tbf_put,
 544         .walk           =       tbf_walk,
 545         .dump           =       tbf_dump_class,
 546 };
 547
 548 static struct Qdisc_ops tbf_qdisc_ops __read_mostly = {
 549         .next           =       NULL,
 550         .cl_ops         =       &tbf_class_ops,
 551         .id             =       "tbf",
 552         .priv_size      =       sizeof(struct tbf_sched_data),
 553         .enqueue        =       tbf_enqueue,
 554         .dequeue        =       tbf_dequeue,
 555         .peek           =       qdisc_peek_dequeued,
 556         .drop           =       tbf_drop,
 557         .init           =       tbf_init,
 558         .reset          =       tbf_reset,
 559         .destroy        =       tbf_destroy,
 560         .change         =       tbf_change,
 561         .dump           =       tbf_dump,
 562         .owner          =       THIS_MODULE,
 563 };
 564
 565 static int __init tbf_module_init(void)
 566 {
 567         return register_qdisc(&tbf_qdisc_ops);
 568 }
 569
 570 static void __exit tbf_module_exit(void)
 571 {
 572         unregister_qdisc(&tbf_qdisc_ops);
 573 }
 574 module_init(tbf_module_init)
 575 module_exit(tbf_module_exit)
 576 MODULE_LICENSE("GPL");