extents.c 102 KB

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