extent-tree.c 135 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385338633873388338933903391339233933394339533963397339833993400340134023403340434053406340734083409341034113412341334143415341634173418341934203421342234233424342534263427342834293430343134323433343434353436343734383439344034413442344334443445344634473448344934503451345234533454345534563457345834593460346134623463346434653466346734683469347034713472347334743475347634773478347934803481348234833484348534863487348834893490349134923493349434953496349734983499350035013502350335043505350635073508350935103511351235133514351535163517351835193520352135223523352435253526352735283529353035313532353335343535353635373538353935403541354235433544354535463547354835493550355135523553355435553556355735583559356035613562356335643565356635673568356935703571357235733574357535763577357835793580358135823583358435853586358735883589359035913592359335943595359635973598359936003601360236033604360536063607360836093610361136123613361436153616361736183619362036213622362336243625362636273628362936303631363236333634363536363637363836393640364136423643364436453646364736483649365036513652365336543655365636573658365936603661366236633664366536663667366836693670367136723673367436753676367736783679368036813682368336843685368636873688368936903691369236933694369536963697369836993700370137023703370437053706370737083709371037113712371337143715371637173718371937203721372237233724372537263727372837293730373137323733373437353736373737383739374037413742374337443745374637473748374937503751375237533754375537563757375837593760376137623763376437653766376737683769377037713772377337743775377637773778377937803781378237833784378537863787378837893790379137923793379437953796379737983799380038013802380338043805380638073808380938103811381238133814381538163817381838193820382138223823382438253826382738283829383038313832383338343835383638373838383938403841384238433844384538463847384838493850385138523853385438553856385738583859386038613862386338643865386638673868386938703871387238733874387538763877387838793880388138823883388438853886388738883889389038913892389338943895389638973898389939003901390239033904390539063907390839093910391139123913391439153916391739183919392039213922392339243925392639273928392939303931393239333934393539363937393839393940394139423943394439453946394739483949395039513952395339543955395639573958395939603961396239633964396539663967396839693970397139723973397439753976397739783979398039813982398339843985398639873988398939903991399239933994399539963997399839994000400140024003400440054006400740084009401040114012401340144015401640174018401940204021402240234024402540264027402840294030403140324033403440354036403740384039404040414042404340444045404640474048404940504051405240534054405540564057405840594060406140624063406440654066406740684069407040714072407340744075407640774078407940804081408240834084408540864087408840894090409140924093409440954096409740984099410041014102410341044105410641074108410941104111411241134114411541164117411841194120412141224123412441254126412741284129413041314132413341344135413641374138413941404141414241434144414541464147414841494150415141524153415441554156415741584159416041614162416341644165416641674168416941704171417241734174417541764177417841794180418141824183418441854186418741884189419041914192419341944195419641974198419942004201420242034204420542064207420842094210421142124213421442154216421742184219422042214222422342244225422642274228422942304231423242334234423542364237423842394240424142424243424442454246424742484249425042514252425342544255425642574258425942604261426242634264426542664267426842694270427142724273427442754276427742784279428042814282428342844285428642874288428942904291429242934294429542964297429842994300430143024303430443054306430743084309431043114312431343144315431643174318431943204321432243234324432543264327432843294330433143324333433443354336433743384339434043414342434343444345434643474348434943504351435243534354435543564357435843594360436143624363436443654366436743684369437043714372437343744375437643774378437943804381438243834384438543864387438843894390439143924393439443954396439743984399440044014402440344044405440644074408440944104411441244134414441544164417441844194420442144224423442444254426442744284429443044314432443344344435443644374438443944404441444244434444444544464447444844494450445144524453445444554456445744584459446044614462446344644465446644674468446944704471447244734474447544764477447844794480448144824483448444854486448744884489449044914492449344944495449644974498449945004501450245034504450545064507450845094510451145124513451445154516451745184519452045214522452345244525452645274528452945304531453245334534453545364537453845394540454145424543454445454546454745484549455045514552455345544555455645574558455945604561456245634564456545664567456845694570457145724573457445754576457745784579458045814582458345844585458645874588458945904591459245934594459545964597459845994600460146024603460446054606460746084609461046114612461346144615461646174618461946204621462246234624462546264627462846294630463146324633463446354636463746384639464046414642464346444645464646474648464946504651465246534654465546564657465846594660466146624663466446654666466746684669467046714672467346744675467646774678467946804681468246834684468546864687468846894690469146924693469446954696469746984699470047014702470347044705470647074708470947104711471247134714471547164717471847194720472147224723472447254726472747284729473047314732473347344735473647374738473947404741474247434744474547464747474847494750475147524753475447554756475747584759476047614762476347644765476647674768476947704771477247734774477547764777477847794780478147824783478447854786478747884789479047914792479347944795479647974798479948004801480248034804480548064807480848094810481148124813481448154816481748184819482048214822482348244825482648274828482948304831483248334834483548364837483848394840484148424843484448454846484748484849485048514852485348544855485648574858485948604861486248634864486548664867486848694870487148724873487448754876487748784879488048814882488348844885488648874888488948904891489248934894489548964897489848994900490149024903490449054906490749084909491049114912491349144915491649174918491949204921492249234924492549264927492849294930493149324933493449354936493749384939494049414942494349444945494649474948494949504951495249534954495549564957495849594960496149624963496449654966496749684969497049714972497349744975497649774978497949804981498249834984498549864987498849894990499149924993499449954996499749984999500050015002500350045005500650075008500950105011501250135014501550165017501850195020502150225023502450255026502750285029503050315032503350345035503650375038503950405041504250435044504550465047504850495050505150525053505450555056505750585059506050615062506350645065506650675068506950705071507250735074507550765077507850795080508150825083508450855086508750885089509050915092509350945095509650975098509951005101510251035104510551065107510851095110511151125113511451155116511751185119512051215122512351245125512651275128512951305131513251335134513551365137513851395140514151425143514451455146514751485149515051515152515351545155515651575158515951605161516251635164516551665167516851695170517151725173517451755176517751785179518051815182518351845185518651875188518951905191519251935194519551965197519851995200520152025203520452055206520752085209521052115212521352145215521652175218521952205221522252235224522552265227522852295230523152325233523452355236523752385239524052415242524352445245524652475248524952505251525252535254525552565257
  1. /*
  2. * Copyright (C) 2007 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/pagemap.h>
  20. #include <linux/writeback.h>
  21. #include <linux/blkdev.h>
  22. #include "hash.h"
  23. #include "crc32c.h"
  24. #include "ctree.h"
  25. #include "disk-io.h"
  26. #include "print-tree.h"
  27. #include "transaction.h"
  28. #include "volumes.h"
  29. #include "locking.h"
  30. #include "ref-cache.h"
  31. #define PENDING_EXTENT_INSERT 0
  32. #define PENDING_EXTENT_DELETE 1
  33. #define PENDING_BACKREF_UPDATE 2
  34. struct pending_extent_op {
  35. int type;
  36. u64 bytenr;
  37. u64 num_bytes;
  38. u64 parent;
  39. u64 orig_parent;
  40. u64 generation;
  41. u64 orig_generation;
  42. int level;
  43. };
  44. static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  45. btrfs_root *extent_root, int all);
  46. static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  47. btrfs_root *extent_root, int all);
  48. static struct btrfs_block_group_cache *
  49. __btrfs_find_block_group(struct btrfs_root *root,
  50. struct btrfs_block_group_cache *hint,
  51. u64 search_start, int data, int owner);
  52. static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
  53. {
  54. return (cache->flags & bits) == bits;
  55. }
  56. /*
  57. * this adds the block group to the fs_info rb tree for the block group
  58. * cache
  59. */
  60. int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
  61. struct btrfs_block_group_cache *block_group)
  62. {
  63. struct rb_node **p;
  64. struct rb_node *parent = NULL;
  65. struct btrfs_block_group_cache *cache;
  66. spin_lock(&info->block_group_cache_lock);
  67. p = &info->block_group_cache_tree.rb_node;
  68. while (*p) {
  69. parent = *p;
  70. cache = rb_entry(parent, struct btrfs_block_group_cache,
  71. cache_node);
  72. if (block_group->key.objectid < cache->key.objectid) {
  73. p = &(*p)->rb_left;
  74. } else if (block_group->key.objectid > cache->key.objectid) {
  75. p = &(*p)->rb_right;
  76. } else {
  77. spin_unlock(&info->block_group_cache_lock);
  78. return -EEXIST;
  79. }
  80. }
  81. rb_link_node(&block_group->cache_node, parent, p);
  82. rb_insert_color(&block_group->cache_node,
  83. &info->block_group_cache_tree);
  84. spin_unlock(&info->block_group_cache_lock);
  85. return 0;
  86. }
  87. /*
  88. * This will return the block group at or after bytenr if contains is 0, else
  89. * it will return the block group that contains the bytenr
  90. */
  91. static struct btrfs_block_group_cache *
  92. block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
  93. int contains)
  94. {
  95. struct btrfs_block_group_cache *cache, *ret = NULL;
  96. struct rb_node *n;
  97. u64 end, start;
  98. spin_lock(&info->block_group_cache_lock);
  99. n = info->block_group_cache_tree.rb_node;
  100. while (n) {
  101. cache = rb_entry(n, struct btrfs_block_group_cache,
  102. cache_node);
  103. end = cache->key.objectid + cache->key.offset - 1;
  104. start = cache->key.objectid;
  105. if (bytenr < start) {
  106. if (!contains && (!ret || start < ret->key.objectid))
  107. ret = cache;
  108. n = n->rb_left;
  109. } else if (bytenr > start) {
  110. if (contains && bytenr <= end) {
  111. ret = cache;
  112. break;
  113. }
  114. n = n->rb_right;
  115. } else {
  116. ret = cache;
  117. break;
  118. }
  119. }
  120. spin_unlock(&info->block_group_cache_lock);
  121. return ret;
  122. }
  123. /*
  124. * this is only called by cache_block_group, since we could have freed extents
  125. * we need to check the pinned_extents for any extents that can't be used yet
  126. * since their free space will be released as soon as the transaction commits.
  127. */
  128. static int add_new_free_space(struct btrfs_block_group_cache *block_group,
  129. struct btrfs_fs_info *info, u64 start, u64 end)
  130. {
  131. u64 extent_start, extent_end, size;
  132. int ret;
  133. mutex_lock(&info->pinned_mutex);
  134. while (start < end) {
  135. ret = find_first_extent_bit(&info->pinned_extents, start,
  136. &extent_start, &extent_end,
  137. EXTENT_DIRTY);
  138. if (ret)
  139. break;
  140. if (extent_start == start) {
  141. start = extent_end + 1;
  142. } else if (extent_start > start && extent_start < end) {
  143. size = extent_start - start;
  144. ret = btrfs_add_free_space_lock(block_group, start,
  145. size);
  146. BUG_ON(ret);
  147. start = extent_end + 1;
  148. } else {
  149. break;
  150. }
  151. }
  152. if (start < end) {
  153. size = end - start;
  154. ret = btrfs_add_free_space_lock(block_group, start, size);
  155. BUG_ON(ret);
  156. }
  157. mutex_unlock(&info->pinned_mutex);
  158. return 0;
  159. }
  160. static int cache_block_group(struct btrfs_root *root,
  161. struct btrfs_block_group_cache *block_group)
  162. {
  163. struct btrfs_path *path;
  164. int ret = 0;
  165. struct btrfs_key key;
  166. struct extent_buffer *leaf;
  167. int slot;
  168. u64 last = 0;
  169. u64 first_free;
  170. int found = 0;
  171. if (!block_group)
  172. return 0;
  173. root = root->fs_info->extent_root;
  174. if (block_group->cached)
  175. return 0;
  176. path = btrfs_alloc_path();
  177. if (!path)
  178. return -ENOMEM;
  179. path->reada = 2;
  180. /*
  181. * we get into deadlocks with paths held by callers of this function.
  182. * since the alloc_mutex is protecting things right now, just
  183. * skip the locking here
  184. */
  185. path->skip_locking = 1;
  186. first_free = max_t(u64, block_group->key.objectid,
  187. BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
  188. key.objectid = block_group->key.objectid;
  189. key.offset = 0;
  190. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  191. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  192. if (ret < 0)
  193. goto err;
  194. ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
  195. if (ret < 0)
  196. goto err;
  197. if (ret == 0) {
  198. leaf = path->nodes[0];
  199. btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  200. if (key.objectid + key.offset > first_free)
  201. first_free = key.objectid + key.offset;
  202. }
  203. while(1) {
  204. leaf = path->nodes[0];
  205. slot = path->slots[0];
  206. if (slot >= btrfs_header_nritems(leaf)) {
  207. ret = btrfs_next_leaf(root, path);
  208. if (ret < 0)
  209. goto err;
  210. if (ret == 0)
  211. continue;
  212. else
  213. break;
  214. }
  215. btrfs_item_key_to_cpu(leaf, &key, slot);
  216. if (key.objectid < block_group->key.objectid)
  217. goto next;
  218. if (key.objectid >= block_group->key.objectid +
  219. block_group->key.offset)
  220. break;
  221. if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
  222. if (!found) {
  223. last = first_free;
  224. found = 1;
  225. }
  226. add_new_free_space(block_group, root->fs_info, last,
  227. key.objectid);
  228. last = key.objectid + key.offset;
  229. }
  230. next:
  231. path->slots[0]++;
  232. }
  233. if (!found)
  234. last = first_free;
  235. add_new_free_space(block_group, root->fs_info, last,
  236. block_group->key.objectid +
  237. block_group->key.offset);
  238. block_group->cached = 1;
  239. ret = 0;
  240. err:
  241. btrfs_free_path(path);
  242. return ret;
  243. }
  244. /*
  245. * return the block group that starts at or after bytenr
  246. */
  247. struct btrfs_block_group_cache *btrfs_lookup_first_block_group(struct
  248. btrfs_fs_info *info,
  249. u64 bytenr)
  250. {
  251. struct btrfs_block_group_cache *cache;
  252. cache = block_group_cache_tree_search(info, bytenr, 0);
  253. return cache;
  254. }
  255. /*
  256. * return the block group that contains teh given bytenr
  257. */
  258. struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
  259. btrfs_fs_info *info,
  260. u64 bytenr)
  261. {
  262. struct btrfs_block_group_cache *cache;
  263. cache = block_group_cache_tree_search(info, bytenr, 1);
  264. return cache;
  265. }
  266. static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
  267. u64 flags)
  268. {
  269. struct list_head *head = &info->space_info;
  270. struct list_head *cur;
  271. struct btrfs_space_info *found;
  272. list_for_each(cur, head) {
  273. found = list_entry(cur, struct btrfs_space_info, list);
  274. if (found->flags == flags)
  275. return found;
  276. }
  277. return NULL;
  278. }
  279. static u64 div_factor(u64 num, int factor)
  280. {
  281. if (factor == 10)
  282. return num;
  283. num *= factor;
  284. do_div(num, 10);
  285. return num;
  286. }
  287. static struct btrfs_block_group_cache *
  288. __btrfs_find_block_group(struct btrfs_root *root,
  289. struct btrfs_block_group_cache *hint,
  290. u64 search_start, int data, int owner)
  291. {
  292. struct btrfs_block_group_cache *cache;
  293. struct btrfs_block_group_cache *found_group = NULL;
  294. struct btrfs_fs_info *info = root->fs_info;
  295. u64 used;
  296. u64 last = 0;
  297. u64 free_check;
  298. int full_search = 0;
  299. int factor = 10;
  300. int wrapped = 0;
  301. if (data & BTRFS_BLOCK_GROUP_METADATA)
  302. factor = 9;
  303. if (search_start) {
  304. struct btrfs_block_group_cache *shint;
  305. shint = btrfs_lookup_first_block_group(info, search_start);
  306. if (shint && block_group_bits(shint, data) && !shint->ro) {
  307. spin_lock(&shint->lock);
  308. used = btrfs_block_group_used(&shint->item);
  309. if (used + shint->pinned + shint->reserved <
  310. div_factor(shint->key.offset, factor)) {
  311. spin_unlock(&shint->lock);
  312. return shint;
  313. }
  314. spin_unlock(&shint->lock);
  315. }
  316. }
  317. if (hint && !hint->ro && block_group_bits(hint, data)) {
  318. spin_lock(&hint->lock);
  319. used = btrfs_block_group_used(&hint->item);
  320. if (used + hint->pinned + hint->reserved <
  321. div_factor(hint->key.offset, factor)) {
  322. spin_unlock(&hint->lock);
  323. return hint;
  324. }
  325. spin_unlock(&hint->lock);
  326. last = hint->key.objectid + hint->key.offset;
  327. } else {
  328. if (hint)
  329. last = max(hint->key.objectid, search_start);
  330. else
  331. last = search_start;
  332. }
  333. again:
  334. while (1) {
  335. cache = btrfs_lookup_first_block_group(root->fs_info, last);
  336. if (!cache)
  337. break;
  338. spin_lock(&cache->lock);
  339. last = cache->key.objectid + cache->key.offset;
  340. used = btrfs_block_group_used(&cache->item);
  341. if (!cache->ro && block_group_bits(cache, data)) {
  342. free_check = div_factor(cache->key.offset, factor);
  343. if (used + cache->pinned + cache->reserved <
  344. free_check) {
  345. found_group = cache;
  346. spin_unlock(&cache->lock);
  347. goto found;
  348. }
  349. }
  350. spin_unlock(&cache->lock);
  351. cond_resched();
  352. }
  353. if (!wrapped) {
  354. last = search_start;
  355. wrapped = 1;
  356. goto again;
  357. }
  358. if (!full_search && factor < 10) {
  359. last = search_start;
  360. full_search = 1;
  361. factor = 10;
  362. goto again;
  363. }
  364. found:
  365. return found_group;
  366. }
  367. struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
  368. struct btrfs_block_group_cache
  369. *hint, u64 search_start,
  370. int data, int owner)
  371. {
  372. struct btrfs_block_group_cache *ret;
  373. ret = __btrfs_find_block_group(root, hint, search_start, data, owner);
  374. return ret;
  375. }
  376. /* simple helper to search for an existing extent at a given offset */
  377. int btrfs_lookup_extent(struct btrfs_root *root, u64 start, u64 len)
  378. {
  379. int ret;
  380. struct btrfs_key key;
  381. struct btrfs_path *path;
  382. path = btrfs_alloc_path();
  383. BUG_ON(!path);
  384. key.objectid = start;
  385. key.offset = len;
  386. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  387. ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
  388. 0, 0);
  389. btrfs_free_path(path);
  390. return ret;
  391. }
  392. /*
  393. * Back reference rules. Back refs have three main goals:
  394. *
  395. * 1) differentiate between all holders of references to an extent so that
  396. * when a reference is dropped we can make sure it was a valid reference
  397. * before freeing the extent.
  398. *
  399. * 2) Provide enough information to quickly find the holders of an extent
  400. * if we notice a given block is corrupted or bad.
  401. *
  402. * 3) Make it easy to migrate blocks for FS shrinking or storage pool
  403. * maintenance. This is actually the same as #2, but with a slightly
  404. * different use case.
  405. *
  406. * File extents can be referenced by:
  407. *
  408. * - multiple snapshots, subvolumes, or different generations in one subvol
  409. * - different files inside a single subvolume
  410. * - different offsets inside a file (bookend extents in file.c)
  411. *
  412. * The extent ref structure has fields for:
  413. *
  414. * - Objectid of the subvolume root
  415. * - Generation number of the tree holding the reference
  416. * - objectid of the file holding the reference
  417. * - number of references holding by parent node (alway 1 for tree blocks)
  418. *
  419. * Btree leaf may hold multiple references to a file extent. In most cases,
  420. * these references are from same file and the corresponding offsets inside
  421. * the file are close together.
  422. *
  423. * When a file extent is allocated the fields are filled in:
  424. * (root_key.objectid, trans->transid, inode objectid, 1)
  425. *
  426. * When a leaf is cow'd new references are added for every file extent found
  427. * in the leaf. It looks similar to the create case, but trans->transid will
  428. * be different when the block is cow'd.
  429. *
  430. * (root_key.objectid, trans->transid, inode objectid,
  431. * number of references in the leaf)
  432. *
  433. * When a file extent is removed either during snapshot deletion or
  434. * file truncation, we find the corresponding back reference and check
  435. * the following fields:
  436. *
  437. * (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
  438. * inode objectid)
  439. *
  440. * Btree extents can be referenced by:
  441. *
  442. * - Different subvolumes
  443. * - Different generations of the same subvolume
  444. *
  445. * When a tree block is created, back references are inserted:
  446. *
  447. * (root->root_key.objectid, trans->transid, level, 1)
  448. *
  449. * When a tree block is cow'd, new back references are added for all the
  450. * blocks it points to. If the tree block isn't in reference counted root,
  451. * the old back references are removed. These new back references are of
  452. * the form (trans->transid will have increased since creation):
  453. *
  454. * (root->root_key.objectid, trans->transid, level, 1)
  455. *
  456. * When a backref is in deleting, the following fields are checked:
  457. *
  458. * if backref was for a tree root:
  459. * (btrfs_header_owner(itself), btrfs_header_generation(itself), level)
  460. * else
  461. * (btrfs_header_owner(parent), btrfs_header_generation(parent), level)
  462. *
  463. * Back Reference Key composing:
  464. *
  465. * The key objectid corresponds to the first byte in the extent, the key
  466. * type is set to BTRFS_EXTENT_REF_KEY, and the key offset is the first
  467. * byte of parent extent. If a extent is tree root, the key offset is set
  468. * to the key objectid.
  469. */
  470. static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
  471. struct btrfs_root *root,
  472. struct btrfs_path *path,
  473. u64 bytenr, u64 parent,
  474. u64 ref_root, u64 ref_generation,
  475. u64 owner_objectid, int del)
  476. {
  477. struct btrfs_key key;
  478. struct btrfs_extent_ref *ref;
  479. struct extent_buffer *leaf;
  480. u64 ref_objectid;
  481. int ret;
  482. key.objectid = bytenr;
  483. key.type = BTRFS_EXTENT_REF_KEY;
  484. key.offset = parent;
  485. ret = btrfs_search_slot(trans, root, &key, path, del ? -1 : 0, 1);
  486. if (ret < 0)
  487. goto out;
  488. if (ret > 0) {
  489. ret = -ENOENT;
  490. goto out;
  491. }
  492. leaf = path->nodes[0];
  493. ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
  494. ref_objectid = btrfs_ref_objectid(leaf, ref);
  495. if (btrfs_ref_root(leaf, ref) != ref_root ||
  496. btrfs_ref_generation(leaf, ref) != ref_generation ||
  497. (ref_objectid != owner_objectid &&
  498. ref_objectid != BTRFS_MULTIPLE_OBJECTIDS)) {
  499. ret = -EIO;
  500. WARN_ON(1);
  501. goto out;
  502. }
  503. ret = 0;
  504. out:
  505. return ret;
  506. }
  507. static int noinline insert_extent_backref(struct btrfs_trans_handle *trans,
  508. struct btrfs_root *root,
  509. struct btrfs_path *path,
  510. u64 bytenr, u64 parent,
  511. u64 ref_root, u64 ref_generation,
  512. u64 owner_objectid)
  513. {
  514. struct btrfs_key key;
  515. struct extent_buffer *leaf;
  516. struct btrfs_extent_ref *ref;
  517. u32 num_refs;
  518. int ret;
  519. key.objectid = bytenr;
  520. key.type = BTRFS_EXTENT_REF_KEY;
  521. key.offset = parent;
  522. ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*ref));
  523. if (ret == 0) {
  524. leaf = path->nodes[0];
  525. ref = btrfs_item_ptr(leaf, path->slots[0],
  526. struct btrfs_extent_ref);
  527. btrfs_set_ref_root(leaf, ref, ref_root);
  528. btrfs_set_ref_generation(leaf, ref, ref_generation);
  529. btrfs_set_ref_objectid(leaf, ref, owner_objectid);
  530. btrfs_set_ref_num_refs(leaf, ref, 1);
  531. } else if (ret == -EEXIST) {
  532. u64 existing_owner;
  533. BUG_ON(owner_objectid < BTRFS_FIRST_FREE_OBJECTID);
  534. leaf = path->nodes[0];
  535. ref = btrfs_item_ptr(leaf, path->slots[0],
  536. struct btrfs_extent_ref);
  537. if (btrfs_ref_root(leaf, ref) != ref_root ||
  538. btrfs_ref_generation(leaf, ref) != ref_generation) {
  539. ret = -EIO;
  540. WARN_ON(1);
  541. goto out;
  542. }
  543. num_refs = btrfs_ref_num_refs(leaf, ref);
  544. BUG_ON(num_refs == 0);
  545. btrfs_set_ref_num_refs(leaf, ref, num_refs + 1);
  546. existing_owner = btrfs_ref_objectid(leaf, ref);
  547. if (existing_owner != owner_objectid &&
  548. existing_owner != BTRFS_MULTIPLE_OBJECTIDS) {
  549. btrfs_set_ref_objectid(leaf, ref,
  550. BTRFS_MULTIPLE_OBJECTIDS);
  551. }
  552. ret = 0;
  553. } else {
  554. goto out;
  555. }
  556. btrfs_mark_buffer_dirty(path->nodes[0]);
  557. out:
  558. btrfs_release_path(root, path);
  559. return ret;
  560. }
  561. static int noinline remove_extent_backref(struct btrfs_trans_handle *trans,
  562. struct btrfs_root *root,
  563. struct btrfs_path *path)
  564. {
  565. struct extent_buffer *leaf;
  566. struct btrfs_extent_ref *ref;
  567. u32 num_refs;
  568. int ret = 0;
  569. leaf = path->nodes[0];
  570. ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
  571. num_refs = btrfs_ref_num_refs(leaf, ref);
  572. BUG_ON(num_refs == 0);
  573. num_refs -= 1;
  574. if (num_refs == 0) {
  575. ret = btrfs_del_item(trans, root, path);
  576. } else {
  577. btrfs_set_ref_num_refs(leaf, ref, num_refs);
  578. btrfs_mark_buffer_dirty(leaf);
  579. }
  580. btrfs_release_path(root, path);
  581. return ret;
  582. }
  583. static int __btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
  584. struct btrfs_root *root, u64 bytenr,
  585. u64 orig_parent, u64 parent,
  586. u64 orig_root, u64 ref_root,
  587. u64 orig_generation, u64 ref_generation,
  588. u64 owner_objectid)
  589. {
  590. int ret;
  591. struct btrfs_root *extent_root = root->fs_info->extent_root;
  592. struct btrfs_path *path;
  593. if (root == root->fs_info->extent_root) {
  594. struct pending_extent_op *extent_op;
  595. u64 num_bytes;
  596. BUG_ON(owner_objectid >= BTRFS_MAX_LEVEL);
  597. num_bytes = btrfs_level_size(root, (int)owner_objectid);
  598. mutex_lock(&root->fs_info->extent_ins_mutex);
  599. if (test_range_bit(&root->fs_info->extent_ins, bytenr,
  600. bytenr + num_bytes - 1, EXTENT_WRITEBACK, 0)) {
  601. u64 priv;
  602. ret = get_state_private(&root->fs_info->extent_ins,
  603. bytenr, &priv);
  604. BUG_ON(ret);
  605. extent_op = (struct pending_extent_op *)
  606. (unsigned long)priv;
  607. BUG_ON(extent_op->parent != orig_parent);
  608. BUG_ON(extent_op->generation != orig_generation);
  609. extent_op->parent = parent;
  610. extent_op->generation = ref_generation;
  611. } else {
  612. extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
  613. BUG_ON(!extent_op);
  614. extent_op->type = PENDING_BACKREF_UPDATE;
  615. extent_op->bytenr = bytenr;
  616. extent_op->num_bytes = num_bytes;
  617. extent_op->parent = parent;
  618. extent_op->orig_parent = orig_parent;
  619. extent_op->generation = ref_generation;
  620. extent_op->orig_generation = orig_generation;
  621. extent_op->level = (int)owner_objectid;
  622. set_extent_bits(&root->fs_info->extent_ins,
  623. bytenr, bytenr + num_bytes - 1,
  624. EXTENT_WRITEBACK, GFP_NOFS);
  625. set_state_private(&root->fs_info->extent_ins,
  626. bytenr, (unsigned long)extent_op);
  627. }
  628. mutex_unlock(&root->fs_info->extent_ins_mutex);
  629. return 0;
  630. }
  631. path = btrfs_alloc_path();
  632. if (!path)
  633. return -ENOMEM;
  634. ret = lookup_extent_backref(trans, extent_root, path,
  635. bytenr, orig_parent, orig_root,
  636. orig_generation, owner_objectid, 1);
  637. if (ret)
  638. goto out;
  639. ret = remove_extent_backref(trans, extent_root, path);
  640. if (ret)
  641. goto out;
  642. ret = insert_extent_backref(trans, extent_root, path, bytenr,
  643. parent, ref_root, ref_generation,
  644. owner_objectid);
  645. BUG_ON(ret);
  646. finish_current_insert(trans, extent_root, 0);
  647. del_pending_extents(trans, extent_root, 0);
  648. out:
  649. btrfs_free_path(path);
  650. return ret;
  651. }
  652. int btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
  653. struct btrfs_root *root, u64 bytenr,
  654. u64 orig_parent, u64 parent,
  655. u64 ref_root, u64 ref_generation,
  656. u64 owner_objectid)
  657. {
  658. int ret;
  659. if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
  660. owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
  661. return 0;
  662. ret = __btrfs_update_extent_ref(trans, root, bytenr, orig_parent,
  663. parent, ref_root, ref_root,
  664. ref_generation, ref_generation,
  665. owner_objectid);
  666. return ret;
  667. }
  668. static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
  669. struct btrfs_root *root, u64 bytenr,
  670. u64 orig_parent, u64 parent,
  671. u64 orig_root, u64 ref_root,
  672. u64 orig_generation, u64 ref_generation,
  673. u64 owner_objectid)
  674. {
  675. struct btrfs_path *path;
  676. int ret;
  677. struct btrfs_key key;
  678. struct extent_buffer *l;
  679. struct btrfs_extent_item *item;
  680. u32 refs;
  681. path = btrfs_alloc_path();
  682. if (!path)
  683. return -ENOMEM;
  684. path->reada = 1;
  685. key.objectid = bytenr;
  686. key.type = BTRFS_EXTENT_ITEM_KEY;
  687. key.offset = (u64)-1;
  688. ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
  689. 0, 1);
  690. if (ret < 0)
  691. return ret;
  692. BUG_ON(ret == 0 || path->slots[0] == 0);
  693. path->slots[0]--;
  694. l = path->nodes[0];
  695. btrfs_item_key_to_cpu(l, &key, path->slots[0]);
  696. if (key.objectid != bytenr) {
  697. btrfs_print_leaf(root->fs_info->extent_root, path->nodes[0]);
  698. printk("wanted %Lu found %Lu\n", bytenr, key.objectid);
  699. BUG();
  700. }
  701. BUG_ON(key.type != BTRFS_EXTENT_ITEM_KEY);
  702. item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
  703. refs = btrfs_extent_refs(l, item);
  704. btrfs_set_extent_refs(l, item, refs + 1);
  705. btrfs_mark_buffer_dirty(path->nodes[0]);
  706. btrfs_release_path(root->fs_info->extent_root, path);
  707. path->reada = 1;
  708. ret = insert_extent_backref(trans, root->fs_info->extent_root,
  709. path, bytenr, parent,
  710. ref_root, ref_generation,
  711. owner_objectid);
  712. BUG_ON(ret);
  713. finish_current_insert(trans, root->fs_info->extent_root, 0);
  714. del_pending_extents(trans, root->fs_info->extent_root, 0);
  715. btrfs_free_path(path);
  716. return 0;
  717. }
  718. int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
  719. struct btrfs_root *root,
  720. u64 bytenr, u64 num_bytes, u64 parent,
  721. u64 ref_root, u64 ref_generation,
  722. u64 owner_objectid)
  723. {
  724. int ret;
  725. if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
  726. owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
  727. return 0;
  728. ret = __btrfs_inc_extent_ref(trans, root, bytenr, 0, parent,
  729. 0, ref_root, 0, ref_generation,
  730. owner_objectid);
  731. return ret;
  732. }
  733. int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
  734. struct btrfs_root *root)
  735. {
  736. finish_current_insert(trans, root->fs_info->extent_root, 1);
  737. del_pending_extents(trans, root->fs_info->extent_root, 1);
  738. return 0;
  739. }
  740. int btrfs_lookup_extent_ref(struct btrfs_trans_handle *trans,
  741. struct btrfs_root *root, u64 bytenr,
  742. u64 num_bytes, u32 *refs)
  743. {
  744. struct btrfs_path *path;
  745. int ret;
  746. struct btrfs_key key;
  747. struct extent_buffer *l;
  748. struct btrfs_extent_item *item;
  749. WARN_ON(num_bytes < root->sectorsize);
  750. path = btrfs_alloc_path();
  751. path->reada = 1;
  752. key.objectid = bytenr;
  753. key.offset = num_bytes;
  754. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  755. ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
  756. 0, 0);
  757. if (ret < 0)
  758. goto out;
  759. if (ret != 0) {
  760. btrfs_print_leaf(root, path->nodes[0]);
  761. printk("failed to find block number %Lu\n", bytenr);
  762. BUG();
  763. }
  764. l = path->nodes[0];
  765. item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
  766. *refs = btrfs_extent_refs(l, item);
  767. out:
  768. btrfs_free_path(path);
  769. return 0;
  770. }
  771. int btrfs_cross_ref_exist(struct btrfs_trans_handle *trans,
  772. struct btrfs_root *root, u64 bytenr)
  773. {
  774. struct btrfs_root *extent_root = root->fs_info->extent_root;
  775. struct btrfs_path *path;
  776. struct extent_buffer *leaf;
  777. struct btrfs_extent_ref *ref_item;
  778. struct btrfs_key key;
  779. struct btrfs_key found_key;
  780. u64 ref_root;
  781. u64 last_snapshot;
  782. u32 nritems;
  783. int ret;
  784. key.objectid = bytenr;
  785. key.offset = (u64)-1;
  786. key.type = BTRFS_EXTENT_ITEM_KEY;
  787. path = btrfs_alloc_path();
  788. ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
  789. if (ret < 0)
  790. goto out;
  791. BUG_ON(ret == 0);
  792. ret = -ENOENT;
  793. if (path->slots[0] == 0)
  794. goto out;
  795. path->slots[0]--;
  796. leaf = path->nodes[0];
  797. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  798. if (found_key.objectid != bytenr ||
  799. found_key.type != BTRFS_EXTENT_ITEM_KEY)
  800. goto out;
  801. last_snapshot = btrfs_root_last_snapshot(&root->root_item);
  802. while (1) {
  803. leaf = path->nodes[0];
  804. nritems = btrfs_header_nritems(leaf);
  805. if (path->slots[0] >= nritems) {
  806. ret = btrfs_next_leaf(extent_root, path);
  807. if (ret < 0)
  808. goto out;
  809. if (ret == 0)
  810. continue;
  811. break;
  812. }
  813. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  814. if (found_key.objectid != bytenr)
  815. break;
  816. if (found_key.type != BTRFS_EXTENT_REF_KEY) {
  817. path->slots[0]++;
  818. continue;
  819. }
  820. ref_item = btrfs_item_ptr(leaf, path->slots[0],
  821. struct btrfs_extent_ref);
  822. ref_root = btrfs_ref_root(leaf, ref_item);
  823. if (ref_root != root->root_key.objectid &&
  824. ref_root != BTRFS_TREE_LOG_OBJECTID) {
  825. ret = 1;
  826. goto out;
  827. }
  828. if (btrfs_ref_generation(leaf, ref_item) <= last_snapshot) {
  829. ret = 1;
  830. goto out;
  831. }
  832. path->slots[0]++;
  833. }
  834. ret = 0;
  835. out:
  836. btrfs_free_path(path);
  837. return ret;
  838. }
  839. int btrfs_cache_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  840. struct extent_buffer *buf, u32 nr_extents)
  841. {
  842. struct btrfs_key key;
  843. struct btrfs_file_extent_item *fi;
  844. u64 root_gen;
  845. u32 nritems;
  846. int i;
  847. int level;
  848. int ret = 0;
  849. int shared = 0;
  850. if (!root->ref_cows)
  851. return 0;
  852. if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
  853. shared = 0;
  854. root_gen = root->root_key.offset;
  855. } else {
  856. shared = 1;
  857. root_gen = trans->transid - 1;
  858. }
  859. level = btrfs_header_level(buf);
  860. nritems = btrfs_header_nritems(buf);
  861. if (level == 0) {
  862. struct btrfs_leaf_ref *ref;
  863. struct btrfs_extent_info *info;
  864. ref = btrfs_alloc_leaf_ref(root, nr_extents);
  865. if (!ref) {
  866. ret = -ENOMEM;
  867. goto out;
  868. }
  869. ref->root_gen = root_gen;
  870. ref->bytenr = buf->start;
  871. ref->owner = btrfs_header_owner(buf);
  872. ref->generation = btrfs_header_generation(buf);
  873. ref->nritems = nr_extents;
  874. info = ref->extents;
  875. for (i = 0; nr_extents > 0 && i < nritems; i++) {
  876. u64 disk_bytenr;
  877. btrfs_item_key_to_cpu(buf, &key, i);
  878. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  879. continue;
  880. fi = btrfs_item_ptr(buf, i,
  881. struct btrfs_file_extent_item);
  882. if (btrfs_file_extent_type(buf, fi) ==
  883. BTRFS_FILE_EXTENT_INLINE)
  884. continue;
  885. disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
  886. if (disk_bytenr == 0)
  887. continue;
  888. info->bytenr = disk_bytenr;
  889. info->num_bytes =
  890. btrfs_file_extent_disk_num_bytes(buf, fi);
  891. info->objectid = key.objectid;
  892. info->offset = key.offset;
  893. info++;
  894. }
  895. ret = btrfs_add_leaf_ref(root, ref, shared);
  896. if (ret == -EEXIST && shared) {
  897. struct btrfs_leaf_ref *old;
  898. old = btrfs_lookup_leaf_ref(root, ref->bytenr);
  899. BUG_ON(!old);
  900. btrfs_remove_leaf_ref(root, old);
  901. btrfs_free_leaf_ref(root, old);
  902. ret = btrfs_add_leaf_ref(root, ref, shared);
  903. }
  904. WARN_ON(ret);
  905. btrfs_free_leaf_ref(root, ref);
  906. }
  907. out:
  908. return ret;
  909. }
  910. int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  911. struct extent_buffer *orig_buf, struct extent_buffer *buf,
  912. u32 *nr_extents)
  913. {
  914. u64 bytenr;
  915. u64 ref_root;
  916. u64 orig_root;
  917. u64 ref_generation;
  918. u64 orig_generation;
  919. u32 nritems;
  920. u32 nr_file_extents = 0;
  921. struct btrfs_key key;
  922. struct btrfs_file_extent_item *fi;
  923. int i;
  924. int level;
  925. int ret = 0;
  926. int faili = 0;
  927. int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
  928. u64, u64, u64, u64, u64, u64, u64, u64);
  929. ref_root = btrfs_header_owner(buf);
  930. ref_generation = btrfs_header_generation(buf);
  931. orig_root = btrfs_header_owner(orig_buf);
  932. orig_generation = btrfs_header_generation(orig_buf);
  933. nritems = btrfs_header_nritems(buf);
  934. level = btrfs_header_level(buf);
  935. if (root->ref_cows) {
  936. process_func = __btrfs_inc_extent_ref;
  937. } else {
  938. if (level == 0 &&
  939. root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
  940. goto out;
  941. if (level != 0 &&
  942. root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID)
  943. goto out;
  944. process_func = __btrfs_update_extent_ref;
  945. }
  946. for (i = 0; i < nritems; i++) {
  947. cond_resched();
  948. if (level == 0) {
  949. btrfs_item_key_to_cpu(buf, &key, i);
  950. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  951. continue;
  952. fi = btrfs_item_ptr(buf, i,
  953. struct btrfs_file_extent_item);
  954. if (btrfs_file_extent_type(buf, fi) ==
  955. BTRFS_FILE_EXTENT_INLINE)
  956. continue;
  957. bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
  958. if (bytenr == 0)
  959. continue;
  960. nr_file_extents++;
  961. ret = process_func(trans, root, bytenr,
  962. orig_buf->start, buf->start,
  963. orig_root, ref_root,
  964. orig_generation, ref_generation,
  965. key.objectid);
  966. if (ret) {
  967. faili = i;
  968. WARN_ON(1);
  969. goto fail;
  970. }
  971. } else {
  972. bytenr = btrfs_node_blockptr(buf, i);
  973. ret = process_func(trans, root, bytenr,
  974. orig_buf->start, buf->start,
  975. orig_root, ref_root,
  976. orig_generation, ref_generation,
  977. level - 1);
  978. if (ret) {
  979. faili = i;
  980. WARN_ON(1);
  981. goto fail;
  982. }
  983. }
  984. }
  985. out:
  986. if (nr_extents) {
  987. if (level == 0)
  988. *nr_extents = nr_file_extents;
  989. else
  990. *nr_extents = nritems;
  991. }
  992. return 0;
  993. fail:
  994. WARN_ON(1);
  995. return ret;
  996. }
  997. int btrfs_update_ref(struct btrfs_trans_handle *trans,
  998. struct btrfs_root *root, struct extent_buffer *orig_buf,
  999. struct extent_buffer *buf, int start_slot, int nr)
  1000. {
  1001. u64 bytenr;
  1002. u64 ref_root;
  1003. u64 orig_root;
  1004. u64 ref_generation;
  1005. u64 orig_generation;
  1006. struct btrfs_key key;
  1007. struct btrfs_file_extent_item *fi;
  1008. int i;
  1009. int ret;
  1010. int slot;
  1011. int level;
  1012. BUG_ON(start_slot < 0);
  1013. BUG_ON(start_slot + nr > btrfs_header_nritems(buf));
  1014. ref_root = btrfs_header_owner(buf);
  1015. ref_generation = btrfs_header_generation(buf);
  1016. orig_root = btrfs_header_owner(orig_buf);
  1017. orig_generation = btrfs_header_generation(orig_buf);
  1018. level = btrfs_header_level(buf);
  1019. if (!root->ref_cows) {
  1020. if (level == 0 &&
  1021. root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
  1022. return 0;
  1023. if (level != 0 &&
  1024. root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID)
  1025. return 0;
  1026. }
  1027. for (i = 0, slot = start_slot; i < nr; i++, slot++) {
  1028. cond_resched();
  1029. if (level == 0) {
  1030. btrfs_item_key_to_cpu(buf, &key, slot);
  1031. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  1032. continue;
  1033. fi = btrfs_item_ptr(buf, slot,
  1034. struct btrfs_file_extent_item);
  1035. if (btrfs_file_extent_type(buf, fi) ==
  1036. BTRFS_FILE_EXTENT_INLINE)
  1037. continue;
  1038. bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
  1039. if (bytenr == 0)
  1040. continue;
  1041. ret = __btrfs_update_extent_ref(trans, root, bytenr,
  1042. orig_buf->start, buf->start,
  1043. orig_root, ref_root,
  1044. orig_generation, ref_generation,
  1045. key.objectid);
  1046. if (ret)
  1047. goto fail;
  1048. } else {
  1049. bytenr = btrfs_node_blockptr(buf, slot);
  1050. ret = __btrfs_update_extent_ref(trans, root, bytenr,
  1051. orig_buf->start, buf->start,
  1052. orig_root, ref_root,
  1053. orig_generation, ref_generation,
  1054. level - 1);
  1055. if (ret)
  1056. goto fail;
  1057. }
  1058. }
  1059. return 0;
  1060. fail:
  1061. WARN_ON(1);
  1062. return -1;
  1063. }
  1064. static int write_one_cache_group(struct btrfs_trans_handle *trans,
  1065. struct btrfs_root *root,
  1066. struct btrfs_path *path,
  1067. struct btrfs_block_group_cache *cache)
  1068. {
  1069. int ret;
  1070. int pending_ret;
  1071. struct btrfs_root *extent_root = root->fs_info->extent_root;
  1072. unsigned long bi;
  1073. struct extent_buffer *leaf;
  1074. ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
  1075. if (ret < 0)
  1076. goto fail;
  1077. BUG_ON(ret);
  1078. leaf = path->nodes[0];
  1079. bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
  1080. write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
  1081. btrfs_mark_buffer_dirty(leaf);
  1082. btrfs_release_path(extent_root, path);
  1083. fail:
  1084. finish_current_insert(trans, extent_root, 0);
  1085. pending_ret = del_pending_extents(trans, extent_root, 0);
  1086. if (ret)
  1087. return ret;
  1088. if (pending_ret)
  1089. return pending_ret;
  1090. return 0;
  1091. }
  1092. int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
  1093. struct btrfs_root *root)
  1094. {
  1095. struct btrfs_block_group_cache *cache, *entry;
  1096. struct rb_node *n;
  1097. int err = 0;
  1098. int werr = 0;
  1099. struct btrfs_path *path;
  1100. u64 last = 0;
  1101. path = btrfs_alloc_path();
  1102. if (!path)
  1103. return -ENOMEM;
  1104. while(1) {
  1105. cache = NULL;
  1106. spin_lock(&root->fs_info->block_group_cache_lock);
  1107. for (n = rb_first(&root->fs_info->block_group_cache_tree);
  1108. n; n = rb_next(n)) {
  1109. entry = rb_entry(n, struct btrfs_block_group_cache,
  1110. cache_node);
  1111. if (entry->dirty) {
  1112. cache = entry;
  1113. break;
  1114. }
  1115. }
  1116. spin_unlock(&root->fs_info->block_group_cache_lock);
  1117. if (!cache)
  1118. break;
  1119. cache->dirty = 0;
  1120. last += cache->key.offset;
  1121. err = write_one_cache_group(trans, root,
  1122. path, cache);
  1123. /*
  1124. * if we fail to write the cache group, we want
  1125. * to keep it marked dirty in hopes that a later
  1126. * write will work
  1127. */
  1128. if (err) {
  1129. werr = err;
  1130. continue;
  1131. }
  1132. }
  1133. btrfs_free_path(path);
  1134. return werr;
  1135. }
  1136. static int update_space_info(struct btrfs_fs_info *info, u64 flags,
  1137. u64 total_bytes, u64 bytes_used,
  1138. struct btrfs_space_info **space_info)
  1139. {
  1140. struct btrfs_space_info *found;
  1141. found = __find_space_info(info, flags);
  1142. if (found) {
  1143. spin_lock(&found->lock);
  1144. found->total_bytes += total_bytes;
  1145. found->bytes_used += bytes_used;
  1146. found->full = 0;
  1147. spin_unlock(&found->lock);
  1148. *space_info = found;
  1149. return 0;
  1150. }
  1151. found = kmalloc(sizeof(*found), GFP_NOFS);
  1152. if (!found)
  1153. return -ENOMEM;
  1154. list_add(&found->list, &info->space_info);
  1155. INIT_LIST_HEAD(&found->block_groups);
  1156. init_rwsem(&found->groups_sem);
  1157. spin_lock_init(&found->lock);
  1158. found->flags = flags;
  1159. found->total_bytes = total_bytes;
  1160. found->bytes_used = bytes_used;
  1161. found->bytes_pinned = 0;
  1162. found->bytes_reserved = 0;
  1163. found->full = 0;
  1164. found->force_alloc = 0;
  1165. *space_info = found;
  1166. return 0;
  1167. }
  1168. static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
  1169. {
  1170. u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
  1171. BTRFS_BLOCK_GROUP_RAID1 |
  1172. BTRFS_BLOCK_GROUP_RAID10 |
  1173. BTRFS_BLOCK_GROUP_DUP);
  1174. if (extra_flags) {
  1175. if (flags & BTRFS_BLOCK_GROUP_DATA)
  1176. fs_info->avail_data_alloc_bits |= extra_flags;
  1177. if (flags & BTRFS_BLOCK_GROUP_METADATA)
  1178. fs_info->avail_metadata_alloc_bits |= extra_flags;
  1179. if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
  1180. fs_info->avail_system_alloc_bits |= extra_flags;
  1181. }
  1182. }
  1183. static u64 reduce_alloc_profile(struct btrfs_root *root, u64 flags)
  1184. {
  1185. u64 num_devices = root->fs_info->fs_devices->num_devices;
  1186. if (num_devices == 1)
  1187. flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
  1188. if (num_devices < 4)
  1189. flags &= ~BTRFS_BLOCK_GROUP_RAID10;
  1190. if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
  1191. (flags & (BTRFS_BLOCK_GROUP_RAID1 |
  1192. BTRFS_BLOCK_GROUP_RAID10))) {
  1193. flags &= ~BTRFS_BLOCK_GROUP_DUP;
  1194. }
  1195. if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
  1196. (flags & BTRFS_BLOCK_GROUP_RAID10)) {
  1197. flags &= ~BTRFS_BLOCK_GROUP_RAID1;
  1198. }
  1199. if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
  1200. ((flags & BTRFS_BLOCK_GROUP_RAID1) |
  1201. (flags & BTRFS_BLOCK_GROUP_RAID10) |
  1202. (flags & BTRFS_BLOCK_GROUP_DUP)))
  1203. flags &= ~BTRFS_BLOCK_GROUP_RAID0;
  1204. return flags;
  1205. }
  1206. static int do_chunk_alloc(struct btrfs_trans_handle *trans,
  1207. struct btrfs_root *extent_root, u64 alloc_bytes,
  1208. u64 flags, int force)
  1209. {
  1210. struct btrfs_space_info *space_info;
  1211. u64 thresh;
  1212. u64 start;
  1213. u64 num_bytes;
  1214. int ret = 0, waited = 0;
  1215. flags = reduce_alloc_profile(extent_root, flags);
  1216. space_info = __find_space_info(extent_root->fs_info, flags);
  1217. if (!space_info) {
  1218. ret = update_space_info(extent_root->fs_info, flags,
  1219. 0, 0, &space_info);
  1220. BUG_ON(ret);
  1221. }
  1222. BUG_ON(!space_info);
  1223. spin_lock(&space_info->lock);
  1224. if (space_info->force_alloc) {
  1225. force = 1;
  1226. space_info->force_alloc = 0;
  1227. }
  1228. if (space_info->full) {
  1229. spin_unlock(&space_info->lock);
  1230. goto out;
  1231. }
  1232. thresh = div_factor(space_info->total_bytes, 6);
  1233. if (!force &&
  1234. (space_info->bytes_used + space_info->bytes_pinned +
  1235. space_info->bytes_reserved + alloc_bytes) < thresh) {
  1236. spin_unlock(&space_info->lock);
  1237. goto out;
  1238. }
  1239. spin_unlock(&space_info->lock);
  1240. ret = mutex_trylock(&extent_root->fs_info->chunk_mutex);
  1241. if (!ret && !force) {
  1242. goto out;
  1243. } else if (!ret) {
  1244. mutex_lock(&extent_root->fs_info->chunk_mutex);
  1245. waited = 1;
  1246. }
  1247. if (waited) {
  1248. spin_lock(&space_info->lock);
  1249. if (space_info->full) {
  1250. spin_unlock(&space_info->lock);
  1251. goto out_unlock;
  1252. }
  1253. spin_unlock(&space_info->lock);
  1254. }
  1255. ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
  1256. if (ret) {
  1257. printk("space info full %Lu\n", flags);
  1258. space_info->full = 1;
  1259. goto out_unlock;
  1260. }
  1261. ret = btrfs_make_block_group(trans, extent_root, 0, flags,
  1262. BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
  1263. BUG_ON(ret);
  1264. out_unlock:
  1265. mutex_unlock(&extent_root->fs_info->chunk_mutex);
  1266. out:
  1267. return ret;
  1268. }
  1269. static int update_block_group(struct btrfs_trans_handle *trans,
  1270. struct btrfs_root *root,
  1271. u64 bytenr, u64 num_bytes, int alloc,
  1272. int mark_free)
  1273. {
  1274. struct btrfs_block_group_cache *cache;
  1275. struct btrfs_fs_info *info = root->fs_info;
  1276. u64 total = num_bytes;
  1277. u64 old_val;
  1278. u64 byte_in_group;
  1279. while(total) {
  1280. cache = btrfs_lookup_block_group(info, bytenr);
  1281. if (!cache) {
  1282. return -1;
  1283. }
  1284. byte_in_group = bytenr - cache->key.objectid;
  1285. WARN_ON(byte_in_group > cache->key.offset);
  1286. spin_lock(&cache->space_info->lock);
  1287. spin_lock(&cache->lock);
  1288. cache->dirty = 1;
  1289. old_val = btrfs_block_group_used(&cache->item);
  1290. num_bytes = min(total, cache->key.offset - byte_in_group);
  1291. if (alloc) {
  1292. old_val += num_bytes;
  1293. cache->space_info->bytes_used += num_bytes;
  1294. btrfs_set_block_group_used(&cache->item, old_val);
  1295. spin_unlock(&cache->lock);
  1296. spin_unlock(&cache->space_info->lock);
  1297. } else {
  1298. old_val -= num_bytes;
  1299. cache->space_info->bytes_used -= num_bytes;
  1300. btrfs_set_block_group_used(&cache->item, old_val);
  1301. spin_unlock(&cache->lock);
  1302. spin_unlock(&cache->space_info->lock);
  1303. if (mark_free) {
  1304. int ret;
  1305. ret = btrfs_add_free_space(cache, bytenr,
  1306. num_bytes);
  1307. if (ret)
  1308. return -1;
  1309. }
  1310. }
  1311. total -= num_bytes;
  1312. bytenr += num_bytes;
  1313. }
  1314. return 0;
  1315. }
  1316. static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
  1317. {
  1318. struct btrfs_block_group_cache *cache;
  1319. cache = btrfs_lookup_first_block_group(root->fs_info, search_start);
  1320. if (!cache)
  1321. return 0;
  1322. return cache->key.objectid;
  1323. }
  1324. int btrfs_update_pinned_extents(struct btrfs_root *root,
  1325. u64 bytenr, u64 num, int pin)
  1326. {
  1327. u64 len;
  1328. struct btrfs_block_group_cache *cache;
  1329. struct btrfs_fs_info *fs_info = root->fs_info;
  1330. WARN_ON(!mutex_is_locked(&root->fs_info->pinned_mutex));
  1331. if (pin) {
  1332. set_extent_dirty(&fs_info->pinned_extents,
  1333. bytenr, bytenr + num - 1, GFP_NOFS);
  1334. } else {
  1335. clear_extent_dirty(&fs_info->pinned_extents,
  1336. bytenr, bytenr + num - 1, GFP_NOFS);
  1337. }
  1338. while (num > 0) {
  1339. cache = btrfs_lookup_block_group(fs_info, bytenr);
  1340. BUG_ON(!cache);
  1341. len = min(num, cache->key.offset -
  1342. (bytenr - cache->key.objectid));
  1343. if (pin) {
  1344. spin_lock(&cache->space_info->lock);
  1345. spin_lock(&cache->lock);
  1346. cache->pinned += len;
  1347. cache->space_info->bytes_pinned += len;
  1348. spin_unlock(&cache->lock);
  1349. spin_unlock(&cache->space_info->lock);
  1350. fs_info->total_pinned += len;
  1351. } else {
  1352. spin_lock(&cache->space_info->lock);
  1353. spin_lock(&cache->lock);
  1354. cache->pinned -= len;
  1355. cache->space_info->bytes_pinned -= len;
  1356. spin_unlock(&cache->lock);
  1357. spin_unlock(&cache->space_info->lock);
  1358. fs_info->total_pinned -= len;
  1359. }
  1360. bytenr += len;
  1361. num -= len;
  1362. }
  1363. return 0;
  1364. }
  1365. static int update_reserved_extents(struct btrfs_root *root,
  1366. u64 bytenr, u64 num, int reserve)
  1367. {
  1368. u64 len;
  1369. struct btrfs_block_group_cache *cache;
  1370. struct btrfs_fs_info *fs_info = root->fs_info;
  1371. while (num > 0) {
  1372. cache = btrfs_lookup_block_group(fs_info, bytenr);
  1373. BUG_ON(!cache);
  1374. len = min(num, cache->key.offset -
  1375. (bytenr - cache->key.objectid));
  1376. spin_lock(&cache->space_info->lock);
  1377. spin_lock(&cache->lock);
  1378. if (reserve) {
  1379. cache->reserved += len;
  1380. cache->space_info->bytes_reserved += len;
  1381. } else {
  1382. cache->reserved -= len;
  1383. cache->space_info->bytes_reserved -= len;
  1384. }
  1385. spin_unlock(&cache->lock);
  1386. spin_unlock(&cache->space_info->lock);
  1387. bytenr += len;
  1388. num -= len;
  1389. }
  1390. return 0;
  1391. }
  1392. int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
  1393. {
  1394. u64 last = 0;
  1395. u64 start;
  1396. u64 end;
  1397. struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
  1398. int ret;
  1399. mutex_lock(&root->fs_info->pinned_mutex);
  1400. while(1) {
  1401. ret = find_first_extent_bit(pinned_extents, last,
  1402. &start, &end, EXTENT_DIRTY);
  1403. if (ret)
  1404. break;
  1405. set_extent_dirty(copy, start, end, GFP_NOFS);
  1406. last = end + 1;
  1407. }
  1408. mutex_unlock(&root->fs_info->pinned_mutex);
  1409. return 0;
  1410. }
  1411. int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
  1412. struct btrfs_root *root,
  1413. struct extent_io_tree *unpin)
  1414. {
  1415. u64 start;
  1416. u64 end;
  1417. int ret;
  1418. struct btrfs_block_group_cache *cache;
  1419. mutex_lock(&root->fs_info->pinned_mutex);
  1420. while(1) {
  1421. ret = find_first_extent_bit(unpin, 0, &start, &end,
  1422. EXTENT_DIRTY);
  1423. if (ret)
  1424. break;
  1425. btrfs_update_pinned_extents(root, start, end + 1 - start, 0);
  1426. clear_extent_dirty(unpin, start, end, GFP_NOFS);
  1427. cache = btrfs_lookup_block_group(root->fs_info, start);
  1428. if (cache->cached)
  1429. btrfs_add_free_space(cache, start, end - start + 1);
  1430. if (need_resched()) {
  1431. mutex_unlock(&root->fs_info->pinned_mutex);
  1432. cond_resched();
  1433. mutex_lock(&root->fs_info->pinned_mutex);
  1434. }
  1435. }
  1436. mutex_unlock(&root->fs_info->pinned_mutex);
  1437. return 0;
  1438. }
  1439. static int finish_current_insert(struct btrfs_trans_handle *trans,
  1440. struct btrfs_root *extent_root, int all)
  1441. {
  1442. u64 start;
  1443. u64 end;
  1444. u64 priv;
  1445. u64 search = 0;
  1446. struct btrfs_fs_info *info = extent_root->fs_info;
  1447. struct btrfs_path *path;
  1448. struct btrfs_extent_ref *ref;
  1449. struct pending_extent_op *extent_op;
  1450. struct btrfs_key key;
  1451. struct btrfs_extent_item extent_item;
  1452. int ret;
  1453. int err = 0;
  1454. btrfs_set_stack_extent_refs(&extent_item, 1);
  1455. path = btrfs_alloc_path();
  1456. while(1) {
  1457. mutex_lock(&info->extent_ins_mutex);
  1458. ret = find_first_extent_bit(&info->extent_ins, search, &start,
  1459. &end, EXTENT_WRITEBACK);
  1460. if (ret) {
  1461. mutex_unlock(&info->extent_ins_mutex);
  1462. if (search && all) {
  1463. search = 0;
  1464. continue;
  1465. }
  1466. break;
  1467. }
  1468. ret = try_lock_extent(&info->extent_ins, start, end, GFP_NOFS);
  1469. if (!ret) {
  1470. search = end + 1;
  1471. mutex_unlock(&info->extent_ins_mutex);
  1472. cond_resched();
  1473. continue;
  1474. }
  1475. BUG_ON(ret < 0);
  1476. ret = get_state_private(&info->extent_ins, start, &priv);
  1477. BUG_ON(ret);
  1478. extent_op = (struct pending_extent_op *)(unsigned long)priv;
  1479. mutex_unlock(&info->extent_ins_mutex);
  1480. if (extent_op->type == PENDING_EXTENT_INSERT) {
  1481. key.objectid = start;
  1482. key.offset = end + 1 - start;
  1483. key.type = BTRFS_EXTENT_ITEM_KEY;
  1484. err = btrfs_insert_item(trans, extent_root, &key,
  1485. &extent_item, sizeof(extent_item));
  1486. BUG_ON(err);
  1487. mutex_lock(&info->extent_ins_mutex);
  1488. clear_extent_bits(&info->extent_ins, start, end,
  1489. EXTENT_WRITEBACK, GFP_NOFS);
  1490. mutex_unlock(&info->extent_ins_mutex);
  1491. err = insert_extent_backref(trans, extent_root, path,
  1492. start, extent_op->parent,
  1493. extent_root->root_key.objectid,
  1494. extent_op->generation,
  1495. extent_op->level);
  1496. BUG_ON(err);
  1497. } else if (extent_op->type == PENDING_BACKREF_UPDATE) {
  1498. err = lookup_extent_backref(trans, extent_root, path,
  1499. start, extent_op->orig_parent,
  1500. extent_root->root_key.objectid,
  1501. extent_op->orig_generation,
  1502. extent_op->level, 0);
  1503. BUG_ON(err);
  1504. mutex_lock(&info->extent_ins_mutex);
  1505. clear_extent_bits(&info->extent_ins, start, end,
  1506. EXTENT_WRITEBACK, GFP_NOFS);
  1507. mutex_unlock(&info->extent_ins_mutex);
  1508. key.objectid = start;
  1509. key.offset = extent_op->parent;
  1510. key.type = BTRFS_EXTENT_REF_KEY;
  1511. err = btrfs_set_item_key_safe(trans, extent_root, path,
  1512. &key);
  1513. BUG_ON(err);
  1514. ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
  1515. struct btrfs_extent_ref);
  1516. btrfs_set_ref_generation(path->nodes[0], ref,
  1517. extent_op->generation);
  1518. btrfs_mark_buffer_dirty(path->nodes[0]);
  1519. btrfs_release_path(extent_root, path);
  1520. } else {
  1521. BUG_ON(1);
  1522. }
  1523. kfree(extent_op);
  1524. unlock_extent(&info->extent_ins, start, end, GFP_NOFS);
  1525. if (all)
  1526. search = 0;
  1527. else
  1528. search = end + 1;
  1529. cond_resched();
  1530. }
  1531. btrfs_free_path(path);
  1532. return 0;
  1533. }
  1534. static int pin_down_bytes(struct btrfs_trans_handle *trans,
  1535. struct btrfs_root *root,
  1536. u64 bytenr, u64 num_bytes, int is_data)
  1537. {
  1538. int err = 0;
  1539. struct extent_buffer *buf;
  1540. if (is_data)
  1541. goto pinit;
  1542. buf = btrfs_find_tree_block(root, bytenr, num_bytes);
  1543. if (!buf)
  1544. goto pinit;
  1545. /* we can reuse a block if it hasn't been written
  1546. * and it is from this transaction. We can't
  1547. * reuse anything from the tree log root because
  1548. * it has tiny sub-transactions.
  1549. */
  1550. if (btrfs_buffer_uptodate(buf, 0) &&
  1551. btrfs_try_tree_lock(buf)) {
  1552. u64 header_owner = btrfs_header_owner(buf);
  1553. u64 header_transid = btrfs_header_generation(buf);
  1554. if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
  1555. header_owner != BTRFS_TREE_RELOC_OBJECTID &&
  1556. header_transid == trans->transid &&
  1557. !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
  1558. clean_tree_block(NULL, root, buf);
  1559. btrfs_tree_unlock(buf);
  1560. free_extent_buffer(buf);
  1561. return 1;
  1562. }
  1563. btrfs_tree_unlock(buf);
  1564. }
  1565. free_extent_buffer(buf);
  1566. pinit:
  1567. btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
  1568. BUG_ON(err < 0);
  1569. return 0;
  1570. }
  1571. /*
  1572. * remove an extent from the root, returns 0 on success
  1573. */
  1574. static int __free_extent(struct btrfs_trans_handle *trans,
  1575. struct btrfs_root *root,
  1576. u64 bytenr, u64 num_bytes, u64 parent,
  1577. u64 root_objectid, u64 ref_generation,
  1578. u64 owner_objectid, int pin, int mark_free)
  1579. {
  1580. struct btrfs_path *path;
  1581. struct btrfs_key key;
  1582. struct btrfs_fs_info *info = root->fs_info;
  1583. struct btrfs_root *extent_root = info->extent_root;
  1584. struct extent_buffer *leaf;
  1585. int ret;
  1586. int extent_slot = 0;
  1587. int found_extent = 0;
  1588. int num_to_del = 1;
  1589. struct btrfs_extent_item *ei;
  1590. u32 refs;
  1591. key.objectid = bytenr;
  1592. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  1593. key.offset = num_bytes;
  1594. path = btrfs_alloc_path();
  1595. if (!path)
  1596. return -ENOMEM;
  1597. path->reada = 1;
  1598. ret = lookup_extent_backref(trans, extent_root, path,
  1599. bytenr, parent, root_objectid,
  1600. ref_generation, owner_objectid, 1);
  1601. if (ret == 0) {
  1602. struct btrfs_key found_key;
  1603. extent_slot = path->slots[0];
  1604. while(extent_slot > 0) {
  1605. extent_slot--;
  1606. btrfs_item_key_to_cpu(path->nodes[0], &found_key,
  1607. extent_slot);
  1608. if (found_key.objectid != bytenr)
  1609. break;
  1610. if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
  1611. found_key.offset == num_bytes) {
  1612. found_extent = 1;
  1613. break;
  1614. }
  1615. if (path->slots[0] - extent_slot > 5)
  1616. break;
  1617. }
  1618. if (!found_extent) {
  1619. ret = remove_extent_backref(trans, extent_root, path);
  1620. BUG_ON(ret);
  1621. btrfs_release_path(extent_root, path);
  1622. ret = btrfs_search_slot(trans, extent_root,
  1623. &key, path, -1, 1);
  1624. BUG_ON(ret);
  1625. extent_slot = path->slots[0];
  1626. }
  1627. } else {
  1628. btrfs_print_leaf(extent_root, path->nodes[0]);
  1629. WARN_ON(1);
  1630. printk("Unable to find ref byte nr %Lu root %Lu "
  1631. "gen %Lu owner %Lu\n", bytenr,
  1632. root_objectid, ref_generation, owner_objectid);
  1633. }
  1634. leaf = path->nodes[0];
  1635. ei = btrfs_item_ptr(leaf, extent_slot,
  1636. struct btrfs_extent_item);
  1637. refs = btrfs_extent_refs(leaf, ei);
  1638. BUG_ON(refs == 0);
  1639. refs -= 1;
  1640. btrfs_set_extent_refs(leaf, ei, refs);
  1641. btrfs_mark_buffer_dirty(leaf);
  1642. if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
  1643. struct btrfs_extent_ref *ref;
  1644. ref = btrfs_item_ptr(leaf, path->slots[0],
  1645. struct btrfs_extent_ref);
  1646. BUG_ON(btrfs_ref_num_refs(leaf, ref) != 1);
  1647. /* if the back ref and the extent are next to each other
  1648. * they get deleted below in one shot
  1649. */
  1650. path->slots[0] = extent_slot;
  1651. num_to_del = 2;
  1652. } else if (found_extent) {
  1653. /* otherwise delete the extent back ref */
  1654. ret = remove_extent_backref(trans, extent_root, path);
  1655. BUG_ON(ret);
  1656. /* if refs are 0, we need to setup the path for deletion */
  1657. if (refs == 0) {
  1658. btrfs_release_path(extent_root, path);
  1659. ret = btrfs_search_slot(trans, extent_root, &key, path,
  1660. -1, 1);
  1661. BUG_ON(ret);
  1662. }
  1663. }
  1664. if (refs == 0) {
  1665. u64 super_used;
  1666. u64 root_used;
  1667. #ifdef BIO_RW_DISCARD
  1668. u64 map_length = num_bytes;
  1669. struct btrfs_multi_bio *multi = NULL;
  1670. #endif
  1671. if (pin) {
  1672. mutex_lock(&root->fs_info->pinned_mutex);
  1673. ret = pin_down_bytes(trans, root, bytenr, num_bytes,
  1674. owner_objectid >= BTRFS_FIRST_FREE_OBJECTID);
  1675. mutex_unlock(&root->fs_info->pinned_mutex);
  1676. if (ret > 0)
  1677. mark_free = 1;
  1678. BUG_ON(ret < 0);
  1679. }
  1680. /* block accounting for super block */
  1681. spin_lock_irq(&info->delalloc_lock);
  1682. super_used = btrfs_super_bytes_used(&info->super_copy);
  1683. btrfs_set_super_bytes_used(&info->super_copy,
  1684. super_used - num_bytes);
  1685. spin_unlock_irq(&info->delalloc_lock);
  1686. /* block accounting for root item */
  1687. root_used = btrfs_root_used(&root->root_item);
  1688. btrfs_set_root_used(&root->root_item,
  1689. root_used - num_bytes);
  1690. ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
  1691. num_to_del);
  1692. BUG_ON(ret);
  1693. btrfs_release_path(extent_root, path);
  1694. ret = update_block_group(trans, root, bytenr, num_bytes, 0,
  1695. mark_free);
  1696. BUG_ON(ret);
  1697. #ifdef BIO_RW_DISCARD
  1698. /* Tell the block device(s) that the sectors can be discarded */
  1699. ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
  1700. bytenr, &map_length, &multi, 0);
  1701. if (!ret) {
  1702. struct btrfs_bio_stripe *stripe = multi->stripes;
  1703. int i;
  1704. if (map_length > num_bytes)
  1705. map_length = num_bytes;
  1706. for (i = 0; i < multi->num_stripes; i++, stripe++) {
  1707. blkdev_issue_discard(stripe->dev->bdev,
  1708. stripe->physical >> 9,
  1709. map_length >> 9);
  1710. }
  1711. kfree(multi);
  1712. }
  1713. #endif
  1714. }
  1715. btrfs_free_path(path);
  1716. finish_current_insert(trans, extent_root, 0);
  1717. return ret;
  1718. }
  1719. /*
  1720. * find all the blocks marked as pending in the radix tree and remove
  1721. * them from the extent map
  1722. */
  1723. static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  1724. btrfs_root *extent_root, int all)
  1725. {
  1726. int ret;
  1727. int err = 0;
  1728. u64 start;
  1729. u64 end;
  1730. u64 priv;
  1731. u64 search = 0;
  1732. struct extent_io_tree *pending_del;
  1733. struct extent_io_tree *extent_ins;
  1734. struct pending_extent_op *extent_op;
  1735. struct btrfs_fs_info *info = extent_root->fs_info;
  1736. extent_ins = &extent_root->fs_info->extent_ins;
  1737. pending_del = &extent_root->fs_info->pending_del;
  1738. while(1) {
  1739. mutex_lock(&info->extent_ins_mutex);
  1740. ret = find_first_extent_bit(pending_del, search, &start, &end,
  1741. EXTENT_WRITEBACK);
  1742. if (ret) {
  1743. mutex_unlock(&info->extent_ins_mutex);
  1744. if (all && search) {
  1745. search = 0;
  1746. continue;
  1747. }
  1748. break;
  1749. }
  1750. ret = try_lock_extent(extent_ins, start, end, GFP_NOFS);
  1751. if (!ret) {
  1752. search = end+1;
  1753. mutex_unlock(&info->extent_ins_mutex);
  1754. cond_resched();
  1755. continue;
  1756. }
  1757. BUG_ON(ret < 0);
  1758. ret = get_state_private(pending_del, start, &priv);
  1759. BUG_ON(ret);
  1760. extent_op = (struct pending_extent_op *)(unsigned long)priv;
  1761. clear_extent_bits(pending_del, start, end, EXTENT_WRITEBACK,
  1762. GFP_NOFS);
  1763. if (!test_range_bit(extent_ins, start, end,
  1764. EXTENT_WRITEBACK, 0)) {
  1765. mutex_unlock(&info->extent_ins_mutex);
  1766. free_extent:
  1767. ret = __free_extent(trans, extent_root,
  1768. start, end + 1 - start,
  1769. extent_op->orig_parent,
  1770. extent_root->root_key.objectid,
  1771. extent_op->orig_generation,
  1772. extent_op->level, 1, 0);
  1773. kfree(extent_op);
  1774. } else {
  1775. kfree(extent_op);
  1776. ret = get_state_private(&info->extent_ins, start,
  1777. &priv);
  1778. BUG_ON(ret);
  1779. extent_op = (struct pending_extent_op *)
  1780. (unsigned long)priv;
  1781. clear_extent_bits(&info->extent_ins, start, end,
  1782. EXTENT_WRITEBACK, GFP_NOFS);
  1783. mutex_unlock(&info->extent_ins_mutex);
  1784. if (extent_op->type == PENDING_BACKREF_UPDATE)
  1785. goto free_extent;
  1786. mutex_lock(&extent_root->fs_info->pinned_mutex);
  1787. ret = pin_down_bytes(trans, extent_root, start,
  1788. end + 1 - start, 0);
  1789. mutex_unlock(&extent_root->fs_info->pinned_mutex);
  1790. ret = update_block_group(trans, extent_root, start,
  1791. end + 1 - start, 0, ret > 0);
  1792. BUG_ON(ret);
  1793. kfree(extent_op);
  1794. }
  1795. if (ret)
  1796. err = ret;
  1797. unlock_extent(extent_ins, start, end, GFP_NOFS);
  1798. if (all)
  1799. search = 0;
  1800. else
  1801. search = end + 1;
  1802. cond_resched();
  1803. }
  1804. return err;
  1805. }
  1806. /*
  1807. * remove an extent from the root, returns 0 on success
  1808. */
  1809. static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
  1810. struct btrfs_root *root,
  1811. u64 bytenr, u64 num_bytes, u64 parent,
  1812. u64 root_objectid, u64 ref_generation,
  1813. u64 owner_objectid, int pin)
  1814. {
  1815. struct btrfs_root *extent_root = root->fs_info->extent_root;
  1816. int pending_ret;
  1817. int ret;
  1818. WARN_ON(num_bytes < root->sectorsize);
  1819. if (root == extent_root) {
  1820. struct pending_extent_op *extent_op;
  1821. extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
  1822. BUG_ON(!extent_op);
  1823. extent_op->type = PENDING_EXTENT_DELETE;
  1824. extent_op->bytenr = bytenr;
  1825. extent_op->num_bytes = num_bytes;
  1826. extent_op->parent = parent;
  1827. extent_op->orig_parent = parent;
  1828. extent_op->generation = ref_generation;
  1829. extent_op->orig_generation = ref_generation;
  1830. extent_op->level = (int)owner_objectid;
  1831. mutex_lock(&root->fs_info->extent_ins_mutex);
  1832. set_extent_bits(&root->fs_info->pending_del,
  1833. bytenr, bytenr + num_bytes - 1,
  1834. EXTENT_WRITEBACK, GFP_NOFS);
  1835. set_state_private(&root->fs_info->pending_del,
  1836. bytenr, (unsigned long)extent_op);
  1837. mutex_unlock(&root->fs_info->extent_ins_mutex);
  1838. return 0;
  1839. }
  1840. /* if metadata always pin */
  1841. if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
  1842. if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
  1843. struct btrfs_block_group_cache *cache;
  1844. /* btrfs_free_reserved_extent */
  1845. cache = btrfs_lookup_block_group(root->fs_info, bytenr);
  1846. BUG_ON(!cache);
  1847. btrfs_add_free_space(cache, bytenr, num_bytes);
  1848. update_reserved_extents(root, bytenr, num_bytes, 0);
  1849. return 0;
  1850. }
  1851. pin = 1;
  1852. }
  1853. /* if data pin when any transaction has committed this */
  1854. if (ref_generation != trans->transid)
  1855. pin = 1;
  1856. ret = __free_extent(trans, root, bytenr, num_bytes, parent,
  1857. root_objectid, ref_generation,
  1858. owner_objectid, pin, pin == 0);
  1859. finish_current_insert(trans, root->fs_info->extent_root, 0);
  1860. pending_ret = del_pending_extents(trans, root->fs_info->extent_root, 0);
  1861. return ret ? ret : pending_ret;
  1862. }
  1863. int btrfs_free_extent(struct btrfs_trans_handle *trans,
  1864. struct btrfs_root *root,
  1865. u64 bytenr, u64 num_bytes, u64 parent,
  1866. u64 root_objectid, u64 ref_generation,
  1867. u64 owner_objectid, int pin)
  1868. {
  1869. int ret;
  1870. ret = __btrfs_free_extent(trans, root, bytenr, num_bytes, parent,
  1871. root_objectid, ref_generation,
  1872. owner_objectid, pin);
  1873. return ret;
  1874. }
  1875. static u64 stripe_align(struct btrfs_root *root, u64 val)
  1876. {
  1877. u64 mask = ((u64)root->stripesize - 1);
  1878. u64 ret = (val + mask) & ~mask;
  1879. return ret;
  1880. }
  1881. /*
  1882. * walks the btree of allocated extents and find a hole of a given size.
  1883. * The key ins is changed to record the hole:
  1884. * ins->objectid == block start
  1885. * ins->flags = BTRFS_EXTENT_ITEM_KEY
  1886. * ins->offset == number of blocks
  1887. * Any available blocks before search_start are skipped.
  1888. */
  1889. static int noinline find_free_extent(struct btrfs_trans_handle *trans,
  1890. struct btrfs_root *orig_root,
  1891. u64 num_bytes, u64 empty_size,
  1892. u64 search_start, u64 search_end,
  1893. u64 hint_byte, struct btrfs_key *ins,
  1894. u64 exclude_start, u64 exclude_nr,
  1895. int data)
  1896. {
  1897. int ret = 0;
  1898. struct btrfs_root * root = orig_root->fs_info->extent_root;
  1899. u64 total_needed = num_bytes;
  1900. u64 *last_ptr = NULL;
  1901. u64 last_wanted = 0;
  1902. struct btrfs_block_group_cache *block_group = NULL;
  1903. int chunk_alloc_done = 0;
  1904. int empty_cluster = 2 * 1024 * 1024;
  1905. int allowed_chunk_alloc = 0;
  1906. struct list_head *head = NULL, *cur = NULL;
  1907. int loop = 0;
  1908. int extra_loop = 0;
  1909. struct btrfs_space_info *space_info;
  1910. WARN_ON(num_bytes < root->sectorsize);
  1911. btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
  1912. ins->objectid = 0;
  1913. ins->offset = 0;
  1914. if (orig_root->ref_cows || empty_size)
  1915. allowed_chunk_alloc = 1;
  1916. if (data & BTRFS_BLOCK_GROUP_METADATA) {
  1917. last_ptr = &root->fs_info->last_alloc;
  1918. empty_cluster = 64 * 1024;
  1919. }
  1920. if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD))
  1921. last_ptr = &root->fs_info->last_data_alloc;
  1922. if (last_ptr) {
  1923. if (*last_ptr) {
  1924. hint_byte = *last_ptr;
  1925. last_wanted = *last_ptr;
  1926. } else
  1927. empty_size += empty_cluster;
  1928. } else {
  1929. empty_cluster = 0;
  1930. }
  1931. search_start = max(search_start, first_logical_byte(root, 0));
  1932. search_start = max(search_start, hint_byte);
  1933. if (last_wanted && search_start != last_wanted) {
  1934. last_wanted = 0;
  1935. empty_size += empty_cluster;
  1936. }
  1937. total_needed += empty_size;
  1938. block_group = btrfs_lookup_block_group(root->fs_info, search_start);
  1939. if (!block_group)
  1940. block_group = btrfs_lookup_first_block_group(root->fs_info,
  1941. search_start);
  1942. space_info = __find_space_info(root->fs_info, data);
  1943. down_read(&space_info->groups_sem);
  1944. while (1) {
  1945. struct btrfs_free_space *free_space;
  1946. /*
  1947. * the only way this happens if our hint points to a block
  1948. * group thats not of the proper type, while looping this
  1949. * should never happen
  1950. */
  1951. if (empty_size)
  1952. extra_loop = 1;
  1953. if (!block_group)
  1954. goto new_group_no_lock;
  1955. mutex_lock(&block_group->alloc_mutex);
  1956. if (unlikely(!block_group_bits(block_group, data)))
  1957. goto new_group;
  1958. ret = cache_block_group(root, block_group);
  1959. if (ret) {
  1960. mutex_unlock(&block_group->alloc_mutex);
  1961. break;
  1962. }
  1963. if (block_group->ro)
  1964. goto new_group;
  1965. free_space = btrfs_find_free_space(block_group, search_start,
  1966. total_needed);
  1967. if (free_space) {
  1968. u64 start = block_group->key.objectid;
  1969. u64 end = block_group->key.objectid +
  1970. block_group->key.offset;
  1971. search_start = stripe_align(root, free_space->offset);
  1972. /* move on to the next group */
  1973. if (search_start + num_bytes >= search_end)
  1974. goto new_group;
  1975. /* move on to the next group */
  1976. if (search_start + num_bytes > end)
  1977. goto new_group;
  1978. if (last_wanted && search_start != last_wanted) {
  1979. total_needed += empty_cluster;
  1980. empty_size += empty_cluster;
  1981. last_wanted = 0;
  1982. /*
  1983. * if search_start is still in this block group
  1984. * then we just re-search this block group
  1985. */
  1986. if (search_start >= start &&
  1987. search_start < end) {
  1988. mutex_unlock(&block_group->alloc_mutex);
  1989. continue;
  1990. }
  1991. /* else we go to the next block group */
  1992. goto new_group;
  1993. }
  1994. if (exclude_nr > 0 &&
  1995. (search_start + num_bytes > exclude_start &&
  1996. search_start < exclude_start + exclude_nr)) {
  1997. search_start = exclude_start + exclude_nr;
  1998. /*
  1999. * if search_start is still in this block group
  2000. * then we just re-search this block group
  2001. */
  2002. if (search_start >= start &&
  2003. search_start < end) {
  2004. mutex_unlock(&block_group->alloc_mutex);
  2005. last_wanted = 0;
  2006. continue;
  2007. }
  2008. /* else we go to the next block group */
  2009. goto new_group;
  2010. }
  2011. ins->objectid = search_start;
  2012. ins->offset = num_bytes;
  2013. btrfs_remove_free_space_lock(block_group, search_start,
  2014. num_bytes);
  2015. /* we are all good, lets return */
  2016. mutex_unlock(&block_group->alloc_mutex);
  2017. break;
  2018. }
  2019. new_group:
  2020. mutex_unlock(&block_group->alloc_mutex);
  2021. new_group_no_lock:
  2022. /* don't try to compare new allocations against the
  2023. * last allocation any more
  2024. */
  2025. last_wanted = 0;
  2026. /*
  2027. * Here's how this works.
  2028. * loop == 0: we were searching a block group via a hint
  2029. * and didn't find anything, so we start at
  2030. * the head of the block groups and keep searching
  2031. * loop == 1: we're searching through all of the block groups
  2032. * if we hit the head again we have searched
  2033. * all of the block groups for this space and we
  2034. * need to try and allocate, if we cant error out.
  2035. * loop == 2: we allocated more space and are looping through
  2036. * all of the block groups again.
  2037. */
  2038. if (loop == 0) {
  2039. head = &space_info->block_groups;
  2040. cur = head->next;
  2041. loop++;
  2042. } else if (loop == 1 && cur == head) {
  2043. int keep_going;
  2044. /* at this point we give up on the empty_size
  2045. * allocations and just try to allocate the min
  2046. * space.
  2047. *
  2048. * The extra_loop field was set if an empty_size
  2049. * allocation was attempted above, and if this
  2050. * is try we need to try the loop again without
  2051. * the additional empty_size.
  2052. */
  2053. total_needed -= empty_size;
  2054. empty_size = 0;
  2055. keep_going = extra_loop;
  2056. loop++;
  2057. if (allowed_chunk_alloc && !chunk_alloc_done) {
  2058. up_read(&space_info->groups_sem);
  2059. ret = do_chunk_alloc(trans, root, num_bytes +
  2060. 2 * 1024 * 1024, data, 1);
  2061. if (ret < 0)
  2062. break;
  2063. down_read(&space_info->groups_sem);
  2064. head = &space_info->block_groups;
  2065. /*
  2066. * we've allocated a new chunk, keep
  2067. * trying
  2068. */
  2069. keep_going = 1;
  2070. chunk_alloc_done = 1;
  2071. } else if (!allowed_chunk_alloc) {
  2072. space_info->force_alloc = 1;
  2073. }
  2074. if (keep_going) {
  2075. cur = head->next;
  2076. extra_loop = 0;
  2077. } else {
  2078. break;
  2079. }
  2080. } else if (cur == head) {
  2081. break;
  2082. }
  2083. block_group = list_entry(cur, struct btrfs_block_group_cache,
  2084. list);
  2085. search_start = block_group->key.objectid;
  2086. cur = cur->next;
  2087. }
  2088. /* we found what we needed */
  2089. if (ins->objectid) {
  2090. if (!(data & BTRFS_BLOCK_GROUP_DATA))
  2091. trans->block_group = block_group;
  2092. if (last_ptr)
  2093. *last_ptr = ins->objectid + ins->offset;
  2094. ret = 0;
  2095. } else if (!ret) {
  2096. ret = -ENOSPC;
  2097. }
  2098. up_read(&space_info->groups_sem);
  2099. return ret;
  2100. }
  2101. static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
  2102. {
  2103. struct btrfs_block_group_cache *cache;
  2104. struct list_head *l;
  2105. printk(KERN_INFO "space_info has %Lu free, is %sfull\n",
  2106. info->total_bytes - info->bytes_used - info->bytes_pinned -
  2107. info->bytes_reserved, (info->full) ? "" : "not ");
  2108. down_read(&info->groups_sem);
  2109. list_for_each(l, &info->block_groups) {
  2110. cache = list_entry(l, struct btrfs_block_group_cache, list);
  2111. spin_lock(&cache->lock);
  2112. printk(KERN_INFO "block group %Lu has %Lu bytes, %Lu used "
  2113. "%Lu pinned %Lu reserved\n",
  2114. cache->key.objectid, cache->key.offset,
  2115. btrfs_block_group_used(&cache->item),
  2116. cache->pinned, cache->reserved);
  2117. btrfs_dump_free_space(cache, bytes);
  2118. spin_unlock(&cache->lock);
  2119. }
  2120. up_read(&info->groups_sem);
  2121. }
  2122. static int __btrfs_reserve_extent(struct btrfs_trans_handle *trans,
  2123. struct btrfs_root *root,
  2124. u64 num_bytes, u64 min_alloc_size,
  2125. u64 empty_size, u64 hint_byte,
  2126. u64 search_end, struct btrfs_key *ins,
  2127. u64 data)
  2128. {
  2129. int ret;
  2130. u64 search_start = 0;
  2131. u64 alloc_profile;
  2132. struct btrfs_fs_info *info = root->fs_info;
  2133. if (data) {
  2134. alloc_profile = info->avail_data_alloc_bits &
  2135. info->data_alloc_profile;
  2136. data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
  2137. } else if (root == root->fs_info->chunk_root) {
  2138. alloc_profile = info->avail_system_alloc_bits &
  2139. info->system_alloc_profile;
  2140. data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
  2141. } else {
  2142. alloc_profile = info->avail_metadata_alloc_bits &
  2143. info->metadata_alloc_profile;
  2144. data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
  2145. }
  2146. again:
  2147. data = reduce_alloc_profile(root, data);
  2148. /*
  2149. * the only place that sets empty_size is btrfs_realloc_node, which
  2150. * is not called recursively on allocations
  2151. */
  2152. if (empty_size || root->ref_cows) {
  2153. if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
  2154. ret = do_chunk_alloc(trans, root->fs_info->extent_root,
  2155. 2 * 1024 * 1024,
  2156. BTRFS_BLOCK_GROUP_METADATA |
  2157. (info->metadata_alloc_profile &
  2158. info->avail_metadata_alloc_bits), 0);
  2159. }
  2160. ret = do_chunk_alloc(trans, root->fs_info->extent_root,
  2161. num_bytes + 2 * 1024 * 1024, data, 0);
  2162. }
  2163. WARN_ON(num_bytes < root->sectorsize);
  2164. ret = find_free_extent(trans, root, num_bytes, empty_size,
  2165. search_start, search_end, hint_byte, ins,
  2166. trans->alloc_exclude_start,
  2167. trans->alloc_exclude_nr, data);
  2168. if (ret == -ENOSPC && num_bytes > min_alloc_size) {
  2169. num_bytes = num_bytes >> 1;
  2170. num_bytes = num_bytes & ~(root->sectorsize - 1);
  2171. num_bytes = max(num_bytes, min_alloc_size);
  2172. do_chunk_alloc(trans, root->fs_info->extent_root,
  2173. num_bytes, data, 1);
  2174. goto again;
  2175. }
  2176. if (ret) {
  2177. struct btrfs_space_info *sinfo;
  2178. sinfo = __find_space_info(root->fs_info, data);
  2179. printk("allocation failed flags %Lu, wanted %Lu\n",
  2180. data, num_bytes);
  2181. dump_space_info(sinfo, num_bytes);
  2182. BUG();
  2183. }
  2184. return ret;
  2185. }
  2186. int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len)
  2187. {
  2188. struct btrfs_block_group_cache *cache;
  2189. cache = btrfs_lookup_block_group(root->fs_info, start);
  2190. if (!cache) {
  2191. printk(KERN_ERR "Unable to find block group for %Lu\n", start);
  2192. return -ENOSPC;
  2193. }
  2194. btrfs_add_free_space(cache, start, len);
  2195. update_reserved_extents(root, start, len, 0);
  2196. return 0;
  2197. }
  2198. int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
  2199. struct btrfs_root *root,
  2200. u64 num_bytes, u64 min_alloc_size,
  2201. u64 empty_size, u64 hint_byte,
  2202. u64 search_end, struct btrfs_key *ins,
  2203. u64 data)
  2204. {
  2205. int ret;
  2206. ret = __btrfs_reserve_extent(trans, root, num_bytes, min_alloc_size,
  2207. empty_size, hint_byte, search_end, ins,
  2208. data);
  2209. update_reserved_extents(root, ins->objectid, ins->offset, 1);
  2210. return ret;
  2211. }
  2212. static int __btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
  2213. struct btrfs_root *root, u64 parent,
  2214. u64 root_objectid, u64 ref_generation,
  2215. u64 owner, struct btrfs_key *ins)
  2216. {
  2217. int ret;
  2218. int pending_ret;
  2219. u64 super_used;
  2220. u64 root_used;
  2221. u64 num_bytes = ins->offset;
  2222. u32 sizes[2];
  2223. struct btrfs_fs_info *info = root->fs_info;
  2224. struct btrfs_root *extent_root = info->extent_root;
  2225. struct btrfs_extent_item *extent_item;
  2226. struct btrfs_extent_ref *ref;
  2227. struct btrfs_path *path;
  2228. struct btrfs_key keys[2];
  2229. if (parent == 0)
  2230. parent = ins->objectid;
  2231. /* block accounting for super block */
  2232. spin_lock_irq(&info->delalloc_lock);
  2233. super_used = btrfs_super_bytes_used(&info->super_copy);
  2234. btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
  2235. spin_unlock_irq(&info->delalloc_lock);
  2236. /* block accounting for root item */
  2237. root_used = btrfs_root_used(&root->root_item);
  2238. btrfs_set_root_used(&root->root_item, root_used + num_bytes);
  2239. if (root == extent_root) {
  2240. struct pending_extent_op *extent_op;
  2241. extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
  2242. BUG_ON(!extent_op);
  2243. extent_op->type = PENDING_EXTENT_INSERT;
  2244. extent_op->bytenr = ins->objectid;
  2245. extent_op->num_bytes = ins->offset;
  2246. extent_op->parent = parent;
  2247. extent_op->orig_parent = 0;
  2248. extent_op->generation = ref_generation;
  2249. extent_op->orig_generation = 0;
  2250. extent_op->level = (int)owner;
  2251. mutex_lock(&root->fs_info->extent_ins_mutex);
  2252. set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
  2253. ins->objectid + ins->offset - 1,
  2254. EXTENT_WRITEBACK, GFP_NOFS);
  2255. set_state_private(&root->fs_info->extent_ins,
  2256. ins->objectid, (unsigned long)extent_op);
  2257. mutex_unlock(&root->fs_info->extent_ins_mutex);
  2258. goto update_block;
  2259. }
  2260. memcpy(&keys[0], ins, sizeof(*ins));
  2261. keys[1].objectid = ins->objectid;
  2262. keys[1].type = BTRFS_EXTENT_REF_KEY;
  2263. keys[1].offset = parent;
  2264. sizes[0] = sizeof(*extent_item);
  2265. sizes[1] = sizeof(*ref);
  2266. path = btrfs_alloc_path();
  2267. BUG_ON(!path);
  2268. ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
  2269. sizes, 2);
  2270. BUG_ON(ret);
  2271. extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
  2272. struct btrfs_extent_item);
  2273. btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
  2274. ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
  2275. struct btrfs_extent_ref);
  2276. btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
  2277. btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
  2278. btrfs_set_ref_objectid(path->nodes[0], ref, owner);
  2279. btrfs_set_ref_num_refs(path->nodes[0], ref, 1);
  2280. btrfs_mark_buffer_dirty(path->nodes[0]);
  2281. trans->alloc_exclude_start = 0;
  2282. trans->alloc_exclude_nr = 0;
  2283. btrfs_free_path(path);
  2284. finish_current_insert(trans, extent_root, 0);
  2285. pending_ret = del_pending_extents(trans, extent_root, 0);
  2286. if (ret)
  2287. goto out;
  2288. if (pending_ret) {
  2289. ret = pending_ret;
  2290. goto out;
  2291. }
  2292. update_block:
  2293. ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
  2294. if (ret) {
  2295. printk("update block group failed for %Lu %Lu\n",
  2296. ins->objectid, ins->offset);
  2297. BUG();
  2298. }
  2299. out:
  2300. return ret;
  2301. }
  2302. int btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
  2303. struct btrfs_root *root, u64 parent,
  2304. u64 root_objectid, u64 ref_generation,
  2305. u64 owner, struct btrfs_key *ins)
  2306. {
  2307. int ret;
  2308. if (root_objectid == BTRFS_TREE_LOG_OBJECTID)
  2309. return 0;
  2310. ret = __btrfs_alloc_reserved_extent(trans, root, parent, root_objectid,
  2311. ref_generation, owner, ins);
  2312. update_reserved_extents(root, ins->objectid, ins->offset, 0);
  2313. return ret;
  2314. }
  2315. /*
  2316. * this is used by the tree logging recovery code. It records that
  2317. * an extent has been allocated and makes sure to clear the free
  2318. * space cache bits as well
  2319. */
  2320. int btrfs_alloc_logged_extent(struct btrfs_trans_handle *trans,
  2321. struct btrfs_root *root, u64 parent,
  2322. u64 root_objectid, u64 ref_generation,
  2323. u64 owner, struct btrfs_key *ins)
  2324. {
  2325. int ret;
  2326. struct btrfs_block_group_cache *block_group;
  2327. block_group = btrfs_lookup_block_group(root->fs_info, ins->objectid);
  2328. mutex_lock(&block_group->alloc_mutex);
  2329. cache_block_group(root, block_group);
  2330. ret = btrfs_remove_free_space_lock(block_group, ins->objectid,
  2331. ins->offset);
  2332. mutex_unlock(&block_group->alloc_mutex);
  2333. BUG_ON(ret);
  2334. ret = __btrfs_alloc_reserved_extent(trans, root, parent, root_objectid,
  2335. ref_generation, owner, ins);
  2336. return ret;
  2337. }
  2338. /*
  2339. * finds a free extent and does all the dirty work required for allocation
  2340. * returns the key for the extent through ins, and a tree buffer for
  2341. * the first block of the extent through buf.
  2342. *
  2343. * returns 0 if everything worked, non-zero otherwise.
  2344. */
  2345. int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
  2346. struct btrfs_root *root,
  2347. u64 num_bytes, u64 parent, u64 min_alloc_size,
  2348. u64 root_objectid, u64 ref_generation,
  2349. u64 owner_objectid, u64 empty_size, u64 hint_byte,
  2350. u64 search_end, struct btrfs_key *ins, u64 data)
  2351. {
  2352. int ret;
  2353. ret = __btrfs_reserve_extent(trans, root, num_bytes,
  2354. min_alloc_size, empty_size, hint_byte,
  2355. search_end, ins, data);
  2356. BUG_ON(ret);
  2357. if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
  2358. ret = __btrfs_alloc_reserved_extent(trans, root, parent,
  2359. root_objectid, ref_generation,
  2360. owner_objectid, ins);
  2361. BUG_ON(ret);
  2362. } else {
  2363. update_reserved_extents(root, ins->objectid, ins->offset, 1);
  2364. }
  2365. return ret;
  2366. }
  2367. struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
  2368. struct btrfs_root *root,
  2369. u64 bytenr, u32 blocksize)
  2370. {
  2371. struct extent_buffer *buf;
  2372. buf = btrfs_find_create_tree_block(root, bytenr, blocksize);
  2373. if (!buf)
  2374. return ERR_PTR(-ENOMEM);
  2375. btrfs_set_header_generation(buf, trans->transid);
  2376. btrfs_tree_lock(buf);
  2377. clean_tree_block(trans, root, buf);
  2378. btrfs_set_buffer_uptodate(buf);
  2379. if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
  2380. set_extent_dirty(&root->dirty_log_pages, buf->start,
  2381. buf->start + buf->len - 1, GFP_NOFS);
  2382. } else {
  2383. set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
  2384. buf->start + buf->len - 1, GFP_NOFS);
  2385. }
  2386. trans->blocks_used++;
  2387. return buf;
  2388. }
  2389. /*
  2390. * helper function to allocate a block for a given tree
  2391. * returns the tree buffer or NULL.
  2392. */
  2393. struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
  2394. struct btrfs_root *root,
  2395. u32 blocksize, u64 parent,
  2396. u64 root_objectid,
  2397. u64 ref_generation,
  2398. int level,
  2399. u64 hint,
  2400. u64 empty_size)
  2401. {
  2402. struct btrfs_key ins;
  2403. int ret;
  2404. struct extent_buffer *buf;
  2405. ret = btrfs_alloc_extent(trans, root, blocksize, parent, blocksize,
  2406. root_objectid, ref_generation, level,
  2407. empty_size, hint, (u64)-1, &ins, 0);
  2408. if (ret) {
  2409. BUG_ON(ret > 0);
  2410. return ERR_PTR(ret);
  2411. }
  2412. buf = btrfs_init_new_buffer(trans, root, ins.objectid, blocksize);
  2413. return buf;
  2414. }
  2415. int btrfs_drop_leaf_ref(struct btrfs_trans_handle *trans,
  2416. struct btrfs_root *root, struct extent_buffer *leaf)
  2417. {
  2418. u64 leaf_owner;
  2419. u64 leaf_generation;
  2420. struct btrfs_key key;
  2421. struct btrfs_file_extent_item *fi;
  2422. int i;
  2423. int nritems;
  2424. int ret;
  2425. BUG_ON(!btrfs_is_leaf(leaf));
  2426. nritems = btrfs_header_nritems(leaf);
  2427. leaf_owner = btrfs_header_owner(leaf);
  2428. leaf_generation = btrfs_header_generation(leaf);
  2429. for (i = 0; i < nritems; i++) {
  2430. u64 disk_bytenr;
  2431. cond_resched();
  2432. btrfs_item_key_to_cpu(leaf, &key, i);
  2433. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  2434. continue;
  2435. fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
  2436. if (btrfs_file_extent_type(leaf, fi) ==
  2437. BTRFS_FILE_EXTENT_INLINE)
  2438. continue;
  2439. /*
  2440. * FIXME make sure to insert a trans record that
  2441. * repeats the snapshot del on crash
  2442. */
  2443. disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
  2444. if (disk_bytenr == 0)
  2445. continue;
  2446. ret = __btrfs_free_extent(trans, root, disk_bytenr,
  2447. btrfs_file_extent_disk_num_bytes(leaf, fi),
  2448. leaf->start, leaf_owner, leaf_generation,
  2449. key.objectid, 0);
  2450. BUG_ON(ret);
  2451. atomic_inc(&root->fs_info->throttle_gen);
  2452. wake_up(&root->fs_info->transaction_throttle);
  2453. cond_resched();
  2454. }
  2455. return 0;
  2456. }
  2457. static int noinline cache_drop_leaf_ref(struct btrfs_trans_handle *trans,
  2458. struct btrfs_root *root,
  2459. struct btrfs_leaf_ref *ref)
  2460. {
  2461. int i;
  2462. int ret;
  2463. struct btrfs_extent_info *info = ref->extents;
  2464. for (i = 0; i < ref->nritems; i++) {
  2465. ret = __btrfs_free_extent(trans, root, info->bytenr,
  2466. info->num_bytes, ref->bytenr,
  2467. ref->owner, ref->generation,
  2468. info->objectid, 0);
  2469. atomic_inc(&root->fs_info->throttle_gen);
  2470. wake_up(&root->fs_info->transaction_throttle);
  2471. cond_resched();
  2472. BUG_ON(ret);
  2473. info++;
  2474. }
  2475. return 0;
  2476. }
  2477. int drop_snap_lookup_refcount(struct btrfs_root *root, u64 start, u64 len,
  2478. u32 *refs)
  2479. {
  2480. int ret;
  2481. ret = btrfs_lookup_extent_ref(NULL, root, start, len, refs);
  2482. BUG_ON(ret);
  2483. #if 0 // some debugging code in case we see problems here
  2484. /* if the refs count is one, it won't get increased again. But
  2485. * if the ref count is > 1, someone may be decreasing it at
  2486. * the same time we are.
  2487. */
  2488. if (*refs != 1) {
  2489. struct extent_buffer *eb = NULL;
  2490. eb = btrfs_find_create_tree_block(root, start, len);
  2491. if (eb)
  2492. btrfs_tree_lock(eb);
  2493. mutex_lock(&root->fs_info->alloc_mutex);
  2494. ret = lookup_extent_ref(NULL, root, start, len, refs);
  2495. BUG_ON(ret);
  2496. mutex_unlock(&root->fs_info->alloc_mutex);
  2497. if (eb) {
  2498. btrfs_tree_unlock(eb);
  2499. free_extent_buffer(eb);
  2500. }
  2501. if (*refs == 1) {
  2502. printk("block %llu went down to one during drop_snap\n",
  2503. (unsigned long long)start);
  2504. }
  2505. }
  2506. #endif
  2507. cond_resched();
  2508. return ret;
  2509. }
  2510. /*
  2511. * helper function for drop_snapshot, this walks down the tree dropping ref
  2512. * counts as it goes.
  2513. */
  2514. static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
  2515. struct btrfs_root *root,
  2516. struct btrfs_path *path, int *level)
  2517. {
  2518. u64 root_owner;
  2519. u64 root_gen;
  2520. u64 bytenr;
  2521. u64 ptr_gen;
  2522. struct extent_buffer *next;
  2523. struct extent_buffer *cur;
  2524. struct extent_buffer *parent;
  2525. struct btrfs_leaf_ref *ref;
  2526. u32 blocksize;
  2527. int ret;
  2528. u32 refs;
  2529. WARN_ON(*level < 0);
  2530. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  2531. ret = drop_snap_lookup_refcount(root, path->nodes[*level]->start,
  2532. path->nodes[*level]->len, &refs);
  2533. BUG_ON(ret);
  2534. if (refs > 1)
  2535. goto out;
  2536. /*
  2537. * walk down to the last node level and free all the leaves
  2538. */
  2539. while(*level >= 0) {
  2540. WARN_ON(*level < 0);
  2541. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  2542. cur = path->nodes[*level];
  2543. if (btrfs_header_level(cur) != *level)
  2544. WARN_ON(1);
  2545. if (path->slots[*level] >=
  2546. btrfs_header_nritems(cur))
  2547. break;
  2548. if (*level == 0) {
  2549. ret = btrfs_drop_leaf_ref(trans, root, cur);
  2550. BUG_ON(ret);
  2551. break;
  2552. }
  2553. bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
  2554. ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
  2555. blocksize = btrfs_level_size(root, *level - 1);
  2556. ret = drop_snap_lookup_refcount(root, bytenr, blocksize, &refs);
  2557. BUG_ON(ret);
  2558. if (refs != 1) {
  2559. parent = path->nodes[*level];
  2560. root_owner = btrfs_header_owner(parent);
  2561. root_gen = btrfs_header_generation(parent);
  2562. path->slots[*level]++;
  2563. ret = __btrfs_free_extent(trans, root, bytenr,
  2564. blocksize, parent->start,
  2565. root_owner, root_gen,
  2566. *level - 1, 1);
  2567. BUG_ON(ret);
  2568. atomic_inc(&root->fs_info->throttle_gen);
  2569. wake_up(&root->fs_info->transaction_throttle);
  2570. cond_resched();
  2571. continue;
  2572. }
  2573. /*
  2574. * at this point, we have a single ref, and since the
  2575. * only place referencing this extent is a dead root
  2576. * the reference count should never go higher.
  2577. * So, we don't need to check it again
  2578. */
  2579. if (*level == 1) {
  2580. ref = btrfs_lookup_leaf_ref(root, bytenr);
  2581. if (ref && ref->generation != ptr_gen) {
  2582. btrfs_free_leaf_ref(root, ref);
  2583. ref = NULL;
  2584. }
  2585. if (ref) {
  2586. ret = cache_drop_leaf_ref(trans, root, ref);
  2587. BUG_ON(ret);
  2588. btrfs_remove_leaf_ref(root, ref);
  2589. btrfs_free_leaf_ref(root, ref);
  2590. *level = 0;
  2591. break;
  2592. }
  2593. if (printk_ratelimit()) {
  2594. printk("leaf ref miss for bytenr %llu\n",
  2595. (unsigned long long)bytenr);
  2596. }
  2597. }
  2598. next = btrfs_find_tree_block(root, bytenr, blocksize);
  2599. if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
  2600. free_extent_buffer(next);
  2601. next = read_tree_block(root, bytenr, blocksize,
  2602. ptr_gen);
  2603. cond_resched();
  2604. #if 0
  2605. /*
  2606. * this is a debugging check and can go away
  2607. * the ref should never go all the way down to 1
  2608. * at this point
  2609. */
  2610. ret = lookup_extent_ref(NULL, root, bytenr, blocksize,
  2611. &refs);
  2612. BUG_ON(ret);
  2613. WARN_ON(refs != 1);
  2614. #endif
  2615. }
  2616. WARN_ON(*level <= 0);
  2617. if (path->nodes[*level-1])
  2618. free_extent_buffer(path->nodes[*level-1]);
  2619. path->nodes[*level-1] = next;
  2620. *level = btrfs_header_level(next);
  2621. path->slots[*level] = 0;
  2622. cond_resched();
  2623. }
  2624. out:
  2625. WARN_ON(*level < 0);
  2626. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  2627. if (path->nodes[*level] == root->node) {
  2628. parent = path->nodes[*level];
  2629. bytenr = path->nodes[*level]->start;
  2630. } else {
  2631. parent = path->nodes[*level + 1];
  2632. bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
  2633. }
  2634. blocksize = btrfs_level_size(root, *level);
  2635. root_owner = btrfs_header_owner(parent);
  2636. root_gen = btrfs_header_generation(parent);
  2637. ret = __btrfs_free_extent(trans, root, bytenr, blocksize,
  2638. parent->start, root_owner, root_gen,
  2639. *level, 1);
  2640. free_extent_buffer(path->nodes[*level]);
  2641. path->nodes[*level] = NULL;
  2642. *level += 1;
  2643. BUG_ON(ret);
  2644. cond_resched();
  2645. return 0;
  2646. }
  2647. /*
  2648. * helper function for drop_subtree, this function is similar to
  2649. * walk_down_tree. The main difference is that it checks reference
  2650. * counts while tree blocks are locked.
  2651. */
  2652. static int noinline walk_down_subtree(struct btrfs_trans_handle *trans,
  2653. struct btrfs_root *root,
  2654. struct btrfs_path *path, int *level)
  2655. {
  2656. struct extent_buffer *next;
  2657. struct extent_buffer *cur;
  2658. struct extent_buffer *parent;
  2659. u64 bytenr;
  2660. u64 ptr_gen;
  2661. u32 blocksize;
  2662. u32 refs;
  2663. int ret;
  2664. cur = path->nodes[*level];
  2665. ret = btrfs_lookup_extent_ref(trans, root, cur->start, cur->len,
  2666. &refs);
  2667. BUG_ON(ret);
  2668. if (refs > 1)
  2669. goto out;
  2670. while (*level >= 0) {
  2671. cur = path->nodes[*level];
  2672. if (*level == 0) {
  2673. ret = btrfs_drop_leaf_ref(trans, root, cur);
  2674. BUG_ON(ret);
  2675. clean_tree_block(trans, root, cur);
  2676. break;
  2677. }
  2678. if (path->slots[*level] >= btrfs_header_nritems(cur)) {
  2679. clean_tree_block(trans, root, cur);
  2680. break;
  2681. }
  2682. bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
  2683. blocksize = btrfs_level_size(root, *level - 1);
  2684. ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
  2685. next = read_tree_block(root, bytenr, blocksize, ptr_gen);
  2686. btrfs_tree_lock(next);
  2687. ret = btrfs_lookup_extent_ref(trans, root, bytenr, blocksize,
  2688. &refs);
  2689. BUG_ON(ret);
  2690. if (refs > 1) {
  2691. parent = path->nodes[*level];
  2692. ret = btrfs_free_extent(trans, root, bytenr,
  2693. blocksize, parent->start,
  2694. btrfs_header_owner(parent),
  2695. btrfs_header_generation(parent),
  2696. *level - 1, 1);
  2697. BUG_ON(ret);
  2698. path->slots[*level]++;
  2699. btrfs_tree_unlock(next);
  2700. free_extent_buffer(next);
  2701. continue;
  2702. }
  2703. *level = btrfs_header_level(next);
  2704. path->nodes[*level] = next;
  2705. path->slots[*level] = 0;
  2706. path->locks[*level] = 1;
  2707. cond_resched();
  2708. }
  2709. out:
  2710. parent = path->nodes[*level + 1];
  2711. bytenr = path->nodes[*level]->start;
  2712. blocksize = path->nodes[*level]->len;
  2713. ret = btrfs_free_extent(trans, root, bytenr, blocksize,
  2714. parent->start, btrfs_header_owner(parent),
  2715. btrfs_header_generation(parent), *level, 1);
  2716. BUG_ON(ret);
  2717. if (path->locks[*level]) {
  2718. btrfs_tree_unlock(path->nodes[*level]);
  2719. path->locks[*level] = 0;
  2720. }
  2721. free_extent_buffer(path->nodes[*level]);
  2722. path->nodes[*level] = NULL;
  2723. *level += 1;
  2724. cond_resched();
  2725. return 0;
  2726. }
  2727. /*
  2728. * helper for dropping snapshots. This walks back up the tree in the path
  2729. * to find the first node higher up where we haven't yet gone through
  2730. * all the slots
  2731. */
  2732. static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
  2733. struct btrfs_root *root,
  2734. struct btrfs_path *path,
  2735. int *level, int max_level)
  2736. {
  2737. u64 root_owner;
  2738. u64 root_gen;
  2739. struct btrfs_root_item *root_item = &root->root_item;
  2740. int i;
  2741. int slot;
  2742. int ret;
  2743. for (i = *level; i < max_level && path->nodes[i]; i++) {
  2744. slot = path->slots[i];
  2745. if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
  2746. struct extent_buffer *node;
  2747. struct btrfs_disk_key disk_key;
  2748. node = path->nodes[i];
  2749. path->slots[i]++;
  2750. *level = i;
  2751. WARN_ON(*level == 0);
  2752. btrfs_node_key(node, &disk_key, path->slots[i]);
  2753. memcpy(&root_item->drop_progress,
  2754. &disk_key, sizeof(disk_key));
  2755. root_item->drop_level = i;
  2756. return 0;
  2757. } else {
  2758. struct extent_buffer *parent;
  2759. if (path->nodes[*level] == root->node)
  2760. parent = path->nodes[*level];
  2761. else
  2762. parent = path->nodes[*level + 1];
  2763. root_owner = btrfs_header_owner(parent);
  2764. root_gen = btrfs_header_generation(parent);
  2765. clean_tree_block(trans, root, path->nodes[*level]);
  2766. ret = btrfs_free_extent(trans, root,
  2767. path->nodes[*level]->start,
  2768. path->nodes[*level]->len,
  2769. parent->start, root_owner,
  2770. root_gen, *level, 1);
  2771. BUG_ON(ret);
  2772. if (path->locks[*level]) {
  2773. btrfs_tree_unlock(path->nodes[*level]);
  2774. path->locks[*level] = 0;
  2775. }
  2776. free_extent_buffer(path->nodes[*level]);
  2777. path->nodes[*level] = NULL;
  2778. *level = i + 1;
  2779. }
  2780. }
  2781. return 1;
  2782. }
  2783. /*
  2784. * drop the reference count on the tree rooted at 'snap'. This traverses
  2785. * the tree freeing any blocks that have a ref count of zero after being
  2786. * decremented.
  2787. */
  2788. int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
  2789. *root)
  2790. {
  2791. int ret = 0;
  2792. int wret;
  2793. int level;
  2794. struct btrfs_path *path;
  2795. int i;
  2796. int orig_level;
  2797. struct btrfs_root_item *root_item = &root->root_item;
  2798. WARN_ON(!mutex_is_locked(&root->fs_info->drop_mutex));
  2799. path = btrfs_alloc_path();
  2800. BUG_ON(!path);
  2801. level = btrfs_header_level(root->node);
  2802. orig_level = level;
  2803. if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
  2804. path->nodes[level] = root->node;
  2805. extent_buffer_get(root->node);
  2806. path->slots[level] = 0;
  2807. } else {
  2808. struct btrfs_key key;
  2809. struct btrfs_disk_key found_key;
  2810. struct extent_buffer *node;
  2811. btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
  2812. level = root_item->drop_level;
  2813. path->lowest_level = level;
  2814. wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  2815. if (wret < 0) {
  2816. ret = wret;
  2817. goto out;
  2818. }
  2819. node = path->nodes[level];
  2820. btrfs_node_key(node, &found_key, path->slots[level]);
  2821. WARN_ON(memcmp(&found_key, &root_item->drop_progress,
  2822. sizeof(found_key)));
  2823. /*
  2824. * unlock our path, this is safe because only this
  2825. * function is allowed to delete this snapshot
  2826. */
  2827. for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  2828. if (path->nodes[i] && path->locks[i]) {
  2829. path->locks[i] = 0;
  2830. btrfs_tree_unlock(path->nodes[i]);
  2831. }
  2832. }
  2833. }
  2834. while(1) {
  2835. wret = walk_down_tree(trans, root, path, &level);
  2836. if (wret > 0)
  2837. break;
  2838. if (wret < 0)
  2839. ret = wret;
  2840. wret = walk_up_tree(trans, root, path, &level,
  2841. BTRFS_MAX_LEVEL);
  2842. if (wret > 0)
  2843. break;
  2844. if (wret < 0)
  2845. ret = wret;
  2846. if (trans->transaction->in_commit) {
  2847. ret = -EAGAIN;
  2848. break;
  2849. }
  2850. atomic_inc(&root->fs_info->throttle_gen);
  2851. wake_up(&root->fs_info->transaction_throttle);
  2852. }
  2853. for (i = 0; i <= orig_level; i++) {
  2854. if (path->nodes[i]) {
  2855. free_extent_buffer(path->nodes[i]);
  2856. path->nodes[i] = NULL;
  2857. }
  2858. }
  2859. out:
  2860. btrfs_free_path(path);
  2861. return ret;
  2862. }
  2863. int btrfs_drop_subtree(struct btrfs_trans_handle *trans,
  2864. struct btrfs_root *root,
  2865. struct extent_buffer *node,
  2866. struct extent_buffer *parent)
  2867. {
  2868. struct btrfs_path *path;
  2869. int level;
  2870. int parent_level;
  2871. int ret = 0;
  2872. int wret;
  2873. path = btrfs_alloc_path();
  2874. BUG_ON(!path);
  2875. BUG_ON(!btrfs_tree_locked(parent));
  2876. parent_level = btrfs_header_level(parent);
  2877. extent_buffer_get(parent);
  2878. path->nodes[parent_level] = parent;
  2879. path->slots[parent_level] = btrfs_header_nritems(parent);
  2880. BUG_ON(!btrfs_tree_locked(node));
  2881. level = btrfs_header_level(node);
  2882. extent_buffer_get(node);
  2883. path->nodes[level] = node;
  2884. path->slots[level] = 0;
  2885. while (1) {
  2886. wret = walk_down_subtree(trans, root, path, &level);
  2887. if (wret < 0)
  2888. ret = wret;
  2889. if (wret != 0)
  2890. break;
  2891. wret = walk_up_tree(trans, root, path, &level, parent_level);
  2892. if (wret < 0)
  2893. ret = wret;
  2894. if (wret != 0)
  2895. break;
  2896. }
  2897. btrfs_free_path(path);
  2898. return ret;
  2899. }
  2900. static unsigned long calc_ra(unsigned long start, unsigned long last,
  2901. unsigned long nr)
  2902. {
  2903. return min(last, start + nr - 1);
  2904. }
  2905. static int noinline relocate_inode_pages(struct inode *inode, u64 start,
  2906. u64 len)
  2907. {
  2908. u64 page_start;
  2909. u64 page_end;
  2910. unsigned long first_index;
  2911. unsigned long last_index;
  2912. unsigned long i;
  2913. struct page *page;
  2914. struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
  2915. struct file_ra_state *ra;
  2916. struct btrfs_ordered_extent *ordered;
  2917. unsigned int total_read = 0;
  2918. unsigned int total_dirty = 0;
  2919. int ret = 0;
  2920. ra = kzalloc(sizeof(*ra), GFP_NOFS);
  2921. mutex_lock(&inode->i_mutex);
  2922. first_index = start >> PAGE_CACHE_SHIFT;
  2923. last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
  2924. /* make sure the dirty trick played by the caller work */
  2925. ret = invalidate_inode_pages2_range(inode->i_mapping,
  2926. first_index, last_index);
  2927. if (ret)
  2928. goto out_unlock;
  2929. file_ra_state_init(ra, inode->i_mapping);
  2930. for (i = first_index ; i <= last_index; i++) {
  2931. if (total_read % ra->ra_pages == 0) {
  2932. btrfs_force_ra(inode->i_mapping, ra, NULL, i,
  2933. calc_ra(i, last_index, ra->ra_pages));
  2934. }
  2935. total_read++;
  2936. again:
  2937. if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
  2938. BUG_ON(1);
  2939. page = grab_cache_page(inode->i_mapping, i);
  2940. if (!page) {
  2941. ret = -ENOMEM;
  2942. goto out_unlock;
  2943. }
  2944. if (!PageUptodate(page)) {
  2945. btrfs_readpage(NULL, page);
  2946. lock_page(page);
  2947. if (!PageUptodate(page)) {
  2948. unlock_page(page);
  2949. page_cache_release(page);
  2950. ret = -EIO;
  2951. goto out_unlock;
  2952. }
  2953. }
  2954. wait_on_page_writeback(page);
  2955. page_start = (u64)page->index << PAGE_CACHE_SHIFT;
  2956. page_end = page_start + PAGE_CACHE_SIZE - 1;
  2957. lock_extent(io_tree, page_start, page_end, GFP_NOFS);
  2958. ordered = btrfs_lookup_ordered_extent(inode, page_start);
  2959. if (ordered) {
  2960. unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
  2961. unlock_page(page);
  2962. page_cache_release(page);
  2963. btrfs_start_ordered_extent(inode, ordered, 1);
  2964. btrfs_put_ordered_extent(ordered);
  2965. goto again;
  2966. }
  2967. set_page_extent_mapped(page);
  2968. btrfs_set_extent_delalloc(inode, page_start, page_end);
  2969. if (i == first_index)
  2970. set_extent_bits(io_tree, page_start, page_end,
  2971. EXTENT_BOUNDARY, GFP_NOFS);
  2972. set_page_dirty(page);
  2973. total_dirty++;
  2974. unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
  2975. unlock_page(page);
  2976. page_cache_release(page);
  2977. }
  2978. out_unlock:
  2979. kfree(ra);
  2980. mutex_unlock(&inode->i_mutex);
  2981. balance_dirty_pages_ratelimited_nr(inode->i_mapping, total_dirty);
  2982. return ret;
  2983. }
  2984. static int noinline relocate_data_extent(struct inode *reloc_inode,
  2985. struct btrfs_key *extent_key,
  2986. u64 offset)
  2987. {
  2988. struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
  2989. struct extent_map_tree *em_tree = &BTRFS_I(reloc_inode)->extent_tree;
  2990. struct extent_map *em;
  2991. u64 start = extent_key->objectid - offset;
  2992. u64 end = start + extent_key->offset - 1;
  2993. em = alloc_extent_map(GFP_NOFS);
  2994. BUG_ON(!em || IS_ERR(em));
  2995. em->start = start;
  2996. em->len = extent_key->offset;
  2997. em->block_len = extent_key->offset;
  2998. em->block_start = extent_key->objectid;
  2999. em->bdev = root->fs_info->fs_devices->latest_bdev;
  3000. set_bit(EXTENT_FLAG_PINNED, &em->flags);
  3001. /* setup extent map to cheat btrfs_readpage */
  3002. lock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
  3003. while (1) {
  3004. int ret;
  3005. spin_lock(&em_tree->lock);
  3006. ret = add_extent_mapping(em_tree, em);
  3007. spin_unlock(&em_tree->lock);
  3008. if (ret != -EEXIST) {
  3009. free_extent_map(em);
  3010. break;
  3011. }
  3012. btrfs_drop_extent_cache(reloc_inode, start, end, 0);
  3013. }
  3014. unlock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
  3015. return relocate_inode_pages(reloc_inode, start, extent_key->offset);
  3016. }
  3017. struct btrfs_ref_path {
  3018. u64 extent_start;
  3019. u64 nodes[BTRFS_MAX_LEVEL];
  3020. u64 root_objectid;
  3021. u64 root_generation;
  3022. u64 owner_objectid;
  3023. u32 num_refs;
  3024. int lowest_level;
  3025. int current_level;
  3026. int shared_level;
  3027. struct btrfs_key node_keys[BTRFS_MAX_LEVEL];
  3028. u64 new_nodes[BTRFS_MAX_LEVEL];
  3029. };
  3030. struct disk_extent {
  3031. u64 ram_bytes;
  3032. u64 disk_bytenr;
  3033. u64 disk_num_bytes;
  3034. u64 offset;
  3035. u64 num_bytes;
  3036. u8 compression;
  3037. u8 encryption;
  3038. u16 other_encoding;
  3039. };
  3040. static int is_cowonly_root(u64 root_objectid)
  3041. {
  3042. if (root_objectid == BTRFS_ROOT_TREE_OBJECTID ||
  3043. root_objectid == BTRFS_EXTENT_TREE_OBJECTID ||
  3044. root_objectid == BTRFS_CHUNK_TREE_OBJECTID ||
  3045. root_objectid == BTRFS_DEV_TREE_OBJECTID ||
  3046. root_objectid == BTRFS_TREE_LOG_OBJECTID)
  3047. return 1;
  3048. return 0;
  3049. }
  3050. static int noinline __next_ref_path(struct btrfs_trans_handle *trans,
  3051. struct btrfs_root *extent_root,
  3052. struct btrfs_ref_path *ref_path,
  3053. int first_time)
  3054. {
  3055. struct extent_buffer *leaf;
  3056. struct btrfs_path *path;
  3057. struct btrfs_extent_ref *ref;
  3058. struct btrfs_key key;
  3059. struct btrfs_key found_key;
  3060. u64 bytenr;
  3061. u32 nritems;
  3062. int level;
  3063. int ret = 1;
  3064. path = btrfs_alloc_path();
  3065. if (!path)
  3066. return -ENOMEM;
  3067. if (first_time) {
  3068. ref_path->lowest_level = -1;
  3069. ref_path->current_level = -1;
  3070. ref_path->shared_level = -1;
  3071. goto walk_up;
  3072. }
  3073. walk_down:
  3074. level = ref_path->current_level - 1;
  3075. while (level >= -1) {
  3076. u64 parent;
  3077. if (level < ref_path->lowest_level)
  3078. break;
  3079. if (level >= 0) {
  3080. bytenr = ref_path->nodes[level];
  3081. } else {
  3082. bytenr = ref_path->extent_start;
  3083. }
  3084. BUG_ON(bytenr == 0);
  3085. parent = ref_path->nodes[level + 1];
  3086. ref_path->nodes[level + 1] = 0;
  3087. ref_path->current_level = level;
  3088. BUG_ON(parent == 0);
  3089. key.objectid = bytenr;
  3090. key.offset = parent + 1;
  3091. key.type = BTRFS_EXTENT_REF_KEY;
  3092. ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
  3093. if (ret < 0)
  3094. goto out;
  3095. BUG_ON(ret == 0);
  3096. leaf = path->nodes[0];
  3097. nritems = btrfs_header_nritems(leaf);
  3098. if (path->slots[0] >= nritems) {
  3099. ret = btrfs_next_leaf(extent_root, path);
  3100. if (ret < 0)
  3101. goto out;
  3102. if (ret > 0)
  3103. goto next;
  3104. leaf = path->nodes[0];
  3105. }
  3106. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  3107. if (found_key.objectid == bytenr &&
  3108. found_key.type == BTRFS_EXTENT_REF_KEY) {
  3109. if (level < ref_path->shared_level)
  3110. ref_path->shared_level = level;
  3111. goto found;
  3112. }
  3113. next:
  3114. level--;
  3115. btrfs_release_path(extent_root, path);
  3116. cond_resched();
  3117. }
  3118. /* reached lowest level */
  3119. ret = 1;
  3120. goto out;
  3121. walk_up:
  3122. level = ref_path->current_level;
  3123. while (level < BTRFS_MAX_LEVEL - 1) {
  3124. u64 ref_objectid;
  3125. if (level >= 0) {
  3126. bytenr = ref_path->nodes[level];
  3127. } else {
  3128. bytenr = ref_path->extent_start;
  3129. }
  3130. BUG_ON(bytenr == 0);
  3131. key.objectid = bytenr;
  3132. key.offset = 0;
  3133. key.type = BTRFS_EXTENT_REF_KEY;
  3134. ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
  3135. if (ret < 0)
  3136. goto out;
  3137. leaf = path->nodes[0];
  3138. nritems = btrfs_header_nritems(leaf);
  3139. if (path->slots[0] >= nritems) {
  3140. ret = btrfs_next_leaf(extent_root, path);
  3141. if (ret < 0)
  3142. goto out;
  3143. if (ret > 0) {
  3144. /* the extent was freed by someone */
  3145. if (ref_path->lowest_level == level)
  3146. goto out;
  3147. btrfs_release_path(extent_root, path);
  3148. goto walk_down;
  3149. }
  3150. leaf = path->nodes[0];
  3151. }
  3152. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  3153. if (found_key.objectid != bytenr ||
  3154. found_key.type != BTRFS_EXTENT_REF_KEY) {
  3155. /* the extent was freed by someone */
  3156. if (ref_path->lowest_level == level) {
  3157. ret = 1;
  3158. goto out;
  3159. }
  3160. btrfs_release_path(extent_root, path);
  3161. goto walk_down;
  3162. }
  3163. found:
  3164. ref = btrfs_item_ptr(leaf, path->slots[0],
  3165. struct btrfs_extent_ref);
  3166. ref_objectid = btrfs_ref_objectid(leaf, ref);
  3167. if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID) {
  3168. if (first_time) {
  3169. level = (int)ref_objectid;
  3170. BUG_ON(level >= BTRFS_MAX_LEVEL);
  3171. ref_path->lowest_level = level;
  3172. ref_path->current_level = level;
  3173. ref_path->nodes[level] = bytenr;
  3174. } else {
  3175. WARN_ON(ref_objectid != level);
  3176. }
  3177. } else {
  3178. WARN_ON(level != -1);
  3179. }
  3180. first_time = 0;
  3181. if (ref_path->lowest_level == level) {
  3182. ref_path->owner_objectid = ref_objectid;
  3183. ref_path->num_refs = btrfs_ref_num_refs(leaf, ref);
  3184. }
  3185. /*
  3186. * the block is tree root or the block isn't in reference
  3187. * counted tree.
  3188. */
  3189. if (found_key.objectid == found_key.offset ||
  3190. is_cowonly_root(btrfs_ref_root(leaf, ref))) {
  3191. ref_path->root_objectid = btrfs_ref_root(leaf, ref);
  3192. ref_path->root_generation =
  3193. btrfs_ref_generation(leaf, ref);
  3194. if (level < 0) {
  3195. /* special reference from the tree log */
  3196. ref_path->nodes[0] = found_key.offset;
  3197. ref_path->current_level = 0;
  3198. }
  3199. ret = 0;
  3200. goto out;
  3201. }
  3202. level++;
  3203. BUG_ON(ref_path->nodes[level] != 0);
  3204. ref_path->nodes[level] = found_key.offset;
  3205. ref_path->current_level = level;
  3206. /*
  3207. * the reference was created in the running transaction,
  3208. * no need to continue walking up.
  3209. */
  3210. if (btrfs_ref_generation(leaf, ref) == trans->transid) {
  3211. ref_path->root_objectid = btrfs_ref_root(leaf, ref);
  3212. ref_path->root_generation =
  3213. btrfs_ref_generation(leaf, ref);
  3214. ret = 0;
  3215. goto out;
  3216. }
  3217. btrfs_release_path(extent_root, path);
  3218. cond_resched();
  3219. }
  3220. /* reached max tree level, but no tree root found. */
  3221. BUG();
  3222. out:
  3223. btrfs_free_path(path);
  3224. return ret;
  3225. }
  3226. static int btrfs_first_ref_path(struct btrfs_trans_handle *trans,
  3227. struct btrfs_root *extent_root,
  3228. struct btrfs_ref_path *ref_path,
  3229. u64 extent_start)
  3230. {
  3231. memset(ref_path, 0, sizeof(*ref_path));
  3232. ref_path->extent_start = extent_start;
  3233. return __next_ref_path(trans, extent_root, ref_path, 1);
  3234. }
  3235. static int btrfs_next_ref_path(struct btrfs_trans_handle *trans,
  3236. struct btrfs_root *extent_root,
  3237. struct btrfs_ref_path *ref_path)
  3238. {
  3239. return __next_ref_path(trans, extent_root, ref_path, 0);
  3240. }
  3241. static int noinline get_new_locations(struct inode *reloc_inode,
  3242. struct btrfs_key *extent_key,
  3243. u64 offset, int no_fragment,
  3244. struct disk_extent **extents,
  3245. int *nr_extents)
  3246. {
  3247. struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
  3248. struct btrfs_path *path;
  3249. struct btrfs_file_extent_item *fi;
  3250. struct extent_buffer *leaf;
  3251. struct disk_extent *exts = *extents;
  3252. struct btrfs_key found_key;
  3253. u64 cur_pos;
  3254. u64 last_byte;
  3255. u32 nritems;
  3256. int nr = 0;
  3257. int max = *nr_extents;
  3258. int ret;
  3259. WARN_ON(!no_fragment && *extents);
  3260. if (!exts) {
  3261. max = 1;
  3262. exts = kmalloc(sizeof(*exts) * max, GFP_NOFS);
  3263. if (!exts)
  3264. return -ENOMEM;
  3265. }
  3266. path = btrfs_alloc_path();
  3267. BUG_ON(!path);
  3268. cur_pos = extent_key->objectid - offset;
  3269. last_byte = extent_key->objectid + extent_key->offset;
  3270. ret = btrfs_lookup_file_extent(NULL, root, path, reloc_inode->i_ino,
  3271. cur_pos, 0);
  3272. if (ret < 0)
  3273. goto out;
  3274. if (ret > 0) {
  3275. ret = -ENOENT;
  3276. goto out;
  3277. }
  3278. while (1) {
  3279. leaf = path->nodes[0];
  3280. nritems = btrfs_header_nritems(leaf);
  3281. if (path->slots[0] >= nritems) {
  3282. ret = btrfs_next_leaf(root, path);
  3283. if (ret < 0)
  3284. goto out;
  3285. if (ret > 0)
  3286. break;
  3287. leaf = path->nodes[0];
  3288. }
  3289. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  3290. if (found_key.offset != cur_pos ||
  3291. found_key.type != BTRFS_EXTENT_DATA_KEY ||
  3292. found_key.objectid != reloc_inode->i_ino)
  3293. break;
  3294. fi = btrfs_item_ptr(leaf, path->slots[0],
  3295. struct btrfs_file_extent_item);
  3296. if (btrfs_file_extent_type(leaf, fi) !=
  3297. BTRFS_FILE_EXTENT_REG ||
  3298. btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
  3299. break;
  3300. if (nr == max) {
  3301. struct disk_extent *old = exts;
  3302. max *= 2;
  3303. exts = kzalloc(sizeof(*exts) * max, GFP_NOFS);
  3304. memcpy(exts, old, sizeof(*exts) * nr);
  3305. if (old != *extents)
  3306. kfree(old);
  3307. }
  3308. exts[nr].disk_bytenr =
  3309. btrfs_file_extent_disk_bytenr(leaf, fi);
  3310. exts[nr].disk_num_bytes =
  3311. btrfs_file_extent_disk_num_bytes(leaf, fi);
  3312. exts[nr].offset = btrfs_file_extent_offset(leaf, fi);
  3313. exts[nr].num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
  3314. exts[nr].ram_bytes = btrfs_file_extent_ram_bytes(leaf, fi);
  3315. exts[nr].compression = btrfs_file_extent_compression(leaf, fi);
  3316. exts[nr].encryption = btrfs_file_extent_encryption(leaf, fi);
  3317. exts[nr].other_encoding = btrfs_file_extent_other_encoding(leaf,
  3318. fi);
  3319. BUG_ON(exts[nr].offset > 0);
  3320. BUG_ON(exts[nr].compression || exts[nr].encryption);
  3321. BUG_ON(exts[nr].num_bytes != exts[nr].disk_num_bytes);
  3322. cur_pos += exts[nr].num_bytes;
  3323. nr++;
  3324. if (cur_pos + offset >= last_byte)
  3325. break;
  3326. if (no_fragment) {
  3327. ret = 1;
  3328. goto out;
  3329. }
  3330. path->slots[0]++;
  3331. }
  3332. WARN_ON(cur_pos + offset > last_byte);
  3333. if (cur_pos + offset < last_byte) {
  3334. ret = -ENOENT;
  3335. goto out;
  3336. }
  3337. ret = 0;
  3338. out:
  3339. btrfs_free_path(path);
  3340. if (ret) {
  3341. if (exts != *extents)
  3342. kfree(exts);
  3343. } else {
  3344. *extents = exts;
  3345. *nr_extents = nr;
  3346. }
  3347. return ret;
  3348. }
  3349. static int noinline replace_one_extent(struct btrfs_trans_handle *trans,
  3350. struct btrfs_root *root,
  3351. struct btrfs_path *path,
  3352. struct btrfs_key *extent_key,
  3353. struct btrfs_key *leaf_key,
  3354. struct btrfs_ref_path *ref_path,
  3355. struct disk_extent *new_extents,
  3356. int nr_extents)
  3357. {
  3358. struct extent_buffer *leaf;
  3359. struct btrfs_file_extent_item *fi;
  3360. struct inode *inode = NULL;
  3361. struct btrfs_key key;
  3362. u64 lock_start = 0;
  3363. u64 lock_end = 0;
  3364. u64 num_bytes;
  3365. u64 ext_offset;
  3366. u64 first_pos;
  3367. u32 nritems;
  3368. int nr_scaned = 0;
  3369. int extent_locked = 0;
  3370. int extent_type;
  3371. int ret;
  3372. memcpy(&key, leaf_key, sizeof(key));
  3373. first_pos = INT_LIMIT(loff_t) - extent_key->offset;
  3374. if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
  3375. if (key.objectid < ref_path->owner_objectid ||
  3376. (key.objectid == ref_path->owner_objectid &&
  3377. key.type < BTRFS_EXTENT_DATA_KEY)) {
  3378. key.objectid = ref_path->owner_objectid;
  3379. key.type = BTRFS_EXTENT_DATA_KEY;
  3380. key.offset = 0;
  3381. }
  3382. }
  3383. while (1) {
  3384. ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
  3385. if (ret < 0)
  3386. goto out;
  3387. leaf = path->nodes[0];
  3388. nritems = btrfs_header_nritems(leaf);
  3389. next:
  3390. if (extent_locked && ret > 0) {
  3391. /*
  3392. * the file extent item was modified by someone
  3393. * before the extent got locked.
  3394. */
  3395. unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
  3396. lock_end, GFP_NOFS);
  3397. extent_locked = 0;
  3398. }
  3399. if (path->slots[0] >= nritems) {
  3400. if (++nr_scaned > 2)
  3401. break;
  3402. BUG_ON(extent_locked);
  3403. ret = btrfs_next_leaf(root, path);
  3404. if (ret < 0)
  3405. goto out;
  3406. if (ret > 0)
  3407. break;
  3408. leaf = path->nodes[0];
  3409. nritems = btrfs_header_nritems(leaf);
  3410. }
  3411. btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  3412. if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
  3413. if ((key.objectid > ref_path->owner_objectid) ||
  3414. (key.objectid == ref_path->owner_objectid &&
  3415. key.type > BTRFS_EXTENT_DATA_KEY) ||
  3416. (key.offset >= first_pos + extent_key->offset))
  3417. break;
  3418. }
  3419. if (inode && key.objectid != inode->i_ino) {
  3420. BUG_ON(extent_locked);
  3421. btrfs_release_path(root, path);
  3422. mutex_unlock(&inode->i_mutex);
  3423. iput(inode);
  3424. inode = NULL;
  3425. continue;
  3426. }
  3427. if (key.type != BTRFS_EXTENT_DATA_KEY) {
  3428. path->slots[0]++;
  3429. ret = 1;
  3430. goto next;
  3431. }
  3432. fi = btrfs_item_ptr(leaf, path->slots[0],
  3433. struct btrfs_file_extent_item);
  3434. extent_type = btrfs_file_extent_type(leaf, fi);
  3435. if ((extent_type != BTRFS_FILE_EXTENT_REG &&
  3436. extent_type != BTRFS_FILE_EXTENT_PREALLOC) ||
  3437. (btrfs_file_extent_disk_bytenr(leaf, fi) !=
  3438. extent_key->objectid)) {
  3439. path->slots[0]++;
  3440. ret = 1;
  3441. goto next;
  3442. }
  3443. num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
  3444. ext_offset = btrfs_file_extent_offset(leaf, fi);
  3445. if (first_pos > key.offset - ext_offset)
  3446. first_pos = key.offset - ext_offset;
  3447. if (!extent_locked) {
  3448. lock_start = key.offset;
  3449. lock_end = lock_start + num_bytes - 1;
  3450. } else {
  3451. if (lock_start > key.offset ||
  3452. lock_end + 1 < key.offset + num_bytes) {
  3453. unlock_extent(&BTRFS_I(inode)->io_tree,
  3454. lock_start, lock_end, GFP_NOFS);
  3455. extent_locked = 0;
  3456. }
  3457. }
  3458. if (!inode) {
  3459. btrfs_release_path(root, path);
  3460. inode = btrfs_iget_locked(root->fs_info->sb,
  3461. key.objectid, root);
  3462. if (inode->i_state & I_NEW) {
  3463. BTRFS_I(inode)->root = root;
  3464. BTRFS_I(inode)->location.objectid =
  3465. key.objectid;
  3466. BTRFS_I(inode)->location.type =
  3467. BTRFS_INODE_ITEM_KEY;
  3468. BTRFS_I(inode)->location.offset = 0;
  3469. btrfs_read_locked_inode(inode);
  3470. unlock_new_inode(inode);
  3471. }
  3472. /*
  3473. * some code call btrfs_commit_transaction while
  3474. * holding the i_mutex, so we can't use mutex_lock
  3475. * here.
  3476. */
  3477. if (is_bad_inode(inode) ||
  3478. !mutex_trylock(&inode->i_mutex)) {
  3479. iput(inode);
  3480. inode = NULL;
  3481. key.offset = (u64)-1;
  3482. goto skip;
  3483. }
  3484. }
  3485. if (!extent_locked) {
  3486. struct btrfs_ordered_extent *ordered;
  3487. btrfs_release_path(root, path);
  3488. lock_extent(&BTRFS_I(inode)->io_tree, lock_start,
  3489. lock_end, GFP_NOFS);
  3490. ordered = btrfs_lookup_first_ordered_extent(inode,
  3491. lock_end);
  3492. if (ordered &&
  3493. ordered->file_offset <= lock_end &&
  3494. ordered->file_offset + ordered->len > lock_start) {
  3495. unlock_extent(&BTRFS_I(inode)->io_tree,
  3496. lock_start, lock_end, GFP_NOFS);
  3497. btrfs_start_ordered_extent(inode, ordered, 1);
  3498. btrfs_put_ordered_extent(ordered);
  3499. key.offset += num_bytes;
  3500. goto skip;
  3501. }
  3502. if (ordered)
  3503. btrfs_put_ordered_extent(ordered);
  3504. extent_locked = 1;
  3505. continue;
  3506. }
  3507. if (nr_extents == 1) {
  3508. /* update extent pointer in place */
  3509. btrfs_set_file_extent_disk_bytenr(leaf, fi,
  3510. new_extents[0].disk_bytenr);
  3511. btrfs_set_file_extent_disk_num_bytes(leaf, fi,
  3512. new_extents[0].disk_num_bytes);
  3513. btrfs_mark_buffer_dirty(leaf);
  3514. btrfs_drop_extent_cache(inode, key.offset,
  3515. key.offset + num_bytes - 1, 0);
  3516. ret = btrfs_inc_extent_ref(trans, root,
  3517. new_extents[0].disk_bytenr,
  3518. new_extents[0].disk_num_bytes,
  3519. leaf->start,
  3520. root->root_key.objectid,
  3521. trans->transid,
  3522. key.objectid);
  3523. BUG_ON(ret);
  3524. ret = btrfs_free_extent(trans, root,
  3525. extent_key->objectid,
  3526. extent_key->offset,
  3527. leaf->start,
  3528. btrfs_header_owner(leaf),
  3529. btrfs_header_generation(leaf),
  3530. key.objectid, 0);
  3531. BUG_ON(ret);
  3532. btrfs_release_path(root, path);
  3533. key.offset += num_bytes;
  3534. } else {
  3535. BUG_ON(1);
  3536. #if 0
  3537. u64 alloc_hint;
  3538. u64 extent_len;
  3539. int i;
  3540. /*
  3541. * drop old extent pointer at first, then insert the
  3542. * new pointers one bye one
  3543. */
  3544. btrfs_release_path(root, path);
  3545. ret = btrfs_drop_extents(trans, root, inode, key.offset,
  3546. key.offset + num_bytes,
  3547. key.offset, &alloc_hint);
  3548. BUG_ON(ret);
  3549. for (i = 0; i < nr_extents; i++) {
  3550. if (ext_offset >= new_extents[i].num_bytes) {
  3551. ext_offset -= new_extents[i].num_bytes;
  3552. continue;
  3553. }
  3554. extent_len = min(new_extents[i].num_bytes -
  3555. ext_offset, num_bytes);
  3556. ret = btrfs_insert_empty_item(trans, root,
  3557. path, &key,
  3558. sizeof(*fi));
  3559. BUG_ON(ret);
  3560. leaf = path->nodes[0];
  3561. fi = btrfs_item_ptr(leaf, path->slots[0],
  3562. struct btrfs_file_extent_item);
  3563. btrfs_set_file_extent_generation(leaf, fi,
  3564. trans->transid);
  3565. btrfs_set_file_extent_type(leaf, fi,
  3566. BTRFS_FILE_EXTENT_REG);
  3567. btrfs_set_file_extent_disk_bytenr(leaf, fi,
  3568. new_extents[i].disk_bytenr);
  3569. btrfs_set_file_extent_disk_num_bytes(leaf, fi,
  3570. new_extents[i].disk_num_bytes);
  3571. btrfs_set_file_extent_ram_bytes(leaf, fi,
  3572. new_extents[i].ram_bytes);
  3573. btrfs_set_file_extent_compression(leaf, fi,
  3574. new_extents[i].compression);
  3575. btrfs_set_file_extent_encryption(leaf, fi,
  3576. new_extents[i].encryption);
  3577. btrfs_set_file_extent_other_encoding(leaf, fi,
  3578. new_extents[i].other_encoding);
  3579. btrfs_set_file_extent_num_bytes(leaf, fi,
  3580. extent_len);
  3581. ext_offset += new_extents[i].offset;
  3582. btrfs_set_file_extent_offset(leaf, fi,
  3583. ext_offset);
  3584. btrfs_mark_buffer_dirty(leaf);
  3585. btrfs_drop_extent_cache(inode, key.offset,
  3586. key.offset + extent_len - 1, 0);
  3587. ret = btrfs_inc_extent_ref(trans, root,
  3588. new_extents[i].disk_bytenr,
  3589. new_extents[i].disk_num_bytes,
  3590. leaf->start,
  3591. root->root_key.objectid,
  3592. trans->transid, key.objectid);
  3593. BUG_ON(ret);
  3594. btrfs_release_path(root, path);
  3595. inode_add_bytes(inode, extent_len);
  3596. ext_offset = 0;
  3597. num_bytes -= extent_len;
  3598. key.offset += extent_len;
  3599. if (num_bytes == 0)
  3600. break;
  3601. }
  3602. BUG_ON(i >= nr_extents);
  3603. #endif
  3604. }
  3605. if (extent_locked) {
  3606. unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
  3607. lock_end, GFP_NOFS);
  3608. extent_locked = 0;
  3609. }
  3610. skip:
  3611. if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS &&
  3612. key.offset >= first_pos + extent_key->offset)
  3613. break;
  3614. cond_resched();
  3615. }
  3616. ret = 0;
  3617. out:
  3618. btrfs_release_path(root, path);
  3619. if (inode) {
  3620. mutex_unlock(&inode->i_mutex);
  3621. if (extent_locked) {
  3622. unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
  3623. lock_end, GFP_NOFS);
  3624. }
  3625. iput(inode);
  3626. }
  3627. return ret;
  3628. }
  3629. int btrfs_reloc_tree_cache_ref(struct btrfs_trans_handle *trans,
  3630. struct btrfs_root *root,
  3631. struct extent_buffer *buf, u64 orig_start)
  3632. {
  3633. int level;
  3634. int ret;
  3635. BUG_ON(btrfs_header_generation(buf) != trans->transid);
  3636. BUG_ON(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
  3637. level = btrfs_header_level(buf);
  3638. if (level == 0) {
  3639. struct btrfs_leaf_ref *ref;
  3640. struct btrfs_leaf_ref *orig_ref;
  3641. orig_ref = btrfs_lookup_leaf_ref(root, orig_start);
  3642. if (!orig_ref)
  3643. return -ENOENT;
  3644. ref = btrfs_alloc_leaf_ref(root, orig_ref->nritems);
  3645. if (!ref) {
  3646. btrfs_free_leaf_ref(root, orig_ref);
  3647. return -ENOMEM;
  3648. }
  3649. ref->nritems = orig_ref->nritems;
  3650. memcpy(ref->extents, orig_ref->extents,
  3651. sizeof(ref->extents[0]) * ref->nritems);
  3652. btrfs_free_leaf_ref(root, orig_ref);
  3653. ref->root_gen = trans->transid;
  3654. ref->bytenr = buf->start;
  3655. ref->owner = btrfs_header_owner(buf);
  3656. ref->generation = btrfs_header_generation(buf);
  3657. ret = btrfs_add_leaf_ref(root, ref, 0);
  3658. WARN_ON(ret);
  3659. btrfs_free_leaf_ref(root, ref);
  3660. }
  3661. return 0;
  3662. }
  3663. static int noinline invalidate_extent_cache(struct btrfs_root *root,
  3664. struct extent_buffer *leaf,
  3665. struct btrfs_block_group_cache *group,
  3666. struct btrfs_root *target_root)
  3667. {
  3668. struct btrfs_key key;
  3669. struct inode *inode = NULL;
  3670. struct btrfs_file_extent_item *fi;
  3671. u64 num_bytes;
  3672. u64 skip_objectid = 0;
  3673. u32 nritems;
  3674. u32 i;
  3675. nritems = btrfs_header_nritems(leaf);
  3676. for (i = 0; i < nritems; i++) {
  3677. btrfs_item_key_to_cpu(leaf, &key, i);
  3678. if (key.objectid == skip_objectid ||
  3679. key.type != BTRFS_EXTENT_DATA_KEY)
  3680. continue;
  3681. fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
  3682. if (btrfs_file_extent_type(leaf, fi) ==
  3683. BTRFS_FILE_EXTENT_INLINE)
  3684. continue;
  3685. if (btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
  3686. continue;
  3687. if (!inode || inode->i_ino != key.objectid) {
  3688. iput(inode);
  3689. inode = btrfs_ilookup(target_root->fs_info->sb,
  3690. key.objectid, target_root, 1);
  3691. }
  3692. if (!inode) {
  3693. skip_objectid = key.objectid;
  3694. continue;
  3695. }
  3696. num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
  3697. lock_extent(&BTRFS_I(inode)->io_tree, key.offset,
  3698. key.offset + num_bytes - 1, GFP_NOFS);
  3699. btrfs_drop_extent_cache(inode, key.offset,
  3700. key.offset + num_bytes - 1, 1);
  3701. unlock_extent(&BTRFS_I(inode)->io_tree, key.offset,
  3702. key.offset + num_bytes - 1, GFP_NOFS);
  3703. cond_resched();
  3704. }
  3705. iput(inode);
  3706. return 0;
  3707. }
  3708. static int noinline replace_extents_in_leaf(struct btrfs_trans_handle *trans,
  3709. struct btrfs_root *root,
  3710. struct extent_buffer *leaf,
  3711. struct btrfs_block_group_cache *group,
  3712. struct inode *reloc_inode)
  3713. {
  3714. struct btrfs_key key;
  3715. struct btrfs_key extent_key;
  3716. struct btrfs_file_extent_item *fi;
  3717. struct btrfs_leaf_ref *ref;
  3718. struct disk_extent *new_extent;
  3719. u64 bytenr;
  3720. u64 num_bytes;
  3721. u32 nritems;
  3722. u32 i;
  3723. int ext_index;
  3724. int nr_extent;
  3725. int ret;
  3726. new_extent = kmalloc(sizeof(*new_extent), GFP_NOFS);
  3727. BUG_ON(!new_extent);
  3728. ref = btrfs_lookup_leaf_ref(root, leaf->start);
  3729. BUG_ON(!ref);
  3730. ext_index = -1;
  3731. nritems = btrfs_header_nritems(leaf);
  3732. for (i = 0; i < nritems; i++) {
  3733. btrfs_item_key_to_cpu(leaf, &key, i);
  3734. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  3735. continue;
  3736. fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
  3737. if (btrfs_file_extent_type(leaf, fi) ==
  3738. BTRFS_FILE_EXTENT_INLINE)
  3739. continue;
  3740. bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
  3741. num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
  3742. if (bytenr == 0)
  3743. continue;
  3744. ext_index++;
  3745. if (bytenr >= group->key.objectid + group->key.offset ||
  3746. bytenr + num_bytes <= group->key.objectid)
  3747. continue;
  3748. extent_key.objectid = bytenr;
  3749. extent_key.offset = num_bytes;
  3750. extent_key.type = BTRFS_EXTENT_ITEM_KEY;
  3751. nr_extent = 1;
  3752. ret = get_new_locations(reloc_inode, &extent_key,
  3753. group->key.objectid, 1,
  3754. &new_extent, &nr_extent);
  3755. if (ret > 0)
  3756. continue;
  3757. BUG_ON(ret < 0);
  3758. BUG_ON(ref->extents[ext_index].bytenr != bytenr);
  3759. BUG_ON(ref->extents[ext_index].num_bytes != num_bytes);
  3760. ref->extents[ext_index].bytenr = new_extent->disk_bytenr;
  3761. ref->extents[ext_index].num_bytes = new_extent->disk_num_bytes;
  3762. btrfs_set_file_extent_disk_bytenr(leaf, fi,
  3763. new_extent->disk_bytenr);
  3764. btrfs_set_file_extent_disk_num_bytes(leaf, fi,
  3765. new_extent->disk_num_bytes);
  3766. btrfs_mark_buffer_dirty(leaf);
  3767. ret = btrfs_inc_extent_ref(trans, root,
  3768. new_extent->disk_bytenr,
  3769. new_extent->disk_num_bytes,
  3770. leaf->start,
  3771. root->root_key.objectid,
  3772. trans->transid, key.objectid);
  3773. BUG_ON(ret);
  3774. ret = btrfs_free_extent(trans, root,
  3775. bytenr, num_bytes, leaf->start,
  3776. btrfs_header_owner(leaf),
  3777. btrfs_header_generation(leaf),
  3778. key.objectid, 0);
  3779. BUG_ON(ret);
  3780. cond_resched();
  3781. }
  3782. kfree(new_extent);
  3783. BUG_ON(ext_index + 1 != ref->nritems);
  3784. btrfs_free_leaf_ref(root, ref);
  3785. return 0;
  3786. }
  3787. int btrfs_free_reloc_root(struct btrfs_trans_handle *trans,
  3788. struct btrfs_root *root)
  3789. {
  3790. struct btrfs_root *reloc_root;
  3791. int ret;
  3792. if (root->reloc_root) {
  3793. reloc_root = root->reloc_root;
  3794. root->reloc_root = NULL;
  3795. list_add(&reloc_root->dead_list,
  3796. &root->fs_info->dead_reloc_roots);
  3797. btrfs_set_root_bytenr(&reloc_root->root_item,
  3798. reloc_root->node->start);
  3799. btrfs_set_root_level(&root->root_item,
  3800. btrfs_header_level(reloc_root->node));
  3801. memset(&reloc_root->root_item.drop_progress, 0,
  3802. sizeof(struct btrfs_disk_key));
  3803. reloc_root->root_item.drop_level = 0;
  3804. ret = btrfs_update_root(trans, root->fs_info->tree_root,
  3805. &reloc_root->root_key,
  3806. &reloc_root->root_item);
  3807. BUG_ON(ret);
  3808. }
  3809. return 0;
  3810. }
  3811. int btrfs_drop_dead_reloc_roots(struct btrfs_root *root)
  3812. {
  3813. struct btrfs_trans_handle *trans;
  3814. struct btrfs_root *reloc_root;
  3815. struct btrfs_root *prev_root = NULL;
  3816. struct list_head dead_roots;
  3817. int ret;
  3818. unsigned long nr;
  3819. INIT_LIST_HEAD(&dead_roots);
  3820. list_splice_init(&root->fs_info->dead_reloc_roots, &dead_roots);
  3821. while (!list_empty(&dead_roots)) {
  3822. reloc_root = list_entry(dead_roots.prev,
  3823. struct btrfs_root, dead_list);
  3824. list_del_init(&reloc_root->dead_list);
  3825. BUG_ON(reloc_root->commit_root != NULL);
  3826. while (1) {
  3827. trans = btrfs_join_transaction(root, 1);
  3828. BUG_ON(!trans);
  3829. mutex_lock(&root->fs_info->drop_mutex);
  3830. ret = btrfs_drop_snapshot(trans, reloc_root);
  3831. if (ret != -EAGAIN)
  3832. break;
  3833. mutex_unlock(&root->fs_info->drop_mutex);
  3834. nr = trans->blocks_used;
  3835. ret = btrfs_end_transaction(trans, root);
  3836. BUG_ON(ret);
  3837. btrfs_btree_balance_dirty(root, nr);
  3838. }
  3839. free_extent_buffer(reloc_root->node);
  3840. ret = btrfs_del_root(trans, root->fs_info->tree_root,
  3841. &reloc_root->root_key);
  3842. BUG_ON(ret);
  3843. mutex_unlock(&root->fs_info->drop_mutex);
  3844. nr = trans->blocks_used;
  3845. ret = btrfs_end_transaction(trans, root);
  3846. BUG_ON(ret);
  3847. btrfs_btree_balance_dirty(root, nr);
  3848. kfree(prev_root);
  3849. prev_root = reloc_root;
  3850. }
  3851. if (prev_root) {
  3852. btrfs_remove_leaf_refs(prev_root, (u64)-1, 0);
  3853. kfree(prev_root);
  3854. }
  3855. return 0;
  3856. }
  3857. int btrfs_add_dead_reloc_root(struct btrfs_root *root)
  3858. {
  3859. list_add(&root->dead_list, &root->fs_info->dead_reloc_roots);
  3860. return 0;
  3861. }
  3862. int btrfs_cleanup_reloc_trees(struct btrfs_root *root)
  3863. {
  3864. struct btrfs_root *reloc_root;
  3865. struct btrfs_trans_handle *trans;
  3866. struct btrfs_key location;
  3867. int found;
  3868. int ret;
  3869. mutex_lock(&root->fs_info->tree_reloc_mutex);
  3870. ret = btrfs_find_dead_roots(root, BTRFS_TREE_RELOC_OBJECTID, NULL);
  3871. BUG_ON(ret);
  3872. found = !list_empty(&root->fs_info->dead_reloc_roots);
  3873. mutex_unlock(&root->fs_info->tree_reloc_mutex);
  3874. if (found) {
  3875. trans = btrfs_start_transaction(root, 1);
  3876. BUG_ON(!trans);
  3877. ret = btrfs_commit_transaction(trans, root);
  3878. BUG_ON(ret);
  3879. }
  3880. location.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
  3881. location.offset = (u64)-1;
  3882. location.type = BTRFS_ROOT_ITEM_KEY;
  3883. reloc_root = btrfs_read_fs_root_no_name(root->fs_info, &location);
  3884. BUG_ON(!reloc_root);
  3885. btrfs_orphan_cleanup(reloc_root);
  3886. return 0;
  3887. }
  3888. static int noinline init_reloc_tree(struct btrfs_trans_handle *trans,
  3889. struct btrfs_root *root)
  3890. {
  3891. struct btrfs_root *reloc_root;
  3892. struct extent_buffer *eb;
  3893. struct btrfs_root_item *root_item;
  3894. struct btrfs_key root_key;
  3895. int ret;
  3896. BUG_ON(!root->ref_cows);
  3897. if (root->reloc_root)
  3898. return 0;
  3899. root_item = kmalloc(sizeof(*root_item), GFP_NOFS);
  3900. BUG_ON(!root_item);
  3901. ret = btrfs_copy_root(trans, root, root->commit_root,
  3902. &eb, BTRFS_TREE_RELOC_OBJECTID);
  3903. BUG_ON(ret);
  3904. root_key.objectid = BTRFS_TREE_RELOC_OBJECTID;
  3905. root_key.offset = root->root_key.objectid;
  3906. root_key.type = BTRFS_ROOT_ITEM_KEY;
  3907. memcpy(root_item, &root->root_item, sizeof(root_item));
  3908. btrfs_set_root_refs(root_item, 0);
  3909. btrfs_set_root_bytenr(root_item, eb->start);
  3910. btrfs_set_root_level(root_item, btrfs_header_level(eb));
  3911. btrfs_set_root_generation(root_item, trans->transid);
  3912. btrfs_tree_unlock(eb);
  3913. free_extent_buffer(eb);
  3914. ret = btrfs_insert_root(trans, root->fs_info->tree_root,
  3915. &root_key, root_item);
  3916. BUG_ON(ret);
  3917. kfree(root_item);
  3918. reloc_root = btrfs_read_fs_root_no_radix(root->fs_info->tree_root,
  3919. &root_key);
  3920. BUG_ON(!reloc_root);
  3921. reloc_root->last_trans = trans->transid;
  3922. reloc_root->commit_root = NULL;
  3923. reloc_root->ref_tree = &root->fs_info->reloc_ref_tree;
  3924. root->reloc_root = reloc_root;
  3925. return 0;
  3926. }
  3927. /*
  3928. * Core function of space balance.
  3929. *
  3930. * The idea is using reloc trees to relocate tree blocks in reference
  3931. * counted roots. There is one reloc tree for each subvol, and all
  3932. * reloc trees share same root key objectid. Reloc trees are snapshots
  3933. * of the latest committed roots of subvols (root->commit_root).
  3934. *
  3935. * To relocate a tree block referenced by a subvol, there are two steps.
  3936. * COW the block through subvol's reloc tree, then update block pointer
  3937. * in the subvol to point to the new block. Since all reloc trees share
  3938. * same root key objectid, doing special handing for tree blocks owned
  3939. * by them is easy. Once a tree block has been COWed in one reloc tree,
  3940. * we can use the resulting new block directly when the same block is
  3941. * required to COW again through other reloc trees. By this way, relocated
  3942. * tree blocks are shared between reloc trees, so they are also shared
  3943. * between subvols.
  3944. */
  3945. static int noinline relocate_one_path(struct btrfs_trans_handle *trans,
  3946. struct btrfs_root *root,
  3947. struct btrfs_path *path,
  3948. struct btrfs_key *first_key,
  3949. struct btrfs_ref_path *ref_path,
  3950. struct btrfs_block_group_cache *group,
  3951. struct inode *reloc_inode)
  3952. {
  3953. struct btrfs_root *reloc_root;
  3954. struct extent_buffer *eb = NULL;
  3955. struct btrfs_key *keys;
  3956. u64 *nodes;
  3957. int level;
  3958. int shared_level;
  3959. int lowest_level = 0;
  3960. int ret;
  3961. if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
  3962. lowest_level = ref_path->owner_objectid;
  3963. if (!root->ref_cows) {
  3964. path->lowest_level = lowest_level;
  3965. ret = btrfs_search_slot(trans, root, first_key, path, 0, 1);
  3966. BUG_ON(ret < 0);
  3967. path->lowest_level = 0;
  3968. btrfs_release_path(root, path);
  3969. return 0;
  3970. }
  3971. mutex_lock(&root->fs_info->tree_reloc_mutex);
  3972. ret = init_reloc_tree(trans, root);
  3973. BUG_ON(ret);
  3974. reloc_root = root->reloc_root;
  3975. shared_level = ref_path->shared_level;
  3976. ref_path->shared_level = BTRFS_MAX_LEVEL - 1;
  3977. keys = ref_path->node_keys;
  3978. nodes = ref_path->new_nodes;
  3979. memset(&keys[shared_level + 1], 0,
  3980. sizeof(*keys) * (BTRFS_MAX_LEVEL - shared_level - 1));
  3981. memset(&nodes[shared_level + 1], 0,
  3982. sizeof(*nodes) * (BTRFS_MAX_LEVEL - shared_level - 1));
  3983. if (nodes[lowest_level] == 0) {
  3984. path->lowest_level = lowest_level;
  3985. ret = btrfs_search_slot(trans, reloc_root, first_key, path,
  3986. 0, 1);
  3987. BUG_ON(ret);
  3988. for (level = lowest_level; level < BTRFS_MAX_LEVEL; level++) {
  3989. eb = path->nodes[level];
  3990. if (!eb || eb == reloc_root->node)
  3991. break;
  3992. nodes[level] = eb->start;
  3993. if (level == 0)
  3994. btrfs_item_key_to_cpu(eb, &keys[level], 0);
  3995. else
  3996. btrfs_node_key_to_cpu(eb, &keys[level], 0);
  3997. }
  3998. if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
  3999. eb = path->nodes[0];
  4000. ret = replace_extents_in_leaf(trans, reloc_root, eb,
  4001. group, reloc_inode);
  4002. BUG_ON(ret);
  4003. }
  4004. btrfs_release_path(reloc_root, path);
  4005. } else {
  4006. ret = btrfs_merge_path(trans, reloc_root, keys, nodes,
  4007. lowest_level);
  4008. BUG_ON(ret);
  4009. }
  4010. /*
  4011. * replace tree blocks in the fs tree with tree blocks in
  4012. * the reloc tree.
  4013. */
  4014. ret = btrfs_merge_path(trans, root, keys, nodes, lowest_level);
  4015. BUG_ON(ret < 0);
  4016. if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
  4017. ret = btrfs_search_slot(trans, reloc_root, first_key, path,
  4018. 0, 0);
  4019. BUG_ON(ret);
  4020. extent_buffer_get(path->nodes[0]);
  4021. eb = path->nodes[0];
  4022. btrfs_release_path(reloc_root, path);
  4023. ret = invalidate_extent_cache(reloc_root, eb, group, root);
  4024. BUG_ON(ret);
  4025. free_extent_buffer(eb);
  4026. }
  4027. mutex_unlock(&root->fs_info->tree_reloc_mutex);
  4028. path->lowest_level = 0;
  4029. return 0;
  4030. }
  4031. static int noinline relocate_tree_block(struct btrfs_trans_handle *trans,
  4032. struct btrfs_root *root,
  4033. struct btrfs_path *path,
  4034. struct btrfs_key *first_key,
  4035. struct btrfs_ref_path *ref_path)
  4036. {
  4037. int ret;
  4038. ret = relocate_one_path(trans, root, path, first_key,
  4039. ref_path, NULL, NULL);
  4040. BUG_ON(ret);
  4041. if (root == root->fs_info->extent_root)
  4042. btrfs_extent_post_op(trans, root);
  4043. return 0;
  4044. }
  4045. static int noinline del_extent_zero(struct btrfs_trans_handle *trans,
  4046. struct btrfs_root *extent_root,
  4047. struct btrfs_path *path,
  4048. struct btrfs_key *extent_key)
  4049. {
  4050. int ret;
  4051. ret = btrfs_search_slot(trans, extent_root, extent_key, path, -1, 1);
  4052. if (ret)
  4053. goto out;
  4054. ret = btrfs_del_item(trans, extent_root, path);
  4055. out:
  4056. btrfs_release_path(extent_root, path);
  4057. return ret;
  4058. }
  4059. static struct btrfs_root noinline *read_ref_root(struct btrfs_fs_info *fs_info,
  4060. struct btrfs_ref_path *ref_path)
  4061. {
  4062. struct btrfs_key root_key;
  4063. root_key.objectid = ref_path->root_objectid;
  4064. root_key.type = BTRFS_ROOT_ITEM_KEY;
  4065. if (is_cowonly_root(ref_path->root_objectid))
  4066. root_key.offset = 0;
  4067. else
  4068. root_key.offset = (u64)-1;
  4069. return btrfs_read_fs_root_no_name(fs_info, &root_key);
  4070. }
  4071. static int noinline relocate_one_extent(struct btrfs_root *extent_root,
  4072. struct btrfs_path *path,
  4073. struct btrfs_key *extent_key,
  4074. struct btrfs_block_group_cache *group,
  4075. struct inode *reloc_inode, int pass)
  4076. {
  4077. struct btrfs_trans_handle *trans;
  4078. struct btrfs_root *found_root;
  4079. struct btrfs_ref_path *ref_path = NULL;
  4080. struct disk_extent *new_extents = NULL;
  4081. int nr_extents = 0;
  4082. int loops;
  4083. int ret;
  4084. int level;
  4085. struct btrfs_key first_key;
  4086. u64 prev_block = 0;
  4087. trans = btrfs_start_transaction(extent_root, 1);
  4088. BUG_ON(!trans);
  4089. if (extent_key->objectid == 0) {
  4090. ret = del_extent_zero(trans, extent_root, path, extent_key);
  4091. goto out;
  4092. }
  4093. ref_path = kmalloc(sizeof(*ref_path), GFP_NOFS);
  4094. if (!ref_path) {
  4095. ret = -ENOMEM;
  4096. goto out;
  4097. }
  4098. for (loops = 0; ; loops++) {
  4099. if (loops == 0) {
  4100. ret = btrfs_first_ref_path(trans, extent_root, ref_path,
  4101. extent_key->objectid);
  4102. } else {
  4103. ret = btrfs_next_ref_path(trans, extent_root, ref_path);
  4104. }
  4105. if (ret < 0)
  4106. goto out;
  4107. if (ret > 0)
  4108. break;
  4109. if (ref_path->root_objectid == BTRFS_TREE_LOG_OBJECTID ||
  4110. ref_path->root_objectid == BTRFS_TREE_RELOC_OBJECTID)
  4111. continue;
  4112. found_root = read_ref_root(extent_root->fs_info, ref_path);
  4113. BUG_ON(!found_root);
  4114. /*
  4115. * for reference counted tree, only process reference paths
  4116. * rooted at the latest committed root.
  4117. */
  4118. if (found_root->ref_cows &&
  4119. ref_path->root_generation != found_root->root_key.offset)
  4120. continue;
  4121. if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
  4122. if (pass == 0) {
  4123. /*
  4124. * copy data extents to new locations
  4125. */
  4126. u64 group_start = group->key.objectid;
  4127. ret = relocate_data_extent(reloc_inode,
  4128. extent_key,
  4129. group_start);
  4130. if (ret < 0)
  4131. goto out;
  4132. break;
  4133. }
  4134. level = 0;
  4135. } else {
  4136. level = ref_path->owner_objectid;
  4137. }
  4138. if (prev_block != ref_path->nodes[level]) {
  4139. struct extent_buffer *eb;
  4140. u64 block_start = ref_path->nodes[level];
  4141. u64 block_size = btrfs_level_size(found_root, level);
  4142. eb = read_tree_block(found_root, block_start,
  4143. block_size, 0);
  4144. btrfs_tree_lock(eb);
  4145. BUG_ON(level != btrfs_header_level(eb));
  4146. if (level == 0)
  4147. btrfs_item_key_to_cpu(eb, &first_key, 0);
  4148. else
  4149. btrfs_node_key_to_cpu(eb, &first_key, 0);
  4150. btrfs_tree_unlock(eb);
  4151. free_extent_buffer(eb);
  4152. prev_block = block_start;
  4153. }
  4154. if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID &&
  4155. pass >= 2) {
  4156. /*
  4157. * use fallback method to process the remaining
  4158. * references.
  4159. */
  4160. if (!new_extents) {
  4161. u64 group_start = group->key.objectid;
  4162. new_extents = kmalloc(sizeof(*new_extents),
  4163. GFP_NOFS);
  4164. nr_extents = 1;
  4165. ret = get_new_locations(reloc_inode,
  4166. extent_key,
  4167. group_start, 1,
  4168. &new_extents,
  4169. &nr_extents);
  4170. if (ret)
  4171. goto out;
  4172. }
  4173. btrfs_record_root_in_trans(found_root);
  4174. ret = replace_one_extent(trans, found_root,
  4175. path, extent_key,
  4176. &first_key, ref_path,
  4177. new_extents, nr_extents);
  4178. if (ret < 0)
  4179. goto out;
  4180. continue;
  4181. }
  4182. btrfs_record_root_in_trans(found_root);
  4183. if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
  4184. ret = relocate_tree_block(trans, found_root, path,
  4185. &first_key, ref_path);
  4186. } else {
  4187. /*
  4188. * try to update data extent references while
  4189. * keeping metadata shared between snapshots.
  4190. */
  4191. ret = relocate_one_path(trans, found_root, path,
  4192. &first_key, ref_path,
  4193. group, reloc_inode);
  4194. }
  4195. if (ret < 0)
  4196. goto out;
  4197. }
  4198. ret = 0;
  4199. out:
  4200. btrfs_end_transaction(trans, extent_root);
  4201. kfree(new_extents);
  4202. kfree(ref_path);
  4203. return ret;
  4204. }
  4205. static u64 update_block_group_flags(struct btrfs_root *root, u64 flags)
  4206. {
  4207. u64 num_devices;
  4208. u64 stripped = BTRFS_BLOCK_GROUP_RAID0 |
  4209. BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10;
  4210. num_devices = root->fs_info->fs_devices->num_devices;
  4211. if (num_devices == 1) {
  4212. stripped |= BTRFS_BLOCK_GROUP_DUP;
  4213. stripped = flags & ~stripped;
  4214. /* turn raid0 into single device chunks */
  4215. if (flags & BTRFS_BLOCK_GROUP_RAID0)
  4216. return stripped;
  4217. /* turn mirroring into duplication */
  4218. if (flags & (BTRFS_BLOCK_GROUP_RAID1 |
  4219. BTRFS_BLOCK_GROUP_RAID10))
  4220. return stripped | BTRFS_BLOCK_GROUP_DUP;
  4221. return flags;
  4222. } else {
  4223. /* they already had raid on here, just return */
  4224. if (flags & stripped)
  4225. return flags;
  4226. stripped |= BTRFS_BLOCK_GROUP_DUP;
  4227. stripped = flags & ~stripped;
  4228. /* switch duplicated blocks with raid1 */
  4229. if (flags & BTRFS_BLOCK_GROUP_DUP)
  4230. return stripped | BTRFS_BLOCK_GROUP_RAID1;
  4231. /* turn single device chunks into raid0 */
  4232. return stripped | BTRFS_BLOCK_GROUP_RAID0;
  4233. }
  4234. return flags;
  4235. }
  4236. int __alloc_chunk_for_shrink(struct btrfs_root *root,
  4237. struct btrfs_block_group_cache *shrink_block_group,
  4238. int force)
  4239. {
  4240. struct btrfs_trans_handle *trans;
  4241. u64 new_alloc_flags;
  4242. u64 calc;
  4243. spin_lock(&shrink_block_group->lock);
  4244. if (btrfs_block_group_used(&shrink_block_group->item) > 0) {
  4245. spin_unlock(&shrink_block_group->lock);
  4246. trans = btrfs_start_transaction(root, 1);
  4247. spin_lock(&shrink_block_group->lock);
  4248. new_alloc_flags = update_block_group_flags(root,
  4249. shrink_block_group->flags);
  4250. if (new_alloc_flags != shrink_block_group->flags) {
  4251. calc =
  4252. btrfs_block_group_used(&shrink_block_group->item);
  4253. } else {
  4254. calc = shrink_block_group->key.offset;
  4255. }
  4256. spin_unlock(&shrink_block_group->lock);
  4257. do_chunk_alloc(trans, root->fs_info->extent_root,
  4258. calc + 2 * 1024 * 1024, new_alloc_flags, force);
  4259. btrfs_end_transaction(trans, root);
  4260. } else
  4261. spin_unlock(&shrink_block_group->lock);
  4262. return 0;
  4263. }
  4264. static int __insert_orphan_inode(struct btrfs_trans_handle *trans,
  4265. struct btrfs_root *root,
  4266. u64 objectid, u64 size)
  4267. {
  4268. struct btrfs_path *path;
  4269. struct btrfs_inode_item *item;
  4270. struct extent_buffer *leaf;
  4271. int ret;
  4272. path = btrfs_alloc_path();
  4273. if (!path)
  4274. return -ENOMEM;
  4275. ret = btrfs_insert_empty_inode(trans, root, path, objectid);
  4276. if (ret)
  4277. goto out;
  4278. leaf = path->nodes[0];
  4279. item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
  4280. memset_extent_buffer(leaf, 0, (unsigned long)item, sizeof(*item));
  4281. btrfs_set_inode_generation(leaf, item, 1);
  4282. btrfs_set_inode_size(leaf, item, size);
  4283. btrfs_set_inode_mode(leaf, item, S_IFREG | 0600);
  4284. btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NODATASUM |
  4285. BTRFS_INODE_NOCOMPRESS);
  4286. btrfs_mark_buffer_dirty(leaf);
  4287. btrfs_release_path(root, path);
  4288. out:
  4289. btrfs_free_path(path);
  4290. return ret;
  4291. }
  4292. static struct inode noinline *create_reloc_inode(struct btrfs_fs_info *fs_info,
  4293. struct btrfs_block_group_cache *group)
  4294. {
  4295. struct inode *inode = NULL;
  4296. struct btrfs_trans_handle *trans;
  4297. struct btrfs_root *root;
  4298. struct btrfs_key root_key;
  4299. u64 objectid = BTRFS_FIRST_FREE_OBJECTID;
  4300. int err = 0;
  4301. root_key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
  4302. root_key.type = BTRFS_ROOT_ITEM_KEY;
  4303. root_key.offset = (u64)-1;
  4304. root = btrfs_read_fs_root_no_name(fs_info, &root_key);
  4305. if (IS_ERR(root))
  4306. return ERR_CAST(root);
  4307. trans = btrfs_start_transaction(root, 1);
  4308. BUG_ON(!trans);
  4309. err = btrfs_find_free_objectid(trans, root, objectid, &objectid);
  4310. if (err)
  4311. goto out;
  4312. err = __insert_orphan_inode(trans, root, objectid, group->key.offset);
  4313. BUG_ON(err);
  4314. err = btrfs_insert_file_extent(trans, root, objectid, 0, 0, 0,
  4315. group->key.offset, 0, group->key.offset,
  4316. 0, 0, 0);
  4317. BUG_ON(err);
  4318. inode = btrfs_iget_locked(root->fs_info->sb, objectid, root);
  4319. if (inode->i_state & I_NEW) {
  4320. BTRFS_I(inode)->root = root;
  4321. BTRFS_I(inode)->location.objectid = objectid;
  4322. BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
  4323. BTRFS_I(inode)->location.offset = 0;
  4324. btrfs_read_locked_inode(inode);
  4325. unlock_new_inode(inode);
  4326. BUG_ON(is_bad_inode(inode));
  4327. } else {
  4328. BUG_ON(1);
  4329. }
  4330. err = btrfs_orphan_add(trans, inode);
  4331. out:
  4332. btrfs_end_transaction(trans, root);
  4333. if (err) {
  4334. if (inode)
  4335. iput(inode);
  4336. inode = ERR_PTR(err);
  4337. }
  4338. return inode;
  4339. }
  4340. int btrfs_relocate_block_group(struct btrfs_root *root, u64 group_start)
  4341. {
  4342. struct btrfs_trans_handle *trans;
  4343. struct btrfs_path *path;
  4344. struct btrfs_fs_info *info = root->fs_info;
  4345. struct extent_buffer *leaf;
  4346. struct inode *reloc_inode;
  4347. struct btrfs_block_group_cache *block_group;
  4348. struct btrfs_key key;
  4349. u64 skipped;
  4350. u64 cur_byte;
  4351. u64 total_found;
  4352. u32 nritems;
  4353. int ret;
  4354. int progress;
  4355. int pass = 0;
  4356. root = root->fs_info->extent_root;
  4357. block_group = btrfs_lookup_block_group(info, group_start);
  4358. BUG_ON(!block_group);
  4359. printk("btrfs relocating block group %llu flags %llu\n",
  4360. (unsigned long long)block_group->key.objectid,
  4361. (unsigned long long)block_group->flags);
  4362. path = btrfs_alloc_path();
  4363. BUG_ON(!path);
  4364. reloc_inode = create_reloc_inode(info, block_group);
  4365. BUG_ON(IS_ERR(reloc_inode));
  4366. __alloc_chunk_for_shrink(root, block_group, 1);
  4367. block_group->ro = 1;
  4368. block_group->space_info->total_bytes -= block_group->key.offset;
  4369. btrfs_start_delalloc_inodes(info->tree_root);
  4370. btrfs_wait_ordered_extents(info->tree_root, 0);
  4371. again:
  4372. skipped = 0;
  4373. total_found = 0;
  4374. progress = 0;
  4375. key.objectid = block_group->key.objectid;
  4376. key.offset = 0;
  4377. key.type = 0;
  4378. cur_byte = key.objectid;
  4379. trans = btrfs_start_transaction(info->tree_root, 1);
  4380. btrfs_commit_transaction(trans, info->tree_root);
  4381. mutex_lock(&root->fs_info->cleaner_mutex);
  4382. btrfs_clean_old_snapshots(info->tree_root);
  4383. btrfs_remove_leaf_refs(info->tree_root, (u64)-1, 1);
  4384. mutex_unlock(&root->fs_info->cleaner_mutex);
  4385. while(1) {
  4386. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  4387. if (ret < 0)
  4388. goto out;
  4389. next:
  4390. leaf = path->nodes[0];
  4391. nritems = btrfs_header_nritems(leaf);
  4392. if (path->slots[0] >= nritems) {
  4393. ret = btrfs_next_leaf(root, path);
  4394. if (ret < 0)
  4395. goto out;
  4396. if (ret == 1) {
  4397. ret = 0;
  4398. break;
  4399. }
  4400. leaf = path->nodes[0];
  4401. nritems = btrfs_header_nritems(leaf);
  4402. }
  4403. btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  4404. if (key.objectid >= block_group->key.objectid +
  4405. block_group->key.offset)
  4406. break;
  4407. if (progress && need_resched()) {
  4408. btrfs_release_path(root, path);
  4409. cond_resched();
  4410. progress = 0;
  4411. continue;
  4412. }
  4413. progress = 1;
  4414. if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY ||
  4415. key.objectid + key.offset <= cur_byte) {
  4416. path->slots[0]++;
  4417. goto next;
  4418. }
  4419. total_found++;
  4420. cur_byte = key.objectid + key.offset;
  4421. btrfs_release_path(root, path);
  4422. __alloc_chunk_for_shrink(root, block_group, 0);
  4423. ret = relocate_one_extent(root, path, &key, block_group,
  4424. reloc_inode, pass);
  4425. BUG_ON(ret < 0);
  4426. if (ret > 0)
  4427. skipped++;
  4428. key.objectid = cur_byte;
  4429. key.type = 0;
  4430. key.offset = 0;
  4431. }
  4432. btrfs_release_path(root, path);
  4433. if (pass == 0) {
  4434. btrfs_wait_ordered_range(reloc_inode, 0, (u64)-1);
  4435. invalidate_mapping_pages(reloc_inode->i_mapping, 0, -1);
  4436. WARN_ON(reloc_inode->i_mapping->nrpages);
  4437. }
  4438. if (total_found > 0) {
  4439. printk("btrfs found %llu extents in pass %d\n",
  4440. (unsigned long long)total_found, pass);
  4441. pass++;
  4442. if (total_found == skipped && pass > 2) {
  4443. iput(reloc_inode);
  4444. reloc_inode = create_reloc_inode(info, block_group);
  4445. pass = 0;
  4446. }
  4447. goto again;
  4448. }
  4449. /* delete reloc_inode */
  4450. iput(reloc_inode);
  4451. /* unpin extents in this range */
  4452. trans = btrfs_start_transaction(info->tree_root, 1);
  4453. btrfs_commit_transaction(trans, info->tree_root);
  4454. spin_lock(&block_group->lock);
  4455. WARN_ON(block_group->pinned > 0);
  4456. WARN_ON(block_group->reserved > 0);
  4457. WARN_ON(btrfs_block_group_used(&block_group->item) > 0);
  4458. spin_unlock(&block_group->lock);
  4459. ret = 0;
  4460. out:
  4461. btrfs_free_path(path);
  4462. return ret;
  4463. }
  4464. int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
  4465. struct btrfs_key *key)
  4466. {
  4467. int ret = 0;
  4468. struct btrfs_key found_key;
  4469. struct extent_buffer *leaf;
  4470. int slot;
  4471. ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
  4472. if (ret < 0)
  4473. goto out;
  4474. while(1) {
  4475. slot = path->slots[0];
  4476. leaf = path->nodes[0];
  4477. if (slot >= btrfs_header_nritems(leaf)) {
  4478. ret = btrfs_next_leaf(root, path);
  4479. if (ret == 0)
  4480. continue;
  4481. if (ret < 0)
  4482. goto out;
  4483. break;
  4484. }
  4485. btrfs_item_key_to_cpu(leaf, &found_key, slot);
  4486. if (found_key.objectid >= key->objectid &&
  4487. found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
  4488. ret = 0;
  4489. goto out;
  4490. }
  4491. path->slots[0]++;
  4492. }
  4493. ret = -ENOENT;
  4494. out:
  4495. return ret;
  4496. }
  4497. int btrfs_free_block_groups(struct btrfs_fs_info *info)
  4498. {
  4499. struct btrfs_block_group_cache *block_group;
  4500. struct rb_node *n;
  4501. spin_lock(&info->block_group_cache_lock);
  4502. while ((n = rb_last(&info->block_group_cache_tree)) != NULL) {
  4503. block_group = rb_entry(n, struct btrfs_block_group_cache,
  4504. cache_node);
  4505. rb_erase(&block_group->cache_node,
  4506. &info->block_group_cache_tree);
  4507. spin_unlock(&info->block_group_cache_lock);
  4508. btrfs_remove_free_space_cache(block_group);
  4509. down_write(&block_group->space_info->groups_sem);
  4510. list_del(&block_group->list);
  4511. up_write(&block_group->space_info->groups_sem);
  4512. kfree(block_group);
  4513. spin_lock(&info->block_group_cache_lock);
  4514. }
  4515. spin_unlock(&info->block_group_cache_lock);
  4516. return 0;
  4517. }
  4518. int btrfs_read_block_groups(struct btrfs_root *root)
  4519. {
  4520. struct btrfs_path *path;
  4521. int ret;
  4522. struct btrfs_block_group_cache *cache;
  4523. struct btrfs_fs_info *info = root->fs_info;
  4524. struct btrfs_space_info *space_info;
  4525. struct btrfs_key key;
  4526. struct btrfs_key found_key;
  4527. struct extent_buffer *leaf;
  4528. root = info->extent_root;
  4529. key.objectid = 0;
  4530. key.offset = 0;
  4531. btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
  4532. path = btrfs_alloc_path();
  4533. if (!path)
  4534. return -ENOMEM;
  4535. while(1) {
  4536. ret = find_first_block_group(root, path, &key);
  4537. if (ret > 0) {
  4538. ret = 0;
  4539. goto error;
  4540. }
  4541. if (ret != 0)
  4542. goto error;
  4543. leaf = path->nodes[0];
  4544. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  4545. cache = kzalloc(sizeof(*cache), GFP_NOFS);
  4546. if (!cache) {
  4547. ret = -ENOMEM;
  4548. break;
  4549. }
  4550. spin_lock_init(&cache->lock);
  4551. mutex_init(&cache->alloc_mutex);
  4552. INIT_LIST_HEAD(&cache->list);
  4553. read_extent_buffer(leaf, &cache->item,
  4554. btrfs_item_ptr_offset(leaf, path->slots[0]),
  4555. sizeof(cache->item));
  4556. memcpy(&cache->key, &found_key, sizeof(found_key));
  4557. key.objectid = found_key.objectid + found_key.offset;
  4558. btrfs_release_path(root, path);
  4559. cache->flags = btrfs_block_group_flags(&cache->item);
  4560. ret = update_space_info(info, cache->flags, found_key.offset,
  4561. btrfs_block_group_used(&cache->item),
  4562. &space_info);
  4563. BUG_ON(ret);
  4564. cache->space_info = space_info;
  4565. down_write(&space_info->groups_sem);
  4566. list_add_tail(&cache->list, &space_info->block_groups);
  4567. up_write(&space_info->groups_sem);
  4568. ret = btrfs_add_block_group_cache(root->fs_info, cache);
  4569. BUG_ON(ret);
  4570. set_avail_alloc_bits(root->fs_info, cache->flags);
  4571. }
  4572. ret = 0;
  4573. error:
  4574. btrfs_free_path(path);
  4575. return ret;
  4576. }
  4577. int btrfs_make_block_group(struct btrfs_trans_handle *trans,
  4578. struct btrfs_root *root, u64 bytes_used,
  4579. u64 type, u64 chunk_objectid, u64 chunk_offset,
  4580. u64 size)
  4581. {
  4582. int ret;
  4583. struct btrfs_root *extent_root;
  4584. struct btrfs_block_group_cache *cache;
  4585. extent_root = root->fs_info->extent_root;
  4586. root->fs_info->last_trans_new_blockgroup = trans->transid;
  4587. cache = kzalloc(sizeof(*cache), GFP_NOFS);
  4588. if (!cache)
  4589. return -ENOMEM;
  4590. cache->key.objectid = chunk_offset;
  4591. cache->key.offset = size;
  4592. spin_lock_init(&cache->lock);
  4593. mutex_init(&cache->alloc_mutex);
  4594. INIT_LIST_HEAD(&cache->list);
  4595. btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
  4596. btrfs_set_block_group_used(&cache->item, bytes_used);
  4597. btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
  4598. cache->flags = type;
  4599. btrfs_set_block_group_flags(&cache->item, type);
  4600. ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
  4601. &cache->space_info);
  4602. BUG_ON(ret);
  4603. down_write(&cache->space_info->groups_sem);
  4604. list_add_tail(&cache->list, &cache->space_info->block_groups);
  4605. up_write(&cache->space_info->groups_sem);
  4606. ret = btrfs_add_block_group_cache(root->fs_info, cache);
  4607. BUG_ON(ret);
  4608. ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
  4609. sizeof(cache->item));
  4610. BUG_ON(ret);
  4611. finish_current_insert(trans, extent_root, 0);
  4612. ret = del_pending_extents(trans, extent_root, 0);
  4613. BUG_ON(ret);
  4614. set_avail_alloc_bits(extent_root->fs_info, type);
  4615. return 0;
  4616. }
  4617. int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
  4618. struct btrfs_root *root, u64 group_start)
  4619. {
  4620. struct btrfs_path *path;
  4621. struct btrfs_block_group_cache *block_group;
  4622. struct btrfs_key key;
  4623. int ret;
  4624. root = root->fs_info->extent_root;
  4625. block_group = btrfs_lookup_block_group(root->fs_info, group_start);
  4626. BUG_ON(!block_group);
  4627. memcpy(&key, &block_group->key, sizeof(key));
  4628. path = btrfs_alloc_path();
  4629. BUG_ON(!path);
  4630. btrfs_remove_free_space_cache(block_group);
  4631. rb_erase(&block_group->cache_node,
  4632. &root->fs_info->block_group_cache_tree);
  4633. down_write(&block_group->space_info->groups_sem);
  4634. list_del(&block_group->list);
  4635. up_write(&block_group->space_info->groups_sem);
  4636. /*
  4637. memset(shrink_block_group, 0, sizeof(*shrink_block_group));
  4638. kfree(shrink_block_group);
  4639. */
  4640. ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
  4641. if (ret > 0)
  4642. ret = -EIO;
  4643. if (ret < 0)
  4644. goto out;
  4645. ret = btrfs_del_item(trans, root, path);
  4646. out:
  4647. btrfs_free_path(path);
  4648. return ret;
  4649. }