ctree.c 146 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572457345744575457645774578457945804581458245834584458545864587458845894590459145924593459445954596459745984599460046014602460346044605460646074608460946104611461246134614461546164617461846194620462146224623462446254626462746284629463046314632463346344635463646374638463946404641464246434644464546464647464846494650465146524653465446554656465746584659466046614662466346644665466646674668466946704671467246734674467546764677467846794680468146824683468446854686468746884689469046914692469346944695469646974698469947004701470247034704470547064707470847094710471147124713471447154716471747184719472047214722472347244725472647274728472947304731473247334734473547364737473847394740474147424743474447454746474747484749475047514752475347544755475647574758475947604761476247634764476547664767476847694770477147724773477447754776477747784779478047814782478347844785478647874788478947904791479247934794479547964797479847994800480148024803480448054806480748084809481048114812481348144815481648174818481948204821482248234824482548264827482848294830483148324833483448354836483748384839484048414842484348444845484648474848484948504851485248534854485548564857485848594860486148624863486448654866486748684869487048714872487348744875487648774878487948804881488248834884488548864887488848894890489148924893489448954896489748984899490049014902490349044905490649074908490949104911491249134914491549164917491849194920492149224923492449254926492749284929493049314932493349344935493649374938493949404941494249434944494549464947494849494950495149524953495449554956495749584959496049614962496349644965496649674968496949704971497249734974497549764977497849794980498149824983498449854986498749884989499049914992499349944995499649974998499950005001500250035004500550065007500850095010501150125013501450155016501750185019502050215022502350245025502650275028502950305031503250335034503550365037503850395040504150425043504450455046504750485049505050515052505350545055505650575058505950605061506250635064506550665067506850695070507150725073507450755076507750785079508050815082508350845085508650875088508950905091509250935094509550965097509850995100510151025103510451055106510751085109511051115112511351145115511651175118511951205121512251235124512551265127512851295130513151325133513451355136513751385139514051415142514351445145514651475148514951505151515251535154515551565157515851595160516151625163516451655166516751685169517051715172517351745175517651775178517951805181518251835184518551865187518851895190519151925193519451955196519751985199520052015202520352045205520652075208520952105211521252135214521552165217521852195220522152225223522452255226522752285229523052315232523352345235523652375238523952405241524252435244524552465247524852495250525152525253525452555256525752585259526052615262526352645265526652675268526952705271527252735274527552765277527852795280528152825283528452855286528752885289529052915292529352945295529652975298529953005301530253035304530553065307530853095310531153125313531453155316531753185319532053215322532353245325532653275328532953305331533253335334533553365337533853395340534153425343534453455346534753485349535053515352535353545355535653575358535953605361536253635364536553665367536853695370537153725373537453755376537753785379538053815382538353845385538653875388538953905391539253935394539553965397539853995400540154025403540454055406540754085409541054115412541354145415541654175418541954205421542254235424542554265427542854295430543154325433543454355436543754385439544054415442544354445445544654475448544954505451545254535454545554565457545854595460546154625463546454655466546754685469547054715472547354745475547654775478547954805481548254835484548554865487548854895490549154925493549454955496549754985499550055015502550355045505550655075508550955105511551255135514551555165517551855195520552155225523552455255526552755285529553055315532553355345535553655375538553955405541554255435544554555465547554855495550555155525553555455555556555755585559556055615562556355645565556655675568556955705571557255735574557555765577557855795580558155825583558455855586558755885589559055915592559355945595559655975598559956005601560256035604560556065607560856095610561156125613561456155616561756185619562056215622562356245625562656275628562956305631563256335634563556365637563856395640564156425643564456455646564756485649565056515652565356545655565656575658565956605661566256635664566556665667566856695670
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (C) 2007,2008 Oracle. All rights reserved.
  4. */
  5. #include <linux/sched.h>
  6. #include <linux/slab.h>
  7. #include <linux/rbtree.h>
  8. #include <linux/mm.h>
  9. #include "ctree.h"
  10. #include "disk-io.h"
  11. #include "transaction.h"
  12. #include "print-tree.h"
  13. #include "locking.h"
  14. #include "volumes.h"
  15. #include "qgroup.h"
  16. static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
  17. *root, struct btrfs_path *path, int level);
  18. static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  19. const struct btrfs_key *ins_key, struct btrfs_path *path,
  20. int data_size, int extend);
  21. static int push_node_left(struct btrfs_trans_handle *trans,
  22. struct extent_buffer *dst,
  23. struct extent_buffer *src, int empty);
  24. static int balance_node_right(struct btrfs_trans_handle *trans,
  25. struct extent_buffer *dst_buf,
  26. struct extent_buffer *src_buf);
  27. static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
  28. int level, int slot);
  29. static const struct btrfs_csums {
  30. u16 size;
  31. const char name[10];
  32. const char driver[12];
  33. } btrfs_csums[] = {
  34. [BTRFS_CSUM_TYPE_CRC32] = { .size = 4, .name = "crc32c" },
  35. [BTRFS_CSUM_TYPE_XXHASH] = { .size = 8, .name = "xxhash64" },
  36. [BTRFS_CSUM_TYPE_SHA256] = { .size = 32, .name = "sha256" },
  37. [BTRFS_CSUM_TYPE_BLAKE2] = { .size = 32, .name = "blake2b",
  38. .driver = "blake2b-256" },
  39. };
  40. int btrfs_super_csum_size(const struct btrfs_super_block *s)
  41. {
  42. u16 t = btrfs_super_csum_type(s);
  43. /*
  44. * csum type is validated at mount time
  45. */
  46. return btrfs_csums[t].size;
  47. }
  48. const char *btrfs_super_csum_name(u16 csum_type)
  49. {
  50. /* csum type is validated at mount time */
  51. return btrfs_csums[csum_type].name;
  52. }
  53. /*
  54. * Return driver name if defined, otherwise the name that's also a valid driver
  55. * name
  56. */
  57. const char *btrfs_super_csum_driver(u16 csum_type)
  58. {
  59. /* csum type is validated at mount time */
  60. return btrfs_csums[csum_type].driver[0] ?
  61. btrfs_csums[csum_type].driver :
  62. btrfs_csums[csum_type].name;
  63. }
  64. size_t __attribute_const__ btrfs_get_num_csums(void)
  65. {
  66. return ARRAY_SIZE(btrfs_csums);
  67. }
  68. struct btrfs_path *btrfs_alloc_path(void)
  69. {
  70. return kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
  71. }
  72. /* this also releases the path */
  73. void btrfs_free_path(struct btrfs_path *p)
  74. {
  75. if (!p)
  76. return;
  77. btrfs_release_path(p);
  78. kmem_cache_free(btrfs_path_cachep, p);
  79. }
  80. /*
  81. * path release drops references on the extent buffers in the path
  82. * and it drops any locks held by this path
  83. *
  84. * It is safe to call this on paths that no locks or extent buffers held.
  85. */
  86. noinline void btrfs_release_path(struct btrfs_path *p)
  87. {
  88. int i;
  89. for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  90. p->slots[i] = 0;
  91. if (!p->nodes[i])
  92. continue;
  93. if (p->locks[i]) {
  94. btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]);
  95. p->locks[i] = 0;
  96. }
  97. free_extent_buffer(p->nodes[i]);
  98. p->nodes[i] = NULL;
  99. }
  100. }
  101. /*
  102. * safely gets a reference on the root node of a tree. A lock
  103. * is not taken, so a concurrent writer may put a different node
  104. * at the root of the tree. See btrfs_lock_root_node for the
  105. * looping required.
  106. *
  107. * The extent buffer returned by this has a reference taken, so
  108. * it won't disappear. It may stop being the root of the tree
  109. * at any time because there are no locks held.
  110. */
  111. struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
  112. {
  113. struct extent_buffer *eb;
  114. while (1) {
  115. rcu_read_lock();
  116. eb = rcu_dereference(root->node);
  117. /*
  118. * RCU really hurts here, we could free up the root node because
  119. * it was COWed but we may not get the new root node yet so do
  120. * the inc_not_zero dance and if it doesn't work then
  121. * synchronize_rcu and try again.
  122. */
  123. if (atomic_inc_not_zero(&eb->refs)) {
  124. rcu_read_unlock();
  125. break;
  126. }
  127. rcu_read_unlock();
  128. synchronize_rcu();
  129. }
  130. return eb;
  131. }
  132. /*
  133. * Cowonly root (not-shareable trees, everything not subvolume or reloc roots),
  134. * just get put onto a simple dirty list. Transaction walks this list to make
  135. * sure they get properly updated on disk.
  136. */
  137. static void add_root_to_dirty_list(struct btrfs_root *root)
  138. {
  139. struct btrfs_fs_info *fs_info = root->fs_info;
  140. if (test_bit(BTRFS_ROOT_DIRTY, &root->state) ||
  141. !test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state))
  142. return;
  143. spin_lock(&fs_info->trans_lock);
  144. if (!test_and_set_bit(BTRFS_ROOT_DIRTY, &root->state)) {
  145. /* Want the extent tree to be the last on the list */
  146. if (root->root_key.objectid == BTRFS_EXTENT_TREE_OBJECTID)
  147. list_move_tail(&root->dirty_list,
  148. &fs_info->dirty_cowonly_roots);
  149. else
  150. list_move(&root->dirty_list,
  151. &fs_info->dirty_cowonly_roots);
  152. }
  153. spin_unlock(&fs_info->trans_lock);
  154. }
  155. /*
  156. * used by snapshot creation to make a copy of a root for a tree with
  157. * a given objectid. The buffer with the new root node is returned in
  158. * cow_ret, and this func returns zero on success or a negative error code.
  159. */
  160. int btrfs_copy_root(struct btrfs_trans_handle *trans,
  161. struct btrfs_root *root,
  162. struct extent_buffer *buf,
  163. struct extent_buffer **cow_ret, u64 new_root_objectid)
  164. {
  165. struct btrfs_fs_info *fs_info = root->fs_info;
  166. struct extent_buffer *cow;
  167. int ret = 0;
  168. int level;
  169. struct btrfs_disk_key disk_key;
  170. WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
  171. trans->transid != fs_info->running_transaction->transid);
  172. WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
  173. trans->transid != root->last_trans);
  174. level = btrfs_header_level(buf);
  175. if (level == 0)
  176. btrfs_item_key(buf, &disk_key, 0);
  177. else
  178. btrfs_node_key(buf, &disk_key, 0);
  179. cow = btrfs_alloc_tree_block(trans, root, 0, new_root_objectid,
  180. &disk_key, level, buf->start, 0,
  181. BTRFS_NESTING_NEW_ROOT);
  182. if (IS_ERR(cow))
  183. return PTR_ERR(cow);
  184. copy_extent_buffer_full(cow, buf);
  185. btrfs_set_header_bytenr(cow, cow->start);
  186. btrfs_set_header_generation(cow, trans->transid);
  187. btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
  188. btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
  189. BTRFS_HEADER_FLAG_RELOC);
  190. if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
  191. btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
  192. else
  193. btrfs_set_header_owner(cow, new_root_objectid);
  194. write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid);
  195. WARN_ON(btrfs_header_generation(buf) > trans->transid);
  196. if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
  197. ret = btrfs_inc_ref(trans, root, cow, 1);
  198. else
  199. ret = btrfs_inc_ref(trans, root, cow, 0);
  200. if (ret) {
  201. btrfs_tree_unlock(cow);
  202. free_extent_buffer(cow);
  203. btrfs_abort_transaction(trans, ret);
  204. return ret;
  205. }
  206. btrfs_mark_buffer_dirty(cow);
  207. *cow_ret = cow;
  208. return 0;
  209. }
  210. enum mod_log_op {
  211. MOD_LOG_KEY_REPLACE,
  212. MOD_LOG_KEY_ADD,
  213. MOD_LOG_KEY_REMOVE,
  214. MOD_LOG_KEY_REMOVE_WHILE_FREEING,
  215. MOD_LOG_KEY_REMOVE_WHILE_MOVING,
  216. MOD_LOG_MOVE_KEYS,
  217. MOD_LOG_ROOT_REPLACE,
  218. };
  219. struct tree_mod_root {
  220. u64 logical;
  221. u8 level;
  222. };
  223. struct tree_mod_elem {
  224. struct rb_node node;
  225. u64 logical;
  226. u64 seq;
  227. enum mod_log_op op;
  228. /* this is used for MOD_LOG_KEY_* and MOD_LOG_MOVE_KEYS operations */
  229. int slot;
  230. /* this is used for MOD_LOG_KEY* and MOD_LOG_ROOT_REPLACE */
  231. u64 generation;
  232. /* those are used for op == MOD_LOG_KEY_{REPLACE,REMOVE} */
  233. struct btrfs_disk_key key;
  234. u64 blockptr;
  235. /* this is used for op == MOD_LOG_MOVE_KEYS */
  236. struct {
  237. int dst_slot;
  238. int nr_items;
  239. } move;
  240. /* this is used for op == MOD_LOG_ROOT_REPLACE */
  241. struct tree_mod_root old_root;
  242. };
  243. /*
  244. * Pull a new tree mod seq number for our operation.
  245. */
  246. static inline u64 btrfs_inc_tree_mod_seq(struct btrfs_fs_info *fs_info)
  247. {
  248. return atomic64_inc_return(&fs_info->tree_mod_seq);
  249. }
  250. /*
  251. * This adds a new blocker to the tree mod log's blocker list if the @elem
  252. * passed does not already have a sequence number set. So when a caller expects
  253. * to record tree modifications, it should ensure to set elem->seq to zero
  254. * before calling btrfs_get_tree_mod_seq.
  255. * Returns a fresh, unused tree log modification sequence number, even if no new
  256. * blocker was added.
  257. */
  258. u64 btrfs_get_tree_mod_seq(struct btrfs_fs_info *fs_info,
  259. struct seq_list *elem)
  260. {
  261. write_lock(&fs_info->tree_mod_log_lock);
  262. if (!elem->seq) {
  263. elem->seq = btrfs_inc_tree_mod_seq(fs_info);
  264. list_add_tail(&elem->list, &fs_info->tree_mod_seq_list);
  265. }
  266. write_unlock(&fs_info->tree_mod_log_lock);
  267. return elem->seq;
  268. }
  269. void btrfs_put_tree_mod_seq(struct btrfs_fs_info *fs_info,
  270. struct seq_list *elem)
  271. {
  272. struct rb_root *tm_root;
  273. struct rb_node *node;
  274. struct rb_node *next;
  275. struct tree_mod_elem *tm;
  276. u64 min_seq = (u64)-1;
  277. u64 seq_putting = elem->seq;
  278. if (!seq_putting)
  279. return;
  280. write_lock(&fs_info->tree_mod_log_lock);
  281. list_del(&elem->list);
  282. elem->seq = 0;
  283. if (!list_empty(&fs_info->tree_mod_seq_list)) {
  284. struct seq_list *first;
  285. first = list_first_entry(&fs_info->tree_mod_seq_list,
  286. struct seq_list, list);
  287. if (seq_putting > first->seq) {
  288. /*
  289. * Blocker with lower sequence number exists, we
  290. * cannot remove anything from the log.
  291. */
  292. write_unlock(&fs_info->tree_mod_log_lock);
  293. return;
  294. }
  295. min_seq = first->seq;
  296. }
  297. /*
  298. * anything that's lower than the lowest existing (read: blocked)
  299. * sequence number can be removed from the tree.
  300. */
  301. tm_root = &fs_info->tree_mod_log;
  302. for (node = rb_first(tm_root); node; node = next) {
  303. next = rb_next(node);
  304. tm = rb_entry(node, struct tree_mod_elem, node);
  305. if (tm->seq >= min_seq)
  306. continue;
  307. rb_erase(node, tm_root);
  308. kfree(tm);
  309. }
  310. write_unlock(&fs_info->tree_mod_log_lock);
  311. }
  312. /*
  313. * key order of the log:
  314. * node/leaf start address -> sequence
  315. *
  316. * The 'start address' is the logical address of the *new* root node
  317. * for root replace operations, or the logical address of the affected
  318. * block for all other operations.
  319. */
  320. static noinline int
  321. __tree_mod_log_insert(struct btrfs_fs_info *fs_info, struct tree_mod_elem *tm)
  322. {
  323. struct rb_root *tm_root;
  324. struct rb_node **new;
  325. struct rb_node *parent = NULL;
  326. struct tree_mod_elem *cur;
  327. lockdep_assert_held_write(&fs_info->tree_mod_log_lock);
  328. tm->seq = btrfs_inc_tree_mod_seq(fs_info);
  329. tm_root = &fs_info->tree_mod_log;
  330. new = &tm_root->rb_node;
  331. while (*new) {
  332. cur = rb_entry(*new, struct tree_mod_elem, node);
  333. parent = *new;
  334. if (cur->logical < tm->logical)
  335. new = &((*new)->rb_left);
  336. else if (cur->logical > tm->logical)
  337. new = &((*new)->rb_right);
  338. else if (cur->seq < tm->seq)
  339. new = &((*new)->rb_left);
  340. else if (cur->seq > tm->seq)
  341. new = &((*new)->rb_right);
  342. else
  343. return -EEXIST;
  344. }
  345. rb_link_node(&tm->node, parent, new);
  346. rb_insert_color(&tm->node, tm_root);
  347. return 0;
  348. }
  349. /*
  350. * Determines if logging can be omitted. Returns 1 if it can. Otherwise, it
  351. * returns zero with the tree_mod_log_lock acquired. The caller must hold
  352. * this until all tree mod log insertions are recorded in the rb tree and then
  353. * write unlock fs_info::tree_mod_log_lock.
  354. */
  355. static inline int tree_mod_dont_log(struct btrfs_fs_info *fs_info,
  356. struct extent_buffer *eb) {
  357. smp_mb();
  358. if (list_empty(&(fs_info)->tree_mod_seq_list))
  359. return 1;
  360. if (eb && btrfs_header_level(eb) == 0)
  361. return 1;
  362. write_lock(&fs_info->tree_mod_log_lock);
  363. if (list_empty(&(fs_info)->tree_mod_seq_list)) {
  364. write_unlock(&fs_info->tree_mod_log_lock);
  365. return 1;
  366. }
  367. return 0;
  368. }
  369. /* Similar to tree_mod_dont_log, but doesn't acquire any locks. */
  370. static inline int tree_mod_need_log(const struct btrfs_fs_info *fs_info,
  371. struct extent_buffer *eb)
  372. {
  373. smp_mb();
  374. if (list_empty(&(fs_info)->tree_mod_seq_list))
  375. return 0;
  376. if (eb && btrfs_header_level(eb) == 0)
  377. return 0;
  378. return 1;
  379. }
  380. static struct tree_mod_elem *
  381. alloc_tree_mod_elem(struct extent_buffer *eb, int slot,
  382. enum mod_log_op op, gfp_t flags)
  383. {
  384. struct tree_mod_elem *tm;
  385. tm = kzalloc(sizeof(*tm), flags);
  386. if (!tm)
  387. return NULL;
  388. tm->logical = eb->start;
  389. if (op != MOD_LOG_KEY_ADD) {
  390. btrfs_node_key(eb, &tm->key, slot);
  391. tm->blockptr = btrfs_node_blockptr(eb, slot);
  392. }
  393. tm->op = op;
  394. tm->slot = slot;
  395. tm->generation = btrfs_node_ptr_generation(eb, slot);
  396. RB_CLEAR_NODE(&tm->node);
  397. return tm;
  398. }
  399. static noinline int tree_mod_log_insert_key(struct extent_buffer *eb, int slot,
  400. enum mod_log_op op, gfp_t flags)
  401. {
  402. struct tree_mod_elem *tm;
  403. int ret;
  404. if (!tree_mod_need_log(eb->fs_info, eb))
  405. return 0;
  406. tm = alloc_tree_mod_elem(eb, slot, op, flags);
  407. if (!tm)
  408. return -ENOMEM;
  409. if (tree_mod_dont_log(eb->fs_info, eb)) {
  410. kfree(tm);
  411. return 0;
  412. }
  413. ret = __tree_mod_log_insert(eb->fs_info, tm);
  414. write_unlock(&eb->fs_info->tree_mod_log_lock);
  415. if (ret)
  416. kfree(tm);
  417. return ret;
  418. }
  419. static noinline int tree_mod_log_insert_move(struct extent_buffer *eb,
  420. int dst_slot, int src_slot, int nr_items)
  421. {
  422. struct tree_mod_elem *tm = NULL;
  423. struct tree_mod_elem **tm_list = NULL;
  424. int ret = 0;
  425. int i;
  426. int locked = 0;
  427. if (!tree_mod_need_log(eb->fs_info, eb))
  428. return 0;
  429. tm_list = kcalloc(nr_items, sizeof(struct tree_mod_elem *), GFP_NOFS);
  430. if (!tm_list)
  431. return -ENOMEM;
  432. tm = kzalloc(sizeof(*tm), GFP_NOFS);
  433. if (!tm) {
  434. ret = -ENOMEM;
  435. goto free_tms;
  436. }
  437. tm->logical = eb->start;
  438. tm->slot = src_slot;
  439. tm->move.dst_slot = dst_slot;
  440. tm->move.nr_items = nr_items;
  441. tm->op = MOD_LOG_MOVE_KEYS;
  442. for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
  443. tm_list[i] = alloc_tree_mod_elem(eb, i + dst_slot,
  444. MOD_LOG_KEY_REMOVE_WHILE_MOVING, GFP_NOFS);
  445. if (!tm_list[i]) {
  446. ret = -ENOMEM;
  447. goto free_tms;
  448. }
  449. }
  450. if (tree_mod_dont_log(eb->fs_info, eb))
  451. goto free_tms;
  452. locked = 1;
  453. /*
  454. * When we override something during the move, we log these removals.
  455. * This can only happen when we move towards the beginning of the
  456. * buffer, i.e. dst_slot < src_slot.
  457. */
  458. for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
  459. ret = __tree_mod_log_insert(eb->fs_info, tm_list[i]);
  460. if (ret)
  461. goto free_tms;
  462. }
  463. ret = __tree_mod_log_insert(eb->fs_info, tm);
  464. if (ret)
  465. goto free_tms;
  466. write_unlock(&eb->fs_info->tree_mod_log_lock);
  467. kfree(tm_list);
  468. return 0;
  469. free_tms:
  470. for (i = 0; i < nr_items; i++) {
  471. if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
  472. rb_erase(&tm_list[i]->node, &eb->fs_info->tree_mod_log);
  473. kfree(tm_list[i]);
  474. }
  475. if (locked)
  476. write_unlock(&eb->fs_info->tree_mod_log_lock);
  477. kfree(tm_list);
  478. kfree(tm);
  479. return ret;
  480. }
  481. static inline int
  482. __tree_mod_log_free_eb(struct btrfs_fs_info *fs_info,
  483. struct tree_mod_elem **tm_list,
  484. int nritems)
  485. {
  486. int i, j;
  487. int ret;
  488. for (i = nritems - 1; i >= 0; i--) {
  489. ret = __tree_mod_log_insert(fs_info, tm_list[i]);
  490. if (ret) {
  491. for (j = nritems - 1; j > i; j--)
  492. rb_erase(&tm_list[j]->node,
  493. &fs_info->tree_mod_log);
  494. return ret;
  495. }
  496. }
  497. return 0;
  498. }
  499. static noinline int tree_mod_log_insert_root(struct extent_buffer *old_root,
  500. struct extent_buffer *new_root, int log_removal)
  501. {
  502. struct btrfs_fs_info *fs_info = old_root->fs_info;
  503. struct tree_mod_elem *tm = NULL;
  504. struct tree_mod_elem **tm_list = NULL;
  505. int nritems = 0;
  506. int ret = 0;
  507. int i;
  508. if (!tree_mod_need_log(fs_info, NULL))
  509. return 0;
  510. if (log_removal && btrfs_header_level(old_root) > 0) {
  511. nritems = btrfs_header_nritems(old_root);
  512. tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *),
  513. GFP_NOFS);
  514. if (!tm_list) {
  515. ret = -ENOMEM;
  516. goto free_tms;
  517. }
  518. for (i = 0; i < nritems; i++) {
  519. tm_list[i] = alloc_tree_mod_elem(old_root, i,
  520. MOD_LOG_KEY_REMOVE_WHILE_FREEING, GFP_NOFS);
  521. if (!tm_list[i]) {
  522. ret = -ENOMEM;
  523. goto free_tms;
  524. }
  525. }
  526. }
  527. tm = kzalloc(sizeof(*tm), GFP_NOFS);
  528. if (!tm) {
  529. ret = -ENOMEM;
  530. goto free_tms;
  531. }
  532. tm->logical = new_root->start;
  533. tm->old_root.logical = old_root->start;
  534. tm->old_root.level = btrfs_header_level(old_root);
  535. tm->generation = btrfs_header_generation(old_root);
  536. tm->op = MOD_LOG_ROOT_REPLACE;
  537. if (tree_mod_dont_log(fs_info, NULL))
  538. goto free_tms;
  539. if (tm_list)
  540. ret = __tree_mod_log_free_eb(fs_info, tm_list, nritems);
  541. if (!ret)
  542. ret = __tree_mod_log_insert(fs_info, tm);
  543. write_unlock(&fs_info->tree_mod_log_lock);
  544. if (ret)
  545. goto free_tms;
  546. kfree(tm_list);
  547. return ret;
  548. free_tms:
  549. if (tm_list) {
  550. for (i = 0; i < nritems; i++)
  551. kfree(tm_list[i]);
  552. kfree(tm_list);
  553. }
  554. kfree(tm);
  555. return ret;
  556. }
  557. static struct tree_mod_elem *
  558. __tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq,
  559. int smallest)
  560. {
  561. struct rb_root *tm_root;
  562. struct rb_node *node;
  563. struct tree_mod_elem *cur = NULL;
  564. struct tree_mod_elem *found = NULL;
  565. read_lock(&fs_info->tree_mod_log_lock);
  566. tm_root = &fs_info->tree_mod_log;
  567. node = tm_root->rb_node;
  568. while (node) {
  569. cur = rb_entry(node, struct tree_mod_elem, node);
  570. if (cur->logical < start) {
  571. node = node->rb_left;
  572. } else if (cur->logical > start) {
  573. node = node->rb_right;
  574. } else if (cur->seq < min_seq) {
  575. node = node->rb_left;
  576. } else if (!smallest) {
  577. /* we want the node with the highest seq */
  578. if (found)
  579. BUG_ON(found->seq > cur->seq);
  580. found = cur;
  581. node = node->rb_left;
  582. } else if (cur->seq > min_seq) {
  583. /* we want the node with the smallest seq */
  584. if (found)
  585. BUG_ON(found->seq < cur->seq);
  586. found = cur;
  587. node = node->rb_right;
  588. } else {
  589. found = cur;
  590. break;
  591. }
  592. }
  593. read_unlock(&fs_info->tree_mod_log_lock);
  594. return found;
  595. }
  596. /*
  597. * this returns the element from the log with the smallest time sequence
  598. * value that's in the log (the oldest log item). any element with a time
  599. * sequence lower than min_seq will be ignored.
  600. */
  601. static struct tree_mod_elem *
  602. tree_mod_log_search_oldest(struct btrfs_fs_info *fs_info, u64 start,
  603. u64 min_seq)
  604. {
  605. return __tree_mod_log_search(fs_info, start, min_seq, 1);
  606. }
  607. /*
  608. * this returns the element from the log with the largest time sequence
  609. * value that's in the log (the most recent log item). any element with
  610. * a time sequence lower than min_seq will be ignored.
  611. */
  612. static struct tree_mod_elem *
  613. tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq)
  614. {
  615. return __tree_mod_log_search(fs_info, start, min_seq, 0);
  616. }
  617. static noinline int tree_mod_log_eb_copy(struct extent_buffer *dst,
  618. struct extent_buffer *src, unsigned long dst_offset,
  619. unsigned long src_offset, int nr_items)
  620. {
  621. struct btrfs_fs_info *fs_info = dst->fs_info;
  622. int ret = 0;
  623. struct tree_mod_elem **tm_list = NULL;
  624. struct tree_mod_elem **tm_list_add, **tm_list_rem;
  625. int i;
  626. int locked = 0;
  627. if (!tree_mod_need_log(fs_info, NULL))
  628. return 0;
  629. if (btrfs_header_level(dst) == 0 && btrfs_header_level(src) == 0)
  630. return 0;
  631. tm_list = kcalloc(nr_items * 2, sizeof(struct tree_mod_elem *),
  632. GFP_NOFS);
  633. if (!tm_list)
  634. return -ENOMEM;
  635. tm_list_add = tm_list;
  636. tm_list_rem = tm_list + nr_items;
  637. for (i = 0; i < nr_items; i++) {
  638. tm_list_rem[i] = alloc_tree_mod_elem(src, i + src_offset,
  639. MOD_LOG_KEY_REMOVE, GFP_NOFS);
  640. if (!tm_list_rem[i]) {
  641. ret = -ENOMEM;
  642. goto free_tms;
  643. }
  644. tm_list_add[i] = alloc_tree_mod_elem(dst, i + dst_offset,
  645. MOD_LOG_KEY_ADD, GFP_NOFS);
  646. if (!tm_list_add[i]) {
  647. ret = -ENOMEM;
  648. goto free_tms;
  649. }
  650. }
  651. if (tree_mod_dont_log(fs_info, NULL))
  652. goto free_tms;
  653. locked = 1;
  654. for (i = 0; i < nr_items; i++) {
  655. ret = __tree_mod_log_insert(fs_info, tm_list_rem[i]);
  656. if (ret)
  657. goto free_tms;
  658. ret = __tree_mod_log_insert(fs_info, tm_list_add[i]);
  659. if (ret)
  660. goto free_tms;
  661. }
  662. write_unlock(&fs_info->tree_mod_log_lock);
  663. kfree(tm_list);
  664. return 0;
  665. free_tms:
  666. for (i = 0; i < nr_items * 2; i++) {
  667. if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
  668. rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log);
  669. kfree(tm_list[i]);
  670. }
  671. if (locked)
  672. write_unlock(&fs_info->tree_mod_log_lock);
  673. kfree(tm_list);
  674. return ret;
  675. }
  676. static noinline int tree_mod_log_free_eb(struct extent_buffer *eb)
  677. {
  678. struct tree_mod_elem **tm_list = NULL;
  679. int nritems = 0;
  680. int i;
  681. int ret = 0;
  682. if (btrfs_header_level(eb) == 0)
  683. return 0;
  684. if (!tree_mod_need_log(eb->fs_info, NULL))
  685. return 0;
  686. nritems = btrfs_header_nritems(eb);
  687. tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *), GFP_NOFS);
  688. if (!tm_list)
  689. return -ENOMEM;
  690. for (i = 0; i < nritems; i++) {
  691. tm_list[i] = alloc_tree_mod_elem(eb, i,
  692. MOD_LOG_KEY_REMOVE_WHILE_FREEING, GFP_NOFS);
  693. if (!tm_list[i]) {
  694. ret = -ENOMEM;
  695. goto free_tms;
  696. }
  697. }
  698. if (tree_mod_dont_log(eb->fs_info, eb))
  699. goto free_tms;
  700. ret = __tree_mod_log_free_eb(eb->fs_info, tm_list, nritems);
  701. write_unlock(&eb->fs_info->tree_mod_log_lock);
  702. if (ret)
  703. goto free_tms;
  704. kfree(tm_list);
  705. return 0;
  706. free_tms:
  707. for (i = 0; i < nritems; i++)
  708. kfree(tm_list[i]);
  709. kfree(tm_list);
  710. return ret;
  711. }
  712. /*
  713. * check if the tree block can be shared by multiple trees
  714. */
  715. int btrfs_block_can_be_shared(struct btrfs_root *root,
  716. struct extent_buffer *buf)
  717. {
  718. /*
  719. * Tree blocks not in shareable trees and tree roots are never shared.
  720. * If a block was allocated after the last snapshot and the block was
  721. * not allocated by tree relocation, we know the block is not shared.
  722. */
  723. if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
  724. buf != root->node && buf != root->commit_root &&
  725. (btrfs_header_generation(buf) <=
  726. btrfs_root_last_snapshot(&root->root_item) ||
  727. btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
  728. return 1;
  729. return 0;
  730. }
  731. static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
  732. struct btrfs_root *root,
  733. struct extent_buffer *buf,
  734. struct extent_buffer *cow,
  735. int *last_ref)
  736. {
  737. struct btrfs_fs_info *fs_info = root->fs_info;
  738. u64 refs;
  739. u64 owner;
  740. u64 flags;
  741. u64 new_flags = 0;
  742. int ret;
  743. /*
  744. * Backrefs update rules:
  745. *
  746. * Always use full backrefs for extent pointers in tree block
  747. * allocated by tree relocation.
  748. *
  749. * If a shared tree block is no longer referenced by its owner
  750. * tree (btrfs_header_owner(buf) == root->root_key.objectid),
  751. * use full backrefs for extent pointers in tree block.
  752. *
  753. * If a tree block is been relocating
  754. * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
  755. * use full backrefs for extent pointers in tree block.
  756. * The reason for this is some operations (such as drop tree)
  757. * are only allowed for blocks use full backrefs.
  758. */
  759. if (btrfs_block_can_be_shared(root, buf)) {
  760. ret = btrfs_lookup_extent_info(trans, fs_info, buf->start,
  761. btrfs_header_level(buf), 1,
  762. &refs, &flags);
  763. if (ret)
  764. return ret;
  765. if (refs == 0) {
  766. ret = -EROFS;
  767. btrfs_handle_fs_error(fs_info, ret, NULL);
  768. return ret;
  769. }
  770. } else {
  771. refs = 1;
  772. if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
  773. btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
  774. flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
  775. else
  776. flags = 0;
  777. }
  778. owner = btrfs_header_owner(buf);
  779. BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
  780. !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
  781. if (refs > 1) {
  782. if ((owner == root->root_key.objectid ||
  783. root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
  784. !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
  785. ret = btrfs_inc_ref(trans, root, buf, 1);
  786. if (ret)
  787. return ret;
  788. if (root->root_key.objectid ==
  789. BTRFS_TREE_RELOC_OBJECTID) {
  790. ret = btrfs_dec_ref(trans, root, buf, 0);
  791. if (ret)
  792. return ret;
  793. ret = btrfs_inc_ref(trans, root, cow, 1);
  794. if (ret)
  795. return ret;
  796. }
  797. new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
  798. } else {
  799. if (root->root_key.objectid ==
  800. BTRFS_TREE_RELOC_OBJECTID)
  801. ret = btrfs_inc_ref(trans, root, cow, 1);
  802. else
  803. ret = btrfs_inc_ref(trans, root, cow, 0);
  804. if (ret)
  805. return ret;
  806. }
  807. if (new_flags != 0) {
  808. int level = btrfs_header_level(buf);
  809. ret = btrfs_set_disk_extent_flags(trans, buf,
  810. new_flags, level, 0);
  811. if (ret)
  812. return ret;
  813. }
  814. } else {
  815. if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
  816. if (root->root_key.objectid ==
  817. BTRFS_TREE_RELOC_OBJECTID)
  818. ret = btrfs_inc_ref(trans, root, cow, 1);
  819. else
  820. ret = btrfs_inc_ref(trans, root, cow, 0);
  821. if (ret)
  822. return ret;
  823. ret = btrfs_dec_ref(trans, root, buf, 1);
  824. if (ret)
  825. return ret;
  826. }
  827. btrfs_clean_tree_block(buf);
  828. *last_ref = 1;
  829. }
  830. return 0;
  831. }
  832. static struct extent_buffer *alloc_tree_block_no_bg_flush(
  833. struct btrfs_trans_handle *trans,
  834. struct btrfs_root *root,
  835. u64 parent_start,
  836. const struct btrfs_disk_key *disk_key,
  837. int level,
  838. u64 hint,
  839. u64 empty_size,
  840. enum btrfs_lock_nesting nest)
  841. {
  842. struct btrfs_fs_info *fs_info = root->fs_info;
  843. struct extent_buffer *ret;
  844. /*
  845. * If we are COWing a node/leaf from the extent, chunk, device or free
  846. * space trees, make sure that we do not finish block group creation of
  847. * pending block groups. We do this to avoid a deadlock.
  848. * COWing can result in allocation of a new chunk, and flushing pending
  849. * block groups (btrfs_create_pending_block_groups()) can be triggered
  850. * when finishing allocation of a new chunk. Creation of a pending block
  851. * group modifies the extent, chunk, device and free space trees,
  852. * therefore we could deadlock with ourselves since we are holding a
  853. * lock on an extent buffer that btrfs_create_pending_block_groups() may
  854. * try to COW later.
  855. * For similar reasons, we also need to delay flushing pending block
  856. * groups when splitting a leaf or node, from one of those trees, since
  857. * we are holding a write lock on it and its parent or when inserting a
  858. * new root node for one of those trees.
  859. */
  860. if (root == fs_info->extent_root ||
  861. root == fs_info->chunk_root ||
  862. root == fs_info->dev_root ||
  863. root == fs_info->free_space_root)
  864. trans->can_flush_pending_bgs = false;
  865. ret = btrfs_alloc_tree_block(trans, root, parent_start,
  866. root->root_key.objectid, disk_key, level,
  867. hint, empty_size, nest);
  868. trans->can_flush_pending_bgs = true;
  869. return ret;
  870. }
  871. /*
  872. * does the dirty work in cow of a single block. The parent block (if
  873. * supplied) is updated to point to the new cow copy. The new buffer is marked
  874. * dirty and returned locked. If you modify the block it needs to be marked
  875. * dirty again.
  876. *
  877. * search_start -- an allocation hint for the new block
  878. *
  879. * empty_size -- a hint that you plan on doing more cow. This is the size in
  880. * bytes the allocator should try to find free next to the block it returns.
  881. * This is just a hint and may be ignored by the allocator.
  882. */
  883. static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
  884. struct btrfs_root *root,
  885. struct extent_buffer *buf,
  886. struct extent_buffer *parent, int parent_slot,
  887. struct extent_buffer **cow_ret,
  888. u64 search_start, u64 empty_size,
  889. enum btrfs_lock_nesting nest)
  890. {
  891. struct btrfs_fs_info *fs_info = root->fs_info;
  892. struct btrfs_disk_key disk_key;
  893. struct extent_buffer *cow;
  894. int level, ret;
  895. int last_ref = 0;
  896. int unlock_orig = 0;
  897. u64 parent_start = 0;
  898. if (*cow_ret == buf)
  899. unlock_orig = 1;
  900. btrfs_assert_tree_locked(buf);
  901. WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
  902. trans->transid != fs_info->running_transaction->transid);
  903. WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
  904. trans->transid != root->last_trans);
  905. level = btrfs_header_level(buf);
  906. if (level == 0)
  907. btrfs_item_key(buf, &disk_key, 0);
  908. else
  909. btrfs_node_key(buf, &disk_key, 0);
  910. if ((root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && parent)
  911. parent_start = parent->start;
  912. cow = alloc_tree_block_no_bg_flush(trans, root, parent_start, &disk_key,
  913. level, search_start, empty_size, nest);
  914. if (IS_ERR(cow))
  915. return PTR_ERR(cow);
  916. /* cow is set to blocking by btrfs_init_new_buffer */
  917. copy_extent_buffer_full(cow, buf);
  918. btrfs_set_header_bytenr(cow, cow->start);
  919. btrfs_set_header_generation(cow, trans->transid);
  920. btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
  921. btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
  922. BTRFS_HEADER_FLAG_RELOC);
  923. if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
  924. btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
  925. else
  926. btrfs_set_header_owner(cow, root->root_key.objectid);
  927. write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid);
  928. ret = update_ref_for_cow(trans, root, buf, cow, &last_ref);
  929. if (ret) {
  930. btrfs_tree_unlock(cow);
  931. free_extent_buffer(cow);
  932. btrfs_abort_transaction(trans, ret);
  933. return ret;
  934. }
  935. if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
  936. ret = btrfs_reloc_cow_block(trans, root, buf, cow);
  937. if (ret) {
  938. btrfs_tree_unlock(cow);
  939. free_extent_buffer(cow);
  940. btrfs_abort_transaction(trans, ret);
  941. return ret;
  942. }
  943. }
  944. if (buf == root->node) {
  945. WARN_ON(parent && parent != buf);
  946. if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
  947. btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
  948. parent_start = buf->start;
  949. atomic_inc(&cow->refs);
  950. ret = tree_mod_log_insert_root(root->node, cow, 1);
  951. BUG_ON(ret < 0);
  952. rcu_assign_pointer(root->node, cow);
  953. btrfs_free_tree_block(trans, root, buf, parent_start,
  954. last_ref);
  955. free_extent_buffer(buf);
  956. add_root_to_dirty_list(root);
  957. } else {
  958. WARN_ON(trans->transid != btrfs_header_generation(parent));
  959. tree_mod_log_insert_key(parent, parent_slot,
  960. MOD_LOG_KEY_REPLACE, GFP_NOFS);
  961. btrfs_set_node_blockptr(parent, parent_slot,
  962. cow->start);
  963. btrfs_set_node_ptr_generation(parent, parent_slot,
  964. trans->transid);
  965. btrfs_mark_buffer_dirty(parent);
  966. if (last_ref) {
  967. ret = tree_mod_log_free_eb(buf);
  968. if (ret) {
  969. btrfs_tree_unlock(cow);
  970. free_extent_buffer(cow);
  971. btrfs_abort_transaction(trans, ret);
  972. return ret;
  973. }
  974. }
  975. btrfs_free_tree_block(trans, root, buf, parent_start,
  976. last_ref);
  977. }
  978. if (unlock_orig)
  979. btrfs_tree_unlock(buf);
  980. free_extent_buffer_stale(buf);
  981. btrfs_mark_buffer_dirty(cow);
  982. *cow_ret = cow;
  983. return 0;
  984. }
  985. /*
  986. * returns the logical address of the oldest predecessor of the given root.
  987. * entries older than time_seq are ignored.
  988. */
  989. static struct tree_mod_elem *__tree_mod_log_oldest_root(
  990. struct extent_buffer *eb_root, u64 time_seq)
  991. {
  992. struct tree_mod_elem *tm;
  993. struct tree_mod_elem *found = NULL;
  994. u64 root_logical = eb_root->start;
  995. int looped = 0;
  996. if (!time_seq)
  997. return NULL;
  998. /*
  999. * the very last operation that's logged for a root is the
  1000. * replacement operation (if it is replaced at all). this has
  1001. * the logical address of the *new* root, making it the very
  1002. * first operation that's logged for this root.
  1003. */
  1004. while (1) {
  1005. tm = tree_mod_log_search_oldest(eb_root->fs_info, root_logical,
  1006. time_seq);
  1007. if (!looped && !tm)
  1008. return NULL;
  1009. /*
  1010. * if there are no tree operation for the oldest root, we simply
  1011. * return it. this should only happen if that (old) root is at
  1012. * level 0.
  1013. */
  1014. if (!tm)
  1015. break;
  1016. /*
  1017. * if there's an operation that's not a root replacement, we
  1018. * found the oldest version of our root. normally, we'll find a
  1019. * MOD_LOG_KEY_REMOVE_WHILE_FREEING operation here.
  1020. */
  1021. if (tm->op != MOD_LOG_ROOT_REPLACE)
  1022. break;
  1023. found = tm;
  1024. root_logical = tm->old_root.logical;
  1025. looped = 1;
  1026. }
  1027. /* if there's no old root to return, return what we found instead */
  1028. if (!found)
  1029. found = tm;
  1030. return found;
  1031. }
  1032. /*
  1033. * tm is a pointer to the first operation to rewind within eb. then, all
  1034. * previous operations will be rewound (until we reach something older than
  1035. * time_seq).
  1036. */
  1037. static void
  1038. __tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct extent_buffer *eb,
  1039. u64 time_seq, struct tree_mod_elem *first_tm)
  1040. {
  1041. u32 n;
  1042. struct rb_node *next;
  1043. struct tree_mod_elem *tm = first_tm;
  1044. unsigned long o_dst;
  1045. unsigned long o_src;
  1046. unsigned long p_size = sizeof(struct btrfs_key_ptr);
  1047. n = btrfs_header_nritems(eb);
  1048. read_lock(&fs_info->tree_mod_log_lock);
  1049. while (tm && tm->seq >= time_seq) {
  1050. /*
  1051. * all the operations are recorded with the operator used for
  1052. * the modification. as we're going backwards, we do the
  1053. * opposite of each operation here.
  1054. */
  1055. switch (tm->op) {
  1056. case MOD_LOG_KEY_REMOVE_WHILE_FREEING:
  1057. BUG_ON(tm->slot < n);
  1058. fallthrough;
  1059. case MOD_LOG_KEY_REMOVE_WHILE_MOVING:
  1060. case MOD_LOG_KEY_REMOVE:
  1061. btrfs_set_node_key(eb, &tm->key, tm->slot);
  1062. btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
  1063. btrfs_set_node_ptr_generation(eb, tm->slot,
  1064. tm->generation);
  1065. n++;
  1066. break;
  1067. case MOD_LOG_KEY_REPLACE:
  1068. BUG_ON(tm->slot >= n);
  1069. btrfs_set_node_key(eb, &tm->key, tm->slot);
  1070. btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
  1071. btrfs_set_node_ptr_generation(eb, tm->slot,
  1072. tm->generation);
  1073. break;
  1074. case MOD_LOG_KEY_ADD:
  1075. /* if a move operation is needed it's in the log */
  1076. n--;
  1077. break;
  1078. case MOD_LOG_MOVE_KEYS:
  1079. o_dst = btrfs_node_key_ptr_offset(tm->slot);
  1080. o_src = btrfs_node_key_ptr_offset(tm->move.dst_slot);
  1081. memmove_extent_buffer(eb, o_dst, o_src,
  1082. tm->move.nr_items * p_size);
  1083. break;
  1084. case MOD_LOG_ROOT_REPLACE:
  1085. /*
  1086. * this operation is special. for roots, this must be
  1087. * handled explicitly before rewinding.
  1088. * for non-roots, this operation may exist if the node
  1089. * was a root: root A -> child B; then A gets empty and
  1090. * B is promoted to the new root. in the mod log, we'll
  1091. * have a root-replace operation for B, a tree block
  1092. * that is no root. we simply ignore that operation.
  1093. */
  1094. break;
  1095. }
  1096. next = rb_next(&tm->node);
  1097. if (!next)
  1098. break;
  1099. tm = rb_entry(next, struct tree_mod_elem, node);
  1100. if (tm->logical != first_tm->logical)
  1101. break;
  1102. }
  1103. read_unlock(&fs_info->tree_mod_log_lock);
  1104. btrfs_set_header_nritems(eb, n);
  1105. }
  1106. /*
  1107. * Called with eb read locked. If the buffer cannot be rewound, the same buffer
  1108. * is returned. If rewind operations happen, a fresh buffer is returned. The
  1109. * returned buffer is always read-locked. If the returned buffer is not the
  1110. * input buffer, the lock on the input buffer is released and the input buffer
  1111. * is freed (its refcount is decremented).
  1112. */
  1113. static struct extent_buffer *
  1114. tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
  1115. struct extent_buffer *eb, u64 time_seq)
  1116. {
  1117. struct extent_buffer *eb_rewin;
  1118. struct tree_mod_elem *tm;
  1119. if (!time_seq)
  1120. return eb;
  1121. if (btrfs_header_level(eb) == 0)
  1122. return eb;
  1123. tm = tree_mod_log_search(fs_info, eb->start, time_seq);
  1124. if (!tm)
  1125. return eb;
  1126. btrfs_set_path_blocking(path);
  1127. btrfs_set_lock_blocking_read(eb);
  1128. if (tm->op == MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
  1129. BUG_ON(tm->slot != 0);
  1130. eb_rewin = alloc_dummy_extent_buffer(fs_info, eb->start);
  1131. if (!eb_rewin) {
  1132. btrfs_tree_read_unlock_blocking(eb);
  1133. free_extent_buffer(eb);
  1134. return NULL;
  1135. }
  1136. btrfs_set_header_bytenr(eb_rewin, eb->start);
  1137. btrfs_set_header_backref_rev(eb_rewin,
  1138. btrfs_header_backref_rev(eb));
  1139. btrfs_set_header_owner(eb_rewin, btrfs_header_owner(eb));
  1140. btrfs_set_header_level(eb_rewin, btrfs_header_level(eb));
  1141. } else {
  1142. eb_rewin = btrfs_clone_extent_buffer(eb);
  1143. if (!eb_rewin) {
  1144. btrfs_tree_read_unlock_blocking(eb);
  1145. free_extent_buffer(eb);
  1146. return NULL;
  1147. }
  1148. }
  1149. btrfs_tree_read_unlock_blocking(eb);
  1150. free_extent_buffer(eb);
  1151. btrfs_set_buffer_lockdep_class(btrfs_header_owner(eb_rewin),
  1152. eb_rewin, btrfs_header_level(eb_rewin));
  1153. btrfs_tree_read_lock(eb_rewin);
  1154. __tree_mod_log_rewind(fs_info, eb_rewin, time_seq, tm);
  1155. WARN_ON(btrfs_header_nritems(eb_rewin) >
  1156. BTRFS_NODEPTRS_PER_BLOCK(fs_info));
  1157. return eb_rewin;
  1158. }
  1159. /*
  1160. * get_old_root() rewinds the state of @root's root node to the given @time_seq
  1161. * value. If there are no changes, the current root->root_node is returned. If
  1162. * anything changed in between, there's a fresh buffer allocated on which the
  1163. * rewind operations are done. In any case, the returned buffer is read locked.
  1164. * Returns NULL on error (with no locks held).
  1165. */
  1166. static inline struct extent_buffer *
  1167. get_old_root(struct btrfs_root *root, u64 time_seq)
  1168. {
  1169. struct btrfs_fs_info *fs_info = root->fs_info;
  1170. struct tree_mod_elem *tm;
  1171. struct extent_buffer *eb = NULL;
  1172. struct extent_buffer *eb_root;
  1173. u64 eb_root_owner = 0;
  1174. struct extent_buffer *old;
  1175. struct tree_mod_root *old_root = NULL;
  1176. u64 old_generation = 0;
  1177. u64 logical;
  1178. int level;
  1179. eb_root = btrfs_read_lock_root_node(root);
  1180. tm = __tree_mod_log_oldest_root(eb_root, time_seq);
  1181. if (!tm)
  1182. return eb_root;
  1183. if (tm->op == MOD_LOG_ROOT_REPLACE) {
  1184. old_root = &tm->old_root;
  1185. old_generation = tm->generation;
  1186. logical = old_root->logical;
  1187. level = old_root->level;
  1188. } else {
  1189. logical = eb_root->start;
  1190. level = btrfs_header_level(eb_root);
  1191. }
  1192. tm = tree_mod_log_search(fs_info, logical, time_seq);
  1193. if (old_root && tm && tm->op != MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
  1194. btrfs_tree_read_unlock(eb_root);
  1195. free_extent_buffer(eb_root);
  1196. old = read_tree_block(fs_info, logical, 0, level, NULL);
  1197. if (WARN_ON(IS_ERR(old) || !extent_buffer_uptodate(old))) {
  1198. if (!IS_ERR(old))
  1199. free_extent_buffer(old);
  1200. btrfs_warn(fs_info,
  1201. "failed to read tree block %llu from get_old_root",
  1202. logical);
  1203. } else {
  1204. struct tree_mod_elem *tm2;
  1205. btrfs_tree_read_lock(old);
  1206. eb = btrfs_clone_extent_buffer(old);
  1207. /*
  1208. * After the lookup for the most recent tree mod operation
  1209. * above and before we locked and cloned the extent buffer
  1210. * 'old', a new tree mod log operation may have been added.
  1211. * So lookup for a more recent one to make sure the number
  1212. * of mod log operations we replay is consistent with the
  1213. * number of items we have in the cloned extent buffer,
  1214. * otherwise we can hit a BUG_ON when rewinding the extent
  1215. * buffer.
  1216. */
  1217. tm2 = tree_mod_log_search(fs_info, logical, time_seq);
  1218. btrfs_tree_read_unlock(old);
  1219. free_extent_buffer(old);
  1220. ASSERT(tm2);
  1221. ASSERT(tm2 == tm || tm2->seq > tm->seq);
  1222. if (!tm2 || tm2->seq < tm->seq) {
  1223. free_extent_buffer(eb);
  1224. return NULL;
  1225. }
  1226. tm = tm2;
  1227. }
  1228. } else if (old_root) {
  1229. eb_root_owner = btrfs_header_owner(eb_root);
  1230. btrfs_tree_read_unlock(eb_root);
  1231. free_extent_buffer(eb_root);
  1232. eb = alloc_dummy_extent_buffer(fs_info, logical);
  1233. } else {
  1234. btrfs_set_lock_blocking_read(eb_root);
  1235. eb = btrfs_clone_extent_buffer(eb_root);
  1236. btrfs_tree_read_unlock_blocking(eb_root);
  1237. free_extent_buffer(eb_root);
  1238. }
  1239. if (!eb)
  1240. return NULL;
  1241. if (old_root) {
  1242. btrfs_set_header_bytenr(eb, eb->start);
  1243. btrfs_set_header_backref_rev(eb, BTRFS_MIXED_BACKREF_REV);
  1244. btrfs_set_header_owner(eb, eb_root_owner);
  1245. btrfs_set_header_level(eb, old_root->level);
  1246. btrfs_set_header_generation(eb, old_generation);
  1247. }
  1248. btrfs_set_buffer_lockdep_class(btrfs_header_owner(eb), eb,
  1249. btrfs_header_level(eb));
  1250. btrfs_tree_read_lock(eb);
  1251. if (tm)
  1252. __tree_mod_log_rewind(fs_info, eb, time_seq, tm);
  1253. else
  1254. WARN_ON(btrfs_header_level(eb) != 0);
  1255. WARN_ON(btrfs_header_nritems(eb) > BTRFS_NODEPTRS_PER_BLOCK(fs_info));
  1256. return eb;
  1257. }
  1258. int btrfs_old_root_level(struct btrfs_root *root, u64 time_seq)
  1259. {
  1260. struct tree_mod_elem *tm;
  1261. int level;
  1262. struct extent_buffer *eb_root = btrfs_root_node(root);
  1263. tm = __tree_mod_log_oldest_root(eb_root, time_seq);
  1264. if (tm && tm->op == MOD_LOG_ROOT_REPLACE) {
  1265. level = tm->old_root.level;
  1266. } else {
  1267. level = btrfs_header_level(eb_root);
  1268. }
  1269. free_extent_buffer(eb_root);
  1270. return level;
  1271. }
  1272. static inline int should_cow_block(struct btrfs_trans_handle *trans,
  1273. struct btrfs_root *root,
  1274. struct extent_buffer *buf)
  1275. {
  1276. if (btrfs_is_testing(root->fs_info))
  1277. return 0;
  1278. /* Ensure we can see the FORCE_COW bit */
  1279. smp_mb__before_atomic();
  1280. /*
  1281. * We do not need to cow a block if
  1282. * 1) this block is not created or changed in this transaction;
  1283. * 2) this block does not belong to TREE_RELOC tree;
  1284. * 3) the root is not forced COW.
  1285. *
  1286. * What is forced COW:
  1287. * when we create snapshot during committing the transaction,
  1288. * after we've finished copying src root, we must COW the shared
  1289. * block to ensure the metadata consistency.
  1290. */
  1291. if (btrfs_header_generation(buf) == trans->transid &&
  1292. !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
  1293. !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
  1294. btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) &&
  1295. !test_bit(BTRFS_ROOT_FORCE_COW, &root->state))
  1296. return 0;
  1297. return 1;
  1298. }
  1299. /*
  1300. * cows a single block, see __btrfs_cow_block for the real work.
  1301. * This version of it has extra checks so that a block isn't COWed more than
  1302. * once per transaction, as long as it hasn't been written yet
  1303. */
  1304. noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
  1305. struct btrfs_root *root, struct extent_buffer *buf,
  1306. struct extent_buffer *parent, int parent_slot,
  1307. struct extent_buffer **cow_ret,
  1308. enum btrfs_lock_nesting nest)
  1309. {
  1310. struct btrfs_fs_info *fs_info = root->fs_info;
  1311. u64 search_start;
  1312. int ret;
  1313. if (test_bit(BTRFS_ROOT_DELETING, &root->state))
  1314. btrfs_err(fs_info,
  1315. "COW'ing blocks on a fs root that's being dropped");
  1316. if (trans->transaction != fs_info->running_transaction)
  1317. WARN(1, KERN_CRIT "trans %llu running %llu\n",
  1318. trans->transid,
  1319. fs_info->running_transaction->transid);
  1320. if (trans->transid != fs_info->generation)
  1321. WARN(1, KERN_CRIT "trans %llu running %llu\n",
  1322. trans->transid, fs_info->generation);
  1323. if (!should_cow_block(trans, root, buf)) {
  1324. trans->dirty = true;
  1325. *cow_ret = buf;
  1326. return 0;
  1327. }
  1328. search_start = buf->start & ~((u64)SZ_1G - 1);
  1329. if (parent)
  1330. btrfs_set_lock_blocking_write(parent);
  1331. btrfs_set_lock_blocking_write(buf);
  1332. /*
  1333. * Before CoWing this block for later modification, check if it's
  1334. * the subtree root and do the delayed subtree trace if needed.
  1335. *
  1336. * Also We don't care about the error, as it's handled internally.
  1337. */
  1338. btrfs_qgroup_trace_subtree_after_cow(trans, root, buf);
  1339. ret = __btrfs_cow_block(trans, root, buf, parent,
  1340. parent_slot, cow_ret, search_start, 0, nest);
  1341. trace_btrfs_cow_block(root, buf, *cow_ret);
  1342. return ret;
  1343. }
  1344. /*
  1345. * helper function for defrag to decide if two blocks pointed to by a
  1346. * node are actually close by
  1347. */
  1348. static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
  1349. {
  1350. if (blocknr < other && other - (blocknr + blocksize) < 32768)
  1351. return 1;
  1352. if (blocknr > other && blocknr - (other + blocksize) < 32768)
  1353. return 1;
  1354. return 0;
  1355. }
  1356. #ifdef __LITTLE_ENDIAN
  1357. /*
  1358. * Compare two keys, on little-endian the disk order is same as CPU order and
  1359. * we can avoid the conversion.
  1360. */
  1361. static int comp_keys(const struct btrfs_disk_key *disk_key,
  1362. const struct btrfs_key *k2)
  1363. {
  1364. const struct btrfs_key *k1 = (const struct btrfs_key *)disk_key;
  1365. return btrfs_comp_cpu_keys(k1, k2);
  1366. }
  1367. #else
  1368. /*
  1369. * compare two keys in a memcmp fashion
  1370. */
  1371. static int comp_keys(const struct btrfs_disk_key *disk,
  1372. const struct btrfs_key *k2)
  1373. {
  1374. struct btrfs_key k1;
  1375. btrfs_disk_key_to_cpu(&k1, disk);
  1376. return btrfs_comp_cpu_keys(&k1, k2);
  1377. }
  1378. #endif
  1379. /*
  1380. * same as comp_keys only with two btrfs_key's
  1381. */
  1382. int __pure btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2)
  1383. {
  1384. if (k1->objectid > k2->objectid)
  1385. return 1;
  1386. if (k1->objectid < k2->objectid)
  1387. return -1;
  1388. if (k1->type > k2->type)
  1389. return 1;
  1390. if (k1->type < k2->type)
  1391. return -1;
  1392. if (k1->offset > k2->offset)
  1393. return 1;
  1394. if (k1->offset < k2->offset)
  1395. return -1;
  1396. return 0;
  1397. }
  1398. /*
  1399. * this is used by the defrag code to go through all the
  1400. * leaves pointed to by a node and reallocate them so that
  1401. * disk order is close to key order
  1402. */
  1403. int btrfs_realloc_node(struct btrfs_trans_handle *trans,
  1404. struct btrfs_root *root, struct extent_buffer *parent,
  1405. int start_slot, u64 *last_ret,
  1406. struct btrfs_key *progress)
  1407. {
  1408. struct btrfs_fs_info *fs_info = root->fs_info;
  1409. struct extent_buffer *cur;
  1410. u64 blocknr;
  1411. u64 gen;
  1412. u64 search_start = *last_ret;
  1413. u64 last_block = 0;
  1414. u64 other;
  1415. u32 parent_nritems;
  1416. int end_slot;
  1417. int i;
  1418. int err = 0;
  1419. int parent_level;
  1420. int uptodate;
  1421. u32 blocksize;
  1422. int progress_passed = 0;
  1423. struct btrfs_disk_key disk_key;
  1424. parent_level = btrfs_header_level(parent);
  1425. WARN_ON(trans->transaction != fs_info->running_transaction);
  1426. WARN_ON(trans->transid != fs_info->generation);
  1427. parent_nritems = btrfs_header_nritems(parent);
  1428. blocksize = fs_info->nodesize;
  1429. end_slot = parent_nritems - 1;
  1430. if (parent_nritems <= 1)
  1431. return 0;
  1432. btrfs_set_lock_blocking_write(parent);
  1433. for (i = start_slot; i <= end_slot; i++) {
  1434. struct btrfs_key first_key;
  1435. int close = 1;
  1436. btrfs_node_key(parent, &disk_key, i);
  1437. if (!progress_passed && comp_keys(&disk_key, progress) < 0)
  1438. continue;
  1439. progress_passed = 1;
  1440. blocknr = btrfs_node_blockptr(parent, i);
  1441. gen = btrfs_node_ptr_generation(parent, i);
  1442. btrfs_node_key_to_cpu(parent, &first_key, i);
  1443. if (last_block == 0)
  1444. last_block = blocknr;
  1445. if (i > 0) {
  1446. other = btrfs_node_blockptr(parent, i - 1);
  1447. close = close_blocks(blocknr, other, blocksize);
  1448. }
  1449. if (!close && i < end_slot) {
  1450. other = btrfs_node_blockptr(parent, i + 1);
  1451. close = close_blocks(blocknr, other, blocksize);
  1452. }
  1453. if (close) {
  1454. last_block = blocknr;
  1455. continue;
  1456. }
  1457. cur = find_extent_buffer(fs_info, blocknr);
  1458. if (cur)
  1459. uptodate = btrfs_buffer_uptodate(cur, gen, 0);
  1460. else
  1461. uptodate = 0;
  1462. if (!cur || !uptodate) {
  1463. if (!cur) {
  1464. cur = read_tree_block(fs_info, blocknr, gen,
  1465. parent_level - 1,
  1466. &first_key);
  1467. if (IS_ERR(cur)) {
  1468. return PTR_ERR(cur);
  1469. } else if (!extent_buffer_uptodate(cur)) {
  1470. free_extent_buffer(cur);
  1471. return -EIO;
  1472. }
  1473. } else if (!uptodate) {
  1474. err = btrfs_read_buffer(cur, gen,
  1475. parent_level - 1,&first_key);
  1476. if (err) {
  1477. free_extent_buffer(cur);
  1478. return err;
  1479. }
  1480. }
  1481. }
  1482. if (search_start == 0)
  1483. search_start = last_block;
  1484. btrfs_tree_lock(cur);
  1485. btrfs_set_lock_blocking_write(cur);
  1486. err = __btrfs_cow_block(trans, root, cur, parent, i,
  1487. &cur, search_start,
  1488. min(16 * blocksize,
  1489. (end_slot - i) * blocksize),
  1490. BTRFS_NESTING_COW);
  1491. if (err) {
  1492. btrfs_tree_unlock(cur);
  1493. free_extent_buffer(cur);
  1494. break;
  1495. }
  1496. search_start = cur->start;
  1497. last_block = cur->start;
  1498. *last_ret = search_start;
  1499. btrfs_tree_unlock(cur);
  1500. free_extent_buffer(cur);
  1501. }
  1502. return err;
  1503. }
  1504. /*
  1505. * search for key in the extent_buffer. The items start at offset p,
  1506. * and they are item_size apart. There are 'max' items in p.
  1507. *
  1508. * the slot in the array is returned via slot, and it points to
  1509. * the place where you would insert key if it is not found in
  1510. * the array.
  1511. *
  1512. * slot may point to max if the key is bigger than all of the keys
  1513. */
  1514. static noinline int generic_bin_search(struct extent_buffer *eb,
  1515. unsigned long p, int item_size,
  1516. const struct btrfs_key *key,
  1517. int max, int *slot)
  1518. {
  1519. int low = 0;
  1520. int high = max;
  1521. int ret;
  1522. const int key_size = sizeof(struct btrfs_disk_key);
  1523. if (low > high) {
  1524. btrfs_err(eb->fs_info,
  1525. "%s: low (%d) > high (%d) eb %llu owner %llu level %d",
  1526. __func__, low, high, eb->start,
  1527. btrfs_header_owner(eb), btrfs_header_level(eb));
  1528. return -EINVAL;
  1529. }
  1530. while (low < high) {
  1531. unsigned long oip;
  1532. unsigned long offset;
  1533. struct btrfs_disk_key *tmp;
  1534. struct btrfs_disk_key unaligned;
  1535. int mid;
  1536. mid = (low + high) / 2;
  1537. offset = p + mid * item_size;
  1538. oip = offset_in_page(offset);
  1539. if (oip + key_size <= PAGE_SIZE) {
  1540. const unsigned long idx = offset >> PAGE_SHIFT;
  1541. char *kaddr = page_address(eb->pages[idx]);
  1542. tmp = (struct btrfs_disk_key *)(kaddr + oip);
  1543. } else {
  1544. read_extent_buffer(eb, &unaligned, offset, key_size);
  1545. tmp = &unaligned;
  1546. }
  1547. ret = comp_keys(tmp, key);
  1548. if (ret < 0)
  1549. low = mid + 1;
  1550. else if (ret > 0)
  1551. high = mid;
  1552. else {
  1553. *slot = mid;
  1554. return 0;
  1555. }
  1556. }
  1557. *slot = low;
  1558. return 1;
  1559. }
  1560. /*
  1561. * simple bin_search frontend that does the right thing for
  1562. * leaves vs nodes
  1563. */
  1564. int btrfs_bin_search(struct extent_buffer *eb, const struct btrfs_key *key,
  1565. int *slot)
  1566. {
  1567. if (btrfs_header_level(eb) == 0)
  1568. return generic_bin_search(eb,
  1569. offsetof(struct btrfs_leaf, items),
  1570. sizeof(struct btrfs_item),
  1571. key, btrfs_header_nritems(eb),
  1572. slot);
  1573. else
  1574. return generic_bin_search(eb,
  1575. offsetof(struct btrfs_node, ptrs),
  1576. sizeof(struct btrfs_key_ptr),
  1577. key, btrfs_header_nritems(eb),
  1578. slot);
  1579. }
  1580. static void root_add_used(struct btrfs_root *root, u32 size)
  1581. {
  1582. spin_lock(&root->accounting_lock);
  1583. btrfs_set_root_used(&root->root_item,
  1584. btrfs_root_used(&root->root_item) + size);
  1585. spin_unlock(&root->accounting_lock);
  1586. }
  1587. static void root_sub_used(struct btrfs_root *root, u32 size)
  1588. {
  1589. spin_lock(&root->accounting_lock);
  1590. btrfs_set_root_used(&root->root_item,
  1591. btrfs_root_used(&root->root_item) - size);
  1592. spin_unlock(&root->accounting_lock);
  1593. }
  1594. /* given a node and slot number, this reads the blocks it points to. The
  1595. * extent buffer is returned with a reference taken (but unlocked).
  1596. */
  1597. struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent,
  1598. int slot)
  1599. {
  1600. int level = btrfs_header_level(parent);
  1601. struct extent_buffer *eb;
  1602. struct btrfs_key first_key;
  1603. if (slot < 0 || slot >= btrfs_header_nritems(parent))
  1604. return ERR_PTR(-ENOENT);
  1605. BUG_ON(level == 0);
  1606. btrfs_node_key_to_cpu(parent, &first_key, slot);
  1607. eb = read_tree_block(parent->fs_info, btrfs_node_blockptr(parent, slot),
  1608. btrfs_node_ptr_generation(parent, slot),
  1609. level - 1, &first_key);
  1610. if (!IS_ERR(eb) && !extent_buffer_uptodate(eb)) {
  1611. free_extent_buffer(eb);
  1612. eb = ERR_PTR(-EIO);
  1613. }
  1614. return eb;
  1615. }
  1616. /*
  1617. * node level balancing, used to make sure nodes are in proper order for
  1618. * item deletion. We balance from the top down, so we have to make sure
  1619. * that a deletion won't leave an node completely empty later on.
  1620. */
  1621. static noinline int balance_level(struct btrfs_trans_handle *trans,
  1622. struct btrfs_root *root,
  1623. struct btrfs_path *path, int level)
  1624. {
  1625. struct btrfs_fs_info *fs_info = root->fs_info;
  1626. struct extent_buffer *right = NULL;
  1627. struct extent_buffer *mid;
  1628. struct extent_buffer *left = NULL;
  1629. struct extent_buffer *parent = NULL;
  1630. int ret = 0;
  1631. int wret;
  1632. int pslot;
  1633. int orig_slot = path->slots[level];
  1634. u64 orig_ptr;
  1635. ASSERT(level > 0);
  1636. mid = path->nodes[level];
  1637. WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK &&
  1638. path->locks[level] != BTRFS_WRITE_LOCK_BLOCKING);
  1639. WARN_ON(btrfs_header_generation(mid) != trans->transid);
  1640. orig_ptr = btrfs_node_blockptr(mid, orig_slot);
  1641. if (level < BTRFS_MAX_LEVEL - 1) {
  1642. parent = path->nodes[level + 1];
  1643. pslot = path->slots[level + 1];
  1644. }
  1645. /*
  1646. * deal with the case where there is only one pointer in the root
  1647. * by promoting the node below to a root
  1648. */
  1649. if (!parent) {
  1650. struct extent_buffer *child;
  1651. if (btrfs_header_nritems(mid) != 1)
  1652. return 0;
  1653. /* promote the child to a root */
  1654. child = btrfs_read_node_slot(mid, 0);
  1655. if (IS_ERR(child)) {
  1656. ret = PTR_ERR(child);
  1657. btrfs_handle_fs_error(fs_info, ret, NULL);
  1658. goto enospc;
  1659. }
  1660. btrfs_tree_lock(child);
  1661. btrfs_set_lock_blocking_write(child);
  1662. ret = btrfs_cow_block(trans, root, child, mid, 0, &child,
  1663. BTRFS_NESTING_COW);
  1664. if (ret) {
  1665. btrfs_tree_unlock(child);
  1666. free_extent_buffer(child);
  1667. goto enospc;
  1668. }
  1669. ret = tree_mod_log_insert_root(root->node, child, 1);
  1670. BUG_ON(ret < 0);
  1671. rcu_assign_pointer(root->node, child);
  1672. add_root_to_dirty_list(root);
  1673. btrfs_tree_unlock(child);
  1674. path->locks[level] = 0;
  1675. path->nodes[level] = NULL;
  1676. btrfs_clean_tree_block(mid);
  1677. btrfs_tree_unlock(mid);
  1678. /* once for the path */
  1679. free_extent_buffer(mid);
  1680. root_sub_used(root, mid->len);
  1681. btrfs_free_tree_block(trans, root, mid, 0, 1);
  1682. /* once for the root ptr */
  1683. free_extent_buffer_stale(mid);
  1684. return 0;
  1685. }
  1686. if (btrfs_header_nritems(mid) >
  1687. BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4)
  1688. return 0;
  1689. left = btrfs_read_node_slot(parent, pslot - 1);
  1690. if (IS_ERR(left))
  1691. left = NULL;
  1692. if (left) {
  1693. __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
  1694. btrfs_set_lock_blocking_write(left);
  1695. wret = btrfs_cow_block(trans, root, left,
  1696. parent, pslot - 1, &left,
  1697. BTRFS_NESTING_LEFT_COW);
  1698. if (wret) {
  1699. ret = wret;
  1700. goto enospc;
  1701. }
  1702. }
  1703. right = btrfs_read_node_slot(parent, pslot + 1);
  1704. if (IS_ERR(right))
  1705. right = NULL;
  1706. if (right) {
  1707. __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
  1708. btrfs_set_lock_blocking_write(right);
  1709. wret = btrfs_cow_block(trans, root, right,
  1710. parent, pslot + 1, &right,
  1711. BTRFS_NESTING_RIGHT_COW);
  1712. if (wret) {
  1713. ret = wret;
  1714. goto enospc;
  1715. }
  1716. }
  1717. /* first, try to make some room in the middle buffer */
  1718. if (left) {
  1719. orig_slot += btrfs_header_nritems(left);
  1720. wret = push_node_left(trans, left, mid, 1);
  1721. if (wret < 0)
  1722. ret = wret;
  1723. }
  1724. /*
  1725. * then try to empty the right most buffer into the middle
  1726. */
  1727. if (right) {
  1728. wret = push_node_left(trans, mid, right, 1);
  1729. if (wret < 0 && wret != -ENOSPC)
  1730. ret = wret;
  1731. if (btrfs_header_nritems(right) == 0) {
  1732. btrfs_clean_tree_block(right);
  1733. btrfs_tree_unlock(right);
  1734. del_ptr(root, path, level + 1, pslot + 1);
  1735. root_sub_used(root, right->len);
  1736. btrfs_free_tree_block(trans, root, right, 0, 1);
  1737. free_extent_buffer_stale(right);
  1738. right = NULL;
  1739. } else {
  1740. struct btrfs_disk_key right_key;
  1741. btrfs_node_key(right, &right_key, 0);
  1742. ret = tree_mod_log_insert_key(parent, pslot + 1,
  1743. MOD_LOG_KEY_REPLACE, GFP_NOFS);
  1744. BUG_ON(ret < 0);
  1745. btrfs_set_node_key(parent, &right_key, pslot + 1);
  1746. btrfs_mark_buffer_dirty(parent);
  1747. }
  1748. }
  1749. if (btrfs_header_nritems(mid) == 1) {
  1750. /*
  1751. * we're not allowed to leave a node with one item in the
  1752. * tree during a delete. A deletion from lower in the tree
  1753. * could try to delete the only pointer in this node.
  1754. * So, pull some keys from the left.
  1755. * There has to be a left pointer at this point because
  1756. * otherwise we would have pulled some pointers from the
  1757. * right
  1758. */
  1759. if (!left) {
  1760. ret = -EROFS;
  1761. btrfs_handle_fs_error(fs_info, ret, NULL);
  1762. goto enospc;
  1763. }
  1764. wret = balance_node_right(trans, mid, left);
  1765. if (wret < 0) {
  1766. ret = wret;
  1767. goto enospc;
  1768. }
  1769. if (wret == 1) {
  1770. wret = push_node_left(trans, left, mid, 1);
  1771. if (wret < 0)
  1772. ret = wret;
  1773. }
  1774. BUG_ON(wret == 1);
  1775. }
  1776. if (btrfs_header_nritems(mid) == 0) {
  1777. btrfs_clean_tree_block(mid);
  1778. btrfs_tree_unlock(mid);
  1779. del_ptr(root, path, level + 1, pslot);
  1780. root_sub_used(root, mid->len);
  1781. btrfs_free_tree_block(trans, root, mid, 0, 1);
  1782. free_extent_buffer_stale(mid);
  1783. mid = NULL;
  1784. } else {
  1785. /* update the parent key to reflect our changes */
  1786. struct btrfs_disk_key mid_key;
  1787. btrfs_node_key(mid, &mid_key, 0);
  1788. ret = tree_mod_log_insert_key(parent, pslot,
  1789. MOD_LOG_KEY_REPLACE, GFP_NOFS);
  1790. BUG_ON(ret < 0);
  1791. btrfs_set_node_key(parent, &mid_key, pslot);
  1792. btrfs_mark_buffer_dirty(parent);
  1793. }
  1794. /* update the path */
  1795. if (left) {
  1796. if (btrfs_header_nritems(left) > orig_slot) {
  1797. atomic_inc(&left->refs);
  1798. /* left was locked after cow */
  1799. path->nodes[level] = left;
  1800. path->slots[level + 1] -= 1;
  1801. path->slots[level] = orig_slot;
  1802. if (mid) {
  1803. btrfs_tree_unlock(mid);
  1804. free_extent_buffer(mid);
  1805. }
  1806. } else {
  1807. orig_slot -= btrfs_header_nritems(left);
  1808. path->slots[level] = orig_slot;
  1809. }
  1810. }
  1811. /* double check we haven't messed things up */
  1812. if (orig_ptr !=
  1813. btrfs_node_blockptr(path->nodes[level], path->slots[level]))
  1814. BUG();
  1815. enospc:
  1816. if (right) {
  1817. btrfs_tree_unlock(right);
  1818. free_extent_buffer(right);
  1819. }
  1820. if (left) {
  1821. if (path->nodes[level] != left)
  1822. btrfs_tree_unlock(left);
  1823. free_extent_buffer(left);
  1824. }
  1825. return ret;
  1826. }
  1827. /* Node balancing for insertion. Here we only split or push nodes around
  1828. * when they are completely full. This is also done top down, so we
  1829. * have to be pessimistic.
  1830. */
  1831. static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
  1832. struct btrfs_root *root,
  1833. struct btrfs_path *path, int level)
  1834. {
  1835. struct btrfs_fs_info *fs_info = root->fs_info;
  1836. struct extent_buffer *right = NULL;
  1837. struct extent_buffer *mid;
  1838. struct extent_buffer *left = NULL;
  1839. struct extent_buffer *parent = NULL;
  1840. int ret = 0;
  1841. int wret;
  1842. int pslot;
  1843. int orig_slot = path->slots[level];
  1844. if (level == 0)
  1845. return 1;
  1846. mid = path->nodes[level];
  1847. WARN_ON(btrfs_header_generation(mid) != trans->transid);
  1848. if (level < BTRFS_MAX_LEVEL - 1) {
  1849. parent = path->nodes[level + 1];
  1850. pslot = path->slots[level + 1];
  1851. }
  1852. if (!parent)
  1853. return 1;
  1854. left = btrfs_read_node_slot(parent, pslot - 1);
  1855. if (IS_ERR(left))
  1856. left = NULL;
  1857. /* first, try to make some room in the middle buffer */
  1858. if (left) {
  1859. u32 left_nr;
  1860. __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
  1861. btrfs_set_lock_blocking_write(left);
  1862. left_nr = btrfs_header_nritems(left);
  1863. if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
  1864. wret = 1;
  1865. } else {
  1866. ret = btrfs_cow_block(trans, root, left, parent,
  1867. pslot - 1, &left,
  1868. BTRFS_NESTING_LEFT_COW);
  1869. if (ret)
  1870. wret = 1;
  1871. else {
  1872. wret = push_node_left(trans, left, mid, 0);
  1873. }
  1874. }
  1875. if (wret < 0)
  1876. ret = wret;
  1877. if (wret == 0) {
  1878. struct btrfs_disk_key disk_key;
  1879. orig_slot += left_nr;
  1880. btrfs_node_key(mid, &disk_key, 0);
  1881. ret = tree_mod_log_insert_key(parent, pslot,
  1882. MOD_LOG_KEY_REPLACE, GFP_NOFS);
  1883. BUG_ON(ret < 0);
  1884. btrfs_set_node_key(parent, &disk_key, pslot);
  1885. btrfs_mark_buffer_dirty(parent);
  1886. if (btrfs_header_nritems(left) > orig_slot) {
  1887. path->nodes[level] = left;
  1888. path->slots[level + 1] -= 1;
  1889. path->slots[level] = orig_slot;
  1890. btrfs_tree_unlock(mid);
  1891. free_extent_buffer(mid);
  1892. } else {
  1893. orig_slot -=
  1894. btrfs_header_nritems(left);
  1895. path->slots[level] = orig_slot;
  1896. btrfs_tree_unlock(left);
  1897. free_extent_buffer(left);
  1898. }
  1899. return 0;
  1900. }
  1901. btrfs_tree_unlock(left);
  1902. free_extent_buffer(left);
  1903. }
  1904. right = btrfs_read_node_slot(parent, pslot + 1);
  1905. if (IS_ERR(right))
  1906. right = NULL;
  1907. /*
  1908. * then try to empty the right most buffer into the middle
  1909. */
  1910. if (right) {
  1911. u32 right_nr;
  1912. __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
  1913. btrfs_set_lock_blocking_write(right);
  1914. right_nr = btrfs_header_nritems(right);
  1915. if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
  1916. wret = 1;
  1917. } else {
  1918. ret = btrfs_cow_block(trans, root, right,
  1919. parent, pslot + 1,
  1920. &right, BTRFS_NESTING_RIGHT_COW);
  1921. if (ret)
  1922. wret = 1;
  1923. else {
  1924. wret = balance_node_right(trans, right, mid);
  1925. }
  1926. }
  1927. if (wret < 0)
  1928. ret = wret;
  1929. if (wret == 0) {
  1930. struct btrfs_disk_key disk_key;
  1931. btrfs_node_key(right, &disk_key, 0);
  1932. ret = tree_mod_log_insert_key(parent, pslot + 1,
  1933. MOD_LOG_KEY_REPLACE, GFP_NOFS);
  1934. BUG_ON(ret < 0);
  1935. btrfs_set_node_key(parent, &disk_key, pslot + 1);
  1936. btrfs_mark_buffer_dirty(parent);
  1937. if (btrfs_header_nritems(mid) <= orig_slot) {
  1938. path->nodes[level] = right;
  1939. path->slots[level + 1] += 1;
  1940. path->slots[level] = orig_slot -
  1941. btrfs_header_nritems(mid);
  1942. btrfs_tree_unlock(mid);
  1943. free_extent_buffer(mid);
  1944. } else {
  1945. btrfs_tree_unlock(right);
  1946. free_extent_buffer(right);
  1947. }
  1948. return 0;
  1949. }
  1950. btrfs_tree_unlock(right);
  1951. free_extent_buffer(right);
  1952. }
  1953. return 1;
  1954. }
  1955. /*
  1956. * readahead one full node of leaves, finding things that are close
  1957. * to the block in 'slot', and triggering ra on them.
  1958. */
  1959. static void reada_for_search(struct btrfs_fs_info *fs_info,
  1960. struct btrfs_path *path,
  1961. int level, int slot, u64 objectid)
  1962. {
  1963. struct extent_buffer *node;
  1964. struct btrfs_disk_key disk_key;
  1965. u32 nritems;
  1966. u64 search;
  1967. u64 target;
  1968. u64 nread = 0;
  1969. struct extent_buffer *eb;
  1970. u32 nr;
  1971. u32 blocksize;
  1972. u32 nscan = 0;
  1973. if (level != 1)
  1974. return;
  1975. if (!path->nodes[level])
  1976. return;
  1977. node = path->nodes[level];
  1978. search = btrfs_node_blockptr(node, slot);
  1979. blocksize = fs_info->nodesize;
  1980. eb = find_extent_buffer(fs_info, search);
  1981. if (eb) {
  1982. free_extent_buffer(eb);
  1983. return;
  1984. }
  1985. target = search;
  1986. nritems = btrfs_header_nritems(node);
  1987. nr = slot;
  1988. while (1) {
  1989. if (path->reada == READA_BACK) {
  1990. if (nr == 0)
  1991. break;
  1992. nr--;
  1993. } else if (path->reada == READA_FORWARD) {
  1994. nr++;
  1995. if (nr >= nritems)
  1996. break;
  1997. }
  1998. if (path->reada == READA_BACK && objectid) {
  1999. btrfs_node_key(node, &disk_key, nr);
  2000. if (btrfs_disk_key_objectid(&disk_key) != objectid)
  2001. break;
  2002. }
  2003. search = btrfs_node_blockptr(node, nr);
  2004. if ((search <= target && target - search <= 65536) ||
  2005. (search > target && search - target <= 65536)) {
  2006. readahead_tree_block(fs_info, search);
  2007. nread += blocksize;
  2008. }
  2009. nscan++;
  2010. if ((nread > 65536 || nscan > 32))
  2011. break;
  2012. }
  2013. }
  2014. static noinline void reada_for_balance(struct btrfs_fs_info *fs_info,
  2015. struct btrfs_path *path, int level)
  2016. {
  2017. int slot;
  2018. int nritems;
  2019. struct extent_buffer *parent;
  2020. struct extent_buffer *eb;
  2021. u64 gen;
  2022. u64 block1 = 0;
  2023. u64 block2 = 0;
  2024. parent = path->nodes[level + 1];
  2025. if (!parent)
  2026. return;
  2027. nritems = btrfs_header_nritems(parent);
  2028. slot = path->slots[level + 1];
  2029. if (slot > 0) {
  2030. block1 = btrfs_node_blockptr(parent, slot - 1);
  2031. gen = btrfs_node_ptr_generation(parent, slot - 1);
  2032. eb = find_extent_buffer(fs_info, block1);
  2033. /*
  2034. * if we get -eagain from btrfs_buffer_uptodate, we
  2035. * don't want to return eagain here. That will loop
  2036. * forever
  2037. */
  2038. if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0)
  2039. block1 = 0;
  2040. free_extent_buffer(eb);
  2041. }
  2042. if (slot + 1 < nritems) {
  2043. block2 = btrfs_node_blockptr(parent, slot + 1);
  2044. gen = btrfs_node_ptr_generation(parent, slot + 1);
  2045. eb = find_extent_buffer(fs_info, block2);
  2046. if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0)
  2047. block2 = 0;
  2048. free_extent_buffer(eb);
  2049. }
  2050. if (block1)
  2051. readahead_tree_block(fs_info, block1);
  2052. if (block2)
  2053. readahead_tree_block(fs_info, block2);
  2054. }
  2055. /*
  2056. * when we walk down the tree, it is usually safe to unlock the higher layers
  2057. * in the tree. The exceptions are when our path goes through slot 0, because
  2058. * operations on the tree might require changing key pointers higher up in the
  2059. * tree.
  2060. *
  2061. * callers might also have set path->keep_locks, which tells this code to keep
  2062. * the lock if the path points to the last slot in the block. This is part of
  2063. * walking through the tree, and selecting the next slot in the higher block.
  2064. *
  2065. * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so
  2066. * if lowest_unlock is 1, level 0 won't be unlocked
  2067. */
  2068. static noinline void unlock_up(struct btrfs_path *path, int level,
  2069. int lowest_unlock, int min_write_lock_level,
  2070. int *write_lock_level)
  2071. {
  2072. int i;
  2073. int skip_level = level;
  2074. int no_skips = 0;
  2075. struct extent_buffer *t;
  2076. for (i = level; i < BTRFS_MAX_LEVEL; i++) {
  2077. if (!path->nodes[i])
  2078. break;
  2079. if (!path->locks[i])
  2080. break;
  2081. if (!no_skips && path->slots[i] == 0) {
  2082. skip_level = i + 1;
  2083. continue;
  2084. }
  2085. if (!no_skips && path->keep_locks) {
  2086. u32 nritems;
  2087. t = path->nodes[i];
  2088. nritems = btrfs_header_nritems(t);
  2089. if (nritems < 1 || path->slots[i] >= nritems - 1) {
  2090. skip_level = i + 1;
  2091. continue;
  2092. }
  2093. }
  2094. if (skip_level < i && i >= lowest_unlock)
  2095. no_skips = 1;
  2096. t = path->nodes[i];
  2097. if (i >= lowest_unlock && i > skip_level) {
  2098. btrfs_tree_unlock_rw(t, path->locks[i]);
  2099. path->locks[i] = 0;
  2100. if (write_lock_level &&
  2101. i > min_write_lock_level &&
  2102. i <= *write_lock_level) {
  2103. *write_lock_level = i - 1;
  2104. }
  2105. }
  2106. }
  2107. }
  2108. /*
  2109. * helper function for btrfs_search_slot. The goal is to find a block
  2110. * in cache without setting the path to blocking. If we find the block
  2111. * we return zero and the path is unchanged.
  2112. *
  2113. * If we can't find the block, we set the path blocking and do some
  2114. * reada. -EAGAIN is returned and the search must be repeated.
  2115. */
  2116. static int
  2117. read_block_for_search(struct btrfs_root *root, struct btrfs_path *p,
  2118. struct extent_buffer **eb_ret, int level, int slot,
  2119. const struct btrfs_key *key)
  2120. {
  2121. struct btrfs_fs_info *fs_info = root->fs_info;
  2122. u64 blocknr;
  2123. u64 gen;
  2124. struct extent_buffer *tmp;
  2125. struct btrfs_key first_key;
  2126. int ret;
  2127. int parent_level;
  2128. blocknr = btrfs_node_blockptr(*eb_ret, slot);
  2129. gen = btrfs_node_ptr_generation(*eb_ret, slot);
  2130. parent_level = btrfs_header_level(*eb_ret);
  2131. btrfs_node_key_to_cpu(*eb_ret, &first_key, slot);
  2132. tmp = find_extent_buffer(fs_info, blocknr);
  2133. if (tmp) {
  2134. /* first we do an atomic uptodate check */
  2135. if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) {
  2136. /*
  2137. * Do extra check for first_key, eb can be stale due to
  2138. * being cached, read from scrub, or have multiple
  2139. * parents (shared tree blocks).
  2140. */
  2141. if (btrfs_verify_level_key(tmp,
  2142. parent_level - 1, &first_key, gen)) {
  2143. free_extent_buffer(tmp);
  2144. return -EUCLEAN;
  2145. }
  2146. *eb_ret = tmp;
  2147. return 0;
  2148. }
  2149. /* the pages were up to date, but we failed
  2150. * the generation number check. Do a full
  2151. * read for the generation number that is correct.
  2152. * We must do this without dropping locks so
  2153. * we can trust our generation number
  2154. */
  2155. btrfs_set_path_blocking(p);
  2156. /* now we're allowed to do a blocking uptodate check */
  2157. ret = btrfs_read_buffer(tmp, gen, parent_level - 1, &first_key);
  2158. if (!ret) {
  2159. *eb_ret = tmp;
  2160. return 0;
  2161. }
  2162. free_extent_buffer(tmp);
  2163. btrfs_release_path(p);
  2164. return -EIO;
  2165. }
  2166. /*
  2167. * reduce lock contention at high levels
  2168. * of the btree by dropping locks before
  2169. * we read. Don't release the lock on the current
  2170. * level because we need to walk this node to figure
  2171. * out which blocks to read.
  2172. */
  2173. btrfs_unlock_up_safe(p, level + 1);
  2174. btrfs_set_path_blocking(p);
  2175. if (p->reada != READA_NONE)
  2176. reada_for_search(fs_info, p, level, slot, key->objectid);
  2177. ret = -EAGAIN;
  2178. tmp = read_tree_block(fs_info, blocknr, gen, parent_level - 1,
  2179. &first_key);
  2180. if (!IS_ERR(tmp)) {
  2181. /*
  2182. * If the read above didn't mark this buffer up to date,
  2183. * it will never end up being up to date. Set ret to EIO now
  2184. * and give up so that our caller doesn't loop forever
  2185. * on our EAGAINs.
  2186. */
  2187. if (!extent_buffer_uptodate(tmp))
  2188. ret = -EIO;
  2189. free_extent_buffer(tmp);
  2190. } else {
  2191. ret = PTR_ERR(tmp);
  2192. }
  2193. btrfs_release_path(p);
  2194. return ret;
  2195. }
  2196. /*
  2197. * helper function for btrfs_search_slot. This does all of the checks
  2198. * for node-level blocks and does any balancing required based on
  2199. * the ins_len.
  2200. *
  2201. * If no extra work was required, zero is returned. If we had to
  2202. * drop the path, -EAGAIN is returned and btrfs_search_slot must
  2203. * start over
  2204. */
  2205. static int
  2206. setup_nodes_for_search(struct btrfs_trans_handle *trans,
  2207. struct btrfs_root *root, struct btrfs_path *p,
  2208. struct extent_buffer *b, int level, int ins_len,
  2209. int *write_lock_level)
  2210. {
  2211. struct btrfs_fs_info *fs_info = root->fs_info;
  2212. int ret;
  2213. if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
  2214. BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) {
  2215. int sret;
  2216. if (*write_lock_level < level + 1) {
  2217. *write_lock_level = level + 1;
  2218. btrfs_release_path(p);
  2219. goto again;
  2220. }
  2221. btrfs_set_path_blocking(p);
  2222. reada_for_balance(fs_info, p, level);
  2223. sret = split_node(trans, root, p, level);
  2224. BUG_ON(sret > 0);
  2225. if (sret) {
  2226. ret = sret;
  2227. goto done;
  2228. }
  2229. b = p->nodes[level];
  2230. } else if (ins_len < 0 && btrfs_header_nritems(b) <
  2231. BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 2) {
  2232. int sret;
  2233. if (*write_lock_level < level + 1) {
  2234. *write_lock_level = level + 1;
  2235. btrfs_release_path(p);
  2236. goto again;
  2237. }
  2238. btrfs_set_path_blocking(p);
  2239. reada_for_balance(fs_info, p, level);
  2240. sret = balance_level(trans, root, p, level);
  2241. if (sret) {
  2242. ret = sret;
  2243. goto done;
  2244. }
  2245. b = p->nodes[level];
  2246. if (!b) {
  2247. btrfs_release_path(p);
  2248. goto again;
  2249. }
  2250. BUG_ON(btrfs_header_nritems(b) == 1);
  2251. }
  2252. return 0;
  2253. again:
  2254. ret = -EAGAIN;
  2255. done:
  2256. return ret;
  2257. }
  2258. int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
  2259. u64 iobjectid, u64 ioff, u8 key_type,
  2260. struct btrfs_key *found_key)
  2261. {
  2262. int ret;
  2263. struct btrfs_key key;
  2264. struct extent_buffer *eb;
  2265. ASSERT(path);
  2266. ASSERT(found_key);
  2267. key.type = key_type;
  2268. key.objectid = iobjectid;
  2269. key.offset = ioff;
  2270. ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
  2271. if (ret < 0)
  2272. return ret;
  2273. eb = path->nodes[0];
  2274. if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
  2275. ret = btrfs_next_leaf(fs_root, path);
  2276. if (ret)
  2277. return ret;
  2278. eb = path->nodes[0];
  2279. }
  2280. btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
  2281. if (found_key->type != key.type ||
  2282. found_key->objectid != key.objectid)
  2283. return 1;
  2284. return 0;
  2285. }
  2286. static struct extent_buffer *btrfs_search_slot_get_root(struct btrfs_root *root,
  2287. struct btrfs_path *p,
  2288. int write_lock_level)
  2289. {
  2290. struct btrfs_fs_info *fs_info = root->fs_info;
  2291. struct extent_buffer *b;
  2292. int root_lock = 0;
  2293. int level = 0;
  2294. if (p->search_commit_root) {
  2295. /*
  2296. * The commit roots are read only so we always do read locks,
  2297. * and we always must hold the commit_root_sem when doing
  2298. * searches on them, the only exception is send where we don't
  2299. * want to block transaction commits for a long time, so
  2300. * we need to clone the commit root in order to avoid races
  2301. * with transaction commits that create a snapshot of one of
  2302. * the roots used by a send operation.
  2303. */
  2304. if (p->need_commit_sem) {
  2305. down_read(&fs_info->commit_root_sem);
  2306. b = btrfs_clone_extent_buffer(root->commit_root);
  2307. up_read(&fs_info->commit_root_sem);
  2308. if (!b)
  2309. return ERR_PTR(-ENOMEM);
  2310. } else {
  2311. b = root->commit_root;
  2312. atomic_inc(&b->refs);
  2313. }
  2314. level = btrfs_header_level(b);
  2315. /*
  2316. * Ensure that all callers have set skip_locking when
  2317. * p->search_commit_root = 1.
  2318. */
  2319. ASSERT(p->skip_locking == 1);
  2320. goto out;
  2321. }
  2322. if (p->skip_locking) {
  2323. b = btrfs_root_node(root);
  2324. level = btrfs_header_level(b);
  2325. goto out;
  2326. }
  2327. /* We try very hard to do read locks on the root */
  2328. root_lock = BTRFS_READ_LOCK;
  2329. /*
  2330. * If the level is set to maximum, we can skip trying to get the read
  2331. * lock.
  2332. */
  2333. if (write_lock_level < BTRFS_MAX_LEVEL) {
  2334. /*
  2335. * We don't know the level of the root node until we actually
  2336. * have it read locked
  2337. */
  2338. b = __btrfs_read_lock_root_node(root, p->recurse);
  2339. level = btrfs_header_level(b);
  2340. if (level > write_lock_level)
  2341. goto out;
  2342. /* Whoops, must trade for write lock */
  2343. btrfs_tree_read_unlock(b);
  2344. free_extent_buffer(b);
  2345. }
  2346. b = btrfs_lock_root_node(root);
  2347. root_lock = BTRFS_WRITE_LOCK;
  2348. /* The level might have changed, check again */
  2349. level = btrfs_header_level(b);
  2350. out:
  2351. /*
  2352. * The root may have failed to write out at some point, and thus is no
  2353. * longer valid, return an error in this case.
  2354. */
  2355. if (!extent_buffer_uptodate(b)) {
  2356. if (root_lock)
  2357. btrfs_tree_unlock_rw(b, root_lock);
  2358. free_extent_buffer(b);
  2359. return ERR_PTR(-EIO);
  2360. }
  2361. p->nodes[level] = b;
  2362. if (!p->skip_locking)
  2363. p->locks[level] = root_lock;
  2364. /*
  2365. * Callers are responsible for dropping b's references.
  2366. */
  2367. return b;
  2368. }
  2369. /*
  2370. * btrfs_search_slot - look for a key in a tree and perform necessary
  2371. * modifications to preserve tree invariants.
  2372. *
  2373. * @trans: Handle of transaction, used when modifying the tree
  2374. * @p: Holds all btree nodes along the search path
  2375. * @root: The root node of the tree
  2376. * @key: The key we are looking for
  2377. * @ins_len: Indicates purpose of search, for inserts it is 1, for
  2378. * deletions it's -1. 0 for plain searches
  2379. * @cow: boolean should CoW operations be performed. Must always be 1
  2380. * when modifying the tree.
  2381. *
  2382. * If @ins_len > 0, nodes and leaves will be split as we walk down the tree.
  2383. * If @ins_len < 0, nodes will be merged as we walk down the tree (if possible)
  2384. *
  2385. * If @key is found, 0 is returned and you can find the item in the leaf level
  2386. * of the path (level 0)
  2387. *
  2388. * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
  2389. * points to the slot where it should be inserted
  2390. *
  2391. * If an error is encountered while searching the tree a negative error number
  2392. * is returned
  2393. */
  2394. int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  2395. const struct btrfs_key *key, struct btrfs_path *p,
  2396. int ins_len, int cow)
  2397. {
  2398. struct extent_buffer *b;
  2399. int slot;
  2400. int ret;
  2401. int err;
  2402. int level;
  2403. int lowest_unlock = 1;
  2404. /* everything at write_lock_level or lower must be write locked */
  2405. int write_lock_level = 0;
  2406. u8 lowest_level = 0;
  2407. int min_write_lock_level;
  2408. int prev_cmp;
  2409. lowest_level = p->lowest_level;
  2410. WARN_ON(lowest_level && ins_len > 0);
  2411. WARN_ON(p->nodes[0] != NULL);
  2412. BUG_ON(!cow && ins_len);
  2413. if (ins_len < 0) {
  2414. lowest_unlock = 2;
  2415. /* when we are removing items, we might have to go up to level
  2416. * two as we update tree pointers Make sure we keep write
  2417. * for those levels as well
  2418. */
  2419. write_lock_level = 2;
  2420. } else if (ins_len > 0) {
  2421. /*
  2422. * for inserting items, make sure we have a write lock on
  2423. * level 1 so we can update keys
  2424. */
  2425. write_lock_level = 1;
  2426. }
  2427. if (!cow)
  2428. write_lock_level = -1;
  2429. if (cow && (p->keep_locks || p->lowest_level))
  2430. write_lock_level = BTRFS_MAX_LEVEL;
  2431. min_write_lock_level = write_lock_level;
  2432. again:
  2433. prev_cmp = -1;
  2434. b = btrfs_search_slot_get_root(root, p, write_lock_level);
  2435. if (IS_ERR(b)) {
  2436. ret = PTR_ERR(b);
  2437. goto done;
  2438. }
  2439. while (b) {
  2440. int dec = 0;
  2441. level = btrfs_header_level(b);
  2442. if (cow) {
  2443. bool last_level = (level == (BTRFS_MAX_LEVEL - 1));
  2444. /*
  2445. * if we don't really need to cow this block
  2446. * then we don't want to set the path blocking,
  2447. * so we test it here
  2448. */
  2449. if (!should_cow_block(trans, root, b)) {
  2450. trans->dirty = true;
  2451. goto cow_done;
  2452. }
  2453. /*
  2454. * must have write locks on this node and the
  2455. * parent
  2456. */
  2457. if (level > write_lock_level ||
  2458. (level + 1 > write_lock_level &&
  2459. level + 1 < BTRFS_MAX_LEVEL &&
  2460. p->nodes[level + 1])) {
  2461. write_lock_level = level + 1;
  2462. btrfs_release_path(p);
  2463. goto again;
  2464. }
  2465. btrfs_set_path_blocking(p);
  2466. if (last_level)
  2467. err = btrfs_cow_block(trans, root, b, NULL, 0,
  2468. &b,
  2469. BTRFS_NESTING_COW);
  2470. else
  2471. err = btrfs_cow_block(trans, root, b,
  2472. p->nodes[level + 1],
  2473. p->slots[level + 1], &b,
  2474. BTRFS_NESTING_COW);
  2475. if (err) {
  2476. ret = err;
  2477. goto done;
  2478. }
  2479. }
  2480. cow_done:
  2481. p->nodes[level] = b;
  2482. /*
  2483. * Leave path with blocking locks to avoid massive
  2484. * lock context switch, this is made on purpose.
  2485. */
  2486. /*
  2487. * we have a lock on b and as long as we aren't changing
  2488. * the tree, there is no way to for the items in b to change.
  2489. * It is safe to drop the lock on our parent before we
  2490. * go through the expensive btree search on b.
  2491. *
  2492. * If we're inserting or deleting (ins_len != 0), then we might
  2493. * be changing slot zero, which may require changing the parent.
  2494. * So, we can't drop the lock until after we know which slot
  2495. * we're operating on.
  2496. */
  2497. if (!ins_len && !p->keep_locks) {
  2498. int u = level + 1;
  2499. if (u < BTRFS_MAX_LEVEL && p->locks[u]) {
  2500. btrfs_tree_unlock_rw(p->nodes[u], p->locks[u]);
  2501. p->locks[u] = 0;
  2502. }
  2503. }
  2504. /*
  2505. * If btrfs_bin_search returns an exact match (prev_cmp == 0)
  2506. * we can safely assume the target key will always be in slot 0
  2507. * on lower levels due to the invariants BTRFS' btree provides,
  2508. * namely that a btrfs_key_ptr entry always points to the
  2509. * lowest key in the child node, thus we can skip searching
  2510. * lower levels
  2511. */
  2512. if (prev_cmp == 0) {
  2513. slot = 0;
  2514. ret = 0;
  2515. } else {
  2516. ret = btrfs_bin_search(b, key, &slot);
  2517. prev_cmp = ret;
  2518. if (ret < 0)
  2519. goto done;
  2520. }
  2521. if (level == 0) {
  2522. p->slots[level] = slot;
  2523. if (ins_len > 0 &&
  2524. btrfs_leaf_free_space(b) < ins_len) {
  2525. if (write_lock_level < 1) {
  2526. write_lock_level = 1;
  2527. btrfs_release_path(p);
  2528. goto again;
  2529. }
  2530. btrfs_set_path_blocking(p);
  2531. err = split_leaf(trans, root, key,
  2532. p, ins_len, ret == 0);
  2533. BUG_ON(err > 0);
  2534. if (err) {
  2535. ret = err;
  2536. goto done;
  2537. }
  2538. }
  2539. if (!p->search_for_split)
  2540. unlock_up(p, level, lowest_unlock,
  2541. min_write_lock_level, NULL);
  2542. goto done;
  2543. }
  2544. if (ret && slot > 0) {
  2545. dec = 1;
  2546. slot--;
  2547. }
  2548. p->slots[level] = slot;
  2549. err = setup_nodes_for_search(trans, root, p, b, level, ins_len,
  2550. &write_lock_level);
  2551. if (err == -EAGAIN)
  2552. goto again;
  2553. if (err) {
  2554. ret = err;
  2555. goto done;
  2556. }
  2557. b = p->nodes[level];
  2558. slot = p->slots[level];
  2559. /*
  2560. * Slot 0 is special, if we change the key we have to update
  2561. * the parent pointer which means we must have a write lock on
  2562. * the parent
  2563. */
  2564. if (slot == 0 && ins_len && write_lock_level < level + 1) {
  2565. write_lock_level = level + 1;
  2566. btrfs_release_path(p);
  2567. goto again;
  2568. }
  2569. unlock_up(p, level, lowest_unlock, min_write_lock_level,
  2570. &write_lock_level);
  2571. if (level == lowest_level) {
  2572. if (dec)
  2573. p->slots[level]++;
  2574. goto done;
  2575. }
  2576. err = read_block_for_search(root, p, &b, level, slot, key);
  2577. if (err == -EAGAIN)
  2578. goto again;
  2579. if (err) {
  2580. ret = err;
  2581. goto done;
  2582. }
  2583. if (!p->skip_locking) {
  2584. level = btrfs_header_level(b);
  2585. if (level <= write_lock_level) {
  2586. if (!btrfs_try_tree_write_lock(b)) {
  2587. btrfs_set_path_blocking(p);
  2588. btrfs_tree_lock(b);
  2589. }
  2590. p->locks[level] = BTRFS_WRITE_LOCK;
  2591. } else {
  2592. if (!btrfs_tree_read_lock_atomic(b)) {
  2593. btrfs_set_path_blocking(p);
  2594. __btrfs_tree_read_lock(b, BTRFS_NESTING_NORMAL,
  2595. p->recurse);
  2596. }
  2597. p->locks[level] = BTRFS_READ_LOCK;
  2598. }
  2599. p->nodes[level] = b;
  2600. }
  2601. }
  2602. ret = 1;
  2603. done:
  2604. /*
  2605. * we don't really know what they plan on doing with the path
  2606. * from here on, so for now just mark it as blocking
  2607. */
  2608. if (!p->leave_spinning)
  2609. btrfs_set_path_blocking(p);
  2610. if (ret < 0 && !p->skip_release_on_error)
  2611. btrfs_release_path(p);
  2612. return ret;
  2613. }
  2614. /*
  2615. * Like btrfs_search_slot, this looks for a key in the given tree. It uses the
  2616. * current state of the tree together with the operations recorded in the tree
  2617. * modification log to search for the key in a previous version of this tree, as
  2618. * denoted by the time_seq parameter.
  2619. *
  2620. * Naturally, there is no support for insert, delete or cow operations.
  2621. *
  2622. * The resulting path and return value will be set up as if we called
  2623. * btrfs_search_slot at that point in time with ins_len and cow both set to 0.
  2624. */
  2625. int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
  2626. struct btrfs_path *p, u64 time_seq)
  2627. {
  2628. struct btrfs_fs_info *fs_info = root->fs_info;
  2629. struct extent_buffer *b;
  2630. int slot;
  2631. int ret;
  2632. int err;
  2633. int level;
  2634. int lowest_unlock = 1;
  2635. u8 lowest_level = 0;
  2636. lowest_level = p->lowest_level;
  2637. WARN_ON(p->nodes[0] != NULL);
  2638. if (p->search_commit_root) {
  2639. BUG_ON(time_seq);
  2640. return btrfs_search_slot(NULL, root, key, p, 0, 0);
  2641. }
  2642. again:
  2643. b = get_old_root(root, time_seq);
  2644. if (!b) {
  2645. ret = -EIO;
  2646. goto done;
  2647. }
  2648. level = btrfs_header_level(b);
  2649. p->locks[level] = BTRFS_READ_LOCK;
  2650. while (b) {
  2651. int dec = 0;
  2652. level = btrfs_header_level(b);
  2653. p->nodes[level] = b;
  2654. /*
  2655. * we have a lock on b and as long as we aren't changing
  2656. * the tree, there is no way to for the items in b to change.
  2657. * It is safe to drop the lock on our parent before we
  2658. * go through the expensive btree search on b.
  2659. */
  2660. btrfs_unlock_up_safe(p, level + 1);
  2661. ret = btrfs_bin_search(b, key, &slot);
  2662. if (ret < 0)
  2663. goto done;
  2664. if (level == 0) {
  2665. p->slots[level] = slot;
  2666. unlock_up(p, level, lowest_unlock, 0, NULL);
  2667. goto done;
  2668. }
  2669. if (ret && slot > 0) {
  2670. dec = 1;
  2671. slot--;
  2672. }
  2673. p->slots[level] = slot;
  2674. unlock_up(p, level, lowest_unlock, 0, NULL);
  2675. if (level == lowest_level) {
  2676. if (dec)
  2677. p->slots[level]++;
  2678. goto done;
  2679. }
  2680. err = read_block_for_search(root, p, &b, level, slot, key);
  2681. if (err == -EAGAIN)
  2682. goto again;
  2683. if (err) {
  2684. ret = err;
  2685. goto done;
  2686. }
  2687. level = btrfs_header_level(b);
  2688. if (!btrfs_tree_read_lock_atomic(b)) {
  2689. btrfs_set_path_blocking(p);
  2690. btrfs_tree_read_lock(b);
  2691. }
  2692. b = tree_mod_log_rewind(fs_info, p, b, time_seq);
  2693. if (!b) {
  2694. ret = -ENOMEM;
  2695. goto done;
  2696. }
  2697. p->locks[level] = BTRFS_READ_LOCK;
  2698. p->nodes[level] = b;
  2699. }
  2700. ret = 1;
  2701. done:
  2702. if (!p->leave_spinning)
  2703. btrfs_set_path_blocking(p);
  2704. if (ret < 0)
  2705. btrfs_release_path(p);
  2706. return ret;
  2707. }
  2708. /*
  2709. * helper to use instead of search slot if no exact match is needed but
  2710. * instead the next or previous item should be returned.
  2711. * When find_higher is true, the next higher item is returned, the next lower
  2712. * otherwise.
  2713. * When return_any and find_higher are both true, and no higher item is found,
  2714. * return the next lower instead.
  2715. * When return_any is true and find_higher is false, and no lower item is found,
  2716. * return the next higher instead.
  2717. * It returns 0 if any item is found, 1 if none is found (tree empty), and
  2718. * < 0 on error
  2719. */
  2720. int btrfs_search_slot_for_read(struct btrfs_root *root,
  2721. const struct btrfs_key *key,
  2722. struct btrfs_path *p, int find_higher,
  2723. int return_any)
  2724. {
  2725. int ret;
  2726. struct extent_buffer *leaf;
  2727. again:
  2728. ret = btrfs_search_slot(NULL, root, key, p, 0, 0);
  2729. if (ret <= 0)
  2730. return ret;
  2731. /*
  2732. * a return value of 1 means the path is at the position where the
  2733. * item should be inserted. Normally this is the next bigger item,
  2734. * but in case the previous item is the last in a leaf, path points
  2735. * to the first free slot in the previous leaf, i.e. at an invalid
  2736. * item.
  2737. */
  2738. leaf = p->nodes[0];
  2739. if (find_higher) {
  2740. if (p->slots[0] >= btrfs_header_nritems(leaf)) {
  2741. ret = btrfs_next_leaf(root, p);
  2742. if (ret <= 0)
  2743. return ret;
  2744. if (!return_any)
  2745. return 1;
  2746. /*
  2747. * no higher item found, return the next
  2748. * lower instead
  2749. */
  2750. return_any = 0;
  2751. find_higher = 0;
  2752. btrfs_release_path(p);
  2753. goto again;
  2754. }
  2755. } else {
  2756. if (p->slots[0] == 0) {
  2757. ret = btrfs_prev_leaf(root, p);
  2758. if (ret < 0)
  2759. return ret;
  2760. if (!ret) {
  2761. leaf = p->nodes[0];
  2762. if (p->slots[0] == btrfs_header_nritems(leaf))
  2763. p->slots[0]--;
  2764. return 0;
  2765. }
  2766. if (!return_any)
  2767. return 1;
  2768. /*
  2769. * no lower item found, return the next
  2770. * higher instead
  2771. */
  2772. return_any = 0;
  2773. find_higher = 1;
  2774. btrfs_release_path(p);
  2775. goto again;
  2776. } else {
  2777. --p->slots[0];
  2778. }
  2779. }
  2780. return 0;
  2781. }
  2782. /*
  2783. * adjust the pointers going up the tree, starting at level
  2784. * making sure the right key of each node is points to 'key'.
  2785. * This is used after shifting pointers to the left, so it stops
  2786. * fixing up pointers when a given leaf/node is not in slot 0 of the
  2787. * higher levels
  2788. *
  2789. */
  2790. static void fixup_low_keys(struct btrfs_path *path,
  2791. struct btrfs_disk_key *key, int level)
  2792. {
  2793. int i;
  2794. struct extent_buffer *t;
  2795. int ret;
  2796. for (i = level; i < BTRFS_MAX_LEVEL; i++) {
  2797. int tslot = path->slots[i];
  2798. if (!path->nodes[i])
  2799. break;
  2800. t = path->nodes[i];
  2801. ret = tree_mod_log_insert_key(t, tslot, MOD_LOG_KEY_REPLACE,
  2802. GFP_ATOMIC);
  2803. BUG_ON(ret < 0);
  2804. btrfs_set_node_key(t, key, tslot);
  2805. btrfs_mark_buffer_dirty(path->nodes[i]);
  2806. if (tslot != 0)
  2807. break;
  2808. }
  2809. }
  2810. /*
  2811. * update item key.
  2812. *
  2813. * This function isn't completely safe. It's the caller's responsibility
  2814. * that the new key won't break the order
  2815. */
  2816. void btrfs_set_item_key_safe(struct btrfs_fs_info *fs_info,
  2817. struct btrfs_path *path,
  2818. const struct btrfs_key *new_key)
  2819. {
  2820. struct btrfs_disk_key disk_key;
  2821. struct extent_buffer *eb;
  2822. int slot;
  2823. eb = path->nodes[0];
  2824. slot = path->slots[0];
  2825. if (slot > 0) {
  2826. btrfs_item_key(eb, &disk_key, slot - 1);
  2827. if (unlikely(comp_keys(&disk_key, new_key) >= 0)) {
  2828. btrfs_crit(fs_info,
  2829. "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
  2830. slot, btrfs_disk_key_objectid(&disk_key),
  2831. btrfs_disk_key_type(&disk_key),
  2832. btrfs_disk_key_offset(&disk_key),
  2833. new_key->objectid, new_key->type,
  2834. new_key->offset);
  2835. btrfs_print_leaf(eb);
  2836. BUG();
  2837. }
  2838. }
  2839. if (slot < btrfs_header_nritems(eb) - 1) {
  2840. btrfs_item_key(eb, &disk_key, slot + 1);
  2841. if (unlikely(comp_keys(&disk_key, new_key) <= 0)) {
  2842. btrfs_crit(fs_info,
  2843. "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
  2844. slot, btrfs_disk_key_objectid(&disk_key),
  2845. btrfs_disk_key_type(&disk_key),
  2846. btrfs_disk_key_offset(&disk_key),
  2847. new_key->objectid, new_key->type,
  2848. new_key->offset);
  2849. btrfs_print_leaf(eb);
  2850. BUG();
  2851. }
  2852. }
  2853. btrfs_cpu_key_to_disk(&disk_key, new_key);
  2854. btrfs_set_item_key(eb, &disk_key, slot);
  2855. btrfs_mark_buffer_dirty(eb);
  2856. if (slot == 0)
  2857. fixup_low_keys(path, &disk_key, 1);
  2858. }
  2859. /*
  2860. * Check key order of two sibling extent buffers.
  2861. *
  2862. * Return true if something is wrong.
  2863. * Return false if everything is fine.
  2864. *
  2865. * Tree-checker only works inside one tree block, thus the following
  2866. * corruption can not be detected by tree-checker:
  2867. *
  2868. * Leaf @left | Leaf @right
  2869. * --------------------------------------------------------------
  2870. * | 1 | 2 | 3 | 4 | 5 | f6 | | 7 | 8 |
  2871. *
  2872. * Key f6 in leaf @left itself is valid, but not valid when the next
  2873. * key in leaf @right is 7.
  2874. * This can only be checked at tree block merge time.
  2875. * And since tree checker has ensured all key order in each tree block
  2876. * is correct, we only need to bother the last key of @left and the first
  2877. * key of @right.
  2878. */
  2879. static bool check_sibling_keys(struct extent_buffer *left,
  2880. struct extent_buffer *right)
  2881. {
  2882. struct btrfs_key left_last;
  2883. struct btrfs_key right_first;
  2884. int level = btrfs_header_level(left);
  2885. int nr_left = btrfs_header_nritems(left);
  2886. int nr_right = btrfs_header_nritems(right);
  2887. /* No key to check in one of the tree blocks */
  2888. if (!nr_left || !nr_right)
  2889. return false;
  2890. if (level) {
  2891. btrfs_node_key_to_cpu(left, &left_last, nr_left - 1);
  2892. btrfs_node_key_to_cpu(right, &right_first, 0);
  2893. } else {
  2894. btrfs_item_key_to_cpu(left, &left_last, nr_left - 1);
  2895. btrfs_item_key_to_cpu(right, &right_first, 0);
  2896. }
  2897. if (btrfs_comp_cpu_keys(&left_last, &right_first) >= 0) {
  2898. btrfs_crit(left->fs_info,
  2899. "bad key order, sibling blocks, left last (%llu %u %llu) right first (%llu %u %llu)",
  2900. left_last.objectid, left_last.type,
  2901. left_last.offset, right_first.objectid,
  2902. right_first.type, right_first.offset);
  2903. return true;
  2904. }
  2905. return false;
  2906. }
  2907. /*
  2908. * try to push data from one node into the next node left in the
  2909. * tree.
  2910. *
  2911. * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
  2912. * error, and > 0 if there was no room in the left hand block.
  2913. */
  2914. static int push_node_left(struct btrfs_trans_handle *trans,
  2915. struct extent_buffer *dst,
  2916. struct extent_buffer *src, int empty)
  2917. {
  2918. struct btrfs_fs_info *fs_info = trans->fs_info;
  2919. int push_items = 0;
  2920. int src_nritems;
  2921. int dst_nritems;
  2922. int ret = 0;
  2923. src_nritems = btrfs_header_nritems(src);
  2924. dst_nritems = btrfs_header_nritems(dst);
  2925. push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems;
  2926. WARN_ON(btrfs_header_generation(src) != trans->transid);
  2927. WARN_ON(btrfs_header_generation(dst) != trans->transid);
  2928. if (!empty && src_nritems <= 8)
  2929. return 1;
  2930. if (push_items <= 0)
  2931. return 1;
  2932. if (empty) {
  2933. push_items = min(src_nritems, push_items);
  2934. if (push_items < src_nritems) {
  2935. /* leave at least 8 pointers in the node if
  2936. * we aren't going to empty it
  2937. */
  2938. if (src_nritems - push_items < 8) {
  2939. if (push_items <= 8)
  2940. return 1;
  2941. push_items -= 8;
  2942. }
  2943. }
  2944. } else
  2945. push_items = min(src_nritems - 8, push_items);
  2946. /* dst is the left eb, src is the middle eb */
  2947. if (check_sibling_keys(dst, src)) {
  2948. ret = -EUCLEAN;
  2949. btrfs_abort_transaction(trans, ret);
  2950. return ret;
  2951. }
  2952. ret = tree_mod_log_eb_copy(dst, src, dst_nritems, 0, push_items);
  2953. if (ret) {
  2954. btrfs_abort_transaction(trans, ret);
  2955. return ret;
  2956. }
  2957. copy_extent_buffer(dst, src,
  2958. btrfs_node_key_ptr_offset(dst_nritems),
  2959. btrfs_node_key_ptr_offset(0),
  2960. push_items * sizeof(struct btrfs_key_ptr));
  2961. if (push_items < src_nritems) {
  2962. /*
  2963. * Don't call tree_mod_log_insert_move here, key removal was
  2964. * already fully logged by tree_mod_log_eb_copy above.
  2965. */
  2966. memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
  2967. btrfs_node_key_ptr_offset(push_items),
  2968. (src_nritems - push_items) *
  2969. sizeof(struct btrfs_key_ptr));
  2970. }
  2971. btrfs_set_header_nritems(src, src_nritems - push_items);
  2972. btrfs_set_header_nritems(dst, dst_nritems + push_items);
  2973. btrfs_mark_buffer_dirty(src);
  2974. btrfs_mark_buffer_dirty(dst);
  2975. return ret;
  2976. }
  2977. /*
  2978. * try to push data from one node into the next node right in the
  2979. * tree.
  2980. *
  2981. * returns 0 if some ptrs were pushed, < 0 if there was some horrible
  2982. * error, and > 0 if there was no room in the right hand block.
  2983. *
  2984. * this will only push up to 1/2 the contents of the left node over
  2985. */
  2986. static int balance_node_right(struct btrfs_trans_handle *trans,
  2987. struct extent_buffer *dst,
  2988. struct extent_buffer *src)
  2989. {
  2990. struct btrfs_fs_info *fs_info = trans->fs_info;
  2991. int push_items = 0;
  2992. int max_push;
  2993. int src_nritems;
  2994. int dst_nritems;
  2995. int ret = 0;
  2996. WARN_ON(btrfs_header_generation(src) != trans->transid);
  2997. WARN_ON(btrfs_header_generation(dst) != trans->transid);
  2998. src_nritems = btrfs_header_nritems(src);
  2999. dst_nritems = btrfs_header_nritems(dst);
  3000. push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems;
  3001. if (push_items <= 0)
  3002. return 1;
  3003. if (src_nritems < 4)
  3004. return 1;
  3005. max_push = src_nritems / 2 + 1;
  3006. /* don't try to empty the node */
  3007. if (max_push >= src_nritems)
  3008. return 1;
  3009. if (max_push < push_items)
  3010. push_items = max_push;
  3011. /* dst is the right eb, src is the middle eb */
  3012. if (check_sibling_keys(src, dst)) {
  3013. ret = -EUCLEAN;
  3014. btrfs_abort_transaction(trans, ret);
  3015. return ret;
  3016. }
  3017. ret = tree_mod_log_insert_move(dst, push_items, 0, dst_nritems);
  3018. BUG_ON(ret < 0);
  3019. memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
  3020. btrfs_node_key_ptr_offset(0),
  3021. (dst_nritems) *
  3022. sizeof(struct btrfs_key_ptr));
  3023. ret = tree_mod_log_eb_copy(dst, src, 0, src_nritems - push_items,
  3024. push_items);
  3025. if (ret) {
  3026. btrfs_abort_transaction(trans, ret);
  3027. return ret;
  3028. }
  3029. copy_extent_buffer(dst, src,
  3030. btrfs_node_key_ptr_offset(0),
  3031. btrfs_node_key_ptr_offset(src_nritems - push_items),
  3032. push_items * sizeof(struct btrfs_key_ptr));
  3033. btrfs_set_header_nritems(src, src_nritems - push_items);
  3034. btrfs_set_header_nritems(dst, dst_nritems + push_items);
  3035. btrfs_mark_buffer_dirty(src);
  3036. btrfs_mark_buffer_dirty(dst);
  3037. return ret;
  3038. }
  3039. /*
  3040. * helper function to insert a new root level in the tree.
  3041. * A new node is allocated, and a single item is inserted to
  3042. * point to the existing root
  3043. *
  3044. * returns zero on success or < 0 on failure.
  3045. */
  3046. static noinline int insert_new_root(struct btrfs_trans_handle *trans,
  3047. struct btrfs_root *root,
  3048. struct btrfs_path *path, int level)
  3049. {
  3050. struct btrfs_fs_info *fs_info = root->fs_info;
  3051. u64 lower_gen;
  3052. struct extent_buffer *lower;
  3053. struct extent_buffer *c;
  3054. struct extent_buffer *old;
  3055. struct btrfs_disk_key lower_key;
  3056. int ret;
  3057. BUG_ON(path->nodes[level]);
  3058. BUG_ON(path->nodes[level-1] != root->node);
  3059. lower = path->nodes[level-1];
  3060. if (level == 1)
  3061. btrfs_item_key(lower, &lower_key, 0);
  3062. else
  3063. btrfs_node_key(lower, &lower_key, 0);
  3064. c = alloc_tree_block_no_bg_flush(trans, root, 0, &lower_key, level,
  3065. root->node->start, 0,
  3066. BTRFS_NESTING_NEW_ROOT);
  3067. if (IS_ERR(c))
  3068. return PTR_ERR(c);
  3069. root_add_used(root, fs_info->nodesize);
  3070. btrfs_set_header_nritems(c, 1);
  3071. btrfs_set_node_key(c, &lower_key, 0);
  3072. btrfs_set_node_blockptr(c, 0, lower->start);
  3073. lower_gen = btrfs_header_generation(lower);
  3074. WARN_ON(lower_gen != trans->transid);
  3075. btrfs_set_node_ptr_generation(c, 0, lower_gen);
  3076. btrfs_mark_buffer_dirty(c);
  3077. old = root->node;
  3078. ret = tree_mod_log_insert_root(root->node, c, 0);
  3079. BUG_ON(ret < 0);
  3080. rcu_assign_pointer(root->node, c);
  3081. /* the super has an extra ref to root->node */
  3082. free_extent_buffer(old);
  3083. add_root_to_dirty_list(root);
  3084. atomic_inc(&c->refs);
  3085. path->nodes[level] = c;
  3086. path->locks[level] = BTRFS_WRITE_LOCK_BLOCKING;
  3087. path->slots[level] = 0;
  3088. return 0;
  3089. }
  3090. /*
  3091. * worker function to insert a single pointer in a node.
  3092. * the node should have enough room for the pointer already
  3093. *
  3094. * slot and level indicate where you want the key to go, and
  3095. * blocknr is the block the key points to.
  3096. */
  3097. static void insert_ptr(struct btrfs_trans_handle *trans,
  3098. struct btrfs_path *path,
  3099. struct btrfs_disk_key *key, u64 bytenr,
  3100. int slot, int level)
  3101. {
  3102. struct extent_buffer *lower;
  3103. int nritems;
  3104. int ret;
  3105. BUG_ON(!path->nodes[level]);
  3106. btrfs_assert_tree_locked(path->nodes[level]);
  3107. lower = path->nodes[level];
  3108. nritems = btrfs_header_nritems(lower);
  3109. BUG_ON(slot > nritems);
  3110. BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(trans->fs_info));
  3111. if (slot != nritems) {
  3112. if (level) {
  3113. ret = tree_mod_log_insert_move(lower, slot + 1, slot,
  3114. nritems - slot);
  3115. BUG_ON(ret < 0);
  3116. }
  3117. memmove_extent_buffer(lower,
  3118. btrfs_node_key_ptr_offset(slot + 1),
  3119. btrfs_node_key_ptr_offset(slot),
  3120. (nritems - slot) * sizeof(struct btrfs_key_ptr));
  3121. }
  3122. if (level) {
  3123. ret = tree_mod_log_insert_key(lower, slot, MOD_LOG_KEY_ADD,
  3124. GFP_NOFS);
  3125. BUG_ON(ret < 0);
  3126. }
  3127. btrfs_set_node_key(lower, key, slot);
  3128. btrfs_set_node_blockptr(lower, slot, bytenr);
  3129. WARN_ON(trans->transid == 0);
  3130. btrfs_set_node_ptr_generation(lower, slot, trans->transid);
  3131. btrfs_set_header_nritems(lower, nritems + 1);
  3132. btrfs_mark_buffer_dirty(lower);
  3133. }
  3134. /*
  3135. * split the node at the specified level in path in two.
  3136. * The path is corrected to point to the appropriate node after the split
  3137. *
  3138. * Before splitting this tries to make some room in the node by pushing
  3139. * left and right, if either one works, it returns right away.
  3140. *
  3141. * returns 0 on success and < 0 on failure
  3142. */
  3143. static noinline int split_node(struct btrfs_trans_handle *trans,
  3144. struct btrfs_root *root,
  3145. struct btrfs_path *path, int level)
  3146. {
  3147. struct btrfs_fs_info *fs_info = root->fs_info;
  3148. struct extent_buffer *c;
  3149. struct extent_buffer *split;
  3150. struct btrfs_disk_key disk_key;
  3151. int mid;
  3152. int ret;
  3153. u32 c_nritems;
  3154. c = path->nodes[level];
  3155. WARN_ON(btrfs_header_generation(c) != trans->transid);
  3156. if (c == root->node) {
  3157. /*
  3158. * trying to split the root, lets make a new one
  3159. *
  3160. * tree mod log: We don't log_removal old root in
  3161. * insert_new_root, because that root buffer will be kept as a
  3162. * normal node. We are going to log removal of half of the
  3163. * elements below with tree_mod_log_eb_copy. We're holding a
  3164. * tree lock on the buffer, which is why we cannot race with
  3165. * other tree_mod_log users.
  3166. */
  3167. ret = insert_new_root(trans, root, path, level + 1);
  3168. if (ret)
  3169. return ret;
  3170. } else {
  3171. ret = push_nodes_for_insert(trans, root, path, level);
  3172. c = path->nodes[level];
  3173. if (!ret && btrfs_header_nritems(c) <
  3174. BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3)
  3175. return 0;
  3176. if (ret < 0)
  3177. return ret;
  3178. }
  3179. c_nritems = btrfs_header_nritems(c);
  3180. mid = (c_nritems + 1) / 2;
  3181. btrfs_node_key(c, &disk_key, mid);
  3182. split = alloc_tree_block_no_bg_flush(trans, root, 0, &disk_key, level,
  3183. c->start, 0, BTRFS_NESTING_SPLIT);
  3184. if (IS_ERR(split))
  3185. return PTR_ERR(split);
  3186. root_add_used(root, fs_info->nodesize);
  3187. ASSERT(btrfs_header_level(c) == level);
  3188. ret = tree_mod_log_eb_copy(split, c, 0, mid, c_nritems - mid);
  3189. if (ret) {
  3190. btrfs_abort_transaction(trans, ret);
  3191. return ret;
  3192. }
  3193. copy_extent_buffer(split, c,
  3194. btrfs_node_key_ptr_offset(0),
  3195. btrfs_node_key_ptr_offset(mid),
  3196. (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
  3197. btrfs_set_header_nritems(split, c_nritems - mid);
  3198. btrfs_set_header_nritems(c, mid);
  3199. ret = 0;
  3200. btrfs_mark_buffer_dirty(c);
  3201. btrfs_mark_buffer_dirty(split);
  3202. insert_ptr(trans, path, &disk_key, split->start,
  3203. path->slots[level + 1] + 1, level + 1);
  3204. if (path->slots[level] >= mid) {
  3205. path->slots[level] -= mid;
  3206. btrfs_tree_unlock(c);
  3207. free_extent_buffer(c);
  3208. path->nodes[level] = split;
  3209. path->slots[level + 1] += 1;
  3210. } else {
  3211. btrfs_tree_unlock(split);
  3212. free_extent_buffer(split);
  3213. }
  3214. return ret;
  3215. }
  3216. /*
  3217. * how many bytes are required to store the items in a leaf. start
  3218. * and nr indicate which items in the leaf to check. This totals up the
  3219. * space used both by the item structs and the item data
  3220. */
  3221. static int leaf_space_used(struct extent_buffer *l, int start, int nr)
  3222. {
  3223. struct btrfs_item *start_item;
  3224. struct btrfs_item *end_item;
  3225. int data_len;
  3226. int nritems = btrfs_header_nritems(l);
  3227. int end = min(nritems, start + nr) - 1;
  3228. if (!nr)
  3229. return 0;
  3230. start_item = btrfs_item_nr(start);
  3231. end_item = btrfs_item_nr(end);
  3232. data_len = btrfs_item_offset(l, start_item) +
  3233. btrfs_item_size(l, start_item);
  3234. data_len = data_len - btrfs_item_offset(l, end_item);
  3235. data_len += sizeof(struct btrfs_item) * nr;
  3236. WARN_ON(data_len < 0);
  3237. return data_len;
  3238. }
  3239. /*
  3240. * The space between the end of the leaf items and
  3241. * the start of the leaf data. IOW, how much room
  3242. * the leaf has left for both items and data
  3243. */
  3244. noinline int btrfs_leaf_free_space(struct extent_buffer *leaf)
  3245. {
  3246. struct btrfs_fs_info *fs_info = leaf->fs_info;
  3247. int nritems = btrfs_header_nritems(leaf);
  3248. int ret;
  3249. ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems);
  3250. if (ret < 0) {
  3251. btrfs_crit(fs_info,
  3252. "leaf free space ret %d, leaf data size %lu, used %d nritems %d",
  3253. ret,
  3254. (unsigned long) BTRFS_LEAF_DATA_SIZE(fs_info),
  3255. leaf_space_used(leaf, 0, nritems), nritems);
  3256. }
  3257. return ret;
  3258. }
  3259. /*
  3260. * min slot controls the lowest index we're willing to push to the
  3261. * right. We'll push up to and including min_slot, but no lower
  3262. */
  3263. static noinline int __push_leaf_right(struct btrfs_path *path,
  3264. int data_size, int empty,
  3265. struct extent_buffer *right,
  3266. int free_space, u32 left_nritems,
  3267. u32 min_slot)
  3268. {
  3269. struct btrfs_fs_info *fs_info = right->fs_info;
  3270. struct extent_buffer *left = path->nodes[0];
  3271. struct extent_buffer *upper = path->nodes[1];
  3272. struct btrfs_map_token token;
  3273. struct btrfs_disk_key disk_key;
  3274. int slot;
  3275. u32 i;
  3276. int push_space = 0;
  3277. int push_items = 0;
  3278. struct btrfs_item *item;
  3279. u32 nr;
  3280. u32 right_nritems;
  3281. u32 data_end;
  3282. u32 this_item_size;
  3283. if (empty)
  3284. nr = 0;
  3285. else
  3286. nr = max_t(u32, 1, min_slot);
  3287. if (path->slots[0] >= left_nritems)
  3288. push_space += data_size;
  3289. slot = path->slots[1];
  3290. i = left_nritems - 1;
  3291. while (i >= nr) {
  3292. item = btrfs_item_nr(i);
  3293. if (!empty && push_items > 0) {
  3294. if (path->slots[0] > i)
  3295. break;
  3296. if (path->slots[0] == i) {
  3297. int space = btrfs_leaf_free_space(left);
  3298. if (space + push_space * 2 > free_space)
  3299. break;
  3300. }
  3301. }
  3302. if (path->slots[0] == i)
  3303. push_space += data_size;
  3304. this_item_size = btrfs_item_size(left, item);
  3305. if (this_item_size + sizeof(*item) + push_space > free_space)
  3306. break;
  3307. push_items++;
  3308. push_space += this_item_size + sizeof(*item);
  3309. if (i == 0)
  3310. break;
  3311. i--;
  3312. }
  3313. if (push_items == 0)
  3314. goto out_unlock;
  3315. WARN_ON(!empty && push_items == left_nritems);
  3316. /* push left to right */
  3317. right_nritems = btrfs_header_nritems(right);
  3318. push_space = btrfs_item_end_nr(left, left_nritems - push_items);
  3319. push_space -= leaf_data_end(left);
  3320. /* make room in the right data area */
  3321. data_end = leaf_data_end(right);
  3322. memmove_extent_buffer(right,
  3323. BTRFS_LEAF_DATA_OFFSET + data_end - push_space,
  3324. BTRFS_LEAF_DATA_OFFSET + data_end,
  3325. BTRFS_LEAF_DATA_SIZE(fs_info) - data_end);
  3326. /* copy from the left data area */
  3327. copy_extent_buffer(right, left, BTRFS_LEAF_DATA_OFFSET +
  3328. BTRFS_LEAF_DATA_SIZE(fs_info) - push_space,
  3329. BTRFS_LEAF_DATA_OFFSET + leaf_data_end(left),
  3330. push_space);
  3331. memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
  3332. btrfs_item_nr_offset(0),
  3333. right_nritems * sizeof(struct btrfs_item));
  3334. /* copy the items from left to right */
  3335. copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
  3336. btrfs_item_nr_offset(left_nritems - push_items),
  3337. push_items * sizeof(struct btrfs_item));
  3338. /* update the item pointers */
  3339. btrfs_init_map_token(&token, right);
  3340. right_nritems += push_items;
  3341. btrfs_set_header_nritems(right, right_nritems);
  3342. push_space = BTRFS_LEAF_DATA_SIZE(fs_info);
  3343. for (i = 0; i < right_nritems; i++) {
  3344. item = btrfs_item_nr(i);
  3345. push_space -= btrfs_token_item_size(&token, item);
  3346. btrfs_set_token_item_offset(&token, item, push_space);
  3347. }
  3348. left_nritems -= push_items;
  3349. btrfs_set_header_nritems(left, left_nritems);
  3350. if (left_nritems)
  3351. btrfs_mark_buffer_dirty(left);
  3352. else
  3353. btrfs_clean_tree_block(left);
  3354. btrfs_mark_buffer_dirty(right);
  3355. btrfs_item_key(right, &disk_key, 0);
  3356. btrfs_set_node_key(upper, &disk_key, slot + 1);
  3357. btrfs_mark_buffer_dirty(upper);
  3358. /* then fixup the leaf pointer in the path */
  3359. if (path->slots[0] >= left_nritems) {
  3360. path->slots[0] -= left_nritems;
  3361. if (btrfs_header_nritems(path->nodes[0]) == 0)
  3362. btrfs_clean_tree_block(path->nodes[0]);
  3363. btrfs_tree_unlock(path->nodes[0]);
  3364. free_extent_buffer(path->nodes[0]);
  3365. path->nodes[0] = right;
  3366. path->slots[1] += 1;
  3367. } else {
  3368. btrfs_tree_unlock(right);
  3369. free_extent_buffer(right);
  3370. }
  3371. return 0;
  3372. out_unlock:
  3373. btrfs_tree_unlock(right);
  3374. free_extent_buffer(right);
  3375. return 1;
  3376. }
  3377. /*
  3378. * push some data in the path leaf to the right, trying to free up at
  3379. * least data_size bytes. returns zero if the push worked, nonzero otherwise
  3380. *
  3381. * returns 1 if the push failed because the other node didn't have enough
  3382. * room, 0 if everything worked out and < 0 if there were major errors.
  3383. *
  3384. * this will push starting from min_slot to the end of the leaf. It won't
  3385. * push any slot lower than min_slot
  3386. */
  3387. static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
  3388. *root, struct btrfs_path *path,
  3389. int min_data_size, int data_size,
  3390. int empty, u32 min_slot)
  3391. {
  3392. struct extent_buffer *left = path->nodes[0];
  3393. struct extent_buffer *right;
  3394. struct extent_buffer *upper;
  3395. int slot;
  3396. int free_space;
  3397. u32 left_nritems;
  3398. int ret;
  3399. if (!path->nodes[1])
  3400. return 1;
  3401. slot = path->slots[1];
  3402. upper = path->nodes[1];
  3403. if (slot >= btrfs_header_nritems(upper) - 1)
  3404. return 1;
  3405. btrfs_assert_tree_locked(path->nodes[1]);
  3406. right = btrfs_read_node_slot(upper, slot + 1);
  3407. /*
  3408. * slot + 1 is not valid or we fail to read the right node,
  3409. * no big deal, just return.
  3410. */
  3411. if (IS_ERR(right))
  3412. return 1;
  3413. __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
  3414. btrfs_set_lock_blocking_write(right);
  3415. free_space = btrfs_leaf_free_space(right);
  3416. if (free_space < data_size)
  3417. goto out_unlock;
  3418. /* cow and double check */
  3419. ret = btrfs_cow_block(trans, root, right, upper,
  3420. slot + 1, &right, BTRFS_NESTING_RIGHT_COW);
  3421. if (ret)
  3422. goto out_unlock;
  3423. free_space = btrfs_leaf_free_space(right);
  3424. if (free_space < data_size)
  3425. goto out_unlock;
  3426. left_nritems = btrfs_header_nritems(left);
  3427. if (left_nritems == 0)
  3428. goto out_unlock;
  3429. if (check_sibling_keys(left, right)) {
  3430. ret = -EUCLEAN;
  3431. btrfs_tree_unlock(right);
  3432. free_extent_buffer(right);
  3433. return ret;
  3434. }
  3435. if (path->slots[0] == left_nritems && !empty) {
  3436. /* Key greater than all keys in the leaf, right neighbor has
  3437. * enough room for it and we're not emptying our leaf to delete
  3438. * it, therefore use right neighbor to insert the new item and
  3439. * no need to touch/dirty our left leaf. */
  3440. btrfs_tree_unlock(left);
  3441. free_extent_buffer(left);
  3442. path->nodes[0] = right;
  3443. path->slots[0] = 0;
  3444. path->slots[1]++;
  3445. return 0;
  3446. }
  3447. return __push_leaf_right(path, min_data_size, empty,
  3448. right, free_space, left_nritems, min_slot);
  3449. out_unlock:
  3450. btrfs_tree_unlock(right);
  3451. free_extent_buffer(right);
  3452. return 1;
  3453. }
  3454. /*
  3455. * push some data in the path leaf to the left, trying to free up at
  3456. * least data_size bytes. returns zero if the push worked, nonzero otherwise
  3457. *
  3458. * max_slot can put a limit on how far into the leaf we'll push items. The
  3459. * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the
  3460. * items
  3461. */
  3462. static noinline int __push_leaf_left(struct btrfs_path *path, int data_size,
  3463. int empty, struct extent_buffer *left,
  3464. int free_space, u32 right_nritems,
  3465. u32 max_slot)
  3466. {
  3467. struct btrfs_fs_info *fs_info = left->fs_info;
  3468. struct btrfs_disk_key disk_key;
  3469. struct extent_buffer *right = path->nodes[0];
  3470. int i;
  3471. int push_space = 0;
  3472. int push_items = 0;
  3473. struct btrfs_item *item;
  3474. u32 old_left_nritems;
  3475. u32 nr;
  3476. int ret = 0;
  3477. u32 this_item_size;
  3478. u32 old_left_item_size;
  3479. struct btrfs_map_token token;
  3480. if (empty)
  3481. nr = min(right_nritems, max_slot);
  3482. else
  3483. nr = min(right_nritems - 1, max_slot);
  3484. for (i = 0; i < nr; i++) {
  3485. item = btrfs_item_nr(i);
  3486. if (!empty && push_items > 0) {
  3487. if (path->slots[0] < i)
  3488. break;
  3489. if (path->slots[0] == i) {
  3490. int space = btrfs_leaf_free_space(right);
  3491. if (space + push_space * 2 > free_space)
  3492. break;
  3493. }
  3494. }
  3495. if (path->slots[0] == i)
  3496. push_space += data_size;
  3497. this_item_size = btrfs_item_size(right, item);
  3498. if (this_item_size + sizeof(*item) + push_space > free_space)
  3499. break;
  3500. push_items++;
  3501. push_space += this_item_size + sizeof(*item);
  3502. }
  3503. if (push_items == 0) {
  3504. ret = 1;
  3505. goto out;
  3506. }
  3507. WARN_ON(!empty && push_items == btrfs_header_nritems(right));
  3508. /* push data from right to left */
  3509. copy_extent_buffer(left, right,
  3510. btrfs_item_nr_offset(btrfs_header_nritems(left)),
  3511. btrfs_item_nr_offset(0),
  3512. push_items * sizeof(struct btrfs_item));
  3513. push_space = BTRFS_LEAF_DATA_SIZE(fs_info) -
  3514. btrfs_item_offset_nr(right, push_items - 1);
  3515. copy_extent_buffer(left, right, BTRFS_LEAF_DATA_OFFSET +
  3516. leaf_data_end(left) - push_space,
  3517. BTRFS_LEAF_DATA_OFFSET +
  3518. btrfs_item_offset_nr(right, push_items - 1),
  3519. push_space);
  3520. old_left_nritems = btrfs_header_nritems(left);
  3521. BUG_ON(old_left_nritems <= 0);
  3522. btrfs_init_map_token(&token, left);
  3523. old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
  3524. for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
  3525. u32 ioff;
  3526. item = btrfs_item_nr(i);
  3527. ioff = btrfs_token_item_offset(&token, item);
  3528. btrfs_set_token_item_offset(&token, item,
  3529. ioff - (BTRFS_LEAF_DATA_SIZE(fs_info) - old_left_item_size));
  3530. }
  3531. btrfs_set_header_nritems(left, old_left_nritems + push_items);
  3532. /* fixup right node */
  3533. if (push_items > right_nritems)
  3534. WARN(1, KERN_CRIT "push items %d nr %u\n", push_items,
  3535. right_nritems);
  3536. if (push_items < right_nritems) {
  3537. push_space = btrfs_item_offset_nr(right, push_items - 1) -
  3538. leaf_data_end(right);
  3539. memmove_extent_buffer(right, BTRFS_LEAF_DATA_OFFSET +
  3540. BTRFS_LEAF_DATA_SIZE(fs_info) - push_space,
  3541. BTRFS_LEAF_DATA_OFFSET +
  3542. leaf_data_end(right), push_space);
  3543. memmove_extent_buffer(right, btrfs_item_nr_offset(0),
  3544. btrfs_item_nr_offset(push_items),
  3545. (btrfs_header_nritems(right) - push_items) *
  3546. sizeof(struct btrfs_item));
  3547. }
  3548. btrfs_init_map_token(&token, right);
  3549. right_nritems -= push_items;
  3550. btrfs_set_header_nritems(right, right_nritems);
  3551. push_space = BTRFS_LEAF_DATA_SIZE(fs_info);
  3552. for (i = 0; i < right_nritems; i++) {
  3553. item = btrfs_item_nr(i);
  3554. push_space = push_space - btrfs_token_item_size(&token, item);
  3555. btrfs_set_token_item_offset(&token, item, push_space);
  3556. }
  3557. btrfs_mark_buffer_dirty(left);
  3558. if (right_nritems)
  3559. btrfs_mark_buffer_dirty(right);
  3560. else
  3561. btrfs_clean_tree_block(right);
  3562. btrfs_item_key(right, &disk_key, 0);
  3563. fixup_low_keys(path, &disk_key, 1);
  3564. /* then fixup the leaf pointer in the path */
  3565. if (path->slots[0] < push_items) {
  3566. path->slots[0] += old_left_nritems;
  3567. btrfs_tree_unlock(path->nodes[0]);
  3568. free_extent_buffer(path->nodes[0]);
  3569. path->nodes[0] = left;
  3570. path->slots[1] -= 1;
  3571. } else {
  3572. btrfs_tree_unlock(left);
  3573. free_extent_buffer(left);
  3574. path->slots[0] -= push_items;
  3575. }
  3576. BUG_ON(path->slots[0] < 0);
  3577. return ret;
  3578. out:
  3579. btrfs_tree_unlock(left);
  3580. free_extent_buffer(left);
  3581. return ret;
  3582. }
  3583. /*
  3584. * push some data in the path leaf to the left, trying to free up at
  3585. * least data_size bytes. returns zero if the push worked, nonzero otherwise
  3586. *
  3587. * max_slot can put a limit on how far into the leaf we'll push items. The
  3588. * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the
  3589. * items
  3590. */
  3591. static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
  3592. *root, struct btrfs_path *path, int min_data_size,
  3593. int data_size, int empty, u32 max_slot)
  3594. {
  3595. struct extent_buffer *right = path->nodes[0];
  3596. struct extent_buffer *left;
  3597. int slot;
  3598. int free_space;
  3599. u32 right_nritems;
  3600. int ret = 0;
  3601. slot = path->slots[1];
  3602. if (slot == 0)
  3603. return 1;
  3604. if (!path->nodes[1])
  3605. return 1;
  3606. right_nritems = btrfs_header_nritems(right);
  3607. if (right_nritems == 0)
  3608. return 1;
  3609. btrfs_assert_tree_locked(path->nodes[1]);
  3610. left = btrfs_read_node_slot(path->nodes[1], slot - 1);
  3611. /*
  3612. * slot - 1 is not valid or we fail to read the left node,
  3613. * no big deal, just return.
  3614. */
  3615. if (IS_ERR(left))
  3616. return 1;
  3617. __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
  3618. btrfs_set_lock_blocking_write(left);
  3619. free_space = btrfs_leaf_free_space(left);
  3620. if (free_space < data_size) {
  3621. ret = 1;
  3622. goto out;
  3623. }
  3624. /* cow and double check */
  3625. ret = btrfs_cow_block(trans, root, left,
  3626. path->nodes[1], slot - 1, &left,
  3627. BTRFS_NESTING_LEFT_COW);
  3628. if (ret) {
  3629. /* we hit -ENOSPC, but it isn't fatal here */
  3630. if (ret == -ENOSPC)
  3631. ret = 1;
  3632. goto out;
  3633. }
  3634. free_space = btrfs_leaf_free_space(left);
  3635. if (free_space < data_size) {
  3636. ret = 1;
  3637. goto out;
  3638. }
  3639. if (check_sibling_keys(left, right)) {
  3640. ret = -EUCLEAN;
  3641. goto out;
  3642. }
  3643. return __push_leaf_left(path, min_data_size,
  3644. empty, left, free_space, right_nritems,
  3645. max_slot);
  3646. out:
  3647. btrfs_tree_unlock(left);
  3648. free_extent_buffer(left);
  3649. return ret;
  3650. }
  3651. /*
  3652. * split the path's leaf in two, making sure there is at least data_size
  3653. * available for the resulting leaf level of the path.
  3654. */
  3655. static noinline void copy_for_split(struct btrfs_trans_handle *trans,
  3656. struct btrfs_path *path,
  3657. struct extent_buffer *l,
  3658. struct extent_buffer *right,
  3659. int slot, int mid, int nritems)
  3660. {
  3661. struct btrfs_fs_info *fs_info = trans->fs_info;
  3662. int data_copy_size;
  3663. int rt_data_off;
  3664. int i;
  3665. struct btrfs_disk_key disk_key;
  3666. struct btrfs_map_token token;
  3667. nritems = nritems - mid;
  3668. btrfs_set_header_nritems(right, nritems);
  3669. data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(l);
  3670. copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
  3671. btrfs_item_nr_offset(mid),
  3672. nritems * sizeof(struct btrfs_item));
  3673. copy_extent_buffer(right, l,
  3674. BTRFS_LEAF_DATA_OFFSET + BTRFS_LEAF_DATA_SIZE(fs_info) -
  3675. data_copy_size, BTRFS_LEAF_DATA_OFFSET +
  3676. leaf_data_end(l), data_copy_size);
  3677. rt_data_off = BTRFS_LEAF_DATA_SIZE(fs_info) - btrfs_item_end_nr(l, mid);
  3678. btrfs_init_map_token(&token, right);
  3679. for (i = 0; i < nritems; i++) {
  3680. struct btrfs_item *item = btrfs_item_nr(i);
  3681. u32 ioff;
  3682. ioff = btrfs_token_item_offset(&token, item);
  3683. btrfs_set_token_item_offset(&token, item, ioff + rt_data_off);
  3684. }
  3685. btrfs_set_header_nritems(l, mid);
  3686. btrfs_item_key(right, &disk_key, 0);
  3687. insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1);
  3688. btrfs_mark_buffer_dirty(right);
  3689. btrfs_mark_buffer_dirty(l);
  3690. BUG_ON(path->slots[0] != slot);
  3691. if (mid <= slot) {
  3692. btrfs_tree_unlock(path->nodes[0]);
  3693. free_extent_buffer(path->nodes[0]);
  3694. path->nodes[0] = right;
  3695. path->slots[0] -= mid;
  3696. path->slots[1] += 1;
  3697. } else {
  3698. btrfs_tree_unlock(right);
  3699. free_extent_buffer(right);
  3700. }
  3701. BUG_ON(path->slots[0] < 0);
  3702. }
  3703. /*
  3704. * double splits happen when we need to insert a big item in the middle
  3705. * of a leaf. A double split can leave us with 3 mostly empty leaves:
  3706. * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
  3707. * A B C
  3708. *
  3709. * We avoid this by trying to push the items on either side of our target
  3710. * into the adjacent leaves. If all goes well we can avoid the double split
  3711. * completely.
  3712. */
  3713. static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
  3714. struct btrfs_root *root,
  3715. struct btrfs_path *path,
  3716. int data_size)
  3717. {
  3718. int ret;
  3719. int progress = 0;
  3720. int slot;
  3721. u32 nritems;
  3722. int space_needed = data_size;
  3723. slot = path->slots[0];
  3724. if (slot < btrfs_header_nritems(path->nodes[0]))
  3725. space_needed -= btrfs_leaf_free_space(path->nodes[0]);
  3726. /*
  3727. * try to push all the items after our slot into the
  3728. * right leaf
  3729. */
  3730. ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot);
  3731. if (ret < 0)
  3732. return ret;
  3733. if (ret == 0)
  3734. progress++;
  3735. nritems = btrfs_header_nritems(path->nodes[0]);
  3736. /*
  3737. * our goal is to get our slot at the start or end of a leaf. If
  3738. * we've done so we're done
  3739. */
  3740. if (path->slots[0] == 0 || path->slots[0] == nritems)
  3741. return 0;
  3742. if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
  3743. return 0;
  3744. /* try to push all the items before our slot into the next leaf */
  3745. slot = path->slots[0];
  3746. space_needed = data_size;
  3747. if (slot > 0)
  3748. space_needed -= btrfs_leaf_free_space(path->nodes[0]);
  3749. ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
  3750. if (ret < 0)
  3751. return ret;
  3752. if (ret == 0)
  3753. progress++;
  3754. if (progress)
  3755. return 0;
  3756. return 1;
  3757. }
  3758. /*
  3759. * split the path's leaf in two, making sure there is at least data_size
  3760. * available for the resulting leaf level of the path.
  3761. *
  3762. * returns 0 if all went well and < 0 on failure.
  3763. */
  3764. static noinline int split_leaf(struct btrfs_trans_handle *trans,
  3765. struct btrfs_root *root,
  3766. const struct btrfs_key *ins_key,
  3767. struct btrfs_path *path, int data_size,
  3768. int extend)
  3769. {
  3770. struct btrfs_disk_key disk_key;
  3771. struct extent_buffer *l;
  3772. u32 nritems;
  3773. int mid;
  3774. int slot;
  3775. struct extent_buffer *right;
  3776. struct btrfs_fs_info *fs_info = root->fs_info;
  3777. int ret = 0;
  3778. int wret;
  3779. int split;
  3780. int num_doubles = 0;
  3781. int tried_avoid_double = 0;
  3782. l = path->nodes[0];
  3783. slot = path->slots[0];
  3784. if (extend && data_size + btrfs_item_size_nr(l, slot) +
  3785. sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(fs_info))
  3786. return -EOVERFLOW;
  3787. /* first try to make some room by pushing left and right */
  3788. if (data_size && path->nodes[1]) {
  3789. int space_needed = data_size;
  3790. if (slot < btrfs_header_nritems(l))
  3791. space_needed -= btrfs_leaf_free_space(l);
  3792. wret = push_leaf_right(trans, root, path, space_needed,
  3793. space_needed, 0, 0);
  3794. if (wret < 0)
  3795. return wret;
  3796. if (wret) {
  3797. space_needed = data_size;
  3798. if (slot > 0)
  3799. space_needed -= btrfs_leaf_free_space(l);
  3800. wret = push_leaf_left(trans, root, path, space_needed,
  3801. space_needed, 0, (u32)-1);
  3802. if (wret < 0)
  3803. return wret;
  3804. }
  3805. l = path->nodes[0];
  3806. /* did the pushes work? */
  3807. if (btrfs_leaf_free_space(l) >= data_size)
  3808. return 0;
  3809. }
  3810. if (!path->nodes[1]) {
  3811. ret = insert_new_root(trans, root, path, 1);
  3812. if (ret)
  3813. return ret;
  3814. }
  3815. again:
  3816. split = 1;
  3817. l = path->nodes[0];
  3818. slot = path->slots[0];
  3819. nritems = btrfs_header_nritems(l);
  3820. mid = (nritems + 1) / 2;
  3821. if (mid <= slot) {
  3822. if (nritems == 1 ||
  3823. leaf_space_used(l, mid, nritems - mid) + data_size >
  3824. BTRFS_LEAF_DATA_SIZE(fs_info)) {
  3825. if (slot >= nritems) {
  3826. split = 0;
  3827. } else {
  3828. mid = slot;
  3829. if (mid != nritems &&
  3830. leaf_space_used(l, mid, nritems - mid) +
  3831. data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) {
  3832. if (data_size && !tried_avoid_double)
  3833. goto push_for_double;
  3834. split = 2;
  3835. }
  3836. }
  3837. }
  3838. } else {
  3839. if (leaf_space_used(l, 0, mid) + data_size >
  3840. BTRFS_LEAF_DATA_SIZE(fs_info)) {
  3841. if (!extend && data_size && slot == 0) {
  3842. split = 0;
  3843. } else if ((extend || !data_size) && slot == 0) {
  3844. mid = 1;
  3845. } else {
  3846. mid = slot;
  3847. if (mid != nritems &&
  3848. leaf_space_used(l, mid, nritems - mid) +
  3849. data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) {
  3850. if (data_size && !tried_avoid_double)
  3851. goto push_for_double;
  3852. split = 2;
  3853. }
  3854. }
  3855. }
  3856. }
  3857. if (split == 0)
  3858. btrfs_cpu_key_to_disk(&disk_key, ins_key);
  3859. else
  3860. btrfs_item_key(l, &disk_key, mid);
  3861. /*
  3862. * We have to about BTRFS_NESTING_NEW_ROOT here if we've done a double
  3863. * split, because we're only allowed to have MAX_LOCKDEP_SUBCLASSES
  3864. * subclasses, which is 8 at the time of this patch, and we've maxed it
  3865. * out. In the future we could add a
  3866. * BTRFS_NESTING_SPLIT_THE_SPLITTENING if we need to, but for now just
  3867. * use BTRFS_NESTING_NEW_ROOT.
  3868. */
  3869. right = alloc_tree_block_no_bg_flush(trans, root, 0, &disk_key, 0,
  3870. l->start, 0, num_doubles ?
  3871. BTRFS_NESTING_NEW_ROOT :
  3872. BTRFS_NESTING_SPLIT);
  3873. if (IS_ERR(right))
  3874. return PTR_ERR(right);
  3875. root_add_used(root, fs_info->nodesize);
  3876. if (split == 0) {
  3877. if (mid <= slot) {
  3878. btrfs_set_header_nritems(right, 0);
  3879. insert_ptr(trans, path, &disk_key,
  3880. right->start, path->slots[1] + 1, 1);
  3881. btrfs_tree_unlock(path->nodes[0]);
  3882. free_extent_buffer(path->nodes[0]);
  3883. path->nodes[0] = right;
  3884. path->slots[0] = 0;
  3885. path->slots[1] += 1;
  3886. } else {
  3887. btrfs_set_header_nritems(right, 0);
  3888. insert_ptr(trans, path, &disk_key,
  3889. right->start, path->slots[1], 1);
  3890. btrfs_tree_unlock(path->nodes[0]);
  3891. free_extent_buffer(path->nodes[0]);
  3892. path->nodes[0] = right;
  3893. path->slots[0] = 0;
  3894. if (path->slots[1] == 0)
  3895. fixup_low_keys(path, &disk_key, 1);
  3896. }
  3897. /*
  3898. * We create a new leaf 'right' for the required ins_len and
  3899. * we'll do btrfs_mark_buffer_dirty() on this leaf after copying
  3900. * the content of ins_len to 'right'.
  3901. */
  3902. return ret;
  3903. }
  3904. copy_for_split(trans, path, l, right, slot, mid, nritems);
  3905. if (split == 2) {
  3906. BUG_ON(num_doubles != 0);
  3907. num_doubles++;
  3908. goto again;
  3909. }
  3910. return 0;
  3911. push_for_double:
  3912. push_for_double_split(trans, root, path, data_size);
  3913. tried_avoid_double = 1;
  3914. if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
  3915. return 0;
  3916. goto again;
  3917. }
  3918. static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
  3919. struct btrfs_root *root,
  3920. struct btrfs_path *path, int ins_len)
  3921. {
  3922. struct btrfs_key key;
  3923. struct extent_buffer *leaf;
  3924. struct btrfs_file_extent_item *fi;
  3925. u64 extent_len = 0;
  3926. u32 item_size;
  3927. int ret;
  3928. leaf = path->nodes[0];
  3929. btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  3930. BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
  3931. key.type != BTRFS_EXTENT_CSUM_KEY);
  3932. if (btrfs_leaf_free_space(leaf) >= ins_len)
  3933. return 0;
  3934. item_size = btrfs_item_size_nr(leaf, path->slots[0]);
  3935. if (key.type == BTRFS_EXTENT_DATA_KEY) {
  3936. fi = btrfs_item_ptr(leaf, path->slots[0],
  3937. struct btrfs_file_extent_item);
  3938. extent_len = btrfs_file_extent_num_bytes(leaf, fi);
  3939. }
  3940. btrfs_release_path(path);
  3941. path->keep_locks = 1;
  3942. path->search_for_split = 1;
  3943. ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
  3944. path->search_for_split = 0;
  3945. if (ret > 0)
  3946. ret = -EAGAIN;
  3947. if (ret < 0)
  3948. goto err;
  3949. ret = -EAGAIN;
  3950. leaf = path->nodes[0];
  3951. /* if our item isn't there, return now */
  3952. if (item_size != btrfs_item_size_nr(leaf, path->slots[0]))
  3953. goto err;
  3954. /* the leaf has changed, it now has room. return now */
  3955. if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len)
  3956. goto err;
  3957. if (key.type == BTRFS_EXTENT_DATA_KEY) {
  3958. fi = btrfs_item_ptr(leaf, path->slots[0],
  3959. struct btrfs_file_extent_item);
  3960. if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
  3961. goto err;
  3962. }
  3963. btrfs_set_path_blocking(path);
  3964. ret = split_leaf(trans, root, &key, path, ins_len, 1);
  3965. if (ret)
  3966. goto err;
  3967. path->keep_locks = 0;
  3968. btrfs_unlock_up_safe(path, 1);
  3969. return 0;
  3970. err:
  3971. path->keep_locks = 0;
  3972. return ret;
  3973. }
  3974. static noinline int split_item(struct btrfs_path *path,
  3975. const struct btrfs_key *new_key,
  3976. unsigned long split_offset)
  3977. {
  3978. struct extent_buffer *leaf;
  3979. struct btrfs_item *item;
  3980. struct btrfs_item *new_item;
  3981. int slot;
  3982. char *buf;
  3983. u32 nritems;
  3984. u32 item_size;
  3985. u32 orig_offset;
  3986. struct btrfs_disk_key disk_key;
  3987. leaf = path->nodes[0];
  3988. BUG_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item));
  3989. btrfs_set_path_blocking(path);
  3990. item = btrfs_item_nr(path->slots[0]);
  3991. orig_offset = btrfs_item_offset(leaf, item);
  3992. item_size = btrfs_item_size(leaf, item);
  3993. buf = kmalloc(item_size, GFP_NOFS);
  3994. if (!buf)
  3995. return -ENOMEM;
  3996. read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
  3997. path->slots[0]), item_size);
  3998. slot = path->slots[0] + 1;
  3999. nritems = btrfs_header_nritems(leaf);
  4000. if (slot != nritems) {
  4001. /* shift the items */
  4002. memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
  4003. btrfs_item_nr_offset(slot),
  4004. (nritems - slot) * sizeof(struct btrfs_item));
  4005. }
  4006. btrfs_cpu_key_to_disk(&disk_key, new_key);
  4007. btrfs_set_item_key(leaf, &disk_key, slot);
  4008. new_item = btrfs_item_nr(slot);
  4009. btrfs_set_item_offset(leaf, new_item, orig_offset);
  4010. btrfs_set_item_size(leaf, new_item, item_size - split_offset);
  4011. btrfs_set_item_offset(leaf, item,
  4012. orig_offset + item_size - split_offset);
  4013. btrfs_set_item_size(leaf, item, split_offset);
  4014. btrfs_set_header_nritems(leaf, nritems + 1);
  4015. /* write the data for the start of the original item */
  4016. write_extent_buffer(leaf, buf,
  4017. btrfs_item_ptr_offset(leaf, path->slots[0]),
  4018. split_offset);
  4019. /* write the data for the new item */
  4020. write_extent_buffer(leaf, buf + split_offset,
  4021. btrfs_item_ptr_offset(leaf, slot),
  4022. item_size - split_offset);
  4023. btrfs_mark_buffer_dirty(leaf);
  4024. BUG_ON(btrfs_leaf_free_space(leaf) < 0);
  4025. kfree(buf);
  4026. return 0;
  4027. }
  4028. /*
  4029. * This function splits a single item into two items,
  4030. * giving 'new_key' to the new item and splitting the
  4031. * old one at split_offset (from the start of the item).
  4032. *
  4033. * The path may be released by this operation. After
  4034. * the split, the path is pointing to the old item. The
  4035. * new item is going to be in the same node as the old one.
  4036. *
  4037. * Note, the item being split must be smaller enough to live alone on
  4038. * a tree block with room for one extra struct btrfs_item
  4039. *
  4040. * This allows us to split the item in place, keeping a lock on the
  4041. * leaf the entire time.
  4042. */
  4043. int btrfs_split_item(struct btrfs_trans_handle *trans,
  4044. struct btrfs_root *root,
  4045. struct btrfs_path *path,
  4046. const struct btrfs_key *new_key,
  4047. unsigned long split_offset)
  4048. {
  4049. int ret;
  4050. ret = setup_leaf_for_split(trans, root, path,
  4051. sizeof(struct btrfs_item));
  4052. if (ret)
  4053. return ret;
  4054. ret = split_item(path, new_key, split_offset);
  4055. return ret;
  4056. }
  4057. /*
  4058. * This function duplicate a item, giving 'new_key' to the new item.
  4059. * It guarantees both items live in the same tree leaf and the new item
  4060. * is contiguous with the original item.
  4061. *
  4062. * This allows us to split file extent in place, keeping a lock on the
  4063. * leaf the entire time.
  4064. */
  4065. int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
  4066. struct btrfs_root *root,
  4067. struct btrfs_path *path,
  4068. const struct btrfs_key *new_key)
  4069. {
  4070. struct extent_buffer *leaf;
  4071. int ret;
  4072. u32 item_size;
  4073. leaf = path->nodes[0];
  4074. item_size = btrfs_item_size_nr(leaf, path->slots[0]);
  4075. ret = setup_leaf_for_split(trans, root, path,
  4076. item_size + sizeof(struct btrfs_item));
  4077. if (ret)
  4078. return ret;
  4079. path->slots[0]++;
  4080. setup_items_for_insert(root, path, new_key, &item_size, 1);
  4081. leaf = path->nodes[0];
  4082. memcpy_extent_buffer(leaf,
  4083. btrfs_item_ptr_offset(leaf, path->slots[0]),
  4084. btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
  4085. item_size);
  4086. return 0;
  4087. }
  4088. /*
  4089. * make the item pointed to by the path smaller. new_size indicates
  4090. * how small to make it, and from_end tells us if we just chop bytes
  4091. * off the end of the item or if we shift the item to chop bytes off
  4092. * the front.
  4093. */
  4094. void btrfs_truncate_item(struct btrfs_path *path, u32 new_size, int from_end)
  4095. {
  4096. int slot;
  4097. struct extent_buffer *leaf;
  4098. struct btrfs_item *item;
  4099. u32 nritems;
  4100. unsigned int data_end;
  4101. unsigned int old_data_start;
  4102. unsigned int old_size;
  4103. unsigned int size_diff;
  4104. int i;
  4105. struct btrfs_map_token token;
  4106. leaf = path->nodes[0];
  4107. slot = path->slots[0];
  4108. old_size = btrfs_item_size_nr(leaf, slot);
  4109. if (old_size == new_size)
  4110. return;
  4111. nritems = btrfs_header_nritems(leaf);
  4112. data_end = leaf_data_end(leaf);
  4113. old_data_start = btrfs_item_offset_nr(leaf, slot);
  4114. size_diff = old_size - new_size;
  4115. BUG_ON(slot < 0);
  4116. BUG_ON(slot >= nritems);
  4117. /*
  4118. * item0..itemN ... dataN.offset..dataN.size .. data0.size
  4119. */
  4120. /* first correct the data pointers */
  4121. btrfs_init_map_token(&token, leaf);
  4122. for (i = slot; i < nritems; i++) {
  4123. u32 ioff;
  4124. item = btrfs_item_nr(i);
  4125. ioff = btrfs_token_item_offset(&token, item);
  4126. btrfs_set_token_item_offset(&token, item, ioff + size_diff);
  4127. }
  4128. /* shift the data */
  4129. if (from_end) {
  4130. memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
  4131. data_end + size_diff, BTRFS_LEAF_DATA_OFFSET +
  4132. data_end, old_data_start + new_size - data_end);
  4133. } else {
  4134. struct btrfs_disk_key disk_key;
  4135. u64 offset;
  4136. btrfs_item_key(leaf, &disk_key, slot);
  4137. if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
  4138. unsigned long ptr;
  4139. struct btrfs_file_extent_item *fi;
  4140. fi = btrfs_item_ptr(leaf, slot,
  4141. struct btrfs_file_extent_item);
  4142. fi = (struct btrfs_file_extent_item *)(
  4143. (unsigned long)fi - size_diff);
  4144. if (btrfs_file_extent_type(leaf, fi) ==
  4145. BTRFS_FILE_EXTENT_INLINE) {
  4146. ptr = btrfs_item_ptr_offset(leaf, slot);
  4147. memmove_extent_buffer(leaf, ptr,
  4148. (unsigned long)fi,
  4149. BTRFS_FILE_EXTENT_INLINE_DATA_START);
  4150. }
  4151. }
  4152. memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
  4153. data_end + size_diff, BTRFS_LEAF_DATA_OFFSET +
  4154. data_end, old_data_start - data_end);
  4155. offset = btrfs_disk_key_offset(&disk_key);
  4156. btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
  4157. btrfs_set_item_key(leaf, &disk_key, slot);
  4158. if (slot == 0)
  4159. fixup_low_keys(path, &disk_key, 1);
  4160. }
  4161. item = btrfs_item_nr(slot);
  4162. btrfs_set_item_size(leaf, item, new_size);
  4163. btrfs_mark_buffer_dirty(leaf);
  4164. if (btrfs_leaf_free_space(leaf) < 0) {
  4165. btrfs_print_leaf(leaf);
  4166. BUG();
  4167. }
  4168. }
  4169. /*
  4170. * make the item pointed to by the path bigger, data_size is the added size.
  4171. */
  4172. void btrfs_extend_item(struct btrfs_path *path, u32 data_size)
  4173. {
  4174. int slot;
  4175. struct extent_buffer *leaf;
  4176. struct btrfs_item *item;
  4177. u32 nritems;
  4178. unsigned int data_end;
  4179. unsigned int old_data;
  4180. unsigned int old_size;
  4181. int i;
  4182. struct btrfs_map_token token;
  4183. leaf = path->nodes[0];
  4184. nritems = btrfs_header_nritems(leaf);
  4185. data_end = leaf_data_end(leaf);
  4186. if (btrfs_leaf_free_space(leaf) < data_size) {
  4187. btrfs_print_leaf(leaf);
  4188. BUG();
  4189. }
  4190. slot = path->slots[0];
  4191. old_data = btrfs_item_end_nr(leaf, slot);
  4192. BUG_ON(slot < 0);
  4193. if (slot >= nritems) {
  4194. btrfs_print_leaf(leaf);
  4195. btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d",
  4196. slot, nritems);
  4197. BUG();
  4198. }
  4199. /*
  4200. * item0..itemN ... dataN.offset..dataN.size .. data0.size
  4201. */
  4202. /* first correct the data pointers */
  4203. btrfs_init_map_token(&token, leaf);
  4204. for (i = slot; i < nritems; i++) {
  4205. u32 ioff;
  4206. item = btrfs_item_nr(i);
  4207. ioff = btrfs_token_item_offset(&token, item);
  4208. btrfs_set_token_item_offset(&token, item, ioff - data_size);
  4209. }
  4210. /* shift the data */
  4211. memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
  4212. data_end - data_size, BTRFS_LEAF_DATA_OFFSET +
  4213. data_end, old_data - data_end);
  4214. data_end = old_data;
  4215. old_size = btrfs_item_size_nr(leaf, slot);
  4216. item = btrfs_item_nr(slot);
  4217. btrfs_set_item_size(leaf, item, old_size + data_size);
  4218. btrfs_mark_buffer_dirty(leaf);
  4219. if (btrfs_leaf_free_space(leaf) < 0) {
  4220. btrfs_print_leaf(leaf);
  4221. BUG();
  4222. }
  4223. }
  4224. /**
  4225. * setup_items_for_insert - Helper called before inserting one or more items
  4226. * to a leaf. Main purpose is to save stack depth by doing the bulk of the work
  4227. * in a function that doesn't call btrfs_search_slot
  4228. *
  4229. * @root: root we are inserting items to
  4230. * @path: points to the leaf/slot where we are going to insert new items
  4231. * @cpu_key: array of keys for items to be inserted
  4232. * @data_size: size of the body of each item we are going to insert
  4233. * @nr: size of @cpu_key/@data_size arrays
  4234. */
  4235. void setup_items_for_insert(struct btrfs_root *root, struct btrfs_path *path,
  4236. const struct btrfs_key *cpu_key, u32 *data_size,
  4237. int nr)
  4238. {
  4239. struct btrfs_fs_info *fs_info = root->fs_info;
  4240. struct btrfs_item *item;
  4241. int i;
  4242. u32 nritems;
  4243. unsigned int data_end;
  4244. struct btrfs_disk_key disk_key;
  4245. struct extent_buffer *leaf;
  4246. int slot;
  4247. struct btrfs_map_token token;
  4248. u32 total_size;
  4249. u32 total_data = 0;
  4250. for (i = 0; i < nr; i++)
  4251. total_data += data_size[i];
  4252. total_size = total_data + (nr * sizeof(struct btrfs_item));
  4253. if (path->slots[0] == 0) {
  4254. btrfs_cpu_key_to_disk(&disk_key, cpu_key);
  4255. fixup_low_keys(path, &disk_key, 1);
  4256. }
  4257. btrfs_unlock_up_safe(path, 1);
  4258. leaf = path->nodes[0];
  4259. slot = path->slots[0];
  4260. nritems = btrfs_header_nritems(leaf);
  4261. data_end = leaf_data_end(leaf);
  4262. if (btrfs_leaf_free_space(leaf) < total_size) {
  4263. btrfs_print_leaf(leaf);
  4264. btrfs_crit(fs_info, "not enough freespace need %u have %d",
  4265. total_size, btrfs_leaf_free_space(leaf));
  4266. BUG();
  4267. }
  4268. btrfs_init_map_token(&token, leaf);
  4269. if (slot != nritems) {
  4270. unsigned int old_data = btrfs_item_end_nr(leaf, slot);
  4271. if (old_data < data_end) {
  4272. btrfs_print_leaf(leaf);
  4273. btrfs_crit(fs_info,
  4274. "item at slot %d with data offset %u beyond data end of leaf %u",
  4275. slot, old_data, data_end);
  4276. BUG();
  4277. }
  4278. /*
  4279. * item0..itemN ... dataN.offset..dataN.size .. data0.size
  4280. */
  4281. /* first correct the data pointers */
  4282. for (i = slot; i < nritems; i++) {
  4283. u32 ioff;
  4284. item = btrfs_item_nr(i);
  4285. ioff = btrfs_token_item_offset(&token, item);
  4286. btrfs_set_token_item_offset(&token, item,
  4287. ioff - total_data);
  4288. }
  4289. /* shift the items */
  4290. memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
  4291. btrfs_item_nr_offset(slot),
  4292. (nritems - slot) * sizeof(struct btrfs_item));
  4293. /* shift the data */
  4294. memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
  4295. data_end - total_data, BTRFS_LEAF_DATA_OFFSET +
  4296. data_end, old_data - data_end);
  4297. data_end = old_data;
  4298. }
  4299. /* setup the item for the new data */
  4300. for (i = 0; i < nr; i++) {
  4301. btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
  4302. btrfs_set_item_key(leaf, &disk_key, slot + i);
  4303. item = btrfs_item_nr(slot + i);
  4304. data_end -= data_size[i];
  4305. btrfs_set_token_item_offset(&token, item, data_end);
  4306. btrfs_set_token_item_size(&token, item, data_size[i]);
  4307. }
  4308. btrfs_set_header_nritems(leaf, nritems + nr);
  4309. btrfs_mark_buffer_dirty(leaf);
  4310. if (btrfs_leaf_free_space(leaf) < 0) {
  4311. btrfs_print_leaf(leaf);
  4312. BUG();
  4313. }
  4314. }
  4315. /*
  4316. * Given a key and some data, insert items into the tree.
  4317. * This does all the path init required, making room in the tree if needed.
  4318. */
  4319. int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
  4320. struct btrfs_root *root,
  4321. struct btrfs_path *path,
  4322. const struct btrfs_key *cpu_key, u32 *data_size,
  4323. int nr)
  4324. {
  4325. int ret = 0;
  4326. int slot;
  4327. int i;
  4328. u32 total_size = 0;
  4329. u32 total_data = 0;
  4330. for (i = 0; i < nr; i++)
  4331. total_data += data_size[i];
  4332. total_size = total_data + (nr * sizeof(struct btrfs_item));
  4333. ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
  4334. if (ret == 0)
  4335. return -EEXIST;
  4336. if (ret < 0)
  4337. return ret;
  4338. slot = path->slots[0];
  4339. BUG_ON(slot < 0);
  4340. setup_items_for_insert(root, path, cpu_key, data_size, nr);
  4341. return 0;
  4342. }
  4343. /*
  4344. * Given a key and some data, insert an item into the tree.
  4345. * This does all the path init required, making room in the tree if needed.
  4346. */
  4347. int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  4348. const struct btrfs_key *cpu_key, void *data,
  4349. u32 data_size)
  4350. {
  4351. int ret = 0;
  4352. struct btrfs_path *path;
  4353. struct extent_buffer *leaf;
  4354. unsigned long ptr;
  4355. path = btrfs_alloc_path();
  4356. if (!path)
  4357. return -ENOMEM;
  4358. ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
  4359. if (!ret) {
  4360. leaf = path->nodes[0];
  4361. ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
  4362. write_extent_buffer(leaf, data, ptr, data_size);
  4363. btrfs_mark_buffer_dirty(leaf);
  4364. }
  4365. btrfs_free_path(path);
  4366. return ret;
  4367. }
  4368. /*
  4369. * delete the pointer from a given node.
  4370. *
  4371. * the tree should have been previously balanced so the deletion does not
  4372. * empty a node.
  4373. */
  4374. static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
  4375. int level, int slot)
  4376. {
  4377. struct extent_buffer *parent = path->nodes[level];
  4378. u32 nritems;
  4379. int ret;
  4380. nritems = btrfs_header_nritems(parent);
  4381. if (slot != nritems - 1) {
  4382. if (level) {
  4383. ret = tree_mod_log_insert_move(parent, slot, slot + 1,
  4384. nritems - slot - 1);
  4385. BUG_ON(ret < 0);
  4386. }
  4387. memmove_extent_buffer(parent,
  4388. btrfs_node_key_ptr_offset(slot),
  4389. btrfs_node_key_ptr_offset(slot + 1),
  4390. sizeof(struct btrfs_key_ptr) *
  4391. (nritems - slot - 1));
  4392. } else if (level) {
  4393. ret = tree_mod_log_insert_key(parent, slot, MOD_LOG_KEY_REMOVE,
  4394. GFP_NOFS);
  4395. BUG_ON(ret < 0);
  4396. }
  4397. nritems--;
  4398. btrfs_set_header_nritems(parent, nritems);
  4399. if (nritems == 0 && parent == root->node) {
  4400. BUG_ON(btrfs_header_level(root->node) != 1);
  4401. /* just turn the root into a leaf and break */
  4402. btrfs_set_header_level(root->node, 0);
  4403. } else if (slot == 0) {
  4404. struct btrfs_disk_key disk_key;
  4405. btrfs_node_key(parent, &disk_key, 0);
  4406. fixup_low_keys(path, &disk_key, level + 1);
  4407. }
  4408. btrfs_mark_buffer_dirty(parent);
  4409. }
  4410. /*
  4411. * a helper function to delete the leaf pointed to by path->slots[1] and
  4412. * path->nodes[1].
  4413. *
  4414. * This deletes the pointer in path->nodes[1] and frees the leaf
  4415. * block extent. zero is returned if it all worked out, < 0 otherwise.
  4416. *
  4417. * The path must have already been setup for deleting the leaf, including
  4418. * all the proper balancing. path->nodes[1] must be locked.
  4419. */
  4420. static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans,
  4421. struct btrfs_root *root,
  4422. struct btrfs_path *path,
  4423. struct extent_buffer *leaf)
  4424. {
  4425. WARN_ON(btrfs_header_generation(leaf) != trans->transid);
  4426. del_ptr(root, path, 1, path->slots[1]);
  4427. /*
  4428. * btrfs_free_extent is expensive, we want to make sure we
  4429. * aren't holding any locks when we call it
  4430. */
  4431. btrfs_unlock_up_safe(path, 0);
  4432. root_sub_used(root, leaf->len);
  4433. atomic_inc(&leaf->refs);
  4434. btrfs_free_tree_block(trans, root, leaf, 0, 1);
  4435. free_extent_buffer_stale(leaf);
  4436. }
  4437. /*
  4438. * delete the item at the leaf level in path. If that empties
  4439. * the leaf, remove it from the tree
  4440. */
  4441. int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  4442. struct btrfs_path *path, int slot, int nr)
  4443. {
  4444. struct btrfs_fs_info *fs_info = root->fs_info;
  4445. struct extent_buffer *leaf;
  4446. struct btrfs_item *item;
  4447. u32 last_off;
  4448. u32 dsize = 0;
  4449. int ret = 0;
  4450. int wret;
  4451. int i;
  4452. u32 nritems;
  4453. leaf = path->nodes[0];
  4454. last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
  4455. for (i = 0; i < nr; i++)
  4456. dsize += btrfs_item_size_nr(leaf, slot + i);
  4457. nritems = btrfs_header_nritems(leaf);
  4458. if (slot + nr != nritems) {
  4459. int data_end = leaf_data_end(leaf);
  4460. struct btrfs_map_token token;
  4461. memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
  4462. data_end + dsize,
  4463. BTRFS_LEAF_DATA_OFFSET + data_end,
  4464. last_off - data_end);
  4465. btrfs_init_map_token(&token, leaf);
  4466. for (i = slot + nr; i < nritems; i++) {
  4467. u32 ioff;
  4468. item = btrfs_item_nr(i);
  4469. ioff = btrfs_token_item_offset(&token, item);
  4470. btrfs_set_token_item_offset(&token, item, ioff + dsize);
  4471. }
  4472. memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
  4473. btrfs_item_nr_offset(slot + nr),
  4474. sizeof(struct btrfs_item) *
  4475. (nritems - slot - nr));
  4476. }
  4477. btrfs_set_header_nritems(leaf, nritems - nr);
  4478. nritems -= nr;
  4479. /* delete the leaf if we've emptied it */
  4480. if (nritems == 0) {
  4481. if (leaf == root->node) {
  4482. btrfs_set_header_level(leaf, 0);
  4483. } else {
  4484. btrfs_set_path_blocking(path);
  4485. btrfs_clean_tree_block(leaf);
  4486. btrfs_del_leaf(trans, root, path, leaf);
  4487. }
  4488. } else {
  4489. int used = leaf_space_used(leaf, 0, nritems);
  4490. if (slot == 0) {
  4491. struct btrfs_disk_key disk_key;
  4492. btrfs_item_key(leaf, &disk_key, 0);
  4493. fixup_low_keys(path, &disk_key, 1);
  4494. }
  4495. /* delete the leaf if it is mostly empty */
  4496. if (used < BTRFS_LEAF_DATA_SIZE(fs_info) / 3) {
  4497. /* push_leaf_left fixes the path.
  4498. * make sure the path still points to our leaf
  4499. * for possible call to del_ptr below
  4500. */
  4501. slot = path->slots[1];
  4502. atomic_inc(&leaf->refs);
  4503. btrfs_set_path_blocking(path);
  4504. wret = push_leaf_left(trans, root, path, 1, 1,
  4505. 1, (u32)-1);
  4506. if (wret < 0 && wret != -ENOSPC)
  4507. ret = wret;
  4508. if (path->nodes[0] == leaf &&
  4509. btrfs_header_nritems(leaf)) {
  4510. wret = push_leaf_right(trans, root, path, 1,
  4511. 1, 1, 0);
  4512. if (wret < 0 && wret != -ENOSPC)
  4513. ret = wret;
  4514. }
  4515. if (btrfs_header_nritems(leaf) == 0) {
  4516. path->slots[1] = slot;
  4517. btrfs_del_leaf(trans, root, path, leaf);
  4518. free_extent_buffer(leaf);
  4519. ret = 0;
  4520. } else {
  4521. /* if we're still in the path, make sure
  4522. * we're dirty. Otherwise, one of the
  4523. * push_leaf functions must have already
  4524. * dirtied this buffer
  4525. */
  4526. if (path->nodes[0] == leaf)
  4527. btrfs_mark_buffer_dirty(leaf);
  4528. free_extent_buffer(leaf);
  4529. }
  4530. } else {
  4531. btrfs_mark_buffer_dirty(leaf);
  4532. }
  4533. }
  4534. return ret;
  4535. }
  4536. /*
  4537. * search the tree again to find a leaf with lesser keys
  4538. * returns 0 if it found something or 1 if there are no lesser leaves.
  4539. * returns < 0 on io errors.
  4540. *
  4541. * This may release the path, and so you may lose any locks held at the
  4542. * time you call it.
  4543. */
  4544. int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
  4545. {
  4546. struct btrfs_key key;
  4547. struct btrfs_disk_key found_key;
  4548. int ret;
  4549. btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
  4550. if (key.offset > 0) {
  4551. key.offset--;
  4552. } else if (key.type > 0) {
  4553. key.type--;
  4554. key.offset = (u64)-1;
  4555. } else if (key.objectid > 0) {
  4556. key.objectid--;
  4557. key.type = (u8)-1;
  4558. key.offset = (u64)-1;
  4559. } else {
  4560. return 1;
  4561. }
  4562. btrfs_release_path(path);
  4563. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  4564. if (ret < 0)
  4565. return ret;
  4566. btrfs_item_key(path->nodes[0], &found_key, 0);
  4567. ret = comp_keys(&found_key, &key);
  4568. /*
  4569. * We might have had an item with the previous key in the tree right
  4570. * before we released our path. And after we released our path, that
  4571. * item might have been pushed to the first slot (0) of the leaf we
  4572. * were holding due to a tree balance. Alternatively, an item with the
  4573. * previous key can exist as the only element of a leaf (big fat item).
  4574. * Therefore account for these 2 cases, so that our callers (like
  4575. * btrfs_previous_item) don't miss an existing item with a key matching
  4576. * the previous key we computed above.
  4577. */
  4578. if (ret <= 0)
  4579. return 0;
  4580. return 1;
  4581. }
  4582. /*
  4583. * A helper function to walk down the tree starting at min_key, and looking
  4584. * for nodes or leaves that are have a minimum transaction id.
  4585. * This is used by the btree defrag code, and tree logging
  4586. *
  4587. * This does not cow, but it does stuff the starting key it finds back
  4588. * into min_key, so you can call btrfs_search_slot with cow=1 on the
  4589. * key and get a writable path.
  4590. *
  4591. * This honors path->lowest_level to prevent descent past a given level
  4592. * of the tree.
  4593. *
  4594. * min_trans indicates the oldest transaction that you are interested
  4595. * in walking through. Any nodes or leaves older than min_trans are
  4596. * skipped over (without reading them).
  4597. *
  4598. * returns zero if something useful was found, < 0 on error and 1 if there
  4599. * was nothing in the tree that matched the search criteria.
  4600. */
  4601. int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
  4602. struct btrfs_path *path,
  4603. u64 min_trans)
  4604. {
  4605. struct extent_buffer *cur;
  4606. struct btrfs_key found_key;
  4607. int slot;
  4608. int sret;
  4609. u32 nritems;
  4610. int level;
  4611. int ret = 1;
  4612. int keep_locks = path->keep_locks;
  4613. path->keep_locks = 1;
  4614. again:
  4615. cur = btrfs_read_lock_root_node(root);
  4616. level = btrfs_header_level(cur);
  4617. WARN_ON(path->nodes[level]);
  4618. path->nodes[level] = cur;
  4619. path->locks[level] = BTRFS_READ_LOCK;
  4620. if (btrfs_header_generation(cur) < min_trans) {
  4621. ret = 1;
  4622. goto out;
  4623. }
  4624. while (1) {
  4625. nritems = btrfs_header_nritems(cur);
  4626. level = btrfs_header_level(cur);
  4627. sret = btrfs_bin_search(cur, min_key, &slot);
  4628. if (sret < 0) {
  4629. ret = sret;
  4630. goto out;
  4631. }
  4632. /* at the lowest level, we're done, setup the path and exit */
  4633. if (level == path->lowest_level) {
  4634. if (slot >= nritems)
  4635. goto find_next_key;
  4636. ret = 0;
  4637. path->slots[level] = slot;
  4638. btrfs_item_key_to_cpu(cur, &found_key, slot);
  4639. goto out;
  4640. }
  4641. if (sret && slot > 0)
  4642. slot--;
  4643. /*
  4644. * check this node pointer against the min_trans parameters.
  4645. * If it is too old, skip to the next one.
  4646. */
  4647. while (slot < nritems) {
  4648. u64 gen;
  4649. gen = btrfs_node_ptr_generation(cur, slot);
  4650. if (gen < min_trans) {
  4651. slot++;
  4652. continue;
  4653. }
  4654. break;
  4655. }
  4656. find_next_key:
  4657. /*
  4658. * we didn't find a candidate key in this node, walk forward
  4659. * and find another one
  4660. */
  4661. if (slot >= nritems) {
  4662. path->slots[level] = slot;
  4663. btrfs_set_path_blocking(path);
  4664. sret = btrfs_find_next_key(root, path, min_key, level,
  4665. min_trans);
  4666. if (sret == 0) {
  4667. btrfs_release_path(path);
  4668. goto again;
  4669. } else {
  4670. goto out;
  4671. }
  4672. }
  4673. /* save our key for returning back */
  4674. btrfs_node_key_to_cpu(cur, &found_key, slot);
  4675. path->slots[level] = slot;
  4676. if (level == path->lowest_level) {
  4677. ret = 0;
  4678. goto out;
  4679. }
  4680. btrfs_set_path_blocking(path);
  4681. cur = btrfs_read_node_slot(cur, slot);
  4682. if (IS_ERR(cur)) {
  4683. ret = PTR_ERR(cur);
  4684. goto out;
  4685. }
  4686. btrfs_tree_read_lock(cur);
  4687. path->locks[level - 1] = BTRFS_READ_LOCK;
  4688. path->nodes[level - 1] = cur;
  4689. unlock_up(path, level, 1, 0, NULL);
  4690. }
  4691. out:
  4692. path->keep_locks = keep_locks;
  4693. if (ret == 0) {
  4694. btrfs_unlock_up_safe(path, path->lowest_level + 1);
  4695. btrfs_set_path_blocking(path);
  4696. memcpy(min_key, &found_key, sizeof(found_key));
  4697. }
  4698. return ret;
  4699. }
  4700. /*
  4701. * this is similar to btrfs_next_leaf, but does not try to preserve
  4702. * and fixup the path. It looks for and returns the next key in the
  4703. * tree based on the current path and the min_trans parameters.
  4704. *
  4705. * 0 is returned if another key is found, < 0 if there are any errors
  4706. * and 1 is returned if there are no higher keys in the tree
  4707. *
  4708. * path->keep_locks should be set to 1 on the search made before
  4709. * calling this function.
  4710. */
  4711. int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
  4712. struct btrfs_key *key, int level, u64 min_trans)
  4713. {
  4714. int slot;
  4715. struct extent_buffer *c;
  4716. WARN_ON(!path->keep_locks && !path->skip_locking);
  4717. while (level < BTRFS_MAX_LEVEL) {
  4718. if (!path->nodes[level])
  4719. return 1;
  4720. slot = path->slots[level] + 1;
  4721. c = path->nodes[level];
  4722. next:
  4723. if (slot >= btrfs_header_nritems(c)) {
  4724. int ret;
  4725. int orig_lowest;
  4726. struct btrfs_key cur_key;
  4727. if (level + 1 >= BTRFS_MAX_LEVEL ||
  4728. !path->nodes[level + 1])
  4729. return 1;
  4730. if (path->locks[level + 1] || path->skip_locking) {
  4731. level++;
  4732. continue;
  4733. }
  4734. slot = btrfs_header_nritems(c) - 1;
  4735. if (level == 0)
  4736. btrfs_item_key_to_cpu(c, &cur_key, slot);
  4737. else
  4738. btrfs_node_key_to_cpu(c, &cur_key, slot);
  4739. orig_lowest = path->lowest_level;
  4740. btrfs_release_path(path);
  4741. path->lowest_level = level;
  4742. ret = btrfs_search_slot(NULL, root, &cur_key, path,
  4743. 0, 0);
  4744. path->lowest_level = orig_lowest;
  4745. if (ret < 0)
  4746. return ret;
  4747. c = path->nodes[level];
  4748. slot = path->slots[level];
  4749. if (ret == 0)
  4750. slot++;
  4751. goto next;
  4752. }
  4753. if (level == 0)
  4754. btrfs_item_key_to_cpu(c, key, slot);
  4755. else {
  4756. u64 gen = btrfs_node_ptr_generation(c, slot);
  4757. if (gen < min_trans) {
  4758. slot++;
  4759. goto next;
  4760. }
  4761. btrfs_node_key_to_cpu(c, key, slot);
  4762. }
  4763. return 0;
  4764. }
  4765. return 1;
  4766. }
  4767. /*
  4768. * search the tree again to find a leaf with greater keys
  4769. * returns 0 if it found something or 1 if there are no greater leaves.
  4770. * returns < 0 on io errors.
  4771. */
  4772. int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
  4773. {
  4774. return btrfs_next_old_leaf(root, path, 0);
  4775. }
  4776. int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
  4777. u64 time_seq)
  4778. {
  4779. int slot;
  4780. int level;
  4781. struct extent_buffer *c;
  4782. struct extent_buffer *next;
  4783. struct btrfs_key key;
  4784. u32 nritems;
  4785. int ret;
  4786. int old_spinning = path->leave_spinning;
  4787. int next_rw_lock = 0;
  4788. nritems = btrfs_header_nritems(path->nodes[0]);
  4789. if (nritems == 0)
  4790. return 1;
  4791. btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
  4792. again:
  4793. level = 1;
  4794. next = NULL;
  4795. next_rw_lock = 0;
  4796. btrfs_release_path(path);
  4797. path->keep_locks = 1;
  4798. path->leave_spinning = 1;
  4799. if (time_seq)
  4800. ret = btrfs_search_old_slot(root, &key, path, time_seq);
  4801. else
  4802. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  4803. path->keep_locks = 0;
  4804. if (ret < 0)
  4805. return ret;
  4806. nritems = btrfs_header_nritems(path->nodes[0]);
  4807. /*
  4808. * by releasing the path above we dropped all our locks. A balance
  4809. * could have added more items next to the key that used to be
  4810. * at the very end of the block. So, check again here and
  4811. * advance the path if there are now more items available.
  4812. */
  4813. if (nritems > 0 && path->slots[0] < nritems - 1) {
  4814. if (ret == 0)
  4815. path->slots[0]++;
  4816. ret = 0;
  4817. goto done;
  4818. }
  4819. /*
  4820. * So the above check misses one case:
  4821. * - after releasing the path above, someone has removed the item that
  4822. * used to be at the very end of the block, and balance between leafs
  4823. * gets another one with bigger key.offset to replace it.
  4824. *
  4825. * This one should be returned as well, or we can get leaf corruption
  4826. * later(esp. in __btrfs_drop_extents()).
  4827. *
  4828. * And a bit more explanation about this check,
  4829. * with ret > 0, the key isn't found, the path points to the slot
  4830. * where it should be inserted, so the path->slots[0] item must be the
  4831. * bigger one.
  4832. */
  4833. if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) {
  4834. ret = 0;
  4835. goto done;
  4836. }
  4837. while (level < BTRFS_MAX_LEVEL) {
  4838. if (!path->nodes[level]) {
  4839. ret = 1;
  4840. goto done;
  4841. }
  4842. slot = path->slots[level] + 1;
  4843. c = path->nodes[level];
  4844. if (slot >= btrfs_header_nritems(c)) {
  4845. level++;
  4846. if (level == BTRFS_MAX_LEVEL) {
  4847. ret = 1;
  4848. goto done;
  4849. }
  4850. continue;
  4851. }
  4852. if (next) {
  4853. btrfs_tree_unlock_rw(next, next_rw_lock);
  4854. free_extent_buffer(next);
  4855. }
  4856. next = c;
  4857. next_rw_lock = path->locks[level];
  4858. ret = read_block_for_search(root, path, &next, level,
  4859. slot, &key);
  4860. if (ret == -EAGAIN)
  4861. goto again;
  4862. if (ret < 0) {
  4863. btrfs_release_path(path);
  4864. goto done;
  4865. }
  4866. if (!path->skip_locking) {
  4867. ret = btrfs_try_tree_read_lock(next);
  4868. if (!ret && time_seq) {
  4869. /*
  4870. * If we don't get the lock, we may be racing
  4871. * with push_leaf_left, holding that lock while
  4872. * itself waiting for the leaf we've currently
  4873. * locked. To solve this situation, we give up
  4874. * on our lock and cycle.
  4875. */
  4876. free_extent_buffer(next);
  4877. btrfs_release_path(path);
  4878. cond_resched();
  4879. goto again;
  4880. }
  4881. if (!ret) {
  4882. btrfs_set_path_blocking(path);
  4883. __btrfs_tree_read_lock(next,
  4884. BTRFS_NESTING_RIGHT,
  4885. path->recurse);
  4886. }
  4887. next_rw_lock = BTRFS_READ_LOCK;
  4888. }
  4889. break;
  4890. }
  4891. path->slots[level] = slot;
  4892. while (1) {
  4893. level--;
  4894. c = path->nodes[level];
  4895. if (path->locks[level])
  4896. btrfs_tree_unlock_rw(c, path->locks[level]);
  4897. free_extent_buffer(c);
  4898. path->nodes[level] = next;
  4899. path->slots[level] = 0;
  4900. if (!path->skip_locking)
  4901. path->locks[level] = next_rw_lock;
  4902. if (!level)
  4903. break;
  4904. ret = read_block_for_search(root, path, &next, level,
  4905. 0, &key);
  4906. if (ret == -EAGAIN)
  4907. goto again;
  4908. if (ret < 0) {
  4909. btrfs_release_path(path);
  4910. goto done;
  4911. }
  4912. if (!path->skip_locking) {
  4913. ret = btrfs_try_tree_read_lock(next);
  4914. if (!ret) {
  4915. btrfs_set_path_blocking(path);
  4916. __btrfs_tree_read_lock(next,
  4917. BTRFS_NESTING_RIGHT,
  4918. path->recurse);
  4919. }
  4920. next_rw_lock = BTRFS_READ_LOCK;
  4921. }
  4922. }
  4923. ret = 0;
  4924. done:
  4925. unlock_up(path, 0, 1, 0, NULL);
  4926. path->leave_spinning = old_spinning;
  4927. if (!old_spinning)
  4928. btrfs_set_path_blocking(path);
  4929. return ret;
  4930. }
  4931. /*
  4932. * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
  4933. * searching until it gets past min_objectid or finds an item of 'type'
  4934. *
  4935. * returns 0 if something is found, 1 if nothing was found and < 0 on error
  4936. */
  4937. int btrfs_previous_item(struct btrfs_root *root,
  4938. struct btrfs_path *path, u64 min_objectid,
  4939. int type)
  4940. {
  4941. struct btrfs_key found_key;
  4942. struct extent_buffer *leaf;
  4943. u32 nritems;
  4944. int ret;
  4945. while (1) {
  4946. if (path->slots[0] == 0) {
  4947. btrfs_set_path_blocking(path);
  4948. ret = btrfs_prev_leaf(root, path);
  4949. if (ret != 0)
  4950. return ret;
  4951. } else {
  4952. path->slots[0]--;
  4953. }
  4954. leaf = path->nodes[0];
  4955. nritems = btrfs_header_nritems(leaf);
  4956. if (nritems == 0)
  4957. return 1;
  4958. if (path->slots[0] == nritems)
  4959. path->slots[0]--;
  4960. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  4961. if (found_key.objectid < min_objectid)
  4962. break;
  4963. if (found_key.type == type)
  4964. return 0;
  4965. if (found_key.objectid == min_objectid &&
  4966. found_key.type < type)
  4967. break;
  4968. }
  4969. return 1;
  4970. }
  4971. /*
  4972. * search in extent tree to find a previous Metadata/Data extent item with
  4973. * min objecitd.
  4974. *
  4975. * returns 0 if something is found, 1 if nothing was found and < 0 on error
  4976. */
  4977. int btrfs_previous_extent_item(struct btrfs_root *root,
  4978. struct btrfs_path *path, u64 min_objectid)
  4979. {
  4980. struct btrfs_key found_key;
  4981. struct extent_buffer *leaf;
  4982. u32 nritems;
  4983. int ret;
  4984. while (1) {
  4985. if (path->slots[0] == 0) {
  4986. btrfs_set_path_blocking(path);
  4987. ret = btrfs_prev_leaf(root, path);
  4988. if (ret != 0)
  4989. return ret;
  4990. } else {
  4991. path->slots[0]--;
  4992. }
  4993. leaf = path->nodes[0];
  4994. nritems = btrfs_header_nritems(leaf);
  4995. if (nritems == 0)
  4996. return 1;
  4997. if (path->slots[0] == nritems)
  4998. path->slots[0]--;
  4999. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  5000. if (found_key.objectid < min_objectid)
  5001. break;
  5002. if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
  5003. found_key.type == BTRFS_METADATA_ITEM_KEY)
  5004. return 0;
  5005. if (found_key.objectid == min_objectid &&
  5006. found_key.type < BTRFS_EXTENT_ITEM_KEY)
  5007. break;
  5008. }
  5009. return 1;
  5010. }