aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs
diff options
context:
space:
mode:
authorChristoph Hellwig <hch@infradead.org>2008-10-30 01:55:45 -0400
committerLachlan McIlroy <lachlan@sgi.com>2008-10-30 01:55:45 -0400
commit637aa50f461b8ea6b1e8bf9877b0d13d00085043 (patch)
treea7c00b821dca04fe90614461749b74eff40bd8ed /fs/xfs
parent65f1eaeac0efc968797f3ac955b85ba3f5d4f9c8 (diff)
[XFS] implement generic xfs_btree_increment
From: Dave Chinner <dgc@sgi.com> Because this is the first major generic btree routine this patch includes some infrastrucure, first a few routines to deal with a btree block that can be either in short or long form, second xfs_btree_read_buf_block, which is the new central routine to read a btree block given a cursor, and third the new xfs_btree_ptr_addr routine to calculate the address for a given btree pointer record. [hch: split out from bigger patch and minor adaptions] SGI-PV: 985583 SGI-Modid: xfs-linux-melb:xfs-kern:32190a Signed-off-by: Christoph Hellwig <hch@infradead.org> Signed-off-by: Lachlan McIlroy <lachlan@sgi.com> Signed-off-by: Bill O'Donnell <billodo@sgi.com> Signed-off-by: David Chinner <david@fromorbit.com>
Diffstat (limited to 'fs/xfs')
-rw-r--r--fs/xfs/xfs_alloc.c12
-rw-r--r--fs/xfs/xfs_alloc_btree.c99
-rw-r--r--fs/xfs/xfs_alloc_btree.h6
-rw-r--r--fs/xfs/xfs_bmap.c4
-rw-r--r--fs/xfs/xfs_bmap_btree.c88
-rw-r--r--fs/xfs/xfs_bmap_btree.h1
-rw-r--r--fs/xfs/xfs_btree.c222
-rw-r--r--fs/xfs/xfs_btree.h10
-rw-r--r--fs/xfs/xfs_ialloc.c14
-rw-r--r--fs/xfs/xfs_ialloc_btree.c99
-rw-r--r--fs/xfs/xfs_ialloc_btree.h6
-rw-r--r--fs/xfs/xfs_itable.c6
12 files changed, 262 insertions, 305 deletions
diff --git a/fs/xfs/xfs_alloc.c b/fs/xfs/xfs_alloc.c
index 69833eb1de4f..b8bb694b7da3 100644
--- a/fs/xfs/xfs_alloc.c
+++ b/fs/xfs/xfs_alloc.c
@@ -818,7 +818,7 @@ xfs_alloc_ag_vextent_near(
818 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 818 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
819 if (ltlen >= args->minlen) 819 if (ltlen >= args->minlen)
820 break; 820 break;
821 if ((error = xfs_alloc_increment(cnt_cur, 0, &i))) 821 if ((error = xfs_btree_increment(cnt_cur, 0, &i)))
822 goto error0; 822 goto error0;
823 } while (i); 823 } while (i);
824 ASSERT(ltlen >= args->minlen); 824 ASSERT(ltlen >= args->minlen);
@@ -828,7 +828,7 @@ xfs_alloc_ag_vextent_near(
828 i = cnt_cur->bc_ptrs[0]; 828 i = cnt_cur->bc_ptrs[0];
829 for (j = 1, blen = 0, bdiff = 0; 829 for (j = 1, blen = 0, bdiff = 0;
830 !error && j && (blen < args->maxlen || bdiff > 0); 830 !error && j && (blen < args->maxlen || bdiff > 0);
831 error = xfs_alloc_increment(cnt_cur, 0, &j)) { 831 error = xfs_btree_increment(cnt_cur, 0, &j)) {
832 /* 832 /*
833 * For each entry, decide if it's better than 833 * For each entry, decide if it's better than
834 * the previous best entry. 834 * the previous best entry.
@@ -938,7 +938,7 @@ xfs_alloc_ag_vextent_near(
938 * Increment the cursor, so we will point at the entry just right 938 * Increment the cursor, so we will point at the entry just right
939 * of the leftward entry if any, or to the leftmost entry. 939 * of the leftward entry if any, or to the leftmost entry.
940 */ 940 */
941 if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i))) 941 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
942 goto error0; 942 goto error0;
943 if (!i) { 943 if (!i) {
944 /* 944 /*
@@ -977,7 +977,7 @@ xfs_alloc_ag_vextent_near(
977 args->minlen, &gtbnoa, &gtlena); 977 args->minlen, &gtbnoa, &gtlena);
978 if (gtlena >= args->minlen) 978 if (gtlena >= args->minlen)
979 break; 979 break;
980 if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i))) 980 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
981 goto error0; 981 goto error0;
982 if (!i) { 982 if (!i) {
983 xfs_btree_del_cursor(bno_cur_gt, 983 xfs_btree_del_cursor(bno_cur_gt,
@@ -1066,7 +1066,7 @@ xfs_alloc_ag_vextent_near(
1066 /* 1066 /*
1067 * Fell off the right end. 1067 * Fell off the right end.
1068 */ 1068 */
1069 if ((error = xfs_alloc_increment( 1069 if ((error = xfs_btree_increment(
1070 bno_cur_gt, 0, &i))) 1070 bno_cur_gt, 0, &i)))
1071 goto error0; 1071 goto error0;
1072 if (!i) { 1072 if (!i) {
@@ -1548,7 +1548,7 @@ xfs_free_ag_extent(
1548 * Look for a neighboring block on the right (higher block numbers) 1548 * Look for a neighboring block on the right (higher block numbers)
1549 * that is contiguous with this space. 1549 * that is contiguous with this space.
1550 */ 1550 */
1551 if ((error = xfs_alloc_increment(bno_cur, 0, &haveright))) 1551 if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
1552 goto error0; 1552 goto error0;
1553 if (haveright) { 1553 if (haveright) {
1554 /* 1554 /*
diff --git a/fs/xfs/xfs_alloc_btree.c b/fs/xfs/xfs_alloc_btree.c
index 9e2421c31a36..febc2d5ea295 100644
--- a/fs/xfs/xfs_alloc_btree.c
+++ b/fs/xfs/xfs_alloc_btree.c
@@ -303,7 +303,7 @@ xfs_alloc_delrec(
303 */ 303 */
304 i = xfs_btree_lastrec(tcur, level); 304 i = xfs_btree_lastrec(tcur, level);
305 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 305 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
306 if ((error = xfs_alloc_increment(tcur, level, &i))) 306 if ((error = xfs_btree_increment(tcur, level, &i)))
307 goto error0; 307 goto error0;
308 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 308 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
309 i = xfs_btree_lastrec(tcur, level); 309 i = xfs_btree_lastrec(tcur, level);
@@ -517,7 +517,7 @@ xfs_alloc_delrec(
517 * us, increment the cursor at that level. 517 * us, increment the cursor at that level.
518 */ 518 */
519 else if (level + 1 < cur->bc_nlevels && 519 else if (level + 1 < cur->bc_nlevels &&
520 (error = xfs_alloc_increment(cur, level + 1, &i))) 520 (error = xfs_btree_increment(cur, level + 1, &i)))
521 return error; 521 return error;
522 /* 522 /*
523 * Fix up the number of records in the surviving block. 523 * Fix up the number of records in the surviving block.
@@ -1134,7 +1134,7 @@ xfs_alloc_lookup(
1134 int i; 1134 int i;
1135 1135
1136 cur->bc_ptrs[0] = keyno; 1136 cur->bc_ptrs[0] = keyno;
1137 if ((error = xfs_alloc_increment(cur, 0, &i))) 1137 if ((error = xfs_btree_increment(cur, 0, &i)))
1138 return error; 1138 return error;
1139 XFS_WANT_CORRUPTED_RETURN(i == 1); 1139 XFS_WANT_CORRUPTED_RETURN(i == 1);
1140 *stat = 1; 1140 *stat = 1;
@@ -1570,7 +1570,7 @@ xfs_alloc_rshift(
1570 return error; 1570 return error;
1571 i = xfs_btree_lastrec(tcur, level); 1571 i = xfs_btree_lastrec(tcur, level);
1572 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1572 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1573 if ((error = xfs_alloc_increment(tcur, level, &i)) || 1573 if ((error = xfs_btree_increment(tcur, level, &i)) ||
1574 (error = xfs_alloc_updkey(tcur, rkp, level + 1))) 1574 (error = xfs_alloc_updkey(tcur, rkp, level + 1)))
1575 goto error0; 1575 goto error0;
1576 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 1576 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
@@ -1943,97 +1943,6 @@ xfs_alloc_get_rec(
1943} 1943}
1944 1944
1945/* 1945/*
1946 * Increment cursor by one record at the level.
1947 * For nonzero levels the leaf-ward information is untouched.
1948 */
1949int /* error */
1950xfs_alloc_increment(
1951 xfs_btree_cur_t *cur, /* btree cursor */
1952 int level, /* level in btree, 0 is leaf */
1953 int *stat) /* success/failure */
1954{
1955 xfs_alloc_block_t *block; /* btree block */
1956 xfs_buf_t *bp; /* tree block buffer */
1957 int error; /* error return value */
1958 int lev; /* btree level */
1959
1960 ASSERT(level < cur->bc_nlevels);
1961 /*
1962 * Read-ahead to the right at this level.
1963 */
1964 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1965 /*
1966 * Get a pointer to the btree block.
1967 */
1968 bp = cur->bc_bufs[level];
1969 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1970#ifdef DEBUG
1971 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1972 return error;
1973#endif
1974 /*
1975 * Increment the ptr at this level. If we're still in the block
1976 * then we're done.
1977 */
1978 if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
1979 *stat = 1;
1980 return 0;
1981 }
1982 /*
1983 * If we just went off the right edge of the tree, return failure.
1984 */
1985 if (be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK) {
1986 *stat = 0;
1987 return 0;
1988 }
1989 /*
1990 * March up the tree incrementing pointers.
1991 * Stop when we don't go off the right edge of a block.
1992 */
1993 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1994 bp = cur->bc_bufs[lev];
1995 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1996#ifdef DEBUG
1997 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1998 return error;
1999#endif
2000 if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
2001 break;
2002 /*
2003 * Read-ahead the right block, we're going to read it
2004 * in the next loop.
2005 */
2006 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
2007 }
2008 /*
2009 * If we went off the root then we are seriously confused.
2010 */
2011 ASSERT(lev < cur->bc_nlevels);
2012 /*
2013 * Now walk back down the tree, fixing up the cursor's buffer
2014 * pointers and key numbers.
2015 */
2016 for (bp = cur->bc_bufs[lev], block = XFS_BUF_TO_ALLOC_BLOCK(bp);
2017 lev > level; ) {
2018 xfs_agblock_t agbno; /* block number of btree block */
2019
2020 agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur));
2021 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
2022 cur->bc_private.a.agno, agbno, 0, &bp,
2023 XFS_ALLOC_BTREE_REF)))
2024 return error;
2025 lev--;
2026 xfs_btree_setbuf(cur, lev, bp);
2027 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
2028 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
2029 return error;
2030 cur->bc_ptrs[lev] = 1;
2031 }
2032 *stat = 1;
2033 return 0;
2034}
2035
2036/*
2037 * Insert the current record at the point referenced by cur. 1946 * Insert the current record at the point referenced by cur.
2038 * The cursor may be inconsistent on return if splits have been done. 1947 * The cursor may be inconsistent on return if splits have been done.
2039 */ 1948 */
diff --git a/fs/xfs/xfs_alloc_btree.h b/fs/xfs/xfs_alloc_btree.h
index 60735384a4ce..643cfabbf675 100644
--- a/fs/xfs/xfs_alloc_btree.h
+++ b/fs/xfs/xfs_alloc_btree.h
@@ -114,12 +114,6 @@ extern int xfs_alloc_get_rec(struct xfs_btree_cur *cur, xfs_agblock_t *bno,
114 xfs_extlen_t *len, int *stat); 114 xfs_extlen_t *len, int *stat);
115 115
116/* 116/*
117 * Increment cursor by one record at the level.
118 * For nonzero levels the leaf-ward information is untouched.
119 */
120extern int xfs_alloc_increment(struct xfs_btree_cur *cur, int level, int *stat);
121
122/*
123 * Insert the current record at the point referenced by cur. 117 * Insert the current record at the point referenced by cur.
124 * The cursor may be inconsistent on return if splits have been done. 118 * The cursor may be inconsistent on return if splits have been done.
125 */ 119 */
diff --git a/fs/xfs/xfs_bmap.c b/fs/xfs/xfs_bmap.c
index a84d0c30b485..4b1ec44c80aa 100644
--- a/fs/xfs/xfs_bmap.c
+++ b/fs/xfs/xfs_bmap.c
@@ -1646,7 +1646,7 @@ xfs_bmap_add_extent_unwritten_real(
1646 PREV.br_blockcount - new->br_blockcount, 1646 PREV.br_blockcount - new->br_blockcount,
1647 oldext))) 1647 oldext)))
1648 goto done; 1648 goto done;
1649 if ((error = xfs_bmbt_increment(cur, 0, &i))) 1649 if ((error = xfs_btree_increment(cur, 0, &i)))
1650 goto done; 1650 goto done;
1651 if ((error = xfs_bmbt_update(cur, new->br_startoff, 1651 if ((error = xfs_bmbt_update(cur, new->br_startoff,
1652 new->br_startblock, 1652 new->br_startblock,
@@ -3253,7 +3253,7 @@ xfs_bmap_del_extent(
3253 got.br_startblock, temp, 3253 got.br_startblock, temp,
3254 got.br_state))) 3254 got.br_state)))
3255 goto done; 3255 goto done;
3256 if ((error = xfs_bmbt_increment(cur, 0, &i))) 3256 if ((error = xfs_btree_increment(cur, 0, &i)))
3257 goto done; 3257 goto done;
3258 cur->bc_rec.b = new; 3258 cur->bc_rec.b = new;
3259 error = xfs_bmbt_insert(cur, &i); 3259 error = xfs_bmbt_insert(cur, &i);
diff --git a/fs/xfs/xfs_bmap_btree.c b/fs/xfs/xfs_bmap_btree.c
index a71010abf6ec..2d29a4980cf7 100644
--- a/fs/xfs/xfs_bmap_btree.c
+++ b/fs/xfs/xfs_bmap_btree.c
@@ -254,7 +254,7 @@ xfs_bmbt_delrec(
254 if (rbno != NULLFSBLOCK) { 254 if (rbno != NULLFSBLOCK) {
255 i = xfs_btree_lastrec(tcur, level); 255 i = xfs_btree_lastrec(tcur, level);
256 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 256 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
257 if ((error = xfs_bmbt_increment(tcur, level, &i))) { 257 if ((error = xfs_btree_increment(tcur, level, &i))) {
258 XFS_BMBT_TRACE_CURSOR(cur, ERROR); 258 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
259 goto error0; 259 goto error0;
260 } 260 }
@@ -445,7 +445,7 @@ xfs_bmbt_delrec(
445 cur->bc_bufs[level] = lbp; 445 cur->bc_bufs[level] = lbp;
446 cur->bc_ptrs[level] += lrecs; 446 cur->bc_ptrs[level] += lrecs;
447 cur->bc_ra[level] = 0; 447 cur->bc_ra[level] = 0;
448 } else if ((error = xfs_bmbt_increment(cur, level + 1, &i))) { 448 } else if ((error = xfs_btree_increment(cur, level + 1, &i))) {
449 XFS_BMBT_TRACE_CURSOR(cur, ERROR); 449 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
450 goto error0; 450 goto error0;
451 } 451 }
@@ -929,7 +929,7 @@ xfs_bmbt_lookup(
929 if (dir == XFS_LOOKUP_GE && keyno > be16_to_cpu(block->bb_numrecs) && 929 if (dir == XFS_LOOKUP_GE && keyno > be16_to_cpu(block->bb_numrecs) &&
930 be64_to_cpu(block->bb_rightsib) != NULLDFSBNO) { 930 be64_to_cpu(block->bb_rightsib) != NULLDFSBNO) {
931 cur->bc_ptrs[0] = keyno; 931 cur->bc_ptrs[0] = keyno;
932 if ((error = xfs_bmbt_increment(cur, 0, &i))) { 932 if ((error = xfs_btree_increment(cur, 0, &i))) {
933 XFS_BMBT_TRACE_CURSOR(cur, ERROR); 933 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
934 return error; 934 return error;
935 } 935 }
@@ -1202,7 +1202,7 @@ xfs_bmbt_rshift(
1202 } 1202 }
1203 i = xfs_btree_lastrec(tcur, level); 1203 i = xfs_btree_lastrec(tcur, level);
1204 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 1204 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1205 if ((error = xfs_bmbt_increment(tcur, level, &i))) { 1205 if ((error = xfs_btree_increment(tcur, level, &i))) {
1206 XFS_BMBT_TRACE_CURSOR(tcur, ERROR); 1206 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1207 goto error1; 1207 goto error1;
1208 } 1208 }
@@ -1761,86 +1761,6 @@ xfs_bmbt_disk_get_startoff(
1761} 1761}
1762 1762
1763/* 1763/*
1764 * Increment cursor by one record at the level.
1765 * For nonzero levels the leaf-ward information is untouched.
1766 */
1767int /* error */
1768xfs_bmbt_increment(
1769 xfs_btree_cur_t *cur,
1770 int level,
1771 int *stat) /* success/failure */
1772{
1773 xfs_bmbt_block_t *block;
1774 xfs_buf_t *bp;
1775 int error; /* error return value */
1776 xfs_fsblock_t fsbno;
1777 int lev;
1778 xfs_mount_t *mp;
1779 xfs_trans_t *tp;
1780
1781 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1782 XFS_BMBT_TRACE_ARGI(cur, level);
1783 ASSERT(level < cur->bc_nlevels);
1784
1785 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1786 block = xfs_bmbt_get_block(cur, level, &bp);
1787#ifdef DEBUG
1788 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1789 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1790 return error;
1791 }
1792#endif
1793 if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
1794 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1795 *stat = 1;
1796 return 0;
1797 }
1798 if (be64_to_cpu(block->bb_rightsib) == NULLDFSBNO) {
1799 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1800 *stat = 0;
1801 return 0;
1802 }
1803 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1804 block = xfs_bmbt_get_block(cur, lev, &bp);
1805#ifdef DEBUG
1806 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
1807 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1808 return error;
1809 }
1810#endif
1811 if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
1812 break;
1813 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1814 }
1815 if (lev == cur->bc_nlevels) {
1816 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1817 *stat = 0;
1818 return 0;
1819 }
1820 tp = cur->bc_tp;
1821 mp = cur->bc_mp;
1822 for (block = xfs_bmbt_get_block(cur, lev, &bp); lev > level; ) {
1823 fsbno = be64_to_cpu(*XFS_BMAP_PTR_IADDR(block, cur->bc_ptrs[lev], cur));
1824 if ((error = xfs_btree_read_bufl(mp, tp, fsbno, 0, &bp,
1825 XFS_BMAP_BTREE_REF))) {
1826 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1827 return error;
1828 }
1829 lev--;
1830 xfs_btree_setbuf(cur, lev, bp);
1831 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1832 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
1833 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1834 return error;
1835 }
1836 cur->bc_ptrs[lev] = 1;
1837 }
1838 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1839 *stat = 1;
1840 return 0;
1841}
1842
1843/*
1844 * Insert the current record at the point referenced by cur. 1764 * Insert the current record at the point referenced by cur.
1845 * 1765 *
1846 * A multi-level split of the tree on insert will invalidate the original 1766 * A multi-level split of the tree on insert will invalidate the original
diff --git a/fs/xfs/xfs_bmap_btree.h b/fs/xfs/xfs_bmap_btree.h
index 5628d89cea45..a45be38d9a37 100644
--- a/fs/xfs/xfs_bmap_btree.h
+++ b/fs/xfs/xfs_bmap_btree.h
@@ -251,7 +251,6 @@ extern void xfs_bmbt_disk_get_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s);
251extern xfs_filblks_t xfs_bmbt_disk_get_blockcount(xfs_bmbt_rec_t *r); 251extern xfs_filblks_t xfs_bmbt_disk_get_blockcount(xfs_bmbt_rec_t *r);
252extern xfs_fileoff_t xfs_bmbt_disk_get_startoff(xfs_bmbt_rec_t *r); 252extern xfs_fileoff_t xfs_bmbt_disk_get_startoff(xfs_bmbt_rec_t *r);
253 253
254extern int xfs_bmbt_increment(struct xfs_btree_cur *, int, int *);
255extern int xfs_bmbt_insert(struct xfs_btree_cur *, int *); 254extern int xfs_bmbt_insert(struct xfs_btree_cur *, int *);
256extern void xfs_bmbt_log_block(struct xfs_btree_cur *, struct xfs_buf *, int); 255extern void xfs_bmbt_log_block(struct xfs_btree_cur *, struct xfs_buf *, int);
257extern void xfs_bmbt_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int, 256extern void xfs_bmbt_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int,
diff --git a/fs/xfs/xfs_btree.c b/fs/xfs/xfs_btree.c
index 4aec7c7d5ba9..e9ab86b7990e 100644
--- a/fs/xfs/xfs_btree.c
+++ b/fs/xfs/xfs_btree.c
@@ -35,6 +35,7 @@
35#include "xfs_dinode.h" 35#include "xfs_dinode.h"
36#include "xfs_inode.h" 36#include "xfs_inode.h"
37#include "xfs_btree.h" 37#include "xfs_btree.h"
38#include "xfs_btree_trace.h"
38#include "xfs_ialloc.h" 39#include "xfs_ialloc.h"
39#include "xfs_error.h" 40#include "xfs_error.h"
40 41
@@ -949,3 +950,224 @@ xfs_btree_setbuf(
949 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA; 950 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
950 } 951 }
951} 952}
953
954STATIC int
955xfs_btree_ptr_is_null(
956 struct xfs_btree_cur *cur,
957 union xfs_btree_ptr *ptr)
958{
959 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
960 return be64_to_cpu(ptr->l) == NULLFSBLOCK;
961 else
962 return be32_to_cpu(ptr->s) == NULLAGBLOCK;
963}
964
965/*
966 * Get/set/init sibling pointers
967 */
968STATIC void
969xfs_btree_get_sibling(
970 struct xfs_btree_cur *cur,
971 struct xfs_btree_block *block,
972 union xfs_btree_ptr *ptr,
973 int lr)
974{
975 ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
976
977 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
978 if (lr == XFS_BB_RIGHTSIB)
979 ptr->l = block->bb_u.l.bb_rightsib;
980 else
981 ptr->l = block->bb_u.l.bb_leftsib;
982 } else {
983 if (lr == XFS_BB_RIGHTSIB)
984 ptr->s = block->bb_u.s.bb_rightsib;
985 else
986 ptr->s = block->bb_u.s.bb_leftsib;
987 }
988}
989
990STATIC xfs_daddr_t
991xfs_btree_ptr_to_daddr(
992 struct xfs_btree_cur *cur,
993 union xfs_btree_ptr *ptr)
994{
995 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
996 ASSERT(be64_to_cpu(ptr->l) != NULLFSBLOCK);
997
998 return XFS_FSB_TO_DADDR(cur->bc_mp, be64_to_cpu(ptr->l));
999 } else {
1000 ASSERT(cur->bc_private.a.agno != NULLAGNUMBER);
1001 ASSERT(be32_to_cpu(ptr->s) != NULLAGBLOCK);
1002
1003 return XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_private.a.agno,
1004 be32_to_cpu(ptr->s));
1005 }
1006}
1007
1008STATIC void
1009xfs_btree_set_refs(
1010 struct xfs_btree_cur *cur,
1011 struct xfs_buf *bp)
1012{
1013 switch (cur->bc_btnum) {
1014 case XFS_BTNUM_BNO:
1015 case XFS_BTNUM_CNT:
1016 XFS_BUF_SET_VTYPE_REF(*bpp, B_FS_MAP, XFS_ALLOC_BTREE_REF);
1017 break;
1018 case XFS_BTNUM_INO:
1019 XFS_BUF_SET_VTYPE_REF(*bpp, B_FS_INOMAP, XFS_INO_BTREE_REF);
1020 break;
1021 case XFS_BTNUM_BMAP:
1022 XFS_BUF_SET_VTYPE_REF(*bpp, B_FS_MAP, XFS_BMAP_BTREE_REF);
1023 break;
1024 default:
1025 ASSERT(0);
1026 }
1027}
1028
1029/*
1030 * Read in the buffer at the given ptr and return the buffer and
1031 * the block pointer within the buffer.
1032 */
1033STATIC int
1034xfs_btree_read_buf_block(
1035 struct xfs_btree_cur *cur,
1036 union xfs_btree_ptr *ptr,
1037 int level,
1038 int flags,
1039 struct xfs_btree_block **block,
1040 struct xfs_buf **bpp)
1041{
1042 struct xfs_mount *mp = cur->bc_mp;
1043 xfs_daddr_t d;
1044 int error;
1045
1046 /* need to sort out how callers deal with failures first */
1047 ASSERT(!(flags & XFS_BUF_TRYLOCK));
1048
1049 d = xfs_btree_ptr_to_daddr(cur, ptr);
1050 error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d,
1051 mp->m_bsize, flags, bpp);
1052 if (error)
1053 return error;
1054
1055 ASSERT(*bpp != NULL);
1056 ASSERT(!XFS_BUF_GETERROR(*bpp));
1057
1058 xfs_btree_set_refs(cur, *bpp);
1059 *block = XFS_BUF_TO_BLOCK(*bpp);
1060
1061 error = xfs_btree_check_block(cur, *block, level, *bpp);
1062 if (error)
1063 xfs_trans_brelse(cur->bc_tp, *bpp);
1064 return error;
1065}
1066
1067/*
1068 * Increment cursor by one record at the level.
1069 * For nonzero levels the leaf-ward information is untouched.
1070 */
1071int /* error */
1072xfs_btree_increment(
1073 struct xfs_btree_cur *cur,
1074 int level,
1075 int *stat) /* success/failure */
1076{
1077 struct xfs_btree_block *block;
1078 union xfs_btree_ptr ptr;
1079 struct xfs_buf *bp;
1080 int error; /* error return value */
1081 int lev;
1082
1083 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1084 XFS_BTREE_TRACE_ARGI(cur, level);
1085
1086 ASSERT(level < cur->bc_nlevels);
1087
1088 /* Read-ahead to the right at this level. */
1089 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1090
1091 /* Get a pointer to the btree block. */
1092 block = xfs_btree_get_block(cur, level, &bp);
1093
1094#ifdef DEBUG
1095 error = xfs_btree_check_block(cur, block, level, bp);
1096 if (error)
1097 goto error0;
1098#endif
1099
1100 /* We're done if we remain in the block after the increment. */
1101 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block))
1102 goto out1;
1103
1104 /* Fail if we just went off the right edge of the tree. */
1105 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1106 if (xfs_btree_ptr_is_null(cur, &ptr))
1107 goto out0;
1108
1109 XFS_BTREE_STATS_INC(cur, increment);
1110
1111 /*
1112 * March up the tree incrementing pointers.
1113 * Stop when we don't go off the right edge of a block.
1114 */
1115 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1116 block = xfs_btree_get_block(cur, lev, &bp);
1117
1118#ifdef DEBUG
1119 error = xfs_btree_check_block(cur, block, lev, bp);
1120 if (error)
1121 goto error0;
1122#endif
1123
1124 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block))
1125 break;
1126
1127 /* Read-ahead the right block for the next loop. */
1128 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1129 }
1130
1131 /*
1132 * If we went off the root then we are either seriously
1133 * confused or have the tree root in an inode.
1134 */
1135 if (lev == cur->bc_nlevels) {
1136 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1137 goto out0;
1138 ASSERT(0);
1139 error = EFSCORRUPTED;
1140 goto error0;
1141 }
1142 ASSERT(lev < cur->bc_nlevels);
1143
1144 /*
1145 * Now walk back down the tree, fixing up the cursor's buffer
1146 * pointers and key numbers.
1147 */
1148 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1149 union xfs_btree_ptr *ptrp;
1150
1151 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1152 error = xfs_btree_read_buf_block(cur, ptrp, --lev,
1153 0, &block, &bp);
1154 if (error)
1155 goto error0;
1156
1157 xfs_btree_setbuf(cur, lev, bp);
1158 cur->bc_ptrs[lev] = 1;
1159 }
1160out1:
1161 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1162 *stat = 1;
1163 return 0;
1164
1165out0:
1166 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1167 *stat = 0;
1168 return 0;
1169
1170error0:
1171 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1172 return error;
1173}
diff --git a/fs/xfs/xfs_btree.h b/fs/xfs/xfs_btree.h
index 593f82b01b6f..f5a4b8ec4cdd 100644
--- a/fs/xfs/xfs_btree.h
+++ b/fs/xfs/xfs_btree.h
@@ -503,8 +503,18 @@ xfs_btree_setbuf(
503 503
504 504
505/* 505/*
506 * Common btree core entry points.
507 */
508int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
509
510/*
506 * Helpers. 511 * Helpers.
507 */ 512 */
513static inline int xfs_btree_get_numrecs(struct xfs_btree_block *block)
514{
515 return be16_to_cpu(block->bb_numrecs);
516}
517
508static inline int xfs_btree_get_level(struct xfs_btree_block *block) 518static inline int xfs_btree_get_level(struct xfs_btree_block *block)
509{ 519{
510 return be16_to_cpu(block->bb_level); 520 return be16_to_cpu(block->bb_level);
diff --git a/fs/xfs/xfs_ialloc.c b/fs/xfs/xfs_ialloc.c
index 11bb169561ce..3a8f0670e070 100644
--- a/fs/xfs/xfs_ialloc.c
+++ b/fs/xfs/xfs_ialloc.c
@@ -695,7 +695,7 @@ nextag:
695 goto error0; 695 goto error0;
696 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 696 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
697 freecount += rec.ir_freecount; 697 freecount += rec.ir_freecount;
698 if ((error = xfs_inobt_increment(cur, 0, &i))) 698 if ((error = xfs_btree_increment(cur, 0, &i)))
699 goto error0; 699 goto error0;
700 } while (i == 1); 700 } while (i == 1);
701 701
@@ -753,7 +753,7 @@ nextag:
753 /* 753 /*
754 * Search right with cur, go forward 1 record. 754 * Search right with cur, go forward 1 record.
755 */ 755 */
756 if ((error = xfs_inobt_increment(cur, 0, &i))) 756 if ((error = xfs_btree_increment(cur, 0, &i)))
757 goto error1; 757 goto error1;
758 doneright = !i; 758 doneright = !i;
759 if (!doneright) { 759 if (!doneright) {
@@ -835,7 +835,7 @@ nextag:
835 * further right. 835 * further right.
836 */ 836 */
837 else { 837 else {
838 if ((error = xfs_inobt_increment(cur, 0, 838 if ((error = xfs_btree_increment(cur, 0,
839 &i))) 839 &i)))
840 goto error1; 840 goto error1;
841 doneright = !i; 841 doneright = !i;
@@ -890,7 +890,7 @@ nextag:
890 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 890 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
891 if (rec.ir_freecount > 0) 891 if (rec.ir_freecount > 0)
892 break; 892 break;
893 if ((error = xfs_inobt_increment(cur, 0, &i))) 893 if ((error = xfs_btree_increment(cur, 0, &i)))
894 goto error0; 894 goto error0;
895 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 895 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
896 } 896 }
@@ -924,7 +924,7 @@ nextag:
924 goto error0; 924 goto error0;
925 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 925 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
926 freecount += rec.ir_freecount; 926 freecount += rec.ir_freecount;
927 if ((error = xfs_inobt_increment(cur, 0, &i))) 927 if ((error = xfs_btree_increment(cur, 0, &i)))
928 goto error0; 928 goto error0;
929 } while (i == 1); 929 } while (i == 1);
930 ASSERT(freecount == be32_to_cpu(agi->agi_freecount) || 930 ASSERT(freecount == be32_to_cpu(agi->agi_freecount) ||
@@ -1033,7 +1033,7 @@ xfs_difree(
1033 goto error0; 1033 goto error0;
1034 if (i) { 1034 if (i) {
1035 freecount += rec.ir_freecount; 1035 freecount += rec.ir_freecount;
1036 if ((error = xfs_inobt_increment(cur, 0, &i))) 1036 if ((error = xfs_btree_increment(cur, 0, &i)))
1037 goto error0; 1037 goto error0;
1038 } 1038 }
1039 } while (i == 1); 1039 } while (i == 1);
@@ -1138,7 +1138,7 @@ xfs_difree(
1138 goto error0; 1138 goto error0;
1139 if (i) { 1139 if (i) {
1140 freecount += rec.ir_freecount; 1140 freecount += rec.ir_freecount;
1141 if ((error = xfs_inobt_increment(cur, 0, &i))) 1141 if ((error = xfs_btree_increment(cur, 0, &i)))
1142 goto error0; 1142 goto error0;
1143 } 1143 }
1144 } while (i == 1); 1144 } while (i == 1);
diff --git a/fs/xfs/xfs_ialloc_btree.c b/fs/xfs/xfs_ialloc_btree.c
index fc6db94492dc..41717da63696 100644
--- a/fs/xfs/xfs_ialloc_btree.c
+++ b/fs/xfs/xfs_ialloc_btree.c
@@ -253,7 +253,7 @@ xfs_inobt_delrec(
253 */ 253 */
254 i = xfs_btree_lastrec(tcur, level); 254 i = xfs_btree_lastrec(tcur, level);
255 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 255 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
256 if ((error = xfs_inobt_increment(tcur, level, &i))) 256 if ((error = xfs_btree_increment(tcur, level, &i)))
257 goto error0; 257 goto error0;
258 XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 258 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
259 i = xfs_btree_lastrec(tcur, level); 259 i = xfs_btree_lastrec(tcur, level);
@@ -463,7 +463,7 @@ xfs_inobt_delrec(
463 * us, increment the cursor at that level. 463 * us, increment the cursor at that level.
464 */ 464 */
465 else if (level + 1 < cur->bc_nlevels && 465 else if (level + 1 < cur->bc_nlevels &&
466 (error = xfs_alloc_increment(cur, level + 1, &i))) 466 (error = xfs_btree_increment(cur, level + 1, &i)))
467 return error; 467 return error;
468 /* 468 /*
469 * Fix up the number of records in the surviving block. 469 * Fix up the number of records in the surviving block.
@@ -1014,7 +1014,7 @@ xfs_inobt_lookup(
1014 int i; 1014 int i;
1015 1015
1016 cur->bc_ptrs[0] = keyno; 1016 cur->bc_ptrs[0] = keyno;
1017 if ((error = xfs_inobt_increment(cur, 0, &i))) 1017 if ((error = xfs_btree_increment(cur, 0, &i)))
1018 return error; 1018 return error;
1019 ASSERT(i == 1); 1019 ASSERT(i == 1);
1020 *stat = 1; 1020 *stat = 1;
@@ -1443,7 +1443,7 @@ xfs_inobt_rshift(
1443 if ((error = xfs_btree_dup_cursor(cur, &tcur))) 1443 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
1444 return error; 1444 return error;
1445 xfs_btree_lastrec(tcur, level); 1445 xfs_btree_lastrec(tcur, level);
1446 if ((error = xfs_inobt_increment(tcur, level, &i)) || 1446 if ((error = xfs_btree_increment(tcur, level, &i)) ||
1447 (error = xfs_inobt_updkey(tcur, rkp, level + 1))) { 1447 (error = xfs_inobt_updkey(tcur, rkp, level + 1))) {
1448 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR); 1448 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1449 return error; 1449 return error;
@@ -1821,97 +1821,6 @@ xfs_inobt_get_rec(
1821} 1821}
1822 1822
1823/* 1823/*
1824 * Increment cursor by one record at the level.
1825 * For nonzero levels the leaf-ward information is untouched.
1826 */
1827int /* error */
1828xfs_inobt_increment(
1829 xfs_btree_cur_t *cur, /* btree cursor */
1830 int level, /* level in btree, 0 is leaf */
1831 int *stat) /* success/failure */
1832{
1833 xfs_inobt_block_t *block; /* btree block */
1834 xfs_buf_t *bp; /* buffer containing btree block */
1835 int error; /* error return value */
1836 int lev; /* btree level */
1837
1838 ASSERT(level < cur->bc_nlevels);
1839 /*
1840 * Read-ahead to the right at this level.
1841 */
1842 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1843 /*
1844 * Get a pointer to the btree block.
1845 */
1846 bp = cur->bc_bufs[level];
1847 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1848#ifdef DEBUG
1849 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1850 return error;
1851#endif
1852 /*
1853 * Increment the ptr at this level. If we're still in the block
1854 * then we're done.
1855 */
1856 if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
1857 *stat = 1;
1858 return 0;
1859 }
1860 /*
1861 * If we just went off the right edge of the tree, return failure.
1862 */
1863 if (be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK) {
1864 *stat = 0;
1865 return 0;
1866 }
1867 /*
1868 * March up the tree incrementing pointers.
1869 * Stop when we don't go off the right edge of a block.
1870 */
1871 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1872 bp = cur->bc_bufs[lev];
1873 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1874#ifdef DEBUG
1875 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1876 return error;
1877#endif
1878 if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
1879 break;
1880 /*
1881 * Read-ahead the right block, we're going to read it
1882 * in the next loop.
1883 */
1884 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1885 }
1886 /*
1887 * If we went off the root then we are seriously confused.
1888 */
1889 ASSERT(lev < cur->bc_nlevels);
1890 /*
1891 * Now walk back down the tree, fixing up the cursor's buffer
1892 * pointers and key numbers.
1893 */
1894 for (bp = cur->bc_bufs[lev], block = XFS_BUF_TO_INOBT_BLOCK(bp);
1895 lev > level; ) {
1896 xfs_agblock_t agbno; /* block number of btree block */
1897
1898 agbno = be32_to_cpu(*XFS_INOBT_PTR_ADDR(block, cur->bc_ptrs[lev], cur));
1899 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1900 cur->bc_private.a.agno, agbno, 0, &bp,
1901 XFS_INO_BTREE_REF)))
1902 return error;
1903 lev--;
1904 xfs_btree_setbuf(cur, lev, bp);
1905 block = XFS_BUF_TO_INOBT_BLOCK(bp);
1906 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1907 return error;
1908 cur->bc_ptrs[lev] = 1;
1909 }
1910 *stat = 1;
1911 return 0;
1912}
1913
1914/*
1915 * Insert the current record at the point referenced by cur. 1824 * Insert the current record at the point referenced by cur.
1916 * The cursor may be inconsistent on return if splits have been done. 1825 * The cursor may be inconsistent on return if splits have been done.
1917 */ 1826 */
diff --git a/fs/xfs/xfs_ialloc_btree.h b/fs/xfs/xfs_ialloc_btree.h
index eea409349eba..07fed62bcb7b 100644
--- a/fs/xfs/xfs_ialloc_btree.h
+++ b/fs/xfs/xfs_ialloc_btree.h
@@ -136,12 +136,6 @@ extern int xfs_inobt_get_rec(struct xfs_btree_cur *cur, xfs_agino_t *ino,
136 __int32_t *fcnt, xfs_inofree_t *free, int *stat); 136 __int32_t *fcnt, xfs_inofree_t *free, int *stat);
137 137
138/* 138/*
139 * Increment cursor by one record at the level.
140 * For nonzero levels the leaf-ward information is untouched.
141 */
142extern int xfs_inobt_increment(struct xfs_btree_cur *cur, int level, int *stat);
143
144/*
145 * Insert the current record at the point referenced by cur. 139 * Insert the current record at the point referenced by cur.
146 * The cursor may be inconsistent on return if splits have been done. 140 * The cursor may be inconsistent on return if splits have been done.
147 */ 141 */
diff --git a/fs/xfs/xfs_itable.c b/fs/xfs/xfs_itable.c
index a5f02f0e4c2a..42a214b8df9e 100644
--- a/fs/xfs/xfs_itable.c
+++ b/fs/xfs/xfs_itable.c
@@ -471,7 +471,7 @@ xfs_bulkstat(
471 * In any case, increment to the next record. 471 * In any case, increment to the next record.
472 */ 472 */
473 if (!error) 473 if (!error)
474 error = xfs_inobt_increment(cur, 0, &tmp); 474 error = xfs_btree_increment(cur, 0, &tmp);
475 } else { 475 } else {
476 /* 476 /*
477 * Start of ag. Lookup the first inode chunk. 477 * Start of ag. Lookup the first inode chunk.
@@ -538,7 +538,7 @@ xfs_bulkstat(
538 * Set agino to after this chunk and bump the cursor. 538 * Set agino to after this chunk and bump the cursor.
539 */ 539 */
540 agino = gino + XFS_INODES_PER_CHUNK; 540 agino = gino + XFS_INODES_PER_CHUNK;
541 error = xfs_inobt_increment(cur, 0, &tmp); 541 error = xfs_btree_increment(cur, 0, &tmp);
542 cond_resched(); 542 cond_resched();
543 } 543 }
544 /* 544 /*
@@ -885,7 +885,7 @@ xfs_inumbers(
885 bufidx = 0; 885 bufidx = 0;
886 } 886 }
887 if (left) { 887 if (left) {
888 error = xfs_inobt_increment(cur, 0, &tmp); 888 error = xfs_btree_increment(cur, 0, &tmp);
889 if (error) { 889 if (error) {
890 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 890 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
891 cur = NULL; 891 cur = NULL;
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-12 08:30:21 -0500