fs/xfs/scrub/btree.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Copyright (C) 2017-2023 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <djwong@kernel.org>
   5  */
   6 #include "xfs.h"
   7 #include "xfs_fs.h"
   8 #include "xfs_shared.h"
   9 #include "xfs_format.h"
  10 #include "xfs_trans_resv.h"
  11 #include "xfs_mount.h"
  12 #include "xfs_inode.h"
  13 #include "xfs_btree.h"
  14 #include "scrub/scrub.h"
  15 #include "scrub/common.h"
  16 #include "scrub/btree.h"
  17 #include "scrub/trace.h"
  18
  19 /* btree scrubbing */
  20
  21 /*
  22  * Check for btree operation errors.  See the section about handling
  23  * operational errors in common.c.
  24  */
  25 static bool
  26 __xchk_btree_process_error(
  27         struct xfs_scrub        *sc,
  28         struct xfs_btree_cur    *cur,
  29         int                     level,
  30         int                     *error,
  31         __u32                   errflag,
  32         void                    *ret_ip)
  33 {
  34         if (*error == 0)
  35                 return true;
  36
  37         switch (*error) {
  38         case -EDEADLOCK:
  39         case -ECHRNG:
  40                 /* Used to restart an op with deadlock avoidance. */
  41                 trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
  42                 break;
  43         case -EFSBADCRC:
  44         case -EFSCORRUPTED:
  45                 /* Note the badness but don't abort. */
  46                 sc->sm->sm_flags |= errflag;
  47                 *error = 0;
  48                 fallthrough;
  49         default:
  50                 if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE)
  51                         trace_xchk_ifork_btree_op_error(sc, cur, level,
  52                                         *error, ret_ip);
  53                 else
  54                         trace_xchk_btree_op_error(sc, cur, level,
  55                                         *error, ret_ip);
  56                 break;
  57         }
  58         return false;
  59 }
  60
  61 bool
  62 xchk_btree_process_error(
  63         struct xfs_scrub        *sc,
  64         struct xfs_btree_cur    *cur,
  65         int                     level,
  66         int                     *error)
  67 {
  68         return __xchk_btree_process_error(sc, cur, level, error,
  69                         XFS_SCRUB_OFLAG_CORRUPT, __return_address);
  70 }
  71
  72 bool
  73 xchk_btree_xref_process_error(
  74         struct xfs_scrub        *sc,
  75         struct xfs_btree_cur    *cur,
  76         int                     level,
  77         int                     *error)
  78 {
  79         return __xchk_btree_process_error(sc, cur, level, error,
  80                         XFS_SCRUB_OFLAG_XFAIL, __return_address);
  81 }
  82
  83 /* Record btree block corruption. */
  84 static void
  85 __xchk_btree_set_corrupt(
  86         struct xfs_scrub        *sc,
  87         struct xfs_btree_cur    *cur,
  88         int                     level,
  89         __u32                   errflag,
  90         void                    *ret_ip)
  91 {
  92         sc->sm->sm_flags |= errflag;
  93
  94         if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE)
  95                 trace_xchk_ifork_btree_error(sc, cur, level,
  96                                 ret_ip);
  97         else
  98                 trace_xchk_btree_error(sc, cur, level,
  99                                 ret_ip);
 100 }
 101
 102 void
 103 xchk_btree_set_corrupt(
 104         struct xfs_scrub        *sc,
 105         struct xfs_btree_cur    *cur,
 106         int                     level)
 107 {
 108         __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT,
 109                         __return_address);
 110 }
 111
 112 void
 113 xchk_btree_xref_set_corrupt(
 114         struct xfs_scrub        *sc,
 115         struct xfs_btree_cur    *cur,
 116         int                     level)
 117 {
 118         __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT,
 119                         __return_address);
 120 }
 121
 122 void
 123 xchk_btree_set_preen(
 124         struct xfs_scrub        *sc,
 125         struct xfs_btree_cur    *cur,
 126         int                     level)
 127 {
 128         __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_PREEN,
 129                         __return_address);
 130 }
 131
 132 /*
 133  * Make sure this record is in order and doesn't stray outside of the parent
 134  * keys.
 135  */
 136 STATIC void
 137 xchk_btree_rec(
 138         struct xchk_btree       *bs)
 139 {
 140         struct xfs_btree_cur    *cur = bs->cur;
 141         union xfs_btree_rec     *rec;
 142         union xfs_btree_key     key;
 143         union xfs_btree_key     hkey;
 144         union xfs_btree_key     *keyp;
 145         struct xfs_btree_block  *block;
 146         struct xfs_btree_block  *keyblock;
 147         struct xfs_buf          *bp;
 148
 149         block = xfs_btree_get_block(cur, 0, &bp);
 150         rec = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, block);
 151
 152         trace_xchk_btree_rec(bs->sc, cur, 0);
 153
 154         /* Are all records across all record blocks in order? */
 155         if (bs->lastrec_valid &&
 156             !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
 157                 xchk_btree_set_corrupt(bs->sc, cur, 0);
 158         memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);
 159         bs->lastrec_valid = true;
 160
 161         if (cur->bc_nlevels == 1)
 162                 return;
 163
 164         /* Is low_key(rec) at least as large as the parent low key? */
 165         cur->bc_ops->init_key_from_rec(&key, rec);
 166         keyblock = xfs_btree_get_block(cur, 1, &bp);
 167         keyp = xfs_btree_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
 168         if (xfs_btree_keycmp_lt(cur, &key, keyp))
 169                 xchk_btree_set_corrupt(bs->sc, cur, 1);
 170
 171         if (!(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING))
 172                 return;
 173
 174         /* Is high_key(rec) no larger than the parent high key? */
 175         cur->bc_ops->init_high_key_from_rec(&hkey, rec);
 176         keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
 177         if (xfs_btree_keycmp_lt(cur, keyp, &hkey))
 178                 xchk_btree_set_corrupt(bs->sc, cur, 1);
 179 }
 180
 181 /*
 182  * Make sure this key is in order and doesn't stray outside of the parent
 183  * keys.
 184  */
 185 STATIC void
 186 xchk_btree_key(
 187         struct xchk_btree       *bs,
 188         int                     level)
 189 {
 190         struct xfs_btree_cur    *cur = bs->cur;
 191         union xfs_btree_key     *key;
 192         union xfs_btree_key     *keyp;
 193         struct xfs_btree_block  *block;
 194         struct xfs_btree_block  *keyblock;
 195         struct xfs_buf          *bp;
 196
 197         block = xfs_btree_get_block(cur, level, &bp);
 198         key = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block);
 199
 200         trace_xchk_btree_key(bs->sc, cur, level);
 201
 202         /* Are all low keys across all node blocks in order? */
 203         if (bs->lastkey[level - 1].valid &&
 204             !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level - 1].key, key))
 205                 xchk_btree_set_corrupt(bs->sc, cur, level);
 206         memcpy(&bs->lastkey[level - 1].key, key, cur->bc_ops->key_len);
 207         bs->lastkey[level - 1].valid = true;
 208
 209         if (level + 1 >= cur->bc_nlevels)
 210                 return;
 211
 212         /* Is this block's low key at least as large as the parent low key? */
 213         keyblock = xfs_btree_get_block(cur, level + 1, &bp);
 214         keyp = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, keyblock);
 215         if (xfs_btree_keycmp_lt(cur, key, keyp))
 216                 xchk_btree_set_corrupt(bs->sc, cur, level);
 217
 218         if (!(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING))
 219                 return;
 220
 221         /* Is this block's high key no larger than the parent high key? */
 222         key = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr, block);
 223         keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
 224                         keyblock);
 225         if (xfs_btree_keycmp_lt(cur, keyp, key))
 226                 xchk_btree_set_corrupt(bs->sc, cur, level);
 227 }
 228
 229 /*
 230  * Check a btree pointer.  Returns true if it's ok to use this pointer.
 231  * Callers do not need to set the corrupt flag.
 232  */
 233 static bool
 234 xchk_btree_ptr_ok(
 235         struct xchk_btree       *bs,
 236         int                     level,
 237         union xfs_btree_ptr     *ptr)
 238 {
 239         /* A btree rooted in an inode has no block pointer to the root. */
 240         if (bs->cur->bc_ops->type == XFS_BTREE_TYPE_INODE &&
 241             level == bs->cur->bc_nlevels)
 242                 return true;
 243
 244         /* Otherwise, check the pointers. */
 245         if (__xfs_btree_check_ptr(bs->cur, ptr, 0, level)) {
 246                 xchk_btree_set_corrupt(bs->sc, bs->cur, level);
 247                 return false;
 248         }
 249
 250         return true;
 251 }
 252
 253 /* Check that a btree block's sibling matches what we expect it. */
 254 STATIC int
 255 xchk_btree_block_check_sibling(
 256         struct xchk_btree       *bs,
 257         int                     level,
 258         int                     direction,
 259         union xfs_btree_ptr     *sibling)
 260 {
 261         struct xfs_btree_cur    *cur = bs->cur;
 262         struct xfs_btree_block  *pblock;
 263         struct xfs_buf          *pbp;
 264         struct xfs_btree_cur    *ncur = NULL;
 265         union xfs_btree_ptr     *pp;
 266         int                     success;
 267         int                     error;
 268
 269         error = xfs_btree_dup_cursor(cur, &ncur);
 270         if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
 271             !ncur)
 272                 return error;
 273
 274         /*
 275          * If the pointer is null, we shouldn't be able to move the upper
 276          * level pointer anywhere.
 277          */
 278         if (xfs_btree_ptr_is_null(cur, sibling)) {
 279                 if (direction > 0)
 280                         error = xfs_btree_increment(ncur, level + 1, &success);
 281                 else
 282                         error = xfs_btree_decrement(ncur, level + 1, &success);
 283                 if (error == 0 && success)
 284                         xchk_btree_set_corrupt(bs->sc, cur, level);
 285                 error = 0;
 286                 goto out;
 287         }
 288
 289         /* Increment upper level pointer. */
 290         if (direction > 0)
 291                 error = xfs_btree_increment(ncur, level + 1, &success);
 292         else
 293                 error = xfs_btree_decrement(ncur, level + 1, &success);
 294         if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
 295                 goto out;
 296         if (!success) {
 297                 xchk_btree_set_corrupt(bs->sc, cur, level + 1);
 298                 goto out;
 299         }
 300
 301         /* Compare upper level pointer to sibling pointer. */
 302         pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
 303         pp = xfs_btree_ptr_addr(ncur, ncur->bc_levels[level + 1].ptr, pblock);
 304         if (!xchk_btree_ptr_ok(bs, level + 1, pp))
 305                 goto out;
 306         if (pbp)
 307                 xchk_buffer_recheck(bs->sc, pbp);
 308
 309         if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
 310                 xchk_btree_set_corrupt(bs->sc, cur, level);
 311 out:
 312         xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
 313         return error;
 314 }
 315
 316 /* Check the siblings of a btree block. */
 317 STATIC int
 318 xchk_btree_block_check_siblings(
 319         struct xchk_btree       *bs,
 320         struct xfs_btree_block  *block)
 321 {
 322         struct xfs_btree_cur    *cur = bs->cur;
 323         union xfs_btree_ptr     leftsib;
 324         union xfs_btree_ptr     rightsib;
 325         int                     level;
 326         int                     error = 0;
 327
 328         xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
 329         xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
 330         level = xfs_btree_get_level(block);
 331
 332         /* Root block should never have siblings. */
 333         if (level == cur->bc_nlevels - 1) {
 334                 if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
 335                     !xfs_btree_ptr_is_null(cur, &rightsib))
 336                         xchk_btree_set_corrupt(bs->sc, cur, level);
 337                 goto out;
 338         }
 339
 340         /*
 341          * Does the left & right sibling pointers match the adjacent
 342          * parent level pointers?
 343          * (These function absorbs error codes for us.)
 344          */
 345         error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
 346         if (error)
 347                 return error;
 348         error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
 349         if (error)
 350                 return error;
 351 out:
 352         return error;
 353 }
 354
 355 struct check_owner {
 356         struct list_head        list;
 357         xfs_daddr_t             daddr;
 358         int                     level;
 359 };
 360
 361 /*
 362  * Make sure this btree block isn't in the free list and that there's
 363  * an rmap record for it.
 364  */
 365 STATIC int
 366 xchk_btree_check_block_owner(
 367         struct xchk_btree       *bs,
 368         int                     level,
 369         xfs_daddr_t             daddr)
 370 {
 371         xfs_agnumber_t          agno;
 372         xfs_agblock_t           agbno;
 373         bool                    init_sa;
 374         int                     error = 0;
 375
 376         if (!bs->cur)
 377                 return 0;
 378
 379         agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
 380         agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);
 381
 382         /*
 383          * If the btree being examined is not itself a per-AG btree, initialize
 384          * sc->sa so that we can check for the presence of an ownership record
 385          * in the rmap btree for the AG containing the block.
 386          */
 387         init_sa = bs->cur->bc_ops->type != XFS_BTREE_TYPE_AG;
 388         if (init_sa) {
 389                 error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa);
 390                 if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
 391                                 level, &error))
 392                         goto out_free;
 393         }
 394
 395         xchk_xref_is_used_space(bs->sc, agbno, 1);
 396         /*
 397          * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we
 398          * have to nullify it (to shut down further block owner checks) if
 399          * self-xref encounters problems.
 400          */
 401         if (!bs->sc->sa.bno_cur && xfs_btree_is_bno(bs->cur->bc_ops))
 402                 bs->cur = NULL;
 403
 404         xchk_xref_is_only_owned_by(bs->sc, agbno, 1, bs->oinfo);
 405         if (!bs->sc->sa.rmap_cur && xfs_btree_is_rmap(bs->cur->bc_ops))
 406                 bs->cur = NULL;
 407
 408 out_free:
 409         if (init_sa)
 410                 xchk_ag_free(bs->sc, &bs->sc->sa);
 411
 412         return error;
 413 }
 414
 415 /* Check the owner of a btree block. */
 416 STATIC int
 417 xchk_btree_check_owner(
 418         struct xchk_btree       *bs,
 419         int                     level,
 420         struct xfs_buf          *bp)
 421 {
 422         struct xfs_btree_cur    *cur = bs->cur;
 423
 424         /*
 425          * In theory, xfs_btree_get_block should only give us a null buffer
 426          * pointer for the root of a root-in-inode btree type, but we need
 427          * to check defensively here in case the cursor state is also screwed
 428          * up.
 429          */
 430         if (bp == NULL) {
 431                 if (cur->bc_ops->type != XFS_BTREE_TYPE_INODE)
 432                         xchk_btree_set_corrupt(bs->sc, bs->cur, level);
 433                 return 0;
 434         }
 435
 436         /*
 437          * We want to cross-reference each btree block with the bnobt
 438          * and the rmapbt.  We cannot cross-reference the bnobt or
 439          * rmapbt while scanning the bnobt or rmapbt, respectively,
 440          * because we cannot alter the cursor and we'd prefer not to
 441          * duplicate cursors.  Therefore, save the buffer daddr for
 442          * later scanning.
 443          */
 444         if (xfs_btree_is_bno(cur->bc_ops) || xfs_btree_is_rmap(cur->bc_ops)) {
 445                 struct check_owner      *co;
 446
 447                 co = kmalloc(sizeof(struct check_owner), XCHK_GFP_FLAGS);
 448                 if (!co)
 449                         return -ENOMEM;
 450
 451                 INIT_LIST_HEAD(&co->list);
 452                 co->level = level;
 453                 co->daddr = xfs_buf_daddr(bp);
 454                 list_add_tail(&co->list, &bs->to_check);
 455                 return 0;
 456         }
 457
 458         return xchk_btree_check_block_owner(bs, level, xfs_buf_daddr(bp));
 459 }
 460
 461 /* Decide if we want to check minrecs of a btree block in the inode root. */
 462 static inline bool
 463 xchk_btree_check_iroot_minrecs(
 464         struct xchk_btree       *bs)
 465 {
 466         /*
 467          * xfs_bmap_add_attrfork_btree had an implementation bug wherein it
 468          * would miscalculate the space required for the data fork bmbt root
 469          * when adding an attr fork, and promote the iroot contents to an
 470          * external block unnecessarily.  This went unnoticed for many years
 471          * until scrub found filesystems in this state.  Inode rooted btrees are
 472          * not supposed to have immediate child blocks that are small enough
 473          * that the contents could fit in the inode root, but we can't fail
 474          * existing filesystems, so instead we disable the check for data fork
 475          * bmap btrees when there's an attr fork.
 476          */
 477         if (xfs_btree_is_bmap(bs->cur->bc_ops) &&
 478             bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&
 479             xfs_inode_has_attr_fork(bs->sc->ip))
 480                 return false;
 481
 482         return true;
 483 }
 484
 485 /*
 486  * Check that this btree block has at least minrecs records or is one of the
 487  * special blocks that don't require that.
 488  */
 489 STATIC void
 490 xchk_btree_check_minrecs(
 491         struct xchk_btree       *bs,
 492         int                     level,
 493         struct xfs_btree_block  *block)
 494 {
 495         struct xfs_btree_cur    *cur = bs->cur;
 496         unsigned int            root_level = cur->bc_nlevels - 1;
 497         unsigned int            numrecs = be16_to_cpu(block->bb_numrecs);
 498
 499         /* More records than minrecs means the block is ok. */
 500         if (numrecs >= cur->bc_ops->get_minrecs(cur, level))
 501                 return;
 502
 503         /*
 504          * For btrees rooted in the inode, it's possible that the root block
 505          * contents spilled into a regular ondisk block because there wasn't
 506          * enough space in the inode root.  The number of records in that
 507          * child block might be less than the standard minrecs, but that's ok
 508          * provided that there's only one direct child of the root.
 509          */
 510         if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE &&
 511             level == cur->bc_nlevels - 2) {
 512                 struct xfs_btree_block  *root_block;
 513                 struct xfs_buf          *root_bp;
 514                 int                     root_maxrecs;
 515
 516                 root_block = xfs_btree_get_block(cur, root_level, &root_bp);
 517                 root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);
 518                 if (xchk_btree_check_iroot_minrecs(bs) &&
 519                     (be16_to_cpu(root_block->bb_numrecs) != 1 ||
 520                      numrecs <= root_maxrecs))
 521                         xchk_btree_set_corrupt(bs->sc, cur, level);
 522                 return;
 523         }
 524
 525         /*
 526          * Otherwise, only the root level is allowed to have fewer than minrecs
 527          * records or keyptrs.
 528          */
 529         if (level < root_level)
 530                 xchk_btree_set_corrupt(bs->sc, cur, level);
 531 }
 532
 533 /*
 534  * If this btree block has a parent, make sure that the parent's keys capture
 535  * the keyspace contained in this block.
 536  */
 537 STATIC void
 538 xchk_btree_block_check_keys(
 539         struct xchk_btree       *bs,
 540         int                     level,
 541         struct xfs_btree_block  *block)
 542 {
 543         union xfs_btree_key     block_key;
 544         union xfs_btree_key     *block_high_key;
 545         union xfs_btree_key     *parent_low_key, *parent_high_key;
 546         struct xfs_btree_cur    *cur = bs->cur;
 547         struct xfs_btree_block  *parent_block;
 548         struct xfs_buf          *bp;
 549
 550         if (level == cur->bc_nlevels - 1)
 551                 return;
 552
 553         xfs_btree_get_keys(cur, block, &block_key);
 554
 555         /* Make sure the low key of this block matches the parent. */
 556         parent_block = xfs_btree_get_block(cur, level + 1, &bp);
 557         parent_low_key = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
 558                         parent_block);
 559         if (xfs_btree_keycmp_ne(cur, &block_key, parent_low_key)) {
 560                 xchk_btree_set_corrupt(bs->sc, bs->cur, level);
 561                 return;
 562         }
 563
 564         if (!(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING))
 565                 return;
 566
 567         /* Make sure the high key of this block matches the parent. */
 568         parent_high_key = xfs_btree_high_key_addr(cur,
 569                         cur->bc_levels[level + 1].ptr, parent_block);
 570         block_high_key = xfs_btree_high_key_from_key(cur, &block_key);
 571         if (xfs_btree_keycmp_ne(cur, block_high_key, parent_high_key))
 572                 xchk_btree_set_corrupt(bs->sc, bs->cur, level);
 573 }
 574
 575 /*
 576  * Grab and scrub a btree block given a btree pointer.  Returns block
 577  * and buffer pointers (if applicable) if they're ok to use.
 578  */
 579 STATIC int
 580 xchk_btree_get_block(
 581         struct xchk_btree       *bs,
 582         int                     level,
 583         union xfs_btree_ptr     *pp,
 584         struct xfs_btree_block  **pblock,
 585         struct xfs_buf          **pbp)
 586 {
 587         int                     error;
 588
 589         *pblock = NULL;
 590         *pbp = NULL;
 591
 592         error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
 593         if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
 594             !*pblock)
 595                 return error;
 596
 597         xfs_btree_get_block(bs->cur, level, pbp);
 598         if (__xfs_btree_check_block(bs->cur, *pblock, level, *pbp)) {
 599                 xchk_btree_set_corrupt(bs->sc, bs->cur, level);
 600                 return 0;
 601         }
 602         if (*pbp)
 603                 xchk_buffer_recheck(bs->sc, *pbp);
 604
 605         xchk_btree_check_minrecs(bs, level, *pblock);
 606
 607         /*
 608          * Check the block's owner; this function absorbs error codes
 609          * for us.
 610          */
 611         error = xchk_btree_check_owner(bs, level, *pbp);
 612         if (error)
 613                 return error;
 614
 615         /*
 616          * Check the block's siblings; this function absorbs error codes
 617          * for us.
 618          */
 619         error = xchk_btree_block_check_siblings(bs, *pblock);
 620         if (error)
 621                 return error;
 622
 623         xchk_btree_block_check_keys(bs, level, *pblock);
 624         return 0;
 625 }
 626
 627 /*
 628  * Check that the low and high keys of this block match the keys stored
 629  * in the parent block.
 630  */
 631 STATIC void
 632 xchk_btree_block_keys(
 633         struct xchk_btree       *bs,
 634         int                     level,
 635         struct xfs_btree_block  *block)
 636 {
 637         union xfs_btree_key     block_keys;
 638         struct xfs_btree_cur    *cur = bs->cur;
 639         union xfs_btree_key     *high_bk;
 640         union xfs_btree_key     *parent_keys;
 641         union xfs_btree_key     *high_pk;
 642         struct xfs_btree_block  *parent_block;
 643         struct xfs_buf          *bp;
 644
 645         if (level >= cur->bc_nlevels - 1)
 646                 return;
 647
 648         /* Calculate the keys for this block. */
 649         xfs_btree_get_keys(cur, block, &block_keys);
 650
 651         /* Obtain the parent's copy of the keys for this block. */
 652         parent_block = xfs_btree_get_block(cur, level + 1, &bp);
 653         parent_keys = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
 654                         parent_block);
 655
 656         if (xfs_btree_keycmp_ne(cur, &block_keys, parent_keys))
 657                 xchk_btree_set_corrupt(bs->sc, cur, 1);
 658
 659         if (!(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING))
 660                 return;
 661
 662         /* Get high keys */
 663         high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
 664         high_pk = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
 665                         parent_block);
 666
 667         if (xfs_btree_keycmp_ne(cur, high_bk, high_pk))
 668                 xchk_btree_set_corrupt(bs->sc, cur, 1);
 669 }
 670
 671 /*
 672  * Visit all nodes and leaves of a btree.  Check that all pointers and
 673  * records are in order, that the keys reflect the records, and use a callback
 674  * so that the caller can verify individual records.
 675  */
 676 int
 677 xchk_btree(
 678         struct xfs_scrub                *sc,
 679         struct xfs_btree_cur            *cur,
 680         xchk_btree_rec_fn               scrub_fn,
 681         const struct xfs_owner_info     *oinfo,
 682         void                            *private)
 683 {
 684         union xfs_btree_ptr             ptr;
 685         struct xchk_btree               *bs;
 686         union xfs_btree_ptr             *pp;
 687         union xfs_btree_rec             *recp;
 688         struct xfs_btree_block          *block;
 689         struct xfs_buf                  *bp;
 690         struct check_owner              *co;
 691         struct check_owner              *n;
 692         size_t                          cur_sz;
 693         int                             level;
 694         int                             error = 0;
 695
 696         /*
 697          * Allocate the btree scrub context from the heap, because this
 698          * structure can get rather large.  Don't let a caller feed us a
 699          * totally absurd size.
 700          */
 701         cur_sz = xchk_btree_sizeof(cur->bc_nlevels);
 702         if (cur_sz > PAGE_SIZE) {
 703                 xchk_btree_set_corrupt(sc, cur, 0);
 704                 return 0;
 705         }
 706         bs = kzalloc(cur_sz, XCHK_GFP_FLAGS);
 707         if (!bs)
 708                 return -ENOMEM;
 709         bs->cur = cur;
 710         bs->scrub_rec = scrub_fn;
 711         bs->oinfo = oinfo;
 712         bs->private = private;
 713         bs->sc = sc;
 714
 715         /* Initialize scrub state */
 716         INIT_LIST_HEAD(&bs->to_check);
 717
 718         /*
 719          * Load the root of the btree.  The helper function absorbs
 720          * error codes for us.
 721          */
 722         level = cur->bc_nlevels - 1;
 723         xfs_btree_init_ptr_from_cur(cur, &ptr);
 724         if (!xchk_btree_ptr_ok(bs, cur->bc_nlevels, &ptr))
 725                 goto out;
 726         error = xchk_btree_get_block(bs, level, &ptr, &block, &bp);
 727         if (error || !block)
 728                 goto out;
 729
 730         cur->bc_levels[level].ptr = 1;
 731
 732         while (level < cur->bc_nlevels) {
 733                 block = xfs_btree_get_block(cur, level, &bp);
 734
 735                 if (level == 0) {
 736                         /* End of leaf, pop back towards the root. */
 737                         if (cur->bc_levels[level].ptr >
 738                             be16_to_cpu(block->bb_numrecs)) {
 739                                 xchk_btree_block_keys(bs, level, block);
 740                                 if (level < cur->bc_nlevels - 1)
 741                                         cur->bc_levels[level + 1].ptr++;
 742                                 level++;
 743                                 continue;
 744                         }
 745
 746                         /* Records in order for scrub? */
 747                         xchk_btree_rec(bs);
 748
 749                         /* Call out to the record checker. */
 750                         recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr,
 751                                         block);
 752                         error = bs->scrub_rec(bs, recp);
 753                         if (error)
 754                                 break;
 755                         if (xchk_should_terminate(sc, &error) ||
 756                             (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
 757                                 break;
 758
 759                         cur->bc_levels[level].ptr++;
 760                         continue;
 761                 }
 762
 763                 /* End of node, pop back towards the root. */
 764                 if (cur->bc_levels[level].ptr >
 765                                         be16_to_cpu(block->bb_numrecs)) {
 766                         xchk_btree_block_keys(bs, level, block);
 767                         if (level < cur->bc_nlevels - 1)
 768                                 cur->bc_levels[level + 1].ptr++;
 769                         level++;
 770                         continue;
 771                 }
 772
 773                 /* Keys in order for scrub? */
 774                 xchk_btree_key(bs, level);
 775
 776                 /* Drill another level deeper. */
 777                 pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block);
 778                 if (!xchk_btree_ptr_ok(bs, level, pp)) {
 779                         cur->bc_levels[level].ptr++;
 780                         continue;
 781                 }
 782                 level--;
 783                 error = xchk_btree_get_block(bs, level, pp, &block, &bp);
 784                 if (error || !block)
 785                         goto out;
 786
 787                 cur->bc_levels[level].ptr = 1;
 788         }
 789
 790 out:
 791         /* Process deferred owner checks on btree blocks. */
 792         list_for_each_entry_safe(co, n, &bs->to_check, list) {
 793                 if (!error && bs->cur)
 794                         error = xchk_btree_check_block_owner(bs, co->level,
 795                                         co->daddr);
 796                 list_del(&co->list);
 797                 kfree(co);
 798         }
 799         kfree(bs);
 800
 801         return error;
 802 }