xref: /openbmc/linux/net/sched/sch_cbs.c (revision cb1aaebe) 
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/netevent.h>
65 #include <net/netlink.h>
66 #include <net/sch_generic.h>
67 #include <net/pkt_sched.h>
68 
69 static LIST_HEAD(cbs_list);
70 static DEFINE_SPINLOCK(cbs_list_lock);
71 
72 #define BYTES_PER_KBIT (1000LL / 8)
73 
74 struct cbs_sched_data {
75 	bool offload;
76 	int queue;
77 	atomic64_t port_rate; /* in bytes/s */
78 	s64 last; /* timestamp in ns */
79 	s64 credits; /* in bytes */
80 	s32 locredit; /* in bytes */
81 	s32 hicredit; /* in bytes */
82 	s64 sendslope; /* in bytes/s */
83 	s64 idleslope; /* in bytes/s */
84 	struct qdisc_watchdog watchdog;
85 	int (*enqueue)(struct sk_buff *skb, struct Qdisc *sch,
86 		       struct sk_buff **to_free);
87 	struct sk_buff *(*dequeue)(struct Qdisc *sch);
88 	struct Qdisc *qdisc;
89 	struct list_head cbs_list;
90 };
91 
92 static int cbs_child_enqueue(struct sk_buff *skb, struct Qdisc *sch,
93 			     struct Qdisc *child,
94 			     struct sk_buff **to_free)
95 {
96 	unsigned int len = qdisc_pkt_len(skb);
97 	int err;
98 
99 	err = child->ops->enqueue(skb, child, to_free);
100 	if (err != NET_XMIT_SUCCESS)
101 		return err;
102 
103 	sch->qstats.backlog += len;
104 	sch->q.qlen++;
105 
106 	return NET_XMIT_SUCCESS;
107 }
108 
109 static int cbs_enqueue_offload(struct sk_buff *skb, struct Qdisc *sch,
110 			       struct sk_buff **to_free)
111 {
112 	struct cbs_sched_data *q = qdisc_priv(sch);
113 	struct Qdisc *qdisc = q->qdisc;
114 
115 	return cbs_child_enqueue(skb, sch, qdisc, to_free);
116 }
117 
118 static int cbs_enqueue_soft(struct sk_buff *skb, struct Qdisc *sch,
119 			    struct sk_buff **to_free)
120 {
121 	struct cbs_sched_data *q = qdisc_priv(sch);
122 	struct Qdisc *qdisc = q->qdisc;
123 
124 	if (sch->q.qlen == 0 && q->credits > 0) {
125 		/* We need to stop accumulating credits when there's
126 		 * no enqueued packets and q->credits is positive.
127 		 */
128 		q->credits = 0;
129 		q->last = ktime_get_ns();
130 	}
131 
132 	return cbs_child_enqueue(skb, sch, qdisc, to_free);
133 }
134 
135 static int cbs_enqueue(struct sk_buff *skb, struct Qdisc *sch,
136 		       struct sk_buff **to_free)
137 {
138 	struct cbs_sched_data *q = qdisc_priv(sch);
139 
140 	return q->enqueue(skb, sch, to_free);
141 }
142 
143 /* timediff is in ns, slope is in bytes/s */
144 static s64 timediff_to_credits(s64 timediff, s64 slope)
145 {
146 	return div64_s64(timediff * slope, NSEC_PER_SEC);
147 }
148 
149 static s64 delay_from_credits(s64 credits, s64 slope)
150 {
151 	if (unlikely(slope == 0))
152 		return S64_MAX;
153 
154 	return div64_s64(-credits * NSEC_PER_SEC, slope);
155 }
156 
157 static s64 credits_from_len(unsigned int len, s64 slope, s64 port_rate)
158 {
159 	if (unlikely(port_rate == 0))
160 		return S64_MAX;
161 
162 	return div64_s64(len * slope, port_rate);
163 }
164 
165 static struct sk_buff *cbs_child_dequeue(struct Qdisc *sch, struct Qdisc *child)
166 {
167 	struct sk_buff *skb;
168 
169 	skb = child->ops->dequeue(child);
170 	if (!skb)
171 		return NULL;
172 
173 	qdisc_qstats_backlog_dec(sch, skb);
174 	qdisc_bstats_update(sch, skb);
175 	sch->q.qlen--;
176 
177 	return skb;
178 }
179 
180 static struct sk_buff *cbs_dequeue_soft(struct Qdisc *sch)
181 {
182 	struct cbs_sched_data *q = qdisc_priv(sch);
183 	struct Qdisc *qdisc = q->qdisc;
184 	s64 now = ktime_get_ns();
185 	struct sk_buff *skb;
186 	s64 credits;
187 	int len;
188 
189 	if (atomic64_read(&q->port_rate) == -1) {
190 		WARN_ONCE(1, "cbs: dequeue() called with unknown port rate.");
191 		return NULL;
192 	}
193 
194 	if (q->credits < 0) {
195 		credits = timediff_to_credits(now - q->last, q->idleslope);
196 
197 		credits = q->credits + credits;
198 		q->credits = min_t(s64, credits, q->hicredit);
199 
200 		if (q->credits < 0) {
201 			s64 delay;
202 
203 			delay = delay_from_credits(q->credits, q->idleslope);
204 			qdisc_watchdog_schedule_ns(&q->watchdog, now + delay);
205 
206 			q->last = now;
207 
208 			return NULL;
209 		}
210 	}
211 	skb = cbs_child_dequeue(sch, qdisc);
212 	if (!skb)
213 		return NULL;
214 
215 	len = qdisc_pkt_len(skb);
216 
217 	/* As sendslope is a negative number, this will decrease the
218 	 * amount of q->credits.
219 	 */
220 	credits = credits_from_len(len, q->sendslope,
221 				   atomic64_read(&q->port_rate));
222 	credits += q->credits;
223 
224 	q->credits = max_t(s64, credits, q->locredit);
225 	q->last = now;
226 
227 	return skb;
228 }
229 
230 static struct sk_buff *cbs_dequeue_offload(struct Qdisc *sch)
231 {
232 	struct cbs_sched_data *q = qdisc_priv(sch);
233 	struct Qdisc *qdisc = q->qdisc;
234 
235 	return cbs_child_dequeue(sch, qdisc);
236 }
237 
238 static struct sk_buff *cbs_dequeue(struct Qdisc *sch)
239 {
240 	struct cbs_sched_data *q = qdisc_priv(sch);
241 
242 	return q->dequeue(sch);
243 }
244 
245 static const struct nla_policy cbs_policy[TCA_CBS_MAX + 1] = {
246 	[TCA_CBS_PARMS]	= { .len = sizeof(struct tc_cbs_qopt) },
247 };
248 
249 static void cbs_disable_offload(struct net_device *dev,
250 				struct cbs_sched_data *q)
251 {
252 	struct tc_cbs_qopt_offload cbs = { };
253 	const struct net_device_ops *ops;
254 	int err;
255 
256 	if (!q->offload)
257 		return;
258 
259 	q->enqueue = cbs_enqueue_soft;
260 	q->dequeue = cbs_dequeue_soft;
261 
262 	ops = dev->netdev_ops;
263 	if (!ops->ndo_setup_tc)
264 		return;
265 
266 	cbs.queue = q->queue;
267 	cbs.enable = 0;
268 
269 	err = ops->ndo_setup_tc(dev, TC_SETUP_QDISC_CBS, &cbs);
270 	if (err < 0)
271 		pr_warn("Couldn't disable CBS offload for queue %d\n",
272 			cbs.queue);
273 }
274 
275 static int cbs_enable_offload(struct net_device *dev, struct cbs_sched_data *q,
276 			      const struct tc_cbs_qopt *opt,
277 			      struct netlink_ext_ack *extack)
278 {
279 	const struct net_device_ops *ops = dev->netdev_ops;
280 	struct tc_cbs_qopt_offload cbs = { };
281 	int err;
282 
283 	if (!ops->ndo_setup_tc) {
284 		NL_SET_ERR_MSG(extack, "Specified device does not support cbs offload");
285 		return -EOPNOTSUPP;
286 	}
287 
288 	cbs.queue = q->queue;
289 
290 	cbs.enable = 1;
291 	cbs.hicredit = opt->hicredit;
292 	cbs.locredit = opt->locredit;
293 	cbs.idleslope = opt->idleslope;
294 	cbs.sendslope = opt->sendslope;
295 
296 	err = ops->ndo_setup_tc(dev, TC_SETUP_QDISC_CBS, &cbs);
297 	if (err < 0) {
298 		NL_SET_ERR_MSG(extack, "Specified device failed to setup cbs hardware offload");
299 		return err;
300 	}
301 
302 	q->enqueue = cbs_enqueue_offload;
303 	q->dequeue = cbs_dequeue_offload;
304 
305 	return 0;
306 }
307 
308 static void cbs_set_port_rate(struct net_device *dev, struct cbs_sched_data *q)
309 {
310 	struct ethtool_link_ksettings ecmd;
311 	int port_rate = -1;
312 
313 	if (!__ethtool_get_link_ksettings(dev, &ecmd) &&
314 	    ecmd.base.speed != SPEED_UNKNOWN)
315 		port_rate = ecmd.base.speed * 1000 * BYTES_PER_KBIT;
316 
317 	atomic64_set(&q->port_rate, port_rate);
318 	netdev_dbg(dev, "cbs: set %s's port_rate to: %lld, linkspeed: %d\n",
319 		   dev->name, (long long)atomic64_read(&q->port_rate),
320 		   ecmd.base.speed);
321 }
322 
323 static int cbs_dev_notifier(struct notifier_block *nb, unsigned long event,
324 			    void *ptr)
325 {
326 	struct net_device *dev = netdev_notifier_info_to_dev(ptr);
327 	struct cbs_sched_data *q;
328 	struct net_device *qdev;
329 	bool found = false;
330 
331 	ASSERT_RTNL();
332 
333 	if (event != NETDEV_UP && event != NETDEV_CHANGE)
334 		return NOTIFY_DONE;
335 
336 	spin_lock(&cbs_list_lock);
337 	list_for_each_entry(q, &cbs_list, cbs_list) {
338 		qdev = qdisc_dev(q->qdisc);
339 		if (qdev == dev) {
340 			found = true;
341 			break;
342 		}
343 	}
344 	spin_unlock(&cbs_list_lock);
345 
346 	if (found)
347 		cbs_set_port_rate(dev, q);
348 
349 	return NOTIFY_DONE;
350 }
351 
352 static int cbs_change(struct Qdisc *sch, struct nlattr *opt,
353 		      struct netlink_ext_ack *extack)
354 {
355 	struct cbs_sched_data *q = qdisc_priv(sch);
356 	struct net_device *dev = qdisc_dev(sch);
357 	struct nlattr *tb[TCA_CBS_MAX + 1];
358 	struct tc_cbs_qopt *qopt;
359 	int err;
360 
361 	err = nla_parse_nested_deprecated(tb, TCA_CBS_MAX, opt, cbs_policy,
362 					  extack);
363 	if (err < 0)
364 		return err;
365 
366 	if (!tb[TCA_CBS_PARMS]) {
367 		NL_SET_ERR_MSG(extack, "Missing CBS parameter which are mandatory");
368 		return -EINVAL;
369 	}
370 
371 	qopt = nla_data(tb[TCA_CBS_PARMS]);
372 
373 	if (!qopt->offload) {
374 		cbs_set_port_rate(dev, q);
375 		cbs_disable_offload(dev, q);
376 	} else {
377 		err = cbs_enable_offload(dev, q, qopt, extack);
378 		if (err < 0)
379 			return err;
380 	}
381 
382 	/* Everything went OK, save the parameters used. */
383 	q->hicredit = qopt->hicredit;
384 	q->locredit = qopt->locredit;
385 	q->idleslope = qopt->idleslope * BYTES_PER_KBIT;
386 	q->sendslope = qopt->sendslope * BYTES_PER_KBIT;
387 	q->offload = qopt->offload;
388 
389 	return 0;
390 }
391 
392 static int cbs_init(struct Qdisc *sch, struct nlattr *opt,
393 		    struct netlink_ext_ack *extack)
394 {
395 	struct cbs_sched_data *q = qdisc_priv(sch);
396 	struct net_device *dev = qdisc_dev(sch);
397 	int err;
398 
399 	if (!opt) {
400 		NL_SET_ERR_MSG(extack, "Missing CBS qdisc options  which are mandatory");
401 		return -EINVAL;
402 	}
403 
404 	q->qdisc = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
405 				     sch->handle, extack);
406 	if (!q->qdisc)
407 		return -ENOMEM;
408 
409 	qdisc_hash_add(q->qdisc, false);
410 
411 	q->queue = sch->dev_queue - netdev_get_tx_queue(dev, 0);
412 
413 	q->enqueue = cbs_enqueue_soft;
414 	q->dequeue = cbs_dequeue_soft;
415 
416 	qdisc_watchdog_init(&q->watchdog, sch);
417 
418 	err = cbs_change(sch, opt, extack);
419 	if (err)
420 		return err;
421 
422 	if (!q->offload) {
423 		spin_lock(&cbs_list_lock);
424 		list_add(&q->cbs_list, &cbs_list);
425 		spin_unlock(&cbs_list_lock);
426 	}
427 
428 	return 0;
429 }
430 
431 static void cbs_destroy(struct Qdisc *sch)
432 {
433 	struct cbs_sched_data *q = qdisc_priv(sch);
434 	struct net_device *dev = qdisc_dev(sch);
435 
436 	spin_lock(&cbs_list_lock);
437 	list_del(&q->cbs_list);
438 	spin_unlock(&cbs_list_lock);
439 
440 	qdisc_watchdog_cancel(&q->watchdog);
441 	cbs_disable_offload(dev, q);
442 
443 	if (q->qdisc)
444 		qdisc_put(q->qdisc);
445 }
446 
447 static int cbs_dump(struct Qdisc *sch, struct sk_buff *skb)
448 {
449 	struct cbs_sched_data *q = qdisc_priv(sch);
450 	struct tc_cbs_qopt opt = { };
451 	struct nlattr *nest;
452 
453 	nest = nla_nest_start_noflag(skb, TCA_OPTIONS);
454 	if (!nest)
455 		goto nla_put_failure;
456 
457 	opt.hicredit = q->hicredit;
458 	opt.locredit = q->locredit;
459 	opt.sendslope = div64_s64(q->sendslope, BYTES_PER_KBIT);
460 	opt.idleslope = div64_s64(q->idleslope, BYTES_PER_KBIT);
461 	opt.offload = q->offload;
462 
463 	if (nla_put(skb, TCA_CBS_PARMS, sizeof(opt), &opt))
464 		goto nla_put_failure;
465 
466 	return nla_nest_end(skb, nest);
467 
468 nla_put_failure:
469 	nla_nest_cancel(skb, nest);
470 	return -1;
471 }
472 
473 static int cbs_dump_class(struct Qdisc *sch, unsigned long cl,
474 			  struct sk_buff *skb, struct tcmsg *tcm)
475 {
476 	struct cbs_sched_data *q = qdisc_priv(sch);
477 
478 	if (cl != 1 || !q->qdisc)	/* only one class */
479 		return -ENOENT;
480 
481 	tcm->tcm_handle |= TC_H_MIN(1);
482 	tcm->tcm_info = q->qdisc->handle;
483 
484 	return 0;
485 }
486 
487 static int cbs_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
488 		     struct Qdisc **old, struct netlink_ext_ack *extack)
489 {
490 	struct cbs_sched_data *q = qdisc_priv(sch);
491 
492 	if (!new) {
493 		new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
494 					sch->handle, NULL);
495 		if (!new)
496 			new = &noop_qdisc;
497 	}
498 
499 	*old = qdisc_replace(sch, new, &q->qdisc);
500 	return 0;
501 }
502 
503 static struct Qdisc *cbs_leaf(struct Qdisc *sch, unsigned long arg)
504 {
505 	struct cbs_sched_data *q = qdisc_priv(sch);
506 
507 	return q->qdisc;
508 }
509 
510 static unsigned long cbs_find(struct Qdisc *sch, u32 classid)
511 {
512 	return 1;
513 }
514 
515 static void cbs_walk(struct Qdisc *sch, struct qdisc_walker *walker)
516 {
517 	if (!walker->stop) {
518 		if (walker->count >= walker->skip) {
519 			if (walker->fn(sch, 1, walker) < 0) {
520 				walker->stop = 1;
521 				return;
522 			}
523 		}
524 		walker->count++;
525 	}
526 }
527 
528 static const struct Qdisc_class_ops cbs_class_ops = {
529 	.graft		=	cbs_graft,
530 	.leaf		=	cbs_leaf,
531 	.find		=	cbs_find,
532 	.walk		=	cbs_walk,
533 	.dump		=	cbs_dump_class,
534 };
535 
536 static struct Qdisc_ops cbs_qdisc_ops __read_mostly = {
537 	.id		=	"cbs",
538 	.cl_ops		=	&cbs_class_ops,
539 	.priv_size	=	sizeof(struct cbs_sched_data),
540 	.enqueue	=	cbs_enqueue,
541 	.dequeue	=	cbs_dequeue,
542 	.peek		=	qdisc_peek_dequeued,
543 	.init		=	cbs_init,
544 	.reset		=	qdisc_reset_queue,
545 	.destroy	=	cbs_destroy,
546 	.change		=	cbs_change,
547 	.dump		=	cbs_dump,
548 	.owner		=	THIS_MODULE,
549 };
550 
551 static struct notifier_block cbs_device_notifier = {
552 	.notifier_call = cbs_dev_notifier,
553 };
554 
555 static int __init cbs_module_init(void)
556 {
557 	int err = register_netdevice_notifier(&cbs_device_notifier);
558 
559 	if (err)
560 		return err;
561 
562 	return register_qdisc(&cbs_qdisc_ops);
563 }
564 
565 static void __exit cbs_module_exit(void)
566 {
567 	unregister_qdisc(&cbs_qdisc_ops);
568 	unregister_netdevice_notifier(&cbs_device_notifier);
569 }
570 module_init(cbs_module_init)
571 module_exit(cbs_module_exit)
572 MODULE_LICENSE("GPL");
573