sch_cbs.c 14 KB

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