1739a2fe0SDarrick J. Wong // SPDX-License-Identifier: GPL-2.0-or-later 2537964bcSDarrick J. Wong /* 3ecc73f8aSDarrick J. Wong * Copyright (C) 2017-2023 Oracle. All Rights Reserved. 4739a2fe0SDarrick J. Wong * Author: Darrick J. Wong <djwong@kernel.org> 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: 3988accf17SDarrick J. Wong case -ECHRNG: 40537964bcSDarrick J. Wong /* Used to restart an op with deadlock avoidance. */ 41c517b3aaSDarrick J. Wong trace_xchk_deadlock_retry(sc->ip, sc->sm, *error); 42537964bcSDarrick J. Wong break; 43537964bcSDarrick J. Wong case -EFSBADCRC: 44537964bcSDarrick J. Wong case -EFSCORRUPTED: 45537964bcSDarrick J. Wong /* Note the badness but don't abort. */ 4664b12563SDarrick J. Wong sc->sm->sm_flags |= errflag; 47537964bcSDarrick J. Wong *error = 0; 4853004ee7SGustavo A. R. Silva fallthrough; 49537964bcSDarrick J. Wong default: 50537964bcSDarrick J. Wong if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) 51c517b3aaSDarrick J. Wong trace_xchk_ifork_btree_op_error(sc, cur, level, 5264b12563SDarrick J. Wong *error, ret_ip); 53537964bcSDarrick J. Wong else 54c517b3aaSDarrick J. Wong trace_xchk_btree_op_error(sc, cur, level, 5564b12563SDarrick J. Wong *error, ret_ip); 56537964bcSDarrick J. Wong break; 57537964bcSDarrick J. Wong } 58537964bcSDarrick J. Wong return false; 59537964bcSDarrick J. Wong } 60537964bcSDarrick J. Wong 6164b12563SDarrick J. Wong bool 62c517b3aaSDarrick J. Wong xchk_btree_process_error( 631d8a748aSDarrick J. Wong struct xfs_scrub *sc, 6464b12563SDarrick J. Wong struct xfs_btree_cur *cur, 6564b12563SDarrick J. Wong int level, 6664b12563SDarrick J. Wong int *error) 6764b12563SDarrick J. Wong { 68c517b3aaSDarrick J. Wong return __xchk_btree_process_error(sc, cur, level, error, 6964b12563SDarrick J. Wong XFS_SCRUB_OFLAG_CORRUPT, __return_address); 7064b12563SDarrick J. Wong } 7164b12563SDarrick J. Wong 7264b12563SDarrick J. Wong bool 73c517b3aaSDarrick J. Wong xchk_btree_xref_process_error( 741d8a748aSDarrick J. Wong struct xfs_scrub *sc, 7564b12563SDarrick J. Wong struct xfs_btree_cur *cur, 7664b12563SDarrick J. Wong int level, 7764b12563SDarrick J. Wong int *error) 7864b12563SDarrick J. Wong { 79c517b3aaSDarrick J. Wong return __xchk_btree_process_error(sc, cur, level, error, 8064b12563SDarrick J. Wong XFS_SCRUB_OFLAG_XFAIL, __return_address); 8164b12563SDarrick J. Wong } 8264b12563SDarrick J. Wong 83537964bcSDarrick J. Wong /* Record btree block corruption. */ 8464b12563SDarrick J. Wong static void 85c517b3aaSDarrick J. Wong __xchk_btree_set_corrupt( 861d8a748aSDarrick J. Wong struct xfs_scrub *sc, 8764b12563SDarrick J. Wong struct xfs_btree_cur *cur, 8864b12563SDarrick J. Wong int level, 8964b12563SDarrick J. Wong __u32 errflag, 9064b12563SDarrick J. Wong void *ret_ip) 9164b12563SDarrick J. Wong { 9264b12563SDarrick J. Wong sc->sm->sm_flags |= errflag; 9364b12563SDarrick J. Wong 9464b12563SDarrick J. Wong if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) 95c517b3aaSDarrick J. Wong trace_xchk_ifork_btree_error(sc, cur, level, 9664b12563SDarrick J. Wong ret_ip); 9764b12563SDarrick J. Wong else 98c517b3aaSDarrick J. Wong trace_xchk_btree_error(sc, cur, level, 9964b12563SDarrick J. Wong ret_ip); 10064b12563SDarrick J. Wong } 10164b12563SDarrick J. Wong 102537964bcSDarrick J. Wong void 103c517b3aaSDarrick J. Wong xchk_btree_set_corrupt( 1041d8a748aSDarrick J. Wong struct xfs_scrub *sc, 105537964bcSDarrick J. Wong struct xfs_btree_cur *cur, 106537964bcSDarrick J. Wong int level) 107537964bcSDarrick J. Wong { 108c517b3aaSDarrick J. Wong __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT, 109537964bcSDarrick J. Wong __return_address); 11064b12563SDarrick J. Wong } 11164b12563SDarrick J. Wong 11264b12563SDarrick J. Wong void 113c517b3aaSDarrick J. Wong xchk_btree_xref_set_corrupt( 1141d8a748aSDarrick J. Wong struct xfs_scrub *sc, 11564b12563SDarrick J. Wong struct xfs_btree_cur *cur, 11664b12563SDarrick J. Wong int level) 11764b12563SDarrick J. Wong { 118c517b3aaSDarrick J. Wong __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT, 119537964bcSDarrick J. Wong __return_address); 120537964bcSDarrick J. Wong } 121537964bcSDarrick J. Wong 12238384569SDarrick J. Wong void 12338384569SDarrick J. Wong xchk_btree_set_preen( 12438384569SDarrick J. Wong struct xfs_scrub *sc, 12538384569SDarrick J. Wong struct xfs_btree_cur *cur, 12638384569SDarrick J. Wong int level) 12738384569SDarrick J. Wong { 12838384569SDarrick J. Wong __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_PREEN, 12938384569SDarrick J. Wong __return_address); 13038384569SDarrick J. Wong } 13138384569SDarrick J. Wong 132537964bcSDarrick J. Wong /* 13337f3fa7fSDarrick J. Wong * Make sure this record is in order and doesn't stray outside of the parent 13437f3fa7fSDarrick J. Wong * keys. 13537f3fa7fSDarrick J. Wong */ 13637f3fa7fSDarrick J. Wong STATIC void 137c517b3aaSDarrick J. Wong xchk_btree_rec( 138c517b3aaSDarrick J. Wong struct xchk_btree *bs) 13937f3fa7fSDarrick J. Wong { 14037f3fa7fSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 14137f3fa7fSDarrick J. Wong union xfs_btree_rec *rec; 14237f3fa7fSDarrick J. Wong union xfs_btree_key key; 14337f3fa7fSDarrick J. Wong union xfs_btree_key hkey; 14437f3fa7fSDarrick J. Wong union xfs_btree_key *keyp; 14537f3fa7fSDarrick J. Wong struct xfs_btree_block *block; 14637f3fa7fSDarrick J. Wong struct xfs_btree_block *keyblock; 14737f3fa7fSDarrick J. Wong struct xfs_buf *bp; 14837f3fa7fSDarrick J. Wong 14937f3fa7fSDarrick J. Wong block = xfs_btree_get_block(cur, 0, &bp); 1506ca444cfSDarrick J. Wong rec = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, block); 15137f3fa7fSDarrick J. Wong 152c517b3aaSDarrick J. Wong trace_xchk_btree_rec(bs->sc, cur, 0); 15337f3fa7fSDarrick J. Wong 1542bea8df0SDarrick J. Wong /* Are all records across all record blocks in order? */ 1552bea8df0SDarrick J. Wong if (bs->lastrec_valid && 156d47fef93SDarrick J. Wong !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec)) 157c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, 0); 15837f3fa7fSDarrick J. Wong memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len); 1592bea8df0SDarrick J. Wong bs->lastrec_valid = true; 16037f3fa7fSDarrick J. Wong 16137f3fa7fSDarrick J. Wong if (cur->bc_nlevels == 1) 16237f3fa7fSDarrick J. Wong return; 16337f3fa7fSDarrick J. Wong 164bd7e7951SDarrick J. Wong /* Is low_key(rec) at least as large as the parent low key? */ 16537f3fa7fSDarrick J. Wong cur->bc_ops->init_key_from_rec(&key, rec); 16637f3fa7fSDarrick J. Wong keyblock = xfs_btree_get_block(cur, 1, &bp); 1676ca444cfSDarrick J. Wong keyp = xfs_btree_key_addr(cur, cur->bc_levels[1].ptr, keyblock); 168bd7e7951SDarrick J. Wong if (xfs_btree_keycmp_lt(cur, &key, keyp)) 169c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, 1); 17037f3fa7fSDarrick J. Wong 17137f3fa7fSDarrick J. Wong if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 17237f3fa7fSDarrick J. Wong return; 17337f3fa7fSDarrick J. Wong 174bd7e7951SDarrick J. Wong /* Is high_key(rec) no larger than the parent high key? */ 17537f3fa7fSDarrick J. Wong cur->bc_ops->init_high_key_from_rec(&hkey, rec); 1766ca444cfSDarrick J. Wong keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[1].ptr, keyblock); 177bd7e7951SDarrick J. Wong if (xfs_btree_keycmp_lt(cur, keyp, &hkey)) 178c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, 1); 17937f3fa7fSDarrick J. Wong } 18037f3fa7fSDarrick J. Wong 18137f3fa7fSDarrick J. Wong /* 18237f3fa7fSDarrick J. Wong * Make sure this key is in order and doesn't stray outside of the parent 18337f3fa7fSDarrick J. Wong * keys. 18437f3fa7fSDarrick J. Wong */ 18537f3fa7fSDarrick J. Wong STATIC void 186c517b3aaSDarrick J. Wong xchk_btree_key( 187c517b3aaSDarrick J. Wong struct xchk_btree *bs, 18837f3fa7fSDarrick J. Wong int level) 18937f3fa7fSDarrick J. Wong { 19037f3fa7fSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 19137f3fa7fSDarrick J. Wong union xfs_btree_key *key; 19237f3fa7fSDarrick J. Wong union xfs_btree_key *keyp; 19337f3fa7fSDarrick J. Wong struct xfs_btree_block *block; 19437f3fa7fSDarrick J. Wong struct xfs_btree_block *keyblock; 19537f3fa7fSDarrick J. Wong struct xfs_buf *bp; 19637f3fa7fSDarrick J. Wong 19737f3fa7fSDarrick J. Wong block = xfs_btree_get_block(cur, level, &bp); 1986ca444cfSDarrick J. Wong key = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block); 19937f3fa7fSDarrick J. Wong 200c517b3aaSDarrick J. Wong trace_xchk_btree_key(bs->sc, cur, level); 20137f3fa7fSDarrick J. Wong 2022bea8df0SDarrick J. Wong /* Are all low keys across all node blocks in order? */ 2032bea8df0SDarrick J. Wong if (bs->lastkey[level - 1].valid && 2042bea8df0SDarrick J. Wong !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level - 1].key, key)) 205c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, level); 2062bea8df0SDarrick J. Wong memcpy(&bs->lastkey[level - 1].key, key, cur->bc_ops->key_len); 2072bea8df0SDarrick J. Wong bs->lastkey[level - 1].valid = true; 20837f3fa7fSDarrick J. Wong 20937f3fa7fSDarrick J. Wong if (level + 1 >= cur->bc_nlevels) 21037f3fa7fSDarrick J. Wong return; 21137f3fa7fSDarrick J. Wong 212bd7e7951SDarrick J. Wong /* Is this block's low key at least as large as the parent low key? */ 21337f3fa7fSDarrick J. Wong keyblock = xfs_btree_get_block(cur, level + 1, &bp); 2146ca444cfSDarrick J. Wong keyp = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, keyblock); 215bd7e7951SDarrick J. Wong if (xfs_btree_keycmp_lt(cur, key, keyp)) 216c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, level); 21737f3fa7fSDarrick J. Wong 21837f3fa7fSDarrick J. Wong if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 21937f3fa7fSDarrick J. Wong return; 22037f3fa7fSDarrick J. Wong 221bd7e7951SDarrick J. Wong /* Is this block's high key no larger than the parent high key? */ 2226ca444cfSDarrick J. Wong key = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr, block); 2236ca444cfSDarrick J. Wong keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr, 2246ca444cfSDarrick J. Wong keyblock); 225bd7e7951SDarrick J. Wong if (xfs_btree_keycmp_lt(cur, keyp, key)) 226c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, level); 22737f3fa7fSDarrick J. Wong } 22837f3fa7fSDarrick J. Wong 22937f3fa7fSDarrick J. Wong /* 230cc3e0948SDarrick J. Wong * Check a btree pointer. Returns true if it's ok to use this pointer. 231cc3e0948SDarrick J. Wong * Callers do not need to set the corrupt flag. 232cc3e0948SDarrick J. Wong */ 233cc3e0948SDarrick J. Wong static bool 234c517b3aaSDarrick J. Wong xchk_btree_ptr_ok( 235c517b3aaSDarrick J. Wong struct xchk_btree *bs, 236cc3e0948SDarrick J. Wong int level, 237cc3e0948SDarrick J. Wong union xfs_btree_ptr *ptr) 238cc3e0948SDarrick J. Wong { 239cc3e0948SDarrick J. Wong bool res; 240cc3e0948SDarrick J. Wong 241cc3e0948SDarrick J. Wong /* A btree rooted in an inode has no block pointer to the root. */ 242cc3e0948SDarrick J. Wong if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 243cc3e0948SDarrick J. Wong level == bs->cur->bc_nlevels) 244cc3e0948SDarrick J. Wong return true; 245cc3e0948SDarrick J. Wong 246cc3e0948SDarrick J. Wong /* Otherwise, check the pointers. */ 247cc3e0948SDarrick J. Wong if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS) 248cc3e0948SDarrick J. Wong res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level); 249cc3e0948SDarrick J. Wong else 250cc3e0948SDarrick J. Wong res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level); 251cc3e0948SDarrick J. Wong if (!res) 252c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, bs->cur, level); 253cc3e0948SDarrick J. Wong 254cc3e0948SDarrick J. Wong return res; 255cc3e0948SDarrick J. Wong } 256cc3e0948SDarrick J. Wong 257cc3e0948SDarrick J. Wong /* Check that a btree block's sibling matches what we expect it. */ 258cc3e0948SDarrick J. Wong STATIC int 259c517b3aaSDarrick J. Wong xchk_btree_block_check_sibling( 260c517b3aaSDarrick J. Wong struct xchk_btree *bs, 261cc3e0948SDarrick J. Wong int level, 262cc3e0948SDarrick J. Wong int direction, 263cc3e0948SDarrick J. Wong union xfs_btree_ptr *sibling) 264cc3e0948SDarrick J. Wong { 265cc3e0948SDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 266cc3e0948SDarrick J. Wong struct xfs_btree_block *pblock; 267cc3e0948SDarrick J. Wong struct xfs_buf *pbp; 268cc3e0948SDarrick J. Wong struct xfs_btree_cur *ncur = NULL; 269cc3e0948SDarrick J. Wong union xfs_btree_ptr *pp; 270cc3e0948SDarrick J. Wong int success; 271cc3e0948SDarrick J. Wong int error; 272cc3e0948SDarrick J. Wong 273cc3e0948SDarrick J. Wong error = xfs_btree_dup_cursor(cur, &ncur); 274c517b3aaSDarrick J. Wong if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) || 275cc3e0948SDarrick J. Wong !ncur) 276cc3e0948SDarrick J. Wong return error; 277cc3e0948SDarrick J. Wong 278cc3e0948SDarrick J. Wong /* 279cc3e0948SDarrick J. Wong * If the pointer is null, we shouldn't be able to move the upper 280cc3e0948SDarrick J. Wong * level pointer anywhere. 281cc3e0948SDarrick J. Wong */ 282cc3e0948SDarrick J. Wong if (xfs_btree_ptr_is_null(cur, sibling)) { 283cc3e0948SDarrick J. Wong if (direction > 0) 284cc3e0948SDarrick J. Wong error = xfs_btree_increment(ncur, level + 1, &success); 285cc3e0948SDarrick J. Wong else 286cc3e0948SDarrick J. Wong error = xfs_btree_decrement(ncur, level + 1, &success); 287cc3e0948SDarrick J. Wong if (error == 0 && success) 288c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, level); 289cc3e0948SDarrick J. Wong error = 0; 290cc3e0948SDarrick J. Wong goto out; 291cc3e0948SDarrick J. Wong } 292cc3e0948SDarrick J. Wong 293cc3e0948SDarrick J. Wong /* Increment upper level pointer. */ 294cc3e0948SDarrick J. Wong if (direction > 0) 295cc3e0948SDarrick J. Wong error = xfs_btree_increment(ncur, level + 1, &success); 296cc3e0948SDarrick J. Wong else 297cc3e0948SDarrick J. Wong error = xfs_btree_decrement(ncur, level + 1, &success); 298c517b3aaSDarrick J. Wong if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error)) 299cc3e0948SDarrick J. Wong goto out; 300cc3e0948SDarrick J. Wong if (!success) { 301c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, level + 1); 302cc3e0948SDarrick J. Wong goto out; 303cc3e0948SDarrick J. Wong } 304cc3e0948SDarrick J. Wong 305cc3e0948SDarrick J. Wong /* Compare upper level pointer to sibling pointer. */ 306cc3e0948SDarrick J. Wong pblock = xfs_btree_get_block(ncur, level + 1, &pbp); 3076ca444cfSDarrick J. Wong pp = xfs_btree_ptr_addr(ncur, ncur->bc_levels[level + 1].ptr, pblock); 308c517b3aaSDarrick J. Wong if (!xchk_btree_ptr_ok(bs, level + 1, pp)) 309cc3e0948SDarrick J. Wong goto out; 310cf1b0b8bSDarrick J. Wong if (pbp) 311c517b3aaSDarrick J. Wong xchk_buffer_recheck(bs->sc, pbp); 312cc3e0948SDarrick J. Wong 313cc3e0948SDarrick J. Wong if (xfs_btree_diff_two_ptrs(cur, pp, sibling)) 314c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, level); 315cc3e0948SDarrick J. Wong out: 316cc3e0948SDarrick J. Wong xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR); 317cc3e0948SDarrick J. Wong return error; 318cc3e0948SDarrick J. Wong } 319cc3e0948SDarrick J. Wong 320cc3e0948SDarrick J. Wong /* Check the siblings of a btree block. */ 321cc3e0948SDarrick J. Wong STATIC int 322c517b3aaSDarrick J. Wong xchk_btree_block_check_siblings( 323c517b3aaSDarrick J. Wong struct xchk_btree *bs, 324cc3e0948SDarrick J. Wong struct xfs_btree_block *block) 325cc3e0948SDarrick J. Wong { 326cc3e0948SDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 327cc3e0948SDarrick J. Wong union xfs_btree_ptr leftsib; 328cc3e0948SDarrick J. Wong union xfs_btree_ptr rightsib; 329cc3e0948SDarrick J. Wong int level; 330cc3e0948SDarrick J. Wong int error = 0; 331cc3e0948SDarrick J. Wong 332cc3e0948SDarrick J. Wong xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB); 333cc3e0948SDarrick J. Wong xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB); 334cc3e0948SDarrick J. Wong level = xfs_btree_get_level(block); 335cc3e0948SDarrick J. Wong 336cc3e0948SDarrick J. Wong /* Root block should never have siblings. */ 337cc3e0948SDarrick J. Wong if (level == cur->bc_nlevels - 1) { 338cc3e0948SDarrick J. Wong if (!xfs_btree_ptr_is_null(cur, &leftsib) || 339cc3e0948SDarrick J. Wong !xfs_btree_ptr_is_null(cur, &rightsib)) 340c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, level); 341cc3e0948SDarrick J. Wong goto out; 342cc3e0948SDarrick J. Wong } 343cc3e0948SDarrick J. Wong 344cc3e0948SDarrick J. Wong /* 345cc3e0948SDarrick J. Wong * Does the left & right sibling pointers match the adjacent 346cc3e0948SDarrick J. Wong * parent level pointers? 347cc3e0948SDarrick J. Wong * (These function absorbs error codes for us.) 348cc3e0948SDarrick J. Wong */ 349c517b3aaSDarrick J. Wong error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib); 350cc3e0948SDarrick J. Wong if (error) 351cc3e0948SDarrick J. Wong return error; 352c517b3aaSDarrick J. Wong error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib); 353cc3e0948SDarrick J. Wong if (error) 354cc3e0948SDarrick J. Wong return error; 355cc3e0948SDarrick J. Wong out: 356cc3e0948SDarrick J. Wong return error; 357cc3e0948SDarrick J. Wong } 358cc3e0948SDarrick J. Wong 359858333dcSDarrick J. Wong struct check_owner { 360858333dcSDarrick J. Wong struct list_head list; 361858333dcSDarrick J. Wong xfs_daddr_t daddr; 362858333dcSDarrick J. Wong int level; 363858333dcSDarrick J. Wong }; 364858333dcSDarrick J. Wong 365858333dcSDarrick J. Wong /* 366858333dcSDarrick J. Wong * Make sure this btree block isn't in the free list and that there's 367858333dcSDarrick J. Wong * an rmap record for it. 368858333dcSDarrick J. Wong */ 369858333dcSDarrick J. Wong STATIC int 370c517b3aaSDarrick J. Wong xchk_btree_check_block_owner( 371c517b3aaSDarrick J. Wong struct xchk_btree *bs, 372858333dcSDarrick J. Wong int level, 373858333dcSDarrick J. Wong xfs_daddr_t daddr) 374858333dcSDarrick J. Wong { 375858333dcSDarrick J. Wong xfs_agnumber_t agno; 37652dc4b44SDarrick J. Wong xfs_agblock_t agbno; 37752dc4b44SDarrick J. Wong xfs_btnum_t btnum; 378858333dcSDarrick J. Wong bool init_sa; 379858333dcSDarrick J. Wong int error = 0; 380858333dcSDarrick J. Wong 381858333dcSDarrick J. Wong if (!bs->cur) 382858333dcSDarrick J. Wong return 0; 383858333dcSDarrick J. Wong 38452dc4b44SDarrick J. Wong btnum = bs->cur->bc_btnum; 385858333dcSDarrick J. Wong agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr); 38652dc4b44SDarrick J. Wong agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr); 387858333dcSDarrick J. Wong 388858333dcSDarrick J. Wong init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS; 389858333dcSDarrick J. Wong if (init_sa) { 39048c6615cSDarrick J. Wong error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa); 391c517b3aaSDarrick J. Wong if (!xchk_btree_xref_process_error(bs->sc, bs->cur, 392858333dcSDarrick J. Wong level, &error)) 39361e0d0ccSDarrick J. Wong goto out_free; 394858333dcSDarrick J. Wong } 395858333dcSDarrick J. Wong 396c517b3aaSDarrick J. Wong xchk_xref_is_used_space(bs->sc, agbno, 1); 39752dc4b44SDarrick J. Wong /* 39852dc4b44SDarrick J. Wong * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we 39952dc4b44SDarrick J. Wong * have to nullify it (to shut down further block owner checks) if 40052dc4b44SDarrick J. Wong * self-xref encounters problems. 40152dc4b44SDarrick J. Wong */ 40252dc4b44SDarrick J. Wong if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO) 40352dc4b44SDarrick J. Wong bs->cur = NULL; 40452dc4b44SDarrick J. Wong 405*69115f77SDarrick J. Wong xchk_xref_is_only_owned_by(bs->sc, agbno, 1, bs->oinfo); 406d852657cSDarrick J. Wong if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP) 407d852657cSDarrick J. Wong bs->cur = NULL; 408d852657cSDarrick J. Wong 40961e0d0ccSDarrick J. Wong out_free: 410858333dcSDarrick J. Wong if (init_sa) 411c517b3aaSDarrick J. Wong xchk_ag_free(bs->sc, &bs->sc->sa); 412858333dcSDarrick J. Wong 413858333dcSDarrick J. Wong return error; 414858333dcSDarrick J. Wong } 415858333dcSDarrick J. Wong 416858333dcSDarrick J. Wong /* Check the owner of a btree block. */ 417858333dcSDarrick J. Wong STATIC int 418c517b3aaSDarrick J. Wong xchk_btree_check_owner( 419c517b3aaSDarrick J. Wong struct xchk_btree *bs, 420858333dcSDarrick J. Wong int level, 421858333dcSDarrick J. Wong struct xfs_buf *bp) 422858333dcSDarrick J. Wong { 423858333dcSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 424858333dcSDarrick J. Wong 425a72e9d8dSDarrick J. Wong /* 426a72e9d8dSDarrick J. Wong * In theory, xfs_btree_get_block should only give us a null buffer 427a72e9d8dSDarrick J. Wong * pointer for the root of a root-in-inode btree type, but we need 428a72e9d8dSDarrick J. Wong * to check defensively here in case the cursor state is also screwed 429a72e9d8dSDarrick J. Wong * up. 430a72e9d8dSDarrick J. Wong */ 431a72e9d8dSDarrick J. Wong if (bp == NULL) { 432a72e9d8dSDarrick J. Wong if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)) 433a72e9d8dSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, bs->cur, level); 434858333dcSDarrick J. Wong return 0; 435a72e9d8dSDarrick J. Wong } 436858333dcSDarrick J. Wong 437858333dcSDarrick J. Wong /* 438858333dcSDarrick J. Wong * We want to cross-reference each btree block with the bnobt 439858333dcSDarrick J. Wong * and the rmapbt. We cannot cross-reference the bnobt or 440858333dcSDarrick J. Wong * rmapbt while scanning the bnobt or rmapbt, respectively, 441858333dcSDarrick J. Wong * because we cannot alter the cursor and we'd prefer not to 442858333dcSDarrick J. Wong * duplicate cursors. Therefore, save the buffer daddr for 443858333dcSDarrick J. Wong * later scanning. 444858333dcSDarrick J. Wong */ 445858333dcSDarrick J. Wong if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) { 446fcd2a434SDarrick J. Wong struct check_owner *co; 447fcd2a434SDarrick J. Wong 448306195f3SDarrick J. Wong co = kmalloc(sizeof(struct check_owner), XCHK_GFP_FLAGS); 449858333dcSDarrick J. Wong if (!co) 450858333dcSDarrick J. Wong return -ENOMEM; 451fcd2a434SDarrick J. Wong 452fcd2a434SDarrick J. Wong INIT_LIST_HEAD(&co->list); 453858333dcSDarrick J. Wong co->level = level; 45404fcad80SDave Chinner co->daddr = xfs_buf_daddr(bp); 455858333dcSDarrick J. Wong list_add_tail(&co->list, &bs->to_check); 456858333dcSDarrick J. Wong return 0; 457858333dcSDarrick J. Wong } 458858333dcSDarrick J. Wong 45904fcad80SDave Chinner return xchk_btree_check_block_owner(bs, level, xfs_buf_daddr(bp)); 460858333dcSDarrick J. Wong } 461858333dcSDarrick J. Wong 462ae7bae68SChandan Babu R /* Decide if we want to check minrecs of a btree block in the inode root. */ 463ae7bae68SChandan Babu R static inline bool 464ae7bae68SChandan Babu R xchk_btree_check_iroot_minrecs( 465ae7bae68SChandan Babu R struct xchk_btree *bs) 466ae7bae68SChandan Babu R { 467ae7bae68SChandan Babu R /* 468ae7bae68SChandan Babu R * xfs_bmap_add_attrfork_btree had an implementation bug wherein it 469ae7bae68SChandan Babu R * would miscalculate the space required for the data fork bmbt root 470ae7bae68SChandan Babu R * when adding an attr fork, and promote the iroot contents to an 471ae7bae68SChandan Babu R * external block unnecessarily. This went unnoticed for many years 472ae7bae68SChandan Babu R * until scrub found filesystems in this state. Inode rooted btrees are 473ae7bae68SChandan Babu R * not supposed to have immediate child blocks that are small enough 474ae7bae68SChandan Babu R * that the contents could fit in the inode root, but we can't fail 475ae7bae68SChandan Babu R * existing filesystems, so instead we disable the check for data fork 476ae7bae68SChandan Babu R * bmap btrees when there's an attr fork. 477ae7bae68SChandan Babu R */ 478ae7bae68SChandan Babu R if (bs->cur->bc_btnum == XFS_BTNUM_BMAP && 479ae7bae68SChandan Babu R bs->cur->bc_ino.whichfork == XFS_DATA_FORK && 480932b42c6SDarrick J. Wong xfs_inode_has_attr_fork(bs->sc->ip)) 481ae7bae68SChandan Babu R return false; 482ae7bae68SChandan Babu R 483ae7bae68SChandan Babu R return true; 484ae7bae68SChandan Babu R } 485ae7bae68SChandan Babu R 486cc3e0948SDarrick J. Wong /* 48708a3a692SDarrick J. Wong * Check that this btree block has at least minrecs records or is one of the 48808a3a692SDarrick J. Wong * special blocks that don't require that. 48908a3a692SDarrick J. Wong */ 49008a3a692SDarrick J. Wong STATIC void 491c517b3aaSDarrick J. Wong xchk_btree_check_minrecs( 492c517b3aaSDarrick J. Wong struct xchk_btree *bs, 49308a3a692SDarrick J. Wong int level, 49408a3a692SDarrick J. Wong struct xfs_btree_block *block) 49508a3a692SDarrick J. Wong { 496e95b6c3eSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 497e95b6c3eSDarrick J. Wong unsigned int root_level = cur->bc_nlevels - 1; 498e95b6c3eSDarrick J. Wong unsigned int numrecs = be16_to_cpu(block->bb_numrecs); 49908a3a692SDarrick J. Wong 50008a3a692SDarrick J. Wong /* More records than minrecs means the block is ok. */ 501e95b6c3eSDarrick J. Wong if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) 50208a3a692SDarrick J. Wong return; 50308a3a692SDarrick J. Wong 50408a3a692SDarrick J. Wong /* 505e95b6c3eSDarrick J. Wong * For btrees rooted in the inode, it's possible that the root block 506e95b6c3eSDarrick J. Wong * contents spilled into a regular ondisk block because there wasn't 507e95b6c3eSDarrick J. Wong * enough space in the inode root. The number of records in that 508e95b6c3eSDarrick J. Wong * child block might be less than the standard minrecs, but that's ok 509e95b6c3eSDarrick J. Wong * provided that there's only one direct child of the root. 51008a3a692SDarrick J. Wong */ 511e95b6c3eSDarrick J. Wong if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 512e95b6c3eSDarrick J. Wong level == cur->bc_nlevels - 2) { 513e95b6c3eSDarrick J. Wong struct xfs_btree_block *root_block; 514e95b6c3eSDarrick J. Wong struct xfs_buf *root_bp; 515e95b6c3eSDarrick J. Wong int root_maxrecs; 51608a3a692SDarrick J. Wong 517e95b6c3eSDarrick J. Wong root_block = xfs_btree_get_block(cur, root_level, &root_bp); 518e95b6c3eSDarrick J. Wong root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level); 519ae7bae68SChandan Babu R if (xchk_btree_check_iroot_minrecs(bs) && 520ae7bae68SChandan Babu R (be16_to_cpu(root_block->bb_numrecs) != 1 || 521ae7bae68SChandan Babu R numrecs <= root_maxrecs)) 522e95b6c3eSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, level); 523e95b6c3eSDarrick J. Wong return; 524e95b6c3eSDarrick J. Wong } 525e95b6c3eSDarrick J. Wong 526e95b6c3eSDarrick J. Wong /* 527e95b6c3eSDarrick J. Wong * Otherwise, only the root level is allowed to have fewer than minrecs 528e95b6c3eSDarrick J. Wong * records or keyptrs. 529e95b6c3eSDarrick J. Wong */ 530e95b6c3eSDarrick J. Wong if (level < root_level) 531e95b6c3eSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, level); 53208a3a692SDarrick J. Wong } 53308a3a692SDarrick J. Wong 53408a3a692SDarrick J. Wong /* 535c99f99faSDarrick J. Wong * If this btree block has a parent, make sure that the parent's keys capture 536c99f99faSDarrick J. Wong * the keyspace contained in this block. 537c99f99faSDarrick J. Wong */ 538c99f99faSDarrick J. Wong STATIC void 539c99f99faSDarrick J. Wong xchk_btree_block_check_keys( 540c99f99faSDarrick J. Wong struct xchk_btree *bs, 541c99f99faSDarrick J. Wong int level, 542c99f99faSDarrick J. Wong struct xfs_btree_block *block) 543c99f99faSDarrick J. Wong { 544c99f99faSDarrick J. Wong union xfs_btree_key block_key; 545c99f99faSDarrick J. Wong union xfs_btree_key *block_high_key; 546c99f99faSDarrick J. Wong union xfs_btree_key *parent_low_key, *parent_high_key; 547c99f99faSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 548c99f99faSDarrick J. Wong struct xfs_btree_block *parent_block; 549c99f99faSDarrick J. Wong struct xfs_buf *bp; 550c99f99faSDarrick J. Wong 551c99f99faSDarrick J. Wong if (level == cur->bc_nlevels - 1) 552c99f99faSDarrick J. Wong return; 553c99f99faSDarrick J. Wong 554c99f99faSDarrick J. Wong xfs_btree_get_keys(cur, block, &block_key); 555c99f99faSDarrick J. Wong 556c99f99faSDarrick J. Wong /* Make sure the low key of this block matches the parent. */ 557c99f99faSDarrick J. Wong parent_block = xfs_btree_get_block(cur, level + 1, &bp); 558c99f99faSDarrick J. Wong parent_low_key = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, 559c99f99faSDarrick J. Wong parent_block); 560bd7e7951SDarrick J. Wong if (xfs_btree_keycmp_ne(cur, &block_key, parent_low_key)) { 561c99f99faSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, bs->cur, level); 562c99f99faSDarrick J. Wong return; 563c99f99faSDarrick J. Wong } 564c99f99faSDarrick J. Wong 565c99f99faSDarrick J. Wong if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 566c99f99faSDarrick J. Wong return; 567c99f99faSDarrick J. Wong 568c99f99faSDarrick J. Wong /* Make sure the high key of this block matches the parent. */ 569c99f99faSDarrick J. Wong parent_high_key = xfs_btree_high_key_addr(cur, 570c99f99faSDarrick J. Wong cur->bc_levels[level + 1].ptr, parent_block); 571c99f99faSDarrick J. Wong block_high_key = xfs_btree_high_key_from_key(cur, &block_key); 572bd7e7951SDarrick J. Wong if (xfs_btree_keycmp_ne(cur, block_high_key, parent_high_key)) 573c99f99faSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, bs->cur, level); 574c99f99faSDarrick J. Wong } 575c99f99faSDarrick J. Wong 576c99f99faSDarrick J. Wong /* 577cc3e0948SDarrick J. Wong * Grab and scrub a btree block given a btree pointer. Returns block 578cc3e0948SDarrick J. Wong * and buffer pointers (if applicable) if they're ok to use. 579cc3e0948SDarrick J. Wong */ 580cc3e0948SDarrick J. Wong STATIC int 581c517b3aaSDarrick J. Wong xchk_btree_get_block( 582c517b3aaSDarrick J. Wong struct xchk_btree *bs, 583cc3e0948SDarrick J. Wong int level, 584cc3e0948SDarrick J. Wong union xfs_btree_ptr *pp, 585cc3e0948SDarrick J. Wong struct xfs_btree_block **pblock, 586cc3e0948SDarrick J. Wong struct xfs_buf **pbp) 587cc3e0948SDarrick J. Wong { 588032d91f9SDarrick J. Wong xfs_failaddr_t failed_at; 589cc3e0948SDarrick J. Wong int error; 590cc3e0948SDarrick J. Wong 591cc3e0948SDarrick J. Wong *pblock = NULL; 592cc3e0948SDarrick J. Wong *pbp = NULL; 593cc3e0948SDarrick J. Wong 594cc3e0948SDarrick J. Wong error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock); 595c517b3aaSDarrick J. Wong if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) || 596a605e869SDarrick J. Wong !*pblock) 597cc3e0948SDarrick J. Wong return error; 598cc3e0948SDarrick J. Wong 599cc3e0948SDarrick J. Wong xfs_btree_get_block(bs->cur, level, pbp); 600cc3e0948SDarrick J. Wong if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS) 601cc3e0948SDarrick J. Wong failed_at = __xfs_btree_check_lblock(bs->cur, *pblock, 602cc3e0948SDarrick J. Wong level, *pbp); 603cc3e0948SDarrick J. Wong else 604cc3e0948SDarrick J. Wong failed_at = __xfs_btree_check_sblock(bs->cur, *pblock, 605cc3e0948SDarrick J. Wong level, *pbp); 606cc3e0948SDarrick J. Wong if (failed_at) { 607c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, bs->cur, level); 608cc3e0948SDarrick J. Wong return 0; 609cc3e0948SDarrick J. Wong } 610cf1b0b8bSDarrick J. Wong if (*pbp) 611c517b3aaSDarrick J. Wong xchk_buffer_recheck(bs->sc, *pbp); 612cc3e0948SDarrick J. Wong 613c517b3aaSDarrick J. Wong xchk_btree_check_minrecs(bs, level, *pblock); 61408a3a692SDarrick J. Wong 615cc3e0948SDarrick J. Wong /* 616858333dcSDarrick J. Wong * Check the block's owner; this function absorbs error codes 617858333dcSDarrick J. Wong * for us. 618858333dcSDarrick J. Wong */ 619c517b3aaSDarrick J. Wong error = xchk_btree_check_owner(bs, level, *pbp); 620858333dcSDarrick J. Wong if (error) 621858333dcSDarrick J. Wong return error; 622858333dcSDarrick J. Wong 623858333dcSDarrick J. Wong /* 624cc3e0948SDarrick J. Wong * Check the block's siblings; this function absorbs error codes 625cc3e0948SDarrick J. Wong * for us. 626cc3e0948SDarrick J. Wong */ 627c99f99faSDarrick J. Wong error = xchk_btree_block_check_siblings(bs, *pblock); 628c99f99faSDarrick J. Wong if (error) 629c99f99faSDarrick J. Wong return error; 630c99f99faSDarrick J. Wong 631c99f99faSDarrick J. Wong xchk_btree_block_check_keys(bs, level, *pblock); 632c99f99faSDarrick J. Wong return 0; 633cc3e0948SDarrick J. Wong } 634cc3e0948SDarrick J. Wong 635cc3e0948SDarrick J. Wong /* 6362fdbec5cSDarrick J. Wong * Check that the low and high keys of this block match the keys stored 6372fdbec5cSDarrick J. Wong * in the parent block. 6382fdbec5cSDarrick J. Wong */ 6392fdbec5cSDarrick J. Wong STATIC void 640c517b3aaSDarrick J. Wong xchk_btree_block_keys( 641c517b3aaSDarrick J. Wong struct xchk_btree *bs, 6422fdbec5cSDarrick J. Wong int level, 6432fdbec5cSDarrick J. Wong struct xfs_btree_block *block) 6442fdbec5cSDarrick J. Wong { 6452fdbec5cSDarrick J. Wong union xfs_btree_key block_keys; 6462fdbec5cSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 6472fdbec5cSDarrick J. Wong union xfs_btree_key *high_bk; 6482fdbec5cSDarrick J. Wong union xfs_btree_key *parent_keys; 6492fdbec5cSDarrick J. Wong union xfs_btree_key *high_pk; 6502fdbec5cSDarrick J. Wong struct xfs_btree_block *parent_block; 6512fdbec5cSDarrick J. Wong struct xfs_buf *bp; 6522fdbec5cSDarrick J. Wong 6532fdbec5cSDarrick J. Wong if (level >= cur->bc_nlevels - 1) 6542fdbec5cSDarrick J. Wong return; 6552fdbec5cSDarrick J. Wong 6562fdbec5cSDarrick J. Wong /* Calculate the keys for this block. */ 6572fdbec5cSDarrick J. Wong xfs_btree_get_keys(cur, block, &block_keys); 6582fdbec5cSDarrick J. Wong 6592fdbec5cSDarrick J. Wong /* Obtain the parent's copy of the keys for this block. */ 6602fdbec5cSDarrick J. Wong parent_block = xfs_btree_get_block(cur, level + 1, &bp); 6616ca444cfSDarrick J. Wong parent_keys = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, 6622fdbec5cSDarrick J. Wong parent_block); 6632fdbec5cSDarrick J. Wong 664bd7e7951SDarrick J. Wong if (xfs_btree_keycmp_ne(cur, &block_keys, parent_keys)) 665c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, 1); 6662fdbec5cSDarrick J. Wong 6672fdbec5cSDarrick J. Wong if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 6682fdbec5cSDarrick J. Wong return; 6692fdbec5cSDarrick J. Wong 6702fdbec5cSDarrick J. Wong /* Get high keys */ 6712fdbec5cSDarrick J. Wong high_bk = xfs_btree_high_key_from_key(cur, &block_keys); 6726ca444cfSDarrick J. Wong high_pk = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr, 6732fdbec5cSDarrick J. Wong parent_block); 6742fdbec5cSDarrick J. Wong 675bd7e7951SDarrick J. Wong if (xfs_btree_keycmp_ne(cur, high_bk, high_pk)) 676c517b3aaSDarrick J. Wong xchk_btree_set_corrupt(bs->sc, cur, 1); 6772fdbec5cSDarrick J. Wong } 6782fdbec5cSDarrick J. Wong 6792fdbec5cSDarrick J. Wong /* 680537964bcSDarrick J. Wong * Visit all nodes and leaves of a btree. Check that all pointers and 681537964bcSDarrick J. Wong * records are in order, that the keys reflect the records, and use a callback 682cc3e0948SDarrick J. Wong * so that the caller can verify individual records. 683537964bcSDarrick J. Wong */ 684537964bcSDarrick J. Wong int 685c517b3aaSDarrick J. Wong xchk_btree( 6861d8a748aSDarrick J. Wong struct xfs_scrub *sc, 687537964bcSDarrick J. Wong struct xfs_btree_cur *cur, 688c517b3aaSDarrick J. Wong xchk_btree_rec_fn scrub_fn, 68966e3237eSDarrick J. Wong const struct xfs_owner_info *oinfo, 690537964bcSDarrick J. Wong void *private) 691537964bcSDarrick J. Wong { 692cc3e0948SDarrick J. Wong union xfs_btree_ptr ptr; 693510a28e1SDarrick J. Wong struct xchk_btree *bs; 694cc3e0948SDarrick J. Wong union xfs_btree_ptr *pp; 69537f3fa7fSDarrick J. Wong union xfs_btree_rec *recp; 696cc3e0948SDarrick J. Wong struct xfs_btree_block *block; 697cc3e0948SDarrick J. Wong struct xfs_buf *bp; 698858333dcSDarrick J. Wong struct check_owner *co; 699858333dcSDarrick J. Wong struct check_owner *n; 700eae5db47SDarrick J. Wong size_t cur_sz; 701eae5db47SDarrick J. Wong int level; 702cc3e0948SDarrick J. Wong int error = 0; 703537964bcSDarrick J. Wong 704510a28e1SDarrick J. Wong /* 705510a28e1SDarrick J. Wong * Allocate the btree scrub context from the heap, because this 706eae5db47SDarrick J. Wong * structure can get rather large. Don't let a caller feed us a 707eae5db47SDarrick J. Wong * totally absurd size. 708510a28e1SDarrick J. Wong */ 709eae5db47SDarrick J. Wong cur_sz = xchk_btree_sizeof(cur->bc_nlevels); 710eae5db47SDarrick J. Wong if (cur_sz > PAGE_SIZE) { 711eae5db47SDarrick J. Wong xchk_btree_set_corrupt(sc, cur, 0); 712eae5db47SDarrick J. Wong return 0; 713eae5db47SDarrick J. Wong } 714306195f3SDarrick J. Wong bs = kzalloc(cur_sz, XCHK_GFP_FLAGS); 715510a28e1SDarrick J. Wong if (!bs) 716510a28e1SDarrick J. Wong return -ENOMEM; 717510a28e1SDarrick J. Wong bs->cur = cur; 718510a28e1SDarrick J. Wong bs->scrub_rec = scrub_fn; 719510a28e1SDarrick J. Wong bs->oinfo = oinfo; 720510a28e1SDarrick J. Wong bs->private = private; 721510a28e1SDarrick J. Wong bs->sc = sc; 722510a28e1SDarrick J. Wong 723cc3e0948SDarrick J. Wong /* Initialize scrub state */ 724510a28e1SDarrick J. Wong INIT_LIST_HEAD(&bs->to_check); 725cc3e0948SDarrick J. Wong 726cc3e0948SDarrick J. Wong /* 727cc3e0948SDarrick J. Wong * Load the root of the btree. The helper function absorbs 728cc3e0948SDarrick J. Wong * error codes for us. 729cc3e0948SDarrick J. Wong */ 730cc3e0948SDarrick J. Wong level = cur->bc_nlevels - 1; 731cc3e0948SDarrick J. Wong cur->bc_ops->init_ptr_from_cur(cur, &ptr); 732510a28e1SDarrick J. Wong if (!xchk_btree_ptr_ok(bs, cur->bc_nlevels, &ptr)) 733cc3e0948SDarrick J. Wong goto out; 734510a28e1SDarrick J. Wong error = xchk_btree_get_block(bs, level, &ptr, &block, &bp); 735cc3e0948SDarrick J. Wong if (error || !block) 736cc3e0948SDarrick J. Wong goto out; 737cc3e0948SDarrick J. Wong 7386ca444cfSDarrick J. Wong cur->bc_levels[level].ptr = 1; 739cc3e0948SDarrick J. Wong 740cc3e0948SDarrick J. Wong while (level < cur->bc_nlevels) { 741cc3e0948SDarrick J. Wong block = xfs_btree_get_block(cur, level, &bp); 742cc3e0948SDarrick J. Wong 743cc3e0948SDarrick J. Wong if (level == 0) { 744cc3e0948SDarrick J. Wong /* End of leaf, pop back towards the root. */ 7456ca444cfSDarrick J. Wong if (cur->bc_levels[level].ptr > 746cc3e0948SDarrick J. Wong be16_to_cpu(block->bb_numrecs)) { 747510a28e1SDarrick J. Wong xchk_btree_block_keys(bs, level, block); 748cc3e0948SDarrick J. Wong if (level < cur->bc_nlevels - 1) 7496ca444cfSDarrick J. Wong cur->bc_levels[level + 1].ptr++; 750cc3e0948SDarrick J. Wong level++; 751cc3e0948SDarrick J. Wong continue; 752cc3e0948SDarrick J. Wong } 753cc3e0948SDarrick J. Wong 75437f3fa7fSDarrick J. Wong /* Records in order for scrub? */ 755510a28e1SDarrick J. Wong xchk_btree_rec(bs); 75637f3fa7fSDarrick J. Wong 75737f3fa7fSDarrick J. Wong /* Call out to the record checker. */ 7586ca444cfSDarrick J. Wong recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, 7596ca444cfSDarrick J. Wong block); 760510a28e1SDarrick J. Wong error = bs->scrub_rec(bs, recp); 76137f3fa7fSDarrick J. Wong if (error) 76237f3fa7fSDarrick J. Wong break; 763c517b3aaSDarrick J. Wong if (xchk_should_terminate(sc, &error) || 76437f3fa7fSDarrick J. Wong (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT)) 765cc3e0948SDarrick J. Wong break; 766cc3e0948SDarrick J. Wong 7676ca444cfSDarrick J. Wong cur->bc_levels[level].ptr++; 768cc3e0948SDarrick J. Wong continue; 769cc3e0948SDarrick J. Wong } 770cc3e0948SDarrick J. Wong 771cc3e0948SDarrick J. Wong /* End of node, pop back towards the root. */ 7726ca444cfSDarrick J. Wong if (cur->bc_levels[level].ptr > 7736ca444cfSDarrick J. Wong be16_to_cpu(block->bb_numrecs)) { 774510a28e1SDarrick J. Wong xchk_btree_block_keys(bs, level, block); 775cc3e0948SDarrick J. Wong if (level < cur->bc_nlevels - 1) 7766ca444cfSDarrick J. Wong cur->bc_levels[level + 1].ptr++; 777cc3e0948SDarrick J. Wong level++; 778cc3e0948SDarrick J. Wong continue; 779cc3e0948SDarrick J. Wong } 780cc3e0948SDarrick J. Wong 78137f3fa7fSDarrick J. Wong /* Keys in order for scrub? */ 782510a28e1SDarrick J. Wong xchk_btree_key(bs, level); 78337f3fa7fSDarrick J. Wong 784cc3e0948SDarrick J. Wong /* Drill another level deeper. */ 7856ca444cfSDarrick J. Wong pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block); 786510a28e1SDarrick J. Wong if (!xchk_btree_ptr_ok(bs, level, pp)) { 7876ca444cfSDarrick J. Wong cur->bc_levels[level].ptr++; 788cc3e0948SDarrick J. Wong continue; 789cc3e0948SDarrick J. Wong } 790cc3e0948SDarrick J. Wong level--; 791510a28e1SDarrick J. Wong error = xchk_btree_get_block(bs, level, pp, &block, &bp); 792cc3e0948SDarrick J. Wong if (error || !block) 793cc3e0948SDarrick J. Wong goto out; 794cc3e0948SDarrick J. Wong 7956ca444cfSDarrick J. Wong cur->bc_levels[level].ptr = 1; 796cc3e0948SDarrick J. Wong } 797cc3e0948SDarrick J. Wong 798cc3e0948SDarrick J. Wong out: 799858333dcSDarrick J. Wong /* Process deferred owner checks on btree blocks. */ 800510a28e1SDarrick J. Wong list_for_each_entry_safe(co, n, &bs->to_check, list) { 801510a28e1SDarrick J. Wong if (!error && bs->cur) 802510a28e1SDarrick J. Wong error = xchk_btree_check_block_owner(bs, co->level, 803510a28e1SDarrick J. Wong co->daddr); 804858333dcSDarrick J. Wong list_del(&co->list); 805306195f3SDarrick J. Wong kfree(co); 806858333dcSDarrick J. Wong } 807306195f3SDarrick J. Wong kfree(bs); 808858333dcSDarrick J. Wong 809537964bcSDarrick J. Wong return error; 810537964bcSDarrick J. Wong } 811