findparent.c

  1// SPDX-License-Identifier: GPL-2.0-or-later
  2/*
  3 * Copyright (c) 2020-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_defer.h"
 13#include "xfs_bit.h"
 14#include "xfs_log_format.h"
 15#include "xfs_trans.h"
 16#include "xfs_sb.h"
 17#include "xfs_inode.h"
 18#include "xfs_icache.h"
 19#include "xfs_da_format.h"
 20#include "xfs_da_btree.h"
 21#include "xfs_dir2.h"
 22#include "xfs_bmap_btree.h"
 23#include "xfs_dir2_priv.h"
 24#include "xfs_trans_space.h"
 25#include "xfs_health.h"
 26#include "xfs_exchmaps.h"
 27#include "xfs_parent.h"
 28#include "scrub/xfs_scrub.h"
 29#include "scrub/scrub.h"
 30#include "scrub/common.h"
 31#include "scrub/trace.h"
 32#include "scrub/repair.h"
 33#include "scrub/iscan.h"
 34#include "scrub/findparent.h"
 35#include "scrub/readdir.h"
 36#include "scrub/tempfile.h"
 37#include "scrub/listxattr.h"
 38
 39/*
 40 * Finding the Parent of a Directory
 41 * =================================
 42 *
 43 * Directories have parent pointers, in the sense that each directory contains
 44 * a dotdot entry that points to the single allowed parent.  The brute force
 45 * way to find the parent of a given directory is to scan every directory in
 46 * the filesystem looking for a child dirent that references this directory.
 47 *
 48 * This module wraps the process of scanning the directory tree.  It requires
 49 * that @sc->ip is the directory whose parent we want to find, and that the
 50 * caller hold only the IOLOCK on that directory.  The scan itself needs to
 51 * take the ILOCK of each directory visited.
 52 *
 53 * Because we cannot hold @sc->ip's ILOCK during a scan of the whole fs, it is
 54 * necessary to use dirent hook to update the parent scan results.  Callers
 55 * must not read the scan results without re-taking @sc->ip's ILOCK.
 56 *
 57 * There are a few shortcuts that we can take to avoid scanning the entire
 58 * filesystem, such as noticing directory tree roots and querying the dentry
 59 * cache for parent information.
 60 */
 61
 62struct xrep_findparent_info {
 63	/* The directory currently being scanned. */
 64	struct xfs_inode	*dp;
 65
 66	/*
 67	 * Scrub context.  We're looking for a @dp containing a directory
 68	 * entry pointing to sc->ip->i_ino.
 69	 */
 70	struct xfs_scrub	*sc;
 71
 72	/* Optional scan information for a xrep_findparent_scan call. */
 73	struct xrep_parent_scan_info *parent_scan;
 74
 75	/*
 76	 * Parent that we've found for sc->ip.  If we're scanning the entire
 77	 * directory tree, we need this to ensure that we only find /one/
 78	 * parent directory.
 79	 */
 80	xfs_ino_t		found_parent;
 81
 82	/*
 83	 * This is set to true if @found_parent was not observed directly from
 84	 * the directory scan but by noticing a change in dotdot entries after
 85	 * cycling the sc->ip IOLOCK.
 86	 */
 87	bool			parent_tentative;
 88};
 89
 90/*
 91 * If this directory entry points to the scrub target inode, then the directory
 92 * we're scanning is the parent of the scrub target inode.
 93 */
 94STATIC int
 95xrep_findparent_dirent(
 96	struct xfs_scrub		*sc,
 97	struct xfs_inode		*dp,
 98	xfs_dir2_dataptr_t		dapos,
 99	const struct xfs_name		*name,
100	xfs_ino_t			ino,
101	void				*priv)
102{
103	struct xrep_findparent_info	*fpi = priv;
104	int				error = 0;
105
106	if (xchk_should_terminate(fpi->sc, &error))
107		return error;
108
109	if (ino != fpi->sc->ip->i_ino)
110		return 0;
111
112	/* Ignore garbage directory entry names. */
113	if (name->len == 0 || !xfs_dir2_namecheck(name->name, name->len))
114		return -EFSCORRUPTED;
115
116	/*
117	 * Ignore dotdot and dot entries -- we're looking for parent -> child
118	 * links only.
119	 */
120	if (name->name[0] == '.' && (name->len == 1 ||
121				     (name->len == 2 && name->name[1] == '.')))
122		return 0;
123
124	/* Uhoh, more than one parent for a dir? */
125	if (fpi->found_parent != NULLFSINO &&
126	    !(fpi->parent_tentative && fpi->found_parent == fpi->dp->i_ino)) {
127		trace_xrep_findparent_dirent(fpi->sc->ip, 0);
128		return -EFSCORRUPTED;
129	}
130
131	/* We found a potential parent; remember this. */
132	trace_xrep_findparent_dirent(fpi->sc->ip, fpi->dp->i_ino);
133	fpi->found_parent = fpi->dp->i_ino;
134	fpi->parent_tentative = false;
135
136	if (fpi->parent_scan)
137		xrep_findparent_scan_found(fpi->parent_scan, fpi->dp->i_ino);
138
139	return 0;
140}
141
142/*
143 * If this is a directory, walk the dirents looking for any that point to the
144 * scrub target inode.
145 */
146STATIC int
147xrep_findparent_walk_directory(
148	struct xrep_findparent_info	*fpi)
149{
150	struct xfs_scrub		*sc = fpi->sc;
151	struct xfs_inode		*dp = fpi->dp;
152	unsigned int			lock_mode;
153	int				error = 0;
154
155	/*
156	 * The inode being scanned cannot be its own parent, nor can any
157	 * temporary directory we created to stage this repair.
158	 */
159	if (dp == sc->ip || dp == sc->tempip)
160		return 0;
161
162	/*
163	 * Similarly, temporary files created to stage a repair cannot be the
164	 * parent of this inode.
165	 */
166	if (xrep_is_tempfile(dp))
167		return 0;
168
169	/*
170	 * Scan the directory to see if there it contains an entry pointing to
171	 * the directory that we are repairing.
172	 */
173	lock_mode = xfs_ilock_data_map_shared(dp);
174
175	/* Don't mix metadata and regular directory trees. */
176	if (xfs_is_metadir_inode(dp) != xfs_is_metadir_inode(sc->ip))
177		goto out_unlock;
178
179	/*
180	 * If this directory is known to be sick, we cannot scan it reliably
181	 * and must abort.
182	 */
183	if (xfs_inode_has_sickness(dp, XFS_SICK_INO_CORE |
184				       XFS_SICK_INO_BMBTD |
185				       XFS_SICK_INO_DIR)) {
186		error = -EFSCORRUPTED;
187		goto out_unlock;
188	}
189
190	/*
191	 * We cannot complete our parent pointer scan if a directory looks as
192	 * though it has been zapped by the inode record repair code.
193	 */
194	if (xchk_dir_looks_zapped(dp)) {
195		error = -EBUSY;
196		goto out_unlock;
197	}
198
199	error = xchk_dir_walk(sc, dp, xrep_findparent_dirent, fpi);
200	if (error)
201		goto out_unlock;
202
203out_unlock:
204	xfs_iunlock(dp, lock_mode);
205	return error;
206}
207
208/*
209 * Update this directory's dotdot pointer based on ongoing dirent updates.
210 */
211STATIC int
212xrep_findparent_live_update(
213	struct notifier_block		*nb,
214	unsigned long			action,
215	void				*data)
216{
217	struct xfs_dir_update_params	*p = data;
218	struct xrep_parent_scan_info	*pscan;
219	struct xfs_scrub		*sc;
220
221	pscan = container_of(nb, struct xrep_parent_scan_info,
222			dhook.dirent_hook.nb);
223	sc = pscan->sc;
224
225	/*
226	 * If @p->ip is the subdirectory that we're interested in and we've
227	 * already scanned @p->dp, update the dotdot target inumber to the
228	 * parent inode.
229	 */
230	if (p->ip->i_ino == sc->ip->i_ino &&
231	    xchk_iscan_want_live_update(&pscan->iscan, p->dp->i_ino)) {
232		if (p->delta > 0) {
233			xrep_findparent_scan_found(pscan, p->dp->i_ino);
234		} else {
235			xrep_findparent_scan_found(pscan, NULLFSINO);
236		}
237	}
238
239	return NOTIFY_DONE;
240}
241
242/*
243 * Set up a scan to find the parent of a directory.  The provided dirent hook
244 * will be called when there is a dotdot update for the inode being repaired.
245 */
246int
247__xrep_findparent_scan_start(
248	struct xfs_scrub		*sc,
249	struct xrep_parent_scan_info	*pscan,
250	notifier_fn_t			custom_fn)
251{
252	int				error;
253
254	if (!(sc->flags & XCHK_FSGATES_DIRENTS)) {
255		ASSERT(sc->flags & XCHK_FSGATES_DIRENTS);
256		return -EINVAL;
257	}
258
259	pscan->sc = sc;
260	pscan->parent_ino = NULLFSINO;
261
262	mutex_init(&pscan->lock);
263
264	xchk_iscan_start(sc, 30000, 100, &pscan->iscan);
265
266	/*
267	 * Hook into the dirent update code.  The hook only operates on inodes
268	 * that were already scanned, and the scanner thread takes each inode's
269	 * ILOCK, which means that any in-progress inode updates will finish
270	 * before we can scan the inode.
271	 */
272	if (custom_fn)
273		xfs_dir_hook_setup(&pscan->dhook, custom_fn);
274	else
275		xfs_dir_hook_setup(&pscan->dhook, xrep_findparent_live_update);
276	error = xfs_dir_hook_add(sc->mp, &pscan->dhook);
277	if (error)
278		goto out_iscan;
279
280	return 0;
281out_iscan:
282	xchk_iscan_teardown(&pscan->iscan);
283	mutex_destroy(&pscan->lock);
284	return error;
285}
286
287/*
288 * Scan the entire filesystem looking for a parent inode for the inode being
289 * scrubbed.  @sc->ip must not be the root of a directory tree.  Callers must
290 * not hold a dirty transaction or any lock that would interfere with taking
291 * an ILOCK.
292 *
293 * Returns 0 with @pscan->parent_ino set to the parent that we found.
294 * Returns 0 with @pscan->parent_ino set to NULLFSINO if we found no parents.
295 * Returns the usual negative errno if something else happened.
296 */
297int
298xrep_findparent_scan(
299	struct xrep_parent_scan_info	*pscan)
300{
301	struct xrep_findparent_info	fpi = {
302		.sc			= pscan->sc,
303		.found_parent		= NULLFSINO,
304		.parent_scan		= pscan,
305	};
306	struct xfs_scrub		*sc = pscan->sc;
307	int				ret;
308
309	ASSERT(S_ISDIR(VFS_IC(sc->ip)->i_mode));
310
311	while ((ret = xchk_iscan_iter(&pscan->iscan, &fpi.dp)) == 1) {
312		if (S_ISDIR(VFS_I(fpi.dp)->i_mode))
313			ret = xrep_findparent_walk_directory(&fpi);
314		else
315			ret = 0;
316		xchk_iscan_mark_visited(&pscan->iscan, fpi.dp);
317		xchk_irele(sc, fpi.dp);
318		if (ret)
319			break;
320
321		if (xchk_should_terminate(sc, &ret))
322			break;
323	}
324	xchk_iscan_iter_finish(&pscan->iscan);
325
326	return ret;
327}
328
329/* Tear down a parent scan. */
330void
331xrep_findparent_scan_teardown(
332	struct xrep_parent_scan_info	*pscan)
333{
334	xfs_dir_hook_del(pscan->sc->mp, &pscan->dhook);
335	xchk_iscan_teardown(&pscan->iscan);
336	mutex_destroy(&pscan->lock);
337}
338
339/* Finish a parent scan early. */
340void
341xrep_findparent_scan_finish_early(
342	struct xrep_parent_scan_info	*pscan,
343	xfs_ino_t			ino)
344{
345	xrep_findparent_scan_found(pscan, ino);
346	xchk_iscan_finish_early(&pscan->iscan);
347}
348
349/*
350 * Confirm that the directory @parent_ino actually contains a directory entry
351 * pointing to the child @sc->ip->ino.  This function returns one of several
352 * ways:
353 *
354 * Returns 0 with @parent_ino unchanged if the parent was confirmed.
355 * Returns 0 with @parent_ino set to NULLFSINO if the parent was not valid.
356 * Returns the usual negative errno if something else happened.
357 */
358int
359xrep_findparent_confirm(
360	struct xfs_scrub	*sc,
361	xfs_ino_t		*parent_ino)
362{
363	struct xrep_findparent_info fpi = {
364		.sc		= sc,
365		.found_parent	= NULLFSINO,
366	};
367	int			error;
368
369	/* The root directory always points to itself. */
370	if (sc->ip == sc->mp->m_rootip) {
371		*parent_ino = sc->mp->m_sb.sb_rootino;
372		return 0;
373	}
374
375	/* The metadata root directory always points to itself. */
376	if (sc->ip == sc->mp->m_metadirip) {
377		*parent_ino = sc->mp->m_sb.sb_metadirino;
378		return 0;
379	}
380
381	/* Unlinked dirs can point anywhere; point them up to the root dir. */
382	if (VFS_I(sc->ip)->i_nlink == 0) {
383		*parent_ino = xchk_inode_rootdir_inum(sc->ip);
384		return 0;
385	}
386
387	/* Reject garbage parent inode numbers and self-referential parents. */
388	if (*parent_ino == NULLFSINO)
389	       return 0;
390	if (!xfs_verify_dir_ino(sc->mp, *parent_ino) ||
391	    *parent_ino == sc->ip->i_ino) {
392		*parent_ino = NULLFSINO;
393		return 0;
394	}
395
396	error = xchk_iget(sc, *parent_ino, &fpi.dp);
397	if (error)
398		return error;
399
400	if (!S_ISDIR(VFS_I(fpi.dp)->i_mode)) {
401		*parent_ino = NULLFSINO;
402		goto out_rele;
403	}
404
405	error = xrep_findparent_walk_directory(&fpi);
406	if (error)
407		goto out_rele;
408
409	*parent_ino = fpi.found_parent;
410out_rele:
411	xchk_irele(sc, fpi.dp);
412	return error;
413}
414
415/*
416 * If we're the root of a directory tree, we are our own parent.  If we're an
417 * unlinked directory, the parent /won't/ have a link to us.  Set the parent
418 * directory to the root for both cases.  Returns NULLFSINO if we don't know
419 * what to do.
420 */
421xfs_ino_t
422xrep_findparent_self_reference(
423	struct xfs_scrub	*sc)
424{
425	if (sc->ip->i_ino == sc->mp->m_sb.sb_rootino)
426		return sc->mp->m_sb.sb_rootino;
427
428	if (sc->ip->i_ino == sc->mp->m_sb.sb_metadirino)
429		return sc->mp->m_sb.sb_metadirino;
430
431	if (VFS_I(sc->ip)->i_nlink == 0)
432		return xchk_inode_rootdir_inum(sc->ip);
433
434	return NULLFSINO;
435}
436
437/* Check the dentry cache to see if knows of a parent for the scrub target. */
438xfs_ino_t
439xrep_findparent_from_dcache(
440	struct xfs_scrub	*sc)
441{
442	struct inode		*pip = NULL;
443	struct dentry		*dentry, *parent;
444	xfs_ino_t		ret = NULLFSINO;
445
446	dentry = d_find_alias(VFS_I(sc->ip));
447	if (!dentry)
448		goto out;
449
450	parent = dget_parent(dentry);
451	if (!parent)
452		goto out_dput;
453
454	ASSERT(parent->d_sb == sc->ip->i_mount->m_super);
455
456	pip = igrab(d_inode(parent));
457	dput(parent);
458
459	if (S_ISDIR(pip->i_mode)) {
460		trace_xrep_findparent_from_dcache(sc->ip, XFS_I(pip)->i_ino);
461		ret = XFS_I(pip)->i_ino;
462	}
463
464	xchk_irele(sc, XFS_I(pip));
465
466out_dput:
467	dput(dentry);
468out:
469	return ret;
470}