aboutsummaryrefslogtreecommitdiffstats
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
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
-rw-r--r--fs/xfs/xfs_alloc.c48
-rw-r--r--fs/xfs/xfs_alloc_btree.c312
-rw-r--r--fs/xfs/xfs_alloc_btree.h20
-rw-r--r--fs/xfs/xfs_bmap.c29
-rw-r--r--fs/xfs/xfs_bmap_btree.c197
-rw-r--r--fs/xfs/xfs_bmap_btree.h4
-rw-r--r--fs/xfs/xfs_btree.c219
-rw-r--r--fs/xfs/xfs_btree.h11
-rw-r--r--fs/xfs/xfs_ialloc.c53
-rw-r--r--fs/xfs/xfs_ialloc.h15
-rw-r--r--fs/xfs/xfs_ialloc_btree.c294
-rw-r--r--fs/xfs/xfs_ialloc_btree.h20
12 files changed, 487 insertions, 735 deletions
diff --git a/fs/xfs/xfs_alloc.c b/fs/xfs/xfs_alloc.c
index 7ca6903e2354..6bda0ae26c2a 100644
--- a/fs/xfs/xfs_alloc.c
+++ b/fs/xfs/xfs_alloc.c
@@ -90,6 +90,54 @@ STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
90 */ 90 */
91 91
92/* 92/*
93 * Lookup the record equal to [bno, len] in the btree given by cur.
94 */
95STATIC int /* error */
96xfs_alloc_lookup_eq(
97 struct xfs_btree_cur *cur, /* btree cursor */
98 xfs_agblock_t bno, /* starting block of extent */
99 xfs_extlen_t len, /* length of extent */
100 int *stat) /* success/failure */
101{
102 cur->bc_rec.a.ar_startblock = bno;
103 cur->bc_rec.a.ar_blockcount = len;
104 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
105}
106
107/*
108 * Lookup the first record greater than or equal to [bno, len]
109 * in the btree given by cur.
110 */
111STATIC int /* error */
112xfs_alloc_lookup_ge(
113 struct xfs_btree_cur *cur, /* btree cursor */
114 xfs_agblock_t bno, /* starting block of extent */
115 xfs_extlen_t len, /* length of extent */
116 int *stat) /* success/failure */
117{
118 cur->bc_rec.a.ar_startblock = bno;
119 cur->bc_rec.a.ar_blockcount = len;
120 return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
121}
122
123/*
124 * Lookup the first record less than or equal to [bno, len]
125 * in the btree given by cur.
126 */
127STATIC int /* error */
128xfs_alloc_lookup_le(
129 struct xfs_btree_cur *cur, /* btree cursor */
130 xfs_agblock_t bno, /* starting block of extent */
131 xfs_extlen_t len, /* length of extent */
132 int *stat) /* success/failure */
133{
134 cur->bc_rec.a.ar_startblock = bno;
135 cur->bc_rec.a.ar_blockcount = len;
136 return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
137}
138
139
140/*
93 * Compute aligned version of the found extent. 141 * Compute aligned version of the found extent.
94 * Takes alignment and min length into account. 142 * Takes alignment and min length into account.
95 */ 143 */
diff --git a/fs/xfs/xfs_alloc_btree.c b/fs/xfs/xfs_alloc_btree.c
index 6b45481ad5b0..b81fbf1216ed 100644
--- a/fs/xfs/xfs_alloc_btree.c
+++ b/fs/xfs/xfs_alloc_btree.c
@@ -938,223 +938,6 @@ xfs_alloc_log_recs(
938} 938}
939 939
940/* 940/*
941 * Lookup the record. The cursor is made to point to it, based on dir.
942 * Return 0 if can't find any such record, 1 for success.
943 */
944STATIC int /* error */
945xfs_alloc_lookup(
946 xfs_btree_cur_t *cur, /* btree cursor */
947 xfs_lookup_t dir, /* <=, ==, or >= */
948 int *stat) /* success/failure */
949{
950 xfs_agblock_t agbno; /* a.g. relative btree block number */
951 xfs_agnumber_t agno; /* allocation group number */
952 xfs_alloc_block_t *block=NULL; /* current btree block */
953 int diff; /* difference for the current key */
954 int error; /* error return value */
955 int keyno=0; /* current key number */
956 int level; /* level in the btree */
957 xfs_mount_t *mp; /* file system mount point */
958
959 XFS_STATS_INC(xs_abt_lookup);
960 /*
961 * Get the allocation group header, and the root block number.
962 */
963 mp = cur->bc_mp;
964
965 {
966 xfs_agf_t *agf; /* a.g. freespace header */
967
968 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
969 agno = be32_to_cpu(agf->agf_seqno);
970 agbno = be32_to_cpu(agf->agf_roots[cur->bc_btnum]);
971 }
972 /*
973 * Iterate over each level in the btree, starting at the root.
974 * For each level above the leaves, find the key we need, based
975 * on the lookup record, then follow the corresponding block
976 * pointer down to the next level.
977 */
978 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
979 xfs_buf_t *bp; /* buffer pointer for btree block */
980 xfs_daddr_t d; /* disk address of btree block */
981
982 /*
983 * Get the disk address we're looking for.
984 */
985 d = XFS_AGB_TO_DADDR(mp, agno, agbno);
986 /*
987 * If the old buffer at this level is for a different block,
988 * throw it away, otherwise just use it.
989 */
990 bp = cur->bc_bufs[level];
991 if (bp && XFS_BUF_ADDR(bp) != d)
992 bp = NULL;
993 if (!bp) {
994 /*
995 * Need to get a new buffer. Read it, then
996 * set it in the cursor, releasing the old one.
997 */
998 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp, agno,
999 agbno, 0, &bp, XFS_ALLOC_BTREE_REF)))
1000 return error;
1001 xfs_btree_setbuf(cur, level, bp);
1002 /*
1003 * Point to the btree block, now that we have the buffer
1004 */
1005 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1006 if ((error = xfs_btree_check_sblock(cur, block, level,
1007 bp)))
1008 return error;
1009 } else
1010 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1011 /*
1012 * If we already had a key match at a higher level, we know
1013 * we need to use the first entry in this block.
1014 */
1015 if (diff == 0)
1016 keyno = 1;
1017 /*
1018 * Otherwise we need to search this block. Do a binary search.
1019 */
1020 else {
1021 int high; /* high entry number */
1022 xfs_alloc_key_t *kkbase=NULL;/* base of keys in block */
1023 xfs_alloc_rec_t *krbase=NULL;/* base of records in block */
1024 int low; /* low entry number */
1025
1026 /*
1027 * Get a pointer to keys or records.
1028 */
1029 if (level > 0)
1030 kkbase = XFS_ALLOC_KEY_ADDR(block, 1, cur);
1031 else
1032 krbase = XFS_ALLOC_REC_ADDR(block, 1, cur);
1033 /*
1034 * Set low and high entry numbers, 1-based.
1035 */
1036 low = 1;
1037 if (!(high = be16_to_cpu(block->bb_numrecs))) {
1038 /*
1039 * If the block is empty, the tree must
1040 * be an empty leaf.
1041 */
1042 ASSERT(level == 0 && cur->bc_nlevels == 1);
1043 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1044 *stat = 0;
1045 return 0;
1046 }
1047 /*
1048 * Binary search the block.
1049 */
1050 while (low <= high) {
1051 xfs_extlen_t blockcount; /* key value */
1052 xfs_agblock_t startblock; /* key value */
1053
1054 XFS_STATS_INC(xs_abt_compare);
1055 /*
1056 * keyno is average of low and high.
1057 */
1058 keyno = (low + high) >> 1;
1059 /*
1060 * Get startblock & blockcount.
1061 */
1062 if (level > 0) {
1063 xfs_alloc_key_t *kkp;
1064
1065 kkp = kkbase + keyno - 1;
1066 startblock = be32_to_cpu(kkp->ar_startblock);
1067 blockcount = be32_to_cpu(kkp->ar_blockcount);
1068 } else {
1069 xfs_alloc_rec_t *krp;
1070
1071 krp = krbase + keyno - 1;
1072 startblock = be32_to_cpu(krp->ar_startblock);
1073 blockcount = be32_to_cpu(krp->ar_blockcount);
1074 }
1075 /*
1076 * Compute difference to get next direction.
1077 */
1078 if (cur->bc_btnum == XFS_BTNUM_BNO)
1079 diff = (int)startblock -
1080 (int)cur->bc_rec.a.ar_startblock;
1081 else if (!(diff = (int)blockcount -
1082 (int)cur->bc_rec.a.ar_blockcount))
1083 diff = (int)startblock -
1084 (int)cur->bc_rec.a.ar_startblock;
1085 /*
1086 * Less than, move right.
1087 */
1088 if (diff < 0)
1089 low = keyno + 1;
1090 /*
1091 * Greater than, move left.
1092 */
1093 else if (diff > 0)
1094 high = keyno - 1;
1095 /*
1096 * Equal, we're done.
1097 */
1098 else
1099 break;
1100 }
1101 }
1102 /*
1103 * If there are more levels, set up for the next level
1104 * by getting the block number and filling in the cursor.
1105 */
1106 if (level > 0) {
1107 /*
1108 * If we moved left, need the previous key number,
1109 * unless there isn't one.
1110 */
1111 if (diff > 0 && --keyno < 1)
1112 keyno = 1;
1113 agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, keyno, cur));
1114#ifdef DEBUG
1115 if ((error = xfs_btree_check_sptr(cur, agbno, level)))
1116 return error;
1117#endif
1118 cur->bc_ptrs[level] = keyno;
1119 }
1120 }
1121 /*
1122 * Done with the search.
1123 * See if we need to adjust the results.
1124 */
1125 if (dir != XFS_LOOKUP_LE && diff < 0) {
1126 keyno++;
1127 /*
1128 * If ge search and we went off the end of the block, but it's
1129 * not the last block, we're in the wrong block.
1130 */
1131 if (dir == XFS_LOOKUP_GE &&
1132 keyno > be16_to_cpu(block->bb_numrecs) &&
1133 be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) {
1134 int i;
1135
1136 cur->bc_ptrs[0] = keyno;
1137 if ((error = xfs_btree_increment(cur, 0, &i)))
1138 return error;
1139 XFS_WANT_CORRUPTED_RETURN(i == 1);
1140 *stat = 1;
1141 return 0;
1142 }
1143 }
1144 else if (dir == XFS_LOOKUP_LE && diff > 0)
1145 keyno--;
1146 cur->bc_ptrs[0] = keyno;
1147 /*
1148 * Return if we succeeded or not.
1149 */
1150 if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs))
1151 *stat = 0;
1152 else
1153 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
1154 return 0;
1155}
1156
1157/*
1158 * Move 1 record left from cur/level if possible. 941 * Move 1 record left from cur/level if possible.
1159 * Update cur to reflect the new path. 942 * Update cur to reflect the new path.
1160 */ 943 */
@@ -1919,53 +1702,6 @@ xfs_alloc_insert(
1919} 1702}
1920 1703
1921/* 1704/*
1922 * Lookup the record equal to [bno, len] in the btree given by cur.
1923 */
1924int /* error */
1925xfs_alloc_lookup_eq(
1926 xfs_btree_cur_t *cur, /* btree cursor */
1927 xfs_agblock_t bno, /* starting block of extent */
1928 xfs_extlen_t len, /* length of extent */
1929 int *stat) /* success/failure */
1930{
1931 cur->bc_rec.a.ar_startblock = bno;
1932 cur->bc_rec.a.ar_blockcount = len;
1933 return xfs_alloc_lookup(cur, XFS_LOOKUP_EQ, stat);
1934}
1935
1936/*
1937 * Lookup the first record greater than or equal to [bno, len]
1938 * in the btree given by cur.
1939 */
1940int /* error */
1941xfs_alloc_lookup_ge(
1942 xfs_btree_cur_t *cur, /* btree cursor */
1943 xfs_agblock_t bno, /* starting block of extent */
1944 xfs_extlen_t len, /* length of extent */
1945 int *stat) /* success/failure */
1946{
1947 cur->bc_rec.a.ar_startblock = bno;
1948 cur->bc_rec.a.ar_blockcount = len;
1949 return xfs_alloc_lookup(cur, XFS_LOOKUP_GE, stat);
1950}
1951
1952/*
1953 * Lookup the first record less than or equal to [bno, len]
1954 * in the btree given by cur.
1955 */
1956int /* error */
1957xfs_alloc_lookup_le(
1958 xfs_btree_cur_t *cur, /* btree cursor */
1959 xfs_agblock_t bno, /* starting block of extent */
1960 xfs_extlen_t len, /* length of extent */
1961 int *stat) /* success/failure */
1962{
1963 cur->bc_rec.a.ar_startblock = bno;
1964 cur->bc_rec.a.ar_blockcount = len;
1965 return xfs_alloc_lookup(cur, XFS_LOOKUP_LE, stat);
1966}
1967
1968/*
1969 * Update the record referred to by cur, to the value given by [bno, len]. 1705 * Update the record referred to by cur, to the value given by [bno, len].
1970 * This either works (return 0) or gets an EFSCORRUPTED error. 1706 * This either works (return 0) or gets an EFSCORRUPTED error.
1971 */ 1707 */
@@ -2052,6 +1788,51 @@ xfs_allocbt_get_maxrecs(
2052 return cur->bc_mp->m_alloc_mxr[level != 0]; 1788 return cur->bc_mp->m_alloc_mxr[level != 0];
2053} 1789}
2054 1790
1791STATIC void
1792xfs_allocbt_init_key_from_rec(
1793 union xfs_btree_key *key,
1794 union xfs_btree_rec *rec)
1795{
1796 ASSERT(rec->alloc.ar_startblock != 0);
1797
1798 key->alloc.ar_startblock = rec->alloc.ar_startblock;
1799 key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
1800}
1801
1802STATIC void
1803xfs_allocbt_init_ptr_from_cur(
1804 struct xfs_btree_cur *cur,
1805 union xfs_btree_ptr *ptr)
1806{
1807 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
1808
1809 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
1810 ASSERT(agf->agf_roots[cur->bc_btnum] != 0);
1811
1812 ptr->s = agf->agf_roots[cur->bc_btnum];
1813}
1814
1815STATIC __int64_t
1816xfs_allocbt_key_diff(
1817 struct xfs_btree_cur *cur,
1818 union xfs_btree_key *key)
1819{
1820 xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a;
1821 xfs_alloc_key_t *kp = &key->alloc;
1822 __int64_t diff;
1823
1824 if (cur->bc_btnum == XFS_BTNUM_BNO) {
1825 return (__int64_t)be32_to_cpu(kp->ar_startblock) -
1826 rec->ar_startblock;
1827 }
1828
1829 diff = (__int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount;
1830 if (diff)
1831 return diff;
1832
1833 return (__int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
1834}
1835
2055#ifdef XFS_BTREE_TRACE 1836#ifdef XFS_BTREE_TRACE
2056ktrace_t *xfs_allocbt_trace_buf; 1837ktrace_t *xfs_allocbt_trace_buf;
2057 1838
@@ -2124,6 +1905,9 @@ static const struct xfs_btree_ops xfs_allocbt_ops = {
2124 1905
2125 .dup_cursor = xfs_allocbt_dup_cursor, 1906 .dup_cursor = xfs_allocbt_dup_cursor,
2126 .get_maxrecs = xfs_allocbt_get_maxrecs, 1907 .get_maxrecs = xfs_allocbt_get_maxrecs,
1908 .init_key_from_rec = xfs_allocbt_init_key_from_rec,
1909 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur,
1910 .key_diff = xfs_allocbt_key_diff,
2127 1911
2128#ifdef XFS_BTREE_TRACE 1912#ifdef XFS_BTREE_TRACE
2129 .trace_enter = xfs_allocbt_trace_enter, 1913 .trace_enter = xfs_allocbt_trace_enter,
diff --git a/fs/xfs/xfs_alloc_btree.h b/fs/xfs/xfs_alloc_btree.h
index b59d7fc78fe6..aa110ff4feb1 100644
--- a/fs/xfs/xfs_alloc_btree.h
+++ b/fs/xfs/xfs_alloc_btree.h
@@ -114,26 +114,6 @@ extern int xfs_alloc_get_rec(struct xfs_btree_cur *cur, xfs_agblock_t *bno,
114extern int xfs_alloc_insert(struct xfs_btree_cur *cur, int *stat); 114extern int xfs_alloc_insert(struct xfs_btree_cur *cur, int *stat);
115 115
116/* 116/*
117 * Lookup the record equal to [bno, len] in the btree given by cur.
118 */
119extern int xfs_alloc_lookup_eq(struct xfs_btree_cur *cur, xfs_agblock_t bno,
120 xfs_extlen_t len, int *stat);
121
122/*
123 * Lookup the first record greater than or equal to [bno, len]
124 * in the btree given by cur.
125 */
126extern int xfs_alloc_lookup_ge(struct xfs_btree_cur *cur, xfs_agblock_t bno,
127 xfs_extlen_t len, int *stat);
128
129/*
130 * Lookup the first record less than or equal to [bno, len]
131 * in the btree given by cur.
132 */
133extern int xfs_alloc_lookup_le(struct xfs_btree_cur *cur, xfs_agblock_t bno,
134 xfs_extlen_t len, int *stat);
135
136/*
137 * Update the record referred to by cur, to the value given by [bno, len]. 117 * Update the record referred to by cur, to the value given by [bno, len].
138 * This either works (return 0) or gets an EFSCORRUPTED error. 118 * This either works (return 0) or gets an EFSCORRUPTED error.
139 */ 119 */
diff --git a/fs/xfs/xfs_bmap.c b/fs/xfs/xfs_bmap.c
index bdbab54948fc..1296b4102e97 100644
--- a/fs/xfs/xfs_bmap.c
+++ b/fs/xfs/xfs_bmap.c
@@ -402,6 +402,35 @@ xfs_bmap_disk_count_leaves(
402 * Bmap internal routines. 402 * Bmap internal routines.
403 */ 403 */
404 404
405STATIC int /* error */
406xfs_bmbt_lookup_eq(
407 struct xfs_btree_cur *cur,
408 xfs_fileoff_t off,
409 xfs_fsblock_t bno,
410 xfs_filblks_t len,
411 int *stat) /* success/failure */
412{
413 cur->bc_rec.b.br_startoff = off;
414 cur->bc_rec.b.br_startblock = bno;
415 cur->bc_rec.b.br_blockcount = len;
416 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
417}
418
419STATIC int /* error */
420xfs_bmbt_lookup_ge(
421 struct xfs_btree_cur *cur,
422 xfs_fileoff_t off,
423 xfs_fsblock_t bno,
424 xfs_filblks_t len,
425 int *stat) /* success/failure */
426{
427 cur->bc_rec.b.br_startoff = off;
428 cur->bc_rec.b.br_startblock = bno;
429 cur->bc_rec.b.br_blockcount = len;
430 return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
431}
432
433
405/* 434/*
406 * Called from xfs_bmap_add_attrfork to handle btree format files. 435 * Called from xfs_bmap_add_attrfork to handle btree format files.
407 */ 436 */
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,
diff --git a/fs/xfs/xfs_bmap_btree.h b/fs/xfs/xfs_bmap_btree.h
index 1e0f1d105059..d04198cdc4b3 100644
--- a/fs/xfs/xfs_bmap_btree.h
+++ b/fs/xfs/xfs_bmap_btree.h
@@ -254,10 +254,6 @@ extern int xfs_bmbt_insert(struct xfs_btree_cur *, int *);
254extern void xfs_bmbt_log_block(struct xfs_btree_cur *, struct xfs_buf *, int); 254extern void xfs_bmbt_log_block(struct xfs_btree_cur *, struct xfs_buf *, int);
255extern void xfs_bmbt_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int, 255extern void xfs_bmbt_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int,
256 int); 256 int);
257extern int xfs_bmbt_lookup_eq(struct xfs_btree_cur *, xfs_fileoff_t,
258 xfs_fsblock_t, xfs_filblks_t, int *);
259extern int xfs_bmbt_lookup_ge(struct xfs_btree_cur *, xfs_fileoff_t,
260 xfs_fsblock_t, xfs_filblks_t, int *);
261 257
262/* 258/*
263 * Give the bmap btree a new root block. Copy the old broot contents 259 * Give the bmap btree a new root block. Copy the old broot contents
diff --git a/fs/xfs/xfs_btree.c b/fs/xfs/xfs_btree.c
index 3d561f8f78d0..41912a01bec7 100644
--- a/fs/xfs/xfs_btree.c
+++ b/fs/xfs/xfs_btree.c
@@ -1270,3 +1270,222 @@ error0:
1270 return error; 1270 return error;
1271} 1271}
1272 1272
1273
1274STATIC int
1275xfs_btree_lookup_get_block(
1276 struct xfs_btree_cur *cur, /* btree cursor */
1277 int level, /* level in the btree */
1278 union xfs_btree_ptr *pp, /* ptr to btree block */
1279 struct xfs_btree_block **blkp) /* return btree block */
1280{
1281 struct xfs_buf *bp; /* buffer pointer for btree block */
1282 int error = 0;
1283
1284 /* special case the root block if in an inode */
1285 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1286 (level == cur->bc_nlevels - 1)) {
1287 *blkp = xfs_btree_get_iroot(cur);
1288 return 0;
1289 }
1290
1291 /*
1292 * If the old buffer at this level for the disk address we are
1293 * looking for re-use it.
1294 *
1295 * Otherwise throw it away and get a new one.
1296 */
1297 bp = cur->bc_bufs[level];
1298 if (bp && XFS_BUF_ADDR(bp) == xfs_btree_ptr_to_daddr(cur, pp)) {
1299 *blkp = XFS_BUF_TO_BLOCK(bp);
1300 return 0;
1301 }
1302
1303 error = xfs_btree_read_buf_block(cur, pp, level, 0, blkp, &bp);
1304 if (error)
1305 return error;
1306
1307 xfs_btree_setbuf(cur, level, bp);
1308 return 0;
1309}
1310
1311/*
1312 * Get current search key. For level 0 we don't actually have a key
1313 * structure so we make one up from the record. For all other levels
1314 * we just return the right key.
1315 */
1316STATIC union xfs_btree_key *
1317xfs_lookup_get_search_key(
1318 struct xfs_btree_cur *cur,
1319 int level,
1320 int keyno,
1321 struct xfs_btree_block *block,
1322 union xfs_btree_key *kp)
1323{
1324 if (level == 0) {
1325 cur->bc_ops->init_key_from_rec(kp,
1326 xfs_btree_rec_addr(cur, keyno, block));
1327 return kp;
1328 }
1329
1330 return xfs_btree_key_addr(cur, keyno, block);
1331}
1332
1333/*
1334 * Lookup the record. The cursor is made to point to it, based on dir.
1335 * Return 0 if can't find any such record, 1 for success.
1336 */
1337int /* error */
1338xfs_btree_lookup(
1339 struct xfs_btree_cur *cur, /* btree cursor */
1340 xfs_lookup_t dir, /* <=, ==, or >= */
1341 int *stat) /* success/failure */
1342{
1343 struct xfs_btree_block *block; /* current btree block */
1344 __int64_t diff; /* difference for the current key */
1345 int error; /* error return value */
1346 int keyno; /* current key number */
1347 int level; /* level in the btree */
1348 union xfs_btree_ptr *pp; /* ptr to btree block */
1349 union xfs_btree_ptr ptr; /* ptr to btree block */
1350
1351 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1352 XFS_BTREE_TRACE_ARGI(cur, dir);
1353
1354 XFS_BTREE_STATS_INC(cur, lookup);
1355
1356 block = NULL;
1357 keyno = 0;
1358
1359 /* initialise start pointer from cursor */
1360 cur->bc_ops->init_ptr_from_cur(cur, &ptr);
1361 pp = &ptr;
1362
1363 /*
1364 * Iterate over each level in the btree, starting at the root.
1365 * For each level above the leaves, find the key we need, based
1366 * on the lookup record, then follow the corresponding block
1367 * pointer down to the next level.
1368 */
1369 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1370 /* Get the block we need to do the lookup on. */
1371 error = xfs_btree_lookup_get_block(cur, level, pp, &block);
1372 if (error)
1373 goto error0;
1374
1375 if (diff == 0) {
1376 /*
1377 * If we already had a key match at a higher level, we
1378 * know we need to use the first entry in this block.
1379 */
1380 keyno = 1;
1381 } else {
1382 /* Otherwise search this block. Do a binary search. */
1383
1384 int high; /* high entry number */
1385 int low; /* low entry number */
1386
1387 /* Set low and high entry numbers, 1-based. */
1388 low = 1;
1389 high = xfs_btree_get_numrecs(block);
1390 if (!high) {
1391 /* Block is empty, must be an empty leaf. */
1392 ASSERT(level == 0 && cur->bc_nlevels == 1);
1393
1394 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1395 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1396 *stat = 0;
1397 return 0;
1398 }
1399
1400 /* Binary search the block. */
1401 while (low <= high) {
1402 union xfs_btree_key key;
1403 union xfs_btree_key *kp;
1404
1405 XFS_BTREE_STATS_INC(cur, compare);
1406
1407 /* keyno is average of low and high. */
1408 keyno = (low + high) >> 1;
1409
1410 /* Get current search key */
1411 kp = xfs_lookup_get_search_key(cur, level,
1412 keyno, block, &key);
1413
1414 /*
1415 * Compute difference to get next direction:
1416 * - less than, move right
1417 * - greater than, move left
1418 * - equal, we're done
1419 */
1420 diff = cur->bc_ops->key_diff(cur, kp);
1421 if (diff < 0)
1422 low = keyno + 1;
1423 else if (diff > 0)
1424 high = keyno - 1;
1425 else
1426 break;
1427 }
1428 }
1429
1430 /*
1431 * If there are more levels, set up for the next level
1432 * by getting the block number and filling in the cursor.
1433 */
1434 if (level > 0) {
1435 /*
1436 * If we moved left, need the previous key number,
1437 * unless there isn't one.
1438 */
1439 if (diff > 0 && --keyno < 1)
1440 keyno = 1;
1441 pp = xfs_btree_ptr_addr(cur, keyno, block);
1442
1443#ifdef DEBUG
1444 error = xfs_btree_check_ptr(cur, pp, 0, level);
1445 if (error)
1446 goto error0;
1447#endif
1448 cur->bc_ptrs[level] = keyno;
1449 }
1450 }
1451
1452 /* Done with the search. See if we need to adjust the results. */
1453 if (dir != XFS_LOOKUP_LE && diff < 0) {
1454 keyno++;
1455 /*
1456 * If ge search and we went off the end of the block, but it's
1457 * not the last block, we're in the wrong block.
1458 */
1459 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1460 if (dir == XFS_LOOKUP_GE &&
1461 keyno > xfs_btree_get_numrecs(block) &&
1462 !xfs_btree_ptr_is_null(cur, &ptr)) {
1463 int i;
1464
1465 cur->bc_ptrs[0] = keyno;
1466 error = xfs_btree_increment(cur, 0, &i);
1467 if (error)
1468 goto error0;
1469 XFS_WANT_CORRUPTED_RETURN(i == 1);
1470 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1471 *stat = 1;
1472 return 0;
1473 }
1474 } else if (dir == XFS_LOOKUP_LE && diff > 0)
1475 keyno--;
1476 cur->bc_ptrs[0] = keyno;
1477
1478 /* Return if we succeeded or not. */
1479 if (keyno == 0 || keyno > xfs_btree_get_numrecs(block))
1480 *stat = 0;
1481 else if (dir != XFS_LOOKUP_EQ || diff == 0)
1482 *stat = 1;
1483 else
1484 *stat = 0;
1485 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1486 return 0;
1487
1488error0:
1489 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1490 return error;
1491}
diff --git a/fs/xfs/xfs_btree.h b/fs/xfs/xfs_btree.h
index 52b2da6ab32e..c151175a5fd0 100644
--- a/fs/xfs/xfs_btree.h
+++ b/fs/xfs/xfs_btree.h
@@ -190,6 +190,16 @@ struct xfs_btree_ops {
190 /* records in block/level */ 190 /* records in block/level */
191 int (*get_maxrecs)(struct xfs_btree_cur *cur, int level); 191 int (*get_maxrecs)(struct xfs_btree_cur *cur, int level);
192 192
193 /* init values of btree structures */
194 void (*init_key_from_rec)(union xfs_btree_key *key,
195 union xfs_btree_rec *rec);
196 void (*init_ptr_from_cur)(struct xfs_btree_cur *cur,
197 union xfs_btree_ptr *ptr);
198
199 /* difference between key value and cursor value */
200 __int64_t (*key_diff)(struct xfs_btree_cur *cur,
201 union xfs_btree_key *key);
202
193 /* btree tracing */ 203 /* btree tracing */
194#ifdef XFS_BTREE_TRACE 204#ifdef XFS_BTREE_TRACE
195 void (*trace_enter)(struct xfs_btree_cur *, const char *, 205 void (*trace_enter)(struct xfs_btree_cur *, const char *,
@@ -507,6 +517,7 @@ xfs_btree_setbuf(
507 */ 517 */
508int xfs_btree_increment(struct xfs_btree_cur *, int, int *); 518int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
509int xfs_btree_decrement(struct xfs_btree_cur *, int, int *); 519int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
520int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
510 521
511/* 522/*
512 * Helpers. 523 * Helpers.
diff --git a/fs/xfs/xfs_ialloc.c b/fs/xfs/xfs_ialloc.c
index d36b42bf3ff6..bbf537f64c41 100644
--- a/fs/xfs/xfs_ialloc.c
+++ b/fs/xfs/xfs_ialloc.c
@@ -119,6 +119,59 @@ xfs_ialloc_cluster_alignment(
119} 119}
120 120
121/* 121/*
122 * Lookup the record equal to ino in the btree given by cur.
123 */
124STATIC int /* error */
125xfs_inobt_lookup_eq(
126 struct xfs_btree_cur *cur, /* btree cursor */
127 xfs_agino_t ino, /* starting inode of chunk */
128 __int32_t fcnt, /* free inode count */
129 xfs_inofree_t free, /* free inode mask */
130 int *stat) /* success/failure */
131{
132 cur->bc_rec.i.ir_startino = ino;
133 cur->bc_rec.i.ir_freecount = fcnt;
134 cur->bc_rec.i.ir_free = free;
135 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
136}
137
138/*
139 * Lookup the first record greater than or equal to ino
140 * in the btree given by cur.
141 */
142int /* error */
143xfs_inobt_lookup_ge(
144 struct xfs_btree_cur *cur, /* btree cursor */
145 xfs_agino_t ino, /* starting inode of chunk */
146 __int32_t fcnt, /* free inode count */
147 xfs_inofree_t free, /* free inode mask */
148 int *stat) /* success/failure */
149{
150 cur->bc_rec.i.ir_startino = ino;
151 cur->bc_rec.i.ir_freecount = fcnt;
152 cur->bc_rec.i.ir_free = free;
153 return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
154}
155
156/*
157 * Lookup the first record less than or equal to ino
158 * in the btree given by cur.
159 */
160int /* error */
161xfs_inobt_lookup_le(
162 struct xfs_btree_cur *cur, /* btree cursor */
163 xfs_agino_t ino, /* starting inode of chunk */
164 __int32_t fcnt, /* free inode count */
165 xfs_inofree_t free, /* free inode mask */
166 int *stat) /* success/failure */
167{
168 cur->bc_rec.i.ir_startino = ino;
169 cur->bc_rec.i.ir_freecount = fcnt;
170 cur->bc_rec.i.ir_free = free;
171 return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
172}
173
174/*
122 * Allocate new inodes in the allocation group specified by agbp. 175 * Allocate new inodes in the allocation group specified by agbp.
123 * Return 0 for success, else error code. 176 * Return 0 for success, else error code.
124 */ 177 */
diff --git a/fs/xfs/xfs_ialloc.h b/fs/xfs/xfs_ialloc.h
index 4e30ec1d13bc..4026578bc264 100644
--- a/fs/xfs/xfs_ialloc.h
+++ b/fs/xfs/xfs_ialloc.h
@@ -154,6 +154,21 @@ xfs_ialloc_pagi_init(
154 struct xfs_trans *tp, /* transaction pointer */ 154 struct xfs_trans *tp, /* transaction pointer */
155 xfs_agnumber_t agno); /* allocation group number */ 155 xfs_agnumber_t agno); /* allocation group number */
156 156
157/*
158 * Lookup the first record greater than or equal to ino
159 * in the btree given by cur.
160 */
161int xfs_inobt_lookup_ge(struct xfs_btree_cur *cur, xfs_agino_t ino,
162 __int32_t fcnt, xfs_inofree_t free, int *stat);
163
164/*
165 * Lookup the first record less than or equal to ino
166 * in the btree given by cur.
167 */
168int xfs_inobt_lookup_le(struct xfs_btree_cur *cur, xfs_agino_t ino,
169 __int32_t fcnt, xfs_inofree_t free, int *stat);
170
171
157#endif /* __KERNEL__ */ 172#endif /* __KERNEL__ */
158 173
159#endif /* __XFS_IALLOC_H__ */ 174#endif /* __XFS_IALLOC_H__ */
diff --git a/fs/xfs/xfs_ialloc_btree.c b/fs/xfs/xfs_ialloc_btree.c
index 9099a32f9972..161c3b2e245f 100644
--- a/fs/xfs/xfs_ialloc_btree.c
+++ b/fs/xfs/xfs_ialloc_btree.c
@@ -829,212 +829,6 @@ xfs_inobt_log_recs(
829} 829}
830 830
831/* 831/*
832 * Lookup the record. The cursor is made to point to it, based on dir.
833 * Return 0 if can't find any such record, 1 for success.
834 */
835STATIC int /* error */
836xfs_inobt_lookup(
837 xfs_btree_cur_t *cur, /* btree cursor */
838 xfs_lookup_t dir, /* <=, ==, or >= */
839 int *stat) /* success/failure */
840{
841 xfs_agblock_t agbno; /* a.g. relative btree block number */
842 xfs_agnumber_t agno; /* allocation group number */
843 xfs_inobt_block_t *block=NULL; /* current btree block */
844 __int64_t diff; /* difference for the current key */
845 int error; /* error return value */
846 int keyno=0; /* current key number */
847 int level; /* level in the btree */
848 xfs_mount_t *mp; /* file system mount point */
849
850 /*
851 * Get the allocation group header, and the root block number.
852 */
853 mp = cur->bc_mp;
854 {
855 xfs_agi_t *agi; /* a.g. inode header */
856
857 agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
858 agno = be32_to_cpu(agi->agi_seqno);
859 agbno = be32_to_cpu(agi->agi_root);
860 }
861 /*
862 * Iterate over each level in the btree, starting at the root.
863 * For each level above the leaves, find the key we need, based
864 * on the lookup record, then follow the corresponding block
865 * pointer down to the next level.
866 */
867 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
868 xfs_buf_t *bp; /* buffer pointer for btree block */
869 xfs_daddr_t d; /* disk address of btree block */
870
871 /*
872 * Get the disk address we're looking for.
873 */
874 d = XFS_AGB_TO_DADDR(mp, agno, agbno);
875 /*
876 * If the old buffer at this level is for a different block,
877 * throw it away, otherwise just use it.
878 */
879 bp = cur->bc_bufs[level];
880 if (bp && XFS_BUF_ADDR(bp) != d)
881 bp = NULL;
882 if (!bp) {
883 /*
884 * Need to get a new buffer. Read it, then
885 * set it in the cursor, releasing the old one.
886 */
887 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
888 agno, agbno, 0, &bp, XFS_INO_BTREE_REF)))
889 return error;
890 xfs_btree_setbuf(cur, level, bp);
891 /*
892 * Point to the btree block, now that we have the buffer
893 */
894 block = XFS_BUF_TO_INOBT_BLOCK(bp);
895 if ((error = xfs_btree_check_sblock(cur, block, level,
896 bp)))
897 return error;
898 } else
899 block = XFS_BUF_TO_INOBT_BLOCK(bp);
900 /*
901 * If we already had a key match at a higher level, we know
902 * we need to use the first entry in this block.
903 */
904 if (diff == 0)
905 keyno = 1;
906 /*
907 * Otherwise we need to search this block. Do a binary search.
908 */
909 else {
910 int high; /* high entry number */
911 xfs_inobt_key_t *kkbase=NULL;/* base of keys in block */
912 xfs_inobt_rec_t *krbase=NULL;/* base of records in block */
913 int low; /* low entry number */
914
915 /*
916 * Get a pointer to keys or records.
917 */
918 if (level > 0)
919 kkbase = XFS_INOBT_KEY_ADDR(block, 1, cur);
920 else
921 krbase = XFS_INOBT_REC_ADDR(block, 1, cur);
922 /*
923 * Set low and high entry numbers, 1-based.
924 */
925 low = 1;
926 if (!(high = be16_to_cpu(block->bb_numrecs))) {
927 /*
928 * If the block is empty, the tree must
929 * be an empty leaf.
930 */
931 ASSERT(level == 0 && cur->bc_nlevels == 1);
932 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
933 *stat = 0;
934 return 0;
935 }
936 /*
937 * Binary search the block.
938 */
939 while (low <= high) {
940 xfs_agino_t startino; /* key value */
941
942 /*
943 * keyno is average of low and high.
944 */
945 keyno = (low + high) >> 1;
946 /*
947 * Get startino.
948 */
949 if (level > 0) {
950 xfs_inobt_key_t *kkp;
951
952 kkp = kkbase + keyno - 1;
953 startino = be32_to_cpu(kkp->ir_startino);
954 } else {
955 xfs_inobt_rec_t *krp;
956
957 krp = krbase + keyno - 1;
958 startino = be32_to_cpu(krp->ir_startino);
959 }
960 /*
961 * Compute difference to get next direction.
962 */
963 diff = (__int64_t)
964 startino - cur->bc_rec.i.ir_startino;
965 /*
966 * Less than, move right.
967 */
968 if (diff < 0)
969 low = keyno + 1;
970 /*
971 * Greater than, move left.
972 */
973 else if (diff > 0)
974 high = keyno - 1;
975 /*
976 * Equal, we're done.
977 */
978 else
979 break;
980 }
981 }
982 /*
983 * If there are more levels, set up for the next level
984 * by getting the block number and filling in the cursor.
985 */
986 if (level > 0) {
987 /*
988 * If we moved left, need the previous key number,
989 * unless there isn't one.
990 */
991 if (diff > 0 && --keyno < 1)
992 keyno = 1;
993 agbno = be32_to_cpu(*XFS_INOBT_PTR_ADDR(block, keyno, cur));
994#ifdef DEBUG
995 if ((error = xfs_btree_check_sptr(cur, agbno, level)))
996 return error;
997#endif
998 cur->bc_ptrs[level] = keyno;
999 }
1000 }
1001 /*
1002 * Done with the search.
1003 * See if we need to adjust the results.
1004 */
1005 if (dir != XFS_LOOKUP_LE && diff < 0) {
1006 keyno++;
1007 /*
1008 * If ge search and we went off the end of the block, but it's
1009 * not the last block, we're in the wrong block.
1010 */
1011 if (dir == XFS_LOOKUP_GE &&
1012 keyno > be16_to_cpu(block->bb_numrecs) &&
1013 be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) {
1014 int i;
1015
1016 cur->bc_ptrs[0] = keyno;
1017 if ((error = xfs_btree_increment(cur, 0, &i)))
1018 return error;
1019 ASSERT(i == 1);
1020 *stat = 1;
1021 return 0;
1022 }
1023 }
1024 else if (dir == XFS_LOOKUP_LE && diff > 0)
1025 keyno--;
1026 cur->bc_ptrs[0] = keyno;
1027 /*
1028 * Return if we succeeded or not.
1029 */
1030 if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs))
1031 *stat = 0;
1032 else
1033 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
1034 return 0;
1035}
1036
1037/*
1038 * Move 1 record left from cur/level if possible. 832 * Move 1 record left from cur/level if possible.
1039 * Update cur to reflect the new path. 833 * Update cur to reflect the new path.
1040 */ 834 */
@@ -1798,59 +1592,6 @@ xfs_inobt_insert(
1798} 1592}
1799 1593
1800/* 1594/*
1801 * Lookup the record equal to ino in the btree given by cur.
1802 */
1803int /* error */
1804xfs_inobt_lookup_eq(
1805 xfs_btree_cur_t *cur, /* btree cursor */
1806 xfs_agino_t ino, /* starting inode of chunk */
1807 __int32_t fcnt, /* free inode count */
1808 xfs_inofree_t free, /* free inode mask */
1809 int *stat) /* success/failure */
1810{
1811 cur->bc_rec.i.ir_startino = ino;
1812 cur->bc_rec.i.ir_freecount = fcnt;
1813 cur->bc_rec.i.ir_free = free;
1814 return xfs_inobt_lookup(cur, XFS_LOOKUP_EQ, stat);
1815}
1816
1817/*
1818 * Lookup the first record greater than or equal to ino
1819 * in the btree given by cur.
1820 */
1821int /* error */
1822xfs_inobt_lookup_ge(
1823 xfs_btree_cur_t *cur, /* btree cursor */
1824 xfs_agino_t ino, /* starting inode of chunk */
1825 __int32_t fcnt, /* free inode count */
1826 xfs_inofree_t free, /* free inode mask */
1827 int *stat) /* success/failure */
1828{
1829 cur->bc_rec.i.ir_startino = ino;
1830 cur->bc_rec.i.ir_freecount = fcnt;
1831 cur->bc_rec.i.ir_free = free;
1832 return xfs_inobt_lookup(cur, XFS_LOOKUP_GE, stat);
1833}
1834
1835/*
1836 * Lookup the first record less than or equal to ino
1837 * in the btree given by cur.
1838 */
1839int /* error */
1840xfs_inobt_lookup_le(
1841 xfs_btree_cur_t *cur, /* btree cursor */
1842 xfs_agino_t ino, /* starting inode of chunk */
1843 __int32_t fcnt, /* free inode count */
1844 xfs_inofree_t free, /* free inode mask */
1845 int *stat) /* success/failure */
1846{
1847 cur->bc_rec.i.ir_startino = ino;
1848 cur->bc_rec.i.ir_freecount = fcnt;
1849 cur->bc_rec.i.ir_free = free;
1850 return xfs_inobt_lookup(cur, XFS_LOOKUP_LE, stat);
1851}
1852
1853/*
1854 * Update the record referred to by cur, to the value given 1595 * Update the record referred to by cur, to the value given
1855 * by [ino, fcnt, free]. 1596 * by [ino, fcnt, free].
1856 * This either works (return 0) or gets an EFSCORRUPTED error. 1597 * This either works (return 0) or gets an EFSCORRUPTED error.
@@ -1918,6 +1659,38 @@ xfs_inobt_get_maxrecs(
1918 return cur->bc_mp->m_inobt_mxr[level != 0]; 1659 return cur->bc_mp->m_inobt_mxr[level != 0];
1919} 1660}
1920 1661
1662STATIC void
1663xfs_inobt_init_key_from_rec(
1664 union xfs_btree_key *key,
1665 union xfs_btree_rec *rec)
1666{
1667 key->inobt.ir_startino = rec->inobt.ir_startino;
1668}
1669
1670/*
1671 * intial value of ptr for lookup
1672 */
1673STATIC void
1674xfs_inobt_init_ptr_from_cur(
1675 struct xfs_btree_cur *cur,
1676 union xfs_btree_ptr *ptr)
1677{
1678 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
1679
1680 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
1681
1682 ptr->s = agi->agi_root;
1683}
1684
1685STATIC __int64_t
1686xfs_inobt_key_diff(
1687 struct xfs_btree_cur *cur,
1688 union xfs_btree_key *key)
1689{
1690 return (__int64_t)be32_to_cpu(key->inobt.ir_startino) -
1691 cur->bc_rec.i.ir_startino;
1692}
1693
1921#ifdef XFS_BTREE_TRACE 1694#ifdef XFS_BTREE_TRACE
1922ktrace_t *xfs_inobt_trace_buf; 1695ktrace_t *xfs_inobt_trace_buf;
1923 1696
@@ -1990,6 +1763,9 @@ static const struct xfs_btree_ops xfs_inobt_ops = {
1990 1763
1991 .dup_cursor = xfs_inobt_dup_cursor, 1764 .dup_cursor = xfs_inobt_dup_cursor,
1992 .get_maxrecs = xfs_inobt_get_maxrecs, 1765 .get_maxrecs = xfs_inobt_get_maxrecs,
1766 .init_key_from_rec = xfs_inobt_init_key_from_rec,
1767 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur,
1768 .key_diff = xfs_inobt_key_diff,
1993 1769
1994#ifdef XFS_BTREE_TRACE 1770#ifdef XFS_BTREE_TRACE
1995 .trace_enter = xfs_inobt_trace_enter, 1771 .trace_enter = xfs_inobt_trace_enter,
diff --git a/fs/xfs/xfs_ialloc_btree.h b/fs/xfs/xfs_ialloc_btree.h
index 84554595d281..674b459521f5 100644
--- a/fs/xfs/xfs_ialloc_btree.h
+++ b/fs/xfs/xfs_ialloc_btree.h
@@ -136,26 +136,6 @@ extern int xfs_inobt_get_rec(struct xfs_btree_cur *cur, xfs_agino_t *ino,
136extern int xfs_inobt_insert(struct xfs_btree_cur *cur, int *stat); 136extern int xfs_inobt_insert(struct xfs_btree_cur *cur, int *stat);
137 137
138/* 138/*
139 * Lookup the record equal to ino in the btree given by cur.
140 */
141extern int xfs_inobt_lookup_eq(struct xfs_btree_cur *cur, xfs_agino_t ino,
142 __int32_t fcnt, xfs_inofree_t free, int *stat);
143
144/*
145 * Lookup the first record greater than or equal to ino
146 * in the btree given by cur.
147 */
148extern int xfs_inobt_lookup_ge(struct xfs_btree_cur *cur, xfs_agino_t ino,
149 __int32_t fcnt, xfs_inofree_t free, int *stat);
150
151/*
152 * Lookup the first record less than or equal to ino
153 * in the btree given by cur.
154 */
155extern int xfs_inobt_lookup_le(struct xfs_btree_cur *cur, xfs_agino_t ino,
156 __int32_t fcnt, xfs_inofree_t free, int *stat);
157
158/*
159 * Update the record referred to by cur, to the value given 139 * Update the record referred to by cur, to the value given
160 * by [ino, fcnt, free]. 140 * by [ino, fcnt, free].
161 * This either works (return 0) or gets an EFSCORRUPTED error. 141 * This either works (return 0) or gets an EFSCORRUPTED error.
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-28 00:39:17 -0500