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