Re: [next-queue PATCH v7 4/6] net/sched: Introduce Credit Based Shaper (CBS) qdisc

[Ivan Khoronzhuk <ivan.khoronzhuk@linaro.org>]

On Thu, Oct 12, 2017 at 05:40:03PM -0700, Vinicius Costa Gomes wrote:
> This queueing discipline implements the shaper algorithm defined by
> the 802.1Q-2014 Section 8.6.8.2 and detailed in Annex L.
> 
> It's primary usage is to apply some bandwidth reservation to user
> defined traffic classes, which are mapped to different queues via the
> mqprio qdisc.
> 
> Only a simple software implementation is added for now.
> 
> Signed-off-by: Vinicius Costa Gomes <vinicius.gomes@intel.com>
> Signed-off-by: Jesus Sanchez-Palencia <jesus.sanchez-palencia@intel.com>
> ---
>  include/uapi/linux/pkt_sched.h |  18 +++
>  net/sched/Kconfig              |  11 ++
>  net/sched/Makefile             |   1 +
>  net/sched/sch_cbs.c            | 314 +++++++++++++++++++++++++++++++++++++++++
>  4 files changed, 344 insertions(+)
>  create mode 100644 net/sched/sch_cbs.c
> 
> diff --git a/include/uapi/linux/pkt_sched.h b/include/uapi/linux/pkt_sched.h
> index 099bf5528fed..41e349df4bf4 100644
> --- a/include/uapi/linux/pkt_sched.h
> +++ b/include/uapi/linux/pkt_sched.h
> @@ -871,4 +871,22 @@ struct tc_pie_xstats {
>  	__u32 maxq;             /* maximum queue size */
>  	__u32 ecn_mark;         /* packets marked with ecn*/
>  };
> +
> +/* CBS */
> +struct tc_cbs_qopt {
> +	__u8 offload;
> +	__s32 hicredit;
> +	__s32 locredit;
> +	__s32 idleslope;
> +	__s32 sendslope;
> +};
> +
> +enum {
> +	TCA_CBS_UNSPEC,
> +	TCA_CBS_PARMS,
> +	__TCA_CBS_MAX,
> +};
> +
> +#define TCA_CBS_MAX (__TCA_CBS_MAX - 1)
> +
>  #endif
> diff --git a/net/sched/Kconfig b/net/sched/Kconfig
> index e70ed26485a2..c03d86a7775e 100644
> --- a/net/sched/Kconfig
> +++ b/net/sched/Kconfig
> @@ -172,6 +172,17 @@ config NET_SCH_TBF
>  	  To compile this code as a module, choose M here: the
>  	  module will be called sch_tbf.
>  
> +config NET_SCH_CBS
> +	tristate "Credit Based Shaper (CBS)"
> +	---help---
> +	  Say Y here if you want to use the Credit Based Shaper (CBS) packet
> +	  scheduling algorithm.
> +
> +	  See the top of <file:net/sched/sch_cbs.c> for more details.
> +
> +	  To compile this code as a module, choose M here: the
> +	  module will be called sch_cbs.
> +
>  config NET_SCH_GRED
>  	tristate "Generic Random Early Detection (GRED)"
>  	---help---
> diff --git a/net/sched/Makefile b/net/sched/Makefile
> index 7b915d226de7..80c8f92d162d 100644
> --- a/net/sched/Makefile
> +++ b/net/sched/Makefile
> @@ -52,6 +52,7 @@ obj-$(CONFIG_NET_SCH_FQ_CODEL)	+= sch_fq_codel.o
>  obj-$(CONFIG_NET_SCH_FQ)	+= sch_fq.o
>  obj-$(CONFIG_NET_SCH_HHF)	+= sch_hhf.o
>  obj-$(CONFIG_NET_SCH_PIE)	+= sch_pie.o
> +obj-$(CONFIG_NET_SCH_CBS)	+= sch_cbs.o
>  
>  obj-$(CONFIG_NET_CLS_U32)	+= cls_u32.o
>  obj-$(CONFIG_NET_CLS_ROUTE4)	+= cls_route.o
> diff --git a/net/sched/sch_cbs.c b/net/sched/sch_cbs.c
> new file mode 100644
> index 000000000000..0643587e6dc8
> --- /dev/null
> +++ b/net/sched/sch_cbs.c
> @@ -0,0 +1,314 @@
> +/*
> + * net/sched/sch_cbs.c	Credit Based Shaper
> + *
> + *		This program is free software; you can redistribute it and/or
> + *		modify it under the terms of the GNU General Public License
> + *		as published by the Free Software Foundation; either version
> + *		2 of the License, or (at your option) any later version.
> + *
> + * Authors:	Vinicius Costa Gomes <vinicius.gomes@intel.com>
> + *
> + */
> +
> +/* Credit Based Shaper (CBS)
> + * =========================
> + *
> + * This is a simple rate-limiting shaper aimed at TSN applications on
> + * systems with known traffic workloads.
> + *
> + * Its algorithm is defined by the IEEE 802.1Q-2014 Specification,
> + * Section 8.6.8.2, and explained in more detail in the Annex L of the
> + * same specification.
> + *
> + * There are four tunables to be considered:
> + *
> + *	'idleslope': Idleslope is the rate of credits that is
> + *	accumulated (in kilobits per second) when there is at least
> + *	one packet waiting for transmission. Packets are transmitted
> + *	when the current value of credits is equal or greater than
> + *	zero. When there is no packet to be transmitted the amount of
> + *	credits is set to zero. This is the main tunable of the CBS
> + *	algorithm.
> + *
> + *	'sendslope':
> + *	Sendslope is the rate of credits that is depleted (it should be a
> + *	negative number of kilobits per second) when a transmission is
> + *	ocurring. It can be calculated as follows, (IEEE 802.1Q-2014 Section
> + *	8.6.8.2 item g):
> + *
> + *	sendslope = idleslope - port_transmit_rate
> + *
> + *	'hicredit': Hicredit defines the maximum amount of credits (in
> + *	bytes) that can be accumulated. Hicredit depends on the
> + *	characteristics of interfering traffic,
> + *	'max_interference_size' is the maximum size of any burst of
> + *	traffic that can delay the transmission of a frame that is
> + *	available for transmission for this traffic class, (IEEE
> + *	802.1Q-2014 Annex L, Equation L-3):
> + *
> + *	hicredit = max_interference_size * (idleslope / port_transmit_rate)
> + *
> + *	'locredit': Locredit is the minimum amount of credits that can
> + *	be reached. It is a function of the traffic flowing through
> + *	this qdisc (IEEE 802.1Q-2014 Annex L, Equation L-2):
> + *
> + *	locredit = max_frame_size * (sendslope / port_transmit_rate)
> + */
> +
> +#include <linux/module.h>
> +#include <linux/types.h>
> +#include <linux/kernel.h>
> +#include <linux/string.h>
> +#include <linux/errno.h>
> +#include <linux/skbuff.h>
> +#include <net/netlink.h>
> +#include <net/sch_generic.h>
> +#include <net/pkt_sched.h>
> +
> +#define BYTES_PER_KBIT (1000 / 8)
> +
> +struct cbs_sched_data {
> +	s64 port_rate; /* in bytes/s */
> +	s64 last; /* timestamp in ns */
> +	s64 credits; /* in bytes */
> +	s32 locredit; /* in bytes */
> +	s32 hicredit; /* in bytes */
> +	s32 sendslope; /* in kbits/s */
> +	s32 idleslope; /* in kbits/s */
> +	struct qdisc_watchdog watchdog;
> +	int (*enqueue)(struct sk_buff *skb, struct Qdisc *sch);
> +	struct sk_buff *(*dequeue)(struct Qdisc *sch);
> +};
> +
> +static int cbs_enqueue_soft(struct sk_buff *skb, struct Qdisc *sch)
> +{
> +	struct cbs_sched_data *q = qdisc_priv(sch);
> +
> +	if (sch->q.qlen == 0 && q->credits > 0) {
> +		/* We need to stop accumulating credits when there's
> +		 * no packet enqueued packets and q->credits is
no packet -> no

> +		 * positive.
> +		 */
> +		q->credits = 0;
> +		q->last = ktime_get_ns();
> +	}
> +
> +	return qdisc_enqueue_tail(skb, sch);
> +}
> +
> +static int cbs_enqueue(struct sk_buff *skb, struct Qdisc *sch,
> +		       struct sk_buff **to_free)
> +{
> +	struct cbs_sched_data *q = qdisc_priv(sch);
> +
> +	return q->enqueue(skb, sch);
> +}
> +
> +/* timediff is in ns, slope is in kbps */
> +static s64 timediff_to_credits(s64 timediff, s32 slope)
> +{
> +	s64 credits = timediff * slope * BYTES_PER_KBIT;
> +
> +	do_div(credits, NSEC_PER_SEC);
> +
> +	return credits;
> +}
> +
> +static s64 delay_from_credits(s64 credits, s32 slope)
> +{
> +	s64 rate = slope * BYTES_PER_KBIT;
> +	s64 delay;
> +
> +	if (unlikely(rate == 0))
> +		return S64_MAX;
> +
> +	delay = -credits * NSEC_PER_SEC;
> +	do_div(delay, rate);
> +
> +	return delay;
> +}
> +
> +static s64 credits_from_len(unsigned int len, s32 slope, s64 port_rate)
> +{
> +	/* As do_div() only works on unsigned quantities, convert
> +	 * slope to a positive number here, and credits to a negative
> +	 * number before returning.
> +	 */
> +	s64 rate = -slope * BYTES_PER_KBIT;
> +	s64 credits;
> +
> +	if (unlikely(port_rate == 0))
> +		return S64_MAX;
> +
> +	credits = len * rate;
> +	do_div(credits, port_rate);
> +
> +	return -credits;
> +}
> +
> +static struct sk_buff *cbs_dequeue_soft(struct Qdisc *sch)
> +{
> +	struct cbs_sched_data *q = qdisc_priv(sch);
> +	s64 now = ktime_get_ns();
> +	struct sk_buff *skb;
> +	s64 credits;
> +	int len;
> +
> +	if (q->credits < 0) {
> +		credits = timediff_to_credits(now - q->last, q->idleslope);
Maybe be better to add small optimization by moving some calculations from data
path, I mean, save idle_slope in bytes instead of kbit and converting it for
every packet. Both delay_from_credits() and timediff_to_credits() is used only
once and with idle_slope only...and both of them converting it.

Same for credits_from_len() and send slope, save it in units of port_rate.

> +
> +		credits = q->credits + credits;
> +		q->credits = min_t(s64, credits, q->hicredit);
> +
> +		if (q->credits < 0) {
> +			s64 delay;
> +
> +			delay = delay_from_credits(q->credits, q->idleslope);
> +			qdisc_watchdog_schedule_ns(&q->watchdog, now + delay);
> +
> +			q->last = now;
> +
> +			return NULL;
> +		}
> +	}
> +
> +	skb = qdisc_dequeue_head(sch);
> +	if (!skb)
> +		return NULL;
> +
> +	len = qdisc_pkt_len(skb);
> +
> +	/* As sendslope is a negative number, this will decrease the
> +	 * amount of q->credits.
> +	 */
> +	credits = credits_from_len(len, q->sendslope, q->port_rate);
> +	credits += q->credits;
> +
> +	q->credits = max_t(s64, credits, q->locredit);
> +	q->last = now;
> +
> +	return skb;
> +}
> +
> +static struct sk_buff *cbs_dequeue(struct Qdisc *sch)
> +{
> +	struct cbs_sched_data *q = qdisc_priv(sch);
> +
> +	return q->dequeue(sch);
> +}
> +
> +static const struct nla_policy cbs_policy[TCA_CBS_MAX + 1] = {
> +	[TCA_CBS_PARMS]	= { .len = sizeof(struct tc_cbs_qopt) },
> +};
> +
> +static int cbs_change(struct Qdisc *sch, struct nlattr *opt)
> +{
> +	struct cbs_sched_data *q = qdisc_priv(sch);
> +	struct net_device *dev = qdisc_dev(sch);
> +	struct nlattr *tb[TCA_CBS_MAX + 1];
> +	struct ethtool_link_ksettings ecmd;
> +	struct tc_cbs_qopt *qopt;
> +	s64 link_speed;
> +	int err;
> +
> +	err = nla_parse_nested(tb, TCA_CBS_MAX, opt, cbs_policy, NULL);
> +	if (err < 0)
> +		return err;
> +
> +	if (!tb[TCA_CBS_PARMS])
> +		return -EINVAL;
> +
> +	qopt = nla_data(tb[TCA_CBS_PARMS]);
> +
> +	if (qopt->offload)
> +		return -EOPNOTSUPP;
> +
> +	if (!__ethtool_get_link_ksettings(dev, &ecmd))
> +		link_speed = ecmd.base.speed;
> +	else
> +		link_speed = SPEED_1000;
> +
> +	q->port_rate = link_speed * 1000 * BYTES_PER_KBIT;
> +
> +	q->enqueue = cbs_enqueue_soft;
> +	q->dequeue = cbs_dequeue_soft;
> +
> +	q->hicredit = qopt->hicredit;
> +	q->locredit = qopt->locredit;
> +	q->idleslope = qopt->idleslope;
> +	q->sendslope = qopt->sendslope;
> +
> +	return 0;
> +}
> +
> +static int cbs_init(struct Qdisc *sch, struct nlattr *opt)
> +{
> +	struct cbs_sched_data *q = qdisc_priv(sch);
> +
> +	if (!opt)
> +		return -EINVAL;
> +
> +	qdisc_watchdog_init(&q->watchdog, sch);
> +
> +	return cbs_change(sch, opt);
> +}
> +
> +static void cbs_destroy(struct Qdisc *sch)
> +{
> +	struct cbs_sched_data *q = qdisc_priv(sch);
> +
> +	qdisc_watchdog_cancel(&q->watchdog);
> +}
> +
> +static int cbs_dump(struct Qdisc *sch, struct sk_buff *skb)
> +{
> +	struct cbs_sched_data *q = qdisc_priv(sch);
> +	struct tc_cbs_qopt opt = { };
> +	struct nlattr *nest;
> +
> +	nest = nla_nest_start(skb, TCA_OPTIONS);
> +	if (!nest)
> +		goto nla_put_failure;
> +
> +	opt.hicredit = q->hicredit;
> +	opt.locredit = q->locredit;
> +	opt.sendslope = q->sendslope;
> +	opt.idleslope = q->idleslope;
> +	opt.offload = 0;
> +
> +	if (nla_put(skb, TCA_CBS_PARMS, sizeof(opt), &opt))
> +		goto nla_put_failure;
> +
> +	return nla_nest_end(skb, nest);
> +
> +nla_put_failure:
> +	nla_nest_cancel(skb, nest);
> +	return -1;
> +}
> +
> +static struct Qdisc_ops cbs_qdisc_ops __read_mostly = {
> +	.id		=	"cbs",
> +	.priv_size	=	sizeof(struct cbs_sched_data),
> +	.enqueue	=	cbs_enqueue,
> +	.dequeue	=	cbs_dequeue,
> +	.peek		=	qdisc_peek_dequeued,
> +	.init		=	cbs_init,
> +	.reset		=	qdisc_reset_queue,
> +	.destroy	=	cbs_destroy,
> +	.change		=	cbs_change,
> +	.dump		=	cbs_dump,
> +	.owner		=	THIS_MODULE,
> +};
> +
> +static int __init cbs_module_init(void)
> +{
> +	return register_qdisc(&cbs_qdisc_ops);
> +}
> +
> +static void __exit cbs_module_exit(void)
> +{
> +	unregister_qdisc(&cbs_qdisc_ops);
> +}
> +module_init(cbs_module_init)
> +module_exit(cbs_module_exit)
> +MODULE_LICENSE("GPL");
> -- 
> 2.14.2
>