xfs_da_btree.c 66 KB

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