xref: /openbmc/linux/net/sched/sch_cbs.c (revision 56c6eed1) 
1 /*
2  * net/sched/sch_cbs.c	Credit Based Shaper
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:	Vinicius Costa Gomes <vinicius.gomes@intel.com>
10  *
11  */
12 
13 /* Credit Based Shaper (CBS)
14  * =========================
15  *
16  * This is a simple rate-limiting shaper aimed at TSN applications on
17  * systems with known traffic workloads.
18  *
19  * Its algorithm is defined by the IEEE 802.1Q-2014 Specification,
20  * Section 8.6.8.2, and explained in more detail in the Annex L of the
21  * same specification.
22  *
23  * There are four tunables to be considered:
24  *
25  *	'idleslope': Idleslope is the rate of credits that is
26  *	accumulated (in kilobits per second) when there is at least
27  *	one packet waiting for transmission. Packets are transmitted
28  *	when the current value of credits is equal or greater than
29  *	zero. When there is no packet to be transmitted the amount of
30  *	credits is set to zero. This is the main tunable of the CBS
31  *	algorithm.
32  *
33  *	'sendslope':
34  *	Sendslope is the rate of credits that is depleted (it should be a
35  *	negative number of kilobits per second) when a transmission is
36  *	ocurring. It can be calculated as follows, (IEEE 802.1Q-2014 Section
37  *	8.6.8.2 item g):
38  *
39  *	sendslope = idleslope - port_transmit_rate
40  *
41  *	'hicredit': Hicredit defines the maximum amount of credits (in
42  *	bytes) that can be accumulated. Hicredit depends on the
43  *	characteristics of interfering traffic,
44  *	'max_interference_size' is the maximum size of any burst of
45  *	traffic that can delay the transmission of a frame that is
46  *	available for transmission for this traffic class, (IEEE
47  *	802.1Q-2014 Annex L, Equation L-3):
48  *
49  *	hicredit = max_interference_size * (idleslope / port_transmit_rate)
50  *
51  *	'locredit': Locredit is the minimum amount of credits that can
52  *	be reached. It is a function of the traffic flowing through
53  *	this qdisc (IEEE 802.1Q-2014 Annex L, Equation L-2):
54  *
55  *	locredit = max_frame_size * (sendslope / port_transmit_rate)
56  */
57 
58 #include <linux/module.h>
59 #include <linux/types.h>
60 #include <linux/kernel.h>
61 #include <linux/string.h>
62 #include <linux/errno.h>
63 #include <linux/skbuff.h>
64 #include <net/netlink.h>
65 #include <net/sch_generic.h>
66 #include <net/pkt_sched.h>
67 
68 #define BYTES_PER_KBIT (1000LL / 8)
69 
70 struct cbs_sched_data {
71 	bool offload;
72 	int queue;
73 	s64 port_rate; /* in bytes/s */
74 	s64 last; /* timestamp in ns */
75 	s64 credits; /* in bytes */
76 	s32 locredit; /* in bytes */
77 	s32 hicredit; /* in bytes */
78 	s64 sendslope; /* in bytes/s */
79 	s64 idleslope; /* in bytes/s */
80 	struct qdisc_watchdog watchdog;
81 	int (*enqueue)(struct sk_buff *skb, struct Qdisc *sch,
82 		       struct sk_buff **to_free);
83 	struct sk_buff *(*dequeue)(struct Qdisc *sch);
84 	struct Qdisc *qdisc;
85 };
86 
87 static int cbs_child_enqueue(struct sk_buff *skb, struct Qdisc *sch,
88 			     struct Qdisc *child,
89 			     struct sk_buff **to_free)
90 {
91 	unsigned int len = qdisc_pkt_len(skb);
92 	int err;
93 
94 	err = child->ops->enqueue(skb, child, to_free);
95 	if (err != NET_XMIT_SUCCESS)
96 		return err;
97 
98 	sch->qstats.backlog += len;
99 	sch->q.qlen++;
100 
101 	return NET_XMIT_SUCCESS;
102 }
103 
104 static int cbs_enqueue_offload(struct sk_buff *skb, struct Qdisc *sch,
105 			       struct sk_buff **to_free)
106 {
107 	struct cbs_sched_data *q = qdisc_priv(sch);
108 	struct Qdisc *qdisc = q->qdisc;
109 
110 	return cbs_child_enqueue(skb, sch, qdisc, to_free);
111 }
112 
113 static int cbs_enqueue_soft(struct sk_buff *skb, struct Qdisc *sch,
114 			    struct sk_buff **to_free)
115 {
116 	struct cbs_sched_data *q = qdisc_priv(sch);
117 	struct Qdisc *qdisc = q->qdisc;
118 
119 	if (sch->q.qlen == 0 && q->credits > 0) {
120 		/* We need to stop accumulating credits when there's
121 		 * no enqueued packets and q->credits is positive.
122 		 */
123 		q->credits = 0;
124 		q->last = ktime_get_ns();
125 	}
126 
127 	return cbs_child_enqueue(skb, sch, qdisc, to_free);
128 }
129 
130 static int cbs_enqueue(struct sk_buff *skb, struct Qdisc *sch,
131 		       struct sk_buff **to_free)
132 {
133 	struct cbs_sched_data *q = qdisc_priv(sch);
134 
135 	return q->enqueue(skb, sch, to_free);
136 }
137 
138 /* timediff is in ns, slope is in bytes/s */
139 static s64 timediff_to_credits(s64 timediff, s64 slope)
140 {
141 	return div64_s64(timediff * slope, NSEC_PER_SEC);
142 }
143 
144 static s64 delay_from_credits(s64 credits, s64 slope)
145 {
146 	if (unlikely(slope == 0))
147 		return S64_MAX;
148 
149 	return div64_s64(-credits * NSEC_PER_SEC, slope);
150 }
151 
152 static s64 credits_from_len(unsigned int len, s64 slope, s64 port_rate)
153 {
154 	if (unlikely(port_rate == 0))
155 		return S64_MAX;
156 
157 	return div64_s64(len * slope, port_rate);
158 }
159 
160 static struct sk_buff *cbs_child_dequeue(struct Qdisc *sch, struct Qdisc *child)
161 {
162 	struct sk_buff *skb;
163 
164 	skb = child->ops->dequeue(child);
165 	if (!skb)
166 		return NULL;
167 
168 	qdisc_qstats_backlog_dec(sch, skb);
169 	qdisc_bstats_update(sch, skb);
170 	sch->q.qlen--;
171 
172 	return skb;
173 }
174 
175 static struct sk_buff *cbs_dequeue_soft(struct Qdisc *sch)
176 {
177 	struct cbs_sched_data *q = qdisc_priv(sch);
178 	struct Qdisc *qdisc = q->qdisc;
179 	s64 now = ktime_get_ns();
180 	struct sk_buff *skb;
181 	s64 credits;
182 	int len;
183 
184 	if (q->credits < 0) {
185 		credits = timediff_to_credits(now - q->last, q->idleslope);
186 
187 		credits = q->credits + credits;
188 		q->credits = min_t(s64, credits, q->hicredit);
189 
190 		if (q->credits < 0) {
191 			s64 delay;
192 
193 			delay = delay_from_credits(q->credits, q->idleslope);
194 			qdisc_watchdog_schedule_ns(&q->watchdog, now + delay);
195 
196 			q->last = now;
197 
198 			return NULL;
199 		}
200 	}
201 	skb = cbs_child_dequeue(sch, qdisc);
202 	if (!skb)
203 		return NULL;
204 
205 	len = qdisc_pkt_len(skb);
206 
207 	/* As sendslope is a negative number, this will decrease the
208 	 * amount of q->credits.
209 	 */
210 	credits = credits_from_len(len, q->sendslope, q->port_rate);
211 	credits += q->credits;
212 
213 	q->credits = max_t(s64, credits, q->locredit);
214 	q->last = now;
215 
216 	return skb;
217 }
218 
219 static struct sk_buff *cbs_dequeue_offload(struct Qdisc *sch)
220 {
221 	struct cbs_sched_data *q = qdisc_priv(sch);
222 	struct Qdisc *qdisc = q->qdisc;
223 
224 	return cbs_child_dequeue(sch, qdisc);
225 }
226 
227 static struct sk_buff *cbs_dequeue(struct Qdisc *sch)
228 {
229 	struct cbs_sched_data *q = qdisc_priv(sch);
230 
231 	return q->dequeue(sch);
232 }
233 
234 static const struct nla_policy cbs_policy[TCA_CBS_MAX + 1] = {
235 	[TCA_CBS_PARMS]	= { .len = sizeof(struct tc_cbs_qopt) },
236 };
237 
238 static void cbs_disable_offload(struct net_device *dev,
239 				struct cbs_sched_data *q)
240 {
241 	struct tc_cbs_qopt_offload cbs = { };
242 	const struct net_device_ops *ops;
243 	int err;
244 
245 	if (!q->offload)
246 		return;
247 
248 	q->enqueue = cbs_enqueue_soft;
249 	q->dequeue = cbs_dequeue_soft;
250 
251 	ops = dev->netdev_ops;
252 	if (!ops->ndo_setup_tc)
253 		return;
254 
255 	cbs.queue = q->queue;
256 	cbs.enable = 0;
257 
258 	err = ops->ndo_setup_tc(dev, TC_SETUP_QDISC_CBS, &cbs);
259 	if (err < 0)
260 		pr_warn("Couldn't disable CBS offload for queue %d\n",
261 			cbs.queue);
262 }
263 
264 static int cbs_enable_offload(struct net_device *dev, struct cbs_sched_data *q,
265 			      const struct tc_cbs_qopt *opt,
266 			      struct netlink_ext_ack *extack)
267 {
268 	const struct net_device_ops *ops = dev->netdev_ops;
269 	struct tc_cbs_qopt_offload cbs = { };
270 	int err;
271 
272 	if (!ops->ndo_setup_tc) {
273 		NL_SET_ERR_MSG(extack, "Specified device does not support cbs offload");
274 		return -EOPNOTSUPP;
275 	}
276 
277 	cbs.queue = q->queue;
278 
279 	cbs.enable = 1;
280 	cbs.hicredit = opt->hicredit;
281 	cbs.locredit = opt->locredit;
282 	cbs.idleslope = opt->idleslope;
283 	cbs.sendslope = opt->sendslope;
284 
285 	err = ops->ndo_setup_tc(dev, TC_SETUP_QDISC_CBS, &cbs);
286 	if (err < 0) {
287 		NL_SET_ERR_MSG(extack, "Specified device failed to setup cbs hardware offload");
288 		return err;
289 	}
290 
291 	q->enqueue = cbs_enqueue_offload;
292 	q->dequeue = cbs_dequeue_offload;
293 
294 	return 0;
295 }
296 
297 static int cbs_change(struct Qdisc *sch, struct nlattr *opt,
298 		      struct netlink_ext_ack *extack)
299 {
300 	struct cbs_sched_data *q = qdisc_priv(sch);
301 	struct net_device *dev = qdisc_dev(sch);
302 	struct nlattr *tb[TCA_CBS_MAX + 1];
303 	struct tc_cbs_qopt *qopt;
304 	int err;
305 
306 	err = nla_parse_nested(tb, TCA_CBS_MAX, opt, cbs_policy, extack);
307 	if (err < 0)
308 		return err;
309 
310 	if (!tb[TCA_CBS_PARMS]) {
311 		NL_SET_ERR_MSG(extack, "Missing CBS parameter which are mandatory");
312 		return -EINVAL;
313 	}
314 
315 	qopt = nla_data(tb[TCA_CBS_PARMS]);
316 
317 	if (!qopt->offload) {
318 		struct ethtool_link_ksettings ecmd;
319 		s64 link_speed;
320 
321 		if (!__ethtool_get_link_ksettings(dev, &ecmd))
322 			link_speed = ecmd.base.speed;
323 		else
324 			link_speed = SPEED_1000;
325 
326 		q->port_rate = link_speed * 1000 * BYTES_PER_KBIT;
327 
328 		cbs_disable_offload(dev, q);
329 	} else {
330 		err = cbs_enable_offload(dev, q, qopt, extack);
331 		if (err < 0)
332 			return err;
333 	}
334 
335 	/* Everything went OK, save the parameters used. */
336 	q->hicredit = qopt->hicredit;
337 	q->locredit = qopt->locredit;
338 	q->idleslope = qopt->idleslope * BYTES_PER_KBIT;
339 	q->sendslope = qopt->sendslope * BYTES_PER_KBIT;
340 	q->offload = qopt->offload;
341 
342 	return 0;
343 }
344 
345 static int cbs_init(struct Qdisc *sch, struct nlattr *opt,
346 		    struct netlink_ext_ack *extack)
347 {
348 	struct cbs_sched_data *q = qdisc_priv(sch);
349 	struct net_device *dev = qdisc_dev(sch);
350 
351 	if (!opt) {
352 		NL_SET_ERR_MSG(extack, "Missing CBS qdisc options  which are mandatory");
353 		return -EINVAL;
354 	}
355 
356 	q->qdisc = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
357 				     sch->handle, extack);
358 	if (!q->qdisc)
359 		return -ENOMEM;
360 
361 	qdisc_hash_add(q->qdisc, false);
362 
363 	q->queue = sch->dev_queue - netdev_get_tx_queue(dev, 0);
364 
365 	q->enqueue = cbs_enqueue_soft;
366 	q->dequeue = cbs_dequeue_soft;
367 
368 	qdisc_watchdog_init(&q->watchdog, sch);
369 
370 	return cbs_change(sch, opt, extack);
371 }
372 
373 static void cbs_destroy(struct Qdisc *sch)
374 {
375 	struct cbs_sched_data *q = qdisc_priv(sch);
376 	struct net_device *dev = qdisc_dev(sch);
377 
378 	qdisc_watchdog_cancel(&q->watchdog);
379 
380 	cbs_disable_offload(dev, q);
381 
382 	if (q->qdisc)
383 		qdisc_put(q->qdisc);
384 }
385 
386 static int cbs_dump(struct Qdisc *sch, struct sk_buff *skb)
387 {
388 	struct cbs_sched_data *q = qdisc_priv(sch);
389 	struct tc_cbs_qopt opt = { };
390 	struct nlattr *nest;
391 
392 	nest = nla_nest_start(skb, TCA_OPTIONS);
393 	if (!nest)
394 		goto nla_put_failure;
395 
396 	opt.hicredit = q->hicredit;
397 	opt.locredit = q->locredit;
398 	opt.sendslope = div64_s64(q->sendslope, BYTES_PER_KBIT);
399 	opt.idleslope = div64_s64(q->idleslope, BYTES_PER_KBIT);
400 	opt.offload = q->offload;
401 
402 	if (nla_put(skb, TCA_CBS_PARMS, sizeof(opt), &opt))
403 		goto nla_put_failure;
404 
405 	return nla_nest_end(skb, nest);
406 
407 nla_put_failure:
408 	nla_nest_cancel(skb, nest);
409 	return -1;
410 }
411 
412 static int cbs_dump_class(struct Qdisc *sch, unsigned long cl,
413 			  struct sk_buff *skb, struct tcmsg *tcm)
414 {
415 	struct cbs_sched_data *q = qdisc_priv(sch);
416 
417 	if (cl != 1 || !q->qdisc)	/* only one class */
418 		return -ENOENT;
419 
420 	tcm->tcm_handle |= TC_H_MIN(1);
421 	tcm->tcm_info = q->qdisc->handle;
422 
423 	return 0;
424 }
425 
426 static int cbs_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
427 		     struct Qdisc **old, struct netlink_ext_ack *extack)
428 {
429 	struct cbs_sched_data *q = qdisc_priv(sch);
430 
431 	if (!new) {
432 		new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
433 					sch->handle, NULL);
434 		if (!new)
435 			new = &noop_qdisc;
436 	}
437 
438 	*old = qdisc_replace(sch, new, &q->qdisc);
439 	return 0;
440 }
441 
442 static struct Qdisc *cbs_leaf(struct Qdisc *sch, unsigned long arg)
443 {
444 	struct cbs_sched_data *q = qdisc_priv(sch);
445 
446 	return q->qdisc;
447 }
448 
449 static unsigned long cbs_find(struct Qdisc *sch, u32 classid)
450 {
451 	return 1;
452 }
453 
454 static void cbs_walk(struct Qdisc *sch, struct qdisc_walker *walker)
455 {
456 	if (!walker->stop) {
457 		if (walker->count >= walker->skip) {
458 			if (walker->fn(sch, 1, walker) < 0) {
459 				walker->stop = 1;
460 				return;
461 			}
462 		}
463 		walker->count++;
464 	}
465 }
466 
467 static const struct Qdisc_class_ops cbs_class_ops = {
468 	.graft		=	cbs_graft,
469 	.leaf		=	cbs_leaf,
470 	.find		=	cbs_find,
471 	.walk		=	cbs_walk,
472 	.dump		=	cbs_dump_class,
473 };
474 
475 static struct Qdisc_ops cbs_qdisc_ops __read_mostly = {
476 	.id		=	"cbs",
477 	.cl_ops		=	&cbs_class_ops,
478 	.priv_size	=	sizeof(struct cbs_sched_data),
479 	.enqueue	=	cbs_enqueue,
480 	.dequeue	=	cbs_dequeue,
481 	.peek		=	qdisc_peek_dequeued,
482 	.init		=	cbs_init,
483 	.reset		=	qdisc_reset_queue,
484 	.destroy	=	cbs_destroy,
485 	.change		=	cbs_change,
486 	.dump		=	cbs_dump,
487 	.owner		=	THIS_MODULE,
488 };
489 
490 static int __init cbs_module_init(void)
491 {
492 	return register_qdisc(&cbs_qdisc_ops);
493 }
494 
495 static void __exit cbs_module_exit(void)
496 {
497 	unregister_qdisc(&cbs_qdisc_ops);
498 }
499 module_init(cbs_module_init)
500 module_exit(cbs_module_exit)
501 MODULE_LICENSE("GPL");
502