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 13596435 : xchk_dirtree_buf_cleanup(
70 : void *buf)
71 : {
72 13596435 : struct xchk_dirtree *dl = buf;
73 13596435 : struct xchk_dirpath *path, *n;
74 :
75 13596435 : if (dl->scan_ino != NULLFSINO)
76 13596450 : xfs_dir_hook_del(dl->sc->mp, &dl->hooks);
77 :
78 27181390 : xchk_dirtree_for_each_path_safe(dl, path, n) {
79 13584272 : list_del_init(&path->list);
80 13584136 : xino_bitmap_destroy(&path->seen_inodes);
81 13583215 : kfree(path);
82 : }
83 :
84 13597118 : xfblob_destroy(dl->path_names);
85 13597173 : xfarray_destroy(dl->path_steps);
86 13597258 : mutex_destroy(&dl->lock);
87 13596895 : }
88 :
89 : /* Set us up to look for directory loops. */
90 : int
91 13597685 : xchk_setup_dirtree(
92 : struct xfs_scrub *sc)
93 : {
94 13597685 : struct xchk_dirtree *dl;
95 13597685 : char *descr;
96 13597685 : int error;
97 :
98 13597685 : xchk_fsgates_enable(sc, XCHK_FSGATES_DIRENTS);
99 :
100 27188844 : if (xchk_could_repair(sc)) {
101 169534 : error = xrep_setup_dirtree(sc);
102 169597 : if (error)
103 : return error;
104 : }
105 :
106 13594485 : dl = kvzalloc(sizeof(struct xchk_dirtree), XCHK_GFP_FLAGS);
107 13583283 : if (!dl)
108 : return -ENOMEM;
109 13583283 : dl->sc = sc;
110 13583283 : INIT_LIST_HEAD(&dl->path_list);
111 13583283 : dl->root_ino = NULLFSINO;
112 13583283 : dl->scan_ino = NULLFSINO;
113 13583283 : dl->parent_ino = NULLFSINO;
114 :
115 13583283 : mutex_init(&dl->lock);
116 :
117 13583527 : descr = xchk_xfile_ino_descr(sc, "dirtree path steps");
118 13364119 : error = xfarray_create(descr, 0, sizeof(struct xchk_dirpath_step),
119 : &dl->path_steps);
120 13557127 : kfree(descr);
121 13571923 : if (error)
122 0 : goto out_dl;
123 :
124 13571923 : descr = xchk_xfile_ino_descr(sc, "dirtree path names");
125 13549188 : error = xfblob_create(descr, &dl->path_names);
126 13590341 : kfree(descr);
127 13593027 : if (error)
128 0 : goto out_steps;
129 :
130 13593027 : error = xchk_setup_inode_contents(sc, 0);
131 13579297 : if (error)
132 7 : goto out_names;
133 :
134 13579290 : sc->buf = dl;
135 13579290 : sc->buf_cleanup = xchk_dirtree_buf_cleanup;
136 13579290 : return 0;
137 :
138 : out_names:
139 7 : xfblob_destroy(dl->path_names);
140 7 : out_steps:
141 7 : xfarray_destroy(dl->path_steps);
142 7 : out_dl:
143 7 : mutex_destroy(&dl->lock);
144 7 : kvfree(dl);
145 7 : 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 1188484112 : 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 1188484112 : struct xchk_dirpath_step step = {
160 1188484112 : .parent_ino = pptr->p_ino,
161 1188484112 : .parent_gen = pptr->p_gen,
162 1188484112 : .name_len = pptr->p_namelen,
163 : };
164 1188484112 : 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 1188484112 : if (path->nr_steps >= XFS_MAXLINK)
171 : return -ELNRNG;
172 :
173 1188484112 : error = xfblob_store(dl->path_names, &step.name_cookie,
174 1188484112 : dl->pptr.p_name, dl->pptr.p_namelen);
175 1190217516 : if (error)
176 : return error;
177 :
178 1190223602 : error = xino_bitmap_set(&path->seen_inodes, ip->i_ino);
179 1187746206 : if (error)
180 : return error;
181 :
182 1187797680 : error = xfarray_append(dl->path_steps, &step);
183 1190061183 : if (error)
184 : return error;
185 :
186 1190061183 : path->nr_steps++;
187 1190061183 : 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 13577663 : 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 13577663 : struct xchk_dirtree *dl = priv;
208 13577663 : struct xchk_dirpath *path;
209 13577663 : 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 13577663 : if (dl->nr_paths >= XFS_MAXLINK)
216 : return -ENOSR;
217 :
218 13577663 : 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 13577217 : path = kmalloc(sizeof(struct xchk_dirpath), XCHK_GFP_FLAGS);
225 13575779 : if (!path)
226 : return -ENOMEM;
227 :
228 13575779 : INIT_LIST_HEAD(&path->list);
229 13575779 : xino_bitmap_init(&path->seen_inodes);
230 13573402 : path->nr_steps = 0;
231 13573402 : path->outcome = XCHK_DIRPATH_SCANNING;
232 :
233 13573402 : error = xchk_dirpath_append(dl, sc->ip, path, pptr);
234 13565436 : if (error)
235 0 : goto out_path;
236 :
237 13565436 : path->first_step = xfarray_length(dl->path_steps) - 1;
238 13561117 : path->second_step = XFARRAY_NULLIDX;
239 13561117 : path->path_nr = dl->nr_paths;
240 :
241 13561117 : list_add_tail(&path->list, &dl->path_list);
242 13558345 : dl->nr_paths++;
243 13558345 : 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 13561639 : xchk_dirpath_revalidate(
261 : struct xchk_dirtree *dl,
262 : struct xchk_dirpath *path)
263 : {
264 13561639 : struct xchk_dirpath_step step;
265 13561639 : struct xfs_scrub *sc = dl->sc;
266 13561639 : int error;
267 :
268 13561639 : error = xfarray_load(dl->path_steps, path->first_step, &step);
269 13580872 : 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 13580428 : dl->pptr.p_ino = step.parent_ino;
277 13580428 : dl->pptr.p_gen = step.parent_gen;
278 13580428 : dl->pptr.p_namelen = step.name_len;
279 :
280 13580428 : error = xfblob_load(dl->path_names, step.name_cookie, dl->pptr.p_name,
281 : step.name_len);
282 13586775 : if (error)
283 : return error;
284 13586776 : 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 13581685 : error = xfs_parent_lookup(sc->tp, sc->ip, &dl->pptr, &dl->scratch);
292 13477477 : 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 1174185466 : 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 1174185466 : 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 1174185466 : if (*parents_found > 0)
320 : return -EMLINK;
321 :
322 1174185466 : (*parents_found)++;
323 1174185466 : 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 13584357 : trace_xchk_dirpath_set_outcome(dl->sc, path->path_nr, path->nr_steps,
334 : outcome);
335 :
336 13584352 : 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 1189976497 : xchk_dirpath_step_up(
347 : struct xchk_dirtree *dl,
348 : struct xchk_dirpath *path)
349 : {
350 1189976497 : struct xfs_scrub *sc = dl->sc;
351 1189976497 : struct xfs_inode *dp;
352 1189976497 : unsigned int lock_mode;
353 1189976497 : unsigned int parents_found = 0;
354 1189976497 : int error;
355 :
356 : /* Grab and lock the parent directory. */
357 1189976497 : error = xchk_iget(sc, dl->pptr.p_ino, &dp);
358 1188437009 : if (error)
359 : return error;
360 :
361 1188471950 : lock_mode = xfs_ilock_attr_map_shared(dp);
362 1189481002 : mutex_lock(&dl->lock);
363 :
364 1190095946 : if (dl->stale) {
365 2469 : error = -ESTALE;
366 2469 : goto out_scanlock;
367 : }
368 :
369 : /* We've reached the root directory; the path is ok. */
370 1190093477 : if (dl->pptr.p_ino == dl->root_ino) {
371 13584357 : xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_OK);
372 13584352 : error = 0;
373 13584352 : goto out_scanlock;
374 : }
375 :
376 : /*
377 : * The inode being scanned is its own distant ancestor! Get rid of
378 : * this path.
379 : */
380 1176509120 : if (dl->pptr.p_ino == sc->ip->i_ino) {
381 0 : xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_DELETE);
382 0 : error = 0;
383 0 : goto out_scanlock;
384 : }
385 :
386 : /*
387 : * We've seen this inode before during the path walk. There's a loop
388 : * above us in the directory tree. This probably means that we cannot
389 : * continue, but let's keep walking paths to get a full picture.
390 : */
391 1176509120 : if (xino_bitmap_test(&path->seen_inodes, dl->pptr.p_ino)) {
392 0 : xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_LOOP);
393 0 : error = 0;
394 0 : goto out_scanlock;
395 : }
396 :
397 : /* The handle encoded in the parent pointer must match. */
398 1174352681 : if (VFS_I(dp)->i_generation != dl->pptr.p_gen) {
399 0 : trace_xchk_dirpath_badgen(dl->sc, dp, path->path_nr,
400 0 : path->nr_steps, &dl->pptr);
401 0 : error = -EFSCORRUPTED;
402 0 : goto out_scanlock;
403 : }
404 :
405 : /* Parent pointer must point up to a directory. */
406 1174352681 : if (!S_ISDIR(VFS_I(dp)->i_mode)) {
407 0 : trace_xchk_dirpath_nondir_parent(dl->sc, dp, path->path_nr,
408 0 : path->nr_steps, &dl->pptr);
409 0 : error = -EFSCORRUPTED;
410 0 : goto out_scanlock;
411 : }
412 :
413 : /* Parent cannot be an unlinked directory. */
414 1174352681 : if (VFS_I(dp)->i_nlink == 0) {
415 0 : trace_xchk_dirpath_unlinked_parent(dl->sc, dp, path->path_nr,
416 0 : path->nr_steps, &dl->pptr);
417 0 : error = -EFSCORRUPTED;
418 0 : goto out_scanlock;
419 : }
420 :
421 : /*
422 : * Walk the parent pointers of @dp to find the parent of this directory
423 : * to find the next step in our walk. If we find that @dp has exactly
424 : * one parent, the parent pointer information will be in @dl->pptr.
425 : */
426 1174352681 : mutex_unlock(&dl->lock);
427 1172610282 : error = xchk_pptr_walk(sc, dp, xchk_dirpath_find_next_step, &dl->pptr,
428 : &parents_found);
429 1174165074 : mutex_lock(&dl->lock);
430 1175000357 : if (error == -EFSCORRUPTED || error == -EMLINK ||
431 1175414150 : (!error && parents_found == 0)) {
432 : /*
433 : * Further up the directory tree from @sc->ip, we found a
434 : * corrupt parent pointer, multiple parent pointers while
435 : * finding this directory's parent, or zero parents despite
436 : * having a nonzero link count. Keep looking for other paths.
437 : */
438 0 : xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_CORRUPT);
439 0 : error = 0;
440 0 : goto out_scanlock;
441 : }
442 1175000357 : if (error)
443 0 : goto out_scanlock;
444 :
445 1175000357 : if (dl->stale) {
446 413 : error = -ESTALE;
447 413 : goto out_scanlock;
448 : }
449 :
450 1174999944 : trace_xchk_dirpath_found_next_step(sc, dp, path->path_nr,
451 : path->nr_steps, &dl->pptr);
452 :
453 : /* Append to the path steps */
454 1174990484 : error = xchk_dirpath_append(dl, dp, path, &dl->pptr);
455 1176486654 : if (error)
456 0 : goto out_scanlock;
457 :
458 1176486654 : if (path->second_step == XFARRAY_NULLIDX)
459 13554841 : path->second_step = xfarray_length(dl->path_steps) - 1;
460 :
461 1162931813 : out_scanlock:
462 1190073021 : mutex_unlock(&dl->lock);
463 1187333418 : xfs_iunlock(dp, lock_mode);
464 1189904896 : xchk_irele(sc, dp);
465 1189904896 : return error;
466 : }
467 :
468 : /*
469 : * Walk the directory tree upwards towards what is hopefully the root
470 : * directory, recording path steps as we go. Returns -ESTALE if the scan data
471 : * are out of date. Returns -EFSCORRUPTED only if the direct parent pointer of
472 : * @sc->ip associated with this path is corrupt.
473 : */
474 : STATIC int
475 13566422 : xchk_dirpath_walk_upwards(
476 : struct xchk_dirtree *dl,
477 : struct xchk_dirpath *path)
478 : {
479 13566422 : struct xfs_scrub *sc = dl->sc;
480 13566422 : int error;
481 :
482 13566422 : ASSERT(sc->ilock_flags & XFS_ILOCK_EXCL);
483 :
484 : /* Reload the start of this path and make sure it's still there. */
485 13566422 : error = xchk_dirpath_revalidate(dl, path);
486 13490731 : if (error)
487 : return error;
488 :
489 13502336 : trace_xchk_dirpath_walk_upwards(sc, sc->ip, path->path_nr, &dl->pptr);
490 :
491 : /*
492 : * The inode being scanned is its own direct ancestor!
493 : * Get rid of this path.
494 : */
495 13506750 : if (dl->pptr.p_ino == sc->ip->i_ino) {
496 0 : xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_DELETE);
497 0 : return 0;
498 : }
499 :
500 : /*
501 : * Drop ILOCK_EXCL on the inode being scanned. We still hold
502 : * IOLOCK_EXCL on it, so it cannot move around or be renamed.
503 : *
504 : * Beyond this point we're walking up the directory tree, which means
505 : * that we can acquire and drop the ILOCK on an alias of sc->ip. The
506 : * ILOCK state is no longer tracked in the scrub context. Hence we
507 : * must drop @sc->ip's ILOCK during the walk.
508 : */
509 13506750 : mutex_unlock(&dl->lock);
510 13457265 : xchk_iunlock(sc, XFS_ILOCK_EXCL);
511 :
512 : /*
513 : * Take the first step in the walk towards the root by checking the
514 : * start of this path, which is a direct parent pointer of @sc->ip.
515 : * If we see any kind of error here (including corruptions), the parent
516 : * pointer of @sc->ip is corrupt. Stop the whole scan.
517 : */
518 13499047 : error = xchk_dirpath_step_up(dl, path);
519 13583759 : if (error) {
520 0 : xchk_ilock(sc, XFS_ILOCK_EXCL);
521 0 : mutex_lock(&dl->lock);
522 0 : return error;
523 : }
524 :
525 : /*
526 : * Take steps upward from the second step in this path towards the
527 : * root. If we hit corruption errors here, there's a problem
528 : * *somewhere* in the path, but we don't need to stop scanning.
529 : */
530 1190134906 : while (!error && path->outcome == XCHK_DIRPATH_SCANNING)
531 1176547773 : error = xchk_dirpath_step_up(dl, path);
532 :
533 : /* Retake the locks we had, mark paths, etc. */
534 13587133 : xchk_ilock(sc, XFS_ILOCK_EXCL);
535 13587240 : mutex_lock(&dl->lock);
536 13587255 : if (error == -EFSCORRUPTED) {
537 0 : xchk_dirpath_set_outcome(dl, path, XCHK_DIRPATH_CORRUPT);
538 0 : error = 0;
539 : }
540 13587255 : if (!error && dl->stale)
541 26 : return -ESTALE;
542 : return error;
543 : }
544 :
545 : /*
546 : * Decide if this path step has been touched by this live update. Returns
547 : * 1 for yes, 0 for no, or a negative errno.
548 : */
549 : STATIC int
550 127711 : xchk_dirpath_step_is_stale(
551 : struct xchk_dirtree *dl,
552 : struct xchk_dirpath *path,
553 : unsigned int step_nr,
554 : xfarray_idx_t step_idx,
555 : struct xfs_dir_update_params *p,
556 : struct xchk_dirpath_step *step)
557 : {
558 127711 : xfs_ino_t child_ino = step->parent_ino;
559 127711 : int error;
560 :
561 127711 : error = xfarray_load(dl->path_steps, step_idx, step);
562 127711 : if (error)
563 : return error;
564 :
565 : /*
566 : * If the parent and child being updated are not the ones mentioned in
567 : * this path step, the scan data is still ok.
568 : */
569 127711 : if (p->ip->i_ino != child_ino || p->dp->i_ino != step->parent_ino)
570 : return 0;
571 :
572 : /*
573 : * If the dirent name lengths or byte sequences are different, the scan
574 : * data is still ok.
575 : */
576 3668 : if (p->name->len != step->name_len)
577 : return 0;
578 :
579 3668 : error = xfblob_load(dl->path_names, step->name_cookie,
580 3668 : dl->hook_namebuf, step->name_len);
581 3668 : if (error)
582 : return error;
583 :
584 7336 : if (memcmp(dl->hook_namebuf, p->name->name, p->name->len) != 0)
585 : return 0;
586 :
587 : /*
588 : * If the update comes from the repair code itself, walk the state
589 : * machine forward.
590 : */
591 3668 : if (p->ip->i_ino == dl->scan_ino &&
592 28 : path->outcome == XREP_DIRPATH_ADOPTING) {
593 0 : xchk_dirpath_set_outcome(dl, path, XREP_DIRPATH_ADOPTED);
594 0 : return 0;
595 : }
596 :
597 3668 : if (p->ip->i_ino == dl->scan_ino &&
598 28 : path->outcome == XREP_DIRPATH_DELETING) {
599 0 : xchk_dirpath_set_outcome(dl, path, XREP_DIRPATH_DELETED);
600 0 : return 0;
601 : }
602 :
603 : /* Exact match, scan data is out of date. */
604 3668 : trace_xchk_dirpath_changed(dl->sc, path->path_nr, step_nr, p->dp,
605 : p->ip, p->name);
606 3668 : return 1;
607 : }
608 :
609 : /*
610 : * Decide if this path has been touched by this live update. Returns 1 for
611 : * yes, 0 for no, or a negative errno.
612 : */
613 : STATIC int
614 10624039 : xchk_dirpath_is_stale(
615 : struct xchk_dirtree *dl,
616 : struct xchk_dirpath *path,
617 : struct xfs_dir_update_params *p)
618 : {
619 10624039 : struct xchk_dirpath_step step = {
620 10624039 : .parent_ino = dl->scan_ino,
621 : };
622 10624039 : xfarray_idx_t idx = path->first_step;
623 10624039 : unsigned int i;
624 10624039 : int ret;
625 :
626 : /*
627 : * The child being updated has not been seen by this path at all; this
628 : * path cannot be stale.
629 : */
630 10624039 : if (!xino_bitmap_test(&path->seen_inodes, p->ip->i_ino))
631 : return 0;
632 :
633 3668 : ret = xchk_dirpath_step_is_stale(dl, path, 0, idx, p, &step);
634 3668 : if (ret != 0)
635 : return ret;
636 :
637 124043 : for (i = 1, idx = path->second_step; i < path->nr_steps; i++, idx++) {
638 124043 : ret = xchk_dirpath_step_is_stale(dl, path, i, idx, p, &step);
639 124043 : if (ret != 0)
640 3640 : return ret;
641 : }
642 :
643 : return 0;
644 : }
645 :
646 : /*
647 : * Decide if a directory update from the regular filesystem touches any of the
648 : * paths we've scanned, and invalidate the scan data if true.
649 : */
650 : STATIC int
651 10877525 : xchk_dirtree_live_update(
652 : struct notifier_block *nb,
653 : unsigned long action,
654 : void *data)
655 : {
656 10877525 : struct xfs_dir_update_params *p = data;
657 10877525 : struct xchk_dirtree *dl;
658 10877525 : struct xchk_dirpath *path;
659 10877525 : int ret;
660 :
661 10877525 : dl = container_of(nb, struct xchk_dirtree, hooks.dirent_hook.nb);
662 :
663 10877525 : trace_xchk_dirtree_live_update(dl->sc, p->dp, action, p->ip, p->delta,
664 : p->name);
665 :
666 10877522 : mutex_lock(&dl->lock);
667 :
668 10877562 : if (dl->stale || dl->aborted)
669 253170 : goto out_unlock;
670 :
671 21244766 : xchk_dirtree_for_each_path(dl, path) {
672 10624047 : ret = xchk_dirpath_is_stale(dl, path, p);
673 10624042 : if (ret < 0) {
674 0 : dl->aborted = true;
675 0 : break;
676 : }
677 10624042 : if (ret == 1) {
678 3668 : dl->stale = true;
679 3668 : break;
680 : }
681 : }
682 :
683 10620719 : out_unlock:
684 10877557 : mutex_unlock(&dl->lock);
685 10877532 : return NOTIFY_DONE;
686 : }
687 :
688 : /* Delete all the collected path information. */
689 : STATIC void
690 13598508 : xchk_dirtree_reset(
691 : void *buf)
692 : {
693 13598508 : struct xchk_dirtree *dl = buf;
694 13598508 : struct xchk_dirpath *path, *n;
695 :
696 13598508 : ASSERT(dl->sc->ilock_flags & XFS_ILOCK_EXCL);
697 :
698 13597754 : xchk_dirtree_for_each_path_safe(dl, path, n) {
699 2908 : list_del_init(&path->list);
700 2908 : xino_bitmap_destroy(&path->seen_inodes);
701 2908 : kfree(path);
702 : }
703 13594846 : dl->nr_paths = 0;
704 :
705 13594846 : xfarray_truncate(dl->path_steps);
706 13589966 : xfblob_truncate(dl->path_names);
707 :
708 13598644 : dl->stale = false;
709 13598644 : }
710 :
711 : /*
712 : * For each parent pointer of this subdir, trace a path upwards towards the
713 : * root directory and record what we find. Returns 0 for success;
714 : * -EFSCORRUPTED if walking the parent pointers of @sc->ip failed, -ELNRNG if a
715 : * path was too deep; -ENOSR if there were too many parent pointers; or
716 : * a negative errno.
717 : */
718 : int
719 13595361 : xchk_dirtree_find_paths_to_root(
720 : struct xchk_dirtree *dl)
721 : {
722 13595361 : struct xfs_scrub *sc = dl->sc;
723 13595361 : struct xchk_dirpath *path;
724 13595361 : int error = 0;
725 :
726 13598240 : do {
727 13598240 : if (xchk_should_terminate(sc, &error))
728 1 : return error;
729 :
730 13598323 : xchk_dirtree_reset(dl);
731 :
732 : /*
733 : * Create path walk contexts for each parent of the directory
734 : * that is being scanned. Directories are supposed to have
735 : * only one parent, but this is how we detect multiple parents.
736 : */
737 13598620 : error = xchk_pptr_walk(sc, sc->ip, xchk_dirtree_create_path,
738 : &dl->pptr, dl);
739 13572330 : if (error)
740 0 : return error;
741 :
742 27156657 : xchk_dirtree_for_each_path(dl, path) {
743 : /*
744 : * Try to walk up each path to the root. This enables
745 : * us to find directory loops in ancestors, and the
746 : * like.
747 : */
748 13558678 : error = xchk_dirpath_walk_upwards(dl, path);
749 13587235 : if (error == -EFSCORRUPTED) {
750 : /*
751 : * A parent pointer of @sc->ip is bad, don't
752 : * bother continuing.
753 : */
754 : break;
755 : }
756 13587235 : if (error == -ESTALE) {
757 : /* This had better be an invalidation. */
758 2908 : ASSERT(dl->stale);
759 : break;
760 : }
761 13584327 : if (error)
762 0 : return error;
763 13584327 : if (dl->aborted)
764 : return 0;
765 : }
766 13600887 : } while (dl->stale);
767 :
768 13598008 : return error;
769 : }
770 :
771 : /*
772 : * Figure out what to do with the paths we tried to find. Do not call this
773 : * if the scan results are stale.
774 : */
775 : void
776 13767472 : xchk_dirtree_evaluate(
777 : struct xchk_dirtree *dl,
778 : struct xchk_dirtree_outcomes *oc)
779 : {
780 13767472 : struct xchk_dirpath *path;
781 :
782 13767472 : ASSERT(!dl->stale);
783 :
784 : /* Scan the paths we have to decide what to do. */
785 13767472 : memset(oc, 0, sizeof(struct xchk_dirtree_outcomes));
786 27519413 : xchk_dirtree_for_each_path(dl, path) {
787 13752033 : trace_xchk_dirpath_evaluate_path(dl->sc, path->path_nr,
788 13752033 : path->nr_steps, path->outcome);
789 :
790 13751941 : switch (path->outcome) {
791 0 : case XCHK_DIRPATH_SCANNING:
792 : /* shouldn't get here */
793 0 : ASSERT(0);
794 0 : break;
795 0 : case XCHK_DIRPATH_DELETE:
796 : /* This one is already going away. */
797 0 : oc->bad++;
798 0 : break;
799 0 : case XCHK_DIRPATH_CORRUPT:
800 : case XCHK_DIRPATH_LOOP:
801 : /* Couldn't find the end of this path. */
802 0 : oc->suspect++;
803 0 : break;
804 0 : case XCHK_DIRPATH_STALE:
805 : /* shouldn't get here either */
806 0 : ASSERT(0);
807 0 : break;
808 13751941 : case XCHK_DIRPATH_OK:
809 : /* This path got all the way to the root. */
810 13751941 : oc->good++;
811 13751941 : break;
812 0 : case XREP_DIRPATH_DELETING:
813 : case XREP_DIRPATH_DELETED:
814 : case XREP_DIRPATH_ADOPTING:
815 : case XREP_DIRPATH_ADOPTED:
816 : /* These should not be in progress! */
817 0 : ASSERT(0);
818 0 : break;
819 : }
820 : }
821 :
822 13767380 : trace_xchk_dirtree_evaluate(dl, oc);
823 13767287 : }
824 :
825 : /* Dump a path step. */
826 : STATIC void
827 0 : xchk_dirpath_step_dump(
828 : struct xchk_dirtree *dl,
829 : struct xchk_dirpath *path,
830 : xfarray_idx_t idx,
831 : unsigned int step_nr)
832 : {
833 0 : struct xchk_dirpath_step step;
834 0 : struct xfs_scrub *sc = dl->sc;
835 0 : int error;
836 :
837 0 : error = xfarray_load(dl->path_steps, idx, &step);
838 0 : if (error)
839 0 : return;
840 :
841 0 : error = xfblob_load(dl->path_names, step.name_cookie, dl->pptr.p_name,
842 : step.name_len);
843 0 : if (error)
844 : return;
845 :
846 0 : xfs_err(sc->mp, " scan_ino 0x%llx path %u step %u parent_ino 0x%llx parent_gen 0x%x name '%.*s'",
847 : sc->ip->i_ino, path->path_nr, step_nr, step.parent_ino,
848 : step.parent_gen, step.name_len, dl->pptr.p_name);
849 : }
850 :
851 : /* Dump a path. */
852 : STATIC void
853 0 : xchk_dirpath_dump(
854 : struct xchk_dirtree *dl,
855 : struct xchk_dirpath *path)
856 : {
857 0 : struct xfs_scrub *sc = dl->sc;
858 0 : xfarray_idx_t idx;
859 0 : unsigned int i;
860 :
861 0 : xfs_err(sc->mp, " scan_ino 0x%llx path %u outcome %u",
862 : dl->scan_ino, path->path_nr, path->outcome);
863 :
864 0 : if (path->nr_steps > 0)
865 0 : xchk_dirpath_step_dump(dl, path, path->first_step, 0);
866 :
867 0 : for (i = 1, idx = path->second_step; i < path->nr_steps; i++, idx++)
868 0 : xchk_dirpath_step_dump(dl, path, idx, i);
869 0 : }
870 :
871 : STATIC int
872 0 : xchk_dirtree_dump_dirent(
873 : struct xfs_scrub *sc,
874 : struct xfs_inode *dp,
875 : xfs_dir2_dataptr_t dapos,
876 : const struct xfs_name *name,
877 : xfs_ino_t ino,
878 : void *priv)
879 : {
880 0 : unsigned int *nrp = priv;
881 :
882 0 : if (name->type == XFS_DIR3_FT_UNKNOWN ||
883 : name->type == XFS_DIR3_FT_DIR)
884 0 : xfs_err(sc->mp, " scan_ino 0x%llx dirent %u ino 0x%llx name '%.*s' type %u",
885 : dp->i_ino, (*nrp)++, ino, name->len,
886 : name->name, name->type);
887 0 : return 0;
888 : }
889 :
890 : STATIC int
891 0 : xchk_dirtree_dump_pptr(
892 : struct xfs_scrub *sc,
893 : struct xfs_inode *ip,
894 : const struct xfs_parent_name_irec *pptr,
895 : void *priv)
896 : {
897 0 : unsigned int *nrp = priv;
898 :
899 0 : xfs_err(sc->mp, " scan_ino 0x%llx pptr %u ino 0x%llx name '%.*s'",
900 : ip->i_ino, (*nrp)++, pptr->p_ino, pptr->p_namelen,
901 : pptr->p_name);
902 0 : return 0;
903 : }
904 :
905 : /* Dump all paths. */
906 : STATIC void
907 0 : xchk_dirtree_dump(
908 : struct xchk_dirtree *dl,
909 : struct xchk_dirtree_outcomes *oc)
910 : {
911 0 : struct xfs_scrub *sc = dl->sc;
912 0 : struct xchk_dirpath *path;
913 0 : unsigned int nr;
914 :
915 0 : xfs_err(sc->mp, "scan_ino 0x%llx parentless? %d nlink %u root_ino 0x%llx paths %u stale? %d aborted? %d",
916 : dl->scan_ino, xchk_dirtree_parentless(dl),
917 : VFS_I(sc->ip)->i_nlink,
918 : dl->root_ino, dl->nr_paths, dl->stale, dl->aborted);
919 0 : xfs_err(sc->mp, " scan_ino 0x%llx good %u bad %u suspect %u",
920 : dl->scan_ino, oc->good, oc->bad, oc->suspect);
921 :
922 0 : xchk_dirtree_for_each_path(dl, path) {
923 0 : xchk_dirpath_dump(dl, path);
924 : }
925 :
926 0 : xfs_err(sc->mp, " scan_ino 0x%llx dirents", sc->ip->i_ino);
927 0 : nr = 0;
928 0 : xchk_dir_walk(sc, sc->ip, xchk_dirtree_dump_dirent, &nr);
929 :
930 0 : xfs_err(sc->mp, " scan_ino 0x%llx pptrs", sc->ip->i_ino);
931 0 : nr = 0;
932 0 : xchk_pptr_walk(sc, sc->ip, xchk_dirtree_dump_pptr, &dl->pptr, &nr);
933 0 : }
934 :
935 : /* Look for directory loops. */
936 : int
937 13587951 : xchk_dirtree(
938 : struct xfs_scrub *sc)
939 : {
940 13587951 : struct xchk_dirtree_outcomes oc;
941 13587951 : struct xchk_dirtree *dl = sc->buf;
942 13587951 : int error;
943 :
944 : /*
945 : * Nondirectories do not point downwards to other files, so they cannot
946 : * cause a cycle in the directory tree.
947 : */
948 13587951 : if (!S_ISDIR(VFS_I(sc->ip)->i_mode))
949 : return -ENOENT;
950 :
951 13587951 : ASSERT(xfs_has_parent(sc->mp));
952 :
953 : /*
954 : * Find the root of the directory tree. Remember which directory to
955 : * scan, because the hook doesn't detach until after sc->ip gets
956 : * released during teardown.
957 : */
958 13587951 : dl->root_ino = sc->mp->m_rootip->i_ino;
959 13587951 : dl->scan_ino = sc->ip->i_ino;
960 :
961 13587951 : trace_xchk_dirtree_start(sc->ip, sc->sm, 0);
962 :
963 13582854 : mutex_lock(&dl->lock);
964 : /*
965 : * Hook into the directory entry code so that we can capture updates to
966 : * paths that we have already scanned. The scanner thread takes each
967 : * directory's ILOCK, which means that any in-progress directory update
968 : * will finish before we can scan the directory.
969 : */
970 13584488 : ASSERT(sc->flags & XCHK_FSGATES_DIRENTS);
971 13584488 : xfs_hook_setup(&dl->hooks.dirent_hook, xchk_dirtree_live_update);
972 13584488 : error = xfs_dir_hook_add(sc->mp, &dl->hooks);
973 13593547 : if (error)
974 0 : goto out_scanlock;
975 :
976 : /* Trace each parent pointer's path to the root. */
977 13593547 : error = xchk_dirtree_find_paths_to_root(dl);
978 13597920 : if (error == -EFSCORRUPTED || error == -ELNRNG || error == -ENOSR) {
979 : /*
980 : * Don't bother walking the paths if the xattr structure or the
981 : * parent pointers are corrupt; this scan cannot be completed
982 : * without full information.
983 : */
984 0 : xchk_ino_xref_set_corrupt(sc, sc->ip->i_ino);
985 0 : error = 0;
986 0 : goto out_scanlock;
987 : }
988 13597920 : if (error)
989 1 : goto out_scanlock;
990 13597919 : if (dl->aborted) {
991 0 : xchk_set_incomplete(sc);
992 0 : goto out_scanlock;
993 : }
994 :
995 : /* Assess what we found in our path evaluation. */
996 13597919 : xchk_dirtree_evaluate(dl, &oc);
997 13597485 : if (xchk_dirtree_parentless(dl)) {
998 13655 : if (oc.good || oc.bad || oc.suspect)
999 0 : xchk_ino_set_corrupt(sc, sc->ip->i_ino);
1000 :
1001 13655 : if (oc.good || oc.bad || oc.suspect)
1002 0 : xchk_dirtree_dump(dl, &oc);
1003 : } else {
1004 13583830 : if (oc.bad || oc.good + oc.suspect != 1)
1005 14 : xchk_ino_set_corrupt(sc, sc->ip->i_ino);
1006 13583986 : if (oc.suspect)
1007 0 : xchk_ino_xref_set_corrupt(sc, sc->ip->i_ino);
1008 :
1009 13583986 : if (oc.bad || oc.good + oc.suspect != 1 || oc.suspect)
1010 73 : xchk_dirtree_dump(dl, &oc);
1011 : }
1012 :
1013 13583918 : out_scanlock:
1014 13597574 : mutex_unlock(&dl->lock);
1015 13597366 : trace_xchk_dirtree_done(sc->ip, sc->sm, error);
1016 13597366 : return error;
1017 : }
|
