sched.c 160 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572457345744575457645774578457945804581458245834584458545864587458845894590459145924593459445954596459745984599460046014602460346044605460646074608460946104611461246134614461546164617461846194620462146224623462446254626462746284629463046314632463346344635463646374638463946404641464246434644464546464647464846494650465146524653465446554656465746584659466046614662466346644665466646674668466946704671467246734674467546764677467846794680468146824683468446854686468746884689469046914692469346944695469646974698469947004701470247034704470547064707470847094710471147124713471447154716471747184719472047214722472347244725472647274728472947304731473247334734473547364737473847394740474147424743474447454746474747484749475047514752475347544755475647574758475947604761476247634764476547664767476847694770477147724773477447754776477747784779478047814782478347844785478647874788478947904791479247934794479547964797479847994800480148024803480448054806480748084809481048114812481348144815481648174818481948204821482248234824482548264827482848294830483148324833483448354836483748384839484048414842484348444845484648474848484948504851485248534854485548564857485848594860486148624863486448654866486748684869487048714872487348744875487648774878487948804881488248834884488548864887488848894890489148924893489448954896489748984899490049014902490349044905490649074908490949104911491249134914491549164917491849194920492149224923492449254926492749284929493049314932493349344935493649374938493949404941494249434944494549464947494849494950495149524953495449554956495749584959496049614962496349644965496649674968496949704971497249734974497549764977497849794980498149824983498449854986498749884989499049914992499349944995499649974998499950005001500250035004500550065007500850095010501150125013501450155016501750185019502050215022502350245025502650275028502950305031503250335034503550365037503850395040504150425043504450455046504750485049505050515052505350545055505650575058505950605061506250635064506550665067506850695070507150725073507450755076507750785079508050815082508350845085508650875088508950905091509250935094509550965097509850995100510151025103510451055106510751085109511051115112511351145115511651175118511951205121512251235124512551265127512851295130513151325133513451355136513751385139514051415142514351445145514651475148514951505151515251535154515551565157515851595160516151625163516451655166516751685169517051715172517351745175517651775178517951805181518251835184518551865187518851895190519151925193519451955196519751985199520052015202520352045205520652075208520952105211521252135214521552165217521852195220522152225223522452255226522752285229523052315232523352345235523652375238523952405241524252435244524552465247524852495250525152525253525452555256525752585259526052615262526352645265526652675268526952705271527252735274527552765277527852795280528152825283528452855286528752885289529052915292529352945295529652975298529953005301530253035304530553065307530853095310531153125313531453155316531753185319532053215322532353245325532653275328532953305331533253335334533553365337533853395340534153425343534453455346534753485349535053515352535353545355535653575358535953605361536253635364536553665367536853695370537153725373537453755376537753785379538053815382538353845385538653875388538953905391539253935394539553965397539853995400540154025403540454055406540754085409541054115412541354145415541654175418541954205421542254235424542554265427542854295430543154325433543454355436543754385439544054415442544354445445544654475448544954505451545254535454545554565457545854595460546154625463546454655466546754685469547054715472547354745475547654775478547954805481548254835484548554865487548854895490549154925493549454955496549754985499550055015502550355045505550655075508550955105511551255135514551555165517551855195520552155225523552455255526552755285529553055315532553355345535553655375538553955405541554255435544554555465547554855495550555155525553555455555556555755585559556055615562556355645565556655675568556955705571557255735574557555765577557855795580558155825583558455855586558755885589559055915592559355945595559655975598559956005601560256035604560556065607560856095610561156125613561456155616561756185619562056215622562356245625562656275628562956305631563256335634563556365637563856395640564156425643564456455646564756485649565056515652565356545655565656575658565956605661566256635664566556665667566856695670567156725673567456755676567756785679568056815682568356845685568656875688568956905691569256935694569556965697569856995700570157025703570457055706570757085709571057115712571357145715571657175718571957205721572257235724572557265727572857295730573157325733573457355736573757385739574057415742574357445745574657475748574957505751575257535754575557565757575857595760576157625763576457655766576757685769577057715772577357745775577657775778577957805781578257835784578557865787578857895790579157925793579457955796579757985799580058015802580358045805580658075808580958105811581258135814581558165817581858195820582158225823582458255826582758285829583058315832583358345835583658375838583958405841584258435844584558465847584858495850585158525853585458555856585758585859586058615862586358645865586658675868586958705871587258735874587558765877587858795880588158825883588458855886588758885889589058915892589358945895589658975898589959005901590259035904590559065907590859095910591159125913591459155916591759185919592059215922592359245925592659275928592959305931593259335934593559365937593859395940594159425943594459455946594759485949595059515952595359545955595659575958595959605961596259635964596559665967596859695970597159725973597459755976597759785979598059815982598359845985598659875988598959905991599259935994599559965997599859996000600160026003600460056006600760086009601060116012601360146015601660176018601960206021602260236024602560266027602860296030603160326033603460356036603760386039604060416042604360446045604660476048604960506051605260536054605560566057605860596060606160626063606460656066606760686069607060716072607360746075607660776078607960806081608260836084608560866087608860896090609160926093609460956096609760986099610061016102610361046105610661076108610961106111611261136114611561166117611861196120612161226123612461256126612761286129613061316132613361346135613661376138613961406141614261436144614561466147614861496150615161526153615461556156615761586159616061616162616361646165616661676168616961706171617261736174617561766177617861796180618161826183618461856186618761886189619061916192619361946195619661976198619962006201620262036204620562066207620862096210621162126213621462156216621762186219622062216222622362246225622662276228622962306231623262336234623562366237623862396240624162426243624462456246624762486249625062516252625362546255625662576258625962606261626262636264626562666267626862696270627162726273627462756276627762786279628062816282628362846285628662876288628962906291629262936294629562966297629862996300630163026303630463056306630763086309631063116312631363146315631663176318631963206321632263236324632563266327632863296330633163326333633463356336633763386339634063416342634363446345634663476348634963506351635263536354635563566357635863596360636163626363636463656366636763686369637063716372637363746375637663776378637963806381638263836384638563866387638863896390639163926393639463956396639763986399640064016402640364046405640664076408640964106411641264136414641564166417641864196420642164226423642464256426642764286429643064316432643364346435643664376438643964406441644264436444644564466447644864496450645164526453645464556456645764586459646064616462646364646465646664676468646964706471647264736474647564766477
  1. /*
  2. * kernel/sched.c
  3. *
  4. * Kernel scheduler and related syscalls
  5. *
  6. * Copyright (C) 1991-2002 Linus Torvalds
  7. *
  8. * 1996-12-23 Modified by Dave Grothe to fix bugs in semaphores and
  9. * make semaphores SMP safe
  10. * 1998-11-19 Implemented schedule_timeout() and related stuff
  11. * by Andrea Arcangeli
  12. * 2002-01-04 New ultra-scalable O(1) scheduler by Ingo Molnar:
  13. * hybrid priority-list and round-robin design with
  14. * an array-switch method of distributing timeslices
  15. * and per-CPU runqueues. Cleanups and useful suggestions
  16. * by Davide Libenzi, preemptible kernel bits by Robert Love.
  17. * 2003-09-03 Interactivity tuning by Con Kolivas.
  18. * 2004-04-02 Scheduler domains code by Nick Piggin
  19. * 2007-04-15 Work begun on replacing all interactivity tuning with a
  20. * fair scheduling design by Con Kolivas.
  21. * 2007-05-05 Load balancing (smp-nice) and other improvements
  22. * by Peter Williams
  23. * 2007-05-06 Interactivity improvements to CFS by Mike Galbraith
  24. * 2007-07-01 Group scheduling enhancements by Srivatsa Vaddagiri
  25. */
  26. #include <linux/mm.h>
  27. #include <linux/module.h>
  28. #include <linux/nmi.h>
  29. #include <linux/init.h>
  30. #include <linux/uaccess.h>
  31. #include <linux/highmem.h>
  32. #include <linux/smp_lock.h>
  33. #include <asm/mmu_context.h>
  34. #include <linux/interrupt.h>
  35. #include <linux/capability.h>
  36. #include <linux/completion.h>
  37. #include <linux/kernel_stat.h>
  38. #include <linux/debug_locks.h>
  39. #include <linux/security.h>
  40. #include <linux/notifier.h>
  41. #include <linux/profile.h>
  42. #include <linux/freezer.h>
  43. #include <linux/vmalloc.h>
  44. #include <linux/blkdev.h>
  45. #include <linux/delay.h>
  46. #include <linux/smp.h>
  47. #include <linux/threads.h>
  48. #include <linux/timer.h>
  49. #include <linux/rcupdate.h>
  50. #include <linux/cpu.h>
  51. #include <linux/cpuset.h>
  52. #include <linux/percpu.h>
  53. #include <linux/kthread.h>
  54. #include <linux/seq_file.h>
  55. #include <linux/syscalls.h>
  56. #include <linux/times.h>
  57. #include <linux/tsacct_kern.h>
  58. #include <linux/kprobes.h>
  59. #include <linux/delayacct.h>
  60. #include <linux/reciprocal_div.h>
  61. #include <linux/unistd.h>
  62. #include <asm/tlb.h>
  63. /*
  64. * Scheduler clock - returns current time in nanosec units.
  65. * This is default implementation.
  66. * Architectures and sub-architectures can override this.
  67. */
  68. unsigned long long __attribute__((weak)) sched_clock(void)
  69. {
  70. return (unsigned long long)jiffies * (1000000000 / HZ);
  71. }
  72. /*
  73. * Convert user-nice values [ -20 ... 0 ... 19 ]
  74. * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
  75. * and back.
  76. */
  77. #define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)
  78. #define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20)
  79. #define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio)
  80. /*
  81. * 'User priority' is the nice value converted to something we
  82. * can work with better when scaling various scheduler parameters,
  83. * it's a [ 0 ... 39 ] range.
  84. */
  85. #define USER_PRIO(p) ((p)-MAX_RT_PRIO)
  86. #define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio)
  87. #define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))
  88. /*
  89. * Some helpers for converting nanosecond timing to jiffy resolution
  90. */
  91. #define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
  92. #define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))
  93. #define NICE_0_LOAD SCHED_LOAD_SCALE
  94. #define NICE_0_SHIFT SCHED_LOAD_SHIFT
  95. /*
  96. * These are the 'tuning knobs' of the scheduler:
  97. *
  98. * Minimum timeslice is 5 msecs (or 1 jiffy, whichever is larger),
  99. * default timeslice is 100 msecs, maximum timeslice is 800 msecs.
  100. * Timeslices get refilled after they expire.
  101. */
  102. #define MIN_TIMESLICE max(5 * HZ / 1000, 1)
  103. #define DEF_TIMESLICE (100 * HZ / 1000)
  104. #ifdef CONFIG_SMP
  105. /*
  106. * Divide a load by a sched group cpu_power : (load / sg->__cpu_power)
  107. * Since cpu_power is a 'constant', we can use a reciprocal divide.
  108. */
  109. static inline u32 sg_div_cpu_power(const struct sched_group *sg, u32 load)
  110. {
  111. return reciprocal_divide(load, sg->reciprocal_cpu_power);
  112. }
  113. /*
  114. * Each time a sched group cpu_power is changed,
  115. * we must compute its reciprocal value
  116. */
  117. static inline void sg_inc_cpu_power(struct sched_group *sg, u32 val)
  118. {
  119. sg->__cpu_power += val;
  120. sg->reciprocal_cpu_power = reciprocal_value(sg->__cpu_power);
  121. }
  122. #endif
  123. #define SCALE_PRIO(x, prio) \
  124. max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_TIMESLICE)
  125. /*
  126. * static_prio_timeslice() scales user-nice values [ -20 ... 0 ... 19 ]
  127. * to time slice values: [800ms ... 100ms ... 5ms]
  128. */
  129. static unsigned int static_prio_timeslice(int static_prio)
  130. {
  131. if (static_prio == NICE_TO_PRIO(19))
  132. return 1;
  133. if (static_prio < NICE_TO_PRIO(0))
  134. return SCALE_PRIO(DEF_TIMESLICE * 4, static_prio);
  135. else
  136. return SCALE_PRIO(DEF_TIMESLICE, static_prio);
  137. }
  138. static inline int rt_policy(int policy)
  139. {
  140. if (unlikely(policy == SCHED_FIFO) || unlikely(policy == SCHED_RR))
  141. return 1;
  142. return 0;
  143. }
  144. static inline int task_has_rt_policy(struct task_struct *p)
  145. {
  146. return rt_policy(p->policy);
  147. }
  148. /*
  149. * This is the priority-queue data structure of the RT scheduling class:
  150. */
  151. struct rt_prio_array {
  152. DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
  153. struct list_head queue[MAX_RT_PRIO];
  154. };
  155. struct load_stat {
  156. struct load_weight load;
  157. u64 load_update_start, load_update_last;
  158. unsigned long delta_fair, delta_exec, delta_stat;
  159. };
  160. /* CFS-related fields in a runqueue */
  161. struct cfs_rq {
  162. struct load_weight load;
  163. unsigned long nr_running;
  164. s64 fair_clock;
  165. u64 exec_clock;
  166. s64 wait_runtime;
  167. u64 sleeper_bonus;
  168. unsigned long wait_runtime_overruns, wait_runtime_underruns;
  169. struct rb_root tasks_timeline;
  170. struct rb_node *rb_leftmost;
  171. struct rb_node *rb_load_balance_curr;
  172. #ifdef CONFIG_FAIR_GROUP_SCHED
  173. /* 'curr' points to currently running entity on this cfs_rq.
  174. * It is set to NULL otherwise (i.e when none are currently running).
  175. */
  176. struct sched_entity *curr;
  177. struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */
  178. /* leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
  179. * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
  180. * (like users, containers etc.)
  181. *
  182. * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
  183. * list is used during load balance.
  184. */
  185. struct list_head leaf_cfs_rq_list; /* Better name : task_cfs_rq_list? */
  186. #endif
  187. };
  188. /* Real-Time classes' related field in a runqueue: */
  189. struct rt_rq {
  190. struct rt_prio_array active;
  191. int rt_load_balance_idx;
  192. struct list_head *rt_load_balance_head, *rt_load_balance_curr;
  193. };
  194. /*
  195. * This is the main, per-CPU runqueue data structure.
  196. *
  197. * Locking rule: those places that want to lock multiple runqueues
  198. * (such as the load balancing or the thread migration code), lock
  199. * acquire operations must be ordered by ascending &runqueue.
  200. */
  201. struct rq {
  202. spinlock_t lock; /* runqueue lock */
  203. /*
  204. * nr_running and cpu_load should be in the same cacheline because
  205. * remote CPUs use both these fields when doing load calculation.
  206. */
  207. unsigned long nr_running;
  208. #define CPU_LOAD_IDX_MAX 5
  209. unsigned long cpu_load[CPU_LOAD_IDX_MAX];
  210. unsigned char idle_at_tick;
  211. #ifdef CONFIG_NO_HZ
  212. unsigned char in_nohz_recently;
  213. #endif
  214. struct load_stat ls; /* capture load from *all* tasks on this cpu */
  215. unsigned long nr_load_updates;
  216. u64 nr_switches;
  217. struct cfs_rq cfs;
  218. #ifdef CONFIG_FAIR_GROUP_SCHED
  219. struct list_head leaf_cfs_rq_list; /* list of leaf cfs_rq on this cpu */
  220. #endif
  221. struct rt_rq rt;
  222. /*
  223. * This is part of a global counter where only the total sum
  224. * over all CPUs matters. A task can increase this counter on
  225. * one CPU and if it got migrated afterwards it may decrease
  226. * it on another CPU. Always updated under the runqueue lock:
  227. */
  228. unsigned long nr_uninterruptible;
  229. struct task_struct *curr, *idle;
  230. unsigned long next_balance;
  231. struct mm_struct *prev_mm;
  232. u64 clock, prev_clock_raw;
  233. s64 clock_max_delta;
  234. unsigned int clock_warps, clock_overflows;
  235. unsigned int clock_unstable_events;
  236. struct sched_class *load_balance_class;
  237. atomic_t nr_iowait;
  238. #ifdef CONFIG_SMP
  239. struct sched_domain *sd;
  240. /* For active balancing */
  241. int active_balance;
  242. int push_cpu;
  243. int cpu; /* cpu of this runqueue */
  244. struct task_struct *migration_thread;
  245. struct list_head migration_queue;
  246. #endif
  247. #ifdef CONFIG_SCHEDSTATS
  248. /* latency stats */
  249. struct sched_info rq_sched_info;
  250. /* sys_sched_yield() stats */
  251. unsigned long yld_exp_empty;
  252. unsigned long yld_act_empty;
  253. unsigned long yld_both_empty;
  254. unsigned long yld_cnt;
  255. /* schedule() stats */
  256. unsigned long sched_switch;
  257. unsigned long sched_cnt;
  258. unsigned long sched_goidle;
  259. /* try_to_wake_up() stats */
  260. unsigned long ttwu_cnt;
  261. unsigned long ttwu_local;
  262. #endif
  263. struct lock_class_key rq_lock_key;
  264. };
  265. static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
  266. static DEFINE_MUTEX(sched_hotcpu_mutex);
  267. static inline void check_preempt_curr(struct rq *rq, struct task_struct *p)
  268. {
  269. rq->curr->sched_class->check_preempt_curr(rq, p);
  270. }
  271. static inline int cpu_of(struct rq *rq)
  272. {
  273. #ifdef CONFIG_SMP
  274. return rq->cpu;
  275. #else
  276. return 0;
  277. #endif
  278. }
  279. /*
  280. * Per-runqueue clock, as finegrained as the platform can give us:
  281. */
  282. static unsigned long long __rq_clock(struct rq *rq)
  283. {
  284. u64 prev_raw = rq->prev_clock_raw;
  285. u64 now = sched_clock();
  286. s64 delta = now - prev_raw;
  287. u64 clock = rq->clock;
  288. /*
  289. * Protect against sched_clock() occasionally going backwards:
  290. */
  291. if (unlikely(delta < 0)) {
  292. clock++;
  293. rq->clock_warps++;
  294. } else {
  295. /*
  296. * Catch too large forward jumps too:
  297. */
  298. if (unlikely(delta > 2*TICK_NSEC)) {
  299. clock++;
  300. rq->clock_overflows++;
  301. } else {
  302. if (unlikely(delta > rq->clock_max_delta))
  303. rq->clock_max_delta = delta;
  304. clock += delta;
  305. }
  306. }
  307. rq->prev_clock_raw = now;
  308. rq->clock = clock;
  309. return clock;
  310. }
  311. static inline unsigned long long rq_clock(struct rq *rq)
  312. {
  313. int this_cpu = smp_processor_id();
  314. if (this_cpu == cpu_of(rq))
  315. return __rq_clock(rq);
  316. return rq->clock;
  317. }
  318. /*
  319. * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
  320. * See detach_destroy_domains: synchronize_sched for details.
  321. *
  322. * The domain tree of any CPU may only be accessed from within
  323. * preempt-disabled sections.
  324. */
  325. #define for_each_domain(cpu, __sd) \
  326. for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)
  327. #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
  328. #define this_rq() (&__get_cpu_var(runqueues))
  329. #define task_rq(p) cpu_rq(task_cpu(p))
  330. #define cpu_curr(cpu) (cpu_rq(cpu)->curr)
  331. #ifdef CONFIG_FAIR_GROUP_SCHED
  332. /* Change a task's ->cfs_rq if it moves across CPUs */
  333. static inline void set_task_cfs_rq(struct task_struct *p)
  334. {
  335. p->se.cfs_rq = &task_rq(p)->cfs;
  336. }
  337. #else
  338. static inline void set_task_cfs_rq(struct task_struct *p)
  339. {
  340. }
  341. #endif
  342. #ifndef prepare_arch_switch
  343. # define prepare_arch_switch(next) do { } while (0)
  344. #endif
  345. #ifndef finish_arch_switch
  346. # define finish_arch_switch(prev) do { } while (0)
  347. #endif
  348. #ifndef __ARCH_WANT_UNLOCKED_CTXSW
  349. static inline int task_running(struct rq *rq, struct task_struct *p)
  350. {
  351. return rq->curr == p;
  352. }
  353. static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
  354. {
  355. }
  356. static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
  357. {
  358. #ifdef CONFIG_DEBUG_SPINLOCK
  359. /* this is a valid case when another task releases the spinlock */
  360. rq->lock.owner = current;
  361. #endif
  362. /*
  363. * If we are tracking spinlock dependencies then we have to
  364. * fix up the runqueue lock - which gets 'carried over' from
  365. * prev into current:
  366. */
  367. spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_);
  368. spin_unlock_irq(&rq->lock);
  369. }
  370. #else /* __ARCH_WANT_UNLOCKED_CTXSW */
  371. static inline int task_running(struct rq *rq, struct task_struct *p)
  372. {
  373. #ifdef CONFIG_SMP
  374. return p->oncpu;
  375. #else
  376. return rq->curr == p;
  377. #endif
  378. }
  379. static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
  380. {
  381. #ifdef CONFIG_SMP
  382. /*
  383. * We can optimise this out completely for !SMP, because the
  384. * SMP rebalancing from interrupt is the only thing that cares
  385. * here.
  386. */
  387. next->oncpu = 1;
  388. #endif
  389. #ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
  390. spin_unlock_irq(&rq->lock);
  391. #else
  392. spin_unlock(&rq->lock);
  393. #endif
  394. }
  395. static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
  396. {
  397. #ifdef CONFIG_SMP
  398. /*
  399. * After ->oncpu is cleared, the task can be moved to a different CPU.
  400. * We must ensure this doesn't happen until the switch is completely
  401. * finished.
  402. */
  403. smp_wmb();
  404. prev->oncpu = 0;
  405. #endif
  406. #ifndef __ARCH_WANT_INTERRUPTS_ON_CTXSW
  407. local_irq_enable();
  408. #endif
  409. }
  410. #endif /* __ARCH_WANT_UNLOCKED_CTXSW */
  411. /*
  412. * __task_rq_lock - lock the runqueue a given task resides on.
  413. * Must be called interrupts disabled.
  414. */
  415. static inline struct rq *__task_rq_lock(struct task_struct *p)
  416. __acquires(rq->lock)
  417. {
  418. struct rq *rq;
  419. repeat_lock_task:
  420. rq = task_rq(p);
  421. spin_lock(&rq->lock);
  422. if (unlikely(rq != task_rq(p))) {
  423. spin_unlock(&rq->lock);
  424. goto repeat_lock_task;
  425. }
  426. return rq;
  427. }
  428. /*
  429. * task_rq_lock - lock the runqueue a given task resides on and disable
  430. * interrupts. Note the ordering: we can safely lookup the task_rq without
  431. * explicitly disabling preemption.
  432. */
  433. static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
  434. __acquires(rq->lock)
  435. {
  436. struct rq *rq;
  437. repeat_lock_task:
  438. local_irq_save(*flags);
  439. rq = task_rq(p);
  440. spin_lock(&rq->lock);
  441. if (unlikely(rq != task_rq(p))) {
  442. spin_unlock_irqrestore(&rq->lock, *flags);
  443. goto repeat_lock_task;
  444. }
  445. return rq;
  446. }
  447. static inline void __task_rq_unlock(struct rq *rq)
  448. __releases(rq->lock)
  449. {
  450. spin_unlock(&rq->lock);
  451. }
  452. static inline void task_rq_unlock(struct rq *rq, unsigned long *flags)
  453. __releases(rq->lock)
  454. {
  455. spin_unlock_irqrestore(&rq->lock, *flags);
  456. }
  457. /*
  458. * this_rq_lock - lock this runqueue and disable interrupts.
  459. */
  460. static inline struct rq *this_rq_lock(void)
  461. __acquires(rq->lock)
  462. {
  463. struct rq *rq;
  464. local_irq_disable();
  465. rq = this_rq();
  466. spin_lock(&rq->lock);
  467. return rq;
  468. }
  469. /*
  470. * CPU frequency is/was unstable - start new by setting prev_clock_raw:
  471. */
  472. void sched_clock_unstable_event(void)
  473. {
  474. unsigned long flags;
  475. struct rq *rq;
  476. rq = task_rq_lock(current, &flags);
  477. rq->prev_clock_raw = sched_clock();
  478. rq->clock_unstable_events++;
  479. task_rq_unlock(rq, &flags);
  480. }
  481. /*
  482. * resched_task - mark a task 'to be rescheduled now'.
  483. *
  484. * On UP this means the setting of the need_resched flag, on SMP it
  485. * might also involve a cross-CPU call to trigger the scheduler on
  486. * the target CPU.
  487. */
  488. #ifdef CONFIG_SMP
  489. #ifndef tsk_is_polling
  490. #define tsk_is_polling(t) test_tsk_thread_flag(t, TIF_POLLING_NRFLAG)
  491. #endif
  492. static void resched_task(struct task_struct *p)
  493. {
  494. int cpu;
  495. assert_spin_locked(&task_rq(p)->lock);
  496. if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
  497. return;
  498. set_tsk_thread_flag(p, TIF_NEED_RESCHED);
  499. cpu = task_cpu(p);
  500. if (cpu == smp_processor_id())
  501. return;
  502. /* NEED_RESCHED must be visible before we test polling */
  503. smp_mb();
  504. if (!tsk_is_polling(p))
  505. smp_send_reschedule(cpu);
  506. }
  507. static void resched_cpu(int cpu)
  508. {
  509. struct rq *rq = cpu_rq(cpu);
  510. unsigned long flags;
  511. if (!spin_trylock_irqsave(&rq->lock, flags))
  512. return;
  513. resched_task(cpu_curr(cpu));
  514. spin_unlock_irqrestore(&rq->lock, flags);
  515. }
  516. #else
  517. static inline void resched_task(struct task_struct *p)
  518. {
  519. assert_spin_locked(&task_rq(p)->lock);
  520. set_tsk_need_resched(p);
  521. }
  522. #endif
  523. static u64 div64_likely32(u64 divident, unsigned long divisor)
  524. {
  525. #if BITS_PER_LONG == 32
  526. if (likely(divident <= 0xffffffffULL))
  527. return (u32)divident / divisor;
  528. do_div(divident, divisor);
  529. return divident;
  530. #else
  531. return divident / divisor;
  532. #endif
  533. }
  534. #if BITS_PER_LONG == 32
  535. # define WMULT_CONST (~0UL)
  536. #else
  537. # define WMULT_CONST (1UL << 32)
  538. #endif
  539. #define WMULT_SHIFT 32
  540. static inline unsigned long
  541. calc_delta_mine(unsigned long delta_exec, unsigned long weight,
  542. struct load_weight *lw)
  543. {
  544. u64 tmp;
  545. if (unlikely(!lw->inv_weight))
  546. lw->inv_weight = WMULT_CONST / lw->weight;
  547. tmp = (u64)delta_exec * weight;
  548. /*
  549. * Check whether we'd overflow the 64-bit multiplication:
  550. */
  551. if (unlikely(tmp > WMULT_CONST)) {
  552. tmp = ((tmp >> WMULT_SHIFT/2) * lw->inv_weight)
  553. >> (WMULT_SHIFT/2);
  554. } else {
  555. tmp = (tmp * lw->inv_weight) >> WMULT_SHIFT;
  556. }
  557. return (unsigned long)min(tmp, (u64)sysctl_sched_runtime_limit);
  558. }
  559. static inline unsigned long
  560. calc_delta_fair(unsigned long delta_exec, struct load_weight *lw)
  561. {
  562. return calc_delta_mine(delta_exec, NICE_0_LOAD, lw);
  563. }
  564. static void update_load_add(struct load_weight *lw, unsigned long inc)
  565. {
  566. lw->weight += inc;
  567. lw->inv_weight = 0;
  568. }
  569. static void update_load_sub(struct load_weight *lw, unsigned long dec)
  570. {
  571. lw->weight -= dec;
  572. lw->inv_weight = 0;
  573. }
  574. static void __update_curr_load(struct rq *rq, struct load_stat *ls)
  575. {
  576. if (rq->curr != rq->idle && ls->load.weight) {
  577. ls->delta_exec += ls->delta_stat;
  578. ls->delta_fair += calc_delta_fair(ls->delta_stat, &ls->load);
  579. ls->delta_stat = 0;
  580. }
  581. }
  582. /*
  583. * Update delta_exec, delta_fair fields for rq.
  584. *
  585. * delta_fair clock advances at a rate inversely proportional to
  586. * total load (rq->ls.load.weight) on the runqueue, while
  587. * delta_exec advances at the same rate as wall-clock (provided
  588. * cpu is not idle).
  589. *
  590. * delta_exec / delta_fair is a measure of the (smoothened) load on this
  591. * runqueue over any given interval. This (smoothened) load is used
  592. * during load balance.
  593. *
  594. * This function is called /before/ updating rq->ls.load
  595. * and when switching tasks.
  596. */
  597. static void update_curr_load(struct rq *rq, u64 now)
  598. {
  599. struct load_stat *ls = &rq->ls;
  600. u64 start;
  601. start = ls->load_update_start;
  602. ls->load_update_start = now;
  603. ls->delta_stat += now - start;
  604. /*
  605. * Stagger updates to ls->delta_fair. Very frequent updates
  606. * can be expensive.
  607. */
  608. if (ls->delta_stat >= sysctl_sched_stat_granularity)
  609. __update_curr_load(rq, ls);
  610. }
  611. /*
  612. * To aid in avoiding the subversion of "niceness" due to uneven distribution
  613. * of tasks with abnormal "nice" values across CPUs the contribution that
  614. * each task makes to its run queue's load is weighted according to its
  615. * scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a
  616. * scaled version of the new time slice allocation that they receive on time
  617. * slice expiry etc.
  618. */
  619. /*
  620. * Assume: static_prio_timeslice(NICE_TO_PRIO(0)) == DEF_TIMESLICE
  621. * If static_prio_timeslice() is ever changed to break this assumption then
  622. * this code will need modification
  623. */
  624. #define TIME_SLICE_NICE_ZERO DEF_TIMESLICE
  625. #define load_weight(lp) \
  626. (((lp) * SCHED_LOAD_SCALE) / TIME_SLICE_NICE_ZERO)
  627. #define PRIO_TO_LOAD_WEIGHT(prio) \
  628. load_weight(static_prio_timeslice(prio))
  629. #define RTPRIO_TO_LOAD_WEIGHT(rp) \
  630. (PRIO_TO_LOAD_WEIGHT(MAX_RT_PRIO) + load_weight(rp))
  631. #define WEIGHT_IDLEPRIO 2
  632. #define WMULT_IDLEPRIO (1 << 31)
  633. /*
  634. * Nice levels are multiplicative, with a gentle 10% change for every
  635. * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
  636. * nice 1, it will get ~10% less CPU time than another CPU-bound task
  637. * that remained on nice 0.
  638. *
  639. * The "10% effect" is relative and cumulative: from _any_ nice level,
  640. * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
  641. * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
  642. * If a task goes up by ~10% and another task goes down by ~10% then
  643. * the relative distance between them is ~25%.)
  644. */
  645. static const int prio_to_weight[40] = {
  646. /* -20 */ 88818, 71054, 56843, 45475, 36380, 29104, 23283, 18626, 14901, 11921,
  647. /* -10 */ 9537, 7629, 6103, 4883, 3906, 3125, 2500, 2000, 1600, 1280,
  648. /* 0 */ NICE_0_LOAD /* 1024 */,
  649. /* 1 */ 819, 655, 524, 419, 336, 268, 215, 172, 137,
  650. /* 10 */ 110, 87, 70, 56, 45, 36, 29, 23, 18, 15,
  651. };
  652. /*
  653. * Inverse (2^32/x) values of the prio_to_weight[] array, precalculated.
  654. *
  655. * In cases where the weight does not change often, we can use the
  656. * precalculated inverse to speed up arithmetics by turning divisions
  657. * into multiplications:
  658. */
  659. static const u32 prio_to_wmult[40] = {
  660. /* -20 */ 48356, 60446, 75558, 94446, 118058,
  661. /* -15 */ 147573, 184467, 230589, 288233, 360285,
  662. /* -10 */ 450347, 562979, 703746, 879575, 1099582,
  663. /* -5 */ 1374389, 1717986, 2147483, 2684354, 3355443,
  664. /* 0 */ 4194304, 5244160, 6557201, 8196502, 10250518,
  665. /* 5 */ 12782640, 16025997, 19976592, 24970740, 31350126,
  666. /* 10 */ 39045157, 49367440, 61356675, 76695844, 95443717,
  667. /* 15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
  668. };
  669. static inline void
  670. inc_load(struct rq *rq, const struct task_struct *p, u64 now)
  671. {
  672. update_curr_load(rq, now);
  673. update_load_add(&rq->ls.load, p->se.load.weight);
  674. }
  675. static inline void
  676. dec_load(struct rq *rq, const struct task_struct *p, u64 now)
  677. {
  678. update_curr_load(rq, now);
  679. update_load_sub(&rq->ls.load, p->se.load.weight);
  680. }
  681. static inline void inc_nr_running(struct task_struct *p, struct rq *rq, u64 now)
  682. {
  683. rq->nr_running++;
  684. inc_load(rq, p, now);
  685. }
  686. static inline void dec_nr_running(struct task_struct *p, struct rq *rq, u64 now)
  687. {
  688. rq->nr_running--;
  689. dec_load(rq, p, now);
  690. }
  691. static void activate_task(struct rq *rq, struct task_struct *p, int wakeup);
  692. /*
  693. * runqueue iterator, to support SMP load-balancing between different
  694. * scheduling classes, without having to expose their internal data
  695. * structures to the load-balancing proper:
  696. */
  697. struct rq_iterator {
  698. void *arg;
  699. struct task_struct *(*start)(void *);
  700. struct task_struct *(*next)(void *);
  701. };
  702. static int balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
  703. unsigned long max_nr_move, unsigned long max_load_move,
  704. struct sched_domain *sd, enum cpu_idle_type idle,
  705. int *all_pinned, unsigned long *load_moved,
  706. int this_best_prio, int best_prio, int best_prio_seen,
  707. struct rq_iterator *iterator);
  708. #include "sched_stats.h"
  709. #include "sched_rt.c"
  710. #include "sched_fair.c"
  711. #include "sched_idletask.c"
  712. #ifdef CONFIG_SCHED_DEBUG
  713. # include "sched_debug.c"
  714. #endif
  715. #define sched_class_highest (&rt_sched_class)
  716. static void set_load_weight(struct task_struct *p)
  717. {
  718. task_rq(p)->cfs.wait_runtime -= p->se.wait_runtime;
  719. p->se.wait_runtime = 0;
  720. if (task_has_rt_policy(p)) {
  721. p->se.load.weight = prio_to_weight[0] * 2;
  722. p->se.load.inv_weight = prio_to_wmult[0] >> 1;
  723. return;
  724. }
  725. /*
  726. * SCHED_IDLE tasks get minimal weight:
  727. */
  728. if (p->policy == SCHED_IDLE) {
  729. p->se.load.weight = WEIGHT_IDLEPRIO;
  730. p->se.load.inv_weight = WMULT_IDLEPRIO;
  731. return;
  732. }
  733. p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
  734. p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
  735. }
  736. static void
  737. enqueue_task(struct rq *rq, struct task_struct *p, int wakeup, u64 now)
  738. {
  739. sched_info_queued(p);
  740. p->sched_class->enqueue_task(rq, p, wakeup, now);
  741. p->se.on_rq = 1;
  742. }
  743. static void
  744. dequeue_task(struct rq *rq, struct task_struct *p, int sleep, u64 now)
  745. {
  746. p->sched_class->dequeue_task(rq, p, sleep, now);
  747. p->se.on_rq = 0;
  748. }
  749. /*
  750. * __normal_prio - return the priority that is based on the static prio
  751. */
  752. static inline int __normal_prio(struct task_struct *p)
  753. {
  754. return p->static_prio;
  755. }
  756. /*
  757. * Calculate the expected normal priority: i.e. priority
  758. * without taking RT-inheritance into account. Might be
  759. * boosted by interactivity modifiers. Changes upon fork,
  760. * setprio syscalls, and whenever the interactivity
  761. * estimator recalculates.
  762. */
  763. static inline int normal_prio(struct task_struct *p)
  764. {
  765. int prio;
  766. if (task_has_rt_policy(p))
  767. prio = MAX_RT_PRIO-1 - p->rt_priority;
  768. else
  769. prio = __normal_prio(p);
  770. return prio;
  771. }
  772. /*
  773. * Calculate the current priority, i.e. the priority
  774. * taken into account by the scheduler. This value might
  775. * be boosted by RT tasks, or might be boosted by
  776. * interactivity modifiers. Will be RT if the task got
  777. * RT-boosted. If not then it returns p->normal_prio.
  778. */
  779. static int effective_prio(struct task_struct *p)
  780. {
  781. p->normal_prio = normal_prio(p);
  782. /*
  783. * If we are RT tasks or we were boosted to RT priority,
  784. * keep the priority unchanged. Otherwise, update priority
  785. * to the normal priority:
  786. */
  787. if (!rt_prio(p->prio))
  788. return p->normal_prio;
  789. return p->prio;
  790. }
  791. /*
  792. * activate_task - move a task to the runqueue.
  793. */
  794. static void activate_task(struct rq *rq, struct task_struct *p, int wakeup)
  795. {
  796. u64 now = rq_clock(rq);
  797. if (p->state == TASK_UNINTERRUPTIBLE)
  798. rq->nr_uninterruptible--;
  799. enqueue_task(rq, p, wakeup, now);
  800. inc_nr_running(p, rq, now);
  801. }
  802. /*
  803. * activate_idle_task - move idle task to the _front_ of runqueue.
  804. */
  805. static inline void activate_idle_task(struct task_struct *p, struct rq *rq)
  806. {
  807. u64 now = rq_clock(rq);
  808. if (p->state == TASK_UNINTERRUPTIBLE)
  809. rq->nr_uninterruptible--;
  810. enqueue_task(rq, p, 0, now);
  811. inc_nr_running(p, rq, now);
  812. }
  813. /*
  814. * deactivate_task - remove a task from the runqueue.
  815. */
  816. static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep)
  817. {
  818. u64 now = rq_clock(rq);
  819. if (p->state == TASK_UNINTERRUPTIBLE)
  820. rq->nr_uninterruptible++;
  821. dequeue_task(rq, p, sleep, now);
  822. dec_nr_running(p, rq, now);
  823. }
  824. /**
  825. * task_curr - is this task currently executing on a CPU?
  826. * @p: the task in question.
  827. */
  828. inline int task_curr(const struct task_struct *p)
  829. {
  830. return cpu_curr(task_cpu(p)) == p;
  831. }
  832. /* Used instead of source_load when we know the type == 0 */
  833. unsigned long weighted_cpuload(const int cpu)
  834. {
  835. return cpu_rq(cpu)->ls.load.weight;
  836. }
  837. static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
  838. {
  839. #ifdef CONFIG_SMP
  840. task_thread_info(p)->cpu = cpu;
  841. set_task_cfs_rq(p);
  842. #endif
  843. }
  844. #ifdef CONFIG_SMP
  845. void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
  846. {
  847. int old_cpu = task_cpu(p);
  848. struct rq *old_rq = cpu_rq(old_cpu), *new_rq = cpu_rq(new_cpu);
  849. u64 clock_offset, fair_clock_offset;
  850. clock_offset = old_rq->clock - new_rq->clock;
  851. fair_clock_offset = old_rq->cfs.fair_clock -
  852. new_rq->cfs.fair_clock;
  853. if (p->se.wait_start)
  854. p->se.wait_start -= clock_offset;
  855. if (p->se.wait_start_fair)
  856. p->se.wait_start_fair -= fair_clock_offset;
  857. if (p->se.sleep_start)
  858. p->se.sleep_start -= clock_offset;
  859. if (p->se.block_start)
  860. p->se.block_start -= clock_offset;
  861. if (p->se.sleep_start_fair)
  862. p->se.sleep_start_fair -= fair_clock_offset;
  863. __set_task_cpu(p, new_cpu);
  864. }
  865. struct migration_req {
  866. struct list_head list;
  867. struct task_struct *task;
  868. int dest_cpu;
  869. struct completion done;
  870. };
  871. /*
  872. * The task's runqueue lock must be held.
  873. * Returns true if you have to wait for migration thread.
  874. */
  875. static int
  876. migrate_task(struct task_struct *p, int dest_cpu, struct migration_req *req)
  877. {
  878. struct rq *rq = task_rq(p);
  879. /*
  880. * If the task is not on a runqueue (and not running), then
  881. * it is sufficient to simply update the task's cpu field.
  882. */
  883. if (!p->se.on_rq && !task_running(rq, p)) {
  884. set_task_cpu(p, dest_cpu);
  885. return 0;
  886. }
  887. init_completion(&req->done);
  888. req->task = p;
  889. req->dest_cpu = dest_cpu;
  890. list_add(&req->list, &rq->migration_queue);
  891. return 1;
  892. }
  893. /*
  894. * wait_task_inactive - wait for a thread to unschedule.
  895. *
  896. * The caller must ensure that the task *will* unschedule sometime soon,
  897. * else this function might spin for a *long* time. This function can't
  898. * be called with interrupts off, or it may introduce deadlock with
  899. * smp_call_function() if an IPI is sent by the same process we are
  900. * waiting to become inactive.
  901. */
  902. void wait_task_inactive(struct task_struct *p)
  903. {
  904. unsigned long flags;
  905. int running, on_rq;
  906. struct rq *rq;
  907. repeat:
  908. /*
  909. * We do the initial early heuristics without holding
  910. * any task-queue locks at all. We'll only try to get
  911. * the runqueue lock when things look like they will
  912. * work out!
  913. */
  914. rq = task_rq(p);
  915. /*
  916. * If the task is actively running on another CPU
  917. * still, just relax and busy-wait without holding
  918. * any locks.
  919. *
  920. * NOTE! Since we don't hold any locks, it's not
  921. * even sure that "rq" stays as the right runqueue!
  922. * But we don't care, since "task_running()" will
  923. * return false if the runqueue has changed and p
  924. * is actually now running somewhere else!
  925. */
  926. while (task_running(rq, p))
  927. cpu_relax();
  928. /*
  929. * Ok, time to look more closely! We need the rq
  930. * lock now, to be *sure*. If we're wrong, we'll
  931. * just go back and repeat.
  932. */
  933. rq = task_rq_lock(p, &flags);
  934. running = task_running(rq, p);
  935. on_rq = p->se.on_rq;
  936. task_rq_unlock(rq, &flags);
  937. /*
  938. * Was it really running after all now that we
  939. * checked with the proper locks actually held?
  940. *
  941. * Oops. Go back and try again..
  942. */
  943. if (unlikely(running)) {
  944. cpu_relax();
  945. goto repeat;
  946. }
  947. /*
  948. * It's not enough that it's not actively running,
  949. * it must be off the runqueue _entirely_, and not
  950. * preempted!
  951. *
  952. * So if it wa still runnable (but just not actively
  953. * running right now), it's preempted, and we should
  954. * yield - it could be a while.
  955. */
  956. if (unlikely(on_rq)) {
  957. yield();
  958. goto repeat;
  959. }
  960. /*
  961. * Ahh, all good. It wasn't running, and it wasn't
  962. * runnable, which means that it will never become
  963. * running in the future either. We're all done!
  964. */
  965. }
  966. /***
  967. * kick_process - kick a running thread to enter/exit the kernel
  968. * @p: the to-be-kicked thread
  969. *
  970. * Cause a process which is running on another CPU to enter
  971. * kernel-mode, without any delay. (to get signals handled.)
  972. *
  973. * NOTE: this function doesnt have to take the runqueue lock,
  974. * because all it wants to ensure is that the remote task enters
  975. * the kernel. If the IPI races and the task has been migrated
  976. * to another CPU then no harm is done and the purpose has been
  977. * achieved as well.
  978. */
  979. void kick_process(struct task_struct *p)
  980. {
  981. int cpu;
  982. preempt_disable();
  983. cpu = task_cpu(p);
  984. if ((cpu != smp_processor_id()) && task_curr(p))
  985. smp_send_reschedule(cpu);
  986. preempt_enable();
  987. }
  988. /*
  989. * Return a low guess at the load of a migration-source cpu weighted
  990. * according to the scheduling class and "nice" value.
  991. *
  992. * We want to under-estimate the load of migration sources, to
  993. * balance conservatively.
  994. */
  995. static inline unsigned long source_load(int cpu, int type)
  996. {
  997. struct rq *rq = cpu_rq(cpu);
  998. unsigned long total = weighted_cpuload(cpu);
  999. if (type == 0)
  1000. return total;
  1001. return min(rq->cpu_load[type-1], total);
  1002. }
  1003. /*
  1004. * Return a high guess at the load of a migration-target cpu weighted
  1005. * according to the scheduling class and "nice" value.
  1006. */
  1007. static inline unsigned long target_load(int cpu, int type)
  1008. {
  1009. struct rq *rq = cpu_rq(cpu);
  1010. unsigned long total = weighted_cpuload(cpu);
  1011. if (type == 0)
  1012. return total;
  1013. return max(rq->cpu_load[type-1], total);
  1014. }
  1015. /*
  1016. * Return the average load per task on the cpu's run queue
  1017. */
  1018. static inline unsigned long cpu_avg_load_per_task(int cpu)
  1019. {
  1020. struct rq *rq = cpu_rq(cpu);
  1021. unsigned long total = weighted_cpuload(cpu);
  1022. unsigned long n = rq->nr_running;
  1023. return n ? total / n : SCHED_LOAD_SCALE;
  1024. }
  1025. /*
  1026. * find_idlest_group finds and returns the least busy CPU group within the
  1027. * domain.
  1028. */
  1029. static struct sched_group *
  1030. find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)
  1031. {
  1032. struct sched_group *idlest = NULL, *this = NULL, *group = sd->groups;
  1033. unsigned long min_load = ULONG_MAX, this_load = 0;
  1034. int load_idx = sd->forkexec_idx;
  1035. int imbalance = 100 + (sd->imbalance_pct-100)/2;
  1036. do {
  1037. unsigned long load, avg_load;
  1038. int local_group;
  1039. int i;
  1040. /* Skip over this group if it has no CPUs allowed */
  1041. if (!cpus_intersects(group->cpumask, p->cpus_allowed))
  1042. goto nextgroup;
  1043. local_group = cpu_isset(this_cpu, group->cpumask);
  1044. /* Tally up the load of all CPUs in the group */
  1045. avg_load = 0;
  1046. for_each_cpu_mask(i, group->cpumask) {
  1047. /* Bias balancing toward cpus of our domain */
  1048. if (local_group)
  1049. load = source_load(i, load_idx);
  1050. else
  1051. load = target_load(i, load_idx);
  1052. avg_load += load;
  1053. }
  1054. /* Adjust by relative CPU power of the group */
  1055. avg_load = sg_div_cpu_power(group,
  1056. avg_load * SCHED_LOAD_SCALE);
  1057. if (local_group) {
  1058. this_load = avg_load;
  1059. this = group;
  1060. } else if (avg_load < min_load) {
  1061. min_load = avg_load;
  1062. idlest = group;
  1063. }
  1064. nextgroup:
  1065. group = group->next;
  1066. } while (group != sd->groups);
  1067. if (!idlest || 100*this_load < imbalance*min_load)
  1068. return NULL;
  1069. return idlest;
  1070. }
  1071. /*
  1072. * find_idlest_cpu - find the idlest cpu among the cpus in group.
  1073. */
  1074. static int
  1075. find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
  1076. {
  1077. cpumask_t tmp;
  1078. unsigned long load, min_load = ULONG_MAX;
  1079. int idlest = -1;
  1080. int i;
  1081. /* Traverse only the allowed CPUs */
  1082. cpus_and(tmp, group->cpumask, p->cpus_allowed);
  1083. for_each_cpu_mask(i, tmp) {
  1084. load = weighted_cpuload(i);
  1085. if (load < min_load || (load == min_load && i == this_cpu)) {
  1086. min_load = load;
  1087. idlest = i;
  1088. }
  1089. }
  1090. return idlest;
  1091. }
  1092. /*
  1093. * sched_balance_self: balance the current task (running on cpu) in domains
  1094. * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
  1095. * SD_BALANCE_EXEC.
  1096. *
  1097. * Balance, ie. select the least loaded group.
  1098. *
  1099. * Returns the target CPU number, or the same CPU if no balancing is needed.
  1100. *
  1101. * preempt must be disabled.
  1102. */
  1103. static int sched_balance_self(int cpu, int flag)
  1104. {
  1105. struct task_struct *t = current;
  1106. struct sched_domain *tmp, *sd = NULL;
  1107. for_each_domain(cpu, tmp) {
  1108. /*
  1109. * If power savings logic is enabled for a domain, stop there.
  1110. */
  1111. if (tmp->flags & SD_POWERSAVINGS_BALANCE)
  1112. break;
  1113. if (tmp->flags & flag)
  1114. sd = tmp;
  1115. }
  1116. while (sd) {
  1117. cpumask_t span;
  1118. struct sched_group *group;
  1119. int new_cpu, weight;
  1120. if (!(sd->flags & flag)) {
  1121. sd = sd->child;
  1122. continue;
  1123. }
  1124. span = sd->span;
  1125. group = find_idlest_group(sd, t, cpu);
  1126. if (!group) {
  1127. sd = sd->child;
  1128. continue;
  1129. }
  1130. new_cpu = find_idlest_cpu(group, t, cpu);
  1131. if (new_cpu == -1 || new_cpu == cpu) {
  1132. /* Now try balancing at a lower domain level of cpu */
  1133. sd = sd->child;
  1134. continue;
  1135. }
  1136. /* Now try balancing at a lower domain level of new_cpu */
  1137. cpu = new_cpu;
  1138. sd = NULL;
  1139. weight = cpus_weight(span);
  1140. for_each_domain(cpu, tmp) {
  1141. if (weight <= cpus_weight(tmp->span))
  1142. break;
  1143. if (tmp->flags & flag)
  1144. sd = tmp;
  1145. }
  1146. /* while loop will break here if sd == NULL */
  1147. }
  1148. return cpu;
  1149. }
  1150. #endif /* CONFIG_SMP */
  1151. /*
  1152. * wake_idle() will wake a task on an idle cpu if task->cpu is
  1153. * not idle and an idle cpu is available. The span of cpus to
  1154. * search starts with cpus closest then further out as needed,
  1155. * so we always favor a closer, idle cpu.
  1156. *
  1157. * Returns the CPU we should wake onto.
  1158. */
  1159. #if defined(ARCH_HAS_SCHED_WAKE_IDLE)
  1160. static int wake_idle(int cpu, struct task_struct *p)
  1161. {
  1162. cpumask_t tmp;
  1163. struct sched_domain *sd;
  1164. int i;
  1165. /*
  1166. * If it is idle, then it is the best cpu to run this task.
  1167. *
  1168. * This cpu is also the best, if it has more than one task already.
  1169. * Siblings must be also busy(in most cases) as they didn't already
  1170. * pickup the extra load from this cpu and hence we need not check
  1171. * sibling runqueue info. This will avoid the checks and cache miss
  1172. * penalities associated with that.
  1173. */
  1174. if (idle_cpu(cpu) || cpu_rq(cpu)->nr_running > 1)
  1175. return cpu;
  1176. for_each_domain(cpu, sd) {
  1177. if (sd->flags & SD_WAKE_IDLE) {
  1178. cpus_and(tmp, sd->span, p->cpus_allowed);
  1179. for_each_cpu_mask(i, tmp) {
  1180. if (idle_cpu(i))
  1181. return i;
  1182. }
  1183. } else {
  1184. break;
  1185. }
  1186. }
  1187. return cpu;
  1188. }
  1189. #else
  1190. static inline int wake_idle(int cpu, struct task_struct *p)
  1191. {
  1192. return cpu;
  1193. }
  1194. #endif
  1195. /***
  1196. * try_to_wake_up - wake up a thread
  1197. * @p: the to-be-woken-up thread
  1198. * @state: the mask of task states that can be woken
  1199. * @sync: do a synchronous wakeup?
  1200. *
  1201. * Put it on the run-queue if it's not already there. The "current"
  1202. * thread is always on the run-queue (except when the actual
  1203. * re-schedule is in progress), and as such you're allowed to do
  1204. * the simpler "current->state = TASK_RUNNING" to mark yourself
  1205. * runnable without the overhead of this.
  1206. *
  1207. * returns failure only if the task is already active.
  1208. */
  1209. static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
  1210. {
  1211. int cpu, this_cpu, success = 0;
  1212. unsigned long flags;
  1213. long old_state;
  1214. struct rq *rq;
  1215. #ifdef CONFIG_SMP
  1216. struct sched_domain *sd, *this_sd = NULL;
  1217. unsigned long load, this_load;
  1218. int new_cpu;
  1219. #endif
  1220. rq = task_rq_lock(p, &flags);
  1221. old_state = p->state;
  1222. if (!(old_state & state))
  1223. goto out;
  1224. if (p->se.on_rq)
  1225. goto out_running;
  1226. cpu = task_cpu(p);
  1227. this_cpu = smp_processor_id();
  1228. #ifdef CONFIG_SMP
  1229. if (unlikely(task_running(rq, p)))
  1230. goto out_activate;
  1231. new_cpu = cpu;
  1232. schedstat_inc(rq, ttwu_cnt);
  1233. if (cpu == this_cpu) {
  1234. schedstat_inc(rq, ttwu_local);
  1235. goto out_set_cpu;
  1236. }
  1237. for_each_domain(this_cpu, sd) {
  1238. if (cpu_isset(cpu, sd->span)) {
  1239. schedstat_inc(sd, ttwu_wake_remote);
  1240. this_sd = sd;
  1241. break;
  1242. }
  1243. }
  1244. if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed)))
  1245. goto out_set_cpu;
  1246. /*
  1247. * Check for affine wakeup and passive balancing possibilities.
  1248. */
  1249. if (this_sd) {
  1250. int idx = this_sd->wake_idx;
  1251. unsigned int imbalance;
  1252. imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;
  1253. load = source_load(cpu, idx);
  1254. this_load = target_load(this_cpu, idx);
  1255. new_cpu = this_cpu; /* Wake to this CPU if we can */
  1256. if (this_sd->flags & SD_WAKE_AFFINE) {
  1257. unsigned long tl = this_load;
  1258. unsigned long tl_per_task;
  1259. tl_per_task = cpu_avg_load_per_task(this_cpu);
  1260. /*
  1261. * If sync wakeup then subtract the (maximum possible)
  1262. * effect of the currently running task from the load
  1263. * of the current CPU:
  1264. */
  1265. if (sync)
  1266. tl -= current->se.load.weight;
  1267. if ((tl <= load &&
  1268. tl + target_load(cpu, idx) <= tl_per_task) ||
  1269. 100*(tl + p->se.load.weight) <= imbalance*load) {
  1270. /*
  1271. * This domain has SD_WAKE_AFFINE and
  1272. * p is cache cold in this domain, and
  1273. * there is no bad imbalance.
  1274. */
  1275. schedstat_inc(this_sd, ttwu_move_affine);
  1276. goto out_set_cpu;
  1277. }
  1278. }
  1279. /*
  1280. * Start passive balancing when half the imbalance_pct
  1281. * limit is reached.
  1282. */
  1283. if (this_sd->flags & SD_WAKE_BALANCE) {
  1284. if (imbalance*this_load <= 100*load) {
  1285. schedstat_inc(this_sd, ttwu_move_balance);
  1286. goto out_set_cpu;
  1287. }
  1288. }
  1289. }
  1290. new_cpu = cpu; /* Could not wake to this_cpu. Wake to cpu instead */
  1291. out_set_cpu:
  1292. new_cpu = wake_idle(new_cpu, p);
  1293. if (new_cpu != cpu) {
  1294. set_task_cpu(p, new_cpu);
  1295. task_rq_unlock(rq, &flags);
  1296. /* might preempt at this point */
  1297. rq = task_rq_lock(p, &flags);
  1298. old_state = p->state;
  1299. if (!(old_state & state))
  1300. goto out;
  1301. if (p->se.on_rq)
  1302. goto out_running;
  1303. this_cpu = smp_processor_id();
  1304. cpu = task_cpu(p);
  1305. }
  1306. out_activate:
  1307. #endif /* CONFIG_SMP */
  1308. activate_task(rq, p, 1);
  1309. /*
  1310. * Sync wakeups (i.e. those types of wakeups where the waker
  1311. * has indicated that it will leave the CPU in short order)
  1312. * don't trigger a preemption, if the woken up task will run on
  1313. * this cpu. (in this case the 'I will reschedule' promise of
  1314. * the waker guarantees that the freshly woken up task is going
  1315. * to be considered on this CPU.)
  1316. */
  1317. if (!sync || cpu != this_cpu)
  1318. check_preempt_curr(rq, p);
  1319. success = 1;
  1320. out_running:
  1321. p->state = TASK_RUNNING;
  1322. out:
  1323. task_rq_unlock(rq, &flags);
  1324. return success;
  1325. }
  1326. int fastcall wake_up_process(struct task_struct *p)
  1327. {
  1328. return try_to_wake_up(p, TASK_STOPPED | TASK_TRACED |
  1329. TASK_INTERRUPTIBLE | TASK_UNINTERRUPTIBLE, 0);
  1330. }
  1331. EXPORT_SYMBOL(wake_up_process);
  1332. int fastcall wake_up_state(struct task_struct *p, unsigned int state)
  1333. {
  1334. return try_to_wake_up(p, state, 0);
  1335. }
  1336. /*
  1337. * Perform scheduler related setup for a newly forked process p.
  1338. * p is forked by current.
  1339. *
  1340. * __sched_fork() is basic setup used by init_idle() too:
  1341. */
  1342. static void __sched_fork(struct task_struct *p)
  1343. {
  1344. p->se.wait_start_fair = 0;
  1345. p->se.wait_start = 0;
  1346. p->se.exec_start = 0;
  1347. p->se.sum_exec_runtime = 0;
  1348. p->se.delta_exec = 0;
  1349. p->se.delta_fair_run = 0;
  1350. p->se.delta_fair_sleep = 0;
  1351. p->se.wait_runtime = 0;
  1352. p->se.sum_wait_runtime = 0;
  1353. p->se.sum_sleep_runtime = 0;
  1354. p->se.sleep_start = 0;
  1355. p->se.sleep_start_fair = 0;
  1356. p->se.block_start = 0;
  1357. p->se.sleep_max = 0;
  1358. p->se.block_max = 0;
  1359. p->se.exec_max = 0;
  1360. p->se.wait_max = 0;
  1361. p->se.wait_runtime_overruns = 0;
  1362. p->se.wait_runtime_underruns = 0;
  1363. INIT_LIST_HEAD(&p->run_list);
  1364. p->se.on_rq = 0;
  1365. /*
  1366. * We mark the process as running here, but have not actually
  1367. * inserted it onto the runqueue yet. This guarantees that
  1368. * nobody will actually run it, and a signal or other external
  1369. * event cannot wake it up and insert it on the runqueue either.
  1370. */
  1371. p->state = TASK_RUNNING;
  1372. }
  1373. /*
  1374. * fork()/clone()-time setup:
  1375. */
  1376. void sched_fork(struct task_struct *p, int clone_flags)
  1377. {
  1378. int cpu = get_cpu();
  1379. __sched_fork(p);
  1380. #ifdef CONFIG_SMP
  1381. cpu = sched_balance_self(cpu, SD_BALANCE_FORK);
  1382. #endif
  1383. __set_task_cpu(p, cpu);
  1384. /*
  1385. * Make sure we do not leak PI boosting priority to the child:
  1386. */
  1387. p->prio = current->normal_prio;
  1388. #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
  1389. if (likely(sched_info_on()))
  1390. memset(&p->sched_info, 0, sizeof(p->sched_info));
  1391. #endif
  1392. #if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
  1393. p->oncpu = 0;
  1394. #endif
  1395. #ifdef CONFIG_PREEMPT
  1396. /* Want to start with kernel preemption disabled. */
  1397. task_thread_info(p)->preempt_count = 1;
  1398. #endif
  1399. put_cpu();
  1400. }
  1401. /*
  1402. * After fork, child runs first. (default) If set to 0 then
  1403. * parent will (try to) run first.
  1404. */
  1405. unsigned int __read_mostly sysctl_sched_child_runs_first = 1;
  1406. /*
  1407. * wake_up_new_task - wake up a newly created task for the first time.
  1408. *
  1409. * This function will do some initial scheduler statistics housekeeping
  1410. * that must be done for every newly created context, then puts the task
  1411. * on the runqueue and wakes it.
  1412. */
  1413. void fastcall wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
  1414. {
  1415. unsigned long flags;
  1416. struct rq *rq;
  1417. int this_cpu;
  1418. rq = task_rq_lock(p, &flags);
  1419. BUG_ON(p->state != TASK_RUNNING);
  1420. this_cpu = smp_processor_id(); /* parent's CPU */
  1421. p->prio = effective_prio(p);
  1422. if (!sysctl_sched_child_runs_first || (clone_flags & CLONE_VM) ||
  1423. task_cpu(p) != this_cpu || !current->se.on_rq) {
  1424. activate_task(rq, p, 0);
  1425. } else {
  1426. /*
  1427. * Let the scheduling class do new task startup
  1428. * management (if any):
  1429. */
  1430. p->sched_class->task_new(rq, p);
  1431. }
  1432. check_preempt_curr(rq, p);
  1433. task_rq_unlock(rq, &flags);
  1434. }
  1435. /**
  1436. * prepare_task_switch - prepare to switch tasks
  1437. * @rq: the runqueue preparing to switch
  1438. * @next: the task we are going to switch to.
  1439. *
  1440. * This is called with the rq lock held and interrupts off. It must
  1441. * be paired with a subsequent finish_task_switch after the context
  1442. * switch.
  1443. *
  1444. * prepare_task_switch sets up locking and calls architecture specific
  1445. * hooks.
  1446. */
  1447. static inline void prepare_task_switch(struct rq *rq, struct task_struct *next)
  1448. {
  1449. prepare_lock_switch(rq, next);
  1450. prepare_arch_switch(next);
  1451. }
  1452. /**
  1453. * finish_task_switch - clean up after a task-switch
  1454. * @rq: runqueue associated with task-switch
  1455. * @prev: the thread we just switched away from.
  1456. *
  1457. * finish_task_switch must be called after the context switch, paired
  1458. * with a prepare_task_switch call before the context switch.
  1459. * finish_task_switch will reconcile locking set up by prepare_task_switch,
  1460. * and do any other architecture-specific cleanup actions.
  1461. *
  1462. * Note that we may have delayed dropping an mm in context_switch(). If
  1463. * so, we finish that here outside of the runqueue lock. (Doing it
  1464. * with the lock held can cause deadlocks; see schedule() for
  1465. * details.)
  1466. */
  1467. static inline void finish_task_switch(struct rq *rq, struct task_struct *prev)
  1468. __releases(rq->lock)
  1469. {
  1470. struct mm_struct *mm = rq->prev_mm;
  1471. long prev_state;
  1472. rq->prev_mm = NULL;
  1473. /*
  1474. * A task struct has one reference for the use as "current".
  1475. * If a task dies, then it sets TASK_DEAD in tsk->state and calls
  1476. * schedule one last time. The schedule call will never return, and
  1477. * the scheduled task must drop that reference.
  1478. * The test for TASK_DEAD must occur while the runqueue locks are
  1479. * still held, otherwise prev could be scheduled on another cpu, die
  1480. * there before we look at prev->state, and then the reference would
  1481. * be dropped twice.
  1482. * Manfred Spraul <manfred@colorfullife.com>
  1483. */
  1484. prev_state = prev->state;
  1485. finish_arch_switch(prev);
  1486. finish_lock_switch(rq, prev);
  1487. if (mm)
  1488. mmdrop(mm);
  1489. if (unlikely(prev_state == TASK_DEAD)) {
  1490. /*
  1491. * Remove function-return probe instances associated with this
  1492. * task and put them back on the free list.
  1493. */
  1494. kprobe_flush_task(prev);
  1495. put_task_struct(prev);
  1496. }
  1497. }
  1498. /**
  1499. * schedule_tail - first thing a freshly forked thread must call.
  1500. * @prev: the thread we just switched away from.
  1501. */
  1502. asmlinkage void schedule_tail(struct task_struct *prev)
  1503. __releases(rq->lock)
  1504. {
  1505. struct rq *rq = this_rq();
  1506. finish_task_switch(rq, prev);
  1507. #ifdef __ARCH_WANT_UNLOCKED_CTXSW
  1508. /* In this case, finish_task_switch does not reenable preemption */
  1509. preempt_enable();
  1510. #endif
  1511. if (current->set_child_tid)
  1512. put_user(current->pid, current->set_child_tid);
  1513. }
  1514. /*
  1515. * context_switch - switch to the new MM and the new
  1516. * thread's register state.
  1517. */
  1518. static inline void
  1519. context_switch(struct rq *rq, struct task_struct *prev,
  1520. struct task_struct *next)
  1521. {
  1522. struct mm_struct *mm, *oldmm;
  1523. prepare_task_switch(rq, next);
  1524. mm = next->mm;
  1525. oldmm = prev->active_mm;
  1526. /*
  1527. * For paravirt, this is coupled with an exit in switch_to to
  1528. * combine the page table reload and the switch backend into
  1529. * one hypercall.
  1530. */
  1531. arch_enter_lazy_cpu_mode();
  1532. if (unlikely(!mm)) {
  1533. next->active_mm = oldmm;
  1534. atomic_inc(&oldmm->mm_count);
  1535. enter_lazy_tlb(oldmm, next);
  1536. } else
  1537. switch_mm(oldmm, mm, next);
  1538. if (unlikely(!prev->mm)) {
  1539. prev->active_mm = NULL;
  1540. rq->prev_mm = oldmm;
  1541. }
  1542. /*
  1543. * Since the runqueue lock will be released by the next
  1544. * task (which is an invalid locking op but in the case
  1545. * of the scheduler it's an obvious special-case), so we
  1546. * do an early lockdep release here:
  1547. */
  1548. #ifndef __ARCH_WANT_UNLOCKED_CTXSW
  1549. spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
  1550. #endif
  1551. /* Here we just switch the register state and the stack. */
  1552. switch_to(prev, next, prev);
  1553. barrier();
  1554. /*
  1555. * this_rq must be evaluated again because prev may have moved
  1556. * CPUs since it called schedule(), thus the 'rq' on its stack
  1557. * frame will be invalid.
  1558. */
  1559. finish_task_switch(this_rq(), prev);
  1560. }
  1561. /*
  1562. * nr_running, nr_uninterruptible and nr_context_switches:
  1563. *
  1564. * externally visible scheduler statistics: current number of runnable
  1565. * threads, current number of uninterruptible-sleeping threads, total
  1566. * number of context switches performed since bootup.
  1567. */
  1568. unsigned long nr_running(void)
  1569. {
  1570. unsigned long i, sum = 0;
  1571. for_each_online_cpu(i)
  1572. sum += cpu_rq(i)->nr_running;
  1573. return sum;
  1574. }
  1575. unsigned long nr_uninterruptible(void)
  1576. {
  1577. unsigned long i, sum = 0;
  1578. for_each_possible_cpu(i)
  1579. sum += cpu_rq(i)->nr_uninterruptible;
  1580. /*
  1581. * Since we read the counters lockless, it might be slightly
  1582. * inaccurate. Do not allow it to go below zero though:
  1583. */
  1584. if (unlikely((long)sum < 0))
  1585. sum = 0;
  1586. return sum;
  1587. }
  1588. unsigned long long nr_context_switches(void)
  1589. {
  1590. int i;
  1591. unsigned long long sum = 0;
  1592. for_each_possible_cpu(i)
  1593. sum += cpu_rq(i)->nr_switches;
  1594. return sum;
  1595. }
  1596. unsigned long nr_iowait(void)
  1597. {
  1598. unsigned long i, sum = 0;
  1599. for_each_possible_cpu(i)
  1600. sum += atomic_read(&cpu_rq(i)->nr_iowait);
  1601. return sum;
  1602. }
  1603. unsigned long nr_active(void)
  1604. {
  1605. unsigned long i, running = 0, uninterruptible = 0;
  1606. for_each_online_cpu(i) {
  1607. running += cpu_rq(i)->nr_running;
  1608. uninterruptible += cpu_rq(i)->nr_uninterruptible;
  1609. }
  1610. if (unlikely((long)uninterruptible < 0))
  1611. uninterruptible = 0;
  1612. return running + uninterruptible;
  1613. }
  1614. /*
  1615. * Update rq->cpu_load[] statistics. This function is usually called every
  1616. * scheduler tick (TICK_NSEC).
  1617. */
  1618. static void update_cpu_load(struct rq *this_rq)
  1619. {
  1620. u64 fair_delta64, exec_delta64, idle_delta64, sample_interval64, tmp64;
  1621. unsigned long total_load = this_rq->ls.load.weight;
  1622. unsigned long this_load = total_load;
  1623. struct load_stat *ls = &this_rq->ls;
  1624. u64 now = __rq_clock(this_rq);
  1625. int i, scale;
  1626. this_rq->nr_load_updates++;
  1627. if (unlikely(!(sysctl_sched_features & SCHED_FEAT_PRECISE_CPU_LOAD)))
  1628. goto do_avg;
  1629. /* Update delta_fair/delta_exec fields first */
  1630. update_curr_load(this_rq, now);
  1631. fair_delta64 = ls->delta_fair + 1;
  1632. ls->delta_fair = 0;
  1633. exec_delta64 = ls->delta_exec + 1;
  1634. ls->delta_exec = 0;
  1635. sample_interval64 = now - ls->load_update_last;
  1636. ls->load_update_last = now;
  1637. if ((s64)sample_interval64 < (s64)TICK_NSEC)
  1638. sample_interval64 = TICK_NSEC;
  1639. if (exec_delta64 > sample_interval64)
  1640. exec_delta64 = sample_interval64;
  1641. idle_delta64 = sample_interval64 - exec_delta64;
  1642. tmp64 = div64_64(SCHED_LOAD_SCALE * exec_delta64, fair_delta64);
  1643. tmp64 = div64_64(tmp64 * exec_delta64, sample_interval64);
  1644. this_load = (unsigned long)tmp64;
  1645. do_avg:
  1646. /* Update our load: */
  1647. for (i = 0, scale = 1; i < CPU_LOAD_IDX_MAX; i++, scale += scale) {
  1648. unsigned long old_load, new_load;
  1649. /* scale is effectively 1 << i now, and >> i divides by scale */
  1650. old_load = this_rq->cpu_load[i];
  1651. new_load = this_load;
  1652. this_rq->cpu_load[i] = (old_load*(scale-1) + new_load) >> i;
  1653. }
  1654. }
  1655. #ifdef CONFIG_SMP
  1656. /*
  1657. * double_rq_lock - safely lock two runqueues
  1658. *
  1659. * Note this does not disable interrupts like task_rq_lock,
  1660. * you need to do so manually before calling.
  1661. */
  1662. static void double_rq_lock(struct rq *rq1, struct rq *rq2)
  1663. __acquires(rq1->lock)
  1664. __acquires(rq2->lock)
  1665. {
  1666. BUG_ON(!irqs_disabled());
  1667. if (rq1 == rq2) {
  1668. spin_lock(&rq1->lock);
  1669. __acquire(rq2->lock); /* Fake it out ;) */
  1670. } else {
  1671. if (rq1 < rq2) {
  1672. spin_lock(&rq1->lock);
  1673. spin_lock(&rq2->lock);
  1674. } else {
  1675. spin_lock(&rq2->lock);
  1676. spin_lock(&rq1->lock);
  1677. }
  1678. }
  1679. }
  1680. /*
  1681. * double_rq_unlock - safely unlock two runqueues
  1682. *
  1683. * Note this does not restore interrupts like task_rq_unlock,
  1684. * you need to do so manually after calling.
  1685. */
  1686. static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
  1687. __releases(rq1->lock)
  1688. __releases(rq2->lock)
  1689. {
  1690. spin_unlock(&rq1->lock);
  1691. if (rq1 != rq2)
  1692. spin_unlock(&rq2->lock);
  1693. else
  1694. __release(rq2->lock);
  1695. }
  1696. /*
  1697. * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
  1698. */
  1699. static void double_lock_balance(struct rq *this_rq, struct rq *busiest)
  1700. __releases(this_rq->lock)
  1701. __acquires(busiest->lock)
  1702. __acquires(this_rq->lock)
  1703. {
  1704. if (unlikely(!irqs_disabled())) {
  1705. /* printk() doesn't work good under rq->lock */
  1706. spin_unlock(&this_rq->lock);
  1707. BUG_ON(1);
  1708. }
  1709. if (unlikely(!spin_trylock(&busiest->lock))) {
  1710. if (busiest < this_rq) {
  1711. spin_unlock(&this_rq->lock);
  1712. spin_lock(&busiest->lock);
  1713. spin_lock(&this_rq->lock);
  1714. } else
  1715. spin_lock(&busiest->lock);
  1716. }
  1717. }
  1718. /*
  1719. * If dest_cpu is allowed for this process, migrate the task to it.
  1720. * This is accomplished by forcing the cpu_allowed mask to only
  1721. * allow dest_cpu, which will force the cpu onto dest_cpu. Then
  1722. * the cpu_allowed mask is restored.
  1723. */
  1724. static void sched_migrate_task(struct task_struct *p, int dest_cpu)
  1725. {
  1726. struct migration_req req;
  1727. unsigned long flags;
  1728. struct rq *rq;
  1729. rq = task_rq_lock(p, &flags);
  1730. if (!cpu_isset(dest_cpu, p->cpus_allowed)
  1731. || unlikely(cpu_is_offline(dest_cpu)))
  1732. goto out;
  1733. /* force the process onto the specified CPU */
  1734. if (migrate_task(p, dest_cpu, &req)) {
  1735. /* Need to wait for migration thread (might exit: take ref). */
  1736. struct task_struct *mt = rq->migration_thread;
  1737. get_task_struct(mt);
  1738. task_rq_unlock(rq, &flags);
  1739. wake_up_process(mt);
  1740. put_task_struct(mt);
  1741. wait_for_completion(&req.done);
  1742. return;
  1743. }
  1744. out:
  1745. task_rq_unlock(rq, &flags);
  1746. }
  1747. /*
  1748. * sched_exec - execve() is a valuable balancing opportunity, because at
  1749. * this point the task has the smallest effective memory and cache footprint.
  1750. */
  1751. void sched_exec(void)
  1752. {
  1753. int new_cpu, this_cpu = get_cpu();
  1754. new_cpu = sched_balance_self(this_cpu, SD_BALANCE_EXEC);
  1755. put_cpu();
  1756. if (new_cpu != this_cpu)
  1757. sched_migrate_task(current, new_cpu);
  1758. }
  1759. /*
  1760. * pull_task - move a task from a remote runqueue to the local runqueue.
  1761. * Both runqueues must be locked.
  1762. */
  1763. static void pull_task(struct rq *src_rq, struct task_struct *p,
  1764. struct rq *this_rq, int this_cpu)
  1765. {
  1766. deactivate_task(src_rq, p, 0);
  1767. set_task_cpu(p, this_cpu);
  1768. activate_task(this_rq, p, 0);
  1769. /*
  1770. * Note that idle threads have a prio of MAX_PRIO, for this test
  1771. * to be always true for them.
  1772. */
  1773. check_preempt_curr(this_rq, p);
  1774. }
  1775. /*
  1776. * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
  1777. */
  1778. static
  1779. int can_migrate_task(struct task_struct *p, struct rq *rq, int this_cpu,
  1780. struct sched_domain *sd, enum cpu_idle_type idle,
  1781. int *all_pinned)
  1782. {
  1783. /*
  1784. * We do not migrate tasks that are:
  1785. * 1) running (obviously), or
  1786. * 2) cannot be migrated to this CPU due to cpus_allowed, or
  1787. * 3) are cache-hot on their current CPU.
  1788. */
  1789. if (!cpu_isset(this_cpu, p->cpus_allowed))
  1790. return 0;
  1791. *all_pinned = 0;
  1792. if (task_running(rq, p))
  1793. return 0;
  1794. /*
  1795. * Aggressive migration if too many balance attempts have failed:
  1796. */
  1797. if (sd->nr_balance_failed > sd->cache_nice_tries)
  1798. return 1;
  1799. return 1;
  1800. }
  1801. static int balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1802. unsigned long max_nr_move, unsigned long max_load_move,
  1803. struct sched_domain *sd, enum cpu_idle_type idle,
  1804. int *all_pinned, unsigned long *load_moved,
  1805. int this_best_prio, int best_prio, int best_prio_seen,
  1806. struct rq_iterator *iterator)
  1807. {
  1808. int pulled = 0, pinned = 0, skip_for_load;
  1809. struct task_struct *p;
  1810. long rem_load_move = max_load_move;
  1811. if (max_nr_move == 0 || max_load_move == 0)
  1812. goto out;
  1813. pinned = 1;
  1814. /*
  1815. * Start the load-balancing iterator:
  1816. */
  1817. p = iterator->start(iterator->arg);
  1818. next:
  1819. if (!p)
  1820. goto out;
  1821. /*
  1822. * To help distribute high priority tasks accross CPUs we don't
  1823. * skip a task if it will be the highest priority task (i.e. smallest
  1824. * prio value) on its new queue regardless of its load weight
  1825. */
  1826. skip_for_load = (p->se.load.weight >> 1) > rem_load_move +
  1827. SCHED_LOAD_SCALE_FUZZ;
  1828. if (skip_for_load && p->prio < this_best_prio)
  1829. skip_for_load = !best_prio_seen && p->prio == best_prio;
  1830. if (skip_for_load ||
  1831. !can_migrate_task(p, busiest, this_cpu, sd, idle, &pinned)) {
  1832. best_prio_seen |= p->prio == best_prio;
  1833. p = iterator->next(iterator->arg);
  1834. goto next;
  1835. }
  1836. pull_task(busiest, p, this_rq, this_cpu);
  1837. pulled++;
  1838. rem_load_move -= p->se.load.weight;
  1839. /*
  1840. * We only want to steal up to the prescribed number of tasks
  1841. * and the prescribed amount of weighted load.
  1842. */
  1843. if (pulled < max_nr_move && rem_load_move > 0) {
  1844. if (p->prio < this_best_prio)
  1845. this_best_prio = p->prio;
  1846. p = iterator->next(iterator->arg);
  1847. goto next;
  1848. }
  1849. out:
  1850. /*
  1851. * Right now, this is the only place pull_task() is called,
  1852. * so we can safely collect pull_task() stats here rather than
  1853. * inside pull_task().
  1854. */
  1855. schedstat_add(sd, lb_gained[idle], pulled);
  1856. if (all_pinned)
  1857. *all_pinned = pinned;
  1858. *load_moved = max_load_move - rem_load_move;
  1859. return pulled;
  1860. }
  1861. /*
  1862. * move_tasks tries to move up to max_nr_move tasks and max_load_move weighted
  1863. * load from busiest to this_rq, as part of a balancing operation within
  1864. * "domain". Returns the number of tasks moved.
  1865. *
  1866. * Called with both runqueues locked.
  1867. */
  1868. static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1869. unsigned long max_nr_move, unsigned long max_load_move,
  1870. struct sched_domain *sd, enum cpu_idle_type idle,
  1871. int *all_pinned)
  1872. {
  1873. struct sched_class *class = sched_class_highest;
  1874. unsigned long load_moved, total_nr_moved = 0, nr_moved;
  1875. long rem_load_move = max_load_move;
  1876. do {
  1877. nr_moved = class->load_balance(this_rq, this_cpu, busiest,
  1878. max_nr_move, (unsigned long)rem_load_move,
  1879. sd, idle, all_pinned, &load_moved);
  1880. total_nr_moved += nr_moved;
  1881. max_nr_move -= nr_moved;
  1882. rem_load_move -= load_moved;
  1883. class = class->next;
  1884. } while (class && max_nr_move && rem_load_move > 0);
  1885. return total_nr_moved;
  1886. }
  1887. /*
  1888. * find_busiest_group finds and returns the busiest CPU group within the
  1889. * domain. It calculates and returns the amount of weighted load which
  1890. * should be moved to restore balance via the imbalance parameter.
  1891. */
  1892. static struct sched_group *
  1893. find_busiest_group(struct sched_domain *sd, int this_cpu,
  1894. unsigned long *imbalance, enum cpu_idle_type idle,
  1895. int *sd_idle, cpumask_t *cpus, int *balance)
  1896. {
  1897. struct sched_group *busiest = NULL, *this = NULL, *group = sd->groups;
  1898. unsigned long max_load, avg_load, total_load, this_load, total_pwr;
  1899. unsigned long max_pull;
  1900. unsigned long busiest_load_per_task, busiest_nr_running;
  1901. unsigned long this_load_per_task, this_nr_running;
  1902. int load_idx;
  1903. #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
  1904. int power_savings_balance = 1;
  1905. unsigned long leader_nr_running = 0, min_load_per_task = 0;
  1906. unsigned long min_nr_running = ULONG_MAX;
  1907. struct sched_group *group_min = NULL, *group_leader = NULL;
  1908. #endif
  1909. max_load = this_load = total_load = total_pwr = 0;
  1910. busiest_load_per_task = busiest_nr_running = 0;
  1911. this_load_per_task = this_nr_running = 0;
  1912. if (idle == CPU_NOT_IDLE)
  1913. load_idx = sd->busy_idx;
  1914. else if (idle == CPU_NEWLY_IDLE)
  1915. load_idx = sd->newidle_idx;
  1916. else
  1917. load_idx = sd->idle_idx;
  1918. do {
  1919. unsigned long load, group_capacity;
  1920. int local_group;
  1921. int i;
  1922. unsigned int balance_cpu = -1, first_idle_cpu = 0;
  1923. unsigned long sum_nr_running, sum_weighted_load;
  1924. local_group = cpu_isset(this_cpu, group->cpumask);
  1925. if (local_group)
  1926. balance_cpu = first_cpu(group->cpumask);
  1927. /* Tally up the load of all CPUs in the group */
  1928. sum_weighted_load = sum_nr_running = avg_load = 0;
  1929. for_each_cpu_mask(i, group->cpumask) {
  1930. struct rq *rq;
  1931. if (!cpu_isset(i, *cpus))
  1932. continue;
  1933. rq = cpu_rq(i);
  1934. if (*sd_idle && rq->nr_running)
  1935. *sd_idle = 0;
  1936. /* Bias balancing toward cpus of our domain */
  1937. if (local_group) {
  1938. if (idle_cpu(i) && !first_idle_cpu) {
  1939. first_idle_cpu = 1;
  1940. balance_cpu = i;
  1941. }
  1942. load = target_load(i, load_idx);
  1943. } else
  1944. load = source_load(i, load_idx);
  1945. avg_load += load;
  1946. sum_nr_running += rq->nr_running;
  1947. sum_weighted_load += weighted_cpuload(i);
  1948. }
  1949. /*
  1950. * First idle cpu or the first cpu(busiest) in this sched group
  1951. * is eligible for doing load balancing at this and above
  1952. * domains. In the newly idle case, we will allow all the cpu's
  1953. * to do the newly idle load balance.
  1954. */
  1955. if (idle != CPU_NEWLY_IDLE && local_group &&
  1956. balance_cpu != this_cpu && balance) {
  1957. *balance = 0;
  1958. goto ret;
  1959. }
  1960. total_load += avg_load;
  1961. total_pwr += group->__cpu_power;
  1962. /* Adjust by relative CPU power of the group */
  1963. avg_load = sg_div_cpu_power(group,
  1964. avg_load * SCHED_LOAD_SCALE);
  1965. group_capacity = group->__cpu_power / SCHED_LOAD_SCALE;
  1966. if (local_group) {
  1967. this_load = avg_load;
  1968. this = group;
  1969. this_nr_running = sum_nr_running;
  1970. this_load_per_task = sum_weighted_load;
  1971. } else if (avg_load > max_load &&
  1972. sum_nr_running > group_capacity) {
  1973. max_load = avg_load;
  1974. busiest = group;
  1975. busiest_nr_running = sum_nr_running;
  1976. busiest_load_per_task = sum_weighted_load;
  1977. }
  1978. #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
  1979. /*
  1980. * Busy processors will not participate in power savings
  1981. * balance.
  1982. */
  1983. if (idle == CPU_NOT_IDLE ||
  1984. !(sd->flags & SD_POWERSAVINGS_BALANCE))
  1985. goto group_next;
  1986. /*
  1987. * If the local group is idle or completely loaded
  1988. * no need to do power savings balance at this domain
  1989. */
  1990. if (local_group && (this_nr_running >= group_capacity ||
  1991. !this_nr_running))
  1992. power_savings_balance = 0;
  1993. /*
  1994. * If a group is already running at full capacity or idle,
  1995. * don't include that group in power savings calculations
  1996. */
  1997. if (!power_savings_balance || sum_nr_running >= group_capacity
  1998. || !sum_nr_running)
  1999. goto group_next;
  2000. /*
  2001. * Calculate the group which has the least non-idle load.
  2002. * This is the group from where we need to pick up the load
  2003. * for saving power
  2004. */
  2005. if ((sum_nr_running < min_nr_running) ||
  2006. (sum_nr_running == min_nr_running &&
  2007. first_cpu(group->cpumask) <
  2008. first_cpu(group_min->cpumask))) {
  2009. group_min = group;
  2010. min_nr_running = sum_nr_running;
  2011. min_load_per_task = sum_weighted_load /
  2012. sum_nr_running;
  2013. }
  2014. /*
  2015. * Calculate the group which is almost near its
  2016. * capacity but still has some space to pick up some load
  2017. * from other group and save more power
  2018. */
  2019. if (sum_nr_running <= group_capacity - 1) {
  2020. if (sum_nr_running > leader_nr_running ||
  2021. (sum_nr_running == leader_nr_running &&
  2022. first_cpu(group->cpumask) >
  2023. first_cpu(group_leader->cpumask))) {
  2024. group_leader = group;
  2025. leader_nr_running = sum_nr_running;
  2026. }
  2027. }
  2028. group_next:
  2029. #endif
  2030. group = group->next;
  2031. } while (group != sd->groups);
  2032. if (!busiest || this_load >= max_load || busiest_nr_running == 0)
  2033. goto out_balanced;
  2034. avg_load = (SCHED_LOAD_SCALE * total_load) / total_pwr;
  2035. if (this_load >= avg_load ||
  2036. 100*max_load <= sd->imbalance_pct*this_load)
  2037. goto out_balanced;
  2038. busiest_load_per_task /= busiest_nr_running;
  2039. /*
  2040. * We're trying to get all the cpus to the average_load, so we don't
  2041. * want to push ourselves above the average load, nor do we wish to
  2042. * reduce the max loaded cpu below the average load, as either of these
  2043. * actions would just result in more rebalancing later, and ping-pong
  2044. * tasks around. Thus we look for the minimum possible imbalance.
  2045. * Negative imbalances (*we* are more loaded than anyone else) will
  2046. * be counted as no imbalance for these purposes -- we can't fix that
  2047. * by pulling tasks to us. Be careful of negative numbers as they'll
  2048. * appear as very large values with unsigned longs.
  2049. */
  2050. if (max_load <= busiest_load_per_task)
  2051. goto out_balanced;
  2052. /*
  2053. * In the presence of smp nice balancing, certain scenarios can have
  2054. * max load less than avg load(as we skip the groups at or below
  2055. * its cpu_power, while calculating max_load..)
  2056. */
  2057. if (max_load < avg_load) {
  2058. *imbalance = 0;
  2059. goto small_imbalance;
  2060. }
  2061. /* Don't want to pull so many tasks that a group would go idle */
  2062. max_pull = min(max_load - avg_load, max_load - busiest_load_per_task);
  2063. /* How much load to actually move to equalise the imbalance */
  2064. *imbalance = min(max_pull * busiest->__cpu_power,
  2065. (avg_load - this_load) * this->__cpu_power)
  2066. / SCHED_LOAD_SCALE;
  2067. /*
  2068. * if *imbalance is less than the average load per runnable task
  2069. * there is no gaurantee that any tasks will be moved so we'll have
  2070. * a think about bumping its value to force at least one task to be
  2071. * moved
  2072. */
  2073. if (*imbalance + SCHED_LOAD_SCALE_FUZZ < busiest_load_per_task/2) {
  2074. unsigned long tmp, pwr_now, pwr_move;
  2075. unsigned int imbn;
  2076. small_imbalance:
  2077. pwr_move = pwr_now = 0;
  2078. imbn = 2;
  2079. if (this_nr_running) {
  2080. this_load_per_task /= this_nr_running;
  2081. if (busiest_load_per_task > this_load_per_task)
  2082. imbn = 1;
  2083. } else
  2084. this_load_per_task = SCHED_LOAD_SCALE;
  2085. if (max_load - this_load + SCHED_LOAD_SCALE_FUZZ >=
  2086. busiest_load_per_task * imbn) {
  2087. *imbalance = busiest_load_per_task;
  2088. return busiest;
  2089. }
  2090. /*
  2091. * OK, we don't have enough imbalance to justify moving tasks,
  2092. * however we may be able to increase total CPU power used by
  2093. * moving them.
  2094. */
  2095. pwr_now += busiest->__cpu_power *
  2096. min(busiest_load_per_task, max_load);
  2097. pwr_now += this->__cpu_power *
  2098. min(this_load_per_task, this_load);
  2099. pwr_now /= SCHED_LOAD_SCALE;
  2100. /* Amount of load we'd subtract */
  2101. tmp = sg_div_cpu_power(busiest,
  2102. busiest_load_per_task * SCHED_LOAD_SCALE);
  2103. if (max_load > tmp)
  2104. pwr_move += busiest->__cpu_power *
  2105. min(busiest_load_per_task, max_load - tmp);
  2106. /* Amount of load we'd add */
  2107. if (max_load * busiest->__cpu_power <
  2108. busiest_load_per_task * SCHED_LOAD_SCALE)
  2109. tmp = sg_div_cpu_power(this,
  2110. max_load * busiest->__cpu_power);
  2111. else
  2112. tmp = sg_div_cpu_power(this,
  2113. busiest_load_per_task * SCHED_LOAD_SCALE);
  2114. pwr_move += this->__cpu_power *
  2115. min(this_load_per_task, this_load + tmp);
  2116. pwr_move /= SCHED_LOAD_SCALE;
  2117. /* Move if we gain throughput */
  2118. if (pwr_move <= pwr_now)
  2119. goto out_balanced;
  2120. *imbalance = busiest_load_per_task;
  2121. }
  2122. return busiest;
  2123. out_balanced:
  2124. #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
  2125. if (idle == CPU_NOT_IDLE || !(sd->flags & SD_POWERSAVINGS_BALANCE))
  2126. goto ret;
  2127. if (this == group_leader && group_leader != group_min) {
  2128. *imbalance = min_load_per_task;
  2129. return group_min;
  2130. }
  2131. #endif
  2132. ret:
  2133. *imbalance = 0;
  2134. return NULL;
  2135. }
  2136. /*
  2137. * find_busiest_queue - find the busiest runqueue among the cpus in group.
  2138. */
  2139. static struct rq *
  2140. find_busiest_queue(struct sched_group *group, enum cpu_idle_type idle,
  2141. unsigned long imbalance, cpumask_t *cpus)
  2142. {
  2143. struct rq *busiest = NULL, *rq;
  2144. unsigned long max_load = 0;
  2145. int i;
  2146. for_each_cpu_mask(i, group->cpumask) {
  2147. unsigned long wl;
  2148. if (!cpu_isset(i, *cpus))
  2149. continue;
  2150. rq = cpu_rq(i);
  2151. wl = weighted_cpuload(i);
  2152. if (rq->nr_running == 1 && wl > imbalance)
  2153. continue;
  2154. if (wl > max_load) {
  2155. max_load = wl;
  2156. busiest = rq;
  2157. }
  2158. }
  2159. return busiest;
  2160. }
  2161. /*
  2162. * Max backoff if we encounter pinned tasks. Pretty arbitrary value, but
  2163. * so long as it is large enough.
  2164. */
  2165. #define MAX_PINNED_INTERVAL 512
  2166. static inline unsigned long minus_1_or_zero(unsigned long n)
  2167. {
  2168. return n > 0 ? n - 1 : 0;
  2169. }
  2170. /*
  2171. * Check this_cpu to ensure it is balanced within domain. Attempt to move
  2172. * tasks if there is an imbalance.
  2173. */
  2174. static int load_balance(int this_cpu, struct rq *this_rq,
  2175. struct sched_domain *sd, enum cpu_idle_type idle,
  2176. int *balance)
  2177. {
  2178. int nr_moved, all_pinned = 0, active_balance = 0, sd_idle = 0;
  2179. struct sched_group *group;
  2180. unsigned long imbalance;
  2181. struct rq *busiest;
  2182. cpumask_t cpus = CPU_MASK_ALL;
  2183. unsigned long flags;
  2184. /*
  2185. * When power savings policy is enabled for the parent domain, idle
  2186. * sibling can pick up load irrespective of busy siblings. In this case,
  2187. * let the state of idle sibling percolate up as CPU_IDLE, instead of
  2188. * portraying it as CPU_NOT_IDLE.
  2189. */
  2190. if (idle != CPU_NOT_IDLE && sd->flags & SD_SHARE_CPUPOWER &&
  2191. !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2192. sd_idle = 1;
  2193. schedstat_inc(sd, lb_cnt[idle]);
  2194. redo:
  2195. group = find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle,
  2196. &cpus, balance);
  2197. if (*balance == 0)
  2198. goto out_balanced;
  2199. if (!group) {
  2200. schedstat_inc(sd, lb_nobusyg[idle]);
  2201. goto out_balanced;
  2202. }
  2203. busiest = find_busiest_queue(group, idle, imbalance, &cpus);
  2204. if (!busiest) {
  2205. schedstat_inc(sd, lb_nobusyq[idle]);
  2206. goto out_balanced;
  2207. }
  2208. BUG_ON(busiest == this_rq);
  2209. schedstat_add(sd, lb_imbalance[idle], imbalance);
  2210. nr_moved = 0;
  2211. if (busiest->nr_running > 1) {
  2212. /*
  2213. * Attempt to move tasks. If find_busiest_group has found
  2214. * an imbalance but busiest->nr_running <= 1, the group is
  2215. * still unbalanced. nr_moved simply stays zero, so it is
  2216. * correctly treated as an imbalance.
  2217. */
  2218. local_irq_save(flags);
  2219. double_rq_lock(this_rq, busiest);
  2220. nr_moved = move_tasks(this_rq, this_cpu, busiest,
  2221. minus_1_or_zero(busiest->nr_running),
  2222. imbalance, sd, idle, &all_pinned);
  2223. double_rq_unlock(this_rq, busiest);
  2224. local_irq_restore(flags);
  2225. /*
  2226. * some other cpu did the load balance for us.
  2227. */
  2228. if (nr_moved && this_cpu != smp_processor_id())
  2229. resched_cpu(this_cpu);
  2230. /* All tasks on this runqueue were pinned by CPU affinity */
  2231. if (unlikely(all_pinned)) {
  2232. cpu_clear(cpu_of(busiest), cpus);
  2233. if (!cpus_empty(cpus))
  2234. goto redo;
  2235. goto out_balanced;
  2236. }
  2237. }
  2238. if (!nr_moved) {
  2239. schedstat_inc(sd, lb_failed[idle]);
  2240. sd->nr_balance_failed++;
  2241. if (unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2)) {
  2242. spin_lock_irqsave(&busiest->lock, flags);
  2243. /* don't kick the migration_thread, if the curr
  2244. * task on busiest cpu can't be moved to this_cpu
  2245. */
  2246. if (!cpu_isset(this_cpu, busiest->curr->cpus_allowed)) {
  2247. spin_unlock_irqrestore(&busiest->lock, flags);
  2248. all_pinned = 1;
  2249. goto out_one_pinned;
  2250. }
  2251. if (!busiest->active_balance) {
  2252. busiest->active_balance = 1;
  2253. busiest->push_cpu = this_cpu;
  2254. active_balance = 1;
  2255. }
  2256. spin_unlock_irqrestore(&busiest->lock, flags);
  2257. if (active_balance)
  2258. wake_up_process(busiest->migration_thread);
  2259. /*
  2260. * We've kicked active balancing, reset the failure
  2261. * counter.
  2262. */
  2263. sd->nr_balance_failed = sd->cache_nice_tries+1;
  2264. }
  2265. } else
  2266. sd->nr_balance_failed = 0;
  2267. if (likely(!active_balance)) {
  2268. /* We were unbalanced, so reset the balancing interval */
  2269. sd->balance_interval = sd->min_interval;
  2270. } else {
  2271. /*
  2272. * If we've begun active balancing, start to back off. This
  2273. * case may not be covered by the all_pinned logic if there
  2274. * is only 1 task on the busy runqueue (because we don't call
  2275. * move_tasks).
  2276. */
  2277. if (sd->balance_interval < sd->max_interval)
  2278. sd->balance_interval *= 2;
  2279. }
  2280. if (!nr_moved && !sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
  2281. !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2282. return -1;
  2283. return nr_moved;
  2284. out_balanced:
  2285. schedstat_inc(sd, lb_balanced[idle]);
  2286. sd->nr_balance_failed = 0;
  2287. out_one_pinned:
  2288. /* tune up the balancing interval */
  2289. if ((all_pinned && sd->balance_interval < MAX_PINNED_INTERVAL) ||
  2290. (sd->balance_interval < sd->max_interval))
  2291. sd->balance_interval *= 2;
  2292. if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
  2293. !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2294. return -1;
  2295. return 0;
  2296. }
  2297. /*
  2298. * Check this_cpu to ensure it is balanced within domain. Attempt to move
  2299. * tasks if there is an imbalance.
  2300. *
  2301. * Called from schedule when this_rq is about to become idle (CPU_NEWLY_IDLE).
  2302. * this_rq is locked.
  2303. */
  2304. static int
  2305. load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd)
  2306. {
  2307. struct sched_group *group;
  2308. struct rq *busiest = NULL;
  2309. unsigned long imbalance;
  2310. int nr_moved = 0;
  2311. int sd_idle = 0;
  2312. int all_pinned = 0;
  2313. cpumask_t cpus = CPU_MASK_ALL;
  2314. /*
  2315. * When power savings policy is enabled for the parent domain, idle
  2316. * sibling can pick up load irrespective of busy siblings. In this case,
  2317. * let the state of idle sibling percolate up as IDLE, instead of
  2318. * portraying it as CPU_NOT_IDLE.
  2319. */
  2320. if (sd->flags & SD_SHARE_CPUPOWER &&
  2321. !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2322. sd_idle = 1;
  2323. schedstat_inc(sd, lb_cnt[CPU_NEWLY_IDLE]);
  2324. redo:
  2325. group = find_busiest_group(sd, this_cpu, &imbalance, CPU_NEWLY_IDLE,
  2326. &sd_idle, &cpus, NULL);
  2327. if (!group) {
  2328. schedstat_inc(sd, lb_nobusyg[CPU_NEWLY_IDLE]);
  2329. goto out_balanced;
  2330. }
  2331. busiest = find_busiest_queue(group, CPU_NEWLY_IDLE, imbalance,
  2332. &cpus);
  2333. if (!busiest) {
  2334. schedstat_inc(sd, lb_nobusyq[CPU_NEWLY_IDLE]);
  2335. goto out_balanced;
  2336. }
  2337. BUG_ON(busiest == this_rq);
  2338. schedstat_add(sd, lb_imbalance[CPU_NEWLY_IDLE], imbalance);
  2339. nr_moved = 0;
  2340. if (busiest->nr_running > 1) {
  2341. /* Attempt to move tasks */
  2342. double_lock_balance(this_rq, busiest);
  2343. nr_moved = move_tasks(this_rq, this_cpu, busiest,
  2344. minus_1_or_zero(busiest->nr_running),
  2345. imbalance, sd, CPU_NEWLY_IDLE,
  2346. &all_pinned);
  2347. spin_unlock(&busiest->lock);
  2348. if (unlikely(all_pinned)) {
  2349. cpu_clear(cpu_of(busiest), cpus);
  2350. if (!cpus_empty(cpus))
  2351. goto redo;
  2352. }
  2353. }
  2354. if (!nr_moved) {
  2355. schedstat_inc(sd, lb_failed[CPU_NEWLY_IDLE]);
  2356. if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
  2357. !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2358. return -1;
  2359. } else
  2360. sd->nr_balance_failed = 0;
  2361. return nr_moved;
  2362. out_balanced:
  2363. schedstat_inc(sd, lb_balanced[CPU_NEWLY_IDLE]);
  2364. if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
  2365. !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2366. return -1;
  2367. sd->nr_balance_failed = 0;
  2368. return 0;
  2369. }
  2370. /*
  2371. * idle_balance is called by schedule() if this_cpu is about to become
  2372. * idle. Attempts to pull tasks from other CPUs.
  2373. */
  2374. static void idle_balance(int this_cpu, struct rq *this_rq)
  2375. {
  2376. struct sched_domain *sd;
  2377. int pulled_task = -1;
  2378. unsigned long next_balance = jiffies + HZ;
  2379. for_each_domain(this_cpu, sd) {
  2380. unsigned long interval;
  2381. if (!(sd->flags & SD_LOAD_BALANCE))
  2382. continue;
  2383. if (sd->flags & SD_BALANCE_NEWIDLE)
  2384. /* If we've pulled tasks over stop searching: */
  2385. pulled_task = load_balance_newidle(this_cpu,
  2386. this_rq, sd);
  2387. interval = msecs_to_jiffies(sd->balance_interval);
  2388. if (time_after(next_balance, sd->last_balance + interval))
  2389. next_balance = sd->last_balance + interval;
  2390. if (pulled_task)
  2391. break;
  2392. }
  2393. if (pulled_task || time_after(jiffies, this_rq->next_balance)) {
  2394. /*
  2395. * We are going idle. next_balance may be set based on
  2396. * a busy processor. So reset next_balance.
  2397. */
  2398. this_rq->next_balance = next_balance;
  2399. }
  2400. }
  2401. /*
  2402. * active_load_balance is run by migration threads. It pushes running tasks
  2403. * off the busiest CPU onto idle CPUs. It requires at least 1 task to be
  2404. * running on each physical CPU where possible, and avoids physical /
  2405. * logical imbalances.
  2406. *
  2407. * Called with busiest_rq locked.
  2408. */
  2409. static void active_load_balance(struct rq *busiest_rq, int busiest_cpu)
  2410. {
  2411. int target_cpu = busiest_rq->push_cpu;
  2412. struct sched_domain *sd;
  2413. struct rq *target_rq;
  2414. /* Is there any task to move? */
  2415. if (busiest_rq->nr_running <= 1)
  2416. return;
  2417. target_rq = cpu_rq(target_cpu);
  2418. /*
  2419. * This condition is "impossible", if it occurs
  2420. * we need to fix it. Originally reported by
  2421. * Bjorn Helgaas on a 128-cpu setup.
  2422. */
  2423. BUG_ON(busiest_rq == target_rq);
  2424. /* move a task from busiest_rq to target_rq */
  2425. double_lock_balance(busiest_rq, target_rq);
  2426. /* Search for an sd spanning us and the target CPU. */
  2427. for_each_domain(target_cpu, sd) {
  2428. if ((sd->flags & SD_LOAD_BALANCE) &&
  2429. cpu_isset(busiest_cpu, sd->span))
  2430. break;
  2431. }
  2432. if (likely(sd)) {
  2433. schedstat_inc(sd, alb_cnt);
  2434. if (move_tasks(target_rq, target_cpu, busiest_rq, 1,
  2435. RTPRIO_TO_LOAD_WEIGHT(100), sd, CPU_IDLE,
  2436. NULL))
  2437. schedstat_inc(sd, alb_pushed);
  2438. else
  2439. schedstat_inc(sd, alb_failed);
  2440. }
  2441. spin_unlock(&target_rq->lock);
  2442. }
  2443. #ifdef CONFIG_NO_HZ
  2444. static struct {
  2445. atomic_t load_balancer;
  2446. cpumask_t cpu_mask;
  2447. } nohz ____cacheline_aligned = {
  2448. .load_balancer = ATOMIC_INIT(-1),
  2449. .cpu_mask = CPU_MASK_NONE,
  2450. };
  2451. /*
  2452. * This routine will try to nominate the ilb (idle load balancing)
  2453. * owner among the cpus whose ticks are stopped. ilb owner will do the idle
  2454. * load balancing on behalf of all those cpus. If all the cpus in the system
  2455. * go into this tickless mode, then there will be no ilb owner (as there is
  2456. * no need for one) and all the cpus will sleep till the next wakeup event
  2457. * arrives...
  2458. *
  2459. * For the ilb owner, tick is not stopped. And this tick will be used
  2460. * for idle load balancing. ilb owner will still be part of
  2461. * nohz.cpu_mask..
  2462. *
  2463. * While stopping the tick, this cpu will become the ilb owner if there
  2464. * is no other owner. And will be the owner till that cpu becomes busy
  2465. * or if all cpus in the system stop their ticks at which point
  2466. * there is no need for ilb owner.
  2467. *
  2468. * When the ilb owner becomes busy, it nominates another owner, during the
  2469. * next busy scheduler_tick()
  2470. */
  2471. int select_nohz_load_balancer(int stop_tick)
  2472. {
  2473. int cpu = smp_processor_id();
  2474. if (stop_tick) {
  2475. cpu_set(cpu, nohz.cpu_mask);
  2476. cpu_rq(cpu)->in_nohz_recently = 1;
  2477. /*
  2478. * If we are going offline and still the leader, give up!
  2479. */
  2480. if (cpu_is_offline(cpu) &&
  2481. atomic_read(&nohz.load_balancer) == cpu) {
  2482. if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
  2483. BUG();
  2484. return 0;
  2485. }
  2486. /* time for ilb owner also to sleep */
  2487. if (cpus_weight(nohz.cpu_mask) == num_online_cpus()) {
  2488. if (atomic_read(&nohz.load_balancer) == cpu)
  2489. atomic_set(&nohz.load_balancer, -1);
  2490. return 0;
  2491. }
  2492. if (atomic_read(&nohz.load_balancer) == -1) {
  2493. /* make me the ilb owner */
  2494. if (atomic_cmpxchg(&nohz.load_balancer, -1, cpu) == -1)
  2495. return 1;
  2496. } else if (atomic_read(&nohz.load_balancer) == cpu)
  2497. return 1;
  2498. } else {
  2499. if (!cpu_isset(cpu, nohz.cpu_mask))
  2500. return 0;
  2501. cpu_clear(cpu, nohz.cpu_mask);
  2502. if (atomic_read(&nohz.load_balancer) == cpu)
  2503. if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
  2504. BUG();
  2505. }
  2506. return 0;
  2507. }
  2508. #endif
  2509. static DEFINE_SPINLOCK(balancing);
  2510. /*
  2511. * It checks each scheduling domain to see if it is due to be balanced,
  2512. * and initiates a balancing operation if so.
  2513. *
  2514. * Balancing parameters are set up in arch_init_sched_domains.
  2515. */
  2516. static inline void rebalance_domains(int cpu, enum cpu_idle_type idle)
  2517. {
  2518. int balance = 1;
  2519. struct rq *rq = cpu_rq(cpu);
  2520. unsigned long interval;
  2521. struct sched_domain *sd;
  2522. /* Earliest time when we have to do rebalance again */
  2523. unsigned long next_balance = jiffies + 60*HZ;
  2524. for_each_domain(cpu, sd) {
  2525. if (!(sd->flags & SD_LOAD_BALANCE))
  2526. continue;
  2527. interval = sd->balance_interval;
  2528. if (idle != CPU_IDLE)
  2529. interval *= sd->busy_factor;
  2530. /* scale ms to jiffies */
  2531. interval = msecs_to_jiffies(interval);
  2532. if (unlikely(!interval))
  2533. interval = 1;
  2534. if (interval > HZ*NR_CPUS/10)
  2535. interval = HZ*NR_CPUS/10;
  2536. if (sd->flags & SD_SERIALIZE) {
  2537. if (!spin_trylock(&balancing))
  2538. goto out;
  2539. }
  2540. if (time_after_eq(jiffies, sd->last_balance + interval)) {
  2541. if (load_balance(cpu, rq, sd, idle, &balance)) {
  2542. /*
  2543. * We've pulled tasks over so either we're no
  2544. * longer idle, or one of our SMT siblings is
  2545. * not idle.
  2546. */
  2547. idle = CPU_NOT_IDLE;
  2548. }
  2549. sd->last_balance = jiffies;
  2550. }
  2551. if (sd->flags & SD_SERIALIZE)
  2552. spin_unlock(&balancing);
  2553. out:
  2554. if (time_after(next_balance, sd->last_balance + interval))
  2555. next_balance = sd->last_balance + interval;
  2556. /*
  2557. * Stop the load balance at this level. There is another
  2558. * CPU in our sched group which is doing load balancing more
  2559. * actively.
  2560. */
  2561. if (!balance)
  2562. break;
  2563. }
  2564. rq->next_balance = next_balance;
  2565. }
  2566. /*
  2567. * run_rebalance_domains is triggered when needed from the scheduler tick.
  2568. * In CONFIG_NO_HZ case, the idle load balance owner will do the
  2569. * rebalancing for all the cpus for whom scheduler ticks are stopped.
  2570. */
  2571. static void run_rebalance_domains(struct softirq_action *h)
  2572. {
  2573. int this_cpu = smp_processor_id();
  2574. struct rq *this_rq = cpu_rq(this_cpu);
  2575. enum cpu_idle_type idle = this_rq->idle_at_tick ?
  2576. CPU_IDLE : CPU_NOT_IDLE;
  2577. rebalance_domains(this_cpu, idle);
  2578. #ifdef CONFIG_NO_HZ
  2579. /*
  2580. * If this cpu is the owner for idle load balancing, then do the
  2581. * balancing on behalf of the other idle cpus whose ticks are
  2582. * stopped.
  2583. */
  2584. if (this_rq->idle_at_tick &&
  2585. atomic_read(&nohz.load_balancer) == this_cpu) {
  2586. cpumask_t cpus = nohz.cpu_mask;
  2587. struct rq *rq;
  2588. int balance_cpu;
  2589. cpu_clear(this_cpu, cpus);
  2590. for_each_cpu_mask(balance_cpu, cpus) {
  2591. /*
  2592. * If this cpu gets work to do, stop the load balancing
  2593. * work being done for other cpus. Next load
  2594. * balancing owner will pick it up.
  2595. */
  2596. if (need_resched())
  2597. break;
  2598. rebalance_domains(balance_cpu, SCHED_IDLE);
  2599. rq = cpu_rq(balance_cpu);
  2600. if (time_after(this_rq->next_balance, rq->next_balance))
  2601. this_rq->next_balance = rq->next_balance;
  2602. }
  2603. }
  2604. #endif
  2605. }
  2606. /*
  2607. * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
  2608. *
  2609. * In case of CONFIG_NO_HZ, this is the place where we nominate a new
  2610. * idle load balancing owner or decide to stop the periodic load balancing,
  2611. * if the whole system is idle.
  2612. */
  2613. static inline void trigger_load_balance(struct rq *rq, int cpu)
  2614. {
  2615. #ifdef CONFIG_NO_HZ
  2616. /*
  2617. * If we were in the nohz mode recently and busy at the current
  2618. * scheduler tick, then check if we need to nominate new idle
  2619. * load balancer.
  2620. */
  2621. if (rq->in_nohz_recently && !rq->idle_at_tick) {
  2622. rq->in_nohz_recently = 0;
  2623. if (atomic_read(&nohz.load_balancer) == cpu) {
  2624. cpu_clear(cpu, nohz.cpu_mask);
  2625. atomic_set(&nohz.load_balancer, -1);
  2626. }
  2627. if (atomic_read(&nohz.load_balancer) == -1) {
  2628. /*
  2629. * simple selection for now: Nominate the
  2630. * first cpu in the nohz list to be the next
  2631. * ilb owner.
  2632. *
  2633. * TBD: Traverse the sched domains and nominate
  2634. * the nearest cpu in the nohz.cpu_mask.
  2635. */
  2636. int ilb = first_cpu(nohz.cpu_mask);
  2637. if (ilb != NR_CPUS)
  2638. resched_cpu(ilb);
  2639. }
  2640. }
  2641. /*
  2642. * If this cpu is idle and doing idle load balancing for all the
  2643. * cpus with ticks stopped, is it time for that to stop?
  2644. */
  2645. if (rq->idle_at_tick && atomic_read(&nohz.load_balancer) == cpu &&
  2646. cpus_weight(nohz.cpu_mask) == num_online_cpus()) {
  2647. resched_cpu(cpu);
  2648. return;
  2649. }
  2650. /*
  2651. * If this cpu is idle and the idle load balancing is done by
  2652. * someone else, then no need raise the SCHED_SOFTIRQ
  2653. */
  2654. if (rq->idle_at_tick && atomic_read(&nohz.load_balancer) != cpu &&
  2655. cpu_isset(cpu, nohz.cpu_mask))
  2656. return;
  2657. #endif
  2658. if (time_after_eq(jiffies, rq->next_balance))
  2659. raise_softirq(SCHED_SOFTIRQ);
  2660. }
  2661. #else /* CONFIG_SMP */
  2662. /*
  2663. * on UP we do not need to balance between CPUs:
  2664. */
  2665. static inline void idle_balance(int cpu, struct rq *rq)
  2666. {
  2667. }
  2668. /* Avoid "used but not defined" warning on UP */
  2669. static int balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
  2670. unsigned long max_nr_move, unsigned long max_load_move,
  2671. struct sched_domain *sd, enum cpu_idle_type idle,
  2672. int *all_pinned, unsigned long *load_moved,
  2673. int this_best_prio, int best_prio, int best_prio_seen,
  2674. struct rq_iterator *iterator)
  2675. {
  2676. *load_moved = 0;
  2677. return 0;
  2678. }
  2679. #endif
  2680. DEFINE_PER_CPU(struct kernel_stat, kstat);
  2681. EXPORT_PER_CPU_SYMBOL(kstat);
  2682. /*
  2683. * Return p->sum_exec_runtime plus any more ns on the sched_clock
  2684. * that have not yet been banked in case the task is currently running.
  2685. */
  2686. unsigned long long task_sched_runtime(struct task_struct *p)
  2687. {
  2688. unsigned long flags;
  2689. u64 ns, delta_exec;
  2690. struct rq *rq;
  2691. rq = task_rq_lock(p, &flags);
  2692. ns = p->se.sum_exec_runtime;
  2693. if (rq->curr == p) {
  2694. delta_exec = rq_clock(rq) - p->se.exec_start;
  2695. if ((s64)delta_exec > 0)
  2696. ns += delta_exec;
  2697. }
  2698. task_rq_unlock(rq, &flags);
  2699. return ns;
  2700. }
  2701. /*
  2702. * Account user cpu time to a process.
  2703. * @p: the process that the cpu time gets accounted to
  2704. * @hardirq_offset: the offset to subtract from hardirq_count()
  2705. * @cputime: the cpu time spent in user space since the last update
  2706. */
  2707. void account_user_time(struct task_struct *p, cputime_t cputime)
  2708. {
  2709. struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
  2710. cputime64_t tmp;
  2711. p->utime = cputime_add(p->utime, cputime);
  2712. /* Add user time to cpustat. */
  2713. tmp = cputime_to_cputime64(cputime);
  2714. if (TASK_NICE(p) > 0)
  2715. cpustat->nice = cputime64_add(cpustat->nice, tmp);
  2716. else
  2717. cpustat->user = cputime64_add(cpustat->user, tmp);
  2718. }
  2719. /*
  2720. * Account system cpu time to a process.
  2721. * @p: the process that the cpu time gets accounted to
  2722. * @hardirq_offset: the offset to subtract from hardirq_count()
  2723. * @cputime: the cpu time spent in kernel space since the last update
  2724. */
  2725. void account_system_time(struct task_struct *p, int hardirq_offset,
  2726. cputime_t cputime)
  2727. {
  2728. struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
  2729. struct rq *rq = this_rq();
  2730. cputime64_t tmp;
  2731. p->stime = cputime_add(p->stime, cputime);
  2732. /* Add system time to cpustat. */
  2733. tmp = cputime_to_cputime64(cputime);
  2734. if (hardirq_count() - hardirq_offset)
  2735. cpustat->irq = cputime64_add(cpustat->irq, tmp);
  2736. else if (softirq_count())
  2737. cpustat->softirq = cputime64_add(cpustat->softirq, tmp);
  2738. else if (p != rq->idle)
  2739. cpustat->system = cputime64_add(cpustat->system, tmp);
  2740. else if (atomic_read(&rq->nr_iowait) > 0)
  2741. cpustat->iowait = cputime64_add(cpustat->iowait, tmp);
  2742. else
  2743. cpustat->idle = cputime64_add(cpustat->idle, tmp);
  2744. /* Account for system time used */
  2745. acct_update_integrals(p);
  2746. }
  2747. /*
  2748. * Account for involuntary wait time.
  2749. * @p: the process from which the cpu time has been stolen
  2750. * @steal: the cpu time spent in involuntary wait
  2751. */
  2752. void account_steal_time(struct task_struct *p, cputime_t steal)
  2753. {
  2754. struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
  2755. cputime64_t tmp = cputime_to_cputime64(steal);
  2756. struct rq *rq = this_rq();
  2757. if (p == rq->idle) {
  2758. p->stime = cputime_add(p->stime, steal);
  2759. if (atomic_read(&rq->nr_iowait) > 0)
  2760. cpustat->iowait = cputime64_add(cpustat->iowait, tmp);
  2761. else
  2762. cpustat->idle = cputime64_add(cpustat->idle, tmp);
  2763. } else
  2764. cpustat->steal = cputime64_add(cpustat->steal, tmp);
  2765. }
  2766. /*
  2767. * This function gets called by the timer code, with HZ frequency.
  2768. * We call it with interrupts disabled.
  2769. *
  2770. * It also gets called by the fork code, when changing the parent's
  2771. * timeslices.
  2772. */
  2773. void scheduler_tick(void)
  2774. {
  2775. int cpu = smp_processor_id();
  2776. struct rq *rq = cpu_rq(cpu);
  2777. struct task_struct *curr = rq->curr;
  2778. spin_lock(&rq->lock);
  2779. if (curr != rq->idle) /* FIXME: needed? */
  2780. curr->sched_class->task_tick(rq, curr);
  2781. update_cpu_load(rq);
  2782. spin_unlock(&rq->lock);
  2783. #ifdef CONFIG_SMP
  2784. rq->idle_at_tick = idle_cpu(cpu);
  2785. trigger_load_balance(rq, cpu);
  2786. #endif
  2787. }
  2788. #if defined(CONFIG_PREEMPT) && defined(CONFIG_DEBUG_PREEMPT)
  2789. void fastcall add_preempt_count(int val)
  2790. {
  2791. /*
  2792. * Underflow?
  2793. */
  2794. if (DEBUG_LOCKS_WARN_ON((preempt_count() < 0)))
  2795. return;
  2796. preempt_count() += val;
  2797. /*
  2798. * Spinlock count overflowing soon?
  2799. */
  2800. DEBUG_LOCKS_WARN_ON((preempt_count() & PREEMPT_MASK) >=
  2801. PREEMPT_MASK - 10);
  2802. }
  2803. EXPORT_SYMBOL(add_preempt_count);
  2804. void fastcall sub_preempt_count(int val)
  2805. {
  2806. /*
  2807. * Underflow?
  2808. */
  2809. if (DEBUG_LOCKS_WARN_ON(val > preempt_count()))
  2810. return;
  2811. /*
  2812. * Is the spinlock portion underflowing?
  2813. */
  2814. if (DEBUG_LOCKS_WARN_ON((val < PREEMPT_MASK) &&
  2815. !(preempt_count() & PREEMPT_MASK)))
  2816. return;
  2817. preempt_count() -= val;
  2818. }
  2819. EXPORT_SYMBOL(sub_preempt_count);
  2820. #endif
  2821. /*
  2822. * Print scheduling while atomic bug:
  2823. */
  2824. static noinline void __schedule_bug(struct task_struct *prev)
  2825. {
  2826. printk(KERN_ERR "BUG: scheduling while atomic: %s/0x%08x/%d\n",
  2827. prev->comm, preempt_count(), prev->pid);
  2828. debug_show_held_locks(prev);
  2829. if (irqs_disabled())
  2830. print_irqtrace_events(prev);
  2831. dump_stack();
  2832. }
  2833. /*
  2834. * Various schedule()-time debugging checks and statistics:
  2835. */
  2836. static inline void schedule_debug(struct task_struct *prev)
  2837. {
  2838. /*
  2839. * Test if we are atomic. Since do_exit() needs to call into
  2840. * schedule() atomically, we ignore that path for now.
  2841. * Otherwise, whine if we are scheduling when we should not be.
  2842. */
  2843. if (unlikely(in_atomic_preempt_off()) && unlikely(!prev->exit_state))
  2844. __schedule_bug(prev);
  2845. profile_hit(SCHED_PROFILING, __builtin_return_address(0));
  2846. schedstat_inc(this_rq(), sched_cnt);
  2847. }
  2848. /*
  2849. * Pick up the highest-prio task:
  2850. */
  2851. static inline struct task_struct *
  2852. pick_next_task(struct rq *rq, struct task_struct *prev, u64 now)
  2853. {
  2854. struct sched_class *class;
  2855. struct task_struct *p;
  2856. /*
  2857. * Optimization: we know that if all tasks are in
  2858. * the fair class we can call that function directly:
  2859. */
  2860. if (likely(rq->nr_running == rq->cfs.nr_running)) {
  2861. p = fair_sched_class.pick_next_task(rq, now);
  2862. if (likely(p))
  2863. return p;
  2864. }
  2865. class = sched_class_highest;
  2866. for ( ; ; ) {
  2867. p = class->pick_next_task(rq, now);
  2868. if (p)
  2869. return p;
  2870. /*
  2871. * Will never be NULL as the idle class always
  2872. * returns a non-NULL p:
  2873. */
  2874. class = class->next;
  2875. }
  2876. }
  2877. /*
  2878. * schedule() is the main scheduler function.
  2879. */
  2880. asmlinkage void __sched schedule(void)
  2881. {
  2882. struct task_struct *prev, *next;
  2883. long *switch_count;
  2884. struct rq *rq;
  2885. u64 now;
  2886. int cpu;
  2887. need_resched:
  2888. preempt_disable();
  2889. cpu = smp_processor_id();
  2890. rq = cpu_rq(cpu);
  2891. rcu_qsctr_inc(cpu);
  2892. prev = rq->curr;
  2893. switch_count = &prev->nivcsw;
  2894. release_kernel_lock(prev);
  2895. need_resched_nonpreemptible:
  2896. schedule_debug(prev);
  2897. spin_lock_irq(&rq->lock);
  2898. clear_tsk_need_resched(prev);
  2899. if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
  2900. if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
  2901. unlikely(signal_pending(prev)))) {
  2902. prev->state = TASK_RUNNING;
  2903. } else {
  2904. deactivate_task(rq, prev, 1);
  2905. }
  2906. switch_count = &prev->nvcsw;
  2907. }
  2908. if (unlikely(!rq->nr_running))
  2909. idle_balance(cpu, rq);
  2910. now = __rq_clock(rq);
  2911. prev->sched_class->put_prev_task(rq, prev, now);
  2912. next = pick_next_task(rq, prev, now);
  2913. sched_info_switch(prev, next);
  2914. if (likely(prev != next)) {
  2915. rq->nr_switches++;
  2916. rq->curr = next;
  2917. ++*switch_count;
  2918. context_switch(rq, prev, next); /* unlocks the rq */
  2919. } else
  2920. spin_unlock_irq(&rq->lock);
  2921. if (unlikely(reacquire_kernel_lock(current) < 0)) {
  2922. cpu = smp_processor_id();
  2923. rq = cpu_rq(cpu);
  2924. goto need_resched_nonpreemptible;
  2925. }
  2926. preempt_enable_no_resched();
  2927. if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
  2928. goto need_resched;
  2929. }
  2930. EXPORT_SYMBOL(schedule);
  2931. #ifdef CONFIG_PREEMPT
  2932. /*
  2933. * this is the entry point to schedule() from in-kernel preemption
  2934. * off of preempt_enable. Kernel preemptions off return from interrupt
  2935. * occur there and call schedule directly.
  2936. */
  2937. asmlinkage void __sched preempt_schedule(void)
  2938. {
  2939. struct thread_info *ti = current_thread_info();
  2940. #ifdef CONFIG_PREEMPT_BKL
  2941. struct task_struct *task = current;
  2942. int saved_lock_depth;
  2943. #endif
  2944. /*
  2945. * If there is a non-zero preempt_count or interrupts are disabled,
  2946. * we do not want to preempt the current task. Just return..
  2947. */
  2948. if (likely(ti->preempt_count || irqs_disabled()))
  2949. return;
  2950. need_resched:
  2951. add_preempt_count(PREEMPT_ACTIVE);
  2952. /*
  2953. * We keep the big kernel semaphore locked, but we
  2954. * clear ->lock_depth so that schedule() doesnt
  2955. * auto-release the semaphore:
  2956. */
  2957. #ifdef CONFIG_PREEMPT_BKL
  2958. saved_lock_depth = task->lock_depth;
  2959. task->lock_depth = -1;
  2960. #endif
  2961. schedule();
  2962. #ifdef CONFIG_PREEMPT_BKL
  2963. task->lock_depth = saved_lock_depth;
  2964. #endif
  2965. sub_preempt_count(PREEMPT_ACTIVE);
  2966. /* we could miss a preemption opportunity between schedule and now */
  2967. barrier();
  2968. if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
  2969. goto need_resched;
  2970. }
  2971. EXPORT_SYMBOL(preempt_schedule);
  2972. /*
  2973. * this is the entry point to schedule() from kernel preemption
  2974. * off of irq context.
  2975. * Note, that this is called and return with irqs disabled. This will
  2976. * protect us against recursive calling from irq.
  2977. */
  2978. asmlinkage void __sched preempt_schedule_irq(void)
  2979. {
  2980. struct thread_info *ti = current_thread_info();
  2981. #ifdef CONFIG_PREEMPT_BKL
  2982. struct task_struct *task = current;
  2983. int saved_lock_depth;
  2984. #endif
  2985. /* Catch callers which need to be fixed */
  2986. BUG_ON(ti->preempt_count || !irqs_disabled());
  2987. need_resched:
  2988. add_preempt_count(PREEMPT_ACTIVE);
  2989. /*
  2990. * We keep the big kernel semaphore locked, but we
  2991. * clear ->lock_depth so that schedule() doesnt
  2992. * auto-release the semaphore:
  2993. */
  2994. #ifdef CONFIG_PREEMPT_BKL
  2995. saved_lock_depth = task->lock_depth;
  2996. task->lock_depth = -1;
  2997. #endif
  2998. local_irq_enable();
  2999. schedule();
  3000. local_irq_disable();
  3001. #ifdef CONFIG_PREEMPT_BKL
  3002. task->lock_depth = saved_lock_depth;
  3003. #endif
  3004. sub_preempt_count(PREEMPT_ACTIVE);
  3005. /* we could miss a preemption opportunity between schedule and now */
  3006. barrier();
  3007. if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
  3008. goto need_resched;
  3009. }
  3010. #endif /* CONFIG_PREEMPT */
  3011. int default_wake_function(wait_queue_t *curr, unsigned mode, int sync,
  3012. void *key)
  3013. {
  3014. return try_to_wake_up(curr->private, mode, sync);
  3015. }
  3016. EXPORT_SYMBOL(default_wake_function);
  3017. /*
  3018. * The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
  3019. * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
  3020. * number) then we wake all the non-exclusive tasks and one exclusive task.
  3021. *
  3022. * There are circumstances in which we can try to wake a task which has already
  3023. * started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
  3024. * zero in this (rare) case, and we handle it by continuing to scan the queue.
  3025. */
  3026. static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
  3027. int nr_exclusive, int sync, void *key)
  3028. {
  3029. struct list_head *tmp, *next;
  3030. list_for_each_safe(tmp, next, &q->task_list) {
  3031. wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list);
  3032. unsigned flags = curr->flags;
  3033. if (curr->func(curr, mode, sync, key) &&
  3034. (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
  3035. break;
  3036. }
  3037. }
  3038. /**
  3039. * __wake_up - wake up threads blocked on a waitqueue.
  3040. * @q: the waitqueue
  3041. * @mode: which threads
  3042. * @nr_exclusive: how many wake-one or wake-many threads to wake up
  3043. * @key: is directly passed to the wakeup function
  3044. */
  3045. void fastcall __wake_up(wait_queue_head_t *q, unsigned int mode,
  3046. int nr_exclusive, void *key)
  3047. {
  3048. unsigned long flags;
  3049. spin_lock_irqsave(&q->lock, flags);
  3050. __wake_up_common(q, mode, nr_exclusive, 0, key);
  3051. spin_unlock_irqrestore(&q->lock, flags);
  3052. }
  3053. EXPORT_SYMBOL(__wake_up);
  3054. /*
  3055. * Same as __wake_up but called with the spinlock in wait_queue_head_t held.
  3056. */
  3057. void fastcall __wake_up_locked(wait_queue_head_t *q, unsigned int mode)
  3058. {
  3059. __wake_up_common(q, mode, 1, 0, NULL);
  3060. }
  3061. /**
  3062. * __wake_up_sync - wake up threads blocked on a waitqueue.
  3063. * @q: the waitqueue
  3064. * @mode: which threads
  3065. * @nr_exclusive: how many wake-one or wake-many threads to wake up
  3066. *
  3067. * The sync wakeup differs that the waker knows that it will schedule
  3068. * away soon, so while the target thread will be woken up, it will not
  3069. * be migrated to another CPU - ie. the two threads are 'synchronized'
  3070. * with each other. This can prevent needless bouncing between CPUs.
  3071. *
  3072. * On UP it can prevent extra preemption.
  3073. */
  3074. void fastcall
  3075. __wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
  3076. {
  3077. unsigned long flags;
  3078. int sync = 1;
  3079. if (unlikely(!q))
  3080. return;
  3081. if (unlikely(!nr_exclusive))
  3082. sync = 0;
  3083. spin_lock_irqsave(&q->lock, flags);
  3084. __wake_up_common(q, mode, nr_exclusive, sync, NULL);
  3085. spin_unlock_irqrestore(&q->lock, flags);
  3086. }
  3087. EXPORT_SYMBOL_GPL(__wake_up_sync); /* For internal use only */
  3088. void fastcall complete(struct completion *x)
  3089. {
  3090. unsigned long flags;
  3091. spin_lock_irqsave(&x->wait.lock, flags);
  3092. x->done++;
  3093. __wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE,
  3094. 1, 0, NULL);
  3095. spin_unlock_irqrestore(&x->wait.lock, flags);
  3096. }
  3097. EXPORT_SYMBOL(complete);
  3098. void fastcall complete_all(struct completion *x)
  3099. {
  3100. unsigned long flags;
  3101. spin_lock_irqsave(&x->wait.lock, flags);
  3102. x->done += UINT_MAX/2;
  3103. __wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE,
  3104. 0, 0, NULL);
  3105. spin_unlock_irqrestore(&x->wait.lock, flags);
  3106. }
  3107. EXPORT_SYMBOL(complete_all);
  3108. void fastcall __sched wait_for_completion(struct completion *x)
  3109. {
  3110. might_sleep();
  3111. spin_lock_irq(&x->wait.lock);
  3112. if (!x->done) {
  3113. DECLARE_WAITQUEUE(wait, current);
  3114. wait.flags |= WQ_FLAG_EXCLUSIVE;
  3115. __add_wait_queue_tail(&x->wait, &wait);
  3116. do {
  3117. __set_current_state(TASK_UNINTERRUPTIBLE);
  3118. spin_unlock_irq(&x->wait.lock);
  3119. schedule();
  3120. spin_lock_irq(&x->wait.lock);
  3121. } while (!x->done);
  3122. __remove_wait_queue(&x->wait, &wait);
  3123. }
  3124. x->done--;
  3125. spin_unlock_irq(&x->wait.lock);
  3126. }
  3127. EXPORT_SYMBOL(wait_for_completion);
  3128. unsigned long fastcall __sched
  3129. wait_for_completion_timeout(struct completion *x, unsigned long timeout)
  3130. {
  3131. might_sleep();
  3132. spin_lock_irq(&x->wait.lock);
  3133. if (!x->done) {
  3134. DECLARE_WAITQUEUE(wait, current);
  3135. wait.flags |= WQ_FLAG_EXCLUSIVE;
  3136. __add_wait_queue_tail(&x->wait, &wait);
  3137. do {
  3138. __set_current_state(TASK_UNINTERRUPTIBLE);
  3139. spin_unlock_irq(&x->wait.lock);
  3140. timeout = schedule_timeout(timeout);
  3141. spin_lock_irq(&x->wait.lock);
  3142. if (!timeout) {
  3143. __remove_wait_queue(&x->wait, &wait);
  3144. goto out;
  3145. }
  3146. } while (!x->done);
  3147. __remove_wait_queue(&x->wait, &wait);
  3148. }
  3149. x->done--;
  3150. out:
  3151. spin_unlock_irq(&x->wait.lock);
  3152. return timeout;
  3153. }
  3154. EXPORT_SYMBOL(wait_for_completion_timeout);
  3155. int fastcall __sched wait_for_completion_interruptible(struct completion *x)
  3156. {
  3157. int ret = 0;
  3158. might_sleep();
  3159. spin_lock_irq(&x->wait.lock);
  3160. if (!x->done) {
  3161. DECLARE_WAITQUEUE(wait, current);
  3162. wait.flags |= WQ_FLAG_EXCLUSIVE;
  3163. __add_wait_queue_tail(&x->wait, &wait);
  3164. do {
  3165. if (signal_pending(current)) {
  3166. ret = -ERESTARTSYS;
  3167. __remove_wait_queue(&x->wait, &wait);
  3168. goto out;
  3169. }
  3170. __set_current_state(TASK_INTERRUPTIBLE);
  3171. spin_unlock_irq(&x->wait.lock);
  3172. schedule();
  3173. spin_lock_irq(&x->wait.lock);
  3174. } while (!x->done);
  3175. __remove_wait_queue(&x->wait, &wait);
  3176. }
  3177. x->done--;
  3178. out:
  3179. spin_unlock_irq(&x->wait.lock);
  3180. return ret;
  3181. }
  3182. EXPORT_SYMBOL(wait_for_completion_interruptible);
  3183. unsigned long fastcall __sched
  3184. wait_for_completion_interruptible_timeout(struct completion *x,
  3185. unsigned long timeout)
  3186. {
  3187. might_sleep();
  3188. spin_lock_irq(&x->wait.lock);
  3189. if (!x->done) {
  3190. DECLARE_WAITQUEUE(wait, current);
  3191. wait.flags |= WQ_FLAG_EXCLUSIVE;
  3192. __add_wait_queue_tail(&x->wait, &wait);
  3193. do {
  3194. if (signal_pending(current)) {
  3195. timeout = -ERESTARTSYS;
  3196. __remove_wait_queue(&x->wait, &wait);
  3197. goto out;
  3198. }
  3199. __set_current_state(TASK_INTERRUPTIBLE);
  3200. spin_unlock_irq(&x->wait.lock);
  3201. timeout = schedule_timeout(timeout);
  3202. spin_lock_irq(&x->wait.lock);
  3203. if (!timeout) {
  3204. __remove_wait_queue(&x->wait, &wait);
  3205. goto out;
  3206. }
  3207. } while (!x->done);
  3208. __remove_wait_queue(&x->wait, &wait);
  3209. }
  3210. x->done--;
  3211. out:
  3212. spin_unlock_irq(&x->wait.lock);
  3213. return timeout;
  3214. }
  3215. EXPORT_SYMBOL(wait_for_completion_interruptible_timeout);
  3216. static inline void
  3217. sleep_on_head(wait_queue_head_t *q, wait_queue_t *wait, unsigned long *flags)
  3218. {
  3219. spin_lock_irqsave(&q->lock, *flags);
  3220. __add_wait_queue(q, wait);
  3221. spin_unlock(&q->lock);
  3222. }
  3223. static inline void
  3224. sleep_on_tail(wait_queue_head_t *q, wait_queue_t *wait, unsigned long *flags)
  3225. {
  3226. spin_lock_irq(&q->lock);
  3227. __remove_wait_queue(q, wait);
  3228. spin_unlock_irqrestore(&q->lock, *flags);
  3229. }
  3230. void __sched interruptible_sleep_on(wait_queue_head_t *q)
  3231. {
  3232. unsigned long flags;
  3233. wait_queue_t wait;
  3234. init_waitqueue_entry(&wait, current);
  3235. current->state = TASK_INTERRUPTIBLE;
  3236. sleep_on_head(q, &wait, &flags);
  3237. schedule();
  3238. sleep_on_tail(q, &wait, &flags);
  3239. }
  3240. EXPORT_SYMBOL(interruptible_sleep_on);
  3241. long __sched
  3242. interruptible_sleep_on_timeout(wait_queue_head_t *q, long timeout)
  3243. {
  3244. unsigned long flags;
  3245. wait_queue_t wait;
  3246. init_waitqueue_entry(&wait, current);
  3247. current->state = TASK_INTERRUPTIBLE;
  3248. sleep_on_head(q, &wait, &flags);
  3249. timeout = schedule_timeout(timeout);
  3250. sleep_on_tail(q, &wait, &flags);
  3251. return timeout;
  3252. }
  3253. EXPORT_SYMBOL(interruptible_sleep_on_timeout);
  3254. void __sched sleep_on(wait_queue_head_t *q)
  3255. {
  3256. unsigned long flags;
  3257. wait_queue_t wait;
  3258. init_waitqueue_entry(&wait, current);
  3259. current->state = TASK_UNINTERRUPTIBLE;
  3260. sleep_on_head(q, &wait, &flags);
  3261. schedule();
  3262. sleep_on_tail(q, &wait, &flags);
  3263. }
  3264. EXPORT_SYMBOL(sleep_on);
  3265. long __sched sleep_on_timeout(wait_queue_head_t *q, long timeout)
  3266. {
  3267. unsigned long flags;
  3268. wait_queue_t wait;
  3269. init_waitqueue_entry(&wait, current);
  3270. current->state = TASK_UNINTERRUPTIBLE;
  3271. sleep_on_head(q, &wait, &flags);
  3272. timeout = schedule_timeout(timeout);
  3273. sleep_on_tail(q, &wait, &flags);
  3274. return timeout;
  3275. }
  3276. EXPORT_SYMBOL(sleep_on_timeout);
  3277. #ifdef CONFIG_RT_MUTEXES
  3278. /*
  3279. * rt_mutex_setprio - set the current priority of a task
  3280. * @p: task
  3281. * @prio: prio value (kernel-internal form)
  3282. *
  3283. * This function changes the 'effective' priority of a task. It does
  3284. * not touch ->normal_prio like __setscheduler().
  3285. *
  3286. * Used by the rt_mutex code to implement priority inheritance logic.
  3287. */
  3288. void rt_mutex_setprio(struct task_struct *p, int prio)
  3289. {
  3290. unsigned long flags;
  3291. int oldprio, on_rq;
  3292. struct rq *rq;
  3293. u64 now;
  3294. BUG_ON(prio < 0 || prio > MAX_PRIO);
  3295. rq = task_rq_lock(p, &flags);
  3296. now = rq_clock(rq);
  3297. oldprio = p->prio;
  3298. on_rq = p->se.on_rq;
  3299. if (on_rq)
  3300. dequeue_task(rq, p, 0, now);
  3301. if (rt_prio(prio))
  3302. p->sched_class = &rt_sched_class;
  3303. else
  3304. p->sched_class = &fair_sched_class;
  3305. p->prio = prio;
  3306. if (on_rq) {
  3307. enqueue_task(rq, p, 0, now);
  3308. /*
  3309. * Reschedule if we are currently running on this runqueue and
  3310. * our priority decreased, or if we are not currently running on
  3311. * this runqueue and our priority is higher than the current's
  3312. */
  3313. if (task_running(rq, p)) {
  3314. if (p->prio > oldprio)
  3315. resched_task(rq->curr);
  3316. } else {
  3317. check_preempt_curr(rq, p);
  3318. }
  3319. }
  3320. task_rq_unlock(rq, &flags);
  3321. }
  3322. #endif
  3323. void set_user_nice(struct task_struct *p, long nice)
  3324. {
  3325. int old_prio, delta, on_rq;
  3326. unsigned long flags;
  3327. struct rq *rq;
  3328. u64 now;
  3329. if (TASK_NICE(p) == nice || nice < -20 || nice > 19)
  3330. return;
  3331. /*
  3332. * We have to be careful, if called from sys_setpriority(),
  3333. * the task might be in the middle of scheduling on another CPU.
  3334. */
  3335. rq = task_rq_lock(p, &flags);
  3336. now = rq_clock(rq);
  3337. /*
  3338. * The RT priorities are set via sched_setscheduler(), but we still
  3339. * allow the 'normal' nice value to be set - but as expected
  3340. * it wont have any effect on scheduling until the task is
  3341. * SCHED_FIFO/SCHED_RR:
  3342. */
  3343. if (task_has_rt_policy(p)) {
  3344. p->static_prio = NICE_TO_PRIO(nice);
  3345. goto out_unlock;
  3346. }
  3347. on_rq = p->se.on_rq;
  3348. if (on_rq) {
  3349. dequeue_task(rq, p, 0, now);
  3350. dec_load(rq, p, now);
  3351. }
  3352. p->static_prio = NICE_TO_PRIO(nice);
  3353. set_load_weight(p);
  3354. old_prio = p->prio;
  3355. p->prio = effective_prio(p);
  3356. delta = p->prio - old_prio;
  3357. if (on_rq) {
  3358. enqueue_task(rq, p, 0, now);
  3359. inc_load(rq, p, now);
  3360. /*
  3361. * If the task increased its priority or is running and
  3362. * lowered its priority, then reschedule its CPU:
  3363. */
  3364. if (delta < 0 || (delta > 0 && task_running(rq, p)))
  3365. resched_task(rq->curr);
  3366. }
  3367. out_unlock:
  3368. task_rq_unlock(rq, &flags);
  3369. }
  3370. EXPORT_SYMBOL(set_user_nice);
  3371. /*
  3372. * can_nice - check if a task can reduce its nice value
  3373. * @p: task
  3374. * @nice: nice value
  3375. */
  3376. int can_nice(const struct task_struct *p, const int nice)
  3377. {
  3378. /* convert nice value [19,-20] to rlimit style value [1,40] */
  3379. int nice_rlim = 20 - nice;
  3380. return (nice_rlim <= p->signal->rlim[RLIMIT_NICE].rlim_cur ||
  3381. capable(CAP_SYS_NICE));
  3382. }
  3383. #ifdef __ARCH_WANT_SYS_NICE
  3384. /*
  3385. * sys_nice - change the priority of the current process.
  3386. * @increment: priority increment
  3387. *
  3388. * sys_setpriority is a more generic, but much slower function that
  3389. * does similar things.
  3390. */
  3391. asmlinkage long sys_nice(int increment)
  3392. {
  3393. long nice, retval;
  3394. /*
  3395. * Setpriority might change our priority at the same moment.
  3396. * We don't have to worry. Conceptually one call occurs first
  3397. * and we have a single winner.
  3398. */
  3399. if (increment < -40)
  3400. increment = -40;
  3401. if (increment > 40)
  3402. increment = 40;
  3403. nice = PRIO_TO_NICE(current->static_prio) + increment;
  3404. if (nice < -20)
  3405. nice = -20;
  3406. if (nice > 19)
  3407. nice = 19;
  3408. if (increment < 0 && !can_nice(current, nice))
  3409. return -EPERM;
  3410. retval = security_task_setnice(current, nice);
  3411. if (retval)
  3412. return retval;
  3413. set_user_nice(current, nice);
  3414. return 0;
  3415. }
  3416. #endif
  3417. /**
  3418. * task_prio - return the priority value of a given task.
  3419. * @p: the task in question.
  3420. *
  3421. * This is the priority value as seen by users in /proc.
  3422. * RT tasks are offset by -200. Normal tasks are centered
  3423. * around 0, value goes from -16 to +15.
  3424. */
  3425. int task_prio(const struct task_struct *p)
  3426. {
  3427. return p->prio - MAX_RT_PRIO;
  3428. }
  3429. /**
  3430. * task_nice - return the nice value of a given task.
  3431. * @p: the task in question.
  3432. */
  3433. int task_nice(const struct task_struct *p)
  3434. {
  3435. return TASK_NICE(p);
  3436. }
  3437. EXPORT_SYMBOL_GPL(task_nice);
  3438. /**
  3439. * idle_cpu - is a given cpu idle currently?
  3440. * @cpu: the processor in question.
  3441. */
  3442. int idle_cpu(int cpu)
  3443. {
  3444. return cpu_curr(cpu) == cpu_rq(cpu)->idle;
  3445. }
  3446. /**
  3447. * idle_task - return the idle task for a given cpu.
  3448. * @cpu: the processor in question.
  3449. */
  3450. struct task_struct *idle_task(int cpu)
  3451. {
  3452. return cpu_rq(cpu)->idle;
  3453. }
  3454. /**
  3455. * find_process_by_pid - find a process with a matching PID value.
  3456. * @pid: the pid in question.
  3457. */
  3458. static inline struct task_struct *find_process_by_pid(pid_t pid)
  3459. {
  3460. return pid ? find_task_by_pid(pid) : current;
  3461. }
  3462. /* Actually do priority change: must hold rq lock. */
  3463. static void
  3464. __setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
  3465. {
  3466. BUG_ON(p->se.on_rq);
  3467. p->policy = policy;
  3468. switch (p->policy) {
  3469. case SCHED_NORMAL:
  3470. case SCHED_BATCH:
  3471. case SCHED_IDLE:
  3472. p->sched_class = &fair_sched_class;
  3473. break;
  3474. case SCHED_FIFO:
  3475. case SCHED_RR:
  3476. p->sched_class = &rt_sched_class;
  3477. break;
  3478. }
  3479. p->rt_priority = prio;
  3480. p->normal_prio = normal_prio(p);
  3481. /* we are holding p->pi_lock already */
  3482. p->prio = rt_mutex_getprio(p);
  3483. set_load_weight(p);
  3484. }
  3485. /**
  3486. * sched_setscheduler - change the scheduling policy and/or RT priority of a thread.
  3487. * @p: the task in question.
  3488. * @policy: new policy.
  3489. * @param: structure containing the new RT priority.
  3490. *
  3491. * NOTE that the task may be already dead.
  3492. */
  3493. int sched_setscheduler(struct task_struct *p, int policy,
  3494. struct sched_param *param)
  3495. {
  3496. int retval, oldprio, oldpolicy = -1, on_rq;
  3497. unsigned long flags;
  3498. struct rq *rq;
  3499. /* may grab non-irq protected spin_locks */
  3500. BUG_ON(in_interrupt());
  3501. recheck:
  3502. /* double check policy once rq lock held */
  3503. if (policy < 0)
  3504. policy = oldpolicy = p->policy;
  3505. else if (policy != SCHED_FIFO && policy != SCHED_RR &&
  3506. policy != SCHED_NORMAL && policy != SCHED_BATCH &&
  3507. policy != SCHED_IDLE)
  3508. return -EINVAL;
  3509. /*
  3510. * Valid priorities for SCHED_FIFO and SCHED_RR are
  3511. * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL,
  3512. * SCHED_BATCH and SCHED_IDLE is 0.
  3513. */
  3514. if (param->sched_priority < 0 ||
  3515. (p->mm && param->sched_priority > MAX_USER_RT_PRIO-1) ||
  3516. (!p->mm && param->sched_priority > MAX_RT_PRIO-1))
  3517. return -EINVAL;
  3518. if (rt_policy(policy) != (param->sched_priority != 0))
  3519. return -EINVAL;
  3520. /*
  3521. * Allow unprivileged RT tasks to decrease priority:
  3522. */
  3523. if (!capable(CAP_SYS_NICE)) {
  3524. if (rt_policy(policy)) {
  3525. unsigned long rlim_rtprio;
  3526. if (!lock_task_sighand(p, &flags))
  3527. return -ESRCH;
  3528. rlim_rtprio = p->signal->rlim[RLIMIT_RTPRIO].rlim_cur;
  3529. unlock_task_sighand(p, &flags);
  3530. /* can't set/change the rt policy */
  3531. if (policy != p->policy && !rlim_rtprio)
  3532. return -EPERM;
  3533. /* can't increase priority */
  3534. if (param->sched_priority > p->rt_priority &&
  3535. param->sched_priority > rlim_rtprio)
  3536. return -EPERM;
  3537. }
  3538. /*
  3539. * Like positive nice levels, dont allow tasks to
  3540. * move out of SCHED_IDLE either:
  3541. */
  3542. if (p->policy == SCHED_IDLE && policy != SCHED_IDLE)
  3543. return -EPERM;
  3544. /* can't change other user's priorities */
  3545. if ((current->euid != p->euid) &&
  3546. (current->euid != p->uid))
  3547. return -EPERM;
  3548. }
  3549. retval = security_task_setscheduler(p, policy, param);
  3550. if (retval)
  3551. return retval;
  3552. /*
  3553. * make sure no PI-waiters arrive (or leave) while we are
  3554. * changing the priority of the task:
  3555. */
  3556. spin_lock_irqsave(&p->pi_lock, flags);
  3557. /*
  3558. * To be able to change p->policy safely, the apropriate
  3559. * runqueue lock must be held.
  3560. */
  3561. rq = __task_rq_lock(p);
  3562. /* recheck policy now with rq lock held */
  3563. if (unlikely(oldpolicy != -1 && oldpolicy != p->policy)) {
  3564. policy = oldpolicy = -1;
  3565. __task_rq_unlock(rq);
  3566. spin_unlock_irqrestore(&p->pi_lock, flags);
  3567. goto recheck;
  3568. }
  3569. on_rq = p->se.on_rq;
  3570. if (on_rq)
  3571. deactivate_task(rq, p, 0);
  3572. oldprio = p->prio;
  3573. __setscheduler(rq, p, policy, param->sched_priority);
  3574. if (on_rq) {
  3575. activate_task(rq, p, 0);
  3576. /*
  3577. * Reschedule if we are currently running on this runqueue and
  3578. * our priority decreased, or if we are not currently running on
  3579. * this runqueue and our priority is higher than the current's
  3580. */
  3581. if (task_running(rq, p)) {
  3582. if (p->prio > oldprio)
  3583. resched_task(rq->curr);
  3584. } else {
  3585. check_preempt_curr(rq, p);
  3586. }
  3587. }
  3588. __task_rq_unlock(rq);
  3589. spin_unlock_irqrestore(&p->pi_lock, flags);
  3590. rt_mutex_adjust_pi(p);
  3591. return 0;
  3592. }
  3593. EXPORT_SYMBOL_GPL(sched_setscheduler);
  3594. static int
  3595. do_sched_setscheduler(pid_t pid, int policy, struct sched_param __user *param)
  3596. {
  3597. struct sched_param lparam;
  3598. struct task_struct *p;
  3599. int retval;
  3600. if (!param || pid < 0)
  3601. return -EINVAL;
  3602. if (copy_from_user(&lparam, param, sizeof(struct sched_param)))
  3603. return -EFAULT;
  3604. rcu_read_lock();
  3605. retval = -ESRCH;
  3606. p = find_process_by_pid(pid);
  3607. if (p != NULL)
  3608. retval = sched_setscheduler(p, policy, &lparam);
  3609. rcu_read_unlock();
  3610. return retval;
  3611. }
  3612. /**
  3613. * sys_sched_setscheduler - set/change the scheduler policy and RT priority
  3614. * @pid: the pid in question.
  3615. * @policy: new policy.
  3616. * @param: structure containing the new RT priority.
  3617. */
  3618. asmlinkage long sys_sched_setscheduler(pid_t pid, int policy,
  3619. struct sched_param __user *param)
  3620. {
  3621. /* negative values for policy are not valid */
  3622. if (policy < 0)
  3623. return -EINVAL;
  3624. return do_sched_setscheduler(pid, policy, param);
  3625. }
  3626. /**
  3627. * sys_sched_setparam - set/change the RT priority of a thread
  3628. * @pid: the pid in question.
  3629. * @param: structure containing the new RT priority.
  3630. */
  3631. asmlinkage long sys_sched_setparam(pid_t pid, struct sched_param __user *param)
  3632. {
  3633. return do_sched_setscheduler(pid, -1, param);
  3634. }
  3635. /**
  3636. * sys_sched_getscheduler - get the policy (scheduling class) of a thread
  3637. * @pid: the pid in question.
  3638. */
  3639. asmlinkage long sys_sched_getscheduler(pid_t pid)
  3640. {
  3641. struct task_struct *p;
  3642. int retval = -EINVAL;
  3643. if (pid < 0)
  3644. goto out_nounlock;
  3645. retval = -ESRCH;
  3646. read_lock(&tasklist_lock);
  3647. p = find_process_by_pid(pid);
  3648. if (p) {
  3649. retval = security_task_getscheduler(p);
  3650. if (!retval)
  3651. retval = p->policy;
  3652. }
  3653. read_unlock(&tasklist_lock);
  3654. out_nounlock:
  3655. return retval;
  3656. }
  3657. /**
  3658. * sys_sched_getscheduler - get the RT priority of a thread
  3659. * @pid: the pid in question.
  3660. * @param: structure containing the RT priority.
  3661. */
  3662. asmlinkage long sys_sched_getparam(pid_t pid, struct sched_param __user *param)
  3663. {
  3664. struct sched_param lp;
  3665. struct task_struct *p;
  3666. int retval = -EINVAL;
  3667. if (!param || pid < 0)
  3668. goto out_nounlock;
  3669. read_lock(&tasklist_lock);
  3670. p = find_process_by_pid(pid);
  3671. retval = -ESRCH;
  3672. if (!p)
  3673. goto out_unlock;
  3674. retval = security_task_getscheduler(p);
  3675. if (retval)
  3676. goto out_unlock;
  3677. lp.sched_priority = p->rt_priority;
  3678. read_unlock(&tasklist_lock);
  3679. /*
  3680. * This one might sleep, we cannot do it with a spinlock held ...
  3681. */
  3682. retval = copy_to_user(param, &lp, sizeof(*param)) ? -EFAULT : 0;
  3683. out_nounlock:
  3684. return retval;
  3685. out_unlock:
  3686. read_unlock(&tasklist_lock);
  3687. return retval;
  3688. }
  3689. long sched_setaffinity(pid_t pid, cpumask_t new_mask)
  3690. {
  3691. cpumask_t cpus_allowed;
  3692. struct task_struct *p;
  3693. int retval;
  3694. mutex_lock(&sched_hotcpu_mutex);
  3695. read_lock(&tasklist_lock);
  3696. p = find_process_by_pid(pid);
  3697. if (!p) {
  3698. read_unlock(&tasklist_lock);
  3699. mutex_unlock(&sched_hotcpu_mutex);
  3700. return -ESRCH;
  3701. }
  3702. /*
  3703. * It is not safe to call set_cpus_allowed with the
  3704. * tasklist_lock held. We will bump the task_struct's
  3705. * usage count and then drop tasklist_lock.
  3706. */
  3707. get_task_struct(p);
  3708. read_unlock(&tasklist_lock);
  3709. retval = -EPERM;
  3710. if ((current->euid != p->euid) && (current->euid != p->uid) &&
  3711. !capable(CAP_SYS_NICE))
  3712. goto out_unlock;
  3713. retval = security_task_setscheduler(p, 0, NULL);
  3714. if (retval)
  3715. goto out_unlock;
  3716. cpus_allowed = cpuset_cpus_allowed(p);
  3717. cpus_and(new_mask, new_mask, cpus_allowed);
  3718. retval = set_cpus_allowed(p, new_mask);
  3719. out_unlock:
  3720. put_task_struct(p);
  3721. mutex_unlock(&sched_hotcpu_mutex);
  3722. return retval;
  3723. }
  3724. static int get_user_cpu_mask(unsigned long __user *user_mask_ptr, unsigned len,
  3725. cpumask_t *new_mask)
  3726. {
  3727. if (len < sizeof(cpumask_t)) {
  3728. memset(new_mask, 0, sizeof(cpumask_t));
  3729. } else if (len > sizeof(cpumask_t)) {
  3730. len = sizeof(cpumask_t);
  3731. }
  3732. return copy_from_user(new_mask, user_mask_ptr, len) ? -EFAULT : 0;
  3733. }
  3734. /**
  3735. * sys_sched_setaffinity - set the cpu affinity of a process
  3736. * @pid: pid of the process
  3737. * @len: length in bytes of the bitmask pointed to by user_mask_ptr
  3738. * @user_mask_ptr: user-space pointer to the new cpu mask
  3739. */
  3740. asmlinkage long sys_sched_setaffinity(pid_t pid, unsigned int len,
  3741. unsigned long __user *user_mask_ptr)
  3742. {
  3743. cpumask_t new_mask;
  3744. int retval;
  3745. retval = get_user_cpu_mask(user_mask_ptr, len, &new_mask);
  3746. if (retval)
  3747. return retval;
  3748. return sched_setaffinity(pid, new_mask);
  3749. }
  3750. /*
  3751. * Represents all cpu's present in the system
  3752. * In systems capable of hotplug, this map could dynamically grow
  3753. * as new cpu's are detected in the system via any platform specific
  3754. * method, such as ACPI for e.g.
  3755. */
  3756. cpumask_t cpu_present_map __read_mostly;
  3757. EXPORT_SYMBOL(cpu_present_map);
  3758. #ifndef CONFIG_SMP
  3759. cpumask_t cpu_online_map __read_mostly = CPU_MASK_ALL;
  3760. EXPORT_SYMBOL(cpu_online_map);
  3761. cpumask_t cpu_possible_map __read_mostly = CPU_MASK_ALL;
  3762. EXPORT_SYMBOL(cpu_possible_map);
  3763. #endif
  3764. long sched_getaffinity(pid_t pid, cpumask_t *mask)
  3765. {
  3766. struct task_struct *p;
  3767. int retval;
  3768. mutex_lock(&sched_hotcpu_mutex);
  3769. read_lock(&tasklist_lock);
  3770. retval = -ESRCH;
  3771. p = find_process_by_pid(pid);
  3772. if (!p)
  3773. goto out_unlock;
  3774. retval = security_task_getscheduler(p);
  3775. if (retval)
  3776. goto out_unlock;
  3777. cpus_and(*mask, p->cpus_allowed, cpu_online_map);
  3778. out_unlock:
  3779. read_unlock(&tasklist_lock);
  3780. mutex_unlock(&sched_hotcpu_mutex);
  3781. if (retval)
  3782. return retval;
  3783. return 0;
  3784. }
  3785. /**
  3786. * sys_sched_getaffinity - get the cpu affinity of a process
  3787. * @pid: pid of the process
  3788. * @len: length in bytes of the bitmask pointed to by user_mask_ptr
  3789. * @user_mask_ptr: user-space pointer to hold the current cpu mask
  3790. */
  3791. asmlinkage long sys_sched_getaffinity(pid_t pid, unsigned int len,
  3792. unsigned long __user *user_mask_ptr)
  3793. {
  3794. int ret;
  3795. cpumask_t mask;
  3796. if (len < sizeof(cpumask_t))
  3797. return -EINVAL;
  3798. ret = sched_getaffinity(pid, &mask);
  3799. if (ret < 0)
  3800. return ret;
  3801. if (copy_to_user(user_mask_ptr, &mask, sizeof(cpumask_t)))
  3802. return -EFAULT;
  3803. return sizeof(cpumask_t);
  3804. }
  3805. /**
  3806. * sys_sched_yield - yield the current processor to other threads.
  3807. *
  3808. * This function yields the current CPU to other tasks. If there are no
  3809. * other threads running on this CPU then this function will return.
  3810. */
  3811. asmlinkage long sys_sched_yield(void)
  3812. {
  3813. struct rq *rq = this_rq_lock();
  3814. schedstat_inc(rq, yld_cnt);
  3815. if (unlikely(rq->nr_running == 1))
  3816. schedstat_inc(rq, yld_act_empty);
  3817. else
  3818. current->sched_class->yield_task(rq, current);
  3819. /*
  3820. * Since we are going to call schedule() anyway, there's
  3821. * no need to preempt or enable interrupts:
  3822. */
  3823. __release(rq->lock);
  3824. spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
  3825. _raw_spin_unlock(&rq->lock);
  3826. preempt_enable_no_resched();
  3827. schedule();
  3828. return 0;
  3829. }
  3830. static void __cond_resched(void)
  3831. {
  3832. #ifdef CONFIG_DEBUG_SPINLOCK_SLEEP
  3833. __might_sleep(__FILE__, __LINE__);
  3834. #endif
  3835. /*
  3836. * The BKS might be reacquired before we have dropped
  3837. * PREEMPT_ACTIVE, which could trigger a second
  3838. * cond_resched() call.
  3839. */
  3840. do {
  3841. add_preempt_count(PREEMPT_ACTIVE);
  3842. schedule();
  3843. sub_preempt_count(PREEMPT_ACTIVE);
  3844. } while (need_resched());
  3845. }
  3846. int __sched cond_resched(void)
  3847. {
  3848. if (need_resched() && !(preempt_count() & PREEMPT_ACTIVE) &&
  3849. system_state == SYSTEM_RUNNING) {
  3850. __cond_resched();
  3851. return 1;
  3852. }
  3853. return 0;
  3854. }
  3855. EXPORT_SYMBOL(cond_resched);
  3856. /*
  3857. * cond_resched_lock() - if a reschedule is pending, drop the given lock,
  3858. * call schedule, and on return reacquire the lock.
  3859. *
  3860. * This works OK both with and without CONFIG_PREEMPT. We do strange low-level
  3861. * operations here to prevent schedule() from being called twice (once via
  3862. * spin_unlock(), once by hand).
  3863. */
  3864. int cond_resched_lock(spinlock_t *lock)
  3865. {
  3866. int ret = 0;
  3867. if (need_lockbreak(lock)) {
  3868. spin_unlock(lock);
  3869. cpu_relax();
  3870. ret = 1;
  3871. spin_lock(lock);
  3872. }
  3873. if (need_resched() && system_state == SYSTEM_RUNNING) {
  3874. spin_release(&lock->dep_map, 1, _THIS_IP_);
  3875. _raw_spin_unlock(lock);
  3876. preempt_enable_no_resched();
  3877. __cond_resched();
  3878. ret = 1;
  3879. spin_lock(lock);
  3880. }
  3881. return ret;
  3882. }
  3883. EXPORT_SYMBOL(cond_resched_lock);
  3884. int __sched cond_resched_softirq(void)
  3885. {
  3886. BUG_ON(!in_softirq());
  3887. if (need_resched() && system_state == SYSTEM_RUNNING) {
  3888. local_bh_enable();
  3889. __cond_resched();
  3890. local_bh_disable();
  3891. return 1;
  3892. }
  3893. return 0;
  3894. }
  3895. EXPORT_SYMBOL(cond_resched_softirq);
  3896. /**
  3897. * yield - yield the current processor to other threads.
  3898. *
  3899. * This is a shortcut for kernel-space yielding - it marks the
  3900. * thread runnable and calls sys_sched_yield().
  3901. */
  3902. void __sched yield(void)
  3903. {
  3904. set_current_state(TASK_RUNNING);
  3905. sys_sched_yield();
  3906. }
  3907. EXPORT_SYMBOL(yield);
  3908. /*
  3909. * This task is about to go to sleep on IO. Increment rq->nr_iowait so
  3910. * that process accounting knows that this is a task in IO wait state.
  3911. *
  3912. * But don't do that if it is a deliberate, throttling IO wait (this task
  3913. * has set its backing_dev_info: the queue against which it should throttle)
  3914. */
  3915. void __sched io_schedule(void)
  3916. {
  3917. struct rq *rq = &__raw_get_cpu_var(runqueues);
  3918. delayacct_blkio_start();
  3919. atomic_inc(&rq->nr_iowait);
  3920. schedule();
  3921. atomic_dec(&rq->nr_iowait);
  3922. delayacct_blkio_end();
  3923. }
  3924. EXPORT_SYMBOL(io_schedule);
  3925. long __sched io_schedule_timeout(long timeout)
  3926. {
  3927. struct rq *rq = &__raw_get_cpu_var(runqueues);
  3928. long ret;
  3929. delayacct_blkio_start();
  3930. atomic_inc(&rq->nr_iowait);
  3931. ret = schedule_timeout(timeout);
  3932. atomic_dec(&rq->nr_iowait);
  3933. delayacct_blkio_end();
  3934. return ret;
  3935. }
  3936. /**
  3937. * sys_sched_get_priority_max - return maximum RT priority.
  3938. * @policy: scheduling class.
  3939. *
  3940. * this syscall returns the maximum rt_priority that can be used
  3941. * by a given scheduling class.
  3942. */
  3943. asmlinkage long sys_sched_get_priority_max(int policy)
  3944. {
  3945. int ret = -EINVAL;
  3946. switch (policy) {
  3947. case SCHED_FIFO:
  3948. case SCHED_RR:
  3949. ret = MAX_USER_RT_PRIO-1;
  3950. break;
  3951. case SCHED_NORMAL:
  3952. case SCHED_BATCH:
  3953. case SCHED_IDLE:
  3954. ret = 0;
  3955. break;
  3956. }
  3957. return ret;
  3958. }
  3959. /**
  3960. * sys_sched_get_priority_min - return minimum RT priority.
  3961. * @policy: scheduling class.
  3962. *
  3963. * this syscall returns the minimum rt_priority that can be used
  3964. * by a given scheduling class.
  3965. */
  3966. asmlinkage long sys_sched_get_priority_min(int policy)
  3967. {
  3968. int ret = -EINVAL;
  3969. switch (policy) {
  3970. case SCHED_FIFO:
  3971. case SCHED_RR:
  3972. ret = 1;
  3973. break;
  3974. case SCHED_NORMAL:
  3975. case SCHED_BATCH:
  3976. case SCHED_IDLE:
  3977. ret = 0;
  3978. }
  3979. return ret;
  3980. }
  3981. /**
  3982. * sys_sched_rr_get_interval - return the default timeslice of a process.
  3983. * @pid: pid of the process.
  3984. * @interval: userspace pointer to the timeslice value.
  3985. *
  3986. * this syscall writes the default timeslice value of a given process
  3987. * into the user-space timespec buffer. A value of '0' means infinity.
  3988. */
  3989. asmlinkage
  3990. long sys_sched_rr_get_interval(pid_t pid, struct timespec __user *interval)
  3991. {
  3992. struct task_struct *p;
  3993. int retval = -EINVAL;
  3994. struct timespec t;
  3995. if (pid < 0)
  3996. goto out_nounlock;
  3997. retval = -ESRCH;
  3998. read_lock(&tasklist_lock);
  3999. p = find_process_by_pid(pid);
  4000. if (!p)
  4001. goto out_unlock;
  4002. retval = security_task_getscheduler(p);
  4003. if (retval)
  4004. goto out_unlock;
  4005. jiffies_to_timespec(p->policy == SCHED_FIFO ?
  4006. 0 : static_prio_timeslice(p->static_prio), &t);
  4007. read_unlock(&tasklist_lock);
  4008. retval = copy_to_user(interval, &t, sizeof(t)) ? -EFAULT : 0;
  4009. out_nounlock:
  4010. return retval;
  4011. out_unlock:
  4012. read_unlock(&tasklist_lock);
  4013. return retval;
  4014. }
  4015. static const char stat_nam[] = "RSDTtZX";
  4016. static void show_task(struct task_struct *p)
  4017. {
  4018. unsigned long free = 0;
  4019. unsigned state;
  4020. state = p->state ? __ffs(p->state) + 1 : 0;
  4021. printk("%-13.13s %c", p->comm,
  4022. state < sizeof(stat_nam) - 1 ? stat_nam[state] : '?');
  4023. #if BITS_PER_LONG == 32
  4024. if (state == TASK_RUNNING)
  4025. printk(" running ");
  4026. else
  4027. printk(" %08lx ", thread_saved_pc(p));
  4028. #else
  4029. if (state == TASK_RUNNING)
  4030. printk(" running task ");
  4031. else
  4032. printk(" %016lx ", thread_saved_pc(p));
  4033. #endif
  4034. #ifdef CONFIG_DEBUG_STACK_USAGE
  4035. {
  4036. unsigned long *n = end_of_stack(p);
  4037. while (!*n)
  4038. n++;
  4039. free = (unsigned long)n - (unsigned long)end_of_stack(p);
  4040. }
  4041. #endif
  4042. printk("%5lu %5d %6d\n", free, p->pid, p->parent->pid);
  4043. if (state != TASK_RUNNING)
  4044. show_stack(p, NULL);
  4045. }
  4046. void show_state_filter(unsigned long state_filter)
  4047. {
  4048. struct task_struct *g, *p;
  4049. #if BITS_PER_LONG == 32
  4050. printk(KERN_INFO
  4051. " task PC stack pid father\n");
  4052. #else
  4053. printk(KERN_INFO
  4054. " task PC stack pid father\n");
  4055. #endif
  4056. read_lock(&tasklist_lock);
  4057. do_each_thread(g, p) {
  4058. /*
  4059. * reset the NMI-timeout, listing all files on a slow
  4060. * console might take alot of time:
  4061. */
  4062. touch_nmi_watchdog();
  4063. if (!state_filter || (p->state & state_filter))
  4064. show_task(p);
  4065. } while_each_thread(g, p);
  4066. touch_all_softlockup_watchdogs();
  4067. #ifdef CONFIG_SCHED_DEBUG
  4068. sysrq_sched_debug_show();
  4069. #endif
  4070. read_unlock(&tasklist_lock);
  4071. /*
  4072. * Only show locks if all tasks are dumped:
  4073. */
  4074. if (state_filter == -1)
  4075. debug_show_all_locks();
  4076. }
  4077. void __cpuinit init_idle_bootup_task(struct task_struct *idle)
  4078. {
  4079. idle->sched_class = &idle_sched_class;
  4080. }
  4081. /**
  4082. * init_idle - set up an idle thread for a given CPU
  4083. * @idle: task in question
  4084. * @cpu: cpu the idle task belongs to
  4085. *
  4086. * NOTE: this function does not set the idle thread's NEED_RESCHED
  4087. * flag, to make booting more robust.
  4088. */
  4089. void __cpuinit init_idle(struct task_struct *idle, int cpu)
  4090. {
  4091. struct rq *rq = cpu_rq(cpu);
  4092. unsigned long flags;
  4093. __sched_fork(idle);
  4094. idle->se.exec_start = sched_clock();
  4095. idle->prio = idle->normal_prio = MAX_PRIO;
  4096. idle->cpus_allowed = cpumask_of_cpu(cpu);
  4097. __set_task_cpu(idle, cpu);
  4098. spin_lock_irqsave(&rq->lock, flags);
  4099. rq->curr = rq->idle = idle;
  4100. #if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
  4101. idle->oncpu = 1;
  4102. #endif
  4103. spin_unlock_irqrestore(&rq->lock, flags);
  4104. /* Set the preempt count _outside_ the spinlocks! */
  4105. #if defined(CONFIG_PREEMPT) && !defined(CONFIG_PREEMPT_BKL)
  4106. task_thread_info(idle)->preempt_count = (idle->lock_depth >= 0);
  4107. #else
  4108. task_thread_info(idle)->preempt_count = 0;
  4109. #endif
  4110. /*
  4111. * The idle tasks have their own, simple scheduling class:
  4112. */
  4113. idle->sched_class = &idle_sched_class;
  4114. }
  4115. /*
  4116. * In a system that switches off the HZ timer nohz_cpu_mask
  4117. * indicates which cpus entered this state. This is used
  4118. * in the rcu update to wait only for active cpus. For system
  4119. * which do not switch off the HZ timer nohz_cpu_mask should
  4120. * always be CPU_MASK_NONE.
  4121. */
  4122. cpumask_t nohz_cpu_mask = CPU_MASK_NONE;
  4123. /*
  4124. * Increase the granularity value when there are more CPUs,
  4125. * because with more CPUs the 'effective latency' as visible
  4126. * to users decreases. But the relationship is not linear,
  4127. * so pick a second-best guess by going with the log2 of the
  4128. * number of CPUs.
  4129. *
  4130. * This idea comes from the SD scheduler of Con Kolivas:
  4131. */
  4132. static inline void sched_init_granularity(void)
  4133. {
  4134. unsigned int factor = 1 + ilog2(num_online_cpus());
  4135. const unsigned long gran_limit = 100000000;
  4136. sysctl_sched_granularity *= factor;
  4137. if (sysctl_sched_granularity > gran_limit)
  4138. sysctl_sched_granularity = gran_limit;
  4139. sysctl_sched_runtime_limit = sysctl_sched_granularity * 4;
  4140. sysctl_sched_wakeup_granularity = sysctl_sched_granularity / 2;
  4141. }
  4142. #ifdef CONFIG_SMP
  4143. /*
  4144. * This is how migration works:
  4145. *
  4146. * 1) we queue a struct migration_req structure in the source CPU's
  4147. * runqueue and wake up that CPU's migration thread.
  4148. * 2) we down() the locked semaphore => thread blocks.
  4149. * 3) migration thread wakes up (implicitly it forces the migrated
  4150. * thread off the CPU)
  4151. * 4) it gets the migration request and checks whether the migrated
  4152. * task is still in the wrong runqueue.
  4153. * 5) if it's in the wrong runqueue then the migration thread removes
  4154. * it and puts it into the right queue.
  4155. * 6) migration thread up()s the semaphore.
  4156. * 7) we wake up and the migration is done.
  4157. */
  4158. /*
  4159. * Change a given task's CPU affinity. Migrate the thread to a
  4160. * proper CPU and schedule it away if the CPU it's executing on
  4161. * is removed from the allowed bitmask.
  4162. *
  4163. * NOTE: the caller must have a valid reference to the task, the
  4164. * task must not exit() & deallocate itself prematurely. The
  4165. * call is not atomic; no spinlocks may be held.
  4166. */
  4167. int set_cpus_allowed(struct task_struct *p, cpumask_t new_mask)
  4168. {
  4169. struct migration_req req;
  4170. unsigned long flags;
  4171. struct rq *rq;
  4172. int ret = 0;
  4173. rq = task_rq_lock(p, &flags);
  4174. if (!cpus_intersects(new_mask, cpu_online_map)) {
  4175. ret = -EINVAL;
  4176. goto out;
  4177. }
  4178. p->cpus_allowed = new_mask;
  4179. /* Can the task run on the task's current CPU? If so, we're done */
  4180. if (cpu_isset(task_cpu(p), new_mask))
  4181. goto out;
  4182. if (migrate_task(p, any_online_cpu(new_mask), &req)) {
  4183. /* Need help from migration thread: drop lock and wait. */
  4184. task_rq_unlock(rq, &flags);
  4185. wake_up_process(rq->migration_thread);
  4186. wait_for_completion(&req.done);
  4187. tlb_migrate_finish(p->mm);
  4188. return 0;
  4189. }
  4190. out:
  4191. task_rq_unlock(rq, &flags);
  4192. return ret;
  4193. }
  4194. EXPORT_SYMBOL_GPL(set_cpus_allowed);
  4195. /*
  4196. * Move (not current) task off this cpu, onto dest cpu. We're doing
  4197. * this because either it can't run here any more (set_cpus_allowed()
  4198. * away from this CPU, or CPU going down), or because we're
  4199. * attempting to rebalance this task on exec (sched_exec).
  4200. *
  4201. * So we race with normal scheduler movements, but that's OK, as long
  4202. * as the task is no longer on this CPU.
  4203. *
  4204. * Returns non-zero if task was successfully migrated.
  4205. */
  4206. static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
  4207. {
  4208. struct rq *rq_dest, *rq_src;
  4209. int ret = 0, on_rq;
  4210. if (unlikely(cpu_is_offline(dest_cpu)))
  4211. return ret;
  4212. rq_src = cpu_rq(src_cpu);
  4213. rq_dest = cpu_rq(dest_cpu);
  4214. double_rq_lock(rq_src, rq_dest);
  4215. /* Already moved. */
  4216. if (task_cpu(p) != src_cpu)
  4217. goto out;
  4218. /* Affinity changed (again). */
  4219. if (!cpu_isset(dest_cpu, p->cpus_allowed))
  4220. goto out;
  4221. on_rq = p->se.on_rq;
  4222. if (on_rq)
  4223. deactivate_task(rq_src, p, 0);
  4224. set_task_cpu(p, dest_cpu);
  4225. if (on_rq) {
  4226. activate_task(rq_dest, p, 0);
  4227. check_preempt_curr(rq_dest, p);
  4228. }
  4229. ret = 1;
  4230. out:
  4231. double_rq_unlock(rq_src, rq_dest);
  4232. return ret;
  4233. }
  4234. /*
  4235. * migration_thread - this is a highprio system thread that performs
  4236. * thread migration by bumping thread off CPU then 'pushing' onto
  4237. * another runqueue.
  4238. */
  4239. static int migration_thread(void *data)
  4240. {
  4241. int cpu = (long)data;
  4242. struct rq *rq;
  4243. rq = cpu_rq(cpu);
  4244. BUG_ON(rq->migration_thread != current);
  4245. set_current_state(TASK_INTERRUPTIBLE);
  4246. while (!kthread_should_stop()) {
  4247. struct migration_req *req;
  4248. struct list_head *head;
  4249. spin_lock_irq(&rq->lock);
  4250. if (cpu_is_offline(cpu)) {
  4251. spin_unlock_irq(&rq->lock);
  4252. goto wait_to_die;
  4253. }
  4254. if (rq->active_balance) {
  4255. active_load_balance(rq, cpu);
  4256. rq->active_balance = 0;
  4257. }
  4258. head = &rq->migration_queue;
  4259. if (list_empty(head)) {
  4260. spin_unlock_irq(&rq->lock);
  4261. schedule();
  4262. set_current_state(TASK_INTERRUPTIBLE);
  4263. continue;
  4264. }
  4265. req = list_entry(head->next, struct migration_req, list);
  4266. list_del_init(head->next);
  4267. spin_unlock(&rq->lock);
  4268. __migrate_task(req->task, cpu, req->dest_cpu);
  4269. local_irq_enable();
  4270. complete(&req->done);
  4271. }
  4272. __set_current_state(TASK_RUNNING);
  4273. return 0;
  4274. wait_to_die:
  4275. /* Wait for kthread_stop */
  4276. set_current_state(TASK_INTERRUPTIBLE);
  4277. while (!kthread_should_stop()) {
  4278. schedule();
  4279. set_current_state(TASK_INTERRUPTIBLE);
  4280. }
  4281. __set_current_state(TASK_RUNNING);
  4282. return 0;
  4283. }
  4284. #ifdef CONFIG_HOTPLUG_CPU
  4285. /*
  4286. * Figure out where task on dead CPU should go, use force if neccessary.
  4287. * NOTE: interrupts should be disabled by the caller
  4288. */
  4289. static void move_task_off_dead_cpu(int dead_cpu, struct task_struct *p)
  4290. {
  4291. unsigned long flags;
  4292. cpumask_t mask;
  4293. struct rq *rq;
  4294. int dest_cpu;
  4295. restart:
  4296. /* On same node? */
  4297. mask = node_to_cpumask(cpu_to_node(dead_cpu));
  4298. cpus_and(mask, mask, p->cpus_allowed);
  4299. dest_cpu = any_online_cpu(mask);
  4300. /* On any allowed CPU? */
  4301. if (dest_cpu == NR_CPUS)
  4302. dest_cpu = any_online_cpu(p->cpus_allowed);
  4303. /* No more Mr. Nice Guy. */
  4304. if (dest_cpu == NR_CPUS) {
  4305. rq = task_rq_lock(p, &flags);
  4306. cpus_setall(p->cpus_allowed);
  4307. dest_cpu = any_online_cpu(p->cpus_allowed);
  4308. task_rq_unlock(rq, &flags);
  4309. /*
  4310. * Don't tell them about moving exiting tasks or
  4311. * kernel threads (both mm NULL), since they never
  4312. * leave kernel.
  4313. */
  4314. if (p->mm && printk_ratelimit())
  4315. printk(KERN_INFO "process %d (%s) no "
  4316. "longer affine to cpu%d\n",
  4317. p->pid, p->comm, dead_cpu);
  4318. }
  4319. if (!__migrate_task(p, dead_cpu, dest_cpu))
  4320. goto restart;
  4321. }
  4322. /*
  4323. * While a dead CPU has no uninterruptible tasks queued at this point,
  4324. * it might still have a nonzero ->nr_uninterruptible counter, because
  4325. * for performance reasons the counter is not stricly tracking tasks to
  4326. * their home CPUs. So we just add the counter to another CPU's counter,
  4327. * to keep the global sum constant after CPU-down:
  4328. */
  4329. static void migrate_nr_uninterruptible(struct rq *rq_src)
  4330. {
  4331. struct rq *rq_dest = cpu_rq(any_online_cpu(CPU_MASK_ALL));
  4332. unsigned long flags;
  4333. local_irq_save(flags);
  4334. double_rq_lock(rq_src, rq_dest);
  4335. rq_dest->nr_uninterruptible += rq_src->nr_uninterruptible;
  4336. rq_src->nr_uninterruptible = 0;
  4337. double_rq_unlock(rq_src, rq_dest);
  4338. local_irq_restore(flags);
  4339. }
  4340. /* Run through task list and migrate tasks from the dead cpu. */
  4341. static void migrate_live_tasks(int src_cpu)
  4342. {
  4343. struct task_struct *p, *t;
  4344. write_lock_irq(&tasklist_lock);
  4345. do_each_thread(t, p) {
  4346. if (p == current)
  4347. continue;
  4348. if (task_cpu(p) == src_cpu)
  4349. move_task_off_dead_cpu(src_cpu, p);
  4350. } while_each_thread(t, p);
  4351. write_unlock_irq(&tasklist_lock);
  4352. }
  4353. /*
  4354. * Schedules idle task to be the next runnable task on current CPU.
  4355. * It does so by boosting its priority to highest possible and adding it to
  4356. * the _front_ of the runqueue. Used by CPU offline code.
  4357. */
  4358. void sched_idle_next(void)
  4359. {
  4360. int this_cpu = smp_processor_id();
  4361. struct rq *rq = cpu_rq(this_cpu);
  4362. struct task_struct *p = rq->idle;
  4363. unsigned long flags;
  4364. /* cpu has to be offline */
  4365. BUG_ON(cpu_online(this_cpu));
  4366. /*
  4367. * Strictly not necessary since rest of the CPUs are stopped by now
  4368. * and interrupts disabled on the current cpu.
  4369. */
  4370. spin_lock_irqsave(&rq->lock, flags);
  4371. __setscheduler(rq, p, SCHED_FIFO, MAX_RT_PRIO-1);
  4372. /* Add idle task to the _front_ of its priority queue: */
  4373. activate_idle_task(p, rq);
  4374. spin_unlock_irqrestore(&rq->lock, flags);
  4375. }
  4376. /*
  4377. * Ensures that the idle task is using init_mm right before its cpu goes
  4378. * offline.
  4379. */
  4380. void idle_task_exit(void)
  4381. {
  4382. struct mm_struct *mm = current->active_mm;
  4383. BUG_ON(cpu_online(smp_processor_id()));
  4384. if (mm != &init_mm)
  4385. switch_mm(mm, &init_mm, current);
  4386. mmdrop(mm);
  4387. }
  4388. /* called under rq->lock with disabled interrupts */
  4389. static void migrate_dead(unsigned int dead_cpu, struct task_struct *p)
  4390. {
  4391. struct rq *rq = cpu_rq(dead_cpu);
  4392. /* Must be exiting, otherwise would be on tasklist. */
  4393. BUG_ON(p->exit_state != EXIT_ZOMBIE && p->exit_state != EXIT_DEAD);
  4394. /* Cannot have done final schedule yet: would have vanished. */
  4395. BUG_ON(p->state == TASK_DEAD);
  4396. get_task_struct(p);
  4397. /*
  4398. * Drop lock around migration; if someone else moves it,
  4399. * that's OK. No task can be added to this CPU, so iteration is
  4400. * fine.
  4401. * NOTE: interrupts should be left disabled --dev@
  4402. */
  4403. spin_unlock(&rq->lock);
  4404. move_task_off_dead_cpu(dead_cpu, p);
  4405. spin_lock(&rq->lock);
  4406. put_task_struct(p);
  4407. }
  4408. /* release_task() removes task from tasklist, so we won't find dead tasks. */
  4409. static void migrate_dead_tasks(unsigned int dead_cpu)
  4410. {
  4411. struct rq *rq = cpu_rq(dead_cpu);
  4412. struct task_struct *next;
  4413. for ( ; ; ) {
  4414. if (!rq->nr_running)
  4415. break;
  4416. next = pick_next_task(rq, rq->curr, rq_clock(rq));
  4417. if (!next)
  4418. break;
  4419. migrate_dead(dead_cpu, next);
  4420. }
  4421. }
  4422. #endif /* CONFIG_HOTPLUG_CPU */
  4423. /*
  4424. * migration_call - callback that gets triggered when a CPU is added.
  4425. * Here we can start up the necessary migration thread for the new CPU.
  4426. */
  4427. static int __cpuinit
  4428. migration_call(struct notifier_block *nfb, unsigned long action, void *hcpu)
  4429. {
  4430. struct task_struct *p;
  4431. int cpu = (long)hcpu;
  4432. unsigned long flags;
  4433. struct rq *rq;
  4434. switch (action) {
  4435. case CPU_LOCK_ACQUIRE:
  4436. mutex_lock(&sched_hotcpu_mutex);
  4437. break;
  4438. case CPU_UP_PREPARE:
  4439. case CPU_UP_PREPARE_FROZEN:
  4440. p = kthread_create(migration_thread, hcpu, "migration/%d", cpu);
  4441. if (IS_ERR(p))
  4442. return NOTIFY_BAD;
  4443. kthread_bind(p, cpu);
  4444. /* Must be high prio: stop_machine expects to yield to it. */
  4445. rq = task_rq_lock(p, &flags);
  4446. __setscheduler(rq, p, SCHED_FIFO, MAX_RT_PRIO-1);
  4447. task_rq_unlock(rq, &flags);
  4448. cpu_rq(cpu)->migration_thread = p;
  4449. break;
  4450. case CPU_ONLINE:
  4451. case CPU_ONLINE_FROZEN:
  4452. /* Strictly unneccessary, as first user will wake it. */
  4453. wake_up_process(cpu_rq(cpu)->migration_thread);
  4454. break;
  4455. #ifdef CONFIG_HOTPLUG_CPU
  4456. case CPU_UP_CANCELED:
  4457. case CPU_UP_CANCELED_FROZEN:
  4458. if (!cpu_rq(cpu)->migration_thread)
  4459. break;
  4460. /* Unbind it from offline cpu so it can run. Fall thru. */
  4461. kthread_bind(cpu_rq(cpu)->migration_thread,
  4462. any_online_cpu(cpu_online_map));
  4463. kthread_stop(cpu_rq(cpu)->migration_thread);
  4464. cpu_rq(cpu)->migration_thread = NULL;
  4465. break;
  4466. case CPU_DEAD:
  4467. case CPU_DEAD_FROZEN:
  4468. migrate_live_tasks(cpu);
  4469. rq = cpu_rq(cpu);
  4470. kthread_stop(rq->migration_thread);
  4471. rq->migration_thread = NULL;
  4472. /* Idle task back to normal (off runqueue, low prio) */
  4473. rq = task_rq_lock(rq->idle, &flags);
  4474. deactivate_task(rq, rq->idle, 0);
  4475. rq->idle->static_prio = MAX_PRIO;
  4476. __setscheduler(rq, rq->idle, SCHED_NORMAL, 0);
  4477. rq->idle->sched_class = &idle_sched_class;
  4478. migrate_dead_tasks(cpu);
  4479. task_rq_unlock(rq, &flags);
  4480. migrate_nr_uninterruptible(rq);
  4481. BUG_ON(rq->nr_running != 0);
  4482. /* No need to migrate the tasks: it was best-effort if
  4483. * they didn't take sched_hotcpu_mutex. Just wake up
  4484. * the requestors. */
  4485. spin_lock_irq(&rq->lock);
  4486. while (!list_empty(&rq->migration_queue)) {
  4487. struct migration_req *req;
  4488. req = list_entry(rq->migration_queue.next,
  4489. struct migration_req, list);
  4490. list_del_init(&req->list);
  4491. complete(&req->done);
  4492. }
  4493. spin_unlock_irq(&rq->lock);
  4494. break;
  4495. #endif
  4496. case CPU_LOCK_RELEASE:
  4497. mutex_unlock(&sched_hotcpu_mutex);
  4498. break;
  4499. }
  4500. return NOTIFY_OK;
  4501. }
  4502. /* Register at highest priority so that task migration (migrate_all_tasks)
  4503. * happens before everything else.
  4504. */
  4505. static struct notifier_block __cpuinitdata migration_notifier = {
  4506. .notifier_call = migration_call,
  4507. .priority = 10
  4508. };
  4509. int __init migration_init(void)
  4510. {
  4511. void *cpu = (void *)(long)smp_processor_id();
  4512. int err;
  4513. /* Start one for the boot CPU: */
  4514. err = migration_call(&migration_notifier, CPU_UP_PREPARE, cpu);
  4515. BUG_ON(err == NOTIFY_BAD);
  4516. migration_call(&migration_notifier, CPU_ONLINE, cpu);
  4517. register_cpu_notifier(&migration_notifier);
  4518. return 0;
  4519. }
  4520. #endif
  4521. #ifdef CONFIG_SMP
  4522. /* Number of possible processor ids */
  4523. int nr_cpu_ids __read_mostly = NR_CPUS;
  4524. EXPORT_SYMBOL(nr_cpu_ids);
  4525. #undef SCHED_DOMAIN_DEBUG
  4526. #ifdef SCHED_DOMAIN_DEBUG
  4527. static void sched_domain_debug(struct sched_domain *sd, int cpu)
  4528. {
  4529. int level = 0;
  4530. if (!sd) {
  4531. printk(KERN_DEBUG "CPU%d attaching NULL sched-domain.\n", cpu);
  4532. return;
  4533. }
  4534. printk(KERN_DEBUG "CPU%d attaching sched-domain:\n", cpu);
  4535. do {
  4536. int i;
  4537. char str[NR_CPUS];
  4538. struct sched_group *group = sd->groups;
  4539. cpumask_t groupmask;
  4540. cpumask_scnprintf(str, NR_CPUS, sd->span);
  4541. cpus_clear(groupmask);
  4542. printk(KERN_DEBUG);
  4543. for (i = 0; i < level + 1; i++)
  4544. printk(" ");
  4545. printk("domain %d: ", level);
  4546. if (!(sd->flags & SD_LOAD_BALANCE)) {
  4547. printk("does not load-balance\n");
  4548. if (sd->parent)
  4549. printk(KERN_ERR "ERROR: !SD_LOAD_BALANCE domain"
  4550. " has parent");
  4551. break;
  4552. }
  4553. printk("span %s\n", str);
  4554. if (!cpu_isset(cpu, sd->span))
  4555. printk(KERN_ERR "ERROR: domain->span does not contain "
  4556. "CPU%d\n", cpu);
  4557. if (!cpu_isset(cpu, group->cpumask))
  4558. printk(KERN_ERR "ERROR: domain->groups does not contain"
  4559. " CPU%d\n", cpu);
  4560. printk(KERN_DEBUG);
  4561. for (i = 0; i < level + 2; i++)
  4562. printk(" ");
  4563. printk("groups:");
  4564. do {
  4565. if (!group) {
  4566. printk("\n");
  4567. printk(KERN_ERR "ERROR: group is NULL\n");
  4568. break;
  4569. }
  4570. if (!group->__cpu_power) {
  4571. printk("\n");
  4572. printk(KERN_ERR "ERROR: domain->cpu_power not "
  4573. "set\n");
  4574. }
  4575. if (!cpus_weight(group->cpumask)) {
  4576. printk("\n");
  4577. printk(KERN_ERR "ERROR: empty group\n");
  4578. }
  4579. if (cpus_intersects(groupmask, group->cpumask)) {
  4580. printk("\n");
  4581. printk(KERN_ERR "ERROR: repeated CPUs\n");
  4582. }
  4583. cpus_or(groupmask, groupmask, group->cpumask);
  4584. cpumask_scnprintf(str, NR_CPUS, group->cpumask);
  4585. printk(" %s", str);
  4586. group = group->next;
  4587. } while (group != sd->groups);
  4588. printk("\n");
  4589. if (!cpus_equal(sd->span, groupmask))
  4590. printk(KERN_ERR "ERROR: groups don't span "
  4591. "domain->span\n");
  4592. level++;
  4593. sd = sd->parent;
  4594. if (!sd)
  4595. continue;
  4596. if (!cpus_subset(groupmask, sd->span))
  4597. printk(KERN_ERR "ERROR: parent span is not a superset "
  4598. "of domain->span\n");
  4599. } while (sd);
  4600. }
  4601. #else
  4602. # define sched_domain_debug(sd, cpu) do { } while (0)
  4603. #endif
  4604. static int sd_degenerate(struct sched_domain *sd)
  4605. {
  4606. if (cpus_weight(sd->span) == 1)
  4607. return 1;
  4608. /* Following flags need at least 2 groups */
  4609. if (sd->flags & (SD_LOAD_BALANCE |
  4610. SD_BALANCE_NEWIDLE |
  4611. SD_BALANCE_FORK |
  4612. SD_BALANCE_EXEC |
  4613. SD_SHARE_CPUPOWER |
  4614. SD_SHARE_PKG_RESOURCES)) {
  4615. if (sd->groups != sd->groups->next)
  4616. return 0;
  4617. }
  4618. /* Following flags don't use groups */
  4619. if (sd->flags & (SD_WAKE_IDLE |
  4620. SD_WAKE_AFFINE |
  4621. SD_WAKE_BALANCE))
  4622. return 0;
  4623. return 1;
  4624. }
  4625. static int
  4626. sd_parent_degenerate(struct sched_domain *sd, struct sched_domain *parent)
  4627. {
  4628. unsigned long cflags = sd->flags, pflags = parent->flags;
  4629. if (sd_degenerate(parent))
  4630. return 1;
  4631. if (!cpus_equal(sd->span, parent->span))
  4632. return 0;
  4633. /* Does parent contain flags not in child? */
  4634. /* WAKE_BALANCE is a subset of WAKE_AFFINE */
  4635. if (cflags & SD_WAKE_AFFINE)
  4636. pflags &= ~SD_WAKE_BALANCE;
  4637. /* Flags needing groups don't count if only 1 group in parent */
  4638. if (parent->groups == parent->groups->next) {
  4639. pflags &= ~(SD_LOAD_BALANCE |
  4640. SD_BALANCE_NEWIDLE |
  4641. SD_BALANCE_FORK |
  4642. SD_BALANCE_EXEC |
  4643. SD_SHARE_CPUPOWER |
  4644. SD_SHARE_PKG_RESOURCES);
  4645. }
  4646. if (~cflags & pflags)
  4647. return 0;
  4648. return 1;
  4649. }
  4650. /*
  4651. * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
  4652. * hold the hotplug lock.
  4653. */
  4654. static void cpu_attach_domain(struct sched_domain *sd, int cpu)
  4655. {
  4656. struct rq *rq = cpu_rq(cpu);
  4657. struct sched_domain *tmp;
  4658. /* Remove the sched domains which do not contribute to scheduling. */
  4659. for (tmp = sd; tmp; tmp = tmp->parent) {
  4660. struct sched_domain *parent = tmp->parent;
  4661. if (!parent)
  4662. break;
  4663. if (sd_parent_degenerate(tmp, parent)) {
  4664. tmp->parent = parent->parent;
  4665. if (parent->parent)
  4666. parent->parent->child = tmp;
  4667. }
  4668. }
  4669. if (sd && sd_degenerate(sd)) {
  4670. sd = sd->parent;
  4671. if (sd)
  4672. sd->child = NULL;
  4673. }
  4674. sched_domain_debug(sd, cpu);
  4675. rcu_assign_pointer(rq->sd, sd);
  4676. }
  4677. /* cpus with isolated domains */
  4678. static cpumask_t cpu_isolated_map = CPU_MASK_NONE;
  4679. /* Setup the mask of cpus configured for isolated domains */
  4680. static int __init isolated_cpu_setup(char *str)
  4681. {
  4682. int ints[NR_CPUS], i;
  4683. str = get_options(str, ARRAY_SIZE(ints), ints);
  4684. cpus_clear(cpu_isolated_map);
  4685. for (i = 1; i <= ints[0]; i++)
  4686. if (ints[i] < NR_CPUS)
  4687. cpu_set(ints[i], cpu_isolated_map);
  4688. return 1;
  4689. }
  4690. __setup ("isolcpus=", isolated_cpu_setup);
  4691. /*
  4692. * init_sched_build_groups takes the cpumask we wish to span, and a pointer
  4693. * to a function which identifies what group(along with sched group) a CPU
  4694. * belongs to. The return value of group_fn must be a >= 0 and < NR_CPUS
  4695. * (due to the fact that we keep track of groups covered with a cpumask_t).
  4696. *
  4697. * init_sched_build_groups will build a circular linked list of the groups
  4698. * covered by the given span, and will set each group's ->cpumask correctly,
  4699. * and ->cpu_power to 0.
  4700. */
  4701. static void
  4702. init_sched_build_groups(cpumask_t span, const cpumask_t *cpu_map,
  4703. int (*group_fn)(int cpu, const cpumask_t *cpu_map,
  4704. struct sched_group **sg))
  4705. {
  4706. struct sched_group *first = NULL, *last = NULL;
  4707. cpumask_t covered = CPU_MASK_NONE;
  4708. int i;
  4709. for_each_cpu_mask(i, span) {
  4710. struct sched_group *sg;
  4711. int group = group_fn(i, cpu_map, &sg);
  4712. int j;
  4713. if (cpu_isset(i, covered))
  4714. continue;
  4715. sg->cpumask = CPU_MASK_NONE;
  4716. sg->__cpu_power = 0;
  4717. for_each_cpu_mask(j, span) {
  4718. if (group_fn(j, cpu_map, NULL) != group)
  4719. continue;
  4720. cpu_set(j, covered);
  4721. cpu_set(j, sg->cpumask);
  4722. }
  4723. if (!first)
  4724. first = sg;
  4725. if (last)
  4726. last->next = sg;
  4727. last = sg;
  4728. }
  4729. last->next = first;
  4730. }
  4731. #define SD_NODES_PER_DOMAIN 16
  4732. #ifdef CONFIG_NUMA
  4733. /**
  4734. * find_next_best_node - find the next node to include in a sched_domain
  4735. * @node: node whose sched_domain we're building
  4736. * @used_nodes: nodes already in the sched_domain
  4737. *
  4738. * Find the next node to include in a given scheduling domain. Simply
  4739. * finds the closest node not already in the @used_nodes map.
  4740. *
  4741. * Should use nodemask_t.
  4742. */
  4743. static int find_next_best_node(int node, unsigned long *used_nodes)
  4744. {
  4745. int i, n, val, min_val, best_node = 0;
  4746. min_val = INT_MAX;
  4747. for (i = 0; i < MAX_NUMNODES; i++) {
  4748. /* Start at @node */
  4749. n = (node + i) % MAX_NUMNODES;
  4750. if (!nr_cpus_node(n))
  4751. continue;
  4752. /* Skip already used nodes */
  4753. if (test_bit(n, used_nodes))
  4754. continue;
  4755. /* Simple min distance search */
  4756. val = node_distance(node, n);
  4757. if (val < min_val) {
  4758. min_val = val;
  4759. best_node = n;
  4760. }
  4761. }
  4762. set_bit(best_node, used_nodes);
  4763. return best_node;
  4764. }
  4765. /**
  4766. * sched_domain_node_span - get a cpumask for a node's sched_domain
  4767. * @node: node whose cpumask we're constructing
  4768. * @size: number of nodes to include in this span
  4769. *
  4770. * Given a node, construct a good cpumask for its sched_domain to span. It
  4771. * should be one that prevents unnecessary balancing, but also spreads tasks
  4772. * out optimally.
  4773. */
  4774. static cpumask_t sched_domain_node_span(int node)
  4775. {
  4776. DECLARE_BITMAP(used_nodes, MAX_NUMNODES);
  4777. cpumask_t span, nodemask;
  4778. int i;
  4779. cpus_clear(span);
  4780. bitmap_zero(used_nodes, MAX_NUMNODES);
  4781. nodemask = node_to_cpumask(node);
  4782. cpus_or(span, span, nodemask);
  4783. set_bit(node, used_nodes);
  4784. for (i = 1; i < SD_NODES_PER_DOMAIN; i++) {
  4785. int next_node = find_next_best_node(node, used_nodes);
  4786. nodemask = node_to_cpumask(next_node);
  4787. cpus_or(span, span, nodemask);
  4788. }
  4789. return span;
  4790. }
  4791. #endif
  4792. int sched_smt_power_savings = 0, sched_mc_power_savings = 0;
  4793. /*
  4794. * SMT sched-domains:
  4795. */
  4796. #ifdef CONFIG_SCHED_SMT
  4797. static DEFINE_PER_CPU(struct sched_domain, cpu_domains);
  4798. static DEFINE_PER_CPU(struct sched_group, sched_group_cpus);
  4799. static int cpu_to_cpu_group(int cpu, const cpumask_t *cpu_map,
  4800. struct sched_group **sg)
  4801. {
  4802. if (sg)
  4803. *sg = &per_cpu(sched_group_cpus, cpu);
  4804. return cpu;
  4805. }
  4806. #endif
  4807. /*
  4808. * multi-core sched-domains:
  4809. */
  4810. #ifdef CONFIG_SCHED_MC
  4811. static DEFINE_PER_CPU(struct sched_domain, core_domains);
  4812. static DEFINE_PER_CPU(struct sched_group, sched_group_core);
  4813. #endif
  4814. #if defined(CONFIG_SCHED_MC) && defined(CONFIG_SCHED_SMT)
  4815. static int cpu_to_core_group(int cpu, const cpumask_t *cpu_map,
  4816. struct sched_group **sg)
  4817. {
  4818. int group;
  4819. cpumask_t mask = cpu_sibling_map[cpu];
  4820. cpus_and(mask, mask, *cpu_map);
  4821. group = first_cpu(mask);
  4822. if (sg)
  4823. *sg = &per_cpu(sched_group_core, group);
  4824. return group;
  4825. }
  4826. #elif defined(CONFIG_SCHED_MC)
  4827. static int cpu_to_core_group(int cpu, const cpumask_t *cpu_map,
  4828. struct sched_group **sg)
  4829. {
  4830. if (sg)
  4831. *sg = &per_cpu(sched_group_core, cpu);
  4832. return cpu;
  4833. }
  4834. #endif
  4835. static DEFINE_PER_CPU(struct sched_domain, phys_domains);
  4836. static DEFINE_PER_CPU(struct sched_group, sched_group_phys);
  4837. static int cpu_to_phys_group(int cpu, const cpumask_t *cpu_map,
  4838. struct sched_group **sg)
  4839. {
  4840. int group;
  4841. #ifdef CONFIG_SCHED_MC
  4842. cpumask_t mask = cpu_coregroup_map(cpu);
  4843. cpus_and(mask, mask, *cpu_map);
  4844. group = first_cpu(mask);
  4845. #elif defined(CONFIG_SCHED_SMT)
  4846. cpumask_t mask = cpu_sibling_map[cpu];
  4847. cpus_and(mask, mask, *cpu_map);
  4848. group = first_cpu(mask);
  4849. #else
  4850. group = cpu;
  4851. #endif
  4852. if (sg)
  4853. *sg = &per_cpu(sched_group_phys, group);
  4854. return group;
  4855. }
  4856. #ifdef CONFIG_NUMA
  4857. /*
  4858. * The init_sched_build_groups can't handle what we want to do with node
  4859. * groups, so roll our own. Now each node has its own list of groups which
  4860. * gets dynamically allocated.
  4861. */
  4862. static DEFINE_PER_CPU(struct sched_domain, node_domains);
  4863. static struct sched_group **sched_group_nodes_bycpu[NR_CPUS];
  4864. static DEFINE_PER_CPU(struct sched_domain, allnodes_domains);
  4865. static DEFINE_PER_CPU(struct sched_group, sched_group_allnodes);
  4866. static int cpu_to_allnodes_group(int cpu, const cpumask_t *cpu_map,
  4867. struct sched_group **sg)
  4868. {
  4869. cpumask_t nodemask = node_to_cpumask(cpu_to_node(cpu));
  4870. int group;
  4871. cpus_and(nodemask, nodemask, *cpu_map);
  4872. group = first_cpu(nodemask);
  4873. if (sg)
  4874. *sg = &per_cpu(sched_group_allnodes, group);
  4875. return group;
  4876. }
  4877. static void init_numa_sched_groups_power(struct sched_group *group_head)
  4878. {
  4879. struct sched_group *sg = group_head;
  4880. int j;
  4881. if (!sg)
  4882. return;
  4883. next_sg:
  4884. for_each_cpu_mask(j, sg->cpumask) {
  4885. struct sched_domain *sd;
  4886. sd = &per_cpu(phys_domains, j);
  4887. if (j != first_cpu(sd->groups->cpumask)) {
  4888. /*
  4889. * Only add "power" once for each
  4890. * physical package.
  4891. */
  4892. continue;
  4893. }
  4894. sg_inc_cpu_power(sg, sd->groups->__cpu_power);
  4895. }
  4896. sg = sg->next;
  4897. if (sg != group_head)
  4898. goto next_sg;
  4899. }
  4900. #endif
  4901. #ifdef CONFIG_NUMA
  4902. /* Free memory allocated for various sched_group structures */
  4903. static void free_sched_groups(const cpumask_t *cpu_map)
  4904. {
  4905. int cpu, i;
  4906. for_each_cpu_mask(cpu, *cpu_map) {
  4907. struct sched_group **sched_group_nodes
  4908. = sched_group_nodes_bycpu[cpu];
  4909. if (!sched_group_nodes)
  4910. continue;
  4911. for (i = 0; i < MAX_NUMNODES; i++) {
  4912. cpumask_t nodemask = node_to_cpumask(i);
  4913. struct sched_group *oldsg, *sg = sched_group_nodes[i];
  4914. cpus_and(nodemask, nodemask, *cpu_map);
  4915. if (cpus_empty(nodemask))
  4916. continue;
  4917. if (sg == NULL)
  4918. continue;
  4919. sg = sg->next;
  4920. next_sg:
  4921. oldsg = sg;
  4922. sg = sg->next;
  4923. kfree(oldsg);
  4924. if (oldsg != sched_group_nodes[i])
  4925. goto next_sg;
  4926. }
  4927. kfree(sched_group_nodes);
  4928. sched_group_nodes_bycpu[cpu] = NULL;
  4929. }
  4930. }
  4931. #else
  4932. static void free_sched_groups(const cpumask_t *cpu_map)
  4933. {
  4934. }
  4935. #endif
  4936. /*
  4937. * Initialize sched groups cpu_power.
  4938. *
  4939. * cpu_power indicates the capacity of sched group, which is used while
  4940. * distributing the load between different sched groups in a sched domain.
  4941. * Typically cpu_power for all the groups in a sched domain will be same unless
  4942. * there are asymmetries in the topology. If there are asymmetries, group
  4943. * having more cpu_power will pickup more load compared to the group having
  4944. * less cpu_power.
  4945. *
  4946. * cpu_power will be a multiple of SCHED_LOAD_SCALE. This multiple represents
  4947. * the maximum number of tasks a group can handle in the presence of other idle
  4948. * or lightly loaded groups in the same sched domain.
  4949. */
  4950. static void init_sched_groups_power(int cpu, struct sched_domain *sd)
  4951. {
  4952. struct sched_domain *child;
  4953. struct sched_group *group;
  4954. WARN_ON(!sd || !sd->groups);
  4955. if (cpu != first_cpu(sd->groups->cpumask))
  4956. return;
  4957. child = sd->child;
  4958. sd->groups->__cpu_power = 0;
  4959. /*
  4960. * For perf policy, if the groups in child domain share resources
  4961. * (for example cores sharing some portions of the cache hierarchy
  4962. * or SMT), then set this domain groups cpu_power such that each group
  4963. * can handle only one task, when there are other idle groups in the
  4964. * same sched domain.
  4965. */
  4966. if (!child || (!(sd->flags & SD_POWERSAVINGS_BALANCE) &&
  4967. (child->flags &
  4968. (SD_SHARE_CPUPOWER | SD_SHARE_PKG_RESOURCES)))) {
  4969. sg_inc_cpu_power(sd->groups, SCHED_LOAD_SCALE);
  4970. return;
  4971. }
  4972. /*
  4973. * add cpu_power of each child group to this groups cpu_power
  4974. */
  4975. group = child->groups;
  4976. do {
  4977. sg_inc_cpu_power(sd->groups, group->__cpu_power);
  4978. group = group->next;
  4979. } while (group != child->groups);
  4980. }
  4981. /*
  4982. * Build sched domains for a given set of cpus and attach the sched domains
  4983. * to the individual cpus
  4984. */
  4985. static int build_sched_domains(const cpumask_t *cpu_map)
  4986. {
  4987. int i;
  4988. #ifdef CONFIG_NUMA
  4989. struct sched_group **sched_group_nodes = NULL;
  4990. int sd_allnodes = 0;
  4991. /*
  4992. * Allocate the per-node list of sched groups
  4993. */
  4994. sched_group_nodes = kzalloc(sizeof(struct sched_group *)*MAX_NUMNODES,
  4995. GFP_KERNEL);
  4996. if (!sched_group_nodes) {
  4997. printk(KERN_WARNING "Can not alloc sched group node list\n");
  4998. return -ENOMEM;
  4999. }
  5000. sched_group_nodes_bycpu[first_cpu(*cpu_map)] = sched_group_nodes;
  5001. #endif
  5002. /*
  5003. * Set up domains for cpus specified by the cpu_map.
  5004. */
  5005. for_each_cpu_mask(i, *cpu_map) {
  5006. struct sched_domain *sd = NULL, *p;
  5007. cpumask_t nodemask = node_to_cpumask(cpu_to_node(i));
  5008. cpus_and(nodemask, nodemask, *cpu_map);
  5009. #ifdef CONFIG_NUMA
  5010. if (cpus_weight(*cpu_map) >
  5011. SD_NODES_PER_DOMAIN*cpus_weight(nodemask)) {
  5012. sd = &per_cpu(allnodes_domains, i);
  5013. *sd = SD_ALLNODES_INIT;
  5014. sd->span = *cpu_map;
  5015. cpu_to_allnodes_group(i, cpu_map, &sd->groups);
  5016. p = sd;
  5017. sd_allnodes = 1;
  5018. } else
  5019. p = NULL;
  5020. sd = &per_cpu(node_domains, i);
  5021. *sd = SD_NODE_INIT;
  5022. sd->span = sched_domain_node_span(cpu_to_node(i));
  5023. sd->parent = p;
  5024. if (p)
  5025. p->child = sd;
  5026. cpus_and(sd->span, sd->span, *cpu_map);
  5027. #endif
  5028. p = sd;
  5029. sd = &per_cpu(phys_domains, i);
  5030. *sd = SD_CPU_INIT;
  5031. sd->span = nodemask;
  5032. sd->parent = p;
  5033. if (p)
  5034. p->child = sd;
  5035. cpu_to_phys_group(i, cpu_map, &sd->groups);
  5036. #ifdef CONFIG_SCHED_MC
  5037. p = sd;
  5038. sd = &per_cpu(core_domains, i);
  5039. *sd = SD_MC_INIT;
  5040. sd->span = cpu_coregroup_map(i);
  5041. cpus_and(sd->span, sd->span, *cpu_map);
  5042. sd->parent = p;
  5043. p->child = sd;
  5044. cpu_to_core_group(i, cpu_map, &sd->groups);
  5045. #endif
  5046. #ifdef CONFIG_SCHED_SMT
  5047. p = sd;
  5048. sd = &per_cpu(cpu_domains, i);
  5049. *sd = SD_SIBLING_INIT;
  5050. sd->span = cpu_sibling_map[i];
  5051. cpus_and(sd->span, sd->span, *cpu_map);
  5052. sd->parent = p;
  5053. p->child = sd;
  5054. cpu_to_cpu_group(i, cpu_map, &sd->groups);
  5055. #endif
  5056. }
  5057. #ifdef CONFIG_SCHED_SMT
  5058. /* Set up CPU (sibling) groups */
  5059. for_each_cpu_mask(i, *cpu_map) {
  5060. cpumask_t this_sibling_map = cpu_sibling_map[i];
  5061. cpus_and(this_sibling_map, this_sibling_map, *cpu_map);
  5062. if (i != first_cpu(this_sibling_map))
  5063. continue;
  5064. init_sched_build_groups(this_sibling_map, cpu_map,
  5065. &cpu_to_cpu_group);
  5066. }
  5067. #endif
  5068. #ifdef CONFIG_SCHED_MC
  5069. /* Set up multi-core groups */
  5070. for_each_cpu_mask(i, *cpu_map) {
  5071. cpumask_t this_core_map = cpu_coregroup_map(i);
  5072. cpus_and(this_core_map, this_core_map, *cpu_map);
  5073. if (i != first_cpu(this_core_map))
  5074. continue;
  5075. init_sched_build_groups(this_core_map, cpu_map,
  5076. &cpu_to_core_group);
  5077. }
  5078. #endif
  5079. /* Set up physical groups */
  5080. for (i = 0; i < MAX_NUMNODES; i++) {
  5081. cpumask_t nodemask = node_to_cpumask(i);
  5082. cpus_and(nodemask, nodemask, *cpu_map);
  5083. if (cpus_empty(nodemask))
  5084. continue;
  5085. init_sched_build_groups(nodemask, cpu_map, &cpu_to_phys_group);
  5086. }
  5087. #ifdef CONFIG_NUMA
  5088. /* Set up node groups */
  5089. if (sd_allnodes)
  5090. init_sched_build_groups(*cpu_map, cpu_map,
  5091. &cpu_to_allnodes_group);
  5092. for (i = 0; i < MAX_NUMNODES; i++) {
  5093. /* Set up node groups */
  5094. struct sched_group *sg, *prev;
  5095. cpumask_t nodemask = node_to_cpumask(i);
  5096. cpumask_t domainspan;
  5097. cpumask_t covered = CPU_MASK_NONE;
  5098. int j;
  5099. cpus_and(nodemask, nodemask, *cpu_map);
  5100. if (cpus_empty(nodemask)) {
  5101. sched_group_nodes[i] = NULL;
  5102. continue;
  5103. }
  5104. domainspan = sched_domain_node_span(i);
  5105. cpus_and(domainspan, domainspan, *cpu_map);
  5106. sg = kmalloc_node(sizeof(struct sched_group), GFP_KERNEL, i);
  5107. if (!sg) {
  5108. printk(KERN_WARNING "Can not alloc domain group for "
  5109. "node %d\n", i);
  5110. goto error;
  5111. }
  5112. sched_group_nodes[i] = sg;
  5113. for_each_cpu_mask(j, nodemask) {
  5114. struct sched_domain *sd;
  5115. sd = &per_cpu(node_domains, j);
  5116. sd->groups = sg;
  5117. }
  5118. sg->__cpu_power = 0;
  5119. sg->cpumask = nodemask;
  5120. sg->next = sg;
  5121. cpus_or(covered, covered, nodemask);
  5122. prev = sg;
  5123. for (j = 0; j < MAX_NUMNODES; j++) {
  5124. cpumask_t tmp, notcovered;
  5125. int n = (i + j) % MAX_NUMNODES;
  5126. cpus_complement(notcovered, covered);
  5127. cpus_and(tmp, notcovered, *cpu_map);
  5128. cpus_and(tmp, tmp, domainspan);
  5129. if (cpus_empty(tmp))
  5130. break;
  5131. nodemask = node_to_cpumask(n);
  5132. cpus_and(tmp, tmp, nodemask);
  5133. if (cpus_empty(tmp))
  5134. continue;
  5135. sg = kmalloc_node(sizeof(struct sched_group),
  5136. GFP_KERNEL, i);
  5137. if (!sg) {
  5138. printk(KERN_WARNING
  5139. "Can not alloc domain group for node %d\n", j);
  5140. goto error;
  5141. }
  5142. sg->__cpu_power = 0;
  5143. sg->cpumask = tmp;
  5144. sg->next = prev->next;
  5145. cpus_or(covered, covered, tmp);
  5146. prev->next = sg;
  5147. prev = sg;
  5148. }
  5149. }
  5150. #endif
  5151. /* Calculate CPU power for physical packages and nodes */
  5152. #ifdef CONFIG_SCHED_SMT
  5153. for_each_cpu_mask(i, *cpu_map) {
  5154. struct sched_domain *sd = &per_cpu(cpu_domains, i);
  5155. init_sched_groups_power(i, sd);
  5156. }
  5157. #endif
  5158. #ifdef CONFIG_SCHED_MC
  5159. for_each_cpu_mask(i, *cpu_map) {
  5160. struct sched_domain *sd = &per_cpu(core_domains, i);
  5161. init_sched_groups_power(i, sd);
  5162. }
  5163. #endif
  5164. for_each_cpu_mask(i, *cpu_map) {
  5165. struct sched_domain *sd = &per_cpu(phys_domains, i);
  5166. init_sched_groups_power(i, sd);
  5167. }
  5168. #ifdef CONFIG_NUMA
  5169. for (i = 0; i < MAX_NUMNODES; i++)
  5170. init_numa_sched_groups_power(sched_group_nodes[i]);
  5171. if (sd_allnodes) {
  5172. struct sched_group *sg;
  5173. cpu_to_allnodes_group(first_cpu(*cpu_map), cpu_map, &sg);
  5174. init_numa_sched_groups_power(sg);
  5175. }
  5176. #endif
  5177. /* Attach the domains */
  5178. for_each_cpu_mask(i, *cpu_map) {
  5179. struct sched_domain *sd;
  5180. #ifdef CONFIG_SCHED_SMT
  5181. sd = &per_cpu(cpu_domains, i);
  5182. #elif defined(CONFIG_SCHED_MC)
  5183. sd = &per_cpu(core_domains, i);
  5184. #else
  5185. sd = &per_cpu(phys_domains, i);
  5186. #endif
  5187. cpu_attach_domain(sd, i);
  5188. }
  5189. return 0;
  5190. #ifdef CONFIG_NUMA
  5191. error:
  5192. free_sched_groups(cpu_map);
  5193. return -ENOMEM;
  5194. #endif
  5195. }
  5196. /*
  5197. * Set up scheduler domains and groups. Callers must hold the hotplug lock.
  5198. */
  5199. static int arch_init_sched_domains(const cpumask_t *cpu_map)
  5200. {
  5201. cpumask_t cpu_default_map;
  5202. int err;
  5203. /*
  5204. * Setup mask for cpus without special case scheduling requirements.
  5205. * For now this just excludes isolated cpus, but could be used to
  5206. * exclude other special cases in the future.
  5207. */
  5208. cpus_andnot(cpu_default_map, *cpu_map, cpu_isolated_map);
  5209. err = build_sched_domains(&cpu_default_map);
  5210. return err;
  5211. }
  5212. static void arch_destroy_sched_domains(const cpumask_t *cpu_map)
  5213. {
  5214. free_sched_groups(cpu_map);
  5215. }
  5216. /*
  5217. * Detach sched domains from a group of cpus specified in cpu_map
  5218. * These cpus will now be attached to the NULL domain
  5219. */
  5220. static void detach_destroy_domains(const cpumask_t *cpu_map)
  5221. {
  5222. int i;
  5223. for_each_cpu_mask(i, *cpu_map)
  5224. cpu_attach_domain(NULL, i);
  5225. synchronize_sched();
  5226. arch_destroy_sched_domains(cpu_map);
  5227. }
  5228. /*
  5229. * Partition sched domains as specified by the cpumasks below.
  5230. * This attaches all cpus from the cpumasks to the NULL domain,
  5231. * waits for a RCU quiescent period, recalculates sched
  5232. * domain information and then attaches them back to the
  5233. * correct sched domains
  5234. * Call with hotplug lock held
  5235. */
  5236. int partition_sched_domains(cpumask_t *partition1, cpumask_t *partition2)
  5237. {
  5238. cpumask_t change_map;
  5239. int err = 0;
  5240. cpus_and(*partition1, *partition1, cpu_online_map);
  5241. cpus_and(*partition2, *partition2, cpu_online_map);
  5242. cpus_or(change_map, *partition1, *partition2);
  5243. /* Detach sched domains from all of the affected cpus */
  5244. detach_destroy_domains(&change_map);
  5245. if (!cpus_empty(*partition1))
  5246. err = build_sched_domains(partition1);
  5247. if (!err && !cpus_empty(*partition2))
  5248. err = build_sched_domains(partition2);
  5249. return err;
  5250. }
  5251. #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
  5252. int arch_reinit_sched_domains(void)
  5253. {
  5254. int err;
  5255. mutex_lock(&sched_hotcpu_mutex);
  5256. detach_destroy_domains(&cpu_online_map);
  5257. err = arch_init_sched_domains(&cpu_online_map);
  5258. mutex_unlock(&sched_hotcpu_mutex);
  5259. return err;
  5260. }
  5261. static ssize_t sched_power_savings_store(const char *buf, size_t count, int smt)
  5262. {
  5263. int ret;
  5264. if (buf[0] != '0' && buf[0] != '1')
  5265. return -EINVAL;
  5266. if (smt)
  5267. sched_smt_power_savings = (buf[0] == '1');
  5268. else
  5269. sched_mc_power_savings = (buf[0] == '1');
  5270. ret = arch_reinit_sched_domains();
  5271. return ret ? ret : count;
  5272. }
  5273. int sched_create_sysfs_power_savings_entries(struct sysdev_class *cls)
  5274. {
  5275. int err = 0;
  5276. #ifdef CONFIG_SCHED_SMT
  5277. if (smt_capable())
  5278. err = sysfs_create_file(&cls->kset.kobj,
  5279. &attr_sched_smt_power_savings.attr);
  5280. #endif
  5281. #ifdef CONFIG_SCHED_MC
  5282. if (!err && mc_capable())
  5283. err = sysfs_create_file(&cls->kset.kobj,
  5284. &attr_sched_mc_power_savings.attr);
  5285. #endif
  5286. return err;
  5287. }
  5288. #endif
  5289. #ifdef CONFIG_SCHED_MC
  5290. static ssize_t sched_mc_power_savings_show(struct sys_device *dev, char *page)
  5291. {
  5292. return sprintf(page, "%u\n", sched_mc_power_savings);
  5293. }
  5294. static ssize_t sched_mc_power_savings_store(struct sys_device *dev,
  5295. const char *buf, size_t count)
  5296. {
  5297. return sched_power_savings_store(buf, count, 0);
  5298. }
  5299. SYSDEV_ATTR(sched_mc_power_savings, 0644, sched_mc_power_savings_show,
  5300. sched_mc_power_savings_store);
  5301. #endif
  5302. #ifdef CONFIG_SCHED_SMT
  5303. static ssize_t sched_smt_power_savings_show(struct sys_device *dev, char *page)
  5304. {
  5305. return sprintf(page, "%u\n", sched_smt_power_savings);
  5306. }
  5307. static ssize_t sched_smt_power_savings_store(struct sys_device *dev,
  5308. const char *buf, size_t count)
  5309. {
  5310. return sched_power_savings_store(buf, count, 1);
  5311. }
  5312. SYSDEV_ATTR(sched_smt_power_savings, 0644, sched_smt_power_savings_show,
  5313. sched_smt_power_savings_store);
  5314. #endif
  5315. /*
  5316. * Force a reinitialization of the sched domains hierarchy. The domains
  5317. * and groups cannot be updated in place without racing with the balancing
  5318. * code, so we temporarily attach all running cpus to the NULL domain
  5319. * which will prevent rebalancing while the sched domains are recalculated.
  5320. */
  5321. static int update_sched_domains(struct notifier_block *nfb,
  5322. unsigned long action, void *hcpu)
  5323. {
  5324. switch (action) {
  5325. case CPU_UP_PREPARE:
  5326. case CPU_UP_PREPARE_FROZEN:
  5327. case CPU_DOWN_PREPARE:
  5328. case CPU_DOWN_PREPARE_FROZEN:
  5329. detach_destroy_domains(&cpu_online_map);
  5330. return NOTIFY_OK;
  5331. case CPU_UP_CANCELED:
  5332. case CPU_UP_CANCELED_FROZEN:
  5333. case CPU_DOWN_FAILED:
  5334. case CPU_DOWN_FAILED_FROZEN:
  5335. case CPU_ONLINE:
  5336. case CPU_ONLINE_FROZEN:
  5337. case CPU_DEAD:
  5338. case CPU_DEAD_FROZEN:
  5339. /*
  5340. * Fall through and re-initialise the domains.
  5341. */
  5342. break;
  5343. default:
  5344. return NOTIFY_DONE;
  5345. }
  5346. /* The hotplug lock is already held by cpu_up/cpu_down */
  5347. arch_init_sched_domains(&cpu_online_map);
  5348. return NOTIFY_OK;
  5349. }
  5350. void __init sched_init_smp(void)
  5351. {
  5352. cpumask_t non_isolated_cpus;
  5353. mutex_lock(&sched_hotcpu_mutex);
  5354. arch_init_sched_domains(&cpu_online_map);
  5355. cpus_andnot(non_isolated_cpus, cpu_possible_map, cpu_isolated_map);
  5356. if (cpus_empty(non_isolated_cpus))
  5357. cpu_set(smp_processor_id(), non_isolated_cpus);
  5358. mutex_unlock(&sched_hotcpu_mutex);
  5359. /* XXX: Theoretical race here - CPU may be hotplugged now */
  5360. hotcpu_notifier(update_sched_domains, 0);
  5361. /* Move init over to a non-isolated CPU */
  5362. if (set_cpus_allowed(current, non_isolated_cpus) < 0)
  5363. BUG();
  5364. sched_init_granularity();
  5365. }
  5366. #else
  5367. void __init sched_init_smp(void)
  5368. {
  5369. sched_init_granularity();
  5370. }
  5371. #endif /* CONFIG_SMP */
  5372. int in_sched_functions(unsigned long addr)
  5373. {
  5374. /* Linker adds these: start and end of __sched functions */
  5375. extern char __sched_text_start[], __sched_text_end[];
  5376. return in_lock_functions(addr) ||
  5377. (addr >= (unsigned long)__sched_text_start
  5378. && addr < (unsigned long)__sched_text_end);
  5379. }
  5380. static inline void init_cfs_rq(struct cfs_rq *cfs_rq, struct rq *rq)
  5381. {
  5382. cfs_rq->tasks_timeline = RB_ROOT;
  5383. cfs_rq->fair_clock = 1;
  5384. #ifdef CONFIG_FAIR_GROUP_SCHED
  5385. cfs_rq->rq = rq;
  5386. #endif
  5387. }
  5388. void __init sched_init(void)
  5389. {
  5390. u64 now = sched_clock();
  5391. int highest_cpu = 0;
  5392. int i, j;
  5393. /*
  5394. * Link up the scheduling class hierarchy:
  5395. */
  5396. rt_sched_class.next = &fair_sched_class;
  5397. fair_sched_class.next = &idle_sched_class;
  5398. idle_sched_class.next = NULL;
  5399. for_each_possible_cpu(i) {
  5400. struct rt_prio_array *array;
  5401. struct rq *rq;
  5402. rq = cpu_rq(i);
  5403. spin_lock_init(&rq->lock);
  5404. lockdep_set_class(&rq->lock, &rq->rq_lock_key);
  5405. rq->nr_running = 0;
  5406. rq->clock = 1;
  5407. init_cfs_rq(&rq->cfs, rq);
  5408. #ifdef CONFIG_FAIR_GROUP_SCHED
  5409. INIT_LIST_HEAD(&rq->leaf_cfs_rq_list);
  5410. list_add(&rq->cfs.leaf_cfs_rq_list, &rq->leaf_cfs_rq_list);
  5411. #endif
  5412. rq->ls.load_update_last = now;
  5413. rq->ls.load_update_start = now;
  5414. for (j = 0; j < CPU_LOAD_IDX_MAX; j++)
  5415. rq->cpu_load[j] = 0;
  5416. #ifdef CONFIG_SMP
  5417. rq->sd = NULL;
  5418. rq->active_balance = 0;
  5419. rq->next_balance = jiffies;
  5420. rq->push_cpu = 0;
  5421. rq->cpu = i;
  5422. rq->migration_thread = NULL;
  5423. INIT_LIST_HEAD(&rq->migration_queue);
  5424. #endif
  5425. atomic_set(&rq->nr_iowait, 0);
  5426. array = &rq->rt.active;
  5427. for (j = 0; j < MAX_RT_PRIO; j++) {
  5428. INIT_LIST_HEAD(array->queue + j);
  5429. __clear_bit(j, array->bitmap);
  5430. }
  5431. highest_cpu = i;
  5432. /* delimiter for bitsearch: */
  5433. __set_bit(MAX_RT_PRIO, array->bitmap);
  5434. }
  5435. set_load_weight(&init_task);
  5436. #ifdef CONFIG_SMP
  5437. nr_cpu_ids = highest_cpu + 1;
  5438. open_softirq(SCHED_SOFTIRQ, run_rebalance_domains, NULL);
  5439. #endif
  5440. #ifdef CONFIG_RT_MUTEXES
  5441. plist_head_init(&init_task.pi_waiters, &init_task.pi_lock);
  5442. #endif
  5443. /*
  5444. * The boot idle thread does lazy MMU switching as well:
  5445. */
  5446. atomic_inc(&init_mm.mm_count);
  5447. enter_lazy_tlb(&init_mm, current);
  5448. /*
  5449. * Make us the idle thread. Technically, schedule() should not be
  5450. * called from this thread, however somewhere below it might be,
  5451. * but because we are the idle thread, we just pick up running again
  5452. * when this runqueue becomes "idle".
  5453. */
  5454. init_idle(current, smp_processor_id());
  5455. /*
  5456. * During early bootup we pretend to be a normal task:
  5457. */
  5458. current->sched_class = &fair_sched_class;
  5459. }
  5460. #ifdef CONFIG_DEBUG_SPINLOCK_SLEEP
  5461. void __might_sleep(char *file, int line)
  5462. {
  5463. #ifdef in_atomic
  5464. static unsigned long prev_jiffy; /* ratelimiting */
  5465. if ((in_atomic() || irqs_disabled()) &&
  5466. system_state == SYSTEM_RUNNING && !oops_in_progress) {
  5467. if (time_before(jiffies, prev_jiffy + HZ) && prev_jiffy)
  5468. return;
  5469. prev_jiffy = jiffies;
  5470. printk(KERN_ERR "BUG: sleeping function called from invalid"
  5471. " context at %s:%d\n", file, line);
  5472. printk("in_atomic():%d, irqs_disabled():%d\n",
  5473. in_atomic(), irqs_disabled());
  5474. debug_show_held_locks(current);
  5475. if (irqs_disabled())
  5476. print_irqtrace_events(current);
  5477. dump_stack();
  5478. }
  5479. #endif
  5480. }
  5481. EXPORT_SYMBOL(__might_sleep);
  5482. #endif
  5483. #ifdef CONFIG_MAGIC_SYSRQ
  5484. void normalize_rt_tasks(void)
  5485. {
  5486. struct task_struct *g, *p;
  5487. unsigned long flags;
  5488. struct rq *rq;
  5489. int on_rq;
  5490. read_lock_irq(&tasklist_lock);
  5491. do_each_thread(g, p) {
  5492. p->se.fair_key = 0;
  5493. p->se.wait_runtime = 0;
  5494. p->se.wait_start_fair = 0;
  5495. p->se.wait_start = 0;
  5496. p->se.exec_start = 0;
  5497. p->se.sleep_start = 0;
  5498. p->se.sleep_start_fair = 0;
  5499. p->se.block_start = 0;
  5500. task_rq(p)->cfs.fair_clock = 0;
  5501. task_rq(p)->clock = 0;
  5502. if (!rt_task(p)) {
  5503. /*
  5504. * Renice negative nice level userspace
  5505. * tasks back to 0:
  5506. */
  5507. if (TASK_NICE(p) < 0 && p->mm)
  5508. set_user_nice(p, 0);
  5509. continue;
  5510. }
  5511. spin_lock_irqsave(&p->pi_lock, flags);
  5512. rq = __task_rq_lock(p);
  5513. #ifdef CONFIG_SMP
  5514. /*
  5515. * Do not touch the migration thread:
  5516. */
  5517. if (p == rq->migration_thread)
  5518. goto out_unlock;
  5519. #endif
  5520. on_rq = p->se.on_rq;
  5521. if (on_rq)
  5522. deactivate_task(task_rq(p), p, 0);
  5523. __setscheduler(rq, p, SCHED_NORMAL, 0);
  5524. if (on_rq) {
  5525. activate_task(task_rq(p), p, 0);
  5526. resched_task(rq->curr);
  5527. }
  5528. #ifdef CONFIG_SMP
  5529. out_unlock:
  5530. #endif
  5531. __task_rq_unlock(rq);
  5532. spin_unlock_irqrestore(&p->pi_lock, flags);
  5533. } while_each_thread(g, p);
  5534. read_unlock_irq(&tasklist_lock);
  5535. }
  5536. #endif /* CONFIG_MAGIC_SYSRQ */
  5537. #ifdef CONFIG_IA64
  5538. /*
  5539. * These functions are only useful for the IA64 MCA handling.
  5540. *
  5541. * They can only be called when the whole system has been
  5542. * stopped - every CPU needs to be quiescent, and no scheduling
  5543. * activity can take place. Using them for anything else would
  5544. * be a serious bug, and as a result, they aren't even visible
  5545. * under any other configuration.
  5546. */
  5547. /**
  5548. * curr_task - return the current task for a given cpu.
  5549. * @cpu: the processor in question.
  5550. *
  5551. * ONLY VALID WHEN THE WHOLE SYSTEM IS STOPPED!
  5552. */
  5553. struct task_struct *curr_task(int cpu)
  5554. {
  5555. return cpu_curr(cpu);
  5556. }
  5557. /**
  5558. * set_curr_task - set the current task for a given cpu.
  5559. * @cpu: the processor in question.
  5560. * @p: the task pointer to set.
  5561. *
  5562. * Description: This function must only be used when non-maskable interrupts
  5563. * are serviced on a separate stack. It allows the architecture to switch the
  5564. * notion of the current task on a cpu in a non-blocking manner. This function
  5565. * must be called with all CPU's synchronized, and interrupts disabled, the
  5566. * and caller must save the original value of the current task (see
  5567. * curr_task() above) and restore that value before reenabling interrupts and
  5568. * re-starting the system.
  5569. *
  5570. * ONLY VALID WHEN THE WHOLE SYSTEM IS STOPPED!
  5571. */
  5572. void set_curr_task(int cpu, struct task_struct *p)
  5573. {
  5574. cpu_curr(cpu) = p;
  5575. }
  5576. #endif