xfs: detect self referencing btree sibling pointers

Source kernel commit: dc04db2aa7c9307e740d6d0e173085301c173b1a

To catch the obvious graph cycle problem and hence potential endless
looping.

Signed-off-by: Dave Chinner <dchinner@redhat.com>
Reviewed-by: Christoph Hellwig <hch@lst.de>
Reviewed-by: Darrick J. Wong <djwong@kernel.org>
Signed-off-by: Dave Chinner <david@fromorbit.com>
Signed-off-by: Eric Sandeen <sandeen@sandeen.net>

diff --git a/libxfs/xfs_btree.c b/libxfs/xfs_btree.c
index 1c6f02ada3d128b6f8330938d5adb02a91055d33..3c624ddcd546e590901c76138825d3ac5aa72cf0 100644 (file)
--- a/libxfs/xfs_btree.c
+++ b/libxfs/xfs_btree.c
@@ -48,6 +48,52 @@ xfs_btree_magic(
        return magic;
 }
 
+static xfs_failaddr_t
+xfs_btree_check_lblock_siblings(
+       struct xfs_mount        *mp,
+       struct xfs_btree_cur    *cur,
+       int                     level,
+       xfs_fsblock_t           fsb,
+       xfs_fsblock_t           sibling)
+{
+       if (sibling == NULLFSBLOCK)
+               return NULL;
+       if (sibling == fsb)
+               return __this_address;
+       if (level >= 0) {
+               if (!xfs_btree_check_lptr(cur, sibling, level + 1))
+                       return __this_address;
+       } else {
+               if (!xfs_verify_fsbno(mp, sibling))
+                       return __this_address;
+       }
+
+       return NULL;
+}
+
+static xfs_failaddr_t
+xfs_btree_check_sblock_siblings(
+       struct xfs_mount        *mp,
+       struct xfs_btree_cur    *cur,
+       int                     level,
+       xfs_agnumber_t          agno,
+       xfs_agblock_t           agbno,
+       xfs_agblock_t           sibling)
+{
+       if (sibling == NULLAGBLOCK)
+               return NULL;
+       if (sibling == agbno)
+               return __this_address;
+       if (level >= 0) {
+               if (!xfs_btree_check_sptr(cur, sibling, level + 1))
+                       return __this_address;
+       } else {
+               if (!xfs_verify_agbno(mp, agno, sibling))
+                       return __this_address;
+       }
+       return NULL;
+}
+
 /*
  * Check a long btree block header.  Return the address of the failing check,
  * or NULL if everything is ok.
@@ -62,6 +108,8 @@ __xfs_btree_check_lblock(
        struct xfs_mount        *mp = cur->bc_mp;
        xfs_btnum_t             btnum = cur->bc_btnum;
        int                     crc = xfs_has_crc(mp);
+       xfs_failaddr_t          fa;
+       xfs_fsblock_t           fsb = NULLFSBLOCK;
 
        if (crc) {
                if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid))
@@ -80,16 +128,16 @@ __xfs_btree_check_lblock(
        if (be16_to_cpu(block->bb_numrecs) >
            cur->bc_ops->get_maxrecs(cur, level))
                return __this_address;
-       if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) &&
-           !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_leftsib),
-                       level + 1))
-               return __this_address;
-       if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) &&
-           !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_rightsib),
-                       level + 1))
-               return __this_address;
 
-       return NULL;
+       if (bp)
+               fsb = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
+
+       fa = xfs_btree_check_lblock_siblings(mp, cur, level, fsb,
+                       be64_to_cpu(block->bb_u.l.bb_leftsib));
+       if (!fa)
+               fa = xfs_btree_check_lblock_siblings(mp, cur, level, fsb,
+                               be64_to_cpu(block->bb_u.l.bb_rightsib));
+       return fa;
 }
 
 /* Check a long btree block header. */
@@ -127,6 +175,9 @@ __xfs_btree_check_sblock(
        struct xfs_mount        *mp = cur->bc_mp;
        xfs_btnum_t             btnum = cur->bc_btnum;
        int                     crc = xfs_has_crc(mp);
+       xfs_failaddr_t          fa;
+       xfs_agblock_t           agbno = NULLAGBLOCK;
+       xfs_agnumber_t          agno = NULLAGNUMBER;
 
        if (crc) {
                if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid))
@@ -143,16 +194,18 @@ __xfs_btree_check_sblock(
        if (be16_to_cpu(block->bb_numrecs) >
            cur->bc_ops->get_maxrecs(cur, level))
                return __this_address;
-       if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) &&
-           !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_leftsib),
-                       level + 1))
-               return __this_address;
-       if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) &&
-           !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_rightsib),
-                       level + 1))
-               return __this_address;
 
-       return NULL;
+       if (bp) {
+               agbno = xfs_daddr_to_agbno(mp, xfs_buf_daddr(bp));
+               agno = xfs_daddr_to_agno(mp, xfs_buf_daddr(bp));
+       }
+
+       fa = xfs_btree_check_sblock_siblings(mp, cur, level, agno, agbno,
+                       be32_to_cpu(block->bb_u.s.bb_leftsib));
+       if (!fa)
+               fa = xfs_btree_check_sblock_siblings(mp, cur, level, agno,
+                                agbno, be32_to_cpu(block->bb_u.s.bb_rightsib));
+       return fa;
 }
 
 /* Check a short btree block header. */
@@ -4268,6 +4321,21 @@ xfs_btree_visit_block(
        if (xfs_btree_ptr_is_null(cur, &rptr))
                return -ENOENT;
 
+       /*
+        * We only visit blocks once in this walk, so we have to avoid the
+        * internal xfs_btree_lookup_get_block() optimisation where it will
+        * return the same block without checking if the right sibling points
+        * back to us and creates a cyclic reference in the btree.
+        */
+       if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
+               if (be64_to_cpu(rptr.l) == XFS_DADDR_TO_FSB(cur->bc_mp,
+                                                       xfs_buf_daddr(bp)))
+                       return -EFSCORRUPTED;
+       } else {
+               if (be32_to_cpu(rptr.s) == xfs_daddr_to_agbno(cur->bc_mp,
+                                                       xfs_buf_daddr(bp)))
+                       return -EFSCORRUPTED;
+       }
        return xfs_btree_lookup_get_block(cur, level, &rptr, &block);
 }
 
@@ -4442,20 +4510,21 @@ xfs_btree_lblock_verify(
 {
        struct xfs_mount        *mp = bp->b_mount;
        struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
+       xfs_fsblock_t           fsb;
+       xfs_failaddr_t          fa;
 
        /* numrecs verification */
        if (be16_to_cpu(block->bb_numrecs) > max_recs)
                return __this_address;
 
        /* sibling pointer verification */
-       if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) &&
-           !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_leftsib)))
-               return __this_address;
-       if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) &&
-           !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_rightsib)))
-               return __this_address;
-
-       return NULL;
+       fsb = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
+       fa = xfs_btree_check_lblock_siblings(mp, NULL, -1, fsb,
+                       be64_to_cpu(block->bb_u.l.bb_leftsib));
+       if (!fa)
+               fa = xfs_btree_check_lblock_siblings(mp, NULL, -1, fsb,
+                               be64_to_cpu(block->bb_u.l.bb_rightsib));
+       return fa;
 }
 
 /**
@@ -4496,7 +4565,9 @@ xfs_btree_sblock_verify(
 {
        struct xfs_mount        *mp = bp->b_mount;
        struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
-       xfs_agblock_t           agno;
+       xfs_agnumber_t          agno;
+       xfs_agblock_t           agbno;
+       xfs_failaddr_t          fa;
 
        /* numrecs verification */
        if (be16_to_cpu(block->bb_numrecs) > max_recs)
@@ -4504,14 +4575,13 @@ xfs_btree_sblock_verify(
 
        /* sibling pointer verification */
        agno = xfs_daddr_to_agno(mp, xfs_buf_daddr(bp));
-       if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) &&
-           !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_leftsib)))
-               return __this_address;
-       if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) &&
-           !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_rightsib)))
-               return __this_address;
-
-       return NULL;
+       agbno = xfs_daddr_to_agbno(mp, xfs_buf_daddr(bp));
+       fa = xfs_btree_check_sblock_siblings(mp, NULL, -1, agno, agbno,
+                       be32_to_cpu(block->bb_u.s.bb_leftsib));
+       if (!fa)
+               fa = xfs_btree_check_sblock_siblings(mp, NULL, -1, agno, agbno,
+                               be32_to_cpu(block->bb_u.s.bb_rightsib));
+       return fa;
 }
 
 /*