extents.c 102 KB

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