aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_alloc_btree.c
diff options
context:
space:
mode:
authorChristoph Hellwig <hch@infradead.org>2008-10-30 01:56:53 -0400
committerLachlan McIlroy <lachlan@sgi.com>2008-10-30 01:56:53 -0400
commit687b890a184fef263ebb773926e1f4aa69240d01 (patch)
treeb8f80c134ff994927225367d148ee63f4d76506b /fs/xfs/xfs_alloc_btree.c
parent9eaead51bed957af0070a277d945744a76df0c8b (diff)
[XFS] implement generic xfs_btree_lshift
Make the btree left shift code generic. Based on a patch from David Chinner with lots of changes to follow the original btree implementations more closely. While this loses some of the generic helper routines for inserting/moving/removing records it also solves some of the one off bugs in the original code and makes it easier to verify. SGI-PV: 985583 SGI-Modid: xfs-linux-melb:xfs-kern:32197a 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.c146
1 files changed, 2 insertions, 144 deletions
diff --git a/fs/xfs/xfs_alloc_btree.c b/fs/xfs/xfs_alloc_btree.c
index 31e42891fc9a..974a412ebc8a 100644
--- a/fs/xfs/xfs_alloc_btree.c
+++ b/fs/xfs/xfs_alloc_btree.c
@@ -47,7 +47,6 @@ STATIC void xfs_alloc_log_block(xfs_trans_t *, xfs_buf_t *, int);
47STATIC void xfs_alloc_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int); 47STATIC void xfs_alloc_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
48STATIC void xfs_alloc_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int); 48STATIC void xfs_alloc_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
49STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int); 49STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
50STATIC int xfs_alloc_lshift(xfs_btree_cur_t *, int, int *);
51STATIC int xfs_alloc_newroot(xfs_btree_cur_t *, int *); 50STATIC int xfs_alloc_newroot(xfs_btree_cur_t *, int *);
52STATIC int xfs_alloc_split(xfs_btree_cur_t *, int, xfs_agblock_t *, 51STATIC int xfs_alloc_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
53 xfs_alloc_key_t *, xfs_btree_cur_t **, int *); 52 xfs_alloc_key_t *, xfs_btree_cur_t **, int *);
@@ -326,7 +325,7 @@ xfs_alloc_delrec(
326 */ 325 */
327 if (be16_to_cpu(right->bb_numrecs) - 1 >= 326 if (be16_to_cpu(right->bb_numrecs) - 1 >=
328 XFS_ALLOC_BLOCK_MINRECS(level, cur)) { 327 XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
329 if ((error = xfs_alloc_lshift(tcur, level, &i))) 328 if ((error = xfs_btree_lshift(tcur, level, &i)))
330 goto error0; 329 goto error0;
331 if (i) { 330 if (i) {
332 ASSERT(be16_to_cpu(block->bb_numrecs) >= 331 ASSERT(be16_to_cpu(block->bb_numrecs) >=
@@ -691,7 +690,7 @@ xfs_alloc_insrec(
691 * Next, try shifting an entry to the left neighbor. 690 * Next, try shifting an entry to the left neighbor.
692 */ 691 */
693 else { 692 else {
694 if ((error = xfs_alloc_lshift(cur, level, &i))) 693 if ((error = xfs_btree_lshift(cur, level, &i)))
695 return error; 694 return error;
696 if (i) 695 if (i)
697 optr = ptr = cur->bc_ptrs[level]; 696 optr = ptr = cur->bc_ptrs[level];
@@ -936,147 +935,6 @@ xfs_alloc_log_recs(
936} 935}
937 936
938/* 937/*
939 * Move 1 record left from cur/level if possible.
940 * Update cur to reflect the new path.
941 */
942STATIC int /* error */
943xfs_alloc_lshift(
944 xfs_btree_cur_t *cur, /* btree cursor */
945 int level, /* level to shift record on */
946 int *stat) /* success/failure */
947{
948 int error; /* error return value */
949#ifdef DEBUG
950 int i; /* loop index */
951#endif
952 xfs_alloc_key_t key; /* key value for leaf level upward */
953 xfs_buf_t *lbp; /* buffer for left neighbor block */
954 xfs_alloc_block_t *left; /* left neighbor btree block */
955 int nrec; /* new number of left block entries */
956 xfs_buf_t *rbp; /* buffer for right (current) block */
957 xfs_alloc_block_t *right; /* right (current) btree block */
958 xfs_alloc_key_t *rkp=NULL; /* key pointer for right block */
959 xfs_alloc_ptr_t *rpp=NULL; /* address pointer for right block */
960 xfs_alloc_rec_t *rrp=NULL; /* record pointer for right block */
961
962 /*
963 * Set up variables for this block as "right".
964 */
965 rbp = cur->bc_bufs[level];
966 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
967#ifdef DEBUG
968 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
969 return error;
970#endif
971 /*
972 * If we've got no left sibling then we can't shift an entry left.
973 */
974 if (be32_to_cpu(right->bb_leftsib) == NULLAGBLOCK) {
975 *stat = 0;
976 return 0;
977 }
978 /*
979 * If the cursor entry is the one that would be moved, don't
980 * do it... it's too complicated.
981 */
982 if (cur->bc_ptrs[level] <= 1) {
983 *stat = 0;
984 return 0;
985 }
986 /*
987 * Set up the left neighbor as "left".
988 */
989 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
990 cur->bc_private.a.agno, be32_to_cpu(right->bb_leftsib),
991 0, &lbp, XFS_ALLOC_BTREE_REF)))
992 return error;
993 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
994 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
995 return error;
996 /*
997 * If it's full, it can't take another entry.
998 */
999 if (be16_to_cpu(left->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
1000 *stat = 0;
1001 return 0;
1002 }
1003 nrec = be16_to_cpu(left->bb_numrecs) + 1;
1004 /*
1005 * If non-leaf, copy a key and a ptr to the left block.
1006 */
1007 if (level > 0) {
1008 xfs_alloc_key_t *lkp; /* key pointer for left block */
1009 xfs_alloc_ptr_t *lpp; /* address pointer for left block */
1010
1011 lkp = XFS_ALLOC_KEY_ADDR(left, nrec, cur);
1012 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1013 *lkp = *rkp;
1014 xfs_alloc_log_keys(cur, lbp, nrec, nrec);
1015 lpp = XFS_ALLOC_PTR_ADDR(left, nrec, cur);
1016 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1017#ifdef DEBUG
1018 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*rpp), level)))
1019 return error;
1020#endif
1021 *lpp = *rpp;
1022 xfs_alloc_log_ptrs(cur, lbp, nrec, nrec);
1023 xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
1024 }
1025 /*
1026 * If leaf, copy a record to the left block.
1027 */
1028 else {
1029 xfs_alloc_rec_t *lrp; /* record pointer for left block */
1030
1031 lrp = XFS_ALLOC_REC_ADDR(left, nrec, cur);
1032 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1033 *lrp = *rrp;
1034 xfs_alloc_log_recs(cur, lbp, nrec, nrec);
1035 xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
1036 }
1037 /*
1038 * Bump and log left's numrecs, decrement and log right's numrecs.
1039 */
1040 be16_add_cpu(&left->bb_numrecs, 1);
1041 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
1042 be16_add_cpu(&right->bb_numrecs, -1);
1043 xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1044 /*
1045 * Slide the contents of right down one entry.
1046 */
1047 if (level > 0) {
1048#ifdef DEBUG
1049 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
1050 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i + 1]),
1051 level)))
1052 return error;
1053 }
1054#endif
1055 memmove(rkp, rkp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1056 memmove(rpp, rpp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1057 xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1058 xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1059 } else {
1060 memmove(rrp, rrp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1061 xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1062 key.ar_startblock = rrp->ar_startblock;
1063 key.ar_blockcount = rrp->ar_blockcount;
1064 rkp = &key;
1065 }
1066 /*
1067 * Update the parent key values of right.
1068 */
1069 if ((error = xfs_btree_updkey(cur, (union xfs_btree_key *)rkp, level + 1)))
1070 return error;
1071 /*
1072 * Slide the cursor value left one.
1073 */
1074 cur->bc_ptrs[level]--;
1075 *stat = 1;
1076 return 0;
1077}
1078
1079/*
1080 * Allocate a new root block, fill it in. 938 * Allocate a new root block, fill it in.
1081 */ 939 */
1082STATIC int /* error */ 940STATIC int /* error */