sch_qfq.c 43 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582
  1. /*
  2. * net/sched/sch_qfq.c Quick Fair Queueing Plus Scheduler.
  3. *
  4. * Copyright (c) 2009 Fabio Checconi, Luigi Rizzo, and Paolo Valente.
  5. * Copyright (c) 2012 Paolo Valente.
  6. *
  7. * This program is free software; you can redistribute it and/or
  8. * modify it under the terms of the GNU General Public License
  9. * version 2 as published by the Free Software Foundation.
  10. */
  11. #include <linux/module.h>
  12. #include <linux/init.h>
  13. #include <linux/bitops.h>
  14. #include <linux/errno.h>
  15. #include <linux/netdevice.h>
  16. #include <linux/pkt_sched.h>
  17. #include <net/sch_generic.h>
  18. #include <net/pkt_sched.h>
  19. #include <net/pkt_cls.h>
  20. /* Quick Fair Queueing Plus
  21. ========================
  22. Sources:
  23. [1] Paolo Valente,
  24. "Reducing the Execution Time of Fair-Queueing Schedulers."
  25. http://algo.ing.unimo.it/people/paolo/agg-sched/agg-sched.pdf
  26. Sources for QFQ:
  27. [2] Fabio Checconi, Luigi Rizzo, and Paolo Valente: "QFQ: Efficient
  28. Packet Scheduling with Tight Bandwidth Distribution Guarantees."
  29. See also:
  30. http://retis.sssup.it/~fabio/linux/qfq/
  31. */
  32. /*
  33. QFQ+ divides classes into aggregates of at most MAX_AGG_CLASSES
  34. classes. Each aggregate is timestamped with a virtual start time S
  35. and a virtual finish time F, and scheduled according to its
  36. timestamps. S and F are computed as a function of a system virtual
  37. time function V. The classes within each aggregate are instead
  38. scheduled with DRR.
  39. To speed up operations, QFQ+ divides also aggregates into a limited
  40. number of groups. Which group a class belongs to depends on the
  41. ratio between the maximum packet length for the class and the weight
  42. of the class. Groups have their own S and F. In the end, QFQ+
  43. schedules groups, then aggregates within groups, then classes within
  44. aggregates. See [1] and [2] for a full description.
  45. Virtual time computations.
  46. S, F and V are all computed in fixed point arithmetic with
  47. FRAC_BITS decimal bits.
  48. QFQ_MAX_INDEX is the maximum index allowed for a group. We need
  49. one bit per index.
  50. QFQ_MAX_WSHIFT is the maximum power of two supported as a weight.
  51. The layout of the bits is as below:
  52. [ MTU_SHIFT ][ FRAC_BITS ]
  53. [ MAX_INDEX ][ MIN_SLOT_SHIFT ]
  54. ^.__grp->index = 0
  55. *.__grp->slot_shift
  56. where MIN_SLOT_SHIFT is derived by difference from the others.
  57. The max group index corresponds to Lmax/w_min, where
  58. Lmax=1<<MTU_SHIFT, w_min = 1 .
  59. From this, and knowing how many groups (MAX_INDEX) we want,
  60. we can derive the shift corresponding to each group.
  61. Because we often need to compute
  62. F = S + len/w_i and V = V + len/wsum
  63. instead of storing w_i store the value
  64. inv_w = (1<<FRAC_BITS)/w_i
  65. so we can do F = S + len * inv_w * wsum.
  66. We use W_TOT in the formulas so we can easily move between
  67. static and adaptive weight sum.
  68. The per-scheduler-instance data contain all the data structures
  69. for the scheduler: bitmaps and bucket lists.
  70. */
  71. /*
  72. * Maximum number of consecutive slots occupied by backlogged classes
  73. * inside a group.
  74. */
  75. #define QFQ_MAX_SLOTS 32
  76. /*
  77. * Shifts used for aggregate<->group mapping. We allow class weights that are
  78. * in the range [1, 2^MAX_WSHIFT], and we try to map each aggregate i to the
  79. * group with the smallest index that can support the L_i / r_i configured
  80. * for the classes in the aggregate.
  81. *
  82. * grp->index is the index of the group; and grp->slot_shift
  83. * is the shift for the corresponding (scaled) sigma_i.
  84. */
  85. #define QFQ_MAX_INDEX 24
  86. #define QFQ_MAX_WSHIFT 10
  87. #define QFQ_MAX_WEIGHT (1<<QFQ_MAX_WSHIFT) /* see qfq_slot_insert */
  88. #define QFQ_MAX_WSUM (64*QFQ_MAX_WEIGHT)
  89. #define FRAC_BITS 30 /* fixed point arithmetic */
  90. #define ONE_FP (1UL << FRAC_BITS)
  91. #define QFQ_MTU_SHIFT 16 /* to support TSO/GSO */
  92. #define QFQ_MIN_LMAX 512 /* see qfq_slot_insert */
  93. #define QFQ_MAX_AGG_CLASSES 8 /* max num classes per aggregate allowed */
  94. /*
  95. * Possible group states. These values are used as indexes for the bitmaps
  96. * array of struct qfq_queue.
  97. */
  98. enum qfq_state { ER, IR, EB, IB, QFQ_MAX_STATE };
  99. struct qfq_group;
  100. struct qfq_aggregate;
  101. struct qfq_class {
  102. struct Qdisc_class_common common;
  103. unsigned int refcnt;
  104. unsigned int filter_cnt;
  105. struct gnet_stats_basic_packed bstats;
  106. struct gnet_stats_queue qstats;
  107. struct gnet_stats_rate_est64 rate_est;
  108. struct Qdisc *qdisc;
  109. struct list_head alist; /* Link for active-classes list. */
  110. struct qfq_aggregate *agg; /* Parent aggregate. */
  111. int deficit; /* DRR deficit counter. */
  112. };
  113. struct qfq_aggregate {
  114. struct hlist_node next; /* Link for the slot list. */
  115. u64 S, F; /* flow timestamps (exact) */
  116. /* group we belong to. In principle we would need the index,
  117. * which is log_2(lmax/weight), but we never reference it
  118. * directly, only the group.
  119. */
  120. struct qfq_group *grp;
  121. /* these are copied from the flowset. */
  122. u32 class_weight; /* Weight of each class in this aggregate. */
  123. /* Max pkt size for the classes in this aggregate, DRR quantum. */
  124. int lmax;
  125. u32 inv_w; /* ONE_FP/(sum of weights of classes in aggr.). */
  126. u32 budgetmax; /* Max budget for this aggregate. */
  127. u32 initial_budget, budget; /* Initial and current budget. */
  128. int num_classes; /* Number of classes in this aggr. */
  129. struct list_head active; /* DRR queue of active classes. */
  130. struct hlist_node nonfull_next; /* See nonfull_aggs in qfq_sched. */
  131. };
  132. struct qfq_group {
  133. u64 S, F; /* group timestamps (approx). */
  134. unsigned int slot_shift; /* Slot shift. */
  135. unsigned int index; /* Group index. */
  136. unsigned int front; /* Index of the front slot. */
  137. unsigned long full_slots; /* non-empty slots */
  138. /* Array of RR lists of active aggregates. */
  139. struct hlist_head slots[QFQ_MAX_SLOTS];
  140. };
  141. struct qfq_sched {
  142. struct tcf_proto __rcu *filter_list;
  143. struct Qdisc_class_hash clhash;
  144. u64 oldV, V; /* Precise virtual times. */
  145. struct qfq_aggregate *in_serv_agg; /* Aggregate being served. */
  146. u32 wsum; /* weight sum */
  147. u32 iwsum; /* inverse weight sum */
  148. unsigned long bitmaps[QFQ_MAX_STATE]; /* Group bitmaps. */
  149. struct qfq_group groups[QFQ_MAX_INDEX + 1]; /* The groups. */
  150. u32 min_slot_shift; /* Index of the group-0 bit in the bitmaps. */
  151. u32 max_agg_classes; /* Max number of classes per aggr. */
  152. struct hlist_head nonfull_aggs; /* Aggs with room for more classes. */
  153. };
  154. /*
  155. * Possible reasons why the timestamps of an aggregate are updated
  156. * enqueue: the aggregate switches from idle to active and must scheduled
  157. * for service
  158. * requeue: the aggregate finishes its budget, so it stops being served and
  159. * must be rescheduled for service
  160. */
  161. enum update_reason {enqueue, requeue};
  162. static struct qfq_class *qfq_find_class(struct Qdisc *sch, u32 classid)
  163. {
  164. struct qfq_sched *q = qdisc_priv(sch);
  165. struct Qdisc_class_common *clc;
  166. clc = qdisc_class_find(&q->clhash, classid);
  167. if (clc == NULL)
  168. return NULL;
  169. return container_of(clc, struct qfq_class, common);
  170. }
  171. static void qfq_purge_queue(struct qfq_class *cl)
  172. {
  173. unsigned int len = cl->qdisc->q.qlen;
  174. unsigned int backlog = cl->qdisc->qstats.backlog;
  175. qdisc_reset(cl->qdisc);
  176. qdisc_tree_reduce_backlog(cl->qdisc, len, backlog);
  177. }
  178. static const struct nla_policy qfq_policy[TCA_QFQ_MAX + 1] = {
  179. [TCA_QFQ_WEIGHT] = { .type = NLA_U32 },
  180. [TCA_QFQ_LMAX] = { .type = NLA_U32 },
  181. };
  182. /*
  183. * Calculate a flow index, given its weight and maximum packet length.
  184. * index = log_2(maxlen/weight) but we need to apply the scaling.
  185. * This is used only once at flow creation.
  186. */
  187. static int qfq_calc_index(u32 inv_w, unsigned int maxlen, u32 min_slot_shift)
  188. {
  189. u64 slot_size = (u64)maxlen * inv_w;
  190. unsigned long size_map;
  191. int index = 0;
  192. size_map = slot_size >> min_slot_shift;
  193. if (!size_map)
  194. goto out;
  195. index = __fls(size_map) + 1; /* basically a log_2 */
  196. index -= !(slot_size - (1ULL << (index + min_slot_shift - 1)));
  197. if (index < 0)
  198. index = 0;
  199. out:
  200. pr_debug("qfq calc_index: W = %lu, L = %u, I = %d\n",
  201. (unsigned long) ONE_FP/inv_w, maxlen, index);
  202. return index;
  203. }
  204. static void qfq_deactivate_agg(struct qfq_sched *, struct qfq_aggregate *);
  205. static void qfq_activate_agg(struct qfq_sched *, struct qfq_aggregate *,
  206. enum update_reason);
  207. static void qfq_init_agg(struct qfq_sched *q, struct qfq_aggregate *agg,
  208. u32 lmax, u32 weight)
  209. {
  210. INIT_LIST_HEAD(&agg->active);
  211. hlist_add_head(&agg->nonfull_next, &q->nonfull_aggs);
  212. agg->lmax = lmax;
  213. agg->class_weight = weight;
  214. }
  215. static struct qfq_aggregate *qfq_find_agg(struct qfq_sched *q,
  216. u32 lmax, u32 weight)
  217. {
  218. struct qfq_aggregate *agg;
  219. hlist_for_each_entry(agg, &q->nonfull_aggs, nonfull_next)
  220. if (agg->lmax == lmax && agg->class_weight == weight)
  221. return agg;
  222. return NULL;
  223. }
  224. /* Update aggregate as a function of the new number of classes. */
  225. static void qfq_update_agg(struct qfq_sched *q, struct qfq_aggregate *agg,
  226. int new_num_classes)
  227. {
  228. u32 new_agg_weight;
  229. if (new_num_classes == q->max_agg_classes)
  230. hlist_del_init(&agg->nonfull_next);
  231. if (agg->num_classes > new_num_classes &&
  232. new_num_classes == q->max_agg_classes - 1) /* agg no more full */
  233. hlist_add_head(&agg->nonfull_next, &q->nonfull_aggs);
  234. /* The next assignment may let
  235. * agg->initial_budget > agg->budgetmax
  236. * hold, we will take it into account in charge_actual_service().
  237. */
  238. agg->budgetmax = new_num_classes * agg->lmax;
  239. new_agg_weight = agg->class_weight * new_num_classes;
  240. agg->inv_w = ONE_FP/new_agg_weight;
  241. if (agg->grp == NULL) {
  242. int i = qfq_calc_index(agg->inv_w, agg->budgetmax,
  243. q->min_slot_shift);
  244. agg->grp = &q->groups[i];
  245. }
  246. q->wsum +=
  247. (int) agg->class_weight * (new_num_classes - agg->num_classes);
  248. q->iwsum = ONE_FP / q->wsum;
  249. agg->num_classes = new_num_classes;
  250. }
  251. /* Add class to aggregate. */
  252. static void qfq_add_to_agg(struct qfq_sched *q,
  253. struct qfq_aggregate *agg,
  254. struct qfq_class *cl)
  255. {
  256. cl->agg = agg;
  257. qfq_update_agg(q, agg, agg->num_classes+1);
  258. if (cl->qdisc->q.qlen > 0) { /* adding an active class */
  259. list_add_tail(&cl->alist, &agg->active);
  260. if (list_first_entry(&agg->active, struct qfq_class, alist) ==
  261. cl && q->in_serv_agg != agg) /* agg was inactive */
  262. qfq_activate_agg(q, agg, enqueue); /* schedule agg */
  263. }
  264. }
  265. static struct qfq_aggregate *qfq_choose_next_agg(struct qfq_sched *);
  266. static void qfq_destroy_agg(struct qfq_sched *q, struct qfq_aggregate *agg)
  267. {
  268. hlist_del_init(&agg->nonfull_next);
  269. q->wsum -= agg->class_weight;
  270. if (q->wsum != 0)
  271. q->iwsum = ONE_FP / q->wsum;
  272. if (q->in_serv_agg == agg)
  273. q->in_serv_agg = qfq_choose_next_agg(q);
  274. kfree(agg);
  275. }
  276. /* Deschedule class from within its parent aggregate. */
  277. static void qfq_deactivate_class(struct qfq_sched *q, struct qfq_class *cl)
  278. {
  279. struct qfq_aggregate *agg = cl->agg;
  280. list_del(&cl->alist); /* remove from RR queue of the aggregate */
  281. if (list_empty(&agg->active)) /* agg is now inactive */
  282. qfq_deactivate_agg(q, agg);
  283. }
  284. /* Remove class from its parent aggregate. */
  285. static void qfq_rm_from_agg(struct qfq_sched *q, struct qfq_class *cl)
  286. {
  287. struct qfq_aggregate *agg = cl->agg;
  288. cl->agg = NULL;
  289. if (agg->num_classes == 1) { /* agg being emptied, destroy it */
  290. qfq_destroy_agg(q, agg);
  291. return;
  292. }
  293. qfq_update_agg(q, agg, agg->num_classes-1);
  294. }
  295. /* Deschedule class and remove it from its parent aggregate. */
  296. static void qfq_deact_rm_from_agg(struct qfq_sched *q, struct qfq_class *cl)
  297. {
  298. if (cl->qdisc->q.qlen > 0) /* class is active */
  299. qfq_deactivate_class(q, cl);
  300. qfq_rm_from_agg(q, cl);
  301. }
  302. /* Move class to a new aggregate, matching the new class weight and/or lmax */
  303. static int qfq_change_agg(struct Qdisc *sch, struct qfq_class *cl, u32 weight,
  304. u32 lmax)
  305. {
  306. struct qfq_sched *q = qdisc_priv(sch);
  307. struct qfq_aggregate *new_agg = qfq_find_agg(q, lmax, weight);
  308. if (new_agg == NULL) { /* create new aggregate */
  309. new_agg = kzalloc(sizeof(*new_agg), GFP_ATOMIC);
  310. if (new_agg == NULL)
  311. return -ENOBUFS;
  312. qfq_init_agg(q, new_agg, lmax, weight);
  313. }
  314. qfq_deact_rm_from_agg(q, cl);
  315. qfq_add_to_agg(q, new_agg, cl);
  316. return 0;
  317. }
  318. static int qfq_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
  319. struct nlattr **tca, unsigned long *arg)
  320. {
  321. struct qfq_sched *q = qdisc_priv(sch);
  322. struct qfq_class *cl = (struct qfq_class *)*arg;
  323. bool existing = false;
  324. struct nlattr *tb[TCA_QFQ_MAX + 1];
  325. struct qfq_aggregate *new_agg = NULL;
  326. u32 weight, lmax, inv_w;
  327. int err;
  328. int delta_w;
  329. if (tca[TCA_OPTIONS] == NULL) {
  330. pr_notice("qfq: no options\n");
  331. return -EINVAL;
  332. }
  333. err = nla_parse_nested(tb, TCA_QFQ_MAX, tca[TCA_OPTIONS], qfq_policy);
  334. if (err < 0)
  335. return err;
  336. if (tb[TCA_QFQ_WEIGHT]) {
  337. weight = nla_get_u32(tb[TCA_QFQ_WEIGHT]);
  338. if (!weight || weight > (1UL << QFQ_MAX_WSHIFT)) {
  339. pr_notice("qfq: invalid weight %u\n", weight);
  340. return -EINVAL;
  341. }
  342. } else
  343. weight = 1;
  344. if (tb[TCA_QFQ_LMAX]) {
  345. lmax = nla_get_u32(tb[TCA_QFQ_LMAX]);
  346. if (lmax < QFQ_MIN_LMAX || lmax > (1UL << QFQ_MTU_SHIFT)) {
  347. pr_notice("qfq: invalid max length %u\n", lmax);
  348. return -EINVAL;
  349. }
  350. } else
  351. lmax = psched_mtu(qdisc_dev(sch));
  352. inv_w = ONE_FP / weight;
  353. weight = ONE_FP / inv_w;
  354. if (cl != NULL &&
  355. lmax == cl->agg->lmax &&
  356. weight == cl->agg->class_weight)
  357. return 0; /* nothing to change */
  358. delta_w = weight - (cl ? cl->agg->class_weight : 0);
  359. if (q->wsum + delta_w > QFQ_MAX_WSUM) {
  360. pr_notice("qfq: total weight out of range (%d + %u)\n",
  361. delta_w, q->wsum);
  362. return -EINVAL;
  363. }
  364. if (cl != NULL) { /* modify existing class */
  365. if (tca[TCA_RATE]) {
  366. err = gen_replace_estimator(&cl->bstats, NULL,
  367. &cl->rate_est,
  368. qdisc_root_sleeping_lock(sch),
  369. tca[TCA_RATE]);
  370. if (err)
  371. return err;
  372. }
  373. existing = true;
  374. goto set_change_agg;
  375. }
  376. /* create and init new class */
  377. cl = kzalloc(sizeof(struct qfq_class), GFP_KERNEL);
  378. if (cl == NULL)
  379. return -ENOBUFS;
  380. cl->refcnt = 1;
  381. cl->common.classid = classid;
  382. cl->deficit = lmax;
  383. cl->qdisc = qdisc_create_dflt(sch->dev_queue,
  384. &pfifo_qdisc_ops, classid);
  385. if (cl->qdisc == NULL)
  386. cl->qdisc = &noop_qdisc;
  387. if (tca[TCA_RATE]) {
  388. err = gen_new_estimator(&cl->bstats, NULL,
  389. &cl->rate_est,
  390. qdisc_root_sleeping_lock(sch),
  391. tca[TCA_RATE]);
  392. if (err)
  393. goto destroy_class;
  394. }
  395. sch_tree_lock(sch);
  396. qdisc_class_hash_insert(&q->clhash, &cl->common);
  397. sch_tree_unlock(sch);
  398. qdisc_class_hash_grow(sch, &q->clhash);
  399. set_change_agg:
  400. sch_tree_lock(sch);
  401. new_agg = qfq_find_agg(q, lmax, weight);
  402. if (new_agg == NULL) { /* create new aggregate */
  403. sch_tree_unlock(sch);
  404. new_agg = kzalloc(sizeof(*new_agg), GFP_KERNEL);
  405. if (new_agg == NULL) {
  406. err = -ENOBUFS;
  407. gen_kill_estimator(&cl->bstats, &cl->rate_est);
  408. goto destroy_class;
  409. }
  410. sch_tree_lock(sch);
  411. qfq_init_agg(q, new_agg, lmax, weight);
  412. }
  413. if (existing)
  414. qfq_deact_rm_from_agg(q, cl);
  415. qfq_add_to_agg(q, new_agg, cl);
  416. sch_tree_unlock(sch);
  417. *arg = (unsigned long)cl;
  418. return 0;
  419. destroy_class:
  420. qdisc_destroy(cl->qdisc);
  421. kfree(cl);
  422. return err;
  423. }
  424. static void qfq_destroy_class(struct Qdisc *sch, struct qfq_class *cl)
  425. {
  426. struct qfq_sched *q = qdisc_priv(sch);
  427. qfq_rm_from_agg(q, cl);
  428. gen_kill_estimator(&cl->bstats, &cl->rate_est);
  429. qdisc_destroy(cl->qdisc);
  430. kfree(cl);
  431. }
  432. static int qfq_delete_class(struct Qdisc *sch, unsigned long arg)
  433. {
  434. struct qfq_sched *q = qdisc_priv(sch);
  435. struct qfq_class *cl = (struct qfq_class *)arg;
  436. if (cl->filter_cnt > 0)
  437. return -EBUSY;
  438. sch_tree_lock(sch);
  439. qfq_purge_queue(cl);
  440. qdisc_class_hash_remove(&q->clhash, &cl->common);
  441. BUG_ON(--cl->refcnt == 0);
  442. /*
  443. * This shouldn't happen: we "hold" one cops->get() when called
  444. * from tc_ctl_tclass; the destroy method is done from cops->put().
  445. */
  446. sch_tree_unlock(sch);
  447. return 0;
  448. }
  449. static unsigned long qfq_get_class(struct Qdisc *sch, u32 classid)
  450. {
  451. struct qfq_class *cl = qfq_find_class(sch, classid);
  452. if (cl != NULL)
  453. cl->refcnt++;
  454. return (unsigned long)cl;
  455. }
  456. static void qfq_put_class(struct Qdisc *sch, unsigned long arg)
  457. {
  458. struct qfq_class *cl = (struct qfq_class *)arg;
  459. if (--cl->refcnt == 0)
  460. qfq_destroy_class(sch, cl);
  461. }
  462. static struct tcf_proto __rcu **qfq_tcf_chain(struct Qdisc *sch,
  463. unsigned long cl)
  464. {
  465. struct qfq_sched *q = qdisc_priv(sch);
  466. if (cl)
  467. return NULL;
  468. return &q->filter_list;
  469. }
  470. static unsigned long qfq_bind_tcf(struct Qdisc *sch, unsigned long parent,
  471. u32 classid)
  472. {
  473. struct qfq_class *cl = qfq_find_class(sch, classid);
  474. if (cl != NULL)
  475. cl->filter_cnt++;
  476. return (unsigned long)cl;
  477. }
  478. static void qfq_unbind_tcf(struct Qdisc *sch, unsigned long arg)
  479. {
  480. struct qfq_class *cl = (struct qfq_class *)arg;
  481. cl->filter_cnt--;
  482. }
  483. static int qfq_graft_class(struct Qdisc *sch, unsigned long arg,
  484. struct Qdisc *new, struct Qdisc **old)
  485. {
  486. struct qfq_class *cl = (struct qfq_class *)arg;
  487. if (new == NULL) {
  488. new = qdisc_create_dflt(sch->dev_queue,
  489. &pfifo_qdisc_ops, cl->common.classid);
  490. if (new == NULL)
  491. new = &noop_qdisc;
  492. }
  493. *old = qdisc_replace(sch, new, &cl->qdisc);
  494. return 0;
  495. }
  496. static struct Qdisc *qfq_class_leaf(struct Qdisc *sch, unsigned long arg)
  497. {
  498. struct qfq_class *cl = (struct qfq_class *)arg;
  499. return cl->qdisc;
  500. }
  501. static int qfq_dump_class(struct Qdisc *sch, unsigned long arg,
  502. struct sk_buff *skb, struct tcmsg *tcm)
  503. {
  504. struct qfq_class *cl = (struct qfq_class *)arg;
  505. struct nlattr *nest;
  506. tcm->tcm_parent = TC_H_ROOT;
  507. tcm->tcm_handle = cl->common.classid;
  508. tcm->tcm_info = cl->qdisc->handle;
  509. nest = nla_nest_start(skb, TCA_OPTIONS);
  510. if (nest == NULL)
  511. goto nla_put_failure;
  512. if (nla_put_u32(skb, TCA_QFQ_WEIGHT, cl->agg->class_weight) ||
  513. nla_put_u32(skb, TCA_QFQ_LMAX, cl->agg->lmax))
  514. goto nla_put_failure;
  515. return nla_nest_end(skb, nest);
  516. nla_put_failure:
  517. nla_nest_cancel(skb, nest);
  518. return -EMSGSIZE;
  519. }
  520. static int qfq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
  521. struct gnet_dump *d)
  522. {
  523. struct qfq_class *cl = (struct qfq_class *)arg;
  524. struct tc_qfq_stats xstats;
  525. memset(&xstats, 0, sizeof(xstats));
  526. xstats.weight = cl->agg->class_weight;
  527. xstats.lmax = cl->agg->lmax;
  528. if (gnet_stats_copy_basic(d, NULL, &cl->bstats) < 0 ||
  529. gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 ||
  530. gnet_stats_copy_queue(d, NULL,
  531. &cl->qdisc->qstats, cl->qdisc->q.qlen) < 0)
  532. return -1;
  533. return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
  534. }
  535. static void qfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
  536. {
  537. struct qfq_sched *q = qdisc_priv(sch);
  538. struct qfq_class *cl;
  539. unsigned int i;
  540. if (arg->stop)
  541. return;
  542. for (i = 0; i < q->clhash.hashsize; i++) {
  543. hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
  544. if (arg->count < arg->skip) {
  545. arg->count++;
  546. continue;
  547. }
  548. if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
  549. arg->stop = 1;
  550. return;
  551. }
  552. arg->count++;
  553. }
  554. }
  555. }
  556. static struct qfq_class *qfq_classify(struct sk_buff *skb, struct Qdisc *sch,
  557. int *qerr)
  558. {
  559. struct qfq_sched *q = qdisc_priv(sch);
  560. struct qfq_class *cl;
  561. struct tcf_result res;
  562. struct tcf_proto *fl;
  563. int result;
  564. if (TC_H_MAJ(skb->priority ^ sch->handle) == 0) {
  565. pr_debug("qfq_classify: found %d\n", skb->priority);
  566. cl = qfq_find_class(sch, skb->priority);
  567. if (cl != NULL)
  568. return cl;
  569. }
  570. *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
  571. fl = rcu_dereference_bh(q->filter_list);
  572. result = tc_classify(skb, fl, &res, false);
  573. if (result >= 0) {
  574. #ifdef CONFIG_NET_CLS_ACT
  575. switch (result) {
  576. case TC_ACT_QUEUED:
  577. case TC_ACT_STOLEN:
  578. *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
  579. case TC_ACT_SHOT:
  580. return NULL;
  581. }
  582. #endif
  583. cl = (struct qfq_class *)res.class;
  584. if (cl == NULL)
  585. cl = qfq_find_class(sch, res.classid);
  586. return cl;
  587. }
  588. return NULL;
  589. }
  590. /* Generic comparison function, handling wraparound. */
  591. static inline int qfq_gt(u64 a, u64 b)
  592. {
  593. return (s64)(a - b) > 0;
  594. }
  595. /* Round a precise timestamp to its slotted value. */
  596. static inline u64 qfq_round_down(u64 ts, unsigned int shift)
  597. {
  598. return ts & ~((1ULL << shift) - 1);
  599. }
  600. /* return the pointer to the group with lowest index in the bitmap */
  601. static inline struct qfq_group *qfq_ffs(struct qfq_sched *q,
  602. unsigned long bitmap)
  603. {
  604. int index = __ffs(bitmap);
  605. return &q->groups[index];
  606. }
  607. /* Calculate a mask to mimic what would be ffs_from(). */
  608. static inline unsigned long mask_from(unsigned long bitmap, int from)
  609. {
  610. return bitmap & ~((1UL << from) - 1);
  611. }
  612. /*
  613. * The state computation relies on ER=0, IR=1, EB=2, IB=3
  614. * First compute eligibility comparing grp->S, q->V,
  615. * then check if someone is blocking us and possibly add EB
  616. */
  617. static int qfq_calc_state(struct qfq_sched *q, const struct qfq_group *grp)
  618. {
  619. /* if S > V we are not eligible */
  620. unsigned int state = qfq_gt(grp->S, q->V);
  621. unsigned long mask = mask_from(q->bitmaps[ER], grp->index);
  622. struct qfq_group *next;
  623. if (mask) {
  624. next = qfq_ffs(q, mask);
  625. if (qfq_gt(grp->F, next->F))
  626. state |= EB;
  627. }
  628. return state;
  629. }
  630. /*
  631. * In principle
  632. * q->bitmaps[dst] |= q->bitmaps[src] & mask;
  633. * q->bitmaps[src] &= ~mask;
  634. * but we should make sure that src != dst
  635. */
  636. static inline void qfq_move_groups(struct qfq_sched *q, unsigned long mask,
  637. int src, int dst)
  638. {
  639. q->bitmaps[dst] |= q->bitmaps[src] & mask;
  640. q->bitmaps[src] &= ~mask;
  641. }
  642. static void qfq_unblock_groups(struct qfq_sched *q, int index, u64 old_F)
  643. {
  644. unsigned long mask = mask_from(q->bitmaps[ER], index + 1);
  645. struct qfq_group *next;
  646. if (mask) {
  647. next = qfq_ffs(q, mask);
  648. if (!qfq_gt(next->F, old_F))
  649. return;
  650. }
  651. mask = (1UL << index) - 1;
  652. qfq_move_groups(q, mask, EB, ER);
  653. qfq_move_groups(q, mask, IB, IR);
  654. }
  655. /*
  656. * perhaps
  657. *
  658. old_V ^= q->V;
  659. old_V >>= q->min_slot_shift;
  660. if (old_V) {
  661. ...
  662. }
  663. *
  664. */
  665. static void qfq_make_eligible(struct qfq_sched *q)
  666. {
  667. unsigned long vslot = q->V >> q->min_slot_shift;
  668. unsigned long old_vslot = q->oldV >> q->min_slot_shift;
  669. if (vslot != old_vslot) {
  670. unsigned long mask;
  671. int last_flip_pos = fls(vslot ^ old_vslot);
  672. if (last_flip_pos > 31) /* higher than the number of groups */
  673. mask = ~0UL; /* make all groups eligible */
  674. else
  675. mask = (1UL << last_flip_pos) - 1;
  676. qfq_move_groups(q, mask, IR, ER);
  677. qfq_move_groups(q, mask, IB, EB);
  678. }
  679. }
  680. /*
  681. * The index of the slot in which the input aggregate agg is to be
  682. * inserted must not be higher than QFQ_MAX_SLOTS-2. There is a '-2'
  683. * and not a '-1' because the start time of the group may be moved
  684. * backward by one slot after the aggregate has been inserted, and
  685. * this would cause non-empty slots to be right-shifted by one
  686. * position.
  687. *
  688. * QFQ+ fully satisfies this bound to the slot index if the parameters
  689. * of the classes are not changed dynamically, and if QFQ+ never
  690. * happens to postpone the service of agg unjustly, i.e., it never
  691. * happens that the aggregate becomes backlogged and eligible, or just
  692. * eligible, while an aggregate with a higher approximated finish time
  693. * is being served. In particular, in this case QFQ+ guarantees that
  694. * the timestamps of agg are low enough that the slot index is never
  695. * higher than 2. Unfortunately, QFQ+ cannot provide the same
  696. * guarantee if it happens to unjustly postpone the service of agg, or
  697. * if the parameters of some class are changed.
  698. *
  699. * As for the first event, i.e., an out-of-order service, the
  700. * upper bound to the slot index guaranteed by QFQ+ grows to
  701. * 2 +
  702. * QFQ_MAX_AGG_CLASSES * ((1<<QFQ_MTU_SHIFT)/QFQ_MIN_LMAX) *
  703. * (current_max_weight/current_wsum) <= 2 + 8 * 128 * 1.
  704. *
  705. * The following function deals with this problem by backward-shifting
  706. * the timestamps of agg, if needed, so as to guarantee that the slot
  707. * index is never higher than QFQ_MAX_SLOTS-2. This backward-shift may
  708. * cause the service of other aggregates to be postponed, yet the
  709. * worst-case guarantees of these aggregates are not violated. In
  710. * fact, in case of no out-of-order service, the timestamps of agg
  711. * would have been even lower than they are after the backward shift,
  712. * because QFQ+ would have guaranteed a maximum value equal to 2 for
  713. * the slot index, and 2 < QFQ_MAX_SLOTS-2. Hence the aggregates whose
  714. * service is postponed because of the backward-shift would have
  715. * however waited for the service of agg before being served.
  716. *
  717. * The other event that may cause the slot index to be higher than 2
  718. * for agg is a recent change of the parameters of some class. If the
  719. * weight of a class is increased or the lmax (max_pkt_size) of the
  720. * class is decreased, then a new aggregate with smaller slot size
  721. * than the original parent aggregate of the class may happen to be
  722. * activated. The activation of this aggregate should be properly
  723. * delayed to when the service of the class has finished in the ideal
  724. * system tracked by QFQ+. If the activation of the aggregate is not
  725. * delayed to this reference time instant, then this aggregate may be
  726. * unjustly served before other aggregates waiting for service. This
  727. * may cause the above bound to the slot index to be violated for some
  728. * of these unlucky aggregates.
  729. *
  730. * Instead of delaying the activation of the new aggregate, which is
  731. * quite complex, the above-discussed capping of the slot index is
  732. * used to handle also the consequences of a change of the parameters
  733. * of a class.
  734. */
  735. static void qfq_slot_insert(struct qfq_group *grp, struct qfq_aggregate *agg,
  736. u64 roundedS)
  737. {
  738. u64 slot = (roundedS - grp->S) >> grp->slot_shift;
  739. unsigned int i; /* slot index in the bucket list */
  740. if (unlikely(slot > QFQ_MAX_SLOTS - 2)) {
  741. u64 deltaS = roundedS - grp->S -
  742. ((u64)(QFQ_MAX_SLOTS - 2)<<grp->slot_shift);
  743. agg->S -= deltaS;
  744. agg->F -= deltaS;
  745. slot = QFQ_MAX_SLOTS - 2;
  746. }
  747. i = (grp->front + slot) % QFQ_MAX_SLOTS;
  748. hlist_add_head(&agg->next, &grp->slots[i]);
  749. __set_bit(slot, &grp->full_slots);
  750. }
  751. /* Maybe introduce hlist_first_entry?? */
  752. static struct qfq_aggregate *qfq_slot_head(struct qfq_group *grp)
  753. {
  754. return hlist_entry(grp->slots[grp->front].first,
  755. struct qfq_aggregate, next);
  756. }
  757. /*
  758. * remove the entry from the slot
  759. */
  760. static void qfq_front_slot_remove(struct qfq_group *grp)
  761. {
  762. struct qfq_aggregate *agg = qfq_slot_head(grp);
  763. BUG_ON(!agg);
  764. hlist_del(&agg->next);
  765. if (hlist_empty(&grp->slots[grp->front]))
  766. __clear_bit(0, &grp->full_slots);
  767. }
  768. /*
  769. * Returns the first aggregate in the first non-empty bucket of the
  770. * group. As a side effect, adjusts the bucket list so the first
  771. * non-empty bucket is at position 0 in full_slots.
  772. */
  773. static struct qfq_aggregate *qfq_slot_scan(struct qfq_group *grp)
  774. {
  775. unsigned int i;
  776. pr_debug("qfq slot_scan: grp %u full %#lx\n",
  777. grp->index, grp->full_slots);
  778. if (grp->full_slots == 0)
  779. return NULL;
  780. i = __ffs(grp->full_slots); /* zero based */
  781. if (i > 0) {
  782. grp->front = (grp->front + i) % QFQ_MAX_SLOTS;
  783. grp->full_slots >>= i;
  784. }
  785. return qfq_slot_head(grp);
  786. }
  787. /*
  788. * adjust the bucket list. When the start time of a group decreases,
  789. * we move the index down (modulo QFQ_MAX_SLOTS) so we don't need to
  790. * move the objects. The mask of occupied slots must be shifted
  791. * because we use ffs() to find the first non-empty slot.
  792. * This covers decreases in the group's start time, but what about
  793. * increases of the start time ?
  794. * Here too we should make sure that i is less than 32
  795. */
  796. static void qfq_slot_rotate(struct qfq_group *grp, u64 roundedS)
  797. {
  798. unsigned int i = (grp->S - roundedS) >> grp->slot_shift;
  799. grp->full_slots <<= i;
  800. grp->front = (grp->front - i) % QFQ_MAX_SLOTS;
  801. }
  802. static void qfq_update_eligible(struct qfq_sched *q)
  803. {
  804. struct qfq_group *grp;
  805. unsigned long ineligible;
  806. ineligible = q->bitmaps[IR] | q->bitmaps[IB];
  807. if (ineligible) {
  808. if (!q->bitmaps[ER]) {
  809. grp = qfq_ffs(q, ineligible);
  810. if (qfq_gt(grp->S, q->V))
  811. q->V = grp->S;
  812. }
  813. qfq_make_eligible(q);
  814. }
  815. }
  816. /* Dequeue head packet of the head class in the DRR queue of the aggregate. */
  817. static void agg_dequeue(struct qfq_aggregate *agg,
  818. struct qfq_class *cl, unsigned int len)
  819. {
  820. qdisc_dequeue_peeked(cl->qdisc);
  821. cl->deficit -= (int) len;
  822. if (cl->qdisc->q.qlen == 0) /* no more packets, remove from list */
  823. list_del(&cl->alist);
  824. else if (cl->deficit < qdisc_pkt_len(cl->qdisc->ops->peek(cl->qdisc))) {
  825. cl->deficit += agg->lmax;
  826. list_move_tail(&cl->alist, &agg->active);
  827. }
  828. }
  829. static inline struct sk_buff *qfq_peek_skb(struct qfq_aggregate *agg,
  830. struct qfq_class **cl,
  831. unsigned int *len)
  832. {
  833. struct sk_buff *skb;
  834. *cl = list_first_entry(&agg->active, struct qfq_class, alist);
  835. skb = (*cl)->qdisc->ops->peek((*cl)->qdisc);
  836. if (skb == NULL)
  837. WARN_ONCE(1, "qfq_dequeue: non-workconserving leaf\n");
  838. else
  839. *len = qdisc_pkt_len(skb);
  840. return skb;
  841. }
  842. /* Update F according to the actual service received by the aggregate. */
  843. static inline void charge_actual_service(struct qfq_aggregate *agg)
  844. {
  845. /* Compute the service received by the aggregate, taking into
  846. * account that, after decreasing the number of classes in
  847. * agg, it may happen that
  848. * agg->initial_budget - agg->budget > agg->bugdetmax
  849. */
  850. u32 service_received = min(agg->budgetmax,
  851. agg->initial_budget - agg->budget);
  852. agg->F = agg->S + (u64)service_received * agg->inv_w;
  853. }
  854. /* Assign a reasonable start time for a new aggregate in group i.
  855. * Admissible values for \hat(F) are multiples of \sigma_i
  856. * no greater than V+\sigma_i . Larger values mean that
  857. * we had a wraparound so we consider the timestamp to be stale.
  858. *
  859. * If F is not stale and F >= V then we set S = F.
  860. * Otherwise we should assign S = V, but this may violate
  861. * the ordering in EB (see [2]). So, if we have groups in ER,
  862. * set S to the F_j of the first group j which would be blocking us.
  863. * We are guaranteed not to move S backward because
  864. * otherwise our group i would still be blocked.
  865. */
  866. static void qfq_update_start(struct qfq_sched *q, struct qfq_aggregate *agg)
  867. {
  868. unsigned long mask;
  869. u64 limit, roundedF;
  870. int slot_shift = agg->grp->slot_shift;
  871. roundedF = qfq_round_down(agg->F, slot_shift);
  872. limit = qfq_round_down(q->V, slot_shift) + (1ULL << slot_shift);
  873. if (!qfq_gt(agg->F, q->V) || qfq_gt(roundedF, limit)) {
  874. /* timestamp was stale */
  875. mask = mask_from(q->bitmaps[ER], agg->grp->index);
  876. if (mask) {
  877. struct qfq_group *next = qfq_ffs(q, mask);
  878. if (qfq_gt(roundedF, next->F)) {
  879. if (qfq_gt(limit, next->F))
  880. agg->S = next->F;
  881. else /* preserve timestamp correctness */
  882. agg->S = limit;
  883. return;
  884. }
  885. }
  886. agg->S = q->V;
  887. } else /* timestamp is not stale */
  888. agg->S = agg->F;
  889. }
  890. /* Update the timestamps of agg before scheduling/rescheduling it for
  891. * service. In particular, assign to agg->F its maximum possible
  892. * value, i.e., the virtual finish time with which the aggregate
  893. * should be labeled if it used all its budget once in service.
  894. */
  895. static inline void
  896. qfq_update_agg_ts(struct qfq_sched *q,
  897. struct qfq_aggregate *agg, enum update_reason reason)
  898. {
  899. if (reason != requeue)
  900. qfq_update_start(q, agg);
  901. else /* just charge agg for the service received */
  902. agg->S = agg->F;
  903. agg->F = agg->S + (u64)agg->budgetmax * agg->inv_w;
  904. }
  905. static void qfq_schedule_agg(struct qfq_sched *q, struct qfq_aggregate *agg);
  906. static struct sk_buff *qfq_dequeue(struct Qdisc *sch)
  907. {
  908. struct qfq_sched *q = qdisc_priv(sch);
  909. struct qfq_aggregate *in_serv_agg = q->in_serv_agg;
  910. struct qfq_class *cl;
  911. struct sk_buff *skb = NULL;
  912. /* next-packet len, 0 means no more active classes in in-service agg */
  913. unsigned int len = 0;
  914. if (in_serv_agg == NULL)
  915. return NULL;
  916. if (!list_empty(&in_serv_agg->active))
  917. skb = qfq_peek_skb(in_serv_agg, &cl, &len);
  918. /*
  919. * If there are no active classes in the in-service aggregate,
  920. * or if the aggregate has not enough budget to serve its next
  921. * class, then choose the next aggregate to serve.
  922. */
  923. if (len == 0 || in_serv_agg->budget < len) {
  924. charge_actual_service(in_serv_agg);
  925. /* recharge the budget of the aggregate */
  926. in_serv_agg->initial_budget = in_serv_agg->budget =
  927. in_serv_agg->budgetmax;
  928. if (!list_empty(&in_serv_agg->active)) {
  929. /*
  930. * Still active: reschedule for
  931. * service. Possible optimization: if no other
  932. * aggregate is active, then there is no point
  933. * in rescheduling this aggregate, and we can
  934. * just keep it as the in-service one. This
  935. * should be however a corner case, and to
  936. * handle it, we would need to maintain an
  937. * extra num_active_aggs field.
  938. */
  939. qfq_update_agg_ts(q, in_serv_agg, requeue);
  940. qfq_schedule_agg(q, in_serv_agg);
  941. } else if (sch->q.qlen == 0) { /* no aggregate to serve */
  942. q->in_serv_agg = NULL;
  943. return NULL;
  944. }
  945. /*
  946. * If we get here, there are other aggregates queued:
  947. * choose the new aggregate to serve.
  948. */
  949. in_serv_agg = q->in_serv_agg = qfq_choose_next_agg(q);
  950. skb = qfq_peek_skb(in_serv_agg, &cl, &len);
  951. }
  952. if (!skb)
  953. return NULL;
  954. sch->q.qlen--;
  955. qdisc_bstats_update(sch, skb);
  956. agg_dequeue(in_serv_agg, cl, len);
  957. /* If lmax is lowered, through qfq_change_class, for a class
  958. * owning pending packets with larger size than the new value
  959. * of lmax, then the following condition may hold.
  960. */
  961. if (unlikely(in_serv_agg->budget < len))
  962. in_serv_agg->budget = 0;
  963. else
  964. in_serv_agg->budget -= len;
  965. q->V += (u64)len * q->iwsum;
  966. pr_debug("qfq dequeue: len %u F %lld now %lld\n",
  967. len, (unsigned long long) in_serv_agg->F,
  968. (unsigned long long) q->V);
  969. return skb;
  970. }
  971. static struct qfq_aggregate *qfq_choose_next_agg(struct qfq_sched *q)
  972. {
  973. struct qfq_group *grp;
  974. struct qfq_aggregate *agg, *new_front_agg;
  975. u64 old_F;
  976. qfq_update_eligible(q);
  977. q->oldV = q->V;
  978. if (!q->bitmaps[ER])
  979. return NULL;
  980. grp = qfq_ffs(q, q->bitmaps[ER]);
  981. old_F = grp->F;
  982. agg = qfq_slot_head(grp);
  983. /* agg starts to be served, remove it from schedule */
  984. qfq_front_slot_remove(grp);
  985. new_front_agg = qfq_slot_scan(grp);
  986. if (new_front_agg == NULL) /* group is now inactive, remove from ER */
  987. __clear_bit(grp->index, &q->bitmaps[ER]);
  988. else {
  989. u64 roundedS = qfq_round_down(new_front_agg->S,
  990. grp->slot_shift);
  991. unsigned int s;
  992. if (grp->S == roundedS)
  993. return agg;
  994. grp->S = roundedS;
  995. grp->F = roundedS + (2ULL << grp->slot_shift);
  996. __clear_bit(grp->index, &q->bitmaps[ER]);
  997. s = qfq_calc_state(q, grp);
  998. __set_bit(grp->index, &q->bitmaps[s]);
  999. }
  1000. qfq_unblock_groups(q, grp->index, old_F);
  1001. return agg;
  1002. }
  1003. static int qfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
  1004. {
  1005. struct qfq_sched *q = qdisc_priv(sch);
  1006. struct qfq_class *cl;
  1007. struct qfq_aggregate *agg;
  1008. int err = 0;
  1009. cl = qfq_classify(skb, sch, &err);
  1010. if (cl == NULL) {
  1011. if (err & __NET_XMIT_BYPASS)
  1012. qdisc_qstats_drop(sch);
  1013. kfree_skb(skb);
  1014. return err;
  1015. }
  1016. pr_debug("qfq_enqueue: cl = %x\n", cl->common.classid);
  1017. if (unlikely(cl->agg->lmax < qdisc_pkt_len(skb))) {
  1018. pr_debug("qfq: increasing maxpkt from %u to %u for class %u",
  1019. cl->agg->lmax, qdisc_pkt_len(skb), cl->common.classid);
  1020. err = qfq_change_agg(sch, cl, cl->agg->class_weight,
  1021. qdisc_pkt_len(skb));
  1022. if (err)
  1023. return err;
  1024. }
  1025. err = qdisc_enqueue(skb, cl->qdisc);
  1026. if (unlikely(err != NET_XMIT_SUCCESS)) {
  1027. pr_debug("qfq_enqueue: enqueue failed %d\n", err);
  1028. if (net_xmit_drop_count(err)) {
  1029. cl->qstats.drops++;
  1030. qdisc_qstats_drop(sch);
  1031. }
  1032. return err;
  1033. }
  1034. bstats_update(&cl->bstats, skb);
  1035. ++sch->q.qlen;
  1036. agg = cl->agg;
  1037. /* if the queue was not empty, then done here */
  1038. if (cl->qdisc->q.qlen != 1) {
  1039. if (unlikely(skb == cl->qdisc->ops->peek(cl->qdisc)) &&
  1040. list_first_entry(&agg->active, struct qfq_class, alist)
  1041. == cl && cl->deficit < qdisc_pkt_len(skb))
  1042. list_move_tail(&cl->alist, &agg->active);
  1043. return err;
  1044. }
  1045. /* schedule class for service within the aggregate */
  1046. cl->deficit = agg->lmax;
  1047. list_add_tail(&cl->alist, &agg->active);
  1048. if (list_first_entry(&agg->active, struct qfq_class, alist) != cl ||
  1049. q->in_serv_agg == agg)
  1050. return err; /* non-empty or in service, nothing else to do */
  1051. qfq_activate_agg(q, agg, enqueue);
  1052. return err;
  1053. }
  1054. /*
  1055. * Schedule aggregate according to its timestamps.
  1056. */
  1057. static void qfq_schedule_agg(struct qfq_sched *q, struct qfq_aggregate *agg)
  1058. {
  1059. struct qfq_group *grp = agg->grp;
  1060. u64 roundedS;
  1061. int s;
  1062. roundedS = qfq_round_down(agg->S, grp->slot_shift);
  1063. /*
  1064. * Insert agg in the correct bucket.
  1065. * If agg->S >= grp->S we don't need to adjust the
  1066. * bucket list and simply go to the insertion phase.
  1067. * Otherwise grp->S is decreasing, we must make room
  1068. * in the bucket list, and also recompute the group state.
  1069. * Finally, if there were no flows in this group and nobody
  1070. * was in ER make sure to adjust V.
  1071. */
  1072. if (grp->full_slots) {
  1073. if (!qfq_gt(grp->S, agg->S))
  1074. goto skip_update;
  1075. /* create a slot for this agg->S */
  1076. qfq_slot_rotate(grp, roundedS);
  1077. /* group was surely ineligible, remove */
  1078. __clear_bit(grp->index, &q->bitmaps[IR]);
  1079. __clear_bit(grp->index, &q->bitmaps[IB]);
  1080. } else if (!q->bitmaps[ER] && qfq_gt(roundedS, q->V) &&
  1081. q->in_serv_agg == NULL)
  1082. q->V = roundedS;
  1083. grp->S = roundedS;
  1084. grp->F = roundedS + (2ULL << grp->slot_shift);
  1085. s = qfq_calc_state(q, grp);
  1086. __set_bit(grp->index, &q->bitmaps[s]);
  1087. pr_debug("qfq enqueue: new state %d %#lx S %lld F %lld V %lld\n",
  1088. s, q->bitmaps[s],
  1089. (unsigned long long) agg->S,
  1090. (unsigned long long) agg->F,
  1091. (unsigned long long) q->V);
  1092. skip_update:
  1093. qfq_slot_insert(grp, agg, roundedS);
  1094. }
  1095. /* Update agg ts and schedule agg for service */
  1096. static void qfq_activate_agg(struct qfq_sched *q, struct qfq_aggregate *agg,
  1097. enum update_reason reason)
  1098. {
  1099. agg->initial_budget = agg->budget = agg->budgetmax; /* recharge budg. */
  1100. qfq_update_agg_ts(q, agg, reason);
  1101. if (q->in_serv_agg == NULL) { /* no aggr. in service or scheduled */
  1102. q->in_serv_agg = agg; /* start serving this aggregate */
  1103. /* update V: to be in service, agg must be eligible */
  1104. q->oldV = q->V = agg->S;
  1105. } else if (agg != q->in_serv_agg)
  1106. qfq_schedule_agg(q, agg);
  1107. }
  1108. static void qfq_slot_remove(struct qfq_sched *q, struct qfq_group *grp,
  1109. struct qfq_aggregate *agg)
  1110. {
  1111. unsigned int i, offset;
  1112. u64 roundedS;
  1113. roundedS = qfq_round_down(agg->S, grp->slot_shift);
  1114. offset = (roundedS - grp->S) >> grp->slot_shift;
  1115. i = (grp->front + offset) % QFQ_MAX_SLOTS;
  1116. hlist_del(&agg->next);
  1117. if (hlist_empty(&grp->slots[i]))
  1118. __clear_bit(offset, &grp->full_slots);
  1119. }
  1120. /*
  1121. * Called to forcibly deschedule an aggregate. If the aggregate is
  1122. * not in the front bucket, or if the latter has other aggregates in
  1123. * the front bucket, we can simply remove the aggregate with no other
  1124. * side effects.
  1125. * Otherwise we must propagate the event up.
  1126. */
  1127. static void qfq_deactivate_agg(struct qfq_sched *q, struct qfq_aggregate *agg)
  1128. {
  1129. struct qfq_group *grp = agg->grp;
  1130. unsigned long mask;
  1131. u64 roundedS;
  1132. int s;
  1133. if (agg == q->in_serv_agg) {
  1134. charge_actual_service(agg);
  1135. q->in_serv_agg = qfq_choose_next_agg(q);
  1136. return;
  1137. }
  1138. agg->F = agg->S;
  1139. qfq_slot_remove(q, grp, agg);
  1140. if (!grp->full_slots) {
  1141. __clear_bit(grp->index, &q->bitmaps[IR]);
  1142. __clear_bit(grp->index, &q->bitmaps[EB]);
  1143. __clear_bit(grp->index, &q->bitmaps[IB]);
  1144. if (test_bit(grp->index, &q->bitmaps[ER]) &&
  1145. !(q->bitmaps[ER] & ~((1UL << grp->index) - 1))) {
  1146. mask = q->bitmaps[ER] & ((1UL << grp->index) - 1);
  1147. if (mask)
  1148. mask = ~((1UL << __fls(mask)) - 1);
  1149. else
  1150. mask = ~0UL;
  1151. qfq_move_groups(q, mask, EB, ER);
  1152. qfq_move_groups(q, mask, IB, IR);
  1153. }
  1154. __clear_bit(grp->index, &q->bitmaps[ER]);
  1155. } else if (hlist_empty(&grp->slots[grp->front])) {
  1156. agg = qfq_slot_scan(grp);
  1157. roundedS = qfq_round_down(agg->S, grp->slot_shift);
  1158. if (grp->S != roundedS) {
  1159. __clear_bit(grp->index, &q->bitmaps[ER]);
  1160. __clear_bit(grp->index, &q->bitmaps[IR]);
  1161. __clear_bit(grp->index, &q->bitmaps[EB]);
  1162. __clear_bit(grp->index, &q->bitmaps[IB]);
  1163. grp->S = roundedS;
  1164. grp->F = roundedS + (2ULL << grp->slot_shift);
  1165. s = qfq_calc_state(q, grp);
  1166. __set_bit(grp->index, &q->bitmaps[s]);
  1167. }
  1168. }
  1169. }
  1170. static void qfq_qlen_notify(struct Qdisc *sch, unsigned long arg)
  1171. {
  1172. struct qfq_sched *q = qdisc_priv(sch);
  1173. struct qfq_class *cl = (struct qfq_class *)arg;
  1174. if (cl->qdisc->q.qlen == 0)
  1175. qfq_deactivate_class(q, cl);
  1176. }
  1177. static unsigned int qfq_drop_from_slot(struct qfq_sched *q,
  1178. struct hlist_head *slot)
  1179. {
  1180. struct qfq_aggregate *agg;
  1181. struct qfq_class *cl;
  1182. unsigned int len;
  1183. hlist_for_each_entry(agg, slot, next) {
  1184. list_for_each_entry(cl, &agg->active, alist) {
  1185. if (!cl->qdisc->ops->drop)
  1186. continue;
  1187. len = cl->qdisc->ops->drop(cl->qdisc);
  1188. if (len > 0) {
  1189. if (cl->qdisc->q.qlen == 0)
  1190. qfq_deactivate_class(q, cl);
  1191. return len;
  1192. }
  1193. }
  1194. }
  1195. return 0;
  1196. }
  1197. static unsigned int qfq_drop(struct Qdisc *sch)
  1198. {
  1199. struct qfq_sched *q = qdisc_priv(sch);
  1200. struct qfq_group *grp;
  1201. unsigned int i, j, len;
  1202. for (i = 0; i <= QFQ_MAX_INDEX; i++) {
  1203. grp = &q->groups[i];
  1204. for (j = 0; j < QFQ_MAX_SLOTS; j++) {
  1205. len = qfq_drop_from_slot(q, &grp->slots[j]);
  1206. if (len > 0) {
  1207. sch->q.qlen--;
  1208. return len;
  1209. }
  1210. }
  1211. }
  1212. return 0;
  1213. }
  1214. static int qfq_init_qdisc(struct Qdisc *sch, struct nlattr *opt)
  1215. {
  1216. struct qfq_sched *q = qdisc_priv(sch);
  1217. struct qfq_group *grp;
  1218. int i, j, err;
  1219. u32 max_cl_shift, maxbudg_shift, max_classes;
  1220. err = qdisc_class_hash_init(&q->clhash);
  1221. if (err < 0)
  1222. return err;
  1223. if (qdisc_dev(sch)->tx_queue_len + 1 > QFQ_MAX_AGG_CLASSES)
  1224. max_classes = QFQ_MAX_AGG_CLASSES;
  1225. else
  1226. max_classes = qdisc_dev(sch)->tx_queue_len + 1;
  1227. /* max_cl_shift = floor(log_2(max_classes)) */
  1228. max_cl_shift = __fls(max_classes);
  1229. q->max_agg_classes = 1<<max_cl_shift;
  1230. /* maxbudg_shift = log2(max_len * max_classes_per_agg) */
  1231. maxbudg_shift = QFQ_MTU_SHIFT + max_cl_shift;
  1232. q->min_slot_shift = FRAC_BITS + maxbudg_shift - QFQ_MAX_INDEX;
  1233. for (i = 0; i <= QFQ_MAX_INDEX; i++) {
  1234. grp = &q->groups[i];
  1235. grp->index = i;
  1236. grp->slot_shift = q->min_slot_shift + i;
  1237. for (j = 0; j < QFQ_MAX_SLOTS; j++)
  1238. INIT_HLIST_HEAD(&grp->slots[j]);
  1239. }
  1240. INIT_HLIST_HEAD(&q->nonfull_aggs);
  1241. return 0;
  1242. }
  1243. static void qfq_reset_qdisc(struct Qdisc *sch)
  1244. {
  1245. struct qfq_sched *q = qdisc_priv(sch);
  1246. struct qfq_class *cl;
  1247. unsigned int i;
  1248. for (i = 0; i < q->clhash.hashsize; i++) {
  1249. hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
  1250. if (cl->qdisc->q.qlen > 0)
  1251. qfq_deactivate_class(q, cl);
  1252. qdisc_reset(cl->qdisc);
  1253. }
  1254. }
  1255. sch->q.qlen = 0;
  1256. }
  1257. static void qfq_destroy_qdisc(struct Qdisc *sch)
  1258. {
  1259. struct qfq_sched *q = qdisc_priv(sch);
  1260. struct qfq_class *cl;
  1261. struct hlist_node *next;
  1262. unsigned int i;
  1263. tcf_destroy_chain(&q->filter_list);
  1264. for (i = 0; i < q->clhash.hashsize; i++) {
  1265. hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i],
  1266. common.hnode) {
  1267. qfq_destroy_class(sch, cl);
  1268. }
  1269. }
  1270. qdisc_class_hash_destroy(&q->clhash);
  1271. }
  1272. static const struct Qdisc_class_ops qfq_class_ops = {
  1273. .change = qfq_change_class,
  1274. .delete = qfq_delete_class,
  1275. .get = qfq_get_class,
  1276. .put = qfq_put_class,
  1277. .tcf_chain = qfq_tcf_chain,
  1278. .bind_tcf = qfq_bind_tcf,
  1279. .unbind_tcf = qfq_unbind_tcf,
  1280. .graft = qfq_graft_class,
  1281. .leaf = qfq_class_leaf,
  1282. .qlen_notify = qfq_qlen_notify,
  1283. .dump = qfq_dump_class,
  1284. .dump_stats = qfq_dump_class_stats,
  1285. .walk = qfq_walk,
  1286. };
  1287. static struct Qdisc_ops qfq_qdisc_ops __read_mostly = {
  1288. .cl_ops = &qfq_class_ops,
  1289. .id = "qfq",
  1290. .priv_size = sizeof(struct qfq_sched),
  1291. .enqueue = qfq_enqueue,
  1292. .dequeue = qfq_dequeue,
  1293. .peek = qdisc_peek_dequeued,
  1294. .drop = qfq_drop,
  1295. .init = qfq_init_qdisc,
  1296. .reset = qfq_reset_qdisc,
  1297. .destroy = qfq_destroy_qdisc,
  1298. .owner = THIS_MODULE,
  1299. };
  1300. static int __init qfq_init(void)
  1301. {
  1302. return register_qdisc(&qfq_qdisc_ops);
  1303. }
  1304. static void __exit qfq_exit(void)
  1305. {
  1306. unregister_qdisc(&qfq_qdisc_ops);
  1307. }
  1308. module_init(qfq_init);
  1309. module_exit(qfq_exit);
  1310. MODULE_LICENSE("GPL");