aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_bmap_btree.c
diff options
context:
space:
mode:
authorChristoph Hellwig <hch@infradead.org>2008-10-30 01:57:03 -0400
committerLachlan McIlroy <lachlan@sgi.com>2008-10-30 01:57:03 -0400
commitf5eb8e7ca58bc1e92436614444006120d21668ba (patch)
tree94825b885653224f74c6087956cb4e1930380467 /fs/xfs/xfs_bmap_btree.c
parent687b890a184fef263ebb773926e1f4aa69240d01 (diff)
[XFS] implement generic xfs_btree_split
Make the btree split 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:32198a 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_bmap_btree.c')
-rw-r--r--fs/xfs/xfs_bmap_btree.c275
1 files changed, 93 insertions, 182 deletions
diff --git a/fs/xfs/xfs_bmap_btree.c b/fs/xfs/xfs_bmap_btree.c
index 809bd6ee177e..e7539263457f 100644
--- a/fs/xfs/xfs_bmap_btree.c
+++ b/fs/xfs/xfs_bmap_btree.c
@@ -52,8 +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_split(xfs_btree_cur_t *, int, xfs_fsblock_t *,
56 __uint64_t *, xfs_btree_cur_t **, int *);
57 55
58#undef EXIT 56#undef EXIT
59 57
@@ -550,13 +548,17 @@ xfs_bmbt_insrec(
550 if (i) { 548 if (i) {
551 optr = ptr = cur->bc_ptrs[level]; 549 optr = ptr = cur->bc_ptrs[level];
552 } else { 550 } else {
553 if ((error = xfs_bmbt_split(cur, level, 551 union xfs_btree_ptr bno = { .l = cpu_to_be64(nbno) };
554 &nbno, &startoff, &ncur, 552 union xfs_btree_key skey;
553 if ((error = xfs_btree_split(cur, level,
554 &bno, &skey, &ncur,
555 &i))) { 555 &i))) {
556 XFS_BMBT_TRACE_CURSOR(cur, 556 XFS_BMBT_TRACE_CURSOR(cur,
557 ERROR); 557 ERROR);
558 return error; 558 return error;
559 } 559 }
560 nbno = be64_to_cpu(bno.l);
561 startoff = be64_to_cpu(skey.bmbt.br_startoff);
560 if (i) { 562 if (i) {
561 block = xfs_bmbt_get_block( 563 block = xfs_bmbt_get_block(
562 cur, level, &bp); 564 cur, level, &bp);
@@ -825,184 +827,6 @@ xfs_extent_state(
825 return XFS_EXT_NORM; 827 return XFS_EXT_NORM;
826} 828}
827 829
828
829/*
830 * Split cur/level block in half.
831 * Return new block number and its first record (to be inserted into parent).
832 */
833STATIC int /* error */
834xfs_bmbt_split(
835 xfs_btree_cur_t *cur,
836 int level,
837 xfs_fsblock_t *bnop,
838 __uint64_t *startoff,
839 xfs_btree_cur_t **curp,
840 int *stat) /* success/failure */
841{
842 xfs_alloc_arg_t args; /* block allocation args */
843 int error; /* error return value */
844 int i; /* loop counter */
845 xfs_fsblock_t lbno; /* left sibling block number */
846 xfs_buf_t *lbp; /* left buffer pointer */
847 xfs_bmbt_block_t *left; /* left btree block */
848 xfs_bmbt_key_t *lkp; /* left btree key */
849 xfs_bmbt_ptr_t *lpp; /* left address pointer */
850 xfs_bmbt_rec_t *lrp; /* left record pointer */
851 xfs_buf_t *rbp; /* right buffer pointer */
852 xfs_bmbt_block_t *right; /* right btree block */
853 xfs_bmbt_key_t *rkp; /* right btree key */
854 xfs_bmbt_ptr_t *rpp; /* right address pointer */
855 xfs_bmbt_block_t *rrblock; /* right-right btree block */
856 xfs_buf_t *rrbp; /* right-right buffer pointer */
857 xfs_bmbt_rec_t *rrp; /* right record pointer */
858
859 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
860 // disable until merged into common code
861// XFS_BMBT_TRACE_ARGIFK(cur, level, *bnop, *startoff);
862 args.tp = cur->bc_tp;
863 args.mp = cur->bc_mp;
864 lbp = cur->bc_bufs[level];
865 lbno = XFS_DADDR_TO_FSB(args.mp, XFS_BUF_ADDR(lbp));
866 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
867 args.fsbno = cur->bc_private.b.firstblock;
868 args.firstblock = args.fsbno;
869 args.minleft = 0;
870 if (args.fsbno == NULLFSBLOCK) {
871 args.fsbno = lbno;
872 args.type = XFS_ALLOCTYPE_START_BNO;
873 /*
874 * Make sure there is sufficient room left in the AG to
875 * complete a full tree split for an extent insert. If
876 * we are converting the middle part of an extent then
877 * we may need space for two tree splits.
878 *
879 * We are relying on the caller to make the correct block
880 * reservation for this operation to succeed. If the
881 * reservation amount is insufficient then we may fail a
882 * block allocation here and corrupt the filesystem.
883 */
884 args.minleft = xfs_trans_get_block_res(args.tp);
885 } else if (cur->bc_private.b.flist->xbf_low)
886 args.type = XFS_ALLOCTYPE_START_BNO;
887 else
888 args.type = XFS_ALLOCTYPE_NEAR_BNO;
889 args.mod = args.alignment = args.total = args.isfl =
890 args.userdata = args.minalignslop = 0;
891 args.minlen = args.maxlen = args.prod = 1;
892 args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
893 if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
894 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
895 return XFS_ERROR(ENOSPC);
896 }
897 if ((error = xfs_alloc_vextent(&args))) {
898 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
899 return error;
900 }
901 if (args.fsbno == NULLFSBLOCK && args.minleft) {
902 /*
903 * Could not find an AG with enough free space to satisfy
904 * a full btree split. Try again without minleft and if
905 * successful activate the lowspace algorithm.
906 */
907 args.fsbno = 0;
908 args.type = XFS_ALLOCTYPE_FIRST_AG;
909 args.minleft = 0;
910 if ((error = xfs_alloc_vextent(&args))) {
911 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
912 return error;
913 }
914 cur->bc_private.b.flist->xbf_low = 1;
915 }
916 if (args.fsbno == NULLFSBLOCK) {
917 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
918 *stat = 0;
919 return 0;
920 }
921 ASSERT(args.len == 1);
922 cur->bc_private.b.firstblock = args.fsbno;
923 cur->bc_private.b.allocated++;
924 cur->bc_private.b.ip->i_d.di_nblocks++;
925 xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
926 XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
927 XFS_TRANS_DQ_BCOUNT, 1L);
928 rbp = xfs_btree_get_bufl(args.mp, args.tp, args.fsbno, 0);
929 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
930#ifdef DEBUG
931 if ((error = xfs_btree_check_lblock(cur, left, level, rbp))) {
932 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
933 return error;
934 }
935#endif
936 right->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
937 right->bb_level = left->bb_level;
938 right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
939 if ((be16_to_cpu(left->bb_numrecs) & 1) &&
940 cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
941 be16_add_cpu(&right->bb_numrecs, 1);
942 i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
943 if (level > 0) {
944 lkp = XFS_BMAP_KEY_IADDR(left, i, cur);
945 lpp = XFS_BMAP_PTR_IADDR(left, i, cur);
946 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
947 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
948#ifdef DEBUG
949 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
950 if ((error = xfs_btree_check_lptr_disk(cur, lpp[i], level))) {
951 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
952 return error;
953 }
954 }
955#endif
956 memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
957 memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
958 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
959 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
960 *startoff = be64_to_cpu(rkp->br_startoff);
961 } else {
962 lrp = XFS_BMAP_REC_IADDR(left, i, cur);
963 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
964 memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
965 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
966 *startoff = xfs_bmbt_disk_get_startoff(rrp);
967 }
968 be16_add_cpu(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
969 right->bb_rightsib = left->bb_rightsib;
970 left->bb_rightsib = cpu_to_be64(args.fsbno);
971 right->bb_leftsib = cpu_to_be64(lbno);
972 xfs_bmbt_log_block(cur, rbp, XFS_BB_ALL_BITS);
973 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
974 if (be64_to_cpu(right->bb_rightsib) != NULLDFSBNO) {
975 if ((error = xfs_btree_read_bufl(args.mp, args.tp,
976 be64_to_cpu(right->bb_rightsib), 0, &rrbp,
977 XFS_BMAP_BTREE_REF))) {
978 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
979 return error;
980 }
981 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
982 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
983 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
984 return error;
985 }
986 rrblock->bb_leftsib = cpu_to_be64(args.fsbno);
987 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
988 }
989 if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
990 xfs_btree_setbuf(cur, level, rbp);
991 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
992 }
993 if (level + 1 < cur->bc_nlevels) {
994 if ((error = xfs_btree_dup_cursor(cur, curp))) {
995 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
996 return error;
997 }
998 (*curp)->bc_ptrs[level + 1]++;
999 }
1000 *bnop = args.fsbno;
1001 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1002 *stat = 1;
1003 return 0;
1004}
1005
1006/* 830/*
1007 * Convert on-disk form of btree root to in-memory form. 831 * Convert on-disk form of btree root to in-memory form.
1008 */ 832 */
@@ -1738,6 +1562,92 @@ xfs_bmbt_dup_cursor(
1738} 1562}
1739 1563
1740STATIC int 1564STATIC int
1565xfs_bmbt_alloc_block(
1566 struct xfs_btree_cur *cur,
1567 union xfs_btree_ptr *start,
1568 union xfs_btree_ptr *new,
1569 int length,
1570 int *stat)
1571{
1572 xfs_alloc_arg_t args; /* block allocation args */
1573 int error; /* error return value */
1574
1575 memset(&args, 0, sizeof(args));
1576 args.tp = cur->bc_tp;
1577 args.mp = cur->bc_mp;
1578 args.fsbno = cur->bc_private.b.firstblock;
1579 args.firstblock = args.fsbno;
1580
1581 if (args.fsbno == NULLFSBLOCK) {
1582 args.fsbno = be64_to_cpu(start->l);
1583 args.type = XFS_ALLOCTYPE_START_BNO;
1584 /*
1585 * Make sure there is sufficient room left in the AG to
1586 * complete a full tree split for an extent insert. If
1587 * we are converting the middle part of an extent then
1588 * we may need space for two tree splits.
1589 *
1590 * We are relying on the caller to make the correct block
1591 * reservation for this operation to succeed. If the
1592 * reservation amount is insufficient then we may fail a
1593 * block allocation here and corrupt the filesystem.
1594 */
1595 args.minleft = xfs_trans_get_block_res(args.tp);
1596 } else if (cur->bc_private.b.flist->xbf_low) {
1597 args.type = XFS_ALLOCTYPE_START_BNO;
1598 } else {
1599 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1600 }
1601
1602 args.minlen = args.maxlen = args.prod = 1;
1603 args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
1604 if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
1605 error = XFS_ERROR(ENOSPC);
1606 goto error0;
1607 }
1608 error = xfs_alloc_vextent(&args);
1609 if (error)
1610 goto error0;
1611
1612 if (args.fsbno == NULLFSBLOCK && args.minleft) {
1613 /*
1614 * Could not find an AG with enough free space to satisfy
1615 * a full btree split. Try again without minleft and if
1616 * successful activate the lowspace algorithm.
1617 */
1618 args.fsbno = 0;
1619 args.type = XFS_ALLOCTYPE_FIRST_AG;
1620 args.minleft = 0;
1621 error = xfs_alloc_vextent(&args);
1622 if (error)
1623 goto error0;
1624 cur->bc_private.b.flist->xbf_low = 1;
1625 }
1626 if (args.fsbno == NULLFSBLOCK) {
1627 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1628 *stat = 0;
1629 return 0;
1630 }
1631 ASSERT(args.len == 1);
1632 cur->bc_private.b.firstblock = args.fsbno;
1633 cur->bc_private.b.allocated++;
1634 cur->bc_private.b.ip->i_d.di_nblocks++;
1635 xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
1636 XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1637 XFS_TRANS_DQ_BCOUNT, 1L);
1638
1639 new->l = cpu_to_be64(args.fsbno);
1640
1641 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1642 *stat = 1;
1643 return 0;
1644
1645 error0:
1646 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1647 return error;
1648}
1649
1650STATIC int
1741xfs_bmbt_get_maxrecs( 1651xfs_bmbt_get_maxrecs(
1742 struct xfs_btree_cur *cur, 1652 struct xfs_btree_cur *cur,
1743 int level) 1653 int level)
@@ -1861,6 +1771,7 @@ static const struct xfs_btree_ops xfs_bmbt_ops = {
1861 .key_len = sizeof(xfs_bmbt_key_t), 1771 .key_len = sizeof(xfs_bmbt_key_t),
1862 1772
1863 .dup_cursor = xfs_bmbt_dup_cursor, 1773 .dup_cursor = xfs_bmbt_dup_cursor,
1774 .alloc_block = xfs_bmbt_alloc_block,
1864 .get_maxrecs = xfs_bmbt_get_maxrecs, 1775 .get_maxrecs = xfs_bmbt_get_maxrecs,
1865 .init_key_from_rec = xfs_bmbt_init_key_from_rec, 1776 .init_key_from_rec = xfs_bmbt_init_key_from_rec,
1866 .init_ptr_from_cur = xfs_bmbt_init_ptr_from_cur, 1777 .init_ptr_from_cur = xfs_bmbt_init_ptr_from_cur,
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-02 10:23:16 -0400