lockdep.c 165 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572457345744575457645774578457945804581458245834584458545864587458845894590459145924593459445954596459745984599460046014602460346044605460646074608460946104611461246134614461546164617461846194620462146224623462446254626462746284629463046314632463346344635463646374638463946404641464246434644464546464647464846494650465146524653465446554656465746584659466046614662466346644665466646674668466946704671467246734674467546764677467846794680468146824683468446854686468746884689469046914692469346944695469646974698469947004701470247034704470547064707470847094710471147124713471447154716471747184719472047214722472347244725472647274728472947304731473247334734473547364737473847394740474147424743474447454746474747484749475047514752475347544755475647574758475947604761476247634764476547664767476847694770477147724773477447754776477747784779478047814782478347844785478647874788478947904791479247934794479547964797479847994800480148024803480448054806480748084809481048114812481348144815481648174818481948204821482248234824482548264827482848294830483148324833483448354836483748384839484048414842484348444845484648474848484948504851485248534854485548564857485848594860486148624863486448654866486748684869487048714872487348744875487648774878487948804881488248834884488548864887488848894890489148924893489448954896489748984899490049014902490349044905490649074908490949104911491249134914491549164917491849194920492149224923492449254926492749284929493049314932493349344935493649374938493949404941494249434944494549464947494849494950495149524953495449554956495749584959496049614962496349644965496649674968496949704971497249734974497549764977497849794980498149824983498449854986498749884989499049914992499349944995499649974998499950005001500250035004500550065007500850095010501150125013501450155016501750185019502050215022502350245025502650275028502950305031503250335034503550365037503850395040504150425043504450455046504750485049505050515052505350545055505650575058505950605061506250635064506550665067506850695070507150725073507450755076507750785079508050815082508350845085508650875088508950905091509250935094509550965097509850995100510151025103510451055106510751085109511051115112511351145115511651175118511951205121512251235124512551265127512851295130513151325133513451355136513751385139514051415142514351445145514651475148514951505151515251535154515551565157515851595160516151625163516451655166516751685169517051715172517351745175517651775178517951805181518251835184518551865187518851895190519151925193519451955196519751985199520052015202520352045205520652075208520952105211521252135214521552165217521852195220522152225223522452255226522752285229523052315232523352345235523652375238523952405241524252435244524552465247524852495250525152525253525452555256525752585259526052615262526352645265526652675268526952705271527252735274527552765277527852795280528152825283528452855286528752885289529052915292529352945295529652975298529953005301530253035304530553065307530853095310531153125313531453155316531753185319532053215322532353245325532653275328532953305331533253335334533553365337533853395340534153425343534453455346534753485349535053515352535353545355535653575358535953605361536253635364536553665367536853695370537153725373537453755376537753785379538053815382538353845385538653875388538953905391539253935394539553965397539853995400540154025403540454055406540754085409541054115412541354145415541654175418541954205421542254235424542554265427542854295430543154325433543454355436543754385439544054415442544354445445544654475448544954505451545254535454545554565457545854595460546154625463546454655466546754685469547054715472547354745475547654775478547954805481548254835484548554865487548854895490549154925493549454955496549754985499550055015502550355045505550655075508550955105511551255135514551555165517551855195520552155225523552455255526552755285529553055315532553355345535553655375538553955405541554255435544554555465547554855495550555155525553555455555556555755585559556055615562556355645565556655675568556955705571557255735574557555765577557855795580558155825583558455855586558755885589559055915592559355945595559655975598559956005601560256035604560556065607560856095610561156125613561456155616561756185619562056215622562356245625562656275628562956305631563256335634563556365637563856395640564156425643564456455646564756485649565056515652565356545655565656575658565956605661566256635664566556665667566856695670567156725673567456755676567756785679568056815682568356845685568656875688568956905691569256935694569556965697569856995700570157025703570457055706570757085709571057115712571357145715571657175718571957205721572257235724572557265727572857295730573157325733573457355736573757385739574057415742574357445745574657475748574957505751575257535754575557565757575857595760576157625763576457655766576757685769577057715772577357745775577657775778577957805781578257835784578557865787578857895790579157925793579457955796579757985799580058015802580358045805580658075808580958105811581258135814581558165817581858195820582158225823582458255826582758285829583058315832583358345835583658375838583958405841584258435844584558465847584858495850585158525853585458555856585758585859586058615862586358645865586658675868586958705871587258735874587558765877587858795880588158825883588458855886588758885889589058915892589358945895589658975898589959005901590259035904590559065907590859095910591159125913591459155916591759185919592059215922592359245925592659275928592959305931593259335934593559365937593859395940594159425943594459455946594759485949595059515952595359545955595659575958595959605961596259635964596559665967596859695970597159725973597459755976597759785979598059815982598359845985598659875988598959905991599259935994599559965997599859996000600160026003600460056006600760086009601060116012601360146015601660176018601960206021602260236024602560266027602860296030603160326033603460356036603760386039604060416042604360446045604660476048604960506051605260536054605560566057605860596060606160626063606460656066606760686069607060716072607360746075607660776078607960806081608260836084608560866087608860896090609160926093609460956096609760986099610061016102610361046105610661076108610961106111611261136114611561166117611861196120612161226123612461256126612761286129613061316132613361346135613661376138613961406141614261436144614561466147614861496150615161526153615461556156615761586159616061616162616361646165616661676168616961706171617261736174617561766177617861796180618161826183618461856186618761886189619061916192619361946195619661976198619962006201620262036204620562066207620862096210621162126213621462156216621762186219622062216222622362246225622662276228622962306231623262336234623562366237623862396240624162426243624462456246624762486249625062516252625362546255625662576258625962606261626262636264626562666267626862696270627162726273627462756276627762786279628062816282628362846285628662876288628962906291629262936294629562966297629862996300630163026303630463056306630763086309631063116312631363146315631663176318631963206321632263236324632563266327632863296330633163326333633463356336633763386339634063416342634363446345634663476348634963506351635263536354635563566357635863596360636163626363636463656366636763686369637063716372637363746375637663776378637963806381638263836384638563866387638863896390639163926393639463956396639763986399640064016402640364046405640664076408640964106411641264136414641564166417641864196420642164226423642464256426642764286429643064316432643364346435643664376438643964406441644264436444644564466447644864496450645164526453645464556456645764586459646064616462646364646465646664676468646964706471647264736474647564766477647864796480648164826483648464856486648764886489649064916492
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * kernel/lockdep.c
  4. *
  5. * Runtime locking correctness validator
  6. *
  7. * Started by Ingo Molnar:
  8. *
  9. * Copyright (C) 2006,2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
  10. * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
  11. *
  12. * this code maps all the lock dependencies as they occur in a live kernel
  13. * and will warn about the following classes of locking bugs:
  14. *
  15. * - lock inversion scenarios
  16. * - circular lock dependencies
  17. * - hardirq/softirq safe/unsafe locking bugs
  18. *
  19. * Bugs are reported even if the current locking scenario does not cause
  20. * any deadlock at this point.
  21. *
  22. * I.e. if anytime in the past two locks were taken in a different order,
  23. * even if it happened for another task, even if those were different
  24. * locks (but of the same class as this lock), this code will detect it.
  25. *
  26. * Thanks to Arjan van de Ven for coming up with the initial idea of
  27. * mapping lock dependencies runtime.
  28. */
  29. #define DISABLE_BRANCH_PROFILING
  30. #include <linux/mutex.h>
  31. #include <linux/sched.h>
  32. #include <linux/sched/clock.h>
  33. #include <linux/sched/task.h>
  34. #include <linux/sched/mm.h>
  35. #include <linux/delay.h>
  36. #include <linux/module.h>
  37. #include <linux/proc_fs.h>
  38. #include <linux/seq_file.h>
  39. #include <linux/spinlock.h>
  40. #include <linux/kallsyms.h>
  41. #include <linux/interrupt.h>
  42. #include <linux/stacktrace.h>
  43. #include <linux/debug_locks.h>
  44. #include <linux/irqflags.h>
  45. #include <linux/utsname.h>
  46. #include <linux/hash.h>
  47. #include <linux/ftrace.h>
  48. #include <linux/stringify.h>
  49. #include <linux/bitmap.h>
  50. #include <linux/bitops.h>
  51. #include <linux/gfp.h>
  52. #include <linux/random.h>
  53. #include <linux/jhash.h>
  54. #include <linux/nmi.h>
  55. #include <linux/rcupdate.h>
  56. #include <linux/kprobes.h>
  57. #include <asm/sections.h>
  58. #include "lockdep_internals.h"
  59. #define CREATE_TRACE_POINTS
  60. #include <trace/events/lock.h>
  61. #ifdef CONFIG_PROVE_LOCKING
  62. int prove_locking = 1;
  63. module_param(prove_locking, int, 0644);
  64. #else
  65. #define prove_locking 0
  66. #endif
  67. #ifdef CONFIG_LOCK_STAT
  68. int lock_stat = 1;
  69. module_param(lock_stat, int, 0644);
  70. #else
  71. #define lock_stat 0
  72. #endif
  73. DEFINE_PER_CPU(unsigned int, lockdep_recursion);
  74. EXPORT_PER_CPU_SYMBOL_GPL(lockdep_recursion);
  75. static __always_inline bool lockdep_enabled(void)
  76. {
  77. if (!debug_locks)
  78. return false;
  79. if (this_cpu_read(lockdep_recursion))
  80. return false;
  81. if (current->lockdep_recursion)
  82. return false;
  83. return true;
  84. }
  85. /*
  86. * lockdep_lock: protects the lockdep graph, the hashes and the
  87. * class/list/hash allocators.
  88. *
  89. * This is one of the rare exceptions where it's justified
  90. * to use a raw spinlock - we really dont want the spinlock
  91. * code to recurse back into the lockdep code...
  92. */
  93. static arch_spinlock_t __lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
  94. static struct task_struct *__owner;
  95. static inline void lockdep_lock(void)
  96. {
  97. DEBUG_LOCKS_WARN_ON(!irqs_disabled());
  98. __this_cpu_inc(lockdep_recursion);
  99. arch_spin_lock(&__lock);
  100. __owner = current;
  101. }
  102. static inline void lockdep_unlock(void)
  103. {
  104. DEBUG_LOCKS_WARN_ON(!irqs_disabled());
  105. if (debug_locks && DEBUG_LOCKS_WARN_ON(__owner != current))
  106. return;
  107. __owner = NULL;
  108. arch_spin_unlock(&__lock);
  109. __this_cpu_dec(lockdep_recursion);
  110. }
  111. static inline bool lockdep_assert_locked(void)
  112. {
  113. return DEBUG_LOCKS_WARN_ON(__owner != current);
  114. }
  115. static struct task_struct *lockdep_selftest_task_struct;
  116. static int graph_lock(void)
  117. {
  118. lockdep_lock();
  119. /*
  120. * Make sure that if another CPU detected a bug while
  121. * walking the graph we dont change it (while the other
  122. * CPU is busy printing out stuff with the graph lock
  123. * dropped already)
  124. */
  125. if (!debug_locks) {
  126. lockdep_unlock();
  127. return 0;
  128. }
  129. return 1;
  130. }
  131. static inline void graph_unlock(void)
  132. {
  133. lockdep_unlock();
  134. }
  135. /*
  136. * Turn lock debugging off and return with 0 if it was off already,
  137. * and also release the graph lock:
  138. */
  139. static inline int debug_locks_off_graph_unlock(void)
  140. {
  141. int ret = debug_locks_off();
  142. lockdep_unlock();
  143. return ret;
  144. }
  145. unsigned long nr_list_entries;
  146. static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
  147. static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);
  148. /*
  149. * All data structures here are protected by the global debug_lock.
  150. *
  151. * nr_lock_classes is the number of elements of lock_classes[] that is
  152. * in use.
  153. */
  154. #define KEYHASH_BITS (MAX_LOCKDEP_KEYS_BITS - 1)
  155. #define KEYHASH_SIZE (1UL << KEYHASH_BITS)
  156. static struct hlist_head lock_keys_hash[KEYHASH_SIZE];
  157. unsigned long nr_lock_classes;
  158. unsigned long nr_zapped_classes;
  159. unsigned long max_lock_class_idx;
  160. struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
  161. DECLARE_BITMAP(lock_classes_in_use, MAX_LOCKDEP_KEYS);
  162. static inline struct lock_class *hlock_class(struct held_lock *hlock)
  163. {
  164. unsigned int class_idx = hlock->class_idx;
  165. /* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfield */
  166. barrier();
  167. if (!test_bit(class_idx, lock_classes_in_use)) {
  168. /*
  169. * Someone passed in garbage, we give up.
  170. */
  171. DEBUG_LOCKS_WARN_ON(1);
  172. return NULL;
  173. }
  174. /*
  175. * At this point, if the passed hlock->class_idx is still garbage,
  176. * we just have to live with it
  177. */
  178. return lock_classes + class_idx;
  179. }
  180. #ifdef CONFIG_LOCK_STAT
  181. static DEFINE_PER_CPU(struct lock_class_stats[MAX_LOCKDEP_KEYS], cpu_lock_stats);
  182. static inline u64 lockstat_clock(void)
  183. {
  184. return local_clock();
  185. }
  186. static int lock_point(unsigned long points[], unsigned long ip)
  187. {
  188. int i;
  189. for (i = 0; i < LOCKSTAT_POINTS; i++) {
  190. if (points[i] == 0) {
  191. points[i] = ip;
  192. break;
  193. }
  194. if (points[i] == ip)
  195. break;
  196. }
  197. return i;
  198. }
  199. static void lock_time_inc(struct lock_time *lt, u64 time)
  200. {
  201. if (time > lt->max)
  202. lt->max = time;
  203. if (time < lt->min || !lt->nr)
  204. lt->min = time;
  205. lt->total += time;
  206. lt->nr++;
  207. }
  208. static inline void lock_time_add(struct lock_time *src, struct lock_time *dst)
  209. {
  210. if (!src->nr)
  211. return;
  212. if (src->max > dst->max)
  213. dst->max = src->max;
  214. if (src->min < dst->min || !dst->nr)
  215. dst->min = src->min;
  216. dst->total += src->total;
  217. dst->nr += src->nr;
  218. }
  219. struct lock_class_stats lock_stats(struct lock_class *class)
  220. {
  221. struct lock_class_stats stats;
  222. int cpu, i;
  223. memset(&stats, 0, sizeof(struct lock_class_stats));
  224. for_each_possible_cpu(cpu) {
  225. struct lock_class_stats *pcs =
  226. &per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
  227. for (i = 0; i < ARRAY_SIZE(stats.contention_point); i++)
  228. stats.contention_point[i] += pcs->contention_point[i];
  229. for (i = 0; i < ARRAY_SIZE(stats.contending_point); i++)
  230. stats.contending_point[i] += pcs->contending_point[i];
  231. lock_time_add(&pcs->read_waittime, &stats.read_waittime);
  232. lock_time_add(&pcs->write_waittime, &stats.write_waittime);
  233. lock_time_add(&pcs->read_holdtime, &stats.read_holdtime);
  234. lock_time_add(&pcs->write_holdtime, &stats.write_holdtime);
  235. for (i = 0; i < ARRAY_SIZE(stats.bounces); i++)
  236. stats.bounces[i] += pcs->bounces[i];
  237. }
  238. return stats;
  239. }
  240. void clear_lock_stats(struct lock_class *class)
  241. {
  242. int cpu;
  243. for_each_possible_cpu(cpu) {
  244. struct lock_class_stats *cpu_stats =
  245. &per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
  246. memset(cpu_stats, 0, sizeof(struct lock_class_stats));
  247. }
  248. memset(class->contention_point, 0, sizeof(class->contention_point));
  249. memset(class->contending_point, 0, sizeof(class->contending_point));
  250. }
  251. static struct lock_class_stats *get_lock_stats(struct lock_class *class)
  252. {
  253. return &this_cpu_ptr(cpu_lock_stats)[class - lock_classes];
  254. }
  255. static void lock_release_holdtime(struct held_lock *hlock)
  256. {
  257. struct lock_class_stats *stats;
  258. u64 holdtime;
  259. if (!lock_stat)
  260. return;
  261. holdtime = lockstat_clock() - hlock->holdtime_stamp;
  262. stats = get_lock_stats(hlock_class(hlock));
  263. if (hlock->read)
  264. lock_time_inc(&stats->read_holdtime, holdtime);
  265. else
  266. lock_time_inc(&stats->write_holdtime, holdtime);
  267. }
  268. #else
  269. static inline void lock_release_holdtime(struct held_lock *hlock)
  270. {
  271. }
  272. #endif
  273. /*
  274. * We keep a global list of all lock classes. The list is only accessed with
  275. * the lockdep spinlock lock held. free_lock_classes is a list with free
  276. * elements. These elements are linked together by the lock_entry member in
  277. * struct lock_class.
  278. */
  279. static LIST_HEAD(all_lock_classes);
  280. static LIST_HEAD(free_lock_classes);
  281. /**
  282. * struct pending_free - information about data structures about to be freed
  283. * @zapped: Head of a list with struct lock_class elements.
  284. * @lock_chains_being_freed: Bitmap that indicates which lock_chains[] elements
  285. * are about to be freed.
  286. */
  287. struct pending_free {
  288. struct list_head zapped;
  289. DECLARE_BITMAP(lock_chains_being_freed, MAX_LOCKDEP_CHAINS);
  290. };
  291. /**
  292. * struct delayed_free - data structures used for delayed freeing
  293. *
  294. * A data structure for delayed freeing of data structures that may be
  295. * accessed by RCU readers at the time these were freed.
  296. *
  297. * @rcu_head: Used to schedule an RCU callback for freeing data structures.
  298. * @index: Index of @pf to which freed data structures are added.
  299. * @scheduled: Whether or not an RCU callback has been scheduled.
  300. * @pf: Array with information about data structures about to be freed.
  301. */
  302. static struct delayed_free {
  303. struct rcu_head rcu_head;
  304. int index;
  305. int scheduled;
  306. struct pending_free pf[2];
  307. } delayed_free;
  308. /*
  309. * The lockdep classes are in a hash-table as well, for fast lookup:
  310. */
  311. #define CLASSHASH_BITS (MAX_LOCKDEP_KEYS_BITS - 1)
  312. #define CLASSHASH_SIZE (1UL << CLASSHASH_BITS)
  313. #define __classhashfn(key) hash_long((unsigned long)key, CLASSHASH_BITS)
  314. #define classhashentry(key) (classhash_table + __classhashfn((key)))
  315. static struct hlist_head classhash_table[CLASSHASH_SIZE];
  316. /*
  317. * We put the lock dependency chains into a hash-table as well, to cache
  318. * their existence:
  319. */
  320. #define CHAINHASH_BITS (MAX_LOCKDEP_CHAINS_BITS-1)
  321. #define CHAINHASH_SIZE (1UL << CHAINHASH_BITS)
  322. #define __chainhashfn(chain) hash_long(chain, CHAINHASH_BITS)
  323. #define chainhashentry(chain) (chainhash_table + __chainhashfn((chain)))
  324. static struct hlist_head chainhash_table[CHAINHASH_SIZE];
  325. /*
  326. * the id of held_lock
  327. */
  328. static inline u16 hlock_id(struct held_lock *hlock)
  329. {
  330. BUILD_BUG_ON(MAX_LOCKDEP_KEYS_BITS + 2 > 16);
  331. return (hlock->class_idx | (hlock->read << MAX_LOCKDEP_KEYS_BITS));
  332. }
  333. static inline unsigned int chain_hlock_class_idx(u16 hlock_id)
  334. {
  335. return hlock_id & (MAX_LOCKDEP_KEYS - 1);
  336. }
  337. /*
  338. * The hash key of the lock dependency chains is a hash itself too:
  339. * it's a hash of all locks taken up to that lock, including that lock.
  340. * It's a 64-bit hash, because it's important for the keys to be
  341. * unique.
  342. */
  343. static inline u64 iterate_chain_key(u64 key, u32 idx)
  344. {
  345. u32 k0 = key, k1 = key >> 32;
  346. __jhash_mix(idx, k0, k1); /* Macro that modifies arguments! */
  347. return k0 | (u64)k1 << 32;
  348. }
  349. void lockdep_init_task(struct task_struct *task)
  350. {
  351. task->lockdep_depth = 0; /* no locks held yet */
  352. task->curr_chain_key = INITIAL_CHAIN_KEY;
  353. task->lockdep_recursion = 0;
  354. }
  355. static __always_inline void lockdep_recursion_inc(void)
  356. {
  357. __this_cpu_inc(lockdep_recursion);
  358. }
  359. static __always_inline void lockdep_recursion_finish(void)
  360. {
  361. if (WARN_ON_ONCE(__this_cpu_dec_return(lockdep_recursion)))
  362. __this_cpu_write(lockdep_recursion, 0);
  363. }
  364. void lockdep_set_selftest_task(struct task_struct *task)
  365. {
  366. lockdep_selftest_task_struct = task;
  367. }
  368. /*
  369. * Debugging switches:
  370. */
  371. #define VERBOSE 0
  372. #define VERY_VERBOSE 0
  373. #if VERBOSE
  374. # define HARDIRQ_VERBOSE 1
  375. # define SOFTIRQ_VERBOSE 1
  376. #else
  377. # define HARDIRQ_VERBOSE 0
  378. # define SOFTIRQ_VERBOSE 0
  379. #endif
  380. #if VERBOSE || HARDIRQ_VERBOSE || SOFTIRQ_VERBOSE
  381. /*
  382. * Quick filtering for interesting events:
  383. */
  384. static int class_filter(struct lock_class *class)
  385. {
  386. #if 0
  387. /* Example */
  388. if (class->name_version == 1 &&
  389. !strcmp(class->name, "lockname"))
  390. return 1;
  391. if (class->name_version == 1 &&
  392. !strcmp(class->name, "&struct->lockfield"))
  393. return 1;
  394. #endif
  395. /* Filter everything else. 1 would be to allow everything else */
  396. return 0;
  397. }
  398. #endif
  399. static int verbose(struct lock_class *class)
  400. {
  401. #if VERBOSE
  402. return class_filter(class);
  403. #endif
  404. return 0;
  405. }
  406. static void print_lockdep_off(const char *bug_msg)
  407. {
  408. printk(KERN_DEBUG "%s\n", bug_msg);
  409. printk(KERN_DEBUG "turning off the locking correctness validator.\n");
  410. #ifdef CONFIG_LOCK_STAT
  411. printk(KERN_DEBUG "Please attach the output of /proc/lock_stat to the bug report\n");
  412. #endif
  413. }
  414. unsigned long nr_stack_trace_entries;
  415. #ifdef CONFIG_PROVE_LOCKING
  416. /**
  417. * struct lock_trace - single stack backtrace
  418. * @hash_entry: Entry in a stack_trace_hash[] list.
  419. * @hash: jhash() of @entries.
  420. * @nr_entries: Number of entries in @entries.
  421. * @entries: Actual stack backtrace.
  422. */
  423. struct lock_trace {
  424. struct hlist_node hash_entry;
  425. u32 hash;
  426. u32 nr_entries;
  427. unsigned long entries[] __aligned(sizeof(unsigned long));
  428. };
  429. #define LOCK_TRACE_SIZE_IN_LONGS \
  430. (sizeof(struct lock_trace) / sizeof(unsigned long))
  431. /*
  432. * Stack-trace: sequence of lock_trace structures. Protected by the graph_lock.
  433. */
  434. static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES];
  435. static struct hlist_head stack_trace_hash[STACK_TRACE_HASH_SIZE];
  436. static bool traces_identical(struct lock_trace *t1, struct lock_trace *t2)
  437. {
  438. return t1->hash == t2->hash && t1->nr_entries == t2->nr_entries &&
  439. memcmp(t1->entries, t2->entries,
  440. t1->nr_entries * sizeof(t1->entries[0])) == 0;
  441. }
  442. static struct lock_trace *save_trace(void)
  443. {
  444. struct lock_trace *trace, *t2;
  445. struct hlist_head *hash_head;
  446. u32 hash;
  447. int max_entries;
  448. BUILD_BUG_ON_NOT_POWER_OF_2(STACK_TRACE_HASH_SIZE);
  449. BUILD_BUG_ON(LOCK_TRACE_SIZE_IN_LONGS >= MAX_STACK_TRACE_ENTRIES);
  450. trace = (struct lock_trace *)(stack_trace + nr_stack_trace_entries);
  451. max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries -
  452. LOCK_TRACE_SIZE_IN_LONGS;
  453. if (max_entries <= 0) {
  454. if (!debug_locks_off_graph_unlock())
  455. return NULL;
  456. print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!");
  457. dump_stack();
  458. return NULL;
  459. }
  460. trace->nr_entries = stack_trace_save(trace->entries, max_entries, 3);
  461. hash = jhash(trace->entries, trace->nr_entries *
  462. sizeof(trace->entries[0]), 0);
  463. trace->hash = hash;
  464. hash_head = stack_trace_hash + (hash & (STACK_TRACE_HASH_SIZE - 1));
  465. hlist_for_each_entry(t2, hash_head, hash_entry) {
  466. if (traces_identical(trace, t2))
  467. return t2;
  468. }
  469. nr_stack_trace_entries += LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries;
  470. hlist_add_head(&trace->hash_entry, hash_head);
  471. return trace;
  472. }
  473. /* Return the number of stack traces in the stack_trace[] array. */
  474. u64 lockdep_stack_trace_count(void)
  475. {
  476. struct lock_trace *trace;
  477. u64 c = 0;
  478. int i;
  479. for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++) {
  480. hlist_for_each_entry(trace, &stack_trace_hash[i], hash_entry) {
  481. c++;
  482. }
  483. }
  484. return c;
  485. }
  486. /* Return the number of stack hash chains that have at least one stack trace. */
  487. u64 lockdep_stack_hash_count(void)
  488. {
  489. u64 c = 0;
  490. int i;
  491. for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++)
  492. if (!hlist_empty(&stack_trace_hash[i]))
  493. c++;
  494. return c;
  495. }
  496. #endif
  497. unsigned int nr_hardirq_chains;
  498. unsigned int nr_softirq_chains;
  499. unsigned int nr_process_chains;
  500. unsigned int max_lockdep_depth;
  501. #ifdef CONFIG_DEBUG_LOCKDEP
  502. /*
  503. * Various lockdep statistics:
  504. */
  505. DEFINE_PER_CPU(struct lockdep_stats, lockdep_stats);
  506. #endif
  507. #ifdef CONFIG_PROVE_LOCKING
  508. /*
  509. * Locking printouts:
  510. */
  511. #define __USAGE(__STATE) \
  512. [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE)"-W", \
  513. [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON-W", \
  514. [LOCK_USED_IN_##__STATE##_READ] = "IN-"__stringify(__STATE)"-R",\
  515. [LOCK_ENABLED_##__STATE##_READ] = __stringify(__STATE)"-ON-R",
  516. static const char *usage_str[] =
  517. {
  518. #define LOCKDEP_STATE(__STATE) __USAGE(__STATE)
  519. #include "lockdep_states.h"
  520. #undef LOCKDEP_STATE
  521. [LOCK_USED] = "INITIAL USE",
  522. [LOCK_USED_READ] = "INITIAL READ USE",
  523. /* abused as string storage for verify_lock_unused() */
  524. [LOCK_USAGE_STATES] = "IN-NMI",
  525. };
  526. #endif
  527. const char *__get_key_name(const struct lockdep_subclass_key *key, char *str)
  528. {
  529. return kallsyms_lookup((unsigned long)key, NULL, NULL, NULL, str);
  530. }
  531. static inline unsigned long lock_flag(enum lock_usage_bit bit)
  532. {
  533. return 1UL << bit;
  534. }
  535. static char get_usage_char(struct lock_class *class, enum lock_usage_bit bit)
  536. {
  537. /*
  538. * The usage character defaults to '.' (i.e., irqs disabled and not in
  539. * irq context), which is the safest usage category.
  540. */
  541. char c = '.';
  542. /*
  543. * The order of the following usage checks matters, which will
  544. * result in the outcome character as follows:
  545. *
  546. * - '+': irq is enabled and not in irq context
  547. * - '-': in irq context and irq is disabled
  548. * - '?': in irq context and irq is enabled
  549. */
  550. if (class->usage_mask & lock_flag(bit + LOCK_USAGE_DIR_MASK)) {
  551. c = '+';
  552. if (class->usage_mask & lock_flag(bit))
  553. c = '?';
  554. } else if (class->usage_mask & lock_flag(bit))
  555. c = '-';
  556. return c;
  557. }
  558. void get_usage_chars(struct lock_class *class, char usage[LOCK_USAGE_CHARS])
  559. {
  560. int i = 0;
  561. #define LOCKDEP_STATE(__STATE) \
  562. usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE); \
  563. usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_READ);
  564. #include "lockdep_states.h"
  565. #undef LOCKDEP_STATE
  566. usage[i] = '\0';
  567. }
  568. static void __print_lock_name(struct lock_class *class)
  569. {
  570. char str[KSYM_NAME_LEN];
  571. const char *name;
  572. name = class->name;
  573. if (!name) {
  574. name = __get_key_name(class->key, str);
  575. printk(KERN_CONT "%s", name);
  576. } else {
  577. printk(KERN_CONT "%s", name);
  578. if (class->name_version > 1)
  579. printk(KERN_CONT "#%d", class->name_version);
  580. if (class->subclass)
  581. printk(KERN_CONT "/%d", class->subclass);
  582. }
  583. }
  584. static void print_lock_name(struct lock_class *class)
  585. {
  586. char usage[LOCK_USAGE_CHARS];
  587. get_usage_chars(class, usage);
  588. printk(KERN_CONT " (");
  589. __print_lock_name(class);
  590. printk(KERN_CONT "){%s}-{%d:%d}", usage,
  591. class->wait_type_outer ?: class->wait_type_inner,
  592. class->wait_type_inner);
  593. }
  594. static void print_lockdep_cache(struct lockdep_map *lock)
  595. {
  596. const char *name;
  597. char str[KSYM_NAME_LEN];
  598. name = lock->name;
  599. if (!name)
  600. name = __get_key_name(lock->key->subkeys, str);
  601. printk(KERN_CONT "%s", name);
  602. }
  603. static void print_lock(struct held_lock *hlock)
  604. {
  605. /*
  606. * We can be called locklessly through debug_show_all_locks() so be
  607. * extra careful, the hlock might have been released and cleared.
  608. *
  609. * If this indeed happens, lets pretend it does not hurt to continue
  610. * to print the lock unless the hlock class_idx does not point to a
  611. * registered class. The rationale here is: since we don't attempt
  612. * to distinguish whether we are in this situation, if it just
  613. * happened we can't count on class_idx to tell either.
  614. */
  615. struct lock_class *lock = hlock_class(hlock);
  616. if (!lock) {
  617. printk(KERN_CONT "<RELEASED>\n");
  618. return;
  619. }
  620. printk(KERN_CONT "%px", hlock->instance);
  621. print_lock_name(lock);
  622. printk(KERN_CONT ", at: %pS\n", (void *)hlock->acquire_ip);
  623. }
  624. static void lockdep_print_held_locks(struct task_struct *p)
  625. {
  626. int i, depth = READ_ONCE(p->lockdep_depth);
  627. if (!depth)
  628. printk("no locks held by %s/%d.\n", p->comm, task_pid_nr(p));
  629. else
  630. printk("%d lock%s held by %s/%d:\n", depth,
  631. depth > 1 ? "s" : "", p->comm, task_pid_nr(p));
  632. /*
  633. * It's not reliable to print a task's held locks if it's not sleeping
  634. * and it's not the current task.
  635. */
  636. if (p->state == TASK_RUNNING && p != current)
  637. return;
  638. for (i = 0; i < depth; i++) {
  639. printk(" #%d: ", i);
  640. print_lock(p->held_locks + i);
  641. }
  642. }
  643. static void print_kernel_ident(void)
  644. {
  645. printk("%s %.*s %s\n", init_utsname()->release,
  646. (int)strcspn(init_utsname()->version, " "),
  647. init_utsname()->version,
  648. print_tainted());
  649. }
  650. static int very_verbose(struct lock_class *class)
  651. {
  652. #if VERY_VERBOSE
  653. return class_filter(class);
  654. #endif
  655. return 0;
  656. }
  657. /*
  658. * Is this the address of a static object:
  659. */
  660. #ifdef __KERNEL__
  661. static int static_obj(const void *obj)
  662. {
  663. unsigned long start = (unsigned long) &_stext,
  664. end = (unsigned long) &_end,
  665. addr = (unsigned long) obj;
  666. if (arch_is_kernel_initmem_freed(addr))
  667. return 0;
  668. /*
  669. * static variable?
  670. */
  671. if ((addr >= start) && (addr < end))
  672. return 1;
  673. if (arch_is_kernel_data(addr))
  674. return 1;
  675. /*
  676. * in-kernel percpu var?
  677. */
  678. if (is_kernel_percpu_address(addr))
  679. return 1;
  680. /*
  681. * module static or percpu var?
  682. */
  683. return is_module_address(addr) || is_module_percpu_address(addr);
  684. }
  685. #endif
  686. /*
  687. * To make lock name printouts unique, we calculate a unique
  688. * class->name_version generation counter. The caller must hold the graph
  689. * lock.
  690. */
  691. static int count_matching_names(struct lock_class *new_class)
  692. {
  693. struct lock_class *class;
  694. int count = 0;
  695. if (!new_class->name)
  696. return 0;
  697. list_for_each_entry(class, &all_lock_classes, lock_entry) {
  698. if (new_class->key - new_class->subclass == class->key)
  699. return class->name_version;
  700. if (class->name && !strcmp(class->name, new_class->name))
  701. count = max(count, class->name_version);
  702. }
  703. return count + 1;
  704. }
  705. /* used from NMI context -- must be lockless */
  706. static noinstr struct lock_class *
  707. look_up_lock_class(const struct lockdep_map *lock, unsigned int subclass)
  708. {
  709. struct lockdep_subclass_key *key;
  710. struct hlist_head *hash_head;
  711. struct lock_class *class;
  712. if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
  713. instrumentation_begin();
  714. debug_locks_off();
  715. printk(KERN_ERR
  716. "BUG: looking up invalid subclass: %u\n", subclass);
  717. printk(KERN_ERR
  718. "turning off the locking correctness validator.\n");
  719. dump_stack();
  720. instrumentation_end();
  721. return NULL;
  722. }
  723. /*
  724. * If it is not initialised then it has never been locked,
  725. * so it won't be present in the hash table.
  726. */
  727. if (unlikely(!lock->key))
  728. return NULL;
  729. /*
  730. * NOTE: the class-key must be unique. For dynamic locks, a static
  731. * lock_class_key variable is passed in through the mutex_init()
  732. * (or spin_lock_init()) call - which acts as the key. For static
  733. * locks we use the lock object itself as the key.
  734. */
  735. BUILD_BUG_ON(sizeof(struct lock_class_key) >
  736. sizeof(struct lockdep_map));
  737. key = lock->key->subkeys + subclass;
  738. hash_head = classhashentry(key);
  739. /*
  740. * We do an RCU walk of the hash, see lockdep_free_key_range().
  741. */
  742. if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
  743. return NULL;
  744. hlist_for_each_entry_rcu_notrace(class, hash_head, hash_entry) {
  745. if (class->key == key) {
  746. /*
  747. * Huh! same key, different name? Did someone trample
  748. * on some memory? We're most confused.
  749. */
  750. WARN_ON_ONCE(class->name != lock->name &&
  751. lock->key != &__lockdep_no_validate__);
  752. return class;
  753. }
  754. }
  755. return NULL;
  756. }
  757. /*
  758. * Static locks do not have their class-keys yet - for them the key is
  759. * the lock object itself. If the lock is in the per cpu area, the
  760. * canonical address of the lock (per cpu offset removed) is used.
  761. */
  762. static bool assign_lock_key(struct lockdep_map *lock)
  763. {
  764. unsigned long can_addr, addr = (unsigned long)lock;
  765. #ifdef __KERNEL__
  766. /*
  767. * lockdep_free_key_range() assumes that struct lock_class_key
  768. * objects do not overlap. Since we use the address of lock
  769. * objects as class key for static objects, check whether the
  770. * size of lock_class_key objects does not exceed the size of
  771. * the smallest lock object.
  772. */
  773. BUILD_BUG_ON(sizeof(struct lock_class_key) > sizeof(raw_spinlock_t));
  774. #endif
  775. if (__is_kernel_percpu_address(addr, &can_addr))
  776. lock->key = (void *)can_addr;
  777. else if (__is_module_percpu_address(addr, &can_addr))
  778. lock->key = (void *)can_addr;
  779. else if (static_obj(lock))
  780. lock->key = (void *)lock;
  781. else {
  782. /* Debug-check: all keys must be persistent! */
  783. debug_locks_off();
  784. pr_err("INFO: trying to register non-static key.\n");
  785. pr_err("The code is fine but needs lockdep annotation, or maybe\n");
  786. pr_err("you didn't initialize this object before use?\n");
  787. pr_err("turning off the locking correctness validator.\n");
  788. dump_stack();
  789. return false;
  790. }
  791. return true;
  792. }
  793. #ifdef CONFIG_DEBUG_LOCKDEP
  794. /* Check whether element @e occurs in list @h */
  795. static bool in_list(struct list_head *e, struct list_head *h)
  796. {
  797. struct list_head *f;
  798. list_for_each(f, h) {
  799. if (e == f)
  800. return true;
  801. }
  802. return false;
  803. }
  804. /*
  805. * Check whether entry @e occurs in any of the locks_after or locks_before
  806. * lists.
  807. */
  808. static bool in_any_class_list(struct list_head *e)
  809. {
  810. struct lock_class *class;
  811. int i;
  812. for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
  813. class = &lock_classes[i];
  814. if (in_list(e, &class->locks_after) ||
  815. in_list(e, &class->locks_before))
  816. return true;
  817. }
  818. return false;
  819. }
  820. static bool class_lock_list_valid(struct lock_class *c, struct list_head *h)
  821. {
  822. struct lock_list *e;
  823. list_for_each_entry(e, h, entry) {
  824. if (e->links_to != c) {
  825. printk(KERN_INFO "class %s: mismatch for lock entry %ld; class %s <> %s",
  826. c->name ? : "(?)",
  827. (unsigned long)(e - list_entries),
  828. e->links_to && e->links_to->name ?
  829. e->links_to->name : "(?)",
  830. e->class && e->class->name ? e->class->name :
  831. "(?)");
  832. return false;
  833. }
  834. }
  835. return true;
  836. }
  837. #ifdef CONFIG_PROVE_LOCKING
  838. static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
  839. #endif
  840. static bool check_lock_chain_key(struct lock_chain *chain)
  841. {
  842. #ifdef CONFIG_PROVE_LOCKING
  843. u64 chain_key = INITIAL_CHAIN_KEY;
  844. int i;
  845. for (i = chain->base; i < chain->base + chain->depth; i++)
  846. chain_key = iterate_chain_key(chain_key, chain_hlocks[i]);
  847. /*
  848. * The 'unsigned long long' casts avoid that a compiler warning
  849. * is reported when building tools/lib/lockdep.
  850. */
  851. if (chain->chain_key != chain_key) {
  852. printk(KERN_INFO "chain %lld: key %#llx <> %#llx\n",
  853. (unsigned long long)(chain - lock_chains),
  854. (unsigned long long)chain->chain_key,
  855. (unsigned long long)chain_key);
  856. return false;
  857. }
  858. #endif
  859. return true;
  860. }
  861. static bool in_any_zapped_class_list(struct lock_class *class)
  862. {
  863. struct pending_free *pf;
  864. int i;
  865. for (i = 0, pf = delayed_free.pf; i < ARRAY_SIZE(delayed_free.pf); i++, pf++) {
  866. if (in_list(&class->lock_entry, &pf->zapped))
  867. return true;
  868. }
  869. return false;
  870. }
  871. static bool __check_data_structures(void)
  872. {
  873. struct lock_class *class;
  874. struct lock_chain *chain;
  875. struct hlist_head *head;
  876. struct lock_list *e;
  877. int i;
  878. /* Check whether all classes occur in a lock list. */
  879. for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
  880. class = &lock_classes[i];
  881. if (!in_list(&class->lock_entry, &all_lock_classes) &&
  882. !in_list(&class->lock_entry, &free_lock_classes) &&
  883. !in_any_zapped_class_list(class)) {
  884. printk(KERN_INFO "class %px/%s is not in any class list\n",
  885. class, class->name ? : "(?)");
  886. return false;
  887. }
  888. }
  889. /* Check whether all classes have valid lock lists. */
  890. for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
  891. class = &lock_classes[i];
  892. if (!class_lock_list_valid(class, &class->locks_before))
  893. return false;
  894. if (!class_lock_list_valid(class, &class->locks_after))
  895. return false;
  896. }
  897. /* Check the chain_key of all lock chains. */
  898. for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
  899. head = chainhash_table + i;
  900. hlist_for_each_entry_rcu(chain, head, entry) {
  901. if (!check_lock_chain_key(chain))
  902. return false;
  903. }
  904. }
  905. /*
  906. * Check whether all list entries that are in use occur in a class
  907. * lock list.
  908. */
  909. for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
  910. e = list_entries + i;
  911. if (!in_any_class_list(&e->entry)) {
  912. printk(KERN_INFO "list entry %d is not in any class list; class %s <> %s\n",
  913. (unsigned int)(e - list_entries),
  914. e->class->name ? : "(?)",
  915. e->links_to->name ? : "(?)");
  916. return false;
  917. }
  918. }
  919. /*
  920. * Check whether all list entries that are not in use do not occur in
  921. * a class lock list.
  922. */
  923. for_each_clear_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
  924. e = list_entries + i;
  925. if (in_any_class_list(&e->entry)) {
  926. printk(KERN_INFO "list entry %d occurs in a class list; class %s <> %s\n",
  927. (unsigned int)(e - list_entries),
  928. e->class && e->class->name ? e->class->name :
  929. "(?)",
  930. e->links_to && e->links_to->name ?
  931. e->links_to->name : "(?)");
  932. return false;
  933. }
  934. }
  935. return true;
  936. }
  937. int check_consistency = 0;
  938. module_param(check_consistency, int, 0644);
  939. static void check_data_structures(void)
  940. {
  941. static bool once = false;
  942. if (check_consistency && !once) {
  943. if (!__check_data_structures()) {
  944. once = true;
  945. WARN_ON(once);
  946. }
  947. }
  948. }
  949. #else /* CONFIG_DEBUG_LOCKDEP */
  950. static inline void check_data_structures(void) { }
  951. #endif /* CONFIG_DEBUG_LOCKDEP */
  952. static void init_chain_block_buckets(void);
  953. /*
  954. * Initialize the lock_classes[] array elements, the free_lock_classes list
  955. * and also the delayed_free structure.
  956. */
  957. static void init_data_structures_once(void)
  958. {
  959. static bool __read_mostly ds_initialized, rcu_head_initialized;
  960. int i;
  961. if (likely(rcu_head_initialized))
  962. return;
  963. if (system_state >= SYSTEM_SCHEDULING) {
  964. init_rcu_head(&delayed_free.rcu_head);
  965. rcu_head_initialized = true;
  966. }
  967. if (ds_initialized)
  968. return;
  969. ds_initialized = true;
  970. INIT_LIST_HEAD(&delayed_free.pf[0].zapped);
  971. INIT_LIST_HEAD(&delayed_free.pf[1].zapped);
  972. for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
  973. list_add_tail(&lock_classes[i].lock_entry, &free_lock_classes);
  974. INIT_LIST_HEAD(&lock_classes[i].locks_after);
  975. INIT_LIST_HEAD(&lock_classes[i].locks_before);
  976. }
  977. init_chain_block_buckets();
  978. }
  979. static inline struct hlist_head *keyhashentry(const struct lock_class_key *key)
  980. {
  981. unsigned long hash = hash_long((uintptr_t)key, KEYHASH_BITS);
  982. return lock_keys_hash + hash;
  983. }
  984. /* Register a dynamically allocated key. */
  985. void lockdep_register_key(struct lock_class_key *key)
  986. {
  987. struct hlist_head *hash_head;
  988. struct lock_class_key *k;
  989. unsigned long flags;
  990. if (WARN_ON_ONCE(static_obj(key)))
  991. return;
  992. hash_head = keyhashentry(key);
  993. raw_local_irq_save(flags);
  994. if (!graph_lock())
  995. goto restore_irqs;
  996. hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
  997. if (WARN_ON_ONCE(k == key))
  998. goto out_unlock;
  999. }
  1000. hlist_add_head_rcu(&key->hash_entry, hash_head);
  1001. out_unlock:
  1002. graph_unlock();
  1003. restore_irqs:
  1004. raw_local_irq_restore(flags);
  1005. }
  1006. EXPORT_SYMBOL_GPL(lockdep_register_key);
  1007. /* Check whether a key has been registered as a dynamic key. */
  1008. static bool is_dynamic_key(const struct lock_class_key *key)
  1009. {
  1010. struct hlist_head *hash_head;
  1011. struct lock_class_key *k;
  1012. bool found = false;
  1013. if (WARN_ON_ONCE(static_obj(key)))
  1014. return false;
  1015. /*
  1016. * If lock debugging is disabled lock_keys_hash[] may contain
  1017. * pointers to memory that has already been freed. Avoid triggering
  1018. * a use-after-free in that case by returning early.
  1019. */
  1020. if (!debug_locks)
  1021. return true;
  1022. hash_head = keyhashentry(key);
  1023. rcu_read_lock();
  1024. hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
  1025. if (k == key) {
  1026. found = true;
  1027. break;
  1028. }
  1029. }
  1030. rcu_read_unlock();
  1031. return found;
  1032. }
  1033. /*
  1034. * Register a lock's class in the hash-table, if the class is not present
  1035. * yet. Otherwise we look it up. We cache the result in the lock object
  1036. * itself, so actual lookup of the hash should be once per lock object.
  1037. */
  1038. static struct lock_class *
  1039. register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
  1040. {
  1041. struct lockdep_subclass_key *key;
  1042. struct hlist_head *hash_head;
  1043. struct lock_class *class;
  1044. int idx;
  1045. DEBUG_LOCKS_WARN_ON(!irqs_disabled());
  1046. class = look_up_lock_class(lock, subclass);
  1047. if (likely(class))
  1048. goto out_set_class_cache;
  1049. if (!lock->key) {
  1050. if (!assign_lock_key(lock))
  1051. return NULL;
  1052. } else if (!static_obj(lock->key) && !is_dynamic_key(lock->key)) {
  1053. return NULL;
  1054. }
  1055. key = lock->key->subkeys + subclass;
  1056. hash_head = classhashentry(key);
  1057. if (!graph_lock()) {
  1058. return NULL;
  1059. }
  1060. /*
  1061. * We have to do the hash-walk again, to avoid races
  1062. * with another CPU:
  1063. */
  1064. hlist_for_each_entry_rcu(class, hash_head, hash_entry) {
  1065. if (class->key == key)
  1066. goto out_unlock_set;
  1067. }
  1068. init_data_structures_once();
  1069. /* Allocate a new lock class and add it to the hash. */
  1070. class = list_first_entry_or_null(&free_lock_classes, typeof(*class),
  1071. lock_entry);
  1072. if (!class) {
  1073. if (!debug_locks_off_graph_unlock()) {
  1074. return NULL;
  1075. }
  1076. print_lockdep_off("BUG: MAX_LOCKDEP_KEYS too low!");
  1077. dump_stack();
  1078. return NULL;
  1079. }
  1080. nr_lock_classes++;
  1081. __set_bit(class - lock_classes, lock_classes_in_use);
  1082. debug_atomic_inc(nr_unused_locks);
  1083. class->key = key;
  1084. class->name = lock->name;
  1085. class->subclass = subclass;
  1086. WARN_ON_ONCE(!list_empty(&class->locks_before));
  1087. WARN_ON_ONCE(!list_empty(&class->locks_after));
  1088. class->name_version = count_matching_names(class);
  1089. class->wait_type_inner = lock->wait_type_inner;
  1090. class->wait_type_outer = lock->wait_type_outer;
  1091. class->lock_type = lock->lock_type;
  1092. /*
  1093. * We use RCU's safe list-add method to make
  1094. * parallel walking of the hash-list safe:
  1095. */
  1096. hlist_add_head_rcu(&class->hash_entry, hash_head);
  1097. /*
  1098. * Remove the class from the free list and add it to the global list
  1099. * of classes.
  1100. */
  1101. list_move_tail(&class->lock_entry, &all_lock_classes);
  1102. idx = class - lock_classes;
  1103. if (idx > max_lock_class_idx)
  1104. max_lock_class_idx = idx;
  1105. if (verbose(class)) {
  1106. graph_unlock();
  1107. printk("\nnew class %px: %s", class->key, class->name);
  1108. if (class->name_version > 1)
  1109. printk(KERN_CONT "#%d", class->name_version);
  1110. printk(KERN_CONT "\n");
  1111. dump_stack();
  1112. if (!graph_lock()) {
  1113. return NULL;
  1114. }
  1115. }
  1116. out_unlock_set:
  1117. graph_unlock();
  1118. out_set_class_cache:
  1119. if (!subclass || force)
  1120. lock->class_cache[0] = class;
  1121. else if (subclass < NR_LOCKDEP_CACHING_CLASSES)
  1122. lock->class_cache[subclass] = class;
  1123. /*
  1124. * Hash collision, did we smoke some? We found a class with a matching
  1125. * hash but the subclass -- which is hashed in -- didn't match.
  1126. */
  1127. if (DEBUG_LOCKS_WARN_ON(class->subclass != subclass))
  1128. return NULL;
  1129. return class;
  1130. }
  1131. #ifdef CONFIG_PROVE_LOCKING
  1132. /*
  1133. * Allocate a lockdep entry. (assumes the graph_lock held, returns
  1134. * with NULL on failure)
  1135. */
  1136. static struct lock_list *alloc_list_entry(void)
  1137. {
  1138. int idx = find_first_zero_bit(list_entries_in_use,
  1139. ARRAY_SIZE(list_entries));
  1140. if (idx >= ARRAY_SIZE(list_entries)) {
  1141. if (!debug_locks_off_graph_unlock())
  1142. return NULL;
  1143. print_lockdep_off("BUG: MAX_LOCKDEP_ENTRIES too low!");
  1144. dump_stack();
  1145. return NULL;
  1146. }
  1147. nr_list_entries++;
  1148. __set_bit(idx, list_entries_in_use);
  1149. return list_entries + idx;
  1150. }
  1151. /*
  1152. * Add a new dependency to the head of the list:
  1153. */
  1154. static int add_lock_to_list(struct lock_class *this,
  1155. struct lock_class *links_to, struct list_head *head,
  1156. unsigned long ip, u16 distance, u8 dep,
  1157. const struct lock_trace *trace)
  1158. {
  1159. struct lock_list *entry;
  1160. /*
  1161. * Lock not present yet - get a new dependency struct and
  1162. * add it to the list:
  1163. */
  1164. entry = alloc_list_entry();
  1165. if (!entry)
  1166. return 0;
  1167. entry->class = this;
  1168. entry->links_to = links_to;
  1169. entry->dep = dep;
  1170. entry->distance = distance;
  1171. entry->trace = trace;
  1172. /*
  1173. * Both allocation and removal are done under the graph lock; but
  1174. * iteration is under RCU-sched; see look_up_lock_class() and
  1175. * lockdep_free_key_range().
  1176. */
  1177. list_add_tail_rcu(&entry->entry, head);
  1178. return 1;
  1179. }
  1180. /*
  1181. * For good efficiency of modular, we use power of 2
  1182. */
  1183. #define MAX_CIRCULAR_QUEUE_SIZE 4096UL
  1184. #define CQ_MASK (MAX_CIRCULAR_QUEUE_SIZE-1)
  1185. /*
  1186. * The circular_queue and helpers are used to implement graph
  1187. * breadth-first search (BFS) algorithm, by which we can determine
  1188. * whether there is a path from a lock to another. In deadlock checks,
  1189. * a path from the next lock to be acquired to a previous held lock
  1190. * indicates that adding the <prev> -> <next> lock dependency will
  1191. * produce a circle in the graph. Breadth-first search instead of
  1192. * depth-first search is used in order to find the shortest (circular)
  1193. * path.
  1194. */
  1195. struct circular_queue {
  1196. struct lock_list *element[MAX_CIRCULAR_QUEUE_SIZE];
  1197. unsigned int front, rear;
  1198. };
  1199. static struct circular_queue lock_cq;
  1200. unsigned int max_bfs_queue_depth;
  1201. static unsigned int lockdep_dependency_gen_id;
  1202. static inline void __cq_init(struct circular_queue *cq)
  1203. {
  1204. cq->front = cq->rear = 0;
  1205. lockdep_dependency_gen_id++;
  1206. }
  1207. static inline int __cq_empty(struct circular_queue *cq)
  1208. {
  1209. return (cq->front == cq->rear);
  1210. }
  1211. static inline int __cq_full(struct circular_queue *cq)
  1212. {
  1213. return ((cq->rear + 1) & CQ_MASK) == cq->front;
  1214. }
  1215. static inline int __cq_enqueue(struct circular_queue *cq, struct lock_list *elem)
  1216. {
  1217. if (__cq_full(cq))
  1218. return -1;
  1219. cq->element[cq->rear] = elem;
  1220. cq->rear = (cq->rear + 1) & CQ_MASK;
  1221. return 0;
  1222. }
  1223. /*
  1224. * Dequeue an element from the circular_queue, return a lock_list if
  1225. * the queue is not empty, or NULL if otherwise.
  1226. */
  1227. static inline struct lock_list * __cq_dequeue(struct circular_queue *cq)
  1228. {
  1229. struct lock_list * lock;
  1230. if (__cq_empty(cq))
  1231. return NULL;
  1232. lock = cq->element[cq->front];
  1233. cq->front = (cq->front + 1) & CQ_MASK;
  1234. return lock;
  1235. }
  1236. static inline unsigned int __cq_get_elem_count(struct circular_queue *cq)
  1237. {
  1238. return (cq->rear - cq->front) & CQ_MASK;
  1239. }
  1240. static inline void mark_lock_accessed(struct lock_list *lock)
  1241. {
  1242. lock->class->dep_gen_id = lockdep_dependency_gen_id;
  1243. }
  1244. static inline void visit_lock_entry(struct lock_list *lock,
  1245. struct lock_list *parent)
  1246. {
  1247. lock->parent = parent;
  1248. }
  1249. static inline unsigned long lock_accessed(struct lock_list *lock)
  1250. {
  1251. return lock->class->dep_gen_id == lockdep_dependency_gen_id;
  1252. }
  1253. static inline struct lock_list *get_lock_parent(struct lock_list *child)
  1254. {
  1255. return child->parent;
  1256. }
  1257. static inline int get_lock_depth(struct lock_list *child)
  1258. {
  1259. int depth = 0;
  1260. struct lock_list *parent;
  1261. while ((parent = get_lock_parent(child))) {
  1262. child = parent;
  1263. depth++;
  1264. }
  1265. return depth;
  1266. }
  1267. /*
  1268. * Return the forward or backward dependency list.
  1269. *
  1270. * @lock: the lock_list to get its class's dependency list
  1271. * @offset: the offset to struct lock_class to determine whether it is
  1272. * locks_after or locks_before
  1273. */
  1274. static inline struct list_head *get_dep_list(struct lock_list *lock, int offset)
  1275. {
  1276. void *lock_class = lock->class;
  1277. return lock_class + offset;
  1278. }
  1279. /*
  1280. * Return values of a bfs search:
  1281. *
  1282. * BFS_E* indicates an error
  1283. * BFS_R* indicates a result (match or not)
  1284. *
  1285. * BFS_EINVALIDNODE: Find a invalid node in the graph.
  1286. *
  1287. * BFS_EQUEUEFULL: The queue is full while doing the bfs.
  1288. *
  1289. * BFS_RMATCH: Find the matched node in the graph, and put that node into
  1290. * *@target_entry.
  1291. *
  1292. * BFS_RNOMATCH: Haven't found the matched node and keep *@target_entry
  1293. * _unchanged_.
  1294. */
  1295. enum bfs_result {
  1296. BFS_EINVALIDNODE = -2,
  1297. BFS_EQUEUEFULL = -1,
  1298. BFS_RMATCH = 0,
  1299. BFS_RNOMATCH = 1,
  1300. };
  1301. /*
  1302. * bfs_result < 0 means error
  1303. */
  1304. static inline bool bfs_error(enum bfs_result res)
  1305. {
  1306. return res < 0;
  1307. }
  1308. /*
  1309. * DEP_*_BIT in lock_list::dep
  1310. *
  1311. * For dependency @prev -> @next:
  1312. *
  1313. * SR: @prev is shared reader (->read != 0) and @next is recursive reader
  1314. * (->read == 2)
  1315. * ER: @prev is exclusive locker (->read == 0) and @next is recursive reader
  1316. * SN: @prev is shared reader and @next is non-recursive locker (->read != 2)
  1317. * EN: @prev is exclusive locker and @next is non-recursive locker
  1318. *
  1319. * Note that we define the value of DEP_*_BITs so that:
  1320. * bit0 is prev->read == 0
  1321. * bit1 is next->read != 2
  1322. */
  1323. #define DEP_SR_BIT (0 + (0 << 1)) /* 0 */
  1324. #define DEP_ER_BIT (1 + (0 << 1)) /* 1 */
  1325. #define DEP_SN_BIT (0 + (1 << 1)) /* 2 */
  1326. #define DEP_EN_BIT (1 + (1 << 1)) /* 3 */
  1327. #define DEP_SR_MASK (1U << (DEP_SR_BIT))
  1328. #define DEP_ER_MASK (1U << (DEP_ER_BIT))
  1329. #define DEP_SN_MASK (1U << (DEP_SN_BIT))
  1330. #define DEP_EN_MASK (1U << (DEP_EN_BIT))
  1331. static inline unsigned int
  1332. __calc_dep_bit(struct held_lock *prev, struct held_lock *next)
  1333. {
  1334. return (prev->read == 0) + ((next->read != 2) << 1);
  1335. }
  1336. static inline u8 calc_dep(struct held_lock *prev, struct held_lock *next)
  1337. {
  1338. return 1U << __calc_dep_bit(prev, next);
  1339. }
  1340. /*
  1341. * calculate the dep_bit for backwards edges. We care about whether @prev is
  1342. * shared and whether @next is recursive.
  1343. */
  1344. static inline unsigned int
  1345. __calc_dep_bitb(struct held_lock *prev, struct held_lock *next)
  1346. {
  1347. return (next->read != 2) + ((prev->read == 0) << 1);
  1348. }
  1349. static inline u8 calc_depb(struct held_lock *prev, struct held_lock *next)
  1350. {
  1351. return 1U << __calc_dep_bitb(prev, next);
  1352. }
  1353. /*
  1354. * Initialize a lock_list entry @lock belonging to @class as the root for a BFS
  1355. * search.
  1356. */
  1357. static inline void __bfs_init_root(struct lock_list *lock,
  1358. struct lock_class *class)
  1359. {
  1360. lock->class = class;
  1361. lock->parent = NULL;
  1362. lock->only_xr = 0;
  1363. }
  1364. /*
  1365. * Initialize a lock_list entry @lock based on a lock acquisition @hlock as the
  1366. * root for a BFS search.
  1367. *
  1368. * ->only_xr of the initial lock node is set to @hlock->read == 2, to make sure
  1369. * that <prev> -> @hlock and @hlock -> <whatever __bfs() found> is not -(*R)->
  1370. * and -(S*)->.
  1371. */
  1372. static inline void bfs_init_root(struct lock_list *lock,
  1373. struct held_lock *hlock)
  1374. {
  1375. __bfs_init_root(lock, hlock_class(hlock));
  1376. lock->only_xr = (hlock->read == 2);
  1377. }
  1378. /*
  1379. * Similar to bfs_init_root() but initialize the root for backwards BFS.
  1380. *
  1381. * ->only_xr of the initial lock node is set to @hlock->read != 0, to make sure
  1382. * that <next> -> @hlock and @hlock -> <whatever backwards BFS found> is not
  1383. * -(*S)-> and -(R*)-> (reverse order of -(*R)-> and -(S*)->).
  1384. */
  1385. static inline void bfs_init_rootb(struct lock_list *lock,
  1386. struct held_lock *hlock)
  1387. {
  1388. __bfs_init_root(lock, hlock_class(hlock));
  1389. lock->only_xr = (hlock->read != 0);
  1390. }
  1391. static inline struct lock_list *__bfs_next(struct lock_list *lock, int offset)
  1392. {
  1393. if (!lock || !lock->parent)
  1394. return NULL;
  1395. return list_next_or_null_rcu(get_dep_list(lock->parent, offset),
  1396. &lock->entry, struct lock_list, entry);
  1397. }
  1398. /*
  1399. * Breadth-First Search to find a strong path in the dependency graph.
  1400. *
  1401. * @source_entry: the source of the path we are searching for.
  1402. * @data: data used for the second parameter of @match function
  1403. * @match: match function for the search
  1404. * @target_entry: pointer to the target of a matched path
  1405. * @offset: the offset to struct lock_class to determine whether it is
  1406. * locks_after or locks_before
  1407. *
  1408. * We may have multiple edges (considering different kinds of dependencies,
  1409. * e.g. ER and SN) between two nodes in the dependency graph. But
  1410. * only the strong dependency path in the graph is relevant to deadlocks. A
  1411. * strong dependency path is a dependency path that doesn't have two adjacent
  1412. * dependencies as -(*R)-> -(S*)->, please see:
  1413. *
  1414. * Documentation/locking/lockdep-design.rst
  1415. *
  1416. * for more explanation of the definition of strong dependency paths
  1417. *
  1418. * In __bfs(), we only traverse in the strong dependency path:
  1419. *
  1420. * In lock_list::only_xr, we record whether the previous dependency only
  1421. * has -(*R)-> in the search, and if it does (prev only has -(*R)->), we
  1422. * filter out any -(S*)-> in the current dependency and after that, the
  1423. * ->only_xr is set according to whether we only have -(*R)-> left.
  1424. */
  1425. static enum bfs_result __bfs(struct lock_list *source_entry,
  1426. void *data,
  1427. bool (*match)(struct lock_list *entry, void *data),
  1428. struct lock_list **target_entry,
  1429. int offset)
  1430. {
  1431. struct circular_queue *cq = &lock_cq;
  1432. struct lock_list *lock = NULL;
  1433. struct lock_list *entry;
  1434. struct list_head *head;
  1435. unsigned int cq_depth;
  1436. bool first;
  1437. lockdep_assert_locked();
  1438. __cq_init(cq);
  1439. __cq_enqueue(cq, source_entry);
  1440. while ((lock = __bfs_next(lock, offset)) || (lock = __cq_dequeue(cq))) {
  1441. if (!lock->class)
  1442. return BFS_EINVALIDNODE;
  1443. /*
  1444. * Step 1: check whether we already finish on this one.
  1445. *
  1446. * If we have visited all the dependencies from this @lock to
  1447. * others (iow, if we have visited all lock_list entries in
  1448. * @lock->class->locks_{after,before}) we skip, otherwise go
  1449. * and visit all the dependencies in the list and mark this
  1450. * list accessed.
  1451. */
  1452. if (lock_accessed(lock))
  1453. continue;
  1454. else
  1455. mark_lock_accessed(lock);
  1456. /*
  1457. * Step 2: check whether prev dependency and this form a strong
  1458. * dependency path.
  1459. */
  1460. if (lock->parent) { /* Parent exists, check prev dependency */
  1461. u8 dep = lock->dep;
  1462. bool prev_only_xr = lock->parent->only_xr;
  1463. /*
  1464. * Mask out all -(S*)-> if we only have *R in previous
  1465. * step, because -(*R)-> -(S*)-> don't make up a strong
  1466. * dependency.
  1467. */
  1468. if (prev_only_xr)
  1469. dep &= ~(DEP_SR_MASK | DEP_SN_MASK);
  1470. /* If nothing left, we skip */
  1471. if (!dep)
  1472. continue;
  1473. /* If there are only -(*R)-> left, set that for the next step */
  1474. lock->only_xr = !(dep & (DEP_SN_MASK | DEP_EN_MASK));
  1475. }
  1476. /*
  1477. * Step 3: we haven't visited this and there is a strong
  1478. * dependency path to this, so check with @match.
  1479. */
  1480. if (match(lock, data)) {
  1481. *target_entry = lock;
  1482. return BFS_RMATCH;
  1483. }
  1484. /*
  1485. * Step 4: if not match, expand the path by adding the
  1486. * forward or backwards dependencis in the search
  1487. *
  1488. */
  1489. first = true;
  1490. head = get_dep_list(lock, offset);
  1491. list_for_each_entry_rcu(entry, head, entry) {
  1492. visit_lock_entry(entry, lock);
  1493. /*
  1494. * Note we only enqueue the first of the list into the
  1495. * queue, because we can always find a sibling
  1496. * dependency from one (see __bfs_next()), as a result
  1497. * the space of queue is saved.
  1498. */
  1499. if (!first)
  1500. continue;
  1501. first = false;
  1502. if (__cq_enqueue(cq, entry))
  1503. return BFS_EQUEUEFULL;
  1504. cq_depth = __cq_get_elem_count(cq);
  1505. if (max_bfs_queue_depth < cq_depth)
  1506. max_bfs_queue_depth = cq_depth;
  1507. }
  1508. }
  1509. return BFS_RNOMATCH;
  1510. }
  1511. static inline enum bfs_result
  1512. __bfs_forwards(struct lock_list *src_entry,
  1513. void *data,
  1514. bool (*match)(struct lock_list *entry, void *data),
  1515. struct lock_list **target_entry)
  1516. {
  1517. return __bfs(src_entry, data, match, target_entry,
  1518. offsetof(struct lock_class, locks_after));
  1519. }
  1520. static inline enum bfs_result
  1521. __bfs_backwards(struct lock_list *src_entry,
  1522. void *data,
  1523. bool (*match)(struct lock_list *entry, void *data),
  1524. struct lock_list **target_entry)
  1525. {
  1526. return __bfs(src_entry, data, match, target_entry,
  1527. offsetof(struct lock_class, locks_before));
  1528. }
  1529. static void print_lock_trace(const struct lock_trace *trace,
  1530. unsigned int spaces)
  1531. {
  1532. stack_trace_print(trace->entries, trace->nr_entries, spaces);
  1533. }
  1534. /*
  1535. * Print a dependency chain entry (this is only done when a deadlock
  1536. * has been detected):
  1537. */
  1538. static noinline void
  1539. print_circular_bug_entry(struct lock_list *target, int depth)
  1540. {
  1541. if (debug_locks_silent)
  1542. return;
  1543. printk("\n-> #%u", depth);
  1544. print_lock_name(target->class);
  1545. printk(KERN_CONT ":\n");
  1546. print_lock_trace(target->trace, 6);
  1547. }
  1548. static void
  1549. print_circular_lock_scenario(struct held_lock *src,
  1550. struct held_lock *tgt,
  1551. struct lock_list *prt)
  1552. {
  1553. struct lock_class *source = hlock_class(src);
  1554. struct lock_class *target = hlock_class(tgt);
  1555. struct lock_class *parent = prt->class;
  1556. /*
  1557. * A direct locking problem where unsafe_class lock is taken
  1558. * directly by safe_class lock, then all we need to show
  1559. * is the deadlock scenario, as it is obvious that the
  1560. * unsafe lock is taken under the safe lock.
  1561. *
  1562. * But if there is a chain instead, where the safe lock takes
  1563. * an intermediate lock (middle_class) where this lock is
  1564. * not the same as the safe lock, then the lock chain is
  1565. * used to describe the problem. Otherwise we would need
  1566. * to show a different CPU case for each link in the chain
  1567. * from the safe_class lock to the unsafe_class lock.
  1568. */
  1569. if (parent != source) {
  1570. printk("Chain exists of:\n ");
  1571. __print_lock_name(source);
  1572. printk(KERN_CONT " --> ");
  1573. __print_lock_name(parent);
  1574. printk(KERN_CONT " --> ");
  1575. __print_lock_name(target);
  1576. printk(KERN_CONT "\n\n");
  1577. }
  1578. printk(" Possible unsafe locking scenario:\n\n");
  1579. printk(" CPU0 CPU1\n");
  1580. printk(" ---- ----\n");
  1581. printk(" lock(");
  1582. __print_lock_name(target);
  1583. printk(KERN_CONT ");\n");
  1584. printk(" lock(");
  1585. __print_lock_name(parent);
  1586. printk(KERN_CONT ");\n");
  1587. printk(" lock(");
  1588. __print_lock_name(target);
  1589. printk(KERN_CONT ");\n");
  1590. printk(" lock(");
  1591. __print_lock_name(source);
  1592. printk(KERN_CONT ");\n");
  1593. printk("\n *** DEADLOCK ***\n\n");
  1594. }
  1595. /*
  1596. * When a circular dependency is detected, print the
  1597. * header first:
  1598. */
  1599. static noinline void
  1600. print_circular_bug_header(struct lock_list *entry, unsigned int depth,
  1601. struct held_lock *check_src,
  1602. struct held_lock *check_tgt)
  1603. {
  1604. struct task_struct *curr = current;
  1605. if (debug_locks_silent)
  1606. return;
  1607. pr_warn("\n");
  1608. pr_warn("======================================================\n");
  1609. pr_warn("WARNING: possible circular locking dependency detected\n");
  1610. print_kernel_ident();
  1611. pr_warn("------------------------------------------------------\n");
  1612. pr_warn("%s/%d is trying to acquire lock:\n",
  1613. curr->comm, task_pid_nr(curr));
  1614. print_lock(check_src);
  1615. pr_warn("\nbut task is already holding lock:\n");
  1616. print_lock(check_tgt);
  1617. pr_warn("\nwhich lock already depends on the new lock.\n\n");
  1618. pr_warn("\nthe existing dependency chain (in reverse order) is:\n");
  1619. print_circular_bug_entry(entry, depth);
  1620. }
  1621. /*
  1622. * We are about to add A -> B into the dependency graph, and in __bfs() a
  1623. * strong dependency path A -> .. -> B is found: hlock_class equals
  1624. * entry->class.
  1625. *
  1626. * If A -> .. -> B can replace A -> B in any __bfs() search (means the former
  1627. * is _stronger_ than or equal to the latter), we consider A -> B as redundant.
  1628. * For example if A -> .. -> B is -(EN)-> (i.e. A -(E*)-> .. -(*N)-> B), and A
  1629. * -> B is -(ER)-> or -(EN)->, then we don't need to add A -> B into the
  1630. * dependency graph, as any strong path ..-> A -> B ->.. we can get with
  1631. * having dependency A -> B, we could already get a equivalent path ..-> A ->
  1632. * .. -> B -> .. with A -> .. -> B. Therefore A -> B is reduntant.
  1633. *
  1634. * We need to make sure both the start and the end of A -> .. -> B is not
  1635. * weaker than A -> B. For the start part, please see the comment in
  1636. * check_redundant(). For the end part, we need:
  1637. *
  1638. * Either
  1639. *
  1640. * a) A -> B is -(*R)-> (everything is not weaker than that)
  1641. *
  1642. * or
  1643. *
  1644. * b) A -> .. -> B is -(*N)-> (nothing is stronger than this)
  1645. *
  1646. */
  1647. static inline bool hlock_equal(struct lock_list *entry, void *data)
  1648. {
  1649. struct held_lock *hlock = (struct held_lock *)data;
  1650. return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */
  1651. (hlock->read == 2 || /* A -> B is -(*R)-> */
  1652. !entry->only_xr); /* A -> .. -> B is -(*N)-> */
  1653. }
  1654. /*
  1655. * We are about to add B -> A into the dependency graph, and in __bfs() a
  1656. * strong dependency path A -> .. -> B is found: hlock_class equals
  1657. * entry->class.
  1658. *
  1659. * We will have a deadlock case (conflict) if A -> .. -> B -> A is a strong
  1660. * dependency cycle, that means:
  1661. *
  1662. * Either
  1663. *
  1664. * a) B -> A is -(E*)->
  1665. *
  1666. * or
  1667. *
  1668. * b) A -> .. -> B is -(*N)-> (i.e. A -> .. -(*N)-> B)
  1669. *
  1670. * as then we don't have -(*R)-> -(S*)-> in the cycle.
  1671. */
  1672. static inline bool hlock_conflict(struct lock_list *entry, void *data)
  1673. {
  1674. struct held_lock *hlock = (struct held_lock *)data;
  1675. return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */
  1676. (hlock->read == 0 || /* B -> A is -(E*)-> */
  1677. !entry->only_xr); /* A -> .. -> B is -(*N)-> */
  1678. }
  1679. static noinline void print_circular_bug(struct lock_list *this,
  1680. struct lock_list *target,
  1681. struct held_lock *check_src,
  1682. struct held_lock *check_tgt)
  1683. {
  1684. struct task_struct *curr = current;
  1685. struct lock_list *parent;
  1686. struct lock_list *first_parent;
  1687. int depth;
  1688. if (!debug_locks_off_graph_unlock() || debug_locks_silent)
  1689. return;
  1690. this->trace = save_trace();
  1691. if (!this->trace)
  1692. return;
  1693. depth = get_lock_depth(target);
  1694. print_circular_bug_header(target, depth, check_src, check_tgt);
  1695. parent = get_lock_parent(target);
  1696. first_parent = parent;
  1697. while (parent) {
  1698. print_circular_bug_entry(parent, --depth);
  1699. parent = get_lock_parent(parent);
  1700. }
  1701. printk("\nother info that might help us debug this:\n\n");
  1702. print_circular_lock_scenario(check_src, check_tgt,
  1703. first_parent);
  1704. lockdep_print_held_locks(curr);
  1705. printk("\nstack backtrace:\n");
  1706. dump_stack();
  1707. }
  1708. static noinline void print_bfs_bug(int ret)
  1709. {
  1710. if (!debug_locks_off_graph_unlock())
  1711. return;
  1712. /*
  1713. * Breadth-first-search failed, graph got corrupted?
  1714. */
  1715. WARN(1, "lockdep bfs error:%d\n", ret);
  1716. }
  1717. static bool noop_count(struct lock_list *entry, void *data)
  1718. {
  1719. (*(unsigned long *)data)++;
  1720. return false;
  1721. }
  1722. static unsigned long __lockdep_count_forward_deps(struct lock_list *this)
  1723. {
  1724. unsigned long count = 0;
  1725. struct lock_list *target_entry;
  1726. __bfs_forwards(this, (void *)&count, noop_count, &target_entry);
  1727. return count;
  1728. }
  1729. unsigned long lockdep_count_forward_deps(struct lock_class *class)
  1730. {
  1731. unsigned long ret, flags;
  1732. struct lock_list this;
  1733. __bfs_init_root(&this, class);
  1734. raw_local_irq_save(flags);
  1735. lockdep_lock();
  1736. ret = __lockdep_count_forward_deps(&this);
  1737. lockdep_unlock();
  1738. raw_local_irq_restore(flags);
  1739. return ret;
  1740. }
  1741. static unsigned long __lockdep_count_backward_deps(struct lock_list *this)
  1742. {
  1743. unsigned long count = 0;
  1744. struct lock_list *target_entry;
  1745. __bfs_backwards(this, (void *)&count, noop_count, &target_entry);
  1746. return count;
  1747. }
  1748. unsigned long lockdep_count_backward_deps(struct lock_class *class)
  1749. {
  1750. unsigned long ret, flags;
  1751. struct lock_list this;
  1752. __bfs_init_root(&this, class);
  1753. raw_local_irq_save(flags);
  1754. lockdep_lock();
  1755. ret = __lockdep_count_backward_deps(&this);
  1756. lockdep_unlock();
  1757. raw_local_irq_restore(flags);
  1758. return ret;
  1759. }
  1760. /*
  1761. * Check that the dependency graph starting at <src> can lead to
  1762. * <target> or not.
  1763. */
  1764. static noinline enum bfs_result
  1765. check_path(struct held_lock *target, struct lock_list *src_entry,
  1766. bool (*match)(struct lock_list *entry, void *data),
  1767. struct lock_list **target_entry)
  1768. {
  1769. enum bfs_result ret;
  1770. ret = __bfs_forwards(src_entry, target, match, target_entry);
  1771. if (unlikely(bfs_error(ret)))
  1772. print_bfs_bug(ret);
  1773. return ret;
  1774. }
  1775. /*
  1776. * Prove that the dependency graph starting at <src> can not
  1777. * lead to <target>. If it can, there is a circle when adding
  1778. * <target> -> <src> dependency.
  1779. *
  1780. * Print an error and return BFS_RMATCH if it does.
  1781. */
  1782. static noinline enum bfs_result
  1783. check_noncircular(struct held_lock *src, struct held_lock *target,
  1784. struct lock_trace **const trace)
  1785. {
  1786. enum bfs_result ret;
  1787. struct lock_list *target_entry;
  1788. struct lock_list src_entry;
  1789. bfs_init_root(&src_entry, src);
  1790. debug_atomic_inc(nr_cyclic_checks);
  1791. ret = check_path(target, &src_entry, hlock_conflict, &target_entry);
  1792. if (unlikely(ret == BFS_RMATCH)) {
  1793. if (!*trace) {
  1794. /*
  1795. * If save_trace fails here, the printing might
  1796. * trigger a WARN but because of the !nr_entries it
  1797. * should not do bad things.
  1798. */
  1799. *trace = save_trace();
  1800. }
  1801. print_circular_bug(&src_entry, target_entry, src, target);
  1802. }
  1803. return ret;
  1804. }
  1805. #ifdef CONFIG_LOCKDEP_SMALL
  1806. /*
  1807. * Check that the dependency graph starting at <src> can lead to
  1808. * <target> or not. If it can, <src> -> <target> dependency is already
  1809. * in the graph.
  1810. *
  1811. * Return BFS_RMATCH if it does, or BFS_RMATCH if it does not, return BFS_E* if
  1812. * any error appears in the bfs search.
  1813. */
  1814. static noinline enum bfs_result
  1815. check_redundant(struct held_lock *src, struct held_lock *target)
  1816. {
  1817. enum bfs_result ret;
  1818. struct lock_list *target_entry;
  1819. struct lock_list src_entry;
  1820. bfs_init_root(&src_entry, src);
  1821. /*
  1822. * Special setup for check_redundant().
  1823. *
  1824. * To report redundant, we need to find a strong dependency path that
  1825. * is equal to or stronger than <src> -> <target>. So if <src> is E,
  1826. * we need to let __bfs() only search for a path starting at a -(E*)->,
  1827. * we achieve this by setting the initial node's ->only_xr to true in
  1828. * that case. And if <prev> is S, we set initial ->only_xr to false
  1829. * because both -(S*)-> (equal) and -(E*)-> (stronger) are redundant.
  1830. */
  1831. src_entry.only_xr = src->read == 0;
  1832. debug_atomic_inc(nr_redundant_checks);
  1833. ret = check_path(target, &src_entry, hlock_equal, &target_entry);
  1834. if (ret == BFS_RMATCH)
  1835. debug_atomic_inc(nr_redundant);
  1836. return ret;
  1837. }
  1838. #endif
  1839. #ifdef CONFIG_TRACE_IRQFLAGS
  1840. /*
  1841. * Forwards and backwards subgraph searching, for the purposes of
  1842. * proving that two subgraphs can be connected by a new dependency
  1843. * without creating any illegal irq-safe -> irq-unsafe lock dependency.
  1844. *
  1845. * A irq safe->unsafe deadlock happens with the following conditions:
  1846. *
  1847. * 1) We have a strong dependency path A -> ... -> B
  1848. *
  1849. * 2) and we have ENABLED_IRQ usage of B and USED_IN_IRQ usage of A, therefore
  1850. * irq can create a new dependency B -> A (consider the case that a holder
  1851. * of B gets interrupted by an irq whose handler will try to acquire A).
  1852. *
  1853. * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a
  1854. * strong circle:
  1855. *
  1856. * For the usage bits of B:
  1857. * a) if A -> B is -(*N)->, then B -> A could be any type, so any
  1858. * ENABLED_IRQ usage suffices.
  1859. * b) if A -> B is -(*R)->, then B -> A must be -(E*)->, so only
  1860. * ENABLED_IRQ_*_READ usage suffices.
  1861. *
  1862. * For the usage bits of A:
  1863. * c) if A -> B is -(E*)->, then B -> A could be any type, so any
  1864. * USED_IN_IRQ usage suffices.
  1865. * d) if A -> B is -(S*)->, then B -> A must be -(*N)->, so only
  1866. * USED_IN_IRQ_*_READ usage suffices.
  1867. */
  1868. /*
  1869. * There is a strong dependency path in the dependency graph: A -> B, and now
  1870. * we need to decide which usage bit of A should be accumulated to detect
  1871. * safe->unsafe bugs.
  1872. *
  1873. * Note that usage_accumulate() is used in backwards search, so ->only_xr
  1874. * stands for whether A -> B only has -(S*)-> (in this case ->only_xr is true).
  1875. *
  1876. * As above, if only_xr is false, which means A -> B has -(E*)-> dependency
  1877. * path, any usage of A should be considered. Otherwise, we should only
  1878. * consider _READ usage.
  1879. */
  1880. static inline bool usage_accumulate(struct lock_list *entry, void *mask)
  1881. {
  1882. if (!entry->only_xr)
  1883. *(unsigned long *)mask |= entry->class->usage_mask;
  1884. else /* Mask out _READ usage bits */
  1885. *(unsigned long *)mask |= (entry->class->usage_mask & LOCKF_IRQ);
  1886. return false;
  1887. }
  1888. /*
  1889. * There is a strong dependency path in the dependency graph: A -> B, and now
  1890. * we need to decide which usage bit of B conflicts with the usage bits of A,
  1891. * i.e. which usage bit of B may introduce safe->unsafe deadlocks.
  1892. *
  1893. * As above, if only_xr is false, which means A -> B has -(*N)-> dependency
  1894. * path, any usage of B should be considered. Otherwise, we should only
  1895. * consider _READ usage.
  1896. */
  1897. static inline bool usage_match(struct lock_list *entry, void *mask)
  1898. {
  1899. if (!entry->only_xr)
  1900. return !!(entry->class->usage_mask & *(unsigned long *)mask);
  1901. else /* Mask out _READ usage bits */
  1902. return !!((entry->class->usage_mask & LOCKF_IRQ) & *(unsigned long *)mask);
  1903. }
  1904. /*
  1905. * Find a node in the forwards-direction dependency sub-graph starting
  1906. * at @root->class that matches @bit.
  1907. *
  1908. * Return BFS_MATCH if such a node exists in the subgraph, and put that node
  1909. * into *@target_entry.
  1910. */
  1911. static enum bfs_result
  1912. find_usage_forwards(struct lock_list *root, unsigned long usage_mask,
  1913. struct lock_list **target_entry)
  1914. {
  1915. enum bfs_result result;
  1916. debug_atomic_inc(nr_find_usage_forwards_checks);
  1917. result = __bfs_forwards(root, &usage_mask, usage_match, target_entry);
  1918. return result;
  1919. }
  1920. /*
  1921. * Find a node in the backwards-direction dependency sub-graph starting
  1922. * at @root->class that matches @bit.
  1923. */
  1924. static enum bfs_result
  1925. find_usage_backwards(struct lock_list *root, unsigned long usage_mask,
  1926. struct lock_list **target_entry)
  1927. {
  1928. enum bfs_result result;
  1929. debug_atomic_inc(nr_find_usage_backwards_checks);
  1930. result = __bfs_backwards(root, &usage_mask, usage_match, target_entry);
  1931. return result;
  1932. }
  1933. static void print_lock_class_header(struct lock_class *class, int depth)
  1934. {
  1935. int bit;
  1936. printk("%*s->", depth, "");
  1937. print_lock_name(class);
  1938. #ifdef CONFIG_DEBUG_LOCKDEP
  1939. printk(KERN_CONT " ops: %lu", debug_class_ops_read(class));
  1940. #endif
  1941. printk(KERN_CONT " {\n");
  1942. for (bit = 0; bit < LOCK_TRACE_STATES; bit++) {
  1943. if (class->usage_mask & (1 << bit)) {
  1944. int len = depth;
  1945. len += printk("%*s %s", depth, "", usage_str[bit]);
  1946. len += printk(KERN_CONT " at:\n");
  1947. print_lock_trace(class->usage_traces[bit], len);
  1948. }
  1949. }
  1950. printk("%*s }\n", depth, "");
  1951. printk("%*s ... key at: [<%px>] %pS\n",
  1952. depth, "", class->key, class->key);
  1953. }
  1954. /*
  1955. * Dependency path printing:
  1956. *
  1957. * After BFS we get a lock dependency path (linked via ->parent of lock_list),
  1958. * printing out each lock in the dependency path will help on understanding how
  1959. * the deadlock could happen. Here are some details about dependency path
  1960. * printing:
  1961. *
  1962. * 1) A lock_list can be either forwards or backwards for a lock dependency,
  1963. * for a lock dependency A -> B, there are two lock_lists:
  1964. *
  1965. * a) lock_list in the ->locks_after list of A, whose ->class is B and
  1966. * ->links_to is A. In this case, we can say the lock_list is
  1967. * "A -> B" (forwards case).
  1968. *
  1969. * b) lock_list in the ->locks_before list of B, whose ->class is A
  1970. * and ->links_to is B. In this case, we can say the lock_list is
  1971. * "B <- A" (bacwards case).
  1972. *
  1973. * The ->trace of both a) and b) point to the call trace where B was
  1974. * acquired with A held.
  1975. *
  1976. * 2) A "helper" lock_list is introduced during BFS, this lock_list doesn't
  1977. * represent a certain lock dependency, it only provides an initial entry
  1978. * for BFS. For example, BFS may introduce a "helper" lock_list whose
  1979. * ->class is A, as a result BFS will search all dependencies starting with
  1980. * A, e.g. A -> B or A -> C.
  1981. *
  1982. * The notation of a forwards helper lock_list is like "-> A", which means
  1983. * we should search the forwards dependencies starting with "A", e.g A -> B
  1984. * or A -> C.
  1985. *
  1986. * The notation of a bacwards helper lock_list is like "<- B", which means
  1987. * we should search the backwards dependencies ending with "B", e.g.
  1988. * B <- A or B <- C.
  1989. */
  1990. /*
  1991. * printk the shortest lock dependencies from @root to @leaf in reverse order.
  1992. *
  1993. * We have a lock dependency path as follow:
  1994. *
  1995. * @root @leaf
  1996. * | |
  1997. * V V
  1998. * ->parent ->parent
  1999. * | lock_list | <--------- | lock_list | ... | lock_list | <--------- | lock_list |
  2000. * | -> L1 | | L1 -> L2 | ... |Ln-2 -> Ln-1| | Ln-1 -> Ln|
  2001. *
  2002. * , so it's natural that we start from @leaf and print every ->class and
  2003. * ->trace until we reach the @root.
  2004. */
  2005. static void __used
  2006. print_shortest_lock_dependencies(struct lock_list *leaf,
  2007. struct lock_list *root)
  2008. {
  2009. struct lock_list *entry = leaf;
  2010. int depth;
  2011. /*compute depth from generated tree by BFS*/
  2012. depth = get_lock_depth(leaf);
  2013. do {
  2014. print_lock_class_header(entry->class, depth);
  2015. printk("%*s ... acquired at:\n", depth, "");
  2016. print_lock_trace(entry->trace, 2);
  2017. printk("\n");
  2018. if (depth == 0 && (entry != root)) {
  2019. printk("lockdep:%s bad path found in chain graph\n", __func__);
  2020. break;
  2021. }
  2022. entry = get_lock_parent(entry);
  2023. depth--;
  2024. } while (entry && (depth >= 0));
  2025. }
  2026. /*
  2027. * printk the shortest lock dependencies from @leaf to @root.
  2028. *
  2029. * We have a lock dependency path (from a backwards search) as follow:
  2030. *
  2031. * @leaf @root
  2032. * | |
  2033. * V V
  2034. * ->parent ->parent
  2035. * | lock_list | ---------> | lock_list | ... | lock_list | ---------> | lock_list |
  2036. * | L2 <- L1 | | L3 <- L2 | ... | Ln <- Ln-1 | | <- Ln |
  2037. *
  2038. * , so when we iterate from @leaf to @root, we actually print the lock
  2039. * dependency path L1 -> L2 -> .. -> Ln in the non-reverse order.
  2040. *
  2041. * Another thing to notice here is that ->class of L2 <- L1 is L1, while the
  2042. * ->trace of L2 <- L1 is the call trace of L2, in fact we don't have the call
  2043. * trace of L1 in the dependency path, which is alright, because most of the
  2044. * time we can figure out where L1 is held from the call trace of L2.
  2045. */
  2046. static void __used
  2047. print_shortest_lock_dependencies_backwards(struct lock_list *leaf,
  2048. struct lock_list *root)
  2049. {
  2050. struct lock_list *entry = leaf;
  2051. const struct lock_trace *trace = NULL;
  2052. int depth;
  2053. /*compute depth from generated tree by BFS*/
  2054. depth = get_lock_depth(leaf);
  2055. do {
  2056. print_lock_class_header(entry->class, depth);
  2057. if (trace) {
  2058. printk("%*s ... acquired at:\n", depth, "");
  2059. print_lock_trace(trace, 2);
  2060. printk("\n");
  2061. }
  2062. /*
  2063. * Record the pointer to the trace for the next lock_list
  2064. * entry, see the comments for the function.
  2065. */
  2066. trace = entry->trace;
  2067. if (depth == 0 && (entry != root)) {
  2068. printk("lockdep:%s bad path found in chain graph\n", __func__);
  2069. break;
  2070. }
  2071. entry = get_lock_parent(entry);
  2072. depth--;
  2073. } while (entry && (depth >= 0));
  2074. }
  2075. static void
  2076. print_irq_lock_scenario(struct lock_list *safe_entry,
  2077. struct lock_list *unsafe_entry,
  2078. struct lock_class *prev_class,
  2079. struct lock_class *next_class)
  2080. {
  2081. struct lock_class *safe_class = safe_entry->class;
  2082. struct lock_class *unsafe_class = unsafe_entry->class;
  2083. struct lock_class *middle_class = prev_class;
  2084. if (middle_class == safe_class)
  2085. middle_class = next_class;
  2086. /*
  2087. * A direct locking problem where unsafe_class lock is taken
  2088. * directly by safe_class lock, then all we need to show
  2089. * is the deadlock scenario, as it is obvious that the
  2090. * unsafe lock is taken under the safe lock.
  2091. *
  2092. * But if there is a chain instead, where the safe lock takes
  2093. * an intermediate lock (middle_class) where this lock is
  2094. * not the same as the safe lock, then the lock chain is
  2095. * used to describe the problem. Otherwise we would need
  2096. * to show a different CPU case for each link in the chain
  2097. * from the safe_class lock to the unsafe_class lock.
  2098. */
  2099. if (middle_class != unsafe_class) {
  2100. printk("Chain exists of:\n ");
  2101. __print_lock_name(safe_class);
  2102. printk(KERN_CONT " --> ");
  2103. __print_lock_name(middle_class);
  2104. printk(KERN_CONT " --> ");
  2105. __print_lock_name(unsafe_class);
  2106. printk(KERN_CONT "\n\n");
  2107. }
  2108. printk(" Possible interrupt unsafe locking scenario:\n\n");
  2109. printk(" CPU0 CPU1\n");
  2110. printk(" ---- ----\n");
  2111. printk(" lock(");
  2112. __print_lock_name(unsafe_class);
  2113. printk(KERN_CONT ");\n");
  2114. printk(" local_irq_disable();\n");
  2115. printk(" lock(");
  2116. __print_lock_name(safe_class);
  2117. printk(KERN_CONT ");\n");
  2118. printk(" lock(");
  2119. __print_lock_name(middle_class);
  2120. printk(KERN_CONT ");\n");
  2121. printk(" <Interrupt>\n");
  2122. printk(" lock(");
  2123. __print_lock_name(safe_class);
  2124. printk(KERN_CONT ");\n");
  2125. printk("\n *** DEADLOCK ***\n\n");
  2126. }
  2127. static void
  2128. print_bad_irq_dependency(struct task_struct *curr,
  2129. struct lock_list *prev_root,
  2130. struct lock_list *next_root,
  2131. struct lock_list *backwards_entry,
  2132. struct lock_list *forwards_entry,
  2133. struct held_lock *prev,
  2134. struct held_lock *next,
  2135. enum lock_usage_bit bit1,
  2136. enum lock_usage_bit bit2,
  2137. const char *irqclass)
  2138. {
  2139. if (!debug_locks_off_graph_unlock() || debug_locks_silent)
  2140. return;
  2141. pr_warn("\n");
  2142. pr_warn("=====================================================\n");
  2143. pr_warn("WARNING: %s-safe -> %s-unsafe lock order detected\n",
  2144. irqclass, irqclass);
  2145. print_kernel_ident();
  2146. pr_warn("-----------------------------------------------------\n");
  2147. pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] is trying to acquire:\n",
  2148. curr->comm, task_pid_nr(curr),
  2149. lockdep_hardirq_context(), hardirq_count() >> HARDIRQ_SHIFT,
  2150. curr->softirq_context, softirq_count() >> SOFTIRQ_SHIFT,
  2151. lockdep_hardirqs_enabled(),
  2152. curr->softirqs_enabled);
  2153. print_lock(next);
  2154. pr_warn("\nand this task is already holding:\n");
  2155. print_lock(prev);
  2156. pr_warn("which would create a new lock dependency:\n");
  2157. print_lock_name(hlock_class(prev));
  2158. pr_cont(" ->");
  2159. print_lock_name(hlock_class(next));
  2160. pr_cont("\n");
  2161. pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",
  2162. irqclass);
  2163. print_lock_name(backwards_entry->class);
  2164. pr_warn("\n... which became %s-irq-safe at:\n", irqclass);
  2165. print_lock_trace(backwards_entry->class->usage_traces[bit1], 1);
  2166. pr_warn("\nto a %s-irq-unsafe lock:\n", irqclass);
  2167. print_lock_name(forwards_entry->class);
  2168. pr_warn("\n... which became %s-irq-unsafe at:\n", irqclass);
  2169. pr_warn("...");
  2170. print_lock_trace(forwards_entry->class->usage_traces[bit2], 1);
  2171. pr_warn("\nother info that might help us debug this:\n\n");
  2172. print_irq_lock_scenario(backwards_entry, forwards_entry,
  2173. hlock_class(prev), hlock_class(next));
  2174. lockdep_print_held_locks(curr);
  2175. pr_warn("\nthe dependencies between %s-irq-safe lock and the holding lock:\n", irqclass);
  2176. prev_root->trace = save_trace();
  2177. if (!prev_root->trace)
  2178. return;
  2179. print_shortest_lock_dependencies_backwards(backwards_entry, prev_root);
  2180. pr_warn("\nthe dependencies between the lock to be acquired");
  2181. pr_warn(" and %s-irq-unsafe lock:\n", irqclass);
  2182. next_root->trace = save_trace();
  2183. if (!next_root->trace)
  2184. return;
  2185. print_shortest_lock_dependencies(forwards_entry, next_root);
  2186. pr_warn("\nstack backtrace:\n");
  2187. dump_stack();
  2188. }
  2189. static const char *state_names[] = {
  2190. #define LOCKDEP_STATE(__STATE) \
  2191. __stringify(__STATE),
  2192. #include "lockdep_states.h"
  2193. #undef LOCKDEP_STATE
  2194. };
  2195. static const char *state_rnames[] = {
  2196. #define LOCKDEP_STATE(__STATE) \
  2197. __stringify(__STATE)"-READ",
  2198. #include "lockdep_states.h"
  2199. #undef LOCKDEP_STATE
  2200. };
  2201. static inline const char *state_name(enum lock_usage_bit bit)
  2202. {
  2203. if (bit & LOCK_USAGE_READ_MASK)
  2204. return state_rnames[bit >> LOCK_USAGE_DIR_MASK];
  2205. else
  2206. return state_names[bit >> LOCK_USAGE_DIR_MASK];
  2207. }
  2208. /*
  2209. * The bit number is encoded like:
  2210. *
  2211. * bit0: 0 exclusive, 1 read lock
  2212. * bit1: 0 used in irq, 1 irq enabled
  2213. * bit2-n: state
  2214. */
  2215. static int exclusive_bit(int new_bit)
  2216. {
  2217. int state = new_bit & LOCK_USAGE_STATE_MASK;
  2218. int dir = new_bit & LOCK_USAGE_DIR_MASK;
  2219. /*
  2220. * keep state, bit flip the direction and strip read.
  2221. */
  2222. return state | (dir ^ LOCK_USAGE_DIR_MASK);
  2223. }
  2224. /*
  2225. * Observe that when given a bitmask where each bitnr is encoded as above, a
  2226. * right shift of the mask transforms the individual bitnrs as -1 and
  2227. * conversely, a left shift transforms into +1 for the individual bitnrs.
  2228. *
  2229. * So for all bits whose number have LOCK_ENABLED_* set (bitnr1 == 1), we can
  2230. * create the mask with those bit numbers using LOCK_USED_IN_* (bitnr1 == 0)
  2231. * instead by subtracting the bit number by 2, or shifting the mask right by 2.
  2232. *
  2233. * Similarly, bitnr1 == 0 becomes bitnr1 == 1 by adding 2, or shifting left 2.
  2234. *
  2235. * So split the mask (note that LOCKF_ENABLED_IRQ_ALL|LOCKF_USED_IN_IRQ_ALL is
  2236. * all bits set) and recompose with bitnr1 flipped.
  2237. */
  2238. static unsigned long invert_dir_mask(unsigned long mask)
  2239. {
  2240. unsigned long excl = 0;
  2241. /* Invert dir */
  2242. excl |= (mask & LOCKF_ENABLED_IRQ_ALL) >> LOCK_USAGE_DIR_MASK;
  2243. excl |= (mask & LOCKF_USED_IN_IRQ_ALL) << LOCK_USAGE_DIR_MASK;
  2244. return excl;
  2245. }
  2246. /*
  2247. * Note that a LOCK_ENABLED_IRQ_*_READ usage and a LOCK_USED_IN_IRQ_*_READ
  2248. * usage may cause deadlock too, for example:
  2249. *
  2250. * P1 P2
  2251. * <irq disabled>
  2252. * write_lock(l1); <irq enabled>
  2253. * read_lock(l2);
  2254. * write_lock(l2);
  2255. * <in irq>
  2256. * read_lock(l1);
  2257. *
  2258. * , in above case, l1 will be marked as LOCK_USED_IN_IRQ_HARDIRQ_READ and l2
  2259. * will marked as LOCK_ENABLE_IRQ_HARDIRQ_READ, and this is a possible
  2260. * deadlock.
  2261. *
  2262. * In fact, all of the following cases may cause deadlocks:
  2263. *
  2264. * LOCK_USED_IN_IRQ_* -> LOCK_ENABLED_IRQ_*
  2265. * LOCK_USED_IN_IRQ_*_READ -> LOCK_ENABLED_IRQ_*
  2266. * LOCK_USED_IN_IRQ_* -> LOCK_ENABLED_IRQ_*_READ
  2267. * LOCK_USED_IN_IRQ_*_READ -> LOCK_ENABLED_IRQ_*_READ
  2268. *
  2269. * As a result, to calculate the "exclusive mask", first we invert the
  2270. * direction (USED_IN/ENABLED) of the original mask, and 1) for all bits with
  2271. * bitnr0 set (LOCK_*_READ), add those with bitnr0 cleared (LOCK_*). 2) for all
  2272. * bits with bitnr0 cleared (LOCK_*_READ), add those with bitnr0 set (LOCK_*).
  2273. */
  2274. static unsigned long exclusive_mask(unsigned long mask)
  2275. {
  2276. unsigned long excl = invert_dir_mask(mask);
  2277. excl |= (excl & LOCKF_IRQ_READ) >> LOCK_USAGE_READ_MASK;
  2278. excl |= (excl & LOCKF_IRQ) << LOCK_USAGE_READ_MASK;
  2279. return excl;
  2280. }
  2281. /*
  2282. * Retrieve the _possible_ original mask to which @mask is
  2283. * exclusive. Ie: this is the opposite of exclusive_mask().
  2284. * Note that 2 possible original bits can match an exclusive
  2285. * bit: one has LOCK_USAGE_READ_MASK set, the other has it
  2286. * cleared. So both are returned for each exclusive bit.
  2287. */
  2288. static unsigned long original_mask(unsigned long mask)
  2289. {
  2290. unsigned long excl = invert_dir_mask(mask);
  2291. /* Include read in existing usages */
  2292. excl |= (excl & LOCKF_IRQ_READ) >> LOCK_USAGE_READ_MASK;
  2293. excl |= (excl & LOCKF_IRQ) << LOCK_USAGE_READ_MASK;
  2294. return excl;
  2295. }
  2296. /*
  2297. * Find the first pair of bit match between an original
  2298. * usage mask and an exclusive usage mask.
  2299. */
  2300. static int find_exclusive_match(unsigned long mask,
  2301. unsigned long excl_mask,
  2302. enum lock_usage_bit *bitp,
  2303. enum lock_usage_bit *excl_bitp)
  2304. {
  2305. int bit, excl, excl_read;
  2306. for_each_set_bit(bit, &mask, LOCK_USED) {
  2307. /*
  2308. * exclusive_bit() strips the read bit, however,
  2309. * LOCK_ENABLED_IRQ_*_READ may cause deadlocks too, so we need
  2310. * to search excl | LOCK_USAGE_READ_MASK as well.
  2311. */
  2312. excl = exclusive_bit(bit);
  2313. excl_read = excl | LOCK_USAGE_READ_MASK;
  2314. if (excl_mask & lock_flag(excl)) {
  2315. *bitp = bit;
  2316. *excl_bitp = excl;
  2317. return 0;
  2318. } else if (excl_mask & lock_flag(excl_read)) {
  2319. *bitp = bit;
  2320. *excl_bitp = excl_read;
  2321. return 0;
  2322. }
  2323. }
  2324. return -1;
  2325. }
  2326. /*
  2327. * Prove that the new dependency does not connect a hardirq-safe(-read)
  2328. * lock with a hardirq-unsafe lock - to achieve this we search
  2329. * the backwards-subgraph starting at <prev>, and the
  2330. * forwards-subgraph starting at <next>:
  2331. */
  2332. static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
  2333. struct held_lock *next)
  2334. {
  2335. unsigned long usage_mask = 0, forward_mask, backward_mask;
  2336. enum lock_usage_bit forward_bit = 0, backward_bit = 0;
  2337. struct lock_list *target_entry1;
  2338. struct lock_list *target_entry;
  2339. struct lock_list this, that;
  2340. enum bfs_result ret;
  2341. /*
  2342. * Step 1: gather all hard/soft IRQs usages backward in an
  2343. * accumulated usage mask.
  2344. */
  2345. bfs_init_rootb(&this, prev);
  2346. ret = __bfs_backwards(&this, &usage_mask, usage_accumulate, NULL);
  2347. if (bfs_error(ret)) {
  2348. print_bfs_bug(ret);
  2349. return 0;
  2350. }
  2351. usage_mask &= LOCKF_USED_IN_IRQ_ALL;
  2352. if (!usage_mask)
  2353. return 1;
  2354. /*
  2355. * Step 2: find exclusive uses forward that match the previous
  2356. * backward accumulated mask.
  2357. */
  2358. forward_mask = exclusive_mask(usage_mask);
  2359. bfs_init_root(&that, next);
  2360. ret = find_usage_forwards(&that, forward_mask, &target_entry1);
  2361. if (bfs_error(ret)) {
  2362. print_bfs_bug(ret);
  2363. return 0;
  2364. }
  2365. if (ret == BFS_RNOMATCH)
  2366. return 1;
  2367. /*
  2368. * Step 3: we found a bad match! Now retrieve a lock from the backward
  2369. * list whose usage mask matches the exclusive usage mask from the
  2370. * lock found on the forward list.
  2371. *
  2372. * Note, we should only keep the LOCKF_ENABLED_IRQ_ALL bits, considering
  2373. * the follow case:
  2374. *
  2375. * When trying to add A -> B to the graph, we find that there is a
  2376. * hardirq-safe L, that L -> ... -> A, and another hardirq-unsafe M,
  2377. * that B -> ... -> M. However M is **softirq-safe**, if we use exact
  2378. * invert bits of M's usage_mask, we will find another lock N that is
  2379. * **softirq-unsafe** and N -> ... -> A, however N -> .. -> M will not
  2380. * cause a inversion deadlock.
  2381. */
  2382. backward_mask = original_mask(target_entry1->class->usage_mask & LOCKF_ENABLED_IRQ_ALL);
  2383. ret = find_usage_backwards(&this, backward_mask, &target_entry);
  2384. if (bfs_error(ret)) {
  2385. print_bfs_bug(ret);
  2386. return 0;
  2387. }
  2388. if (DEBUG_LOCKS_WARN_ON(ret == BFS_RNOMATCH))
  2389. return 1;
  2390. /*
  2391. * Step 4: narrow down to a pair of incompatible usage bits
  2392. * and report it.
  2393. */
  2394. ret = find_exclusive_match(target_entry->class->usage_mask,
  2395. target_entry1->class->usage_mask,
  2396. &backward_bit, &forward_bit);
  2397. if (DEBUG_LOCKS_WARN_ON(ret == -1))
  2398. return 1;
  2399. print_bad_irq_dependency(curr, &this, &that,
  2400. target_entry, target_entry1,
  2401. prev, next,
  2402. backward_bit, forward_bit,
  2403. state_name(backward_bit));
  2404. return 0;
  2405. }
  2406. #else
  2407. static inline int check_irq_usage(struct task_struct *curr,
  2408. struct held_lock *prev, struct held_lock *next)
  2409. {
  2410. return 1;
  2411. }
  2412. #endif /* CONFIG_TRACE_IRQFLAGS */
  2413. static void inc_chains(int irq_context)
  2414. {
  2415. if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT)
  2416. nr_hardirq_chains++;
  2417. else if (irq_context & LOCK_CHAIN_SOFTIRQ_CONTEXT)
  2418. nr_softirq_chains++;
  2419. else
  2420. nr_process_chains++;
  2421. }
  2422. static void dec_chains(int irq_context)
  2423. {
  2424. if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT)
  2425. nr_hardirq_chains--;
  2426. else if (irq_context & LOCK_CHAIN_SOFTIRQ_CONTEXT)
  2427. nr_softirq_chains--;
  2428. else
  2429. nr_process_chains--;
  2430. }
  2431. static void
  2432. print_deadlock_scenario(struct held_lock *nxt, struct held_lock *prv)
  2433. {
  2434. struct lock_class *next = hlock_class(nxt);
  2435. struct lock_class *prev = hlock_class(prv);
  2436. printk(" Possible unsafe locking scenario:\n\n");
  2437. printk(" CPU0\n");
  2438. printk(" ----\n");
  2439. printk(" lock(");
  2440. __print_lock_name(prev);
  2441. printk(KERN_CONT ");\n");
  2442. printk(" lock(");
  2443. __print_lock_name(next);
  2444. printk(KERN_CONT ");\n");
  2445. printk("\n *** DEADLOCK ***\n\n");
  2446. printk(" May be due to missing lock nesting notation\n\n");
  2447. }
  2448. static void
  2449. print_deadlock_bug(struct task_struct *curr, struct held_lock *prev,
  2450. struct held_lock *next)
  2451. {
  2452. if (!debug_locks_off_graph_unlock() || debug_locks_silent)
  2453. return;
  2454. pr_warn("\n");
  2455. pr_warn("============================================\n");
  2456. pr_warn("WARNING: possible recursive locking detected\n");
  2457. print_kernel_ident();
  2458. pr_warn("--------------------------------------------\n");
  2459. pr_warn("%s/%d is trying to acquire lock:\n",
  2460. curr->comm, task_pid_nr(curr));
  2461. print_lock(next);
  2462. pr_warn("\nbut task is already holding lock:\n");
  2463. print_lock(prev);
  2464. pr_warn("\nother info that might help us debug this:\n");
  2465. print_deadlock_scenario(next, prev);
  2466. lockdep_print_held_locks(curr);
  2467. pr_warn("\nstack backtrace:\n");
  2468. dump_stack();
  2469. }
  2470. /*
  2471. * Check whether we are holding such a class already.
  2472. *
  2473. * (Note that this has to be done separately, because the graph cannot
  2474. * detect such classes of deadlocks.)
  2475. *
  2476. * Returns: 0 on deadlock detected, 1 on OK, 2 if another lock with the same
  2477. * lock class is held but nest_lock is also held, i.e. we rely on the
  2478. * nest_lock to avoid the deadlock.
  2479. */
  2480. static int
  2481. check_deadlock(struct task_struct *curr, struct held_lock *next)
  2482. {
  2483. struct held_lock *prev;
  2484. struct held_lock *nest = NULL;
  2485. int i;
  2486. for (i = 0; i < curr->lockdep_depth; i++) {
  2487. prev = curr->held_locks + i;
  2488. if (prev->instance == next->nest_lock)
  2489. nest = prev;
  2490. if (hlock_class(prev) != hlock_class(next))
  2491. continue;
  2492. /*
  2493. * Allow read-after-read recursion of the same
  2494. * lock class (i.e. read_lock(lock)+read_lock(lock)):
  2495. */
  2496. if ((next->read == 2) && prev->read)
  2497. continue;
  2498. /*
  2499. * We're holding the nest_lock, which serializes this lock's
  2500. * nesting behaviour.
  2501. */
  2502. if (nest)
  2503. return 2;
  2504. print_deadlock_bug(curr, prev, next);
  2505. return 0;
  2506. }
  2507. return 1;
  2508. }
  2509. /*
  2510. * There was a chain-cache miss, and we are about to add a new dependency
  2511. * to a previous lock. We validate the following rules:
  2512. *
  2513. * - would the adding of the <prev> -> <next> dependency create a
  2514. * circular dependency in the graph? [== circular deadlock]
  2515. *
  2516. * - does the new prev->next dependency connect any hardirq-safe lock
  2517. * (in the full backwards-subgraph starting at <prev>) with any
  2518. * hardirq-unsafe lock (in the full forwards-subgraph starting at
  2519. * <next>)? [== illegal lock inversion with hardirq contexts]
  2520. *
  2521. * - does the new prev->next dependency connect any softirq-safe lock
  2522. * (in the full backwards-subgraph starting at <prev>) with any
  2523. * softirq-unsafe lock (in the full forwards-subgraph starting at
  2524. * <next>)? [== illegal lock inversion with softirq contexts]
  2525. *
  2526. * any of these scenarios could lead to a deadlock.
  2527. *
  2528. * Then if all the validations pass, we add the forwards and backwards
  2529. * dependency.
  2530. */
  2531. static int
  2532. check_prev_add(struct task_struct *curr, struct held_lock *prev,
  2533. struct held_lock *next, u16 distance,
  2534. struct lock_trace **const trace)
  2535. {
  2536. struct lock_list *entry;
  2537. enum bfs_result ret;
  2538. if (!hlock_class(prev)->key || !hlock_class(next)->key) {
  2539. /*
  2540. * The warning statements below may trigger a use-after-free
  2541. * of the class name. It is better to trigger a use-after free
  2542. * and to have the class name most of the time instead of not
  2543. * having the class name available.
  2544. */
  2545. WARN_ONCE(!debug_locks_silent && !hlock_class(prev)->key,
  2546. "Detected use-after-free of lock class %px/%s\n",
  2547. hlock_class(prev),
  2548. hlock_class(prev)->name);
  2549. WARN_ONCE(!debug_locks_silent && !hlock_class(next)->key,
  2550. "Detected use-after-free of lock class %px/%s\n",
  2551. hlock_class(next),
  2552. hlock_class(next)->name);
  2553. return 2;
  2554. }
  2555. /*
  2556. * Prove that the new <prev> -> <next> dependency would not
  2557. * create a circular dependency in the graph. (We do this by
  2558. * a breadth-first search into the graph starting at <next>,
  2559. * and check whether we can reach <prev>.)
  2560. *
  2561. * The search is limited by the size of the circular queue (i.e.,
  2562. * MAX_CIRCULAR_QUEUE_SIZE) which keeps track of a breadth of nodes
  2563. * in the graph whose neighbours are to be checked.
  2564. */
  2565. ret = check_noncircular(next, prev, trace);
  2566. if (unlikely(bfs_error(ret) || ret == BFS_RMATCH))
  2567. return 0;
  2568. if (!check_irq_usage(curr, prev, next))
  2569. return 0;
  2570. /*
  2571. * Is the <prev> -> <next> dependency already present?
  2572. *
  2573. * (this may occur even though this is a new chain: consider
  2574. * e.g. the L1 -> L2 -> L3 -> L4 and the L5 -> L1 -> L2 -> L3
  2575. * chains - the second one will be new, but L1 already has
  2576. * L2 added to its dependency list, due to the first chain.)
  2577. */
  2578. list_for_each_entry(entry, &hlock_class(prev)->locks_after, entry) {
  2579. if (entry->class == hlock_class(next)) {
  2580. if (distance == 1)
  2581. entry->distance = 1;
  2582. entry->dep |= calc_dep(prev, next);
  2583. /*
  2584. * Also, update the reverse dependency in @next's
  2585. * ->locks_before list.
  2586. *
  2587. * Here we reuse @entry as the cursor, which is fine
  2588. * because we won't go to the next iteration of the
  2589. * outer loop:
  2590. *
  2591. * For normal cases, we return in the inner loop.
  2592. *
  2593. * If we fail to return, we have inconsistency, i.e.
  2594. * <prev>::locks_after contains <next> while
  2595. * <next>::locks_before doesn't contain <prev>. In
  2596. * that case, we return after the inner and indicate
  2597. * something is wrong.
  2598. */
  2599. list_for_each_entry(entry, &hlock_class(next)->locks_before, entry) {
  2600. if (entry->class == hlock_class(prev)) {
  2601. if (distance == 1)
  2602. entry->distance = 1;
  2603. entry->dep |= calc_depb(prev, next);
  2604. return 1;
  2605. }
  2606. }
  2607. /* <prev> is not found in <next>::locks_before */
  2608. return 0;
  2609. }
  2610. }
  2611. #ifdef CONFIG_LOCKDEP_SMALL
  2612. /*
  2613. * Is the <prev> -> <next> link redundant?
  2614. */
  2615. ret = check_redundant(prev, next);
  2616. if (bfs_error(ret))
  2617. return 0;
  2618. else if (ret == BFS_RMATCH)
  2619. return 2;
  2620. #endif
  2621. if (!*trace) {
  2622. *trace = save_trace();
  2623. if (!*trace)
  2624. return 0;
  2625. }
  2626. /*
  2627. * Ok, all validations passed, add the new lock
  2628. * to the previous lock's dependency list:
  2629. */
  2630. ret = add_lock_to_list(hlock_class(next), hlock_class(prev),
  2631. &hlock_class(prev)->locks_after,
  2632. next->acquire_ip, distance,
  2633. calc_dep(prev, next),
  2634. *trace);
  2635. if (!ret)
  2636. return 0;
  2637. ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
  2638. &hlock_class(next)->locks_before,
  2639. next->acquire_ip, distance,
  2640. calc_depb(prev, next),
  2641. *trace);
  2642. if (!ret)
  2643. return 0;
  2644. return 2;
  2645. }
  2646. /*
  2647. * Add the dependency to all directly-previous locks that are 'relevant'.
  2648. * The ones that are relevant are (in increasing distance from curr):
  2649. * all consecutive trylock entries and the final non-trylock entry - or
  2650. * the end of this context's lock-chain - whichever comes first.
  2651. */
  2652. static int
  2653. check_prevs_add(struct task_struct *curr, struct held_lock *next)
  2654. {
  2655. struct lock_trace *trace = NULL;
  2656. int depth = curr->lockdep_depth;
  2657. struct held_lock *hlock;
  2658. /*
  2659. * Debugging checks.
  2660. *
  2661. * Depth must not be zero for a non-head lock:
  2662. */
  2663. if (!depth)
  2664. goto out_bug;
  2665. /*
  2666. * At least two relevant locks must exist for this
  2667. * to be a head:
  2668. */
  2669. if (curr->held_locks[depth].irq_context !=
  2670. curr->held_locks[depth-1].irq_context)
  2671. goto out_bug;
  2672. for (;;) {
  2673. u16 distance = curr->lockdep_depth - depth + 1;
  2674. hlock = curr->held_locks + depth - 1;
  2675. if (hlock->check) {
  2676. int ret = check_prev_add(curr, hlock, next, distance, &trace);
  2677. if (!ret)
  2678. return 0;
  2679. /*
  2680. * Stop after the first non-trylock entry,
  2681. * as non-trylock entries have added their
  2682. * own direct dependencies already, so this
  2683. * lock is connected to them indirectly:
  2684. */
  2685. if (!hlock->trylock)
  2686. break;
  2687. }
  2688. depth--;
  2689. /*
  2690. * End of lock-stack?
  2691. */
  2692. if (!depth)
  2693. break;
  2694. /*
  2695. * Stop the search if we cross into another context:
  2696. */
  2697. if (curr->held_locks[depth].irq_context !=
  2698. curr->held_locks[depth-1].irq_context)
  2699. break;
  2700. }
  2701. return 1;
  2702. out_bug:
  2703. if (!debug_locks_off_graph_unlock())
  2704. return 0;
  2705. /*
  2706. * Clearly we all shouldn't be here, but since we made it we
  2707. * can reliable say we messed up our state. See the above two
  2708. * gotos for reasons why we could possibly end up here.
  2709. */
  2710. WARN_ON(1);
  2711. return 0;
  2712. }
  2713. struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS];
  2714. static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
  2715. static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
  2716. unsigned long nr_zapped_lock_chains;
  2717. unsigned int nr_free_chain_hlocks; /* Free chain_hlocks in buckets */
  2718. unsigned int nr_lost_chain_hlocks; /* Lost chain_hlocks */
  2719. unsigned int nr_large_chain_blocks; /* size > MAX_CHAIN_BUCKETS */
  2720. /*
  2721. * The first 2 chain_hlocks entries in the chain block in the bucket
  2722. * list contains the following meta data:
  2723. *
  2724. * entry[0]:
  2725. * Bit 15 - always set to 1 (it is not a class index)
  2726. * Bits 0-14 - upper 15 bits of the next block index
  2727. * entry[1] - lower 16 bits of next block index
  2728. *
  2729. * A next block index of all 1 bits means it is the end of the list.
  2730. *
  2731. * On the unsized bucket (bucket-0), the 3rd and 4th entries contain
  2732. * the chain block size:
  2733. *
  2734. * entry[2] - upper 16 bits of the chain block size
  2735. * entry[3] - lower 16 bits of the chain block size
  2736. */
  2737. #define MAX_CHAIN_BUCKETS 16
  2738. #define CHAIN_BLK_FLAG (1U << 15)
  2739. #define CHAIN_BLK_LIST_END 0xFFFFU
  2740. static int chain_block_buckets[MAX_CHAIN_BUCKETS];
  2741. static inline int size_to_bucket(int size)
  2742. {
  2743. if (size > MAX_CHAIN_BUCKETS)
  2744. return 0;
  2745. return size - 1;
  2746. }
  2747. /*
  2748. * Iterate all the chain blocks in a bucket.
  2749. */
  2750. #define for_each_chain_block(bucket, prev, curr) \
  2751. for ((prev) = -1, (curr) = chain_block_buckets[bucket]; \
  2752. (curr) >= 0; \
  2753. (prev) = (curr), (curr) = chain_block_next(curr))
  2754. /*
  2755. * next block or -1
  2756. */
  2757. static inline int chain_block_next(int offset)
  2758. {
  2759. int next = chain_hlocks[offset];
  2760. WARN_ON_ONCE(!(next & CHAIN_BLK_FLAG));
  2761. if (next == CHAIN_BLK_LIST_END)
  2762. return -1;
  2763. next &= ~CHAIN_BLK_FLAG;
  2764. next <<= 16;
  2765. next |= chain_hlocks[offset + 1];
  2766. return next;
  2767. }
  2768. /*
  2769. * bucket-0 only
  2770. */
  2771. static inline int chain_block_size(int offset)
  2772. {
  2773. return (chain_hlocks[offset + 2] << 16) | chain_hlocks[offset + 3];
  2774. }
  2775. static inline void init_chain_block(int offset, int next, int bucket, int size)
  2776. {
  2777. chain_hlocks[offset] = (next >> 16) | CHAIN_BLK_FLAG;
  2778. chain_hlocks[offset + 1] = (u16)next;
  2779. if (size && !bucket) {
  2780. chain_hlocks[offset + 2] = size >> 16;
  2781. chain_hlocks[offset + 3] = (u16)size;
  2782. }
  2783. }
  2784. static inline void add_chain_block(int offset, int size)
  2785. {
  2786. int bucket = size_to_bucket(size);
  2787. int next = chain_block_buckets[bucket];
  2788. int prev, curr;
  2789. if (unlikely(size < 2)) {
  2790. /*
  2791. * We can't store single entries on the freelist. Leak them.
  2792. *
  2793. * One possible way out would be to uniquely mark them, other
  2794. * than with CHAIN_BLK_FLAG, such that we can recover them when
  2795. * the block before it is re-added.
  2796. */
  2797. if (size)
  2798. nr_lost_chain_hlocks++;
  2799. return;
  2800. }
  2801. nr_free_chain_hlocks += size;
  2802. if (!bucket) {
  2803. nr_large_chain_blocks++;
  2804. /*
  2805. * Variable sized, sort large to small.
  2806. */
  2807. for_each_chain_block(0, prev, curr) {
  2808. if (size >= chain_block_size(curr))
  2809. break;
  2810. }
  2811. init_chain_block(offset, curr, 0, size);
  2812. if (prev < 0)
  2813. chain_block_buckets[0] = offset;
  2814. else
  2815. init_chain_block(prev, offset, 0, 0);
  2816. return;
  2817. }
  2818. /*
  2819. * Fixed size, add to head.
  2820. */
  2821. init_chain_block(offset, next, bucket, size);
  2822. chain_block_buckets[bucket] = offset;
  2823. }
  2824. /*
  2825. * Only the first block in the list can be deleted.
  2826. *
  2827. * For the variable size bucket[0], the first block (the largest one) is
  2828. * returned, broken up and put back into the pool. So if a chain block of
  2829. * length > MAX_CHAIN_BUCKETS is ever used and zapped, it will just be
  2830. * queued up after the primordial chain block and never be used until the
  2831. * hlock entries in the primordial chain block is almost used up. That
  2832. * causes fragmentation and reduce allocation efficiency. That can be
  2833. * monitored by looking at the "large chain blocks" number in lockdep_stats.
  2834. */
  2835. static inline void del_chain_block(int bucket, int size, int next)
  2836. {
  2837. nr_free_chain_hlocks -= size;
  2838. chain_block_buckets[bucket] = next;
  2839. if (!bucket)
  2840. nr_large_chain_blocks--;
  2841. }
  2842. static void init_chain_block_buckets(void)
  2843. {
  2844. int i;
  2845. for (i = 0; i < MAX_CHAIN_BUCKETS; i++)
  2846. chain_block_buckets[i] = -1;
  2847. add_chain_block(0, ARRAY_SIZE(chain_hlocks));
  2848. }
  2849. /*
  2850. * Return offset of a chain block of the right size or -1 if not found.
  2851. *
  2852. * Fairly simple worst-fit allocator with the addition of a number of size
  2853. * specific free lists.
  2854. */
  2855. static int alloc_chain_hlocks(int req)
  2856. {
  2857. int bucket, curr, size;
  2858. /*
  2859. * We rely on the MSB to act as an escape bit to denote freelist
  2860. * pointers. Make sure this bit isn't set in 'normal' class_idx usage.
  2861. */
  2862. BUILD_BUG_ON((MAX_LOCKDEP_KEYS-1) & CHAIN_BLK_FLAG);
  2863. init_data_structures_once();
  2864. if (nr_free_chain_hlocks < req)
  2865. return -1;
  2866. /*
  2867. * We require a minimum of 2 (u16) entries to encode a freelist
  2868. * 'pointer'.
  2869. */
  2870. req = max(req, 2);
  2871. bucket = size_to_bucket(req);
  2872. curr = chain_block_buckets[bucket];
  2873. if (bucket) {
  2874. if (curr >= 0) {
  2875. del_chain_block(bucket, req, chain_block_next(curr));
  2876. return curr;
  2877. }
  2878. /* Try bucket 0 */
  2879. curr = chain_block_buckets[0];
  2880. }
  2881. /*
  2882. * The variable sized freelist is sorted by size; the first entry is
  2883. * the largest. Use it if it fits.
  2884. */
  2885. if (curr >= 0) {
  2886. size = chain_block_size(curr);
  2887. if (likely(size >= req)) {
  2888. del_chain_block(0, size, chain_block_next(curr));
  2889. add_chain_block(curr + req, size - req);
  2890. return curr;
  2891. }
  2892. }
  2893. /*
  2894. * Last resort, split a block in a larger sized bucket.
  2895. */
  2896. for (size = MAX_CHAIN_BUCKETS; size > req; size--) {
  2897. bucket = size_to_bucket(size);
  2898. curr = chain_block_buckets[bucket];
  2899. if (curr < 0)
  2900. continue;
  2901. del_chain_block(bucket, size, chain_block_next(curr));
  2902. add_chain_block(curr + req, size - req);
  2903. return curr;
  2904. }
  2905. return -1;
  2906. }
  2907. static inline void free_chain_hlocks(int base, int size)
  2908. {
  2909. add_chain_block(base, max(size, 2));
  2910. }
  2911. struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
  2912. {
  2913. u16 chain_hlock = chain_hlocks[chain->base + i];
  2914. unsigned int class_idx = chain_hlock_class_idx(chain_hlock);
  2915. return lock_classes + class_idx;
  2916. }
  2917. /*
  2918. * Returns the index of the first held_lock of the current chain
  2919. */
  2920. static inline int get_first_held_lock(struct task_struct *curr,
  2921. struct held_lock *hlock)
  2922. {
  2923. int i;
  2924. struct held_lock *hlock_curr;
  2925. for (i = curr->lockdep_depth - 1; i >= 0; i--) {
  2926. hlock_curr = curr->held_locks + i;
  2927. if (hlock_curr->irq_context != hlock->irq_context)
  2928. break;
  2929. }
  2930. return ++i;
  2931. }
  2932. #ifdef CONFIG_DEBUG_LOCKDEP
  2933. /*
  2934. * Returns the next chain_key iteration
  2935. */
  2936. static u64 print_chain_key_iteration(u16 hlock_id, u64 chain_key)
  2937. {
  2938. u64 new_chain_key = iterate_chain_key(chain_key, hlock_id);
  2939. printk(" hlock_id:%d -> chain_key:%016Lx",
  2940. (unsigned int)hlock_id,
  2941. (unsigned long long)new_chain_key);
  2942. return new_chain_key;
  2943. }
  2944. static void
  2945. print_chain_keys_held_locks(struct task_struct *curr, struct held_lock *hlock_next)
  2946. {
  2947. struct held_lock *hlock;
  2948. u64 chain_key = INITIAL_CHAIN_KEY;
  2949. int depth = curr->lockdep_depth;
  2950. int i = get_first_held_lock(curr, hlock_next);
  2951. printk("depth: %u (irq_context %u)\n", depth - i + 1,
  2952. hlock_next->irq_context);
  2953. for (; i < depth; i++) {
  2954. hlock = curr->held_locks + i;
  2955. chain_key = print_chain_key_iteration(hlock_id(hlock), chain_key);
  2956. print_lock(hlock);
  2957. }
  2958. print_chain_key_iteration(hlock_id(hlock_next), chain_key);
  2959. print_lock(hlock_next);
  2960. }
  2961. static void print_chain_keys_chain(struct lock_chain *chain)
  2962. {
  2963. int i;
  2964. u64 chain_key = INITIAL_CHAIN_KEY;
  2965. u16 hlock_id;
  2966. printk("depth: %u\n", chain->depth);
  2967. for (i = 0; i < chain->depth; i++) {
  2968. hlock_id = chain_hlocks[chain->base + i];
  2969. chain_key = print_chain_key_iteration(hlock_id, chain_key);
  2970. print_lock_name(lock_classes + chain_hlock_class_idx(hlock_id));
  2971. printk("\n");
  2972. }
  2973. }
  2974. static void print_collision(struct task_struct *curr,
  2975. struct held_lock *hlock_next,
  2976. struct lock_chain *chain)
  2977. {
  2978. pr_warn("\n");
  2979. pr_warn("============================\n");
  2980. pr_warn("WARNING: chain_key collision\n");
  2981. print_kernel_ident();
  2982. pr_warn("----------------------------\n");
  2983. pr_warn("%s/%d: ", current->comm, task_pid_nr(current));
  2984. pr_warn("Hash chain already cached but the contents don't match!\n");
  2985. pr_warn("Held locks:");
  2986. print_chain_keys_held_locks(curr, hlock_next);
  2987. pr_warn("Locks in cached chain:");
  2988. print_chain_keys_chain(chain);
  2989. pr_warn("\nstack backtrace:\n");
  2990. dump_stack();
  2991. }
  2992. #endif
  2993. /*
  2994. * Checks whether the chain and the current held locks are consistent
  2995. * in depth and also in content. If they are not it most likely means
  2996. * that there was a collision during the calculation of the chain_key.
  2997. * Returns: 0 not passed, 1 passed
  2998. */
  2999. static int check_no_collision(struct task_struct *curr,
  3000. struct held_lock *hlock,
  3001. struct lock_chain *chain)
  3002. {
  3003. #ifdef CONFIG_DEBUG_LOCKDEP
  3004. int i, j, id;
  3005. i = get_first_held_lock(curr, hlock);
  3006. if (DEBUG_LOCKS_WARN_ON(chain->depth != curr->lockdep_depth - (i - 1))) {
  3007. print_collision(curr, hlock, chain);
  3008. return 0;
  3009. }
  3010. for (j = 0; j < chain->depth - 1; j++, i++) {
  3011. id = hlock_id(&curr->held_locks[i]);
  3012. if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id)) {
  3013. print_collision(curr, hlock, chain);
  3014. return 0;
  3015. }
  3016. }
  3017. #endif
  3018. return 1;
  3019. }
  3020. /*
  3021. * Given an index that is >= -1, return the index of the next lock chain.
  3022. * Return -2 if there is no next lock chain.
  3023. */
  3024. long lockdep_next_lockchain(long i)
  3025. {
  3026. i = find_next_bit(lock_chains_in_use, ARRAY_SIZE(lock_chains), i + 1);
  3027. return i < ARRAY_SIZE(lock_chains) ? i : -2;
  3028. }
  3029. unsigned long lock_chain_count(void)
  3030. {
  3031. return bitmap_weight(lock_chains_in_use, ARRAY_SIZE(lock_chains));
  3032. }
  3033. /* Must be called with the graph lock held. */
  3034. static struct lock_chain *alloc_lock_chain(void)
  3035. {
  3036. int idx = find_first_zero_bit(lock_chains_in_use,
  3037. ARRAY_SIZE(lock_chains));
  3038. if (unlikely(idx >= ARRAY_SIZE(lock_chains)))
  3039. return NULL;
  3040. __set_bit(idx, lock_chains_in_use);
  3041. return lock_chains + idx;
  3042. }
  3043. /*
  3044. * Adds a dependency chain into chain hashtable. And must be called with
  3045. * graph_lock held.
  3046. *
  3047. * Return 0 if fail, and graph_lock is released.
  3048. * Return 1 if succeed, with graph_lock held.
  3049. */
  3050. static inline int add_chain_cache(struct task_struct *curr,
  3051. struct held_lock *hlock,
  3052. u64 chain_key)
  3053. {
  3054. struct hlist_head *hash_head = chainhashentry(chain_key);
  3055. struct lock_chain *chain;
  3056. int i, j;
  3057. /*
  3058. * The caller must hold the graph lock, ensure we've got IRQs
  3059. * disabled to make this an IRQ-safe lock.. for recursion reasons
  3060. * lockdep won't complain about its own locking errors.
  3061. */
  3062. if (lockdep_assert_locked())
  3063. return 0;
  3064. chain = alloc_lock_chain();
  3065. if (!chain) {
  3066. if (!debug_locks_off_graph_unlock())
  3067. return 0;
  3068. print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!");
  3069. dump_stack();
  3070. return 0;
  3071. }
  3072. chain->chain_key = chain_key;
  3073. chain->irq_context = hlock->irq_context;
  3074. i = get_first_held_lock(curr, hlock);
  3075. chain->depth = curr->lockdep_depth + 1 - i;
  3076. BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks));
  3077. BUILD_BUG_ON((1UL << 6) <= ARRAY_SIZE(curr->held_locks));
  3078. BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <= ARRAY_SIZE(lock_classes));
  3079. j = alloc_chain_hlocks(chain->depth);
  3080. if (j < 0) {
  3081. if (!debug_locks_off_graph_unlock())
  3082. return 0;
  3083. print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
  3084. dump_stack();
  3085. return 0;
  3086. }
  3087. chain->base = j;
  3088. for (j = 0; j < chain->depth - 1; j++, i++) {
  3089. int lock_id = hlock_id(curr->held_locks + i);
  3090. chain_hlocks[chain->base + j] = lock_id;
  3091. }
  3092. chain_hlocks[chain->base + j] = hlock_id(hlock);
  3093. hlist_add_head_rcu(&chain->entry, hash_head);
  3094. debug_atomic_inc(chain_lookup_misses);
  3095. inc_chains(chain->irq_context);
  3096. return 1;
  3097. }
  3098. /*
  3099. * Look up a dependency chain. Must be called with either the graph lock or
  3100. * the RCU read lock held.
  3101. */
  3102. static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
  3103. {
  3104. struct hlist_head *hash_head = chainhashentry(chain_key);
  3105. struct lock_chain *chain;
  3106. hlist_for_each_entry_rcu(chain, hash_head, entry) {
  3107. if (READ_ONCE(chain->chain_key) == chain_key) {
  3108. debug_atomic_inc(chain_lookup_hits);
  3109. return chain;
  3110. }
  3111. }
  3112. return NULL;
  3113. }
  3114. /*
  3115. * If the key is not present yet in dependency chain cache then
  3116. * add it and return 1 - in this case the new dependency chain is
  3117. * validated. If the key is already hashed, return 0.
  3118. * (On return with 1 graph_lock is held.)
  3119. */
  3120. static inline int lookup_chain_cache_add(struct task_struct *curr,
  3121. struct held_lock *hlock,
  3122. u64 chain_key)
  3123. {
  3124. struct lock_class *class = hlock_class(hlock);
  3125. struct lock_chain *chain = lookup_chain_cache(chain_key);
  3126. if (chain) {
  3127. cache_hit:
  3128. if (!check_no_collision(curr, hlock, chain))
  3129. return 0;
  3130. if (very_verbose(class)) {
  3131. printk("\nhash chain already cached, key: "
  3132. "%016Lx tail class: [%px] %s\n",
  3133. (unsigned long long)chain_key,
  3134. class->key, class->name);
  3135. }
  3136. return 0;
  3137. }
  3138. if (very_verbose(class)) {
  3139. printk("\nnew hash chain, key: %016Lx tail class: [%px] %s\n",
  3140. (unsigned long long)chain_key, class->key, class->name);
  3141. }
  3142. if (!graph_lock())
  3143. return 0;
  3144. /*
  3145. * We have to walk the chain again locked - to avoid duplicates:
  3146. */
  3147. chain = lookup_chain_cache(chain_key);
  3148. if (chain) {
  3149. graph_unlock();
  3150. goto cache_hit;
  3151. }
  3152. if (!add_chain_cache(curr, hlock, chain_key))
  3153. return 0;
  3154. return 1;
  3155. }
  3156. static int validate_chain(struct task_struct *curr,
  3157. struct held_lock *hlock,
  3158. int chain_head, u64 chain_key)
  3159. {
  3160. /*
  3161. * Trylock needs to maintain the stack of held locks, but it
  3162. * does not add new dependencies, because trylock can be done
  3163. * in any order.
  3164. *
  3165. * We look up the chain_key and do the O(N^2) check and update of
  3166. * the dependencies only if this is a new dependency chain.
  3167. * (If lookup_chain_cache_add() return with 1 it acquires
  3168. * graph_lock for us)
  3169. */
  3170. if (!hlock->trylock && hlock->check &&
  3171. lookup_chain_cache_add(curr, hlock, chain_key)) {
  3172. /*
  3173. * Check whether last held lock:
  3174. *
  3175. * - is irq-safe, if this lock is irq-unsafe
  3176. * - is softirq-safe, if this lock is hardirq-unsafe
  3177. *
  3178. * And check whether the new lock's dependency graph
  3179. * could lead back to the previous lock:
  3180. *
  3181. * - within the current held-lock stack
  3182. * - across our accumulated lock dependency records
  3183. *
  3184. * any of these scenarios could lead to a deadlock.
  3185. */
  3186. /*
  3187. * The simple case: does the current hold the same lock
  3188. * already?
  3189. */
  3190. int ret = check_deadlock(curr, hlock);
  3191. if (!ret)
  3192. return 0;
  3193. /*
  3194. * Add dependency only if this lock is not the head
  3195. * of the chain, and if the new lock introduces no more
  3196. * lock dependency (because we already hold a lock with the
  3197. * same lock class) nor deadlock (because the nest_lock
  3198. * serializes nesting locks), see the comments for
  3199. * check_deadlock().
  3200. */
  3201. if (!chain_head && ret != 2) {
  3202. if (!check_prevs_add(curr, hlock))
  3203. return 0;
  3204. }
  3205. graph_unlock();
  3206. } else {
  3207. /* after lookup_chain_cache_add(): */
  3208. if (unlikely(!debug_locks))
  3209. return 0;
  3210. }
  3211. return 1;
  3212. }
  3213. #else
  3214. static inline int validate_chain(struct task_struct *curr,
  3215. struct held_lock *hlock,
  3216. int chain_head, u64 chain_key)
  3217. {
  3218. return 1;
  3219. }
  3220. static void init_chain_block_buckets(void) { }
  3221. #endif /* CONFIG_PROVE_LOCKING */
  3222. /*
  3223. * We are building curr_chain_key incrementally, so double-check
  3224. * it from scratch, to make sure that it's done correctly:
  3225. */
  3226. static void check_chain_key(struct task_struct *curr)
  3227. {
  3228. #ifdef CONFIG_DEBUG_LOCKDEP
  3229. struct held_lock *hlock, *prev_hlock = NULL;
  3230. unsigned int i;
  3231. u64 chain_key = INITIAL_CHAIN_KEY;
  3232. for (i = 0; i < curr->lockdep_depth; i++) {
  3233. hlock = curr->held_locks + i;
  3234. if (chain_key != hlock->prev_chain_key) {
  3235. debug_locks_off();
  3236. /*
  3237. * We got mighty confused, our chain keys don't match
  3238. * with what we expect, someone trample on our task state?
  3239. */
  3240. WARN(1, "hm#1, depth: %u [%u], %016Lx != %016Lx\n",
  3241. curr->lockdep_depth, i,
  3242. (unsigned long long)chain_key,
  3243. (unsigned long long)hlock->prev_chain_key);
  3244. return;
  3245. }
  3246. /*
  3247. * hlock->class_idx can't go beyond MAX_LOCKDEP_KEYS, but is
  3248. * it registered lock class index?
  3249. */
  3250. if (DEBUG_LOCKS_WARN_ON(!test_bit(hlock->class_idx, lock_classes_in_use)))
  3251. return;
  3252. if (prev_hlock && (prev_hlock->irq_context !=
  3253. hlock->irq_context))
  3254. chain_key = INITIAL_CHAIN_KEY;
  3255. chain_key = iterate_chain_key(chain_key, hlock_id(hlock));
  3256. prev_hlock = hlock;
  3257. }
  3258. if (chain_key != curr->curr_chain_key) {
  3259. debug_locks_off();
  3260. /*
  3261. * More smoking hash instead of calculating it, damn see these
  3262. * numbers float.. I bet that a pink elephant stepped on my memory.
  3263. */
  3264. WARN(1, "hm#2, depth: %u [%u], %016Lx != %016Lx\n",
  3265. curr->lockdep_depth, i,
  3266. (unsigned long long)chain_key,
  3267. (unsigned long long)curr->curr_chain_key);
  3268. }
  3269. #endif
  3270. }
  3271. #ifdef CONFIG_PROVE_LOCKING
  3272. static int mark_lock(struct task_struct *curr, struct held_lock *this,
  3273. enum lock_usage_bit new_bit);
  3274. static void print_usage_bug_scenario(struct held_lock *lock)
  3275. {
  3276. struct lock_class *class = hlock_class(lock);
  3277. printk(" Possible unsafe locking scenario:\n\n");
  3278. printk(" CPU0\n");
  3279. printk(" ----\n");
  3280. printk(" lock(");
  3281. __print_lock_name(class);
  3282. printk(KERN_CONT ");\n");
  3283. printk(" <Interrupt>\n");
  3284. printk(" lock(");
  3285. __print_lock_name(class);
  3286. printk(KERN_CONT ");\n");
  3287. printk("\n *** DEADLOCK ***\n\n");
  3288. }
  3289. static void
  3290. print_usage_bug(struct task_struct *curr, struct held_lock *this,
  3291. enum lock_usage_bit prev_bit, enum lock_usage_bit new_bit)
  3292. {
  3293. if (!debug_locks_off() || debug_locks_silent)
  3294. return;
  3295. pr_warn("\n");
  3296. pr_warn("================================\n");
  3297. pr_warn("WARNING: inconsistent lock state\n");
  3298. print_kernel_ident();
  3299. pr_warn("--------------------------------\n");
  3300. pr_warn("inconsistent {%s} -> {%s} usage.\n",
  3301. usage_str[prev_bit], usage_str[new_bit]);
  3302. pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] takes:\n",
  3303. curr->comm, task_pid_nr(curr),
  3304. lockdep_hardirq_context(), hardirq_count() >> HARDIRQ_SHIFT,
  3305. lockdep_softirq_context(curr), softirq_count() >> SOFTIRQ_SHIFT,
  3306. lockdep_hardirqs_enabled(),
  3307. lockdep_softirqs_enabled(curr));
  3308. print_lock(this);
  3309. pr_warn("{%s} state was registered at:\n", usage_str[prev_bit]);
  3310. print_lock_trace(hlock_class(this)->usage_traces[prev_bit], 1);
  3311. print_irqtrace_events(curr);
  3312. pr_warn("\nother info that might help us debug this:\n");
  3313. print_usage_bug_scenario(this);
  3314. lockdep_print_held_locks(curr);
  3315. pr_warn("\nstack backtrace:\n");
  3316. dump_stack();
  3317. }
  3318. /*
  3319. * Print out an error if an invalid bit is set:
  3320. */
  3321. static inline int
  3322. valid_state(struct task_struct *curr, struct held_lock *this,
  3323. enum lock_usage_bit new_bit, enum lock_usage_bit bad_bit)
  3324. {
  3325. if (unlikely(hlock_class(this)->usage_mask & (1 << bad_bit))) {
  3326. graph_unlock();
  3327. print_usage_bug(curr, this, bad_bit, new_bit);
  3328. return 0;
  3329. }
  3330. return 1;
  3331. }
  3332. /*
  3333. * print irq inversion bug:
  3334. */
  3335. static void
  3336. print_irq_inversion_bug(struct task_struct *curr,
  3337. struct lock_list *root, struct lock_list *other,
  3338. struct held_lock *this, int forwards,
  3339. const char *irqclass)
  3340. {
  3341. struct lock_list *entry = other;
  3342. struct lock_list *middle = NULL;
  3343. int depth;
  3344. if (!debug_locks_off_graph_unlock() || debug_locks_silent)
  3345. return;
  3346. pr_warn("\n");
  3347. pr_warn("========================================================\n");
  3348. pr_warn("WARNING: possible irq lock inversion dependency detected\n");
  3349. print_kernel_ident();
  3350. pr_warn("--------------------------------------------------------\n");
  3351. pr_warn("%s/%d just changed the state of lock:\n",
  3352. curr->comm, task_pid_nr(curr));
  3353. print_lock(this);
  3354. if (forwards)
  3355. pr_warn("but this lock took another, %s-unsafe lock in the past:\n", irqclass);
  3356. else
  3357. pr_warn("but this lock was taken by another, %s-safe lock in the past:\n", irqclass);
  3358. print_lock_name(other->class);
  3359. pr_warn("\n\nand interrupts could create inverse lock ordering between them.\n\n");
  3360. pr_warn("\nother info that might help us debug this:\n");
  3361. /* Find a middle lock (if one exists) */
  3362. depth = get_lock_depth(other);
  3363. do {
  3364. if (depth == 0 && (entry != root)) {
  3365. pr_warn("lockdep:%s bad path found in chain graph\n", __func__);
  3366. break;
  3367. }
  3368. middle = entry;
  3369. entry = get_lock_parent(entry);
  3370. depth--;
  3371. } while (entry && entry != root && (depth >= 0));
  3372. if (forwards)
  3373. print_irq_lock_scenario(root, other,
  3374. middle ? middle->class : root->class, other->class);
  3375. else
  3376. print_irq_lock_scenario(other, root,
  3377. middle ? middle->class : other->class, root->class);
  3378. lockdep_print_held_locks(curr);
  3379. pr_warn("\nthe shortest dependencies between 2nd lock and 1st lock:\n");
  3380. root->trace = save_trace();
  3381. if (!root->trace)
  3382. return;
  3383. print_shortest_lock_dependencies(other, root);
  3384. pr_warn("\nstack backtrace:\n");
  3385. dump_stack();
  3386. }
  3387. /*
  3388. * Prove that in the forwards-direction subgraph starting at <this>
  3389. * there is no lock matching <mask>:
  3390. */
  3391. static int
  3392. check_usage_forwards(struct task_struct *curr, struct held_lock *this,
  3393. enum lock_usage_bit bit)
  3394. {
  3395. enum bfs_result ret;
  3396. struct lock_list root;
  3397. struct lock_list *target_entry;
  3398. enum lock_usage_bit read_bit = bit + LOCK_USAGE_READ_MASK;
  3399. unsigned usage_mask = lock_flag(bit) | lock_flag(read_bit);
  3400. bfs_init_root(&root, this);
  3401. ret = find_usage_forwards(&root, usage_mask, &target_entry);
  3402. if (bfs_error(ret)) {
  3403. print_bfs_bug(ret);
  3404. return 0;
  3405. }
  3406. if (ret == BFS_RNOMATCH)
  3407. return 1;
  3408. /* Check whether write or read usage is the match */
  3409. if (target_entry->class->usage_mask & lock_flag(bit)) {
  3410. print_irq_inversion_bug(curr, &root, target_entry,
  3411. this, 1, state_name(bit));
  3412. } else {
  3413. print_irq_inversion_bug(curr, &root, target_entry,
  3414. this, 1, state_name(read_bit));
  3415. }
  3416. return 0;
  3417. }
  3418. /*
  3419. * Prove that in the backwards-direction subgraph starting at <this>
  3420. * there is no lock matching <mask>:
  3421. */
  3422. static int
  3423. check_usage_backwards(struct task_struct *curr, struct held_lock *this,
  3424. enum lock_usage_bit bit)
  3425. {
  3426. enum bfs_result ret;
  3427. struct lock_list root;
  3428. struct lock_list *target_entry;
  3429. enum lock_usage_bit read_bit = bit + LOCK_USAGE_READ_MASK;
  3430. unsigned usage_mask = lock_flag(bit) | lock_flag(read_bit);
  3431. bfs_init_rootb(&root, this);
  3432. ret = find_usage_backwards(&root, usage_mask, &target_entry);
  3433. if (bfs_error(ret)) {
  3434. print_bfs_bug(ret);
  3435. return 0;
  3436. }
  3437. if (ret == BFS_RNOMATCH)
  3438. return 1;
  3439. /* Check whether write or read usage is the match */
  3440. if (target_entry->class->usage_mask & lock_flag(bit)) {
  3441. print_irq_inversion_bug(curr, &root, target_entry,
  3442. this, 0, state_name(bit));
  3443. } else {
  3444. print_irq_inversion_bug(curr, &root, target_entry,
  3445. this, 0, state_name(read_bit));
  3446. }
  3447. return 0;
  3448. }
  3449. void print_irqtrace_events(struct task_struct *curr)
  3450. {
  3451. const struct irqtrace_events *trace = &curr->irqtrace;
  3452. printk("irq event stamp: %u\n", trace->irq_events);
  3453. printk("hardirqs last enabled at (%u): [<%px>] %pS\n",
  3454. trace->hardirq_enable_event, (void *)trace->hardirq_enable_ip,
  3455. (void *)trace->hardirq_enable_ip);
  3456. printk("hardirqs last disabled at (%u): [<%px>] %pS\n",
  3457. trace->hardirq_disable_event, (void *)trace->hardirq_disable_ip,
  3458. (void *)trace->hardirq_disable_ip);
  3459. printk("softirqs last enabled at (%u): [<%px>] %pS\n",
  3460. trace->softirq_enable_event, (void *)trace->softirq_enable_ip,
  3461. (void *)trace->softirq_enable_ip);
  3462. printk("softirqs last disabled at (%u): [<%px>] %pS\n",
  3463. trace->softirq_disable_event, (void *)trace->softirq_disable_ip,
  3464. (void *)trace->softirq_disable_ip);
  3465. }
  3466. static int HARDIRQ_verbose(struct lock_class *class)
  3467. {
  3468. #if HARDIRQ_VERBOSE
  3469. return class_filter(class);
  3470. #endif
  3471. return 0;
  3472. }
  3473. static int SOFTIRQ_verbose(struct lock_class *class)
  3474. {
  3475. #if SOFTIRQ_VERBOSE
  3476. return class_filter(class);
  3477. #endif
  3478. return 0;
  3479. }
  3480. static int (*state_verbose_f[])(struct lock_class *class) = {
  3481. #define LOCKDEP_STATE(__STATE) \
  3482. __STATE##_verbose,
  3483. #include "lockdep_states.h"
  3484. #undef LOCKDEP_STATE
  3485. };
  3486. static inline int state_verbose(enum lock_usage_bit bit,
  3487. struct lock_class *class)
  3488. {
  3489. return state_verbose_f[bit >> LOCK_USAGE_DIR_MASK](class);
  3490. }
  3491. typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
  3492. enum lock_usage_bit bit, const char *name);
  3493. static int
  3494. mark_lock_irq(struct task_struct *curr, struct held_lock *this,
  3495. enum lock_usage_bit new_bit)
  3496. {
  3497. int excl_bit = exclusive_bit(new_bit);
  3498. int read = new_bit & LOCK_USAGE_READ_MASK;
  3499. int dir = new_bit & LOCK_USAGE_DIR_MASK;
  3500. /*
  3501. * Validate that this particular lock does not have conflicting
  3502. * usage states.
  3503. */
  3504. if (!valid_state(curr, this, new_bit, excl_bit))
  3505. return 0;
  3506. /*
  3507. * Check for read in write conflicts
  3508. */
  3509. if (!read && !valid_state(curr, this, new_bit,
  3510. excl_bit + LOCK_USAGE_READ_MASK))
  3511. return 0;
  3512. /*
  3513. * Validate that the lock dependencies don't have conflicting usage
  3514. * states.
  3515. */
  3516. if (dir) {
  3517. /*
  3518. * mark ENABLED has to look backwards -- to ensure no dependee
  3519. * has USED_IN state, which, again, would allow recursion deadlocks.
  3520. */
  3521. if (!check_usage_backwards(curr, this, excl_bit))
  3522. return 0;
  3523. } else {
  3524. /*
  3525. * mark USED_IN has to look forwards -- to ensure no dependency
  3526. * has ENABLED state, which would allow recursion deadlocks.
  3527. */
  3528. if (!check_usage_forwards(curr, this, excl_bit))
  3529. return 0;
  3530. }
  3531. if (state_verbose(new_bit, hlock_class(this)))
  3532. return 2;
  3533. return 1;
  3534. }
  3535. /*
  3536. * Mark all held locks with a usage bit:
  3537. */
  3538. static int
  3539. mark_held_locks(struct task_struct *curr, enum lock_usage_bit base_bit)
  3540. {
  3541. struct held_lock *hlock;
  3542. int i;
  3543. for (i = 0; i < curr->lockdep_depth; i++) {
  3544. enum lock_usage_bit hlock_bit = base_bit;
  3545. hlock = curr->held_locks + i;
  3546. if (hlock->read)
  3547. hlock_bit += LOCK_USAGE_READ_MASK;
  3548. BUG_ON(hlock_bit >= LOCK_USAGE_STATES);
  3549. if (!hlock->check)
  3550. continue;
  3551. if (!mark_lock(curr, hlock, hlock_bit))
  3552. return 0;
  3553. }
  3554. return 1;
  3555. }
  3556. /*
  3557. * Hardirqs will be enabled:
  3558. */
  3559. static void __trace_hardirqs_on_caller(void)
  3560. {
  3561. struct task_struct *curr = current;
  3562. /*
  3563. * We are going to turn hardirqs on, so set the
  3564. * usage bit for all held locks:
  3565. */
  3566. if (!mark_held_locks(curr, LOCK_ENABLED_HARDIRQ))
  3567. return;
  3568. /*
  3569. * If we have softirqs enabled, then set the usage
  3570. * bit for all held locks. (disabled hardirqs prevented
  3571. * this bit from being set before)
  3572. */
  3573. if (curr->softirqs_enabled)
  3574. mark_held_locks(curr, LOCK_ENABLED_SOFTIRQ);
  3575. }
  3576. /**
  3577. * lockdep_hardirqs_on_prepare - Prepare for enabling interrupts
  3578. * @ip: Caller address
  3579. *
  3580. * Invoked before a possible transition to RCU idle from exit to user or
  3581. * guest mode. This ensures that all RCU operations are done before RCU
  3582. * stops watching. After the RCU transition lockdep_hardirqs_on() has to be
  3583. * invoked to set the final state.
  3584. */
  3585. void lockdep_hardirqs_on_prepare(unsigned long ip)
  3586. {
  3587. if (unlikely(!debug_locks))
  3588. return;
  3589. /*
  3590. * NMIs do not (and cannot) track lock dependencies, nothing to do.
  3591. */
  3592. if (unlikely(in_nmi()))
  3593. return;
  3594. if (unlikely(this_cpu_read(lockdep_recursion)))
  3595. return;
  3596. if (unlikely(lockdep_hardirqs_enabled())) {
  3597. /*
  3598. * Neither irq nor preemption are disabled here
  3599. * so this is racy by nature but losing one hit
  3600. * in a stat is not a big deal.
  3601. */
  3602. __debug_atomic_inc(redundant_hardirqs_on);
  3603. return;
  3604. }
  3605. /*
  3606. * We're enabling irqs and according to our state above irqs weren't
  3607. * already enabled, yet we find the hardware thinks they are in fact
  3608. * enabled.. someone messed up their IRQ state tracing.
  3609. */
  3610. if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
  3611. return;
  3612. /*
  3613. * See the fine text that goes along with this variable definition.
  3614. */
  3615. if (DEBUG_LOCKS_WARN_ON(early_boot_irqs_disabled))
  3616. return;
  3617. /*
  3618. * Can't allow enabling interrupts while in an interrupt handler,
  3619. * that's general bad form and such. Recursion, limited stack etc..
  3620. */
  3621. if (DEBUG_LOCKS_WARN_ON(lockdep_hardirq_context()))
  3622. return;
  3623. current->hardirq_chain_key = current->curr_chain_key;
  3624. lockdep_recursion_inc();
  3625. __trace_hardirqs_on_caller();
  3626. lockdep_recursion_finish();
  3627. }
  3628. EXPORT_SYMBOL_GPL(lockdep_hardirqs_on_prepare);
  3629. void noinstr lockdep_hardirqs_on(unsigned long ip)
  3630. {
  3631. struct irqtrace_events *trace = &current->irqtrace;
  3632. if (unlikely(!debug_locks))
  3633. return;
  3634. /*
  3635. * NMIs can happen in the middle of local_irq_{en,dis}able() where the
  3636. * tracking state and hardware state are out of sync.
  3637. *
  3638. * NMIs must save lockdep_hardirqs_enabled() to restore IRQ state from,
  3639. * and not rely on hardware state like normal interrupts.
  3640. */
  3641. if (unlikely(in_nmi())) {
  3642. if (!IS_ENABLED(CONFIG_TRACE_IRQFLAGS_NMI))
  3643. return;
  3644. /*
  3645. * Skip:
  3646. * - recursion check, because NMI can hit lockdep;
  3647. * - hardware state check, because above;
  3648. * - chain_key check, see lockdep_hardirqs_on_prepare().
  3649. */
  3650. goto skip_checks;
  3651. }
  3652. if (unlikely(this_cpu_read(lockdep_recursion)))
  3653. return;
  3654. if (lockdep_hardirqs_enabled()) {
  3655. /*
  3656. * Neither irq nor preemption are disabled here
  3657. * so this is racy by nature but losing one hit
  3658. * in a stat is not a big deal.
  3659. */
  3660. __debug_atomic_inc(redundant_hardirqs_on);
  3661. return;
  3662. }
  3663. /*
  3664. * We're enabling irqs and according to our state above irqs weren't
  3665. * already enabled, yet we find the hardware thinks they are in fact
  3666. * enabled.. someone messed up their IRQ state tracing.
  3667. */
  3668. if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
  3669. return;
  3670. /*
  3671. * Ensure the lock stack remained unchanged between
  3672. * lockdep_hardirqs_on_prepare() and lockdep_hardirqs_on().
  3673. */
  3674. DEBUG_LOCKS_WARN_ON(current->hardirq_chain_key !=
  3675. current->curr_chain_key);
  3676. skip_checks:
  3677. /* we'll do an OFF -> ON transition: */
  3678. __this_cpu_write(hardirqs_enabled, 1);
  3679. trace->hardirq_enable_ip = ip;
  3680. trace->hardirq_enable_event = ++trace->irq_events;
  3681. debug_atomic_inc(hardirqs_on_events);
  3682. }
  3683. EXPORT_SYMBOL_GPL(lockdep_hardirqs_on);
  3684. /*
  3685. * Hardirqs were disabled:
  3686. */
  3687. void noinstr lockdep_hardirqs_off(unsigned long ip)
  3688. {
  3689. if (unlikely(!debug_locks))
  3690. return;
  3691. /*
  3692. * Matching lockdep_hardirqs_on(), allow NMIs in the middle of lockdep;
  3693. * they will restore the software state. This ensures the software
  3694. * state is consistent inside NMIs as well.
  3695. */
  3696. if (in_nmi()) {
  3697. if (!IS_ENABLED(CONFIG_TRACE_IRQFLAGS_NMI))
  3698. return;
  3699. } else if (__this_cpu_read(lockdep_recursion))
  3700. return;
  3701. /*
  3702. * So we're supposed to get called after you mask local IRQs, but for
  3703. * some reason the hardware doesn't quite think you did a proper job.
  3704. */
  3705. if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
  3706. return;
  3707. if (lockdep_hardirqs_enabled()) {
  3708. struct irqtrace_events *trace = &current->irqtrace;
  3709. /*
  3710. * We have done an ON -> OFF transition:
  3711. */
  3712. __this_cpu_write(hardirqs_enabled, 0);
  3713. trace->hardirq_disable_ip = ip;
  3714. trace->hardirq_disable_event = ++trace->irq_events;
  3715. debug_atomic_inc(hardirqs_off_events);
  3716. } else {
  3717. debug_atomic_inc(redundant_hardirqs_off);
  3718. }
  3719. }
  3720. EXPORT_SYMBOL_GPL(lockdep_hardirqs_off);
  3721. /*
  3722. * Softirqs will be enabled:
  3723. */
  3724. void lockdep_softirqs_on(unsigned long ip)
  3725. {
  3726. struct irqtrace_events *trace = &current->irqtrace;
  3727. if (unlikely(!lockdep_enabled()))
  3728. return;
  3729. /*
  3730. * We fancy IRQs being disabled here, see softirq.c, avoids
  3731. * funny state and nesting things.
  3732. */
  3733. if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
  3734. return;
  3735. if (current->softirqs_enabled) {
  3736. debug_atomic_inc(redundant_softirqs_on);
  3737. return;
  3738. }
  3739. lockdep_recursion_inc();
  3740. /*
  3741. * We'll do an OFF -> ON transition:
  3742. */
  3743. current->softirqs_enabled = 1;
  3744. trace->softirq_enable_ip = ip;
  3745. trace->softirq_enable_event = ++trace->irq_events;
  3746. debug_atomic_inc(softirqs_on_events);
  3747. /*
  3748. * We are going to turn softirqs on, so set the
  3749. * usage bit for all held locks, if hardirqs are
  3750. * enabled too:
  3751. */
  3752. if (lockdep_hardirqs_enabled())
  3753. mark_held_locks(current, LOCK_ENABLED_SOFTIRQ);
  3754. lockdep_recursion_finish();
  3755. }
  3756. /*
  3757. * Softirqs were disabled:
  3758. */
  3759. void lockdep_softirqs_off(unsigned long ip)
  3760. {
  3761. if (unlikely(!lockdep_enabled()))
  3762. return;
  3763. /*
  3764. * We fancy IRQs being disabled here, see softirq.c
  3765. */
  3766. if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
  3767. return;
  3768. if (current->softirqs_enabled) {
  3769. struct irqtrace_events *trace = &current->irqtrace;
  3770. /*
  3771. * We have done an ON -> OFF transition:
  3772. */
  3773. current->softirqs_enabled = 0;
  3774. trace->softirq_disable_ip = ip;
  3775. trace->softirq_disable_event = ++trace->irq_events;
  3776. debug_atomic_inc(softirqs_off_events);
  3777. /*
  3778. * Whoops, we wanted softirqs off, so why aren't they?
  3779. */
  3780. DEBUG_LOCKS_WARN_ON(!softirq_count());
  3781. } else
  3782. debug_atomic_inc(redundant_softirqs_off);
  3783. }
  3784. static int
  3785. mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
  3786. {
  3787. if (!check)
  3788. goto lock_used;
  3789. /*
  3790. * If non-trylock use in a hardirq or softirq context, then
  3791. * mark the lock as used in these contexts:
  3792. */
  3793. if (!hlock->trylock) {
  3794. if (hlock->read) {
  3795. if (lockdep_hardirq_context())
  3796. if (!mark_lock(curr, hlock,
  3797. LOCK_USED_IN_HARDIRQ_READ))
  3798. return 0;
  3799. if (curr->softirq_context)
  3800. if (!mark_lock(curr, hlock,
  3801. LOCK_USED_IN_SOFTIRQ_READ))
  3802. return 0;
  3803. } else {
  3804. if (lockdep_hardirq_context())
  3805. if (!mark_lock(curr, hlock, LOCK_USED_IN_HARDIRQ))
  3806. return 0;
  3807. if (curr->softirq_context)
  3808. if (!mark_lock(curr, hlock, LOCK_USED_IN_SOFTIRQ))
  3809. return 0;
  3810. }
  3811. }
  3812. if (!hlock->hardirqs_off) {
  3813. if (hlock->read) {
  3814. if (!mark_lock(curr, hlock,
  3815. LOCK_ENABLED_HARDIRQ_READ))
  3816. return 0;
  3817. if (curr->softirqs_enabled)
  3818. if (!mark_lock(curr, hlock,
  3819. LOCK_ENABLED_SOFTIRQ_READ))
  3820. return 0;
  3821. } else {
  3822. if (!mark_lock(curr, hlock,
  3823. LOCK_ENABLED_HARDIRQ))
  3824. return 0;
  3825. if (curr->softirqs_enabled)
  3826. if (!mark_lock(curr, hlock,
  3827. LOCK_ENABLED_SOFTIRQ))
  3828. return 0;
  3829. }
  3830. }
  3831. lock_used:
  3832. /* mark it as used: */
  3833. if (!mark_lock(curr, hlock, LOCK_USED))
  3834. return 0;
  3835. return 1;
  3836. }
  3837. static inline unsigned int task_irq_context(struct task_struct *task)
  3838. {
  3839. return LOCK_CHAIN_HARDIRQ_CONTEXT * !!lockdep_hardirq_context() +
  3840. LOCK_CHAIN_SOFTIRQ_CONTEXT * !!task->softirq_context;
  3841. }
  3842. static int separate_irq_context(struct task_struct *curr,
  3843. struct held_lock *hlock)
  3844. {
  3845. unsigned int depth = curr->lockdep_depth;
  3846. /*
  3847. * Keep track of points where we cross into an interrupt context:
  3848. */
  3849. if (depth) {
  3850. struct held_lock *prev_hlock;
  3851. prev_hlock = curr->held_locks + depth-1;
  3852. /*
  3853. * If we cross into another context, reset the
  3854. * hash key (this also prevents the checking and the
  3855. * adding of the dependency to 'prev'):
  3856. */
  3857. if (prev_hlock->irq_context != hlock->irq_context)
  3858. return 1;
  3859. }
  3860. return 0;
  3861. }
  3862. /*
  3863. * Mark a lock with a usage bit, and validate the state transition:
  3864. */
  3865. static int mark_lock(struct task_struct *curr, struct held_lock *this,
  3866. enum lock_usage_bit new_bit)
  3867. {
  3868. unsigned int new_mask, ret = 1;
  3869. if (new_bit >= LOCK_USAGE_STATES) {
  3870. DEBUG_LOCKS_WARN_ON(1);
  3871. return 0;
  3872. }
  3873. if (new_bit == LOCK_USED && this->read)
  3874. new_bit = LOCK_USED_READ;
  3875. new_mask = 1 << new_bit;
  3876. /*
  3877. * If already set then do not dirty the cacheline,
  3878. * nor do any checks:
  3879. */
  3880. if (likely(hlock_class(this)->usage_mask & new_mask))
  3881. return 1;
  3882. if (!graph_lock())
  3883. return 0;
  3884. /*
  3885. * Make sure we didn't race:
  3886. */
  3887. if (unlikely(hlock_class(this)->usage_mask & new_mask))
  3888. goto unlock;
  3889. if (!hlock_class(this)->usage_mask)
  3890. debug_atomic_dec(nr_unused_locks);
  3891. hlock_class(this)->usage_mask |= new_mask;
  3892. if (new_bit < LOCK_TRACE_STATES) {
  3893. if (!(hlock_class(this)->usage_traces[new_bit] = save_trace()))
  3894. return 0;
  3895. }
  3896. if (new_bit < LOCK_USED) {
  3897. ret = mark_lock_irq(curr, this, new_bit);
  3898. if (!ret)
  3899. return 0;
  3900. }
  3901. unlock:
  3902. graph_unlock();
  3903. /*
  3904. * We must printk outside of the graph_lock:
  3905. */
  3906. if (ret == 2) {
  3907. printk("\nmarked lock as {%s}:\n", usage_str[new_bit]);
  3908. print_lock(this);
  3909. print_irqtrace_events(curr);
  3910. dump_stack();
  3911. }
  3912. return ret;
  3913. }
  3914. static inline short task_wait_context(struct task_struct *curr)
  3915. {
  3916. /*
  3917. * Set appropriate wait type for the context; for IRQs we have to take
  3918. * into account force_irqthread as that is implied by PREEMPT_RT.
  3919. */
  3920. if (lockdep_hardirq_context()) {
  3921. /*
  3922. * Check if force_irqthreads will run us threaded.
  3923. */
  3924. if (curr->hardirq_threaded || curr->irq_config)
  3925. return LD_WAIT_CONFIG;
  3926. return LD_WAIT_SPIN;
  3927. } else if (curr->softirq_context) {
  3928. /*
  3929. * Softirqs are always threaded.
  3930. */
  3931. return LD_WAIT_CONFIG;
  3932. }
  3933. return LD_WAIT_MAX;
  3934. }
  3935. static int
  3936. print_lock_invalid_wait_context(struct task_struct *curr,
  3937. struct held_lock *hlock)
  3938. {
  3939. short curr_inner;
  3940. if (!debug_locks_off())
  3941. return 0;
  3942. if (debug_locks_silent)
  3943. return 0;
  3944. pr_warn("\n");
  3945. pr_warn("=============================\n");
  3946. pr_warn("[ BUG: Invalid wait context ]\n");
  3947. print_kernel_ident();
  3948. pr_warn("-----------------------------\n");
  3949. pr_warn("%s/%d is trying to lock:\n", curr->comm, task_pid_nr(curr));
  3950. print_lock(hlock);
  3951. pr_warn("other info that might help us debug this:\n");
  3952. curr_inner = task_wait_context(curr);
  3953. pr_warn("context-{%d:%d}\n", curr_inner, curr_inner);
  3954. lockdep_print_held_locks(curr);
  3955. pr_warn("stack backtrace:\n");
  3956. dump_stack();
  3957. return 0;
  3958. }
  3959. /*
  3960. * Verify the wait_type context.
  3961. *
  3962. * This check validates we takes locks in the right wait-type order; that is it
  3963. * ensures that we do not take mutexes inside spinlocks and do not attempt to
  3964. * acquire spinlocks inside raw_spinlocks and the sort.
  3965. *
  3966. * The entire thing is slightly more complex because of RCU, RCU is a lock that
  3967. * can be taken from (pretty much) any context but also has constraints.
  3968. * However when taken in a stricter environment the RCU lock does not loosen
  3969. * the constraints.
  3970. *
  3971. * Therefore we must look for the strictest environment in the lock stack and
  3972. * compare that to the lock we're trying to acquire.
  3973. */
  3974. static int check_wait_context(struct task_struct *curr, struct held_lock *next)
  3975. {
  3976. u8 next_inner = hlock_class(next)->wait_type_inner;
  3977. u8 next_outer = hlock_class(next)->wait_type_outer;
  3978. u8 curr_inner;
  3979. int depth;
  3980. if (!next_inner || next->trylock)
  3981. return 0;
  3982. if (!next_outer)
  3983. next_outer = next_inner;
  3984. /*
  3985. * Find start of current irq_context..
  3986. */
  3987. for (depth = curr->lockdep_depth - 1; depth >= 0; depth--) {
  3988. struct held_lock *prev = curr->held_locks + depth;
  3989. if (prev->irq_context != next->irq_context)
  3990. break;
  3991. }
  3992. depth++;
  3993. curr_inner = task_wait_context(curr);
  3994. for (; depth < curr->lockdep_depth; depth++) {
  3995. struct held_lock *prev = curr->held_locks + depth;
  3996. u8 prev_inner = hlock_class(prev)->wait_type_inner;
  3997. if (prev_inner) {
  3998. /*
  3999. * We can have a bigger inner than a previous one
  4000. * when outer is smaller than inner, as with RCU.
  4001. *
  4002. * Also due to trylocks.
  4003. */
  4004. curr_inner = min(curr_inner, prev_inner);
  4005. }
  4006. }
  4007. if (next_outer > curr_inner)
  4008. return print_lock_invalid_wait_context(curr, next);
  4009. return 0;
  4010. }
  4011. #else /* CONFIG_PROVE_LOCKING */
  4012. static inline int
  4013. mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
  4014. {
  4015. return 1;
  4016. }
  4017. static inline unsigned int task_irq_context(struct task_struct *task)
  4018. {
  4019. return 0;
  4020. }
  4021. static inline int separate_irq_context(struct task_struct *curr,
  4022. struct held_lock *hlock)
  4023. {
  4024. return 0;
  4025. }
  4026. static inline int check_wait_context(struct task_struct *curr,
  4027. struct held_lock *next)
  4028. {
  4029. return 0;
  4030. }
  4031. #endif /* CONFIG_PROVE_LOCKING */
  4032. /*
  4033. * Initialize a lock instance's lock-class mapping info:
  4034. */
  4035. void lockdep_init_map_type(struct lockdep_map *lock, const char *name,
  4036. struct lock_class_key *key, int subclass,
  4037. u8 inner, u8 outer, u8 lock_type)
  4038. {
  4039. int i;
  4040. for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
  4041. lock->class_cache[i] = NULL;
  4042. #ifdef CONFIG_LOCK_STAT
  4043. lock->cpu = raw_smp_processor_id();
  4044. #endif
  4045. /*
  4046. * Can't be having no nameless bastards around this place!
  4047. */
  4048. if (DEBUG_LOCKS_WARN_ON(!name)) {
  4049. lock->name = "NULL";
  4050. return;
  4051. }
  4052. lock->name = name;
  4053. lock->wait_type_outer = outer;
  4054. lock->wait_type_inner = inner;
  4055. lock->lock_type = lock_type;
  4056. /*
  4057. * No key, no joy, we need to hash something.
  4058. */
  4059. if (DEBUG_LOCKS_WARN_ON(!key))
  4060. return;
  4061. /*
  4062. * Sanity check, the lock-class key must either have been allocated
  4063. * statically or must have been registered as a dynamic key.
  4064. */
  4065. if (!static_obj(key) && !is_dynamic_key(key)) {
  4066. if (debug_locks)
  4067. printk(KERN_ERR "BUG: key %px has not been registered!\n", key);
  4068. DEBUG_LOCKS_WARN_ON(1);
  4069. return;
  4070. }
  4071. lock->key = key;
  4072. if (unlikely(!debug_locks))
  4073. return;
  4074. if (subclass) {
  4075. unsigned long flags;
  4076. if (DEBUG_LOCKS_WARN_ON(!lockdep_enabled()))
  4077. return;
  4078. raw_local_irq_save(flags);
  4079. lockdep_recursion_inc();
  4080. register_lock_class(lock, subclass, 1);
  4081. lockdep_recursion_finish();
  4082. raw_local_irq_restore(flags);
  4083. }
  4084. }
  4085. EXPORT_SYMBOL_GPL(lockdep_init_map_type);
  4086. struct lock_class_key __lockdep_no_validate__;
  4087. EXPORT_SYMBOL_GPL(__lockdep_no_validate__);
  4088. static void
  4089. print_lock_nested_lock_not_held(struct task_struct *curr,
  4090. struct held_lock *hlock,
  4091. unsigned long ip)
  4092. {
  4093. if (!debug_locks_off())
  4094. return;
  4095. if (debug_locks_silent)
  4096. return;
  4097. pr_warn("\n");
  4098. pr_warn("==================================\n");
  4099. pr_warn("WARNING: Nested lock was not taken\n");
  4100. print_kernel_ident();
  4101. pr_warn("----------------------------------\n");
  4102. pr_warn("%s/%d is trying to lock:\n", curr->comm, task_pid_nr(curr));
  4103. print_lock(hlock);
  4104. pr_warn("\nbut this task is not holding:\n");
  4105. pr_warn("%s\n", hlock->nest_lock->name);
  4106. pr_warn("\nstack backtrace:\n");
  4107. dump_stack();
  4108. pr_warn("\nother info that might help us debug this:\n");
  4109. lockdep_print_held_locks(curr);
  4110. pr_warn("\nstack backtrace:\n");
  4111. dump_stack();
  4112. }
  4113. static int __lock_is_held(const struct lockdep_map *lock, int read);
  4114. /*
  4115. * This gets called for every mutex_lock*()/spin_lock*() operation.
  4116. * We maintain the dependency maps and validate the locking attempt:
  4117. *
  4118. * The callers must make sure that IRQs are disabled before calling it,
  4119. * otherwise we could get an interrupt which would want to take locks,
  4120. * which would end up in lockdep again.
  4121. */
  4122. static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  4123. int trylock, int read, int check, int hardirqs_off,
  4124. struct lockdep_map *nest_lock, unsigned long ip,
  4125. int references, int pin_count)
  4126. {
  4127. struct task_struct *curr = current;
  4128. struct lock_class *class = NULL;
  4129. struct held_lock *hlock;
  4130. unsigned int depth;
  4131. int chain_head = 0;
  4132. int class_idx;
  4133. u64 chain_key;
  4134. if (unlikely(!debug_locks))
  4135. return 0;
  4136. if (!prove_locking || lock->key == &__lockdep_no_validate__)
  4137. check = 0;
  4138. if (subclass < NR_LOCKDEP_CACHING_CLASSES)
  4139. class = lock->class_cache[subclass];
  4140. /*
  4141. * Not cached?
  4142. */
  4143. if (unlikely(!class)) {
  4144. class = register_lock_class(lock, subclass, 0);
  4145. if (!class)
  4146. return 0;
  4147. }
  4148. debug_class_ops_inc(class);
  4149. if (very_verbose(class)) {
  4150. printk("\nacquire class [%px] %s", class->key, class->name);
  4151. if (class->name_version > 1)
  4152. printk(KERN_CONT "#%d", class->name_version);
  4153. printk(KERN_CONT "\n");
  4154. dump_stack();
  4155. }
  4156. /*
  4157. * Add the lock to the list of currently held locks.
  4158. * (we dont increase the depth just yet, up until the
  4159. * dependency checks are done)
  4160. */
  4161. depth = curr->lockdep_depth;
  4162. /*
  4163. * Ran out of static storage for our per-task lock stack again have we?
  4164. */
  4165. if (DEBUG_LOCKS_WARN_ON(depth >= MAX_LOCK_DEPTH))
  4166. return 0;
  4167. class_idx = class - lock_classes;
  4168. if (depth) { /* we're holding locks */
  4169. hlock = curr->held_locks + depth - 1;
  4170. if (hlock->class_idx == class_idx && nest_lock) {
  4171. if (!references)
  4172. references++;
  4173. if (!hlock->references)
  4174. hlock->references++;
  4175. hlock->references += references;
  4176. /* Overflow */
  4177. if (DEBUG_LOCKS_WARN_ON(hlock->references < references))
  4178. return 0;
  4179. return 2;
  4180. }
  4181. }
  4182. hlock = curr->held_locks + depth;
  4183. /*
  4184. * Plain impossible, we just registered it and checked it weren't no
  4185. * NULL like.. I bet this mushroom I ate was good!
  4186. */
  4187. if (DEBUG_LOCKS_WARN_ON(!class))
  4188. return 0;
  4189. hlock->class_idx = class_idx;
  4190. hlock->acquire_ip = ip;
  4191. hlock->instance = lock;
  4192. hlock->nest_lock = nest_lock;
  4193. hlock->irq_context = task_irq_context(curr);
  4194. hlock->trylock = trylock;
  4195. hlock->read = read;
  4196. hlock->check = check;
  4197. hlock->hardirqs_off = !!hardirqs_off;
  4198. hlock->references = references;
  4199. #ifdef CONFIG_LOCK_STAT
  4200. hlock->waittime_stamp = 0;
  4201. hlock->holdtime_stamp = lockstat_clock();
  4202. #endif
  4203. hlock->pin_count = pin_count;
  4204. if (check_wait_context(curr, hlock))
  4205. return 0;
  4206. /* Initialize the lock usage bit */
  4207. if (!mark_usage(curr, hlock, check))
  4208. return 0;
  4209. /*
  4210. * Calculate the chain hash: it's the combined hash of all the
  4211. * lock keys along the dependency chain. We save the hash value
  4212. * at every step so that we can get the current hash easily
  4213. * after unlock. The chain hash is then used to cache dependency
  4214. * results.
  4215. *
  4216. * The 'key ID' is what is the most compact key value to drive
  4217. * the hash, not class->key.
  4218. */
  4219. /*
  4220. * Whoops, we did it again.. class_idx is invalid.
  4221. */
  4222. if (DEBUG_LOCKS_WARN_ON(!test_bit(class_idx, lock_classes_in_use)))
  4223. return 0;
  4224. chain_key = curr->curr_chain_key;
  4225. if (!depth) {
  4226. /*
  4227. * How can we have a chain hash when we ain't got no keys?!
  4228. */
  4229. if (DEBUG_LOCKS_WARN_ON(chain_key != INITIAL_CHAIN_KEY))
  4230. return 0;
  4231. chain_head = 1;
  4232. }
  4233. hlock->prev_chain_key = chain_key;
  4234. if (separate_irq_context(curr, hlock)) {
  4235. chain_key = INITIAL_CHAIN_KEY;
  4236. chain_head = 1;
  4237. }
  4238. chain_key = iterate_chain_key(chain_key, hlock_id(hlock));
  4239. if (nest_lock && !__lock_is_held(nest_lock, -1)) {
  4240. print_lock_nested_lock_not_held(curr, hlock, ip);
  4241. return 0;
  4242. }
  4243. if (!debug_locks_silent) {
  4244. WARN_ON_ONCE(depth && !hlock_class(hlock - 1)->key);
  4245. WARN_ON_ONCE(!hlock_class(hlock)->key);
  4246. }
  4247. if (!validate_chain(curr, hlock, chain_head, chain_key))
  4248. return 0;
  4249. curr->curr_chain_key = chain_key;
  4250. curr->lockdep_depth++;
  4251. check_chain_key(curr);
  4252. #ifdef CONFIG_DEBUG_LOCKDEP
  4253. if (unlikely(!debug_locks))
  4254. return 0;
  4255. #endif
  4256. if (unlikely(curr->lockdep_depth >= MAX_LOCK_DEPTH)) {
  4257. debug_locks_off();
  4258. print_lockdep_off("BUG: MAX_LOCK_DEPTH too low!");
  4259. printk(KERN_DEBUG "depth: %i max: %lu!\n",
  4260. curr->lockdep_depth, MAX_LOCK_DEPTH);
  4261. lockdep_print_held_locks(current);
  4262. debug_show_all_locks();
  4263. dump_stack();
  4264. return 0;
  4265. }
  4266. if (unlikely(curr->lockdep_depth > max_lockdep_depth))
  4267. max_lockdep_depth = curr->lockdep_depth;
  4268. return 1;
  4269. }
  4270. static void print_unlock_imbalance_bug(struct task_struct *curr,
  4271. struct lockdep_map *lock,
  4272. unsigned long ip)
  4273. {
  4274. if (!debug_locks_off())
  4275. return;
  4276. if (debug_locks_silent)
  4277. return;
  4278. pr_warn("\n");
  4279. pr_warn("=====================================\n");
  4280. pr_warn("WARNING: bad unlock balance detected!\n");
  4281. print_kernel_ident();
  4282. pr_warn("-------------------------------------\n");
  4283. pr_warn("%s/%d is trying to release lock (",
  4284. curr->comm, task_pid_nr(curr));
  4285. print_lockdep_cache(lock);
  4286. pr_cont(") at:\n");
  4287. print_ip_sym(KERN_WARNING, ip);
  4288. pr_warn("but there are no more locks to release!\n");
  4289. pr_warn("\nother info that might help us debug this:\n");
  4290. lockdep_print_held_locks(curr);
  4291. pr_warn("\nstack backtrace:\n");
  4292. dump_stack();
  4293. }
  4294. static noinstr int match_held_lock(const struct held_lock *hlock,
  4295. const struct lockdep_map *lock)
  4296. {
  4297. if (hlock->instance == lock)
  4298. return 1;
  4299. if (hlock->references) {
  4300. const struct lock_class *class = lock->class_cache[0];
  4301. if (!class)
  4302. class = look_up_lock_class(lock, 0);
  4303. /*
  4304. * If look_up_lock_class() failed to find a class, we're trying
  4305. * to test if we hold a lock that has never yet been acquired.
  4306. * Clearly if the lock hasn't been acquired _ever_, we're not
  4307. * holding it either, so report failure.
  4308. */
  4309. if (!class)
  4310. return 0;
  4311. /*
  4312. * References, but not a lock we're actually ref-counting?
  4313. * State got messed up, follow the sites that change ->references
  4314. * and try to make sense of it.
  4315. */
  4316. if (DEBUG_LOCKS_WARN_ON(!hlock->nest_lock))
  4317. return 0;
  4318. if (hlock->class_idx == class - lock_classes)
  4319. return 1;
  4320. }
  4321. return 0;
  4322. }
  4323. /* @depth must not be zero */
  4324. static struct held_lock *find_held_lock(struct task_struct *curr,
  4325. struct lockdep_map *lock,
  4326. unsigned int depth, int *idx)
  4327. {
  4328. struct held_lock *ret, *hlock, *prev_hlock;
  4329. int i;
  4330. i = depth - 1;
  4331. hlock = curr->held_locks + i;
  4332. ret = hlock;
  4333. if (match_held_lock(hlock, lock))
  4334. goto out;
  4335. ret = NULL;
  4336. for (i--, prev_hlock = hlock--;
  4337. i >= 0;
  4338. i--, prev_hlock = hlock--) {
  4339. /*
  4340. * We must not cross into another context:
  4341. */
  4342. if (prev_hlock->irq_context != hlock->irq_context) {
  4343. ret = NULL;
  4344. break;
  4345. }
  4346. if (match_held_lock(hlock, lock)) {
  4347. ret = hlock;
  4348. break;
  4349. }
  4350. }
  4351. out:
  4352. *idx = i;
  4353. return ret;
  4354. }
  4355. static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
  4356. int idx, unsigned int *merged)
  4357. {
  4358. struct held_lock *hlock;
  4359. int first_idx = idx;
  4360. if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
  4361. return 0;
  4362. for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) {
  4363. switch (__lock_acquire(hlock->instance,
  4364. hlock_class(hlock)->subclass,
  4365. hlock->trylock,
  4366. hlock->read, hlock->check,
  4367. hlock->hardirqs_off,
  4368. hlock->nest_lock, hlock->acquire_ip,
  4369. hlock->references, hlock->pin_count)) {
  4370. case 0:
  4371. return 1;
  4372. case 1:
  4373. break;
  4374. case 2:
  4375. *merged += (idx == first_idx);
  4376. break;
  4377. default:
  4378. WARN_ON(1);
  4379. return 0;
  4380. }
  4381. }
  4382. return 0;
  4383. }
  4384. static int
  4385. __lock_set_class(struct lockdep_map *lock, const char *name,
  4386. struct lock_class_key *key, unsigned int subclass,
  4387. unsigned long ip)
  4388. {
  4389. struct task_struct *curr = current;
  4390. unsigned int depth, merged = 0;
  4391. struct held_lock *hlock;
  4392. struct lock_class *class;
  4393. int i;
  4394. if (unlikely(!debug_locks))
  4395. return 0;
  4396. depth = curr->lockdep_depth;
  4397. /*
  4398. * This function is about (re)setting the class of a held lock,
  4399. * yet we're not actually holding any locks. Naughty user!
  4400. */
  4401. if (DEBUG_LOCKS_WARN_ON(!depth))
  4402. return 0;
  4403. hlock = find_held_lock(curr, lock, depth, &i);
  4404. if (!hlock) {
  4405. print_unlock_imbalance_bug(curr, lock, ip);
  4406. return 0;
  4407. }
  4408. lockdep_init_map_waits(lock, name, key, 0,
  4409. lock->wait_type_inner,
  4410. lock->wait_type_outer);
  4411. class = register_lock_class(lock, subclass, 0);
  4412. hlock->class_idx = class - lock_classes;
  4413. curr->lockdep_depth = i;
  4414. curr->curr_chain_key = hlock->prev_chain_key;
  4415. if (reacquire_held_locks(curr, depth, i, &merged))
  4416. return 0;
  4417. /*
  4418. * I took it apart and put it back together again, except now I have
  4419. * these 'spare' parts.. where shall I put them.
  4420. */
  4421. if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged))
  4422. return 0;
  4423. return 1;
  4424. }
  4425. static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
  4426. {
  4427. struct task_struct *curr = current;
  4428. unsigned int depth, merged = 0;
  4429. struct held_lock *hlock;
  4430. int i;
  4431. if (unlikely(!debug_locks))
  4432. return 0;
  4433. depth = curr->lockdep_depth;
  4434. /*
  4435. * This function is about (re)setting the class of a held lock,
  4436. * yet we're not actually holding any locks. Naughty user!
  4437. */
  4438. if (DEBUG_LOCKS_WARN_ON(!depth))
  4439. return 0;
  4440. hlock = find_held_lock(curr, lock, depth, &i);
  4441. if (!hlock) {
  4442. print_unlock_imbalance_bug(curr, lock, ip);
  4443. return 0;
  4444. }
  4445. curr->lockdep_depth = i;
  4446. curr->curr_chain_key = hlock->prev_chain_key;
  4447. WARN(hlock->read, "downgrading a read lock");
  4448. hlock->read = 1;
  4449. hlock->acquire_ip = ip;
  4450. if (reacquire_held_locks(curr, depth, i, &merged))
  4451. return 0;
  4452. /* Merging can't happen with unchanged classes.. */
  4453. if (DEBUG_LOCKS_WARN_ON(merged))
  4454. return 0;
  4455. /*
  4456. * I took it apart and put it back together again, except now I have
  4457. * these 'spare' parts.. where shall I put them.
  4458. */
  4459. if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
  4460. return 0;
  4461. return 1;
  4462. }
  4463. /*
  4464. * Remove the lock from the list of currently held locks - this gets
  4465. * called on mutex_unlock()/spin_unlock*() (or on a failed
  4466. * mutex_lock_interruptible()).
  4467. */
  4468. static int
  4469. __lock_release(struct lockdep_map *lock, unsigned long ip)
  4470. {
  4471. struct task_struct *curr = current;
  4472. unsigned int depth, merged = 1;
  4473. struct held_lock *hlock;
  4474. int i;
  4475. if (unlikely(!debug_locks))
  4476. return 0;
  4477. depth = curr->lockdep_depth;
  4478. /*
  4479. * So we're all set to release this lock.. wait what lock? We don't
  4480. * own any locks, you've been drinking again?
  4481. */
  4482. if (depth <= 0) {
  4483. print_unlock_imbalance_bug(curr, lock, ip);
  4484. return 0;
  4485. }
  4486. /*
  4487. * Check whether the lock exists in the current stack
  4488. * of held locks:
  4489. */
  4490. hlock = find_held_lock(curr, lock, depth, &i);
  4491. if (!hlock) {
  4492. print_unlock_imbalance_bug(curr, lock, ip);
  4493. return 0;
  4494. }
  4495. if (hlock->instance == lock)
  4496. lock_release_holdtime(hlock);
  4497. WARN(hlock->pin_count, "releasing a pinned lock\n");
  4498. if (hlock->references) {
  4499. hlock->references--;
  4500. if (hlock->references) {
  4501. /*
  4502. * We had, and after removing one, still have
  4503. * references, the current lock stack is still
  4504. * valid. We're done!
  4505. */
  4506. return 1;
  4507. }
  4508. }
  4509. /*
  4510. * We have the right lock to unlock, 'hlock' points to it.
  4511. * Now we remove it from the stack, and add back the other
  4512. * entries (if any), recalculating the hash along the way:
  4513. */
  4514. curr->lockdep_depth = i;
  4515. curr->curr_chain_key = hlock->prev_chain_key;
  4516. /*
  4517. * The most likely case is when the unlock is on the innermost
  4518. * lock. In this case, we are done!
  4519. */
  4520. if (i == depth-1)
  4521. return 1;
  4522. if (reacquire_held_locks(curr, depth, i + 1, &merged))
  4523. return 0;
  4524. /*
  4525. * We had N bottles of beer on the wall, we drank one, but now
  4526. * there's not N-1 bottles of beer left on the wall...
  4527. * Pouring two of the bottles together is acceptable.
  4528. */
  4529. DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged);
  4530. /*
  4531. * Since reacquire_held_locks() would have called check_chain_key()
  4532. * indirectly via __lock_acquire(), we don't need to do it again
  4533. * on return.
  4534. */
  4535. return 0;
  4536. }
  4537. static __always_inline
  4538. int __lock_is_held(const struct lockdep_map *lock, int read)
  4539. {
  4540. struct task_struct *curr = current;
  4541. int i;
  4542. for (i = 0; i < curr->lockdep_depth; i++) {
  4543. struct held_lock *hlock = curr->held_locks + i;
  4544. if (match_held_lock(hlock, lock)) {
  4545. if (read == -1 || !!hlock->read == read)
  4546. return 1;
  4547. return 0;
  4548. }
  4549. }
  4550. return 0;
  4551. }
  4552. static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock)
  4553. {
  4554. struct pin_cookie cookie = NIL_COOKIE;
  4555. struct task_struct *curr = current;
  4556. int i;
  4557. if (unlikely(!debug_locks))
  4558. return cookie;
  4559. for (i = 0; i < curr->lockdep_depth; i++) {
  4560. struct held_lock *hlock = curr->held_locks + i;
  4561. if (match_held_lock(hlock, lock)) {
  4562. /*
  4563. * Grab 16bits of randomness; this is sufficient to not
  4564. * be guessable and still allows some pin nesting in
  4565. * our u32 pin_count.
  4566. */
  4567. cookie.val = 1 + (prandom_u32() >> 16);
  4568. hlock->pin_count += cookie.val;
  4569. return cookie;
  4570. }
  4571. }
  4572. WARN(1, "pinning an unheld lock\n");
  4573. return cookie;
  4574. }
  4575. static void __lock_repin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
  4576. {
  4577. struct task_struct *curr = current;
  4578. int i;
  4579. if (unlikely(!debug_locks))
  4580. return;
  4581. for (i = 0; i < curr->lockdep_depth; i++) {
  4582. struct held_lock *hlock = curr->held_locks + i;
  4583. if (match_held_lock(hlock, lock)) {
  4584. hlock->pin_count += cookie.val;
  4585. return;
  4586. }
  4587. }
  4588. WARN(1, "pinning an unheld lock\n");
  4589. }
  4590. static void __lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
  4591. {
  4592. struct task_struct *curr = current;
  4593. int i;
  4594. if (unlikely(!debug_locks))
  4595. return;
  4596. for (i = 0; i < curr->lockdep_depth; i++) {
  4597. struct held_lock *hlock = curr->held_locks + i;
  4598. if (match_held_lock(hlock, lock)) {
  4599. if (WARN(!hlock->pin_count, "unpinning an unpinned lock\n"))
  4600. return;
  4601. hlock->pin_count -= cookie.val;
  4602. if (WARN((int)hlock->pin_count < 0, "pin count corrupted\n"))
  4603. hlock->pin_count = 0;
  4604. return;
  4605. }
  4606. }
  4607. WARN(1, "unpinning an unheld lock\n");
  4608. }
  4609. /*
  4610. * Check whether we follow the irq-flags state precisely:
  4611. */
  4612. static noinstr void check_flags(unsigned long flags)
  4613. {
  4614. #if defined(CONFIG_PROVE_LOCKING) && defined(CONFIG_DEBUG_LOCKDEP)
  4615. if (!debug_locks)
  4616. return;
  4617. /* Get the warning out.. */
  4618. instrumentation_begin();
  4619. if (irqs_disabled_flags(flags)) {
  4620. if (DEBUG_LOCKS_WARN_ON(lockdep_hardirqs_enabled())) {
  4621. printk("possible reason: unannotated irqs-off.\n");
  4622. }
  4623. } else {
  4624. if (DEBUG_LOCKS_WARN_ON(!lockdep_hardirqs_enabled())) {
  4625. printk("possible reason: unannotated irqs-on.\n");
  4626. }
  4627. }
  4628. /*
  4629. * We dont accurately track softirq state in e.g.
  4630. * hardirq contexts (such as on 4KSTACKS), so only
  4631. * check if not in hardirq contexts:
  4632. */
  4633. if (!hardirq_count()) {
  4634. if (softirq_count()) {
  4635. /* like the above, but with softirqs */
  4636. DEBUG_LOCKS_WARN_ON(current->softirqs_enabled);
  4637. } else {
  4638. /* lick the above, does it taste good? */
  4639. DEBUG_LOCKS_WARN_ON(!current->softirqs_enabled);
  4640. }
  4641. }
  4642. if (!debug_locks)
  4643. print_irqtrace_events(current);
  4644. instrumentation_end();
  4645. #endif
  4646. }
  4647. void lock_set_class(struct lockdep_map *lock, const char *name,
  4648. struct lock_class_key *key, unsigned int subclass,
  4649. unsigned long ip)
  4650. {
  4651. unsigned long flags;
  4652. if (unlikely(!lockdep_enabled()))
  4653. return;
  4654. raw_local_irq_save(flags);
  4655. lockdep_recursion_inc();
  4656. check_flags(flags);
  4657. if (__lock_set_class(lock, name, key, subclass, ip))
  4658. check_chain_key(current);
  4659. lockdep_recursion_finish();
  4660. raw_local_irq_restore(flags);
  4661. }
  4662. EXPORT_SYMBOL_GPL(lock_set_class);
  4663. void lock_downgrade(struct lockdep_map *lock, unsigned long ip)
  4664. {
  4665. unsigned long flags;
  4666. if (unlikely(!lockdep_enabled()))
  4667. return;
  4668. raw_local_irq_save(flags);
  4669. lockdep_recursion_inc();
  4670. check_flags(flags);
  4671. if (__lock_downgrade(lock, ip))
  4672. check_chain_key(current);
  4673. lockdep_recursion_finish();
  4674. raw_local_irq_restore(flags);
  4675. }
  4676. EXPORT_SYMBOL_GPL(lock_downgrade);
  4677. /* NMI context !!! */
  4678. static void verify_lock_unused(struct lockdep_map *lock, struct held_lock *hlock, int subclass)
  4679. {
  4680. #ifdef CONFIG_PROVE_LOCKING
  4681. struct lock_class *class = look_up_lock_class(lock, subclass);
  4682. unsigned long mask = LOCKF_USED;
  4683. /* if it doesn't have a class (yet), it certainly hasn't been used yet */
  4684. if (!class)
  4685. return;
  4686. /*
  4687. * READ locks only conflict with USED, such that if we only ever use
  4688. * READ locks, there is no deadlock possible -- RCU.
  4689. */
  4690. if (!hlock->read)
  4691. mask |= LOCKF_USED_READ;
  4692. if (!(class->usage_mask & mask))
  4693. return;
  4694. hlock->class_idx = class - lock_classes;
  4695. print_usage_bug(current, hlock, LOCK_USED, LOCK_USAGE_STATES);
  4696. #endif
  4697. }
  4698. static bool lockdep_nmi(void)
  4699. {
  4700. if (raw_cpu_read(lockdep_recursion))
  4701. return false;
  4702. if (!in_nmi())
  4703. return false;
  4704. return true;
  4705. }
  4706. /*
  4707. * read_lock() is recursive if:
  4708. * 1. We force lockdep think this way in selftests or
  4709. * 2. The implementation is not queued read/write lock or
  4710. * 3. The locker is at an in_interrupt() context.
  4711. */
  4712. bool read_lock_is_recursive(void)
  4713. {
  4714. return force_read_lock_recursive ||
  4715. !IS_ENABLED(CONFIG_QUEUED_RWLOCKS) ||
  4716. in_interrupt();
  4717. }
  4718. EXPORT_SYMBOL_GPL(read_lock_is_recursive);
  4719. /*
  4720. * We are not always called with irqs disabled - do that here,
  4721. * and also avoid lockdep recursion:
  4722. */
  4723. void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  4724. int trylock, int read, int check,
  4725. struct lockdep_map *nest_lock, unsigned long ip)
  4726. {
  4727. unsigned long flags;
  4728. trace_lock_acquire(lock, subclass, trylock, read, check, nest_lock, ip);
  4729. if (!debug_locks)
  4730. return;
  4731. if (unlikely(!lockdep_enabled())) {
  4732. /* XXX allow trylock from NMI ?!? */
  4733. if (lockdep_nmi() && !trylock) {
  4734. struct held_lock hlock;
  4735. hlock.acquire_ip = ip;
  4736. hlock.instance = lock;
  4737. hlock.nest_lock = nest_lock;
  4738. hlock.irq_context = 2; // XXX
  4739. hlock.trylock = trylock;
  4740. hlock.read = read;
  4741. hlock.check = check;
  4742. hlock.hardirqs_off = true;
  4743. hlock.references = 0;
  4744. verify_lock_unused(lock, &hlock, subclass);
  4745. }
  4746. return;
  4747. }
  4748. raw_local_irq_save(flags);
  4749. check_flags(flags);
  4750. lockdep_recursion_inc();
  4751. __lock_acquire(lock, subclass, trylock, read, check,
  4752. irqs_disabled_flags(flags), nest_lock, ip, 0, 0);
  4753. lockdep_recursion_finish();
  4754. raw_local_irq_restore(flags);
  4755. }
  4756. EXPORT_SYMBOL_GPL(lock_acquire);
  4757. void lock_release(struct lockdep_map *lock, unsigned long ip)
  4758. {
  4759. unsigned long flags;
  4760. trace_lock_release(lock, ip);
  4761. if (unlikely(!lockdep_enabled()))
  4762. return;
  4763. raw_local_irq_save(flags);
  4764. check_flags(flags);
  4765. lockdep_recursion_inc();
  4766. if (__lock_release(lock, ip))
  4767. check_chain_key(current);
  4768. lockdep_recursion_finish();
  4769. raw_local_irq_restore(flags);
  4770. }
  4771. EXPORT_SYMBOL_GPL(lock_release);
  4772. noinstr int lock_is_held_type(const struct lockdep_map *lock, int read)
  4773. {
  4774. unsigned long flags;
  4775. int ret = 0;
  4776. if (unlikely(!lockdep_enabled()))
  4777. return 1; /* avoid false negative lockdep_assert_held() */
  4778. raw_local_irq_save(flags);
  4779. check_flags(flags);
  4780. lockdep_recursion_inc();
  4781. ret = __lock_is_held(lock, read);
  4782. lockdep_recursion_finish();
  4783. raw_local_irq_restore(flags);
  4784. return ret;
  4785. }
  4786. EXPORT_SYMBOL_GPL(lock_is_held_type);
  4787. NOKPROBE_SYMBOL(lock_is_held_type);
  4788. struct pin_cookie lock_pin_lock(struct lockdep_map *lock)
  4789. {
  4790. struct pin_cookie cookie = NIL_COOKIE;
  4791. unsigned long flags;
  4792. if (unlikely(!lockdep_enabled()))
  4793. return cookie;
  4794. raw_local_irq_save(flags);
  4795. check_flags(flags);
  4796. lockdep_recursion_inc();
  4797. cookie = __lock_pin_lock(lock);
  4798. lockdep_recursion_finish();
  4799. raw_local_irq_restore(flags);
  4800. return cookie;
  4801. }
  4802. EXPORT_SYMBOL_GPL(lock_pin_lock);
  4803. void lock_repin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
  4804. {
  4805. unsigned long flags;
  4806. if (unlikely(!lockdep_enabled()))
  4807. return;
  4808. raw_local_irq_save(flags);
  4809. check_flags(flags);
  4810. lockdep_recursion_inc();
  4811. __lock_repin_lock(lock, cookie);
  4812. lockdep_recursion_finish();
  4813. raw_local_irq_restore(flags);
  4814. }
  4815. EXPORT_SYMBOL_GPL(lock_repin_lock);
  4816. void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
  4817. {
  4818. unsigned long flags;
  4819. if (unlikely(!lockdep_enabled()))
  4820. return;
  4821. raw_local_irq_save(flags);
  4822. check_flags(flags);
  4823. lockdep_recursion_inc();
  4824. __lock_unpin_lock(lock, cookie);
  4825. lockdep_recursion_finish();
  4826. raw_local_irq_restore(flags);
  4827. }
  4828. EXPORT_SYMBOL_GPL(lock_unpin_lock);
  4829. #ifdef CONFIG_LOCK_STAT
  4830. static void print_lock_contention_bug(struct task_struct *curr,
  4831. struct lockdep_map *lock,
  4832. unsigned long ip)
  4833. {
  4834. if (!debug_locks_off())
  4835. return;
  4836. if (debug_locks_silent)
  4837. return;
  4838. pr_warn("\n");
  4839. pr_warn("=================================\n");
  4840. pr_warn("WARNING: bad contention detected!\n");
  4841. print_kernel_ident();
  4842. pr_warn("---------------------------------\n");
  4843. pr_warn("%s/%d is trying to contend lock (",
  4844. curr->comm, task_pid_nr(curr));
  4845. print_lockdep_cache(lock);
  4846. pr_cont(") at:\n");
  4847. print_ip_sym(KERN_WARNING, ip);
  4848. pr_warn("but there are no locks held!\n");
  4849. pr_warn("\nother info that might help us debug this:\n");
  4850. lockdep_print_held_locks(curr);
  4851. pr_warn("\nstack backtrace:\n");
  4852. dump_stack();
  4853. }
  4854. static void
  4855. __lock_contended(struct lockdep_map *lock, unsigned long ip)
  4856. {
  4857. struct task_struct *curr = current;
  4858. struct held_lock *hlock;
  4859. struct lock_class_stats *stats;
  4860. unsigned int depth;
  4861. int i, contention_point, contending_point;
  4862. depth = curr->lockdep_depth;
  4863. /*
  4864. * Whee, we contended on this lock, except it seems we're not
  4865. * actually trying to acquire anything much at all..
  4866. */
  4867. if (DEBUG_LOCKS_WARN_ON(!depth))
  4868. return;
  4869. hlock = find_held_lock(curr, lock, depth, &i);
  4870. if (!hlock) {
  4871. print_lock_contention_bug(curr, lock, ip);
  4872. return;
  4873. }
  4874. if (hlock->instance != lock)
  4875. return;
  4876. hlock->waittime_stamp = lockstat_clock();
  4877. contention_point = lock_point(hlock_class(hlock)->contention_point, ip);
  4878. contending_point = lock_point(hlock_class(hlock)->contending_point,
  4879. lock->ip);
  4880. stats = get_lock_stats(hlock_class(hlock));
  4881. if (contention_point < LOCKSTAT_POINTS)
  4882. stats->contention_point[contention_point]++;
  4883. if (contending_point < LOCKSTAT_POINTS)
  4884. stats->contending_point[contending_point]++;
  4885. if (lock->cpu != smp_processor_id())
  4886. stats->bounces[bounce_contended + !!hlock->read]++;
  4887. }
  4888. static void
  4889. __lock_acquired(struct lockdep_map *lock, unsigned long ip)
  4890. {
  4891. struct task_struct *curr = current;
  4892. struct held_lock *hlock;
  4893. struct lock_class_stats *stats;
  4894. unsigned int depth;
  4895. u64 now, waittime = 0;
  4896. int i, cpu;
  4897. depth = curr->lockdep_depth;
  4898. /*
  4899. * Yay, we acquired ownership of this lock we didn't try to
  4900. * acquire, how the heck did that happen?
  4901. */
  4902. if (DEBUG_LOCKS_WARN_ON(!depth))
  4903. return;
  4904. hlock = find_held_lock(curr, lock, depth, &i);
  4905. if (!hlock) {
  4906. print_lock_contention_bug(curr, lock, _RET_IP_);
  4907. return;
  4908. }
  4909. if (hlock->instance != lock)
  4910. return;
  4911. cpu = smp_processor_id();
  4912. if (hlock->waittime_stamp) {
  4913. now = lockstat_clock();
  4914. waittime = now - hlock->waittime_stamp;
  4915. hlock->holdtime_stamp = now;
  4916. }
  4917. stats = get_lock_stats(hlock_class(hlock));
  4918. if (waittime) {
  4919. if (hlock->read)
  4920. lock_time_inc(&stats->read_waittime, waittime);
  4921. else
  4922. lock_time_inc(&stats->write_waittime, waittime);
  4923. }
  4924. if (lock->cpu != cpu)
  4925. stats->bounces[bounce_acquired + !!hlock->read]++;
  4926. lock->cpu = cpu;
  4927. lock->ip = ip;
  4928. }
  4929. void lock_contended(struct lockdep_map *lock, unsigned long ip)
  4930. {
  4931. unsigned long flags;
  4932. trace_lock_contended(lock, ip);
  4933. if (unlikely(!lock_stat || !lockdep_enabled()))
  4934. return;
  4935. raw_local_irq_save(flags);
  4936. check_flags(flags);
  4937. lockdep_recursion_inc();
  4938. __lock_contended(lock, ip);
  4939. lockdep_recursion_finish();
  4940. raw_local_irq_restore(flags);
  4941. }
  4942. EXPORT_SYMBOL_GPL(lock_contended);
  4943. void lock_acquired(struct lockdep_map *lock, unsigned long ip)
  4944. {
  4945. unsigned long flags;
  4946. trace_lock_acquired(lock, ip);
  4947. if (unlikely(!lock_stat || !lockdep_enabled()))
  4948. return;
  4949. raw_local_irq_save(flags);
  4950. check_flags(flags);
  4951. lockdep_recursion_inc();
  4952. __lock_acquired(lock, ip);
  4953. lockdep_recursion_finish();
  4954. raw_local_irq_restore(flags);
  4955. }
  4956. EXPORT_SYMBOL_GPL(lock_acquired);
  4957. #endif
  4958. /*
  4959. * Used by the testsuite, sanitize the validator state
  4960. * after a simulated failure:
  4961. */
  4962. void lockdep_reset(void)
  4963. {
  4964. unsigned long flags;
  4965. int i;
  4966. raw_local_irq_save(flags);
  4967. lockdep_init_task(current);
  4968. memset(current->held_locks, 0, MAX_LOCK_DEPTH*sizeof(struct held_lock));
  4969. nr_hardirq_chains = 0;
  4970. nr_softirq_chains = 0;
  4971. nr_process_chains = 0;
  4972. debug_locks = 1;
  4973. for (i = 0; i < CHAINHASH_SIZE; i++)
  4974. INIT_HLIST_HEAD(chainhash_table + i);
  4975. raw_local_irq_restore(flags);
  4976. }
  4977. /* Remove a class from a lock chain. Must be called with the graph lock held. */
  4978. static void remove_class_from_lock_chain(struct pending_free *pf,
  4979. struct lock_chain *chain,
  4980. struct lock_class *class)
  4981. {
  4982. #ifdef CONFIG_PROVE_LOCKING
  4983. int i;
  4984. for (i = chain->base; i < chain->base + chain->depth; i++) {
  4985. if (chain_hlock_class_idx(chain_hlocks[i]) != class - lock_classes)
  4986. continue;
  4987. /*
  4988. * Each lock class occurs at most once in a lock chain so once
  4989. * we found a match we can break out of this loop.
  4990. */
  4991. goto free_lock_chain;
  4992. }
  4993. /* Since the chain has not been modified, return. */
  4994. return;
  4995. free_lock_chain:
  4996. free_chain_hlocks(chain->base, chain->depth);
  4997. /* Overwrite the chain key for concurrent RCU readers. */
  4998. WRITE_ONCE(chain->chain_key, INITIAL_CHAIN_KEY);
  4999. dec_chains(chain->irq_context);
  5000. /*
  5001. * Note: calling hlist_del_rcu() from inside a
  5002. * hlist_for_each_entry_rcu() loop is safe.
  5003. */
  5004. hlist_del_rcu(&chain->entry);
  5005. __set_bit(chain - lock_chains, pf->lock_chains_being_freed);
  5006. nr_zapped_lock_chains++;
  5007. #endif
  5008. }
  5009. /* Must be called with the graph lock held. */
  5010. static void remove_class_from_lock_chains(struct pending_free *pf,
  5011. struct lock_class *class)
  5012. {
  5013. struct lock_chain *chain;
  5014. struct hlist_head *head;
  5015. int i;
  5016. for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
  5017. head = chainhash_table + i;
  5018. hlist_for_each_entry_rcu(chain, head, entry) {
  5019. remove_class_from_lock_chain(pf, chain, class);
  5020. }
  5021. }
  5022. }
  5023. /*
  5024. * Remove all references to a lock class. The caller must hold the graph lock.
  5025. */
  5026. static void zap_class(struct pending_free *pf, struct lock_class *class)
  5027. {
  5028. struct lock_list *entry;
  5029. int i;
  5030. WARN_ON_ONCE(!class->key);
  5031. /*
  5032. * Remove all dependencies this lock is
  5033. * involved in:
  5034. */
  5035. for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
  5036. entry = list_entries + i;
  5037. if (entry->class != class && entry->links_to != class)
  5038. continue;
  5039. __clear_bit(i, list_entries_in_use);
  5040. nr_list_entries--;
  5041. list_del_rcu(&entry->entry);
  5042. }
  5043. if (list_empty(&class->locks_after) &&
  5044. list_empty(&class->locks_before)) {
  5045. list_move_tail(&class->lock_entry, &pf->zapped);
  5046. hlist_del_rcu(&class->hash_entry);
  5047. WRITE_ONCE(class->key, NULL);
  5048. WRITE_ONCE(class->name, NULL);
  5049. nr_lock_classes--;
  5050. __clear_bit(class - lock_classes, lock_classes_in_use);
  5051. if (class - lock_classes == max_lock_class_idx)
  5052. max_lock_class_idx--;
  5053. } else {
  5054. WARN_ONCE(true, "%s() failed for class %s\n", __func__,
  5055. class->name);
  5056. }
  5057. remove_class_from_lock_chains(pf, class);
  5058. nr_zapped_classes++;
  5059. }
  5060. static void reinit_class(struct lock_class *class)
  5061. {
  5062. void *const p = class;
  5063. const unsigned int offset = offsetof(struct lock_class, key);
  5064. WARN_ON_ONCE(!class->lock_entry.next);
  5065. WARN_ON_ONCE(!list_empty(&class->locks_after));
  5066. WARN_ON_ONCE(!list_empty(&class->locks_before));
  5067. memset(p + offset, 0, sizeof(*class) - offset);
  5068. WARN_ON_ONCE(!class->lock_entry.next);
  5069. WARN_ON_ONCE(!list_empty(&class->locks_after));
  5070. WARN_ON_ONCE(!list_empty(&class->locks_before));
  5071. }
  5072. static inline int within(const void *addr, void *start, unsigned long size)
  5073. {
  5074. return addr >= start && addr < start + size;
  5075. }
  5076. static bool inside_selftest(void)
  5077. {
  5078. return current == lockdep_selftest_task_struct;
  5079. }
  5080. /* The caller must hold the graph lock. */
  5081. static struct pending_free *get_pending_free(void)
  5082. {
  5083. return delayed_free.pf + delayed_free.index;
  5084. }
  5085. static void free_zapped_rcu(struct rcu_head *cb);
  5086. /*
  5087. * Schedule an RCU callback if no RCU callback is pending. Must be called with
  5088. * the graph lock held.
  5089. */
  5090. static void call_rcu_zapped(struct pending_free *pf)
  5091. {
  5092. WARN_ON_ONCE(inside_selftest());
  5093. if (list_empty(&pf->zapped))
  5094. return;
  5095. if (delayed_free.scheduled)
  5096. return;
  5097. delayed_free.scheduled = true;
  5098. WARN_ON_ONCE(delayed_free.pf + delayed_free.index != pf);
  5099. delayed_free.index ^= 1;
  5100. call_rcu(&delayed_free.rcu_head, free_zapped_rcu);
  5101. }
  5102. /* The caller must hold the graph lock. May be called from RCU context. */
  5103. static void __free_zapped_classes(struct pending_free *pf)
  5104. {
  5105. struct lock_class *class;
  5106. check_data_structures();
  5107. list_for_each_entry(class, &pf->zapped, lock_entry)
  5108. reinit_class(class);
  5109. list_splice_init(&pf->zapped, &free_lock_classes);
  5110. #ifdef CONFIG_PROVE_LOCKING
  5111. bitmap_andnot(lock_chains_in_use, lock_chains_in_use,
  5112. pf->lock_chains_being_freed, ARRAY_SIZE(lock_chains));
  5113. bitmap_clear(pf->lock_chains_being_freed, 0, ARRAY_SIZE(lock_chains));
  5114. #endif
  5115. }
  5116. static void free_zapped_rcu(struct rcu_head *ch)
  5117. {
  5118. struct pending_free *pf;
  5119. unsigned long flags;
  5120. if (WARN_ON_ONCE(ch != &delayed_free.rcu_head))
  5121. return;
  5122. raw_local_irq_save(flags);
  5123. lockdep_lock();
  5124. /* closed head */
  5125. pf = delayed_free.pf + (delayed_free.index ^ 1);
  5126. __free_zapped_classes(pf);
  5127. delayed_free.scheduled = false;
  5128. /*
  5129. * If there's anything on the open list, close and start a new callback.
  5130. */
  5131. call_rcu_zapped(delayed_free.pf + delayed_free.index);
  5132. lockdep_unlock();
  5133. raw_local_irq_restore(flags);
  5134. }
  5135. /*
  5136. * Remove all lock classes from the class hash table and from the
  5137. * all_lock_classes list whose key or name is in the address range [start,
  5138. * start + size). Move these lock classes to the zapped_classes list. Must
  5139. * be called with the graph lock held.
  5140. */
  5141. static void __lockdep_free_key_range(struct pending_free *pf, void *start,
  5142. unsigned long size)
  5143. {
  5144. struct lock_class *class;
  5145. struct hlist_head *head;
  5146. int i;
  5147. /* Unhash all classes that were created by a module. */
  5148. for (i = 0; i < CLASSHASH_SIZE; i++) {
  5149. head = classhash_table + i;
  5150. hlist_for_each_entry_rcu(class, head, hash_entry) {
  5151. if (!within(class->key, start, size) &&
  5152. !within(class->name, start, size))
  5153. continue;
  5154. zap_class(pf, class);
  5155. }
  5156. }
  5157. }
  5158. /*
  5159. * Used in module.c to remove lock classes from memory that is going to be
  5160. * freed; and possibly re-used by other modules.
  5161. *
  5162. * We will have had one synchronize_rcu() before getting here, so we're
  5163. * guaranteed nobody will look up these exact classes -- they're properly dead
  5164. * but still allocated.
  5165. */
  5166. static void lockdep_free_key_range_reg(void *start, unsigned long size)
  5167. {
  5168. struct pending_free *pf;
  5169. unsigned long flags;
  5170. init_data_structures_once();
  5171. raw_local_irq_save(flags);
  5172. lockdep_lock();
  5173. pf = get_pending_free();
  5174. __lockdep_free_key_range(pf, start, size);
  5175. call_rcu_zapped(pf);
  5176. lockdep_unlock();
  5177. raw_local_irq_restore(flags);
  5178. /*
  5179. * Wait for any possible iterators from look_up_lock_class() to pass
  5180. * before continuing to free the memory they refer to.
  5181. */
  5182. synchronize_rcu();
  5183. }
  5184. /*
  5185. * Free all lockdep keys in the range [start, start+size). Does not sleep.
  5186. * Ignores debug_locks. Must only be used by the lockdep selftests.
  5187. */
  5188. static void lockdep_free_key_range_imm(void *start, unsigned long size)
  5189. {
  5190. struct pending_free *pf = delayed_free.pf;
  5191. unsigned long flags;
  5192. init_data_structures_once();
  5193. raw_local_irq_save(flags);
  5194. lockdep_lock();
  5195. __lockdep_free_key_range(pf, start, size);
  5196. __free_zapped_classes(pf);
  5197. lockdep_unlock();
  5198. raw_local_irq_restore(flags);
  5199. }
  5200. void lockdep_free_key_range(void *start, unsigned long size)
  5201. {
  5202. init_data_structures_once();
  5203. if (inside_selftest())
  5204. lockdep_free_key_range_imm(start, size);
  5205. else
  5206. lockdep_free_key_range_reg(start, size);
  5207. }
  5208. /*
  5209. * Check whether any element of the @lock->class_cache[] array refers to a
  5210. * registered lock class. The caller must hold either the graph lock or the
  5211. * RCU read lock.
  5212. */
  5213. static bool lock_class_cache_is_registered(struct lockdep_map *lock)
  5214. {
  5215. struct lock_class *class;
  5216. struct hlist_head *head;
  5217. int i, j;
  5218. for (i = 0; i < CLASSHASH_SIZE; i++) {
  5219. head = classhash_table + i;
  5220. hlist_for_each_entry_rcu(class, head, hash_entry) {
  5221. for (j = 0; j < NR_LOCKDEP_CACHING_CLASSES; j++)
  5222. if (lock->class_cache[j] == class)
  5223. return true;
  5224. }
  5225. }
  5226. return false;
  5227. }
  5228. /* The caller must hold the graph lock. Does not sleep. */
  5229. static void __lockdep_reset_lock(struct pending_free *pf,
  5230. struct lockdep_map *lock)
  5231. {
  5232. struct lock_class *class;
  5233. int j;
  5234. /*
  5235. * Remove all classes this lock might have:
  5236. */
  5237. for (j = 0; j < MAX_LOCKDEP_SUBCLASSES; j++) {
  5238. /*
  5239. * If the class exists we look it up and zap it:
  5240. */
  5241. class = look_up_lock_class(lock, j);
  5242. if (class)
  5243. zap_class(pf, class);
  5244. }
  5245. /*
  5246. * Debug check: in the end all mapped classes should
  5247. * be gone.
  5248. */
  5249. if (WARN_ON_ONCE(lock_class_cache_is_registered(lock)))
  5250. debug_locks_off();
  5251. }
  5252. /*
  5253. * Remove all information lockdep has about a lock if debug_locks == 1. Free
  5254. * released data structures from RCU context.
  5255. */
  5256. static void lockdep_reset_lock_reg(struct lockdep_map *lock)
  5257. {
  5258. struct pending_free *pf;
  5259. unsigned long flags;
  5260. int locked;
  5261. raw_local_irq_save(flags);
  5262. locked = graph_lock();
  5263. if (!locked)
  5264. goto out_irq;
  5265. pf = get_pending_free();
  5266. __lockdep_reset_lock(pf, lock);
  5267. call_rcu_zapped(pf);
  5268. graph_unlock();
  5269. out_irq:
  5270. raw_local_irq_restore(flags);
  5271. }
  5272. /*
  5273. * Reset a lock. Does not sleep. Ignores debug_locks. Must only be used by the
  5274. * lockdep selftests.
  5275. */
  5276. static void lockdep_reset_lock_imm(struct lockdep_map *lock)
  5277. {
  5278. struct pending_free *pf = delayed_free.pf;
  5279. unsigned long flags;
  5280. raw_local_irq_save(flags);
  5281. lockdep_lock();
  5282. __lockdep_reset_lock(pf, lock);
  5283. __free_zapped_classes(pf);
  5284. lockdep_unlock();
  5285. raw_local_irq_restore(flags);
  5286. }
  5287. void lockdep_reset_lock(struct lockdep_map *lock)
  5288. {
  5289. init_data_structures_once();
  5290. if (inside_selftest())
  5291. lockdep_reset_lock_imm(lock);
  5292. else
  5293. lockdep_reset_lock_reg(lock);
  5294. }
  5295. /*
  5296. * Unregister a dynamically allocated key.
  5297. *
  5298. * Unlike lockdep_register_key(), a search is always done to find a matching
  5299. * key irrespective of debug_locks to avoid potential invalid access to freed
  5300. * memory in lock_class entry.
  5301. */
  5302. void lockdep_unregister_key(struct lock_class_key *key)
  5303. {
  5304. struct hlist_head *hash_head = keyhashentry(key);
  5305. struct lock_class_key *k;
  5306. struct pending_free *pf;
  5307. unsigned long flags;
  5308. bool found = false;
  5309. might_sleep();
  5310. if (WARN_ON_ONCE(static_obj(key)))
  5311. return;
  5312. raw_local_irq_save(flags);
  5313. lockdep_lock();
  5314. hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
  5315. if (k == key) {
  5316. hlist_del_rcu(&k->hash_entry);
  5317. found = true;
  5318. break;
  5319. }
  5320. }
  5321. WARN_ON_ONCE(!found && debug_locks);
  5322. if (found) {
  5323. pf = get_pending_free();
  5324. __lockdep_free_key_range(pf, key, 1);
  5325. call_rcu_zapped(pf);
  5326. }
  5327. lockdep_unlock();
  5328. raw_local_irq_restore(flags);
  5329. /* Wait until is_dynamic_key() has finished accessing k->hash_entry. */
  5330. synchronize_rcu();
  5331. }
  5332. EXPORT_SYMBOL_GPL(lockdep_unregister_key);
  5333. void __init lockdep_init(void)
  5334. {
  5335. printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");
  5336. printk("... MAX_LOCKDEP_SUBCLASSES: %lu\n", MAX_LOCKDEP_SUBCLASSES);
  5337. printk("... MAX_LOCK_DEPTH: %lu\n", MAX_LOCK_DEPTH);
  5338. printk("... MAX_LOCKDEP_KEYS: %lu\n", MAX_LOCKDEP_KEYS);
  5339. printk("... CLASSHASH_SIZE: %lu\n", CLASSHASH_SIZE);
  5340. printk("... MAX_LOCKDEP_ENTRIES: %lu\n", MAX_LOCKDEP_ENTRIES);
  5341. printk("... MAX_LOCKDEP_CHAINS: %lu\n", MAX_LOCKDEP_CHAINS);
  5342. printk("... CHAINHASH_SIZE: %lu\n", CHAINHASH_SIZE);
  5343. printk(" memory used by lock dependency info: %zu kB\n",
  5344. (sizeof(lock_classes) +
  5345. sizeof(lock_classes_in_use) +
  5346. sizeof(classhash_table) +
  5347. sizeof(list_entries) +
  5348. sizeof(list_entries_in_use) +
  5349. sizeof(chainhash_table) +
  5350. sizeof(delayed_free)
  5351. #ifdef CONFIG_PROVE_LOCKING
  5352. + sizeof(lock_cq)
  5353. + sizeof(lock_chains)
  5354. + sizeof(lock_chains_in_use)
  5355. + sizeof(chain_hlocks)
  5356. #endif
  5357. ) / 1024
  5358. );
  5359. #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
  5360. printk(" memory used for stack traces: %zu kB\n",
  5361. (sizeof(stack_trace) + sizeof(stack_trace_hash)) / 1024
  5362. );
  5363. #endif
  5364. printk(" per task-struct memory footprint: %zu bytes\n",
  5365. sizeof(((struct task_struct *)NULL)->held_locks));
  5366. }
  5367. static void
  5368. print_freed_lock_bug(struct task_struct *curr, const void *mem_from,
  5369. const void *mem_to, struct held_lock *hlock)
  5370. {
  5371. if (!debug_locks_off())
  5372. return;
  5373. if (debug_locks_silent)
  5374. return;
  5375. pr_warn("\n");
  5376. pr_warn("=========================\n");
  5377. pr_warn("WARNING: held lock freed!\n");
  5378. print_kernel_ident();
  5379. pr_warn("-------------------------\n");
  5380. pr_warn("%s/%d is freeing memory %px-%px, with a lock still held there!\n",
  5381. curr->comm, task_pid_nr(curr), mem_from, mem_to-1);
  5382. print_lock(hlock);
  5383. lockdep_print_held_locks(curr);
  5384. pr_warn("\nstack backtrace:\n");
  5385. dump_stack();
  5386. }
  5387. static inline int not_in_range(const void* mem_from, unsigned long mem_len,
  5388. const void* lock_from, unsigned long lock_len)
  5389. {
  5390. return lock_from + lock_len <= mem_from ||
  5391. mem_from + mem_len <= lock_from;
  5392. }
  5393. /*
  5394. * Called when kernel memory is freed (or unmapped), or if a lock
  5395. * is destroyed or reinitialized - this code checks whether there is
  5396. * any held lock in the memory range of <from> to <to>:
  5397. */
  5398. void debug_check_no_locks_freed(const void *mem_from, unsigned long mem_len)
  5399. {
  5400. struct task_struct *curr = current;
  5401. struct held_lock *hlock;
  5402. unsigned long flags;
  5403. int i;
  5404. if (unlikely(!debug_locks))
  5405. return;
  5406. raw_local_irq_save(flags);
  5407. for (i = 0; i < curr->lockdep_depth; i++) {
  5408. hlock = curr->held_locks + i;
  5409. if (not_in_range(mem_from, mem_len, hlock->instance,
  5410. sizeof(*hlock->instance)))
  5411. continue;
  5412. print_freed_lock_bug(curr, mem_from, mem_from + mem_len, hlock);
  5413. break;
  5414. }
  5415. raw_local_irq_restore(flags);
  5416. }
  5417. EXPORT_SYMBOL_GPL(debug_check_no_locks_freed);
  5418. static void print_held_locks_bug(void)
  5419. {
  5420. if (!debug_locks_off())
  5421. return;
  5422. if (debug_locks_silent)
  5423. return;
  5424. pr_warn("\n");
  5425. pr_warn("====================================\n");
  5426. pr_warn("WARNING: %s/%d still has locks held!\n",
  5427. current->comm, task_pid_nr(current));
  5428. print_kernel_ident();
  5429. pr_warn("------------------------------------\n");
  5430. lockdep_print_held_locks(current);
  5431. pr_warn("\nstack backtrace:\n");
  5432. dump_stack();
  5433. }
  5434. void debug_check_no_locks_held(void)
  5435. {
  5436. if (unlikely(current->lockdep_depth > 0))
  5437. print_held_locks_bug();
  5438. }
  5439. EXPORT_SYMBOL_GPL(debug_check_no_locks_held);
  5440. #ifdef __KERNEL__
  5441. void debug_show_all_locks(void)
  5442. {
  5443. struct task_struct *g, *p;
  5444. if (unlikely(!debug_locks)) {
  5445. pr_warn("INFO: lockdep is turned off.\n");
  5446. return;
  5447. }
  5448. pr_warn("\nShowing all locks held in the system:\n");
  5449. rcu_read_lock();
  5450. for_each_process_thread(g, p) {
  5451. if (!p->lockdep_depth)
  5452. continue;
  5453. lockdep_print_held_locks(p);
  5454. touch_nmi_watchdog();
  5455. touch_all_softlockup_watchdogs();
  5456. }
  5457. rcu_read_unlock();
  5458. pr_warn("\n");
  5459. pr_warn("=============================================\n\n");
  5460. }
  5461. EXPORT_SYMBOL_GPL(debug_show_all_locks);
  5462. #endif
  5463. /*
  5464. * Careful: only use this function if you are sure that
  5465. * the task cannot run in parallel!
  5466. */
  5467. void debug_show_held_locks(struct task_struct *task)
  5468. {
  5469. if (unlikely(!debug_locks)) {
  5470. printk("INFO: lockdep is turned off.\n");
  5471. return;
  5472. }
  5473. lockdep_print_held_locks(task);
  5474. }
  5475. EXPORT_SYMBOL_GPL(debug_show_held_locks);
  5476. asmlinkage __visible void lockdep_sys_exit(void)
  5477. {
  5478. struct task_struct *curr = current;
  5479. if (unlikely(curr->lockdep_depth)) {
  5480. if (!debug_locks_off())
  5481. return;
  5482. pr_warn("\n");
  5483. pr_warn("================================================\n");
  5484. pr_warn("WARNING: lock held when returning to user space!\n");
  5485. print_kernel_ident();
  5486. pr_warn("------------------------------------------------\n");
  5487. pr_warn("%s/%d is leaving the kernel with locks still held!\n",
  5488. curr->comm, curr->pid);
  5489. lockdep_print_held_locks(curr);
  5490. }
  5491. /*
  5492. * The lock history for each syscall should be independent. So wipe the
  5493. * slate clean on return to userspace.
  5494. */
  5495. lockdep_invariant_state(false);
  5496. }
  5497. void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
  5498. {
  5499. struct task_struct *curr = current;
  5500. /* Note: the following can be executed concurrently, so be careful. */
  5501. pr_warn("\n");
  5502. pr_warn("=============================\n");
  5503. pr_warn("WARNING: suspicious RCU usage\n");
  5504. print_kernel_ident();
  5505. pr_warn("-----------------------------\n");
  5506. pr_warn("%s:%d %s!\n", file, line, s);
  5507. pr_warn("\nother info that might help us debug this:\n\n");
  5508. pr_warn("\n%srcu_scheduler_active = %d, debug_locks = %d\n",
  5509. !rcu_lockdep_current_cpu_online()
  5510. ? "RCU used illegally from offline CPU!\n"
  5511. : "",
  5512. rcu_scheduler_active, debug_locks);
  5513. /*
  5514. * If a CPU is in the RCU-free window in idle (ie: in the section
  5515. * between rcu_idle_enter() and rcu_idle_exit(), then RCU
  5516. * considers that CPU to be in an "extended quiescent state",
  5517. * which means that RCU will be completely ignoring that CPU.
  5518. * Therefore, rcu_read_lock() and friends have absolutely no
  5519. * effect on a CPU running in that state. In other words, even if
  5520. * such an RCU-idle CPU has called rcu_read_lock(), RCU might well
  5521. * delete data structures out from under it. RCU really has no
  5522. * choice here: we need to keep an RCU-free window in idle where
  5523. * the CPU may possibly enter into low power mode. This way we can
  5524. * notice an extended quiescent state to other CPUs that started a grace
  5525. * period. Otherwise we would delay any grace period as long as we run
  5526. * in the idle task.
  5527. *
  5528. * So complain bitterly if someone does call rcu_read_lock(),
  5529. * rcu_read_lock_bh() and so on from extended quiescent states.
  5530. */
  5531. if (!rcu_is_watching())
  5532. pr_warn("RCU used illegally from extended quiescent state!\n");
  5533. lockdep_print_held_locks(curr);
  5534. pr_warn("\nstack backtrace:\n");
  5535. dump_stack();
  5536. }
  5537. EXPORT_SYMBOL_GPL(lockdep_rcu_suspicious);