sched_fair.c 108 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385338633873388338933903391339233933394339533963397339833993400340134023403340434053406340734083409341034113412341334143415341634173418341934203421342234233424342534263427342834293430343134323433343434353436343734383439344034413442344334443445344634473448344934503451345234533454345534563457345834593460346134623463346434653466346734683469347034713472347334743475347634773478347934803481348234833484348534863487348834893490349134923493349434953496349734983499350035013502350335043505350635073508350935103511351235133514351535163517351835193520352135223523352435253526352735283529353035313532353335343535353635373538353935403541354235433544354535463547354835493550355135523553355435553556355735583559356035613562356335643565356635673568356935703571357235733574357535763577357835793580358135823583358435853586358735883589359035913592359335943595359635973598359936003601360236033604360536063607360836093610361136123613361436153616361736183619362036213622362336243625362636273628362936303631363236333634363536363637363836393640364136423643364436453646364736483649365036513652365336543655365636573658365936603661366236633664366536663667366836693670367136723673367436753676367736783679368036813682368336843685368636873688368936903691369236933694369536963697369836993700370137023703370437053706370737083709371037113712371337143715371637173718371937203721372237233724372537263727372837293730373137323733373437353736373737383739374037413742374337443745374637473748374937503751375237533754375537563757375837593760376137623763376437653766376737683769377037713772377337743775377637773778377937803781378237833784378537863787378837893790379137923793379437953796379737983799380038013802380338043805380638073808380938103811381238133814381538163817381838193820382138223823382438253826382738283829383038313832383338343835383638373838383938403841384238433844384538463847384838493850385138523853385438553856385738583859386038613862386338643865386638673868386938703871387238733874387538763877387838793880388138823883388438853886388738883889389038913892389338943895389638973898389939003901390239033904390539063907390839093910391139123913391439153916391739183919392039213922392339243925392639273928392939303931393239333934393539363937393839393940394139423943394439453946394739483949395039513952395339543955395639573958395939603961396239633964396539663967396839693970397139723973397439753976397739783979398039813982398339843985398639873988398939903991399239933994399539963997399839994000400140024003400440054006400740084009401040114012401340144015401640174018401940204021402240234024402540264027402840294030403140324033403440354036403740384039404040414042404340444045404640474048404940504051405240534054405540564057405840594060406140624063406440654066406740684069407040714072407340744075407640774078407940804081408240834084408540864087408840894090409140924093409440954096409740984099410041014102410341044105410641074108410941104111411241134114411541164117411841194120412141224123412441254126412741284129413041314132413341344135413641374138413941404141414241434144414541464147414841494150415141524153415441554156415741584159416041614162416341644165416641674168416941704171417241734174417541764177417841794180418141824183418441854186418741884189419041914192419341944195419641974198419942004201420242034204420542064207420842094210421142124213421442154216
  1. /*
  2. * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH)
  3. *
  4. * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
  5. *
  6. * Interactivity improvements by Mike Galbraith
  7. * (C) 2007 Mike Galbraith <efault@gmx.de>
  8. *
  9. * Various enhancements by Dmitry Adamushko.
  10. * (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
  11. *
  12. * Group scheduling enhancements by Srivatsa Vaddagiri
  13. * Copyright IBM Corporation, 2007
  14. * Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
  15. *
  16. * Scaled math optimizations by Thomas Gleixner
  17. * Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
  18. *
  19. * Adaptive scheduling granularity, math enhancements by Peter Zijlstra
  20. * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
  21. */
  22. #include <linux/latencytop.h>
  23. #include <linux/sched.h>
  24. /*
  25. * Targeted preemption latency for CPU-bound tasks:
  26. * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds)
  27. *
  28. * NOTE: this latency value is not the same as the concept of
  29. * 'timeslice length' - timeslices in CFS are of variable length
  30. * and have no persistent notion like in traditional, time-slice
  31. * based scheduling concepts.
  32. *
  33. * (to see the precise effective timeslice length of your workload,
  34. * run vmstat and monitor the context-switches (cs) field)
  35. */
  36. unsigned int sysctl_sched_latency = 6000000ULL;
  37. unsigned int normalized_sysctl_sched_latency = 6000000ULL;
  38. /*
  39. * The initial- and re-scaling of tunables is configurable
  40. * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus))
  41. *
  42. * Options are:
  43. * SCHED_TUNABLESCALING_NONE - unscaled, always *1
  44. * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus)
  45. * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
  46. */
  47. enum sched_tunable_scaling sysctl_sched_tunable_scaling
  48. = SCHED_TUNABLESCALING_LOG;
  49. /*
  50. * Minimal preemption granularity for CPU-bound tasks:
  51. * (default: 0.75 msec * (1 + ilog(ncpus)), units: nanoseconds)
  52. */
  53. unsigned int sysctl_sched_min_granularity = 750000ULL;
  54. unsigned int normalized_sysctl_sched_min_granularity = 750000ULL;
  55. /*
  56. * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
  57. */
  58. static unsigned int sched_nr_latency = 8;
  59. /*
  60. * After fork, child runs first. If set to 0 (default) then
  61. * parent will (try to) run first.
  62. */
  63. unsigned int sysctl_sched_child_runs_first __read_mostly;
  64. /*
  65. * sys_sched_yield() compat mode
  66. *
  67. * This option switches the agressive yield implementation of the
  68. * old scheduler back on.
  69. */
  70. unsigned int __read_mostly sysctl_sched_compat_yield;
  71. /*
  72. * SCHED_OTHER wake-up granularity.
  73. * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
  74. *
  75. * This option delays the preemption effects of decoupled workloads
  76. * and reduces their over-scheduling. Synchronous workloads will still
  77. * have immediate wakeup/sleep latencies.
  78. */
  79. unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
  80. unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
  81. const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
  82. /*
  83. * The exponential sliding window over which load is averaged for shares
  84. * distribution.
  85. * (default: 10msec)
  86. */
  87. unsigned int __read_mostly sysctl_sched_shares_window = 10000000UL;
  88. static const struct sched_class fair_sched_class;
  89. /**************************************************************
  90. * CFS operations on generic schedulable entities:
  91. */
  92. #ifdef CONFIG_FAIR_GROUP_SCHED
  93. /* cpu runqueue to which this cfs_rq is attached */
  94. static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
  95. {
  96. return cfs_rq->rq;
  97. }
  98. /* An entity is a task if it doesn't "own" a runqueue */
  99. #define entity_is_task(se) (!se->my_q)
  100. static inline struct task_struct *task_of(struct sched_entity *se)
  101. {
  102. #ifdef CONFIG_SCHED_DEBUG
  103. WARN_ON_ONCE(!entity_is_task(se));
  104. #endif
  105. return container_of(se, struct task_struct, se);
  106. }
  107. /* Walk up scheduling entities hierarchy */
  108. #define for_each_sched_entity(se) \
  109. for (; se; se = se->parent)
  110. static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
  111. {
  112. return p->se.cfs_rq;
  113. }
  114. /* runqueue on which this entity is (to be) queued */
  115. static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
  116. {
  117. return se->cfs_rq;
  118. }
  119. /* runqueue "owned" by this group */
  120. static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
  121. {
  122. return grp->my_q;
  123. }
  124. /* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on
  125. * another cpu ('this_cpu')
  126. */
  127. static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
  128. {
  129. return cfs_rq->tg->cfs_rq[this_cpu];
  130. }
  131. static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
  132. {
  133. if (!cfs_rq->on_list) {
  134. /*
  135. * Ensure we either appear before our parent (if already
  136. * enqueued) or force our parent to appear after us when it is
  137. * enqueued. The fact that we always enqueue bottom-up
  138. * reduces this to two cases.
  139. */
  140. if (cfs_rq->tg->parent &&
  141. cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
  142. list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
  143. &rq_of(cfs_rq)->leaf_cfs_rq_list);
  144. } else {
  145. list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
  146. &rq_of(cfs_rq)->leaf_cfs_rq_list);
  147. }
  148. cfs_rq->on_list = 1;
  149. }
  150. }
  151. static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
  152. {
  153. if (cfs_rq->on_list) {
  154. list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
  155. cfs_rq->on_list = 0;
  156. }
  157. }
  158. /* Iterate thr' all leaf cfs_rq's on a runqueue */
  159. #define for_each_leaf_cfs_rq(rq, cfs_rq) \
  160. list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
  161. /* Do the two (enqueued) entities belong to the same group ? */
  162. static inline int
  163. is_same_group(struct sched_entity *se, struct sched_entity *pse)
  164. {
  165. if (se->cfs_rq == pse->cfs_rq)
  166. return 1;
  167. return 0;
  168. }
  169. static inline struct sched_entity *parent_entity(struct sched_entity *se)
  170. {
  171. return se->parent;
  172. }
  173. /* return depth at which a sched entity is present in the hierarchy */
  174. static inline int depth_se(struct sched_entity *se)
  175. {
  176. int depth = 0;
  177. for_each_sched_entity(se)
  178. depth++;
  179. return depth;
  180. }
  181. static void
  182. find_matching_se(struct sched_entity **se, struct sched_entity **pse)
  183. {
  184. int se_depth, pse_depth;
  185. /*
  186. * preemption test can be made between sibling entities who are in the
  187. * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
  188. * both tasks until we find their ancestors who are siblings of common
  189. * parent.
  190. */
  191. /* First walk up until both entities are at same depth */
  192. se_depth = depth_se(*se);
  193. pse_depth = depth_se(*pse);
  194. while (se_depth > pse_depth) {
  195. se_depth--;
  196. *se = parent_entity(*se);
  197. }
  198. while (pse_depth > se_depth) {
  199. pse_depth--;
  200. *pse = parent_entity(*pse);
  201. }
  202. while (!is_same_group(*se, *pse)) {
  203. *se = parent_entity(*se);
  204. *pse = parent_entity(*pse);
  205. }
  206. }
  207. #else /* !CONFIG_FAIR_GROUP_SCHED */
  208. static inline struct task_struct *task_of(struct sched_entity *se)
  209. {
  210. return container_of(se, struct task_struct, se);
  211. }
  212. static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
  213. {
  214. return container_of(cfs_rq, struct rq, cfs);
  215. }
  216. #define entity_is_task(se) 1
  217. #define for_each_sched_entity(se) \
  218. for (; se; se = NULL)
  219. static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
  220. {
  221. return &task_rq(p)->cfs;
  222. }
  223. static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
  224. {
  225. struct task_struct *p = task_of(se);
  226. struct rq *rq = task_rq(p);
  227. return &rq->cfs;
  228. }
  229. /* runqueue "owned" by this group */
  230. static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
  231. {
  232. return NULL;
  233. }
  234. static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
  235. {
  236. return &cpu_rq(this_cpu)->cfs;
  237. }
  238. static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
  239. {
  240. }
  241. static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
  242. {
  243. }
  244. #define for_each_leaf_cfs_rq(rq, cfs_rq) \
  245. for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
  246. static inline int
  247. is_same_group(struct sched_entity *se, struct sched_entity *pse)
  248. {
  249. return 1;
  250. }
  251. static inline struct sched_entity *parent_entity(struct sched_entity *se)
  252. {
  253. return NULL;
  254. }
  255. static inline void
  256. find_matching_se(struct sched_entity **se, struct sched_entity **pse)
  257. {
  258. }
  259. #endif /* CONFIG_FAIR_GROUP_SCHED */
  260. /**************************************************************
  261. * Scheduling class tree data structure manipulation methods:
  262. */
  263. static inline u64 max_vruntime(u64 min_vruntime, u64 vruntime)
  264. {
  265. s64 delta = (s64)(vruntime - min_vruntime);
  266. if (delta > 0)
  267. min_vruntime = vruntime;
  268. return min_vruntime;
  269. }
  270. static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
  271. {
  272. s64 delta = (s64)(vruntime - min_vruntime);
  273. if (delta < 0)
  274. min_vruntime = vruntime;
  275. return min_vruntime;
  276. }
  277. static inline int entity_before(struct sched_entity *a,
  278. struct sched_entity *b)
  279. {
  280. return (s64)(a->vruntime - b->vruntime) < 0;
  281. }
  282. static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
  283. {
  284. return se->vruntime - cfs_rq->min_vruntime;
  285. }
  286. static void update_min_vruntime(struct cfs_rq *cfs_rq)
  287. {
  288. u64 vruntime = cfs_rq->min_vruntime;
  289. if (cfs_rq->curr)
  290. vruntime = cfs_rq->curr->vruntime;
  291. if (cfs_rq->rb_leftmost) {
  292. struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
  293. struct sched_entity,
  294. run_node);
  295. if (!cfs_rq->curr)
  296. vruntime = se->vruntime;
  297. else
  298. vruntime = min_vruntime(vruntime, se->vruntime);
  299. }
  300. cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
  301. }
  302. /*
  303. * Enqueue an entity into the rb-tree:
  304. */
  305. static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  306. {
  307. struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
  308. struct rb_node *parent = NULL;
  309. struct sched_entity *entry;
  310. s64 key = entity_key(cfs_rq, se);
  311. int leftmost = 1;
  312. /*
  313. * Find the right place in the rbtree:
  314. */
  315. while (*link) {
  316. parent = *link;
  317. entry = rb_entry(parent, struct sched_entity, run_node);
  318. /*
  319. * We dont care about collisions. Nodes with
  320. * the same key stay together.
  321. */
  322. if (key < entity_key(cfs_rq, entry)) {
  323. link = &parent->rb_left;
  324. } else {
  325. link = &parent->rb_right;
  326. leftmost = 0;
  327. }
  328. }
  329. /*
  330. * Maintain a cache of leftmost tree entries (it is frequently
  331. * used):
  332. */
  333. if (leftmost)
  334. cfs_rq->rb_leftmost = &se->run_node;
  335. rb_link_node(&se->run_node, parent, link);
  336. rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
  337. }
  338. static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  339. {
  340. if (cfs_rq->rb_leftmost == &se->run_node) {
  341. struct rb_node *next_node;
  342. next_node = rb_next(&se->run_node);
  343. cfs_rq->rb_leftmost = next_node;
  344. }
  345. rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
  346. }
  347. static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
  348. {
  349. struct rb_node *left = cfs_rq->rb_leftmost;
  350. if (!left)
  351. return NULL;
  352. return rb_entry(left, struct sched_entity, run_node);
  353. }
  354. static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
  355. {
  356. struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
  357. if (!last)
  358. return NULL;
  359. return rb_entry(last, struct sched_entity, run_node);
  360. }
  361. /**************************************************************
  362. * Scheduling class statistics methods:
  363. */
  364. #ifdef CONFIG_SCHED_DEBUG
  365. int sched_proc_update_handler(struct ctl_table *table, int write,
  366. void __user *buffer, size_t *lenp,
  367. loff_t *ppos)
  368. {
  369. int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
  370. int factor = get_update_sysctl_factor();
  371. if (ret || !write)
  372. return ret;
  373. sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
  374. sysctl_sched_min_granularity);
  375. #define WRT_SYSCTL(name) \
  376. (normalized_sysctl_##name = sysctl_##name / (factor))
  377. WRT_SYSCTL(sched_min_granularity);
  378. WRT_SYSCTL(sched_latency);
  379. WRT_SYSCTL(sched_wakeup_granularity);
  380. #undef WRT_SYSCTL
  381. return 0;
  382. }
  383. #endif
  384. /*
  385. * delta /= w
  386. */
  387. static inline unsigned long
  388. calc_delta_fair(unsigned long delta, struct sched_entity *se)
  389. {
  390. if (unlikely(se->load.weight != NICE_0_LOAD))
  391. delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
  392. return delta;
  393. }
  394. /*
  395. * The idea is to set a period in which each task runs once.
  396. *
  397. * When there are too many tasks (sysctl_sched_nr_latency) we have to stretch
  398. * this period because otherwise the slices get too small.
  399. *
  400. * p = (nr <= nl) ? l : l*nr/nl
  401. */
  402. static u64 __sched_period(unsigned long nr_running)
  403. {
  404. u64 period = sysctl_sched_latency;
  405. unsigned long nr_latency = sched_nr_latency;
  406. if (unlikely(nr_running > nr_latency)) {
  407. period = sysctl_sched_min_granularity;
  408. period *= nr_running;
  409. }
  410. return period;
  411. }
  412. /*
  413. * We calculate the wall-time slice from the period by taking a part
  414. * proportional to the weight.
  415. *
  416. * s = p*P[w/rw]
  417. */
  418. static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
  419. {
  420. u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
  421. for_each_sched_entity(se) {
  422. struct load_weight *load;
  423. struct load_weight lw;
  424. cfs_rq = cfs_rq_of(se);
  425. load = &cfs_rq->load;
  426. if (unlikely(!se->on_rq)) {
  427. lw = cfs_rq->load;
  428. update_load_add(&lw, se->load.weight);
  429. load = &lw;
  430. }
  431. slice = calc_delta_mine(slice, se->load.weight, load);
  432. }
  433. return slice;
  434. }
  435. /*
  436. * We calculate the vruntime slice of a to be inserted task
  437. *
  438. * vs = s/w
  439. */
  440. static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
  441. {
  442. return calc_delta_fair(sched_slice(cfs_rq, se), se);
  443. }
  444. static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update);
  445. static void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta);
  446. /*
  447. * Update the current task's runtime statistics. Skip current tasks that
  448. * are not in our scheduling class.
  449. */
  450. static inline void
  451. __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
  452. unsigned long delta_exec)
  453. {
  454. unsigned long delta_exec_weighted;
  455. schedstat_set(curr->statistics.exec_max,
  456. max((u64)delta_exec, curr->statistics.exec_max));
  457. curr->sum_exec_runtime += delta_exec;
  458. schedstat_add(cfs_rq, exec_clock, delta_exec);
  459. delta_exec_weighted = calc_delta_fair(delta_exec, curr);
  460. curr->vruntime += delta_exec_weighted;
  461. update_min_vruntime(cfs_rq);
  462. #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
  463. cfs_rq->load_unacc_exec_time += delta_exec;
  464. #endif
  465. }
  466. static void update_curr(struct cfs_rq *cfs_rq)
  467. {
  468. struct sched_entity *curr = cfs_rq->curr;
  469. u64 now = rq_of(cfs_rq)->clock_task;
  470. unsigned long delta_exec;
  471. if (unlikely(!curr))
  472. return;
  473. /*
  474. * Get the amount of time the current task was running
  475. * since the last time we changed load (this cannot
  476. * overflow on 32 bits):
  477. */
  478. delta_exec = (unsigned long)(now - curr->exec_start);
  479. if (!delta_exec)
  480. return;
  481. __update_curr(cfs_rq, curr, delta_exec);
  482. curr->exec_start = now;
  483. if (entity_is_task(curr)) {
  484. struct task_struct *curtask = task_of(curr);
  485. trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
  486. cpuacct_charge(curtask, delta_exec);
  487. account_group_exec_runtime(curtask, delta_exec);
  488. }
  489. }
  490. static inline void
  491. update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
  492. {
  493. schedstat_set(se->statistics.wait_start, rq_of(cfs_rq)->clock);
  494. }
  495. /*
  496. * Task is being enqueued - update stats:
  497. */
  498. static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  499. {
  500. /*
  501. * Are we enqueueing a waiting task? (for current tasks
  502. * a dequeue/enqueue event is a NOP)
  503. */
  504. if (se != cfs_rq->curr)
  505. update_stats_wait_start(cfs_rq, se);
  506. }
  507. static void
  508. update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
  509. {
  510. schedstat_set(se->statistics.wait_max, max(se->statistics.wait_max,
  511. rq_of(cfs_rq)->clock - se->statistics.wait_start));
  512. schedstat_set(se->statistics.wait_count, se->statistics.wait_count + 1);
  513. schedstat_set(se->statistics.wait_sum, se->statistics.wait_sum +
  514. rq_of(cfs_rq)->clock - se->statistics.wait_start);
  515. #ifdef CONFIG_SCHEDSTATS
  516. if (entity_is_task(se)) {
  517. trace_sched_stat_wait(task_of(se),
  518. rq_of(cfs_rq)->clock - se->statistics.wait_start);
  519. }
  520. #endif
  521. schedstat_set(se->statistics.wait_start, 0);
  522. }
  523. static inline void
  524. update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  525. {
  526. /*
  527. * Mark the end of the wait period if dequeueing a
  528. * waiting task:
  529. */
  530. if (se != cfs_rq->curr)
  531. update_stats_wait_end(cfs_rq, se);
  532. }
  533. /*
  534. * We are picking a new current task - update its stats:
  535. */
  536. static inline void
  537. update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
  538. {
  539. /*
  540. * We are starting a new run period:
  541. */
  542. se->exec_start = rq_of(cfs_rq)->clock_task;
  543. }
  544. /**************************************************
  545. * Scheduling class queueing methods:
  546. */
  547. #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
  548. static void
  549. add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
  550. {
  551. cfs_rq->task_weight += weight;
  552. }
  553. #else
  554. static inline void
  555. add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
  556. {
  557. }
  558. #endif
  559. static void
  560. account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  561. {
  562. update_load_add(&cfs_rq->load, se->load.weight);
  563. if (!parent_entity(se))
  564. inc_cpu_load(rq_of(cfs_rq), se->load.weight);
  565. if (entity_is_task(se)) {
  566. add_cfs_task_weight(cfs_rq, se->load.weight);
  567. list_add(&se->group_node, &cfs_rq->tasks);
  568. }
  569. cfs_rq->nr_running++;
  570. }
  571. static void
  572. account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  573. {
  574. update_load_sub(&cfs_rq->load, se->load.weight);
  575. if (!parent_entity(se))
  576. dec_cpu_load(rq_of(cfs_rq), se->load.weight);
  577. if (entity_is_task(se)) {
  578. add_cfs_task_weight(cfs_rq, -se->load.weight);
  579. list_del_init(&se->group_node);
  580. }
  581. cfs_rq->nr_running--;
  582. }
  583. #ifdef CONFIG_FAIR_GROUP_SCHED
  584. # ifdef CONFIG_SMP
  585. static void update_cfs_rq_load_contribution(struct cfs_rq *cfs_rq,
  586. int global_update)
  587. {
  588. struct task_group *tg = cfs_rq->tg;
  589. long load_avg;
  590. load_avg = div64_u64(cfs_rq->load_avg, cfs_rq->load_period+1);
  591. load_avg -= cfs_rq->load_contribution;
  592. if (global_update || abs(load_avg) > cfs_rq->load_contribution / 8) {
  593. atomic_add(load_avg, &tg->load_weight);
  594. cfs_rq->load_contribution += load_avg;
  595. }
  596. }
  597. static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
  598. {
  599. u64 period = sysctl_sched_shares_window;
  600. u64 now, delta;
  601. unsigned long load = cfs_rq->load.weight;
  602. if (!cfs_rq)
  603. return;
  604. now = rq_of(cfs_rq)->clock;
  605. delta = now - cfs_rq->load_stamp;
  606. /* truncate load history at 4 idle periods */
  607. if (cfs_rq->load_stamp > cfs_rq->load_last &&
  608. now - cfs_rq->load_last > 4 * period) {
  609. cfs_rq->load_period = 0;
  610. cfs_rq->load_avg = 0;
  611. }
  612. cfs_rq->load_stamp = now;
  613. cfs_rq->load_unacc_exec_time = 0;
  614. cfs_rq->load_period += delta;
  615. if (load) {
  616. cfs_rq->load_last = now;
  617. cfs_rq->load_avg += delta * load;
  618. }
  619. /* consider updating load contribution on each fold or truncate */
  620. if (global_update || cfs_rq->load_period > period
  621. || !cfs_rq->load_period)
  622. update_cfs_rq_load_contribution(cfs_rq, global_update);
  623. while (cfs_rq->load_period > period) {
  624. /*
  625. * Inline assembly required to prevent the compiler
  626. * optimising this loop into a divmod call.
  627. * See __iter_div_u64_rem() for another example of this.
  628. */
  629. asm("" : "+rm" (cfs_rq->load_period));
  630. cfs_rq->load_period /= 2;
  631. cfs_rq->load_avg /= 2;
  632. }
  633. if (!cfs_rq->curr && !cfs_rq->nr_running && !cfs_rq->load_avg)
  634. list_del_leaf_cfs_rq(cfs_rq);
  635. }
  636. static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg,
  637. long weight_delta)
  638. {
  639. long load_weight, load, shares;
  640. load = cfs_rq->load.weight + weight_delta;
  641. load_weight = atomic_read(&tg->load_weight);
  642. load_weight -= cfs_rq->load_contribution;
  643. load_weight += load;
  644. shares = (tg->shares * load);
  645. if (load_weight)
  646. shares /= load_weight;
  647. if (shares < MIN_SHARES)
  648. shares = MIN_SHARES;
  649. if (shares > tg->shares)
  650. shares = tg->shares;
  651. return shares;
  652. }
  653. static void update_entity_shares_tick(struct cfs_rq *cfs_rq)
  654. {
  655. if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
  656. update_cfs_load(cfs_rq, 0);
  657. update_cfs_shares(cfs_rq, 0);
  658. }
  659. }
  660. # else /* CONFIG_SMP */
  661. static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
  662. {
  663. }
  664. static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg,
  665. long weight_delta)
  666. {
  667. return tg->shares;
  668. }
  669. static inline void update_entity_shares_tick(struct cfs_rq *cfs_rq)
  670. {
  671. }
  672. # endif /* CONFIG_SMP */
  673. static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
  674. unsigned long weight)
  675. {
  676. if (se->on_rq) {
  677. /* commit outstanding execution time */
  678. if (cfs_rq->curr == se)
  679. update_curr(cfs_rq);
  680. account_entity_dequeue(cfs_rq, se);
  681. }
  682. update_load_set(&se->load, weight);
  683. if (se->on_rq)
  684. account_entity_enqueue(cfs_rq, se);
  685. }
  686. static void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta)
  687. {
  688. struct task_group *tg;
  689. struct sched_entity *se;
  690. long shares;
  691. if (!cfs_rq)
  692. return;
  693. tg = cfs_rq->tg;
  694. se = tg->se[cpu_of(rq_of(cfs_rq))];
  695. if (!se)
  696. return;
  697. #ifndef CONFIG_SMP
  698. if (likely(se->load.weight == tg->shares))
  699. return;
  700. #endif
  701. shares = calc_cfs_shares(cfs_rq, tg, weight_delta);
  702. reweight_entity(cfs_rq_of(se), se, shares);
  703. }
  704. #else /* CONFIG_FAIR_GROUP_SCHED */
  705. static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
  706. {
  707. }
  708. static inline void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta)
  709. {
  710. }
  711. static inline void update_entity_shares_tick(struct cfs_rq *cfs_rq)
  712. {
  713. }
  714. #endif /* CONFIG_FAIR_GROUP_SCHED */
  715. static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
  716. {
  717. #ifdef CONFIG_SCHEDSTATS
  718. struct task_struct *tsk = NULL;
  719. if (entity_is_task(se))
  720. tsk = task_of(se);
  721. if (se->statistics.sleep_start) {
  722. u64 delta = rq_of(cfs_rq)->clock - se->statistics.sleep_start;
  723. if ((s64)delta < 0)
  724. delta = 0;
  725. if (unlikely(delta > se->statistics.sleep_max))
  726. se->statistics.sleep_max = delta;
  727. se->statistics.sleep_start = 0;
  728. se->statistics.sum_sleep_runtime += delta;
  729. if (tsk) {
  730. account_scheduler_latency(tsk, delta >> 10, 1);
  731. trace_sched_stat_sleep(tsk, delta);
  732. }
  733. }
  734. if (se->statistics.block_start) {
  735. u64 delta = rq_of(cfs_rq)->clock - se->statistics.block_start;
  736. if ((s64)delta < 0)
  737. delta = 0;
  738. if (unlikely(delta > se->statistics.block_max))
  739. se->statistics.block_max = delta;
  740. se->statistics.block_start = 0;
  741. se->statistics.sum_sleep_runtime += delta;
  742. if (tsk) {
  743. if (tsk->in_iowait) {
  744. se->statistics.iowait_sum += delta;
  745. se->statistics.iowait_count++;
  746. trace_sched_stat_iowait(tsk, delta);
  747. }
  748. /*
  749. * Blocking time is in units of nanosecs, so shift by
  750. * 20 to get a milliseconds-range estimation of the
  751. * amount of time that the task spent sleeping:
  752. */
  753. if (unlikely(prof_on == SLEEP_PROFILING)) {
  754. profile_hits(SLEEP_PROFILING,
  755. (void *)get_wchan(tsk),
  756. delta >> 20);
  757. }
  758. account_scheduler_latency(tsk, delta >> 10, 0);
  759. }
  760. }
  761. #endif
  762. }
  763. static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
  764. {
  765. #ifdef CONFIG_SCHED_DEBUG
  766. s64 d = se->vruntime - cfs_rq->min_vruntime;
  767. if (d < 0)
  768. d = -d;
  769. if (d > 3*sysctl_sched_latency)
  770. schedstat_inc(cfs_rq, nr_spread_over);
  771. #endif
  772. }
  773. static void
  774. place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
  775. {
  776. u64 vruntime = cfs_rq->min_vruntime;
  777. /*
  778. * The 'current' period is already promised to the current tasks,
  779. * however the extra weight of the new task will slow them down a
  780. * little, place the new task so that it fits in the slot that
  781. * stays open at the end.
  782. */
  783. if (initial && sched_feat(START_DEBIT))
  784. vruntime += sched_vslice(cfs_rq, se);
  785. /* sleeps up to a single latency don't count. */
  786. if (!initial) {
  787. unsigned long thresh = sysctl_sched_latency;
  788. /*
  789. * Halve their sleep time's effect, to allow
  790. * for a gentler effect of sleepers:
  791. */
  792. if (sched_feat(GENTLE_FAIR_SLEEPERS))
  793. thresh >>= 1;
  794. vruntime -= thresh;
  795. }
  796. /* ensure we never gain time by being placed backwards. */
  797. vruntime = max_vruntime(se->vruntime, vruntime);
  798. se->vruntime = vruntime;
  799. }
  800. static void
  801. enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
  802. {
  803. /*
  804. * Update the normalized vruntime before updating min_vruntime
  805. * through callig update_curr().
  806. */
  807. if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
  808. se->vruntime += cfs_rq->min_vruntime;
  809. /*
  810. * Update run-time statistics of the 'current'.
  811. */
  812. update_curr(cfs_rq);
  813. update_cfs_load(cfs_rq, 0);
  814. update_cfs_shares(cfs_rq, se->load.weight);
  815. account_entity_enqueue(cfs_rq, se);
  816. if (flags & ENQUEUE_WAKEUP) {
  817. place_entity(cfs_rq, se, 0);
  818. enqueue_sleeper(cfs_rq, se);
  819. }
  820. update_stats_enqueue(cfs_rq, se);
  821. check_spread(cfs_rq, se);
  822. if (se != cfs_rq->curr)
  823. __enqueue_entity(cfs_rq, se);
  824. se->on_rq = 1;
  825. if (cfs_rq->nr_running == 1)
  826. list_add_leaf_cfs_rq(cfs_rq);
  827. }
  828. static void __clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
  829. {
  830. if (!se || cfs_rq->last == se)
  831. cfs_rq->last = NULL;
  832. if (!se || cfs_rq->next == se)
  833. cfs_rq->next = NULL;
  834. }
  835. static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
  836. {
  837. for_each_sched_entity(se)
  838. __clear_buddies(cfs_rq_of(se), se);
  839. }
  840. static void
  841. dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
  842. {
  843. /*
  844. * Update run-time statistics of the 'current'.
  845. */
  846. update_curr(cfs_rq);
  847. update_stats_dequeue(cfs_rq, se);
  848. if (flags & DEQUEUE_SLEEP) {
  849. #ifdef CONFIG_SCHEDSTATS
  850. if (entity_is_task(se)) {
  851. struct task_struct *tsk = task_of(se);
  852. if (tsk->state & TASK_INTERRUPTIBLE)
  853. se->statistics.sleep_start = rq_of(cfs_rq)->clock;
  854. if (tsk->state & TASK_UNINTERRUPTIBLE)
  855. se->statistics.block_start = rq_of(cfs_rq)->clock;
  856. }
  857. #endif
  858. }
  859. clear_buddies(cfs_rq, se);
  860. if (se != cfs_rq->curr)
  861. __dequeue_entity(cfs_rq, se);
  862. se->on_rq = 0;
  863. update_cfs_load(cfs_rq, 0);
  864. account_entity_dequeue(cfs_rq, se);
  865. update_min_vruntime(cfs_rq);
  866. update_cfs_shares(cfs_rq, 0);
  867. /*
  868. * Normalize the entity after updating the min_vruntime because the
  869. * update can refer to the ->curr item and we need to reflect this
  870. * movement in our normalized position.
  871. */
  872. if (!(flags & DEQUEUE_SLEEP))
  873. se->vruntime -= cfs_rq->min_vruntime;
  874. }
  875. /*
  876. * Preempt the current task with a newly woken task if needed:
  877. */
  878. static void
  879. check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
  880. {
  881. unsigned long ideal_runtime, delta_exec;
  882. ideal_runtime = sched_slice(cfs_rq, curr);
  883. delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
  884. if (delta_exec > ideal_runtime) {
  885. resched_task(rq_of(cfs_rq)->curr);
  886. /*
  887. * The current task ran long enough, ensure it doesn't get
  888. * re-elected due to buddy favours.
  889. */
  890. clear_buddies(cfs_rq, curr);
  891. return;
  892. }
  893. /*
  894. * Ensure that a task that missed wakeup preemption by a
  895. * narrow margin doesn't have to wait for a full slice.
  896. * This also mitigates buddy induced latencies under load.
  897. */
  898. if (!sched_feat(WAKEUP_PREEMPT))
  899. return;
  900. if (delta_exec < sysctl_sched_min_granularity)
  901. return;
  902. if (cfs_rq->nr_running > 1) {
  903. struct sched_entity *se = __pick_next_entity(cfs_rq);
  904. s64 delta = curr->vruntime - se->vruntime;
  905. if (delta < 0)
  906. return;
  907. if (delta > ideal_runtime)
  908. resched_task(rq_of(cfs_rq)->curr);
  909. }
  910. }
  911. static void
  912. set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  913. {
  914. /* 'current' is not kept within the tree. */
  915. if (se->on_rq) {
  916. /*
  917. * Any task has to be enqueued before it get to execute on
  918. * a CPU. So account for the time it spent waiting on the
  919. * runqueue.
  920. */
  921. update_stats_wait_end(cfs_rq, se);
  922. __dequeue_entity(cfs_rq, se);
  923. }
  924. update_stats_curr_start(cfs_rq, se);
  925. cfs_rq->curr = se;
  926. #ifdef CONFIG_SCHEDSTATS
  927. /*
  928. * Track our maximum slice length, if the CPU's load is at
  929. * least twice that of our own weight (i.e. dont track it
  930. * when there are only lesser-weight tasks around):
  931. */
  932. if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
  933. se->statistics.slice_max = max(se->statistics.slice_max,
  934. se->sum_exec_runtime - se->prev_sum_exec_runtime);
  935. }
  936. #endif
  937. se->prev_sum_exec_runtime = se->sum_exec_runtime;
  938. }
  939. static int
  940. wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
  941. static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
  942. {
  943. struct sched_entity *se = __pick_next_entity(cfs_rq);
  944. struct sched_entity *left = se;
  945. if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
  946. se = cfs_rq->next;
  947. /*
  948. * Prefer last buddy, try to return the CPU to a preempted task.
  949. */
  950. if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
  951. se = cfs_rq->last;
  952. clear_buddies(cfs_rq, se);
  953. return se;
  954. }
  955. static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
  956. {
  957. /*
  958. * If still on the runqueue then deactivate_task()
  959. * was not called and update_curr() has to be done:
  960. */
  961. if (prev->on_rq)
  962. update_curr(cfs_rq);
  963. check_spread(cfs_rq, prev);
  964. if (prev->on_rq) {
  965. update_stats_wait_start(cfs_rq, prev);
  966. /* Put 'current' back into the tree. */
  967. __enqueue_entity(cfs_rq, prev);
  968. }
  969. cfs_rq->curr = NULL;
  970. }
  971. static void
  972. entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
  973. {
  974. /*
  975. * Update run-time statistics of the 'current'.
  976. */
  977. update_curr(cfs_rq);
  978. /*
  979. * Update share accounting for long-running entities.
  980. */
  981. update_entity_shares_tick(cfs_rq);
  982. #ifdef CONFIG_SCHED_HRTICK
  983. /*
  984. * queued ticks are scheduled to match the slice, so don't bother
  985. * validating it and just reschedule.
  986. */
  987. if (queued) {
  988. resched_task(rq_of(cfs_rq)->curr);
  989. return;
  990. }
  991. /*
  992. * don't let the period tick interfere with the hrtick preemption
  993. */
  994. if (!sched_feat(DOUBLE_TICK) &&
  995. hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
  996. return;
  997. #endif
  998. if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
  999. check_preempt_tick(cfs_rq, curr);
  1000. }
  1001. /**************************************************
  1002. * CFS operations on tasks:
  1003. */
  1004. #ifdef CONFIG_SCHED_HRTICK
  1005. static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
  1006. {
  1007. struct sched_entity *se = &p->se;
  1008. struct cfs_rq *cfs_rq = cfs_rq_of(se);
  1009. WARN_ON(task_rq(p) != rq);
  1010. if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) {
  1011. u64 slice = sched_slice(cfs_rq, se);
  1012. u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
  1013. s64 delta = slice - ran;
  1014. if (delta < 0) {
  1015. if (rq->curr == p)
  1016. resched_task(p);
  1017. return;
  1018. }
  1019. /*
  1020. * Don't schedule slices shorter than 10000ns, that just
  1021. * doesn't make sense. Rely on vruntime for fairness.
  1022. */
  1023. if (rq->curr != p)
  1024. delta = max_t(s64, 10000LL, delta);
  1025. hrtick_start(rq, delta);
  1026. }
  1027. }
  1028. /*
  1029. * called from enqueue/dequeue and updates the hrtick when the
  1030. * current task is from our class and nr_running is low enough
  1031. * to matter.
  1032. */
  1033. static void hrtick_update(struct rq *rq)
  1034. {
  1035. struct task_struct *curr = rq->curr;
  1036. if (curr->sched_class != &fair_sched_class)
  1037. return;
  1038. if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
  1039. hrtick_start_fair(rq, curr);
  1040. }
  1041. #else /* !CONFIG_SCHED_HRTICK */
  1042. static inline void
  1043. hrtick_start_fair(struct rq *rq, struct task_struct *p)
  1044. {
  1045. }
  1046. static inline void hrtick_update(struct rq *rq)
  1047. {
  1048. }
  1049. #endif
  1050. /*
  1051. * The enqueue_task method is called before nr_running is
  1052. * increased. Here we update the fair scheduling stats and
  1053. * then put the task into the rbtree:
  1054. */
  1055. static void
  1056. enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
  1057. {
  1058. struct cfs_rq *cfs_rq;
  1059. struct sched_entity *se = &p->se;
  1060. for_each_sched_entity(se) {
  1061. if (se->on_rq)
  1062. break;
  1063. cfs_rq = cfs_rq_of(se);
  1064. enqueue_entity(cfs_rq, se, flags);
  1065. flags = ENQUEUE_WAKEUP;
  1066. }
  1067. for_each_sched_entity(se) {
  1068. struct cfs_rq *cfs_rq = cfs_rq_of(se);
  1069. update_cfs_load(cfs_rq, 0);
  1070. update_cfs_shares(cfs_rq, 0);
  1071. }
  1072. hrtick_update(rq);
  1073. }
  1074. /*
  1075. * The dequeue_task method is called before nr_running is
  1076. * decreased. We remove the task from the rbtree and
  1077. * update the fair scheduling stats:
  1078. */
  1079. static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
  1080. {
  1081. struct cfs_rq *cfs_rq;
  1082. struct sched_entity *se = &p->se;
  1083. for_each_sched_entity(se) {
  1084. cfs_rq = cfs_rq_of(se);
  1085. dequeue_entity(cfs_rq, se, flags);
  1086. /* Don't dequeue parent if it has other entities besides us */
  1087. if (cfs_rq->load.weight)
  1088. break;
  1089. flags |= DEQUEUE_SLEEP;
  1090. }
  1091. for_each_sched_entity(se) {
  1092. struct cfs_rq *cfs_rq = cfs_rq_of(se);
  1093. update_cfs_load(cfs_rq, 0);
  1094. update_cfs_shares(cfs_rq, 0);
  1095. }
  1096. hrtick_update(rq);
  1097. }
  1098. /*
  1099. * sched_yield() support is very simple - we dequeue and enqueue.
  1100. *
  1101. * If compat_yield is turned on then we requeue to the end of the tree.
  1102. */
  1103. static void yield_task_fair(struct rq *rq)
  1104. {
  1105. struct task_struct *curr = rq->curr;
  1106. struct cfs_rq *cfs_rq = task_cfs_rq(curr);
  1107. struct sched_entity *rightmost, *se = &curr->se;
  1108. /*
  1109. * Are we the only task in the tree?
  1110. */
  1111. if (unlikely(cfs_rq->nr_running == 1))
  1112. return;
  1113. clear_buddies(cfs_rq, se);
  1114. if (likely(!sysctl_sched_compat_yield) && curr->policy != SCHED_BATCH) {
  1115. update_rq_clock(rq);
  1116. /*
  1117. * Update run-time statistics of the 'current'.
  1118. */
  1119. update_curr(cfs_rq);
  1120. return;
  1121. }
  1122. /*
  1123. * Find the rightmost entry in the rbtree:
  1124. */
  1125. rightmost = __pick_last_entity(cfs_rq);
  1126. /*
  1127. * Already in the rightmost position?
  1128. */
  1129. if (unlikely(!rightmost || entity_before(rightmost, se)))
  1130. return;
  1131. /*
  1132. * Minimally necessary key value to be last in the tree:
  1133. * Upon rescheduling, sched_class::put_prev_task() will place
  1134. * 'current' within the tree based on its new key value.
  1135. */
  1136. se->vruntime = rightmost->vruntime + 1;
  1137. }
  1138. #ifdef CONFIG_SMP
  1139. static void task_waking_fair(struct rq *rq, struct task_struct *p)
  1140. {
  1141. struct sched_entity *se = &p->se;
  1142. struct cfs_rq *cfs_rq = cfs_rq_of(se);
  1143. se->vruntime -= cfs_rq->min_vruntime;
  1144. }
  1145. #ifdef CONFIG_FAIR_GROUP_SCHED
  1146. /*
  1147. * effective_load() calculates the load change as seen from the root_task_group
  1148. *
  1149. * Adding load to a group doesn't make a group heavier, but can cause movement
  1150. * of group shares between cpus. Assuming the shares were perfectly aligned one
  1151. * can calculate the shift in shares.
  1152. */
  1153. static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
  1154. {
  1155. struct sched_entity *se = tg->se[cpu];
  1156. if (!tg->parent)
  1157. return wl;
  1158. for_each_sched_entity(se) {
  1159. long lw, w;
  1160. tg = se->my_q->tg;
  1161. w = se->my_q->load.weight;
  1162. /* use this cpu's instantaneous contribution */
  1163. lw = atomic_read(&tg->load_weight);
  1164. lw -= se->my_q->load_contribution;
  1165. lw += w + wg;
  1166. wl += w;
  1167. if (lw > 0 && wl < lw)
  1168. wl = (wl * tg->shares) / lw;
  1169. else
  1170. wl = tg->shares;
  1171. /* zero point is MIN_SHARES */
  1172. if (wl < MIN_SHARES)
  1173. wl = MIN_SHARES;
  1174. wl -= se->load.weight;
  1175. wg = 0;
  1176. }
  1177. return wl;
  1178. }
  1179. #else
  1180. static inline unsigned long effective_load(struct task_group *tg, int cpu,
  1181. unsigned long wl, unsigned long wg)
  1182. {
  1183. return wl;
  1184. }
  1185. #endif
  1186. static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
  1187. {
  1188. unsigned long this_load, load;
  1189. int idx, this_cpu, prev_cpu;
  1190. unsigned long tl_per_task;
  1191. struct task_group *tg;
  1192. unsigned long weight;
  1193. int balanced;
  1194. idx = sd->wake_idx;
  1195. this_cpu = smp_processor_id();
  1196. prev_cpu = task_cpu(p);
  1197. load = source_load(prev_cpu, idx);
  1198. this_load = target_load(this_cpu, idx);
  1199. /*
  1200. * If sync wakeup then subtract the (maximum possible)
  1201. * effect of the currently running task from the load
  1202. * of the current CPU:
  1203. */
  1204. rcu_read_lock();
  1205. if (sync) {
  1206. tg = task_group(current);
  1207. weight = current->se.load.weight;
  1208. this_load += effective_load(tg, this_cpu, -weight, -weight);
  1209. load += effective_load(tg, prev_cpu, 0, -weight);
  1210. }
  1211. tg = task_group(p);
  1212. weight = p->se.load.weight;
  1213. /*
  1214. * In low-load situations, where prev_cpu is idle and this_cpu is idle
  1215. * due to the sync cause above having dropped this_load to 0, we'll
  1216. * always have an imbalance, but there's really nothing you can do
  1217. * about that, so that's good too.
  1218. *
  1219. * Otherwise check if either cpus are near enough in load to allow this
  1220. * task to be woken on this_cpu.
  1221. */
  1222. if (this_load) {
  1223. unsigned long this_eff_load, prev_eff_load;
  1224. this_eff_load = 100;
  1225. this_eff_load *= power_of(prev_cpu);
  1226. this_eff_load *= this_load +
  1227. effective_load(tg, this_cpu, weight, weight);
  1228. prev_eff_load = 100 + (sd->imbalance_pct - 100) / 2;
  1229. prev_eff_load *= power_of(this_cpu);
  1230. prev_eff_load *= load + effective_load(tg, prev_cpu, 0, weight);
  1231. balanced = this_eff_load <= prev_eff_load;
  1232. } else
  1233. balanced = true;
  1234. rcu_read_unlock();
  1235. /*
  1236. * If the currently running task will sleep within
  1237. * a reasonable amount of time then attract this newly
  1238. * woken task:
  1239. */
  1240. if (sync && balanced)
  1241. return 1;
  1242. schedstat_inc(p, se.statistics.nr_wakeups_affine_attempts);
  1243. tl_per_task = cpu_avg_load_per_task(this_cpu);
  1244. if (balanced ||
  1245. (this_load <= load &&
  1246. this_load + target_load(prev_cpu, idx) <= tl_per_task)) {
  1247. /*
  1248. * This domain has SD_WAKE_AFFINE and
  1249. * p is cache cold in this domain, and
  1250. * there is no bad imbalance.
  1251. */
  1252. schedstat_inc(sd, ttwu_move_affine);
  1253. schedstat_inc(p, se.statistics.nr_wakeups_affine);
  1254. return 1;
  1255. }
  1256. return 0;
  1257. }
  1258. /*
  1259. * find_idlest_group finds and returns the least busy CPU group within the
  1260. * domain.
  1261. */
  1262. static struct sched_group *
  1263. find_idlest_group(struct sched_domain *sd, struct task_struct *p,
  1264. int this_cpu, int load_idx)
  1265. {
  1266. struct sched_group *idlest = NULL, *group = sd->groups;
  1267. unsigned long min_load = ULONG_MAX, this_load = 0;
  1268. int imbalance = 100 + (sd->imbalance_pct-100)/2;
  1269. do {
  1270. unsigned long load, avg_load;
  1271. int local_group;
  1272. int i;
  1273. /* Skip over this group if it has no CPUs allowed */
  1274. if (!cpumask_intersects(sched_group_cpus(group),
  1275. &p->cpus_allowed))
  1276. continue;
  1277. local_group = cpumask_test_cpu(this_cpu,
  1278. sched_group_cpus(group));
  1279. /* Tally up the load of all CPUs in the group */
  1280. avg_load = 0;
  1281. for_each_cpu(i, sched_group_cpus(group)) {
  1282. /* Bias balancing toward cpus of our domain */
  1283. if (local_group)
  1284. load = source_load(i, load_idx);
  1285. else
  1286. load = target_load(i, load_idx);
  1287. avg_load += load;
  1288. }
  1289. /* Adjust by relative CPU power of the group */
  1290. avg_load = (avg_load * SCHED_LOAD_SCALE) / group->cpu_power;
  1291. if (local_group) {
  1292. this_load = avg_load;
  1293. } else if (avg_load < min_load) {
  1294. min_load = avg_load;
  1295. idlest = group;
  1296. }
  1297. } while (group = group->next, group != sd->groups);
  1298. if (!idlest || 100*this_load < imbalance*min_load)
  1299. return NULL;
  1300. return idlest;
  1301. }
  1302. /*
  1303. * find_idlest_cpu - find the idlest cpu among the cpus in group.
  1304. */
  1305. static int
  1306. find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
  1307. {
  1308. unsigned long load, min_load = ULONG_MAX;
  1309. int idlest = -1;
  1310. int i;
  1311. /* Traverse only the allowed CPUs */
  1312. for_each_cpu_and(i, sched_group_cpus(group), &p->cpus_allowed) {
  1313. load = weighted_cpuload(i);
  1314. if (load < min_load || (load == min_load && i == this_cpu)) {
  1315. min_load = load;
  1316. idlest = i;
  1317. }
  1318. }
  1319. return idlest;
  1320. }
  1321. /*
  1322. * Try and locate an idle CPU in the sched_domain.
  1323. */
  1324. static int select_idle_sibling(struct task_struct *p, int target)
  1325. {
  1326. int cpu = smp_processor_id();
  1327. int prev_cpu = task_cpu(p);
  1328. struct sched_domain *sd;
  1329. int i;
  1330. /*
  1331. * If the task is going to be woken-up on this cpu and if it is
  1332. * already idle, then it is the right target.
  1333. */
  1334. if (target == cpu && idle_cpu(cpu))
  1335. return cpu;
  1336. /*
  1337. * If the task is going to be woken-up on the cpu where it previously
  1338. * ran and if it is currently idle, then it the right target.
  1339. */
  1340. if (target == prev_cpu && idle_cpu(prev_cpu))
  1341. return prev_cpu;
  1342. /*
  1343. * Otherwise, iterate the domains and find an elegible idle cpu.
  1344. */
  1345. for_each_domain(target, sd) {
  1346. if (!(sd->flags & SD_SHARE_PKG_RESOURCES))
  1347. break;
  1348. for_each_cpu_and(i, sched_domain_span(sd), &p->cpus_allowed) {
  1349. if (idle_cpu(i)) {
  1350. target = i;
  1351. break;
  1352. }
  1353. }
  1354. /*
  1355. * Lets stop looking for an idle sibling when we reached
  1356. * the domain that spans the current cpu and prev_cpu.
  1357. */
  1358. if (cpumask_test_cpu(cpu, sched_domain_span(sd)) &&
  1359. cpumask_test_cpu(prev_cpu, sched_domain_span(sd)))
  1360. break;
  1361. }
  1362. return target;
  1363. }
  1364. /*
  1365. * sched_balance_self: balance the current task (running on cpu) in domains
  1366. * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
  1367. * SD_BALANCE_EXEC.
  1368. *
  1369. * Balance, ie. select the least loaded group.
  1370. *
  1371. * Returns the target CPU number, or the same CPU if no balancing is needed.
  1372. *
  1373. * preempt must be disabled.
  1374. */
  1375. static int
  1376. select_task_rq_fair(struct rq *rq, struct task_struct *p, int sd_flag, int wake_flags)
  1377. {
  1378. struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
  1379. int cpu = smp_processor_id();
  1380. int prev_cpu = task_cpu(p);
  1381. int new_cpu = cpu;
  1382. int want_affine = 0;
  1383. int want_sd = 1;
  1384. int sync = wake_flags & WF_SYNC;
  1385. if (sd_flag & SD_BALANCE_WAKE) {
  1386. if (cpumask_test_cpu(cpu, &p->cpus_allowed))
  1387. want_affine = 1;
  1388. new_cpu = prev_cpu;
  1389. }
  1390. for_each_domain(cpu, tmp) {
  1391. if (!(tmp->flags & SD_LOAD_BALANCE))
  1392. continue;
  1393. /*
  1394. * If power savings logic is enabled for a domain, see if we
  1395. * are not overloaded, if so, don't balance wider.
  1396. */
  1397. if (tmp->flags & (SD_POWERSAVINGS_BALANCE|SD_PREFER_LOCAL)) {
  1398. unsigned long power = 0;
  1399. unsigned long nr_running = 0;
  1400. unsigned long capacity;
  1401. int i;
  1402. for_each_cpu(i, sched_domain_span(tmp)) {
  1403. power += power_of(i);
  1404. nr_running += cpu_rq(i)->cfs.nr_running;
  1405. }
  1406. capacity = DIV_ROUND_CLOSEST(power, SCHED_LOAD_SCALE);
  1407. if (tmp->flags & SD_POWERSAVINGS_BALANCE)
  1408. nr_running /= 2;
  1409. if (nr_running < capacity)
  1410. want_sd = 0;
  1411. }
  1412. /*
  1413. * If both cpu and prev_cpu are part of this domain,
  1414. * cpu is a valid SD_WAKE_AFFINE target.
  1415. */
  1416. if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
  1417. cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
  1418. affine_sd = tmp;
  1419. want_affine = 0;
  1420. }
  1421. if (!want_sd && !want_affine)
  1422. break;
  1423. if (!(tmp->flags & sd_flag))
  1424. continue;
  1425. if (want_sd)
  1426. sd = tmp;
  1427. }
  1428. if (affine_sd) {
  1429. if (cpu == prev_cpu || wake_affine(affine_sd, p, sync))
  1430. return select_idle_sibling(p, cpu);
  1431. else
  1432. return select_idle_sibling(p, prev_cpu);
  1433. }
  1434. while (sd) {
  1435. int load_idx = sd->forkexec_idx;
  1436. struct sched_group *group;
  1437. int weight;
  1438. if (!(sd->flags & sd_flag)) {
  1439. sd = sd->child;
  1440. continue;
  1441. }
  1442. if (sd_flag & SD_BALANCE_WAKE)
  1443. load_idx = sd->wake_idx;
  1444. group = find_idlest_group(sd, p, cpu, load_idx);
  1445. if (!group) {
  1446. sd = sd->child;
  1447. continue;
  1448. }
  1449. new_cpu = find_idlest_cpu(group, p, cpu);
  1450. if (new_cpu == -1 || new_cpu == cpu) {
  1451. /* Now try balancing at a lower domain level of cpu */
  1452. sd = sd->child;
  1453. continue;
  1454. }
  1455. /* Now try balancing at a lower domain level of new_cpu */
  1456. cpu = new_cpu;
  1457. weight = sd->span_weight;
  1458. sd = NULL;
  1459. for_each_domain(cpu, tmp) {
  1460. if (weight <= tmp->span_weight)
  1461. break;
  1462. if (tmp->flags & sd_flag)
  1463. sd = tmp;
  1464. }
  1465. /* while loop will break here if sd == NULL */
  1466. }
  1467. return new_cpu;
  1468. }
  1469. #endif /* CONFIG_SMP */
  1470. static unsigned long
  1471. wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
  1472. {
  1473. unsigned long gran = sysctl_sched_wakeup_granularity;
  1474. /*
  1475. * Since its curr running now, convert the gran from real-time
  1476. * to virtual-time in his units.
  1477. *
  1478. * By using 'se' instead of 'curr' we penalize light tasks, so
  1479. * they get preempted easier. That is, if 'se' < 'curr' then
  1480. * the resulting gran will be larger, therefore penalizing the
  1481. * lighter, if otoh 'se' > 'curr' then the resulting gran will
  1482. * be smaller, again penalizing the lighter task.
  1483. *
  1484. * This is especially important for buddies when the leftmost
  1485. * task is higher priority than the buddy.
  1486. */
  1487. if (unlikely(se->load.weight != NICE_0_LOAD))
  1488. gran = calc_delta_fair(gran, se);
  1489. return gran;
  1490. }
  1491. /*
  1492. * Should 'se' preempt 'curr'.
  1493. *
  1494. * |s1
  1495. * |s2
  1496. * |s3
  1497. * g
  1498. * |<--->|c
  1499. *
  1500. * w(c, s1) = -1
  1501. * w(c, s2) = 0
  1502. * w(c, s3) = 1
  1503. *
  1504. */
  1505. static int
  1506. wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
  1507. {
  1508. s64 gran, vdiff = curr->vruntime - se->vruntime;
  1509. if (vdiff <= 0)
  1510. return -1;
  1511. gran = wakeup_gran(curr, se);
  1512. if (vdiff > gran)
  1513. return 1;
  1514. return 0;
  1515. }
  1516. static void set_last_buddy(struct sched_entity *se)
  1517. {
  1518. if (likely(task_of(se)->policy != SCHED_IDLE)) {
  1519. for_each_sched_entity(se)
  1520. cfs_rq_of(se)->last = se;
  1521. }
  1522. }
  1523. static void set_next_buddy(struct sched_entity *se)
  1524. {
  1525. if (likely(task_of(se)->policy != SCHED_IDLE)) {
  1526. for_each_sched_entity(se)
  1527. cfs_rq_of(se)->next = se;
  1528. }
  1529. }
  1530. /*
  1531. * Preempt the current task with a newly woken task if needed:
  1532. */
  1533. static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
  1534. {
  1535. struct task_struct *curr = rq->curr;
  1536. struct sched_entity *se = &curr->se, *pse = &p->se;
  1537. struct cfs_rq *cfs_rq = task_cfs_rq(curr);
  1538. int scale = cfs_rq->nr_running >= sched_nr_latency;
  1539. if (unlikely(se == pse))
  1540. return;
  1541. if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK))
  1542. set_next_buddy(pse);
  1543. /*
  1544. * We can come here with TIF_NEED_RESCHED already set from new task
  1545. * wake up path.
  1546. */
  1547. if (test_tsk_need_resched(curr))
  1548. return;
  1549. /*
  1550. * Batch and idle tasks do not preempt (their preemption is driven by
  1551. * the tick):
  1552. */
  1553. if (unlikely(p->policy != SCHED_NORMAL))
  1554. return;
  1555. /* Idle tasks are by definition preempted by everybody. */
  1556. if (unlikely(curr->policy == SCHED_IDLE))
  1557. goto preempt;
  1558. if (!sched_feat(WAKEUP_PREEMPT))
  1559. return;
  1560. update_curr(cfs_rq);
  1561. find_matching_se(&se, &pse);
  1562. BUG_ON(!pse);
  1563. if (wakeup_preempt_entity(se, pse) == 1)
  1564. goto preempt;
  1565. return;
  1566. preempt:
  1567. resched_task(curr);
  1568. /*
  1569. * Only set the backward buddy when the current task is still
  1570. * on the rq. This can happen when a wakeup gets interleaved
  1571. * with schedule on the ->pre_schedule() or idle_balance()
  1572. * point, either of which can * drop the rq lock.
  1573. *
  1574. * Also, during early boot the idle thread is in the fair class,
  1575. * for obvious reasons its a bad idea to schedule back to it.
  1576. */
  1577. if (unlikely(!se->on_rq || curr == rq->idle))
  1578. return;
  1579. if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
  1580. set_last_buddy(se);
  1581. }
  1582. static struct task_struct *pick_next_task_fair(struct rq *rq)
  1583. {
  1584. struct task_struct *p;
  1585. struct cfs_rq *cfs_rq = &rq->cfs;
  1586. struct sched_entity *se;
  1587. if (!cfs_rq->nr_running)
  1588. return NULL;
  1589. do {
  1590. se = pick_next_entity(cfs_rq);
  1591. set_next_entity(cfs_rq, se);
  1592. cfs_rq = group_cfs_rq(se);
  1593. } while (cfs_rq);
  1594. p = task_of(se);
  1595. hrtick_start_fair(rq, p);
  1596. return p;
  1597. }
  1598. /*
  1599. * Account for a descheduled task:
  1600. */
  1601. static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
  1602. {
  1603. struct sched_entity *se = &prev->se;
  1604. struct cfs_rq *cfs_rq;
  1605. for_each_sched_entity(se) {
  1606. cfs_rq = cfs_rq_of(se);
  1607. put_prev_entity(cfs_rq, se);
  1608. }
  1609. }
  1610. #ifdef CONFIG_SMP
  1611. /**************************************************
  1612. * Fair scheduling class load-balancing methods:
  1613. */
  1614. /*
  1615. * pull_task - move a task from a remote runqueue to the local runqueue.
  1616. * Both runqueues must be locked.
  1617. */
  1618. static void pull_task(struct rq *src_rq, struct task_struct *p,
  1619. struct rq *this_rq, int this_cpu)
  1620. {
  1621. deactivate_task(src_rq, p, 0);
  1622. set_task_cpu(p, this_cpu);
  1623. activate_task(this_rq, p, 0);
  1624. check_preempt_curr(this_rq, p, 0);
  1625. }
  1626. /*
  1627. * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
  1628. */
  1629. static
  1630. int can_migrate_task(struct task_struct *p, struct rq *rq, int this_cpu,
  1631. struct sched_domain *sd, enum cpu_idle_type idle,
  1632. int *all_pinned)
  1633. {
  1634. int tsk_cache_hot = 0;
  1635. /*
  1636. * We do not migrate tasks that are:
  1637. * 1) running (obviously), or
  1638. * 2) cannot be migrated to this CPU due to cpus_allowed, or
  1639. * 3) are cache-hot on their current CPU.
  1640. */
  1641. if (!cpumask_test_cpu(this_cpu, &p->cpus_allowed)) {
  1642. schedstat_inc(p, se.statistics.nr_failed_migrations_affine);
  1643. return 0;
  1644. }
  1645. *all_pinned = 0;
  1646. if (task_running(rq, p)) {
  1647. schedstat_inc(p, se.statistics.nr_failed_migrations_running);
  1648. return 0;
  1649. }
  1650. /*
  1651. * Aggressive migration if:
  1652. * 1) task is cache cold, or
  1653. * 2) too many balance attempts have failed.
  1654. */
  1655. tsk_cache_hot = task_hot(p, rq->clock_task, sd);
  1656. if (!tsk_cache_hot ||
  1657. sd->nr_balance_failed > sd->cache_nice_tries) {
  1658. #ifdef CONFIG_SCHEDSTATS
  1659. if (tsk_cache_hot) {
  1660. schedstat_inc(sd, lb_hot_gained[idle]);
  1661. schedstat_inc(p, se.statistics.nr_forced_migrations);
  1662. }
  1663. #endif
  1664. return 1;
  1665. }
  1666. if (tsk_cache_hot) {
  1667. schedstat_inc(p, se.statistics.nr_failed_migrations_hot);
  1668. return 0;
  1669. }
  1670. return 1;
  1671. }
  1672. /*
  1673. * move_one_task tries to move exactly one task from busiest to this_rq, as
  1674. * part of active balancing operations within "domain".
  1675. * Returns 1 if successful and 0 otherwise.
  1676. *
  1677. * Called with both runqueues locked.
  1678. */
  1679. static int
  1680. move_one_task(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1681. struct sched_domain *sd, enum cpu_idle_type idle)
  1682. {
  1683. struct task_struct *p, *n;
  1684. struct cfs_rq *cfs_rq;
  1685. int pinned = 0;
  1686. for_each_leaf_cfs_rq(busiest, cfs_rq) {
  1687. list_for_each_entry_safe(p, n, &cfs_rq->tasks, se.group_node) {
  1688. if (!can_migrate_task(p, busiest, this_cpu,
  1689. sd, idle, &pinned))
  1690. continue;
  1691. pull_task(busiest, p, this_rq, this_cpu);
  1692. /*
  1693. * Right now, this is only the second place pull_task()
  1694. * is called, so we can safely collect pull_task()
  1695. * stats here rather than inside pull_task().
  1696. */
  1697. schedstat_inc(sd, lb_gained[idle]);
  1698. return 1;
  1699. }
  1700. }
  1701. return 0;
  1702. }
  1703. static unsigned long
  1704. balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1705. unsigned long max_load_move, struct sched_domain *sd,
  1706. enum cpu_idle_type idle, int *all_pinned,
  1707. int *this_best_prio, struct cfs_rq *busiest_cfs_rq)
  1708. {
  1709. int loops = 0, pulled = 0, pinned = 0;
  1710. long rem_load_move = max_load_move;
  1711. struct task_struct *p, *n;
  1712. if (max_load_move == 0)
  1713. goto out;
  1714. pinned = 1;
  1715. list_for_each_entry_safe(p, n, &busiest_cfs_rq->tasks, se.group_node) {
  1716. if (loops++ > sysctl_sched_nr_migrate)
  1717. break;
  1718. if ((p->se.load.weight >> 1) > rem_load_move ||
  1719. !can_migrate_task(p, busiest, this_cpu, sd, idle, &pinned))
  1720. continue;
  1721. pull_task(busiest, p, this_rq, this_cpu);
  1722. pulled++;
  1723. rem_load_move -= p->se.load.weight;
  1724. #ifdef CONFIG_PREEMPT
  1725. /*
  1726. * NEWIDLE balancing is a source of latency, so preemptible
  1727. * kernels will stop after the first task is pulled to minimize
  1728. * the critical section.
  1729. */
  1730. if (idle == CPU_NEWLY_IDLE)
  1731. break;
  1732. #endif
  1733. /*
  1734. * We only want to steal up to the prescribed amount of
  1735. * weighted load.
  1736. */
  1737. if (rem_load_move <= 0)
  1738. break;
  1739. if (p->prio < *this_best_prio)
  1740. *this_best_prio = p->prio;
  1741. }
  1742. out:
  1743. /*
  1744. * Right now, this is one of only two places pull_task() is called,
  1745. * so we can safely collect pull_task() stats here rather than
  1746. * inside pull_task().
  1747. */
  1748. schedstat_add(sd, lb_gained[idle], pulled);
  1749. if (all_pinned)
  1750. *all_pinned = pinned;
  1751. return max_load_move - rem_load_move;
  1752. }
  1753. #ifdef CONFIG_FAIR_GROUP_SCHED
  1754. /*
  1755. * update tg->load_weight by folding this cpu's load_avg
  1756. */
  1757. static int update_shares_cpu(struct task_group *tg, int cpu)
  1758. {
  1759. struct cfs_rq *cfs_rq;
  1760. unsigned long flags;
  1761. struct rq *rq;
  1762. if (!tg->se[cpu])
  1763. return 0;
  1764. rq = cpu_rq(cpu);
  1765. cfs_rq = tg->cfs_rq[cpu];
  1766. raw_spin_lock_irqsave(&rq->lock, flags);
  1767. update_rq_clock(rq);
  1768. update_cfs_load(cfs_rq, 1);
  1769. /*
  1770. * We need to update shares after updating tg->load_weight in
  1771. * order to adjust the weight of groups with long running tasks.
  1772. */
  1773. update_cfs_shares(cfs_rq, 0);
  1774. raw_spin_unlock_irqrestore(&rq->lock, flags);
  1775. return 0;
  1776. }
  1777. static void update_shares(int cpu)
  1778. {
  1779. struct cfs_rq *cfs_rq;
  1780. struct rq *rq = cpu_rq(cpu);
  1781. rcu_read_lock();
  1782. for_each_leaf_cfs_rq(rq, cfs_rq)
  1783. update_shares_cpu(cfs_rq->tg, cpu);
  1784. rcu_read_unlock();
  1785. }
  1786. static unsigned long
  1787. load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1788. unsigned long max_load_move,
  1789. struct sched_domain *sd, enum cpu_idle_type idle,
  1790. int *all_pinned, int *this_best_prio)
  1791. {
  1792. long rem_load_move = max_load_move;
  1793. int busiest_cpu = cpu_of(busiest);
  1794. struct task_group *tg;
  1795. rcu_read_lock();
  1796. update_h_load(busiest_cpu);
  1797. list_for_each_entry_rcu(tg, &task_groups, list) {
  1798. struct cfs_rq *busiest_cfs_rq = tg->cfs_rq[busiest_cpu];
  1799. unsigned long busiest_h_load = busiest_cfs_rq->h_load;
  1800. unsigned long busiest_weight = busiest_cfs_rq->load.weight;
  1801. u64 rem_load, moved_load;
  1802. /*
  1803. * empty group
  1804. */
  1805. if (!busiest_cfs_rq->task_weight)
  1806. continue;
  1807. rem_load = (u64)rem_load_move * busiest_weight;
  1808. rem_load = div_u64(rem_load, busiest_h_load + 1);
  1809. moved_load = balance_tasks(this_rq, this_cpu, busiest,
  1810. rem_load, sd, idle, all_pinned, this_best_prio,
  1811. busiest_cfs_rq);
  1812. if (!moved_load)
  1813. continue;
  1814. moved_load *= busiest_h_load;
  1815. moved_load = div_u64(moved_load, busiest_weight + 1);
  1816. rem_load_move -= moved_load;
  1817. if (rem_load_move < 0)
  1818. break;
  1819. }
  1820. rcu_read_unlock();
  1821. return max_load_move - rem_load_move;
  1822. }
  1823. #else
  1824. static inline void update_shares(int cpu)
  1825. {
  1826. }
  1827. static unsigned long
  1828. load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1829. unsigned long max_load_move,
  1830. struct sched_domain *sd, enum cpu_idle_type idle,
  1831. int *all_pinned, int *this_best_prio)
  1832. {
  1833. return balance_tasks(this_rq, this_cpu, busiest,
  1834. max_load_move, sd, idle, all_pinned,
  1835. this_best_prio, &busiest->cfs);
  1836. }
  1837. #endif
  1838. /*
  1839. * move_tasks tries to move up to max_load_move weighted load from busiest to
  1840. * this_rq, as part of a balancing operation within domain "sd".
  1841. * Returns 1 if successful and 0 otherwise.
  1842. *
  1843. * Called with both runqueues locked.
  1844. */
  1845. static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1846. unsigned long max_load_move,
  1847. struct sched_domain *sd, enum cpu_idle_type idle,
  1848. int *all_pinned)
  1849. {
  1850. unsigned long total_load_moved = 0, load_moved;
  1851. int this_best_prio = this_rq->curr->prio;
  1852. do {
  1853. load_moved = load_balance_fair(this_rq, this_cpu, busiest,
  1854. max_load_move - total_load_moved,
  1855. sd, idle, all_pinned, &this_best_prio);
  1856. total_load_moved += load_moved;
  1857. #ifdef CONFIG_PREEMPT
  1858. /*
  1859. * NEWIDLE balancing is a source of latency, so preemptible
  1860. * kernels will stop after the first task is pulled to minimize
  1861. * the critical section.
  1862. */
  1863. if (idle == CPU_NEWLY_IDLE && this_rq->nr_running)
  1864. break;
  1865. if (raw_spin_is_contended(&this_rq->lock) ||
  1866. raw_spin_is_contended(&busiest->lock))
  1867. break;
  1868. #endif
  1869. } while (load_moved && max_load_move > total_load_moved);
  1870. return total_load_moved > 0;
  1871. }
  1872. /********** Helpers for find_busiest_group ************************/
  1873. /*
  1874. * sd_lb_stats - Structure to store the statistics of a sched_domain
  1875. * during load balancing.
  1876. */
  1877. struct sd_lb_stats {
  1878. struct sched_group *busiest; /* Busiest group in this sd */
  1879. struct sched_group *this; /* Local group in this sd */
  1880. unsigned long total_load; /* Total load of all groups in sd */
  1881. unsigned long total_pwr; /* Total power of all groups in sd */
  1882. unsigned long avg_load; /* Average load across all groups in sd */
  1883. /** Statistics of this group */
  1884. unsigned long this_load;
  1885. unsigned long this_load_per_task;
  1886. unsigned long this_nr_running;
  1887. unsigned long this_has_capacity;
  1888. unsigned int this_idle_cpus;
  1889. /* Statistics of the busiest group */
  1890. unsigned int busiest_idle_cpus;
  1891. unsigned long max_load;
  1892. unsigned long busiest_load_per_task;
  1893. unsigned long busiest_nr_running;
  1894. unsigned long busiest_group_capacity;
  1895. unsigned long busiest_has_capacity;
  1896. unsigned int busiest_group_weight;
  1897. int group_imb; /* Is there imbalance in this sd */
  1898. #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
  1899. int power_savings_balance; /* Is powersave balance needed for this sd */
  1900. struct sched_group *group_min; /* Least loaded group in sd */
  1901. struct sched_group *group_leader; /* Group which relieves group_min */
  1902. unsigned long min_load_per_task; /* load_per_task in group_min */
  1903. unsigned long leader_nr_running; /* Nr running of group_leader */
  1904. unsigned long min_nr_running; /* Nr running of group_min */
  1905. #endif
  1906. };
  1907. /*
  1908. * sg_lb_stats - stats of a sched_group required for load_balancing
  1909. */
  1910. struct sg_lb_stats {
  1911. unsigned long avg_load; /*Avg load across the CPUs of the group */
  1912. unsigned long group_load; /* Total load over the CPUs of the group */
  1913. unsigned long sum_nr_running; /* Nr tasks running in the group */
  1914. unsigned long sum_weighted_load; /* Weighted load of group's tasks */
  1915. unsigned long group_capacity;
  1916. unsigned long idle_cpus;
  1917. unsigned long group_weight;
  1918. int group_imb; /* Is there an imbalance in the group ? */
  1919. int group_has_capacity; /* Is there extra capacity in the group? */
  1920. };
  1921. /**
  1922. * group_first_cpu - Returns the first cpu in the cpumask of a sched_group.
  1923. * @group: The group whose first cpu is to be returned.
  1924. */
  1925. static inline unsigned int group_first_cpu(struct sched_group *group)
  1926. {
  1927. return cpumask_first(sched_group_cpus(group));
  1928. }
  1929. /**
  1930. * get_sd_load_idx - Obtain the load index for a given sched domain.
  1931. * @sd: The sched_domain whose load_idx is to be obtained.
  1932. * @idle: The Idle status of the CPU for whose sd load_icx is obtained.
  1933. */
  1934. static inline int get_sd_load_idx(struct sched_domain *sd,
  1935. enum cpu_idle_type idle)
  1936. {
  1937. int load_idx;
  1938. switch (idle) {
  1939. case CPU_NOT_IDLE:
  1940. load_idx = sd->busy_idx;
  1941. break;
  1942. case CPU_NEWLY_IDLE:
  1943. load_idx = sd->newidle_idx;
  1944. break;
  1945. default:
  1946. load_idx = sd->idle_idx;
  1947. break;
  1948. }
  1949. return load_idx;
  1950. }
  1951. #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
  1952. /**
  1953. * init_sd_power_savings_stats - Initialize power savings statistics for
  1954. * the given sched_domain, during load balancing.
  1955. *
  1956. * @sd: Sched domain whose power-savings statistics are to be initialized.
  1957. * @sds: Variable containing the statistics for sd.
  1958. * @idle: Idle status of the CPU at which we're performing load-balancing.
  1959. */
  1960. static inline void init_sd_power_savings_stats(struct sched_domain *sd,
  1961. struct sd_lb_stats *sds, enum cpu_idle_type idle)
  1962. {
  1963. /*
  1964. * Busy processors will not participate in power savings
  1965. * balance.
  1966. */
  1967. if (idle == CPU_NOT_IDLE || !(sd->flags & SD_POWERSAVINGS_BALANCE))
  1968. sds->power_savings_balance = 0;
  1969. else {
  1970. sds->power_savings_balance = 1;
  1971. sds->min_nr_running = ULONG_MAX;
  1972. sds->leader_nr_running = 0;
  1973. }
  1974. }
  1975. /**
  1976. * update_sd_power_savings_stats - Update the power saving stats for a
  1977. * sched_domain while performing load balancing.
  1978. *
  1979. * @group: sched_group belonging to the sched_domain under consideration.
  1980. * @sds: Variable containing the statistics of the sched_domain
  1981. * @local_group: Does group contain the CPU for which we're performing
  1982. * load balancing ?
  1983. * @sgs: Variable containing the statistics of the group.
  1984. */
  1985. static inline void update_sd_power_savings_stats(struct sched_group *group,
  1986. struct sd_lb_stats *sds, int local_group, struct sg_lb_stats *sgs)
  1987. {
  1988. if (!sds->power_savings_balance)
  1989. return;
  1990. /*
  1991. * If the local group is idle or completely loaded
  1992. * no need to do power savings balance at this domain
  1993. */
  1994. if (local_group && (sds->this_nr_running >= sgs->group_capacity ||
  1995. !sds->this_nr_running))
  1996. sds->power_savings_balance = 0;
  1997. /*
  1998. * If a group is already running at full capacity or idle,
  1999. * don't include that group in power savings calculations
  2000. */
  2001. if (!sds->power_savings_balance ||
  2002. sgs->sum_nr_running >= sgs->group_capacity ||
  2003. !sgs->sum_nr_running)
  2004. return;
  2005. /*
  2006. * Calculate the group which has the least non-idle load.
  2007. * This is the group from where we need to pick up the load
  2008. * for saving power
  2009. */
  2010. if ((sgs->sum_nr_running < sds->min_nr_running) ||
  2011. (sgs->sum_nr_running == sds->min_nr_running &&
  2012. group_first_cpu(group) > group_first_cpu(sds->group_min))) {
  2013. sds->group_min = group;
  2014. sds->min_nr_running = sgs->sum_nr_running;
  2015. sds->min_load_per_task = sgs->sum_weighted_load /
  2016. sgs->sum_nr_running;
  2017. }
  2018. /*
  2019. * Calculate the group which is almost near its
  2020. * capacity but still has some space to pick up some load
  2021. * from other group and save more power
  2022. */
  2023. if (sgs->sum_nr_running + 1 > sgs->group_capacity)
  2024. return;
  2025. if (sgs->sum_nr_running > sds->leader_nr_running ||
  2026. (sgs->sum_nr_running == sds->leader_nr_running &&
  2027. group_first_cpu(group) < group_first_cpu(sds->group_leader))) {
  2028. sds->group_leader = group;
  2029. sds->leader_nr_running = sgs->sum_nr_running;
  2030. }
  2031. }
  2032. /**
  2033. * check_power_save_busiest_group - see if there is potential for some power-savings balance
  2034. * @sds: Variable containing the statistics of the sched_domain
  2035. * under consideration.
  2036. * @this_cpu: Cpu at which we're currently performing load-balancing.
  2037. * @imbalance: Variable to store the imbalance.
  2038. *
  2039. * Description:
  2040. * Check if we have potential to perform some power-savings balance.
  2041. * If yes, set the busiest group to be the least loaded group in the
  2042. * sched_domain, so that it's CPUs can be put to idle.
  2043. *
  2044. * Returns 1 if there is potential to perform power-savings balance.
  2045. * Else returns 0.
  2046. */
  2047. static inline int check_power_save_busiest_group(struct sd_lb_stats *sds,
  2048. int this_cpu, unsigned long *imbalance)
  2049. {
  2050. if (!sds->power_savings_balance)
  2051. return 0;
  2052. if (sds->this != sds->group_leader ||
  2053. sds->group_leader == sds->group_min)
  2054. return 0;
  2055. *imbalance = sds->min_load_per_task;
  2056. sds->busiest = sds->group_min;
  2057. return 1;
  2058. }
  2059. #else /* CONFIG_SCHED_MC || CONFIG_SCHED_SMT */
  2060. static inline void init_sd_power_savings_stats(struct sched_domain *sd,
  2061. struct sd_lb_stats *sds, enum cpu_idle_type idle)
  2062. {
  2063. return;
  2064. }
  2065. static inline void update_sd_power_savings_stats(struct sched_group *group,
  2066. struct sd_lb_stats *sds, int local_group, struct sg_lb_stats *sgs)
  2067. {
  2068. return;
  2069. }
  2070. static inline int check_power_save_busiest_group(struct sd_lb_stats *sds,
  2071. int this_cpu, unsigned long *imbalance)
  2072. {
  2073. return 0;
  2074. }
  2075. #endif /* CONFIG_SCHED_MC || CONFIG_SCHED_SMT */
  2076. unsigned long default_scale_freq_power(struct sched_domain *sd, int cpu)
  2077. {
  2078. return SCHED_LOAD_SCALE;
  2079. }
  2080. unsigned long __weak arch_scale_freq_power(struct sched_domain *sd, int cpu)
  2081. {
  2082. return default_scale_freq_power(sd, cpu);
  2083. }
  2084. unsigned long default_scale_smt_power(struct sched_domain *sd, int cpu)
  2085. {
  2086. unsigned long weight = sd->span_weight;
  2087. unsigned long smt_gain = sd->smt_gain;
  2088. smt_gain /= weight;
  2089. return smt_gain;
  2090. }
  2091. unsigned long __weak arch_scale_smt_power(struct sched_domain *sd, int cpu)
  2092. {
  2093. return default_scale_smt_power(sd, cpu);
  2094. }
  2095. unsigned long scale_rt_power(int cpu)
  2096. {
  2097. struct rq *rq = cpu_rq(cpu);
  2098. u64 total, available;
  2099. total = sched_avg_period() + (rq->clock - rq->age_stamp);
  2100. if (unlikely(total < rq->rt_avg)) {
  2101. /* Ensures that power won't end up being negative */
  2102. available = 0;
  2103. } else {
  2104. available = total - rq->rt_avg;
  2105. }
  2106. if (unlikely((s64)total < SCHED_LOAD_SCALE))
  2107. total = SCHED_LOAD_SCALE;
  2108. total >>= SCHED_LOAD_SHIFT;
  2109. return div_u64(available, total);
  2110. }
  2111. static void update_cpu_power(struct sched_domain *sd, int cpu)
  2112. {
  2113. unsigned long weight = sd->span_weight;
  2114. unsigned long power = SCHED_LOAD_SCALE;
  2115. struct sched_group *sdg = sd->groups;
  2116. if ((sd->flags & SD_SHARE_CPUPOWER) && weight > 1) {
  2117. if (sched_feat(ARCH_POWER))
  2118. power *= arch_scale_smt_power(sd, cpu);
  2119. else
  2120. power *= default_scale_smt_power(sd, cpu);
  2121. power >>= SCHED_LOAD_SHIFT;
  2122. }
  2123. sdg->cpu_power_orig = power;
  2124. if (sched_feat(ARCH_POWER))
  2125. power *= arch_scale_freq_power(sd, cpu);
  2126. else
  2127. power *= default_scale_freq_power(sd, cpu);
  2128. power >>= SCHED_LOAD_SHIFT;
  2129. power *= scale_rt_power(cpu);
  2130. power >>= SCHED_LOAD_SHIFT;
  2131. if (!power)
  2132. power = 1;
  2133. cpu_rq(cpu)->cpu_power = power;
  2134. sdg->cpu_power = power;
  2135. }
  2136. static void update_group_power(struct sched_domain *sd, int cpu)
  2137. {
  2138. struct sched_domain *child = sd->child;
  2139. struct sched_group *group, *sdg = sd->groups;
  2140. unsigned long power;
  2141. if (!child) {
  2142. update_cpu_power(sd, cpu);
  2143. return;
  2144. }
  2145. power = 0;
  2146. group = child->groups;
  2147. do {
  2148. power += group->cpu_power;
  2149. group = group->next;
  2150. } while (group != child->groups);
  2151. sdg->cpu_power = power;
  2152. }
  2153. /*
  2154. * Try and fix up capacity for tiny siblings, this is needed when
  2155. * things like SD_ASYM_PACKING need f_b_g to select another sibling
  2156. * which on its own isn't powerful enough.
  2157. *
  2158. * See update_sd_pick_busiest() and check_asym_packing().
  2159. */
  2160. static inline int
  2161. fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
  2162. {
  2163. /*
  2164. * Only siblings can have significantly less than SCHED_LOAD_SCALE
  2165. */
  2166. if (sd->level != SD_LV_SIBLING)
  2167. return 0;
  2168. /*
  2169. * If ~90% of the cpu_power is still there, we're good.
  2170. */
  2171. if (group->cpu_power * 32 > group->cpu_power_orig * 29)
  2172. return 1;
  2173. return 0;
  2174. }
  2175. /**
  2176. * update_sg_lb_stats - Update sched_group's statistics for load balancing.
  2177. * @sd: The sched_domain whose statistics are to be updated.
  2178. * @group: sched_group whose statistics are to be updated.
  2179. * @this_cpu: Cpu for which load balance is currently performed.
  2180. * @idle: Idle status of this_cpu
  2181. * @load_idx: Load index of sched_domain of this_cpu for load calc.
  2182. * @sd_idle: Idle status of the sched_domain containing group.
  2183. * @local_group: Does group contain this_cpu.
  2184. * @cpus: Set of cpus considered for load balancing.
  2185. * @balance: Should we balance.
  2186. * @sgs: variable to hold the statistics for this group.
  2187. */
  2188. static inline void update_sg_lb_stats(struct sched_domain *sd,
  2189. struct sched_group *group, int this_cpu,
  2190. enum cpu_idle_type idle, int load_idx, int *sd_idle,
  2191. int local_group, const struct cpumask *cpus,
  2192. int *balance, struct sg_lb_stats *sgs)
  2193. {
  2194. unsigned long load, max_cpu_load, min_cpu_load, max_nr_running;
  2195. int i;
  2196. unsigned int balance_cpu = -1, first_idle_cpu = 0;
  2197. unsigned long avg_load_per_task = 0;
  2198. if (local_group)
  2199. balance_cpu = group_first_cpu(group);
  2200. /* Tally up the load of all CPUs in the group */
  2201. max_cpu_load = 0;
  2202. min_cpu_load = ~0UL;
  2203. max_nr_running = 0;
  2204. for_each_cpu_and(i, sched_group_cpus(group), cpus) {
  2205. struct rq *rq = cpu_rq(i);
  2206. if (*sd_idle && rq->nr_running)
  2207. *sd_idle = 0;
  2208. /* Bias balancing toward cpus of our domain */
  2209. if (local_group) {
  2210. if (idle_cpu(i) && !first_idle_cpu) {
  2211. first_idle_cpu = 1;
  2212. balance_cpu = i;
  2213. }
  2214. load = target_load(i, load_idx);
  2215. } else {
  2216. load = source_load(i, load_idx);
  2217. if (load > max_cpu_load) {
  2218. max_cpu_load = load;
  2219. max_nr_running = rq->nr_running;
  2220. }
  2221. if (min_cpu_load > load)
  2222. min_cpu_load = load;
  2223. }
  2224. sgs->group_load += load;
  2225. sgs->sum_nr_running += rq->nr_running;
  2226. sgs->sum_weighted_load += weighted_cpuload(i);
  2227. if (idle_cpu(i))
  2228. sgs->idle_cpus++;
  2229. }
  2230. /*
  2231. * First idle cpu or the first cpu(busiest) in this sched group
  2232. * is eligible for doing load balancing at this and above
  2233. * domains. In the newly idle case, we will allow all the cpu's
  2234. * to do the newly idle load balance.
  2235. */
  2236. if (idle != CPU_NEWLY_IDLE && local_group) {
  2237. if (balance_cpu != this_cpu) {
  2238. *balance = 0;
  2239. return;
  2240. }
  2241. update_group_power(sd, this_cpu);
  2242. }
  2243. /* Adjust by relative CPU power of the group */
  2244. sgs->avg_load = (sgs->group_load * SCHED_LOAD_SCALE) / group->cpu_power;
  2245. /*
  2246. * Consider the group unbalanced when the imbalance is larger
  2247. * than the average weight of two tasks.
  2248. *
  2249. * APZ: with cgroup the avg task weight can vary wildly and
  2250. * might not be a suitable number - should we keep a
  2251. * normalized nr_running number somewhere that negates
  2252. * the hierarchy?
  2253. */
  2254. if (sgs->sum_nr_running)
  2255. avg_load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running;
  2256. if ((max_cpu_load - min_cpu_load) > 2*avg_load_per_task && max_nr_running > 1)
  2257. sgs->group_imb = 1;
  2258. sgs->group_capacity = DIV_ROUND_CLOSEST(group->cpu_power, SCHED_LOAD_SCALE);
  2259. if (!sgs->group_capacity)
  2260. sgs->group_capacity = fix_small_capacity(sd, group);
  2261. sgs->group_weight = group->group_weight;
  2262. if (sgs->group_capacity > sgs->sum_nr_running)
  2263. sgs->group_has_capacity = 1;
  2264. }
  2265. /**
  2266. * update_sd_pick_busiest - return 1 on busiest group
  2267. * @sd: sched_domain whose statistics are to be checked
  2268. * @sds: sched_domain statistics
  2269. * @sg: sched_group candidate to be checked for being the busiest
  2270. * @sgs: sched_group statistics
  2271. * @this_cpu: the current cpu
  2272. *
  2273. * Determine if @sg is a busier group than the previously selected
  2274. * busiest group.
  2275. */
  2276. static bool update_sd_pick_busiest(struct sched_domain *sd,
  2277. struct sd_lb_stats *sds,
  2278. struct sched_group *sg,
  2279. struct sg_lb_stats *sgs,
  2280. int this_cpu)
  2281. {
  2282. if (sgs->avg_load <= sds->max_load)
  2283. return false;
  2284. if (sgs->sum_nr_running > sgs->group_capacity)
  2285. return true;
  2286. if (sgs->group_imb)
  2287. return true;
  2288. /*
  2289. * ASYM_PACKING needs to move all the work to the lowest
  2290. * numbered CPUs in the group, therefore mark all groups
  2291. * higher than ourself as busy.
  2292. */
  2293. if ((sd->flags & SD_ASYM_PACKING) && sgs->sum_nr_running &&
  2294. this_cpu < group_first_cpu(sg)) {
  2295. if (!sds->busiest)
  2296. return true;
  2297. if (group_first_cpu(sds->busiest) > group_first_cpu(sg))
  2298. return true;
  2299. }
  2300. return false;
  2301. }
  2302. /**
  2303. * update_sd_lb_stats - Update sched_group's statistics for load balancing.
  2304. * @sd: sched_domain whose statistics are to be updated.
  2305. * @this_cpu: Cpu for which load balance is currently performed.
  2306. * @idle: Idle status of this_cpu
  2307. * @sd_idle: Idle status of the sched_domain containing sg.
  2308. * @cpus: Set of cpus considered for load balancing.
  2309. * @balance: Should we balance.
  2310. * @sds: variable to hold the statistics for this sched_domain.
  2311. */
  2312. static inline void update_sd_lb_stats(struct sched_domain *sd, int this_cpu,
  2313. enum cpu_idle_type idle, int *sd_idle,
  2314. const struct cpumask *cpus, int *balance,
  2315. struct sd_lb_stats *sds)
  2316. {
  2317. struct sched_domain *child = sd->child;
  2318. struct sched_group *sg = sd->groups;
  2319. struct sg_lb_stats sgs;
  2320. int load_idx, prefer_sibling = 0;
  2321. if (child && child->flags & SD_PREFER_SIBLING)
  2322. prefer_sibling = 1;
  2323. init_sd_power_savings_stats(sd, sds, idle);
  2324. load_idx = get_sd_load_idx(sd, idle);
  2325. do {
  2326. int local_group;
  2327. local_group = cpumask_test_cpu(this_cpu, sched_group_cpus(sg));
  2328. memset(&sgs, 0, sizeof(sgs));
  2329. update_sg_lb_stats(sd, sg, this_cpu, idle, load_idx, sd_idle,
  2330. local_group, cpus, balance, &sgs);
  2331. if (local_group && !(*balance))
  2332. return;
  2333. sds->total_load += sgs.group_load;
  2334. sds->total_pwr += sg->cpu_power;
  2335. /*
  2336. * In case the child domain prefers tasks go to siblings
  2337. * first, lower the sg capacity to one so that we'll try
  2338. * and move all the excess tasks away. We lower the capacity
  2339. * of a group only if the local group has the capacity to fit
  2340. * these excess tasks, i.e. nr_running < group_capacity. The
  2341. * extra check prevents the case where you always pull from the
  2342. * heaviest group when it is already under-utilized (possible
  2343. * with a large weight task outweighs the tasks on the system).
  2344. */
  2345. if (prefer_sibling && !local_group && sds->this_has_capacity)
  2346. sgs.group_capacity = min(sgs.group_capacity, 1UL);
  2347. if (local_group) {
  2348. sds->this_load = sgs.avg_load;
  2349. sds->this = sg;
  2350. sds->this_nr_running = sgs.sum_nr_running;
  2351. sds->this_load_per_task = sgs.sum_weighted_load;
  2352. sds->this_has_capacity = sgs.group_has_capacity;
  2353. sds->this_idle_cpus = sgs.idle_cpus;
  2354. } else if (update_sd_pick_busiest(sd, sds, sg, &sgs, this_cpu)) {
  2355. sds->max_load = sgs.avg_load;
  2356. sds->busiest = sg;
  2357. sds->busiest_nr_running = sgs.sum_nr_running;
  2358. sds->busiest_idle_cpus = sgs.idle_cpus;
  2359. sds->busiest_group_capacity = sgs.group_capacity;
  2360. sds->busiest_load_per_task = sgs.sum_weighted_load;
  2361. sds->busiest_has_capacity = sgs.group_has_capacity;
  2362. sds->busiest_group_weight = sgs.group_weight;
  2363. sds->group_imb = sgs.group_imb;
  2364. }
  2365. update_sd_power_savings_stats(sg, sds, local_group, &sgs);
  2366. sg = sg->next;
  2367. } while (sg != sd->groups);
  2368. }
  2369. int __weak arch_sd_sibling_asym_packing(void)
  2370. {
  2371. return 0*SD_ASYM_PACKING;
  2372. }
  2373. /**
  2374. * check_asym_packing - Check to see if the group is packed into the
  2375. * sched doman.
  2376. *
  2377. * This is primarily intended to used at the sibling level. Some
  2378. * cores like POWER7 prefer to use lower numbered SMT threads. In the
  2379. * case of POWER7, it can move to lower SMT modes only when higher
  2380. * threads are idle. When in lower SMT modes, the threads will
  2381. * perform better since they share less core resources. Hence when we
  2382. * have idle threads, we want them to be the higher ones.
  2383. *
  2384. * This packing function is run on idle threads. It checks to see if
  2385. * the busiest CPU in this domain (core in the P7 case) has a higher
  2386. * CPU number than the packing function is being run on. Here we are
  2387. * assuming lower CPU number will be equivalent to lower a SMT thread
  2388. * number.
  2389. *
  2390. * Returns 1 when packing is required and a task should be moved to
  2391. * this CPU. The amount of the imbalance is returned in *imbalance.
  2392. *
  2393. * @sd: The sched_domain whose packing is to be checked.
  2394. * @sds: Statistics of the sched_domain which is to be packed
  2395. * @this_cpu: The cpu at whose sched_domain we're performing load-balance.
  2396. * @imbalance: returns amount of imbalanced due to packing.
  2397. */
  2398. static int check_asym_packing(struct sched_domain *sd,
  2399. struct sd_lb_stats *sds,
  2400. int this_cpu, unsigned long *imbalance)
  2401. {
  2402. int busiest_cpu;
  2403. if (!(sd->flags & SD_ASYM_PACKING))
  2404. return 0;
  2405. if (!sds->busiest)
  2406. return 0;
  2407. busiest_cpu = group_first_cpu(sds->busiest);
  2408. if (this_cpu > busiest_cpu)
  2409. return 0;
  2410. *imbalance = DIV_ROUND_CLOSEST(sds->max_load * sds->busiest->cpu_power,
  2411. SCHED_LOAD_SCALE);
  2412. return 1;
  2413. }
  2414. /**
  2415. * fix_small_imbalance - Calculate the minor imbalance that exists
  2416. * amongst the groups of a sched_domain, during
  2417. * load balancing.
  2418. * @sds: Statistics of the sched_domain whose imbalance is to be calculated.
  2419. * @this_cpu: The cpu at whose sched_domain we're performing load-balance.
  2420. * @imbalance: Variable to store the imbalance.
  2421. */
  2422. static inline void fix_small_imbalance(struct sd_lb_stats *sds,
  2423. int this_cpu, unsigned long *imbalance)
  2424. {
  2425. unsigned long tmp, pwr_now = 0, pwr_move = 0;
  2426. unsigned int imbn = 2;
  2427. unsigned long scaled_busy_load_per_task;
  2428. if (sds->this_nr_running) {
  2429. sds->this_load_per_task /= sds->this_nr_running;
  2430. if (sds->busiest_load_per_task >
  2431. sds->this_load_per_task)
  2432. imbn = 1;
  2433. } else
  2434. sds->this_load_per_task =
  2435. cpu_avg_load_per_task(this_cpu);
  2436. scaled_busy_load_per_task = sds->busiest_load_per_task
  2437. * SCHED_LOAD_SCALE;
  2438. scaled_busy_load_per_task /= sds->busiest->cpu_power;
  2439. if (sds->max_load - sds->this_load + scaled_busy_load_per_task >=
  2440. (scaled_busy_load_per_task * imbn)) {
  2441. *imbalance = sds->busiest_load_per_task;
  2442. return;
  2443. }
  2444. /*
  2445. * OK, we don't have enough imbalance to justify moving tasks,
  2446. * however we may be able to increase total CPU power used by
  2447. * moving them.
  2448. */
  2449. pwr_now += sds->busiest->cpu_power *
  2450. min(sds->busiest_load_per_task, sds->max_load);
  2451. pwr_now += sds->this->cpu_power *
  2452. min(sds->this_load_per_task, sds->this_load);
  2453. pwr_now /= SCHED_LOAD_SCALE;
  2454. /* Amount of load we'd subtract */
  2455. tmp = (sds->busiest_load_per_task * SCHED_LOAD_SCALE) /
  2456. sds->busiest->cpu_power;
  2457. if (sds->max_load > tmp)
  2458. pwr_move += sds->busiest->cpu_power *
  2459. min(sds->busiest_load_per_task, sds->max_load - tmp);
  2460. /* Amount of load we'd add */
  2461. if (sds->max_load * sds->busiest->cpu_power <
  2462. sds->busiest_load_per_task * SCHED_LOAD_SCALE)
  2463. tmp = (sds->max_load * sds->busiest->cpu_power) /
  2464. sds->this->cpu_power;
  2465. else
  2466. tmp = (sds->busiest_load_per_task * SCHED_LOAD_SCALE) /
  2467. sds->this->cpu_power;
  2468. pwr_move += sds->this->cpu_power *
  2469. min(sds->this_load_per_task, sds->this_load + tmp);
  2470. pwr_move /= SCHED_LOAD_SCALE;
  2471. /* Move if we gain throughput */
  2472. if (pwr_move > pwr_now)
  2473. *imbalance = sds->busiest_load_per_task;
  2474. }
  2475. /**
  2476. * calculate_imbalance - Calculate the amount of imbalance present within the
  2477. * groups of a given sched_domain during load balance.
  2478. * @sds: statistics of the sched_domain whose imbalance is to be calculated.
  2479. * @this_cpu: Cpu for which currently load balance is being performed.
  2480. * @imbalance: The variable to store the imbalance.
  2481. */
  2482. static inline void calculate_imbalance(struct sd_lb_stats *sds, int this_cpu,
  2483. unsigned long *imbalance)
  2484. {
  2485. unsigned long max_pull, load_above_capacity = ~0UL;
  2486. sds->busiest_load_per_task /= sds->busiest_nr_running;
  2487. if (sds->group_imb) {
  2488. sds->busiest_load_per_task =
  2489. min(sds->busiest_load_per_task, sds->avg_load);
  2490. }
  2491. /*
  2492. * In the presence of smp nice balancing, certain scenarios can have
  2493. * max load less than avg load(as we skip the groups at or below
  2494. * its cpu_power, while calculating max_load..)
  2495. */
  2496. if (sds->max_load < sds->avg_load) {
  2497. *imbalance = 0;
  2498. return fix_small_imbalance(sds, this_cpu, imbalance);
  2499. }
  2500. if (!sds->group_imb) {
  2501. /*
  2502. * Don't want to pull so many tasks that a group would go idle.
  2503. */
  2504. load_above_capacity = (sds->busiest_nr_running -
  2505. sds->busiest_group_capacity);
  2506. load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_LOAD_SCALE);
  2507. load_above_capacity /= sds->busiest->cpu_power;
  2508. }
  2509. /*
  2510. * We're trying to get all the cpus to the average_load, so we don't
  2511. * want to push ourselves above the average load, nor do we wish to
  2512. * reduce the max loaded cpu below the average load. At the same time,
  2513. * we also don't want to reduce the group load below the group capacity
  2514. * (so that we can implement power-savings policies etc). Thus we look
  2515. * for the minimum possible imbalance.
  2516. * Be careful of negative numbers as they'll appear as very large values
  2517. * with unsigned longs.
  2518. */
  2519. max_pull = min(sds->max_load - sds->avg_load, load_above_capacity);
  2520. /* How much load to actually move to equalise the imbalance */
  2521. *imbalance = min(max_pull * sds->busiest->cpu_power,
  2522. (sds->avg_load - sds->this_load) * sds->this->cpu_power)
  2523. / SCHED_LOAD_SCALE;
  2524. /*
  2525. * if *imbalance is less than the average load per runnable task
  2526. * there is no gaurantee that any tasks will be moved so we'll have
  2527. * a think about bumping its value to force at least one task to be
  2528. * moved
  2529. */
  2530. if (*imbalance < sds->busiest_load_per_task)
  2531. return fix_small_imbalance(sds, this_cpu, imbalance);
  2532. }
  2533. /******* find_busiest_group() helpers end here *********************/
  2534. /**
  2535. * find_busiest_group - Returns the busiest group within the sched_domain
  2536. * if there is an imbalance. If there isn't an imbalance, and
  2537. * the user has opted for power-savings, it returns a group whose
  2538. * CPUs can be put to idle by rebalancing those tasks elsewhere, if
  2539. * such a group exists.
  2540. *
  2541. * Also calculates the amount of weighted load which should be moved
  2542. * to restore balance.
  2543. *
  2544. * @sd: The sched_domain whose busiest group is to be returned.
  2545. * @this_cpu: The cpu for which load balancing is currently being performed.
  2546. * @imbalance: Variable which stores amount of weighted load which should
  2547. * be moved to restore balance/put a group to idle.
  2548. * @idle: The idle status of this_cpu.
  2549. * @sd_idle: The idleness of sd
  2550. * @cpus: The set of CPUs under consideration for load-balancing.
  2551. * @balance: Pointer to a variable indicating if this_cpu
  2552. * is the appropriate cpu to perform load balancing at this_level.
  2553. *
  2554. * Returns: - the busiest group if imbalance exists.
  2555. * - If no imbalance and user has opted for power-savings balance,
  2556. * return the least loaded group whose CPUs can be
  2557. * put to idle by rebalancing its tasks onto our group.
  2558. */
  2559. static struct sched_group *
  2560. find_busiest_group(struct sched_domain *sd, int this_cpu,
  2561. unsigned long *imbalance, enum cpu_idle_type idle,
  2562. int *sd_idle, const struct cpumask *cpus, int *balance)
  2563. {
  2564. struct sd_lb_stats sds;
  2565. memset(&sds, 0, sizeof(sds));
  2566. /*
  2567. * Compute the various statistics relavent for load balancing at
  2568. * this level.
  2569. */
  2570. update_sd_lb_stats(sd, this_cpu, idle, sd_idle, cpus,
  2571. balance, &sds);
  2572. /* Cases where imbalance does not exist from POV of this_cpu */
  2573. /* 1) this_cpu is not the appropriate cpu to perform load balancing
  2574. * at this level.
  2575. * 2) There is no busy sibling group to pull from.
  2576. * 3) This group is the busiest group.
  2577. * 4) This group is more busy than the avg busieness at this
  2578. * sched_domain.
  2579. * 5) The imbalance is within the specified limit.
  2580. *
  2581. * Note: when doing newidle balance, if the local group has excess
  2582. * capacity (i.e. nr_running < group_capacity) and the busiest group
  2583. * does not have any capacity, we force a load balance to pull tasks
  2584. * to the local group. In this case, we skip past checks 3, 4 and 5.
  2585. */
  2586. if (!(*balance))
  2587. goto ret;
  2588. if ((idle == CPU_IDLE || idle == CPU_NEWLY_IDLE) &&
  2589. check_asym_packing(sd, &sds, this_cpu, imbalance))
  2590. return sds.busiest;
  2591. if (!sds.busiest || sds.busiest_nr_running == 0)
  2592. goto out_balanced;
  2593. /* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */
  2594. if (idle == CPU_NEWLY_IDLE && sds.this_has_capacity &&
  2595. !sds.busiest_has_capacity)
  2596. goto force_balance;
  2597. if (sds.this_load >= sds.max_load)
  2598. goto out_balanced;
  2599. sds.avg_load = (SCHED_LOAD_SCALE * sds.total_load) / sds.total_pwr;
  2600. if (sds.this_load >= sds.avg_load)
  2601. goto out_balanced;
  2602. /*
  2603. * In the CPU_NEWLY_IDLE, use imbalance_pct to be conservative.
  2604. * And to check for busy balance use !idle_cpu instead of
  2605. * CPU_NOT_IDLE. This is because HT siblings will use CPU_NOT_IDLE
  2606. * even when they are idle.
  2607. */
  2608. if (idle == CPU_NEWLY_IDLE || !idle_cpu(this_cpu)) {
  2609. if (100 * sds.max_load <= sd->imbalance_pct * sds.this_load)
  2610. goto out_balanced;
  2611. } else {
  2612. /*
  2613. * This cpu is idle. If the busiest group load doesn't
  2614. * have more tasks than the number of available cpu's and
  2615. * there is no imbalance between this and busiest group
  2616. * wrt to idle cpu's, it is balanced.
  2617. */
  2618. if ((sds.this_idle_cpus <= sds.busiest_idle_cpus + 1) &&
  2619. sds.busiest_nr_running <= sds.busiest_group_weight)
  2620. goto out_balanced;
  2621. }
  2622. force_balance:
  2623. /* Looks like there is an imbalance. Compute it */
  2624. calculate_imbalance(&sds, this_cpu, imbalance);
  2625. return sds.busiest;
  2626. out_balanced:
  2627. /*
  2628. * There is no obvious imbalance. But check if we can do some balancing
  2629. * to save power.
  2630. */
  2631. if (check_power_save_busiest_group(&sds, this_cpu, imbalance))
  2632. return sds.busiest;
  2633. ret:
  2634. *imbalance = 0;
  2635. return NULL;
  2636. }
  2637. /*
  2638. * find_busiest_queue - find the busiest runqueue among the cpus in group.
  2639. */
  2640. static struct rq *
  2641. find_busiest_queue(struct sched_domain *sd, struct sched_group *group,
  2642. enum cpu_idle_type idle, unsigned long imbalance,
  2643. const struct cpumask *cpus)
  2644. {
  2645. struct rq *busiest = NULL, *rq;
  2646. unsigned long max_load = 0;
  2647. int i;
  2648. for_each_cpu(i, sched_group_cpus(group)) {
  2649. unsigned long power = power_of(i);
  2650. unsigned long capacity = DIV_ROUND_CLOSEST(power, SCHED_LOAD_SCALE);
  2651. unsigned long wl;
  2652. if (!capacity)
  2653. capacity = fix_small_capacity(sd, group);
  2654. if (!cpumask_test_cpu(i, cpus))
  2655. continue;
  2656. rq = cpu_rq(i);
  2657. wl = weighted_cpuload(i);
  2658. /*
  2659. * When comparing with imbalance, use weighted_cpuload()
  2660. * which is not scaled with the cpu power.
  2661. */
  2662. if (capacity && rq->nr_running == 1 && wl > imbalance)
  2663. continue;
  2664. /*
  2665. * For the load comparisons with the other cpu's, consider
  2666. * the weighted_cpuload() scaled with the cpu power, so that
  2667. * the load can be moved away from the cpu that is potentially
  2668. * running at a lower capacity.
  2669. */
  2670. wl = (wl * SCHED_LOAD_SCALE) / power;
  2671. if (wl > max_load) {
  2672. max_load = wl;
  2673. busiest = rq;
  2674. }
  2675. }
  2676. return busiest;
  2677. }
  2678. /*
  2679. * Max backoff if we encounter pinned tasks. Pretty arbitrary value, but
  2680. * so long as it is large enough.
  2681. */
  2682. #define MAX_PINNED_INTERVAL 512
  2683. /* Working cpumask for load_balance and load_balance_newidle. */
  2684. static DEFINE_PER_CPU(cpumask_var_t, load_balance_tmpmask);
  2685. static int need_active_balance(struct sched_domain *sd, int sd_idle, int idle,
  2686. int busiest_cpu, int this_cpu)
  2687. {
  2688. if (idle == CPU_NEWLY_IDLE) {
  2689. /*
  2690. * ASYM_PACKING needs to force migrate tasks from busy but
  2691. * higher numbered CPUs in order to pack all tasks in the
  2692. * lowest numbered CPUs.
  2693. */
  2694. if ((sd->flags & SD_ASYM_PACKING) && busiest_cpu > this_cpu)
  2695. return 1;
  2696. /*
  2697. * The only task running in a non-idle cpu can be moved to this
  2698. * cpu in an attempt to completely freeup the other CPU
  2699. * package.
  2700. *
  2701. * The package power saving logic comes from
  2702. * find_busiest_group(). If there are no imbalance, then
  2703. * f_b_g() will return NULL. However when sched_mc={1,2} then
  2704. * f_b_g() will select a group from which a running task may be
  2705. * pulled to this cpu in order to make the other package idle.
  2706. * If there is no opportunity to make a package idle and if
  2707. * there are no imbalance, then f_b_g() will return NULL and no
  2708. * action will be taken in load_balance_newidle().
  2709. *
  2710. * Under normal task pull operation due to imbalance, there
  2711. * will be more than one task in the source run queue and
  2712. * move_tasks() will succeed. ld_moved will be true and this
  2713. * active balance code will not be triggered.
  2714. */
  2715. if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
  2716. !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2717. return 0;
  2718. if (sched_mc_power_savings < POWERSAVINGS_BALANCE_WAKEUP)
  2719. return 0;
  2720. }
  2721. return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
  2722. }
  2723. static int active_load_balance_cpu_stop(void *data);
  2724. /*
  2725. * Check this_cpu to ensure it is balanced within domain. Attempt to move
  2726. * tasks if there is an imbalance.
  2727. */
  2728. static int load_balance(int this_cpu, struct rq *this_rq,
  2729. struct sched_domain *sd, enum cpu_idle_type idle,
  2730. int *balance)
  2731. {
  2732. int ld_moved, all_pinned = 0, active_balance = 0, sd_idle = 0;
  2733. struct sched_group *group;
  2734. unsigned long imbalance;
  2735. struct rq *busiest;
  2736. unsigned long flags;
  2737. struct cpumask *cpus = __get_cpu_var(load_balance_tmpmask);
  2738. cpumask_copy(cpus, cpu_active_mask);
  2739. /*
  2740. * When power savings policy is enabled for the parent domain, idle
  2741. * sibling can pick up load irrespective of busy siblings. In this case,
  2742. * let the state of idle sibling percolate up as CPU_IDLE, instead of
  2743. * portraying it as CPU_NOT_IDLE.
  2744. */
  2745. if (idle != CPU_NOT_IDLE && sd->flags & SD_SHARE_CPUPOWER &&
  2746. !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2747. sd_idle = 1;
  2748. schedstat_inc(sd, lb_count[idle]);
  2749. redo:
  2750. group = find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle,
  2751. cpus, balance);
  2752. if (*balance == 0)
  2753. goto out_balanced;
  2754. if (!group) {
  2755. schedstat_inc(sd, lb_nobusyg[idle]);
  2756. goto out_balanced;
  2757. }
  2758. busiest = find_busiest_queue(sd, group, idle, imbalance, cpus);
  2759. if (!busiest) {
  2760. schedstat_inc(sd, lb_nobusyq[idle]);
  2761. goto out_balanced;
  2762. }
  2763. BUG_ON(busiest == this_rq);
  2764. schedstat_add(sd, lb_imbalance[idle], imbalance);
  2765. ld_moved = 0;
  2766. if (busiest->nr_running > 1) {
  2767. /*
  2768. * Attempt to move tasks. If find_busiest_group has found
  2769. * an imbalance but busiest->nr_running <= 1, the group is
  2770. * still unbalanced. ld_moved simply stays zero, so it is
  2771. * correctly treated as an imbalance.
  2772. */
  2773. local_irq_save(flags);
  2774. double_rq_lock(this_rq, busiest);
  2775. ld_moved = move_tasks(this_rq, this_cpu, busiest,
  2776. imbalance, sd, idle, &all_pinned);
  2777. double_rq_unlock(this_rq, busiest);
  2778. local_irq_restore(flags);
  2779. /*
  2780. * some other cpu did the load balance for us.
  2781. */
  2782. if (ld_moved && this_cpu != smp_processor_id())
  2783. resched_cpu(this_cpu);
  2784. /* All tasks on this runqueue were pinned by CPU affinity */
  2785. if (unlikely(all_pinned)) {
  2786. cpumask_clear_cpu(cpu_of(busiest), cpus);
  2787. if (!cpumask_empty(cpus))
  2788. goto redo;
  2789. goto out_balanced;
  2790. }
  2791. }
  2792. if (!ld_moved) {
  2793. schedstat_inc(sd, lb_failed[idle]);
  2794. /*
  2795. * Increment the failure counter only on periodic balance.
  2796. * We do not want newidle balance, which can be very
  2797. * frequent, pollute the failure counter causing
  2798. * excessive cache_hot migrations and active balances.
  2799. */
  2800. if (idle != CPU_NEWLY_IDLE)
  2801. sd->nr_balance_failed++;
  2802. if (need_active_balance(sd, sd_idle, idle, cpu_of(busiest),
  2803. this_cpu)) {
  2804. raw_spin_lock_irqsave(&busiest->lock, flags);
  2805. /* don't kick the active_load_balance_cpu_stop,
  2806. * if the curr task on busiest cpu can't be
  2807. * moved to this_cpu
  2808. */
  2809. if (!cpumask_test_cpu(this_cpu,
  2810. &busiest->curr->cpus_allowed)) {
  2811. raw_spin_unlock_irqrestore(&busiest->lock,
  2812. flags);
  2813. all_pinned = 1;
  2814. goto out_one_pinned;
  2815. }
  2816. /*
  2817. * ->active_balance synchronizes accesses to
  2818. * ->active_balance_work. Once set, it's cleared
  2819. * only after active load balance is finished.
  2820. */
  2821. if (!busiest->active_balance) {
  2822. busiest->active_balance = 1;
  2823. busiest->push_cpu = this_cpu;
  2824. active_balance = 1;
  2825. }
  2826. raw_spin_unlock_irqrestore(&busiest->lock, flags);
  2827. if (active_balance)
  2828. stop_one_cpu_nowait(cpu_of(busiest),
  2829. active_load_balance_cpu_stop, busiest,
  2830. &busiest->active_balance_work);
  2831. /*
  2832. * We've kicked active balancing, reset the failure
  2833. * counter.
  2834. */
  2835. sd->nr_balance_failed = sd->cache_nice_tries+1;
  2836. }
  2837. } else
  2838. sd->nr_balance_failed = 0;
  2839. if (likely(!active_balance)) {
  2840. /* We were unbalanced, so reset the balancing interval */
  2841. sd->balance_interval = sd->min_interval;
  2842. } else {
  2843. /*
  2844. * If we've begun active balancing, start to back off. This
  2845. * case may not be covered by the all_pinned logic if there
  2846. * is only 1 task on the busy runqueue (because we don't call
  2847. * move_tasks).
  2848. */
  2849. if (sd->balance_interval < sd->max_interval)
  2850. sd->balance_interval *= 2;
  2851. }
  2852. if (!ld_moved && !sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
  2853. !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2854. ld_moved = -1;
  2855. goto out;
  2856. out_balanced:
  2857. schedstat_inc(sd, lb_balanced[idle]);
  2858. sd->nr_balance_failed = 0;
  2859. out_one_pinned:
  2860. /* tune up the balancing interval */
  2861. if ((all_pinned && sd->balance_interval < MAX_PINNED_INTERVAL) ||
  2862. (sd->balance_interval < sd->max_interval))
  2863. sd->balance_interval *= 2;
  2864. if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
  2865. !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2866. ld_moved = -1;
  2867. else
  2868. ld_moved = 0;
  2869. out:
  2870. return ld_moved;
  2871. }
  2872. /*
  2873. * idle_balance is called by schedule() if this_cpu is about to become
  2874. * idle. Attempts to pull tasks from other CPUs.
  2875. */
  2876. static void idle_balance(int this_cpu, struct rq *this_rq)
  2877. {
  2878. struct sched_domain *sd;
  2879. int pulled_task = 0;
  2880. unsigned long next_balance = jiffies + HZ;
  2881. this_rq->idle_stamp = this_rq->clock;
  2882. if (this_rq->avg_idle < sysctl_sched_migration_cost)
  2883. return;
  2884. /*
  2885. * Drop the rq->lock, but keep IRQ/preempt disabled.
  2886. */
  2887. raw_spin_unlock(&this_rq->lock);
  2888. update_shares(this_cpu);
  2889. for_each_domain(this_cpu, sd) {
  2890. unsigned long interval;
  2891. int balance = 1;
  2892. if (!(sd->flags & SD_LOAD_BALANCE))
  2893. continue;
  2894. if (sd->flags & SD_BALANCE_NEWIDLE) {
  2895. /* If we've pulled tasks over stop searching: */
  2896. pulled_task = load_balance(this_cpu, this_rq,
  2897. sd, CPU_NEWLY_IDLE, &balance);
  2898. }
  2899. interval = msecs_to_jiffies(sd->balance_interval);
  2900. if (time_after(next_balance, sd->last_balance + interval))
  2901. next_balance = sd->last_balance + interval;
  2902. if (pulled_task) {
  2903. this_rq->idle_stamp = 0;
  2904. break;
  2905. }
  2906. }
  2907. raw_spin_lock(&this_rq->lock);
  2908. if (pulled_task || time_after(jiffies, this_rq->next_balance)) {
  2909. /*
  2910. * We are going idle. next_balance may be set based on
  2911. * a busy processor. So reset next_balance.
  2912. */
  2913. this_rq->next_balance = next_balance;
  2914. }
  2915. }
  2916. /*
  2917. * active_load_balance_cpu_stop is run by cpu stopper. It pushes
  2918. * running tasks off the busiest CPU onto idle CPUs. It requires at
  2919. * least 1 task to be running on each physical CPU where possible, and
  2920. * avoids physical / logical imbalances.
  2921. */
  2922. static int active_load_balance_cpu_stop(void *data)
  2923. {
  2924. struct rq *busiest_rq = data;
  2925. int busiest_cpu = cpu_of(busiest_rq);
  2926. int target_cpu = busiest_rq->push_cpu;
  2927. struct rq *target_rq = cpu_rq(target_cpu);
  2928. struct sched_domain *sd;
  2929. raw_spin_lock_irq(&busiest_rq->lock);
  2930. /* make sure the requested cpu hasn't gone down in the meantime */
  2931. if (unlikely(busiest_cpu != smp_processor_id() ||
  2932. !busiest_rq->active_balance))
  2933. goto out_unlock;
  2934. /* Is there any task to move? */
  2935. if (busiest_rq->nr_running <= 1)
  2936. goto out_unlock;
  2937. /*
  2938. * This condition is "impossible", if it occurs
  2939. * we need to fix it. Originally reported by
  2940. * Bjorn Helgaas on a 128-cpu setup.
  2941. */
  2942. BUG_ON(busiest_rq == target_rq);
  2943. /* move a task from busiest_rq to target_rq */
  2944. double_lock_balance(busiest_rq, target_rq);
  2945. /* Search for an sd spanning us and the target CPU. */
  2946. for_each_domain(target_cpu, sd) {
  2947. if ((sd->flags & SD_LOAD_BALANCE) &&
  2948. cpumask_test_cpu(busiest_cpu, sched_domain_span(sd)))
  2949. break;
  2950. }
  2951. if (likely(sd)) {
  2952. schedstat_inc(sd, alb_count);
  2953. if (move_one_task(target_rq, target_cpu, busiest_rq,
  2954. sd, CPU_IDLE))
  2955. schedstat_inc(sd, alb_pushed);
  2956. else
  2957. schedstat_inc(sd, alb_failed);
  2958. }
  2959. double_unlock_balance(busiest_rq, target_rq);
  2960. out_unlock:
  2961. busiest_rq->active_balance = 0;
  2962. raw_spin_unlock_irq(&busiest_rq->lock);
  2963. return 0;
  2964. }
  2965. #ifdef CONFIG_NO_HZ
  2966. static DEFINE_PER_CPU(struct call_single_data, remote_sched_softirq_cb);
  2967. static void trigger_sched_softirq(void *data)
  2968. {
  2969. raise_softirq_irqoff(SCHED_SOFTIRQ);
  2970. }
  2971. static inline void init_sched_softirq_csd(struct call_single_data *csd)
  2972. {
  2973. csd->func = trigger_sched_softirq;
  2974. csd->info = NULL;
  2975. csd->flags = 0;
  2976. csd->priv = 0;
  2977. }
  2978. /*
  2979. * idle load balancing details
  2980. * - One of the idle CPUs nominates itself as idle load_balancer, while
  2981. * entering idle.
  2982. * - This idle load balancer CPU will also go into tickless mode when
  2983. * it is idle, just like all other idle CPUs
  2984. * - When one of the busy CPUs notice that there may be an idle rebalancing
  2985. * needed, they will kick the idle load balancer, which then does idle
  2986. * load balancing for all the idle CPUs.
  2987. */
  2988. static struct {
  2989. atomic_t load_balancer;
  2990. atomic_t first_pick_cpu;
  2991. atomic_t second_pick_cpu;
  2992. cpumask_var_t idle_cpus_mask;
  2993. cpumask_var_t grp_idle_mask;
  2994. unsigned long next_balance; /* in jiffy units */
  2995. } nohz ____cacheline_aligned;
  2996. int get_nohz_load_balancer(void)
  2997. {
  2998. return atomic_read(&nohz.load_balancer);
  2999. }
  3000. #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
  3001. /**
  3002. * lowest_flag_domain - Return lowest sched_domain containing flag.
  3003. * @cpu: The cpu whose lowest level of sched domain is to
  3004. * be returned.
  3005. * @flag: The flag to check for the lowest sched_domain
  3006. * for the given cpu.
  3007. *
  3008. * Returns the lowest sched_domain of a cpu which contains the given flag.
  3009. */
  3010. static inline struct sched_domain *lowest_flag_domain(int cpu, int flag)
  3011. {
  3012. struct sched_domain *sd;
  3013. for_each_domain(cpu, sd)
  3014. if (sd && (sd->flags & flag))
  3015. break;
  3016. return sd;
  3017. }
  3018. /**
  3019. * for_each_flag_domain - Iterates over sched_domains containing the flag.
  3020. * @cpu: The cpu whose domains we're iterating over.
  3021. * @sd: variable holding the value of the power_savings_sd
  3022. * for cpu.
  3023. * @flag: The flag to filter the sched_domains to be iterated.
  3024. *
  3025. * Iterates over all the scheduler domains for a given cpu that has the 'flag'
  3026. * set, starting from the lowest sched_domain to the highest.
  3027. */
  3028. #define for_each_flag_domain(cpu, sd, flag) \
  3029. for (sd = lowest_flag_domain(cpu, flag); \
  3030. (sd && (sd->flags & flag)); sd = sd->parent)
  3031. /**
  3032. * is_semi_idle_group - Checks if the given sched_group is semi-idle.
  3033. * @ilb_group: group to be checked for semi-idleness
  3034. *
  3035. * Returns: 1 if the group is semi-idle. 0 otherwise.
  3036. *
  3037. * We define a sched_group to be semi idle if it has atleast one idle-CPU
  3038. * and atleast one non-idle CPU. This helper function checks if the given
  3039. * sched_group is semi-idle or not.
  3040. */
  3041. static inline int is_semi_idle_group(struct sched_group *ilb_group)
  3042. {
  3043. cpumask_and(nohz.grp_idle_mask, nohz.idle_cpus_mask,
  3044. sched_group_cpus(ilb_group));
  3045. /*
  3046. * A sched_group is semi-idle when it has atleast one busy cpu
  3047. * and atleast one idle cpu.
  3048. */
  3049. if (cpumask_empty(nohz.grp_idle_mask))
  3050. return 0;
  3051. if (cpumask_equal(nohz.grp_idle_mask, sched_group_cpus(ilb_group)))
  3052. return 0;
  3053. return 1;
  3054. }
  3055. /**
  3056. * find_new_ilb - Finds the optimum idle load balancer for nomination.
  3057. * @cpu: The cpu which is nominating a new idle_load_balancer.
  3058. *
  3059. * Returns: Returns the id of the idle load balancer if it exists,
  3060. * Else, returns >= nr_cpu_ids.
  3061. *
  3062. * This algorithm picks the idle load balancer such that it belongs to a
  3063. * semi-idle powersavings sched_domain. The idea is to try and avoid
  3064. * completely idle packages/cores just for the purpose of idle load balancing
  3065. * when there are other idle cpu's which are better suited for that job.
  3066. */
  3067. static int find_new_ilb(int cpu)
  3068. {
  3069. struct sched_domain *sd;
  3070. struct sched_group *ilb_group;
  3071. /*
  3072. * Have idle load balancer selection from semi-idle packages only
  3073. * when power-aware load balancing is enabled
  3074. */
  3075. if (!(sched_smt_power_savings || sched_mc_power_savings))
  3076. goto out_done;
  3077. /*
  3078. * Optimize for the case when we have no idle CPUs or only one
  3079. * idle CPU. Don't walk the sched_domain hierarchy in such cases
  3080. */
  3081. if (cpumask_weight(nohz.idle_cpus_mask) < 2)
  3082. goto out_done;
  3083. for_each_flag_domain(cpu, sd, SD_POWERSAVINGS_BALANCE) {
  3084. ilb_group = sd->groups;
  3085. do {
  3086. if (is_semi_idle_group(ilb_group))
  3087. return cpumask_first(nohz.grp_idle_mask);
  3088. ilb_group = ilb_group->next;
  3089. } while (ilb_group != sd->groups);
  3090. }
  3091. out_done:
  3092. return nr_cpu_ids;
  3093. }
  3094. #else /* (CONFIG_SCHED_MC || CONFIG_SCHED_SMT) */
  3095. static inline int find_new_ilb(int call_cpu)
  3096. {
  3097. return nr_cpu_ids;
  3098. }
  3099. #endif
  3100. /*
  3101. * Kick a CPU to do the nohz balancing, if it is time for it. We pick the
  3102. * nohz_load_balancer CPU (if there is one) otherwise fallback to any idle
  3103. * CPU (if there is one).
  3104. */
  3105. static void nohz_balancer_kick(int cpu)
  3106. {
  3107. int ilb_cpu;
  3108. nohz.next_balance++;
  3109. ilb_cpu = get_nohz_load_balancer();
  3110. if (ilb_cpu >= nr_cpu_ids) {
  3111. ilb_cpu = cpumask_first(nohz.idle_cpus_mask);
  3112. if (ilb_cpu >= nr_cpu_ids)
  3113. return;
  3114. }
  3115. if (!cpu_rq(ilb_cpu)->nohz_balance_kick) {
  3116. struct call_single_data *cp;
  3117. cpu_rq(ilb_cpu)->nohz_balance_kick = 1;
  3118. cp = &per_cpu(remote_sched_softirq_cb, cpu);
  3119. __smp_call_function_single(ilb_cpu, cp, 0);
  3120. }
  3121. return;
  3122. }
  3123. /*
  3124. * This routine will try to nominate the ilb (idle load balancing)
  3125. * owner among the cpus whose ticks are stopped. ilb owner will do the idle
  3126. * load balancing on behalf of all those cpus.
  3127. *
  3128. * When the ilb owner becomes busy, we will not have new ilb owner until some
  3129. * idle CPU wakes up and goes back to idle or some busy CPU tries to kick
  3130. * idle load balancing by kicking one of the idle CPUs.
  3131. *
  3132. * Ticks are stopped for the ilb owner as well, with busy CPU kicking this
  3133. * ilb owner CPU in future (when there is a need for idle load balancing on
  3134. * behalf of all idle CPUs).
  3135. */
  3136. void select_nohz_load_balancer(int stop_tick)
  3137. {
  3138. int cpu = smp_processor_id();
  3139. if (stop_tick) {
  3140. if (!cpu_active(cpu)) {
  3141. if (atomic_read(&nohz.load_balancer) != cpu)
  3142. return;
  3143. /*
  3144. * If we are going offline and still the leader,
  3145. * give up!
  3146. */
  3147. if (atomic_cmpxchg(&nohz.load_balancer, cpu,
  3148. nr_cpu_ids) != cpu)
  3149. BUG();
  3150. return;
  3151. }
  3152. cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
  3153. if (atomic_read(&nohz.first_pick_cpu) == cpu)
  3154. atomic_cmpxchg(&nohz.first_pick_cpu, cpu, nr_cpu_ids);
  3155. if (atomic_read(&nohz.second_pick_cpu) == cpu)
  3156. atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
  3157. if (atomic_read(&nohz.load_balancer) >= nr_cpu_ids) {
  3158. int new_ilb;
  3159. /* make me the ilb owner */
  3160. if (atomic_cmpxchg(&nohz.load_balancer, nr_cpu_ids,
  3161. cpu) != nr_cpu_ids)
  3162. return;
  3163. /*
  3164. * Check to see if there is a more power-efficient
  3165. * ilb.
  3166. */
  3167. new_ilb = find_new_ilb(cpu);
  3168. if (new_ilb < nr_cpu_ids && new_ilb != cpu) {
  3169. atomic_set(&nohz.load_balancer, nr_cpu_ids);
  3170. resched_cpu(new_ilb);
  3171. return;
  3172. }
  3173. return;
  3174. }
  3175. } else {
  3176. if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
  3177. return;
  3178. cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
  3179. if (atomic_read(&nohz.load_balancer) == cpu)
  3180. if (atomic_cmpxchg(&nohz.load_balancer, cpu,
  3181. nr_cpu_ids) != cpu)
  3182. BUG();
  3183. }
  3184. return;
  3185. }
  3186. #endif
  3187. static DEFINE_SPINLOCK(balancing);
  3188. /*
  3189. * It checks each scheduling domain to see if it is due to be balanced,
  3190. * and initiates a balancing operation if so.
  3191. *
  3192. * Balancing parameters are set up in arch_init_sched_domains.
  3193. */
  3194. static void rebalance_domains(int cpu, enum cpu_idle_type idle)
  3195. {
  3196. int balance = 1;
  3197. struct rq *rq = cpu_rq(cpu);
  3198. unsigned long interval;
  3199. struct sched_domain *sd;
  3200. /* Earliest time when we have to do rebalance again */
  3201. unsigned long next_balance = jiffies + 60*HZ;
  3202. int update_next_balance = 0;
  3203. int need_serialize;
  3204. update_shares(cpu);
  3205. for_each_domain(cpu, sd) {
  3206. if (!(sd->flags & SD_LOAD_BALANCE))
  3207. continue;
  3208. interval = sd->balance_interval;
  3209. if (idle != CPU_IDLE)
  3210. interval *= sd->busy_factor;
  3211. /* scale ms to jiffies */
  3212. interval = msecs_to_jiffies(interval);
  3213. if (unlikely(!interval))
  3214. interval = 1;
  3215. if (interval > HZ*NR_CPUS/10)
  3216. interval = HZ*NR_CPUS/10;
  3217. need_serialize = sd->flags & SD_SERIALIZE;
  3218. if (need_serialize) {
  3219. if (!spin_trylock(&balancing))
  3220. goto out;
  3221. }
  3222. if (time_after_eq(jiffies, sd->last_balance + interval)) {
  3223. if (load_balance(cpu, rq, sd, idle, &balance)) {
  3224. /*
  3225. * We've pulled tasks over so either we're no
  3226. * longer idle, or one of our SMT siblings is
  3227. * not idle.
  3228. */
  3229. idle = CPU_NOT_IDLE;
  3230. }
  3231. sd->last_balance = jiffies;
  3232. }
  3233. if (need_serialize)
  3234. spin_unlock(&balancing);
  3235. out:
  3236. if (time_after(next_balance, sd->last_balance + interval)) {
  3237. next_balance = sd->last_balance + interval;
  3238. update_next_balance = 1;
  3239. }
  3240. /*
  3241. * Stop the load balance at this level. There is another
  3242. * CPU in our sched group which is doing load balancing more
  3243. * actively.
  3244. */
  3245. if (!balance)
  3246. break;
  3247. }
  3248. /*
  3249. * next_balance will be updated only when there is a need.
  3250. * When the cpu is attached to null domain for ex, it will not be
  3251. * updated.
  3252. */
  3253. if (likely(update_next_balance))
  3254. rq->next_balance = next_balance;
  3255. }
  3256. #ifdef CONFIG_NO_HZ
  3257. /*
  3258. * In CONFIG_NO_HZ case, the idle balance kickee will do the
  3259. * rebalancing for all the cpus for whom scheduler ticks are stopped.
  3260. */
  3261. static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle)
  3262. {
  3263. struct rq *this_rq = cpu_rq(this_cpu);
  3264. struct rq *rq;
  3265. int balance_cpu;
  3266. if (idle != CPU_IDLE || !this_rq->nohz_balance_kick)
  3267. return;
  3268. for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
  3269. if (balance_cpu == this_cpu)
  3270. continue;
  3271. /*
  3272. * If this cpu gets work to do, stop the load balancing
  3273. * work being done for other cpus. Next load
  3274. * balancing owner will pick it up.
  3275. */
  3276. if (need_resched()) {
  3277. this_rq->nohz_balance_kick = 0;
  3278. break;
  3279. }
  3280. raw_spin_lock_irq(&this_rq->lock);
  3281. update_rq_clock(this_rq);
  3282. update_cpu_load(this_rq);
  3283. raw_spin_unlock_irq(&this_rq->lock);
  3284. rebalance_domains(balance_cpu, CPU_IDLE);
  3285. rq = cpu_rq(balance_cpu);
  3286. if (time_after(this_rq->next_balance, rq->next_balance))
  3287. this_rq->next_balance = rq->next_balance;
  3288. }
  3289. nohz.next_balance = this_rq->next_balance;
  3290. this_rq->nohz_balance_kick = 0;
  3291. }
  3292. /*
  3293. * Current heuristic for kicking the idle load balancer
  3294. * - first_pick_cpu is the one of the busy CPUs. It will kick
  3295. * idle load balancer when it has more than one process active. This
  3296. * eliminates the need for idle load balancing altogether when we have
  3297. * only one running process in the system (common case).
  3298. * - If there are more than one busy CPU, idle load balancer may have
  3299. * to run for active_load_balance to happen (i.e., two busy CPUs are
  3300. * SMT or core siblings and can run better if they move to different
  3301. * physical CPUs). So, second_pick_cpu is the second of the busy CPUs
  3302. * which will kick idle load balancer as soon as it has any load.
  3303. */
  3304. static inline int nohz_kick_needed(struct rq *rq, int cpu)
  3305. {
  3306. unsigned long now = jiffies;
  3307. int ret;
  3308. int first_pick_cpu, second_pick_cpu;
  3309. if (time_before(now, nohz.next_balance))
  3310. return 0;
  3311. if (rq->idle_at_tick)
  3312. return 0;
  3313. first_pick_cpu = atomic_read(&nohz.first_pick_cpu);
  3314. second_pick_cpu = atomic_read(&nohz.second_pick_cpu);
  3315. if (first_pick_cpu < nr_cpu_ids && first_pick_cpu != cpu &&
  3316. second_pick_cpu < nr_cpu_ids && second_pick_cpu != cpu)
  3317. return 0;
  3318. ret = atomic_cmpxchg(&nohz.first_pick_cpu, nr_cpu_ids, cpu);
  3319. if (ret == nr_cpu_ids || ret == cpu) {
  3320. atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
  3321. if (rq->nr_running > 1)
  3322. return 1;
  3323. } else {
  3324. ret = atomic_cmpxchg(&nohz.second_pick_cpu, nr_cpu_ids, cpu);
  3325. if (ret == nr_cpu_ids || ret == cpu) {
  3326. if (rq->nr_running)
  3327. return 1;
  3328. }
  3329. }
  3330. return 0;
  3331. }
  3332. #else
  3333. static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle) { }
  3334. #endif
  3335. /*
  3336. * run_rebalance_domains is triggered when needed from the scheduler tick.
  3337. * Also triggered for nohz idle balancing (with nohz_balancing_kick set).
  3338. */
  3339. static void run_rebalance_domains(struct softirq_action *h)
  3340. {
  3341. int this_cpu = smp_processor_id();
  3342. struct rq *this_rq = cpu_rq(this_cpu);
  3343. enum cpu_idle_type idle = this_rq->idle_at_tick ?
  3344. CPU_IDLE : CPU_NOT_IDLE;
  3345. rebalance_domains(this_cpu, idle);
  3346. /*
  3347. * If this cpu has a pending nohz_balance_kick, then do the
  3348. * balancing on behalf of the other idle cpus whose ticks are
  3349. * stopped.
  3350. */
  3351. nohz_idle_balance(this_cpu, idle);
  3352. }
  3353. static inline int on_null_domain(int cpu)
  3354. {
  3355. return !rcu_dereference_sched(cpu_rq(cpu)->sd);
  3356. }
  3357. /*
  3358. * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
  3359. */
  3360. static inline void trigger_load_balance(struct rq *rq, int cpu)
  3361. {
  3362. /* Don't need to rebalance while attached to NULL domain */
  3363. if (time_after_eq(jiffies, rq->next_balance) &&
  3364. likely(!on_null_domain(cpu)))
  3365. raise_softirq(SCHED_SOFTIRQ);
  3366. #ifdef CONFIG_NO_HZ
  3367. else if (nohz_kick_needed(rq, cpu) && likely(!on_null_domain(cpu)))
  3368. nohz_balancer_kick(cpu);
  3369. #endif
  3370. }
  3371. static void rq_online_fair(struct rq *rq)
  3372. {
  3373. update_sysctl();
  3374. }
  3375. static void rq_offline_fair(struct rq *rq)
  3376. {
  3377. update_sysctl();
  3378. }
  3379. #else /* CONFIG_SMP */
  3380. /*
  3381. * on UP we do not need to balance between CPUs:
  3382. */
  3383. static inline void idle_balance(int cpu, struct rq *rq)
  3384. {
  3385. }
  3386. #endif /* CONFIG_SMP */
  3387. /*
  3388. * scheduler tick hitting a task of our scheduling class:
  3389. */
  3390. static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
  3391. {
  3392. struct cfs_rq *cfs_rq;
  3393. struct sched_entity *se = &curr->se;
  3394. for_each_sched_entity(se) {
  3395. cfs_rq = cfs_rq_of(se);
  3396. entity_tick(cfs_rq, se, queued);
  3397. }
  3398. }
  3399. /*
  3400. * called on fork with the child task as argument from the parent's context
  3401. * - child not yet on the tasklist
  3402. * - preemption disabled
  3403. */
  3404. static void task_fork_fair(struct task_struct *p)
  3405. {
  3406. struct cfs_rq *cfs_rq = task_cfs_rq(current);
  3407. struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
  3408. int this_cpu = smp_processor_id();
  3409. struct rq *rq = this_rq();
  3410. unsigned long flags;
  3411. raw_spin_lock_irqsave(&rq->lock, flags);
  3412. update_rq_clock(rq);
  3413. if (unlikely(task_cpu(p) != this_cpu)) {
  3414. rcu_read_lock();
  3415. __set_task_cpu(p, this_cpu);
  3416. rcu_read_unlock();
  3417. }
  3418. update_curr(cfs_rq);
  3419. if (curr)
  3420. se->vruntime = curr->vruntime;
  3421. place_entity(cfs_rq, se, 1);
  3422. if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
  3423. /*
  3424. * Upon rescheduling, sched_class::put_prev_task() will place
  3425. * 'current' within the tree based on its new key value.
  3426. */
  3427. swap(curr->vruntime, se->vruntime);
  3428. resched_task(rq->curr);
  3429. }
  3430. se->vruntime -= cfs_rq->min_vruntime;
  3431. raw_spin_unlock_irqrestore(&rq->lock, flags);
  3432. }
  3433. /*
  3434. * Priority of the task has changed. Check to see if we preempt
  3435. * the current task.
  3436. */
  3437. static void prio_changed_fair(struct rq *rq, struct task_struct *p,
  3438. int oldprio, int running)
  3439. {
  3440. /*
  3441. * Reschedule if we are currently running on this runqueue and
  3442. * our priority decreased, or if we are not currently running on
  3443. * this runqueue and our priority is higher than the current's
  3444. */
  3445. if (running) {
  3446. if (p->prio > oldprio)
  3447. resched_task(rq->curr);
  3448. } else
  3449. check_preempt_curr(rq, p, 0);
  3450. }
  3451. /*
  3452. * We switched to the sched_fair class.
  3453. */
  3454. static void switched_to_fair(struct rq *rq, struct task_struct *p,
  3455. int running)
  3456. {
  3457. /*
  3458. * We were most likely switched from sched_rt, so
  3459. * kick off the schedule if running, otherwise just see
  3460. * if we can still preempt the current task.
  3461. */
  3462. if (running)
  3463. resched_task(rq->curr);
  3464. else
  3465. check_preempt_curr(rq, p, 0);
  3466. }
  3467. /* Account for a task changing its policy or group.
  3468. *
  3469. * This routine is mostly called to set cfs_rq->curr field when a task
  3470. * migrates between groups/classes.
  3471. */
  3472. static void set_curr_task_fair(struct rq *rq)
  3473. {
  3474. struct sched_entity *se = &rq->curr->se;
  3475. for_each_sched_entity(se)
  3476. set_next_entity(cfs_rq_of(se), se);
  3477. }
  3478. #ifdef CONFIG_FAIR_GROUP_SCHED
  3479. static void task_move_group_fair(struct task_struct *p, int on_rq)
  3480. {
  3481. /*
  3482. * If the task was not on the rq at the time of this cgroup movement
  3483. * it must have been asleep, sleeping tasks keep their ->vruntime
  3484. * absolute on their old rq until wakeup (needed for the fair sleeper
  3485. * bonus in place_entity()).
  3486. *
  3487. * If it was on the rq, we've just 'preempted' it, which does convert
  3488. * ->vruntime to a relative base.
  3489. *
  3490. * Make sure both cases convert their relative position when migrating
  3491. * to another cgroup's rq. This does somewhat interfere with the
  3492. * fair sleeper stuff for the first placement, but who cares.
  3493. */
  3494. if (!on_rq)
  3495. p->se.vruntime -= cfs_rq_of(&p->se)->min_vruntime;
  3496. set_task_rq(p, task_cpu(p));
  3497. if (!on_rq)
  3498. p->se.vruntime += cfs_rq_of(&p->se)->min_vruntime;
  3499. }
  3500. #endif
  3501. static unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task)
  3502. {
  3503. struct sched_entity *se = &task->se;
  3504. unsigned int rr_interval = 0;
  3505. /*
  3506. * Time slice is 0 for SCHED_OTHER tasks that are on an otherwise
  3507. * idle runqueue:
  3508. */
  3509. if (rq->cfs.load.weight)
  3510. rr_interval = NS_TO_JIFFIES(sched_slice(&rq->cfs, se));
  3511. return rr_interval;
  3512. }
  3513. /*
  3514. * All the scheduling class methods:
  3515. */
  3516. static const struct sched_class fair_sched_class = {
  3517. .next = &idle_sched_class,
  3518. .enqueue_task = enqueue_task_fair,
  3519. .dequeue_task = dequeue_task_fair,
  3520. .yield_task = yield_task_fair,
  3521. .check_preempt_curr = check_preempt_wakeup,
  3522. .pick_next_task = pick_next_task_fair,
  3523. .put_prev_task = put_prev_task_fair,
  3524. #ifdef CONFIG_SMP
  3525. .select_task_rq = select_task_rq_fair,
  3526. .rq_online = rq_online_fair,
  3527. .rq_offline = rq_offline_fair,
  3528. .task_waking = task_waking_fair,
  3529. #endif
  3530. .set_curr_task = set_curr_task_fair,
  3531. .task_tick = task_tick_fair,
  3532. .task_fork = task_fork_fair,
  3533. .prio_changed = prio_changed_fair,
  3534. .switched_to = switched_to_fair,
  3535. .get_rr_interval = get_rr_interval_fair,
  3536. #ifdef CONFIG_FAIR_GROUP_SCHED
  3537. .task_move_group = task_move_group_fair,
  3538. #endif
  3539. };
  3540. #ifdef CONFIG_SCHED_DEBUG
  3541. static void print_cfs_stats(struct seq_file *m, int cpu)
  3542. {
  3543. struct cfs_rq *cfs_rq;
  3544. rcu_read_lock();
  3545. for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
  3546. print_cfs_rq(m, cpu, cfs_rq);
  3547. rcu_read_unlock();
  3548. }
  3549. #endif