jfs_xtree.c 99 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902390339043905390639073908390939103911391239133914391539163917391839193920392139223923392439253926392739283929393039313932393339343935393639373938393939403941394239433944394539463947394839493950395139523953395439553956395739583959396039613962396339643965396639673968396939703971397239733974397539763977397839793980398139823983398439853986398739883989399039913992399339943995399639973998399940004001400240034004400540064007400840094010401140124013401440154016401740184019402040214022402340244025402640274028402940304031403240334034403540364037403840394040404140424043404440454046404740484049405040514052405340544055405640574058405940604061406240634064406540664067406840694070407140724073407440754076407740784079408040814082408340844085408640874088408940904091409240934094409540964097409840994100410141024103410441054106410741084109411041114112411341144115411641174118411941204121412241234124412541264127412841294130413141324133413441354136413741384139414041414142414341444145414641474148414941504151415241534154415541564157415841594160416141624163416441654166416741684169417041714172417341744175417641774178417941804181
  1. /*
  2. * Copyright (C) International Business Machines Corp., 2000-2005
  3. *
  4. * This program is free software; you can redistribute it and/or modify
  5. * it under the terms of the GNU General Public License as published by
  6. * the Free Software Foundation; either version 2 of the License, or
  7. * (at your option) any later version.
  8. *
  9. * This program is distributed in the hope that it will be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
  12. * the GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program; if not, write to the Free Software
  16. * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  17. */
  18. /*
  19. * jfs_xtree.c: extent allocation descriptor B+-tree manager
  20. */
  21. #include <linux/fs.h>
  22. #include <linux/quotaops.h>
  23. #include "jfs_incore.h"
  24. #include "jfs_filsys.h"
  25. #include "jfs_metapage.h"
  26. #include "jfs_dmap.h"
  27. #include "jfs_dinode.h"
  28. #include "jfs_superblock.h"
  29. #include "jfs_debug.h"
  30. /*
  31. * xtree local flag
  32. */
  33. #define XT_INSERT 0x00000001
  34. /*
  35. * xtree key/entry comparison: extent offset
  36. *
  37. * return:
  38. * -1: k < start of extent
  39. * 0: start_of_extent <= k <= end_of_extent
  40. * 1: k > end_of_extent
  41. */
  42. #define XT_CMP(CMP, K, X, OFFSET64)\
  43. {\
  44. OFFSET64 = offsetXAD(X);\
  45. (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
  46. ((K) < OFFSET64) ? -1 : 0;\
  47. }
  48. /* write a xad entry */
  49. #define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
  50. {\
  51. (XAD)->flag = (FLAG);\
  52. XADoffset((XAD), (OFF));\
  53. XADlength((XAD), (LEN));\
  54. XADaddress((XAD), (ADDR));\
  55. }
  56. #define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot)
  57. /* get page buffer for specified block address */
  58. /* ToDo: Replace this ugly macro with a function */
  59. #define XT_GETPAGE(IP, BN, MP, SIZE, P, RC)\
  60. {\
  61. BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot)\
  62. if (!(RC))\
  63. {\
  64. if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) ||\
  65. (le16_to_cpu((P)->header.nextindex) > le16_to_cpu((P)->header.maxentry)) ||\
  66. (le16_to_cpu((P)->header.maxentry) > (((BN)==0)?XTROOTMAXSLOT:PSIZE>>L2XTSLOTSIZE)))\
  67. {\
  68. jfs_error((IP)->i_sb, "XT_GETPAGE: xtree page corrupt");\
  69. BT_PUTPAGE(MP);\
  70. MP = NULL;\
  71. RC = -EIO;\
  72. }\
  73. }\
  74. }
  75. /* for consistency */
  76. #define XT_PUTPAGE(MP) BT_PUTPAGE(MP)
  77. #define XT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
  78. BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot)
  79. /* xtree entry parameter descriptor */
  80. struct xtsplit {
  81. struct metapage *mp;
  82. s16 index;
  83. u8 flag;
  84. s64 off;
  85. s64 addr;
  86. int len;
  87. struct pxdlist *pxdlist;
  88. };
  89. /*
  90. * statistics
  91. */
  92. #ifdef CONFIG_JFS_STATISTICS
  93. static struct {
  94. uint search;
  95. uint fastSearch;
  96. uint split;
  97. } xtStat;
  98. #endif
  99. /*
  100. * forward references
  101. */
  102. static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
  103. struct btstack * btstack, int flag);
  104. static int xtSplitUp(tid_t tid,
  105. struct inode *ip,
  106. struct xtsplit * split, struct btstack * btstack);
  107. static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
  108. struct metapage ** rmpp, s64 * rbnp);
  109. static int xtSplitRoot(tid_t tid, struct inode *ip,
  110. struct xtsplit * split, struct metapage ** rmpp);
  111. #ifdef _STILL_TO_PORT
  112. static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
  113. xtpage_t * fp, struct btstack * btstack);
  114. static int xtSearchNode(struct inode *ip,
  115. xad_t * xad,
  116. int *cmpp, struct btstack * btstack, int flag);
  117. static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp);
  118. #endif /* _STILL_TO_PORT */
  119. /*
  120. * xtLookup()
  121. *
  122. * function: map a single page into a physical extent;
  123. */
  124. int xtLookup(struct inode *ip, s64 lstart,
  125. s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
  126. {
  127. int rc = 0;
  128. struct btstack btstack;
  129. int cmp;
  130. s64 bn;
  131. struct metapage *mp;
  132. xtpage_t *p;
  133. int index;
  134. xad_t *xad;
  135. s64 next, size, xoff, xend;
  136. int xlen;
  137. s64 xaddr;
  138. *paddr = 0;
  139. *plen = llen;
  140. if (!no_check) {
  141. /* is lookup offset beyond eof ? */
  142. size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
  143. JFS_SBI(ip->i_sb)->l2bsize;
  144. if (lstart >= size) {
  145. jfs_err("xtLookup: lstart (0x%lx) >= size (0x%lx)",
  146. (ulong) lstart, (ulong) size);
  147. return 0;
  148. }
  149. }
  150. /*
  151. * search for the xad entry covering the logical extent
  152. */
  153. //search:
  154. if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) {
  155. jfs_err("xtLookup: xtSearch returned %d", rc);
  156. return rc;
  157. }
  158. /*
  159. * compute the physical extent covering logical extent
  160. *
  161. * N.B. search may have failed (e.g., hole in sparse file),
  162. * and returned the index of the next entry.
  163. */
  164. /* retrieve search result */
  165. XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  166. /* is xad found covering start of logical extent ?
  167. * lstart is a page start address,
  168. * i.e., lstart cannot start in a hole;
  169. */
  170. if (cmp) {
  171. if (next)
  172. *plen = min(next - lstart, llen);
  173. goto out;
  174. }
  175. /*
  176. * lxd covered by xad
  177. */
  178. xad = &p->xad[index];
  179. xoff = offsetXAD(xad);
  180. xlen = lengthXAD(xad);
  181. xend = xoff + xlen;
  182. xaddr = addressXAD(xad);
  183. /* initialize new pxd */
  184. *pflag = xad->flag;
  185. *paddr = xaddr + (lstart - xoff);
  186. /* a page must be fully covered by an xad */
  187. *plen = min(xend - lstart, llen);
  188. out:
  189. XT_PUTPAGE(mp);
  190. return rc;
  191. }
  192. /*
  193. * xtLookupList()
  194. *
  195. * function: map a single logical extent into a list of physical extent;
  196. *
  197. * parameter:
  198. * struct inode *ip,
  199. * struct lxdlist *lxdlist, lxd list (in)
  200. * struct xadlist *xadlist, xad list (in/out)
  201. * int flag)
  202. *
  203. * coverage of lxd by xad under assumption of
  204. * . lxd's are ordered and disjoint.
  205. * . xad's are ordered and disjoint.
  206. *
  207. * return:
  208. * 0: success
  209. *
  210. * note: a page being written (even a single byte) is backed fully,
  211. * except the last page which is only backed with blocks
  212. * required to cover the last byte;
  213. * the extent backing a page is fully contained within an xad;
  214. */
  215. int xtLookupList(struct inode *ip, struct lxdlist * lxdlist,
  216. struct xadlist * xadlist, int flag)
  217. {
  218. int rc = 0;
  219. struct btstack btstack;
  220. int cmp;
  221. s64 bn;
  222. struct metapage *mp;
  223. xtpage_t *p;
  224. int index;
  225. lxd_t *lxd;
  226. xad_t *xad, *pxd;
  227. s64 size, lstart, lend, xstart, xend, pstart;
  228. s64 llen, xlen, plen;
  229. s64 xaddr, paddr;
  230. int nlxd, npxd, maxnpxd;
  231. npxd = xadlist->nxad = 0;
  232. maxnpxd = xadlist->maxnxad;
  233. pxd = xadlist->xad;
  234. nlxd = lxdlist->nlxd;
  235. lxd = lxdlist->lxd;
  236. lstart = offsetLXD(lxd);
  237. llen = lengthLXD(lxd);
  238. lend = lstart + llen;
  239. size = (ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
  240. JFS_SBI(ip->i_sb)->l2bsize;
  241. /*
  242. * search for the xad entry covering the logical extent
  243. */
  244. search:
  245. if (lstart >= size)
  246. return 0;
  247. if ((rc = xtSearch(ip, lstart, NULL, &cmp, &btstack, 0)))
  248. return rc;
  249. /*
  250. * compute the physical extent covering logical extent
  251. *
  252. * N.B. search may have failed (e.g., hole in sparse file),
  253. * and returned the index of the next entry.
  254. */
  255. //map:
  256. /* retrieve search result */
  257. XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  258. /* is xad on the next sibling page ? */
  259. if (index == le16_to_cpu(p->header.nextindex)) {
  260. if (p->header.flag & BT_ROOT)
  261. goto mapend;
  262. if ((bn = le64_to_cpu(p->header.next)) == 0)
  263. goto mapend;
  264. XT_PUTPAGE(mp);
  265. /* get next sibling page */
  266. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  267. if (rc)
  268. return rc;
  269. index = XTENTRYSTART;
  270. }
  271. xad = &p->xad[index];
  272. /*
  273. * is lxd covered by xad ?
  274. */
  275. compare:
  276. xstart = offsetXAD(xad);
  277. xlen = lengthXAD(xad);
  278. xend = xstart + xlen;
  279. xaddr = addressXAD(xad);
  280. compare1:
  281. if (xstart < lstart)
  282. goto compare2;
  283. /* (lstart <= xstart) */
  284. /* lxd is NOT covered by xad */
  285. if (lend <= xstart) {
  286. /*
  287. * get next lxd
  288. */
  289. if (--nlxd == 0)
  290. goto mapend;
  291. lxd++;
  292. lstart = offsetLXD(lxd);
  293. llen = lengthLXD(lxd);
  294. lend = lstart + llen;
  295. if (lstart >= size)
  296. goto mapend;
  297. /* compare with the current xad */
  298. goto compare1;
  299. }
  300. /* lxd is covered by xad */
  301. else { /* (xstart < lend) */
  302. /* initialize new pxd */
  303. pstart = xstart;
  304. plen = min(lend - xstart, xlen);
  305. paddr = xaddr;
  306. goto cover;
  307. }
  308. /* (xstart < lstart) */
  309. compare2:
  310. /* lxd is covered by xad */
  311. if (lstart < xend) {
  312. /* initialize new pxd */
  313. pstart = lstart;
  314. plen = min(xend - lstart, llen);
  315. paddr = xaddr + (lstart - xstart);
  316. goto cover;
  317. }
  318. /* lxd is NOT covered by xad */
  319. else { /* (xend <= lstart) */
  320. /*
  321. * get next xad
  322. *
  323. * linear search next xad covering lxd on
  324. * the current xad page, and then tree search
  325. */
  326. if (index == le16_to_cpu(p->header.nextindex) - 1) {
  327. if (p->header.flag & BT_ROOT)
  328. goto mapend;
  329. XT_PUTPAGE(mp);
  330. goto search;
  331. } else {
  332. index++;
  333. xad++;
  334. /* compare with new xad */
  335. goto compare;
  336. }
  337. }
  338. /*
  339. * lxd is covered by xad and a new pxd has been initialized
  340. * (lstart <= xstart < lend) or (xstart < lstart < xend)
  341. */
  342. cover:
  343. /* finalize pxd corresponding to current xad */
  344. XT_PUTENTRY(pxd, xad->flag, pstart, plen, paddr);
  345. if (++npxd >= maxnpxd)
  346. goto mapend;
  347. pxd++;
  348. /*
  349. * lxd is fully covered by xad
  350. */
  351. if (lend <= xend) {
  352. /*
  353. * get next lxd
  354. */
  355. if (--nlxd == 0)
  356. goto mapend;
  357. lxd++;
  358. lstart = offsetLXD(lxd);
  359. llen = lengthLXD(lxd);
  360. lend = lstart + llen;
  361. if (lstart >= size)
  362. goto mapend;
  363. /*
  364. * test for old xad covering new lxd
  365. * (old xstart < new lstart)
  366. */
  367. goto compare2;
  368. }
  369. /*
  370. * lxd is partially covered by xad
  371. */
  372. else { /* (xend < lend) */
  373. /*
  374. * get next xad
  375. *
  376. * linear search next xad covering lxd on
  377. * the current xad page, and then next xad page search
  378. */
  379. if (index == le16_to_cpu(p->header.nextindex) - 1) {
  380. if (p->header.flag & BT_ROOT)
  381. goto mapend;
  382. if ((bn = le64_to_cpu(p->header.next)) == 0)
  383. goto mapend;
  384. XT_PUTPAGE(mp);
  385. /* get next sibling page */
  386. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  387. if (rc)
  388. return rc;
  389. index = XTENTRYSTART;
  390. xad = &p->xad[index];
  391. } else {
  392. index++;
  393. xad++;
  394. }
  395. /*
  396. * test for new xad covering old lxd
  397. * (old lstart < new xstart)
  398. */
  399. goto compare;
  400. }
  401. mapend:
  402. xadlist->nxad = npxd;
  403. //out:
  404. XT_PUTPAGE(mp);
  405. return rc;
  406. }
  407. /*
  408. * xtSearch()
  409. *
  410. * function: search for the xad entry covering specified offset.
  411. *
  412. * parameters:
  413. * ip - file object;
  414. * xoff - extent offset;
  415. * nextp - address of next extent (if any) for search miss
  416. * cmpp - comparison result:
  417. * btstack - traverse stack;
  418. * flag - search process flag (XT_INSERT);
  419. *
  420. * returns:
  421. * btstack contains (bn, index) of search path traversed to the entry.
  422. * *cmpp is set to result of comparison with the entry returned.
  423. * the page containing the entry is pinned at exit.
  424. */
  425. static int xtSearch(struct inode *ip, s64 xoff, s64 *nextp,
  426. int *cmpp, struct btstack * btstack, int flag)
  427. {
  428. struct jfs_inode_info *jfs_ip = JFS_IP(ip);
  429. int rc = 0;
  430. int cmp = 1; /* init for empty page */
  431. s64 bn; /* block number */
  432. struct metapage *mp; /* page buffer */
  433. xtpage_t *p; /* page */
  434. xad_t *xad;
  435. int base, index, lim, btindex;
  436. struct btframe *btsp;
  437. int nsplit = 0; /* number of pages to split */
  438. s64 t64;
  439. s64 next = 0;
  440. INCREMENT(xtStat.search);
  441. BT_CLR(btstack);
  442. btstack->nsplit = 0;
  443. /*
  444. * search down tree from root:
  445. *
  446. * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
  447. * internal page, child page Pi contains entry with k, Ki <= K < Kj.
  448. *
  449. * if entry with search key K is not found
  450. * internal page search find the entry with largest key Ki
  451. * less than K which point to the child page to search;
  452. * leaf page search find the entry with smallest key Kj
  453. * greater than K so that the returned index is the position of
  454. * the entry to be shifted right for insertion of new entry.
  455. * for empty tree, search key is greater than any key of the tree.
  456. *
  457. * by convention, root bn = 0.
  458. */
  459. for (bn = 0;;) {
  460. /* get/pin the page to search */
  461. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  462. if (rc)
  463. return rc;
  464. /* try sequential access heuristics with the previous
  465. * access entry in target leaf page:
  466. * once search narrowed down into the target leaf,
  467. * key must either match an entry in the leaf or
  468. * key entry does not exist in the tree;
  469. */
  470. //fastSearch:
  471. if ((jfs_ip->btorder & BT_SEQUENTIAL) &&
  472. (p->header.flag & BT_LEAF) &&
  473. (index = jfs_ip->btindex) <
  474. le16_to_cpu(p->header.nextindex)) {
  475. xad = &p->xad[index];
  476. t64 = offsetXAD(xad);
  477. if (xoff < t64 + lengthXAD(xad)) {
  478. if (xoff >= t64) {
  479. *cmpp = 0;
  480. goto out;
  481. }
  482. /* stop sequential access heuristics */
  483. goto binarySearch;
  484. } else { /* (t64 + lengthXAD(xad)) <= xoff */
  485. /* try next sequential entry */
  486. index++;
  487. if (index <
  488. le16_to_cpu(p->header.nextindex)) {
  489. xad++;
  490. t64 = offsetXAD(xad);
  491. if (xoff < t64 + lengthXAD(xad)) {
  492. if (xoff >= t64) {
  493. *cmpp = 0;
  494. goto out;
  495. }
  496. /* miss: key falls between
  497. * previous and this entry
  498. */
  499. *cmpp = 1;
  500. next = t64;
  501. goto out;
  502. }
  503. /* (xoff >= t64 + lengthXAD(xad));
  504. * matching entry may be further out:
  505. * stop heuristic search
  506. */
  507. /* stop sequential access heuristics */
  508. goto binarySearch;
  509. }
  510. /* (index == p->header.nextindex);
  511. * miss: key entry does not exist in
  512. * the target leaf/tree
  513. */
  514. *cmpp = 1;
  515. goto out;
  516. }
  517. /*
  518. * if hit, return index of the entry found, and
  519. * if miss, where new entry with search key is
  520. * to be inserted;
  521. */
  522. out:
  523. /* compute number of pages to split */
  524. if (flag & XT_INSERT) {
  525. if (p->header.nextindex == /* little-endian */
  526. p->header.maxentry)
  527. nsplit++;
  528. else
  529. nsplit = 0;
  530. btstack->nsplit = nsplit;
  531. }
  532. /* save search result */
  533. btsp = btstack->top;
  534. btsp->bn = bn;
  535. btsp->index = index;
  536. btsp->mp = mp;
  537. /* update sequential access heuristics */
  538. jfs_ip->btindex = index;
  539. if (nextp)
  540. *nextp = next;
  541. INCREMENT(xtStat.fastSearch);
  542. return 0;
  543. }
  544. /* well, ... full search now */
  545. binarySearch:
  546. lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
  547. /*
  548. * binary search with search key K on the current page
  549. */
  550. for (base = XTENTRYSTART; lim; lim >>= 1) {
  551. index = base + (lim >> 1);
  552. XT_CMP(cmp, xoff, &p->xad[index], t64);
  553. if (cmp == 0) {
  554. /*
  555. * search hit
  556. */
  557. /* search hit - leaf page:
  558. * return the entry found
  559. */
  560. if (p->header.flag & BT_LEAF) {
  561. *cmpp = cmp;
  562. /* compute number of pages to split */
  563. if (flag & XT_INSERT) {
  564. if (p->header.nextindex ==
  565. p->header.maxentry)
  566. nsplit++;
  567. else
  568. nsplit = 0;
  569. btstack->nsplit = nsplit;
  570. }
  571. /* save search result */
  572. btsp = btstack->top;
  573. btsp->bn = bn;
  574. btsp->index = index;
  575. btsp->mp = mp;
  576. /* init sequential access heuristics */
  577. btindex = jfs_ip->btindex;
  578. if (index == btindex ||
  579. index == btindex + 1)
  580. jfs_ip->btorder = BT_SEQUENTIAL;
  581. else
  582. jfs_ip->btorder = BT_RANDOM;
  583. jfs_ip->btindex = index;
  584. return 0;
  585. }
  586. /* search hit - internal page:
  587. * descend/search its child page
  588. */
  589. if (index < le16_to_cpu(p->header.nextindex)-1)
  590. next = offsetXAD(&p->xad[index + 1]);
  591. goto next;
  592. }
  593. if (cmp > 0) {
  594. base = index + 1;
  595. --lim;
  596. }
  597. }
  598. /*
  599. * search miss
  600. *
  601. * base is the smallest index with key (Kj) greater than
  602. * search key (K) and may be zero or maxentry index.
  603. */
  604. if (base < le16_to_cpu(p->header.nextindex))
  605. next = offsetXAD(&p->xad[base]);
  606. /*
  607. * search miss - leaf page:
  608. *
  609. * return location of entry (base) where new entry with
  610. * search key K is to be inserted.
  611. */
  612. if (p->header.flag & BT_LEAF) {
  613. *cmpp = cmp;
  614. /* compute number of pages to split */
  615. if (flag & XT_INSERT) {
  616. if (p->header.nextindex ==
  617. p->header.maxentry)
  618. nsplit++;
  619. else
  620. nsplit = 0;
  621. btstack->nsplit = nsplit;
  622. }
  623. /* save search result */
  624. btsp = btstack->top;
  625. btsp->bn = bn;
  626. btsp->index = base;
  627. btsp->mp = mp;
  628. /* init sequential access heuristics */
  629. btindex = jfs_ip->btindex;
  630. if (base == btindex || base == btindex + 1)
  631. jfs_ip->btorder = BT_SEQUENTIAL;
  632. else
  633. jfs_ip->btorder = BT_RANDOM;
  634. jfs_ip->btindex = base;
  635. if (nextp)
  636. *nextp = next;
  637. return 0;
  638. }
  639. /*
  640. * search miss - non-leaf page:
  641. *
  642. * if base is non-zero, decrement base by one to get the parent
  643. * entry of the child page to search.
  644. */
  645. index = base ? base - 1 : base;
  646. /*
  647. * go down to child page
  648. */
  649. next:
  650. /* update number of pages to split */
  651. if (p->header.nextindex == p->header.maxentry)
  652. nsplit++;
  653. else
  654. nsplit = 0;
  655. /* push (bn, index) of the parent page/entry */
  656. if (BT_STACK_FULL(btstack)) {
  657. jfs_error(ip->i_sb, "stack overrun in xtSearch!");
  658. XT_PUTPAGE(mp);
  659. return -EIO;
  660. }
  661. BT_PUSH(btstack, bn, index);
  662. /* get the child page block number */
  663. bn = addressXAD(&p->xad[index]);
  664. /* unpin the parent page */
  665. XT_PUTPAGE(mp);
  666. }
  667. }
  668. /*
  669. * xtInsert()
  670. *
  671. * function:
  672. *
  673. * parameter:
  674. * tid - transaction id;
  675. * ip - file object;
  676. * xflag - extent flag (XAD_NOTRECORDED):
  677. * xoff - extent offset;
  678. * xlen - extent length;
  679. * xaddrp - extent address pointer (in/out):
  680. * if (*xaddrp)
  681. * caller allocated data extent at *xaddrp;
  682. * else
  683. * allocate data extent and return its xaddr;
  684. * flag -
  685. *
  686. * return:
  687. */
  688. int xtInsert(tid_t tid, /* transaction id */
  689. struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp,
  690. int flag)
  691. {
  692. int rc = 0;
  693. s64 xaddr, hint;
  694. struct metapage *mp; /* meta-page buffer */
  695. xtpage_t *p; /* base B+-tree index page */
  696. s64 bn;
  697. int index, nextindex;
  698. struct btstack btstack; /* traverse stack */
  699. struct xtsplit split; /* split information */
  700. xad_t *xad;
  701. int cmp;
  702. s64 next;
  703. struct tlock *tlck;
  704. struct xtlock *xtlck;
  705. jfs_info("xtInsert: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
  706. /*
  707. * search for the entry location at which to insert:
  708. *
  709. * xtFastSearch() and xtSearch() both returns (leaf page
  710. * pinned, index at which to insert).
  711. * n.b. xtSearch() may return index of maxentry of
  712. * the full page.
  713. */
  714. if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
  715. return rc;
  716. /* retrieve search result */
  717. XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  718. /* This test must follow XT_GETSEARCH since mp must be valid if
  719. * we branch to out: */
  720. if ((cmp == 0) || (next && (xlen > next - xoff))) {
  721. rc = -EEXIST;
  722. goto out;
  723. }
  724. /*
  725. * allocate data extent requested
  726. *
  727. * allocation hint: last xad
  728. */
  729. if ((xaddr = *xaddrp) == 0) {
  730. if (index > XTENTRYSTART) {
  731. xad = &p->xad[index - 1];
  732. hint = addressXAD(xad) + lengthXAD(xad) - 1;
  733. } else
  734. hint = 0;
  735. if ((rc = DQUOT_ALLOC_BLOCK(ip, xlen)))
  736. goto out;
  737. if ((rc = dbAlloc(ip, hint, (s64) xlen, &xaddr))) {
  738. DQUOT_FREE_BLOCK(ip, xlen);
  739. goto out;
  740. }
  741. }
  742. /*
  743. * insert entry for new extent
  744. */
  745. xflag |= XAD_NEW;
  746. /*
  747. * if the leaf page is full, split the page and
  748. * propagate up the router entry for the new page from split
  749. *
  750. * The xtSplitUp() will insert the entry and unpin the leaf page.
  751. */
  752. nextindex = le16_to_cpu(p->header.nextindex);
  753. if (nextindex == le16_to_cpu(p->header.maxentry)) {
  754. split.mp = mp;
  755. split.index = index;
  756. split.flag = xflag;
  757. split.off = xoff;
  758. split.len = xlen;
  759. split.addr = xaddr;
  760. split.pxdlist = NULL;
  761. if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
  762. /* undo data extent allocation */
  763. if (*xaddrp == 0) {
  764. dbFree(ip, xaddr, (s64) xlen);
  765. DQUOT_FREE_BLOCK(ip, xlen);
  766. }
  767. return rc;
  768. }
  769. *xaddrp = xaddr;
  770. return 0;
  771. }
  772. /*
  773. * insert the new entry into the leaf page
  774. */
  775. /*
  776. * acquire a transaction lock on the leaf page;
  777. *
  778. * action: xad insertion/extension;
  779. */
  780. BT_MARK_DIRTY(mp, ip);
  781. /* if insert into middle, shift right remaining entries. */
  782. if (index < nextindex)
  783. memmove(&p->xad[index + 1], &p->xad[index],
  784. (nextindex - index) * sizeof(xad_t));
  785. /* insert the new entry: mark the entry NEW */
  786. xad = &p->xad[index];
  787. XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
  788. /* advance next available entry index */
  789. p->header.nextindex =
  790. cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
  791. /* Don't log it if there are no links to the file */
  792. if (!test_cflag(COMMIT_Nolink, ip)) {
  793. tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
  794. xtlck = (struct xtlock *) & tlck->lock;
  795. xtlck->lwm.offset =
  796. (xtlck->lwm.offset) ? min(index,
  797. (int)xtlck->lwm.offset) : index;
  798. xtlck->lwm.length =
  799. le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
  800. }
  801. *xaddrp = xaddr;
  802. out:
  803. /* unpin the leaf page */
  804. XT_PUTPAGE(mp);
  805. return rc;
  806. }
  807. /*
  808. * xtSplitUp()
  809. *
  810. * function:
  811. * split full pages as propagating insertion up the tree
  812. *
  813. * parameter:
  814. * tid - transaction id;
  815. * ip - file object;
  816. * split - entry parameter descriptor;
  817. * btstack - traverse stack from xtSearch()
  818. *
  819. * return:
  820. */
  821. static int
  822. xtSplitUp(tid_t tid,
  823. struct inode *ip, struct xtsplit * split, struct btstack * btstack)
  824. {
  825. int rc = 0;
  826. struct metapage *smp;
  827. xtpage_t *sp; /* split page */
  828. struct metapage *rmp;
  829. s64 rbn; /* new right page block number */
  830. struct metapage *rcmp;
  831. xtpage_t *rcp; /* right child page */
  832. s64 rcbn; /* right child page block number */
  833. int skip; /* index of entry of insertion */
  834. int nextindex; /* next available entry index of p */
  835. struct btframe *parent; /* parent page entry on traverse stack */
  836. xad_t *xad;
  837. s64 xaddr;
  838. int xlen;
  839. int nsplit; /* number of pages split */
  840. struct pxdlist pxdlist;
  841. pxd_t *pxd;
  842. struct tlock *tlck;
  843. struct xtlock *xtlck;
  844. smp = split->mp;
  845. sp = XT_PAGE(ip, smp);
  846. /* is inode xtree root extension/inline EA area free ? */
  847. if ((sp->header.flag & BT_ROOT) && (!S_ISDIR(ip->i_mode)) &&
  848. (le16_to_cpu(sp->header.maxentry) < XTROOTMAXSLOT) &&
  849. (JFS_IP(ip)->mode2 & INLINEEA)) {
  850. sp->header.maxentry = cpu_to_le16(XTROOTMAXSLOT);
  851. JFS_IP(ip)->mode2 &= ~INLINEEA;
  852. BT_MARK_DIRTY(smp, ip);
  853. /*
  854. * acquire a transaction lock on the leaf page;
  855. *
  856. * action: xad insertion/extension;
  857. */
  858. /* if insert into middle, shift right remaining entries. */
  859. skip = split->index;
  860. nextindex = le16_to_cpu(sp->header.nextindex);
  861. if (skip < nextindex)
  862. memmove(&sp->xad[skip + 1], &sp->xad[skip],
  863. (nextindex - skip) * sizeof(xad_t));
  864. /* insert the new entry: mark the entry NEW */
  865. xad = &sp->xad[skip];
  866. XT_PUTENTRY(xad, split->flag, split->off, split->len,
  867. split->addr);
  868. /* advance next available entry index */
  869. sp->header.nextindex =
  870. cpu_to_le16(le16_to_cpu(sp->header.nextindex) + 1);
  871. /* Don't log it if there are no links to the file */
  872. if (!test_cflag(COMMIT_Nolink, ip)) {
  873. tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
  874. xtlck = (struct xtlock *) & tlck->lock;
  875. xtlck->lwm.offset = (xtlck->lwm.offset) ?
  876. min(skip, (int)xtlck->lwm.offset) : skip;
  877. xtlck->lwm.length =
  878. le16_to_cpu(sp->header.nextindex) -
  879. xtlck->lwm.offset;
  880. }
  881. return 0;
  882. }
  883. /*
  884. * allocate new index blocks to cover index page split(s)
  885. *
  886. * allocation hint: ?
  887. */
  888. if (split->pxdlist == NULL) {
  889. nsplit = btstack->nsplit;
  890. split->pxdlist = &pxdlist;
  891. pxdlist.maxnpxd = pxdlist.npxd = 0;
  892. pxd = &pxdlist.pxd[0];
  893. xlen = JFS_SBI(ip->i_sb)->nbperpage;
  894. for (; nsplit > 0; nsplit--, pxd++) {
  895. if ((rc = dbAlloc(ip, (s64) 0, (s64) xlen, &xaddr))
  896. == 0) {
  897. PXDaddress(pxd, xaddr);
  898. PXDlength(pxd, xlen);
  899. pxdlist.maxnpxd++;
  900. continue;
  901. }
  902. /* undo allocation */
  903. XT_PUTPAGE(smp);
  904. return rc;
  905. }
  906. }
  907. /*
  908. * Split leaf page <sp> into <sp> and a new right page <rp>.
  909. *
  910. * The split routines insert the new entry into the leaf page,
  911. * and acquire txLock as appropriate.
  912. * return <rp> pinned and its block number <rpbn>.
  913. */
  914. rc = (sp->header.flag & BT_ROOT) ?
  915. xtSplitRoot(tid, ip, split, &rmp) :
  916. xtSplitPage(tid, ip, split, &rmp, &rbn);
  917. XT_PUTPAGE(smp);
  918. if (rc)
  919. return -EIO;
  920. /*
  921. * propagate up the router entry for the leaf page just split
  922. *
  923. * insert a router entry for the new page into the parent page,
  924. * propagate the insert/split up the tree by walking back the stack
  925. * of (bn of parent page, index of child page entry in parent page)
  926. * that were traversed during the search for the page that split.
  927. *
  928. * the propagation of insert/split up the tree stops if the root
  929. * splits or the page inserted into doesn't have to split to hold
  930. * the new entry.
  931. *
  932. * the parent entry for the split page remains the same, and
  933. * a new entry is inserted at its right with the first key and
  934. * block number of the new right page.
  935. *
  936. * There are a maximum of 3 pages pinned at any time:
  937. * right child, left parent and right parent (when the parent splits)
  938. * to keep the child page pinned while working on the parent.
  939. * make sure that all pins are released at exit.
  940. */
  941. while ((parent = BT_POP(btstack)) != NULL) {
  942. /* parent page specified by stack frame <parent> */
  943. /* keep current child pages <rcp> pinned */
  944. rcmp = rmp;
  945. rcbn = rbn;
  946. rcp = XT_PAGE(ip, rcmp);
  947. /*
  948. * insert router entry in parent for new right child page <rp>
  949. */
  950. /* get/pin the parent page <sp> */
  951. XT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc);
  952. if (rc) {
  953. XT_PUTPAGE(rcmp);
  954. return rc;
  955. }
  956. /*
  957. * The new key entry goes ONE AFTER the index of parent entry,
  958. * because the split was to the right.
  959. */
  960. skip = parent->index + 1;
  961. /*
  962. * split or shift right remaining entries of the parent page
  963. */
  964. nextindex = le16_to_cpu(sp->header.nextindex);
  965. /*
  966. * parent page is full - split the parent page
  967. */
  968. if (nextindex == le16_to_cpu(sp->header.maxentry)) {
  969. /* init for parent page split */
  970. split->mp = smp;
  971. split->index = skip; /* index at insert */
  972. split->flag = XAD_NEW;
  973. split->off = offsetXAD(&rcp->xad[XTENTRYSTART]);
  974. split->len = JFS_SBI(ip->i_sb)->nbperpage;
  975. split->addr = rcbn;
  976. /* unpin previous right child page */
  977. XT_PUTPAGE(rcmp);
  978. /* The split routines insert the new entry,
  979. * and acquire txLock as appropriate.
  980. * return <rp> pinned and its block number <rpbn>.
  981. */
  982. rc = (sp->header.flag & BT_ROOT) ?
  983. xtSplitRoot(tid, ip, split, &rmp) :
  984. xtSplitPage(tid, ip, split, &rmp, &rbn);
  985. if (rc) {
  986. XT_PUTPAGE(smp);
  987. return rc;
  988. }
  989. XT_PUTPAGE(smp);
  990. /* keep new child page <rp> pinned */
  991. }
  992. /*
  993. * parent page is not full - insert in parent page
  994. */
  995. else {
  996. /*
  997. * insert router entry in parent for the right child
  998. * page from the first entry of the right child page:
  999. */
  1000. /*
  1001. * acquire a transaction lock on the parent page;
  1002. *
  1003. * action: router xad insertion;
  1004. */
  1005. BT_MARK_DIRTY(smp, ip);
  1006. /*
  1007. * if insert into middle, shift right remaining entries
  1008. */
  1009. if (skip < nextindex)
  1010. memmove(&sp->xad[skip + 1], &sp->xad[skip],
  1011. (nextindex -
  1012. skip) << L2XTSLOTSIZE);
  1013. /* insert the router entry */
  1014. xad = &sp->xad[skip];
  1015. XT_PUTENTRY(xad, XAD_NEW,
  1016. offsetXAD(&rcp->xad[XTENTRYSTART]),
  1017. JFS_SBI(ip->i_sb)->nbperpage, rcbn);
  1018. /* advance next available entry index. */
  1019. sp->header.nextindex =
  1020. cpu_to_le16(le16_to_cpu(sp->header.nextindex) +
  1021. 1);
  1022. /* Don't log it if there are no links to the file */
  1023. if (!test_cflag(COMMIT_Nolink, ip)) {
  1024. tlck = txLock(tid, ip, smp,
  1025. tlckXTREE | tlckGROW);
  1026. xtlck = (struct xtlock *) & tlck->lock;
  1027. xtlck->lwm.offset = (xtlck->lwm.offset) ?
  1028. min(skip, (int)xtlck->lwm.offset) : skip;
  1029. xtlck->lwm.length =
  1030. le16_to_cpu(sp->header.nextindex) -
  1031. xtlck->lwm.offset;
  1032. }
  1033. /* unpin parent page */
  1034. XT_PUTPAGE(smp);
  1035. /* exit propagate up */
  1036. break;
  1037. }
  1038. }
  1039. /* unpin current right page */
  1040. XT_PUTPAGE(rmp);
  1041. return 0;
  1042. }
  1043. /*
  1044. * xtSplitPage()
  1045. *
  1046. * function:
  1047. * split a full non-root page into
  1048. * original/split/left page and new right page
  1049. * i.e., the original/split page remains as left page.
  1050. *
  1051. * parameter:
  1052. * int tid,
  1053. * struct inode *ip,
  1054. * struct xtsplit *split,
  1055. * struct metapage **rmpp,
  1056. * u64 *rbnp,
  1057. *
  1058. * return:
  1059. * Pointer to page in which to insert or NULL on error.
  1060. */
  1061. static int
  1062. xtSplitPage(tid_t tid, struct inode *ip,
  1063. struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
  1064. {
  1065. int rc = 0;
  1066. struct metapage *smp;
  1067. xtpage_t *sp;
  1068. struct metapage *rmp;
  1069. xtpage_t *rp; /* new right page allocated */
  1070. s64 rbn; /* new right page block number */
  1071. struct metapage *mp;
  1072. xtpage_t *p;
  1073. s64 nextbn;
  1074. int skip, maxentry, middle, righthalf, n;
  1075. xad_t *xad;
  1076. struct pxdlist *pxdlist;
  1077. pxd_t *pxd;
  1078. struct tlock *tlck;
  1079. struct xtlock *sxtlck = NULL, *rxtlck = NULL;
  1080. int quota_allocation = 0;
  1081. smp = split->mp;
  1082. sp = XT_PAGE(ip, smp);
  1083. INCREMENT(xtStat.split);
  1084. pxdlist = split->pxdlist;
  1085. pxd = &pxdlist->pxd[pxdlist->npxd];
  1086. pxdlist->npxd++;
  1087. rbn = addressPXD(pxd);
  1088. /* Allocate blocks to quota. */
  1089. if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) {
  1090. rc = -EDQUOT;
  1091. goto clean_up;
  1092. }
  1093. quota_allocation += lengthPXD(pxd);
  1094. /*
  1095. * allocate the new right page for the split
  1096. */
  1097. rmp = get_metapage(ip, rbn, PSIZE, 1);
  1098. if (rmp == NULL) {
  1099. rc = -EIO;
  1100. goto clean_up;
  1101. }
  1102. jfs_info("xtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
  1103. BT_MARK_DIRTY(rmp, ip);
  1104. /*
  1105. * action: new page;
  1106. */
  1107. rp = (xtpage_t *) rmp->data;
  1108. rp->header.self = *pxd;
  1109. rp->header.flag = sp->header.flag & BT_TYPE;
  1110. rp->header.maxentry = sp->header.maxentry; /* little-endian */
  1111. rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
  1112. BT_MARK_DIRTY(smp, ip);
  1113. /* Don't log it if there are no links to the file */
  1114. if (!test_cflag(COMMIT_Nolink, ip)) {
  1115. /*
  1116. * acquire a transaction lock on the new right page;
  1117. */
  1118. tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
  1119. rxtlck = (struct xtlock *) & tlck->lock;
  1120. rxtlck->lwm.offset = XTENTRYSTART;
  1121. /*
  1122. * acquire a transaction lock on the split page
  1123. */
  1124. tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
  1125. sxtlck = (struct xtlock *) & tlck->lock;
  1126. }
  1127. /*
  1128. * initialize/update sibling pointers of <sp> and <rp>
  1129. */
  1130. nextbn = le64_to_cpu(sp->header.next);
  1131. rp->header.next = cpu_to_le64(nextbn);
  1132. rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
  1133. sp->header.next = cpu_to_le64(rbn);
  1134. skip = split->index;
  1135. /*
  1136. * sequential append at tail (after last entry of last page)
  1137. *
  1138. * if splitting the last page on a level because of appending
  1139. * a entry to it (skip is maxentry), it's likely that the access is
  1140. * sequential. adding an empty page on the side of the level is less
  1141. * work and can push the fill factor much higher than normal.
  1142. * if we're wrong it's no big deal - we will do the split the right
  1143. * way next time.
  1144. * (it may look like it's equally easy to do a similar hack for
  1145. * reverse sorted data, that is, split the tree left, but it's not.
  1146. * Be my guest.)
  1147. */
  1148. if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) {
  1149. /*
  1150. * acquire a transaction lock on the new/right page;
  1151. *
  1152. * action: xad insertion;
  1153. */
  1154. /* insert entry at the first entry of the new right page */
  1155. xad = &rp->xad[XTENTRYSTART];
  1156. XT_PUTENTRY(xad, split->flag, split->off, split->len,
  1157. split->addr);
  1158. rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
  1159. if (!test_cflag(COMMIT_Nolink, ip)) {
  1160. /* rxtlck->lwm.offset = XTENTRYSTART; */
  1161. rxtlck->lwm.length = 1;
  1162. }
  1163. *rmpp = rmp;
  1164. *rbnp = rbn;
  1165. jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
  1166. return 0;
  1167. }
  1168. /*
  1169. * non-sequential insert (at possibly middle page)
  1170. */
  1171. /*
  1172. * update previous pointer of old next/right page of <sp>
  1173. */
  1174. if (nextbn != 0) {
  1175. XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
  1176. if (rc) {
  1177. XT_PUTPAGE(rmp);
  1178. goto clean_up;
  1179. }
  1180. BT_MARK_DIRTY(mp, ip);
  1181. /*
  1182. * acquire a transaction lock on the next page;
  1183. *
  1184. * action:sibling pointer update;
  1185. */
  1186. if (!test_cflag(COMMIT_Nolink, ip))
  1187. tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
  1188. p->header.prev = cpu_to_le64(rbn);
  1189. /* sibling page may have been updated previously, or
  1190. * it may be updated later;
  1191. */
  1192. XT_PUTPAGE(mp);
  1193. }
  1194. /*
  1195. * split the data between the split and new/right pages
  1196. */
  1197. maxentry = le16_to_cpu(sp->header.maxentry);
  1198. middle = maxentry >> 1;
  1199. righthalf = maxentry - middle;
  1200. /*
  1201. * skip index in old split/left page - insert into left page:
  1202. */
  1203. if (skip <= middle) {
  1204. /* move right half of split page to the new right page */
  1205. memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
  1206. righthalf << L2XTSLOTSIZE);
  1207. /* shift right tail of left half to make room for new entry */
  1208. if (skip < middle)
  1209. memmove(&sp->xad[skip + 1], &sp->xad[skip],
  1210. (middle - skip) << L2XTSLOTSIZE);
  1211. /* insert new entry */
  1212. xad = &sp->xad[skip];
  1213. XT_PUTENTRY(xad, split->flag, split->off, split->len,
  1214. split->addr);
  1215. /* update page header */
  1216. sp->header.nextindex = cpu_to_le16(middle + 1);
  1217. if (!test_cflag(COMMIT_Nolink, ip)) {
  1218. sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
  1219. min(skip, (int)sxtlck->lwm.offset) : skip;
  1220. }
  1221. rp->header.nextindex =
  1222. cpu_to_le16(XTENTRYSTART + righthalf);
  1223. }
  1224. /*
  1225. * skip index in new right page - insert into right page:
  1226. */
  1227. else {
  1228. /* move left head of right half to right page */
  1229. n = skip - middle;
  1230. memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
  1231. n << L2XTSLOTSIZE);
  1232. /* insert new entry */
  1233. n += XTENTRYSTART;
  1234. xad = &rp->xad[n];
  1235. XT_PUTENTRY(xad, split->flag, split->off, split->len,
  1236. split->addr);
  1237. /* move right tail of right half to right page */
  1238. if (skip < maxentry)
  1239. memmove(&rp->xad[n + 1], &sp->xad[skip],
  1240. (maxentry - skip) << L2XTSLOTSIZE);
  1241. /* update page header */
  1242. sp->header.nextindex = cpu_to_le16(middle);
  1243. if (!test_cflag(COMMIT_Nolink, ip)) {
  1244. sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
  1245. min(middle, (int)sxtlck->lwm.offset) : middle;
  1246. }
  1247. rp->header.nextindex = cpu_to_le16(XTENTRYSTART +
  1248. righthalf + 1);
  1249. }
  1250. if (!test_cflag(COMMIT_Nolink, ip)) {
  1251. sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) -
  1252. sxtlck->lwm.offset;
  1253. /* rxtlck->lwm.offset = XTENTRYSTART; */
  1254. rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
  1255. XTENTRYSTART;
  1256. }
  1257. *rmpp = rmp;
  1258. *rbnp = rbn;
  1259. jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
  1260. return rc;
  1261. clean_up:
  1262. /* Rollback quota allocation. */
  1263. if (quota_allocation)
  1264. DQUOT_FREE_BLOCK(ip, quota_allocation);
  1265. return (rc);
  1266. }
  1267. /*
  1268. * xtSplitRoot()
  1269. *
  1270. * function:
  1271. * split the full root page into
  1272. * original/root/split page and new right page
  1273. * i.e., root remains fixed in tree anchor (inode) and
  1274. * the root is copied to a single new right child page
  1275. * since root page << non-root page, and
  1276. * the split root page contains a single entry for the
  1277. * new right child page.
  1278. *
  1279. * parameter:
  1280. * int tid,
  1281. * struct inode *ip,
  1282. * struct xtsplit *split,
  1283. * struct metapage **rmpp)
  1284. *
  1285. * return:
  1286. * Pointer to page in which to insert or NULL on error.
  1287. */
  1288. static int
  1289. xtSplitRoot(tid_t tid,
  1290. struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
  1291. {
  1292. xtpage_t *sp;
  1293. struct metapage *rmp;
  1294. xtpage_t *rp;
  1295. s64 rbn;
  1296. int skip, nextindex;
  1297. xad_t *xad;
  1298. pxd_t *pxd;
  1299. struct pxdlist *pxdlist;
  1300. struct tlock *tlck;
  1301. struct xtlock *xtlck;
  1302. sp = &JFS_IP(ip)->i_xtroot;
  1303. INCREMENT(xtStat.split);
  1304. /*
  1305. * allocate a single (right) child page
  1306. */
  1307. pxdlist = split->pxdlist;
  1308. pxd = &pxdlist->pxd[pxdlist->npxd];
  1309. pxdlist->npxd++;
  1310. rbn = addressPXD(pxd);
  1311. rmp = get_metapage(ip, rbn, PSIZE, 1);
  1312. if (rmp == NULL)
  1313. return -EIO;
  1314. /* Allocate blocks to quota. */
  1315. if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) {
  1316. release_metapage(rmp);
  1317. return -EDQUOT;
  1318. }
  1319. jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp);
  1320. /*
  1321. * acquire a transaction lock on the new right page;
  1322. *
  1323. * action: new page;
  1324. */
  1325. BT_MARK_DIRTY(rmp, ip);
  1326. rp = (xtpage_t *) rmp->data;
  1327. rp->header.flag =
  1328. (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
  1329. rp->header.self = *pxd;
  1330. rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
  1331. rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE);
  1332. /* initialize sibling pointers */
  1333. rp->header.next = 0;
  1334. rp->header.prev = 0;
  1335. /*
  1336. * copy the in-line root page into new right page extent
  1337. */
  1338. nextindex = le16_to_cpu(sp->header.maxentry);
  1339. memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART],
  1340. (nextindex - XTENTRYSTART) << L2XTSLOTSIZE);
  1341. /*
  1342. * insert the new entry into the new right/child page
  1343. * (skip index in the new right page will not change)
  1344. */
  1345. skip = split->index;
  1346. /* if insert into middle, shift right remaining entries */
  1347. if (skip != nextindex)
  1348. memmove(&rp->xad[skip + 1], &rp->xad[skip],
  1349. (nextindex - skip) * sizeof(xad_t));
  1350. xad = &rp->xad[skip];
  1351. XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
  1352. /* update page header */
  1353. rp->header.nextindex = cpu_to_le16(nextindex + 1);
  1354. if (!test_cflag(COMMIT_Nolink, ip)) {
  1355. tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
  1356. xtlck = (struct xtlock *) & tlck->lock;
  1357. xtlck->lwm.offset = XTENTRYSTART;
  1358. xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
  1359. XTENTRYSTART;
  1360. }
  1361. /*
  1362. * reset the root
  1363. *
  1364. * init root with the single entry for the new right page
  1365. * set the 1st entry offset to 0, which force the left-most key
  1366. * at any level of the tree to be less than any search key.
  1367. */
  1368. /*
  1369. * acquire a transaction lock on the root page (in-memory inode);
  1370. *
  1371. * action: root split;
  1372. */
  1373. BT_MARK_DIRTY(split->mp, ip);
  1374. xad = &sp->xad[XTENTRYSTART];
  1375. XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn);
  1376. /* update page header of root */
  1377. sp->header.flag &= ~BT_LEAF;
  1378. sp->header.flag |= BT_INTERNAL;
  1379. sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
  1380. if (!test_cflag(COMMIT_Nolink, ip)) {
  1381. tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
  1382. xtlck = (struct xtlock *) & tlck->lock;
  1383. xtlck->lwm.offset = XTENTRYSTART;
  1384. xtlck->lwm.length = 1;
  1385. }
  1386. *rmpp = rmp;
  1387. jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp);
  1388. return 0;
  1389. }
  1390. /*
  1391. * xtExtend()
  1392. *
  1393. * function: extend in-place;
  1394. *
  1395. * note: existing extent may or may not have been committed.
  1396. * caller is responsible for pager buffer cache update, and
  1397. * working block allocation map update;
  1398. * update pmap: alloc whole extended extent;
  1399. */
  1400. int xtExtend(tid_t tid, /* transaction id */
  1401. struct inode *ip, s64 xoff, /* delta extent offset */
  1402. s32 xlen, /* delta extent length */
  1403. int flag)
  1404. {
  1405. int rc = 0;
  1406. int cmp;
  1407. struct metapage *mp; /* meta-page buffer */
  1408. xtpage_t *p; /* base B+-tree index page */
  1409. s64 bn;
  1410. int index, nextindex, len;
  1411. struct btstack btstack; /* traverse stack */
  1412. struct xtsplit split; /* split information */
  1413. xad_t *xad;
  1414. s64 xaddr;
  1415. struct tlock *tlck;
  1416. struct xtlock *xtlck = NULL;
  1417. jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
  1418. /* there must exist extent to be extended */
  1419. if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT)))
  1420. return rc;
  1421. /* retrieve search result */
  1422. XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  1423. if (cmp != 0) {
  1424. XT_PUTPAGE(mp);
  1425. jfs_error(ip->i_sb, "xtExtend: xtSearch did not find extent");
  1426. return -EIO;
  1427. }
  1428. /* extension must be contiguous */
  1429. xad = &p->xad[index];
  1430. if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) {
  1431. XT_PUTPAGE(mp);
  1432. jfs_error(ip->i_sb, "xtExtend: extension is not contiguous");
  1433. return -EIO;
  1434. }
  1435. /*
  1436. * acquire a transaction lock on the leaf page;
  1437. *
  1438. * action: xad insertion/extension;
  1439. */
  1440. BT_MARK_DIRTY(mp, ip);
  1441. if (!test_cflag(COMMIT_Nolink, ip)) {
  1442. tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
  1443. xtlck = (struct xtlock *) & tlck->lock;
  1444. }
  1445. /* extend will overflow extent ? */
  1446. xlen = lengthXAD(xad) + xlen;
  1447. if ((len = xlen - MAXXLEN) <= 0)
  1448. goto extendOld;
  1449. /*
  1450. * extent overflow: insert entry for new extent
  1451. */
  1452. //insertNew:
  1453. xoff = offsetXAD(xad) + MAXXLEN;
  1454. xaddr = addressXAD(xad) + MAXXLEN;
  1455. nextindex = le16_to_cpu(p->header.nextindex);
  1456. /*
  1457. * if the leaf page is full, insert the new entry and
  1458. * propagate up the router entry for the new page from split
  1459. *
  1460. * The xtSplitUp() will insert the entry and unpin the leaf page.
  1461. */
  1462. if (nextindex == le16_to_cpu(p->header.maxentry)) {
  1463. /* xtSpliUp() unpins leaf pages */
  1464. split.mp = mp;
  1465. split.index = index + 1;
  1466. split.flag = XAD_NEW;
  1467. split.off = xoff; /* split offset */
  1468. split.len = len;
  1469. split.addr = xaddr;
  1470. split.pxdlist = NULL;
  1471. if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
  1472. return rc;
  1473. /* get back old page */
  1474. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  1475. if (rc)
  1476. return rc;
  1477. /*
  1478. * if leaf root has been split, original root has been
  1479. * copied to new child page, i.e., original entry now
  1480. * resides on the new child page;
  1481. */
  1482. if (p->header.flag & BT_INTERNAL) {
  1483. ASSERT(p->header.nextindex ==
  1484. cpu_to_le16(XTENTRYSTART + 1));
  1485. xad = &p->xad[XTENTRYSTART];
  1486. bn = addressXAD(xad);
  1487. XT_PUTPAGE(mp);
  1488. /* get new child page */
  1489. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  1490. if (rc)
  1491. return rc;
  1492. BT_MARK_DIRTY(mp, ip);
  1493. if (!test_cflag(COMMIT_Nolink, ip)) {
  1494. tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
  1495. xtlck = (struct xtlock *) & tlck->lock;
  1496. }
  1497. }
  1498. }
  1499. /*
  1500. * insert the new entry into the leaf page
  1501. */
  1502. else {
  1503. /* insert the new entry: mark the entry NEW */
  1504. xad = &p->xad[index + 1];
  1505. XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr);
  1506. /* advance next available entry index */
  1507. p->header.nextindex =
  1508. cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
  1509. }
  1510. /* get back old entry */
  1511. xad = &p->xad[index];
  1512. xlen = MAXXLEN;
  1513. /*
  1514. * extend old extent
  1515. */
  1516. extendOld:
  1517. XADlength(xad, xlen);
  1518. if (!(xad->flag & XAD_NEW))
  1519. xad->flag |= XAD_EXTENDED;
  1520. if (!test_cflag(COMMIT_Nolink, ip)) {
  1521. xtlck->lwm.offset =
  1522. (xtlck->lwm.offset) ? min(index,
  1523. (int)xtlck->lwm.offset) : index;
  1524. xtlck->lwm.length =
  1525. le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
  1526. }
  1527. /* unpin the leaf page */
  1528. XT_PUTPAGE(mp);
  1529. return rc;
  1530. }
  1531. #ifdef _NOTYET
  1532. /*
  1533. * xtTailgate()
  1534. *
  1535. * function: split existing 'tail' extent
  1536. * (split offset >= start offset of tail extent), and
  1537. * relocate and extend the split tail half;
  1538. *
  1539. * note: existing extent may or may not have been committed.
  1540. * caller is responsible for pager buffer cache update, and
  1541. * working block allocation map update;
  1542. * update pmap: free old split tail extent, alloc new extent;
  1543. */
  1544. int xtTailgate(tid_t tid, /* transaction id */
  1545. struct inode *ip, s64 xoff, /* split/new extent offset */
  1546. s32 xlen, /* new extent length */
  1547. s64 xaddr, /* new extent address */
  1548. int flag)
  1549. {
  1550. int rc = 0;
  1551. int cmp;
  1552. struct metapage *mp; /* meta-page buffer */
  1553. xtpage_t *p; /* base B+-tree index page */
  1554. s64 bn;
  1555. int index, nextindex, llen, rlen;
  1556. struct btstack btstack; /* traverse stack */
  1557. struct xtsplit split; /* split information */
  1558. xad_t *xad;
  1559. struct tlock *tlck;
  1560. struct xtlock *xtlck = 0;
  1561. struct tlock *mtlck;
  1562. struct maplock *pxdlock;
  1563. /*
  1564. printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
  1565. (ulong)xoff, xlen, (ulong)xaddr);
  1566. */
  1567. /* there must exist extent to be tailgated */
  1568. if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT)))
  1569. return rc;
  1570. /* retrieve search result */
  1571. XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  1572. if (cmp != 0) {
  1573. XT_PUTPAGE(mp);
  1574. jfs_error(ip->i_sb, "xtTailgate: couldn't find extent");
  1575. return -EIO;
  1576. }
  1577. /* entry found must be last entry */
  1578. nextindex = le16_to_cpu(p->header.nextindex);
  1579. if (index != nextindex - 1) {
  1580. XT_PUTPAGE(mp);
  1581. jfs_error(ip->i_sb,
  1582. "xtTailgate: the entry found is not the last entry");
  1583. return -EIO;
  1584. }
  1585. BT_MARK_DIRTY(mp, ip);
  1586. /*
  1587. * acquire tlock of the leaf page containing original entry
  1588. */
  1589. if (!test_cflag(COMMIT_Nolink, ip)) {
  1590. tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
  1591. xtlck = (struct xtlock *) & tlck->lock;
  1592. }
  1593. /* completely replace extent ? */
  1594. xad = &p->xad[index];
  1595. /*
  1596. printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n",
  1597. (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad));
  1598. */
  1599. if ((llen = xoff - offsetXAD(xad)) == 0)
  1600. goto updateOld;
  1601. /*
  1602. * partially replace extent: insert entry for new extent
  1603. */
  1604. //insertNew:
  1605. /*
  1606. * if the leaf page is full, insert the new entry and
  1607. * propagate up the router entry for the new page from split
  1608. *
  1609. * The xtSplitUp() will insert the entry and unpin the leaf page.
  1610. */
  1611. if (nextindex == le16_to_cpu(p->header.maxentry)) {
  1612. /* xtSpliUp() unpins leaf pages */
  1613. split.mp = mp;
  1614. split.index = index + 1;
  1615. split.flag = XAD_NEW;
  1616. split.off = xoff; /* split offset */
  1617. split.len = xlen;
  1618. split.addr = xaddr;
  1619. split.pxdlist = NULL;
  1620. if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
  1621. return rc;
  1622. /* get back old page */
  1623. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  1624. if (rc)
  1625. return rc;
  1626. /*
  1627. * if leaf root has been split, original root has been
  1628. * copied to new child page, i.e., original entry now
  1629. * resides on the new child page;
  1630. */
  1631. if (p->header.flag & BT_INTERNAL) {
  1632. ASSERT(p->header.nextindex ==
  1633. cpu_to_le16(XTENTRYSTART + 1));
  1634. xad = &p->xad[XTENTRYSTART];
  1635. bn = addressXAD(xad);
  1636. XT_PUTPAGE(mp);
  1637. /* get new child page */
  1638. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  1639. if (rc)
  1640. return rc;
  1641. BT_MARK_DIRTY(mp, ip);
  1642. if (!test_cflag(COMMIT_Nolink, ip)) {
  1643. tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
  1644. xtlck = (struct xtlock *) & tlck->lock;
  1645. }
  1646. }
  1647. }
  1648. /*
  1649. * insert the new entry into the leaf page
  1650. */
  1651. else {
  1652. /* insert the new entry: mark the entry NEW */
  1653. xad = &p->xad[index + 1];
  1654. XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
  1655. /* advance next available entry index */
  1656. p->header.nextindex =
  1657. cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
  1658. }
  1659. /* get back old XAD */
  1660. xad = &p->xad[index];
  1661. /*
  1662. * truncate/relocate old extent at split offset
  1663. */
  1664. updateOld:
  1665. /* update dmap for old/committed/truncated extent */
  1666. rlen = lengthXAD(xad) - llen;
  1667. if (!(xad->flag & XAD_NEW)) {
  1668. /* free from PWMAP at commit */
  1669. if (!test_cflag(COMMIT_Nolink, ip)) {
  1670. mtlck = txMaplock(tid, ip, tlckMAP);
  1671. pxdlock = (struct maplock *) & mtlck->lock;
  1672. pxdlock->flag = mlckFREEPXD;
  1673. PXDaddress(&pxdlock->pxd, addressXAD(xad) + llen);
  1674. PXDlength(&pxdlock->pxd, rlen);
  1675. pxdlock->index = 1;
  1676. }
  1677. } else
  1678. /* free from WMAP */
  1679. dbFree(ip, addressXAD(xad) + llen, (s64) rlen);
  1680. if (llen)
  1681. /* truncate */
  1682. XADlength(xad, llen);
  1683. else
  1684. /* replace */
  1685. XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
  1686. if (!test_cflag(COMMIT_Nolink, ip)) {
  1687. xtlck->lwm.offset = (xtlck->lwm.offset) ?
  1688. min(index, (int)xtlck->lwm.offset) : index;
  1689. xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
  1690. xtlck->lwm.offset;
  1691. }
  1692. /* unpin the leaf page */
  1693. XT_PUTPAGE(mp);
  1694. return rc;
  1695. }
  1696. #endif /* _NOTYET */
  1697. /*
  1698. * xtUpdate()
  1699. *
  1700. * function: update XAD;
  1701. *
  1702. * update extent for allocated_but_not_recorded or
  1703. * compressed extent;
  1704. *
  1705. * parameter:
  1706. * nxad - new XAD;
  1707. * logical extent of the specified XAD must be completely
  1708. * contained by an existing XAD;
  1709. */
  1710. int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
  1711. { /* new XAD */
  1712. int rc = 0;
  1713. int cmp;
  1714. struct metapage *mp; /* meta-page buffer */
  1715. xtpage_t *p; /* base B+-tree index page */
  1716. s64 bn;
  1717. int index0, index, newindex, nextindex;
  1718. struct btstack btstack; /* traverse stack */
  1719. struct xtsplit split; /* split information */
  1720. xad_t *xad, *lxad, *rxad;
  1721. int xflag;
  1722. s64 nxoff, xoff;
  1723. int nxlen, xlen, lxlen, rxlen;
  1724. s64 nxaddr, xaddr;
  1725. struct tlock *tlck;
  1726. struct xtlock *xtlck = NULL;
  1727. int newpage = 0;
  1728. /* there must exist extent to be tailgated */
  1729. nxoff = offsetXAD(nxad);
  1730. nxlen = lengthXAD(nxad);
  1731. nxaddr = addressXAD(nxad);
  1732. if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
  1733. return rc;
  1734. /* retrieve search result */
  1735. XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
  1736. if (cmp != 0) {
  1737. XT_PUTPAGE(mp);
  1738. jfs_error(ip->i_sb, "xtUpdate: Could not find extent");
  1739. return -EIO;
  1740. }
  1741. BT_MARK_DIRTY(mp, ip);
  1742. /*
  1743. * acquire tlock of the leaf page containing original entry
  1744. */
  1745. if (!test_cflag(COMMIT_Nolink, ip)) {
  1746. tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
  1747. xtlck = (struct xtlock *) & tlck->lock;
  1748. }
  1749. xad = &p->xad[index0];
  1750. xflag = xad->flag;
  1751. xoff = offsetXAD(xad);
  1752. xlen = lengthXAD(xad);
  1753. xaddr = addressXAD(xad);
  1754. /* nXAD must be completely contained within XAD */
  1755. if ((xoff > nxoff) ||
  1756. (nxoff + nxlen > xoff + xlen)) {
  1757. XT_PUTPAGE(mp);
  1758. jfs_error(ip->i_sb,
  1759. "xtUpdate: nXAD in not completely contained within XAD");
  1760. return -EIO;
  1761. }
  1762. index = index0;
  1763. newindex = index + 1;
  1764. nextindex = le16_to_cpu(p->header.nextindex);
  1765. #ifdef _JFS_WIP_NOCOALESCE
  1766. if (xoff < nxoff)
  1767. goto updateRight;
  1768. /*
  1769. * replace XAD with nXAD
  1770. */
  1771. replace: /* (nxoff == xoff) */
  1772. if (nxlen == xlen) {
  1773. /* replace XAD with nXAD:recorded */
  1774. *xad = *nxad;
  1775. xad->flag = xflag & ~XAD_NOTRECORDED;
  1776. goto out;
  1777. } else /* (nxlen < xlen) */
  1778. goto updateLeft;
  1779. #endif /* _JFS_WIP_NOCOALESCE */
  1780. /* #ifdef _JFS_WIP_COALESCE */
  1781. if (xoff < nxoff)
  1782. goto coalesceRight;
  1783. /*
  1784. * coalesce with left XAD
  1785. */
  1786. //coalesceLeft: /* (xoff == nxoff) */
  1787. /* is XAD first entry of page ? */
  1788. if (index == XTENTRYSTART)
  1789. goto replace;
  1790. /* is nXAD logically and physically contiguous with lXAD ? */
  1791. lxad = &p->xad[index - 1];
  1792. lxlen = lengthXAD(lxad);
  1793. if (!(lxad->flag & XAD_NOTRECORDED) &&
  1794. (nxoff == offsetXAD(lxad) + lxlen) &&
  1795. (nxaddr == addressXAD(lxad) + lxlen) &&
  1796. (lxlen + nxlen < MAXXLEN)) {
  1797. /* extend right lXAD */
  1798. index0 = index - 1;
  1799. XADlength(lxad, lxlen + nxlen);
  1800. /* If we just merged two extents together, need to make sure the
  1801. * right extent gets logged. If the left one is marked XAD_NEW,
  1802. * then we know it will be logged. Otherwise, mark as
  1803. * XAD_EXTENDED
  1804. */
  1805. if (!(lxad->flag & XAD_NEW))
  1806. lxad->flag |= XAD_EXTENDED;
  1807. if (xlen > nxlen) {
  1808. /* truncate XAD */
  1809. XADoffset(xad, xoff + nxlen);
  1810. XADlength(xad, xlen - nxlen);
  1811. XADaddress(xad, xaddr + nxlen);
  1812. goto out;
  1813. } else { /* (xlen == nxlen) */
  1814. /* remove XAD */
  1815. if (index < nextindex - 1)
  1816. memmove(&p->xad[index], &p->xad[index + 1],
  1817. (nextindex - index -
  1818. 1) << L2XTSLOTSIZE);
  1819. p->header.nextindex =
  1820. cpu_to_le16(le16_to_cpu(p->header.nextindex) -
  1821. 1);
  1822. index = index0;
  1823. newindex = index + 1;
  1824. nextindex = le16_to_cpu(p->header.nextindex);
  1825. xoff = nxoff = offsetXAD(lxad);
  1826. xlen = nxlen = lxlen + nxlen;
  1827. xaddr = nxaddr = addressXAD(lxad);
  1828. goto coalesceRight;
  1829. }
  1830. }
  1831. /*
  1832. * replace XAD with nXAD
  1833. */
  1834. replace: /* (nxoff == xoff) */
  1835. if (nxlen == xlen) {
  1836. /* replace XAD with nXAD:recorded */
  1837. *xad = *nxad;
  1838. xad->flag = xflag & ~XAD_NOTRECORDED;
  1839. goto coalesceRight;
  1840. } else /* (nxlen < xlen) */
  1841. goto updateLeft;
  1842. /*
  1843. * coalesce with right XAD
  1844. */
  1845. coalesceRight: /* (xoff <= nxoff) */
  1846. /* is XAD last entry of page ? */
  1847. if (newindex == nextindex) {
  1848. if (xoff == nxoff)
  1849. goto out;
  1850. goto updateRight;
  1851. }
  1852. /* is nXAD logically and physically contiguous with rXAD ? */
  1853. rxad = &p->xad[index + 1];
  1854. rxlen = lengthXAD(rxad);
  1855. if (!(rxad->flag & XAD_NOTRECORDED) &&
  1856. (nxoff + nxlen == offsetXAD(rxad)) &&
  1857. (nxaddr + nxlen == addressXAD(rxad)) &&
  1858. (rxlen + nxlen < MAXXLEN)) {
  1859. /* extend left rXAD */
  1860. XADoffset(rxad, nxoff);
  1861. XADlength(rxad, rxlen + nxlen);
  1862. XADaddress(rxad, nxaddr);
  1863. /* If we just merged two extents together, need to make sure
  1864. * the left extent gets logged. If the right one is marked
  1865. * XAD_NEW, then we know it will be logged. Otherwise, mark as
  1866. * XAD_EXTENDED
  1867. */
  1868. if (!(rxad->flag & XAD_NEW))
  1869. rxad->flag |= XAD_EXTENDED;
  1870. if (xlen > nxlen)
  1871. /* truncate XAD */
  1872. XADlength(xad, xlen - nxlen);
  1873. else { /* (xlen == nxlen) */
  1874. /* remove XAD */
  1875. memmove(&p->xad[index], &p->xad[index + 1],
  1876. (nextindex - index - 1) << L2XTSLOTSIZE);
  1877. p->header.nextindex =
  1878. cpu_to_le16(le16_to_cpu(p->header.nextindex) -
  1879. 1);
  1880. }
  1881. goto out;
  1882. } else if (xoff == nxoff)
  1883. goto out;
  1884. if (xoff >= nxoff) {
  1885. XT_PUTPAGE(mp);
  1886. jfs_error(ip->i_sb, "xtUpdate: xoff >= nxoff");
  1887. return -EIO;
  1888. }
  1889. /* #endif _JFS_WIP_COALESCE */
  1890. /*
  1891. * split XAD into (lXAD, nXAD):
  1892. *
  1893. * |---nXAD--->
  1894. * --|----------XAD----------|--
  1895. * |-lXAD-|
  1896. */
  1897. updateRight: /* (xoff < nxoff) */
  1898. /* truncate old XAD as lXAD:not_recorded */
  1899. xad = &p->xad[index];
  1900. XADlength(xad, nxoff - xoff);
  1901. /* insert nXAD:recorded */
  1902. if (nextindex == le16_to_cpu(p->header.maxentry)) {
  1903. /* xtSpliUp() unpins leaf pages */
  1904. split.mp = mp;
  1905. split.index = newindex;
  1906. split.flag = xflag & ~XAD_NOTRECORDED;
  1907. split.off = nxoff;
  1908. split.len = nxlen;
  1909. split.addr = nxaddr;
  1910. split.pxdlist = NULL;
  1911. if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
  1912. return rc;
  1913. /* get back old page */
  1914. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  1915. if (rc)
  1916. return rc;
  1917. /*
  1918. * if leaf root has been split, original root has been
  1919. * copied to new child page, i.e., original entry now
  1920. * resides on the new child page;
  1921. */
  1922. if (p->header.flag & BT_INTERNAL) {
  1923. ASSERT(p->header.nextindex ==
  1924. cpu_to_le16(XTENTRYSTART + 1));
  1925. xad = &p->xad[XTENTRYSTART];
  1926. bn = addressXAD(xad);
  1927. XT_PUTPAGE(mp);
  1928. /* get new child page */
  1929. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  1930. if (rc)
  1931. return rc;
  1932. BT_MARK_DIRTY(mp, ip);
  1933. if (!test_cflag(COMMIT_Nolink, ip)) {
  1934. tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
  1935. xtlck = (struct xtlock *) & tlck->lock;
  1936. }
  1937. } else {
  1938. /* is nXAD on new page ? */
  1939. if (newindex >
  1940. (le16_to_cpu(p->header.maxentry) >> 1)) {
  1941. newindex =
  1942. newindex -
  1943. le16_to_cpu(p->header.nextindex) +
  1944. XTENTRYSTART;
  1945. newpage = 1;
  1946. }
  1947. }
  1948. } else {
  1949. /* if insert into middle, shift right remaining entries */
  1950. if (newindex < nextindex)
  1951. memmove(&p->xad[newindex + 1], &p->xad[newindex],
  1952. (nextindex - newindex) << L2XTSLOTSIZE);
  1953. /* insert the entry */
  1954. xad = &p->xad[newindex];
  1955. *xad = *nxad;
  1956. xad->flag = xflag & ~XAD_NOTRECORDED;
  1957. /* advance next available entry index. */
  1958. p->header.nextindex =
  1959. cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
  1960. }
  1961. /*
  1962. * does nXAD force 3-way split ?
  1963. *
  1964. * |---nXAD--->|
  1965. * --|----------XAD-------------|--
  1966. * |-lXAD-| |-rXAD -|
  1967. */
  1968. if (nxoff + nxlen == xoff + xlen)
  1969. goto out;
  1970. /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
  1971. if (newpage) {
  1972. /* close out old page */
  1973. if (!test_cflag(COMMIT_Nolink, ip)) {
  1974. xtlck->lwm.offset = (xtlck->lwm.offset) ?
  1975. min(index0, (int)xtlck->lwm.offset) : index0;
  1976. xtlck->lwm.length =
  1977. le16_to_cpu(p->header.nextindex) -
  1978. xtlck->lwm.offset;
  1979. }
  1980. bn = le64_to_cpu(p->header.next);
  1981. XT_PUTPAGE(mp);
  1982. /* get new right page */
  1983. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  1984. if (rc)
  1985. return rc;
  1986. BT_MARK_DIRTY(mp, ip);
  1987. if (!test_cflag(COMMIT_Nolink, ip)) {
  1988. tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
  1989. xtlck = (struct xtlock *) & tlck->lock;
  1990. }
  1991. index0 = index = newindex;
  1992. } else
  1993. index++;
  1994. newindex = index + 1;
  1995. nextindex = le16_to_cpu(p->header.nextindex);
  1996. xlen = xlen - (nxoff - xoff);
  1997. xoff = nxoff;
  1998. xaddr = nxaddr;
  1999. /* recompute split pages */
  2000. if (nextindex == le16_to_cpu(p->header.maxentry)) {
  2001. XT_PUTPAGE(mp);
  2002. if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
  2003. return rc;
  2004. /* retrieve search result */
  2005. XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
  2006. if (cmp != 0) {
  2007. XT_PUTPAGE(mp);
  2008. jfs_error(ip->i_sb, "xtUpdate: xtSearch failed");
  2009. return -EIO;
  2010. }
  2011. if (index0 != index) {
  2012. XT_PUTPAGE(mp);
  2013. jfs_error(ip->i_sb,
  2014. "xtUpdate: unexpected value of index");
  2015. return -EIO;
  2016. }
  2017. }
  2018. /*
  2019. * split XAD into (nXAD, rXAD)
  2020. *
  2021. * ---nXAD---|
  2022. * --|----------XAD----------|--
  2023. * |-rXAD-|
  2024. */
  2025. updateLeft: /* (nxoff == xoff) && (nxlen < xlen) */
  2026. /* update old XAD with nXAD:recorded */
  2027. xad = &p->xad[index];
  2028. *xad = *nxad;
  2029. xad->flag = xflag & ~XAD_NOTRECORDED;
  2030. /* insert rXAD:not_recorded */
  2031. xoff = xoff + nxlen;
  2032. xlen = xlen - nxlen;
  2033. xaddr = xaddr + nxlen;
  2034. if (nextindex == le16_to_cpu(p->header.maxentry)) {
  2035. /*
  2036. printf("xtUpdate.updateLeft.split p:0x%p\n", p);
  2037. */
  2038. /* xtSpliUp() unpins leaf pages */
  2039. split.mp = mp;
  2040. split.index = newindex;
  2041. split.flag = xflag;
  2042. split.off = xoff;
  2043. split.len = xlen;
  2044. split.addr = xaddr;
  2045. split.pxdlist = NULL;
  2046. if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
  2047. return rc;
  2048. /* get back old page */
  2049. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  2050. if (rc)
  2051. return rc;
  2052. /*
  2053. * if leaf root has been split, original root has been
  2054. * copied to new child page, i.e., original entry now
  2055. * resides on the new child page;
  2056. */
  2057. if (p->header.flag & BT_INTERNAL) {
  2058. ASSERT(p->header.nextindex ==
  2059. cpu_to_le16(XTENTRYSTART + 1));
  2060. xad = &p->xad[XTENTRYSTART];
  2061. bn = addressXAD(xad);
  2062. XT_PUTPAGE(mp);
  2063. /* get new child page */
  2064. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  2065. if (rc)
  2066. return rc;
  2067. BT_MARK_DIRTY(mp, ip);
  2068. if (!test_cflag(COMMIT_Nolink, ip)) {
  2069. tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
  2070. xtlck = (struct xtlock *) & tlck->lock;
  2071. }
  2072. }
  2073. } else {
  2074. /* if insert into middle, shift right remaining entries */
  2075. if (newindex < nextindex)
  2076. memmove(&p->xad[newindex + 1], &p->xad[newindex],
  2077. (nextindex - newindex) << L2XTSLOTSIZE);
  2078. /* insert the entry */
  2079. xad = &p->xad[newindex];
  2080. XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
  2081. /* advance next available entry index. */
  2082. p->header.nextindex =
  2083. cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
  2084. }
  2085. out:
  2086. if (!test_cflag(COMMIT_Nolink, ip)) {
  2087. xtlck->lwm.offset = (xtlck->lwm.offset) ?
  2088. min(index0, (int)xtlck->lwm.offset) : index0;
  2089. xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
  2090. xtlck->lwm.offset;
  2091. }
  2092. /* unpin the leaf page */
  2093. XT_PUTPAGE(mp);
  2094. return rc;
  2095. }
  2096. /*
  2097. * xtAppend()
  2098. *
  2099. * function: grow in append mode from contiguous region specified ;
  2100. *
  2101. * parameter:
  2102. * tid - transaction id;
  2103. * ip - file object;
  2104. * xflag - extent flag:
  2105. * xoff - extent offset;
  2106. * maxblocks - max extent length;
  2107. * xlen - extent length (in/out);
  2108. * xaddrp - extent address pointer (in/out):
  2109. * flag -
  2110. *
  2111. * return:
  2112. */
  2113. int xtAppend(tid_t tid, /* transaction id */
  2114. struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
  2115. s32 * xlenp, /* (in/out) */
  2116. s64 * xaddrp, /* (in/out) */
  2117. int flag)
  2118. {
  2119. int rc = 0;
  2120. struct metapage *mp; /* meta-page buffer */
  2121. xtpage_t *p; /* base B+-tree index page */
  2122. s64 bn, xaddr;
  2123. int index, nextindex;
  2124. struct btstack btstack; /* traverse stack */
  2125. struct xtsplit split; /* split information */
  2126. xad_t *xad;
  2127. int cmp;
  2128. struct tlock *tlck;
  2129. struct xtlock *xtlck;
  2130. int nsplit, nblocks, xlen;
  2131. struct pxdlist pxdlist;
  2132. pxd_t *pxd;
  2133. s64 next;
  2134. xaddr = *xaddrp;
  2135. xlen = *xlenp;
  2136. jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx",
  2137. (ulong) xoff, maxblocks, xlen, (ulong) xaddr);
  2138. /*
  2139. * search for the entry location at which to insert:
  2140. *
  2141. * xtFastSearch() and xtSearch() both returns (leaf page
  2142. * pinned, index at which to insert).
  2143. * n.b. xtSearch() may return index of maxentry of
  2144. * the full page.
  2145. */
  2146. if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
  2147. return rc;
  2148. /* retrieve search result */
  2149. XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  2150. if (cmp == 0) {
  2151. rc = -EEXIST;
  2152. goto out;
  2153. }
  2154. if (next)
  2155. xlen = min(xlen, (int)(next - xoff));
  2156. //insert:
  2157. /*
  2158. * insert entry for new extent
  2159. */
  2160. xflag |= XAD_NEW;
  2161. /*
  2162. * if the leaf page is full, split the page and
  2163. * propagate up the router entry for the new page from split
  2164. *
  2165. * The xtSplitUp() will insert the entry and unpin the leaf page.
  2166. */
  2167. nextindex = le16_to_cpu(p->header.nextindex);
  2168. if (nextindex < le16_to_cpu(p->header.maxentry))
  2169. goto insertLeaf;
  2170. /*
  2171. * allocate new index blocks to cover index page split(s)
  2172. */
  2173. nsplit = btstack.nsplit;
  2174. split.pxdlist = &pxdlist;
  2175. pxdlist.maxnpxd = pxdlist.npxd = 0;
  2176. pxd = &pxdlist.pxd[0];
  2177. nblocks = JFS_SBI(ip->i_sb)->nbperpage;
  2178. for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) {
  2179. if ((rc = dbAllocBottomUp(ip, xaddr, (s64) nblocks)) == 0) {
  2180. PXDaddress(pxd, xaddr);
  2181. PXDlength(pxd, nblocks);
  2182. pxdlist.maxnpxd++;
  2183. continue;
  2184. }
  2185. /* undo allocation */
  2186. goto out;
  2187. }
  2188. xlen = min(xlen, maxblocks);
  2189. /*
  2190. * allocate data extent requested
  2191. */
  2192. if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
  2193. goto out;
  2194. split.mp = mp;
  2195. split.index = index;
  2196. split.flag = xflag;
  2197. split.off = xoff;
  2198. split.len = xlen;
  2199. split.addr = xaddr;
  2200. if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
  2201. /* undo data extent allocation */
  2202. dbFree(ip, *xaddrp, (s64) * xlenp);
  2203. return rc;
  2204. }
  2205. *xaddrp = xaddr;
  2206. *xlenp = xlen;
  2207. return 0;
  2208. /*
  2209. * insert the new entry into the leaf page
  2210. */
  2211. insertLeaf:
  2212. /*
  2213. * allocate data extent requested
  2214. */
  2215. if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
  2216. goto out;
  2217. BT_MARK_DIRTY(mp, ip);
  2218. /*
  2219. * acquire a transaction lock on the leaf page;
  2220. *
  2221. * action: xad insertion/extension;
  2222. */
  2223. tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
  2224. xtlck = (struct xtlock *) & tlck->lock;
  2225. /* insert the new entry: mark the entry NEW */
  2226. xad = &p->xad[index];
  2227. XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
  2228. /* advance next available entry index */
  2229. p->header.nextindex =
  2230. cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
  2231. xtlck->lwm.offset =
  2232. (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index;
  2233. xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
  2234. xtlck->lwm.offset;
  2235. *xaddrp = xaddr;
  2236. *xlenp = xlen;
  2237. out:
  2238. /* unpin the leaf page */
  2239. XT_PUTPAGE(mp);
  2240. return rc;
  2241. }
  2242. #ifdef _STILL_TO_PORT
  2243. /* - TBD for defragmentaion/reorganization -
  2244. *
  2245. * xtDelete()
  2246. *
  2247. * function:
  2248. * delete the entry with the specified key.
  2249. *
  2250. * N.B.: whole extent of the entry is assumed to be deleted.
  2251. *
  2252. * parameter:
  2253. *
  2254. * return:
  2255. * ENOENT: if the entry is not found.
  2256. *
  2257. * exception:
  2258. */
  2259. int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag)
  2260. {
  2261. int rc = 0;
  2262. struct btstack btstack;
  2263. int cmp;
  2264. s64 bn;
  2265. struct metapage *mp;
  2266. xtpage_t *p;
  2267. int index, nextindex;
  2268. struct tlock *tlck;
  2269. struct xtlock *xtlck;
  2270. /*
  2271. * find the matching entry; xtSearch() pins the page
  2272. */
  2273. if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
  2274. return rc;
  2275. XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  2276. if (cmp) {
  2277. /* unpin the leaf page */
  2278. XT_PUTPAGE(mp);
  2279. return -ENOENT;
  2280. }
  2281. /*
  2282. * delete the entry from the leaf page
  2283. */
  2284. nextindex = le16_to_cpu(p->header.nextindex);
  2285. p->header.nextindex =
  2286. cpu_to_le16(le16_to_cpu(p->header.nextindex) - 1);
  2287. /*
  2288. * if the leaf page bocome empty, free the page
  2289. */
  2290. if (p->header.nextindex == cpu_to_le16(XTENTRYSTART))
  2291. return (xtDeleteUp(tid, ip, mp, p, &btstack));
  2292. BT_MARK_DIRTY(mp, ip);
  2293. /*
  2294. * acquire a transaction lock on the leaf page;
  2295. *
  2296. * action:xad deletion;
  2297. */
  2298. tlck = txLock(tid, ip, mp, tlckXTREE);
  2299. xtlck = (struct xtlock *) & tlck->lock;
  2300. xtlck->lwm.offset =
  2301. (xtlck->lwm.offset) ? min(index, xtlck->lwm.offset) : index;
  2302. /* if delete from middle, shift left/compact the remaining entries */
  2303. if (index < nextindex - 1)
  2304. memmove(&p->xad[index], &p->xad[index + 1],
  2305. (nextindex - index - 1) * sizeof(xad_t));
  2306. XT_PUTPAGE(mp);
  2307. return 0;
  2308. }
  2309. /* - TBD for defragmentaion/reorganization -
  2310. *
  2311. * xtDeleteUp()
  2312. *
  2313. * function:
  2314. * free empty pages as propagating deletion up the tree
  2315. *
  2316. * parameter:
  2317. *
  2318. * return:
  2319. */
  2320. static int
  2321. xtDeleteUp(tid_t tid, struct inode *ip,
  2322. struct metapage * fmp, xtpage_t * fp, struct btstack * btstack)
  2323. {
  2324. int rc = 0;
  2325. struct metapage *mp;
  2326. xtpage_t *p;
  2327. int index, nextindex;
  2328. s64 xaddr;
  2329. int xlen;
  2330. struct btframe *parent;
  2331. struct tlock *tlck;
  2332. struct xtlock *xtlck;
  2333. /*
  2334. * keep root leaf page which has become empty
  2335. */
  2336. if (fp->header.flag & BT_ROOT) {
  2337. /* keep the root page */
  2338. fp->header.flag &= ~BT_INTERNAL;
  2339. fp->header.flag |= BT_LEAF;
  2340. fp->header.nextindex = cpu_to_le16(XTENTRYSTART);
  2341. /* XT_PUTPAGE(fmp); */
  2342. return 0;
  2343. }
  2344. /*
  2345. * free non-root leaf page
  2346. */
  2347. if ((rc = xtRelink(tid, ip, fp))) {
  2348. XT_PUTPAGE(fmp);
  2349. return rc;
  2350. }
  2351. xaddr = addressPXD(&fp->header.self);
  2352. xlen = lengthPXD(&fp->header.self);
  2353. /* free the page extent */
  2354. dbFree(ip, xaddr, (s64) xlen);
  2355. /* free the buffer page */
  2356. discard_metapage(fmp);
  2357. /*
  2358. * propagate page deletion up the index tree
  2359. *
  2360. * If the delete from the parent page makes it empty,
  2361. * continue all the way up the tree.
  2362. * stop if the root page is reached (which is never deleted) or
  2363. * if the entry deletion does not empty the page.
  2364. */
  2365. while ((parent = BT_POP(btstack)) != NULL) {
  2366. /* get/pin the parent page <sp> */
  2367. XT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc);
  2368. if (rc)
  2369. return rc;
  2370. index = parent->index;
  2371. /* delete the entry for the freed child page from parent.
  2372. */
  2373. nextindex = le16_to_cpu(p->header.nextindex);
  2374. /*
  2375. * the parent has the single entry being deleted:
  2376. * free the parent page which has become empty.
  2377. */
  2378. if (nextindex == 1) {
  2379. if (p->header.flag & BT_ROOT) {
  2380. /* keep the root page */
  2381. p->header.flag &= ~BT_INTERNAL;
  2382. p->header.flag |= BT_LEAF;
  2383. p->header.nextindex =
  2384. cpu_to_le16(XTENTRYSTART);
  2385. /* XT_PUTPAGE(mp); */
  2386. break;
  2387. } else {
  2388. /* free the parent page */
  2389. if ((rc = xtRelink(tid, ip, p)))
  2390. return rc;
  2391. xaddr = addressPXD(&p->header.self);
  2392. /* free the page extent */
  2393. dbFree(ip, xaddr,
  2394. (s64) JFS_SBI(ip->i_sb)->nbperpage);
  2395. /* unpin/free the buffer page */
  2396. discard_metapage(mp);
  2397. /* propagate up */
  2398. continue;
  2399. }
  2400. }
  2401. /*
  2402. * the parent has other entries remaining:
  2403. * delete the router entry from the parent page.
  2404. */
  2405. else {
  2406. BT_MARK_DIRTY(mp, ip);
  2407. /*
  2408. * acquire a transaction lock on the leaf page;
  2409. *
  2410. * action:xad deletion;
  2411. */
  2412. tlck = txLock(tid, ip, mp, tlckXTREE);
  2413. xtlck = (struct xtlock *) & tlck->lock;
  2414. xtlck->lwm.offset =
  2415. (xtlck->lwm.offset) ? min(index,
  2416. xtlck->lwm.
  2417. offset) : index;
  2418. /* if delete from middle,
  2419. * shift left/compact the remaining entries in the page
  2420. */
  2421. if (index < nextindex - 1)
  2422. memmove(&p->xad[index], &p->xad[index + 1],
  2423. (nextindex - index -
  2424. 1) << L2XTSLOTSIZE);
  2425. p->header.nextindex =
  2426. cpu_to_le16(le16_to_cpu(p->header.nextindex) -
  2427. 1);
  2428. jfs_info("xtDeleteUp(entry): 0x%lx[%d]",
  2429. (ulong) parent->bn, index);
  2430. }
  2431. /* unpin the parent page */
  2432. XT_PUTPAGE(mp);
  2433. /* exit propagation up */
  2434. break;
  2435. }
  2436. return 0;
  2437. }
  2438. /*
  2439. * NAME: xtRelocate()
  2440. *
  2441. * FUNCTION: relocate xtpage or data extent of regular file;
  2442. * This function is mainly used by defragfs utility.
  2443. *
  2444. * NOTE: This routine does not have the logic to handle
  2445. * uncommitted allocated extent. The caller should call
  2446. * txCommit() to commit all the allocation before call
  2447. * this routine.
  2448. */
  2449. int
  2450. xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */
  2451. s64 nxaddr, /* new xaddr */
  2452. int xtype)
  2453. { /* extent type: XTPAGE or DATAEXT */
  2454. int rc = 0;
  2455. struct tblock *tblk;
  2456. struct tlock *tlck;
  2457. struct xtlock *xtlck;
  2458. struct metapage *mp, *pmp, *lmp, *rmp; /* meta-page buffer */
  2459. xtpage_t *p, *pp, *rp, *lp; /* base B+-tree index page */
  2460. xad_t *xad;
  2461. pxd_t *pxd;
  2462. s64 xoff, xsize;
  2463. int xlen;
  2464. s64 oxaddr, sxaddr, dxaddr, nextbn, prevbn;
  2465. cbuf_t *cp;
  2466. s64 offset, nbytes, nbrd, pno;
  2467. int nb, npages, nblks;
  2468. s64 bn;
  2469. int cmp;
  2470. int index;
  2471. struct pxd_lock *pxdlock;
  2472. struct btstack btstack; /* traverse stack */
  2473. xtype = xtype & EXTENT_TYPE;
  2474. xoff = offsetXAD(oxad);
  2475. oxaddr = addressXAD(oxad);
  2476. xlen = lengthXAD(oxad);
  2477. /* validate extent offset */
  2478. offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
  2479. if (offset >= ip->i_size)
  2480. return -ESTALE; /* stale extent */
  2481. jfs_info("xtRelocate: xtype:%d xoff:0x%lx xlen:0x%x xaddr:0x%lx:0x%lx",
  2482. xtype, (ulong) xoff, xlen, (ulong) oxaddr, (ulong) nxaddr);
  2483. /*
  2484. * 1. get and validate the parent xtpage/xad entry
  2485. * covering the source extent to be relocated;
  2486. */
  2487. if (xtype == DATAEXT) {
  2488. /* search in leaf entry */
  2489. rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
  2490. if (rc)
  2491. return rc;
  2492. /* retrieve search result */
  2493. XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
  2494. if (cmp) {
  2495. XT_PUTPAGE(pmp);
  2496. return -ESTALE;
  2497. }
  2498. /* validate for exact match with a single entry */
  2499. xad = &pp->xad[index];
  2500. if (addressXAD(xad) != oxaddr || lengthXAD(xad) != xlen) {
  2501. XT_PUTPAGE(pmp);
  2502. return -ESTALE;
  2503. }
  2504. } else { /* (xtype == XTPAGE) */
  2505. /* search in internal entry */
  2506. rc = xtSearchNode(ip, oxad, &cmp, &btstack, 0);
  2507. if (rc)
  2508. return rc;
  2509. /* retrieve search result */
  2510. XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
  2511. if (cmp) {
  2512. XT_PUTPAGE(pmp);
  2513. return -ESTALE;
  2514. }
  2515. /* xtSearchNode() validated for exact match with a single entry
  2516. */
  2517. xad = &pp->xad[index];
  2518. }
  2519. jfs_info("xtRelocate: parent xad entry validated.");
  2520. /*
  2521. * 2. relocate the extent
  2522. */
  2523. if (xtype == DATAEXT) {
  2524. /* if the extent is allocated-but-not-recorded
  2525. * there is no real data to be moved in this extent,
  2526. */
  2527. if (xad->flag & XAD_NOTRECORDED)
  2528. goto out;
  2529. else
  2530. /* release xtpage for cmRead()/xtLookup() */
  2531. XT_PUTPAGE(pmp);
  2532. /*
  2533. * cmRelocate()
  2534. *
  2535. * copy target data pages to be relocated;
  2536. *
  2537. * data extent must start at page boundary and
  2538. * multiple of page size (except the last data extent);
  2539. * read in each page of the source data extent into cbuf,
  2540. * update the cbuf extent descriptor of the page to be
  2541. * homeward bound to new dst data extent
  2542. * copy the data from the old extent to new extent.
  2543. * copy is essential for compressed files to avoid problems
  2544. * that can arise if there was a change in compression
  2545. * algorithms.
  2546. * it is a good strategy because it may disrupt cache
  2547. * policy to keep the pages in memory afterwards.
  2548. */
  2549. offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
  2550. assert((offset & CM_OFFSET) == 0);
  2551. nbytes = xlen << JFS_SBI(ip->i_sb)->l2bsize;
  2552. pno = offset >> CM_L2BSIZE;
  2553. npages = (nbytes + (CM_BSIZE - 1)) >> CM_L2BSIZE;
  2554. /*
  2555. npages = ((offset + nbytes - 1) >> CM_L2BSIZE) -
  2556. (offset >> CM_L2BSIZE) + 1;
  2557. */
  2558. sxaddr = oxaddr;
  2559. dxaddr = nxaddr;
  2560. /* process the request one cache buffer at a time */
  2561. for (nbrd = 0; nbrd < nbytes; nbrd += nb,
  2562. offset += nb, pno++, npages--) {
  2563. /* compute page size */
  2564. nb = min(nbytes - nbrd, CM_BSIZE);
  2565. /* get the cache buffer of the page */
  2566. if (rc = cmRead(ip, offset, npages, &cp))
  2567. break;
  2568. assert(addressPXD(&cp->cm_pxd) == sxaddr);
  2569. assert(!cp->cm_modified);
  2570. /* bind buffer with the new extent address */
  2571. nblks = nb >> JFS_IP(ip->i_sb)->l2bsize;
  2572. cmSetXD(ip, cp, pno, dxaddr, nblks);
  2573. /* release the cbuf, mark it as modified */
  2574. cmPut(cp, true);
  2575. dxaddr += nblks;
  2576. sxaddr += nblks;
  2577. }
  2578. /* get back parent page */
  2579. if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
  2580. return rc;
  2581. XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
  2582. jfs_info("xtRelocate: target data extent relocated.");
  2583. } else { /* (xtype == XTPAGE) */
  2584. /*
  2585. * read in the target xtpage from the source extent;
  2586. */
  2587. XT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc);
  2588. if (rc) {
  2589. XT_PUTPAGE(pmp);
  2590. return rc;
  2591. }
  2592. /*
  2593. * read in sibling pages if any to update sibling pointers;
  2594. */
  2595. rmp = NULL;
  2596. if (p->header.next) {
  2597. nextbn = le64_to_cpu(p->header.next);
  2598. XT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc);
  2599. if (rc) {
  2600. XT_PUTPAGE(pmp);
  2601. XT_PUTPAGE(mp);
  2602. return (rc);
  2603. }
  2604. }
  2605. lmp = NULL;
  2606. if (p->header.prev) {
  2607. prevbn = le64_to_cpu(p->header.prev);
  2608. XT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc);
  2609. if (rc) {
  2610. XT_PUTPAGE(pmp);
  2611. XT_PUTPAGE(mp);
  2612. if (rmp)
  2613. XT_PUTPAGE(rmp);
  2614. return (rc);
  2615. }
  2616. }
  2617. /* at this point, all xtpages to be updated are in memory */
  2618. /*
  2619. * update sibling pointers of sibling xtpages if any;
  2620. */
  2621. if (lmp) {
  2622. BT_MARK_DIRTY(lmp, ip);
  2623. tlck =
  2624. txLock(tid, ip, lmp, tlckXTREE | tlckRELINK);
  2625. lp->header.next = cpu_to_le64(nxaddr);
  2626. XT_PUTPAGE(lmp);
  2627. }
  2628. if (rmp) {
  2629. BT_MARK_DIRTY(rmp, ip);
  2630. tlck =
  2631. txLock(tid, ip, rmp, tlckXTREE | tlckRELINK);
  2632. rp->header.prev = cpu_to_le64(nxaddr);
  2633. XT_PUTPAGE(rmp);
  2634. }
  2635. /*
  2636. * update the target xtpage to be relocated
  2637. *
  2638. * update the self address of the target page
  2639. * and write to destination extent;
  2640. * redo image covers the whole xtpage since it is new page
  2641. * to the destination extent;
  2642. * update of bmap for the free of source extent
  2643. * of the target xtpage itself:
  2644. * update of bmap for the allocation of destination extent
  2645. * of the target xtpage itself:
  2646. * update of bmap for the extents covered by xad entries in
  2647. * the target xtpage is not necessary since they are not
  2648. * updated;
  2649. * if not committed before this relocation,
  2650. * target page may contain XAD_NEW entries which must
  2651. * be scanned for bmap update (logredo() always
  2652. * scan xtpage REDOPAGE image for bmap update);
  2653. * if committed before this relocation (tlckRELOCATE),
  2654. * scan may be skipped by commit() and logredo();
  2655. */
  2656. BT_MARK_DIRTY(mp, ip);
  2657. /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */
  2658. tlck = txLock(tid, ip, mp, tlckXTREE | tlckNEW);
  2659. xtlck = (struct xtlock *) & tlck->lock;
  2660. /* update the self address in the xtpage header */
  2661. pxd = &p->header.self;
  2662. PXDaddress(pxd, nxaddr);
  2663. /* linelock for the after image of the whole page */
  2664. xtlck->lwm.length =
  2665. le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
  2666. /* update the buffer extent descriptor of target xtpage */
  2667. xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize;
  2668. bmSetXD(mp, nxaddr, xsize);
  2669. /* unpin the target page to new homeward bound */
  2670. XT_PUTPAGE(mp);
  2671. jfs_info("xtRelocate: target xtpage relocated.");
  2672. }
  2673. /*
  2674. * 3. acquire maplock for the source extent to be freed;
  2675. *
  2676. * acquire a maplock saving the src relocated extent address;
  2677. * to free of the extent at commit time;
  2678. */
  2679. out:
  2680. /* if DATAEXT relocation, write a LOG_UPDATEMAP record for
  2681. * free PXD of the source data extent (logredo() will update
  2682. * bmap for free of source data extent), and update bmap for
  2683. * free of the source data extent;
  2684. */
  2685. if (xtype == DATAEXT)
  2686. tlck = txMaplock(tid, ip, tlckMAP);
  2687. /* if XTPAGE relocation, write a LOG_NOREDOPAGE record
  2688. * for the source xtpage (logredo() will init NoRedoPage
  2689. * filter and will also update bmap for free of the source
  2690. * xtpage), and update bmap for free of the source xtpage;
  2691. * N.B. We use tlckMAP instead of tlkcXTREE because there
  2692. * is no buffer associated with this lock since the buffer
  2693. * has been redirected to the target location.
  2694. */
  2695. else /* (xtype == XTPAGE) */
  2696. tlck = txMaplock(tid, ip, tlckMAP | tlckRELOCATE);
  2697. pxdlock = (struct pxd_lock *) & tlck->lock;
  2698. pxdlock->flag = mlckFREEPXD;
  2699. PXDaddress(&pxdlock->pxd, oxaddr);
  2700. PXDlength(&pxdlock->pxd, xlen);
  2701. pxdlock->index = 1;
  2702. /*
  2703. * 4. update the parent xad entry for relocation;
  2704. *
  2705. * acquire tlck for the parent entry with XAD_NEW as entry
  2706. * update which will write LOG_REDOPAGE and update bmap for
  2707. * allocation of XAD_NEW destination extent;
  2708. */
  2709. jfs_info("xtRelocate: update parent xad entry.");
  2710. BT_MARK_DIRTY(pmp, ip);
  2711. tlck = txLock(tid, ip, pmp, tlckXTREE | tlckGROW);
  2712. xtlck = (struct xtlock *) & tlck->lock;
  2713. /* update the XAD with the new destination extent; */
  2714. xad = &pp->xad[index];
  2715. xad->flag |= XAD_NEW;
  2716. XADaddress(xad, nxaddr);
  2717. xtlck->lwm.offset = min(index, xtlck->lwm.offset);
  2718. xtlck->lwm.length = le16_to_cpu(pp->header.nextindex) -
  2719. xtlck->lwm.offset;
  2720. /* unpin the parent xtpage */
  2721. XT_PUTPAGE(pmp);
  2722. return rc;
  2723. }
  2724. /*
  2725. * xtSearchNode()
  2726. *
  2727. * function: search for the internal xad entry covering specified extent.
  2728. * This function is mainly used by defragfs utility.
  2729. *
  2730. * parameters:
  2731. * ip - file object;
  2732. * xad - extent to find;
  2733. * cmpp - comparison result:
  2734. * btstack - traverse stack;
  2735. * flag - search process flag;
  2736. *
  2737. * returns:
  2738. * btstack contains (bn, index) of search path traversed to the entry.
  2739. * *cmpp is set to result of comparison with the entry returned.
  2740. * the page containing the entry is pinned at exit.
  2741. */
  2742. static int xtSearchNode(struct inode *ip, xad_t * xad, /* required XAD entry */
  2743. int *cmpp, struct btstack * btstack, int flag)
  2744. {
  2745. int rc = 0;
  2746. s64 xoff, xaddr;
  2747. int xlen;
  2748. int cmp = 1; /* init for empty page */
  2749. s64 bn; /* block number */
  2750. struct metapage *mp; /* meta-page buffer */
  2751. xtpage_t *p; /* page */
  2752. int base, index, lim;
  2753. struct btframe *btsp;
  2754. s64 t64;
  2755. BT_CLR(btstack);
  2756. xoff = offsetXAD(xad);
  2757. xlen = lengthXAD(xad);
  2758. xaddr = addressXAD(xad);
  2759. /*
  2760. * search down tree from root:
  2761. *
  2762. * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
  2763. * internal page, child page Pi contains entry with k, Ki <= K < Kj.
  2764. *
  2765. * if entry with search key K is not found
  2766. * internal page search find the entry with largest key Ki
  2767. * less than K which point to the child page to search;
  2768. * leaf page search find the entry with smallest key Kj
  2769. * greater than K so that the returned index is the position of
  2770. * the entry to be shifted right for insertion of new entry.
  2771. * for empty tree, search key is greater than any key of the tree.
  2772. *
  2773. * by convention, root bn = 0.
  2774. */
  2775. for (bn = 0;;) {
  2776. /* get/pin the page to search */
  2777. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  2778. if (rc)
  2779. return rc;
  2780. if (p->header.flag & BT_LEAF) {
  2781. XT_PUTPAGE(mp);
  2782. return -ESTALE;
  2783. }
  2784. lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
  2785. /*
  2786. * binary search with search key K on the current page
  2787. */
  2788. for (base = XTENTRYSTART; lim; lim >>= 1) {
  2789. index = base + (lim >> 1);
  2790. XT_CMP(cmp, xoff, &p->xad[index], t64);
  2791. if (cmp == 0) {
  2792. /*
  2793. * search hit
  2794. *
  2795. * verify for exact match;
  2796. */
  2797. if (xaddr == addressXAD(&p->xad[index]) &&
  2798. xoff == offsetXAD(&p->xad[index])) {
  2799. *cmpp = cmp;
  2800. /* save search result */
  2801. btsp = btstack->top;
  2802. btsp->bn = bn;
  2803. btsp->index = index;
  2804. btsp->mp = mp;
  2805. return 0;
  2806. }
  2807. /* descend/search its child page */
  2808. goto next;
  2809. }
  2810. if (cmp > 0) {
  2811. base = index + 1;
  2812. --lim;
  2813. }
  2814. }
  2815. /*
  2816. * search miss - non-leaf page:
  2817. *
  2818. * base is the smallest index with key (Kj) greater than
  2819. * search key (K) and may be zero or maxentry index.
  2820. * if base is non-zero, decrement base by one to get the parent
  2821. * entry of the child page to search.
  2822. */
  2823. index = base ? base - 1 : base;
  2824. /*
  2825. * go down to child page
  2826. */
  2827. next:
  2828. /* get the child page block number */
  2829. bn = addressXAD(&p->xad[index]);
  2830. /* unpin the parent page */
  2831. XT_PUTPAGE(mp);
  2832. }
  2833. }
  2834. /*
  2835. * xtRelink()
  2836. *
  2837. * function:
  2838. * link around a freed page.
  2839. *
  2840. * Parameter:
  2841. * int tid,
  2842. * struct inode *ip,
  2843. * xtpage_t *p)
  2844. *
  2845. * returns:
  2846. */
  2847. static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * p)
  2848. {
  2849. int rc = 0;
  2850. struct metapage *mp;
  2851. s64 nextbn, prevbn;
  2852. struct tlock *tlck;
  2853. nextbn = le64_to_cpu(p->header.next);
  2854. prevbn = le64_to_cpu(p->header.prev);
  2855. /* update prev pointer of the next page */
  2856. if (nextbn != 0) {
  2857. XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
  2858. if (rc)
  2859. return rc;
  2860. /*
  2861. * acquire a transaction lock on the page;
  2862. *
  2863. * action: update prev pointer;
  2864. */
  2865. BT_MARK_DIRTY(mp, ip);
  2866. tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
  2867. /* the page may already have been tlock'd */
  2868. p->header.prev = cpu_to_le64(prevbn);
  2869. XT_PUTPAGE(mp);
  2870. }
  2871. /* update next pointer of the previous page */
  2872. if (prevbn != 0) {
  2873. XT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc);
  2874. if (rc)
  2875. return rc;
  2876. /*
  2877. * acquire a transaction lock on the page;
  2878. *
  2879. * action: update next pointer;
  2880. */
  2881. BT_MARK_DIRTY(mp, ip);
  2882. tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
  2883. /* the page may already have been tlock'd */
  2884. p->header.next = le64_to_cpu(nextbn);
  2885. XT_PUTPAGE(mp);
  2886. }
  2887. return 0;
  2888. }
  2889. #endif /* _STILL_TO_PORT */
  2890. /*
  2891. * xtInitRoot()
  2892. *
  2893. * initialize file root (inline in inode)
  2894. */
  2895. void xtInitRoot(tid_t tid, struct inode *ip)
  2896. {
  2897. xtpage_t *p;
  2898. /*
  2899. * acquire a transaction lock on the root
  2900. *
  2901. * action:
  2902. */
  2903. txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag,
  2904. tlckXTREE | tlckNEW);
  2905. p = &JFS_IP(ip)->i_xtroot;
  2906. p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
  2907. p->header.nextindex = cpu_to_le16(XTENTRYSTART);
  2908. if (S_ISDIR(ip->i_mode))
  2909. p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR);
  2910. else {
  2911. p->header.maxentry = cpu_to_le16(XTROOTINITSLOT);
  2912. ip->i_size = 0;
  2913. }
  2914. return;
  2915. }
  2916. /*
  2917. * We can run into a deadlock truncating a file with a large number of
  2918. * xtree pages (large fragmented file). A robust fix would entail a
  2919. * reservation system where we would reserve a number of metadata pages
  2920. * and tlocks which we would be guaranteed without a deadlock. Without
  2921. * this, a partial fix is to limit number of metadata pages we will lock
  2922. * in a single transaction. Currently we will truncate the file so that
  2923. * no more than 50 leaf pages will be locked. The caller of xtTruncate
  2924. * will be responsible for ensuring that the current transaction gets
  2925. * committed, and that subsequent transactions are created to truncate
  2926. * the file further if needed.
  2927. */
  2928. #define MAX_TRUNCATE_LEAVES 50
  2929. /*
  2930. * xtTruncate()
  2931. *
  2932. * function:
  2933. * traverse for truncation logging backward bottom up;
  2934. * terminate at the last extent entry at the current subtree
  2935. * root page covering new down size.
  2936. * truncation may occur within the last extent entry.
  2937. *
  2938. * parameter:
  2939. * int tid,
  2940. * struct inode *ip,
  2941. * s64 newsize,
  2942. * int type) {PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
  2943. *
  2944. * return:
  2945. *
  2946. * note:
  2947. * PWMAP:
  2948. * 1. truncate (non-COMMIT_NOLINK file)
  2949. * by jfs_truncate() or jfs_open(O_TRUNC):
  2950. * xtree is updated;
  2951. * 2. truncate index table of directory when last entry removed
  2952. * map update via tlock at commit time;
  2953. * PMAP:
  2954. * Call xtTruncate_pmap instead
  2955. * WMAP:
  2956. * 1. remove (free zero link count) on last reference release
  2957. * (pmap has been freed at commit zero link count);
  2958. * 2. truncate (COMMIT_NOLINK file, i.e., tmp file):
  2959. * xtree is updated;
  2960. * map update directly at truncation time;
  2961. *
  2962. * if (DELETE)
  2963. * no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
  2964. * else if (TRUNCATE)
  2965. * must write LOG_NOREDOPAGE for deleted index page;
  2966. *
  2967. * pages may already have been tlocked by anonymous transactions
  2968. * during file growth (i.e., write) before truncation;
  2969. *
  2970. * except last truncated entry, deleted entries remains as is
  2971. * in the page (nextindex is updated) for other use
  2972. * (e.g., log/update allocation map): this avoid copying the page
  2973. * info but delay free of pages;
  2974. *
  2975. */
  2976. s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag)
  2977. {
  2978. int rc = 0;
  2979. s64 teof;
  2980. struct metapage *mp;
  2981. xtpage_t *p;
  2982. s64 bn;
  2983. int index, nextindex;
  2984. xad_t *xad;
  2985. s64 xoff, xaddr;
  2986. int xlen, len, freexlen;
  2987. struct btstack btstack;
  2988. struct btframe *parent;
  2989. struct tblock *tblk = NULL;
  2990. struct tlock *tlck = NULL;
  2991. struct xtlock *xtlck = NULL;
  2992. struct xdlistlock xadlock; /* maplock for COMMIT_WMAP */
  2993. struct pxd_lock *pxdlock; /* maplock for COMMIT_WMAP */
  2994. s64 nfreed;
  2995. int freed, log;
  2996. int locked_leaves = 0;
  2997. /* save object truncation type */
  2998. if (tid) {
  2999. tblk = tid_to_tblock(tid);
  3000. tblk->xflag |= flag;
  3001. }
  3002. nfreed = 0;
  3003. flag &= COMMIT_MAP;
  3004. assert(flag != COMMIT_PMAP);
  3005. if (flag == COMMIT_PWMAP)
  3006. log = 1;
  3007. else {
  3008. log = 0;
  3009. xadlock.flag = mlckFREEXADLIST;
  3010. xadlock.index = 1;
  3011. }
  3012. /*
  3013. * if the newsize is not an integral number of pages,
  3014. * the file between newsize and next page boundary will
  3015. * be cleared.
  3016. * if truncating into a file hole, it will cause
  3017. * a full block to be allocated for the logical block.
  3018. */
  3019. /*
  3020. * release page blocks of truncated region <teof, eof>
  3021. *
  3022. * free the data blocks from the leaf index blocks.
  3023. * delete the parent index entries corresponding to
  3024. * the freed child data/index blocks.
  3025. * free the index blocks themselves which aren't needed
  3026. * in new sized file.
  3027. *
  3028. * index blocks are updated only if the blocks are to be
  3029. * retained in the new sized file.
  3030. * if type is PMAP, the data and index pages are NOT
  3031. * freed, and the data and index blocks are NOT freed
  3032. * from working map.
  3033. * (this will allow continued access of data/index of
  3034. * temporary file (zerolink count file truncated to zero-length)).
  3035. */
  3036. teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
  3037. JFS_SBI(ip->i_sb)->l2bsize;
  3038. /* clear stack */
  3039. BT_CLR(&btstack);
  3040. /*
  3041. * start with root
  3042. *
  3043. * root resides in the inode
  3044. */
  3045. bn = 0;
  3046. /*
  3047. * first access of each page:
  3048. */
  3049. getPage:
  3050. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  3051. if (rc)
  3052. return rc;
  3053. /* process entries backward from last index */
  3054. index = le16_to_cpu(p->header.nextindex) - 1;
  3055. /* Since this is the rightmost page at this level, and we may have
  3056. * already freed a page that was formerly to the right, let's make
  3057. * sure that the next pointer is zero.
  3058. */
  3059. if (p->header.next) {
  3060. if (log)
  3061. /*
  3062. * Make sure this change to the header is logged.
  3063. * If we really truncate this leaf, the flag
  3064. * will be changed to tlckTRUNCATE
  3065. */
  3066. tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
  3067. BT_MARK_DIRTY(mp, ip);
  3068. p->header.next = 0;
  3069. }
  3070. if (p->header.flag & BT_INTERNAL)
  3071. goto getChild;
  3072. /*
  3073. * leaf page
  3074. */
  3075. freed = 0;
  3076. /* does region covered by leaf page precede Teof ? */
  3077. xad = &p->xad[index];
  3078. xoff = offsetXAD(xad);
  3079. xlen = lengthXAD(xad);
  3080. if (teof >= xoff + xlen) {
  3081. XT_PUTPAGE(mp);
  3082. goto getParent;
  3083. }
  3084. /* (re)acquire tlock of the leaf page */
  3085. if (log) {
  3086. if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
  3087. /*
  3088. * We need to limit the size of the transaction
  3089. * to avoid exhausting pagecache & tlocks
  3090. */
  3091. XT_PUTPAGE(mp);
  3092. newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
  3093. goto getParent;
  3094. }
  3095. tlck = txLock(tid, ip, mp, tlckXTREE);
  3096. tlck->type = tlckXTREE | tlckTRUNCATE;
  3097. xtlck = (struct xtlock *) & tlck->lock;
  3098. xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
  3099. }
  3100. BT_MARK_DIRTY(mp, ip);
  3101. /*
  3102. * scan backward leaf page entries
  3103. */
  3104. for (; index >= XTENTRYSTART; index--) {
  3105. xad = &p->xad[index];
  3106. xoff = offsetXAD(xad);
  3107. xlen = lengthXAD(xad);
  3108. xaddr = addressXAD(xad);
  3109. /*
  3110. * The "data" for a directory is indexed by the block
  3111. * device's address space. This metadata must be invalidated
  3112. * here
  3113. */
  3114. if (S_ISDIR(ip->i_mode) && (teof == 0))
  3115. invalidate_xad_metapages(ip, *xad);
  3116. /*
  3117. * entry beyond eof: continue scan of current page
  3118. * xad
  3119. * ---|---=======------->
  3120. * eof
  3121. */
  3122. if (teof < xoff) {
  3123. nfreed += xlen;
  3124. continue;
  3125. }
  3126. /*
  3127. * (xoff <= teof): last entry to be deleted from page;
  3128. * If other entries remain in page: keep and update the page.
  3129. */
  3130. /*
  3131. * eof == entry_start: delete the entry
  3132. * xad
  3133. * -------|=======------->
  3134. * eof
  3135. *
  3136. */
  3137. if (teof == xoff) {
  3138. nfreed += xlen;
  3139. if (index == XTENTRYSTART)
  3140. break;
  3141. nextindex = index;
  3142. }
  3143. /*
  3144. * eof within the entry: truncate the entry.
  3145. * xad
  3146. * -------===|===------->
  3147. * eof
  3148. */
  3149. else if (teof < xoff + xlen) {
  3150. /* update truncated entry */
  3151. len = teof - xoff;
  3152. freexlen = xlen - len;
  3153. XADlength(xad, len);
  3154. /* save pxd of truncated extent in tlck */
  3155. xaddr += len;
  3156. if (log) { /* COMMIT_PWMAP */
  3157. xtlck->lwm.offset = (xtlck->lwm.offset) ?
  3158. min(index, (int)xtlck->lwm.offset) : index;
  3159. xtlck->lwm.length = index + 1 -
  3160. xtlck->lwm.offset;
  3161. xtlck->twm.offset = index;
  3162. pxdlock = (struct pxd_lock *) & xtlck->pxdlock;
  3163. pxdlock->flag = mlckFREEPXD;
  3164. PXDaddress(&pxdlock->pxd, xaddr);
  3165. PXDlength(&pxdlock->pxd, freexlen);
  3166. }
  3167. /* free truncated extent */
  3168. else { /* COMMIT_WMAP */
  3169. pxdlock = (struct pxd_lock *) & xadlock;
  3170. pxdlock->flag = mlckFREEPXD;
  3171. PXDaddress(&pxdlock->pxd, xaddr);
  3172. PXDlength(&pxdlock->pxd, freexlen);
  3173. txFreeMap(ip, pxdlock, NULL, COMMIT_WMAP);
  3174. /* reset map lock */
  3175. xadlock.flag = mlckFREEXADLIST;
  3176. }
  3177. /* current entry is new last entry; */
  3178. nextindex = index + 1;
  3179. nfreed += freexlen;
  3180. }
  3181. /*
  3182. * eof beyond the entry:
  3183. * xad
  3184. * -------=======---|--->
  3185. * eof
  3186. */
  3187. else { /* (xoff + xlen < teof) */
  3188. nextindex = index + 1;
  3189. }
  3190. if (nextindex < le16_to_cpu(p->header.nextindex)) {
  3191. if (!log) { /* COMMIT_WAMP */
  3192. xadlock.xdlist = &p->xad[nextindex];
  3193. xadlock.count =
  3194. le16_to_cpu(p->header.nextindex) -
  3195. nextindex;
  3196. txFreeMap(ip, (struct maplock *) & xadlock,
  3197. NULL, COMMIT_WMAP);
  3198. }
  3199. p->header.nextindex = cpu_to_le16(nextindex);
  3200. }
  3201. XT_PUTPAGE(mp);
  3202. /* assert(freed == 0); */
  3203. goto getParent;
  3204. } /* end scan of leaf page entries */
  3205. freed = 1;
  3206. /*
  3207. * leaf page become empty: free the page if type != PMAP
  3208. */
  3209. if (log) { /* COMMIT_PWMAP */
  3210. /* txCommit() with tlckFREE:
  3211. * free data extents covered by leaf [XTENTRYSTART:hwm);
  3212. * invalidate leaf if COMMIT_PWMAP;
  3213. * if (TRUNCATE), will write LOG_NOREDOPAGE;
  3214. */
  3215. tlck->type = tlckXTREE | tlckFREE;
  3216. } else { /* COMMIT_WAMP */
  3217. /* free data extents covered by leaf */
  3218. xadlock.xdlist = &p->xad[XTENTRYSTART];
  3219. xadlock.count =
  3220. le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
  3221. txFreeMap(ip, (struct maplock *) & xadlock, NULL, COMMIT_WMAP);
  3222. }
  3223. if (p->header.flag & BT_ROOT) {
  3224. p->header.flag &= ~BT_INTERNAL;
  3225. p->header.flag |= BT_LEAF;
  3226. p->header.nextindex = cpu_to_le16(XTENTRYSTART);
  3227. XT_PUTPAGE(mp); /* debug */
  3228. goto out;
  3229. } else {
  3230. if (log) { /* COMMIT_PWMAP */
  3231. /* page will be invalidated at tx completion
  3232. */
  3233. XT_PUTPAGE(mp);
  3234. } else { /* COMMIT_WMAP */
  3235. if (mp->lid)
  3236. lid_to_tlock(mp->lid)->flag |= tlckFREELOCK;
  3237. /* invalidate empty leaf page */
  3238. discard_metapage(mp);
  3239. }
  3240. }
  3241. /*
  3242. * the leaf page become empty: delete the parent entry
  3243. * for the leaf page if the parent page is to be kept
  3244. * in the new sized file.
  3245. */
  3246. /*
  3247. * go back up to the parent page
  3248. */
  3249. getParent:
  3250. /* pop/restore parent entry for the current child page */
  3251. if ((parent = BT_POP(&btstack)) == NULL)
  3252. /* current page must have been root */
  3253. goto out;
  3254. /* get back the parent page */
  3255. bn = parent->bn;
  3256. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  3257. if (rc)
  3258. return rc;
  3259. index = parent->index;
  3260. /*
  3261. * child page was not empty:
  3262. */
  3263. if (freed == 0) {
  3264. /* has any entry deleted from parent ? */
  3265. if (index < le16_to_cpu(p->header.nextindex) - 1) {
  3266. /* (re)acquire tlock on the parent page */
  3267. if (log) { /* COMMIT_PWMAP */
  3268. /* txCommit() with tlckTRUNCATE:
  3269. * free child extents covered by parent [);
  3270. */
  3271. tlck = txLock(tid, ip, mp, tlckXTREE);
  3272. xtlck = (struct xtlock *) & tlck->lock;
  3273. if (!(tlck->type & tlckTRUNCATE)) {
  3274. xtlck->hwm.offset =
  3275. le16_to_cpu(p->header.
  3276. nextindex) - 1;
  3277. tlck->type =
  3278. tlckXTREE | tlckTRUNCATE;
  3279. }
  3280. } else { /* COMMIT_WMAP */
  3281. /* free child extents covered by parent */
  3282. xadlock.xdlist = &p->xad[index + 1];
  3283. xadlock.count =
  3284. le16_to_cpu(p->header.nextindex) -
  3285. index - 1;
  3286. txFreeMap(ip, (struct maplock *) & xadlock,
  3287. NULL, COMMIT_WMAP);
  3288. }
  3289. BT_MARK_DIRTY(mp, ip);
  3290. p->header.nextindex = cpu_to_le16(index + 1);
  3291. }
  3292. XT_PUTPAGE(mp);
  3293. goto getParent;
  3294. }
  3295. /*
  3296. * child page was empty:
  3297. */
  3298. nfreed += lengthXAD(&p->xad[index]);
  3299. /*
  3300. * During working map update, child page's tlock must be handled
  3301. * before parent's. This is because the parent's tlock will cause
  3302. * the child's disk space to be marked available in the wmap, so
  3303. * it's important that the child page be released by that time.
  3304. *
  3305. * ToDo: tlocks should be on doubly-linked list, so we can
  3306. * quickly remove it and add it to the end.
  3307. */
  3308. /*
  3309. * Move parent page's tlock to the end of the tid's tlock list
  3310. */
  3311. if (log && mp->lid && (tblk->last != mp->lid) &&
  3312. lid_to_tlock(mp->lid)->tid) {
  3313. lid_t lid = mp->lid;
  3314. struct tlock *prev;
  3315. tlck = lid_to_tlock(lid);
  3316. if (tblk->next == lid)
  3317. tblk->next = tlck->next;
  3318. else {
  3319. for (prev = lid_to_tlock(tblk->next);
  3320. prev->next != lid;
  3321. prev = lid_to_tlock(prev->next)) {
  3322. assert(prev->next);
  3323. }
  3324. prev->next = tlck->next;
  3325. }
  3326. lid_to_tlock(tblk->last)->next = lid;
  3327. tlck->next = 0;
  3328. tblk->last = lid;
  3329. }
  3330. /*
  3331. * parent page become empty: free the page
  3332. */
  3333. if (index == XTENTRYSTART) {
  3334. if (log) { /* COMMIT_PWMAP */
  3335. /* txCommit() with tlckFREE:
  3336. * free child extents covered by parent;
  3337. * invalidate parent if COMMIT_PWMAP;
  3338. */
  3339. tlck = txLock(tid, ip, mp, tlckXTREE);
  3340. xtlck = (struct xtlock *) & tlck->lock;
  3341. xtlck->hwm.offset =
  3342. le16_to_cpu(p->header.nextindex) - 1;
  3343. tlck->type = tlckXTREE | tlckFREE;
  3344. } else { /* COMMIT_WMAP */
  3345. /* free child extents covered by parent */
  3346. xadlock.xdlist = &p->xad[XTENTRYSTART];
  3347. xadlock.count =
  3348. le16_to_cpu(p->header.nextindex) -
  3349. XTENTRYSTART;
  3350. txFreeMap(ip, (struct maplock *) & xadlock, NULL,
  3351. COMMIT_WMAP);
  3352. }
  3353. BT_MARK_DIRTY(mp, ip);
  3354. if (p->header.flag & BT_ROOT) {
  3355. p->header.flag &= ~BT_INTERNAL;
  3356. p->header.flag |= BT_LEAF;
  3357. p->header.nextindex = cpu_to_le16(XTENTRYSTART);
  3358. if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) {
  3359. /*
  3360. * Shrink root down to allow inline
  3361. * EA (otherwise fsck complains)
  3362. */
  3363. p->header.maxentry =
  3364. cpu_to_le16(XTROOTINITSLOT);
  3365. JFS_IP(ip)->mode2 |= INLINEEA;
  3366. }
  3367. XT_PUTPAGE(mp); /* debug */
  3368. goto out;
  3369. } else {
  3370. if (log) { /* COMMIT_PWMAP */
  3371. /* page will be invalidated at tx completion
  3372. */
  3373. XT_PUTPAGE(mp);
  3374. } else { /* COMMIT_WMAP */
  3375. if (mp->lid)
  3376. lid_to_tlock(mp->lid)->flag |=
  3377. tlckFREELOCK;
  3378. /* invalidate parent page */
  3379. discard_metapage(mp);
  3380. }
  3381. /* parent has become empty and freed:
  3382. * go back up to its parent page
  3383. */
  3384. /* freed = 1; */
  3385. goto getParent;
  3386. }
  3387. }
  3388. /*
  3389. * parent page still has entries for front region;
  3390. */
  3391. else {
  3392. /* try truncate region covered by preceding entry
  3393. * (process backward)
  3394. */
  3395. index--;
  3396. /* go back down to the child page corresponding
  3397. * to the entry
  3398. */
  3399. goto getChild;
  3400. }
  3401. /*
  3402. * internal page: go down to child page of current entry
  3403. */
  3404. getChild:
  3405. /* save current parent entry for the child page */
  3406. if (BT_STACK_FULL(&btstack)) {
  3407. jfs_error(ip->i_sb, "stack overrun in xtTruncate!");
  3408. XT_PUTPAGE(mp);
  3409. return -EIO;
  3410. }
  3411. BT_PUSH(&btstack, bn, index);
  3412. /* get child page */
  3413. xad = &p->xad[index];
  3414. bn = addressXAD(xad);
  3415. /*
  3416. * first access of each internal entry:
  3417. */
  3418. /* release parent page */
  3419. XT_PUTPAGE(mp);
  3420. /* process the child page */
  3421. goto getPage;
  3422. out:
  3423. /*
  3424. * update file resource stat
  3425. */
  3426. /* set size
  3427. */
  3428. if (S_ISDIR(ip->i_mode) && !newsize)
  3429. ip->i_size = 1; /* fsck hates zero-length directories */
  3430. else
  3431. ip->i_size = newsize;
  3432. /* update quota allocation to reflect freed blocks */
  3433. DQUOT_FREE_BLOCK(ip, nfreed);
  3434. /*
  3435. * free tlock of invalidated pages
  3436. */
  3437. if (flag == COMMIT_WMAP)
  3438. txFreelock(ip);
  3439. return newsize;
  3440. }
  3441. /*
  3442. * xtTruncate_pmap()
  3443. *
  3444. * function:
  3445. * Perform truncate to zero lenghth for deleted file, leaving the
  3446. * the xtree and working map untouched. This allows the file to
  3447. * be accessed via open file handles, while the delete of the file
  3448. * is committed to disk.
  3449. *
  3450. * parameter:
  3451. * tid_t tid,
  3452. * struct inode *ip,
  3453. * s64 committed_size)
  3454. *
  3455. * return: new committed size
  3456. *
  3457. * note:
  3458. *
  3459. * To avoid deadlock by holding too many transaction locks, the
  3460. * truncation may be broken up into multiple transactions.
  3461. * The committed_size keeps track of part of the file has been
  3462. * freed from the pmaps.
  3463. */
  3464. s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
  3465. {
  3466. s64 bn;
  3467. struct btstack btstack;
  3468. int cmp;
  3469. int index;
  3470. int locked_leaves = 0;
  3471. struct metapage *mp;
  3472. xtpage_t *p;
  3473. struct btframe *parent;
  3474. int rc;
  3475. struct tblock *tblk;
  3476. struct tlock *tlck = NULL;
  3477. xad_t *xad;
  3478. int xlen;
  3479. s64 xoff;
  3480. struct xtlock *xtlck = NULL;
  3481. /* save object truncation type */
  3482. tblk = tid_to_tblock(tid);
  3483. tblk->xflag |= COMMIT_PMAP;
  3484. /* clear stack */
  3485. BT_CLR(&btstack);
  3486. if (committed_size) {
  3487. xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
  3488. rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
  3489. if (rc)
  3490. return rc;
  3491. XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  3492. if (cmp != 0) {
  3493. XT_PUTPAGE(mp);
  3494. jfs_error(ip->i_sb,
  3495. "xtTruncate_pmap: did not find extent");
  3496. return -EIO;
  3497. }
  3498. } else {
  3499. /*
  3500. * start with root
  3501. *
  3502. * root resides in the inode
  3503. */
  3504. bn = 0;
  3505. /*
  3506. * first access of each page:
  3507. */
  3508. getPage:
  3509. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  3510. if (rc)
  3511. return rc;
  3512. /* process entries backward from last index */
  3513. index = le16_to_cpu(p->header.nextindex) - 1;
  3514. if (p->header.flag & BT_INTERNAL)
  3515. goto getChild;
  3516. }
  3517. /*
  3518. * leaf page
  3519. */
  3520. if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
  3521. /*
  3522. * We need to limit the size of the transaction
  3523. * to avoid exhausting pagecache & tlocks
  3524. */
  3525. xad = &p->xad[index];
  3526. xoff = offsetXAD(xad);
  3527. xlen = lengthXAD(xad);
  3528. XT_PUTPAGE(mp);
  3529. return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
  3530. }
  3531. tlck = txLock(tid, ip, mp, tlckXTREE);
  3532. tlck->type = tlckXTREE | tlckFREE;
  3533. xtlck = (struct xtlock *) & tlck->lock;
  3534. xtlck->hwm.offset = index;
  3535. XT_PUTPAGE(mp);
  3536. /*
  3537. * go back up to the parent page
  3538. */
  3539. getParent:
  3540. /* pop/restore parent entry for the current child page */
  3541. if ((parent = BT_POP(&btstack)) == NULL)
  3542. /* current page must have been root */
  3543. goto out;
  3544. /* get back the parent page */
  3545. bn = parent->bn;
  3546. XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  3547. if (rc)
  3548. return rc;
  3549. index = parent->index;
  3550. /*
  3551. * parent page become empty: free the page
  3552. */
  3553. if (index == XTENTRYSTART) {
  3554. /* txCommit() with tlckFREE:
  3555. * free child extents covered by parent;
  3556. * invalidate parent if COMMIT_PWMAP;
  3557. */
  3558. tlck = txLock(tid, ip, mp, tlckXTREE);
  3559. xtlck = (struct xtlock *) & tlck->lock;
  3560. xtlck->hwm.offset =
  3561. le16_to_cpu(p->header.nextindex) - 1;
  3562. tlck->type = tlckXTREE | tlckFREE;
  3563. XT_PUTPAGE(mp);
  3564. if (p->header.flag & BT_ROOT) {
  3565. goto out;
  3566. } else {
  3567. goto getParent;
  3568. }
  3569. }
  3570. /*
  3571. * parent page still has entries for front region;
  3572. */
  3573. else
  3574. index--;
  3575. /*
  3576. * internal page: go down to child page of current entry
  3577. */
  3578. getChild:
  3579. /* save current parent entry for the child page */
  3580. if (BT_STACK_FULL(&btstack)) {
  3581. jfs_error(ip->i_sb, "stack overrun in xtTruncate_pmap!");
  3582. XT_PUTPAGE(mp);
  3583. return -EIO;
  3584. }
  3585. BT_PUSH(&btstack, bn, index);
  3586. /* get child page */
  3587. xad = &p->xad[index];
  3588. bn = addressXAD(xad);
  3589. /*
  3590. * first access of each internal entry:
  3591. */
  3592. /* release parent page */
  3593. XT_PUTPAGE(mp);
  3594. /* process the child page */
  3595. goto getPage;
  3596. out:
  3597. return 0;
  3598. }
  3599. #ifdef CONFIG_JFS_STATISTICS
  3600. int jfs_xtstat_read(char *buffer, char **start, off_t offset, int length,
  3601. int *eof, void *data)
  3602. {
  3603. int len = 0;
  3604. off_t begin;
  3605. len += sprintf(buffer,
  3606. "JFS Xtree statistics\n"
  3607. "====================\n"
  3608. "searches = %d\n"
  3609. "fast searches = %d\n"
  3610. "splits = %d\n",
  3611. xtStat.search,
  3612. xtStat.fastSearch,
  3613. xtStat.split);
  3614. begin = offset;
  3615. *start = buffer + begin;
  3616. len -= begin;
  3617. if (len > length)
  3618. len = length;
  3619. else
  3620. *eof = 1;
  3621. if (len < 0)
  3622. len = 0;
  3623. return len;
  3624. }
  3625. #endif