xref: /linux/net/sched/sch_tbf.c (revision 367b8112fe2ea5c39a7bb4d263dcdd9b612fae18) 
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");
494