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