aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_bmap_btree.c
diff options
context:
space:
mode:
authorChristoph Hellwig <hch@infradead.org>2008-10-30 01:56:09 -0400
committerLachlan McIlroy <lachlan@sgi.com>2008-10-30 01:56:09 -0400
commitfe033cc848489851f0c7de48f0b1bab5d744ad8a (patch)
treef69709f4e9c125c528a699c32f439b53ea0969f3 /fs/xfs/xfs_bmap_btree.c
parent8df4da4a0a642d3a016028c0d922bcb4d5a4a6d7 (diff)
[XFS] implement generic xfs_btree_lookup
From: Dave Chinner <dgc@sgi.com> [hch: split out from bigger patch and minor adaptions] SGI-PV: 985583 SGI-Modid: xfs-linux-melb:xfs-kern:32192a 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/xfs_bmap_btree.c')
-rw-r--r--fs/xfs/xfs_bmap_btree.c197
1 files changed, 29 insertions, 168 deletions
diff --git a/fs/xfs/xfs_bmap_btree.c b/fs/xfs/xfs_bmap_btree.c
index 7b5181d34a5b..8403d154ae09 100644
--- a/fs/xfs/xfs_bmap_btree.c
+++ b/fs/xfs/xfs_bmap_btree.c
@@ -813,146 +813,6 @@ xfs_bmbt_log_ptrs(
813} 813}
814 814
815/* 815/*
816 * Lookup the record. The cursor is made to point to it, based on dir.
817 */
818STATIC int /* error */
819xfs_bmbt_lookup(
820 xfs_btree_cur_t *cur,
821 xfs_lookup_t dir,
822 int *stat) /* success/failure */
823{
824 xfs_bmbt_block_t *block=NULL;
825 xfs_buf_t *bp;
826 xfs_daddr_t d;
827 xfs_sfiloff_t diff;
828 int error; /* error return value */
829 xfs_fsblock_t fsbno=0;
830 int high;
831 int i;
832 int keyno=0;
833 xfs_bmbt_key_t *kkbase=NULL;
834 xfs_bmbt_key_t *kkp;
835 xfs_bmbt_rec_t *krbase=NULL;
836 xfs_bmbt_rec_t *krp;
837 int level;
838 int low;
839 xfs_mount_t *mp;
840 xfs_bmbt_ptr_t *pp;
841 xfs_bmbt_irec_t *rp;
842 xfs_fileoff_t startoff;
843 xfs_trans_t *tp;
844
845 XFS_STATS_INC(xs_bmbt_lookup);
846 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
847 XFS_BMBT_TRACE_ARGI(cur, (int)dir);
848 tp = cur->bc_tp;
849 mp = cur->bc_mp;
850 rp = &cur->bc_rec.b;
851 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
852 if (level < cur->bc_nlevels - 1) {
853 d = XFS_FSB_TO_DADDR(mp, fsbno);
854 bp = cur->bc_bufs[level];
855 if (bp && XFS_BUF_ADDR(bp) != d)
856 bp = NULL;
857 if (!bp) {
858 if ((error = xfs_btree_read_bufl(mp, tp, fsbno,
859 0, &bp, XFS_BMAP_BTREE_REF))) {
860 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
861 return error;
862 }
863 xfs_btree_setbuf(cur, level, bp);
864 block = XFS_BUF_TO_BMBT_BLOCK(bp);
865 if ((error = xfs_btree_check_lblock(cur, block,
866 level, bp))) {
867 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
868 return error;
869 }
870 } else
871 block = XFS_BUF_TO_BMBT_BLOCK(bp);
872 } else
873 block = xfs_bmbt_get_block(cur, level, &bp);
874 if (diff == 0)
875 keyno = 1;
876 else {
877 if (level > 0)
878 kkbase = XFS_BMAP_KEY_IADDR(block, 1, cur);
879 else
880 krbase = XFS_BMAP_REC_IADDR(block, 1, cur);
881 low = 1;
882 if (!(high = be16_to_cpu(block->bb_numrecs))) {
883 ASSERT(level == 0);
884 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
885 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
886 *stat = 0;
887 return 0;
888 }
889 while (low <= high) {
890 XFS_STATS_INC(xs_bmbt_compare);
891 keyno = (low + high) >> 1;
892 if (level > 0) {
893 kkp = kkbase + keyno - 1;
894 startoff = be64_to_cpu(kkp->br_startoff);
895 } else {
896 krp = krbase + keyno - 1;
897 startoff = xfs_bmbt_disk_get_startoff(krp);
898 }
899 diff = (xfs_sfiloff_t)
900 (startoff - rp->br_startoff);
901 if (diff < 0)
902 low = keyno + 1;
903 else if (diff > 0)
904 high = keyno - 1;
905 else
906 break;
907 }
908 }
909 if (level > 0) {
910 if (diff > 0 && --keyno < 1)
911 keyno = 1;
912 pp = XFS_BMAP_PTR_IADDR(block, keyno, cur);
913 fsbno = be64_to_cpu(*pp);
914#ifdef DEBUG
915 if ((error = xfs_btree_check_lptr(cur, fsbno, level))) {
916 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
917 return error;
918 }
919#endif
920 cur->bc_ptrs[level] = keyno;
921 }
922 }
923 if (dir != XFS_LOOKUP_LE && diff < 0) {
924 keyno++;
925 /*
926 * If ge search and we went off the end of the block, but it's
927 * not the last block, we're in the wrong block.
928 */
929 if (dir == XFS_LOOKUP_GE && keyno > be16_to_cpu(block->bb_numrecs) &&
930 be64_to_cpu(block->bb_rightsib) != NULLDFSBNO) {
931 cur->bc_ptrs[0] = keyno;
932 if ((error = xfs_btree_increment(cur, 0, &i))) {
933 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
934 return error;
935 }
936 XFS_WANT_CORRUPTED_RETURN(i == 1);
937 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
938 *stat = 1;
939 return 0;
940 }
941 }
942 else if (dir == XFS_LOOKUP_LE && diff > 0)
943 keyno--;
944 cur->bc_ptrs[0] = keyno;
945 if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs)) {
946 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
947 *stat = 0;
948 } else {
949 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
950 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
951 }
952 return 0;
953}
954
955/*
956 * Move 1 record left from cur/level if possible. 816 * Move 1 record left from cur/level if possible.
957 * Update cur to reflect the new path. 817 * Update cur to reflect the new path.
958 */ 818 */
@@ -1809,34 +1669,6 @@ xfs_bmbt_log_recs(
1809 XFS_BMBT_TRACE_CURSOR(cur, EXIT); 1669 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1810} 1670}
1811 1671
1812int /* error */
1813xfs_bmbt_lookup_eq(
1814 xfs_btree_cur_t *cur,
1815 xfs_fileoff_t off,
1816 xfs_fsblock_t bno,
1817 xfs_filblks_t len,
1818 int *stat) /* success/failure */
1819{
1820 cur->bc_rec.b.br_startoff = off;
1821 cur->bc_rec.b.br_startblock = bno;
1822 cur->bc_rec.b.br_blockcount = len;
1823 return xfs_bmbt_lookup(cur, XFS_LOOKUP_EQ, stat);
1824}
1825
1826int /* error */
1827xfs_bmbt_lookup_ge(
1828 xfs_btree_cur_t *cur,
1829 xfs_fileoff_t off,
1830 xfs_fsblock_t bno,
1831 xfs_filblks_t len,
1832 int *stat) /* success/failure */
1833{
1834 cur->bc_rec.b.br_startoff = off;
1835 cur->bc_rec.b.br_startblock = bno;
1836 cur->bc_rec.b.br_blockcount = len;
1837 return xfs_bmbt_lookup(cur, XFS_LOOKUP_GE, stat);
1838}
1839
1840/* 1672/*
1841 * Give the bmap btree a new root block. Copy the old broot contents 1673 * Give the bmap btree a new root block. Copy the old broot contents
1842 * down into a real block and make the broot point to it. 1674 * down into a real block and make the broot point to it.
@@ -2269,6 +2101,32 @@ xfs_bmbt_get_maxrecs(
2269 return XFS_BMAP_BLOCK_IMAXRECS(level, cur); 2101 return XFS_BMAP_BLOCK_IMAXRECS(level, cur);
2270} 2102}
2271 2103
2104STATIC void
2105xfs_bmbt_init_key_from_rec(
2106 union xfs_btree_key *key,
2107 union xfs_btree_rec *rec)
2108{
2109 key->bmbt.br_startoff =
2110 cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
2111}
2112
2113STATIC void
2114xfs_bmbt_init_ptr_from_cur(
2115 struct xfs_btree_cur *cur,
2116 union xfs_btree_ptr *ptr)
2117{
2118 ptr->l = 0;
2119}
2120
2121STATIC __int64_t
2122xfs_bmbt_key_diff(
2123 struct xfs_btree_cur *cur,
2124 union xfs_btree_key *key)
2125{
2126 return (__int64_t)be64_to_cpu(key->bmbt.br_startoff) -
2127 cur->bc_rec.b.br_startoff;
2128}
2129
2272#ifdef XFS_BTREE_TRACE 2130#ifdef XFS_BTREE_TRACE
2273ktrace_t *xfs_bmbt_trace_buf; 2131ktrace_t *xfs_bmbt_trace_buf;
2274 2132
@@ -2360,6 +2218,9 @@ static const struct xfs_btree_ops xfs_bmbt_ops = {
2360 2218
2361 .dup_cursor = xfs_bmbt_dup_cursor, 2219 .dup_cursor = xfs_bmbt_dup_cursor,
2362 .get_maxrecs = xfs_bmbt_get_maxrecs, 2220 .get_maxrecs = xfs_bmbt_get_maxrecs,
2221 .init_key_from_rec = xfs_bmbt_init_key_from_rec,
2222 .init_ptr_from_cur = xfs_bmbt_init_ptr_from_cur,
2223 .key_diff = xfs_bmbt_key_diff,
2363 2224
2364#ifdef XFS_BTREE_TRACE 2225#ifdef XFS_BTREE_TRACE
2365 .trace_enter = xfs_bmbt_trace_enter, 2226 .trace_enter = xfs_bmbt_trace_enter,
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-10 22:10:47 -0500