1537964bcSDarrick J. Wong /* 2537964bcSDarrick J. Wong * Copyright (C) 2017 Oracle. All Rights Reserved. 3537964bcSDarrick J. Wong * 4537964bcSDarrick J. Wong * Author: Darrick J. Wong <darrick.wong@oracle.com> 5537964bcSDarrick J. Wong * 6537964bcSDarrick J. Wong * This program is free software; you can redistribute it and/or 7537964bcSDarrick J. Wong * modify it under the terms of the GNU General Public License 8537964bcSDarrick J. Wong * as published by the Free Software Foundation; either version 2 9537964bcSDarrick J. Wong * of the License, or (at your option) any later version. 10537964bcSDarrick J. Wong * 11537964bcSDarrick J. Wong * This program is distributed in the hope that it would be useful, 12537964bcSDarrick J. Wong * but WITHOUT ANY WARRANTY; without even the implied warranty of 13537964bcSDarrick J. Wong * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14537964bcSDarrick J. Wong * GNU General Public License for more details. 15537964bcSDarrick J. Wong * 16537964bcSDarrick J. Wong * You should have received a copy of the GNU General Public License 17537964bcSDarrick J. Wong * along with this program; if not, write the Free Software Foundation, 18537964bcSDarrick J. Wong * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. 19537964bcSDarrick J. Wong */ 20537964bcSDarrick J. Wong #include "xfs.h" 21537964bcSDarrick J. Wong #include "xfs_fs.h" 22537964bcSDarrick J. Wong #include "xfs_shared.h" 23537964bcSDarrick J. Wong #include "xfs_format.h" 24537964bcSDarrick J. Wong #include "xfs_trans_resv.h" 25537964bcSDarrick J. Wong #include "xfs_mount.h" 26537964bcSDarrick J. Wong #include "xfs_defer.h" 27537964bcSDarrick J. Wong #include "xfs_btree.h" 28537964bcSDarrick J. Wong #include "xfs_bit.h" 29537964bcSDarrick J. Wong #include "xfs_log_format.h" 30537964bcSDarrick J. Wong #include "xfs_trans.h" 31537964bcSDarrick J. Wong #include "xfs_sb.h" 32537964bcSDarrick J. Wong #include "xfs_inode.h" 33537964bcSDarrick J. Wong #include "xfs_alloc.h" 34537964bcSDarrick J. Wong #include "scrub/scrub.h" 35537964bcSDarrick J. Wong #include "scrub/common.h" 36537964bcSDarrick J. Wong #include "scrub/btree.h" 37537964bcSDarrick J. Wong #include "scrub/trace.h" 38537964bcSDarrick J. Wong 39537964bcSDarrick J. Wong /* btree scrubbing */ 40537964bcSDarrick J. Wong 41537964bcSDarrick J. Wong /* 42537964bcSDarrick J. Wong * Check for btree operation errors. See the section about handling 43537964bcSDarrick J. Wong * operational errors in common.c. 44537964bcSDarrick J. Wong */ 4564b12563SDarrick J. Wong static bool 4664b12563SDarrick J. Wong __xfs_scrub_btree_process_error( 47537964bcSDarrick J. Wong struct xfs_scrub_context *sc, 48537964bcSDarrick J. Wong struct xfs_btree_cur *cur, 49537964bcSDarrick J. Wong int level, 5064b12563SDarrick J. Wong int *error, 5164b12563SDarrick J. Wong __u32 errflag, 5264b12563SDarrick J. Wong void *ret_ip) 53537964bcSDarrick J. Wong { 54537964bcSDarrick J. Wong if (*error == 0) 55537964bcSDarrick J. Wong return true; 56537964bcSDarrick J. Wong 57537964bcSDarrick J. Wong switch (*error) { 58537964bcSDarrick J. Wong case -EDEADLOCK: 59537964bcSDarrick J. Wong /* Used to restart an op with deadlock avoidance. */ 60537964bcSDarrick J. Wong trace_xfs_scrub_deadlock_retry(sc->ip, sc->sm, *error); 61537964bcSDarrick J. Wong break; 62537964bcSDarrick J. Wong case -EFSBADCRC: 63537964bcSDarrick J. Wong case -EFSCORRUPTED: 64537964bcSDarrick J. Wong /* Note the badness but don't abort. */ 6564b12563SDarrick J. Wong sc->sm->sm_flags |= errflag; 66537964bcSDarrick J. Wong *error = 0; 67537964bcSDarrick J. Wong /* fall through */ 68537964bcSDarrick J. Wong default: 69537964bcSDarrick J. Wong if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) 70537964bcSDarrick J. Wong trace_xfs_scrub_ifork_btree_op_error(sc, cur, level, 7164b12563SDarrick J. Wong *error, ret_ip); 72537964bcSDarrick J. Wong else 73537964bcSDarrick J. Wong trace_xfs_scrub_btree_op_error(sc, cur, level, 7464b12563SDarrick J. Wong *error, ret_ip); 75537964bcSDarrick J. Wong break; 76537964bcSDarrick J. Wong } 77537964bcSDarrick J. Wong return false; 78537964bcSDarrick J. Wong } 79537964bcSDarrick J. Wong 8064b12563SDarrick J. Wong bool 8164b12563SDarrick J. Wong xfs_scrub_btree_process_error( 8264b12563SDarrick J. Wong struct xfs_scrub_context *sc, 8364b12563SDarrick J. Wong struct xfs_btree_cur *cur, 8464b12563SDarrick J. Wong int level, 8564b12563SDarrick J. Wong int *error) 8664b12563SDarrick J. Wong { 8764b12563SDarrick J. Wong return __xfs_scrub_btree_process_error(sc, cur, level, error, 8864b12563SDarrick J. Wong XFS_SCRUB_OFLAG_CORRUPT, __return_address); 8964b12563SDarrick J. Wong } 9064b12563SDarrick J. Wong 9164b12563SDarrick J. Wong bool 9264b12563SDarrick J. Wong xfs_scrub_btree_xref_process_error( 9364b12563SDarrick J. Wong struct xfs_scrub_context *sc, 9464b12563SDarrick J. Wong struct xfs_btree_cur *cur, 9564b12563SDarrick J. Wong int level, 9664b12563SDarrick J. Wong int *error) 9764b12563SDarrick J. Wong { 9864b12563SDarrick J. Wong return __xfs_scrub_btree_process_error(sc, cur, level, error, 9964b12563SDarrick J. Wong XFS_SCRUB_OFLAG_XFAIL, __return_address); 10064b12563SDarrick J. Wong } 10164b12563SDarrick J. Wong 102537964bcSDarrick J. Wong /* Record btree block corruption. */ 10364b12563SDarrick J. Wong static void 10464b12563SDarrick J. Wong __xfs_scrub_btree_set_corrupt( 10564b12563SDarrick J. Wong struct xfs_scrub_context *sc, 10664b12563SDarrick J. Wong struct xfs_btree_cur *cur, 10764b12563SDarrick J. Wong int level, 10864b12563SDarrick J. Wong __u32 errflag, 10964b12563SDarrick J. Wong void *ret_ip) 11064b12563SDarrick J. Wong { 11164b12563SDarrick J. Wong sc->sm->sm_flags |= errflag; 11264b12563SDarrick J. Wong 11364b12563SDarrick J. Wong if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) 11464b12563SDarrick J. Wong trace_xfs_scrub_ifork_btree_error(sc, cur, level, 11564b12563SDarrick J. Wong ret_ip); 11664b12563SDarrick J. Wong else 11764b12563SDarrick J. Wong trace_xfs_scrub_btree_error(sc, cur, level, 11864b12563SDarrick J. Wong ret_ip); 11964b12563SDarrick J. Wong } 12064b12563SDarrick J. Wong 121537964bcSDarrick J. Wong void 122537964bcSDarrick J. Wong xfs_scrub_btree_set_corrupt( 123537964bcSDarrick J. Wong struct xfs_scrub_context *sc, 124537964bcSDarrick J. Wong struct xfs_btree_cur *cur, 125537964bcSDarrick J. Wong int level) 126537964bcSDarrick J. Wong { 12764b12563SDarrick J. Wong __xfs_scrub_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT, 128537964bcSDarrick J. Wong __return_address); 12964b12563SDarrick J. Wong } 13064b12563SDarrick J. Wong 13164b12563SDarrick J. Wong void 13264b12563SDarrick J. Wong xfs_scrub_btree_xref_set_corrupt( 13364b12563SDarrick J. Wong struct xfs_scrub_context *sc, 13464b12563SDarrick J. Wong struct xfs_btree_cur *cur, 13564b12563SDarrick J. Wong int level) 13664b12563SDarrick J. Wong { 13764b12563SDarrick J. Wong __xfs_scrub_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT, 138537964bcSDarrick J. Wong __return_address); 139537964bcSDarrick J. Wong } 140537964bcSDarrick J. Wong 141537964bcSDarrick J. Wong /* 14237f3fa7fSDarrick J. Wong * Make sure this record is in order and doesn't stray outside of the parent 14337f3fa7fSDarrick J. Wong * keys. 14437f3fa7fSDarrick J. Wong */ 14537f3fa7fSDarrick J. Wong STATIC void 14637f3fa7fSDarrick J. Wong xfs_scrub_btree_rec( 14737f3fa7fSDarrick J. Wong struct xfs_scrub_btree *bs) 14837f3fa7fSDarrick J. Wong { 14937f3fa7fSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 15037f3fa7fSDarrick J. Wong union xfs_btree_rec *rec; 15137f3fa7fSDarrick J. Wong union xfs_btree_key key; 15237f3fa7fSDarrick J. Wong union xfs_btree_key hkey; 15337f3fa7fSDarrick J. Wong union xfs_btree_key *keyp; 15437f3fa7fSDarrick J. Wong struct xfs_btree_block *block; 15537f3fa7fSDarrick J. Wong struct xfs_btree_block *keyblock; 15637f3fa7fSDarrick J. Wong struct xfs_buf *bp; 15737f3fa7fSDarrick J. Wong 15837f3fa7fSDarrick J. Wong block = xfs_btree_get_block(cur, 0, &bp); 15937f3fa7fSDarrick J. Wong rec = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); 16037f3fa7fSDarrick J. Wong 16137f3fa7fSDarrick J. Wong trace_xfs_scrub_btree_rec(bs->sc, cur, 0); 16237f3fa7fSDarrick J. Wong 16337f3fa7fSDarrick J. Wong /* If this isn't the first record, are they in order? */ 16437f3fa7fSDarrick J. Wong if (!bs->firstrec && !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec)) 16537f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, 0); 16637f3fa7fSDarrick J. Wong bs->firstrec = false; 16737f3fa7fSDarrick J. Wong memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len); 16837f3fa7fSDarrick J. Wong 16937f3fa7fSDarrick J. Wong if (cur->bc_nlevels == 1) 17037f3fa7fSDarrick J. Wong return; 17137f3fa7fSDarrick J. Wong 17237f3fa7fSDarrick J. Wong /* Is this at least as large as the parent low key? */ 17337f3fa7fSDarrick J. Wong cur->bc_ops->init_key_from_rec(&key, rec); 17437f3fa7fSDarrick J. Wong keyblock = xfs_btree_get_block(cur, 1, &bp); 17537f3fa7fSDarrick J. Wong keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[1], keyblock); 17637f3fa7fSDarrick J. Wong if (cur->bc_ops->diff_two_keys(cur, &key, keyp) < 0) 17737f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, 1); 17837f3fa7fSDarrick J. Wong 17937f3fa7fSDarrick J. Wong if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 18037f3fa7fSDarrick J. Wong return; 18137f3fa7fSDarrick J. Wong 18237f3fa7fSDarrick J. Wong /* Is this no larger than the parent high key? */ 18337f3fa7fSDarrick J. Wong cur->bc_ops->init_high_key_from_rec(&hkey, rec); 18437f3fa7fSDarrick J. Wong keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[1], keyblock); 18537f3fa7fSDarrick J. Wong if (cur->bc_ops->diff_two_keys(cur, keyp, &hkey) < 0) 18637f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, 1); 18737f3fa7fSDarrick J. Wong } 18837f3fa7fSDarrick J. Wong 18937f3fa7fSDarrick J. Wong /* 19037f3fa7fSDarrick J. Wong * Make sure this key is in order and doesn't stray outside of the parent 19137f3fa7fSDarrick J. Wong * keys. 19237f3fa7fSDarrick J. Wong */ 19337f3fa7fSDarrick J. Wong STATIC void 19437f3fa7fSDarrick J. Wong xfs_scrub_btree_key( 19537f3fa7fSDarrick J. Wong struct xfs_scrub_btree *bs, 19637f3fa7fSDarrick J. Wong int level) 19737f3fa7fSDarrick J. Wong { 19837f3fa7fSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 19937f3fa7fSDarrick J. Wong union xfs_btree_key *key; 20037f3fa7fSDarrick J. Wong union xfs_btree_key *keyp; 20137f3fa7fSDarrick J. Wong struct xfs_btree_block *block; 20237f3fa7fSDarrick J. Wong struct xfs_btree_block *keyblock; 20337f3fa7fSDarrick J. Wong struct xfs_buf *bp; 20437f3fa7fSDarrick J. Wong 20537f3fa7fSDarrick J. Wong block = xfs_btree_get_block(cur, level, &bp); 20637f3fa7fSDarrick J. Wong key = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); 20737f3fa7fSDarrick J. Wong 20837f3fa7fSDarrick J. Wong trace_xfs_scrub_btree_key(bs->sc, cur, level); 20937f3fa7fSDarrick J. Wong 21037f3fa7fSDarrick J. Wong /* If this isn't the first key, are they in order? */ 21137f3fa7fSDarrick J. Wong if (!bs->firstkey[level] && 21237f3fa7fSDarrick J. Wong !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level], key)) 21337f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 21437f3fa7fSDarrick J. Wong bs->firstkey[level] = false; 21537f3fa7fSDarrick J. Wong memcpy(&bs->lastkey[level], key, cur->bc_ops->key_len); 21637f3fa7fSDarrick J. Wong 21737f3fa7fSDarrick J. Wong if (level + 1 >= cur->bc_nlevels) 21837f3fa7fSDarrick J. Wong return; 21937f3fa7fSDarrick J. Wong 22037f3fa7fSDarrick J. Wong /* Is this at least as large as the parent low key? */ 22137f3fa7fSDarrick J. Wong keyblock = xfs_btree_get_block(cur, level + 1, &bp); 22237f3fa7fSDarrick J. Wong keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1], keyblock); 22337f3fa7fSDarrick J. Wong if (cur->bc_ops->diff_two_keys(cur, key, keyp) < 0) 22437f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 22537f3fa7fSDarrick J. Wong 22637f3fa7fSDarrick J. Wong if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 22737f3fa7fSDarrick J. Wong return; 22837f3fa7fSDarrick J. Wong 22937f3fa7fSDarrick J. Wong /* Is this no larger than the parent high key? */ 23037f3fa7fSDarrick J. Wong key = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); 23137f3fa7fSDarrick J. Wong keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1], keyblock); 23237f3fa7fSDarrick J. Wong if (cur->bc_ops->diff_two_keys(cur, keyp, key) < 0) 23337f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 23437f3fa7fSDarrick J. Wong } 23537f3fa7fSDarrick J. Wong 23637f3fa7fSDarrick J. Wong /* 237cc3e0948SDarrick J. Wong * Check a btree pointer. Returns true if it's ok to use this pointer. 238cc3e0948SDarrick J. Wong * Callers do not need to set the corrupt flag. 239cc3e0948SDarrick J. Wong */ 240cc3e0948SDarrick J. Wong static bool 241cc3e0948SDarrick J. Wong xfs_scrub_btree_ptr_ok( 242cc3e0948SDarrick J. Wong struct xfs_scrub_btree *bs, 243cc3e0948SDarrick J. Wong int level, 244cc3e0948SDarrick J. Wong union xfs_btree_ptr *ptr) 245cc3e0948SDarrick J. Wong { 246cc3e0948SDarrick J. Wong bool res; 247cc3e0948SDarrick J. Wong 248cc3e0948SDarrick J. Wong /* A btree rooted in an inode has no block pointer to the root. */ 249cc3e0948SDarrick J. Wong if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 250cc3e0948SDarrick J. Wong level == bs->cur->bc_nlevels) 251cc3e0948SDarrick J. Wong return true; 252cc3e0948SDarrick J. Wong 253cc3e0948SDarrick J. Wong /* Otherwise, check the pointers. */ 254cc3e0948SDarrick J. Wong if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS) 255cc3e0948SDarrick J. Wong res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level); 256cc3e0948SDarrick J. Wong else 257cc3e0948SDarrick J. Wong res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level); 258cc3e0948SDarrick J. Wong if (!res) 259cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, bs->cur, level); 260cc3e0948SDarrick J. Wong 261cc3e0948SDarrick J. Wong return res; 262cc3e0948SDarrick J. Wong } 263cc3e0948SDarrick J. Wong 264cc3e0948SDarrick J. Wong /* Check that a btree block's sibling matches what we expect it. */ 265cc3e0948SDarrick J. Wong STATIC int 266cc3e0948SDarrick J. Wong xfs_scrub_btree_block_check_sibling( 267cc3e0948SDarrick J. Wong struct xfs_scrub_btree *bs, 268cc3e0948SDarrick J. Wong int level, 269cc3e0948SDarrick J. Wong int direction, 270cc3e0948SDarrick J. Wong union xfs_btree_ptr *sibling) 271cc3e0948SDarrick J. Wong { 272cc3e0948SDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 273cc3e0948SDarrick J. Wong struct xfs_btree_block *pblock; 274cc3e0948SDarrick J. Wong struct xfs_buf *pbp; 275cc3e0948SDarrick J. Wong struct xfs_btree_cur *ncur = NULL; 276cc3e0948SDarrick J. Wong union xfs_btree_ptr *pp; 277cc3e0948SDarrick J. Wong int success; 278cc3e0948SDarrick J. Wong int error; 279cc3e0948SDarrick J. Wong 280cc3e0948SDarrick J. Wong error = xfs_btree_dup_cursor(cur, &ncur); 281cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_process_error(bs->sc, cur, level + 1, &error) || 282cc3e0948SDarrick J. Wong !ncur) 283cc3e0948SDarrick J. Wong return error; 284cc3e0948SDarrick J. Wong 285cc3e0948SDarrick J. Wong /* 286cc3e0948SDarrick J. Wong * If the pointer is null, we shouldn't be able to move the upper 287cc3e0948SDarrick J. Wong * level pointer anywhere. 288cc3e0948SDarrick J. Wong */ 289cc3e0948SDarrick J. Wong if (xfs_btree_ptr_is_null(cur, sibling)) { 290cc3e0948SDarrick J. Wong if (direction > 0) 291cc3e0948SDarrick J. Wong error = xfs_btree_increment(ncur, level + 1, &success); 292cc3e0948SDarrick J. Wong else 293cc3e0948SDarrick J. Wong error = xfs_btree_decrement(ncur, level + 1, &success); 294cc3e0948SDarrick J. Wong if (error == 0 && success) 295cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 296cc3e0948SDarrick J. Wong error = 0; 297cc3e0948SDarrick J. Wong goto out; 298cc3e0948SDarrick J. Wong } 299cc3e0948SDarrick J. Wong 300cc3e0948SDarrick J. Wong /* Increment upper level pointer. */ 301cc3e0948SDarrick J. Wong if (direction > 0) 302cc3e0948SDarrick J. Wong error = xfs_btree_increment(ncur, level + 1, &success); 303cc3e0948SDarrick J. Wong else 304cc3e0948SDarrick J. Wong error = xfs_btree_decrement(ncur, level + 1, &success); 305cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_process_error(bs->sc, cur, level + 1, &error)) 306cc3e0948SDarrick J. Wong goto out; 307cc3e0948SDarrick J. Wong if (!success) { 308cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level + 1); 309cc3e0948SDarrick J. Wong goto out; 310cc3e0948SDarrick J. Wong } 311cc3e0948SDarrick J. Wong 312cc3e0948SDarrick J. Wong /* Compare upper level pointer to sibling pointer. */ 313cc3e0948SDarrick J. Wong pblock = xfs_btree_get_block(ncur, level + 1, &pbp); 314cc3e0948SDarrick J. Wong pp = xfs_btree_ptr_addr(ncur, ncur->bc_ptrs[level + 1], pblock); 315cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_ptr_ok(bs, level + 1, pp)) 316cc3e0948SDarrick J. Wong goto out; 317cf1b0b8bSDarrick J. Wong if (pbp) 318cf1b0b8bSDarrick J. Wong xfs_scrub_buffer_recheck(bs->sc, pbp); 319cc3e0948SDarrick J. Wong 320cc3e0948SDarrick J. Wong if (xfs_btree_diff_two_ptrs(cur, pp, sibling)) 321cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 322cc3e0948SDarrick J. Wong out: 323cc3e0948SDarrick J. Wong xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR); 324cc3e0948SDarrick J. Wong return error; 325cc3e0948SDarrick J. Wong } 326cc3e0948SDarrick J. Wong 327cc3e0948SDarrick J. Wong /* Check the siblings of a btree block. */ 328cc3e0948SDarrick J. Wong STATIC int 329cc3e0948SDarrick J. Wong xfs_scrub_btree_block_check_siblings( 330cc3e0948SDarrick J. Wong struct xfs_scrub_btree *bs, 331cc3e0948SDarrick J. Wong struct xfs_btree_block *block) 332cc3e0948SDarrick J. Wong { 333cc3e0948SDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 334cc3e0948SDarrick J. Wong union xfs_btree_ptr leftsib; 335cc3e0948SDarrick J. Wong union xfs_btree_ptr rightsib; 336cc3e0948SDarrick J. Wong int level; 337cc3e0948SDarrick J. Wong int error = 0; 338cc3e0948SDarrick J. Wong 339cc3e0948SDarrick J. Wong xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB); 340cc3e0948SDarrick J. Wong xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB); 341cc3e0948SDarrick J. Wong level = xfs_btree_get_level(block); 342cc3e0948SDarrick J. Wong 343cc3e0948SDarrick J. Wong /* Root block should never have siblings. */ 344cc3e0948SDarrick J. Wong if (level == cur->bc_nlevels - 1) { 345cc3e0948SDarrick J. Wong if (!xfs_btree_ptr_is_null(cur, &leftsib) || 346cc3e0948SDarrick J. Wong !xfs_btree_ptr_is_null(cur, &rightsib)) 347cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 348cc3e0948SDarrick J. Wong goto out; 349cc3e0948SDarrick J. Wong } 350cc3e0948SDarrick J. Wong 351cc3e0948SDarrick J. Wong /* 352cc3e0948SDarrick J. Wong * Does the left & right sibling pointers match the adjacent 353cc3e0948SDarrick J. Wong * parent level pointers? 354cc3e0948SDarrick J. Wong * (These function absorbs error codes for us.) 355cc3e0948SDarrick J. Wong */ 356cc3e0948SDarrick J. Wong error = xfs_scrub_btree_block_check_sibling(bs, level, -1, &leftsib); 357cc3e0948SDarrick J. Wong if (error) 358cc3e0948SDarrick J. Wong return error; 359cc3e0948SDarrick J. Wong error = xfs_scrub_btree_block_check_sibling(bs, level, 1, &rightsib); 360cc3e0948SDarrick J. Wong if (error) 361cc3e0948SDarrick J. Wong return error; 362cc3e0948SDarrick J. Wong out: 363cc3e0948SDarrick J. Wong return error; 364cc3e0948SDarrick J. Wong } 365cc3e0948SDarrick J. Wong 366858333dcSDarrick J. Wong struct check_owner { 367858333dcSDarrick J. Wong struct list_head list; 368858333dcSDarrick J. Wong xfs_daddr_t daddr; 369858333dcSDarrick J. Wong int level; 370858333dcSDarrick J. Wong }; 371858333dcSDarrick J. Wong 372858333dcSDarrick J. Wong /* 373858333dcSDarrick J. Wong * Make sure this btree block isn't in the free list and that there's 374858333dcSDarrick J. Wong * an rmap record for it. 375858333dcSDarrick J. Wong */ 376858333dcSDarrick J. Wong STATIC int 377858333dcSDarrick J. Wong xfs_scrub_btree_check_block_owner( 378858333dcSDarrick J. Wong struct xfs_scrub_btree *bs, 379858333dcSDarrick J. Wong int level, 380858333dcSDarrick J. Wong xfs_daddr_t daddr) 381858333dcSDarrick J. Wong { 382858333dcSDarrick J. Wong xfs_agnumber_t agno; 38352dc4b44SDarrick J. Wong xfs_agblock_t agbno; 38452dc4b44SDarrick J. Wong xfs_btnum_t btnum; 385858333dcSDarrick J. Wong bool init_sa; 386858333dcSDarrick J. Wong int error = 0; 387858333dcSDarrick J. Wong 388858333dcSDarrick J. Wong if (!bs->cur) 389858333dcSDarrick J. Wong return 0; 390858333dcSDarrick J. Wong 39152dc4b44SDarrick J. Wong btnum = bs->cur->bc_btnum; 392858333dcSDarrick J. Wong agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr); 39352dc4b44SDarrick J. Wong agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr); 394858333dcSDarrick J. Wong 395858333dcSDarrick J. Wong init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS; 396858333dcSDarrick J. Wong if (init_sa) { 397858333dcSDarrick J. Wong error = xfs_scrub_ag_init(bs->sc, agno, &bs->sc->sa); 398858333dcSDarrick J. Wong if (!xfs_scrub_btree_xref_process_error(bs->sc, bs->cur, 399858333dcSDarrick J. Wong level, &error)) 400858333dcSDarrick J. Wong return error; 401858333dcSDarrick J. Wong } 402858333dcSDarrick J. Wong 40352dc4b44SDarrick J. Wong xfs_scrub_xref_is_used_space(bs->sc, agbno, 1); 40452dc4b44SDarrick J. Wong /* 40552dc4b44SDarrick J. Wong * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we 40652dc4b44SDarrick J. Wong * have to nullify it (to shut down further block owner checks) if 40752dc4b44SDarrick J. Wong * self-xref encounters problems. 40852dc4b44SDarrick J. Wong */ 40952dc4b44SDarrick J. Wong if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO) 41052dc4b44SDarrick J. Wong bs->cur = NULL; 41152dc4b44SDarrick J. Wong 412d852657cSDarrick J. Wong xfs_scrub_xref_is_owned_by(bs->sc, agbno, 1, bs->oinfo); 413d852657cSDarrick J. Wong if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP) 414d852657cSDarrick J. Wong bs->cur = NULL; 415d852657cSDarrick J. Wong 416858333dcSDarrick J. Wong if (init_sa) 417858333dcSDarrick J. Wong xfs_scrub_ag_free(bs->sc, &bs->sc->sa); 418858333dcSDarrick J. Wong 419858333dcSDarrick J. Wong return error; 420858333dcSDarrick J. Wong } 421858333dcSDarrick J. Wong 422858333dcSDarrick J. Wong /* Check the owner of a btree block. */ 423858333dcSDarrick J. Wong STATIC int 424858333dcSDarrick J. Wong xfs_scrub_btree_check_owner( 425858333dcSDarrick J. Wong struct xfs_scrub_btree *bs, 426858333dcSDarrick J. Wong int level, 427858333dcSDarrick J. Wong struct xfs_buf *bp) 428858333dcSDarrick J. Wong { 429858333dcSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 430858333dcSDarrick J. Wong struct check_owner *co; 431858333dcSDarrick J. Wong 432858333dcSDarrick J. Wong if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && bp == NULL) 433858333dcSDarrick J. Wong return 0; 434858333dcSDarrick J. Wong 435858333dcSDarrick J. Wong /* 436858333dcSDarrick J. Wong * We want to cross-reference each btree block with the bnobt 437858333dcSDarrick J. Wong * and the rmapbt. We cannot cross-reference the bnobt or 438858333dcSDarrick J. Wong * rmapbt while scanning the bnobt or rmapbt, respectively, 439858333dcSDarrick J. Wong * because we cannot alter the cursor and we'd prefer not to 440858333dcSDarrick J. Wong * duplicate cursors. Therefore, save the buffer daddr for 441858333dcSDarrick J. Wong * later scanning. 442858333dcSDarrick J. Wong */ 443858333dcSDarrick J. Wong if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) { 444858333dcSDarrick J. Wong co = kmem_alloc(sizeof(struct check_owner), 445858333dcSDarrick J. Wong KM_MAYFAIL | KM_NOFS); 446858333dcSDarrick J. Wong if (!co) 447858333dcSDarrick J. Wong return -ENOMEM; 448858333dcSDarrick J. Wong co->level = level; 449858333dcSDarrick J. Wong co->daddr = XFS_BUF_ADDR(bp); 450858333dcSDarrick J. Wong list_add_tail(&co->list, &bs->to_check); 451858333dcSDarrick J. Wong return 0; 452858333dcSDarrick J. Wong } 453858333dcSDarrick J. Wong 454858333dcSDarrick J. Wong return xfs_scrub_btree_check_block_owner(bs, level, XFS_BUF_ADDR(bp)); 455858333dcSDarrick J. Wong } 456858333dcSDarrick J. Wong 457cc3e0948SDarrick J. Wong /* 458cc3e0948SDarrick J. Wong * Grab and scrub a btree block given a btree pointer. Returns block 459cc3e0948SDarrick J. Wong * and buffer pointers (if applicable) if they're ok to use. 460cc3e0948SDarrick J. Wong */ 461cc3e0948SDarrick J. Wong STATIC int 462cc3e0948SDarrick J. Wong xfs_scrub_btree_get_block( 463cc3e0948SDarrick J. Wong struct xfs_scrub_btree *bs, 464cc3e0948SDarrick J. Wong int level, 465cc3e0948SDarrick J. Wong union xfs_btree_ptr *pp, 466cc3e0948SDarrick J. Wong struct xfs_btree_block **pblock, 467cc3e0948SDarrick J. Wong struct xfs_buf **pbp) 468cc3e0948SDarrick J. Wong { 469cc3e0948SDarrick J. Wong void *failed_at; 470cc3e0948SDarrick J. Wong int error; 471cc3e0948SDarrick J. Wong 472cc3e0948SDarrick J. Wong *pblock = NULL; 473cc3e0948SDarrick J. Wong *pbp = NULL; 474cc3e0948SDarrick J. Wong 475cc3e0948SDarrick J. Wong error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock); 476cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_process_error(bs->sc, bs->cur, level, &error) || 477a605e869SDarrick J. Wong !*pblock) 478cc3e0948SDarrick J. Wong return error; 479cc3e0948SDarrick J. Wong 480cc3e0948SDarrick J. Wong xfs_btree_get_block(bs->cur, level, pbp); 481cc3e0948SDarrick J. Wong if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS) 482cc3e0948SDarrick J. Wong failed_at = __xfs_btree_check_lblock(bs->cur, *pblock, 483cc3e0948SDarrick J. Wong level, *pbp); 484cc3e0948SDarrick J. Wong else 485cc3e0948SDarrick J. Wong failed_at = __xfs_btree_check_sblock(bs->cur, *pblock, 486cc3e0948SDarrick J. Wong level, *pbp); 487cc3e0948SDarrick J. Wong if (failed_at) { 488cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, bs->cur, level); 489cc3e0948SDarrick J. Wong return 0; 490cc3e0948SDarrick J. Wong } 491cf1b0b8bSDarrick J. Wong if (*pbp) 492cf1b0b8bSDarrick J. Wong xfs_scrub_buffer_recheck(bs->sc, *pbp); 493cc3e0948SDarrick J. Wong 494cc3e0948SDarrick J. Wong /* 495858333dcSDarrick J. Wong * Check the block's owner; this function absorbs error codes 496858333dcSDarrick J. Wong * for us. 497858333dcSDarrick J. Wong */ 498858333dcSDarrick J. Wong error = xfs_scrub_btree_check_owner(bs, level, *pbp); 499858333dcSDarrick J. Wong if (error) 500858333dcSDarrick J. Wong return error; 501858333dcSDarrick J. Wong 502858333dcSDarrick J. Wong /* 503cc3e0948SDarrick J. Wong * Check the block's siblings; this function absorbs error codes 504cc3e0948SDarrick J. Wong * for us. 505cc3e0948SDarrick J. Wong */ 506cc3e0948SDarrick J. Wong return xfs_scrub_btree_block_check_siblings(bs, *pblock); 507cc3e0948SDarrick J. Wong } 508cc3e0948SDarrick J. Wong 509cc3e0948SDarrick J. Wong /* 5102fdbec5cSDarrick J. Wong * Check that the low and high keys of this block match the keys stored 5112fdbec5cSDarrick J. Wong * in the parent block. 5122fdbec5cSDarrick J. Wong */ 5132fdbec5cSDarrick J. Wong STATIC void 5142fdbec5cSDarrick J. Wong xfs_scrub_btree_block_keys( 5152fdbec5cSDarrick J. Wong struct xfs_scrub_btree *bs, 5162fdbec5cSDarrick J. Wong int level, 5172fdbec5cSDarrick J. Wong struct xfs_btree_block *block) 5182fdbec5cSDarrick J. Wong { 5192fdbec5cSDarrick J. Wong union xfs_btree_key block_keys; 5202fdbec5cSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 5212fdbec5cSDarrick J. Wong union xfs_btree_key *high_bk; 5222fdbec5cSDarrick J. Wong union xfs_btree_key *parent_keys; 5232fdbec5cSDarrick J. Wong union xfs_btree_key *high_pk; 5242fdbec5cSDarrick J. Wong struct xfs_btree_block *parent_block; 5252fdbec5cSDarrick J. Wong struct xfs_buf *bp; 5262fdbec5cSDarrick J. Wong 5272fdbec5cSDarrick J. Wong if (level >= cur->bc_nlevels - 1) 5282fdbec5cSDarrick J. Wong return; 5292fdbec5cSDarrick J. Wong 5302fdbec5cSDarrick J. Wong /* Calculate the keys for this block. */ 5312fdbec5cSDarrick J. Wong xfs_btree_get_keys(cur, block, &block_keys); 5322fdbec5cSDarrick J. Wong 5332fdbec5cSDarrick J. Wong /* Obtain the parent's copy of the keys for this block. */ 5342fdbec5cSDarrick J. Wong parent_block = xfs_btree_get_block(cur, level + 1, &bp); 5352fdbec5cSDarrick J. Wong parent_keys = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1], 5362fdbec5cSDarrick J. Wong parent_block); 5372fdbec5cSDarrick J. Wong 5382fdbec5cSDarrick J. Wong if (cur->bc_ops->diff_two_keys(cur, &block_keys, parent_keys) != 0) 5392fdbec5cSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, 1); 5402fdbec5cSDarrick J. Wong 5412fdbec5cSDarrick J. Wong if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 5422fdbec5cSDarrick J. Wong return; 5432fdbec5cSDarrick J. Wong 5442fdbec5cSDarrick J. Wong /* Get high keys */ 5452fdbec5cSDarrick J. Wong high_bk = xfs_btree_high_key_from_key(cur, &block_keys); 5462fdbec5cSDarrick J. Wong high_pk = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1], 5472fdbec5cSDarrick J. Wong parent_block); 5482fdbec5cSDarrick J. Wong 5492fdbec5cSDarrick J. Wong if (cur->bc_ops->diff_two_keys(cur, high_bk, high_pk) != 0) 5502fdbec5cSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, 1); 5512fdbec5cSDarrick J. Wong } 5522fdbec5cSDarrick J. Wong 5532fdbec5cSDarrick J. Wong /* 554537964bcSDarrick J. Wong * Visit all nodes and leaves of a btree. Check that all pointers and 555537964bcSDarrick J. Wong * records are in order, that the keys reflect the records, and use a callback 556cc3e0948SDarrick J. Wong * so that the caller can verify individual records. 557537964bcSDarrick J. Wong */ 558537964bcSDarrick J. Wong int 559537964bcSDarrick J. Wong xfs_scrub_btree( 560537964bcSDarrick J. Wong struct xfs_scrub_context *sc, 561537964bcSDarrick J. Wong struct xfs_btree_cur *cur, 562537964bcSDarrick J. Wong xfs_scrub_btree_rec_fn scrub_fn, 563537964bcSDarrick J. Wong struct xfs_owner_info *oinfo, 564537964bcSDarrick J. Wong void *private) 565537964bcSDarrick J. Wong { 56688aa5de4SChristoph Hellwig struct xfs_scrub_btree bs = { NULL }; 567cc3e0948SDarrick J. Wong union xfs_btree_ptr ptr; 568cc3e0948SDarrick J. Wong union xfs_btree_ptr *pp; 56937f3fa7fSDarrick J. Wong union xfs_btree_rec *recp; 570cc3e0948SDarrick J. Wong struct xfs_btree_block *block; 571cc3e0948SDarrick J. Wong int level; 572cc3e0948SDarrick J. Wong struct xfs_buf *bp; 573858333dcSDarrick J. Wong struct check_owner *co; 574858333dcSDarrick J. Wong struct check_owner *n; 575cc3e0948SDarrick J. Wong int i; 576cc3e0948SDarrick J. Wong int error = 0; 577537964bcSDarrick J. Wong 578cc3e0948SDarrick J. Wong /* Initialize scrub state */ 579cc3e0948SDarrick J. Wong bs.cur = cur; 580cc3e0948SDarrick J. Wong bs.scrub_rec = scrub_fn; 581cc3e0948SDarrick J. Wong bs.oinfo = oinfo; 582cc3e0948SDarrick J. Wong bs.firstrec = true; 583cc3e0948SDarrick J. Wong bs.private = private; 584cc3e0948SDarrick J. Wong bs.sc = sc; 585cc3e0948SDarrick J. Wong for (i = 0; i < XFS_BTREE_MAXLEVELS; i++) 586cc3e0948SDarrick J. Wong bs.firstkey[i] = true; 587cc3e0948SDarrick J. Wong INIT_LIST_HEAD(&bs.to_check); 588cc3e0948SDarrick J. Wong 589cc3e0948SDarrick J. Wong /* Don't try to check a tree with a height we can't handle. */ 590cc3e0948SDarrick J. Wong if (cur->bc_nlevels > XFS_BTREE_MAXLEVELS) { 591cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(sc, cur, 0); 592cc3e0948SDarrick J. Wong goto out; 593cc3e0948SDarrick J. Wong } 594cc3e0948SDarrick J. Wong 595cc3e0948SDarrick J. Wong /* 596cc3e0948SDarrick J. Wong * Load the root of the btree. The helper function absorbs 597cc3e0948SDarrick J. Wong * error codes for us. 598cc3e0948SDarrick J. Wong */ 599cc3e0948SDarrick J. Wong level = cur->bc_nlevels - 1; 600cc3e0948SDarrick J. Wong cur->bc_ops->init_ptr_from_cur(cur, &ptr); 601cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_ptr_ok(&bs, cur->bc_nlevels, &ptr)) 602cc3e0948SDarrick J. Wong goto out; 603cc3e0948SDarrick J. Wong error = xfs_scrub_btree_get_block(&bs, level, &ptr, &block, &bp); 604cc3e0948SDarrick J. Wong if (error || !block) 605cc3e0948SDarrick J. Wong goto out; 606cc3e0948SDarrick J. Wong 607cc3e0948SDarrick J. Wong cur->bc_ptrs[level] = 1; 608cc3e0948SDarrick J. Wong 609cc3e0948SDarrick J. Wong while (level < cur->bc_nlevels) { 610cc3e0948SDarrick J. Wong block = xfs_btree_get_block(cur, level, &bp); 611cc3e0948SDarrick J. Wong 612cc3e0948SDarrick J. Wong if (level == 0) { 613cc3e0948SDarrick J. Wong /* End of leaf, pop back towards the root. */ 614cc3e0948SDarrick J. Wong if (cur->bc_ptrs[level] > 615cc3e0948SDarrick J. Wong be16_to_cpu(block->bb_numrecs)) { 6162fdbec5cSDarrick J. Wong xfs_scrub_btree_block_keys(&bs, level, block); 617cc3e0948SDarrick J. Wong if (level < cur->bc_nlevels - 1) 618cc3e0948SDarrick J. Wong cur->bc_ptrs[level + 1]++; 619cc3e0948SDarrick J. Wong level++; 620cc3e0948SDarrick J. Wong continue; 621cc3e0948SDarrick J. Wong } 622cc3e0948SDarrick J. Wong 62337f3fa7fSDarrick J. Wong /* Records in order for scrub? */ 62437f3fa7fSDarrick J. Wong xfs_scrub_btree_rec(&bs); 62537f3fa7fSDarrick J. Wong 62637f3fa7fSDarrick J. Wong /* Call out to the record checker. */ 62737f3fa7fSDarrick J. Wong recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); 62837f3fa7fSDarrick J. Wong error = bs.scrub_rec(&bs, recp); 62937f3fa7fSDarrick J. Wong if (error) 63037f3fa7fSDarrick J. Wong break; 63137f3fa7fSDarrick J. Wong if (xfs_scrub_should_terminate(sc, &error) || 63237f3fa7fSDarrick J. Wong (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT)) 633cc3e0948SDarrick J. Wong break; 634cc3e0948SDarrick J. Wong 635cc3e0948SDarrick J. Wong cur->bc_ptrs[level]++; 636cc3e0948SDarrick J. Wong continue; 637cc3e0948SDarrick J. Wong } 638cc3e0948SDarrick J. Wong 639cc3e0948SDarrick J. Wong /* End of node, pop back towards the root. */ 640cc3e0948SDarrick J. Wong if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { 6412fdbec5cSDarrick J. Wong xfs_scrub_btree_block_keys(&bs, level, block); 642cc3e0948SDarrick J. Wong if (level < cur->bc_nlevels - 1) 643cc3e0948SDarrick J. Wong cur->bc_ptrs[level + 1]++; 644cc3e0948SDarrick J. Wong level++; 645cc3e0948SDarrick J. Wong continue; 646cc3e0948SDarrick J. Wong } 647cc3e0948SDarrick J. Wong 64837f3fa7fSDarrick J. Wong /* Keys in order for scrub? */ 64937f3fa7fSDarrick J. Wong xfs_scrub_btree_key(&bs, level); 65037f3fa7fSDarrick J. Wong 651cc3e0948SDarrick J. Wong /* Drill another level deeper. */ 652cc3e0948SDarrick J. Wong pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); 653cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_ptr_ok(&bs, level, pp)) { 654cc3e0948SDarrick J. Wong cur->bc_ptrs[level]++; 655cc3e0948SDarrick J. Wong continue; 656cc3e0948SDarrick J. Wong } 657cc3e0948SDarrick J. Wong level--; 658cc3e0948SDarrick J. Wong error = xfs_scrub_btree_get_block(&bs, level, pp, &block, &bp); 659cc3e0948SDarrick J. Wong if (error || !block) 660cc3e0948SDarrick J. Wong goto out; 661cc3e0948SDarrick J. Wong 662cc3e0948SDarrick J. Wong cur->bc_ptrs[level] = 1; 663cc3e0948SDarrick J. Wong } 664cc3e0948SDarrick J. Wong 665cc3e0948SDarrick J. Wong out: 666858333dcSDarrick J. Wong /* Process deferred owner checks on btree blocks. */ 667858333dcSDarrick J. Wong list_for_each_entry_safe(co, n, &bs.to_check, list) { 668858333dcSDarrick J. Wong if (!error && bs.cur) 669858333dcSDarrick J. Wong error = xfs_scrub_btree_check_block_owner(&bs, 670858333dcSDarrick J. Wong co->level, co->daddr); 671858333dcSDarrick J. Wong list_del(&co->list); 672858333dcSDarrick J. Wong kmem_free(co); 673858333dcSDarrick J. Wong } 674858333dcSDarrick J. Wong 675537964bcSDarrick J. Wong return error; 676537964bcSDarrick J. Wong } 677