51  * to detect a race.  If a race occurs in a path, we restart the scan.
53  * If the walk terminates without reaching the root, we know the path is
73 	struct xchk_dirpath	*path, *n;  in xchk_dirtree_buf_cleanup()  local
78 	xchk_dirtree_for_each_path_safe(dl, path, n) {  in xchk_dirtree_buf_cleanup()
79 		list_del_init(&path->list);  in xchk_dirtree_buf_cleanup()
80 		xino_bitmap_destroy(&path->seen_inodes);  in xchk_dirtree_buf_cleanup()
81 		kfree(path);  in xchk_dirtree_buf_cleanup()
119 	descr = xchk_xfile_ino_descr(sc, "dirtree path steps");  in xchk_setup_dirtree()
126 	descr = xchk_xfile_ino_descr(sc, "dirtree path names");  in xchk_setup_dirtree()
151  * Add the parent pointer described by @dl->pptr to the given path as a new
152  * step.  Returns -ELNRNG if the path is too deep.
158 	struct xchk_dirpath		*path,  in xchk_dirpath_append()  argument
169 	 * If this path is more than 2 billion steps long, this directory tree  in xchk_dirpath_append()
172 	if (path->nr_steps >= XFS_MAXLINK)  in xchk_dirpath_append()
179 	error = xino_bitmap_set(&path->seen_inodes, ip->i_ino);  in xchk_dirpath_append()
187 	path->nr_steps++;  in xchk_dirpath_append()
193  * scanning.  For each path created, we will eventually try to walk towards the
217 	struct xchk_dirpath		*path;  in xchk_dirtree_create_path()  local
242 	path = kmalloc(sizeof(struct xchk_dirpath), XCHK_GFP_FLAGS);  in xchk_dirtree_create_path()
243 	if (!path)  in xchk_dirtree_create_path()
246 	INIT_LIST_HEAD(&path->list);  in xchk_dirtree_create_path()
247 	xino_bitmap_init(&path->seen_inodes);  in xchk_dirtree_create_path()
248 	path->nr_steps = 0;  in xchk_dirtree_create_path()
249 	path->outcome = XCHK_DIRPATH_SCANNING;  in xchk_dirtree_create_path()
251 	error = xchk_dirpath_append(dl, sc->ip, path, &xname, rec);  in xchk_dirtree_create_path()
255 	path->first_step = xfarray_length(dl->path_steps) - 1;  in xchk_dirtree_create_path()
256 	path->second_step = XFARRAY_NULLIDX;  in xchk_dirtree_create_path()
257 	path->path_nr = dl->nr_paths;  in xchk_dirtree_create_path()
259 	list_add_tail(&path->list, &dl->path_list);  in xchk_dirtree_create_path()
263 	kfree(path);  in xchk_dirtree_create_path()
268  * Validate that the first step of this path still has a corresponding
273  * path into the parent pointer scratch pad.  This prepares us to walk up the
280 	struct xchk_dirpath		*path)  in xchk_dirpath_revalidate()  argument
287 	 * path.  If the parent pointer has disappeared on us, dump all the  in xchk_dirpath_revalidate()
293 		trace_xchk_dirpath_disappeared(dl->sc, sc->ip, path->path_nr,  in xchk_dirpath_revalidate()
294 				path->first_step, &dl->xname, &dl->pptr_rec);  in xchk_dirpath_revalidate()
303  * Walk the parent pointers of a directory at the end of a path and record
343 /* Set and log the outcome of a path walk. */
347 	struct xchk_dirpath		*path,  in xchk_dirpath_set_outcome()  argument
350 	trace_xchk_dirpath_set_outcome(dl->sc, path->path_nr, path->nr_steps,  in xchk_dirpath_set_outcome()
353 	path->outcome = outcome;  in xchk_dirpath_set_outcome()
357  * Scan the directory at the end of this path for its parent directory link.
358  * If we find one, extend the path.  Returns -ESTALE if the scan data out of
360  * the path got too deep.
365 	struct xchk_dirpath	*path,  in xchk_dirpath_step_up()  argument
387 	/* We've reached the root directory; the path is ok. */  in xchk_dirpath_step_up()
389 		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_OK);  in xchk_dirpath_step_up()
396 	 * this path.  in xchk_dirpath_step_up()
399 		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_DELETE);  in xchk_dirpath_step_up()
405 	 * We've seen this inode before during the path walk.  There's a loop  in xchk_dirpath_step_up()
409 	if (xino_bitmap_test(&path->seen_inodes, parent_ino)) {  in xchk_dirpath_step_up()
410 		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_LOOP);  in xchk_dirpath_step_up()
417 		trace_xchk_dirpath_badgen(dl->sc, dp, path->path_nr,  in xchk_dirpath_step_up()
418 				path->nr_steps, &dl->xname, &dl->pptr_rec);  in xchk_dirpath_step_up()
425 		trace_xchk_dirpath_nondir_parent(dl->sc, dp, path->path_nr,  in xchk_dirpath_step_up()
426 				path->nr_steps, &dl->xname, &dl->pptr_rec);  in xchk_dirpath_step_up()
433 		trace_xchk_dirpath_unlinked_parent(dl->sc, dp, path->path_nr,  in xchk_dirpath_step_up()
434 				path->nr_steps, &dl->xname, &dl->pptr_rec);  in xchk_dirpath_step_up()
441 		trace_xchk_dirpath_crosses_tree(dl->sc, dp, path->path_nr,  in xchk_dirpath_step_up()
442 				path->nr_steps, &dl->xname, &dl->pptr_rec);  in xchk_dirpath_step_up()
475 		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_CORRUPT);  in xchk_dirpath_step_up()
487 	trace_xchk_dirpath_found_next_step(sc, dp, path->path_nr,  in xchk_dirpath_step_up()
488 			path->nr_steps, &dl->xname, &dl->pptr_rec);  in xchk_dirpath_step_up()
490 	/* Append to the path steps */  in xchk_dirpath_step_up()
491 	error = xchk_dirpath_append(dl, dp, path, &dl->xname, &dl->pptr_rec);  in xchk_dirpath_step_up()
495 	if (path->second_step == XFARRAY_NULLIDX)  in xchk_dirpath_step_up()
496 		path->second_step = xfarray_length(dl->path_steps) - 1;  in xchk_dirpath_step_up()
507  * directory, recording path steps as we go.  The current path components are
511  * only if the direct parent pointer of @sc->ip associated with this path is
517 	struct xchk_dirpath	*path)  in xchk_dirpath_walk_upwards()  argument
525 	/* Reload the start of this path and make sure it's still there. */  in xchk_dirpath_walk_upwards()
526 	error = xchk_dirpath_revalidate(dl, path);  in xchk_dirpath_walk_upwards()
530 	trace_xchk_dirpath_walk_upwards(sc, sc->ip, path->path_nr, &dl->xname,  in xchk_dirpath_walk_upwards()
535 	 * Get rid of this path.  in xchk_dirpath_walk_upwards()
538 		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_DELETE);  in xchk_dirpath_walk_upwards()
557 	 * start of this path, which is a direct parent pointer of @sc->ip.  in xchk_dirpath_walk_upwards()
561 	error = xchk_dirpath_step_up(dl, path, is_metadir);  in xchk_dirpath_walk_upwards()
569 	 * Take steps upward from the second step in this path towards the  in xchk_dirpath_walk_upwards()
571 	 * *somewhere* in the path, but we don't need to stop scanning.  in xchk_dirpath_walk_upwards()
573 	while (!error && path->outcome == XCHK_DIRPATH_SCANNING)  in xchk_dirpath_walk_upwards()
574 		error = xchk_dirpath_step_up(dl, path, is_metadir);  in xchk_dirpath_walk_upwards()
580 		xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_CORRUPT);  in xchk_dirpath_walk_upwards()
589  * Decide if this path step has been touched by this live update.  Returns
595 	struct xchk_dirpath		*path,  in xchk_dirpath_step_is_stale()  argument
612 	 * this path step, the scan data is still ok.  in xchk_dirpath_step_is_stale()
637 	    path->outcome == XREP_DIRPATH_ADOPTING) {  in xchk_dirpath_step_is_stale()
638 		xchk_dirpath_set_outcome(dl, path, XREP_DIRPATH_ADOPTED);  in xchk_dirpath_step_is_stale()
643 	    path->outcome == XREP_DIRPATH_DELETING) {  in xchk_dirpath_step_is_stale()
644 		xchk_dirpath_set_outcome(dl, path, XREP_DIRPATH_DELETED);  in xchk_dirpath_step_is_stale()
649 	trace_xchk_dirpath_changed(dl->sc, path->path_nr, step_nr, p->dp,  in xchk_dirpath_step_is_stale()
655  * Decide if this path has been touched by this live update.  Returns 1 for
661 	struct xchk_dirpath		*path,  in xchk_dirpath_is_stale()  argument
665 	xfarray_idx_t			idx = path->first_step;  in xchk_dirpath_is_stale()
670 	 * The child being updated has not been seen by this path at all; this  in xchk_dirpath_is_stale()
671 	 * path cannot be stale.  in xchk_dirpath_is_stale()
673 	if (!xino_bitmap_test(&path->seen_inodes, p->ip->i_ino))  in xchk_dirpath_is_stale()
676 	ret = xchk_dirpath_step_is_stale(dl, path, 0, idx, p, &cursor);  in xchk_dirpath_is_stale()
680 	for (i = 1, idx = path->second_step; i < path->nr_steps; i++, idx++) {  in xchk_dirpath_is_stale()
681 		ret = xchk_dirpath_step_is_stale(dl, path, i, idx, p, &cursor);  in xchk_dirpath_is_stale()
701 	struct xchk_dirpath		*path;  in xchk_dirtree_live_update()  local
714 	xchk_dirtree_for_each_path(dl, path) {  in xchk_dirtree_live_update()
715 		ret = xchk_dirpath_is_stale(dl, path, p);  in xchk_dirtree_live_update()
731 /* Delete all the collected path information. */
737 	struct xchk_dirpath	*path, *n;  in xchk_dirtree_reset()  local
741 	xchk_dirtree_for_each_path_safe(dl, path, n) {  in xchk_dirtree_reset()
742 		list_del_init(&path->list);  in xchk_dirtree_reset()
743 		xino_bitmap_destroy(&path->seen_inodes);  in xchk_dirtree_reset()
744 		kfree(path);  in xchk_dirtree_reset()
755  * Load the name/pptr from the first step in this path into @dl->pptr_rec and
761 	struct xchk_dirpath		*path)  in xchk_dirtree_load_path()  argument
766 	error = xfarray_load(dl->path_steps, path->first_step, &step);  in xchk_dirtree_load_path()
780  * For each parent pointer of this subdir, trace a path upwards towards the
783  * path was too deep; -ENOSR if there were too many parent pointers; or
791 	struct xchk_dirpath	*path;  in xchk_dirtree_find_paths_to_root()  local
811 		 * Create path walk contexts for each parent of the directory  in xchk_dirtree_find_paths_to_root()
820 		xchk_dirtree_for_each_path(dl, path) {  in xchk_dirtree_find_paths_to_root()
821 			/* Load path components into dl->pptr/xname */  in xchk_dirtree_find_paths_to_root()
822 			error = xchk_dirtree_load_path(dl, path);  in xchk_dirtree_find_paths_to_root()
827 			 * Try to walk up each path to the root.  This enables  in xchk_dirtree_find_paths_to_root()
831 			error = xchk_dirpath_walk_upwards(dl, path);  in xchk_dirtree_find_paths_to_root()
863 	struct xchk_dirpath		*path;  in xchk_dirtree_evaluate()  local
869 	xchk_dirtree_for_each_path(dl, path) {  in xchk_dirtree_evaluate()
870 		trace_xchk_dirpath_evaluate_path(dl->sc, path->path_nr,  in xchk_dirtree_evaluate()
871 				path->nr_steps, path->outcome);  in xchk_dirtree_evaluate()
873 		switch (path->outcome) {  in xchk_dirtree_evaluate()
884 			/* Couldn't find the end of this path. */  in xchk_dirtree_evaluate()
892 			/* This path got all the way to the root. */  in xchk_dirtree_evaluate()
950 	/* Trace each parent pointer's path to the root. */  in xchk_dirtree()
979 	/* Assess what we found in our path evaluation. */  in xchk_dirtree()