xref: /openbmc/linux/fs/xfs/scrub/btree.c (revision 53004ee7)
10b61f8a4SDave Chinner // SPDX-License-Identifier: GPL-2.0+
2537964bcSDarrick J. Wong /*
3537964bcSDarrick J. Wong  * Copyright (C) 2017 Oracle.  All Rights Reserved.
4537964bcSDarrick J. Wong  * Author: Darrick J. Wong <darrick.wong@oracle.com>
5537964bcSDarrick J. Wong  */
6537964bcSDarrick J. Wong #include "xfs.h"
7537964bcSDarrick J. Wong #include "xfs_fs.h"
8537964bcSDarrick J. Wong #include "xfs_shared.h"
9537964bcSDarrick J. Wong #include "xfs_format.h"
10537964bcSDarrick J. Wong #include "xfs_trans_resv.h"
11537964bcSDarrick J. Wong #include "xfs_mount.h"
12ae7bae68SChandan Babu R #include "xfs_inode.h"
13537964bcSDarrick J. Wong #include "xfs_btree.h"
14537964bcSDarrick J. Wong #include "scrub/scrub.h"
15537964bcSDarrick J. Wong #include "scrub/common.h"
16537964bcSDarrick J. Wong #include "scrub/btree.h"
17537964bcSDarrick J. Wong #include "scrub/trace.h"
18537964bcSDarrick J. Wong 
19537964bcSDarrick J. Wong /* btree scrubbing */
20537964bcSDarrick J. Wong 
21537964bcSDarrick J. Wong /*
22537964bcSDarrick J. Wong  * Check for btree operation errors.  See the section about handling
23537964bcSDarrick J. Wong  * operational errors in common.c.
24537964bcSDarrick J. Wong  */
2564b12563SDarrick J. Wong static bool
26c517b3aaSDarrick J. Wong __xchk_btree_process_error(
271d8a748aSDarrick J. Wong 	struct xfs_scrub	*sc,
28537964bcSDarrick J. Wong 	struct xfs_btree_cur	*cur,
29537964bcSDarrick J. Wong 	int			level,
3064b12563SDarrick J. Wong 	int			*error,
3164b12563SDarrick J. Wong 	__u32			errflag,
3264b12563SDarrick J. Wong 	void			*ret_ip)
33537964bcSDarrick J. Wong {
34537964bcSDarrick J. Wong 	if (*error == 0)
35537964bcSDarrick J. Wong 		return true;
36537964bcSDarrick J. Wong 
37537964bcSDarrick J. Wong 	switch (*error) {
38537964bcSDarrick J. Wong 	case -EDEADLOCK:
39537964bcSDarrick J. Wong 		/* Used to restart an op with deadlock avoidance. */
40c517b3aaSDarrick J. Wong 		trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
41537964bcSDarrick J. Wong 		break;
42537964bcSDarrick J. Wong 	case -EFSBADCRC:
43537964bcSDarrick J. Wong 	case -EFSCORRUPTED:
44537964bcSDarrick J. Wong 		/* Note the badness but don't abort. */
4564b12563SDarrick J. Wong 		sc->sm->sm_flags |= errflag;
46537964bcSDarrick J. Wong 		*error = 0;
47*53004ee7SGustavo A. R. Silva 		fallthrough;
48537964bcSDarrick J. Wong 	default:
49537964bcSDarrick J. Wong 		if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
50c517b3aaSDarrick J. Wong 			trace_xchk_ifork_btree_op_error(sc, cur, level,
5164b12563SDarrick J. Wong 					*error, ret_ip);
52537964bcSDarrick J. Wong 		else
53c517b3aaSDarrick J. Wong 			trace_xchk_btree_op_error(sc, cur, level,
5464b12563SDarrick J. Wong 					*error, ret_ip);
55537964bcSDarrick J. Wong 		break;
56537964bcSDarrick J. Wong 	}
57537964bcSDarrick J. Wong 	return false;
58537964bcSDarrick J. Wong }
59537964bcSDarrick J. Wong 
6064b12563SDarrick J. Wong bool
61c517b3aaSDarrick J. Wong xchk_btree_process_error(
621d8a748aSDarrick J. Wong 	struct xfs_scrub	*sc,
6364b12563SDarrick J. Wong 	struct xfs_btree_cur	*cur,
6464b12563SDarrick J. Wong 	int			level,
6564b12563SDarrick J. Wong 	int			*error)
6664b12563SDarrick J. Wong {
67c517b3aaSDarrick J. Wong 	return __xchk_btree_process_error(sc, cur, level, error,
6864b12563SDarrick J. Wong 			XFS_SCRUB_OFLAG_CORRUPT, __return_address);
6964b12563SDarrick J. Wong }
7064b12563SDarrick J. Wong 
7164b12563SDarrick J. Wong bool
72c517b3aaSDarrick J. Wong xchk_btree_xref_process_error(
731d8a748aSDarrick J. Wong 	struct xfs_scrub	*sc,
7464b12563SDarrick J. Wong 	struct xfs_btree_cur	*cur,
7564b12563SDarrick J. Wong 	int			level,
7664b12563SDarrick J. Wong 	int			*error)
7764b12563SDarrick J. Wong {
78c517b3aaSDarrick J. Wong 	return __xchk_btree_process_error(sc, cur, level, error,
7964b12563SDarrick J. Wong 			XFS_SCRUB_OFLAG_XFAIL, __return_address);
8064b12563SDarrick J. Wong }
8164b12563SDarrick J. Wong 
82537964bcSDarrick J. Wong /* Record btree block corruption. */
8364b12563SDarrick J. Wong static void
84c517b3aaSDarrick J. Wong __xchk_btree_set_corrupt(
851d8a748aSDarrick J. Wong 	struct xfs_scrub	*sc,
8664b12563SDarrick J. Wong 	struct xfs_btree_cur	*cur,
8764b12563SDarrick J. Wong 	int			level,
8864b12563SDarrick J. Wong 	__u32			errflag,
8964b12563SDarrick J. Wong 	void			*ret_ip)
9064b12563SDarrick J. Wong {
9164b12563SDarrick J. Wong 	sc->sm->sm_flags |= errflag;
9264b12563SDarrick J. Wong 
9364b12563SDarrick J. Wong 	if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
94c517b3aaSDarrick J. Wong 		trace_xchk_ifork_btree_error(sc, cur, level,
9564b12563SDarrick J. Wong 				ret_ip);
9664b12563SDarrick J. Wong 	else
97c517b3aaSDarrick J. Wong 		trace_xchk_btree_error(sc, cur, level,
9864b12563SDarrick J. Wong 				ret_ip);
9964b12563SDarrick J. Wong }
10064b12563SDarrick J. Wong 
101537964bcSDarrick J. Wong void
102c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(
1031d8a748aSDarrick J. Wong 	struct xfs_scrub	*sc,
104537964bcSDarrick J. Wong 	struct xfs_btree_cur	*cur,
105537964bcSDarrick J. Wong 	int			level)
106537964bcSDarrick J. Wong {
107c517b3aaSDarrick J. Wong 	__xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT,
108537964bcSDarrick J. Wong 			__return_address);
10964b12563SDarrick J. Wong }
11064b12563SDarrick J. Wong 
11164b12563SDarrick J. Wong void
112c517b3aaSDarrick J. Wong xchk_btree_xref_set_corrupt(
1131d8a748aSDarrick J. Wong 	struct xfs_scrub	*sc,
11464b12563SDarrick J. Wong 	struct xfs_btree_cur	*cur,
11564b12563SDarrick J. Wong 	int			level)
11664b12563SDarrick J. Wong {
117c517b3aaSDarrick J. Wong 	__xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT,
118537964bcSDarrick J. Wong 			__return_address);
119537964bcSDarrick J. Wong }
120537964bcSDarrick J. Wong 
121537964bcSDarrick J. Wong /*
12237f3fa7fSDarrick J. Wong  * Make sure this record is in order and doesn't stray outside of the parent
12337f3fa7fSDarrick J. Wong  * keys.
12437f3fa7fSDarrick J. Wong  */
12537f3fa7fSDarrick J. Wong STATIC void
126c517b3aaSDarrick J. Wong xchk_btree_rec(
127c517b3aaSDarrick J. Wong 	struct xchk_btree	*bs)
12837f3fa7fSDarrick J. Wong {
12937f3fa7fSDarrick J. Wong 	struct xfs_btree_cur	*cur = bs->cur;
13037f3fa7fSDarrick J. Wong 	union xfs_btree_rec	*rec;
13137f3fa7fSDarrick J. Wong 	union xfs_btree_key	key;
13237f3fa7fSDarrick J. Wong 	union xfs_btree_key	hkey;
13337f3fa7fSDarrick J. Wong 	union xfs_btree_key	*keyp;
13437f3fa7fSDarrick J. Wong 	struct xfs_btree_block	*block;
13537f3fa7fSDarrick J. Wong 	struct xfs_btree_block	*keyblock;
13637f3fa7fSDarrick J. Wong 	struct xfs_buf		*bp;
13737f3fa7fSDarrick J. Wong 
13837f3fa7fSDarrick J. Wong 	block = xfs_btree_get_block(cur, 0, &bp);
13937f3fa7fSDarrick J. Wong 	rec = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block);
14037f3fa7fSDarrick J. Wong 
141c517b3aaSDarrick J. Wong 	trace_xchk_btree_rec(bs->sc, cur, 0);
14237f3fa7fSDarrick J. Wong 
14337f3fa7fSDarrick J. Wong 	/* If this isn't the first record, are they in order? */
14437f3fa7fSDarrick J. Wong 	if (!bs->firstrec && !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
145c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, 0);
14637f3fa7fSDarrick J. Wong 	bs->firstrec = false;
14737f3fa7fSDarrick J. Wong 	memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);
14837f3fa7fSDarrick J. Wong 
14937f3fa7fSDarrick J. Wong 	if (cur->bc_nlevels == 1)
15037f3fa7fSDarrick J. Wong 		return;
15137f3fa7fSDarrick J. Wong 
15237f3fa7fSDarrick J. Wong 	/* Is this at least as large as the parent low key? */
15337f3fa7fSDarrick J. Wong 	cur->bc_ops->init_key_from_rec(&key, rec);
15437f3fa7fSDarrick J. Wong 	keyblock = xfs_btree_get_block(cur, 1, &bp);
15537f3fa7fSDarrick J. Wong 	keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[1], keyblock);
15637f3fa7fSDarrick J. Wong 	if (cur->bc_ops->diff_two_keys(cur, &key, keyp) < 0)
157c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, 1);
15837f3fa7fSDarrick J. Wong 
15937f3fa7fSDarrick J. Wong 	if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
16037f3fa7fSDarrick J. Wong 		return;
16137f3fa7fSDarrick J. Wong 
16237f3fa7fSDarrick J. Wong 	/* Is this no larger than the parent high key? */
16337f3fa7fSDarrick J. Wong 	cur->bc_ops->init_high_key_from_rec(&hkey, rec);
16437f3fa7fSDarrick J. Wong 	keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[1], keyblock);
16537f3fa7fSDarrick J. Wong 	if (cur->bc_ops->diff_two_keys(cur, keyp, &hkey) < 0)
166c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, 1);
16737f3fa7fSDarrick J. Wong }
16837f3fa7fSDarrick J. Wong 
16937f3fa7fSDarrick J. Wong /*
17037f3fa7fSDarrick J. Wong  * Make sure this key is in order and doesn't stray outside of the parent
17137f3fa7fSDarrick J. Wong  * keys.
17237f3fa7fSDarrick J. Wong  */
17337f3fa7fSDarrick J. Wong STATIC void
174c517b3aaSDarrick J. Wong xchk_btree_key(
175c517b3aaSDarrick J. Wong 	struct xchk_btree	*bs,
17637f3fa7fSDarrick J. Wong 	int			level)
17737f3fa7fSDarrick J. Wong {
17837f3fa7fSDarrick J. Wong 	struct xfs_btree_cur	*cur = bs->cur;
17937f3fa7fSDarrick J. Wong 	union xfs_btree_key	*key;
18037f3fa7fSDarrick J. Wong 	union xfs_btree_key	*keyp;
18137f3fa7fSDarrick J. Wong 	struct xfs_btree_block	*block;
18237f3fa7fSDarrick J. Wong 	struct xfs_btree_block	*keyblock;
18337f3fa7fSDarrick J. Wong 	struct xfs_buf		*bp;
18437f3fa7fSDarrick J. Wong 
18537f3fa7fSDarrick J. Wong 	block = xfs_btree_get_block(cur, level, &bp);
18637f3fa7fSDarrick J. Wong 	key = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block);
18737f3fa7fSDarrick J. Wong 
188c517b3aaSDarrick J. Wong 	trace_xchk_btree_key(bs->sc, cur, level);
18937f3fa7fSDarrick J. Wong 
19037f3fa7fSDarrick J. Wong 	/* If this isn't the first key, are they in order? */
19137f3fa7fSDarrick J. Wong 	if (!bs->firstkey[level] &&
19237f3fa7fSDarrick J. Wong 	    !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level], key))
193c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, level);
19437f3fa7fSDarrick J. Wong 	bs->firstkey[level] = false;
19537f3fa7fSDarrick J. Wong 	memcpy(&bs->lastkey[level], key, cur->bc_ops->key_len);
19637f3fa7fSDarrick J. Wong 
19737f3fa7fSDarrick J. Wong 	if (level + 1 >= cur->bc_nlevels)
19837f3fa7fSDarrick J. Wong 		return;
19937f3fa7fSDarrick J. Wong 
20037f3fa7fSDarrick J. Wong 	/* Is this at least as large as the parent low key? */
20137f3fa7fSDarrick J. Wong 	keyblock = xfs_btree_get_block(cur, level + 1, &bp);
20237f3fa7fSDarrick J. Wong 	keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1], keyblock);
20337f3fa7fSDarrick J. Wong 	if (cur->bc_ops->diff_two_keys(cur, key, keyp) < 0)
204c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, level);
20537f3fa7fSDarrick J. Wong 
20637f3fa7fSDarrick J. Wong 	if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
20737f3fa7fSDarrick J. Wong 		return;
20837f3fa7fSDarrick J. Wong 
20937f3fa7fSDarrick J. Wong 	/* Is this no larger than the parent high key? */
21037f3fa7fSDarrick J. Wong 	key = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block);
21137f3fa7fSDarrick J. Wong 	keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1], keyblock);
21237f3fa7fSDarrick J. Wong 	if (cur->bc_ops->diff_two_keys(cur, keyp, key) < 0)
213c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, level);
21437f3fa7fSDarrick J. Wong }
21537f3fa7fSDarrick J. Wong 
21637f3fa7fSDarrick J. Wong /*
217cc3e0948SDarrick J. Wong  * Check a btree pointer.  Returns true if it's ok to use this pointer.
218cc3e0948SDarrick J. Wong  * Callers do not need to set the corrupt flag.
219cc3e0948SDarrick J. Wong  */
220cc3e0948SDarrick J. Wong static bool
221c517b3aaSDarrick J. Wong xchk_btree_ptr_ok(
222c517b3aaSDarrick J. Wong 	struct xchk_btree	*bs,
223cc3e0948SDarrick J. Wong 	int			level,
224cc3e0948SDarrick J. Wong 	union xfs_btree_ptr	*ptr)
225cc3e0948SDarrick J. Wong {
226cc3e0948SDarrick J. Wong 	bool			res;
227cc3e0948SDarrick J. Wong 
228cc3e0948SDarrick J. Wong 	/* A btree rooted in an inode has no block pointer to the root. */
229cc3e0948SDarrick J. Wong 	if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
230cc3e0948SDarrick J. Wong 	    level == bs->cur->bc_nlevels)
231cc3e0948SDarrick J. Wong 		return true;
232cc3e0948SDarrick J. Wong 
233cc3e0948SDarrick J. Wong 	/* Otherwise, check the pointers. */
234cc3e0948SDarrick J. Wong 	if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
235cc3e0948SDarrick J. Wong 		res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
236cc3e0948SDarrick J. Wong 	else
237cc3e0948SDarrick J. Wong 		res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
238cc3e0948SDarrick J. Wong 	if (!res)
239c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, bs->cur, level);
240cc3e0948SDarrick J. Wong 
241cc3e0948SDarrick J. Wong 	return res;
242cc3e0948SDarrick J. Wong }
243cc3e0948SDarrick J. Wong 
244cc3e0948SDarrick J. Wong /* Check that a btree block's sibling matches what we expect it. */
245cc3e0948SDarrick J. Wong STATIC int
246c517b3aaSDarrick J. Wong xchk_btree_block_check_sibling(
247c517b3aaSDarrick J. Wong 	struct xchk_btree	*bs,
248cc3e0948SDarrick J. Wong 	int			level,
249cc3e0948SDarrick J. Wong 	int			direction,
250cc3e0948SDarrick J. Wong 	union xfs_btree_ptr	*sibling)
251cc3e0948SDarrick J. Wong {
252cc3e0948SDarrick J. Wong 	struct xfs_btree_cur	*cur = bs->cur;
253cc3e0948SDarrick J. Wong 	struct xfs_btree_block	*pblock;
254cc3e0948SDarrick J. Wong 	struct xfs_buf		*pbp;
255cc3e0948SDarrick J. Wong 	struct xfs_btree_cur	*ncur = NULL;
256cc3e0948SDarrick J. Wong 	union xfs_btree_ptr	*pp;
257cc3e0948SDarrick J. Wong 	int			success;
258cc3e0948SDarrick J. Wong 	int			error;
259cc3e0948SDarrick J. Wong 
260cc3e0948SDarrick J. Wong 	error = xfs_btree_dup_cursor(cur, &ncur);
261c517b3aaSDarrick J. Wong 	if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
262cc3e0948SDarrick J. Wong 	    !ncur)
263cc3e0948SDarrick J. Wong 		return error;
264cc3e0948SDarrick J. Wong 
265cc3e0948SDarrick J. Wong 	/*
266cc3e0948SDarrick J. Wong 	 * If the pointer is null, we shouldn't be able to move the upper
267cc3e0948SDarrick J. Wong 	 * level pointer anywhere.
268cc3e0948SDarrick J. Wong 	 */
269cc3e0948SDarrick J. Wong 	if (xfs_btree_ptr_is_null(cur, sibling)) {
270cc3e0948SDarrick J. Wong 		if (direction > 0)
271cc3e0948SDarrick J. Wong 			error = xfs_btree_increment(ncur, level + 1, &success);
272cc3e0948SDarrick J. Wong 		else
273cc3e0948SDarrick J. Wong 			error = xfs_btree_decrement(ncur, level + 1, &success);
274cc3e0948SDarrick J. Wong 		if (error == 0 && success)
275c517b3aaSDarrick J. Wong 			xchk_btree_set_corrupt(bs->sc, cur, level);
276cc3e0948SDarrick J. Wong 		error = 0;
277cc3e0948SDarrick J. Wong 		goto out;
278cc3e0948SDarrick J. Wong 	}
279cc3e0948SDarrick J. Wong 
280cc3e0948SDarrick J. Wong 	/* Increment upper level pointer. */
281cc3e0948SDarrick J. Wong 	if (direction > 0)
282cc3e0948SDarrick J. Wong 		error = xfs_btree_increment(ncur, level + 1, &success);
283cc3e0948SDarrick J. Wong 	else
284cc3e0948SDarrick J. Wong 		error = xfs_btree_decrement(ncur, level + 1, &success);
285c517b3aaSDarrick J. Wong 	if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
286cc3e0948SDarrick J. Wong 		goto out;
287cc3e0948SDarrick J. Wong 	if (!success) {
288c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, level + 1);
289cc3e0948SDarrick J. Wong 		goto out;
290cc3e0948SDarrick J. Wong 	}
291cc3e0948SDarrick J. Wong 
292cc3e0948SDarrick J. Wong 	/* Compare upper level pointer to sibling pointer. */
293cc3e0948SDarrick J. Wong 	pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
294cc3e0948SDarrick J. Wong 	pp = xfs_btree_ptr_addr(ncur, ncur->bc_ptrs[level + 1], pblock);
295c517b3aaSDarrick J. Wong 	if (!xchk_btree_ptr_ok(bs, level + 1, pp))
296cc3e0948SDarrick J. Wong 		goto out;
297cf1b0b8bSDarrick J. Wong 	if (pbp)
298c517b3aaSDarrick J. Wong 		xchk_buffer_recheck(bs->sc, pbp);
299cc3e0948SDarrick J. Wong 
300cc3e0948SDarrick J. Wong 	if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
301c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, level);
302cc3e0948SDarrick J. Wong out:
303cc3e0948SDarrick J. Wong 	xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
304cc3e0948SDarrick J. Wong 	return error;
305cc3e0948SDarrick J. Wong }
306cc3e0948SDarrick J. Wong 
307cc3e0948SDarrick J. Wong /* Check the siblings of a btree block. */
308cc3e0948SDarrick J. Wong STATIC int
309c517b3aaSDarrick J. Wong xchk_btree_block_check_siblings(
310c517b3aaSDarrick J. Wong 	struct xchk_btree	*bs,
311cc3e0948SDarrick J. Wong 	struct xfs_btree_block	*block)
312cc3e0948SDarrick J. Wong {
313cc3e0948SDarrick J. Wong 	struct xfs_btree_cur	*cur = bs->cur;
314cc3e0948SDarrick J. Wong 	union xfs_btree_ptr	leftsib;
315cc3e0948SDarrick J. Wong 	union xfs_btree_ptr	rightsib;
316cc3e0948SDarrick J. Wong 	int			level;
317cc3e0948SDarrick J. Wong 	int			error = 0;
318cc3e0948SDarrick J. Wong 
319cc3e0948SDarrick J. Wong 	xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
320cc3e0948SDarrick J. Wong 	xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
321cc3e0948SDarrick J. Wong 	level = xfs_btree_get_level(block);
322cc3e0948SDarrick J. Wong 
323cc3e0948SDarrick J. Wong 	/* Root block should never have siblings. */
324cc3e0948SDarrick J. Wong 	if (level == cur->bc_nlevels - 1) {
325cc3e0948SDarrick J. Wong 		if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
326cc3e0948SDarrick J. Wong 		    !xfs_btree_ptr_is_null(cur, &rightsib))
327c517b3aaSDarrick J. Wong 			xchk_btree_set_corrupt(bs->sc, cur, level);
328cc3e0948SDarrick J. Wong 		goto out;
329cc3e0948SDarrick J. Wong 	}
330cc3e0948SDarrick J. Wong 
331cc3e0948SDarrick J. Wong 	/*
332cc3e0948SDarrick J. Wong 	 * Does the left & right sibling pointers match the adjacent
333cc3e0948SDarrick J. Wong 	 * parent level pointers?
334cc3e0948SDarrick J. Wong 	 * (These function absorbs error codes for us.)
335cc3e0948SDarrick J. Wong 	 */
336c517b3aaSDarrick J. Wong 	error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
337cc3e0948SDarrick J. Wong 	if (error)
338cc3e0948SDarrick J. Wong 		return error;
339c517b3aaSDarrick J. Wong 	error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
340cc3e0948SDarrick J. Wong 	if (error)
341cc3e0948SDarrick J. Wong 		return error;
342cc3e0948SDarrick J. Wong out:
343cc3e0948SDarrick J. Wong 	return error;
344cc3e0948SDarrick J. Wong }
345cc3e0948SDarrick J. Wong 
346858333dcSDarrick J. Wong struct check_owner {
347858333dcSDarrick J. Wong 	struct list_head	list;
348858333dcSDarrick J. Wong 	xfs_daddr_t		daddr;
349858333dcSDarrick J. Wong 	int			level;
350858333dcSDarrick J. Wong };
351858333dcSDarrick J. Wong 
352858333dcSDarrick J. Wong /*
353858333dcSDarrick J. Wong  * Make sure this btree block isn't in the free list and that there's
354858333dcSDarrick J. Wong  * an rmap record for it.
355858333dcSDarrick J. Wong  */
356858333dcSDarrick J. Wong STATIC int
357c517b3aaSDarrick J. Wong xchk_btree_check_block_owner(
358c517b3aaSDarrick J. Wong 	struct xchk_btree	*bs,
359858333dcSDarrick J. Wong 	int			level,
360858333dcSDarrick J. Wong 	xfs_daddr_t		daddr)
361858333dcSDarrick J. Wong {
362858333dcSDarrick J. Wong 	xfs_agnumber_t		agno;
36352dc4b44SDarrick J. Wong 	xfs_agblock_t		agbno;
36452dc4b44SDarrick J. Wong 	xfs_btnum_t		btnum;
365858333dcSDarrick J. Wong 	bool			init_sa;
366858333dcSDarrick J. Wong 	int			error = 0;
367858333dcSDarrick J. Wong 
368858333dcSDarrick J. Wong 	if (!bs->cur)
369858333dcSDarrick J. Wong 		return 0;
370858333dcSDarrick J. Wong 
37152dc4b44SDarrick J. Wong 	btnum = bs->cur->bc_btnum;
372858333dcSDarrick J. Wong 	agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
37352dc4b44SDarrick J. Wong 	agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);
374858333dcSDarrick J. Wong 
375858333dcSDarrick J. Wong 	init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS;
376858333dcSDarrick J. Wong 	if (init_sa) {
377c517b3aaSDarrick J. Wong 		error = xchk_ag_init(bs->sc, agno, &bs->sc->sa);
378c517b3aaSDarrick J. Wong 		if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
379858333dcSDarrick J. Wong 				level, &error))
380858333dcSDarrick J. Wong 			return error;
381858333dcSDarrick J. Wong 	}
382858333dcSDarrick J. Wong 
383c517b3aaSDarrick J. Wong 	xchk_xref_is_used_space(bs->sc, agbno, 1);
38452dc4b44SDarrick J. Wong 	/*
38552dc4b44SDarrick J. Wong 	 * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we
38652dc4b44SDarrick J. Wong 	 * have to nullify it (to shut down further block owner checks) if
38752dc4b44SDarrick J. Wong 	 * self-xref encounters problems.
38852dc4b44SDarrick J. Wong 	 */
38952dc4b44SDarrick J. Wong 	if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO)
39052dc4b44SDarrick J. Wong 		bs->cur = NULL;
39152dc4b44SDarrick J. Wong 
392c517b3aaSDarrick J. Wong 	xchk_xref_is_owned_by(bs->sc, agbno, 1, bs->oinfo);
393d852657cSDarrick J. Wong 	if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP)
394d852657cSDarrick J. Wong 		bs->cur = NULL;
395d852657cSDarrick J. Wong 
396858333dcSDarrick J. Wong 	if (init_sa)
397c517b3aaSDarrick J. Wong 		xchk_ag_free(bs->sc, &bs->sc->sa);
398858333dcSDarrick J. Wong 
399858333dcSDarrick J. Wong 	return error;
400858333dcSDarrick J. Wong }
401858333dcSDarrick J. Wong 
402858333dcSDarrick J. Wong /* Check the owner of a btree block. */
403858333dcSDarrick J. Wong STATIC int
404c517b3aaSDarrick J. Wong xchk_btree_check_owner(
405c517b3aaSDarrick J. Wong 	struct xchk_btree	*bs,
406858333dcSDarrick J. Wong 	int			level,
407858333dcSDarrick J. Wong 	struct xfs_buf		*bp)
408858333dcSDarrick J. Wong {
409858333dcSDarrick J. Wong 	struct xfs_btree_cur	*cur = bs->cur;
410858333dcSDarrick J. Wong 	struct check_owner	*co;
411858333dcSDarrick J. Wong 
412a72e9d8dSDarrick J. Wong 	/*
413a72e9d8dSDarrick J. Wong 	 * In theory, xfs_btree_get_block should only give us a null buffer
414a72e9d8dSDarrick J. Wong 	 * pointer for the root of a root-in-inode btree type, but we need
415a72e9d8dSDarrick J. Wong 	 * to check defensively here in case the cursor state is also screwed
416a72e9d8dSDarrick J. Wong 	 * up.
417a72e9d8dSDarrick J. Wong 	 */
418a72e9d8dSDarrick J. Wong 	if (bp == NULL) {
419a72e9d8dSDarrick J. Wong 		if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
420a72e9d8dSDarrick J. Wong 			xchk_btree_set_corrupt(bs->sc, bs->cur, level);
421858333dcSDarrick J. Wong 		return 0;
422a72e9d8dSDarrick J. Wong 	}
423858333dcSDarrick J. Wong 
424858333dcSDarrick J. Wong 	/*
425858333dcSDarrick J. Wong 	 * We want to cross-reference each btree block with the bnobt
426858333dcSDarrick J. Wong 	 * and the rmapbt.  We cannot cross-reference the bnobt or
427858333dcSDarrick J. Wong 	 * rmapbt while scanning the bnobt or rmapbt, respectively,
428858333dcSDarrick J. Wong 	 * because we cannot alter the cursor and we'd prefer not to
429858333dcSDarrick J. Wong 	 * duplicate cursors.  Therefore, save the buffer daddr for
430858333dcSDarrick J. Wong 	 * later scanning.
431858333dcSDarrick J. Wong 	 */
432858333dcSDarrick J. Wong 	if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) {
433858333dcSDarrick J. Wong 		co = kmem_alloc(sizeof(struct check_owner),
434631fc955SDarrick J. Wong 				KM_MAYFAIL);
435858333dcSDarrick J. Wong 		if (!co)
436858333dcSDarrick J. Wong 			return -ENOMEM;
437858333dcSDarrick J. Wong 		co->level = level;
438858333dcSDarrick J. Wong 		co->daddr = XFS_BUF_ADDR(bp);
439858333dcSDarrick J. Wong 		list_add_tail(&co->list, &bs->to_check);
440858333dcSDarrick J. Wong 		return 0;
441858333dcSDarrick J. Wong 	}
442858333dcSDarrick J. Wong 
443c517b3aaSDarrick J. Wong 	return xchk_btree_check_block_owner(bs, level, XFS_BUF_ADDR(bp));
444858333dcSDarrick J. Wong }
445858333dcSDarrick J. Wong 
446ae7bae68SChandan Babu R /* Decide if we want to check minrecs of a btree block in the inode root. */
447ae7bae68SChandan Babu R static inline bool
448ae7bae68SChandan Babu R xchk_btree_check_iroot_minrecs(
449ae7bae68SChandan Babu R 	struct xchk_btree	*bs)
450ae7bae68SChandan Babu R {
451ae7bae68SChandan Babu R 	/*
452ae7bae68SChandan Babu R 	 * xfs_bmap_add_attrfork_btree had an implementation bug wherein it
453ae7bae68SChandan Babu R 	 * would miscalculate the space required for the data fork bmbt root
454ae7bae68SChandan Babu R 	 * when adding an attr fork, and promote the iroot contents to an
455ae7bae68SChandan Babu R 	 * external block unnecessarily.  This went unnoticed for many years
456ae7bae68SChandan Babu R 	 * until scrub found filesystems in this state.  Inode rooted btrees are
457ae7bae68SChandan Babu R 	 * not supposed to have immediate child blocks that are small enough
458ae7bae68SChandan Babu R 	 * that the contents could fit in the inode root, but we can't fail
459ae7bae68SChandan Babu R 	 * existing filesystems, so instead we disable the check for data fork
460ae7bae68SChandan Babu R 	 * bmap btrees when there's an attr fork.
461ae7bae68SChandan Babu R 	 */
462ae7bae68SChandan Babu R 	if (bs->cur->bc_btnum == XFS_BTNUM_BMAP &&
463ae7bae68SChandan Babu R 	    bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&
464ae7bae68SChandan Babu R 	    XFS_IFORK_Q(bs->sc->ip))
465ae7bae68SChandan Babu R 		return false;
466ae7bae68SChandan Babu R 
467ae7bae68SChandan Babu R 	return true;
468ae7bae68SChandan Babu R }
469ae7bae68SChandan Babu R 
470cc3e0948SDarrick J. Wong /*
47108a3a692SDarrick J. Wong  * Check that this btree block has at least minrecs records or is one of the
47208a3a692SDarrick J. Wong  * special blocks that don't require that.
47308a3a692SDarrick J. Wong  */
47408a3a692SDarrick J. Wong STATIC void
475c517b3aaSDarrick J. Wong xchk_btree_check_minrecs(
476c517b3aaSDarrick J. Wong 	struct xchk_btree	*bs,
47708a3a692SDarrick J. Wong 	int			level,
47808a3a692SDarrick J. Wong 	struct xfs_btree_block	*block)
47908a3a692SDarrick J. Wong {
480e95b6c3eSDarrick J. Wong 	struct xfs_btree_cur	*cur = bs->cur;
481e95b6c3eSDarrick J. Wong 	unsigned int		root_level = cur->bc_nlevels - 1;
482e95b6c3eSDarrick J. Wong 	unsigned int		numrecs = be16_to_cpu(block->bb_numrecs);
48308a3a692SDarrick J. Wong 
48408a3a692SDarrick J. Wong 	/* More records than minrecs means the block is ok. */
485e95b6c3eSDarrick J. Wong 	if (numrecs >= cur->bc_ops->get_minrecs(cur, level))
48608a3a692SDarrick J. Wong 		return;
48708a3a692SDarrick J. Wong 
48808a3a692SDarrick J. Wong 	/*
489e95b6c3eSDarrick J. Wong 	 * For btrees rooted in the inode, it's possible that the root block
490e95b6c3eSDarrick J. Wong 	 * contents spilled into a regular ondisk block because there wasn't
491e95b6c3eSDarrick J. Wong 	 * enough space in the inode root.  The number of records in that
492e95b6c3eSDarrick J. Wong 	 * child block might be less than the standard minrecs, but that's ok
493e95b6c3eSDarrick J. Wong 	 * provided that there's only one direct child of the root.
49408a3a692SDarrick J. Wong 	 */
495e95b6c3eSDarrick J. Wong 	if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
496e95b6c3eSDarrick J. Wong 	    level == cur->bc_nlevels - 2) {
497e95b6c3eSDarrick J. Wong 		struct xfs_btree_block	*root_block;
498e95b6c3eSDarrick J. Wong 		struct xfs_buf		*root_bp;
499e95b6c3eSDarrick J. Wong 		int			root_maxrecs;
50008a3a692SDarrick J. Wong 
501e95b6c3eSDarrick J. Wong 		root_block = xfs_btree_get_block(cur, root_level, &root_bp);
502e95b6c3eSDarrick J. Wong 		root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);
503ae7bae68SChandan Babu R 		if (xchk_btree_check_iroot_minrecs(bs) &&
504ae7bae68SChandan Babu R 		    (be16_to_cpu(root_block->bb_numrecs) != 1 ||
505ae7bae68SChandan Babu R 		     numrecs <= root_maxrecs))
506e95b6c3eSDarrick J. Wong 			xchk_btree_set_corrupt(bs->sc, cur, level);
507e95b6c3eSDarrick J. Wong 		return;
508e95b6c3eSDarrick J. Wong 	}
509e95b6c3eSDarrick J. Wong 
510e95b6c3eSDarrick J. Wong 	/*
511e95b6c3eSDarrick J. Wong 	 * Otherwise, only the root level is allowed to have fewer than minrecs
512e95b6c3eSDarrick J. Wong 	 * records or keyptrs.
513e95b6c3eSDarrick J. Wong 	 */
514e95b6c3eSDarrick J. Wong 	if (level < root_level)
515e95b6c3eSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, level);
51608a3a692SDarrick J. Wong }
51708a3a692SDarrick J. Wong 
51808a3a692SDarrick J. Wong /*
519cc3e0948SDarrick J. Wong  * Grab and scrub a btree block given a btree pointer.  Returns block
520cc3e0948SDarrick J. Wong  * and buffer pointers (if applicable) if they're ok to use.
521cc3e0948SDarrick J. Wong  */
522cc3e0948SDarrick J. Wong STATIC int
523c517b3aaSDarrick J. Wong xchk_btree_get_block(
524c517b3aaSDarrick J. Wong 	struct xchk_btree	*bs,
525cc3e0948SDarrick J. Wong 	int			level,
526cc3e0948SDarrick J. Wong 	union xfs_btree_ptr	*pp,
527cc3e0948SDarrick J. Wong 	struct xfs_btree_block	**pblock,
528cc3e0948SDarrick J. Wong 	struct xfs_buf		**pbp)
529cc3e0948SDarrick J. Wong {
530032d91f9SDarrick J. Wong 	xfs_failaddr_t		failed_at;
531cc3e0948SDarrick J. Wong 	int			error;
532cc3e0948SDarrick J. Wong 
533cc3e0948SDarrick J. Wong 	*pblock = NULL;
534cc3e0948SDarrick J. Wong 	*pbp = NULL;
535cc3e0948SDarrick J. Wong 
536cc3e0948SDarrick J. Wong 	error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
537c517b3aaSDarrick J. Wong 	if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
538a605e869SDarrick J. Wong 	    !*pblock)
539cc3e0948SDarrick J. Wong 		return error;
540cc3e0948SDarrick J. Wong 
541cc3e0948SDarrick J. Wong 	xfs_btree_get_block(bs->cur, level, pbp);
542cc3e0948SDarrick J. Wong 	if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
543cc3e0948SDarrick J. Wong 		failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
544cc3e0948SDarrick J. Wong 				level, *pbp);
545cc3e0948SDarrick J. Wong 	else
546cc3e0948SDarrick J. Wong 		failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
547cc3e0948SDarrick J. Wong 				 level, *pbp);
548cc3e0948SDarrick J. Wong 	if (failed_at) {
549c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, bs->cur, level);
550cc3e0948SDarrick J. Wong 		return 0;
551cc3e0948SDarrick J. Wong 	}
552cf1b0b8bSDarrick J. Wong 	if (*pbp)
553c517b3aaSDarrick J. Wong 		xchk_buffer_recheck(bs->sc, *pbp);
554cc3e0948SDarrick J. Wong 
555c517b3aaSDarrick J. Wong 	xchk_btree_check_minrecs(bs, level, *pblock);
55608a3a692SDarrick J. Wong 
557cc3e0948SDarrick J. Wong 	/*
558858333dcSDarrick J. Wong 	 * Check the block's owner; this function absorbs error codes
559858333dcSDarrick J. Wong 	 * for us.
560858333dcSDarrick J. Wong 	 */
561c517b3aaSDarrick J. Wong 	error = xchk_btree_check_owner(bs, level, *pbp);
562858333dcSDarrick J. Wong 	if (error)
563858333dcSDarrick J. Wong 		return error;
564858333dcSDarrick J. Wong 
565858333dcSDarrick J. Wong 	/*
566cc3e0948SDarrick J. Wong 	 * Check the block's siblings; this function absorbs error codes
567cc3e0948SDarrick J. Wong 	 * for us.
568cc3e0948SDarrick J. Wong 	 */
569c517b3aaSDarrick J. Wong 	return xchk_btree_block_check_siblings(bs, *pblock);
570cc3e0948SDarrick J. Wong }
571cc3e0948SDarrick J. Wong 
572cc3e0948SDarrick J. Wong /*
5732fdbec5cSDarrick J. Wong  * Check that the low and high keys of this block match the keys stored
5742fdbec5cSDarrick J. Wong  * in the parent block.
5752fdbec5cSDarrick J. Wong  */
5762fdbec5cSDarrick J. Wong STATIC void
577c517b3aaSDarrick J. Wong xchk_btree_block_keys(
578c517b3aaSDarrick J. Wong 	struct xchk_btree	*bs,
5792fdbec5cSDarrick J. Wong 	int			level,
5802fdbec5cSDarrick J. Wong 	struct xfs_btree_block	*block)
5812fdbec5cSDarrick J. Wong {
5822fdbec5cSDarrick J. Wong 	union xfs_btree_key	block_keys;
5832fdbec5cSDarrick J. Wong 	struct xfs_btree_cur	*cur = bs->cur;
5842fdbec5cSDarrick J. Wong 	union xfs_btree_key	*high_bk;
5852fdbec5cSDarrick J. Wong 	union xfs_btree_key	*parent_keys;
5862fdbec5cSDarrick J. Wong 	union xfs_btree_key	*high_pk;
5872fdbec5cSDarrick J. Wong 	struct xfs_btree_block	*parent_block;
5882fdbec5cSDarrick J. Wong 	struct xfs_buf		*bp;
5892fdbec5cSDarrick J. Wong 
5902fdbec5cSDarrick J. Wong 	if (level >= cur->bc_nlevels - 1)
5912fdbec5cSDarrick J. Wong 		return;
5922fdbec5cSDarrick J. Wong 
5932fdbec5cSDarrick J. Wong 	/* Calculate the keys for this block. */
5942fdbec5cSDarrick J. Wong 	xfs_btree_get_keys(cur, block, &block_keys);
5952fdbec5cSDarrick J. Wong 
5962fdbec5cSDarrick J. Wong 	/* Obtain the parent's copy of the keys for this block. */
5972fdbec5cSDarrick J. Wong 	parent_block = xfs_btree_get_block(cur, level + 1, &bp);
5982fdbec5cSDarrick J. Wong 	parent_keys = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1],
5992fdbec5cSDarrick J. Wong 			parent_block);
6002fdbec5cSDarrick J. Wong 
6012fdbec5cSDarrick J. Wong 	if (cur->bc_ops->diff_two_keys(cur, &block_keys, parent_keys) != 0)
602c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, 1);
6032fdbec5cSDarrick J. Wong 
6042fdbec5cSDarrick J. Wong 	if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
6052fdbec5cSDarrick J. Wong 		return;
6062fdbec5cSDarrick J. Wong 
6072fdbec5cSDarrick J. Wong 	/* Get high keys */
6082fdbec5cSDarrick J. Wong 	high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
6092fdbec5cSDarrick J. Wong 	high_pk = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1],
6102fdbec5cSDarrick J. Wong 			parent_block);
6112fdbec5cSDarrick J. Wong 
6122fdbec5cSDarrick J. Wong 	if (cur->bc_ops->diff_two_keys(cur, high_bk, high_pk) != 0)
613c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(bs->sc, cur, 1);
6142fdbec5cSDarrick J. Wong }
6152fdbec5cSDarrick J. Wong 
6162fdbec5cSDarrick J. Wong /*
617537964bcSDarrick J. Wong  * Visit all nodes and leaves of a btree.  Check that all pointers and
618537964bcSDarrick J. Wong  * records are in order, that the keys reflect the records, and use a callback
619cc3e0948SDarrick J. Wong  * so that the caller can verify individual records.
620537964bcSDarrick J. Wong  */
621537964bcSDarrick J. Wong int
622c517b3aaSDarrick J. Wong xchk_btree(
6231d8a748aSDarrick J. Wong 	struct xfs_scrub		*sc,
624537964bcSDarrick J. Wong 	struct xfs_btree_cur		*cur,
625c517b3aaSDarrick J. Wong 	xchk_btree_rec_fn		scrub_fn,
62666e3237eSDarrick J. Wong 	const struct xfs_owner_info	*oinfo,
627537964bcSDarrick J. Wong 	void				*private)
628537964bcSDarrick J. Wong {
62966e3237eSDarrick J. Wong 	struct xchk_btree		bs = {
63066e3237eSDarrick J. Wong 		.cur			= cur,
63166e3237eSDarrick J. Wong 		.scrub_rec		= scrub_fn,
63266e3237eSDarrick J. Wong 		.oinfo			= oinfo,
63366e3237eSDarrick J. Wong 		.firstrec		= true,
63466e3237eSDarrick J. Wong 		.private		= private,
63566e3237eSDarrick J. Wong 		.sc			= sc,
63666e3237eSDarrick J. Wong 	};
637cc3e0948SDarrick J. Wong 	union xfs_btree_ptr		ptr;
638cc3e0948SDarrick J. Wong 	union xfs_btree_ptr		*pp;
63937f3fa7fSDarrick J. Wong 	union xfs_btree_rec		*recp;
640cc3e0948SDarrick J. Wong 	struct xfs_btree_block		*block;
641cc3e0948SDarrick J. Wong 	int				level;
642cc3e0948SDarrick J. Wong 	struct xfs_buf			*bp;
643858333dcSDarrick J. Wong 	struct check_owner		*co;
644858333dcSDarrick J. Wong 	struct check_owner		*n;
645cc3e0948SDarrick J. Wong 	int				i;
646cc3e0948SDarrick J. Wong 	int				error = 0;
647537964bcSDarrick J. Wong 
648cc3e0948SDarrick J. Wong 	/* Initialize scrub state */
649cc3e0948SDarrick J. Wong 	for (i = 0; i < XFS_BTREE_MAXLEVELS; i++)
650cc3e0948SDarrick J. Wong 		bs.firstkey[i] = true;
651cc3e0948SDarrick J. Wong 	INIT_LIST_HEAD(&bs.to_check);
652cc3e0948SDarrick J. Wong 
653cc3e0948SDarrick J. Wong 	/* Don't try to check a tree with a height we can't handle. */
654cc3e0948SDarrick J. Wong 	if (cur->bc_nlevels > XFS_BTREE_MAXLEVELS) {
655c517b3aaSDarrick J. Wong 		xchk_btree_set_corrupt(sc, cur, 0);
656cc3e0948SDarrick J. Wong 		goto out;
657cc3e0948SDarrick J. Wong 	}
658cc3e0948SDarrick J. Wong 
659cc3e0948SDarrick J. Wong 	/*
660cc3e0948SDarrick J. Wong 	 * Load the root of the btree.  The helper function absorbs
661cc3e0948SDarrick J. Wong 	 * error codes for us.
662cc3e0948SDarrick J. Wong 	 */
663cc3e0948SDarrick J. Wong 	level = cur->bc_nlevels - 1;
664cc3e0948SDarrick J. Wong 	cur->bc_ops->init_ptr_from_cur(cur, &ptr);
665c517b3aaSDarrick J. Wong 	if (!xchk_btree_ptr_ok(&bs, cur->bc_nlevels, &ptr))
666cc3e0948SDarrick J. Wong 		goto out;
667c517b3aaSDarrick J. Wong 	error = xchk_btree_get_block(&bs, level, &ptr, &block, &bp);
668cc3e0948SDarrick J. Wong 	if (error || !block)
669cc3e0948SDarrick J. Wong 		goto out;
670cc3e0948SDarrick J. Wong 
671cc3e0948SDarrick J. Wong 	cur->bc_ptrs[level] = 1;
672cc3e0948SDarrick J. Wong 
673cc3e0948SDarrick J. Wong 	while (level < cur->bc_nlevels) {
674cc3e0948SDarrick J. Wong 		block = xfs_btree_get_block(cur, level, &bp);
675cc3e0948SDarrick J. Wong 
676cc3e0948SDarrick J. Wong 		if (level == 0) {
677cc3e0948SDarrick J. Wong 			/* End of leaf, pop back towards the root. */
678cc3e0948SDarrick J. Wong 			if (cur->bc_ptrs[level] >
679cc3e0948SDarrick J. Wong 			    be16_to_cpu(block->bb_numrecs)) {
680c517b3aaSDarrick J. Wong 				xchk_btree_block_keys(&bs, level, block);
681cc3e0948SDarrick J. Wong 				if (level < cur->bc_nlevels - 1)
682cc3e0948SDarrick J. Wong 					cur->bc_ptrs[level + 1]++;
683cc3e0948SDarrick J. Wong 				level++;
684cc3e0948SDarrick J. Wong 				continue;
685cc3e0948SDarrick J. Wong 			}
686cc3e0948SDarrick J. Wong 
68737f3fa7fSDarrick J. Wong 			/* Records in order for scrub? */
688c517b3aaSDarrick J. Wong 			xchk_btree_rec(&bs);
68937f3fa7fSDarrick J. Wong 
69037f3fa7fSDarrick J. Wong 			/* Call out to the record checker. */
69137f3fa7fSDarrick J. Wong 			recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block);
69237f3fa7fSDarrick J. Wong 			error = bs.scrub_rec(&bs, recp);
69337f3fa7fSDarrick J. Wong 			if (error)
69437f3fa7fSDarrick J. Wong 				break;
695c517b3aaSDarrick J. Wong 			if (xchk_should_terminate(sc, &error) ||
69637f3fa7fSDarrick J. Wong 			    (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
697cc3e0948SDarrick J. Wong 				break;
698cc3e0948SDarrick J. Wong 
699cc3e0948SDarrick J. Wong 			cur->bc_ptrs[level]++;
700cc3e0948SDarrick J. Wong 			continue;
701cc3e0948SDarrick J. Wong 		}
702cc3e0948SDarrick J. Wong 
703cc3e0948SDarrick J. Wong 		/* End of node, pop back towards the root. */
704cc3e0948SDarrick J. Wong 		if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) {
705c517b3aaSDarrick J. Wong 			xchk_btree_block_keys(&bs, level, block);
706cc3e0948SDarrick J. Wong 			if (level < cur->bc_nlevels - 1)
707cc3e0948SDarrick J. Wong 				cur->bc_ptrs[level + 1]++;
708cc3e0948SDarrick J. Wong 			level++;
709cc3e0948SDarrick J. Wong 			continue;
710cc3e0948SDarrick J. Wong 		}
711cc3e0948SDarrick J. Wong 
71237f3fa7fSDarrick J. Wong 		/* Keys in order for scrub? */
713c517b3aaSDarrick J. Wong 		xchk_btree_key(&bs, level);
71437f3fa7fSDarrick J. Wong 
715cc3e0948SDarrick J. Wong 		/* Drill another level deeper. */
716cc3e0948SDarrick J. Wong 		pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block);
717c517b3aaSDarrick J. Wong 		if (!xchk_btree_ptr_ok(&bs, level, pp)) {
718cc3e0948SDarrick J. Wong 			cur->bc_ptrs[level]++;
719cc3e0948SDarrick J. Wong 			continue;
720cc3e0948SDarrick J. Wong 		}
721cc3e0948SDarrick J. Wong 		level--;
722c517b3aaSDarrick J. Wong 		error = xchk_btree_get_block(&bs, level, pp, &block, &bp);
723cc3e0948SDarrick J. Wong 		if (error || !block)
724cc3e0948SDarrick J. Wong 			goto out;
725cc3e0948SDarrick J. Wong 
726cc3e0948SDarrick J. Wong 		cur->bc_ptrs[level] = 1;
727cc3e0948SDarrick J. Wong 	}
728cc3e0948SDarrick J. Wong 
729cc3e0948SDarrick J. Wong out:
730858333dcSDarrick J. Wong 	/* Process deferred owner checks on btree blocks. */
731858333dcSDarrick J. Wong 	list_for_each_entry_safe(co, n, &bs.to_check, list) {
732858333dcSDarrick J. Wong 		if (!error && bs.cur)
733c517b3aaSDarrick J. Wong 			error = xchk_btree_check_block_owner(&bs,
734858333dcSDarrick J. Wong 					co->level, co->daddr);
735858333dcSDarrick J. Wong 		list_del(&co->list);
736858333dcSDarrick J. Wong 		kmem_free(co);
737858333dcSDarrick J. Wong 	}
738858333dcSDarrick J. Wong 
739537964bcSDarrick J. Wong 	return error;
740537964bcSDarrick J. Wong }
741