xfs_da_btree.c 71 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703
  1. /*
  2. * Copyright (c) 2000-2005 Silicon Graphics, Inc.
  3. * Copyright (c) 2013 Red Hat, Inc.
  4. * All Rights Reserved.
  5. *
  6. * This program is free software; you can redistribute it and/or
  7. * modify it under the terms of the GNU General Public License as
  8. * published by the Free Software Foundation.
  9. *
  10. * This program is distributed in the hope that it would be useful,
  11. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13. * GNU General Public License for more details.
  14. *
  15. * You should have received a copy of the GNU General Public License
  16. * along with this program; if not, write the Free Software Foundation,
  17. * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  18. */
  19. #include "xfs.h"
  20. #include "xfs_fs.h"
  21. #include "xfs_types.h"
  22. #include "xfs_bit.h"
  23. #include "xfs_log.h"
  24. #include "xfs_trans.h"
  25. #include "xfs_sb.h"
  26. #include "xfs_ag.h"
  27. #include "xfs_mount.h"
  28. #include "xfs_da_btree.h"
  29. #include "xfs_bmap_btree.h"
  30. #include "xfs_dir2.h"
  31. #include "xfs_dir2_format.h"
  32. #include "xfs_dir2_priv.h"
  33. #include "xfs_dinode.h"
  34. #include "xfs_inode.h"
  35. #include "xfs_inode_item.h"
  36. #include "xfs_alloc.h"
  37. #include "xfs_bmap.h"
  38. #include "xfs_attr.h"
  39. #include "xfs_attr_leaf.h"
  40. #include "xfs_error.h"
  41. #include "xfs_trace.h"
  42. #include "xfs_cksum.h"
  43. #include "xfs_buf_item.h"
  44. /*
  45. * xfs_da_btree.c
  46. *
  47. * Routines to implement directories as Btrees of hashed names.
  48. */
  49. /*========================================================================
  50. * Function prototypes for the kernel.
  51. *========================================================================*/
  52. /*
  53. * Routines used for growing the Btree.
  54. */
  55. STATIC int xfs_da3_root_split(xfs_da_state_t *state,
  56. xfs_da_state_blk_t *existing_root,
  57. xfs_da_state_blk_t *new_child);
  58. STATIC int xfs_da3_node_split(xfs_da_state_t *state,
  59. xfs_da_state_blk_t *existing_blk,
  60. xfs_da_state_blk_t *split_blk,
  61. xfs_da_state_blk_t *blk_to_add,
  62. int treelevel,
  63. int *result);
  64. STATIC void xfs_da3_node_rebalance(xfs_da_state_t *state,
  65. xfs_da_state_blk_t *node_blk_1,
  66. xfs_da_state_blk_t *node_blk_2);
  67. STATIC void xfs_da3_node_add(xfs_da_state_t *state,
  68. xfs_da_state_blk_t *old_node_blk,
  69. xfs_da_state_blk_t *new_node_blk);
  70. /*
  71. * Routines used for shrinking the Btree.
  72. */
  73. STATIC int xfs_da3_root_join(xfs_da_state_t *state,
  74. xfs_da_state_blk_t *root_blk);
  75. STATIC int xfs_da3_node_toosmall(xfs_da_state_t *state, int *retval);
  76. STATIC void xfs_da3_node_remove(xfs_da_state_t *state,
  77. xfs_da_state_blk_t *drop_blk);
  78. STATIC void xfs_da3_node_unbalance(xfs_da_state_t *state,
  79. xfs_da_state_blk_t *src_node_blk,
  80. xfs_da_state_blk_t *dst_node_blk);
  81. /*
  82. * Utility routines.
  83. */
  84. STATIC int xfs_da3_blk_unlink(xfs_da_state_t *state,
  85. xfs_da_state_blk_t *drop_blk,
  86. xfs_da_state_blk_t *save_blk);
  87. kmem_zone_t *xfs_da_state_zone; /* anchor for state struct zone */
  88. /*
  89. * Allocate a dir-state structure.
  90. * We don't put them on the stack since they're large.
  91. */
  92. xfs_da_state_t *
  93. xfs_da_state_alloc(void)
  94. {
  95. return kmem_zone_zalloc(xfs_da_state_zone, KM_NOFS);
  96. }
  97. /*
  98. * Kill the altpath contents of a da-state structure.
  99. */
  100. STATIC void
  101. xfs_da_state_kill_altpath(xfs_da_state_t *state)
  102. {
  103. int i;
  104. for (i = 0; i < state->altpath.active; i++)
  105. state->altpath.blk[i].bp = NULL;
  106. state->altpath.active = 0;
  107. }
  108. /*
  109. * Free a da-state structure.
  110. */
  111. void
  112. xfs_da_state_free(xfs_da_state_t *state)
  113. {
  114. xfs_da_state_kill_altpath(state);
  115. #ifdef DEBUG
  116. memset((char *)state, 0, sizeof(*state));
  117. #endif /* DEBUG */
  118. kmem_zone_free(xfs_da_state_zone, state);
  119. }
  120. void
  121. xfs_da3_node_hdr_from_disk(
  122. struct xfs_da3_icnode_hdr *to,
  123. struct xfs_da_intnode *from)
  124. {
  125. ASSERT(from->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
  126. from->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
  127. if (from->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC)) {
  128. struct xfs_da3_node_hdr *hdr3 = (struct xfs_da3_node_hdr *)from;
  129. to->forw = be32_to_cpu(hdr3->info.hdr.forw);
  130. to->back = be32_to_cpu(hdr3->info.hdr.back);
  131. to->magic = be16_to_cpu(hdr3->info.hdr.magic);
  132. to->count = be16_to_cpu(hdr3->__count);
  133. to->level = be16_to_cpu(hdr3->__level);
  134. return;
  135. }
  136. to->forw = be32_to_cpu(from->hdr.info.forw);
  137. to->back = be32_to_cpu(from->hdr.info.back);
  138. to->magic = be16_to_cpu(from->hdr.info.magic);
  139. to->count = be16_to_cpu(from->hdr.__count);
  140. to->level = be16_to_cpu(from->hdr.__level);
  141. }
  142. void
  143. xfs_da3_node_hdr_to_disk(
  144. struct xfs_da_intnode *to,
  145. struct xfs_da3_icnode_hdr *from)
  146. {
  147. ASSERT(from->magic == XFS_DA_NODE_MAGIC ||
  148. from->magic == XFS_DA3_NODE_MAGIC);
  149. if (from->magic == XFS_DA3_NODE_MAGIC) {
  150. struct xfs_da3_node_hdr *hdr3 = (struct xfs_da3_node_hdr *)to;
  151. hdr3->info.hdr.forw = cpu_to_be32(from->forw);
  152. hdr3->info.hdr.back = cpu_to_be32(from->back);
  153. hdr3->info.hdr.magic = cpu_to_be16(from->magic);
  154. hdr3->__count = cpu_to_be16(from->count);
  155. hdr3->__level = cpu_to_be16(from->level);
  156. return;
  157. }
  158. to->hdr.info.forw = cpu_to_be32(from->forw);
  159. to->hdr.info.back = cpu_to_be32(from->back);
  160. to->hdr.info.magic = cpu_to_be16(from->magic);
  161. to->hdr.__count = cpu_to_be16(from->count);
  162. to->hdr.__level = cpu_to_be16(from->level);
  163. }
  164. static bool
  165. xfs_da3_node_verify(
  166. struct xfs_buf *bp)
  167. {
  168. struct xfs_mount *mp = bp->b_target->bt_mount;
  169. struct xfs_da_intnode *hdr = bp->b_addr;
  170. struct xfs_da3_icnode_hdr ichdr;
  171. xfs_da3_node_hdr_from_disk(&ichdr, hdr);
  172. if (xfs_sb_version_hascrc(&mp->m_sb)) {
  173. struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
  174. if (ichdr.magic != XFS_DA3_NODE_MAGIC)
  175. return false;
  176. if (!uuid_equal(&hdr3->info.uuid, &mp->m_sb.sb_uuid))
  177. return false;
  178. if (be64_to_cpu(hdr3->info.blkno) != bp->b_bn)
  179. return false;
  180. } else {
  181. if (ichdr.magic != XFS_DA_NODE_MAGIC)
  182. return false;
  183. }
  184. if (ichdr.level == 0)
  185. return false;
  186. if (ichdr.level > XFS_DA_NODE_MAXDEPTH)
  187. return false;
  188. if (ichdr.count == 0)
  189. return false;
  190. /*
  191. * we don't know if the node is for and attribute or directory tree,
  192. * so only fail if the count is outside both bounds
  193. */
  194. if (ichdr.count > mp->m_dir_node_ents &&
  195. ichdr.count > mp->m_attr_node_ents)
  196. return false;
  197. /* XXX: hash order check? */
  198. return true;
  199. }
  200. static void
  201. xfs_da3_node_write_verify(
  202. struct xfs_buf *bp)
  203. {
  204. struct xfs_mount *mp = bp->b_target->bt_mount;
  205. struct xfs_buf_log_item *bip = bp->b_fspriv;
  206. struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
  207. if (!xfs_da3_node_verify(bp)) {
  208. XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
  209. xfs_buf_ioerror(bp, EFSCORRUPTED);
  210. return;
  211. }
  212. if (!xfs_sb_version_hascrc(&mp->m_sb))
  213. return;
  214. if (bip)
  215. hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
  216. xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length), XFS_DA3_NODE_CRC_OFF);
  217. }
  218. /*
  219. * leaf/node format detection on trees is sketchy, so a node read can be done on
  220. * leaf level blocks when detection identifies the tree as a node format tree
  221. * incorrectly. In this case, we need to swap the verifier to match the correct
  222. * format of the block being read.
  223. */
  224. static void
  225. xfs_da3_node_read_verify(
  226. struct xfs_buf *bp)
  227. {
  228. struct xfs_mount *mp = bp->b_target->bt_mount;
  229. struct xfs_da_blkinfo *info = bp->b_addr;
  230. switch (be16_to_cpu(info->magic)) {
  231. case XFS_DA3_NODE_MAGIC:
  232. if (!xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
  233. XFS_DA3_NODE_CRC_OFF))
  234. break;
  235. /* fall through */
  236. case XFS_DA_NODE_MAGIC:
  237. if (!xfs_da3_node_verify(bp))
  238. break;
  239. return;
  240. case XFS_ATTR_LEAF_MAGIC:
  241. bp->b_ops = &xfs_attr3_leaf_buf_ops;
  242. bp->b_ops->verify_read(bp);
  243. return;
  244. case XFS_DIR2_LEAFN_MAGIC:
  245. case XFS_DIR3_LEAFN_MAGIC:
  246. bp->b_ops = &xfs_dir3_leafn_buf_ops;
  247. bp->b_ops->verify_read(bp);
  248. return;
  249. default:
  250. break;
  251. }
  252. /* corrupt block */
  253. XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
  254. xfs_buf_ioerror(bp, EFSCORRUPTED);
  255. }
  256. const struct xfs_buf_ops xfs_da3_node_buf_ops = {
  257. .verify_read = xfs_da3_node_read_verify,
  258. .verify_write = xfs_da3_node_write_verify,
  259. };
  260. int
  261. xfs_da3_node_read(
  262. struct xfs_trans *tp,
  263. struct xfs_inode *dp,
  264. xfs_dablk_t bno,
  265. xfs_daddr_t mappedbno,
  266. struct xfs_buf **bpp,
  267. int which_fork)
  268. {
  269. return xfs_da_read_buf(tp, dp, bno, mappedbno, bpp,
  270. which_fork, &xfs_da3_node_buf_ops);
  271. }
  272. /*========================================================================
  273. * Routines used for growing the Btree.
  274. *========================================================================*/
  275. /*
  276. * Create the initial contents of an intermediate node.
  277. */
  278. int
  279. xfs_da3_node_create(
  280. struct xfs_da_args *args,
  281. xfs_dablk_t blkno,
  282. int level,
  283. struct xfs_buf **bpp,
  284. int whichfork)
  285. {
  286. struct xfs_da_intnode *node;
  287. struct xfs_trans *tp = args->trans;
  288. struct xfs_mount *mp = tp->t_mountp;
  289. struct xfs_da3_icnode_hdr ichdr = {0};
  290. struct xfs_buf *bp;
  291. int error;
  292. trace_xfs_da_node_create(args);
  293. ASSERT(level <= XFS_DA_NODE_MAXDEPTH);
  294. error = xfs_da_get_buf(tp, args->dp, blkno, -1, &bp, whichfork);
  295. if (error)
  296. return(error);
  297. node = bp->b_addr;
  298. if (xfs_sb_version_hascrc(&mp->m_sb)) {
  299. struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
  300. ichdr.magic = XFS_DA3_NODE_MAGIC;
  301. hdr3->info.blkno = cpu_to_be64(bp->b_bn);
  302. hdr3->info.owner = cpu_to_be64(args->dp->i_ino);
  303. uuid_copy(&hdr3->info.uuid, &mp->m_sb.sb_uuid);
  304. } else {
  305. ichdr.magic = XFS_DA_NODE_MAGIC;
  306. }
  307. ichdr.level = level;
  308. xfs_da3_node_hdr_to_disk(node, &ichdr);
  309. xfs_trans_log_buf(tp, bp,
  310. XFS_DA_LOGRANGE(node, &node->hdr, xfs_da3_node_hdr_size(node)));
  311. bp->b_ops = &xfs_da3_node_buf_ops;
  312. *bpp = bp;
  313. return(0);
  314. }
  315. /*
  316. * Split a leaf node, rebalance, then possibly split
  317. * intermediate nodes, rebalance, etc.
  318. */
  319. int /* error */
  320. xfs_da3_split(
  321. struct xfs_da_state *state)
  322. {
  323. struct xfs_da_state_blk *oldblk;
  324. struct xfs_da_state_blk *newblk;
  325. struct xfs_da_state_blk *addblk;
  326. struct xfs_da_intnode *node;
  327. struct xfs_buf *bp;
  328. int max;
  329. int action;
  330. int error;
  331. int i;
  332. trace_xfs_da_split(state->args);
  333. /*
  334. * Walk back up the tree splitting/inserting/adjusting as necessary.
  335. * If we need to insert and there isn't room, split the node, then
  336. * decide which fragment to insert the new block from below into.
  337. * Note that we may split the root this way, but we need more fixup.
  338. */
  339. max = state->path.active - 1;
  340. ASSERT((max >= 0) && (max < XFS_DA_NODE_MAXDEPTH));
  341. ASSERT(state->path.blk[max].magic == XFS_ATTR_LEAF_MAGIC ||
  342. state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
  343. addblk = &state->path.blk[max]; /* initial dummy value */
  344. for (i = max; (i >= 0) && addblk; state->path.active--, i--) {
  345. oldblk = &state->path.blk[i];
  346. newblk = &state->altpath.blk[i];
  347. /*
  348. * If a leaf node then
  349. * Allocate a new leaf node, then rebalance across them.
  350. * else if an intermediate node then
  351. * We split on the last layer, must we split the node?
  352. */
  353. switch (oldblk->magic) {
  354. case XFS_ATTR_LEAF_MAGIC:
  355. error = xfs_attr3_leaf_split(state, oldblk, newblk);
  356. if ((error != 0) && (error != ENOSPC)) {
  357. return(error); /* GROT: attr is inconsistent */
  358. }
  359. if (!error) {
  360. addblk = newblk;
  361. break;
  362. }
  363. /*
  364. * Entry wouldn't fit, split the leaf again.
  365. */
  366. state->extravalid = 1;
  367. if (state->inleaf) {
  368. state->extraafter = 0; /* before newblk */
  369. trace_xfs_attr_leaf_split_before(state->args);
  370. error = xfs_attr3_leaf_split(state, oldblk,
  371. &state->extrablk);
  372. } else {
  373. state->extraafter = 1; /* after newblk */
  374. trace_xfs_attr_leaf_split_after(state->args);
  375. error = xfs_attr3_leaf_split(state, newblk,
  376. &state->extrablk);
  377. }
  378. if (error)
  379. return(error); /* GROT: attr inconsistent */
  380. addblk = newblk;
  381. break;
  382. case XFS_DIR2_LEAFN_MAGIC:
  383. error = xfs_dir2_leafn_split(state, oldblk, newblk);
  384. if (error)
  385. return error;
  386. addblk = newblk;
  387. break;
  388. case XFS_DA_NODE_MAGIC:
  389. error = xfs_da3_node_split(state, oldblk, newblk, addblk,
  390. max - i, &action);
  391. addblk->bp = NULL;
  392. if (error)
  393. return(error); /* GROT: dir is inconsistent */
  394. /*
  395. * Record the newly split block for the next time thru?
  396. */
  397. if (action)
  398. addblk = newblk;
  399. else
  400. addblk = NULL;
  401. break;
  402. }
  403. /*
  404. * Update the btree to show the new hashval for this child.
  405. */
  406. xfs_da3_fixhashpath(state, &state->path);
  407. }
  408. if (!addblk)
  409. return(0);
  410. /*
  411. * Split the root node.
  412. */
  413. ASSERT(state->path.active == 0);
  414. oldblk = &state->path.blk[0];
  415. error = xfs_da3_root_split(state, oldblk, addblk);
  416. if (error) {
  417. addblk->bp = NULL;
  418. return(error); /* GROT: dir is inconsistent */
  419. }
  420. /*
  421. * Update pointers to the node which used to be block 0 and
  422. * just got bumped because of the addition of a new root node.
  423. * There might be three blocks involved if a double split occurred,
  424. * and the original block 0 could be at any position in the list.
  425. *
  426. * Note: the magic numbers and sibling pointers are in the same
  427. * physical place for both v2 and v3 headers (by design). Hence it
  428. * doesn't matter which version of the xfs_da_intnode structure we use
  429. * here as the result will be the same using either structure.
  430. */
  431. node = oldblk->bp->b_addr;
  432. if (node->hdr.info.forw) {
  433. if (be32_to_cpu(node->hdr.info.forw) == addblk->blkno) {
  434. bp = addblk->bp;
  435. } else {
  436. ASSERT(state->extravalid);
  437. bp = state->extrablk.bp;
  438. }
  439. node = bp->b_addr;
  440. node->hdr.info.back = cpu_to_be32(oldblk->blkno);
  441. xfs_trans_log_buf(state->args->trans, bp,
  442. XFS_DA_LOGRANGE(node, &node->hdr.info,
  443. sizeof(node->hdr.info)));
  444. }
  445. node = oldblk->bp->b_addr;
  446. if (node->hdr.info.back) {
  447. if (be32_to_cpu(node->hdr.info.back) == addblk->blkno) {
  448. bp = addblk->bp;
  449. } else {
  450. ASSERT(state->extravalid);
  451. bp = state->extrablk.bp;
  452. }
  453. node = bp->b_addr;
  454. node->hdr.info.forw = cpu_to_be32(oldblk->blkno);
  455. xfs_trans_log_buf(state->args->trans, bp,
  456. XFS_DA_LOGRANGE(node, &node->hdr.info,
  457. sizeof(node->hdr.info)));
  458. }
  459. addblk->bp = NULL;
  460. return(0);
  461. }
  462. /*
  463. * Split the root. We have to create a new root and point to the two
  464. * parts (the split old root) that we just created. Copy block zero to
  465. * the EOF, extending the inode in process.
  466. */
  467. STATIC int /* error */
  468. xfs_da3_root_split(
  469. struct xfs_da_state *state,
  470. struct xfs_da_state_blk *blk1,
  471. struct xfs_da_state_blk *blk2)
  472. {
  473. struct xfs_da_intnode *node;
  474. struct xfs_da_intnode *oldroot;
  475. struct xfs_da_node_entry *btree;
  476. struct xfs_da3_icnode_hdr nodehdr;
  477. struct xfs_da_args *args;
  478. struct xfs_buf *bp;
  479. struct xfs_inode *dp;
  480. struct xfs_trans *tp;
  481. struct xfs_mount *mp;
  482. struct xfs_dir2_leaf *leaf;
  483. xfs_dablk_t blkno;
  484. int level;
  485. int error;
  486. int size;
  487. trace_xfs_da_root_split(state->args);
  488. /*
  489. * Copy the existing (incorrect) block from the root node position
  490. * to a free space somewhere.
  491. */
  492. args = state->args;
  493. error = xfs_da_grow_inode(args, &blkno);
  494. if (error)
  495. return error;
  496. dp = args->dp;
  497. tp = args->trans;
  498. mp = state->mp;
  499. error = xfs_da_get_buf(tp, dp, blkno, -1, &bp, args->whichfork);
  500. if (error)
  501. return error;
  502. node = bp->b_addr;
  503. oldroot = blk1->bp->b_addr;
  504. if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
  505. oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC)) {
  506. struct xfs_da3_icnode_hdr nodehdr;
  507. xfs_da3_node_hdr_from_disk(&nodehdr, oldroot);
  508. btree = xfs_da3_node_tree_p(oldroot);
  509. size = (int)((char *)&btree[nodehdr.count] - (char *)oldroot);
  510. level = nodehdr.level;
  511. } else {
  512. struct xfs_dir3_icleaf_hdr leafhdr;
  513. struct xfs_dir2_leaf_entry *ents;
  514. leaf = (xfs_dir2_leaf_t *)oldroot;
  515. xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
  516. ents = xfs_dir3_leaf_ents_p(leaf);
  517. ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
  518. leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
  519. size = (int)((char *)&ents[leafhdr.count] - (char *)leaf);
  520. level = 0;
  521. }
  522. /*
  523. * we can copy most of the information in the node from one block to
  524. * another, but for CRC enabled headers we have to make sure that the
  525. * block specific identifiers are kept intact. We update the buffer
  526. * directly for this.
  527. */
  528. memcpy(node, oldroot, size);
  529. if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||
  530. oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
  531. struct xfs_da3_intnode *node3 = (struct xfs_da3_intnode *)node;
  532. node3->hdr.info.blkno = cpu_to_be64(bp->b_bn);
  533. }
  534. xfs_trans_log_buf(tp, bp, 0, size - 1);
  535. bp->b_ops = blk1->bp->b_ops;
  536. blk1->bp = bp;
  537. blk1->blkno = blkno;
  538. /*
  539. * Set up the new root node.
  540. */
  541. error = xfs_da3_node_create(args,
  542. (args->whichfork == XFS_DATA_FORK) ? mp->m_dirleafblk : 0,
  543. level + 1, &bp, args->whichfork);
  544. if (error)
  545. return error;
  546. node = bp->b_addr;
  547. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  548. btree = xfs_da3_node_tree_p(node);
  549. btree[0].hashval = cpu_to_be32(blk1->hashval);
  550. btree[0].before = cpu_to_be32(blk1->blkno);
  551. btree[1].hashval = cpu_to_be32(blk2->hashval);
  552. btree[1].before = cpu_to_be32(blk2->blkno);
  553. nodehdr.count = 2;
  554. xfs_da3_node_hdr_to_disk(node, &nodehdr);
  555. #ifdef DEBUG
  556. if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  557. oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
  558. ASSERT(blk1->blkno >= mp->m_dirleafblk &&
  559. blk1->blkno < mp->m_dirfreeblk);
  560. ASSERT(blk2->blkno >= mp->m_dirleafblk &&
  561. blk2->blkno < mp->m_dirfreeblk);
  562. }
  563. #endif
  564. /* Header is already logged by xfs_da_node_create */
  565. xfs_trans_log_buf(tp, bp,
  566. XFS_DA_LOGRANGE(node, btree, sizeof(xfs_da_node_entry_t) * 2));
  567. return 0;
  568. }
  569. /*
  570. * Split the node, rebalance, then add the new entry.
  571. */
  572. STATIC int /* error */
  573. xfs_da3_node_split(
  574. struct xfs_da_state *state,
  575. struct xfs_da_state_blk *oldblk,
  576. struct xfs_da_state_blk *newblk,
  577. struct xfs_da_state_blk *addblk,
  578. int treelevel,
  579. int *result)
  580. {
  581. struct xfs_da_intnode *node;
  582. struct xfs_da3_icnode_hdr nodehdr;
  583. xfs_dablk_t blkno;
  584. int newcount;
  585. int error;
  586. int useextra;
  587. trace_xfs_da_node_split(state->args);
  588. node = oldblk->bp->b_addr;
  589. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  590. /*
  591. * With V2 dirs the extra block is data or freespace.
  592. */
  593. useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK;
  594. newcount = 1 + useextra;
  595. /*
  596. * Do we have to split the node?
  597. */
  598. if (nodehdr.count + newcount > state->node_ents) {
  599. /*
  600. * Allocate a new node, add to the doubly linked chain of
  601. * nodes, then move some of our excess entries into it.
  602. */
  603. error = xfs_da_grow_inode(state->args, &blkno);
  604. if (error)
  605. return(error); /* GROT: dir is inconsistent */
  606. error = xfs_da3_node_create(state->args, blkno, treelevel,
  607. &newblk->bp, state->args->whichfork);
  608. if (error)
  609. return(error); /* GROT: dir is inconsistent */
  610. newblk->blkno = blkno;
  611. newblk->magic = XFS_DA_NODE_MAGIC;
  612. xfs_da3_node_rebalance(state, oldblk, newblk);
  613. error = xfs_da3_blk_link(state, oldblk, newblk);
  614. if (error)
  615. return(error);
  616. *result = 1;
  617. } else {
  618. *result = 0;
  619. }
  620. /*
  621. * Insert the new entry(s) into the correct block
  622. * (updating last hashval in the process).
  623. *
  624. * xfs_da3_node_add() inserts BEFORE the given index,
  625. * and as a result of using node_lookup_int() we always
  626. * point to a valid entry (not after one), but a split
  627. * operation always results in a new block whose hashvals
  628. * FOLLOW the current block.
  629. *
  630. * If we had double-split op below us, then add the extra block too.
  631. */
  632. node = oldblk->bp->b_addr;
  633. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  634. if (oldblk->index <= nodehdr.count) {
  635. oldblk->index++;
  636. xfs_da3_node_add(state, oldblk, addblk);
  637. if (useextra) {
  638. if (state->extraafter)
  639. oldblk->index++;
  640. xfs_da3_node_add(state, oldblk, &state->extrablk);
  641. state->extravalid = 0;
  642. }
  643. } else {
  644. newblk->index++;
  645. xfs_da3_node_add(state, newblk, addblk);
  646. if (useextra) {
  647. if (state->extraafter)
  648. newblk->index++;
  649. xfs_da3_node_add(state, newblk, &state->extrablk);
  650. state->extravalid = 0;
  651. }
  652. }
  653. return(0);
  654. }
  655. /*
  656. * Balance the btree elements between two intermediate nodes,
  657. * usually one full and one empty.
  658. *
  659. * NOTE: if blk2 is empty, then it will get the upper half of blk1.
  660. */
  661. STATIC void
  662. xfs_da3_node_rebalance(
  663. struct xfs_da_state *state,
  664. struct xfs_da_state_blk *blk1,
  665. struct xfs_da_state_blk *blk2)
  666. {
  667. struct xfs_da_intnode *node1;
  668. struct xfs_da_intnode *node2;
  669. struct xfs_da_intnode *tmpnode;
  670. struct xfs_da_node_entry *btree1;
  671. struct xfs_da_node_entry *btree2;
  672. struct xfs_da_node_entry *btree_s;
  673. struct xfs_da_node_entry *btree_d;
  674. struct xfs_da3_icnode_hdr nodehdr1;
  675. struct xfs_da3_icnode_hdr nodehdr2;
  676. struct xfs_trans *tp;
  677. int count;
  678. int tmp;
  679. int swap = 0;
  680. trace_xfs_da_node_rebalance(state->args);
  681. node1 = blk1->bp->b_addr;
  682. node2 = blk2->bp->b_addr;
  683. xfs_da3_node_hdr_from_disk(&nodehdr1, node1);
  684. xfs_da3_node_hdr_from_disk(&nodehdr2, node2);
  685. btree1 = xfs_da3_node_tree_p(node1);
  686. btree2 = xfs_da3_node_tree_p(node2);
  687. /*
  688. * Figure out how many entries need to move, and in which direction.
  689. * Swap the nodes around if that makes it simpler.
  690. */
  691. if (nodehdr1.count > 0 && nodehdr2.count > 0 &&
  692. ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
  693. (be32_to_cpu(btree2[nodehdr2.count - 1].hashval) <
  694. be32_to_cpu(btree1[nodehdr1.count - 1].hashval)))) {
  695. tmpnode = node1;
  696. node1 = node2;
  697. node2 = tmpnode;
  698. xfs_da3_node_hdr_from_disk(&nodehdr1, node1);
  699. xfs_da3_node_hdr_from_disk(&nodehdr2, node2);
  700. btree1 = xfs_da3_node_tree_p(node1);
  701. btree2 = xfs_da3_node_tree_p(node2);
  702. swap = 1;
  703. }
  704. count = (nodehdr1.count - nodehdr2.count) / 2;
  705. if (count == 0)
  706. return;
  707. tp = state->args->trans;
  708. /*
  709. * Two cases: high-to-low and low-to-high.
  710. */
  711. if (count > 0) {
  712. /*
  713. * Move elements in node2 up to make a hole.
  714. */
  715. tmp = nodehdr2.count;
  716. if (tmp > 0) {
  717. tmp *= (uint)sizeof(xfs_da_node_entry_t);
  718. btree_s = &btree2[0];
  719. btree_d = &btree2[count];
  720. memmove(btree_d, btree_s, tmp);
  721. }
  722. /*
  723. * Move the req'd B-tree elements from high in node1 to
  724. * low in node2.
  725. */
  726. nodehdr2.count += count;
  727. tmp = count * (uint)sizeof(xfs_da_node_entry_t);
  728. btree_s = &btree1[nodehdr1.count - count];
  729. btree_d = &btree2[0];
  730. memcpy(btree_d, btree_s, tmp);
  731. nodehdr1.count -= count;
  732. } else {
  733. /*
  734. * Move the req'd B-tree elements from low in node2 to
  735. * high in node1.
  736. */
  737. count = -count;
  738. tmp = count * (uint)sizeof(xfs_da_node_entry_t);
  739. btree_s = &btree2[0];
  740. btree_d = &btree1[nodehdr1.count];
  741. memcpy(btree_d, btree_s, tmp);
  742. nodehdr1.count += count;
  743. xfs_trans_log_buf(tp, blk1->bp,
  744. XFS_DA_LOGRANGE(node1, btree_d, tmp));
  745. /*
  746. * Move elements in node2 down to fill the hole.
  747. */
  748. tmp = nodehdr2.count - count;
  749. tmp *= (uint)sizeof(xfs_da_node_entry_t);
  750. btree_s = &btree2[count];
  751. btree_d = &btree2[0];
  752. memmove(btree_d, btree_s, tmp);
  753. nodehdr2.count -= count;
  754. }
  755. /*
  756. * Log header of node 1 and all current bits of node 2.
  757. */
  758. xfs_da3_node_hdr_to_disk(node1, &nodehdr1);
  759. xfs_trans_log_buf(tp, blk1->bp,
  760. XFS_DA_LOGRANGE(node1, &node1->hdr,
  761. xfs_da3_node_hdr_size(node1)));
  762. xfs_da3_node_hdr_to_disk(node2, &nodehdr2);
  763. xfs_trans_log_buf(tp, blk2->bp,
  764. XFS_DA_LOGRANGE(node2, &node2->hdr,
  765. xfs_da3_node_hdr_size(node2) +
  766. (sizeof(btree2[0]) * nodehdr2.count)));
  767. /*
  768. * Record the last hashval from each block for upward propagation.
  769. * (note: don't use the swapped node pointers)
  770. */
  771. if (swap) {
  772. node1 = blk1->bp->b_addr;
  773. node2 = blk2->bp->b_addr;
  774. xfs_da3_node_hdr_from_disk(&nodehdr1, node1);
  775. xfs_da3_node_hdr_from_disk(&nodehdr2, node2);
  776. btree1 = xfs_da3_node_tree_p(node1);
  777. btree2 = xfs_da3_node_tree_p(node2);
  778. }
  779. blk1->hashval = be32_to_cpu(btree1[nodehdr1.count - 1].hashval);
  780. blk2->hashval = be32_to_cpu(btree2[nodehdr2.count - 1].hashval);
  781. /*
  782. * Adjust the expected index for insertion.
  783. */
  784. if (blk1->index >= nodehdr1.count) {
  785. blk2->index = blk1->index - nodehdr1.count;
  786. blk1->index = nodehdr1.count + 1; /* make it invalid */
  787. }
  788. }
  789. /*
  790. * Add a new entry to an intermediate node.
  791. */
  792. STATIC void
  793. xfs_da3_node_add(
  794. struct xfs_da_state *state,
  795. struct xfs_da_state_blk *oldblk,
  796. struct xfs_da_state_blk *newblk)
  797. {
  798. struct xfs_da_intnode *node;
  799. struct xfs_da3_icnode_hdr nodehdr;
  800. struct xfs_da_node_entry *btree;
  801. int tmp;
  802. trace_xfs_da_node_add(state->args);
  803. node = oldblk->bp->b_addr;
  804. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  805. btree = xfs_da3_node_tree_p(node);
  806. ASSERT(oldblk->index >= 0 && oldblk->index <= nodehdr.count);
  807. ASSERT(newblk->blkno != 0);
  808. if (state->args->whichfork == XFS_DATA_FORK)
  809. ASSERT(newblk->blkno >= state->mp->m_dirleafblk &&
  810. newblk->blkno < state->mp->m_dirfreeblk);
  811. /*
  812. * We may need to make some room before we insert the new node.
  813. */
  814. tmp = 0;
  815. if (oldblk->index < nodehdr.count) {
  816. tmp = (nodehdr.count - oldblk->index) * (uint)sizeof(*btree);
  817. memmove(&btree[oldblk->index + 1], &btree[oldblk->index], tmp);
  818. }
  819. btree[oldblk->index].hashval = cpu_to_be32(newblk->hashval);
  820. btree[oldblk->index].before = cpu_to_be32(newblk->blkno);
  821. xfs_trans_log_buf(state->args->trans, oldblk->bp,
  822. XFS_DA_LOGRANGE(node, &btree[oldblk->index],
  823. tmp + sizeof(*btree)));
  824. nodehdr.count += 1;
  825. xfs_da3_node_hdr_to_disk(node, &nodehdr);
  826. xfs_trans_log_buf(state->args->trans, oldblk->bp,
  827. XFS_DA_LOGRANGE(node, &node->hdr, xfs_da3_node_hdr_size(node)));
  828. /*
  829. * Copy the last hash value from the oldblk to propagate upwards.
  830. */
  831. oldblk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
  832. }
  833. /*========================================================================
  834. * Routines used for shrinking the Btree.
  835. *========================================================================*/
  836. /*
  837. * Deallocate an empty leaf node, remove it from its parent,
  838. * possibly deallocating that block, etc...
  839. */
  840. int
  841. xfs_da3_join(
  842. struct xfs_da_state *state)
  843. {
  844. struct xfs_da_state_blk *drop_blk;
  845. struct xfs_da_state_blk *save_blk;
  846. int action = 0;
  847. int error;
  848. trace_xfs_da_join(state->args);
  849. drop_blk = &state->path.blk[ state->path.active-1 ];
  850. save_blk = &state->altpath.blk[ state->path.active-1 ];
  851. ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC);
  852. ASSERT(drop_blk->magic == XFS_ATTR_LEAF_MAGIC ||
  853. drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
  854. /*
  855. * Walk back up the tree joining/deallocating as necessary.
  856. * When we stop dropping blocks, break out.
  857. */
  858. for ( ; state->path.active >= 2; drop_blk--, save_blk--,
  859. state->path.active--) {
  860. /*
  861. * See if we can combine the block with a neighbor.
  862. * (action == 0) => no options, just leave
  863. * (action == 1) => coalesce, then unlink
  864. * (action == 2) => block empty, unlink it
  865. */
  866. switch (drop_blk->magic) {
  867. case XFS_ATTR_LEAF_MAGIC:
  868. error = xfs_attr3_leaf_toosmall(state, &action);
  869. if (error)
  870. return(error);
  871. if (action == 0)
  872. return(0);
  873. xfs_attr3_leaf_unbalance(state, drop_blk, save_blk);
  874. break;
  875. case XFS_DIR2_LEAFN_MAGIC:
  876. error = xfs_dir2_leafn_toosmall(state, &action);
  877. if (error)
  878. return error;
  879. if (action == 0)
  880. return 0;
  881. xfs_dir2_leafn_unbalance(state, drop_blk, save_blk);
  882. break;
  883. case XFS_DA_NODE_MAGIC:
  884. /*
  885. * Remove the offending node, fixup hashvals,
  886. * check for a toosmall neighbor.
  887. */
  888. xfs_da3_node_remove(state, drop_blk);
  889. xfs_da3_fixhashpath(state, &state->path);
  890. error = xfs_da3_node_toosmall(state, &action);
  891. if (error)
  892. return(error);
  893. if (action == 0)
  894. return 0;
  895. xfs_da3_node_unbalance(state, drop_blk, save_blk);
  896. break;
  897. }
  898. xfs_da3_fixhashpath(state, &state->altpath);
  899. error = xfs_da3_blk_unlink(state, drop_blk, save_blk);
  900. xfs_da_state_kill_altpath(state);
  901. if (error)
  902. return(error);
  903. error = xfs_da_shrink_inode(state->args, drop_blk->blkno,
  904. drop_blk->bp);
  905. drop_blk->bp = NULL;
  906. if (error)
  907. return(error);
  908. }
  909. /*
  910. * We joined all the way to the top. If it turns out that
  911. * we only have one entry in the root, make the child block
  912. * the new root.
  913. */
  914. xfs_da3_node_remove(state, drop_blk);
  915. xfs_da3_fixhashpath(state, &state->path);
  916. error = xfs_da3_root_join(state, &state->path.blk[0]);
  917. return(error);
  918. }
  919. #ifdef DEBUG
  920. static void
  921. xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo *blkinfo, __u16 level)
  922. {
  923. __be16 magic = blkinfo->magic;
  924. if (level == 1) {
  925. ASSERT(magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  926. magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
  927. magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
  928. magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
  929. } else {
  930. ASSERT(magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
  931. magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
  932. }
  933. ASSERT(!blkinfo->forw);
  934. ASSERT(!blkinfo->back);
  935. }
  936. #else /* !DEBUG */
  937. #define xfs_da_blkinfo_onlychild_validate(blkinfo, level)
  938. #endif /* !DEBUG */
  939. /*
  940. * We have only one entry in the root. Copy the only remaining child of
  941. * the old root to block 0 as the new root node.
  942. */
  943. STATIC int
  944. xfs_da3_root_join(
  945. struct xfs_da_state *state,
  946. struct xfs_da_state_blk *root_blk)
  947. {
  948. struct xfs_da_intnode *oldroot;
  949. struct xfs_da_args *args;
  950. xfs_dablk_t child;
  951. struct xfs_buf *bp;
  952. struct xfs_da3_icnode_hdr oldroothdr;
  953. struct xfs_da_node_entry *btree;
  954. int error;
  955. trace_xfs_da_root_join(state->args);
  956. ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC);
  957. args = state->args;
  958. oldroot = root_blk->bp->b_addr;
  959. xfs_da3_node_hdr_from_disk(&oldroothdr, oldroot);
  960. ASSERT(oldroothdr.forw == 0);
  961. ASSERT(oldroothdr.back == 0);
  962. /*
  963. * If the root has more than one child, then don't do anything.
  964. */
  965. if (oldroothdr.count > 1)
  966. return 0;
  967. /*
  968. * Read in the (only) child block, then copy those bytes into
  969. * the root block's buffer and free the original child block.
  970. */
  971. btree = xfs_da3_node_tree_p(oldroot);
  972. child = be32_to_cpu(btree[0].before);
  973. ASSERT(child != 0);
  974. error = xfs_da3_node_read(args->trans, args->dp, child, -1, &bp,
  975. args->whichfork);
  976. if (error)
  977. return error;
  978. xfs_da_blkinfo_onlychild_validate(bp->b_addr, oldroothdr.level);
  979. /*
  980. * This could be copying a leaf back into the root block in the case of
  981. * there only being a single leaf block left in the tree. Hence we have
  982. * to update the b_ops pointer as well to match the buffer type change
  983. * that could occur. For dir3 blocks we also need to update the block
  984. * number in the buffer header.
  985. */
  986. memcpy(root_blk->bp->b_addr, bp->b_addr, state->blocksize);
  987. root_blk->bp->b_ops = bp->b_ops;
  988. if (oldroothdr.magic == XFS_DA3_NODE_MAGIC) {
  989. struct xfs_da3_blkinfo *da3 = root_blk->bp->b_addr;
  990. da3->blkno = cpu_to_be64(root_blk->bp->b_bn);
  991. }
  992. xfs_trans_log_buf(args->trans, root_blk->bp, 0, state->blocksize - 1);
  993. error = xfs_da_shrink_inode(args, child, bp);
  994. return(error);
  995. }
  996. /*
  997. * Check a node block and its neighbors to see if the block should be
  998. * collapsed into one or the other neighbor. Always keep the block
  999. * with the smaller block number.
  1000. * If the current block is over 50% full, don't try to join it, return 0.
  1001. * If the block is empty, fill in the state structure and return 2.
  1002. * If it can be collapsed, fill in the state structure and return 1.
  1003. * If nothing can be done, return 0.
  1004. */
  1005. STATIC int
  1006. xfs_da3_node_toosmall(
  1007. struct xfs_da_state *state,
  1008. int *action)
  1009. {
  1010. struct xfs_da_intnode *node;
  1011. struct xfs_da_state_blk *blk;
  1012. struct xfs_da_blkinfo *info;
  1013. xfs_dablk_t blkno;
  1014. struct xfs_buf *bp;
  1015. struct xfs_da3_icnode_hdr nodehdr;
  1016. int count;
  1017. int forward;
  1018. int error;
  1019. int retval;
  1020. int i;
  1021. trace_xfs_da_node_toosmall(state->args);
  1022. /*
  1023. * Check for the degenerate case of the block being over 50% full.
  1024. * If so, it's not worth even looking to see if we might be able
  1025. * to coalesce with a sibling.
  1026. */
  1027. blk = &state->path.blk[ state->path.active-1 ];
  1028. info = blk->bp->b_addr;
  1029. node = (xfs_da_intnode_t *)info;
  1030. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  1031. if (nodehdr.count > (state->node_ents >> 1)) {
  1032. *action = 0; /* blk over 50%, don't try to join */
  1033. return(0); /* blk over 50%, don't try to join */
  1034. }
  1035. /*
  1036. * Check for the degenerate case of the block being empty.
  1037. * If the block is empty, we'll simply delete it, no need to
  1038. * coalesce it with a sibling block. We choose (arbitrarily)
  1039. * to merge with the forward block unless it is NULL.
  1040. */
  1041. if (nodehdr.count == 0) {
  1042. /*
  1043. * Make altpath point to the block we want to keep and
  1044. * path point to the block we want to drop (this one).
  1045. */
  1046. forward = (info->forw != 0);
  1047. memcpy(&state->altpath, &state->path, sizeof(state->path));
  1048. error = xfs_da3_path_shift(state, &state->altpath, forward,
  1049. 0, &retval);
  1050. if (error)
  1051. return(error);
  1052. if (retval) {
  1053. *action = 0;
  1054. } else {
  1055. *action = 2;
  1056. }
  1057. return(0);
  1058. }
  1059. /*
  1060. * Examine each sibling block to see if we can coalesce with
  1061. * at least 25% free space to spare. We need to figure out
  1062. * whether to merge with the forward or the backward block.
  1063. * We prefer coalescing with the lower numbered sibling so as
  1064. * to shrink a directory over time.
  1065. */
  1066. count = state->node_ents;
  1067. count -= state->node_ents >> 2;
  1068. count -= nodehdr.count;
  1069. /* start with smaller blk num */
  1070. forward = nodehdr.forw < nodehdr.back;
  1071. for (i = 0; i < 2; forward = !forward, i++) {
  1072. if (forward)
  1073. blkno = nodehdr.forw;
  1074. else
  1075. blkno = nodehdr.back;
  1076. if (blkno == 0)
  1077. continue;
  1078. error = xfs_da3_node_read(state->args->trans, state->args->dp,
  1079. blkno, -1, &bp, state->args->whichfork);
  1080. if (error)
  1081. return(error);
  1082. node = bp->b_addr;
  1083. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  1084. xfs_trans_brelse(state->args->trans, bp);
  1085. if (count - nodehdr.count >= 0)
  1086. break; /* fits with at least 25% to spare */
  1087. }
  1088. if (i >= 2) {
  1089. *action = 0;
  1090. return 0;
  1091. }
  1092. /*
  1093. * Make altpath point to the block we want to keep (the lower
  1094. * numbered block) and path point to the block we want to drop.
  1095. */
  1096. memcpy(&state->altpath, &state->path, sizeof(state->path));
  1097. if (blkno < blk->blkno) {
  1098. error = xfs_da3_path_shift(state, &state->altpath, forward,
  1099. 0, &retval);
  1100. } else {
  1101. error = xfs_da3_path_shift(state, &state->path, forward,
  1102. 0, &retval);
  1103. }
  1104. if (error)
  1105. return error;
  1106. if (retval) {
  1107. *action = 0;
  1108. return 0;
  1109. }
  1110. *action = 1;
  1111. return 0;
  1112. }
  1113. /*
  1114. * Pick up the last hashvalue from an intermediate node.
  1115. */
  1116. STATIC uint
  1117. xfs_da3_node_lasthash(
  1118. struct xfs_buf *bp,
  1119. int *count)
  1120. {
  1121. struct xfs_da_intnode *node;
  1122. struct xfs_da_node_entry *btree;
  1123. struct xfs_da3_icnode_hdr nodehdr;
  1124. node = bp->b_addr;
  1125. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  1126. if (count)
  1127. *count = nodehdr.count;
  1128. if (!nodehdr.count)
  1129. return 0;
  1130. btree = xfs_da3_node_tree_p(node);
  1131. return be32_to_cpu(btree[nodehdr.count - 1].hashval);
  1132. }
  1133. /*
  1134. * Walk back up the tree adjusting hash values as necessary,
  1135. * when we stop making changes, return.
  1136. */
  1137. void
  1138. xfs_da3_fixhashpath(
  1139. struct xfs_da_state *state,
  1140. struct xfs_da_state_path *path)
  1141. {
  1142. struct xfs_da_state_blk *blk;
  1143. struct xfs_da_intnode *node;
  1144. struct xfs_da_node_entry *btree;
  1145. xfs_dahash_t lasthash=0;
  1146. int level;
  1147. int count;
  1148. trace_xfs_da_fixhashpath(state->args);
  1149. level = path->active-1;
  1150. blk = &path->blk[ level ];
  1151. switch (blk->magic) {
  1152. case XFS_ATTR_LEAF_MAGIC:
  1153. lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);
  1154. if (count == 0)
  1155. return;
  1156. break;
  1157. case XFS_DIR2_LEAFN_MAGIC:
  1158. lasthash = xfs_dir2_leafn_lasthash(blk->bp, &count);
  1159. if (count == 0)
  1160. return;
  1161. break;
  1162. case XFS_DA_NODE_MAGIC:
  1163. lasthash = xfs_da3_node_lasthash(blk->bp, &count);
  1164. if (count == 0)
  1165. return;
  1166. break;
  1167. }
  1168. for (blk--, level--; level >= 0; blk--, level--) {
  1169. struct xfs_da3_icnode_hdr nodehdr;
  1170. node = blk->bp->b_addr;
  1171. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  1172. btree = xfs_da3_node_tree_p(node);
  1173. if (be32_to_cpu(btree->hashval) == lasthash)
  1174. break;
  1175. blk->hashval = lasthash;
  1176. btree[blk->index].hashval = cpu_to_be32(lasthash);
  1177. xfs_trans_log_buf(state->args->trans, blk->bp,
  1178. XFS_DA_LOGRANGE(node, &btree[blk->index],
  1179. sizeof(*btree)));
  1180. lasthash = be32_to_cpu(btree[nodehdr.count - 1].hashval);
  1181. }
  1182. }
  1183. /*
  1184. * Remove an entry from an intermediate node.
  1185. */
  1186. STATIC void
  1187. xfs_da3_node_remove(
  1188. struct xfs_da_state *state,
  1189. struct xfs_da_state_blk *drop_blk)
  1190. {
  1191. struct xfs_da_intnode *node;
  1192. struct xfs_da3_icnode_hdr nodehdr;
  1193. struct xfs_da_node_entry *btree;
  1194. int index;
  1195. int tmp;
  1196. trace_xfs_da_node_remove(state->args);
  1197. node = drop_blk->bp->b_addr;
  1198. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  1199. ASSERT(drop_blk->index < nodehdr.count);
  1200. ASSERT(drop_blk->index >= 0);
  1201. /*
  1202. * Copy over the offending entry, or just zero it out.
  1203. */
  1204. index = drop_blk->index;
  1205. btree = xfs_da3_node_tree_p(node);
  1206. if (index < nodehdr.count - 1) {
  1207. tmp = nodehdr.count - index - 1;
  1208. tmp *= (uint)sizeof(xfs_da_node_entry_t);
  1209. memmove(&btree[index], &btree[index + 1], tmp);
  1210. xfs_trans_log_buf(state->args->trans, drop_blk->bp,
  1211. XFS_DA_LOGRANGE(node, &btree[index], tmp));
  1212. index = nodehdr.count - 1;
  1213. }
  1214. memset(&btree[index], 0, sizeof(xfs_da_node_entry_t));
  1215. xfs_trans_log_buf(state->args->trans, drop_blk->bp,
  1216. XFS_DA_LOGRANGE(node, &btree[index], sizeof(btree[index])));
  1217. nodehdr.count -= 1;
  1218. xfs_da3_node_hdr_to_disk(node, &nodehdr);
  1219. xfs_trans_log_buf(state->args->trans, drop_blk->bp,
  1220. XFS_DA_LOGRANGE(node, &node->hdr, xfs_da3_node_hdr_size(node)));
  1221. /*
  1222. * Copy the last hash value from the block to propagate upwards.
  1223. */
  1224. drop_blk->hashval = be32_to_cpu(btree[index - 1].hashval);
  1225. }
  1226. /*
  1227. * Unbalance the elements between two intermediate nodes,
  1228. * move all Btree elements from one node into another.
  1229. */
  1230. STATIC void
  1231. xfs_da3_node_unbalance(
  1232. struct xfs_da_state *state,
  1233. struct xfs_da_state_blk *drop_blk,
  1234. struct xfs_da_state_blk *save_blk)
  1235. {
  1236. struct xfs_da_intnode *drop_node;
  1237. struct xfs_da_intnode *save_node;
  1238. struct xfs_da_node_entry *drop_btree;
  1239. struct xfs_da_node_entry *save_btree;
  1240. struct xfs_da3_icnode_hdr drop_hdr;
  1241. struct xfs_da3_icnode_hdr save_hdr;
  1242. struct xfs_trans *tp;
  1243. int sindex;
  1244. int tmp;
  1245. trace_xfs_da_node_unbalance(state->args);
  1246. drop_node = drop_blk->bp->b_addr;
  1247. save_node = save_blk->bp->b_addr;
  1248. xfs_da3_node_hdr_from_disk(&drop_hdr, drop_node);
  1249. xfs_da3_node_hdr_from_disk(&save_hdr, save_node);
  1250. drop_btree = xfs_da3_node_tree_p(drop_node);
  1251. save_btree = xfs_da3_node_tree_p(save_node);
  1252. tp = state->args->trans;
  1253. /*
  1254. * If the dying block has lower hashvals, then move all the
  1255. * elements in the remaining block up to make a hole.
  1256. */
  1257. if ((be32_to_cpu(drop_btree[0].hashval) <
  1258. be32_to_cpu(save_btree[0].hashval)) ||
  1259. (be32_to_cpu(drop_btree[drop_hdr.count - 1].hashval) <
  1260. be32_to_cpu(save_btree[save_hdr.count - 1].hashval))) {
  1261. /* XXX: check this - is memmove dst correct? */
  1262. tmp = save_hdr.count * sizeof(xfs_da_node_entry_t);
  1263. memmove(&save_btree[drop_hdr.count], &save_btree[0], tmp);
  1264. sindex = 0;
  1265. xfs_trans_log_buf(tp, save_blk->bp,
  1266. XFS_DA_LOGRANGE(save_node, &save_btree[0],
  1267. (save_hdr.count + drop_hdr.count) *
  1268. sizeof(xfs_da_node_entry_t)));
  1269. } else {
  1270. sindex = save_hdr.count;
  1271. xfs_trans_log_buf(tp, save_blk->bp,
  1272. XFS_DA_LOGRANGE(save_node, &save_btree[sindex],
  1273. drop_hdr.count * sizeof(xfs_da_node_entry_t)));
  1274. }
  1275. /*
  1276. * Move all the B-tree elements from drop_blk to save_blk.
  1277. */
  1278. tmp = drop_hdr.count * (uint)sizeof(xfs_da_node_entry_t);
  1279. memcpy(&save_btree[sindex], &drop_btree[0], tmp);
  1280. save_hdr.count += drop_hdr.count;
  1281. xfs_da3_node_hdr_to_disk(save_node, &save_hdr);
  1282. xfs_trans_log_buf(tp, save_blk->bp,
  1283. XFS_DA_LOGRANGE(save_node, &save_node->hdr,
  1284. xfs_da3_node_hdr_size(save_node)));
  1285. /*
  1286. * Save the last hashval in the remaining block for upward propagation.
  1287. */
  1288. save_blk->hashval = be32_to_cpu(save_btree[save_hdr.count - 1].hashval);
  1289. }
  1290. /*========================================================================
  1291. * Routines used for finding things in the Btree.
  1292. *========================================================================*/
  1293. /*
  1294. * Walk down the Btree looking for a particular filename, filling
  1295. * in the state structure as we go.
  1296. *
  1297. * We will set the state structure to point to each of the elements
  1298. * in each of the nodes where either the hashval is or should be.
  1299. *
  1300. * We support duplicate hashval's so for each entry in the current
  1301. * node that could contain the desired hashval, descend. This is a
  1302. * pruned depth-first tree search.
  1303. */
  1304. int /* error */
  1305. xfs_da3_node_lookup_int(
  1306. struct xfs_da_state *state,
  1307. int *result)
  1308. {
  1309. struct xfs_da_state_blk *blk;
  1310. struct xfs_da_blkinfo *curr;
  1311. struct xfs_da_intnode *node;
  1312. struct xfs_da_node_entry *btree;
  1313. struct xfs_da3_icnode_hdr nodehdr;
  1314. struct xfs_da_args *args;
  1315. xfs_dablk_t blkno;
  1316. xfs_dahash_t hashval;
  1317. xfs_dahash_t btreehashval;
  1318. int probe;
  1319. int span;
  1320. int max;
  1321. int error;
  1322. int retval;
  1323. args = state->args;
  1324. /*
  1325. * Descend thru the B-tree searching each level for the right
  1326. * node to use, until the right hashval is found.
  1327. */
  1328. blkno = (args->whichfork == XFS_DATA_FORK)? state->mp->m_dirleafblk : 0;
  1329. for (blk = &state->path.blk[0], state->path.active = 1;
  1330. state->path.active <= XFS_DA_NODE_MAXDEPTH;
  1331. blk++, state->path.active++) {
  1332. /*
  1333. * Read the next node down in the tree.
  1334. */
  1335. blk->blkno = blkno;
  1336. error = xfs_da3_node_read(args->trans, args->dp, blkno,
  1337. -1, &blk->bp, args->whichfork);
  1338. if (error) {
  1339. blk->blkno = 0;
  1340. state->path.active--;
  1341. return(error);
  1342. }
  1343. curr = blk->bp->b_addr;
  1344. blk->magic = be16_to_cpu(curr->magic);
  1345. if (blk->magic == XFS_ATTR_LEAF_MAGIC ||
  1346. blk->magic == XFS_ATTR3_LEAF_MAGIC) {
  1347. blk->magic = XFS_ATTR_LEAF_MAGIC;
  1348. blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
  1349. break;
  1350. }
  1351. if (blk->magic == XFS_DIR2_LEAFN_MAGIC ||
  1352. blk->magic == XFS_DIR3_LEAFN_MAGIC) {
  1353. blk->magic = XFS_DIR2_LEAFN_MAGIC;
  1354. blk->hashval = xfs_dir2_leafn_lasthash(blk->bp, NULL);
  1355. break;
  1356. }
  1357. blk->magic = XFS_DA_NODE_MAGIC;
  1358. /*
  1359. * Search an intermediate node for a match.
  1360. */
  1361. node = blk->bp->b_addr;
  1362. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  1363. btree = xfs_da3_node_tree_p(node);
  1364. max = nodehdr.count;
  1365. blk->hashval = be32_to_cpu(btree[max - 1].hashval);
  1366. /*
  1367. * Binary search. (note: small blocks will skip loop)
  1368. */
  1369. probe = span = max / 2;
  1370. hashval = args->hashval;
  1371. while (span > 4) {
  1372. span /= 2;
  1373. btreehashval = be32_to_cpu(btree[probe].hashval);
  1374. if (btreehashval < hashval)
  1375. probe += span;
  1376. else if (btreehashval > hashval)
  1377. probe -= span;
  1378. else
  1379. break;
  1380. }
  1381. ASSERT((probe >= 0) && (probe < max));
  1382. ASSERT((span <= 4) ||
  1383. (be32_to_cpu(btree[probe].hashval) == hashval));
  1384. /*
  1385. * Since we may have duplicate hashval's, find the first
  1386. * matching hashval in the node.
  1387. */
  1388. while (probe > 0 &&
  1389. be32_to_cpu(btree[probe].hashval) >= hashval) {
  1390. probe--;
  1391. }
  1392. while (probe < max &&
  1393. be32_to_cpu(btree[probe].hashval) < hashval) {
  1394. probe++;
  1395. }
  1396. /*
  1397. * Pick the right block to descend on.
  1398. */
  1399. if (probe == max) {
  1400. blk->index = max - 1;
  1401. blkno = be32_to_cpu(btree[max - 1].before);
  1402. } else {
  1403. blk->index = probe;
  1404. blkno = be32_to_cpu(btree[probe].before);
  1405. }
  1406. }
  1407. /*
  1408. * A leaf block that ends in the hashval that we are interested in
  1409. * (final hashval == search hashval) means that the next block may
  1410. * contain more entries with the same hashval, shift upward to the
  1411. * next leaf and keep searching.
  1412. */
  1413. for (;;) {
  1414. if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
  1415. retval = xfs_dir2_leafn_lookup_int(blk->bp, args,
  1416. &blk->index, state);
  1417. } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
  1418. retval = xfs_attr3_leaf_lookup_int(blk->bp, args);
  1419. blk->index = args->index;
  1420. args->blkno = blk->blkno;
  1421. } else {
  1422. ASSERT(0);
  1423. return XFS_ERROR(EFSCORRUPTED);
  1424. }
  1425. if (((retval == ENOENT) || (retval == ENOATTR)) &&
  1426. (blk->hashval == args->hashval)) {
  1427. error = xfs_da3_path_shift(state, &state->path, 1, 1,
  1428. &retval);
  1429. if (error)
  1430. return(error);
  1431. if (retval == 0) {
  1432. continue;
  1433. } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
  1434. /* path_shift() gives ENOENT */
  1435. retval = XFS_ERROR(ENOATTR);
  1436. }
  1437. }
  1438. break;
  1439. }
  1440. *result = retval;
  1441. return(0);
  1442. }
  1443. /*========================================================================
  1444. * Utility routines.
  1445. *========================================================================*/
  1446. /*
  1447. * Compare two intermediate nodes for "order".
  1448. */
  1449. STATIC int
  1450. xfs_da3_node_order(
  1451. struct xfs_buf *node1_bp,
  1452. struct xfs_buf *node2_bp)
  1453. {
  1454. struct xfs_da_intnode *node1;
  1455. struct xfs_da_intnode *node2;
  1456. struct xfs_da_node_entry *btree1;
  1457. struct xfs_da_node_entry *btree2;
  1458. struct xfs_da3_icnode_hdr node1hdr;
  1459. struct xfs_da3_icnode_hdr node2hdr;
  1460. node1 = node1_bp->b_addr;
  1461. node2 = node2_bp->b_addr;
  1462. xfs_da3_node_hdr_from_disk(&node1hdr, node1);
  1463. xfs_da3_node_hdr_from_disk(&node2hdr, node2);
  1464. btree1 = xfs_da3_node_tree_p(node1);
  1465. btree2 = xfs_da3_node_tree_p(node2);
  1466. if (node1hdr.count > 0 && node2hdr.count > 0 &&
  1467. ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
  1468. (be32_to_cpu(btree2[node2hdr.count - 1].hashval) <
  1469. be32_to_cpu(btree1[node1hdr.count - 1].hashval)))) {
  1470. return 1;
  1471. }
  1472. return 0;
  1473. }
  1474. /*
  1475. * Link a new block into a doubly linked list of blocks (of whatever type).
  1476. */
  1477. int /* error */
  1478. xfs_da3_blk_link(
  1479. struct xfs_da_state *state,
  1480. struct xfs_da_state_blk *old_blk,
  1481. struct xfs_da_state_blk *new_blk)
  1482. {
  1483. struct xfs_da_blkinfo *old_info;
  1484. struct xfs_da_blkinfo *new_info;
  1485. struct xfs_da_blkinfo *tmp_info;
  1486. struct xfs_da_args *args;
  1487. struct xfs_buf *bp;
  1488. int before = 0;
  1489. int error;
  1490. /*
  1491. * Set up environment.
  1492. */
  1493. args = state->args;
  1494. ASSERT(args != NULL);
  1495. old_info = old_blk->bp->b_addr;
  1496. new_info = new_blk->bp->b_addr;
  1497. ASSERT(old_blk->magic == XFS_DA_NODE_MAGIC ||
  1498. old_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
  1499. old_blk->magic == XFS_ATTR_LEAF_MAGIC);
  1500. switch (old_blk->magic) {
  1501. case XFS_ATTR_LEAF_MAGIC:
  1502. before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);
  1503. break;
  1504. case XFS_DIR2_LEAFN_MAGIC:
  1505. before = xfs_dir2_leafn_order(old_blk->bp, new_blk->bp);
  1506. break;
  1507. case XFS_DA_NODE_MAGIC:
  1508. before = xfs_da3_node_order(old_blk->bp, new_blk->bp);
  1509. break;
  1510. }
  1511. /*
  1512. * Link blocks in appropriate order.
  1513. */
  1514. if (before) {
  1515. /*
  1516. * Link new block in before existing block.
  1517. */
  1518. trace_xfs_da_link_before(args);
  1519. new_info->forw = cpu_to_be32(old_blk->blkno);
  1520. new_info->back = old_info->back;
  1521. if (old_info->back) {
  1522. error = xfs_da3_node_read(args->trans, args->dp,
  1523. be32_to_cpu(old_info->back),
  1524. -1, &bp, args->whichfork);
  1525. if (error)
  1526. return(error);
  1527. ASSERT(bp != NULL);
  1528. tmp_info = bp->b_addr;
  1529. ASSERT(tmp_info->magic == old_info->magic);
  1530. ASSERT(be32_to_cpu(tmp_info->forw) == old_blk->blkno);
  1531. tmp_info->forw = cpu_to_be32(new_blk->blkno);
  1532. xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
  1533. }
  1534. old_info->back = cpu_to_be32(new_blk->blkno);
  1535. } else {
  1536. /*
  1537. * Link new block in after existing block.
  1538. */
  1539. trace_xfs_da_link_after(args);
  1540. new_info->forw = old_info->forw;
  1541. new_info->back = cpu_to_be32(old_blk->blkno);
  1542. if (old_info->forw) {
  1543. error = xfs_da3_node_read(args->trans, args->dp,
  1544. be32_to_cpu(old_info->forw),
  1545. -1, &bp, args->whichfork);
  1546. if (error)
  1547. return(error);
  1548. ASSERT(bp != NULL);
  1549. tmp_info = bp->b_addr;
  1550. ASSERT(tmp_info->magic == old_info->magic);
  1551. ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno);
  1552. tmp_info->back = cpu_to_be32(new_blk->blkno);
  1553. xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
  1554. }
  1555. old_info->forw = cpu_to_be32(new_blk->blkno);
  1556. }
  1557. xfs_trans_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);
  1558. xfs_trans_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);
  1559. return(0);
  1560. }
  1561. /*
  1562. * Unlink a block from a doubly linked list of blocks.
  1563. */
  1564. STATIC int /* error */
  1565. xfs_da3_blk_unlink(
  1566. struct xfs_da_state *state,
  1567. struct xfs_da_state_blk *drop_blk,
  1568. struct xfs_da_state_blk *save_blk)
  1569. {
  1570. struct xfs_da_blkinfo *drop_info;
  1571. struct xfs_da_blkinfo *save_info;
  1572. struct xfs_da_blkinfo *tmp_info;
  1573. struct xfs_da_args *args;
  1574. struct xfs_buf *bp;
  1575. int error;
  1576. /*
  1577. * Set up environment.
  1578. */
  1579. args = state->args;
  1580. ASSERT(args != NULL);
  1581. save_info = save_blk->bp->b_addr;
  1582. drop_info = drop_blk->bp->b_addr;
  1583. ASSERT(save_blk->magic == XFS_DA_NODE_MAGIC ||
  1584. save_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
  1585. save_blk->magic == XFS_ATTR_LEAF_MAGIC);
  1586. ASSERT(save_blk->magic == drop_blk->magic);
  1587. ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) ||
  1588. (be32_to_cpu(save_info->back) == drop_blk->blkno));
  1589. ASSERT((be32_to_cpu(drop_info->forw) == save_blk->blkno) ||
  1590. (be32_to_cpu(drop_info->back) == save_blk->blkno));
  1591. /*
  1592. * Unlink the leaf block from the doubly linked chain of leaves.
  1593. */
  1594. if (be32_to_cpu(save_info->back) == drop_blk->blkno) {
  1595. trace_xfs_da_unlink_back(args);
  1596. save_info->back = drop_info->back;
  1597. if (drop_info->back) {
  1598. error = xfs_da3_node_read(args->trans, args->dp,
  1599. be32_to_cpu(drop_info->back),
  1600. -1, &bp, args->whichfork);
  1601. if (error)
  1602. return(error);
  1603. ASSERT(bp != NULL);
  1604. tmp_info = bp->b_addr;
  1605. ASSERT(tmp_info->magic == save_info->magic);
  1606. ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno);
  1607. tmp_info->forw = cpu_to_be32(save_blk->blkno);
  1608. xfs_trans_log_buf(args->trans, bp, 0,
  1609. sizeof(*tmp_info) - 1);
  1610. }
  1611. } else {
  1612. trace_xfs_da_unlink_forward(args);
  1613. save_info->forw = drop_info->forw;
  1614. if (drop_info->forw) {
  1615. error = xfs_da3_node_read(args->trans, args->dp,
  1616. be32_to_cpu(drop_info->forw),
  1617. -1, &bp, args->whichfork);
  1618. if (error)
  1619. return(error);
  1620. ASSERT(bp != NULL);
  1621. tmp_info = bp->b_addr;
  1622. ASSERT(tmp_info->magic == save_info->magic);
  1623. ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno);
  1624. tmp_info->back = cpu_to_be32(save_blk->blkno);
  1625. xfs_trans_log_buf(args->trans, bp, 0,
  1626. sizeof(*tmp_info) - 1);
  1627. }
  1628. }
  1629. xfs_trans_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);
  1630. return(0);
  1631. }
  1632. /*
  1633. * Move a path "forward" or "!forward" one block at the current level.
  1634. *
  1635. * This routine will adjust a "path" to point to the next block
  1636. * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
  1637. * Btree, including updating pointers to the intermediate nodes between
  1638. * the new bottom and the root.
  1639. */
  1640. int /* error */
  1641. xfs_da3_path_shift(
  1642. struct xfs_da_state *state,
  1643. struct xfs_da_state_path *path,
  1644. int forward,
  1645. int release,
  1646. int *result)
  1647. {
  1648. struct xfs_da_state_blk *blk;
  1649. struct xfs_da_blkinfo *info;
  1650. struct xfs_da_intnode *node;
  1651. struct xfs_da_args *args;
  1652. struct xfs_da_node_entry *btree;
  1653. struct xfs_da3_icnode_hdr nodehdr;
  1654. xfs_dablk_t blkno = 0;
  1655. int level;
  1656. int error;
  1657. trace_xfs_da_path_shift(state->args);
  1658. /*
  1659. * Roll up the Btree looking for the first block where our
  1660. * current index is not at the edge of the block. Note that
  1661. * we skip the bottom layer because we want the sibling block.
  1662. */
  1663. args = state->args;
  1664. ASSERT(args != NULL);
  1665. ASSERT(path != NULL);
  1666. ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));
  1667. level = (path->active-1) - 1; /* skip bottom layer in path */
  1668. for (blk = &path->blk[level]; level >= 0; blk--, level--) {
  1669. node = blk->bp->b_addr;
  1670. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  1671. btree = xfs_da3_node_tree_p(node);
  1672. if (forward && (blk->index < nodehdr.count - 1)) {
  1673. blk->index++;
  1674. blkno = be32_to_cpu(btree[blk->index].before);
  1675. break;
  1676. } else if (!forward && (blk->index > 0)) {
  1677. blk->index--;
  1678. blkno = be32_to_cpu(btree[blk->index].before);
  1679. break;
  1680. }
  1681. }
  1682. if (level < 0) {
  1683. *result = XFS_ERROR(ENOENT); /* we're out of our tree */
  1684. ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
  1685. return(0);
  1686. }
  1687. /*
  1688. * Roll down the edge of the subtree until we reach the
  1689. * same depth we were at originally.
  1690. */
  1691. for (blk++, level++; level < path->active; blk++, level++) {
  1692. /*
  1693. * Release the old block.
  1694. * (if it's dirty, trans won't actually let go)
  1695. */
  1696. if (release)
  1697. xfs_trans_brelse(args->trans, blk->bp);
  1698. /*
  1699. * Read the next child block.
  1700. */
  1701. blk->blkno = blkno;
  1702. error = xfs_da3_node_read(args->trans, args->dp, blkno, -1,
  1703. &blk->bp, args->whichfork);
  1704. if (error)
  1705. return(error);
  1706. info = blk->bp->b_addr;
  1707. ASSERT(info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
  1708. info->magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||
  1709. info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  1710. info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
  1711. info->magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
  1712. info->magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
  1713. /*
  1714. * Note: we flatten the magic number to a single type so we
  1715. * don't have to compare against crc/non-crc types elsewhere.
  1716. */
  1717. switch (be16_to_cpu(info->magic)) {
  1718. case XFS_DA_NODE_MAGIC:
  1719. case XFS_DA3_NODE_MAGIC:
  1720. blk->magic = XFS_DA_NODE_MAGIC;
  1721. node = (xfs_da_intnode_t *)info;
  1722. xfs_da3_node_hdr_from_disk(&nodehdr, node);
  1723. btree = xfs_da3_node_tree_p(node);
  1724. blk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
  1725. if (forward)
  1726. blk->index = 0;
  1727. else
  1728. blk->index = nodehdr.count - 1;
  1729. blkno = be32_to_cpu(btree[blk->index].before);
  1730. break;
  1731. case XFS_ATTR_LEAF_MAGIC:
  1732. case XFS_ATTR3_LEAF_MAGIC:
  1733. blk->magic = XFS_ATTR_LEAF_MAGIC;
  1734. ASSERT(level == path->active-1);
  1735. blk->index = 0;
  1736. blk->hashval = xfs_attr_leaf_lasthash(blk->bp,
  1737. NULL);
  1738. break;
  1739. case XFS_DIR2_LEAFN_MAGIC:
  1740. case XFS_DIR3_LEAFN_MAGIC:
  1741. blk->magic = XFS_DIR2_LEAFN_MAGIC;
  1742. ASSERT(level == path->active-1);
  1743. blk->index = 0;
  1744. blk->hashval = xfs_dir2_leafn_lasthash(blk->bp,
  1745. NULL);
  1746. break;
  1747. default:
  1748. ASSERT(0);
  1749. break;
  1750. }
  1751. }
  1752. *result = 0;
  1753. return 0;
  1754. }
  1755. /*========================================================================
  1756. * Utility routines.
  1757. *========================================================================*/
  1758. /*
  1759. * Implement a simple hash on a character string.
  1760. * Rotate the hash value by 7 bits, then XOR each character in.
  1761. * This is implemented with some source-level loop unrolling.
  1762. */
  1763. xfs_dahash_t
  1764. xfs_da_hashname(const __uint8_t *name, int namelen)
  1765. {
  1766. xfs_dahash_t hash;
  1767. /*
  1768. * Do four characters at a time as long as we can.
  1769. */
  1770. for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
  1771. hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
  1772. (name[3] << 0) ^ rol32(hash, 7 * 4);
  1773. /*
  1774. * Now do the rest of the characters.
  1775. */
  1776. switch (namelen) {
  1777. case 3:
  1778. return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
  1779. rol32(hash, 7 * 3);
  1780. case 2:
  1781. return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
  1782. case 1:
  1783. return (name[0] << 0) ^ rol32(hash, 7 * 1);
  1784. default: /* case 0: */
  1785. return hash;
  1786. }
  1787. }
  1788. enum xfs_dacmp
  1789. xfs_da_compname(
  1790. struct xfs_da_args *args,
  1791. const unsigned char *name,
  1792. int len)
  1793. {
  1794. return (args->namelen == len && memcmp(args->name, name, len) == 0) ?
  1795. XFS_CMP_EXACT : XFS_CMP_DIFFERENT;
  1796. }
  1797. static xfs_dahash_t
  1798. xfs_default_hashname(
  1799. struct xfs_name *name)
  1800. {
  1801. return xfs_da_hashname(name->name, name->len);
  1802. }
  1803. const struct xfs_nameops xfs_default_nameops = {
  1804. .hashname = xfs_default_hashname,
  1805. .compname = xfs_da_compname
  1806. };
  1807. int
  1808. xfs_da_grow_inode_int(
  1809. struct xfs_da_args *args,
  1810. xfs_fileoff_t *bno,
  1811. int count)
  1812. {
  1813. struct xfs_trans *tp = args->trans;
  1814. struct xfs_inode *dp = args->dp;
  1815. int w = args->whichfork;
  1816. xfs_drfsbno_t nblks = dp->i_d.di_nblocks;
  1817. struct xfs_bmbt_irec map, *mapp;
  1818. int nmap, error, got, i, mapi;
  1819. /*
  1820. * Find a spot in the file space to put the new block.
  1821. */
  1822. error = xfs_bmap_first_unused(tp, dp, count, bno, w);
  1823. if (error)
  1824. return error;
  1825. /*
  1826. * Try mapping it in one filesystem block.
  1827. */
  1828. nmap = 1;
  1829. ASSERT(args->firstblock != NULL);
  1830. error = xfs_bmapi_write(tp, dp, *bno, count,
  1831. xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA|XFS_BMAPI_CONTIG,
  1832. args->firstblock, args->total, &map, &nmap,
  1833. args->flist);
  1834. if (error)
  1835. return error;
  1836. ASSERT(nmap <= 1);
  1837. if (nmap == 1) {
  1838. mapp = &map;
  1839. mapi = 1;
  1840. } else if (nmap == 0 && count > 1) {
  1841. xfs_fileoff_t b;
  1842. int c;
  1843. /*
  1844. * If we didn't get it and the block might work if fragmented,
  1845. * try without the CONTIG flag. Loop until we get it all.
  1846. */
  1847. mapp = kmem_alloc(sizeof(*mapp) * count, KM_SLEEP);
  1848. for (b = *bno, mapi = 0; b < *bno + count; ) {
  1849. nmap = MIN(XFS_BMAP_MAX_NMAP, count);
  1850. c = (int)(*bno + count - b);
  1851. error = xfs_bmapi_write(tp, dp, b, c,
  1852. xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
  1853. args->firstblock, args->total,
  1854. &mapp[mapi], &nmap, args->flist);
  1855. if (error)
  1856. goto out_free_map;
  1857. if (nmap < 1)
  1858. break;
  1859. mapi += nmap;
  1860. b = mapp[mapi - 1].br_startoff +
  1861. mapp[mapi - 1].br_blockcount;
  1862. }
  1863. } else {
  1864. mapi = 0;
  1865. mapp = NULL;
  1866. }
  1867. /*
  1868. * Count the blocks we got, make sure it matches the total.
  1869. */
  1870. for (i = 0, got = 0; i < mapi; i++)
  1871. got += mapp[i].br_blockcount;
  1872. if (got != count || mapp[0].br_startoff != *bno ||
  1873. mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
  1874. *bno + count) {
  1875. error = XFS_ERROR(ENOSPC);
  1876. goto out_free_map;
  1877. }
  1878. /* account for newly allocated blocks in reserved blocks total */
  1879. args->total -= dp->i_d.di_nblocks - nblks;
  1880. out_free_map:
  1881. if (mapp != &map)
  1882. kmem_free(mapp);
  1883. return error;
  1884. }
  1885. /*
  1886. * Add a block to the btree ahead of the file.
  1887. * Return the new block number to the caller.
  1888. */
  1889. int
  1890. xfs_da_grow_inode(
  1891. struct xfs_da_args *args,
  1892. xfs_dablk_t *new_blkno)
  1893. {
  1894. xfs_fileoff_t bno;
  1895. int count;
  1896. int error;
  1897. trace_xfs_da_grow_inode(args);
  1898. if (args->whichfork == XFS_DATA_FORK) {
  1899. bno = args->dp->i_mount->m_dirleafblk;
  1900. count = args->dp->i_mount->m_dirblkfsbs;
  1901. } else {
  1902. bno = 0;
  1903. count = 1;
  1904. }
  1905. error = xfs_da_grow_inode_int(args, &bno, count);
  1906. if (!error)
  1907. *new_blkno = (xfs_dablk_t)bno;
  1908. return error;
  1909. }
  1910. /*
  1911. * Ick. We need to always be able to remove a btree block, even
  1912. * if there's no space reservation because the filesystem is full.
  1913. * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
  1914. * It swaps the target block with the last block in the file. The
  1915. * last block in the file can always be removed since it can't cause
  1916. * a bmap btree split to do that.
  1917. */
  1918. STATIC int
  1919. xfs_da3_swap_lastblock(
  1920. struct xfs_da_args *args,
  1921. xfs_dablk_t *dead_blknop,
  1922. struct xfs_buf **dead_bufp)
  1923. {
  1924. struct xfs_da_blkinfo *dead_info;
  1925. struct xfs_da_blkinfo *sib_info;
  1926. struct xfs_da_intnode *par_node;
  1927. struct xfs_da_intnode *dead_node;
  1928. struct xfs_dir2_leaf *dead_leaf2;
  1929. struct xfs_da_node_entry *btree;
  1930. struct xfs_da3_icnode_hdr par_hdr;
  1931. struct xfs_inode *ip;
  1932. struct xfs_trans *tp;
  1933. struct xfs_mount *mp;
  1934. struct xfs_buf *dead_buf;
  1935. struct xfs_buf *last_buf;
  1936. struct xfs_buf *sib_buf;
  1937. struct xfs_buf *par_buf;
  1938. xfs_dahash_t dead_hash;
  1939. xfs_fileoff_t lastoff;
  1940. xfs_dablk_t dead_blkno;
  1941. xfs_dablk_t last_blkno;
  1942. xfs_dablk_t sib_blkno;
  1943. xfs_dablk_t par_blkno;
  1944. int error;
  1945. int w;
  1946. int entno;
  1947. int level;
  1948. int dead_level;
  1949. trace_xfs_da_swap_lastblock(args);
  1950. dead_buf = *dead_bufp;
  1951. dead_blkno = *dead_blknop;
  1952. tp = args->trans;
  1953. ip = args->dp;
  1954. w = args->whichfork;
  1955. ASSERT(w == XFS_DATA_FORK);
  1956. mp = ip->i_mount;
  1957. lastoff = mp->m_dirfreeblk;
  1958. error = xfs_bmap_last_before(tp, ip, &lastoff, w);
  1959. if (error)
  1960. return error;
  1961. if (unlikely(lastoff == 0)) {
  1962. XFS_ERROR_REPORT("xfs_da_swap_lastblock(1)", XFS_ERRLEVEL_LOW,
  1963. mp);
  1964. return XFS_ERROR(EFSCORRUPTED);
  1965. }
  1966. /*
  1967. * Read the last block in the btree space.
  1968. */
  1969. last_blkno = (xfs_dablk_t)lastoff - mp->m_dirblkfsbs;
  1970. error = xfs_da3_node_read(tp, ip, last_blkno, -1, &last_buf, w);
  1971. if (error)
  1972. return error;
  1973. /*
  1974. * Copy the last block into the dead buffer and log it.
  1975. */
  1976. memcpy(dead_buf->b_addr, last_buf->b_addr, mp->m_dirblksize);
  1977. xfs_trans_log_buf(tp, dead_buf, 0, mp->m_dirblksize - 1);
  1978. dead_info = dead_buf->b_addr;
  1979. /*
  1980. * Get values from the moved block.
  1981. */
  1982. if (dead_info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  1983. dead_info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
  1984. struct xfs_dir3_icleaf_hdr leafhdr;
  1985. struct xfs_dir2_leaf_entry *ents;
  1986. dead_leaf2 = (xfs_dir2_leaf_t *)dead_info;
  1987. xfs_dir3_leaf_hdr_from_disk(&leafhdr, dead_leaf2);
  1988. ents = xfs_dir3_leaf_ents_p(dead_leaf2);
  1989. dead_level = 0;
  1990. dead_hash = be32_to_cpu(ents[leafhdr.count - 1].hashval);
  1991. } else {
  1992. struct xfs_da3_icnode_hdr deadhdr;
  1993. dead_node = (xfs_da_intnode_t *)dead_info;
  1994. xfs_da3_node_hdr_from_disk(&deadhdr, dead_node);
  1995. btree = xfs_da3_node_tree_p(dead_node);
  1996. dead_level = deadhdr.level;
  1997. dead_hash = be32_to_cpu(btree[deadhdr.count - 1].hashval);
  1998. }
  1999. sib_buf = par_buf = NULL;
  2000. /*
  2001. * If the moved block has a left sibling, fix up the pointers.
  2002. */
  2003. if ((sib_blkno = be32_to_cpu(dead_info->back))) {
  2004. error = xfs_da3_node_read(tp, ip, sib_blkno, -1, &sib_buf, w);
  2005. if (error)
  2006. goto done;
  2007. sib_info = sib_buf->b_addr;
  2008. if (unlikely(
  2009. be32_to_cpu(sib_info->forw) != last_blkno ||
  2010. sib_info->magic != dead_info->magic)) {
  2011. XFS_ERROR_REPORT("xfs_da_swap_lastblock(2)",
  2012. XFS_ERRLEVEL_LOW, mp);
  2013. error = XFS_ERROR(EFSCORRUPTED);
  2014. goto done;
  2015. }
  2016. sib_info->forw = cpu_to_be32(dead_blkno);
  2017. xfs_trans_log_buf(tp, sib_buf,
  2018. XFS_DA_LOGRANGE(sib_info, &sib_info->forw,
  2019. sizeof(sib_info->forw)));
  2020. sib_buf = NULL;
  2021. }
  2022. /*
  2023. * If the moved block has a right sibling, fix up the pointers.
  2024. */
  2025. if ((sib_blkno = be32_to_cpu(dead_info->forw))) {
  2026. error = xfs_da3_node_read(tp, ip, sib_blkno, -1, &sib_buf, w);
  2027. if (error)
  2028. goto done;
  2029. sib_info = sib_buf->b_addr;
  2030. if (unlikely(
  2031. be32_to_cpu(sib_info->back) != last_blkno ||
  2032. sib_info->magic != dead_info->magic)) {
  2033. XFS_ERROR_REPORT("xfs_da_swap_lastblock(3)",
  2034. XFS_ERRLEVEL_LOW, mp);
  2035. error = XFS_ERROR(EFSCORRUPTED);
  2036. goto done;
  2037. }
  2038. sib_info->back = cpu_to_be32(dead_blkno);
  2039. xfs_trans_log_buf(tp, sib_buf,
  2040. XFS_DA_LOGRANGE(sib_info, &sib_info->back,
  2041. sizeof(sib_info->back)));
  2042. sib_buf = NULL;
  2043. }
  2044. par_blkno = mp->m_dirleafblk;
  2045. level = -1;
  2046. /*
  2047. * Walk down the tree looking for the parent of the moved block.
  2048. */
  2049. for (;;) {
  2050. error = xfs_da3_node_read(tp, ip, par_blkno, -1, &par_buf, w);
  2051. if (error)
  2052. goto done;
  2053. par_node = par_buf->b_addr;
  2054. xfs_da3_node_hdr_from_disk(&par_hdr, par_node);
  2055. if (level >= 0 && level != par_hdr.level + 1) {
  2056. XFS_ERROR_REPORT("xfs_da_swap_lastblock(4)",
  2057. XFS_ERRLEVEL_LOW, mp);
  2058. error = XFS_ERROR(EFSCORRUPTED);
  2059. goto done;
  2060. }
  2061. level = par_hdr.level;
  2062. btree = xfs_da3_node_tree_p(par_node);
  2063. for (entno = 0;
  2064. entno < par_hdr.count &&
  2065. be32_to_cpu(btree[entno].hashval) < dead_hash;
  2066. entno++)
  2067. continue;
  2068. if (entno == par_hdr.count) {
  2069. XFS_ERROR_REPORT("xfs_da_swap_lastblock(5)",
  2070. XFS_ERRLEVEL_LOW, mp);
  2071. error = XFS_ERROR(EFSCORRUPTED);
  2072. goto done;
  2073. }
  2074. par_blkno = be32_to_cpu(btree[entno].before);
  2075. if (level == dead_level + 1)
  2076. break;
  2077. xfs_trans_brelse(tp, par_buf);
  2078. par_buf = NULL;
  2079. }
  2080. /*
  2081. * We're in the right parent block.
  2082. * Look for the right entry.
  2083. */
  2084. for (;;) {
  2085. for (;
  2086. entno < par_hdr.count &&
  2087. be32_to_cpu(btree[entno].before) != last_blkno;
  2088. entno++)
  2089. continue;
  2090. if (entno < par_hdr.count)
  2091. break;
  2092. par_blkno = par_hdr.forw;
  2093. xfs_trans_brelse(tp, par_buf);
  2094. par_buf = NULL;
  2095. if (unlikely(par_blkno == 0)) {
  2096. XFS_ERROR_REPORT("xfs_da_swap_lastblock(6)",
  2097. XFS_ERRLEVEL_LOW, mp);
  2098. error = XFS_ERROR(EFSCORRUPTED);
  2099. goto done;
  2100. }
  2101. error = xfs_da3_node_read(tp, ip, par_blkno, -1, &par_buf, w);
  2102. if (error)
  2103. goto done;
  2104. par_node = par_buf->b_addr;
  2105. xfs_da3_node_hdr_from_disk(&par_hdr, par_node);
  2106. if (par_hdr.level != level) {
  2107. XFS_ERROR_REPORT("xfs_da_swap_lastblock(7)",
  2108. XFS_ERRLEVEL_LOW, mp);
  2109. error = XFS_ERROR(EFSCORRUPTED);
  2110. goto done;
  2111. }
  2112. btree = xfs_da3_node_tree_p(par_node);
  2113. entno = 0;
  2114. }
  2115. /*
  2116. * Update the parent entry pointing to the moved block.
  2117. */
  2118. btree[entno].before = cpu_to_be32(dead_blkno);
  2119. xfs_trans_log_buf(tp, par_buf,
  2120. XFS_DA_LOGRANGE(par_node, &btree[entno].before,
  2121. sizeof(btree[entno].before)));
  2122. *dead_blknop = last_blkno;
  2123. *dead_bufp = last_buf;
  2124. return 0;
  2125. done:
  2126. if (par_buf)
  2127. xfs_trans_brelse(tp, par_buf);
  2128. if (sib_buf)
  2129. xfs_trans_brelse(tp, sib_buf);
  2130. xfs_trans_brelse(tp, last_buf);
  2131. return error;
  2132. }
  2133. /*
  2134. * Remove a btree block from a directory or attribute.
  2135. */
  2136. int
  2137. xfs_da_shrink_inode(
  2138. xfs_da_args_t *args,
  2139. xfs_dablk_t dead_blkno,
  2140. struct xfs_buf *dead_buf)
  2141. {
  2142. xfs_inode_t *dp;
  2143. int done, error, w, count;
  2144. xfs_trans_t *tp;
  2145. xfs_mount_t *mp;
  2146. trace_xfs_da_shrink_inode(args);
  2147. dp = args->dp;
  2148. w = args->whichfork;
  2149. tp = args->trans;
  2150. mp = dp->i_mount;
  2151. if (w == XFS_DATA_FORK)
  2152. count = mp->m_dirblkfsbs;
  2153. else
  2154. count = 1;
  2155. for (;;) {
  2156. /*
  2157. * Remove extents. If we get ENOSPC for a dir we have to move
  2158. * the last block to the place we want to kill.
  2159. */
  2160. error = xfs_bunmapi(tp, dp, dead_blkno, count,
  2161. xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
  2162. 0, args->firstblock, args->flist, &done);
  2163. if (error == ENOSPC) {
  2164. if (w != XFS_DATA_FORK)
  2165. break;
  2166. error = xfs_da3_swap_lastblock(args, &dead_blkno,
  2167. &dead_buf);
  2168. if (error)
  2169. break;
  2170. } else {
  2171. break;
  2172. }
  2173. }
  2174. xfs_trans_binval(tp, dead_buf);
  2175. return error;
  2176. }
  2177. /*
  2178. * See if the mapping(s) for this btree block are valid, i.e.
  2179. * don't contain holes, are logically contiguous, and cover the whole range.
  2180. */
  2181. STATIC int
  2182. xfs_da_map_covers_blocks(
  2183. int nmap,
  2184. xfs_bmbt_irec_t *mapp,
  2185. xfs_dablk_t bno,
  2186. int count)
  2187. {
  2188. int i;
  2189. xfs_fileoff_t off;
  2190. for (i = 0, off = bno; i < nmap; i++) {
  2191. if (mapp[i].br_startblock == HOLESTARTBLOCK ||
  2192. mapp[i].br_startblock == DELAYSTARTBLOCK) {
  2193. return 0;
  2194. }
  2195. if (off != mapp[i].br_startoff) {
  2196. return 0;
  2197. }
  2198. off += mapp[i].br_blockcount;
  2199. }
  2200. return off == bno + count;
  2201. }
  2202. /*
  2203. * Convert a struct xfs_bmbt_irec to a struct xfs_buf_map.
  2204. *
  2205. * For the single map case, it is assumed that the caller has provided a pointer
  2206. * to a valid xfs_buf_map. For the multiple map case, this function will
  2207. * allocate the xfs_buf_map to hold all the maps and replace the caller's single
  2208. * map pointer with the allocated map.
  2209. */
  2210. static int
  2211. xfs_buf_map_from_irec(
  2212. struct xfs_mount *mp,
  2213. struct xfs_buf_map **mapp,
  2214. unsigned int *nmaps,
  2215. struct xfs_bmbt_irec *irecs,
  2216. unsigned int nirecs)
  2217. {
  2218. struct xfs_buf_map *map;
  2219. int i;
  2220. ASSERT(*nmaps == 1);
  2221. ASSERT(nirecs >= 1);
  2222. if (nirecs > 1) {
  2223. map = kmem_zalloc(nirecs * sizeof(struct xfs_buf_map), KM_SLEEP);
  2224. if (!map)
  2225. return ENOMEM;
  2226. *mapp = map;
  2227. }
  2228. *nmaps = nirecs;
  2229. map = *mapp;
  2230. for (i = 0; i < *nmaps; i++) {
  2231. ASSERT(irecs[i].br_startblock != DELAYSTARTBLOCK &&
  2232. irecs[i].br_startblock != HOLESTARTBLOCK);
  2233. map[i].bm_bn = XFS_FSB_TO_DADDR(mp, irecs[i].br_startblock);
  2234. map[i].bm_len = XFS_FSB_TO_BB(mp, irecs[i].br_blockcount);
  2235. }
  2236. return 0;
  2237. }
  2238. /*
  2239. * Map the block we are given ready for reading. There are three possible return
  2240. * values:
  2241. * -1 - will be returned if we land in a hole and mappedbno == -2 so the
  2242. * caller knows not to execute a subsequent read.
  2243. * 0 - if we mapped the block successfully
  2244. * >0 - positive error number if there was an error.
  2245. */
  2246. static int
  2247. xfs_dabuf_map(
  2248. struct xfs_trans *trans,
  2249. struct xfs_inode *dp,
  2250. xfs_dablk_t bno,
  2251. xfs_daddr_t mappedbno,
  2252. int whichfork,
  2253. struct xfs_buf_map **map,
  2254. int *nmaps)
  2255. {
  2256. struct xfs_mount *mp = dp->i_mount;
  2257. int nfsb;
  2258. int error = 0;
  2259. struct xfs_bmbt_irec irec;
  2260. struct xfs_bmbt_irec *irecs = &irec;
  2261. int nirecs;
  2262. ASSERT(map && *map);
  2263. ASSERT(*nmaps == 1);
  2264. nfsb = (whichfork == XFS_DATA_FORK) ? mp->m_dirblkfsbs : 1;
  2265. /*
  2266. * Caller doesn't have a mapping. -2 means don't complain
  2267. * if we land in a hole.
  2268. */
  2269. if (mappedbno == -1 || mappedbno == -2) {
  2270. /*
  2271. * Optimize the one-block case.
  2272. */
  2273. if (nfsb != 1)
  2274. irecs = kmem_zalloc(sizeof(irec) * nfsb, KM_SLEEP);
  2275. nirecs = nfsb;
  2276. error = xfs_bmapi_read(dp, (xfs_fileoff_t)bno, nfsb, irecs,
  2277. &nirecs, xfs_bmapi_aflag(whichfork));
  2278. if (error)
  2279. goto out;
  2280. } else {
  2281. irecs->br_startblock = XFS_DADDR_TO_FSB(mp, mappedbno);
  2282. irecs->br_startoff = (xfs_fileoff_t)bno;
  2283. irecs->br_blockcount = nfsb;
  2284. irecs->br_state = 0;
  2285. nirecs = 1;
  2286. }
  2287. if (!xfs_da_map_covers_blocks(nirecs, irecs, bno, nfsb)) {
  2288. error = mappedbno == -2 ? -1 : XFS_ERROR(EFSCORRUPTED);
  2289. if (unlikely(error == EFSCORRUPTED)) {
  2290. if (xfs_error_level >= XFS_ERRLEVEL_LOW) {
  2291. int i;
  2292. xfs_alert(mp, "%s: bno %lld dir: inode %lld",
  2293. __func__, (long long)bno,
  2294. (long long)dp->i_ino);
  2295. for (i = 0; i < *nmaps; i++) {
  2296. xfs_alert(mp,
  2297. "[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d",
  2298. i,
  2299. (long long)irecs[i].br_startoff,
  2300. (long long)irecs[i].br_startblock,
  2301. (long long)irecs[i].br_blockcount,
  2302. irecs[i].br_state);
  2303. }
  2304. }
  2305. XFS_ERROR_REPORT("xfs_da_do_buf(1)",
  2306. XFS_ERRLEVEL_LOW, mp);
  2307. }
  2308. goto out;
  2309. }
  2310. error = xfs_buf_map_from_irec(mp, map, nmaps, irecs, nirecs);
  2311. out:
  2312. if (irecs != &irec)
  2313. kmem_free(irecs);
  2314. return error;
  2315. }
  2316. /*
  2317. * Get a buffer for the dir/attr block.
  2318. */
  2319. int
  2320. xfs_da_get_buf(
  2321. struct xfs_trans *trans,
  2322. struct xfs_inode *dp,
  2323. xfs_dablk_t bno,
  2324. xfs_daddr_t mappedbno,
  2325. struct xfs_buf **bpp,
  2326. int whichfork)
  2327. {
  2328. struct xfs_buf *bp;
  2329. struct xfs_buf_map map;
  2330. struct xfs_buf_map *mapp;
  2331. int nmap;
  2332. int error;
  2333. *bpp = NULL;
  2334. mapp = &map;
  2335. nmap = 1;
  2336. error = xfs_dabuf_map(trans, dp, bno, mappedbno, whichfork,
  2337. &mapp, &nmap);
  2338. if (error) {
  2339. /* mapping a hole is not an error, but we don't continue */
  2340. if (error == -1)
  2341. error = 0;
  2342. goto out_free;
  2343. }
  2344. bp = xfs_trans_get_buf_map(trans, dp->i_mount->m_ddev_targp,
  2345. mapp, nmap, 0);
  2346. error = bp ? bp->b_error : XFS_ERROR(EIO);
  2347. if (error) {
  2348. xfs_trans_brelse(trans, bp);
  2349. goto out_free;
  2350. }
  2351. *bpp = bp;
  2352. out_free:
  2353. if (mapp != &map)
  2354. kmem_free(mapp);
  2355. return error;
  2356. }
  2357. /*
  2358. * Get a buffer for the dir/attr block, fill in the contents.
  2359. */
  2360. int
  2361. xfs_da_read_buf(
  2362. struct xfs_trans *trans,
  2363. struct xfs_inode *dp,
  2364. xfs_dablk_t bno,
  2365. xfs_daddr_t mappedbno,
  2366. struct xfs_buf **bpp,
  2367. int whichfork,
  2368. const struct xfs_buf_ops *ops)
  2369. {
  2370. struct xfs_buf *bp;
  2371. struct xfs_buf_map map;
  2372. struct xfs_buf_map *mapp;
  2373. int nmap;
  2374. int error;
  2375. *bpp = NULL;
  2376. mapp = &map;
  2377. nmap = 1;
  2378. error = xfs_dabuf_map(trans, dp, bno, mappedbno, whichfork,
  2379. &mapp, &nmap);
  2380. if (error) {
  2381. /* mapping a hole is not an error, but we don't continue */
  2382. if (error == -1)
  2383. error = 0;
  2384. goto out_free;
  2385. }
  2386. error = xfs_trans_read_buf_map(dp->i_mount, trans,
  2387. dp->i_mount->m_ddev_targp,
  2388. mapp, nmap, 0, &bp, ops);
  2389. if (error)
  2390. goto out_free;
  2391. if (whichfork == XFS_ATTR_FORK)
  2392. xfs_buf_set_ref(bp, XFS_ATTR_BTREE_REF);
  2393. else
  2394. xfs_buf_set_ref(bp, XFS_DIR_BTREE_REF);
  2395. /*
  2396. * This verification code will be moved to a CRC verification callback
  2397. * function so just leave it here unchanged until then.
  2398. */
  2399. {
  2400. xfs_dir2_data_hdr_t *hdr = bp->b_addr;
  2401. xfs_dir2_free_t *free = bp->b_addr;
  2402. xfs_da_blkinfo_t *info = bp->b_addr;
  2403. uint magic, magic1;
  2404. struct xfs_mount *mp = dp->i_mount;
  2405. magic = be16_to_cpu(info->magic);
  2406. magic1 = be32_to_cpu(hdr->magic);
  2407. if (unlikely(
  2408. XFS_TEST_ERROR((magic != XFS_DA_NODE_MAGIC) &&
  2409. (magic != XFS_DA3_NODE_MAGIC) &&
  2410. (magic != XFS_ATTR_LEAF_MAGIC) &&
  2411. (magic != XFS_ATTR3_LEAF_MAGIC) &&
  2412. (magic != XFS_DIR2_LEAF1_MAGIC) &&
  2413. (magic != XFS_DIR3_LEAF1_MAGIC) &&
  2414. (magic != XFS_DIR2_LEAFN_MAGIC) &&
  2415. (magic != XFS_DIR3_LEAFN_MAGIC) &&
  2416. (magic1 != XFS_DIR2_BLOCK_MAGIC) &&
  2417. (magic1 != XFS_DIR3_BLOCK_MAGIC) &&
  2418. (magic1 != XFS_DIR2_DATA_MAGIC) &&
  2419. (magic1 != XFS_DIR3_DATA_MAGIC) &&
  2420. (free->hdr.magic !=
  2421. cpu_to_be32(XFS_DIR2_FREE_MAGIC)) &&
  2422. (free->hdr.magic !=
  2423. cpu_to_be32(XFS_DIR3_FREE_MAGIC)),
  2424. mp, XFS_ERRTAG_DA_READ_BUF,
  2425. XFS_RANDOM_DA_READ_BUF))) {
  2426. trace_xfs_da_btree_corrupt(bp, _RET_IP_);
  2427. XFS_CORRUPTION_ERROR("xfs_da_do_buf(2)",
  2428. XFS_ERRLEVEL_LOW, mp, info);
  2429. error = XFS_ERROR(EFSCORRUPTED);
  2430. xfs_trans_brelse(trans, bp);
  2431. goto out_free;
  2432. }
  2433. }
  2434. *bpp = bp;
  2435. out_free:
  2436. if (mapp != &map)
  2437. kmem_free(mapp);
  2438. return error;
  2439. }
  2440. /*
  2441. * Readahead the dir/attr block.
  2442. */
  2443. xfs_daddr_t
  2444. xfs_da_reada_buf(
  2445. struct xfs_trans *trans,
  2446. struct xfs_inode *dp,
  2447. xfs_dablk_t bno,
  2448. xfs_daddr_t mappedbno,
  2449. int whichfork,
  2450. const struct xfs_buf_ops *ops)
  2451. {
  2452. struct xfs_buf_map map;
  2453. struct xfs_buf_map *mapp;
  2454. int nmap;
  2455. int error;
  2456. mapp = &map;
  2457. nmap = 1;
  2458. error = xfs_dabuf_map(trans, dp, bno, mappedbno, whichfork,
  2459. &mapp, &nmap);
  2460. if (error) {
  2461. /* mapping a hole is not an error, but we don't continue */
  2462. if (error == -1)
  2463. error = 0;
  2464. goto out_free;
  2465. }
  2466. mappedbno = mapp[0].bm_bn;
  2467. xfs_buf_readahead_map(dp->i_mount->m_ddev_targp, mapp, nmap, ops);
  2468. out_free:
  2469. if (mapp != &map)
  2470. kmem_free(mapp);
  2471. if (error)
  2472. return -1;
  2473. return mappedbno;
  2474. }