aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_btree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/xfs/xfs_btree.c')
-rw-r--r--fs/xfs/xfs_btree.c222
1 files changed, 222 insertions, 0 deletions
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}