[people/ms/linux.git] / fs / xfs / scrub / dabtree.c

// 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_log_format.h"
#include "xfs_trans.h"
#include "xfs_inode.h"
#include "xfs_dir2.h"
#include "xfs_dir2_priv.h"
#include "xfs_attr_leaf.h"
#include "scrub/scrub.h"
#include "scrub/common.h"
#include "scrub/trace.h"
#include "scrub/dabtree.h"

/* Directory/Attribute Btree */

/*
 * Check for da btree operation errors.  See the section about handling
 * operational errors in common.c.
 */
bool
xchk_da_process_error(
	struct xchk_da_btree	*ds,
	int			level,
	int			*error)
{
	struct xfs_scrub	*sc = ds->sc;

	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 |= XFS_SCRUB_OFLAG_CORRUPT;
		*error = 0;
		fallthrough;
	default:
		trace_xchk_file_op_error(sc, ds->dargs.whichfork,
				xfs_dir2_da_to_db(ds->dargs.geo,
					ds->state->path.blk[level].blkno),
				*error, __return_address);
		break;
	}
	return false;
}

/*
 * Check for da btree corruption.  See the section about handling
 * operational errors in common.c.
 */
void
xchk_da_set_corrupt(
	struct xchk_da_btree	*ds,
	int			level)
{
	struct xfs_scrub	*sc = ds->sc;

	sc->sm->sm_flags |= XFS_SCRUB_OFLAG_CORRUPT;

	trace_xchk_fblock_error(sc, ds->dargs.whichfork,
			xfs_dir2_da_to_db(ds->dargs.geo,
				ds->state->path.blk[level].blkno),
			__return_address);
}

static struct xfs_da_node_entry *
xchk_da_btree_node_entry(
	struct xchk_da_btree		*ds,
	int				level)
{
	struct xfs_da_state_blk		*blk = &ds->state->path.blk[level];
	struct xfs_da3_icnode_hdr	hdr;

	ASSERT(blk->magic == XFS_DA_NODE_MAGIC);

	xfs_da3_node_hdr_from_disk(ds->sc->mp, &hdr, blk->bp->b_addr);
	return hdr.btree + blk->index;
}

/* Scrub a da btree hash (key). */
int
xchk_da_btree_hash(
	struct xchk_da_btree		*ds,
	int				level,
	__be32				*hashp)
{
	struct xfs_da_node_entry	*entry;
	xfs_dahash_t			hash;
	xfs_dahash_t			parent_hash;

	/* Is this hash in order? */
	hash = be32_to_cpu(*hashp);
	if (hash < ds->hashes[level])
		xchk_da_set_corrupt(ds, level);
	ds->hashes[level] = hash;

	if (level == 0)
		return 0;

	/* Is this hash no larger than the parent hash? */
	entry = xchk_da_btree_node_entry(ds, level - 1);
	parent_hash = be32_to_cpu(entry->hashval);
	if (parent_hash < hash)
		xchk_da_set_corrupt(ds, level);

	return 0;
}

/*
 * Check a da btree pointer.  Returns true if it's ok to use this
 * pointer.
 */
STATIC bool
xchk_da_btree_ptr_ok(
	struct xchk_da_btree	*ds,
	int			level,
	xfs_dablk_t		blkno)
{
	if (blkno < ds->lowest || (ds->highest != 0 && blkno >= ds->highest)) {
		xchk_da_set_corrupt(ds, level);
		return false;
	}

	return true;
}

/*
 * The da btree scrubber can handle leaf1 blocks as a degenerate
 * form of leafn blocks.  Since the regular da code doesn't handle
 * leaf1, we must multiplex the verifiers.
 */
static void
xchk_da_btree_read_verify(
	struct xfs_buf		*bp)
{
	struct xfs_da_blkinfo	*info = bp->b_addr;

	switch (be16_to_cpu(info->magic)) {
	case XFS_DIR2_LEAF1_MAGIC:
	case XFS_DIR3_LEAF1_MAGIC:
		bp->b_ops = &xfs_dir3_leaf1_buf_ops;
		bp->b_ops->verify_read(bp);
		return;
	default:
		/*
		 * xfs_da3_node_buf_ops already know how to handle
		 * DA*_NODE, ATTR*_LEAF, and DIR*_LEAFN blocks.
		 */
		bp->b_ops = &xfs_da3_node_buf_ops;
		bp->b_ops->verify_read(bp);
		return;
	}
}
static void
xchk_da_btree_write_verify(
	struct xfs_buf		*bp)
{
	struct xfs_da_blkinfo	*info = bp->b_addr;

	switch (be16_to_cpu(info->magic)) {
	case XFS_DIR2_LEAF1_MAGIC:
	case XFS_DIR3_LEAF1_MAGIC:
		bp->b_ops = &xfs_dir3_leaf1_buf_ops;
		bp->b_ops->verify_write(bp);
		return;
	default:
		/*
		 * xfs_da3_node_buf_ops already know how to handle
		 * DA*_NODE, ATTR*_LEAF, and DIR*_LEAFN blocks.
		 */
		bp->b_ops = &xfs_da3_node_buf_ops;
		bp->b_ops->verify_write(bp);
		return;
	}
}
static void *
xchk_da_btree_verify(
	struct xfs_buf		*bp)
{
	struct xfs_da_blkinfo	*info = bp->b_addr;

	switch (be16_to_cpu(info->magic)) {
	case XFS_DIR2_LEAF1_MAGIC:
	case XFS_DIR3_LEAF1_MAGIC:
		bp->b_ops = &xfs_dir3_leaf1_buf_ops;
		return bp->b_ops->verify_struct(bp);
	default:
		bp->b_ops = &xfs_da3_node_buf_ops;
		return bp->b_ops->verify_struct(bp);
	}
}

static const struct xfs_buf_ops xchk_da_btree_buf_ops = {
	.name = "xchk_da_btree",
	.verify_read = xchk_da_btree_read_verify,
	.verify_write = xchk_da_btree_write_verify,
	.verify_struct = xchk_da_btree_verify,
};

/* Check a block's sibling. */
STATIC int
xchk_da_btree_block_check_sibling(
	struct xchk_da_btree	*ds,
	int			level,
	int			direction,
	xfs_dablk_t		sibling)
{
	struct xfs_da_state_path *path = &ds->state->path;
	struct xfs_da_state_path *altpath = &ds->state->altpath;
	int			retval;
	int			plevel;
	int			error;

	memcpy(altpath, path, sizeof(ds->state->altpath));

	/*
	 * If the pointer is null, we shouldn't be able to move the upper
	 * level pointer anywhere.
	 */
	if (sibling == 0) {
		error = xfs_da3_path_shift(ds->state, altpath, direction,
				false, &retval);
		if (error == 0 && retval == 0)
			xchk_da_set_corrupt(ds, level);
		error = 0;
		goto out;
	}

	/* Move the alternate cursor one block in the direction given. */
	error = xfs_da3_path_shift(ds->state, altpath, direction, false,
			&retval);
	if (!xchk_da_process_error(ds, level, &error))
		goto out;
	if (retval) {
		xchk_da_set_corrupt(ds, level);
		goto out;
	}
	if (altpath->blk[level].bp)
		xchk_buffer_recheck(ds->sc, altpath->blk[level].bp);

	/* Compare upper level pointer to sibling pointer. */
	if (altpath->blk[level].blkno != sibling)
		xchk_da_set_corrupt(ds, level);

out:
	/* Free all buffers in the altpath that aren't referenced from path. */
	for (plevel = 0; plevel < altpath->active; plevel++) {
		if (altpath->blk[plevel].bp == NULL ||
		    (plevel < path->active &&
		     altpath->blk[plevel].bp == path->blk[plevel].bp))
			continue;

		xfs_trans_brelse(ds->dargs.trans, altpath->blk[plevel].bp);
		altpath->blk[plevel].bp = NULL;
	}

	return error;
}

/* Check a block's sibling pointers. */
STATIC int
xchk_da_btree_block_check_siblings(
	struct xchk_da_btree	*ds,
	int			level,
	struct xfs_da_blkinfo	*hdr)
{
	xfs_dablk_t		forw;
	xfs_dablk_t		back;
	int			error = 0;

	forw = be32_to_cpu(hdr->forw);
	back = be32_to_cpu(hdr->back);

	/* Top level blocks should not have sibling pointers. */
	if (level == 0) {
		if (forw != 0 || back != 0)
			xchk_da_set_corrupt(ds, level);
		return 0;
	}

	/*
	 * Check back (left) and forw (right) pointers.  These functions
	 * absorb error codes for us.
	 */
	error = xchk_da_btree_block_check_sibling(ds, level, 0, back);
	if (error)
		goto out;
	error = xchk_da_btree_block_check_sibling(ds, level, 1, forw);

out:
	memset(&ds->state->altpath, 0, sizeof(ds->state->altpath));
	return error;
}

/* Load a dir/attribute block from a btree. */
STATIC int
xchk_da_btree_block(
	struct xchk_da_btree		*ds,
	int				level,
	xfs_dablk_t			blkno)
{
	struct xfs_da_state_blk		*blk;
	struct xfs_da_intnode		*node;
	struct xfs_da_node_entry	*btree;
	struct xfs_da3_blkinfo		*hdr3;
	struct xfs_da_args		*dargs = &ds->dargs;
	struct xfs_inode		*ip = ds->dargs.dp;
	xfs_ino_t			owner;
	int				*pmaxrecs;
	struct xfs_da3_icnode_hdr	nodehdr;
	int				error = 0;

	blk = &ds->state->path.blk[level];
	ds->state->path.active = level + 1;

	/* Release old block. */
	if (blk->bp) {
		xfs_trans_brelse(dargs->trans, blk->bp);
		blk->bp = NULL;
	}

	/* Check the pointer. */
	blk->blkno = blkno;
	if (!xchk_da_btree_ptr_ok(ds, level, blkno))
		goto out_nobuf;

	/* Read the buffer. */
	error = xfs_da_read_buf(dargs->trans, dargs->dp, blk->blkno,
			XFS_DABUF_MAP_HOLE_OK, &blk->bp, dargs->whichfork,
			&xchk_da_btree_buf_ops);
	if (!xchk_da_process_error(ds, level, &error))
		goto out_nobuf;
	if (blk->bp)
		xchk_buffer_recheck(ds->sc, blk->bp);

	/*
	 * We didn't find a dir btree root block, which means that
	 * there's no LEAF1/LEAFN tree (at least not where it's supposed
	 * to be), so jump out now.
	 */
	if (ds->dargs.whichfork == XFS_DATA_FORK && level == 0 &&
			blk->bp == NULL)
		goto out_nobuf;

	/* It's /not/ ok for attr trees not to have a da btree. */
	if (blk->bp == NULL) {
		xchk_da_set_corrupt(ds, level);
		goto out_nobuf;
	}

	hdr3 = blk->bp->b_addr;
	blk->magic = be16_to_cpu(hdr3->hdr.magic);
	pmaxrecs = &ds->maxrecs[level];

	/* We only started zeroing the header on v5 filesystems. */
	if (xfs_has_crc(ds->sc->mp) && hdr3->hdr.pad)
		xchk_da_set_corrupt(ds, level);

	/* Check the owner. */
	if (xfs_has_crc(ip->i_mount)) {
		owner = be64_to_cpu(hdr3->owner);
		if (owner != ip->i_ino)
			xchk_da_set_corrupt(ds, level);
	}

	/* Check the siblings. */
	error = xchk_da_btree_block_check_siblings(ds, level, &hdr3->hdr);
	if (error)
		goto out;

	/* Interpret the buffer. */
	switch (blk->magic) {
	case XFS_ATTR_LEAF_MAGIC:
	case XFS_ATTR3_LEAF_MAGIC:
		xfs_trans_buf_set_type(dargs->trans, blk->bp,
				XFS_BLFT_ATTR_LEAF_BUF);
		blk->magic = XFS_ATTR_LEAF_MAGIC;
		blk->hashval = xfs_attr_leaf_lasthash(blk->bp, pmaxrecs);
		if (ds->tree_level != 0)
			xchk_da_set_corrupt(ds, level);
		break;
	case XFS_DIR2_LEAFN_MAGIC:
	case XFS_DIR3_LEAFN_MAGIC:
		xfs_trans_buf_set_type(dargs->trans, blk->bp,
				XFS_BLFT_DIR_LEAFN_BUF);
		blk->magic = XFS_DIR2_LEAFN_MAGIC;
		blk->hashval = xfs_dir2_leaf_lasthash(ip, blk->bp, pmaxrecs);
		if (ds->tree_level != 0)
			xchk_da_set_corrupt(ds, level);
		break;
	case XFS_DIR2_LEAF1_MAGIC:
	case XFS_DIR3_LEAF1_MAGIC:
		xfs_trans_buf_set_type(dargs->trans, blk->bp,
				XFS_BLFT_DIR_LEAF1_BUF);
		blk->magic = XFS_DIR2_LEAF1_MAGIC;
		blk->hashval = xfs_dir2_leaf_lasthash(ip, blk->bp, pmaxrecs);
		if (ds->tree_level != 0)
			xchk_da_set_corrupt(ds, level);
		break;
	case XFS_DA_NODE_MAGIC:
	case XFS_DA3_NODE_MAGIC:
		xfs_trans_buf_set_type(dargs->trans, blk->bp,
				XFS_BLFT_DA_NODE_BUF);
		blk->magic = XFS_DA_NODE_MAGIC;
		node = blk->bp->b_addr;
		xfs_da3_node_hdr_from_disk(ip->i_mount, &nodehdr, node);
		btree = nodehdr.btree;
		*pmaxrecs = nodehdr.count;
		blk->hashval = be32_to_cpu(btree[*pmaxrecs - 1].hashval);
		if (level == 0) {
			if (nodehdr.level >= XFS_DA_NODE_MAXDEPTH) {
				xchk_da_set_corrupt(ds, level);
				goto out_freebp;
			}
			ds->tree_level = nodehdr.level;
		} else {
			if (ds->tree_level != nodehdr.level) {
				xchk_da_set_corrupt(ds, level);
				goto out_freebp;
			}
		}

		/* XXX: Check hdr3.pad32 once we know how to fix it. */
		break;
	default:
		xchk_da_set_corrupt(ds, level);
		goto out_freebp;
	}

	/*
	 * If we've been handed a block that is below the dabtree root, does
	 * its hashval match what the parent block expected to see?
	 */
	if (level > 0) {
		struct xfs_da_node_entry	*key;

		key = xchk_da_btree_node_entry(ds, level - 1);
		if (be32_to_cpu(key->hashval) != blk->hashval) {
			xchk_da_set_corrupt(ds, level);
			goto out_freebp;
		}
	}

out:
	return error;
out_freebp:
	xfs_trans_brelse(dargs->trans, blk->bp);
	blk->bp = NULL;
out_nobuf:
	blk->blkno = 0;
	return error;
}

/* Visit all nodes and leaves of a da btree. */
int
xchk_da_btree(
	struct xfs_scrub		*sc,
	int				whichfork,
	xchk_da_btree_rec_fn		scrub_fn,
	void				*private)
{
	struct xchk_da_btree		*ds;
	struct xfs_mount		*mp = sc->mp;
	struct xfs_da_state_blk		*blks;
	struct xfs_da_node_entry	*key;
	xfs_dablk_t			blkno;
	int				level;
	int				error;

	/* Skip short format data structures; no btree to scan. */
	if (!xfs_ifork_has_extents(xfs_ifork_ptr(sc->ip, whichfork)))
		return 0;

	/* Set up initial da state. */
	ds = kmem_zalloc(sizeof(struct xchk_da_btree), KM_NOFS | KM_MAYFAIL);
	if (!ds)
		return -ENOMEM;
	ds->dargs.dp = sc->ip;
	ds->dargs.whichfork = whichfork;
	ds->dargs.trans = sc->tp;
	ds->dargs.op_flags = XFS_DA_OP_OKNOENT;
	ds->state = xfs_da_state_alloc(&ds->dargs);
	ds->sc = sc;
	ds->private = private;
	if (whichfork == XFS_ATTR_FORK) {
		ds->dargs.geo = mp->m_attr_geo;
		ds->lowest = 0;
		ds->highest = 0;
	} else {
		ds->dargs.geo = mp->m_dir_geo;
		ds->lowest = ds->dargs.geo->leafblk;
		ds->highest = ds->dargs.geo->freeblk;
	}
	blkno = ds->lowest;
	level = 0;

	/* Find the root of the da tree, if present. */
	blks = ds->state->path.blk;
	error = xchk_da_btree_block(ds, level, blkno);
	if (error)
		goto out_state;
	/*
	 * We didn't find a block at ds->lowest, which means that there's
	 * no LEAF1/LEAFN tree (at least not where it's supposed to be),
	 * so jump out now.
	 */
	if (blks[level].bp == NULL)
		goto out_state;

	blks[level].index = 0;
	while (level >= 0 && level < XFS_DA_NODE_MAXDEPTH) {
		/* Handle leaf block. */
		if (blks[level].magic != XFS_DA_NODE_MAGIC) {
			/* End of leaf, pop back towards the root. */
			if (blks[level].index >= ds->maxrecs[level]) {
				if (level > 0)
					blks[level - 1].index++;
				ds->tree_level++;
				level--;
				continue;
			}

			/* Dispatch record scrubbing. */
			error = scrub_fn(ds, level);
			if (error)
				break;
			if (xchk_should_terminate(sc, &error) ||
			    (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
				break;

			blks[level].index++;
			continue;
		}


		/* End of node, pop back towards the root. */
		if (blks[level].index >= ds->maxrecs[level]) {
			if (level > 0)
				blks[level - 1].index++;
			ds->tree_level++;
			level--;
			continue;
		}

		/* Hashes in order for scrub? */
		key = xchk_da_btree_node_entry(ds, level);
		error = xchk_da_btree_hash(ds, level, &key->hashval);
		if (error)
			goto out;

		/* Drill another level deeper. */
		blkno = be32_to_cpu(key->before);
		level++;
		if (level >= XFS_DA_NODE_MAXDEPTH) {
			/* Too deep! */
			xchk_da_set_corrupt(ds, level - 1);
			break;
		}
		ds->tree_level--;
		error = xchk_da_btree_block(ds, level, blkno);
		if (error)
			goto out;
		if (blks[level].bp == NULL)
			goto out;

		blks[level].index = 0;
	}

out:
	/* Release all the buffers we're tracking. */
	for (level = 0; level < XFS_DA_NODE_MAXDEPTH; level++) {
		if (blks[level].bp == NULL)
			continue;
		xfs_trans_brelse(sc->tp, blks[level].bp);
		blks[level].bp = NULL;
	}

out_state:
	xfs_da_state_free(ds->state);
	kmem_free(ds);
	return error;
}
Commit	Line	Data
0b61f8a4	1	// SPDX-License-Identifier: GPL-2.0+
7c4a07a4 DW	2	/*
7c4a07a4 DW	3	* Copyright (C) 2017 Oracle. All Rights Reserved.
7c4a07a4	4	* Author: Darrick J. Wong <darrick.wong@oracle.com>
7c4a07a4 DW	5	*/
	6	#include "xfs.h"
	7	#include "xfs_fs.h"
	8	#include "xfs_shared.h"
	9	#include "xfs_format.h"
	10	#include "xfs_trans_resv.h"
	11	#include "xfs_mount.h"
7c4a07a4 DW	12	#include "xfs_log_format.h"
7c4a07a4 DW	13	#include "xfs_trans.h"
7c4a07a4	14	#include "xfs_inode.h"
7c4a07a4 DW	15	#include "xfs_dir2.h"
	16	#include "xfs_dir2_priv.h"
	17	#include "xfs_attr_leaf.h"
7c4a07a4 DW	18	#include "scrub/scrub.h"
	19	#include "scrub/common.h"
	20	#include "scrub/trace.h"
	21	#include "scrub/dabtree.h"
	22
	23	/* Directory/Attribute Btree */
	24
	25	/*
	26	* Check for da btree operation errors. See the section about handling
	27	* operational errors in common.c.
	28	*/
	29	bool
c517b3aa	30	xchk_da_process_error(
032d91f9 DW	31	struct xchk_da_btree *ds,
	32	int level,
	33	int *error)
7c4a07a4	34	{
1d8a748a	35	struct xfs_scrub *sc = ds->sc;
7c4a07a4 DW	36
	37	if (*error == 0)
	38	return true;
	39
	40	switch (*error) {
	41	case -EDEADLOCK:
	42	/* Used to restart an op with deadlock avoidance. */
c517b3aa	43	trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
7c4a07a4 DW	44	break;
	45	case -EFSBADCRC:
	46	case -EFSCORRUPTED:
	47	/* Note the badness but don't abort. */
	48	sc->sm->sm_flags \|= XFS_SCRUB_OFLAG_CORRUPT;
	49	*error = 0;
53004ee7	50	fallthrough;
7c4a07a4	51	default:
c517b3aa	52	trace_xchk_file_op_error(sc, ds->dargs.whichfork,
7c4a07a4 DW	53	xfs_dir2_da_to_db(ds->dargs.geo,
	54	ds->state->path.blk[level].blkno),
	55	*error, __return_address);
	56	break;
	57	}
	58	return false;
	59	}
	60
	61	/*
	62	* Check for da btree corruption. See the section about handling
	63	* operational errors in common.c.
	64	*/
	65	void
c517b3aa	66	xchk_da_set_corrupt(
032d91f9 DW	67	struct xchk_da_btree *ds,
032d91f9 DW	68	int level)
7c4a07a4	69	{
1d8a748a	70	struct xfs_scrub *sc = ds->sc;
7c4a07a4 DW	71
	72	sc->sm->sm_flags \|= XFS_SCRUB_OFLAG_CORRUPT;
	73
c517b3aa	74	trace_xchk_fblock_error(sc, ds->dargs.whichfork,
7c4a07a4 DW	75	xfs_dir2_da_to_db(ds->dargs.geo,
	76	ds->state->path.blk[level].blkno),
	77	__return_address);
	78	}
	79
649d9d98 CH	80	static struct xfs_da_node_entry *
	81	xchk_da_btree_node_entry(
	82	struct xchk_da_btree *ds,
	83	int level)
7c4a07a4	84	{
649d9d98	85	struct xfs_da_state_blk *blk = &ds->state->path.blk[level];
51908ca7	86	struct xfs_da3_icnode_hdr hdr;
7c4a07a4	87
649d9d98	88	ASSERT(blk->magic == XFS_DA_NODE_MAGIC);
7c4a07a4	89
51908ca7 CH	90	xfs_da3_node_hdr_from_disk(ds->sc->mp, &hdr, blk->bp->b_addr);
51908ca7 CH	91	return hdr.btree + blk->index;
7c4a07a4 DW	92	}
	93
	94	/* Scrub a da btree hash (key). */
	95	int
c517b3aa DW	96	xchk_da_btree_hash(
c517b3aa DW	97	struct xchk_da_btree *ds,
7c4a07a4 DW	98	int level,
	99	__be32 *hashp)
	100	{
7c4a07a4 DW	101	struct xfs_da_node_entry *entry;
	102	xfs_dahash_t hash;
	103	xfs_dahash_t parent_hash;
	104
	105	/* Is this hash in order? */
	106	hash = be32_to_cpu(*hashp);
	107	if (hash < ds->hashes[level])
c517b3aa	108	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	109	ds->hashes[level] = hash;
	110
	111	if (level == 0)
	112	return 0;
	113
	114	/* Is this hash no larger than the parent hash? */
649d9d98	115	entry = xchk_da_btree_node_entry(ds, level - 1);
7c4a07a4 DW	116	parent_hash = be32_to_cpu(entry->hashval);
7c4a07a4 DW	117	if (parent_hash < hash)
c517b3aa	118	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	119
	120	return 0;
	121	}
	122
	123	/*
	124	* Check a da btree pointer. Returns true if it's ok to use this
	125	* pointer.
	126	*/
	127	STATIC bool
c517b3aa	128	xchk_da_btree_ptr_ok(
032d91f9 DW	129	struct xchk_da_btree *ds,
	130	int level,
	131	xfs_dablk_t blkno)
7c4a07a4 DW	132	{
7c4a07a4 DW	133	if (blkno < ds->lowest \|\| (ds->highest != 0 && blkno >= ds->highest)) {
c517b3aa	134	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	135	return false;
	136	}
	137
	138	return true;
	139	}
	140
	141	/*
	142	* The da btree scrubber can handle leaf1 blocks as a degenerate
	143	* form of leafn blocks. Since the regular da code doesn't handle
	144	* leaf1, we must multiplex the verifiers.
	145	*/
	146	static void
c517b3aa	147	xchk_da_btree_read_verify(
7c4a07a4 DW	148	struct xfs_buf *bp)
	149	{
	150	struct xfs_da_blkinfo *info = bp->b_addr;
	151
	152	switch (be16_to_cpu(info->magic)) {
	153	case XFS_DIR2_LEAF1_MAGIC:
	154	case XFS_DIR3_LEAF1_MAGIC:
	155	bp->b_ops = &xfs_dir3_leaf1_buf_ops;
	156	bp->b_ops->verify_read(bp);
	157	return;
	158	default:
	159	/*
	160	* xfs_da3_node_buf_ops already know how to handle
	161	* DA_NODE, ATTR_LEAF, and DIR*_LEAFN blocks.
	162	*/
	163	bp->b_ops = &xfs_da3_node_buf_ops;
	164	bp->b_ops->verify_read(bp);
	165	return;
	166	}
	167	}
	168	static void
c517b3aa	169	xchk_da_btree_write_verify(
7c4a07a4 DW	170	struct xfs_buf *bp)
	171	{
	172	struct xfs_da_blkinfo *info = bp->b_addr;
	173
	174	switch (be16_to_cpu(info->magic)) {
	175	case XFS_DIR2_LEAF1_MAGIC:
	176	case XFS_DIR3_LEAF1_MAGIC:
	177	bp->b_ops = &xfs_dir3_leaf1_buf_ops;
	178	bp->b_ops->verify_write(bp);
	179	return;
	180	default:
	181	/*
	182	* xfs_da3_node_buf_ops already know how to handle
	183	* DA_NODE, ATTR_LEAF, and DIR*_LEAFN blocks.
	184	*/
	185	bp->b_ops = &xfs_da3_node_buf_ops;
	186	bp->b_ops->verify_write(bp);
	187	return;
	188	}
	189	}
cf1b0b8b	190	static void *
c517b3aa	191	xchk_da_btree_verify(
cf1b0b8b DW	192	struct xfs_buf *bp)
	193	{
	194	struct xfs_da_blkinfo *info = bp->b_addr;
	195
	196	switch (be16_to_cpu(info->magic)) {
	197	case XFS_DIR2_LEAF1_MAGIC:
	198	case XFS_DIR3_LEAF1_MAGIC:
	199	bp->b_ops = &xfs_dir3_leaf1_buf_ops;
	200	return bp->b_ops->verify_struct(bp);
	201	default:
	202	bp->b_ops = &xfs_da3_node_buf_ops;
	203	return bp->b_ops->verify_struct(bp);
	204	}
	205	}
7c4a07a4	206
c517b3aa DW	207	static const struct xfs_buf_ops xchk_da_btree_buf_ops = {
	208	.name = "xchk_da_btree",
	209	.verify_read = xchk_da_btree_read_verify,
	210	.verify_write = xchk_da_btree_write_verify,
	211	.verify_struct = xchk_da_btree_verify,
7c4a07a4 DW	212	};
	213
	214	/* Check a block's sibling. */
	215	STATIC int
c517b3aa	216	xchk_da_btree_block_check_sibling(
032d91f9 DW	217	struct xchk_da_btree *ds,
	218	int level,
	219	int direction,
	220	xfs_dablk_t sibling)
7c4a07a4	221	{
afbabf56 DW	222	struct xfs_da_state_path *path = &ds->state->path;
afbabf56 DW	223	struct xfs_da_state_path *altpath = &ds->state->altpath;
032d91f9	224	int retval;
afbabf56	225	int plevel;
032d91f9	226	int error;
7c4a07a4	227
afbabf56	228	memcpy(altpath, path, sizeof(ds->state->altpath));
7c4a07a4 DW	229
	230	/*
	231	* If the pointer is null, we shouldn't be able to move the upper
	232	* level pointer anywhere.
	233	*/
	234	if (sibling == 0) {
afbabf56 DW	235	error = xfs_da3_path_shift(ds->state, altpath, direction,
afbabf56 DW	236	false, &retval);
7c4a07a4	237	if (error == 0 && retval == 0)
c517b3aa	238	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	239	error = 0;
	240	goto out;
	241	}
	242
	243	/* Move the alternate cursor one block in the direction given. */
afbabf56 DW	244	error = xfs_da3_path_shift(ds->state, altpath, direction, false,
afbabf56 DW	245	&retval);
c517b3aa	246	if (!xchk_da_process_error(ds, level, &error))
afbabf56	247	goto out;
7c4a07a4	248	if (retval) {
c517b3aa	249	xchk_da_set_corrupt(ds, level);
afbabf56	250	goto out;
7c4a07a4	251	}
afbabf56 DW	252	if (altpath->blk[level].bp)
afbabf56 DW	253	xchk_buffer_recheck(ds->sc, altpath->blk[level].bp);
7c4a07a4 DW	254
7c4a07a4 DW	255	/* Compare upper level pointer to sibling pointer. */
afbabf56	256	if (altpath->blk[level].blkno != sibling)
c517b3aa	257	xchk_da_set_corrupt(ds, level);
afbabf56	258
7c4a07a4	259	out:
afbabf56 DW	260	/* Free all buffers in the altpath that aren't referenced from path. */
	261	for (plevel = 0; plevel < altpath->active; plevel++) {
	262	if (altpath->blk[plevel].bp == NULL \|\|
	263	(plevel < path->active &&
	264	altpath->blk[plevel].bp == path->blk[plevel].bp))
	265	continue;
	266
	267	xfs_trans_brelse(ds->dargs.trans, altpath->blk[plevel].bp);
	268	altpath->blk[plevel].bp = NULL;
	269	}
	270
7c4a07a4 DW	271	return error;
	272	}
	273
	274	/* Check a block's sibling pointers. */
	275	STATIC int
c517b3aa	276	xchk_da_btree_block_check_siblings(
032d91f9 DW	277	struct xchk_da_btree *ds,
	278	int level,
	279	struct xfs_da_blkinfo *hdr)
7c4a07a4	280	{
032d91f9 DW	281	xfs_dablk_t forw;
	282	xfs_dablk_t back;
	283	int error = 0;
7c4a07a4 DW	284
	285	forw = be32_to_cpu(hdr->forw);
	286	back = be32_to_cpu(hdr->back);
	287
	288	/* Top level blocks should not have sibling pointers. */
	289	if (level == 0) {
	290	if (forw != 0 \|\| back != 0)
c517b3aa	291	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	292	return 0;
	293	}
	294
	295	/*
	296	* Check back (left) and forw (right) pointers. These functions
	297	* absorb error codes for us.
	298	*/
c517b3aa	299	error = xchk_da_btree_block_check_sibling(ds, level, 0, back);
7c4a07a4 DW	300	if (error)
7c4a07a4 DW	301	goto out;
c517b3aa	302	error = xchk_da_btree_block_check_sibling(ds, level, 1, forw);
7c4a07a4 DW	303
	304	out:
	305	memset(&ds->state->altpath, 0, sizeof(ds->state->altpath));
	306	return error;
	307	}
	308
	309	/* Load a dir/attribute block from a btree. */
	310	STATIC int
c517b3aa DW	311	xchk_da_btree_block(
c517b3aa DW	312	struct xchk_da_btree *ds,
7c4a07a4 DW	313	int level,
	314	xfs_dablk_t blkno)
	315	{
	316	struct xfs_da_state_blk *blk;
	317	struct xfs_da_intnode *node;
	318	struct xfs_da_node_entry *btree;
	319	struct xfs_da3_blkinfo *hdr3;
	320	struct xfs_da_args *dargs = &ds->dargs;
	321	struct xfs_inode *ip = ds->dargs.dp;
	322	xfs_ino_t owner;
	323	int *pmaxrecs;
	324	struct xfs_da3_icnode_hdr nodehdr;
0dca060c	325	int error = 0;
7c4a07a4 DW	326
	327	blk = &ds->state->path.blk[level];
	328	ds->state->path.active = level + 1;
	329
	330	/* Release old block. */
	331	if (blk->bp) {
	332	xfs_trans_brelse(dargs->trans, blk->bp);
	333	blk->bp = NULL;
	334	}
	335
	336	/* Check the pointer. */
	337	blk->blkno = blkno;
c517b3aa	338	if (!xchk_da_btree_ptr_ok(ds, level, blkno))
7c4a07a4 DW	339	goto out_nobuf;
	340
	341	/* Read the buffer. */
cd2c9f1b CH	342	error = xfs_da_read_buf(dargs->trans, dargs->dp, blk->blkno,
cd2c9f1b CH	343	XFS_DABUF_MAP_HOLE_OK, &blk->bp, dargs->whichfork,
c517b3aa DW	344	&xchk_da_btree_buf_ops);
c517b3aa DW	345	if (!xchk_da_process_error(ds, level, &error))
7c4a07a4	346	goto out_nobuf;
cf1b0b8b	347	if (blk->bp)
c517b3aa	348	xchk_buffer_recheck(ds->sc, blk->bp);
7c4a07a4 DW	349
	350	/*
	351	* We didn't find a dir btree root block, which means that
	352	* there's no LEAF1/LEAFN tree (at least not where it's supposed
	353	* to be), so jump out now.
	354	*/
	355	if (ds->dargs.whichfork == XFS_DATA_FORK && level == 0 &&
	356	blk->bp == NULL)
	357	goto out_nobuf;
	358
	359	/* It's /not/ ok for attr trees not to have a da btree. */
	360	if (blk->bp == NULL) {
c517b3aa	361	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	362	goto out_nobuf;
	363	}
	364
	365	hdr3 = blk->bp->b_addr;
	366	blk->magic = be16_to_cpu(hdr3->hdr.magic);
	367	pmaxrecs = &ds->maxrecs[level];
	368
4da4b10b	369	/* We only started zeroing the header on v5 filesystems. */
38c26bfd	370	if (xfs_has_crc(ds->sc->mp) && hdr3->hdr.pad)
c517b3aa	371	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	372
7c4a07a4 DW	373	/* Check the owner. */
38c26bfd	374	if (xfs_has_crc(ip->i_mount)) {
7c4a07a4 DW	375	owner = be64_to_cpu(hdr3->owner);
7c4a07a4 DW	376	if (owner != ip->i_ino)
c517b3aa	377	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	378	}
	379
	380	/* Check the siblings. */
c517b3aa	381	error = xchk_da_btree_block_check_siblings(ds, level, &hdr3->hdr);
7c4a07a4 DW	382	if (error)
	383	goto out;
	384
	385	/* Interpret the buffer. */
	386	switch (blk->magic) {
	387	case XFS_ATTR_LEAF_MAGIC:
	388	case XFS_ATTR3_LEAF_MAGIC:
	389	xfs_trans_buf_set_type(dargs->trans, blk->bp,
	390	XFS_BLFT_ATTR_LEAF_BUF);
	391	blk->magic = XFS_ATTR_LEAF_MAGIC;
	392	blk->hashval = xfs_attr_leaf_lasthash(blk->bp, pmaxrecs);
	393	if (ds->tree_level != 0)
c517b3aa	394	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	395	break;
	396	case XFS_DIR2_LEAFN_MAGIC:
	397	case XFS_DIR3_LEAFN_MAGIC:
	398	xfs_trans_buf_set_type(dargs->trans, blk->bp,
	399	XFS_BLFT_DIR_LEAFN_BUF);
	400	blk->magic = XFS_DIR2_LEAFN_MAGIC;
	401	blk->hashval = xfs_dir2_leaf_lasthash(ip, blk->bp, pmaxrecs);
	402	if (ds->tree_level != 0)
c517b3aa	403	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	404	break;
	405	case XFS_DIR2_LEAF1_MAGIC:
	406	case XFS_DIR3_LEAF1_MAGIC:
	407	xfs_trans_buf_set_type(dargs->trans, blk->bp,
	408	XFS_BLFT_DIR_LEAF1_BUF);
	409	blk->magic = XFS_DIR2_LEAF1_MAGIC;
	410	blk->hashval = xfs_dir2_leaf_lasthash(ip, blk->bp, pmaxrecs);
	411	if (ds->tree_level != 0)
c517b3aa	412	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	413	break;
	414	case XFS_DA_NODE_MAGIC:
	415	case XFS_DA3_NODE_MAGIC:
	416	xfs_trans_buf_set_type(dargs->trans, blk->bp,
	417	XFS_BLFT_DA_NODE_BUF);
	418	blk->magic = XFS_DA_NODE_MAGIC;
	419	node = blk->bp->b_addr;
f475dc4d	420	xfs_da3_node_hdr_from_disk(ip->i_mount, &nodehdr, node);
51908ca7	421	btree = nodehdr.btree;
7c4a07a4 DW	422	*pmaxrecs = nodehdr.count;
	423	blk->hashval = be32_to_cpu(btree[*pmaxrecs - 1].hashval);
	424	if (level == 0) {
	425	if (nodehdr.level >= XFS_DA_NODE_MAXDEPTH) {
c517b3aa	426	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	427	goto out_freebp;
	428	}
	429	ds->tree_level = nodehdr.level;
	430	} else {
	431	if (ds->tree_level != nodehdr.level) {
c517b3aa	432	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	433	goto out_freebp;
	434	}
	435	}
	436
	437	/* XXX: Check hdr3.pad32 once we know how to fix it. */
	438	break;
	439	default:
c517b3aa	440	xchk_da_set_corrupt(ds, level);
7c4a07a4 DW	441	goto out_freebp;
	442	}
	443
e581c939 DW	444	/*
	445	* If we've been handed a block that is below the dabtree root, does
	446	* its hashval match what the parent block expected to see?
	447	*/
	448	if (level > 0) {
	449	struct xfs_da_node_entry *key;
	450
	451	key = xchk_da_btree_node_entry(ds, level - 1);
	452	if (be32_to_cpu(key->hashval) != blk->hashval) {
	453	xchk_da_set_corrupt(ds, level);
	454	goto out_freebp;
	455	}
	456	}
	457
7c4a07a4 DW	458	out:
	459	return error;
	460	out_freebp:
	461	xfs_trans_brelse(dargs->trans, blk->bp);
	462	blk->bp = NULL;
	463	out_nobuf:
	464	blk->blkno = 0;
	465	return error;
	466	}
	467
	468	/* Visit all nodes and leaves of a da btree. */
	469	int
c517b3aa	470	xchk_da_btree(
032d91f9	471	struct xfs_scrub *sc,
7c4a07a4	472	int whichfork,
032d91f9	473	xchk_da_btree_rec_fn scrub_fn,
13791d3b	474	void *private)
7c4a07a4	475	{
510a28e1	476	struct xchk_da_btree *ds;
7c4a07a4 DW	477	struct xfs_mount *mp = sc->mp;
	478	struct xfs_da_state_blk *blks;
	479	struct xfs_da_node_entry *key;
7c4a07a4 DW	480	xfs_dablk_t blkno;
	481	int level;
	482	int error;
	483
	484	/* Skip short format data structures; no btree to scan. */
732436ef	485	if (!xfs_ifork_has_extents(xfs_ifork_ptr(sc->ip, whichfork)))
7c4a07a4 DW	486	return 0;
	487
	488	/* Set up initial da state. */
510a28e1 DW	489	ds = kmem_zalloc(sizeof(struct xchk_da_btree), KM_NOFS \| KM_MAYFAIL);
	490	if (!ds)
	491	return -ENOMEM;
	492	ds->dargs.dp = sc->ip;
	493	ds->dargs.whichfork = whichfork;
	494	ds->dargs.trans = sc->tp;
	495	ds->dargs.op_flags = XFS_DA_OP_OKNOENT;
	496	ds->state = xfs_da_state_alloc(&ds->dargs);
	497	ds->sc = sc;
	498	ds->private = private;
7c4a07a4	499	if (whichfork == XFS_ATTR_FORK) {
510a28e1 DW	500	ds->dargs.geo = mp->m_attr_geo;
	501	ds->lowest = 0;
	502	ds->highest = 0;
7c4a07a4	503	} else {
510a28e1 DW	504	ds->dargs.geo = mp->m_dir_geo;
	505	ds->lowest = ds->dargs.geo->leafblk;
	506	ds->highest = ds->dargs.geo->freeblk;
7c4a07a4	507	}
510a28e1	508	blkno = ds->lowest;
7c4a07a4 DW	509	level = 0;
	510
	511	/* Find the root of the da tree, if present. */
510a28e1 DW	512	blks = ds->state->path.blk;
510a28e1 DW	513	error = xchk_da_btree_block(ds, level, blkno);
7c4a07a4 DW	514	if (error)
	515	goto out_state;
	516	/*
510a28e1	517	* We didn't find a block at ds->lowest, which means that there's
7c4a07a4 DW	518	* no LEAF1/LEAFN tree (at least not where it's supposed to be),
	519	* so jump out now.
	520	*/
	521	if (blks[level].bp == NULL)
	522	goto out_state;
	523
	524	blks[level].index = 0;
	525	while (level >= 0 && level < XFS_DA_NODE_MAXDEPTH) {
	526	/* Handle leaf block. */
	527	if (blks[level].magic != XFS_DA_NODE_MAGIC) {
	528	/* End of leaf, pop back towards the root. */
510a28e1	529	if (blks[level].index >= ds->maxrecs[level]) {
7c4a07a4 DW	530	if (level > 0)
7c4a07a4 DW	531	blks[level - 1].index++;
510a28e1	532	ds->tree_level++;
7c4a07a4 DW	533	level--;
	534	continue;
	535	}
	536
	537	/* Dispatch record scrubbing. */
510a28e1	538	error = scrub_fn(ds, level);
7c4a07a4 DW	539	if (error)
7c4a07a4 DW	540	break;
c517b3aa	541	if (xchk_should_terminate(sc, &error) \|\|
7c4a07a4 DW	542	(sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
	543	break;
	544
	545	blks[level].index++;
	546	continue;
	547	}
	548
	549
	550	/* End of node, pop back towards the root. */
510a28e1	551	if (blks[level].index >= ds->maxrecs[level]) {
7c4a07a4 DW	552	if (level > 0)
7c4a07a4 DW	553	blks[level - 1].index++;
510a28e1	554	ds->tree_level++;
7c4a07a4 DW	555	level--;
	556	continue;
	557	}
	558
	559	/* Hashes in order for scrub? */
510a28e1 DW	560	key = xchk_da_btree_node_entry(ds, level);
510a28e1 DW	561	error = xchk_da_btree_hash(ds, level, &key->hashval);
7c4a07a4 DW	562	if (error)
	563	goto out;
	564
	565	/* Drill another level deeper. */
	566	blkno = be32_to_cpu(key->before);
	567	level++;
228de124 DW	568	if (level >= XFS_DA_NODE_MAXDEPTH) {
228de124 DW	569	/* Too deep! */
510a28e1	570	xchk_da_set_corrupt(ds, level - 1);
228de124 DW	571	break;
228de124 DW	572	}
510a28e1 DW	573	ds->tree_level--;
510a28e1 DW	574	error = xchk_da_btree_block(ds, level, blkno);
7c4a07a4 DW	575	if (error)
	576	goto out;
	577	if (blks[level].bp == NULL)
	578	goto out;
	579
	580	blks[level].index = 0;
	581	}
	582
	583	out:
	584	/* Release all the buffers we're tracking. */
	585	for (level = 0; level < XFS_DA_NODE_MAXDEPTH; level++) {
	586	if (blks[level].bp == NULL)
	587	continue;
	588	xfs_trans_brelse(sc->tp, blks[level].bp);
	589	blks[level].bp = NULL;
	590	}
	591
	592	out_state:
510a28e1 DW	593	xfs_da_state_free(ds->state);
510a28e1 DW	594	kmem_free(ds);
7c4a07a4 DW	595	return error;
7c4a07a4 DW	596	}