dirtree.c

   1// SPDX-License-Identifier: GPL-2.0-or-later
   2/*
   3 * Copyright (c) 2023-2024 Oracle.  All Rights Reserved.
   4 * Author: Darrick J. Wong <djwong@kernel.org>
   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"
  12#include "xfs_log_format.h"
  13#include "xfs_trans.h"
  14#include "xfs_inode.h"
  15#include "xfs_icache.h"
  16#include "xfs_dir2.h"
  17#include "xfs_dir2_priv.h"
  18#include "xfs_attr.h"
  19#include "xfs_parent.h"
  20#include "scrub/scrub.h"
  21#include "scrub/common.h"
  22#include "scrub/bitmap.h"
  23#include "scrub/ino_bitmap.h"
  24#include "scrub/xfile.h"
  25#include "scrub/xfarray.h"
  26#include "scrub/xfblob.h"
  27#include "scrub/listxattr.h"
  28#include "scrub/trace.h"
  29#include "scrub/repair.h"
  30#include "scrub/orphanage.h"
  31#include "scrub/dirtree.h"
  32
  33/*
  34 * Directory Tree Structure Validation
  35 * ===================================
  36 *
  37 * Validating the tree qualities of the directory tree structure can be
  38 * difficult.  If the tree is frozen, running a depth (or breadth) first search
  39 * and marking a bitmap suffices to determine if there is a cycle.  XORing the
  40 * mark bitmap with the inode bitmap afterwards tells us if there are
  41 * disconnected cycles.  If the tree is not frozen, directory updates can move
  42 * subtrees across the scanner wavefront, which complicates the design greatly.
  43 *
  44 * Directory parent pointers change that by enabling an incremental approach to
  45 * validation of the tree structure.  Instead of using one thread to scan the
  46 * entire filesystem, we instead can have multiple threads walking individual
  47 * subdirectories upwards to the root.  In a perfect world, the IOLOCK would
  48 * suffice to stabilize two directories in a parent -> child relationship.
  49 * Unfortunately, the VFS does not take the IOLOCK when moving a child
  50 * subdirectory, so we instead synchronize on ILOCK and use dirent update hooks
  51 * to detect a race.  If a race occurs in a path, we restart the scan.
  52 *
  53 * If the walk terminates without reaching the root, we know the path is
  54 * disconnected and ought to be attached to the lost and found.  If on the walk
  55 * we find the same subdir that we're scanning, we know this is a cycle and
  56 * should delete an incoming edge.  If we find multiple paths to the root, we
  57 * know to delete an incoming edge.
  58 *
  59 * There are two big hitches with this approach: first, all file link counts
  60 * must be correct to prevent other writers from doing the wrong thing with the
  61 * directory tree structure.  Second, because we're walking upwards in a tree
  62 * of arbitrary depth, we cannot hold all the ILOCKs.  Instead, we will use a
  63 * directory update hook to invalidate the scan results if one of the paths
  64 * we've scanned has changed.
  65 */
  66
  67/* Clean up the dirtree checking resources. */
  68STATIC void
  69xchk_dirtree_buf_cleanup(
  70	void			*buf)
  71{
  72	struct xchk_dirtree	*dl = buf;
  73	struct xchk_dirpath	*path, *n;
  74
  75	if (dl->scan_ino != NULLFSINO)
  76		xfs_dir_hook_del(dl->sc->mp, &dl->dhook);
  77
  78	xchk_dirtree_for_each_path_safe(dl, path, n) {
  79		list_del_init(&path->list);
  80		xino_bitmap_destroy(&path->seen_inodes);
  81		kfree(path);
  82	}
  83
  84	if (dl->path_names)
  85		xfblob_destroy(dl->path_names);
  86	dl->path_names = NULL;
  87	if (dl->path_steps)
  88		xfarray_destroy(dl->path_steps);
  89	dl->path_steps = NULL;
  90	mutex_destroy(&dl->lock);
  91}
  92
  93/* Set us up to look for directory loops. */
  94int
  95xchk_setup_dirtree(
  96	struct xfs_scrub	*sc)
  97{
  98	struct xchk_dirtree	*dl;
  99	int			error;
 100
 101	xchk_fsgates_enable(sc, XCHK_FSGATES_DIRENTS);
 102
 103	if (xchk_could_repair(sc)) {
 104		error = xrep_setup_dirtree(sc);
 105		if (error)
 106			return error;
 107	}
 108
 109	dl = kvzalloc(sizeof(struct xchk_dirtree), XCHK_GFP_FLAGS);
 110	if (!dl)
 111		return -ENOMEM;
 112	dl->sc = sc;
 113	dl->xname.name = dl->namebuf;
 114	dl->hook_xname.name = dl->hook_namebuf;
 115	INIT_LIST_HEAD(&dl->path_list);
 116	dl->root_ino = NULLFSINO;
 117	dl->scan_ino = NULLFSINO;
 118	dl->parent_ino = NULLFSINO;
 119
 120	mutex_init(&dl->lock);
 121
 122	error = xfarray_create("dirtree path steps", 0,
 123			sizeof(struct xchk_dirpath_step), &dl->path_steps);
 124	if (error)
 125		goto out_dl;
 126
 127	error = xfblob_create("dirtree path names", &dl->path_names);
 128	if (error)
 129		goto out_steps;
 130
 131	error = xchk_setup_inode_contents(sc, 0);
 132	if (error)
 133		goto out_names;
 134
 135	sc->buf = dl;
 136	sc->buf_cleanup = xchk_dirtree_buf_cleanup;
 137	return 0;
 138
 139out_names:
 140	xfblob_destroy(dl->path_names);
 141out_steps:
 142	xfarray_destroy(dl->path_steps);
 143out_dl:
 144	mutex_destroy(&dl->lock);
 145	kvfree(dl);
 146	return error;
 147}
 148
 149/*
 150 * Add the parent pointer described by @dl->pptr to the given path as a new
 151 * step.  Returns -ELNRNG if the path is too deep.
 152 */
 153int
 154xchk_dirpath_append(
 155	struct xchk_dirtree		*dl,
 156	struct xfs_inode		*ip,
 157	struct xchk_dirpath		*path,
 158	const struct xfs_name		*name,
 159	const struct xfs_parent_rec	*pptr)
 160{
 161	struct xchk_dirpath_step	step = {
 162		.pptr_rec		= *pptr, /* struct copy */
 163		.name_len		= name->len,
 164	};
 165	int				error;
 166
 167	/*
 168	 * If this path is more than 2 billion steps long, this directory tree
 169	 * is too far gone to fix.
 170	 */
 171	if (path->nr_steps >= XFS_MAXLINK)
 172		return -ELNRNG;
 173
 174	error = xfblob_storename(dl->path_names, &step.name_cookie, name);
 175	if (error)
 176		return error;
 177
 178	error = xino_bitmap_set(&path->seen_inodes, ip->i_ino);
 179	if (error)
 180		return error;
 181
 182	error = xfarray_append(dl->path_steps, &step);
 183	if (error)
 184		return error;
 185
 186	path->nr_steps++;
 187	return 0;
 188}
 189
 190/*
 191 * Create an xchk_path for each parent pointer of the directory that we're
 192 * scanning.  For each path created, we will eventually try to walk towards the
 193 * root with the goal of deleting all parents except for one that leads to the
 194 * root.
 195 *
 196 * Returns -EFSCORRUPTED to signal that the inode being scanned has a corrupt
 197 * parent pointer and hence there's no point in continuing; or -ENOSR if there
 198 * are too many parent pointers for this directory.
 199 */
 200STATIC int
 201xchk_dirtree_create_path(
 202	struct xfs_scrub		*sc,
 203	struct xfs_inode		*ip,
 204	unsigned int			attr_flags,
 205	const unsigned char		*name,
 206	unsigned int			namelen,
 207	const void			*value,
 208	unsigned int			valuelen,
 209	void				*priv)
 210{
 211	struct xfs_name			xname = {
 212		.name			= name,
 213		.len			= namelen,
 214	};
 215	struct xchk_dirtree		*dl = priv;
 216	struct xchk_dirpath		*path;
 217	const struct xfs_parent_rec	*rec = value;
 218	int				error;
 219
 220	if (!(attr_flags & XFS_ATTR_PARENT))
 221		return 0;
 222
 223	error = xfs_parent_from_attr(sc->mp, attr_flags, name, namelen, value,
 224			valuelen, NULL, NULL);
 225	if (error)
 226		return error;
 227
 228	/*
 229	 * If there are more than 2 billion actual parent pointers for this
 230	 * subdirectory, this fs is too far gone to fix.
 231	 */
 232	if (dl->nr_paths >= XFS_MAXLINK)
 233		return -ENOSR;
 234
 235	trace_xchk_dirtree_create_path(sc, ip, dl->nr_paths, &xname, rec);
 236
 237	/*
 238	 * Create a new xchk_path structure to remember this parent pointer
 239	 * and record the first name step.
 240	 */
 241	path = kmalloc(sizeof(struct xchk_dirpath), XCHK_GFP_FLAGS);
 242	if (!path)
 243		return -ENOMEM;
 244
 245	INIT_LIST_HEAD(&path->list);
 246	xino_bitmap_init(&path->seen_inodes);
 247	path->nr_steps = 0;
 248	path->outcome = XCHK_DIRPATH_SCANNING;
 249
 250	error = xchk_dirpath_append(dl, sc->ip, path, &xname, rec);
 251	if (error)
 252		goto out_path;
 253
 254	path->first_step = xfarray_length(dl->path_steps) - 1;
 255	path->second_step = XFARRAY_NULLIDX;
 256	path->path_nr = dl->nr_paths;
 257
 258	list_add_tail(&path->list, &dl->path_list);
 259	dl->nr_paths++;
 260	return 0;
 261out_path:
 262	kfree(path);
 263	return error;
 264}
 265
 266/*
 267 * Validate that the first step of this path still has a corresponding
 268 * parent pointer in @sc->ip.  We probably dropped @sc->ip's ILOCK while
 269 * walking towards the roots, which is why this is necessary.
 270 *
 271 * This function has a side effect of loading the first parent pointer of this
 272 * path into the parent pointer scratch pad.  This prepares us to walk up the
 273 * directory tree towards the root.  Returns -ESTALE if the scan data is now
 274 * out of date.
 275 */
 276STATIC int
 277xchk_dirpath_revalidate(
 278	struct xchk_dirtree		*dl,
 279	struct xchk_dirpath		*path)
 280{
 281	struct xfs_scrub		*sc = dl->sc;
 282	int				error;
 283
 284	/*
 285	 * Look up the parent pointer that corresponds to the start of this
 286	 * path.  If the parent pointer has disappeared on us, dump all the
 287	 * scan results and try again.
 288	 */
 289	error = xfs_parent_lookup(sc->tp, sc->ip, &dl->xname, &dl->pptr_rec,
 290			&dl->pptr_args);
 291	if (error == -ENOATTR) {
 292		trace_xchk_dirpath_disappeared(dl->sc, sc->ip, path->path_nr,
 293				path->first_step, &dl->xname, &dl->pptr_rec);
 294		dl->stale = true;
 295		return -ESTALE;
 296	}
 297
 298	return error;
 299}
 300
 301/*
 302 * Walk the parent pointers of a directory at the end of a path and record
 303 * the parent that we find in @dl->xname/pptr_rec.
 304 */
 305STATIC int
 306xchk_dirpath_find_next_step(
 307	struct xfs_scrub		*sc,
 308	struct xfs_inode		*ip,
 309	unsigned int			attr_flags,
 310	const unsigned char		*name,
 311	unsigned int			namelen,
 312	const void			*value,
 313	unsigned int			valuelen,
 314	void				*priv)
 315{
 316	struct xchk_dirtree		*dl = priv;
 317	const struct xfs_parent_rec	*rec = value;
 318	int				error;
 319
 320	if (!(attr_flags & XFS_ATTR_PARENT))
 321		return 0;
 322
 323	error = xfs_parent_from_attr(sc->mp, attr_flags, name, namelen, value,
 324			valuelen, NULL, NULL);
 325	if (error)
 326		return error;
 327
 328	/*
 329	 * If we've already set @dl->pptr_rec, then this directory has multiple
 330	 * parents.  Signal this back to the caller via -EMLINK.
 331	 */
 332	if (dl->parents_found > 0)
 333		return -EMLINK;
 334
 335	dl->parents_found++;
 336	memcpy(dl->namebuf, name, namelen);
 337	dl->xname.len = namelen;
 338	dl->pptr_rec = *rec; /* struct copy */
 339	return 0;
 340}
 341
 342/* Set and log the outcome of a path walk. */
 343static inline void
 344xchk_dirpath_set_outcome(
 345	struct xchk_dirtree		*dl,
 346	struct xchk_dirpath		*path,
 347	enum xchk_dirpath_outcome	outcome)
 348{
 349	trace_xchk_dirpath_set_outcome(dl->sc, path->path_nr, path->nr_steps,
 350			outcome);
 351
 352	path->outcome = outcome;
 353}
 354
 355/*
 356 * Scan the directory at the end of this path for its parent directory link.
 357 * If we find one, extend the path.  Returns -ESTALE if the scan data out of
 358 * date.  Returns -EFSCORRUPTED if the parent pointer is bad; or -ELNRNG if
 359 * the path got too deep.
 360 */
 361STATIC int
 362xchk_dirpath_step_up(
 363	struct xchk_dirtree	*dl,
 364	struct xchk_dirpath	*path,
 365	bool			is_metadir)
 366{
 367	struct xfs_scrub	*sc = dl->sc;
 368	struct xfs_inode	*dp;
 369	xfs_ino_t		parent_ino = be64_to_cpu(dl->pptr_rec.p_ino);
 370	unsigned int		lock_mode;
 371	int			error;
 372
 373	/* Grab and lock the parent directory. */
 374	error = xchk_iget(sc, parent_ino, &dp);
 375	if (error)
 376		return error;
 377
 378	lock_mode = xfs_ilock_attr_map_shared(dp);
 379	mutex_lock(&dl->lock);
 380
 381	if (dl->stale) {
 382		error = -ESTALE;
 383		goto out_scanlock;
 384	}
 385
 386	/* We've reached the root directory; the path is ok. */
 387	if (parent_ino == dl->root_ino) {
 388		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_OK);
 389		error = 0;
 390		goto out_scanlock;
 391	}
 392
 393	/*
 394	 * The inode being scanned is its own distant ancestor!  Get rid of
 395	 * this path.
 396	 */
 397	if (parent_ino == sc->ip->i_ino) {
 398		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_DELETE);
 399		error = 0;
 400		goto out_scanlock;
 401	}
 402
 403	/*
 404	 * We've seen this inode before during the path walk.  There's a loop
 405	 * above us in the directory tree.  This probably means that we cannot
 406	 * continue, but let's keep walking paths to get a full picture.
 407	 */
 408	if (xino_bitmap_test(&path->seen_inodes, parent_ino)) {
 409		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_LOOP);
 410		error = 0;
 411		goto out_scanlock;
 412	}
 413
 414	/* The handle encoded in the parent pointer must match. */
 415	if (VFS_I(dp)->i_generation != be32_to_cpu(dl->pptr_rec.p_gen)) {
 416		trace_xchk_dirpath_badgen(dl->sc, dp, path->path_nr,
 417				path->nr_steps, &dl->xname, &dl->pptr_rec);
 418		error = -EFSCORRUPTED;
 419		goto out_scanlock;
 420	}
 421
 422	/* Parent pointer must point up to a directory. */
 423	if (!S_ISDIR(VFS_I(dp)->i_mode)) {
 424		trace_xchk_dirpath_nondir_parent(dl->sc, dp, path->path_nr,
 425				path->nr_steps, &dl->xname, &dl->pptr_rec);
 426		error = -EFSCORRUPTED;
 427		goto out_scanlock;
 428	}
 429
 430	/* Parent cannot be an unlinked directory. */
 431	if (VFS_I(dp)->i_nlink == 0) {
 432		trace_xchk_dirpath_unlinked_parent(dl->sc, dp, path->path_nr,
 433				path->nr_steps, &dl->xname, &dl->pptr_rec);
 434		error = -EFSCORRUPTED;
 435		goto out_scanlock;
 436	}
 437
 438	/* Parent must be in the same directory tree. */
 439	if (is_metadir != xfs_is_metadir_inode(dp)) {
 440		trace_xchk_dirpath_crosses_tree(dl->sc, dp, path->path_nr,
 441				path->nr_steps, &dl->xname, &dl->pptr_rec);
 442		error = -EFSCORRUPTED;
 443		goto out_scanlock;
 444	}
 445
 446	/*
 447	 * If the extended attributes look as though they has been zapped by
 448	 * the inode record repair code, we cannot scan for parent pointers.
 449	 */
 450	if (xchk_pptr_looks_zapped(dp)) {
 451		error = -EBUSY;
 452		xchk_set_incomplete(sc);
 453		goto out_scanlock;
 454	}
 455
 456	/*
 457	 * Walk the parent pointers of @dp to find the parent of this directory
 458	 * to find the next step in our walk.  If we find that @dp has exactly
 459	 * one parent, the parent pointer information will be stored in
 460	 * @dl->pptr_rec.  This prepares us for the next step of the walk.
 461	 */
 462	mutex_unlock(&dl->lock);
 463	dl->parents_found = 0;
 464	error = xchk_xattr_walk(sc, dp, xchk_dirpath_find_next_step, NULL, dl);
 465	mutex_lock(&dl->lock);
 466	if (error == -EFSCORRUPTED || error == -EMLINK ||
 467	    (!error && dl->parents_found == 0)) {
 468		/*
 469		 * Further up the directory tree from @sc->ip, we found a
 470		 * corrupt parent pointer, multiple parent pointers while
 471		 * finding this directory's parent, or zero parents despite
 472		 * having a nonzero link count.  Keep looking for other paths.
 473		 */
 474		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_CORRUPT);
 475		error = 0;
 476		goto out_scanlock;
 477	}
 478	if (error)
 479		goto out_scanlock;
 480
 481	if (dl->stale) {
 482		error = -ESTALE;
 483		goto out_scanlock;
 484	}
 485
 486	trace_xchk_dirpath_found_next_step(sc, dp, path->path_nr,
 487			path->nr_steps, &dl->xname, &dl->pptr_rec);
 488
 489	/* Append to the path steps */
 490	error = xchk_dirpath_append(dl, dp, path, &dl->xname, &dl->pptr_rec);
 491	if (error)
 492		goto out_scanlock;
 493
 494	if (path->second_step == XFARRAY_NULLIDX)
 495		path->second_step = xfarray_length(dl->path_steps) - 1;
 496
 497out_scanlock:
 498	mutex_unlock(&dl->lock);
 499	xfs_iunlock(dp, lock_mode);
 500	xchk_irele(sc, dp);
 501	return error;
 502}
 503
 504/*
 505 * Walk the directory tree upwards towards what is hopefully the root
 506 * directory, recording path steps as we go.  The current path components are
 507 * stored in dl->pptr_rec and dl->xname.
 508 *
 509 * Returns -ESTALE if the scan data are out of date.  Returns -EFSCORRUPTED
 510 * only if the direct parent pointer of @sc->ip associated with this path is
 511 * corrupt.
 512 */
 513STATIC int
 514xchk_dirpath_walk_upwards(
 515	struct xchk_dirtree	*dl,
 516	struct xchk_dirpath	*path)
 517{
 518	struct xfs_scrub	*sc = dl->sc;
 519	bool			is_metadir;
 520	int			error;
 521
 522	ASSERT(sc->ilock_flags & XFS_ILOCK_EXCL);
 523
 524	/* Reload the start of this path and make sure it's still there. */
 525	error = xchk_dirpath_revalidate(dl, path);
 526	if (error)
 527		return error;
 528
 529	trace_xchk_dirpath_walk_upwards(sc, sc->ip, path->path_nr, &dl->xname,
 530			&dl->pptr_rec);
 531
 532	/*
 533	 * The inode being scanned is its own direct ancestor!
 534	 * Get rid of this path.
 535	 */
 536	if (be64_to_cpu(dl->pptr_rec.p_ino) == sc->ip->i_ino) {
 537		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_DELETE);
 538		return 0;
 539	}
 540
 541	/*
 542	 * Drop ILOCK_EXCL on the inode being scanned.  We still hold
 543	 * IOLOCK_EXCL on it, so it cannot move around or be renamed.
 544	 *
 545	 * Beyond this point we're walking up the directory tree, which means
 546	 * that we can acquire and drop the ILOCK on an alias of sc->ip.  The
 547	 * ILOCK state is no longer tracked in the scrub context.  Hence we
 548	 * must drop @sc->ip's ILOCK during the walk.
 549	 */
 550	is_metadir = xfs_is_metadir_inode(sc->ip);
 551	mutex_unlock(&dl->lock);
 552	xchk_iunlock(sc, XFS_ILOCK_EXCL);
 553
 554	/*
 555	 * Take the first step in the walk towards the root by checking the
 556	 * start of this path, which is a direct parent pointer of @sc->ip.
 557	 * If we see any kind of error here (including corruptions), the parent
 558	 * pointer of @sc->ip is corrupt.  Stop the whole scan.
 559	 */
 560	error = xchk_dirpath_step_up(dl, path, is_metadir);
 561	if (error) {
 562		xchk_ilock(sc, XFS_ILOCK_EXCL);
 563		mutex_lock(&dl->lock);
 564		return error;
 565	}
 566
 567	/*
 568	 * Take steps upward from the second step in this path towards the
 569	 * root.  If we hit corruption errors here, there's a problem
 570	 * *somewhere* in the path, but we don't need to stop scanning.
 571	 */
 572	while (!error && path->outcome == XCHK_DIRPATH_SCANNING)
 573		error = xchk_dirpath_step_up(dl, path, is_metadir);
 574
 575	/* Retake the locks we had, mark paths, etc. */
 576	xchk_ilock(sc, XFS_ILOCK_EXCL);
 577	mutex_lock(&dl->lock);
 578	if (error == -EFSCORRUPTED) {
 579		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_CORRUPT);
 580		error = 0;
 581	}
 582	if (!error && dl->stale)
 583		return -ESTALE;
 584	return error;
 585}
 586
 587/*
 588 * Decide if this path step has been touched by this live update.  Returns
 589 * 1 for yes, 0 for no, or a negative errno.
 590 */
 591STATIC int
 592xchk_dirpath_step_is_stale(
 593	struct xchk_dirtree		*dl,
 594	struct xchk_dirpath		*path,
 595	unsigned int			step_nr,
 596	xfarray_idx_t			step_idx,
 597	struct xfs_dir_update_params	*p,
 598	xfs_ino_t			*cursor)
 599{
 600	struct xchk_dirpath_step	step;
 601	xfs_ino_t			child_ino = *cursor;
 602	int				error;
 603
 604	error = xfarray_load(dl->path_steps, step_idx, &step);
 605	if (error)
 606		return error;
 607	*cursor = be64_to_cpu(step.pptr_rec.p_ino);
 608
 609	/*
 610	 * If the parent and child being updated are not the ones mentioned in
 611	 * this path step, the scan data is still ok.
 612	 */
 613	if (p->ip->i_ino != child_ino || p->dp->i_ino != *cursor)
 614		return 0;
 615
 616	/*
 617	 * If the dirent name lengths or byte sequences are different, the scan
 618	 * data is still ok.
 619	 */
 620	if (p->name->len != step.name_len)
 621		return 0;
 622
 623	error = xfblob_loadname(dl->path_names, step.name_cookie,
 624			&dl->hook_xname, step.name_len);
 625	if (error)
 626		return error;
 627
 628	if (memcmp(dl->hook_xname.name, p->name->name, p->name->len) != 0)
 629		return 0;
 630
 631	/*
 632	 * If the update comes from the repair code itself, walk the state
 633	 * machine forward.
 634	 */
 635	if (p->ip->i_ino == dl->scan_ino &&
 636	    path->outcome == XREP_DIRPATH_ADOPTING) {
 637		xchk_dirpath_set_outcome(dl, path, XREP_DIRPATH_ADOPTED);
 638		return 0;
 639	}
 640
 641	if (p->ip->i_ino == dl->scan_ino &&
 642	    path->outcome == XREP_DIRPATH_DELETING) {
 643		xchk_dirpath_set_outcome(dl, path, XREP_DIRPATH_DELETED);
 644		return 0;
 645	}
 646
 647	/* Exact match, scan data is out of date. */
 648	trace_xchk_dirpath_changed(dl->sc, path->path_nr, step_nr, p->dp,
 649			p->ip, p->name);
 650	return 1;
 651}
 652
 653/*
 654 * Decide if this path has been touched by this live update.  Returns 1 for
 655 * yes, 0 for no, or a negative errno.
 656 */
 657STATIC int
 658xchk_dirpath_is_stale(
 659	struct xchk_dirtree		*dl,
 660	struct xchk_dirpath		*path,
 661	struct xfs_dir_update_params	*p)
 662{
 663	xfs_ino_t			cursor = dl->scan_ino;
 664	xfarray_idx_t			idx = path->first_step;
 665	unsigned int			i;
 666	int				ret;
 667
 668	/*
 669	 * The child being updated has not been seen by this path at all; this
 670	 * path cannot be stale.
 671	 */
 672	if (!xino_bitmap_test(&path->seen_inodes, p->ip->i_ino))
 673		return 0;
 674
 675	ret = xchk_dirpath_step_is_stale(dl, path, 0, idx, p, &cursor);
 676	if (ret != 0)
 677		return ret;
 678
 679	for (i = 1, idx = path->second_step; i < path->nr_steps; i++, idx++) {
 680		ret = xchk_dirpath_step_is_stale(dl, path, i, idx, p, &cursor);
 681		if (ret != 0)
 682			return ret;
 683	}
 684
 685	return 0;
 686}
 687
 688/*
 689 * Decide if a directory update from the regular filesystem touches any of the
 690 * paths we've scanned, and invalidate the scan data if true.
 691 */
 692STATIC int
 693xchk_dirtree_live_update(
 694	struct notifier_block		*nb,
 695	unsigned long			action,
 696	void				*data)
 697{
 698	struct xfs_dir_update_params	*p = data;
 699	struct xchk_dirtree		*dl;
 700	struct xchk_dirpath		*path;
 701	int				ret;
 702
 703	dl = container_of(nb, struct xchk_dirtree, dhook.dirent_hook.nb);
 704
 705	trace_xchk_dirtree_live_update(dl->sc, p->dp, action, p->ip, p->delta,
 706			p->name);
 707
 708	mutex_lock(&dl->lock);
 709
 710	if (dl->stale || dl->aborted)
 711		goto out_unlock;
 712
 713	xchk_dirtree_for_each_path(dl, path) {
 714		ret = xchk_dirpath_is_stale(dl, path, p);
 715		if (ret < 0) {
 716			dl->aborted = true;
 717			break;
 718		}
 719		if (ret == 1) {
 720			dl->stale = true;
 721			break;
 722		}
 723	}
 724
 725out_unlock:
 726	mutex_unlock(&dl->lock);
 727	return NOTIFY_DONE;
 728}
 729
 730/* Delete all the collected path information. */
 731STATIC void
 732xchk_dirtree_reset(
 733	void			*buf)
 734{
 735	struct xchk_dirtree	*dl = buf;
 736	struct xchk_dirpath	*path, *n;
 737
 738	ASSERT(dl->sc->ilock_flags & XFS_ILOCK_EXCL);
 739
 740	xchk_dirtree_for_each_path_safe(dl, path, n) {
 741		list_del_init(&path->list);
 742		xino_bitmap_destroy(&path->seen_inodes);
 743		kfree(path);
 744	}
 745	dl->nr_paths = 0;
 746
 747	xfarray_truncate(dl->path_steps);
 748	xfblob_truncate(dl->path_names);
 749
 750	dl->stale = false;
 751}
 752
 753/*
 754 * Load the name/pptr from the first step in this path into @dl->pptr_rec and
 755 * @dl->xname.
 756 */
 757STATIC int
 758xchk_dirtree_load_path(
 759	struct xchk_dirtree		*dl,
 760	struct xchk_dirpath		*path)
 761{
 762	struct xchk_dirpath_step	step;
 763	int				error;
 764
 765	error = xfarray_load(dl->path_steps, path->first_step, &step);
 766	if (error)
 767		return error;
 768
 769	error = xfblob_loadname(dl->path_names, step.name_cookie, &dl->xname,
 770			step.name_len);
 771	if (error)
 772		return error;
 773
 774	dl->pptr_rec = step.pptr_rec; /* struct copy */
 775	return 0;
 776}
 777
 778/*
 779 * For each parent pointer of this subdir, trace a path upwards towards the
 780 * root directory and record what we find.  Returns 0 for success;
 781 * -EFSCORRUPTED if walking the parent pointers of @sc->ip failed, -ELNRNG if a
 782 * path was too deep; -ENOSR if there were too many parent pointers; or
 783 * a negative errno.
 784 */
 785int
 786xchk_dirtree_find_paths_to_root(
 787	struct xchk_dirtree	*dl)
 788{
 789	struct xfs_scrub	*sc = dl->sc;
 790	struct xchk_dirpath	*path;
 791	int			error = 0;
 792
 793	do {
 794		if (xchk_should_terminate(sc, &error))
 795			return error;
 796
 797		xchk_dirtree_reset(dl);
 798
 799		/*
 800		 * If the extended attributes look as though they has been
 801		 * zapped by the inode record repair code, we cannot scan for
 802		 * parent pointers.
 803		 */
 804		if (xchk_pptr_looks_zapped(sc->ip)) {
 805			xchk_set_incomplete(sc);
 806			return -EBUSY;
 807		}
 808
 809		/*
 810		 * Create path walk contexts for each parent of the directory
 811		 * that is being scanned.  Directories are supposed to have
 812		 * only one parent, but this is how we detect multiple parents.
 813		 */
 814		error = xchk_xattr_walk(sc, sc->ip, xchk_dirtree_create_path,
 815				NULL, dl);
 816		if (error)
 817			return error;
 818
 819		xchk_dirtree_for_each_path(dl, path) {
 820			/* Load path components into dl->pptr/xname */
 821			error = xchk_dirtree_load_path(dl, path);
 822			if (error)
 823				return error;
 824
 825			/*
 826			 * Try to walk up each path to the root.  This enables
 827			 * us to find directory loops in ancestors, and the
 828			 * like.
 829			 */
 830			error = xchk_dirpath_walk_upwards(dl, path);
 831			if (error == -EFSCORRUPTED) {
 832				/*
 833				 * A parent pointer of @sc->ip is bad, don't
 834				 * bother continuing.
 835				 */
 836				break;
 837			}
 838			if (error == -ESTALE) {
 839				/* This had better be an invalidation. */
 840				ASSERT(dl->stale);
 841				break;
 842			}
 843			if (error)
 844				return error;
 845			if (dl->aborted)
 846				return 0;
 847		}
 848	} while (dl->stale);
 849
 850	return error;
 851}
 852
 853/*
 854 * Figure out what to do with the paths we tried to find.  Do not call this
 855 * if the scan results are stale.
 856 */
 857void
 858xchk_dirtree_evaluate(
 859	struct xchk_dirtree		*dl,
 860	struct xchk_dirtree_outcomes	*oc)
 861{
 862	struct xchk_dirpath		*path;
 863
 864	ASSERT(!dl->stale);
 865
 866	/* Scan the paths we have to decide what to do. */
 867	memset(oc, 0, sizeof(struct xchk_dirtree_outcomes));
 868	xchk_dirtree_for_each_path(dl, path) {
 869		trace_xchk_dirpath_evaluate_path(dl->sc, path->path_nr,
 870				path->nr_steps, path->outcome);
 871
 872		switch (path->outcome) {
 873		case XCHK_DIRPATH_SCANNING:
 874			/* shouldn't get here */
 875			ASSERT(0);
 876			break;
 877		case XCHK_DIRPATH_DELETE:
 878			/* This one is already going away. */
 879			oc->bad++;
 880			break;
 881		case XCHK_DIRPATH_CORRUPT:
 882		case XCHK_DIRPATH_LOOP:
 883			/* Couldn't find the end of this path. */
 884			oc->suspect++;
 885			break;
 886		case XCHK_DIRPATH_STALE:
 887			/* shouldn't get here either */
 888			ASSERT(0);
 889			break;
 890		case XCHK_DIRPATH_OK:
 891			/* This path got all the way to the root. */
 892			oc->good++;
 893			break;
 894		case XREP_DIRPATH_DELETING:
 895		case XREP_DIRPATH_DELETED:
 896		case XREP_DIRPATH_ADOPTING:
 897		case XREP_DIRPATH_ADOPTED:
 898			/* These should not be in progress! */
 899			ASSERT(0);
 900			break;
 901		}
 902	}
 903
 904	trace_xchk_dirtree_evaluate(dl, oc);
 905}
 906
 907/* Look for directory loops. */
 908int
 909xchk_dirtree(
 910	struct xfs_scrub		*sc)
 911{
 912	struct xchk_dirtree_outcomes	oc;
 913	struct xchk_dirtree		*dl = sc->buf;
 914	int				error;
 915
 916	/*
 917	 * Nondirectories do not point downwards to other files, so they cannot
 918	 * cause a cycle in the directory tree.
 919	 */
 920	if (!S_ISDIR(VFS_I(sc->ip)->i_mode))
 921		return -ENOENT;
 922
 923	ASSERT(xfs_has_parent(sc->mp));
 924
 925	/*
 926	 * Find the root of the directory tree.  Remember which directory to
 927	 * scan, because the hook doesn't detach until after sc->ip gets
 928	 * released during teardown.
 929	 */
 930	dl->root_ino = xchk_inode_rootdir_inum(sc->ip);
 931	dl->scan_ino = sc->ip->i_ino;
 932
 933	trace_xchk_dirtree_start(sc->ip, sc->sm, 0);
 934
 935	/*
 936	 * Hook into the directory entry code so that we can capture updates to
 937	 * paths that we have already scanned.  The scanner thread takes each
 938	 * directory's ILOCK, which means that any in-progress directory update
 939	 * will finish before we can scan the directory.
 940	 */
 941	ASSERT(sc->flags & XCHK_FSGATES_DIRENTS);
 942	xfs_dir_hook_setup(&dl->dhook, xchk_dirtree_live_update);
 943	error = xfs_dir_hook_add(sc->mp, &dl->dhook);
 944	if (error)
 945		goto out;
 946
 947	mutex_lock(&dl->lock);
 948
 949	/* Trace each parent pointer's path to the root. */
 950	error = xchk_dirtree_find_paths_to_root(dl);
 951	if (error == -EFSCORRUPTED || error == -ELNRNG || error == -ENOSR) {
 952		/*
 953		 * Don't bother walking the paths if the xattr structure or the
 954		 * parent pointers are corrupt; this scan cannot be completed
 955		 * without full information.
 956		 */
 957		xchk_ino_xref_set_corrupt(sc, sc->ip->i_ino);
 958		error = 0;
 959		goto out_scanlock;
 960	}
 961	if (error == -EBUSY) {
 962		/*
 963		 * We couldn't scan some directory's parent pointers because
 964		 * the attr fork looked like it had been zapped.  The
 965		 * scan was marked incomplete, so no further error code
 966		 * is necessary.
 967		 */
 968		error = 0;
 969		goto out_scanlock;
 970	}
 971	if (error)
 972		goto out_scanlock;
 973	if (dl->aborted) {
 974		xchk_set_incomplete(sc);
 975		goto out_scanlock;
 976	}
 977
 978	/* Assess what we found in our path evaluation. */
 979	xchk_dirtree_evaluate(dl, &oc);
 980	if (xchk_dirtree_parentless(dl)) {
 981		if (oc.good || oc.bad || oc.suspect)
 982			xchk_ino_set_corrupt(sc, sc->ip->i_ino);
 983	} else {
 984		if (oc.bad || oc.good + oc.suspect != 1)
 985			xchk_ino_set_corrupt(sc, sc->ip->i_ino);
 986		if (oc.suspect)
 987			xchk_ino_xref_set_corrupt(sc, sc->ip->i_ino);
 988	}
 989
 990out_scanlock:
 991	mutex_unlock(&dl->lock);
 992out:
 993	trace_xchk_dirtree_done(sc->ip, sc->sm, error);
 994	return error;
 995}
 996
 997/* Does the directory targetted by this scrub have no parents? */
 998bool
 999xchk_dirtree_parentless(const struct xchk_dirtree *dl)
1000{
1001	struct xfs_scrub	*sc = dl->sc;
1002
1003	if (xchk_inode_is_dirtree_root(sc->ip))
1004		return true;
1005	if (VFS_I(sc->ip)->i_nlink == 0)
1006		return true;
1007	return false;
1008}