jfs_dtree.c 100 KB

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