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 */ 45537964bcSDarrick J. Wong bool 46537964bcSDarrick 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, 50537964bcSDarrick J. Wong int *error) 51537964bcSDarrick J. Wong { 52537964bcSDarrick J. Wong if (*error == 0) 53537964bcSDarrick J. Wong return true; 54537964bcSDarrick J. Wong 55537964bcSDarrick J. Wong switch (*error) { 56537964bcSDarrick J. Wong case -EDEADLOCK: 57537964bcSDarrick J. Wong /* Used to restart an op with deadlock avoidance. */ 58537964bcSDarrick J. Wong trace_xfs_scrub_deadlock_retry(sc->ip, sc->sm, *error); 59537964bcSDarrick J. Wong break; 60537964bcSDarrick J. Wong case -EFSBADCRC: 61537964bcSDarrick J. Wong case -EFSCORRUPTED: 62537964bcSDarrick J. Wong /* Note the badness but don't abort. */ 63537964bcSDarrick J. Wong sc->sm->sm_flags |= XFS_SCRUB_OFLAG_CORRUPT; 64537964bcSDarrick J. Wong *error = 0; 65537964bcSDarrick J. Wong /* fall through */ 66537964bcSDarrick J. Wong default: 67537964bcSDarrick J. Wong if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) 68537964bcSDarrick J. Wong trace_xfs_scrub_ifork_btree_op_error(sc, cur, level, 69537964bcSDarrick J. Wong *error, __return_address); 70537964bcSDarrick J. Wong else 71537964bcSDarrick J. Wong trace_xfs_scrub_btree_op_error(sc, cur, level, 72537964bcSDarrick J. Wong *error, __return_address); 73537964bcSDarrick J. Wong break; 74537964bcSDarrick J. Wong } 75537964bcSDarrick J. Wong return false; 76537964bcSDarrick J. Wong } 77537964bcSDarrick J. Wong 78537964bcSDarrick J. Wong /* Record btree block corruption. */ 79537964bcSDarrick J. Wong void 80537964bcSDarrick J. Wong xfs_scrub_btree_set_corrupt( 81537964bcSDarrick J. Wong struct xfs_scrub_context *sc, 82537964bcSDarrick J. Wong struct xfs_btree_cur *cur, 83537964bcSDarrick J. Wong int level) 84537964bcSDarrick J. Wong { 85537964bcSDarrick J. Wong sc->sm->sm_flags |= XFS_SCRUB_OFLAG_CORRUPT; 86537964bcSDarrick J. Wong 87537964bcSDarrick J. Wong if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) 88537964bcSDarrick J. Wong trace_xfs_scrub_ifork_btree_error(sc, cur, level, 89537964bcSDarrick J. Wong __return_address); 90537964bcSDarrick J. Wong else 91537964bcSDarrick J. Wong trace_xfs_scrub_btree_error(sc, cur, level, 92537964bcSDarrick J. Wong __return_address); 93537964bcSDarrick J. Wong } 94537964bcSDarrick J. Wong 95537964bcSDarrick J. Wong /* 9637f3fa7fSDarrick J. Wong * Make sure this record is in order and doesn't stray outside of the parent 9737f3fa7fSDarrick J. Wong * keys. 9837f3fa7fSDarrick J. Wong */ 9937f3fa7fSDarrick J. Wong STATIC void 10037f3fa7fSDarrick J. Wong xfs_scrub_btree_rec( 10137f3fa7fSDarrick J. Wong struct xfs_scrub_btree *bs) 10237f3fa7fSDarrick J. Wong { 10337f3fa7fSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 10437f3fa7fSDarrick J. Wong union xfs_btree_rec *rec; 10537f3fa7fSDarrick J. Wong union xfs_btree_key key; 10637f3fa7fSDarrick J. Wong union xfs_btree_key hkey; 10737f3fa7fSDarrick J. Wong union xfs_btree_key *keyp; 10837f3fa7fSDarrick J. Wong struct xfs_btree_block *block; 10937f3fa7fSDarrick J. Wong struct xfs_btree_block *keyblock; 11037f3fa7fSDarrick J. Wong struct xfs_buf *bp; 11137f3fa7fSDarrick J. Wong 11237f3fa7fSDarrick J. Wong block = xfs_btree_get_block(cur, 0, &bp); 11337f3fa7fSDarrick J. Wong rec = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); 11437f3fa7fSDarrick J. Wong 11537f3fa7fSDarrick J. Wong trace_xfs_scrub_btree_rec(bs->sc, cur, 0); 11637f3fa7fSDarrick J. Wong 11737f3fa7fSDarrick J. Wong /* If this isn't the first record, are they in order? */ 11837f3fa7fSDarrick J. Wong if (!bs->firstrec && !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec)) 11937f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, 0); 12037f3fa7fSDarrick J. Wong bs->firstrec = false; 12137f3fa7fSDarrick J. Wong memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len); 12237f3fa7fSDarrick J. Wong 12337f3fa7fSDarrick J. Wong if (cur->bc_nlevels == 1) 12437f3fa7fSDarrick J. Wong return; 12537f3fa7fSDarrick J. Wong 12637f3fa7fSDarrick J. Wong /* Is this at least as large as the parent low key? */ 12737f3fa7fSDarrick J. Wong cur->bc_ops->init_key_from_rec(&key, rec); 12837f3fa7fSDarrick J. Wong keyblock = xfs_btree_get_block(cur, 1, &bp); 12937f3fa7fSDarrick J. Wong keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[1], keyblock); 13037f3fa7fSDarrick J. Wong if (cur->bc_ops->diff_two_keys(cur, &key, keyp) < 0) 13137f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, 1); 13237f3fa7fSDarrick J. Wong 13337f3fa7fSDarrick J. Wong if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 13437f3fa7fSDarrick J. Wong return; 13537f3fa7fSDarrick J. Wong 13637f3fa7fSDarrick J. Wong /* Is this no larger than the parent high key? */ 13737f3fa7fSDarrick J. Wong cur->bc_ops->init_high_key_from_rec(&hkey, rec); 13837f3fa7fSDarrick J. Wong keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[1], keyblock); 13937f3fa7fSDarrick J. Wong if (cur->bc_ops->diff_two_keys(cur, keyp, &hkey) < 0) 14037f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, 1); 14137f3fa7fSDarrick J. Wong } 14237f3fa7fSDarrick J. Wong 14337f3fa7fSDarrick J. Wong /* 14437f3fa7fSDarrick J. Wong * Make sure this key is in order and doesn't stray outside of the parent 14537f3fa7fSDarrick J. Wong * keys. 14637f3fa7fSDarrick J. Wong */ 14737f3fa7fSDarrick J. Wong STATIC void 14837f3fa7fSDarrick J. Wong xfs_scrub_btree_key( 14937f3fa7fSDarrick J. Wong struct xfs_scrub_btree *bs, 15037f3fa7fSDarrick J. Wong int level) 15137f3fa7fSDarrick J. Wong { 15237f3fa7fSDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 15337f3fa7fSDarrick J. Wong union xfs_btree_key *key; 15437f3fa7fSDarrick J. Wong union xfs_btree_key *keyp; 15537f3fa7fSDarrick J. Wong struct xfs_btree_block *block; 15637f3fa7fSDarrick J. Wong struct xfs_btree_block *keyblock; 15737f3fa7fSDarrick J. Wong struct xfs_buf *bp; 15837f3fa7fSDarrick J. Wong 15937f3fa7fSDarrick J. Wong block = xfs_btree_get_block(cur, level, &bp); 16037f3fa7fSDarrick J. Wong key = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); 16137f3fa7fSDarrick J. Wong 16237f3fa7fSDarrick J. Wong trace_xfs_scrub_btree_key(bs->sc, cur, level); 16337f3fa7fSDarrick J. Wong 16437f3fa7fSDarrick J. Wong /* If this isn't the first key, are they in order? */ 16537f3fa7fSDarrick J. Wong if (!bs->firstkey[level] && 16637f3fa7fSDarrick J. Wong !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level], key)) 16737f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 16837f3fa7fSDarrick J. Wong bs->firstkey[level] = false; 16937f3fa7fSDarrick J. Wong memcpy(&bs->lastkey[level], key, cur->bc_ops->key_len); 17037f3fa7fSDarrick J. Wong 17137f3fa7fSDarrick J. Wong if (level + 1 >= cur->bc_nlevels) 17237f3fa7fSDarrick J. Wong return; 17337f3fa7fSDarrick J. Wong 17437f3fa7fSDarrick J. Wong /* Is this at least as large as the parent low key? */ 17537f3fa7fSDarrick J. Wong keyblock = xfs_btree_get_block(cur, level + 1, &bp); 17637f3fa7fSDarrick J. Wong keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1], keyblock); 17737f3fa7fSDarrick J. Wong if (cur->bc_ops->diff_two_keys(cur, key, keyp) < 0) 17837f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 17937f3fa7fSDarrick J. Wong 18037f3fa7fSDarrick J. Wong if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) 18137f3fa7fSDarrick J. Wong return; 18237f3fa7fSDarrick J. Wong 18337f3fa7fSDarrick J. Wong /* Is this no larger than the parent high key? */ 18437f3fa7fSDarrick J. Wong key = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); 18537f3fa7fSDarrick J. Wong keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1], keyblock); 18637f3fa7fSDarrick J. Wong if (cur->bc_ops->diff_two_keys(cur, keyp, key) < 0) 18737f3fa7fSDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 18837f3fa7fSDarrick J. Wong } 18937f3fa7fSDarrick J. Wong 19037f3fa7fSDarrick J. Wong /* 191cc3e0948SDarrick J. Wong * Check a btree pointer. Returns true if it's ok to use this pointer. 192cc3e0948SDarrick J. Wong * Callers do not need to set the corrupt flag. 193cc3e0948SDarrick J. Wong */ 194cc3e0948SDarrick J. Wong static bool 195cc3e0948SDarrick J. Wong xfs_scrub_btree_ptr_ok( 196cc3e0948SDarrick J. Wong struct xfs_scrub_btree *bs, 197cc3e0948SDarrick J. Wong int level, 198cc3e0948SDarrick J. Wong union xfs_btree_ptr *ptr) 199cc3e0948SDarrick J. Wong { 200cc3e0948SDarrick J. Wong bool res; 201cc3e0948SDarrick J. Wong 202cc3e0948SDarrick J. Wong /* A btree rooted in an inode has no block pointer to the root. */ 203cc3e0948SDarrick J. Wong if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && 204cc3e0948SDarrick J. Wong level == bs->cur->bc_nlevels) 205cc3e0948SDarrick J. Wong return true; 206cc3e0948SDarrick J. Wong 207cc3e0948SDarrick J. Wong /* Otherwise, check the pointers. */ 208cc3e0948SDarrick J. Wong if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS) 209cc3e0948SDarrick J. Wong res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level); 210cc3e0948SDarrick J. Wong else 211cc3e0948SDarrick J. Wong res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level); 212cc3e0948SDarrick J. Wong if (!res) 213cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, bs->cur, level); 214cc3e0948SDarrick J. Wong 215cc3e0948SDarrick J. Wong return res; 216cc3e0948SDarrick J. Wong } 217cc3e0948SDarrick J. Wong 218cc3e0948SDarrick J. Wong /* Check that a btree block's sibling matches what we expect it. */ 219cc3e0948SDarrick J. Wong STATIC int 220cc3e0948SDarrick J. Wong xfs_scrub_btree_block_check_sibling( 221cc3e0948SDarrick J. Wong struct xfs_scrub_btree *bs, 222cc3e0948SDarrick J. Wong int level, 223cc3e0948SDarrick J. Wong int direction, 224cc3e0948SDarrick J. Wong union xfs_btree_ptr *sibling) 225cc3e0948SDarrick J. Wong { 226cc3e0948SDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 227cc3e0948SDarrick J. Wong struct xfs_btree_block *pblock; 228cc3e0948SDarrick J. Wong struct xfs_buf *pbp; 229cc3e0948SDarrick J. Wong struct xfs_btree_cur *ncur = NULL; 230cc3e0948SDarrick J. Wong union xfs_btree_ptr *pp; 231cc3e0948SDarrick J. Wong int success; 232cc3e0948SDarrick J. Wong int error; 233cc3e0948SDarrick J. Wong 234cc3e0948SDarrick J. Wong error = xfs_btree_dup_cursor(cur, &ncur); 235cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_process_error(bs->sc, cur, level + 1, &error) || 236cc3e0948SDarrick J. Wong !ncur) 237cc3e0948SDarrick J. Wong return error; 238cc3e0948SDarrick J. Wong 239cc3e0948SDarrick J. Wong /* 240cc3e0948SDarrick J. Wong * If the pointer is null, we shouldn't be able to move the upper 241cc3e0948SDarrick J. Wong * level pointer anywhere. 242cc3e0948SDarrick J. Wong */ 243cc3e0948SDarrick J. Wong if (xfs_btree_ptr_is_null(cur, sibling)) { 244cc3e0948SDarrick J. Wong if (direction > 0) 245cc3e0948SDarrick J. Wong error = xfs_btree_increment(ncur, level + 1, &success); 246cc3e0948SDarrick J. Wong else 247cc3e0948SDarrick J. Wong error = xfs_btree_decrement(ncur, level + 1, &success); 248cc3e0948SDarrick J. Wong if (error == 0 && success) 249cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 250cc3e0948SDarrick J. Wong error = 0; 251cc3e0948SDarrick J. Wong goto out; 252cc3e0948SDarrick J. Wong } 253cc3e0948SDarrick J. Wong 254cc3e0948SDarrick J. Wong /* Increment upper level pointer. */ 255cc3e0948SDarrick J. Wong if (direction > 0) 256cc3e0948SDarrick J. Wong error = xfs_btree_increment(ncur, level + 1, &success); 257cc3e0948SDarrick J. Wong else 258cc3e0948SDarrick J. Wong error = xfs_btree_decrement(ncur, level + 1, &success); 259cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_process_error(bs->sc, cur, level + 1, &error)) 260cc3e0948SDarrick J. Wong goto out; 261cc3e0948SDarrick J. Wong if (!success) { 262cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level + 1); 263cc3e0948SDarrick J. Wong goto out; 264cc3e0948SDarrick J. Wong } 265cc3e0948SDarrick J. Wong 266cc3e0948SDarrick J. Wong /* Compare upper level pointer to sibling pointer. */ 267cc3e0948SDarrick J. Wong pblock = xfs_btree_get_block(ncur, level + 1, &pbp); 268cc3e0948SDarrick J. Wong pp = xfs_btree_ptr_addr(ncur, ncur->bc_ptrs[level + 1], pblock); 269cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_ptr_ok(bs, level + 1, pp)) 270cc3e0948SDarrick J. Wong goto out; 271cc3e0948SDarrick J. Wong 272cc3e0948SDarrick J. Wong if (xfs_btree_diff_two_ptrs(cur, pp, sibling)) 273cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 274cc3e0948SDarrick J. Wong out: 275cc3e0948SDarrick J. Wong xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR); 276cc3e0948SDarrick J. Wong return error; 277cc3e0948SDarrick J. Wong } 278cc3e0948SDarrick J. Wong 279cc3e0948SDarrick J. Wong /* Check the siblings of a btree block. */ 280cc3e0948SDarrick J. Wong STATIC int 281cc3e0948SDarrick J. Wong xfs_scrub_btree_block_check_siblings( 282cc3e0948SDarrick J. Wong struct xfs_scrub_btree *bs, 283cc3e0948SDarrick J. Wong struct xfs_btree_block *block) 284cc3e0948SDarrick J. Wong { 285cc3e0948SDarrick J. Wong struct xfs_btree_cur *cur = bs->cur; 286cc3e0948SDarrick J. Wong union xfs_btree_ptr leftsib; 287cc3e0948SDarrick J. Wong union xfs_btree_ptr rightsib; 288cc3e0948SDarrick J. Wong int level; 289cc3e0948SDarrick J. Wong int error = 0; 290cc3e0948SDarrick J. Wong 291cc3e0948SDarrick J. Wong xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB); 292cc3e0948SDarrick J. Wong xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB); 293cc3e0948SDarrick J. Wong level = xfs_btree_get_level(block); 294cc3e0948SDarrick J. Wong 295cc3e0948SDarrick J. Wong /* Root block should never have siblings. */ 296cc3e0948SDarrick J. Wong if (level == cur->bc_nlevels - 1) { 297cc3e0948SDarrick J. Wong if (!xfs_btree_ptr_is_null(cur, &leftsib) || 298cc3e0948SDarrick J. Wong !xfs_btree_ptr_is_null(cur, &rightsib)) 299cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, cur, level); 300cc3e0948SDarrick J. Wong goto out; 301cc3e0948SDarrick J. Wong } 302cc3e0948SDarrick J. Wong 303cc3e0948SDarrick J. Wong /* 304cc3e0948SDarrick J. Wong * Does the left & right sibling pointers match the adjacent 305cc3e0948SDarrick J. Wong * parent level pointers? 306cc3e0948SDarrick J. Wong * (These function absorbs error codes for us.) 307cc3e0948SDarrick J. Wong */ 308cc3e0948SDarrick J. Wong error = xfs_scrub_btree_block_check_sibling(bs, level, -1, &leftsib); 309cc3e0948SDarrick J. Wong if (error) 310cc3e0948SDarrick J. Wong return error; 311cc3e0948SDarrick J. Wong error = xfs_scrub_btree_block_check_sibling(bs, level, 1, &rightsib); 312cc3e0948SDarrick J. Wong if (error) 313cc3e0948SDarrick J. Wong return error; 314cc3e0948SDarrick J. Wong out: 315cc3e0948SDarrick J. Wong return error; 316cc3e0948SDarrick J. Wong } 317cc3e0948SDarrick J. Wong 318cc3e0948SDarrick J. Wong /* 319cc3e0948SDarrick J. Wong * Grab and scrub a btree block given a btree pointer. Returns block 320cc3e0948SDarrick J. Wong * and buffer pointers (if applicable) if they're ok to use. 321cc3e0948SDarrick J. Wong */ 322cc3e0948SDarrick J. Wong STATIC int 323cc3e0948SDarrick J. Wong xfs_scrub_btree_get_block( 324cc3e0948SDarrick J. Wong struct xfs_scrub_btree *bs, 325cc3e0948SDarrick J. Wong int level, 326cc3e0948SDarrick J. Wong union xfs_btree_ptr *pp, 327cc3e0948SDarrick J. Wong struct xfs_btree_block **pblock, 328cc3e0948SDarrick J. Wong struct xfs_buf **pbp) 329cc3e0948SDarrick J. Wong { 330cc3e0948SDarrick J. Wong void *failed_at; 331cc3e0948SDarrick J. Wong int error; 332cc3e0948SDarrick J. Wong 333cc3e0948SDarrick J. Wong *pblock = NULL; 334cc3e0948SDarrick J. Wong *pbp = NULL; 335cc3e0948SDarrick J. Wong 336cc3e0948SDarrick J. Wong error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock); 337cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_process_error(bs->sc, bs->cur, level, &error) || 338cc3e0948SDarrick J. Wong !pblock) 339cc3e0948SDarrick J. Wong return error; 340cc3e0948SDarrick J. Wong 341cc3e0948SDarrick J. Wong xfs_btree_get_block(bs->cur, level, pbp); 342cc3e0948SDarrick J. Wong if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS) 343cc3e0948SDarrick J. Wong failed_at = __xfs_btree_check_lblock(bs->cur, *pblock, 344cc3e0948SDarrick J. Wong level, *pbp); 345cc3e0948SDarrick J. Wong else 346cc3e0948SDarrick J. Wong failed_at = __xfs_btree_check_sblock(bs->cur, *pblock, 347cc3e0948SDarrick J. Wong level, *pbp); 348cc3e0948SDarrick J. Wong if (failed_at) { 349cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(bs->sc, bs->cur, level); 350cc3e0948SDarrick J. Wong return 0; 351cc3e0948SDarrick J. Wong } 352cc3e0948SDarrick J. Wong 353cc3e0948SDarrick J. Wong /* 354cc3e0948SDarrick J. Wong * Check the block's siblings; this function absorbs error codes 355cc3e0948SDarrick J. Wong * for us. 356cc3e0948SDarrick J. Wong */ 357cc3e0948SDarrick J. Wong return xfs_scrub_btree_block_check_siblings(bs, *pblock); 358cc3e0948SDarrick J. Wong } 359cc3e0948SDarrick J. Wong 360cc3e0948SDarrick J. Wong /* 361537964bcSDarrick J. Wong * Visit all nodes and leaves of a btree. Check that all pointers and 362537964bcSDarrick J. Wong * records are in order, that the keys reflect the records, and use a callback 363cc3e0948SDarrick J. Wong * so that the caller can verify individual records. 364537964bcSDarrick J. Wong */ 365537964bcSDarrick J. Wong int 366537964bcSDarrick J. Wong xfs_scrub_btree( 367537964bcSDarrick J. Wong struct xfs_scrub_context *sc, 368537964bcSDarrick J. Wong struct xfs_btree_cur *cur, 369537964bcSDarrick J. Wong xfs_scrub_btree_rec_fn scrub_fn, 370537964bcSDarrick J. Wong struct xfs_owner_info *oinfo, 371537964bcSDarrick J. Wong void *private) 372537964bcSDarrick J. Wong { 373cc3e0948SDarrick J. Wong struct xfs_scrub_btree bs = {0}; 374cc3e0948SDarrick J. Wong union xfs_btree_ptr ptr; 375cc3e0948SDarrick J. Wong union xfs_btree_ptr *pp; 37637f3fa7fSDarrick J. Wong union xfs_btree_rec *recp; 377cc3e0948SDarrick J. Wong struct xfs_btree_block *block; 378cc3e0948SDarrick J. Wong int level; 379cc3e0948SDarrick J. Wong struct xfs_buf *bp; 380cc3e0948SDarrick J. Wong int i; 381cc3e0948SDarrick J. Wong int error = 0; 382537964bcSDarrick J. Wong 383cc3e0948SDarrick J. Wong /* Initialize scrub state */ 384cc3e0948SDarrick J. Wong bs.cur = cur; 385cc3e0948SDarrick J. Wong bs.scrub_rec = scrub_fn; 386cc3e0948SDarrick J. Wong bs.oinfo = oinfo; 387cc3e0948SDarrick J. Wong bs.firstrec = true; 388cc3e0948SDarrick J. Wong bs.private = private; 389cc3e0948SDarrick J. Wong bs.sc = sc; 390cc3e0948SDarrick J. Wong for (i = 0; i < XFS_BTREE_MAXLEVELS; i++) 391cc3e0948SDarrick J. Wong bs.firstkey[i] = true; 392cc3e0948SDarrick J. Wong INIT_LIST_HEAD(&bs.to_check); 393cc3e0948SDarrick J. Wong 394cc3e0948SDarrick J. Wong /* Don't try to check a tree with a height we can't handle. */ 395cc3e0948SDarrick J. Wong if (cur->bc_nlevels > XFS_BTREE_MAXLEVELS) { 396cc3e0948SDarrick J. Wong xfs_scrub_btree_set_corrupt(sc, cur, 0); 397cc3e0948SDarrick J. Wong goto out; 398cc3e0948SDarrick J. Wong } 399cc3e0948SDarrick J. Wong 400cc3e0948SDarrick J. Wong /* 401cc3e0948SDarrick J. Wong * Load the root of the btree. The helper function absorbs 402cc3e0948SDarrick J. Wong * error codes for us. 403cc3e0948SDarrick J. Wong */ 404cc3e0948SDarrick J. Wong level = cur->bc_nlevels - 1; 405cc3e0948SDarrick J. Wong cur->bc_ops->init_ptr_from_cur(cur, &ptr); 406cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_ptr_ok(&bs, cur->bc_nlevels, &ptr)) 407cc3e0948SDarrick J. Wong goto out; 408cc3e0948SDarrick J. Wong error = xfs_scrub_btree_get_block(&bs, level, &ptr, &block, &bp); 409cc3e0948SDarrick J. Wong if (error || !block) 410cc3e0948SDarrick J. Wong goto out; 411cc3e0948SDarrick J. Wong 412cc3e0948SDarrick J. Wong cur->bc_ptrs[level] = 1; 413cc3e0948SDarrick J. Wong 414cc3e0948SDarrick J. Wong while (level < cur->bc_nlevels) { 415cc3e0948SDarrick J. Wong block = xfs_btree_get_block(cur, level, &bp); 416cc3e0948SDarrick J. Wong 417cc3e0948SDarrick J. Wong if (level == 0) { 418cc3e0948SDarrick J. Wong /* End of leaf, pop back towards the root. */ 419cc3e0948SDarrick J. Wong if (cur->bc_ptrs[level] > 420cc3e0948SDarrick J. Wong be16_to_cpu(block->bb_numrecs)) { 421cc3e0948SDarrick J. Wong if (level < cur->bc_nlevels - 1) 422cc3e0948SDarrick J. Wong cur->bc_ptrs[level + 1]++; 423cc3e0948SDarrick J. Wong level++; 424cc3e0948SDarrick J. Wong continue; 425cc3e0948SDarrick J. Wong } 426cc3e0948SDarrick J. Wong 42737f3fa7fSDarrick J. Wong /* Records in order for scrub? */ 42837f3fa7fSDarrick J. Wong xfs_scrub_btree_rec(&bs); 42937f3fa7fSDarrick J. Wong 43037f3fa7fSDarrick J. Wong /* Call out to the record checker. */ 43137f3fa7fSDarrick J. Wong recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); 43237f3fa7fSDarrick J. Wong error = bs.scrub_rec(&bs, recp); 43337f3fa7fSDarrick J. Wong if (error) 43437f3fa7fSDarrick J. Wong break; 43537f3fa7fSDarrick J. Wong if (xfs_scrub_should_terminate(sc, &error) || 43637f3fa7fSDarrick J. Wong (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT)) 437cc3e0948SDarrick J. Wong break; 438cc3e0948SDarrick J. Wong 439cc3e0948SDarrick J. Wong cur->bc_ptrs[level]++; 440cc3e0948SDarrick J. Wong continue; 441cc3e0948SDarrick J. Wong } 442cc3e0948SDarrick J. Wong 443cc3e0948SDarrick J. Wong /* End of node, pop back towards the root. */ 444cc3e0948SDarrick J. Wong if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { 445cc3e0948SDarrick J. Wong if (level < cur->bc_nlevels - 1) 446cc3e0948SDarrick J. Wong cur->bc_ptrs[level + 1]++; 447cc3e0948SDarrick J. Wong level++; 448cc3e0948SDarrick J. Wong continue; 449cc3e0948SDarrick J. Wong } 450cc3e0948SDarrick J. Wong 45137f3fa7fSDarrick J. Wong /* Keys in order for scrub? */ 45237f3fa7fSDarrick J. Wong xfs_scrub_btree_key(&bs, level); 45337f3fa7fSDarrick J. Wong 454cc3e0948SDarrick J. Wong /* Drill another level deeper. */ 455cc3e0948SDarrick J. Wong pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); 456cc3e0948SDarrick J. Wong if (!xfs_scrub_btree_ptr_ok(&bs, level, pp)) { 457cc3e0948SDarrick J. Wong cur->bc_ptrs[level]++; 458cc3e0948SDarrick J. Wong continue; 459cc3e0948SDarrick J. Wong } 460cc3e0948SDarrick J. Wong level--; 461cc3e0948SDarrick J. Wong error = xfs_scrub_btree_get_block(&bs, level, pp, &block, &bp); 462cc3e0948SDarrick J. Wong if (error || !block) 463cc3e0948SDarrick J. Wong goto out; 464cc3e0948SDarrick J. Wong 465cc3e0948SDarrick J. Wong cur->bc_ptrs[level] = 1; 466cc3e0948SDarrick J. Wong } 467cc3e0948SDarrick J. Wong 468cc3e0948SDarrick J. Wong out: 469537964bcSDarrick J. Wong return error; 470537964bcSDarrick J. Wong } 471