xfs_btree.c 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941
  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_bit.h"
  22. #include "xfs_log.h"
  23. #include "xfs_inum.h"
  24. #include "xfs_trans.h"
  25. #include "xfs_sb.h"
  26. #include "xfs_ag.h"
  27. #include "xfs_dir2.h"
  28. #include "xfs_dmapi.h"
  29. #include "xfs_mount.h"
  30. #include "xfs_bmap_btree.h"
  31. #include "xfs_alloc_btree.h"
  32. #include "xfs_ialloc_btree.h"
  33. #include "xfs_dir2_sf.h"
  34. #include "xfs_attr_sf.h"
  35. #include "xfs_dinode.h"
  36. #include "xfs_inode.h"
  37. #include "xfs_btree.h"
  38. #include "xfs_ialloc.h"
  39. #include "xfs_error.h"
  40. /*
  41. * Cursor allocation zone.
  42. */
  43. kmem_zone_t *xfs_btree_cur_zone;
  44. /*
  45. * Btree magic numbers.
  46. */
  47. const __uint32_t xfs_magics[XFS_BTNUM_MAX] =
  48. {
  49. XFS_ABTB_MAGIC, XFS_ABTC_MAGIC, XFS_BMAP_MAGIC, XFS_IBT_MAGIC
  50. };
  51. /*
  52. * Prototypes for internal routines.
  53. */
  54. /*
  55. * Checking routine: return maxrecs for the block.
  56. */
  57. STATIC int /* number of records fitting in block */
  58. xfs_btree_maxrecs(
  59. xfs_btree_cur_t *cur, /* btree cursor */
  60. xfs_btree_block_t *block);/* generic btree block pointer */
  61. /*
  62. * Internal routines.
  63. */
  64. /*
  65. * Retrieve the block pointer from the cursor at the given level.
  66. * This may be a bmap btree root or from a buffer.
  67. */
  68. STATIC xfs_btree_block_t * /* generic btree block pointer */
  69. xfs_btree_get_block(
  70. xfs_btree_cur_t *cur, /* btree cursor */
  71. int level, /* level in btree */
  72. struct xfs_buf **bpp); /* buffer containing the block */
  73. /*
  74. * Checking routine: return maxrecs for the block.
  75. */
  76. STATIC int /* number of records fitting in block */
  77. xfs_btree_maxrecs(
  78. xfs_btree_cur_t *cur, /* btree cursor */
  79. xfs_btree_block_t *block) /* generic btree block pointer */
  80. {
  81. switch (cur->bc_btnum) {
  82. case XFS_BTNUM_BNO:
  83. case XFS_BTNUM_CNT:
  84. return (int)XFS_ALLOC_BLOCK_MAXRECS(
  85. be16_to_cpu(block->bb_h.bb_level), cur);
  86. case XFS_BTNUM_BMAP:
  87. return (int)XFS_BMAP_BLOCK_IMAXRECS(
  88. be16_to_cpu(block->bb_h.bb_level), cur);
  89. case XFS_BTNUM_INO:
  90. return (int)XFS_INOBT_BLOCK_MAXRECS(
  91. be16_to_cpu(block->bb_h.bb_level), cur);
  92. default:
  93. ASSERT(0);
  94. return 0;
  95. }
  96. }
  97. /*
  98. * External routines.
  99. */
  100. #ifdef DEBUG
  101. /*
  102. * Debug routine: check that block header is ok.
  103. */
  104. void
  105. xfs_btree_check_block(
  106. xfs_btree_cur_t *cur, /* btree cursor */
  107. xfs_btree_block_t *block, /* generic btree block pointer */
  108. int level, /* level of the btree block */
  109. xfs_buf_t *bp) /* buffer containing block, if any */
  110. {
  111. if (XFS_BTREE_LONG_PTRS(cur->bc_btnum))
  112. xfs_btree_check_lblock(cur, (xfs_btree_lblock_t *)block, level,
  113. bp);
  114. else
  115. xfs_btree_check_sblock(cur, (xfs_btree_sblock_t *)block, level,
  116. bp);
  117. }
  118. /*
  119. * Debug routine: check that keys are in the right order.
  120. */
  121. void
  122. xfs_btree_check_key(
  123. xfs_btnum_t btnum, /* btree identifier */
  124. void *ak1, /* pointer to left (lower) key */
  125. void *ak2) /* pointer to right (higher) key */
  126. {
  127. switch (btnum) {
  128. case XFS_BTNUM_BNO: {
  129. xfs_alloc_key_t *k1;
  130. xfs_alloc_key_t *k2;
  131. k1 = ak1;
  132. k2 = ak2;
  133. ASSERT(be32_to_cpu(k1->ar_startblock) < be32_to_cpu(k2->ar_startblock));
  134. break;
  135. }
  136. case XFS_BTNUM_CNT: {
  137. xfs_alloc_key_t *k1;
  138. xfs_alloc_key_t *k2;
  139. k1 = ak1;
  140. k2 = ak2;
  141. ASSERT(be32_to_cpu(k1->ar_blockcount) < be32_to_cpu(k2->ar_blockcount) ||
  142. (k1->ar_blockcount == k2->ar_blockcount &&
  143. be32_to_cpu(k1->ar_startblock) < be32_to_cpu(k2->ar_startblock)));
  144. break;
  145. }
  146. case XFS_BTNUM_BMAP: {
  147. xfs_bmbt_key_t *k1;
  148. xfs_bmbt_key_t *k2;
  149. k1 = ak1;
  150. k2 = ak2;
  151. ASSERT(be64_to_cpu(k1->br_startoff) < be64_to_cpu(k2->br_startoff));
  152. break;
  153. }
  154. case XFS_BTNUM_INO: {
  155. xfs_inobt_key_t *k1;
  156. xfs_inobt_key_t *k2;
  157. k1 = ak1;
  158. k2 = ak2;
  159. ASSERT(be32_to_cpu(k1->ir_startino) < be32_to_cpu(k2->ir_startino));
  160. break;
  161. }
  162. default:
  163. ASSERT(0);
  164. }
  165. }
  166. #endif /* DEBUG */
  167. /*
  168. * Checking routine: check that long form block header is ok.
  169. */
  170. /* ARGSUSED */
  171. int /* error (0 or EFSCORRUPTED) */
  172. xfs_btree_check_lblock(
  173. xfs_btree_cur_t *cur, /* btree cursor */
  174. xfs_btree_lblock_t *block, /* btree long form block pointer */
  175. int level, /* level of the btree block */
  176. xfs_buf_t *bp) /* buffer for block, if any */
  177. {
  178. int lblock_ok; /* block passes checks */
  179. xfs_mount_t *mp; /* file system mount point */
  180. mp = cur->bc_mp;
  181. lblock_ok =
  182. be32_to_cpu(block->bb_magic) == xfs_magics[cur->bc_btnum] &&
  183. be16_to_cpu(block->bb_level) == level &&
  184. be16_to_cpu(block->bb_numrecs) <=
  185. xfs_btree_maxrecs(cur, (xfs_btree_block_t *)block) &&
  186. block->bb_leftsib &&
  187. (be64_to_cpu(block->bb_leftsib) == NULLDFSBNO ||
  188. XFS_FSB_SANITY_CHECK(mp, be64_to_cpu(block->bb_leftsib))) &&
  189. block->bb_rightsib &&
  190. (be64_to_cpu(block->bb_rightsib) == NULLDFSBNO ||
  191. XFS_FSB_SANITY_CHECK(mp, be64_to_cpu(block->bb_rightsib)));
  192. if (unlikely(XFS_TEST_ERROR(!lblock_ok, mp, XFS_ERRTAG_BTREE_CHECK_LBLOCK,
  193. XFS_RANDOM_BTREE_CHECK_LBLOCK))) {
  194. if (bp)
  195. xfs_buftrace("LBTREE ERROR", bp);
  196. XFS_ERROR_REPORT("xfs_btree_check_lblock", XFS_ERRLEVEL_LOW,
  197. mp);
  198. return XFS_ERROR(EFSCORRUPTED);
  199. }
  200. return 0;
  201. }
  202. /*
  203. * Checking routine: check that (long) pointer is ok.
  204. */
  205. int /* error (0 or EFSCORRUPTED) */
  206. xfs_btree_check_lptr(
  207. xfs_btree_cur_t *cur, /* btree cursor */
  208. xfs_dfsbno_t ptr, /* btree block disk address */
  209. int level) /* btree block level */
  210. {
  211. xfs_mount_t *mp; /* file system mount point */
  212. mp = cur->bc_mp;
  213. XFS_WANT_CORRUPTED_RETURN(
  214. level > 0 &&
  215. ptr != NULLDFSBNO &&
  216. XFS_FSB_SANITY_CHECK(mp, ptr));
  217. return 0;
  218. }
  219. #ifdef DEBUG
  220. /*
  221. * Debug routine: check that records are in the right order.
  222. */
  223. void
  224. xfs_btree_check_rec(
  225. xfs_btnum_t btnum, /* btree identifier */
  226. void *ar1, /* pointer to left (lower) record */
  227. void *ar2) /* pointer to right (higher) record */
  228. {
  229. switch (btnum) {
  230. case XFS_BTNUM_BNO: {
  231. xfs_alloc_rec_t *r1;
  232. xfs_alloc_rec_t *r2;
  233. r1 = ar1;
  234. r2 = ar2;
  235. ASSERT(be32_to_cpu(r1->ar_startblock) +
  236. be32_to_cpu(r1->ar_blockcount) <=
  237. be32_to_cpu(r2->ar_startblock));
  238. break;
  239. }
  240. case XFS_BTNUM_CNT: {
  241. xfs_alloc_rec_t *r1;
  242. xfs_alloc_rec_t *r2;
  243. r1 = ar1;
  244. r2 = ar2;
  245. ASSERT(be32_to_cpu(r1->ar_blockcount) < be32_to_cpu(r2->ar_blockcount) ||
  246. (r1->ar_blockcount == r2->ar_blockcount &&
  247. be32_to_cpu(r1->ar_startblock) < be32_to_cpu(r2->ar_startblock)));
  248. break;
  249. }
  250. case XFS_BTNUM_BMAP: {
  251. xfs_bmbt_rec_t *r1;
  252. xfs_bmbt_rec_t *r2;
  253. r1 = ar1;
  254. r2 = ar2;
  255. ASSERT(xfs_bmbt_disk_get_startoff(r1) +
  256. xfs_bmbt_disk_get_blockcount(r1) <=
  257. xfs_bmbt_disk_get_startoff(r2));
  258. break;
  259. }
  260. case XFS_BTNUM_INO: {
  261. xfs_inobt_rec_t *r1;
  262. xfs_inobt_rec_t *r2;
  263. r1 = ar1;
  264. r2 = ar2;
  265. ASSERT(be32_to_cpu(r1->ir_startino) + XFS_INODES_PER_CHUNK <=
  266. be32_to_cpu(r2->ir_startino));
  267. break;
  268. }
  269. default:
  270. ASSERT(0);
  271. }
  272. }
  273. #endif /* DEBUG */
  274. /*
  275. * Checking routine: check that block header is ok.
  276. */
  277. /* ARGSUSED */
  278. int /* error (0 or EFSCORRUPTED) */
  279. xfs_btree_check_sblock(
  280. xfs_btree_cur_t *cur, /* btree cursor */
  281. xfs_btree_sblock_t *block, /* btree short form block pointer */
  282. int level, /* level of the btree block */
  283. xfs_buf_t *bp) /* buffer containing block */
  284. {
  285. xfs_buf_t *agbp; /* buffer for ag. freespace struct */
  286. xfs_agf_t *agf; /* ag. freespace structure */
  287. xfs_agblock_t agflen; /* native ag. freespace length */
  288. int sblock_ok; /* block passes checks */
  289. agbp = cur->bc_private.a.agbp;
  290. agf = XFS_BUF_TO_AGF(agbp);
  291. agflen = be32_to_cpu(agf->agf_length);
  292. sblock_ok =
  293. be32_to_cpu(block->bb_magic) == xfs_magics[cur->bc_btnum] &&
  294. be16_to_cpu(block->bb_level) == level &&
  295. be16_to_cpu(block->bb_numrecs) <=
  296. xfs_btree_maxrecs(cur, (xfs_btree_block_t *)block) &&
  297. (be32_to_cpu(block->bb_leftsib) == NULLAGBLOCK ||
  298. be32_to_cpu(block->bb_leftsib) < agflen) &&
  299. block->bb_leftsib &&
  300. (be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK ||
  301. be32_to_cpu(block->bb_rightsib) < agflen) &&
  302. block->bb_rightsib;
  303. if (unlikely(XFS_TEST_ERROR(!sblock_ok, cur->bc_mp,
  304. XFS_ERRTAG_BTREE_CHECK_SBLOCK,
  305. XFS_RANDOM_BTREE_CHECK_SBLOCK))) {
  306. if (bp)
  307. xfs_buftrace("SBTREE ERROR", bp);
  308. XFS_ERROR_REPORT("xfs_btree_check_sblock", XFS_ERRLEVEL_LOW,
  309. cur->bc_mp);
  310. return XFS_ERROR(EFSCORRUPTED);
  311. }
  312. return 0;
  313. }
  314. /*
  315. * Checking routine: check that (short) pointer is ok.
  316. */
  317. int /* error (0 or EFSCORRUPTED) */
  318. xfs_btree_check_sptr(
  319. xfs_btree_cur_t *cur, /* btree cursor */
  320. xfs_agblock_t ptr, /* btree block disk address */
  321. int level) /* btree block level */
  322. {
  323. xfs_buf_t *agbp; /* buffer for ag. freespace struct */
  324. xfs_agf_t *agf; /* ag. freespace structure */
  325. agbp = cur->bc_private.a.agbp;
  326. agf = XFS_BUF_TO_AGF(agbp);
  327. XFS_WANT_CORRUPTED_RETURN(
  328. level > 0 &&
  329. ptr != NULLAGBLOCK && ptr != 0 &&
  330. ptr < be32_to_cpu(agf->agf_length));
  331. return 0;
  332. }
  333. /*
  334. * Delete the btree cursor.
  335. */
  336. void
  337. xfs_btree_del_cursor(
  338. xfs_btree_cur_t *cur, /* btree cursor */
  339. int error) /* del because of error */
  340. {
  341. int i; /* btree level */
  342. /*
  343. * Clear the buffer pointers, and release the buffers.
  344. * If we're doing this in the face of an error, we
  345. * need to make sure to inspect all of the entries
  346. * in the bc_bufs array for buffers to be unlocked.
  347. * This is because some of the btree code works from
  348. * level n down to 0, and if we get an error along
  349. * the way we won't have initialized all the entries
  350. * down to 0.
  351. */
  352. for (i = 0; i < cur->bc_nlevels; i++) {
  353. if (cur->bc_bufs[i])
  354. xfs_btree_setbuf(cur, i, NULL);
  355. else if (!error)
  356. break;
  357. }
  358. /*
  359. * Can't free a bmap cursor without having dealt with the
  360. * allocated indirect blocks' accounting.
  361. */
  362. ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP ||
  363. cur->bc_private.b.allocated == 0);
  364. /*
  365. * Free the cursor.
  366. */
  367. kmem_zone_free(xfs_btree_cur_zone, cur);
  368. }
  369. /*
  370. * Duplicate the btree cursor.
  371. * Allocate a new one, copy the record, re-get the buffers.
  372. */
  373. int /* error */
  374. xfs_btree_dup_cursor(
  375. xfs_btree_cur_t *cur, /* input cursor */
  376. xfs_btree_cur_t **ncur) /* output cursor */
  377. {
  378. xfs_buf_t *bp; /* btree block's buffer pointer */
  379. int error; /* error return value */
  380. int i; /* level number of btree block */
  381. xfs_mount_t *mp; /* mount structure for filesystem */
  382. xfs_btree_cur_t *new; /* new cursor value */
  383. xfs_trans_t *tp; /* transaction pointer, can be NULL */
  384. tp = cur->bc_tp;
  385. mp = cur->bc_mp;
  386. /*
  387. * Allocate a new cursor like the old one.
  388. */
  389. new = xfs_btree_init_cursor(mp, tp, cur->bc_private.a.agbp,
  390. cur->bc_private.a.agno, cur->bc_btnum, cur->bc_private.b.ip,
  391. cur->bc_private.b.whichfork);
  392. /*
  393. * Copy the record currently in the cursor.
  394. */
  395. new->bc_rec = cur->bc_rec;
  396. /*
  397. * For each level current, re-get the buffer and copy the ptr value.
  398. */
  399. for (i = 0; i < new->bc_nlevels; i++) {
  400. new->bc_ptrs[i] = cur->bc_ptrs[i];
  401. new->bc_ra[i] = cur->bc_ra[i];
  402. if ((bp = cur->bc_bufs[i])) {
  403. if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
  404. XFS_BUF_ADDR(bp), mp->m_bsize, 0, &bp))) {
  405. xfs_btree_del_cursor(new, error);
  406. *ncur = NULL;
  407. return error;
  408. }
  409. new->bc_bufs[i] = bp;
  410. ASSERT(bp);
  411. ASSERT(!XFS_BUF_GETERROR(bp));
  412. } else
  413. new->bc_bufs[i] = NULL;
  414. }
  415. /*
  416. * For bmap btrees, copy the firstblock, flist, and flags values,
  417. * since init cursor doesn't get them.
  418. */
  419. if (new->bc_btnum == XFS_BTNUM_BMAP) {
  420. new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
  421. new->bc_private.b.flist = cur->bc_private.b.flist;
  422. new->bc_private.b.flags = cur->bc_private.b.flags;
  423. }
  424. *ncur = new;
  425. return 0;
  426. }
  427. /*
  428. * Change the cursor to point to the first record at the given level.
  429. * Other levels are unaffected.
  430. */
  431. int /* success=1, failure=0 */
  432. xfs_btree_firstrec(
  433. xfs_btree_cur_t *cur, /* btree cursor */
  434. int level) /* level to change */
  435. {
  436. xfs_btree_block_t *block; /* generic btree block pointer */
  437. xfs_buf_t *bp; /* buffer containing block */
  438. /*
  439. * Get the block pointer for this level.
  440. */
  441. block = xfs_btree_get_block(cur, level, &bp);
  442. xfs_btree_check_block(cur, block, level, bp);
  443. /*
  444. * It's empty, there is no such record.
  445. */
  446. if (!block->bb_h.bb_numrecs)
  447. return 0;
  448. /*
  449. * Set the ptr value to 1, that's the first record/key.
  450. */
  451. cur->bc_ptrs[level] = 1;
  452. return 1;
  453. }
  454. /*
  455. * Retrieve the block pointer from the cursor at the given level.
  456. * This may be a bmap btree root or from a buffer.
  457. */
  458. STATIC xfs_btree_block_t * /* generic btree block pointer */
  459. xfs_btree_get_block(
  460. xfs_btree_cur_t *cur, /* btree cursor */
  461. int level, /* level in btree */
  462. xfs_buf_t **bpp) /* buffer containing the block */
  463. {
  464. xfs_btree_block_t *block; /* return value */
  465. xfs_buf_t *bp; /* return buffer */
  466. xfs_ifork_t *ifp; /* inode fork pointer */
  467. int whichfork; /* data or attr fork */
  468. if (cur->bc_btnum == XFS_BTNUM_BMAP && level == cur->bc_nlevels - 1) {
  469. whichfork = cur->bc_private.b.whichfork;
  470. ifp = XFS_IFORK_PTR(cur->bc_private.b.ip, whichfork);
  471. block = (xfs_btree_block_t *)ifp->if_broot;
  472. bp = NULL;
  473. } else {
  474. bp = cur->bc_bufs[level];
  475. block = XFS_BUF_TO_BLOCK(bp);
  476. }
  477. ASSERT(block != NULL);
  478. *bpp = bp;
  479. return block;
  480. }
  481. /*
  482. * Get a buffer for the block, return it with no data read.
  483. * Long-form addressing.
  484. */
  485. xfs_buf_t * /* buffer for fsbno */
  486. xfs_btree_get_bufl(
  487. xfs_mount_t *mp, /* file system mount point */
  488. xfs_trans_t *tp, /* transaction pointer */
  489. xfs_fsblock_t fsbno, /* file system block number */
  490. uint lock) /* lock flags for get_buf */
  491. {
  492. xfs_buf_t *bp; /* buffer pointer (return value) */
  493. xfs_daddr_t d; /* real disk block address */
  494. ASSERT(fsbno != NULLFSBLOCK);
  495. d = XFS_FSB_TO_DADDR(mp, fsbno);
  496. bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
  497. ASSERT(bp);
  498. ASSERT(!XFS_BUF_GETERROR(bp));
  499. return bp;
  500. }
  501. /*
  502. * Get a buffer for the block, return it with no data read.
  503. * Short-form addressing.
  504. */
  505. xfs_buf_t * /* buffer for agno/agbno */
  506. xfs_btree_get_bufs(
  507. xfs_mount_t *mp, /* file system mount point */
  508. xfs_trans_t *tp, /* transaction pointer */
  509. xfs_agnumber_t agno, /* allocation group number */
  510. xfs_agblock_t agbno, /* allocation group block number */
  511. uint lock) /* lock flags for get_buf */
  512. {
  513. xfs_buf_t *bp; /* buffer pointer (return value) */
  514. xfs_daddr_t d; /* real disk block address */
  515. ASSERT(agno != NULLAGNUMBER);
  516. ASSERT(agbno != NULLAGBLOCK);
  517. d = XFS_AGB_TO_DADDR(mp, agno, agbno);
  518. bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
  519. ASSERT(bp);
  520. ASSERT(!XFS_BUF_GETERROR(bp));
  521. return bp;
  522. }
  523. /*
  524. * Allocate a new btree cursor.
  525. * The cursor is either for allocation (A) or bmap (B) or inodes (I).
  526. */
  527. xfs_btree_cur_t * /* new btree cursor */
  528. xfs_btree_init_cursor(
  529. xfs_mount_t *mp, /* file system mount point */
  530. xfs_trans_t *tp, /* transaction pointer */
  531. xfs_buf_t *agbp, /* (A only) buffer for agf structure */
  532. /* (I only) buffer for agi structure */
  533. xfs_agnumber_t agno, /* (AI only) allocation group number */
  534. xfs_btnum_t btnum, /* btree identifier */
  535. xfs_inode_t *ip, /* (B only) inode owning the btree */
  536. int whichfork) /* (B only) data or attr fork */
  537. {
  538. xfs_agf_t *agf; /* (A) allocation group freespace */
  539. xfs_agi_t *agi; /* (I) allocation group inodespace */
  540. xfs_btree_cur_t *cur; /* return value */
  541. xfs_ifork_t *ifp; /* (I) inode fork pointer */
  542. int nlevels=0; /* number of levels in the btree */
  543. ASSERT(xfs_btree_cur_zone != NULL);
  544. /*
  545. * Allocate a new cursor.
  546. */
  547. cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
  548. /*
  549. * Deduce the number of btree levels from the arguments.
  550. */
  551. switch (btnum) {
  552. case XFS_BTNUM_BNO:
  553. case XFS_BTNUM_CNT:
  554. agf = XFS_BUF_TO_AGF(agbp);
  555. nlevels = be32_to_cpu(agf->agf_levels[btnum]);
  556. break;
  557. case XFS_BTNUM_BMAP:
  558. ifp = XFS_IFORK_PTR(ip, whichfork);
  559. nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
  560. break;
  561. case XFS_BTNUM_INO:
  562. agi = XFS_BUF_TO_AGI(agbp);
  563. nlevels = be32_to_cpu(agi->agi_level);
  564. break;
  565. default:
  566. ASSERT(0);
  567. }
  568. /*
  569. * Fill in the common fields.
  570. */
  571. cur->bc_tp = tp;
  572. cur->bc_mp = mp;
  573. cur->bc_nlevels = nlevels;
  574. cur->bc_btnum = btnum;
  575. cur->bc_blocklog = mp->m_sb.sb_blocklog;
  576. /*
  577. * Fill in private fields.
  578. */
  579. switch (btnum) {
  580. case XFS_BTNUM_BNO:
  581. case XFS_BTNUM_CNT:
  582. /*
  583. * Allocation btree fields.
  584. */
  585. cur->bc_private.a.agbp = agbp;
  586. cur->bc_private.a.agno = agno;
  587. break;
  588. case XFS_BTNUM_BMAP:
  589. /*
  590. * Bmap btree fields.
  591. */
  592. cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
  593. cur->bc_private.b.ip = ip;
  594. cur->bc_private.b.firstblock = NULLFSBLOCK;
  595. cur->bc_private.b.flist = NULL;
  596. cur->bc_private.b.allocated = 0;
  597. cur->bc_private.b.flags = 0;
  598. cur->bc_private.b.whichfork = whichfork;
  599. break;
  600. case XFS_BTNUM_INO:
  601. /*
  602. * Inode allocation btree fields.
  603. */
  604. cur->bc_private.i.agbp = agbp;
  605. cur->bc_private.i.agno = agno;
  606. break;
  607. default:
  608. ASSERT(0);
  609. }
  610. return cur;
  611. }
  612. /*
  613. * Check for the cursor referring to the last block at the given level.
  614. */
  615. int /* 1=is last block, 0=not last block */
  616. xfs_btree_islastblock(
  617. xfs_btree_cur_t *cur, /* btree cursor */
  618. int level) /* level to check */
  619. {
  620. xfs_btree_block_t *block; /* generic btree block pointer */
  621. xfs_buf_t *bp; /* buffer containing block */
  622. block = xfs_btree_get_block(cur, level, &bp);
  623. xfs_btree_check_block(cur, block, level, bp);
  624. if (XFS_BTREE_LONG_PTRS(cur->bc_btnum))
  625. return be64_to_cpu(block->bb_u.l.bb_rightsib) == NULLDFSBNO;
  626. else
  627. return be32_to_cpu(block->bb_u.s.bb_rightsib) == NULLAGBLOCK;
  628. }
  629. /*
  630. * Change the cursor to point to the last record in the current block
  631. * at the given level. Other levels are unaffected.
  632. */
  633. int /* success=1, failure=0 */
  634. xfs_btree_lastrec(
  635. xfs_btree_cur_t *cur, /* btree cursor */
  636. int level) /* level to change */
  637. {
  638. xfs_btree_block_t *block; /* generic btree block pointer */
  639. xfs_buf_t *bp; /* buffer containing block */
  640. /*
  641. * Get the block pointer for this level.
  642. */
  643. block = xfs_btree_get_block(cur, level, &bp);
  644. xfs_btree_check_block(cur, block, level, bp);
  645. /*
  646. * It's empty, there is no such record.
  647. */
  648. if (!block->bb_h.bb_numrecs)
  649. return 0;
  650. /*
  651. * Set the ptr value to numrecs, that's the last record/key.
  652. */
  653. cur->bc_ptrs[level] = be16_to_cpu(block->bb_h.bb_numrecs);
  654. return 1;
  655. }
  656. /*
  657. * Compute first and last byte offsets for the fields given.
  658. * Interprets the offsets table, which contains struct field offsets.
  659. */
  660. void
  661. xfs_btree_offsets(
  662. __int64_t fields, /* bitmask of fields */
  663. const short *offsets, /* table of field offsets */
  664. int nbits, /* number of bits to inspect */
  665. int *first, /* output: first byte offset */
  666. int *last) /* output: last byte offset */
  667. {
  668. int i; /* current bit number */
  669. __int64_t imask; /* mask for current bit number */
  670. ASSERT(fields != 0);
  671. /*
  672. * Find the lowest bit, so the first byte offset.
  673. */
  674. for (i = 0, imask = 1LL; ; i++, imask <<= 1) {
  675. if (imask & fields) {
  676. *first = offsets[i];
  677. break;
  678. }
  679. }
  680. /*
  681. * Find the highest bit, so the last byte offset.
  682. */
  683. for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) {
  684. if (imask & fields) {
  685. *last = offsets[i + 1] - 1;
  686. break;
  687. }
  688. }
  689. }
  690. /*
  691. * Get a buffer for the block, return it read in.
  692. * Long-form addressing.
  693. */
  694. int /* error */
  695. xfs_btree_read_bufl(
  696. xfs_mount_t *mp, /* file system mount point */
  697. xfs_trans_t *tp, /* transaction pointer */
  698. xfs_fsblock_t fsbno, /* file system block number */
  699. uint lock, /* lock flags for read_buf */
  700. xfs_buf_t **bpp, /* buffer for fsbno */
  701. int refval) /* ref count value for buffer */
  702. {
  703. xfs_buf_t *bp; /* return value */
  704. xfs_daddr_t d; /* real disk block address */
  705. int error;
  706. ASSERT(fsbno != NULLFSBLOCK);
  707. d = XFS_FSB_TO_DADDR(mp, fsbno);
  708. if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
  709. mp->m_bsize, lock, &bp))) {
  710. return error;
  711. }
  712. ASSERT(!bp || !XFS_BUF_GETERROR(bp));
  713. if (bp != NULL) {
  714. XFS_BUF_SET_VTYPE_REF(bp, B_FS_MAP, refval);
  715. }
  716. *bpp = bp;
  717. return 0;
  718. }
  719. /*
  720. * Get a buffer for the block, return it read in.
  721. * Short-form addressing.
  722. */
  723. int /* error */
  724. xfs_btree_read_bufs(
  725. xfs_mount_t *mp, /* file system mount point */
  726. xfs_trans_t *tp, /* transaction pointer */
  727. xfs_agnumber_t agno, /* allocation group number */
  728. xfs_agblock_t agbno, /* allocation group block number */
  729. uint lock, /* lock flags for read_buf */
  730. xfs_buf_t **bpp, /* buffer for agno/agbno */
  731. int refval) /* ref count value for buffer */
  732. {
  733. xfs_buf_t *bp; /* return value */
  734. xfs_daddr_t d; /* real disk block address */
  735. int error;
  736. ASSERT(agno != NULLAGNUMBER);
  737. ASSERT(agbno != NULLAGBLOCK);
  738. d = XFS_AGB_TO_DADDR(mp, agno, agbno);
  739. if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
  740. mp->m_bsize, lock, &bp))) {
  741. return error;
  742. }
  743. ASSERT(!bp || !XFS_BUF_GETERROR(bp));
  744. if (bp != NULL) {
  745. switch (refval) {
  746. case XFS_ALLOC_BTREE_REF:
  747. XFS_BUF_SET_VTYPE_REF(bp, B_FS_MAP, refval);
  748. break;
  749. case XFS_INO_BTREE_REF:
  750. XFS_BUF_SET_VTYPE_REF(bp, B_FS_INOMAP, refval);
  751. break;
  752. }
  753. }
  754. *bpp = bp;
  755. return 0;
  756. }
  757. /*
  758. * Read-ahead the block, don't wait for it, don't return a buffer.
  759. * Long-form addressing.
  760. */
  761. /* ARGSUSED */
  762. void
  763. xfs_btree_reada_bufl(
  764. xfs_mount_t *mp, /* file system mount point */
  765. xfs_fsblock_t fsbno, /* file system block number */
  766. xfs_extlen_t count) /* count of filesystem blocks */
  767. {
  768. xfs_daddr_t d;
  769. ASSERT(fsbno != NULLFSBLOCK);
  770. d = XFS_FSB_TO_DADDR(mp, fsbno);
  771. xfs_baread(mp->m_ddev_targp, d, mp->m_bsize * count);
  772. }
  773. /*
  774. * Read-ahead the block, don't wait for it, don't return a buffer.
  775. * Short-form addressing.
  776. */
  777. /* ARGSUSED */
  778. void
  779. xfs_btree_reada_bufs(
  780. xfs_mount_t *mp, /* file system mount point */
  781. xfs_agnumber_t agno, /* allocation group number */
  782. xfs_agblock_t agbno, /* allocation group block number */
  783. xfs_extlen_t count) /* count of filesystem blocks */
  784. {
  785. xfs_daddr_t d;
  786. ASSERT(agno != NULLAGNUMBER);
  787. ASSERT(agbno != NULLAGBLOCK);
  788. d = XFS_AGB_TO_DADDR(mp, agno, agbno);
  789. xfs_baread(mp->m_ddev_targp, d, mp->m_bsize * count);
  790. }
  791. /*
  792. * Read-ahead btree blocks, at the given level.
  793. * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
  794. */
  795. int
  796. xfs_btree_readahead_core(
  797. xfs_btree_cur_t *cur, /* btree cursor */
  798. int lev, /* level in btree */
  799. int lr) /* left/right bits */
  800. {
  801. xfs_alloc_block_t *a;
  802. xfs_bmbt_block_t *b;
  803. xfs_inobt_block_t *i;
  804. int rval = 0;
  805. ASSERT(cur->bc_bufs[lev] != NULL);
  806. cur->bc_ra[lev] |= lr;
  807. switch (cur->bc_btnum) {
  808. case XFS_BTNUM_BNO:
  809. case XFS_BTNUM_CNT:
  810. a = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[lev]);
  811. if ((lr & XFS_BTCUR_LEFTRA) && be32_to_cpu(a->bb_leftsib) != NULLAGBLOCK) {
  812. xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
  813. be32_to_cpu(a->bb_leftsib), 1);
  814. rval++;
  815. }
  816. if ((lr & XFS_BTCUR_RIGHTRA) && be32_to_cpu(a->bb_rightsib) != NULLAGBLOCK) {
  817. xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
  818. be32_to_cpu(a->bb_rightsib), 1);
  819. rval++;
  820. }
  821. break;
  822. case XFS_BTNUM_BMAP:
  823. b = XFS_BUF_TO_BMBT_BLOCK(cur->bc_bufs[lev]);
  824. if ((lr & XFS_BTCUR_LEFTRA) && be64_to_cpu(b->bb_leftsib) != NULLDFSBNO) {
  825. xfs_btree_reada_bufl(cur->bc_mp, be64_to_cpu(b->bb_leftsib), 1);
  826. rval++;
  827. }
  828. if ((lr & XFS_BTCUR_RIGHTRA) && be64_to_cpu(b->bb_rightsib) != NULLDFSBNO) {
  829. xfs_btree_reada_bufl(cur->bc_mp, be64_to_cpu(b->bb_rightsib), 1);
  830. rval++;
  831. }
  832. break;
  833. case XFS_BTNUM_INO:
  834. i = XFS_BUF_TO_INOBT_BLOCK(cur->bc_bufs[lev]);
  835. if ((lr & XFS_BTCUR_LEFTRA) && be32_to_cpu(i->bb_leftsib) != NULLAGBLOCK) {
  836. xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.i.agno,
  837. be32_to_cpu(i->bb_leftsib), 1);
  838. rval++;
  839. }
  840. if ((lr & XFS_BTCUR_RIGHTRA) && be32_to_cpu(i->bb_rightsib) != NULLAGBLOCK) {
  841. xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.i.agno,
  842. be32_to_cpu(i->bb_rightsib), 1);
  843. rval++;
  844. }
  845. break;
  846. default:
  847. ASSERT(0);
  848. }
  849. return rval;
  850. }
  851. /*
  852. * Set the buffer for level "lev" in the cursor to bp, releasing
  853. * any previous buffer.
  854. */
  855. void
  856. xfs_btree_setbuf(
  857. xfs_btree_cur_t *cur, /* btree cursor */
  858. int lev, /* level in btree */
  859. xfs_buf_t *bp) /* new buffer to set */
  860. {
  861. xfs_btree_block_t *b; /* btree block */
  862. xfs_buf_t *obp; /* old buffer pointer */
  863. obp = cur->bc_bufs[lev];
  864. if (obp)
  865. xfs_trans_brelse(cur->bc_tp, obp);
  866. cur->bc_bufs[lev] = bp;
  867. cur->bc_ra[lev] = 0;
  868. if (!bp)
  869. return;
  870. b = XFS_BUF_TO_BLOCK(bp);
  871. if (XFS_BTREE_LONG_PTRS(cur->bc_btnum)) {
  872. if (be64_to_cpu(b->bb_u.l.bb_leftsib) == NULLDFSBNO)
  873. cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
  874. if (be64_to_cpu(b->bb_u.l.bb_rightsib) == NULLDFSBNO)
  875. cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
  876. } else {
  877. if (be32_to_cpu(b->bb_u.s.bb_leftsib) == NULLAGBLOCK)
  878. cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
  879. if (be32_to_cpu(b->bb_u.s.bb_rightsib) == NULLAGBLOCK)
  880. cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
  881. }
  882. }