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