sch_drr.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515
  1. /*
  2. * net/sched/sch_drr.c Deficit Round Robin scheduler
  3. *
  4. * Copyright (c) 2008 Patrick McHardy <kaber@trash.net>
  5. *
  6. * This program is free software; you can redistribute it and/or
  7. * modify it under the terms of the GNU General Public License
  8. * version 2 as published by the Free Software Foundation.
  9. */
  10. #include <linux/module.h>
  11. #include <linux/slab.h>
  12. #include <linux/init.h>
  13. #include <linux/errno.h>
  14. #include <linux/netdevice.h>
  15. #include <linux/pkt_sched.h>
  16. #include <net/sch_generic.h>
  17. #include <net/pkt_sched.h>
  18. #include <net/pkt_cls.h>
  19. struct drr_class {
  20. struct Qdisc_class_common common;
  21. unsigned int refcnt;
  22. unsigned int filter_cnt;
  23. struct gnet_stats_basic_packed bstats;
  24. struct gnet_stats_queue qstats;
  25. struct gnet_stats_rate_est64 rate_est;
  26. struct list_head alist;
  27. struct Qdisc *qdisc;
  28. u32 quantum;
  29. u32 deficit;
  30. };
  31. struct drr_sched {
  32. struct list_head active;
  33. struct tcf_proto __rcu *filter_list;
  34. struct Qdisc_class_hash clhash;
  35. };
  36. static struct drr_class *drr_find_class(struct Qdisc *sch, u32 classid)
  37. {
  38. struct drr_sched *q = qdisc_priv(sch);
  39. struct Qdisc_class_common *clc;
  40. clc = qdisc_class_find(&q->clhash, classid);
  41. if (clc == NULL)
  42. return NULL;
  43. return container_of(clc, struct drr_class, common);
  44. }
  45. static void drr_purge_queue(struct drr_class *cl)
  46. {
  47. unsigned int len = cl->qdisc->q.qlen;
  48. unsigned int backlog = cl->qdisc->qstats.backlog;
  49. qdisc_reset(cl->qdisc);
  50. qdisc_tree_reduce_backlog(cl->qdisc, len, backlog);
  51. }
  52. static const struct nla_policy drr_policy[TCA_DRR_MAX + 1] = {
  53. [TCA_DRR_QUANTUM] = { .type = NLA_U32 },
  54. };
  55. static int drr_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
  56. struct nlattr **tca, unsigned long *arg)
  57. {
  58. struct drr_sched *q = qdisc_priv(sch);
  59. struct drr_class *cl = (struct drr_class *)*arg;
  60. struct nlattr *opt = tca[TCA_OPTIONS];
  61. struct nlattr *tb[TCA_DRR_MAX + 1];
  62. u32 quantum;
  63. int err;
  64. if (!opt)
  65. return -EINVAL;
  66. err = nla_parse_nested(tb, TCA_DRR_MAX, opt, drr_policy);
  67. if (err < 0)
  68. return err;
  69. if (tb[TCA_DRR_QUANTUM]) {
  70. quantum = nla_get_u32(tb[TCA_DRR_QUANTUM]);
  71. if (quantum == 0)
  72. return -EINVAL;
  73. } else
  74. quantum = psched_mtu(qdisc_dev(sch));
  75. if (cl != NULL) {
  76. if (tca[TCA_RATE]) {
  77. err = gen_replace_estimator(&cl->bstats, NULL,
  78. &cl->rate_est,
  79. NULL,
  80. qdisc_root_sleeping_running(sch),
  81. tca[TCA_RATE]);
  82. if (err)
  83. return err;
  84. }
  85. sch_tree_lock(sch);
  86. if (tb[TCA_DRR_QUANTUM])
  87. cl->quantum = quantum;
  88. sch_tree_unlock(sch);
  89. return 0;
  90. }
  91. cl = kzalloc(sizeof(struct drr_class), GFP_KERNEL);
  92. if (cl == NULL)
  93. return -ENOBUFS;
  94. cl->refcnt = 1;
  95. cl->common.classid = classid;
  96. cl->quantum = quantum;
  97. cl->qdisc = qdisc_create_dflt(sch->dev_queue,
  98. &pfifo_qdisc_ops, classid);
  99. if (cl->qdisc == NULL)
  100. cl->qdisc = &noop_qdisc;
  101. if (tca[TCA_RATE]) {
  102. err = gen_replace_estimator(&cl->bstats, NULL, &cl->rate_est,
  103. NULL,
  104. qdisc_root_sleeping_running(sch),
  105. tca[TCA_RATE]);
  106. if (err) {
  107. qdisc_destroy(cl->qdisc);
  108. kfree(cl);
  109. return err;
  110. }
  111. }
  112. sch_tree_lock(sch);
  113. qdisc_class_hash_insert(&q->clhash, &cl->common);
  114. sch_tree_unlock(sch);
  115. qdisc_class_hash_grow(sch, &q->clhash);
  116. *arg = (unsigned long)cl;
  117. return 0;
  118. }
  119. static void drr_destroy_class(struct Qdisc *sch, struct drr_class *cl)
  120. {
  121. gen_kill_estimator(&cl->bstats, &cl->rate_est);
  122. qdisc_destroy(cl->qdisc);
  123. kfree(cl);
  124. }
  125. static int drr_delete_class(struct Qdisc *sch, unsigned long arg)
  126. {
  127. struct drr_sched *q = qdisc_priv(sch);
  128. struct drr_class *cl = (struct drr_class *)arg;
  129. if (cl->filter_cnt > 0)
  130. return -EBUSY;
  131. sch_tree_lock(sch);
  132. drr_purge_queue(cl);
  133. qdisc_class_hash_remove(&q->clhash, &cl->common);
  134. BUG_ON(--cl->refcnt == 0);
  135. /*
  136. * This shouldn't happen: we "hold" one cops->get() when called
  137. * from tc_ctl_tclass; the destroy method is done from cops->put().
  138. */
  139. sch_tree_unlock(sch);
  140. return 0;
  141. }
  142. static unsigned long drr_get_class(struct Qdisc *sch, u32 classid)
  143. {
  144. struct drr_class *cl = drr_find_class(sch, classid);
  145. if (cl != NULL)
  146. cl->refcnt++;
  147. return (unsigned long)cl;
  148. }
  149. static void drr_put_class(struct Qdisc *sch, unsigned long arg)
  150. {
  151. struct drr_class *cl = (struct drr_class *)arg;
  152. if (--cl->refcnt == 0)
  153. drr_destroy_class(sch, cl);
  154. }
  155. static struct tcf_proto __rcu **drr_tcf_chain(struct Qdisc *sch,
  156. unsigned long cl)
  157. {
  158. struct drr_sched *q = qdisc_priv(sch);
  159. if (cl)
  160. return NULL;
  161. return &q->filter_list;
  162. }
  163. static unsigned long drr_bind_tcf(struct Qdisc *sch, unsigned long parent,
  164. u32 classid)
  165. {
  166. struct drr_class *cl = drr_find_class(sch, classid);
  167. if (cl != NULL)
  168. cl->filter_cnt++;
  169. return (unsigned long)cl;
  170. }
  171. static void drr_unbind_tcf(struct Qdisc *sch, unsigned long arg)
  172. {
  173. struct drr_class *cl = (struct drr_class *)arg;
  174. cl->filter_cnt--;
  175. }
  176. static int drr_graft_class(struct Qdisc *sch, unsigned long arg,
  177. struct Qdisc *new, struct Qdisc **old)
  178. {
  179. struct drr_class *cl = (struct drr_class *)arg;
  180. if (new == NULL) {
  181. new = qdisc_create_dflt(sch->dev_queue,
  182. &pfifo_qdisc_ops, cl->common.classid);
  183. if (new == NULL)
  184. new = &noop_qdisc;
  185. }
  186. *old = qdisc_replace(sch, new, &cl->qdisc);
  187. return 0;
  188. }
  189. static struct Qdisc *drr_class_leaf(struct Qdisc *sch, unsigned long arg)
  190. {
  191. struct drr_class *cl = (struct drr_class *)arg;
  192. return cl->qdisc;
  193. }
  194. static void drr_qlen_notify(struct Qdisc *csh, unsigned long arg)
  195. {
  196. struct drr_class *cl = (struct drr_class *)arg;
  197. if (cl->qdisc->q.qlen == 0)
  198. list_del(&cl->alist);
  199. }
  200. static int drr_dump_class(struct Qdisc *sch, unsigned long arg,
  201. struct sk_buff *skb, struct tcmsg *tcm)
  202. {
  203. struct drr_class *cl = (struct drr_class *)arg;
  204. struct nlattr *nest;
  205. tcm->tcm_parent = TC_H_ROOT;
  206. tcm->tcm_handle = cl->common.classid;
  207. tcm->tcm_info = cl->qdisc->handle;
  208. nest = nla_nest_start(skb, TCA_OPTIONS);
  209. if (nest == NULL)
  210. goto nla_put_failure;
  211. if (nla_put_u32(skb, TCA_DRR_QUANTUM, cl->quantum))
  212. goto nla_put_failure;
  213. return nla_nest_end(skb, nest);
  214. nla_put_failure:
  215. nla_nest_cancel(skb, nest);
  216. return -EMSGSIZE;
  217. }
  218. static int drr_dump_class_stats(struct Qdisc *sch, unsigned long arg,
  219. struct gnet_dump *d)
  220. {
  221. struct drr_class *cl = (struct drr_class *)arg;
  222. __u32 qlen = cl->qdisc->q.qlen;
  223. struct tc_drr_stats xstats;
  224. memset(&xstats, 0, sizeof(xstats));
  225. if (qlen)
  226. xstats.deficit = cl->deficit;
  227. if (gnet_stats_copy_basic(qdisc_root_sleeping_running(sch),
  228. d, NULL, &cl->bstats) < 0 ||
  229. gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 ||
  230. gnet_stats_copy_queue(d, NULL, &cl->qdisc->qstats, qlen) < 0)
  231. return -1;
  232. return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
  233. }
  234. static void drr_walk(struct Qdisc *sch, struct qdisc_walker *arg)
  235. {
  236. struct drr_sched *q = qdisc_priv(sch);
  237. struct drr_class *cl;
  238. unsigned int i;
  239. if (arg->stop)
  240. return;
  241. for (i = 0; i < q->clhash.hashsize; i++) {
  242. hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
  243. if (arg->count < arg->skip) {
  244. arg->count++;
  245. continue;
  246. }
  247. if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
  248. arg->stop = 1;
  249. return;
  250. }
  251. arg->count++;
  252. }
  253. }
  254. }
  255. static struct drr_class *drr_classify(struct sk_buff *skb, struct Qdisc *sch,
  256. int *qerr)
  257. {
  258. struct drr_sched *q = qdisc_priv(sch);
  259. struct drr_class *cl;
  260. struct tcf_result res;
  261. struct tcf_proto *fl;
  262. int result;
  263. if (TC_H_MAJ(skb->priority ^ sch->handle) == 0) {
  264. cl = drr_find_class(sch, skb->priority);
  265. if (cl != NULL)
  266. return cl;
  267. }
  268. *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
  269. fl = rcu_dereference_bh(q->filter_list);
  270. result = tc_classify(skb, fl, &res, false);
  271. if (result >= 0) {
  272. #ifdef CONFIG_NET_CLS_ACT
  273. switch (result) {
  274. case TC_ACT_QUEUED:
  275. case TC_ACT_STOLEN:
  276. *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
  277. case TC_ACT_SHOT:
  278. return NULL;
  279. }
  280. #endif
  281. cl = (struct drr_class *)res.class;
  282. if (cl == NULL)
  283. cl = drr_find_class(sch, res.classid);
  284. return cl;
  285. }
  286. return NULL;
  287. }
  288. static int drr_enqueue(struct sk_buff *skb, struct Qdisc *sch,
  289. struct sk_buff **to_free)
  290. {
  291. struct drr_sched *q = qdisc_priv(sch);
  292. struct drr_class *cl;
  293. int err = 0;
  294. cl = drr_classify(skb, sch, &err);
  295. if (cl == NULL) {
  296. if (err & __NET_XMIT_BYPASS)
  297. qdisc_qstats_drop(sch);
  298. __qdisc_drop(skb, to_free);
  299. return err;
  300. }
  301. err = qdisc_enqueue(skb, cl->qdisc, to_free);
  302. if (unlikely(err != NET_XMIT_SUCCESS)) {
  303. if (net_xmit_drop_count(err)) {
  304. cl->qstats.drops++;
  305. qdisc_qstats_drop(sch);
  306. }
  307. return err;
  308. }
  309. if (cl->qdisc->q.qlen == 1) {
  310. list_add_tail(&cl->alist, &q->active);
  311. cl->deficit = cl->quantum;
  312. }
  313. qdisc_qstats_backlog_inc(sch, skb);
  314. sch->q.qlen++;
  315. return err;
  316. }
  317. static struct sk_buff *drr_dequeue(struct Qdisc *sch)
  318. {
  319. struct drr_sched *q = qdisc_priv(sch);
  320. struct drr_class *cl;
  321. struct sk_buff *skb;
  322. unsigned int len;
  323. if (list_empty(&q->active))
  324. goto out;
  325. while (1) {
  326. cl = list_first_entry(&q->active, struct drr_class, alist);
  327. skb = cl->qdisc->ops->peek(cl->qdisc);
  328. if (skb == NULL) {
  329. qdisc_warn_nonwc(__func__, cl->qdisc);
  330. goto out;
  331. }
  332. len = qdisc_pkt_len(skb);
  333. if (len <= cl->deficit) {
  334. cl->deficit -= len;
  335. skb = qdisc_dequeue_peeked(cl->qdisc);
  336. if (unlikely(skb == NULL))
  337. goto out;
  338. if (cl->qdisc->q.qlen == 0)
  339. list_del(&cl->alist);
  340. bstats_update(&cl->bstats, skb);
  341. qdisc_bstats_update(sch, skb);
  342. qdisc_qstats_backlog_dec(sch, skb);
  343. sch->q.qlen--;
  344. return skb;
  345. }
  346. cl->deficit += cl->quantum;
  347. list_move_tail(&cl->alist, &q->active);
  348. }
  349. out:
  350. return NULL;
  351. }
  352. static int drr_init_qdisc(struct Qdisc *sch, struct nlattr *opt)
  353. {
  354. struct drr_sched *q = qdisc_priv(sch);
  355. int err;
  356. err = qdisc_class_hash_init(&q->clhash);
  357. if (err < 0)
  358. return err;
  359. INIT_LIST_HEAD(&q->active);
  360. return 0;
  361. }
  362. static void drr_reset_qdisc(struct Qdisc *sch)
  363. {
  364. struct drr_sched *q = qdisc_priv(sch);
  365. struct drr_class *cl;
  366. unsigned int i;
  367. for (i = 0; i < q->clhash.hashsize; i++) {
  368. hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
  369. if (cl->qdisc->q.qlen)
  370. list_del(&cl->alist);
  371. qdisc_reset(cl->qdisc);
  372. }
  373. }
  374. sch->qstats.backlog = 0;
  375. sch->q.qlen = 0;
  376. }
  377. static void drr_destroy_qdisc(struct Qdisc *sch)
  378. {
  379. struct drr_sched *q = qdisc_priv(sch);
  380. struct drr_class *cl;
  381. struct hlist_node *next;
  382. unsigned int i;
  383. tcf_destroy_chain(&q->filter_list);
  384. for (i = 0; i < q->clhash.hashsize; i++) {
  385. hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i],
  386. common.hnode)
  387. drr_destroy_class(sch, cl);
  388. }
  389. qdisc_class_hash_destroy(&q->clhash);
  390. }
  391. static const struct Qdisc_class_ops drr_class_ops = {
  392. .change = drr_change_class,
  393. .delete = drr_delete_class,
  394. .get = drr_get_class,
  395. .put = drr_put_class,
  396. .tcf_chain = drr_tcf_chain,
  397. .bind_tcf = drr_bind_tcf,
  398. .unbind_tcf = drr_unbind_tcf,
  399. .graft = drr_graft_class,
  400. .leaf = drr_class_leaf,
  401. .qlen_notify = drr_qlen_notify,
  402. .dump = drr_dump_class,
  403. .dump_stats = drr_dump_class_stats,
  404. .walk = drr_walk,
  405. };
  406. static struct Qdisc_ops drr_qdisc_ops __read_mostly = {
  407. .cl_ops = &drr_class_ops,
  408. .id = "drr",
  409. .priv_size = sizeof(struct drr_sched),
  410. .enqueue = drr_enqueue,
  411. .dequeue = drr_dequeue,
  412. .peek = qdisc_peek_dequeued,
  413. .init = drr_init_qdisc,
  414. .reset = drr_reset_qdisc,
  415. .destroy = drr_destroy_qdisc,
  416. .owner = THIS_MODULE,
  417. };
  418. static int __init drr_init(void)
  419. {
  420. return register_qdisc(&drr_qdisc_ops);
  421. }
  422. static void __exit drr_exit(void)
  423. {
  424. unregister_qdisc(&drr_qdisc_ops);
  425. }
  426. module_init(drr_init);
  427. module_exit(drr_exit);
  428. MODULE_LICENSE("GPL");