extents.c 166 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572457345744575457645774578457945804581458245834584458545864587458845894590459145924593459445954596459745984599460046014602460346044605460646074608460946104611461246134614461546164617461846194620462146224623462446254626462746284629463046314632463346344635463646374638463946404641464246434644464546464647464846494650465146524653465446554656465746584659466046614662466346644665466646674668466946704671467246734674467546764677467846794680468146824683468446854686468746884689469046914692469346944695469646974698469947004701470247034704470547064707470847094710471147124713471447154716471747184719472047214722472347244725472647274728472947304731473247334734473547364737473847394740474147424743474447454746474747484749475047514752475347544755475647574758475947604761476247634764476547664767476847694770477147724773477447754776477747784779478047814782478347844785478647874788478947904791479247934794479547964797479847994800480148024803480448054806480748084809481048114812481348144815481648174818481948204821482248234824482548264827482848294830483148324833483448354836483748384839484048414842484348444845484648474848484948504851485248534854485548564857485848594860486148624863486448654866486748684869487048714872487348744875487648774878487948804881488248834884488548864887488848894890489148924893489448954896489748984899490049014902490349044905490649074908490949104911491249134914491549164917491849194920492149224923492449254926492749284929493049314932493349344935493649374938493949404941494249434944494549464947494849494950495149524953495449554956495749584959496049614962496349644965496649674968496949704971497249734974497549764977497849794980498149824983498449854986498749884989499049914992499349944995499649974998499950005001500250035004500550065007500850095010501150125013501450155016501750185019502050215022502350245025502650275028502950305031503250335034503550365037503850395040504150425043504450455046504750485049505050515052505350545055505650575058505950605061506250635064506550665067506850695070507150725073507450755076507750785079508050815082508350845085508650875088508950905091509250935094509550965097509850995100510151025103510451055106510751085109511051115112511351145115511651175118511951205121512251235124512551265127512851295130513151325133513451355136513751385139514051415142514351445145514651475148514951505151515251535154515551565157515851595160516151625163516451655166516751685169517051715172517351745175517651775178517951805181518251835184518551865187518851895190519151925193519451955196519751985199520052015202520352045205520652075208520952105211521252135214521552165217521852195220522152225223522452255226522752285229523052315232523352345235523652375238523952405241524252435244524552465247524852495250525152525253525452555256525752585259526052615262526352645265526652675268526952705271527252735274527552765277527852795280528152825283528452855286528752885289529052915292529352945295529652975298529953005301530253035304530553065307530853095310531153125313531453155316531753185319532053215322532353245325532653275328532953305331533253335334533553365337533853395340534153425343534453455346534753485349535053515352535353545355535653575358535953605361536253635364536553665367536853695370537153725373537453755376537753785379538053815382538353845385538653875388538953905391539253935394539553965397539853995400540154025403540454055406540754085409541054115412541354145415541654175418541954205421542254235424542554265427542854295430543154325433543454355436543754385439544054415442544354445445544654475448544954505451545254535454545554565457545854595460546154625463546454655466546754685469547054715472547354745475547654775478547954805481548254835484548554865487548854895490549154925493549454955496549754985499550055015502550355045505550655075508550955105511551255135514551555165517551855195520552155225523552455255526552755285529553055315532553355345535553655375538553955405541554255435544554555465547554855495550555155525553555455555556555755585559556055615562556355645565556655675568556955705571557255735574557555765577557855795580558155825583558455855586558755885589559055915592559355945595559655975598559956005601560256035604560556065607560856095610561156125613561456155616561756185619562056215622562356245625562656275628562956305631563256335634563556365637563856395640564156425643564456455646564756485649565056515652565356545655565656575658565956605661566256635664566556665667566856695670567156725673567456755676567756785679568056815682568356845685568656875688568956905691569256935694569556965697569856995700570157025703570457055706570757085709571057115712571357145715571657175718571957205721572257235724572557265727572857295730573157325733573457355736573757385739574057415742574357445745574657475748574957505751575257535754575557565757575857595760576157625763576457655766576757685769577057715772577357745775577657775778577957805781578257835784578557865787578857895790579157925793579457955796579757985799580058015802580358045805580658075808580958105811581258135814581558165817581858195820582158225823582458255826582758285829583058315832583358345835583658375838583958405841584258435844584558465847584858495850585158525853585458555856585758585859586058615862586358645865586658675868586958705871587258735874587558765877587858795880588158825883588458855886588758885889589058915892589358945895589658975898589959005901590259035904590559065907590859095910591159125913591459155916591759185919592059215922592359245925592659275928592959305931593259335934593559365937593859395940594159425943594459455946594759485949595059515952595359545955595659575958595959605961596259635964596559665967596859695970597159725973597459755976597759785979598059815982598359845985598659875988598959905991599259935994599559965997599859996000600160026003600460056006600760086009601060116012601360146015601660176018601960206021602260236024602560266027602860296030603160326033603460356036603760386039604060416042604360446045604660476048604960506051605260536054605560566057605860596060606160626063606460656066606760686069607060716072607360746075607660776078607960806081608260836084608560866087608860896090609160926093609460956096609760986099610061016102610361046105610661076108610961106111611261136114611561166117611861196120612161226123
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
  4. * Written by Alex Tomas <alex@clusterfs.com>
  5. *
  6. * Architecture independence:
  7. * Copyright (c) 2005, Bull S.A.
  8. * Written by Pierre Peiffer <pierre.peiffer@bull.net>
  9. */
  10. /*
  11. * Extents support for EXT4
  12. *
  13. * TODO:
  14. * - ext4*_error() should be used in some situations
  15. * - analyze all BUG()/BUG_ON(), use -EIO where appropriate
  16. * - smart tree reduction
  17. */
  18. #include <linux/fs.h>
  19. #include <linux/time.h>
  20. #include <linux/jbd2.h>
  21. #include <linux/highuid.h>
  22. #include <linux/pagemap.h>
  23. #include <linux/quotaops.h>
  24. #include <linux/string.h>
  25. #include <linux/slab.h>
  26. #include <linux/uaccess.h>
  27. #include <linux/fiemap.h>
  28. #include <linux/backing-dev.h>
  29. #include <linux/iomap.h>
  30. #include "ext4_jbd2.h"
  31. #include "ext4_extents.h"
  32. #include "xattr.h"
  33. #include <trace/events/ext4.h>
  34. /*
  35. * used by extent splitting.
  36. */
  37. #define EXT4_EXT_MAY_ZEROOUT 0x1 /* safe to zeroout if split fails \
  38. due to ENOSPC */
  39. #define EXT4_EXT_MARK_UNWRIT1 0x2 /* mark first half unwritten */
  40. #define EXT4_EXT_MARK_UNWRIT2 0x4 /* mark second half unwritten */
  41. #define EXT4_EXT_DATA_VALID1 0x8 /* first half contains valid data */
  42. #define EXT4_EXT_DATA_VALID2 0x10 /* second half contains valid data */
  43. static __le32 ext4_extent_block_csum(struct inode *inode,
  44. struct ext4_extent_header *eh)
  45. {
  46. struct ext4_inode_info *ei = EXT4_I(inode);
  47. struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  48. __u32 csum;
  49. csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)eh,
  50. EXT4_EXTENT_TAIL_OFFSET(eh));
  51. return cpu_to_le32(csum);
  52. }
  53. static int ext4_extent_block_csum_verify(struct inode *inode,
  54. struct ext4_extent_header *eh)
  55. {
  56. struct ext4_extent_tail *et;
  57. if (!ext4_has_metadata_csum(inode->i_sb))
  58. return 1;
  59. et = find_ext4_extent_tail(eh);
  60. if (et->et_checksum != ext4_extent_block_csum(inode, eh))
  61. return 0;
  62. return 1;
  63. }
  64. static void ext4_extent_block_csum_set(struct inode *inode,
  65. struct ext4_extent_header *eh)
  66. {
  67. struct ext4_extent_tail *et;
  68. if (!ext4_has_metadata_csum(inode->i_sb))
  69. return;
  70. et = find_ext4_extent_tail(eh);
  71. et->et_checksum = ext4_extent_block_csum(inode, eh);
  72. }
  73. static int ext4_split_extent_at(handle_t *handle,
  74. struct inode *inode,
  75. struct ext4_ext_path **ppath,
  76. ext4_lblk_t split,
  77. int split_flag,
  78. int flags);
  79. static int ext4_ext_trunc_restart_fn(struct inode *inode, int *dropped)
  80. {
  81. /*
  82. * Drop i_data_sem to avoid deadlock with ext4_map_blocks. At this
  83. * moment, get_block can be called only for blocks inside i_size since
  84. * page cache has been already dropped and writes are blocked by
  85. * i_mutex. So we can safely drop the i_data_sem here.
  86. */
  87. BUG_ON(EXT4_JOURNAL(inode) == NULL);
  88. ext4_discard_preallocations(inode, 0);
  89. up_write(&EXT4_I(inode)->i_data_sem);
  90. *dropped = 1;
  91. return 0;
  92. }
  93. /*
  94. * Make sure 'handle' has at least 'check_cred' credits. If not, restart
  95. * transaction with 'restart_cred' credits. The function drops i_data_sem
  96. * when restarting transaction and gets it after transaction is restarted.
  97. *
  98. * The function returns 0 on success, 1 if transaction had to be restarted,
  99. * and < 0 in case of fatal error.
  100. */
  101. int ext4_datasem_ensure_credits(handle_t *handle, struct inode *inode,
  102. int check_cred, int restart_cred,
  103. int revoke_cred)
  104. {
  105. int ret;
  106. int dropped = 0;
  107. ret = ext4_journal_ensure_credits_fn(handle, check_cred, restart_cred,
  108. revoke_cred, ext4_ext_trunc_restart_fn(inode, &dropped));
  109. if (dropped)
  110. down_write(&EXT4_I(inode)->i_data_sem);
  111. return ret;
  112. }
  113. /*
  114. * could return:
  115. * - EROFS
  116. * - ENOMEM
  117. */
  118. static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
  119. struct ext4_ext_path *path)
  120. {
  121. int err = 0;
  122. if (path->p_bh) {
  123. /* path points to block */
  124. BUFFER_TRACE(path->p_bh, "get_write_access");
  125. err = ext4_journal_get_write_access(handle, path->p_bh);
  126. /*
  127. * The extent buffer's verified bit will be set again in
  128. * __ext4_ext_dirty(). We could leave an inconsistent
  129. * buffer if the extents updating procudure break off du
  130. * to some error happens, force to check it again.
  131. */
  132. if (!err)
  133. clear_buffer_verified(path->p_bh);
  134. }
  135. /* path points to leaf/index in inode body */
  136. /* we use in-core data, no need to protect them */
  137. return err;
  138. }
  139. /*
  140. * could return:
  141. * - EROFS
  142. * - ENOMEM
  143. * - EIO
  144. */
  145. static int __ext4_ext_dirty(const char *where, unsigned int line,
  146. handle_t *handle, struct inode *inode,
  147. struct ext4_ext_path *path)
  148. {
  149. int err;
  150. WARN_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
  151. if (path->p_bh) {
  152. ext4_extent_block_csum_set(inode, ext_block_hdr(path->p_bh));
  153. /* path points to block */
  154. err = __ext4_handle_dirty_metadata(where, line, handle,
  155. inode, path->p_bh);
  156. /* Extents updating done, re-set verified flag */
  157. if (!err)
  158. set_buffer_verified(path->p_bh);
  159. } else {
  160. /* path points to leaf/index in inode body */
  161. err = ext4_mark_inode_dirty(handle, inode);
  162. }
  163. return err;
  164. }
  165. #define ext4_ext_dirty(handle, inode, path) \
  166. __ext4_ext_dirty(__func__, __LINE__, (handle), (inode), (path))
  167. static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
  168. struct ext4_ext_path *path,
  169. ext4_lblk_t block)
  170. {
  171. if (path) {
  172. int depth = path->p_depth;
  173. struct ext4_extent *ex;
  174. /*
  175. * Try to predict block placement assuming that we are
  176. * filling in a file which will eventually be
  177. * non-sparse --- i.e., in the case of libbfd writing
  178. * an ELF object sections out-of-order but in a way
  179. * the eventually results in a contiguous object or
  180. * executable file, or some database extending a table
  181. * space file. However, this is actually somewhat
  182. * non-ideal if we are writing a sparse file such as
  183. * qemu or KVM writing a raw image file that is going
  184. * to stay fairly sparse, since it will end up
  185. * fragmenting the file system's free space. Maybe we
  186. * should have some hueristics or some way to allow
  187. * userspace to pass a hint to file system,
  188. * especially if the latter case turns out to be
  189. * common.
  190. */
  191. ex = path[depth].p_ext;
  192. if (ex) {
  193. ext4_fsblk_t ext_pblk = ext4_ext_pblock(ex);
  194. ext4_lblk_t ext_block = le32_to_cpu(ex->ee_block);
  195. if (block > ext_block)
  196. return ext_pblk + (block - ext_block);
  197. else
  198. return ext_pblk - (ext_block - block);
  199. }
  200. /* it looks like index is empty;
  201. * try to find starting block from index itself */
  202. if (path[depth].p_bh)
  203. return path[depth].p_bh->b_blocknr;
  204. }
  205. /* OK. use inode's group */
  206. return ext4_inode_to_goal_block(inode);
  207. }
  208. /*
  209. * Allocation for a meta data block
  210. */
  211. static ext4_fsblk_t
  212. ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
  213. struct ext4_ext_path *path,
  214. struct ext4_extent *ex, int *err, unsigned int flags)
  215. {
  216. ext4_fsblk_t goal, newblock;
  217. goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
  218. newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
  219. NULL, err);
  220. return newblock;
  221. }
  222. static inline int ext4_ext_space_block(struct inode *inode, int check)
  223. {
  224. int size;
  225. size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
  226. / sizeof(struct ext4_extent);
  227. #ifdef AGGRESSIVE_TEST
  228. if (!check && size > 6)
  229. size = 6;
  230. #endif
  231. return size;
  232. }
  233. static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
  234. {
  235. int size;
  236. size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
  237. / sizeof(struct ext4_extent_idx);
  238. #ifdef AGGRESSIVE_TEST
  239. if (!check && size > 5)
  240. size = 5;
  241. #endif
  242. return size;
  243. }
  244. static inline int ext4_ext_space_root(struct inode *inode, int check)
  245. {
  246. int size;
  247. size = sizeof(EXT4_I(inode)->i_data);
  248. size -= sizeof(struct ext4_extent_header);
  249. size /= sizeof(struct ext4_extent);
  250. #ifdef AGGRESSIVE_TEST
  251. if (!check && size > 3)
  252. size = 3;
  253. #endif
  254. return size;
  255. }
  256. static inline int ext4_ext_space_root_idx(struct inode *inode, int check)
  257. {
  258. int size;
  259. size = sizeof(EXT4_I(inode)->i_data);
  260. size -= sizeof(struct ext4_extent_header);
  261. size /= sizeof(struct ext4_extent_idx);
  262. #ifdef AGGRESSIVE_TEST
  263. if (!check && size > 4)
  264. size = 4;
  265. #endif
  266. return size;
  267. }
  268. static inline int
  269. ext4_force_split_extent_at(handle_t *handle, struct inode *inode,
  270. struct ext4_ext_path **ppath, ext4_lblk_t lblk,
  271. int nofail)
  272. {
  273. struct ext4_ext_path *path = *ppath;
  274. int unwritten = ext4_ext_is_unwritten(path[path->p_depth].p_ext);
  275. int flags = EXT4_EX_NOCACHE | EXT4_GET_BLOCKS_PRE_IO;
  276. if (nofail)
  277. flags |= EXT4_GET_BLOCKS_METADATA_NOFAIL | EXT4_EX_NOFAIL;
  278. return ext4_split_extent_at(handle, inode, ppath, lblk, unwritten ?
  279. EXT4_EXT_MARK_UNWRIT1|EXT4_EXT_MARK_UNWRIT2 : 0,
  280. flags);
  281. }
  282. static int
  283. ext4_ext_max_entries(struct inode *inode, int depth)
  284. {
  285. int max;
  286. if (depth == ext_depth(inode)) {
  287. if (depth == 0)
  288. max = ext4_ext_space_root(inode, 1);
  289. else
  290. max = ext4_ext_space_root_idx(inode, 1);
  291. } else {
  292. if (depth == 0)
  293. max = ext4_ext_space_block(inode, 1);
  294. else
  295. max = ext4_ext_space_block_idx(inode, 1);
  296. }
  297. return max;
  298. }
  299. static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
  300. {
  301. ext4_fsblk_t block = ext4_ext_pblock(ext);
  302. int len = ext4_ext_get_actual_len(ext);
  303. ext4_lblk_t lblock = le32_to_cpu(ext->ee_block);
  304. /*
  305. * We allow neither:
  306. * - zero length
  307. * - overflow/wrap-around
  308. */
  309. if (lblock + len <= lblock)
  310. return 0;
  311. return ext4_inode_block_valid(inode, block, len);
  312. }
  313. static int ext4_valid_extent_idx(struct inode *inode,
  314. struct ext4_extent_idx *ext_idx)
  315. {
  316. ext4_fsblk_t block = ext4_idx_pblock(ext_idx);
  317. return ext4_inode_block_valid(inode, block, 1);
  318. }
  319. static int ext4_valid_extent_entries(struct inode *inode,
  320. struct ext4_extent_header *eh,
  321. ext4_lblk_t lblk, ext4_fsblk_t *pblk,
  322. int depth)
  323. {
  324. unsigned short entries;
  325. ext4_lblk_t lblock = 0;
  326. ext4_lblk_t prev = 0;
  327. if (eh->eh_entries == 0)
  328. return 1;
  329. entries = le16_to_cpu(eh->eh_entries);
  330. if (depth == 0) {
  331. /* leaf entries */
  332. struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
  333. /*
  334. * The logical block in the first entry should equal to
  335. * the number in the index block.
  336. */
  337. if (depth != ext_depth(inode) &&
  338. lblk != le32_to_cpu(ext->ee_block))
  339. return 0;
  340. while (entries) {
  341. if (!ext4_valid_extent(inode, ext))
  342. return 0;
  343. /* Check for overlapping extents */
  344. lblock = le32_to_cpu(ext->ee_block);
  345. if ((lblock <= prev) && prev) {
  346. *pblk = ext4_ext_pblock(ext);
  347. return 0;
  348. }
  349. prev = lblock + ext4_ext_get_actual_len(ext) - 1;
  350. ext++;
  351. entries--;
  352. }
  353. } else {
  354. struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
  355. /*
  356. * The logical block in the first entry should equal to
  357. * the number in the parent index block.
  358. */
  359. if (depth != ext_depth(inode) &&
  360. lblk != le32_to_cpu(ext_idx->ei_block))
  361. return 0;
  362. while (entries) {
  363. if (!ext4_valid_extent_idx(inode, ext_idx))
  364. return 0;
  365. /* Check for overlapping index extents */
  366. lblock = le32_to_cpu(ext_idx->ei_block);
  367. if ((lblock <= prev) && prev) {
  368. *pblk = ext4_idx_pblock(ext_idx);
  369. return 0;
  370. }
  371. ext_idx++;
  372. entries--;
  373. prev = lblock;
  374. }
  375. }
  376. return 1;
  377. }
  378. static int __ext4_ext_check(const char *function, unsigned int line,
  379. struct inode *inode, struct ext4_extent_header *eh,
  380. int depth, ext4_fsblk_t pblk, ext4_lblk_t lblk)
  381. {
  382. const char *error_msg;
  383. int max = 0, err = -EFSCORRUPTED;
  384. if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
  385. error_msg = "invalid magic";
  386. goto corrupted;
  387. }
  388. if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
  389. error_msg = "unexpected eh_depth";
  390. goto corrupted;
  391. }
  392. if (unlikely(eh->eh_max == 0)) {
  393. error_msg = "invalid eh_max";
  394. goto corrupted;
  395. }
  396. max = ext4_ext_max_entries(inode, depth);
  397. if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
  398. error_msg = "too large eh_max";
  399. goto corrupted;
  400. }
  401. if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
  402. error_msg = "invalid eh_entries";
  403. goto corrupted;
  404. }
  405. if (!ext4_valid_extent_entries(inode, eh, lblk, &pblk, depth)) {
  406. error_msg = "invalid extent entries";
  407. goto corrupted;
  408. }
  409. if (unlikely(depth > 32)) {
  410. error_msg = "too large eh_depth";
  411. goto corrupted;
  412. }
  413. /* Verify checksum on non-root extent tree nodes */
  414. if (ext_depth(inode) != depth &&
  415. !ext4_extent_block_csum_verify(inode, eh)) {
  416. error_msg = "extent tree corrupted";
  417. err = -EFSBADCRC;
  418. goto corrupted;
  419. }
  420. return 0;
  421. corrupted:
  422. ext4_error_inode_err(inode, function, line, 0, -err,
  423. "pblk %llu bad header/extent: %s - magic %x, "
  424. "entries %u, max %u(%u), depth %u(%u)",
  425. (unsigned long long) pblk, error_msg,
  426. le16_to_cpu(eh->eh_magic),
  427. le16_to_cpu(eh->eh_entries),
  428. le16_to_cpu(eh->eh_max),
  429. max, le16_to_cpu(eh->eh_depth), depth);
  430. return err;
  431. }
  432. #define ext4_ext_check(inode, eh, depth, pblk) \
  433. __ext4_ext_check(__func__, __LINE__, (inode), (eh), (depth), (pblk), 0)
  434. int ext4_ext_check_inode(struct inode *inode)
  435. {
  436. return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode), 0);
  437. }
  438. static void ext4_cache_extents(struct inode *inode,
  439. struct ext4_extent_header *eh)
  440. {
  441. struct ext4_extent *ex = EXT_FIRST_EXTENT(eh);
  442. ext4_lblk_t prev = 0;
  443. int i;
  444. for (i = le16_to_cpu(eh->eh_entries); i > 0; i--, ex++) {
  445. unsigned int status = EXTENT_STATUS_WRITTEN;
  446. ext4_lblk_t lblk = le32_to_cpu(ex->ee_block);
  447. int len = ext4_ext_get_actual_len(ex);
  448. if (prev && (prev != lblk))
  449. ext4_es_cache_extent(inode, prev, lblk - prev, ~0,
  450. EXTENT_STATUS_HOLE);
  451. if (ext4_ext_is_unwritten(ex))
  452. status = EXTENT_STATUS_UNWRITTEN;
  453. ext4_es_cache_extent(inode, lblk, len,
  454. ext4_ext_pblock(ex), status);
  455. prev = lblk + len;
  456. }
  457. }
  458. static struct buffer_head *
  459. __read_extent_tree_block(const char *function, unsigned int line,
  460. struct inode *inode, struct ext4_extent_idx *idx,
  461. int depth, int flags)
  462. {
  463. struct buffer_head *bh;
  464. int err;
  465. gfp_t gfp_flags = __GFP_MOVABLE | GFP_NOFS;
  466. ext4_fsblk_t pblk;
  467. if (flags & EXT4_EX_NOFAIL)
  468. gfp_flags |= __GFP_NOFAIL;
  469. pblk = ext4_idx_pblock(idx);
  470. bh = sb_getblk_gfp(inode->i_sb, pblk, gfp_flags);
  471. if (unlikely(!bh))
  472. return ERR_PTR(-ENOMEM);
  473. if (!bh_uptodate_or_lock(bh)) {
  474. trace_ext4_ext_load_extent(inode, pblk, _RET_IP_);
  475. err = ext4_read_bh(bh, 0, NULL);
  476. if (err < 0)
  477. goto errout;
  478. }
  479. if (buffer_verified(bh) && !(flags & EXT4_EX_FORCE_CACHE))
  480. return bh;
  481. err = __ext4_ext_check(function, line, inode, ext_block_hdr(bh),
  482. depth, pblk, le32_to_cpu(idx->ei_block));
  483. if (err)
  484. goto errout;
  485. set_buffer_verified(bh);
  486. /*
  487. * If this is a leaf block, cache all of its entries
  488. */
  489. if (!(flags & EXT4_EX_NOCACHE) && depth == 0) {
  490. struct ext4_extent_header *eh = ext_block_hdr(bh);
  491. ext4_cache_extents(inode, eh);
  492. }
  493. return bh;
  494. errout:
  495. put_bh(bh);
  496. return ERR_PTR(err);
  497. }
  498. #define read_extent_tree_block(inode, idx, depth, flags) \
  499. __read_extent_tree_block(__func__, __LINE__, (inode), (idx), \
  500. (depth), (flags))
  501. /*
  502. * This function is called to cache a file's extent information in the
  503. * extent status tree
  504. */
  505. int ext4_ext_precache(struct inode *inode)
  506. {
  507. struct ext4_inode_info *ei = EXT4_I(inode);
  508. struct ext4_ext_path *path = NULL;
  509. struct buffer_head *bh;
  510. int i = 0, depth, ret = 0;
  511. if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
  512. return 0; /* not an extent-mapped inode */
  513. down_read(&ei->i_data_sem);
  514. depth = ext_depth(inode);
  515. /* Don't cache anything if there are no external extent blocks */
  516. if (!depth) {
  517. up_read(&ei->i_data_sem);
  518. return ret;
  519. }
  520. path = kcalloc(depth + 1, sizeof(struct ext4_ext_path),
  521. GFP_NOFS);
  522. if (path == NULL) {
  523. up_read(&ei->i_data_sem);
  524. return -ENOMEM;
  525. }
  526. path[0].p_hdr = ext_inode_hdr(inode);
  527. ret = ext4_ext_check(inode, path[0].p_hdr, depth, 0);
  528. if (ret)
  529. goto out;
  530. path[0].p_idx = EXT_FIRST_INDEX(path[0].p_hdr);
  531. while (i >= 0) {
  532. /*
  533. * If this is a leaf block or we've reached the end of
  534. * the index block, go up
  535. */
  536. if ((i == depth) ||
  537. path[i].p_idx > EXT_LAST_INDEX(path[i].p_hdr)) {
  538. brelse(path[i].p_bh);
  539. path[i].p_bh = NULL;
  540. i--;
  541. continue;
  542. }
  543. bh = read_extent_tree_block(inode, path[i].p_idx++,
  544. depth - i - 1,
  545. EXT4_EX_FORCE_CACHE);
  546. if (IS_ERR(bh)) {
  547. ret = PTR_ERR(bh);
  548. break;
  549. }
  550. i++;
  551. path[i].p_bh = bh;
  552. path[i].p_hdr = ext_block_hdr(bh);
  553. path[i].p_idx = EXT_FIRST_INDEX(path[i].p_hdr);
  554. }
  555. ext4_set_inode_state(inode, EXT4_STATE_EXT_PRECACHED);
  556. out:
  557. up_read(&ei->i_data_sem);
  558. ext4_ext_drop_refs(path);
  559. kfree(path);
  560. return ret;
  561. }
  562. #ifdef EXT_DEBUG
  563. static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
  564. {
  565. int k, l = path->p_depth;
  566. ext_debug(inode, "path:");
  567. for (k = 0; k <= l; k++, path++) {
  568. if (path->p_idx) {
  569. ext_debug(inode, " %d->%llu",
  570. le32_to_cpu(path->p_idx->ei_block),
  571. ext4_idx_pblock(path->p_idx));
  572. } else if (path->p_ext) {
  573. ext_debug(inode, " %d:[%d]%d:%llu ",
  574. le32_to_cpu(path->p_ext->ee_block),
  575. ext4_ext_is_unwritten(path->p_ext),
  576. ext4_ext_get_actual_len(path->p_ext),
  577. ext4_ext_pblock(path->p_ext));
  578. } else
  579. ext_debug(inode, " []");
  580. }
  581. ext_debug(inode, "\n");
  582. }
  583. static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
  584. {
  585. int depth = ext_depth(inode);
  586. struct ext4_extent_header *eh;
  587. struct ext4_extent *ex;
  588. int i;
  589. if (!path)
  590. return;
  591. eh = path[depth].p_hdr;
  592. ex = EXT_FIRST_EXTENT(eh);
  593. ext_debug(inode, "Displaying leaf extents\n");
  594. for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
  595. ext_debug(inode, "%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
  596. ext4_ext_is_unwritten(ex),
  597. ext4_ext_get_actual_len(ex), ext4_ext_pblock(ex));
  598. }
  599. ext_debug(inode, "\n");
  600. }
  601. static void ext4_ext_show_move(struct inode *inode, struct ext4_ext_path *path,
  602. ext4_fsblk_t newblock, int level)
  603. {
  604. int depth = ext_depth(inode);
  605. struct ext4_extent *ex;
  606. if (depth != level) {
  607. struct ext4_extent_idx *idx;
  608. idx = path[level].p_idx;
  609. while (idx <= EXT_MAX_INDEX(path[level].p_hdr)) {
  610. ext_debug(inode, "%d: move %d:%llu in new index %llu\n",
  611. level, le32_to_cpu(idx->ei_block),
  612. ext4_idx_pblock(idx), newblock);
  613. idx++;
  614. }
  615. return;
  616. }
  617. ex = path[depth].p_ext;
  618. while (ex <= EXT_MAX_EXTENT(path[depth].p_hdr)) {
  619. ext_debug(inode, "move %d:%llu:[%d]%d in new leaf %llu\n",
  620. le32_to_cpu(ex->ee_block),
  621. ext4_ext_pblock(ex),
  622. ext4_ext_is_unwritten(ex),
  623. ext4_ext_get_actual_len(ex),
  624. newblock);
  625. ex++;
  626. }
  627. }
  628. #else
  629. #define ext4_ext_show_path(inode, path)
  630. #define ext4_ext_show_leaf(inode, path)
  631. #define ext4_ext_show_move(inode, path, newblock, level)
  632. #endif
  633. void ext4_ext_drop_refs(struct ext4_ext_path *path)
  634. {
  635. int depth, i;
  636. if (!path)
  637. return;
  638. depth = path->p_depth;
  639. for (i = 0; i <= depth; i++, path++) {
  640. brelse(path->p_bh);
  641. path->p_bh = NULL;
  642. }
  643. }
  644. /*
  645. * ext4_ext_binsearch_idx:
  646. * binary search for the closest index of the given block
  647. * the header must be checked before calling this
  648. */
  649. static void
  650. ext4_ext_binsearch_idx(struct inode *inode,
  651. struct ext4_ext_path *path, ext4_lblk_t block)
  652. {
  653. struct ext4_extent_header *eh = path->p_hdr;
  654. struct ext4_extent_idx *r, *l, *m;
  655. ext_debug(inode, "binsearch for %u(idx): ", block);
  656. l = EXT_FIRST_INDEX(eh) + 1;
  657. r = EXT_LAST_INDEX(eh);
  658. while (l <= r) {
  659. m = l + (r - l) / 2;
  660. if (block < le32_to_cpu(m->ei_block))
  661. r = m - 1;
  662. else
  663. l = m + 1;
  664. ext_debug(inode, "%p(%u):%p(%u):%p(%u) ", l,
  665. le32_to_cpu(l->ei_block), m, le32_to_cpu(m->ei_block),
  666. r, le32_to_cpu(r->ei_block));
  667. }
  668. path->p_idx = l - 1;
  669. ext_debug(inode, " -> %u->%lld ", le32_to_cpu(path->p_idx->ei_block),
  670. ext4_idx_pblock(path->p_idx));
  671. #ifdef CHECK_BINSEARCH
  672. {
  673. struct ext4_extent_idx *chix, *ix;
  674. int k;
  675. chix = ix = EXT_FIRST_INDEX(eh);
  676. for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
  677. if (k != 0 && le32_to_cpu(ix->ei_block) <=
  678. le32_to_cpu(ix[-1].ei_block)) {
  679. printk(KERN_DEBUG "k=%d, ix=0x%p, "
  680. "first=0x%p\n", k,
  681. ix, EXT_FIRST_INDEX(eh));
  682. printk(KERN_DEBUG "%u <= %u\n",
  683. le32_to_cpu(ix->ei_block),
  684. le32_to_cpu(ix[-1].ei_block));
  685. }
  686. BUG_ON(k && le32_to_cpu(ix->ei_block)
  687. <= le32_to_cpu(ix[-1].ei_block));
  688. if (block < le32_to_cpu(ix->ei_block))
  689. break;
  690. chix = ix;
  691. }
  692. BUG_ON(chix != path->p_idx);
  693. }
  694. #endif
  695. }
  696. /*
  697. * ext4_ext_binsearch:
  698. * binary search for closest extent of the given block
  699. * the header must be checked before calling this
  700. */
  701. static void
  702. ext4_ext_binsearch(struct inode *inode,
  703. struct ext4_ext_path *path, ext4_lblk_t block)
  704. {
  705. struct ext4_extent_header *eh = path->p_hdr;
  706. struct ext4_extent *r, *l, *m;
  707. if (eh->eh_entries == 0) {
  708. /*
  709. * this leaf is empty:
  710. * we get such a leaf in split/add case
  711. */
  712. return;
  713. }
  714. ext_debug(inode, "binsearch for %u: ", block);
  715. l = EXT_FIRST_EXTENT(eh) + 1;
  716. r = EXT_LAST_EXTENT(eh);
  717. while (l <= r) {
  718. m = l + (r - l) / 2;
  719. if (block < le32_to_cpu(m->ee_block))
  720. r = m - 1;
  721. else
  722. l = m + 1;
  723. ext_debug(inode, "%p(%u):%p(%u):%p(%u) ", l,
  724. le32_to_cpu(l->ee_block), m, le32_to_cpu(m->ee_block),
  725. r, le32_to_cpu(r->ee_block));
  726. }
  727. path->p_ext = l - 1;
  728. ext_debug(inode, " -> %d:%llu:[%d]%d ",
  729. le32_to_cpu(path->p_ext->ee_block),
  730. ext4_ext_pblock(path->p_ext),
  731. ext4_ext_is_unwritten(path->p_ext),
  732. ext4_ext_get_actual_len(path->p_ext));
  733. #ifdef CHECK_BINSEARCH
  734. {
  735. struct ext4_extent *chex, *ex;
  736. int k;
  737. chex = ex = EXT_FIRST_EXTENT(eh);
  738. for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
  739. BUG_ON(k && le32_to_cpu(ex->ee_block)
  740. <= le32_to_cpu(ex[-1].ee_block));
  741. if (block < le32_to_cpu(ex->ee_block))
  742. break;
  743. chex = ex;
  744. }
  745. BUG_ON(chex != path->p_ext);
  746. }
  747. #endif
  748. }
  749. void ext4_ext_tree_init(handle_t *handle, struct inode *inode)
  750. {
  751. struct ext4_extent_header *eh;
  752. eh = ext_inode_hdr(inode);
  753. eh->eh_depth = 0;
  754. eh->eh_entries = 0;
  755. eh->eh_magic = EXT4_EXT_MAGIC;
  756. eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
  757. eh->eh_generation = 0;
  758. ext4_mark_inode_dirty(handle, inode);
  759. }
  760. struct ext4_ext_path *
  761. ext4_find_extent(struct inode *inode, ext4_lblk_t block,
  762. struct ext4_ext_path **orig_path, int flags)
  763. {
  764. struct ext4_extent_header *eh;
  765. struct buffer_head *bh;
  766. struct ext4_ext_path *path = orig_path ? *orig_path : NULL;
  767. short int depth, i, ppos = 0;
  768. int ret;
  769. gfp_t gfp_flags = GFP_NOFS;
  770. if (flags & EXT4_EX_NOFAIL)
  771. gfp_flags |= __GFP_NOFAIL;
  772. eh = ext_inode_hdr(inode);
  773. depth = ext_depth(inode);
  774. if (depth < 0 || depth > EXT4_MAX_EXTENT_DEPTH) {
  775. EXT4_ERROR_INODE(inode, "inode has invalid extent depth: %d",
  776. depth);
  777. ret = -EFSCORRUPTED;
  778. goto err;
  779. }
  780. if (path) {
  781. ext4_ext_drop_refs(path);
  782. if (depth > path[0].p_maxdepth) {
  783. kfree(path);
  784. *orig_path = path = NULL;
  785. }
  786. }
  787. if (!path) {
  788. /* account possible depth increase */
  789. path = kcalloc(depth + 2, sizeof(struct ext4_ext_path),
  790. gfp_flags);
  791. if (unlikely(!path))
  792. return ERR_PTR(-ENOMEM);
  793. path[0].p_maxdepth = depth + 1;
  794. }
  795. path[0].p_hdr = eh;
  796. path[0].p_bh = NULL;
  797. i = depth;
  798. if (!(flags & EXT4_EX_NOCACHE) && depth == 0)
  799. ext4_cache_extents(inode, eh);
  800. /* walk through the tree */
  801. while (i) {
  802. ext_debug(inode, "depth %d: num %d, max %d\n",
  803. ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
  804. ext4_ext_binsearch_idx(inode, path + ppos, block);
  805. path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
  806. path[ppos].p_depth = i;
  807. path[ppos].p_ext = NULL;
  808. bh = read_extent_tree_block(inode, path[ppos].p_idx, --i, flags);
  809. if (IS_ERR(bh)) {
  810. ret = PTR_ERR(bh);
  811. goto err;
  812. }
  813. eh = ext_block_hdr(bh);
  814. ppos++;
  815. path[ppos].p_bh = bh;
  816. path[ppos].p_hdr = eh;
  817. }
  818. path[ppos].p_depth = i;
  819. path[ppos].p_ext = NULL;
  820. path[ppos].p_idx = NULL;
  821. /* find extent */
  822. ext4_ext_binsearch(inode, path + ppos, block);
  823. /* if not an empty leaf */
  824. if (path[ppos].p_ext)
  825. path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext);
  826. ext4_ext_show_path(inode, path);
  827. return path;
  828. err:
  829. ext4_ext_drop_refs(path);
  830. kfree(path);
  831. if (orig_path)
  832. *orig_path = NULL;
  833. return ERR_PTR(ret);
  834. }
  835. /*
  836. * ext4_ext_insert_index:
  837. * insert new index [@logical;@ptr] into the block at @curp;
  838. * check where to insert: before @curp or after @curp
  839. */
  840. static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
  841. struct ext4_ext_path *curp,
  842. int logical, ext4_fsblk_t ptr)
  843. {
  844. struct ext4_extent_idx *ix;
  845. int len, err;
  846. err = ext4_ext_get_access(handle, inode, curp);
  847. if (err)
  848. return err;
  849. if (unlikely(logical == le32_to_cpu(curp->p_idx->ei_block))) {
  850. EXT4_ERROR_INODE(inode,
  851. "logical %d == ei_block %d!",
  852. logical, le32_to_cpu(curp->p_idx->ei_block));
  853. return -EFSCORRUPTED;
  854. }
  855. if (unlikely(le16_to_cpu(curp->p_hdr->eh_entries)
  856. >= le16_to_cpu(curp->p_hdr->eh_max))) {
  857. EXT4_ERROR_INODE(inode,
  858. "eh_entries %d >= eh_max %d!",
  859. le16_to_cpu(curp->p_hdr->eh_entries),
  860. le16_to_cpu(curp->p_hdr->eh_max));
  861. return -EFSCORRUPTED;
  862. }
  863. if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
  864. /* insert after */
  865. ext_debug(inode, "insert new index %d after: %llu\n",
  866. logical, ptr);
  867. ix = curp->p_idx + 1;
  868. } else {
  869. /* insert before */
  870. ext_debug(inode, "insert new index %d before: %llu\n",
  871. logical, ptr);
  872. ix = curp->p_idx;
  873. }
  874. len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1;
  875. BUG_ON(len < 0);
  876. if (len > 0) {
  877. ext_debug(inode, "insert new index %d: "
  878. "move %d indices from 0x%p to 0x%p\n",
  879. logical, len, ix, ix + 1);
  880. memmove(ix + 1, ix, len * sizeof(struct ext4_extent_idx));
  881. }
  882. if (unlikely(ix > EXT_MAX_INDEX(curp->p_hdr))) {
  883. EXT4_ERROR_INODE(inode, "ix > EXT_MAX_INDEX!");
  884. return -EFSCORRUPTED;
  885. }
  886. ix->ei_block = cpu_to_le32(logical);
  887. ext4_idx_store_pblock(ix, ptr);
  888. le16_add_cpu(&curp->p_hdr->eh_entries, 1);
  889. if (unlikely(ix > EXT_LAST_INDEX(curp->p_hdr))) {
  890. EXT4_ERROR_INODE(inode, "ix > EXT_LAST_INDEX!");
  891. return -EFSCORRUPTED;
  892. }
  893. err = ext4_ext_dirty(handle, inode, curp);
  894. ext4_std_error(inode->i_sb, err);
  895. return err;
  896. }
  897. /*
  898. * ext4_ext_split:
  899. * inserts new subtree into the path, using free index entry
  900. * at depth @at:
  901. * - allocates all needed blocks (new leaf and all intermediate index blocks)
  902. * - makes decision where to split
  903. * - moves remaining extents and index entries (right to the split point)
  904. * into the newly allocated blocks
  905. * - initializes subtree
  906. */
  907. static int ext4_ext_split(handle_t *handle, struct inode *inode,
  908. unsigned int flags,
  909. struct ext4_ext_path *path,
  910. struct ext4_extent *newext, int at)
  911. {
  912. struct buffer_head *bh = NULL;
  913. int depth = ext_depth(inode);
  914. struct ext4_extent_header *neh;
  915. struct ext4_extent_idx *fidx;
  916. int i = at, k, m, a;
  917. ext4_fsblk_t newblock, oldblock;
  918. __le32 border;
  919. ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
  920. gfp_t gfp_flags = GFP_NOFS;
  921. int err = 0;
  922. size_t ext_size = 0;
  923. if (flags & EXT4_EX_NOFAIL)
  924. gfp_flags |= __GFP_NOFAIL;
  925. /* make decision: where to split? */
  926. /* FIXME: now decision is simplest: at current extent */
  927. /* if current leaf will be split, then we should use
  928. * border from split point */
  929. if (unlikely(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr))) {
  930. EXT4_ERROR_INODE(inode, "p_ext > EXT_MAX_EXTENT!");
  931. return -EFSCORRUPTED;
  932. }
  933. if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
  934. border = path[depth].p_ext[1].ee_block;
  935. ext_debug(inode, "leaf will be split."
  936. " next leaf starts at %d\n",
  937. le32_to_cpu(border));
  938. } else {
  939. border = newext->ee_block;
  940. ext_debug(inode, "leaf will be added."
  941. " next leaf starts at %d\n",
  942. le32_to_cpu(border));
  943. }
  944. /*
  945. * If error occurs, then we break processing
  946. * and mark filesystem read-only. index won't
  947. * be inserted and tree will be in consistent
  948. * state. Next mount will repair buffers too.
  949. */
  950. /*
  951. * Get array to track all allocated blocks.
  952. * We need this to handle errors and free blocks
  953. * upon them.
  954. */
  955. ablocks = kcalloc(depth, sizeof(ext4_fsblk_t), gfp_flags);
  956. if (!ablocks)
  957. return -ENOMEM;
  958. /* allocate all needed blocks */
  959. ext_debug(inode, "allocate %d blocks for indexes/leaf\n", depth - at);
  960. for (a = 0; a < depth - at; a++) {
  961. newblock = ext4_ext_new_meta_block(handle, inode, path,
  962. newext, &err, flags);
  963. if (newblock == 0)
  964. goto cleanup;
  965. ablocks[a] = newblock;
  966. }
  967. /* initialize new leaf */
  968. newblock = ablocks[--a];
  969. if (unlikely(newblock == 0)) {
  970. EXT4_ERROR_INODE(inode, "newblock == 0!");
  971. err = -EFSCORRUPTED;
  972. goto cleanup;
  973. }
  974. bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
  975. if (unlikely(!bh)) {
  976. err = -ENOMEM;
  977. goto cleanup;
  978. }
  979. lock_buffer(bh);
  980. err = ext4_journal_get_create_access(handle, bh);
  981. if (err)
  982. goto cleanup;
  983. neh = ext_block_hdr(bh);
  984. neh->eh_entries = 0;
  985. neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
  986. neh->eh_magic = EXT4_EXT_MAGIC;
  987. neh->eh_depth = 0;
  988. neh->eh_generation = 0;
  989. /* move remainder of path[depth] to the new leaf */
  990. if (unlikely(path[depth].p_hdr->eh_entries !=
  991. path[depth].p_hdr->eh_max)) {
  992. EXT4_ERROR_INODE(inode, "eh_entries %d != eh_max %d!",
  993. path[depth].p_hdr->eh_entries,
  994. path[depth].p_hdr->eh_max);
  995. err = -EFSCORRUPTED;
  996. goto cleanup;
  997. }
  998. /* start copy from next extent */
  999. m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++;
  1000. ext4_ext_show_move(inode, path, newblock, depth);
  1001. if (m) {
  1002. struct ext4_extent *ex;
  1003. ex = EXT_FIRST_EXTENT(neh);
  1004. memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m);
  1005. le16_add_cpu(&neh->eh_entries, m);
  1006. }
  1007. /* zero out unused area in the extent block */
  1008. ext_size = sizeof(struct ext4_extent_header) +
  1009. sizeof(struct ext4_extent) * le16_to_cpu(neh->eh_entries);
  1010. memset(bh->b_data + ext_size, 0, inode->i_sb->s_blocksize - ext_size);
  1011. ext4_extent_block_csum_set(inode, neh);
  1012. set_buffer_uptodate(bh);
  1013. unlock_buffer(bh);
  1014. err = ext4_handle_dirty_metadata(handle, inode, bh);
  1015. if (err)
  1016. goto cleanup;
  1017. brelse(bh);
  1018. bh = NULL;
  1019. /* correct old leaf */
  1020. if (m) {
  1021. err = ext4_ext_get_access(handle, inode, path + depth);
  1022. if (err)
  1023. goto cleanup;
  1024. le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
  1025. err = ext4_ext_dirty(handle, inode, path + depth);
  1026. if (err)
  1027. goto cleanup;
  1028. }
  1029. /* create intermediate indexes */
  1030. k = depth - at - 1;
  1031. if (unlikely(k < 0)) {
  1032. EXT4_ERROR_INODE(inode, "k %d < 0!", k);
  1033. err = -EFSCORRUPTED;
  1034. goto cleanup;
  1035. }
  1036. if (k)
  1037. ext_debug(inode, "create %d intermediate indices\n", k);
  1038. /* insert new index into current index block */
  1039. /* current depth stored in i var */
  1040. i = depth - 1;
  1041. while (k--) {
  1042. oldblock = newblock;
  1043. newblock = ablocks[--a];
  1044. bh = sb_getblk(inode->i_sb, newblock);
  1045. if (unlikely(!bh)) {
  1046. err = -ENOMEM;
  1047. goto cleanup;
  1048. }
  1049. lock_buffer(bh);
  1050. err = ext4_journal_get_create_access(handle, bh);
  1051. if (err)
  1052. goto cleanup;
  1053. neh = ext_block_hdr(bh);
  1054. neh->eh_entries = cpu_to_le16(1);
  1055. neh->eh_magic = EXT4_EXT_MAGIC;
  1056. neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
  1057. neh->eh_depth = cpu_to_le16(depth - i);
  1058. neh->eh_generation = 0;
  1059. fidx = EXT_FIRST_INDEX(neh);
  1060. fidx->ei_block = border;
  1061. ext4_idx_store_pblock(fidx, oldblock);
  1062. ext_debug(inode, "int.index at %d (block %llu): %u -> %llu\n",
  1063. i, newblock, le32_to_cpu(border), oldblock);
  1064. /* move remainder of path[i] to the new index block */
  1065. if (unlikely(EXT_MAX_INDEX(path[i].p_hdr) !=
  1066. EXT_LAST_INDEX(path[i].p_hdr))) {
  1067. EXT4_ERROR_INODE(inode,
  1068. "EXT_MAX_INDEX != EXT_LAST_INDEX ee_block %d!",
  1069. le32_to_cpu(path[i].p_ext->ee_block));
  1070. err = -EFSCORRUPTED;
  1071. goto cleanup;
  1072. }
  1073. /* start copy indexes */
  1074. m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
  1075. ext_debug(inode, "cur 0x%p, last 0x%p\n", path[i].p_idx,
  1076. EXT_MAX_INDEX(path[i].p_hdr));
  1077. ext4_ext_show_move(inode, path, newblock, i);
  1078. if (m) {
  1079. memmove(++fidx, path[i].p_idx,
  1080. sizeof(struct ext4_extent_idx) * m);
  1081. le16_add_cpu(&neh->eh_entries, m);
  1082. }
  1083. /* zero out unused area in the extent block */
  1084. ext_size = sizeof(struct ext4_extent_header) +
  1085. (sizeof(struct ext4_extent) * le16_to_cpu(neh->eh_entries));
  1086. memset(bh->b_data + ext_size, 0,
  1087. inode->i_sb->s_blocksize - ext_size);
  1088. ext4_extent_block_csum_set(inode, neh);
  1089. set_buffer_uptodate(bh);
  1090. unlock_buffer(bh);
  1091. err = ext4_handle_dirty_metadata(handle, inode, bh);
  1092. if (err)
  1093. goto cleanup;
  1094. brelse(bh);
  1095. bh = NULL;
  1096. /* correct old index */
  1097. if (m) {
  1098. err = ext4_ext_get_access(handle, inode, path + i);
  1099. if (err)
  1100. goto cleanup;
  1101. le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
  1102. err = ext4_ext_dirty(handle, inode, path + i);
  1103. if (err)
  1104. goto cleanup;
  1105. }
  1106. i--;
  1107. }
  1108. /* insert new index */
  1109. err = ext4_ext_insert_index(handle, inode, path + at,
  1110. le32_to_cpu(border), newblock);
  1111. cleanup:
  1112. if (bh) {
  1113. if (buffer_locked(bh))
  1114. unlock_buffer(bh);
  1115. brelse(bh);
  1116. }
  1117. if (err) {
  1118. /* free all allocated blocks in error case */
  1119. for (i = 0; i < depth; i++) {
  1120. if (!ablocks[i])
  1121. continue;
  1122. ext4_free_blocks(handle, inode, NULL, ablocks[i], 1,
  1123. EXT4_FREE_BLOCKS_METADATA);
  1124. }
  1125. }
  1126. kfree(ablocks);
  1127. return err;
  1128. }
  1129. /*
  1130. * ext4_ext_grow_indepth:
  1131. * implements tree growing procedure:
  1132. * - allocates new block
  1133. * - moves top-level data (index block or leaf) into the new block
  1134. * - initializes new top-level, creating index that points to the
  1135. * just created block
  1136. */
  1137. static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
  1138. unsigned int flags)
  1139. {
  1140. struct ext4_extent_header *neh;
  1141. struct buffer_head *bh;
  1142. ext4_fsblk_t newblock, goal = 0;
  1143. struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
  1144. int err = 0;
  1145. size_t ext_size = 0;
  1146. /* Try to prepend new index to old one */
  1147. if (ext_depth(inode))
  1148. goal = ext4_idx_pblock(EXT_FIRST_INDEX(ext_inode_hdr(inode)));
  1149. if (goal > le32_to_cpu(es->s_first_data_block)) {
  1150. flags |= EXT4_MB_HINT_TRY_GOAL;
  1151. goal--;
  1152. } else
  1153. goal = ext4_inode_to_goal_block(inode);
  1154. newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
  1155. NULL, &err);
  1156. if (newblock == 0)
  1157. return err;
  1158. bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
  1159. if (unlikely(!bh))
  1160. return -ENOMEM;
  1161. lock_buffer(bh);
  1162. err = ext4_journal_get_create_access(handle, bh);
  1163. if (err) {
  1164. unlock_buffer(bh);
  1165. goto out;
  1166. }
  1167. ext_size = sizeof(EXT4_I(inode)->i_data);
  1168. /* move top-level index/leaf into new block */
  1169. memmove(bh->b_data, EXT4_I(inode)->i_data, ext_size);
  1170. /* zero out unused area in the extent block */
  1171. memset(bh->b_data + ext_size, 0, inode->i_sb->s_blocksize - ext_size);
  1172. /* set size of new block */
  1173. neh = ext_block_hdr(bh);
  1174. /* old root could have indexes or leaves
  1175. * so calculate e_max right way */
  1176. if (ext_depth(inode))
  1177. neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
  1178. else
  1179. neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
  1180. neh->eh_magic = EXT4_EXT_MAGIC;
  1181. ext4_extent_block_csum_set(inode, neh);
  1182. set_buffer_uptodate(bh);
  1183. unlock_buffer(bh);
  1184. err = ext4_handle_dirty_metadata(handle, inode, bh);
  1185. if (err)
  1186. goto out;
  1187. /* Update top-level index: num,max,pointer */
  1188. neh = ext_inode_hdr(inode);
  1189. neh->eh_entries = cpu_to_le16(1);
  1190. ext4_idx_store_pblock(EXT_FIRST_INDEX(neh), newblock);
  1191. if (neh->eh_depth == 0) {
  1192. /* Root extent block becomes index block */
  1193. neh->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0));
  1194. EXT_FIRST_INDEX(neh)->ei_block =
  1195. EXT_FIRST_EXTENT(neh)->ee_block;
  1196. }
  1197. ext_debug(inode, "new root: num %d(%d), lblock %d, ptr %llu\n",
  1198. le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
  1199. le32_to_cpu(EXT_FIRST_INDEX(neh)->ei_block),
  1200. ext4_idx_pblock(EXT_FIRST_INDEX(neh)));
  1201. le16_add_cpu(&neh->eh_depth, 1);
  1202. err = ext4_mark_inode_dirty(handle, inode);
  1203. out:
  1204. brelse(bh);
  1205. return err;
  1206. }
  1207. /*
  1208. * ext4_ext_create_new_leaf:
  1209. * finds empty index and adds new leaf.
  1210. * if no free index is found, then it requests in-depth growing.
  1211. */
  1212. static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
  1213. unsigned int mb_flags,
  1214. unsigned int gb_flags,
  1215. struct ext4_ext_path **ppath,
  1216. struct ext4_extent *newext)
  1217. {
  1218. struct ext4_ext_path *path = *ppath;
  1219. struct ext4_ext_path *curp;
  1220. int depth, i, err = 0;
  1221. repeat:
  1222. i = depth = ext_depth(inode);
  1223. /* walk up to the tree and look for free index entry */
  1224. curp = path + depth;
  1225. while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
  1226. i--;
  1227. curp--;
  1228. }
  1229. /* we use already allocated block for index block,
  1230. * so subsequent data blocks should be contiguous */
  1231. if (EXT_HAS_FREE_INDEX(curp)) {
  1232. /* if we found index with free entry, then use that
  1233. * entry: create all needed subtree and add new leaf */
  1234. err = ext4_ext_split(handle, inode, mb_flags, path, newext, i);
  1235. if (err)
  1236. goto out;
  1237. /* refill path */
  1238. path = ext4_find_extent(inode,
  1239. (ext4_lblk_t)le32_to_cpu(newext->ee_block),
  1240. ppath, gb_flags);
  1241. if (IS_ERR(path))
  1242. err = PTR_ERR(path);
  1243. } else {
  1244. /* tree is full, time to grow in depth */
  1245. err = ext4_ext_grow_indepth(handle, inode, mb_flags);
  1246. if (err)
  1247. goto out;
  1248. /* refill path */
  1249. path = ext4_find_extent(inode,
  1250. (ext4_lblk_t)le32_to_cpu(newext->ee_block),
  1251. ppath, gb_flags);
  1252. if (IS_ERR(path)) {
  1253. err = PTR_ERR(path);
  1254. goto out;
  1255. }
  1256. /*
  1257. * only first (depth 0 -> 1) produces free space;
  1258. * in all other cases we have to split the grown tree
  1259. */
  1260. depth = ext_depth(inode);
  1261. if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
  1262. /* now we need to split */
  1263. goto repeat;
  1264. }
  1265. }
  1266. out:
  1267. return err;
  1268. }
  1269. /*
  1270. * search the closest allocated block to the left for *logical
  1271. * and returns it at @logical + it's physical address at @phys
  1272. * if *logical is the smallest allocated block, the function
  1273. * returns 0 at @phys
  1274. * return value contains 0 (success) or error code
  1275. */
  1276. static int ext4_ext_search_left(struct inode *inode,
  1277. struct ext4_ext_path *path,
  1278. ext4_lblk_t *logical, ext4_fsblk_t *phys)
  1279. {
  1280. struct ext4_extent_idx *ix;
  1281. struct ext4_extent *ex;
  1282. int depth, ee_len;
  1283. if (unlikely(path == NULL)) {
  1284. EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
  1285. return -EFSCORRUPTED;
  1286. }
  1287. depth = path->p_depth;
  1288. *phys = 0;
  1289. if (depth == 0 && path->p_ext == NULL)
  1290. return 0;
  1291. /* usually extent in the path covers blocks smaller
  1292. * then *logical, but it can be that extent is the
  1293. * first one in the file */
  1294. ex = path[depth].p_ext;
  1295. ee_len = ext4_ext_get_actual_len(ex);
  1296. if (*logical < le32_to_cpu(ex->ee_block)) {
  1297. if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
  1298. EXT4_ERROR_INODE(inode,
  1299. "EXT_FIRST_EXTENT != ex *logical %d ee_block %d!",
  1300. *logical, le32_to_cpu(ex->ee_block));
  1301. return -EFSCORRUPTED;
  1302. }
  1303. while (--depth >= 0) {
  1304. ix = path[depth].p_idx;
  1305. if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
  1306. EXT4_ERROR_INODE(inode,
  1307. "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
  1308. ix != NULL ? le32_to_cpu(ix->ei_block) : 0,
  1309. EXT_FIRST_INDEX(path[depth].p_hdr) != NULL ?
  1310. le32_to_cpu(EXT_FIRST_INDEX(path[depth].p_hdr)->ei_block) : 0,
  1311. depth);
  1312. return -EFSCORRUPTED;
  1313. }
  1314. }
  1315. return 0;
  1316. }
  1317. if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
  1318. EXT4_ERROR_INODE(inode,
  1319. "logical %d < ee_block %d + ee_len %d!",
  1320. *logical, le32_to_cpu(ex->ee_block), ee_len);
  1321. return -EFSCORRUPTED;
  1322. }
  1323. *logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
  1324. *phys = ext4_ext_pblock(ex) + ee_len - 1;
  1325. return 0;
  1326. }
  1327. /*
  1328. * Search the closest allocated block to the right for *logical
  1329. * and returns it at @logical + it's physical address at @phys.
  1330. * If not exists, return 0 and @phys is set to 0. We will return
  1331. * 1 which means we found an allocated block and ret_ex is valid.
  1332. * Or return a (< 0) error code.
  1333. */
  1334. static int ext4_ext_search_right(struct inode *inode,
  1335. struct ext4_ext_path *path,
  1336. ext4_lblk_t *logical, ext4_fsblk_t *phys,
  1337. struct ext4_extent *ret_ex)
  1338. {
  1339. struct buffer_head *bh = NULL;
  1340. struct ext4_extent_header *eh;
  1341. struct ext4_extent_idx *ix;
  1342. struct ext4_extent *ex;
  1343. int depth; /* Note, NOT eh_depth; depth from top of tree */
  1344. int ee_len;
  1345. if (unlikely(path == NULL)) {
  1346. EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
  1347. return -EFSCORRUPTED;
  1348. }
  1349. depth = path->p_depth;
  1350. *phys = 0;
  1351. if (depth == 0 && path->p_ext == NULL)
  1352. return 0;
  1353. /* usually extent in the path covers blocks smaller
  1354. * then *logical, but it can be that extent is the
  1355. * first one in the file */
  1356. ex = path[depth].p_ext;
  1357. ee_len = ext4_ext_get_actual_len(ex);
  1358. if (*logical < le32_to_cpu(ex->ee_block)) {
  1359. if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
  1360. EXT4_ERROR_INODE(inode,
  1361. "first_extent(path[%d].p_hdr) != ex",
  1362. depth);
  1363. return -EFSCORRUPTED;
  1364. }
  1365. while (--depth >= 0) {
  1366. ix = path[depth].p_idx;
  1367. if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
  1368. EXT4_ERROR_INODE(inode,
  1369. "ix != EXT_FIRST_INDEX *logical %d!",
  1370. *logical);
  1371. return -EFSCORRUPTED;
  1372. }
  1373. }
  1374. goto found_extent;
  1375. }
  1376. if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
  1377. EXT4_ERROR_INODE(inode,
  1378. "logical %d < ee_block %d + ee_len %d!",
  1379. *logical, le32_to_cpu(ex->ee_block), ee_len);
  1380. return -EFSCORRUPTED;
  1381. }
  1382. if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
  1383. /* next allocated block in this leaf */
  1384. ex++;
  1385. goto found_extent;
  1386. }
  1387. /* go up and search for index to the right */
  1388. while (--depth >= 0) {
  1389. ix = path[depth].p_idx;
  1390. if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
  1391. goto got_index;
  1392. }
  1393. /* we've gone up to the root and found no index to the right */
  1394. return 0;
  1395. got_index:
  1396. /* we've found index to the right, let's
  1397. * follow it and find the closest allocated
  1398. * block to the right */
  1399. ix++;
  1400. while (++depth < path->p_depth) {
  1401. /* subtract from p_depth to get proper eh_depth */
  1402. bh = read_extent_tree_block(inode, ix, path->p_depth - depth, 0);
  1403. if (IS_ERR(bh))
  1404. return PTR_ERR(bh);
  1405. eh = ext_block_hdr(bh);
  1406. ix = EXT_FIRST_INDEX(eh);
  1407. put_bh(bh);
  1408. }
  1409. bh = read_extent_tree_block(inode, ix, path->p_depth - depth, 0);
  1410. if (IS_ERR(bh))
  1411. return PTR_ERR(bh);
  1412. eh = ext_block_hdr(bh);
  1413. ex = EXT_FIRST_EXTENT(eh);
  1414. found_extent:
  1415. *logical = le32_to_cpu(ex->ee_block);
  1416. *phys = ext4_ext_pblock(ex);
  1417. if (ret_ex)
  1418. *ret_ex = *ex;
  1419. if (bh)
  1420. put_bh(bh);
  1421. return 1;
  1422. }
  1423. /*
  1424. * ext4_ext_next_allocated_block:
  1425. * returns allocated block in subsequent extent or EXT_MAX_BLOCKS.
  1426. * NOTE: it considers block number from index entry as
  1427. * allocated block. Thus, index entries have to be consistent
  1428. * with leaves.
  1429. */
  1430. ext4_lblk_t
  1431. ext4_ext_next_allocated_block(struct ext4_ext_path *path)
  1432. {
  1433. int depth;
  1434. BUG_ON(path == NULL);
  1435. depth = path->p_depth;
  1436. if (depth == 0 && path->p_ext == NULL)
  1437. return EXT_MAX_BLOCKS;
  1438. while (depth >= 0) {
  1439. struct ext4_ext_path *p = &path[depth];
  1440. if (depth == path->p_depth) {
  1441. /* leaf */
  1442. if (p->p_ext && p->p_ext != EXT_LAST_EXTENT(p->p_hdr))
  1443. return le32_to_cpu(p->p_ext[1].ee_block);
  1444. } else {
  1445. /* index */
  1446. if (p->p_idx != EXT_LAST_INDEX(p->p_hdr))
  1447. return le32_to_cpu(p->p_idx[1].ei_block);
  1448. }
  1449. depth--;
  1450. }
  1451. return EXT_MAX_BLOCKS;
  1452. }
  1453. /*
  1454. * ext4_ext_next_leaf_block:
  1455. * returns first allocated block from next leaf or EXT_MAX_BLOCKS
  1456. */
  1457. static ext4_lblk_t ext4_ext_next_leaf_block(struct ext4_ext_path *path)
  1458. {
  1459. int depth;
  1460. BUG_ON(path == NULL);
  1461. depth = path->p_depth;
  1462. /* zero-tree has no leaf blocks at all */
  1463. if (depth == 0)
  1464. return EXT_MAX_BLOCKS;
  1465. /* go to index block */
  1466. depth--;
  1467. while (depth >= 0) {
  1468. if (path[depth].p_idx !=
  1469. EXT_LAST_INDEX(path[depth].p_hdr))
  1470. return (ext4_lblk_t)
  1471. le32_to_cpu(path[depth].p_idx[1].ei_block);
  1472. depth--;
  1473. }
  1474. return EXT_MAX_BLOCKS;
  1475. }
  1476. /*
  1477. * ext4_ext_correct_indexes:
  1478. * if leaf gets modified and modified extent is first in the leaf,
  1479. * then we have to correct all indexes above.
  1480. * TODO: do we need to correct tree in all cases?
  1481. */
  1482. static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
  1483. struct ext4_ext_path *path)
  1484. {
  1485. struct ext4_extent_header *eh;
  1486. int depth = ext_depth(inode);
  1487. struct ext4_extent *ex;
  1488. __le32 border;
  1489. int k, err = 0;
  1490. eh = path[depth].p_hdr;
  1491. ex = path[depth].p_ext;
  1492. if (unlikely(ex == NULL || eh == NULL)) {
  1493. EXT4_ERROR_INODE(inode,
  1494. "ex %p == NULL or eh %p == NULL", ex, eh);
  1495. return -EFSCORRUPTED;
  1496. }
  1497. if (depth == 0) {
  1498. /* there is no tree at all */
  1499. return 0;
  1500. }
  1501. if (ex != EXT_FIRST_EXTENT(eh)) {
  1502. /* we correct tree if first leaf got modified only */
  1503. return 0;
  1504. }
  1505. /*
  1506. * TODO: we need correction if border is smaller than current one
  1507. */
  1508. k = depth - 1;
  1509. border = path[depth].p_ext->ee_block;
  1510. err = ext4_ext_get_access(handle, inode, path + k);
  1511. if (err)
  1512. return err;
  1513. path[k].p_idx->ei_block = border;
  1514. err = ext4_ext_dirty(handle, inode, path + k);
  1515. if (err)
  1516. return err;
  1517. while (k--) {
  1518. /* change all left-side indexes */
  1519. if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
  1520. break;
  1521. err = ext4_ext_get_access(handle, inode, path + k);
  1522. if (err)
  1523. break;
  1524. path[k].p_idx->ei_block = border;
  1525. err = ext4_ext_dirty(handle, inode, path + k);
  1526. if (err)
  1527. break;
  1528. }
  1529. return err;
  1530. }
  1531. static int ext4_can_extents_be_merged(struct inode *inode,
  1532. struct ext4_extent *ex1,
  1533. struct ext4_extent *ex2)
  1534. {
  1535. unsigned short ext1_ee_len, ext2_ee_len;
  1536. if (ext4_ext_is_unwritten(ex1) != ext4_ext_is_unwritten(ex2))
  1537. return 0;
  1538. ext1_ee_len = ext4_ext_get_actual_len(ex1);
  1539. ext2_ee_len = ext4_ext_get_actual_len(ex2);
  1540. if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
  1541. le32_to_cpu(ex2->ee_block))
  1542. return 0;
  1543. if (ext1_ee_len + ext2_ee_len > EXT_INIT_MAX_LEN)
  1544. return 0;
  1545. if (ext4_ext_is_unwritten(ex1) &&
  1546. ext1_ee_len + ext2_ee_len > EXT_UNWRITTEN_MAX_LEN)
  1547. return 0;
  1548. #ifdef AGGRESSIVE_TEST
  1549. if (ext1_ee_len >= 4)
  1550. return 0;
  1551. #endif
  1552. if (ext4_ext_pblock(ex1) + ext1_ee_len == ext4_ext_pblock(ex2))
  1553. return 1;
  1554. return 0;
  1555. }
  1556. /*
  1557. * This function tries to merge the "ex" extent to the next extent in the tree.
  1558. * It always tries to merge towards right. If you want to merge towards
  1559. * left, pass "ex - 1" as argument instead of "ex".
  1560. * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
  1561. * 1 if they got merged.
  1562. */
  1563. static int ext4_ext_try_to_merge_right(struct inode *inode,
  1564. struct ext4_ext_path *path,
  1565. struct ext4_extent *ex)
  1566. {
  1567. struct ext4_extent_header *eh;
  1568. unsigned int depth, len;
  1569. int merge_done = 0, unwritten;
  1570. depth = ext_depth(inode);
  1571. BUG_ON(path[depth].p_hdr == NULL);
  1572. eh = path[depth].p_hdr;
  1573. while (ex < EXT_LAST_EXTENT(eh)) {
  1574. if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
  1575. break;
  1576. /* merge with next extent! */
  1577. unwritten = ext4_ext_is_unwritten(ex);
  1578. ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
  1579. + ext4_ext_get_actual_len(ex + 1));
  1580. if (unwritten)
  1581. ext4_ext_mark_unwritten(ex);
  1582. if (ex + 1 < EXT_LAST_EXTENT(eh)) {
  1583. len = (EXT_LAST_EXTENT(eh) - ex - 1)
  1584. * sizeof(struct ext4_extent);
  1585. memmove(ex + 1, ex + 2, len);
  1586. }
  1587. le16_add_cpu(&eh->eh_entries, -1);
  1588. merge_done = 1;
  1589. WARN_ON(eh->eh_entries == 0);
  1590. if (!eh->eh_entries)
  1591. EXT4_ERROR_INODE(inode, "eh->eh_entries = 0!");
  1592. }
  1593. return merge_done;
  1594. }
  1595. /*
  1596. * This function does a very simple check to see if we can collapse
  1597. * an extent tree with a single extent tree leaf block into the inode.
  1598. */
  1599. static void ext4_ext_try_to_merge_up(handle_t *handle,
  1600. struct inode *inode,
  1601. struct ext4_ext_path *path)
  1602. {
  1603. size_t s;
  1604. unsigned max_root = ext4_ext_space_root(inode, 0);
  1605. ext4_fsblk_t blk;
  1606. if ((path[0].p_depth != 1) ||
  1607. (le16_to_cpu(path[0].p_hdr->eh_entries) != 1) ||
  1608. (le16_to_cpu(path[1].p_hdr->eh_entries) > max_root))
  1609. return;
  1610. /*
  1611. * We need to modify the block allocation bitmap and the block
  1612. * group descriptor to release the extent tree block. If we
  1613. * can't get the journal credits, give up.
  1614. */
  1615. if (ext4_journal_extend(handle, 2,
  1616. ext4_free_metadata_revoke_credits(inode->i_sb, 1)))
  1617. return;
  1618. /*
  1619. * Copy the extent data up to the inode
  1620. */
  1621. blk = ext4_idx_pblock(path[0].p_idx);
  1622. s = le16_to_cpu(path[1].p_hdr->eh_entries) *
  1623. sizeof(struct ext4_extent_idx);
  1624. s += sizeof(struct ext4_extent_header);
  1625. path[1].p_maxdepth = path[0].p_maxdepth;
  1626. memcpy(path[0].p_hdr, path[1].p_hdr, s);
  1627. path[0].p_depth = 0;
  1628. path[0].p_ext = EXT_FIRST_EXTENT(path[0].p_hdr) +
  1629. (path[1].p_ext - EXT_FIRST_EXTENT(path[1].p_hdr));
  1630. path[0].p_hdr->eh_max = cpu_to_le16(max_root);
  1631. brelse(path[1].p_bh);
  1632. ext4_free_blocks(handle, inode, NULL, blk, 1,
  1633. EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
  1634. }
  1635. /*
  1636. * This function tries to merge the @ex extent to neighbours in the tree, then
  1637. * tries to collapse the extent tree into the inode.
  1638. */
  1639. static void ext4_ext_try_to_merge(handle_t *handle,
  1640. struct inode *inode,
  1641. struct ext4_ext_path *path,
  1642. struct ext4_extent *ex)
  1643. {
  1644. struct ext4_extent_header *eh;
  1645. unsigned int depth;
  1646. int merge_done = 0;
  1647. depth = ext_depth(inode);
  1648. BUG_ON(path[depth].p_hdr == NULL);
  1649. eh = path[depth].p_hdr;
  1650. if (ex > EXT_FIRST_EXTENT(eh))
  1651. merge_done = ext4_ext_try_to_merge_right(inode, path, ex - 1);
  1652. if (!merge_done)
  1653. (void) ext4_ext_try_to_merge_right(inode, path, ex);
  1654. ext4_ext_try_to_merge_up(handle, inode, path);
  1655. }
  1656. /*
  1657. * check if a portion of the "newext" extent overlaps with an
  1658. * existing extent.
  1659. *
  1660. * If there is an overlap discovered, it updates the length of the newext
  1661. * such that there will be no overlap, and then returns 1.
  1662. * If there is no overlap found, it returns 0.
  1663. */
  1664. static unsigned int ext4_ext_check_overlap(struct ext4_sb_info *sbi,
  1665. struct inode *inode,
  1666. struct ext4_extent *newext,
  1667. struct ext4_ext_path *path)
  1668. {
  1669. ext4_lblk_t b1, b2;
  1670. unsigned int depth, len1;
  1671. unsigned int ret = 0;
  1672. b1 = le32_to_cpu(newext->ee_block);
  1673. len1 = ext4_ext_get_actual_len(newext);
  1674. depth = ext_depth(inode);
  1675. if (!path[depth].p_ext)
  1676. goto out;
  1677. b2 = EXT4_LBLK_CMASK(sbi, le32_to_cpu(path[depth].p_ext->ee_block));
  1678. /*
  1679. * get the next allocated block if the extent in the path
  1680. * is before the requested block(s)
  1681. */
  1682. if (b2 < b1) {
  1683. b2 = ext4_ext_next_allocated_block(path);
  1684. if (b2 == EXT_MAX_BLOCKS)
  1685. goto out;
  1686. b2 = EXT4_LBLK_CMASK(sbi, b2);
  1687. }
  1688. /* check for wrap through zero on extent logical start block*/
  1689. if (b1 + len1 < b1) {
  1690. len1 = EXT_MAX_BLOCKS - b1;
  1691. newext->ee_len = cpu_to_le16(len1);
  1692. ret = 1;
  1693. }
  1694. /* check for overlap */
  1695. if (b1 + len1 > b2) {
  1696. newext->ee_len = cpu_to_le16(b2 - b1);
  1697. ret = 1;
  1698. }
  1699. out:
  1700. return ret;
  1701. }
  1702. /*
  1703. * ext4_ext_insert_extent:
  1704. * tries to merge requested extent into the existing extent or
  1705. * inserts requested extent as new one into the tree,
  1706. * creating new leaf in the no-space case.
  1707. */
  1708. int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
  1709. struct ext4_ext_path **ppath,
  1710. struct ext4_extent *newext, int gb_flags)
  1711. {
  1712. struct ext4_ext_path *path = *ppath;
  1713. struct ext4_extent_header *eh;
  1714. struct ext4_extent *ex, *fex;
  1715. struct ext4_extent *nearex; /* nearest extent */
  1716. struct ext4_ext_path *npath = NULL;
  1717. int depth, len, err;
  1718. ext4_lblk_t next;
  1719. int mb_flags = 0, unwritten;
  1720. if (gb_flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
  1721. mb_flags |= EXT4_MB_DELALLOC_RESERVED;
  1722. if (unlikely(ext4_ext_get_actual_len(newext) == 0)) {
  1723. EXT4_ERROR_INODE(inode, "ext4_ext_get_actual_len(newext) == 0");
  1724. return -EFSCORRUPTED;
  1725. }
  1726. depth = ext_depth(inode);
  1727. ex = path[depth].p_ext;
  1728. eh = path[depth].p_hdr;
  1729. if (unlikely(path[depth].p_hdr == NULL)) {
  1730. EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
  1731. return -EFSCORRUPTED;
  1732. }
  1733. /* try to insert block into found extent and return */
  1734. if (ex && !(gb_flags & EXT4_GET_BLOCKS_PRE_IO)) {
  1735. /*
  1736. * Try to see whether we should rather test the extent on
  1737. * right from ex, or from the left of ex. This is because
  1738. * ext4_find_extent() can return either extent on the
  1739. * left, or on the right from the searched position. This
  1740. * will make merging more effective.
  1741. */
  1742. if (ex < EXT_LAST_EXTENT(eh) &&
  1743. (le32_to_cpu(ex->ee_block) +
  1744. ext4_ext_get_actual_len(ex) <
  1745. le32_to_cpu(newext->ee_block))) {
  1746. ex += 1;
  1747. goto prepend;
  1748. } else if ((ex > EXT_FIRST_EXTENT(eh)) &&
  1749. (le32_to_cpu(newext->ee_block) +
  1750. ext4_ext_get_actual_len(newext) <
  1751. le32_to_cpu(ex->ee_block)))
  1752. ex -= 1;
  1753. /* Try to append newex to the ex */
  1754. if (ext4_can_extents_be_merged(inode, ex, newext)) {
  1755. ext_debug(inode, "append [%d]%d block to %u:[%d]%d"
  1756. "(from %llu)\n",
  1757. ext4_ext_is_unwritten(newext),
  1758. ext4_ext_get_actual_len(newext),
  1759. le32_to_cpu(ex->ee_block),
  1760. ext4_ext_is_unwritten(ex),
  1761. ext4_ext_get_actual_len(ex),
  1762. ext4_ext_pblock(ex));
  1763. err = ext4_ext_get_access(handle, inode,
  1764. path + depth);
  1765. if (err)
  1766. return err;
  1767. unwritten = ext4_ext_is_unwritten(ex);
  1768. ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
  1769. + ext4_ext_get_actual_len(newext));
  1770. if (unwritten)
  1771. ext4_ext_mark_unwritten(ex);
  1772. eh = path[depth].p_hdr;
  1773. nearex = ex;
  1774. goto merge;
  1775. }
  1776. prepend:
  1777. /* Try to prepend newex to the ex */
  1778. if (ext4_can_extents_be_merged(inode, newext, ex)) {
  1779. ext_debug(inode, "prepend %u[%d]%d block to %u:[%d]%d"
  1780. "(from %llu)\n",
  1781. le32_to_cpu(newext->ee_block),
  1782. ext4_ext_is_unwritten(newext),
  1783. ext4_ext_get_actual_len(newext),
  1784. le32_to_cpu(ex->ee_block),
  1785. ext4_ext_is_unwritten(ex),
  1786. ext4_ext_get_actual_len(ex),
  1787. ext4_ext_pblock(ex));
  1788. err = ext4_ext_get_access(handle, inode,
  1789. path + depth);
  1790. if (err)
  1791. return err;
  1792. unwritten = ext4_ext_is_unwritten(ex);
  1793. ex->ee_block = newext->ee_block;
  1794. ext4_ext_store_pblock(ex, ext4_ext_pblock(newext));
  1795. ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
  1796. + ext4_ext_get_actual_len(newext));
  1797. if (unwritten)
  1798. ext4_ext_mark_unwritten(ex);
  1799. eh = path[depth].p_hdr;
  1800. nearex = ex;
  1801. goto merge;
  1802. }
  1803. }
  1804. depth = ext_depth(inode);
  1805. eh = path[depth].p_hdr;
  1806. if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
  1807. goto has_space;
  1808. /* probably next leaf has space for us? */
  1809. fex = EXT_LAST_EXTENT(eh);
  1810. next = EXT_MAX_BLOCKS;
  1811. if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))
  1812. next = ext4_ext_next_leaf_block(path);
  1813. if (next != EXT_MAX_BLOCKS) {
  1814. ext_debug(inode, "next leaf block - %u\n", next);
  1815. BUG_ON(npath != NULL);
  1816. npath = ext4_find_extent(inode, next, NULL, gb_flags);
  1817. if (IS_ERR(npath))
  1818. return PTR_ERR(npath);
  1819. BUG_ON(npath->p_depth != path->p_depth);
  1820. eh = npath[depth].p_hdr;
  1821. if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
  1822. ext_debug(inode, "next leaf isn't full(%d)\n",
  1823. le16_to_cpu(eh->eh_entries));
  1824. path = npath;
  1825. goto has_space;
  1826. }
  1827. ext_debug(inode, "next leaf has no free space(%d,%d)\n",
  1828. le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
  1829. }
  1830. /*
  1831. * There is no free space in the found leaf.
  1832. * We're gonna add a new leaf in the tree.
  1833. */
  1834. if (gb_flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
  1835. mb_flags |= EXT4_MB_USE_RESERVED;
  1836. err = ext4_ext_create_new_leaf(handle, inode, mb_flags, gb_flags,
  1837. ppath, newext);
  1838. if (err)
  1839. goto cleanup;
  1840. depth = ext_depth(inode);
  1841. eh = path[depth].p_hdr;
  1842. has_space:
  1843. nearex = path[depth].p_ext;
  1844. err = ext4_ext_get_access(handle, inode, path + depth);
  1845. if (err)
  1846. goto cleanup;
  1847. if (!nearex) {
  1848. /* there is no extent in this leaf, create first one */
  1849. ext_debug(inode, "first extent in the leaf: %u:%llu:[%d]%d\n",
  1850. le32_to_cpu(newext->ee_block),
  1851. ext4_ext_pblock(newext),
  1852. ext4_ext_is_unwritten(newext),
  1853. ext4_ext_get_actual_len(newext));
  1854. nearex = EXT_FIRST_EXTENT(eh);
  1855. } else {
  1856. if (le32_to_cpu(newext->ee_block)
  1857. > le32_to_cpu(nearex->ee_block)) {
  1858. /* Insert after */
  1859. ext_debug(inode, "insert %u:%llu:[%d]%d before: "
  1860. "nearest %p\n",
  1861. le32_to_cpu(newext->ee_block),
  1862. ext4_ext_pblock(newext),
  1863. ext4_ext_is_unwritten(newext),
  1864. ext4_ext_get_actual_len(newext),
  1865. nearex);
  1866. nearex++;
  1867. } else {
  1868. /* Insert before */
  1869. BUG_ON(newext->ee_block == nearex->ee_block);
  1870. ext_debug(inode, "insert %u:%llu:[%d]%d after: "
  1871. "nearest %p\n",
  1872. le32_to_cpu(newext->ee_block),
  1873. ext4_ext_pblock(newext),
  1874. ext4_ext_is_unwritten(newext),
  1875. ext4_ext_get_actual_len(newext),
  1876. nearex);
  1877. }
  1878. len = EXT_LAST_EXTENT(eh) - nearex + 1;
  1879. if (len > 0) {
  1880. ext_debug(inode, "insert %u:%llu:[%d]%d: "
  1881. "move %d extents from 0x%p to 0x%p\n",
  1882. le32_to_cpu(newext->ee_block),
  1883. ext4_ext_pblock(newext),
  1884. ext4_ext_is_unwritten(newext),
  1885. ext4_ext_get_actual_len(newext),
  1886. len, nearex, nearex + 1);
  1887. memmove(nearex + 1, nearex,
  1888. len * sizeof(struct ext4_extent));
  1889. }
  1890. }
  1891. le16_add_cpu(&eh->eh_entries, 1);
  1892. path[depth].p_ext = nearex;
  1893. nearex->ee_block = newext->ee_block;
  1894. ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext));
  1895. nearex->ee_len = newext->ee_len;
  1896. merge:
  1897. /* try to merge extents */
  1898. if (!(gb_flags & EXT4_GET_BLOCKS_PRE_IO))
  1899. ext4_ext_try_to_merge(handle, inode, path, nearex);
  1900. /* time to correct all indexes above */
  1901. err = ext4_ext_correct_indexes(handle, inode, path);
  1902. if (err)
  1903. goto cleanup;
  1904. err = ext4_ext_dirty(handle, inode, path + path->p_depth);
  1905. cleanup:
  1906. ext4_ext_drop_refs(npath);
  1907. kfree(npath);
  1908. return err;
  1909. }
  1910. static int ext4_fill_es_cache_info(struct inode *inode,
  1911. ext4_lblk_t block, ext4_lblk_t num,
  1912. struct fiemap_extent_info *fieinfo)
  1913. {
  1914. ext4_lblk_t next, end = block + num - 1;
  1915. struct extent_status es;
  1916. unsigned char blksize_bits = inode->i_sb->s_blocksize_bits;
  1917. unsigned int flags;
  1918. int err;
  1919. while (block <= end) {
  1920. next = 0;
  1921. flags = 0;
  1922. if (!ext4_es_lookup_extent(inode, block, &next, &es))
  1923. break;
  1924. if (ext4_es_is_unwritten(&es))
  1925. flags |= FIEMAP_EXTENT_UNWRITTEN;
  1926. if (ext4_es_is_delayed(&es))
  1927. flags |= (FIEMAP_EXTENT_DELALLOC |
  1928. FIEMAP_EXTENT_UNKNOWN);
  1929. if (ext4_es_is_hole(&es))
  1930. flags |= EXT4_FIEMAP_EXTENT_HOLE;
  1931. if (next == 0)
  1932. flags |= FIEMAP_EXTENT_LAST;
  1933. if (flags & (FIEMAP_EXTENT_DELALLOC|
  1934. EXT4_FIEMAP_EXTENT_HOLE))
  1935. es.es_pblk = 0;
  1936. else
  1937. es.es_pblk = ext4_es_pblock(&es);
  1938. err = fiemap_fill_next_extent(fieinfo,
  1939. (__u64)es.es_lblk << blksize_bits,
  1940. (__u64)es.es_pblk << blksize_bits,
  1941. (__u64)es.es_len << blksize_bits,
  1942. flags);
  1943. if (next == 0)
  1944. break;
  1945. block = next;
  1946. if (err < 0)
  1947. return err;
  1948. if (err == 1)
  1949. return 0;
  1950. }
  1951. return 0;
  1952. }
  1953. /*
  1954. * ext4_ext_determine_hole - determine hole around given block
  1955. * @inode: inode we lookup in
  1956. * @path: path in extent tree to @lblk
  1957. * @lblk: pointer to logical block around which we want to determine hole
  1958. *
  1959. * Determine hole length (and start if easily possible) around given logical
  1960. * block. We don't try too hard to find the beginning of the hole but @path
  1961. * actually points to extent before @lblk, we provide it.
  1962. *
  1963. * The function returns the length of a hole starting at @lblk. We update @lblk
  1964. * to the beginning of the hole if we managed to find it.
  1965. */
  1966. static ext4_lblk_t ext4_ext_determine_hole(struct inode *inode,
  1967. struct ext4_ext_path *path,
  1968. ext4_lblk_t *lblk)
  1969. {
  1970. int depth = ext_depth(inode);
  1971. struct ext4_extent *ex;
  1972. ext4_lblk_t len;
  1973. ex = path[depth].p_ext;
  1974. if (ex == NULL) {
  1975. /* there is no extent yet, so gap is [0;-] */
  1976. *lblk = 0;
  1977. len = EXT_MAX_BLOCKS;
  1978. } else if (*lblk < le32_to_cpu(ex->ee_block)) {
  1979. len = le32_to_cpu(ex->ee_block) - *lblk;
  1980. } else if (*lblk >= le32_to_cpu(ex->ee_block)
  1981. + ext4_ext_get_actual_len(ex)) {
  1982. ext4_lblk_t next;
  1983. *lblk = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
  1984. next = ext4_ext_next_allocated_block(path);
  1985. BUG_ON(next == *lblk);
  1986. len = next - *lblk;
  1987. } else {
  1988. BUG();
  1989. }
  1990. return len;
  1991. }
  1992. /*
  1993. * ext4_ext_put_gap_in_cache:
  1994. * calculate boundaries of the gap that the requested block fits into
  1995. * and cache this gap
  1996. */
  1997. static void
  1998. ext4_ext_put_gap_in_cache(struct inode *inode, ext4_lblk_t hole_start,
  1999. ext4_lblk_t hole_len)
  2000. {
  2001. struct extent_status es;
  2002. ext4_es_find_extent_range(inode, &ext4_es_is_delayed, hole_start,
  2003. hole_start + hole_len - 1, &es);
  2004. if (es.es_len) {
  2005. /* There's delayed extent containing lblock? */
  2006. if (es.es_lblk <= hole_start)
  2007. return;
  2008. hole_len = min(es.es_lblk - hole_start, hole_len);
  2009. }
  2010. ext_debug(inode, " -> %u:%u\n", hole_start, hole_len);
  2011. ext4_es_insert_extent(inode, hole_start, hole_len, ~0,
  2012. EXTENT_STATUS_HOLE);
  2013. }
  2014. /*
  2015. * ext4_ext_rm_idx:
  2016. * removes index from the index block.
  2017. */
  2018. static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
  2019. struct ext4_ext_path *path, int depth)
  2020. {
  2021. int err;
  2022. ext4_fsblk_t leaf;
  2023. /* free index block */
  2024. depth--;
  2025. path = path + depth;
  2026. leaf = ext4_idx_pblock(path->p_idx);
  2027. if (unlikely(path->p_hdr->eh_entries == 0)) {
  2028. EXT4_ERROR_INODE(inode, "path->p_hdr->eh_entries == 0");
  2029. return -EFSCORRUPTED;
  2030. }
  2031. err = ext4_ext_get_access(handle, inode, path);
  2032. if (err)
  2033. return err;
  2034. if (path->p_idx != EXT_LAST_INDEX(path->p_hdr)) {
  2035. int len = EXT_LAST_INDEX(path->p_hdr) - path->p_idx;
  2036. len *= sizeof(struct ext4_extent_idx);
  2037. memmove(path->p_idx, path->p_idx + 1, len);
  2038. }
  2039. le16_add_cpu(&path->p_hdr->eh_entries, -1);
  2040. err = ext4_ext_dirty(handle, inode, path);
  2041. if (err)
  2042. return err;
  2043. ext_debug(inode, "index is empty, remove it, free block %llu\n", leaf);
  2044. trace_ext4_ext_rm_idx(inode, leaf);
  2045. ext4_free_blocks(handle, inode, NULL, leaf, 1,
  2046. EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
  2047. while (--depth >= 0) {
  2048. if (path->p_idx != EXT_FIRST_INDEX(path->p_hdr))
  2049. break;
  2050. path--;
  2051. err = ext4_ext_get_access(handle, inode, path);
  2052. if (err)
  2053. break;
  2054. path->p_idx->ei_block = (path+1)->p_idx->ei_block;
  2055. err = ext4_ext_dirty(handle, inode, path);
  2056. if (err)
  2057. break;
  2058. }
  2059. return err;
  2060. }
  2061. /*
  2062. * ext4_ext_calc_credits_for_single_extent:
  2063. * This routine returns max. credits that needed to insert an extent
  2064. * to the extent tree.
  2065. * When pass the actual path, the caller should calculate credits
  2066. * under i_data_sem.
  2067. */
  2068. int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
  2069. struct ext4_ext_path *path)
  2070. {
  2071. if (path) {
  2072. int depth = ext_depth(inode);
  2073. int ret = 0;
  2074. /* probably there is space in leaf? */
  2075. if (le16_to_cpu(path[depth].p_hdr->eh_entries)
  2076. < le16_to_cpu(path[depth].p_hdr->eh_max)) {
  2077. /*
  2078. * There are some space in the leaf tree, no
  2079. * need to account for leaf block credit
  2080. *
  2081. * bitmaps and block group descriptor blocks
  2082. * and other metadata blocks still need to be
  2083. * accounted.
  2084. */
  2085. /* 1 bitmap, 1 block group descriptor */
  2086. ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
  2087. return ret;
  2088. }
  2089. }
  2090. return ext4_chunk_trans_blocks(inode, nrblocks);
  2091. }
  2092. /*
  2093. * How many index/leaf blocks need to change/allocate to add @extents extents?
  2094. *
  2095. * If we add a single extent, then in the worse case, each tree level
  2096. * index/leaf need to be changed in case of the tree split.
  2097. *
  2098. * If more extents are inserted, they could cause the whole tree split more
  2099. * than once, but this is really rare.
  2100. */
  2101. int ext4_ext_index_trans_blocks(struct inode *inode, int extents)
  2102. {
  2103. int index;
  2104. int depth;
  2105. /* If we are converting the inline data, only one is needed here. */
  2106. if (ext4_has_inline_data(inode))
  2107. return 1;
  2108. depth = ext_depth(inode);
  2109. if (extents <= 1)
  2110. index = depth * 2;
  2111. else
  2112. index = depth * 3;
  2113. return index;
  2114. }
  2115. static inline int get_default_free_blocks_flags(struct inode *inode)
  2116. {
  2117. if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode) ||
  2118. ext4_test_inode_flag(inode, EXT4_INODE_EA_INODE))
  2119. return EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET;
  2120. else if (ext4_should_journal_data(inode))
  2121. return EXT4_FREE_BLOCKS_FORGET;
  2122. return 0;
  2123. }
  2124. /*
  2125. * ext4_rereserve_cluster - increment the reserved cluster count when
  2126. * freeing a cluster with a pending reservation
  2127. *
  2128. * @inode - file containing the cluster
  2129. * @lblk - logical block in cluster to be reserved
  2130. *
  2131. * Increments the reserved cluster count and adjusts quota in a bigalloc
  2132. * file system when freeing a partial cluster containing at least one
  2133. * delayed and unwritten block. A partial cluster meeting that
  2134. * requirement will have a pending reservation. If so, the
  2135. * RERESERVE_CLUSTER flag is used when calling ext4_free_blocks() to
  2136. * defer reserved and allocated space accounting to a subsequent call
  2137. * to this function.
  2138. */
  2139. static void ext4_rereserve_cluster(struct inode *inode, ext4_lblk_t lblk)
  2140. {
  2141. struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  2142. struct ext4_inode_info *ei = EXT4_I(inode);
  2143. dquot_reclaim_block(inode, EXT4_C2B(sbi, 1));
  2144. spin_lock(&ei->i_block_reservation_lock);
  2145. ei->i_reserved_data_blocks++;
  2146. percpu_counter_add(&sbi->s_dirtyclusters_counter, 1);
  2147. spin_unlock(&ei->i_block_reservation_lock);
  2148. percpu_counter_add(&sbi->s_freeclusters_counter, 1);
  2149. ext4_remove_pending(inode, lblk);
  2150. }
  2151. static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
  2152. struct ext4_extent *ex,
  2153. struct partial_cluster *partial,
  2154. ext4_lblk_t from, ext4_lblk_t to)
  2155. {
  2156. struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  2157. unsigned short ee_len = ext4_ext_get_actual_len(ex);
  2158. ext4_fsblk_t last_pblk, pblk;
  2159. ext4_lblk_t num;
  2160. int flags;
  2161. /* only extent tail removal is allowed */
  2162. if (from < le32_to_cpu(ex->ee_block) ||
  2163. to != le32_to_cpu(ex->ee_block) + ee_len - 1) {
  2164. ext4_error(sbi->s_sb,
  2165. "strange request: removal(2) %u-%u from %u:%u",
  2166. from, to, le32_to_cpu(ex->ee_block), ee_len);
  2167. return 0;
  2168. }
  2169. #ifdef EXTENTS_STATS
  2170. spin_lock(&sbi->s_ext_stats_lock);
  2171. sbi->s_ext_blocks += ee_len;
  2172. sbi->s_ext_extents++;
  2173. if (ee_len < sbi->s_ext_min)
  2174. sbi->s_ext_min = ee_len;
  2175. if (ee_len > sbi->s_ext_max)
  2176. sbi->s_ext_max = ee_len;
  2177. if (ext_depth(inode) > sbi->s_depth_max)
  2178. sbi->s_depth_max = ext_depth(inode);
  2179. spin_unlock(&sbi->s_ext_stats_lock);
  2180. #endif
  2181. trace_ext4_remove_blocks(inode, ex, from, to, partial);
  2182. /*
  2183. * if we have a partial cluster, and it's different from the
  2184. * cluster of the last block in the extent, we free it
  2185. */
  2186. last_pblk = ext4_ext_pblock(ex) + ee_len - 1;
  2187. if (partial->state != initial &&
  2188. partial->pclu != EXT4_B2C(sbi, last_pblk)) {
  2189. if (partial->state == tofree) {
  2190. flags = get_default_free_blocks_flags(inode);
  2191. if (ext4_is_pending(inode, partial->lblk))
  2192. flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
  2193. ext4_free_blocks(handle, inode, NULL,
  2194. EXT4_C2B(sbi, partial->pclu),
  2195. sbi->s_cluster_ratio, flags);
  2196. if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
  2197. ext4_rereserve_cluster(inode, partial->lblk);
  2198. }
  2199. partial->state = initial;
  2200. }
  2201. num = le32_to_cpu(ex->ee_block) + ee_len - from;
  2202. pblk = ext4_ext_pblock(ex) + ee_len - num;
  2203. /*
  2204. * We free the partial cluster at the end of the extent (if any),
  2205. * unless the cluster is used by another extent (partial_cluster
  2206. * state is nofree). If a partial cluster exists here, it must be
  2207. * shared with the last block in the extent.
  2208. */
  2209. flags = get_default_free_blocks_flags(inode);
  2210. /* partial, left end cluster aligned, right end unaligned */
  2211. if ((EXT4_LBLK_COFF(sbi, to) != sbi->s_cluster_ratio - 1) &&
  2212. (EXT4_LBLK_CMASK(sbi, to) >= from) &&
  2213. (partial->state != nofree)) {
  2214. if (ext4_is_pending(inode, to))
  2215. flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
  2216. ext4_free_blocks(handle, inode, NULL,
  2217. EXT4_PBLK_CMASK(sbi, last_pblk),
  2218. sbi->s_cluster_ratio, flags);
  2219. if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
  2220. ext4_rereserve_cluster(inode, to);
  2221. partial->state = initial;
  2222. flags = get_default_free_blocks_flags(inode);
  2223. }
  2224. flags |= EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER;
  2225. /*
  2226. * For bigalloc file systems, we never free a partial cluster
  2227. * at the beginning of the extent. Instead, we check to see if we
  2228. * need to free it on a subsequent call to ext4_remove_blocks,
  2229. * or at the end of ext4_ext_rm_leaf or ext4_ext_remove_space.
  2230. */
  2231. flags |= EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER;
  2232. ext4_free_blocks(handle, inode, NULL, pblk, num, flags);
  2233. /* reset the partial cluster if we've freed past it */
  2234. if (partial->state != initial && partial->pclu != EXT4_B2C(sbi, pblk))
  2235. partial->state = initial;
  2236. /*
  2237. * If we've freed the entire extent but the beginning is not left
  2238. * cluster aligned and is not marked as ineligible for freeing we
  2239. * record the partial cluster at the beginning of the extent. It
  2240. * wasn't freed by the preceding ext4_free_blocks() call, and we
  2241. * need to look farther to the left to determine if it's to be freed
  2242. * (not shared with another extent). Else, reset the partial
  2243. * cluster - we're either done freeing or the beginning of the
  2244. * extent is left cluster aligned.
  2245. */
  2246. if (EXT4_LBLK_COFF(sbi, from) && num == ee_len) {
  2247. if (partial->state == initial) {
  2248. partial->pclu = EXT4_B2C(sbi, pblk);
  2249. partial->lblk = from;
  2250. partial->state = tofree;
  2251. }
  2252. } else {
  2253. partial->state = initial;
  2254. }
  2255. return 0;
  2256. }
  2257. /*
  2258. * ext4_ext_rm_leaf() Removes the extents associated with the
  2259. * blocks appearing between "start" and "end". Both "start"
  2260. * and "end" must appear in the same extent or EIO is returned.
  2261. *
  2262. * @handle: The journal handle
  2263. * @inode: The files inode
  2264. * @path: The path to the leaf
  2265. * @partial_cluster: The cluster which we'll have to free if all extents
  2266. * has been released from it. However, if this value is
  2267. * negative, it's a cluster just to the right of the
  2268. * punched region and it must not be freed.
  2269. * @start: The first block to remove
  2270. * @end: The last block to remove
  2271. */
  2272. static int
  2273. ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
  2274. struct ext4_ext_path *path,
  2275. struct partial_cluster *partial,
  2276. ext4_lblk_t start, ext4_lblk_t end)
  2277. {
  2278. struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  2279. int err = 0, correct_index = 0;
  2280. int depth = ext_depth(inode), credits, revoke_credits;
  2281. struct ext4_extent_header *eh;
  2282. ext4_lblk_t a, b;
  2283. unsigned num;
  2284. ext4_lblk_t ex_ee_block;
  2285. unsigned short ex_ee_len;
  2286. unsigned unwritten = 0;
  2287. struct ext4_extent *ex;
  2288. ext4_fsblk_t pblk;
  2289. /* the header must be checked already in ext4_ext_remove_space() */
  2290. ext_debug(inode, "truncate since %u in leaf to %u\n", start, end);
  2291. if (!path[depth].p_hdr)
  2292. path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
  2293. eh = path[depth].p_hdr;
  2294. if (unlikely(path[depth].p_hdr == NULL)) {
  2295. EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
  2296. return -EFSCORRUPTED;
  2297. }
  2298. /* find where to start removing */
  2299. ex = path[depth].p_ext;
  2300. if (!ex)
  2301. ex = EXT_LAST_EXTENT(eh);
  2302. ex_ee_block = le32_to_cpu(ex->ee_block);
  2303. ex_ee_len = ext4_ext_get_actual_len(ex);
  2304. trace_ext4_ext_rm_leaf(inode, start, ex, partial);
  2305. while (ex >= EXT_FIRST_EXTENT(eh) &&
  2306. ex_ee_block + ex_ee_len > start) {
  2307. if (ext4_ext_is_unwritten(ex))
  2308. unwritten = 1;
  2309. else
  2310. unwritten = 0;
  2311. ext_debug(inode, "remove ext %u:[%d]%d\n", ex_ee_block,
  2312. unwritten, ex_ee_len);
  2313. path[depth].p_ext = ex;
  2314. a = ex_ee_block > start ? ex_ee_block : start;
  2315. b = ex_ee_block+ex_ee_len - 1 < end ?
  2316. ex_ee_block+ex_ee_len - 1 : end;
  2317. ext_debug(inode, " border %u:%u\n", a, b);
  2318. /* If this extent is beyond the end of the hole, skip it */
  2319. if (end < ex_ee_block) {
  2320. /*
  2321. * We're going to skip this extent and move to another,
  2322. * so note that its first cluster is in use to avoid
  2323. * freeing it when removing blocks. Eventually, the
  2324. * right edge of the truncated/punched region will
  2325. * be just to the left.
  2326. */
  2327. if (sbi->s_cluster_ratio > 1) {
  2328. pblk = ext4_ext_pblock(ex);
  2329. partial->pclu = EXT4_B2C(sbi, pblk);
  2330. partial->state = nofree;
  2331. }
  2332. ex--;
  2333. ex_ee_block = le32_to_cpu(ex->ee_block);
  2334. ex_ee_len = ext4_ext_get_actual_len(ex);
  2335. continue;
  2336. } else if (b != ex_ee_block + ex_ee_len - 1) {
  2337. EXT4_ERROR_INODE(inode,
  2338. "can not handle truncate %u:%u "
  2339. "on extent %u:%u",
  2340. start, end, ex_ee_block,
  2341. ex_ee_block + ex_ee_len - 1);
  2342. err = -EFSCORRUPTED;
  2343. goto out;
  2344. } else if (a != ex_ee_block) {
  2345. /* remove tail of the extent */
  2346. num = a - ex_ee_block;
  2347. } else {
  2348. /* remove whole extent: excellent! */
  2349. num = 0;
  2350. }
  2351. /*
  2352. * 3 for leaf, sb, and inode plus 2 (bmap and group
  2353. * descriptor) for each block group; assume two block
  2354. * groups plus ex_ee_len/blocks_per_block_group for
  2355. * the worst case
  2356. */
  2357. credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
  2358. if (ex == EXT_FIRST_EXTENT(eh)) {
  2359. correct_index = 1;
  2360. credits += (ext_depth(inode)) + 1;
  2361. }
  2362. credits += EXT4_MAXQUOTAS_TRANS_BLOCKS(inode->i_sb);
  2363. /*
  2364. * We may end up freeing some index blocks and data from the
  2365. * punched range. Note that partial clusters are accounted for
  2366. * by ext4_free_data_revoke_credits().
  2367. */
  2368. revoke_credits =
  2369. ext4_free_metadata_revoke_credits(inode->i_sb,
  2370. ext_depth(inode)) +
  2371. ext4_free_data_revoke_credits(inode, b - a + 1);
  2372. err = ext4_datasem_ensure_credits(handle, inode, credits,
  2373. credits, revoke_credits);
  2374. if (err) {
  2375. if (err > 0)
  2376. err = -EAGAIN;
  2377. goto out;
  2378. }
  2379. err = ext4_ext_get_access(handle, inode, path + depth);
  2380. if (err)
  2381. goto out;
  2382. err = ext4_remove_blocks(handle, inode, ex, partial, a, b);
  2383. if (err)
  2384. goto out;
  2385. if (num == 0)
  2386. /* this extent is removed; mark slot entirely unused */
  2387. ext4_ext_store_pblock(ex, 0);
  2388. ex->ee_len = cpu_to_le16(num);
  2389. /*
  2390. * Do not mark unwritten if all the blocks in the
  2391. * extent have been removed.
  2392. */
  2393. if (unwritten && num)
  2394. ext4_ext_mark_unwritten(ex);
  2395. /*
  2396. * If the extent was completely released,
  2397. * we need to remove it from the leaf
  2398. */
  2399. if (num == 0) {
  2400. if (end != EXT_MAX_BLOCKS - 1) {
  2401. /*
  2402. * For hole punching, we need to scoot all the
  2403. * extents up when an extent is removed so that
  2404. * we dont have blank extents in the middle
  2405. */
  2406. memmove(ex, ex+1, (EXT_LAST_EXTENT(eh) - ex) *
  2407. sizeof(struct ext4_extent));
  2408. /* Now get rid of the one at the end */
  2409. memset(EXT_LAST_EXTENT(eh), 0,
  2410. sizeof(struct ext4_extent));
  2411. }
  2412. le16_add_cpu(&eh->eh_entries, -1);
  2413. }
  2414. err = ext4_ext_dirty(handle, inode, path + depth);
  2415. if (err)
  2416. goto out;
  2417. ext_debug(inode, "new extent: %u:%u:%llu\n", ex_ee_block, num,
  2418. ext4_ext_pblock(ex));
  2419. ex--;
  2420. ex_ee_block = le32_to_cpu(ex->ee_block);
  2421. ex_ee_len = ext4_ext_get_actual_len(ex);
  2422. }
  2423. if (correct_index && eh->eh_entries)
  2424. err = ext4_ext_correct_indexes(handle, inode, path);
  2425. /*
  2426. * If there's a partial cluster and at least one extent remains in
  2427. * the leaf, free the partial cluster if it isn't shared with the
  2428. * current extent. If it is shared with the current extent
  2429. * we reset the partial cluster because we've reached the start of the
  2430. * truncated/punched region and we're done removing blocks.
  2431. */
  2432. if (partial->state == tofree && ex >= EXT_FIRST_EXTENT(eh)) {
  2433. pblk = ext4_ext_pblock(ex) + ex_ee_len - 1;
  2434. if (partial->pclu != EXT4_B2C(sbi, pblk)) {
  2435. int flags = get_default_free_blocks_flags(inode);
  2436. if (ext4_is_pending(inode, partial->lblk))
  2437. flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
  2438. ext4_free_blocks(handle, inode, NULL,
  2439. EXT4_C2B(sbi, partial->pclu),
  2440. sbi->s_cluster_ratio, flags);
  2441. if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
  2442. ext4_rereserve_cluster(inode, partial->lblk);
  2443. }
  2444. partial->state = initial;
  2445. }
  2446. /* if this leaf is free, then we should
  2447. * remove it from index block above */
  2448. if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
  2449. err = ext4_ext_rm_idx(handle, inode, path, depth);
  2450. out:
  2451. return err;
  2452. }
  2453. /*
  2454. * ext4_ext_more_to_rm:
  2455. * returns 1 if current index has to be freed (even partial)
  2456. */
  2457. static int
  2458. ext4_ext_more_to_rm(struct ext4_ext_path *path)
  2459. {
  2460. BUG_ON(path->p_idx == NULL);
  2461. if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
  2462. return 0;
  2463. /*
  2464. * if truncate on deeper level happened, it wasn't partial,
  2465. * so we have to consider current index for truncation
  2466. */
  2467. if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
  2468. return 0;
  2469. return 1;
  2470. }
  2471. int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start,
  2472. ext4_lblk_t end)
  2473. {
  2474. struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  2475. int depth = ext_depth(inode);
  2476. struct ext4_ext_path *path = NULL;
  2477. struct partial_cluster partial;
  2478. handle_t *handle;
  2479. int i = 0, err = 0;
  2480. partial.pclu = 0;
  2481. partial.lblk = 0;
  2482. partial.state = initial;
  2483. ext_debug(inode, "truncate since %u to %u\n", start, end);
  2484. /* probably first extent we're gonna free will be last in block */
  2485. handle = ext4_journal_start_with_revoke(inode, EXT4_HT_TRUNCATE,
  2486. depth + 1,
  2487. ext4_free_metadata_revoke_credits(inode->i_sb, depth));
  2488. if (IS_ERR(handle))
  2489. return PTR_ERR(handle);
  2490. again:
  2491. trace_ext4_ext_remove_space(inode, start, end, depth);
  2492. /*
  2493. * Check if we are removing extents inside the extent tree. If that
  2494. * is the case, we are going to punch a hole inside the extent tree
  2495. * so we have to check whether we need to split the extent covering
  2496. * the last block to remove so we can easily remove the part of it
  2497. * in ext4_ext_rm_leaf().
  2498. */
  2499. if (end < EXT_MAX_BLOCKS - 1) {
  2500. struct ext4_extent *ex;
  2501. ext4_lblk_t ee_block, ex_end, lblk;
  2502. ext4_fsblk_t pblk;
  2503. /* find extent for or closest extent to this block */
  2504. path = ext4_find_extent(inode, end, NULL,
  2505. EXT4_EX_NOCACHE | EXT4_EX_NOFAIL);
  2506. if (IS_ERR(path)) {
  2507. ext4_journal_stop(handle);
  2508. return PTR_ERR(path);
  2509. }
  2510. depth = ext_depth(inode);
  2511. /* Leaf not may not exist only if inode has no blocks at all */
  2512. ex = path[depth].p_ext;
  2513. if (!ex) {
  2514. if (depth) {
  2515. EXT4_ERROR_INODE(inode,
  2516. "path[%d].p_hdr == NULL",
  2517. depth);
  2518. err = -EFSCORRUPTED;
  2519. }
  2520. goto out;
  2521. }
  2522. ee_block = le32_to_cpu(ex->ee_block);
  2523. ex_end = ee_block + ext4_ext_get_actual_len(ex) - 1;
  2524. /*
  2525. * See if the last block is inside the extent, if so split
  2526. * the extent at 'end' block so we can easily remove the
  2527. * tail of the first part of the split extent in
  2528. * ext4_ext_rm_leaf().
  2529. */
  2530. if (end >= ee_block && end < ex_end) {
  2531. /*
  2532. * If we're going to split the extent, note that
  2533. * the cluster containing the block after 'end' is
  2534. * in use to avoid freeing it when removing blocks.
  2535. */
  2536. if (sbi->s_cluster_ratio > 1) {
  2537. pblk = ext4_ext_pblock(ex) + end - ee_block + 1;
  2538. partial.pclu = EXT4_B2C(sbi, pblk);
  2539. partial.state = nofree;
  2540. }
  2541. /*
  2542. * Split the extent in two so that 'end' is the last
  2543. * block in the first new extent. Also we should not
  2544. * fail removing space due to ENOSPC so try to use
  2545. * reserved block if that happens.
  2546. */
  2547. err = ext4_force_split_extent_at(handle, inode, &path,
  2548. end + 1, 1);
  2549. if (err < 0)
  2550. goto out;
  2551. } else if (sbi->s_cluster_ratio > 1 && end >= ex_end &&
  2552. partial.state == initial) {
  2553. /*
  2554. * If we're punching, there's an extent to the right.
  2555. * If the partial cluster hasn't been set, set it to
  2556. * that extent's first cluster and its state to nofree
  2557. * so it won't be freed should it contain blocks to be
  2558. * removed. If it's already set (tofree/nofree), we're
  2559. * retrying and keep the original partial cluster info
  2560. * so a cluster marked tofree as a result of earlier
  2561. * extent removal is not lost.
  2562. */
  2563. lblk = ex_end + 1;
  2564. err = ext4_ext_search_right(inode, path, &lblk, &pblk,
  2565. NULL);
  2566. if (err < 0)
  2567. goto out;
  2568. if (pblk) {
  2569. partial.pclu = EXT4_B2C(sbi, pblk);
  2570. partial.state = nofree;
  2571. }
  2572. }
  2573. }
  2574. /*
  2575. * We start scanning from right side, freeing all the blocks
  2576. * after i_size and walking into the tree depth-wise.
  2577. */
  2578. depth = ext_depth(inode);
  2579. if (path) {
  2580. int k = i = depth;
  2581. while (--k > 0)
  2582. path[k].p_block =
  2583. le16_to_cpu(path[k].p_hdr->eh_entries)+1;
  2584. } else {
  2585. path = kcalloc(depth + 1, sizeof(struct ext4_ext_path),
  2586. GFP_NOFS | __GFP_NOFAIL);
  2587. if (path == NULL) {
  2588. ext4_journal_stop(handle);
  2589. return -ENOMEM;
  2590. }
  2591. path[0].p_maxdepth = path[0].p_depth = depth;
  2592. path[0].p_hdr = ext_inode_hdr(inode);
  2593. i = 0;
  2594. if (ext4_ext_check(inode, path[0].p_hdr, depth, 0)) {
  2595. err = -EFSCORRUPTED;
  2596. goto out;
  2597. }
  2598. }
  2599. err = 0;
  2600. while (i >= 0 && err == 0) {
  2601. if (i == depth) {
  2602. /* this is leaf block */
  2603. err = ext4_ext_rm_leaf(handle, inode, path,
  2604. &partial, start, end);
  2605. /* root level has p_bh == NULL, brelse() eats this */
  2606. brelse(path[i].p_bh);
  2607. path[i].p_bh = NULL;
  2608. i--;
  2609. continue;
  2610. }
  2611. /* this is index block */
  2612. if (!path[i].p_hdr) {
  2613. ext_debug(inode, "initialize header\n");
  2614. path[i].p_hdr = ext_block_hdr(path[i].p_bh);
  2615. }
  2616. if (!path[i].p_idx) {
  2617. /* this level hasn't been touched yet */
  2618. path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
  2619. path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
  2620. ext_debug(inode, "init index ptr: hdr 0x%p, num %d\n",
  2621. path[i].p_hdr,
  2622. le16_to_cpu(path[i].p_hdr->eh_entries));
  2623. } else {
  2624. /* we were already here, see at next index */
  2625. path[i].p_idx--;
  2626. }
  2627. ext_debug(inode, "level %d - index, first 0x%p, cur 0x%p\n",
  2628. i, EXT_FIRST_INDEX(path[i].p_hdr),
  2629. path[i].p_idx);
  2630. if (ext4_ext_more_to_rm(path + i)) {
  2631. struct buffer_head *bh;
  2632. /* go to the next level */
  2633. ext_debug(inode, "move to level %d (block %llu)\n",
  2634. i + 1, ext4_idx_pblock(path[i].p_idx));
  2635. memset(path + i + 1, 0, sizeof(*path));
  2636. bh = read_extent_tree_block(inode, path[i].p_idx,
  2637. depth - i - 1,
  2638. EXT4_EX_NOCACHE);
  2639. if (IS_ERR(bh)) {
  2640. /* should we reset i_size? */
  2641. err = PTR_ERR(bh);
  2642. break;
  2643. }
  2644. /* Yield here to deal with large extent trees.
  2645. * Should be a no-op if we did IO above. */
  2646. cond_resched();
  2647. if (WARN_ON(i + 1 > depth)) {
  2648. err = -EFSCORRUPTED;
  2649. break;
  2650. }
  2651. path[i + 1].p_bh = bh;
  2652. /* save actual number of indexes since this
  2653. * number is changed at the next iteration */
  2654. path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
  2655. i++;
  2656. } else {
  2657. /* we finished processing this index, go up */
  2658. if (path[i].p_hdr->eh_entries == 0 && i > 0) {
  2659. /* index is empty, remove it;
  2660. * handle must be already prepared by the
  2661. * truncatei_leaf() */
  2662. err = ext4_ext_rm_idx(handle, inode, path, i);
  2663. }
  2664. /* root level has p_bh == NULL, brelse() eats this */
  2665. brelse(path[i].p_bh);
  2666. path[i].p_bh = NULL;
  2667. i--;
  2668. ext_debug(inode, "return to level %d\n", i);
  2669. }
  2670. }
  2671. trace_ext4_ext_remove_space_done(inode, start, end, depth, &partial,
  2672. path->p_hdr->eh_entries);
  2673. /*
  2674. * if there's a partial cluster and we have removed the first extent
  2675. * in the file, then we also free the partial cluster, if any
  2676. */
  2677. if (partial.state == tofree && err == 0) {
  2678. int flags = get_default_free_blocks_flags(inode);
  2679. if (ext4_is_pending(inode, partial.lblk))
  2680. flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
  2681. ext4_free_blocks(handle, inode, NULL,
  2682. EXT4_C2B(sbi, partial.pclu),
  2683. sbi->s_cluster_ratio, flags);
  2684. if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
  2685. ext4_rereserve_cluster(inode, partial.lblk);
  2686. partial.state = initial;
  2687. }
  2688. /* TODO: flexible tree reduction should be here */
  2689. if (path->p_hdr->eh_entries == 0) {
  2690. /*
  2691. * truncate to zero freed all the tree,
  2692. * so we need to correct eh_depth
  2693. */
  2694. err = ext4_ext_get_access(handle, inode, path);
  2695. if (err == 0) {
  2696. ext_inode_hdr(inode)->eh_depth = 0;
  2697. ext_inode_hdr(inode)->eh_max =
  2698. cpu_to_le16(ext4_ext_space_root(inode, 0));
  2699. err = ext4_ext_dirty(handle, inode, path);
  2700. }
  2701. }
  2702. out:
  2703. ext4_ext_drop_refs(path);
  2704. kfree(path);
  2705. path = NULL;
  2706. if (err == -EAGAIN)
  2707. goto again;
  2708. ext4_journal_stop(handle);
  2709. return err;
  2710. }
  2711. /*
  2712. * called at mount time
  2713. */
  2714. void ext4_ext_init(struct super_block *sb)
  2715. {
  2716. /*
  2717. * possible initialization would be here
  2718. */
  2719. if (ext4_has_feature_extents(sb)) {
  2720. #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
  2721. printk(KERN_INFO "EXT4-fs: file extents enabled"
  2722. #ifdef AGGRESSIVE_TEST
  2723. ", aggressive tests"
  2724. #endif
  2725. #ifdef CHECK_BINSEARCH
  2726. ", check binsearch"
  2727. #endif
  2728. #ifdef EXTENTS_STATS
  2729. ", stats"
  2730. #endif
  2731. "\n");
  2732. #endif
  2733. #ifdef EXTENTS_STATS
  2734. spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
  2735. EXT4_SB(sb)->s_ext_min = 1 << 30;
  2736. EXT4_SB(sb)->s_ext_max = 0;
  2737. #endif
  2738. }
  2739. }
  2740. /*
  2741. * called at umount time
  2742. */
  2743. void ext4_ext_release(struct super_block *sb)
  2744. {
  2745. if (!ext4_has_feature_extents(sb))
  2746. return;
  2747. #ifdef EXTENTS_STATS
  2748. if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
  2749. struct ext4_sb_info *sbi = EXT4_SB(sb);
  2750. printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
  2751. sbi->s_ext_blocks, sbi->s_ext_extents,
  2752. sbi->s_ext_blocks / sbi->s_ext_extents);
  2753. printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
  2754. sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
  2755. }
  2756. #endif
  2757. }
  2758. static int ext4_zeroout_es(struct inode *inode, struct ext4_extent *ex)
  2759. {
  2760. ext4_lblk_t ee_block;
  2761. ext4_fsblk_t ee_pblock;
  2762. unsigned int ee_len;
  2763. ee_block = le32_to_cpu(ex->ee_block);
  2764. ee_len = ext4_ext_get_actual_len(ex);
  2765. ee_pblock = ext4_ext_pblock(ex);
  2766. if (ee_len == 0)
  2767. return 0;
  2768. return ext4_es_insert_extent(inode, ee_block, ee_len, ee_pblock,
  2769. EXTENT_STATUS_WRITTEN);
  2770. }
  2771. /* FIXME!! we need to try to merge to left or right after zero-out */
  2772. static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
  2773. {
  2774. ext4_fsblk_t ee_pblock;
  2775. unsigned int ee_len;
  2776. ee_len = ext4_ext_get_actual_len(ex);
  2777. ee_pblock = ext4_ext_pblock(ex);
  2778. return ext4_issue_zeroout(inode, le32_to_cpu(ex->ee_block), ee_pblock,
  2779. ee_len);
  2780. }
  2781. /*
  2782. * ext4_split_extent_at() splits an extent at given block.
  2783. *
  2784. * @handle: the journal handle
  2785. * @inode: the file inode
  2786. * @path: the path to the extent
  2787. * @split: the logical block where the extent is splitted.
  2788. * @split_flags: indicates if the extent could be zeroout if split fails, and
  2789. * the states(init or unwritten) of new extents.
  2790. * @flags: flags used to insert new extent to extent tree.
  2791. *
  2792. *
  2793. * Splits extent [a, b] into two extents [a, @split) and [@split, b], states
  2794. * of which are determined by split_flag.
  2795. *
  2796. * There are two cases:
  2797. * a> the extent are splitted into two extent.
  2798. * b> split is not needed, and just mark the extent.
  2799. *
  2800. * return 0 on success.
  2801. */
  2802. static int ext4_split_extent_at(handle_t *handle,
  2803. struct inode *inode,
  2804. struct ext4_ext_path **ppath,
  2805. ext4_lblk_t split,
  2806. int split_flag,
  2807. int flags)
  2808. {
  2809. struct ext4_ext_path *path = *ppath;
  2810. ext4_fsblk_t newblock;
  2811. ext4_lblk_t ee_block;
  2812. struct ext4_extent *ex, newex, orig_ex, zero_ex;
  2813. struct ext4_extent *ex2 = NULL;
  2814. unsigned int ee_len, depth;
  2815. int err = 0;
  2816. BUG_ON((split_flag & (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2)) ==
  2817. (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2));
  2818. ext_debug(inode, "logical block %llu\n", (unsigned long long)split);
  2819. ext4_ext_show_leaf(inode, path);
  2820. depth = ext_depth(inode);
  2821. ex = path[depth].p_ext;
  2822. ee_block = le32_to_cpu(ex->ee_block);
  2823. ee_len = ext4_ext_get_actual_len(ex);
  2824. newblock = split - ee_block + ext4_ext_pblock(ex);
  2825. BUG_ON(split < ee_block || split >= (ee_block + ee_len));
  2826. BUG_ON(!ext4_ext_is_unwritten(ex) &&
  2827. split_flag & (EXT4_EXT_MAY_ZEROOUT |
  2828. EXT4_EXT_MARK_UNWRIT1 |
  2829. EXT4_EXT_MARK_UNWRIT2));
  2830. err = ext4_ext_get_access(handle, inode, path + depth);
  2831. if (err)
  2832. goto out;
  2833. if (split == ee_block) {
  2834. /*
  2835. * case b: block @split is the block that the extent begins with
  2836. * then we just change the state of the extent, and splitting
  2837. * is not needed.
  2838. */
  2839. if (split_flag & EXT4_EXT_MARK_UNWRIT2)
  2840. ext4_ext_mark_unwritten(ex);
  2841. else
  2842. ext4_ext_mark_initialized(ex);
  2843. if (!(flags & EXT4_GET_BLOCKS_PRE_IO))
  2844. ext4_ext_try_to_merge(handle, inode, path, ex);
  2845. err = ext4_ext_dirty(handle, inode, path + path->p_depth);
  2846. goto out;
  2847. }
  2848. /* case a */
  2849. memcpy(&orig_ex, ex, sizeof(orig_ex));
  2850. ex->ee_len = cpu_to_le16(split - ee_block);
  2851. if (split_flag & EXT4_EXT_MARK_UNWRIT1)
  2852. ext4_ext_mark_unwritten(ex);
  2853. /*
  2854. * path may lead to new leaf, not to original leaf any more
  2855. * after ext4_ext_insert_extent() returns,
  2856. */
  2857. err = ext4_ext_dirty(handle, inode, path + depth);
  2858. if (err)
  2859. goto fix_extent_len;
  2860. ex2 = &newex;
  2861. ex2->ee_block = cpu_to_le32(split);
  2862. ex2->ee_len = cpu_to_le16(ee_len - (split - ee_block));
  2863. ext4_ext_store_pblock(ex2, newblock);
  2864. if (split_flag & EXT4_EXT_MARK_UNWRIT2)
  2865. ext4_ext_mark_unwritten(ex2);
  2866. err = ext4_ext_insert_extent(handle, inode, ppath, &newex, flags);
  2867. if (err != -ENOSPC && err != -EDQUOT)
  2868. goto out;
  2869. if (EXT4_EXT_MAY_ZEROOUT & split_flag) {
  2870. if (split_flag & (EXT4_EXT_DATA_VALID1|EXT4_EXT_DATA_VALID2)) {
  2871. if (split_flag & EXT4_EXT_DATA_VALID1) {
  2872. err = ext4_ext_zeroout(inode, ex2);
  2873. zero_ex.ee_block = ex2->ee_block;
  2874. zero_ex.ee_len = cpu_to_le16(
  2875. ext4_ext_get_actual_len(ex2));
  2876. ext4_ext_store_pblock(&zero_ex,
  2877. ext4_ext_pblock(ex2));
  2878. } else {
  2879. err = ext4_ext_zeroout(inode, ex);
  2880. zero_ex.ee_block = ex->ee_block;
  2881. zero_ex.ee_len = cpu_to_le16(
  2882. ext4_ext_get_actual_len(ex));
  2883. ext4_ext_store_pblock(&zero_ex,
  2884. ext4_ext_pblock(ex));
  2885. }
  2886. } else {
  2887. err = ext4_ext_zeroout(inode, &orig_ex);
  2888. zero_ex.ee_block = orig_ex.ee_block;
  2889. zero_ex.ee_len = cpu_to_le16(
  2890. ext4_ext_get_actual_len(&orig_ex));
  2891. ext4_ext_store_pblock(&zero_ex,
  2892. ext4_ext_pblock(&orig_ex));
  2893. }
  2894. if (!err) {
  2895. /* update the extent length and mark as initialized */
  2896. ex->ee_len = cpu_to_le16(ee_len);
  2897. ext4_ext_try_to_merge(handle, inode, path, ex);
  2898. err = ext4_ext_dirty(handle, inode, path + path->p_depth);
  2899. if (!err)
  2900. /* update extent status tree */
  2901. err = ext4_zeroout_es(inode, &zero_ex);
  2902. /* If we failed at this point, we don't know in which
  2903. * state the extent tree exactly is so don't try to fix
  2904. * length of the original extent as it may do even more
  2905. * damage.
  2906. */
  2907. goto out;
  2908. }
  2909. }
  2910. fix_extent_len:
  2911. ex->ee_len = orig_ex.ee_len;
  2912. /*
  2913. * Ignore ext4_ext_dirty return value since we are already in error path
  2914. * and err is a non-zero error code.
  2915. */
  2916. ext4_ext_dirty(handle, inode, path + path->p_depth);
  2917. return err;
  2918. out:
  2919. ext4_ext_show_leaf(inode, path);
  2920. return err;
  2921. }
  2922. /*
  2923. * ext4_split_extents() splits an extent and mark extent which is covered
  2924. * by @map as split_flags indicates
  2925. *
  2926. * It may result in splitting the extent into multiple extents (up to three)
  2927. * There are three possibilities:
  2928. * a> There is no split required
  2929. * b> Splits in two extents: Split is happening at either end of the extent
  2930. * c> Splits in three extents: Somone is splitting in middle of the extent
  2931. *
  2932. */
  2933. static int ext4_split_extent(handle_t *handle,
  2934. struct inode *inode,
  2935. struct ext4_ext_path **ppath,
  2936. struct ext4_map_blocks *map,
  2937. int split_flag,
  2938. int flags)
  2939. {
  2940. struct ext4_ext_path *path = *ppath;
  2941. ext4_lblk_t ee_block;
  2942. struct ext4_extent *ex;
  2943. unsigned int ee_len, depth;
  2944. int err = 0;
  2945. int unwritten;
  2946. int split_flag1, flags1;
  2947. int allocated = map->m_len;
  2948. depth = ext_depth(inode);
  2949. ex = path[depth].p_ext;
  2950. ee_block = le32_to_cpu(ex->ee_block);
  2951. ee_len = ext4_ext_get_actual_len(ex);
  2952. unwritten = ext4_ext_is_unwritten(ex);
  2953. if (map->m_lblk + map->m_len < ee_block + ee_len) {
  2954. split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT;
  2955. flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;
  2956. if (unwritten)
  2957. split_flag1 |= EXT4_EXT_MARK_UNWRIT1 |
  2958. EXT4_EXT_MARK_UNWRIT2;
  2959. if (split_flag & EXT4_EXT_DATA_VALID2)
  2960. split_flag1 |= EXT4_EXT_DATA_VALID1;
  2961. err = ext4_split_extent_at(handle, inode, ppath,
  2962. map->m_lblk + map->m_len, split_flag1, flags1);
  2963. if (err)
  2964. goto out;
  2965. } else {
  2966. allocated = ee_len - (map->m_lblk - ee_block);
  2967. }
  2968. /*
  2969. * Update path is required because previous ext4_split_extent_at() may
  2970. * result in split of original leaf or extent zeroout.
  2971. */
  2972. path = ext4_find_extent(inode, map->m_lblk, ppath, flags);
  2973. if (IS_ERR(path))
  2974. return PTR_ERR(path);
  2975. depth = ext_depth(inode);
  2976. ex = path[depth].p_ext;
  2977. if (!ex) {
  2978. EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
  2979. (unsigned long) map->m_lblk);
  2980. return -EFSCORRUPTED;
  2981. }
  2982. unwritten = ext4_ext_is_unwritten(ex);
  2983. split_flag1 = 0;
  2984. if (map->m_lblk >= ee_block) {
  2985. split_flag1 = split_flag & EXT4_EXT_DATA_VALID2;
  2986. if (unwritten) {
  2987. split_flag1 |= EXT4_EXT_MARK_UNWRIT1;
  2988. split_flag1 |= split_flag & (EXT4_EXT_MAY_ZEROOUT |
  2989. EXT4_EXT_MARK_UNWRIT2);
  2990. }
  2991. err = ext4_split_extent_at(handle, inode, ppath,
  2992. map->m_lblk, split_flag1, flags);
  2993. if (err)
  2994. goto out;
  2995. }
  2996. ext4_ext_show_leaf(inode, path);
  2997. out:
  2998. return err ? err : allocated;
  2999. }
  3000. /*
  3001. * This function is called by ext4_ext_map_blocks() if someone tries to write
  3002. * to an unwritten extent. It may result in splitting the unwritten
  3003. * extent into multiple extents (up to three - one initialized and two
  3004. * unwritten).
  3005. * There are three possibilities:
  3006. * a> There is no split required: Entire extent should be initialized
  3007. * b> Splits in two extents: Write is happening at either end of the extent
  3008. * c> Splits in three extents: Somone is writing in middle of the extent
  3009. *
  3010. * Pre-conditions:
  3011. * - The extent pointed to by 'path' is unwritten.
  3012. * - The extent pointed to by 'path' contains a superset
  3013. * of the logical span [map->m_lblk, map->m_lblk + map->m_len).
  3014. *
  3015. * Post-conditions on success:
  3016. * - the returned value is the number of blocks beyond map->l_lblk
  3017. * that are allocated and initialized.
  3018. * It is guaranteed to be >= map->m_len.
  3019. */
  3020. static int ext4_ext_convert_to_initialized(handle_t *handle,
  3021. struct inode *inode,
  3022. struct ext4_map_blocks *map,
  3023. struct ext4_ext_path **ppath,
  3024. int flags)
  3025. {
  3026. struct ext4_ext_path *path = *ppath;
  3027. struct ext4_sb_info *sbi;
  3028. struct ext4_extent_header *eh;
  3029. struct ext4_map_blocks split_map;
  3030. struct ext4_extent zero_ex1, zero_ex2;
  3031. struct ext4_extent *ex, *abut_ex;
  3032. ext4_lblk_t ee_block, eof_block;
  3033. unsigned int ee_len, depth, map_len = map->m_len;
  3034. int allocated = 0, max_zeroout = 0;
  3035. int err = 0;
  3036. int split_flag = EXT4_EXT_DATA_VALID2;
  3037. ext_debug(inode, "logical block %llu, max_blocks %u\n",
  3038. (unsigned long long)map->m_lblk, map_len);
  3039. sbi = EXT4_SB(inode->i_sb);
  3040. eof_block = (EXT4_I(inode)->i_disksize + inode->i_sb->s_blocksize - 1)
  3041. >> inode->i_sb->s_blocksize_bits;
  3042. if (eof_block < map->m_lblk + map_len)
  3043. eof_block = map->m_lblk + map_len;
  3044. depth = ext_depth(inode);
  3045. eh = path[depth].p_hdr;
  3046. ex = path[depth].p_ext;
  3047. ee_block = le32_to_cpu(ex->ee_block);
  3048. ee_len = ext4_ext_get_actual_len(ex);
  3049. zero_ex1.ee_len = 0;
  3050. zero_ex2.ee_len = 0;
  3051. trace_ext4_ext_convert_to_initialized_enter(inode, map, ex);
  3052. /* Pre-conditions */
  3053. BUG_ON(!ext4_ext_is_unwritten(ex));
  3054. BUG_ON(!in_range(map->m_lblk, ee_block, ee_len));
  3055. /*
  3056. * Attempt to transfer newly initialized blocks from the currently
  3057. * unwritten extent to its neighbor. This is much cheaper
  3058. * than an insertion followed by a merge as those involve costly
  3059. * memmove() calls. Transferring to the left is the common case in
  3060. * steady state for workloads doing fallocate(FALLOC_FL_KEEP_SIZE)
  3061. * followed by append writes.
  3062. *
  3063. * Limitations of the current logic:
  3064. * - L1: we do not deal with writes covering the whole extent.
  3065. * This would require removing the extent if the transfer
  3066. * is possible.
  3067. * - L2: we only attempt to merge with an extent stored in the
  3068. * same extent tree node.
  3069. */
  3070. if ((map->m_lblk == ee_block) &&
  3071. /* See if we can merge left */
  3072. (map_len < ee_len) && /*L1*/
  3073. (ex > EXT_FIRST_EXTENT(eh))) { /*L2*/
  3074. ext4_lblk_t prev_lblk;
  3075. ext4_fsblk_t prev_pblk, ee_pblk;
  3076. unsigned int prev_len;
  3077. abut_ex = ex - 1;
  3078. prev_lblk = le32_to_cpu(abut_ex->ee_block);
  3079. prev_len = ext4_ext_get_actual_len(abut_ex);
  3080. prev_pblk = ext4_ext_pblock(abut_ex);
  3081. ee_pblk = ext4_ext_pblock(ex);
  3082. /*
  3083. * A transfer of blocks from 'ex' to 'abut_ex' is allowed
  3084. * upon those conditions:
  3085. * - C1: abut_ex is initialized,
  3086. * - C2: abut_ex is logically abutting ex,
  3087. * - C3: abut_ex is physically abutting ex,
  3088. * - C4: abut_ex can receive the additional blocks without
  3089. * overflowing the (initialized) length limit.
  3090. */
  3091. if ((!ext4_ext_is_unwritten(abut_ex)) && /*C1*/
  3092. ((prev_lblk + prev_len) == ee_block) && /*C2*/
  3093. ((prev_pblk + prev_len) == ee_pblk) && /*C3*/
  3094. (prev_len < (EXT_INIT_MAX_LEN - map_len))) { /*C4*/
  3095. err = ext4_ext_get_access(handle, inode, path + depth);
  3096. if (err)
  3097. goto out;
  3098. trace_ext4_ext_convert_to_initialized_fastpath(inode,
  3099. map, ex, abut_ex);
  3100. /* Shift the start of ex by 'map_len' blocks */
  3101. ex->ee_block = cpu_to_le32(ee_block + map_len);
  3102. ext4_ext_store_pblock(ex, ee_pblk + map_len);
  3103. ex->ee_len = cpu_to_le16(ee_len - map_len);
  3104. ext4_ext_mark_unwritten(ex); /* Restore the flag */
  3105. /* Extend abut_ex by 'map_len' blocks */
  3106. abut_ex->ee_len = cpu_to_le16(prev_len + map_len);
  3107. /* Result: number of initialized blocks past m_lblk */
  3108. allocated = map_len;
  3109. }
  3110. } else if (((map->m_lblk + map_len) == (ee_block + ee_len)) &&
  3111. (map_len < ee_len) && /*L1*/
  3112. ex < EXT_LAST_EXTENT(eh)) { /*L2*/
  3113. /* See if we can merge right */
  3114. ext4_lblk_t next_lblk;
  3115. ext4_fsblk_t next_pblk, ee_pblk;
  3116. unsigned int next_len;
  3117. abut_ex = ex + 1;
  3118. next_lblk = le32_to_cpu(abut_ex->ee_block);
  3119. next_len = ext4_ext_get_actual_len(abut_ex);
  3120. next_pblk = ext4_ext_pblock(abut_ex);
  3121. ee_pblk = ext4_ext_pblock(ex);
  3122. /*
  3123. * A transfer of blocks from 'ex' to 'abut_ex' is allowed
  3124. * upon those conditions:
  3125. * - C1: abut_ex is initialized,
  3126. * - C2: abut_ex is logically abutting ex,
  3127. * - C3: abut_ex is physically abutting ex,
  3128. * - C4: abut_ex can receive the additional blocks without
  3129. * overflowing the (initialized) length limit.
  3130. */
  3131. if ((!ext4_ext_is_unwritten(abut_ex)) && /*C1*/
  3132. ((map->m_lblk + map_len) == next_lblk) && /*C2*/
  3133. ((ee_pblk + ee_len) == next_pblk) && /*C3*/
  3134. (next_len < (EXT_INIT_MAX_LEN - map_len))) { /*C4*/
  3135. err = ext4_ext_get_access(handle, inode, path + depth);
  3136. if (err)
  3137. goto out;
  3138. trace_ext4_ext_convert_to_initialized_fastpath(inode,
  3139. map, ex, abut_ex);
  3140. /* Shift the start of abut_ex by 'map_len' blocks */
  3141. abut_ex->ee_block = cpu_to_le32(next_lblk - map_len);
  3142. ext4_ext_store_pblock(abut_ex, next_pblk - map_len);
  3143. ex->ee_len = cpu_to_le16(ee_len - map_len);
  3144. ext4_ext_mark_unwritten(ex); /* Restore the flag */
  3145. /* Extend abut_ex by 'map_len' blocks */
  3146. abut_ex->ee_len = cpu_to_le16(next_len + map_len);
  3147. /* Result: number of initialized blocks past m_lblk */
  3148. allocated = map_len;
  3149. }
  3150. }
  3151. if (allocated) {
  3152. /* Mark the block containing both extents as dirty */
  3153. err = ext4_ext_dirty(handle, inode, path + depth);
  3154. /* Update path to point to the right extent */
  3155. path[depth].p_ext = abut_ex;
  3156. goto out;
  3157. } else
  3158. allocated = ee_len - (map->m_lblk - ee_block);
  3159. WARN_ON(map->m_lblk < ee_block);
  3160. /*
  3161. * It is safe to convert extent to initialized via explicit
  3162. * zeroout only if extent is fully inside i_size or new_size.
  3163. */
  3164. split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
  3165. if (EXT4_EXT_MAY_ZEROOUT & split_flag)
  3166. max_zeroout = sbi->s_extent_max_zeroout_kb >>
  3167. (inode->i_sb->s_blocksize_bits - 10);
  3168. /*
  3169. * five cases:
  3170. * 1. split the extent into three extents.
  3171. * 2. split the extent into two extents, zeroout the head of the first
  3172. * extent.
  3173. * 3. split the extent into two extents, zeroout the tail of the second
  3174. * extent.
  3175. * 4. split the extent into two extents with out zeroout.
  3176. * 5. no splitting needed, just possibly zeroout the head and / or the
  3177. * tail of the extent.
  3178. */
  3179. split_map.m_lblk = map->m_lblk;
  3180. split_map.m_len = map->m_len;
  3181. if (max_zeroout && (allocated > split_map.m_len)) {
  3182. if (allocated <= max_zeroout) {
  3183. /* case 3 or 5 */
  3184. zero_ex1.ee_block =
  3185. cpu_to_le32(split_map.m_lblk +
  3186. split_map.m_len);
  3187. zero_ex1.ee_len =
  3188. cpu_to_le16(allocated - split_map.m_len);
  3189. ext4_ext_store_pblock(&zero_ex1,
  3190. ext4_ext_pblock(ex) + split_map.m_lblk +
  3191. split_map.m_len - ee_block);
  3192. err = ext4_ext_zeroout(inode, &zero_ex1);
  3193. if (err)
  3194. goto out;
  3195. split_map.m_len = allocated;
  3196. }
  3197. if (split_map.m_lblk - ee_block + split_map.m_len <
  3198. max_zeroout) {
  3199. /* case 2 or 5 */
  3200. if (split_map.m_lblk != ee_block) {
  3201. zero_ex2.ee_block = ex->ee_block;
  3202. zero_ex2.ee_len = cpu_to_le16(split_map.m_lblk -
  3203. ee_block);
  3204. ext4_ext_store_pblock(&zero_ex2,
  3205. ext4_ext_pblock(ex));
  3206. err = ext4_ext_zeroout(inode, &zero_ex2);
  3207. if (err)
  3208. goto out;
  3209. }
  3210. split_map.m_len += split_map.m_lblk - ee_block;
  3211. split_map.m_lblk = ee_block;
  3212. allocated = map->m_len;
  3213. }
  3214. }
  3215. err = ext4_split_extent(handle, inode, ppath, &split_map, split_flag,
  3216. flags);
  3217. if (err > 0)
  3218. err = 0;
  3219. out:
  3220. /* If we have gotten a failure, don't zero out status tree */
  3221. if (!err) {
  3222. err = ext4_zeroout_es(inode, &zero_ex1);
  3223. if (!err)
  3224. err = ext4_zeroout_es(inode, &zero_ex2);
  3225. }
  3226. return err ? err : allocated;
  3227. }
  3228. /*
  3229. * This function is called by ext4_ext_map_blocks() from
  3230. * ext4_get_blocks_dio_write() when DIO to write
  3231. * to an unwritten extent.
  3232. *
  3233. * Writing to an unwritten extent may result in splitting the unwritten
  3234. * extent into multiple initialized/unwritten extents (up to three)
  3235. * There are three possibilities:
  3236. * a> There is no split required: Entire extent should be unwritten
  3237. * b> Splits in two extents: Write is happening at either end of the extent
  3238. * c> Splits in three extents: Somone is writing in middle of the extent
  3239. *
  3240. * This works the same way in the case of initialized -> unwritten conversion.
  3241. *
  3242. * One of more index blocks maybe needed if the extent tree grow after
  3243. * the unwritten extent split. To prevent ENOSPC occur at the IO
  3244. * complete, we need to split the unwritten extent before DIO submit
  3245. * the IO. The unwritten extent called at this time will be split
  3246. * into three unwritten extent(at most). After IO complete, the part
  3247. * being filled will be convert to initialized by the end_io callback function
  3248. * via ext4_convert_unwritten_extents().
  3249. *
  3250. * Returns the size of unwritten extent to be written on success.
  3251. */
  3252. static int ext4_split_convert_extents(handle_t *handle,
  3253. struct inode *inode,
  3254. struct ext4_map_blocks *map,
  3255. struct ext4_ext_path **ppath,
  3256. int flags)
  3257. {
  3258. struct ext4_ext_path *path = *ppath;
  3259. ext4_lblk_t eof_block;
  3260. ext4_lblk_t ee_block;
  3261. struct ext4_extent *ex;
  3262. unsigned int ee_len;
  3263. int split_flag = 0, depth;
  3264. ext_debug(inode, "logical block %llu, max_blocks %u\n",
  3265. (unsigned long long)map->m_lblk, map->m_len);
  3266. eof_block = (EXT4_I(inode)->i_disksize + inode->i_sb->s_blocksize - 1)
  3267. >> inode->i_sb->s_blocksize_bits;
  3268. if (eof_block < map->m_lblk + map->m_len)
  3269. eof_block = map->m_lblk + map->m_len;
  3270. /*
  3271. * It is safe to convert extent to initialized via explicit
  3272. * zeroout only if extent is fully inside i_size or new_size.
  3273. */
  3274. depth = ext_depth(inode);
  3275. ex = path[depth].p_ext;
  3276. ee_block = le32_to_cpu(ex->ee_block);
  3277. ee_len = ext4_ext_get_actual_len(ex);
  3278. /* Convert to unwritten */
  3279. if (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN) {
  3280. split_flag |= EXT4_EXT_DATA_VALID1;
  3281. /* Convert to initialized */
  3282. } else if (flags & EXT4_GET_BLOCKS_CONVERT) {
  3283. split_flag |= ee_block + ee_len <= eof_block ?
  3284. EXT4_EXT_MAY_ZEROOUT : 0;
  3285. split_flag |= (EXT4_EXT_MARK_UNWRIT2 | EXT4_EXT_DATA_VALID2);
  3286. }
  3287. flags |= EXT4_GET_BLOCKS_PRE_IO;
  3288. return ext4_split_extent(handle, inode, ppath, map, split_flag, flags);
  3289. }
  3290. static int ext4_convert_unwritten_extents_endio(handle_t *handle,
  3291. struct inode *inode,
  3292. struct ext4_map_blocks *map,
  3293. struct ext4_ext_path **ppath)
  3294. {
  3295. struct ext4_ext_path *path = *ppath;
  3296. struct ext4_extent *ex;
  3297. ext4_lblk_t ee_block;
  3298. unsigned int ee_len;
  3299. int depth;
  3300. int err = 0;
  3301. depth = ext_depth(inode);
  3302. ex = path[depth].p_ext;
  3303. ee_block = le32_to_cpu(ex->ee_block);
  3304. ee_len = ext4_ext_get_actual_len(ex);
  3305. ext_debug(inode, "logical block %llu, max_blocks %u\n",
  3306. (unsigned long long)ee_block, ee_len);
  3307. /* If extent is larger than requested it is a clear sign that we still
  3308. * have some extent state machine issues left. So extent_split is still
  3309. * required.
  3310. * TODO: Once all related issues will be fixed this situation should be
  3311. * illegal.
  3312. */
  3313. if (ee_block != map->m_lblk || ee_len > map->m_len) {
  3314. #ifdef CONFIG_EXT4_DEBUG
  3315. ext4_warning(inode->i_sb, "Inode (%ld) finished: extent logical block %llu,"
  3316. " len %u; IO logical block %llu, len %u",
  3317. inode->i_ino, (unsigned long long)ee_block, ee_len,
  3318. (unsigned long long)map->m_lblk, map->m_len);
  3319. #endif
  3320. err = ext4_split_convert_extents(handle, inode, map, ppath,
  3321. EXT4_GET_BLOCKS_CONVERT);
  3322. if (err < 0)
  3323. return err;
  3324. path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
  3325. if (IS_ERR(path))
  3326. return PTR_ERR(path);
  3327. depth = ext_depth(inode);
  3328. ex = path[depth].p_ext;
  3329. }
  3330. err = ext4_ext_get_access(handle, inode, path + depth);
  3331. if (err)
  3332. goto out;
  3333. /* first mark the extent as initialized */
  3334. ext4_ext_mark_initialized(ex);
  3335. /* note: ext4_ext_correct_indexes() isn't needed here because
  3336. * borders are not changed
  3337. */
  3338. ext4_ext_try_to_merge(handle, inode, path, ex);
  3339. /* Mark modified extent as dirty */
  3340. err = ext4_ext_dirty(handle, inode, path + path->p_depth);
  3341. out:
  3342. ext4_ext_show_leaf(inode, path);
  3343. return err;
  3344. }
  3345. static int
  3346. convert_initialized_extent(handle_t *handle, struct inode *inode,
  3347. struct ext4_map_blocks *map,
  3348. struct ext4_ext_path **ppath,
  3349. unsigned int *allocated)
  3350. {
  3351. struct ext4_ext_path *path = *ppath;
  3352. struct ext4_extent *ex;
  3353. ext4_lblk_t ee_block;
  3354. unsigned int ee_len;
  3355. int depth;
  3356. int err = 0;
  3357. /*
  3358. * Make sure that the extent is no bigger than we support with
  3359. * unwritten extent
  3360. */
  3361. if (map->m_len > EXT_UNWRITTEN_MAX_LEN)
  3362. map->m_len = EXT_UNWRITTEN_MAX_LEN / 2;
  3363. depth = ext_depth(inode);
  3364. ex = path[depth].p_ext;
  3365. ee_block = le32_to_cpu(ex->ee_block);
  3366. ee_len = ext4_ext_get_actual_len(ex);
  3367. ext_debug(inode, "logical block %llu, max_blocks %u\n",
  3368. (unsigned long long)ee_block, ee_len);
  3369. if (ee_block != map->m_lblk || ee_len > map->m_len) {
  3370. err = ext4_split_convert_extents(handle, inode, map, ppath,
  3371. EXT4_GET_BLOCKS_CONVERT_UNWRITTEN);
  3372. if (err < 0)
  3373. return err;
  3374. path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
  3375. if (IS_ERR(path))
  3376. return PTR_ERR(path);
  3377. depth = ext_depth(inode);
  3378. ex = path[depth].p_ext;
  3379. if (!ex) {
  3380. EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
  3381. (unsigned long) map->m_lblk);
  3382. return -EFSCORRUPTED;
  3383. }
  3384. }
  3385. err = ext4_ext_get_access(handle, inode, path + depth);
  3386. if (err)
  3387. return err;
  3388. /* first mark the extent as unwritten */
  3389. ext4_ext_mark_unwritten(ex);
  3390. /* note: ext4_ext_correct_indexes() isn't needed here because
  3391. * borders are not changed
  3392. */
  3393. ext4_ext_try_to_merge(handle, inode, path, ex);
  3394. /* Mark modified extent as dirty */
  3395. err = ext4_ext_dirty(handle, inode, path + path->p_depth);
  3396. if (err)
  3397. return err;
  3398. ext4_ext_show_leaf(inode, path);
  3399. ext4_update_inode_fsync_trans(handle, inode, 1);
  3400. map->m_flags |= EXT4_MAP_UNWRITTEN;
  3401. if (*allocated > map->m_len)
  3402. *allocated = map->m_len;
  3403. map->m_len = *allocated;
  3404. return 0;
  3405. }
  3406. static int
  3407. ext4_ext_handle_unwritten_extents(handle_t *handle, struct inode *inode,
  3408. struct ext4_map_blocks *map,
  3409. struct ext4_ext_path **ppath, int flags,
  3410. unsigned int allocated, ext4_fsblk_t newblock)
  3411. {
  3412. struct ext4_ext_path __maybe_unused *path = *ppath;
  3413. int ret = 0;
  3414. int err = 0;
  3415. ext_debug(inode, "logical block %llu, max_blocks %u, flags 0x%x, allocated %u\n",
  3416. (unsigned long long)map->m_lblk, map->m_len, flags,
  3417. allocated);
  3418. ext4_ext_show_leaf(inode, path);
  3419. /*
  3420. * When writing into unwritten space, we should not fail to
  3421. * allocate metadata blocks for the new extent block if needed.
  3422. */
  3423. flags |= EXT4_GET_BLOCKS_METADATA_NOFAIL;
  3424. trace_ext4_ext_handle_unwritten_extents(inode, map, flags,
  3425. allocated, newblock);
  3426. /* get_block() before submitting IO, split the extent */
  3427. if (flags & EXT4_GET_BLOCKS_PRE_IO) {
  3428. ret = ext4_split_convert_extents(handle, inode, map, ppath,
  3429. flags | EXT4_GET_BLOCKS_CONVERT);
  3430. if (ret < 0) {
  3431. err = ret;
  3432. goto out2;
  3433. }
  3434. /*
  3435. * shouldn't get a 0 return when splitting an extent unless
  3436. * m_len is 0 (bug) or extent has been corrupted
  3437. */
  3438. if (unlikely(ret == 0)) {
  3439. EXT4_ERROR_INODE(inode,
  3440. "unexpected ret == 0, m_len = %u",
  3441. map->m_len);
  3442. err = -EFSCORRUPTED;
  3443. goto out2;
  3444. }
  3445. map->m_flags |= EXT4_MAP_UNWRITTEN;
  3446. goto out;
  3447. }
  3448. /* IO end_io complete, convert the filled extent to written */
  3449. if (flags & EXT4_GET_BLOCKS_CONVERT) {
  3450. err = ext4_convert_unwritten_extents_endio(handle, inode, map,
  3451. ppath);
  3452. if (err < 0)
  3453. goto out2;
  3454. ext4_update_inode_fsync_trans(handle, inode, 1);
  3455. goto map_out;
  3456. }
  3457. /* buffered IO cases */
  3458. /*
  3459. * repeat fallocate creation request
  3460. * we already have an unwritten extent
  3461. */
  3462. if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT) {
  3463. map->m_flags |= EXT4_MAP_UNWRITTEN;
  3464. goto map_out;
  3465. }
  3466. /* buffered READ or buffered write_begin() lookup */
  3467. if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
  3468. /*
  3469. * We have blocks reserved already. We
  3470. * return allocated blocks so that delalloc
  3471. * won't do block reservation for us. But
  3472. * the buffer head will be unmapped so that
  3473. * a read from the block returns 0s.
  3474. */
  3475. map->m_flags |= EXT4_MAP_UNWRITTEN;
  3476. goto out1;
  3477. }
  3478. /*
  3479. * Default case when (flags & EXT4_GET_BLOCKS_CREATE) == 1.
  3480. * For buffered writes, at writepage time, etc. Convert a
  3481. * discovered unwritten extent to written.
  3482. */
  3483. ret = ext4_ext_convert_to_initialized(handle, inode, map, ppath, flags);
  3484. if (ret < 0) {
  3485. err = ret;
  3486. goto out2;
  3487. }
  3488. ext4_update_inode_fsync_trans(handle, inode, 1);
  3489. /*
  3490. * shouldn't get a 0 return when converting an unwritten extent
  3491. * unless m_len is 0 (bug) or extent has been corrupted
  3492. */
  3493. if (unlikely(ret == 0)) {
  3494. EXT4_ERROR_INODE(inode, "unexpected ret == 0, m_len = %u",
  3495. map->m_len);
  3496. err = -EFSCORRUPTED;
  3497. goto out2;
  3498. }
  3499. out:
  3500. allocated = ret;
  3501. map->m_flags |= EXT4_MAP_NEW;
  3502. map_out:
  3503. map->m_flags |= EXT4_MAP_MAPPED;
  3504. out1:
  3505. map->m_pblk = newblock;
  3506. if (allocated > map->m_len)
  3507. allocated = map->m_len;
  3508. map->m_len = allocated;
  3509. ext4_ext_show_leaf(inode, path);
  3510. out2:
  3511. return err ? err : allocated;
  3512. }
  3513. /*
  3514. * get_implied_cluster_alloc - check to see if the requested
  3515. * allocation (in the map structure) overlaps with a cluster already
  3516. * allocated in an extent.
  3517. * @sb The filesystem superblock structure
  3518. * @map The requested lblk->pblk mapping
  3519. * @ex The extent structure which might contain an implied
  3520. * cluster allocation
  3521. *
  3522. * This function is called by ext4_ext_map_blocks() after we failed to
  3523. * find blocks that were already in the inode's extent tree. Hence,
  3524. * we know that the beginning of the requested region cannot overlap
  3525. * the extent from the inode's extent tree. There are three cases we
  3526. * want to catch. The first is this case:
  3527. *
  3528. * |--- cluster # N--|
  3529. * |--- extent ---| |---- requested region ---|
  3530. * |==========|
  3531. *
  3532. * The second case that we need to test for is this one:
  3533. *
  3534. * |--------- cluster # N ----------------|
  3535. * |--- requested region --| |------- extent ----|
  3536. * |=======================|
  3537. *
  3538. * The third case is when the requested region lies between two extents
  3539. * within the same cluster:
  3540. * |------------- cluster # N-------------|
  3541. * |----- ex -----| |---- ex_right ----|
  3542. * |------ requested region ------|
  3543. * |================|
  3544. *
  3545. * In each of the above cases, we need to set the map->m_pblk and
  3546. * map->m_len so it corresponds to the return the extent labelled as
  3547. * "|====|" from cluster #N, since it is already in use for data in
  3548. * cluster EXT4_B2C(sbi, map->m_lblk). We will then return 1 to
  3549. * signal to ext4_ext_map_blocks() that map->m_pblk should be treated
  3550. * as a new "allocated" block region. Otherwise, we will return 0 and
  3551. * ext4_ext_map_blocks() will then allocate one or more new clusters
  3552. * by calling ext4_mb_new_blocks().
  3553. */
  3554. static int get_implied_cluster_alloc(struct super_block *sb,
  3555. struct ext4_map_blocks *map,
  3556. struct ext4_extent *ex,
  3557. struct ext4_ext_path *path)
  3558. {
  3559. struct ext4_sb_info *sbi = EXT4_SB(sb);
  3560. ext4_lblk_t c_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
  3561. ext4_lblk_t ex_cluster_start, ex_cluster_end;
  3562. ext4_lblk_t rr_cluster_start;
  3563. ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
  3564. ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
  3565. unsigned short ee_len = ext4_ext_get_actual_len(ex);
  3566. /* The extent passed in that we are trying to match */
  3567. ex_cluster_start = EXT4_B2C(sbi, ee_block);
  3568. ex_cluster_end = EXT4_B2C(sbi, ee_block + ee_len - 1);
  3569. /* The requested region passed into ext4_map_blocks() */
  3570. rr_cluster_start = EXT4_B2C(sbi, map->m_lblk);
  3571. if ((rr_cluster_start == ex_cluster_end) ||
  3572. (rr_cluster_start == ex_cluster_start)) {
  3573. if (rr_cluster_start == ex_cluster_end)
  3574. ee_start += ee_len - 1;
  3575. map->m_pblk = EXT4_PBLK_CMASK(sbi, ee_start) + c_offset;
  3576. map->m_len = min(map->m_len,
  3577. (unsigned) sbi->s_cluster_ratio - c_offset);
  3578. /*
  3579. * Check for and handle this case:
  3580. *
  3581. * |--------- cluster # N-------------|
  3582. * |------- extent ----|
  3583. * |--- requested region ---|
  3584. * |===========|
  3585. */
  3586. if (map->m_lblk < ee_block)
  3587. map->m_len = min(map->m_len, ee_block - map->m_lblk);
  3588. /*
  3589. * Check for the case where there is already another allocated
  3590. * block to the right of 'ex' but before the end of the cluster.
  3591. *
  3592. * |------------- cluster # N-------------|
  3593. * |----- ex -----| |---- ex_right ----|
  3594. * |------ requested region ------|
  3595. * |================|
  3596. */
  3597. if (map->m_lblk > ee_block) {
  3598. ext4_lblk_t next = ext4_ext_next_allocated_block(path);
  3599. map->m_len = min(map->m_len, next - map->m_lblk);
  3600. }
  3601. trace_ext4_get_implied_cluster_alloc_exit(sb, map, 1);
  3602. return 1;
  3603. }
  3604. trace_ext4_get_implied_cluster_alloc_exit(sb, map, 0);
  3605. return 0;
  3606. }
  3607. /*
  3608. * Block allocation/map/preallocation routine for extents based files
  3609. *
  3610. *
  3611. * Need to be called with
  3612. * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
  3613. * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
  3614. *
  3615. * return > 0, number of blocks already mapped/allocated
  3616. * if create == 0 and these are pre-allocated blocks
  3617. * buffer head is unmapped
  3618. * otherwise blocks are mapped
  3619. *
  3620. * return = 0, if plain look up failed (blocks have not been allocated)
  3621. * buffer head is unmapped
  3622. *
  3623. * return < 0, error case.
  3624. */
  3625. int ext4_ext_map_blocks(handle_t *handle, struct inode *inode,
  3626. struct ext4_map_blocks *map, int flags)
  3627. {
  3628. struct ext4_ext_path *path = NULL;
  3629. struct ext4_extent newex, *ex, ex2;
  3630. struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  3631. ext4_fsblk_t newblock = 0, pblk;
  3632. int err = 0, depth, ret;
  3633. unsigned int allocated = 0, offset = 0;
  3634. unsigned int allocated_clusters = 0;
  3635. struct ext4_allocation_request ar;
  3636. ext4_lblk_t cluster_offset;
  3637. ext_debug(inode, "blocks %u/%u requested\n", map->m_lblk, map->m_len);
  3638. trace_ext4_ext_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
  3639. /* find extent for this block */
  3640. path = ext4_find_extent(inode, map->m_lblk, NULL, 0);
  3641. if (IS_ERR(path)) {
  3642. err = PTR_ERR(path);
  3643. path = NULL;
  3644. goto out;
  3645. }
  3646. depth = ext_depth(inode);
  3647. /*
  3648. * consistent leaf must not be empty;
  3649. * this situation is possible, though, _during_ tree modification;
  3650. * this is why assert can't be put in ext4_find_extent()
  3651. */
  3652. if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
  3653. EXT4_ERROR_INODE(inode, "bad extent address "
  3654. "lblock: %lu, depth: %d pblock %lld",
  3655. (unsigned long) map->m_lblk, depth,
  3656. path[depth].p_block);
  3657. err = -EFSCORRUPTED;
  3658. goto out;
  3659. }
  3660. ex = path[depth].p_ext;
  3661. if (ex) {
  3662. ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
  3663. ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
  3664. unsigned short ee_len;
  3665. /*
  3666. * unwritten extents are treated as holes, except that
  3667. * we split out initialized portions during a write.
  3668. */
  3669. ee_len = ext4_ext_get_actual_len(ex);
  3670. trace_ext4_ext_show_extent(inode, ee_block, ee_start, ee_len);
  3671. /* if found extent covers block, simply return it */
  3672. if (in_range(map->m_lblk, ee_block, ee_len)) {
  3673. newblock = map->m_lblk - ee_block + ee_start;
  3674. /* number of remaining blocks in the extent */
  3675. allocated = ee_len - (map->m_lblk - ee_block);
  3676. ext_debug(inode, "%u fit into %u:%d -> %llu\n",
  3677. map->m_lblk, ee_block, ee_len, newblock);
  3678. /*
  3679. * If the extent is initialized check whether the
  3680. * caller wants to convert it to unwritten.
  3681. */
  3682. if ((!ext4_ext_is_unwritten(ex)) &&
  3683. (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN)) {
  3684. err = convert_initialized_extent(handle,
  3685. inode, map, &path, &allocated);
  3686. goto out;
  3687. } else if (!ext4_ext_is_unwritten(ex)) {
  3688. map->m_flags |= EXT4_MAP_MAPPED;
  3689. map->m_pblk = newblock;
  3690. if (allocated > map->m_len)
  3691. allocated = map->m_len;
  3692. map->m_len = allocated;
  3693. ext4_ext_show_leaf(inode, path);
  3694. goto out;
  3695. }
  3696. ret = ext4_ext_handle_unwritten_extents(
  3697. handle, inode, map, &path, flags,
  3698. allocated, newblock);
  3699. if (ret < 0)
  3700. err = ret;
  3701. else
  3702. allocated = ret;
  3703. goto out;
  3704. }
  3705. }
  3706. /*
  3707. * requested block isn't allocated yet;
  3708. * we couldn't try to create block if create flag is zero
  3709. */
  3710. if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
  3711. ext4_lblk_t hole_start, hole_len;
  3712. hole_start = map->m_lblk;
  3713. hole_len = ext4_ext_determine_hole(inode, path, &hole_start);
  3714. /*
  3715. * put just found gap into cache to speed up
  3716. * subsequent requests
  3717. */
  3718. ext4_ext_put_gap_in_cache(inode, hole_start, hole_len);
  3719. /* Update hole_len to reflect hole size after map->m_lblk */
  3720. if (hole_start != map->m_lblk)
  3721. hole_len -= map->m_lblk - hole_start;
  3722. map->m_pblk = 0;
  3723. map->m_len = min_t(unsigned int, map->m_len, hole_len);
  3724. goto out;
  3725. }
  3726. /*
  3727. * Okay, we need to do block allocation.
  3728. */
  3729. newex.ee_block = cpu_to_le32(map->m_lblk);
  3730. cluster_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
  3731. /*
  3732. * If we are doing bigalloc, check to see if the extent returned
  3733. * by ext4_find_extent() implies a cluster we can use.
  3734. */
  3735. if (cluster_offset && ex &&
  3736. get_implied_cluster_alloc(inode->i_sb, map, ex, path)) {
  3737. ar.len = allocated = map->m_len;
  3738. newblock = map->m_pblk;
  3739. goto got_allocated_blocks;
  3740. }
  3741. /* find neighbour allocated blocks */
  3742. ar.lleft = map->m_lblk;
  3743. err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
  3744. if (err)
  3745. goto out;
  3746. ar.lright = map->m_lblk;
  3747. err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright, &ex2);
  3748. if (err < 0)
  3749. goto out;
  3750. /* Check if the extent after searching to the right implies a
  3751. * cluster we can use. */
  3752. if ((sbi->s_cluster_ratio > 1) && err &&
  3753. get_implied_cluster_alloc(inode->i_sb, map, &ex2, path)) {
  3754. ar.len = allocated = map->m_len;
  3755. newblock = map->m_pblk;
  3756. goto got_allocated_blocks;
  3757. }
  3758. /*
  3759. * See if request is beyond maximum number of blocks we can have in
  3760. * a single extent. For an initialized extent this limit is
  3761. * EXT_INIT_MAX_LEN and for an unwritten extent this limit is
  3762. * EXT_UNWRITTEN_MAX_LEN.
  3763. */
  3764. if (map->m_len > EXT_INIT_MAX_LEN &&
  3765. !(flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
  3766. map->m_len = EXT_INIT_MAX_LEN;
  3767. else if (map->m_len > EXT_UNWRITTEN_MAX_LEN &&
  3768. (flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
  3769. map->m_len = EXT_UNWRITTEN_MAX_LEN;
  3770. /* Check if we can really insert (m_lblk)::(m_lblk + m_len) extent */
  3771. newex.ee_len = cpu_to_le16(map->m_len);
  3772. err = ext4_ext_check_overlap(sbi, inode, &newex, path);
  3773. if (err)
  3774. allocated = ext4_ext_get_actual_len(&newex);
  3775. else
  3776. allocated = map->m_len;
  3777. /* allocate new block */
  3778. ar.inode = inode;
  3779. ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk);
  3780. ar.logical = map->m_lblk;
  3781. /*
  3782. * We calculate the offset from the beginning of the cluster
  3783. * for the logical block number, since when we allocate a
  3784. * physical cluster, the physical block should start at the
  3785. * same offset from the beginning of the cluster. This is
  3786. * needed so that future calls to get_implied_cluster_alloc()
  3787. * work correctly.
  3788. */
  3789. offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
  3790. ar.len = EXT4_NUM_B2C(sbi, offset+allocated);
  3791. ar.goal -= offset;
  3792. ar.logical -= offset;
  3793. if (S_ISREG(inode->i_mode))
  3794. ar.flags = EXT4_MB_HINT_DATA;
  3795. else
  3796. /* disable in-core preallocation for non-regular files */
  3797. ar.flags = 0;
  3798. if (flags & EXT4_GET_BLOCKS_NO_NORMALIZE)
  3799. ar.flags |= EXT4_MB_HINT_NOPREALLOC;
  3800. if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
  3801. ar.flags |= EXT4_MB_DELALLOC_RESERVED;
  3802. if (flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
  3803. ar.flags |= EXT4_MB_USE_RESERVED;
  3804. newblock = ext4_mb_new_blocks(handle, &ar, &err);
  3805. if (!newblock)
  3806. goto out;
  3807. allocated_clusters = ar.len;
  3808. ar.len = EXT4_C2B(sbi, ar.len) - offset;
  3809. ext_debug(inode, "allocate new block: goal %llu, found %llu/%u, requested %u\n",
  3810. ar.goal, newblock, ar.len, allocated);
  3811. if (ar.len > allocated)
  3812. ar.len = allocated;
  3813. got_allocated_blocks:
  3814. /* try to insert new extent into found leaf and return */
  3815. pblk = newblock + offset;
  3816. ext4_ext_store_pblock(&newex, pblk);
  3817. newex.ee_len = cpu_to_le16(ar.len);
  3818. /* Mark unwritten */
  3819. if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT) {
  3820. ext4_ext_mark_unwritten(&newex);
  3821. map->m_flags |= EXT4_MAP_UNWRITTEN;
  3822. }
  3823. err = ext4_ext_insert_extent(handle, inode, &path, &newex, flags);
  3824. if (err) {
  3825. if (allocated_clusters) {
  3826. int fb_flags = 0;
  3827. /*
  3828. * free data blocks we just allocated.
  3829. * not a good idea to call discard here directly,
  3830. * but otherwise we'd need to call it every free().
  3831. */
  3832. ext4_discard_preallocations(inode, 0);
  3833. if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
  3834. fb_flags = EXT4_FREE_BLOCKS_NO_QUOT_UPDATE;
  3835. ext4_free_blocks(handle, inode, NULL, newblock,
  3836. EXT4_C2B(sbi, allocated_clusters),
  3837. fb_flags);
  3838. }
  3839. goto out;
  3840. }
  3841. /*
  3842. * Reduce the reserved cluster count to reflect successful deferred
  3843. * allocation of delayed allocated clusters or direct allocation of
  3844. * clusters discovered to be delayed allocated. Once allocated, a
  3845. * cluster is not included in the reserved count.
  3846. */
  3847. if (test_opt(inode->i_sb, DELALLOC) && allocated_clusters) {
  3848. if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
  3849. /*
  3850. * When allocating delayed allocated clusters, simply
  3851. * reduce the reserved cluster count and claim quota
  3852. */
  3853. ext4_da_update_reserve_space(inode, allocated_clusters,
  3854. 1);
  3855. } else {
  3856. ext4_lblk_t lblk, len;
  3857. unsigned int n;
  3858. /*
  3859. * When allocating non-delayed allocated clusters
  3860. * (from fallocate, filemap, DIO, or clusters
  3861. * allocated when delalloc has been disabled by
  3862. * ext4_nonda_switch), reduce the reserved cluster
  3863. * count by the number of allocated clusters that
  3864. * have previously been delayed allocated. Quota
  3865. * has been claimed by ext4_mb_new_blocks() above,
  3866. * so release the quota reservations made for any
  3867. * previously delayed allocated clusters.
  3868. */
  3869. lblk = EXT4_LBLK_CMASK(sbi, map->m_lblk);
  3870. len = allocated_clusters << sbi->s_cluster_bits;
  3871. n = ext4_es_delayed_clu(inode, lblk, len);
  3872. if (n > 0)
  3873. ext4_da_update_reserve_space(inode, (int) n, 0);
  3874. }
  3875. }
  3876. /*
  3877. * Cache the extent and update transaction to commit on fdatasync only
  3878. * when it is _not_ an unwritten extent.
  3879. */
  3880. if ((flags & EXT4_GET_BLOCKS_UNWRIT_EXT) == 0)
  3881. ext4_update_inode_fsync_trans(handle, inode, 1);
  3882. else
  3883. ext4_update_inode_fsync_trans(handle, inode, 0);
  3884. map->m_flags |= (EXT4_MAP_NEW | EXT4_MAP_MAPPED);
  3885. map->m_pblk = pblk;
  3886. map->m_len = ar.len;
  3887. allocated = map->m_len;
  3888. ext4_ext_show_leaf(inode, path);
  3889. out:
  3890. ext4_ext_drop_refs(path);
  3891. kfree(path);
  3892. trace_ext4_ext_map_blocks_exit(inode, flags, map,
  3893. err ? err : allocated);
  3894. return err ? err : allocated;
  3895. }
  3896. int ext4_ext_truncate(handle_t *handle, struct inode *inode)
  3897. {
  3898. struct super_block *sb = inode->i_sb;
  3899. ext4_lblk_t last_block;
  3900. int err = 0;
  3901. /*
  3902. * TODO: optimization is possible here.
  3903. * Probably we need not scan at all,
  3904. * because page truncation is enough.
  3905. */
  3906. /* we have to know where to truncate from in crash case */
  3907. EXT4_I(inode)->i_disksize = inode->i_size;
  3908. err = ext4_mark_inode_dirty(handle, inode);
  3909. if (err)
  3910. return err;
  3911. last_block = (inode->i_size + sb->s_blocksize - 1)
  3912. >> EXT4_BLOCK_SIZE_BITS(sb);
  3913. retry:
  3914. err = ext4_es_remove_extent(inode, last_block,
  3915. EXT_MAX_BLOCKS - last_block);
  3916. if (err == -ENOMEM) {
  3917. cond_resched();
  3918. congestion_wait(BLK_RW_ASYNC, HZ/50);
  3919. goto retry;
  3920. }
  3921. if (err)
  3922. return err;
  3923. retry_remove_space:
  3924. err = ext4_ext_remove_space(inode, last_block, EXT_MAX_BLOCKS - 1);
  3925. if (err == -ENOMEM) {
  3926. cond_resched();
  3927. congestion_wait(BLK_RW_ASYNC, HZ/50);
  3928. goto retry_remove_space;
  3929. }
  3930. return err;
  3931. }
  3932. static int ext4_alloc_file_blocks(struct file *file, ext4_lblk_t offset,
  3933. ext4_lblk_t len, loff_t new_size,
  3934. int flags)
  3935. {
  3936. struct inode *inode = file_inode(file);
  3937. handle_t *handle;
  3938. int ret = 0;
  3939. int ret2 = 0, ret3 = 0;
  3940. int retries = 0;
  3941. int depth = 0;
  3942. struct ext4_map_blocks map;
  3943. unsigned int credits;
  3944. loff_t epos;
  3945. BUG_ON(!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS));
  3946. map.m_lblk = offset;
  3947. map.m_len = len;
  3948. /*
  3949. * Don't normalize the request if it can fit in one extent so
  3950. * that it doesn't get unnecessarily split into multiple
  3951. * extents.
  3952. */
  3953. if (len <= EXT_UNWRITTEN_MAX_LEN)
  3954. flags |= EXT4_GET_BLOCKS_NO_NORMALIZE;
  3955. /*
  3956. * credits to insert 1 extent into extent tree
  3957. */
  3958. credits = ext4_chunk_trans_blocks(inode, len);
  3959. depth = ext_depth(inode);
  3960. retry:
  3961. while (ret >= 0 && len) {
  3962. /*
  3963. * Recalculate credits when extent tree depth changes.
  3964. */
  3965. if (depth != ext_depth(inode)) {
  3966. credits = ext4_chunk_trans_blocks(inode, len);
  3967. depth = ext_depth(inode);
  3968. }
  3969. handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
  3970. credits);
  3971. if (IS_ERR(handle)) {
  3972. ret = PTR_ERR(handle);
  3973. break;
  3974. }
  3975. ret = ext4_map_blocks(handle, inode, &map, flags);
  3976. if (ret <= 0) {
  3977. ext4_debug("inode #%lu: block %u: len %u: "
  3978. "ext4_ext_map_blocks returned %d",
  3979. inode->i_ino, map.m_lblk,
  3980. map.m_len, ret);
  3981. ext4_mark_inode_dirty(handle, inode);
  3982. ret2 = ext4_journal_stop(handle);
  3983. break;
  3984. }
  3985. map.m_lblk += ret;
  3986. map.m_len = len = len - ret;
  3987. epos = (loff_t)map.m_lblk << inode->i_blkbits;
  3988. inode->i_ctime = current_time(inode);
  3989. if (new_size) {
  3990. if (epos > new_size)
  3991. epos = new_size;
  3992. if (ext4_update_inode_size(inode, epos) & 0x1)
  3993. inode->i_mtime = inode->i_ctime;
  3994. }
  3995. ret2 = ext4_mark_inode_dirty(handle, inode);
  3996. ext4_update_inode_fsync_trans(handle, inode, 1);
  3997. ret3 = ext4_journal_stop(handle);
  3998. ret2 = ret3 ? ret3 : ret2;
  3999. if (unlikely(ret2))
  4000. break;
  4001. }
  4002. if (ret == -ENOSPC &&
  4003. ext4_should_retry_alloc(inode->i_sb, &retries)) {
  4004. ret = 0;
  4005. goto retry;
  4006. }
  4007. return ret > 0 ? ret2 : ret;
  4008. }
  4009. static int ext4_collapse_range(struct file *file, loff_t offset, loff_t len);
  4010. static int ext4_insert_range(struct file *file, loff_t offset, loff_t len);
  4011. static long ext4_zero_range(struct file *file, loff_t offset,
  4012. loff_t len, int mode)
  4013. {
  4014. struct inode *inode = file_inode(file);
  4015. handle_t *handle = NULL;
  4016. unsigned int max_blocks;
  4017. loff_t new_size = 0;
  4018. int ret = 0;
  4019. int flags;
  4020. int credits;
  4021. int partial_begin, partial_end;
  4022. loff_t start, end;
  4023. ext4_lblk_t lblk;
  4024. unsigned int blkbits = inode->i_blkbits;
  4025. trace_ext4_zero_range(inode, offset, len, mode);
  4026. /* Call ext4_force_commit to flush all data in case of data=journal. */
  4027. if (ext4_should_journal_data(inode)) {
  4028. ret = ext4_force_commit(inode->i_sb);
  4029. if (ret)
  4030. return ret;
  4031. }
  4032. /*
  4033. * Round up offset. This is not fallocate, we need to zero out
  4034. * blocks, so convert interior block aligned part of the range to
  4035. * unwritten and possibly manually zero out unaligned parts of the
  4036. * range.
  4037. */
  4038. start = round_up(offset, 1 << blkbits);
  4039. end = round_down((offset + len), 1 << blkbits);
  4040. if (start < offset || end > offset + len)
  4041. return -EINVAL;
  4042. partial_begin = offset & ((1 << blkbits) - 1);
  4043. partial_end = (offset + len) & ((1 << blkbits) - 1);
  4044. lblk = start >> blkbits;
  4045. max_blocks = (end >> blkbits);
  4046. if (max_blocks < lblk)
  4047. max_blocks = 0;
  4048. else
  4049. max_blocks -= lblk;
  4050. inode_lock(inode);
  4051. /*
  4052. * Indirect files do not support unwritten extents
  4053. */
  4054. if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
  4055. ret = -EOPNOTSUPP;
  4056. goto out_mutex;
  4057. }
  4058. if (!(mode & FALLOC_FL_KEEP_SIZE) &&
  4059. (offset + len > inode->i_size ||
  4060. offset + len > EXT4_I(inode)->i_disksize)) {
  4061. new_size = offset + len;
  4062. ret = inode_newsize_ok(inode, new_size);
  4063. if (ret)
  4064. goto out_mutex;
  4065. }
  4066. flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
  4067. /* Wait all existing dio workers, newcomers will block on i_mutex */
  4068. inode_dio_wait(inode);
  4069. ret = file_modified(file);
  4070. if (ret)
  4071. goto out_mutex;
  4072. /* Preallocate the range including the unaligned edges */
  4073. if (partial_begin || partial_end) {
  4074. ret = ext4_alloc_file_blocks(file,
  4075. round_down(offset, 1 << blkbits) >> blkbits,
  4076. (round_up((offset + len), 1 << blkbits) -
  4077. round_down(offset, 1 << blkbits)) >> blkbits,
  4078. new_size, flags);
  4079. if (ret)
  4080. goto out_mutex;
  4081. }
  4082. /* Zero range excluding the unaligned edges */
  4083. if (max_blocks > 0) {
  4084. flags |= (EXT4_GET_BLOCKS_CONVERT_UNWRITTEN |
  4085. EXT4_EX_NOCACHE);
  4086. /*
  4087. * Prevent page faults from reinstantiating pages we have
  4088. * released from page cache.
  4089. */
  4090. down_write(&EXT4_I(inode)->i_mmap_sem);
  4091. ret = ext4_break_layouts(inode);
  4092. if (ret) {
  4093. up_write(&EXT4_I(inode)->i_mmap_sem);
  4094. goto out_mutex;
  4095. }
  4096. ret = ext4_update_disksize_before_punch(inode, offset, len);
  4097. if (ret) {
  4098. up_write(&EXT4_I(inode)->i_mmap_sem);
  4099. goto out_mutex;
  4100. }
  4101. /* Now release the pages and zero block aligned part of pages */
  4102. truncate_pagecache_range(inode, start, end - 1);
  4103. inode->i_mtime = inode->i_ctime = current_time(inode);
  4104. ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size,
  4105. flags);
  4106. up_write(&EXT4_I(inode)->i_mmap_sem);
  4107. if (ret)
  4108. goto out_mutex;
  4109. }
  4110. if (!partial_begin && !partial_end)
  4111. goto out_mutex;
  4112. /*
  4113. * In worst case we have to writeout two nonadjacent unwritten
  4114. * blocks and update the inode
  4115. */
  4116. credits = (2 * ext4_ext_index_trans_blocks(inode, 2)) + 1;
  4117. if (ext4_should_journal_data(inode))
  4118. credits += 2;
  4119. handle = ext4_journal_start(inode, EXT4_HT_MISC, credits);
  4120. if (IS_ERR(handle)) {
  4121. ret = PTR_ERR(handle);
  4122. ext4_std_error(inode->i_sb, ret);
  4123. goto out_mutex;
  4124. }
  4125. inode->i_mtime = inode->i_ctime = current_time(inode);
  4126. if (new_size)
  4127. ext4_update_inode_size(inode, new_size);
  4128. ret = ext4_mark_inode_dirty(handle, inode);
  4129. if (unlikely(ret))
  4130. goto out_handle;
  4131. /* Zero out partial block at the edges of the range */
  4132. ret = ext4_zero_partial_blocks(handle, inode, offset, len);
  4133. if (ret >= 0)
  4134. ext4_update_inode_fsync_trans(handle, inode, 1);
  4135. if (file->f_flags & O_SYNC)
  4136. ext4_handle_sync(handle);
  4137. out_handle:
  4138. ext4_journal_stop(handle);
  4139. out_mutex:
  4140. inode_unlock(inode);
  4141. return ret;
  4142. }
  4143. /*
  4144. * preallocate space for a file. This implements ext4's fallocate file
  4145. * operation, which gets called from sys_fallocate system call.
  4146. * For block-mapped files, posix_fallocate should fall back to the method
  4147. * of writing zeroes to the required new blocks (the same behavior which is
  4148. * expected for file systems which do not support fallocate() system call).
  4149. */
  4150. long ext4_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
  4151. {
  4152. struct inode *inode = file_inode(file);
  4153. loff_t new_size = 0;
  4154. unsigned int max_blocks;
  4155. int ret = 0;
  4156. int flags;
  4157. ext4_lblk_t lblk;
  4158. unsigned int blkbits = inode->i_blkbits;
  4159. /*
  4160. * Encrypted inodes can't handle collapse range or insert
  4161. * range since we would need to re-encrypt blocks with a
  4162. * different IV or XTS tweak (which are based on the logical
  4163. * block number).
  4164. */
  4165. if (IS_ENCRYPTED(inode) &&
  4166. (mode & (FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_INSERT_RANGE)))
  4167. return -EOPNOTSUPP;
  4168. /* Return error if mode is not supported */
  4169. if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE |
  4170. FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_ZERO_RANGE |
  4171. FALLOC_FL_INSERT_RANGE))
  4172. return -EOPNOTSUPP;
  4173. ext4_fc_start_update(inode);
  4174. if (mode & FALLOC_FL_PUNCH_HOLE) {
  4175. ret = ext4_punch_hole(file, offset, len);
  4176. goto exit;
  4177. }
  4178. ret = ext4_convert_inline_data(inode);
  4179. if (ret)
  4180. goto exit;
  4181. if (mode & FALLOC_FL_COLLAPSE_RANGE) {
  4182. ret = ext4_collapse_range(file, offset, len);
  4183. goto exit;
  4184. }
  4185. if (mode & FALLOC_FL_INSERT_RANGE) {
  4186. ret = ext4_insert_range(file, offset, len);
  4187. goto exit;
  4188. }
  4189. if (mode & FALLOC_FL_ZERO_RANGE) {
  4190. ret = ext4_zero_range(file, offset, len, mode);
  4191. goto exit;
  4192. }
  4193. trace_ext4_fallocate_enter(inode, offset, len, mode);
  4194. lblk = offset >> blkbits;
  4195. max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
  4196. flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
  4197. inode_lock(inode);
  4198. /*
  4199. * We only support preallocation for extent-based files only
  4200. */
  4201. if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
  4202. ret = -EOPNOTSUPP;
  4203. goto out;
  4204. }
  4205. if (!(mode & FALLOC_FL_KEEP_SIZE) &&
  4206. (offset + len > inode->i_size ||
  4207. offset + len > EXT4_I(inode)->i_disksize)) {
  4208. new_size = offset + len;
  4209. ret = inode_newsize_ok(inode, new_size);
  4210. if (ret)
  4211. goto out;
  4212. }
  4213. /* Wait all existing dio workers, newcomers will block on i_mutex */
  4214. inode_dio_wait(inode);
  4215. ret = file_modified(file);
  4216. if (ret)
  4217. goto out;
  4218. ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size, flags);
  4219. if (ret)
  4220. goto out;
  4221. if (file->f_flags & O_SYNC && EXT4_SB(inode->i_sb)->s_journal) {
  4222. ret = ext4_fc_commit(EXT4_SB(inode->i_sb)->s_journal,
  4223. EXT4_I(inode)->i_sync_tid);
  4224. }
  4225. out:
  4226. inode_unlock(inode);
  4227. trace_ext4_fallocate_exit(inode, offset, max_blocks, ret);
  4228. exit:
  4229. ext4_fc_stop_update(inode);
  4230. return ret;
  4231. }
  4232. /*
  4233. * This function convert a range of blocks to written extents
  4234. * The caller of this function will pass the start offset and the size.
  4235. * all unwritten extents within this range will be converted to
  4236. * written extents.
  4237. *
  4238. * This function is called from the direct IO end io call back
  4239. * function, to convert the fallocated extents after IO is completed.
  4240. * Returns 0 on success.
  4241. */
  4242. int ext4_convert_unwritten_extents(handle_t *handle, struct inode *inode,
  4243. loff_t offset, ssize_t len)
  4244. {
  4245. unsigned int max_blocks;
  4246. int ret = 0, ret2 = 0, ret3 = 0;
  4247. struct ext4_map_blocks map;
  4248. unsigned int blkbits = inode->i_blkbits;
  4249. unsigned int credits = 0;
  4250. map.m_lblk = offset >> blkbits;
  4251. max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
  4252. if (!handle) {
  4253. /*
  4254. * credits to insert 1 extent into extent tree
  4255. */
  4256. credits = ext4_chunk_trans_blocks(inode, max_blocks);
  4257. }
  4258. while (ret >= 0 && ret < max_blocks) {
  4259. map.m_lblk += ret;
  4260. map.m_len = (max_blocks -= ret);
  4261. if (credits) {
  4262. handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
  4263. credits);
  4264. if (IS_ERR(handle)) {
  4265. ret = PTR_ERR(handle);
  4266. break;
  4267. }
  4268. }
  4269. ret = ext4_map_blocks(handle, inode, &map,
  4270. EXT4_GET_BLOCKS_IO_CONVERT_EXT);
  4271. if (ret <= 0)
  4272. ext4_warning(inode->i_sb,
  4273. "inode #%lu: block %u: len %u: "
  4274. "ext4_ext_map_blocks returned %d",
  4275. inode->i_ino, map.m_lblk,
  4276. map.m_len, ret);
  4277. ret2 = ext4_mark_inode_dirty(handle, inode);
  4278. if (credits) {
  4279. ret3 = ext4_journal_stop(handle);
  4280. if (unlikely(ret3))
  4281. ret2 = ret3;
  4282. }
  4283. if (ret <= 0 || ret2)
  4284. break;
  4285. }
  4286. return ret > 0 ? ret2 : ret;
  4287. }
  4288. int ext4_convert_unwritten_io_end_vec(handle_t *handle, ext4_io_end_t *io_end)
  4289. {
  4290. int ret = 0, err = 0;
  4291. struct ext4_io_end_vec *io_end_vec;
  4292. /*
  4293. * This is somewhat ugly but the idea is clear: When transaction is
  4294. * reserved, everything goes into it. Otherwise we rather start several
  4295. * smaller transactions for conversion of each extent separately.
  4296. */
  4297. if (handle) {
  4298. handle = ext4_journal_start_reserved(handle,
  4299. EXT4_HT_EXT_CONVERT);
  4300. if (IS_ERR(handle))
  4301. return PTR_ERR(handle);
  4302. }
  4303. list_for_each_entry(io_end_vec, &io_end->list_vec, list) {
  4304. ret = ext4_convert_unwritten_extents(handle, io_end->inode,
  4305. io_end_vec->offset,
  4306. io_end_vec->size);
  4307. if (ret)
  4308. break;
  4309. }
  4310. if (handle)
  4311. err = ext4_journal_stop(handle);
  4312. return ret < 0 ? ret : err;
  4313. }
  4314. static int ext4_iomap_xattr_fiemap(struct inode *inode, struct iomap *iomap)
  4315. {
  4316. __u64 physical = 0;
  4317. __u64 length = 0;
  4318. int blockbits = inode->i_sb->s_blocksize_bits;
  4319. int error = 0;
  4320. u16 iomap_type;
  4321. /* in-inode? */
  4322. if (ext4_test_inode_state(inode, EXT4_STATE_XATTR)) {
  4323. struct ext4_iloc iloc;
  4324. int offset; /* offset of xattr in inode */
  4325. error = ext4_get_inode_loc(inode, &iloc);
  4326. if (error)
  4327. return error;
  4328. physical = (__u64)iloc.bh->b_blocknr << blockbits;
  4329. offset = EXT4_GOOD_OLD_INODE_SIZE +
  4330. EXT4_I(inode)->i_extra_isize;
  4331. physical += offset;
  4332. length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
  4333. brelse(iloc.bh);
  4334. iomap_type = IOMAP_INLINE;
  4335. } else if (EXT4_I(inode)->i_file_acl) { /* external block */
  4336. physical = (__u64)EXT4_I(inode)->i_file_acl << blockbits;
  4337. length = inode->i_sb->s_blocksize;
  4338. iomap_type = IOMAP_MAPPED;
  4339. } else {
  4340. /* no in-inode or external block for xattr, so return -ENOENT */
  4341. error = -ENOENT;
  4342. goto out;
  4343. }
  4344. iomap->addr = physical;
  4345. iomap->offset = 0;
  4346. iomap->length = length;
  4347. iomap->type = iomap_type;
  4348. iomap->flags = 0;
  4349. out:
  4350. return error;
  4351. }
  4352. static int ext4_iomap_xattr_begin(struct inode *inode, loff_t offset,
  4353. loff_t length, unsigned flags,
  4354. struct iomap *iomap, struct iomap *srcmap)
  4355. {
  4356. int error;
  4357. error = ext4_iomap_xattr_fiemap(inode, iomap);
  4358. if (error == 0 && (offset >= iomap->length))
  4359. error = -ENOENT;
  4360. return error;
  4361. }
  4362. static const struct iomap_ops ext4_iomap_xattr_ops = {
  4363. .iomap_begin = ext4_iomap_xattr_begin,
  4364. };
  4365. static int ext4_fiemap_check_ranges(struct inode *inode, u64 start, u64 *len)
  4366. {
  4367. u64 maxbytes;
  4368. if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
  4369. maxbytes = inode->i_sb->s_maxbytes;
  4370. else
  4371. maxbytes = EXT4_SB(inode->i_sb)->s_bitmap_maxbytes;
  4372. if (*len == 0)
  4373. return -EINVAL;
  4374. if (start > maxbytes)
  4375. return -EFBIG;
  4376. /*
  4377. * Shrink request scope to what the fs can actually handle.
  4378. */
  4379. if (*len > maxbytes || (maxbytes - *len) < start)
  4380. *len = maxbytes - start;
  4381. return 0;
  4382. }
  4383. int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
  4384. u64 start, u64 len)
  4385. {
  4386. int error = 0;
  4387. if (fieinfo->fi_flags & FIEMAP_FLAG_CACHE) {
  4388. error = ext4_ext_precache(inode);
  4389. if (error)
  4390. return error;
  4391. fieinfo->fi_flags &= ~FIEMAP_FLAG_CACHE;
  4392. }
  4393. /*
  4394. * For bitmap files the maximum size limit could be smaller than
  4395. * s_maxbytes, so check len here manually instead of just relying on the
  4396. * generic check.
  4397. */
  4398. error = ext4_fiemap_check_ranges(inode, start, &len);
  4399. if (error)
  4400. return error;
  4401. if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
  4402. fieinfo->fi_flags &= ~FIEMAP_FLAG_XATTR;
  4403. return iomap_fiemap(inode, fieinfo, start, len,
  4404. &ext4_iomap_xattr_ops);
  4405. }
  4406. return iomap_fiemap(inode, fieinfo, start, len, &ext4_iomap_report_ops);
  4407. }
  4408. int ext4_get_es_cache(struct inode *inode, struct fiemap_extent_info *fieinfo,
  4409. __u64 start, __u64 len)
  4410. {
  4411. ext4_lblk_t start_blk, len_blks;
  4412. __u64 last_blk;
  4413. int error = 0;
  4414. if (ext4_has_inline_data(inode)) {
  4415. int has_inline;
  4416. down_read(&EXT4_I(inode)->xattr_sem);
  4417. has_inline = ext4_has_inline_data(inode);
  4418. up_read(&EXT4_I(inode)->xattr_sem);
  4419. if (has_inline)
  4420. return 0;
  4421. }
  4422. if (fieinfo->fi_flags & FIEMAP_FLAG_CACHE) {
  4423. error = ext4_ext_precache(inode);
  4424. if (error)
  4425. return error;
  4426. fieinfo->fi_flags &= ~FIEMAP_FLAG_CACHE;
  4427. }
  4428. error = fiemap_prep(inode, fieinfo, start, &len, 0);
  4429. if (error)
  4430. return error;
  4431. error = ext4_fiemap_check_ranges(inode, start, &len);
  4432. if (error)
  4433. return error;
  4434. start_blk = start >> inode->i_sb->s_blocksize_bits;
  4435. last_blk = (start + len - 1) >> inode->i_sb->s_blocksize_bits;
  4436. if (last_blk >= EXT_MAX_BLOCKS)
  4437. last_blk = EXT_MAX_BLOCKS-1;
  4438. len_blks = ((ext4_lblk_t) last_blk) - start_blk + 1;
  4439. /*
  4440. * Walk the extent tree gathering extent information
  4441. * and pushing extents back to the user.
  4442. */
  4443. return ext4_fill_es_cache_info(inode, start_blk, len_blks, fieinfo);
  4444. }
  4445. /*
  4446. * ext4_ext_shift_path_extents:
  4447. * Shift the extents of a path structure lying between path[depth].p_ext
  4448. * and EXT_LAST_EXTENT(path[depth].p_hdr), by @shift blocks. @SHIFT tells
  4449. * if it is right shift or left shift operation.
  4450. */
  4451. static int
  4452. ext4_ext_shift_path_extents(struct ext4_ext_path *path, ext4_lblk_t shift,
  4453. struct inode *inode, handle_t *handle,
  4454. enum SHIFT_DIRECTION SHIFT)
  4455. {
  4456. int depth, err = 0;
  4457. struct ext4_extent *ex_start, *ex_last;
  4458. bool update = false;
  4459. int credits, restart_credits;
  4460. depth = path->p_depth;
  4461. while (depth >= 0) {
  4462. if (depth == path->p_depth) {
  4463. ex_start = path[depth].p_ext;
  4464. if (!ex_start)
  4465. return -EFSCORRUPTED;
  4466. ex_last = EXT_LAST_EXTENT(path[depth].p_hdr);
  4467. /* leaf + sb + inode */
  4468. credits = 3;
  4469. if (ex_start == EXT_FIRST_EXTENT(path[depth].p_hdr)) {
  4470. update = true;
  4471. /* extent tree + sb + inode */
  4472. credits = depth + 2;
  4473. }
  4474. restart_credits = ext4_writepage_trans_blocks(inode);
  4475. err = ext4_datasem_ensure_credits(handle, inode, credits,
  4476. restart_credits, 0);
  4477. if (err) {
  4478. if (err > 0)
  4479. err = -EAGAIN;
  4480. goto out;
  4481. }
  4482. err = ext4_ext_get_access(handle, inode, path + depth);
  4483. if (err)
  4484. goto out;
  4485. while (ex_start <= ex_last) {
  4486. if (SHIFT == SHIFT_LEFT) {
  4487. le32_add_cpu(&ex_start->ee_block,
  4488. -shift);
  4489. /* Try to merge to the left. */
  4490. if ((ex_start >
  4491. EXT_FIRST_EXTENT(path[depth].p_hdr))
  4492. &&
  4493. ext4_ext_try_to_merge_right(inode,
  4494. path, ex_start - 1))
  4495. ex_last--;
  4496. else
  4497. ex_start++;
  4498. } else {
  4499. le32_add_cpu(&ex_last->ee_block, shift);
  4500. ext4_ext_try_to_merge_right(inode, path,
  4501. ex_last);
  4502. ex_last--;
  4503. }
  4504. }
  4505. err = ext4_ext_dirty(handle, inode, path + depth);
  4506. if (err)
  4507. goto out;
  4508. if (--depth < 0 || !update)
  4509. break;
  4510. }
  4511. /* Update index too */
  4512. err = ext4_ext_get_access(handle, inode, path + depth);
  4513. if (err)
  4514. goto out;
  4515. if (SHIFT == SHIFT_LEFT)
  4516. le32_add_cpu(&path[depth].p_idx->ei_block, -shift);
  4517. else
  4518. le32_add_cpu(&path[depth].p_idx->ei_block, shift);
  4519. err = ext4_ext_dirty(handle, inode, path + depth);
  4520. if (err)
  4521. goto out;
  4522. /* we are done if current index is not a starting index */
  4523. if (path[depth].p_idx != EXT_FIRST_INDEX(path[depth].p_hdr))
  4524. break;
  4525. depth--;
  4526. }
  4527. out:
  4528. return err;
  4529. }
  4530. /*
  4531. * ext4_ext_shift_extents:
  4532. * All the extents which lies in the range from @start to the last allocated
  4533. * block for the @inode are shifted either towards left or right (depending
  4534. * upon @SHIFT) by @shift blocks.
  4535. * On success, 0 is returned, error otherwise.
  4536. */
  4537. static int
  4538. ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
  4539. ext4_lblk_t start, ext4_lblk_t shift,
  4540. enum SHIFT_DIRECTION SHIFT)
  4541. {
  4542. struct ext4_ext_path *path;
  4543. int ret = 0, depth;
  4544. struct ext4_extent *extent;
  4545. ext4_lblk_t stop, *iterator, ex_start, ex_end;
  4546. ext4_lblk_t tmp = EXT_MAX_BLOCKS;
  4547. /* Let path point to the last extent */
  4548. path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
  4549. EXT4_EX_NOCACHE);
  4550. if (IS_ERR(path))
  4551. return PTR_ERR(path);
  4552. depth = path->p_depth;
  4553. extent = path[depth].p_ext;
  4554. if (!extent)
  4555. goto out;
  4556. stop = le32_to_cpu(extent->ee_block);
  4557. /*
  4558. * For left shifts, make sure the hole on the left is big enough to
  4559. * accommodate the shift. For right shifts, make sure the last extent
  4560. * won't be shifted beyond EXT_MAX_BLOCKS.
  4561. */
  4562. if (SHIFT == SHIFT_LEFT) {
  4563. path = ext4_find_extent(inode, start - 1, &path,
  4564. EXT4_EX_NOCACHE);
  4565. if (IS_ERR(path))
  4566. return PTR_ERR(path);
  4567. depth = path->p_depth;
  4568. extent = path[depth].p_ext;
  4569. if (extent) {
  4570. ex_start = le32_to_cpu(extent->ee_block);
  4571. ex_end = le32_to_cpu(extent->ee_block) +
  4572. ext4_ext_get_actual_len(extent);
  4573. } else {
  4574. ex_start = 0;
  4575. ex_end = 0;
  4576. }
  4577. if ((start == ex_start && shift > ex_start) ||
  4578. (shift > start - ex_end)) {
  4579. ret = -EINVAL;
  4580. goto out;
  4581. }
  4582. } else {
  4583. if (shift > EXT_MAX_BLOCKS -
  4584. (stop + ext4_ext_get_actual_len(extent))) {
  4585. ret = -EINVAL;
  4586. goto out;
  4587. }
  4588. }
  4589. /*
  4590. * In case of left shift, iterator points to start and it is increased
  4591. * till we reach stop. In case of right shift, iterator points to stop
  4592. * and it is decreased till we reach start.
  4593. */
  4594. again:
  4595. if (SHIFT == SHIFT_LEFT)
  4596. iterator = &start;
  4597. else
  4598. iterator = &stop;
  4599. if (tmp != EXT_MAX_BLOCKS)
  4600. *iterator = tmp;
  4601. /*
  4602. * Its safe to start updating extents. Start and stop are unsigned, so
  4603. * in case of right shift if extent with 0 block is reached, iterator
  4604. * becomes NULL to indicate the end of the loop.
  4605. */
  4606. while (iterator && start <= stop) {
  4607. path = ext4_find_extent(inode, *iterator, &path,
  4608. EXT4_EX_NOCACHE);
  4609. if (IS_ERR(path))
  4610. return PTR_ERR(path);
  4611. depth = path->p_depth;
  4612. extent = path[depth].p_ext;
  4613. if (!extent) {
  4614. EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
  4615. (unsigned long) *iterator);
  4616. return -EFSCORRUPTED;
  4617. }
  4618. if (SHIFT == SHIFT_LEFT && *iterator >
  4619. le32_to_cpu(extent->ee_block)) {
  4620. /* Hole, move to the next extent */
  4621. if (extent < EXT_LAST_EXTENT(path[depth].p_hdr)) {
  4622. path[depth].p_ext++;
  4623. } else {
  4624. *iterator = ext4_ext_next_allocated_block(path);
  4625. continue;
  4626. }
  4627. }
  4628. tmp = *iterator;
  4629. if (SHIFT == SHIFT_LEFT) {
  4630. extent = EXT_LAST_EXTENT(path[depth].p_hdr);
  4631. *iterator = le32_to_cpu(extent->ee_block) +
  4632. ext4_ext_get_actual_len(extent);
  4633. } else {
  4634. extent = EXT_FIRST_EXTENT(path[depth].p_hdr);
  4635. if (le32_to_cpu(extent->ee_block) > 0)
  4636. *iterator = le32_to_cpu(extent->ee_block) - 1;
  4637. else
  4638. /* Beginning is reached, end of the loop */
  4639. iterator = NULL;
  4640. /* Update path extent in case we need to stop */
  4641. while (le32_to_cpu(extent->ee_block) < start)
  4642. extent++;
  4643. path[depth].p_ext = extent;
  4644. }
  4645. ret = ext4_ext_shift_path_extents(path, shift, inode,
  4646. handle, SHIFT);
  4647. /* iterator can be NULL which means we should break */
  4648. if (ret == -EAGAIN)
  4649. goto again;
  4650. if (ret)
  4651. break;
  4652. }
  4653. out:
  4654. ext4_ext_drop_refs(path);
  4655. kfree(path);
  4656. return ret;
  4657. }
  4658. /*
  4659. * ext4_collapse_range:
  4660. * This implements the fallocate's collapse range functionality for ext4
  4661. * Returns: 0 and non-zero on error.
  4662. */
  4663. static int ext4_collapse_range(struct file *file, loff_t offset, loff_t len)
  4664. {
  4665. struct inode *inode = file_inode(file);
  4666. struct super_block *sb = inode->i_sb;
  4667. ext4_lblk_t punch_start, punch_stop;
  4668. handle_t *handle;
  4669. unsigned int credits;
  4670. loff_t new_size, ioffset;
  4671. int ret;
  4672. /*
  4673. * We need to test this early because xfstests assumes that a
  4674. * collapse range of (0, 1) will return EOPNOTSUPP if the file
  4675. * system does not support collapse range.
  4676. */
  4677. if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
  4678. return -EOPNOTSUPP;
  4679. /* Collapse range works only on fs cluster size aligned regions. */
  4680. if (!IS_ALIGNED(offset | len, EXT4_CLUSTER_SIZE(sb)))
  4681. return -EINVAL;
  4682. trace_ext4_collapse_range(inode, offset, len);
  4683. punch_start = offset >> EXT4_BLOCK_SIZE_BITS(sb);
  4684. punch_stop = (offset + len) >> EXT4_BLOCK_SIZE_BITS(sb);
  4685. /* Call ext4_force_commit to flush all data in case of data=journal. */
  4686. if (ext4_should_journal_data(inode)) {
  4687. ret = ext4_force_commit(inode->i_sb);
  4688. if (ret)
  4689. return ret;
  4690. }
  4691. inode_lock(inode);
  4692. /*
  4693. * There is no need to overlap collapse range with EOF, in which case
  4694. * it is effectively a truncate operation
  4695. */
  4696. if (offset + len >= inode->i_size) {
  4697. ret = -EINVAL;
  4698. goto out_mutex;
  4699. }
  4700. /* Currently just for extent based files */
  4701. if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
  4702. ret = -EOPNOTSUPP;
  4703. goto out_mutex;
  4704. }
  4705. /* Wait for existing dio to complete */
  4706. inode_dio_wait(inode);
  4707. ret = file_modified(file);
  4708. if (ret)
  4709. goto out_mutex;
  4710. /*
  4711. * Prevent page faults from reinstantiating pages we have released from
  4712. * page cache.
  4713. */
  4714. down_write(&EXT4_I(inode)->i_mmap_sem);
  4715. ret = ext4_break_layouts(inode);
  4716. if (ret)
  4717. goto out_mmap;
  4718. /*
  4719. * Need to round down offset to be aligned with page size boundary
  4720. * for page size > block size.
  4721. */
  4722. ioffset = round_down(offset, PAGE_SIZE);
  4723. /*
  4724. * Write tail of the last page before removed range since it will get
  4725. * removed from the page cache below.
  4726. */
  4727. ret = filemap_write_and_wait_range(inode->i_mapping, ioffset, offset);
  4728. if (ret)
  4729. goto out_mmap;
  4730. /*
  4731. * Write data that will be shifted to preserve them when discarding
  4732. * page cache below. We are also protected from pages becoming dirty
  4733. * by i_mmap_sem.
  4734. */
  4735. ret = filemap_write_and_wait_range(inode->i_mapping, offset + len,
  4736. LLONG_MAX);
  4737. if (ret)
  4738. goto out_mmap;
  4739. truncate_pagecache(inode, ioffset);
  4740. credits = ext4_writepage_trans_blocks(inode);
  4741. handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
  4742. if (IS_ERR(handle)) {
  4743. ret = PTR_ERR(handle);
  4744. goto out_mmap;
  4745. }
  4746. ext4_fc_start_ineligible(sb, EXT4_FC_REASON_FALLOC_RANGE);
  4747. down_write(&EXT4_I(inode)->i_data_sem);
  4748. ext4_discard_preallocations(inode, 0);
  4749. ret = ext4_es_remove_extent(inode, punch_start,
  4750. EXT_MAX_BLOCKS - punch_start);
  4751. if (ret) {
  4752. up_write(&EXT4_I(inode)->i_data_sem);
  4753. goto out_stop;
  4754. }
  4755. ret = ext4_ext_remove_space(inode, punch_start, punch_stop - 1);
  4756. if (ret) {
  4757. up_write(&EXT4_I(inode)->i_data_sem);
  4758. goto out_stop;
  4759. }
  4760. ext4_discard_preallocations(inode, 0);
  4761. ret = ext4_ext_shift_extents(inode, handle, punch_stop,
  4762. punch_stop - punch_start, SHIFT_LEFT);
  4763. if (ret) {
  4764. up_write(&EXT4_I(inode)->i_data_sem);
  4765. goto out_stop;
  4766. }
  4767. new_size = inode->i_size - len;
  4768. i_size_write(inode, new_size);
  4769. EXT4_I(inode)->i_disksize = new_size;
  4770. up_write(&EXT4_I(inode)->i_data_sem);
  4771. if (IS_SYNC(inode))
  4772. ext4_handle_sync(handle);
  4773. inode->i_mtime = inode->i_ctime = current_time(inode);
  4774. ret = ext4_mark_inode_dirty(handle, inode);
  4775. ext4_update_inode_fsync_trans(handle, inode, 1);
  4776. out_stop:
  4777. ext4_journal_stop(handle);
  4778. ext4_fc_stop_ineligible(sb);
  4779. out_mmap:
  4780. up_write(&EXT4_I(inode)->i_mmap_sem);
  4781. out_mutex:
  4782. inode_unlock(inode);
  4783. return ret;
  4784. }
  4785. /*
  4786. * ext4_insert_range:
  4787. * This function implements the FALLOC_FL_INSERT_RANGE flag of fallocate.
  4788. * The data blocks starting from @offset to the EOF are shifted by @len
  4789. * towards right to create a hole in the @inode. Inode size is increased
  4790. * by len bytes.
  4791. * Returns 0 on success, error otherwise.
  4792. */
  4793. static int ext4_insert_range(struct file *file, loff_t offset, loff_t len)
  4794. {
  4795. struct inode *inode = file_inode(file);
  4796. struct super_block *sb = inode->i_sb;
  4797. handle_t *handle;
  4798. struct ext4_ext_path *path;
  4799. struct ext4_extent *extent;
  4800. ext4_lblk_t offset_lblk, len_lblk, ee_start_lblk = 0;
  4801. unsigned int credits, ee_len;
  4802. int ret = 0, depth, split_flag = 0;
  4803. loff_t ioffset;
  4804. /*
  4805. * We need to test this early because xfstests assumes that an
  4806. * insert range of (0, 1) will return EOPNOTSUPP if the file
  4807. * system does not support insert range.
  4808. */
  4809. if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
  4810. return -EOPNOTSUPP;
  4811. /* Insert range works only on fs cluster size aligned regions. */
  4812. if (!IS_ALIGNED(offset | len, EXT4_CLUSTER_SIZE(sb)))
  4813. return -EINVAL;
  4814. trace_ext4_insert_range(inode, offset, len);
  4815. offset_lblk = offset >> EXT4_BLOCK_SIZE_BITS(sb);
  4816. len_lblk = len >> EXT4_BLOCK_SIZE_BITS(sb);
  4817. /* Call ext4_force_commit to flush all data in case of data=journal */
  4818. if (ext4_should_journal_data(inode)) {
  4819. ret = ext4_force_commit(inode->i_sb);
  4820. if (ret)
  4821. return ret;
  4822. }
  4823. inode_lock(inode);
  4824. /* Currently just for extent based files */
  4825. if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
  4826. ret = -EOPNOTSUPP;
  4827. goto out_mutex;
  4828. }
  4829. /* Check whether the maximum file size would be exceeded */
  4830. if (len > inode->i_sb->s_maxbytes - inode->i_size) {
  4831. ret = -EFBIG;
  4832. goto out_mutex;
  4833. }
  4834. /* Offset must be less than i_size */
  4835. if (offset >= inode->i_size) {
  4836. ret = -EINVAL;
  4837. goto out_mutex;
  4838. }
  4839. /* Wait for existing dio to complete */
  4840. inode_dio_wait(inode);
  4841. ret = file_modified(file);
  4842. if (ret)
  4843. goto out_mutex;
  4844. /*
  4845. * Prevent page faults from reinstantiating pages we have released from
  4846. * page cache.
  4847. */
  4848. down_write(&EXT4_I(inode)->i_mmap_sem);
  4849. ret = ext4_break_layouts(inode);
  4850. if (ret)
  4851. goto out_mmap;
  4852. /*
  4853. * Need to round down to align start offset to page size boundary
  4854. * for page size > block size.
  4855. */
  4856. ioffset = round_down(offset, PAGE_SIZE);
  4857. /* Write out all dirty pages */
  4858. ret = filemap_write_and_wait_range(inode->i_mapping, ioffset,
  4859. LLONG_MAX);
  4860. if (ret)
  4861. goto out_mmap;
  4862. truncate_pagecache(inode, ioffset);
  4863. credits = ext4_writepage_trans_blocks(inode);
  4864. handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
  4865. if (IS_ERR(handle)) {
  4866. ret = PTR_ERR(handle);
  4867. goto out_mmap;
  4868. }
  4869. ext4_fc_start_ineligible(sb, EXT4_FC_REASON_FALLOC_RANGE);
  4870. /* Expand file to avoid data loss if there is error while shifting */
  4871. inode->i_size += len;
  4872. EXT4_I(inode)->i_disksize += len;
  4873. inode->i_mtime = inode->i_ctime = current_time(inode);
  4874. ret = ext4_mark_inode_dirty(handle, inode);
  4875. if (ret)
  4876. goto out_stop;
  4877. down_write(&EXT4_I(inode)->i_data_sem);
  4878. ext4_discard_preallocations(inode, 0);
  4879. path = ext4_find_extent(inode, offset_lblk, NULL, 0);
  4880. if (IS_ERR(path)) {
  4881. up_write(&EXT4_I(inode)->i_data_sem);
  4882. goto out_stop;
  4883. }
  4884. depth = ext_depth(inode);
  4885. extent = path[depth].p_ext;
  4886. if (extent) {
  4887. ee_start_lblk = le32_to_cpu(extent->ee_block);
  4888. ee_len = ext4_ext_get_actual_len(extent);
  4889. /*
  4890. * If offset_lblk is not the starting block of extent, split
  4891. * the extent @offset_lblk
  4892. */
  4893. if ((offset_lblk > ee_start_lblk) &&
  4894. (offset_lblk < (ee_start_lblk + ee_len))) {
  4895. if (ext4_ext_is_unwritten(extent))
  4896. split_flag = EXT4_EXT_MARK_UNWRIT1 |
  4897. EXT4_EXT_MARK_UNWRIT2;
  4898. ret = ext4_split_extent_at(handle, inode, &path,
  4899. offset_lblk, split_flag,
  4900. EXT4_EX_NOCACHE |
  4901. EXT4_GET_BLOCKS_PRE_IO |
  4902. EXT4_GET_BLOCKS_METADATA_NOFAIL);
  4903. }
  4904. ext4_ext_drop_refs(path);
  4905. kfree(path);
  4906. if (ret < 0) {
  4907. up_write(&EXT4_I(inode)->i_data_sem);
  4908. goto out_stop;
  4909. }
  4910. } else {
  4911. ext4_ext_drop_refs(path);
  4912. kfree(path);
  4913. }
  4914. ret = ext4_es_remove_extent(inode, offset_lblk,
  4915. EXT_MAX_BLOCKS - offset_lblk);
  4916. if (ret) {
  4917. up_write(&EXT4_I(inode)->i_data_sem);
  4918. goto out_stop;
  4919. }
  4920. /*
  4921. * if offset_lblk lies in a hole which is at start of file, use
  4922. * ee_start_lblk to shift extents
  4923. */
  4924. ret = ext4_ext_shift_extents(inode, handle,
  4925. ee_start_lblk > offset_lblk ? ee_start_lblk : offset_lblk,
  4926. len_lblk, SHIFT_RIGHT);
  4927. up_write(&EXT4_I(inode)->i_data_sem);
  4928. if (IS_SYNC(inode))
  4929. ext4_handle_sync(handle);
  4930. if (ret >= 0)
  4931. ext4_update_inode_fsync_trans(handle, inode, 1);
  4932. out_stop:
  4933. ext4_journal_stop(handle);
  4934. ext4_fc_stop_ineligible(sb);
  4935. out_mmap:
  4936. up_write(&EXT4_I(inode)->i_mmap_sem);
  4937. out_mutex:
  4938. inode_unlock(inode);
  4939. return ret;
  4940. }
  4941. /**
  4942. * ext4_swap_extents() - Swap extents between two inodes
  4943. * @handle: handle for this transaction
  4944. * @inode1: First inode
  4945. * @inode2: Second inode
  4946. * @lblk1: Start block for first inode
  4947. * @lblk2: Start block for second inode
  4948. * @count: Number of blocks to swap
  4949. * @unwritten: Mark second inode's extents as unwritten after swap
  4950. * @erp: Pointer to save error value
  4951. *
  4952. * This helper routine does exactly what is promise "swap extents". All other
  4953. * stuff such as page-cache locking consistency, bh mapping consistency or
  4954. * extent's data copying must be performed by caller.
  4955. * Locking:
  4956. * i_mutex is held for both inodes
  4957. * i_data_sem is locked for write for both inodes
  4958. * Assumptions:
  4959. * All pages from requested range are locked for both inodes
  4960. */
  4961. int
  4962. ext4_swap_extents(handle_t *handle, struct inode *inode1,
  4963. struct inode *inode2, ext4_lblk_t lblk1, ext4_lblk_t lblk2,
  4964. ext4_lblk_t count, int unwritten, int *erp)
  4965. {
  4966. struct ext4_ext_path *path1 = NULL;
  4967. struct ext4_ext_path *path2 = NULL;
  4968. int replaced_count = 0;
  4969. BUG_ON(!rwsem_is_locked(&EXT4_I(inode1)->i_data_sem));
  4970. BUG_ON(!rwsem_is_locked(&EXT4_I(inode2)->i_data_sem));
  4971. BUG_ON(!inode_is_locked(inode1));
  4972. BUG_ON(!inode_is_locked(inode2));
  4973. *erp = ext4_es_remove_extent(inode1, lblk1, count);
  4974. if (unlikely(*erp))
  4975. return 0;
  4976. *erp = ext4_es_remove_extent(inode2, lblk2, count);
  4977. if (unlikely(*erp))
  4978. return 0;
  4979. while (count) {
  4980. struct ext4_extent *ex1, *ex2, tmp_ex;
  4981. ext4_lblk_t e1_blk, e2_blk;
  4982. int e1_len, e2_len, len;
  4983. int split = 0;
  4984. path1 = ext4_find_extent(inode1, lblk1, NULL, EXT4_EX_NOCACHE);
  4985. if (IS_ERR(path1)) {
  4986. *erp = PTR_ERR(path1);
  4987. path1 = NULL;
  4988. finish:
  4989. count = 0;
  4990. goto repeat;
  4991. }
  4992. path2 = ext4_find_extent(inode2, lblk2, NULL, EXT4_EX_NOCACHE);
  4993. if (IS_ERR(path2)) {
  4994. *erp = PTR_ERR(path2);
  4995. path2 = NULL;
  4996. goto finish;
  4997. }
  4998. ex1 = path1[path1->p_depth].p_ext;
  4999. ex2 = path2[path2->p_depth].p_ext;
  5000. /* Do we have something to swap ? */
  5001. if (unlikely(!ex2 || !ex1))
  5002. goto finish;
  5003. e1_blk = le32_to_cpu(ex1->ee_block);
  5004. e2_blk = le32_to_cpu(ex2->ee_block);
  5005. e1_len = ext4_ext_get_actual_len(ex1);
  5006. e2_len = ext4_ext_get_actual_len(ex2);
  5007. /* Hole handling */
  5008. if (!in_range(lblk1, e1_blk, e1_len) ||
  5009. !in_range(lblk2, e2_blk, e2_len)) {
  5010. ext4_lblk_t next1, next2;
  5011. /* if hole after extent, then go to next extent */
  5012. next1 = ext4_ext_next_allocated_block(path1);
  5013. next2 = ext4_ext_next_allocated_block(path2);
  5014. /* If hole before extent, then shift to that extent */
  5015. if (e1_blk > lblk1)
  5016. next1 = e1_blk;
  5017. if (e2_blk > lblk2)
  5018. next2 = e2_blk;
  5019. /* Do we have something to swap */
  5020. if (next1 == EXT_MAX_BLOCKS || next2 == EXT_MAX_BLOCKS)
  5021. goto finish;
  5022. /* Move to the rightest boundary */
  5023. len = next1 - lblk1;
  5024. if (len < next2 - lblk2)
  5025. len = next2 - lblk2;
  5026. if (len > count)
  5027. len = count;
  5028. lblk1 += len;
  5029. lblk2 += len;
  5030. count -= len;
  5031. goto repeat;
  5032. }
  5033. /* Prepare left boundary */
  5034. if (e1_blk < lblk1) {
  5035. split = 1;
  5036. *erp = ext4_force_split_extent_at(handle, inode1,
  5037. &path1, lblk1, 0);
  5038. if (unlikely(*erp))
  5039. goto finish;
  5040. }
  5041. if (e2_blk < lblk2) {
  5042. split = 1;
  5043. *erp = ext4_force_split_extent_at(handle, inode2,
  5044. &path2, lblk2, 0);
  5045. if (unlikely(*erp))
  5046. goto finish;
  5047. }
  5048. /* ext4_split_extent_at() may result in leaf extent split,
  5049. * path must to be revalidated. */
  5050. if (split)
  5051. goto repeat;
  5052. /* Prepare right boundary */
  5053. len = count;
  5054. if (len > e1_blk + e1_len - lblk1)
  5055. len = e1_blk + e1_len - lblk1;
  5056. if (len > e2_blk + e2_len - lblk2)
  5057. len = e2_blk + e2_len - lblk2;
  5058. if (len != e1_len) {
  5059. split = 1;
  5060. *erp = ext4_force_split_extent_at(handle, inode1,
  5061. &path1, lblk1 + len, 0);
  5062. if (unlikely(*erp))
  5063. goto finish;
  5064. }
  5065. if (len != e2_len) {
  5066. split = 1;
  5067. *erp = ext4_force_split_extent_at(handle, inode2,
  5068. &path2, lblk2 + len, 0);
  5069. if (*erp)
  5070. goto finish;
  5071. }
  5072. /* ext4_split_extent_at() may result in leaf extent split,
  5073. * path must to be revalidated. */
  5074. if (split)
  5075. goto repeat;
  5076. BUG_ON(e2_len != e1_len);
  5077. *erp = ext4_ext_get_access(handle, inode1, path1 + path1->p_depth);
  5078. if (unlikely(*erp))
  5079. goto finish;
  5080. *erp = ext4_ext_get_access(handle, inode2, path2 + path2->p_depth);
  5081. if (unlikely(*erp))
  5082. goto finish;
  5083. /* Both extents are fully inside boundaries. Swap it now */
  5084. tmp_ex = *ex1;
  5085. ext4_ext_store_pblock(ex1, ext4_ext_pblock(ex2));
  5086. ext4_ext_store_pblock(ex2, ext4_ext_pblock(&tmp_ex));
  5087. ex1->ee_len = cpu_to_le16(e2_len);
  5088. ex2->ee_len = cpu_to_le16(e1_len);
  5089. if (unwritten)
  5090. ext4_ext_mark_unwritten(ex2);
  5091. if (ext4_ext_is_unwritten(&tmp_ex))
  5092. ext4_ext_mark_unwritten(ex1);
  5093. ext4_ext_try_to_merge(handle, inode2, path2, ex2);
  5094. ext4_ext_try_to_merge(handle, inode1, path1, ex1);
  5095. *erp = ext4_ext_dirty(handle, inode2, path2 +
  5096. path2->p_depth);
  5097. if (unlikely(*erp))
  5098. goto finish;
  5099. *erp = ext4_ext_dirty(handle, inode1, path1 +
  5100. path1->p_depth);
  5101. /*
  5102. * Looks scarry ah..? second inode already points to new blocks,
  5103. * and it was successfully dirtied. But luckily error may happen
  5104. * only due to journal error, so full transaction will be
  5105. * aborted anyway.
  5106. */
  5107. if (unlikely(*erp))
  5108. goto finish;
  5109. lblk1 += len;
  5110. lblk2 += len;
  5111. replaced_count += len;
  5112. count -= len;
  5113. repeat:
  5114. ext4_ext_drop_refs(path1);
  5115. kfree(path1);
  5116. ext4_ext_drop_refs(path2);
  5117. kfree(path2);
  5118. path1 = path2 = NULL;
  5119. }
  5120. return replaced_count;
  5121. }
  5122. /*
  5123. * ext4_clu_mapped - determine whether any block in a logical cluster has
  5124. * been mapped to a physical cluster
  5125. *
  5126. * @inode - file containing the logical cluster
  5127. * @lclu - logical cluster of interest
  5128. *
  5129. * Returns 1 if any block in the logical cluster is mapped, signifying
  5130. * that a physical cluster has been allocated for it. Otherwise,
  5131. * returns 0. Can also return negative error codes. Derived from
  5132. * ext4_ext_map_blocks().
  5133. */
  5134. int ext4_clu_mapped(struct inode *inode, ext4_lblk_t lclu)
  5135. {
  5136. struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  5137. struct ext4_ext_path *path;
  5138. int depth, mapped = 0, err = 0;
  5139. struct ext4_extent *extent;
  5140. ext4_lblk_t first_lblk, first_lclu, last_lclu;
  5141. /* search for the extent closest to the first block in the cluster */
  5142. path = ext4_find_extent(inode, EXT4_C2B(sbi, lclu), NULL, 0);
  5143. if (IS_ERR(path)) {
  5144. err = PTR_ERR(path);
  5145. path = NULL;
  5146. goto out;
  5147. }
  5148. depth = ext_depth(inode);
  5149. /*
  5150. * A consistent leaf must not be empty. This situation is possible,
  5151. * though, _during_ tree modification, and it's why an assert can't
  5152. * be put in ext4_find_extent().
  5153. */
  5154. if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
  5155. EXT4_ERROR_INODE(inode,
  5156. "bad extent address - lblock: %lu, depth: %d, pblock: %lld",
  5157. (unsigned long) EXT4_C2B(sbi, lclu),
  5158. depth, path[depth].p_block);
  5159. err = -EFSCORRUPTED;
  5160. goto out;
  5161. }
  5162. extent = path[depth].p_ext;
  5163. /* can't be mapped if the extent tree is empty */
  5164. if (extent == NULL)
  5165. goto out;
  5166. first_lblk = le32_to_cpu(extent->ee_block);
  5167. first_lclu = EXT4_B2C(sbi, first_lblk);
  5168. /*
  5169. * Three possible outcomes at this point - found extent spanning
  5170. * the target cluster, to the left of the target cluster, or to the
  5171. * right of the target cluster. The first two cases are handled here.
  5172. * The last case indicates the target cluster is not mapped.
  5173. */
  5174. if (lclu >= first_lclu) {
  5175. last_lclu = EXT4_B2C(sbi, first_lblk +
  5176. ext4_ext_get_actual_len(extent) - 1);
  5177. if (lclu <= last_lclu) {
  5178. mapped = 1;
  5179. } else {
  5180. first_lblk = ext4_ext_next_allocated_block(path);
  5181. first_lclu = EXT4_B2C(sbi, first_lblk);
  5182. if (lclu == first_lclu)
  5183. mapped = 1;
  5184. }
  5185. }
  5186. out:
  5187. ext4_ext_drop_refs(path);
  5188. kfree(path);
  5189. return err ? err : mapped;
  5190. }
  5191. /*
  5192. * Updates physical block address and unwritten status of extent
  5193. * starting at lblk start and of len. If such an extent doesn't exist,
  5194. * this function splits the extent tree appropriately to create an
  5195. * extent like this. This function is called in the fast commit
  5196. * replay path. Returns 0 on success and error on failure.
  5197. */
  5198. int ext4_ext_replay_update_ex(struct inode *inode, ext4_lblk_t start,
  5199. int len, int unwritten, ext4_fsblk_t pblk)
  5200. {
  5201. struct ext4_ext_path *path = NULL, *ppath;
  5202. struct ext4_extent *ex;
  5203. int ret;
  5204. path = ext4_find_extent(inode, start, NULL, 0);
  5205. if (IS_ERR(path))
  5206. return PTR_ERR(path);
  5207. ex = path[path->p_depth].p_ext;
  5208. if (!ex) {
  5209. ret = -EFSCORRUPTED;
  5210. goto out;
  5211. }
  5212. if (le32_to_cpu(ex->ee_block) != start ||
  5213. ext4_ext_get_actual_len(ex) != len) {
  5214. /* We need to split this extent to match our extent first */
  5215. ppath = path;
  5216. down_write(&EXT4_I(inode)->i_data_sem);
  5217. ret = ext4_force_split_extent_at(NULL, inode, &ppath, start, 1);
  5218. up_write(&EXT4_I(inode)->i_data_sem);
  5219. if (ret)
  5220. goto out;
  5221. kfree(path);
  5222. path = ext4_find_extent(inode, start, NULL, 0);
  5223. if (IS_ERR(path))
  5224. return -1;
  5225. ppath = path;
  5226. ex = path[path->p_depth].p_ext;
  5227. WARN_ON(le32_to_cpu(ex->ee_block) != start);
  5228. if (ext4_ext_get_actual_len(ex) != len) {
  5229. down_write(&EXT4_I(inode)->i_data_sem);
  5230. ret = ext4_force_split_extent_at(NULL, inode, &ppath,
  5231. start + len, 1);
  5232. up_write(&EXT4_I(inode)->i_data_sem);
  5233. if (ret)
  5234. goto out;
  5235. kfree(path);
  5236. path = ext4_find_extent(inode, start, NULL, 0);
  5237. if (IS_ERR(path))
  5238. return -EINVAL;
  5239. ex = path[path->p_depth].p_ext;
  5240. }
  5241. }
  5242. if (unwritten)
  5243. ext4_ext_mark_unwritten(ex);
  5244. else
  5245. ext4_ext_mark_initialized(ex);
  5246. ext4_ext_store_pblock(ex, pblk);
  5247. down_write(&EXT4_I(inode)->i_data_sem);
  5248. ret = ext4_ext_dirty(NULL, inode, &path[path->p_depth]);
  5249. up_write(&EXT4_I(inode)->i_data_sem);
  5250. out:
  5251. ext4_ext_drop_refs(path);
  5252. kfree(path);
  5253. ext4_mark_inode_dirty(NULL, inode);
  5254. return ret;
  5255. }
  5256. /* Try to shrink the extent tree */
  5257. void ext4_ext_replay_shrink_inode(struct inode *inode, ext4_lblk_t end)
  5258. {
  5259. struct ext4_ext_path *path = NULL;
  5260. struct ext4_extent *ex;
  5261. ext4_lblk_t old_cur, cur = 0;
  5262. while (cur < end) {
  5263. path = ext4_find_extent(inode, cur, NULL, 0);
  5264. if (IS_ERR(path))
  5265. return;
  5266. ex = path[path->p_depth].p_ext;
  5267. if (!ex) {
  5268. ext4_ext_drop_refs(path);
  5269. kfree(path);
  5270. ext4_mark_inode_dirty(NULL, inode);
  5271. return;
  5272. }
  5273. old_cur = cur;
  5274. cur = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
  5275. if (cur <= old_cur)
  5276. cur = old_cur + 1;
  5277. ext4_ext_try_to_merge(NULL, inode, path, ex);
  5278. down_write(&EXT4_I(inode)->i_data_sem);
  5279. ext4_ext_dirty(NULL, inode, &path[path->p_depth]);
  5280. up_write(&EXT4_I(inode)->i_data_sem);
  5281. ext4_mark_inode_dirty(NULL, inode);
  5282. ext4_ext_drop_refs(path);
  5283. kfree(path);
  5284. }
  5285. }
  5286. /* Check if *cur is a hole and if it is, skip it */
  5287. static int skip_hole(struct inode *inode, ext4_lblk_t *cur)
  5288. {
  5289. int ret;
  5290. struct ext4_map_blocks map;
  5291. map.m_lblk = *cur;
  5292. map.m_len = ((inode->i_size) >> inode->i_sb->s_blocksize_bits) - *cur;
  5293. ret = ext4_map_blocks(NULL, inode, &map, 0);
  5294. if (ret < 0)
  5295. return ret;
  5296. if (ret != 0)
  5297. return 0;
  5298. *cur = *cur + map.m_len;
  5299. return 0;
  5300. }
  5301. /* Count number of blocks used by this inode and update i_blocks */
  5302. int ext4_ext_replay_set_iblocks(struct inode *inode)
  5303. {
  5304. struct ext4_ext_path *path = NULL, *path2 = NULL;
  5305. struct ext4_extent *ex;
  5306. ext4_lblk_t cur = 0, end;
  5307. int numblks = 0, i, ret = 0;
  5308. ext4_fsblk_t cmp1, cmp2;
  5309. struct ext4_map_blocks map;
  5310. /* Determin the size of the file first */
  5311. path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
  5312. EXT4_EX_NOCACHE);
  5313. if (IS_ERR(path))
  5314. return PTR_ERR(path);
  5315. ex = path[path->p_depth].p_ext;
  5316. if (!ex) {
  5317. ext4_ext_drop_refs(path);
  5318. kfree(path);
  5319. goto out;
  5320. }
  5321. end = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
  5322. ext4_ext_drop_refs(path);
  5323. kfree(path);
  5324. /* Count the number of data blocks */
  5325. cur = 0;
  5326. while (cur < end) {
  5327. map.m_lblk = cur;
  5328. map.m_len = end - cur;
  5329. ret = ext4_map_blocks(NULL, inode, &map, 0);
  5330. if (ret < 0)
  5331. break;
  5332. if (ret > 0)
  5333. numblks += ret;
  5334. cur = cur + map.m_len;
  5335. }
  5336. /*
  5337. * Count the number of extent tree blocks. We do it by looking up
  5338. * two successive extents and determining the difference between
  5339. * their paths. When path is different for 2 successive extents
  5340. * we compare the blocks in the path at each level and increment
  5341. * iblocks by total number of differences found.
  5342. */
  5343. cur = 0;
  5344. ret = skip_hole(inode, &cur);
  5345. if (ret < 0)
  5346. goto out;
  5347. path = ext4_find_extent(inode, cur, NULL, 0);
  5348. if (IS_ERR(path))
  5349. goto out;
  5350. numblks += path->p_depth;
  5351. ext4_ext_drop_refs(path);
  5352. kfree(path);
  5353. while (cur < end) {
  5354. path = ext4_find_extent(inode, cur, NULL, 0);
  5355. if (IS_ERR(path))
  5356. break;
  5357. ex = path[path->p_depth].p_ext;
  5358. if (!ex) {
  5359. ext4_ext_drop_refs(path);
  5360. kfree(path);
  5361. return 0;
  5362. }
  5363. cur = max(cur + 1, le32_to_cpu(ex->ee_block) +
  5364. ext4_ext_get_actual_len(ex));
  5365. ret = skip_hole(inode, &cur);
  5366. if (ret < 0) {
  5367. ext4_ext_drop_refs(path);
  5368. kfree(path);
  5369. break;
  5370. }
  5371. path2 = ext4_find_extent(inode, cur, NULL, 0);
  5372. if (IS_ERR(path2)) {
  5373. ext4_ext_drop_refs(path);
  5374. kfree(path);
  5375. break;
  5376. }
  5377. ex = path2[path2->p_depth].p_ext;
  5378. for (i = 0; i <= max(path->p_depth, path2->p_depth); i++) {
  5379. cmp1 = cmp2 = 0;
  5380. if (i <= path->p_depth)
  5381. cmp1 = path[i].p_bh ?
  5382. path[i].p_bh->b_blocknr : 0;
  5383. if (i <= path2->p_depth)
  5384. cmp2 = path2[i].p_bh ?
  5385. path2[i].p_bh->b_blocknr : 0;
  5386. if (cmp1 != cmp2 && cmp2 != 0)
  5387. numblks++;
  5388. }
  5389. ext4_ext_drop_refs(path);
  5390. ext4_ext_drop_refs(path2);
  5391. kfree(path);
  5392. kfree(path2);
  5393. }
  5394. out:
  5395. inode->i_blocks = numblks << (inode->i_sb->s_blocksize_bits - 9);
  5396. ext4_mark_inode_dirty(NULL, inode);
  5397. return 0;
  5398. }
  5399. int ext4_ext_clear_bb(struct inode *inode)
  5400. {
  5401. struct ext4_ext_path *path = NULL;
  5402. struct ext4_extent *ex;
  5403. ext4_lblk_t cur = 0, end;
  5404. int j, ret = 0;
  5405. struct ext4_map_blocks map;
  5406. /* Determin the size of the file first */
  5407. path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
  5408. EXT4_EX_NOCACHE);
  5409. if (IS_ERR(path))
  5410. return PTR_ERR(path);
  5411. ex = path[path->p_depth].p_ext;
  5412. if (!ex) {
  5413. ext4_ext_drop_refs(path);
  5414. kfree(path);
  5415. return 0;
  5416. }
  5417. end = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
  5418. ext4_ext_drop_refs(path);
  5419. kfree(path);
  5420. cur = 0;
  5421. while (cur < end) {
  5422. map.m_lblk = cur;
  5423. map.m_len = end - cur;
  5424. ret = ext4_map_blocks(NULL, inode, &map, 0);
  5425. if (ret < 0)
  5426. break;
  5427. if (ret > 0) {
  5428. path = ext4_find_extent(inode, map.m_lblk, NULL, 0);
  5429. if (!IS_ERR_OR_NULL(path)) {
  5430. for (j = 0; j < path->p_depth; j++) {
  5431. ext4_mb_mark_bb(inode->i_sb,
  5432. path[j].p_block, 1, 0);
  5433. ext4_fc_record_regions(inode->i_sb, inode->i_ino,
  5434. 0, path[j].p_block, 1, 1);
  5435. }
  5436. ext4_ext_drop_refs(path);
  5437. kfree(path);
  5438. }
  5439. ext4_mb_mark_bb(inode->i_sb, map.m_pblk, map.m_len, 0);
  5440. ext4_fc_record_regions(inode->i_sb, inode->i_ino,
  5441. map.m_lblk, map.m_pblk, map.m_len, 1);
  5442. }
  5443. cur = cur + map.m_len;
  5444. }
  5445. return 0;
  5446. }