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 if (q->qdisc != &noop_qdisc) { 338 err = fifo_set_limit(q->qdisc, qopt->limit); 339 if (err) 340 goto done; 341 } else if (qopt->limit > 0) { 342 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, qopt->limit); 343 if (IS_ERR(child)) { 344 err = PTR_ERR(child); 345 goto done; 346 } 347 } 348 349 buffer = min_t(u64, PSCHED_TICKS2NS(qopt->buffer), ~0U); 350 mtu = min_t(u64, PSCHED_TICKS2NS(qopt->mtu), ~0U); 351 352 if (tb[TCA_TBF_RATE64]) 353 rate64 = nla_get_u64(tb[TCA_TBF_RATE64]); 354 psched_ratecfg_precompute(&rate, &qopt->rate, rate64); 355 356 if (tb[TCA_TBF_BURST]) { 357 max_size = nla_get_u32(tb[TCA_TBF_BURST]); 358 buffer = psched_l2t_ns(&rate, max_size); 359 } else { 360 max_size = min_t(u64, psched_ns_t2l(&rate, buffer), ~0U); 361 } 362 363 if (qopt->peakrate.rate) { 364 if (tb[TCA_TBF_PRATE64]) 365 prate64 = nla_get_u64(tb[TCA_TBF_PRATE64]); 366 psched_ratecfg_precompute(&peak, &qopt->peakrate, prate64); 367 if (peak.rate_bytes_ps <= rate.rate_bytes_ps) { 368 pr_warn_ratelimited("sch_tbf: peakrate %llu is lower than or equals to rate %llu !\n", 369 peak.rate_bytes_ps, rate.rate_bytes_ps); 370 err = -EINVAL; 371 goto done; 372 } 373 374 if (tb[TCA_TBF_PBURST]) { 375 u32 pburst = nla_get_u32(tb[TCA_TBF_PBURST]); 376 max_size = min_t(u32, max_size, pburst); 377 mtu = psched_l2t_ns(&peak, pburst); 378 } else { 379 max_size = min_t(u64, max_size, psched_ns_t2l(&peak, mtu)); 380 } 381 } 382 383 if (max_size < psched_mtu(qdisc_dev(sch))) 384 pr_warn_ratelimited("sch_tbf: burst %llu is lower than device %s mtu (%u) !\n", 385 max_size, qdisc_dev(sch)->name, 386 psched_mtu(qdisc_dev(sch))); 387 388 if (!max_size) { 389 err = -EINVAL; 390 goto done; 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"); 579