mballoc.c 125 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572457345744575457645774578457945804581458245834584458545864587458845894590459145924593459445954596459745984599460046014602460346044605460646074608460946104611461246134614461546164617461846194620462146224623462446254626462746284629463046314632463346344635463646374638463946404641464246434644464546464647
  1. /*
  2. * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
  3. * Written by Alex Tomas <alex@clusterfs.com>
  4. *
  5. * This program is free software; you can redistribute it and/or modify
  6. * it under the terms of the GNU General Public License version 2 as
  7. * published by the Free Software Foundation.
  8. *
  9. * This program is distributed in the hope that it will be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public Licens
  15. * along with this program; if not, write to the Free Software
  16. * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-
  17. */
  18. /*
  19. * mballoc.c contains the multiblocks allocation routines
  20. */
  21. #include "mballoc.h"
  22. /*
  23. * MUSTDO:
  24. * - test ext4_ext_search_left() and ext4_ext_search_right()
  25. * - search for metadata in few groups
  26. *
  27. * TODO v4:
  28. * - normalization should take into account whether file is still open
  29. * - discard preallocations if no free space left (policy?)
  30. * - don't normalize tails
  31. * - quota
  32. * - reservation for superuser
  33. *
  34. * TODO v3:
  35. * - bitmap read-ahead (proposed by Oleg Drokin aka green)
  36. * - track min/max extents in each group for better group selection
  37. * - mb_mark_used() may allocate chunk right after splitting buddy
  38. * - tree of groups sorted by number of free blocks
  39. * - error handling
  40. */
  41. /*
  42. * The allocation request involve request for multiple number of blocks
  43. * near to the goal(block) value specified.
  44. *
  45. * During initialization phase of the allocator we decide to use the group
  46. * preallocation or inode preallocation depending on the size file. The
  47. * size of the file could be the resulting file size we would have after
  48. * allocation or the current file size which ever is larger. If the size is
  49. * less that sbi->s_mb_stream_request we select the group
  50. * preallocation. The default value of s_mb_stream_request is 16
  51. * blocks. This can also be tuned via
  52. * /proc/fs/ext4/<partition>/stream_req. The value is represented in terms
  53. * of number of blocks.
  54. *
  55. * The main motivation for having small file use group preallocation is to
  56. * ensure that we have small file closer in the disk.
  57. *
  58. * First stage the allocator looks at the inode prealloc list
  59. * ext4_inode_info->i_prealloc_list contain list of prealloc spaces for
  60. * this particular inode. The inode prealloc space is represented as:
  61. *
  62. * pa_lstart -> the logical start block for this prealloc space
  63. * pa_pstart -> the physical start block for this prealloc space
  64. * pa_len -> lenght for this prealloc space
  65. * pa_free -> free space available in this prealloc space
  66. *
  67. * The inode preallocation space is used looking at the _logical_ start
  68. * block. If only the logical file block falls within the range of prealloc
  69. * space we will consume the particular prealloc space. This make sure that
  70. * that the we have contiguous physical blocks representing the file blocks
  71. *
  72. * The important thing to be noted in case of inode prealloc space is that
  73. * we don't modify the values associated to inode prealloc space except
  74. * pa_free.
  75. *
  76. * If we are not able to find blocks in the inode prealloc space and if we
  77. * have the group allocation flag set then we look at the locality group
  78. * prealloc space. These are per CPU prealloc list repreasented as
  79. *
  80. * ext4_sb_info.s_locality_groups[smp_processor_id()]
  81. *
  82. * The reason for having a per cpu locality group is to reduce the contention
  83. * between CPUs. It is possible to get scheduled at this point.
  84. *
  85. * The locality group prealloc space is used looking at whether we have
  86. * enough free space (pa_free) withing the prealloc space.
  87. *
  88. * If we can't allocate blocks via inode prealloc or/and locality group
  89. * prealloc then we look at the buddy cache. The buddy cache is represented
  90. * by ext4_sb_info.s_buddy_cache (struct inode) whose file offset gets
  91. * mapped to the buddy and bitmap information regarding different
  92. * groups. The buddy information is attached to buddy cache inode so that
  93. * we can access them through the page cache. The information regarding
  94. * each group is loaded via ext4_mb_load_buddy. The information involve
  95. * block bitmap and buddy information. The information are stored in the
  96. * inode as:
  97. *
  98. * { page }
  99. * [ group 0 buddy][ group 0 bitmap] [group 1][ group 1]...
  100. *
  101. *
  102. * one block each for bitmap and buddy information. So for each group we
  103. * take up 2 blocks. A page can contain blocks_per_page (PAGE_CACHE_SIZE /
  104. * blocksize) blocks. So it can have information regarding groups_per_page
  105. * which is blocks_per_page/2
  106. *
  107. * The buddy cache inode is not stored on disk. The inode is thrown
  108. * away when the filesystem is unmounted.
  109. *
  110. * We look for count number of blocks in the buddy cache. If we were able
  111. * to locate that many free blocks we return with additional information
  112. * regarding rest of the contiguous physical block available
  113. *
  114. * Before allocating blocks via buddy cache we normalize the request
  115. * blocks. This ensure we ask for more blocks that we needed. The extra
  116. * blocks that we get after allocation is added to the respective prealloc
  117. * list. In case of inode preallocation we follow a list of heuristics
  118. * based on file size. This can be found in ext4_mb_normalize_request. If
  119. * we are doing a group prealloc we try to normalize the request to
  120. * sbi->s_mb_group_prealloc. Default value of s_mb_group_prealloc is set to
  121. * 512 blocks. This can be tuned via
  122. * /proc/fs/ext4/<partition/group_prealloc. The value is represented in
  123. * terms of number of blocks. If we have mounted the file system with -O
  124. * stripe=<value> option the group prealloc request is normalized to the
  125. * stripe value (sbi->s_stripe)
  126. *
  127. * The regular allocator(using the buddy cache) support few tunables.
  128. *
  129. * /proc/fs/ext4/<partition>/min_to_scan
  130. * /proc/fs/ext4/<partition>/max_to_scan
  131. * /proc/fs/ext4/<partition>/order2_req
  132. *
  133. * The regular allocator use buddy scan only if the request len is power of
  134. * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The
  135. * value of s_mb_order2_reqs can be tuned via
  136. * /proc/fs/ext4/<partition>/order2_req. If the request len is equal to
  137. * stripe size (sbi->s_stripe), we try to search for contigous block in
  138. * stripe size. This should result in better allocation on RAID setup. If
  139. * not we search in the specific group using bitmap for best extents. The
  140. * tunable min_to_scan and max_to_scan controll the behaviour here.
  141. * min_to_scan indicate how long the mballoc __must__ look for a best
  142. * extent and max_to_scanindicate how long the mballoc __can__ look for a
  143. * best extent in the found extents. Searching for the blocks starts with
  144. * the group specified as the goal value in allocation context via
  145. * ac_g_ex. Each group is first checked based on the criteria whether it
  146. * can used for allocation. ext4_mb_good_group explains how the groups are
  147. * checked.
  148. *
  149. * Both the prealloc space are getting populated as above. So for the first
  150. * request we will hit the buddy cache which will result in this prealloc
  151. * space getting filled. The prealloc space is then later used for the
  152. * subsequent request.
  153. */
  154. /*
  155. * mballoc operates on the following data:
  156. * - on-disk bitmap
  157. * - in-core buddy (actually includes buddy and bitmap)
  158. * - preallocation descriptors (PAs)
  159. *
  160. * there are two types of preallocations:
  161. * - inode
  162. * assiged to specific inode and can be used for this inode only.
  163. * it describes part of inode's space preallocated to specific
  164. * physical blocks. any block from that preallocated can be used
  165. * independent. the descriptor just tracks number of blocks left
  166. * unused. so, before taking some block from descriptor, one must
  167. * make sure corresponded logical block isn't allocated yet. this
  168. * also means that freeing any block within descriptor's range
  169. * must discard all preallocated blocks.
  170. * - locality group
  171. * assigned to specific locality group which does not translate to
  172. * permanent set of inodes: inode can join and leave group. space
  173. * from this type of preallocation can be used for any inode. thus
  174. * it's consumed from the beginning to the end.
  175. *
  176. * relation between them can be expressed as:
  177. * in-core buddy = on-disk bitmap + preallocation descriptors
  178. *
  179. * this mean blocks mballoc considers used are:
  180. * - allocated blocks (persistent)
  181. * - preallocated blocks (non-persistent)
  182. *
  183. * consistency in mballoc world means that at any time a block is either
  184. * free or used in ALL structures. notice: "any time" should not be read
  185. * literally -- time is discrete and delimited by locks.
  186. *
  187. * to keep it simple, we don't use block numbers, instead we count number of
  188. * blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA.
  189. *
  190. * all operations can be expressed as:
  191. * - init buddy: buddy = on-disk + PAs
  192. * - new PA: buddy += N; PA = N
  193. * - use inode PA: on-disk += N; PA -= N
  194. * - discard inode PA buddy -= on-disk - PA; PA = 0
  195. * - use locality group PA on-disk += N; PA -= N
  196. * - discard locality group PA buddy -= PA; PA = 0
  197. * note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap
  198. * is used in real operation because we can't know actual used
  199. * bits from PA, only from on-disk bitmap
  200. *
  201. * if we follow this strict logic, then all operations above should be atomic.
  202. * given some of them can block, we'd have to use something like semaphores
  203. * killing performance on high-end SMP hardware. let's try to relax it using
  204. * the following knowledge:
  205. * 1) if buddy is referenced, it's already initialized
  206. * 2) while block is used in buddy and the buddy is referenced,
  207. * nobody can re-allocate that block
  208. * 3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has
  209. * bit set and PA claims same block, it's OK. IOW, one can set bit in
  210. * on-disk bitmap if buddy has same bit set or/and PA covers corresponded
  211. * block
  212. *
  213. * so, now we're building a concurrency table:
  214. * - init buddy vs.
  215. * - new PA
  216. * blocks for PA are allocated in the buddy, buddy must be referenced
  217. * until PA is linked to allocation group to avoid concurrent buddy init
  218. * - use inode PA
  219. * we need to make sure that either on-disk bitmap or PA has uptodate data
  220. * given (3) we care that PA-=N operation doesn't interfere with init
  221. * - discard inode PA
  222. * the simplest way would be to have buddy initialized by the discard
  223. * - use locality group PA
  224. * again PA-=N must be serialized with init
  225. * - discard locality group PA
  226. * the simplest way would be to have buddy initialized by the discard
  227. * - new PA vs.
  228. * - use inode PA
  229. * i_data_sem serializes them
  230. * - discard inode PA
  231. * discard process must wait until PA isn't used by another process
  232. * - use locality group PA
  233. * some mutex should serialize them
  234. * - discard locality group PA
  235. * discard process must wait until PA isn't used by another process
  236. * - use inode PA
  237. * - use inode PA
  238. * i_data_sem or another mutex should serializes them
  239. * - discard inode PA
  240. * discard process must wait until PA isn't used by another process
  241. * - use locality group PA
  242. * nothing wrong here -- they're different PAs covering different blocks
  243. * - discard locality group PA
  244. * discard process must wait until PA isn't used by another process
  245. *
  246. * now we're ready to make few consequences:
  247. * - PA is referenced and while it is no discard is possible
  248. * - PA is referenced until block isn't marked in on-disk bitmap
  249. * - PA changes only after on-disk bitmap
  250. * - discard must not compete with init. either init is done before
  251. * any discard or they're serialized somehow
  252. * - buddy init as sum of on-disk bitmap and PAs is done atomically
  253. *
  254. * a special case when we've used PA to emptiness. no need to modify buddy
  255. * in this case, but we should care about concurrent init
  256. *
  257. */
  258. /*
  259. * Logic in few words:
  260. *
  261. * - allocation:
  262. * load group
  263. * find blocks
  264. * mark bits in on-disk bitmap
  265. * release group
  266. *
  267. * - use preallocation:
  268. * find proper PA (per-inode or group)
  269. * load group
  270. * mark bits in on-disk bitmap
  271. * release group
  272. * release PA
  273. *
  274. * - free:
  275. * load group
  276. * mark bits in on-disk bitmap
  277. * release group
  278. *
  279. * - discard preallocations in group:
  280. * mark PAs deleted
  281. * move them onto local list
  282. * load on-disk bitmap
  283. * load group
  284. * remove PA from object (inode or locality group)
  285. * mark free blocks in-core
  286. *
  287. * - discard inode's preallocations:
  288. */
  289. /*
  290. * Locking rules
  291. *
  292. * Locks:
  293. * - bitlock on a group (group)
  294. * - object (inode/locality) (object)
  295. * - per-pa lock (pa)
  296. *
  297. * Paths:
  298. * - new pa
  299. * object
  300. * group
  301. *
  302. * - find and use pa:
  303. * pa
  304. *
  305. * - release consumed pa:
  306. * pa
  307. * group
  308. * object
  309. *
  310. * - generate in-core bitmap:
  311. * group
  312. * pa
  313. *
  314. * - discard all for given object (inode, locality group):
  315. * object
  316. * pa
  317. * group
  318. *
  319. * - discard all for given group:
  320. * group
  321. * pa
  322. * group
  323. * object
  324. *
  325. */
  326. static inline void *mb_correct_addr_and_bit(int *bit, void *addr)
  327. {
  328. #if BITS_PER_LONG == 64
  329. *bit += ((unsigned long) addr & 7UL) << 3;
  330. addr = (void *) ((unsigned long) addr & ~7UL);
  331. #elif BITS_PER_LONG == 32
  332. *bit += ((unsigned long) addr & 3UL) << 3;
  333. addr = (void *) ((unsigned long) addr & ~3UL);
  334. #else
  335. #error "how many bits you are?!"
  336. #endif
  337. return addr;
  338. }
  339. static inline int mb_test_bit(int bit, void *addr)
  340. {
  341. /*
  342. * ext4_test_bit on architecture like powerpc
  343. * needs unsigned long aligned address
  344. */
  345. addr = mb_correct_addr_and_bit(&bit, addr);
  346. return ext4_test_bit(bit, addr);
  347. }
  348. static inline void mb_set_bit(int bit, void *addr)
  349. {
  350. addr = mb_correct_addr_and_bit(&bit, addr);
  351. ext4_set_bit(bit, addr);
  352. }
  353. static inline void mb_set_bit_atomic(spinlock_t *lock, int bit, void *addr)
  354. {
  355. addr = mb_correct_addr_and_bit(&bit, addr);
  356. ext4_set_bit_atomic(lock, bit, addr);
  357. }
  358. static inline void mb_clear_bit(int bit, void *addr)
  359. {
  360. addr = mb_correct_addr_and_bit(&bit, addr);
  361. ext4_clear_bit(bit, addr);
  362. }
  363. static inline void mb_clear_bit_atomic(spinlock_t *lock, int bit, void *addr)
  364. {
  365. addr = mb_correct_addr_and_bit(&bit, addr);
  366. ext4_clear_bit_atomic(lock, bit, addr);
  367. }
  368. static inline int mb_find_next_zero_bit(void *addr, int max, int start)
  369. {
  370. int fix = 0, ret, tmpmax;
  371. addr = mb_correct_addr_and_bit(&fix, addr);
  372. tmpmax = max + fix;
  373. start += fix;
  374. ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix;
  375. if (ret > max)
  376. return max;
  377. return ret;
  378. }
  379. static inline int mb_find_next_bit(void *addr, int max, int start)
  380. {
  381. int fix = 0, ret, tmpmax;
  382. addr = mb_correct_addr_and_bit(&fix, addr);
  383. tmpmax = max + fix;
  384. start += fix;
  385. ret = ext4_find_next_bit(addr, tmpmax, start) - fix;
  386. if (ret > max)
  387. return max;
  388. return ret;
  389. }
  390. static void *mb_find_buddy(struct ext4_buddy *e4b, int order, int *max)
  391. {
  392. char *bb;
  393. BUG_ON(EXT4_MB_BITMAP(e4b) == EXT4_MB_BUDDY(e4b));
  394. BUG_ON(max == NULL);
  395. if (order > e4b->bd_blkbits + 1) {
  396. *max = 0;
  397. return NULL;
  398. }
  399. /* at order 0 we see each particular block */
  400. *max = 1 << (e4b->bd_blkbits + 3);
  401. if (order == 0)
  402. return EXT4_MB_BITMAP(e4b);
  403. bb = EXT4_MB_BUDDY(e4b) + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order];
  404. *max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order];
  405. return bb;
  406. }
  407. #ifdef DOUBLE_CHECK
  408. static void mb_free_blocks_double(struct inode *inode, struct ext4_buddy *e4b,
  409. int first, int count)
  410. {
  411. int i;
  412. struct super_block *sb = e4b->bd_sb;
  413. if (unlikely(e4b->bd_info->bb_bitmap == NULL))
  414. return;
  415. BUG_ON(!ext4_is_group_locked(sb, e4b->bd_group));
  416. for (i = 0; i < count; i++) {
  417. if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) {
  418. ext4_fsblk_t blocknr;
  419. blocknr = e4b->bd_group * EXT4_BLOCKS_PER_GROUP(sb);
  420. blocknr += first + i;
  421. blocknr +=
  422. le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
  423. ext4_error(sb, __func__, "double-free of inode"
  424. " %lu's block %llu(bit %u in group %lu)\n",
  425. inode ? inode->i_ino : 0, blocknr,
  426. first + i, e4b->bd_group);
  427. }
  428. mb_clear_bit(first + i, e4b->bd_info->bb_bitmap);
  429. }
  430. }
  431. static void mb_mark_used_double(struct ext4_buddy *e4b, int first, int count)
  432. {
  433. int i;
  434. if (unlikely(e4b->bd_info->bb_bitmap == NULL))
  435. return;
  436. BUG_ON(!ext4_is_group_locked(e4b->bd_sb, e4b->bd_group));
  437. for (i = 0; i < count; i++) {
  438. BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap));
  439. mb_set_bit(first + i, e4b->bd_info->bb_bitmap);
  440. }
  441. }
  442. static void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
  443. {
  444. if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) {
  445. unsigned char *b1, *b2;
  446. int i;
  447. b1 = (unsigned char *) e4b->bd_info->bb_bitmap;
  448. b2 = (unsigned char *) bitmap;
  449. for (i = 0; i < e4b->bd_sb->s_blocksize; i++) {
  450. if (b1[i] != b2[i]) {
  451. printk(KERN_ERR "corruption in group %lu "
  452. "at byte %u(%u): %x in copy != %x "
  453. "on disk/prealloc\n",
  454. e4b->bd_group, i, i * 8, b1[i], b2[i]);
  455. BUG();
  456. }
  457. }
  458. }
  459. }
  460. #else
  461. static inline void mb_free_blocks_double(struct inode *inode,
  462. struct ext4_buddy *e4b, int first, int count)
  463. {
  464. return;
  465. }
  466. static inline void mb_mark_used_double(struct ext4_buddy *e4b,
  467. int first, int count)
  468. {
  469. return;
  470. }
  471. static inline void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
  472. {
  473. return;
  474. }
  475. #endif
  476. #ifdef AGGRESSIVE_CHECK
  477. #define MB_CHECK_ASSERT(assert) \
  478. do { \
  479. if (!(assert)) { \
  480. printk(KERN_EMERG \
  481. "Assertion failure in %s() at %s:%d: \"%s\"\n", \
  482. function, file, line, # assert); \
  483. BUG(); \
  484. } \
  485. } while (0)
  486. static int __mb_check_buddy(struct ext4_buddy *e4b, char *file,
  487. const char *function, int line)
  488. {
  489. struct super_block *sb = e4b->bd_sb;
  490. int order = e4b->bd_blkbits + 1;
  491. int max;
  492. int max2;
  493. int i;
  494. int j;
  495. int k;
  496. int count;
  497. struct ext4_group_info *grp;
  498. int fragments = 0;
  499. int fstart;
  500. struct list_head *cur;
  501. void *buddy;
  502. void *buddy2;
  503. {
  504. static int mb_check_counter;
  505. if (mb_check_counter++ % 100 != 0)
  506. return 0;
  507. }
  508. while (order > 1) {
  509. buddy = mb_find_buddy(e4b, order, &max);
  510. MB_CHECK_ASSERT(buddy);
  511. buddy2 = mb_find_buddy(e4b, order - 1, &max2);
  512. MB_CHECK_ASSERT(buddy2);
  513. MB_CHECK_ASSERT(buddy != buddy2);
  514. MB_CHECK_ASSERT(max * 2 == max2);
  515. count = 0;
  516. for (i = 0; i < max; i++) {
  517. if (mb_test_bit(i, buddy)) {
  518. /* only single bit in buddy2 may be 1 */
  519. if (!mb_test_bit(i << 1, buddy2)) {
  520. MB_CHECK_ASSERT(
  521. mb_test_bit((i<<1)+1, buddy2));
  522. } else if (!mb_test_bit((i << 1) + 1, buddy2)) {
  523. MB_CHECK_ASSERT(
  524. mb_test_bit(i << 1, buddy2));
  525. }
  526. continue;
  527. }
  528. /* both bits in buddy2 must be 0 */
  529. MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2));
  530. MB_CHECK_ASSERT(mb_test_bit((i << 1) + 1, buddy2));
  531. for (j = 0; j < (1 << order); j++) {
  532. k = (i * (1 << order)) + j;
  533. MB_CHECK_ASSERT(
  534. !mb_test_bit(k, EXT4_MB_BITMAP(e4b)));
  535. }
  536. count++;
  537. }
  538. MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);
  539. order--;
  540. }
  541. fstart = -1;
  542. buddy = mb_find_buddy(e4b, 0, &max);
  543. for (i = 0; i < max; i++) {
  544. if (!mb_test_bit(i, buddy)) {
  545. MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free);
  546. if (fstart == -1) {
  547. fragments++;
  548. fstart = i;
  549. }
  550. continue;
  551. }
  552. fstart = -1;
  553. /* check used bits only */
  554. for (j = 0; j < e4b->bd_blkbits + 1; j++) {
  555. buddy2 = mb_find_buddy(e4b, j, &max2);
  556. k = i >> j;
  557. MB_CHECK_ASSERT(k < max2);
  558. MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
  559. }
  560. }
  561. MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));
  562. MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments);
  563. grp = ext4_get_group_info(sb, e4b->bd_group);
  564. buddy = mb_find_buddy(e4b, 0, &max);
  565. list_for_each(cur, &grp->bb_prealloc_list) {
  566. ext4_group_t groupnr;
  567. struct ext4_prealloc_space *pa;
  568. pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
  569. ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);
  570. MB_CHECK_ASSERT(groupnr == e4b->bd_group);
  571. for (i = 0; i < pa->pa_len; i++)
  572. MB_CHECK_ASSERT(mb_test_bit(k + i, buddy));
  573. }
  574. return 0;
  575. }
  576. #undef MB_CHECK_ASSERT
  577. #define mb_check_buddy(e4b) __mb_check_buddy(e4b, \
  578. __FILE__, __func__, __LINE__)
  579. #else
  580. #define mb_check_buddy(e4b)
  581. #endif
  582. /* FIXME!! need more doc */
  583. static void ext4_mb_mark_free_simple(struct super_block *sb,
  584. void *buddy, unsigned first, int len,
  585. struct ext4_group_info *grp)
  586. {
  587. struct ext4_sb_info *sbi = EXT4_SB(sb);
  588. unsigned short min;
  589. unsigned short max;
  590. unsigned short chunk;
  591. unsigned short border;
  592. BUG_ON(len > EXT4_BLOCKS_PER_GROUP(sb));
  593. border = 2 << sb->s_blocksize_bits;
  594. while (len > 0) {
  595. /* find how many blocks can be covered since this position */
  596. max = ffs(first | border) - 1;
  597. /* find how many blocks of power 2 we need to mark */
  598. min = fls(len) - 1;
  599. if (max < min)
  600. min = max;
  601. chunk = 1 << min;
  602. /* mark multiblock chunks only */
  603. grp->bb_counters[min]++;
  604. if (min > 0)
  605. mb_clear_bit(first >> min,
  606. buddy + sbi->s_mb_offsets[min]);
  607. len -= chunk;
  608. first += chunk;
  609. }
  610. }
  611. static void ext4_mb_generate_buddy(struct super_block *sb,
  612. void *buddy, void *bitmap, ext4_group_t group)
  613. {
  614. struct ext4_group_info *grp = ext4_get_group_info(sb, group);
  615. unsigned short max = EXT4_BLOCKS_PER_GROUP(sb);
  616. unsigned short i = 0;
  617. unsigned short first;
  618. unsigned short len;
  619. unsigned free = 0;
  620. unsigned fragments = 0;
  621. unsigned long long period = get_cycles();
  622. /* initialize buddy from bitmap which is aggregation
  623. * of on-disk bitmap and preallocations */
  624. i = mb_find_next_zero_bit(bitmap, max, 0);
  625. grp->bb_first_free = i;
  626. while (i < max) {
  627. fragments++;
  628. first = i;
  629. i = mb_find_next_bit(bitmap, max, i);
  630. len = i - first;
  631. free += len;
  632. if (len > 1)
  633. ext4_mb_mark_free_simple(sb, buddy, first, len, grp);
  634. else
  635. grp->bb_counters[0]++;
  636. if (i < max)
  637. i = mb_find_next_zero_bit(bitmap, max, i);
  638. }
  639. grp->bb_fragments = fragments;
  640. if (free != grp->bb_free) {
  641. ext4_error(sb, __func__,
  642. "EXT4-fs: group %lu: %u blocks in bitmap, %u in gd\n",
  643. group, free, grp->bb_free);
  644. /*
  645. * If we intent to continue, we consider group descritor
  646. * corrupt and update bb_free using bitmap value
  647. */
  648. grp->bb_free = free;
  649. }
  650. clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));
  651. period = get_cycles() - period;
  652. spin_lock(&EXT4_SB(sb)->s_bal_lock);
  653. EXT4_SB(sb)->s_mb_buddies_generated++;
  654. EXT4_SB(sb)->s_mb_generation_time += period;
  655. spin_unlock(&EXT4_SB(sb)->s_bal_lock);
  656. }
  657. /* The buddy information is attached the buddy cache inode
  658. * for convenience. The information regarding each group
  659. * is loaded via ext4_mb_load_buddy. The information involve
  660. * block bitmap and buddy information. The information are
  661. * stored in the inode as
  662. *
  663. * { page }
  664. * [ group 0 buddy][ group 0 bitmap] [group 1][ group 1]...
  665. *
  666. *
  667. * one block each for bitmap and buddy information.
  668. * So for each group we take up 2 blocks. A page can
  669. * contain blocks_per_page (PAGE_CACHE_SIZE / blocksize) blocks.
  670. * So it can have information regarding groups_per_page which
  671. * is blocks_per_page/2
  672. */
  673. static int ext4_mb_init_cache(struct page *page, char *incore)
  674. {
  675. int blocksize;
  676. int blocks_per_page;
  677. int groups_per_page;
  678. int err = 0;
  679. int i;
  680. ext4_group_t first_group;
  681. int first_block;
  682. struct super_block *sb;
  683. struct buffer_head *bhs;
  684. struct buffer_head **bh;
  685. struct inode *inode;
  686. char *data;
  687. char *bitmap;
  688. mb_debug("init page %lu\n", page->index);
  689. inode = page->mapping->host;
  690. sb = inode->i_sb;
  691. blocksize = 1 << inode->i_blkbits;
  692. blocks_per_page = PAGE_CACHE_SIZE / blocksize;
  693. groups_per_page = blocks_per_page >> 1;
  694. if (groups_per_page == 0)
  695. groups_per_page = 1;
  696. /* allocate buffer_heads to read bitmaps */
  697. if (groups_per_page > 1) {
  698. err = -ENOMEM;
  699. i = sizeof(struct buffer_head *) * groups_per_page;
  700. bh = kzalloc(i, GFP_NOFS);
  701. if (bh == NULL)
  702. goto out;
  703. } else
  704. bh = &bhs;
  705. first_group = page->index * blocks_per_page / 2;
  706. /* read all groups the page covers into the cache */
  707. for (i = 0; i < groups_per_page; i++) {
  708. struct ext4_group_desc *desc;
  709. if (first_group + i >= EXT4_SB(sb)->s_groups_count)
  710. break;
  711. err = -EIO;
  712. desc = ext4_get_group_desc(sb, first_group + i, NULL);
  713. if (desc == NULL)
  714. goto out;
  715. err = -ENOMEM;
  716. bh[i] = sb_getblk(sb, ext4_block_bitmap(sb, desc));
  717. if (bh[i] == NULL)
  718. goto out;
  719. if (bh_uptodate_or_lock(bh[i]))
  720. continue;
  721. spin_lock(sb_bgl_lock(EXT4_SB(sb), first_group + i));
  722. if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
  723. ext4_init_block_bitmap(sb, bh[i],
  724. first_group + i, desc);
  725. set_buffer_uptodate(bh[i]);
  726. unlock_buffer(bh[i]);
  727. spin_unlock(sb_bgl_lock(EXT4_SB(sb), first_group + i));
  728. continue;
  729. }
  730. spin_unlock(sb_bgl_lock(EXT4_SB(sb), first_group + i));
  731. get_bh(bh[i]);
  732. bh[i]->b_end_io = end_buffer_read_sync;
  733. submit_bh(READ, bh[i]);
  734. mb_debug("read bitmap for group %lu\n", first_group + i);
  735. }
  736. /* wait for I/O completion */
  737. for (i = 0; i < groups_per_page && bh[i]; i++)
  738. wait_on_buffer(bh[i]);
  739. err = -EIO;
  740. for (i = 0; i < groups_per_page && bh[i]; i++)
  741. if (!buffer_uptodate(bh[i]))
  742. goto out;
  743. err = 0;
  744. first_block = page->index * blocks_per_page;
  745. for (i = 0; i < blocks_per_page; i++) {
  746. int group;
  747. struct ext4_group_info *grinfo;
  748. group = (first_block + i) >> 1;
  749. if (group >= EXT4_SB(sb)->s_groups_count)
  750. break;
  751. /*
  752. * data carry information regarding this
  753. * particular group in the format specified
  754. * above
  755. *
  756. */
  757. data = page_address(page) + (i * blocksize);
  758. bitmap = bh[group - first_group]->b_data;
  759. /*
  760. * We place the buddy block and bitmap block
  761. * close together
  762. */
  763. if ((first_block + i) & 1) {
  764. /* this is block of buddy */
  765. BUG_ON(incore == NULL);
  766. mb_debug("put buddy for group %u in page %lu/%x\n",
  767. group, page->index, i * blocksize);
  768. memset(data, 0xff, blocksize);
  769. grinfo = ext4_get_group_info(sb, group);
  770. grinfo->bb_fragments = 0;
  771. memset(grinfo->bb_counters, 0,
  772. sizeof(unsigned short)*(sb->s_blocksize_bits+2));
  773. /*
  774. * incore got set to the group block bitmap below
  775. */
  776. ext4_mb_generate_buddy(sb, data, incore, group);
  777. incore = NULL;
  778. } else {
  779. /* this is block of bitmap */
  780. BUG_ON(incore != NULL);
  781. mb_debug("put bitmap for group %u in page %lu/%x\n",
  782. group, page->index, i * blocksize);
  783. /* see comments in ext4_mb_put_pa() */
  784. ext4_lock_group(sb, group);
  785. memcpy(data, bitmap, blocksize);
  786. /* mark all preallocated blks used in in-core bitmap */
  787. ext4_mb_generate_from_pa(sb, data, group);
  788. ext4_unlock_group(sb, group);
  789. /* set incore so that the buddy information can be
  790. * generated using this
  791. */
  792. incore = data;
  793. }
  794. }
  795. SetPageUptodate(page);
  796. out:
  797. if (bh) {
  798. for (i = 0; i < groups_per_page && bh[i]; i++)
  799. brelse(bh[i]);
  800. if (bh != &bhs)
  801. kfree(bh);
  802. }
  803. return err;
  804. }
  805. static noinline_for_stack int
  806. ext4_mb_load_buddy(struct super_block *sb, ext4_group_t group,
  807. struct ext4_buddy *e4b)
  808. {
  809. struct ext4_sb_info *sbi = EXT4_SB(sb);
  810. struct inode *inode = sbi->s_buddy_cache;
  811. int blocks_per_page;
  812. int block;
  813. int pnum;
  814. int poff;
  815. struct page *page;
  816. int ret;
  817. mb_debug("load group %lu\n", group);
  818. blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
  819. e4b->bd_blkbits = sb->s_blocksize_bits;
  820. e4b->bd_info = ext4_get_group_info(sb, group);
  821. e4b->bd_sb = sb;
  822. e4b->bd_group = group;
  823. e4b->bd_buddy_page = NULL;
  824. e4b->bd_bitmap_page = NULL;
  825. /*
  826. * the buddy cache inode stores the block bitmap
  827. * and buddy information in consecutive blocks.
  828. * So for each group we need two blocks.
  829. */
  830. block = group * 2;
  831. pnum = block / blocks_per_page;
  832. poff = block % blocks_per_page;
  833. /* we could use find_or_create_page(), but it locks page
  834. * what we'd like to avoid in fast path ... */
  835. page = find_get_page(inode->i_mapping, pnum);
  836. if (page == NULL || !PageUptodate(page)) {
  837. if (page)
  838. page_cache_release(page);
  839. page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
  840. if (page) {
  841. BUG_ON(page->mapping != inode->i_mapping);
  842. if (!PageUptodate(page)) {
  843. ret = ext4_mb_init_cache(page, NULL);
  844. if (ret) {
  845. unlock_page(page);
  846. goto err;
  847. }
  848. mb_cmp_bitmaps(e4b, page_address(page) +
  849. (poff * sb->s_blocksize));
  850. }
  851. unlock_page(page);
  852. }
  853. }
  854. if (page == NULL || !PageUptodate(page)) {
  855. ret = -EIO;
  856. goto err;
  857. }
  858. e4b->bd_bitmap_page = page;
  859. e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);
  860. mark_page_accessed(page);
  861. block++;
  862. pnum = block / blocks_per_page;
  863. poff = block % blocks_per_page;
  864. page = find_get_page(inode->i_mapping, pnum);
  865. if (page == NULL || !PageUptodate(page)) {
  866. if (page)
  867. page_cache_release(page);
  868. page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
  869. if (page) {
  870. BUG_ON(page->mapping != inode->i_mapping);
  871. if (!PageUptodate(page)) {
  872. ret = ext4_mb_init_cache(page, e4b->bd_bitmap);
  873. if (ret) {
  874. unlock_page(page);
  875. goto err;
  876. }
  877. }
  878. unlock_page(page);
  879. }
  880. }
  881. if (page == NULL || !PageUptodate(page)) {
  882. ret = -EIO;
  883. goto err;
  884. }
  885. e4b->bd_buddy_page = page;
  886. e4b->bd_buddy = page_address(page) + (poff * sb->s_blocksize);
  887. mark_page_accessed(page);
  888. BUG_ON(e4b->bd_bitmap_page == NULL);
  889. BUG_ON(e4b->bd_buddy_page == NULL);
  890. return 0;
  891. err:
  892. if (e4b->bd_bitmap_page)
  893. page_cache_release(e4b->bd_bitmap_page);
  894. if (e4b->bd_buddy_page)
  895. page_cache_release(e4b->bd_buddy_page);
  896. e4b->bd_buddy = NULL;
  897. e4b->bd_bitmap = NULL;
  898. return ret;
  899. }
  900. static void ext4_mb_release_desc(struct ext4_buddy *e4b)
  901. {
  902. if (e4b->bd_bitmap_page)
  903. page_cache_release(e4b->bd_bitmap_page);
  904. if (e4b->bd_buddy_page)
  905. page_cache_release(e4b->bd_buddy_page);
  906. }
  907. static int mb_find_order_for_block(struct ext4_buddy *e4b, int block)
  908. {
  909. int order = 1;
  910. void *bb;
  911. BUG_ON(EXT4_MB_BITMAP(e4b) == EXT4_MB_BUDDY(e4b));
  912. BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));
  913. bb = EXT4_MB_BUDDY(e4b);
  914. while (order <= e4b->bd_blkbits + 1) {
  915. block = block >> 1;
  916. if (!mb_test_bit(block, bb)) {
  917. /* this block is part of buddy of order 'order' */
  918. return order;
  919. }
  920. bb += 1 << (e4b->bd_blkbits - order);
  921. order++;
  922. }
  923. return 0;
  924. }
  925. static void mb_clear_bits(spinlock_t *lock, void *bm, int cur, int len)
  926. {
  927. __u32 *addr;
  928. len = cur + len;
  929. while (cur < len) {
  930. if ((cur & 31) == 0 && (len - cur) >= 32) {
  931. /* fast path: clear whole word at once */
  932. addr = bm + (cur >> 3);
  933. *addr = 0;
  934. cur += 32;
  935. continue;
  936. }
  937. mb_clear_bit_atomic(lock, cur, bm);
  938. cur++;
  939. }
  940. }
  941. static void mb_set_bits(spinlock_t *lock, void *bm, int cur, int len)
  942. {
  943. __u32 *addr;
  944. len = cur + len;
  945. while (cur < len) {
  946. if ((cur & 31) == 0 && (len - cur) >= 32) {
  947. /* fast path: set whole word at once */
  948. addr = bm + (cur >> 3);
  949. *addr = 0xffffffff;
  950. cur += 32;
  951. continue;
  952. }
  953. mb_set_bit_atomic(lock, cur, bm);
  954. cur++;
  955. }
  956. }
  957. static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
  958. int first, int count)
  959. {
  960. int block = 0;
  961. int max = 0;
  962. int order;
  963. void *buddy;
  964. void *buddy2;
  965. struct super_block *sb = e4b->bd_sb;
  966. BUG_ON(first + count > (sb->s_blocksize << 3));
  967. BUG_ON(!ext4_is_group_locked(sb, e4b->bd_group));
  968. mb_check_buddy(e4b);
  969. mb_free_blocks_double(inode, e4b, first, count);
  970. e4b->bd_info->bb_free += count;
  971. if (first < e4b->bd_info->bb_first_free)
  972. e4b->bd_info->bb_first_free = first;
  973. /* let's maintain fragments counter */
  974. if (first != 0)
  975. block = !mb_test_bit(first - 1, EXT4_MB_BITMAP(e4b));
  976. if (first + count < EXT4_SB(sb)->s_mb_maxs[0])
  977. max = !mb_test_bit(first + count, EXT4_MB_BITMAP(e4b));
  978. if (block && max)
  979. e4b->bd_info->bb_fragments--;
  980. else if (!block && !max)
  981. e4b->bd_info->bb_fragments++;
  982. /* let's maintain buddy itself */
  983. while (count-- > 0) {
  984. block = first++;
  985. order = 0;
  986. if (!mb_test_bit(block, EXT4_MB_BITMAP(e4b))) {
  987. ext4_fsblk_t blocknr;
  988. blocknr = e4b->bd_group * EXT4_BLOCKS_PER_GROUP(sb);
  989. blocknr += block;
  990. blocknr +=
  991. le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
  992. ext4_unlock_group(sb, e4b->bd_group);
  993. ext4_error(sb, __func__, "double-free of inode"
  994. " %lu's block %llu(bit %u in group %lu)\n",
  995. inode ? inode->i_ino : 0, blocknr, block,
  996. e4b->bd_group);
  997. ext4_lock_group(sb, e4b->bd_group);
  998. }
  999. mb_clear_bit(block, EXT4_MB_BITMAP(e4b));
  1000. e4b->bd_info->bb_counters[order]++;
  1001. /* start of the buddy */
  1002. buddy = mb_find_buddy(e4b, order, &max);
  1003. do {
  1004. block &= ~1UL;
  1005. if (mb_test_bit(block, buddy) ||
  1006. mb_test_bit(block + 1, buddy))
  1007. break;
  1008. /* both the buddies are free, try to coalesce them */
  1009. buddy2 = mb_find_buddy(e4b, order + 1, &max);
  1010. if (!buddy2)
  1011. break;
  1012. if (order > 0) {
  1013. /* for special purposes, we don't set
  1014. * free bits in bitmap */
  1015. mb_set_bit(block, buddy);
  1016. mb_set_bit(block + 1, buddy);
  1017. }
  1018. e4b->bd_info->bb_counters[order]--;
  1019. e4b->bd_info->bb_counters[order]--;
  1020. block = block >> 1;
  1021. order++;
  1022. e4b->bd_info->bb_counters[order]++;
  1023. mb_clear_bit(block, buddy2);
  1024. buddy = buddy2;
  1025. } while (1);
  1026. }
  1027. mb_check_buddy(e4b);
  1028. }
  1029. static int mb_find_extent(struct ext4_buddy *e4b, int order, int block,
  1030. int needed, struct ext4_free_extent *ex)
  1031. {
  1032. int next = block;
  1033. int max;
  1034. int ord;
  1035. void *buddy;
  1036. BUG_ON(!ext4_is_group_locked(e4b->bd_sb, e4b->bd_group));
  1037. BUG_ON(ex == NULL);
  1038. buddy = mb_find_buddy(e4b, order, &max);
  1039. BUG_ON(buddy == NULL);
  1040. BUG_ON(block >= max);
  1041. if (mb_test_bit(block, buddy)) {
  1042. ex->fe_len = 0;
  1043. ex->fe_start = 0;
  1044. ex->fe_group = 0;
  1045. return 0;
  1046. }
  1047. /* FIXME dorp order completely ? */
  1048. if (likely(order == 0)) {
  1049. /* find actual order */
  1050. order = mb_find_order_for_block(e4b, block);
  1051. block = block >> order;
  1052. }
  1053. ex->fe_len = 1 << order;
  1054. ex->fe_start = block << order;
  1055. ex->fe_group = e4b->bd_group;
  1056. /* calc difference from given start */
  1057. next = next - ex->fe_start;
  1058. ex->fe_len -= next;
  1059. ex->fe_start += next;
  1060. while (needed > ex->fe_len &&
  1061. (buddy = mb_find_buddy(e4b, order, &max))) {
  1062. if (block + 1 >= max)
  1063. break;
  1064. next = (block + 1) * (1 << order);
  1065. if (mb_test_bit(next, EXT4_MB_BITMAP(e4b)))
  1066. break;
  1067. ord = mb_find_order_for_block(e4b, next);
  1068. order = ord;
  1069. block = next >> order;
  1070. ex->fe_len += 1 << order;
  1071. }
  1072. BUG_ON(ex->fe_start + ex->fe_len > (1 << (e4b->bd_blkbits + 3)));
  1073. return ex->fe_len;
  1074. }
  1075. static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
  1076. {
  1077. int ord;
  1078. int mlen = 0;
  1079. int max = 0;
  1080. int cur;
  1081. int start = ex->fe_start;
  1082. int len = ex->fe_len;
  1083. unsigned ret = 0;
  1084. int len0 = len;
  1085. void *buddy;
  1086. BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));
  1087. BUG_ON(e4b->bd_group != ex->fe_group);
  1088. BUG_ON(!ext4_is_group_locked(e4b->bd_sb, e4b->bd_group));
  1089. mb_check_buddy(e4b);
  1090. mb_mark_used_double(e4b, start, len);
  1091. e4b->bd_info->bb_free -= len;
  1092. if (e4b->bd_info->bb_first_free == start)
  1093. e4b->bd_info->bb_first_free += len;
  1094. /* let's maintain fragments counter */
  1095. if (start != 0)
  1096. mlen = !mb_test_bit(start - 1, EXT4_MB_BITMAP(e4b));
  1097. if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0])
  1098. max = !mb_test_bit(start + len, EXT4_MB_BITMAP(e4b));
  1099. if (mlen && max)
  1100. e4b->bd_info->bb_fragments++;
  1101. else if (!mlen && !max)
  1102. e4b->bd_info->bb_fragments--;
  1103. /* let's maintain buddy itself */
  1104. while (len) {
  1105. ord = mb_find_order_for_block(e4b, start);
  1106. if (((start >> ord) << ord) == start && len >= (1 << ord)) {
  1107. /* the whole chunk may be allocated at once! */
  1108. mlen = 1 << ord;
  1109. buddy = mb_find_buddy(e4b, ord, &max);
  1110. BUG_ON((start >> ord) >= max);
  1111. mb_set_bit(start >> ord, buddy);
  1112. e4b->bd_info->bb_counters[ord]--;
  1113. start += mlen;
  1114. len -= mlen;
  1115. BUG_ON(len < 0);
  1116. continue;
  1117. }
  1118. /* store for history */
  1119. if (ret == 0)
  1120. ret = len | (ord << 16);
  1121. /* we have to split large buddy */
  1122. BUG_ON(ord <= 0);
  1123. buddy = mb_find_buddy(e4b, ord, &max);
  1124. mb_set_bit(start >> ord, buddy);
  1125. e4b->bd_info->bb_counters[ord]--;
  1126. ord--;
  1127. cur = (start >> ord) & ~1U;
  1128. buddy = mb_find_buddy(e4b, ord, &max);
  1129. mb_clear_bit(cur, buddy);
  1130. mb_clear_bit(cur + 1, buddy);
  1131. e4b->bd_info->bb_counters[ord]++;
  1132. e4b->bd_info->bb_counters[ord]++;
  1133. }
  1134. mb_set_bits(sb_bgl_lock(EXT4_SB(e4b->bd_sb), ex->fe_group),
  1135. EXT4_MB_BITMAP(e4b), ex->fe_start, len0);
  1136. mb_check_buddy(e4b);
  1137. return ret;
  1138. }
  1139. /*
  1140. * Must be called under group lock!
  1141. */
  1142. static void ext4_mb_use_best_found(struct ext4_allocation_context *ac,
  1143. struct ext4_buddy *e4b)
  1144. {
  1145. struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
  1146. int ret;
  1147. BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);
  1148. BUG_ON(ac->ac_status == AC_STATUS_FOUND);
  1149. ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);
  1150. ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;
  1151. ret = mb_mark_used(e4b, &ac->ac_b_ex);
  1152. /* preallocation can change ac_b_ex, thus we store actually
  1153. * allocated blocks for history */
  1154. ac->ac_f_ex = ac->ac_b_ex;
  1155. ac->ac_status = AC_STATUS_FOUND;
  1156. ac->ac_tail = ret & 0xffff;
  1157. ac->ac_buddy = ret >> 16;
  1158. /* XXXXXXX: SUCH A HORRIBLE **CK */
  1159. /*FIXME!! Why ? */
  1160. ac->ac_bitmap_page = e4b->bd_bitmap_page;
  1161. get_page(ac->ac_bitmap_page);
  1162. ac->ac_buddy_page = e4b->bd_buddy_page;
  1163. get_page(ac->ac_buddy_page);
  1164. /* store last allocated for subsequent stream allocation */
  1165. if ((ac->ac_flags & EXT4_MB_HINT_DATA)) {
  1166. spin_lock(&sbi->s_md_lock);
  1167. sbi->s_mb_last_group = ac->ac_f_ex.fe_group;
  1168. sbi->s_mb_last_start = ac->ac_f_ex.fe_start;
  1169. spin_unlock(&sbi->s_md_lock);
  1170. }
  1171. }
  1172. /*
  1173. * regular allocator, for general purposes allocation
  1174. */
  1175. static void ext4_mb_check_limits(struct ext4_allocation_context *ac,
  1176. struct ext4_buddy *e4b,
  1177. int finish_group)
  1178. {
  1179. struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
  1180. struct ext4_free_extent *bex = &ac->ac_b_ex;
  1181. struct ext4_free_extent *gex = &ac->ac_g_ex;
  1182. struct ext4_free_extent ex;
  1183. int max;
  1184. /*
  1185. * We don't want to scan for a whole year
  1186. */
  1187. if (ac->ac_found > sbi->s_mb_max_to_scan &&
  1188. !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
  1189. ac->ac_status = AC_STATUS_BREAK;
  1190. return;
  1191. }
  1192. /*
  1193. * Haven't found good chunk so far, let's continue
  1194. */
  1195. if (bex->fe_len < gex->fe_len)
  1196. return;
  1197. if ((finish_group || ac->ac_found > sbi->s_mb_min_to_scan)
  1198. && bex->fe_group == e4b->bd_group) {
  1199. /* recheck chunk's availability - we don't know
  1200. * when it was found (within this lock-unlock
  1201. * period or not) */
  1202. max = mb_find_extent(e4b, 0, bex->fe_start, gex->fe_len, &ex);
  1203. if (max >= gex->fe_len) {
  1204. ext4_mb_use_best_found(ac, e4b);
  1205. return;
  1206. }
  1207. }
  1208. }
  1209. /*
  1210. * The routine checks whether found extent is good enough. If it is,
  1211. * then the extent gets marked used and flag is set to the context
  1212. * to stop scanning. Otherwise, the extent is compared with the
  1213. * previous found extent and if new one is better, then it's stored
  1214. * in the context. Later, the best found extent will be used, if
  1215. * mballoc can't find good enough extent.
  1216. *
  1217. * FIXME: real allocation policy is to be designed yet!
  1218. */
  1219. static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,
  1220. struct ext4_free_extent *ex,
  1221. struct ext4_buddy *e4b)
  1222. {
  1223. struct ext4_free_extent *bex = &ac->ac_b_ex;
  1224. struct ext4_free_extent *gex = &ac->ac_g_ex;
  1225. BUG_ON(ex->fe_len <= 0);
  1226. BUG_ON(ex->fe_len >= EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
  1227. BUG_ON(ex->fe_start >= EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
  1228. BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);
  1229. ac->ac_found++;
  1230. /*
  1231. * The special case - take what you catch first
  1232. */
  1233. if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
  1234. *bex = *ex;
  1235. ext4_mb_use_best_found(ac, e4b);
  1236. return;
  1237. }
  1238. /*
  1239. * Let's check whether the chuck is good enough
  1240. */
  1241. if (ex->fe_len == gex->fe_len) {
  1242. *bex = *ex;
  1243. ext4_mb_use_best_found(ac, e4b);
  1244. return;
  1245. }
  1246. /*
  1247. * If this is first found extent, just store it in the context
  1248. */
  1249. if (bex->fe_len == 0) {
  1250. *bex = *ex;
  1251. return;
  1252. }
  1253. /*
  1254. * If new found extent is better, store it in the context
  1255. */
  1256. if (bex->fe_len < gex->fe_len) {
  1257. /* if the request isn't satisfied, any found extent
  1258. * larger than previous best one is better */
  1259. if (ex->fe_len > bex->fe_len)
  1260. *bex = *ex;
  1261. } else if (ex->fe_len > gex->fe_len) {
  1262. /* if the request is satisfied, then we try to find
  1263. * an extent that still satisfy the request, but is
  1264. * smaller than previous one */
  1265. if (ex->fe_len < bex->fe_len)
  1266. *bex = *ex;
  1267. }
  1268. ext4_mb_check_limits(ac, e4b, 0);
  1269. }
  1270. static int ext4_mb_try_best_found(struct ext4_allocation_context *ac,
  1271. struct ext4_buddy *e4b)
  1272. {
  1273. struct ext4_free_extent ex = ac->ac_b_ex;
  1274. ext4_group_t group = ex.fe_group;
  1275. int max;
  1276. int err;
  1277. BUG_ON(ex.fe_len <= 0);
  1278. err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
  1279. if (err)
  1280. return err;
  1281. ext4_lock_group(ac->ac_sb, group);
  1282. max = mb_find_extent(e4b, 0, ex.fe_start, ex.fe_len, &ex);
  1283. if (max > 0) {
  1284. ac->ac_b_ex = ex;
  1285. ext4_mb_use_best_found(ac, e4b);
  1286. }
  1287. ext4_unlock_group(ac->ac_sb, group);
  1288. ext4_mb_release_desc(e4b);
  1289. return 0;
  1290. }
  1291. static int ext4_mb_find_by_goal(struct ext4_allocation_context *ac,
  1292. struct ext4_buddy *e4b)
  1293. {
  1294. ext4_group_t group = ac->ac_g_ex.fe_group;
  1295. int max;
  1296. int err;
  1297. struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
  1298. struct ext4_super_block *es = sbi->s_es;
  1299. struct ext4_free_extent ex;
  1300. if (!(ac->ac_flags & EXT4_MB_HINT_TRY_GOAL))
  1301. return 0;
  1302. err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
  1303. if (err)
  1304. return err;
  1305. ext4_lock_group(ac->ac_sb, group);
  1306. max = mb_find_extent(e4b, 0, ac->ac_g_ex.fe_start,
  1307. ac->ac_g_ex.fe_len, &ex);
  1308. if (max >= ac->ac_g_ex.fe_len && ac->ac_g_ex.fe_len == sbi->s_stripe) {
  1309. ext4_fsblk_t start;
  1310. start = (e4b->bd_group * EXT4_BLOCKS_PER_GROUP(ac->ac_sb)) +
  1311. ex.fe_start + le32_to_cpu(es->s_first_data_block);
  1312. /* use do_div to get remainder (would be 64-bit modulo) */
  1313. if (do_div(start, sbi->s_stripe) == 0) {
  1314. ac->ac_found++;
  1315. ac->ac_b_ex = ex;
  1316. ext4_mb_use_best_found(ac, e4b);
  1317. }
  1318. } else if (max >= ac->ac_g_ex.fe_len) {
  1319. BUG_ON(ex.fe_len <= 0);
  1320. BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
  1321. BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
  1322. ac->ac_found++;
  1323. ac->ac_b_ex = ex;
  1324. ext4_mb_use_best_found(ac, e4b);
  1325. } else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {
  1326. /* Sometimes, caller may want to merge even small
  1327. * number of blocks to an existing extent */
  1328. BUG_ON(ex.fe_len <= 0);
  1329. BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
  1330. BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
  1331. ac->ac_found++;
  1332. ac->ac_b_ex = ex;
  1333. ext4_mb_use_best_found(ac, e4b);
  1334. }
  1335. ext4_unlock_group(ac->ac_sb, group);
  1336. ext4_mb_release_desc(e4b);
  1337. return 0;
  1338. }
  1339. /*
  1340. * The routine scans buddy structures (not bitmap!) from given order
  1341. * to max order and tries to find big enough chunk to satisfy the req
  1342. */
  1343. static void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac,
  1344. struct ext4_buddy *e4b)
  1345. {
  1346. struct super_block *sb = ac->ac_sb;
  1347. struct ext4_group_info *grp = e4b->bd_info;
  1348. void *buddy;
  1349. int i;
  1350. int k;
  1351. int max;
  1352. BUG_ON(ac->ac_2order <= 0);
  1353. for (i = ac->ac_2order; i <= sb->s_blocksize_bits + 1; i++) {
  1354. if (grp->bb_counters[i] == 0)
  1355. continue;
  1356. buddy = mb_find_buddy(e4b, i, &max);
  1357. BUG_ON(buddy == NULL);
  1358. k = mb_find_next_zero_bit(buddy, max, 0);
  1359. BUG_ON(k >= max);
  1360. ac->ac_found++;
  1361. ac->ac_b_ex.fe_len = 1 << i;
  1362. ac->ac_b_ex.fe_start = k << i;
  1363. ac->ac_b_ex.fe_group = e4b->bd_group;
  1364. ext4_mb_use_best_found(ac, e4b);
  1365. BUG_ON(ac->ac_b_ex.fe_len != ac->ac_g_ex.fe_len);
  1366. if (EXT4_SB(sb)->s_mb_stats)
  1367. atomic_inc(&EXT4_SB(sb)->s_bal_2orders);
  1368. break;
  1369. }
  1370. }
  1371. /*
  1372. * The routine scans the group and measures all found extents.
  1373. * In order to optimize scanning, caller must pass number of
  1374. * free blocks in the group, so the routine can know upper limit.
  1375. */
  1376. static void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac,
  1377. struct ext4_buddy *e4b)
  1378. {
  1379. struct super_block *sb = ac->ac_sb;
  1380. void *bitmap = EXT4_MB_BITMAP(e4b);
  1381. struct ext4_free_extent ex;
  1382. int i;
  1383. int free;
  1384. free = e4b->bd_info->bb_free;
  1385. BUG_ON(free <= 0);
  1386. i = e4b->bd_info->bb_first_free;
  1387. while (free && ac->ac_status == AC_STATUS_CONTINUE) {
  1388. i = mb_find_next_zero_bit(bitmap,
  1389. EXT4_BLOCKS_PER_GROUP(sb), i);
  1390. if (i >= EXT4_BLOCKS_PER_GROUP(sb)) {
  1391. /*
  1392. * IF we have corrupt bitmap, we won't find any
  1393. * free blocks even though group info says we
  1394. * we have free blocks
  1395. */
  1396. ext4_error(sb, __func__, "%d free blocks as per "
  1397. "group info. But bitmap says 0\n",
  1398. free);
  1399. break;
  1400. }
  1401. mb_find_extent(e4b, 0, i, ac->ac_g_ex.fe_len, &ex);
  1402. BUG_ON(ex.fe_len <= 0);
  1403. if (free < ex.fe_len) {
  1404. ext4_error(sb, __func__, "%d free blocks as per "
  1405. "group info. But got %d blocks\n",
  1406. free, ex.fe_len);
  1407. /*
  1408. * The number of free blocks differs. This mostly
  1409. * indicate that the bitmap is corrupt. So exit
  1410. * without claiming the space.
  1411. */
  1412. break;
  1413. }
  1414. ext4_mb_measure_extent(ac, &ex, e4b);
  1415. i += ex.fe_len;
  1416. free -= ex.fe_len;
  1417. }
  1418. ext4_mb_check_limits(ac, e4b, 1);
  1419. }
  1420. /*
  1421. * This is a special case for storages like raid5
  1422. * we try to find stripe-aligned chunks for stripe-size requests
  1423. * XXX should do so at least for multiples of stripe size as well
  1424. */
  1425. static void ext4_mb_scan_aligned(struct ext4_allocation_context *ac,
  1426. struct ext4_buddy *e4b)
  1427. {
  1428. struct super_block *sb = ac->ac_sb;
  1429. struct ext4_sb_info *sbi = EXT4_SB(sb);
  1430. void *bitmap = EXT4_MB_BITMAP(e4b);
  1431. struct ext4_free_extent ex;
  1432. ext4_fsblk_t first_group_block;
  1433. ext4_fsblk_t a;
  1434. ext4_grpblk_t i;
  1435. int max;
  1436. BUG_ON(sbi->s_stripe == 0);
  1437. /* find first stripe-aligned block in group */
  1438. first_group_block = e4b->bd_group * EXT4_BLOCKS_PER_GROUP(sb)
  1439. + le32_to_cpu(sbi->s_es->s_first_data_block);
  1440. a = first_group_block + sbi->s_stripe - 1;
  1441. do_div(a, sbi->s_stripe);
  1442. i = (a * sbi->s_stripe) - first_group_block;
  1443. while (i < EXT4_BLOCKS_PER_GROUP(sb)) {
  1444. if (!mb_test_bit(i, bitmap)) {
  1445. max = mb_find_extent(e4b, 0, i, sbi->s_stripe, &ex);
  1446. if (max >= sbi->s_stripe) {
  1447. ac->ac_found++;
  1448. ac->ac_b_ex = ex;
  1449. ext4_mb_use_best_found(ac, e4b);
  1450. break;
  1451. }
  1452. }
  1453. i += sbi->s_stripe;
  1454. }
  1455. }
  1456. static int ext4_mb_good_group(struct ext4_allocation_context *ac,
  1457. ext4_group_t group, int cr)
  1458. {
  1459. unsigned free, fragments;
  1460. unsigned i, bits;
  1461. struct ext4_group_desc *desc;
  1462. struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);
  1463. BUG_ON(cr < 0 || cr >= 4);
  1464. BUG_ON(EXT4_MB_GRP_NEED_INIT(grp));
  1465. free = grp->bb_free;
  1466. fragments = grp->bb_fragments;
  1467. if (free == 0)
  1468. return 0;
  1469. if (fragments == 0)
  1470. return 0;
  1471. switch (cr) {
  1472. case 0:
  1473. BUG_ON(ac->ac_2order == 0);
  1474. /* If this group is uninitialized, skip it initially */
  1475. desc = ext4_get_group_desc(ac->ac_sb, group, NULL);
  1476. if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))
  1477. return 0;
  1478. bits = ac->ac_sb->s_blocksize_bits + 1;
  1479. for (i = ac->ac_2order; i <= bits; i++)
  1480. if (grp->bb_counters[i] > 0)
  1481. return 1;
  1482. break;
  1483. case 1:
  1484. if ((free / fragments) >= ac->ac_g_ex.fe_len)
  1485. return 1;
  1486. break;
  1487. case 2:
  1488. if (free >= ac->ac_g_ex.fe_len)
  1489. return 1;
  1490. break;
  1491. case 3:
  1492. return 1;
  1493. default:
  1494. BUG();
  1495. }
  1496. return 0;
  1497. }
  1498. static noinline_for_stack int
  1499. ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
  1500. {
  1501. ext4_group_t group;
  1502. ext4_group_t i;
  1503. int cr;
  1504. int err = 0;
  1505. int bsbits;
  1506. struct ext4_sb_info *sbi;
  1507. struct super_block *sb;
  1508. struct ext4_buddy e4b;
  1509. loff_t size, isize;
  1510. sb = ac->ac_sb;
  1511. sbi = EXT4_SB(sb);
  1512. BUG_ON(ac->ac_status == AC_STATUS_FOUND);
  1513. /* first, try the goal */
  1514. err = ext4_mb_find_by_goal(ac, &e4b);
  1515. if (err || ac->ac_status == AC_STATUS_FOUND)
  1516. goto out;
  1517. if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
  1518. goto out;
  1519. /*
  1520. * ac->ac2_order is set only if the fe_len is a power of 2
  1521. * if ac2_order is set we also set criteria to 0 so that we
  1522. * try exact allocation using buddy.
  1523. */
  1524. i = fls(ac->ac_g_ex.fe_len);
  1525. ac->ac_2order = 0;
  1526. /*
  1527. * We search using buddy data only if the order of the request
  1528. * is greater than equal to the sbi_s_mb_order2_reqs
  1529. * You can tune it via /proc/fs/ext4/<partition>/order2_req
  1530. */
  1531. if (i >= sbi->s_mb_order2_reqs) {
  1532. /*
  1533. * This should tell if fe_len is exactly power of 2
  1534. */
  1535. if ((ac->ac_g_ex.fe_len & (~(1 << (i - 1)))) == 0)
  1536. ac->ac_2order = i - 1;
  1537. }
  1538. bsbits = ac->ac_sb->s_blocksize_bits;
  1539. /* if stream allocation is enabled, use global goal */
  1540. size = ac->ac_o_ex.fe_logical + ac->ac_o_ex.fe_len;
  1541. isize = i_size_read(ac->ac_inode) >> bsbits;
  1542. if (size < isize)
  1543. size = isize;
  1544. if (size < sbi->s_mb_stream_request &&
  1545. (ac->ac_flags & EXT4_MB_HINT_DATA)) {
  1546. /* TBD: may be hot point */
  1547. spin_lock(&sbi->s_md_lock);
  1548. ac->ac_g_ex.fe_group = sbi->s_mb_last_group;
  1549. ac->ac_g_ex.fe_start = sbi->s_mb_last_start;
  1550. spin_unlock(&sbi->s_md_lock);
  1551. }
  1552. /* Let's just scan groups to find more-less suitable blocks */
  1553. cr = ac->ac_2order ? 0 : 1;
  1554. /*
  1555. * cr == 0 try to get exact allocation,
  1556. * cr == 3 try to get anything
  1557. */
  1558. repeat:
  1559. for (; cr < 4 && ac->ac_status == AC_STATUS_CONTINUE; cr++) {
  1560. ac->ac_criteria = cr;
  1561. /*
  1562. * searching for the right group start
  1563. * from the goal value specified
  1564. */
  1565. group = ac->ac_g_ex.fe_group;
  1566. for (i = 0; i < EXT4_SB(sb)->s_groups_count; group++, i++) {
  1567. struct ext4_group_info *grp;
  1568. struct ext4_group_desc *desc;
  1569. if (group == EXT4_SB(sb)->s_groups_count)
  1570. group = 0;
  1571. /* quick check to skip empty groups */
  1572. grp = ext4_get_group_info(ac->ac_sb, group);
  1573. if (grp->bb_free == 0)
  1574. continue;
  1575. /*
  1576. * if the group is already init we check whether it is
  1577. * a good group and if not we don't load the buddy
  1578. */
  1579. if (EXT4_MB_GRP_NEED_INIT(grp)) {
  1580. /*
  1581. * we need full data about the group
  1582. * to make a good selection
  1583. */
  1584. err = ext4_mb_load_buddy(sb, group, &e4b);
  1585. if (err)
  1586. goto out;
  1587. ext4_mb_release_desc(&e4b);
  1588. }
  1589. /*
  1590. * If the particular group doesn't satisfy our
  1591. * criteria we continue with the next group
  1592. */
  1593. if (!ext4_mb_good_group(ac, group, cr))
  1594. continue;
  1595. err = ext4_mb_load_buddy(sb, group, &e4b);
  1596. if (err)
  1597. goto out;
  1598. ext4_lock_group(sb, group);
  1599. if (!ext4_mb_good_group(ac, group, cr)) {
  1600. /* someone did allocation from this group */
  1601. ext4_unlock_group(sb, group);
  1602. ext4_mb_release_desc(&e4b);
  1603. continue;
  1604. }
  1605. ac->ac_groups_scanned++;
  1606. desc = ext4_get_group_desc(sb, group, NULL);
  1607. if (cr == 0 || (desc->bg_flags &
  1608. cpu_to_le16(EXT4_BG_BLOCK_UNINIT) &&
  1609. ac->ac_2order != 0))
  1610. ext4_mb_simple_scan_group(ac, &e4b);
  1611. else if (cr == 1 &&
  1612. ac->ac_g_ex.fe_len == sbi->s_stripe)
  1613. ext4_mb_scan_aligned(ac, &e4b);
  1614. else
  1615. ext4_mb_complex_scan_group(ac, &e4b);
  1616. ext4_unlock_group(sb, group);
  1617. ext4_mb_release_desc(&e4b);
  1618. if (ac->ac_status != AC_STATUS_CONTINUE)
  1619. break;
  1620. }
  1621. }
  1622. if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&
  1623. !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
  1624. /*
  1625. * We've been searching too long. Let's try to allocate
  1626. * the best chunk we've found so far
  1627. */
  1628. ext4_mb_try_best_found(ac, &e4b);
  1629. if (ac->ac_status != AC_STATUS_FOUND) {
  1630. /*
  1631. * Someone more lucky has already allocated it.
  1632. * The only thing we can do is just take first
  1633. * found block(s)
  1634. printk(KERN_DEBUG "EXT4-fs: someone won our chunk\n");
  1635. */
  1636. ac->ac_b_ex.fe_group = 0;
  1637. ac->ac_b_ex.fe_start = 0;
  1638. ac->ac_b_ex.fe_len = 0;
  1639. ac->ac_status = AC_STATUS_CONTINUE;
  1640. ac->ac_flags |= EXT4_MB_HINT_FIRST;
  1641. cr = 3;
  1642. atomic_inc(&sbi->s_mb_lost_chunks);
  1643. goto repeat;
  1644. }
  1645. }
  1646. out:
  1647. return err;
  1648. }
  1649. #ifdef EXT4_MB_HISTORY
  1650. struct ext4_mb_proc_session {
  1651. struct ext4_mb_history *history;
  1652. struct super_block *sb;
  1653. int start;
  1654. int max;
  1655. };
  1656. static void *ext4_mb_history_skip_empty(struct ext4_mb_proc_session *s,
  1657. struct ext4_mb_history *hs,
  1658. int first)
  1659. {
  1660. if (hs == s->history + s->max)
  1661. hs = s->history;
  1662. if (!first && hs == s->history + s->start)
  1663. return NULL;
  1664. while (hs->orig.fe_len == 0) {
  1665. hs++;
  1666. if (hs == s->history + s->max)
  1667. hs = s->history;
  1668. if (hs == s->history + s->start)
  1669. return NULL;
  1670. }
  1671. return hs;
  1672. }
  1673. static void *ext4_mb_seq_history_start(struct seq_file *seq, loff_t *pos)
  1674. {
  1675. struct ext4_mb_proc_session *s = seq->private;
  1676. struct ext4_mb_history *hs;
  1677. int l = *pos;
  1678. if (l == 0)
  1679. return SEQ_START_TOKEN;
  1680. hs = ext4_mb_history_skip_empty(s, s->history + s->start, 1);
  1681. if (!hs)
  1682. return NULL;
  1683. while (--l && (hs = ext4_mb_history_skip_empty(s, ++hs, 0)) != NULL);
  1684. return hs;
  1685. }
  1686. static void *ext4_mb_seq_history_next(struct seq_file *seq, void *v,
  1687. loff_t *pos)
  1688. {
  1689. struct ext4_mb_proc_session *s = seq->private;
  1690. struct ext4_mb_history *hs = v;
  1691. ++*pos;
  1692. if (v == SEQ_START_TOKEN)
  1693. return ext4_mb_history_skip_empty(s, s->history + s->start, 1);
  1694. else
  1695. return ext4_mb_history_skip_empty(s, ++hs, 0);
  1696. }
  1697. static int ext4_mb_seq_history_show(struct seq_file *seq, void *v)
  1698. {
  1699. char buf[25], buf2[25], buf3[25], *fmt;
  1700. struct ext4_mb_history *hs = v;
  1701. if (v == SEQ_START_TOKEN) {
  1702. seq_printf(seq, "%-5s %-8s %-23s %-23s %-23s %-5s "
  1703. "%-5s %-2s %-5s %-5s %-5s %-6s\n",
  1704. "pid", "inode", "original", "goal", "result", "found",
  1705. "grps", "cr", "flags", "merge", "tail", "broken");
  1706. return 0;
  1707. }
  1708. if (hs->op == EXT4_MB_HISTORY_ALLOC) {
  1709. fmt = "%-5u %-8u %-23s %-23s %-23s %-5u %-5u %-2u "
  1710. "%-5u %-5s %-5u %-6u\n";
  1711. sprintf(buf2, "%lu/%d/%u@%u", hs->result.fe_group,
  1712. hs->result.fe_start, hs->result.fe_len,
  1713. hs->result.fe_logical);
  1714. sprintf(buf, "%lu/%d/%u@%u", hs->orig.fe_group,
  1715. hs->orig.fe_start, hs->orig.fe_len,
  1716. hs->orig.fe_logical);
  1717. sprintf(buf3, "%lu/%d/%u@%u", hs->goal.fe_group,
  1718. hs->goal.fe_start, hs->goal.fe_len,
  1719. hs->goal.fe_logical);
  1720. seq_printf(seq, fmt, hs->pid, hs->ino, buf, buf3, buf2,
  1721. hs->found, hs->groups, hs->cr, hs->flags,
  1722. hs->merged ? "M" : "", hs->tail,
  1723. hs->buddy ? 1 << hs->buddy : 0);
  1724. } else if (hs->op == EXT4_MB_HISTORY_PREALLOC) {
  1725. fmt = "%-5u %-8u %-23s %-23s %-23s\n";
  1726. sprintf(buf2, "%lu/%d/%u@%u", hs->result.fe_group,
  1727. hs->result.fe_start, hs->result.fe_len,
  1728. hs->result.fe_logical);
  1729. sprintf(buf, "%lu/%d/%u@%u", hs->orig.fe_group,
  1730. hs->orig.fe_start, hs->orig.fe_len,
  1731. hs->orig.fe_logical);
  1732. seq_printf(seq, fmt, hs->pid, hs->ino, buf, "", buf2);
  1733. } else if (hs->op == EXT4_MB_HISTORY_DISCARD) {
  1734. sprintf(buf2, "%lu/%d/%u", hs->result.fe_group,
  1735. hs->result.fe_start, hs->result.fe_len);
  1736. seq_printf(seq, "%-5u %-8u %-23s discard\n",
  1737. hs->pid, hs->ino, buf2);
  1738. } else if (hs->op == EXT4_MB_HISTORY_FREE) {
  1739. sprintf(buf2, "%lu/%d/%u", hs->result.fe_group,
  1740. hs->result.fe_start, hs->result.fe_len);
  1741. seq_printf(seq, "%-5u %-8u %-23s free\n",
  1742. hs->pid, hs->ino, buf2);
  1743. }
  1744. return 0;
  1745. }
  1746. static void ext4_mb_seq_history_stop(struct seq_file *seq, void *v)
  1747. {
  1748. }
  1749. static struct seq_operations ext4_mb_seq_history_ops = {
  1750. .start = ext4_mb_seq_history_start,
  1751. .next = ext4_mb_seq_history_next,
  1752. .stop = ext4_mb_seq_history_stop,
  1753. .show = ext4_mb_seq_history_show,
  1754. };
  1755. static int ext4_mb_seq_history_open(struct inode *inode, struct file *file)
  1756. {
  1757. struct super_block *sb = PDE(inode)->data;
  1758. struct ext4_sb_info *sbi = EXT4_SB(sb);
  1759. struct ext4_mb_proc_session *s;
  1760. int rc;
  1761. int size;
  1762. if (unlikely(sbi->s_mb_history == NULL))
  1763. return -ENOMEM;
  1764. s = kmalloc(sizeof(*s), GFP_KERNEL);
  1765. if (s == NULL)
  1766. return -ENOMEM;
  1767. s->sb = sb;
  1768. size = sizeof(struct ext4_mb_history) * sbi->s_mb_history_max;
  1769. s->history = kmalloc(size, GFP_KERNEL);
  1770. if (s->history == NULL) {
  1771. kfree(s);
  1772. return -ENOMEM;
  1773. }
  1774. spin_lock(&sbi->s_mb_history_lock);
  1775. memcpy(s->history, sbi->s_mb_history, size);
  1776. s->max = sbi->s_mb_history_max;
  1777. s->start = sbi->s_mb_history_cur % s->max;
  1778. spin_unlock(&sbi->s_mb_history_lock);
  1779. rc = seq_open(file, &ext4_mb_seq_history_ops);
  1780. if (rc == 0) {
  1781. struct seq_file *m = (struct seq_file *)file->private_data;
  1782. m->private = s;
  1783. } else {
  1784. kfree(s->history);
  1785. kfree(s);
  1786. }
  1787. return rc;
  1788. }
  1789. static int ext4_mb_seq_history_release(struct inode *inode, struct file *file)
  1790. {
  1791. struct seq_file *seq = (struct seq_file *)file->private_data;
  1792. struct ext4_mb_proc_session *s = seq->private;
  1793. kfree(s->history);
  1794. kfree(s);
  1795. return seq_release(inode, file);
  1796. }
  1797. static ssize_t ext4_mb_seq_history_write(struct file *file,
  1798. const char __user *buffer,
  1799. size_t count, loff_t *ppos)
  1800. {
  1801. struct seq_file *seq = (struct seq_file *)file->private_data;
  1802. struct ext4_mb_proc_session *s = seq->private;
  1803. struct super_block *sb = s->sb;
  1804. char str[32];
  1805. int value;
  1806. if (count >= sizeof(str)) {
  1807. printk(KERN_ERR "EXT4-fs: %s string too long, max %u bytes\n",
  1808. "mb_history", (int)sizeof(str));
  1809. return -EOVERFLOW;
  1810. }
  1811. if (copy_from_user(str, buffer, count))
  1812. return -EFAULT;
  1813. value = simple_strtol(str, NULL, 0);
  1814. if (value < 0)
  1815. return -ERANGE;
  1816. EXT4_SB(sb)->s_mb_history_filter = value;
  1817. return count;
  1818. }
  1819. static struct file_operations ext4_mb_seq_history_fops = {
  1820. .owner = THIS_MODULE,
  1821. .open = ext4_mb_seq_history_open,
  1822. .read = seq_read,
  1823. .write = ext4_mb_seq_history_write,
  1824. .llseek = seq_lseek,
  1825. .release = ext4_mb_seq_history_release,
  1826. };
  1827. static void *ext4_mb_seq_groups_start(struct seq_file *seq, loff_t *pos)
  1828. {
  1829. struct super_block *sb = seq->private;
  1830. struct ext4_sb_info *sbi = EXT4_SB(sb);
  1831. ext4_group_t group;
  1832. if (*pos < 0 || *pos >= sbi->s_groups_count)
  1833. return NULL;
  1834. group = *pos + 1;
  1835. return (void *) group;
  1836. }
  1837. static void *ext4_mb_seq_groups_next(struct seq_file *seq, void *v, loff_t *pos)
  1838. {
  1839. struct super_block *sb = seq->private;
  1840. struct ext4_sb_info *sbi = EXT4_SB(sb);
  1841. ext4_group_t group;
  1842. ++*pos;
  1843. if (*pos < 0 || *pos >= sbi->s_groups_count)
  1844. return NULL;
  1845. group = *pos + 1;
  1846. return (void *) group;;
  1847. }
  1848. static int ext4_mb_seq_groups_show(struct seq_file *seq, void *v)
  1849. {
  1850. struct super_block *sb = seq->private;
  1851. long group = (long) v;
  1852. int i;
  1853. int err;
  1854. struct ext4_buddy e4b;
  1855. struct sg {
  1856. struct ext4_group_info info;
  1857. unsigned short counters[16];
  1858. } sg;
  1859. group--;
  1860. if (group == 0)
  1861. seq_printf(seq, "#%-5s: %-5s %-5s %-5s "
  1862. "[ %-5s %-5s %-5s %-5s %-5s %-5s %-5s "
  1863. "%-5s %-5s %-5s %-5s %-5s %-5s %-5s ]\n",
  1864. "group", "free", "frags", "first",
  1865. "2^0", "2^1", "2^2", "2^3", "2^4", "2^5", "2^6",
  1866. "2^7", "2^8", "2^9", "2^10", "2^11", "2^12", "2^13");
  1867. i = (sb->s_blocksize_bits + 2) * sizeof(sg.info.bb_counters[0]) +
  1868. sizeof(struct ext4_group_info);
  1869. err = ext4_mb_load_buddy(sb, group, &e4b);
  1870. if (err) {
  1871. seq_printf(seq, "#%-5lu: I/O error\n", group);
  1872. return 0;
  1873. }
  1874. ext4_lock_group(sb, group);
  1875. memcpy(&sg, ext4_get_group_info(sb, group), i);
  1876. ext4_unlock_group(sb, group);
  1877. ext4_mb_release_desc(&e4b);
  1878. seq_printf(seq, "#%-5lu: %-5u %-5u %-5u [", group, sg.info.bb_free,
  1879. sg.info.bb_fragments, sg.info.bb_first_free);
  1880. for (i = 0; i <= 13; i++)
  1881. seq_printf(seq, " %-5u", i <= sb->s_blocksize_bits + 1 ?
  1882. sg.info.bb_counters[i] : 0);
  1883. seq_printf(seq, " ]\n");
  1884. return 0;
  1885. }
  1886. static void ext4_mb_seq_groups_stop(struct seq_file *seq, void *v)
  1887. {
  1888. }
  1889. static struct seq_operations ext4_mb_seq_groups_ops = {
  1890. .start = ext4_mb_seq_groups_start,
  1891. .next = ext4_mb_seq_groups_next,
  1892. .stop = ext4_mb_seq_groups_stop,
  1893. .show = ext4_mb_seq_groups_show,
  1894. };
  1895. static int ext4_mb_seq_groups_open(struct inode *inode, struct file *file)
  1896. {
  1897. struct super_block *sb = PDE(inode)->data;
  1898. int rc;
  1899. rc = seq_open(file, &ext4_mb_seq_groups_ops);
  1900. if (rc == 0) {
  1901. struct seq_file *m = (struct seq_file *)file->private_data;
  1902. m->private = sb;
  1903. }
  1904. return rc;
  1905. }
  1906. static struct file_operations ext4_mb_seq_groups_fops = {
  1907. .owner = THIS_MODULE,
  1908. .open = ext4_mb_seq_groups_open,
  1909. .read = seq_read,
  1910. .llseek = seq_lseek,
  1911. .release = seq_release,
  1912. };
  1913. static void ext4_mb_history_release(struct super_block *sb)
  1914. {
  1915. struct ext4_sb_info *sbi = EXT4_SB(sb);
  1916. if (sbi->s_proc != NULL) {
  1917. remove_proc_entry("mb_groups", sbi->s_proc);
  1918. remove_proc_entry("mb_history", sbi->s_proc);
  1919. }
  1920. kfree(sbi->s_mb_history);
  1921. }
  1922. static void ext4_mb_history_init(struct super_block *sb)
  1923. {
  1924. struct ext4_sb_info *sbi = EXT4_SB(sb);
  1925. int i;
  1926. if (sbi->s_proc != NULL) {
  1927. proc_create_data("mb_history", S_IRUGO, sbi->s_proc,
  1928. &ext4_mb_seq_history_fops, sb);
  1929. proc_create_data("mb_groups", S_IRUGO, sbi->s_proc,
  1930. &ext4_mb_seq_groups_fops, sb);
  1931. }
  1932. sbi->s_mb_history_max = 1000;
  1933. sbi->s_mb_history_cur = 0;
  1934. spin_lock_init(&sbi->s_mb_history_lock);
  1935. i = sbi->s_mb_history_max * sizeof(struct ext4_mb_history);
  1936. sbi->s_mb_history = kzalloc(i, GFP_KERNEL);
  1937. /* if we can't allocate history, then we simple won't use it */
  1938. }
  1939. static noinline_for_stack void
  1940. ext4_mb_store_history(struct ext4_allocation_context *ac)
  1941. {
  1942. struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
  1943. struct ext4_mb_history h;
  1944. if (unlikely(sbi->s_mb_history == NULL))
  1945. return;
  1946. if (!(ac->ac_op & sbi->s_mb_history_filter))
  1947. return;
  1948. h.op = ac->ac_op;
  1949. h.pid = current->pid;
  1950. h.ino = ac->ac_inode ? ac->ac_inode->i_ino : 0;
  1951. h.orig = ac->ac_o_ex;
  1952. h.result = ac->ac_b_ex;
  1953. h.flags = ac->ac_flags;
  1954. h.found = ac->ac_found;
  1955. h.groups = ac->ac_groups_scanned;
  1956. h.cr = ac->ac_criteria;
  1957. h.tail = ac->ac_tail;
  1958. h.buddy = ac->ac_buddy;
  1959. h.merged = 0;
  1960. if (ac->ac_op == EXT4_MB_HISTORY_ALLOC) {
  1961. if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
  1962. ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
  1963. h.merged = 1;
  1964. h.goal = ac->ac_g_ex;
  1965. h.result = ac->ac_f_ex;
  1966. }
  1967. spin_lock(&sbi->s_mb_history_lock);
  1968. memcpy(sbi->s_mb_history + sbi->s_mb_history_cur, &h, sizeof(h));
  1969. if (++sbi->s_mb_history_cur >= sbi->s_mb_history_max)
  1970. sbi->s_mb_history_cur = 0;
  1971. spin_unlock(&sbi->s_mb_history_lock);
  1972. }
  1973. #else
  1974. #define ext4_mb_history_release(sb)
  1975. #define ext4_mb_history_init(sb)
  1976. #endif
  1977. /* Create and initialize ext4_group_info data for the given group. */
  1978. int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
  1979. struct ext4_group_desc *desc)
  1980. {
  1981. int i, len;
  1982. int metalen = 0;
  1983. struct ext4_sb_info *sbi = EXT4_SB(sb);
  1984. struct ext4_group_info **meta_group_info;
  1985. /*
  1986. * First check if this group is the first of a reserved block.
  1987. * If it's true, we have to allocate a new table of pointers
  1988. * to ext4_group_info structures
  1989. */
  1990. if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {
  1991. metalen = sizeof(*meta_group_info) <<
  1992. EXT4_DESC_PER_BLOCK_BITS(sb);
  1993. meta_group_info = kmalloc(metalen, GFP_KERNEL);
  1994. if (meta_group_info == NULL) {
  1995. printk(KERN_ERR "EXT4-fs: can't allocate mem for a "
  1996. "buddy group\n");
  1997. goto exit_meta_group_info;
  1998. }
  1999. sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)] =
  2000. meta_group_info;
  2001. }
  2002. /*
  2003. * calculate needed size. if change bb_counters size,
  2004. * don't forget about ext4_mb_generate_buddy()
  2005. */
  2006. len = offsetof(typeof(**meta_group_info),
  2007. bb_counters[sb->s_blocksize_bits + 2]);
  2008. meta_group_info =
  2009. sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)];
  2010. i = group & (EXT4_DESC_PER_BLOCK(sb) - 1);
  2011. meta_group_info[i] = kzalloc(len, GFP_KERNEL);
  2012. if (meta_group_info[i] == NULL) {
  2013. printk(KERN_ERR "EXT4-fs: can't allocate buddy mem\n");
  2014. goto exit_group_info;
  2015. }
  2016. set_bit(EXT4_GROUP_INFO_NEED_INIT_BIT,
  2017. &(meta_group_info[i]->bb_state));
  2018. /*
  2019. * initialize bb_free to be able to skip
  2020. * empty groups without initialization
  2021. */
  2022. if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
  2023. meta_group_info[i]->bb_free =
  2024. ext4_free_blocks_after_init(sb, group, desc);
  2025. } else {
  2026. meta_group_info[i]->bb_free =
  2027. le16_to_cpu(desc->bg_free_blocks_count);
  2028. }
  2029. INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
  2030. #ifdef DOUBLE_CHECK
  2031. {
  2032. struct buffer_head *bh;
  2033. meta_group_info[i]->bb_bitmap =
  2034. kmalloc(sb->s_blocksize, GFP_KERNEL);
  2035. BUG_ON(meta_group_info[i]->bb_bitmap == NULL);
  2036. bh = ext4_read_block_bitmap(sb, group);
  2037. BUG_ON(bh == NULL);
  2038. memcpy(meta_group_info[i]->bb_bitmap, bh->b_data,
  2039. sb->s_blocksize);
  2040. put_bh(bh);
  2041. }
  2042. #endif
  2043. return 0;
  2044. exit_group_info:
  2045. /* If a meta_group_info table has been allocated, release it now */
  2046. if (group % EXT4_DESC_PER_BLOCK(sb) == 0)
  2047. kfree(sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)]);
  2048. exit_meta_group_info:
  2049. return -ENOMEM;
  2050. } /* ext4_mb_add_groupinfo */
  2051. /*
  2052. * Add a group to the existing groups.
  2053. * This function is used for online resize
  2054. */
  2055. int ext4_mb_add_more_groupinfo(struct super_block *sb, ext4_group_t group,
  2056. struct ext4_group_desc *desc)
  2057. {
  2058. struct ext4_sb_info *sbi = EXT4_SB(sb);
  2059. struct inode *inode = sbi->s_buddy_cache;
  2060. int blocks_per_page;
  2061. int block;
  2062. int pnum;
  2063. struct page *page;
  2064. int err;
  2065. /* Add group based on group descriptor*/
  2066. err = ext4_mb_add_groupinfo(sb, group, desc);
  2067. if (err)
  2068. return err;
  2069. /*
  2070. * Cache pages containing dynamic mb_alloc datas (buddy and bitmap
  2071. * datas) are set not up to date so that they will be re-initilaized
  2072. * during the next call to ext4_mb_load_buddy
  2073. */
  2074. /* Set buddy page as not up to date */
  2075. blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
  2076. block = group * 2;
  2077. pnum = block / blocks_per_page;
  2078. page = find_get_page(inode->i_mapping, pnum);
  2079. if (page != NULL) {
  2080. ClearPageUptodate(page);
  2081. page_cache_release(page);
  2082. }
  2083. /* Set bitmap page as not up to date */
  2084. block++;
  2085. pnum = block / blocks_per_page;
  2086. page = find_get_page(inode->i_mapping, pnum);
  2087. if (page != NULL) {
  2088. ClearPageUptodate(page);
  2089. page_cache_release(page);
  2090. }
  2091. return 0;
  2092. }
  2093. /*
  2094. * Update an existing group.
  2095. * This function is used for online resize
  2096. */
  2097. void ext4_mb_update_group_info(struct ext4_group_info *grp, ext4_grpblk_t add)
  2098. {
  2099. grp->bb_free += add;
  2100. }
  2101. static int ext4_mb_init_backend(struct super_block *sb)
  2102. {
  2103. ext4_group_t i;
  2104. int metalen;
  2105. struct ext4_sb_info *sbi = EXT4_SB(sb);
  2106. struct ext4_super_block *es = sbi->s_es;
  2107. int num_meta_group_infos;
  2108. int num_meta_group_infos_max;
  2109. int array_size;
  2110. struct ext4_group_info **meta_group_info;
  2111. struct ext4_group_desc *desc;
  2112. /* This is the number of blocks used by GDT */
  2113. num_meta_group_infos = (sbi->s_groups_count + EXT4_DESC_PER_BLOCK(sb) -
  2114. 1) >> EXT4_DESC_PER_BLOCK_BITS(sb);
  2115. /*
  2116. * This is the total number of blocks used by GDT including
  2117. * the number of reserved blocks for GDT.
  2118. * The s_group_info array is allocated with this value
  2119. * to allow a clean online resize without a complex
  2120. * manipulation of pointer.
  2121. * The drawback is the unused memory when no resize
  2122. * occurs but it's very low in terms of pages
  2123. * (see comments below)
  2124. * Need to handle this properly when META_BG resizing is allowed
  2125. */
  2126. num_meta_group_infos_max = num_meta_group_infos +
  2127. le16_to_cpu(es->s_reserved_gdt_blocks);
  2128. /*
  2129. * array_size is the size of s_group_info array. We round it
  2130. * to the next power of two because this approximation is done
  2131. * internally by kmalloc so we can have some more memory
  2132. * for free here (e.g. may be used for META_BG resize).
  2133. */
  2134. array_size = 1;
  2135. while (array_size < sizeof(*sbi->s_group_info) *
  2136. num_meta_group_infos_max)
  2137. array_size = array_size << 1;
  2138. /* An 8TB filesystem with 64-bit pointers requires a 4096 byte
  2139. * kmalloc. A 128kb malloc should suffice for a 256TB filesystem.
  2140. * So a two level scheme suffices for now. */
  2141. sbi->s_group_info = kmalloc(array_size, GFP_KERNEL);
  2142. if (sbi->s_group_info == NULL) {
  2143. printk(KERN_ERR "EXT4-fs: can't allocate buddy meta group\n");
  2144. return -ENOMEM;
  2145. }
  2146. sbi->s_buddy_cache = new_inode(sb);
  2147. if (sbi->s_buddy_cache == NULL) {
  2148. printk(KERN_ERR "EXT4-fs: can't get new inode\n");
  2149. goto err_freesgi;
  2150. }
  2151. EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;
  2152. metalen = sizeof(*meta_group_info) << EXT4_DESC_PER_BLOCK_BITS(sb);
  2153. for (i = 0; i < num_meta_group_infos; i++) {
  2154. if ((i + 1) == num_meta_group_infos)
  2155. metalen = sizeof(*meta_group_info) *
  2156. (sbi->s_groups_count -
  2157. (i << EXT4_DESC_PER_BLOCK_BITS(sb)));
  2158. meta_group_info = kmalloc(metalen, GFP_KERNEL);
  2159. if (meta_group_info == NULL) {
  2160. printk(KERN_ERR "EXT4-fs: can't allocate mem for a "
  2161. "buddy group\n");
  2162. goto err_freemeta;
  2163. }
  2164. sbi->s_group_info[i] = meta_group_info;
  2165. }
  2166. for (i = 0; i < sbi->s_groups_count; i++) {
  2167. desc = ext4_get_group_desc(sb, i, NULL);
  2168. if (desc == NULL) {
  2169. printk(KERN_ERR
  2170. "EXT4-fs: can't read descriptor %lu\n", i);
  2171. goto err_freebuddy;
  2172. }
  2173. if (ext4_mb_add_groupinfo(sb, i, desc) != 0)
  2174. goto err_freebuddy;
  2175. }
  2176. return 0;
  2177. err_freebuddy:
  2178. while (i-- > 0)
  2179. kfree(ext4_get_group_info(sb, i));
  2180. i = num_meta_group_infos;
  2181. err_freemeta:
  2182. while (i-- > 0)
  2183. kfree(sbi->s_group_info[i]);
  2184. iput(sbi->s_buddy_cache);
  2185. err_freesgi:
  2186. kfree(sbi->s_group_info);
  2187. return -ENOMEM;
  2188. }
  2189. int ext4_mb_init(struct super_block *sb, int needs_recovery)
  2190. {
  2191. struct ext4_sb_info *sbi = EXT4_SB(sb);
  2192. unsigned i, j;
  2193. unsigned offset;
  2194. unsigned max;
  2195. int ret;
  2196. i = (sb->s_blocksize_bits + 2) * sizeof(unsigned short);
  2197. sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL);
  2198. if (sbi->s_mb_offsets == NULL) {
  2199. return -ENOMEM;
  2200. }
  2201. sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL);
  2202. if (sbi->s_mb_maxs == NULL) {
  2203. kfree(sbi->s_mb_maxs);
  2204. return -ENOMEM;
  2205. }
  2206. /* order 0 is regular bitmap */
  2207. sbi->s_mb_maxs[0] = sb->s_blocksize << 3;
  2208. sbi->s_mb_offsets[0] = 0;
  2209. i = 1;
  2210. offset = 0;
  2211. max = sb->s_blocksize << 2;
  2212. do {
  2213. sbi->s_mb_offsets[i] = offset;
  2214. sbi->s_mb_maxs[i] = max;
  2215. offset += 1 << (sb->s_blocksize_bits - i);
  2216. max = max >> 1;
  2217. i++;
  2218. } while (i <= sb->s_blocksize_bits + 1);
  2219. /* init file for buddy data */
  2220. ret = ext4_mb_init_backend(sb);
  2221. if (ret != 0) {
  2222. kfree(sbi->s_mb_offsets);
  2223. kfree(sbi->s_mb_maxs);
  2224. return ret;
  2225. }
  2226. spin_lock_init(&sbi->s_md_lock);
  2227. INIT_LIST_HEAD(&sbi->s_active_transaction);
  2228. INIT_LIST_HEAD(&sbi->s_closed_transaction);
  2229. INIT_LIST_HEAD(&sbi->s_committed_transaction);
  2230. spin_lock_init(&sbi->s_bal_lock);
  2231. sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;
  2232. sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;
  2233. sbi->s_mb_stats = MB_DEFAULT_STATS;
  2234. sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;
  2235. sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;
  2236. sbi->s_mb_history_filter = EXT4_MB_HISTORY_DEFAULT;
  2237. sbi->s_mb_group_prealloc = MB_DEFAULT_GROUP_PREALLOC;
  2238. sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group);
  2239. if (sbi->s_locality_groups == NULL) {
  2240. kfree(sbi->s_mb_offsets);
  2241. kfree(sbi->s_mb_maxs);
  2242. return -ENOMEM;
  2243. }
  2244. for_each_possible_cpu(i) {
  2245. struct ext4_locality_group *lg;
  2246. lg = per_cpu_ptr(sbi->s_locality_groups, i);
  2247. mutex_init(&lg->lg_mutex);
  2248. for (j = 0; j < PREALLOC_TB_SIZE; j++)
  2249. INIT_LIST_HEAD(&lg->lg_prealloc_list[j]);
  2250. spin_lock_init(&lg->lg_prealloc_lock);
  2251. }
  2252. ext4_mb_init_per_dev_proc(sb);
  2253. ext4_mb_history_init(sb);
  2254. printk(KERN_INFO "EXT4-fs: mballoc enabled\n");
  2255. return 0;
  2256. }
  2257. /* need to called with ext4 group lock (ext4_lock_group) */
  2258. static void ext4_mb_cleanup_pa(struct ext4_group_info *grp)
  2259. {
  2260. struct ext4_prealloc_space *pa;
  2261. struct list_head *cur, *tmp;
  2262. int count = 0;
  2263. list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {
  2264. pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
  2265. list_del(&pa->pa_group_list);
  2266. count++;
  2267. kfree(pa);
  2268. }
  2269. if (count)
  2270. mb_debug("mballoc: %u PAs left\n", count);
  2271. }
  2272. int ext4_mb_release(struct super_block *sb)
  2273. {
  2274. ext4_group_t i;
  2275. int num_meta_group_infos;
  2276. struct ext4_group_info *grinfo;
  2277. struct ext4_sb_info *sbi = EXT4_SB(sb);
  2278. /* release freed, non-committed blocks */
  2279. spin_lock(&sbi->s_md_lock);
  2280. list_splice_init(&sbi->s_closed_transaction,
  2281. &sbi->s_committed_transaction);
  2282. list_splice_init(&sbi->s_active_transaction,
  2283. &sbi->s_committed_transaction);
  2284. spin_unlock(&sbi->s_md_lock);
  2285. ext4_mb_free_committed_blocks(sb);
  2286. if (sbi->s_group_info) {
  2287. for (i = 0; i < sbi->s_groups_count; i++) {
  2288. grinfo = ext4_get_group_info(sb, i);
  2289. #ifdef DOUBLE_CHECK
  2290. kfree(grinfo->bb_bitmap);
  2291. #endif
  2292. ext4_lock_group(sb, i);
  2293. ext4_mb_cleanup_pa(grinfo);
  2294. ext4_unlock_group(sb, i);
  2295. kfree(grinfo);
  2296. }
  2297. num_meta_group_infos = (sbi->s_groups_count +
  2298. EXT4_DESC_PER_BLOCK(sb) - 1) >>
  2299. EXT4_DESC_PER_BLOCK_BITS(sb);
  2300. for (i = 0; i < num_meta_group_infos; i++)
  2301. kfree(sbi->s_group_info[i]);
  2302. kfree(sbi->s_group_info);
  2303. }
  2304. kfree(sbi->s_mb_offsets);
  2305. kfree(sbi->s_mb_maxs);
  2306. if (sbi->s_buddy_cache)
  2307. iput(sbi->s_buddy_cache);
  2308. if (sbi->s_mb_stats) {
  2309. printk(KERN_INFO
  2310. "EXT4-fs: mballoc: %u blocks %u reqs (%u success)\n",
  2311. atomic_read(&sbi->s_bal_allocated),
  2312. atomic_read(&sbi->s_bal_reqs),
  2313. atomic_read(&sbi->s_bal_success));
  2314. printk(KERN_INFO
  2315. "EXT4-fs: mballoc: %u extents scanned, %u goal hits, "
  2316. "%u 2^N hits, %u breaks, %u lost\n",
  2317. atomic_read(&sbi->s_bal_ex_scanned),
  2318. atomic_read(&sbi->s_bal_goals),
  2319. atomic_read(&sbi->s_bal_2orders),
  2320. atomic_read(&sbi->s_bal_breaks),
  2321. atomic_read(&sbi->s_mb_lost_chunks));
  2322. printk(KERN_INFO
  2323. "EXT4-fs: mballoc: %lu generated and it took %Lu\n",
  2324. sbi->s_mb_buddies_generated++,
  2325. sbi->s_mb_generation_time);
  2326. printk(KERN_INFO
  2327. "EXT4-fs: mballoc: %u preallocated, %u discarded\n",
  2328. atomic_read(&sbi->s_mb_preallocated),
  2329. atomic_read(&sbi->s_mb_discarded));
  2330. }
  2331. free_percpu(sbi->s_locality_groups);
  2332. ext4_mb_history_release(sb);
  2333. ext4_mb_destroy_per_dev_proc(sb);
  2334. return 0;
  2335. }
  2336. static noinline_for_stack void
  2337. ext4_mb_free_committed_blocks(struct super_block *sb)
  2338. {
  2339. struct ext4_sb_info *sbi = EXT4_SB(sb);
  2340. int err;
  2341. int i;
  2342. int count = 0;
  2343. int count2 = 0;
  2344. struct ext4_free_metadata *md;
  2345. struct ext4_buddy e4b;
  2346. if (list_empty(&sbi->s_committed_transaction))
  2347. return;
  2348. /* there is committed blocks to be freed yet */
  2349. do {
  2350. /* get next array of blocks */
  2351. md = NULL;
  2352. spin_lock(&sbi->s_md_lock);
  2353. if (!list_empty(&sbi->s_committed_transaction)) {
  2354. md = list_entry(sbi->s_committed_transaction.next,
  2355. struct ext4_free_metadata, list);
  2356. list_del(&md->list);
  2357. }
  2358. spin_unlock(&sbi->s_md_lock);
  2359. if (md == NULL)
  2360. break;
  2361. mb_debug("gonna free %u blocks in group %lu (0x%p):",
  2362. md->num, md->group, md);
  2363. err = ext4_mb_load_buddy(sb, md->group, &e4b);
  2364. /* we expect to find existing buddy because it's pinned */
  2365. BUG_ON(err != 0);
  2366. /* there are blocks to put in buddy to make them really free */
  2367. count += md->num;
  2368. count2++;
  2369. ext4_lock_group(sb, md->group);
  2370. for (i = 0; i < md->num; i++) {
  2371. mb_debug(" %u", md->blocks[i]);
  2372. mb_free_blocks(NULL, &e4b, md->blocks[i], 1);
  2373. }
  2374. mb_debug("\n");
  2375. ext4_unlock_group(sb, md->group);
  2376. /* balance refcounts from ext4_mb_free_metadata() */
  2377. page_cache_release(e4b.bd_buddy_page);
  2378. page_cache_release(e4b.bd_bitmap_page);
  2379. kfree(md);
  2380. ext4_mb_release_desc(&e4b);
  2381. } while (md);
  2382. mb_debug("freed %u blocks in %u structures\n", count, count2);
  2383. }
  2384. #define EXT4_MB_STATS_NAME "stats"
  2385. #define EXT4_MB_MAX_TO_SCAN_NAME "max_to_scan"
  2386. #define EXT4_MB_MIN_TO_SCAN_NAME "min_to_scan"
  2387. #define EXT4_MB_ORDER2_REQ "order2_req"
  2388. #define EXT4_MB_STREAM_REQ "stream_req"
  2389. #define EXT4_MB_GROUP_PREALLOC "group_prealloc"
  2390. static int ext4_mb_init_per_dev_proc(struct super_block *sb)
  2391. {
  2392. mode_t mode = S_IFREG | S_IRUGO | S_IWUSR;
  2393. struct ext4_sb_info *sbi = EXT4_SB(sb);
  2394. struct proc_dir_entry *proc;
  2395. if (sbi->s_proc == NULL)
  2396. return -EINVAL;
  2397. EXT4_PROC_HANDLER(EXT4_MB_STATS_NAME, mb_stats);
  2398. EXT4_PROC_HANDLER(EXT4_MB_MAX_TO_SCAN_NAME, mb_max_to_scan);
  2399. EXT4_PROC_HANDLER(EXT4_MB_MIN_TO_SCAN_NAME, mb_min_to_scan);
  2400. EXT4_PROC_HANDLER(EXT4_MB_ORDER2_REQ, mb_order2_reqs);
  2401. EXT4_PROC_HANDLER(EXT4_MB_STREAM_REQ, mb_stream_request);
  2402. EXT4_PROC_HANDLER(EXT4_MB_GROUP_PREALLOC, mb_group_prealloc);
  2403. return 0;
  2404. err_out:
  2405. remove_proc_entry(EXT4_MB_GROUP_PREALLOC, sbi->s_proc);
  2406. remove_proc_entry(EXT4_MB_STREAM_REQ, sbi->s_proc);
  2407. remove_proc_entry(EXT4_MB_ORDER2_REQ, sbi->s_proc);
  2408. remove_proc_entry(EXT4_MB_MIN_TO_SCAN_NAME, sbi->s_proc);
  2409. remove_proc_entry(EXT4_MB_MAX_TO_SCAN_NAME, sbi->s_proc);
  2410. remove_proc_entry(EXT4_MB_STATS_NAME, sbi->s_proc);
  2411. return -ENOMEM;
  2412. }
  2413. static int ext4_mb_destroy_per_dev_proc(struct super_block *sb)
  2414. {
  2415. struct ext4_sb_info *sbi = EXT4_SB(sb);
  2416. if (sbi->s_proc == NULL)
  2417. return -EINVAL;
  2418. remove_proc_entry(EXT4_MB_GROUP_PREALLOC, sbi->s_proc);
  2419. remove_proc_entry(EXT4_MB_STREAM_REQ, sbi->s_proc);
  2420. remove_proc_entry(EXT4_MB_ORDER2_REQ, sbi->s_proc);
  2421. remove_proc_entry(EXT4_MB_MIN_TO_SCAN_NAME, sbi->s_proc);
  2422. remove_proc_entry(EXT4_MB_MAX_TO_SCAN_NAME, sbi->s_proc);
  2423. remove_proc_entry(EXT4_MB_STATS_NAME, sbi->s_proc);
  2424. return 0;
  2425. }
  2426. int __init init_ext4_mballoc(void)
  2427. {
  2428. ext4_pspace_cachep =
  2429. kmem_cache_create("ext4_prealloc_space",
  2430. sizeof(struct ext4_prealloc_space),
  2431. 0, SLAB_RECLAIM_ACCOUNT, NULL);
  2432. if (ext4_pspace_cachep == NULL)
  2433. return -ENOMEM;
  2434. ext4_ac_cachep =
  2435. kmem_cache_create("ext4_alloc_context",
  2436. sizeof(struct ext4_allocation_context),
  2437. 0, SLAB_RECLAIM_ACCOUNT, NULL);
  2438. if (ext4_ac_cachep == NULL) {
  2439. kmem_cache_destroy(ext4_pspace_cachep);
  2440. return -ENOMEM;
  2441. }
  2442. return 0;
  2443. }
  2444. void exit_ext4_mballoc(void)
  2445. {
  2446. /* XXX: synchronize_rcu(); */
  2447. kmem_cache_destroy(ext4_pspace_cachep);
  2448. kmem_cache_destroy(ext4_ac_cachep);
  2449. }
  2450. /*
  2451. * Check quota and mark choosed space (ac->ac_b_ex) non-free in bitmaps
  2452. * Returns 0 if success or error code
  2453. */
  2454. static noinline_for_stack int
  2455. ext4_mb_mark_diskspace_used(struct ext4_allocation_context *ac,
  2456. handle_t *handle, unsigned long reserv_blks)
  2457. {
  2458. struct buffer_head *bitmap_bh = NULL;
  2459. struct ext4_super_block *es;
  2460. struct ext4_group_desc *gdp;
  2461. struct buffer_head *gdp_bh;
  2462. struct ext4_sb_info *sbi;
  2463. struct super_block *sb;
  2464. ext4_fsblk_t block;
  2465. int err, len;
  2466. BUG_ON(ac->ac_status != AC_STATUS_FOUND);
  2467. BUG_ON(ac->ac_b_ex.fe_len <= 0);
  2468. sb = ac->ac_sb;
  2469. sbi = EXT4_SB(sb);
  2470. es = sbi->s_es;
  2471. err = -EIO;
  2472. bitmap_bh = ext4_read_block_bitmap(sb, ac->ac_b_ex.fe_group);
  2473. if (!bitmap_bh)
  2474. goto out_err;
  2475. err = ext4_journal_get_write_access(handle, bitmap_bh);
  2476. if (err)
  2477. goto out_err;
  2478. err = -EIO;
  2479. gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, &gdp_bh);
  2480. if (!gdp)
  2481. goto out_err;
  2482. ext4_debug("using block group %lu(%d)\n", ac->ac_b_ex.fe_group,
  2483. gdp->bg_free_blocks_count);
  2484. err = ext4_journal_get_write_access(handle, gdp_bh);
  2485. if (err)
  2486. goto out_err;
  2487. block = ac->ac_b_ex.fe_group * EXT4_BLOCKS_PER_GROUP(sb)
  2488. + ac->ac_b_ex.fe_start
  2489. + le32_to_cpu(es->s_first_data_block);
  2490. len = ac->ac_b_ex.fe_len;
  2491. if (in_range(ext4_block_bitmap(sb, gdp), block, len) ||
  2492. in_range(ext4_inode_bitmap(sb, gdp), block, len) ||
  2493. in_range(block, ext4_inode_table(sb, gdp),
  2494. EXT4_SB(sb)->s_itb_per_group) ||
  2495. in_range(block + len - 1, ext4_inode_table(sb, gdp),
  2496. EXT4_SB(sb)->s_itb_per_group)) {
  2497. ext4_error(sb, __func__,
  2498. "Allocating block in system zone - block = %llu",
  2499. block);
  2500. /* File system mounted not to panic on error
  2501. * Fix the bitmap and repeat the block allocation
  2502. * We leak some of the blocks here.
  2503. */
  2504. mb_set_bits(sb_bgl_lock(sbi, ac->ac_b_ex.fe_group),
  2505. bitmap_bh->b_data, ac->ac_b_ex.fe_start,
  2506. ac->ac_b_ex.fe_len);
  2507. err = ext4_journal_dirty_metadata(handle, bitmap_bh);
  2508. if (!err)
  2509. err = -EAGAIN;
  2510. goto out_err;
  2511. }
  2512. #ifdef AGGRESSIVE_CHECK
  2513. {
  2514. int i;
  2515. for (i = 0; i < ac->ac_b_ex.fe_len; i++) {
  2516. BUG_ON(mb_test_bit(ac->ac_b_ex.fe_start + i,
  2517. bitmap_bh->b_data));
  2518. }
  2519. }
  2520. #endif
  2521. mb_set_bits(sb_bgl_lock(sbi, ac->ac_b_ex.fe_group), bitmap_bh->b_data,
  2522. ac->ac_b_ex.fe_start, ac->ac_b_ex.fe_len);
  2523. spin_lock(sb_bgl_lock(sbi, ac->ac_b_ex.fe_group));
  2524. if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
  2525. gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
  2526. gdp->bg_free_blocks_count =
  2527. cpu_to_le16(ext4_free_blocks_after_init(sb,
  2528. ac->ac_b_ex.fe_group,
  2529. gdp));
  2530. }
  2531. le16_add_cpu(&gdp->bg_free_blocks_count, -ac->ac_b_ex.fe_len);
  2532. gdp->bg_checksum = ext4_group_desc_csum(sbi, ac->ac_b_ex.fe_group, gdp);
  2533. spin_unlock(sb_bgl_lock(sbi, ac->ac_b_ex.fe_group));
  2534. percpu_counter_sub(&sbi->s_freeblocks_counter, ac->ac_b_ex.fe_len);
  2535. /*
  2536. * Now reduce the dirty block count also. Should not go negative
  2537. */
  2538. if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))
  2539. /* release all the reserved blocks if non delalloc */
  2540. percpu_counter_sub(&sbi->s_dirtyblocks_counter, reserv_blks);
  2541. else
  2542. percpu_counter_sub(&sbi->s_dirtyblocks_counter,
  2543. ac->ac_b_ex.fe_len);
  2544. if (sbi->s_log_groups_per_flex) {
  2545. ext4_group_t flex_group = ext4_flex_group(sbi,
  2546. ac->ac_b_ex.fe_group);
  2547. spin_lock(sb_bgl_lock(sbi, flex_group));
  2548. sbi->s_flex_groups[flex_group].free_blocks -= ac->ac_b_ex.fe_len;
  2549. spin_unlock(sb_bgl_lock(sbi, flex_group));
  2550. }
  2551. err = ext4_journal_dirty_metadata(handle, bitmap_bh);
  2552. if (err)
  2553. goto out_err;
  2554. err = ext4_journal_dirty_metadata(handle, gdp_bh);
  2555. out_err:
  2556. sb->s_dirt = 1;
  2557. brelse(bitmap_bh);
  2558. return err;
  2559. }
  2560. /*
  2561. * here we normalize request for locality group
  2562. * Group request are normalized to s_strip size if we set the same via mount
  2563. * option. If not we set it to s_mb_group_prealloc which can be configured via
  2564. * /proc/fs/ext4/<partition>/group_prealloc
  2565. *
  2566. * XXX: should we try to preallocate more than the group has now?
  2567. */
  2568. static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac)
  2569. {
  2570. struct super_block *sb = ac->ac_sb;
  2571. struct ext4_locality_group *lg = ac->ac_lg;
  2572. BUG_ON(lg == NULL);
  2573. if (EXT4_SB(sb)->s_stripe)
  2574. ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_stripe;
  2575. else
  2576. ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;
  2577. mb_debug("#%u: goal %u blocks for locality group\n",
  2578. current->pid, ac->ac_g_ex.fe_len);
  2579. }
  2580. /*
  2581. * Normalization means making request better in terms of
  2582. * size and alignment
  2583. */
  2584. static noinline_for_stack void
  2585. ext4_mb_normalize_request(struct ext4_allocation_context *ac,
  2586. struct ext4_allocation_request *ar)
  2587. {
  2588. int bsbits, max;
  2589. ext4_lblk_t end;
  2590. loff_t size, orig_size, start_off;
  2591. ext4_lblk_t start, orig_start;
  2592. struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
  2593. struct ext4_prealloc_space *pa;
  2594. /* do normalize only data requests, metadata requests
  2595. do not need preallocation */
  2596. if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
  2597. return;
  2598. /* sometime caller may want exact blocks */
  2599. if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
  2600. return;
  2601. /* caller may indicate that preallocation isn't
  2602. * required (it's a tail, for example) */
  2603. if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)
  2604. return;
  2605. if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {
  2606. ext4_mb_normalize_group_request(ac);
  2607. return ;
  2608. }
  2609. bsbits = ac->ac_sb->s_blocksize_bits;
  2610. /* first, let's learn actual file size
  2611. * given current request is allocated */
  2612. size = ac->ac_o_ex.fe_logical + ac->ac_o_ex.fe_len;
  2613. size = size << bsbits;
  2614. if (size < i_size_read(ac->ac_inode))
  2615. size = i_size_read(ac->ac_inode);
  2616. /* max size of free chunks */
  2617. max = 2 << bsbits;
  2618. #define NRL_CHECK_SIZE(req, size, max, chunk_size) \
  2619. (req <= (size) || max <= (chunk_size))
  2620. /* first, try to predict filesize */
  2621. /* XXX: should this table be tunable? */
  2622. start_off = 0;
  2623. if (size <= 16 * 1024) {
  2624. size = 16 * 1024;
  2625. } else if (size <= 32 * 1024) {
  2626. size = 32 * 1024;
  2627. } else if (size <= 64 * 1024) {
  2628. size = 64 * 1024;
  2629. } else if (size <= 128 * 1024) {
  2630. size = 128 * 1024;
  2631. } else if (size <= 256 * 1024) {
  2632. size = 256 * 1024;
  2633. } else if (size <= 512 * 1024) {
  2634. size = 512 * 1024;
  2635. } else if (size <= 1024 * 1024) {
  2636. size = 1024 * 1024;
  2637. } else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) {
  2638. start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
  2639. (21 - bsbits)) << 21;
  2640. size = 2 * 1024 * 1024;
  2641. } else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) {
  2642. start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
  2643. (22 - bsbits)) << 22;
  2644. size = 4 * 1024 * 1024;
  2645. } else if (NRL_CHECK_SIZE(ac->ac_o_ex.fe_len,
  2646. (8<<20)>>bsbits, max, 8 * 1024)) {
  2647. start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
  2648. (23 - bsbits)) << 23;
  2649. size = 8 * 1024 * 1024;
  2650. } else {
  2651. start_off = (loff_t)ac->ac_o_ex.fe_logical << bsbits;
  2652. size = ac->ac_o_ex.fe_len << bsbits;
  2653. }
  2654. orig_size = size = size >> bsbits;
  2655. orig_start = start = start_off >> bsbits;
  2656. /* don't cover already allocated blocks in selected range */
  2657. if (ar->pleft && start <= ar->lleft) {
  2658. size -= ar->lleft + 1 - start;
  2659. start = ar->lleft + 1;
  2660. }
  2661. if (ar->pright && start + size - 1 >= ar->lright)
  2662. size -= start + size - ar->lright;
  2663. end = start + size;
  2664. /* check we don't cross already preallocated blocks */
  2665. rcu_read_lock();
  2666. list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
  2667. unsigned long pa_end;
  2668. if (pa->pa_deleted)
  2669. continue;
  2670. spin_lock(&pa->pa_lock);
  2671. if (pa->pa_deleted) {
  2672. spin_unlock(&pa->pa_lock);
  2673. continue;
  2674. }
  2675. pa_end = pa->pa_lstart + pa->pa_len;
  2676. /* PA must not overlap original request */
  2677. BUG_ON(!(ac->ac_o_ex.fe_logical >= pa_end ||
  2678. ac->ac_o_ex.fe_logical < pa->pa_lstart));
  2679. /* skip PA normalized request doesn't overlap with */
  2680. if (pa->pa_lstart >= end) {
  2681. spin_unlock(&pa->pa_lock);
  2682. continue;
  2683. }
  2684. if (pa_end <= start) {
  2685. spin_unlock(&pa->pa_lock);
  2686. continue;
  2687. }
  2688. BUG_ON(pa->pa_lstart <= start && pa_end >= end);
  2689. if (pa_end <= ac->ac_o_ex.fe_logical) {
  2690. BUG_ON(pa_end < start);
  2691. start = pa_end;
  2692. }
  2693. if (pa->pa_lstart > ac->ac_o_ex.fe_logical) {
  2694. BUG_ON(pa->pa_lstart > end);
  2695. end = pa->pa_lstart;
  2696. }
  2697. spin_unlock(&pa->pa_lock);
  2698. }
  2699. rcu_read_unlock();
  2700. size = end - start;
  2701. /* XXX: extra loop to check we really don't overlap preallocations */
  2702. rcu_read_lock();
  2703. list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
  2704. unsigned long pa_end;
  2705. spin_lock(&pa->pa_lock);
  2706. if (pa->pa_deleted == 0) {
  2707. pa_end = pa->pa_lstart + pa->pa_len;
  2708. BUG_ON(!(start >= pa_end || end <= pa->pa_lstart));
  2709. }
  2710. spin_unlock(&pa->pa_lock);
  2711. }
  2712. rcu_read_unlock();
  2713. if (start + size <= ac->ac_o_ex.fe_logical &&
  2714. start > ac->ac_o_ex.fe_logical) {
  2715. printk(KERN_ERR "start %lu, size %lu, fe_logical %lu\n",
  2716. (unsigned long) start, (unsigned long) size,
  2717. (unsigned long) ac->ac_o_ex.fe_logical);
  2718. }
  2719. BUG_ON(start + size <= ac->ac_o_ex.fe_logical &&
  2720. start > ac->ac_o_ex.fe_logical);
  2721. BUG_ON(size <= 0 || size >= EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
  2722. /* now prepare goal request */
  2723. /* XXX: is it better to align blocks WRT to logical
  2724. * placement or satisfy big request as is */
  2725. ac->ac_g_ex.fe_logical = start;
  2726. ac->ac_g_ex.fe_len = size;
  2727. /* define goal start in order to merge */
  2728. if (ar->pright && (ar->lright == (start + size))) {
  2729. /* merge to the right */
  2730. ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,
  2731. &ac->ac_f_ex.fe_group,
  2732. &ac->ac_f_ex.fe_start);
  2733. ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
  2734. }
  2735. if (ar->pleft && (ar->lleft + 1 == start)) {
  2736. /* merge to the left */
  2737. ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,
  2738. &ac->ac_f_ex.fe_group,
  2739. &ac->ac_f_ex.fe_start);
  2740. ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
  2741. }
  2742. mb_debug("goal: %u(was %u) blocks at %u\n", (unsigned) size,
  2743. (unsigned) orig_size, (unsigned) start);
  2744. }
  2745. static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)
  2746. {
  2747. struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
  2748. if (sbi->s_mb_stats && ac->ac_g_ex.fe_len > 1) {
  2749. atomic_inc(&sbi->s_bal_reqs);
  2750. atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);
  2751. if (ac->ac_o_ex.fe_len >= ac->ac_g_ex.fe_len)
  2752. atomic_inc(&sbi->s_bal_success);
  2753. atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);
  2754. if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
  2755. ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
  2756. atomic_inc(&sbi->s_bal_goals);
  2757. if (ac->ac_found > sbi->s_mb_max_to_scan)
  2758. atomic_inc(&sbi->s_bal_breaks);
  2759. }
  2760. ext4_mb_store_history(ac);
  2761. }
  2762. /*
  2763. * use blocks preallocated to inode
  2764. */
  2765. static void ext4_mb_use_inode_pa(struct ext4_allocation_context *ac,
  2766. struct ext4_prealloc_space *pa)
  2767. {
  2768. ext4_fsblk_t start;
  2769. ext4_fsblk_t end;
  2770. int len;
  2771. /* found preallocated blocks, use them */
  2772. start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);
  2773. end = min(pa->pa_pstart + pa->pa_len, start + ac->ac_o_ex.fe_len);
  2774. len = end - start;
  2775. ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,
  2776. &ac->ac_b_ex.fe_start);
  2777. ac->ac_b_ex.fe_len = len;
  2778. ac->ac_status = AC_STATUS_FOUND;
  2779. ac->ac_pa = pa;
  2780. BUG_ON(start < pa->pa_pstart);
  2781. BUG_ON(start + len > pa->pa_pstart + pa->pa_len);
  2782. BUG_ON(pa->pa_free < len);
  2783. pa->pa_free -= len;
  2784. mb_debug("use %llu/%u from inode pa %p\n", start, len, pa);
  2785. }
  2786. /*
  2787. * use blocks preallocated to locality group
  2788. */
  2789. static void ext4_mb_use_group_pa(struct ext4_allocation_context *ac,
  2790. struct ext4_prealloc_space *pa)
  2791. {
  2792. unsigned int len = ac->ac_o_ex.fe_len;
  2793. ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,
  2794. &ac->ac_b_ex.fe_group,
  2795. &ac->ac_b_ex.fe_start);
  2796. ac->ac_b_ex.fe_len = len;
  2797. ac->ac_status = AC_STATUS_FOUND;
  2798. ac->ac_pa = pa;
  2799. /* we don't correct pa_pstart or pa_plen here to avoid
  2800. * possible race when the group is being loaded concurrently
  2801. * instead we correct pa later, after blocks are marked
  2802. * in on-disk bitmap -- see ext4_mb_release_context()
  2803. * Other CPUs are prevented from allocating from this pa by lg_mutex
  2804. */
  2805. mb_debug("use %u/%u from group pa %p\n", pa->pa_lstart-len, len, pa);
  2806. }
  2807. /*
  2808. * Return the prealloc space that have minimal distance
  2809. * from the goal block. @cpa is the prealloc
  2810. * space that is having currently known minimal distance
  2811. * from the goal block.
  2812. */
  2813. static struct ext4_prealloc_space *
  2814. ext4_mb_check_group_pa(ext4_fsblk_t goal_block,
  2815. struct ext4_prealloc_space *pa,
  2816. struct ext4_prealloc_space *cpa)
  2817. {
  2818. ext4_fsblk_t cur_distance, new_distance;
  2819. if (cpa == NULL) {
  2820. atomic_inc(&pa->pa_count);
  2821. return pa;
  2822. }
  2823. cur_distance = abs(goal_block - cpa->pa_pstart);
  2824. new_distance = abs(goal_block - pa->pa_pstart);
  2825. if (cur_distance < new_distance)
  2826. return cpa;
  2827. /* drop the previous reference */
  2828. atomic_dec(&cpa->pa_count);
  2829. atomic_inc(&pa->pa_count);
  2830. return pa;
  2831. }
  2832. /*
  2833. * search goal blocks in preallocated space
  2834. */
  2835. static noinline_for_stack int
  2836. ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
  2837. {
  2838. int order, i;
  2839. struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
  2840. struct ext4_locality_group *lg;
  2841. struct ext4_prealloc_space *pa, *cpa = NULL;
  2842. ext4_fsblk_t goal_block;
  2843. /* only data can be preallocated */
  2844. if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
  2845. return 0;
  2846. /* first, try per-file preallocation */
  2847. rcu_read_lock();
  2848. list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
  2849. /* all fields in this condition don't change,
  2850. * so we can skip locking for them */
  2851. if (ac->ac_o_ex.fe_logical < pa->pa_lstart ||
  2852. ac->ac_o_ex.fe_logical >= pa->pa_lstart + pa->pa_len)
  2853. continue;
  2854. /* found preallocated blocks, use them */
  2855. spin_lock(&pa->pa_lock);
  2856. if (pa->pa_deleted == 0 && pa->pa_free) {
  2857. atomic_inc(&pa->pa_count);
  2858. ext4_mb_use_inode_pa(ac, pa);
  2859. spin_unlock(&pa->pa_lock);
  2860. ac->ac_criteria = 10;
  2861. rcu_read_unlock();
  2862. return 1;
  2863. }
  2864. spin_unlock(&pa->pa_lock);
  2865. }
  2866. rcu_read_unlock();
  2867. /* can we use group allocation? */
  2868. if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))
  2869. return 0;
  2870. /* inode may have no locality group for some reason */
  2871. lg = ac->ac_lg;
  2872. if (lg == NULL)
  2873. return 0;
  2874. order = fls(ac->ac_o_ex.fe_len) - 1;
  2875. if (order > PREALLOC_TB_SIZE - 1)
  2876. /* The max size of hash table is PREALLOC_TB_SIZE */
  2877. order = PREALLOC_TB_SIZE - 1;
  2878. goal_block = ac->ac_g_ex.fe_group * EXT4_BLOCKS_PER_GROUP(ac->ac_sb) +
  2879. ac->ac_g_ex.fe_start +
  2880. le32_to_cpu(EXT4_SB(ac->ac_sb)->s_es->s_first_data_block);
  2881. /*
  2882. * search for the prealloc space that is having
  2883. * minimal distance from the goal block.
  2884. */
  2885. for (i = order; i < PREALLOC_TB_SIZE; i++) {
  2886. rcu_read_lock();
  2887. list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[i],
  2888. pa_inode_list) {
  2889. spin_lock(&pa->pa_lock);
  2890. if (pa->pa_deleted == 0 &&
  2891. pa->pa_free >= ac->ac_o_ex.fe_len) {
  2892. cpa = ext4_mb_check_group_pa(goal_block,
  2893. pa, cpa);
  2894. }
  2895. spin_unlock(&pa->pa_lock);
  2896. }
  2897. rcu_read_unlock();
  2898. }
  2899. if (cpa) {
  2900. ext4_mb_use_group_pa(ac, cpa);
  2901. ac->ac_criteria = 20;
  2902. return 1;
  2903. }
  2904. return 0;
  2905. }
  2906. /*
  2907. * the function goes through all preallocation in this group and marks them
  2908. * used in in-core bitmap. buddy must be generated from this bitmap
  2909. * Need to be called with ext4 group lock (ext4_lock_group)
  2910. */
  2911. static void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
  2912. ext4_group_t group)
  2913. {
  2914. struct ext4_group_info *grp = ext4_get_group_info(sb, group);
  2915. struct ext4_prealloc_space *pa;
  2916. struct list_head *cur;
  2917. ext4_group_t groupnr;
  2918. ext4_grpblk_t start;
  2919. int preallocated = 0;
  2920. int count = 0;
  2921. int len;
  2922. /* all form of preallocation discards first load group,
  2923. * so the only competing code is preallocation use.
  2924. * we don't need any locking here
  2925. * notice we do NOT ignore preallocations with pa_deleted
  2926. * otherwise we could leave used blocks available for
  2927. * allocation in buddy when concurrent ext4_mb_put_pa()
  2928. * is dropping preallocation
  2929. */
  2930. list_for_each(cur, &grp->bb_prealloc_list) {
  2931. pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
  2932. spin_lock(&pa->pa_lock);
  2933. ext4_get_group_no_and_offset(sb, pa->pa_pstart,
  2934. &groupnr, &start);
  2935. len = pa->pa_len;
  2936. spin_unlock(&pa->pa_lock);
  2937. if (unlikely(len == 0))
  2938. continue;
  2939. BUG_ON(groupnr != group);
  2940. mb_set_bits(sb_bgl_lock(EXT4_SB(sb), group),
  2941. bitmap, start, len);
  2942. preallocated += len;
  2943. count++;
  2944. }
  2945. mb_debug("prellocated %u for group %lu\n", preallocated, group);
  2946. }
  2947. static void ext4_mb_pa_callback(struct rcu_head *head)
  2948. {
  2949. struct ext4_prealloc_space *pa;
  2950. pa = container_of(head, struct ext4_prealloc_space, u.pa_rcu);
  2951. kmem_cache_free(ext4_pspace_cachep, pa);
  2952. }
  2953. /*
  2954. * drops a reference to preallocated space descriptor
  2955. * if this was the last reference and the space is consumed
  2956. */
  2957. static void ext4_mb_put_pa(struct ext4_allocation_context *ac,
  2958. struct super_block *sb, struct ext4_prealloc_space *pa)
  2959. {
  2960. unsigned long grp;
  2961. if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0)
  2962. return;
  2963. /* in this short window concurrent discard can set pa_deleted */
  2964. spin_lock(&pa->pa_lock);
  2965. if (pa->pa_deleted == 1) {
  2966. spin_unlock(&pa->pa_lock);
  2967. return;
  2968. }
  2969. pa->pa_deleted = 1;
  2970. spin_unlock(&pa->pa_lock);
  2971. /* -1 is to protect from crossing allocation group */
  2972. ext4_get_group_no_and_offset(sb, pa->pa_pstart - 1, &grp, NULL);
  2973. /*
  2974. * possible race:
  2975. *
  2976. * P1 (buddy init) P2 (regular allocation)
  2977. * find block B in PA
  2978. * copy on-disk bitmap to buddy
  2979. * mark B in on-disk bitmap
  2980. * drop PA from group
  2981. * mark all PAs in buddy
  2982. *
  2983. * thus, P1 initializes buddy with B available. to prevent this
  2984. * we make "copy" and "mark all PAs" atomic and serialize "drop PA"
  2985. * against that pair
  2986. */
  2987. ext4_lock_group(sb, grp);
  2988. list_del(&pa->pa_group_list);
  2989. ext4_unlock_group(sb, grp);
  2990. spin_lock(pa->pa_obj_lock);
  2991. list_del_rcu(&pa->pa_inode_list);
  2992. spin_unlock(pa->pa_obj_lock);
  2993. call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
  2994. }
  2995. /*
  2996. * creates new preallocated space for given inode
  2997. */
  2998. static noinline_for_stack int
  2999. ext4_mb_new_inode_pa(struct ext4_allocation_context *ac)
  3000. {
  3001. struct super_block *sb = ac->ac_sb;
  3002. struct ext4_prealloc_space *pa;
  3003. struct ext4_group_info *grp;
  3004. struct ext4_inode_info *ei;
  3005. /* preallocate only when found space is larger then requested */
  3006. BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
  3007. BUG_ON(ac->ac_status != AC_STATUS_FOUND);
  3008. BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
  3009. pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
  3010. if (pa == NULL)
  3011. return -ENOMEM;
  3012. if (ac->ac_b_ex.fe_len < ac->ac_g_ex.fe_len) {
  3013. int winl;
  3014. int wins;
  3015. int win;
  3016. int offs;
  3017. /* we can't allocate as much as normalizer wants.
  3018. * so, found space must get proper lstart
  3019. * to cover original request */
  3020. BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);
  3021. BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);
  3022. /* we're limited by original request in that
  3023. * logical block must be covered any way
  3024. * winl is window we can move our chunk within */
  3025. winl = ac->ac_o_ex.fe_logical - ac->ac_g_ex.fe_logical;
  3026. /* also, we should cover whole original request */
  3027. wins = ac->ac_b_ex.fe_len - ac->ac_o_ex.fe_len;
  3028. /* the smallest one defines real window */
  3029. win = min(winl, wins);
  3030. offs = ac->ac_o_ex.fe_logical % ac->ac_b_ex.fe_len;
  3031. if (offs && offs < win)
  3032. win = offs;
  3033. ac->ac_b_ex.fe_logical = ac->ac_o_ex.fe_logical - win;
  3034. BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);
  3035. BUG_ON(ac->ac_o_ex.fe_len > ac->ac_b_ex.fe_len);
  3036. }
  3037. /* preallocation can change ac_b_ex, thus we store actually
  3038. * allocated blocks for history */
  3039. ac->ac_f_ex = ac->ac_b_ex;
  3040. pa->pa_lstart = ac->ac_b_ex.fe_logical;
  3041. pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
  3042. pa->pa_len = ac->ac_b_ex.fe_len;
  3043. pa->pa_free = pa->pa_len;
  3044. atomic_set(&pa->pa_count, 1);
  3045. spin_lock_init(&pa->pa_lock);
  3046. pa->pa_deleted = 0;
  3047. pa->pa_linear = 0;
  3048. mb_debug("new inode pa %p: %llu/%u for %u\n", pa,
  3049. pa->pa_pstart, pa->pa_len, pa->pa_lstart);
  3050. ext4_mb_use_inode_pa(ac, pa);
  3051. atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);
  3052. ei = EXT4_I(ac->ac_inode);
  3053. grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
  3054. pa->pa_obj_lock = &ei->i_prealloc_lock;
  3055. pa->pa_inode = ac->ac_inode;
  3056. ext4_lock_group(sb, ac->ac_b_ex.fe_group);
  3057. list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
  3058. ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
  3059. spin_lock(pa->pa_obj_lock);
  3060. list_add_rcu(&pa->pa_inode_list, &ei->i_prealloc_list);
  3061. spin_unlock(pa->pa_obj_lock);
  3062. return 0;
  3063. }
  3064. /*
  3065. * creates new preallocated space for locality group inodes belongs to
  3066. */
  3067. static noinline_for_stack int
  3068. ext4_mb_new_group_pa(struct ext4_allocation_context *ac)
  3069. {
  3070. struct super_block *sb = ac->ac_sb;
  3071. struct ext4_locality_group *lg;
  3072. struct ext4_prealloc_space *pa;
  3073. struct ext4_group_info *grp;
  3074. /* preallocate only when found space is larger then requested */
  3075. BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
  3076. BUG_ON(ac->ac_status != AC_STATUS_FOUND);
  3077. BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
  3078. BUG_ON(ext4_pspace_cachep == NULL);
  3079. pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
  3080. if (pa == NULL)
  3081. return -ENOMEM;
  3082. /* preallocation can change ac_b_ex, thus we store actually
  3083. * allocated blocks for history */
  3084. ac->ac_f_ex = ac->ac_b_ex;
  3085. pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
  3086. pa->pa_lstart = pa->pa_pstart;
  3087. pa->pa_len = ac->ac_b_ex.fe_len;
  3088. pa->pa_free = pa->pa_len;
  3089. atomic_set(&pa->pa_count, 1);
  3090. spin_lock_init(&pa->pa_lock);
  3091. INIT_LIST_HEAD(&pa->pa_inode_list);
  3092. pa->pa_deleted = 0;
  3093. pa->pa_linear = 1;
  3094. mb_debug("new group pa %p: %llu/%u for %u\n", pa,
  3095. pa->pa_pstart, pa->pa_len, pa->pa_lstart);
  3096. ext4_mb_use_group_pa(ac, pa);
  3097. atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);
  3098. grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
  3099. lg = ac->ac_lg;
  3100. BUG_ON(lg == NULL);
  3101. pa->pa_obj_lock = &lg->lg_prealloc_lock;
  3102. pa->pa_inode = NULL;
  3103. ext4_lock_group(sb, ac->ac_b_ex.fe_group);
  3104. list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
  3105. ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
  3106. /*
  3107. * We will later add the new pa to the right bucket
  3108. * after updating the pa_free in ext4_mb_release_context
  3109. */
  3110. return 0;
  3111. }
  3112. static int ext4_mb_new_preallocation(struct ext4_allocation_context *ac)
  3113. {
  3114. int err;
  3115. if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
  3116. err = ext4_mb_new_group_pa(ac);
  3117. else
  3118. err = ext4_mb_new_inode_pa(ac);
  3119. return err;
  3120. }
  3121. /*
  3122. * finds all unused blocks in on-disk bitmap, frees them in
  3123. * in-core bitmap and buddy.
  3124. * @pa must be unlinked from inode and group lists, so that
  3125. * nobody else can find/use it.
  3126. * the caller MUST hold group/inode locks.
  3127. * TODO: optimize the case when there are no in-core structures yet
  3128. */
  3129. static noinline_for_stack int
  3130. ext4_mb_release_inode_pa(struct ext4_buddy *e4b, struct buffer_head *bitmap_bh,
  3131. struct ext4_prealloc_space *pa,
  3132. struct ext4_allocation_context *ac)
  3133. {
  3134. struct super_block *sb = e4b->bd_sb;
  3135. struct ext4_sb_info *sbi = EXT4_SB(sb);
  3136. unsigned long end;
  3137. unsigned long next;
  3138. ext4_group_t group;
  3139. ext4_grpblk_t bit;
  3140. sector_t start;
  3141. int err = 0;
  3142. int free = 0;
  3143. BUG_ON(pa->pa_deleted == 0);
  3144. ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
  3145. BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
  3146. end = bit + pa->pa_len;
  3147. if (ac) {
  3148. ac->ac_sb = sb;
  3149. ac->ac_inode = pa->pa_inode;
  3150. ac->ac_op = EXT4_MB_HISTORY_DISCARD;
  3151. }
  3152. while (bit < end) {
  3153. bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);
  3154. if (bit >= end)
  3155. break;
  3156. next = mb_find_next_bit(bitmap_bh->b_data, end, bit);
  3157. start = group * EXT4_BLOCKS_PER_GROUP(sb) + bit +
  3158. le32_to_cpu(sbi->s_es->s_first_data_block);
  3159. mb_debug(" free preallocated %u/%u in group %u\n",
  3160. (unsigned) start, (unsigned) next - bit,
  3161. (unsigned) group);
  3162. free += next - bit;
  3163. if (ac) {
  3164. ac->ac_b_ex.fe_group = group;
  3165. ac->ac_b_ex.fe_start = bit;
  3166. ac->ac_b_ex.fe_len = next - bit;
  3167. ac->ac_b_ex.fe_logical = 0;
  3168. ext4_mb_store_history(ac);
  3169. }
  3170. mb_free_blocks(pa->pa_inode, e4b, bit, next - bit);
  3171. bit = next + 1;
  3172. }
  3173. if (free != pa->pa_free) {
  3174. printk(KERN_CRIT "pa %p: logic %lu, phys. %lu, len %lu\n",
  3175. pa, (unsigned long) pa->pa_lstart,
  3176. (unsigned long) pa->pa_pstart,
  3177. (unsigned long) pa->pa_len);
  3178. ext4_error(sb, __func__, "free %u, pa_free %u\n",
  3179. free, pa->pa_free);
  3180. /*
  3181. * pa is already deleted so we use the value obtained
  3182. * from the bitmap and continue.
  3183. */
  3184. }
  3185. atomic_add(free, &sbi->s_mb_discarded);
  3186. return err;
  3187. }
  3188. static noinline_for_stack int
  3189. ext4_mb_release_group_pa(struct ext4_buddy *e4b,
  3190. struct ext4_prealloc_space *pa,
  3191. struct ext4_allocation_context *ac)
  3192. {
  3193. struct super_block *sb = e4b->bd_sb;
  3194. ext4_group_t group;
  3195. ext4_grpblk_t bit;
  3196. if (ac)
  3197. ac->ac_op = EXT4_MB_HISTORY_DISCARD;
  3198. BUG_ON(pa->pa_deleted == 0);
  3199. ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
  3200. BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
  3201. mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len);
  3202. atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded);
  3203. if (ac) {
  3204. ac->ac_sb = sb;
  3205. ac->ac_inode = NULL;
  3206. ac->ac_b_ex.fe_group = group;
  3207. ac->ac_b_ex.fe_start = bit;
  3208. ac->ac_b_ex.fe_len = pa->pa_len;
  3209. ac->ac_b_ex.fe_logical = 0;
  3210. ext4_mb_store_history(ac);
  3211. }
  3212. return 0;
  3213. }
  3214. /*
  3215. * releases all preallocations in given group
  3216. *
  3217. * first, we need to decide discard policy:
  3218. * - when do we discard
  3219. * 1) ENOSPC
  3220. * - how many do we discard
  3221. * 1) how many requested
  3222. */
  3223. static noinline_for_stack int
  3224. ext4_mb_discard_group_preallocations(struct super_block *sb,
  3225. ext4_group_t group, int needed)
  3226. {
  3227. struct ext4_group_info *grp = ext4_get_group_info(sb, group);
  3228. struct buffer_head *bitmap_bh = NULL;
  3229. struct ext4_prealloc_space *pa, *tmp;
  3230. struct ext4_allocation_context *ac;
  3231. struct list_head list;
  3232. struct ext4_buddy e4b;
  3233. int err;
  3234. int busy = 0;
  3235. int free = 0;
  3236. mb_debug("discard preallocation for group %lu\n", group);
  3237. if (list_empty(&grp->bb_prealloc_list))
  3238. return 0;
  3239. bitmap_bh = ext4_read_block_bitmap(sb, group);
  3240. if (bitmap_bh == NULL) {
  3241. ext4_error(sb, __func__, "Error in reading block "
  3242. "bitmap for %lu\n", group);
  3243. return 0;
  3244. }
  3245. err = ext4_mb_load_buddy(sb, group, &e4b);
  3246. if (err) {
  3247. ext4_error(sb, __func__, "Error in loading buddy "
  3248. "information for %lu\n", group);
  3249. put_bh(bitmap_bh);
  3250. return 0;
  3251. }
  3252. if (needed == 0)
  3253. needed = EXT4_BLOCKS_PER_GROUP(sb) + 1;
  3254. INIT_LIST_HEAD(&list);
  3255. ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
  3256. repeat:
  3257. ext4_lock_group(sb, group);
  3258. list_for_each_entry_safe(pa, tmp,
  3259. &grp->bb_prealloc_list, pa_group_list) {
  3260. spin_lock(&pa->pa_lock);
  3261. if (atomic_read(&pa->pa_count)) {
  3262. spin_unlock(&pa->pa_lock);
  3263. busy = 1;
  3264. continue;
  3265. }
  3266. if (pa->pa_deleted) {
  3267. spin_unlock(&pa->pa_lock);
  3268. continue;
  3269. }
  3270. /* seems this one can be freed ... */
  3271. pa->pa_deleted = 1;
  3272. /* we can trust pa_free ... */
  3273. free += pa->pa_free;
  3274. spin_unlock(&pa->pa_lock);
  3275. list_del(&pa->pa_group_list);
  3276. list_add(&pa->u.pa_tmp_list, &list);
  3277. }
  3278. /* if we still need more blocks and some PAs were used, try again */
  3279. if (free < needed && busy) {
  3280. busy = 0;
  3281. ext4_unlock_group(sb, group);
  3282. /*
  3283. * Yield the CPU here so that we don't get soft lockup
  3284. * in non preempt case.
  3285. */
  3286. yield();
  3287. goto repeat;
  3288. }
  3289. /* found anything to free? */
  3290. if (list_empty(&list)) {
  3291. BUG_ON(free != 0);
  3292. goto out;
  3293. }
  3294. /* now free all selected PAs */
  3295. list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
  3296. /* remove from object (inode or locality group) */
  3297. spin_lock(pa->pa_obj_lock);
  3298. list_del_rcu(&pa->pa_inode_list);
  3299. spin_unlock(pa->pa_obj_lock);
  3300. if (pa->pa_linear)
  3301. ext4_mb_release_group_pa(&e4b, pa, ac);
  3302. else
  3303. ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa, ac);
  3304. list_del(&pa->u.pa_tmp_list);
  3305. call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
  3306. }
  3307. out:
  3308. ext4_unlock_group(sb, group);
  3309. if (ac)
  3310. kmem_cache_free(ext4_ac_cachep, ac);
  3311. ext4_mb_release_desc(&e4b);
  3312. put_bh(bitmap_bh);
  3313. return free;
  3314. }
  3315. /*
  3316. * releases all non-used preallocated blocks for given inode
  3317. *
  3318. * It's important to discard preallocations under i_data_sem
  3319. * We don't want another block to be served from the prealloc
  3320. * space when we are discarding the inode prealloc space.
  3321. *
  3322. * FIXME!! Make sure it is valid at all the call sites
  3323. */
  3324. void ext4_discard_preallocations(struct inode *inode)
  3325. {
  3326. struct ext4_inode_info *ei = EXT4_I(inode);
  3327. struct super_block *sb = inode->i_sb;
  3328. struct buffer_head *bitmap_bh = NULL;
  3329. struct ext4_prealloc_space *pa, *tmp;
  3330. struct ext4_allocation_context *ac;
  3331. ext4_group_t group = 0;
  3332. struct list_head list;
  3333. struct ext4_buddy e4b;
  3334. int err;
  3335. if (!S_ISREG(inode->i_mode)) {
  3336. /*BUG_ON(!list_empty(&ei->i_prealloc_list));*/
  3337. return;
  3338. }
  3339. mb_debug("discard preallocation for inode %lu\n", inode->i_ino);
  3340. INIT_LIST_HEAD(&list);
  3341. ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
  3342. repeat:
  3343. /* first, collect all pa's in the inode */
  3344. spin_lock(&ei->i_prealloc_lock);
  3345. while (!list_empty(&ei->i_prealloc_list)) {
  3346. pa = list_entry(ei->i_prealloc_list.next,
  3347. struct ext4_prealloc_space, pa_inode_list);
  3348. BUG_ON(pa->pa_obj_lock != &ei->i_prealloc_lock);
  3349. spin_lock(&pa->pa_lock);
  3350. if (atomic_read(&pa->pa_count)) {
  3351. /* this shouldn't happen often - nobody should
  3352. * use preallocation while we're discarding it */
  3353. spin_unlock(&pa->pa_lock);
  3354. spin_unlock(&ei->i_prealloc_lock);
  3355. printk(KERN_ERR "uh-oh! used pa while discarding\n");
  3356. WARN_ON(1);
  3357. schedule_timeout_uninterruptible(HZ);
  3358. goto repeat;
  3359. }
  3360. if (pa->pa_deleted == 0) {
  3361. pa->pa_deleted = 1;
  3362. spin_unlock(&pa->pa_lock);
  3363. list_del_rcu(&pa->pa_inode_list);
  3364. list_add(&pa->u.pa_tmp_list, &list);
  3365. continue;
  3366. }
  3367. /* someone is deleting pa right now */
  3368. spin_unlock(&pa->pa_lock);
  3369. spin_unlock(&ei->i_prealloc_lock);
  3370. /* we have to wait here because pa_deleted
  3371. * doesn't mean pa is already unlinked from
  3372. * the list. as we might be called from
  3373. * ->clear_inode() the inode will get freed
  3374. * and concurrent thread which is unlinking
  3375. * pa from inode's list may access already
  3376. * freed memory, bad-bad-bad */
  3377. /* XXX: if this happens too often, we can
  3378. * add a flag to force wait only in case
  3379. * of ->clear_inode(), but not in case of
  3380. * regular truncate */
  3381. schedule_timeout_uninterruptible(HZ);
  3382. goto repeat;
  3383. }
  3384. spin_unlock(&ei->i_prealloc_lock);
  3385. list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
  3386. BUG_ON(pa->pa_linear != 0);
  3387. ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, NULL);
  3388. err = ext4_mb_load_buddy(sb, group, &e4b);
  3389. if (err) {
  3390. ext4_error(sb, __func__, "Error in loading buddy "
  3391. "information for %lu\n", group);
  3392. continue;
  3393. }
  3394. bitmap_bh = ext4_read_block_bitmap(sb, group);
  3395. if (bitmap_bh == NULL) {
  3396. ext4_error(sb, __func__, "Error in reading block "
  3397. "bitmap for %lu\n", group);
  3398. ext4_mb_release_desc(&e4b);
  3399. continue;
  3400. }
  3401. ext4_lock_group(sb, group);
  3402. list_del(&pa->pa_group_list);
  3403. ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa, ac);
  3404. ext4_unlock_group(sb, group);
  3405. ext4_mb_release_desc(&e4b);
  3406. put_bh(bitmap_bh);
  3407. list_del(&pa->u.pa_tmp_list);
  3408. call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
  3409. }
  3410. if (ac)
  3411. kmem_cache_free(ext4_ac_cachep, ac);
  3412. }
  3413. /*
  3414. * finds all preallocated spaces and return blocks being freed to them
  3415. * if preallocated space becomes full (no block is used from the space)
  3416. * then the function frees space in buddy
  3417. * XXX: at the moment, truncate (which is the only way to free blocks)
  3418. * discards all preallocations
  3419. */
  3420. static void ext4_mb_return_to_preallocation(struct inode *inode,
  3421. struct ext4_buddy *e4b,
  3422. sector_t block, int count)
  3423. {
  3424. BUG_ON(!list_empty(&EXT4_I(inode)->i_prealloc_list));
  3425. }
  3426. #ifdef MB_DEBUG
  3427. static void ext4_mb_show_ac(struct ext4_allocation_context *ac)
  3428. {
  3429. struct super_block *sb = ac->ac_sb;
  3430. ext4_group_t i;
  3431. printk(KERN_ERR "EXT4-fs: Can't allocate:"
  3432. " Allocation context details:\n");
  3433. printk(KERN_ERR "EXT4-fs: status %d flags %d\n",
  3434. ac->ac_status, ac->ac_flags);
  3435. printk(KERN_ERR "EXT4-fs: orig %lu/%lu/%lu@%lu, goal %lu/%lu/%lu@%lu, "
  3436. "best %lu/%lu/%lu@%lu cr %d\n",
  3437. (unsigned long)ac->ac_o_ex.fe_group,
  3438. (unsigned long)ac->ac_o_ex.fe_start,
  3439. (unsigned long)ac->ac_o_ex.fe_len,
  3440. (unsigned long)ac->ac_o_ex.fe_logical,
  3441. (unsigned long)ac->ac_g_ex.fe_group,
  3442. (unsigned long)ac->ac_g_ex.fe_start,
  3443. (unsigned long)ac->ac_g_ex.fe_len,
  3444. (unsigned long)ac->ac_g_ex.fe_logical,
  3445. (unsigned long)ac->ac_b_ex.fe_group,
  3446. (unsigned long)ac->ac_b_ex.fe_start,
  3447. (unsigned long)ac->ac_b_ex.fe_len,
  3448. (unsigned long)ac->ac_b_ex.fe_logical,
  3449. (int)ac->ac_criteria);
  3450. printk(KERN_ERR "EXT4-fs: %lu scanned, %d found\n", ac->ac_ex_scanned,
  3451. ac->ac_found);
  3452. printk(KERN_ERR "EXT4-fs: groups: \n");
  3453. for (i = 0; i < EXT4_SB(sb)->s_groups_count; i++) {
  3454. struct ext4_group_info *grp = ext4_get_group_info(sb, i);
  3455. struct ext4_prealloc_space *pa;
  3456. ext4_grpblk_t start;
  3457. struct list_head *cur;
  3458. ext4_lock_group(sb, i);
  3459. list_for_each(cur, &grp->bb_prealloc_list) {
  3460. pa = list_entry(cur, struct ext4_prealloc_space,
  3461. pa_group_list);
  3462. spin_lock(&pa->pa_lock);
  3463. ext4_get_group_no_and_offset(sb, pa->pa_pstart,
  3464. NULL, &start);
  3465. spin_unlock(&pa->pa_lock);
  3466. printk(KERN_ERR "PA:%lu:%d:%u \n", i,
  3467. start, pa->pa_len);
  3468. }
  3469. ext4_unlock_group(sb, i);
  3470. if (grp->bb_free == 0)
  3471. continue;
  3472. printk(KERN_ERR "%lu: %d/%d \n",
  3473. i, grp->bb_free, grp->bb_fragments);
  3474. }
  3475. printk(KERN_ERR "\n");
  3476. }
  3477. #else
  3478. static inline void ext4_mb_show_ac(struct ext4_allocation_context *ac)
  3479. {
  3480. return;
  3481. }
  3482. #endif
  3483. /*
  3484. * We use locality group preallocation for small size file. The size of the
  3485. * file is determined by the current size or the resulting size after
  3486. * allocation which ever is larger
  3487. *
  3488. * One can tune this size via /proc/fs/ext4/<partition>/stream_req
  3489. */
  3490. static void ext4_mb_group_or_file(struct ext4_allocation_context *ac)
  3491. {
  3492. struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
  3493. int bsbits = ac->ac_sb->s_blocksize_bits;
  3494. loff_t size, isize;
  3495. if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
  3496. return;
  3497. size = ac->ac_o_ex.fe_logical + ac->ac_o_ex.fe_len;
  3498. isize = i_size_read(ac->ac_inode) >> bsbits;
  3499. size = max(size, isize);
  3500. /* don't use group allocation for large files */
  3501. if (size >= sbi->s_mb_stream_request)
  3502. return;
  3503. if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
  3504. return;
  3505. BUG_ON(ac->ac_lg != NULL);
  3506. /*
  3507. * locality group prealloc space are per cpu. The reason for having
  3508. * per cpu locality group is to reduce the contention between block
  3509. * request from multiple CPUs.
  3510. */
  3511. ac->ac_lg = per_cpu_ptr(sbi->s_locality_groups, raw_smp_processor_id());
  3512. /* we're going to use group allocation */
  3513. ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;
  3514. /* serialize all allocations in the group */
  3515. mutex_lock(&ac->ac_lg->lg_mutex);
  3516. }
  3517. static noinline_for_stack int
  3518. ext4_mb_initialize_context(struct ext4_allocation_context *ac,
  3519. struct ext4_allocation_request *ar)
  3520. {
  3521. struct super_block *sb = ar->inode->i_sb;
  3522. struct ext4_sb_info *sbi = EXT4_SB(sb);
  3523. struct ext4_super_block *es = sbi->s_es;
  3524. ext4_group_t group;
  3525. unsigned long len;
  3526. unsigned long goal;
  3527. ext4_grpblk_t block;
  3528. /* we can't allocate > group size */
  3529. len = ar->len;
  3530. /* just a dirty hack to filter too big requests */
  3531. if (len >= EXT4_BLOCKS_PER_GROUP(sb) - 10)
  3532. len = EXT4_BLOCKS_PER_GROUP(sb) - 10;
  3533. /* start searching from the goal */
  3534. goal = ar->goal;
  3535. if (goal < le32_to_cpu(es->s_first_data_block) ||
  3536. goal >= ext4_blocks_count(es))
  3537. goal = le32_to_cpu(es->s_first_data_block);
  3538. ext4_get_group_no_and_offset(sb, goal, &group, &block);
  3539. /* set up allocation goals */
  3540. ac->ac_b_ex.fe_logical = ar->logical;
  3541. ac->ac_b_ex.fe_group = 0;
  3542. ac->ac_b_ex.fe_start = 0;
  3543. ac->ac_b_ex.fe_len = 0;
  3544. ac->ac_status = AC_STATUS_CONTINUE;
  3545. ac->ac_groups_scanned = 0;
  3546. ac->ac_ex_scanned = 0;
  3547. ac->ac_found = 0;
  3548. ac->ac_sb = sb;
  3549. ac->ac_inode = ar->inode;
  3550. ac->ac_o_ex.fe_logical = ar->logical;
  3551. ac->ac_o_ex.fe_group = group;
  3552. ac->ac_o_ex.fe_start = block;
  3553. ac->ac_o_ex.fe_len = len;
  3554. ac->ac_g_ex.fe_logical = ar->logical;
  3555. ac->ac_g_ex.fe_group = group;
  3556. ac->ac_g_ex.fe_start = block;
  3557. ac->ac_g_ex.fe_len = len;
  3558. ac->ac_f_ex.fe_len = 0;
  3559. ac->ac_flags = ar->flags;
  3560. ac->ac_2order = 0;
  3561. ac->ac_criteria = 0;
  3562. ac->ac_pa = NULL;
  3563. ac->ac_bitmap_page = NULL;
  3564. ac->ac_buddy_page = NULL;
  3565. ac->ac_lg = NULL;
  3566. /* we have to define context: we'll we work with a file or
  3567. * locality group. this is a policy, actually */
  3568. ext4_mb_group_or_file(ac);
  3569. mb_debug("init ac: %u blocks @ %u, goal %u, flags %x, 2^%d, "
  3570. "left: %u/%u, right %u/%u to %swritable\n",
  3571. (unsigned) ar->len, (unsigned) ar->logical,
  3572. (unsigned) ar->goal, ac->ac_flags, ac->ac_2order,
  3573. (unsigned) ar->lleft, (unsigned) ar->pleft,
  3574. (unsigned) ar->lright, (unsigned) ar->pright,
  3575. atomic_read(&ar->inode->i_writecount) ? "" : "non-");
  3576. return 0;
  3577. }
  3578. static noinline_for_stack void
  3579. ext4_mb_discard_lg_preallocations(struct super_block *sb,
  3580. struct ext4_locality_group *lg,
  3581. int order, int total_entries)
  3582. {
  3583. ext4_group_t group = 0;
  3584. struct ext4_buddy e4b;
  3585. struct list_head discard_list;
  3586. struct ext4_prealloc_space *pa, *tmp;
  3587. struct ext4_allocation_context *ac;
  3588. mb_debug("discard locality group preallocation\n");
  3589. INIT_LIST_HEAD(&discard_list);
  3590. ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
  3591. spin_lock(&lg->lg_prealloc_lock);
  3592. list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order],
  3593. pa_inode_list) {
  3594. spin_lock(&pa->pa_lock);
  3595. if (atomic_read(&pa->pa_count)) {
  3596. /*
  3597. * This is the pa that we just used
  3598. * for block allocation. So don't
  3599. * free that
  3600. */
  3601. spin_unlock(&pa->pa_lock);
  3602. continue;
  3603. }
  3604. if (pa->pa_deleted) {
  3605. spin_unlock(&pa->pa_lock);
  3606. continue;
  3607. }
  3608. /* only lg prealloc space */
  3609. BUG_ON(!pa->pa_linear);
  3610. /* seems this one can be freed ... */
  3611. pa->pa_deleted = 1;
  3612. spin_unlock(&pa->pa_lock);
  3613. list_del_rcu(&pa->pa_inode_list);
  3614. list_add(&pa->u.pa_tmp_list, &discard_list);
  3615. total_entries--;
  3616. if (total_entries <= 5) {
  3617. /*
  3618. * we want to keep only 5 entries
  3619. * allowing it to grow to 8. This
  3620. * mak sure we don't call discard
  3621. * soon for this list.
  3622. */
  3623. break;
  3624. }
  3625. }
  3626. spin_unlock(&lg->lg_prealloc_lock);
  3627. list_for_each_entry_safe(pa, tmp, &discard_list, u.pa_tmp_list) {
  3628. ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, NULL);
  3629. if (ext4_mb_load_buddy(sb, group, &e4b)) {
  3630. ext4_error(sb, __func__, "Error in loading buddy "
  3631. "information for %lu\n", group);
  3632. continue;
  3633. }
  3634. ext4_lock_group(sb, group);
  3635. list_del(&pa->pa_group_list);
  3636. ext4_mb_release_group_pa(&e4b, pa, ac);
  3637. ext4_unlock_group(sb, group);
  3638. ext4_mb_release_desc(&e4b);
  3639. list_del(&pa->u.pa_tmp_list);
  3640. call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
  3641. }
  3642. if (ac)
  3643. kmem_cache_free(ext4_ac_cachep, ac);
  3644. }
  3645. /*
  3646. * We have incremented pa_count. So it cannot be freed at this
  3647. * point. Also we hold lg_mutex. So no parallel allocation is
  3648. * possible from this lg. That means pa_free cannot be updated.
  3649. *
  3650. * A parallel ext4_mb_discard_group_preallocations is possible.
  3651. * which can cause the lg_prealloc_list to be updated.
  3652. */
  3653. static void ext4_mb_add_n_trim(struct ext4_allocation_context *ac)
  3654. {
  3655. int order, added = 0, lg_prealloc_count = 1;
  3656. struct super_block *sb = ac->ac_sb;
  3657. struct ext4_locality_group *lg = ac->ac_lg;
  3658. struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa;
  3659. order = fls(pa->pa_free) - 1;
  3660. if (order > PREALLOC_TB_SIZE - 1)
  3661. /* The max size of hash table is PREALLOC_TB_SIZE */
  3662. order = PREALLOC_TB_SIZE - 1;
  3663. /* Add the prealloc space to lg */
  3664. rcu_read_lock();
  3665. list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order],
  3666. pa_inode_list) {
  3667. spin_lock(&tmp_pa->pa_lock);
  3668. if (tmp_pa->pa_deleted) {
  3669. spin_unlock(&pa->pa_lock);
  3670. continue;
  3671. }
  3672. if (!added && pa->pa_free < tmp_pa->pa_free) {
  3673. /* Add to the tail of the previous entry */
  3674. list_add_tail_rcu(&pa->pa_inode_list,
  3675. &tmp_pa->pa_inode_list);
  3676. added = 1;
  3677. /*
  3678. * we want to count the total
  3679. * number of entries in the list
  3680. */
  3681. }
  3682. spin_unlock(&tmp_pa->pa_lock);
  3683. lg_prealloc_count++;
  3684. }
  3685. if (!added)
  3686. list_add_tail_rcu(&pa->pa_inode_list,
  3687. &lg->lg_prealloc_list[order]);
  3688. rcu_read_unlock();
  3689. /* Now trim the list to be not more than 8 elements */
  3690. if (lg_prealloc_count > 8) {
  3691. ext4_mb_discard_lg_preallocations(sb, lg,
  3692. order, lg_prealloc_count);
  3693. return;
  3694. }
  3695. return ;
  3696. }
  3697. /*
  3698. * release all resource we used in allocation
  3699. */
  3700. static int ext4_mb_release_context(struct ext4_allocation_context *ac)
  3701. {
  3702. struct ext4_prealloc_space *pa = ac->ac_pa;
  3703. if (pa) {
  3704. if (pa->pa_linear) {
  3705. /* see comment in ext4_mb_use_group_pa() */
  3706. spin_lock(&pa->pa_lock);
  3707. pa->pa_pstart += ac->ac_b_ex.fe_len;
  3708. pa->pa_lstart += ac->ac_b_ex.fe_len;
  3709. pa->pa_free -= ac->ac_b_ex.fe_len;
  3710. pa->pa_len -= ac->ac_b_ex.fe_len;
  3711. spin_unlock(&pa->pa_lock);
  3712. /*
  3713. * We want to add the pa to the right bucket.
  3714. * Remove it from the list and while adding
  3715. * make sure the list to which we are adding
  3716. * doesn't grow big.
  3717. */
  3718. if (likely(pa->pa_free)) {
  3719. spin_lock(pa->pa_obj_lock);
  3720. list_del_rcu(&pa->pa_inode_list);
  3721. spin_unlock(pa->pa_obj_lock);
  3722. ext4_mb_add_n_trim(ac);
  3723. }
  3724. }
  3725. ext4_mb_put_pa(ac, ac->ac_sb, pa);
  3726. }
  3727. if (ac->ac_bitmap_page)
  3728. page_cache_release(ac->ac_bitmap_page);
  3729. if (ac->ac_buddy_page)
  3730. page_cache_release(ac->ac_buddy_page);
  3731. if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
  3732. mutex_unlock(&ac->ac_lg->lg_mutex);
  3733. ext4_mb_collect_stats(ac);
  3734. return 0;
  3735. }
  3736. static int ext4_mb_discard_preallocations(struct super_block *sb, int needed)
  3737. {
  3738. ext4_group_t i;
  3739. int ret;
  3740. int freed = 0;
  3741. for (i = 0; i < EXT4_SB(sb)->s_groups_count && needed > 0; i++) {
  3742. ret = ext4_mb_discard_group_preallocations(sb, i, needed);
  3743. freed += ret;
  3744. needed -= ret;
  3745. }
  3746. return freed;
  3747. }
  3748. /*
  3749. * Main entry point into mballoc to allocate blocks
  3750. * it tries to use preallocation first, then falls back
  3751. * to usual allocation
  3752. */
  3753. ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
  3754. struct ext4_allocation_request *ar, int *errp)
  3755. {
  3756. int freed;
  3757. struct ext4_allocation_context *ac = NULL;
  3758. struct ext4_sb_info *sbi;
  3759. struct super_block *sb;
  3760. ext4_fsblk_t block = 0;
  3761. unsigned long inquota;
  3762. unsigned long reserv_blks = 0;
  3763. sb = ar->inode->i_sb;
  3764. sbi = EXT4_SB(sb);
  3765. if (!EXT4_I(ar->inode)->i_delalloc_reserved_flag) {
  3766. /*
  3767. * With delalloc we already reserved the blocks
  3768. */
  3769. while (ar->len && ext4_claim_free_blocks(sbi, ar->len)) {
  3770. /* let others to free the space */
  3771. yield();
  3772. ar->len = ar->len >> 1;
  3773. }
  3774. if (!ar->len) {
  3775. *errp = -ENOSPC;
  3776. return 0;
  3777. }
  3778. reserv_blks = ar->len;
  3779. }
  3780. while (ar->len && DQUOT_ALLOC_BLOCK(ar->inode, ar->len)) {
  3781. ar->flags |= EXT4_MB_HINT_NOPREALLOC;
  3782. ar->len--;
  3783. }
  3784. if (ar->len == 0) {
  3785. *errp = -EDQUOT;
  3786. return 0;
  3787. }
  3788. inquota = ar->len;
  3789. if (EXT4_I(ar->inode)->i_delalloc_reserved_flag)
  3790. ar->flags |= EXT4_MB_DELALLOC_RESERVED;
  3791. ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
  3792. if (!ac) {
  3793. ar->len = 0;
  3794. *errp = -ENOMEM;
  3795. goto out1;
  3796. }
  3797. ext4_mb_poll_new_transaction(sb, handle);
  3798. *errp = ext4_mb_initialize_context(ac, ar);
  3799. if (*errp) {
  3800. ar->len = 0;
  3801. goto out2;
  3802. }
  3803. ac->ac_op = EXT4_MB_HISTORY_PREALLOC;
  3804. if (!ext4_mb_use_preallocated(ac)) {
  3805. ac->ac_op = EXT4_MB_HISTORY_ALLOC;
  3806. ext4_mb_normalize_request(ac, ar);
  3807. repeat:
  3808. /* allocate space in core */
  3809. ext4_mb_regular_allocator(ac);
  3810. /* as we've just preallocated more space than
  3811. * user requested orinally, we store allocated
  3812. * space in a special descriptor */
  3813. if (ac->ac_status == AC_STATUS_FOUND &&
  3814. ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)
  3815. ext4_mb_new_preallocation(ac);
  3816. }
  3817. if (likely(ac->ac_status == AC_STATUS_FOUND)) {
  3818. *errp = ext4_mb_mark_diskspace_used(ac, handle, reserv_blks);
  3819. if (*errp == -EAGAIN) {
  3820. ac->ac_b_ex.fe_group = 0;
  3821. ac->ac_b_ex.fe_start = 0;
  3822. ac->ac_b_ex.fe_len = 0;
  3823. ac->ac_status = AC_STATUS_CONTINUE;
  3824. goto repeat;
  3825. } else if (*errp) {
  3826. ac->ac_b_ex.fe_len = 0;
  3827. ar->len = 0;
  3828. ext4_mb_show_ac(ac);
  3829. } else {
  3830. block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
  3831. ar->len = ac->ac_b_ex.fe_len;
  3832. }
  3833. } else {
  3834. freed = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len);
  3835. if (freed)
  3836. goto repeat;
  3837. *errp = -ENOSPC;
  3838. ac->ac_b_ex.fe_len = 0;
  3839. ar->len = 0;
  3840. ext4_mb_show_ac(ac);
  3841. }
  3842. ext4_mb_release_context(ac);
  3843. out2:
  3844. kmem_cache_free(ext4_ac_cachep, ac);
  3845. out1:
  3846. if (ar->len < inquota)
  3847. DQUOT_FREE_BLOCK(ar->inode, inquota - ar->len);
  3848. return block;
  3849. }
  3850. static void ext4_mb_poll_new_transaction(struct super_block *sb,
  3851. handle_t *handle)
  3852. {
  3853. struct ext4_sb_info *sbi = EXT4_SB(sb);
  3854. if (sbi->s_last_transaction == handle->h_transaction->t_tid)
  3855. return;
  3856. /* new transaction! time to close last one and free blocks for
  3857. * committed transaction. we know that only transaction can be
  3858. * active, so previos transaction can be being logged and we
  3859. * know that transaction before previous is known to be already
  3860. * logged. this means that now we may free blocks freed in all
  3861. * transactions before previous one. hope I'm clear enough ... */
  3862. spin_lock(&sbi->s_md_lock);
  3863. if (sbi->s_last_transaction != handle->h_transaction->t_tid) {
  3864. mb_debug("new transaction %lu, old %lu\n",
  3865. (unsigned long) handle->h_transaction->t_tid,
  3866. (unsigned long) sbi->s_last_transaction);
  3867. list_splice_init(&sbi->s_closed_transaction,
  3868. &sbi->s_committed_transaction);
  3869. list_splice_init(&sbi->s_active_transaction,
  3870. &sbi->s_closed_transaction);
  3871. sbi->s_last_transaction = handle->h_transaction->t_tid;
  3872. }
  3873. spin_unlock(&sbi->s_md_lock);
  3874. ext4_mb_free_committed_blocks(sb);
  3875. }
  3876. static noinline_for_stack int
  3877. ext4_mb_free_metadata(handle_t *handle, struct ext4_buddy *e4b,
  3878. ext4_group_t group, ext4_grpblk_t block, int count)
  3879. {
  3880. struct ext4_group_info *db = e4b->bd_info;
  3881. struct super_block *sb = e4b->bd_sb;
  3882. struct ext4_sb_info *sbi = EXT4_SB(sb);
  3883. struct ext4_free_metadata *md;
  3884. int i;
  3885. BUG_ON(e4b->bd_bitmap_page == NULL);
  3886. BUG_ON(e4b->bd_buddy_page == NULL);
  3887. ext4_lock_group(sb, group);
  3888. for (i = 0; i < count; i++) {
  3889. md = db->bb_md_cur;
  3890. if (md && db->bb_tid != handle->h_transaction->t_tid) {
  3891. db->bb_md_cur = NULL;
  3892. md = NULL;
  3893. }
  3894. if (md == NULL) {
  3895. ext4_unlock_group(sb, group);
  3896. md = kmalloc(sizeof(*md), GFP_NOFS);
  3897. if (md == NULL)
  3898. return -ENOMEM;
  3899. md->num = 0;
  3900. md->group = group;
  3901. ext4_lock_group(sb, group);
  3902. if (db->bb_md_cur == NULL) {
  3903. spin_lock(&sbi->s_md_lock);
  3904. list_add(&md->list, &sbi->s_active_transaction);
  3905. spin_unlock(&sbi->s_md_lock);
  3906. /* protect buddy cache from being freed,
  3907. * otherwise we'll refresh it from
  3908. * on-disk bitmap and lose not-yet-available
  3909. * blocks */
  3910. page_cache_get(e4b->bd_buddy_page);
  3911. page_cache_get(e4b->bd_bitmap_page);
  3912. db->bb_md_cur = md;
  3913. db->bb_tid = handle->h_transaction->t_tid;
  3914. mb_debug("new md 0x%p for group %lu\n",
  3915. md, md->group);
  3916. } else {
  3917. kfree(md);
  3918. md = db->bb_md_cur;
  3919. }
  3920. }
  3921. BUG_ON(md->num >= EXT4_BB_MAX_BLOCKS);
  3922. md->blocks[md->num] = block + i;
  3923. md->num++;
  3924. if (md->num == EXT4_BB_MAX_BLOCKS) {
  3925. /* no more space, put full container on a sb's list */
  3926. db->bb_md_cur = NULL;
  3927. }
  3928. }
  3929. ext4_unlock_group(sb, group);
  3930. return 0;
  3931. }
  3932. /*
  3933. * Main entry point into mballoc to free blocks
  3934. */
  3935. void ext4_mb_free_blocks(handle_t *handle, struct inode *inode,
  3936. unsigned long block, unsigned long count,
  3937. int metadata, unsigned long *freed)
  3938. {
  3939. struct buffer_head *bitmap_bh = NULL;
  3940. struct super_block *sb = inode->i_sb;
  3941. struct ext4_allocation_context *ac = NULL;
  3942. struct ext4_group_desc *gdp;
  3943. struct ext4_super_block *es;
  3944. unsigned long overflow;
  3945. ext4_grpblk_t bit;
  3946. struct buffer_head *gd_bh;
  3947. ext4_group_t block_group;
  3948. struct ext4_sb_info *sbi;
  3949. struct ext4_buddy e4b;
  3950. int err = 0;
  3951. int ret;
  3952. *freed = 0;
  3953. ext4_mb_poll_new_transaction(sb, handle);
  3954. sbi = EXT4_SB(sb);
  3955. es = EXT4_SB(sb)->s_es;
  3956. if (block < le32_to_cpu(es->s_first_data_block) ||
  3957. block + count < block ||
  3958. block + count > ext4_blocks_count(es)) {
  3959. ext4_error(sb, __func__,
  3960. "Freeing blocks not in datazone - "
  3961. "block = %lu, count = %lu", block, count);
  3962. goto error_return;
  3963. }
  3964. ext4_debug("freeing block %lu\n", block);
  3965. ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
  3966. if (ac) {
  3967. ac->ac_op = EXT4_MB_HISTORY_FREE;
  3968. ac->ac_inode = inode;
  3969. ac->ac_sb = sb;
  3970. }
  3971. do_more:
  3972. overflow = 0;
  3973. ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
  3974. /*
  3975. * Check to see if we are freeing blocks across a group
  3976. * boundary.
  3977. */
  3978. if (bit + count > EXT4_BLOCKS_PER_GROUP(sb)) {
  3979. overflow = bit + count - EXT4_BLOCKS_PER_GROUP(sb);
  3980. count -= overflow;
  3981. }
  3982. bitmap_bh = ext4_read_block_bitmap(sb, block_group);
  3983. if (!bitmap_bh) {
  3984. err = -EIO;
  3985. goto error_return;
  3986. }
  3987. gdp = ext4_get_group_desc(sb, block_group, &gd_bh);
  3988. if (!gdp) {
  3989. err = -EIO;
  3990. goto error_return;
  3991. }
  3992. if (in_range(ext4_block_bitmap(sb, gdp), block, count) ||
  3993. in_range(ext4_inode_bitmap(sb, gdp), block, count) ||
  3994. in_range(block, ext4_inode_table(sb, gdp),
  3995. EXT4_SB(sb)->s_itb_per_group) ||
  3996. in_range(block + count - 1, ext4_inode_table(sb, gdp),
  3997. EXT4_SB(sb)->s_itb_per_group)) {
  3998. ext4_error(sb, __func__,
  3999. "Freeing blocks in system zone - "
  4000. "Block = %lu, count = %lu", block, count);
  4001. /* err = 0. ext4_std_error should be a no op */
  4002. goto error_return;
  4003. }
  4004. BUFFER_TRACE(bitmap_bh, "getting write access");
  4005. err = ext4_journal_get_write_access(handle, bitmap_bh);
  4006. if (err)
  4007. goto error_return;
  4008. /*
  4009. * We are about to modify some metadata. Call the journal APIs
  4010. * to unshare ->b_data if a currently-committing transaction is
  4011. * using it
  4012. */
  4013. BUFFER_TRACE(gd_bh, "get_write_access");
  4014. err = ext4_journal_get_write_access(handle, gd_bh);
  4015. if (err)
  4016. goto error_return;
  4017. err = ext4_mb_load_buddy(sb, block_group, &e4b);
  4018. if (err)
  4019. goto error_return;
  4020. #ifdef AGGRESSIVE_CHECK
  4021. {
  4022. int i;
  4023. for (i = 0; i < count; i++)
  4024. BUG_ON(!mb_test_bit(bit + i, bitmap_bh->b_data));
  4025. }
  4026. #endif
  4027. mb_clear_bits(sb_bgl_lock(sbi, block_group), bitmap_bh->b_data,
  4028. bit, count);
  4029. /* We dirtied the bitmap block */
  4030. BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
  4031. err = ext4_journal_dirty_metadata(handle, bitmap_bh);
  4032. if (ac) {
  4033. ac->ac_b_ex.fe_group = block_group;
  4034. ac->ac_b_ex.fe_start = bit;
  4035. ac->ac_b_ex.fe_len = count;
  4036. ext4_mb_store_history(ac);
  4037. }
  4038. if (metadata) {
  4039. /* blocks being freed are metadata. these blocks shouldn't
  4040. * be used until this transaction is committed */
  4041. ext4_mb_free_metadata(handle, &e4b, block_group, bit, count);
  4042. } else {
  4043. ext4_lock_group(sb, block_group);
  4044. mb_free_blocks(inode, &e4b, bit, count);
  4045. ext4_mb_return_to_preallocation(inode, &e4b, block, count);
  4046. ext4_unlock_group(sb, block_group);
  4047. }
  4048. spin_lock(sb_bgl_lock(sbi, block_group));
  4049. le16_add_cpu(&gdp->bg_free_blocks_count, count);
  4050. gdp->bg_checksum = ext4_group_desc_csum(sbi, block_group, gdp);
  4051. spin_unlock(sb_bgl_lock(sbi, block_group));
  4052. percpu_counter_add(&sbi->s_freeblocks_counter, count);
  4053. if (sbi->s_log_groups_per_flex) {
  4054. ext4_group_t flex_group = ext4_flex_group(sbi, block_group);
  4055. spin_lock(sb_bgl_lock(sbi, flex_group));
  4056. sbi->s_flex_groups[flex_group].free_blocks += count;
  4057. spin_unlock(sb_bgl_lock(sbi, flex_group));
  4058. }
  4059. ext4_mb_release_desc(&e4b);
  4060. *freed += count;
  4061. /* And the group descriptor block */
  4062. BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
  4063. ret = ext4_journal_dirty_metadata(handle, gd_bh);
  4064. if (!err)
  4065. err = ret;
  4066. if (overflow && !err) {
  4067. block += count;
  4068. count = overflow;
  4069. put_bh(bitmap_bh);
  4070. goto do_more;
  4071. }
  4072. sb->s_dirt = 1;
  4073. error_return:
  4074. brelse(bitmap_bh);
  4075. ext4_std_error(sb, err);
  4076. if (ac)
  4077. kmem_cache_free(ext4_ac_cachep, ac);
  4078. return;
  4079. }