dirtree.c | Explore in Territory

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Copyright (c) 2023-2024 Oracle.  All Rights Reserved.
 * Author: Darrick J. Wong <[email protected]>
 */
#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_icache.h"
#include "xfs_dir2.h"
#include "xfs_dir2_priv.h"
#include "xfs_attr.h"
#include "xfs_parent.h"
#include "scrub/scrub.h"
#include "scrub/common.h"
#include "scrub/bitmap.h"
#include "scrub/ino_bitmap.h"
#include "scrub/xfile.h"
#include "scrub/xfarray.h"
#include "scrub/xfblob.h"
#include "scrub/listxattr.h"
#include "scrub/trace.h"
#include "scrub/repair.h"
#include "scrub/orphanage.h"
#include "scrub/dirtree.h"

/*
 * Directory Tree Structure Validation
 * ===================================
 *
 * Validating the tree qualities of the directory tree structure can be
 * difficult.  If the tree is frozen, running a depth (or breadth) first search
 * and marking a bitmap suffices to determine if there is a cycle.  XORing the
 * mark bitmap with the inode bitmap afterwards tells us if there are
 * disconnected cycles.  If the tree is not frozen, directory updates can move
 * subtrees across the scanner wavefront, which complicates the design greatly.
 *
 * Directory parent pointers change that by enabling an incremental approach to
 * validation of the tree structure.  Instead of using one thread to scan the
 * entire filesystem, we instead can have multiple threads walking individual
 * subdirectories upwards to the root.  In a perfect world, the IOLOCK would
 * suffice to stabilize two directories in a parent -> child relationship.
 * Unfortunately, the VFS does not take the IOLOCK when moving a child
 * subdirectory, so we instead synchronize on ILOCK and use dirent update hooks
 * to detect a race.  If a race occurs in a path, we restart the scan.
 *
 * If the walk terminates without reaching the root, we know the path is
 * disconnected and ought to be attached to the lost and found.  If on the walk
 * we find the same subdir that we're scanning, we know this is a cycle and
 * should delete an incoming edge.  If we find multiple paths to the root, we
 * know to delete an incoming edge.
 *
 * There are two big hitches with this approach: first, all file link counts
 * must be correct to prevent other writers from doing the wrong thing with the
 * directory tree structure.  Second, because we're walking upwards in a tree
 * of arbitrary depth, we cannot hold all the ILOCKs.  Instead, we will use a
 * directory update hook to invalidate the scan results if one of the paths
 * we've scanned has changed.
 */

/* Clean up the dirtree checking resources. */
STATIC void
xchk_dirtree_buf_cleanup(
	void			*buf)
{ … }

/* Set us up to look for directory loops. */
int
xchk_setup_dirtree(
	struct xfs_scrub	*sc)
{ … }

/*
 * Add the parent pointer described by @dl->pptr to the given path as a new
 * step.  Returns -ELNRNG if the path is too deep.
 */
int
xchk_dirpath_append(
	struct xchk_dirtree		*dl,
	struct xfs_inode		*ip,
	struct xchk_dirpath		*path,
	const struct xfs_name		*name,
	const struct xfs_parent_rec	*pptr)
{ … }

/*
 * Create an xchk_path for each parent pointer of the directory that we're
 * scanning.  For each path created, we will eventually try to walk towards the
 * root with the goal of deleting all parents except for one that leads to the
 * root.
 *
 * Returns -EFSCORRUPTED to signal that the inode being scanned has a corrupt
 * parent pointer and hence there's no point in continuing; or -ENOSR if there
 * are too many parent pointers for this directory.
 */
STATIC int
xchk_dirtree_create_path(
	struct xfs_scrub		*sc,
	struct xfs_inode		*ip,
	unsigned int			attr_flags,
	const unsigned char		*name,
	unsigned int			namelen,
	const void			*value,
	unsigned int			valuelen,
	void				*priv)
{ … }

/*
 * Validate that the first step of this path still has a corresponding
 * parent pointer in @sc->ip.  We probably dropped @sc->ip's ILOCK while
 * walking towards the roots, which is why this is necessary.
 *
 * This function has a side effect of loading the first parent pointer of this
 * path into the parent pointer scratch pad.  This prepares us to walk up the
 * directory tree towards the root.  Returns -ESTALE if the scan data is now
 * out of date.
 */
STATIC int
xchk_dirpath_revalidate(
	struct xchk_dirtree		*dl,
	struct xchk_dirpath		*path)
{ … }

/*
 * Walk the parent pointers of a directory at the end of a path and record
 * the parent that we find in @dl->xname/pptr_rec.
 */
STATIC int
xchk_dirpath_find_next_step(
	struct xfs_scrub		*sc,
	struct xfs_inode		*ip,
	unsigned int			attr_flags,
	const unsigned char		*name,
	unsigned int			namelen,
	const void			*value,
	unsigned int			valuelen,
	void				*priv)
{ … }

/* Set and log the outcome of a path walk. */
static inline void
xchk_dirpath_set_outcome(
	struct xchk_dirtree		*dl,
	struct xchk_dirpath		*path,
	enum xchk_dirpath_outcome	outcome)
{ … }

/*
 * Scan the directory at the end of this path for its parent directory link.
 * If we find one, extend the path.  Returns -ESTALE if the scan data out of
 * date.  Returns -EFSCORRUPTED if the parent pointer is bad; or -ELNRNG if
 * the path got too deep.
 */
STATIC int
xchk_dirpath_step_up(
	struct xchk_dirtree	*dl,
	struct xchk_dirpath	*path)
{ … }

/*
 * Walk the directory tree upwards towards what is hopefully the root
 * directory, recording path steps as we go.  The current path components are
 * stored in dl->pptr_rec and dl->xname.
 *
 * Returns -ESTALE if the scan data are out of date.  Returns -EFSCORRUPTED
 * only if the direct parent pointer of @sc->ip associated with this path is
 * corrupt.
 */
STATIC int
xchk_dirpath_walk_upwards(
	struct xchk_dirtree	*dl,
	struct xchk_dirpath	*path)
{ … }

/*
 * Decide if this path step has been touched by this live update.  Returns
 * 1 for yes, 0 for no, or a negative errno.
 */
STATIC int
xchk_dirpath_step_is_stale(
	struct xchk_dirtree		*dl,
	struct xchk_dirpath		*path,
	unsigned int			step_nr,
	xfarray_idx_t			step_idx,
	struct xfs_dir_update_params	*p,
	xfs_ino_t			*cursor)
{ … }

/*
 * Decide if this path has been touched by this live update.  Returns 1 for
 * yes, 0 for no, or a negative errno.
 */
STATIC int
xchk_dirpath_is_stale(
	struct xchk_dirtree		*dl,
	struct xchk_dirpath		*path,
	struct xfs_dir_update_params	*p)
{ … }

/*
 * Decide if a directory update from the regular filesystem touches any of the
 * paths we've scanned, and invalidate the scan data if true.
 */
STATIC int
xchk_dirtree_live_update(
	struct notifier_block		*nb,
	unsigned long			action,
	void				*data)
{ … }

/* Delete all the collected path information. */
STATIC void
xchk_dirtree_reset(
	void			*buf)
{ … }

/*
 * Load the name/pptr from the first step in this path into @dl->pptr_rec and
 * @dl->xname.
 */
STATIC int
xchk_dirtree_load_path(
	struct xchk_dirtree		*dl,
	struct xchk_dirpath		*path)
{ … }

/*
 * For each parent pointer of this subdir, trace a path upwards towards the
 * root directory and record what we find.  Returns 0 for success;
 * -EFSCORRUPTED if walking the parent pointers of @sc->ip failed, -ELNRNG if a
 * path was too deep; -ENOSR if there were too many parent pointers; or
 * a negative errno.
 */
int
xchk_dirtree_find_paths_to_root(
	struct xchk_dirtree	*dl)
{ … }

/*
 * Figure out what to do with the paths we tried to find.  Do not call this
 * if the scan results are stale.
 */
void
xchk_dirtree_evaluate(
	struct xchk_dirtree		*dl,
	struct xchk_dirtree_outcomes	*oc)
{ … }

/* Look for directory loops. */
int
xchk_dirtree(
	struct xfs_scrub		*sc)
{ … }
linux/fs/xfs/scrub/dirtree.c
