mballoc.c 143 KB

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