aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_alloc_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_alloc_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_alloc_btree.c')
-rw-r--r--fs/xfs/xfs_alloc_btree.c312
1 files changed, 48 insertions, 264 deletions
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,
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-01 08:20:46 -0400