extents.c 113 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326
  1. /*
  2. * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
  3. * Written by Alex Tomas <alex@clusterfs.com>
  4. *
  5. * Architecture independence:
  6. * Copyright (c) 2005, Bull S.A.
  7. * Written by Pierre Peiffer <pierre.peiffer@bull.net>
  8. *
  9. * This program is free software; you can redistribute it and/or modify
  10. * it under the terms of the GNU General Public License version 2 as
  11. * published by the Free Software Foundation.
  12. *
  13. * This program is distributed in the hope that it will be useful,
  14. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16. * GNU General Public License for more details.
  17. *
  18. * You should have received a copy of the GNU General Public Licens
  19. * along with this program; if not, write to the Free Software
  20. * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-
  21. */
  22. /*
  23. * Extents support for EXT4
  24. *
  25. * TODO:
  26. * - ext4*_error() should be used in some situations
  27. * - analyze all BUG()/BUG_ON(), use -EIO where appropriate
  28. * - smart tree reduction
  29. */
  30. #include <linux/module.h>
  31. #include <linux/fs.h>
  32. #include <linux/time.h>
  33. #include <linux/jbd2.h>
  34. #include <linux/highuid.h>
  35. #include <linux/pagemap.h>
  36. #include <linux/quotaops.h>
  37. #include <linux/string.h>
  38. #include <linux/slab.h>
  39. #include <linux/falloc.h>
  40. #include <asm/uaccess.h>
  41. #include <linux/fiemap.h>
  42. #include "ext4_jbd2.h"
  43. #include "ext4_extents.h"
  44. #include <trace/events/ext4.h>
  45. static int ext4_split_extent(handle_t *handle,
  46. struct inode *inode,
  47. struct ext4_ext_path *path,
  48. struct ext4_map_blocks *map,
  49. int split_flag,
  50. int flags);
  51. static int ext4_ext_truncate_extend_restart(handle_t *handle,
  52. struct inode *inode,
  53. int needed)
  54. {
  55. int err;
  56. if (!ext4_handle_valid(handle))
  57. return 0;
  58. if (handle->h_buffer_credits > needed)
  59. return 0;
  60. err = ext4_journal_extend(handle, needed);
  61. if (err <= 0)
  62. return err;
  63. err = ext4_truncate_restart_trans(handle, inode, needed);
  64. if (err == 0)
  65. err = -EAGAIN;
  66. return err;
  67. }
  68. /*
  69. * could return:
  70. * - EROFS
  71. * - ENOMEM
  72. */
  73. static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
  74. struct ext4_ext_path *path)
  75. {
  76. if (path->p_bh) {
  77. /* path points to block */
  78. return ext4_journal_get_write_access(handle, path->p_bh);
  79. }
  80. /* path points to leaf/index in inode body */
  81. /* we use in-core data, no need to protect them */
  82. return 0;
  83. }
  84. /*
  85. * could return:
  86. * - EROFS
  87. * - ENOMEM
  88. * - EIO
  89. */
  90. static int ext4_ext_dirty(handle_t *handle, struct inode *inode,
  91. struct ext4_ext_path *path)
  92. {
  93. int err;
  94. if (path->p_bh) {
  95. /* path points to block */
  96. err = ext4_handle_dirty_metadata(handle, inode, path->p_bh);
  97. } else {
  98. /* path points to leaf/index in inode body */
  99. err = ext4_mark_inode_dirty(handle, inode);
  100. }
  101. return err;
  102. }
  103. static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
  104. struct ext4_ext_path *path,
  105. ext4_lblk_t block)
  106. {
  107. int depth;
  108. if (path) {
  109. struct ext4_extent *ex;
  110. depth = path->p_depth;
  111. /*
  112. * Try to predict block placement assuming that we are
  113. * filling in a file which will eventually be
  114. * non-sparse --- i.e., in the case of libbfd writing
  115. * an ELF object sections out-of-order but in a way
  116. * the eventually results in a contiguous object or
  117. * executable file, or some database extending a table
  118. * space file. However, this is actually somewhat
  119. * non-ideal if we are writing a sparse file such as
  120. * qemu or KVM writing a raw image file that is going
  121. * to stay fairly sparse, since it will end up
  122. * fragmenting the file system's free space. Maybe we
  123. * should have some hueristics or some way to allow
  124. * userspace to pass a hint to file system,
  125. * especially if the latter case turns out to be
  126. * common.
  127. */
  128. ex = path[depth].p_ext;
  129. if (ex) {
  130. ext4_fsblk_t ext_pblk = ext4_ext_pblock(ex);
  131. ext4_lblk_t ext_block = le32_to_cpu(ex->ee_block);
  132. if (block > ext_block)
  133. return ext_pblk + (block - ext_block);
  134. else
  135. return ext_pblk - (ext_block - block);
  136. }
  137. /* it looks like index is empty;
  138. * try to find starting block from index itself */
  139. if (path[depth].p_bh)
  140. return path[depth].p_bh->b_blocknr;
  141. }
  142. /* OK. use inode's group */
  143. return ext4_inode_to_goal_block(inode);
  144. }
  145. /*
  146. * Allocation for a meta data block
  147. */
  148. static ext4_fsblk_t
  149. ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
  150. struct ext4_ext_path *path,
  151. struct ext4_extent *ex, int *err, unsigned int flags)
  152. {
  153. ext4_fsblk_t goal, newblock;
  154. goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
  155. newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
  156. NULL, err);
  157. return newblock;
  158. }
  159. static inline int ext4_ext_space_block(struct inode *inode, int check)
  160. {
  161. int size;
  162. size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
  163. / sizeof(struct ext4_extent);
  164. if (!check) {
  165. #ifdef AGGRESSIVE_TEST
  166. if (size > 6)
  167. size = 6;
  168. #endif
  169. }
  170. return size;
  171. }
  172. static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
  173. {
  174. int size;
  175. size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
  176. / sizeof(struct ext4_extent_idx);
  177. if (!check) {
  178. #ifdef AGGRESSIVE_TEST
  179. if (size > 5)
  180. size = 5;
  181. #endif
  182. }
  183. return size;
  184. }
  185. static inline int ext4_ext_space_root(struct inode *inode, int check)
  186. {
  187. int size;
  188. size = sizeof(EXT4_I(inode)->i_data);
  189. size -= sizeof(struct ext4_extent_header);
  190. size /= sizeof(struct ext4_extent);
  191. if (!check) {
  192. #ifdef AGGRESSIVE_TEST
  193. if (size > 3)
  194. size = 3;
  195. #endif
  196. }
  197. return size;
  198. }
  199. static inline int ext4_ext_space_root_idx(struct inode *inode, int check)
  200. {
  201. int size;
  202. size = sizeof(EXT4_I(inode)->i_data);
  203. size -= sizeof(struct ext4_extent_header);
  204. size /= sizeof(struct ext4_extent_idx);
  205. if (!check) {
  206. #ifdef AGGRESSIVE_TEST
  207. if (size > 4)
  208. size = 4;
  209. #endif
  210. }
  211. return size;
  212. }
  213. /*
  214. * Calculate the number of metadata blocks needed
  215. * to allocate @blocks
  216. * Worse case is one block per extent
  217. */
  218. int ext4_ext_calc_metadata_amount(struct inode *inode, ext4_lblk_t lblock)
  219. {
  220. struct ext4_inode_info *ei = EXT4_I(inode);
  221. int idxs, num = 0;
  222. idxs = ((inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
  223. / sizeof(struct ext4_extent_idx));
  224. /*
  225. * If the new delayed allocation block is contiguous with the
  226. * previous da block, it can share index blocks with the
  227. * previous block, so we only need to allocate a new index
  228. * block every idxs leaf blocks. At ldxs**2 blocks, we need
  229. * an additional index block, and at ldxs**3 blocks, yet
  230. * another index blocks.
  231. */
  232. if (ei->i_da_metadata_calc_len &&
  233. ei->i_da_metadata_calc_last_lblock+1 == lblock) {
  234. if ((ei->i_da_metadata_calc_len % idxs) == 0)
  235. num++;
  236. if ((ei->i_da_metadata_calc_len % (idxs*idxs)) == 0)
  237. num++;
  238. if ((ei->i_da_metadata_calc_len % (idxs*idxs*idxs)) == 0) {
  239. num++;
  240. ei->i_da_metadata_calc_len = 0;
  241. } else
  242. ei->i_da_metadata_calc_len++;
  243. ei->i_da_metadata_calc_last_lblock++;
  244. return num;
  245. }
  246. /*
  247. * In the worst case we need a new set of index blocks at
  248. * every level of the inode's extent tree.
  249. */
  250. ei->i_da_metadata_calc_len = 1;
  251. ei->i_da_metadata_calc_last_lblock = lblock;
  252. return ext_depth(inode) + 1;
  253. }
  254. static int
  255. ext4_ext_max_entries(struct inode *inode, int depth)
  256. {
  257. int max;
  258. if (depth == ext_depth(inode)) {
  259. if (depth == 0)
  260. max = ext4_ext_space_root(inode, 1);
  261. else
  262. max = ext4_ext_space_root_idx(inode, 1);
  263. } else {
  264. if (depth == 0)
  265. max = ext4_ext_space_block(inode, 1);
  266. else
  267. max = ext4_ext_space_block_idx(inode, 1);
  268. }
  269. return max;
  270. }
  271. static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
  272. {
  273. ext4_fsblk_t block = ext4_ext_pblock(ext);
  274. int len = ext4_ext_get_actual_len(ext);
  275. return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len);
  276. }
  277. static int ext4_valid_extent_idx(struct inode *inode,
  278. struct ext4_extent_idx *ext_idx)
  279. {
  280. ext4_fsblk_t block = ext4_idx_pblock(ext_idx);
  281. return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, 1);
  282. }
  283. static int ext4_valid_extent_entries(struct inode *inode,
  284. struct ext4_extent_header *eh,
  285. int depth)
  286. {
  287. struct ext4_extent *ext;
  288. struct ext4_extent_idx *ext_idx;
  289. unsigned short entries;
  290. if (eh->eh_entries == 0)
  291. return 1;
  292. entries = le16_to_cpu(eh->eh_entries);
  293. if (depth == 0) {
  294. /* leaf entries */
  295. ext = EXT_FIRST_EXTENT(eh);
  296. while (entries) {
  297. if (!ext4_valid_extent(inode, ext))
  298. return 0;
  299. ext++;
  300. entries--;
  301. }
  302. } else {
  303. ext_idx = EXT_FIRST_INDEX(eh);
  304. while (entries) {
  305. if (!ext4_valid_extent_idx(inode, ext_idx))
  306. return 0;
  307. ext_idx++;
  308. entries--;
  309. }
  310. }
  311. return 1;
  312. }
  313. static int __ext4_ext_check(const char *function, unsigned int line,
  314. struct inode *inode, struct ext4_extent_header *eh,
  315. int depth)
  316. {
  317. const char *error_msg;
  318. int max = 0;
  319. if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
  320. error_msg = "invalid magic";
  321. goto corrupted;
  322. }
  323. if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
  324. error_msg = "unexpected eh_depth";
  325. goto corrupted;
  326. }
  327. if (unlikely(eh->eh_max == 0)) {
  328. error_msg = "invalid eh_max";
  329. goto corrupted;
  330. }
  331. max = ext4_ext_max_entries(inode, depth);
  332. if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
  333. error_msg = "too large eh_max";
  334. goto corrupted;
  335. }
  336. if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
  337. error_msg = "invalid eh_entries";
  338. goto corrupted;
  339. }
  340. if (!ext4_valid_extent_entries(inode, eh, depth)) {
  341. error_msg = "invalid extent entries";
  342. goto corrupted;
  343. }
  344. return 0;
  345. corrupted:
  346. ext4_error_inode(inode, function, line, 0,
  347. "bad header/extent: %s - magic %x, "
  348. "entries %u, max %u(%u), depth %u(%u)",
  349. error_msg, le16_to_cpu(eh->eh_magic),
  350. le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
  351. max, le16_to_cpu(eh->eh_depth), depth);
  352. return -EIO;
  353. }
  354. #define ext4_ext_check(inode, eh, depth) \
  355. __ext4_ext_check(__func__, __LINE__, inode, eh, depth)
  356. int ext4_ext_check_inode(struct inode *inode)
  357. {
  358. return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode));
  359. }
  360. #ifdef EXT_DEBUG
  361. static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
  362. {
  363. int k, l = path->p_depth;
  364. ext_debug("path:");
  365. for (k = 0; k <= l; k++, path++) {
  366. if (path->p_idx) {
  367. ext_debug(" %d->%llu", le32_to_cpu(path->p_idx->ei_block),
  368. ext4_idx_pblock(path->p_idx));
  369. } else if (path->p_ext) {
  370. ext_debug(" %d:[%d]%d:%llu ",
  371. le32_to_cpu(path->p_ext->ee_block),
  372. ext4_ext_is_uninitialized(path->p_ext),
  373. ext4_ext_get_actual_len(path->p_ext),
  374. ext4_ext_pblock(path->p_ext));
  375. } else
  376. ext_debug(" []");
  377. }
  378. ext_debug("\n");
  379. }
  380. static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
  381. {
  382. int depth = ext_depth(inode);
  383. struct ext4_extent_header *eh;
  384. struct ext4_extent *ex;
  385. int i;
  386. if (!path)
  387. return;
  388. eh = path[depth].p_hdr;
  389. ex = EXT_FIRST_EXTENT(eh);
  390. ext_debug("Displaying leaf extents for inode %lu\n", inode->i_ino);
  391. for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
  392. ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
  393. ext4_ext_is_uninitialized(ex),
  394. ext4_ext_get_actual_len(ex), ext4_ext_pblock(ex));
  395. }
  396. ext_debug("\n");
  397. }
  398. static void ext4_ext_show_move(struct inode *inode, struct ext4_ext_path *path,
  399. ext4_fsblk_t newblock, int level)
  400. {
  401. int depth = ext_depth(inode);
  402. struct ext4_extent *ex;
  403. if (depth != level) {
  404. struct ext4_extent_idx *idx;
  405. idx = path[level].p_idx;
  406. while (idx <= EXT_MAX_INDEX(path[level].p_hdr)) {
  407. ext_debug("%d: move %d:%llu in new index %llu\n", level,
  408. le32_to_cpu(idx->ei_block),
  409. ext4_idx_pblock(idx),
  410. newblock);
  411. idx++;
  412. }
  413. return;
  414. }
  415. ex = path[depth].p_ext;
  416. while (ex <= EXT_MAX_EXTENT(path[depth].p_hdr)) {
  417. ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
  418. le32_to_cpu(ex->ee_block),
  419. ext4_ext_pblock(ex),
  420. ext4_ext_is_uninitialized(ex),
  421. ext4_ext_get_actual_len(ex),
  422. newblock);
  423. ex++;
  424. }
  425. }
  426. #else
  427. #define ext4_ext_show_path(inode, path)
  428. #define ext4_ext_show_leaf(inode, path)
  429. #define ext4_ext_show_move(inode, path, newblock, level)
  430. #endif
  431. void ext4_ext_drop_refs(struct ext4_ext_path *path)
  432. {
  433. int depth = path->p_depth;
  434. int i;
  435. for (i = 0; i <= depth; i++, path++)
  436. if (path->p_bh) {
  437. brelse(path->p_bh);
  438. path->p_bh = NULL;
  439. }
  440. }
  441. /*
  442. * ext4_ext_binsearch_idx:
  443. * binary search for the closest index of the given block
  444. * the header must be checked before calling this
  445. */
  446. static void
  447. ext4_ext_binsearch_idx(struct inode *inode,
  448. struct ext4_ext_path *path, ext4_lblk_t block)
  449. {
  450. struct ext4_extent_header *eh = path->p_hdr;
  451. struct ext4_extent_idx *r, *l, *m;
  452. ext_debug("binsearch for %u(idx): ", block);
  453. l = EXT_FIRST_INDEX(eh) + 1;
  454. r = EXT_LAST_INDEX(eh);
  455. while (l <= r) {
  456. m = l + (r - l) / 2;
  457. if (block < le32_to_cpu(m->ei_block))
  458. r = m - 1;
  459. else
  460. l = m + 1;
  461. ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
  462. m, le32_to_cpu(m->ei_block),
  463. r, le32_to_cpu(r->ei_block));
  464. }
  465. path->p_idx = l - 1;
  466. ext_debug(" -> %d->%lld ", le32_to_cpu(path->p_idx->ei_block),
  467. ext4_idx_pblock(path->p_idx));
  468. #ifdef CHECK_BINSEARCH
  469. {
  470. struct ext4_extent_idx *chix, *ix;
  471. int k;
  472. chix = ix = EXT_FIRST_INDEX(eh);
  473. for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
  474. if (k != 0 &&
  475. le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
  476. printk(KERN_DEBUG "k=%d, ix=0x%p, "
  477. "first=0x%p\n", k,
  478. ix, EXT_FIRST_INDEX(eh));
  479. printk(KERN_DEBUG "%u <= %u\n",
  480. le32_to_cpu(ix->ei_block),
  481. le32_to_cpu(ix[-1].ei_block));
  482. }
  483. BUG_ON(k && le32_to_cpu(ix->ei_block)
  484. <= le32_to_cpu(ix[-1].ei_block));
  485. if (block < le32_to_cpu(ix->ei_block))
  486. break;
  487. chix = ix;
  488. }
  489. BUG_ON(chix != path->p_idx);
  490. }
  491. #endif
  492. }
  493. /*
  494. * ext4_ext_binsearch:
  495. * binary search for closest extent of the given block
  496. * the header must be checked before calling this
  497. */
  498. static void
  499. ext4_ext_binsearch(struct inode *inode,
  500. struct ext4_ext_path *path, ext4_lblk_t block)
  501. {
  502. struct ext4_extent_header *eh = path->p_hdr;
  503. struct ext4_extent *r, *l, *m;
  504. if (eh->eh_entries == 0) {
  505. /*
  506. * this leaf is empty:
  507. * we get such a leaf in split/add case
  508. */
  509. return;
  510. }
  511. ext_debug("binsearch for %u: ", block);
  512. l = EXT_FIRST_EXTENT(eh) + 1;
  513. r = EXT_LAST_EXTENT(eh);
  514. while (l <= r) {
  515. m = l + (r - l) / 2;
  516. if (block < le32_to_cpu(m->ee_block))
  517. r = m - 1;
  518. else
  519. l = m + 1;
  520. ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
  521. m, le32_to_cpu(m->ee_block),
  522. r, le32_to_cpu(r->ee_block));
  523. }
  524. path->p_ext = l - 1;
  525. ext_debug(" -> %d:%llu:[%d]%d ",
  526. le32_to_cpu(path->p_ext->ee_block),
  527. ext4_ext_pblock(path->p_ext),
  528. ext4_ext_is_uninitialized(path->p_ext),
  529. ext4_ext_get_actual_len(path->p_ext));
  530. #ifdef CHECK_BINSEARCH
  531. {
  532. struct ext4_extent *chex, *ex;
  533. int k;
  534. chex = ex = EXT_FIRST_EXTENT(eh);
  535. for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
  536. BUG_ON(k && le32_to_cpu(ex->ee_block)
  537. <= le32_to_cpu(ex[-1].ee_block));
  538. if (block < le32_to_cpu(ex->ee_block))
  539. break;
  540. chex = ex;
  541. }
  542. BUG_ON(chex != path->p_ext);
  543. }
  544. #endif
  545. }
  546. int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
  547. {
  548. struct ext4_extent_header *eh;
  549. eh = ext_inode_hdr(inode);
  550. eh->eh_depth = 0;
  551. eh->eh_entries = 0;
  552. eh->eh_magic = EXT4_EXT_MAGIC;
  553. eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
  554. ext4_mark_inode_dirty(handle, inode);
  555. ext4_ext_invalidate_cache(inode);
  556. return 0;
  557. }
  558. struct ext4_ext_path *
  559. ext4_ext_find_extent(struct inode *inode, ext4_lblk_t block,
  560. struct ext4_ext_path *path)
  561. {
  562. struct ext4_extent_header *eh;
  563. struct buffer_head *bh;
  564. short int depth, i, ppos = 0, alloc = 0;
  565. eh = ext_inode_hdr(inode);
  566. depth = ext_depth(inode);
  567. /* account possible depth increase */
  568. if (!path) {
  569. path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2),
  570. GFP_NOFS);
  571. if (!path)
  572. return ERR_PTR(-ENOMEM);
  573. alloc = 1;
  574. }
  575. path[0].p_hdr = eh;
  576. path[0].p_bh = NULL;
  577. i = depth;
  578. /* walk through the tree */
  579. while (i) {
  580. int need_to_validate = 0;
  581. ext_debug("depth %d: num %d, max %d\n",
  582. ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
  583. ext4_ext_binsearch_idx(inode, path + ppos, block);
  584. path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
  585. path[ppos].p_depth = i;
  586. path[ppos].p_ext = NULL;
  587. bh = sb_getblk(inode->i_sb, path[ppos].p_block);
  588. if (unlikely(!bh))
  589. goto err;
  590. if (!bh_uptodate_or_lock(bh)) {
  591. trace_ext4_ext_load_extent(inode, block,
  592. path[ppos].p_block);
  593. if (bh_submit_read(bh) < 0) {
  594. put_bh(bh);
  595. goto err;
  596. }
  597. /* validate the extent entries */
  598. need_to_validate = 1;
  599. }
  600. eh = ext_block_hdr(bh);
  601. ppos++;
  602. if (unlikely(ppos > depth)) {
  603. put_bh(bh);
  604. EXT4_ERROR_INODE(inode,
  605. "ppos %d > depth %d", ppos, depth);
  606. goto err;
  607. }
  608. path[ppos].p_bh = bh;
  609. path[ppos].p_hdr = eh;
  610. i--;
  611. if (need_to_validate && ext4_ext_check(inode, eh, i))
  612. goto err;
  613. }
  614. path[ppos].p_depth = i;
  615. path[ppos].p_ext = NULL;
  616. path[ppos].p_idx = NULL;
  617. /* find extent */
  618. ext4_ext_binsearch(inode, path + ppos, block);
  619. /* if not an empty leaf */
  620. if (path[ppos].p_ext)
  621. path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext);
  622. ext4_ext_show_path(inode, path);
  623. return path;
  624. err:
  625. ext4_ext_drop_refs(path);
  626. if (alloc)
  627. kfree(path);
  628. return ERR_PTR(-EIO);
  629. }
  630. /*
  631. * ext4_ext_insert_index:
  632. * insert new index [@logical;@ptr] into the block at @curp;
  633. * check where to insert: before @curp or after @curp
  634. */
  635. static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
  636. struct ext4_ext_path *curp,
  637. int logical, ext4_fsblk_t ptr)
  638. {
  639. struct ext4_extent_idx *ix;
  640. int len, err;
  641. err = ext4_ext_get_access(handle, inode, curp);
  642. if (err)
  643. return err;
  644. if (unlikely(logical == le32_to_cpu(curp->p_idx->ei_block))) {
  645. EXT4_ERROR_INODE(inode,
  646. "logical %d == ei_block %d!",
  647. logical, le32_to_cpu(curp->p_idx->ei_block));
  648. return -EIO;
  649. }
  650. len = EXT_MAX_INDEX(curp->p_hdr) - curp->p_idx;
  651. if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
  652. /* insert after */
  653. if (curp->p_idx != EXT_LAST_INDEX(curp->p_hdr)) {
  654. len = (len - 1) * sizeof(struct ext4_extent_idx);
  655. len = len < 0 ? 0 : len;
  656. ext_debug("insert new index %d after: %llu. "
  657. "move %d from 0x%p to 0x%p\n",
  658. logical, ptr, len,
  659. (curp->p_idx + 1), (curp->p_idx + 2));
  660. memmove(curp->p_idx + 2, curp->p_idx + 1, len);
  661. }
  662. ix = curp->p_idx + 1;
  663. } else {
  664. /* insert before */
  665. len = len * sizeof(struct ext4_extent_idx);
  666. len = len < 0 ? 0 : len;
  667. ext_debug("insert new index %d before: %llu. "
  668. "move %d from 0x%p to 0x%p\n",
  669. logical, ptr, len,
  670. curp->p_idx, (curp->p_idx + 1));
  671. memmove(curp->p_idx + 1, curp->p_idx, len);
  672. ix = curp->p_idx;
  673. }
  674. ix->ei_block = cpu_to_le32(logical);
  675. ext4_idx_store_pblock(ix, ptr);
  676. le16_add_cpu(&curp->p_hdr->eh_entries, 1);
  677. if (unlikely(le16_to_cpu(curp->p_hdr->eh_entries)
  678. > le16_to_cpu(curp->p_hdr->eh_max))) {
  679. EXT4_ERROR_INODE(inode,
  680. "eh_entries %d > eh_max %d!",
  681. le16_to_cpu(curp->p_hdr->eh_entries),
  682. le16_to_cpu(curp->p_hdr->eh_max));
  683. return -EIO;
  684. }
  685. if (unlikely(ix > EXT_LAST_INDEX(curp->p_hdr))) {
  686. EXT4_ERROR_INODE(inode, "ix > EXT_LAST_INDEX!");
  687. return -EIO;
  688. }
  689. err = ext4_ext_dirty(handle, inode, curp);
  690. ext4_std_error(inode->i_sb, err);
  691. return err;
  692. }
  693. /*
  694. * ext4_ext_split:
  695. * inserts new subtree into the path, using free index entry
  696. * at depth @at:
  697. * - allocates all needed blocks (new leaf and all intermediate index blocks)
  698. * - makes decision where to split
  699. * - moves remaining extents and index entries (right to the split point)
  700. * into the newly allocated blocks
  701. * - initializes subtree
  702. */
  703. static int ext4_ext_split(handle_t *handle, struct inode *inode,
  704. unsigned int flags,
  705. struct ext4_ext_path *path,
  706. struct ext4_extent *newext, int at)
  707. {
  708. struct buffer_head *bh = NULL;
  709. int depth = ext_depth(inode);
  710. struct ext4_extent_header *neh;
  711. struct ext4_extent_idx *fidx;
  712. int i = at, k, m, a;
  713. ext4_fsblk_t newblock, oldblock;
  714. __le32 border;
  715. ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
  716. int err = 0;
  717. /* make decision: where to split? */
  718. /* FIXME: now decision is simplest: at current extent */
  719. /* if current leaf will be split, then we should use
  720. * border from split point */
  721. if (unlikely(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr))) {
  722. EXT4_ERROR_INODE(inode, "p_ext > EXT_MAX_EXTENT!");
  723. return -EIO;
  724. }
  725. if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
  726. border = path[depth].p_ext[1].ee_block;
  727. ext_debug("leaf will be split."
  728. " next leaf starts at %d\n",
  729. le32_to_cpu(border));
  730. } else {
  731. border = newext->ee_block;
  732. ext_debug("leaf will be added."
  733. " next leaf starts at %d\n",
  734. le32_to_cpu(border));
  735. }
  736. /*
  737. * If error occurs, then we break processing
  738. * and mark filesystem read-only. index won't
  739. * be inserted and tree will be in consistent
  740. * state. Next mount will repair buffers too.
  741. */
  742. /*
  743. * Get array to track all allocated blocks.
  744. * We need this to handle errors and free blocks
  745. * upon them.
  746. */
  747. ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS);
  748. if (!ablocks)
  749. return -ENOMEM;
  750. /* allocate all needed blocks */
  751. ext_debug("allocate %d blocks for indexes/leaf\n", depth - at);
  752. for (a = 0; a < depth - at; a++) {
  753. newblock = ext4_ext_new_meta_block(handle, inode, path,
  754. newext, &err, flags);
  755. if (newblock == 0)
  756. goto cleanup;
  757. ablocks[a] = newblock;
  758. }
  759. /* initialize new leaf */
  760. newblock = ablocks[--a];
  761. if (unlikely(newblock == 0)) {
  762. EXT4_ERROR_INODE(inode, "newblock == 0!");
  763. err = -EIO;
  764. goto cleanup;
  765. }
  766. bh = sb_getblk(inode->i_sb, newblock);
  767. if (!bh) {
  768. err = -EIO;
  769. goto cleanup;
  770. }
  771. lock_buffer(bh);
  772. err = ext4_journal_get_create_access(handle, bh);
  773. if (err)
  774. goto cleanup;
  775. neh = ext_block_hdr(bh);
  776. neh->eh_entries = 0;
  777. neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
  778. neh->eh_magic = EXT4_EXT_MAGIC;
  779. neh->eh_depth = 0;
  780. /* move remainder of path[depth] to the new leaf */
  781. if (unlikely(path[depth].p_hdr->eh_entries !=
  782. path[depth].p_hdr->eh_max)) {
  783. EXT4_ERROR_INODE(inode, "eh_entries %d != eh_max %d!",
  784. path[depth].p_hdr->eh_entries,
  785. path[depth].p_hdr->eh_max);
  786. err = -EIO;
  787. goto cleanup;
  788. }
  789. /* start copy from next extent */
  790. m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++;
  791. ext4_ext_show_move(inode, path, newblock, depth);
  792. if (m) {
  793. struct ext4_extent *ex;
  794. ex = EXT_FIRST_EXTENT(neh);
  795. memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m);
  796. le16_add_cpu(&neh->eh_entries, m);
  797. }
  798. set_buffer_uptodate(bh);
  799. unlock_buffer(bh);
  800. err = ext4_handle_dirty_metadata(handle, inode, bh);
  801. if (err)
  802. goto cleanup;
  803. brelse(bh);
  804. bh = NULL;
  805. /* correct old leaf */
  806. if (m) {
  807. err = ext4_ext_get_access(handle, inode, path + depth);
  808. if (err)
  809. goto cleanup;
  810. le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
  811. err = ext4_ext_dirty(handle, inode, path + depth);
  812. if (err)
  813. goto cleanup;
  814. }
  815. /* create intermediate indexes */
  816. k = depth - at - 1;
  817. if (unlikely(k < 0)) {
  818. EXT4_ERROR_INODE(inode, "k %d < 0!", k);
  819. err = -EIO;
  820. goto cleanup;
  821. }
  822. if (k)
  823. ext_debug("create %d intermediate indices\n", k);
  824. /* insert new index into current index block */
  825. /* current depth stored in i var */
  826. i = depth - 1;
  827. while (k--) {
  828. oldblock = newblock;
  829. newblock = ablocks[--a];
  830. bh = sb_getblk(inode->i_sb, newblock);
  831. if (!bh) {
  832. err = -EIO;
  833. goto cleanup;
  834. }
  835. lock_buffer(bh);
  836. err = ext4_journal_get_create_access(handle, bh);
  837. if (err)
  838. goto cleanup;
  839. neh = ext_block_hdr(bh);
  840. neh->eh_entries = cpu_to_le16(1);
  841. neh->eh_magic = EXT4_EXT_MAGIC;
  842. neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
  843. neh->eh_depth = cpu_to_le16(depth - i);
  844. fidx = EXT_FIRST_INDEX(neh);
  845. fidx->ei_block = border;
  846. ext4_idx_store_pblock(fidx, oldblock);
  847. ext_debug("int.index at %d (block %llu): %u -> %llu\n",
  848. i, newblock, le32_to_cpu(border), oldblock);
  849. /* move remainder of path[i] to the new index block */
  850. if (unlikely(EXT_MAX_INDEX(path[i].p_hdr) !=
  851. EXT_LAST_INDEX(path[i].p_hdr))) {
  852. EXT4_ERROR_INODE(inode,
  853. "EXT_MAX_INDEX != EXT_LAST_INDEX ee_block %d!",
  854. le32_to_cpu(path[i].p_ext->ee_block));
  855. err = -EIO;
  856. goto cleanup;
  857. }
  858. /* start copy indexes */
  859. m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
  860. ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
  861. EXT_MAX_INDEX(path[i].p_hdr));
  862. ext4_ext_show_move(inode, path, newblock, i);
  863. if (m) {
  864. memmove(++fidx, path[i].p_idx,
  865. sizeof(struct ext4_extent_idx) * m);
  866. le16_add_cpu(&neh->eh_entries, m);
  867. }
  868. set_buffer_uptodate(bh);
  869. unlock_buffer(bh);
  870. err = ext4_handle_dirty_metadata(handle, inode, bh);
  871. if (err)
  872. goto cleanup;
  873. brelse(bh);
  874. bh = NULL;
  875. /* correct old index */
  876. if (m) {
  877. err = ext4_ext_get_access(handle, inode, path + i);
  878. if (err)
  879. goto cleanup;
  880. le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
  881. err = ext4_ext_dirty(handle, inode, path + i);
  882. if (err)
  883. goto cleanup;
  884. }
  885. i--;
  886. }
  887. /* insert new index */
  888. err = ext4_ext_insert_index(handle, inode, path + at,
  889. le32_to_cpu(border), newblock);
  890. cleanup:
  891. if (bh) {
  892. if (buffer_locked(bh))
  893. unlock_buffer(bh);
  894. brelse(bh);
  895. }
  896. if (err) {
  897. /* free all allocated blocks in error case */
  898. for (i = 0; i < depth; i++) {
  899. if (!ablocks[i])
  900. continue;
  901. ext4_free_blocks(handle, inode, NULL, ablocks[i], 1,
  902. EXT4_FREE_BLOCKS_METADATA);
  903. }
  904. }
  905. kfree(ablocks);
  906. return err;
  907. }
  908. /*
  909. * ext4_ext_grow_indepth:
  910. * implements tree growing procedure:
  911. * - allocates new block
  912. * - moves top-level data (index block or leaf) into the new block
  913. * - initializes new top-level, creating index that points to the
  914. * just created block
  915. */
  916. static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
  917. unsigned int flags,
  918. struct ext4_ext_path *path,
  919. struct ext4_extent *newext)
  920. {
  921. struct ext4_ext_path *curp = path;
  922. struct ext4_extent_header *neh;
  923. struct buffer_head *bh;
  924. ext4_fsblk_t newblock;
  925. int err = 0;
  926. newblock = ext4_ext_new_meta_block(handle, inode, path,
  927. newext, &err, flags);
  928. if (newblock == 0)
  929. return err;
  930. bh = sb_getblk(inode->i_sb, newblock);
  931. if (!bh) {
  932. err = -EIO;
  933. ext4_std_error(inode->i_sb, err);
  934. return err;
  935. }
  936. lock_buffer(bh);
  937. err = ext4_journal_get_create_access(handle, bh);
  938. if (err) {
  939. unlock_buffer(bh);
  940. goto out;
  941. }
  942. /* move top-level index/leaf into new block */
  943. memmove(bh->b_data, curp->p_hdr, sizeof(EXT4_I(inode)->i_data));
  944. /* set size of new block */
  945. neh = ext_block_hdr(bh);
  946. /* old root could have indexes or leaves
  947. * so calculate e_max right way */
  948. if (ext_depth(inode))
  949. neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
  950. else
  951. neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
  952. neh->eh_magic = EXT4_EXT_MAGIC;
  953. set_buffer_uptodate(bh);
  954. unlock_buffer(bh);
  955. err = ext4_handle_dirty_metadata(handle, inode, bh);
  956. if (err)
  957. goto out;
  958. /* create index in new top-level index: num,max,pointer */
  959. err = ext4_ext_get_access(handle, inode, curp);
  960. if (err)
  961. goto out;
  962. curp->p_hdr->eh_magic = EXT4_EXT_MAGIC;
  963. curp->p_hdr->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0));
  964. curp->p_hdr->eh_entries = cpu_to_le16(1);
  965. curp->p_idx = EXT_FIRST_INDEX(curp->p_hdr);
  966. if (path[0].p_hdr->eh_depth)
  967. curp->p_idx->ei_block =
  968. EXT_FIRST_INDEX(path[0].p_hdr)->ei_block;
  969. else
  970. curp->p_idx->ei_block =
  971. EXT_FIRST_EXTENT(path[0].p_hdr)->ee_block;
  972. ext4_idx_store_pblock(curp->p_idx, newblock);
  973. neh = ext_inode_hdr(inode);
  974. ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
  975. le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
  976. le32_to_cpu(EXT_FIRST_INDEX(neh)->ei_block),
  977. ext4_idx_pblock(EXT_FIRST_INDEX(neh)));
  978. neh->eh_depth = cpu_to_le16(path->p_depth + 1);
  979. err = ext4_ext_dirty(handle, inode, curp);
  980. out:
  981. brelse(bh);
  982. return err;
  983. }
  984. /*
  985. * ext4_ext_create_new_leaf:
  986. * finds empty index and adds new leaf.
  987. * if no free index is found, then it requests in-depth growing.
  988. */
  989. static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
  990. unsigned int flags,
  991. struct ext4_ext_path *path,
  992. struct ext4_extent *newext)
  993. {
  994. struct ext4_ext_path *curp;
  995. int depth, i, err = 0;
  996. repeat:
  997. i = depth = ext_depth(inode);
  998. /* walk up to the tree and look for free index entry */
  999. curp = path + depth;
  1000. while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
  1001. i--;
  1002. curp--;
  1003. }
  1004. /* we use already allocated block for index block,
  1005. * so subsequent data blocks should be contiguous */
  1006. if (EXT_HAS_FREE_INDEX(curp)) {
  1007. /* if we found index with free entry, then use that
  1008. * entry: create all needed subtree and add new leaf */
  1009. err = ext4_ext_split(handle, inode, flags, path, newext, i);
  1010. if (err)
  1011. goto out;
  1012. /* refill path */
  1013. ext4_ext_drop_refs(path);
  1014. path = ext4_ext_find_extent(inode,
  1015. (ext4_lblk_t)le32_to_cpu(newext->ee_block),
  1016. path);
  1017. if (IS_ERR(path))
  1018. err = PTR_ERR(path);
  1019. } else {
  1020. /* tree is full, time to grow in depth */
  1021. err = ext4_ext_grow_indepth(handle, inode, flags,
  1022. path, newext);
  1023. if (err)
  1024. goto out;
  1025. /* refill path */
  1026. ext4_ext_drop_refs(path);
  1027. path = ext4_ext_find_extent(inode,
  1028. (ext4_lblk_t)le32_to_cpu(newext->ee_block),
  1029. path);
  1030. if (IS_ERR(path)) {
  1031. err = PTR_ERR(path);
  1032. goto out;
  1033. }
  1034. /*
  1035. * only first (depth 0 -> 1) produces free space;
  1036. * in all other cases we have to split the grown tree
  1037. */
  1038. depth = ext_depth(inode);
  1039. if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
  1040. /* now we need to split */
  1041. goto repeat;
  1042. }
  1043. }
  1044. out:
  1045. return err;
  1046. }
  1047. /*
  1048. * search the closest allocated block to the left for *logical
  1049. * and returns it at @logical + it's physical address at @phys
  1050. * if *logical is the smallest allocated block, the function
  1051. * returns 0 at @phys
  1052. * return value contains 0 (success) or error code
  1053. */
  1054. static int ext4_ext_search_left(struct inode *inode,
  1055. struct ext4_ext_path *path,
  1056. ext4_lblk_t *logical, ext4_fsblk_t *phys)
  1057. {
  1058. struct ext4_extent_idx *ix;
  1059. struct ext4_extent *ex;
  1060. int depth, ee_len;
  1061. if (unlikely(path == NULL)) {
  1062. EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
  1063. return -EIO;
  1064. }
  1065. depth = path->p_depth;
  1066. *phys = 0;
  1067. if (depth == 0 && path->p_ext == NULL)
  1068. return 0;
  1069. /* usually extent in the path covers blocks smaller
  1070. * then *logical, but it can be that extent is the
  1071. * first one in the file */
  1072. ex = path[depth].p_ext;
  1073. ee_len = ext4_ext_get_actual_len(ex);
  1074. if (*logical < le32_to_cpu(ex->ee_block)) {
  1075. if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
  1076. EXT4_ERROR_INODE(inode,
  1077. "EXT_FIRST_EXTENT != ex *logical %d ee_block %d!",
  1078. *logical, le32_to_cpu(ex->ee_block));
  1079. return -EIO;
  1080. }
  1081. while (--depth >= 0) {
  1082. ix = path[depth].p_idx;
  1083. if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
  1084. EXT4_ERROR_INODE(inode,
  1085. "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
  1086. ix != NULL ? ix->ei_block : 0,
  1087. EXT_FIRST_INDEX(path[depth].p_hdr) != NULL ?
  1088. EXT_FIRST_INDEX(path[depth].p_hdr)->ei_block : 0,
  1089. depth);
  1090. return -EIO;
  1091. }
  1092. }
  1093. return 0;
  1094. }
  1095. if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
  1096. EXT4_ERROR_INODE(inode,
  1097. "logical %d < ee_block %d + ee_len %d!",
  1098. *logical, le32_to_cpu(ex->ee_block), ee_len);
  1099. return -EIO;
  1100. }
  1101. *logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
  1102. *phys = ext4_ext_pblock(ex) + ee_len - 1;
  1103. return 0;
  1104. }
  1105. /*
  1106. * search the closest allocated block to the right for *logical
  1107. * and returns it at @logical + it's physical address at @phys
  1108. * if *logical is the smallest allocated block, the function
  1109. * returns 0 at @phys
  1110. * return value contains 0 (success) or error code
  1111. */
  1112. static int ext4_ext_search_right(struct inode *inode,
  1113. struct ext4_ext_path *path,
  1114. ext4_lblk_t *logical, ext4_fsblk_t *phys)
  1115. {
  1116. struct buffer_head *bh = NULL;
  1117. struct ext4_extent_header *eh;
  1118. struct ext4_extent_idx *ix;
  1119. struct ext4_extent *ex;
  1120. ext4_fsblk_t block;
  1121. int depth; /* Note, NOT eh_depth; depth from top of tree */
  1122. int ee_len;
  1123. if (unlikely(path == NULL)) {
  1124. EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
  1125. return -EIO;
  1126. }
  1127. depth = path->p_depth;
  1128. *phys = 0;
  1129. if (depth == 0 && path->p_ext == NULL)
  1130. return 0;
  1131. /* usually extent in the path covers blocks smaller
  1132. * then *logical, but it can be that extent is the
  1133. * first one in the file */
  1134. ex = path[depth].p_ext;
  1135. ee_len = ext4_ext_get_actual_len(ex);
  1136. if (*logical < le32_to_cpu(ex->ee_block)) {
  1137. if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
  1138. EXT4_ERROR_INODE(inode,
  1139. "first_extent(path[%d].p_hdr) != ex",
  1140. depth);
  1141. return -EIO;
  1142. }
  1143. while (--depth >= 0) {
  1144. ix = path[depth].p_idx;
  1145. if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
  1146. EXT4_ERROR_INODE(inode,
  1147. "ix != EXT_FIRST_INDEX *logical %d!",
  1148. *logical);
  1149. return -EIO;
  1150. }
  1151. }
  1152. *logical = le32_to_cpu(ex->ee_block);
  1153. *phys = ext4_ext_pblock(ex);
  1154. return 0;
  1155. }
  1156. if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
  1157. EXT4_ERROR_INODE(inode,
  1158. "logical %d < ee_block %d + ee_len %d!",
  1159. *logical, le32_to_cpu(ex->ee_block), ee_len);
  1160. return -EIO;
  1161. }
  1162. if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
  1163. /* next allocated block in this leaf */
  1164. ex++;
  1165. *logical = le32_to_cpu(ex->ee_block);
  1166. *phys = ext4_ext_pblock(ex);
  1167. return 0;
  1168. }
  1169. /* go up and search for index to the right */
  1170. while (--depth >= 0) {
  1171. ix = path[depth].p_idx;
  1172. if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
  1173. goto got_index;
  1174. }
  1175. /* we've gone up to the root and found no index to the right */
  1176. return 0;
  1177. got_index:
  1178. /* we've found index to the right, let's
  1179. * follow it and find the closest allocated
  1180. * block to the right */
  1181. ix++;
  1182. block = ext4_idx_pblock(ix);
  1183. while (++depth < path->p_depth) {
  1184. bh = sb_bread(inode->i_sb, block);
  1185. if (bh == NULL)
  1186. return -EIO;
  1187. eh = ext_block_hdr(bh);
  1188. /* subtract from p_depth to get proper eh_depth */
  1189. if (ext4_ext_check(inode, eh, path->p_depth - depth)) {
  1190. put_bh(bh);
  1191. return -EIO;
  1192. }
  1193. ix = EXT_FIRST_INDEX(eh);
  1194. block = ext4_idx_pblock(ix);
  1195. put_bh(bh);
  1196. }
  1197. bh = sb_bread(inode->i_sb, block);
  1198. if (bh == NULL)
  1199. return -EIO;
  1200. eh = ext_block_hdr(bh);
  1201. if (ext4_ext_check(inode, eh, path->p_depth - depth)) {
  1202. put_bh(bh);
  1203. return -EIO;
  1204. }
  1205. ex = EXT_FIRST_EXTENT(eh);
  1206. *logical = le32_to_cpu(ex->ee_block);
  1207. *phys = ext4_ext_pblock(ex);
  1208. put_bh(bh);
  1209. return 0;
  1210. }
  1211. /*
  1212. * ext4_ext_next_allocated_block:
  1213. * returns allocated block in subsequent extent or EXT_MAX_BLOCKS.
  1214. * NOTE: it considers block number from index entry as
  1215. * allocated block. Thus, index entries have to be consistent
  1216. * with leaves.
  1217. */
  1218. static ext4_lblk_t
  1219. ext4_ext_next_allocated_block(struct ext4_ext_path *path)
  1220. {
  1221. int depth;
  1222. BUG_ON(path == NULL);
  1223. depth = path->p_depth;
  1224. if (depth == 0 && path->p_ext == NULL)
  1225. return EXT_MAX_BLOCKS;
  1226. while (depth >= 0) {
  1227. if (depth == path->p_depth) {
  1228. /* leaf */
  1229. if (path[depth].p_ext !=
  1230. EXT_LAST_EXTENT(path[depth].p_hdr))
  1231. return le32_to_cpu(path[depth].p_ext[1].ee_block);
  1232. } else {
  1233. /* index */
  1234. if (path[depth].p_idx !=
  1235. EXT_LAST_INDEX(path[depth].p_hdr))
  1236. return le32_to_cpu(path[depth].p_idx[1].ei_block);
  1237. }
  1238. depth--;
  1239. }
  1240. return EXT_MAX_BLOCKS;
  1241. }
  1242. /*
  1243. * ext4_ext_next_leaf_block:
  1244. * returns first allocated block from next leaf or EXT_MAX_BLOCKS
  1245. */
  1246. static ext4_lblk_t ext4_ext_next_leaf_block(struct inode *inode,
  1247. struct ext4_ext_path *path)
  1248. {
  1249. int depth;
  1250. BUG_ON(path == NULL);
  1251. depth = path->p_depth;
  1252. /* zero-tree has no leaf blocks at all */
  1253. if (depth == 0)
  1254. return EXT_MAX_BLOCKS;
  1255. /* go to index block */
  1256. depth--;
  1257. while (depth >= 0) {
  1258. if (path[depth].p_idx !=
  1259. EXT_LAST_INDEX(path[depth].p_hdr))
  1260. return (ext4_lblk_t)
  1261. le32_to_cpu(path[depth].p_idx[1].ei_block);
  1262. depth--;
  1263. }
  1264. return EXT_MAX_BLOCKS;
  1265. }
  1266. /*
  1267. * ext4_ext_correct_indexes:
  1268. * if leaf gets modified and modified extent is first in the leaf,
  1269. * then we have to correct all indexes above.
  1270. * TODO: do we need to correct tree in all cases?
  1271. */
  1272. static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
  1273. struct ext4_ext_path *path)
  1274. {
  1275. struct ext4_extent_header *eh;
  1276. int depth = ext_depth(inode);
  1277. struct ext4_extent *ex;
  1278. __le32 border;
  1279. int k, err = 0;
  1280. eh = path[depth].p_hdr;
  1281. ex = path[depth].p_ext;
  1282. if (unlikely(ex == NULL || eh == NULL)) {
  1283. EXT4_ERROR_INODE(inode,
  1284. "ex %p == NULL or eh %p == NULL", ex, eh);
  1285. return -EIO;
  1286. }
  1287. if (depth == 0) {
  1288. /* there is no tree at all */
  1289. return 0;
  1290. }
  1291. if (ex != EXT_FIRST_EXTENT(eh)) {
  1292. /* we correct tree if first leaf got modified only */
  1293. return 0;
  1294. }
  1295. /*
  1296. * TODO: we need correction if border is smaller than current one
  1297. */
  1298. k = depth - 1;
  1299. border = path[depth].p_ext->ee_block;
  1300. err = ext4_ext_get_access(handle, inode, path + k);
  1301. if (err)
  1302. return err;
  1303. path[k].p_idx->ei_block = border;
  1304. err = ext4_ext_dirty(handle, inode, path + k);
  1305. if (err)
  1306. return err;
  1307. while (k--) {
  1308. /* change all left-side indexes */
  1309. if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
  1310. break;
  1311. err = ext4_ext_get_access(handle, inode, path + k);
  1312. if (err)
  1313. break;
  1314. path[k].p_idx->ei_block = border;
  1315. err = ext4_ext_dirty(handle, inode, path + k);
  1316. if (err)
  1317. break;
  1318. }
  1319. return err;
  1320. }
  1321. int
  1322. ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
  1323. struct ext4_extent *ex2)
  1324. {
  1325. unsigned short ext1_ee_len, ext2_ee_len, max_len;
  1326. /*
  1327. * Make sure that either both extents are uninitialized, or
  1328. * both are _not_.
  1329. */
  1330. if (ext4_ext_is_uninitialized(ex1) ^ ext4_ext_is_uninitialized(ex2))
  1331. return 0;
  1332. if (ext4_ext_is_uninitialized(ex1))
  1333. max_len = EXT_UNINIT_MAX_LEN;
  1334. else
  1335. max_len = EXT_INIT_MAX_LEN;
  1336. ext1_ee_len = ext4_ext_get_actual_len(ex1);
  1337. ext2_ee_len = ext4_ext_get_actual_len(ex2);
  1338. if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
  1339. le32_to_cpu(ex2->ee_block))
  1340. return 0;
  1341. /*
  1342. * To allow future support for preallocated extents to be added
  1343. * as an RO_COMPAT feature, refuse to merge to extents if
  1344. * this can result in the top bit of ee_len being set.
  1345. */
  1346. if (ext1_ee_len + ext2_ee_len > max_len)
  1347. return 0;
  1348. #ifdef AGGRESSIVE_TEST
  1349. if (ext1_ee_len >= 4)
  1350. return 0;
  1351. #endif
  1352. if (ext4_ext_pblock(ex1) + ext1_ee_len == ext4_ext_pblock(ex2))
  1353. return 1;
  1354. return 0;
  1355. }
  1356. /*
  1357. * This function tries to merge the "ex" extent to the next extent in the tree.
  1358. * It always tries to merge towards right. If you want to merge towards
  1359. * left, pass "ex - 1" as argument instead of "ex".
  1360. * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
  1361. * 1 if they got merged.
  1362. */
  1363. static int ext4_ext_try_to_merge_right(struct inode *inode,
  1364. struct ext4_ext_path *path,
  1365. struct ext4_extent *ex)
  1366. {
  1367. struct ext4_extent_header *eh;
  1368. unsigned int depth, len;
  1369. int merge_done = 0;
  1370. int uninitialized = 0;
  1371. depth = ext_depth(inode);
  1372. BUG_ON(path[depth].p_hdr == NULL);
  1373. eh = path[depth].p_hdr;
  1374. while (ex < EXT_LAST_EXTENT(eh)) {
  1375. if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
  1376. break;
  1377. /* merge with next extent! */
  1378. if (ext4_ext_is_uninitialized(ex))
  1379. uninitialized = 1;
  1380. ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
  1381. + ext4_ext_get_actual_len(ex + 1));
  1382. if (uninitialized)
  1383. ext4_ext_mark_uninitialized(ex);
  1384. if (ex + 1 < EXT_LAST_EXTENT(eh)) {
  1385. len = (EXT_LAST_EXTENT(eh) - ex - 1)
  1386. * sizeof(struct ext4_extent);
  1387. memmove(ex + 1, ex + 2, len);
  1388. }
  1389. le16_add_cpu(&eh->eh_entries, -1);
  1390. merge_done = 1;
  1391. WARN_ON(eh->eh_entries == 0);
  1392. if (!eh->eh_entries)
  1393. EXT4_ERROR_INODE(inode, "eh->eh_entries = 0!");
  1394. }
  1395. return merge_done;
  1396. }
  1397. /*
  1398. * This function tries to merge the @ex extent to neighbours in the tree.
  1399. * return 1 if merge left else 0.
  1400. */
  1401. static int ext4_ext_try_to_merge(struct inode *inode,
  1402. struct ext4_ext_path *path,
  1403. struct ext4_extent *ex) {
  1404. struct ext4_extent_header *eh;
  1405. unsigned int depth;
  1406. int merge_done = 0;
  1407. int ret = 0;
  1408. depth = ext_depth(inode);
  1409. BUG_ON(path[depth].p_hdr == NULL);
  1410. eh = path[depth].p_hdr;
  1411. if (ex > EXT_FIRST_EXTENT(eh))
  1412. merge_done = ext4_ext_try_to_merge_right(inode, path, ex - 1);
  1413. if (!merge_done)
  1414. ret = ext4_ext_try_to_merge_right(inode, path, ex);
  1415. return ret;
  1416. }
  1417. /*
  1418. * check if a portion of the "newext" extent overlaps with an
  1419. * existing extent.
  1420. *
  1421. * If there is an overlap discovered, it updates the length of the newext
  1422. * such that there will be no overlap, and then returns 1.
  1423. * If there is no overlap found, it returns 0.
  1424. */
  1425. static unsigned int ext4_ext_check_overlap(struct inode *inode,
  1426. struct ext4_extent *newext,
  1427. struct ext4_ext_path *path)
  1428. {
  1429. ext4_lblk_t b1, b2;
  1430. unsigned int depth, len1;
  1431. unsigned int ret = 0;
  1432. b1 = le32_to_cpu(newext->ee_block);
  1433. len1 = ext4_ext_get_actual_len(newext);
  1434. depth = ext_depth(inode);
  1435. if (!path[depth].p_ext)
  1436. goto out;
  1437. b2 = le32_to_cpu(path[depth].p_ext->ee_block);
  1438. /*
  1439. * get the next allocated block if the extent in the path
  1440. * is before the requested block(s)
  1441. */
  1442. if (b2 < b1) {
  1443. b2 = ext4_ext_next_allocated_block(path);
  1444. if (b2 == EXT_MAX_BLOCKS)
  1445. goto out;
  1446. }
  1447. /* check for wrap through zero on extent logical start block*/
  1448. if (b1 + len1 < b1) {
  1449. len1 = EXT_MAX_BLOCKS - b1;
  1450. newext->ee_len = cpu_to_le16(len1);
  1451. ret = 1;
  1452. }
  1453. /* check for overlap */
  1454. if (b1 + len1 > b2) {
  1455. newext->ee_len = cpu_to_le16(b2 - b1);
  1456. ret = 1;
  1457. }
  1458. out:
  1459. return ret;
  1460. }
  1461. /*
  1462. * ext4_ext_insert_extent:
  1463. * tries to merge requsted extent into the existing extent or
  1464. * inserts requested extent as new one into the tree,
  1465. * creating new leaf in the no-space case.
  1466. */
  1467. int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
  1468. struct ext4_ext_path *path,
  1469. struct ext4_extent *newext, int flag)
  1470. {
  1471. struct ext4_extent_header *eh;
  1472. struct ext4_extent *ex, *fex;
  1473. struct ext4_extent *nearex; /* nearest extent */
  1474. struct ext4_ext_path *npath = NULL;
  1475. int depth, len, err;
  1476. ext4_lblk_t next;
  1477. unsigned uninitialized = 0;
  1478. int flags = 0;
  1479. if (unlikely(ext4_ext_get_actual_len(newext) == 0)) {
  1480. EXT4_ERROR_INODE(inode, "ext4_ext_get_actual_len(newext) == 0");
  1481. return -EIO;
  1482. }
  1483. depth = ext_depth(inode);
  1484. ex = path[depth].p_ext;
  1485. if (unlikely(path[depth].p_hdr == NULL)) {
  1486. EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
  1487. return -EIO;
  1488. }
  1489. /* try to insert block into found extent and return */
  1490. if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO)
  1491. && ext4_can_extents_be_merged(inode, ex, newext)) {
  1492. ext_debug("append [%d]%d block to %d:[%d]%d (from %llu)\n",
  1493. ext4_ext_is_uninitialized(newext),
  1494. ext4_ext_get_actual_len(newext),
  1495. le32_to_cpu(ex->ee_block),
  1496. ext4_ext_is_uninitialized(ex),
  1497. ext4_ext_get_actual_len(ex),
  1498. ext4_ext_pblock(ex));
  1499. err = ext4_ext_get_access(handle, inode, path + depth);
  1500. if (err)
  1501. return err;
  1502. /*
  1503. * ext4_can_extents_be_merged should have checked that either
  1504. * both extents are uninitialized, or both aren't. Thus we
  1505. * need to check only one of them here.
  1506. */
  1507. if (ext4_ext_is_uninitialized(ex))
  1508. uninitialized = 1;
  1509. ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
  1510. + ext4_ext_get_actual_len(newext));
  1511. if (uninitialized)
  1512. ext4_ext_mark_uninitialized(ex);
  1513. eh = path[depth].p_hdr;
  1514. nearex = ex;
  1515. goto merge;
  1516. }
  1517. depth = ext_depth(inode);
  1518. eh = path[depth].p_hdr;
  1519. if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
  1520. goto has_space;
  1521. /* probably next leaf has space for us? */
  1522. fex = EXT_LAST_EXTENT(eh);
  1523. next = EXT_MAX_BLOCKS;
  1524. if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))
  1525. next = ext4_ext_next_leaf_block(inode, path);
  1526. if (next != EXT_MAX_BLOCKS) {
  1527. ext_debug("next leaf block - %d\n", next);
  1528. BUG_ON(npath != NULL);
  1529. npath = ext4_ext_find_extent(inode, next, NULL);
  1530. if (IS_ERR(npath))
  1531. return PTR_ERR(npath);
  1532. BUG_ON(npath->p_depth != path->p_depth);
  1533. eh = npath[depth].p_hdr;
  1534. if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
  1535. ext_debug("next leaf isn't full(%d)\n",
  1536. le16_to_cpu(eh->eh_entries));
  1537. path = npath;
  1538. goto has_space;
  1539. }
  1540. ext_debug("next leaf has no free space(%d,%d)\n",
  1541. le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
  1542. }
  1543. /*
  1544. * There is no free space in the found leaf.
  1545. * We're gonna add a new leaf in the tree.
  1546. */
  1547. if (flag & EXT4_GET_BLOCKS_PUNCH_OUT_EXT)
  1548. flags = EXT4_MB_USE_ROOT_BLOCKS;
  1549. err = ext4_ext_create_new_leaf(handle, inode, flags, path, newext);
  1550. if (err)
  1551. goto cleanup;
  1552. depth = ext_depth(inode);
  1553. eh = path[depth].p_hdr;
  1554. has_space:
  1555. nearex = path[depth].p_ext;
  1556. err = ext4_ext_get_access(handle, inode, path + depth);
  1557. if (err)
  1558. goto cleanup;
  1559. if (!nearex) {
  1560. /* there is no extent in this leaf, create first one */
  1561. ext_debug("first extent in the leaf: %d:%llu:[%d]%d\n",
  1562. le32_to_cpu(newext->ee_block),
  1563. ext4_ext_pblock(newext),
  1564. ext4_ext_is_uninitialized(newext),
  1565. ext4_ext_get_actual_len(newext));
  1566. path[depth].p_ext = EXT_FIRST_EXTENT(eh);
  1567. } else if (le32_to_cpu(newext->ee_block)
  1568. > le32_to_cpu(nearex->ee_block)) {
  1569. /* BUG_ON(newext->ee_block == nearex->ee_block); */
  1570. if (nearex != EXT_LAST_EXTENT(eh)) {
  1571. len = EXT_MAX_EXTENT(eh) - nearex;
  1572. len = (len - 1) * sizeof(struct ext4_extent);
  1573. len = len < 0 ? 0 : len;
  1574. ext_debug("insert %d:%llu:[%d]%d after: nearest 0x%p, "
  1575. "move %d from 0x%p to 0x%p\n",
  1576. le32_to_cpu(newext->ee_block),
  1577. ext4_ext_pblock(newext),
  1578. ext4_ext_is_uninitialized(newext),
  1579. ext4_ext_get_actual_len(newext),
  1580. nearex, len, nearex + 1, nearex + 2);
  1581. memmove(nearex + 2, nearex + 1, len);
  1582. }
  1583. path[depth].p_ext = nearex + 1;
  1584. } else {
  1585. BUG_ON(newext->ee_block == nearex->ee_block);
  1586. len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent);
  1587. len = len < 0 ? 0 : len;
  1588. ext_debug("insert %d:%llu:[%d]%d before: nearest 0x%p, "
  1589. "move %d from 0x%p to 0x%p\n",
  1590. le32_to_cpu(newext->ee_block),
  1591. ext4_ext_pblock(newext),
  1592. ext4_ext_is_uninitialized(newext),
  1593. ext4_ext_get_actual_len(newext),
  1594. nearex, len, nearex + 1, nearex + 2);
  1595. memmove(nearex + 1, nearex, len);
  1596. path[depth].p_ext = nearex;
  1597. }
  1598. le16_add_cpu(&eh->eh_entries, 1);
  1599. nearex = path[depth].p_ext;
  1600. nearex->ee_block = newext->ee_block;
  1601. ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext));
  1602. nearex->ee_len = newext->ee_len;
  1603. merge:
  1604. /* try to merge extents to the right */
  1605. if (!(flag & EXT4_GET_BLOCKS_PRE_IO))
  1606. ext4_ext_try_to_merge(inode, path, nearex);
  1607. /* try to merge extents to the left */
  1608. /* time to correct all indexes above */
  1609. err = ext4_ext_correct_indexes(handle, inode, path);
  1610. if (err)
  1611. goto cleanup;
  1612. err = ext4_ext_dirty(handle, inode, path + depth);
  1613. cleanup:
  1614. if (npath) {
  1615. ext4_ext_drop_refs(npath);
  1616. kfree(npath);
  1617. }
  1618. ext4_ext_invalidate_cache(inode);
  1619. return err;
  1620. }
  1621. static int ext4_ext_walk_space(struct inode *inode, ext4_lblk_t block,
  1622. ext4_lblk_t num, ext_prepare_callback func,
  1623. void *cbdata)
  1624. {
  1625. struct ext4_ext_path *path = NULL;
  1626. struct ext4_ext_cache cbex;
  1627. struct ext4_extent *ex;
  1628. ext4_lblk_t next, start = 0, end = 0;
  1629. ext4_lblk_t last = block + num;
  1630. int depth, exists, err = 0;
  1631. BUG_ON(func == NULL);
  1632. BUG_ON(inode == NULL);
  1633. while (block < last && block != EXT_MAX_BLOCKS) {
  1634. num = last - block;
  1635. /* find extent for this block */
  1636. down_read(&EXT4_I(inode)->i_data_sem);
  1637. path = ext4_ext_find_extent(inode, block, path);
  1638. up_read(&EXT4_I(inode)->i_data_sem);
  1639. if (IS_ERR(path)) {
  1640. err = PTR_ERR(path);
  1641. path = NULL;
  1642. break;
  1643. }
  1644. depth = ext_depth(inode);
  1645. if (unlikely(path[depth].p_hdr == NULL)) {
  1646. EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
  1647. err = -EIO;
  1648. break;
  1649. }
  1650. ex = path[depth].p_ext;
  1651. next = ext4_ext_next_allocated_block(path);
  1652. exists = 0;
  1653. if (!ex) {
  1654. /* there is no extent yet, so try to allocate
  1655. * all requested space */
  1656. start = block;
  1657. end = block + num;
  1658. } else if (le32_to_cpu(ex->ee_block) > block) {
  1659. /* need to allocate space before found extent */
  1660. start = block;
  1661. end = le32_to_cpu(ex->ee_block);
  1662. if (block + num < end)
  1663. end = block + num;
  1664. } else if (block >= le32_to_cpu(ex->ee_block)
  1665. + ext4_ext_get_actual_len(ex)) {
  1666. /* need to allocate space after found extent */
  1667. start = block;
  1668. end = block + num;
  1669. if (end >= next)
  1670. end = next;
  1671. } else if (block >= le32_to_cpu(ex->ee_block)) {
  1672. /*
  1673. * some part of requested space is covered
  1674. * by found extent
  1675. */
  1676. start = block;
  1677. end = le32_to_cpu(ex->ee_block)
  1678. + ext4_ext_get_actual_len(ex);
  1679. if (block + num < end)
  1680. end = block + num;
  1681. exists = 1;
  1682. } else {
  1683. BUG();
  1684. }
  1685. BUG_ON(end <= start);
  1686. if (!exists) {
  1687. cbex.ec_block = start;
  1688. cbex.ec_len = end - start;
  1689. cbex.ec_start = 0;
  1690. } else {
  1691. cbex.ec_block = le32_to_cpu(ex->ee_block);
  1692. cbex.ec_len = ext4_ext_get_actual_len(ex);
  1693. cbex.ec_start = ext4_ext_pblock(ex);
  1694. }
  1695. if (unlikely(cbex.ec_len == 0)) {
  1696. EXT4_ERROR_INODE(inode, "cbex.ec_len == 0");
  1697. err = -EIO;
  1698. break;
  1699. }
  1700. err = func(inode, next, &cbex, ex, cbdata);
  1701. ext4_ext_drop_refs(path);
  1702. if (err < 0)
  1703. break;
  1704. if (err == EXT_REPEAT)
  1705. continue;
  1706. else if (err == EXT_BREAK) {
  1707. err = 0;
  1708. break;
  1709. }
  1710. if (ext_depth(inode) != depth) {
  1711. /* depth was changed. we have to realloc path */
  1712. kfree(path);
  1713. path = NULL;
  1714. }
  1715. block = cbex.ec_block + cbex.ec_len;
  1716. }
  1717. if (path) {
  1718. ext4_ext_drop_refs(path);
  1719. kfree(path);
  1720. }
  1721. return err;
  1722. }
  1723. static void
  1724. ext4_ext_put_in_cache(struct inode *inode, ext4_lblk_t block,
  1725. __u32 len, ext4_fsblk_t start)
  1726. {
  1727. struct ext4_ext_cache *cex;
  1728. BUG_ON(len == 0);
  1729. spin_lock(&EXT4_I(inode)->i_block_reservation_lock);
  1730. cex = &EXT4_I(inode)->i_cached_extent;
  1731. cex->ec_block = block;
  1732. cex->ec_len = len;
  1733. cex->ec_start = start;
  1734. spin_unlock(&EXT4_I(inode)->i_block_reservation_lock);
  1735. }
  1736. /*
  1737. * ext4_ext_put_gap_in_cache:
  1738. * calculate boundaries of the gap that the requested block fits into
  1739. * and cache this gap
  1740. */
  1741. static void
  1742. ext4_ext_put_gap_in_cache(struct inode *inode, struct ext4_ext_path *path,
  1743. ext4_lblk_t block)
  1744. {
  1745. int depth = ext_depth(inode);
  1746. unsigned long len;
  1747. ext4_lblk_t lblock;
  1748. struct ext4_extent *ex;
  1749. ex = path[depth].p_ext;
  1750. if (ex == NULL) {
  1751. /* there is no extent yet, so gap is [0;-] */
  1752. lblock = 0;
  1753. len = EXT_MAX_BLOCKS;
  1754. ext_debug("cache gap(whole file):");
  1755. } else if (block < le32_to_cpu(ex->ee_block)) {
  1756. lblock = block;
  1757. len = le32_to_cpu(ex->ee_block) - block;
  1758. ext_debug("cache gap(before): %u [%u:%u]",
  1759. block,
  1760. le32_to_cpu(ex->ee_block),
  1761. ext4_ext_get_actual_len(ex));
  1762. } else if (block >= le32_to_cpu(ex->ee_block)
  1763. + ext4_ext_get_actual_len(ex)) {
  1764. ext4_lblk_t next;
  1765. lblock = le32_to_cpu(ex->ee_block)
  1766. + ext4_ext_get_actual_len(ex);
  1767. next = ext4_ext_next_allocated_block(path);
  1768. ext_debug("cache gap(after): [%u:%u] %u",
  1769. le32_to_cpu(ex->ee_block),
  1770. ext4_ext_get_actual_len(ex),
  1771. block);
  1772. BUG_ON(next == lblock);
  1773. len = next - lblock;
  1774. } else {
  1775. lblock = len = 0;
  1776. BUG();
  1777. }
  1778. ext_debug(" -> %u:%lu\n", lblock, len);
  1779. ext4_ext_put_in_cache(inode, lblock, len, 0);
  1780. }
  1781. /*
  1782. * ext4_ext_in_cache()
  1783. * Checks to see if the given block is in the cache.
  1784. * If it is, the cached extent is stored in the given
  1785. * cache extent pointer. If the cached extent is a hole,
  1786. * this routine should be used instead of
  1787. * ext4_ext_in_cache if the calling function needs to
  1788. * know the size of the hole.
  1789. *
  1790. * @inode: The files inode
  1791. * @block: The block to look for in the cache
  1792. * @ex: Pointer where the cached extent will be stored
  1793. * if it contains block
  1794. *
  1795. * Return 0 if cache is invalid; 1 if the cache is valid
  1796. */
  1797. static int ext4_ext_check_cache(struct inode *inode, ext4_lblk_t block,
  1798. struct ext4_ext_cache *ex){
  1799. struct ext4_ext_cache *cex;
  1800. struct ext4_sb_info *sbi;
  1801. int ret = 0;
  1802. /*
  1803. * We borrow i_block_reservation_lock to protect i_cached_extent
  1804. */
  1805. spin_lock(&EXT4_I(inode)->i_block_reservation_lock);
  1806. cex = &EXT4_I(inode)->i_cached_extent;
  1807. sbi = EXT4_SB(inode->i_sb);
  1808. /* has cache valid data? */
  1809. if (cex->ec_len == 0)
  1810. goto errout;
  1811. if (in_range(block, cex->ec_block, cex->ec_len)) {
  1812. memcpy(ex, cex, sizeof(struct ext4_ext_cache));
  1813. ext_debug("%u cached by %u:%u:%llu\n",
  1814. block,
  1815. cex->ec_block, cex->ec_len, cex->ec_start);
  1816. ret = 1;
  1817. }
  1818. errout:
  1819. if (!ret)
  1820. sbi->extent_cache_misses++;
  1821. else
  1822. sbi->extent_cache_hits++;
  1823. spin_unlock(&EXT4_I(inode)->i_block_reservation_lock);
  1824. return ret;
  1825. }
  1826. /*
  1827. * ext4_ext_in_cache()
  1828. * Checks to see if the given block is in the cache.
  1829. * If it is, the cached extent is stored in the given
  1830. * extent pointer.
  1831. *
  1832. * @inode: The files inode
  1833. * @block: The block to look for in the cache
  1834. * @ex: Pointer where the cached extent will be stored
  1835. * if it contains block
  1836. *
  1837. * Return 0 if cache is invalid; 1 if the cache is valid
  1838. */
  1839. static int
  1840. ext4_ext_in_cache(struct inode *inode, ext4_lblk_t block,
  1841. struct ext4_extent *ex)
  1842. {
  1843. struct ext4_ext_cache cex;
  1844. int ret = 0;
  1845. if (ext4_ext_check_cache(inode, block, &cex)) {
  1846. ex->ee_block = cpu_to_le32(cex.ec_block);
  1847. ext4_ext_store_pblock(ex, cex.ec_start);
  1848. ex->ee_len = cpu_to_le16(cex.ec_len);
  1849. ret = 1;
  1850. }
  1851. return ret;
  1852. }
  1853. /*
  1854. * ext4_ext_rm_idx:
  1855. * removes index from the index block.
  1856. * It's used in truncate case only, thus all requests are for
  1857. * last index in the block only.
  1858. */
  1859. static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
  1860. struct ext4_ext_path *path)
  1861. {
  1862. int err;
  1863. ext4_fsblk_t leaf;
  1864. /* free index block */
  1865. path--;
  1866. leaf = ext4_idx_pblock(path->p_idx);
  1867. if (unlikely(path->p_hdr->eh_entries == 0)) {
  1868. EXT4_ERROR_INODE(inode, "path->p_hdr->eh_entries == 0");
  1869. return -EIO;
  1870. }
  1871. err = ext4_ext_get_access(handle, inode, path);
  1872. if (err)
  1873. return err;
  1874. le16_add_cpu(&path->p_hdr->eh_entries, -1);
  1875. err = ext4_ext_dirty(handle, inode, path);
  1876. if (err)
  1877. return err;
  1878. ext_debug("index is empty, remove it, free block %llu\n", leaf);
  1879. ext4_free_blocks(handle, inode, NULL, leaf, 1,
  1880. EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
  1881. return err;
  1882. }
  1883. /*
  1884. * ext4_ext_calc_credits_for_single_extent:
  1885. * This routine returns max. credits that needed to insert an extent
  1886. * to the extent tree.
  1887. * When pass the actual path, the caller should calculate credits
  1888. * under i_data_sem.
  1889. */
  1890. int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
  1891. struct ext4_ext_path *path)
  1892. {
  1893. if (path) {
  1894. int depth = ext_depth(inode);
  1895. int ret = 0;
  1896. /* probably there is space in leaf? */
  1897. if (le16_to_cpu(path[depth].p_hdr->eh_entries)
  1898. < le16_to_cpu(path[depth].p_hdr->eh_max)) {
  1899. /*
  1900. * There are some space in the leaf tree, no
  1901. * need to account for leaf block credit
  1902. *
  1903. * bitmaps and block group descriptor blocks
  1904. * and other metadat blocks still need to be
  1905. * accounted.
  1906. */
  1907. /* 1 bitmap, 1 block group descriptor */
  1908. ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
  1909. return ret;
  1910. }
  1911. }
  1912. return ext4_chunk_trans_blocks(inode, nrblocks);
  1913. }
  1914. /*
  1915. * How many index/leaf blocks need to change/allocate to modify nrblocks?
  1916. *
  1917. * if nrblocks are fit in a single extent (chunk flag is 1), then
  1918. * in the worse case, each tree level index/leaf need to be changed
  1919. * if the tree split due to insert a new extent, then the old tree
  1920. * index/leaf need to be updated too
  1921. *
  1922. * If the nrblocks are discontiguous, they could cause
  1923. * the whole tree split more than once, but this is really rare.
  1924. */
  1925. int ext4_ext_index_trans_blocks(struct inode *inode, int nrblocks, int chunk)
  1926. {
  1927. int index;
  1928. int depth = ext_depth(inode);
  1929. if (chunk)
  1930. index = depth * 2;
  1931. else
  1932. index = depth * 3;
  1933. return index;
  1934. }
  1935. static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
  1936. struct ext4_extent *ex,
  1937. ext4_lblk_t from, ext4_lblk_t to)
  1938. {
  1939. unsigned short ee_len = ext4_ext_get_actual_len(ex);
  1940. int flags = EXT4_FREE_BLOCKS_FORGET;
  1941. if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
  1942. flags |= EXT4_FREE_BLOCKS_METADATA;
  1943. #ifdef EXTENTS_STATS
  1944. {
  1945. struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  1946. spin_lock(&sbi->s_ext_stats_lock);
  1947. sbi->s_ext_blocks += ee_len;
  1948. sbi->s_ext_extents++;
  1949. if (ee_len < sbi->s_ext_min)
  1950. sbi->s_ext_min = ee_len;
  1951. if (ee_len > sbi->s_ext_max)
  1952. sbi->s_ext_max = ee_len;
  1953. if (ext_depth(inode) > sbi->s_depth_max)
  1954. sbi->s_depth_max = ext_depth(inode);
  1955. spin_unlock(&sbi->s_ext_stats_lock);
  1956. }
  1957. #endif
  1958. if (from >= le32_to_cpu(ex->ee_block)
  1959. && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
  1960. /* tail removal */
  1961. ext4_lblk_t num;
  1962. ext4_fsblk_t start;
  1963. num = le32_to_cpu(ex->ee_block) + ee_len - from;
  1964. start = ext4_ext_pblock(ex) + ee_len - num;
  1965. ext_debug("free last %u blocks starting %llu\n", num, start);
  1966. ext4_free_blocks(handle, inode, NULL, start, num, flags);
  1967. } else if (from == le32_to_cpu(ex->ee_block)
  1968. && to <= le32_to_cpu(ex->ee_block) + ee_len - 1) {
  1969. /* head removal */
  1970. ext4_lblk_t num;
  1971. ext4_fsblk_t start;
  1972. num = to - from;
  1973. start = ext4_ext_pblock(ex);
  1974. ext_debug("free first %u blocks starting %llu\n", num, start);
  1975. ext4_free_blocks(handle, inode, 0, start, num, flags);
  1976. } else {
  1977. printk(KERN_INFO "strange request: removal(2) "
  1978. "%u-%u from %u:%u\n",
  1979. from, to, le32_to_cpu(ex->ee_block), ee_len);
  1980. }
  1981. return 0;
  1982. }
  1983. /*
  1984. * ext4_ext_rm_leaf() Removes the extents associated with the
  1985. * blocks appearing between "start" and "end", and splits the extents
  1986. * if "start" and "end" appear in the same extent
  1987. *
  1988. * @handle: The journal handle
  1989. * @inode: The files inode
  1990. * @path: The path to the leaf
  1991. * @start: The first block to remove
  1992. * @end: The last block to remove
  1993. */
  1994. static int
  1995. ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
  1996. struct ext4_ext_path *path, ext4_lblk_t start,
  1997. ext4_lblk_t end)
  1998. {
  1999. int err = 0, correct_index = 0;
  2000. int depth = ext_depth(inode), credits;
  2001. struct ext4_extent_header *eh;
  2002. ext4_lblk_t a, b, block;
  2003. unsigned num;
  2004. ext4_lblk_t ex_ee_block;
  2005. unsigned short ex_ee_len;
  2006. unsigned uninitialized = 0;
  2007. struct ext4_extent *ex;
  2008. struct ext4_map_blocks map;
  2009. /* the header must be checked already in ext4_ext_remove_space() */
  2010. ext_debug("truncate since %u in leaf\n", start);
  2011. if (!path[depth].p_hdr)
  2012. path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
  2013. eh = path[depth].p_hdr;
  2014. if (unlikely(path[depth].p_hdr == NULL)) {
  2015. EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
  2016. return -EIO;
  2017. }
  2018. /* find where to start removing */
  2019. ex = EXT_LAST_EXTENT(eh);
  2020. ex_ee_block = le32_to_cpu(ex->ee_block);
  2021. ex_ee_len = ext4_ext_get_actual_len(ex);
  2022. while (ex >= EXT_FIRST_EXTENT(eh) &&
  2023. ex_ee_block + ex_ee_len > start) {
  2024. if (ext4_ext_is_uninitialized(ex))
  2025. uninitialized = 1;
  2026. else
  2027. uninitialized = 0;
  2028. ext_debug("remove ext %u:[%d]%d\n", ex_ee_block,
  2029. uninitialized, ex_ee_len);
  2030. path[depth].p_ext = ex;
  2031. a = ex_ee_block > start ? ex_ee_block : start;
  2032. b = ex_ee_block+ex_ee_len - 1 < end ?
  2033. ex_ee_block+ex_ee_len - 1 : end;
  2034. ext_debug(" border %u:%u\n", a, b);
  2035. /* If this extent is beyond the end of the hole, skip it */
  2036. if (end <= ex_ee_block) {
  2037. ex--;
  2038. ex_ee_block = le32_to_cpu(ex->ee_block);
  2039. ex_ee_len = ext4_ext_get_actual_len(ex);
  2040. continue;
  2041. } else if (a != ex_ee_block &&
  2042. b != ex_ee_block + ex_ee_len - 1) {
  2043. /*
  2044. * If this is a truncate, then this condition should
  2045. * never happen because at least one of the end points
  2046. * needs to be on the edge of the extent.
  2047. */
  2048. if (end == EXT_MAX_BLOCKS - 1) {
  2049. ext_debug(" bad truncate %u:%u\n",
  2050. start, end);
  2051. block = 0;
  2052. num = 0;
  2053. err = -EIO;
  2054. goto out;
  2055. }
  2056. /*
  2057. * else this is a hole punch, so the extent needs to
  2058. * be split since neither edge of the hole is on the
  2059. * extent edge
  2060. */
  2061. else{
  2062. map.m_pblk = ext4_ext_pblock(ex);
  2063. map.m_lblk = ex_ee_block;
  2064. map.m_len = b - ex_ee_block;
  2065. err = ext4_split_extent(handle,
  2066. inode, path, &map, 0,
  2067. EXT4_GET_BLOCKS_PUNCH_OUT_EXT |
  2068. EXT4_GET_BLOCKS_PRE_IO);
  2069. if (err < 0)
  2070. goto out;
  2071. ex_ee_len = ext4_ext_get_actual_len(ex);
  2072. b = ex_ee_block+ex_ee_len - 1 < end ?
  2073. ex_ee_block+ex_ee_len - 1 : end;
  2074. /* Then remove tail of this extent */
  2075. block = ex_ee_block;
  2076. num = a - block;
  2077. }
  2078. } else if (a != ex_ee_block) {
  2079. /* remove tail of the extent */
  2080. block = ex_ee_block;
  2081. num = a - block;
  2082. } else if (b != ex_ee_block + ex_ee_len - 1) {
  2083. /* remove head of the extent */
  2084. block = b;
  2085. num = ex_ee_block + ex_ee_len - b;
  2086. /*
  2087. * If this is a truncate, this condition
  2088. * should never happen
  2089. */
  2090. if (end == EXT_MAX_BLOCKS - 1) {
  2091. ext_debug(" bad truncate %u:%u\n",
  2092. start, end);
  2093. err = -EIO;
  2094. goto out;
  2095. }
  2096. } else {
  2097. /* remove whole extent: excellent! */
  2098. block = ex_ee_block;
  2099. num = 0;
  2100. if (a != ex_ee_block) {
  2101. ext_debug(" bad truncate %u:%u\n",
  2102. start, end);
  2103. err = -EIO;
  2104. goto out;
  2105. }
  2106. if (b != ex_ee_block + ex_ee_len - 1) {
  2107. ext_debug(" bad truncate %u:%u\n",
  2108. start, end);
  2109. err = -EIO;
  2110. goto out;
  2111. }
  2112. }
  2113. /*
  2114. * 3 for leaf, sb, and inode plus 2 (bmap and group
  2115. * descriptor) for each block group; assume two block
  2116. * groups plus ex_ee_len/blocks_per_block_group for
  2117. * the worst case
  2118. */
  2119. credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
  2120. if (ex == EXT_FIRST_EXTENT(eh)) {
  2121. correct_index = 1;
  2122. credits += (ext_depth(inode)) + 1;
  2123. }
  2124. credits += EXT4_MAXQUOTAS_TRANS_BLOCKS(inode->i_sb);
  2125. err = ext4_ext_truncate_extend_restart(handle, inode, credits);
  2126. if (err)
  2127. goto out;
  2128. err = ext4_ext_get_access(handle, inode, path + depth);
  2129. if (err)
  2130. goto out;
  2131. err = ext4_remove_blocks(handle, inode, ex, a, b);
  2132. if (err)
  2133. goto out;
  2134. if (num == 0) {
  2135. /* this extent is removed; mark slot entirely unused */
  2136. ext4_ext_store_pblock(ex, 0);
  2137. } else if (block != ex_ee_block) {
  2138. /*
  2139. * If this was a head removal, then we need to update
  2140. * the physical block since it is now at a different
  2141. * location
  2142. */
  2143. ext4_ext_store_pblock(ex, ext4_ext_pblock(ex) + (b-a));
  2144. }
  2145. ex->ee_block = cpu_to_le32(block);
  2146. ex->ee_len = cpu_to_le16(num);
  2147. /*
  2148. * Do not mark uninitialized if all the blocks in the
  2149. * extent have been removed.
  2150. */
  2151. if (uninitialized && num)
  2152. ext4_ext_mark_uninitialized(ex);
  2153. err = ext4_ext_dirty(handle, inode, path + depth);
  2154. if (err)
  2155. goto out;
  2156. /*
  2157. * If the extent was completely released,
  2158. * we need to remove it from the leaf
  2159. */
  2160. if (num == 0) {
  2161. if (end != EXT_MAX_BLOCKS - 1) {
  2162. /*
  2163. * For hole punching, we need to scoot all the
  2164. * extents up when an extent is removed so that
  2165. * we dont have blank extents in the middle
  2166. */
  2167. memmove(ex, ex+1, (EXT_LAST_EXTENT(eh) - ex) *
  2168. sizeof(struct ext4_extent));
  2169. /* Now get rid of the one at the end */
  2170. memset(EXT_LAST_EXTENT(eh), 0,
  2171. sizeof(struct ext4_extent));
  2172. }
  2173. le16_add_cpu(&eh->eh_entries, -1);
  2174. }
  2175. ext_debug("new extent: %u:%u:%llu\n", block, num,
  2176. ext4_ext_pblock(ex));
  2177. ex--;
  2178. ex_ee_block = le32_to_cpu(ex->ee_block);
  2179. ex_ee_len = ext4_ext_get_actual_len(ex);
  2180. }
  2181. if (correct_index && eh->eh_entries)
  2182. err = ext4_ext_correct_indexes(handle, inode, path);
  2183. /* if this leaf is free, then we should
  2184. * remove it from index block above */
  2185. if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
  2186. err = ext4_ext_rm_idx(handle, inode, path + depth);
  2187. out:
  2188. return err;
  2189. }
  2190. /*
  2191. * ext4_ext_more_to_rm:
  2192. * returns 1 if current index has to be freed (even partial)
  2193. */
  2194. static int
  2195. ext4_ext_more_to_rm(struct ext4_ext_path *path)
  2196. {
  2197. BUG_ON(path->p_idx == NULL);
  2198. if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
  2199. return 0;
  2200. /*
  2201. * if truncate on deeper level happened, it wasn't partial,
  2202. * so we have to consider current index for truncation
  2203. */
  2204. if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
  2205. return 0;
  2206. return 1;
  2207. }
  2208. static int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start,
  2209. ext4_lblk_t end)
  2210. {
  2211. struct super_block *sb = inode->i_sb;
  2212. int depth = ext_depth(inode);
  2213. struct ext4_ext_path *path;
  2214. handle_t *handle;
  2215. int i, err;
  2216. ext_debug("truncate since %u\n", start);
  2217. /* probably first extent we're gonna free will be last in block */
  2218. handle = ext4_journal_start(inode, depth + 1);
  2219. if (IS_ERR(handle))
  2220. return PTR_ERR(handle);
  2221. again:
  2222. ext4_ext_invalidate_cache(inode);
  2223. /*
  2224. * We start scanning from right side, freeing all the blocks
  2225. * after i_size and walking into the tree depth-wise.
  2226. */
  2227. depth = ext_depth(inode);
  2228. path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1), GFP_NOFS);
  2229. if (path == NULL) {
  2230. ext4_journal_stop(handle);
  2231. return -ENOMEM;
  2232. }
  2233. path[0].p_depth = depth;
  2234. path[0].p_hdr = ext_inode_hdr(inode);
  2235. if (ext4_ext_check(inode, path[0].p_hdr, depth)) {
  2236. err = -EIO;
  2237. goto out;
  2238. }
  2239. i = err = 0;
  2240. while (i >= 0 && err == 0) {
  2241. if (i == depth) {
  2242. /* this is leaf block */
  2243. err = ext4_ext_rm_leaf(handle, inode, path,
  2244. start, end);
  2245. /* root level has p_bh == NULL, brelse() eats this */
  2246. brelse(path[i].p_bh);
  2247. path[i].p_bh = NULL;
  2248. i--;
  2249. continue;
  2250. }
  2251. /* this is index block */
  2252. if (!path[i].p_hdr) {
  2253. ext_debug("initialize header\n");
  2254. path[i].p_hdr = ext_block_hdr(path[i].p_bh);
  2255. }
  2256. if (!path[i].p_idx) {
  2257. /* this level hasn't been touched yet */
  2258. path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
  2259. path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
  2260. ext_debug("init index ptr: hdr 0x%p, num %d\n",
  2261. path[i].p_hdr,
  2262. le16_to_cpu(path[i].p_hdr->eh_entries));
  2263. } else {
  2264. /* we were already here, see at next index */
  2265. path[i].p_idx--;
  2266. }
  2267. ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
  2268. i, EXT_FIRST_INDEX(path[i].p_hdr),
  2269. path[i].p_idx);
  2270. if (ext4_ext_more_to_rm(path + i)) {
  2271. struct buffer_head *bh;
  2272. /* go to the next level */
  2273. ext_debug("move to level %d (block %llu)\n",
  2274. i + 1, ext4_idx_pblock(path[i].p_idx));
  2275. memset(path + i + 1, 0, sizeof(*path));
  2276. bh = sb_bread(sb, ext4_idx_pblock(path[i].p_idx));
  2277. if (!bh) {
  2278. /* should we reset i_size? */
  2279. err = -EIO;
  2280. break;
  2281. }
  2282. if (WARN_ON(i + 1 > depth)) {
  2283. err = -EIO;
  2284. break;
  2285. }
  2286. if (ext4_ext_check(inode, ext_block_hdr(bh),
  2287. depth - i - 1)) {
  2288. err = -EIO;
  2289. break;
  2290. }
  2291. path[i + 1].p_bh = bh;
  2292. /* save actual number of indexes since this
  2293. * number is changed at the next iteration */
  2294. path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
  2295. i++;
  2296. } else {
  2297. /* we finished processing this index, go up */
  2298. if (path[i].p_hdr->eh_entries == 0 && i > 0) {
  2299. /* index is empty, remove it;
  2300. * handle must be already prepared by the
  2301. * truncatei_leaf() */
  2302. err = ext4_ext_rm_idx(handle, inode, path + i);
  2303. }
  2304. /* root level has p_bh == NULL, brelse() eats this */
  2305. brelse(path[i].p_bh);
  2306. path[i].p_bh = NULL;
  2307. i--;
  2308. ext_debug("return to level %d\n", i);
  2309. }
  2310. }
  2311. /* TODO: flexible tree reduction should be here */
  2312. if (path->p_hdr->eh_entries == 0) {
  2313. /*
  2314. * truncate to zero freed all the tree,
  2315. * so we need to correct eh_depth
  2316. */
  2317. err = ext4_ext_get_access(handle, inode, path);
  2318. if (err == 0) {
  2319. ext_inode_hdr(inode)->eh_depth = 0;
  2320. ext_inode_hdr(inode)->eh_max =
  2321. cpu_to_le16(ext4_ext_space_root(inode, 0));
  2322. err = ext4_ext_dirty(handle, inode, path);
  2323. }
  2324. }
  2325. out:
  2326. ext4_ext_drop_refs(path);
  2327. kfree(path);
  2328. if (err == -EAGAIN)
  2329. goto again;
  2330. ext4_journal_stop(handle);
  2331. return err;
  2332. }
  2333. /*
  2334. * called at mount time
  2335. */
  2336. void ext4_ext_init(struct super_block *sb)
  2337. {
  2338. /*
  2339. * possible initialization would be here
  2340. */
  2341. if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
  2342. #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
  2343. printk(KERN_INFO "EXT4-fs: file extents enabled");
  2344. #ifdef AGGRESSIVE_TEST
  2345. printk(", aggressive tests");
  2346. #endif
  2347. #ifdef CHECK_BINSEARCH
  2348. printk(", check binsearch");
  2349. #endif
  2350. #ifdef EXTENTS_STATS
  2351. printk(", stats");
  2352. #endif
  2353. printk("\n");
  2354. #endif
  2355. #ifdef EXTENTS_STATS
  2356. spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
  2357. EXT4_SB(sb)->s_ext_min = 1 << 30;
  2358. EXT4_SB(sb)->s_ext_max = 0;
  2359. #endif
  2360. }
  2361. }
  2362. /*
  2363. * called at umount time
  2364. */
  2365. void ext4_ext_release(struct super_block *sb)
  2366. {
  2367. if (!EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS))
  2368. return;
  2369. #ifdef EXTENTS_STATS
  2370. if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
  2371. struct ext4_sb_info *sbi = EXT4_SB(sb);
  2372. printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
  2373. sbi->s_ext_blocks, sbi->s_ext_extents,
  2374. sbi->s_ext_blocks / sbi->s_ext_extents);
  2375. printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
  2376. sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
  2377. }
  2378. #endif
  2379. }
  2380. /* FIXME!! we need to try to merge to left or right after zero-out */
  2381. static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
  2382. {
  2383. ext4_fsblk_t ee_pblock;
  2384. unsigned int ee_len;
  2385. int ret;
  2386. ee_len = ext4_ext_get_actual_len(ex);
  2387. ee_pblock = ext4_ext_pblock(ex);
  2388. ret = sb_issue_zeroout(inode->i_sb, ee_pblock, ee_len, GFP_NOFS);
  2389. if (ret > 0)
  2390. ret = 0;
  2391. return ret;
  2392. }
  2393. /*
  2394. * used by extent splitting.
  2395. */
  2396. #define EXT4_EXT_MAY_ZEROOUT 0x1 /* safe to zeroout if split fails \
  2397. due to ENOSPC */
  2398. #define EXT4_EXT_MARK_UNINIT1 0x2 /* mark first half uninitialized */
  2399. #define EXT4_EXT_MARK_UNINIT2 0x4 /* mark second half uninitialized */
  2400. /*
  2401. * ext4_split_extent_at() splits an extent at given block.
  2402. *
  2403. * @handle: the journal handle
  2404. * @inode: the file inode
  2405. * @path: the path to the extent
  2406. * @split: the logical block where the extent is splitted.
  2407. * @split_flags: indicates if the extent could be zeroout if split fails, and
  2408. * the states(init or uninit) of new extents.
  2409. * @flags: flags used to insert new extent to extent tree.
  2410. *
  2411. *
  2412. * Splits extent [a, b] into two extents [a, @split) and [@split, b], states
  2413. * of which are deterimined by split_flag.
  2414. *
  2415. * There are two cases:
  2416. * a> the extent are splitted into two extent.
  2417. * b> split is not needed, and just mark the extent.
  2418. *
  2419. * return 0 on success.
  2420. */
  2421. static int ext4_split_extent_at(handle_t *handle,
  2422. struct inode *inode,
  2423. struct ext4_ext_path *path,
  2424. ext4_lblk_t split,
  2425. int split_flag,
  2426. int flags)
  2427. {
  2428. ext4_fsblk_t newblock;
  2429. ext4_lblk_t ee_block;
  2430. struct ext4_extent *ex, newex, orig_ex;
  2431. struct ext4_extent *ex2 = NULL;
  2432. unsigned int ee_len, depth;
  2433. int err = 0;
  2434. ext_debug("ext4_split_extents_at: inode %lu, logical"
  2435. "block %llu\n", inode->i_ino, (unsigned long long)split);
  2436. ext4_ext_show_leaf(inode, path);
  2437. depth = ext_depth(inode);
  2438. ex = path[depth].p_ext;
  2439. ee_block = le32_to_cpu(ex->ee_block);
  2440. ee_len = ext4_ext_get_actual_len(ex);
  2441. newblock = split - ee_block + ext4_ext_pblock(ex);
  2442. BUG_ON(split < ee_block || split >= (ee_block + ee_len));
  2443. err = ext4_ext_get_access(handle, inode, path + depth);
  2444. if (err)
  2445. goto out;
  2446. if (split == ee_block) {
  2447. /*
  2448. * case b: block @split is the block that the extent begins with
  2449. * then we just change the state of the extent, and splitting
  2450. * is not needed.
  2451. */
  2452. if (split_flag & EXT4_EXT_MARK_UNINIT2)
  2453. ext4_ext_mark_uninitialized(ex);
  2454. else
  2455. ext4_ext_mark_initialized(ex);
  2456. if (!(flags & EXT4_GET_BLOCKS_PRE_IO))
  2457. ext4_ext_try_to_merge(inode, path, ex);
  2458. err = ext4_ext_dirty(handle, inode, path + depth);
  2459. goto out;
  2460. }
  2461. /* case a */
  2462. memcpy(&orig_ex, ex, sizeof(orig_ex));
  2463. ex->ee_len = cpu_to_le16(split - ee_block);
  2464. if (split_flag & EXT4_EXT_MARK_UNINIT1)
  2465. ext4_ext_mark_uninitialized(ex);
  2466. /*
  2467. * path may lead to new leaf, not to original leaf any more
  2468. * after ext4_ext_insert_extent() returns,
  2469. */
  2470. err = ext4_ext_dirty(handle, inode, path + depth);
  2471. if (err)
  2472. goto fix_extent_len;
  2473. ex2 = &newex;
  2474. ex2->ee_block = cpu_to_le32(split);
  2475. ex2->ee_len = cpu_to_le16(ee_len - (split - ee_block));
  2476. ext4_ext_store_pblock(ex2, newblock);
  2477. if (split_flag & EXT4_EXT_MARK_UNINIT2)
  2478. ext4_ext_mark_uninitialized(ex2);
  2479. err = ext4_ext_insert_extent(handle, inode, path, &newex, flags);
  2480. if (err == -ENOSPC && (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
  2481. err = ext4_ext_zeroout(inode, &orig_ex);
  2482. if (err)
  2483. goto fix_extent_len;
  2484. /* update the extent length and mark as initialized */
  2485. ex->ee_len = cpu_to_le32(ee_len);
  2486. ext4_ext_try_to_merge(inode, path, ex);
  2487. err = ext4_ext_dirty(handle, inode, path + depth);
  2488. goto out;
  2489. } else if (err)
  2490. goto fix_extent_len;
  2491. out:
  2492. ext4_ext_show_leaf(inode, path);
  2493. return err;
  2494. fix_extent_len:
  2495. ex->ee_len = orig_ex.ee_len;
  2496. ext4_ext_dirty(handle, inode, path + depth);
  2497. return err;
  2498. }
  2499. /*
  2500. * ext4_split_extents() splits an extent and mark extent which is covered
  2501. * by @map as split_flags indicates
  2502. *
  2503. * It may result in splitting the extent into multiple extents (upto three)
  2504. * There are three possibilities:
  2505. * a> There is no split required
  2506. * b> Splits in two extents: Split is happening at either end of the extent
  2507. * c> Splits in three extents: Somone is splitting in middle of the extent
  2508. *
  2509. */
  2510. static int ext4_split_extent(handle_t *handle,
  2511. struct inode *inode,
  2512. struct ext4_ext_path *path,
  2513. struct ext4_map_blocks *map,
  2514. int split_flag,
  2515. int flags)
  2516. {
  2517. ext4_lblk_t ee_block;
  2518. struct ext4_extent *ex;
  2519. unsigned int ee_len, depth;
  2520. int err = 0;
  2521. int uninitialized;
  2522. int split_flag1, flags1;
  2523. depth = ext_depth(inode);
  2524. ex = path[depth].p_ext;
  2525. ee_block = le32_to_cpu(ex->ee_block);
  2526. ee_len = ext4_ext_get_actual_len(ex);
  2527. uninitialized = ext4_ext_is_uninitialized(ex);
  2528. if (map->m_lblk + map->m_len < ee_block + ee_len) {
  2529. split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT ?
  2530. EXT4_EXT_MAY_ZEROOUT : 0;
  2531. flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;
  2532. if (uninitialized)
  2533. split_flag1 |= EXT4_EXT_MARK_UNINIT1 |
  2534. EXT4_EXT_MARK_UNINIT2;
  2535. err = ext4_split_extent_at(handle, inode, path,
  2536. map->m_lblk + map->m_len, split_flag1, flags1);
  2537. if (err)
  2538. goto out;
  2539. }
  2540. ext4_ext_drop_refs(path);
  2541. path = ext4_ext_find_extent(inode, map->m_lblk, path);
  2542. if (IS_ERR(path))
  2543. return PTR_ERR(path);
  2544. if (map->m_lblk >= ee_block) {
  2545. split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT ?
  2546. EXT4_EXT_MAY_ZEROOUT : 0;
  2547. if (uninitialized)
  2548. split_flag1 |= EXT4_EXT_MARK_UNINIT1;
  2549. if (split_flag & EXT4_EXT_MARK_UNINIT2)
  2550. split_flag1 |= EXT4_EXT_MARK_UNINIT2;
  2551. err = ext4_split_extent_at(handle, inode, path,
  2552. map->m_lblk, split_flag1, flags);
  2553. if (err)
  2554. goto out;
  2555. }
  2556. ext4_ext_show_leaf(inode, path);
  2557. out:
  2558. return err ? err : map->m_len;
  2559. }
  2560. #define EXT4_EXT_ZERO_LEN 7
  2561. /*
  2562. * This function is called by ext4_ext_map_blocks() if someone tries to write
  2563. * to an uninitialized extent. It may result in splitting the uninitialized
  2564. * extent into multiple extents (up to three - one initialized and two
  2565. * uninitialized).
  2566. * There are three possibilities:
  2567. * a> There is no split required: Entire extent should be initialized
  2568. * b> Splits in two extents: Write is happening at either end of the extent
  2569. * c> Splits in three extents: Somone is writing in middle of the extent
  2570. */
  2571. static int ext4_ext_convert_to_initialized(handle_t *handle,
  2572. struct inode *inode,
  2573. struct ext4_map_blocks *map,
  2574. struct ext4_ext_path *path)
  2575. {
  2576. struct ext4_map_blocks split_map;
  2577. struct ext4_extent zero_ex;
  2578. struct ext4_extent *ex;
  2579. ext4_lblk_t ee_block, eof_block;
  2580. unsigned int allocated, ee_len, depth;
  2581. int err = 0;
  2582. int split_flag = 0;
  2583. ext_debug("ext4_ext_convert_to_initialized: inode %lu, logical"
  2584. "block %llu, max_blocks %u\n", inode->i_ino,
  2585. (unsigned long long)map->m_lblk, map->m_len);
  2586. eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
  2587. inode->i_sb->s_blocksize_bits;
  2588. if (eof_block < map->m_lblk + map->m_len)
  2589. eof_block = map->m_lblk + map->m_len;
  2590. depth = ext_depth(inode);
  2591. ex = path[depth].p_ext;
  2592. ee_block = le32_to_cpu(ex->ee_block);
  2593. ee_len = ext4_ext_get_actual_len(ex);
  2594. allocated = ee_len - (map->m_lblk - ee_block);
  2595. WARN_ON(map->m_lblk < ee_block);
  2596. /*
  2597. * It is safe to convert extent to initialized via explicit
  2598. * zeroout only if extent is fully insde i_size or new_size.
  2599. */
  2600. split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
  2601. /* If extent has less than 2*EXT4_EXT_ZERO_LEN zerout directly */
  2602. if (ee_len <= 2*EXT4_EXT_ZERO_LEN &&
  2603. (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
  2604. err = ext4_ext_zeroout(inode, ex);
  2605. if (err)
  2606. goto out;
  2607. err = ext4_ext_get_access(handle, inode, path + depth);
  2608. if (err)
  2609. goto out;
  2610. ext4_ext_mark_initialized(ex);
  2611. ext4_ext_try_to_merge(inode, path, ex);
  2612. err = ext4_ext_dirty(handle, inode, path + depth);
  2613. goto out;
  2614. }
  2615. /*
  2616. * four cases:
  2617. * 1. split the extent into three extents.
  2618. * 2. split the extent into two extents, zeroout the first half.
  2619. * 3. split the extent into two extents, zeroout the second half.
  2620. * 4. split the extent into two extents with out zeroout.
  2621. */
  2622. split_map.m_lblk = map->m_lblk;
  2623. split_map.m_len = map->m_len;
  2624. if (allocated > map->m_len) {
  2625. if (allocated <= EXT4_EXT_ZERO_LEN &&
  2626. (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
  2627. /* case 3 */
  2628. zero_ex.ee_block =
  2629. cpu_to_le32(map->m_lblk);
  2630. zero_ex.ee_len = cpu_to_le16(allocated);
  2631. ext4_ext_store_pblock(&zero_ex,
  2632. ext4_ext_pblock(ex) + map->m_lblk - ee_block);
  2633. err = ext4_ext_zeroout(inode, &zero_ex);
  2634. if (err)
  2635. goto out;
  2636. split_map.m_lblk = map->m_lblk;
  2637. split_map.m_len = allocated;
  2638. } else if ((map->m_lblk - ee_block + map->m_len <
  2639. EXT4_EXT_ZERO_LEN) &&
  2640. (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
  2641. /* case 2 */
  2642. if (map->m_lblk != ee_block) {
  2643. zero_ex.ee_block = ex->ee_block;
  2644. zero_ex.ee_len = cpu_to_le16(map->m_lblk -
  2645. ee_block);
  2646. ext4_ext_store_pblock(&zero_ex,
  2647. ext4_ext_pblock(ex));
  2648. err = ext4_ext_zeroout(inode, &zero_ex);
  2649. if (err)
  2650. goto out;
  2651. }
  2652. split_map.m_lblk = ee_block;
  2653. split_map.m_len = map->m_lblk - ee_block + map->m_len;
  2654. allocated = map->m_len;
  2655. }
  2656. }
  2657. allocated = ext4_split_extent(handle, inode, path,
  2658. &split_map, split_flag, 0);
  2659. if (allocated < 0)
  2660. err = allocated;
  2661. out:
  2662. return err ? err : allocated;
  2663. }
  2664. /*
  2665. * This function is called by ext4_ext_map_blocks() from
  2666. * ext4_get_blocks_dio_write() when DIO to write
  2667. * to an uninitialized extent.
  2668. *
  2669. * Writing to an uninitialized extent may result in splitting the uninitialized
  2670. * extent into multiple /initialized uninitialized extents (up to three)
  2671. * There are three possibilities:
  2672. * a> There is no split required: Entire extent should be uninitialized
  2673. * b> Splits in two extents: Write is happening at either end of the extent
  2674. * c> Splits in three extents: Somone is writing in middle of the extent
  2675. *
  2676. * One of more index blocks maybe needed if the extent tree grow after
  2677. * the uninitialized extent split. To prevent ENOSPC occur at the IO
  2678. * complete, we need to split the uninitialized extent before DIO submit
  2679. * the IO. The uninitialized extent called at this time will be split
  2680. * into three uninitialized extent(at most). After IO complete, the part
  2681. * being filled will be convert to initialized by the end_io callback function
  2682. * via ext4_convert_unwritten_extents().
  2683. *
  2684. * Returns the size of uninitialized extent to be written on success.
  2685. */
  2686. static int ext4_split_unwritten_extents(handle_t *handle,
  2687. struct inode *inode,
  2688. struct ext4_map_blocks *map,
  2689. struct ext4_ext_path *path,
  2690. int flags)
  2691. {
  2692. ext4_lblk_t eof_block;
  2693. ext4_lblk_t ee_block;
  2694. struct ext4_extent *ex;
  2695. unsigned int ee_len;
  2696. int split_flag = 0, depth;
  2697. ext_debug("ext4_split_unwritten_extents: inode %lu, logical"
  2698. "block %llu, max_blocks %u\n", inode->i_ino,
  2699. (unsigned long long)map->m_lblk, map->m_len);
  2700. eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
  2701. inode->i_sb->s_blocksize_bits;
  2702. if (eof_block < map->m_lblk + map->m_len)
  2703. eof_block = map->m_lblk + map->m_len;
  2704. /*
  2705. * It is safe to convert extent to initialized via explicit
  2706. * zeroout only if extent is fully insde i_size or new_size.
  2707. */
  2708. depth = ext_depth(inode);
  2709. ex = path[depth].p_ext;
  2710. ee_block = le32_to_cpu(ex->ee_block);
  2711. ee_len = ext4_ext_get_actual_len(ex);
  2712. split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
  2713. split_flag |= EXT4_EXT_MARK_UNINIT2;
  2714. flags |= EXT4_GET_BLOCKS_PRE_IO;
  2715. return ext4_split_extent(handle, inode, path, map, split_flag, flags);
  2716. }
  2717. static int ext4_convert_unwritten_extents_endio(handle_t *handle,
  2718. struct inode *inode,
  2719. struct ext4_ext_path *path)
  2720. {
  2721. struct ext4_extent *ex;
  2722. int depth;
  2723. int err = 0;
  2724. depth = ext_depth(inode);
  2725. ex = path[depth].p_ext;
  2726. ext_debug("ext4_convert_unwritten_extents_endio: inode %lu, logical"
  2727. "block %llu, max_blocks %u\n", inode->i_ino,
  2728. (unsigned long long)le32_to_cpu(ex->ee_block),
  2729. ext4_ext_get_actual_len(ex));
  2730. err = ext4_ext_get_access(handle, inode, path + depth);
  2731. if (err)
  2732. goto out;
  2733. /* first mark the extent as initialized */
  2734. ext4_ext_mark_initialized(ex);
  2735. /* note: ext4_ext_correct_indexes() isn't needed here because
  2736. * borders are not changed
  2737. */
  2738. ext4_ext_try_to_merge(inode, path, ex);
  2739. /* Mark modified extent as dirty */
  2740. err = ext4_ext_dirty(handle, inode, path + depth);
  2741. out:
  2742. ext4_ext_show_leaf(inode, path);
  2743. return err;
  2744. }
  2745. static void unmap_underlying_metadata_blocks(struct block_device *bdev,
  2746. sector_t block, int count)
  2747. {
  2748. int i;
  2749. for (i = 0; i < count; i++)
  2750. unmap_underlying_metadata(bdev, block + i);
  2751. }
  2752. /*
  2753. * Handle EOFBLOCKS_FL flag, clearing it if necessary
  2754. */
  2755. static int check_eofblocks_fl(handle_t *handle, struct inode *inode,
  2756. ext4_lblk_t lblk,
  2757. struct ext4_ext_path *path,
  2758. unsigned int len)
  2759. {
  2760. int i, depth;
  2761. struct ext4_extent_header *eh;
  2762. struct ext4_extent *last_ex;
  2763. if (!ext4_test_inode_flag(inode, EXT4_INODE_EOFBLOCKS))
  2764. return 0;
  2765. depth = ext_depth(inode);
  2766. eh = path[depth].p_hdr;
  2767. if (unlikely(!eh->eh_entries)) {
  2768. EXT4_ERROR_INODE(inode, "eh->eh_entries == 0 and "
  2769. "EOFBLOCKS_FL set");
  2770. return -EIO;
  2771. }
  2772. last_ex = EXT_LAST_EXTENT(eh);
  2773. /*
  2774. * We should clear the EOFBLOCKS_FL flag if we are writing the
  2775. * last block in the last extent in the file. We test this by
  2776. * first checking to see if the caller to
  2777. * ext4_ext_get_blocks() was interested in the last block (or
  2778. * a block beyond the last block) in the current extent. If
  2779. * this turns out to be false, we can bail out from this
  2780. * function immediately.
  2781. */
  2782. if (lblk + len < le32_to_cpu(last_ex->ee_block) +
  2783. ext4_ext_get_actual_len(last_ex))
  2784. return 0;
  2785. /*
  2786. * If the caller does appear to be planning to write at or
  2787. * beyond the end of the current extent, we then test to see
  2788. * if the current extent is the last extent in the file, by
  2789. * checking to make sure it was reached via the rightmost node
  2790. * at each level of the tree.
  2791. */
  2792. for (i = depth-1; i >= 0; i--)
  2793. if (path[i].p_idx != EXT_LAST_INDEX(path[i].p_hdr))
  2794. return 0;
  2795. ext4_clear_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
  2796. return ext4_mark_inode_dirty(handle, inode);
  2797. }
  2798. static int
  2799. ext4_ext_handle_uninitialized_extents(handle_t *handle, struct inode *inode,
  2800. struct ext4_map_blocks *map,
  2801. struct ext4_ext_path *path, int flags,
  2802. unsigned int allocated, ext4_fsblk_t newblock)
  2803. {
  2804. int ret = 0;
  2805. int err = 0;
  2806. ext4_io_end_t *io = EXT4_I(inode)->cur_aio_dio;
  2807. ext_debug("ext4_ext_handle_uninitialized_extents: inode %lu, logical"
  2808. "block %llu, max_blocks %u, flags %d, allocated %u",
  2809. inode->i_ino, (unsigned long long)map->m_lblk, map->m_len,
  2810. flags, allocated);
  2811. ext4_ext_show_leaf(inode, path);
  2812. /* get_block() before submit the IO, split the extent */
  2813. if ((flags & EXT4_GET_BLOCKS_PRE_IO)) {
  2814. ret = ext4_split_unwritten_extents(handle, inode, map,
  2815. path, flags);
  2816. /*
  2817. * Flag the inode(non aio case) or end_io struct (aio case)
  2818. * that this IO needs to conversion to written when IO is
  2819. * completed
  2820. */
  2821. if (io && !(io->flag & EXT4_IO_END_UNWRITTEN)) {
  2822. io->flag = EXT4_IO_END_UNWRITTEN;
  2823. atomic_inc(&EXT4_I(inode)->i_aiodio_unwritten);
  2824. } else
  2825. ext4_set_inode_state(inode, EXT4_STATE_DIO_UNWRITTEN);
  2826. if (ext4_should_dioread_nolock(inode))
  2827. map->m_flags |= EXT4_MAP_UNINIT;
  2828. goto out;
  2829. }
  2830. /* IO end_io complete, convert the filled extent to written */
  2831. if ((flags & EXT4_GET_BLOCKS_CONVERT)) {
  2832. ret = ext4_convert_unwritten_extents_endio(handle, inode,
  2833. path);
  2834. if (ret >= 0) {
  2835. ext4_update_inode_fsync_trans(handle, inode, 1);
  2836. err = check_eofblocks_fl(handle, inode, map->m_lblk,
  2837. path, map->m_len);
  2838. } else
  2839. err = ret;
  2840. goto out2;
  2841. }
  2842. /* buffered IO case */
  2843. /*
  2844. * repeat fallocate creation request
  2845. * we already have an unwritten extent
  2846. */
  2847. if (flags & EXT4_GET_BLOCKS_UNINIT_EXT)
  2848. goto map_out;
  2849. /* buffered READ or buffered write_begin() lookup */
  2850. if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
  2851. /*
  2852. * We have blocks reserved already. We
  2853. * return allocated blocks so that delalloc
  2854. * won't do block reservation for us. But
  2855. * the buffer head will be unmapped so that
  2856. * a read from the block returns 0s.
  2857. */
  2858. map->m_flags |= EXT4_MAP_UNWRITTEN;
  2859. goto out1;
  2860. }
  2861. /* buffered write, writepage time, convert*/
  2862. ret = ext4_ext_convert_to_initialized(handle, inode, map, path);
  2863. if (ret >= 0) {
  2864. ext4_update_inode_fsync_trans(handle, inode, 1);
  2865. err = check_eofblocks_fl(handle, inode, map->m_lblk, path,
  2866. map->m_len);
  2867. if (err < 0)
  2868. goto out2;
  2869. }
  2870. out:
  2871. if (ret <= 0) {
  2872. err = ret;
  2873. goto out2;
  2874. } else
  2875. allocated = ret;
  2876. map->m_flags |= EXT4_MAP_NEW;
  2877. /*
  2878. * if we allocated more blocks than requested
  2879. * we need to make sure we unmap the extra block
  2880. * allocated. The actual needed block will get
  2881. * unmapped later when we find the buffer_head marked
  2882. * new.
  2883. */
  2884. if (allocated > map->m_len) {
  2885. unmap_underlying_metadata_blocks(inode->i_sb->s_bdev,
  2886. newblock + map->m_len,
  2887. allocated - map->m_len);
  2888. allocated = map->m_len;
  2889. }
  2890. /*
  2891. * If we have done fallocate with the offset that is already
  2892. * delayed allocated, we would have block reservation
  2893. * and quota reservation done in the delayed write path.
  2894. * But fallocate would have already updated quota and block
  2895. * count for this offset. So cancel these reservation
  2896. */
  2897. if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
  2898. ext4_da_update_reserve_space(inode, allocated, 0);
  2899. map_out:
  2900. map->m_flags |= EXT4_MAP_MAPPED;
  2901. out1:
  2902. if (allocated > map->m_len)
  2903. allocated = map->m_len;
  2904. ext4_ext_show_leaf(inode, path);
  2905. map->m_pblk = newblock;
  2906. map->m_len = allocated;
  2907. out2:
  2908. if (path) {
  2909. ext4_ext_drop_refs(path);
  2910. kfree(path);
  2911. }
  2912. return err ? err : allocated;
  2913. }
  2914. /*
  2915. * Block allocation/map/preallocation routine for extents based files
  2916. *
  2917. *
  2918. * Need to be called with
  2919. * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
  2920. * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
  2921. *
  2922. * return > 0, number of of blocks already mapped/allocated
  2923. * if create == 0 and these are pre-allocated blocks
  2924. * buffer head is unmapped
  2925. * otherwise blocks are mapped
  2926. *
  2927. * return = 0, if plain look up failed (blocks have not been allocated)
  2928. * buffer head is unmapped
  2929. *
  2930. * return < 0, error case.
  2931. */
  2932. int ext4_ext_map_blocks(handle_t *handle, struct inode *inode,
  2933. struct ext4_map_blocks *map, int flags)
  2934. {
  2935. struct ext4_ext_path *path = NULL;
  2936. struct ext4_extent newex, *ex;
  2937. ext4_fsblk_t newblock = 0;
  2938. int err = 0, depth, ret;
  2939. unsigned int allocated = 0;
  2940. unsigned int punched_out = 0;
  2941. unsigned int result = 0;
  2942. struct ext4_allocation_request ar;
  2943. ext4_io_end_t *io = EXT4_I(inode)->cur_aio_dio;
  2944. struct ext4_map_blocks punch_map;
  2945. ext_debug("blocks %u/%u requested for inode %lu\n",
  2946. map->m_lblk, map->m_len, inode->i_ino);
  2947. trace_ext4_ext_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
  2948. /* check in cache */
  2949. if (ext4_ext_in_cache(inode, map->m_lblk, &newex) &&
  2950. ((flags & EXT4_GET_BLOCKS_PUNCH_OUT_EXT) == 0)) {
  2951. if (!newex.ee_start_lo && !newex.ee_start_hi) {
  2952. if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
  2953. /*
  2954. * block isn't allocated yet and
  2955. * user doesn't want to allocate it
  2956. */
  2957. goto out2;
  2958. }
  2959. /* we should allocate requested block */
  2960. } else {
  2961. /* block is already allocated */
  2962. newblock = map->m_lblk
  2963. - le32_to_cpu(newex.ee_block)
  2964. + ext4_ext_pblock(&newex);
  2965. /* number of remaining blocks in the extent */
  2966. allocated = ext4_ext_get_actual_len(&newex) -
  2967. (map->m_lblk - le32_to_cpu(newex.ee_block));
  2968. goto out;
  2969. }
  2970. }
  2971. /* find extent for this block */
  2972. path = ext4_ext_find_extent(inode, map->m_lblk, NULL);
  2973. if (IS_ERR(path)) {
  2974. err = PTR_ERR(path);
  2975. path = NULL;
  2976. goto out2;
  2977. }
  2978. depth = ext_depth(inode);
  2979. /*
  2980. * consistent leaf must not be empty;
  2981. * this situation is possible, though, _during_ tree modification;
  2982. * this is why assert can't be put in ext4_ext_find_extent()
  2983. */
  2984. if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
  2985. EXT4_ERROR_INODE(inode, "bad extent address "
  2986. "lblock: %lu, depth: %d pblock %lld",
  2987. (unsigned long) map->m_lblk, depth,
  2988. path[depth].p_block);
  2989. err = -EIO;
  2990. goto out2;
  2991. }
  2992. ex = path[depth].p_ext;
  2993. if (ex) {
  2994. ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
  2995. ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
  2996. unsigned short ee_len;
  2997. /*
  2998. * Uninitialized extents are treated as holes, except that
  2999. * we split out initialized portions during a write.
  3000. */
  3001. ee_len = ext4_ext_get_actual_len(ex);
  3002. /* if found extent covers block, simply return it */
  3003. if (in_range(map->m_lblk, ee_block, ee_len)) {
  3004. newblock = map->m_lblk - ee_block + ee_start;
  3005. /* number of remaining blocks in the extent */
  3006. allocated = ee_len - (map->m_lblk - ee_block);
  3007. ext_debug("%u fit into %u:%d -> %llu\n", map->m_lblk,
  3008. ee_block, ee_len, newblock);
  3009. if ((flags & EXT4_GET_BLOCKS_PUNCH_OUT_EXT) == 0) {
  3010. /*
  3011. * Do not put uninitialized extent
  3012. * in the cache
  3013. */
  3014. if (!ext4_ext_is_uninitialized(ex)) {
  3015. ext4_ext_put_in_cache(inode, ee_block,
  3016. ee_len, ee_start);
  3017. goto out;
  3018. }
  3019. ret = ext4_ext_handle_uninitialized_extents(
  3020. handle, inode, map, path, flags,
  3021. allocated, newblock);
  3022. return ret;
  3023. }
  3024. /*
  3025. * Punch out the map length, but only to the
  3026. * end of the extent
  3027. */
  3028. punched_out = allocated < map->m_len ?
  3029. allocated : map->m_len;
  3030. /*
  3031. * Sense extents need to be converted to
  3032. * uninitialized, they must fit in an
  3033. * uninitialized extent
  3034. */
  3035. if (punched_out > EXT_UNINIT_MAX_LEN)
  3036. punched_out = EXT_UNINIT_MAX_LEN;
  3037. punch_map.m_lblk = map->m_lblk;
  3038. punch_map.m_pblk = newblock;
  3039. punch_map.m_len = punched_out;
  3040. punch_map.m_flags = 0;
  3041. /* Check to see if the extent needs to be split */
  3042. if (punch_map.m_len != ee_len ||
  3043. punch_map.m_lblk != ee_block) {
  3044. ret = ext4_split_extent(handle, inode,
  3045. path, &punch_map, 0,
  3046. EXT4_GET_BLOCKS_PUNCH_OUT_EXT |
  3047. EXT4_GET_BLOCKS_PRE_IO);
  3048. if (ret < 0) {
  3049. err = ret;
  3050. goto out2;
  3051. }
  3052. /*
  3053. * find extent for the block at
  3054. * the start of the hole
  3055. */
  3056. ext4_ext_drop_refs(path);
  3057. kfree(path);
  3058. path = ext4_ext_find_extent(inode,
  3059. map->m_lblk, NULL);
  3060. if (IS_ERR(path)) {
  3061. err = PTR_ERR(path);
  3062. path = NULL;
  3063. goto out2;
  3064. }
  3065. depth = ext_depth(inode);
  3066. ex = path[depth].p_ext;
  3067. ee_len = ext4_ext_get_actual_len(ex);
  3068. ee_block = le32_to_cpu(ex->ee_block);
  3069. ee_start = ext4_ext_pblock(ex);
  3070. }
  3071. ext4_ext_mark_uninitialized(ex);
  3072. err = ext4_ext_remove_space(inode, map->m_lblk,
  3073. map->m_lblk + punched_out);
  3074. goto out2;
  3075. }
  3076. }
  3077. /*
  3078. * requested block isn't allocated yet;
  3079. * we couldn't try to create block if create flag is zero
  3080. */
  3081. if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
  3082. /*
  3083. * put just found gap into cache to speed up
  3084. * subsequent requests
  3085. */
  3086. ext4_ext_put_gap_in_cache(inode, path, map->m_lblk);
  3087. goto out2;
  3088. }
  3089. /*
  3090. * Okay, we need to do block allocation.
  3091. */
  3092. /* find neighbour allocated blocks */
  3093. ar.lleft = map->m_lblk;
  3094. err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
  3095. if (err)
  3096. goto out2;
  3097. ar.lright = map->m_lblk;
  3098. err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright);
  3099. if (err)
  3100. goto out2;
  3101. /*
  3102. * See if request is beyond maximum number of blocks we can have in
  3103. * a single extent. For an initialized extent this limit is
  3104. * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is
  3105. * EXT_UNINIT_MAX_LEN.
  3106. */
  3107. if (map->m_len > EXT_INIT_MAX_LEN &&
  3108. !(flags & EXT4_GET_BLOCKS_UNINIT_EXT))
  3109. map->m_len = EXT_INIT_MAX_LEN;
  3110. else if (map->m_len > EXT_UNINIT_MAX_LEN &&
  3111. (flags & EXT4_GET_BLOCKS_UNINIT_EXT))
  3112. map->m_len = EXT_UNINIT_MAX_LEN;
  3113. /* Check if we can really insert (m_lblk)::(m_lblk + m_len) extent */
  3114. newex.ee_block = cpu_to_le32(map->m_lblk);
  3115. newex.ee_len = cpu_to_le16(map->m_len);
  3116. err = ext4_ext_check_overlap(inode, &newex, path);
  3117. if (err)
  3118. allocated = ext4_ext_get_actual_len(&newex);
  3119. else
  3120. allocated = map->m_len;
  3121. /* allocate new block */
  3122. ar.inode = inode;
  3123. ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk);
  3124. ar.logical = map->m_lblk;
  3125. ar.len = allocated;
  3126. if (S_ISREG(inode->i_mode))
  3127. ar.flags = EXT4_MB_HINT_DATA;
  3128. else
  3129. /* disable in-core preallocation for non-regular files */
  3130. ar.flags = 0;
  3131. if (flags & EXT4_GET_BLOCKS_NO_NORMALIZE)
  3132. ar.flags |= EXT4_MB_HINT_NOPREALLOC;
  3133. newblock = ext4_mb_new_blocks(handle, &ar, &err);
  3134. if (!newblock)
  3135. goto out2;
  3136. ext_debug("allocate new block: goal %llu, found %llu/%u\n",
  3137. ar.goal, newblock, allocated);
  3138. /* try to insert new extent into found leaf and return */
  3139. ext4_ext_store_pblock(&newex, newblock);
  3140. newex.ee_len = cpu_to_le16(ar.len);
  3141. /* Mark uninitialized */
  3142. if (flags & EXT4_GET_BLOCKS_UNINIT_EXT){
  3143. ext4_ext_mark_uninitialized(&newex);
  3144. /*
  3145. * io_end structure was created for every IO write to an
  3146. * uninitialized extent. To avoid unnecessary conversion,
  3147. * here we flag the IO that really needs the conversion.
  3148. * For non asycn direct IO case, flag the inode state
  3149. * that we need to perform conversion when IO is done.
  3150. */
  3151. if ((flags & EXT4_GET_BLOCKS_PRE_IO)) {
  3152. if (io && !(io->flag & EXT4_IO_END_UNWRITTEN)) {
  3153. io->flag = EXT4_IO_END_UNWRITTEN;
  3154. atomic_inc(&EXT4_I(inode)->i_aiodio_unwritten);
  3155. } else
  3156. ext4_set_inode_state(inode,
  3157. EXT4_STATE_DIO_UNWRITTEN);
  3158. }
  3159. if (ext4_should_dioread_nolock(inode))
  3160. map->m_flags |= EXT4_MAP_UNINIT;
  3161. }
  3162. err = check_eofblocks_fl(handle, inode, map->m_lblk, path, ar.len);
  3163. if (!err)
  3164. err = ext4_ext_insert_extent(handle, inode, path,
  3165. &newex, flags);
  3166. if (err) {
  3167. int fb_flags = flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE ?
  3168. EXT4_FREE_BLOCKS_NO_QUOT_UPDATE : 0;
  3169. /* free data blocks we just allocated */
  3170. /* not a good idea to call discard here directly,
  3171. * but otherwise we'd need to call it every free() */
  3172. ext4_discard_preallocations(inode);
  3173. ext4_free_blocks(handle, inode, NULL, ext4_ext_pblock(&newex),
  3174. ext4_ext_get_actual_len(&newex), fb_flags);
  3175. goto out2;
  3176. }
  3177. /* previous routine could use block we allocated */
  3178. newblock = ext4_ext_pblock(&newex);
  3179. allocated = ext4_ext_get_actual_len(&newex);
  3180. if (allocated > map->m_len)
  3181. allocated = map->m_len;
  3182. map->m_flags |= EXT4_MAP_NEW;
  3183. /*
  3184. * Update reserved blocks/metadata blocks after successful
  3185. * block allocation which had been deferred till now.
  3186. */
  3187. if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
  3188. ext4_da_update_reserve_space(inode, allocated, 1);
  3189. /*
  3190. * Cache the extent and update transaction to commit on fdatasync only
  3191. * when it is _not_ an uninitialized extent.
  3192. */
  3193. if ((flags & EXT4_GET_BLOCKS_UNINIT_EXT) == 0) {
  3194. ext4_ext_put_in_cache(inode, map->m_lblk, allocated, newblock);
  3195. ext4_update_inode_fsync_trans(handle, inode, 1);
  3196. } else
  3197. ext4_update_inode_fsync_trans(handle, inode, 0);
  3198. out:
  3199. if (allocated > map->m_len)
  3200. allocated = map->m_len;
  3201. ext4_ext_show_leaf(inode, path);
  3202. map->m_flags |= EXT4_MAP_MAPPED;
  3203. map->m_pblk = newblock;
  3204. map->m_len = allocated;
  3205. out2:
  3206. if (path) {
  3207. ext4_ext_drop_refs(path);
  3208. kfree(path);
  3209. }
  3210. trace_ext4_ext_map_blocks_exit(inode, map->m_lblk,
  3211. newblock, map->m_len, err ? err : allocated);
  3212. result = (flags & EXT4_GET_BLOCKS_PUNCH_OUT_EXT) ?
  3213. punched_out : allocated;
  3214. return err ? err : result;
  3215. }
  3216. void ext4_ext_truncate(struct inode *inode)
  3217. {
  3218. struct address_space *mapping = inode->i_mapping;
  3219. struct super_block *sb = inode->i_sb;
  3220. ext4_lblk_t last_block;
  3221. handle_t *handle;
  3222. int err = 0;
  3223. /*
  3224. * finish any pending end_io work so we won't run the risk of
  3225. * converting any truncated blocks to initialized later
  3226. */
  3227. ext4_flush_completed_IO(inode);
  3228. /*
  3229. * probably first extent we're gonna free will be last in block
  3230. */
  3231. err = ext4_writepage_trans_blocks(inode);
  3232. handle = ext4_journal_start(inode, err);
  3233. if (IS_ERR(handle))
  3234. return;
  3235. if (inode->i_size & (sb->s_blocksize - 1))
  3236. ext4_block_truncate_page(handle, mapping, inode->i_size);
  3237. if (ext4_orphan_add(handle, inode))
  3238. goto out_stop;
  3239. down_write(&EXT4_I(inode)->i_data_sem);
  3240. ext4_ext_invalidate_cache(inode);
  3241. ext4_discard_preallocations(inode);
  3242. /*
  3243. * TODO: optimization is possible here.
  3244. * Probably we need not scan at all,
  3245. * because page truncation is enough.
  3246. */
  3247. /* we have to know where to truncate from in crash case */
  3248. EXT4_I(inode)->i_disksize = inode->i_size;
  3249. ext4_mark_inode_dirty(handle, inode);
  3250. last_block = (inode->i_size + sb->s_blocksize - 1)
  3251. >> EXT4_BLOCK_SIZE_BITS(sb);
  3252. err = ext4_ext_remove_space(inode, last_block, EXT_MAX_BLOCKS - 1);
  3253. /* In a multi-transaction truncate, we only make the final
  3254. * transaction synchronous.
  3255. */
  3256. if (IS_SYNC(inode))
  3257. ext4_handle_sync(handle);
  3258. up_write(&EXT4_I(inode)->i_data_sem);
  3259. out_stop:
  3260. /*
  3261. * If this was a simple ftruncate() and the file will remain alive,
  3262. * then we need to clear up the orphan record which we created above.
  3263. * However, if this was a real unlink then we were called by
  3264. * ext4_delete_inode(), and we allow that function to clean up the
  3265. * orphan info for us.
  3266. */
  3267. if (inode->i_nlink)
  3268. ext4_orphan_del(handle, inode);
  3269. inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
  3270. ext4_mark_inode_dirty(handle, inode);
  3271. ext4_journal_stop(handle);
  3272. }
  3273. static void ext4_falloc_update_inode(struct inode *inode,
  3274. int mode, loff_t new_size, int update_ctime)
  3275. {
  3276. struct timespec now;
  3277. if (update_ctime) {
  3278. now = current_fs_time(inode->i_sb);
  3279. if (!timespec_equal(&inode->i_ctime, &now))
  3280. inode->i_ctime = now;
  3281. }
  3282. /*
  3283. * Update only when preallocation was requested beyond
  3284. * the file size.
  3285. */
  3286. if (!(mode & FALLOC_FL_KEEP_SIZE)) {
  3287. if (new_size > i_size_read(inode))
  3288. i_size_write(inode, new_size);
  3289. if (new_size > EXT4_I(inode)->i_disksize)
  3290. ext4_update_i_disksize(inode, new_size);
  3291. } else {
  3292. /*
  3293. * Mark that we allocate beyond EOF so the subsequent truncate
  3294. * can proceed even if the new size is the same as i_size.
  3295. */
  3296. if (new_size > i_size_read(inode))
  3297. ext4_set_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
  3298. }
  3299. }
  3300. /*
  3301. * preallocate space for a file. This implements ext4's fallocate file
  3302. * operation, which gets called from sys_fallocate system call.
  3303. * For block-mapped files, posix_fallocate should fall back to the method
  3304. * of writing zeroes to the required new blocks (the same behavior which is
  3305. * expected for file systems which do not support fallocate() system call).
  3306. */
  3307. long ext4_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
  3308. {
  3309. struct inode *inode = file->f_path.dentry->d_inode;
  3310. handle_t *handle;
  3311. loff_t new_size;
  3312. unsigned int max_blocks;
  3313. int ret = 0;
  3314. int ret2 = 0;
  3315. int retries = 0;
  3316. struct ext4_map_blocks map;
  3317. unsigned int credits, blkbits = inode->i_blkbits;
  3318. /*
  3319. * currently supporting (pre)allocate mode for extent-based
  3320. * files _only_
  3321. */
  3322. if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
  3323. return -EOPNOTSUPP;
  3324. /* Return error if mode is not supported */
  3325. if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE))
  3326. return -EOPNOTSUPP;
  3327. if (mode & FALLOC_FL_PUNCH_HOLE)
  3328. return ext4_punch_hole(file, offset, len);
  3329. trace_ext4_fallocate_enter(inode, offset, len, mode);
  3330. map.m_lblk = offset >> blkbits;
  3331. /*
  3332. * We can't just convert len to max_blocks because
  3333. * If blocksize = 4096 offset = 3072 and len = 2048
  3334. */
  3335. max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits)
  3336. - map.m_lblk;
  3337. /*
  3338. * credits to insert 1 extent into extent tree
  3339. */
  3340. credits = ext4_chunk_trans_blocks(inode, max_blocks);
  3341. mutex_lock(&inode->i_mutex);
  3342. ret = inode_newsize_ok(inode, (len + offset));
  3343. if (ret) {
  3344. mutex_unlock(&inode->i_mutex);
  3345. trace_ext4_fallocate_exit(inode, offset, max_blocks, ret);
  3346. return ret;
  3347. }
  3348. retry:
  3349. while (ret >= 0 && ret < max_blocks) {
  3350. map.m_lblk = map.m_lblk + ret;
  3351. map.m_len = max_blocks = max_blocks - ret;
  3352. handle = ext4_journal_start(inode, credits);
  3353. if (IS_ERR(handle)) {
  3354. ret = PTR_ERR(handle);
  3355. break;
  3356. }
  3357. ret = ext4_map_blocks(handle, inode, &map,
  3358. EXT4_GET_BLOCKS_CREATE_UNINIT_EXT |
  3359. EXT4_GET_BLOCKS_NO_NORMALIZE);
  3360. if (ret <= 0) {
  3361. #ifdef EXT4FS_DEBUG
  3362. WARN_ON(ret <= 0);
  3363. printk(KERN_ERR "%s: ext4_ext_map_blocks "
  3364. "returned error inode#%lu, block=%u, "
  3365. "max_blocks=%u", __func__,
  3366. inode->i_ino, map.m_lblk, max_blocks);
  3367. #endif
  3368. ext4_mark_inode_dirty(handle, inode);
  3369. ret2 = ext4_journal_stop(handle);
  3370. break;
  3371. }
  3372. if ((map.m_lblk + ret) >= (EXT4_BLOCK_ALIGN(offset + len,
  3373. blkbits) >> blkbits))
  3374. new_size = offset + len;
  3375. else
  3376. new_size = (map.m_lblk + ret) << blkbits;
  3377. ext4_falloc_update_inode(inode, mode, new_size,
  3378. (map.m_flags & EXT4_MAP_NEW));
  3379. ext4_mark_inode_dirty(handle, inode);
  3380. ret2 = ext4_journal_stop(handle);
  3381. if (ret2)
  3382. break;
  3383. }
  3384. if (ret == -ENOSPC &&
  3385. ext4_should_retry_alloc(inode->i_sb, &retries)) {
  3386. ret = 0;
  3387. goto retry;
  3388. }
  3389. mutex_unlock(&inode->i_mutex);
  3390. trace_ext4_fallocate_exit(inode, offset, max_blocks,
  3391. ret > 0 ? ret2 : ret);
  3392. return ret > 0 ? ret2 : ret;
  3393. }
  3394. /*
  3395. * This function convert a range of blocks to written extents
  3396. * The caller of this function will pass the start offset and the size.
  3397. * all unwritten extents within this range will be converted to
  3398. * written extents.
  3399. *
  3400. * This function is called from the direct IO end io call back
  3401. * function, to convert the fallocated extents after IO is completed.
  3402. * Returns 0 on success.
  3403. */
  3404. int ext4_convert_unwritten_extents(struct inode *inode, loff_t offset,
  3405. ssize_t len)
  3406. {
  3407. handle_t *handle;
  3408. unsigned int max_blocks;
  3409. int ret = 0;
  3410. int ret2 = 0;
  3411. struct ext4_map_blocks map;
  3412. unsigned int credits, blkbits = inode->i_blkbits;
  3413. map.m_lblk = offset >> blkbits;
  3414. /*
  3415. * We can't just convert len to max_blocks because
  3416. * If blocksize = 4096 offset = 3072 and len = 2048
  3417. */
  3418. max_blocks = ((EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits) -
  3419. map.m_lblk);
  3420. /*
  3421. * credits to insert 1 extent into extent tree
  3422. */
  3423. credits = ext4_chunk_trans_blocks(inode, max_blocks);
  3424. while (ret >= 0 && ret < max_blocks) {
  3425. map.m_lblk += ret;
  3426. map.m_len = (max_blocks -= ret);
  3427. handle = ext4_journal_start(inode, credits);
  3428. if (IS_ERR(handle)) {
  3429. ret = PTR_ERR(handle);
  3430. break;
  3431. }
  3432. ret = ext4_map_blocks(handle, inode, &map,
  3433. EXT4_GET_BLOCKS_IO_CONVERT_EXT);
  3434. if (ret <= 0) {
  3435. WARN_ON(ret <= 0);
  3436. printk(KERN_ERR "%s: ext4_ext_map_blocks "
  3437. "returned error inode#%lu, block=%u, "
  3438. "max_blocks=%u", __func__,
  3439. inode->i_ino, map.m_lblk, map.m_len);
  3440. }
  3441. ext4_mark_inode_dirty(handle, inode);
  3442. ret2 = ext4_journal_stop(handle);
  3443. if (ret <= 0 || ret2 )
  3444. break;
  3445. }
  3446. return ret > 0 ? ret2 : ret;
  3447. }
  3448. /*
  3449. * Callback function called for each extent to gather FIEMAP information.
  3450. */
  3451. static int ext4_ext_fiemap_cb(struct inode *inode, ext4_lblk_t next,
  3452. struct ext4_ext_cache *newex, struct ext4_extent *ex,
  3453. void *data)
  3454. {
  3455. __u64 logical;
  3456. __u64 physical;
  3457. __u64 length;
  3458. __u32 flags = 0;
  3459. int ret = 0;
  3460. struct fiemap_extent_info *fieinfo = data;
  3461. unsigned char blksize_bits;
  3462. blksize_bits = inode->i_sb->s_blocksize_bits;
  3463. logical = (__u64)newex->ec_block << blksize_bits;
  3464. if (newex->ec_start == 0) {
  3465. /*
  3466. * No extent in extent-tree contains block @newex->ec_start,
  3467. * then the block may stay in 1)a hole or 2)delayed-extent.
  3468. *
  3469. * Holes or delayed-extents are processed as follows.
  3470. * 1. lookup dirty pages with specified range in pagecache.
  3471. * If no page is got, then there is no delayed-extent and
  3472. * return with EXT_CONTINUE.
  3473. * 2. find the 1st mapped buffer,
  3474. * 3. check if the mapped buffer is both in the request range
  3475. * and a delayed buffer. If not, there is no delayed-extent,
  3476. * then return.
  3477. * 4. a delayed-extent is found, the extent will be collected.
  3478. */
  3479. ext4_lblk_t end = 0;
  3480. pgoff_t last_offset;
  3481. pgoff_t offset;
  3482. pgoff_t index;
  3483. pgoff_t start_index = 0;
  3484. struct page **pages = NULL;
  3485. struct buffer_head *bh = NULL;
  3486. struct buffer_head *head = NULL;
  3487. unsigned int nr_pages = PAGE_SIZE / sizeof(struct page *);
  3488. pages = kmalloc(PAGE_SIZE, GFP_KERNEL);
  3489. if (pages == NULL)
  3490. return -ENOMEM;
  3491. offset = logical >> PAGE_SHIFT;
  3492. repeat:
  3493. last_offset = offset;
  3494. head = NULL;
  3495. ret = find_get_pages_tag(inode->i_mapping, &offset,
  3496. PAGECACHE_TAG_DIRTY, nr_pages, pages);
  3497. if (!(flags & FIEMAP_EXTENT_DELALLOC)) {
  3498. /* First time, try to find a mapped buffer. */
  3499. if (ret == 0) {
  3500. out:
  3501. for (index = 0; index < ret; index++)
  3502. page_cache_release(pages[index]);
  3503. /* just a hole. */
  3504. kfree(pages);
  3505. return EXT_CONTINUE;
  3506. }
  3507. index = 0;
  3508. next_page:
  3509. /* Try to find the 1st mapped buffer. */
  3510. end = ((__u64)pages[index]->index << PAGE_SHIFT) >>
  3511. blksize_bits;
  3512. if (!page_has_buffers(pages[index]))
  3513. goto out;
  3514. head = page_buffers(pages[index]);
  3515. if (!head)
  3516. goto out;
  3517. index++;
  3518. bh = head;
  3519. do {
  3520. if (end >= newex->ec_block +
  3521. newex->ec_len)
  3522. /* The buffer is out of
  3523. * the request range.
  3524. */
  3525. goto out;
  3526. if (buffer_mapped(bh) &&
  3527. end >= newex->ec_block) {
  3528. start_index = index - 1;
  3529. /* get the 1st mapped buffer. */
  3530. goto found_mapped_buffer;
  3531. }
  3532. bh = bh->b_this_page;
  3533. end++;
  3534. } while (bh != head);
  3535. /* No mapped buffer in the range found in this page,
  3536. * We need to look up next page.
  3537. */
  3538. if (index >= ret) {
  3539. /* There is no page left, but we need to limit
  3540. * newex->ec_len.
  3541. */
  3542. newex->ec_len = end - newex->ec_block;
  3543. goto out;
  3544. }
  3545. goto next_page;
  3546. } else {
  3547. /*Find contiguous delayed buffers. */
  3548. if (ret > 0 && pages[0]->index == last_offset)
  3549. head = page_buffers(pages[0]);
  3550. bh = head;
  3551. index = 1;
  3552. start_index = 0;
  3553. }
  3554. found_mapped_buffer:
  3555. if (bh != NULL && buffer_delay(bh)) {
  3556. /* 1st or contiguous delayed buffer found. */
  3557. if (!(flags & FIEMAP_EXTENT_DELALLOC)) {
  3558. /*
  3559. * 1st delayed buffer found, record
  3560. * the start of extent.
  3561. */
  3562. flags |= FIEMAP_EXTENT_DELALLOC;
  3563. newex->ec_block = end;
  3564. logical = (__u64)end << blksize_bits;
  3565. }
  3566. /* Find contiguous delayed buffers. */
  3567. do {
  3568. if (!buffer_delay(bh))
  3569. goto found_delayed_extent;
  3570. bh = bh->b_this_page;
  3571. end++;
  3572. } while (bh != head);
  3573. for (; index < ret; index++) {
  3574. if (!page_has_buffers(pages[index])) {
  3575. bh = NULL;
  3576. break;
  3577. }
  3578. head = page_buffers(pages[index]);
  3579. if (!head) {
  3580. bh = NULL;
  3581. break;
  3582. }
  3583. if (pages[index]->index !=
  3584. pages[start_index]->index + index
  3585. - start_index) {
  3586. /* Blocks are not contiguous. */
  3587. bh = NULL;
  3588. break;
  3589. }
  3590. bh = head;
  3591. do {
  3592. if (!buffer_delay(bh))
  3593. /* Delayed-extent ends. */
  3594. goto found_delayed_extent;
  3595. bh = bh->b_this_page;
  3596. end++;
  3597. } while (bh != head);
  3598. }
  3599. } else if (!(flags & FIEMAP_EXTENT_DELALLOC))
  3600. /* a hole found. */
  3601. goto out;
  3602. found_delayed_extent:
  3603. newex->ec_len = min(end - newex->ec_block,
  3604. (ext4_lblk_t)EXT_INIT_MAX_LEN);
  3605. if (ret == nr_pages && bh != NULL &&
  3606. newex->ec_len < EXT_INIT_MAX_LEN &&
  3607. buffer_delay(bh)) {
  3608. /* Have not collected an extent and continue. */
  3609. for (index = 0; index < ret; index++)
  3610. page_cache_release(pages[index]);
  3611. goto repeat;
  3612. }
  3613. for (index = 0; index < ret; index++)
  3614. page_cache_release(pages[index]);
  3615. kfree(pages);
  3616. }
  3617. physical = (__u64)newex->ec_start << blksize_bits;
  3618. length = (__u64)newex->ec_len << blksize_bits;
  3619. if (ex && ext4_ext_is_uninitialized(ex))
  3620. flags |= FIEMAP_EXTENT_UNWRITTEN;
  3621. if (next == EXT_MAX_BLOCKS)
  3622. flags |= FIEMAP_EXTENT_LAST;
  3623. ret = fiemap_fill_next_extent(fieinfo, logical, physical,
  3624. length, flags);
  3625. if (ret < 0)
  3626. return ret;
  3627. if (ret == 1)
  3628. return EXT_BREAK;
  3629. return EXT_CONTINUE;
  3630. }
  3631. /* fiemap flags we can handle specified here */
  3632. #define EXT4_FIEMAP_FLAGS (FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
  3633. static int ext4_xattr_fiemap(struct inode *inode,
  3634. struct fiemap_extent_info *fieinfo)
  3635. {
  3636. __u64 physical = 0;
  3637. __u64 length;
  3638. __u32 flags = FIEMAP_EXTENT_LAST;
  3639. int blockbits = inode->i_sb->s_blocksize_bits;
  3640. int error = 0;
  3641. /* in-inode? */
  3642. if (ext4_test_inode_state(inode, EXT4_STATE_XATTR)) {
  3643. struct ext4_iloc iloc;
  3644. int offset; /* offset of xattr in inode */
  3645. error = ext4_get_inode_loc(inode, &iloc);
  3646. if (error)
  3647. return error;
  3648. physical = iloc.bh->b_blocknr << blockbits;
  3649. offset = EXT4_GOOD_OLD_INODE_SIZE +
  3650. EXT4_I(inode)->i_extra_isize;
  3651. physical += offset;
  3652. length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
  3653. flags |= FIEMAP_EXTENT_DATA_INLINE;
  3654. brelse(iloc.bh);
  3655. } else { /* external block */
  3656. physical = EXT4_I(inode)->i_file_acl << blockbits;
  3657. length = inode->i_sb->s_blocksize;
  3658. }
  3659. if (physical)
  3660. error = fiemap_fill_next_extent(fieinfo, 0, physical,
  3661. length, flags);
  3662. return (error < 0 ? error : 0);
  3663. }
  3664. /*
  3665. * ext4_ext_punch_hole
  3666. *
  3667. * Punches a hole of "length" bytes in a file starting
  3668. * at byte "offset"
  3669. *
  3670. * @inode: The inode of the file to punch a hole in
  3671. * @offset: The starting byte offset of the hole
  3672. * @length: The length of the hole
  3673. *
  3674. * Returns the number of blocks removed or negative on err
  3675. */
  3676. int ext4_ext_punch_hole(struct file *file, loff_t offset, loff_t length)
  3677. {
  3678. struct inode *inode = file->f_path.dentry->d_inode;
  3679. struct super_block *sb = inode->i_sb;
  3680. struct ext4_ext_cache cache_ex;
  3681. ext4_lblk_t first_block, last_block, num_blocks, iblock, max_blocks;
  3682. struct address_space *mapping = inode->i_mapping;
  3683. struct ext4_map_blocks map;
  3684. handle_t *handle;
  3685. loff_t first_block_offset, last_block_offset, block_len;
  3686. loff_t first_page, last_page, first_page_offset, last_page_offset;
  3687. int ret, credits, blocks_released, err = 0;
  3688. first_block = (offset + sb->s_blocksize - 1) >>
  3689. EXT4_BLOCK_SIZE_BITS(sb);
  3690. last_block = (offset + length) >> EXT4_BLOCK_SIZE_BITS(sb);
  3691. first_block_offset = first_block << EXT4_BLOCK_SIZE_BITS(sb);
  3692. last_block_offset = last_block << EXT4_BLOCK_SIZE_BITS(sb);
  3693. first_page = (offset + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
  3694. last_page = (offset + length) >> PAGE_CACHE_SHIFT;
  3695. first_page_offset = first_page << PAGE_CACHE_SHIFT;
  3696. last_page_offset = last_page << PAGE_CACHE_SHIFT;
  3697. /*
  3698. * Write out all dirty pages to avoid race conditions
  3699. * Then release them.
  3700. */
  3701. if (mapping->nrpages && mapping_tagged(mapping, PAGECACHE_TAG_DIRTY)) {
  3702. err = filemap_write_and_wait_range(mapping,
  3703. first_page_offset == 0 ? 0 : first_page_offset-1,
  3704. last_page_offset);
  3705. if (err)
  3706. return err;
  3707. }
  3708. /* Now release the pages */
  3709. if (last_page_offset > first_page_offset) {
  3710. truncate_inode_pages_range(mapping, first_page_offset,
  3711. last_page_offset-1);
  3712. }
  3713. /* finish any pending end_io work */
  3714. ext4_flush_completed_IO(inode);
  3715. credits = ext4_writepage_trans_blocks(inode);
  3716. handle = ext4_journal_start(inode, credits);
  3717. if (IS_ERR(handle))
  3718. return PTR_ERR(handle);
  3719. err = ext4_orphan_add(handle, inode);
  3720. if (err)
  3721. goto out;
  3722. /*
  3723. * Now we need to zero out the un block aligned data.
  3724. * If the file is smaller than a block, just
  3725. * zero out the middle
  3726. */
  3727. if (first_block > last_block)
  3728. ext4_block_zero_page_range(handle, mapping, offset, length);
  3729. else {
  3730. /* zero out the head of the hole before the first block */
  3731. block_len = first_block_offset - offset;
  3732. if (block_len > 0)
  3733. ext4_block_zero_page_range(handle, mapping,
  3734. offset, block_len);
  3735. /* zero out the tail of the hole after the last block */
  3736. block_len = offset + length - last_block_offset;
  3737. if (block_len > 0) {
  3738. ext4_block_zero_page_range(handle, mapping,
  3739. last_block_offset, block_len);
  3740. }
  3741. }
  3742. /* If there are no blocks to remove, return now */
  3743. if (first_block >= last_block)
  3744. goto out;
  3745. down_write(&EXT4_I(inode)->i_data_sem);
  3746. ext4_ext_invalidate_cache(inode);
  3747. ext4_discard_preallocations(inode);
  3748. /*
  3749. * Loop over all the blocks and identify blocks
  3750. * that need to be punched out
  3751. */
  3752. iblock = first_block;
  3753. blocks_released = 0;
  3754. while (iblock < last_block) {
  3755. max_blocks = last_block - iblock;
  3756. num_blocks = 1;
  3757. memset(&map, 0, sizeof(map));
  3758. map.m_lblk = iblock;
  3759. map.m_len = max_blocks;
  3760. ret = ext4_ext_map_blocks(handle, inode, &map,
  3761. EXT4_GET_BLOCKS_PUNCH_OUT_EXT);
  3762. if (ret > 0) {
  3763. blocks_released += ret;
  3764. num_blocks = ret;
  3765. } else if (ret == 0) {
  3766. /*
  3767. * If map blocks could not find the block,
  3768. * then it is in a hole. If the hole was
  3769. * not already cached, then map blocks should
  3770. * put it in the cache. So we can get the hole
  3771. * out of the cache
  3772. */
  3773. memset(&cache_ex, 0, sizeof(cache_ex));
  3774. if ((ext4_ext_check_cache(inode, iblock, &cache_ex)) &&
  3775. !cache_ex.ec_start) {
  3776. /* The hole is cached */
  3777. num_blocks = cache_ex.ec_block +
  3778. cache_ex.ec_len - iblock;
  3779. } else {
  3780. /* The block could not be identified */
  3781. err = -EIO;
  3782. break;
  3783. }
  3784. } else {
  3785. /* Map blocks error */
  3786. err = ret;
  3787. break;
  3788. }
  3789. if (num_blocks == 0) {
  3790. /* This condition should never happen */
  3791. ext_debug("Block lookup failed");
  3792. err = -EIO;
  3793. break;
  3794. }
  3795. iblock += num_blocks;
  3796. }
  3797. if (blocks_released > 0) {
  3798. ext4_ext_invalidate_cache(inode);
  3799. ext4_discard_preallocations(inode);
  3800. }
  3801. if (IS_SYNC(inode))
  3802. ext4_handle_sync(handle);
  3803. up_write(&EXT4_I(inode)->i_data_sem);
  3804. out:
  3805. ext4_orphan_del(handle, inode);
  3806. inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
  3807. ext4_mark_inode_dirty(handle, inode);
  3808. ext4_journal_stop(handle);
  3809. return err;
  3810. }
  3811. int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
  3812. __u64 start, __u64 len)
  3813. {
  3814. ext4_lblk_t start_blk;
  3815. int error = 0;
  3816. /* fallback to generic here if not in extents fmt */
  3817. if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
  3818. return generic_block_fiemap(inode, fieinfo, start, len,
  3819. ext4_get_block);
  3820. if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS))
  3821. return -EBADR;
  3822. if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
  3823. error = ext4_xattr_fiemap(inode, fieinfo);
  3824. } else {
  3825. ext4_lblk_t len_blks;
  3826. __u64 last_blk;
  3827. start_blk = start >> inode->i_sb->s_blocksize_bits;
  3828. last_blk = (start + len - 1) >> inode->i_sb->s_blocksize_bits;
  3829. if (last_blk >= EXT_MAX_BLOCKS)
  3830. last_blk = EXT_MAX_BLOCKS-1;
  3831. len_blks = ((ext4_lblk_t) last_blk) - start_blk + 1;
  3832. /*
  3833. * Walk the extent tree gathering extent information.
  3834. * ext4_ext_fiemap_cb will push extents back to user.
  3835. */
  3836. error = ext4_ext_walk_space(inode, start_blk, len_blks,
  3837. ext4_ext_fiemap_cb, fieinfo);
  3838. }
  3839. return error;
  3840. }