xfs_dir2_data.c 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834
  1. /*
  2. * Copyright (c) 2000-2002,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_log.h"
  22. #include "xfs_inum.h"
  23. #include "xfs_trans.h"
  24. #include "xfs_sb.h"
  25. #include "xfs_dir2.h"
  26. #include "xfs_dmapi.h"
  27. #include "xfs_mount.h"
  28. #include "xfs_da_btree.h"
  29. #include "xfs_bmap_btree.h"
  30. #include "xfs_dir2_sf.h"
  31. #include "xfs_attr_sf.h"
  32. #include "xfs_dinode.h"
  33. #include "xfs_inode.h"
  34. #include "xfs_dir2_data.h"
  35. #include "xfs_dir2_leaf.h"
  36. #include "xfs_dir2_block.h"
  37. #include "xfs_error.h"
  38. #ifdef DEBUG
  39. /*
  40. * Check the consistency of the data block.
  41. * The input can also be a block-format directory.
  42. * Pop an assert if we find anything bad.
  43. */
  44. void
  45. xfs_dir2_data_check(
  46. xfs_inode_t *dp, /* incore inode pointer */
  47. xfs_dabuf_t *bp) /* data block's buffer */
  48. {
  49. xfs_dir2_dataptr_t addr; /* addr for leaf lookup */
  50. xfs_dir2_data_free_t *bf; /* bestfree table */
  51. xfs_dir2_block_tail_t *btp=NULL; /* block tail */
  52. int count; /* count of entries found */
  53. xfs_dir2_data_t *d; /* data block pointer */
  54. xfs_dir2_data_entry_t *dep; /* data entry */
  55. xfs_dir2_data_free_t *dfp; /* bestfree entry */
  56. xfs_dir2_data_unused_t *dup; /* unused entry */
  57. char *endp; /* end of useful data */
  58. int freeseen; /* mask of bestfrees seen */
  59. xfs_dahash_t hash; /* hash of current name */
  60. int i; /* leaf index */
  61. int lastfree; /* last entry was unused */
  62. xfs_dir2_leaf_entry_t *lep=NULL; /* block leaf entries */
  63. xfs_mount_t *mp; /* filesystem mount point */
  64. char *p; /* current data position */
  65. int stale; /* count of stale leaves */
  66. mp = dp->i_mount;
  67. d = bp->data;
  68. ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
  69. be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
  70. bf = d->hdr.bestfree;
  71. p = (char *)d->u;
  72. if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) {
  73. btp = XFS_DIR2_BLOCK_TAIL_P(mp, (xfs_dir2_block_t *)d);
  74. lep = XFS_DIR2_BLOCK_LEAF_P(btp);
  75. endp = (char *)lep;
  76. } else
  77. endp = (char *)d + mp->m_dirblksize;
  78. count = lastfree = freeseen = 0;
  79. /*
  80. * Account for zero bestfree entries.
  81. */
  82. if (!bf[0].length) {
  83. ASSERT(!bf[0].offset);
  84. freeseen |= 1 << 0;
  85. }
  86. if (!bf[1].length) {
  87. ASSERT(!bf[1].offset);
  88. freeseen |= 1 << 1;
  89. }
  90. if (!bf[2].length) {
  91. ASSERT(!bf[2].offset);
  92. freeseen |= 1 << 2;
  93. }
  94. ASSERT(be16_to_cpu(bf[0].length) >= be16_to_cpu(bf[1].length));
  95. ASSERT(be16_to_cpu(bf[1].length) >= be16_to_cpu(bf[2].length));
  96. /*
  97. * Loop over the data/unused entries.
  98. */
  99. while (p < endp) {
  100. dup = (xfs_dir2_data_unused_t *)p;
  101. /*
  102. * If it's unused, look for the space in the bestfree table.
  103. * If we find it, account for that, else make sure it
  104. * doesn't need to be there.
  105. */
  106. if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
  107. ASSERT(lastfree == 0);
  108. ASSERT(be16_to_cpu(*XFS_DIR2_DATA_UNUSED_TAG_P(dup)) ==
  109. (char *)dup - (char *)d);
  110. dfp = xfs_dir2_data_freefind(d, dup);
  111. if (dfp) {
  112. i = (int)(dfp - bf);
  113. ASSERT((freeseen & (1 << i)) == 0);
  114. freeseen |= 1 << i;
  115. } else {
  116. ASSERT(be16_to_cpu(dup->length) <=
  117. be16_to_cpu(bf[2].length));
  118. }
  119. p += be16_to_cpu(dup->length);
  120. lastfree = 1;
  121. continue;
  122. }
  123. /*
  124. * It's a real entry. Validate the fields.
  125. * If this is a block directory then make sure it's
  126. * in the leaf section of the block.
  127. * The linear search is crude but this is DEBUG code.
  128. */
  129. dep = (xfs_dir2_data_entry_t *)p;
  130. ASSERT(dep->namelen != 0);
  131. ASSERT(xfs_dir_ino_validate(mp, be64_to_cpu(dep->inumber)) == 0);
  132. ASSERT(be16_to_cpu(*XFS_DIR2_DATA_ENTRY_TAG_P(dep)) ==
  133. (char *)dep - (char *)d);
  134. count++;
  135. lastfree = 0;
  136. if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) {
  137. addr = XFS_DIR2_DB_OFF_TO_DATAPTR(mp, mp->m_dirdatablk,
  138. (xfs_dir2_data_aoff_t)
  139. ((char *)dep - (char *)d));
  140. hash = xfs_da_hashname((char *)dep->name, dep->namelen);
  141. for (i = 0; i < be32_to_cpu(btp->count); i++) {
  142. if (be32_to_cpu(lep[i].address) == addr &&
  143. be32_to_cpu(lep[i].hashval) == hash)
  144. break;
  145. }
  146. ASSERT(i < be32_to_cpu(btp->count));
  147. }
  148. p += XFS_DIR2_DATA_ENTSIZE(dep->namelen);
  149. }
  150. /*
  151. * Need to have seen all the entries and all the bestfree slots.
  152. */
  153. ASSERT(freeseen == 7);
  154. if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) {
  155. for (i = stale = 0; i < be32_to_cpu(btp->count); i++) {
  156. if (be32_to_cpu(lep[i].address) == XFS_DIR2_NULL_DATAPTR)
  157. stale++;
  158. if (i > 0)
  159. ASSERT(be32_to_cpu(lep[i].hashval) >= be32_to_cpu(lep[i - 1].hashval));
  160. }
  161. ASSERT(count == be32_to_cpu(btp->count) - be32_to_cpu(btp->stale));
  162. ASSERT(stale == be32_to_cpu(btp->stale));
  163. }
  164. }
  165. #endif
  166. /*
  167. * Given a data block and an unused entry from that block,
  168. * return the bestfree entry if any that corresponds to it.
  169. */
  170. xfs_dir2_data_free_t *
  171. xfs_dir2_data_freefind(
  172. xfs_dir2_data_t *d, /* data block */
  173. xfs_dir2_data_unused_t *dup) /* data unused entry */
  174. {
  175. xfs_dir2_data_free_t *dfp; /* bestfree entry */
  176. xfs_dir2_data_aoff_t off; /* offset value needed */
  177. #if defined(DEBUG) && defined(__KERNEL__)
  178. int matched; /* matched the value */
  179. int seenzero; /* saw a 0 bestfree entry */
  180. #endif
  181. off = (xfs_dir2_data_aoff_t)((char *)dup - (char *)d);
  182. #if defined(DEBUG) && defined(__KERNEL__)
  183. /*
  184. * Validate some consistency in the bestfree table.
  185. * Check order, non-overlapping entries, and if we find the
  186. * one we're looking for it has to be exact.
  187. */
  188. ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
  189. be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
  190. for (dfp = &d->hdr.bestfree[0], seenzero = matched = 0;
  191. dfp < &d->hdr.bestfree[XFS_DIR2_DATA_FD_COUNT];
  192. dfp++) {
  193. if (!dfp->offset) {
  194. ASSERT(!dfp->length);
  195. seenzero = 1;
  196. continue;
  197. }
  198. ASSERT(seenzero == 0);
  199. if (be16_to_cpu(dfp->offset) == off) {
  200. matched = 1;
  201. ASSERT(dfp->length == dup->length);
  202. } else if (off < be16_to_cpu(dfp->offset))
  203. ASSERT(off + be16_to_cpu(dup->length) <= be16_to_cpu(dfp->offset));
  204. else
  205. ASSERT(be16_to_cpu(dfp->offset) + be16_to_cpu(dfp->length) <= off);
  206. ASSERT(matched || be16_to_cpu(dfp->length) >= be16_to_cpu(dup->length));
  207. if (dfp > &d->hdr.bestfree[0])
  208. ASSERT(be16_to_cpu(dfp[-1].length) >= be16_to_cpu(dfp[0].length));
  209. }
  210. #endif
  211. /*
  212. * If this is smaller than the smallest bestfree entry,
  213. * it can't be there since they're sorted.
  214. */
  215. if (be16_to_cpu(dup->length) <
  216. be16_to_cpu(d->hdr.bestfree[XFS_DIR2_DATA_FD_COUNT - 1].length))
  217. return NULL;
  218. /*
  219. * Look at the three bestfree entries for our guy.
  220. */
  221. for (dfp = &d->hdr.bestfree[0];
  222. dfp < &d->hdr.bestfree[XFS_DIR2_DATA_FD_COUNT];
  223. dfp++) {
  224. if (!dfp->offset)
  225. return NULL;
  226. if (be16_to_cpu(dfp->offset) == off)
  227. return dfp;
  228. }
  229. /*
  230. * Didn't find it. This only happens if there are duplicate lengths.
  231. */
  232. return NULL;
  233. }
  234. /*
  235. * Insert an unused-space entry into the bestfree table.
  236. */
  237. xfs_dir2_data_free_t * /* entry inserted */
  238. xfs_dir2_data_freeinsert(
  239. xfs_dir2_data_t *d, /* data block pointer */
  240. xfs_dir2_data_unused_t *dup, /* unused space */
  241. int *loghead) /* log the data header (out) */
  242. {
  243. xfs_dir2_data_free_t *dfp; /* bestfree table pointer */
  244. xfs_dir2_data_free_t new; /* new bestfree entry */
  245. #ifdef __KERNEL__
  246. ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
  247. be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
  248. #endif
  249. dfp = d->hdr.bestfree;
  250. new.length = dup->length;
  251. new.offset = cpu_to_be16((char *)dup - (char *)d);
  252. /*
  253. * Insert at position 0, 1, or 2; or not at all.
  254. */
  255. if (be16_to_cpu(new.length) > be16_to_cpu(dfp[0].length)) {
  256. dfp[2] = dfp[1];
  257. dfp[1] = dfp[0];
  258. dfp[0] = new;
  259. *loghead = 1;
  260. return &dfp[0];
  261. }
  262. if (be16_to_cpu(new.length) > be16_to_cpu(dfp[1].length)) {
  263. dfp[2] = dfp[1];
  264. dfp[1] = new;
  265. *loghead = 1;
  266. return &dfp[1];
  267. }
  268. if (be16_to_cpu(new.length) > be16_to_cpu(dfp[2].length)) {
  269. dfp[2] = new;
  270. *loghead = 1;
  271. return &dfp[2];
  272. }
  273. return NULL;
  274. }
  275. /*
  276. * Remove a bestfree entry from the table.
  277. */
  278. STATIC void
  279. xfs_dir2_data_freeremove(
  280. xfs_dir2_data_t *d, /* data block pointer */
  281. xfs_dir2_data_free_t *dfp, /* bestfree entry pointer */
  282. int *loghead) /* out: log data header */
  283. {
  284. #ifdef __KERNEL__
  285. ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
  286. be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
  287. #endif
  288. /*
  289. * It's the first entry, slide the next 2 up.
  290. */
  291. if (dfp == &d->hdr.bestfree[0]) {
  292. d->hdr.bestfree[0] = d->hdr.bestfree[1];
  293. d->hdr.bestfree[1] = d->hdr.bestfree[2];
  294. }
  295. /*
  296. * It's the second entry, slide the 3rd entry up.
  297. */
  298. else if (dfp == &d->hdr.bestfree[1])
  299. d->hdr.bestfree[1] = d->hdr.bestfree[2];
  300. /*
  301. * Must be the last entry.
  302. */
  303. else
  304. ASSERT(dfp == &d->hdr.bestfree[2]);
  305. /*
  306. * Clear the 3rd entry, must be zero now.
  307. */
  308. d->hdr.bestfree[2].length = 0;
  309. d->hdr.bestfree[2].offset = 0;
  310. *loghead = 1;
  311. }
  312. /*
  313. * Given a data block, reconstruct its bestfree map.
  314. */
  315. void
  316. xfs_dir2_data_freescan(
  317. xfs_mount_t *mp, /* filesystem mount point */
  318. xfs_dir2_data_t *d, /* data block pointer */
  319. int *loghead, /* out: log data header */
  320. char *aendp) /* in: caller's endp */
  321. {
  322. xfs_dir2_block_tail_t *btp; /* block tail */
  323. xfs_dir2_data_entry_t *dep; /* active data entry */
  324. xfs_dir2_data_unused_t *dup; /* unused data entry */
  325. char *endp; /* end of block's data */
  326. char *p; /* current entry pointer */
  327. #ifdef __KERNEL__
  328. ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
  329. be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
  330. #endif
  331. /*
  332. * Start by clearing the table.
  333. */
  334. memset(d->hdr.bestfree, 0, sizeof(d->hdr.bestfree));
  335. *loghead = 1;
  336. /*
  337. * Set up pointers.
  338. */
  339. p = (char *)d->u;
  340. if (aendp)
  341. endp = aendp;
  342. else if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) {
  343. btp = XFS_DIR2_BLOCK_TAIL_P(mp, (xfs_dir2_block_t *)d);
  344. endp = (char *)XFS_DIR2_BLOCK_LEAF_P(btp);
  345. } else
  346. endp = (char *)d + mp->m_dirblksize;
  347. /*
  348. * Loop over the block's entries.
  349. */
  350. while (p < endp) {
  351. dup = (xfs_dir2_data_unused_t *)p;
  352. /*
  353. * If it's a free entry, insert it.
  354. */
  355. if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
  356. ASSERT((char *)dup - (char *)d ==
  357. be16_to_cpu(*XFS_DIR2_DATA_UNUSED_TAG_P(dup)));
  358. xfs_dir2_data_freeinsert(d, dup, loghead);
  359. p += be16_to_cpu(dup->length);
  360. }
  361. /*
  362. * For active entries, check their tags and skip them.
  363. */
  364. else {
  365. dep = (xfs_dir2_data_entry_t *)p;
  366. ASSERT((char *)dep - (char *)d ==
  367. be16_to_cpu(*XFS_DIR2_DATA_ENTRY_TAG_P(dep)));
  368. p += XFS_DIR2_DATA_ENTSIZE(dep->namelen);
  369. }
  370. }
  371. }
  372. /*
  373. * Initialize a data block at the given block number in the directory.
  374. * Give back the buffer for the created block.
  375. */
  376. int /* error */
  377. xfs_dir2_data_init(
  378. xfs_da_args_t *args, /* directory operation args */
  379. xfs_dir2_db_t blkno, /* logical dir block number */
  380. xfs_dabuf_t **bpp) /* output block buffer */
  381. {
  382. xfs_dabuf_t *bp; /* block buffer */
  383. xfs_dir2_data_t *d; /* pointer to block */
  384. xfs_inode_t *dp; /* incore directory inode */
  385. xfs_dir2_data_unused_t *dup; /* unused entry pointer */
  386. int error; /* error return value */
  387. int i; /* bestfree index */
  388. xfs_mount_t *mp; /* filesystem mount point */
  389. xfs_trans_t *tp; /* transaction pointer */
  390. int t; /* temp */
  391. dp = args->dp;
  392. mp = dp->i_mount;
  393. tp = args->trans;
  394. /*
  395. * Get the buffer set up for the block.
  396. */
  397. error = xfs_da_get_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, blkno), -1, &bp,
  398. XFS_DATA_FORK);
  399. if (error) {
  400. return error;
  401. }
  402. ASSERT(bp != NULL);
  403. /*
  404. * Initialize the header.
  405. */
  406. d = bp->data;
  407. d->hdr.magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
  408. d->hdr.bestfree[0].offset = cpu_to_be16(sizeof(d->hdr));
  409. for (i = 1; i < XFS_DIR2_DATA_FD_COUNT; i++) {
  410. d->hdr.bestfree[i].length = 0;
  411. d->hdr.bestfree[i].offset = 0;
  412. }
  413. /*
  414. * Set up an unused entry for the block's body.
  415. */
  416. dup = &d->u[0].unused;
  417. dup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
  418. t=mp->m_dirblksize - (uint)sizeof(d->hdr);
  419. d->hdr.bestfree[0].length = cpu_to_be16(t);
  420. dup->length = cpu_to_be16(t);
  421. *XFS_DIR2_DATA_UNUSED_TAG_P(dup) = cpu_to_be16((char *)dup - (char *)d);
  422. /*
  423. * Log it and return it.
  424. */
  425. xfs_dir2_data_log_header(tp, bp);
  426. xfs_dir2_data_log_unused(tp, bp, dup);
  427. *bpp = bp;
  428. return 0;
  429. }
  430. /*
  431. * Log an active data entry from the block.
  432. */
  433. void
  434. xfs_dir2_data_log_entry(
  435. xfs_trans_t *tp, /* transaction pointer */
  436. xfs_dabuf_t *bp, /* block buffer */
  437. xfs_dir2_data_entry_t *dep) /* data entry pointer */
  438. {
  439. xfs_dir2_data_t *d; /* data block pointer */
  440. d = bp->data;
  441. ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
  442. be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
  443. xfs_da_log_buf(tp, bp, (uint)((char *)dep - (char *)d),
  444. (uint)((char *)(XFS_DIR2_DATA_ENTRY_TAG_P(dep) + 1) -
  445. (char *)d - 1));
  446. }
  447. /*
  448. * Log a data block header.
  449. */
  450. void
  451. xfs_dir2_data_log_header(
  452. xfs_trans_t *tp, /* transaction pointer */
  453. xfs_dabuf_t *bp) /* block buffer */
  454. {
  455. xfs_dir2_data_t *d; /* data block pointer */
  456. d = bp->data;
  457. ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
  458. be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
  459. xfs_da_log_buf(tp, bp, (uint)((char *)&d->hdr - (char *)d),
  460. (uint)(sizeof(d->hdr) - 1));
  461. }
  462. /*
  463. * Log a data unused entry.
  464. */
  465. void
  466. xfs_dir2_data_log_unused(
  467. xfs_trans_t *tp, /* transaction pointer */
  468. xfs_dabuf_t *bp, /* block buffer */
  469. xfs_dir2_data_unused_t *dup) /* data unused pointer */
  470. {
  471. xfs_dir2_data_t *d; /* data block pointer */
  472. d = bp->data;
  473. ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
  474. be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
  475. /*
  476. * Log the first part of the unused entry.
  477. */
  478. xfs_da_log_buf(tp, bp, (uint)((char *)dup - (char *)d),
  479. (uint)((char *)&dup->length + sizeof(dup->length) -
  480. 1 - (char *)d));
  481. /*
  482. * Log the end (tag) of the unused entry.
  483. */
  484. xfs_da_log_buf(tp, bp,
  485. (uint)((char *)XFS_DIR2_DATA_UNUSED_TAG_P(dup) - (char *)d),
  486. (uint)((char *)XFS_DIR2_DATA_UNUSED_TAG_P(dup) - (char *)d +
  487. sizeof(xfs_dir2_data_off_t) - 1));
  488. }
  489. /*
  490. * Make a byte range in the data block unused.
  491. * Its current contents are unimportant.
  492. */
  493. void
  494. xfs_dir2_data_make_free(
  495. xfs_trans_t *tp, /* transaction pointer */
  496. xfs_dabuf_t *bp, /* block buffer */
  497. xfs_dir2_data_aoff_t offset, /* starting byte offset */
  498. xfs_dir2_data_aoff_t len, /* length in bytes */
  499. int *needlogp, /* out: log header */
  500. int *needscanp) /* out: regen bestfree */
  501. {
  502. xfs_dir2_data_t *d; /* data block pointer */
  503. xfs_dir2_data_free_t *dfp; /* bestfree pointer */
  504. char *endptr; /* end of data area */
  505. xfs_mount_t *mp; /* filesystem mount point */
  506. int needscan; /* need to regen bestfree */
  507. xfs_dir2_data_unused_t *newdup; /* new unused entry */
  508. xfs_dir2_data_unused_t *postdup; /* unused entry after us */
  509. xfs_dir2_data_unused_t *prevdup; /* unused entry before us */
  510. mp = tp->t_mountp;
  511. d = bp->data;
  512. /*
  513. * Figure out where the end of the data area is.
  514. */
  515. if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC)
  516. endptr = (char *)d + mp->m_dirblksize;
  517. else {
  518. xfs_dir2_block_tail_t *btp; /* block tail */
  519. ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
  520. btp = XFS_DIR2_BLOCK_TAIL_P(mp, (xfs_dir2_block_t *)d);
  521. endptr = (char *)XFS_DIR2_BLOCK_LEAF_P(btp);
  522. }
  523. /*
  524. * If this isn't the start of the block, then back up to
  525. * the previous entry and see if it's free.
  526. */
  527. if (offset > sizeof(d->hdr)) {
  528. __be16 *tagp; /* tag just before us */
  529. tagp = (__be16 *)((char *)d + offset) - 1;
  530. prevdup = (xfs_dir2_data_unused_t *)((char *)d + be16_to_cpu(*tagp));
  531. if (be16_to_cpu(prevdup->freetag) != XFS_DIR2_DATA_FREE_TAG)
  532. prevdup = NULL;
  533. } else
  534. prevdup = NULL;
  535. /*
  536. * If this isn't the end of the block, see if the entry after
  537. * us is free.
  538. */
  539. if ((char *)d + offset + len < endptr) {
  540. postdup =
  541. (xfs_dir2_data_unused_t *)((char *)d + offset + len);
  542. if (be16_to_cpu(postdup->freetag) != XFS_DIR2_DATA_FREE_TAG)
  543. postdup = NULL;
  544. } else
  545. postdup = NULL;
  546. ASSERT(*needscanp == 0);
  547. needscan = 0;
  548. /*
  549. * Previous and following entries are both free,
  550. * merge everything into a single free entry.
  551. */
  552. if (prevdup && postdup) {
  553. xfs_dir2_data_free_t *dfp2; /* another bestfree pointer */
  554. /*
  555. * See if prevdup and/or postdup are in bestfree table.
  556. */
  557. dfp = xfs_dir2_data_freefind(d, prevdup);
  558. dfp2 = xfs_dir2_data_freefind(d, postdup);
  559. /*
  560. * We need a rescan unless there are exactly 2 free entries
  561. * namely our two. Then we know what's happening, otherwise
  562. * since the third bestfree is there, there might be more
  563. * entries.
  564. */
  565. needscan = (d->hdr.bestfree[2].length != 0);
  566. /*
  567. * Fix up the new big freespace.
  568. */
  569. be16_add(&prevdup->length, len + be16_to_cpu(postdup->length));
  570. *XFS_DIR2_DATA_UNUSED_TAG_P(prevdup) =
  571. cpu_to_be16((char *)prevdup - (char *)d);
  572. xfs_dir2_data_log_unused(tp, bp, prevdup);
  573. if (!needscan) {
  574. /*
  575. * Has to be the case that entries 0 and 1 are
  576. * dfp and dfp2 (don't know which is which), and
  577. * entry 2 is empty.
  578. * Remove entry 1 first then entry 0.
  579. */
  580. ASSERT(dfp && dfp2);
  581. if (dfp == &d->hdr.bestfree[1]) {
  582. dfp = &d->hdr.bestfree[0];
  583. ASSERT(dfp2 == dfp);
  584. dfp2 = &d->hdr.bestfree[1];
  585. }
  586. xfs_dir2_data_freeremove(d, dfp2, needlogp);
  587. xfs_dir2_data_freeremove(d, dfp, needlogp);
  588. /*
  589. * Now insert the new entry.
  590. */
  591. dfp = xfs_dir2_data_freeinsert(d, prevdup, needlogp);
  592. ASSERT(dfp == &d->hdr.bestfree[0]);
  593. ASSERT(dfp->length == prevdup->length);
  594. ASSERT(!dfp[1].length);
  595. ASSERT(!dfp[2].length);
  596. }
  597. }
  598. /*
  599. * The entry before us is free, merge with it.
  600. */
  601. else if (prevdup) {
  602. dfp = xfs_dir2_data_freefind(d, prevdup);
  603. be16_add(&prevdup->length, len);
  604. *XFS_DIR2_DATA_UNUSED_TAG_P(prevdup) =
  605. cpu_to_be16((char *)prevdup - (char *)d);
  606. xfs_dir2_data_log_unused(tp, bp, prevdup);
  607. /*
  608. * If the previous entry was in the table, the new entry
  609. * is longer, so it will be in the table too. Remove
  610. * the old one and add the new one.
  611. */
  612. if (dfp) {
  613. xfs_dir2_data_freeremove(d, dfp, needlogp);
  614. (void)xfs_dir2_data_freeinsert(d, prevdup, needlogp);
  615. }
  616. /*
  617. * Otherwise we need a scan if the new entry is big enough.
  618. */
  619. else {
  620. needscan = be16_to_cpu(prevdup->length) >
  621. be16_to_cpu(d->hdr.bestfree[2].length);
  622. }
  623. }
  624. /*
  625. * The following entry is free, merge with it.
  626. */
  627. else if (postdup) {
  628. dfp = xfs_dir2_data_freefind(d, postdup);
  629. newdup = (xfs_dir2_data_unused_t *)((char *)d + offset);
  630. newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
  631. newdup->length = cpu_to_be16(len + be16_to_cpu(postdup->length));
  632. *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) =
  633. cpu_to_be16((char *)newdup - (char *)d);
  634. xfs_dir2_data_log_unused(tp, bp, newdup);
  635. /*
  636. * If the following entry was in the table, the new entry
  637. * is longer, so it will be in the table too. Remove
  638. * the old one and add the new one.
  639. */
  640. if (dfp) {
  641. xfs_dir2_data_freeremove(d, dfp, needlogp);
  642. (void)xfs_dir2_data_freeinsert(d, newdup, needlogp);
  643. }
  644. /*
  645. * Otherwise we need a scan if the new entry is big enough.
  646. */
  647. else {
  648. needscan = be16_to_cpu(newdup->length) >
  649. be16_to_cpu(d->hdr.bestfree[2].length);
  650. }
  651. }
  652. /*
  653. * Neither neighbor is free. Make a new entry.
  654. */
  655. else {
  656. newdup = (xfs_dir2_data_unused_t *)((char *)d + offset);
  657. newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
  658. newdup->length = cpu_to_be16(len);
  659. *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) =
  660. cpu_to_be16((char *)newdup - (char *)d);
  661. xfs_dir2_data_log_unused(tp, bp, newdup);
  662. (void)xfs_dir2_data_freeinsert(d, newdup, needlogp);
  663. }
  664. *needscanp = needscan;
  665. }
  666. /*
  667. * Take a byte range out of an existing unused space and make it un-free.
  668. */
  669. void
  670. xfs_dir2_data_use_free(
  671. xfs_trans_t *tp, /* transaction pointer */
  672. xfs_dabuf_t *bp, /* data block buffer */
  673. xfs_dir2_data_unused_t *dup, /* unused entry */
  674. xfs_dir2_data_aoff_t offset, /* starting offset to use */
  675. xfs_dir2_data_aoff_t len, /* length to use */
  676. int *needlogp, /* out: need to log header */
  677. int *needscanp) /* out: need regen bestfree */
  678. {
  679. xfs_dir2_data_t *d; /* data block */
  680. xfs_dir2_data_free_t *dfp; /* bestfree pointer */
  681. int matchback; /* matches end of freespace */
  682. int matchfront; /* matches start of freespace */
  683. int needscan; /* need to regen bestfree */
  684. xfs_dir2_data_unused_t *newdup; /* new unused entry */
  685. xfs_dir2_data_unused_t *newdup2; /* another new unused entry */
  686. int oldlen; /* old unused entry's length */
  687. d = bp->data;
  688. ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
  689. be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
  690. ASSERT(be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG);
  691. ASSERT(offset >= (char *)dup - (char *)d);
  692. ASSERT(offset + len <= (char *)dup + be16_to_cpu(dup->length) - (char *)d);
  693. ASSERT((char *)dup - (char *)d == be16_to_cpu(*XFS_DIR2_DATA_UNUSED_TAG_P(dup)));
  694. /*
  695. * Look up the entry in the bestfree table.
  696. */
  697. dfp = xfs_dir2_data_freefind(d, dup);
  698. oldlen = be16_to_cpu(dup->length);
  699. ASSERT(dfp || oldlen <= be16_to_cpu(d->hdr.bestfree[2].length));
  700. /*
  701. * Check for alignment with front and back of the entry.
  702. */
  703. matchfront = (char *)dup - (char *)d == offset;
  704. matchback = (char *)dup + oldlen - (char *)d == offset + len;
  705. ASSERT(*needscanp == 0);
  706. needscan = 0;
  707. /*
  708. * If we matched it exactly we just need to get rid of it from
  709. * the bestfree table.
  710. */
  711. if (matchfront && matchback) {
  712. if (dfp) {
  713. needscan = (d->hdr.bestfree[2].offset != 0);
  714. if (!needscan)
  715. xfs_dir2_data_freeremove(d, dfp, needlogp);
  716. }
  717. }
  718. /*
  719. * We match the first part of the entry.
  720. * Make a new entry with the remaining freespace.
  721. */
  722. else if (matchfront) {
  723. newdup = (xfs_dir2_data_unused_t *)((char *)d + offset + len);
  724. newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
  725. newdup->length = cpu_to_be16(oldlen - len);
  726. *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) =
  727. cpu_to_be16((char *)newdup - (char *)d);
  728. xfs_dir2_data_log_unused(tp, bp, newdup);
  729. /*
  730. * If it was in the table, remove it and add the new one.
  731. */
  732. if (dfp) {
  733. xfs_dir2_data_freeremove(d, dfp, needlogp);
  734. dfp = xfs_dir2_data_freeinsert(d, newdup, needlogp);
  735. ASSERT(dfp != NULL);
  736. ASSERT(dfp->length == newdup->length);
  737. ASSERT(be16_to_cpu(dfp->offset) == (char *)newdup - (char *)d);
  738. /*
  739. * If we got inserted at the last slot,
  740. * that means we don't know if there was a better
  741. * choice for the last slot, or not. Rescan.
  742. */
  743. needscan = dfp == &d->hdr.bestfree[2];
  744. }
  745. }
  746. /*
  747. * We match the last part of the entry.
  748. * Trim the allocated space off the tail of the entry.
  749. */
  750. else if (matchback) {
  751. newdup = dup;
  752. newdup->length = cpu_to_be16(((char *)d + offset) - (char *)newdup);
  753. *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) =
  754. cpu_to_be16((char *)newdup - (char *)d);
  755. xfs_dir2_data_log_unused(tp, bp, newdup);
  756. /*
  757. * If it was in the table, remove it and add the new one.
  758. */
  759. if (dfp) {
  760. xfs_dir2_data_freeremove(d, dfp, needlogp);
  761. dfp = xfs_dir2_data_freeinsert(d, newdup, needlogp);
  762. ASSERT(dfp != NULL);
  763. ASSERT(dfp->length == newdup->length);
  764. ASSERT(be16_to_cpu(dfp->offset) == (char *)newdup - (char *)d);
  765. /*
  766. * If we got inserted at the last slot,
  767. * that means we don't know if there was a better
  768. * choice for the last slot, or not. Rescan.
  769. */
  770. needscan = dfp == &d->hdr.bestfree[2];
  771. }
  772. }
  773. /*
  774. * Poking out the middle of an entry.
  775. * Make two new entries.
  776. */
  777. else {
  778. newdup = dup;
  779. newdup->length = cpu_to_be16(((char *)d + offset) - (char *)newdup);
  780. *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) =
  781. cpu_to_be16((char *)newdup - (char *)d);
  782. xfs_dir2_data_log_unused(tp, bp, newdup);
  783. newdup2 = (xfs_dir2_data_unused_t *)((char *)d + offset + len);
  784. newdup2->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
  785. newdup2->length = cpu_to_be16(oldlen - len - be16_to_cpu(newdup->length));
  786. *XFS_DIR2_DATA_UNUSED_TAG_P(newdup2) =
  787. cpu_to_be16((char *)newdup2 - (char *)d);
  788. xfs_dir2_data_log_unused(tp, bp, newdup2);
  789. /*
  790. * If the old entry was in the table, we need to scan
  791. * if the 3rd entry was valid, since these entries
  792. * are smaller than the old one.
  793. * If we don't need to scan that means there were 1 or 2
  794. * entries in the table, and removing the old and adding
  795. * the 2 new will work.
  796. */
  797. if (dfp) {
  798. needscan = (d->hdr.bestfree[2].length != 0);
  799. if (!needscan) {
  800. xfs_dir2_data_freeremove(d, dfp, needlogp);
  801. (void)xfs_dir2_data_freeinsert(d, newdup,
  802. needlogp);
  803. (void)xfs_dir2_data_freeinsert(d, newdup2,
  804. needlogp);
  805. }
  806. }
  807. }
  808. *needscanp = needscan;
  809. }