sch_hfsc.c 42 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820
  1. /*
  2. * Copyright (c) 2003 Patrick McHardy, <kaber@trash.net>
  3. *
  4. * This program is free software; you can redistribute it and/or
  5. * modify it under the terms of the GNU General Public License
  6. * as published by the Free Software Foundation; either version 2
  7. * of the License, or (at your option) any later version.
  8. *
  9. * 2003-10-17 - Ported from altq
  10. */
  11. /*
  12. * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved.
  13. *
  14. * Permission to use, copy, modify, and distribute this software and
  15. * its documentation is hereby granted (including for commercial or
  16. * for-profit use), provided that both the copyright notice and this
  17. * permission notice appear in all copies of the software, derivative
  18. * works, or modified versions, and any portions thereof.
  19. *
  20. * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF
  21. * WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS
  22. * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED
  23. * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  24. * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  25. * DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
  26. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  27. * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
  28. * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  29. * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  30. * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  31. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
  32. * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
  33. * DAMAGE.
  34. *
  35. * Carnegie Mellon encourages (but does not require) users of this
  36. * software to return any improvements or extensions that they make,
  37. * and to grant Carnegie Mellon the rights to redistribute these
  38. * changes without encumbrance.
  39. */
  40. /*
  41. * H-FSC is described in Proceedings of SIGCOMM'97,
  42. * "A Hierarchical Fair Service Curve Algorithm for Link-Sharing,
  43. * Real-Time and Priority Service"
  44. * by Ion Stoica, Hui Zhang, and T. S. Eugene Ng.
  45. *
  46. * Oleg Cherevko <olwi@aq.ml.com.ua> added the upperlimit for link-sharing.
  47. * when a class has an upperlimit, the fit-time is computed from the
  48. * upperlimit service curve. the link-sharing scheduler does not schedule
  49. * a class whose fit-time exceeds the current time.
  50. */
  51. #include <linux/kernel.h>
  52. #include <linux/module.h>
  53. #include <linux/types.h>
  54. #include <linux/errno.h>
  55. #include <linux/jiffies.h>
  56. #include <linux/compiler.h>
  57. #include <linux/spinlock.h>
  58. #include <linux/skbuff.h>
  59. #include <linux/string.h>
  60. #include <linux/slab.h>
  61. #include <linux/timer.h>
  62. #include <linux/list.h>
  63. #include <linux/rbtree.h>
  64. #include <linux/init.h>
  65. #include <linux/netdevice.h>
  66. #include <linux/rtnetlink.h>
  67. #include <linux/pkt_sched.h>
  68. #include <net/pkt_sched.h>
  69. #include <net/pkt_cls.h>
  70. #include <asm/system.h>
  71. #include <asm/div64.h>
  72. /*
  73. * kernel internal service curve representation:
  74. * coordinates are given by 64 bit unsigned integers.
  75. * x-axis: unit is clock count.
  76. * y-axis: unit is byte.
  77. *
  78. * The service curve parameters are converted to the internal
  79. * representation. The slope values are scaled to avoid overflow.
  80. * the inverse slope values as well as the y-projection of the 1st
  81. * segment are kept in order to to avoid 64-bit divide operations
  82. * that are expensive on 32-bit architectures.
  83. */
  84. struct internal_sc
  85. {
  86. u64 sm1; /* scaled slope of the 1st segment */
  87. u64 ism1; /* scaled inverse-slope of the 1st segment */
  88. u64 dx; /* the x-projection of the 1st segment */
  89. u64 dy; /* the y-projection of the 1st segment */
  90. u64 sm2; /* scaled slope of the 2nd segment */
  91. u64 ism2; /* scaled inverse-slope of the 2nd segment */
  92. };
  93. /* runtime service curve */
  94. struct runtime_sc
  95. {
  96. u64 x; /* current starting position on x-axis */
  97. u64 y; /* current starting position on y-axis */
  98. u64 sm1; /* scaled slope of the 1st segment */
  99. u64 ism1; /* scaled inverse-slope of the 1st segment */
  100. u64 dx; /* the x-projection of the 1st segment */
  101. u64 dy; /* the y-projection of the 1st segment */
  102. u64 sm2; /* scaled slope of the 2nd segment */
  103. u64 ism2; /* scaled inverse-slope of the 2nd segment */
  104. };
  105. enum hfsc_class_flags
  106. {
  107. HFSC_RSC = 0x1,
  108. HFSC_FSC = 0x2,
  109. HFSC_USC = 0x4
  110. };
  111. struct hfsc_class
  112. {
  113. u32 classid; /* class id */
  114. unsigned int refcnt; /* usage count */
  115. struct gnet_stats_basic bstats;
  116. struct gnet_stats_queue qstats;
  117. struct gnet_stats_rate_est rate_est;
  118. spinlock_t *stats_lock;
  119. unsigned int level; /* class level in hierarchy */
  120. struct tcf_proto *filter_list; /* filter list */
  121. unsigned int filter_cnt; /* filter count */
  122. struct hfsc_sched *sched; /* scheduler data */
  123. struct hfsc_class *cl_parent; /* parent class */
  124. struct list_head siblings; /* sibling classes */
  125. struct list_head children; /* child classes */
  126. struct Qdisc *qdisc; /* leaf qdisc */
  127. struct rb_node el_node; /* qdisc's eligible tree member */
  128. struct rb_root vt_tree; /* active children sorted by cl_vt */
  129. struct rb_node vt_node; /* parent's vt_tree member */
  130. struct rb_root cf_tree; /* active children sorted by cl_f */
  131. struct rb_node cf_node; /* parent's cf_heap member */
  132. struct list_head hlist; /* hash list member */
  133. struct list_head dlist; /* drop list member */
  134. u64 cl_total; /* total work in bytes */
  135. u64 cl_cumul; /* cumulative work in bytes done by
  136. real-time criteria */
  137. u64 cl_d; /* deadline*/
  138. u64 cl_e; /* eligible time */
  139. u64 cl_vt; /* virtual time */
  140. u64 cl_f; /* time when this class will fit for
  141. link-sharing, max(myf, cfmin) */
  142. u64 cl_myf; /* my fit-time (calculated from this
  143. class's own upperlimit curve) */
  144. u64 cl_myfadj; /* my fit-time adjustment (to cancel
  145. history dependence) */
  146. u64 cl_cfmin; /* earliest children's fit-time (used
  147. with cl_myf to obtain cl_f) */
  148. u64 cl_cvtmin; /* minimal virtual time among the
  149. children fit for link-sharing
  150. (monotonic within a period) */
  151. u64 cl_vtadj; /* intra-period cumulative vt
  152. adjustment */
  153. u64 cl_vtoff; /* inter-period cumulative vt offset */
  154. u64 cl_cvtmax; /* max child's vt in the last period */
  155. u64 cl_cvtoff; /* cumulative cvtmax of all periods */
  156. u64 cl_pcvtoff; /* parent's cvtoff at initalization
  157. time */
  158. struct internal_sc cl_rsc; /* internal real-time service curve */
  159. struct internal_sc cl_fsc; /* internal fair service curve */
  160. struct internal_sc cl_usc; /* internal upperlimit service curve */
  161. struct runtime_sc cl_deadline; /* deadline curve */
  162. struct runtime_sc cl_eligible; /* eligible curve */
  163. struct runtime_sc cl_virtual; /* virtual curve */
  164. struct runtime_sc cl_ulimit; /* upperlimit curve */
  165. unsigned long cl_flags; /* which curves are valid */
  166. unsigned long cl_vtperiod; /* vt period sequence number */
  167. unsigned long cl_parentperiod;/* parent's vt period sequence number*/
  168. unsigned long cl_nactive; /* number of active children */
  169. };
  170. #define HFSC_HSIZE 16
  171. struct hfsc_sched
  172. {
  173. u16 defcls; /* default class id */
  174. struct hfsc_class root; /* root class */
  175. struct list_head clhash[HFSC_HSIZE]; /* class hash */
  176. struct rb_root eligible; /* eligible tree */
  177. struct list_head droplist; /* active leaf class list (for
  178. dropping) */
  179. struct sk_buff_head requeue; /* requeued packet */
  180. struct timer_list wd_timer; /* watchdog timer */
  181. };
  182. /*
  183. * macros
  184. */
  185. #ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY
  186. #include <linux/time.h>
  187. #undef PSCHED_GET_TIME
  188. #define PSCHED_GET_TIME(stamp) \
  189. do { \
  190. struct timeval tv; \
  191. do_gettimeofday(&tv); \
  192. (stamp) = 1ULL * USEC_PER_SEC * tv.tv_sec + tv.tv_usec; \
  193. } while (0)
  194. #endif
  195. #define HT_INFINITY 0xffffffffffffffffULL /* infinite time value */
  196. /*
  197. * eligible tree holds backlogged classes being sorted by their eligible times.
  198. * there is one eligible tree per hfsc instance.
  199. */
  200. static void
  201. eltree_insert(struct hfsc_class *cl)
  202. {
  203. struct rb_node **p = &cl->sched->eligible.rb_node;
  204. struct rb_node *parent = NULL;
  205. struct hfsc_class *cl1;
  206. while (*p != NULL) {
  207. parent = *p;
  208. cl1 = rb_entry(parent, struct hfsc_class, el_node);
  209. if (cl->cl_e >= cl1->cl_e)
  210. p = &parent->rb_right;
  211. else
  212. p = &parent->rb_left;
  213. }
  214. rb_link_node(&cl->el_node, parent, p);
  215. rb_insert_color(&cl->el_node, &cl->sched->eligible);
  216. }
  217. static inline void
  218. eltree_remove(struct hfsc_class *cl)
  219. {
  220. rb_erase(&cl->el_node, &cl->sched->eligible);
  221. }
  222. static inline void
  223. eltree_update(struct hfsc_class *cl)
  224. {
  225. eltree_remove(cl);
  226. eltree_insert(cl);
  227. }
  228. /* find the class with the minimum deadline among the eligible classes */
  229. static inline struct hfsc_class *
  230. eltree_get_mindl(struct hfsc_sched *q, u64 cur_time)
  231. {
  232. struct hfsc_class *p, *cl = NULL;
  233. struct rb_node *n;
  234. for (n = rb_first(&q->eligible); n != NULL; n = rb_next(n)) {
  235. p = rb_entry(n, struct hfsc_class, el_node);
  236. if (p->cl_e > cur_time)
  237. break;
  238. if (cl == NULL || p->cl_d < cl->cl_d)
  239. cl = p;
  240. }
  241. return cl;
  242. }
  243. /* find the class with minimum eligible time among the eligible classes */
  244. static inline struct hfsc_class *
  245. eltree_get_minel(struct hfsc_sched *q)
  246. {
  247. struct rb_node *n;
  248. n = rb_first(&q->eligible);
  249. if (n == NULL)
  250. return NULL;
  251. return rb_entry(n, struct hfsc_class, el_node);
  252. }
  253. /*
  254. * vttree holds holds backlogged child classes being sorted by their virtual
  255. * time. each intermediate class has one vttree.
  256. */
  257. static void
  258. vttree_insert(struct hfsc_class *cl)
  259. {
  260. struct rb_node **p = &cl->cl_parent->vt_tree.rb_node;
  261. struct rb_node *parent = NULL;
  262. struct hfsc_class *cl1;
  263. while (*p != NULL) {
  264. parent = *p;
  265. cl1 = rb_entry(parent, struct hfsc_class, vt_node);
  266. if (cl->cl_vt >= cl1->cl_vt)
  267. p = &parent->rb_right;
  268. else
  269. p = &parent->rb_left;
  270. }
  271. rb_link_node(&cl->vt_node, parent, p);
  272. rb_insert_color(&cl->vt_node, &cl->cl_parent->vt_tree);
  273. }
  274. static inline void
  275. vttree_remove(struct hfsc_class *cl)
  276. {
  277. rb_erase(&cl->vt_node, &cl->cl_parent->vt_tree);
  278. }
  279. static inline void
  280. vttree_update(struct hfsc_class *cl)
  281. {
  282. vttree_remove(cl);
  283. vttree_insert(cl);
  284. }
  285. static inline struct hfsc_class *
  286. vttree_firstfit(struct hfsc_class *cl, u64 cur_time)
  287. {
  288. struct hfsc_class *p;
  289. struct rb_node *n;
  290. for (n = rb_first(&cl->vt_tree); n != NULL; n = rb_next(n)) {
  291. p = rb_entry(n, struct hfsc_class, vt_node);
  292. if (p->cl_f <= cur_time)
  293. return p;
  294. }
  295. return NULL;
  296. }
  297. /*
  298. * get the leaf class with the minimum vt in the hierarchy
  299. */
  300. static struct hfsc_class *
  301. vttree_get_minvt(struct hfsc_class *cl, u64 cur_time)
  302. {
  303. /* if root-class's cfmin is bigger than cur_time nothing to do */
  304. if (cl->cl_cfmin > cur_time)
  305. return NULL;
  306. while (cl->level > 0) {
  307. cl = vttree_firstfit(cl, cur_time);
  308. if (cl == NULL)
  309. return NULL;
  310. /*
  311. * update parent's cl_cvtmin.
  312. */
  313. if (cl->cl_parent->cl_cvtmin < cl->cl_vt)
  314. cl->cl_parent->cl_cvtmin = cl->cl_vt;
  315. }
  316. return cl;
  317. }
  318. static void
  319. cftree_insert(struct hfsc_class *cl)
  320. {
  321. struct rb_node **p = &cl->cl_parent->cf_tree.rb_node;
  322. struct rb_node *parent = NULL;
  323. struct hfsc_class *cl1;
  324. while (*p != NULL) {
  325. parent = *p;
  326. cl1 = rb_entry(parent, struct hfsc_class, cf_node);
  327. if (cl->cl_f >= cl1->cl_f)
  328. p = &parent->rb_right;
  329. else
  330. p = &parent->rb_left;
  331. }
  332. rb_link_node(&cl->cf_node, parent, p);
  333. rb_insert_color(&cl->cf_node, &cl->cl_parent->cf_tree);
  334. }
  335. static inline void
  336. cftree_remove(struct hfsc_class *cl)
  337. {
  338. rb_erase(&cl->cf_node, &cl->cl_parent->cf_tree);
  339. }
  340. static inline void
  341. cftree_update(struct hfsc_class *cl)
  342. {
  343. cftree_remove(cl);
  344. cftree_insert(cl);
  345. }
  346. /*
  347. * service curve support functions
  348. *
  349. * external service curve parameters
  350. * m: bps
  351. * d: us
  352. * internal service curve parameters
  353. * sm: (bytes/psched_us) << SM_SHIFT
  354. * ism: (psched_us/byte) << ISM_SHIFT
  355. * dx: psched_us
  356. *
  357. * Clock source resolution (CONFIG_NET_SCH_CLK_*)
  358. * JIFFIES: for 48<=HZ<=1534 resolution is between 0.63us and 1.27us.
  359. * CPU: resolution is between 0.5us and 1us.
  360. * GETTIMEOFDAY: resolution is exactly 1us.
  361. *
  362. * sm and ism are scaled in order to keep effective digits.
  363. * SM_SHIFT and ISM_SHIFT are selected to keep at least 4 effective
  364. * digits in decimal using the following table.
  365. *
  366. * Note: We can afford the additional accuracy (altq hfsc keeps at most
  367. * 3 effective digits) thanks to the fact that linux clock is bounded
  368. * much more tightly.
  369. *
  370. * bits/sec 100Kbps 1Mbps 10Mbps 100Mbps 1Gbps
  371. * ------------+-------------------------------------------------------
  372. * bytes/0.5us 6.25e-3 62.5e-3 625e-3 6250e-e 62500e-3
  373. * bytes/us 12.5e-3 125e-3 1250e-3 12500e-3 125000e-3
  374. * bytes/1.27us 15.875e-3 158.75e-3 1587.5e-3 15875e-3 158750e-3
  375. *
  376. * 0.5us/byte 160 16 1.6 0.16 0.016
  377. * us/byte 80 8 0.8 0.08 0.008
  378. * 1.27us/byte 63 6.3 0.63 0.063 0.0063
  379. */
  380. #define SM_SHIFT 20
  381. #define ISM_SHIFT 18
  382. #define SM_MASK ((1ULL << SM_SHIFT) - 1)
  383. #define ISM_MASK ((1ULL << ISM_SHIFT) - 1)
  384. static inline u64
  385. seg_x2y(u64 x, u64 sm)
  386. {
  387. u64 y;
  388. /*
  389. * compute
  390. * y = x * sm >> SM_SHIFT
  391. * but divide it for the upper and lower bits to avoid overflow
  392. */
  393. y = (x >> SM_SHIFT) * sm + (((x & SM_MASK) * sm) >> SM_SHIFT);
  394. return y;
  395. }
  396. static inline u64
  397. seg_y2x(u64 y, u64 ism)
  398. {
  399. u64 x;
  400. if (y == 0)
  401. x = 0;
  402. else if (ism == HT_INFINITY)
  403. x = HT_INFINITY;
  404. else {
  405. x = (y >> ISM_SHIFT) * ism
  406. + (((y & ISM_MASK) * ism) >> ISM_SHIFT);
  407. }
  408. return x;
  409. }
  410. /* Convert m (bps) into sm (bytes/psched us) */
  411. static u64
  412. m2sm(u32 m)
  413. {
  414. u64 sm;
  415. sm = ((u64)m << SM_SHIFT);
  416. sm += PSCHED_JIFFIE2US(HZ) - 1;
  417. do_div(sm, PSCHED_JIFFIE2US(HZ));
  418. return sm;
  419. }
  420. /* convert m (bps) into ism (psched us/byte) */
  421. static u64
  422. m2ism(u32 m)
  423. {
  424. u64 ism;
  425. if (m == 0)
  426. ism = HT_INFINITY;
  427. else {
  428. ism = ((u64)PSCHED_JIFFIE2US(HZ) << ISM_SHIFT);
  429. ism += m - 1;
  430. do_div(ism, m);
  431. }
  432. return ism;
  433. }
  434. /* convert d (us) into dx (psched us) */
  435. static u64
  436. d2dx(u32 d)
  437. {
  438. u64 dx;
  439. dx = ((u64)d * PSCHED_JIFFIE2US(HZ));
  440. dx += USEC_PER_SEC - 1;
  441. do_div(dx, USEC_PER_SEC);
  442. return dx;
  443. }
  444. /* convert sm (bytes/psched us) into m (bps) */
  445. static u32
  446. sm2m(u64 sm)
  447. {
  448. u64 m;
  449. m = (sm * PSCHED_JIFFIE2US(HZ)) >> SM_SHIFT;
  450. return (u32)m;
  451. }
  452. /* convert dx (psched us) into d (us) */
  453. static u32
  454. dx2d(u64 dx)
  455. {
  456. u64 d;
  457. d = dx * USEC_PER_SEC;
  458. do_div(d, PSCHED_JIFFIE2US(HZ));
  459. return (u32)d;
  460. }
  461. static void
  462. sc2isc(struct tc_service_curve *sc, struct internal_sc *isc)
  463. {
  464. isc->sm1 = m2sm(sc->m1);
  465. isc->ism1 = m2ism(sc->m1);
  466. isc->dx = d2dx(sc->d);
  467. isc->dy = seg_x2y(isc->dx, isc->sm1);
  468. isc->sm2 = m2sm(sc->m2);
  469. isc->ism2 = m2ism(sc->m2);
  470. }
  471. /*
  472. * initialize the runtime service curve with the given internal
  473. * service curve starting at (x, y).
  474. */
  475. static void
  476. rtsc_init(struct runtime_sc *rtsc, struct internal_sc *isc, u64 x, u64 y)
  477. {
  478. rtsc->x = x;
  479. rtsc->y = y;
  480. rtsc->sm1 = isc->sm1;
  481. rtsc->ism1 = isc->ism1;
  482. rtsc->dx = isc->dx;
  483. rtsc->dy = isc->dy;
  484. rtsc->sm2 = isc->sm2;
  485. rtsc->ism2 = isc->ism2;
  486. }
  487. /*
  488. * calculate the y-projection of the runtime service curve by the
  489. * given x-projection value
  490. */
  491. static u64
  492. rtsc_y2x(struct runtime_sc *rtsc, u64 y)
  493. {
  494. u64 x;
  495. if (y < rtsc->y)
  496. x = rtsc->x;
  497. else if (y <= rtsc->y + rtsc->dy) {
  498. /* x belongs to the 1st segment */
  499. if (rtsc->dy == 0)
  500. x = rtsc->x + rtsc->dx;
  501. else
  502. x = rtsc->x + seg_y2x(y - rtsc->y, rtsc->ism1);
  503. } else {
  504. /* x belongs to the 2nd segment */
  505. x = rtsc->x + rtsc->dx
  506. + seg_y2x(y - rtsc->y - rtsc->dy, rtsc->ism2);
  507. }
  508. return x;
  509. }
  510. static u64
  511. rtsc_x2y(struct runtime_sc *rtsc, u64 x)
  512. {
  513. u64 y;
  514. if (x <= rtsc->x)
  515. y = rtsc->y;
  516. else if (x <= rtsc->x + rtsc->dx)
  517. /* y belongs to the 1st segment */
  518. y = rtsc->y + seg_x2y(x - rtsc->x, rtsc->sm1);
  519. else
  520. /* y belongs to the 2nd segment */
  521. y = rtsc->y + rtsc->dy
  522. + seg_x2y(x - rtsc->x - rtsc->dx, rtsc->sm2);
  523. return y;
  524. }
  525. /*
  526. * update the runtime service curve by taking the minimum of the current
  527. * runtime service curve and the service curve starting at (x, y).
  528. */
  529. static void
  530. rtsc_min(struct runtime_sc *rtsc, struct internal_sc *isc, u64 x, u64 y)
  531. {
  532. u64 y1, y2, dx, dy;
  533. u32 dsm;
  534. if (isc->sm1 <= isc->sm2) {
  535. /* service curve is convex */
  536. y1 = rtsc_x2y(rtsc, x);
  537. if (y1 < y)
  538. /* the current rtsc is smaller */
  539. return;
  540. rtsc->x = x;
  541. rtsc->y = y;
  542. return;
  543. }
  544. /*
  545. * service curve is concave
  546. * compute the two y values of the current rtsc
  547. * y1: at x
  548. * y2: at (x + dx)
  549. */
  550. y1 = rtsc_x2y(rtsc, x);
  551. if (y1 <= y) {
  552. /* rtsc is below isc, no change to rtsc */
  553. return;
  554. }
  555. y2 = rtsc_x2y(rtsc, x + isc->dx);
  556. if (y2 >= y + isc->dy) {
  557. /* rtsc is above isc, replace rtsc by isc */
  558. rtsc->x = x;
  559. rtsc->y = y;
  560. rtsc->dx = isc->dx;
  561. rtsc->dy = isc->dy;
  562. return;
  563. }
  564. /*
  565. * the two curves intersect
  566. * compute the offsets (dx, dy) using the reverse
  567. * function of seg_x2y()
  568. * seg_x2y(dx, sm1) == seg_x2y(dx, sm2) + (y1 - y)
  569. */
  570. dx = (y1 - y) << SM_SHIFT;
  571. dsm = isc->sm1 - isc->sm2;
  572. do_div(dx, dsm);
  573. /*
  574. * check if (x, y1) belongs to the 1st segment of rtsc.
  575. * if so, add the offset.
  576. */
  577. if (rtsc->x + rtsc->dx > x)
  578. dx += rtsc->x + rtsc->dx - x;
  579. dy = seg_x2y(dx, isc->sm1);
  580. rtsc->x = x;
  581. rtsc->y = y;
  582. rtsc->dx = dx;
  583. rtsc->dy = dy;
  584. return;
  585. }
  586. static void
  587. init_ed(struct hfsc_class *cl, unsigned int next_len)
  588. {
  589. u64 cur_time;
  590. PSCHED_GET_TIME(cur_time);
  591. /* update the deadline curve */
  592. rtsc_min(&cl->cl_deadline, &cl->cl_rsc, cur_time, cl->cl_cumul);
  593. /*
  594. * update the eligible curve.
  595. * for concave, it is equal to the deadline curve.
  596. * for convex, it is a linear curve with slope m2.
  597. */
  598. cl->cl_eligible = cl->cl_deadline;
  599. if (cl->cl_rsc.sm1 <= cl->cl_rsc.sm2) {
  600. cl->cl_eligible.dx = 0;
  601. cl->cl_eligible.dy = 0;
  602. }
  603. /* compute e and d */
  604. cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul);
  605. cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
  606. eltree_insert(cl);
  607. }
  608. static void
  609. update_ed(struct hfsc_class *cl, unsigned int next_len)
  610. {
  611. cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul);
  612. cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
  613. eltree_update(cl);
  614. }
  615. static inline void
  616. update_d(struct hfsc_class *cl, unsigned int next_len)
  617. {
  618. cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
  619. }
  620. static inline void
  621. update_cfmin(struct hfsc_class *cl)
  622. {
  623. struct rb_node *n = rb_first(&cl->cf_tree);
  624. struct hfsc_class *p;
  625. if (n == NULL) {
  626. cl->cl_cfmin = 0;
  627. return;
  628. }
  629. p = rb_entry(n, struct hfsc_class, cf_node);
  630. cl->cl_cfmin = p->cl_f;
  631. }
  632. static void
  633. init_vf(struct hfsc_class *cl, unsigned int len)
  634. {
  635. struct hfsc_class *max_cl;
  636. struct rb_node *n;
  637. u64 vt, f, cur_time;
  638. int go_active;
  639. cur_time = 0;
  640. go_active = 1;
  641. for (; cl->cl_parent != NULL; cl = cl->cl_parent) {
  642. if (go_active && cl->cl_nactive++ == 0)
  643. go_active = 1;
  644. else
  645. go_active = 0;
  646. if (go_active) {
  647. n = rb_last(&cl->cl_parent->vt_tree);
  648. if (n != NULL) {
  649. max_cl = rb_entry(n, struct hfsc_class,vt_node);
  650. /*
  651. * set vt to the average of the min and max
  652. * classes. if the parent's period didn't
  653. * change, don't decrease vt of the class.
  654. */
  655. vt = max_cl->cl_vt;
  656. if (cl->cl_parent->cl_cvtmin != 0)
  657. vt = (cl->cl_parent->cl_cvtmin + vt)/2;
  658. if (cl->cl_parent->cl_vtperiod !=
  659. cl->cl_parentperiod || vt > cl->cl_vt)
  660. cl->cl_vt = vt;
  661. } else {
  662. /*
  663. * first child for a new parent backlog period.
  664. * add parent's cvtmax to cvtoff to make a new
  665. * vt (vtoff + vt) larger than the vt in the
  666. * last period for all children.
  667. */
  668. vt = cl->cl_parent->cl_cvtmax;
  669. cl->cl_parent->cl_cvtoff += vt;
  670. cl->cl_parent->cl_cvtmax = 0;
  671. cl->cl_parent->cl_cvtmin = 0;
  672. cl->cl_vt = 0;
  673. }
  674. cl->cl_vtoff = cl->cl_parent->cl_cvtoff -
  675. cl->cl_pcvtoff;
  676. /* update the virtual curve */
  677. vt = cl->cl_vt + cl->cl_vtoff;
  678. rtsc_min(&cl->cl_virtual, &cl->cl_fsc, vt,
  679. cl->cl_total);
  680. if (cl->cl_virtual.x == vt) {
  681. cl->cl_virtual.x -= cl->cl_vtoff;
  682. cl->cl_vtoff = 0;
  683. }
  684. cl->cl_vtadj = 0;
  685. cl->cl_vtperiod++; /* increment vt period */
  686. cl->cl_parentperiod = cl->cl_parent->cl_vtperiod;
  687. if (cl->cl_parent->cl_nactive == 0)
  688. cl->cl_parentperiod++;
  689. cl->cl_f = 0;
  690. vttree_insert(cl);
  691. cftree_insert(cl);
  692. if (cl->cl_flags & HFSC_USC) {
  693. /* class has upper limit curve */
  694. if (cur_time == 0)
  695. PSCHED_GET_TIME(cur_time);
  696. /* update the ulimit curve */
  697. rtsc_min(&cl->cl_ulimit, &cl->cl_usc, cur_time,
  698. cl->cl_total);
  699. /* compute myf */
  700. cl->cl_myf = rtsc_y2x(&cl->cl_ulimit,
  701. cl->cl_total);
  702. cl->cl_myfadj = 0;
  703. }
  704. }
  705. f = max(cl->cl_myf, cl->cl_cfmin);
  706. if (f != cl->cl_f) {
  707. cl->cl_f = f;
  708. cftree_update(cl);
  709. update_cfmin(cl->cl_parent);
  710. }
  711. }
  712. }
  713. static void
  714. update_vf(struct hfsc_class *cl, unsigned int len, u64 cur_time)
  715. {
  716. u64 f; /* , myf_bound, delta; */
  717. int go_passive = 0;
  718. if (cl->qdisc->q.qlen == 0 && cl->cl_flags & HFSC_FSC)
  719. go_passive = 1;
  720. for (; cl->cl_parent != NULL; cl = cl->cl_parent) {
  721. cl->cl_total += len;
  722. if (!(cl->cl_flags & HFSC_FSC) || cl->cl_nactive == 0)
  723. continue;
  724. if (go_passive && --cl->cl_nactive == 0)
  725. go_passive = 1;
  726. else
  727. go_passive = 0;
  728. if (go_passive) {
  729. /* no more active child, going passive */
  730. /* update cvtmax of the parent class */
  731. if (cl->cl_vt > cl->cl_parent->cl_cvtmax)
  732. cl->cl_parent->cl_cvtmax = cl->cl_vt;
  733. /* remove this class from the vt tree */
  734. vttree_remove(cl);
  735. cftree_remove(cl);
  736. update_cfmin(cl->cl_parent);
  737. continue;
  738. }
  739. /*
  740. * update vt and f
  741. */
  742. cl->cl_vt = rtsc_y2x(&cl->cl_virtual, cl->cl_total)
  743. - cl->cl_vtoff + cl->cl_vtadj;
  744. /*
  745. * if vt of the class is smaller than cvtmin,
  746. * the class was skipped in the past due to non-fit.
  747. * if so, we need to adjust vtadj.
  748. */
  749. if (cl->cl_vt < cl->cl_parent->cl_cvtmin) {
  750. cl->cl_vtadj += cl->cl_parent->cl_cvtmin - cl->cl_vt;
  751. cl->cl_vt = cl->cl_parent->cl_cvtmin;
  752. }
  753. /* update the vt tree */
  754. vttree_update(cl);
  755. if (cl->cl_flags & HFSC_USC) {
  756. cl->cl_myf = cl->cl_myfadj + rtsc_y2x(&cl->cl_ulimit,
  757. cl->cl_total);
  758. #if 0
  759. /*
  760. * This code causes classes to stay way under their
  761. * limit when multiple classes are used at gigabit
  762. * speed. needs investigation. -kaber
  763. */
  764. /*
  765. * if myf lags behind by more than one clock tick
  766. * from the current time, adjust myfadj to prevent
  767. * a rate-limited class from going greedy.
  768. * in a steady state under rate-limiting, myf
  769. * fluctuates within one clock tick.
  770. */
  771. myf_bound = cur_time - PSCHED_JIFFIE2US(1);
  772. if (cl->cl_myf < myf_bound) {
  773. delta = cur_time - cl->cl_myf;
  774. cl->cl_myfadj += delta;
  775. cl->cl_myf += delta;
  776. }
  777. #endif
  778. }
  779. f = max(cl->cl_myf, cl->cl_cfmin);
  780. if (f != cl->cl_f) {
  781. cl->cl_f = f;
  782. cftree_update(cl);
  783. update_cfmin(cl->cl_parent);
  784. }
  785. }
  786. }
  787. static void
  788. set_active(struct hfsc_class *cl, unsigned int len)
  789. {
  790. if (cl->cl_flags & HFSC_RSC)
  791. init_ed(cl, len);
  792. if (cl->cl_flags & HFSC_FSC)
  793. init_vf(cl, len);
  794. list_add_tail(&cl->dlist, &cl->sched->droplist);
  795. }
  796. static void
  797. set_passive(struct hfsc_class *cl)
  798. {
  799. if (cl->cl_flags & HFSC_RSC)
  800. eltree_remove(cl);
  801. list_del(&cl->dlist);
  802. /*
  803. * vttree is now handled in update_vf() so that update_vf(cl, 0, 0)
  804. * needs to be called explicitly to remove a class from vttree.
  805. */
  806. }
  807. /*
  808. * hack to get length of first packet in queue.
  809. */
  810. static unsigned int
  811. qdisc_peek_len(struct Qdisc *sch)
  812. {
  813. struct sk_buff *skb;
  814. unsigned int len;
  815. skb = sch->dequeue(sch);
  816. if (skb == NULL) {
  817. if (net_ratelimit())
  818. printk("qdisc_peek_len: non work-conserving qdisc ?\n");
  819. return 0;
  820. }
  821. len = skb->len;
  822. if (unlikely(sch->ops->requeue(skb, sch) != NET_XMIT_SUCCESS)) {
  823. if (net_ratelimit())
  824. printk("qdisc_peek_len: failed to requeue\n");
  825. qdisc_tree_decrease_qlen(sch, 1);
  826. return 0;
  827. }
  828. return len;
  829. }
  830. static void
  831. hfsc_purge_queue(struct Qdisc *sch, struct hfsc_class *cl)
  832. {
  833. unsigned int len = cl->qdisc->q.qlen;
  834. qdisc_reset(cl->qdisc);
  835. qdisc_tree_decrease_qlen(cl->qdisc, len);
  836. }
  837. static void
  838. hfsc_adjust_levels(struct hfsc_class *cl)
  839. {
  840. struct hfsc_class *p;
  841. unsigned int level;
  842. do {
  843. level = 0;
  844. list_for_each_entry(p, &cl->children, siblings) {
  845. if (p->level >= level)
  846. level = p->level + 1;
  847. }
  848. cl->level = level;
  849. } while ((cl = cl->cl_parent) != NULL);
  850. }
  851. static inline unsigned int
  852. hfsc_hash(u32 h)
  853. {
  854. h ^= h >> 8;
  855. h ^= h >> 4;
  856. return h & (HFSC_HSIZE - 1);
  857. }
  858. static inline struct hfsc_class *
  859. hfsc_find_class(u32 classid, struct Qdisc *sch)
  860. {
  861. struct hfsc_sched *q = qdisc_priv(sch);
  862. struct hfsc_class *cl;
  863. list_for_each_entry(cl, &q->clhash[hfsc_hash(classid)], hlist) {
  864. if (cl->classid == classid)
  865. return cl;
  866. }
  867. return NULL;
  868. }
  869. static void
  870. hfsc_change_rsc(struct hfsc_class *cl, struct tc_service_curve *rsc,
  871. u64 cur_time)
  872. {
  873. sc2isc(rsc, &cl->cl_rsc);
  874. rtsc_init(&cl->cl_deadline, &cl->cl_rsc, cur_time, cl->cl_cumul);
  875. cl->cl_eligible = cl->cl_deadline;
  876. if (cl->cl_rsc.sm1 <= cl->cl_rsc.sm2) {
  877. cl->cl_eligible.dx = 0;
  878. cl->cl_eligible.dy = 0;
  879. }
  880. cl->cl_flags |= HFSC_RSC;
  881. }
  882. static void
  883. hfsc_change_fsc(struct hfsc_class *cl, struct tc_service_curve *fsc)
  884. {
  885. sc2isc(fsc, &cl->cl_fsc);
  886. rtsc_init(&cl->cl_virtual, &cl->cl_fsc, cl->cl_vt, cl->cl_total);
  887. cl->cl_flags |= HFSC_FSC;
  888. }
  889. static void
  890. hfsc_change_usc(struct hfsc_class *cl, struct tc_service_curve *usc,
  891. u64 cur_time)
  892. {
  893. sc2isc(usc, &cl->cl_usc);
  894. rtsc_init(&cl->cl_ulimit, &cl->cl_usc, cur_time, cl->cl_total);
  895. cl->cl_flags |= HFSC_USC;
  896. }
  897. static int
  898. hfsc_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
  899. struct rtattr **tca, unsigned long *arg)
  900. {
  901. struct hfsc_sched *q = qdisc_priv(sch);
  902. struct hfsc_class *cl = (struct hfsc_class *)*arg;
  903. struct hfsc_class *parent = NULL;
  904. struct rtattr *opt = tca[TCA_OPTIONS-1];
  905. struct rtattr *tb[TCA_HFSC_MAX];
  906. struct tc_service_curve *rsc = NULL, *fsc = NULL, *usc = NULL;
  907. u64 cur_time;
  908. if (opt == NULL || rtattr_parse_nested(tb, TCA_HFSC_MAX, opt))
  909. return -EINVAL;
  910. if (tb[TCA_HFSC_RSC-1]) {
  911. if (RTA_PAYLOAD(tb[TCA_HFSC_RSC-1]) < sizeof(*rsc))
  912. return -EINVAL;
  913. rsc = RTA_DATA(tb[TCA_HFSC_RSC-1]);
  914. if (rsc->m1 == 0 && rsc->m2 == 0)
  915. rsc = NULL;
  916. }
  917. if (tb[TCA_HFSC_FSC-1]) {
  918. if (RTA_PAYLOAD(tb[TCA_HFSC_FSC-1]) < sizeof(*fsc))
  919. return -EINVAL;
  920. fsc = RTA_DATA(tb[TCA_HFSC_FSC-1]);
  921. if (fsc->m1 == 0 && fsc->m2 == 0)
  922. fsc = NULL;
  923. }
  924. if (tb[TCA_HFSC_USC-1]) {
  925. if (RTA_PAYLOAD(tb[TCA_HFSC_USC-1]) < sizeof(*usc))
  926. return -EINVAL;
  927. usc = RTA_DATA(tb[TCA_HFSC_USC-1]);
  928. if (usc->m1 == 0 && usc->m2 == 0)
  929. usc = NULL;
  930. }
  931. if (cl != NULL) {
  932. if (parentid) {
  933. if (cl->cl_parent && cl->cl_parent->classid != parentid)
  934. return -EINVAL;
  935. if (cl->cl_parent == NULL && parentid != TC_H_ROOT)
  936. return -EINVAL;
  937. }
  938. PSCHED_GET_TIME(cur_time);
  939. sch_tree_lock(sch);
  940. if (rsc != NULL)
  941. hfsc_change_rsc(cl, rsc, cur_time);
  942. if (fsc != NULL)
  943. hfsc_change_fsc(cl, fsc);
  944. if (usc != NULL)
  945. hfsc_change_usc(cl, usc, cur_time);
  946. if (cl->qdisc->q.qlen != 0) {
  947. if (cl->cl_flags & HFSC_RSC)
  948. update_ed(cl, qdisc_peek_len(cl->qdisc));
  949. if (cl->cl_flags & HFSC_FSC)
  950. update_vf(cl, 0, cur_time);
  951. }
  952. sch_tree_unlock(sch);
  953. #ifdef CONFIG_NET_ESTIMATOR
  954. if (tca[TCA_RATE-1])
  955. gen_replace_estimator(&cl->bstats, &cl->rate_est,
  956. cl->stats_lock, tca[TCA_RATE-1]);
  957. #endif
  958. return 0;
  959. }
  960. if (parentid == TC_H_ROOT)
  961. return -EEXIST;
  962. parent = &q->root;
  963. if (parentid) {
  964. parent = hfsc_find_class(parentid, sch);
  965. if (parent == NULL)
  966. return -ENOENT;
  967. }
  968. if (classid == 0 || TC_H_MAJ(classid ^ sch->handle) != 0)
  969. return -EINVAL;
  970. if (hfsc_find_class(classid, sch))
  971. return -EEXIST;
  972. if (rsc == NULL && fsc == NULL)
  973. return -EINVAL;
  974. cl = kzalloc(sizeof(struct hfsc_class), GFP_KERNEL);
  975. if (cl == NULL)
  976. return -ENOBUFS;
  977. if (rsc != NULL)
  978. hfsc_change_rsc(cl, rsc, 0);
  979. if (fsc != NULL)
  980. hfsc_change_fsc(cl, fsc);
  981. if (usc != NULL)
  982. hfsc_change_usc(cl, usc, 0);
  983. cl->refcnt = 1;
  984. cl->classid = classid;
  985. cl->sched = q;
  986. cl->cl_parent = parent;
  987. cl->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid);
  988. if (cl->qdisc == NULL)
  989. cl->qdisc = &noop_qdisc;
  990. cl->stats_lock = &sch->dev->queue_lock;
  991. INIT_LIST_HEAD(&cl->children);
  992. cl->vt_tree = RB_ROOT;
  993. cl->cf_tree = RB_ROOT;
  994. sch_tree_lock(sch);
  995. list_add_tail(&cl->hlist, &q->clhash[hfsc_hash(classid)]);
  996. list_add_tail(&cl->siblings, &parent->children);
  997. if (parent->level == 0)
  998. hfsc_purge_queue(sch, parent);
  999. hfsc_adjust_levels(parent);
  1000. cl->cl_pcvtoff = parent->cl_cvtoff;
  1001. sch_tree_unlock(sch);
  1002. #ifdef CONFIG_NET_ESTIMATOR
  1003. if (tca[TCA_RATE-1])
  1004. gen_new_estimator(&cl->bstats, &cl->rate_est,
  1005. cl->stats_lock, tca[TCA_RATE-1]);
  1006. #endif
  1007. *arg = (unsigned long)cl;
  1008. return 0;
  1009. }
  1010. static void
  1011. hfsc_destroy_filters(struct tcf_proto **fl)
  1012. {
  1013. struct tcf_proto *tp;
  1014. while ((tp = *fl) != NULL) {
  1015. *fl = tp->next;
  1016. tcf_destroy(tp);
  1017. }
  1018. }
  1019. static void
  1020. hfsc_destroy_class(struct Qdisc *sch, struct hfsc_class *cl)
  1021. {
  1022. struct hfsc_sched *q = qdisc_priv(sch);
  1023. hfsc_destroy_filters(&cl->filter_list);
  1024. qdisc_destroy(cl->qdisc);
  1025. #ifdef CONFIG_NET_ESTIMATOR
  1026. gen_kill_estimator(&cl->bstats, &cl->rate_est);
  1027. #endif
  1028. if (cl != &q->root)
  1029. kfree(cl);
  1030. }
  1031. static int
  1032. hfsc_delete_class(struct Qdisc *sch, unsigned long arg)
  1033. {
  1034. struct hfsc_sched *q = qdisc_priv(sch);
  1035. struct hfsc_class *cl = (struct hfsc_class *)arg;
  1036. if (cl->level > 0 || cl->filter_cnt > 0 || cl == &q->root)
  1037. return -EBUSY;
  1038. sch_tree_lock(sch);
  1039. list_del(&cl->siblings);
  1040. hfsc_adjust_levels(cl->cl_parent);
  1041. hfsc_purge_queue(sch, cl);
  1042. list_del(&cl->hlist);
  1043. if (--cl->refcnt == 0)
  1044. hfsc_destroy_class(sch, cl);
  1045. sch_tree_unlock(sch);
  1046. return 0;
  1047. }
  1048. static struct hfsc_class *
  1049. hfsc_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr)
  1050. {
  1051. struct hfsc_sched *q = qdisc_priv(sch);
  1052. struct hfsc_class *cl;
  1053. struct tcf_result res;
  1054. struct tcf_proto *tcf;
  1055. int result;
  1056. if (TC_H_MAJ(skb->priority ^ sch->handle) == 0 &&
  1057. (cl = hfsc_find_class(skb->priority, sch)) != NULL)
  1058. if (cl->level == 0)
  1059. return cl;
  1060. *qerr = NET_XMIT_BYPASS;
  1061. tcf = q->root.filter_list;
  1062. while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
  1063. #ifdef CONFIG_NET_CLS_ACT
  1064. switch (result) {
  1065. case TC_ACT_QUEUED:
  1066. case TC_ACT_STOLEN:
  1067. *qerr = NET_XMIT_SUCCESS;
  1068. case TC_ACT_SHOT:
  1069. return NULL;
  1070. }
  1071. #elif defined(CONFIG_NET_CLS_POLICE)
  1072. if (result == TC_POLICE_SHOT)
  1073. return NULL;
  1074. #endif
  1075. if ((cl = (struct hfsc_class *)res.class) == NULL) {
  1076. if ((cl = hfsc_find_class(res.classid, sch)) == NULL)
  1077. break; /* filter selected invalid classid */
  1078. }
  1079. if (cl->level == 0)
  1080. return cl; /* hit leaf class */
  1081. /* apply inner filter chain */
  1082. tcf = cl->filter_list;
  1083. }
  1084. /* classification failed, try default class */
  1085. cl = hfsc_find_class(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
  1086. if (cl == NULL || cl->level > 0)
  1087. return NULL;
  1088. return cl;
  1089. }
  1090. static int
  1091. hfsc_graft_class(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
  1092. struct Qdisc **old)
  1093. {
  1094. struct hfsc_class *cl = (struct hfsc_class *)arg;
  1095. if (cl == NULL)
  1096. return -ENOENT;
  1097. if (cl->level > 0)
  1098. return -EINVAL;
  1099. if (new == NULL) {
  1100. new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
  1101. cl->classid);
  1102. if (new == NULL)
  1103. new = &noop_qdisc;
  1104. }
  1105. sch_tree_lock(sch);
  1106. hfsc_purge_queue(sch, cl);
  1107. *old = xchg(&cl->qdisc, new);
  1108. sch_tree_unlock(sch);
  1109. return 0;
  1110. }
  1111. static struct Qdisc *
  1112. hfsc_class_leaf(struct Qdisc *sch, unsigned long arg)
  1113. {
  1114. struct hfsc_class *cl = (struct hfsc_class *)arg;
  1115. if (cl != NULL && cl->level == 0)
  1116. return cl->qdisc;
  1117. return NULL;
  1118. }
  1119. static void
  1120. hfsc_qlen_notify(struct Qdisc *sch, unsigned long arg)
  1121. {
  1122. struct hfsc_class *cl = (struct hfsc_class *)arg;
  1123. if (cl->qdisc->q.qlen == 0) {
  1124. update_vf(cl, 0, 0);
  1125. set_passive(cl);
  1126. }
  1127. }
  1128. static unsigned long
  1129. hfsc_get_class(struct Qdisc *sch, u32 classid)
  1130. {
  1131. struct hfsc_class *cl = hfsc_find_class(classid, sch);
  1132. if (cl != NULL)
  1133. cl->refcnt++;
  1134. return (unsigned long)cl;
  1135. }
  1136. static void
  1137. hfsc_put_class(struct Qdisc *sch, unsigned long arg)
  1138. {
  1139. struct hfsc_class *cl = (struct hfsc_class *)arg;
  1140. if (--cl->refcnt == 0)
  1141. hfsc_destroy_class(sch, cl);
  1142. }
  1143. static unsigned long
  1144. hfsc_bind_tcf(struct Qdisc *sch, unsigned long parent, u32 classid)
  1145. {
  1146. struct hfsc_class *p = (struct hfsc_class *)parent;
  1147. struct hfsc_class *cl = hfsc_find_class(classid, sch);
  1148. if (cl != NULL) {
  1149. if (p != NULL && p->level <= cl->level)
  1150. return 0;
  1151. cl->filter_cnt++;
  1152. }
  1153. return (unsigned long)cl;
  1154. }
  1155. static void
  1156. hfsc_unbind_tcf(struct Qdisc *sch, unsigned long arg)
  1157. {
  1158. struct hfsc_class *cl = (struct hfsc_class *)arg;
  1159. cl->filter_cnt--;
  1160. }
  1161. static struct tcf_proto **
  1162. hfsc_tcf_chain(struct Qdisc *sch, unsigned long arg)
  1163. {
  1164. struct hfsc_sched *q = qdisc_priv(sch);
  1165. struct hfsc_class *cl = (struct hfsc_class *)arg;
  1166. if (cl == NULL)
  1167. cl = &q->root;
  1168. return &cl->filter_list;
  1169. }
  1170. static int
  1171. hfsc_dump_sc(struct sk_buff *skb, int attr, struct internal_sc *sc)
  1172. {
  1173. struct tc_service_curve tsc;
  1174. tsc.m1 = sm2m(sc->sm1);
  1175. tsc.d = dx2d(sc->dx);
  1176. tsc.m2 = sm2m(sc->sm2);
  1177. RTA_PUT(skb, attr, sizeof(tsc), &tsc);
  1178. return skb->len;
  1179. rtattr_failure:
  1180. return -1;
  1181. }
  1182. static inline int
  1183. hfsc_dump_curves(struct sk_buff *skb, struct hfsc_class *cl)
  1184. {
  1185. if ((cl->cl_flags & HFSC_RSC) &&
  1186. (hfsc_dump_sc(skb, TCA_HFSC_RSC, &cl->cl_rsc) < 0))
  1187. goto rtattr_failure;
  1188. if ((cl->cl_flags & HFSC_FSC) &&
  1189. (hfsc_dump_sc(skb, TCA_HFSC_FSC, &cl->cl_fsc) < 0))
  1190. goto rtattr_failure;
  1191. if ((cl->cl_flags & HFSC_USC) &&
  1192. (hfsc_dump_sc(skb, TCA_HFSC_USC, &cl->cl_usc) < 0))
  1193. goto rtattr_failure;
  1194. return skb->len;
  1195. rtattr_failure:
  1196. return -1;
  1197. }
  1198. static int
  1199. hfsc_dump_class(struct Qdisc *sch, unsigned long arg, struct sk_buff *skb,
  1200. struct tcmsg *tcm)
  1201. {
  1202. struct hfsc_class *cl = (struct hfsc_class *)arg;
  1203. unsigned char *b = skb->tail;
  1204. struct rtattr *rta = (struct rtattr *)b;
  1205. tcm->tcm_parent = cl->cl_parent ? cl->cl_parent->classid : TC_H_ROOT;
  1206. tcm->tcm_handle = cl->classid;
  1207. if (cl->level == 0)
  1208. tcm->tcm_info = cl->qdisc->handle;
  1209. RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
  1210. if (hfsc_dump_curves(skb, cl) < 0)
  1211. goto rtattr_failure;
  1212. rta->rta_len = skb->tail - b;
  1213. return skb->len;
  1214. rtattr_failure:
  1215. skb_trim(skb, b - skb->data);
  1216. return -1;
  1217. }
  1218. static int
  1219. hfsc_dump_class_stats(struct Qdisc *sch, unsigned long arg,
  1220. struct gnet_dump *d)
  1221. {
  1222. struct hfsc_class *cl = (struct hfsc_class *)arg;
  1223. struct tc_hfsc_stats xstats;
  1224. cl->qstats.qlen = cl->qdisc->q.qlen;
  1225. xstats.level = cl->level;
  1226. xstats.period = cl->cl_vtperiod;
  1227. xstats.work = cl->cl_total;
  1228. xstats.rtwork = cl->cl_cumul;
  1229. if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
  1230. #ifdef CONFIG_NET_ESTIMATOR
  1231. gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
  1232. #endif
  1233. gnet_stats_copy_queue(d, &cl->qstats) < 0)
  1234. return -1;
  1235. return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
  1236. }
  1237. static void
  1238. hfsc_walk(struct Qdisc *sch, struct qdisc_walker *arg)
  1239. {
  1240. struct hfsc_sched *q = qdisc_priv(sch);
  1241. struct hfsc_class *cl;
  1242. unsigned int i;
  1243. if (arg->stop)
  1244. return;
  1245. for (i = 0; i < HFSC_HSIZE; i++) {
  1246. list_for_each_entry(cl, &q->clhash[i], hlist) {
  1247. if (arg->count < arg->skip) {
  1248. arg->count++;
  1249. continue;
  1250. }
  1251. if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
  1252. arg->stop = 1;
  1253. return;
  1254. }
  1255. arg->count++;
  1256. }
  1257. }
  1258. }
  1259. static void
  1260. hfsc_watchdog(unsigned long arg)
  1261. {
  1262. struct Qdisc *sch = (struct Qdisc *)arg;
  1263. sch->flags &= ~TCQ_F_THROTTLED;
  1264. netif_schedule(sch->dev);
  1265. }
  1266. static void
  1267. hfsc_schedule_watchdog(struct Qdisc *sch, u64 cur_time)
  1268. {
  1269. struct hfsc_sched *q = qdisc_priv(sch);
  1270. struct hfsc_class *cl;
  1271. u64 next_time = 0;
  1272. long delay;
  1273. if ((cl = eltree_get_minel(q)) != NULL)
  1274. next_time = cl->cl_e;
  1275. if (q->root.cl_cfmin != 0) {
  1276. if (next_time == 0 || next_time > q->root.cl_cfmin)
  1277. next_time = q->root.cl_cfmin;
  1278. }
  1279. WARN_ON(next_time == 0);
  1280. delay = next_time - cur_time;
  1281. delay = PSCHED_US2JIFFIE(delay);
  1282. sch->flags |= TCQ_F_THROTTLED;
  1283. mod_timer(&q->wd_timer, jiffies + delay);
  1284. }
  1285. static int
  1286. hfsc_init_qdisc(struct Qdisc *sch, struct rtattr *opt)
  1287. {
  1288. struct hfsc_sched *q = qdisc_priv(sch);
  1289. struct tc_hfsc_qopt *qopt;
  1290. unsigned int i;
  1291. if (opt == NULL || RTA_PAYLOAD(opt) < sizeof(*qopt))
  1292. return -EINVAL;
  1293. qopt = RTA_DATA(opt);
  1294. sch->stats_lock = &sch->dev->queue_lock;
  1295. q->defcls = qopt->defcls;
  1296. for (i = 0; i < HFSC_HSIZE; i++)
  1297. INIT_LIST_HEAD(&q->clhash[i]);
  1298. q->eligible = RB_ROOT;
  1299. INIT_LIST_HEAD(&q->droplist);
  1300. skb_queue_head_init(&q->requeue);
  1301. q->root.refcnt = 1;
  1302. q->root.classid = sch->handle;
  1303. q->root.sched = q;
  1304. q->root.qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
  1305. sch->handle);
  1306. if (q->root.qdisc == NULL)
  1307. q->root.qdisc = &noop_qdisc;
  1308. q->root.stats_lock = &sch->dev->queue_lock;
  1309. INIT_LIST_HEAD(&q->root.children);
  1310. q->root.vt_tree = RB_ROOT;
  1311. q->root.cf_tree = RB_ROOT;
  1312. list_add(&q->root.hlist, &q->clhash[hfsc_hash(q->root.classid)]);
  1313. init_timer(&q->wd_timer);
  1314. q->wd_timer.function = hfsc_watchdog;
  1315. q->wd_timer.data = (unsigned long)sch;
  1316. return 0;
  1317. }
  1318. static int
  1319. hfsc_change_qdisc(struct Qdisc *sch, struct rtattr *opt)
  1320. {
  1321. struct hfsc_sched *q = qdisc_priv(sch);
  1322. struct tc_hfsc_qopt *qopt;
  1323. if (opt == NULL || RTA_PAYLOAD(opt) < sizeof(*qopt))
  1324. return -EINVAL;
  1325. qopt = RTA_DATA(opt);
  1326. sch_tree_lock(sch);
  1327. q->defcls = qopt->defcls;
  1328. sch_tree_unlock(sch);
  1329. return 0;
  1330. }
  1331. static void
  1332. hfsc_reset_class(struct hfsc_class *cl)
  1333. {
  1334. cl->cl_total = 0;
  1335. cl->cl_cumul = 0;
  1336. cl->cl_d = 0;
  1337. cl->cl_e = 0;
  1338. cl->cl_vt = 0;
  1339. cl->cl_vtadj = 0;
  1340. cl->cl_vtoff = 0;
  1341. cl->cl_cvtmin = 0;
  1342. cl->cl_cvtmax = 0;
  1343. cl->cl_cvtoff = 0;
  1344. cl->cl_pcvtoff = 0;
  1345. cl->cl_vtperiod = 0;
  1346. cl->cl_parentperiod = 0;
  1347. cl->cl_f = 0;
  1348. cl->cl_myf = 0;
  1349. cl->cl_myfadj = 0;
  1350. cl->cl_cfmin = 0;
  1351. cl->cl_nactive = 0;
  1352. cl->vt_tree = RB_ROOT;
  1353. cl->cf_tree = RB_ROOT;
  1354. qdisc_reset(cl->qdisc);
  1355. if (cl->cl_flags & HFSC_RSC)
  1356. rtsc_init(&cl->cl_deadline, &cl->cl_rsc, 0, 0);
  1357. if (cl->cl_flags & HFSC_FSC)
  1358. rtsc_init(&cl->cl_virtual, &cl->cl_fsc, 0, 0);
  1359. if (cl->cl_flags & HFSC_USC)
  1360. rtsc_init(&cl->cl_ulimit, &cl->cl_usc, 0, 0);
  1361. }
  1362. static void
  1363. hfsc_reset_qdisc(struct Qdisc *sch)
  1364. {
  1365. struct hfsc_sched *q = qdisc_priv(sch);
  1366. struct hfsc_class *cl;
  1367. unsigned int i;
  1368. for (i = 0; i < HFSC_HSIZE; i++) {
  1369. list_for_each_entry(cl, &q->clhash[i], hlist)
  1370. hfsc_reset_class(cl);
  1371. }
  1372. __skb_queue_purge(&q->requeue);
  1373. q->eligible = RB_ROOT;
  1374. INIT_LIST_HEAD(&q->droplist);
  1375. del_timer(&q->wd_timer);
  1376. sch->flags &= ~TCQ_F_THROTTLED;
  1377. sch->q.qlen = 0;
  1378. }
  1379. static void
  1380. hfsc_destroy_qdisc(struct Qdisc *sch)
  1381. {
  1382. struct hfsc_sched *q = qdisc_priv(sch);
  1383. struct hfsc_class *cl, *next;
  1384. unsigned int i;
  1385. for (i = 0; i < HFSC_HSIZE; i++) {
  1386. list_for_each_entry_safe(cl, next, &q->clhash[i], hlist)
  1387. hfsc_destroy_class(sch, cl);
  1388. }
  1389. __skb_queue_purge(&q->requeue);
  1390. del_timer(&q->wd_timer);
  1391. }
  1392. static int
  1393. hfsc_dump_qdisc(struct Qdisc *sch, struct sk_buff *skb)
  1394. {
  1395. struct hfsc_sched *q = qdisc_priv(sch);
  1396. unsigned char *b = skb->tail;
  1397. struct tc_hfsc_qopt qopt;
  1398. qopt.defcls = q->defcls;
  1399. RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
  1400. return skb->len;
  1401. rtattr_failure:
  1402. skb_trim(skb, b - skb->data);
  1403. return -1;
  1404. }
  1405. static int
  1406. hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
  1407. {
  1408. struct hfsc_class *cl;
  1409. unsigned int len;
  1410. int err;
  1411. cl = hfsc_classify(skb, sch, &err);
  1412. if (cl == NULL) {
  1413. if (err == NET_XMIT_BYPASS)
  1414. sch->qstats.drops++;
  1415. kfree_skb(skb);
  1416. return err;
  1417. }
  1418. len = skb->len;
  1419. err = cl->qdisc->enqueue(skb, cl->qdisc);
  1420. if (unlikely(err != NET_XMIT_SUCCESS)) {
  1421. cl->qstats.drops++;
  1422. sch->qstats.drops++;
  1423. return err;
  1424. }
  1425. if (cl->qdisc->q.qlen == 1)
  1426. set_active(cl, len);
  1427. cl->bstats.packets++;
  1428. cl->bstats.bytes += len;
  1429. sch->bstats.packets++;
  1430. sch->bstats.bytes += len;
  1431. sch->q.qlen++;
  1432. return NET_XMIT_SUCCESS;
  1433. }
  1434. static struct sk_buff *
  1435. hfsc_dequeue(struct Qdisc *sch)
  1436. {
  1437. struct hfsc_sched *q = qdisc_priv(sch);
  1438. struct hfsc_class *cl;
  1439. struct sk_buff *skb;
  1440. u64 cur_time;
  1441. unsigned int next_len;
  1442. int realtime = 0;
  1443. if (sch->q.qlen == 0)
  1444. return NULL;
  1445. if ((skb = __skb_dequeue(&q->requeue)))
  1446. goto out;
  1447. PSCHED_GET_TIME(cur_time);
  1448. /*
  1449. * if there are eligible classes, use real-time criteria.
  1450. * find the class with the minimum deadline among
  1451. * the eligible classes.
  1452. */
  1453. if ((cl = eltree_get_mindl(q, cur_time)) != NULL) {
  1454. realtime = 1;
  1455. } else {
  1456. /*
  1457. * use link-sharing criteria
  1458. * get the class with the minimum vt in the hierarchy
  1459. */
  1460. cl = vttree_get_minvt(&q->root, cur_time);
  1461. if (cl == NULL) {
  1462. sch->qstats.overlimits++;
  1463. hfsc_schedule_watchdog(sch, cur_time);
  1464. return NULL;
  1465. }
  1466. }
  1467. skb = cl->qdisc->dequeue(cl->qdisc);
  1468. if (skb == NULL) {
  1469. if (net_ratelimit())
  1470. printk("HFSC: Non-work-conserving qdisc ?\n");
  1471. return NULL;
  1472. }
  1473. update_vf(cl, skb->len, cur_time);
  1474. if (realtime)
  1475. cl->cl_cumul += skb->len;
  1476. if (cl->qdisc->q.qlen != 0) {
  1477. if (cl->cl_flags & HFSC_RSC) {
  1478. /* update ed */
  1479. next_len = qdisc_peek_len(cl->qdisc);
  1480. if (realtime)
  1481. update_ed(cl, next_len);
  1482. else
  1483. update_d(cl, next_len);
  1484. }
  1485. } else {
  1486. /* the class becomes passive */
  1487. set_passive(cl);
  1488. }
  1489. out:
  1490. sch->flags &= ~TCQ_F_THROTTLED;
  1491. sch->q.qlen--;
  1492. return skb;
  1493. }
  1494. static int
  1495. hfsc_requeue(struct sk_buff *skb, struct Qdisc *sch)
  1496. {
  1497. struct hfsc_sched *q = qdisc_priv(sch);
  1498. __skb_queue_head(&q->requeue, skb);
  1499. sch->q.qlen++;
  1500. sch->qstats.requeues++;
  1501. return NET_XMIT_SUCCESS;
  1502. }
  1503. static unsigned int
  1504. hfsc_drop(struct Qdisc *sch)
  1505. {
  1506. struct hfsc_sched *q = qdisc_priv(sch);
  1507. struct hfsc_class *cl;
  1508. unsigned int len;
  1509. list_for_each_entry(cl, &q->droplist, dlist) {
  1510. if (cl->qdisc->ops->drop != NULL &&
  1511. (len = cl->qdisc->ops->drop(cl->qdisc)) > 0) {
  1512. if (cl->qdisc->q.qlen == 0) {
  1513. update_vf(cl, 0, 0);
  1514. set_passive(cl);
  1515. } else {
  1516. list_move_tail(&cl->dlist, &q->droplist);
  1517. }
  1518. cl->qstats.drops++;
  1519. sch->qstats.drops++;
  1520. sch->q.qlen--;
  1521. return len;
  1522. }
  1523. }
  1524. return 0;
  1525. }
  1526. static struct Qdisc_class_ops hfsc_class_ops = {
  1527. .change = hfsc_change_class,
  1528. .delete = hfsc_delete_class,
  1529. .graft = hfsc_graft_class,
  1530. .leaf = hfsc_class_leaf,
  1531. .qlen_notify = hfsc_qlen_notify,
  1532. .get = hfsc_get_class,
  1533. .put = hfsc_put_class,
  1534. .bind_tcf = hfsc_bind_tcf,
  1535. .unbind_tcf = hfsc_unbind_tcf,
  1536. .tcf_chain = hfsc_tcf_chain,
  1537. .dump = hfsc_dump_class,
  1538. .dump_stats = hfsc_dump_class_stats,
  1539. .walk = hfsc_walk
  1540. };
  1541. static struct Qdisc_ops hfsc_qdisc_ops = {
  1542. .id = "hfsc",
  1543. .init = hfsc_init_qdisc,
  1544. .change = hfsc_change_qdisc,
  1545. .reset = hfsc_reset_qdisc,
  1546. .destroy = hfsc_destroy_qdisc,
  1547. .dump = hfsc_dump_qdisc,
  1548. .enqueue = hfsc_enqueue,
  1549. .dequeue = hfsc_dequeue,
  1550. .requeue = hfsc_requeue,
  1551. .drop = hfsc_drop,
  1552. .cl_ops = &hfsc_class_ops,
  1553. .priv_size = sizeof(struct hfsc_sched),
  1554. .owner = THIS_MODULE
  1555. };
  1556. static int __init
  1557. hfsc_init(void)
  1558. {
  1559. return register_qdisc(&hfsc_qdisc_ops);
  1560. }
  1561. static void __exit
  1562. hfsc_cleanup(void)
  1563. {
  1564. unregister_qdisc(&hfsc_qdisc_ops);
  1565. }
  1566. MODULE_LICENSE("GPL");
  1567. module_init(hfsc_init);
  1568. module_exit(hfsc_cleanup);