1 // SPDX-License-Identifier: GPL-2.0-or-later
3  * Copyright (C) 2017-2023 Oracle.  All Rights Reserved.
29 	int			level,  in __xchk_btree_process_error()  argument
38 	case -EDEADLOCK:  in __xchk_btree_process_error()
39 	case -ECHRNG:  in __xchk_btree_process_error()
41 		trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);  in __xchk_btree_process_error()
43 	case -EFSBADCRC:  in __xchk_btree_process_error()
44 	case -EFSCORRUPTED:  in __xchk_btree_process_error()
46 		sc->sm->sm_flags |= errflag;  in __xchk_btree_process_error()
50 		if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE)  in __xchk_btree_process_error()
51 			trace_xchk_ifork_btree_op_error(sc, cur, level,  in __xchk_btree_process_error()
54 			trace_xchk_btree_op_error(sc, cur, level,  in __xchk_btree_process_error()
65 	int			level,  in xchk_btree_process_error()  argument
68 	return __xchk_btree_process_error(sc, cur, level, error,  in xchk_btree_process_error()
76 	int			level,  in xchk_btree_xref_process_error()  argument
79 	return __xchk_btree_process_error(sc, cur, level, error,  in xchk_btree_xref_process_error()
88 	int			level,  in __xchk_btree_set_corrupt()  argument
92 	sc->sm->sm_flags |= errflag;  in __xchk_btree_set_corrupt()
94 	if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE)  in __xchk_btree_set_corrupt()
95 		trace_xchk_ifork_btree_error(sc, cur, level,  in __xchk_btree_set_corrupt()
98 		trace_xchk_btree_error(sc, cur, level,  in __xchk_btree_set_corrupt()
106 	int			level)  in xchk_btree_set_corrupt()  argument
108 	__xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT,  in xchk_btree_set_corrupt()
116 	int			level)  in xchk_btree_xref_set_corrupt()  argument
118 	__xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT,  in xchk_btree_xref_set_corrupt()
126 	int			level)  in xchk_btree_set_preen()  argument
128 	__xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_PREEN,  in xchk_btree_set_preen()
140 	struct xfs_btree_cur	*cur = bs->cur;  in xchk_btree_rec()
150 	rec = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, block);  in xchk_btree_rec()
152 	trace_xchk_btree_rec(bs->sc, cur, 0);  in xchk_btree_rec()
155 	if (bs->lastrec_valid &&  in xchk_btree_rec()
156 	    !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))  in xchk_btree_rec()
157 		xchk_btree_set_corrupt(bs->sc, cur, 0);  in xchk_btree_rec()
158 	memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);  in xchk_btree_rec()
159 	bs->lastrec_valid = true;  in xchk_btree_rec()
161 	if (cur->bc_nlevels == 1)  in xchk_btree_rec()
165 	cur->bc_ops->init_key_from_rec(&key, rec);  in xchk_btree_rec()
167 	keyp = xfs_btree_key_addr(cur, cur->bc_levels[1].ptr, keyblock);  in xchk_btree_rec()
169 		xchk_btree_set_corrupt(bs->sc, cur, 1);  in xchk_btree_rec()
171 	if (!(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING))  in xchk_btree_rec()
174 	/* Is high_key(rec) no larger than the parent high key? */  in xchk_btree_rec()
175 	cur->bc_ops->init_high_key_from_rec(&hkey, rec);  in xchk_btree_rec()
176 	keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[1].ptr, keyblock);  in xchk_btree_rec()
178 		xchk_btree_set_corrupt(bs->sc, cur, 1);  in xchk_btree_rec()
188 	int			level)  in xchk_btree_key()  argument
190 	struct xfs_btree_cur	*cur = bs->cur;  in xchk_btree_key()
197 	block = xfs_btree_get_block(cur, level, &bp);  in xchk_btree_key()
198 	key = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block);  in xchk_btree_key()
200 	trace_xchk_btree_key(bs->sc, cur, level);  in xchk_btree_key()
203 	if (bs->lastkey[level - 1].valid &&  in xchk_btree_key()
204 	    !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level - 1].key, key))  in xchk_btree_key()
205 		xchk_btree_set_corrupt(bs->sc, cur, level);  in xchk_btree_key()
206 	memcpy(&bs->lastkey[level - 1].key, key, cur->bc_ops->key_len);  in xchk_btree_key()
207 	bs->lastkey[level - 1].valid = true;  in xchk_btree_key()
209 	if (level + 1 >= cur->bc_nlevels)  in xchk_btree_key()
213 	keyblock = xfs_btree_get_block(cur, level + 1, &bp);  in xchk_btree_key()
214 	keyp = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, keyblock);  in xchk_btree_key()
216 		xchk_btree_set_corrupt(bs->sc, cur, level);  in xchk_btree_key()
218 	if (!(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING))  in xchk_btree_key()
221 	/* Is this block's high key no larger than the parent high key? */  in xchk_btree_key()
222 	key = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr, block);  in xchk_btree_key()
223 	keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,  in xchk_btree_key()
226 		xchk_btree_set_corrupt(bs->sc, cur, level);  in xchk_btree_key()
236 	int			level,  in xchk_btree_ptr_ok()  argument
240 	if (bs->cur->bc_ops->type == XFS_BTREE_TYPE_INODE &&  in xchk_btree_ptr_ok()
241 	    level == bs->cur->bc_nlevels)  in xchk_btree_ptr_ok()
245 	if (__xfs_btree_check_ptr(bs->cur, ptr, 0, level)) {  in xchk_btree_ptr_ok()
246 		xchk_btree_set_corrupt(bs->sc, bs->cur, level);  in xchk_btree_ptr_ok()
257 	int			level,  in xchk_btree_block_check_sibling()  argument
261 	struct xfs_btree_cur	*cur = bs->cur;  in xchk_btree_block_check_sibling()
270 	if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||  in xchk_btree_block_check_sibling()
276 	 * level pointer anywhere.  in xchk_btree_block_check_sibling()
280 			error = xfs_btree_increment(ncur, level + 1, &success);  in xchk_btree_block_check_sibling()
282 			error = xfs_btree_decrement(ncur, level + 1, &success);  in xchk_btree_block_check_sibling()
284 			xchk_btree_set_corrupt(bs->sc, cur, level);  in xchk_btree_block_check_sibling()
289 	/* Increment upper level pointer. */  in xchk_btree_block_check_sibling()
291 		error = xfs_btree_increment(ncur, level + 1, &success);  in xchk_btree_block_check_sibling()
293 		error = xfs_btree_decrement(ncur, level + 1, &success);  in xchk_btree_block_check_sibling()
294 	if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))  in xchk_btree_block_check_sibling()
297 		xchk_btree_set_corrupt(bs->sc, cur, level + 1);  in xchk_btree_block_check_sibling()
301 	/* Compare upper level pointer to sibling pointer. */  in xchk_btree_block_check_sibling()
302 	pblock = xfs_btree_get_block(ncur, level + 1, &pbp);  in xchk_btree_block_check_sibling()
303 	pp = xfs_btree_ptr_addr(ncur, ncur->bc_levels[level + 1].ptr, pblock);  in xchk_btree_block_check_sibling()
304 	if (!xchk_btree_ptr_ok(bs, level + 1, pp))  in xchk_btree_block_check_sibling()
307 		xchk_buffer_recheck(bs->sc, pbp);  in xchk_btree_block_check_sibling()
310 		xchk_btree_set_corrupt(bs->sc, cur, level);  in xchk_btree_block_check_sibling()
322 	struct xfs_btree_cur	*cur = bs->cur;  in xchk_btree_block_check_siblings()
325 	int			level;  in xchk_btree_block_check_siblings()  local
330 	level = xfs_btree_get_level(block);  in xchk_btree_block_check_siblings()
333 	if (level == cur->bc_nlevels - 1) {  in xchk_btree_block_check_siblings()
336 			xchk_btree_set_corrupt(bs->sc, cur, level);  in xchk_btree_block_check_siblings()
342 	 * parent level pointers?  in xchk_btree_block_check_siblings()
345 	error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);  in xchk_btree_block_check_siblings()
348 	error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);  in xchk_btree_block_check_siblings()
358 	int			level;  member
368 	int			level,  in xchk_btree_check_block_owner()  argument
376 	if (!bs->cur)  in xchk_btree_check_block_owner()
379 	agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);  in xchk_btree_check_block_owner()
380 	agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);  in xchk_btree_check_block_owner()
383 	 * If the btree being examined is not itself a per-AG btree, initialize  in xchk_btree_check_block_owner()
384 	 * sc->sa so that we can check for the presence of an ownership record  in xchk_btree_check_block_owner()
387 	init_sa = bs->cur->bc_ops->type != XFS_BTREE_TYPE_AG;  in xchk_btree_check_block_owner()
389 		error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa);  in xchk_btree_check_block_owner()
390 		if (!xchk_btree_xref_process_error(bs->sc, bs->cur,  in xchk_btree_check_block_owner()
391 				level, &error))  in xchk_btree_check_block_owner()
395 	xchk_xref_is_used_space(bs->sc, agbno, 1);  in xchk_btree_check_block_owner()
397 	 * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we  in xchk_btree_check_block_owner()
399 	 * self-xref encounters problems.  in xchk_btree_check_block_owner()
401 	if (!bs->sc->sa.bno_cur && xfs_btree_is_bno(bs->cur->bc_ops))  in xchk_btree_check_block_owner()
402 		bs->cur = NULL;  in xchk_btree_check_block_owner()
404 	xchk_xref_is_only_owned_by(bs->sc, agbno, 1, bs->oinfo);  in xchk_btree_check_block_owner()
405 	if (!bs->sc->sa.rmap_cur && xfs_btree_is_rmap(bs->cur->bc_ops))  in xchk_btree_check_block_owner()
406 		bs->cur = NULL;  in xchk_btree_check_block_owner()
410 		xchk_ag_free(bs->sc, &bs->sc->sa);  in xchk_btree_check_block_owner()
419 	int			level,  in xchk_btree_check_owner()  argument
422 	struct xfs_btree_cur	*cur = bs->cur;  in xchk_btree_check_owner()
426 	 * pointer for the root of a root-in-inode btree type, but we need  in xchk_btree_check_owner()
431 		if (cur->bc_ops->type != XFS_BTREE_TYPE_INODE)  in xchk_btree_check_owner()
432 			xchk_btree_set_corrupt(bs->sc, bs->cur, level);  in xchk_btree_check_owner()
437 	 * We want to cross-reference each btree block with the bnobt  in xchk_btree_check_owner()
438 	 * and the rmapbt.  We cannot cross-reference the bnobt or  in xchk_btree_check_owner()
444 	if (xfs_btree_is_bno(cur->bc_ops) || xfs_btree_is_rmap(cur->bc_ops)) {  in xchk_btree_check_owner()
449 			return -ENOMEM;  in xchk_btree_check_owner()
451 		INIT_LIST_HEAD(&co->list);  in xchk_btree_check_owner()
452 		co->level = level;  in xchk_btree_check_owner()
453 		co->daddr = xfs_buf_daddr(bp);  in xchk_btree_check_owner()
454 		list_add_tail(&co->list, &bs->to_check);  in xchk_btree_check_owner()
458 	return xchk_btree_check_block_owner(bs, level, xfs_buf_daddr(bp));  in xchk_btree_check_owner()
477 	if (xfs_btree_is_bmap(bs->cur->bc_ops) &&  in xchk_btree_check_iroot_minrecs()
478 	    bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&  in xchk_btree_check_iroot_minrecs()
479 	    xfs_inode_has_attr_fork(bs->sc->ip))  in xchk_btree_check_iroot_minrecs()
492 	int			level,  in xchk_btree_check_minrecs()  argument
495 	struct xfs_btree_cur	*cur = bs->cur;  in xchk_btree_check_minrecs()
496 	unsigned int		root_level = cur->bc_nlevels - 1;  in xchk_btree_check_minrecs()
497 	unsigned int		numrecs = be16_to_cpu(block->bb_numrecs);  in xchk_btree_check_minrecs()
500 	if (numrecs >= cur->bc_ops->get_minrecs(cur, level))  in xchk_btree_check_minrecs()
510 	if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE &&  in xchk_btree_check_minrecs()
511 	    level == cur->bc_nlevels - 2) {  in xchk_btree_check_minrecs()
517 		root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);  in xchk_btree_check_minrecs()
519 		    (be16_to_cpu(root_block->bb_numrecs) != 1 ||  in xchk_btree_check_minrecs()
521 			xchk_btree_set_corrupt(bs->sc, cur, level);  in xchk_btree_check_minrecs()
526 	 * Otherwise, only the root level is allowed to have fewer than minrecs  in xchk_btree_check_minrecs()
529 	if (level < root_level)  in xchk_btree_check_minrecs()
530 		xchk_btree_set_corrupt(bs->sc, cur, level);  in xchk_btree_check_minrecs()
540 	int			level,  in xchk_btree_block_check_keys()  argument
546 	struct xfs_btree_cur	*cur = bs->cur;  in xchk_btree_block_check_keys()
550 	if (level == cur->bc_nlevels - 1)  in xchk_btree_block_check_keys()
556 	parent_block = xfs_btree_get_block(cur, level + 1, &bp);  in xchk_btree_block_check_keys()
557 	parent_low_key = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,  in xchk_btree_block_check_keys()
560 		xchk_btree_set_corrupt(bs->sc, bs->cur, level);  in xchk_btree_block_check_keys()
564 	if (!(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING))  in xchk_btree_block_check_keys()
567 	/* Make sure the high key of this block matches the parent. */  in xchk_btree_block_check_keys()
569 			cur->bc_levels[level + 1].ptr, parent_block);  in xchk_btree_block_check_keys()
572 		xchk_btree_set_corrupt(bs->sc, bs->cur, level);  in xchk_btree_block_check_keys()
582 	int			level,  in xchk_btree_get_block()  argument
592 	error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);  in xchk_btree_get_block()
593 	if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||  in xchk_btree_get_block()
597 	xfs_btree_get_block(bs->cur, level, pbp);  in xchk_btree_get_block()
598 	if (__xfs_btree_check_block(bs->cur, *pblock, level, *pbp)) {  in xchk_btree_get_block()
599 		xchk_btree_set_corrupt(bs->sc, bs->cur, level);  in xchk_btree_get_block()
603 		xchk_buffer_recheck(bs->sc, *pbp);  in xchk_btree_get_block()
605 	xchk_btree_check_minrecs(bs, level, *pblock);  in xchk_btree_get_block()
611 	error = xchk_btree_check_owner(bs, level, *pbp);  in xchk_btree_get_block()
623 	xchk_btree_block_check_keys(bs, level, *pblock);  in xchk_btree_get_block()
628  * Check that the low and high keys of this block match the keys stored
634 	int			level,  in xchk_btree_block_keys()  argument
638 	struct xfs_btree_cur	*cur = bs->cur;  in xchk_btree_block_keys()
645 	if (level >= cur->bc_nlevels - 1)  in xchk_btree_block_keys()
652 	parent_block = xfs_btree_get_block(cur, level + 1, &bp);  in xchk_btree_block_keys()
653 	parent_keys = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,  in xchk_btree_block_keys()
657 		xchk_btree_set_corrupt(bs->sc, cur, 1);  in xchk_btree_block_keys()
659 	if (!(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING))  in xchk_btree_block_keys()
662 	/* Get high keys */  in xchk_btree_block_keys()
664 	high_pk = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,  in xchk_btree_block_keys()
668 		xchk_btree_set_corrupt(bs->sc, cur, 1);  in xchk_btree_block_keys()
693 	int				level;  in xchk_btree()  local
701 	cur_sz = xchk_btree_sizeof(cur->bc_nlevels);  in xchk_btree()
708 		return -ENOMEM;  in xchk_btree()
709 	bs->cur = cur;  in xchk_btree()
710 	bs->scrub_rec = scrub_fn;  in xchk_btree()
711 	bs->oinfo = oinfo;  in xchk_btree()
712 	bs->private = private;  in xchk_btree()
713 	bs->sc = sc;  in xchk_btree()
716 	INIT_LIST_HEAD(&bs->to_check);  in xchk_btree()
722 	level = cur->bc_nlevels - 1;  in xchk_btree()
724 	if (!xchk_btree_ptr_ok(bs, cur->bc_nlevels, &ptr))  in xchk_btree()
726 	error = xchk_btree_get_block(bs, level, &ptr, &block, &bp);  in xchk_btree()
730 	cur->bc_levels[level].ptr = 1;  in xchk_btree()
732 	while (level < cur->bc_nlevels) {  in xchk_btree()
733 		block = xfs_btree_get_block(cur, level, &bp);  in xchk_btree()
735 		if (level == 0) {  in xchk_btree()
737 			if (cur->bc_levels[level].ptr >  in xchk_btree()
738 			    be16_to_cpu(block->bb_numrecs)) {  in xchk_btree()
739 				xchk_btree_block_keys(bs, level, block);  in xchk_btree()
740 				if (level < cur->bc_nlevels - 1)  in xchk_btree()
741 					cur->bc_levels[level + 1].ptr++;  in xchk_btree()
742 				level++;  in xchk_btree()
750 			recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr,  in xchk_btree()
752 			error = bs->scrub_rec(bs, recp);  in xchk_btree()
756 			    (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))  in xchk_btree()
759 			cur->bc_levels[level].ptr++;  in xchk_btree()
764 		if (cur->bc_levels[level].ptr >  in xchk_btree()
765 					be16_to_cpu(block->bb_numrecs)) {  in xchk_btree()
766 			xchk_btree_block_keys(bs, level, block);  in xchk_btree()
767 			if (level < cur->bc_nlevels - 1)  in xchk_btree()
768 				cur->bc_levels[level + 1].ptr++;  in xchk_btree()
769 			level++;  in xchk_btree()
774 		xchk_btree_key(bs, level);  in xchk_btree()
776 		/* Drill another level deeper. */  in xchk_btree()
777 		pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block);  in xchk_btree()
778 		if (!xchk_btree_ptr_ok(bs, level, pp)) {  in xchk_btree()
779 			cur->bc_levels[level].ptr++;  in xchk_btree()
782 		level--;  in xchk_btree()
783 		error = xchk_btree_get_block(bs, level, pp, &block, &bp);  in xchk_btree()
787 		cur->bc_levels[level].ptr = 1;  in xchk_btree()
792 	list_for_each_entry_safe(co, n, &bs->to_check, list) {  in xchk_btree()
793 		if (!error && bs->cur)  in xchk_btree()
794 			error = xchk_btree_check_block_owner(bs, co->level,  in xchk_btree()
795 					co->daddr);  in xchk_btree()
796 		list_del(&co->list);  in xchk_btree()