2 * net/sched/sch_tbf.c Token Bucket Filter queue.
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.
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
15 #include <linux/module.h>
16 #include <asm/uaccess.h>
17 #include <asm/system.h>
18 #include <linux/bitops.h>
19 #include <linux/types.h>
20 #include <linux/kernel.h>
21 #include <linux/jiffies.h>
22 #include <linux/string.h>
24 #include <linux/socket.h>
25 #include <linux/sockios.h>
27 #include <linux/errno.h>
28 #include <linux/interrupt.h>
29 #include <linux/if_ether.h>
30 #include <linux/inet.h>
31 #include <linux/netdevice.h>
32 #include <linux/etherdevice.h>
33 #include <linux/notifier.h>
35 #include <net/netlink.h>
36 #include <net/route.h>
37 #include <linux/skbuff.h>
39 #include <net/pkt_sched.h>
42 /* Simple Token Bucket Filter.
43 =======================================
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).
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:
61 s_i+....+s_k <= B + R*(t_k - t_i)
66 Let N(t_i) be B/R initially and N(t) grow continuously with time as:
68 N(t+delta) = min{B/R, N(t) + delta}
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:
74 N(t_* + 0) = N(t_* - 0) - S/R.
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.
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.
86 When TBF works in reshaping mode, latency is estimated as:
88 lat = max ((L-B)/R, (L-M)/P)
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.
102 This means, that with depth B, the maximal rate is
106 F.e. for 10Mbit ethernet and HZ=100 the minimal allowed B is ~10Kbytes.
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 :-)
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.
117 struct tbf_sched_data
120 u32 limit; /* Maximal length of backlog: bytes */
121 u32 buffer; /* Token bucket depth/rate: MUST BE >= MTU/B */
124 struct qdisc_rate_table *R_tab;
125 struct qdisc_rate_table *P_tab;
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 Qdisc *qdisc; /* Inner qdisc, default - bfifo queue */
132 struct qdisc_watchdog watchdog; /* Watchdog timer */
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])
138 static int tbf_enqueue(struct sk_buff *skb, struct Qdisc* sch)
140 struct tbf_sched_data *q = qdisc_priv(sch);
143 if (skb->len > q->max_size) {
145 #ifdef CONFIG_NET_CLS_POLICE
146 if (sch->reshape_fail == NULL || sch->reshape_fail(skb, sch))
150 return NET_XMIT_DROP;
153 if ((ret = q->qdisc->enqueue(skb, q->qdisc)) != 0) {
159 sch->bstats.bytes += skb->len;
160 sch->bstats.packets++;
164 static int tbf_requeue(struct sk_buff *skb, struct Qdisc* sch)
166 struct tbf_sched_data *q = qdisc_priv(sch);
169 if ((ret = q->qdisc->ops->requeue(skb, q->qdisc)) == 0) {
171 sch->qstats.requeues++;
177 static unsigned int tbf_drop(struct Qdisc* sch)
179 struct tbf_sched_data *q = qdisc_priv(sch);
180 unsigned int len = 0;
182 if (q->qdisc->ops->drop && (len = q->qdisc->ops->drop(q->qdisc)) != 0) {
189 static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
191 struct tbf_sched_data *q = qdisc_priv(sch);
194 skb = q->qdisc->dequeue(q->qdisc);
200 unsigned int len = skb->len;
202 PSCHED_GET_TIME(now);
204 toks = PSCHED_TDIFF_SAFE(now, q->t_c, q->buffer);
207 ptoks = toks + q->ptokens;
208 if (ptoks > (long)q->mtu)
210 ptoks -= L2T_P(q, len);
213 if (toks > (long)q->buffer)
217 if ((toks|ptoks) >= 0) {
222 sch->flags &= ~TCQ_F_THROTTLED;
226 qdisc_watchdog_schedule(&q->watchdog,
227 now + max_t(long, -toks, -ptoks));
229 /* Maybe we have a shorter packet in the queue,
230 which can be sent now. It sounds cool,
231 but, however, this is wrong in principle.
232 We MUST NOT reorder packets under these circumstances.
234 Really, if we split the flow into independent
235 subflows, it would be a very good solution.
236 This is the main idea of all FQ algorithms
237 (cf. CSZ, HPFQ, HFSC)
240 if (q->qdisc->ops->requeue(skb, q->qdisc) != NET_XMIT_SUCCESS) {
241 /* When requeue fails skb is dropped */
242 qdisc_tree_decrease_qlen(q->qdisc, 1);
246 sch->qstats.overlimits++;
251 static void tbf_reset(struct Qdisc* sch)
253 struct tbf_sched_data *q = qdisc_priv(sch);
255 qdisc_reset(q->qdisc);
257 PSCHED_GET_TIME(q->t_c);
258 q->tokens = q->buffer;
260 qdisc_watchdog_cancel(&q->watchdog);
263 static struct Qdisc *tbf_create_dflt_qdisc(struct Qdisc *sch, u32 limit)
269 q = qdisc_create_dflt(sch->dev, &bfifo_qdisc_ops,
270 TC_H_MAKE(sch->handle, 1));
272 rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)), GFP_KERNEL);
274 rta->rta_type = RTM_NEWQDISC;
275 rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt));
276 ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;
278 ret = q->ops->change(q, rta);
290 static int tbf_change(struct Qdisc* sch, struct rtattr *opt)
293 struct tbf_sched_data *q = qdisc_priv(sch);
294 struct rtattr *tb[TCA_TBF_PTAB];
295 struct tc_tbf_qopt *qopt;
296 struct qdisc_rate_table *rtab = NULL;
297 struct qdisc_rate_table *ptab = NULL;
298 struct Qdisc *child = NULL;
301 if (rtattr_parse_nested(tb, TCA_TBF_PTAB, opt) ||
302 tb[TCA_TBF_PARMS-1] == NULL ||
303 RTA_PAYLOAD(tb[TCA_TBF_PARMS-1]) < sizeof(*qopt))
306 qopt = RTA_DATA(tb[TCA_TBF_PARMS-1]);
307 rtab = qdisc_get_rtab(&qopt->rate, tb[TCA_TBF_RTAB-1]);
311 if (qopt->peakrate.rate) {
312 if (qopt->peakrate.rate > qopt->rate.rate)
313 ptab = qdisc_get_rtab(&qopt->peakrate, tb[TCA_TBF_PTAB-1]);
318 for (n = 0; n < 256; n++)
319 if (rtab->data[n] > qopt->buffer) break;
320 max_size = (n << qopt->rate.cell_log)-1;
324 for (n = 0; n < 256; n++)
325 if (ptab->data[n] > qopt->mtu) break;
326 size = (n << qopt->peakrate.cell_log)-1;
327 if (size < max_size) max_size = size;
332 if (qopt->limit > 0) {
333 if ((child = tbf_create_dflt_qdisc(sch, qopt->limit)) == NULL)
339 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
340 qdisc_destroy(xchg(&q->qdisc, child));
342 q->limit = qopt->limit;
344 q->max_size = max_size;
345 q->buffer = qopt->buffer;
346 q->tokens = q->buffer;
348 rtab = xchg(&q->R_tab, rtab);
349 ptab = xchg(&q->P_tab, ptab);
350 sch_tree_unlock(sch);
354 qdisc_put_rtab(rtab);
356 qdisc_put_rtab(ptab);
360 static int tbf_init(struct Qdisc* sch, struct rtattr *opt)
362 struct tbf_sched_data *q = qdisc_priv(sch);
367 PSCHED_GET_TIME(q->t_c);
368 qdisc_watchdog_init(&q->watchdog, sch);
369 q->qdisc = &noop_qdisc;
371 return tbf_change(sch, opt);
374 static void tbf_destroy(struct Qdisc *sch)
376 struct tbf_sched_data *q = qdisc_priv(sch);
378 qdisc_watchdog_cancel(&q->watchdog);
381 qdisc_put_rtab(q->P_tab);
383 qdisc_put_rtab(q->R_tab);
385 qdisc_destroy(q->qdisc);
388 static int tbf_dump(struct Qdisc *sch, struct sk_buff *skb)
390 struct tbf_sched_data *q = qdisc_priv(sch);
391 unsigned char *b = skb_tail_pointer(skb);
393 struct tc_tbf_qopt opt;
395 rta = (struct rtattr*)b;
396 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
398 opt.limit = q->limit;
399 opt.rate = q->R_tab->rate;
401 opt.peakrate = q->P_tab->rate;
403 memset(&opt.peakrate, 0, sizeof(opt.peakrate));
405 opt.buffer = q->buffer;
406 RTA_PUT(skb, TCA_TBF_PARMS, sizeof(opt), &opt);
407 rta->rta_len = skb_tail_pointer(skb) - b;
416 static int tbf_dump_class(struct Qdisc *sch, unsigned long cl,
417 struct sk_buff *skb, struct tcmsg *tcm)
419 struct tbf_sched_data *q = qdisc_priv(sch);
421 if (cl != 1) /* only one class */
424 tcm->tcm_handle |= TC_H_MIN(1);
425 tcm->tcm_info = q->qdisc->handle;
430 static int tbf_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
433 struct tbf_sched_data *q = qdisc_priv(sch);
439 *old = xchg(&q->qdisc, new);
440 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
442 sch_tree_unlock(sch);
447 static struct Qdisc *tbf_leaf(struct Qdisc *sch, unsigned long arg)
449 struct tbf_sched_data *q = qdisc_priv(sch);
453 static unsigned long tbf_get(struct Qdisc *sch, u32 classid)
458 static void tbf_put(struct Qdisc *sch, unsigned long arg)
462 static int tbf_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
463 struct rtattr **tca, unsigned long *arg)
468 static int tbf_delete(struct Qdisc *sch, unsigned long arg)
473 static void tbf_walk(struct Qdisc *sch, struct qdisc_walker *walker)
476 if (walker->count >= walker->skip)
477 if (walker->fn(sch, 1, walker) < 0) {
485 static struct tcf_proto **tbf_find_tcf(struct Qdisc *sch, unsigned long cl)
490 static struct Qdisc_class_ops tbf_class_ops =
496 .change = tbf_change_class,
497 .delete = tbf_delete,
499 .tcf_chain = tbf_find_tcf,
500 .dump = tbf_dump_class,
503 static struct Qdisc_ops tbf_qdisc_ops = {
505 .cl_ops = &tbf_class_ops,
507 .priv_size = sizeof(struct tbf_sched_data),
508 .enqueue = tbf_enqueue,
509 .dequeue = tbf_dequeue,
510 .requeue = tbf_requeue,
514 .destroy = tbf_destroy,
515 .change = tbf_change,
517 .owner = THIS_MODULE,
520 static int __init tbf_module_init(void)
522 return register_qdisc(&tbf_qdisc_ops);
525 static void __exit tbf_module_exit(void)
527 unregister_qdisc(&tbf_qdisc_ops);
529 module_init(tbf_module_init)
530 module_exit(tbf_module_exit)
531 MODULE_LICENSE("GPL");