xfs_dir2_leaf.c 50 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822
  1. /*
  2. * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
  3. * Copyright (c) 2013 Red Hat, Inc.
  4. * All Rights Reserved.
  5. *
  6. * This program is free software; you can redistribute it and/or
  7. * modify it under the terms of the GNU General Public License as
  8. * published by the Free Software Foundation.
  9. *
  10. * This program is distributed in the hope that it would be useful,
  11. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13. * GNU General Public License for more details.
  14. *
  15. * You should have received a copy of the GNU General Public License
  16. * along with this program; if not, write the Free Software Foundation,
  17. * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  18. */
  19. #include "xfs.h"
  20. #include "xfs_fs.h"
  21. #include "xfs_format.h"
  22. #include "xfs_log_format.h"
  23. #include "xfs_trans_resv.h"
  24. #include "xfs_mount.h"
  25. #include "xfs_da_format.h"
  26. #include "xfs_da_btree.h"
  27. #include "xfs_inode.h"
  28. #include "xfs_bmap.h"
  29. #include "xfs_dir2.h"
  30. #include "xfs_dir2_priv.h"
  31. #include "xfs_error.h"
  32. #include "xfs_trace.h"
  33. #include "xfs_trans.h"
  34. #include "xfs_buf_item.h"
  35. #include "xfs_cksum.h"
  36. #include "xfs_log.h"
  37. /*
  38. * Local function declarations.
  39. */
  40. static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, struct xfs_buf **lbpp,
  41. int *indexp, struct xfs_buf **dbpp);
  42. static void xfs_dir3_leaf_log_bests(struct xfs_da_args *args,
  43. struct xfs_buf *bp, int first, int last);
  44. static void xfs_dir3_leaf_log_tail(struct xfs_da_args *args,
  45. struct xfs_buf *bp);
  46. /*
  47. * Check the internal consistency of a leaf1 block.
  48. * Pop an assert if something is wrong.
  49. */
  50. #ifdef DEBUG
  51. #define xfs_dir3_leaf_check(dp, bp) \
  52. do { \
  53. if (!xfs_dir3_leaf1_check((dp), (bp))) \
  54. ASSERT(0); \
  55. } while (0);
  56. STATIC bool
  57. xfs_dir3_leaf1_check(
  58. struct xfs_inode *dp,
  59. struct xfs_buf *bp)
  60. {
  61. struct xfs_dir2_leaf *leaf = bp->b_addr;
  62. struct xfs_dir3_icleaf_hdr leafhdr;
  63. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  64. if (leafhdr.magic == XFS_DIR3_LEAF1_MAGIC) {
  65. struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
  66. if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
  67. return false;
  68. } else if (leafhdr.magic != XFS_DIR2_LEAF1_MAGIC)
  69. return false;
  70. return xfs_dir3_leaf_check_int(dp->i_mount, dp, &leafhdr, leaf);
  71. }
  72. #else
  73. #define xfs_dir3_leaf_check(dp, bp)
  74. #endif
  75. bool
  76. xfs_dir3_leaf_check_int(
  77. struct xfs_mount *mp,
  78. struct xfs_inode *dp,
  79. struct xfs_dir3_icleaf_hdr *hdr,
  80. struct xfs_dir2_leaf *leaf)
  81. {
  82. struct xfs_dir2_leaf_entry *ents;
  83. xfs_dir2_leaf_tail_t *ltp;
  84. int stale;
  85. int i;
  86. const struct xfs_dir_ops *ops;
  87. struct xfs_dir3_icleaf_hdr leafhdr;
  88. struct xfs_da_geometry *geo = mp->m_dir_geo;
  89. /*
  90. * we can be passed a null dp here from a verifier, so we need to go the
  91. * hard way to get them.
  92. */
  93. ops = xfs_dir_get_ops(mp, dp);
  94. if (!hdr) {
  95. ops->leaf_hdr_from_disk(&leafhdr, leaf);
  96. hdr = &leafhdr;
  97. }
  98. ents = ops->leaf_ents_p(leaf);
  99. ltp = xfs_dir2_leaf_tail_p(geo, leaf);
  100. /*
  101. * XXX (dgc): This value is not restrictive enough.
  102. * Should factor in the size of the bests table as well.
  103. * We can deduce a value for that from di_size.
  104. */
  105. if (hdr->count > ops->leaf_max_ents(geo))
  106. return false;
  107. /* Leaves and bests don't overlap in leaf format. */
  108. if ((hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
  109. hdr->magic == XFS_DIR3_LEAF1_MAGIC) &&
  110. (char *)&ents[hdr->count] > (char *)xfs_dir2_leaf_bests_p(ltp))
  111. return false;
  112. /* Check hash value order, count stale entries. */
  113. for (i = stale = 0; i < hdr->count; i++) {
  114. if (i + 1 < hdr->count) {
  115. if (be32_to_cpu(ents[i].hashval) >
  116. be32_to_cpu(ents[i + 1].hashval))
  117. return false;
  118. }
  119. if (ents[i].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
  120. stale++;
  121. }
  122. if (hdr->stale != stale)
  123. return false;
  124. return true;
  125. }
  126. /*
  127. * We verify the magic numbers before decoding the leaf header so that on debug
  128. * kernels we don't get assertion failures in xfs_dir3_leaf_hdr_from_disk() due
  129. * to incorrect magic numbers.
  130. */
  131. static bool
  132. xfs_dir3_leaf_verify(
  133. struct xfs_buf *bp,
  134. __uint16_t magic)
  135. {
  136. struct xfs_mount *mp = bp->b_target->bt_mount;
  137. struct xfs_dir2_leaf *leaf = bp->b_addr;
  138. ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
  139. if (xfs_sb_version_hascrc(&mp->m_sb)) {
  140. struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
  141. __uint16_t magic3;
  142. magic3 = (magic == XFS_DIR2_LEAF1_MAGIC) ? XFS_DIR3_LEAF1_MAGIC
  143. : XFS_DIR3_LEAFN_MAGIC;
  144. if (leaf3->info.hdr.magic != cpu_to_be16(magic3))
  145. return false;
  146. if (!uuid_equal(&leaf3->info.uuid, &mp->m_sb.sb_meta_uuid))
  147. return false;
  148. if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
  149. return false;
  150. if (!xfs_log_check_lsn(mp, be64_to_cpu(leaf3->info.lsn)))
  151. return false;
  152. } else {
  153. if (leaf->hdr.info.magic != cpu_to_be16(magic))
  154. return false;
  155. }
  156. return xfs_dir3_leaf_check_int(mp, NULL, NULL, leaf);
  157. }
  158. static void
  159. __read_verify(
  160. struct xfs_buf *bp,
  161. __uint16_t magic)
  162. {
  163. struct xfs_mount *mp = bp->b_target->bt_mount;
  164. if (xfs_sb_version_hascrc(&mp->m_sb) &&
  165. !xfs_buf_verify_cksum(bp, XFS_DIR3_LEAF_CRC_OFF))
  166. xfs_buf_ioerror(bp, -EFSBADCRC);
  167. else if (!xfs_dir3_leaf_verify(bp, magic))
  168. xfs_buf_ioerror(bp, -EFSCORRUPTED);
  169. if (bp->b_error)
  170. xfs_verifier_error(bp);
  171. }
  172. static void
  173. __write_verify(
  174. struct xfs_buf *bp,
  175. __uint16_t magic)
  176. {
  177. struct xfs_mount *mp = bp->b_target->bt_mount;
  178. struct xfs_buf_log_item *bip = bp->b_fspriv;
  179. struct xfs_dir3_leaf_hdr *hdr3 = bp->b_addr;
  180. if (!xfs_dir3_leaf_verify(bp, magic)) {
  181. xfs_buf_ioerror(bp, -EFSCORRUPTED);
  182. xfs_verifier_error(bp);
  183. return;
  184. }
  185. if (!xfs_sb_version_hascrc(&mp->m_sb))
  186. return;
  187. if (bip)
  188. hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
  189. xfs_buf_update_cksum(bp, XFS_DIR3_LEAF_CRC_OFF);
  190. }
  191. static void
  192. xfs_dir3_leaf1_read_verify(
  193. struct xfs_buf *bp)
  194. {
  195. __read_verify(bp, XFS_DIR2_LEAF1_MAGIC);
  196. }
  197. static void
  198. xfs_dir3_leaf1_write_verify(
  199. struct xfs_buf *bp)
  200. {
  201. __write_verify(bp, XFS_DIR2_LEAF1_MAGIC);
  202. }
  203. static void
  204. xfs_dir3_leafn_read_verify(
  205. struct xfs_buf *bp)
  206. {
  207. __read_verify(bp, XFS_DIR2_LEAFN_MAGIC);
  208. }
  209. static void
  210. xfs_dir3_leafn_write_verify(
  211. struct xfs_buf *bp)
  212. {
  213. __write_verify(bp, XFS_DIR2_LEAFN_MAGIC);
  214. }
  215. const struct xfs_buf_ops xfs_dir3_leaf1_buf_ops = {
  216. .verify_read = xfs_dir3_leaf1_read_verify,
  217. .verify_write = xfs_dir3_leaf1_write_verify,
  218. };
  219. const struct xfs_buf_ops xfs_dir3_leafn_buf_ops = {
  220. .verify_read = xfs_dir3_leafn_read_verify,
  221. .verify_write = xfs_dir3_leafn_write_verify,
  222. };
  223. static int
  224. xfs_dir3_leaf_read(
  225. struct xfs_trans *tp,
  226. struct xfs_inode *dp,
  227. xfs_dablk_t fbno,
  228. xfs_daddr_t mappedbno,
  229. struct xfs_buf **bpp)
  230. {
  231. int err;
  232. err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
  233. XFS_DATA_FORK, &xfs_dir3_leaf1_buf_ops);
  234. if (!err && tp)
  235. xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAF1_BUF);
  236. return err;
  237. }
  238. int
  239. xfs_dir3_leafn_read(
  240. struct xfs_trans *tp,
  241. struct xfs_inode *dp,
  242. xfs_dablk_t fbno,
  243. xfs_daddr_t mappedbno,
  244. struct xfs_buf **bpp)
  245. {
  246. int err;
  247. err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
  248. XFS_DATA_FORK, &xfs_dir3_leafn_buf_ops);
  249. if (!err && tp)
  250. xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAFN_BUF);
  251. return err;
  252. }
  253. /*
  254. * Initialize a new leaf block, leaf1 or leafn magic accepted.
  255. */
  256. static void
  257. xfs_dir3_leaf_init(
  258. struct xfs_mount *mp,
  259. struct xfs_trans *tp,
  260. struct xfs_buf *bp,
  261. xfs_ino_t owner,
  262. __uint16_t type)
  263. {
  264. struct xfs_dir2_leaf *leaf = bp->b_addr;
  265. ASSERT(type == XFS_DIR2_LEAF1_MAGIC || type == XFS_DIR2_LEAFN_MAGIC);
  266. if (xfs_sb_version_hascrc(&mp->m_sb)) {
  267. struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
  268. memset(leaf3, 0, sizeof(*leaf3));
  269. leaf3->info.hdr.magic = (type == XFS_DIR2_LEAF1_MAGIC)
  270. ? cpu_to_be16(XFS_DIR3_LEAF1_MAGIC)
  271. : cpu_to_be16(XFS_DIR3_LEAFN_MAGIC);
  272. leaf3->info.blkno = cpu_to_be64(bp->b_bn);
  273. leaf3->info.owner = cpu_to_be64(owner);
  274. uuid_copy(&leaf3->info.uuid, &mp->m_sb.sb_meta_uuid);
  275. } else {
  276. memset(leaf, 0, sizeof(*leaf));
  277. leaf->hdr.info.magic = cpu_to_be16(type);
  278. }
  279. /*
  280. * If it's a leaf-format directory initialize the tail.
  281. * Caller is responsible for initialising the bests table.
  282. */
  283. if (type == XFS_DIR2_LEAF1_MAGIC) {
  284. struct xfs_dir2_leaf_tail *ltp;
  285. ltp = xfs_dir2_leaf_tail_p(mp->m_dir_geo, leaf);
  286. ltp->bestcount = 0;
  287. bp->b_ops = &xfs_dir3_leaf1_buf_ops;
  288. xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAF1_BUF);
  289. } else {
  290. bp->b_ops = &xfs_dir3_leafn_buf_ops;
  291. xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
  292. }
  293. }
  294. int
  295. xfs_dir3_leaf_get_buf(
  296. xfs_da_args_t *args,
  297. xfs_dir2_db_t bno,
  298. struct xfs_buf **bpp,
  299. __uint16_t magic)
  300. {
  301. struct xfs_inode *dp = args->dp;
  302. struct xfs_trans *tp = args->trans;
  303. struct xfs_mount *mp = dp->i_mount;
  304. struct xfs_buf *bp;
  305. int error;
  306. ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
  307. ASSERT(bno >= xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET) &&
  308. bno < xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET));
  309. error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(args->geo, bno),
  310. -1, &bp, XFS_DATA_FORK);
  311. if (error)
  312. return error;
  313. xfs_dir3_leaf_init(mp, tp, bp, dp->i_ino, magic);
  314. xfs_dir3_leaf_log_header(args, bp);
  315. if (magic == XFS_DIR2_LEAF1_MAGIC)
  316. xfs_dir3_leaf_log_tail(args, bp);
  317. *bpp = bp;
  318. return 0;
  319. }
  320. /*
  321. * Convert a block form directory to a leaf form directory.
  322. */
  323. int /* error */
  324. xfs_dir2_block_to_leaf(
  325. xfs_da_args_t *args, /* operation arguments */
  326. struct xfs_buf *dbp) /* input block's buffer */
  327. {
  328. __be16 *bestsp; /* leaf's bestsp entries */
  329. xfs_dablk_t blkno; /* leaf block's bno */
  330. xfs_dir2_data_hdr_t *hdr; /* block header */
  331. xfs_dir2_leaf_entry_t *blp; /* block's leaf entries */
  332. xfs_dir2_block_tail_t *btp; /* block's tail */
  333. xfs_inode_t *dp; /* incore directory inode */
  334. int error; /* error return code */
  335. struct xfs_buf *lbp; /* leaf block's buffer */
  336. xfs_dir2_db_t ldb; /* leaf block's bno */
  337. xfs_dir2_leaf_t *leaf; /* leaf structure */
  338. xfs_dir2_leaf_tail_t *ltp; /* leaf's tail */
  339. int needlog; /* need to log block header */
  340. int needscan; /* need to rescan bestfree */
  341. xfs_trans_t *tp; /* transaction pointer */
  342. struct xfs_dir2_data_free *bf;
  343. struct xfs_dir2_leaf_entry *ents;
  344. struct xfs_dir3_icleaf_hdr leafhdr;
  345. trace_xfs_dir2_block_to_leaf(args);
  346. dp = args->dp;
  347. tp = args->trans;
  348. /*
  349. * Add the leaf block to the inode.
  350. * This interface will only put blocks in the leaf/node range.
  351. * Since that's empty now, we'll get the root (block 0 in range).
  352. */
  353. if ((error = xfs_da_grow_inode(args, &blkno))) {
  354. return error;
  355. }
  356. ldb = xfs_dir2_da_to_db(args->geo, blkno);
  357. ASSERT(ldb == xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET));
  358. /*
  359. * Initialize the leaf block, get a buffer for it.
  360. */
  361. error = xfs_dir3_leaf_get_buf(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC);
  362. if (error)
  363. return error;
  364. leaf = lbp->b_addr;
  365. hdr = dbp->b_addr;
  366. xfs_dir3_data_check(dp, dbp);
  367. btp = xfs_dir2_block_tail_p(args->geo, hdr);
  368. blp = xfs_dir2_block_leaf_p(btp);
  369. bf = dp->d_ops->data_bestfree_p(hdr);
  370. ents = dp->d_ops->leaf_ents_p(leaf);
  371. /*
  372. * Set the counts in the leaf header.
  373. */
  374. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  375. leafhdr.count = be32_to_cpu(btp->count);
  376. leafhdr.stale = be32_to_cpu(btp->stale);
  377. dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
  378. xfs_dir3_leaf_log_header(args, lbp);
  379. /*
  380. * Could compact these but I think we always do the conversion
  381. * after squeezing out stale entries.
  382. */
  383. memcpy(ents, blp, be32_to_cpu(btp->count) * sizeof(xfs_dir2_leaf_entry_t));
  384. xfs_dir3_leaf_log_ents(args, lbp, 0, leafhdr.count - 1);
  385. needscan = 0;
  386. needlog = 1;
  387. /*
  388. * Make the space formerly occupied by the leaf entries and block
  389. * tail be free.
  390. */
  391. xfs_dir2_data_make_free(args, dbp,
  392. (xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr),
  393. (xfs_dir2_data_aoff_t)((char *)hdr + args->geo->blksize -
  394. (char *)blp),
  395. &needlog, &needscan);
  396. /*
  397. * Fix up the block header, make it a data block.
  398. */
  399. dbp->b_ops = &xfs_dir3_data_buf_ops;
  400. xfs_trans_buf_set_type(tp, dbp, XFS_BLFT_DIR_DATA_BUF);
  401. if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC))
  402. hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
  403. else
  404. hdr->magic = cpu_to_be32(XFS_DIR3_DATA_MAGIC);
  405. if (needscan)
  406. xfs_dir2_data_freescan(dp, hdr, &needlog);
  407. /*
  408. * Set up leaf tail and bests table.
  409. */
  410. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  411. ltp->bestcount = cpu_to_be32(1);
  412. bestsp = xfs_dir2_leaf_bests_p(ltp);
  413. bestsp[0] = bf[0].length;
  414. /*
  415. * Log the data header and leaf bests table.
  416. */
  417. if (needlog)
  418. xfs_dir2_data_log_header(args, dbp);
  419. xfs_dir3_leaf_check(dp, lbp);
  420. xfs_dir3_data_check(dp, dbp);
  421. xfs_dir3_leaf_log_bests(args, lbp, 0, 0);
  422. return 0;
  423. }
  424. STATIC void
  425. xfs_dir3_leaf_find_stale(
  426. struct xfs_dir3_icleaf_hdr *leafhdr,
  427. struct xfs_dir2_leaf_entry *ents,
  428. int index,
  429. int *lowstale,
  430. int *highstale)
  431. {
  432. /*
  433. * Find the first stale entry before our index, if any.
  434. */
  435. for (*lowstale = index - 1; *lowstale >= 0; --*lowstale) {
  436. if (ents[*lowstale].address ==
  437. cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
  438. break;
  439. }
  440. /*
  441. * Find the first stale entry at or after our index, if any.
  442. * Stop if the result would require moving more entries than using
  443. * lowstale.
  444. */
  445. for (*highstale = index; *highstale < leafhdr->count; ++*highstale) {
  446. if (ents[*highstale].address ==
  447. cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
  448. break;
  449. if (*lowstale >= 0 && index - *lowstale <= *highstale - index)
  450. break;
  451. }
  452. }
  453. struct xfs_dir2_leaf_entry *
  454. xfs_dir3_leaf_find_entry(
  455. struct xfs_dir3_icleaf_hdr *leafhdr,
  456. struct xfs_dir2_leaf_entry *ents,
  457. int index, /* leaf table position */
  458. int compact, /* need to compact leaves */
  459. int lowstale, /* index of prev stale leaf */
  460. int highstale, /* index of next stale leaf */
  461. int *lfloglow, /* low leaf logging index */
  462. int *lfloghigh) /* high leaf logging index */
  463. {
  464. if (!leafhdr->stale) {
  465. xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
  466. /*
  467. * Now we need to make room to insert the leaf entry.
  468. *
  469. * If there are no stale entries, just insert a hole at index.
  470. */
  471. lep = &ents[index];
  472. if (index < leafhdr->count)
  473. memmove(lep + 1, lep,
  474. (leafhdr->count - index) * sizeof(*lep));
  475. /*
  476. * Record low and high logging indices for the leaf.
  477. */
  478. *lfloglow = index;
  479. *lfloghigh = leafhdr->count++;
  480. return lep;
  481. }
  482. /*
  483. * There are stale entries.
  484. *
  485. * We will use one of them for the new entry. It's probably not at
  486. * the right location, so we'll have to shift some up or down first.
  487. *
  488. * If we didn't compact before, we need to find the nearest stale
  489. * entries before and after our insertion point.
  490. */
  491. if (compact == 0)
  492. xfs_dir3_leaf_find_stale(leafhdr, ents, index,
  493. &lowstale, &highstale);
  494. /*
  495. * If the low one is better, use it.
  496. */
  497. if (lowstale >= 0 &&
  498. (highstale == leafhdr->count ||
  499. index - lowstale - 1 < highstale - index)) {
  500. ASSERT(index - lowstale - 1 >= 0);
  501. ASSERT(ents[lowstale].address ==
  502. cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
  503. /*
  504. * Copy entries up to cover the stale entry and make room
  505. * for the new entry.
  506. */
  507. if (index - lowstale - 1 > 0) {
  508. memmove(&ents[lowstale], &ents[lowstale + 1],
  509. (index - lowstale - 1) *
  510. sizeof(xfs_dir2_leaf_entry_t));
  511. }
  512. *lfloglow = MIN(lowstale, *lfloglow);
  513. *lfloghigh = MAX(index - 1, *lfloghigh);
  514. leafhdr->stale--;
  515. return &ents[index - 1];
  516. }
  517. /*
  518. * The high one is better, so use that one.
  519. */
  520. ASSERT(highstale - index >= 0);
  521. ASSERT(ents[highstale].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
  522. /*
  523. * Copy entries down to cover the stale entry and make room for the
  524. * new entry.
  525. */
  526. if (highstale - index > 0) {
  527. memmove(&ents[index + 1], &ents[index],
  528. (highstale - index) * sizeof(xfs_dir2_leaf_entry_t));
  529. }
  530. *lfloglow = MIN(index, *lfloglow);
  531. *lfloghigh = MAX(highstale, *lfloghigh);
  532. leafhdr->stale--;
  533. return &ents[index];
  534. }
  535. /*
  536. * Add an entry to a leaf form directory.
  537. */
  538. int /* error */
  539. xfs_dir2_leaf_addname(
  540. xfs_da_args_t *args) /* operation arguments */
  541. {
  542. __be16 *bestsp; /* freespace table in leaf */
  543. int compact; /* need to compact leaves */
  544. xfs_dir2_data_hdr_t *hdr; /* data block header */
  545. struct xfs_buf *dbp; /* data block buffer */
  546. xfs_dir2_data_entry_t *dep; /* data block entry */
  547. xfs_inode_t *dp; /* incore directory inode */
  548. xfs_dir2_data_unused_t *dup; /* data unused entry */
  549. int error; /* error return value */
  550. int grown; /* allocated new data block */
  551. int highstale; /* index of next stale leaf */
  552. int i; /* temporary, index */
  553. int index; /* leaf table position */
  554. struct xfs_buf *lbp; /* leaf's buffer */
  555. xfs_dir2_leaf_t *leaf; /* leaf structure */
  556. int length; /* length of new entry */
  557. xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
  558. int lfloglow; /* low leaf logging index */
  559. int lfloghigh; /* high leaf logging index */
  560. int lowstale; /* index of prev stale leaf */
  561. xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */
  562. int needbytes; /* leaf block bytes needed */
  563. int needlog; /* need to log data header */
  564. int needscan; /* need to rescan data free */
  565. __be16 *tagp; /* end of data entry */
  566. xfs_trans_t *tp; /* transaction pointer */
  567. xfs_dir2_db_t use_block; /* data block number */
  568. struct xfs_dir2_data_free *bf; /* bestfree table */
  569. struct xfs_dir2_leaf_entry *ents;
  570. struct xfs_dir3_icleaf_hdr leafhdr;
  571. trace_xfs_dir2_leaf_addname(args);
  572. dp = args->dp;
  573. tp = args->trans;
  574. error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, -1, &lbp);
  575. if (error)
  576. return error;
  577. /*
  578. * Look up the entry by hash value and name.
  579. * We know it's not there, our caller has already done a lookup.
  580. * So the index is of the entry to insert in front of.
  581. * But if there are dup hash values the index is of the first of those.
  582. */
  583. index = xfs_dir2_leaf_search_hash(args, lbp);
  584. leaf = lbp->b_addr;
  585. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  586. ents = dp->d_ops->leaf_ents_p(leaf);
  587. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  588. bestsp = xfs_dir2_leaf_bests_p(ltp);
  589. length = dp->d_ops->data_entsize(args->namelen);
  590. /*
  591. * See if there are any entries with the same hash value
  592. * and space in their block for the new entry.
  593. * This is good because it puts multiple same-hash value entries
  594. * in a data block, improving the lookup of those entries.
  595. */
  596. for (use_block = -1, lep = &ents[index];
  597. index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
  598. index++, lep++) {
  599. if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
  600. continue;
  601. i = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address));
  602. ASSERT(i < be32_to_cpu(ltp->bestcount));
  603. ASSERT(bestsp[i] != cpu_to_be16(NULLDATAOFF));
  604. if (be16_to_cpu(bestsp[i]) >= length) {
  605. use_block = i;
  606. break;
  607. }
  608. }
  609. /*
  610. * Didn't find a block yet, linear search all the data blocks.
  611. */
  612. if (use_block == -1) {
  613. for (i = 0; i < be32_to_cpu(ltp->bestcount); i++) {
  614. /*
  615. * Remember a block we see that's missing.
  616. */
  617. if (bestsp[i] == cpu_to_be16(NULLDATAOFF) &&
  618. use_block == -1)
  619. use_block = i;
  620. else if (be16_to_cpu(bestsp[i]) >= length) {
  621. use_block = i;
  622. break;
  623. }
  624. }
  625. }
  626. /*
  627. * How many bytes do we need in the leaf block?
  628. */
  629. needbytes = 0;
  630. if (!leafhdr.stale)
  631. needbytes += sizeof(xfs_dir2_leaf_entry_t);
  632. if (use_block == -1)
  633. needbytes += sizeof(xfs_dir2_data_off_t);
  634. /*
  635. * Now kill use_block if it refers to a missing block, so we
  636. * can use it as an indication of allocation needed.
  637. */
  638. if (use_block != -1 && bestsp[use_block] == cpu_to_be16(NULLDATAOFF))
  639. use_block = -1;
  640. /*
  641. * If we don't have enough free bytes but we can make enough
  642. * by compacting out stale entries, we'll do that.
  643. */
  644. if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes &&
  645. leafhdr.stale > 1)
  646. compact = 1;
  647. /*
  648. * Otherwise if we don't have enough free bytes we need to
  649. * convert to node form.
  650. */
  651. else if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes) {
  652. /*
  653. * Just checking or no space reservation, give up.
  654. */
  655. if ((args->op_flags & XFS_DA_OP_JUSTCHECK) ||
  656. args->total == 0) {
  657. xfs_trans_brelse(tp, lbp);
  658. return -ENOSPC;
  659. }
  660. /*
  661. * Convert to node form.
  662. */
  663. error = xfs_dir2_leaf_to_node(args, lbp);
  664. if (error)
  665. return error;
  666. /*
  667. * Then add the new entry.
  668. */
  669. return xfs_dir2_node_addname(args);
  670. }
  671. /*
  672. * Otherwise it will fit without compaction.
  673. */
  674. else
  675. compact = 0;
  676. /*
  677. * If just checking, then it will fit unless we needed to allocate
  678. * a new data block.
  679. */
  680. if (args->op_flags & XFS_DA_OP_JUSTCHECK) {
  681. xfs_trans_brelse(tp, lbp);
  682. return use_block == -1 ? -ENOSPC : 0;
  683. }
  684. /*
  685. * If no allocations are allowed, return now before we've
  686. * changed anything.
  687. */
  688. if (args->total == 0 && use_block == -1) {
  689. xfs_trans_brelse(tp, lbp);
  690. return -ENOSPC;
  691. }
  692. /*
  693. * Need to compact the leaf entries, removing stale ones.
  694. * Leave one stale entry behind - the one closest to our
  695. * insertion index - and we'll shift that one to our insertion
  696. * point later.
  697. */
  698. if (compact) {
  699. xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale,
  700. &highstale, &lfloglow, &lfloghigh);
  701. }
  702. /*
  703. * There are stale entries, so we'll need log-low and log-high
  704. * impossibly bad values later.
  705. */
  706. else if (leafhdr.stale) {
  707. lfloglow = leafhdr.count;
  708. lfloghigh = -1;
  709. }
  710. /*
  711. * If there was no data block space found, we need to allocate
  712. * a new one.
  713. */
  714. if (use_block == -1) {
  715. /*
  716. * Add the new data block.
  717. */
  718. if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE,
  719. &use_block))) {
  720. xfs_trans_brelse(tp, lbp);
  721. return error;
  722. }
  723. /*
  724. * Initialize the block.
  725. */
  726. if ((error = xfs_dir3_data_init(args, use_block, &dbp))) {
  727. xfs_trans_brelse(tp, lbp);
  728. return error;
  729. }
  730. /*
  731. * If we're adding a new data block on the end we need to
  732. * extend the bests table. Copy it up one entry.
  733. */
  734. if (use_block >= be32_to_cpu(ltp->bestcount)) {
  735. bestsp--;
  736. memmove(&bestsp[0], &bestsp[1],
  737. be32_to_cpu(ltp->bestcount) * sizeof(bestsp[0]));
  738. be32_add_cpu(&ltp->bestcount, 1);
  739. xfs_dir3_leaf_log_tail(args, lbp);
  740. xfs_dir3_leaf_log_bests(args, lbp, 0,
  741. be32_to_cpu(ltp->bestcount) - 1);
  742. }
  743. /*
  744. * If we're filling in a previously empty block just log it.
  745. */
  746. else
  747. xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block);
  748. hdr = dbp->b_addr;
  749. bf = dp->d_ops->data_bestfree_p(hdr);
  750. bestsp[use_block] = bf[0].length;
  751. grown = 1;
  752. } else {
  753. /*
  754. * Already had space in some data block.
  755. * Just read that one in.
  756. */
  757. error = xfs_dir3_data_read(tp, dp,
  758. xfs_dir2_db_to_da(args->geo, use_block),
  759. -1, &dbp);
  760. if (error) {
  761. xfs_trans_brelse(tp, lbp);
  762. return error;
  763. }
  764. hdr = dbp->b_addr;
  765. bf = dp->d_ops->data_bestfree_p(hdr);
  766. grown = 0;
  767. }
  768. /*
  769. * Point to the biggest freespace in our data block.
  770. */
  771. dup = (xfs_dir2_data_unused_t *)
  772. ((char *)hdr + be16_to_cpu(bf[0].offset));
  773. ASSERT(be16_to_cpu(dup->length) >= length);
  774. needscan = needlog = 0;
  775. /*
  776. * Mark the initial part of our freespace in use for the new entry.
  777. */
  778. xfs_dir2_data_use_free(args, dbp, dup,
  779. (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr), length,
  780. &needlog, &needscan);
  781. /*
  782. * Initialize our new entry (at last).
  783. */
  784. dep = (xfs_dir2_data_entry_t *)dup;
  785. dep->inumber = cpu_to_be64(args->inumber);
  786. dep->namelen = args->namelen;
  787. memcpy(dep->name, args->name, dep->namelen);
  788. dp->d_ops->data_put_ftype(dep, args->filetype);
  789. tagp = dp->d_ops->data_entry_tag_p(dep);
  790. *tagp = cpu_to_be16((char *)dep - (char *)hdr);
  791. /*
  792. * Need to scan fix up the bestfree table.
  793. */
  794. if (needscan)
  795. xfs_dir2_data_freescan(dp, hdr, &needlog);
  796. /*
  797. * Need to log the data block's header.
  798. */
  799. if (needlog)
  800. xfs_dir2_data_log_header(args, dbp);
  801. xfs_dir2_data_log_entry(args, dbp, dep);
  802. /*
  803. * If the bests table needs to be changed, do it.
  804. * Log the change unless we've already done that.
  805. */
  806. if (be16_to_cpu(bestsp[use_block]) != be16_to_cpu(bf[0].length)) {
  807. bestsp[use_block] = bf[0].length;
  808. if (!grown)
  809. xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block);
  810. }
  811. lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale,
  812. highstale, &lfloglow, &lfloghigh);
  813. /*
  814. * Fill in the new leaf entry.
  815. */
  816. lep->hashval = cpu_to_be32(args->hashval);
  817. lep->address = cpu_to_be32(
  818. xfs_dir2_db_off_to_dataptr(args->geo, use_block,
  819. be16_to_cpu(*tagp)));
  820. /*
  821. * Log the leaf fields and give up the buffers.
  822. */
  823. dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
  824. xfs_dir3_leaf_log_header(args, lbp);
  825. xfs_dir3_leaf_log_ents(args, lbp, lfloglow, lfloghigh);
  826. xfs_dir3_leaf_check(dp, lbp);
  827. xfs_dir3_data_check(dp, dbp);
  828. return 0;
  829. }
  830. /*
  831. * Compact out any stale entries in the leaf.
  832. * Log the header and changed leaf entries, if any.
  833. */
  834. void
  835. xfs_dir3_leaf_compact(
  836. xfs_da_args_t *args, /* operation arguments */
  837. struct xfs_dir3_icleaf_hdr *leafhdr,
  838. struct xfs_buf *bp) /* leaf buffer */
  839. {
  840. int from; /* source leaf index */
  841. xfs_dir2_leaf_t *leaf; /* leaf structure */
  842. int loglow; /* first leaf entry to log */
  843. int to; /* target leaf index */
  844. struct xfs_dir2_leaf_entry *ents;
  845. struct xfs_inode *dp = args->dp;
  846. leaf = bp->b_addr;
  847. if (!leafhdr->stale)
  848. return;
  849. /*
  850. * Compress out the stale entries in place.
  851. */
  852. ents = dp->d_ops->leaf_ents_p(leaf);
  853. for (from = to = 0, loglow = -1; from < leafhdr->count; from++) {
  854. if (ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
  855. continue;
  856. /*
  857. * Only actually copy the entries that are different.
  858. */
  859. if (from > to) {
  860. if (loglow == -1)
  861. loglow = to;
  862. ents[to] = ents[from];
  863. }
  864. to++;
  865. }
  866. /*
  867. * Update and log the header, log the leaf entries.
  868. */
  869. ASSERT(leafhdr->stale == from - to);
  870. leafhdr->count -= leafhdr->stale;
  871. leafhdr->stale = 0;
  872. dp->d_ops->leaf_hdr_to_disk(leaf, leafhdr);
  873. xfs_dir3_leaf_log_header(args, bp);
  874. if (loglow != -1)
  875. xfs_dir3_leaf_log_ents(args, bp, loglow, to - 1);
  876. }
  877. /*
  878. * Compact the leaf entries, removing stale ones.
  879. * Leave one stale entry behind - the one closest to our
  880. * insertion index - and the caller will shift that one to our insertion
  881. * point later.
  882. * Return new insertion index, where the remaining stale entry is,
  883. * and leaf logging indices.
  884. */
  885. void
  886. xfs_dir3_leaf_compact_x1(
  887. struct xfs_dir3_icleaf_hdr *leafhdr,
  888. struct xfs_dir2_leaf_entry *ents,
  889. int *indexp, /* insertion index */
  890. int *lowstalep, /* out: stale entry before us */
  891. int *highstalep, /* out: stale entry after us */
  892. int *lowlogp, /* out: low log index */
  893. int *highlogp) /* out: high log index */
  894. {
  895. int from; /* source copy index */
  896. int highstale; /* stale entry at/after index */
  897. int index; /* insertion index */
  898. int keepstale; /* source index of kept stale */
  899. int lowstale; /* stale entry before index */
  900. int newindex=0; /* new insertion index */
  901. int to; /* destination copy index */
  902. ASSERT(leafhdr->stale > 1);
  903. index = *indexp;
  904. xfs_dir3_leaf_find_stale(leafhdr, ents, index, &lowstale, &highstale);
  905. /*
  906. * Pick the better of lowstale and highstale.
  907. */
  908. if (lowstale >= 0 &&
  909. (highstale == leafhdr->count ||
  910. index - lowstale <= highstale - index))
  911. keepstale = lowstale;
  912. else
  913. keepstale = highstale;
  914. /*
  915. * Copy the entries in place, removing all the stale entries
  916. * except keepstale.
  917. */
  918. for (from = to = 0; from < leafhdr->count; from++) {
  919. /*
  920. * Notice the new value of index.
  921. */
  922. if (index == from)
  923. newindex = to;
  924. if (from != keepstale &&
  925. ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) {
  926. if (from == to)
  927. *lowlogp = to;
  928. continue;
  929. }
  930. /*
  931. * Record the new keepstale value for the insertion.
  932. */
  933. if (from == keepstale)
  934. lowstale = highstale = to;
  935. /*
  936. * Copy only the entries that have moved.
  937. */
  938. if (from > to)
  939. ents[to] = ents[from];
  940. to++;
  941. }
  942. ASSERT(from > to);
  943. /*
  944. * If the insertion point was past the last entry,
  945. * set the new insertion point accordingly.
  946. */
  947. if (index == from)
  948. newindex = to;
  949. *indexp = newindex;
  950. /*
  951. * Adjust the leaf header values.
  952. */
  953. leafhdr->count -= from - to;
  954. leafhdr->stale = 1;
  955. /*
  956. * Remember the low/high stale value only in the "right"
  957. * direction.
  958. */
  959. if (lowstale >= newindex)
  960. lowstale = -1;
  961. else
  962. highstale = leafhdr->count;
  963. *highlogp = leafhdr->count - 1;
  964. *lowstalep = lowstale;
  965. *highstalep = highstale;
  966. }
  967. /*
  968. * Log the bests entries indicated from a leaf1 block.
  969. */
  970. static void
  971. xfs_dir3_leaf_log_bests(
  972. struct xfs_da_args *args,
  973. struct xfs_buf *bp, /* leaf buffer */
  974. int first, /* first entry to log */
  975. int last) /* last entry to log */
  976. {
  977. __be16 *firstb; /* pointer to first entry */
  978. __be16 *lastb; /* pointer to last entry */
  979. struct xfs_dir2_leaf *leaf = bp->b_addr;
  980. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  981. ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
  982. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC));
  983. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  984. firstb = xfs_dir2_leaf_bests_p(ltp) + first;
  985. lastb = xfs_dir2_leaf_bests_p(ltp) + last;
  986. xfs_trans_log_buf(args->trans, bp,
  987. (uint)((char *)firstb - (char *)leaf),
  988. (uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1));
  989. }
  990. /*
  991. * Log the leaf entries indicated from a leaf1 or leafn block.
  992. */
  993. void
  994. xfs_dir3_leaf_log_ents(
  995. struct xfs_da_args *args,
  996. struct xfs_buf *bp,
  997. int first,
  998. int last)
  999. {
  1000. xfs_dir2_leaf_entry_t *firstlep; /* pointer to first entry */
  1001. xfs_dir2_leaf_entry_t *lastlep; /* pointer to last entry */
  1002. struct xfs_dir2_leaf *leaf = bp->b_addr;
  1003. struct xfs_dir2_leaf_entry *ents;
  1004. ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
  1005. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
  1006. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  1007. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
  1008. ents = args->dp->d_ops->leaf_ents_p(leaf);
  1009. firstlep = &ents[first];
  1010. lastlep = &ents[last];
  1011. xfs_trans_log_buf(args->trans, bp,
  1012. (uint)((char *)firstlep - (char *)leaf),
  1013. (uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1));
  1014. }
  1015. /*
  1016. * Log the header of the leaf1 or leafn block.
  1017. */
  1018. void
  1019. xfs_dir3_leaf_log_header(
  1020. struct xfs_da_args *args,
  1021. struct xfs_buf *bp)
  1022. {
  1023. struct xfs_dir2_leaf *leaf = bp->b_addr;
  1024. ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
  1025. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
  1026. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  1027. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
  1028. xfs_trans_log_buf(args->trans, bp,
  1029. (uint)((char *)&leaf->hdr - (char *)leaf),
  1030. args->dp->d_ops->leaf_hdr_size - 1);
  1031. }
  1032. /*
  1033. * Log the tail of the leaf1 block.
  1034. */
  1035. STATIC void
  1036. xfs_dir3_leaf_log_tail(
  1037. struct xfs_da_args *args,
  1038. struct xfs_buf *bp)
  1039. {
  1040. struct xfs_dir2_leaf *leaf = bp->b_addr;
  1041. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1042. ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
  1043. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
  1044. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  1045. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
  1046. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  1047. xfs_trans_log_buf(args->trans, bp, (uint)((char *)ltp - (char *)leaf),
  1048. (uint)(args->geo->blksize - 1));
  1049. }
  1050. /*
  1051. * Look up the entry referred to by args in the leaf format directory.
  1052. * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
  1053. * is also used by the node-format code.
  1054. */
  1055. int
  1056. xfs_dir2_leaf_lookup(
  1057. xfs_da_args_t *args) /* operation arguments */
  1058. {
  1059. struct xfs_buf *dbp; /* data block buffer */
  1060. xfs_dir2_data_entry_t *dep; /* data block entry */
  1061. xfs_inode_t *dp; /* incore directory inode */
  1062. int error; /* error return code */
  1063. int index; /* found entry index */
  1064. struct xfs_buf *lbp; /* leaf buffer */
  1065. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1066. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1067. xfs_trans_t *tp; /* transaction pointer */
  1068. struct xfs_dir2_leaf_entry *ents;
  1069. trace_xfs_dir2_leaf_lookup(args);
  1070. /*
  1071. * Look up name in the leaf block, returning both buffers and index.
  1072. */
  1073. if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
  1074. return error;
  1075. }
  1076. tp = args->trans;
  1077. dp = args->dp;
  1078. xfs_dir3_leaf_check(dp, lbp);
  1079. leaf = lbp->b_addr;
  1080. ents = dp->d_ops->leaf_ents_p(leaf);
  1081. /*
  1082. * Get to the leaf entry and contained data entry address.
  1083. */
  1084. lep = &ents[index];
  1085. /*
  1086. * Point to the data entry.
  1087. */
  1088. dep = (xfs_dir2_data_entry_t *)
  1089. ((char *)dbp->b_addr +
  1090. xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
  1091. /*
  1092. * Return the found inode number & CI name if appropriate
  1093. */
  1094. args->inumber = be64_to_cpu(dep->inumber);
  1095. args->filetype = dp->d_ops->data_get_ftype(dep);
  1096. error = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
  1097. xfs_trans_brelse(tp, dbp);
  1098. xfs_trans_brelse(tp, lbp);
  1099. return error;
  1100. }
  1101. /*
  1102. * Look up name/hash in the leaf block.
  1103. * Fill in indexp with the found index, and dbpp with the data buffer.
  1104. * If not found dbpp will be NULL, and ENOENT comes back.
  1105. * lbpp will always be filled in with the leaf buffer unless there's an error.
  1106. */
  1107. static int /* error */
  1108. xfs_dir2_leaf_lookup_int(
  1109. xfs_da_args_t *args, /* operation arguments */
  1110. struct xfs_buf **lbpp, /* out: leaf buffer */
  1111. int *indexp, /* out: index in leaf block */
  1112. struct xfs_buf **dbpp) /* out: data buffer */
  1113. {
  1114. xfs_dir2_db_t curdb = -1; /* current data block number */
  1115. struct xfs_buf *dbp = NULL; /* data buffer */
  1116. xfs_dir2_data_entry_t *dep; /* data entry */
  1117. xfs_inode_t *dp; /* incore directory inode */
  1118. int error; /* error return code */
  1119. int index; /* index in leaf block */
  1120. struct xfs_buf *lbp; /* leaf buffer */
  1121. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1122. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1123. xfs_mount_t *mp; /* filesystem mount point */
  1124. xfs_dir2_db_t newdb; /* new data block number */
  1125. xfs_trans_t *tp; /* transaction pointer */
  1126. xfs_dir2_db_t cidb = -1; /* case match data block no. */
  1127. enum xfs_dacmp cmp; /* name compare result */
  1128. struct xfs_dir2_leaf_entry *ents;
  1129. struct xfs_dir3_icleaf_hdr leafhdr;
  1130. dp = args->dp;
  1131. tp = args->trans;
  1132. mp = dp->i_mount;
  1133. error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, -1, &lbp);
  1134. if (error)
  1135. return error;
  1136. *lbpp = lbp;
  1137. leaf = lbp->b_addr;
  1138. xfs_dir3_leaf_check(dp, lbp);
  1139. ents = dp->d_ops->leaf_ents_p(leaf);
  1140. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  1141. /*
  1142. * Look for the first leaf entry with our hash value.
  1143. */
  1144. index = xfs_dir2_leaf_search_hash(args, lbp);
  1145. /*
  1146. * Loop over all the entries with the right hash value
  1147. * looking to match the name.
  1148. */
  1149. for (lep = &ents[index];
  1150. index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
  1151. lep++, index++) {
  1152. /*
  1153. * Skip over stale leaf entries.
  1154. */
  1155. if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
  1156. continue;
  1157. /*
  1158. * Get the new data block number.
  1159. */
  1160. newdb = xfs_dir2_dataptr_to_db(args->geo,
  1161. be32_to_cpu(lep->address));
  1162. /*
  1163. * If it's not the same as the old data block number,
  1164. * need to pitch the old one and read the new one.
  1165. */
  1166. if (newdb != curdb) {
  1167. if (dbp)
  1168. xfs_trans_brelse(tp, dbp);
  1169. error = xfs_dir3_data_read(tp, dp,
  1170. xfs_dir2_db_to_da(args->geo, newdb),
  1171. -1, &dbp);
  1172. if (error) {
  1173. xfs_trans_brelse(tp, lbp);
  1174. return error;
  1175. }
  1176. curdb = newdb;
  1177. }
  1178. /*
  1179. * Point to the data entry.
  1180. */
  1181. dep = (xfs_dir2_data_entry_t *)((char *)dbp->b_addr +
  1182. xfs_dir2_dataptr_to_off(args->geo,
  1183. be32_to_cpu(lep->address)));
  1184. /*
  1185. * Compare name and if it's an exact match, return the index
  1186. * and buffer. If it's the first case-insensitive match, store
  1187. * the index and buffer and continue looking for an exact match.
  1188. */
  1189. cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen);
  1190. if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
  1191. args->cmpresult = cmp;
  1192. *indexp = index;
  1193. /* case exact match: return the current buffer. */
  1194. if (cmp == XFS_CMP_EXACT) {
  1195. *dbpp = dbp;
  1196. return 0;
  1197. }
  1198. cidb = curdb;
  1199. }
  1200. }
  1201. ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
  1202. /*
  1203. * Here, we can only be doing a lookup (not a rename or remove).
  1204. * If a case-insensitive match was found earlier, re-read the
  1205. * appropriate data block if required and return it.
  1206. */
  1207. if (args->cmpresult == XFS_CMP_CASE) {
  1208. ASSERT(cidb != -1);
  1209. if (cidb != curdb) {
  1210. xfs_trans_brelse(tp, dbp);
  1211. error = xfs_dir3_data_read(tp, dp,
  1212. xfs_dir2_db_to_da(args->geo, cidb),
  1213. -1, &dbp);
  1214. if (error) {
  1215. xfs_trans_brelse(tp, lbp);
  1216. return error;
  1217. }
  1218. }
  1219. *dbpp = dbp;
  1220. return 0;
  1221. }
  1222. /*
  1223. * No match found, return -ENOENT.
  1224. */
  1225. ASSERT(cidb == -1);
  1226. if (dbp)
  1227. xfs_trans_brelse(tp, dbp);
  1228. xfs_trans_brelse(tp, lbp);
  1229. return -ENOENT;
  1230. }
  1231. /*
  1232. * Remove an entry from a leaf format directory.
  1233. */
  1234. int /* error */
  1235. xfs_dir2_leaf_removename(
  1236. xfs_da_args_t *args) /* operation arguments */
  1237. {
  1238. __be16 *bestsp; /* leaf block best freespace */
  1239. xfs_dir2_data_hdr_t *hdr; /* data block header */
  1240. xfs_dir2_db_t db; /* data block number */
  1241. struct xfs_buf *dbp; /* data block buffer */
  1242. xfs_dir2_data_entry_t *dep; /* data entry structure */
  1243. xfs_inode_t *dp; /* incore directory inode */
  1244. int error; /* error return code */
  1245. xfs_dir2_db_t i; /* temporary data block # */
  1246. int index; /* index into leaf entries */
  1247. struct xfs_buf *lbp; /* leaf buffer */
  1248. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1249. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1250. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1251. int needlog; /* need to log data header */
  1252. int needscan; /* need to rescan data frees */
  1253. xfs_dir2_data_off_t oldbest; /* old value of best free */
  1254. struct xfs_dir2_data_free *bf; /* bestfree table */
  1255. struct xfs_dir2_leaf_entry *ents;
  1256. struct xfs_dir3_icleaf_hdr leafhdr;
  1257. trace_xfs_dir2_leaf_removename(args);
  1258. /*
  1259. * Lookup the leaf entry, get the leaf and data blocks read in.
  1260. */
  1261. if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
  1262. return error;
  1263. }
  1264. dp = args->dp;
  1265. leaf = lbp->b_addr;
  1266. hdr = dbp->b_addr;
  1267. xfs_dir3_data_check(dp, dbp);
  1268. bf = dp->d_ops->data_bestfree_p(hdr);
  1269. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  1270. ents = dp->d_ops->leaf_ents_p(leaf);
  1271. /*
  1272. * Point to the leaf entry, use that to point to the data entry.
  1273. */
  1274. lep = &ents[index];
  1275. db = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address));
  1276. dep = (xfs_dir2_data_entry_t *)((char *)hdr +
  1277. xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
  1278. needscan = needlog = 0;
  1279. oldbest = be16_to_cpu(bf[0].length);
  1280. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  1281. bestsp = xfs_dir2_leaf_bests_p(ltp);
  1282. ASSERT(be16_to_cpu(bestsp[db]) == oldbest);
  1283. /*
  1284. * Mark the former data entry unused.
  1285. */
  1286. xfs_dir2_data_make_free(args, dbp,
  1287. (xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr),
  1288. dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan);
  1289. /*
  1290. * We just mark the leaf entry stale by putting a null in it.
  1291. */
  1292. leafhdr.stale++;
  1293. dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
  1294. xfs_dir3_leaf_log_header(args, lbp);
  1295. lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
  1296. xfs_dir3_leaf_log_ents(args, lbp, index, index);
  1297. /*
  1298. * Scan the freespace in the data block again if necessary,
  1299. * log the data block header if necessary.
  1300. */
  1301. if (needscan)
  1302. xfs_dir2_data_freescan(dp, hdr, &needlog);
  1303. if (needlog)
  1304. xfs_dir2_data_log_header(args, dbp);
  1305. /*
  1306. * If the longest freespace in the data block has changed,
  1307. * put the new value in the bests table and log that.
  1308. */
  1309. if (be16_to_cpu(bf[0].length) != oldbest) {
  1310. bestsp[db] = bf[0].length;
  1311. xfs_dir3_leaf_log_bests(args, lbp, db, db);
  1312. }
  1313. xfs_dir3_data_check(dp, dbp);
  1314. /*
  1315. * If the data block is now empty then get rid of the data block.
  1316. */
  1317. if (be16_to_cpu(bf[0].length) ==
  1318. args->geo->blksize - dp->d_ops->data_entry_offset) {
  1319. ASSERT(db != args->geo->datablk);
  1320. if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
  1321. /*
  1322. * Nope, can't get rid of it because it caused
  1323. * allocation of a bmap btree block to do so.
  1324. * Just go on, returning success, leaving the
  1325. * empty block in place.
  1326. */
  1327. if (error == -ENOSPC && args->total == 0)
  1328. error = 0;
  1329. xfs_dir3_leaf_check(dp, lbp);
  1330. return error;
  1331. }
  1332. dbp = NULL;
  1333. /*
  1334. * If this is the last data block then compact the
  1335. * bests table by getting rid of entries.
  1336. */
  1337. if (db == be32_to_cpu(ltp->bestcount) - 1) {
  1338. /*
  1339. * Look for the last active entry (i).
  1340. */
  1341. for (i = db - 1; i > 0; i--) {
  1342. if (bestsp[i] != cpu_to_be16(NULLDATAOFF))
  1343. break;
  1344. }
  1345. /*
  1346. * Copy the table down so inactive entries at the
  1347. * end are removed.
  1348. */
  1349. memmove(&bestsp[db - i], bestsp,
  1350. (be32_to_cpu(ltp->bestcount) - (db - i)) * sizeof(*bestsp));
  1351. be32_add_cpu(&ltp->bestcount, -(db - i));
  1352. xfs_dir3_leaf_log_tail(args, lbp);
  1353. xfs_dir3_leaf_log_bests(args, lbp, 0,
  1354. be32_to_cpu(ltp->bestcount) - 1);
  1355. } else
  1356. bestsp[db] = cpu_to_be16(NULLDATAOFF);
  1357. }
  1358. /*
  1359. * If the data block was not the first one, drop it.
  1360. */
  1361. else if (db != args->geo->datablk)
  1362. dbp = NULL;
  1363. xfs_dir3_leaf_check(dp, lbp);
  1364. /*
  1365. * See if we can convert to block form.
  1366. */
  1367. return xfs_dir2_leaf_to_block(args, lbp, dbp);
  1368. }
  1369. /*
  1370. * Replace the inode number in a leaf format directory entry.
  1371. */
  1372. int /* error */
  1373. xfs_dir2_leaf_replace(
  1374. xfs_da_args_t *args) /* operation arguments */
  1375. {
  1376. struct xfs_buf *dbp; /* data block buffer */
  1377. xfs_dir2_data_entry_t *dep; /* data block entry */
  1378. xfs_inode_t *dp; /* incore directory inode */
  1379. int error; /* error return code */
  1380. int index; /* index of leaf entry */
  1381. struct xfs_buf *lbp; /* leaf buffer */
  1382. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1383. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1384. xfs_trans_t *tp; /* transaction pointer */
  1385. struct xfs_dir2_leaf_entry *ents;
  1386. trace_xfs_dir2_leaf_replace(args);
  1387. /*
  1388. * Look up the entry.
  1389. */
  1390. if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
  1391. return error;
  1392. }
  1393. dp = args->dp;
  1394. leaf = lbp->b_addr;
  1395. ents = dp->d_ops->leaf_ents_p(leaf);
  1396. /*
  1397. * Point to the leaf entry, get data address from it.
  1398. */
  1399. lep = &ents[index];
  1400. /*
  1401. * Point to the data entry.
  1402. */
  1403. dep = (xfs_dir2_data_entry_t *)
  1404. ((char *)dbp->b_addr +
  1405. xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
  1406. ASSERT(args->inumber != be64_to_cpu(dep->inumber));
  1407. /*
  1408. * Put the new inode number in, log it.
  1409. */
  1410. dep->inumber = cpu_to_be64(args->inumber);
  1411. dp->d_ops->data_put_ftype(dep, args->filetype);
  1412. tp = args->trans;
  1413. xfs_dir2_data_log_entry(args, dbp, dep);
  1414. xfs_dir3_leaf_check(dp, lbp);
  1415. xfs_trans_brelse(tp, lbp);
  1416. return 0;
  1417. }
  1418. /*
  1419. * Return index in the leaf block (lbp) which is either the first
  1420. * one with this hash value, or if there are none, the insert point
  1421. * for that hash value.
  1422. */
  1423. int /* index value */
  1424. xfs_dir2_leaf_search_hash(
  1425. xfs_da_args_t *args, /* operation arguments */
  1426. struct xfs_buf *lbp) /* leaf buffer */
  1427. {
  1428. xfs_dahash_t hash=0; /* hash from this entry */
  1429. xfs_dahash_t hashwant; /* hash value looking for */
  1430. int high; /* high leaf index */
  1431. int low; /* low leaf index */
  1432. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1433. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1434. int mid=0; /* current leaf index */
  1435. struct xfs_dir2_leaf_entry *ents;
  1436. struct xfs_dir3_icleaf_hdr leafhdr;
  1437. leaf = lbp->b_addr;
  1438. ents = args->dp->d_ops->leaf_ents_p(leaf);
  1439. args->dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  1440. /*
  1441. * Note, the table cannot be empty, so we have to go through the loop.
  1442. * Binary search the leaf entries looking for our hash value.
  1443. */
  1444. for (lep = ents, low = 0, high = leafhdr.count - 1,
  1445. hashwant = args->hashval;
  1446. low <= high; ) {
  1447. mid = (low + high) >> 1;
  1448. if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant)
  1449. break;
  1450. if (hash < hashwant)
  1451. low = mid + 1;
  1452. else
  1453. high = mid - 1;
  1454. }
  1455. /*
  1456. * Found one, back up through all the equal hash values.
  1457. */
  1458. if (hash == hashwant) {
  1459. while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) {
  1460. mid--;
  1461. }
  1462. }
  1463. /*
  1464. * Need to point to an entry higher than ours.
  1465. */
  1466. else if (hash < hashwant)
  1467. mid++;
  1468. return mid;
  1469. }
  1470. /*
  1471. * Trim off a trailing data block. We know it's empty since the leaf
  1472. * freespace table says so.
  1473. */
  1474. int /* error */
  1475. xfs_dir2_leaf_trim_data(
  1476. xfs_da_args_t *args, /* operation arguments */
  1477. struct xfs_buf *lbp, /* leaf buffer */
  1478. xfs_dir2_db_t db) /* data block number */
  1479. {
  1480. __be16 *bestsp; /* leaf bests table */
  1481. struct xfs_buf *dbp; /* data block buffer */
  1482. xfs_inode_t *dp; /* incore directory inode */
  1483. int error; /* error return value */
  1484. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1485. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1486. xfs_trans_t *tp; /* transaction pointer */
  1487. dp = args->dp;
  1488. tp = args->trans;
  1489. /*
  1490. * Read the offending data block. We need its buffer.
  1491. */
  1492. error = xfs_dir3_data_read(tp, dp, xfs_dir2_db_to_da(args->geo, db),
  1493. -1, &dbp);
  1494. if (error)
  1495. return error;
  1496. leaf = lbp->b_addr;
  1497. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  1498. #ifdef DEBUG
  1499. {
  1500. struct xfs_dir2_data_hdr *hdr = dbp->b_addr;
  1501. struct xfs_dir2_data_free *bf = dp->d_ops->data_bestfree_p(hdr);
  1502. ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
  1503. hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));
  1504. ASSERT(be16_to_cpu(bf[0].length) ==
  1505. args->geo->blksize - dp->d_ops->data_entry_offset);
  1506. ASSERT(db == be32_to_cpu(ltp->bestcount) - 1);
  1507. }
  1508. #endif
  1509. /*
  1510. * Get rid of the data block.
  1511. */
  1512. if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
  1513. ASSERT(error != -ENOSPC);
  1514. xfs_trans_brelse(tp, dbp);
  1515. return error;
  1516. }
  1517. /*
  1518. * Eliminate the last bests entry from the table.
  1519. */
  1520. bestsp = xfs_dir2_leaf_bests_p(ltp);
  1521. be32_add_cpu(&ltp->bestcount, -1);
  1522. memmove(&bestsp[1], &bestsp[0], be32_to_cpu(ltp->bestcount) * sizeof(*bestsp));
  1523. xfs_dir3_leaf_log_tail(args, lbp);
  1524. xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
  1525. return 0;
  1526. }
  1527. static inline size_t
  1528. xfs_dir3_leaf_size(
  1529. struct xfs_dir3_icleaf_hdr *hdr,
  1530. int counts)
  1531. {
  1532. int entries;
  1533. int hdrsize;
  1534. entries = hdr->count - hdr->stale;
  1535. if (hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
  1536. hdr->magic == XFS_DIR2_LEAFN_MAGIC)
  1537. hdrsize = sizeof(struct xfs_dir2_leaf_hdr);
  1538. else
  1539. hdrsize = sizeof(struct xfs_dir3_leaf_hdr);
  1540. return hdrsize + entries * sizeof(xfs_dir2_leaf_entry_t)
  1541. + counts * sizeof(xfs_dir2_data_off_t)
  1542. + sizeof(xfs_dir2_leaf_tail_t);
  1543. }
  1544. /*
  1545. * Convert node form directory to leaf form directory.
  1546. * The root of the node form dir needs to already be a LEAFN block.
  1547. * Just return if we can't do anything.
  1548. */
  1549. int /* error */
  1550. xfs_dir2_node_to_leaf(
  1551. xfs_da_state_t *state) /* directory operation state */
  1552. {
  1553. xfs_da_args_t *args; /* operation arguments */
  1554. xfs_inode_t *dp; /* incore directory inode */
  1555. int error; /* error return code */
  1556. struct xfs_buf *fbp; /* buffer for freespace block */
  1557. xfs_fileoff_t fo; /* freespace file offset */
  1558. xfs_dir2_free_t *free; /* freespace structure */
  1559. struct xfs_buf *lbp; /* buffer for leaf block */
  1560. xfs_dir2_leaf_tail_t *ltp; /* tail of leaf structure */
  1561. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1562. xfs_mount_t *mp; /* filesystem mount point */
  1563. int rval; /* successful free trim? */
  1564. xfs_trans_t *tp; /* transaction pointer */
  1565. struct xfs_dir3_icleaf_hdr leafhdr;
  1566. struct xfs_dir3_icfree_hdr freehdr;
  1567. /*
  1568. * There's more than a leaf level in the btree, so there must
  1569. * be multiple leafn blocks. Give up.
  1570. */
  1571. if (state->path.active > 1)
  1572. return 0;
  1573. args = state->args;
  1574. trace_xfs_dir2_node_to_leaf(args);
  1575. mp = state->mp;
  1576. dp = args->dp;
  1577. tp = args->trans;
  1578. /*
  1579. * Get the last offset in the file.
  1580. */
  1581. if ((error = xfs_bmap_last_offset(dp, &fo, XFS_DATA_FORK))) {
  1582. return error;
  1583. }
  1584. fo -= args->geo->fsbcount;
  1585. /*
  1586. * If there are freespace blocks other than the first one,
  1587. * take this opportunity to remove trailing empty freespace blocks
  1588. * that may have been left behind during no-space-reservation
  1589. * operations.
  1590. */
  1591. while (fo > args->geo->freeblk) {
  1592. if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) {
  1593. return error;
  1594. }
  1595. if (rval)
  1596. fo -= args->geo->fsbcount;
  1597. else
  1598. return 0;
  1599. }
  1600. /*
  1601. * Now find the block just before the freespace block.
  1602. */
  1603. if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) {
  1604. return error;
  1605. }
  1606. /*
  1607. * If it's not the single leaf block, give up.
  1608. */
  1609. if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + args->geo->blksize)
  1610. return 0;
  1611. lbp = state->path.blk[0].bp;
  1612. leaf = lbp->b_addr;
  1613. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  1614. ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
  1615. leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
  1616. /*
  1617. * Read the freespace block.
  1618. */
  1619. error = xfs_dir2_free_read(tp, dp, args->geo->freeblk, &fbp);
  1620. if (error)
  1621. return error;
  1622. free = fbp->b_addr;
  1623. dp->d_ops->free_hdr_from_disk(&freehdr, free);
  1624. ASSERT(!freehdr.firstdb);
  1625. /*
  1626. * Now see if the leafn and free data will fit in a leaf1.
  1627. * If not, release the buffer and give up.
  1628. */
  1629. if (xfs_dir3_leaf_size(&leafhdr, freehdr.nvalid) > args->geo->blksize) {
  1630. xfs_trans_brelse(tp, fbp);
  1631. return 0;
  1632. }
  1633. /*
  1634. * If the leaf has any stale entries in it, compress them out.
  1635. */
  1636. if (leafhdr.stale)
  1637. xfs_dir3_leaf_compact(args, &leafhdr, lbp);
  1638. lbp->b_ops = &xfs_dir3_leaf1_buf_ops;
  1639. xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAF1_BUF);
  1640. leafhdr.magic = (leafhdr.magic == XFS_DIR2_LEAFN_MAGIC)
  1641. ? XFS_DIR2_LEAF1_MAGIC
  1642. : XFS_DIR3_LEAF1_MAGIC;
  1643. /*
  1644. * Set up the leaf tail from the freespace block.
  1645. */
  1646. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  1647. ltp->bestcount = cpu_to_be32(freehdr.nvalid);
  1648. /*
  1649. * Set up the leaf bests table.
  1650. */
  1651. memcpy(xfs_dir2_leaf_bests_p(ltp), dp->d_ops->free_bests_p(free),
  1652. freehdr.nvalid * sizeof(xfs_dir2_data_off_t));
  1653. dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
  1654. xfs_dir3_leaf_log_header(args, lbp);
  1655. xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
  1656. xfs_dir3_leaf_log_tail(args, lbp);
  1657. xfs_dir3_leaf_check(dp, lbp);
  1658. /*
  1659. * Get rid of the freespace block.
  1660. */
  1661. error = xfs_dir2_shrink_inode(args,
  1662. xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET),
  1663. fbp);
  1664. if (error) {
  1665. /*
  1666. * This can't fail here because it can only happen when
  1667. * punching out the middle of an extent, and this is an
  1668. * isolated block.
  1669. */
  1670. ASSERT(error != -ENOSPC);
  1671. return error;
  1672. }
  1673. fbp = NULL;
  1674. /*
  1675. * Now see if we can convert the single-leaf directory
  1676. * down to a block form directory.
  1677. * This routine always kills the dabuf for the leaf, so
  1678. * eliminate it from the path.
  1679. */
  1680. error = xfs_dir2_leaf_to_block(args, lbp, NULL);
  1681. state->path.blk[0].bp = NULL;
  1682. return error;
  1683. }