// SPDX-License-Identifier: GPL-2.0+
/*
 * Copyright (C) 2017 Oracle.  All Rights Reserved.
 * Author: Darrick J. Wong <darrick.wong@oracle.com>
 */
#include "xfs.h"
#include "xfs_fs.h"
#include "xfs_shared.h"
#include "xfs_format.h"
#include "xfs_trans_resv.h"
#include "xfs_mount.h"
#include "xfs_defer.h"
#include "xfs_btree.h"
#include "xfs_bit.h"
#include "xfs_log_format.h"
#include "xfs_trans.h"
#include "xfs_sb.h"
#include "xfs_inode.h"
#include "xfs_alloc.h"
#include "scrub/scrub.h"
#include "scrub/common.h"
#include "scrub/btree.h"
#include "scrub/trace.h"

/* btree scrubbing */

/*
 * Check for btree operation errors.  See the section about handling
 * operational errors in common.c.
 */
static bool
__xchk_btree_process_error(
        struct xfs_scrub        *sc,
        struct xfs_btree_cur    *cur,
        int                     level,
        int                     *error,
        __u32                   errflag,
        void                    *ret_ip)
{
        if (*error == 0)
                return true;

        switch (*error) {
        case -EDEADLOCK:
                /* Used to restart an op with deadlock avoidance. */
                trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
                break;
        case -EFSBADCRC:
        case -EFSCORRUPTED:
                /* Note the badness but don't abort. */
                sc->sm->sm_flags |= errflag;
                *error = 0;
                /* fall through */
        default:
                if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
                        trace_xchk_ifork_btree_op_error(sc, cur, level,
                                        *error, ret_ip);
                else
                        trace_xchk_btree_op_error(sc, cur, level,
                                        *error, ret_ip);
                break;
        }
        return false;
}

bool
xchk_btree_process_error(
        struct xfs_scrub        *sc,
        struct xfs_btree_cur    *cur,
        int                     level,
        int                     *error)
{
        return __xchk_btree_process_error(sc, cur, level, error,
                        XFS_SCRUB_OFLAG_CORRUPT, __return_address);
}

bool
xchk_btree_xref_process_error(
        struct xfs_scrub        *sc,
        struct xfs_btree_cur    *cur,
        int                     level,
        int                     *error)
{
        return __xchk_btree_process_error(sc, cur, level, error,
                        XFS_SCRUB_OFLAG_XFAIL, __return_address);
}

/* Record btree block corruption. */
static void
__xchk_btree_set_corrupt(
        struct xfs_scrub        *sc,
        struct xfs_btree_cur    *cur,
        int                     level,
        __u32                   errflag,
        void                    *ret_ip)
{
        sc->sm->sm_flags |= errflag;

        if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
                trace_xchk_ifork_btree_error(sc, cur, level,
                                ret_ip);
        else
                trace_xchk_btree_error(sc, cur, level,
                                ret_ip);
}

void
xchk_btree_set_corrupt(
        struct xfs_scrub        *sc,
        struct xfs_btree_cur    *cur,
        int                     level)
{
        __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT,
                        __return_address);
}

void
xchk_btree_xref_set_corrupt(
        struct xfs_scrub        *sc,
        struct xfs_btree_cur    *cur,
        int                     level)
{
        __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT,
                        __return_address);
}

/*
 * Make sure this record is in order and doesn't stray outside of the parent
 * keys.
 */
STATIC void
xchk_btree_rec(
        struct xchk_btree       *bs)
{
        struct xfs_btree_cur    *cur = bs->cur;
        union xfs_btree_rec     *rec;
        union xfs_btree_key     key;
        union xfs_btree_key     hkey;
        union xfs_btree_key     *keyp;
        struct xfs_btree_block  *block;
        struct xfs_btree_block  *keyblock;
        struct xfs_buf          *bp;

        block = xfs_btree_get_block(cur, 0, &bp);
        rec = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block);

        trace_xchk_btree_rec(bs->sc, cur, 0);

        /* If this isn't the first record, are they in order? */
        if (!bs->firstrec && !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
                xchk_btree_set_corrupt(bs->sc, cur, 0);
        bs->firstrec = false;
        memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);

        if (cur->bc_nlevels == 1)
                return;

        /* Is this at least as large as the parent low key? */
        cur->bc_ops->init_key_from_rec(&key, rec);
        keyblock = xfs_btree_get_block(cur, 1, &bp);
        keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[1], keyblock);
        if (cur->bc_ops->diff_two_keys(cur, &key, keyp) < 0)
                xchk_btree_set_corrupt(bs->sc, cur, 1);

        if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
                return;

        /* Is this no larger than the parent high key? */
        cur->bc_ops->init_high_key_from_rec(&hkey, rec);
        keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[1], keyblock);
        if (cur->bc_ops->diff_two_keys(cur, keyp, &hkey) < 0)
                xchk_btree_set_corrupt(bs->sc, cur, 1);
}

/*
 * Make sure this key is in order and doesn't stray outside of the parent
 * keys.
 */
STATIC void
xchk_btree_key(
        struct xchk_btree       *bs,
        int                     level)
{
        struct xfs_btree_cur    *cur = bs->cur;
        union xfs_btree_key     *key;
        union xfs_btree_key     *keyp;
        struct xfs_btree_block  *block;
        struct xfs_btree_block  *keyblock;
        struct xfs_buf          *bp;

        block = xfs_btree_get_block(cur, level, &bp);
        key = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block);

        trace_xchk_btree_key(bs->sc, cur, level);

        /* If this isn't the first key, are they in order? */
        if (!bs->firstkey[level] &&
            !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level], key))
                xchk_btree_set_corrupt(bs->sc, cur, level);
        bs->firstkey[level] = false;
        memcpy(&bs->lastkey[level], key, cur->bc_ops->key_len);

        if (level + 1 >= cur->bc_nlevels)
                return;

        /* Is this at least as large as the parent low key? */
        keyblock = xfs_btree_get_block(cur, level + 1, &bp);
        keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1], keyblock);
        if (cur->bc_ops->diff_two_keys(cur, key, keyp) < 0)
                xchk_btree_set_corrupt(bs->sc, cur, level);

        if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
                return;

        /* Is this no larger than the parent high key? */
        key = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block);
        keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1], keyblock);
        if (cur->bc_ops->diff_two_keys(cur, keyp, key) < 0)
                xchk_btree_set_corrupt(bs->sc, cur, level);
}

/*
 * Check a btree pointer.  Returns true if it's ok to use this pointer.
 * Callers do not need to set the corrupt flag.
 */
static bool
xchk_btree_ptr_ok(
        struct xchk_btree       *bs,
        int                     level,
        union xfs_btree_ptr     *ptr)
{
        bool                    res;

        /* A btree rooted in an inode has no block pointer to the root. */
        if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
            level == bs->cur->bc_nlevels)
                return true;

        /* Otherwise, check the pointers. */
        if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
                res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
        else
                res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
        if (!res)
                xchk_btree_set_corrupt(bs->sc, bs->cur, level);

        return res;
}

/* Check that a btree block's sibling matches what we expect it. */
STATIC int
xchk_btree_block_check_sibling(
        struct xchk_btree       *bs,
        int                     level,
        int                     direction,
        union xfs_btree_ptr     *sibling)
{
        struct xfs_btree_cur    *cur = bs->cur;
        struct xfs_btree_block  *pblock;
        struct xfs_buf          *pbp;
        struct xfs_btree_cur    *ncur = NULL;
        union xfs_btree_ptr     *pp;
        int                     success;
        int                     error;

        error = xfs_btree_dup_cursor(cur, &ncur);
        if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
            !ncur)
                return error;

        /*
         * If the pointer is null, we shouldn't be able to move the upper
         * level pointer anywhere.
         */
        if (xfs_btree_ptr_is_null(cur, sibling)) {
                if (direction > 0)
                        error = xfs_btree_increment(ncur, level + 1, &success);
                else
                        error = xfs_btree_decrement(ncur, level + 1, &success);
                if (error == 0 && success)
                        xchk_btree_set_corrupt(bs->sc, cur, level);
                error = 0;
                goto out;
        }

        /* Increment upper level pointer. */
        if (direction > 0)
                error = xfs_btree_increment(ncur, level + 1, &success);
        else
                error = xfs_btree_decrement(ncur, level + 1, &success);
        if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
                goto out;
        if (!success) {
                xchk_btree_set_corrupt(bs->sc, cur, level + 1);
                goto out;
        }

        /* Compare upper level pointer to sibling pointer. */
        pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
        pp = xfs_btree_ptr_addr(ncur, ncur->bc_ptrs[level + 1], pblock);
        if (!xchk_btree_ptr_ok(bs, level + 1, pp))
                goto out;
        if (pbp)
                xchk_buffer_recheck(bs->sc, pbp);

        if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
                xchk_btree_set_corrupt(bs->sc, cur, level);
out:
        xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
        return error;
}

/* Check the siblings of a btree block. */
STATIC int
xchk_btree_block_check_siblings(
        struct xchk_btree       *bs,
        struct xfs_btree_block  *block)
{
        struct xfs_btree_cur    *cur = bs->cur;
        union xfs_btree_ptr     leftsib;
        union xfs_btree_ptr     rightsib;
        int                     level;
        int                     error = 0;

        xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
        xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
        level = xfs_btree_get_level(block);

        /* Root block should never have siblings. */
        if (level == cur->bc_nlevels - 1) {
                if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
                    !xfs_btree_ptr_is_null(cur, &rightsib))
                        xchk_btree_set_corrupt(bs->sc, cur, level);
                goto out;
        }

        /*
         * Does the left & right sibling pointers match the adjacent
         * parent level pointers?
         * (These function absorbs error codes for us.)
         */
        error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
        if (error)
                return error;
        error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
        if (error)
                return error;
out:
        return error;
}

struct check_owner {
        struct list_head        list;
        xfs_daddr_t             daddr;
        int                     level;
};

/*
 * Make sure this btree block isn't in the free list and that there's
 * an rmap record for it.
 */
STATIC int
xchk_btree_check_block_owner(
        struct xchk_btree       *bs,
        int                     level,
        xfs_daddr_t             daddr)
{
        xfs_agnumber_t          agno;
        xfs_agblock_t           agbno;
        xfs_btnum_t             btnum;
        bool                    init_sa;
        int                     error = 0;

        if (!bs->cur)
                return 0;

        btnum = bs->cur->bc_btnum;
        agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
        agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);

        init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS;
        if (init_sa) {
                error = xchk_ag_init(bs->sc, agno, &bs->sc->sa);
                if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
                                level, &error))
                        return error;
        }

        xchk_xref_is_used_space(bs->sc, agbno, 1);
        /*
         * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we
         * have to nullify it (to shut down further block owner checks) if
         * self-xref encounters problems.
         */
        if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO)
                bs->cur = NULL;

        xchk_xref_is_owned_by(bs->sc, agbno, 1, bs->oinfo);
        if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP)
                bs->cur = NULL;

        if (init_sa)
                xchk_ag_free(bs->sc, &bs->sc->sa);

        return error;
}

/* Check the owner of a btree block. */
STATIC int
xchk_btree_check_owner(
        struct xchk_btree       *bs,
        int                     level,
        struct xfs_buf          *bp)
{
        struct xfs_btree_cur    *cur = bs->cur;
        struct check_owner      *co;

        /*
         * In theory, xfs_btree_get_block should only give us a null buffer
         * pointer for the root of a root-in-inode btree type, but we need
         * to check defensively here in case the cursor state is also screwed
         * up.
         */
        if (bp == NULL) {
                if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
                        xchk_btree_set_corrupt(bs->sc, bs->cur, level);
                return 0;
        }

        /*
         * We want to cross-reference each btree block with the bnobt
         * and the rmapbt.  We cannot cross-reference the bnobt or
         * rmapbt while scanning the bnobt or rmapbt, respectively,
         * because we cannot alter the cursor and we'd prefer not to
         * duplicate cursors.  Therefore, save the buffer daddr for
         * later scanning.
         */
        if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) {
                co = kmem_alloc(sizeof(struct check_owner),
                                KM_MAYFAIL);
                if (!co)
                        return -ENOMEM;
                co->level = level;
                co->daddr = XFS_BUF_ADDR(bp);
                list_add_tail(&co->list, &bs->to_check);
                return 0;
        }

        return xchk_btree_check_block_owner(bs, level, XFS_BUF_ADDR(bp));
}

/*
 * Check that this btree block has at least minrecs records or is one of the
 * special blocks that don't require that.
 */
STATIC void
xchk_btree_check_minrecs(
        struct xchk_btree       *bs,
        int                     level,
        struct xfs_btree_block  *block)
{
        unsigned int            numrecs;
        int                     ok_level;

        numrecs = be16_to_cpu(block->bb_numrecs);

        /* More records than minrecs means the block is ok. */
        if (numrecs >= bs->cur->bc_ops->get_minrecs(bs->cur, level))
                return;

        /*
         * Certain btree blocks /can/ have fewer than minrecs records.  Any
         * level greater than or equal to the level of the highest dedicated
         * btree block are allowed to violate this constraint.
         *
         * For a btree rooted in a block, the btree root can have fewer than
         * minrecs records.  If the btree is rooted in an inode and does not
         * store records in the root, the direct children of the root and the
         * root itself can have fewer than minrecs records.
         */
        ok_level = bs->cur->bc_nlevels - 1;
        if (bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
                ok_level--;
        if (level >= ok_level)
                return;

        xchk_btree_set_corrupt(bs->sc, bs->cur, level);
}

/*
 * Grab and scrub a btree block given a btree pointer.  Returns block
 * and buffer pointers (if applicable) if they're ok to use.
 */
STATIC int
xchk_btree_get_block(
        struct xchk_btree       *bs,
        int                     level,
        union xfs_btree_ptr     *pp,
        struct xfs_btree_block  **pblock,
        struct xfs_buf          **pbp)
{
        xfs_failaddr_t          failed_at;
        int                     error;

        *pblock = NULL;
        *pbp = NULL;

        error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
        if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
            !*pblock)
                return error;

        xfs_btree_get_block(bs->cur, level, pbp);
        if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
                failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
                                level, *pbp);
        else
                failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
                                 level, *pbp);
        if (failed_at) {
                xchk_btree_set_corrupt(bs->sc, bs->cur, level);
                return 0;
        }
        if (*pbp)
                xchk_buffer_recheck(bs->sc, *pbp);

        xchk_btree_check_minrecs(bs, level, *pblock);

        /*
         * Check the block's owner; this function absorbs error codes
         * for us.
         */
        error = xchk_btree_check_owner(bs, level, *pbp);
        if (error)
                return error;

        /*
         * Check the block's siblings; this function absorbs error codes
         * for us.
         */
        return xchk_btree_block_check_siblings(bs, *pblock);
}

/*
 * Check that the low and high keys of this block match the keys stored
 * in the parent block.
 */
STATIC void
xchk_btree_block_keys(
        struct xchk_btree       *bs,
        int                     level,
        struct xfs_btree_block  *block)
{
        union xfs_btree_key     block_keys;
        struct xfs_btree_cur    *cur = bs->cur;
        union xfs_btree_key     *high_bk;
        union xfs_btree_key     *parent_keys;
        union xfs_btree_key     *high_pk;
        struct xfs_btree_block  *parent_block;
        struct xfs_buf          *bp;

        if (level >= cur->bc_nlevels - 1)
                return;

        /* Calculate the keys for this block. */
        xfs_btree_get_keys(cur, block, &block_keys);

        /* Obtain the parent's copy of the keys for this block. */
        parent_block = xfs_btree_get_block(cur, level + 1, &bp);
        parent_keys = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1],
                        parent_block);

        if (cur->bc_ops->diff_two_keys(cur, &block_keys, parent_keys) != 0)
                xchk_btree_set_corrupt(bs->sc, cur, 1);

        if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
                return;

        /* Get high keys */
        high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
        high_pk = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1],
                        parent_block);

        if (cur->bc_ops->diff_two_keys(cur, high_bk, high_pk) != 0)
                xchk_btree_set_corrupt(bs->sc, cur, 1);
}

/*
 * Visit all nodes and leaves of a btree.  Check that all pointers and
 * records are in order, that the keys reflect the records, and use a callback
 * so that the caller can verify individual records.
 */
int
xchk_btree(
        struct xfs_scrub                *sc,
        struct xfs_btree_cur            *cur,
        xchk_btree_rec_fn               scrub_fn,
        const struct xfs_owner_info     *oinfo,
        void                            *private)
{
        struct xchk_btree               bs = {
                .cur                    = cur,
                .scrub_rec              = scrub_fn,
                .oinfo                  = oinfo,
                .firstrec               = true,
                .private                = private,
                .sc                     = sc,
        };
        union xfs_btree_ptr             ptr;
        union xfs_btree_ptr             *pp;
        union xfs_btree_rec             *recp;
        struct xfs_btree_block          *block;
        int                             level;
        struct xfs_buf                  *bp;
        struct check_owner              *co;
        struct check_owner              *n;
        int                             i;
        int                             error = 0;

        /* Initialize scrub state */
        for (i = 0; i < XFS_BTREE_MAXLEVELS; i++)
                bs.firstkey[i] = true;
        INIT_LIST_HEAD(&bs.to_check);

        /* Don't try to check a tree with a height we can't handle. */
        if (cur->bc_nlevels > XFS_BTREE_MAXLEVELS) {
                xchk_btree_set_corrupt(sc, cur, 0);
                goto out;
        }

        /*
         * Load the root of the btree.  The helper function absorbs
         * error codes for us.
         */
        level = cur->bc_nlevels - 1;
        cur->bc_ops->init_ptr_from_cur(cur, &ptr);
        if (!xchk_btree_ptr_ok(&bs, cur->bc_nlevels, &ptr))
                goto out;
        error = xchk_btree_get_block(&bs, level, &ptr, &block, &bp);
        if (error || !block)
                goto out;

        cur->bc_ptrs[level] = 1;

        while (level < cur->bc_nlevels) {
                block = xfs_btree_get_block(cur, level, &bp);

                if (level == 0) {
                        /* End of leaf, pop back towards the root. */
                        if (cur->bc_ptrs[level] >
                            be16_to_cpu(block->bb_numrecs)) {
                                xchk_btree_block_keys(&bs, level, block);
                                if (level < cur->bc_nlevels - 1)
                                        cur->bc_ptrs[level + 1]++;
                                level++;
                                continue;
                        }

                        /* Records in order for scrub? */
                        xchk_btree_rec(&bs);

                        /* Call out to the record checker. */
                        recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block);
                        error = bs.scrub_rec(&bs, recp);
                        if (error)
                                break;
                        if (xchk_should_terminate(sc, &error) ||
                            (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
                                break;

                        cur->bc_ptrs[level]++;
                        continue;
                }

                /* End of node, pop back towards the root. */
                if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) {
                        xchk_btree_block_keys(&bs, level, block);
                        if (level < cur->bc_nlevels - 1)
                                cur->bc_ptrs[level + 1]++;
                        level++;
                        continue;
                }

                /* Keys in order for scrub? */
                xchk_btree_key(&bs, level);

                /* Drill another level deeper. */
                pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block);
                if (!xchk_btree_ptr_ok(&bs, level, pp)) {
                        cur->bc_ptrs[level]++;
                        continue;
                }
                level--;
                error = xchk_btree_get_block(&bs, level, pp, &block, &bp);
                if (error || !block)
                        goto out;

                cur->bc_ptrs[level] = 1;
        }

out:
        /* Process deferred owner checks on btree blocks. */
        list_for_each_entry_safe(co, n, &bs.to_check, list) {
                if (!error && bs.cur)
                        error = xchk_btree_check_block_owner(&bs,
                                        co->level, co->daddr);
                list_del(&co->list);
                kmem_free(co);
        }

        return error;
}