deadline.c 79 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Deadline Scheduling Class (SCHED_DEADLINE)
  4. *
  5. * Earliest Deadline First (EDF) + Constant Bandwidth Server (CBS).
  6. *
  7. * Tasks that periodically executes their instances for less than their
  8. * runtime won't miss any of their deadlines.
  9. * Tasks that are not periodic or sporadic or that tries to execute more
  10. * than their reserved bandwidth will be slowed down (and may potentially
  11. * miss some of their deadlines), and won't affect any other task.
  12. *
  13. * Copyright (C) 2012 Dario Faggioli <raistlin@linux.it>,
  14. * Juri Lelli <juri.lelli@gmail.com>,
  15. * Michael Trimarchi <michael@amarulasolutions.com>,
  16. * Fabio Checconi <fchecconi@gmail.com>
  17. */
  18. #include "sched.h"
  19. #include "pelt.h"
  20. struct dl_bandwidth def_dl_bandwidth;
  21. static inline struct task_struct *dl_task_of(struct sched_dl_entity *dl_se)
  22. {
  23. return container_of(dl_se, struct task_struct, dl);
  24. }
  25. static inline struct rq *rq_of_dl_rq(struct dl_rq *dl_rq)
  26. {
  27. return container_of(dl_rq, struct rq, dl);
  28. }
  29. static inline struct dl_rq *dl_rq_of_se(struct sched_dl_entity *dl_se)
  30. {
  31. struct task_struct *p = dl_task_of(dl_se);
  32. struct rq *rq = task_rq(p);
  33. return &rq->dl;
  34. }
  35. static inline int on_dl_rq(struct sched_dl_entity *dl_se)
  36. {
  37. return !RB_EMPTY_NODE(&dl_se->rb_node);
  38. }
  39. #ifdef CONFIG_RT_MUTEXES
  40. static inline struct sched_dl_entity *pi_of(struct sched_dl_entity *dl_se)
  41. {
  42. return dl_se->pi_se;
  43. }
  44. static inline bool is_dl_boosted(struct sched_dl_entity *dl_se)
  45. {
  46. return pi_of(dl_se) != dl_se;
  47. }
  48. #else
  49. static inline struct sched_dl_entity *pi_of(struct sched_dl_entity *dl_se)
  50. {
  51. return dl_se;
  52. }
  53. static inline bool is_dl_boosted(struct sched_dl_entity *dl_se)
  54. {
  55. return false;
  56. }
  57. #endif
  58. #ifdef CONFIG_SMP
  59. static inline struct dl_bw *dl_bw_of(int i)
  60. {
  61. RCU_LOCKDEP_WARN(!rcu_read_lock_sched_held(),
  62. "sched RCU must be held");
  63. return &cpu_rq(i)->rd->dl_bw;
  64. }
  65. static inline int dl_bw_cpus(int i)
  66. {
  67. struct root_domain *rd = cpu_rq(i)->rd;
  68. int cpus;
  69. RCU_LOCKDEP_WARN(!rcu_read_lock_sched_held(),
  70. "sched RCU must be held");
  71. if (cpumask_subset(rd->span, cpu_active_mask))
  72. return cpumask_weight(rd->span);
  73. cpus = 0;
  74. for_each_cpu_and(i, rd->span, cpu_active_mask)
  75. cpus++;
  76. return cpus;
  77. }
  78. static inline unsigned long __dl_bw_capacity(int i)
  79. {
  80. struct root_domain *rd = cpu_rq(i)->rd;
  81. unsigned long cap = 0;
  82. RCU_LOCKDEP_WARN(!rcu_read_lock_sched_held(),
  83. "sched RCU must be held");
  84. for_each_cpu_and(i, rd->span, cpu_active_mask)
  85. cap += capacity_orig_of(i);
  86. return cap;
  87. }
  88. /*
  89. * XXX Fix: If 'rq->rd == def_root_domain' perform AC against capacity
  90. * of the CPU the task is running on rather rd's \Sum CPU capacity.
  91. */
  92. static inline unsigned long dl_bw_capacity(int i)
  93. {
  94. if (!static_branch_unlikely(&sched_asym_cpucapacity) &&
  95. capacity_orig_of(i) == SCHED_CAPACITY_SCALE) {
  96. return dl_bw_cpus(i) << SCHED_CAPACITY_SHIFT;
  97. } else {
  98. return __dl_bw_capacity(i);
  99. }
  100. }
  101. #else
  102. static inline struct dl_bw *dl_bw_of(int i)
  103. {
  104. return &cpu_rq(i)->dl.dl_bw;
  105. }
  106. static inline int dl_bw_cpus(int i)
  107. {
  108. return 1;
  109. }
  110. static inline unsigned long dl_bw_capacity(int i)
  111. {
  112. return SCHED_CAPACITY_SCALE;
  113. }
  114. #endif
  115. static inline
  116. void __add_running_bw(u64 dl_bw, struct dl_rq *dl_rq)
  117. {
  118. u64 old = dl_rq->running_bw;
  119. lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
  120. dl_rq->running_bw += dl_bw;
  121. SCHED_WARN_ON(dl_rq->running_bw < old); /* overflow */
  122. SCHED_WARN_ON(dl_rq->running_bw > dl_rq->this_bw);
  123. /* kick cpufreq (see the comment in kernel/sched/sched.h). */
  124. cpufreq_update_util(rq_of_dl_rq(dl_rq), 0);
  125. }
  126. static inline
  127. void __sub_running_bw(u64 dl_bw, struct dl_rq *dl_rq)
  128. {
  129. u64 old = dl_rq->running_bw;
  130. lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
  131. dl_rq->running_bw -= dl_bw;
  132. SCHED_WARN_ON(dl_rq->running_bw > old); /* underflow */
  133. if (dl_rq->running_bw > old)
  134. dl_rq->running_bw = 0;
  135. /* kick cpufreq (see the comment in kernel/sched/sched.h). */
  136. cpufreq_update_util(rq_of_dl_rq(dl_rq), 0);
  137. }
  138. static inline
  139. void __add_rq_bw(u64 dl_bw, struct dl_rq *dl_rq)
  140. {
  141. u64 old = dl_rq->this_bw;
  142. lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
  143. dl_rq->this_bw += dl_bw;
  144. SCHED_WARN_ON(dl_rq->this_bw < old); /* overflow */
  145. }
  146. static inline
  147. void __sub_rq_bw(u64 dl_bw, struct dl_rq *dl_rq)
  148. {
  149. u64 old = dl_rq->this_bw;
  150. lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
  151. dl_rq->this_bw -= dl_bw;
  152. SCHED_WARN_ON(dl_rq->this_bw > old); /* underflow */
  153. if (dl_rq->this_bw > old)
  154. dl_rq->this_bw = 0;
  155. SCHED_WARN_ON(dl_rq->running_bw > dl_rq->this_bw);
  156. }
  157. static inline
  158. void add_rq_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
  159. {
  160. if (!dl_entity_is_special(dl_se))
  161. __add_rq_bw(dl_se->dl_bw, dl_rq);
  162. }
  163. static inline
  164. void sub_rq_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
  165. {
  166. if (!dl_entity_is_special(dl_se))
  167. __sub_rq_bw(dl_se->dl_bw, dl_rq);
  168. }
  169. static inline
  170. void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
  171. {
  172. if (!dl_entity_is_special(dl_se))
  173. __add_running_bw(dl_se->dl_bw, dl_rq);
  174. }
  175. static inline
  176. void sub_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
  177. {
  178. if (!dl_entity_is_special(dl_se))
  179. __sub_running_bw(dl_se->dl_bw, dl_rq);
  180. }
  181. static void dl_change_utilization(struct task_struct *p, u64 new_bw)
  182. {
  183. struct rq *rq;
  184. BUG_ON(p->dl.flags & SCHED_FLAG_SUGOV);
  185. if (task_on_rq_queued(p))
  186. return;
  187. rq = task_rq(p);
  188. if (p->dl.dl_non_contending) {
  189. sub_running_bw(&p->dl, &rq->dl);
  190. p->dl.dl_non_contending = 0;
  191. /*
  192. * If the timer handler is currently running and the
  193. * timer cannot be cancelled, inactive_task_timer()
  194. * will see that dl_not_contending is not set, and
  195. * will not touch the rq's active utilization,
  196. * so we are still safe.
  197. */
  198. if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1)
  199. put_task_struct(p);
  200. }
  201. __sub_rq_bw(p->dl.dl_bw, &rq->dl);
  202. __add_rq_bw(new_bw, &rq->dl);
  203. }
  204. /*
  205. * The utilization of a task cannot be immediately removed from
  206. * the rq active utilization (running_bw) when the task blocks.
  207. * Instead, we have to wait for the so called "0-lag time".
  208. *
  209. * If a task blocks before the "0-lag time", a timer (the inactive
  210. * timer) is armed, and running_bw is decreased when the timer
  211. * fires.
  212. *
  213. * If the task wakes up again before the inactive timer fires,
  214. * the timer is cancelled, whereas if the task wakes up after the
  215. * inactive timer fired (and running_bw has been decreased) the
  216. * task's utilization has to be added to running_bw again.
  217. * A flag in the deadline scheduling entity (dl_non_contending)
  218. * is used to avoid race conditions between the inactive timer handler
  219. * and task wakeups.
  220. *
  221. * The following diagram shows how running_bw is updated. A task is
  222. * "ACTIVE" when its utilization contributes to running_bw; an
  223. * "ACTIVE contending" task is in the TASK_RUNNING state, while an
  224. * "ACTIVE non contending" task is a blocked task for which the "0-lag time"
  225. * has not passed yet. An "INACTIVE" task is a task for which the "0-lag"
  226. * time already passed, which does not contribute to running_bw anymore.
  227. * +------------------+
  228. * wakeup | ACTIVE |
  229. * +------------------>+ contending |
  230. * | add_running_bw | |
  231. * | +----+------+------+
  232. * | | ^
  233. * | dequeue | |
  234. * +--------+-------+ | |
  235. * | | t >= 0-lag | | wakeup
  236. * | INACTIVE |<---------------+ |
  237. * | | sub_running_bw | |
  238. * +--------+-------+ | |
  239. * ^ | |
  240. * | t < 0-lag | |
  241. * | | |
  242. * | V |
  243. * | +----+------+------+
  244. * | sub_running_bw | ACTIVE |
  245. * +-------------------+ |
  246. * inactive timer | non contending |
  247. * fired +------------------+
  248. *
  249. * The task_non_contending() function is invoked when a task
  250. * blocks, and checks if the 0-lag time already passed or
  251. * not (in the first case, it directly updates running_bw;
  252. * in the second case, it arms the inactive timer).
  253. *
  254. * The task_contending() function is invoked when a task wakes
  255. * up, and checks if the task is still in the "ACTIVE non contending"
  256. * state or not (in the second case, it updates running_bw).
  257. */
  258. static void task_non_contending(struct task_struct *p)
  259. {
  260. struct sched_dl_entity *dl_se = &p->dl;
  261. struct hrtimer *timer = &dl_se->inactive_timer;
  262. struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
  263. struct rq *rq = rq_of_dl_rq(dl_rq);
  264. s64 zerolag_time;
  265. /*
  266. * If this is a non-deadline task that has been boosted,
  267. * do nothing
  268. */
  269. if (dl_se->dl_runtime == 0)
  270. return;
  271. if (dl_entity_is_special(dl_se))
  272. return;
  273. WARN_ON(dl_se->dl_non_contending);
  274. zerolag_time = dl_se->deadline -
  275. div64_long((dl_se->runtime * dl_se->dl_period),
  276. dl_se->dl_runtime);
  277. /*
  278. * Using relative times instead of the absolute "0-lag time"
  279. * allows to simplify the code
  280. */
  281. zerolag_time -= rq_clock(rq);
  282. /*
  283. * If the "0-lag time" already passed, decrease the active
  284. * utilization now, instead of starting a timer
  285. */
  286. if ((zerolag_time < 0) || hrtimer_active(&dl_se->inactive_timer)) {
  287. if (dl_task(p))
  288. sub_running_bw(dl_se, dl_rq);
  289. if (!dl_task(p) || p->state == TASK_DEAD) {
  290. struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
  291. if (p->state == TASK_DEAD)
  292. sub_rq_bw(&p->dl, &rq->dl);
  293. raw_spin_lock(&dl_b->lock);
  294. __dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p)));
  295. __dl_clear_params(p);
  296. raw_spin_unlock(&dl_b->lock);
  297. }
  298. return;
  299. }
  300. dl_se->dl_non_contending = 1;
  301. get_task_struct(p);
  302. hrtimer_start(timer, ns_to_ktime(zerolag_time), HRTIMER_MODE_REL_HARD);
  303. }
  304. static void task_contending(struct sched_dl_entity *dl_se, int flags)
  305. {
  306. struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
  307. /*
  308. * If this is a non-deadline task that has been boosted,
  309. * do nothing
  310. */
  311. if (dl_se->dl_runtime == 0)
  312. return;
  313. if (flags & ENQUEUE_MIGRATED)
  314. add_rq_bw(dl_se, dl_rq);
  315. if (dl_se->dl_non_contending) {
  316. dl_se->dl_non_contending = 0;
  317. /*
  318. * If the timer handler is currently running and the
  319. * timer cannot be cancelled, inactive_task_timer()
  320. * will see that dl_not_contending is not set, and
  321. * will not touch the rq's active utilization,
  322. * so we are still safe.
  323. */
  324. if (hrtimer_try_to_cancel(&dl_se->inactive_timer) == 1)
  325. put_task_struct(dl_task_of(dl_se));
  326. } else {
  327. /*
  328. * Since "dl_non_contending" is not set, the
  329. * task's utilization has already been removed from
  330. * active utilization (either when the task blocked,
  331. * when the "inactive timer" fired).
  332. * So, add it back.
  333. */
  334. add_running_bw(dl_se, dl_rq);
  335. }
  336. }
  337. static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)
  338. {
  339. struct sched_dl_entity *dl_se = &p->dl;
  340. return dl_rq->root.rb_leftmost == &dl_se->rb_node;
  341. }
  342. static void init_dl_rq_bw_ratio(struct dl_rq *dl_rq);
  343. void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime)
  344. {
  345. raw_spin_lock_init(&dl_b->dl_runtime_lock);
  346. dl_b->dl_period = period;
  347. dl_b->dl_runtime = runtime;
  348. }
  349. void init_dl_bw(struct dl_bw *dl_b)
  350. {
  351. raw_spin_lock_init(&dl_b->lock);
  352. raw_spin_lock(&def_dl_bandwidth.dl_runtime_lock);
  353. if (global_rt_runtime() == RUNTIME_INF)
  354. dl_b->bw = -1;
  355. else
  356. dl_b->bw = to_ratio(global_rt_period(), global_rt_runtime());
  357. raw_spin_unlock(&def_dl_bandwidth.dl_runtime_lock);
  358. dl_b->total_bw = 0;
  359. }
  360. void init_dl_rq(struct dl_rq *dl_rq)
  361. {
  362. dl_rq->root = RB_ROOT_CACHED;
  363. #ifdef CONFIG_SMP
  364. /* zero means no -deadline tasks */
  365. dl_rq->earliest_dl.curr = dl_rq->earliest_dl.next = 0;
  366. dl_rq->dl_nr_migratory = 0;
  367. dl_rq->overloaded = 0;
  368. dl_rq->pushable_dl_tasks_root = RB_ROOT_CACHED;
  369. #else
  370. init_dl_bw(&dl_rq->dl_bw);
  371. #endif
  372. dl_rq->running_bw = 0;
  373. dl_rq->this_bw = 0;
  374. init_dl_rq_bw_ratio(dl_rq);
  375. }
  376. #ifdef CONFIG_SMP
  377. static inline int dl_overloaded(struct rq *rq)
  378. {
  379. return atomic_read(&rq->rd->dlo_count);
  380. }
  381. static inline void dl_set_overload(struct rq *rq)
  382. {
  383. if (!rq->online)
  384. return;
  385. cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask);
  386. /*
  387. * Must be visible before the overload count is
  388. * set (as in sched_rt.c).
  389. *
  390. * Matched by the barrier in pull_dl_task().
  391. */
  392. smp_wmb();
  393. atomic_inc(&rq->rd->dlo_count);
  394. }
  395. static inline void dl_clear_overload(struct rq *rq)
  396. {
  397. if (!rq->online)
  398. return;
  399. atomic_dec(&rq->rd->dlo_count);
  400. cpumask_clear_cpu(rq->cpu, rq->rd->dlo_mask);
  401. }
  402. static void update_dl_migration(struct dl_rq *dl_rq)
  403. {
  404. if (dl_rq->dl_nr_migratory && dl_rq->dl_nr_running > 1) {
  405. if (!dl_rq->overloaded) {
  406. dl_set_overload(rq_of_dl_rq(dl_rq));
  407. dl_rq->overloaded = 1;
  408. }
  409. } else if (dl_rq->overloaded) {
  410. dl_clear_overload(rq_of_dl_rq(dl_rq));
  411. dl_rq->overloaded = 0;
  412. }
  413. }
  414. static void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
  415. {
  416. struct task_struct *p = dl_task_of(dl_se);
  417. if (p->nr_cpus_allowed > 1)
  418. dl_rq->dl_nr_migratory++;
  419. update_dl_migration(dl_rq);
  420. }
  421. static void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
  422. {
  423. struct task_struct *p = dl_task_of(dl_se);
  424. if (p->nr_cpus_allowed > 1)
  425. dl_rq->dl_nr_migratory--;
  426. update_dl_migration(dl_rq);
  427. }
  428. /*
  429. * The list of pushable -deadline task is not a plist, like in
  430. * sched_rt.c, it is an rb-tree with tasks ordered by deadline.
  431. */
  432. static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
  433. {
  434. struct dl_rq *dl_rq = &rq->dl;
  435. struct rb_node **link = &dl_rq->pushable_dl_tasks_root.rb_root.rb_node;
  436. struct rb_node *parent = NULL;
  437. struct task_struct *entry;
  438. bool leftmost = true;
  439. BUG_ON(!RB_EMPTY_NODE(&p->pushable_dl_tasks));
  440. while (*link) {
  441. parent = *link;
  442. entry = rb_entry(parent, struct task_struct,
  443. pushable_dl_tasks);
  444. if (dl_entity_preempt(&p->dl, &entry->dl))
  445. link = &parent->rb_left;
  446. else {
  447. link = &parent->rb_right;
  448. leftmost = false;
  449. }
  450. }
  451. if (leftmost)
  452. dl_rq->earliest_dl.next = p->dl.deadline;
  453. rb_link_node(&p->pushable_dl_tasks, parent, link);
  454. rb_insert_color_cached(&p->pushable_dl_tasks,
  455. &dl_rq->pushable_dl_tasks_root, leftmost);
  456. }
  457. static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
  458. {
  459. struct dl_rq *dl_rq = &rq->dl;
  460. if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
  461. return;
  462. if (dl_rq->pushable_dl_tasks_root.rb_leftmost == &p->pushable_dl_tasks) {
  463. struct rb_node *next_node;
  464. next_node = rb_next(&p->pushable_dl_tasks);
  465. if (next_node) {
  466. dl_rq->earliest_dl.next = rb_entry(next_node,
  467. struct task_struct, pushable_dl_tasks)->dl.deadline;
  468. }
  469. }
  470. rb_erase_cached(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
  471. RB_CLEAR_NODE(&p->pushable_dl_tasks);
  472. }
  473. static inline int has_pushable_dl_tasks(struct rq *rq)
  474. {
  475. return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root.rb_root);
  476. }
  477. static int push_dl_task(struct rq *rq);
  478. static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
  479. {
  480. return dl_task(prev);
  481. }
  482. static DEFINE_PER_CPU(struct callback_head, dl_push_head);
  483. static DEFINE_PER_CPU(struct callback_head, dl_pull_head);
  484. static void push_dl_tasks(struct rq *);
  485. static void pull_dl_task(struct rq *);
  486. static inline void deadline_queue_push_tasks(struct rq *rq)
  487. {
  488. if (!has_pushable_dl_tasks(rq))
  489. return;
  490. queue_balance_callback(rq, &per_cpu(dl_push_head, rq->cpu), push_dl_tasks);
  491. }
  492. static inline void deadline_queue_pull_task(struct rq *rq)
  493. {
  494. queue_balance_callback(rq, &per_cpu(dl_pull_head, rq->cpu), pull_dl_task);
  495. }
  496. static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq);
  497. static struct rq *dl_task_offline_migration(struct rq *rq, struct task_struct *p)
  498. {
  499. struct rq *later_rq = NULL;
  500. struct dl_bw *dl_b;
  501. later_rq = find_lock_later_rq(p, rq);
  502. if (!later_rq) {
  503. int cpu;
  504. /*
  505. * If we cannot preempt any rq, fall back to pick any
  506. * online CPU:
  507. */
  508. cpu = cpumask_any_and(cpu_active_mask, p->cpus_ptr);
  509. if (cpu >= nr_cpu_ids) {
  510. /*
  511. * Failed to find any suitable CPU.
  512. * The task will never come back!
  513. */
  514. BUG_ON(dl_bandwidth_enabled());
  515. /*
  516. * If admission control is disabled we
  517. * try a little harder to let the task
  518. * run.
  519. */
  520. cpu = cpumask_any(cpu_active_mask);
  521. }
  522. later_rq = cpu_rq(cpu);
  523. double_lock_balance(rq, later_rq);
  524. }
  525. if (p->dl.dl_non_contending || p->dl.dl_throttled) {
  526. /*
  527. * Inactive timer is armed (or callback is running, but
  528. * waiting for us to release rq locks). In any case, when it
  529. * will fire (or continue), it will see running_bw of this
  530. * task migrated to later_rq (and correctly handle it).
  531. */
  532. sub_running_bw(&p->dl, &rq->dl);
  533. sub_rq_bw(&p->dl, &rq->dl);
  534. add_rq_bw(&p->dl, &later_rq->dl);
  535. add_running_bw(&p->dl, &later_rq->dl);
  536. } else {
  537. sub_rq_bw(&p->dl, &rq->dl);
  538. add_rq_bw(&p->dl, &later_rq->dl);
  539. }
  540. /*
  541. * And we finally need to fixup root_domain(s) bandwidth accounting,
  542. * since p is still hanging out in the old (now moved to default) root
  543. * domain.
  544. */
  545. dl_b = &rq->rd->dl_bw;
  546. raw_spin_lock(&dl_b->lock);
  547. __dl_sub(dl_b, p->dl.dl_bw, cpumask_weight(rq->rd->span));
  548. raw_spin_unlock(&dl_b->lock);
  549. dl_b = &later_rq->rd->dl_bw;
  550. raw_spin_lock(&dl_b->lock);
  551. __dl_add(dl_b, p->dl.dl_bw, cpumask_weight(later_rq->rd->span));
  552. raw_spin_unlock(&dl_b->lock);
  553. set_task_cpu(p, later_rq->cpu);
  554. double_unlock_balance(later_rq, rq);
  555. return later_rq;
  556. }
  557. #else
  558. static inline
  559. void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
  560. {
  561. }
  562. static inline
  563. void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
  564. {
  565. }
  566. static inline
  567. void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
  568. {
  569. }
  570. static inline
  571. void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
  572. {
  573. }
  574. static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
  575. {
  576. return false;
  577. }
  578. static inline void pull_dl_task(struct rq *rq)
  579. {
  580. }
  581. static inline void deadline_queue_push_tasks(struct rq *rq)
  582. {
  583. }
  584. static inline void deadline_queue_pull_task(struct rq *rq)
  585. {
  586. }
  587. #endif /* CONFIG_SMP */
  588. static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags);
  589. static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags);
  590. static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p, int flags);
  591. /*
  592. * We are being explicitly informed that a new instance is starting,
  593. * and this means that:
  594. * - the absolute deadline of the entity has to be placed at
  595. * current time + relative deadline;
  596. * - the runtime of the entity has to be set to the maximum value.
  597. *
  598. * The capability of specifying such event is useful whenever a -deadline
  599. * entity wants to (try to!) synchronize its behaviour with the scheduler's
  600. * one, and to (try to!) reconcile itself with its own scheduling
  601. * parameters.
  602. */
  603. static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  604. {
  605. struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
  606. struct rq *rq = rq_of_dl_rq(dl_rq);
  607. WARN_ON(is_dl_boosted(dl_se));
  608. WARN_ON(dl_time_before(rq_clock(rq), dl_se->deadline));
  609. /*
  610. * We are racing with the deadline timer. So, do nothing because
  611. * the deadline timer handler will take care of properly recharging
  612. * the runtime and postponing the deadline
  613. */
  614. if (dl_se->dl_throttled)
  615. return;
  616. /*
  617. * We use the regular wall clock time to set deadlines in the
  618. * future; in fact, we must consider execution overheads (time
  619. * spent on hardirq context, etc.).
  620. */
  621. dl_se->deadline = rq_clock(rq) + dl_se->dl_deadline;
  622. dl_se->runtime = dl_se->dl_runtime;
  623. }
  624. /*
  625. * Pure Earliest Deadline First (EDF) scheduling does not deal with the
  626. * possibility of a entity lasting more than what it declared, and thus
  627. * exhausting its runtime.
  628. *
  629. * Here we are interested in making runtime overrun possible, but we do
  630. * not want a entity which is misbehaving to affect the scheduling of all
  631. * other entities.
  632. * Therefore, a budgeting strategy called Constant Bandwidth Server (CBS)
  633. * is used, in order to confine each entity within its own bandwidth.
  634. *
  635. * This function deals exactly with that, and ensures that when the runtime
  636. * of a entity is replenished, its deadline is also postponed. That ensures
  637. * the overrunning entity can't interfere with other entity in the system and
  638. * can't make them miss their deadlines. Reasons why this kind of overruns
  639. * could happen are, typically, a entity voluntarily trying to overcome its
  640. * runtime, or it just underestimated it during sched_setattr().
  641. */
  642. static void replenish_dl_entity(struct sched_dl_entity *dl_se)
  643. {
  644. struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
  645. struct rq *rq = rq_of_dl_rq(dl_rq);
  646. BUG_ON(pi_of(dl_se)->dl_runtime <= 0);
  647. /*
  648. * This could be the case for a !-dl task that is boosted.
  649. * Just go with full inherited parameters.
  650. */
  651. if (dl_se->dl_deadline == 0) {
  652. dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
  653. dl_se->runtime = pi_of(dl_se)->dl_runtime;
  654. }
  655. if (dl_se->dl_yielded && dl_se->runtime > 0)
  656. dl_se->runtime = 0;
  657. /*
  658. * We keep moving the deadline away until we get some
  659. * available runtime for the entity. This ensures correct
  660. * handling of situations where the runtime overrun is
  661. * arbitrary large.
  662. */
  663. while (dl_se->runtime <= 0) {
  664. dl_se->deadline += pi_of(dl_se)->dl_period;
  665. dl_se->runtime += pi_of(dl_se)->dl_runtime;
  666. }
  667. /*
  668. * At this point, the deadline really should be "in
  669. * the future" with respect to rq->clock. If it's
  670. * not, we are, for some reason, lagging too much!
  671. * Anyway, after having warn userspace abut that,
  672. * we still try to keep the things running by
  673. * resetting the deadline and the budget of the
  674. * entity.
  675. */
  676. if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
  677. printk_deferred_once("sched: DL replenish lagged too much\n");
  678. dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
  679. dl_se->runtime = pi_of(dl_se)->dl_runtime;
  680. }
  681. if (dl_se->dl_yielded)
  682. dl_se->dl_yielded = 0;
  683. if (dl_se->dl_throttled)
  684. dl_se->dl_throttled = 0;
  685. }
  686. /*
  687. * Here we check if --at time t-- an entity (which is probably being
  688. * [re]activated or, in general, enqueued) can use its remaining runtime
  689. * and its current deadline _without_ exceeding the bandwidth it is
  690. * assigned (function returns true if it can't). We are in fact applying
  691. * one of the CBS rules: when a task wakes up, if the residual runtime
  692. * over residual deadline fits within the allocated bandwidth, then we
  693. * can keep the current (absolute) deadline and residual budget without
  694. * disrupting the schedulability of the system. Otherwise, we should
  695. * refill the runtime and set the deadline a period in the future,
  696. * because keeping the current (absolute) deadline of the task would
  697. * result in breaking guarantees promised to other tasks (refer to
  698. * Documentation/scheduler/sched-deadline.rst for more information).
  699. *
  700. * This function returns true if:
  701. *
  702. * runtime / (deadline - t) > dl_runtime / dl_deadline ,
  703. *
  704. * IOW we can't recycle current parameters.
  705. *
  706. * Notice that the bandwidth check is done against the deadline. For
  707. * task with deadline equal to period this is the same of using
  708. * dl_period instead of dl_deadline in the equation above.
  709. */
  710. static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t)
  711. {
  712. u64 left, right;
  713. /*
  714. * left and right are the two sides of the equation above,
  715. * after a bit of shuffling to use multiplications instead
  716. * of divisions.
  717. *
  718. * Note that none of the time values involved in the two
  719. * multiplications are absolute: dl_deadline and dl_runtime
  720. * are the relative deadline and the maximum runtime of each
  721. * instance, runtime is the runtime left for the last instance
  722. * and (deadline - t), since t is rq->clock, is the time left
  723. * to the (absolute) deadline. Even if overflowing the u64 type
  724. * is very unlikely to occur in both cases, here we scale down
  725. * as we want to avoid that risk at all. Scaling down by 10
  726. * means that we reduce granularity to 1us. We are fine with it,
  727. * since this is only a true/false check and, anyway, thinking
  728. * of anything below microseconds resolution is actually fiction
  729. * (but still we want to give the user that illusion >;).
  730. */
  731. left = (pi_of(dl_se)->dl_deadline >> DL_SCALE) * (dl_se->runtime >> DL_SCALE);
  732. right = ((dl_se->deadline - t) >> DL_SCALE) *
  733. (pi_of(dl_se)->dl_runtime >> DL_SCALE);
  734. return dl_time_before(right, left);
  735. }
  736. /*
  737. * Revised wakeup rule [1]: For self-suspending tasks, rather then
  738. * re-initializing task's runtime and deadline, the revised wakeup
  739. * rule adjusts the task's runtime to avoid the task to overrun its
  740. * density.
  741. *
  742. * Reasoning: a task may overrun the density if:
  743. * runtime / (deadline - t) > dl_runtime / dl_deadline
  744. *
  745. * Therefore, runtime can be adjusted to:
  746. * runtime = (dl_runtime / dl_deadline) * (deadline - t)
  747. *
  748. * In such way that runtime will be equal to the maximum density
  749. * the task can use without breaking any rule.
  750. *
  751. * [1] Luca Abeni, Giuseppe Lipari, and Juri Lelli. 2015. Constant
  752. * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24.
  753. */
  754. static void
  755. update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
  756. {
  757. u64 laxity = dl_se->deadline - rq_clock(rq);
  758. /*
  759. * If the task has deadline < period, and the deadline is in the past,
  760. * it should already be throttled before this check.
  761. *
  762. * See update_dl_entity() comments for further details.
  763. */
  764. WARN_ON(dl_time_before(dl_se->deadline, rq_clock(rq)));
  765. dl_se->runtime = (dl_se->dl_density * laxity) >> BW_SHIFT;
  766. }
  767. /*
  768. * Regarding the deadline, a task with implicit deadline has a relative
  769. * deadline == relative period. A task with constrained deadline has a
  770. * relative deadline <= relative period.
  771. *
  772. * We support constrained deadline tasks. However, there are some restrictions
  773. * applied only for tasks which do not have an implicit deadline. See
  774. * update_dl_entity() to know more about such restrictions.
  775. *
  776. * The dl_is_implicit() returns true if the task has an implicit deadline.
  777. */
  778. static inline bool dl_is_implicit(struct sched_dl_entity *dl_se)
  779. {
  780. return dl_se->dl_deadline == dl_se->dl_period;
  781. }
  782. /*
  783. * When a deadline entity is placed in the runqueue, its runtime and deadline
  784. * might need to be updated. This is done by a CBS wake up rule. There are two
  785. * different rules: 1) the original CBS; and 2) the Revisited CBS.
  786. *
  787. * When the task is starting a new period, the Original CBS is used. In this
  788. * case, the runtime is replenished and a new absolute deadline is set.
  789. *
  790. * When a task is queued before the begin of the next period, using the
  791. * remaining runtime and deadline could make the entity to overflow, see
  792. * dl_entity_overflow() to find more about runtime overflow. When such case
  793. * is detected, the runtime and deadline need to be updated.
  794. *
  795. * If the task has an implicit deadline, i.e., deadline == period, the Original
  796. * CBS is applied. the runtime is replenished and a new absolute deadline is
  797. * set, as in the previous cases.
  798. *
  799. * However, the Original CBS does not work properly for tasks with
  800. * deadline < period, which are said to have a constrained deadline. By
  801. * applying the Original CBS, a constrained deadline task would be able to run
  802. * runtime/deadline in a period. With deadline < period, the task would
  803. * overrun the runtime/period allowed bandwidth, breaking the admission test.
  804. *
  805. * In order to prevent this misbehave, the Revisited CBS is used for
  806. * constrained deadline tasks when a runtime overflow is detected. In the
  807. * Revisited CBS, rather than replenishing & setting a new absolute deadline,
  808. * the remaining runtime of the task is reduced to avoid runtime overflow.
  809. * Please refer to the comments update_dl_revised_wakeup() function to find
  810. * more about the Revised CBS rule.
  811. */
  812. static void update_dl_entity(struct sched_dl_entity *dl_se)
  813. {
  814. struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
  815. struct rq *rq = rq_of_dl_rq(dl_rq);
  816. if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
  817. dl_entity_overflow(dl_se, rq_clock(rq))) {
  818. if (unlikely(!dl_is_implicit(dl_se) &&
  819. !dl_time_before(dl_se->deadline, rq_clock(rq)) &&
  820. !is_dl_boosted(dl_se))) {
  821. update_dl_revised_wakeup(dl_se, rq);
  822. return;
  823. }
  824. dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
  825. dl_se->runtime = pi_of(dl_se)->dl_runtime;
  826. }
  827. }
  828. static inline u64 dl_next_period(struct sched_dl_entity *dl_se)
  829. {
  830. return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period;
  831. }
  832. /*
  833. * If the entity depleted all its runtime, and if we want it to sleep
  834. * while waiting for some new execution time to become available, we
  835. * set the bandwidth replenishment timer to the replenishment instant
  836. * and try to activate it.
  837. *
  838. * Notice that it is important for the caller to know if the timer
  839. * actually started or not (i.e., the replenishment instant is in
  840. * the future or in the past).
  841. */
  842. static int start_dl_timer(struct task_struct *p)
  843. {
  844. struct sched_dl_entity *dl_se = &p->dl;
  845. struct hrtimer *timer = &dl_se->dl_timer;
  846. struct rq *rq = task_rq(p);
  847. ktime_t now, act;
  848. s64 delta;
  849. lockdep_assert_held(&rq->lock);
  850. /*
  851. * We want the timer to fire at the deadline, but considering
  852. * that it is actually coming from rq->clock and not from
  853. * hrtimer's time base reading.
  854. */
  855. act = ns_to_ktime(dl_next_period(dl_se));
  856. now = hrtimer_cb_get_time(timer);
  857. delta = ktime_to_ns(now) - rq_clock(rq);
  858. act = ktime_add_ns(act, delta);
  859. /*
  860. * If the expiry time already passed, e.g., because the value
  861. * chosen as the deadline is too small, don't even try to
  862. * start the timer in the past!
  863. */
  864. if (ktime_us_delta(act, now) < 0)
  865. return 0;
  866. /*
  867. * !enqueued will guarantee another callback; even if one is already in
  868. * progress. This ensures a balanced {get,put}_task_struct().
  869. *
  870. * The race against __run_timer() clearing the enqueued state is
  871. * harmless because we're holding task_rq()->lock, therefore the timer
  872. * expiring after we've done the check will wait on its task_rq_lock()
  873. * and observe our state.
  874. */
  875. if (!hrtimer_is_queued(timer)) {
  876. get_task_struct(p);
  877. hrtimer_start(timer, act, HRTIMER_MODE_ABS_HARD);
  878. }
  879. return 1;
  880. }
  881. /*
  882. * This is the bandwidth enforcement timer callback. If here, we know
  883. * a task is not on its dl_rq, since the fact that the timer was running
  884. * means the task is throttled and needs a runtime replenishment.
  885. *
  886. * However, what we actually do depends on the fact the task is active,
  887. * (it is on its rq) or has been removed from there by a call to
  888. * dequeue_task_dl(). In the former case we must issue the runtime
  889. * replenishment and add the task back to the dl_rq; in the latter, we just
  890. * do nothing but clearing dl_throttled, so that runtime and deadline
  891. * updating (and the queueing back to dl_rq) will be done by the
  892. * next call to enqueue_task_dl().
  893. */
  894. static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
  895. {
  896. struct sched_dl_entity *dl_se = container_of(timer,
  897. struct sched_dl_entity,
  898. dl_timer);
  899. struct task_struct *p = dl_task_of(dl_se);
  900. struct rq_flags rf;
  901. struct rq *rq;
  902. rq = task_rq_lock(p, &rf);
  903. /*
  904. * The task might have changed its scheduling policy to something
  905. * different than SCHED_DEADLINE (through switched_from_dl()).
  906. */
  907. if (!dl_task(p))
  908. goto unlock;
  909. /*
  910. * The task might have been boosted by someone else and might be in the
  911. * boosting/deboosting path, its not throttled.
  912. */
  913. if (is_dl_boosted(dl_se))
  914. goto unlock;
  915. /*
  916. * Spurious timer due to start_dl_timer() race; or we already received
  917. * a replenishment from rt_mutex_setprio().
  918. */
  919. if (!dl_se->dl_throttled)
  920. goto unlock;
  921. sched_clock_tick();
  922. update_rq_clock(rq);
  923. /*
  924. * If the throttle happened during sched-out; like:
  925. *
  926. * schedule()
  927. * deactivate_task()
  928. * dequeue_task_dl()
  929. * update_curr_dl()
  930. * start_dl_timer()
  931. * __dequeue_task_dl()
  932. * prev->on_rq = 0;
  933. *
  934. * We can be both throttled and !queued. Replenish the counter
  935. * but do not enqueue -- wait for our wakeup to do that.
  936. */
  937. if (!task_on_rq_queued(p)) {
  938. replenish_dl_entity(dl_se);
  939. goto unlock;
  940. }
  941. #ifdef CONFIG_SMP
  942. if (unlikely(!rq->online)) {
  943. /*
  944. * If the runqueue is no longer available, migrate the
  945. * task elsewhere. This necessarily changes rq.
  946. */
  947. lockdep_unpin_lock(&rq->lock, rf.cookie);
  948. rq = dl_task_offline_migration(rq, p);
  949. rf.cookie = lockdep_pin_lock(&rq->lock);
  950. update_rq_clock(rq);
  951. /*
  952. * Now that the task has been migrated to the new RQ and we
  953. * have that locked, proceed as normal and enqueue the task
  954. * there.
  955. */
  956. }
  957. #endif
  958. enqueue_task_dl(rq, p, ENQUEUE_REPLENISH);
  959. if (dl_task(rq->curr))
  960. check_preempt_curr_dl(rq, p, 0);
  961. else
  962. resched_curr(rq);
  963. #ifdef CONFIG_SMP
  964. /*
  965. * Queueing this task back might have overloaded rq, check if we need
  966. * to kick someone away.
  967. */
  968. if (has_pushable_dl_tasks(rq)) {
  969. /*
  970. * Nothing relies on rq->lock after this, so its safe to drop
  971. * rq->lock.
  972. */
  973. rq_unpin_lock(rq, &rf);
  974. push_dl_task(rq);
  975. rq_repin_lock(rq, &rf);
  976. }
  977. #endif
  978. unlock:
  979. task_rq_unlock(rq, p, &rf);
  980. /*
  981. * This can free the task_struct, including this hrtimer, do not touch
  982. * anything related to that after this.
  983. */
  984. put_task_struct(p);
  985. return HRTIMER_NORESTART;
  986. }
  987. void init_dl_task_timer(struct sched_dl_entity *dl_se)
  988. {
  989. struct hrtimer *timer = &dl_se->dl_timer;
  990. hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL_HARD);
  991. timer->function = dl_task_timer;
  992. }
  993. /*
  994. * During the activation, CBS checks if it can reuse the current task's
  995. * runtime and period. If the deadline of the task is in the past, CBS
  996. * cannot use the runtime, and so it replenishes the task. This rule
  997. * works fine for implicit deadline tasks (deadline == period), and the
  998. * CBS was designed for implicit deadline tasks. However, a task with
  999. * constrained deadline (deadline < period) might be awakened after the
  1000. * deadline, but before the next period. In this case, replenishing the
  1001. * task would allow it to run for runtime / deadline. As in this case
  1002. * deadline < period, CBS enables a task to run for more than the
  1003. * runtime / period. In a very loaded system, this can cause a domino
  1004. * effect, making other tasks miss their deadlines.
  1005. *
  1006. * To avoid this problem, in the activation of a constrained deadline
  1007. * task after the deadline but before the next period, throttle the
  1008. * task and set the replenishing timer to the begin of the next period,
  1009. * unless it is boosted.
  1010. */
  1011. static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
  1012. {
  1013. struct task_struct *p = dl_task_of(dl_se);
  1014. struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
  1015. if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
  1016. dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
  1017. if (unlikely(is_dl_boosted(dl_se) || !start_dl_timer(p)))
  1018. return;
  1019. dl_se->dl_throttled = 1;
  1020. if (dl_se->runtime > 0)
  1021. dl_se->runtime = 0;
  1022. }
  1023. }
  1024. static
  1025. int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
  1026. {
  1027. return (dl_se->runtime <= 0);
  1028. }
  1029. extern bool sched_rt_bandwidth_account(struct rt_rq *rt_rq);
  1030. /*
  1031. * This function implements the GRUB accounting rule:
  1032. * according to the GRUB reclaiming algorithm, the runtime is
  1033. * not decreased as "dq = -dt", but as
  1034. * "dq = -max{u / Umax, (1 - Uinact - Uextra)} dt",
  1035. * where u is the utilization of the task, Umax is the maximum reclaimable
  1036. * utilization, Uinact is the (per-runqueue) inactive utilization, computed
  1037. * as the difference between the "total runqueue utilization" and the
  1038. * runqueue active utilization, and Uextra is the (per runqueue) extra
  1039. * reclaimable utilization.
  1040. * Since rq->dl.running_bw and rq->dl.this_bw contain utilizations
  1041. * multiplied by 2^BW_SHIFT, the result has to be shifted right by
  1042. * BW_SHIFT.
  1043. * Since rq->dl.bw_ratio contains 1 / Umax multipled by 2^RATIO_SHIFT,
  1044. * dl_bw is multiped by rq->dl.bw_ratio and shifted right by RATIO_SHIFT.
  1045. * Since delta is a 64 bit variable, to have an overflow its value
  1046. * should be larger than 2^(64 - 20 - 8), which is more than 64 seconds.
  1047. * So, overflow is not an issue here.
  1048. */
  1049. static u64 grub_reclaim(u64 delta, struct rq *rq, struct sched_dl_entity *dl_se)
  1050. {
  1051. u64 u_inact = rq->dl.this_bw - rq->dl.running_bw; /* Utot - Uact */
  1052. u64 u_act;
  1053. u64 u_act_min = (dl_se->dl_bw * rq->dl.bw_ratio) >> RATIO_SHIFT;
  1054. /*
  1055. * Instead of computing max{u * bw_ratio, (1 - u_inact - u_extra)},
  1056. * we compare u_inact + rq->dl.extra_bw with
  1057. * 1 - (u * rq->dl.bw_ratio >> RATIO_SHIFT), because
  1058. * u_inact + rq->dl.extra_bw can be larger than
  1059. * 1 * (so, 1 - u_inact - rq->dl.extra_bw would be negative
  1060. * leading to wrong results)
  1061. */
  1062. if (u_inact + rq->dl.extra_bw > BW_UNIT - u_act_min)
  1063. u_act = u_act_min;
  1064. else
  1065. u_act = BW_UNIT - u_inact - rq->dl.extra_bw;
  1066. return (delta * u_act) >> BW_SHIFT;
  1067. }
  1068. /*
  1069. * Update the current task's runtime statistics (provided it is still
  1070. * a -deadline task and has not been removed from the dl_rq).
  1071. */
  1072. static void update_curr_dl(struct rq *rq)
  1073. {
  1074. struct task_struct *curr = rq->curr;
  1075. struct sched_dl_entity *dl_se = &curr->dl;
  1076. u64 delta_exec, scaled_delta_exec;
  1077. int cpu = cpu_of(rq);
  1078. u64 now;
  1079. if (!dl_task(curr) || !on_dl_rq(dl_se))
  1080. return;
  1081. /*
  1082. * Consumed budget is computed considering the time as
  1083. * observed by schedulable tasks (excluding time spent
  1084. * in hardirq context, etc.). Deadlines are instead
  1085. * computed using hard walltime. This seems to be the more
  1086. * natural solution, but the full ramifications of this
  1087. * approach need further study.
  1088. */
  1089. now = rq_clock_task(rq);
  1090. delta_exec = now - curr->se.exec_start;
  1091. if (unlikely((s64)delta_exec <= 0)) {
  1092. if (unlikely(dl_se->dl_yielded))
  1093. goto throttle;
  1094. return;
  1095. }
  1096. schedstat_set(curr->se.statistics.exec_max,
  1097. max(curr->se.statistics.exec_max, delta_exec));
  1098. curr->se.sum_exec_runtime += delta_exec;
  1099. account_group_exec_runtime(curr, delta_exec);
  1100. curr->se.exec_start = now;
  1101. cgroup_account_cputime(curr, delta_exec);
  1102. if (dl_entity_is_special(dl_se))
  1103. return;
  1104. /*
  1105. * For tasks that participate in GRUB, we implement GRUB-PA: the
  1106. * spare reclaimed bandwidth is used to clock down frequency.
  1107. *
  1108. * For the others, we still need to scale reservation parameters
  1109. * according to current frequency and CPU maximum capacity.
  1110. */
  1111. if (unlikely(dl_se->flags & SCHED_FLAG_RECLAIM)) {
  1112. scaled_delta_exec = grub_reclaim(delta_exec,
  1113. rq,
  1114. &curr->dl);
  1115. } else {
  1116. unsigned long scale_freq = arch_scale_freq_capacity(cpu);
  1117. unsigned long scale_cpu = arch_scale_cpu_capacity(cpu);
  1118. scaled_delta_exec = cap_scale(delta_exec, scale_freq);
  1119. scaled_delta_exec = cap_scale(scaled_delta_exec, scale_cpu);
  1120. }
  1121. dl_se->runtime -= scaled_delta_exec;
  1122. throttle:
  1123. if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
  1124. dl_se->dl_throttled = 1;
  1125. /* If requested, inform the user about runtime overruns. */
  1126. if (dl_runtime_exceeded(dl_se) &&
  1127. (dl_se->flags & SCHED_FLAG_DL_OVERRUN))
  1128. dl_se->dl_overrun = 1;
  1129. __dequeue_task_dl(rq, curr, 0);
  1130. if (unlikely(is_dl_boosted(dl_se) || !start_dl_timer(curr)))
  1131. enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH);
  1132. if (!is_leftmost(curr, &rq->dl))
  1133. resched_curr(rq);
  1134. }
  1135. /*
  1136. * Because -- for now -- we share the rt bandwidth, we need to
  1137. * account our runtime there too, otherwise actual rt tasks
  1138. * would be able to exceed the shared quota.
  1139. *
  1140. * Account to the root rt group for now.
  1141. *
  1142. * The solution we're working towards is having the RT groups scheduled
  1143. * using deadline servers -- however there's a few nasties to figure
  1144. * out before that can happen.
  1145. */
  1146. if (rt_bandwidth_enabled()) {
  1147. struct rt_rq *rt_rq = &rq->rt;
  1148. raw_spin_lock(&rt_rq->rt_runtime_lock);
  1149. /*
  1150. * We'll let actual RT tasks worry about the overflow here, we
  1151. * have our own CBS to keep us inline; only account when RT
  1152. * bandwidth is relevant.
  1153. */
  1154. if (sched_rt_bandwidth_account(rt_rq))
  1155. rt_rq->rt_time += delta_exec;
  1156. raw_spin_unlock(&rt_rq->rt_runtime_lock);
  1157. }
  1158. }
  1159. static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer)
  1160. {
  1161. struct sched_dl_entity *dl_se = container_of(timer,
  1162. struct sched_dl_entity,
  1163. inactive_timer);
  1164. struct task_struct *p = dl_task_of(dl_se);
  1165. struct rq_flags rf;
  1166. struct rq *rq;
  1167. rq = task_rq_lock(p, &rf);
  1168. sched_clock_tick();
  1169. update_rq_clock(rq);
  1170. if (!dl_task(p) || p->state == TASK_DEAD) {
  1171. struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
  1172. if (p->state == TASK_DEAD && dl_se->dl_non_contending) {
  1173. sub_running_bw(&p->dl, dl_rq_of_se(&p->dl));
  1174. sub_rq_bw(&p->dl, dl_rq_of_se(&p->dl));
  1175. dl_se->dl_non_contending = 0;
  1176. }
  1177. raw_spin_lock(&dl_b->lock);
  1178. __dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p)));
  1179. raw_spin_unlock(&dl_b->lock);
  1180. __dl_clear_params(p);
  1181. goto unlock;
  1182. }
  1183. if (dl_se->dl_non_contending == 0)
  1184. goto unlock;
  1185. sub_running_bw(dl_se, &rq->dl);
  1186. dl_se->dl_non_contending = 0;
  1187. unlock:
  1188. task_rq_unlock(rq, p, &rf);
  1189. put_task_struct(p);
  1190. return HRTIMER_NORESTART;
  1191. }
  1192. void init_dl_inactive_task_timer(struct sched_dl_entity *dl_se)
  1193. {
  1194. struct hrtimer *timer = &dl_se->inactive_timer;
  1195. hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL_HARD);
  1196. timer->function = inactive_task_timer;
  1197. }
  1198. #ifdef CONFIG_SMP
  1199. static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
  1200. {
  1201. struct rq *rq = rq_of_dl_rq(dl_rq);
  1202. if (dl_rq->earliest_dl.curr == 0 ||
  1203. dl_time_before(deadline, dl_rq->earliest_dl.curr)) {
  1204. dl_rq->earliest_dl.curr = deadline;
  1205. cpudl_set(&rq->rd->cpudl, rq->cpu, deadline);
  1206. }
  1207. }
  1208. static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
  1209. {
  1210. struct rq *rq = rq_of_dl_rq(dl_rq);
  1211. /*
  1212. * Since we may have removed our earliest (and/or next earliest)
  1213. * task we must recompute them.
  1214. */
  1215. if (!dl_rq->dl_nr_running) {
  1216. dl_rq->earliest_dl.curr = 0;
  1217. dl_rq->earliest_dl.next = 0;
  1218. cpudl_clear(&rq->rd->cpudl, rq->cpu);
  1219. } else {
  1220. struct rb_node *leftmost = dl_rq->root.rb_leftmost;
  1221. struct sched_dl_entity *entry;
  1222. entry = rb_entry(leftmost, struct sched_dl_entity, rb_node);
  1223. dl_rq->earliest_dl.curr = entry->deadline;
  1224. cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline);
  1225. }
  1226. }
  1227. #else
  1228. static inline void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
  1229. static inline void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
  1230. #endif /* CONFIG_SMP */
  1231. static inline
  1232. void inc_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
  1233. {
  1234. int prio = dl_task_of(dl_se)->prio;
  1235. u64 deadline = dl_se->deadline;
  1236. WARN_ON(!dl_prio(prio));
  1237. dl_rq->dl_nr_running++;
  1238. add_nr_running(rq_of_dl_rq(dl_rq), 1);
  1239. inc_dl_deadline(dl_rq, deadline);
  1240. inc_dl_migration(dl_se, dl_rq);
  1241. }
  1242. static inline
  1243. void dec_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
  1244. {
  1245. int prio = dl_task_of(dl_se)->prio;
  1246. WARN_ON(!dl_prio(prio));
  1247. WARN_ON(!dl_rq->dl_nr_running);
  1248. dl_rq->dl_nr_running--;
  1249. sub_nr_running(rq_of_dl_rq(dl_rq), 1);
  1250. dec_dl_deadline(dl_rq, dl_se->deadline);
  1251. dec_dl_migration(dl_se, dl_rq);
  1252. }
  1253. static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
  1254. {
  1255. struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
  1256. struct rb_node **link = &dl_rq->root.rb_root.rb_node;
  1257. struct rb_node *parent = NULL;
  1258. struct sched_dl_entity *entry;
  1259. int leftmost = 1;
  1260. BUG_ON(!RB_EMPTY_NODE(&dl_se->rb_node));
  1261. while (*link) {
  1262. parent = *link;
  1263. entry = rb_entry(parent, struct sched_dl_entity, rb_node);
  1264. if (dl_time_before(dl_se->deadline, entry->deadline))
  1265. link = &parent->rb_left;
  1266. else {
  1267. link = &parent->rb_right;
  1268. leftmost = 0;
  1269. }
  1270. }
  1271. rb_link_node(&dl_se->rb_node, parent, link);
  1272. rb_insert_color_cached(&dl_se->rb_node, &dl_rq->root, leftmost);
  1273. inc_dl_tasks(dl_se, dl_rq);
  1274. }
  1275. static void __dequeue_dl_entity(struct sched_dl_entity *dl_se)
  1276. {
  1277. struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
  1278. if (RB_EMPTY_NODE(&dl_se->rb_node))
  1279. return;
  1280. rb_erase_cached(&dl_se->rb_node, &dl_rq->root);
  1281. RB_CLEAR_NODE(&dl_se->rb_node);
  1282. dec_dl_tasks(dl_se, dl_rq);
  1283. }
  1284. static void
  1285. enqueue_dl_entity(struct sched_dl_entity *dl_se, int flags)
  1286. {
  1287. BUG_ON(on_dl_rq(dl_se));
  1288. /*
  1289. * If this is a wakeup or a new instance, the scheduling
  1290. * parameters of the task might need updating. Otherwise,
  1291. * we want a replenishment of its runtime.
  1292. */
  1293. if (flags & ENQUEUE_WAKEUP) {
  1294. task_contending(dl_se, flags);
  1295. update_dl_entity(dl_se);
  1296. } else if (flags & ENQUEUE_REPLENISH) {
  1297. replenish_dl_entity(dl_se);
  1298. } else if ((flags & ENQUEUE_RESTORE) &&
  1299. dl_time_before(dl_se->deadline,
  1300. rq_clock(rq_of_dl_rq(dl_rq_of_se(dl_se))))) {
  1301. setup_new_dl_entity(dl_se);
  1302. }
  1303. __enqueue_dl_entity(dl_se);
  1304. }
  1305. static void dequeue_dl_entity(struct sched_dl_entity *dl_se)
  1306. {
  1307. __dequeue_dl_entity(dl_se);
  1308. }
  1309. static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
  1310. {
  1311. if (is_dl_boosted(&p->dl)) {
  1312. /*
  1313. * Because of delays in the detection of the overrun of a
  1314. * thread's runtime, it might be the case that a thread
  1315. * goes to sleep in a rt mutex with negative runtime. As
  1316. * a consequence, the thread will be throttled.
  1317. *
  1318. * While waiting for the mutex, this thread can also be
  1319. * boosted via PI, resulting in a thread that is throttled
  1320. * and boosted at the same time.
  1321. *
  1322. * In this case, the boost overrides the throttle.
  1323. */
  1324. if (p->dl.dl_throttled) {
  1325. /*
  1326. * The replenish timer needs to be canceled. No
  1327. * problem if it fires concurrently: boosted threads
  1328. * are ignored in dl_task_timer().
  1329. */
  1330. hrtimer_try_to_cancel(&p->dl.dl_timer);
  1331. p->dl.dl_throttled = 0;
  1332. }
  1333. } else if (!dl_prio(p->normal_prio)) {
  1334. /*
  1335. * Special case in which we have a !SCHED_DEADLINE task that is going
  1336. * to be deboosted, but exceeds its runtime while doing so. No point in
  1337. * replenishing it, as it's going to return back to its original
  1338. * scheduling class after this. If it has been throttled, we need to
  1339. * clear the flag, otherwise the task may wake up as throttled after
  1340. * being boosted again with no means to replenish the runtime and clear
  1341. * the throttle.
  1342. */
  1343. p->dl.dl_throttled = 0;
  1344. BUG_ON(!is_dl_boosted(&p->dl) || flags != ENQUEUE_REPLENISH);
  1345. return;
  1346. }
  1347. /*
  1348. * Check if a constrained deadline task was activated
  1349. * after the deadline but before the next period.
  1350. * If that is the case, the task will be throttled and
  1351. * the replenishment timer will be set to the next period.
  1352. */
  1353. if (!p->dl.dl_throttled && !dl_is_implicit(&p->dl))
  1354. dl_check_constrained_dl(&p->dl);
  1355. if (p->on_rq == TASK_ON_RQ_MIGRATING || flags & ENQUEUE_RESTORE) {
  1356. add_rq_bw(&p->dl, &rq->dl);
  1357. add_running_bw(&p->dl, &rq->dl);
  1358. }
  1359. /*
  1360. * If p is throttled, we do not enqueue it. In fact, if it exhausted
  1361. * its budget it needs a replenishment and, since it now is on
  1362. * its rq, the bandwidth timer callback (which clearly has not
  1363. * run yet) will take care of this.
  1364. * However, the active utilization does not depend on the fact
  1365. * that the task is on the runqueue or not (but depends on the
  1366. * task's state - in GRUB parlance, "inactive" vs "active contending").
  1367. * In other words, even if a task is throttled its utilization must
  1368. * be counted in the active utilization; hence, we need to call
  1369. * add_running_bw().
  1370. */
  1371. if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH)) {
  1372. if (flags & ENQUEUE_WAKEUP)
  1373. task_contending(&p->dl, flags);
  1374. return;
  1375. }
  1376. enqueue_dl_entity(&p->dl, flags);
  1377. if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
  1378. enqueue_pushable_dl_task(rq, p);
  1379. }
  1380. static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
  1381. {
  1382. dequeue_dl_entity(&p->dl);
  1383. dequeue_pushable_dl_task(rq, p);
  1384. }
  1385. static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
  1386. {
  1387. update_curr_dl(rq);
  1388. __dequeue_task_dl(rq, p, flags);
  1389. if (p->on_rq == TASK_ON_RQ_MIGRATING || flags & DEQUEUE_SAVE) {
  1390. sub_running_bw(&p->dl, &rq->dl);
  1391. sub_rq_bw(&p->dl, &rq->dl);
  1392. }
  1393. /*
  1394. * This check allows to start the inactive timer (or to immediately
  1395. * decrease the active utilization, if needed) in two cases:
  1396. * when the task blocks and when it is terminating
  1397. * (p->state == TASK_DEAD). We can handle the two cases in the same
  1398. * way, because from GRUB's point of view the same thing is happening
  1399. * (the task moves from "active contending" to "active non contending"
  1400. * or "inactive")
  1401. */
  1402. if (flags & DEQUEUE_SLEEP)
  1403. task_non_contending(p);
  1404. }
  1405. /*
  1406. * Yield task semantic for -deadline tasks is:
  1407. *
  1408. * get off from the CPU until our next instance, with
  1409. * a new runtime. This is of little use now, since we
  1410. * don't have a bandwidth reclaiming mechanism. Anyway,
  1411. * bandwidth reclaiming is planned for the future, and
  1412. * yield_task_dl will indicate that some spare budget
  1413. * is available for other task instances to use it.
  1414. */
  1415. static void yield_task_dl(struct rq *rq)
  1416. {
  1417. /*
  1418. * We make the task go to sleep until its current deadline by
  1419. * forcing its runtime to zero. This way, update_curr_dl() stops
  1420. * it and the bandwidth timer will wake it up and will give it
  1421. * new scheduling parameters (thanks to dl_yielded=1).
  1422. */
  1423. rq->curr->dl.dl_yielded = 1;
  1424. update_rq_clock(rq);
  1425. update_curr_dl(rq);
  1426. /*
  1427. * Tell update_rq_clock() that we've just updated,
  1428. * so we don't do microscopic update in schedule()
  1429. * and double the fastpath cost.
  1430. */
  1431. rq_clock_skip_update(rq);
  1432. }
  1433. #ifdef CONFIG_SMP
  1434. static int find_later_rq(struct task_struct *task);
  1435. static int
  1436. select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
  1437. {
  1438. struct task_struct *curr;
  1439. bool select_rq;
  1440. struct rq *rq;
  1441. if (sd_flag != SD_BALANCE_WAKE)
  1442. goto out;
  1443. rq = cpu_rq(cpu);
  1444. rcu_read_lock();
  1445. curr = READ_ONCE(rq->curr); /* unlocked access */
  1446. /*
  1447. * If we are dealing with a -deadline task, we must
  1448. * decide where to wake it up.
  1449. * If it has a later deadline and the current task
  1450. * on this rq can't move (provided the waking task
  1451. * can!) we prefer to send it somewhere else. On the
  1452. * other hand, if it has a shorter deadline, we
  1453. * try to make it stay here, it might be important.
  1454. */
  1455. select_rq = unlikely(dl_task(curr)) &&
  1456. (curr->nr_cpus_allowed < 2 ||
  1457. !dl_entity_preempt(&p->dl, &curr->dl)) &&
  1458. p->nr_cpus_allowed > 1;
  1459. /*
  1460. * Take the capacity of the CPU into account to
  1461. * ensure it fits the requirement of the task.
  1462. */
  1463. if (static_branch_unlikely(&sched_asym_cpucapacity))
  1464. select_rq |= !dl_task_fits_capacity(p, cpu);
  1465. if (select_rq) {
  1466. int target = find_later_rq(p);
  1467. if (target != -1 &&
  1468. (dl_time_before(p->dl.deadline,
  1469. cpu_rq(target)->dl.earliest_dl.curr) ||
  1470. (cpu_rq(target)->dl.dl_nr_running == 0)))
  1471. cpu = target;
  1472. }
  1473. rcu_read_unlock();
  1474. out:
  1475. return cpu;
  1476. }
  1477. static void migrate_task_rq_dl(struct task_struct *p, int new_cpu __maybe_unused)
  1478. {
  1479. struct rq *rq;
  1480. if (p->state != TASK_WAKING)
  1481. return;
  1482. rq = task_rq(p);
  1483. /*
  1484. * Since p->state == TASK_WAKING, set_task_cpu() has been called
  1485. * from try_to_wake_up(). Hence, p->pi_lock is locked, but
  1486. * rq->lock is not... So, lock it
  1487. */
  1488. raw_spin_lock(&rq->lock);
  1489. if (p->dl.dl_non_contending) {
  1490. update_rq_clock(rq);
  1491. sub_running_bw(&p->dl, &rq->dl);
  1492. p->dl.dl_non_contending = 0;
  1493. /*
  1494. * If the timer handler is currently running and the
  1495. * timer cannot be cancelled, inactive_task_timer()
  1496. * will see that dl_not_contending is not set, and
  1497. * will not touch the rq's active utilization,
  1498. * so we are still safe.
  1499. */
  1500. if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1)
  1501. put_task_struct(p);
  1502. }
  1503. sub_rq_bw(&p->dl, &rq->dl);
  1504. raw_spin_unlock(&rq->lock);
  1505. }
  1506. static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
  1507. {
  1508. /*
  1509. * Current can't be migrated, useless to reschedule,
  1510. * let's hope p can move out.
  1511. */
  1512. if (rq->curr->nr_cpus_allowed == 1 ||
  1513. !cpudl_find(&rq->rd->cpudl, rq->curr, NULL))
  1514. return;
  1515. /*
  1516. * p is migratable, so let's not schedule it and
  1517. * see if it is pushed or pulled somewhere else.
  1518. */
  1519. if (p->nr_cpus_allowed != 1 &&
  1520. cpudl_find(&rq->rd->cpudl, p, NULL))
  1521. return;
  1522. resched_curr(rq);
  1523. }
  1524. static int balance_dl(struct rq *rq, struct task_struct *p, struct rq_flags *rf)
  1525. {
  1526. if (!on_dl_rq(&p->dl) && need_pull_dl_task(rq, p)) {
  1527. /*
  1528. * This is OK, because current is on_cpu, which avoids it being
  1529. * picked for load-balance and preemption/IRQs are still
  1530. * disabled avoiding further scheduler activity on it and we've
  1531. * not yet started the picking loop.
  1532. */
  1533. rq_unpin_lock(rq, rf);
  1534. pull_dl_task(rq);
  1535. rq_repin_lock(rq, rf);
  1536. }
  1537. return sched_stop_runnable(rq) || sched_dl_runnable(rq);
  1538. }
  1539. #endif /* CONFIG_SMP */
  1540. /*
  1541. * Only called when both the current and waking task are -deadline
  1542. * tasks.
  1543. */
  1544. static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p,
  1545. int flags)
  1546. {
  1547. if (dl_entity_preempt(&p->dl, &rq->curr->dl)) {
  1548. resched_curr(rq);
  1549. return;
  1550. }
  1551. #ifdef CONFIG_SMP
  1552. /*
  1553. * In the unlikely case current and p have the same deadline
  1554. * let us try to decide what's the best thing to do...
  1555. */
  1556. if ((p->dl.deadline == rq->curr->dl.deadline) &&
  1557. !test_tsk_need_resched(rq->curr))
  1558. check_preempt_equal_dl(rq, p);
  1559. #endif /* CONFIG_SMP */
  1560. }
  1561. #ifdef CONFIG_SCHED_HRTICK
  1562. static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
  1563. {
  1564. hrtick_start(rq, p->dl.runtime);
  1565. }
  1566. #else /* !CONFIG_SCHED_HRTICK */
  1567. static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
  1568. {
  1569. }
  1570. #endif
  1571. static void set_next_task_dl(struct rq *rq, struct task_struct *p, bool first)
  1572. {
  1573. p->se.exec_start = rq_clock_task(rq);
  1574. /* You can't push away the running task */
  1575. dequeue_pushable_dl_task(rq, p);
  1576. if (!first)
  1577. return;
  1578. if (hrtick_enabled(rq))
  1579. start_hrtick_dl(rq, p);
  1580. if (rq->curr->sched_class != &dl_sched_class)
  1581. update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 0);
  1582. deadline_queue_push_tasks(rq);
  1583. }
  1584. static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq,
  1585. struct dl_rq *dl_rq)
  1586. {
  1587. struct rb_node *left = rb_first_cached(&dl_rq->root);
  1588. if (!left)
  1589. return NULL;
  1590. return rb_entry(left, struct sched_dl_entity, rb_node);
  1591. }
  1592. static struct task_struct *pick_next_task_dl(struct rq *rq)
  1593. {
  1594. struct sched_dl_entity *dl_se;
  1595. struct dl_rq *dl_rq = &rq->dl;
  1596. struct task_struct *p;
  1597. if (!sched_dl_runnable(rq))
  1598. return NULL;
  1599. dl_se = pick_next_dl_entity(rq, dl_rq);
  1600. BUG_ON(!dl_se);
  1601. p = dl_task_of(dl_se);
  1602. set_next_task_dl(rq, p, true);
  1603. return p;
  1604. }
  1605. static void put_prev_task_dl(struct rq *rq, struct task_struct *p)
  1606. {
  1607. update_curr_dl(rq);
  1608. update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 1);
  1609. if (on_dl_rq(&p->dl) && p->nr_cpus_allowed > 1)
  1610. enqueue_pushable_dl_task(rq, p);
  1611. }
  1612. /*
  1613. * scheduler tick hitting a task of our scheduling class.
  1614. *
  1615. * NOTE: This function can be called remotely by the tick offload that
  1616. * goes along full dynticks. Therefore no local assumption can be made
  1617. * and everything must be accessed through the @rq and @curr passed in
  1618. * parameters.
  1619. */
  1620. static void task_tick_dl(struct rq *rq, struct task_struct *p, int queued)
  1621. {
  1622. update_curr_dl(rq);
  1623. update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 1);
  1624. /*
  1625. * Even when we have runtime, update_curr_dl() might have resulted in us
  1626. * not being the leftmost task anymore. In that case NEED_RESCHED will
  1627. * be set and schedule() will start a new hrtick for the next task.
  1628. */
  1629. if (hrtick_enabled(rq) && queued && p->dl.runtime > 0 &&
  1630. is_leftmost(p, &rq->dl))
  1631. start_hrtick_dl(rq, p);
  1632. }
  1633. static void task_fork_dl(struct task_struct *p)
  1634. {
  1635. /*
  1636. * SCHED_DEADLINE tasks cannot fork and this is achieved through
  1637. * sched_fork()
  1638. */
  1639. }
  1640. #ifdef CONFIG_SMP
  1641. /* Only try algorithms three times */
  1642. #define DL_MAX_TRIES 3
  1643. static int pick_dl_task(struct rq *rq, struct task_struct *p, int cpu)
  1644. {
  1645. if (!task_running(rq, p) &&
  1646. cpumask_test_cpu(cpu, p->cpus_ptr))
  1647. return 1;
  1648. return 0;
  1649. }
  1650. /*
  1651. * Return the earliest pushable rq's task, which is suitable to be executed
  1652. * on the CPU, NULL otherwise:
  1653. */
  1654. static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu)
  1655. {
  1656. struct rb_node *next_node = rq->dl.pushable_dl_tasks_root.rb_leftmost;
  1657. struct task_struct *p = NULL;
  1658. if (!has_pushable_dl_tasks(rq))
  1659. return NULL;
  1660. next_node:
  1661. if (next_node) {
  1662. p = rb_entry(next_node, struct task_struct, pushable_dl_tasks);
  1663. if (pick_dl_task(rq, p, cpu))
  1664. return p;
  1665. next_node = rb_next(next_node);
  1666. goto next_node;
  1667. }
  1668. return NULL;
  1669. }
  1670. static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
  1671. static int find_later_rq(struct task_struct *task)
  1672. {
  1673. struct sched_domain *sd;
  1674. struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
  1675. int this_cpu = smp_processor_id();
  1676. int cpu = task_cpu(task);
  1677. /* Make sure the mask is initialized first */
  1678. if (unlikely(!later_mask))
  1679. return -1;
  1680. if (task->nr_cpus_allowed == 1)
  1681. return -1;
  1682. /*
  1683. * We have to consider system topology and task affinity
  1684. * first, then we can look for a suitable CPU.
  1685. */
  1686. if (!cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask))
  1687. return -1;
  1688. /*
  1689. * If we are here, some targets have been found, including
  1690. * the most suitable which is, among the runqueues where the
  1691. * current tasks have later deadlines than the task's one, the
  1692. * rq with the latest possible one.
  1693. *
  1694. * Now we check how well this matches with task's
  1695. * affinity and system topology.
  1696. *
  1697. * The last CPU where the task run is our first
  1698. * guess, since it is most likely cache-hot there.
  1699. */
  1700. if (cpumask_test_cpu(cpu, later_mask))
  1701. return cpu;
  1702. /*
  1703. * Check if this_cpu is to be skipped (i.e., it is
  1704. * not in the mask) or not.
  1705. */
  1706. if (!cpumask_test_cpu(this_cpu, later_mask))
  1707. this_cpu = -1;
  1708. rcu_read_lock();
  1709. for_each_domain(cpu, sd) {
  1710. if (sd->flags & SD_WAKE_AFFINE) {
  1711. int best_cpu;
  1712. /*
  1713. * If possible, preempting this_cpu is
  1714. * cheaper than migrating.
  1715. */
  1716. if (this_cpu != -1 &&
  1717. cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
  1718. rcu_read_unlock();
  1719. return this_cpu;
  1720. }
  1721. best_cpu = cpumask_first_and(later_mask,
  1722. sched_domain_span(sd));
  1723. /*
  1724. * Last chance: if a CPU being in both later_mask
  1725. * and current sd span is valid, that becomes our
  1726. * choice. Of course, the latest possible CPU is
  1727. * already under consideration through later_mask.
  1728. */
  1729. if (best_cpu < nr_cpu_ids) {
  1730. rcu_read_unlock();
  1731. return best_cpu;
  1732. }
  1733. }
  1734. }
  1735. rcu_read_unlock();
  1736. /*
  1737. * At this point, all our guesses failed, we just return
  1738. * 'something', and let the caller sort the things out.
  1739. */
  1740. if (this_cpu != -1)
  1741. return this_cpu;
  1742. cpu = cpumask_any(later_mask);
  1743. if (cpu < nr_cpu_ids)
  1744. return cpu;
  1745. return -1;
  1746. }
  1747. /* Locks the rq it finds */
  1748. static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq)
  1749. {
  1750. struct rq *later_rq = NULL;
  1751. int tries;
  1752. int cpu;
  1753. for (tries = 0; tries < DL_MAX_TRIES; tries++) {
  1754. cpu = find_later_rq(task);
  1755. if ((cpu == -1) || (cpu == rq->cpu))
  1756. break;
  1757. later_rq = cpu_rq(cpu);
  1758. if (later_rq->dl.dl_nr_running &&
  1759. !dl_time_before(task->dl.deadline,
  1760. later_rq->dl.earliest_dl.curr)) {
  1761. /*
  1762. * Target rq has tasks of equal or earlier deadline,
  1763. * retrying does not release any lock and is unlikely
  1764. * to yield a different result.
  1765. */
  1766. later_rq = NULL;
  1767. break;
  1768. }
  1769. /* Retry if something changed. */
  1770. if (double_lock_balance(rq, later_rq)) {
  1771. if (unlikely(task_rq(task) != rq ||
  1772. !cpumask_test_cpu(later_rq->cpu, task->cpus_ptr) ||
  1773. task_running(rq, task) ||
  1774. !dl_task(task) ||
  1775. !task_on_rq_queued(task))) {
  1776. double_unlock_balance(rq, later_rq);
  1777. later_rq = NULL;
  1778. break;
  1779. }
  1780. }
  1781. /*
  1782. * If the rq we found has no -deadline task, or
  1783. * its earliest one has a later deadline than our
  1784. * task, the rq is a good one.
  1785. */
  1786. if (!later_rq->dl.dl_nr_running ||
  1787. dl_time_before(task->dl.deadline,
  1788. later_rq->dl.earliest_dl.curr))
  1789. break;
  1790. /* Otherwise we try again. */
  1791. double_unlock_balance(rq, later_rq);
  1792. later_rq = NULL;
  1793. }
  1794. return later_rq;
  1795. }
  1796. static struct task_struct *pick_next_pushable_dl_task(struct rq *rq)
  1797. {
  1798. struct task_struct *p;
  1799. if (!has_pushable_dl_tasks(rq))
  1800. return NULL;
  1801. p = rb_entry(rq->dl.pushable_dl_tasks_root.rb_leftmost,
  1802. struct task_struct, pushable_dl_tasks);
  1803. BUG_ON(rq->cpu != task_cpu(p));
  1804. BUG_ON(task_current(rq, p));
  1805. BUG_ON(p->nr_cpus_allowed <= 1);
  1806. BUG_ON(!task_on_rq_queued(p));
  1807. BUG_ON(!dl_task(p));
  1808. return p;
  1809. }
  1810. /*
  1811. * See if the non running -deadline tasks on this rq
  1812. * can be sent to some other CPU where they can preempt
  1813. * and start executing.
  1814. */
  1815. static int push_dl_task(struct rq *rq)
  1816. {
  1817. struct task_struct *next_task;
  1818. struct rq *later_rq;
  1819. int ret = 0;
  1820. if (!rq->dl.overloaded)
  1821. return 0;
  1822. next_task = pick_next_pushable_dl_task(rq);
  1823. if (!next_task)
  1824. return 0;
  1825. retry:
  1826. if (WARN_ON(next_task == rq->curr))
  1827. return 0;
  1828. /*
  1829. * If next_task preempts rq->curr, and rq->curr
  1830. * can move away, it makes sense to just reschedule
  1831. * without going further in pushing next_task.
  1832. */
  1833. if (dl_task(rq->curr) &&
  1834. dl_time_before(next_task->dl.deadline, rq->curr->dl.deadline) &&
  1835. rq->curr->nr_cpus_allowed > 1) {
  1836. resched_curr(rq);
  1837. return 0;
  1838. }
  1839. /* We might release rq lock */
  1840. get_task_struct(next_task);
  1841. /* Will lock the rq it'll find */
  1842. later_rq = find_lock_later_rq(next_task, rq);
  1843. if (!later_rq) {
  1844. struct task_struct *task;
  1845. /*
  1846. * We must check all this again, since
  1847. * find_lock_later_rq releases rq->lock and it is
  1848. * then possible that next_task has migrated.
  1849. */
  1850. task = pick_next_pushable_dl_task(rq);
  1851. if (task == next_task) {
  1852. /*
  1853. * The task is still there. We don't try
  1854. * again, some other CPU will pull it when ready.
  1855. */
  1856. goto out;
  1857. }
  1858. if (!task)
  1859. /* No more tasks */
  1860. goto out;
  1861. put_task_struct(next_task);
  1862. next_task = task;
  1863. goto retry;
  1864. }
  1865. deactivate_task(rq, next_task, 0);
  1866. set_task_cpu(next_task, later_rq->cpu);
  1867. /*
  1868. * Update the later_rq clock here, because the clock is used
  1869. * by the cpufreq_update_util() inside __add_running_bw().
  1870. */
  1871. update_rq_clock(later_rq);
  1872. activate_task(later_rq, next_task, ENQUEUE_NOCLOCK);
  1873. ret = 1;
  1874. resched_curr(later_rq);
  1875. double_unlock_balance(rq, later_rq);
  1876. out:
  1877. put_task_struct(next_task);
  1878. return ret;
  1879. }
  1880. static void push_dl_tasks(struct rq *rq)
  1881. {
  1882. /* push_dl_task() will return true if it moved a -deadline task */
  1883. while (push_dl_task(rq))
  1884. ;
  1885. }
  1886. static void pull_dl_task(struct rq *this_rq)
  1887. {
  1888. int this_cpu = this_rq->cpu, cpu;
  1889. struct task_struct *p;
  1890. bool resched = false;
  1891. struct rq *src_rq;
  1892. u64 dmin = LONG_MAX;
  1893. if (likely(!dl_overloaded(this_rq)))
  1894. return;
  1895. /*
  1896. * Match the barrier from dl_set_overloaded; this guarantees that if we
  1897. * see overloaded we must also see the dlo_mask bit.
  1898. */
  1899. smp_rmb();
  1900. for_each_cpu(cpu, this_rq->rd->dlo_mask) {
  1901. if (this_cpu == cpu)
  1902. continue;
  1903. src_rq = cpu_rq(cpu);
  1904. /*
  1905. * It looks racy, abd it is! However, as in sched_rt.c,
  1906. * we are fine with this.
  1907. */
  1908. if (this_rq->dl.dl_nr_running &&
  1909. dl_time_before(this_rq->dl.earliest_dl.curr,
  1910. src_rq->dl.earliest_dl.next))
  1911. continue;
  1912. /* Might drop this_rq->lock */
  1913. double_lock_balance(this_rq, src_rq);
  1914. /*
  1915. * If there are no more pullable tasks on the
  1916. * rq, we're done with it.
  1917. */
  1918. if (src_rq->dl.dl_nr_running <= 1)
  1919. goto skip;
  1920. p = pick_earliest_pushable_dl_task(src_rq, this_cpu);
  1921. /*
  1922. * We found a task to be pulled if:
  1923. * - it preempts our current (if there's one),
  1924. * - it will preempt the last one we pulled (if any).
  1925. */
  1926. if (p && dl_time_before(p->dl.deadline, dmin) &&
  1927. (!this_rq->dl.dl_nr_running ||
  1928. dl_time_before(p->dl.deadline,
  1929. this_rq->dl.earliest_dl.curr))) {
  1930. WARN_ON(p == src_rq->curr);
  1931. WARN_ON(!task_on_rq_queued(p));
  1932. /*
  1933. * Then we pull iff p has actually an earlier
  1934. * deadline than the current task of its runqueue.
  1935. */
  1936. if (dl_time_before(p->dl.deadline,
  1937. src_rq->curr->dl.deadline))
  1938. goto skip;
  1939. resched = true;
  1940. deactivate_task(src_rq, p, 0);
  1941. set_task_cpu(p, this_cpu);
  1942. activate_task(this_rq, p, 0);
  1943. dmin = p->dl.deadline;
  1944. /* Is there any other task even earlier? */
  1945. }
  1946. skip:
  1947. double_unlock_balance(this_rq, src_rq);
  1948. }
  1949. if (resched)
  1950. resched_curr(this_rq);
  1951. }
  1952. /*
  1953. * Since the task is not running and a reschedule is not going to happen
  1954. * anytime soon on its runqueue, we try pushing it away now.
  1955. */
  1956. static void task_woken_dl(struct rq *rq, struct task_struct *p)
  1957. {
  1958. if (!task_running(rq, p) &&
  1959. !test_tsk_need_resched(rq->curr) &&
  1960. p->nr_cpus_allowed > 1 &&
  1961. dl_task(rq->curr) &&
  1962. (rq->curr->nr_cpus_allowed < 2 ||
  1963. !dl_entity_preempt(&p->dl, &rq->curr->dl))) {
  1964. push_dl_tasks(rq);
  1965. }
  1966. }
  1967. static void set_cpus_allowed_dl(struct task_struct *p,
  1968. const struct cpumask *new_mask)
  1969. {
  1970. struct root_domain *src_rd;
  1971. struct rq *rq;
  1972. BUG_ON(!dl_task(p));
  1973. rq = task_rq(p);
  1974. src_rd = rq->rd;
  1975. /*
  1976. * Migrating a SCHED_DEADLINE task between exclusive
  1977. * cpusets (different root_domains) entails a bandwidth
  1978. * update. We already made space for us in the destination
  1979. * domain (see cpuset_can_attach()).
  1980. */
  1981. if (!cpumask_intersects(src_rd->span, new_mask)) {
  1982. struct dl_bw *src_dl_b;
  1983. src_dl_b = dl_bw_of(cpu_of(rq));
  1984. /*
  1985. * We now free resources of the root_domain we are migrating
  1986. * off. In the worst case, sched_setattr() may temporary fail
  1987. * until we complete the update.
  1988. */
  1989. raw_spin_lock(&src_dl_b->lock);
  1990. __dl_sub(src_dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p)));
  1991. raw_spin_unlock(&src_dl_b->lock);
  1992. }
  1993. set_cpus_allowed_common(p, new_mask);
  1994. }
  1995. /* Assumes rq->lock is held */
  1996. static void rq_online_dl(struct rq *rq)
  1997. {
  1998. if (rq->dl.overloaded)
  1999. dl_set_overload(rq);
  2000. cpudl_set_freecpu(&rq->rd->cpudl, rq->cpu);
  2001. if (rq->dl.dl_nr_running > 0)
  2002. cpudl_set(&rq->rd->cpudl, rq->cpu, rq->dl.earliest_dl.curr);
  2003. }
  2004. /* Assumes rq->lock is held */
  2005. static void rq_offline_dl(struct rq *rq)
  2006. {
  2007. if (rq->dl.overloaded)
  2008. dl_clear_overload(rq);
  2009. cpudl_clear(&rq->rd->cpudl, rq->cpu);
  2010. cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu);
  2011. }
  2012. void __init init_sched_dl_class(void)
  2013. {
  2014. unsigned int i;
  2015. for_each_possible_cpu(i)
  2016. zalloc_cpumask_var_node(&per_cpu(local_cpu_mask_dl, i),
  2017. GFP_KERNEL, cpu_to_node(i));
  2018. }
  2019. void dl_add_task_root_domain(struct task_struct *p)
  2020. {
  2021. struct rq_flags rf;
  2022. struct rq *rq;
  2023. struct dl_bw *dl_b;
  2024. raw_spin_lock_irqsave(&p->pi_lock, rf.flags);
  2025. if (!dl_task(p)) {
  2026. raw_spin_unlock_irqrestore(&p->pi_lock, rf.flags);
  2027. return;
  2028. }
  2029. rq = __task_rq_lock(p, &rf);
  2030. dl_b = &rq->rd->dl_bw;
  2031. raw_spin_lock(&dl_b->lock);
  2032. __dl_add(dl_b, p->dl.dl_bw, cpumask_weight(rq->rd->span));
  2033. raw_spin_unlock(&dl_b->lock);
  2034. task_rq_unlock(rq, p, &rf);
  2035. }
  2036. void dl_clear_root_domain(struct root_domain *rd)
  2037. {
  2038. unsigned long flags;
  2039. raw_spin_lock_irqsave(&rd->dl_bw.lock, flags);
  2040. rd->dl_bw.total_bw = 0;
  2041. raw_spin_unlock_irqrestore(&rd->dl_bw.lock, flags);
  2042. }
  2043. #endif /* CONFIG_SMP */
  2044. static void switched_from_dl(struct rq *rq, struct task_struct *p)
  2045. {
  2046. /*
  2047. * task_non_contending() can start the "inactive timer" (if the 0-lag
  2048. * time is in the future). If the task switches back to dl before
  2049. * the "inactive timer" fires, it can continue to consume its current
  2050. * runtime using its current deadline. If it stays outside of
  2051. * SCHED_DEADLINE until the 0-lag time passes, inactive_task_timer()
  2052. * will reset the task parameters.
  2053. */
  2054. if (task_on_rq_queued(p) && p->dl.dl_runtime)
  2055. task_non_contending(p);
  2056. if (!task_on_rq_queued(p)) {
  2057. /*
  2058. * Inactive timer is armed. However, p is leaving DEADLINE and
  2059. * might migrate away from this rq while continuing to run on
  2060. * some other class. We need to remove its contribution from
  2061. * this rq running_bw now, or sub_rq_bw (below) will complain.
  2062. */
  2063. if (p->dl.dl_non_contending)
  2064. sub_running_bw(&p->dl, &rq->dl);
  2065. sub_rq_bw(&p->dl, &rq->dl);
  2066. }
  2067. /*
  2068. * We cannot use inactive_task_timer() to invoke sub_running_bw()
  2069. * at the 0-lag time, because the task could have been migrated
  2070. * while SCHED_OTHER in the meanwhile.
  2071. */
  2072. if (p->dl.dl_non_contending)
  2073. p->dl.dl_non_contending = 0;
  2074. /*
  2075. * Since this might be the only -deadline task on the rq,
  2076. * this is the right place to try to pull some other one
  2077. * from an overloaded CPU, if any.
  2078. */
  2079. if (!task_on_rq_queued(p) || rq->dl.dl_nr_running)
  2080. return;
  2081. deadline_queue_pull_task(rq);
  2082. }
  2083. /*
  2084. * When switching to -deadline, we may overload the rq, then
  2085. * we try to push someone off, if possible.
  2086. */
  2087. static void switched_to_dl(struct rq *rq, struct task_struct *p)
  2088. {
  2089. if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1)
  2090. put_task_struct(p);
  2091. /* If p is not queued we will update its parameters at next wakeup. */
  2092. if (!task_on_rq_queued(p)) {
  2093. add_rq_bw(&p->dl, &rq->dl);
  2094. return;
  2095. }
  2096. if (rq->curr != p) {
  2097. #ifdef CONFIG_SMP
  2098. if (p->nr_cpus_allowed > 1 && rq->dl.overloaded)
  2099. deadline_queue_push_tasks(rq);
  2100. #endif
  2101. if (dl_task(rq->curr))
  2102. check_preempt_curr_dl(rq, p, 0);
  2103. else
  2104. resched_curr(rq);
  2105. } else {
  2106. update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 0);
  2107. }
  2108. }
  2109. /*
  2110. * If the scheduling parameters of a -deadline task changed,
  2111. * a push or pull operation might be needed.
  2112. */
  2113. static void prio_changed_dl(struct rq *rq, struct task_struct *p,
  2114. int oldprio)
  2115. {
  2116. if (task_on_rq_queued(p) || rq->curr == p) {
  2117. #ifdef CONFIG_SMP
  2118. /*
  2119. * This might be too much, but unfortunately
  2120. * we don't have the old deadline value, and
  2121. * we can't argue if the task is increasing
  2122. * or lowering its prio, so...
  2123. */
  2124. if (!rq->dl.overloaded)
  2125. deadline_queue_pull_task(rq);
  2126. /*
  2127. * If we now have a earlier deadline task than p,
  2128. * then reschedule, provided p is still on this
  2129. * runqueue.
  2130. */
  2131. if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline))
  2132. resched_curr(rq);
  2133. #else
  2134. /*
  2135. * Again, we don't know if p has a earlier
  2136. * or later deadline, so let's blindly set a
  2137. * (maybe not needed) rescheduling point.
  2138. */
  2139. resched_curr(rq);
  2140. #endif /* CONFIG_SMP */
  2141. }
  2142. }
  2143. const struct sched_class dl_sched_class
  2144. __section("__dl_sched_class") = {
  2145. .enqueue_task = enqueue_task_dl,
  2146. .dequeue_task = dequeue_task_dl,
  2147. .yield_task = yield_task_dl,
  2148. .check_preempt_curr = check_preempt_curr_dl,
  2149. .pick_next_task = pick_next_task_dl,
  2150. .put_prev_task = put_prev_task_dl,
  2151. .set_next_task = set_next_task_dl,
  2152. #ifdef CONFIG_SMP
  2153. .balance = balance_dl,
  2154. .select_task_rq = select_task_rq_dl,
  2155. .migrate_task_rq = migrate_task_rq_dl,
  2156. .set_cpus_allowed = set_cpus_allowed_dl,
  2157. .rq_online = rq_online_dl,
  2158. .rq_offline = rq_offline_dl,
  2159. .task_woken = task_woken_dl,
  2160. #endif
  2161. .task_tick = task_tick_dl,
  2162. .task_fork = task_fork_dl,
  2163. .prio_changed = prio_changed_dl,
  2164. .switched_from = switched_from_dl,
  2165. .switched_to = switched_to_dl,
  2166. .update_curr = update_curr_dl,
  2167. };
  2168. int sched_dl_global_validate(void)
  2169. {
  2170. u64 runtime = global_rt_runtime();
  2171. u64 period = global_rt_period();
  2172. u64 new_bw = to_ratio(period, runtime);
  2173. struct dl_bw *dl_b;
  2174. int cpu, cpus, ret = 0;
  2175. unsigned long flags;
  2176. /*
  2177. * Here we want to check the bandwidth not being set to some
  2178. * value smaller than the currently allocated bandwidth in
  2179. * any of the root_domains.
  2180. *
  2181. * FIXME: Cycling on all the CPUs is overdoing, but simpler than
  2182. * cycling on root_domains... Discussion on different/better
  2183. * solutions is welcome!
  2184. */
  2185. for_each_possible_cpu(cpu) {
  2186. rcu_read_lock_sched();
  2187. dl_b = dl_bw_of(cpu);
  2188. cpus = dl_bw_cpus(cpu);
  2189. raw_spin_lock_irqsave(&dl_b->lock, flags);
  2190. if (new_bw * cpus < dl_b->total_bw)
  2191. ret = -EBUSY;
  2192. raw_spin_unlock_irqrestore(&dl_b->lock, flags);
  2193. rcu_read_unlock_sched();
  2194. if (ret)
  2195. break;
  2196. }
  2197. return ret;
  2198. }
  2199. static void init_dl_rq_bw_ratio(struct dl_rq *dl_rq)
  2200. {
  2201. if (global_rt_runtime() == RUNTIME_INF) {
  2202. dl_rq->bw_ratio = 1 << RATIO_SHIFT;
  2203. dl_rq->extra_bw = 1 << BW_SHIFT;
  2204. } else {
  2205. dl_rq->bw_ratio = to_ratio(global_rt_runtime(),
  2206. global_rt_period()) >> (BW_SHIFT - RATIO_SHIFT);
  2207. dl_rq->extra_bw = to_ratio(global_rt_period(),
  2208. global_rt_runtime());
  2209. }
  2210. }
  2211. void sched_dl_do_global(void)
  2212. {
  2213. u64 new_bw = -1;
  2214. struct dl_bw *dl_b;
  2215. int cpu;
  2216. unsigned long flags;
  2217. def_dl_bandwidth.dl_period = global_rt_period();
  2218. def_dl_bandwidth.dl_runtime = global_rt_runtime();
  2219. if (global_rt_runtime() != RUNTIME_INF)
  2220. new_bw = to_ratio(global_rt_period(), global_rt_runtime());
  2221. /*
  2222. * FIXME: As above...
  2223. */
  2224. for_each_possible_cpu(cpu) {
  2225. rcu_read_lock_sched();
  2226. dl_b = dl_bw_of(cpu);
  2227. raw_spin_lock_irqsave(&dl_b->lock, flags);
  2228. dl_b->bw = new_bw;
  2229. raw_spin_unlock_irqrestore(&dl_b->lock, flags);
  2230. rcu_read_unlock_sched();
  2231. init_dl_rq_bw_ratio(&cpu_rq(cpu)->dl);
  2232. }
  2233. }
  2234. /*
  2235. * We must be sure that accepting a new task (or allowing changing the
  2236. * parameters of an existing one) is consistent with the bandwidth
  2237. * constraints. If yes, this function also accordingly updates the currently
  2238. * allocated bandwidth to reflect the new situation.
  2239. *
  2240. * This function is called while holding p's rq->lock.
  2241. */
  2242. int sched_dl_overflow(struct task_struct *p, int policy,
  2243. const struct sched_attr *attr)
  2244. {
  2245. u64 period = attr->sched_period ?: attr->sched_deadline;
  2246. u64 runtime = attr->sched_runtime;
  2247. u64 new_bw = dl_policy(policy) ? to_ratio(period, runtime) : 0;
  2248. int cpus, err = -1, cpu = task_cpu(p);
  2249. struct dl_bw *dl_b = dl_bw_of(cpu);
  2250. unsigned long cap;
  2251. if (attr->sched_flags & SCHED_FLAG_SUGOV)
  2252. return 0;
  2253. /* !deadline task may carry old deadline bandwidth */
  2254. if (new_bw == p->dl.dl_bw && task_has_dl_policy(p))
  2255. return 0;
  2256. /*
  2257. * Either if a task, enters, leave, or stays -deadline but changes
  2258. * its parameters, we may need to update accordingly the total
  2259. * allocated bandwidth of the container.
  2260. */
  2261. raw_spin_lock(&dl_b->lock);
  2262. cpus = dl_bw_cpus(cpu);
  2263. cap = dl_bw_capacity(cpu);
  2264. if (dl_policy(policy) && !task_has_dl_policy(p) &&
  2265. !__dl_overflow(dl_b, cap, 0, new_bw)) {
  2266. if (hrtimer_active(&p->dl.inactive_timer))
  2267. __dl_sub(dl_b, p->dl.dl_bw, cpus);
  2268. __dl_add(dl_b, new_bw, cpus);
  2269. err = 0;
  2270. } else if (dl_policy(policy) && task_has_dl_policy(p) &&
  2271. !__dl_overflow(dl_b, cap, p->dl.dl_bw, new_bw)) {
  2272. /*
  2273. * XXX this is slightly incorrect: when the task
  2274. * utilization decreases, we should delay the total
  2275. * utilization change until the task's 0-lag point.
  2276. * But this would require to set the task's "inactive
  2277. * timer" when the task is not inactive.
  2278. */
  2279. __dl_sub(dl_b, p->dl.dl_bw, cpus);
  2280. __dl_add(dl_b, new_bw, cpus);
  2281. dl_change_utilization(p, new_bw);
  2282. err = 0;
  2283. } else if (!dl_policy(policy) && task_has_dl_policy(p)) {
  2284. /*
  2285. * Do not decrease the total deadline utilization here,
  2286. * switched_from_dl() will take care to do it at the correct
  2287. * (0-lag) time.
  2288. */
  2289. err = 0;
  2290. }
  2291. raw_spin_unlock(&dl_b->lock);
  2292. return err;
  2293. }
  2294. /*
  2295. * This function initializes the sched_dl_entity of a newly becoming
  2296. * SCHED_DEADLINE task.
  2297. *
  2298. * Only the static values are considered here, the actual runtime and the
  2299. * absolute deadline will be properly calculated when the task is enqueued
  2300. * for the first time with its new policy.
  2301. */
  2302. void __setparam_dl(struct task_struct *p, const struct sched_attr *attr)
  2303. {
  2304. struct sched_dl_entity *dl_se = &p->dl;
  2305. dl_se->dl_runtime = attr->sched_runtime;
  2306. dl_se->dl_deadline = attr->sched_deadline;
  2307. dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline;
  2308. dl_se->flags = attr->sched_flags & SCHED_DL_FLAGS;
  2309. dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime);
  2310. dl_se->dl_density = to_ratio(dl_se->dl_deadline, dl_se->dl_runtime);
  2311. }
  2312. void __getparam_dl(struct task_struct *p, struct sched_attr *attr)
  2313. {
  2314. struct sched_dl_entity *dl_se = &p->dl;
  2315. attr->sched_priority = p->rt_priority;
  2316. attr->sched_runtime = dl_se->dl_runtime;
  2317. attr->sched_deadline = dl_se->dl_deadline;
  2318. attr->sched_period = dl_se->dl_period;
  2319. attr->sched_flags &= ~SCHED_DL_FLAGS;
  2320. attr->sched_flags |= dl_se->flags;
  2321. }
  2322. /*
  2323. * Default limits for DL period; on the top end we guard against small util
  2324. * tasks still getting rediculous long effective runtimes, on the bottom end we
  2325. * guard against timer DoS.
  2326. */
  2327. unsigned int sysctl_sched_dl_period_max = 1 << 22; /* ~4 seconds */
  2328. unsigned int sysctl_sched_dl_period_min = 100; /* 100 us */
  2329. /*
  2330. * This function validates the new parameters of a -deadline task.
  2331. * We ask for the deadline not being zero, and greater or equal
  2332. * than the runtime, as well as the period of being zero or
  2333. * greater than deadline. Furthermore, we have to be sure that
  2334. * user parameters are above the internal resolution of 1us (we
  2335. * check sched_runtime only since it is always the smaller one) and
  2336. * below 2^63 ns (we have to check both sched_deadline and
  2337. * sched_period, as the latter can be zero).
  2338. */
  2339. bool __checkparam_dl(const struct sched_attr *attr)
  2340. {
  2341. u64 period, max, min;
  2342. /* special dl tasks don't actually use any parameter */
  2343. if (attr->sched_flags & SCHED_FLAG_SUGOV)
  2344. return true;
  2345. /* deadline != 0 */
  2346. if (attr->sched_deadline == 0)
  2347. return false;
  2348. /*
  2349. * Since we truncate DL_SCALE bits, make sure we're at least
  2350. * that big.
  2351. */
  2352. if (attr->sched_runtime < (1ULL << DL_SCALE))
  2353. return false;
  2354. /*
  2355. * Since we use the MSB for wrap-around and sign issues, make
  2356. * sure it's not set (mind that period can be equal to zero).
  2357. */
  2358. if (attr->sched_deadline & (1ULL << 63) ||
  2359. attr->sched_period & (1ULL << 63))
  2360. return false;
  2361. period = attr->sched_period;
  2362. if (!period)
  2363. period = attr->sched_deadline;
  2364. /* runtime <= deadline <= period (if period != 0) */
  2365. if (period < attr->sched_deadline ||
  2366. attr->sched_deadline < attr->sched_runtime)
  2367. return false;
  2368. max = (u64)READ_ONCE(sysctl_sched_dl_period_max) * NSEC_PER_USEC;
  2369. min = (u64)READ_ONCE(sysctl_sched_dl_period_min) * NSEC_PER_USEC;
  2370. if (period < min || period > max)
  2371. return false;
  2372. return true;
  2373. }
  2374. /*
  2375. * This function clears the sched_dl_entity static params.
  2376. */
  2377. void __dl_clear_params(struct task_struct *p)
  2378. {
  2379. struct sched_dl_entity *dl_se = &p->dl;
  2380. dl_se->dl_runtime = 0;
  2381. dl_se->dl_deadline = 0;
  2382. dl_se->dl_period = 0;
  2383. dl_se->flags = 0;
  2384. dl_se->dl_bw = 0;
  2385. dl_se->dl_density = 0;
  2386. dl_se->dl_throttled = 0;
  2387. dl_se->dl_yielded = 0;
  2388. dl_se->dl_non_contending = 0;
  2389. dl_se->dl_overrun = 0;
  2390. #ifdef CONFIG_RT_MUTEXES
  2391. dl_se->pi_se = dl_se;
  2392. #endif
  2393. }
  2394. bool dl_param_changed(struct task_struct *p, const struct sched_attr *attr)
  2395. {
  2396. struct sched_dl_entity *dl_se = &p->dl;
  2397. if (dl_se->dl_runtime != attr->sched_runtime ||
  2398. dl_se->dl_deadline != attr->sched_deadline ||
  2399. dl_se->dl_period != attr->sched_period ||
  2400. dl_se->flags != (attr->sched_flags & SCHED_DL_FLAGS))
  2401. return true;
  2402. return false;
  2403. }
  2404. #ifdef CONFIG_SMP
  2405. int dl_task_can_attach(struct task_struct *p, const struct cpumask *cs_cpus_allowed)
  2406. {
  2407. unsigned long flags, cap;
  2408. unsigned int dest_cpu;
  2409. struct dl_bw *dl_b;
  2410. bool overflow;
  2411. int ret;
  2412. dest_cpu = cpumask_any_and(cpu_active_mask, cs_cpus_allowed);
  2413. rcu_read_lock_sched();
  2414. dl_b = dl_bw_of(dest_cpu);
  2415. raw_spin_lock_irqsave(&dl_b->lock, flags);
  2416. cap = dl_bw_capacity(dest_cpu);
  2417. overflow = __dl_overflow(dl_b, cap, 0, p->dl.dl_bw);
  2418. if (overflow) {
  2419. ret = -EBUSY;
  2420. } else {
  2421. /*
  2422. * We reserve space for this task in the destination
  2423. * root_domain, as we can't fail after this point.
  2424. * We will free resources in the source root_domain
  2425. * later on (see set_cpus_allowed_dl()).
  2426. */
  2427. int cpus = dl_bw_cpus(dest_cpu);
  2428. __dl_add(dl_b, p->dl.dl_bw, cpus);
  2429. ret = 0;
  2430. }
  2431. raw_spin_unlock_irqrestore(&dl_b->lock, flags);
  2432. rcu_read_unlock_sched();
  2433. return ret;
  2434. }
  2435. int dl_cpuset_cpumask_can_shrink(const struct cpumask *cur,
  2436. const struct cpumask *trial)
  2437. {
  2438. int ret = 1, trial_cpus;
  2439. struct dl_bw *cur_dl_b;
  2440. unsigned long flags;
  2441. rcu_read_lock_sched();
  2442. cur_dl_b = dl_bw_of(cpumask_any(cur));
  2443. trial_cpus = cpumask_weight(trial);
  2444. raw_spin_lock_irqsave(&cur_dl_b->lock, flags);
  2445. if (cur_dl_b->bw != -1 &&
  2446. cur_dl_b->bw * trial_cpus < cur_dl_b->total_bw)
  2447. ret = 0;
  2448. raw_spin_unlock_irqrestore(&cur_dl_b->lock, flags);
  2449. rcu_read_unlock_sched();
  2450. return ret;
  2451. }
  2452. bool dl_cpu_busy(unsigned int cpu)
  2453. {
  2454. unsigned long flags, cap;
  2455. struct dl_bw *dl_b;
  2456. bool overflow;
  2457. rcu_read_lock_sched();
  2458. dl_b = dl_bw_of(cpu);
  2459. raw_spin_lock_irqsave(&dl_b->lock, flags);
  2460. cap = dl_bw_capacity(cpu);
  2461. overflow = __dl_overflow(dl_b, cap, 0, 0);
  2462. raw_spin_unlock_irqrestore(&dl_b->lock, flags);
  2463. rcu_read_unlock_sched();
  2464. return overflow;
  2465. }
  2466. #endif
  2467. #ifdef CONFIG_SCHED_DEBUG
  2468. void print_dl_stats(struct seq_file *m, int cpu)
  2469. {
  2470. print_dl_rq(m, cpu, &cpu_rq(cpu)->dl);
  2471. }
  2472. #endif /* CONFIG_SCHED_DEBUG */