aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_ialloc_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_ialloc_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_ialloc_btree.c')
-rw-r--r--fs/xfs/xfs_ialloc_btree.c294
1 files changed, 35 insertions, 259 deletions
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,
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-10 21:53:27 -0500