extents.c 102 KB

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