sch_cake.c 77 KB

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