sch_cake.c 79 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122
  1. // SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause
  2. /* COMMON Applications Kept Enhanced (CAKE) discipline
  3. *
  4. * Copyright (C) 2014-2018 Jonathan Morton <chromatix99@gmail.com>
  5. * Copyright (C) 2015-2018 Toke Høiland-Jørgensen <toke@toke.dk>
  6. * Copyright (C) 2014-2018 Dave Täht <dave.taht@gmail.com>
  7. * Copyright (C) 2015-2018 Sebastian Moeller <moeller0@gmx.de>
  8. * (C) 2015-2018 Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk>
  9. * Copyright (C) 2017-2018 Ryan Mounce <ryan@mounce.com.au>
  10. *
  11. * The CAKE Principles:
  12. * (or, how to have your cake and eat it too)
  13. *
  14. * This is a combination of several shaping, AQM and FQ techniques into one
  15. * easy-to-use package:
  16. *
  17. * - An overall bandwidth shaper, to move the bottleneck away from dumb CPE
  18. * equipment and bloated MACs. This operates in deficit mode (as in sch_fq),
  19. * eliminating the need for any sort of burst parameter (eg. token bucket
  20. * depth). Burst support is limited to that necessary to overcome scheduling
  21. * latency.
  22. *
  23. * - A Diffserv-aware priority queue, giving more priority to certain classes,
  24. * up to a specified fraction of bandwidth. Above that bandwidth threshold,
  25. * the priority is reduced to avoid starving other tins.
  26. *
  27. * - Each priority tin has a separate Flow Queue system, to isolate traffic
  28. * flows from each other. This prevents a burst on one flow from increasing
  29. * the delay to another. Flows are distributed to queues using a
  30. * set-associative hash function.
  31. *
  32. * - Each queue is actively managed by Cobalt, which is a combination of the
  33. * Codel and Blue AQM algorithms. This serves flows fairly, and signals
  34. * congestion early via ECN (if available) and/or packet drops, to keep
  35. * latency low. The codel parameters are auto-tuned based on the bandwidth
  36. * setting, as is necessary at low bandwidths.
  37. *
  38. * The configuration parameters are kept deliberately simple for ease of use.
  39. * Everything has sane defaults. Complete generality of configuration is *not*
  40. * a goal.
  41. *
  42. * The priority queue operates according to a weighted DRR scheme, combined with
  43. * a bandwidth tracker which reuses the shaper logic to detect which side of the
  44. * bandwidth sharing threshold the tin is operating. This determines whether a
  45. * priority-based weight (high) or a bandwidth-based weight (low) is used for
  46. * that tin in the current pass.
  47. *
  48. * This qdisc was inspired by Eric Dumazet's fq_codel code, which he kindly
  49. * granted us permission to leverage.
  50. */
  51. #include <linux/module.h>
  52. #include <linux/types.h>
  53. #include <linux/kernel.h>
  54. #include <linux/jiffies.h>
  55. #include <linux/string.h>
  56. #include <linux/in.h>
  57. #include <linux/errno.h>
  58. #include <linux/init.h>
  59. #include <linux/skbuff.h>
  60. #include <linux/jhash.h>
  61. #include <linux/slab.h>
  62. #include <linux/vmalloc.h>
  63. #include <linux/reciprocal_div.h>
  64. #include <net/netlink.h>
  65. #include <linux/if_vlan.h>
  66. #include <net/pkt_sched.h>
  67. #include <net/pkt_cls.h>
  68. #include <net/tcp.h>
  69. #include <net/flow_dissector.h>
  70. #if IS_ENABLED(CONFIG_NF_CONNTRACK)
  71. #include <net/netfilter/nf_conntrack_core.h>
  72. #endif
  73. #define CAKE_SET_WAYS (8)
  74. #define CAKE_MAX_TINS (8)
  75. #define CAKE_QUEUES (1024)
  76. #define CAKE_FLOW_MASK 63
  77. #define CAKE_FLOW_NAT_FLAG 64
  78. /* struct cobalt_params - contains codel and blue parameters
  79. * @interval: codel initial drop rate
  80. * @target: maximum persistent sojourn time & blue update rate
  81. * @mtu_time: serialisation delay of maximum-size packet
  82. * @p_inc: increment of blue drop probability (0.32 fxp)
  83. * @p_dec: decrement of blue drop probability (0.32 fxp)
  84. */
  85. struct cobalt_params {
  86. u64 interval;
  87. u64 target;
  88. u64 mtu_time;
  89. u32 p_inc;
  90. u32 p_dec;
  91. };
  92. /* struct cobalt_vars - contains codel and blue variables
  93. * @count: codel dropping frequency
  94. * @rec_inv_sqrt: reciprocal value of sqrt(count) >> 1
  95. * @drop_next: time to drop next packet, or when we dropped last
  96. * @blue_timer: Blue time to next drop
  97. * @p_drop: BLUE drop probability (0.32 fxp)
  98. * @dropping: set if in dropping state
  99. * @ecn_marked: set if marked
  100. */
  101. struct cobalt_vars {
  102. u32 count;
  103. u32 rec_inv_sqrt;
  104. ktime_t drop_next;
  105. ktime_t blue_timer;
  106. u32 p_drop;
  107. bool dropping;
  108. bool ecn_marked;
  109. };
  110. enum {
  111. CAKE_SET_NONE = 0,
  112. CAKE_SET_SPARSE,
  113. CAKE_SET_SPARSE_WAIT, /* counted in SPARSE, actually in BULK */
  114. CAKE_SET_BULK,
  115. CAKE_SET_DECAYING
  116. };
  117. struct cake_flow {
  118. /* this stuff is all needed per-flow at dequeue time */
  119. struct sk_buff *head;
  120. struct sk_buff *tail;
  121. struct list_head flowchain;
  122. s32 deficit;
  123. u32 dropped;
  124. struct cobalt_vars cvars;
  125. u16 srchost; /* index into cake_host table */
  126. u16 dsthost;
  127. u8 set;
  128. }; /* please try to keep this structure <= 64 bytes */
  129. struct cake_host {
  130. u32 srchost_tag;
  131. u32 dsthost_tag;
  132. u16 srchost_bulk_flow_count;
  133. u16 dsthost_bulk_flow_count;
  134. };
  135. struct cake_heap_entry {
  136. u16 t:3, b:10;
  137. };
  138. struct cake_tin_data {
  139. struct cake_flow flows[CAKE_QUEUES];
  140. u32 backlogs[CAKE_QUEUES];
  141. u32 tags[CAKE_QUEUES]; /* for set association */
  142. u16 overflow_idx[CAKE_QUEUES];
  143. struct cake_host hosts[CAKE_QUEUES]; /* for triple isolation */
  144. u16 flow_quantum;
  145. struct cobalt_params cparams;
  146. u32 drop_overlimit;
  147. u16 bulk_flow_count;
  148. u16 sparse_flow_count;
  149. u16 decaying_flow_count;
  150. u16 unresponsive_flow_count;
  151. u32 max_skblen;
  152. struct list_head new_flows;
  153. struct list_head old_flows;
  154. struct list_head decaying_flows;
  155. /* time_next = time_this + ((len * rate_ns) >> rate_shft) */
  156. ktime_t time_next_packet;
  157. u64 tin_rate_ns;
  158. u64 tin_rate_bps;
  159. u16 tin_rate_shft;
  160. u16 tin_quantum;
  161. s32 tin_deficit;
  162. u32 tin_backlog;
  163. u32 tin_dropped;
  164. u32 tin_ecn_mark;
  165. u32 packets;
  166. u64 bytes;
  167. u32 ack_drops;
  168. /* moving averages */
  169. u64 avge_delay;
  170. u64 peak_delay;
  171. u64 base_delay;
  172. /* hash function stats */
  173. u32 way_directs;
  174. u32 way_hits;
  175. u32 way_misses;
  176. u32 way_collisions;
  177. }; /* number of tins is small, so size of this struct doesn't matter much */
  178. struct cake_sched_data {
  179. struct tcf_proto __rcu *filter_list; /* optional external classifier */
  180. struct tcf_block *block;
  181. struct cake_tin_data *tins;
  182. struct cake_heap_entry overflow_heap[CAKE_QUEUES * CAKE_MAX_TINS];
  183. u16 overflow_timeout;
  184. u16 tin_cnt;
  185. u8 tin_mode;
  186. u8 flow_mode;
  187. u8 ack_filter;
  188. u8 atm_mode;
  189. u32 fwmark_mask;
  190. u16 fwmark_shft;
  191. /* time_next = time_this + ((len * rate_ns) >> rate_shft) */
  192. u16 rate_shft;
  193. ktime_t time_next_packet;
  194. ktime_t failsafe_next_packet;
  195. u64 rate_ns;
  196. u64 rate_bps;
  197. u16 rate_flags;
  198. s16 rate_overhead;
  199. u16 rate_mpu;
  200. u64 interval;
  201. u64 target;
  202. /* resource tracking */
  203. u32 buffer_used;
  204. u32 buffer_max_used;
  205. u32 buffer_limit;
  206. u32 buffer_config_limit;
  207. /* indices for dequeue */
  208. u16 cur_tin;
  209. u16 cur_flow;
  210. struct qdisc_watchdog watchdog;
  211. const u8 *tin_index;
  212. const u8 *tin_order;
  213. /* bandwidth capacity estimate */
  214. ktime_t last_packet_time;
  215. ktime_t avg_window_begin;
  216. u64 avg_packet_interval;
  217. u64 avg_window_bytes;
  218. u64 avg_peak_bandwidth;
  219. ktime_t last_reconfig_time;
  220. /* packet length stats */
  221. u32 avg_netoff;
  222. u16 max_netlen;
  223. u16 max_adjlen;
  224. u16 min_netlen;
  225. u16 min_adjlen;
  226. };
  227. enum {
  228. CAKE_FLAG_OVERHEAD = BIT(0),
  229. CAKE_FLAG_AUTORATE_INGRESS = BIT(1),
  230. CAKE_FLAG_INGRESS = BIT(2),
  231. CAKE_FLAG_WASH = BIT(3),
  232. CAKE_FLAG_SPLIT_GSO = BIT(4)
  233. };
  234. /* COBALT operates the Codel and BLUE algorithms in parallel, in order to
  235. * obtain the best features of each. Codel is excellent on flows which
  236. * respond to congestion signals in a TCP-like way. BLUE is more effective on
  237. * unresponsive flows.
  238. */
  239. struct cobalt_skb_cb {
  240. ktime_t enqueue_time;
  241. u32 adjusted_len;
  242. };
  243. static u64 us_to_ns(u64 us)
  244. {
  245. return us * NSEC_PER_USEC;
  246. }
  247. static struct cobalt_skb_cb *get_cobalt_cb(const struct sk_buff *skb)
  248. {
  249. qdisc_cb_private_validate(skb, sizeof(struct cobalt_skb_cb));
  250. return (struct cobalt_skb_cb *)qdisc_skb_cb(skb)->data;
  251. }
  252. static ktime_t cobalt_get_enqueue_time(const struct sk_buff *skb)
  253. {
  254. return get_cobalt_cb(skb)->enqueue_time;
  255. }
  256. static void cobalt_set_enqueue_time(struct sk_buff *skb,
  257. ktime_t now)
  258. {
  259. get_cobalt_cb(skb)->enqueue_time = now;
  260. }
  261. static u16 quantum_div[CAKE_QUEUES + 1] = {0};
  262. /* Diffserv lookup tables */
  263. static const u8 precedence[] = {
  264. 0, 0, 0, 0, 0, 0, 0, 0,
  265. 1, 1, 1, 1, 1, 1, 1, 1,
  266. 2, 2, 2, 2, 2, 2, 2, 2,
  267. 3, 3, 3, 3, 3, 3, 3, 3,
  268. 4, 4, 4, 4, 4, 4, 4, 4,
  269. 5, 5, 5, 5, 5, 5, 5, 5,
  270. 6, 6, 6, 6, 6, 6, 6, 6,
  271. 7, 7, 7, 7, 7, 7, 7, 7,
  272. };
  273. static const u8 diffserv8[] = {
  274. 2, 0, 1, 2, 4, 2, 2, 2,
  275. 1, 2, 1, 2, 1, 2, 1, 2,
  276. 5, 2, 4, 2, 4, 2, 4, 2,
  277. 3, 2, 3, 2, 3, 2, 3, 2,
  278. 6, 2, 3, 2, 3, 2, 3, 2,
  279. 6, 2, 2, 2, 6, 2, 6, 2,
  280. 7, 2, 2, 2, 2, 2, 2, 2,
  281. 7, 2, 2, 2, 2, 2, 2, 2,
  282. };
  283. static const u8 diffserv4[] = {
  284. 0, 1, 0, 0, 2, 0, 0, 0,
  285. 1, 0, 0, 0, 0, 0, 0, 0,
  286. 2, 0, 2, 0, 2, 0, 2, 0,
  287. 2, 0, 2, 0, 2, 0, 2, 0,
  288. 3, 0, 2, 0, 2, 0, 2, 0,
  289. 3, 0, 0, 0, 3, 0, 3, 0,
  290. 3, 0, 0, 0, 0, 0, 0, 0,
  291. 3, 0, 0, 0, 0, 0, 0, 0,
  292. };
  293. static const u8 diffserv3[] = {
  294. 0, 1, 0, 0, 2, 0, 0, 0,
  295. 1, 0, 0, 0, 0, 0, 0, 0,
  296. 0, 0, 0, 0, 0, 0, 0, 0,
  297. 0, 0, 0, 0, 0, 0, 0, 0,
  298. 0, 0, 0, 0, 0, 0, 0, 0,
  299. 0, 0, 0, 0, 2, 0, 2, 0,
  300. 2, 0, 0, 0, 0, 0, 0, 0,
  301. 2, 0, 0, 0, 0, 0, 0, 0,
  302. };
  303. static const u8 besteffort[] = {
  304. 0, 0, 0, 0, 0, 0, 0, 0,
  305. 0, 0, 0, 0, 0, 0, 0, 0,
  306. 0, 0, 0, 0, 0, 0, 0, 0,
  307. 0, 0, 0, 0, 0, 0, 0, 0,
  308. 0, 0, 0, 0, 0, 0, 0, 0,
  309. 0, 0, 0, 0, 0, 0, 0, 0,
  310. 0, 0, 0, 0, 0, 0, 0, 0,
  311. 0, 0, 0, 0, 0, 0, 0, 0,
  312. };
  313. /* tin priority order for stats dumping */
  314. static const u8 normal_order[] = {0, 1, 2, 3, 4, 5, 6, 7};
  315. static const u8 bulk_order[] = {1, 0, 2, 3};
  316. #define REC_INV_SQRT_CACHE (16)
  317. static u32 cobalt_rec_inv_sqrt_cache[REC_INV_SQRT_CACHE] = {0};
  318. /* http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
  319. * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
  320. *
  321. * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32
  322. */
  323. static void cobalt_newton_step(struct cobalt_vars *vars)
  324. {
  325. u32 invsqrt, invsqrt2;
  326. u64 val;
  327. invsqrt = vars->rec_inv_sqrt;
  328. invsqrt2 = ((u64)invsqrt * invsqrt) >> 32;
  329. val = (3LL << 32) - ((u64)vars->count * invsqrt2);
  330. val >>= 2; /* avoid overflow in following multiply */
  331. val = (val * invsqrt) >> (32 - 2 + 1);
  332. vars->rec_inv_sqrt = val;
  333. }
  334. static void cobalt_invsqrt(struct cobalt_vars *vars)
  335. {
  336. if (vars->count < REC_INV_SQRT_CACHE)
  337. vars->rec_inv_sqrt = cobalt_rec_inv_sqrt_cache[vars->count];
  338. else
  339. cobalt_newton_step(vars);
  340. }
  341. /* There is a big difference in timing between the accurate values placed in
  342. * the cache and the approximations given by a single Newton step for small
  343. * count values, particularly when stepping from count 1 to 2 or vice versa.
  344. * Above 16, a single Newton step gives sufficient accuracy in either
  345. * direction, given the precision stored.
  346. *
  347. * The magnitude of the error when stepping up to count 2 is such as to give
  348. * the value that *should* have been produced at count 4.
  349. */
  350. static void cobalt_cache_init(void)
  351. {
  352. struct cobalt_vars v;
  353. memset(&v, 0, sizeof(v));
  354. v.rec_inv_sqrt = ~0U;
  355. cobalt_rec_inv_sqrt_cache[0] = v.rec_inv_sqrt;
  356. for (v.count = 1; v.count < REC_INV_SQRT_CACHE; v.count++) {
  357. cobalt_newton_step(&v);
  358. cobalt_newton_step(&v);
  359. cobalt_newton_step(&v);
  360. cobalt_newton_step(&v);
  361. cobalt_rec_inv_sqrt_cache[v.count] = v.rec_inv_sqrt;
  362. }
  363. }
  364. static void cobalt_vars_init(struct cobalt_vars *vars)
  365. {
  366. memset(vars, 0, sizeof(*vars));
  367. if (!cobalt_rec_inv_sqrt_cache[0]) {
  368. cobalt_cache_init();
  369. cobalt_rec_inv_sqrt_cache[0] = ~0;
  370. }
  371. }
  372. /* CoDel control_law is t + interval/sqrt(count)
  373. * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to avoid
  374. * both sqrt() and divide operation.
  375. */
  376. static ktime_t cobalt_control(ktime_t t,
  377. u64 interval,
  378. u32 rec_inv_sqrt)
  379. {
  380. return ktime_add_ns(t, reciprocal_scale(interval,
  381. rec_inv_sqrt));
  382. }
  383. /* Call this when a packet had to be dropped due to queue overflow. Returns
  384. * true if the BLUE state was quiescent before but active after this call.
  385. */
  386. static bool cobalt_queue_full(struct cobalt_vars *vars,
  387. struct cobalt_params *p,
  388. ktime_t now)
  389. {
  390. bool up = false;
  391. if (ktime_to_ns(ktime_sub(now, vars->blue_timer)) > p->target) {
  392. up = !vars->p_drop;
  393. vars->p_drop += p->p_inc;
  394. if (vars->p_drop < p->p_inc)
  395. vars->p_drop = ~0;
  396. vars->blue_timer = now;
  397. }
  398. vars->dropping = true;
  399. vars->drop_next = now;
  400. if (!vars->count)
  401. vars->count = 1;
  402. return up;
  403. }
  404. /* Call this when the queue was serviced but turned out to be empty. Returns
  405. * true if the BLUE state was active before but quiescent after this call.
  406. */
  407. static bool cobalt_queue_empty(struct cobalt_vars *vars,
  408. struct cobalt_params *p,
  409. ktime_t now)
  410. {
  411. bool down = false;
  412. if (vars->p_drop &&
  413. ktime_to_ns(ktime_sub(now, vars->blue_timer)) > p->target) {
  414. if (vars->p_drop < p->p_dec)
  415. vars->p_drop = 0;
  416. else
  417. vars->p_drop -= p->p_dec;
  418. vars->blue_timer = now;
  419. down = !vars->p_drop;
  420. }
  421. vars->dropping = false;
  422. if (vars->count && ktime_to_ns(ktime_sub(now, vars->drop_next)) >= 0) {
  423. vars->count--;
  424. cobalt_invsqrt(vars);
  425. vars->drop_next = cobalt_control(vars->drop_next,
  426. p->interval,
  427. vars->rec_inv_sqrt);
  428. }
  429. return down;
  430. }
  431. /* Call this with a freshly dequeued packet for possible congestion marking.
  432. * Returns true as an instruction to drop the packet, false for delivery.
  433. */
  434. static bool cobalt_should_drop(struct cobalt_vars *vars,
  435. struct cobalt_params *p,
  436. ktime_t now,
  437. struct sk_buff *skb,
  438. u32 bulk_flows)
  439. {
  440. bool next_due, over_target, drop = false;
  441. ktime_t schedule;
  442. u64 sojourn;
  443. /* The 'schedule' variable records, in its sign, whether 'now' is before or
  444. * after 'drop_next'. This allows 'drop_next' to be updated before the next
  445. * scheduling decision is actually branched, without destroying that
  446. * information. Similarly, the first 'schedule' value calculated is preserved
  447. * in the boolean 'next_due'.
  448. *
  449. * As for 'drop_next', we take advantage of the fact that 'interval' is both
  450. * the delay between first exceeding 'target' and the first signalling event,
  451. * *and* the scaling factor for the signalling frequency. It's therefore very
  452. * natural to use a single mechanism for both purposes, and eliminates a
  453. * significant amount of reference Codel's spaghetti code. To help with this,
  454. * both the '0' and '1' entries in the invsqrt cache are 0xFFFFFFFF, as close
  455. * as possible to 1.0 in fixed-point.
  456. */
  457. sojourn = ktime_to_ns(ktime_sub(now, cobalt_get_enqueue_time(skb)));
  458. schedule = ktime_sub(now, vars->drop_next);
  459. over_target = sojourn > p->target &&
  460. sojourn > p->mtu_time * bulk_flows * 2 &&
  461. sojourn > p->mtu_time * 4;
  462. next_due = vars->count && ktime_to_ns(schedule) >= 0;
  463. vars->ecn_marked = false;
  464. if (over_target) {
  465. if (!vars->dropping) {
  466. vars->dropping = true;
  467. vars->drop_next = cobalt_control(now,
  468. p->interval,
  469. vars->rec_inv_sqrt);
  470. }
  471. if (!vars->count)
  472. vars->count = 1;
  473. } else if (vars->dropping) {
  474. vars->dropping = false;
  475. }
  476. if (next_due && vars->dropping) {
  477. /* Use ECN mark if possible, otherwise drop */
  478. drop = !(vars->ecn_marked = INET_ECN_set_ce(skb));
  479. vars->count++;
  480. if (!vars->count)
  481. vars->count--;
  482. cobalt_invsqrt(vars);
  483. vars->drop_next = cobalt_control(vars->drop_next,
  484. p->interval,
  485. vars->rec_inv_sqrt);
  486. schedule = ktime_sub(now, vars->drop_next);
  487. } else {
  488. while (next_due) {
  489. vars->count--;
  490. cobalt_invsqrt(vars);
  491. vars->drop_next = cobalt_control(vars->drop_next,
  492. p->interval,
  493. vars->rec_inv_sqrt);
  494. schedule = ktime_sub(now, vars->drop_next);
  495. next_due = vars->count && ktime_to_ns(schedule) >= 0;
  496. }
  497. }
  498. /* Simple BLUE implementation. Lack of ECN is deliberate. */
  499. if (vars->p_drop)
  500. drop |= (prandom_u32() < vars->p_drop);
  501. /* Overload the drop_next field as an activity timeout */
  502. if (!vars->count)
  503. vars->drop_next = ktime_add_ns(now, p->interval);
  504. else if (ktime_to_ns(schedule) > 0 && !drop)
  505. vars->drop_next = now;
  506. return drop;
  507. }
  508. static bool cake_update_flowkeys(struct flow_keys *keys,
  509. const struct sk_buff *skb)
  510. {
  511. #if IS_ENABLED(CONFIG_NF_CONNTRACK)
  512. struct nf_conntrack_tuple tuple = {};
  513. bool rev = !skb->_nfct, upd = false;
  514. __be32 ip;
  515. if (skb_protocol(skb, true) != htons(ETH_P_IP))
  516. return false;
  517. if (!nf_ct_get_tuple_skb(&tuple, skb))
  518. return false;
  519. ip = rev ? tuple.dst.u3.ip : tuple.src.u3.ip;
  520. if (ip != keys->addrs.v4addrs.src) {
  521. keys->addrs.v4addrs.src = ip;
  522. upd = true;
  523. }
  524. ip = rev ? tuple.src.u3.ip : tuple.dst.u3.ip;
  525. if (ip != keys->addrs.v4addrs.dst) {
  526. keys->addrs.v4addrs.dst = ip;
  527. upd = true;
  528. }
  529. if (keys->ports.ports) {
  530. __be16 port;
  531. port = rev ? tuple.dst.u.all : tuple.src.u.all;
  532. if (port != keys->ports.src) {
  533. keys->ports.src = port;
  534. upd = true;
  535. }
  536. port = rev ? tuple.src.u.all : tuple.dst.u.all;
  537. if (port != keys->ports.dst) {
  538. port = keys->ports.dst;
  539. upd = true;
  540. }
  541. }
  542. return upd;
  543. #else
  544. return false;
  545. #endif
  546. }
  547. /* Cake has several subtle multiple bit settings. In these cases you
  548. * would be matching triple isolate mode as well.
  549. */
  550. static bool cake_dsrc(int flow_mode)
  551. {
  552. return (flow_mode & CAKE_FLOW_DUAL_SRC) == CAKE_FLOW_DUAL_SRC;
  553. }
  554. static bool cake_ddst(int flow_mode)
  555. {
  556. return (flow_mode & CAKE_FLOW_DUAL_DST) == CAKE_FLOW_DUAL_DST;
  557. }
  558. static u32 cake_hash(struct cake_tin_data *q, const struct sk_buff *skb,
  559. int flow_mode, u16 flow_override, u16 host_override)
  560. {
  561. bool hash_flows = (!flow_override && !!(flow_mode & CAKE_FLOW_FLOWS));
  562. bool hash_hosts = (!host_override && !!(flow_mode & CAKE_FLOW_HOSTS));
  563. bool nat_enabled = !!(flow_mode & CAKE_FLOW_NAT_FLAG);
  564. u32 flow_hash = 0, srchost_hash = 0, dsthost_hash = 0;
  565. u16 reduced_hash, srchost_idx, dsthost_idx;
  566. struct flow_keys keys, host_keys;
  567. bool use_skbhash = skb->l4_hash;
  568. if (unlikely(flow_mode == CAKE_FLOW_NONE))
  569. return 0;
  570. /* If both overrides are set, or we can use the SKB hash and nat mode is
  571. * disabled, we can skip packet dissection entirely. If nat mode is
  572. * enabled there's another check below after doing the conntrack lookup.
  573. */
  574. if ((!hash_flows || (use_skbhash && !nat_enabled)) && !hash_hosts)
  575. goto skip_hash;
  576. skb_flow_dissect_flow_keys(skb, &keys,
  577. FLOW_DISSECTOR_F_STOP_AT_FLOW_LABEL);
  578. /* Don't use the SKB hash if we change the lookup keys from conntrack */
  579. if (nat_enabled && cake_update_flowkeys(&keys, skb))
  580. use_skbhash = false;
  581. /* If we can still use the SKB hash and don't need the host hash, we can
  582. * skip the rest of the hashing procedure
  583. */
  584. if (use_skbhash && !hash_hosts)
  585. goto skip_hash;
  586. /* flow_hash_from_keys() sorts the addresses by value, so we have
  587. * to preserve their order in a separate data structure to treat
  588. * src and dst host addresses as independently selectable.
  589. */
  590. host_keys = keys;
  591. host_keys.ports.ports = 0;
  592. host_keys.basic.ip_proto = 0;
  593. host_keys.keyid.keyid = 0;
  594. host_keys.tags.flow_label = 0;
  595. switch (host_keys.control.addr_type) {
  596. case FLOW_DISSECTOR_KEY_IPV4_ADDRS:
  597. host_keys.addrs.v4addrs.src = 0;
  598. dsthost_hash = flow_hash_from_keys(&host_keys);
  599. host_keys.addrs.v4addrs.src = keys.addrs.v4addrs.src;
  600. host_keys.addrs.v4addrs.dst = 0;
  601. srchost_hash = flow_hash_from_keys(&host_keys);
  602. break;
  603. case FLOW_DISSECTOR_KEY_IPV6_ADDRS:
  604. memset(&host_keys.addrs.v6addrs.src, 0,
  605. sizeof(host_keys.addrs.v6addrs.src));
  606. dsthost_hash = flow_hash_from_keys(&host_keys);
  607. host_keys.addrs.v6addrs.src = keys.addrs.v6addrs.src;
  608. memset(&host_keys.addrs.v6addrs.dst, 0,
  609. sizeof(host_keys.addrs.v6addrs.dst));
  610. srchost_hash = flow_hash_from_keys(&host_keys);
  611. break;
  612. default:
  613. dsthost_hash = 0;
  614. srchost_hash = 0;
  615. }
  616. /* This *must* be after the above switch, since as a
  617. * side-effect it sorts the src and dst addresses.
  618. */
  619. if (hash_flows && !use_skbhash)
  620. flow_hash = flow_hash_from_keys(&keys);
  621. skip_hash:
  622. if (flow_override)
  623. flow_hash = flow_override - 1;
  624. else if (use_skbhash && (flow_mode & CAKE_FLOW_FLOWS))
  625. flow_hash = skb->hash;
  626. if (host_override) {
  627. dsthost_hash = host_override - 1;
  628. srchost_hash = host_override - 1;
  629. }
  630. if (!(flow_mode & CAKE_FLOW_FLOWS)) {
  631. if (flow_mode & CAKE_FLOW_SRC_IP)
  632. flow_hash ^= srchost_hash;
  633. if (flow_mode & CAKE_FLOW_DST_IP)
  634. flow_hash ^= dsthost_hash;
  635. }
  636. reduced_hash = flow_hash % CAKE_QUEUES;
  637. /* set-associative hashing */
  638. /* fast path if no hash collision (direct lookup succeeds) */
  639. if (likely(q->tags[reduced_hash] == flow_hash &&
  640. q->flows[reduced_hash].set)) {
  641. q->way_directs++;
  642. } else {
  643. u32 inner_hash = reduced_hash % CAKE_SET_WAYS;
  644. u32 outer_hash = reduced_hash - inner_hash;
  645. bool allocate_src = false;
  646. bool allocate_dst = false;
  647. u32 i, k;
  648. /* check if any active queue in the set is reserved for
  649. * this flow.
  650. */
  651. for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;
  652. i++, k = (k + 1) % CAKE_SET_WAYS) {
  653. if (q->tags[outer_hash + k] == flow_hash) {
  654. if (i)
  655. q->way_hits++;
  656. if (!q->flows[outer_hash + k].set) {
  657. /* need to increment host refcnts */
  658. allocate_src = cake_dsrc(flow_mode);
  659. allocate_dst = cake_ddst(flow_mode);
  660. }
  661. goto found;
  662. }
  663. }
  664. /* no queue is reserved for this flow, look for an
  665. * empty one.
  666. */
  667. for (i = 0; i < CAKE_SET_WAYS;
  668. i++, k = (k + 1) % CAKE_SET_WAYS) {
  669. if (!q->flows[outer_hash + k].set) {
  670. q->way_misses++;
  671. allocate_src = cake_dsrc(flow_mode);
  672. allocate_dst = cake_ddst(flow_mode);
  673. goto found;
  674. }
  675. }
  676. /* With no empty queues, default to the original
  677. * queue, accept the collision, update the host tags.
  678. */
  679. q->way_collisions++;
  680. if (q->flows[outer_hash + k].set == CAKE_SET_BULK) {
  681. q->hosts[q->flows[reduced_hash].srchost].srchost_bulk_flow_count--;
  682. q->hosts[q->flows[reduced_hash].dsthost].dsthost_bulk_flow_count--;
  683. }
  684. allocate_src = cake_dsrc(flow_mode);
  685. allocate_dst = cake_ddst(flow_mode);
  686. found:
  687. /* reserve queue for future packets in same flow */
  688. reduced_hash = outer_hash + k;
  689. q->tags[reduced_hash] = flow_hash;
  690. if (allocate_src) {
  691. srchost_idx = srchost_hash % CAKE_QUEUES;
  692. inner_hash = srchost_idx % CAKE_SET_WAYS;
  693. outer_hash = srchost_idx - inner_hash;
  694. for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;
  695. i++, k = (k + 1) % CAKE_SET_WAYS) {
  696. if (q->hosts[outer_hash + k].srchost_tag ==
  697. srchost_hash)
  698. goto found_src;
  699. }
  700. for (i = 0; i < CAKE_SET_WAYS;
  701. i++, k = (k + 1) % CAKE_SET_WAYS) {
  702. if (!q->hosts[outer_hash + k].srchost_bulk_flow_count)
  703. break;
  704. }
  705. q->hosts[outer_hash + k].srchost_tag = srchost_hash;
  706. found_src:
  707. srchost_idx = outer_hash + k;
  708. if (q->flows[reduced_hash].set == CAKE_SET_BULK)
  709. q->hosts[srchost_idx].srchost_bulk_flow_count++;
  710. q->flows[reduced_hash].srchost = srchost_idx;
  711. }
  712. if (allocate_dst) {
  713. dsthost_idx = dsthost_hash % CAKE_QUEUES;
  714. inner_hash = dsthost_idx % CAKE_SET_WAYS;
  715. outer_hash = dsthost_idx - inner_hash;
  716. for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;
  717. i++, k = (k + 1) % CAKE_SET_WAYS) {
  718. if (q->hosts[outer_hash + k].dsthost_tag ==
  719. dsthost_hash)
  720. goto found_dst;
  721. }
  722. for (i = 0; i < CAKE_SET_WAYS;
  723. i++, k = (k + 1) % CAKE_SET_WAYS) {
  724. if (!q->hosts[outer_hash + k].dsthost_bulk_flow_count)
  725. break;
  726. }
  727. q->hosts[outer_hash + k].dsthost_tag = dsthost_hash;
  728. found_dst:
  729. dsthost_idx = outer_hash + k;
  730. if (q->flows[reduced_hash].set == CAKE_SET_BULK)
  731. q->hosts[dsthost_idx].dsthost_bulk_flow_count++;
  732. q->flows[reduced_hash].dsthost = dsthost_idx;
  733. }
  734. }
  735. return reduced_hash;
  736. }
  737. /* helper functions : might be changed when/if skb use a standard list_head */
  738. /* remove one skb from head of slot queue */
  739. static struct sk_buff *dequeue_head(struct cake_flow *flow)
  740. {
  741. struct sk_buff *skb = flow->head;
  742. if (skb) {
  743. flow->head = skb->next;
  744. skb_mark_not_on_list(skb);
  745. }
  746. return skb;
  747. }
  748. /* add skb to flow queue (tail add) */
  749. static void flow_queue_add(struct cake_flow *flow, struct sk_buff *skb)
  750. {
  751. if (!flow->head)
  752. flow->head = skb;
  753. else
  754. flow->tail->next = skb;
  755. flow->tail = skb;
  756. skb->next = NULL;
  757. }
  758. static struct iphdr *cake_get_iphdr(const struct sk_buff *skb,
  759. struct ipv6hdr *buf)
  760. {
  761. unsigned int offset = skb_network_offset(skb);
  762. struct iphdr *iph;
  763. iph = skb_header_pointer(skb, offset, sizeof(struct iphdr), buf);
  764. if (!iph)
  765. return NULL;
  766. if (iph->version == 4 && iph->protocol == IPPROTO_IPV6)
  767. return skb_header_pointer(skb, offset + iph->ihl * 4,
  768. sizeof(struct ipv6hdr), buf);
  769. else if (iph->version == 4)
  770. return iph;
  771. else if (iph->version == 6)
  772. return skb_header_pointer(skb, offset, sizeof(struct ipv6hdr),
  773. buf);
  774. return NULL;
  775. }
  776. static struct tcphdr *cake_get_tcphdr(const struct sk_buff *skb,
  777. void *buf, unsigned int bufsize)
  778. {
  779. unsigned int offset = skb_network_offset(skb);
  780. const struct ipv6hdr *ipv6h;
  781. const struct tcphdr *tcph;
  782. const struct iphdr *iph;
  783. struct ipv6hdr _ipv6h;
  784. struct tcphdr _tcph;
  785. ipv6h = skb_header_pointer(skb, offset, sizeof(_ipv6h), &_ipv6h);
  786. if (!ipv6h)
  787. return NULL;
  788. if (ipv6h->version == 4) {
  789. iph = (struct iphdr *)ipv6h;
  790. offset += iph->ihl * 4;
  791. /* special-case 6in4 tunnelling, as that is a common way to get
  792. * v6 connectivity in the home
  793. */
  794. if (iph->protocol == IPPROTO_IPV6) {
  795. ipv6h = skb_header_pointer(skb, offset,
  796. sizeof(_ipv6h), &_ipv6h);
  797. if (!ipv6h || ipv6h->nexthdr != IPPROTO_TCP)
  798. return NULL;
  799. offset += sizeof(struct ipv6hdr);
  800. } else if (iph->protocol != IPPROTO_TCP) {
  801. return NULL;
  802. }
  803. } else if (ipv6h->version == 6) {
  804. if (ipv6h->nexthdr != IPPROTO_TCP)
  805. return NULL;
  806. offset += sizeof(struct ipv6hdr);
  807. } else {
  808. return NULL;
  809. }
  810. tcph = skb_header_pointer(skb, offset, sizeof(_tcph), &_tcph);
  811. if (!tcph || tcph->doff < 5)
  812. return NULL;
  813. return skb_header_pointer(skb, offset,
  814. min(__tcp_hdrlen(tcph), bufsize), buf);
  815. }
  816. static const void *cake_get_tcpopt(const struct tcphdr *tcph,
  817. int code, int *oplen)
  818. {
  819. /* inspired by tcp_parse_options in tcp_input.c */
  820. int length = __tcp_hdrlen(tcph) - sizeof(struct tcphdr);
  821. const u8 *ptr = (const u8 *)(tcph + 1);
  822. while (length > 0) {
  823. int opcode = *ptr++;
  824. int opsize;
  825. if (opcode == TCPOPT_EOL)
  826. break;
  827. if (opcode == TCPOPT_NOP) {
  828. length--;
  829. continue;
  830. }
  831. if (length < 2)
  832. break;
  833. opsize = *ptr++;
  834. if (opsize < 2 || opsize > length)
  835. break;
  836. if (opcode == code) {
  837. *oplen = opsize;
  838. return ptr;
  839. }
  840. ptr += opsize - 2;
  841. length -= opsize;
  842. }
  843. return NULL;
  844. }
  845. /* Compare two SACK sequences. A sequence is considered greater if it SACKs more
  846. * bytes than the other. In the case where both sequences ACKs bytes that the
  847. * other doesn't, A is considered greater. DSACKs in A also makes A be
  848. * considered greater.
  849. *
  850. * @return -1, 0 or 1 as normal compare functions
  851. */
  852. static int cake_tcph_sack_compare(const struct tcphdr *tcph_a,
  853. const struct tcphdr *tcph_b)
  854. {
  855. const struct tcp_sack_block_wire *sack_a, *sack_b;
  856. u32 ack_seq_a = ntohl(tcph_a->ack_seq);
  857. u32 bytes_a = 0, bytes_b = 0;
  858. int oplen_a, oplen_b;
  859. bool first = true;
  860. sack_a = cake_get_tcpopt(tcph_a, TCPOPT_SACK, &oplen_a);
  861. sack_b = cake_get_tcpopt(tcph_b, TCPOPT_SACK, &oplen_b);
  862. /* pointers point to option contents */
  863. oplen_a -= TCPOLEN_SACK_BASE;
  864. oplen_b -= TCPOLEN_SACK_BASE;
  865. if (sack_a && oplen_a >= sizeof(*sack_a) &&
  866. (!sack_b || oplen_b < sizeof(*sack_b)))
  867. return -1;
  868. else if (sack_b && oplen_b >= sizeof(*sack_b) &&
  869. (!sack_a || oplen_a < sizeof(*sack_a)))
  870. return 1;
  871. else if ((!sack_a || oplen_a < sizeof(*sack_a)) &&
  872. (!sack_b || oplen_b < sizeof(*sack_b)))
  873. return 0;
  874. while (oplen_a >= sizeof(*sack_a)) {
  875. const struct tcp_sack_block_wire *sack_tmp = sack_b;
  876. u32 start_a = get_unaligned_be32(&sack_a->start_seq);
  877. u32 end_a = get_unaligned_be32(&sack_a->end_seq);
  878. int oplen_tmp = oplen_b;
  879. bool found = false;
  880. /* DSACK; always considered greater to prevent dropping */
  881. if (before(start_a, ack_seq_a))
  882. return -1;
  883. bytes_a += end_a - start_a;
  884. while (oplen_tmp >= sizeof(*sack_tmp)) {
  885. u32 start_b = get_unaligned_be32(&sack_tmp->start_seq);
  886. u32 end_b = get_unaligned_be32(&sack_tmp->end_seq);
  887. /* first time through we count the total size */
  888. if (first)
  889. bytes_b += end_b - start_b;
  890. if (!after(start_b, start_a) && !before(end_b, end_a)) {
  891. found = true;
  892. if (!first)
  893. break;
  894. }
  895. oplen_tmp -= sizeof(*sack_tmp);
  896. sack_tmp++;
  897. }
  898. if (!found)
  899. return -1;
  900. oplen_a -= sizeof(*sack_a);
  901. sack_a++;
  902. first = false;
  903. }
  904. /* If we made it this far, all ranges SACKed by A are covered by B, so
  905. * either the SACKs are equal, or B SACKs more bytes.
  906. */
  907. return bytes_b > bytes_a ? 1 : 0;
  908. }
  909. static void cake_tcph_get_tstamp(const struct tcphdr *tcph,
  910. u32 *tsval, u32 *tsecr)
  911. {
  912. const u8 *ptr;
  913. int opsize;
  914. ptr = cake_get_tcpopt(tcph, TCPOPT_TIMESTAMP, &opsize);
  915. if (ptr && opsize == TCPOLEN_TIMESTAMP) {
  916. *tsval = get_unaligned_be32(ptr);
  917. *tsecr = get_unaligned_be32(ptr + 4);
  918. }
  919. }
  920. static bool cake_tcph_may_drop(const struct tcphdr *tcph,
  921. u32 tstamp_new, u32 tsecr_new)
  922. {
  923. /* inspired by tcp_parse_options in tcp_input.c */
  924. int length = __tcp_hdrlen(tcph) - sizeof(struct tcphdr);
  925. const u8 *ptr = (const u8 *)(tcph + 1);
  926. u32 tstamp, tsecr;
  927. /* 3 reserved flags must be unset to avoid future breakage
  928. * ACK must be set
  929. * ECE/CWR are handled separately
  930. * All other flags URG/PSH/RST/SYN/FIN must be unset
  931. * 0x0FFF0000 = all TCP flags (confirm ACK=1, others zero)
  932. * 0x00C00000 = CWR/ECE (handled separately)
  933. * 0x0F3F0000 = 0x0FFF0000 & ~0x00C00000
  934. */
  935. if (((tcp_flag_word(tcph) &
  936. cpu_to_be32(0x0F3F0000)) != TCP_FLAG_ACK))
  937. return false;
  938. while (length > 0) {
  939. int opcode = *ptr++;
  940. int opsize;
  941. if (opcode == TCPOPT_EOL)
  942. break;
  943. if (opcode == TCPOPT_NOP) {
  944. length--;
  945. continue;
  946. }
  947. if (length < 2)
  948. break;
  949. opsize = *ptr++;
  950. if (opsize < 2 || opsize > length)
  951. break;
  952. switch (opcode) {
  953. case TCPOPT_MD5SIG: /* doesn't influence state */
  954. break;
  955. case TCPOPT_SACK: /* stricter checking performed later */
  956. if (opsize % 8 != 2)
  957. return false;
  958. break;
  959. case TCPOPT_TIMESTAMP:
  960. /* only drop timestamps lower than new */
  961. if (opsize != TCPOLEN_TIMESTAMP)
  962. return false;
  963. tstamp = get_unaligned_be32(ptr);
  964. tsecr = get_unaligned_be32(ptr + 4);
  965. if (after(tstamp, tstamp_new) ||
  966. after(tsecr, tsecr_new))
  967. return false;
  968. break;
  969. case TCPOPT_MSS: /* these should only be set on SYN */
  970. case TCPOPT_WINDOW:
  971. case TCPOPT_SACK_PERM:
  972. case TCPOPT_FASTOPEN:
  973. case TCPOPT_EXP:
  974. default: /* don't drop if any unknown options are present */
  975. return false;
  976. }
  977. ptr += opsize - 2;
  978. length -= opsize;
  979. }
  980. return true;
  981. }
  982. static struct sk_buff *cake_ack_filter(struct cake_sched_data *q,
  983. struct cake_flow *flow)
  984. {
  985. bool aggressive = q->ack_filter == CAKE_ACK_AGGRESSIVE;
  986. struct sk_buff *elig_ack = NULL, *elig_ack_prev = NULL;
  987. struct sk_buff *skb_check, *skb_prev = NULL;
  988. const struct ipv6hdr *ipv6h, *ipv6h_check;
  989. unsigned char _tcph[64], _tcph_check[64];
  990. const struct tcphdr *tcph, *tcph_check;
  991. const struct iphdr *iph, *iph_check;
  992. struct ipv6hdr _iph, _iph_check;
  993. const struct sk_buff *skb;
  994. int seglen, num_found = 0;
  995. u32 tstamp = 0, tsecr = 0;
  996. __be32 elig_flags = 0;
  997. int sack_comp;
  998. /* no other possible ACKs to filter */
  999. if (flow->head == flow->tail)
  1000. return NULL;
  1001. skb = flow->tail;
  1002. tcph = cake_get_tcphdr(skb, _tcph, sizeof(_tcph));
  1003. iph = cake_get_iphdr(skb, &_iph);
  1004. if (!tcph)
  1005. return NULL;
  1006. cake_tcph_get_tstamp(tcph, &tstamp, &tsecr);
  1007. /* the 'triggering' packet need only have the ACK flag set.
  1008. * also check that SYN is not set, as there won't be any previous ACKs.
  1009. */
  1010. if ((tcp_flag_word(tcph) &
  1011. (TCP_FLAG_ACK | TCP_FLAG_SYN)) != TCP_FLAG_ACK)
  1012. return NULL;
  1013. /* the 'triggering' ACK is at the tail of the queue, we have already
  1014. * returned if it is the only packet in the flow. loop through the rest
  1015. * of the queue looking for pure ACKs with the same 5-tuple as the
  1016. * triggering one.
  1017. */
  1018. for (skb_check = flow->head;
  1019. skb_check && skb_check != skb;
  1020. skb_prev = skb_check, skb_check = skb_check->next) {
  1021. iph_check = cake_get_iphdr(skb_check, &_iph_check);
  1022. tcph_check = cake_get_tcphdr(skb_check, &_tcph_check,
  1023. sizeof(_tcph_check));
  1024. /* only TCP packets with matching 5-tuple are eligible, and only
  1025. * drop safe headers
  1026. */
  1027. if (!tcph_check || iph->version != iph_check->version ||
  1028. tcph_check->source != tcph->source ||
  1029. tcph_check->dest != tcph->dest)
  1030. continue;
  1031. if (iph_check->version == 4) {
  1032. if (iph_check->saddr != iph->saddr ||
  1033. iph_check->daddr != iph->daddr)
  1034. continue;
  1035. seglen = ntohs(iph_check->tot_len) -
  1036. (4 * iph_check->ihl);
  1037. } else if (iph_check->version == 6) {
  1038. ipv6h = (struct ipv6hdr *)iph;
  1039. ipv6h_check = (struct ipv6hdr *)iph_check;
  1040. if (ipv6_addr_cmp(&ipv6h_check->saddr, &ipv6h->saddr) ||
  1041. ipv6_addr_cmp(&ipv6h_check->daddr, &ipv6h->daddr))
  1042. continue;
  1043. seglen = ntohs(ipv6h_check->payload_len);
  1044. } else {
  1045. WARN_ON(1); /* shouldn't happen */
  1046. continue;
  1047. }
  1048. /* If the ECE/CWR flags changed from the previous eligible
  1049. * packet in the same flow, we should no longer be dropping that
  1050. * previous packet as this would lose information.
  1051. */
  1052. if (elig_ack && (tcp_flag_word(tcph_check) &
  1053. (TCP_FLAG_ECE | TCP_FLAG_CWR)) != elig_flags) {
  1054. elig_ack = NULL;
  1055. elig_ack_prev = NULL;
  1056. num_found--;
  1057. }
  1058. /* Check TCP options and flags, don't drop ACKs with segment
  1059. * data, and don't drop ACKs with a higher cumulative ACK
  1060. * counter than the triggering packet. Check ACK seqno here to
  1061. * avoid parsing SACK options of packets we are going to exclude
  1062. * anyway.
  1063. */
  1064. if (!cake_tcph_may_drop(tcph_check, tstamp, tsecr) ||
  1065. (seglen - __tcp_hdrlen(tcph_check)) != 0 ||
  1066. after(ntohl(tcph_check->ack_seq), ntohl(tcph->ack_seq)))
  1067. continue;
  1068. /* Check SACK options. The triggering packet must SACK more data
  1069. * than the ACK under consideration, or SACK the same range but
  1070. * have a larger cumulative ACK counter. The latter is a
  1071. * pathological case, but is contained in the following check
  1072. * anyway, just to be safe.
  1073. */
  1074. sack_comp = cake_tcph_sack_compare(tcph_check, tcph);
  1075. if (sack_comp < 0 ||
  1076. (ntohl(tcph_check->ack_seq) == ntohl(tcph->ack_seq) &&
  1077. sack_comp == 0))
  1078. continue;
  1079. /* At this point we have found an eligible pure ACK to drop; if
  1080. * we are in aggressive mode, we are done. Otherwise, keep
  1081. * searching unless this is the second eligible ACK we
  1082. * found.
  1083. *
  1084. * Since we want to drop ACK closest to the head of the queue,
  1085. * save the first eligible ACK we find, even if we need to loop
  1086. * again.
  1087. */
  1088. if (!elig_ack) {
  1089. elig_ack = skb_check;
  1090. elig_ack_prev = skb_prev;
  1091. elig_flags = (tcp_flag_word(tcph_check)
  1092. & (TCP_FLAG_ECE | TCP_FLAG_CWR));
  1093. }
  1094. if (num_found++ > 0)
  1095. goto found;
  1096. }
  1097. /* We made it through the queue without finding two eligible ACKs . If
  1098. * we found a single eligible ACK we can drop it in aggressive mode if
  1099. * we can guarantee that this does not interfere with ECN flag
  1100. * information. We ensure this by dropping it only if the enqueued
  1101. * packet is consecutive with the eligible ACK, and their flags match.
  1102. */
  1103. if (elig_ack && aggressive && elig_ack->next == skb &&
  1104. (elig_flags == (tcp_flag_word(tcph) &
  1105. (TCP_FLAG_ECE | TCP_FLAG_CWR))))
  1106. goto found;
  1107. return NULL;
  1108. found:
  1109. if (elig_ack_prev)
  1110. elig_ack_prev->next = elig_ack->next;
  1111. else
  1112. flow->head = elig_ack->next;
  1113. skb_mark_not_on_list(elig_ack);
  1114. return elig_ack;
  1115. }
  1116. static u64 cake_ewma(u64 avg, u64 sample, u32 shift)
  1117. {
  1118. avg -= avg >> shift;
  1119. avg += sample >> shift;
  1120. return avg;
  1121. }
  1122. static u32 cake_calc_overhead(struct cake_sched_data *q, u32 len, u32 off)
  1123. {
  1124. if (q->rate_flags & CAKE_FLAG_OVERHEAD)
  1125. len -= off;
  1126. if (q->max_netlen < len)
  1127. q->max_netlen = len;
  1128. if (q->min_netlen > len)
  1129. q->min_netlen = len;
  1130. len += q->rate_overhead;
  1131. if (len < q->rate_mpu)
  1132. len = q->rate_mpu;
  1133. if (q->atm_mode == CAKE_ATM_ATM) {
  1134. len += 47;
  1135. len /= 48;
  1136. len *= 53;
  1137. } else if (q->atm_mode == CAKE_ATM_PTM) {
  1138. /* Add one byte per 64 bytes or part thereof.
  1139. * This is conservative and easier to calculate than the
  1140. * precise value.
  1141. */
  1142. len += (len + 63) / 64;
  1143. }
  1144. if (q->max_adjlen < len)
  1145. q->max_adjlen = len;
  1146. if (q->min_adjlen > len)
  1147. q->min_adjlen = len;
  1148. return len;
  1149. }
  1150. static u32 cake_overhead(struct cake_sched_data *q, const struct sk_buff *skb)
  1151. {
  1152. const struct skb_shared_info *shinfo = skb_shinfo(skb);
  1153. unsigned int hdr_len, last_len = 0;
  1154. u32 off = skb_network_offset(skb);
  1155. u32 len = qdisc_pkt_len(skb);
  1156. u16 segs = 1;
  1157. q->avg_netoff = cake_ewma(q->avg_netoff, off << 16, 8);
  1158. if (!shinfo->gso_size)
  1159. return cake_calc_overhead(q, len, off);
  1160. /* borrowed from qdisc_pkt_len_init() */
  1161. hdr_len = skb_transport_header(skb) - skb_mac_header(skb);
  1162. /* + transport layer */
  1163. if (likely(shinfo->gso_type & (SKB_GSO_TCPV4 |
  1164. SKB_GSO_TCPV6))) {
  1165. const struct tcphdr *th;
  1166. struct tcphdr _tcphdr;
  1167. th = skb_header_pointer(skb, skb_transport_offset(skb),
  1168. sizeof(_tcphdr), &_tcphdr);
  1169. if (likely(th))
  1170. hdr_len += __tcp_hdrlen(th);
  1171. } else {
  1172. struct udphdr _udphdr;
  1173. if (skb_header_pointer(skb, skb_transport_offset(skb),
  1174. sizeof(_udphdr), &_udphdr))
  1175. hdr_len += sizeof(struct udphdr);
  1176. }
  1177. if (unlikely(shinfo->gso_type & SKB_GSO_DODGY))
  1178. segs = DIV_ROUND_UP(skb->len - hdr_len,
  1179. shinfo->gso_size);
  1180. else
  1181. segs = shinfo->gso_segs;
  1182. len = shinfo->gso_size + hdr_len;
  1183. last_len = skb->len - shinfo->gso_size * (segs - 1);
  1184. return (cake_calc_overhead(q, len, off) * (segs - 1) +
  1185. cake_calc_overhead(q, last_len, off));
  1186. }
  1187. static void cake_heap_swap(struct cake_sched_data *q, u16 i, u16 j)
  1188. {
  1189. struct cake_heap_entry ii = q->overflow_heap[i];
  1190. struct cake_heap_entry jj = q->overflow_heap[j];
  1191. q->overflow_heap[i] = jj;
  1192. q->overflow_heap[j] = ii;
  1193. q->tins[ii.t].overflow_idx[ii.b] = j;
  1194. q->tins[jj.t].overflow_idx[jj.b] = i;
  1195. }
  1196. static u32 cake_heap_get_backlog(const struct cake_sched_data *q, u16 i)
  1197. {
  1198. struct cake_heap_entry ii = q->overflow_heap[i];
  1199. return q->tins[ii.t].backlogs[ii.b];
  1200. }
  1201. static void cake_heapify(struct cake_sched_data *q, u16 i)
  1202. {
  1203. static const u32 a = CAKE_MAX_TINS * CAKE_QUEUES;
  1204. u32 mb = cake_heap_get_backlog(q, i);
  1205. u32 m = i;
  1206. while (m < a) {
  1207. u32 l = m + m + 1;
  1208. u32 r = l + 1;
  1209. if (l < a) {
  1210. u32 lb = cake_heap_get_backlog(q, l);
  1211. if (lb > mb) {
  1212. m = l;
  1213. mb = lb;
  1214. }
  1215. }
  1216. if (r < a) {
  1217. u32 rb = cake_heap_get_backlog(q, r);
  1218. if (rb > mb) {
  1219. m = r;
  1220. mb = rb;
  1221. }
  1222. }
  1223. if (m != i) {
  1224. cake_heap_swap(q, i, m);
  1225. i = m;
  1226. } else {
  1227. break;
  1228. }
  1229. }
  1230. }
  1231. static void cake_heapify_up(struct cake_sched_data *q, u16 i)
  1232. {
  1233. while (i > 0 && i < CAKE_MAX_TINS * CAKE_QUEUES) {
  1234. u16 p = (i - 1) >> 1;
  1235. u32 ib = cake_heap_get_backlog(q, i);
  1236. u32 pb = cake_heap_get_backlog(q, p);
  1237. if (ib > pb) {
  1238. cake_heap_swap(q, i, p);
  1239. i = p;
  1240. } else {
  1241. break;
  1242. }
  1243. }
  1244. }
  1245. static int cake_advance_shaper(struct cake_sched_data *q,
  1246. struct cake_tin_data *b,
  1247. struct sk_buff *skb,
  1248. ktime_t now, bool drop)
  1249. {
  1250. u32 len = get_cobalt_cb(skb)->adjusted_len;
  1251. /* charge packet bandwidth to this tin
  1252. * and to the global shaper.
  1253. */
  1254. if (q->rate_ns) {
  1255. u64 tin_dur = (len * b->tin_rate_ns) >> b->tin_rate_shft;
  1256. u64 global_dur = (len * q->rate_ns) >> q->rate_shft;
  1257. u64 failsafe_dur = global_dur + (global_dur >> 1);
  1258. if (ktime_before(b->time_next_packet, now))
  1259. b->time_next_packet = ktime_add_ns(b->time_next_packet,
  1260. tin_dur);
  1261. else if (ktime_before(b->time_next_packet,
  1262. ktime_add_ns(now, tin_dur)))
  1263. b->time_next_packet = ktime_add_ns(now, tin_dur);
  1264. q->time_next_packet = ktime_add_ns(q->time_next_packet,
  1265. global_dur);
  1266. if (!drop)
  1267. q->failsafe_next_packet = \
  1268. ktime_add_ns(q->failsafe_next_packet,
  1269. failsafe_dur);
  1270. }
  1271. return len;
  1272. }
  1273. static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
  1274. {
  1275. struct cake_sched_data *q = qdisc_priv(sch);
  1276. ktime_t now = ktime_get();
  1277. u32 idx = 0, tin = 0, len;
  1278. struct cake_heap_entry qq;
  1279. struct cake_tin_data *b;
  1280. struct cake_flow *flow;
  1281. struct sk_buff *skb;
  1282. if (!q->overflow_timeout) {
  1283. int i;
  1284. /* Build fresh max-heap */
  1285. for (i = CAKE_MAX_TINS * CAKE_QUEUES / 2; i >= 0; i--)
  1286. cake_heapify(q, i);
  1287. }
  1288. q->overflow_timeout = 65535;
  1289. /* select longest queue for pruning */
  1290. qq = q->overflow_heap[0];
  1291. tin = qq.t;
  1292. idx = qq.b;
  1293. b = &q->tins[tin];
  1294. flow = &b->flows[idx];
  1295. skb = dequeue_head(flow);
  1296. if (unlikely(!skb)) {
  1297. /* heap has gone wrong, rebuild it next time */
  1298. q->overflow_timeout = 0;
  1299. return idx + (tin << 16);
  1300. }
  1301. if (cobalt_queue_full(&flow->cvars, &b->cparams, now))
  1302. b->unresponsive_flow_count++;
  1303. len = qdisc_pkt_len(skb);
  1304. q->buffer_used -= skb->truesize;
  1305. b->backlogs[idx] -= len;
  1306. b->tin_backlog -= len;
  1307. sch->qstats.backlog -= len;
  1308. qdisc_tree_reduce_backlog(sch, 1, len);
  1309. flow->dropped++;
  1310. b->tin_dropped++;
  1311. sch->qstats.drops++;
  1312. if (q->rate_flags & CAKE_FLAG_INGRESS)
  1313. cake_advance_shaper(q, b, skb, now, true);
  1314. __qdisc_drop(skb, to_free);
  1315. sch->q.qlen--;
  1316. cake_heapify(q, 0);
  1317. return idx + (tin << 16);
  1318. }
  1319. static u8 cake_handle_diffserv(struct sk_buff *skb, bool wash)
  1320. {
  1321. const int offset = skb_network_offset(skb);
  1322. u16 *buf, buf_;
  1323. u8 dscp;
  1324. switch (skb_protocol(skb, true)) {
  1325. case htons(ETH_P_IP):
  1326. buf = skb_header_pointer(skb, offset, sizeof(buf_), &buf_);
  1327. if (unlikely(!buf))
  1328. return 0;
  1329. /* ToS is in the second byte of iphdr */
  1330. dscp = ipv4_get_dsfield((struct iphdr *)buf) >> 2;
  1331. if (wash && dscp) {
  1332. const int wlen = offset + sizeof(struct iphdr);
  1333. if (!pskb_may_pull(skb, wlen) ||
  1334. skb_try_make_writable(skb, wlen))
  1335. return 0;
  1336. ipv4_change_dsfield(ip_hdr(skb), INET_ECN_MASK, 0);
  1337. }
  1338. return dscp;
  1339. case htons(ETH_P_IPV6):
  1340. buf = skb_header_pointer(skb, offset, sizeof(buf_), &buf_);
  1341. if (unlikely(!buf))
  1342. return 0;
  1343. /* Traffic class is in the first and second bytes of ipv6hdr */
  1344. dscp = ipv6_get_dsfield((struct ipv6hdr *)buf) >> 2;
  1345. if (wash && dscp) {
  1346. const int wlen = offset + sizeof(struct ipv6hdr);
  1347. if (!pskb_may_pull(skb, wlen) ||
  1348. skb_try_make_writable(skb, wlen))
  1349. return 0;
  1350. ipv6_change_dsfield(ipv6_hdr(skb), INET_ECN_MASK, 0);
  1351. }
  1352. return dscp;
  1353. case htons(ETH_P_ARP):
  1354. return 0x38; /* CS7 - Net Control */
  1355. default:
  1356. /* If there is no Diffserv field, treat as best-effort */
  1357. return 0;
  1358. }
  1359. }
  1360. static struct cake_tin_data *cake_select_tin(struct Qdisc *sch,
  1361. struct sk_buff *skb)
  1362. {
  1363. struct cake_sched_data *q = qdisc_priv(sch);
  1364. u32 tin, mark;
  1365. bool wash;
  1366. u8 dscp;
  1367. /* Tin selection: Default to diffserv-based selection, allow overriding
  1368. * using firewall marks or skb->priority. Call DSCP parsing early if
  1369. * wash is enabled, otherwise defer to below to skip unneeded parsing.
  1370. */
  1371. mark = (skb->mark & q->fwmark_mask) >> q->fwmark_shft;
  1372. wash = !!(q->rate_flags & CAKE_FLAG_WASH);
  1373. if (wash)
  1374. dscp = cake_handle_diffserv(skb, wash);
  1375. if (q->tin_mode == CAKE_DIFFSERV_BESTEFFORT)
  1376. tin = 0;
  1377. else if (mark && mark <= q->tin_cnt)
  1378. tin = q->tin_order[mark - 1];
  1379. else if (TC_H_MAJ(skb->priority) == sch->handle &&
  1380. TC_H_MIN(skb->priority) > 0 &&
  1381. TC_H_MIN(skb->priority) <= q->tin_cnt)
  1382. tin = q->tin_order[TC_H_MIN(skb->priority) - 1];
  1383. else {
  1384. if (!wash)
  1385. dscp = cake_handle_diffserv(skb, wash);
  1386. tin = q->tin_index[dscp];
  1387. if (unlikely(tin >= q->tin_cnt))
  1388. tin = 0;
  1389. }
  1390. return &q->tins[tin];
  1391. }
  1392. static u32 cake_classify(struct Qdisc *sch, struct cake_tin_data **t,
  1393. struct sk_buff *skb, int flow_mode, int *qerr)
  1394. {
  1395. struct cake_sched_data *q = qdisc_priv(sch);
  1396. struct tcf_proto *filter;
  1397. struct tcf_result res;
  1398. u16 flow = 0, host = 0;
  1399. int result;
  1400. filter = rcu_dereference_bh(q->filter_list);
  1401. if (!filter)
  1402. goto hash;
  1403. *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
  1404. result = tcf_classify(skb, filter, &res, false);
  1405. if (result >= 0) {
  1406. #ifdef CONFIG_NET_CLS_ACT
  1407. switch (result) {
  1408. case TC_ACT_STOLEN:
  1409. case TC_ACT_QUEUED:
  1410. case TC_ACT_TRAP:
  1411. *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
  1412. fallthrough;
  1413. case TC_ACT_SHOT:
  1414. return 0;
  1415. }
  1416. #endif
  1417. if (TC_H_MIN(res.classid) <= CAKE_QUEUES)
  1418. flow = TC_H_MIN(res.classid);
  1419. if (TC_H_MAJ(res.classid) <= (CAKE_QUEUES << 16))
  1420. host = TC_H_MAJ(res.classid) >> 16;
  1421. }
  1422. hash:
  1423. *t = cake_select_tin(sch, skb);
  1424. return cake_hash(*t, skb, flow_mode, flow, host) + 1;
  1425. }
  1426. static void cake_reconfigure(struct Qdisc *sch);
  1427. static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
  1428. struct sk_buff **to_free)
  1429. {
  1430. struct cake_sched_data *q = qdisc_priv(sch);
  1431. int len = qdisc_pkt_len(skb);
  1432. int ret;
  1433. struct sk_buff *ack = NULL;
  1434. ktime_t now = ktime_get();
  1435. struct cake_tin_data *b;
  1436. struct cake_flow *flow;
  1437. u32 idx;
  1438. /* choose flow to insert into */
  1439. idx = cake_classify(sch, &b, skb, q->flow_mode, &ret);
  1440. if (idx == 0) {
  1441. if (ret & __NET_XMIT_BYPASS)
  1442. qdisc_qstats_drop(sch);
  1443. __qdisc_drop(skb, to_free);
  1444. return ret;
  1445. }
  1446. idx--;
  1447. flow = &b->flows[idx];
  1448. /* ensure shaper state isn't stale */
  1449. if (!b->tin_backlog) {
  1450. if (ktime_before(b->time_next_packet, now))
  1451. b->time_next_packet = now;
  1452. if (!sch->q.qlen) {
  1453. if (ktime_before(q->time_next_packet, now)) {
  1454. q->failsafe_next_packet = now;
  1455. q->time_next_packet = now;
  1456. } else if (ktime_after(q->time_next_packet, now) &&
  1457. ktime_after(q->failsafe_next_packet, now)) {
  1458. u64 next = \
  1459. min(ktime_to_ns(q->time_next_packet),
  1460. ktime_to_ns(
  1461. q->failsafe_next_packet));
  1462. sch->qstats.overlimits++;
  1463. qdisc_watchdog_schedule_ns(&q->watchdog, next);
  1464. }
  1465. }
  1466. }
  1467. if (unlikely(len > b->max_skblen))
  1468. b->max_skblen = len;
  1469. if (skb_is_gso(skb) && q->rate_flags & CAKE_FLAG_SPLIT_GSO) {
  1470. struct sk_buff *segs, *nskb;
  1471. netdev_features_t features = netif_skb_features(skb);
  1472. unsigned int slen = 0, numsegs = 0;
  1473. segs = skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK);
  1474. if (IS_ERR_OR_NULL(segs))
  1475. return qdisc_drop(skb, sch, to_free);
  1476. skb_list_walk_safe(segs, segs, nskb) {
  1477. skb_mark_not_on_list(segs);
  1478. qdisc_skb_cb(segs)->pkt_len = segs->len;
  1479. cobalt_set_enqueue_time(segs, now);
  1480. get_cobalt_cb(segs)->adjusted_len = cake_overhead(q,
  1481. segs);
  1482. flow_queue_add(flow, segs);
  1483. sch->q.qlen++;
  1484. numsegs++;
  1485. slen += segs->len;
  1486. q->buffer_used += segs->truesize;
  1487. b->packets++;
  1488. }
  1489. /* stats */
  1490. b->bytes += slen;
  1491. b->backlogs[idx] += slen;
  1492. b->tin_backlog += slen;
  1493. sch->qstats.backlog += slen;
  1494. q->avg_window_bytes += slen;
  1495. qdisc_tree_reduce_backlog(sch, 1-numsegs, len-slen);
  1496. consume_skb(skb);
  1497. } else {
  1498. /* not splitting */
  1499. cobalt_set_enqueue_time(skb, now);
  1500. get_cobalt_cb(skb)->adjusted_len = cake_overhead(q, skb);
  1501. flow_queue_add(flow, skb);
  1502. if (q->ack_filter)
  1503. ack = cake_ack_filter(q, flow);
  1504. if (ack) {
  1505. b->ack_drops++;
  1506. sch->qstats.drops++;
  1507. b->bytes += qdisc_pkt_len(ack);
  1508. len -= qdisc_pkt_len(ack);
  1509. q->buffer_used += skb->truesize - ack->truesize;
  1510. if (q->rate_flags & CAKE_FLAG_INGRESS)
  1511. cake_advance_shaper(q, b, ack, now, true);
  1512. qdisc_tree_reduce_backlog(sch, 1, qdisc_pkt_len(ack));
  1513. consume_skb(ack);
  1514. } else {
  1515. sch->q.qlen++;
  1516. q->buffer_used += skb->truesize;
  1517. }
  1518. /* stats */
  1519. b->packets++;
  1520. b->bytes += len;
  1521. b->backlogs[idx] += len;
  1522. b->tin_backlog += len;
  1523. sch->qstats.backlog += len;
  1524. q->avg_window_bytes += len;
  1525. }
  1526. if (q->overflow_timeout)
  1527. cake_heapify_up(q, b->overflow_idx[idx]);
  1528. /* incoming bandwidth capacity estimate */
  1529. if (q->rate_flags & CAKE_FLAG_AUTORATE_INGRESS) {
  1530. u64 packet_interval = \
  1531. ktime_to_ns(ktime_sub(now, q->last_packet_time));
  1532. if (packet_interval > NSEC_PER_SEC)
  1533. packet_interval = NSEC_PER_SEC;
  1534. /* filter out short-term bursts, eg. wifi aggregation */
  1535. q->avg_packet_interval = \
  1536. cake_ewma(q->avg_packet_interval,
  1537. packet_interval,
  1538. (packet_interval > q->avg_packet_interval ?
  1539. 2 : 8));
  1540. q->last_packet_time = now;
  1541. if (packet_interval > q->avg_packet_interval) {
  1542. u64 window_interval = \
  1543. ktime_to_ns(ktime_sub(now,
  1544. q->avg_window_begin));
  1545. u64 b = q->avg_window_bytes * (u64)NSEC_PER_SEC;
  1546. b = div64_u64(b, window_interval);
  1547. q->avg_peak_bandwidth =
  1548. cake_ewma(q->avg_peak_bandwidth, b,
  1549. b > q->avg_peak_bandwidth ? 2 : 8);
  1550. q->avg_window_bytes = 0;
  1551. q->avg_window_begin = now;
  1552. if (ktime_after(now,
  1553. ktime_add_ms(q->last_reconfig_time,
  1554. 250))) {
  1555. q->rate_bps = (q->avg_peak_bandwidth * 15) >> 4;
  1556. cake_reconfigure(sch);
  1557. }
  1558. }
  1559. } else {
  1560. q->avg_window_bytes = 0;
  1561. q->last_packet_time = now;
  1562. }
  1563. /* flowchain */
  1564. if (!flow->set || flow->set == CAKE_SET_DECAYING) {
  1565. struct cake_host *srchost = &b->hosts[flow->srchost];
  1566. struct cake_host *dsthost = &b->hosts[flow->dsthost];
  1567. u16 host_load = 1;
  1568. if (!flow->set) {
  1569. list_add_tail(&flow->flowchain, &b->new_flows);
  1570. } else {
  1571. b->decaying_flow_count--;
  1572. list_move_tail(&flow->flowchain, &b->new_flows);
  1573. }
  1574. flow->set = CAKE_SET_SPARSE;
  1575. b->sparse_flow_count++;
  1576. if (cake_dsrc(q->flow_mode))
  1577. host_load = max(host_load, srchost->srchost_bulk_flow_count);
  1578. if (cake_ddst(q->flow_mode))
  1579. host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
  1580. flow->deficit = (b->flow_quantum *
  1581. quantum_div[host_load]) >> 16;
  1582. } else if (flow->set == CAKE_SET_SPARSE_WAIT) {
  1583. struct cake_host *srchost = &b->hosts[flow->srchost];
  1584. struct cake_host *dsthost = &b->hosts[flow->dsthost];
  1585. /* this flow was empty, accounted as a sparse flow, but actually
  1586. * in the bulk rotation.
  1587. */
  1588. flow->set = CAKE_SET_BULK;
  1589. b->sparse_flow_count--;
  1590. b->bulk_flow_count++;
  1591. if (cake_dsrc(q->flow_mode))
  1592. srchost->srchost_bulk_flow_count++;
  1593. if (cake_ddst(q->flow_mode))
  1594. dsthost->dsthost_bulk_flow_count++;
  1595. }
  1596. if (q->buffer_used > q->buffer_max_used)
  1597. q->buffer_max_used = q->buffer_used;
  1598. if (q->buffer_used > q->buffer_limit) {
  1599. u32 dropped = 0;
  1600. while (q->buffer_used > q->buffer_limit) {
  1601. dropped++;
  1602. cake_drop(sch, to_free);
  1603. }
  1604. b->drop_overlimit += dropped;
  1605. }
  1606. return NET_XMIT_SUCCESS;
  1607. }
  1608. static struct sk_buff *cake_dequeue_one(struct Qdisc *sch)
  1609. {
  1610. struct cake_sched_data *q = qdisc_priv(sch);
  1611. struct cake_tin_data *b = &q->tins[q->cur_tin];
  1612. struct cake_flow *flow = &b->flows[q->cur_flow];
  1613. struct sk_buff *skb = NULL;
  1614. u32 len;
  1615. if (flow->head) {
  1616. skb = dequeue_head(flow);
  1617. len = qdisc_pkt_len(skb);
  1618. b->backlogs[q->cur_flow] -= len;
  1619. b->tin_backlog -= len;
  1620. sch->qstats.backlog -= len;
  1621. q->buffer_used -= skb->truesize;
  1622. sch->q.qlen--;
  1623. if (q->overflow_timeout)
  1624. cake_heapify(q, b->overflow_idx[q->cur_flow]);
  1625. }
  1626. return skb;
  1627. }
  1628. /* Discard leftover packets from a tin no longer in use. */
  1629. static void cake_clear_tin(struct Qdisc *sch, u16 tin)
  1630. {
  1631. struct cake_sched_data *q = qdisc_priv(sch);
  1632. struct sk_buff *skb;
  1633. q->cur_tin = tin;
  1634. for (q->cur_flow = 0; q->cur_flow < CAKE_QUEUES; q->cur_flow++)
  1635. while (!!(skb = cake_dequeue_one(sch)))
  1636. kfree_skb(skb);
  1637. }
  1638. static struct sk_buff *cake_dequeue(struct Qdisc *sch)
  1639. {
  1640. struct cake_sched_data *q = qdisc_priv(sch);
  1641. struct cake_tin_data *b = &q->tins[q->cur_tin];
  1642. struct cake_host *srchost, *dsthost;
  1643. ktime_t now = ktime_get();
  1644. struct cake_flow *flow;
  1645. struct list_head *head;
  1646. bool first_flow = true;
  1647. struct sk_buff *skb;
  1648. u16 host_load;
  1649. u64 delay;
  1650. u32 len;
  1651. begin:
  1652. if (!sch->q.qlen)
  1653. return NULL;
  1654. /* global hard shaper */
  1655. if (ktime_after(q->time_next_packet, now) &&
  1656. ktime_after(q->failsafe_next_packet, now)) {
  1657. u64 next = min(ktime_to_ns(q->time_next_packet),
  1658. ktime_to_ns(q->failsafe_next_packet));
  1659. sch->qstats.overlimits++;
  1660. qdisc_watchdog_schedule_ns(&q->watchdog, next);
  1661. return NULL;
  1662. }
  1663. /* Choose a class to work on. */
  1664. if (!q->rate_ns) {
  1665. /* In unlimited mode, can't rely on shaper timings, just balance
  1666. * with DRR
  1667. */
  1668. bool wrapped = false, empty = true;
  1669. while (b->tin_deficit < 0 ||
  1670. !(b->sparse_flow_count + b->bulk_flow_count)) {
  1671. if (b->tin_deficit <= 0)
  1672. b->tin_deficit += b->tin_quantum;
  1673. if (b->sparse_flow_count + b->bulk_flow_count)
  1674. empty = false;
  1675. q->cur_tin++;
  1676. b++;
  1677. if (q->cur_tin >= q->tin_cnt) {
  1678. q->cur_tin = 0;
  1679. b = q->tins;
  1680. if (wrapped) {
  1681. /* It's possible for q->qlen to be
  1682. * nonzero when we actually have no
  1683. * packets anywhere.
  1684. */
  1685. if (empty)
  1686. return NULL;
  1687. } else {
  1688. wrapped = true;
  1689. }
  1690. }
  1691. }
  1692. } else {
  1693. /* In shaped mode, choose:
  1694. * - Highest-priority tin with queue and meeting schedule, or
  1695. * - The earliest-scheduled tin with queue.
  1696. */
  1697. ktime_t best_time = KTIME_MAX;
  1698. int tin, best_tin = 0;
  1699. for (tin = 0; tin < q->tin_cnt; tin++) {
  1700. b = q->tins + tin;
  1701. if ((b->sparse_flow_count + b->bulk_flow_count) > 0) {
  1702. ktime_t time_to_pkt = \
  1703. ktime_sub(b->time_next_packet, now);
  1704. if (ktime_to_ns(time_to_pkt) <= 0 ||
  1705. ktime_compare(time_to_pkt,
  1706. best_time) <= 0) {
  1707. best_time = time_to_pkt;
  1708. best_tin = tin;
  1709. }
  1710. }
  1711. }
  1712. q->cur_tin = best_tin;
  1713. b = q->tins + best_tin;
  1714. /* No point in going further if no packets to deliver. */
  1715. if (unlikely(!(b->sparse_flow_count + b->bulk_flow_count)))
  1716. return NULL;
  1717. }
  1718. retry:
  1719. /* service this class */
  1720. head = &b->decaying_flows;
  1721. if (!first_flow || list_empty(head)) {
  1722. head = &b->new_flows;
  1723. if (list_empty(head)) {
  1724. head = &b->old_flows;
  1725. if (unlikely(list_empty(head))) {
  1726. head = &b->decaying_flows;
  1727. if (unlikely(list_empty(head)))
  1728. goto begin;
  1729. }
  1730. }
  1731. }
  1732. flow = list_first_entry(head, struct cake_flow, flowchain);
  1733. q->cur_flow = flow - b->flows;
  1734. first_flow = false;
  1735. /* triple isolation (modified DRR++) */
  1736. srchost = &b->hosts[flow->srchost];
  1737. dsthost = &b->hosts[flow->dsthost];
  1738. host_load = 1;
  1739. /* flow isolation (DRR++) */
  1740. if (flow->deficit <= 0) {
  1741. /* Keep all flows with deficits out of the sparse and decaying
  1742. * rotations. No non-empty flow can go into the decaying
  1743. * rotation, so they can't get deficits
  1744. */
  1745. if (flow->set == CAKE_SET_SPARSE) {
  1746. if (flow->head) {
  1747. b->sparse_flow_count--;
  1748. b->bulk_flow_count++;
  1749. if (cake_dsrc(q->flow_mode))
  1750. srchost->srchost_bulk_flow_count++;
  1751. if (cake_ddst(q->flow_mode))
  1752. dsthost->dsthost_bulk_flow_count++;
  1753. flow->set = CAKE_SET_BULK;
  1754. } else {
  1755. /* we've moved it to the bulk rotation for
  1756. * correct deficit accounting but we still want
  1757. * to count it as a sparse flow, not a bulk one.
  1758. */
  1759. flow->set = CAKE_SET_SPARSE_WAIT;
  1760. }
  1761. }
  1762. if (cake_dsrc(q->flow_mode))
  1763. host_load = max(host_load, srchost->srchost_bulk_flow_count);
  1764. if (cake_ddst(q->flow_mode))
  1765. host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
  1766. WARN_ON(host_load > CAKE_QUEUES);
  1767. /* The shifted prandom_u32() is a way to apply dithering to
  1768. * avoid accumulating roundoff errors
  1769. */
  1770. flow->deficit += (b->flow_quantum * quantum_div[host_load] +
  1771. (prandom_u32() >> 16)) >> 16;
  1772. list_move_tail(&flow->flowchain, &b->old_flows);
  1773. goto retry;
  1774. }
  1775. /* Retrieve a packet via the AQM */
  1776. while (1) {
  1777. skb = cake_dequeue_one(sch);
  1778. if (!skb) {
  1779. /* this queue was actually empty */
  1780. if (cobalt_queue_empty(&flow->cvars, &b->cparams, now))
  1781. b->unresponsive_flow_count--;
  1782. if (flow->cvars.p_drop || flow->cvars.count ||
  1783. ktime_before(now, flow->cvars.drop_next)) {
  1784. /* keep in the flowchain until the state has
  1785. * decayed to rest
  1786. */
  1787. list_move_tail(&flow->flowchain,
  1788. &b->decaying_flows);
  1789. if (flow->set == CAKE_SET_BULK) {
  1790. b->bulk_flow_count--;
  1791. if (cake_dsrc(q->flow_mode))
  1792. srchost->srchost_bulk_flow_count--;
  1793. if (cake_ddst(q->flow_mode))
  1794. dsthost->dsthost_bulk_flow_count--;
  1795. b->decaying_flow_count++;
  1796. } else if (flow->set == CAKE_SET_SPARSE ||
  1797. flow->set == CAKE_SET_SPARSE_WAIT) {
  1798. b->sparse_flow_count--;
  1799. b->decaying_flow_count++;
  1800. }
  1801. flow->set = CAKE_SET_DECAYING;
  1802. } else {
  1803. /* remove empty queue from the flowchain */
  1804. list_del_init(&flow->flowchain);
  1805. if (flow->set == CAKE_SET_SPARSE ||
  1806. flow->set == CAKE_SET_SPARSE_WAIT)
  1807. b->sparse_flow_count--;
  1808. else if (flow->set == CAKE_SET_BULK) {
  1809. b->bulk_flow_count--;
  1810. if (cake_dsrc(q->flow_mode))
  1811. srchost->srchost_bulk_flow_count--;
  1812. if (cake_ddst(q->flow_mode))
  1813. dsthost->dsthost_bulk_flow_count--;
  1814. } else
  1815. b->decaying_flow_count--;
  1816. flow->set = CAKE_SET_NONE;
  1817. }
  1818. goto begin;
  1819. }
  1820. /* Last packet in queue may be marked, shouldn't be dropped */
  1821. if (!cobalt_should_drop(&flow->cvars, &b->cparams, now, skb,
  1822. (b->bulk_flow_count *
  1823. !!(q->rate_flags &
  1824. CAKE_FLAG_INGRESS))) ||
  1825. !flow->head)
  1826. break;
  1827. /* drop this packet, get another one */
  1828. if (q->rate_flags & CAKE_FLAG_INGRESS) {
  1829. len = cake_advance_shaper(q, b, skb,
  1830. now, true);
  1831. flow->deficit -= len;
  1832. b->tin_deficit -= len;
  1833. }
  1834. flow->dropped++;
  1835. b->tin_dropped++;
  1836. qdisc_tree_reduce_backlog(sch, 1, qdisc_pkt_len(skb));
  1837. qdisc_qstats_drop(sch);
  1838. kfree_skb(skb);
  1839. if (q->rate_flags & CAKE_FLAG_INGRESS)
  1840. goto retry;
  1841. }
  1842. b->tin_ecn_mark += !!flow->cvars.ecn_marked;
  1843. qdisc_bstats_update(sch, skb);
  1844. /* collect delay stats */
  1845. delay = ktime_to_ns(ktime_sub(now, cobalt_get_enqueue_time(skb)));
  1846. b->avge_delay = cake_ewma(b->avge_delay, delay, 8);
  1847. b->peak_delay = cake_ewma(b->peak_delay, delay,
  1848. delay > b->peak_delay ? 2 : 8);
  1849. b->base_delay = cake_ewma(b->base_delay, delay,
  1850. delay < b->base_delay ? 2 : 8);
  1851. len = cake_advance_shaper(q, b, skb, now, false);
  1852. flow->deficit -= len;
  1853. b->tin_deficit -= len;
  1854. if (ktime_after(q->time_next_packet, now) && sch->q.qlen) {
  1855. u64 next = min(ktime_to_ns(q->time_next_packet),
  1856. ktime_to_ns(q->failsafe_next_packet));
  1857. qdisc_watchdog_schedule_ns(&q->watchdog, next);
  1858. } else if (!sch->q.qlen) {
  1859. int i;
  1860. for (i = 0; i < q->tin_cnt; i++) {
  1861. if (q->tins[i].decaying_flow_count) {
  1862. ktime_t next = \
  1863. ktime_add_ns(now,
  1864. q->tins[i].cparams.target);
  1865. qdisc_watchdog_schedule_ns(&q->watchdog,
  1866. ktime_to_ns(next));
  1867. break;
  1868. }
  1869. }
  1870. }
  1871. if (q->overflow_timeout)
  1872. q->overflow_timeout--;
  1873. return skb;
  1874. }
  1875. static void cake_reset(struct Qdisc *sch)
  1876. {
  1877. u32 c;
  1878. for (c = 0; c < CAKE_MAX_TINS; c++)
  1879. cake_clear_tin(sch, c);
  1880. }
  1881. static const struct nla_policy cake_policy[TCA_CAKE_MAX + 1] = {
  1882. [TCA_CAKE_BASE_RATE64] = { .type = NLA_U64 },
  1883. [TCA_CAKE_DIFFSERV_MODE] = { .type = NLA_U32 },
  1884. [TCA_CAKE_ATM] = { .type = NLA_U32 },
  1885. [TCA_CAKE_FLOW_MODE] = { .type = NLA_U32 },
  1886. [TCA_CAKE_OVERHEAD] = { .type = NLA_S32 },
  1887. [TCA_CAKE_RTT] = { .type = NLA_U32 },
  1888. [TCA_CAKE_TARGET] = { .type = NLA_U32 },
  1889. [TCA_CAKE_AUTORATE] = { .type = NLA_U32 },
  1890. [TCA_CAKE_MEMORY] = { .type = NLA_U32 },
  1891. [TCA_CAKE_NAT] = { .type = NLA_U32 },
  1892. [TCA_CAKE_RAW] = { .type = NLA_U32 },
  1893. [TCA_CAKE_WASH] = { .type = NLA_U32 },
  1894. [TCA_CAKE_MPU] = { .type = NLA_U32 },
  1895. [TCA_CAKE_INGRESS] = { .type = NLA_U32 },
  1896. [TCA_CAKE_ACK_FILTER] = { .type = NLA_U32 },
  1897. [TCA_CAKE_SPLIT_GSO] = { .type = NLA_U32 },
  1898. [TCA_CAKE_FWMARK] = { .type = NLA_U32 },
  1899. };
  1900. static void cake_set_rate(struct cake_tin_data *b, u64 rate, u32 mtu,
  1901. u64 target_ns, u64 rtt_est_ns)
  1902. {
  1903. /* convert byte-rate into time-per-byte
  1904. * so it will always unwedge in reasonable time.
  1905. */
  1906. static const u64 MIN_RATE = 64;
  1907. u32 byte_target = mtu;
  1908. u64 byte_target_ns;
  1909. u8 rate_shft = 0;
  1910. u64 rate_ns = 0;
  1911. b->flow_quantum = 1514;
  1912. if (rate) {
  1913. b->flow_quantum = max(min(rate >> 12, 1514ULL), 300ULL);
  1914. rate_shft = 34;
  1915. rate_ns = ((u64)NSEC_PER_SEC) << rate_shft;
  1916. rate_ns = div64_u64(rate_ns, max(MIN_RATE, rate));
  1917. while (!!(rate_ns >> 34)) {
  1918. rate_ns >>= 1;
  1919. rate_shft--;
  1920. }
  1921. } /* else unlimited, ie. zero delay */
  1922. b->tin_rate_bps = rate;
  1923. b->tin_rate_ns = rate_ns;
  1924. b->tin_rate_shft = rate_shft;
  1925. byte_target_ns = (byte_target * rate_ns) >> rate_shft;
  1926. b->cparams.target = max((byte_target_ns * 3) / 2, target_ns);
  1927. b->cparams.interval = max(rtt_est_ns +
  1928. b->cparams.target - target_ns,
  1929. b->cparams.target * 2);
  1930. b->cparams.mtu_time = byte_target_ns;
  1931. b->cparams.p_inc = 1 << 24; /* 1/256 */
  1932. b->cparams.p_dec = 1 << 20; /* 1/4096 */
  1933. }
  1934. static int cake_config_besteffort(struct Qdisc *sch)
  1935. {
  1936. struct cake_sched_data *q = qdisc_priv(sch);
  1937. struct cake_tin_data *b = &q->tins[0];
  1938. u32 mtu = psched_mtu(qdisc_dev(sch));
  1939. u64 rate = q->rate_bps;
  1940. q->tin_cnt = 1;
  1941. q->tin_index = besteffort;
  1942. q->tin_order = normal_order;
  1943. cake_set_rate(b, rate, mtu,
  1944. us_to_ns(q->target), us_to_ns(q->interval));
  1945. b->tin_quantum = 65535;
  1946. return 0;
  1947. }
  1948. static int cake_config_precedence(struct Qdisc *sch)
  1949. {
  1950. /* convert high-level (user visible) parameters into internal format */
  1951. struct cake_sched_data *q = qdisc_priv(sch);
  1952. u32 mtu = psched_mtu(qdisc_dev(sch));
  1953. u64 rate = q->rate_bps;
  1954. u32 quantum = 256;
  1955. u32 i;
  1956. q->tin_cnt = 8;
  1957. q->tin_index = precedence;
  1958. q->tin_order = normal_order;
  1959. for (i = 0; i < q->tin_cnt; i++) {
  1960. struct cake_tin_data *b = &q->tins[i];
  1961. cake_set_rate(b, rate, mtu, us_to_ns(q->target),
  1962. us_to_ns(q->interval));
  1963. b->tin_quantum = max_t(u16, 1U, quantum);
  1964. /* calculate next class's parameters */
  1965. rate *= 7;
  1966. rate >>= 3;
  1967. quantum *= 7;
  1968. quantum >>= 3;
  1969. }
  1970. return 0;
  1971. }
  1972. /* List of known Diffserv codepoints:
  1973. *
  1974. * Least Effort (CS1)
  1975. * Best Effort (CS0)
  1976. * Max Reliability & LLT "Lo" (TOS1)
  1977. * Max Throughput (TOS2)
  1978. * Min Delay (TOS4)
  1979. * LLT "La" (TOS5)
  1980. * Assured Forwarding 1 (AF1x) - x3
  1981. * Assured Forwarding 2 (AF2x) - x3
  1982. * Assured Forwarding 3 (AF3x) - x3
  1983. * Assured Forwarding 4 (AF4x) - x3
  1984. * Precedence Class 2 (CS2)
  1985. * Precedence Class 3 (CS3)
  1986. * Precedence Class 4 (CS4)
  1987. * Precedence Class 5 (CS5)
  1988. * Precedence Class 6 (CS6)
  1989. * Precedence Class 7 (CS7)
  1990. * Voice Admit (VA)
  1991. * Expedited Forwarding (EF)
  1992. * Total 25 codepoints.
  1993. */
  1994. /* List of traffic classes in RFC 4594:
  1995. * (roughly descending order of contended priority)
  1996. * (roughly ascending order of uncontended throughput)
  1997. *
  1998. * Network Control (CS6,CS7) - routing traffic
  1999. * Telephony (EF,VA) - aka. VoIP streams
  2000. * Signalling (CS5) - VoIP setup
  2001. * Multimedia Conferencing (AF4x) - aka. video calls
  2002. * Realtime Interactive (CS4) - eg. games
  2003. * Multimedia Streaming (AF3x) - eg. YouTube, NetFlix, Twitch
  2004. * Broadcast Video (CS3)
  2005. * Low Latency Data (AF2x,TOS4) - eg. database
  2006. * Ops, Admin, Management (CS2,TOS1) - eg. ssh
  2007. * Standard Service (CS0 & unrecognised codepoints)
  2008. * High Throughput Data (AF1x,TOS2) - eg. web traffic
  2009. * Low Priority Data (CS1) - eg. BitTorrent
  2010. * Total 12 traffic classes.
  2011. */
  2012. static int cake_config_diffserv8(struct Qdisc *sch)
  2013. {
  2014. /* Pruned list of traffic classes for typical applications:
  2015. *
  2016. * Network Control (CS6, CS7)
  2017. * Minimum Latency (EF, VA, CS5, CS4)
  2018. * Interactive Shell (CS2, TOS1)
  2019. * Low Latency Transactions (AF2x, TOS4)
  2020. * Video Streaming (AF4x, AF3x, CS3)
  2021. * Bog Standard (CS0 etc.)
  2022. * High Throughput (AF1x, TOS2)
  2023. * Background Traffic (CS1)
  2024. *
  2025. * Total 8 traffic classes.
  2026. */
  2027. struct cake_sched_data *q = qdisc_priv(sch);
  2028. u32 mtu = psched_mtu(qdisc_dev(sch));
  2029. u64 rate = q->rate_bps;
  2030. u32 quantum = 256;
  2031. u32 i;
  2032. q->tin_cnt = 8;
  2033. /* codepoint to class mapping */
  2034. q->tin_index = diffserv8;
  2035. q->tin_order = normal_order;
  2036. /* class characteristics */
  2037. for (i = 0; i < q->tin_cnt; i++) {
  2038. struct cake_tin_data *b = &q->tins[i];
  2039. cake_set_rate(b, rate, mtu, us_to_ns(q->target),
  2040. us_to_ns(q->interval));
  2041. b->tin_quantum = max_t(u16, 1U, quantum);
  2042. /* calculate next class's parameters */
  2043. rate *= 7;
  2044. rate >>= 3;
  2045. quantum *= 7;
  2046. quantum >>= 3;
  2047. }
  2048. return 0;
  2049. }
  2050. static int cake_config_diffserv4(struct Qdisc *sch)
  2051. {
  2052. /* Further pruned list of traffic classes for four-class system:
  2053. *
  2054. * Latency Sensitive (CS7, CS6, EF, VA, CS5, CS4)
  2055. * Streaming Media (AF4x, AF3x, CS3, AF2x, TOS4, CS2, TOS1)
  2056. * Best Effort (CS0, AF1x, TOS2, and those not specified)
  2057. * Background Traffic (CS1)
  2058. *
  2059. * Total 4 traffic classes.
  2060. */
  2061. struct cake_sched_data *q = qdisc_priv(sch);
  2062. u32 mtu = psched_mtu(qdisc_dev(sch));
  2063. u64 rate = q->rate_bps;
  2064. u32 quantum = 1024;
  2065. q->tin_cnt = 4;
  2066. /* codepoint to class mapping */
  2067. q->tin_index = diffserv4;
  2068. q->tin_order = bulk_order;
  2069. /* class characteristics */
  2070. cake_set_rate(&q->tins[0], rate, mtu,
  2071. us_to_ns(q->target), us_to_ns(q->interval));
  2072. cake_set_rate(&q->tins[1], rate >> 4, mtu,
  2073. us_to_ns(q->target), us_to_ns(q->interval));
  2074. cake_set_rate(&q->tins[2], rate >> 1, mtu,
  2075. us_to_ns(q->target), us_to_ns(q->interval));
  2076. cake_set_rate(&q->tins[3], rate >> 2, mtu,
  2077. us_to_ns(q->target), us_to_ns(q->interval));
  2078. /* bandwidth-sharing weights */
  2079. q->tins[0].tin_quantum = quantum;
  2080. q->tins[1].tin_quantum = quantum >> 4;
  2081. q->tins[2].tin_quantum = quantum >> 1;
  2082. q->tins[3].tin_quantum = quantum >> 2;
  2083. return 0;
  2084. }
  2085. static int cake_config_diffserv3(struct Qdisc *sch)
  2086. {
  2087. /* Simplified Diffserv structure with 3 tins.
  2088. * Low Priority (CS1)
  2089. * Best Effort
  2090. * Latency Sensitive (TOS4, VA, EF, CS6, CS7)
  2091. */
  2092. struct cake_sched_data *q = qdisc_priv(sch);
  2093. u32 mtu = psched_mtu(qdisc_dev(sch));
  2094. u64 rate = q->rate_bps;
  2095. u32 quantum = 1024;
  2096. q->tin_cnt = 3;
  2097. /* codepoint to class mapping */
  2098. q->tin_index = diffserv3;
  2099. q->tin_order = bulk_order;
  2100. /* class characteristics */
  2101. cake_set_rate(&q->tins[0], rate, mtu,
  2102. us_to_ns(q->target), us_to_ns(q->interval));
  2103. cake_set_rate(&q->tins[1], rate >> 4, mtu,
  2104. us_to_ns(q->target), us_to_ns(q->interval));
  2105. cake_set_rate(&q->tins[2], rate >> 2, mtu,
  2106. us_to_ns(q->target), us_to_ns(q->interval));
  2107. /* bandwidth-sharing weights */
  2108. q->tins[0].tin_quantum = quantum;
  2109. q->tins[1].tin_quantum = quantum >> 4;
  2110. q->tins[2].tin_quantum = quantum >> 2;
  2111. return 0;
  2112. }
  2113. static void cake_reconfigure(struct Qdisc *sch)
  2114. {
  2115. struct cake_sched_data *q = qdisc_priv(sch);
  2116. int c, ft;
  2117. switch (q->tin_mode) {
  2118. case CAKE_DIFFSERV_BESTEFFORT:
  2119. ft = cake_config_besteffort(sch);
  2120. break;
  2121. case CAKE_DIFFSERV_PRECEDENCE:
  2122. ft = cake_config_precedence(sch);
  2123. break;
  2124. case CAKE_DIFFSERV_DIFFSERV8:
  2125. ft = cake_config_diffserv8(sch);
  2126. break;
  2127. case CAKE_DIFFSERV_DIFFSERV4:
  2128. ft = cake_config_diffserv4(sch);
  2129. break;
  2130. case CAKE_DIFFSERV_DIFFSERV3:
  2131. default:
  2132. ft = cake_config_diffserv3(sch);
  2133. break;
  2134. }
  2135. for (c = q->tin_cnt; c < CAKE_MAX_TINS; c++) {
  2136. cake_clear_tin(sch, c);
  2137. q->tins[c].cparams.mtu_time = q->tins[ft].cparams.mtu_time;
  2138. }
  2139. q->rate_ns = q->tins[ft].tin_rate_ns;
  2140. q->rate_shft = q->tins[ft].tin_rate_shft;
  2141. if (q->buffer_config_limit) {
  2142. q->buffer_limit = q->buffer_config_limit;
  2143. } else if (q->rate_bps) {
  2144. u64 t = q->rate_bps * q->interval;
  2145. do_div(t, USEC_PER_SEC / 4);
  2146. q->buffer_limit = max_t(u32, t, 4U << 20);
  2147. } else {
  2148. q->buffer_limit = ~0;
  2149. }
  2150. sch->flags &= ~TCQ_F_CAN_BYPASS;
  2151. q->buffer_limit = min(q->buffer_limit,
  2152. max(sch->limit * psched_mtu(qdisc_dev(sch)),
  2153. q->buffer_config_limit));
  2154. }
  2155. static int cake_change(struct Qdisc *sch, struct nlattr *opt,
  2156. struct netlink_ext_ack *extack)
  2157. {
  2158. struct cake_sched_data *q = qdisc_priv(sch);
  2159. struct nlattr *tb[TCA_CAKE_MAX + 1];
  2160. int err;
  2161. if (!opt)
  2162. return -EINVAL;
  2163. err = nla_parse_nested_deprecated(tb, TCA_CAKE_MAX, opt, cake_policy,
  2164. extack);
  2165. if (err < 0)
  2166. return err;
  2167. if (tb[TCA_CAKE_NAT]) {
  2168. #if IS_ENABLED(CONFIG_NF_CONNTRACK)
  2169. q->flow_mode &= ~CAKE_FLOW_NAT_FLAG;
  2170. q->flow_mode |= CAKE_FLOW_NAT_FLAG *
  2171. !!nla_get_u32(tb[TCA_CAKE_NAT]);
  2172. #else
  2173. NL_SET_ERR_MSG_ATTR(extack, tb[TCA_CAKE_NAT],
  2174. "No conntrack support in kernel");
  2175. return -EOPNOTSUPP;
  2176. #endif
  2177. }
  2178. if (tb[TCA_CAKE_BASE_RATE64])
  2179. q->rate_bps = nla_get_u64(tb[TCA_CAKE_BASE_RATE64]);
  2180. if (tb[TCA_CAKE_DIFFSERV_MODE])
  2181. q->tin_mode = nla_get_u32(tb[TCA_CAKE_DIFFSERV_MODE]);
  2182. if (tb[TCA_CAKE_WASH]) {
  2183. if (!!nla_get_u32(tb[TCA_CAKE_WASH]))
  2184. q->rate_flags |= CAKE_FLAG_WASH;
  2185. else
  2186. q->rate_flags &= ~CAKE_FLAG_WASH;
  2187. }
  2188. if (tb[TCA_CAKE_FLOW_MODE])
  2189. q->flow_mode = ((q->flow_mode & CAKE_FLOW_NAT_FLAG) |
  2190. (nla_get_u32(tb[TCA_CAKE_FLOW_MODE]) &
  2191. CAKE_FLOW_MASK));
  2192. if (tb[TCA_CAKE_ATM])
  2193. q->atm_mode = nla_get_u32(tb[TCA_CAKE_ATM]);
  2194. if (tb[TCA_CAKE_OVERHEAD]) {
  2195. q->rate_overhead = nla_get_s32(tb[TCA_CAKE_OVERHEAD]);
  2196. q->rate_flags |= CAKE_FLAG_OVERHEAD;
  2197. q->max_netlen = 0;
  2198. q->max_adjlen = 0;
  2199. q->min_netlen = ~0;
  2200. q->min_adjlen = ~0;
  2201. }
  2202. if (tb[TCA_CAKE_RAW]) {
  2203. q->rate_flags &= ~CAKE_FLAG_OVERHEAD;
  2204. q->max_netlen = 0;
  2205. q->max_adjlen = 0;
  2206. q->min_netlen = ~0;
  2207. q->min_adjlen = ~0;
  2208. }
  2209. if (tb[TCA_CAKE_MPU])
  2210. q->rate_mpu = nla_get_u32(tb[TCA_CAKE_MPU]);
  2211. if (tb[TCA_CAKE_RTT]) {
  2212. q->interval = nla_get_u32(tb[TCA_CAKE_RTT]);
  2213. if (!q->interval)
  2214. q->interval = 1;
  2215. }
  2216. if (tb[TCA_CAKE_TARGET]) {
  2217. q->target = nla_get_u32(tb[TCA_CAKE_TARGET]);
  2218. if (!q->target)
  2219. q->target = 1;
  2220. }
  2221. if (tb[TCA_CAKE_AUTORATE]) {
  2222. if (!!nla_get_u32(tb[TCA_CAKE_AUTORATE]))
  2223. q->rate_flags |= CAKE_FLAG_AUTORATE_INGRESS;
  2224. else
  2225. q->rate_flags &= ~CAKE_FLAG_AUTORATE_INGRESS;
  2226. }
  2227. if (tb[TCA_CAKE_INGRESS]) {
  2228. if (!!nla_get_u32(tb[TCA_CAKE_INGRESS]))
  2229. q->rate_flags |= CAKE_FLAG_INGRESS;
  2230. else
  2231. q->rate_flags &= ~CAKE_FLAG_INGRESS;
  2232. }
  2233. if (tb[TCA_CAKE_ACK_FILTER])
  2234. q->ack_filter = nla_get_u32(tb[TCA_CAKE_ACK_FILTER]);
  2235. if (tb[TCA_CAKE_MEMORY])
  2236. q->buffer_config_limit = nla_get_u32(tb[TCA_CAKE_MEMORY]);
  2237. if (tb[TCA_CAKE_SPLIT_GSO]) {
  2238. if (!!nla_get_u32(tb[TCA_CAKE_SPLIT_GSO]))
  2239. q->rate_flags |= CAKE_FLAG_SPLIT_GSO;
  2240. else
  2241. q->rate_flags &= ~CAKE_FLAG_SPLIT_GSO;
  2242. }
  2243. if (tb[TCA_CAKE_FWMARK]) {
  2244. q->fwmark_mask = nla_get_u32(tb[TCA_CAKE_FWMARK]);
  2245. q->fwmark_shft = q->fwmark_mask ? __ffs(q->fwmark_mask) : 0;
  2246. }
  2247. if (q->tins) {
  2248. sch_tree_lock(sch);
  2249. cake_reconfigure(sch);
  2250. sch_tree_unlock(sch);
  2251. }
  2252. return 0;
  2253. }
  2254. static void cake_destroy(struct Qdisc *sch)
  2255. {
  2256. struct cake_sched_data *q = qdisc_priv(sch);
  2257. qdisc_watchdog_cancel(&q->watchdog);
  2258. tcf_block_put(q->block);
  2259. kvfree(q->tins);
  2260. }
  2261. static int cake_init(struct Qdisc *sch, struct nlattr *opt,
  2262. struct netlink_ext_ack *extack)
  2263. {
  2264. struct cake_sched_data *q = qdisc_priv(sch);
  2265. int i, j, err;
  2266. sch->limit = 10240;
  2267. q->tin_mode = CAKE_DIFFSERV_DIFFSERV3;
  2268. q->flow_mode = CAKE_FLOW_TRIPLE;
  2269. q->rate_bps = 0; /* unlimited by default */
  2270. q->interval = 100000; /* 100ms default */
  2271. q->target = 5000; /* 5ms: codel RFC argues
  2272. * for 5 to 10% of interval
  2273. */
  2274. q->rate_flags |= CAKE_FLAG_SPLIT_GSO;
  2275. q->cur_tin = 0;
  2276. q->cur_flow = 0;
  2277. qdisc_watchdog_init(&q->watchdog, sch);
  2278. if (opt) {
  2279. err = cake_change(sch, opt, extack);
  2280. if (err)
  2281. return err;
  2282. }
  2283. err = tcf_block_get(&q->block, &q->filter_list, sch, extack);
  2284. if (err)
  2285. return err;
  2286. quantum_div[0] = ~0;
  2287. for (i = 1; i <= CAKE_QUEUES; i++)
  2288. quantum_div[i] = 65535 / i;
  2289. q->tins = kvcalloc(CAKE_MAX_TINS, sizeof(struct cake_tin_data),
  2290. GFP_KERNEL);
  2291. if (!q->tins)
  2292. return -ENOMEM;
  2293. for (i = 0; i < CAKE_MAX_TINS; i++) {
  2294. struct cake_tin_data *b = q->tins + i;
  2295. INIT_LIST_HEAD(&b->new_flows);
  2296. INIT_LIST_HEAD(&b->old_flows);
  2297. INIT_LIST_HEAD(&b->decaying_flows);
  2298. b->sparse_flow_count = 0;
  2299. b->bulk_flow_count = 0;
  2300. b->decaying_flow_count = 0;
  2301. for (j = 0; j < CAKE_QUEUES; j++) {
  2302. struct cake_flow *flow = b->flows + j;
  2303. u32 k = j * CAKE_MAX_TINS + i;
  2304. INIT_LIST_HEAD(&flow->flowchain);
  2305. cobalt_vars_init(&flow->cvars);
  2306. q->overflow_heap[k].t = i;
  2307. q->overflow_heap[k].b = j;
  2308. b->overflow_idx[j] = k;
  2309. }
  2310. }
  2311. cake_reconfigure(sch);
  2312. q->avg_peak_bandwidth = q->rate_bps;
  2313. q->min_netlen = ~0;
  2314. q->min_adjlen = ~0;
  2315. return 0;
  2316. }
  2317. static int cake_dump(struct Qdisc *sch, struct sk_buff *skb)
  2318. {
  2319. struct cake_sched_data *q = qdisc_priv(sch);
  2320. struct nlattr *opts;
  2321. opts = nla_nest_start_noflag(skb, TCA_OPTIONS);
  2322. if (!opts)
  2323. goto nla_put_failure;
  2324. if (nla_put_u64_64bit(skb, TCA_CAKE_BASE_RATE64, q->rate_bps,
  2325. TCA_CAKE_PAD))
  2326. goto nla_put_failure;
  2327. if (nla_put_u32(skb, TCA_CAKE_FLOW_MODE,
  2328. q->flow_mode & CAKE_FLOW_MASK))
  2329. goto nla_put_failure;
  2330. if (nla_put_u32(skb, TCA_CAKE_RTT, q->interval))
  2331. goto nla_put_failure;
  2332. if (nla_put_u32(skb, TCA_CAKE_TARGET, q->target))
  2333. goto nla_put_failure;
  2334. if (nla_put_u32(skb, TCA_CAKE_MEMORY, q->buffer_config_limit))
  2335. goto nla_put_failure;
  2336. if (nla_put_u32(skb, TCA_CAKE_AUTORATE,
  2337. !!(q->rate_flags & CAKE_FLAG_AUTORATE_INGRESS)))
  2338. goto nla_put_failure;
  2339. if (nla_put_u32(skb, TCA_CAKE_INGRESS,
  2340. !!(q->rate_flags & CAKE_FLAG_INGRESS)))
  2341. goto nla_put_failure;
  2342. if (nla_put_u32(skb, TCA_CAKE_ACK_FILTER, q->ack_filter))
  2343. goto nla_put_failure;
  2344. if (nla_put_u32(skb, TCA_CAKE_NAT,
  2345. !!(q->flow_mode & CAKE_FLOW_NAT_FLAG)))
  2346. goto nla_put_failure;
  2347. if (nla_put_u32(skb, TCA_CAKE_DIFFSERV_MODE, q->tin_mode))
  2348. goto nla_put_failure;
  2349. if (nla_put_u32(skb, TCA_CAKE_WASH,
  2350. !!(q->rate_flags & CAKE_FLAG_WASH)))
  2351. goto nla_put_failure;
  2352. if (nla_put_u32(skb, TCA_CAKE_OVERHEAD, q->rate_overhead))
  2353. goto nla_put_failure;
  2354. if (!(q->rate_flags & CAKE_FLAG_OVERHEAD))
  2355. if (nla_put_u32(skb, TCA_CAKE_RAW, 0))
  2356. goto nla_put_failure;
  2357. if (nla_put_u32(skb, TCA_CAKE_ATM, q->atm_mode))
  2358. goto nla_put_failure;
  2359. if (nla_put_u32(skb, TCA_CAKE_MPU, q->rate_mpu))
  2360. goto nla_put_failure;
  2361. if (nla_put_u32(skb, TCA_CAKE_SPLIT_GSO,
  2362. !!(q->rate_flags & CAKE_FLAG_SPLIT_GSO)))
  2363. goto nla_put_failure;
  2364. if (nla_put_u32(skb, TCA_CAKE_FWMARK, q->fwmark_mask))
  2365. goto nla_put_failure;
  2366. return nla_nest_end(skb, opts);
  2367. nla_put_failure:
  2368. return -1;
  2369. }
  2370. static int cake_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
  2371. {
  2372. struct nlattr *stats = nla_nest_start_noflag(d->skb, TCA_STATS_APP);
  2373. struct cake_sched_data *q = qdisc_priv(sch);
  2374. struct nlattr *tstats, *ts;
  2375. int i;
  2376. if (!stats)
  2377. return -1;
  2378. #define PUT_STAT_U32(attr, data) do { \
  2379. if (nla_put_u32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \
  2380. goto nla_put_failure; \
  2381. } while (0)
  2382. #define PUT_STAT_U64(attr, data) do { \
  2383. if (nla_put_u64_64bit(d->skb, TCA_CAKE_STATS_ ## attr, \
  2384. data, TCA_CAKE_STATS_PAD)) \
  2385. goto nla_put_failure; \
  2386. } while (0)
  2387. PUT_STAT_U64(CAPACITY_ESTIMATE64, q->avg_peak_bandwidth);
  2388. PUT_STAT_U32(MEMORY_LIMIT, q->buffer_limit);
  2389. PUT_STAT_U32(MEMORY_USED, q->buffer_max_used);
  2390. PUT_STAT_U32(AVG_NETOFF, ((q->avg_netoff + 0x8000) >> 16));
  2391. PUT_STAT_U32(MAX_NETLEN, q->max_netlen);
  2392. PUT_STAT_U32(MAX_ADJLEN, q->max_adjlen);
  2393. PUT_STAT_U32(MIN_NETLEN, q->min_netlen);
  2394. PUT_STAT_U32(MIN_ADJLEN, q->min_adjlen);
  2395. #undef PUT_STAT_U32
  2396. #undef PUT_STAT_U64
  2397. tstats = nla_nest_start_noflag(d->skb, TCA_CAKE_STATS_TIN_STATS);
  2398. if (!tstats)
  2399. goto nla_put_failure;
  2400. #define PUT_TSTAT_U32(attr, data) do { \
  2401. if (nla_put_u32(d->skb, TCA_CAKE_TIN_STATS_ ## attr, data)) \
  2402. goto nla_put_failure; \
  2403. } while (0)
  2404. #define PUT_TSTAT_U64(attr, data) do { \
  2405. if (nla_put_u64_64bit(d->skb, TCA_CAKE_TIN_STATS_ ## attr, \
  2406. data, TCA_CAKE_TIN_STATS_PAD)) \
  2407. goto nla_put_failure; \
  2408. } while (0)
  2409. for (i = 0; i < q->tin_cnt; i++) {
  2410. struct cake_tin_data *b = &q->tins[q->tin_order[i]];
  2411. ts = nla_nest_start_noflag(d->skb, i + 1);
  2412. if (!ts)
  2413. goto nla_put_failure;
  2414. PUT_TSTAT_U64(THRESHOLD_RATE64, b->tin_rate_bps);
  2415. PUT_TSTAT_U64(SENT_BYTES64, b->bytes);
  2416. PUT_TSTAT_U32(BACKLOG_BYTES, b->tin_backlog);
  2417. PUT_TSTAT_U32(TARGET_US,
  2418. ktime_to_us(ns_to_ktime(b->cparams.target)));
  2419. PUT_TSTAT_U32(INTERVAL_US,
  2420. ktime_to_us(ns_to_ktime(b->cparams.interval)));
  2421. PUT_TSTAT_U32(SENT_PACKETS, b->packets);
  2422. PUT_TSTAT_U32(DROPPED_PACKETS, b->tin_dropped);
  2423. PUT_TSTAT_U32(ECN_MARKED_PACKETS, b->tin_ecn_mark);
  2424. PUT_TSTAT_U32(ACKS_DROPPED_PACKETS, b->ack_drops);
  2425. PUT_TSTAT_U32(PEAK_DELAY_US,
  2426. ktime_to_us(ns_to_ktime(b->peak_delay)));
  2427. PUT_TSTAT_U32(AVG_DELAY_US,
  2428. ktime_to_us(ns_to_ktime(b->avge_delay)));
  2429. PUT_TSTAT_U32(BASE_DELAY_US,
  2430. ktime_to_us(ns_to_ktime(b->base_delay)));
  2431. PUT_TSTAT_U32(WAY_INDIRECT_HITS, b->way_hits);
  2432. PUT_TSTAT_U32(WAY_MISSES, b->way_misses);
  2433. PUT_TSTAT_U32(WAY_COLLISIONS, b->way_collisions);
  2434. PUT_TSTAT_U32(SPARSE_FLOWS, b->sparse_flow_count +
  2435. b->decaying_flow_count);
  2436. PUT_TSTAT_U32(BULK_FLOWS, b->bulk_flow_count);
  2437. PUT_TSTAT_U32(UNRESPONSIVE_FLOWS, b->unresponsive_flow_count);
  2438. PUT_TSTAT_U32(MAX_SKBLEN, b->max_skblen);
  2439. PUT_TSTAT_U32(FLOW_QUANTUM, b->flow_quantum);
  2440. nla_nest_end(d->skb, ts);
  2441. }
  2442. #undef PUT_TSTAT_U32
  2443. #undef PUT_TSTAT_U64
  2444. nla_nest_end(d->skb, tstats);
  2445. return nla_nest_end(d->skb, stats);
  2446. nla_put_failure:
  2447. nla_nest_cancel(d->skb, stats);
  2448. return -1;
  2449. }
  2450. static struct Qdisc *cake_leaf(struct Qdisc *sch, unsigned long arg)
  2451. {
  2452. return NULL;
  2453. }
  2454. static unsigned long cake_find(struct Qdisc *sch, u32 classid)
  2455. {
  2456. return 0;
  2457. }
  2458. static unsigned long cake_bind(struct Qdisc *sch, unsigned long parent,
  2459. u32 classid)
  2460. {
  2461. return 0;
  2462. }
  2463. static void cake_unbind(struct Qdisc *q, unsigned long cl)
  2464. {
  2465. }
  2466. static struct tcf_block *cake_tcf_block(struct Qdisc *sch, unsigned long cl,
  2467. struct netlink_ext_ack *extack)
  2468. {
  2469. struct cake_sched_data *q = qdisc_priv(sch);
  2470. if (cl)
  2471. return NULL;
  2472. return q->block;
  2473. }
  2474. static int cake_dump_class(struct Qdisc *sch, unsigned long cl,
  2475. struct sk_buff *skb, struct tcmsg *tcm)
  2476. {
  2477. tcm->tcm_handle |= TC_H_MIN(cl);
  2478. return 0;
  2479. }
  2480. static int cake_dump_class_stats(struct Qdisc *sch, unsigned long cl,
  2481. struct gnet_dump *d)
  2482. {
  2483. struct cake_sched_data *q = qdisc_priv(sch);
  2484. const struct cake_flow *flow = NULL;
  2485. struct gnet_stats_queue qs = { 0 };
  2486. struct nlattr *stats;
  2487. u32 idx = cl - 1;
  2488. if (idx < CAKE_QUEUES * q->tin_cnt) {
  2489. const struct cake_tin_data *b = \
  2490. &q->tins[q->tin_order[idx / CAKE_QUEUES]];
  2491. const struct sk_buff *skb;
  2492. flow = &b->flows[idx % CAKE_QUEUES];
  2493. if (flow->head) {
  2494. sch_tree_lock(sch);
  2495. skb = flow->head;
  2496. while (skb) {
  2497. qs.qlen++;
  2498. skb = skb->next;
  2499. }
  2500. sch_tree_unlock(sch);
  2501. }
  2502. qs.backlog = b->backlogs[idx % CAKE_QUEUES];
  2503. qs.drops = flow->dropped;
  2504. }
  2505. if (gnet_stats_copy_queue(d, NULL, &qs, qs.qlen) < 0)
  2506. return -1;
  2507. if (flow) {
  2508. ktime_t now = ktime_get();
  2509. stats = nla_nest_start_noflag(d->skb, TCA_STATS_APP);
  2510. if (!stats)
  2511. return -1;
  2512. #define PUT_STAT_U32(attr, data) do { \
  2513. if (nla_put_u32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \
  2514. goto nla_put_failure; \
  2515. } while (0)
  2516. #define PUT_STAT_S32(attr, data) do { \
  2517. if (nla_put_s32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \
  2518. goto nla_put_failure; \
  2519. } while (0)
  2520. PUT_STAT_S32(DEFICIT, flow->deficit);
  2521. PUT_STAT_U32(DROPPING, flow->cvars.dropping);
  2522. PUT_STAT_U32(COBALT_COUNT, flow->cvars.count);
  2523. PUT_STAT_U32(P_DROP, flow->cvars.p_drop);
  2524. if (flow->cvars.p_drop) {
  2525. PUT_STAT_S32(BLUE_TIMER_US,
  2526. ktime_to_us(
  2527. ktime_sub(now,
  2528. flow->cvars.blue_timer)));
  2529. }
  2530. if (flow->cvars.dropping) {
  2531. PUT_STAT_S32(DROP_NEXT_US,
  2532. ktime_to_us(
  2533. ktime_sub(now,
  2534. flow->cvars.drop_next)));
  2535. }
  2536. if (nla_nest_end(d->skb, stats) < 0)
  2537. return -1;
  2538. }
  2539. return 0;
  2540. nla_put_failure:
  2541. nla_nest_cancel(d->skb, stats);
  2542. return -1;
  2543. }
  2544. static void cake_walk(struct Qdisc *sch, struct qdisc_walker *arg)
  2545. {
  2546. struct cake_sched_data *q = qdisc_priv(sch);
  2547. unsigned int i, j;
  2548. if (arg->stop)
  2549. return;
  2550. for (i = 0; i < q->tin_cnt; i++) {
  2551. struct cake_tin_data *b = &q->tins[q->tin_order[i]];
  2552. for (j = 0; j < CAKE_QUEUES; j++) {
  2553. if (list_empty(&b->flows[j].flowchain) ||
  2554. arg->count < arg->skip) {
  2555. arg->count++;
  2556. continue;
  2557. }
  2558. if (arg->fn(sch, i * CAKE_QUEUES + j + 1, arg) < 0) {
  2559. arg->stop = 1;
  2560. break;
  2561. }
  2562. arg->count++;
  2563. }
  2564. }
  2565. }
  2566. static const struct Qdisc_class_ops cake_class_ops = {
  2567. .leaf = cake_leaf,
  2568. .find = cake_find,
  2569. .tcf_block = cake_tcf_block,
  2570. .bind_tcf = cake_bind,
  2571. .unbind_tcf = cake_unbind,
  2572. .dump = cake_dump_class,
  2573. .dump_stats = cake_dump_class_stats,
  2574. .walk = cake_walk,
  2575. };
  2576. static struct Qdisc_ops cake_qdisc_ops __read_mostly = {
  2577. .cl_ops = &cake_class_ops,
  2578. .id = "cake",
  2579. .priv_size = sizeof(struct cake_sched_data),
  2580. .enqueue = cake_enqueue,
  2581. .dequeue = cake_dequeue,
  2582. .peek = qdisc_peek_dequeued,
  2583. .init = cake_init,
  2584. .reset = cake_reset,
  2585. .destroy = cake_destroy,
  2586. .change = cake_change,
  2587. .dump = cake_dump,
  2588. .dump_stats = cake_dump_stats,
  2589. .owner = THIS_MODULE,
  2590. };
  2591. static int __init cake_module_init(void)
  2592. {
  2593. return register_qdisc(&cake_qdisc_ops);
  2594. }
  2595. static void __exit cake_module_exit(void)
  2596. {
  2597. unregister_qdisc(&cake_qdisc_ops);
  2598. }
  2599. module_init(cake_module_init)
  2600. module_exit(cake_module_exit)
  2601. MODULE_AUTHOR("Jonathan Morton");
  2602. MODULE_LICENSE("Dual BSD/GPL");
  2603. MODULE_DESCRIPTION("The CAKE shaper.");