sched.c 177 KB

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