• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3  * Copyright (C) 2017 Oracle.  All Rights Reserved.
4  * Author: Darrick J. Wong <darrick.wong@oracle.com>
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_inode.h"
13 #include "xfs_btree.h"
14 #include "scrub/scrub.h"
15 #include "scrub/common.h"
16 #include "scrub/btree.h"
17 #include "scrub/trace.h"
18 
19 /* btree scrubbing */
20 
21 /*
22  * Check for btree operation errors.  See the section about handling
23  * operational errors in common.c.
24  */
25 static bool
__xchk_btree_process_error(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level,int * error,__u32 errflag,void * ret_ip)26 __xchk_btree_process_error(
27 	struct xfs_scrub	*sc,
28 	struct xfs_btree_cur	*cur,
29 	int			level,
30 	int			*error,
31 	__u32			errflag,
32 	void			*ret_ip)
33 {
34 	if (*error == 0)
35 		return true;
36 
37 	switch (*error) {
38 	case -EDEADLOCK:
39 		/* Used to restart an op with deadlock avoidance. */
40 		trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
41 		break;
42 	case -EFSBADCRC:
43 	case -EFSCORRUPTED:
44 		/* Note the badness but don't abort. */
45 		sc->sm->sm_flags |= errflag;
46 		*error = 0;
47 		fallthrough;
48 	default:
49 		if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
50 			trace_xchk_ifork_btree_op_error(sc, cur, level,
51 					*error, ret_ip);
52 		else
53 			trace_xchk_btree_op_error(sc, cur, level,
54 					*error, ret_ip);
55 		break;
56 	}
57 	return false;
58 }
59 
60 bool
xchk_btree_process_error(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level,int * error)61 xchk_btree_process_error(
62 	struct xfs_scrub	*sc,
63 	struct xfs_btree_cur	*cur,
64 	int			level,
65 	int			*error)
66 {
67 	return __xchk_btree_process_error(sc, cur, level, error,
68 			XFS_SCRUB_OFLAG_CORRUPT, __return_address);
69 }
70 
71 bool
xchk_btree_xref_process_error(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level,int * error)72 xchk_btree_xref_process_error(
73 	struct xfs_scrub	*sc,
74 	struct xfs_btree_cur	*cur,
75 	int			level,
76 	int			*error)
77 {
78 	return __xchk_btree_process_error(sc, cur, level, error,
79 			XFS_SCRUB_OFLAG_XFAIL, __return_address);
80 }
81 
82 /* Record btree block corruption. */
83 static void
__xchk_btree_set_corrupt(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level,__u32 errflag,void * ret_ip)84 __xchk_btree_set_corrupt(
85 	struct xfs_scrub	*sc,
86 	struct xfs_btree_cur	*cur,
87 	int			level,
88 	__u32			errflag,
89 	void			*ret_ip)
90 {
91 	sc->sm->sm_flags |= errflag;
92 
93 	if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
94 		trace_xchk_ifork_btree_error(sc, cur, level,
95 				ret_ip);
96 	else
97 		trace_xchk_btree_error(sc, cur, level,
98 				ret_ip);
99 }
100 
101 void
xchk_btree_set_corrupt(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level)102 xchk_btree_set_corrupt(
103 	struct xfs_scrub	*sc,
104 	struct xfs_btree_cur	*cur,
105 	int			level)
106 {
107 	__xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT,
108 			__return_address);
109 }
110 
111 void
xchk_btree_xref_set_corrupt(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level)112 xchk_btree_xref_set_corrupt(
113 	struct xfs_scrub	*sc,
114 	struct xfs_btree_cur	*cur,
115 	int			level)
116 {
117 	__xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT,
118 			__return_address);
119 }
120 
121 /*
122  * Make sure this record is in order and doesn't stray outside of the parent
123  * keys.
124  */
125 STATIC void
xchk_btree_rec(struct xchk_btree * bs)126 xchk_btree_rec(
127 	struct xchk_btree	*bs)
128 {
129 	struct xfs_btree_cur	*cur = bs->cur;
130 	union xfs_btree_rec	*rec;
131 	union xfs_btree_key	key;
132 	union xfs_btree_key	hkey;
133 	union xfs_btree_key	*keyp;
134 	struct xfs_btree_block	*block;
135 	struct xfs_btree_block	*keyblock;
136 	struct xfs_buf		*bp;
137 
138 	block = xfs_btree_get_block(cur, 0, &bp);
139 	rec = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block);
140 
141 	trace_xchk_btree_rec(bs->sc, cur, 0);
142 
143 	/* If this isn't the first record, are they in order? */
144 	if (!bs->firstrec && !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
145 		xchk_btree_set_corrupt(bs->sc, cur, 0);
146 	bs->firstrec = false;
147 	memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);
148 
149 	if (cur->bc_nlevels == 1)
150 		return;
151 
152 	/* Is this at least as large as the parent low key? */
153 	cur->bc_ops->init_key_from_rec(&key, rec);
154 	keyblock = xfs_btree_get_block(cur, 1, &bp);
155 	keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[1], keyblock);
156 	if (cur->bc_ops->diff_two_keys(cur, &key, keyp) < 0)
157 		xchk_btree_set_corrupt(bs->sc, cur, 1);
158 
159 	if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
160 		return;
161 
162 	/* Is this no larger than the parent high key? */
163 	cur->bc_ops->init_high_key_from_rec(&hkey, rec);
164 	keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[1], keyblock);
165 	if (cur->bc_ops->diff_two_keys(cur, keyp, &hkey) < 0)
166 		xchk_btree_set_corrupt(bs->sc, cur, 1);
167 }
168 
169 /*
170  * Make sure this key is in order and doesn't stray outside of the parent
171  * keys.
172  */
173 STATIC void
xchk_btree_key(struct xchk_btree * bs,int level)174 xchk_btree_key(
175 	struct xchk_btree	*bs,
176 	int			level)
177 {
178 	struct xfs_btree_cur	*cur = bs->cur;
179 	union xfs_btree_key	*key;
180 	union xfs_btree_key	*keyp;
181 	struct xfs_btree_block	*block;
182 	struct xfs_btree_block	*keyblock;
183 	struct xfs_buf		*bp;
184 
185 	block = xfs_btree_get_block(cur, level, &bp);
186 	key = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block);
187 
188 	trace_xchk_btree_key(bs->sc, cur, level);
189 
190 	/* If this isn't the first key, are they in order? */
191 	if (!bs->firstkey[level] &&
192 	    !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level], key))
193 		xchk_btree_set_corrupt(bs->sc, cur, level);
194 	bs->firstkey[level] = false;
195 	memcpy(&bs->lastkey[level], key, cur->bc_ops->key_len);
196 
197 	if (level + 1 >= cur->bc_nlevels)
198 		return;
199 
200 	/* Is this at least as large as the parent low key? */
201 	keyblock = xfs_btree_get_block(cur, level + 1, &bp);
202 	keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1], keyblock);
203 	if (cur->bc_ops->diff_two_keys(cur, key, keyp) < 0)
204 		xchk_btree_set_corrupt(bs->sc, cur, level);
205 
206 	if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
207 		return;
208 
209 	/* Is this no larger than the parent high key? */
210 	key = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block);
211 	keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1], keyblock);
212 	if (cur->bc_ops->diff_two_keys(cur, keyp, key) < 0)
213 		xchk_btree_set_corrupt(bs->sc, cur, level);
214 }
215 
216 /*
217  * Check a btree pointer.  Returns true if it's ok to use this pointer.
218  * Callers do not need to set the corrupt flag.
219  */
220 static bool
xchk_btree_ptr_ok(struct xchk_btree * bs,int level,union xfs_btree_ptr * ptr)221 xchk_btree_ptr_ok(
222 	struct xchk_btree	*bs,
223 	int			level,
224 	union xfs_btree_ptr	*ptr)
225 {
226 	bool			res;
227 
228 	/* A btree rooted in an inode has no block pointer to the root. */
229 	if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
230 	    level == bs->cur->bc_nlevels)
231 		return true;
232 
233 	/* Otherwise, check the pointers. */
234 	if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
235 		res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
236 	else
237 		res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
238 	if (!res)
239 		xchk_btree_set_corrupt(bs->sc, bs->cur, level);
240 
241 	return res;
242 }
243 
244 /* Check that a btree block's sibling matches what we expect it. */
245 STATIC int
xchk_btree_block_check_sibling(struct xchk_btree * bs,int level,int direction,union xfs_btree_ptr * sibling)246 xchk_btree_block_check_sibling(
247 	struct xchk_btree	*bs,
248 	int			level,
249 	int			direction,
250 	union xfs_btree_ptr	*sibling)
251 {
252 	struct xfs_btree_cur	*cur = bs->cur;
253 	struct xfs_btree_block	*pblock;
254 	struct xfs_buf		*pbp;
255 	struct xfs_btree_cur	*ncur = NULL;
256 	union xfs_btree_ptr	*pp;
257 	int			success;
258 	int			error;
259 
260 	error = xfs_btree_dup_cursor(cur, &ncur);
261 	if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
262 	    !ncur)
263 		return error;
264 
265 	/*
266 	 * If the pointer is null, we shouldn't be able to move the upper
267 	 * level pointer anywhere.
268 	 */
269 	if (xfs_btree_ptr_is_null(cur, sibling)) {
270 		if (direction > 0)
271 			error = xfs_btree_increment(ncur, level + 1, &success);
272 		else
273 			error = xfs_btree_decrement(ncur, level + 1, &success);
274 		if (error == 0 && success)
275 			xchk_btree_set_corrupt(bs->sc, cur, level);
276 		error = 0;
277 		goto out;
278 	}
279 
280 	/* Increment upper level pointer. */
281 	if (direction > 0)
282 		error = xfs_btree_increment(ncur, level + 1, &success);
283 	else
284 		error = xfs_btree_decrement(ncur, level + 1, &success);
285 	if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
286 		goto out;
287 	if (!success) {
288 		xchk_btree_set_corrupt(bs->sc, cur, level + 1);
289 		goto out;
290 	}
291 
292 	/* Compare upper level pointer to sibling pointer. */
293 	pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
294 	pp = xfs_btree_ptr_addr(ncur, ncur->bc_ptrs[level + 1], pblock);
295 	if (!xchk_btree_ptr_ok(bs, level + 1, pp))
296 		goto out;
297 	if (pbp)
298 		xchk_buffer_recheck(bs->sc, pbp);
299 
300 	if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
301 		xchk_btree_set_corrupt(bs->sc, cur, level);
302 out:
303 	xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
304 	return error;
305 }
306 
307 /* Check the siblings of a btree block. */
308 STATIC int
xchk_btree_block_check_siblings(struct xchk_btree * bs,struct xfs_btree_block * block)309 xchk_btree_block_check_siblings(
310 	struct xchk_btree	*bs,
311 	struct xfs_btree_block	*block)
312 {
313 	struct xfs_btree_cur	*cur = bs->cur;
314 	union xfs_btree_ptr	leftsib;
315 	union xfs_btree_ptr	rightsib;
316 	int			level;
317 	int			error = 0;
318 
319 	xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
320 	xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
321 	level = xfs_btree_get_level(block);
322 
323 	/* Root block should never have siblings. */
324 	if (level == cur->bc_nlevels - 1) {
325 		if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
326 		    !xfs_btree_ptr_is_null(cur, &rightsib))
327 			xchk_btree_set_corrupt(bs->sc, cur, level);
328 		goto out;
329 	}
330 
331 	/*
332 	 * Does the left & right sibling pointers match the adjacent
333 	 * parent level pointers?
334 	 * (These function absorbs error codes for us.)
335 	 */
336 	error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
337 	if (error)
338 		return error;
339 	error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
340 	if (error)
341 		return error;
342 out:
343 	return error;
344 }
345 
346 struct check_owner {
347 	struct list_head	list;
348 	xfs_daddr_t		daddr;
349 	int			level;
350 };
351 
352 /*
353  * Make sure this btree block isn't in the free list and that there's
354  * an rmap record for it.
355  */
356 STATIC int
xchk_btree_check_block_owner(struct xchk_btree * bs,int level,xfs_daddr_t daddr)357 xchk_btree_check_block_owner(
358 	struct xchk_btree	*bs,
359 	int			level,
360 	xfs_daddr_t		daddr)
361 {
362 	xfs_agnumber_t		agno;
363 	xfs_agblock_t		agbno;
364 	xfs_btnum_t		btnum;
365 	bool			init_sa;
366 	int			error = 0;
367 
368 	if (!bs->cur)
369 		return 0;
370 
371 	btnum = bs->cur->bc_btnum;
372 	agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
373 	agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);
374 
375 	init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS;
376 	if (init_sa) {
377 		error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa);
378 		if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
379 				level, &error))
380 			goto out_free;
381 	}
382 
383 	xchk_xref_is_used_space(bs->sc, agbno, 1);
384 	/*
385 	 * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we
386 	 * have to nullify it (to shut down further block owner checks) if
387 	 * self-xref encounters problems.
388 	 */
389 	if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO)
390 		bs->cur = NULL;
391 
392 	xchk_xref_is_owned_by(bs->sc, agbno, 1, bs->oinfo);
393 	if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP)
394 		bs->cur = NULL;
395 
396 out_free:
397 	if (init_sa)
398 		xchk_ag_free(bs->sc, &bs->sc->sa);
399 
400 	return error;
401 }
402 
403 /* Check the owner of a btree block. */
404 STATIC int
xchk_btree_check_owner(struct xchk_btree * bs,int level,struct xfs_buf * bp)405 xchk_btree_check_owner(
406 	struct xchk_btree	*bs,
407 	int			level,
408 	struct xfs_buf		*bp)
409 {
410 	struct xfs_btree_cur	*cur = bs->cur;
411 	struct check_owner	*co;
412 
413 	/*
414 	 * In theory, xfs_btree_get_block should only give us a null buffer
415 	 * pointer for the root of a root-in-inode btree type, but we need
416 	 * to check defensively here in case the cursor state is also screwed
417 	 * up.
418 	 */
419 	if (bp == NULL) {
420 		if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
421 			xchk_btree_set_corrupt(bs->sc, bs->cur, level);
422 		return 0;
423 	}
424 
425 	/*
426 	 * We want to cross-reference each btree block with the bnobt
427 	 * and the rmapbt.  We cannot cross-reference the bnobt or
428 	 * rmapbt while scanning the bnobt or rmapbt, respectively,
429 	 * because we cannot alter the cursor and we'd prefer not to
430 	 * duplicate cursors.  Therefore, save the buffer daddr for
431 	 * later scanning.
432 	 */
433 	if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) {
434 		co = kmem_alloc(sizeof(struct check_owner),
435 				KM_MAYFAIL);
436 		if (!co)
437 			return -ENOMEM;
438 		co->level = level;
439 		co->daddr = xfs_buf_daddr(bp);
440 		list_add_tail(&co->list, &bs->to_check);
441 		return 0;
442 	}
443 
444 	return xchk_btree_check_block_owner(bs, level, xfs_buf_daddr(bp));
445 }
446 
447 /* Decide if we want to check minrecs of a btree block in the inode root. */
448 static inline bool
xchk_btree_check_iroot_minrecs(struct xchk_btree * bs)449 xchk_btree_check_iroot_minrecs(
450 	struct xchk_btree	*bs)
451 {
452 	/*
453 	 * xfs_bmap_add_attrfork_btree had an implementation bug wherein it
454 	 * would miscalculate the space required for the data fork bmbt root
455 	 * when adding an attr fork, and promote the iroot contents to an
456 	 * external block unnecessarily.  This went unnoticed for many years
457 	 * until scrub found filesystems in this state.  Inode rooted btrees are
458 	 * not supposed to have immediate child blocks that are small enough
459 	 * that the contents could fit in the inode root, but we can't fail
460 	 * existing filesystems, so instead we disable the check for data fork
461 	 * bmap btrees when there's an attr fork.
462 	 */
463 	if (bs->cur->bc_btnum == XFS_BTNUM_BMAP &&
464 	    bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&
465 	    XFS_IFORK_Q(bs->sc->ip))
466 		return false;
467 
468 	return true;
469 }
470 
471 /*
472  * Check that this btree block has at least minrecs records or is one of the
473  * special blocks that don't require that.
474  */
475 STATIC void
xchk_btree_check_minrecs(struct xchk_btree * bs,int level,struct xfs_btree_block * block)476 xchk_btree_check_minrecs(
477 	struct xchk_btree	*bs,
478 	int			level,
479 	struct xfs_btree_block	*block)
480 {
481 	struct xfs_btree_cur	*cur = bs->cur;
482 	unsigned int		root_level = cur->bc_nlevels - 1;
483 	unsigned int		numrecs = be16_to_cpu(block->bb_numrecs);
484 
485 	/* More records than minrecs means the block is ok. */
486 	if (numrecs >= cur->bc_ops->get_minrecs(cur, level))
487 		return;
488 
489 	/*
490 	 * For btrees rooted in the inode, it's possible that the root block
491 	 * contents spilled into a regular ondisk block because there wasn't
492 	 * enough space in the inode root.  The number of records in that
493 	 * child block might be less than the standard minrecs, but that's ok
494 	 * provided that there's only one direct child of the root.
495 	 */
496 	if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
497 	    level == cur->bc_nlevels - 2) {
498 		struct xfs_btree_block	*root_block;
499 		struct xfs_buf		*root_bp;
500 		int			root_maxrecs;
501 
502 		root_block = xfs_btree_get_block(cur, root_level, &root_bp);
503 		root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);
504 		if (xchk_btree_check_iroot_minrecs(bs) &&
505 		    (be16_to_cpu(root_block->bb_numrecs) != 1 ||
506 		     numrecs <= root_maxrecs))
507 			xchk_btree_set_corrupt(bs->sc, cur, level);
508 		return;
509 	}
510 
511 	/*
512 	 * Otherwise, only the root level is allowed to have fewer than minrecs
513 	 * records or keyptrs.
514 	 */
515 	if (level < root_level)
516 		xchk_btree_set_corrupt(bs->sc, cur, level);
517 }
518 
519 /*
520  * Grab and scrub a btree block given a btree pointer.  Returns block
521  * and buffer pointers (if applicable) if they're ok to use.
522  */
523 STATIC int
xchk_btree_get_block(struct xchk_btree * bs,int level,union xfs_btree_ptr * pp,struct xfs_btree_block ** pblock,struct xfs_buf ** pbp)524 xchk_btree_get_block(
525 	struct xchk_btree	*bs,
526 	int			level,
527 	union xfs_btree_ptr	*pp,
528 	struct xfs_btree_block	**pblock,
529 	struct xfs_buf		**pbp)
530 {
531 	xfs_failaddr_t		failed_at;
532 	int			error;
533 
534 	*pblock = NULL;
535 	*pbp = NULL;
536 
537 	error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
538 	if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
539 	    !*pblock)
540 		return error;
541 
542 	xfs_btree_get_block(bs->cur, level, pbp);
543 	if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
544 		failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
545 				level, *pbp);
546 	else
547 		failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
548 				 level, *pbp);
549 	if (failed_at) {
550 		xchk_btree_set_corrupt(bs->sc, bs->cur, level);
551 		return 0;
552 	}
553 	if (*pbp)
554 		xchk_buffer_recheck(bs->sc, *pbp);
555 
556 	xchk_btree_check_minrecs(bs, level, *pblock);
557 
558 	/*
559 	 * Check the block's owner; this function absorbs error codes
560 	 * for us.
561 	 */
562 	error = xchk_btree_check_owner(bs, level, *pbp);
563 	if (error)
564 		return error;
565 
566 	/*
567 	 * Check the block's siblings; this function absorbs error codes
568 	 * for us.
569 	 */
570 	return xchk_btree_block_check_siblings(bs, *pblock);
571 }
572 
573 /*
574  * Check that the low and high keys of this block match the keys stored
575  * in the parent block.
576  */
577 STATIC void
xchk_btree_block_keys(struct xchk_btree * bs,int level,struct xfs_btree_block * block)578 xchk_btree_block_keys(
579 	struct xchk_btree	*bs,
580 	int			level,
581 	struct xfs_btree_block	*block)
582 {
583 	union xfs_btree_key	block_keys;
584 	struct xfs_btree_cur	*cur = bs->cur;
585 	union xfs_btree_key	*high_bk;
586 	union xfs_btree_key	*parent_keys;
587 	union xfs_btree_key	*high_pk;
588 	struct xfs_btree_block	*parent_block;
589 	struct xfs_buf		*bp;
590 
591 	if (level >= cur->bc_nlevels - 1)
592 		return;
593 
594 	/* Calculate the keys for this block. */
595 	xfs_btree_get_keys(cur, block, &block_keys);
596 
597 	/* Obtain the parent's copy of the keys for this block. */
598 	parent_block = xfs_btree_get_block(cur, level + 1, &bp);
599 	parent_keys = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1],
600 			parent_block);
601 
602 	if (cur->bc_ops->diff_two_keys(cur, &block_keys, parent_keys) != 0)
603 		xchk_btree_set_corrupt(bs->sc, cur, 1);
604 
605 	if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
606 		return;
607 
608 	/* Get high keys */
609 	high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
610 	high_pk = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1],
611 			parent_block);
612 
613 	if (cur->bc_ops->diff_two_keys(cur, high_bk, high_pk) != 0)
614 		xchk_btree_set_corrupt(bs->sc, cur, 1);
615 }
616 
617 /*
618  * Visit all nodes and leaves of a btree.  Check that all pointers and
619  * records are in order, that the keys reflect the records, and use a callback
620  * so that the caller can verify individual records.
621  */
622 int
xchk_btree(struct xfs_scrub * sc,struct xfs_btree_cur * cur,xchk_btree_rec_fn scrub_fn,const struct xfs_owner_info * oinfo,void * private)623 xchk_btree(
624 	struct xfs_scrub		*sc,
625 	struct xfs_btree_cur		*cur,
626 	xchk_btree_rec_fn		scrub_fn,
627 	const struct xfs_owner_info	*oinfo,
628 	void				*private)
629 {
630 	struct xchk_btree		bs = {
631 		.cur			= cur,
632 		.scrub_rec		= scrub_fn,
633 		.oinfo			= oinfo,
634 		.firstrec		= true,
635 		.private		= private,
636 		.sc			= sc,
637 	};
638 	union xfs_btree_ptr		ptr;
639 	union xfs_btree_ptr		*pp;
640 	union xfs_btree_rec		*recp;
641 	struct xfs_btree_block		*block;
642 	int				level;
643 	struct xfs_buf			*bp;
644 	struct check_owner		*co;
645 	struct check_owner		*n;
646 	int				i;
647 	int				error = 0;
648 
649 	/* Initialize scrub state */
650 	for (i = 0; i < XFS_BTREE_MAXLEVELS; i++)
651 		bs.firstkey[i] = true;
652 	INIT_LIST_HEAD(&bs.to_check);
653 
654 	/* Don't try to check a tree with a height we can't handle. */
655 	if (cur->bc_nlevels > XFS_BTREE_MAXLEVELS) {
656 		xchk_btree_set_corrupt(sc, cur, 0);
657 		goto out;
658 	}
659 
660 	/*
661 	 * Load the root of the btree.  The helper function absorbs
662 	 * error codes for us.
663 	 */
664 	level = cur->bc_nlevels - 1;
665 	cur->bc_ops->init_ptr_from_cur(cur, &ptr);
666 	if (!xchk_btree_ptr_ok(&bs, cur->bc_nlevels, &ptr))
667 		goto out;
668 	error = xchk_btree_get_block(&bs, level, &ptr, &block, &bp);
669 	if (error || !block)
670 		goto out;
671 
672 	cur->bc_ptrs[level] = 1;
673 
674 	while (level < cur->bc_nlevels) {
675 		block = xfs_btree_get_block(cur, level, &bp);
676 
677 		if (level == 0) {
678 			/* End of leaf, pop back towards the root. */
679 			if (cur->bc_ptrs[level] >
680 			    be16_to_cpu(block->bb_numrecs)) {
681 				xchk_btree_block_keys(&bs, level, block);
682 				if (level < cur->bc_nlevels - 1)
683 					cur->bc_ptrs[level + 1]++;
684 				level++;
685 				continue;
686 			}
687 
688 			/* Records in order for scrub? */
689 			xchk_btree_rec(&bs);
690 
691 			/* Call out to the record checker. */
692 			recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block);
693 			error = bs.scrub_rec(&bs, recp);
694 			if (error)
695 				break;
696 			if (xchk_should_terminate(sc, &error) ||
697 			    (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
698 				break;
699 
700 			cur->bc_ptrs[level]++;
701 			continue;
702 		}
703 
704 		/* End of node, pop back towards the root. */
705 		if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) {
706 			xchk_btree_block_keys(&bs, level, block);
707 			if (level < cur->bc_nlevels - 1)
708 				cur->bc_ptrs[level + 1]++;
709 			level++;
710 			continue;
711 		}
712 
713 		/* Keys in order for scrub? */
714 		xchk_btree_key(&bs, level);
715 
716 		/* Drill another level deeper. */
717 		pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block);
718 		if (!xchk_btree_ptr_ok(&bs, level, pp)) {
719 			cur->bc_ptrs[level]++;
720 			continue;
721 		}
722 		level--;
723 		error = xchk_btree_get_block(&bs, level, pp, &block, &bp);
724 		if (error || !block)
725 			goto out;
726 
727 		cur->bc_ptrs[level] = 1;
728 	}
729 
730 out:
731 	/* Process deferred owner checks on btree blocks. */
732 	list_for_each_entry_safe(co, n, &bs.to_check, list) {
733 		if (!error && bs.cur)
734 			error = xchk_btree_check_block_owner(&bs,
735 					co->level, co->daddr);
736 		list_del(&co->list);
737 		kmem_free(co);
738 	}
739 
740 	return error;
741 }
742