ctree.c 150 KB

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