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