sch_qfq.c 30 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234
  1. /*
  2. * net/sched/sch_qfq.c Quick Fair Queueing Scheduler.
  3. *
  4. * Copyright (c) 2009 Fabio Checconi, Luigi Rizzo, and Paolo Valente.
  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/init.h>
  12. #include <linux/bitops.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. /* Quick Fair Queueing
  20. ===================
  21. Sources:
  22. Fabio Checconi, Luigi Rizzo, and Paolo Valente: "QFQ: Efficient
  23. Packet Scheduling with Tight Bandwidth Distribution Guarantees."
  24. See also:
  25. http://retis.sssup.it/~fabio/linux/qfq/
  26. */
  27. /*
  28. Virtual time computations.
  29. S, F and V are all computed in fixed point arithmetic with
  30. FRAC_BITS decimal bits.
  31. QFQ_MAX_INDEX is the maximum index allowed for a group. We need
  32. one bit per index.
  33. QFQ_MAX_WSHIFT is the maximum power of two supported as a weight.
  34. The layout of the bits is as below:
  35. [ MTU_SHIFT ][ FRAC_BITS ]
  36. [ MAX_INDEX ][ MIN_SLOT_SHIFT ]
  37. ^.__grp->index = 0
  38. *.__grp->slot_shift
  39. where MIN_SLOT_SHIFT is derived by difference from the others.
  40. The max group index corresponds to Lmax/w_min, where
  41. Lmax=1<<MTU_SHIFT, w_min = 1 .
  42. From this, and knowing how many groups (MAX_INDEX) we want,
  43. we can derive the shift corresponding to each group.
  44. Because we often need to compute
  45. F = S + len/w_i and V = V + len/wsum
  46. instead of storing w_i store the value
  47. inv_w = (1<<FRAC_BITS)/w_i
  48. so we can do F = S + len * inv_w * wsum.
  49. We use W_TOT in the formulas so we can easily move between
  50. static and adaptive weight sum.
  51. The per-scheduler-instance data contain all the data structures
  52. for the scheduler: bitmaps and bucket lists.
  53. */
  54. /*
  55. * Maximum number of consecutive slots occupied by backlogged classes
  56. * inside a group.
  57. */
  58. #define QFQ_MAX_SLOTS 32
  59. /*
  60. * Shifts used for class<->group mapping. We allow class weights that are
  61. * in the range [1, 2^MAX_WSHIFT], and we try to map each class i to the
  62. * group with the smallest index that can support the L_i / r_i configured
  63. * for the class.
  64. *
  65. * grp->index is the index of the group; and grp->slot_shift
  66. * is the shift for the corresponding (scaled) sigma_i.
  67. */
  68. #define QFQ_MAX_INDEX 24
  69. #define QFQ_MAX_WSHIFT 12
  70. #define QFQ_MAX_WEIGHT (1<<QFQ_MAX_WSHIFT)
  71. #define QFQ_MAX_WSUM (16*QFQ_MAX_WEIGHT)
  72. #define FRAC_BITS 30 /* fixed point arithmetic */
  73. #define ONE_FP (1UL << FRAC_BITS)
  74. #define IWSUM (ONE_FP/QFQ_MAX_WSUM)
  75. #define QFQ_MTU_SHIFT 16 /* to support TSO/GSO */
  76. #define QFQ_MIN_SLOT_SHIFT (FRAC_BITS + QFQ_MTU_SHIFT - QFQ_MAX_INDEX)
  77. #define QFQ_MIN_LMAX 256 /* min possible lmax for a class */
  78. /*
  79. * Possible group states. These values are used as indexes for the bitmaps
  80. * array of struct qfq_queue.
  81. */
  82. enum qfq_state { ER, IR, EB, IB, QFQ_MAX_STATE };
  83. struct qfq_group;
  84. struct qfq_class {
  85. struct Qdisc_class_common common;
  86. unsigned int refcnt;
  87. unsigned int filter_cnt;
  88. struct gnet_stats_basic_packed bstats;
  89. struct gnet_stats_queue qstats;
  90. struct gnet_stats_rate_est rate_est;
  91. struct Qdisc *qdisc;
  92. struct hlist_node next; /* Link for the slot list. */
  93. u64 S, F; /* flow timestamps (exact) */
  94. /* group we belong to. In principle we would need the index,
  95. * which is log_2(lmax/weight), but we never reference it
  96. * directly, only the group.
  97. */
  98. struct qfq_group *grp;
  99. /* these are copied from the flowset. */
  100. u32 inv_w; /* ONE_FP/weight */
  101. u32 lmax; /* Max packet size for this flow. */
  102. };
  103. struct qfq_group {
  104. u64 S, F; /* group timestamps (approx). */
  105. unsigned int slot_shift; /* Slot shift. */
  106. unsigned int index; /* Group index. */
  107. unsigned int front; /* Index of the front slot. */
  108. unsigned long full_slots; /* non-empty slots */
  109. /* Array of RR lists of active classes. */
  110. struct hlist_head slots[QFQ_MAX_SLOTS];
  111. };
  112. struct qfq_sched {
  113. struct tcf_proto *filter_list;
  114. struct Qdisc_class_hash clhash;
  115. u64 V; /* Precise virtual time. */
  116. u32 wsum; /* weight sum */
  117. unsigned long bitmaps[QFQ_MAX_STATE]; /* Group bitmaps. */
  118. struct qfq_group groups[QFQ_MAX_INDEX + 1]; /* The groups. */
  119. };
  120. static struct qfq_class *qfq_find_class(struct Qdisc *sch, u32 classid)
  121. {
  122. struct qfq_sched *q = qdisc_priv(sch);
  123. struct Qdisc_class_common *clc;
  124. clc = qdisc_class_find(&q->clhash, classid);
  125. if (clc == NULL)
  126. return NULL;
  127. return container_of(clc, struct qfq_class, common);
  128. }
  129. static void qfq_purge_queue(struct qfq_class *cl)
  130. {
  131. unsigned int len = cl->qdisc->q.qlen;
  132. qdisc_reset(cl->qdisc);
  133. qdisc_tree_decrease_qlen(cl->qdisc, len);
  134. }
  135. static const struct nla_policy qfq_policy[TCA_QFQ_MAX + 1] = {
  136. [TCA_QFQ_WEIGHT] = { .type = NLA_U32 },
  137. [TCA_QFQ_LMAX] = { .type = NLA_U32 },
  138. };
  139. /*
  140. * Calculate a flow index, given its weight and maximum packet length.
  141. * index = log_2(maxlen/weight) but we need to apply the scaling.
  142. * This is used only once at flow creation.
  143. */
  144. static int qfq_calc_index(u32 inv_w, unsigned int maxlen)
  145. {
  146. u64 slot_size = (u64)maxlen * inv_w;
  147. unsigned long size_map;
  148. int index = 0;
  149. size_map = slot_size >> QFQ_MIN_SLOT_SHIFT;
  150. if (!size_map)
  151. goto out;
  152. index = __fls(size_map) + 1; /* basically a log_2 */
  153. index -= !(slot_size - (1ULL << (index + QFQ_MIN_SLOT_SHIFT - 1)));
  154. if (index < 0)
  155. index = 0;
  156. out:
  157. pr_debug("qfq calc_index: W = %lu, L = %u, I = %d\n",
  158. (unsigned long) ONE_FP/inv_w, maxlen, index);
  159. return index;
  160. }
  161. /* Length of the next packet (0 if the queue is empty). */
  162. static unsigned int qdisc_peek_len(struct Qdisc *sch)
  163. {
  164. struct sk_buff *skb;
  165. skb = sch->ops->peek(sch);
  166. return skb ? qdisc_pkt_len(skb) : 0;
  167. }
  168. static void qfq_deactivate_class(struct qfq_sched *, struct qfq_class *);
  169. static void qfq_activate_class(struct qfq_sched *q, struct qfq_class *cl,
  170. unsigned int len);
  171. static void qfq_update_class_params(struct qfq_sched *q, struct qfq_class *cl,
  172. u32 lmax, u32 inv_w, int delta_w)
  173. {
  174. int i;
  175. /* update qfq-specific data */
  176. cl->lmax = lmax;
  177. cl->inv_w = inv_w;
  178. i = qfq_calc_index(cl->inv_w, cl->lmax);
  179. cl->grp = &q->groups[i];
  180. q->wsum += delta_w;
  181. }
  182. static void qfq_update_reactivate_class(struct qfq_sched *q,
  183. struct qfq_class *cl,
  184. u32 inv_w, u32 lmax, int delta_w)
  185. {
  186. bool need_reactivation = false;
  187. int i = qfq_calc_index(inv_w, lmax);
  188. if (&q->groups[i] != cl->grp && cl->qdisc->q.qlen > 0) {
  189. /*
  190. * shift cl->F back, to not charge the
  191. * class for the not-yet-served head
  192. * packet
  193. */
  194. cl->F = cl->S;
  195. /* remove class from its slot in the old group */
  196. qfq_deactivate_class(q, cl);
  197. need_reactivation = true;
  198. }
  199. qfq_update_class_params(q, cl, lmax, inv_w, delta_w);
  200. if (need_reactivation) /* activate in new group */
  201. qfq_activate_class(q, cl, qdisc_peek_len(cl->qdisc));
  202. }
  203. static int qfq_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
  204. struct nlattr **tca, unsigned long *arg)
  205. {
  206. struct qfq_sched *q = qdisc_priv(sch);
  207. struct qfq_class *cl = (struct qfq_class *)*arg;
  208. struct nlattr *tb[TCA_QFQ_MAX + 1];
  209. u32 weight, lmax, inv_w;
  210. int err;
  211. int delta_w;
  212. if (tca[TCA_OPTIONS] == NULL) {
  213. pr_notice("qfq: no options\n");
  214. return -EINVAL;
  215. }
  216. err = nla_parse_nested(tb, TCA_QFQ_MAX, tca[TCA_OPTIONS], qfq_policy);
  217. if (err < 0)
  218. return err;
  219. if (tb[TCA_QFQ_WEIGHT]) {
  220. weight = nla_get_u32(tb[TCA_QFQ_WEIGHT]);
  221. if (!weight || weight > (1UL << QFQ_MAX_WSHIFT)) {
  222. pr_notice("qfq: invalid weight %u\n", weight);
  223. return -EINVAL;
  224. }
  225. } else
  226. weight = 1;
  227. inv_w = ONE_FP / weight;
  228. weight = ONE_FP / inv_w;
  229. delta_w = weight - (cl ? ONE_FP / cl->inv_w : 0);
  230. if (q->wsum + delta_w > QFQ_MAX_WSUM) {
  231. pr_notice("qfq: total weight out of range (%u + %u)\n",
  232. delta_w, q->wsum);
  233. return -EINVAL;
  234. }
  235. if (tb[TCA_QFQ_LMAX]) {
  236. lmax = nla_get_u32(tb[TCA_QFQ_LMAX]);
  237. if (lmax < QFQ_MIN_LMAX || lmax > (1UL << QFQ_MTU_SHIFT)) {
  238. pr_notice("qfq: invalid max length %u\n", lmax);
  239. return -EINVAL;
  240. }
  241. } else
  242. lmax = psched_mtu(qdisc_dev(sch));
  243. if (cl != NULL) {
  244. if (tca[TCA_RATE]) {
  245. err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
  246. qdisc_root_sleeping_lock(sch),
  247. tca[TCA_RATE]);
  248. if (err)
  249. return err;
  250. }
  251. if (lmax == cl->lmax && inv_w == cl->inv_w)
  252. return 0; /* nothing to update */
  253. sch_tree_lock(sch);
  254. qfq_update_reactivate_class(q, cl, inv_w, lmax, delta_w);
  255. sch_tree_unlock(sch);
  256. return 0;
  257. }
  258. cl = kzalloc(sizeof(struct qfq_class), GFP_KERNEL);
  259. if (cl == NULL)
  260. return -ENOBUFS;
  261. cl->refcnt = 1;
  262. cl->common.classid = classid;
  263. qfq_update_class_params(q, cl, lmax, inv_w, delta_w);
  264. cl->qdisc = qdisc_create_dflt(sch->dev_queue,
  265. &pfifo_qdisc_ops, classid);
  266. if (cl->qdisc == NULL)
  267. cl->qdisc = &noop_qdisc;
  268. if (tca[TCA_RATE]) {
  269. err = gen_new_estimator(&cl->bstats, &cl->rate_est,
  270. qdisc_root_sleeping_lock(sch),
  271. tca[TCA_RATE]);
  272. if (err) {
  273. qdisc_destroy(cl->qdisc);
  274. kfree(cl);
  275. return err;
  276. }
  277. }
  278. sch_tree_lock(sch);
  279. qdisc_class_hash_insert(&q->clhash, &cl->common);
  280. sch_tree_unlock(sch);
  281. qdisc_class_hash_grow(sch, &q->clhash);
  282. *arg = (unsigned long)cl;
  283. return 0;
  284. }
  285. static void qfq_destroy_class(struct Qdisc *sch, struct qfq_class *cl)
  286. {
  287. struct qfq_sched *q = qdisc_priv(sch);
  288. if (cl->inv_w) {
  289. q->wsum -= ONE_FP / cl->inv_w;
  290. cl->inv_w = 0;
  291. }
  292. gen_kill_estimator(&cl->bstats, &cl->rate_est);
  293. qdisc_destroy(cl->qdisc);
  294. kfree(cl);
  295. }
  296. static int qfq_delete_class(struct Qdisc *sch, unsigned long arg)
  297. {
  298. struct qfq_sched *q = qdisc_priv(sch);
  299. struct qfq_class *cl = (struct qfq_class *)arg;
  300. if (cl->filter_cnt > 0)
  301. return -EBUSY;
  302. sch_tree_lock(sch);
  303. qfq_purge_queue(cl);
  304. qdisc_class_hash_remove(&q->clhash, &cl->common);
  305. BUG_ON(--cl->refcnt == 0);
  306. /*
  307. * This shouldn't happen: we "hold" one cops->get() when called
  308. * from tc_ctl_tclass; the destroy method is done from cops->put().
  309. */
  310. sch_tree_unlock(sch);
  311. return 0;
  312. }
  313. static unsigned long qfq_get_class(struct Qdisc *sch, u32 classid)
  314. {
  315. struct qfq_class *cl = qfq_find_class(sch, classid);
  316. if (cl != NULL)
  317. cl->refcnt++;
  318. return (unsigned long)cl;
  319. }
  320. static void qfq_put_class(struct Qdisc *sch, unsigned long arg)
  321. {
  322. struct qfq_class *cl = (struct qfq_class *)arg;
  323. if (--cl->refcnt == 0)
  324. qfq_destroy_class(sch, cl);
  325. }
  326. static struct tcf_proto **qfq_tcf_chain(struct Qdisc *sch, unsigned long cl)
  327. {
  328. struct qfq_sched *q = qdisc_priv(sch);
  329. if (cl)
  330. return NULL;
  331. return &q->filter_list;
  332. }
  333. static unsigned long qfq_bind_tcf(struct Qdisc *sch, unsigned long parent,
  334. u32 classid)
  335. {
  336. struct qfq_class *cl = qfq_find_class(sch, classid);
  337. if (cl != NULL)
  338. cl->filter_cnt++;
  339. return (unsigned long)cl;
  340. }
  341. static void qfq_unbind_tcf(struct Qdisc *sch, unsigned long arg)
  342. {
  343. struct qfq_class *cl = (struct qfq_class *)arg;
  344. cl->filter_cnt--;
  345. }
  346. static int qfq_graft_class(struct Qdisc *sch, unsigned long arg,
  347. struct Qdisc *new, struct Qdisc **old)
  348. {
  349. struct qfq_class *cl = (struct qfq_class *)arg;
  350. if (new == NULL) {
  351. new = qdisc_create_dflt(sch->dev_queue,
  352. &pfifo_qdisc_ops, cl->common.classid);
  353. if (new == NULL)
  354. new = &noop_qdisc;
  355. }
  356. sch_tree_lock(sch);
  357. qfq_purge_queue(cl);
  358. *old = cl->qdisc;
  359. cl->qdisc = new;
  360. sch_tree_unlock(sch);
  361. return 0;
  362. }
  363. static struct Qdisc *qfq_class_leaf(struct Qdisc *sch, unsigned long arg)
  364. {
  365. struct qfq_class *cl = (struct qfq_class *)arg;
  366. return cl->qdisc;
  367. }
  368. static int qfq_dump_class(struct Qdisc *sch, unsigned long arg,
  369. struct sk_buff *skb, struct tcmsg *tcm)
  370. {
  371. struct qfq_class *cl = (struct qfq_class *)arg;
  372. struct nlattr *nest;
  373. tcm->tcm_parent = TC_H_ROOT;
  374. tcm->tcm_handle = cl->common.classid;
  375. tcm->tcm_info = cl->qdisc->handle;
  376. nest = nla_nest_start(skb, TCA_OPTIONS);
  377. if (nest == NULL)
  378. goto nla_put_failure;
  379. if (nla_put_u32(skb, TCA_QFQ_WEIGHT, ONE_FP/cl->inv_w) ||
  380. nla_put_u32(skb, TCA_QFQ_LMAX, cl->lmax))
  381. goto nla_put_failure;
  382. return nla_nest_end(skb, nest);
  383. nla_put_failure:
  384. nla_nest_cancel(skb, nest);
  385. return -EMSGSIZE;
  386. }
  387. static int qfq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
  388. struct gnet_dump *d)
  389. {
  390. struct qfq_class *cl = (struct qfq_class *)arg;
  391. struct tc_qfq_stats xstats;
  392. memset(&xstats, 0, sizeof(xstats));
  393. cl->qdisc->qstats.qlen = cl->qdisc->q.qlen;
  394. xstats.weight = ONE_FP/cl->inv_w;
  395. xstats.lmax = cl->lmax;
  396. if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
  397. gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 ||
  398. gnet_stats_copy_queue(d, &cl->qdisc->qstats) < 0)
  399. return -1;
  400. return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
  401. }
  402. static void qfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
  403. {
  404. struct qfq_sched *q = qdisc_priv(sch);
  405. struct qfq_class *cl;
  406. struct hlist_node *n;
  407. unsigned int i;
  408. if (arg->stop)
  409. return;
  410. for (i = 0; i < q->clhash.hashsize; i++) {
  411. hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
  412. if (arg->count < arg->skip) {
  413. arg->count++;
  414. continue;
  415. }
  416. if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
  417. arg->stop = 1;
  418. return;
  419. }
  420. arg->count++;
  421. }
  422. }
  423. }
  424. static struct qfq_class *qfq_classify(struct sk_buff *skb, struct Qdisc *sch,
  425. int *qerr)
  426. {
  427. struct qfq_sched *q = qdisc_priv(sch);
  428. struct qfq_class *cl;
  429. struct tcf_result res;
  430. int result;
  431. if (TC_H_MAJ(skb->priority ^ sch->handle) == 0) {
  432. pr_debug("qfq_classify: found %d\n", skb->priority);
  433. cl = qfq_find_class(sch, skb->priority);
  434. if (cl != NULL)
  435. return cl;
  436. }
  437. *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
  438. result = tc_classify(skb, q->filter_list, &res);
  439. if (result >= 0) {
  440. #ifdef CONFIG_NET_CLS_ACT
  441. switch (result) {
  442. case TC_ACT_QUEUED:
  443. case TC_ACT_STOLEN:
  444. *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
  445. case TC_ACT_SHOT:
  446. return NULL;
  447. }
  448. #endif
  449. cl = (struct qfq_class *)res.class;
  450. if (cl == NULL)
  451. cl = qfq_find_class(sch, res.classid);
  452. return cl;
  453. }
  454. return NULL;
  455. }
  456. /* Generic comparison function, handling wraparound. */
  457. static inline int qfq_gt(u64 a, u64 b)
  458. {
  459. return (s64)(a - b) > 0;
  460. }
  461. /* Round a precise timestamp to its slotted value. */
  462. static inline u64 qfq_round_down(u64 ts, unsigned int shift)
  463. {
  464. return ts & ~((1ULL << shift) - 1);
  465. }
  466. /* return the pointer to the group with lowest index in the bitmap */
  467. static inline struct qfq_group *qfq_ffs(struct qfq_sched *q,
  468. unsigned long bitmap)
  469. {
  470. int index = __ffs(bitmap);
  471. return &q->groups[index];
  472. }
  473. /* Calculate a mask to mimic what would be ffs_from(). */
  474. static inline unsigned long mask_from(unsigned long bitmap, int from)
  475. {
  476. return bitmap & ~((1UL << from) - 1);
  477. }
  478. /*
  479. * The state computation relies on ER=0, IR=1, EB=2, IB=3
  480. * First compute eligibility comparing grp->S, q->V,
  481. * then check if someone is blocking us and possibly add EB
  482. */
  483. static int qfq_calc_state(struct qfq_sched *q, const struct qfq_group *grp)
  484. {
  485. /* if S > V we are not eligible */
  486. unsigned int state = qfq_gt(grp->S, q->V);
  487. unsigned long mask = mask_from(q->bitmaps[ER], grp->index);
  488. struct qfq_group *next;
  489. if (mask) {
  490. next = qfq_ffs(q, mask);
  491. if (qfq_gt(grp->F, next->F))
  492. state |= EB;
  493. }
  494. return state;
  495. }
  496. /*
  497. * In principle
  498. * q->bitmaps[dst] |= q->bitmaps[src] & mask;
  499. * q->bitmaps[src] &= ~mask;
  500. * but we should make sure that src != dst
  501. */
  502. static inline void qfq_move_groups(struct qfq_sched *q, unsigned long mask,
  503. int src, int dst)
  504. {
  505. q->bitmaps[dst] |= q->bitmaps[src] & mask;
  506. q->bitmaps[src] &= ~mask;
  507. }
  508. static void qfq_unblock_groups(struct qfq_sched *q, int index, u64 old_F)
  509. {
  510. unsigned long mask = mask_from(q->bitmaps[ER], index + 1);
  511. struct qfq_group *next;
  512. if (mask) {
  513. next = qfq_ffs(q, mask);
  514. if (!qfq_gt(next->F, old_F))
  515. return;
  516. }
  517. mask = (1UL << index) - 1;
  518. qfq_move_groups(q, mask, EB, ER);
  519. qfq_move_groups(q, mask, IB, IR);
  520. }
  521. /*
  522. * perhaps
  523. *
  524. old_V ^= q->V;
  525. old_V >>= QFQ_MIN_SLOT_SHIFT;
  526. if (old_V) {
  527. ...
  528. }
  529. *
  530. */
  531. static void qfq_make_eligible(struct qfq_sched *q, u64 old_V)
  532. {
  533. unsigned long vslot = q->V >> QFQ_MIN_SLOT_SHIFT;
  534. unsigned long old_vslot = old_V >> QFQ_MIN_SLOT_SHIFT;
  535. if (vslot != old_vslot) {
  536. unsigned long mask = (1UL << fls(vslot ^ old_vslot)) - 1;
  537. qfq_move_groups(q, mask, IR, ER);
  538. qfq_move_groups(q, mask, IB, EB);
  539. }
  540. }
  541. /*
  542. * If the weight and lmax (max_pkt_size) of the classes do not change,
  543. * then QFQ guarantees that the slot index is never higher than
  544. * 2 + ((1<<QFQ_MTU_SHIFT)/QFQ_MIN_LMAX) * (QFQ_MAX_WEIGHT/QFQ_MAX_WSUM).
  545. *
  546. * With the current values of the above constants, the index is
  547. * then guaranteed to never be higher than 2 + 256 * (1 / 16) = 18.
  548. *
  549. * When the weight of a class is increased or the lmax of the class is
  550. * decreased, a new class with smaller slot size may happen to be
  551. * activated. The activation of this class should be properly delayed
  552. * to when the service of the class has finished in the ideal system
  553. * tracked by QFQ. If the activation of the class is not delayed to
  554. * this reference time instant, then this class may be unjustly served
  555. * before other classes waiting for service. This may cause
  556. * (unfrequently) the above bound to the slot index to be violated for
  557. * some of these unlucky classes.
  558. *
  559. * Instead of delaying the activation of the new class, which is quite
  560. * complex, the following inaccurate but simple solution is used: if
  561. * the slot index is higher than QFQ_MAX_SLOTS-2, then the timestamps
  562. * of the class are shifted backward so as to let the slot index
  563. * become equal to QFQ_MAX_SLOTS-2. This threshold is used because, if
  564. * the slot index is above it, then the data structure implementing
  565. * the bucket list either gets immediately corrupted or may get
  566. * corrupted on a possible next packet arrival that causes the start
  567. * time of the group to be shifted backward.
  568. */
  569. static void qfq_slot_insert(struct qfq_group *grp, struct qfq_class *cl,
  570. u64 roundedS)
  571. {
  572. u64 slot = (roundedS - grp->S) >> grp->slot_shift;
  573. unsigned int i; /* slot index in the bucket list */
  574. if (unlikely(slot > QFQ_MAX_SLOTS - 2)) {
  575. u64 deltaS = roundedS - grp->S -
  576. ((u64)(QFQ_MAX_SLOTS - 2)<<grp->slot_shift);
  577. cl->S -= deltaS;
  578. cl->F -= deltaS;
  579. slot = QFQ_MAX_SLOTS - 2;
  580. }
  581. i = (grp->front + slot) % QFQ_MAX_SLOTS;
  582. hlist_add_head(&cl->next, &grp->slots[i]);
  583. __set_bit(slot, &grp->full_slots);
  584. }
  585. /* Maybe introduce hlist_first_entry?? */
  586. static struct qfq_class *qfq_slot_head(struct qfq_group *grp)
  587. {
  588. return hlist_entry(grp->slots[grp->front].first,
  589. struct qfq_class, next);
  590. }
  591. /*
  592. * remove the entry from the slot
  593. */
  594. static void qfq_front_slot_remove(struct qfq_group *grp)
  595. {
  596. struct qfq_class *cl = qfq_slot_head(grp);
  597. BUG_ON(!cl);
  598. hlist_del(&cl->next);
  599. if (hlist_empty(&grp->slots[grp->front]))
  600. __clear_bit(0, &grp->full_slots);
  601. }
  602. /*
  603. * Returns the first full queue in a group. As a side effect,
  604. * adjust the bucket list so the first non-empty bucket is at
  605. * position 0 in full_slots.
  606. */
  607. static struct qfq_class *qfq_slot_scan(struct qfq_group *grp)
  608. {
  609. unsigned int i;
  610. pr_debug("qfq slot_scan: grp %u full %#lx\n",
  611. grp->index, grp->full_slots);
  612. if (grp->full_slots == 0)
  613. return NULL;
  614. i = __ffs(grp->full_slots); /* zero based */
  615. if (i > 0) {
  616. grp->front = (grp->front + i) % QFQ_MAX_SLOTS;
  617. grp->full_slots >>= i;
  618. }
  619. return qfq_slot_head(grp);
  620. }
  621. /*
  622. * adjust the bucket list. When the start time of a group decreases,
  623. * we move the index down (modulo QFQ_MAX_SLOTS) so we don't need to
  624. * move the objects. The mask of occupied slots must be shifted
  625. * because we use ffs() to find the first non-empty slot.
  626. * This covers decreases in the group's start time, but what about
  627. * increases of the start time ?
  628. * Here too we should make sure that i is less than 32
  629. */
  630. static void qfq_slot_rotate(struct qfq_group *grp, u64 roundedS)
  631. {
  632. unsigned int i = (grp->S - roundedS) >> grp->slot_shift;
  633. grp->full_slots <<= i;
  634. grp->front = (grp->front - i) % QFQ_MAX_SLOTS;
  635. }
  636. static void qfq_update_eligible(struct qfq_sched *q, u64 old_V)
  637. {
  638. struct qfq_group *grp;
  639. unsigned long ineligible;
  640. ineligible = q->bitmaps[IR] | q->bitmaps[IB];
  641. if (ineligible) {
  642. if (!q->bitmaps[ER]) {
  643. grp = qfq_ffs(q, ineligible);
  644. if (qfq_gt(grp->S, q->V))
  645. q->V = grp->S;
  646. }
  647. qfq_make_eligible(q, old_V);
  648. }
  649. }
  650. /*
  651. * Updates the class, returns true if also the group needs to be updated.
  652. */
  653. static bool qfq_update_class(struct qfq_group *grp, struct qfq_class *cl)
  654. {
  655. unsigned int len = qdisc_peek_len(cl->qdisc);
  656. cl->S = cl->F;
  657. if (!len)
  658. qfq_front_slot_remove(grp); /* queue is empty */
  659. else {
  660. u64 roundedS;
  661. cl->F = cl->S + (u64)len * cl->inv_w;
  662. roundedS = qfq_round_down(cl->S, grp->slot_shift);
  663. if (roundedS == grp->S)
  664. return false;
  665. qfq_front_slot_remove(grp);
  666. qfq_slot_insert(grp, cl, roundedS);
  667. }
  668. return true;
  669. }
  670. static struct sk_buff *qfq_dequeue(struct Qdisc *sch)
  671. {
  672. struct qfq_sched *q = qdisc_priv(sch);
  673. struct qfq_group *grp;
  674. struct qfq_class *cl;
  675. struct sk_buff *skb;
  676. unsigned int len;
  677. u64 old_V;
  678. if (!q->bitmaps[ER])
  679. return NULL;
  680. grp = qfq_ffs(q, q->bitmaps[ER]);
  681. cl = qfq_slot_head(grp);
  682. skb = qdisc_dequeue_peeked(cl->qdisc);
  683. if (!skb) {
  684. WARN_ONCE(1, "qfq_dequeue: non-workconserving leaf\n");
  685. return NULL;
  686. }
  687. sch->q.qlen--;
  688. qdisc_bstats_update(sch, skb);
  689. old_V = q->V;
  690. len = qdisc_pkt_len(skb);
  691. q->V += (u64)len * IWSUM;
  692. pr_debug("qfq dequeue: len %u F %lld now %lld\n",
  693. len, (unsigned long long) cl->F, (unsigned long long) q->V);
  694. if (qfq_update_class(grp, cl)) {
  695. u64 old_F = grp->F;
  696. cl = qfq_slot_scan(grp);
  697. if (!cl)
  698. __clear_bit(grp->index, &q->bitmaps[ER]);
  699. else {
  700. u64 roundedS = qfq_round_down(cl->S, grp->slot_shift);
  701. unsigned int s;
  702. if (grp->S == roundedS)
  703. goto skip_unblock;
  704. grp->S = roundedS;
  705. grp->F = roundedS + (2ULL << grp->slot_shift);
  706. __clear_bit(grp->index, &q->bitmaps[ER]);
  707. s = qfq_calc_state(q, grp);
  708. __set_bit(grp->index, &q->bitmaps[s]);
  709. }
  710. qfq_unblock_groups(q, grp->index, old_F);
  711. }
  712. skip_unblock:
  713. qfq_update_eligible(q, old_V);
  714. return skb;
  715. }
  716. /*
  717. * Assign a reasonable start time for a new flow k in group i.
  718. * Admissible values for \hat(F) are multiples of \sigma_i
  719. * no greater than V+\sigma_i . Larger values mean that
  720. * we had a wraparound so we consider the timestamp to be stale.
  721. *
  722. * If F is not stale and F >= V then we set S = F.
  723. * Otherwise we should assign S = V, but this may violate
  724. * the ordering in ER. So, if we have groups in ER, set S to
  725. * the F_j of the first group j which would be blocking us.
  726. * We are guaranteed not to move S backward because
  727. * otherwise our group i would still be blocked.
  728. */
  729. static void qfq_update_start(struct qfq_sched *q, struct qfq_class *cl)
  730. {
  731. unsigned long mask;
  732. u64 limit, roundedF;
  733. int slot_shift = cl->grp->slot_shift;
  734. roundedF = qfq_round_down(cl->F, slot_shift);
  735. limit = qfq_round_down(q->V, slot_shift) + (1ULL << slot_shift);
  736. if (!qfq_gt(cl->F, q->V) || qfq_gt(roundedF, limit)) {
  737. /* timestamp was stale */
  738. mask = mask_from(q->bitmaps[ER], cl->grp->index);
  739. if (mask) {
  740. struct qfq_group *next = qfq_ffs(q, mask);
  741. if (qfq_gt(roundedF, next->F)) {
  742. if (qfq_gt(limit, next->F))
  743. cl->S = next->F;
  744. else /* preserve timestamp correctness */
  745. cl->S = limit;
  746. return;
  747. }
  748. }
  749. cl->S = q->V;
  750. } else /* timestamp is not stale */
  751. cl->S = cl->F;
  752. }
  753. static int qfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
  754. {
  755. struct qfq_sched *q = qdisc_priv(sch);
  756. struct qfq_class *cl;
  757. int err = 0;
  758. cl = qfq_classify(skb, sch, &err);
  759. if (cl == NULL) {
  760. if (err & __NET_XMIT_BYPASS)
  761. sch->qstats.drops++;
  762. kfree_skb(skb);
  763. return err;
  764. }
  765. pr_debug("qfq_enqueue: cl = %x\n", cl->common.classid);
  766. if (unlikely(cl->lmax < qdisc_pkt_len(skb))) {
  767. pr_debug("qfq: increasing maxpkt from %u to %u for class %u",
  768. cl->lmax, qdisc_pkt_len(skb), cl->common.classid);
  769. qfq_update_reactivate_class(q, cl, cl->inv_w,
  770. qdisc_pkt_len(skb), 0);
  771. }
  772. err = qdisc_enqueue(skb, cl->qdisc);
  773. if (unlikely(err != NET_XMIT_SUCCESS)) {
  774. pr_debug("qfq_enqueue: enqueue failed %d\n", err);
  775. if (net_xmit_drop_count(err)) {
  776. cl->qstats.drops++;
  777. sch->qstats.drops++;
  778. }
  779. return err;
  780. }
  781. bstats_update(&cl->bstats, skb);
  782. ++sch->q.qlen;
  783. /* If the new skb is not the head of queue, then done here. */
  784. if (cl->qdisc->q.qlen != 1)
  785. return err;
  786. /* If reach this point, queue q was idle */
  787. qfq_activate_class(q, cl, qdisc_pkt_len(skb));
  788. return err;
  789. }
  790. /*
  791. * Handle class switch from idle to backlogged.
  792. */
  793. static void qfq_activate_class(struct qfq_sched *q, struct qfq_class *cl,
  794. unsigned int pkt_len)
  795. {
  796. struct qfq_group *grp = cl->grp;
  797. u64 roundedS;
  798. int s;
  799. qfq_update_start(q, cl);
  800. /* compute new finish time and rounded start. */
  801. cl->F = cl->S + (u64)pkt_len * cl->inv_w;
  802. roundedS = qfq_round_down(cl->S, grp->slot_shift);
  803. /*
  804. * insert cl in the correct bucket.
  805. * If cl->S >= grp->S we don't need to adjust the
  806. * bucket list and simply go to the insertion phase.
  807. * Otherwise grp->S is decreasing, we must make room
  808. * in the bucket list, and also recompute the group state.
  809. * Finally, if there were no flows in this group and nobody
  810. * was in ER make sure to adjust V.
  811. */
  812. if (grp->full_slots) {
  813. if (!qfq_gt(grp->S, cl->S))
  814. goto skip_update;
  815. /* create a slot for this cl->S */
  816. qfq_slot_rotate(grp, roundedS);
  817. /* group was surely ineligible, remove */
  818. __clear_bit(grp->index, &q->bitmaps[IR]);
  819. __clear_bit(grp->index, &q->bitmaps[IB]);
  820. } else if (!q->bitmaps[ER] && qfq_gt(roundedS, q->V))
  821. q->V = roundedS;
  822. grp->S = roundedS;
  823. grp->F = roundedS + (2ULL << grp->slot_shift);
  824. s = qfq_calc_state(q, grp);
  825. __set_bit(grp->index, &q->bitmaps[s]);
  826. pr_debug("qfq enqueue: new state %d %#lx S %lld F %lld V %lld\n",
  827. s, q->bitmaps[s],
  828. (unsigned long long) cl->S,
  829. (unsigned long long) cl->F,
  830. (unsigned long long) q->V);
  831. skip_update:
  832. qfq_slot_insert(grp, cl, roundedS);
  833. }
  834. static void qfq_slot_remove(struct qfq_sched *q, struct qfq_group *grp,
  835. struct qfq_class *cl)
  836. {
  837. unsigned int i, offset;
  838. u64 roundedS;
  839. roundedS = qfq_round_down(cl->S, grp->slot_shift);
  840. offset = (roundedS - grp->S) >> grp->slot_shift;
  841. i = (grp->front + offset) % QFQ_MAX_SLOTS;
  842. hlist_del(&cl->next);
  843. if (hlist_empty(&grp->slots[i]))
  844. __clear_bit(offset, &grp->full_slots);
  845. }
  846. /*
  847. * called to forcibly destroy a queue.
  848. * If the queue is not in the front bucket, or if it has
  849. * other queues in the front bucket, we can simply remove
  850. * the queue with no other side effects.
  851. * Otherwise we must propagate the event up.
  852. */
  853. static void qfq_deactivate_class(struct qfq_sched *q, struct qfq_class *cl)
  854. {
  855. struct qfq_group *grp = cl->grp;
  856. unsigned long mask;
  857. u64 roundedS;
  858. int s;
  859. cl->F = cl->S;
  860. qfq_slot_remove(q, grp, cl);
  861. if (!grp->full_slots) {
  862. __clear_bit(grp->index, &q->bitmaps[IR]);
  863. __clear_bit(grp->index, &q->bitmaps[EB]);
  864. __clear_bit(grp->index, &q->bitmaps[IB]);
  865. if (test_bit(grp->index, &q->bitmaps[ER]) &&
  866. !(q->bitmaps[ER] & ~((1UL << grp->index) - 1))) {
  867. mask = q->bitmaps[ER] & ((1UL << grp->index) - 1);
  868. if (mask)
  869. mask = ~((1UL << __fls(mask)) - 1);
  870. else
  871. mask = ~0UL;
  872. qfq_move_groups(q, mask, EB, ER);
  873. qfq_move_groups(q, mask, IB, IR);
  874. }
  875. __clear_bit(grp->index, &q->bitmaps[ER]);
  876. } else if (hlist_empty(&grp->slots[grp->front])) {
  877. cl = qfq_slot_scan(grp);
  878. roundedS = qfq_round_down(cl->S, grp->slot_shift);
  879. if (grp->S != roundedS) {
  880. __clear_bit(grp->index, &q->bitmaps[ER]);
  881. __clear_bit(grp->index, &q->bitmaps[IR]);
  882. __clear_bit(grp->index, &q->bitmaps[EB]);
  883. __clear_bit(grp->index, &q->bitmaps[IB]);
  884. grp->S = roundedS;
  885. grp->F = roundedS + (2ULL << grp->slot_shift);
  886. s = qfq_calc_state(q, grp);
  887. __set_bit(grp->index, &q->bitmaps[s]);
  888. }
  889. }
  890. qfq_update_eligible(q, q->V);
  891. }
  892. static void qfq_qlen_notify(struct Qdisc *sch, unsigned long arg)
  893. {
  894. struct qfq_sched *q = qdisc_priv(sch);
  895. struct qfq_class *cl = (struct qfq_class *)arg;
  896. if (cl->qdisc->q.qlen == 0)
  897. qfq_deactivate_class(q, cl);
  898. }
  899. static unsigned int qfq_drop(struct Qdisc *sch)
  900. {
  901. struct qfq_sched *q = qdisc_priv(sch);
  902. struct qfq_group *grp;
  903. unsigned int i, j, len;
  904. for (i = 0; i <= QFQ_MAX_INDEX; i++) {
  905. grp = &q->groups[i];
  906. for (j = 0; j < QFQ_MAX_SLOTS; j++) {
  907. struct qfq_class *cl;
  908. struct hlist_node *n;
  909. hlist_for_each_entry(cl, n, &grp->slots[j], next) {
  910. if (!cl->qdisc->ops->drop)
  911. continue;
  912. len = cl->qdisc->ops->drop(cl->qdisc);
  913. if (len > 0) {
  914. sch->q.qlen--;
  915. if (!cl->qdisc->q.qlen)
  916. qfq_deactivate_class(q, cl);
  917. return len;
  918. }
  919. }
  920. }
  921. }
  922. return 0;
  923. }
  924. static int qfq_init_qdisc(struct Qdisc *sch, struct nlattr *opt)
  925. {
  926. struct qfq_sched *q = qdisc_priv(sch);
  927. struct qfq_group *grp;
  928. int i, j, err;
  929. err = qdisc_class_hash_init(&q->clhash);
  930. if (err < 0)
  931. return err;
  932. for (i = 0; i <= QFQ_MAX_INDEX; i++) {
  933. grp = &q->groups[i];
  934. grp->index = i;
  935. grp->slot_shift = QFQ_MTU_SHIFT + FRAC_BITS
  936. - (QFQ_MAX_INDEX - i);
  937. for (j = 0; j < QFQ_MAX_SLOTS; j++)
  938. INIT_HLIST_HEAD(&grp->slots[j]);
  939. }
  940. return 0;
  941. }
  942. static void qfq_reset_qdisc(struct Qdisc *sch)
  943. {
  944. struct qfq_sched *q = qdisc_priv(sch);
  945. struct qfq_group *grp;
  946. struct qfq_class *cl;
  947. struct hlist_node *n, *tmp;
  948. unsigned int i, j;
  949. for (i = 0; i <= QFQ_MAX_INDEX; i++) {
  950. grp = &q->groups[i];
  951. for (j = 0; j < QFQ_MAX_SLOTS; j++) {
  952. hlist_for_each_entry_safe(cl, n, tmp,
  953. &grp->slots[j], next) {
  954. qfq_deactivate_class(q, cl);
  955. }
  956. }
  957. }
  958. for (i = 0; i < q->clhash.hashsize; i++) {
  959. hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
  960. qdisc_reset(cl->qdisc);
  961. }
  962. sch->q.qlen = 0;
  963. }
  964. static void qfq_destroy_qdisc(struct Qdisc *sch)
  965. {
  966. struct qfq_sched *q = qdisc_priv(sch);
  967. struct qfq_class *cl;
  968. struct hlist_node *n, *next;
  969. unsigned int i;
  970. tcf_destroy_chain(&q->filter_list);
  971. for (i = 0; i < q->clhash.hashsize; i++) {
  972. hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[i],
  973. common.hnode) {
  974. qfq_destroy_class(sch, cl);
  975. }
  976. }
  977. qdisc_class_hash_destroy(&q->clhash);
  978. }
  979. static const struct Qdisc_class_ops qfq_class_ops = {
  980. .change = qfq_change_class,
  981. .delete = qfq_delete_class,
  982. .get = qfq_get_class,
  983. .put = qfq_put_class,
  984. .tcf_chain = qfq_tcf_chain,
  985. .bind_tcf = qfq_bind_tcf,
  986. .unbind_tcf = qfq_unbind_tcf,
  987. .graft = qfq_graft_class,
  988. .leaf = qfq_class_leaf,
  989. .qlen_notify = qfq_qlen_notify,
  990. .dump = qfq_dump_class,
  991. .dump_stats = qfq_dump_class_stats,
  992. .walk = qfq_walk,
  993. };
  994. static struct Qdisc_ops qfq_qdisc_ops __read_mostly = {
  995. .cl_ops = &qfq_class_ops,
  996. .id = "qfq",
  997. .priv_size = sizeof(struct qfq_sched),
  998. .enqueue = qfq_enqueue,
  999. .dequeue = qfq_dequeue,
  1000. .peek = qdisc_peek_dequeued,
  1001. .drop = qfq_drop,
  1002. .init = qfq_init_qdisc,
  1003. .reset = qfq_reset_qdisc,
  1004. .destroy = qfq_destroy_qdisc,
  1005. .owner = THIS_MODULE,
  1006. };
  1007. static int __init qfq_init(void)
  1008. {
  1009. return register_qdisc(&qfq_qdisc_ops);
  1010. }
  1011. static void __exit qfq_exit(void)
  1012. {
  1013. unregister_qdisc(&qfq_qdisc_ops);
  1014. }
  1015. module_init(qfq_init);
  1016. module_exit(qfq_exit);
  1017. MODULE_LICENSE("GPL");