jfs_dtree.c 101 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572
  1. /*
  2. * Copyright (C) International Business Machines Corp., 2000-2004
  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_dtree.c: directory B+-tree manager
  20. *
  21. * B+-tree with variable length key directory:
  22. *
  23. * each directory page is structured as an array of 32-byte
  24. * directory entry slots initialized as a freelist
  25. * to avoid search/compaction of free space at insertion.
  26. * when an entry is inserted, a number of slots are allocated
  27. * from the freelist as required to store variable length data
  28. * of the entry; when the entry is deleted, slots of the entry
  29. * are returned to freelist.
  30. *
  31. * leaf entry stores full name as key and file serial number
  32. * (aka inode number) as data.
  33. * internal/router entry stores sufffix compressed name
  34. * as key and simple extent descriptor as data.
  35. *
  36. * each directory page maintains a sorted entry index table
  37. * which stores the start slot index of sorted entries
  38. * to allow binary search on the table.
  39. *
  40. * directory starts as a root/leaf page in on-disk inode
  41. * inline data area.
  42. * when it becomes full, it starts a leaf of a external extent
  43. * of length of 1 block. each time the first leaf becomes full,
  44. * it is extended rather than split (its size is doubled),
  45. * until its length becoms 4 KBytes, from then the extent is split
  46. * with new 4 Kbyte extent when it becomes full
  47. * to reduce external fragmentation of small directories.
  48. *
  49. * blah, blah, blah, for linear scan of directory in pieces by
  50. * readdir().
  51. *
  52. *
  53. * case-insensitive directory file system
  54. *
  55. * names are stored in case-sensitive way in leaf entry.
  56. * but stored, searched and compared in case-insensitive (uppercase) order
  57. * (i.e., both search key and entry key are folded for search/compare):
  58. * (note that case-sensitive order is BROKEN in storage, e.g.,
  59. * sensitive: Ad, aB, aC, aD -> insensitive: aB, aC, aD, Ad
  60. *
  61. * entries which folds to the same key makes up a equivalent class
  62. * whose members are stored as contiguous cluster (may cross page boundary)
  63. * but whose order is arbitrary and acts as duplicate, e.g.,
  64. * abc, Abc, aBc, abC)
  65. *
  66. * once match is found at leaf, requires scan forward/backward
  67. * either for, in case-insensitive search, duplicate
  68. * or for, in case-sensitive search, for exact match
  69. *
  70. * router entry must be created/stored in case-insensitive way
  71. * in internal entry:
  72. * (right most key of left page and left most key of right page
  73. * are folded, and its suffix compression is propagated as router
  74. * key in parent)
  75. * (e.g., if split occurs <abc> and <aBd>, <ABD> trather than <aB>
  76. * should be made the router key for the split)
  77. *
  78. * case-insensitive search:
  79. *
  80. * fold search key;
  81. *
  82. * case-insensitive search of B-tree:
  83. * for internal entry, router key is already folded;
  84. * for leaf entry, fold the entry key before comparison.
  85. *
  86. * if (leaf entry case-insensitive match found)
  87. * if (next entry satisfies case-insensitive match)
  88. * return EDUPLICATE;
  89. * if (prev entry satisfies case-insensitive match)
  90. * return EDUPLICATE;
  91. * return match;
  92. * else
  93. * return no match;
  94. *
  95. * serialization:
  96. * target directory inode lock is being held on entry/exit
  97. * of all main directory service routines.
  98. *
  99. * log based recovery:
  100. */
  101. #include <linux/fs.h>
  102. #include <linux/quotaops.h>
  103. #include "jfs_incore.h"
  104. #include "jfs_superblock.h"
  105. #include "jfs_filsys.h"
  106. #include "jfs_metapage.h"
  107. #include "jfs_dmap.h"
  108. #include "jfs_unicode.h"
  109. #include "jfs_debug.h"
  110. /* dtree split parameter */
  111. struct dtsplit {
  112. struct metapage *mp;
  113. s16 index;
  114. s16 nslot;
  115. struct component_name *key;
  116. ddata_t *data;
  117. struct pxdlist *pxdlist;
  118. };
  119. #define DT_PAGE(IP, MP) BT_PAGE(IP, MP, dtpage_t, i_dtroot)
  120. /* get page buffer for specified block address */
  121. #define DT_GETPAGE(IP, BN, MP, SIZE, P, RC)\
  122. {\
  123. BT_GETPAGE(IP, BN, MP, dtpage_t, SIZE, P, RC, i_dtroot)\
  124. if (!(RC))\
  125. {\
  126. if (((P)->header.nextindex > (((BN)==0)?DTROOTMAXSLOT:(P)->header.maxslot)) ||\
  127. ((BN) && ((P)->header.maxslot > DTPAGEMAXSLOT)))\
  128. {\
  129. BT_PUTPAGE(MP);\
  130. jfs_error((IP)->i_sb, "DT_GETPAGE: dtree page corrupt");\
  131. MP = NULL;\
  132. RC = -EIO;\
  133. }\
  134. }\
  135. }
  136. /* for consistency */
  137. #define DT_PUTPAGE(MP) BT_PUTPAGE(MP)
  138. #define DT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
  139. BT_GETSEARCH(IP, LEAF, BN, MP, dtpage_t, P, INDEX, i_dtroot)
  140. /*
  141. * forward references
  142. */
  143. static int dtSplitUp(tid_t tid, struct inode *ip,
  144. struct dtsplit * split, struct btstack * btstack);
  145. static int dtSplitPage(tid_t tid, struct inode *ip, struct dtsplit * split,
  146. struct metapage ** rmpp, dtpage_t ** rpp, pxd_t * rxdp);
  147. static int dtExtendPage(tid_t tid, struct inode *ip,
  148. struct dtsplit * split, struct btstack * btstack);
  149. static int dtSplitRoot(tid_t tid, struct inode *ip,
  150. struct dtsplit * split, struct metapage ** rmpp);
  151. static int dtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
  152. dtpage_t * fp, struct btstack * btstack);
  153. static int dtRelink(tid_t tid, struct inode *ip, dtpage_t * p);
  154. static int dtReadFirst(struct inode *ip, struct btstack * btstack);
  155. static int dtReadNext(struct inode *ip,
  156. loff_t * offset, struct btstack * btstack);
  157. static int dtCompare(struct component_name * key, dtpage_t * p, int si);
  158. static int ciCompare(struct component_name * key, dtpage_t * p, int si,
  159. int flag);
  160. static void dtGetKey(dtpage_t * p, int i, struct component_name * key,
  161. int flag);
  162. static int ciGetLeafPrefixKey(dtpage_t * lp, int li, dtpage_t * rp,
  163. int ri, struct component_name * key, int flag);
  164. static void dtInsertEntry(dtpage_t * p, int index, struct component_name * key,
  165. ddata_t * data, struct dt_lock **);
  166. static void dtMoveEntry(dtpage_t * sp, int si, dtpage_t * dp,
  167. struct dt_lock ** sdtlock, struct dt_lock ** ddtlock,
  168. int do_index);
  169. static void dtDeleteEntry(dtpage_t * p, int fi, struct dt_lock ** dtlock);
  170. static void dtTruncateEntry(dtpage_t * p, int ti, struct dt_lock ** dtlock);
  171. static void dtLinelockFreelist(dtpage_t * p, int m, struct dt_lock ** dtlock);
  172. #define ciToUpper(c) UniStrupr((c)->name)
  173. /*
  174. * read_index_page()
  175. *
  176. * Reads a page of a directory's index table.
  177. * Having metadata mapped into the directory inode's address space
  178. * presents a multitude of problems. We avoid this by mapping to
  179. * the absolute address space outside of the *_metapage routines
  180. */
  181. static struct metapage *read_index_page(struct inode *inode, s64 blkno)
  182. {
  183. int rc;
  184. s64 xaddr;
  185. int xflag;
  186. s32 xlen;
  187. rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1);
  188. if (rc || (xaddr == 0))
  189. return NULL;
  190. return read_metapage(inode, xaddr, PSIZE, 1);
  191. }
  192. /*
  193. * get_index_page()
  194. *
  195. * Same as get_index_page(), but get's a new page without reading
  196. */
  197. static struct metapage *get_index_page(struct inode *inode, s64 blkno)
  198. {
  199. int rc;
  200. s64 xaddr;
  201. int xflag;
  202. s32 xlen;
  203. rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1);
  204. if (rc || (xaddr == 0))
  205. return NULL;
  206. return get_metapage(inode, xaddr, PSIZE, 1);
  207. }
  208. /*
  209. * find_index()
  210. *
  211. * Returns dtree page containing directory table entry for specified
  212. * index and pointer to its entry.
  213. *
  214. * mp must be released by caller.
  215. */
  216. static struct dir_table_slot *find_index(struct inode *ip, u32 index,
  217. struct metapage ** mp, s64 *lblock)
  218. {
  219. struct jfs_inode_info *jfs_ip = JFS_IP(ip);
  220. s64 blkno;
  221. s64 offset;
  222. int page_offset;
  223. struct dir_table_slot *slot;
  224. static int maxWarnings = 10;
  225. if (index < 2) {
  226. if (maxWarnings) {
  227. jfs_warn("find_entry called with index = %d", index);
  228. maxWarnings--;
  229. }
  230. return NULL;
  231. }
  232. if (index >= jfs_ip->next_index) {
  233. jfs_warn("find_entry called with index >= next_index");
  234. return NULL;
  235. }
  236. if (jfs_dirtable_inline(ip)) {
  237. /*
  238. * Inline directory table
  239. */
  240. *mp = NULL;
  241. slot = &jfs_ip->i_dirtable[index - 2];
  242. } else {
  243. offset = (index - 2) * sizeof(struct dir_table_slot);
  244. page_offset = offset & (PSIZE - 1);
  245. blkno = ((offset + 1) >> L2PSIZE) <<
  246. JFS_SBI(ip->i_sb)->l2nbperpage;
  247. if (*mp && (*lblock != blkno)) {
  248. release_metapage(*mp);
  249. *mp = NULL;
  250. }
  251. if (*mp == 0) {
  252. *lblock = blkno;
  253. *mp = read_index_page(ip, blkno);
  254. }
  255. if (*mp == 0) {
  256. jfs_err("free_index: error reading directory table");
  257. return NULL;
  258. }
  259. slot =
  260. (struct dir_table_slot *) ((char *) (*mp)->data +
  261. page_offset);
  262. }
  263. return slot;
  264. }
  265. static inline void lock_index(tid_t tid, struct inode *ip, struct metapage * mp,
  266. u32 index)
  267. {
  268. struct tlock *tlck;
  269. struct linelock *llck;
  270. struct lv *lv;
  271. tlck = txLock(tid, ip, mp, tlckDATA);
  272. llck = (struct linelock *) tlck->lock;
  273. if (llck->index >= llck->maxcnt)
  274. llck = txLinelock(llck);
  275. lv = &llck->lv[llck->index];
  276. /*
  277. * Linelock slot size is twice the size of directory table
  278. * slot size. 512 entries per page.
  279. */
  280. lv->offset = ((index - 2) & 511) >> 1;
  281. lv->length = 1;
  282. llck->index++;
  283. }
  284. /*
  285. * add_index()
  286. *
  287. * Adds an entry to the directory index table. This is used to provide
  288. * each directory entry with a persistent index in which to resume
  289. * directory traversals
  290. */
  291. static u32 add_index(tid_t tid, struct inode *ip, s64 bn, int slot)
  292. {
  293. struct super_block *sb = ip->i_sb;
  294. struct jfs_sb_info *sbi = JFS_SBI(sb);
  295. struct jfs_inode_info *jfs_ip = JFS_IP(ip);
  296. u64 blkno;
  297. struct dir_table_slot *dirtab_slot;
  298. u32 index;
  299. struct linelock *llck;
  300. struct lv *lv;
  301. struct metapage *mp;
  302. s64 offset;
  303. uint page_offset;
  304. struct tlock *tlck;
  305. s64 xaddr;
  306. ASSERT(DO_INDEX(ip));
  307. if (jfs_ip->next_index < 2) {
  308. jfs_warn("add_index: next_index = %d. Resetting!",
  309. jfs_ip->next_index);
  310. jfs_ip->next_index = 2;
  311. }
  312. index = jfs_ip->next_index++;
  313. if (index <= MAX_INLINE_DIRTABLE_ENTRY) {
  314. /*
  315. * i_size reflects size of index table, or 8 bytes per entry.
  316. */
  317. ip->i_size = (loff_t) (index - 1) << 3;
  318. /*
  319. * dir table fits inline within inode
  320. */
  321. dirtab_slot = &jfs_ip->i_dirtable[index-2];
  322. dirtab_slot->flag = DIR_INDEX_VALID;
  323. dirtab_slot->slot = slot;
  324. DTSaddress(dirtab_slot, bn);
  325. set_cflag(COMMIT_Dirtable, ip);
  326. return index;
  327. }
  328. if (index == (MAX_INLINE_DIRTABLE_ENTRY + 1)) {
  329. struct dir_table_slot temp_table[12];
  330. /*
  331. * It's time to move the inline table to an external
  332. * page and begin to build the xtree
  333. */
  334. if (DQUOT_ALLOC_BLOCK(ip, sbi->nbperpage))
  335. goto clean_up;
  336. if (dbAlloc(ip, 0, sbi->nbperpage, &xaddr)) {
  337. DQUOT_FREE_BLOCK(ip, sbi->nbperpage);
  338. goto clean_up;
  339. }
  340. /*
  341. * Save the table, we're going to overwrite it with the
  342. * xtree root
  343. */
  344. memcpy(temp_table, &jfs_ip->i_dirtable, sizeof(temp_table));
  345. /*
  346. * Initialize empty x-tree
  347. */
  348. xtInitRoot(tid, ip);
  349. /*
  350. * Add the first block to the xtree
  351. */
  352. if (xtInsert(tid, ip, 0, 0, sbi->nbperpage, &xaddr, 0)) {
  353. /* This really shouldn't fail */
  354. jfs_warn("add_index: xtInsert failed!");
  355. memcpy(&jfs_ip->i_dirtable, temp_table,
  356. sizeof (temp_table));
  357. dbFree(ip, xaddr, sbi->nbperpage);
  358. DQUOT_FREE_BLOCK(ip, sbi->nbperpage);
  359. goto clean_up;
  360. }
  361. ip->i_size = PSIZE;
  362. if ((mp = get_index_page(ip, 0)) == 0) {
  363. jfs_err("add_index: get_metapage failed!");
  364. xtTruncate(tid, ip, 0, COMMIT_PWMAP);
  365. memcpy(&jfs_ip->i_dirtable, temp_table,
  366. sizeof (temp_table));
  367. goto clean_up;
  368. }
  369. tlck = txLock(tid, ip, mp, tlckDATA);
  370. llck = (struct linelock *) & tlck->lock;
  371. ASSERT(llck->index == 0);
  372. lv = &llck->lv[0];
  373. lv->offset = 0;
  374. lv->length = 6; /* tlckDATA slot size is 16 bytes */
  375. llck->index++;
  376. memcpy(mp->data, temp_table, sizeof(temp_table));
  377. mark_metapage_dirty(mp);
  378. release_metapage(mp);
  379. /*
  380. * Logging is now directed by xtree tlocks
  381. */
  382. clear_cflag(COMMIT_Dirtable, ip);
  383. }
  384. offset = (index - 2) * sizeof(struct dir_table_slot);
  385. page_offset = offset & (PSIZE - 1);
  386. blkno = ((offset + 1) >> L2PSIZE) << sbi->l2nbperpage;
  387. if (page_offset == 0) {
  388. /*
  389. * This will be the beginning of a new page
  390. */
  391. xaddr = 0;
  392. if (xtInsert(tid, ip, 0, blkno, sbi->nbperpage, &xaddr, 0)) {
  393. jfs_warn("add_index: xtInsert failed!");
  394. goto clean_up;
  395. }
  396. ip->i_size += PSIZE;
  397. if ((mp = get_index_page(ip, blkno)))
  398. memset(mp->data, 0, PSIZE); /* Just looks better */
  399. else
  400. xtTruncate(tid, ip, offset, COMMIT_PWMAP);
  401. } else
  402. mp = read_index_page(ip, blkno);
  403. if (mp == 0) {
  404. jfs_err("add_index: get/read_metapage failed!");
  405. goto clean_up;
  406. }
  407. lock_index(tid, ip, mp, index);
  408. dirtab_slot =
  409. (struct dir_table_slot *) ((char *) mp->data + page_offset);
  410. dirtab_slot->flag = DIR_INDEX_VALID;
  411. dirtab_slot->slot = slot;
  412. DTSaddress(dirtab_slot, bn);
  413. mark_metapage_dirty(mp);
  414. release_metapage(mp);
  415. return index;
  416. clean_up:
  417. jfs_ip->next_index--;
  418. return 0;
  419. }
  420. /*
  421. * free_index()
  422. *
  423. * Marks an entry to the directory index table as free.
  424. */
  425. static void free_index(tid_t tid, struct inode *ip, u32 index, u32 next)
  426. {
  427. struct dir_table_slot *dirtab_slot;
  428. s64 lblock;
  429. struct metapage *mp = NULL;
  430. dirtab_slot = find_index(ip, index, &mp, &lblock);
  431. if (dirtab_slot == 0)
  432. return;
  433. dirtab_slot->flag = DIR_INDEX_FREE;
  434. dirtab_slot->slot = dirtab_slot->addr1 = 0;
  435. dirtab_slot->addr2 = cpu_to_le32(next);
  436. if (mp) {
  437. lock_index(tid, ip, mp, index);
  438. mark_metapage_dirty(mp);
  439. release_metapage(mp);
  440. } else
  441. set_cflag(COMMIT_Dirtable, ip);
  442. }
  443. /*
  444. * modify_index()
  445. *
  446. * Changes an entry in the directory index table
  447. */
  448. static void modify_index(tid_t tid, struct inode *ip, u32 index, s64 bn,
  449. int slot, struct metapage ** mp, u64 *lblock)
  450. {
  451. struct dir_table_slot *dirtab_slot;
  452. dirtab_slot = find_index(ip, index, mp, lblock);
  453. if (dirtab_slot == 0)
  454. return;
  455. DTSaddress(dirtab_slot, bn);
  456. dirtab_slot->slot = slot;
  457. if (*mp) {
  458. lock_index(tid, ip, *mp, index);
  459. mark_metapage_dirty(*mp);
  460. } else
  461. set_cflag(COMMIT_Dirtable, ip);
  462. }
  463. /*
  464. * read_index()
  465. *
  466. * reads a directory table slot
  467. */
  468. static int read_index(struct inode *ip, u32 index,
  469. struct dir_table_slot * dirtab_slot)
  470. {
  471. s64 lblock;
  472. struct metapage *mp = NULL;
  473. struct dir_table_slot *slot;
  474. slot = find_index(ip, index, &mp, &lblock);
  475. if (slot == 0) {
  476. return -EIO;
  477. }
  478. memcpy(dirtab_slot, slot, sizeof(struct dir_table_slot));
  479. if (mp)
  480. release_metapage(mp);
  481. return 0;
  482. }
  483. /*
  484. * dtSearch()
  485. *
  486. * function:
  487. * Search for the entry with specified key
  488. *
  489. * parameter:
  490. *
  491. * return: 0 - search result on stack, leaf page pinned;
  492. * errno - I/O error
  493. */
  494. int dtSearch(struct inode *ip, struct component_name * key, ino_t * data,
  495. struct btstack * btstack, int flag)
  496. {
  497. int rc = 0;
  498. int cmp = 1; /* init for empty page */
  499. s64 bn;
  500. struct metapage *mp;
  501. dtpage_t *p;
  502. s8 *stbl;
  503. int base, index, lim;
  504. struct btframe *btsp;
  505. pxd_t *pxd;
  506. int psize = 288; /* initial in-line directory */
  507. ino_t inumber;
  508. struct component_name ciKey;
  509. struct super_block *sb = ip->i_sb;
  510. ciKey.name =
  511. (wchar_t *) kmalloc((JFS_NAME_MAX + 1) * sizeof(wchar_t),
  512. GFP_NOFS);
  513. if (ciKey.name == 0) {
  514. rc = -ENOMEM;
  515. goto dtSearch_Exit2;
  516. }
  517. /* uppercase search key for c-i directory */
  518. UniStrcpy(ciKey.name, key->name);
  519. ciKey.namlen = key->namlen;
  520. /* only uppercase if case-insensitive support is on */
  521. if ((JFS_SBI(sb)->mntflag & JFS_OS2) == JFS_OS2) {
  522. ciToUpper(&ciKey);
  523. }
  524. BT_CLR(btstack); /* reset stack */
  525. /* init level count for max pages to split */
  526. btstack->nsplit = 1;
  527. /*
  528. * search down tree from root:
  529. *
  530. * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
  531. * internal page, child page Pi contains entry with k, Ki <= K < Kj.
  532. *
  533. * if entry with search key K is not found
  534. * internal page search find the entry with largest key Ki
  535. * less than K which point to the child page to search;
  536. * leaf page search find the entry with smallest key Kj
  537. * greater than K so that the returned index is the position of
  538. * the entry to be shifted right for insertion of new entry.
  539. * for empty tree, search key is greater than any key of the tree.
  540. *
  541. * by convention, root bn = 0.
  542. */
  543. for (bn = 0;;) {
  544. /* get/pin the page to search */
  545. DT_GETPAGE(ip, bn, mp, psize, p, rc);
  546. if (rc)
  547. goto dtSearch_Exit1;
  548. /* get sorted entry table of the page */
  549. stbl = DT_GETSTBL(p);
  550. /*
  551. * binary search with search key K on the current page.
  552. */
  553. for (base = 0, lim = p->header.nextindex; lim; lim >>= 1) {
  554. index = base + (lim >> 1);
  555. if (p->header.flag & BT_LEAF) {
  556. /* uppercase leaf name to compare */
  557. cmp =
  558. ciCompare(&ciKey, p, stbl[index],
  559. JFS_SBI(sb)->mntflag);
  560. } else {
  561. /* router key is in uppercase */
  562. cmp = dtCompare(&ciKey, p, stbl[index]);
  563. }
  564. if (cmp == 0) {
  565. /*
  566. * search hit
  567. */
  568. /* search hit - leaf page:
  569. * return the entry found
  570. */
  571. if (p->header.flag & BT_LEAF) {
  572. inumber = le32_to_cpu(
  573. ((struct ldtentry *) & p->slot[stbl[index]])->inumber);
  574. /*
  575. * search for JFS_LOOKUP
  576. */
  577. if (flag == JFS_LOOKUP) {
  578. *data = inumber;
  579. rc = 0;
  580. goto out;
  581. }
  582. /*
  583. * search for JFS_CREATE
  584. */
  585. if (flag == JFS_CREATE) {
  586. *data = inumber;
  587. rc = -EEXIST;
  588. goto out;
  589. }
  590. /*
  591. * search for JFS_REMOVE or JFS_RENAME
  592. */
  593. if ((flag == JFS_REMOVE ||
  594. flag == JFS_RENAME) &&
  595. *data != inumber) {
  596. rc = -ESTALE;
  597. goto out;
  598. }
  599. /*
  600. * JFS_REMOVE|JFS_FINDDIR|JFS_RENAME
  601. */
  602. /* save search result */
  603. *data = inumber;
  604. btsp = btstack->top;
  605. btsp->bn = bn;
  606. btsp->index = index;
  607. btsp->mp = mp;
  608. rc = 0;
  609. goto dtSearch_Exit1;
  610. }
  611. /* search hit - internal page:
  612. * descend/search its child page
  613. */
  614. goto getChild;
  615. }
  616. if (cmp > 0) {
  617. base = index + 1;
  618. --lim;
  619. }
  620. }
  621. /*
  622. * search miss
  623. *
  624. * base is the smallest index with key (Kj) greater than
  625. * search key (K) and may be zero or (maxindex + 1) index.
  626. */
  627. /*
  628. * search miss - leaf page
  629. *
  630. * return location of entry (base) where new entry with
  631. * search key K is to be inserted.
  632. */
  633. if (p->header.flag & BT_LEAF) {
  634. /*
  635. * search for JFS_LOOKUP, JFS_REMOVE, or JFS_RENAME
  636. */
  637. if (flag == JFS_LOOKUP || flag == JFS_REMOVE ||
  638. flag == JFS_RENAME) {
  639. rc = -ENOENT;
  640. goto out;
  641. }
  642. /*
  643. * search for JFS_CREATE|JFS_FINDDIR:
  644. *
  645. * save search result
  646. */
  647. *data = 0;
  648. btsp = btstack->top;
  649. btsp->bn = bn;
  650. btsp->index = base;
  651. btsp->mp = mp;
  652. rc = 0;
  653. goto dtSearch_Exit1;
  654. }
  655. /*
  656. * search miss - internal page
  657. *
  658. * if base is non-zero, decrement base by one to get the parent
  659. * entry of the child page to search.
  660. */
  661. index = base ? base - 1 : base;
  662. /*
  663. * go down to child page
  664. */
  665. getChild:
  666. /* update max. number of pages to split */
  667. if (BT_STACK_FULL(btstack)) {
  668. /* Something's corrupted, mark filesytem dirty so
  669. * chkdsk will fix it.
  670. */
  671. jfs_error(sb, "stack overrun in dtSearch!");
  672. BT_STACK_DUMP(btstack);
  673. rc = -EIO;
  674. goto out;
  675. }
  676. btstack->nsplit++;
  677. /* push (bn, index) of the parent page/entry */
  678. BT_PUSH(btstack, bn, index);
  679. /* get the child page block number */
  680. pxd = (pxd_t *) & p->slot[stbl[index]];
  681. bn = addressPXD(pxd);
  682. psize = lengthPXD(pxd) << JFS_SBI(ip->i_sb)->l2bsize;
  683. /* unpin the parent page */
  684. DT_PUTPAGE(mp);
  685. }
  686. out:
  687. DT_PUTPAGE(mp);
  688. dtSearch_Exit1:
  689. kfree(ciKey.name);
  690. dtSearch_Exit2:
  691. return rc;
  692. }
  693. /*
  694. * dtInsert()
  695. *
  696. * function: insert an entry to directory tree
  697. *
  698. * parameter:
  699. *
  700. * return: 0 - success;
  701. * errno - failure;
  702. */
  703. int dtInsert(tid_t tid, struct inode *ip,
  704. struct component_name * name, ino_t * fsn, struct btstack * btstack)
  705. {
  706. int rc = 0;
  707. struct metapage *mp; /* meta-page buffer */
  708. dtpage_t *p; /* base B+-tree index page */
  709. s64 bn;
  710. int index;
  711. struct dtsplit split; /* split information */
  712. ddata_t data;
  713. struct dt_lock *dtlck;
  714. int n;
  715. struct tlock *tlck;
  716. struct lv *lv;
  717. /*
  718. * retrieve search result
  719. *
  720. * dtSearch() returns (leaf page pinned, index at which to insert).
  721. * n.b. dtSearch() may return index of (maxindex + 1) of
  722. * the full page.
  723. */
  724. DT_GETSEARCH(ip, btstack->top, bn, mp, p, index);
  725. /*
  726. * insert entry for new key
  727. */
  728. if (DO_INDEX(ip)) {
  729. if (JFS_IP(ip)->next_index == DIREND) {
  730. DT_PUTPAGE(mp);
  731. return -EMLINK;
  732. }
  733. n = NDTLEAF(name->namlen);
  734. data.leaf.tid = tid;
  735. data.leaf.ip = ip;
  736. } else {
  737. n = NDTLEAF_LEGACY(name->namlen);
  738. data.leaf.ip = NULL; /* signifies legacy directory format */
  739. }
  740. data.leaf.ino = *fsn;
  741. /*
  742. * leaf page does not have enough room for new entry:
  743. *
  744. * extend/split the leaf page;
  745. *
  746. * dtSplitUp() will insert the entry and unpin the leaf page.
  747. */
  748. if (n > p->header.freecnt) {
  749. split.mp = mp;
  750. split.index = index;
  751. split.nslot = n;
  752. split.key = name;
  753. split.data = &data;
  754. rc = dtSplitUp(tid, ip, &split, btstack);
  755. return rc;
  756. }
  757. /*
  758. * leaf page does have enough room for new entry:
  759. *
  760. * insert the new data entry into the leaf page;
  761. */
  762. BT_MARK_DIRTY(mp, ip);
  763. /*
  764. * acquire a transaction lock on the leaf page
  765. */
  766. tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY);
  767. dtlck = (struct dt_lock *) & tlck->lock;
  768. ASSERT(dtlck->index == 0);
  769. lv = & dtlck->lv[0];
  770. /* linelock header */
  771. lv->offset = 0;
  772. lv->length = 1;
  773. dtlck->index++;
  774. dtInsertEntry(p, index, name, &data, &dtlck);
  775. /* linelock stbl of non-root leaf page */
  776. if (!(p->header.flag & BT_ROOT)) {
  777. if (dtlck->index >= dtlck->maxcnt)
  778. dtlck = (struct dt_lock *) txLinelock(dtlck);
  779. lv = & dtlck->lv[dtlck->index];
  780. n = index >> L2DTSLOTSIZE;
  781. lv->offset = p->header.stblindex + n;
  782. lv->length =
  783. ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1;
  784. dtlck->index++;
  785. }
  786. /* unpin the leaf page */
  787. DT_PUTPAGE(mp);
  788. return 0;
  789. }
  790. /*
  791. * dtSplitUp()
  792. *
  793. * function: propagate insertion bottom up;
  794. *
  795. * parameter:
  796. *
  797. * return: 0 - success;
  798. * errno - failure;
  799. * leaf page unpinned;
  800. */
  801. static int dtSplitUp(tid_t tid,
  802. struct inode *ip, struct dtsplit * split, struct btstack * btstack)
  803. {
  804. struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
  805. int rc = 0;
  806. struct metapage *smp;
  807. dtpage_t *sp; /* split page */
  808. struct metapage *rmp;
  809. dtpage_t *rp; /* new right page split from sp */
  810. pxd_t rpxd; /* new right page extent descriptor */
  811. struct metapage *lmp;
  812. dtpage_t *lp; /* left child page */
  813. int skip; /* index of entry of insertion */
  814. struct btframe *parent; /* parent page entry on traverse stack */
  815. s64 xaddr, nxaddr;
  816. int xlen, xsize;
  817. struct pxdlist pxdlist;
  818. pxd_t *pxd;
  819. struct component_name key = { 0, NULL };
  820. ddata_t *data = split->data;
  821. int n;
  822. struct dt_lock *dtlck;
  823. struct tlock *tlck;
  824. struct lv *lv;
  825. int quota_allocation = 0;
  826. /* get split page */
  827. smp = split->mp;
  828. sp = DT_PAGE(ip, smp);
  829. key.name =
  830. (wchar_t *) kmalloc((JFS_NAME_MAX + 2) * sizeof(wchar_t),
  831. GFP_NOFS);
  832. if (key.name == 0) {
  833. DT_PUTPAGE(smp);
  834. rc = -ENOMEM;
  835. goto dtSplitUp_Exit;
  836. }
  837. /*
  838. * split leaf page
  839. *
  840. * The split routines insert the new entry, and
  841. * acquire txLock as appropriate.
  842. */
  843. /*
  844. * split root leaf page:
  845. */
  846. if (sp->header.flag & BT_ROOT) {
  847. /*
  848. * allocate a single extent child page
  849. */
  850. xlen = 1;
  851. n = sbi->bsize >> L2DTSLOTSIZE;
  852. n -= (n + 31) >> L2DTSLOTSIZE; /* stbl size */
  853. n -= DTROOTMAXSLOT - sp->header.freecnt; /* header + entries */
  854. if (n <= split->nslot)
  855. xlen++;
  856. if ((rc = dbAlloc(ip, 0, (s64) xlen, &xaddr))) {
  857. DT_PUTPAGE(smp);
  858. goto freeKeyName;
  859. }
  860. pxdlist.maxnpxd = 1;
  861. pxdlist.npxd = 0;
  862. pxd = &pxdlist.pxd[0];
  863. PXDaddress(pxd, xaddr);
  864. PXDlength(pxd, xlen);
  865. split->pxdlist = &pxdlist;
  866. rc = dtSplitRoot(tid, ip, split, &rmp);
  867. if (rc)
  868. dbFree(ip, xaddr, xlen);
  869. else
  870. DT_PUTPAGE(rmp);
  871. DT_PUTPAGE(smp);
  872. if (!DO_INDEX(ip))
  873. ip->i_size = xlen << sbi->l2bsize;
  874. goto freeKeyName;
  875. }
  876. /*
  877. * extend first leaf page
  878. *
  879. * extend the 1st extent if less than buffer page size
  880. * (dtExtendPage() reurns leaf page unpinned)
  881. */
  882. pxd = &sp->header.self;
  883. xlen = lengthPXD(pxd);
  884. xsize = xlen << sbi->l2bsize;
  885. if (xsize < PSIZE) {
  886. xaddr = addressPXD(pxd);
  887. n = xsize >> L2DTSLOTSIZE;
  888. n -= (n + 31) >> L2DTSLOTSIZE; /* stbl size */
  889. if ((n + sp->header.freecnt) <= split->nslot)
  890. n = xlen + (xlen << 1);
  891. else
  892. n = xlen;
  893. /* Allocate blocks to quota. */
  894. if (DQUOT_ALLOC_BLOCK(ip, n)) {
  895. rc = -EDQUOT;
  896. goto extendOut;
  897. }
  898. quota_allocation += n;
  899. if ((rc = dbReAlloc(sbi->ipbmap, xaddr, (s64) xlen,
  900. (s64) n, &nxaddr)))
  901. goto extendOut;
  902. pxdlist.maxnpxd = 1;
  903. pxdlist.npxd = 0;
  904. pxd = &pxdlist.pxd[0];
  905. PXDaddress(pxd, nxaddr)
  906. PXDlength(pxd, xlen + n);
  907. split->pxdlist = &pxdlist;
  908. if ((rc = dtExtendPage(tid, ip, split, btstack))) {
  909. nxaddr = addressPXD(pxd);
  910. if (xaddr != nxaddr) {
  911. /* free relocated extent */
  912. xlen = lengthPXD(pxd);
  913. dbFree(ip, nxaddr, (s64) xlen);
  914. } else {
  915. /* free extended delta */
  916. xlen = lengthPXD(pxd) - n;
  917. xaddr = addressPXD(pxd) + xlen;
  918. dbFree(ip, xaddr, (s64) n);
  919. }
  920. } else if (!DO_INDEX(ip))
  921. ip->i_size = lengthPXD(pxd) << sbi->l2bsize;
  922. extendOut:
  923. DT_PUTPAGE(smp);
  924. goto freeKeyName;
  925. }
  926. /*
  927. * split leaf page <sp> into <sp> and a new right page <rp>.
  928. *
  929. * return <rp> pinned and its extent descriptor <rpxd>
  930. */
  931. /*
  932. * allocate new directory page extent and
  933. * new index page(s) to cover page split(s)
  934. *
  935. * allocation hint: ?
  936. */
  937. n = btstack->nsplit;
  938. pxdlist.maxnpxd = pxdlist.npxd = 0;
  939. xlen = sbi->nbperpage;
  940. for (pxd = pxdlist.pxd; n > 0; n--, pxd++) {
  941. if ((rc = dbAlloc(ip, 0, (s64) xlen, &xaddr)) == 0) {
  942. PXDaddress(pxd, xaddr);
  943. PXDlength(pxd, xlen);
  944. pxdlist.maxnpxd++;
  945. continue;
  946. }
  947. DT_PUTPAGE(smp);
  948. /* undo allocation */
  949. goto splitOut;
  950. }
  951. split->pxdlist = &pxdlist;
  952. if ((rc = dtSplitPage(tid, ip, split, &rmp, &rp, &rpxd))) {
  953. DT_PUTPAGE(smp);
  954. /* undo allocation */
  955. goto splitOut;
  956. }
  957. if (!DO_INDEX(ip))
  958. ip->i_size += PSIZE;
  959. /*
  960. * propagate up the router entry for the leaf page just split
  961. *
  962. * insert a router entry for the new page into the parent page,
  963. * propagate the insert/split up the tree by walking back the stack
  964. * of (bn of parent page, index of child page entry in parent page)
  965. * that were traversed during the search for the page that split.
  966. *
  967. * the propagation of insert/split up the tree stops if the root
  968. * splits or the page inserted into doesn't have to split to hold
  969. * the new entry.
  970. *
  971. * the parent entry for the split page remains the same, and
  972. * a new entry is inserted at its right with the first key and
  973. * block number of the new right page.
  974. *
  975. * There are a maximum of 4 pages pinned at any time:
  976. * two children, left parent and right parent (when the parent splits).
  977. * keep the child pages pinned while working on the parent.
  978. * make sure that all pins are released at exit.
  979. */
  980. while ((parent = BT_POP(btstack)) != NULL) {
  981. /* parent page specified by stack frame <parent> */
  982. /* keep current child pages (<lp>, <rp>) pinned */
  983. lmp = smp;
  984. lp = sp;
  985. /*
  986. * insert router entry in parent for new right child page <rp>
  987. */
  988. /* get the parent page <sp> */
  989. DT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc);
  990. if (rc) {
  991. DT_PUTPAGE(lmp);
  992. DT_PUTPAGE(rmp);
  993. goto splitOut;
  994. }
  995. /*
  996. * The new key entry goes ONE AFTER the index of parent entry,
  997. * because the split was to the right.
  998. */
  999. skip = parent->index + 1;
  1000. /*
  1001. * compute the key for the router entry
  1002. *
  1003. * key suffix compression:
  1004. * for internal pages that have leaf pages as children,
  1005. * retain only what's needed to distinguish between
  1006. * the new entry and the entry on the page to its left.
  1007. * If the keys compare equal, retain the entire key.
  1008. *
  1009. * note that compression is performed only at computing
  1010. * router key at the lowest internal level.
  1011. * further compression of the key between pairs of higher
  1012. * level internal pages loses too much information and
  1013. * the search may fail.
  1014. * (e.g., two adjacent leaf pages of {a, ..., x} {xx, ...,}
  1015. * results in two adjacent parent entries (a)(xx).
  1016. * if split occurs between these two entries, and
  1017. * if compression is applied, the router key of parent entry
  1018. * of right page (x) will divert search for x into right
  1019. * subtree and miss x in the left subtree.)
  1020. *
  1021. * the entire key must be retained for the next-to-leftmost
  1022. * internal key at any level of the tree, or search may fail
  1023. * (e.g., ?)
  1024. */
  1025. switch (rp->header.flag & BT_TYPE) {
  1026. case BT_LEAF:
  1027. /*
  1028. * compute the length of prefix for suffix compression
  1029. * between last entry of left page and first entry
  1030. * of right page
  1031. */
  1032. if ((sp->header.flag & BT_ROOT && skip > 1) ||
  1033. sp->header.prev != 0 || skip > 1) {
  1034. /* compute uppercase router prefix key */
  1035. rc = ciGetLeafPrefixKey(lp,
  1036. lp->header.nextindex-1,
  1037. rp, 0, &key,
  1038. sbi->mntflag);
  1039. if (rc) {
  1040. DT_PUTPAGE(lmp);
  1041. DT_PUTPAGE(rmp);
  1042. DT_PUTPAGE(smp);
  1043. goto splitOut;
  1044. }
  1045. } else {
  1046. /* next to leftmost entry of
  1047. lowest internal level */
  1048. /* compute uppercase router key */
  1049. dtGetKey(rp, 0, &key, sbi->mntflag);
  1050. key.name[key.namlen] = 0;
  1051. if ((sbi->mntflag & JFS_OS2) == JFS_OS2)
  1052. ciToUpper(&key);
  1053. }
  1054. n = NDTINTERNAL(key.namlen);
  1055. break;
  1056. case BT_INTERNAL:
  1057. dtGetKey(rp, 0, &key, sbi->mntflag);
  1058. n = NDTINTERNAL(key.namlen);
  1059. break;
  1060. default:
  1061. jfs_err("dtSplitUp(): UFO!");
  1062. break;
  1063. }
  1064. /* unpin left child page */
  1065. DT_PUTPAGE(lmp);
  1066. /*
  1067. * compute the data for the router entry
  1068. */
  1069. data->xd = rpxd; /* child page xd */
  1070. /*
  1071. * parent page is full - split the parent page
  1072. */
  1073. if (n > sp->header.freecnt) {
  1074. /* init for parent page split */
  1075. split->mp = smp;
  1076. split->index = skip; /* index at insert */
  1077. split->nslot = n;
  1078. split->key = &key;
  1079. /* split->data = data; */
  1080. /* unpin right child page */
  1081. DT_PUTPAGE(rmp);
  1082. /* The split routines insert the new entry,
  1083. * acquire txLock as appropriate.
  1084. * return <rp> pinned and its block number <rbn>.
  1085. */
  1086. rc = (sp->header.flag & BT_ROOT) ?
  1087. dtSplitRoot(tid, ip, split, &rmp) :
  1088. dtSplitPage(tid, ip, split, &rmp, &rp, &rpxd);
  1089. if (rc) {
  1090. DT_PUTPAGE(smp);
  1091. goto splitOut;
  1092. }
  1093. /* smp and rmp are pinned */
  1094. }
  1095. /*
  1096. * parent page is not full - insert router entry in parent page
  1097. */
  1098. else {
  1099. BT_MARK_DIRTY(smp, ip);
  1100. /*
  1101. * acquire a transaction lock on the parent page
  1102. */
  1103. tlck = txLock(tid, ip, smp, tlckDTREE | tlckENTRY);
  1104. dtlck = (struct dt_lock *) & tlck->lock;
  1105. ASSERT(dtlck->index == 0);
  1106. lv = & dtlck->lv[0];
  1107. /* linelock header */
  1108. lv->offset = 0;
  1109. lv->length = 1;
  1110. dtlck->index++;
  1111. /* linelock stbl of non-root parent page */
  1112. if (!(sp->header.flag & BT_ROOT)) {
  1113. lv++;
  1114. n = skip >> L2DTSLOTSIZE;
  1115. lv->offset = sp->header.stblindex + n;
  1116. lv->length =
  1117. ((sp->header.nextindex -
  1118. 1) >> L2DTSLOTSIZE) - n + 1;
  1119. dtlck->index++;
  1120. }
  1121. dtInsertEntry(sp, skip, &key, data, &dtlck);
  1122. /* exit propagate up */
  1123. break;
  1124. }
  1125. }
  1126. /* unpin current split and its right page */
  1127. DT_PUTPAGE(smp);
  1128. DT_PUTPAGE(rmp);
  1129. /*
  1130. * free remaining extents allocated for split
  1131. */
  1132. splitOut:
  1133. n = pxdlist.npxd;
  1134. pxd = &pxdlist.pxd[n];
  1135. for (; n < pxdlist.maxnpxd; n++, pxd++)
  1136. dbFree(ip, addressPXD(pxd), (s64) lengthPXD(pxd));
  1137. freeKeyName:
  1138. kfree(key.name);
  1139. /* Rollback quota allocation */
  1140. if (rc && quota_allocation)
  1141. DQUOT_FREE_BLOCK(ip, quota_allocation);
  1142. dtSplitUp_Exit:
  1143. return rc;
  1144. }
  1145. /*
  1146. * dtSplitPage()
  1147. *
  1148. * function: Split a non-root page of a btree.
  1149. *
  1150. * parameter:
  1151. *
  1152. * return: 0 - success;
  1153. * errno - failure;
  1154. * return split and new page pinned;
  1155. */
  1156. static int dtSplitPage(tid_t tid, struct inode *ip, struct dtsplit * split,
  1157. struct metapage ** rmpp, dtpage_t ** rpp, pxd_t * rpxdp)
  1158. {
  1159. int rc = 0;
  1160. struct metapage *smp;
  1161. dtpage_t *sp;
  1162. struct metapage *rmp;
  1163. dtpage_t *rp; /* new right page allocated */
  1164. s64 rbn; /* new right page block number */
  1165. struct metapage *mp;
  1166. dtpage_t *p;
  1167. s64 nextbn;
  1168. struct pxdlist *pxdlist;
  1169. pxd_t *pxd;
  1170. int skip, nextindex, half, left, nxt, off, si;
  1171. struct ldtentry *ldtentry;
  1172. struct idtentry *idtentry;
  1173. u8 *stbl;
  1174. struct dtslot *f;
  1175. int fsi, stblsize;
  1176. int n;
  1177. struct dt_lock *sdtlck, *rdtlck;
  1178. struct tlock *tlck;
  1179. struct dt_lock *dtlck;
  1180. struct lv *slv, *rlv, *lv;
  1181. /* get split page */
  1182. smp = split->mp;
  1183. sp = DT_PAGE(ip, smp);
  1184. /*
  1185. * allocate the new right page for the split
  1186. */
  1187. pxdlist = split->pxdlist;
  1188. pxd = &pxdlist->pxd[pxdlist->npxd];
  1189. pxdlist->npxd++;
  1190. rbn = addressPXD(pxd);
  1191. rmp = get_metapage(ip, rbn, PSIZE, 1);
  1192. if (rmp == NULL)
  1193. return -EIO;
  1194. /* Allocate blocks to quota. */
  1195. if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) {
  1196. release_metapage(rmp);
  1197. return -EDQUOT;
  1198. }
  1199. jfs_info("dtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
  1200. BT_MARK_DIRTY(rmp, ip);
  1201. /*
  1202. * acquire a transaction lock on the new right page
  1203. */
  1204. tlck = txLock(tid, ip, rmp, tlckDTREE | tlckNEW);
  1205. rdtlck = (struct dt_lock *) & tlck->lock;
  1206. rp = (dtpage_t *) rmp->data;
  1207. *rpp = rp;
  1208. rp->header.self = *pxd;
  1209. BT_MARK_DIRTY(smp, ip);
  1210. /*
  1211. * acquire a transaction lock on the split page
  1212. *
  1213. * action:
  1214. */
  1215. tlck = txLock(tid, ip, smp, tlckDTREE | tlckENTRY);
  1216. sdtlck = (struct dt_lock *) & tlck->lock;
  1217. /* linelock header of split page */
  1218. ASSERT(sdtlck->index == 0);
  1219. slv = & sdtlck->lv[0];
  1220. slv->offset = 0;
  1221. slv->length = 1;
  1222. sdtlck->index++;
  1223. /*
  1224. * initialize/update sibling pointers between sp and rp
  1225. */
  1226. nextbn = le64_to_cpu(sp->header.next);
  1227. rp->header.next = cpu_to_le64(nextbn);
  1228. rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
  1229. sp->header.next = cpu_to_le64(rbn);
  1230. /*
  1231. * initialize new right page
  1232. */
  1233. rp->header.flag = sp->header.flag;
  1234. /* compute sorted entry table at start of extent data area */
  1235. rp->header.nextindex = 0;
  1236. rp->header.stblindex = 1;
  1237. n = PSIZE >> L2DTSLOTSIZE;
  1238. rp->header.maxslot = n;
  1239. stblsize = (n + 31) >> L2DTSLOTSIZE; /* in unit of slot */
  1240. /* init freelist */
  1241. fsi = rp->header.stblindex + stblsize;
  1242. rp->header.freelist = fsi;
  1243. rp->header.freecnt = rp->header.maxslot - fsi;
  1244. /*
  1245. * sequential append at tail: append without split
  1246. *
  1247. * If splitting the last page on a level because of appending
  1248. * a entry to it (skip is maxentry), it's likely that the access is
  1249. * sequential. Adding an empty page on the side of the level is less
  1250. * work and can push the fill factor much higher than normal.
  1251. * If we're wrong it's no big deal, we'll just do the split the right
  1252. * way next time.
  1253. * (It may look like it's equally easy to do a similar hack for
  1254. * reverse sorted data, that is, split the tree left,
  1255. * but it's not. Be my guest.)
  1256. */
  1257. if (nextbn == 0 && split->index == sp->header.nextindex) {
  1258. /* linelock header + stbl (first slot) of new page */
  1259. rlv = & rdtlck->lv[rdtlck->index];
  1260. rlv->offset = 0;
  1261. rlv->length = 2;
  1262. rdtlck->index++;
  1263. /*
  1264. * initialize freelist of new right page
  1265. */
  1266. f = &rp->slot[fsi];
  1267. for (fsi++; fsi < rp->header.maxslot; f++, fsi++)
  1268. f->next = fsi;
  1269. f->next = -1;
  1270. /* insert entry at the first entry of the new right page */
  1271. dtInsertEntry(rp, 0, split->key, split->data, &rdtlck);
  1272. goto out;
  1273. }
  1274. /*
  1275. * non-sequential insert (at possibly middle page)
  1276. */
  1277. /*
  1278. * update prev pointer of previous right sibling page;
  1279. */
  1280. if (nextbn != 0) {
  1281. DT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
  1282. if (rc) {
  1283. discard_metapage(rmp);
  1284. return rc;
  1285. }
  1286. BT_MARK_DIRTY(mp, ip);
  1287. /*
  1288. * acquire a transaction lock on the next page
  1289. */
  1290. tlck = txLock(tid, ip, mp, tlckDTREE | tlckRELINK);
  1291. jfs_info("dtSplitPage: tlck = 0x%p, ip = 0x%p, mp=0x%p",
  1292. tlck, ip, mp);
  1293. dtlck = (struct dt_lock *) & tlck->lock;
  1294. /* linelock header of previous right sibling page */
  1295. lv = & dtlck->lv[dtlck->index];
  1296. lv->offset = 0;
  1297. lv->length = 1;
  1298. dtlck->index++;
  1299. p->header.prev = cpu_to_le64(rbn);
  1300. DT_PUTPAGE(mp);
  1301. }
  1302. /*
  1303. * split the data between the split and right pages.
  1304. */
  1305. skip = split->index;
  1306. half = (PSIZE >> L2DTSLOTSIZE) >> 1; /* swag */
  1307. left = 0;
  1308. /*
  1309. * compute fill factor for split pages
  1310. *
  1311. * <nxt> traces the next entry to move to rp
  1312. * <off> traces the next entry to stay in sp
  1313. */
  1314. stbl = (u8 *) & sp->slot[sp->header.stblindex];
  1315. nextindex = sp->header.nextindex;
  1316. for (nxt = off = 0; nxt < nextindex; ++off) {
  1317. if (off == skip)
  1318. /* check for fill factor with new entry size */
  1319. n = split->nslot;
  1320. else {
  1321. si = stbl[nxt];
  1322. switch (sp->header.flag & BT_TYPE) {
  1323. case BT_LEAF:
  1324. ldtentry = (struct ldtentry *) & sp->slot[si];
  1325. if (DO_INDEX(ip))
  1326. n = NDTLEAF(ldtentry->namlen);
  1327. else
  1328. n = NDTLEAF_LEGACY(ldtentry->
  1329. namlen);
  1330. break;
  1331. case BT_INTERNAL:
  1332. idtentry = (struct idtentry *) & sp->slot[si];
  1333. n = NDTINTERNAL(idtentry->namlen);
  1334. break;
  1335. default:
  1336. break;
  1337. }
  1338. ++nxt; /* advance to next entry to move in sp */
  1339. }
  1340. left += n;
  1341. if (left >= half)
  1342. break;
  1343. }
  1344. /* <nxt> poins to the 1st entry to move */
  1345. /*
  1346. * move entries to right page
  1347. *
  1348. * dtMoveEntry() initializes rp and reserves entry for insertion
  1349. *
  1350. * split page moved out entries are linelocked;
  1351. * new/right page moved in entries are linelocked;
  1352. */
  1353. /* linelock header + stbl of new right page */
  1354. rlv = & rdtlck->lv[rdtlck->index];
  1355. rlv->offset = 0;
  1356. rlv->length = 5;
  1357. rdtlck->index++;
  1358. dtMoveEntry(sp, nxt, rp, &sdtlck, &rdtlck, DO_INDEX(ip));
  1359. sp->header.nextindex = nxt;
  1360. /*
  1361. * finalize freelist of new right page
  1362. */
  1363. fsi = rp->header.freelist;
  1364. f = &rp->slot[fsi];
  1365. for (fsi++; fsi < rp->header.maxslot; f++, fsi++)
  1366. f->next = fsi;
  1367. f->next = -1;
  1368. /*
  1369. * Update directory index table for entries now in right page
  1370. */
  1371. if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) {
  1372. s64 lblock;
  1373. mp = NULL;
  1374. stbl = DT_GETSTBL(rp);
  1375. for (n = 0; n < rp->header.nextindex; n++) {
  1376. ldtentry = (struct ldtentry *) & rp->slot[stbl[n]];
  1377. modify_index(tid, ip, le32_to_cpu(ldtentry->index),
  1378. rbn, n, &mp, &lblock);
  1379. }
  1380. if (mp)
  1381. release_metapage(mp);
  1382. }
  1383. /*
  1384. * the skipped index was on the left page,
  1385. */
  1386. if (skip <= off) {
  1387. /* insert the new entry in the split page */
  1388. dtInsertEntry(sp, skip, split->key, split->data, &sdtlck);
  1389. /* linelock stbl of split page */
  1390. if (sdtlck->index >= sdtlck->maxcnt)
  1391. sdtlck = (struct dt_lock *) txLinelock(sdtlck);
  1392. slv = & sdtlck->lv[sdtlck->index];
  1393. n = skip >> L2DTSLOTSIZE;
  1394. slv->offset = sp->header.stblindex + n;
  1395. slv->length =
  1396. ((sp->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1;
  1397. sdtlck->index++;
  1398. }
  1399. /*
  1400. * the skipped index was on the right page,
  1401. */
  1402. else {
  1403. /* adjust the skip index to reflect the new position */
  1404. skip -= nxt;
  1405. /* insert the new entry in the right page */
  1406. dtInsertEntry(rp, skip, split->key, split->data, &rdtlck);
  1407. }
  1408. out:
  1409. *rmpp = rmp;
  1410. *rpxdp = *pxd;
  1411. return rc;
  1412. }
  1413. /*
  1414. * dtExtendPage()
  1415. *
  1416. * function: extend 1st/only directory leaf page
  1417. *
  1418. * parameter:
  1419. *
  1420. * return: 0 - success;
  1421. * errno - failure;
  1422. * return extended page pinned;
  1423. */
  1424. static int dtExtendPage(tid_t tid,
  1425. struct inode *ip, struct dtsplit * split, struct btstack * btstack)
  1426. {
  1427. struct super_block *sb = ip->i_sb;
  1428. int rc;
  1429. struct metapage *smp, *pmp, *mp;
  1430. dtpage_t *sp, *pp;
  1431. struct pxdlist *pxdlist;
  1432. pxd_t *pxd, *tpxd;
  1433. int xlen, xsize;
  1434. int newstblindex, newstblsize;
  1435. int oldstblindex, oldstblsize;
  1436. int fsi, last;
  1437. struct dtslot *f;
  1438. struct btframe *parent;
  1439. int n;
  1440. struct dt_lock *dtlck;
  1441. s64 xaddr, txaddr;
  1442. struct tlock *tlck;
  1443. struct pxd_lock *pxdlock;
  1444. struct lv *lv;
  1445. uint type;
  1446. struct ldtentry *ldtentry;
  1447. u8 *stbl;
  1448. /* get page to extend */
  1449. smp = split->mp;
  1450. sp = DT_PAGE(ip, smp);
  1451. /* get parent/root page */
  1452. parent = BT_POP(btstack);
  1453. DT_GETPAGE(ip, parent->bn, pmp, PSIZE, pp, rc);
  1454. if (rc)
  1455. return (rc);
  1456. /*
  1457. * extend the extent
  1458. */
  1459. pxdlist = split->pxdlist;
  1460. pxd = &pxdlist->pxd[pxdlist->npxd];
  1461. pxdlist->npxd++;
  1462. xaddr = addressPXD(pxd);
  1463. tpxd = &sp->header.self;
  1464. txaddr = addressPXD(tpxd);
  1465. /* in-place extension */
  1466. if (xaddr == txaddr) {
  1467. type = tlckEXTEND;
  1468. }
  1469. /* relocation */
  1470. else {
  1471. type = tlckNEW;
  1472. /* save moved extent descriptor for later free */
  1473. tlck = txMaplock(tid, ip, tlckDTREE | tlckRELOCATE);
  1474. pxdlock = (struct pxd_lock *) & tlck->lock;
  1475. pxdlock->flag = mlckFREEPXD;
  1476. pxdlock->pxd = sp->header.self;
  1477. pxdlock->index = 1;
  1478. /*
  1479. * Update directory index table to reflect new page address
  1480. */
  1481. if (DO_INDEX(ip)) {
  1482. s64 lblock;
  1483. mp = NULL;
  1484. stbl = DT_GETSTBL(sp);
  1485. for (n = 0; n < sp->header.nextindex; n++) {
  1486. ldtentry =
  1487. (struct ldtentry *) & sp->slot[stbl[n]];
  1488. modify_index(tid, ip,
  1489. le32_to_cpu(ldtentry->index),
  1490. xaddr, n, &mp, &lblock);
  1491. }
  1492. if (mp)
  1493. release_metapage(mp);
  1494. }
  1495. }
  1496. /*
  1497. * extend the page
  1498. */
  1499. sp->header.self = *pxd;
  1500. jfs_info("dtExtendPage: ip:0x%p smp:0x%p sp:0x%p", ip, smp, sp);
  1501. BT_MARK_DIRTY(smp, ip);
  1502. /*
  1503. * acquire a transaction lock on the extended/leaf page
  1504. */
  1505. tlck = txLock(tid, ip, smp, tlckDTREE | type);
  1506. dtlck = (struct dt_lock *) & tlck->lock;
  1507. lv = & dtlck->lv[0];
  1508. /* update buffer extent descriptor of extended page */
  1509. xlen = lengthPXD(pxd);
  1510. xsize = xlen << JFS_SBI(sb)->l2bsize;
  1511. #ifdef _STILL_TO_PORT
  1512. bmSetXD(smp, xaddr, xsize);
  1513. #endif /* _STILL_TO_PORT */
  1514. /*
  1515. * copy old stbl to new stbl at start of extended area
  1516. */
  1517. oldstblindex = sp->header.stblindex;
  1518. oldstblsize = (sp->header.maxslot + 31) >> L2DTSLOTSIZE;
  1519. newstblindex = sp->header.maxslot;
  1520. n = xsize >> L2DTSLOTSIZE;
  1521. newstblsize = (n + 31) >> L2DTSLOTSIZE;
  1522. memcpy(&sp->slot[newstblindex], &sp->slot[oldstblindex],
  1523. sp->header.nextindex);
  1524. /*
  1525. * in-line extension: linelock old area of extended page
  1526. */
  1527. if (type == tlckEXTEND) {
  1528. /* linelock header */
  1529. lv->offset = 0;
  1530. lv->length = 1;
  1531. dtlck->index++;
  1532. lv++;
  1533. /* linelock new stbl of extended page */
  1534. lv->offset = newstblindex;
  1535. lv->length = newstblsize;
  1536. }
  1537. /*
  1538. * relocation: linelock whole relocated area
  1539. */
  1540. else {
  1541. lv->offset = 0;
  1542. lv->length = sp->header.maxslot + newstblsize;
  1543. }
  1544. dtlck->index++;
  1545. sp->header.maxslot = n;
  1546. sp->header.stblindex = newstblindex;
  1547. /* sp->header.nextindex remains the same */
  1548. /*
  1549. * add old stbl region at head of freelist
  1550. */
  1551. fsi = oldstblindex;
  1552. f = &sp->slot[fsi];
  1553. last = sp->header.freelist;
  1554. for (n = 0; n < oldstblsize; n++, fsi++, f++) {
  1555. f->next = last;
  1556. last = fsi;
  1557. }
  1558. sp->header.freelist = last;
  1559. sp->header.freecnt += oldstblsize;
  1560. /*
  1561. * append free region of newly extended area at tail of freelist
  1562. */
  1563. /* init free region of newly extended area */
  1564. fsi = n = newstblindex + newstblsize;
  1565. f = &sp->slot[fsi];
  1566. for (fsi++; fsi < sp->header.maxslot; f++, fsi++)
  1567. f->next = fsi;
  1568. f->next = -1;
  1569. /* append new free region at tail of old freelist */
  1570. fsi = sp->header.freelist;
  1571. if (fsi == -1)
  1572. sp->header.freelist = n;
  1573. else {
  1574. do {
  1575. f = &sp->slot[fsi];
  1576. fsi = f->next;
  1577. } while (fsi != -1);
  1578. f->next = n;
  1579. }
  1580. sp->header.freecnt += sp->header.maxslot - n;
  1581. /*
  1582. * insert the new entry
  1583. */
  1584. dtInsertEntry(sp, split->index, split->key, split->data, &dtlck);
  1585. BT_MARK_DIRTY(pmp, ip);
  1586. /*
  1587. * linelock any freeslots residing in old extent
  1588. */
  1589. if (type == tlckEXTEND) {
  1590. n = sp->header.maxslot >> 2;
  1591. if (sp->header.freelist < n)
  1592. dtLinelockFreelist(sp, n, &dtlck);
  1593. }
  1594. /*
  1595. * update parent entry on the parent/root page
  1596. */
  1597. /*
  1598. * acquire a transaction lock on the parent/root page
  1599. */
  1600. tlck = txLock(tid, ip, pmp, tlckDTREE | tlckENTRY);
  1601. dtlck = (struct dt_lock *) & tlck->lock;
  1602. lv = & dtlck->lv[dtlck->index];
  1603. /* linelock parent entry - 1st slot */
  1604. lv->offset = 1;
  1605. lv->length = 1;
  1606. dtlck->index++;
  1607. /* update the parent pxd for page extension */
  1608. tpxd = (pxd_t *) & pp->slot[1];
  1609. *tpxd = *pxd;
  1610. DT_PUTPAGE(pmp);
  1611. return 0;
  1612. }
  1613. /*
  1614. * dtSplitRoot()
  1615. *
  1616. * function:
  1617. * split the full root page into
  1618. * original/root/split page and new right page
  1619. * i.e., root remains fixed in tree anchor (inode) and
  1620. * the root is copied to a single new right child page
  1621. * since root page << non-root page, and
  1622. * the split root page contains a single entry for the
  1623. * new right child page.
  1624. *
  1625. * parameter:
  1626. *
  1627. * return: 0 - success;
  1628. * errno - failure;
  1629. * return new page pinned;
  1630. */
  1631. static int dtSplitRoot(tid_t tid,
  1632. struct inode *ip, struct dtsplit * split, struct metapage ** rmpp)
  1633. {
  1634. struct super_block *sb = ip->i_sb;
  1635. struct metapage *smp;
  1636. dtroot_t *sp;
  1637. struct metapage *rmp;
  1638. dtpage_t *rp;
  1639. s64 rbn;
  1640. int xlen;
  1641. int xsize;
  1642. struct dtslot *f;
  1643. s8 *stbl;
  1644. int fsi, stblsize, n;
  1645. struct idtentry *s;
  1646. pxd_t *ppxd;
  1647. struct pxdlist *pxdlist;
  1648. pxd_t *pxd;
  1649. struct dt_lock *dtlck;
  1650. struct tlock *tlck;
  1651. struct lv *lv;
  1652. /* get split root page */
  1653. smp = split->mp;
  1654. sp = &JFS_IP(ip)->i_dtroot;
  1655. /*
  1656. * allocate/initialize a single (right) child page
  1657. *
  1658. * N.B. at first split, a one (or two) block to fit new entry
  1659. * is allocated; at subsequent split, a full page is allocated;
  1660. */
  1661. pxdlist = split->pxdlist;
  1662. pxd = &pxdlist->pxd[pxdlist->npxd];
  1663. pxdlist->npxd++;
  1664. rbn = addressPXD(pxd);
  1665. xlen = lengthPXD(pxd);
  1666. xsize = xlen << JFS_SBI(sb)->l2bsize;
  1667. rmp = get_metapage(ip, rbn, xsize, 1);
  1668. if (!rmp)
  1669. return -EIO;
  1670. rp = rmp->data;
  1671. /* Allocate blocks to quota. */
  1672. if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) {
  1673. release_metapage(rmp);
  1674. return -EDQUOT;
  1675. }
  1676. BT_MARK_DIRTY(rmp, ip);
  1677. /*
  1678. * acquire a transaction lock on the new right page
  1679. */
  1680. tlck = txLock(tid, ip, rmp, tlckDTREE | tlckNEW);
  1681. dtlck = (struct dt_lock *) & tlck->lock;
  1682. rp->header.flag =
  1683. (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
  1684. rp->header.self = *pxd;
  1685. /* initialize sibling pointers */
  1686. rp->header.next = 0;
  1687. rp->header.prev = 0;
  1688. /*
  1689. * move in-line root page into new right page extent
  1690. */
  1691. /* linelock header + copied entries + new stbl (1st slot) in new page */
  1692. ASSERT(dtlck->index == 0);
  1693. lv = & dtlck->lv[0];
  1694. lv->offset = 0;
  1695. lv->length = 10; /* 1 + 8 + 1 */
  1696. dtlck->index++;
  1697. n = xsize >> L2DTSLOTSIZE;
  1698. rp->header.maxslot = n;
  1699. stblsize = (n + 31) >> L2DTSLOTSIZE;
  1700. /* copy old stbl to new stbl at start of extended area */
  1701. rp->header.stblindex = DTROOTMAXSLOT;
  1702. stbl = (s8 *) & rp->slot[DTROOTMAXSLOT];
  1703. memcpy(stbl, sp->header.stbl, sp->header.nextindex);
  1704. rp->header.nextindex = sp->header.nextindex;
  1705. /* copy old data area to start of new data area */
  1706. memcpy(&rp->slot[1], &sp->slot[1], IDATASIZE);
  1707. /*
  1708. * append free region of newly extended area at tail of freelist
  1709. */
  1710. /* init free region of newly extended area */
  1711. fsi = n = DTROOTMAXSLOT + stblsize;
  1712. f = &rp->slot[fsi];
  1713. for (fsi++; fsi < rp->header.maxslot; f++, fsi++)
  1714. f->next = fsi;
  1715. f->next = -1;
  1716. /* append new free region at tail of old freelist */
  1717. fsi = sp->header.freelist;
  1718. if (fsi == -1)
  1719. rp->header.freelist = n;
  1720. else {
  1721. rp->header.freelist = fsi;
  1722. do {
  1723. f = &rp->slot[fsi];
  1724. fsi = f->next;
  1725. } while (fsi != -1);
  1726. f->next = n;
  1727. }
  1728. rp->header.freecnt = sp->header.freecnt + rp->header.maxslot - n;
  1729. /*
  1730. * Update directory index table for entries now in right page
  1731. */
  1732. if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) {
  1733. s64 lblock;
  1734. struct metapage *mp = NULL;
  1735. struct ldtentry *ldtentry;
  1736. stbl = DT_GETSTBL(rp);
  1737. for (n = 0; n < rp->header.nextindex; n++) {
  1738. ldtentry = (struct ldtentry *) & rp->slot[stbl[n]];
  1739. modify_index(tid, ip, le32_to_cpu(ldtentry->index),
  1740. rbn, n, &mp, &lblock);
  1741. }
  1742. if (mp)
  1743. release_metapage(mp);
  1744. }
  1745. /*
  1746. * insert the new entry into the new right/child page
  1747. * (skip index in the new right page will not change)
  1748. */
  1749. dtInsertEntry(rp, split->index, split->key, split->data, &dtlck);
  1750. /*
  1751. * reset parent/root page
  1752. *
  1753. * set the 1st entry offset to 0, which force the left-most key
  1754. * at any level of the tree to be less than any search key.
  1755. *
  1756. * The btree comparison code guarantees that the left-most key on any
  1757. * level of the tree is never used, so it doesn't need to be filled in.
  1758. */
  1759. BT_MARK_DIRTY(smp, ip);
  1760. /*
  1761. * acquire a transaction lock on the root page (in-memory inode)
  1762. */
  1763. tlck = txLock(tid, ip, smp, tlckDTREE | tlckNEW | tlckBTROOT);
  1764. dtlck = (struct dt_lock *) & tlck->lock;
  1765. /* linelock root */
  1766. ASSERT(dtlck->index == 0);
  1767. lv = & dtlck->lv[0];
  1768. lv->offset = 0;
  1769. lv->length = DTROOTMAXSLOT;
  1770. dtlck->index++;
  1771. /* update page header of root */
  1772. if (sp->header.flag & BT_LEAF) {
  1773. sp->header.flag &= ~BT_LEAF;
  1774. sp->header.flag |= BT_INTERNAL;
  1775. }
  1776. /* init the first entry */
  1777. s = (struct idtentry *) & sp->slot[DTENTRYSTART];
  1778. ppxd = (pxd_t *) s;
  1779. *ppxd = *pxd;
  1780. s->next = -1;
  1781. s->namlen = 0;
  1782. stbl = sp->header.stbl;
  1783. stbl[0] = DTENTRYSTART;
  1784. sp->header.nextindex = 1;
  1785. /* init freelist */
  1786. fsi = DTENTRYSTART + 1;
  1787. f = &sp->slot[fsi];
  1788. /* init free region of remaining area */
  1789. for (fsi++; fsi < DTROOTMAXSLOT; f++, fsi++)
  1790. f->next = fsi;
  1791. f->next = -1;
  1792. sp->header.freelist = DTENTRYSTART + 1;
  1793. sp->header.freecnt = DTROOTMAXSLOT - (DTENTRYSTART + 1);
  1794. *rmpp = rmp;
  1795. return 0;
  1796. }
  1797. /*
  1798. * dtDelete()
  1799. *
  1800. * function: delete the entry(s) referenced by a key.
  1801. *
  1802. * parameter:
  1803. *
  1804. * return:
  1805. */
  1806. int dtDelete(tid_t tid,
  1807. struct inode *ip, struct component_name * key, ino_t * ino, int flag)
  1808. {
  1809. int rc = 0;
  1810. s64 bn;
  1811. struct metapage *mp, *imp;
  1812. dtpage_t *p;
  1813. int index;
  1814. struct btstack btstack;
  1815. struct dt_lock *dtlck;
  1816. struct tlock *tlck;
  1817. struct lv *lv;
  1818. int i;
  1819. struct ldtentry *ldtentry;
  1820. u8 *stbl;
  1821. u32 table_index, next_index;
  1822. struct metapage *nmp;
  1823. dtpage_t *np;
  1824. /*
  1825. * search for the entry to delete:
  1826. *
  1827. * dtSearch() returns (leaf page pinned, index at which to delete).
  1828. */
  1829. if ((rc = dtSearch(ip, key, ino, &btstack, flag)))
  1830. return rc;
  1831. /* retrieve search result */
  1832. DT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  1833. /*
  1834. * We need to find put the index of the next entry into the
  1835. * directory index table in order to resume a readdir from this
  1836. * entry.
  1837. */
  1838. if (DO_INDEX(ip)) {
  1839. stbl = DT_GETSTBL(p);
  1840. ldtentry = (struct ldtentry *) & p->slot[stbl[index]];
  1841. table_index = le32_to_cpu(ldtentry->index);
  1842. if (index == (p->header.nextindex - 1)) {
  1843. /*
  1844. * Last entry in this leaf page
  1845. */
  1846. if ((p->header.flag & BT_ROOT)
  1847. || (p->header.next == 0))
  1848. next_index = -1;
  1849. else {
  1850. /* Read next leaf page */
  1851. DT_GETPAGE(ip, le64_to_cpu(p->header.next),
  1852. nmp, PSIZE, np, rc);
  1853. if (rc)
  1854. next_index = -1;
  1855. else {
  1856. stbl = DT_GETSTBL(np);
  1857. ldtentry =
  1858. (struct ldtentry *) & np->
  1859. slot[stbl[0]];
  1860. next_index =
  1861. le32_to_cpu(ldtentry->index);
  1862. DT_PUTPAGE(nmp);
  1863. }
  1864. }
  1865. } else {
  1866. ldtentry =
  1867. (struct ldtentry *) & p->slot[stbl[index + 1]];
  1868. next_index = le32_to_cpu(ldtentry->index);
  1869. }
  1870. free_index(tid, ip, table_index, next_index);
  1871. }
  1872. /*
  1873. * the leaf page becomes empty, delete the page
  1874. */
  1875. if (p->header.nextindex == 1) {
  1876. /* delete empty page */
  1877. rc = dtDeleteUp(tid, ip, mp, p, &btstack);
  1878. }
  1879. /*
  1880. * the leaf page has other entries remaining:
  1881. *
  1882. * delete the entry from the leaf page.
  1883. */
  1884. else {
  1885. BT_MARK_DIRTY(mp, ip);
  1886. /*
  1887. * acquire a transaction lock on the leaf page
  1888. */
  1889. tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY);
  1890. dtlck = (struct dt_lock *) & tlck->lock;
  1891. /*
  1892. * Do not assume that dtlck->index will be zero. During a
  1893. * rename within a directory, this transaction may have
  1894. * modified this page already when adding the new entry.
  1895. */
  1896. /* linelock header */
  1897. if (dtlck->index >= dtlck->maxcnt)
  1898. dtlck = (struct dt_lock *) txLinelock(dtlck);
  1899. lv = & dtlck->lv[dtlck->index];
  1900. lv->offset = 0;
  1901. lv->length = 1;
  1902. dtlck->index++;
  1903. /* linelock stbl of non-root leaf page */
  1904. if (!(p->header.flag & BT_ROOT)) {
  1905. if (dtlck->index >= dtlck->maxcnt)
  1906. dtlck = (struct dt_lock *) txLinelock(dtlck);
  1907. lv = & dtlck->lv[dtlck->index];
  1908. i = index >> L2DTSLOTSIZE;
  1909. lv->offset = p->header.stblindex + i;
  1910. lv->length =
  1911. ((p->header.nextindex - 1) >> L2DTSLOTSIZE) -
  1912. i + 1;
  1913. dtlck->index++;
  1914. }
  1915. /* free the leaf entry */
  1916. dtDeleteEntry(p, index, &dtlck);
  1917. /*
  1918. * Update directory index table for entries moved in stbl
  1919. */
  1920. if (DO_INDEX(ip) && index < p->header.nextindex) {
  1921. s64 lblock;
  1922. imp = NULL;
  1923. stbl = DT_GETSTBL(p);
  1924. for (i = index; i < p->header.nextindex; i++) {
  1925. ldtentry =
  1926. (struct ldtentry *) & p->slot[stbl[i]];
  1927. modify_index(tid, ip,
  1928. le32_to_cpu(ldtentry->index),
  1929. bn, i, &imp, &lblock);
  1930. }
  1931. if (imp)
  1932. release_metapage(imp);
  1933. }
  1934. DT_PUTPAGE(mp);
  1935. }
  1936. return rc;
  1937. }
  1938. /*
  1939. * dtDeleteUp()
  1940. *
  1941. * function:
  1942. * free empty pages as propagating deletion up the tree
  1943. *
  1944. * parameter:
  1945. *
  1946. * return:
  1947. */
  1948. static int dtDeleteUp(tid_t tid, struct inode *ip,
  1949. struct metapage * fmp, dtpage_t * fp, struct btstack * btstack)
  1950. {
  1951. int rc = 0;
  1952. struct metapage *mp;
  1953. dtpage_t *p;
  1954. int index, nextindex;
  1955. int xlen;
  1956. struct btframe *parent;
  1957. struct dt_lock *dtlck;
  1958. struct tlock *tlck;
  1959. struct lv *lv;
  1960. struct pxd_lock *pxdlock;
  1961. int i;
  1962. /*
  1963. * keep the root leaf page which has become empty
  1964. */
  1965. if (BT_IS_ROOT(fmp)) {
  1966. /*
  1967. * reset the root
  1968. *
  1969. * dtInitRoot() acquires txlock on the root
  1970. */
  1971. dtInitRoot(tid, ip, PARENT(ip));
  1972. DT_PUTPAGE(fmp);
  1973. return 0;
  1974. }
  1975. /*
  1976. * free the non-root leaf page
  1977. */
  1978. /*
  1979. * acquire a transaction lock on the page
  1980. *
  1981. * write FREEXTENT|NOREDOPAGE log record
  1982. * N.B. linelock is overlaid as freed extent descriptor, and
  1983. * the buffer page is freed;
  1984. */
  1985. tlck = txMaplock(tid, ip, tlckDTREE | tlckFREE);
  1986. pxdlock = (struct pxd_lock *) & tlck->lock;
  1987. pxdlock->flag = mlckFREEPXD;
  1988. pxdlock->pxd = fp->header.self;
  1989. pxdlock->index = 1;
  1990. /* update sibling pointers */
  1991. if ((rc = dtRelink(tid, ip, fp))) {
  1992. BT_PUTPAGE(fmp);
  1993. return rc;
  1994. }
  1995. xlen = lengthPXD(&fp->header.self);
  1996. /* Free quota allocation. */
  1997. DQUOT_FREE_BLOCK(ip, xlen);
  1998. /* free/invalidate its buffer page */
  1999. discard_metapage(fmp);
  2000. /*
  2001. * propagate page deletion up the directory tree
  2002. *
  2003. * If the delete from the parent page makes it empty,
  2004. * continue all the way up the tree.
  2005. * stop if the root page is reached (which is never deleted) or
  2006. * if the entry deletion does not empty the page.
  2007. */
  2008. while ((parent = BT_POP(btstack)) != NULL) {
  2009. /* pin the parent page <sp> */
  2010. DT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc);
  2011. if (rc)
  2012. return rc;
  2013. /*
  2014. * free the extent of the child page deleted
  2015. */
  2016. index = parent->index;
  2017. /*
  2018. * delete the entry for the child page from parent
  2019. */
  2020. nextindex = p->header.nextindex;
  2021. /*
  2022. * the parent has the single entry being deleted:
  2023. *
  2024. * free the parent page which has become empty.
  2025. */
  2026. if (nextindex == 1) {
  2027. /*
  2028. * keep the root internal page which has become empty
  2029. */
  2030. if (p->header.flag & BT_ROOT) {
  2031. /*
  2032. * reset the root
  2033. *
  2034. * dtInitRoot() acquires txlock on the root
  2035. */
  2036. dtInitRoot(tid, ip, PARENT(ip));
  2037. DT_PUTPAGE(mp);
  2038. return 0;
  2039. }
  2040. /*
  2041. * free the parent page
  2042. */
  2043. else {
  2044. /*
  2045. * acquire a transaction lock on the page
  2046. *
  2047. * write FREEXTENT|NOREDOPAGE log record
  2048. */
  2049. tlck =
  2050. txMaplock(tid, ip,
  2051. tlckDTREE | tlckFREE);
  2052. pxdlock = (struct pxd_lock *) & tlck->lock;
  2053. pxdlock->flag = mlckFREEPXD;
  2054. pxdlock->pxd = p->header.self;
  2055. pxdlock->index = 1;
  2056. /* update sibling pointers */
  2057. if ((rc = dtRelink(tid, ip, p))) {
  2058. DT_PUTPAGE(mp);
  2059. return rc;
  2060. }
  2061. xlen = lengthPXD(&p->header.self);
  2062. /* Free quota allocation */
  2063. DQUOT_FREE_BLOCK(ip, xlen);
  2064. /* free/invalidate its buffer page */
  2065. discard_metapage(mp);
  2066. /* propagate up */
  2067. continue;
  2068. }
  2069. }
  2070. /*
  2071. * the parent has other entries remaining:
  2072. *
  2073. * delete the router entry from the parent page.
  2074. */
  2075. BT_MARK_DIRTY(mp, ip);
  2076. /*
  2077. * acquire a transaction lock on the page
  2078. *
  2079. * action: router entry deletion
  2080. */
  2081. tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY);
  2082. dtlck = (struct dt_lock *) & tlck->lock;
  2083. /* linelock header */
  2084. if (dtlck->index >= dtlck->maxcnt)
  2085. dtlck = (struct dt_lock *) txLinelock(dtlck);
  2086. lv = & dtlck->lv[dtlck->index];
  2087. lv->offset = 0;
  2088. lv->length = 1;
  2089. dtlck->index++;
  2090. /* linelock stbl of non-root leaf page */
  2091. if (!(p->header.flag & BT_ROOT)) {
  2092. if (dtlck->index < dtlck->maxcnt)
  2093. lv++;
  2094. else {
  2095. dtlck = (struct dt_lock *) txLinelock(dtlck);
  2096. lv = & dtlck->lv[0];
  2097. }
  2098. i = index >> L2DTSLOTSIZE;
  2099. lv->offset = p->header.stblindex + i;
  2100. lv->length =
  2101. ((p->header.nextindex - 1) >> L2DTSLOTSIZE) -
  2102. i + 1;
  2103. dtlck->index++;
  2104. }
  2105. /* free the router entry */
  2106. dtDeleteEntry(p, index, &dtlck);
  2107. /* reset key of new leftmost entry of level (for consistency) */
  2108. if (index == 0 &&
  2109. ((p->header.flag & BT_ROOT) || p->header.prev == 0))
  2110. dtTruncateEntry(p, 0, &dtlck);
  2111. /* unpin the parent page */
  2112. DT_PUTPAGE(mp);
  2113. /* exit propagation up */
  2114. break;
  2115. }
  2116. if (!DO_INDEX(ip))
  2117. ip->i_size -= PSIZE;
  2118. return 0;
  2119. }
  2120. #ifdef _NOTYET
  2121. /*
  2122. * NAME: dtRelocate()
  2123. *
  2124. * FUNCTION: relocate dtpage (internal or leaf) of directory;
  2125. * This function is mainly used by defragfs utility.
  2126. */
  2127. int dtRelocate(tid_t tid, struct inode *ip, s64 lmxaddr, pxd_t * opxd,
  2128. s64 nxaddr)
  2129. {
  2130. int rc = 0;
  2131. struct metapage *mp, *pmp, *lmp, *rmp;
  2132. dtpage_t *p, *pp, *rp = 0, *lp= 0;
  2133. s64 bn;
  2134. int index;
  2135. struct btstack btstack;
  2136. pxd_t *pxd;
  2137. s64 oxaddr, nextbn, prevbn;
  2138. int xlen, xsize;
  2139. struct tlock *tlck;
  2140. struct dt_lock *dtlck;
  2141. struct pxd_lock *pxdlock;
  2142. s8 *stbl;
  2143. struct lv *lv;
  2144. oxaddr = addressPXD(opxd);
  2145. xlen = lengthPXD(opxd);
  2146. jfs_info("dtRelocate: lmxaddr:%Ld xaddr:%Ld:%Ld xlen:%d",
  2147. (long long)lmxaddr, (long long)oxaddr, (long long)nxaddr,
  2148. xlen);
  2149. /*
  2150. * 1. get the internal parent dtpage covering
  2151. * router entry for the tartget page to be relocated;
  2152. */
  2153. rc = dtSearchNode(ip, lmxaddr, opxd, &btstack);
  2154. if (rc)
  2155. return rc;
  2156. /* retrieve search result */
  2157. DT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
  2158. jfs_info("dtRelocate: parent router entry validated.");
  2159. /*
  2160. * 2. relocate the target dtpage
  2161. */
  2162. /* read in the target page from src extent */
  2163. DT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc);
  2164. if (rc) {
  2165. /* release the pinned parent page */
  2166. DT_PUTPAGE(pmp);
  2167. return rc;
  2168. }
  2169. /*
  2170. * read in sibling pages if any to update sibling pointers;
  2171. */
  2172. rmp = NULL;
  2173. if (p->header.next) {
  2174. nextbn = le64_to_cpu(p->header.next);
  2175. DT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc);
  2176. if (rc) {
  2177. DT_PUTPAGE(mp);
  2178. DT_PUTPAGE(pmp);
  2179. return (rc);
  2180. }
  2181. }
  2182. lmp = NULL;
  2183. if (p->header.prev) {
  2184. prevbn = le64_to_cpu(p->header.prev);
  2185. DT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc);
  2186. if (rc) {
  2187. DT_PUTPAGE(mp);
  2188. DT_PUTPAGE(pmp);
  2189. if (rmp)
  2190. DT_PUTPAGE(rmp);
  2191. return (rc);
  2192. }
  2193. }
  2194. /* at this point, all xtpages to be updated are in memory */
  2195. /*
  2196. * update sibling pointers of sibling dtpages if any;
  2197. */
  2198. if (lmp) {
  2199. tlck = txLock(tid, ip, lmp, tlckDTREE | tlckRELINK);
  2200. dtlck = (struct dt_lock *) & tlck->lock;
  2201. /* linelock header */
  2202. ASSERT(dtlck->index == 0);
  2203. lv = & dtlck->lv[0];
  2204. lv->offset = 0;
  2205. lv->length = 1;
  2206. dtlck->index++;
  2207. lp->header.next = cpu_to_le64(nxaddr);
  2208. DT_PUTPAGE(lmp);
  2209. }
  2210. if (rmp) {
  2211. tlck = txLock(tid, ip, rmp, tlckDTREE | tlckRELINK);
  2212. dtlck = (struct dt_lock *) & tlck->lock;
  2213. /* linelock header */
  2214. ASSERT(dtlck->index == 0);
  2215. lv = & dtlck->lv[0];
  2216. lv->offset = 0;
  2217. lv->length = 1;
  2218. dtlck->index++;
  2219. rp->header.prev = cpu_to_le64(nxaddr);
  2220. DT_PUTPAGE(rmp);
  2221. }
  2222. /*
  2223. * update the target dtpage to be relocated
  2224. *
  2225. * write LOG_REDOPAGE of LOG_NEW type for dst page
  2226. * for the whole target page (logredo() will apply
  2227. * after image and update bmap for allocation of the
  2228. * dst extent), and update bmap for allocation of
  2229. * the dst extent;
  2230. */
  2231. tlck = txLock(tid, ip, mp, tlckDTREE | tlckNEW);
  2232. dtlck = (struct dt_lock *) & tlck->lock;
  2233. /* linelock header */
  2234. ASSERT(dtlck->index == 0);
  2235. lv = & dtlck->lv[0];
  2236. /* update the self address in the dtpage header */
  2237. pxd = &p->header.self;
  2238. PXDaddress(pxd, nxaddr);
  2239. /* the dst page is the same as the src page, i.e.,
  2240. * linelock for afterimage of the whole page;
  2241. */
  2242. lv->offset = 0;
  2243. lv->length = p->header.maxslot;
  2244. dtlck->index++;
  2245. /* update the buffer extent descriptor of the dtpage */
  2246. xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize;
  2247. #ifdef _STILL_TO_PORT
  2248. bmSetXD(mp, nxaddr, xsize);
  2249. #endif /* _STILL_TO_PORT */
  2250. /* unpin the relocated page */
  2251. DT_PUTPAGE(mp);
  2252. jfs_info("dtRelocate: target dtpage relocated.");
  2253. /* the moved extent is dtpage, then a LOG_NOREDOPAGE log rec
  2254. * needs to be written (in logredo(), the LOG_NOREDOPAGE log rec
  2255. * will also force a bmap update ).
  2256. */
  2257. /*
  2258. * 3. acquire maplock for the source extent to be freed;
  2259. */
  2260. /* for dtpage relocation, write a LOG_NOREDOPAGE record
  2261. * for the source dtpage (logredo() will init NoRedoPage
  2262. * filter and will also update bmap for free of the source
  2263. * dtpage), and upadte bmap for free of the source dtpage;
  2264. */
  2265. tlck = txMaplock(tid, ip, tlckDTREE | tlckFREE);
  2266. pxdlock = (struct pxd_lock *) & tlck->lock;
  2267. pxdlock->flag = mlckFREEPXD;
  2268. PXDaddress(&pxdlock->pxd, oxaddr);
  2269. PXDlength(&pxdlock->pxd, xlen);
  2270. pxdlock->index = 1;
  2271. /*
  2272. * 4. update the parent router entry for relocation;
  2273. *
  2274. * acquire tlck for the parent entry covering the target dtpage;
  2275. * write LOG_REDOPAGE to apply after image only;
  2276. */
  2277. jfs_info("dtRelocate: update parent router entry.");
  2278. tlck = txLock(tid, ip, pmp, tlckDTREE | tlckENTRY);
  2279. dtlck = (struct dt_lock *) & tlck->lock;
  2280. lv = & dtlck->lv[dtlck->index];
  2281. /* update the PXD with the new address */
  2282. stbl = DT_GETSTBL(pp);
  2283. pxd = (pxd_t *) & pp->slot[stbl[index]];
  2284. PXDaddress(pxd, nxaddr);
  2285. lv->offset = stbl[index];
  2286. lv->length = 1;
  2287. dtlck->index++;
  2288. /* unpin the parent dtpage */
  2289. DT_PUTPAGE(pmp);
  2290. return rc;
  2291. }
  2292. /*
  2293. * NAME: dtSearchNode()
  2294. *
  2295. * FUNCTION: Search for an dtpage containing a specified address
  2296. * This function is mainly used by defragfs utility.
  2297. *
  2298. * NOTE: Search result on stack, the found page is pinned at exit.
  2299. * The result page must be an internal dtpage.
  2300. * lmxaddr give the address of the left most page of the
  2301. * dtree level, in which the required dtpage resides.
  2302. */
  2303. static int dtSearchNode(struct inode *ip, s64 lmxaddr, pxd_t * kpxd,
  2304. struct btstack * btstack)
  2305. {
  2306. int rc = 0;
  2307. s64 bn;
  2308. struct metapage *mp;
  2309. dtpage_t *p;
  2310. int psize = 288; /* initial in-line directory */
  2311. s8 *stbl;
  2312. int i;
  2313. pxd_t *pxd;
  2314. struct btframe *btsp;
  2315. BT_CLR(btstack); /* reset stack */
  2316. /*
  2317. * descend tree to the level with specified leftmost page
  2318. *
  2319. * by convention, root bn = 0.
  2320. */
  2321. for (bn = 0;;) {
  2322. /* get/pin the page to search */
  2323. DT_GETPAGE(ip, bn, mp, psize, p, rc);
  2324. if (rc)
  2325. return rc;
  2326. /* does the xaddr of leftmost page of the levevl
  2327. * matches levevl search key ?
  2328. */
  2329. if (p->header.flag & BT_ROOT) {
  2330. if (lmxaddr == 0)
  2331. break;
  2332. } else if (addressPXD(&p->header.self) == lmxaddr)
  2333. break;
  2334. /*
  2335. * descend down to leftmost child page
  2336. */
  2337. if (p->header.flag & BT_LEAF) {
  2338. DT_PUTPAGE(mp);
  2339. return -ESTALE;
  2340. }
  2341. /* get the leftmost entry */
  2342. stbl = DT_GETSTBL(p);
  2343. pxd = (pxd_t *) & p->slot[stbl[0]];
  2344. /* get the child page block address */
  2345. bn = addressPXD(pxd);
  2346. psize = lengthPXD(pxd) << JFS_SBI(ip->i_sb)->l2bsize;
  2347. /* unpin the parent page */
  2348. DT_PUTPAGE(mp);
  2349. }
  2350. /*
  2351. * search each page at the current levevl
  2352. */
  2353. loop:
  2354. stbl = DT_GETSTBL(p);
  2355. for (i = 0; i < p->header.nextindex; i++) {
  2356. pxd = (pxd_t *) & p->slot[stbl[i]];
  2357. /* found the specified router entry */
  2358. if (addressPXD(pxd) == addressPXD(kpxd) &&
  2359. lengthPXD(pxd) == lengthPXD(kpxd)) {
  2360. btsp = btstack->top;
  2361. btsp->bn = bn;
  2362. btsp->index = i;
  2363. btsp->mp = mp;
  2364. return 0;
  2365. }
  2366. }
  2367. /* get the right sibling page if any */
  2368. if (p->header.next)
  2369. bn = le64_to_cpu(p->header.next);
  2370. else {
  2371. DT_PUTPAGE(mp);
  2372. return -ESTALE;
  2373. }
  2374. /* unpin current page */
  2375. DT_PUTPAGE(mp);
  2376. /* get the right sibling page */
  2377. DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  2378. if (rc)
  2379. return rc;
  2380. goto loop;
  2381. }
  2382. #endif /* _NOTYET */
  2383. /*
  2384. * dtRelink()
  2385. *
  2386. * function:
  2387. * link around a freed page.
  2388. *
  2389. * parameter:
  2390. * fp: page to be freed
  2391. *
  2392. * return:
  2393. */
  2394. static int dtRelink(tid_t tid, struct inode *ip, dtpage_t * p)
  2395. {
  2396. int rc;
  2397. struct metapage *mp;
  2398. s64 nextbn, prevbn;
  2399. struct tlock *tlck;
  2400. struct dt_lock *dtlck;
  2401. struct lv *lv;
  2402. nextbn = le64_to_cpu(p->header.next);
  2403. prevbn = le64_to_cpu(p->header.prev);
  2404. /* update prev pointer of the next page */
  2405. if (nextbn != 0) {
  2406. DT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
  2407. if (rc)
  2408. return rc;
  2409. BT_MARK_DIRTY(mp, ip);
  2410. /*
  2411. * acquire a transaction lock on the next page
  2412. *
  2413. * action: update prev pointer;
  2414. */
  2415. tlck = txLock(tid, ip, mp, tlckDTREE | tlckRELINK);
  2416. jfs_info("dtRelink nextbn: tlck = 0x%p, ip = 0x%p, mp=0x%p",
  2417. tlck, ip, mp);
  2418. dtlck = (struct dt_lock *) & tlck->lock;
  2419. /* linelock header */
  2420. if (dtlck->index >= dtlck->maxcnt)
  2421. dtlck = (struct dt_lock *) txLinelock(dtlck);
  2422. lv = & dtlck->lv[dtlck->index];
  2423. lv->offset = 0;
  2424. lv->length = 1;
  2425. dtlck->index++;
  2426. p->header.prev = cpu_to_le64(prevbn);
  2427. DT_PUTPAGE(mp);
  2428. }
  2429. /* update next pointer of the previous page */
  2430. if (prevbn != 0) {
  2431. DT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc);
  2432. if (rc)
  2433. return rc;
  2434. BT_MARK_DIRTY(mp, ip);
  2435. /*
  2436. * acquire a transaction lock on the prev page
  2437. *
  2438. * action: update next pointer;
  2439. */
  2440. tlck = txLock(tid, ip, mp, tlckDTREE | tlckRELINK);
  2441. jfs_info("dtRelink prevbn: tlck = 0x%p, ip = 0x%p, mp=0x%p",
  2442. tlck, ip, mp);
  2443. dtlck = (struct dt_lock *) & tlck->lock;
  2444. /* linelock header */
  2445. if (dtlck->index >= dtlck->maxcnt)
  2446. dtlck = (struct dt_lock *) txLinelock(dtlck);
  2447. lv = & dtlck->lv[dtlck->index];
  2448. lv->offset = 0;
  2449. lv->length = 1;
  2450. dtlck->index++;
  2451. p->header.next = cpu_to_le64(nextbn);
  2452. DT_PUTPAGE(mp);
  2453. }
  2454. return 0;
  2455. }
  2456. /*
  2457. * dtInitRoot()
  2458. *
  2459. * initialize directory root (inline in inode)
  2460. */
  2461. void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot)
  2462. {
  2463. struct jfs_inode_info *jfs_ip = JFS_IP(ip);
  2464. dtroot_t *p;
  2465. int fsi;
  2466. struct dtslot *f;
  2467. struct tlock *tlck;
  2468. struct dt_lock *dtlck;
  2469. struct lv *lv;
  2470. u16 xflag_save;
  2471. /*
  2472. * If this was previously an non-empty directory, we need to remove
  2473. * the old directory table.
  2474. */
  2475. if (DO_INDEX(ip)) {
  2476. if (!jfs_dirtable_inline(ip)) {
  2477. struct tblock *tblk = tid_to_tblock(tid);
  2478. /*
  2479. * We're playing games with the tid's xflag. If
  2480. * we're removing a regular file, the file's xtree
  2481. * is committed with COMMIT_PMAP, but we always
  2482. * commit the directories xtree with COMMIT_PWMAP.
  2483. */
  2484. xflag_save = tblk->xflag;
  2485. tblk->xflag = 0;
  2486. /*
  2487. * xtTruncate isn't guaranteed to fully truncate
  2488. * the xtree. The caller needs to check i_size
  2489. * after committing the transaction to see if
  2490. * additional truncation is needed. The
  2491. * COMMIT_Stale flag tells caller that we
  2492. * initiated the truncation.
  2493. */
  2494. xtTruncate(tid, ip, 0, COMMIT_PWMAP);
  2495. set_cflag(COMMIT_Stale, ip);
  2496. tblk->xflag = xflag_save;
  2497. } else
  2498. ip->i_size = 1;
  2499. jfs_ip->next_index = 2;
  2500. } else
  2501. ip->i_size = IDATASIZE;
  2502. /*
  2503. * acquire a transaction lock on the root
  2504. *
  2505. * action: directory initialization;
  2506. */
  2507. tlck = txLock(tid, ip, (struct metapage *) & jfs_ip->bxflag,
  2508. tlckDTREE | tlckENTRY | tlckBTROOT);
  2509. dtlck = (struct dt_lock *) & tlck->lock;
  2510. /* linelock root */
  2511. ASSERT(dtlck->index == 0);
  2512. lv = & dtlck->lv[0];
  2513. lv->offset = 0;
  2514. lv->length = DTROOTMAXSLOT;
  2515. dtlck->index++;
  2516. p = &jfs_ip->i_dtroot;
  2517. p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
  2518. p->header.nextindex = 0;
  2519. /* init freelist */
  2520. fsi = 1;
  2521. f = &p->slot[fsi];
  2522. /* init data area of root */
  2523. for (fsi++; fsi < DTROOTMAXSLOT; f++, fsi++)
  2524. f->next = fsi;
  2525. f->next = -1;
  2526. p->header.freelist = 1;
  2527. p->header.freecnt = 8;
  2528. /* init '..' entry */
  2529. p->header.idotdot = cpu_to_le32(idotdot);
  2530. return;
  2531. }
  2532. /*
  2533. * add_missing_indices()
  2534. *
  2535. * function: Fix dtree page in which one or more entries has an invalid index.
  2536. * fsck.jfs should really fix this, but it currently does not.
  2537. * Called from jfs_readdir when bad index is detected.
  2538. */
  2539. static void add_missing_indices(struct inode *inode, s64 bn)
  2540. {
  2541. struct ldtentry *d;
  2542. struct dt_lock *dtlck;
  2543. int i;
  2544. uint index;
  2545. struct lv *lv;
  2546. struct metapage *mp;
  2547. dtpage_t *p;
  2548. int rc;
  2549. s8 *stbl;
  2550. tid_t tid;
  2551. struct tlock *tlck;
  2552. tid = txBegin(inode->i_sb, 0);
  2553. DT_GETPAGE(inode, bn, mp, PSIZE, p, rc);
  2554. if (rc) {
  2555. printk(KERN_ERR "DT_GETPAGE failed!\n");
  2556. goto end;
  2557. }
  2558. BT_MARK_DIRTY(mp, inode);
  2559. ASSERT(p->header.flag & BT_LEAF);
  2560. tlck = txLock(tid, inode, mp, tlckDTREE | tlckENTRY);
  2561. if (BT_IS_ROOT(mp))
  2562. tlck->type |= tlckBTROOT;
  2563. dtlck = (struct dt_lock *) &tlck->lock;
  2564. stbl = DT_GETSTBL(p);
  2565. for (i = 0; i < p->header.nextindex; i++) {
  2566. d = (struct ldtentry *) &p->slot[stbl[i]];
  2567. index = le32_to_cpu(d->index);
  2568. if ((index < 2) || (index >= JFS_IP(inode)->next_index)) {
  2569. d->index = cpu_to_le32(add_index(tid, inode, bn, i));
  2570. if (dtlck->index >= dtlck->maxcnt)
  2571. dtlck = (struct dt_lock *) txLinelock(dtlck);
  2572. lv = &dtlck->lv[dtlck->index];
  2573. lv->offset = stbl[i];
  2574. lv->length = 1;
  2575. dtlck->index++;
  2576. }
  2577. }
  2578. DT_PUTPAGE(mp);
  2579. (void) txCommit(tid, 1, &inode, 0);
  2580. end:
  2581. txEnd(tid);
  2582. }
  2583. /*
  2584. * Buffer to hold directory entry info while traversing a dtree page
  2585. * before being fed to the filldir function
  2586. */
  2587. struct jfs_dirent {
  2588. loff_t position;
  2589. int ino;
  2590. u16 name_len;
  2591. char name[0];
  2592. };
  2593. /*
  2594. * function to determine next variable-sized jfs_dirent in buffer
  2595. */
  2596. static inline struct jfs_dirent *next_jfs_dirent(struct jfs_dirent *dirent)
  2597. {
  2598. return (struct jfs_dirent *)
  2599. ((char *)dirent +
  2600. ((sizeof (struct jfs_dirent) + dirent->name_len + 1 +
  2601. sizeof (loff_t) - 1) &
  2602. ~(sizeof (loff_t) - 1)));
  2603. }
  2604. /*
  2605. * jfs_readdir()
  2606. *
  2607. * function: read directory entries sequentially
  2608. * from the specified entry offset
  2609. *
  2610. * parameter:
  2611. *
  2612. * return: offset = (pn, index) of start entry
  2613. * of next jfs_readdir()/dtRead()
  2614. */
  2615. int jfs_readdir(struct file *filp, void *dirent, filldir_t filldir)
  2616. {
  2617. struct inode *ip = filp->f_path.dentry->d_inode;
  2618. struct nls_table *codepage = JFS_SBI(ip->i_sb)->nls_tab;
  2619. int rc = 0;
  2620. loff_t dtpos; /* legacy OS/2 style position */
  2621. struct dtoffset {
  2622. s16 pn;
  2623. s16 index;
  2624. s32 unused;
  2625. } *dtoffset = (struct dtoffset *) &dtpos;
  2626. s64 bn;
  2627. struct metapage *mp;
  2628. dtpage_t *p;
  2629. int index;
  2630. s8 *stbl;
  2631. struct btstack btstack;
  2632. int i, next;
  2633. struct ldtentry *d;
  2634. struct dtslot *t;
  2635. int d_namleft, len, outlen;
  2636. unsigned long dirent_buf;
  2637. char *name_ptr;
  2638. u32 dir_index;
  2639. int do_index = 0;
  2640. uint loop_count = 0;
  2641. struct jfs_dirent *jfs_dirent;
  2642. int jfs_dirents;
  2643. int overflow, fix_page, page_fixed = 0;
  2644. static int unique_pos = 2; /* If we can't fix broken index */
  2645. if (filp->f_pos == DIREND)
  2646. return 0;
  2647. if (DO_INDEX(ip)) {
  2648. /*
  2649. * persistent index is stored in directory entries.
  2650. * Special cases: 0 = .
  2651. * 1 = ..
  2652. * -1 = End of directory
  2653. */
  2654. do_index = 1;
  2655. dir_index = (u32) filp->f_pos;
  2656. if (dir_index > 1) {
  2657. struct dir_table_slot dirtab_slot;
  2658. if (dtEmpty(ip) ||
  2659. (dir_index >= JFS_IP(ip)->next_index)) {
  2660. /* Stale position. Directory has shrunk */
  2661. filp->f_pos = DIREND;
  2662. return 0;
  2663. }
  2664. repeat:
  2665. rc = read_index(ip, dir_index, &dirtab_slot);
  2666. if (rc) {
  2667. filp->f_pos = DIREND;
  2668. return rc;
  2669. }
  2670. if (dirtab_slot.flag == DIR_INDEX_FREE) {
  2671. if (loop_count++ > JFS_IP(ip)->next_index) {
  2672. jfs_err("jfs_readdir detected "
  2673. "infinite loop!");
  2674. filp->f_pos = DIREND;
  2675. return 0;
  2676. }
  2677. dir_index = le32_to_cpu(dirtab_slot.addr2);
  2678. if (dir_index == -1) {
  2679. filp->f_pos = DIREND;
  2680. return 0;
  2681. }
  2682. goto repeat;
  2683. }
  2684. bn = addressDTS(&dirtab_slot);
  2685. index = dirtab_slot.slot;
  2686. DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  2687. if (rc) {
  2688. filp->f_pos = DIREND;
  2689. return 0;
  2690. }
  2691. if (p->header.flag & BT_INTERNAL) {
  2692. jfs_err("jfs_readdir: bad index table");
  2693. DT_PUTPAGE(mp);
  2694. filp->f_pos = -1;
  2695. return 0;
  2696. }
  2697. } else {
  2698. if (dir_index == 0) {
  2699. /*
  2700. * self "."
  2701. */
  2702. filp->f_pos = 0;
  2703. if (filldir(dirent, ".", 1, 0, ip->i_ino,
  2704. DT_DIR))
  2705. return 0;
  2706. }
  2707. /*
  2708. * parent ".."
  2709. */
  2710. filp->f_pos = 1;
  2711. if (filldir(dirent, "..", 2, 1, PARENT(ip), DT_DIR))
  2712. return 0;
  2713. /*
  2714. * Find first entry of left-most leaf
  2715. */
  2716. if (dtEmpty(ip)) {
  2717. filp->f_pos = DIREND;
  2718. return 0;
  2719. }
  2720. if ((rc = dtReadFirst(ip, &btstack)))
  2721. return rc;
  2722. DT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  2723. }
  2724. } else {
  2725. /*
  2726. * Legacy filesystem - OS/2 & Linux JFS < 0.3.6
  2727. *
  2728. * pn = index = 0: First entry "."
  2729. * pn = 0; index = 1: Second entry ".."
  2730. * pn > 0: Real entries, pn=1 -> leftmost page
  2731. * pn = index = -1: No more entries
  2732. */
  2733. dtpos = filp->f_pos;
  2734. if (dtpos == 0) {
  2735. /* build "." entry */
  2736. if (filldir(dirent, ".", 1, filp->f_pos, ip->i_ino,
  2737. DT_DIR))
  2738. return 0;
  2739. dtoffset->index = 1;
  2740. filp->f_pos = dtpos;
  2741. }
  2742. if (dtoffset->pn == 0) {
  2743. if (dtoffset->index == 1) {
  2744. /* build ".." entry */
  2745. if (filldir(dirent, "..", 2, filp->f_pos,
  2746. PARENT(ip), DT_DIR))
  2747. return 0;
  2748. } else {
  2749. jfs_err("jfs_readdir called with "
  2750. "invalid offset!");
  2751. }
  2752. dtoffset->pn = 1;
  2753. dtoffset->index = 0;
  2754. filp->f_pos = dtpos;
  2755. }
  2756. if (dtEmpty(ip)) {
  2757. filp->f_pos = DIREND;
  2758. return 0;
  2759. }
  2760. if ((rc = dtReadNext(ip, &filp->f_pos, &btstack))) {
  2761. jfs_err("jfs_readdir: unexpected rc = %d "
  2762. "from dtReadNext", rc);
  2763. filp->f_pos = DIREND;
  2764. return 0;
  2765. }
  2766. /* get start leaf page and index */
  2767. DT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  2768. /* offset beyond directory eof ? */
  2769. if (bn < 0) {
  2770. filp->f_pos = DIREND;
  2771. return 0;
  2772. }
  2773. }
  2774. dirent_buf = __get_free_page(GFP_KERNEL);
  2775. if (dirent_buf == 0) {
  2776. DT_PUTPAGE(mp);
  2777. jfs_warn("jfs_readdir: __get_free_page failed!");
  2778. filp->f_pos = DIREND;
  2779. return -ENOMEM;
  2780. }
  2781. while (1) {
  2782. jfs_dirent = (struct jfs_dirent *) dirent_buf;
  2783. jfs_dirents = 0;
  2784. overflow = fix_page = 0;
  2785. stbl = DT_GETSTBL(p);
  2786. for (i = index; i < p->header.nextindex; i++) {
  2787. d = (struct ldtentry *) & p->slot[stbl[i]];
  2788. if (((long) jfs_dirent + d->namlen + 1) >
  2789. (dirent_buf + PAGE_SIZE)) {
  2790. /* DBCS codepages could overrun dirent_buf */
  2791. index = i;
  2792. overflow = 1;
  2793. break;
  2794. }
  2795. d_namleft = d->namlen;
  2796. name_ptr = jfs_dirent->name;
  2797. jfs_dirent->ino = le32_to_cpu(d->inumber);
  2798. if (do_index) {
  2799. len = min(d_namleft, DTLHDRDATALEN);
  2800. jfs_dirent->position = le32_to_cpu(d->index);
  2801. /*
  2802. * d->index should always be valid, but it
  2803. * isn't. fsck.jfs doesn't create the
  2804. * directory index for the lost+found
  2805. * directory. Rather than let it go,
  2806. * we can try to fix it.
  2807. */
  2808. if ((jfs_dirent->position < 2) ||
  2809. (jfs_dirent->position >=
  2810. JFS_IP(ip)->next_index)) {
  2811. if (!page_fixed && !isReadOnly(ip)) {
  2812. fix_page = 1;
  2813. /*
  2814. * setting overflow and setting
  2815. * index to i will cause the
  2816. * same page to be processed
  2817. * again starting here
  2818. */
  2819. overflow = 1;
  2820. index = i;
  2821. break;
  2822. }
  2823. jfs_dirent->position = unique_pos++;
  2824. }
  2825. } else {
  2826. jfs_dirent->position = dtpos;
  2827. len = min(d_namleft, DTLHDRDATALEN_LEGACY);
  2828. }
  2829. /* copy the name of head/only segment */
  2830. outlen = jfs_strfromUCS_le(name_ptr, d->name, len,
  2831. codepage);
  2832. jfs_dirent->name_len = outlen;
  2833. /* copy name in the additional segment(s) */
  2834. next = d->next;
  2835. while (next >= 0) {
  2836. t = (struct dtslot *) & p->slot[next];
  2837. name_ptr += outlen;
  2838. d_namleft -= len;
  2839. /* Sanity Check */
  2840. if (d_namleft == 0) {
  2841. jfs_error(ip->i_sb,
  2842. "JFS:Dtree error: ino = "
  2843. "%ld, bn=%Ld, index = %d",
  2844. (long)ip->i_ino,
  2845. (long long)bn,
  2846. i);
  2847. goto skip_one;
  2848. }
  2849. len = min(d_namleft, DTSLOTDATALEN);
  2850. outlen = jfs_strfromUCS_le(name_ptr, t->name,
  2851. len, codepage);
  2852. jfs_dirent->name_len += outlen;
  2853. next = t->next;
  2854. }
  2855. jfs_dirents++;
  2856. jfs_dirent = next_jfs_dirent(jfs_dirent);
  2857. skip_one:
  2858. if (!do_index)
  2859. dtoffset->index++;
  2860. }
  2861. if (!overflow) {
  2862. /* Point to next leaf page */
  2863. if (p->header.flag & BT_ROOT)
  2864. bn = 0;
  2865. else {
  2866. bn = le64_to_cpu(p->header.next);
  2867. index = 0;
  2868. /* update offset (pn:index) for new page */
  2869. if (!do_index) {
  2870. dtoffset->pn++;
  2871. dtoffset->index = 0;
  2872. }
  2873. }
  2874. page_fixed = 0;
  2875. }
  2876. /* unpin previous leaf page */
  2877. DT_PUTPAGE(mp);
  2878. jfs_dirent = (struct jfs_dirent *) dirent_buf;
  2879. while (jfs_dirents--) {
  2880. filp->f_pos = jfs_dirent->position;
  2881. if (filldir(dirent, jfs_dirent->name,
  2882. jfs_dirent->name_len, filp->f_pos,
  2883. jfs_dirent->ino, DT_UNKNOWN))
  2884. goto out;
  2885. jfs_dirent = next_jfs_dirent(jfs_dirent);
  2886. }
  2887. if (fix_page) {
  2888. add_missing_indices(ip, bn);
  2889. page_fixed = 1;
  2890. }
  2891. if (!overflow && (bn == 0)) {
  2892. filp->f_pos = DIREND;
  2893. break;
  2894. }
  2895. DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  2896. if (rc) {
  2897. free_page(dirent_buf);
  2898. return rc;
  2899. }
  2900. }
  2901. out:
  2902. free_page(dirent_buf);
  2903. return rc;
  2904. }
  2905. /*
  2906. * dtReadFirst()
  2907. *
  2908. * function: get the leftmost page of the directory
  2909. */
  2910. static int dtReadFirst(struct inode *ip, struct btstack * btstack)
  2911. {
  2912. int rc = 0;
  2913. s64 bn;
  2914. int psize = 288; /* initial in-line directory */
  2915. struct metapage *mp;
  2916. dtpage_t *p;
  2917. s8 *stbl;
  2918. struct btframe *btsp;
  2919. pxd_t *xd;
  2920. BT_CLR(btstack); /* reset stack */
  2921. /*
  2922. * descend leftmost path of the tree
  2923. *
  2924. * by convention, root bn = 0.
  2925. */
  2926. for (bn = 0;;) {
  2927. DT_GETPAGE(ip, bn, mp, psize, p, rc);
  2928. if (rc)
  2929. return rc;
  2930. /*
  2931. * leftmost leaf page
  2932. */
  2933. if (p->header.flag & BT_LEAF) {
  2934. /* return leftmost entry */
  2935. btsp = btstack->top;
  2936. btsp->bn = bn;
  2937. btsp->index = 0;
  2938. btsp->mp = mp;
  2939. return 0;
  2940. }
  2941. /*
  2942. * descend down to leftmost child page
  2943. */
  2944. if (BT_STACK_FULL(btstack)) {
  2945. DT_PUTPAGE(mp);
  2946. jfs_error(ip->i_sb, "dtReadFirst: btstack overrun");
  2947. BT_STACK_DUMP(btstack);
  2948. return -EIO;
  2949. }
  2950. /* push (bn, index) of the parent page/entry */
  2951. BT_PUSH(btstack, bn, 0);
  2952. /* get the leftmost entry */
  2953. stbl = DT_GETSTBL(p);
  2954. xd = (pxd_t *) & p->slot[stbl[0]];
  2955. /* get the child page block address */
  2956. bn = addressPXD(xd);
  2957. psize = lengthPXD(xd) << JFS_SBI(ip->i_sb)->l2bsize;
  2958. /* unpin the parent page */
  2959. DT_PUTPAGE(mp);
  2960. }
  2961. }
  2962. /*
  2963. * dtReadNext()
  2964. *
  2965. * function: get the page of the specified offset (pn:index)
  2966. *
  2967. * return: if (offset > eof), bn = -1;
  2968. *
  2969. * note: if index > nextindex of the target leaf page,
  2970. * start with 1st entry of next leaf page;
  2971. */
  2972. static int dtReadNext(struct inode *ip, loff_t * offset,
  2973. struct btstack * btstack)
  2974. {
  2975. int rc = 0;
  2976. struct dtoffset {
  2977. s16 pn;
  2978. s16 index;
  2979. s32 unused;
  2980. } *dtoffset = (struct dtoffset *) offset;
  2981. s64 bn;
  2982. struct metapage *mp;
  2983. dtpage_t *p;
  2984. int index;
  2985. int pn;
  2986. s8 *stbl;
  2987. struct btframe *btsp, *parent;
  2988. pxd_t *xd;
  2989. /*
  2990. * get leftmost leaf page pinned
  2991. */
  2992. if ((rc = dtReadFirst(ip, btstack)))
  2993. return rc;
  2994. /* get leaf page */
  2995. DT_GETSEARCH(ip, btstack->top, bn, mp, p, index);
  2996. /* get the start offset (pn:index) */
  2997. pn = dtoffset->pn - 1; /* Now pn = 0 represents leftmost leaf */
  2998. index = dtoffset->index;
  2999. /* start at leftmost page ? */
  3000. if (pn == 0) {
  3001. /* offset beyond eof ? */
  3002. if (index < p->header.nextindex)
  3003. goto out;
  3004. if (p->header.flag & BT_ROOT) {
  3005. bn = -1;
  3006. goto out;
  3007. }
  3008. /* start with 1st entry of next leaf page */
  3009. dtoffset->pn++;
  3010. dtoffset->index = index = 0;
  3011. goto a;
  3012. }
  3013. /* start at non-leftmost page: scan parent pages for large pn */
  3014. if (p->header.flag & BT_ROOT) {
  3015. bn = -1;
  3016. goto out;
  3017. }
  3018. /* start after next leaf page ? */
  3019. if (pn > 1)
  3020. goto b;
  3021. /* get leaf page pn = 1 */
  3022. a:
  3023. bn = le64_to_cpu(p->header.next);
  3024. /* unpin leaf page */
  3025. DT_PUTPAGE(mp);
  3026. /* offset beyond eof ? */
  3027. if (bn == 0) {
  3028. bn = -1;
  3029. goto out;
  3030. }
  3031. goto c;
  3032. /*
  3033. * scan last internal page level to get target leaf page
  3034. */
  3035. b:
  3036. /* unpin leftmost leaf page */
  3037. DT_PUTPAGE(mp);
  3038. /* get left most parent page */
  3039. btsp = btstack->top;
  3040. parent = btsp - 1;
  3041. bn = parent->bn;
  3042. DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  3043. if (rc)
  3044. return rc;
  3045. /* scan parent pages at last internal page level */
  3046. while (pn >= p->header.nextindex) {
  3047. pn -= p->header.nextindex;
  3048. /* get next parent page address */
  3049. bn = le64_to_cpu(p->header.next);
  3050. /* unpin current parent page */
  3051. DT_PUTPAGE(mp);
  3052. /* offset beyond eof ? */
  3053. if (bn == 0) {
  3054. bn = -1;
  3055. goto out;
  3056. }
  3057. /* get next parent page */
  3058. DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  3059. if (rc)
  3060. return rc;
  3061. /* update parent page stack frame */
  3062. parent->bn = bn;
  3063. }
  3064. /* get leaf page address */
  3065. stbl = DT_GETSTBL(p);
  3066. xd = (pxd_t *) & p->slot[stbl[pn]];
  3067. bn = addressPXD(xd);
  3068. /* unpin parent page */
  3069. DT_PUTPAGE(mp);
  3070. /*
  3071. * get target leaf page
  3072. */
  3073. c:
  3074. DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  3075. if (rc)
  3076. return rc;
  3077. /*
  3078. * leaf page has been completed:
  3079. * start with 1st entry of next leaf page
  3080. */
  3081. if (index >= p->header.nextindex) {
  3082. bn = le64_to_cpu(p->header.next);
  3083. /* unpin leaf page */
  3084. DT_PUTPAGE(mp);
  3085. /* offset beyond eof ? */
  3086. if (bn == 0) {
  3087. bn = -1;
  3088. goto out;
  3089. }
  3090. /* get next leaf page */
  3091. DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
  3092. if (rc)
  3093. return rc;
  3094. /* start with 1st entry of next leaf page */
  3095. dtoffset->pn++;
  3096. dtoffset->index = 0;
  3097. }
  3098. out:
  3099. /* return target leaf page pinned */
  3100. btsp = btstack->top;
  3101. btsp->bn = bn;
  3102. btsp->index = dtoffset->index;
  3103. btsp->mp = mp;
  3104. return 0;
  3105. }
  3106. /*
  3107. * dtCompare()
  3108. *
  3109. * function: compare search key with an internal entry
  3110. *
  3111. * return:
  3112. * < 0 if k is < record
  3113. * = 0 if k is = record
  3114. * > 0 if k is > record
  3115. */
  3116. static int dtCompare(struct component_name * key, /* search key */
  3117. dtpage_t * p, /* directory page */
  3118. int si)
  3119. { /* entry slot index */
  3120. wchar_t *kname;
  3121. __le16 *name;
  3122. int klen, namlen, len, rc;
  3123. struct idtentry *ih;
  3124. struct dtslot *t;
  3125. /*
  3126. * force the left-most key on internal pages, at any level of
  3127. * the tree, to be less than any search key.
  3128. * this obviates having to update the leftmost key on an internal
  3129. * page when the user inserts a new key in the tree smaller than
  3130. * anything that has been stored.
  3131. *
  3132. * (? if/when dtSearch() narrows down to 1st entry (index = 0),
  3133. * at any internal page at any level of the tree,
  3134. * it descends to child of the entry anyway -
  3135. * ? make the entry as min size dummy entry)
  3136. *
  3137. * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF))
  3138. * return (1);
  3139. */
  3140. kname = key->name;
  3141. klen = key->namlen;
  3142. ih = (struct idtentry *) & p->slot[si];
  3143. si = ih->next;
  3144. name = ih->name;
  3145. namlen = ih->namlen;
  3146. len = min(namlen, DTIHDRDATALEN);
  3147. /* compare with head/only segment */
  3148. len = min(klen, len);
  3149. if ((rc = UniStrncmp_le(kname, name, len)))
  3150. return rc;
  3151. klen -= len;
  3152. namlen -= len;
  3153. /* compare with additional segment(s) */
  3154. kname += len;
  3155. while (klen > 0 && namlen > 0) {
  3156. /* compare with next name segment */
  3157. t = (struct dtslot *) & p->slot[si];
  3158. len = min(namlen, DTSLOTDATALEN);
  3159. len = min(klen, len);
  3160. name = t->name;
  3161. if ((rc = UniStrncmp_le(kname, name, len)))
  3162. return rc;
  3163. klen -= len;
  3164. namlen -= len;
  3165. kname += len;
  3166. si = t->next;
  3167. }
  3168. return (klen - namlen);
  3169. }
  3170. /*
  3171. * ciCompare()
  3172. *
  3173. * function: compare search key with an (leaf/internal) entry
  3174. *
  3175. * return:
  3176. * < 0 if k is < record
  3177. * = 0 if k is = record
  3178. * > 0 if k is > record
  3179. */
  3180. static int ciCompare(struct component_name * key, /* search key */
  3181. dtpage_t * p, /* directory page */
  3182. int si, /* entry slot index */
  3183. int flag)
  3184. {
  3185. wchar_t *kname, x;
  3186. __le16 *name;
  3187. int klen, namlen, len, rc;
  3188. struct ldtentry *lh;
  3189. struct idtentry *ih;
  3190. struct dtslot *t;
  3191. int i;
  3192. /*
  3193. * force the left-most key on internal pages, at any level of
  3194. * the tree, to be less than any search key.
  3195. * this obviates having to update the leftmost key on an internal
  3196. * page when the user inserts a new key in the tree smaller than
  3197. * anything that has been stored.
  3198. *
  3199. * (? if/when dtSearch() narrows down to 1st entry (index = 0),
  3200. * at any internal page at any level of the tree,
  3201. * it descends to child of the entry anyway -
  3202. * ? make the entry as min size dummy entry)
  3203. *
  3204. * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF))
  3205. * return (1);
  3206. */
  3207. kname = key->name;
  3208. klen = key->namlen;
  3209. /*
  3210. * leaf page entry
  3211. */
  3212. if (p->header.flag & BT_LEAF) {
  3213. lh = (struct ldtentry *) & p->slot[si];
  3214. si = lh->next;
  3215. name = lh->name;
  3216. namlen = lh->namlen;
  3217. if (flag & JFS_DIR_INDEX)
  3218. len = min(namlen, DTLHDRDATALEN);
  3219. else
  3220. len = min(namlen, DTLHDRDATALEN_LEGACY);
  3221. }
  3222. /*
  3223. * internal page entry
  3224. */
  3225. else {
  3226. ih = (struct idtentry *) & p->slot[si];
  3227. si = ih->next;
  3228. name = ih->name;
  3229. namlen = ih->namlen;
  3230. len = min(namlen, DTIHDRDATALEN);
  3231. }
  3232. /* compare with head/only segment */
  3233. len = min(klen, len);
  3234. for (i = 0; i < len; i++, kname++, name++) {
  3235. /* only uppercase if case-insensitive support is on */
  3236. if ((flag & JFS_OS2) == JFS_OS2)
  3237. x = UniToupper(le16_to_cpu(*name));
  3238. else
  3239. x = le16_to_cpu(*name);
  3240. if ((rc = *kname - x))
  3241. return rc;
  3242. }
  3243. klen -= len;
  3244. namlen -= len;
  3245. /* compare with additional segment(s) */
  3246. while (klen > 0 && namlen > 0) {
  3247. /* compare with next name segment */
  3248. t = (struct dtslot *) & p->slot[si];
  3249. len = min(namlen, DTSLOTDATALEN);
  3250. len = min(klen, len);
  3251. name = t->name;
  3252. for (i = 0; i < len; i++, kname++, name++) {
  3253. /* only uppercase if case-insensitive support is on */
  3254. if ((flag & JFS_OS2) == JFS_OS2)
  3255. x = UniToupper(le16_to_cpu(*name));
  3256. else
  3257. x = le16_to_cpu(*name);
  3258. if ((rc = *kname - x))
  3259. return rc;
  3260. }
  3261. klen -= len;
  3262. namlen -= len;
  3263. si = t->next;
  3264. }
  3265. return (klen - namlen);
  3266. }
  3267. /*
  3268. * ciGetLeafPrefixKey()
  3269. *
  3270. * function: compute prefix of suffix compression
  3271. * from two adjacent leaf entries
  3272. * across page boundary
  3273. *
  3274. * return: non-zero on error
  3275. *
  3276. */
  3277. static int ciGetLeafPrefixKey(dtpage_t * lp, int li, dtpage_t * rp,
  3278. int ri, struct component_name * key, int flag)
  3279. {
  3280. int klen, namlen;
  3281. wchar_t *pl, *pr, *kname;
  3282. struct component_name lkey;
  3283. struct component_name rkey;
  3284. lkey.name = kmalloc((JFS_NAME_MAX + 1) * sizeof(wchar_t),
  3285. GFP_KERNEL);
  3286. if (lkey.name == NULL)
  3287. return -ENOMEM;
  3288. rkey.name = kmalloc((JFS_NAME_MAX + 1) * sizeof(wchar_t),
  3289. GFP_KERNEL);
  3290. if (rkey.name == NULL) {
  3291. kfree(lkey.name);
  3292. return -ENOMEM;
  3293. }
  3294. /* get left and right key */
  3295. dtGetKey(lp, li, &lkey, flag);
  3296. lkey.name[lkey.namlen] = 0;
  3297. if ((flag & JFS_OS2) == JFS_OS2)
  3298. ciToUpper(&lkey);
  3299. dtGetKey(rp, ri, &rkey, flag);
  3300. rkey.name[rkey.namlen] = 0;
  3301. if ((flag & JFS_OS2) == JFS_OS2)
  3302. ciToUpper(&rkey);
  3303. /* compute prefix */
  3304. klen = 0;
  3305. kname = key->name;
  3306. namlen = min(lkey.namlen, rkey.namlen);
  3307. for (pl = lkey.name, pr = rkey.name;
  3308. namlen; pl++, pr++, namlen--, klen++, kname++) {
  3309. *kname = *pr;
  3310. if (*pl != *pr) {
  3311. key->namlen = klen + 1;
  3312. goto free_names;
  3313. }
  3314. }
  3315. /* l->namlen <= r->namlen since l <= r */
  3316. if (lkey.namlen < rkey.namlen) {
  3317. *kname = *pr;
  3318. key->namlen = klen + 1;
  3319. } else /* l->namelen == r->namelen */
  3320. key->namlen = klen;
  3321. free_names:
  3322. kfree(lkey.name);
  3323. kfree(rkey.name);
  3324. return 0;
  3325. }
  3326. /*
  3327. * dtGetKey()
  3328. *
  3329. * function: get key of the entry
  3330. */
  3331. static void dtGetKey(dtpage_t * p, int i, /* entry index */
  3332. struct component_name * key, int flag)
  3333. {
  3334. int si;
  3335. s8 *stbl;
  3336. struct ldtentry *lh;
  3337. struct idtentry *ih;
  3338. struct dtslot *t;
  3339. int namlen, len;
  3340. wchar_t *kname;
  3341. __le16 *name;
  3342. /* get entry */
  3343. stbl = DT_GETSTBL(p);
  3344. si = stbl[i];
  3345. if (p->header.flag & BT_LEAF) {
  3346. lh = (struct ldtentry *) & p->slot[si];
  3347. si = lh->next;
  3348. namlen = lh->namlen;
  3349. name = lh->name;
  3350. if (flag & JFS_DIR_INDEX)
  3351. len = min(namlen, DTLHDRDATALEN);
  3352. else
  3353. len = min(namlen, DTLHDRDATALEN_LEGACY);
  3354. } else {
  3355. ih = (struct idtentry *) & p->slot[si];
  3356. si = ih->next;
  3357. namlen = ih->namlen;
  3358. name = ih->name;
  3359. len = min(namlen, DTIHDRDATALEN);
  3360. }
  3361. key->namlen = namlen;
  3362. kname = key->name;
  3363. /*
  3364. * move head/only segment
  3365. */
  3366. UniStrncpy_from_le(kname, name, len);
  3367. /*
  3368. * move additional segment(s)
  3369. */
  3370. while (si >= 0) {
  3371. /* get next segment */
  3372. t = &p->slot[si];
  3373. kname += len;
  3374. namlen -= len;
  3375. len = min(namlen, DTSLOTDATALEN);
  3376. UniStrncpy_from_le(kname, t->name, len);
  3377. si = t->next;
  3378. }
  3379. }
  3380. /*
  3381. * dtInsertEntry()
  3382. *
  3383. * function: allocate free slot(s) and
  3384. * write a leaf/internal entry
  3385. *
  3386. * return: entry slot index
  3387. */
  3388. static void dtInsertEntry(dtpage_t * p, int index, struct component_name * key,
  3389. ddata_t * data, struct dt_lock ** dtlock)
  3390. {
  3391. struct dtslot *h, *t;
  3392. struct ldtentry *lh = NULL;
  3393. struct idtentry *ih = NULL;
  3394. int hsi, fsi, klen, len, nextindex;
  3395. wchar_t *kname;
  3396. __le16 *name;
  3397. s8 *stbl;
  3398. pxd_t *xd;
  3399. struct dt_lock *dtlck = *dtlock;
  3400. struct lv *lv;
  3401. int xsi, n;
  3402. s64 bn = 0;
  3403. struct metapage *mp = NULL;
  3404. klen = key->namlen;
  3405. kname = key->name;
  3406. /* allocate a free slot */
  3407. hsi = fsi = p->header.freelist;
  3408. h = &p->slot[fsi];
  3409. p->header.freelist = h->next;
  3410. --p->header.freecnt;
  3411. /* open new linelock */
  3412. if (dtlck->index >= dtlck->maxcnt)
  3413. dtlck = (struct dt_lock *) txLinelock(dtlck);
  3414. lv = & dtlck->lv[dtlck->index];
  3415. lv->offset = hsi;
  3416. /* write head/only segment */
  3417. if (p->header.flag & BT_LEAF) {
  3418. lh = (struct ldtentry *) h;
  3419. lh->next = h->next;
  3420. lh->inumber = cpu_to_le32(data->leaf.ino);
  3421. lh->namlen = klen;
  3422. name = lh->name;
  3423. if (data->leaf.ip) {
  3424. len = min(klen, DTLHDRDATALEN);
  3425. if (!(p->header.flag & BT_ROOT))
  3426. bn = addressPXD(&p->header.self);
  3427. lh->index = cpu_to_le32(add_index(data->leaf.tid,
  3428. data->leaf.ip,
  3429. bn, index));
  3430. } else
  3431. len = min(klen, DTLHDRDATALEN_LEGACY);
  3432. } else {
  3433. ih = (struct idtentry *) h;
  3434. ih->next = h->next;
  3435. xd = (pxd_t *) ih;
  3436. *xd = data->xd;
  3437. ih->namlen = klen;
  3438. name = ih->name;
  3439. len = min(klen, DTIHDRDATALEN);
  3440. }
  3441. UniStrncpy_to_le(name, kname, len);
  3442. n = 1;
  3443. xsi = hsi;
  3444. /* write additional segment(s) */
  3445. t = h;
  3446. klen -= len;
  3447. while (klen) {
  3448. /* get free slot */
  3449. fsi = p->header.freelist;
  3450. t = &p->slot[fsi];
  3451. p->header.freelist = t->next;
  3452. --p->header.freecnt;
  3453. /* is next slot contiguous ? */
  3454. if (fsi != xsi + 1) {
  3455. /* close current linelock */
  3456. lv->length = n;
  3457. dtlck->index++;
  3458. /* open new linelock */
  3459. if (dtlck->index < dtlck->maxcnt)
  3460. lv++;
  3461. else {
  3462. dtlck = (struct dt_lock *) txLinelock(dtlck);
  3463. lv = & dtlck->lv[0];
  3464. }
  3465. lv->offset = fsi;
  3466. n = 0;
  3467. }
  3468. kname += len;
  3469. len = min(klen, DTSLOTDATALEN);
  3470. UniStrncpy_to_le(t->name, kname, len);
  3471. n++;
  3472. xsi = fsi;
  3473. klen -= len;
  3474. }
  3475. /* close current linelock */
  3476. lv->length = n;
  3477. dtlck->index++;
  3478. *dtlock = dtlck;
  3479. /* terminate last/only segment */
  3480. if (h == t) {
  3481. /* single segment entry */
  3482. if (p->header.flag & BT_LEAF)
  3483. lh->next = -1;
  3484. else
  3485. ih->next = -1;
  3486. } else
  3487. /* multi-segment entry */
  3488. t->next = -1;
  3489. /* if insert into middle, shift right succeeding entries in stbl */
  3490. stbl = DT_GETSTBL(p);
  3491. nextindex = p->header.nextindex;
  3492. if (index < nextindex) {
  3493. memmove(stbl + index + 1, stbl + index, nextindex - index);
  3494. if ((p->header.flag & BT_LEAF) && data->leaf.ip) {
  3495. s64 lblock;
  3496. /*
  3497. * Need to update slot number for entries that moved
  3498. * in the stbl
  3499. */
  3500. mp = NULL;
  3501. for (n = index + 1; n <= nextindex; n++) {
  3502. lh = (struct ldtentry *) & (p->slot[stbl[n]]);
  3503. modify_index(data->leaf.tid, data->leaf.ip,
  3504. le32_to_cpu(lh->index), bn, n,
  3505. &mp, &lblock);
  3506. }
  3507. if (mp)
  3508. release_metapage(mp);
  3509. }
  3510. }
  3511. stbl[index] = hsi;
  3512. /* advance next available entry index of stbl */
  3513. ++p->header.nextindex;
  3514. }
  3515. /*
  3516. * dtMoveEntry()
  3517. *
  3518. * function: move entries from split/left page to new/right page
  3519. *
  3520. * nextindex of dst page and freelist/freecnt of both pages
  3521. * are updated.
  3522. */
  3523. static void dtMoveEntry(dtpage_t * sp, int si, dtpage_t * dp,
  3524. struct dt_lock ** sdtlock, struct dt_lock ** ddtlock,
  3525. int do_index)
  3526. {
  3527. int ssi, next; /* src slot index */
  3528. int di; /* dst entry index */
  3529. int dsi; /* dst slot index */
  3530. s8 *sstbl, *dstbl; /* sorted entry table */
  3531. int snamlen, len;
  3532. struct ldtentry *slh, *dlh = NULL;
  3533. struct idtentry *sih, *dih = NULL;
  3534. struct dtslot *h, *s, *d;
  3535. struct dt_lock *sdtlck = *sdtlock, *ddtlck = *ddtlock;
  3536. struct lv *slv, *dlv;
  3537. int xssi, ns, nd;
  3538. int sfsi;
  3539. sstbl = (s8 *) & sp->slot[sp->header.stblindex];
  3540. dstbl = (s8 *) & dp->slot[dp->header.stblindex];
  3541. dsi = dp->header.freelist; /* first (whole page) free slot */
  3542. sfsi = sp->header.freelist;
  3543. /* linelock destination entry slot */
  3544. dlv = & ddtlck->lv[ddtlck->index];
  3545. dlv->offset = dsi;
  3546. /* linelock source entry slot */
  3547. slv = & sdtlck->lv[sdtlck->index];
  3548. slv->offset = sstbl[si];
  3549. xssi = slv->offset - 1;
  3550. /*
  3551. * move entries
  3552. */
  3553. ns = nd = 0;
  3554. for (di = 0; si < sp->header.nextindex; si++, di++) {
  3555. ssi = sstbl[si];
  3556. dstbl[di] = dsi;
  3557. /* is next slot contiguous ? */
  3558. if (ssi != xssi + 1) {
  3559. /* close current linelock */
  3560. slv->length = ns;
  3561. sdtlck->index++;
  3562. /* open new linelock */
  3563. if (sdtlck->index < sdtlck->maxcnt)
  3564. slv++;
  3565. else {
  3566. sdtlck = (struct dt_lock *) txLinelock(sdtlck);
  3567. slv = & sdtlck->lv[0];
  3568. }
  3569. slv->offset = ssi;
  3570. ns = 0;
  3571. }
  3572. /*
  3573. * move head/only segment of an entry
  3574. */
  3575. /* get dst slot */
  3576. h = d = &dp->slot[dsi];
  3577. /* get src slot and move */
  3578. s = &sp->slot[ssi];
  3579. if (sp->header.flag & BT_LEAF) {
  3580. /* get source entry */
  3581. slh = (struct ldtentry *) s;
  3582. dlh = (struct ldtentry *) h;
  3583. snamlen = slh->namlen;
  3584. if (do_index) {
  3585. len = min(snamlen, DTLHDRDATALEN);
  3586. dlh->index = slh->index; /* little-endian */
  3587. } else
  3588. len = min(snamlen, DTLHDRDATALEN_LEGACY);
  3589. memcpy(dlh, slh, 6 + len * 2);
  3590. next = slh->next;
  3591. /* update dst head/only segment next field */
  3592. dsi++;
  3593. dlh->next = dsi;
  3594. } else {
  3595. sih = (struct idtentry *) s;
  3596. snamlen = sih->namlen;
  3597. len = min(snamlen, DTIHDRDATALEN);
  3598. dih = (struct idtentry *) h;
  3599. memcpy(dih, sih, 10 + len * 2);
  3600. next = sih->next;
  3601. dsi++;
  3602. dih->next = dsi;
  3603. }
  3604. /* free src head/only segment */
  3605. s->next = sfsi;
  3606. s->cnt = 1;
  3607. sfsi = ssi;
  3608. ns++;
  3609. nd++;
  3610. xssi = ssi;
  3611. /*
  3612. * move additional segment(s) of the entry
  3613. */
  3614. snamlen -= len;
  3615. while ((ssi = next) >= 0) {
  3616. /* is next slot contiguous ? */
  3617. if (ssi != xssi + 1) {
  3618. /* close current linelock */
  3619. slv->length = ns;
  3620. sdtlck->index++;
  3621. /* open new linelock */
  3622. if (sdtlck->index < sdtlck->maxcnt)
  3623. slv++;
  3624. else {
  3625. sdtlck =
  3626. (struct dt_lock *)
  3627. txLinelock(sdtlck);
  3628. slv = & sdtlck->lv[0];
  3629. }
  3630. slv->offset = ssi;
  3631. ns = 0;
  3632. }
  3633. /* get next source segment */
  3634. s = &sp->slot[ssi];
  3635. /* get next destination free slot */
  3636. d++;
  3637. len = min(snamlen, DTSLOTDATALEN);
  3638. UniStrncpy_le(d->name, s->name, len);
  3639. ns++;
  3640. nd++;
  3641. xssi = ssi;
  3642. dsi++;
  3643. d->next = dsi;
  3644. /* free source segment */
  3645. next = s->next;
  3646. s->next = sfsi;
  3647. s->cnt = 1;
  3648. sfsi = ssi;
  3649. snamlen -= len;
  3650. } /* end while */
  3651. /* terminate dst last/only segment */
  3652. if (h == d) {
  3653. /* single segment entry */
  3654. if (dp->header.flag & BT_LEAF)
  3655. dlh->next = -1;
  3656. else
  3657. dih->next = -1;
  3658. } else
  3659. /* multi-segment entry */
  3660. d->next = -1;
  3661. } /* end for */
  3662. /* close current linelock */
  3663. slv->length = ns;
  3664. sdtlck->index++;
  3665. *sdtlock = sdtlck;
  3666. dlv->length = nd;
  3667. ddtlck->index++;
  3668. *ddtlock = ddtlck;
  3669. /* update source header */
  3670. sp->header.freelist = sfsi;
  3671. sp->header.freecnt += nd;
  3672. /* update destination header */
  3673. dp->header.nextindex = di;
  3674. dp->header.freelist = dsi;
  3675. dp->header.freecnt -= nd;
  3676. }
  3677. /*
  3678. * dtDeleteEntry()
  3679. *
  3680. * function: free a (leaf/internal) entry
  3681. *
  3682. * log freelist header, stbl, and each segment slot of entry
  3683. * (even though last/only segment next field is modified,
  3684. * physical image logging requires all segment slots of
  3685. * the entry logged to avoid applying previous updates
  3686. * to the same slots)
  3687. */
  3688. static void dtDeleteEntry(dtpage_t * p, int fi, struct dt_lock ** dtlock)
  3689. {
  3690. int fsi; /* free entry slot index */
  3691. s8 *stbl;
  3692. struct dtslot *t;
  3693. int si, freecnt;
  3694. struct dt_lock *dtlck = *dtlock;
  3695. struct lv *lv;
  3696. int xsi, n;
  3697. /* get free entry slot index */
  3698. stbl = DT_GETSTBL(p);
  3699. fsi = stbl[fi];
  3700. /* open new linelock */
  3701. if (dtlck->index >= dtlck->maxcnt)
  3702. dtlck = (struct dt_lock *) txLinelock(dtlck);
  3703. lv = & dtlck->lv[dtlck->index];
  3704. lv->offset = fsi;
  3705. /* get the head/only segment */
  3706. t = &p->slot[fsi];
  3707. if (p->header.flag & BT_LEAF)
  3708. si = ((struct ldtentry *) t)->next;
  3709. else
  3710. si = ((struct idtentry *) t)->next;
  3711. t->next = si;
  3712. t->cnt = 1;
  3713. n = freecnt = 1;
  3714. xsi = fsi;
  3715. /* find the last/only segment */
  3716. while (si >= 0) {
  3717. /* is next slot contiguous ? */
  3718. if (si != xsi + 1) {
  3719. /* close current linelock */
  3720. lv->length = n;
  3721. dtlck->index++;
  3722. /* open new linelock */
  3723. if (dtlck->index < dtlck->maxcnt)
  3724. lv++;
  3725. else {
  3726. dtlck = (struct dt_lock *) txLinelock(dtlck);
  3727. lv = & dtlck->lv[0];
  3728. }
  3729. lv->offset = si;
  3730. n = 0;
  3731. }
  3732. n++;
  3733. xsi = si;
  3734. freecnt++;
  3735. t = &p->slot[si];
  3736. t->cnt = 1;
  3737. si = t->next;
  3738. }
  3739. /* close current linelock */
  3740. lv->length = n;
  3741. dtlck->index++;
  3742. *dtlock = dtlck;
  3743. /* update freelist */
  3744. t->next = p->header.freelist;
  3745. p->header.freelist = fsi;
  3746. p->header.freecnt += freecnt;
  3747. /* if delete from middle,
  3748. * shift left the succedding entries in the stbl
  3749. */
  3750. si = p->header.nextindex;
  3751. if (fi < si - 1)
  3752. memmove(&stbl[fi], &stbl[fi + 1], si - fi - 1);
  3753. p->header.nextindex--;
  3754. }
  3755. /*
  3756. * dtTruncateEntry()
  3757. *
  3758. * function: truncate a (leaf/internal) entry
  3759. *
  3760. * log freelist header, stbl, and each segment slot of entry
  3761. * (even though last/only segment next field is modified,
  3762. * physical image logging requires all segment slots of
  3763. * the entry logged to avoid applying previous updates
  3764. * to the same slots)
  3765. */
  3766. static void dtTruncateEntry(dtpage_t * p, int ti, struct dt_lock ** dtlock)
  3767. {
  3768. int tsi; /* truncate entry slot index */
  3769. s8 *stbl;
  3770. struct dtslot *t;
  3771. int si, freecnt;
  3772. struct dt_lock *dtlck = *dtlock;
  3773. struct lv *lv;
  3774. int fsi, xsi, n;
  3775. /* get free entry slot index */
  3776. stbl = DT_GETSTBL(p);
  3777. tsi = stbl[ti];
  3778. /* open new linelock */
  3779. if (dtlck->index >= dtlck->maxcnt)
  3780. dtlck = (struct dt_lock *) txLinelock(dtlck);
  3781. lv = & dtlck->lv[dtlck->index];
  3782. lv->offset = tsi;
  3783. /* get the head/only segment */
  3784. t = &p->slot[tsi];
  3785. ASSERT(p->header.flag & BT_INTERNAL);
  3786. ((struct idtentry *) t)->namlen = 0;
  3787. si = ((struct idtentry *) t)->next;
  3788. ((struct idtentry *) t)->next = -1;
  3789. n = 1;
  3790. freecnt = 0;
  3791. fsi = si;
  3792. xsi = tsi;
  3793. /* find the last/only segment */
  3794. while (si >= 0) {
  3795. /* is next slot contiguous ? */
  3796. if (si != xsi + 1) {
  3797. /* close current linelock */
  3798. lv->length = n;
  3799. dtlck->index++;
  3800. /* open new linelock */
  3801. if (dtlck->index < dtlck->maxcnt)
  3802. lv++;
  3803. else {
  3804. dtlck = (struct dt_lock *) txLinelock(dtlck);
  3805. lv = & dtlck->lv[0];
  3806. }
  3807. lv->offset = si;
  3808. n = 0;
  3809. }
  3810. n++;
  3811. xsi = si;
  3812. freecnt++;
  3813. t = &p->slot[si];
  3814. t->cnt = 1;
  3815. si = t->next;
  3816. }
  3817. /* close current linelock */
  3818. lv->length = n;
  3819. dtlck->index++;
  3820. *dtlock = dtlck;
  3821. /* update freelist */
  3822. if (freecnt == 0)
  3823. return;
  3824. t->next = p->header.freelist;
  3825. p->header.freelist = fsi;
  3826. p->header.freecnt += freecnt;
  3827. }
  3828. /*
  3829. * dtLinelockFreelist()
  3830. */
  3831. static void dtLinelockFreelist(dtpage_t * p, /* directory page */
  3832. int m, /* max slot index */
  3833. struct dt_lock ** dtlock)
  3834. {
  3835. int fsi; /* free entry slot index */
  3836. struct dtslot *t;
  3837. int si;
  3838. struct dt_lock *dtlck = *dtlock;
  3839. struct lv *lv;
  3840. int xsi, n;
  3841. /* get free entry slot index */
  3842. fsi = p->header.freelist;
  3843. /* open new linelock */
  3844. if (dtlck->index >= dtlck->maxcnt)
  3845. dtlck = (struct dt_lock *) txLinelock(dtlck);
  3846. lv = & dtlck->lv[dtlck->index];
  3847. lv->offset = fsi;
  3848. n = 1;
  3849. xsi = fsi;
  3850. t = &p->slot[fsi];
  3851. si = t->next;
  3852. /* find the last/only segment */
  3853. while (si < m && si >= 0) {
  3854. /* is next slot contiguous ? */
  3855. if (si != xsi + 1) {
  3856. /* close current linelock */
  3857. lv->length = n;
  3858. dtlck->index++;
  3859. /* open new linelock */
  3860. if (dtlck->index < dtlck->maxcnt)
  3861. lv++;
  3862. else {
  3863. dtlck = (struct dt_lock *) txLinelock(dtlck);
  3864. lv = & dtlck->lv[0];
  3865. }
  3866. lv->offset = si;
  3867. n = 0;
  3868. }
  3869. n++;
  3870. xsi = si;
  3871. t = &p->slot[si];
  3872. si = t->next;
  3873. }
  3874. /* close current linelock */
  3875. lv->length = n;
  3876. dtlck->index++;
  3877. *dtlock = dtlck;
  3878. }
  3879. /*
  3880. * NAME: dtModify
  3881. *
  3882. * FUNCTION: Modify the inode number part of a directory entry
  3883. *
  3884. * PARAMETERS:
  3885. * tid - Transaction id
  3886. * ip - Inode of parent directory
  3887. * key - Name of entry to be modified
  3888. * orig_ino - Original inode number expected in entry
  3889. * new_ino - New inode number to put into entry
  3890. * flag - JFS_RENAME
  3891. *
  3892. * RETURNS:
  3893. * -ESTALE - If entry found does not match orig_ino passed in
  3894. * -ENOENT - If no entry can be found to match key
  3895. * 0 - If successfully modified entry
  3896. */
  3897. int dtModify(tid_t tid, struct inode *ip,
  3898. struct component_name * key, ino_t * orig_ino, ino_t new_ino, int flag)
  3899. {
  3900. int rc;
  3901. s64 bn;
  3902. struct metapage *mp;
  3903. dtpage_t *p;
  3904. int index;
  3905. struct btstack btstack;
  3906. struct tlock *tlck;
  3907. struct dt_lock *dtlck;
  3908. struct lv *lv;
  3909. s8 *stbl;
  3910. int entry_si; /* entry slot index */
  3911. struct ldtentry *entry;
  3912. /*
  3913. * search for the entry to modify:
  3914. *
  3915. * dtSearch() returns (leaf page pinned, index at which to modify).
  3916. */
  3917. if ((rc = dtSearch(ip, key, orig_ino, &btstack, flag)))
  3918. return rc;
  3919. /* retrieve search result */
  3920. DT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
  3921. BT_MARK_DIRTY(mp, ip);
  3922. /*
  3923. * acquire a transaction lock on the leaf page of named entry
  3924. */
  3925. tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY);
  3926. dtlck = (struct dt_lock *) & tlck->lock;
  3927. /* get slot index of the entry */
  3928. stbl = DT_GETSTBL(p);
  3929. entry_si = stbl[index];
  3930. /* linelock entry */
  3931. ASSERT(dtlck->index == 0);
  3932. lv = & dtlck->lv[0];
  3933. lv->offset = entry_si;
  3934. lv->length = 1;
  3935. dtlck->index++;
  3936. /* get the head/only segment */
  3937. entry = (struct ldtentry *) & p->slot[entry_si];
  3938. /* substitute the inode number of the entry */
  3939. entry->inumber = cpu_to_le32(new_ino);
  3940. /* unpin the leaf page */
  3941. DT_PUTPAGE(mp);
  3942. return 0;
  3943. }