/* * 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.
*/
/* * 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, conststruct xfs_name *name, conststruct xfs_parent_rec *pptr)
{ struct xchk_dirpath_step step = {
.pptr_rec = *pptr, /* struct copy */
.name_len = name->len,
}; int error;
/* * If this path is more than 2 billion steps long, this directory tree * is too far gone to fix.
*/ if (path->nr_steps >= XFS_MAXLINK) return -ELNRNG;
error = xfblob_storename(dl->path_names, &step.name_cookie, name); if (error) return error;
error = xino_bitmap_set(&path->seen_inodes, ip->i_ino); if (error) return error;
error = xfarray_append(dl->path_steps, &step); if (error) return error;
path->nr_steps++; return 0;
}
/* * 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.
*/ STATICint
xchk_dirtree_create_path( struct xfs_scrub *sc, struct xfs_inode *ip, unsignedint attr_flags, constunsignedchar *name, unsignedint namelen, constvoid *value, unsignedint valuelen, void *priv)
{ struct xfs_name xname = {
.name = name,
.len = namelen,
}; struct xchk_dirtree *dl = priv; struct xchk_dirpath *path; conststruct xfs_parent_rec *rec = value; int error;
/* * If there are more than 2 billion actual parent pointers for this * subdirectory, this fs is too far gone to fix.
*/ if (dl->nr_paths >= XFS_MAXLINK) return -ENOSR;
/* * Create a new xchk_path structure to remember this parent pointer * and record the first name step.
*/
path = kmalloc(sizeof(struct xchk_dirpath), XCHK_GFP_FLAGS); if (!path) return -ENOMEM;
/* * 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.
*/ STATICint
xchk_dirpath_revalidate( struct xchk_dirtree *dl, struct xchk_dirpath *path)
{ struct xfs_scrub *sc = dl->sc; int error;
/* * Look up the parent pointer that corresponds to the start of this * path. If the parent pointer has disappeared on us, dump all the * scan results and try again.
*/
error = xfs_parent_lookup(sc->tp, sc->ip, &dl->xname, &dl->pptr_rec,
&dl->pptr_args); if (error == -ENOATTR) {
trace_xchk_dirpath_disappeared(dl->sc, sc->ip, path->path_nr,
path->first_step, &dl->xname, &dl->pptr_rec);
dl->stale = true; return -ESTALE;
}
return error;
}
/* * 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.
*/ STATICint
xchk_dirpath_find_next_step( struct xfs_scrub *sc, struct xfs_inode *ip, unsignedint attr_flags, constunsignedchar *name, unsignedint namelen, constvoid *value, unsignedint valuelen, void *priv)
{ struct xchk_dirtree *dl = priv; conststruct xfs_parent_rec *rec = value; int error;
/* * If we've already set @dl->pptr_rec, then this directory has multiple * parents. Signal this back to the caller via -EMLINK.
*/ if (dl->parents_found > 0) return -EMLINK;
/* Set and log the outcome of a path walk. */ staticinlinevoid
xchk_dirpath_set_outcome( struct xchk_dirtree *dl, struct xchk_dirpath *path, enum xchk_dirpath_outcome outcome)
{
trace_xchk_dirpath_set_outcome(dl->sc, path->path_nr, path->nr_steps,
outcome);
path->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.
*/ STATICint
xchk_dirpath_step_up( struct xchk_dirtree *dl, struct xchk_dirpath *path, bool is_metadir)
{ struct xfs_scrub *sc = dl->sc; struct xfs_inode *dp;
xfs_ino_t parent_ino = be64_to_cpu(dl->pptr_rec.p_ino); unsignedint lock_mode; int error;
/* Grab and lock the parent directory. */
error = xchk_iget(sc, parent_ino, &dp); if (error) return error;
if (dl->stale) {
error = -ESTALE; goto out_scanlock;
}
/* We've reached the root directory; the path is ok. */ if (parent_ino == dl->root_ino) {
xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_OK);
error = 0; goto out_scanlock;
}
/* * The inode being scanned is its own distant ancestor! Get rid of * this path.
*/ if (parent_ino == sc->ip->i_ino) {
xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_DELETE);
error = 0; goto out_scanlock;
}
/* * We've seen this inode before during the path walk. There's a loop * above us in the directory tree. This probably means that we cannot * continue, but let's keep walking paths to get a full picture.
*/ if (xino_bitmap_test(&path->seen_inodes, parent_ino)) {
xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_LOOP);
error = 0; goto out_scanlock;
}
/* The handle encoded in the parent pointer must match. */ if (VFS_I(dp)->i_generation != be32_to_cpu(dl->pptr_rec.p_gen)) {
trace_xchk_dirpath_badgen(dl->sc, dp, path->path_nr,
path->nr_steps, &dl->xname, &dl->pptr_rec);
error = -EFSCORRUPTED; goto out_scanlock;
}
/* Parent pointer must point up to a directory. */ if (!S_ISDIR(VFS_I(dp)->i_mode)) {
trace_xchk_dirpath_nondir_parent(dl->sc, dp, path->path_nr,
path->nr_steps, &dl->xname, &dl->pptr_rec);
error = -EFSCORRUPTED; goto out_scanlock;
}
/* Parent cannot be an unlinked directory. */ if (VFS_I(dp)->i_nlink == 0) {
trace_xchk_dirpath_unlinked_parent(dl->sc, dp, path->path_nr,
path->nr_steps, &dl->xname, &dl->pptr_rec);
error = -EFSCORRUPTED; goto out_scanlock;
}
/* Parent must be in the same directory tree. */ if (is_metadir != xfs_is_metadir_inode(dp)) {
trace_xchk_dirpath_crosses_tree(dl->sc, dp, path->path_nr,
path->nr_steps, &dl->xname, &dl->pptr_rec);
error = -EFSCORRUPTED; goto out_scanlock;
}
/* * If the extended attributes look as though they has been zapped by * the inode record repair code, we cannot scan for parent pointers.
*/ if (xchk_pptr_looks_zapped(dp)) {
error = -EBUSY;
xchk_set_incomplete(sc); goto out_scanlock;
}
/* * Walk the parent pointers of @dp to find the parent of this directory * to find the next step in our walk. If we find that @dp has exactly * one parent, the parent pointer information will be stored in * @dl->pptr_rec. This prepares us for the next step of the walk.
*/
mutex_unlock(&dl->lock);
dl->parents_found = 0;
error = xchk_xattr_walk(sc, dp, xchk_dirpath_find_next_step, NULL, dl);
mutex_lock(&dl->lock); if (error == -EFSCORRUPTED || error == -EMLINK ||
(!error && dl->parents_found == 0)) { /* * Further up the directory tree from @sc->ip, we found a * corrupt parent pointer, multiple parent pointers while * finding this directory's parent, or zero parents despite * having a nonzero link count. Keep looking for other paths.
*/
xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_CORRUPT);
error = 0; goto out_scanlock;
} if (error) goto out_scanlock;
if (dl->stale) {
error = -ESTALE; goto out_scanlock;
}
/* * 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.
*/ STATICint
xchk_dirpath_walk_upwards( struct xchk_dirtree *dl, struct xchk_dirpath *path)
{ struct xfs_scrub *sc = dl->sc; bool is_metadir; int error;
ASSERT(sc->ilock_flags & XFS_ILOCK_EXCL);
/* Reload the start of this path and make sure it's still there. */
error = xchk_dirpath_revalidate(dl, path); if (error) return error;
/* * The inode being scanned is its own direct ancestor! * Get rid of this path.
*/ if (be64_to_cpu(dl->pptr_rec.p_ino) == sc->ip->i_ino) {
xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_DELETE); return 0;
}
/* * Drop ILOCK_EXCL on the inode being scanned. We still hold * IOLOCK_EXCL on it, so it cannot move around or be renamed. * * Beyond this point we're walking up the directory tree, which means * that we can acquire and drop the ILOCK on an alias of sc->ip. The * ILOCK state is no longer tracked in the scrub context. Hence we * must drop @sc->ip's ILOCK during the walk.
*/
is_metadir = xfs_is_metadir_inode(sc->ip);
mutex_unlock(&dl->lock);
xchk_iunlock(sc, XFS_ILOCK_EXCL);
/* * Take the first step in the walk towards the root by checking the * start of this path, which is a direct parent pointer of @sc->ip. * If we see any kind of error here (including corruptions), the parent * pointer of @sc->ip is corrupt. Stop the whole scan.
*/
error = xchk_dirpath_step_up(dl, path, is_metadir); if (error) {
xchk_ilock(sc, XFS_ILOCK_EXCL);
mutex_lock(&dl->lock); return error;
}
/* * Take steps upward from the second step in this path towards the * root. If we hit corruption errors here, there's a problem * *somewhere* in the path, but we don't need to stop scanning.
*/ while (!error && path->outcome == XCHK_DIRPATH_SCANNING)
error = xchk_dirpath_step_up(dl, path, is_metadir);
/* Retake the locks we had, mark paths, etc. */
xchk_ilock(sc, XFS_ILOCK_EXCL);
mutex_lock(&dl->lock); if (error == -EFSCORRUPTED) {
xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_CORRUPT);
error = 0;
} if (!error && dl->stale) return -ESTALE; return error;
}
/* * Decide if this path step has been touched by this live update. Returns * 1 for yes, 0 for no, or a negative errno.
*/ STATICint
xchk_dirpath_step_is_stale( struct xchk_dirtree *dl, struct xchk_dirpath *path, unsignedint step_nr,
xfarray_idx_t step_idx, struct xfs_dir_update_params *p,
xfs_ino_t *cursor)
{ struct xchk_dirpath_step step;
xfs_ino_t child_ino = *cursor; int error;
/* * If the parent and child being updated are not the ones mentioned in * this path step, the scan data is still ok.
*/ if (p->ip->i_ino != child_ino || p->dp->i_ino != *cursor) return 0;
/* * If the dirent name lengths or byte sequences are different, the scan * data is still ok.
*/ if (p->name->len != step.name_len) return 0;
error = xfblob_loadname(dl->path_names, step.name_cookie,
&dl->hook_xname, step.name_len); if (error) return error;
if (memcmp(dl->hook_xname.name, p->name->name, p->name->len) != 0) return 0;
/* * If the update comes from the repair code itself, walk the state * machine forward.
*/ if (p->ip->i_ino == dl->scan_ino &&
path->outcome == XREP_DIRPATH_ADOPTING) {
xchk_dirpath_set_outcome(dl, path, XREP_DIRPATH_ADOPTED); return 0;
}
/* Exact match, scan data is out of date. */
trace_xchk_dirpath_changed(dl->sc, path->path_nr, step_nr, p->dp,
p->ip, p->name); return 1;
}
/* * Decide if this path has been touched by this live update. Returns 1 for * yes, 0 for no, or a negative errno.
*/ STATICint
xchk_dirpath_is_stale( struct xchk_dirtree *dl, struct xchk_dirpath *path, struct xfs_dir_update_params *p)
{
xfs_ino_t cursor = dl->scan_ino;
xfarray_idx_t idx = path->first_step; unsignedint i; int ret;
/* * The child being updated has not been seen by this path at all; this * path cannot be stale.
*/ if (!xino_bitmap_test(&path->seen_inodes, p->ip->i_ino)) return 0;
ret = xchk_dirpath_step_is_stale(dl, path, 0, idx, p, &cursor); if (ret != 0) return ret;
for (i = 1, idx = path->second_step; i < path->nr_steps; i++, idx++) {
ret = xchk_dirpath_step_is_stale(dl, path, i, idx, p, &cursor); if (ret != 0) return ret;
}
return 0;
}
/* * Decide if a directory update from the regular filesystem touches any of the * paths we've scanned, and invalidate the scan data if true.
*/ STATICint
xchk_dirtree_live_update( struct notifier_block *nb, unsignedlong action, void *data)
{ struct xfs_dir_update_params *p = data; struct xchk_dirtree *dl; struct xchk_dirpath *path; int ret;
/* * Load the name/pptr from the first step in this path into @dl->pptr_rec and * @dl->xname.
*/ STATICint
xchk_dirtree_load_path( struct xchk_dirtree *dl, struct xchk_dirpath *path)
{ struct xchk_dirpath_step step; int error;
error = xfarray_load(dl->path_steps, path->first_step, &step); if (error) return error;
error = xfblob_loadname(dl->path_names, step.name_cookie, &dl->xname,
step.name_len); if (error) return error;
/* * 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)
{ struct xfs_scrub *sc = dl->sc; struct xchk_dirpath *path; int error = 0;
do { if (xchk_should_terminate(sc, &error)) return error;
xchk_dirtree_reset(dl);
/* * If the extended attributes look as though they has been * zapped by the inode record repair code, we cannot scan for * parent pointers.
*/ if (xchk_pptr_looks_zapped(sc->ip)) {
xchk_set_incomplete(sc); return -EBUSY;
}
/* * Create path walk contexts for each parent of the directory * that is being scanned. Directories are supposed to have * only one parent, but this is how we detect multiple parents.
*/
error = xchk_xattr_walk(sc, sc->ip, xchk_dirtree_create_path,
NULL, dl); if (error) return error;
xchk_dirtree_for_each_path(dl, path) { /* Load path components into dl->pptr/xname */
error = xchk_dirtree_load_path(dl, path); if (error) return error;
/* * Try to walk up each path to the root. This enables * us to find directory loops in ancestors, and the * like.
*/
error = xchk_dirpath_walk_upwards(dl, path); if (error == -EFSCORRUPTED) { /* * A parent pointer of @sc->ip is bad, don't * bother continuing.
*/ break;
} if (error == -ESTALE) { /* This had better be an invalidation. */
ASSERT(dl->stale); break;
} if (error) return error; if (dl->aborted) return 0;
}
} while (dl->stale);
return error;
}
/* * 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)
{ struct xchk_dirpath *path;
ASSERT(!dl->stale);
/* Scan the paths we have to decide what to do. */
memset(oc, 0, sizeof(struct xchk_dirtree_outcomes));
xchk_dirtree_for_each_path(dl, path) {
trace_xchk_dirpath_evaluate_path(dl->sc, path->path_nr,
path->nr_steps, path->outcome);
switch (path->outcome) { case XCHK_DIRPATH_SCANNING: /* shouldn't get here */
ASSERT(0); break; case XCHK_DIRPATH_DELETE: /* This one is already going away. */
oc->bad++; break; case XCHK_DIRPATH_CORRUPT: case XCHK_DIRPATH_LOOP: /* Couldn't find the end of this path. */
oc->suspect++; break; case XCHK_DIRPATH_STALE: /* shouldn't get here either */
ASSERT(0); break; case XCHK_DIRPATH_OK: /* This path got all the way to the root. */
oc->good++; break; case XREP_DIRPATH_DELETING: case XREP_DIRPATH_DELETED: case XREP_DIRPATH_ADOPTING: case XREP_DIRPATH_ADOPTED: /* These should not be in progress! */
ASSERT(0); break;
}
}
trace_xchk_dirtree_evaluate(dl, oc);
}
/* Look for directory loops. */ int
xchk_dirtree( struct xfs_scrub *sc)
{ struct xchk_dirtree_outcomes oc; struct xchk_dirtree *dl = sc->buf; int error;
/* * Nondirectories do not point downwards to other files, so they cannot * cause a cycle in the directory tree.
*/ if (!S_ISDIR(VFS_I(sc->ip)->i_mode)) return -ENOENT;
ASSERT(xfs_has_parent(sc->mp));
/* * Find the root of the directory tree. Remember which directory to * scan, because the hook doesn't detach until after sc->ip gets * released during teardown.
*/
dl->root_ino = xchk_inode_rootdir_inum(sc->ip);
dl->scan_ino = sc->ip->i_ino;
trace_xchk_dirtree_start(sc->ip, sc->sm, 0);
/* * Hook into the directory entry code so that we can capture updates to * paths that we have already scanned. The scanner thread takes each * directory's ILOCK, which means that any in-progress directory update * will finish before we can scan the directory.
*/
ASSERT(sc->flags & XCHK_FSGATES_DIRENTS);
xfs_dir_hook_setup(&dl->dhook, xchk_dirtree_live_update);
error = xfs_dir_hook_add(sc->mp, &dl->dhook); if (error) goto out;
mutex_lock(&dl->lock);
/* Trace each parent pointer's path to the root. */
error = xchk_dirtree_find_paths_to_root(dl); if (error == -EFSCORRUPTED || error == -ELNRNG || error == -ENOSR) { /* * Don't bother walking the paths if the xattr structure or the * parent pointers are corrupt; this scan cannot be completed * without full information.
*/
xchk_ino_xref_set_corrupt(sc, sc->ip->i_ino);
error = 0; goto out_scanlock;
} if (error == -EBUSY) { /* * We couldn't scan some directory's parent pointers because * the attr fork looked like it had been zapped. The * scan was marked incomplete, so no further error code * is necessary.
*/
error = 0; goto out_scanlock;
} if (error) goto out_scanlock; if (dl->aborted) {
xchk_set_incomplete(sc); goto out_scanlock;
}
/* Assess what we found in our path evaluation. */
xchk_dirtree_evaluate(dl, &oc); if (xchk_dirtree_parentless(dl)) { if (oc.good || oc.bad || oc.suspect)
xchk_ino_set_corrupt(sc, sc->ip->i_ino);
} else { if (oc.bad || oc.good + oc.suspect != 1)
xchk_ino_set_corrupt(sc, sc->ip->i_ino); if (oc.suspect)
xchk_ino_xref_set_corrupt(sc, sc->ip->i_ino);
}
/* Does the directory targetted by this scrub have no parents? */ bool
xchk_dirtree_parentless(conststruct xchk_dirtree *dl)
{ struct xfs_scrub *sc = dl->sc;
if (xchk_inode_is_dirtree_root(sc->ip)) returntrue; if (VFS_I(sc->ip)->i_nlink == 0) returntrue; returnfalse;
}
Messung V0.5
¤ Dauer der Verarbeitung: 0.2 Sekunden
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
