Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound-2.6
[linux-2.6] / 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/pkt_sched.h>
23
24
25 /*      Simple Token Bucket Filter.
26         =======================================
27
28         SOURCE.
29         -------
30
31         None.
32
33         Description.
34         ------------
35
36         A data flow obeys TBF with rate R and depth B, if for any
37         time interval t_i...t_f the number of transmitted bits
38         does not exceed B + R*(t_f-t_i).
39
40         Packetized version of this definition:
41         The sequence of packets of sizes s_i served at moments t_i
42         obeys TBF, if for any i<=k:
43
44         s_i+....+s_k <= B + R*(t_k - t_i)
45
46         Algorithm.
47         ----------
48
49         Let N(t_i) be B/R initially and N(t) grow continuously with time as:
50
51         N(t+delta) = min{B/R, N(t) + delta}
52
53         If the first packet in queue has length S, it may be
54         transmitted only at the time t_* when S/R <= N(t_*),
55         and in this case N(t) jumps:
56
57         N(t_* + 0) = N(t_* - 0) - S/R.
58
59
60
61         Actually, QoS requires two TBF to be applied to a data stream.
62         One of them controls steady state burst size, another
63         one with rate P (peak rate) and depth M (equal to link MTU)
64         limits bursts at a smaller time scale.
65
66         It is easy to see that P>R, and B>M. If P is infinity, this double
67         TBF is equivalent to a single one.
68
69         When TBF works in reshaping mode, latency is estimated as:
70
71         lat = max ((L-B)/R, (L-M)/P)
72
73
74         NOTES.
75         ------
76
77         If TBF throttles, it starts a watchdog timer, which will wake it up
78         when it is ready to transmit.
79         Note that the minimal timer resolution is 1/HZ.
80         If no new packets arrive during this period,
81         or if the device is not awaken by EOI for some previous packet,
82         TBF can stop its activity for 1/HZ.
83
84
85         This means, that with depth B, the maximal rate is
86
87         R_crit = B*HZ
88
89         F.e. for 10Mbit ethernet and HZ=100 the minimal allowed B is ~10Kbytes.
90
91         Note that the peak rate TBF is much more tough: with MTU 1500
92         P_crit = 150Kbytes/sec. So, if you need greater peak
93         rates, use alpha with HZ=1000 :-)
94
95         With classful TBF, limit is just kept for backwards compatibility.
96         It is passed to the default bfifo qdisc - if the inner qdisc is
97         changed the limit is not effective anymore.
98 */
99
100 struct tbf_sched_data
101 {
102 /* Parameters */
103         u32             limit;          /* Maximal length of backlog: bytes */
104         u32             buffer;         /* Token bucket depth/rate: MUST BE >= MTU/B */
105         u32             mtu;
106         u32             max_size;
107         struct qdisc_rate_table *R_tab;
108         struct qdisc_rate_table *P_tab;
109
110 /* Variables */
111         long    tokens;                 /* Current number of B tokens */
112         long    ptokens;                /* Current number of P tokens */
113         psched_time_t   t_c;            /* Time check-point */
114         struct Qdisc    *qdisc;         /* Inner qdisc, default - bfifo queue */
115         struct qdisc_watchdog watchdog; /* Watchdog timer */
116 };
117
118 #define L2T(q,L)   qdisc_l2t((q)->R_tab,L)
119 #define L2T_P(q,L) qdisc_l2t((q)->P_tab,L)
120
121 static int tbf_enqueue(struct sk_buff *skb, struct Qdisc* sch)
122 {
123         struct tbf_sched_data *q = qdisc_priv(sch);
124         int ret;
125
126         if (qdisc_pkt_len(skb) > q->max_size)
127                 return qdisc_reshape_fail(skb, sch);
128
129         ret = qdisc_enqueue(skb, q->qdisc);
130         if (ret != 0) {
131                 if (net_xmit_drop_count(ret))
132                         sch->qstats.drops++;
133                 return ret;
134         }
135
136         sch->q.qlen++;
137         sch->bstats.bytes += qdisc_pkt_len(skb);
138         sch->bstats.packets++;
139         return 0;
140 }
141
142 static int tbf_requeue(struct sk_buff *skb, struct Qdisc* sch)
143 {
144         struct tbf_sched_data *q = qdisc_priv(sch);
145         int ret;
146
147         if ((ret = q->qdisc->ops->requeue(skb, q->qdisc)) == 0) {
148                 sch->q.qlen++;
149                 sch->qstats.requeues++;
150         }
151
152         return ret;
153 }
154
155 static unsigned int tbf_drop(struct Qdisc* sch)
156 {
157         struct tbf_sched_data *q = qdisc_priv(sch);
158         unsigned int len = 0;
159
160         if (q->qdisc->ops->drop && (len = q->qdisc->ops->drop(q->qdisc)) != 0) {
161                 sch->q.qlen--;
162                 sch->qstats.drops++;
163         }
164         return len;
165 }
166
167 static struct sk_buff *tbf_dequeue(struct Qdisc* sch)
168 {
169         struct tbf_sched_data *q = qdisc_priv(sch);
170         struct sk_buff *skb;
171
172         skb = q->qdisc->dequeue(q->qdisc);
173
174         if (skb) {
175                 psched_time_t now;
176                 long toks;
177                 long ptoks = 0;
178                 unsigned int len = qdisc_pkt_len(skb);
179
180                 now = psched_get_time();
181                 toks = psched_tdiff_bounded(now, q->t_c, q->buffer);
182
183                 if (q->P_tab) {
184                         ptoks = toks + q->ptokens;
185                         if (ptoks > (long)q->mtu)
186                                 ptoks = q->mtu;
187                         ptoks -= L2T_P(q, len);
188                 }
189                 toks += q->tokens;
190                 if (toks > (long)q->buffer)
191                         toks = q->buffer;
192                 toks -= L2T(q, len);
193
194                 if ((toks|ptoks) >= 0) {
195                         q->t_c = now;
196                         q->tokens = toks;
197                         q->ptokens = ptoks;
198                         sch->q.qlen--;
199                         sch->flags &= ~TCQ_F_THROTTLED;
200                         return skb;
201                 }
202
203                 qdisc_watchdog_schedule(&q->watchdog,
204                                         now + max_t(long, -toks, -ptoks));
205
206                 /* Maybe we have a shorter packet in the queue,
207                    which can be sent now. It sounds cool,
208                    but, however, this is wrong in principle.
209                    We MUST NOT reorder packets under these circumstances.
210
211                    Really, if we split the flow into independent
212                    subflows, it would be a very good solution.
213                    This is the main idea of all FQ algorithms
214                    (cf. CSZ, HPFQ, HFSC)
215                  */
216
217                 if (q->qdisc->ops->requeue(skb, q->qdisc) != NET_XMIT_SUCCESS) {
218                         /* When requeue fails skb is dropped */
219                         qdisc_tree_decrease_qlen(q->qdisc, 1);
220                         sch->qstats.drops++;
221                 }
222
223                 sch->qstats.overlimits++;
224         }
225         return NULL;
226 }
227
228 static void tbf_reset(struct Qdisc* sch)
229 {
230         struct tbf_sched_data *q = qdisc_priv(sch);
231
232         qdisc_reset(q->qdisc);
233         sch->q.qlen = 0;
234         q->t_c = psched_get_time();
235         q->tokens = q->buffer;
236         q->ptokens = q->mtu;
237         qdisc_watchdog_cancel(&q->watchdog);
238 }
239
240 static const struct nla_policy tbf_policy[TCA_TBF_MAX + 1] = {
241         [TCA_TBF_PARMS] = { .len = sizeof(struct tc_tbf_qopt) },
242         [TCA_TBF_RTAB]  = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
243         [TCA_TBF_PTAB]  = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
244 };
245
246 static int tbf_change(struct Qdisc* sch, struct nlattr *opt)
247 {
248         int err;
249         struct tbf_sched_data *q = qdisc_priv(sch);
250         struct nlattr *tb[TCA_TBF_PTAB + 1];
251         struct tc_tbf_qopt *qopt;
252         struct qdisc_rate_table *rtab = NULL;
253         struct qdisc_rate_table *ptab = NULL;
254         struct Qdisc *child = NULL;
255         int max_size,n;
256
257         err = nla_parse_nested(tb, TCA_TBF_PTAB, opt, tbf_policy);
258         if (err < 0)
259                 return err;
260
261         err = -EINVAL;
262         if (tb[TCA_TBF_PARMS] == NULL)
263                 goto done;
264
265         qopt = nla_data(tb[TCA_TBF_PARMS]);
266         rtab = qdisc_get_rtab(&qopt->rate, tb[TCA_TBF_RTAB]);
267         if (rtab == NULL)
268                 goto done;
269
270         if (qopt->peakrate.rate) {
271                 if (qopt->peakrate.rate > qopt->rate.rate)
272                         ptab = qdisc_get_rtab(&qopt->peakrate, tb[TCA_TBF_PTAB]);
273                 if (ptab == NULL)
274                         goto done;
275         }
276
277         for (n = 0; n < 256; n++)
278                 if (rtab->data[n] > qopt->buffer) break;
279         max_size = (n << qopt->rate.cell_log)-1;
280         if (ptab) {
281                 int size;
282
283                 for (n = 0; n < 256; n++)
284                         if (ptab->data[n] > qopt->mtu) break;
285                 size = (n << qopt->peakrate.cell_log)-1;
286                 if (size < max_size) max_size = size;
287         }
288         if (max_size < 0)
289                 goto done;
290
291         if (qopt->limit > 0) {
292                 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, qopt->limit);
293                 if (IS_ERR(child)) {
294                         err = PTR_ERR(child);
295                         goto done;
296                 }
297         }
298
299         sch_tree_lock(sch);
300         if (child) {
301                 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
302                 qdisc_destroy(xchg(&q->qdisc, child));
303         }
304         q->limit = qopt->limit;
305         q->mtu = qopt->mtu;
306         q->max_size = max_size;
307         q->buffer = qopt->buffer;
308         q->tokens = q->buffer;
309         q->ptokens = q->mtu;
310         rtab = xchg(&q->R_tab, rtab);
311         ptab = xchg(&q->P_tab, ptab);
312         sch_tree_unlock(sch);
313         err = 0;
314 done:
315         if (rtab)
316                 qdisc_put_rtab(rtab);
317         if (ptab)
318                 qdisc_put_rtab(ptab);
319         return err;
320 }
321
322 static int tbf_init(struct Qdisc* sch, struct nlattr *opt)
323 {
324         struct tbf_sched_data *q = qdisc_priv(sch);
325
326         if (opt == NULL)
327                 return -EINVAL;
328
329         q->t_c = psched_get_time();
330         qdisc_watchdog_init(&q->watchdog, sch);
331         q->qdisc = &noop_qdisc;
332
333         return tbf_change(sch, opt);
334 }
335
336 static void tbf_destroy(struct Qdisc *sch)
337 {
338         struct tbf_sched_data *q = qdisc_priv(sch);
339
340         qdisc_watchdog_cancel(&q->watchdog);
341
342         if (q->P_tab)
343                 qdisc_put_rtab(q->P_tab);
344         if (q->R_tab)
345                 qdisc_put_rtab(q->R_tab);
346
347         qdisc_destroy(q->qdisc);
348 }
349
350 static int tbf_dump(struct Qdisc *sch, struct sk_buff *skb)
351 {
352         struct tbf_sched_data *q = qdisc_priv(sch);
353         struct nlattr *nest;
354         struct tc_tbf_qopt opt;
355
356         nest = nla_nest_start(skb, TCA_OPTIONS);
357         if (nest == NULL)
358                 goto nla_put_failure;
359
360         opt.limit = q->limit;
361         opt.rate = q->R_tab->rate;
362         if (q->P_tab)
363                 opt.peakrate = q->P_tab->rate;
364         else
365                 memset(&opt.peakrate, 0, sizeof(opt.peakrate));
366         opt.mtu = q->mtu;
367         opt.buffer = q->buffer;
368         NLA_PUT(skb, TCA_TBF_PARMS, sizeof(opt), &opt);
369
370         nla_nest_end(skb, nest);
371         return skb->len;
372
373 nla_put_failure:
374         nla_nest_cancel(skb, nest);
375         return -1;
376 }
377
378 static int tbf_dump_class(struct Qdisc *sch, unsigned long cl,
379                           struct sk_buff *skb, struct tcmsg *tcm)
380 {
381         struct tbf_sched_data *q = qdisc_priv(sch);
382
383         if (cl != 1)    /* only one class */
384                 return -ENOENT;
385
386         tcm->tcm_handle |= TC_H_MIN(1);
387         tcm->tcm_info = q->qdisc->handle;
388
389         return 0;
390 }
391
392 static int tbf_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
393                      struct Qdisc **old)
394 {
395         struct tbf_sched_data *q = qdisc_priv(sch);
396
397         if (new == NULL)
398                 new = &noop_qdisc;
399
400         sch_tree_lock(sch);
401         *old = xchg(&q->qdisc, new);
402         qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
403         qdisc_reset(*old);
404         sch_tree_unlock(sch);
405
406         return 0;
407 }
408
409 static struct Qdisc *tbf_leaf(struct Qdisc *sch, unsigned long arg)
410 {
411         struct tbf_sched_data *q = qdisc_priv(sch);
412         return q->qdisc;
413 }
414
415 static unsigned long tbf_get(struct Qdisc *sch, u32 classid)
416 {
417         return 1;
418 }
419
420 static void tbf_put(struct Qdisc *sch, unsigned long arg)
421 {
422 }
423
424 static int tbf_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
425                             struct nlattr **tca, unsigned long *arg)
426 {
427         return -ENOSYS;
428 }
429
430 static int tbf_delete(struct Qdisc *sch, unsigned long arg)
431 {
432         return -ENOSYS;
433 }
434
435 static void tbf_walk(struct Qdisc *sch, struct qdisc_walker *walker)
436 {
437         if (!walker->stop) {
438                 if (walker->count >= walker->skip)
439                         if (walker->fn(sch, 1, walker) < 0) {
440                                 walker->stop = 1;
441                                 return;
442                         }
443                 walker->count++;
444         }
445 }
446
447 static struct tcf_proto **tbf_find_tcf(struct Qdisc *sch, unsigned long cl)
448 {
449         return NULL;
450 }
451
452 static const struct Qdisc_class_ops tbf_class_ops =
453 {
454         .graft          =       tbf_graft,
455         .leaf           =       tbf_leaf,
456         .get            =       tbf_get,
457         .put            =       tbf_put,
458         .change         =       tbf_change_class,
459         .delete         =       tbf_delete,
460         .walk           =       tbf_walk,
461         .tcf_chain      =       tbf_find_tcf,
462         .dump           =       tbf_dump_class,
463 };
464
465 static struct Qdisc_ops tbf_qdisc_ops __read_mostly = {
466         .next           =       NULL,
467         .cl_ops         =       &tbf_class_ops,
468         .id             =       "tbf",
469         .priv_size      =       sizeof(struct tbf_sched_data),
470         .enqueue        =       tbf_enqueue,
471         .dequeue        =       tbf_dequeue,
472         .requeue        =       tbf_requeue,
473         .drop           =       tbf_drop,
474         .init           =       tbf_init,
475         .reset          =       tbf_reset,
476         .destroy        =       tbf_destroy,
477         .change         =       tbf_change,
478         .dump           =       tbf_dump,
479         .owner          =       THIS_MODULE,
480 };
481
482 static int __init tbf_module_init(void)
483 {
484         return register_qdisc(&tbf_qdisc_ops);
485 }
486
487 static void __exit tbf_module_exit(void)
488 {
489         unregister_qdisc(&tbf_qdisc_ops);
490 }
491 module_init(tbf_module_init)
492 module_exit(tbf_module_exit)
493 MODULE_LICENSE("GPL");