aboutsummaryrefslogtreecommitdiffstats
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
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
-rw-r--r--fs/xfs/xfs_alloc_btree.c146
-rw-r--r--fs/xfs/xfs_bmap_btree.c138
-rw-r--r--fs/xfs/xfs_btree.c185
-rw-r--r--fs/xfs/xfs_btree.h1
-rw-r--r--fs/xfs/xfs_ialloc_btree.c147
5 files changed, 192 insertions, 425 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 */
diff --git a/fs/xfs/xfs_bmap_btree.c b/fs/xfs/xfs_bmap_btree.c
index 9d18fa8aa1da..809bd6ee177e 100644
--- a/fs/xfs/xfs_bmap_btree.c
+++ b/fs/xfs/xfs_bmap_btree.c
@@ -52,7 +52,6 @@
52STATIC int xfs_bmbt_killroot(xfs_btree_cur_t *); 52STATIC int xfs_bmbt_killroot(xfs_btree_cur_t *);
53STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int); 53STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
54STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int); 54STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
55STATIC int xfs_bmbt_lshift(xfs_btree_cur_t *, int, int *);
56STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *, 55STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *,
57 __uint64_t *, xfs_btree_cur_t **, int *); 56 __uint64_t *, xfs_btree_cur_t **, int *);
58 57
@@ -270,7 +269,7 @@ xfs_bmbt_delrec(
270 bno = be64_to_cpu(right->bb_leftsib); 269 bno = be64_to_cpu(right->bb_leftsib);
271 if (be16_to_cpu(right->bb_numrecs) - 1 >= 270 if (be16_to_cpu(right->bb_numrecs) - 1 >=
272 XFS_BMAP_BLOCK_IMINRECS(level, cur)) { 271 XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
273 if ((error = xfs_bmbt_lshift(tcur, level, &i))) { 272 if ((error = xfs_btree_lshift(tcur, level, &i))) {
274 XFS_BMBT_TRACE_CURSOR(cur, ERROR); 273 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
275 goto error0; 274 goto error0;
276 } 275 }
@@ -544,7 +543,7 @@ xfs_bmbt_insrec(
544 if (i) { 543 if (i) {
545 /* nothing */ 544 /* nothing */
546 } else { 545 } else {
547 if ((error = xfs_bmbt_lshift(cur, level, &i))) { 546 if ((error = xfs_btree_lshift(cur, level, &i))) {
548 XFS_BMBT_TRACE_CURSOR(cur, ERROR); 547 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
549 return error; 548 return error;
550 } 549 }
@@ -811,139 +810,6 @@ xfs_bmbt_log_ptrs(
811} 810}
812 811
813/* 812/*
814 * Move 1 record left from cur/level if possible.
815 * Update cur to reflect the new path.
816 */
817STATIC int /* error */
818xfs_bmbt_lshift(
819 xfs_btree_cur_t *cur,
820 int level,
821 int *stat) /* success/failure */
822{
823 int error; /* error return value */
824#ifdef DEBUG
825 int i; /* loop counter */
826#endif
827 xfs_bmbt_key_t key; /* bmap btree key */
828 xfs_buf_t *lbp; /* left buffer pointer */
829 xfs_bmbt_block_t *left; /* left btree block */
830 xfs_bmbt_key_t *lkp=NULL; /* left btree key */
831 xfs_bmbt_ptr_t *lpp; /* left address pointer */
832 int lrecs; /* left record count */
833 xfs_bmbt_rec_t *lrp=NULL; /* left record pointer */
834 xfs_mount_t *mp; /* file system mount point */
835 xfs_buf_t *rbp; /* right buffer pointer */
836 xfs_bmbt_block_t *right; /* right btree block */
837 xfs_bmbt_key_t *rkp=NULL; /* right btree key */
838 xfs_bmbt_ptr_t *rpp=NULL; /* right address pointer */
839 xfs_bmbt_rec_t *rrp=NULL; /* right record pointer */
840 int rrecs; /* right record count */
841
842 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
843 XFS_BMBT_TRACE_ARGI(cur, level);
844 if (level == cur->bc_nlevels - 1) {
845 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
846 *stat = 0;
847 return 0;
848 }
849 rbp = cur->bc_bufs[level];
850 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
851#ifdef DEBUG
852 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
853 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
854 return error;
855 }
856#endif
857 if (be64_to_cpu(right->bb_leftsib) == NULLDFSBNO) {
858 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
859 *stat = 0;
860 return 0;
861 }
862 if (cur->bc_ptrs[level] <= 1) {
863 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
864 *stat = 0;
865 return 0;
866 }
867 mp = cur->bc_mp;
868 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(right->bb_leftsib), 0,
869 &lbp, XFS_BMAP_BTREE_REF))) {
870 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
871 return error;
872 }
873 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
874 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
875 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
876 return error;
877 }
878 if (be16_to_cpu(left->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
879 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
880 *stat = 0;
881 return 0;
882 }
883 lrecs = be16_to_cpu(left->bb_numrecs) + 1;
884 if (level > 0) {
885 lkp = XFS_BMAP_KEY_IADDR(left, lrecs, cur);
886 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
887 *lkp = *rkp;
888 xfs_bmbt_log_keys(cur, lbp, lrecs, lrecs);
889 lpp = XFS_BMAP_PTR_IADDR(left, lrecs, cur);
890 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
891#ifdef DEBUG
892 if ((error = xfs_btree_check_lptr_disk(cur, *rpp, level))) {
893 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
894 return error;
895 }
896#endif
897 *lpp = *rpp;
898 xfs_bmbt_log_ptrs(cur, lbp, lrecs, lrecs);
899 } else {
900 lrp = XFS_BMAP_REC_IADDR(left, lrecs, cur);
901 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
902 *lrp = *rrp;
903 xfs_bmbt_log_recs(cur, lbp, lrecs, lrecs);
904 }
905 left->bb_numrecs = cpu_to_be16(lrecs);
906 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
907#ifdef DEBUG
908 if (level > 0)
909 xfs_btree_check_key(XFS_BTNUM_BMAP, lkp - 1, lkp);
910 else
911 xfs_btree_check_rec(XFS_BTNUM_BMAP, lrp - 1, lrp);
912#endif
913 rrecs = be16_to_cpu(right->bb_numrecs) - 1;
914 right->bb_numrecs = cpu_to_be16(rrecs);
915 xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
916 if (level > 0) {
917#ifdef DEBUG
918 for (i = 0; i < rrecs; i++) {
919 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i + 1],
920 level))) {
921 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
922 return error;
923 }
924 }
925#endif
926 memmove(rkp, rkp + 1, rrecs * sizeof(*rkp));
927 memmove(rpp, rpp + 1, rrecs * sizeof(*rpp));
928 xfs_bmbt_log_keys(cur, rbp, 1, rrecs);
929 xfs_bmbt_log_ptrs(cur, rbp, 1, rrecs);
930 } else {
931 memmove(rrp, rrp + 1, rrecs * sizeof(*rrp));
932 xfs_bmbt_log_recs(cur, rbp, 1, rrecs);
933 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
934 rkp = &key;
935 }
936 if ((error = xfs_btree_updkey(cur, (union xfs_btree_key *)rkp, level + 1))) {
937 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
938 return error;
939 }
940 cur->bc_ptrs[level]--;
941 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
942 *stat = 1;
943 return 0;
944}
945
946/*
947 * Determine the extent state. 813 * Determine the extent state.
948 */ 814 */
949/* ARGSUSED */ 815/* ARGSUSED */
diff --git a/fs/xfs/xfs_btree.c b/fs/xfs/xfs_btree.c
index e1a213781849..2b0d1422c4c6 100644
--- a/fs/xfs/xfs_btree.c
+++ b/fs/xfs/xfs_btree.c
@@ -1841,6 +1841,191 @@ error0:
1841} 1841}
1842 1842
1843/* 1843/*
1844 * Move 1 record left from cur/level if possible.
1845 * Update cur to reflect the new path.
1846 */
1847int /* error */
1848xfs_btree_lshift(
1849 struct xfs_btree_cur *cur,
1850 int level,
1851 int *stat) /* success/failure */
1852{
1853 union xfs_btree_key key; /* btree key */
1854 struct xfs_buf *lbp; /* left buffer pointer */
1855 struct xfs_btree_block *left; /* left btree block */
1856 int lrecs; /* left record count */
1857 struct xfs_buf *rbp; /* right buffer pointer */
1858 struct xfs_btree_block *right; /* right btree block */
1859 int rrecs; /* right record count */
1860 union xfs_btree_ptr lptr; /* left btree pointer */
1861 union xfs_btree_key *rkp = NULL; /* right btree key */
1862 union xfs_btree_ptr *rpp = NULL; /* right address pointer */
1863 union xfs_btree_rec *rrp = NULL; /* right record pointer */
1864 int error; /* error return value */
1865
1866 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1867 XFS_BTREE_TRACE_ARGI(cur, level);
1868
1869 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1870 level == cur->bc_nlevels - 1)
1871 goto out0;
1872
1873 /* Set up variables for this block as "right". */
1874 right = xfs_btree_get_block(cur, level, &rbp);
1875
1876#ifdef DEBUG
1877 error = xfs_btree_check_block(cur, right, level, rbp);
1878 if (error)
1879 goto error0;
1880#endif
1881
1882 /* If we've got no left sibling then we can't shift an entry left. */
1883 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
1884 if (xfs_btree_ptr_is_null(cur, &lptr))
1885 goto out0;
1886
1887 /*
1888 * If the cursor entry is the one that would be moved, don't
1889 * do it... it's too complicated.
1890 */
1891 if (cur->bc_ptrs[level] <= 1)
1892 goto out0;
1893
1894 /* Set up the left neighbor as "left". */
1895 error = xfs_btree_read_buf_block(cur, &lptr, level, 0, &left, &lbp);
1896 if (error)
1897 goto error0;
1898
1899 /* If it's full, it can't take another entry. */
1900 lrecs = xfs_btree_get_numrecs(left);
1901 if (lrecs == cur->bc_ops->get_maxrecs(cur, level))
1902 goto out0;
1903
1904 rrecs = xfs_btree_get_numrecs(right);
1905
1906 /*
1907 * We add one entry to the left side and remove one for the right side.
1908 * Accout for it here, the changes will be updated on disk and logged
1909 * later.
1910 */
1911 lrecs++;
1912 rrecs--;
1913
1914 XFS_BTREE_STATS_INC(cur, lshift);
1915 XFS_BTREE_STATS_ADD(cur, moves, 1);
1916
1917 /*
1918 * If non-leaf, copy a key and a ptr to the left block.
1919 * Log the changes to the left block.
1920 */
1921 if (level > 0) {
1922 /* It's a non-leaf. Move keys and pointers. */
1923 union xfs_btree_key *lkp; /* left btree key */
1924 union xfs_btree_ptr *lpp; /* left address pointer */
1925
1926 lkp = xfs_btree_key_addr(cur, lrecs, left);
1927 rkp = xfs_btree_key_addr(cur, 1, right);
1928
1929 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
1930 rpp = xfs_btree_ptr_addr(cur, 1, right);
1931#ifdef DEBUG
1932 error = xfs_btree_check_ptr(cur, rpp, 0, level);
1933 if (error)
1934 goto error0;
1935#endif
1936 xfs_btree_copy_keys(cur, lkp, rkp, 1);
1937 xfs_btree_copy_ptrs(cur, lpp, rpp, 1);
1938
1939 xfs_btree_log_keys(cur, lbp, lrecs, lrecs);
1940 xfs_btree_log_ptrs(cur, lbp, lrecs, lrecs);
1941
1942 xfs_btree_check_key(cur->bc_btnum,
1943 xfs_btree_key_addr(cur, lrecs - 1, left),
1944 lkp);
1945 } else {
1946 /* It's a leaf. Move records. */
1947 union xfs_btree_rec *lrp; /* left record pointer */
1948
1949 lrp = xfs_btree_rec_addr(cur, lrecs, left);
1950 rrp = xfs_btree_rec_addr(cur, 1, right);
1951
1952 xfs_btree_copy_recs(cur, lrp, rrp, 1);
1953 xfs_btree_log_recs(cur, lbp, lrecs, lrecs);
1954
1955 xfs_btree_check_rec(cur->bc_btnum,
1956 xfs_btree_rec_addr(cur, lrecs - 1, left),
1957 lrp);
1958 }
1959
1960 xfs_btree_set_numrecs(left, lrecs);
1961 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
1962
1963 xfs_btree_set_numrecs(right, rrecs);
1964 xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
1965
1966 /*
1967 * Slide the contents of right down one entry.
1968 */
1969 XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1);
1970 if (level > 0) {
1971 /* It's a nonleaf. operate on keys and ptrs */
1972#ifdef DEBUG
1973 int i; /* loop index */
1974
1975 for (i = 0; i < rrecs; i++) {
1976 error = xfs_btree_check_ptr(cur, rpp, i + 1, level);
1977 if (error)
1978 goto error0;
1979 }
1980#endif
1981 xfs_btree_shift_keys(cur,
1982 xfs_btree_key_addr(cur, 2, right),
1983 -1, rrecs);
1984 xfs_btree_shift_ptrs(cur,
1985 xfs_btree_ptr_addr(cur, 2, right),
1986 -1, rrecs);
1987
1988 xfs_btree_log_keys(cur, rbp, 1, rrecs);
1989 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
1990 } else {
1991 /* It's a leaf. operate on records */
1992 xfs_btree_shift_recs(cur,
1993 xfs_btree_rec_addr(cur, 2, right),
1994 -1, rrecs);
1995 xfs_btree_log_recs(cur, rbp, 1, rrecs);
1996
1997 /*
1998 * If it's the first record in the block, we'll need a key
1999 * structure to pass up to the next level (updkey).
2000 */
2001 cur->bc_ops->init_key_from_rec(&key,
2002 xfs_btree_rec_addr(cur, 1, right));
2003 rkp = &key;
2004 }
2005
2006 /* Update the parent key values of right. */
2007 error = xfs_btree_updkey(cur, rkp, level + 1);
2008 if (error)
2009 goto error0;
2010
2011 /* Slide the cursor value left one. */
2012 cur->bc_ptrs[level]--;
2013
2014 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2015 *stat = 1;
2016 return 0;
2017
2018out0:
2019 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2020 *stat = 0;
2021 return 0;
2022
2023error0:
2024 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2025 return error;
2026}
2027
2028/*
1844 * Move 1 record right from cur/level if possible. 2029 * Move 1 record right from cur/level if possible.
1845 * Update cur to reflect the new path. 2030 * Update cur to reflect the new path.
1846 */ 2031 */
diff --git a/fs/xfs/xfs_btree.h b/fs/xfs/xfs_btree.h
index 04311dbeff19..7cde287b5c9c 100644
--- a/fs/xfs/xfs_btree.h
+++ b/fs/xfs/xfs_btree.h
@@ -533,6 +533,7 @@ int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
533int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *); 533int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
534int xfs_btree_updkey(struct xfs_btree_cur *, union xfs_btree_key *, int); 534int xfs_btree_updkey(struct xfs_btree_cur *, union xfs_btree_key *, int);
535int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *); 535int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *);
536int xfs_btree_lshift(struct xfs_btree_cur *, int, int *);
536int xfs_btree_rshift(struct xfs_btree_cur *, int, int *); 537int xfs_btree_rshift(struct xfs_btree_cur *, int, int *);
537 538
538/* 539/*
diff --git a/fs/xfs/xfs_ialloc_btree.c b/fs/xfs/xfs_ialloc_btree.c
index 457f88a76e10..60f5db5d6dfa 100644
--- a/fs/xfs/xfs_ialloc_btree.c
+++ b/fs/xfs/xfs_ialloc_btree.c
@@ -43,7 +43,6 @@ STATIC void xfs_inobt_log_block(xfs_trans_t *, xfs_buf_t *, int);
43STATIC void xfs_inobt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int); 43STATIC void xfs_inobt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
44STATIC void xfs_inobt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int); 44STATIC void xfs_inobt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
45STATIC void xfs_inobt_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int); 45STATIC void xfs_inobt_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
46STATIC int xfs_inobt_lshift(xfs_btree_cur_t *, int, int *);
47STATIC int xfs_inobt_newroot(xfs_btree_cur_t *, int *); 46STATIC int xfs_inobt_newroot(xfs_btree_cur_t *, int *);
48STATIC int xfs_inobt_split(xfs_btree_cur_t *, int, xfs_agblock_t *, 47STATIC int xfs_inobt_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
49 xfs_inobt_key_t *, xfs_btree_cur_t **, int *); 48 xfs_inobt_key_t *, xfs_btree_cur_t **, int *);
@@ -276,7 +275,7 @@ xfs_inobt_delrec(
276 */ 275 */
277 if (be16_to_cpu(right->bb_numrecs) - 1 >= 276 if (be16_to_cpu(right->bb_numrecs) - 1 >=
278 XFS_INOBT_BLOCK_MINRECS(level, cur)) { 277 XFS_INOBT_BLOCK_MINRECS(level, cur)) {
279 if ((error = xfs_inobt_lshift(tcur, level, &i))) 278 if ((error = xfs_btree_lshift(tcur, level, &i)))
280 goto error0; 279 goto error0;
281 if (i) { 280 if (i) {
282 ASSERT(be16_to_cpu(block->bb_numrecs) >= 281 ASSERT(be16_to_cpu(block->bb_numrecs) >=
@@ -616,7 +615,7 @@ xfs_inobt_insrec(
616 * Next, try shifting an entry to the left neighbor. 615 * Next, try shifting an entry to the left neighbor.
617 */ 616 */
618 else { 617 else {
619 if ((error = xfs_inobt_lshift(cur, level, &i))) 618 if ((error = xfs_btree_lshift(cur, level, &i)))
620 return error; 619 return error;
621 if (i) { 620 if (i) {
622 optr = ptr = cur->bc_ptrs[level]; 621 optr = ptr = cur->bc_ptrs[level];
@@ -827,148 +826,6 @@ xfs_inobt_log_recs(
827} 826}
828 827
829/* 828/*
830 * Move 1 record left from cur/level if possible.
831 * Update cur to reflect the new path.
832 */
833STATIC int /* error */
834xfs_inobt_lshift(
835 xfs_btree_cur_t *cur, /* btree cursor */
836 int level, /* level to shift record on */
837 int *stat) /* success/failure */
838{
839 int error; /* error return value */
840#ifdef DEBUG
841 int i; /* loop index */
842#endif
843 xfs_inobt_key_t key; /* key value for leaf level upward */
844 xfs_buf_t *lbp; /* buffer for left neighbor block */
845 xfs_inobt_block_t *left; /* left neighbor btree block */
846 xfs_inobt_key_t *lkp=NULL; /* key pointer for left block */
847 xfs_inobt_ptr_t *lpp; /* address pointer for left block */
848 xfs_inobt_rec_t *lrp=NULL; /* record pointer for left block */
849 int nrec; /* new number of left block entries */
850 xfs_buf_t *rbp; /* buffer for right (current) block */
851 xfs_inobt_block_t *right; /* right (current) btree block */
852 xfs_inobt_key_t *rkp=NULL; /* key pointer for right block */
853 xfs_inobt_ptr_t *rpp=NULL; /* address pointer for right block */
854 xfs_inobt_rec_t *rrp=NULL; /* record pointer for right block */
855
856 /*
857 * Set up variables for this block as "right".
858 */
859 rbp = cur->bc_bufs[level];
860 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
861#ifdef DEBUG
862 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
863 return error;
864#endif
865 /*
866 * If we've got no left sibling then we can't shift an entry left.
867 */
868 if (be32_to_cpu(right->bb_leftsib) == NULLAGBLOCK) {
869 *stat = 0;
870 return 0;
871 }
872 /*
873 * If the cursor entry is the one that would be moved, don't
874 * do it... it's too complicated.
875 */
876 if (cur->bc_ptrs[level] <= 1) {
877 *stat = 0;
878 return 0;
879 }
880 /*
881 * Set up the left neighbor as "left".
882 */
883 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
884 cur->bc_private.a.agno, be32_to_cpu(right->bb_leftsib),
885 0, &lbp, XFS_INO_BTREE_REF)))
886 return error;
887 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
888 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
889 return error;
890 /*
891 * If it's full, it can't take another entry.
892 */
893 if (be16_to_cpu(left->bb_numrecs) == XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
894 *stat = 0;
895 return 0;
896 }
897 nrec = be16_to_cpu(left->bb_numrecs) + 1;
898 /*
899 * If non-leaf, copy a key and a ptr to the left block.
900 */
901 if (level > 0) {
902 lkp = XFS_INOBT_KEY_ADDR(left, nrec, cur);
903 rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
904 *lkp = *rkp;
905 xfs_inobt_log_keys(cur, lbp, nrec, nrec);
906 lpp = XFS_INOBT_PTR_ADDR(left, nrec, cur);
907 rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
908#ifdef DEBUG
909 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*rpp), level)))
910 return error;
911#endif
912 *lpp = *rpp;
913 xfs_inobt_log_ptrs(cur, lbp, nrec, nrec);
914 }
915 /*
916 * If leaf, copy a record to the left block.
917 */
918 else {
919 lrp = XFS_INOBT_REC_ADDR(left, nrec, cur);
920 rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
921 *lrp = *rrp;
922 xfs_inobt_log_recs(cur, lbp, nrec, nrec);
923 }
924 /*
925 * Bump and log left's numrecs, decrement and log right's numrecs.
926 */
927 be16_add_cpu(&left->bb_numrecs, 1);
928 xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
929#ifdef DEBUG
930 if (level > 0)
931 xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
932 else
933 xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
934#endif
935 be16_add_cpu(&right->bb_numrecs, -1);
936 xfs_inobt_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
937 /*
938 * Slide the contents of right down one entry.
939 */
940 if (level > 0) {
941#ifdef DEBUG
942 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
943 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i + 1]),
944 level)))
945 return error;
946 }
947#endif
948 memmove(rkp, rkp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
949 memmove(rpp, rpp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
950 xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
951 xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
952 } else {
953 memmove(rrp, rrp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
954 xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
955 key.ir_startino = rrp->ir_startino;
956 rkp = &key;
957 }
958 /*
959 * Update the parent key values of right.
960 */
961 if ((error = xfs_btree_updkey(cur, (union xfs_btree_key *)rkp, level + 1)))
962 return error;
963 /*
964 * Slide the cursor value left one.
965 */
966 cur->bc_ptrs[level]--;
967 *stat = 1;
968 return 0;
969}
970
971/*
972 * Allocate a new root block, fill it in. 829 * Allocate a new root block, fill it in.
973 */ 830 */
974STATIC int /* error */ 831STATIC int /* error */
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-01 06:19:21 -0500