xfs_dir2_leaf.c 53 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875
  1. /*
  2. * Copyright (c) 2000-2003,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_attr_sf.h"
  33. #include "xfs_dir2_sf.h"
  34. #include "xfs_dinode.h"
  35. #include "xfs_inode.h"
  36. #include "xfs_bmap.h"
  37. #include "xfs_dir2_data.h"
  38. #include "xfs_dir2_leaf.h"
  39. #include "xfs_dir2_block.h"
  40. #include "xfs_dir2_node.h"
  41. #include "xfs_dir2_trace.h"
  42. #include "xfs_error.h"
  43. /*
  44. * Local function declarations.
  45. */
  46. #ifdef DEBUG
  47. static void xfs_dir2_leaf_check(xfs_inode_t *dp, xfs_dabuf_t *bp);
  48. #else
  49. #define xfs_dir2_leaf_check(dp, bp)
  50. #endif
  51. static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, xfs_dabuf_t **lbpp,
  52. int *indexp, xfs_dabuf_t **dbpp);
  53. static void xfs_dir2_leaf_log_bests(struct xfs_trans *tp, struct xfs_dabuf *bp,
  54. int first, int last);
  55. static void xfs_dir2_leaf_log_tail(struct xfs_trans *tp, struct xfs_dabuf *bp);
  56. /*
  57. * Convert a block form directory to a leaf form directory.
  58. */
  59. int /* error */
  60. xfs_dir2_block_to_leaf(
  61. xfs_da_args_t *args, /* operation arguments */
  62. xfs_dabuf_t *dbp) /* input block's buffer */
  63. {
  64. __be16 *bestsp; /* leaf's bestsp entries */
  65. xfs_dablk_t blkno; /* leaf block's bno */
  66. xfs_dir2_block_t *block; /* block structure */
  67. xfs_dir2_leaf_entry_t *blp; /* block's leaf entries */
  68. xfs_dir2_block_tail_t *btp; /* block's tail */
  69. xfs_inode_t *dp; /* incore directory inode */
  70. int error; /* error return code */
  71. xfs_dabuf_t *lbp; /* leaf block's buffer */
  72. xfs_dir2_db_t ldb; /* leaf block's bno */
  73. xfs_dir2_leaf_t *leaf; /* leaf structure */
  74. xfs_dir2_leaf_tail_t *ltp; /* leaf's tail */
  75. xfs_mount_t *mp; /* filesystem mount point */
  76. int needlog; /* need to log block header */
  77. int needscan; /* need to rescan bestfree */
  78. xfs_trans_t *tp; /* transaction pointer */
  79. xfs_dir2_trace_args_b("block_to_leaf", args, dbp);
  80. dp = args->dp;
  81. mp = dp->i_mount;
  82. tp = args->trans;
  83. /*
  84. * Add the leaf block to the inode.
  85. * This interface will only put blocks in the leaf/node range.
  86. * Since that's empty now, we'll get the root (block 0 in range).
  87. */
  88. if ((error = xfs_da_grow_inode(args, &blkno))) {
  89. return error;
  90. }
  91. ldb = XFS_DIR2_DA_TO_DB(mp, blkno);
  92. ASSERT(ldb == XFS_DIR2_LEAF_FIRSTDB(mp));
  93. /*
  94. * Initialize the leaf block, get a buffer for it.
  95. */
  96. if ((error = xfs_dir2_leaf_init(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC))) {
  97. return error;
  98. }
  99. ASSERT(lbp != NULL);
  100. leaf = lbp->data;
  101. block = dbp->data;
  102. xfs_dir2_data_check(dp, dbp);
  103. btp = XFS_DIR2_BLOCK_TAIL_P(mp, block);
  104. blp = XFS_DIR2_BLOCK_LEAF_P(btp);
  105. /*
  106. * Set the counts in the leaf header.
  107. */
  108. leaf->hdr.count = cpu_to_be16(be32_to_cpu(btp->count));
  109. leaf->hdr.stale = cpu_to_be16(be32_to_cpu(btp->stale));
  110. /*
  111. * Could compact these but I think we always do the conversion
  112. * after squeezing out stale entries.
  113. */
  114. memcpy(leaf->ents, blp, be32_to_cpu(btp->count) * sizeof(xfs_dir2_leaf_entry_t));
  115. xfs_dir2_leaf_log_ents(tp, lbp, 0, be16_to_cpu(leaf->hdr.count) - 1);
  116. needscan = 0;
  117. needlog = 1;
  118. /*
  119. * Make the space formerly occupied by the leaf entries and block
  120. * tail be free.
  121. */
  122. xfs_dir2_data_make_free(tp, dbp,
  123. (xfs_dir2_data_aoff_t)((char *)blp - (char *)block),
  124. (xfs_dir2_data_aoff_t)((char *)block + mp->m_dirblksize -
  125. (char *)blp),
  126. &needlog, &needscan);
  127. /*
  128. * Fix up the block header, make it a data block.
  129. */
  130. block->hdr.magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
  131. if (needscan)
  132. xfs_dir2_data_freescan(mp, (xfs_dir2_data_t *)block, &needlog,
  133. NULL);
  134. /*
  135. * Set up leaf tail and bests table.
  136. */
  137. ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
  138. ltp->bestcount = cpu_to_be32(1);
  139. bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
  140. bestsp[0] = block->hdr.bestfree[0].length;
  141. /*
  142. * Log the data header and leaf bests table.
  143. */
  144. if (needlog)
  145. xfs_dir2_data_log_header(tp, dbp);
  146. xfs_dir2_leaf_check(dp, lbp);
  147. xfs_dir2_data_check(dp, dbp);
  148. xfs_dir2_leaf_log_bests(tp, lbp, 0, 0);
  149. xfs_da_buf_done(lbp);
  150. return 0;
  151. }
  152. /*
  153. * Add an entry to a leaf form directory.
  154. */
  155. int /* error */
  156. xfs_dir2_leaf_addname(
  157. xfs_da_args_t *args) /* operation arguments */
  158. {
  159. __be16 *bestsp; /* freespace table in leaf */
  160. int compact; /* need to compact leaves */
  161. xfs_dir2_data_t *data; /* data block structure */
  162. xfs_dabuf_t *dbp; /* data block buffer */
  163. xfs_dir2_data_entry_t *dep; /* data block entry */
  164. xfs_inode_t *dp; /* incore directory inode */
  165. xfs_dir2_data_unused_t *dup; /* data unused entry */
  166. int error; /* error return value */
  167. int grown; /* allocated new data block */
  168. int highstale; /* index of next stale leaf */
  169. int i; /* temporary, index */
  170. int index; /* leaf table position */
  171. xfs_dabuf_t *lbp; /* leaf's buffer */
  172. xfs_dir2_leaf_t *leaf; /* leaf structure */
  173. int length; /* length of new entry */
  174. xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
  175. int lfloglow; /* low leaf logging index */
  176. int lfloghigh; /* high leaf logging index */
  177. int lowstale; /* index of prev stale leaf */
  178. xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */
  179. xfs_mount_t *mp; /* filesystem mount point */
  180. int needbytes; /* leaf block bytes needed */
  181. int needlog; /* need to log data header */
  182. int needscan; /* need to rescan data free */
  183. __be16 *tagp; /* end of data entry */
  184. xfs_trans_t *tp; /* transaction pointer */
  185. xfs_dir2_db_t use_block; /* data block number */
  186. xfs_dir2_trace_args("leaf_addname", args);
  187. dp = args->dp;
  188. tp = args->trans;
  189. mp = dp->i_mount;
  190. /*
  191. * Read the leaf block.
  192. */
  193. error = xfs_da_read_buf(tp, dp, mp->m_dirleafblk, -1, &lbp,
  194. XFS_DATA_FORK);
  195. if (error) {
  196. return error;
  197. }
  198. ASSERT(lbp != NULL);
  199. /*
  200. * Look up the entry by hash value and name.
  201. * We know it's not there, our caller has already done a lookup.
  202. * So the index is of the entry to insert in front of.
  203. * But if there are dup hash values the index is of the first of those.
  204. */
  205. index = xfs_dir2_leaf_search_hash(args, lbp);
  206. leaf = lbp->data;
  207. ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
  208. bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
  209. length = XFS_DIR2_DATA_ENTSIZE(args->namelen);
  210. /*
  211. * See if there are any entries with the same hash value
  212. * and space in their block for the new entry.
  213. * This is good because it puts multiple same-hash value entries
  214. * in a data block, improving the lookup of those entries.
  215. */
  216. for (use_block = -1, lep = &leaf->ents[index];
  217. index < be16_to_cpu(leaf->hdr.count) && be32_to_cpu(lep->hashval) == args->hashval;
  218. index++, lep++) {
  219. if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
  220. continue;
  221. i = XFS_DIR2_DATAPTR_TO_DB(mp, be32_to_cpu(lep->address));
  222. ASSERT(i < be32_to_cpu(ltp->bestcount));
  223. ASSERT(be16_to_cpu(bestsp[i]) != NULLDATAOFF);
  224. if (be16_to_cpu(bestsp[i]) >= length) {
  225. use_block = i;
  226. break;
  227. }
  228. }
  229. /*
  230. * Didn't find a block yet, linear search all the data blocks.
  231. */
  232. if (use_block == -1) {
  233. for (i = 0; i < be32_to_cpu(ltp->bestcount); i++) {
  234. /*
  235. * Remember a block we see that's missing.
  236. */
  237. if (be16_to_cpu(bestsp[i]) == NULLDATAOFF && use_block == -1)
  238. use_block = i;
  239. else if (be16_to_cpu(bestsp[i]) >= length) {
  240. use_block = i;
  241. break;
  242. }
  243. }
  244. }
  245. /*
  246. * How many bytes do we need in the leaf block?
  247. */
  248. needbytes =
  249. (leaf->hdr.stale ? 0 : (uint)sizeof(leaf->ents[0])) +
  250. (use_block != -1 ? 0 : (uint)sizeof(leaf->bests[0]));
  251. /*
  252. * Now kill use_block if it refers to a missing block, so we
  253. * can use it as an indication of allocation needed.
  254. */
  255. if (use_block != -1 && be16_to_cpu(bestsp[use_block]) == NULLDATAOFF)
  256. use_block = -1;
  257. /*
  258. * If we don't have enough free bytes but we can make enough
  259. * by compacting out stale entries, we'll do that.
  260. */
  261. if ((char *)bestsp - (char *)&leaf->ents[be16_to_cpu(leaf->hdr.count)] < needbytes &&
  262. be16_to_cpu(leaf->hdr.stale) > 1) {
  263. compact = 1;
  264. }
  265. /*
  266. * Otherwise if we don't have enough free bytes we need to
  267. * convert to node form.
  268. */
  269. else if ((char *)bestsp - (char *)&leaf->ents[be16_to_cpu(leaf->hdr.count)] <
  270. needbytes) {
  271. /*
  272. * Just checking or no space reservation, give up.
  273. */
  274. if (args->justcheck || args->total == 0) {
  275. xfs_da_brelse(tp, lbp);
  276. return XFS_ERROR(ENOSPC);
  277. }
  278. /*
  279. * Convert to node form.
  280. */
  281. error = xfs_dir2_leaf_to_node(args, lbp);
  282. xfs_da_buf_done(lbp);
  283. if (error)
  284. return error;
  285. /*
  286. * Then add the new entry.
  287. */
  288. return xfs_dir2_node_addname(args);
  289. }
  290. /*
  291. * Otherwise it will fit without compaction.
  292. */
  293. else
  294. compact = 0;
  295. /*
  296. * If just checking, then it will fit unless we needed to allocate
  297. * a new data block.
  298. */
  299. if (args->justcheck) {
  300. xfs_da_brelse(tp, lbp);
  301. return use_block == -1 ? XFS_ERROR(ENOSPC) : 0;
  302. }
  303. /*
  304. * If no allocations are allowed, return now before we've
  305. * changed anything.
  306. */
  307. if (args->total == 0 && use_block == -1) {
  308. xfs_da_brelse(tp, lbp);
  309. return XFS_ERROR(ENOSPC);
  310. }
  311. /*
  312. * Need to compact the leaf entries, removing stale ones.
  313. * Leave one stale entry behind - the one closest to our
  314. * insertion index - and we'll shift that one to our insertion
  315. * point later.
  316. */
  317. if (compact) {
  318. xfs_dir2_leaf_compact_x1(lbp, &index, &lowstale, &highstale,
  319. &lfloglow, &lfloghigh);
  320. }
  321. /*
  322. * There are stale entries, so we'll need log-low and log-high
  323. * impossibly bad values later.
  324. */
  325. else if (be16_to_cpu(leaf->hdr.stale)) {
  326. lfloglow = be16_to_cpu(leaf->hdr.count);
  327. lfloghigh = -1;
  328. }
  329. /*
  330. * If there was no data block space found, we need to allocate
  331. * a new one.
  332. */
  333. if (use_block == -1) {
  334. /*
  335. * Add the new data block.
  336. */
  337. if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE,
  338. &use_block))) {
  339. xfs_da_brelse(tp, lbp);
  340. return error;
  341. }
  342. /*
  343. * Initialize the block.
  344. */
  345. if ((error = xfs_dir2_data_init(args, use_block, &dbp))) {
  346. xfs_da_brelse(tp, lbp);
  347. return error;
  348. }
  349. /*
  350. * If we're adding a new data block on the end we need to
  351. * extend the bests table. Copy it up one entry.
  352. */
  353. if (use_block >= be32_to_cpu(ltp->bestcount)) {
  354. bestsp--;
  355. memmove(&bestsp[0], &bestsp[1],
  356. be32_to_cpu(ltp->bestcount) * sizeof(bestsp[0]));
  357. be32_add(&ltp->bestcount, 1);
  358. xfs_dir2_leaf_log_tail(tp, lbp);
  359. xfs_dir2_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
  360. }
  361. /*
  362. * If we're filling in a previously empty block just log it.
  363. */
  364. else
  365. xfs_dir2_leaf_log_bests(tp, lbp, use_block, use_block);
  366. data = dbp->data;
  367. bestsp[use_block] = data->hdr.bestfree[0].length;
  368. grown = 1;
  369. }
  370. /*
  371. * Already had space in some data block.
  372. * Just read that one in.
  373. */
  374. else {
  375. if ((error =
  376. xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, use_block),
  377. -1, &dbp, XFS_DATA_FORK))) {
  378. xfs_da_brelse(tp, lbp);
  379. return error;
  380. }
  381. data = dbp->data;
  382. grown = 0;
  383. }
  384. xfs_dir2_data_check(dp, dbp);
  385. /*
  386. * Point to the biggest freespace in our data block.
  387. */
  388. dup = (xfs_dir2_data_unused_t *)
  389. ((char *)data + be16_to_cpu(data->hdr.bestfree[0].offset));
  390. ASSERT(be16_to_cpu(dup->length) >= length);
  391. needscan = needlog = 0;
  392. /*
  393. * Mark the initial part of our freespace in use for the new entry.
  394. */
  395. xfs_dir2_data_use_free(tp, dbp, dup,
  396. (xfs_dir2_data_aoff_t)((char *)dup - (char *)data), length,
  397. &needlog, &needscan);
  398. /*
  399. * Initialize our new entry (at last).
  400. */
  401. dep = (xfs_dir2_data_entry_t *)dup;
  402. dep->inumber = cpu_to_be64(args->inumber);
  403. dep->namelen = args->namelen;
  404. memcpy(dep->name, args->name, dep->namelen);
  405. tagp = XFS_DIR2_DATA_ENTRY_TAG_P(dep);
  406. *tagp = cpu_to_be16((char *)dep - (char *)data);
  407. /*
  408. * Need to scan fix up the bestfree table.
  409. */
  410. if (needscan)
  411. xfs_dir2_data_freescan(mp, data, &needlog, NULL);
  412. /*
  413. * Need to log the data block's header.
  414. */
  415. if (needlog)
  416. xfs_dir2_data_log_header(tp, dbp);
  417. xfs_dir2_data_log_entry(tp, dbp, dep);
  418. /*
  419. * If the bests table needs to be changed, do it.
  420. * Log the change unless we've already done that.
  421. */
  422. if (be16_to_cpu(bestsp[use_block]) != be16_to_cpu(data->hdr.bestfree[0].length)) {
  423. bestsp[use_block] = data->hdr.bestfree[0].length;
  424. if (!grown)
  425. xfs_dir2_leaf_log_bests(tp, lbp, use_block, use_block);
  426. }
  427. /*
  428. * Now we need to make room to insert the leaf entry.
  429. * If there are no stale entries, we just insert a hole at index.
  430. */
  431. if (!leaf->hdr.stale) {
  432. /*
  433. * lep is still good as the index leaf entry.
  434. */
  435. if (index < be16_to_cpu(leaf->hdr.count))
  436. memmove(lep + 1, lep,
  437. (be16_to_cpu(leaf->hdr.count) - index) * sizeof(*lep));
  438. /*
  439. * Record low and high logging indices for the leaf.
  440. */
  441. lfloglow = index;
  442. lfloghigh = be16_to_cpu(leaf->hdr.count);
  443. be16_add(&leaf->hdr.count, 1);
  444. }
  445. /*
  446. * There are stale entries.
  447. * We will use one of them for the new entry.
  448. * It's probably not at the right location, so we'll have to
  449. * shift some up or down first.
  450. */
  451. else {
  452. /*
  453. * If we didn't compact before, we need to find the nearest
  454. * stale entries before and after our insertion point.
  455. */
  456. if (compact == 0) {
  457. /*
  458. * Find the first stale entry before the insertion
  459. * point, if any.
  460. */
  461. for (lowstale = index - 1;
  462. lowstale >= 0 &&
  463. be32_to_cpu(leaf->ents[lowstale].address) !=
  464. XFS_DIR2_NULL_DATAPTR;
  465. lowstale--)
  466. continue;
  467. /*
  468. * Find the next stale entry at or after the insertion
  469. * point, if any. Stop if we go so far that the
  470. * lowstale entry would be better.
  471. */
  472. for (highstale = index;
  473. highstale < be16_to_cpu(leaf->hdr.count) &&
  474. be32_to_cpu(leaf->ents[highstale].address) !=
  475. XFS_DIR2_NULL_DATAPTR &&
  476. (lowstale < 0 ||
  477. index - lowstale - 1 >= highstale - index);
  478. highstale++)
  479. continue;
  480. }
  481. /*
  482. * If the low one is better, use it.
  483. */
  484. if (lowstale >= 0 &&
  485. (highstale == be16_to_cpu(leaf->hdr.count) ||
  486. index - lowstale - 1 < highstale - index)) {
  487. ASSERT(index - lowstale - 1 >= 0);
  488. ASSERT(be32_to_cpu(leaf->ents[lowstale].address) ==
  489. XFS_DIR2_NULL_DATAPTR);
  490. /*
  491. * Copy entries up to cover the stale entry
  492. * and make room for the new entry.
  493. */
  494. if (index - lowstale - 1 > 0)
  495. memmove(&leaf->ents[lowstale],
  496. &leaf->ents[lowstale + 1],
  497. (index - lowstale - 1) * sizeof(*lep));
  498. lep = &leaf->ents[index - 1];
  499. lfloglow = MIN(lowstale, lfloglow);
  500. lfloghigh = MAX(index - 1, lfloghigh);
  501. }
  502. /*
  503. * The high one is better, so use that one.
  504. */
  505. else {
  506. ASSERT(highstale - index >= 0);
  507. ASSERT(be32_to_cpu(leaf->ents[highstale].address) ==
  508. XFS_DIR2_NULL_DATAPTR);
  509. /*
  510. * Copy entries down to cover the stale entry
  511. * and make room for the new entry.
  512. */
  513. if (highstale - index > 0)
  514. memmove(&leaf->ents[index + 1],
  515. &leaf->ents[index],
  516. (highstale - index) * sizeof(*lep));
  517. lep = &leaf->ents[index];
  518. lfloglow = MIN(index, lfloglow);
  519. lfloghigh = MAX(highstale, lfloghigh);
  520. }
  521. be16_add(&leaf->hdr.stale, -1);
  522. }
  523. /*
  524. * Fill in the new leaf entry.
  525. */
  526. lep->hashval = cpu_to_be32(args->hashval);
  527. lep->address = cpu_to_be32(XFS_DIR2_DB_OFF_TO_DATAPTR(mp, use_block,
  528. be16_to_cpu(*tagp)));
  529. /*
  530. * Log the leaf fields and give up the buffers.
  531. */
  532. xfs_dir2_leaf_log_header(tp, lbp);
  533. xfs_dir2_leaf_log_ents(tp, lbp, lfloglow, lfloghigh);
  534. xfs_dir2_leaf_check(dp, lbp);
  535. xfs_da_buf_done(lbp);
  536. xfs_dir2_data_check(dp, dbp);
  537. xfs_da_buf_done(dbp);
  538. return 0;
  539. }
  540. #ifdef DEBUG
  541. /*
  542. * Check the internal consistency of a leaf1 block.
  543. * Pop an assert if something is wrong.
  544. */
  545. void
  546. xfs_dir2_leaf_check(
  547. xfs_inode_t *dp, /* incore directory inode */
  548. xfs_dabuf_t *bp) /* leaf's buffer */
  549. {
  550. int i; /* leaf index */
  551. xfs_dir2_leaf_t *leaf; /* leaf structure */
  552. xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */
  553. xfs_mount_t *mp; /* filesystem mount point */
  554. int stale; /* count of stale leaves */
  555. leaf = bp->data;
  556. mp = dp->i_mount;
  557. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAF1_MAGIC);
  558. /*
  559. * This value is not restrictive enough.
  560. * Should factor in the size of the bests table as well.
  561. * We can deduce a value for that from di_size.
  562. */
  563. ASSERT(be16_to_cpu(leaf->hdr.count) <= XFS_DIR2_MAX_LEAF_ENTS(mp));
  564. ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
  565. /*
  566. * Leaves and bests don't overlap.
  567. */
  568. ASSERT((char *)&leaf->ents[be16_to_cpu(leaf->hdr.count)] <=
  569. (char *)XFS_DIR2_LEAF_BESTS_P(ltp));
  570. /*
  571. * Check hash value order, count stale entries.
  572. */
  573. for (i = stale = 0; i < be16_to_cpu(leaf->hdr.count); i++) {
  574. if (i + 1 < be16_to_cpu(leaf->hdr.count))
  575. ASSERT(be32_to_cpu(leaf->ents[i].hashval) <=
  576. be32_to_cpu(leaf->ents[i + 1].hashval));
  577. if (be32_to_cpu(leaf->ents[i].address) == XFS_DIR2_NULL_DATAPTR)
  578. stale++;
  579. }
  580. ASSERT(be16_to_cpu(leaf->hdr.stale) == stale);
  581. }
  582. #endif /* DEBUG */
  583. /*
  584. * Compact out any stale entries in the leaf.
  585. * Log the header and changed leaf entries, if any.
  586. */
  587. void
  588. xfs_dir2_leaf_compact(
  589. xfs_da_args_t *args, /* operation arguments */
  590. xfs_dabuf_t *bp) /* leaf buffer */
  591. {
  592. int from; /* source leaf index */
  593. xfs_dir2_leaf_t *leaf; /* leaf structure */
  594. int loglow; /* first leaf entry to log */
  595. int to; /* target leaf index */
  596. leaf = bp->data;
  597. if (!leaf->hdr.stale) {
  598. return;
  599. }
  600. /*
  601. * Compress out the stale entries in place.
  602. */
  603. for (from = to = 0, loglow = -1; from < be16_to_cpu(leaf->hdr.count); from++) {
  604. if (be32_to_cpu(leaf->ents[from].address) == XFS_DIR2_NULL_DATAPTR)
  605. continue;
  606. /*
  607. * Only actually copy the entries that are different.
  608. */
  609. if (from > to) {
  610. if (loglow == -1)
  611. loglow = to;
  612. leaf->ents[to] = leaf->ents[from];
  613. }
  614. to++;
  615. }
  616. /*
  617. * Update and log the header, log the leaf entries.
  618. */
  619. ASSERT(be16_to_cpu(leaf->hdr.stale) == from - to);
  620. be16_add(&leaf->hdr.count, -(be16_to_cpu(leaf->hdr.stale)));
  621. leaf->hdr.stale = 0;
  622. xfs_dir2_leaf_log_header(args->trans, bp);
  623. if (loglow != -1)
  624. xfs_dir2_leaf_log_ents(args->trans, bp, loglow, to - 1);
  625. }
  626. /*
  627. * Compact the leaf entries, removing stale ones.
  628. * Leave one stale entry behind - the one closest to our
  629. * insertion index - and the caller will shift that one to our insertion
  630. * point later.
  631. * Return new insertion index, where the remaining stale entry is,
  632. * and leaf logging indices.
  633. */
  634. void
  635. xfs_dir2_leaf_compact_x1(
  636. xfs_dabuf_t *bp, /* leaf buffer */
  637. int *indexp, /* insertion index */
  638. int *lowstalep, /* out: stale entry before us */
  639. int *highstalep, /* out: stale entry after us */
  640. int *lowlogp, /* out: low log index */
  641. int *highlogp) /* out: high log index */
  642. {
  643. int from; /* source copy index */
  644. int highstale; /* stale entry at/after index */
  645. int index; /* insertion index */
  646. int keepstale; /* source index of kept stale */
  647. xfs_dir2_leaf_t *leaf; /* leaf structure */
  648. int lowstale; /* stale entry before index */
  649. int newindex=0; /* new insertion index */
  650. int to; /* destination copy index */
  651. leaf = bp->data;
  652. ASSERT(be16_to_cpu(leaf->hdr.stale) > 1);
  653. index = *indexp;
  654. /*
  655. * Find the first stale entry before our index, if any.
  656. */
  657. for (lowstale = index - 1;
  658. lowstale >= 0 &&
  659. be32_to_cpu(leaf->ents[lowstale].address) != XFS_DIR2_NULL_DATAPTR;
  660. lowstale--)
  661. continue;
  662. /*
  663. * Find the first stale entry at or after our index, if any.
  664. * Stop if the answer would be worse than lowstale.
  665. */
  666. for (highstale = index;
  667. highstale < be16_to_cpu(leaf->hdr.count) &&
  668. be32_to_cpu(leaf->ents[highstale].address) != XFS_DIR2_NULL_DATAPTR &&
  669. (lowstale < 0 || index - lowstale > highstale - index);
  670. highstale++)
  671. continue;
  672. /*
  673. * Pick the better of lowstale and highstale.
  674. */
  675. if (lowstale >= 0 &&
  676. (highstale == be16_to_cpu(leaf->hdr.count) ||
  677. index - lowstale <= highstale - index))
  678. keepstale = lowstale;
  679. else
  680. keepstale = highstale;
  681. /*
  682. * Copy the entries in place, removing all the stale entries
  683. * except keepstale.
  684. */
  685. for (from = to = 0; from < be16_to_cpu(leaf->hdr.count); from++) {
  686. /*
  687. * Notice the new value of index.
  688. */
  689. if (index == from)
  690. newindex = to;
  691. if (from != keepstale &&
  692. be32_to_cpu(leaf->ents[from].address) == XFS_DIR2_NULL_DATAPTR) {
  693. if (from == to)
  694. *lowlogp = to;
  695. continue;
  696. }
  697. /*
  698. * Record the new keepstale value for the insertion.
  699. */
  700. if (from == keepstale)
  701. lowstale = highstale = to;
  702. /*
  703. * Copy only the entries that have moved.
  704. */
  705. if (from > to)
  706. leaf->ents[to] = leaf->ents[from];
  707. to++;
  708. }
  709. ASSERT(from > to);
  710. /*
  711. * If the insertion point was past the last entry,
  712. * set the new insertion point accordingly.
  713. */
  714. if (index == from)
  715. newindex = to;
  716. *indexp = newindex;
  717. /*
  718. * Adjust the leaf header values.
  719. */
  720. be16_add(&leaf->hdr.count, -(from - to));
  721. leaf->hdr.stale = cpu_to_be16(1);
  722. /*
  723. * Remember the low/high stale value only in the "right"
  724. * direction.
  725. */
  726. if (lowstale >= newindex)
  727. lowstale = -1;
  728. else
  729. highstale = be16_to_cpu(leaf->hdr.count);
  730. *highlogp = be16_to_cpu(leaf->hdr.count) - 1;
  731. *lowstalep = lowstale;
  732. *highstalep = highstale;
  733. }
  734. /*
  735. * Getdents (readdir) for leaf and node directories.
  736. * This reads the data blocks only, so is the same for both forms.
  737. */
  738. int /* error */
  739. xfs_dir2_leaf_getdents(
  740. xfs_trans_t *tp, /* transaction pointer */
  741. xfs_inode_t *dp, /* incore directory inode */
  742. uio_t *uio, /* I/O control & vectors */
  743. int *eofp, /* out: reached end of dir */
  744. xfs_dirent_t *dbp, /* caller's buffer */
  745. xfs_dir2_put_t put) /* ABI formatting routine */
  746. {
  747. xfs_dabuf_t *bp; /* data block buffer */
  748. int byteoff; /* offset in current block */
  749. xfs_dir2_db_t curdb; /* db for current block */
  750. xfs_dir2_off_t curoff; /* current overall offset */
  751. xfs_dir2_data_t *data; /* data block structure */
  752. xfs_dir2_data_entry_t *dep; /* data entry */
  753. xfs_dir2_data_unused_t *dup; /* unused entry */
  754. int eof; /* reached end of directory */
  755. int error = 0; /* error return value */
  756. int i; /* temporary loop index */
  757. int j; /* temporary loop index */
  758. int length; /* temporary length value */
  759. xfs_bmbt_irec_t *map; /* map vector for blocks */
  760. xfs_extlen_t map_blocks; /* number of fsbs in map */
  761. xfs_dablk_t map_off; /* last mapped file offset */
  762. int map_size; /* total entries in *map */
  763. int map_valid; /* valid entries in *map */
  764. xfs_mount_t *mp; /* filesystem mount point */
  765. xfs_dir2_off_t newoff; /* new curoff after new blk */
  766. int nmap; /* mappings to ask xfs_bmapi */
  767. xfs_dir2_put_args_t *p; /* formatting arg bundle */
  768. char *ptr = NULL; /* pointer to current data */
  769. int ra_current; /* number of read-ahead blks */
  770. int ra_index; /* *map index for read-ahead */
  771. int ra_offset; /* map entry offset for ra */
  772. int ra_want; /* readahead count wanted */
  773. /*
  774. * If the offset is at or past the largest allowed value,
  775. * give up right away, return eof.
  776. */
  777. if (uio->uio_offset >= XFS_DIR2_MAX_DATAPTR) {
  778. *eofp = 1;
  779. return 0;
  780. }
  781. mp = dp->i_mount;
  782. /*
  783. * Setup formatting arguments.
  784. */
  785. p = kmem_alloc(sizeof(*p), KM_SLEEP);
  786. p->dbp = dbp;
  787. p->put = put;
  788. p->uio = uio;
  789. /*
  790. * Set up to bmap a number of blocks based on the caller's
  791. * buffer size, the directory block size, and the filesystem
  792. * block size.
  793. */
  794. map_size =
  795. howmany(uio->uio_resid + mp->m_dirblksize,
  796. mp->m_sb.sb_blocksize);
  797. map = kmem_alloc(map_size * sizeof(*map), KM_SLEEP);
  798. map_valid = ra_index = ra_offset = ra_current = map_blocks = 0;
  799. bp = NULL;
  800. eof = 1;
  801. /*
  802. * Inside the loop we keep the main offset value as a byte offset
  803. * in the directory file.
  804. */
  805. curoff = XFS_DIR2_DATAPTR_TO_BYTE(mp, uio->uio_offset);
  806. /*
  807. * Force this conversion through db so we truncate the offset
  808. * down to get the start of the data block.
  809. */
  810. map_off = XFS_DIR2_DB_TO_DA(mp, XFS_DIR2_BYTE_TO_DB(mp, curoff));
  811. /*
  812. * Loop over directory entries until we reach the end offset.
  813. * Get more blocks and readahead as necessary.
  814. */
  815. while (curoff < XFS_DIR2_LEAF_OFFSET) {
  816. /*
  817. * If we have no buffer, or we're off the end of the
  818. * current buffer, need to get another one.
  819. */
  820. if (!bp || ptr >= (char *)bp->data + mp->m_dirblksize) {
  821. /*
  822. * If we have a buffer, we need to release it and
  823. * take it out of the mapping.
  824. */
  825. if (bp) {
  826. xfs_da_brelse(tp, bp);
  827. bp = NULL;
  828. map_blocks -= mp->m_dirblkfsbs;
  829. /*
  830. * Loop to get rid of the extents for the
  831. * directory block.
  832. */
  833. for (i = mp->m_dirblkfsbs; i > 0; ) {
  834. j = MIN((int)map->br_blockcount, i);
  835. map->br_blockcount -= j;
  836. map->br_startblock += j;
  837. map->br_startoff += j;
  838. /*
  839. * If mapping is done, pitch it from
  840. * the table.
  841. */
  842. if (!map->br_blockcount && --map_valid)
  843. memmove(&map[0], &map[1],
  844. sizeof(map[0]) *
  845. map_valid);
  846. i -= j;
  847. }
  848. }
  849. /*
  850. * Recalculate the readahead blocks wanted.
  851. */
  852. ra_want = howmany(uio->uio_resid + mp->m_dirblksize,
  853. mp->m_sb.sb_blocksize) - 1;
  854. /*
  855. * If we don't have as many as we want, and we haven't
  856. * run out of data blocks, get some more mappings.
  857. */
  858. if (1 + ra_want > map_blocks &&
  859. map_off <
  860. XFS_DIR2_BYTE_TO_DA(mp, XFS_DIR2_LEAF_OFFSET)) {
  861. /*
  862. * Get more bmaps, fill in after the ones
  863. * we already have in the table.
  864. */
  865. nmap = map_size - map_valid;
  866. error = xfs_bmapi(tp, dp,
  867. map_off,
  868. XFS_DIR2_BYTE_TO_DA(mp,
  869. XFS_DIR2_LEAF_OFFSET) - map_off,
  870. XFS_BMAPI_METADATA, NULL, 0,
  871. &map[map_valid], &nmap, NULL, NULL);
  872. /*
  873. * Don't know if we should ignore this or
  874. * try to return an error.
  875. * The trouble with returning errors
  876. * is that readdir will just stop without
  877. * actually passing the error through.
  878. */
  879. if (error)
  880. break; /* XXX */
  881. /*
  882. * If we got all the mappings we asked for,
  883. * set the final map offset based on the
  884. * last bmap value received.
  885. * Otherwise, we've reached the end.
  886. */
  887. if (nmap == map_size - map_valid)
  888. map_off =
  889. map[map_valid + nmap - 1].br_startoff +
  890. map[map_valid + nmap - 1].br_blockcount;
  891. else
  892. map_off =
  893. XFS_DIR2_BYTE_TO_DA(mp,
  894. XFS_DIR2_LEAF_OFFSET);
  895. /*
  896. * Look for holes in the mapping, and
  897. * eliminate them. Count up the valid blocks.
  898. */
  899. for (i = map_valid; i < map_valid + nmap; ) {
  900. if (map[i].br_startblock ==
  901. HOLESTARTBLOCK) {
  902. nmap--;
  903. length = map_valid + nmap - i;
  904. if (length)
  905. memmove(&map[i],
  906. &map[i + 1],
  907. sizeof(map[i]) *
  908. length);
  909. } else {
  910. map_blocks +=
  911. map[i].br_blockcount;
  912. i++;
  913. }
  914. }
  915. map_valid += nmap;
  916. }
  917. /*
  918. * No valid mappings, so no more data blocks.
  919. */
  920. if (!map_valid) {
  921. curoff = XFS_DIR2_DA_TO_BYTE(mp, map_off);
  922. break;
  923. }
  924. /*
  925. * Read the directory block starting at the first
  926. * mapping.
  927. */
  928. curdb = XFS_DIR2_DA_TO_DB(mp, map->br_startoff);
  929. error = xfs_da_read_buf(tp, dp, map->br_startoff,
  930. map->br_blockcount >= mp->m_dirblkfsbs ?
  931. XFS_FSB_TO_DADDR(mp, map->br_startblock) :
  932. -1,
  933. &bp, XFS_DATA_FORK);
  934. /*
  935. * Should just skip over the data block instead
  936. * of giving up.
  937. */
  938. if (error)
  939. break; /* XXX */
  940. /*
  941. * Adjust the current amount of read-ahead: we just
  942. * read a block that was previously ra.
  943. */
  944. if (ra_current)
  945. ra_current -= mp->m_dirblkfsbs;
  946. /*
  947. * Do we need more readahead?
  948. */
  949. for (ra_index = ra_offset = i = 0;
  950. ra_want > ra_current && i < map_blocks;
  951. i += mp->m_dirblkfsbs) {
  952. ASSERT(ra_index < map_valid);
  953. /*
  954. * Read-ahead a contiguous directory block.
  955. */
  956. if (i > ra_current &&
  957. map[ra_index].br_blockcount >=
  958. mp->m_dirblkfsbs) {
  959. xfs_baread(mp->m_ddev_targp,
  960. XFS_FSB_TO_DADDR(mp,
  961. map[ra_index].br_startblock +
  962. ra_offset),
  963. (int)BTOBB(mp->m_dirblksize));
  964. ra_current = i;
  965. }
  966. /*
  967. * Read-ahead a non-contiguous directory block.
  968. * This doesn't use our mapping, but this
  969. * is a very rare case.
  970. */
  971. else if (i > ra_current) {
  972. (void)xfs_da_reada_buf(tp, dp,
  973. map[ra_index].br_startoff +
  974. ra_offset, XFS_DATA_FORK);
  975. ra_current = i;
  976. }
  977. /*
  978. * Advance offset through the mapping table.
  979. */
  980. for (j = 0; j < mp->m_dirblkfsbs; j++) {
  981. /*
  982. * The rest of this extent but not
  983. * more than a dir block.
  984. */
  985. length = MIN(mp->m_dirblkfsbs,
  986. (int)(map[ra_index].br_blockcount -
  987. ra_offset));
  988. j += length;
  989. ra_offset += length;
  990. /*
  991. * Advance to the next mapping if
  992. * this one is used up.
  993. */
  994. if (ra_offset ==
  995. map[ra_index].br_blockcount) {
  996. ra_offset = 0;
  997. ra_index++;
  998. }
  999. }
  1000. }
  1001. /*
  1002. * Having done a read, we need to set a new offset.
  1003. */
  1004. newoff = XFS_DIR2_DB_OFF_TO_BYTE(mp, curdb, 0);
  1005. /*
  1006. * Start of the current block.
  1007. */
  1008. if (curoff < newoff)
  1009. curoff = newoff;
  1010. /*
  1011. * Make sure we're in the right block.
  1012. */
  1013. else if (curoff > newoff)
  1014. ASSERT(XFS_DIR2_BYTE_TO_DB(mp, curoff) ==
  1015. curdb);
  1016. data = bp->data;
  1017. xfs_dir2_data_check(dp, bp);
  1018. /*
  1019. * Find our position in the block.
  1020. */
  1021. ptr = (char *)&data->u;
  1022. byteoff = XFS_DIR2_BYTE_TO_OFF(mp, curoff);
  1023. /*
  1024. * Skip past the header.
  1025. */
  1026. if (byteoff == 0)
  1027. curoff += (uint)sizeof(data->hdr);
  1028. /*
  1029. * Skip past entries until we reach our offset.
  1030. */
  1031. else {
  1032. while ((char *)ptr - (char *)data < byteoff) {
  1033. dup = (xfs_dir2_data_unused_t *)ptr;
  1034. if (be16_to_cpu(dup->freetag)
  1035. == XFS_DIR2_DATA_FREE_TAG) {
  1036. length = be16_to_cpu(dup->length);
  1037. ptr += length;
  1038. continue;
  1039. }
  1040. dep = (xfs_dir2_data_entry_t *)ptr;
  1041. length =
  1042. XFS_DIR2_DATA_ENTSIZE(dep->namelen);
  1043. ptr += length;
  1044. }
  1045. /*
  1046. * Now set our real offset.
  1047. */
  1048. curoff =
  1049. XFS_DIR2_DB_OFF_TO_BYTE(mp,
  1050. XFS_DIR2_BYTE_TO_DB(mp, curoff),
  1051. (char *)ptr - (char *)data);
  1052. if (ptr >= (char *)data + mp->m_dirblksize) {
  1053. continue;
  1054. }
  1055. }
  1056. }
  1057. /*
  1058. * We have a pointer to an entry.
  1059. * Is it a live one?
  1060. */
  1061. dup = (xfs_dir2_data_unused_t *)ptr;
  1062. /*
  1063. * No, it's unused, skip over it.
  1064. */
  1065. if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
  1066. length = be16_to_cpu(dup->length);
  1067. ptr += length;
  1068. curoff += length;
  1069. continue;
  1070. }
  1071. /*
  1072. * Copy the entry into the putargs, and try formatting it.
  1073. */
  1074. dep = (xfs_dir2_data_entry_t *)ptr;
  1075. p->namelen = dep->namelen;
  1076. length = XFS_DIR2_DATA_ENTSIZE(p->namelen);
  1077. p->cook = XFS_DIR2_BYTE_TO_DATAPTR(mp, curoff + length);
  1078. p->ino = be64_to_cpu(dep->inumber);
  1079. #if XFS_BIG_INUMS
  1080. p->ino += mp->m_inoadd;
  1081. #endif
  1082. p->name = (char *)dep->name;
  1083. error = p->put(p);
  1084. /*
  1085. * Won't fit. Return to caller.
  1086. */
  1087. if (!p->done) {
  1088. eof = 0;
  1089. break;
  1090. }
  1091. /*
  1092. * Advance to next entry in the block.
  1093. */
  1094. ptr += length;
  1095. curoff += length;
  1096. }
  1097. /*
  1098. * All done. Set output offset value to current offset.
  1099. */
  1100. *eofp = eof;
  1101. if (curoff > XFS_DIR2_DATAPTR_TO_BYTE(mp, XFS_DIR2_MAX_DATAPTR))
  1102. uio->uio_offset = XFS_DIR2_MAX_DATAPTR;
  1103. else
  1104. uio->uio_offset = XFS_DIR2_BYTE_TO_DATAPTR(mp, curoff);
  1105. kmem_free(map, map_size * sizeof(*map));
  1106. kmem_free(p, sizeof(*p));
  1107. if (bp)
  1108. xfs_da_brelse(tp, bp);
  1109. return error;
  1110. }
  1111. /*
  1112. * Initialize a new leaf block, leaf1 or leafn magic accepted.
  1113. */
  1114. int
  1115. xfs_dir2_leaf_init(
  1116. xfs_da_args_t *args, /* operation arguments */
  1117. xfs_dir2_db_t bno, /* directory block number */
  1118. xfs_dabuf_t **bpp, /* out: leaf buffer */
  1119. int magic) /* magic number for block */
  1120. {
  1121. xfs_dabuf_t *bp; /* leaf buffer */
  1122. xfs_inode_t *dp; /* incore directory inode */
  1123. int error; /* error return code */
  1124. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1125. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1126. xfs_mount_t *mp; /* filesystem mount point */
  1127. xfs_trans_t *tp; /* transaction pointer */
  1128. dp = args->dp;
  1129. ASSERT(dp != NULL);
  1130. tp = args->trans;
  1131. mp = dp->i_mount;
  1132. ASSERT(bno >= XFS_DIR2_LEAF_FIRSTDB(mp) &&
  1133. bno < XFS_DIR2_FREE_FIRSTDB(mp));
  1134. /*
  1135. * Get the buffer for the block.
  1136. */
  1137. error = xfs_da_get_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, bno), -1, &bp,
  1138. XFS_DATA_FORK);
  1139. if (error) {
  1140. return error;
  1141. }
  1142. ASSERT(bp != NULL);
  1143. leaf = bp->data;
  1144. /*
  1145. * Initialize the header.
  1146. */
  1147. leaf->hdr.info.magic = cpu_to_be16(magic);
  1148. leaf->hdr.info.forw = 0;
  1149. leaf->hdr.info.back = 0;
  1150. leaf->hdr.count = 0;
  1151. leaf->hdr.stale = 0;
  1152. xfs_dir2_leaf_log_header(tp, bp);
  1153. /*
  1154. * If it's a leaf-format directory initialize the tail.
  1155. * In this case our caller has the real bests table to copy into
  1156. * the block.
  1157. */
  1158. if (magic == XFS_DIR2_LEAF1_MAGIC) {
  1159. ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
  1160. ltp->bestcount = 0;
  1161. xfs_dir2_leaf_log_tail(tp, bp);
  1162. }
  1163. *bpp = bp;
  1164. return 0;
  1165. }
  1166. /*
  1167. * Log the bests entries indicated from a leaf1 block.
  1168. */
  1169. static void
  1170. xfs_dir2_leaf_log_bests(
  1171. xfs_trans_t *tp, /* transaction pointer */
  1172. xfs_dabuf_t *bp, /* leaf buffer */
  1173. int first, /* first entry to log */
  1174. int last) /* last entry to log */
  1175. {
  1176. __be16 *firstb; /* pointer to first entry */
  1177. __be16 *lastb; /* pointer to last entry */
  1178. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1179. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1180. leaf = bp->data;
  1181. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAF1_MAGIC);
  1182. ltp = XFS_DIR2_LEAF_TAIL_P(tp->t_mountp, leaf);
  1183. firstb = XFS_DIR2_LEAF_BESTS_P(ltp) + first;
  1184. lastb = XFS_DIR2_LEAF_BESTS_P(ltp) + last;
  1185. xfs_da_log_buf(tp, bp, (uint)((char *)firstb - (char *)leaf),
  1186. (uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1));
  1187. }
  1188. /*
  1189. * Log the leaf entries indicated from a leaf1 or leafn block.
  1190. */
  1191. void
  1192. xfs_dir2_leaf_log_ents(
  1193. xfs_trans_t *tp, /* transaction pointer */
  1194. xfs_dabuf_t *bp, /* leaf buffer */
  1195. int first, /* first entry to log */
  1196. int last) /* last entry to log */
  1197. {
  1198. xfs_dir2_leaf_entry_t *firstlep; /* pointer to first entry */
  1199. xfs_dir2_leaf_entry_t *lastlep; /* pointer to last entry */
  1200. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1201. leaf = bp->data;
  1202. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAF1_MAGIC ||
  1203. be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  1204. firstlep = &leaf->ents[first];
  1205. lastlep = &leaf->ents[last];
  1206. xfs_da_log_buf(tp, bp, (uint)((char *)firstlep - (char *)leaf),
  1207. (uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1));
  1208. }
  1209. /*
  1210. * Log the header of the leaf1 or leafn block.
  1211. */
  1212. void
  1213. xfs_dir2_leaf_log_header(
  1214. xfs_trans_t *tp, /* transaction pointer */
  1215. xfs_dabuf_t *bp) /* leaf buffer */
  1216. {
  1217. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1218. leaf = bp->data;
  1219. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAF1_MAGIC ||
  1220. be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  1221. xfs_da_log_buf(tp, bp, (uint)((char *)&leaf->hdr - (char *)leaf),
  1222. (uint)(sizeof(leaf->hdr) - 1));
  1223. }
  1224. /*
  1225. * Log the tail of the leaf1 block.
  1226. */
  1227. STATIC void
  1228. xfs_dir2_leaf_log_tail(
  1229. xfs_trans_t *tp, /* transaction pointer */
  1230. xfs_dabuf_t *bp) /* leaf buffer */
  1231. {
  1232. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1233. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1234. xfs_mount_t *mp; /* filesystem mount point */
  1235. mp = tp->t_mountp;
  1236. leaf = bp->data;
  1237. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAF1_MAGIC);
  1238. ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
  1239. xfs_da_log_buf(tp, bp, (uint)((char *)ltp - (char *)leaf),
  1240. (uint)(mp->m_dirblksize - 1));
  1241. }
  1242. /*
  1243. * Look up the entry referred to by args in the leaf format directory.
  1244. * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
  1245. * is also used by the node-format code.
  1246. */
  1247. int
  1248. xfs_dir2_leaf_lookup(
  1249. xfs_da_args_t *args) /* operation arguments */
  1250. {
  1251. xfs_dabuf_t *dbp; /* data block buffer */
  1252. xfs_dir2_data_entry_t *dep; /* data block entry */
  1253. xfs_inode_t *dp; /* incore directory inode */
  1254. int error; /* error return code */
  1255. int index; /* found entry index */
  1256. xfs_dabuf_t *lbp; /* leaf buffer */
  1257. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1258. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1259. xfs_trans_t *tp; /* transaction pointer */
  1260. xfs_dir2_trace_args("leaf_lookup", args);
  1261. /*
  1262. * Look up name in the leaf block, returning both buffers and index.
  1263. */
  1264. if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
  1265. return error;
  1266. }
  1267. tp = args->trans;
  1268. dp = args->dp;
  1269. xfs_dir2_leaf_check(dp, lbp);
  1270. leaf = lbp->data;
  1271. /*
  1272. * Get to the leaf entry and contained data entry address.
  1273. */
  1274. lep = &leaf->ents[index];
  1275. /*
  1276. * Point to the data entry.
  1277. */
  1278. dep = (xfs_dir2_data_entry_t *)
  1279. ((char *)dbp->data +
  1280. XFS_DIR2_DATAPTR_TO_OFF(dp->i_mount, be32_to_cpu(lep->address)));
  1281. /*
  1282. * Return the found inode number.
  1283. */
  1284. args->inumber = be64_to_cpu(dep->inumber);
  1285. xfs_da_brelse(tp, dbp);
  1286. xfs_da_brelse(tp, lbp);
  1287. return XFS_ERROR(EEXIST);
  1288. }
  1289. /*
  1290. * Look up name/hash in the leaf block.
  1291. * Fill in indexp with the found index, and dbpp with the data buffer.
  1292. * If not found dbpp will be NULL, and ENOENT comes back.
  1293. * lbpp will always be filled in with the leaf buffer unless there's an error.
  1294. */
  1295. static int /* error */
  1296. xfs_dir2_leaf_lookup_int(
  1297. xfs_da_args_t *args, /* operation arguments */
  1298. xfs_dabuf_t **lbpp, /* out: leaf buffer */
  1299. int *indexp, /* out: index in leaf block */
  1300. xfs_dabuf_t **dbpp) /* out: data buffer */
  1301. {
  1302. xfs_dir2_db_t curdb; /* current data block number */
  1303. xfs_dabuf_t *dbp; /* data buffer */
  1304. xfs_dir2_data_entry_t *dep; /* data entry */
  1305. xfs_inode_t *dp; /* incore directory inode */
  1306. int error; /* error return code */
  1307. int index; /* index in leaf block */
  1308. xfs_dabuf_t *lbp; /* leaf buffer */
  1309. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1310. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1311. xfs_mount_t *mp; /* filesystem mount point */
  1312. xfs_dir2_db_t newdb; /* new data block number */
  1313. xfs_trans_t *tp; /* transaction pointer */
  1314. dp = args->dp;
  1315. tp = args->trans;
  1316. mp = dp->i_mount;
  1317. /*
  1318. * Read the leaf block into the buffer.
  1319. */
  1320. if ((error =
  1321. xfs_da_read_buf(tp, dp, mp->m_dirleafblk, -1, &lbp,
  1322. XFS_DATA_FORK))) {
  1323. return error;
  1324. }
  1325. *lbpp = lbp;
  1326. leaf = lbp->data;
  1327. xfs_dir2_leaf_check(dp, lbp);
  1328. /*
  1329. * Look for the first leaf entry with our hash value.
  1330. */
  1331. index = xfs_dir2_leaf_search_hash(args, lbp);
  1332. /*
  1333. * Loop over all the entries with the right hash value
  1334. * looking to match the name.
  1335. */
  1336. for (lep = &leaf->ents[index], dbp = NULL, curdb = -1;
  1337. index < be16_to_cpu(leaf->hdr.count) && be32_to_cpu(lep->hashval) == args->hashval;
  1338. lep++, index++) {
  1339. /*
  1340. * Skip over stale leaf entries.
  1341. */
  1342. if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
  1343. continue;
  1344. /*
  1345. * Get the new data block number.
  1346. */
  1347. newdb = XFS_DIR2_DATAPTR_TO_DB(mp, be32_to_cpu(lep->address));
  1348. /*
  1349. * If it's not the same as the old data block number,
  1350. * need to pitch the old one and read the new one.
  1351. */
  1352. if (newdb != curdb) {
  1353. if (dbp)
  1354. xfs_da_brelse(tp, dbp);
  1355. if ((error =
  1356. xfs_da_read_buf(tp, dp,
  1357. XFS_DIR2_DB_TO_DA(mp, newdb), -1, &dbp,
  1358. XFS_DATA_FORK))) {
  1359. xfs_da_brelse(tp, lbp);
  1360. return error;
  1361. }
  1362. xfs_dir2_data_check(dp, dbp);
  1363. curdb = newdb;
  1364. }
  1365. /*
  1366. * Point to the data entry.
  1367. */
  1368. dep = (xfs_dir2_data_entry_t *)
  1369. ((char *)dbp->data +
  1370. XFS_DIR2_DATAPTR_TO_OFF(mp, be32_to_cpu(lep->address)));
  1371. /*
  1372. * If it matches then return it.
  1373. */
  1374. if (dep->namelen == args->namelen &&
  1375. dep->name[0] == args->name[0] &&
  1376. memcmp(dep->name, args->name, args->namelen) == 0) {
  1377. *dbpp = dbp;
  1378. *indexp = index;
  1379. return 0;
  1380. }
  1381. }
  1382. /*
  1383. * No match found, return ENOENT.
  1384. */
  1385. ASSERT(args->oknoent);
  1386. if (dbp)
  1387. xfs_da_brelse(tp, dbp);
  1388. xfs_da_brelse(tp, lbp);
  1389. return XFS_ERROR(ENOENT);
  1390. }
  1391. /*
  1392. * Remove an entry from a leaf format directory.
  1393. */
  1394. int /* error */
  1395. xfs_dir2_leaf_removename(
  1396. xfs_da_args_t *args) /* operation arguments */
  1397. {
  1398. __be16 *bestsp; /* leaf block best freespace */
  1399. xfs_dir2_data_t *data; /* data block structure */
  1400. xfs_dir2_db_t db; /* data block number */
  1401. xfs_dabuf_t *dbp; /* data block buffer */
  1402. xfs_dir2_data_entry_t *dep; /* data entry structure */
  1403. xfs_inode_t *dp; /* incore directory inode */
  1404. int error; /* error return code */
  1405. xfs_dir2_db_t i; /* temporary data block # */
  1406. int index; /* index into leaf entries */
  1407. xfs_dabuf_t *lbp; /* leaf buffer */
  1408. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1409. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1410. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1411. xfs_mount_t *mp; /* filesystem mount point */
  1412. int needlog; /* need to log data header */
  1413. int needscan; /* need to rescan data frees */
  1414. xfs_dir2_data_off_t oldbest; /* old value of best free */
  1415. xfs_trans_t *tp; /* transaction pointer */
  1416. xfs_dir2_trace_args("leaf_removename", args);
  1417. /*
  1418. * Lookup the leaf entry, get the leaf and data blocks read in.
  1419. */
  1420. if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
  1421. return error;
  1422. }
  1423. dp = args->dp;
  1424. tp = args->trans;
  1425. mp = dp->i_mount;
  1426. leaf = lbp->data;
  1427. data = dbp->data;
  1428. xfs_dir2_data_check(dp, dbp);
  1429. /*
  1430. * Point to the leaf entry, use that to point to the data entry.
  1431. */
  1432. lep = &leaf->ents[index];
  1433. db = XFS_DIR2_DATAPTR_TO_DB(mp, be32_to_cpu(lep->address));
  1434. dep = (xfs_dir2_data_entry_t *)
  1435. ((char *)data + XFS_DIR2_DATAPTR_TO_OFF(mp, be32_to_cpu(lep->address)));
  1436. needscan = needlog = 0;
  1437. oldbest = be16_to_cpu(data->hdr.bestfree[0].length);
  1438. ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
  1439. bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
  1440. ASSERT(be16_to_cpu(bestsp[db]) == oldbest);
  1441. /*
  1442. * Mark the former data entry unused.
  1443. */
  1444. xfs_dir2_data_make_free(tp, dbp,
  1445. (xfs_dir2_data_aoff_t)((char *)dep - (char *)data),
  1446. XFS_DIR2_DATA_ENTSIZE(dep->namelen), &needlog, &needscan);
  1447. /*
  1448. * We just mark the leaf entry stale by putting a null in it.
  1449. */
  1450. be16_add(&leaf->hdr.stale, 1);
  1451. xfs_dir2_leaf_log_header(tp, lbp);
  1452. lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
  1453. xfs_dir2_leaf_log_ents(tp, lbp, index, index);
  1454. /*
  1455. * Scan the freespace in the data block again if necessary,
  1456. * log the data block header if necessary.
  1457. */
  1458. if (needscan)
  1459. xfs_dir2_data_freescan(mp, data, &needlog, NULL);
  1460. if (needlog)
  1461. xfs_dir2_data_log_header(tp, dbp);
  1462. /*
  1463. * If the longest freespace in the data block has changed,
  1464. * put the new value in the bests table and log that.
  1465. */
  1466. if (be16_to_cpu(data->hdr.bestfree[0].length) != oldbest) {
  1467. bestsp[db] = data->hdr.bestfree[0].length;
  1468. xfs_dir2_leaf_log_bests(tp, lbp, db, db);
  1469. }
  1470. xfs_dir2_data_check(dp, dbp);
  1471. /*
  1472. * If the data block is now empty then get rid of the data block.
  1473. */
  1474. if (be16_to_cpu(data->hdr.bestfree[0].length) ==
  1475. mp->m_dirblksize - (uint)sizeof(data->hdr)) {
  1476. ASSERT(db != mp->m_dirdatablk);
  1477. if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
  1478. /*
  1479. * Nope, can't get rid of it because it caused
  1480. * allocation of a bmap btree block to do so.
  1481. * Just go on, returning success, leaving the
  1482. * empty block in place.
  1483. */
  1484. if (error == ENOSPC && args->total == 0) {
  1485. xfs_da_buf_done(dbp);
  1486. error = 0;
  1487. }
  1488. xfs_dir2_leaf_check(dp, lbp);
  1489. xfs_da_buf_done(lbp);
  1490. return error;
  1491. }
  1492. dbp = NULL;
  1493. /*
  1494. * If this is the last data block then compact the
  1495. * bests table by getting rid of entries.
  1496. */
  1497. if (db == be32_to_cpu(ltp->bestcount) - 1) {
  1498. /*
  1499. * Look for the last active entry (i).
  1500. */
  1501. for (i = db - 1; i > 0; i--) {
  1502. if (be16_to_cpu(bestsp[i]) != NULLDATAOFF)
  1503. break;
  1504. }
  1505. /*
  1506. * Copy the table down so inactive entries at the
  1507. * end are removed.
  1508. */
  1509. memmove(&bestsp[db - i], bestsp,
  1510. (be32_to_cpu(ltp->bestcount) - (db - i)) * sizeof(*bestsp));
  1511. be32_add(&ltp->bestcount, -(db - i));
  1512. xfs_dir2_leaf_log_tail(tp, lbp);
  1513. xfs_dir2_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
  1514. } else
  1515. bestsp[db] = cpu_to_be16(NULLDATAOFF);
  1516. }
  1517. /*
  1518. * If the data block was not the first one, drop it.
  1519. */
  1520. else if (db != mp->m_dirdatablk && dbp != NULL) {
  1521. xfs_da_buf_done(dbp);
  1522. dbp = NULL;
  1523. }
  1524. xfs_dir2_leaf_check(dp, lbp);
  1525. /*
  1526. * See if we can convert to block form.
  1527. */
  1528. return xfs_dir2_leaf_to_block(args, lbp, dbp);
  1529. }
  1530. /*
  1531. * Replace the inode number in a leaf format directory entry.
  1532. */
  1533. int /* error */
  1534. xfs_dir2_leaf_replace(
  1535. xfs_da_args_t *args) /* operation arguments */
  1536. {
  1537. xfs_dabuf_t *dbp; /* data block buffer */
  1538. xfs_dir2_data_entry_t *dep; /* data block entry */
  1539. xfs_inode_t *dp; /* incore directory inode */
  1540. int error; /* error return code */
  1541. int index; /* index of leaf entry */
  1542. xfs_dabuf_t *lbp; /* leaf buffer */
  1543. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1544. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1545. xfs_trans_t *tp; /* transaction pointer */
  1546. xfs_dir2_trace_args("leaf_replace", args);
  1547. /*
  1548. * Look up the entry.
  1549. */
  1550. if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
  1551. return error;
  1552. }
  1553. dp = args->dp;
  1554. leaf = lbp->data;
  1555. /*
  1556. * Point to the leaf entry, get data address from it.
  1557. */
  1558. lep = &leaf->ents[index];
  1559. /*
  1560. * Point to the data entry.
  1561. */
  1562. dep = (xfs_dir2_data_entry_t *)
  1563. ((char *)dbp->data +
  1564. XFS_DIR2_DATAPTR_TO_OFF(dp->i_mount, be32_to_cpu(lep->address)));
  1565. ASSERT(args->inumber != be64_to_cpu(dep->inumber));
  1566. /*
  1567. * Put the new inode number in, log it.
  1568. */
  1569. dep->inumber = cpu_to_be64(args->inumber);
  1570. tp = args->trans;
  1571. xfs_dir2_data_log_entry(tp, dbp, dep);
  1572. xfs_da_buf_done(dbp);
  1573. xfs_dir2_leaf_check(dp, lbp);
  1574. xfs_da_brelse(tp, lbp);
  1575. return 0;
  1576. }
  1577. /*
  1578. * Return index in the leaf block (lbp) which is either the first
  1579. * one with this hash value, or if there are none, the insert point
  1580. * for that hash value.
  1581. */
  1582. int /* index value */
  1583. xfs_dir2_leaf_search_hash(
  1584. xfs_da_args_t *args, /* operation arguments */
  1585. xfs_dabuf_t *lbp) /* leaf buffer */
  1586. {
  1587. xfs_dahash_t hash=0; /* hash from this entry */
  1588. xfs_dahash_t hashwant; /* hash value looking for */
  1589. int high; /* high leaf index */
  1590. int low; /* low leaf index */
  1591. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1592. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1593. int mid=0; /* current leaf index */
  1594. leaf = lbp->data;
  1595. #ifndef __KERNEL__
  1596. if (!leaf->hdr.count)
  1597. return 0;
  1598. #endif
  1599. /*
  1600. * Note, the table cannot be empty, so we have to go through the loop.
  1601. * Binary search the leaf entries looking for our hash value.
  1602. */
  1603. for (lep = leaf->ents, low = 0, high = be16_to_cpu(leaf->hdr.count) - 1,
  1604. hashwant = args->hashval;
  1605. low <= high; ) {
  1606. mid = (low + high) >> 1;
  1607. if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant)
  1608. break;
  1609. if (hash < hashwant)
  1610. low = mid + 1;
  1611. else
  1612. high = mid - 1;
  1613. }
  1614. /*
  1615. * Found one, back up through all the equal hash values.
  1616. */
  1617. if (hash == hashwant) {
  1618. while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) {
  1619. mid--;
  1620. }
  1621. }
  1622. /*
  1623. * Need to point to an entry higher than ours.
  1624. */
  1625. else if (hash < hashwant)
  1626. mid++;
  1627. return mid;
  1628. }
  1629. /*
  1630. * Trim off a trailing data block. We know it's empty since the leaf
  1631. * freespace table says so.
  1632. */
  1633. int /* error */
  1634. xfs_dir2_leaf_trim_data(
  1635. xfs_da_args_t *args, /* operation arguments */
  1636. xfs_dabuf_t *lbp, /* leaf buffer */
  1637. xfs_dir2_db_t db) /* data block number */
  1638. {
  1639. __be16 *bestsp; /* leaf bests table */
  1640. #ifdef DEBUG
  1641. xfs_dir2_data_t *data; /* data block structure */
  1642. #endif
  1643. xfs_dabuf_t *dbp; /* data block buffer */
  1644. xfs_inode_t *dp; /* incore directory inode */
  1645. int error; /* error return value */
  1646. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1647. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1648. xfs_mount_t *mp; /* filesystem mount point */
  1649. xfs_trans_t *tp; /* transaction pointer */
  1650. dp = args->dp;
  1651. mp = dp->i_mount;
  1652. tp = args->trans;
  1653. /*
  1654. * Read the offending data block. We need its buffer.
  1655. */
  1656. if ((error = xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, db), -1, &dbp,
  1657. XFS_DATA_FORK))) {
  1658. return error;
  1659. }
  1660. #ifdef DEBUG
  1661. data = dbp->data;
  1662. ASSERT(be32_to_cpu(data->hdr.magic) == XFS_DIR2_DATA_MAGIC);
  1663. #endif
  1664. /* this seems to be an error
  1665. * data is only valid if DEBUG is defined?
  1666. * RMC 09/08/1999
  1667. */
  1668. leaf = lbp->data;
  1669. ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
  1670. ASSERT(be16_to_cpu(data->hdr.bestfree[0].length) ==
  1671. mp->m_dirblksize - (uint)sizeof(data->hdr));
  1672. ASSERT(db == be32_to_cpu(ltp->bestcount) - 1);
  1673. /*
  1674. * Get rid of the data block.
  1675. */
  1676. if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
  1677. ASSERT(error != ENOSPC);
  1678. xfs_da_brelse(tp, dbp);
  1679. return error;
  1680. }
  1681. /*
  1682. * Eliminate the last bests entry from the table.
  1683. */
  1684. bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
  1685. be32_add(&ltp->bestcount, -1);
  1686. memmove(&bestsp[1], &bestsp[0], be32_to_cpu(ltp->bestcount) * sizeof(*bestsp));
  1687. xfs_dir2_leaf_log_tail(tp, lbp);
  1688. xfs_dir2_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
  1689. return 0;
  1690. }
  1691. /*
  1692. * Convert node form directory to leaf form directory.
  1693. * The root of the node form dir needs to already be a LEAFN block.
  1694. * Just return if we can't do anything.
  1695. */
  1696. int /* error */
  1697. xfs_dir2_node_to_leaf(
  1698. xfs_da_state_t *state) /* directory operation state */
  1699. {
  1700. xfs_da_args_t *args; /* operation arguments */
  1701. xfs_inode_t *dp; /* incore directory inode */
  1702. int error; /* error return code */
  1703. xfs_dabuf_t *fbp; /* buffer for freespace block */
  1704. xfs_fileoff_t fo; /* freespace file offset */
  1705. xfs_dir2_free_t *free; /* freespace structure */
  1706. xfs_dabuf_t *lbp; /* buffer for leaf block */
  1707. xfs_dir2_leaf_tail_t *ltp; /* tail of leaf structure */
  1708. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1709. xfs_mount_t *mp; /* filesystem mount point */
  1710. int rval; /* successful free trim? */
  1711. xfs_trans_t *tp; /* transaction pointer */
  1712. /*
  1713. * There's more than a leaf level in the btree, so there must
  1714. * be multiple leafn blocks. Give up.
  1715. */
  1716. if (state->path.active > 1)
  1717. return 0;
  1718. args = state->args;
  1719. xfs_dir2_trace_args("node_to_leaf", args);
  1720. mp = state->mp;
  1721. dp = args->dp;
  1722. tp = args->trans;
  1723. /*
  1724. * Get the last offset in the file.
  1725. */
  1726. if ((error = xfs_bmap_last_offset(tp, dp, &fo, XFS_DATA_FORK))) {
  1727. return error;
  1728. }
  1729. fo -= mp->m_dirblkfsbs;
  1730. /*
  1731. * If there are freespace blocks other than the first one,
  1732. * take this opportunity to remove trailing empty freespace blocks
  1733. * that may have been left behind during no-space-reservation
  1734. * operations.
  1735. */
  1736. while (fo > mp->m_dirfreeblk) {
  1737. if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) {
  1738. return error;
  1739. }
  1740. if (rval)
  1741. fo -= mp->m_dirblkfsbs;
  1742. else
  1743. return 0;
  1744. }
  1745. /*
  1746. * Now find the block just before the freespace block.
  1747. */
  1748. if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) {
  1749. return error;
  1750. }
  1751. /*
  1752. * If it's not the single leaf block, give up.
  1753. */
  1754. if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + mp->m_dirblksize)
  1755. return 0;
  1756. lbp = state->path.blk[0].bp;
  1757. leaf = lbp->data;
  1758. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  1759. /*
  1760. * Read the freespace block.
  1761. */
  1762. if ((error = xfs_da_read_buf(tp, dp, mp->m_dirfreeblk, -1, &fbp,
  1763. XFS_DATA_FORK))) {
  1764. return error;
  1765. }
  1766. free = fbp->data;
  1767. ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
  1768. ASSERT(!free->hdr.firstdb);
  1769. /*
  1770. * Now see if the leafn and free data will fit in a leaf1.
  1771. * If not, release the buffer and give up.
  1772. */
  1773. if ((uint)sizeof(leaf->hdr) +
  1774. (be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale)) * (uint)sizeof(leaf->ents[0]) +
  1775. be32_to_cpu(free->hdr.nvalid) * (uint)sizeof(leaf->bests[0]) +
  1776. (uint)sizeof(leaf->tail) >
  1777. mp->m_dirblksize) {
  1778. xfs_da_brelse(tp, fbp);
  1779. return 0;
  1780. }
  1781. /*
  1782. * If the leaf has any stale entries in it, compress them out.
  1783. * The compact routine will log the header.
  1784. */
  1785. if (be16_to_cpu(leaf->hdr.stale))
  1786. xfs_dir2_leaf_compact(args, lbp);
  1787. else
  1788. xfs_dir2_leaf_log_header(tp, lbp);
  1789. leaf->hdr.info.magic = cpu_to_be16(XFS_DIR2_LEAF1_MAGIC);
  1790. /*
  1791. * Set up the leaf tail from the freespace block.
  1792. */
  1793. ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
  1794. ltp->bestcount = free->hdr.nvalid;
  1795. /*
  1796. * Set up the leaf bests table.
  1797. */
  1798. memcpy(XFS_DIR2_LEAF_BESTS_P(ltp), free->bests,
  1799. be32_to_cpu(ltp->bestcount) * sizeof(leaf->bests[0]));
  1800. xfs_dir2_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
  1801. xfs_dir2_leaf_log_tail(tp, lbp);
  1802. xfs_dir2_leaf_check(dp, lbp);
  1803. /*
  1804. * Get rid of the freespace block.
  1805. */
  1806. error = xfs_dir2_shrink_inode(args, XFS_DIR2_FREE_FIRSTDB(mp), fbp);
  1807. if (error) {
  1808. /*
  1809. * This can't fail here because it can only happen when
  1810. * punching out the middle of an extent, and this is an
  1811. * isolated block.
  1812. */
  1813. ASSERT(error != ENOSPC);
  1814. return error;
  1815. }
  1816. fbp = NULL;
  1817. /*
  1818. * Now see if we can convert the single-leaf directory
  1819. * down to a block form directory.
  1820. * This routine always kills the dabuf for the leaf, so
  1821. * eliminate it from the path.
  1822. */
  1823. error = xfs_dir2_leaf_to_block(args, lbp, NULL);
  1824. state->path.blk[0].bp = NULL;
  1825. return error;
  1826. }