fs/xfs/scrub/dabtree.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Copyright (C) 2017 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <darrick.wong@oracle.com>
   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_log_format.h"
  13 #include "xfs_trans.h"
  14 #include "xfs_inode.h"
  15 #include "xfs_dir2.h"
  16 #include "xfs_dir2_priv.h"
  17 #include "xfs_attr_leaf.h"
  18 #include "scrub/scrub.h"
  19 #include "scrub/common.h"
  20 #include "scrub/trace.h"
  21 #include "scrub/dabtree.h"
  22
  23 /* Directory/Attribute Btree */
  24
  25 /*
  26  * Check for da btree operation errors.  See the section about handling
  27  * operational errors in common.c.
  28  */
  29 bool
  30 xchk_da_process_error(
  31         struct xchk_da_btree    *ds,
  32         int                     level,
  33         int                     *error)
  34 {
  35         struct xfs_scrub        *sc = ds->sc;
  36
  37         if (*error == 0)
  38                 return true;
  39
  40         switch (*error) {
  41         case -EDEADLOCK:
  42                 /* Used to restart an op with deadlock avoidance. */
  43                 trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
  44                 break;
  45         case -EFSBADCRC:
  46         case -EFSCORRUPTED:
  47                 /* Note the badness but don't abort. */
  48                 sc->sm->sm_flags |= XFS_SCRUB_OFLAG_CORRUPT;
  49                 *error = 0;
  50                 /* fall through */
  51         default:
  52                 trace_xchk_file_op_error(sc, ds->dargs.whichfork,
  53                                 xfs_dir2_da_to_db(ds->dargs.geo,
  54                                         ds->state->path.blk[level].blkno),
  55                                 *error, __return_address);
  56                 break;
  57         }
  58         return false;
  59 }
  60
  61 /*
  62  * Check for da btree corruption.  See the section about handling
  63  * operational errors in common.c.
  64  */
  65 void
  66 xchk_da_set_corrupt(
  67         struct xchk_da_btree    *ds,
  68         int                     level)
  69 {
  70         struct xfs_scrub        *sc = ds->sc;
  71
  72         sc->sm->sm_flags |= XFS_SCRUB_OFLAG_CORRUPT;
  73
  74         trace_xchk_fblock_error(sc, ds->dargs.whichfork,
  75                         xfs_dir2_da_to_db(ds->dargs.geo,
  76                                 ds->state->path.blk[level].blkno),
  77                         __return_address);
  78 }
  79
  80 /* Find an entry at a certain level in a da btree. */
  81 STATIC void *
  82 xchk_da_btree_entry(
  83         struct xchk_da_btree    *ds,
  84         int                     level,
  85         int                     rec)
  86 {
  87         char                    *ents;
  88         struct xfs_da_state_blk *blk;
  89         void                    *baddr;
  90
  91         /* Dispatch the entry finding function. */
  92         blk = &ds->state->path.blk[level];
  93         baddr = blk->bp->b_addr;
  94         switch (blk->magic) {
  95         case XFS_ATTR_LEAF_MAGIC:
  96         case XFS_ATTR3_LEAF_MAGIC:
  97                 ents = (char *)xfs_attr3_leaf_entryp(baddr);
  98                 return ents + (rec * sizeof(struct xfs_attr_leaf_entry));
  99         case XFS_DIR2_LEAFN_MAGIC:
 100         case XFS_DIR3_LEAFN_MAGIC:
 101                 ents = (char *)ds->dargs.dp->d_ops->leaf_ents_p(baddr);
 102                 return ents + (rec * sizeof(struct xfs_dir2_leaf_entry));
 103         case XFS_DIR2_LEAF1_MAGIC:
 104         case XFS_DIR3_LEAF1_MAGIC:
 105                 ents = (char *)ds->dargs.dp->d_ops->leaf_ents_p(baddr);
 106                 return ents + (rec * sizeof(struct xfs_dir2_leaf_entry));
 107         case XFS_DA_NODE_MAGIC:
 108         case XFS_DA3_NODE_MAGIC:
 109                 ents = (char *)ds->dargs.dp->d_ops->node_tree_p(baddr);
 110                 return ents + (rec * sizeof(struct xfs_da_node_entry));
 111         }
 112
 113         return NULL;
 114 }
 115
 116 /* Scrub a da btree hash (key). */
 117 int
 118 xchk_da_btree_hash(
 119         struct xchk_da_btree            *ds,
 120         int                             level,
 121         __be32                          *hashp)
 122 {
 123         struct xfs_da_state_blk         *blks;
 124         struct xfs_da_node_entry        *entry;
 125         xfs_dahash_t                    hash;
 126         xfs_dahash_t                    parent_hash;
 127
 128         /* Is this hash in order? */
 129         hash = be32_to_cpu(*hashp);
 130         if (hash < ds->hashes[level])
 131                 xchk_da_set_corrupt(ds, level);
 132         ds->hashes[level] = hash;
 133
 134         if (level == 0)
 135                 return 0;
 136
 137         /* Is this hash no larger than the parent hash? */
 138         blks = ds->state->path.blk;
 139         entry = xchk_da_btree_entry(ds, level - 1, blks[level - 1].index);
 140         parent_hash = be32_to_cpu(entry->hashval);
 141         if (parent_hash < hash)
 142                 xchk_da_set_corrupt(ds, level);
 143
 144         return 0;
 145 }
 146
 147 /*
 148  * Check a da btree pointer.  Returns true if it's ok to use this
 149  * pointer.
 150  */
 151 STATIC bool
 152 xchk_da_btree_ptr_ok(
 153         struct xchk_da_btree    *ds,
 154         int                     level,
 155         xfs_dablk_t             blkno)
 156 {
 157         if (blkno < ds->lowest || (ds->highest != 0 && blkno >= ds->highest)) {
 158                 xchk_da_set_corrupt(ds, level);
 159                 return false;
 160         }
 161
 162         return true;
 163 }
 164
 165 /*
 166  * The da btree scrubber can handle leaf1 blocks as a degenerate
 167  * form of leafn blocks.  Since the regular da code doesn't handle
 168  * leaf1, we must multiplex the verifiers.
 169  */
 170 static void
 171 xchk_da_btree_read_verify(
 172         struct xfs_buf          *bp)
 173 {
 174         struct xfs_da_blkinfo   *info = bp->b_addr;
 175
 176         switch (be16_to_cpu(info->magic)) {
 177         case XFS_DIR2_LEAF1_MAGIC:
 178         case XFS_DIR3_LEAF1_MAGIC:
 179                 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
 180                 bp->b_ops->verify_read(bp);
 181                 return;
 182         default:
 183                 /*
 184                  * xfs_da3_node_buf_ops already know how to handle
 185                  * DA*_NODE, ATTR*_LEAF, and DIR*_LEAFN blocks.
 186                  */
 187                 bp->b_ops = &xfs_da3_node_buf_ops;
 188                 bp->b_ops->verify_read(bp);
 189                 return;
 190         }
 191 }
 192 static void
 193 xchk_da_btree_write_verify(
 194         struct xfs_buf          *bp)
 195 {
 196         struct xfs_da_blkinfo   *info = bp->b_addr;
 197
 198         switch (be16_to_cpu(info->magic)) {
 199         case XFS_DIR2_LEAF1_MAGIC:
 200         case XFS_DIR3_LEAF1_MAGIC:
 201                 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
 202                 bp->b_ops->verify_write(bp);
 203                 return;
 204         default:
 205                 /*
 206                  * xfs_da3_node_buf_ops already know how to handle
 207                  * DA*_NODE, ATTR*_LEAF, and DIR*_LEAFN blocks.
 208                  */
 209                 bp->b_ops = &xfs_da3_node_buf_ops;
 210                 bp->b_ops->verify_write(bp);
 211                 return;
 212         }
 213 }
 214 static void *
 215 xchk_da_btree_verify(
 216         struct xfs_buf          *bp)
 217 {
 218         struct xfs_da_blkinfo   *info = bp->b_addr;
 219
 220         switch (be16_to_cpu(info->magic)) {
 221         case XFS_DIR2_LEAF1_MAGIC:
 222         case XFS_DIR3_LEAF1_MAGIC:
 223                 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
 224                 return bp->b_ops->verify_struct(bp);
 225         default:
 226                 bp->b_ops = &xfs_da3_node_buf_ops;
 227                 return bp->b_ops->verify_struct(bp);
 228         }
 229 }
 230
 231 static const struct xfs_buf_ops xchk_da_btree_buf_ops = {
 232         .name = "xchk_da_btree",
 233         .verify_read = xchk_da_btree_read_verify,
 234         .verify_write = xchk_da_btree_write_verify,
 235         .verify_struct = xchk_da_btree_verify,
 236 };
 237
 238 /* Check a block's sibling. */
 239 STATIC int
 240 xchk_da_btree_block_check_sibling(
 241         struct xchk_da_btree    *ds,
 242         int                     level,
 243         int                     direction,
 244         xfs_dablk_t             sibling)
 245 {
 246         int                     retval;
 247         int                     error;
 248
 249         memcpy(&ds->state->altpath, &ds->state->path,
 250                         sizeof(ds->state->altpath));
 251
 252         /*
 253          * If the pointer is null, we shouldn't be able to move the upper
 254          * level pointer anywhere.
 255          */
 256         if (sibling == 0) {
 257                 error = xfs_da3_path_shift(ds->state, &ds->state->altpath,
 258                                 direction, false, &retval);
 259                 if (error == 0 && retval == 0)
 260                         xchk_da_set_corrupt(ds, level);
 261                 error = 0;
 262                 goto out;
 263         }
 264
 265         /* Move the alternate cursor one block in the direction given. */
 266         error = xfs_da3_path_shift(ds->state, &ds->state->altpath,
 267                         direction, false, &retval);
 268         if (!xchk_da_process_error(ds, level, &error))
 269                 return error;
 270         if (retval) {
 271                 xchk_da_set_corrupt(ds, level);
 272                 return error;
 273         }
 274         if (ds->state->altpath.blk[level].bp)
 275                 xchk_buffer_recheck(ds->sc,
 276                                 ds->state->altpath.blk[level].bp);
 277
 278         /* Compare upper level pointer to sibling pointer. */
 279         if (ds->state->altpath.blk[level].blkno != sibling)
 280                 xchk_da_set_corrupt(ds, level);
 281         if (ds->state->altpath.blk[level].bp) {
 282                 xfs_trans_brelse(ds->dargs.trans,
 283                                 ds->state->altpath.blk[level].bp);
 284                 ds->state->altpath.blk[level].bp = NULL;
 285         }
 286 out:
 287         return error;
 288 }
 289
 290 /* Check a block's sibling pointers. */
 291 STATIC int
 292 xchk_da_btree_block_check_siblings(
 293         struct xchk_da_btree    *ds,
 294         int                     level,
 295         struct xfs_da_blkinfo   *hdr)
 296 {
 297         xfs_dablk_t             forw;
 298         xfs_dablk_t             back;
 299         int                     error = 0;
 300
 301         forw = be32_to_cpu(hdr->forw);
 302         back = be32_to_cpu(hdr->back);
 303
 304         /* Top level blocks should not have sibling pointers. */
 305         if (level == 0) {
 306                 if (forw != 0 || back != 0)
 307                         xchk_da_set_corrupt(ds, level);
 308                 return 0;
 309         }
 310
 311         /*
 312          * Check back (left) and forw (right) pointers.  These functions
 313          * absorb error codes for us.
 314          */
 315         error = xchk_da_btree_block_check_sibling(ds, level, 0, back);
 316         if (error)
 317                 goto out;
 318         error = xchk_da_btree_block_check_sibling(ds, level, 1, forw);
 319
 320 out:
 321         memset(&ds->state->altpath, 0, sizeof(ds->state->altpath));
 322         return error;
 323 }
 324
 325 /* Load a dir/attribute block from a btree. */
 326 STATIC int
 327 xchk_da_btree_block(
 328         struct xchk_da_btree            *ds,
 329         int                             level,
 330         xfs_dablk_t                     blkno)
 331 {
 332         struct xfs_da_state_blk         *blk;
 333         struct xfs_da_intnode           *node;
 334         struct xfs_da_node_entry        *btree;
 335         struct xfs_da3_blkinfo          *hdr3;
 336         struct xfs_da_args              *dargs = &ds->dargs;
 337         struct xfs_inode                *ip = ds->dargs.dp;
 338         xfs_ino_t                       owner;
 339         int                             *pmaxrecs;
 340         struct xfs_da3_icnode_hdr       nodehdr;
 341         int                             error = 0;
 342
 343         blk = &ds->state->path.blk[level];
 344         ds->state->path.active = level + 1;
 345
 346         /* Release old block. */
 347         if (blk->bp) {
 348                 xfs_trans_brelse(dargs->trans, blk->bp);
 349                 blk->bp = NULL;
 350         }
 351
 352         /* Check the pointer. */
 353         blk->blkno = blkno;
 354         if (!xchk_da_btree_ptr_ok(ds, level, blkno))
 355                 goto out_nobuf;
 356
 357         /* Read the buffer. */
 358         error = xfs_da_read_buf(dargs->trans, dargs->dp, blk->blkno, -2,
 359                         &blk->bp, dargs->whichfork,
 360                         &xchk_da_btree_buf_ops);
 361         if (!xchk_da_process_error(ds, level, &error))
 362                 goto out_nobuf;
 363         if (blk->bp)
 364                 xchk_buffer_recheck(ds->sc, blk->bp);
 365
 366         /*
 367          * We didn't find a dir btree root block, which means that
 368          * there's no LEAF1/LEAFN tree (at least not where it's supposed
 369          * to be), so jump out now.
 370          */
 371         if (ds->dargs.whichfork == XFS_DATA_FORK && level == 0 &&
 372                         blk->bp == NULL)
 373                 goto out_nobuf;
 374
 375         /* It's /not/ ok for attr trees not to have a da btree. */
 376         if (blk->bp == NULL) {
 377                 xchk_da_set_corrupt(ds, level);
 378                 goto out_nobuf;
 379         }
 380
 381         hdr3 = blk->bp->b_addr;
 382         blk->magic = be16_to_cpu(hdr3->hdr.magic);
 383         pmaxrecs = &ds->maxrecs[level];
 384
 385         /* We only started zeroing the header on v5 filesystems. */
 386         if (xfs_sb_version_hascrc(&ds->sc->mp->m_sb) && hdr3->hdr.pad)
 387                 xchk_da_set_corrupt(ds, level);
 388
 389         /* Check the owner. */
 390         if (xfs_sb_version_hascrc(&ip->i_mount->m_sb)) {
 391                 owner = be64_to_cpu(hdr3->owner);
 392                 if (owner != ip->i_ino)
 393                         xchk_da_set_corrupt(ds, level);
 394         }
 395
 396         /* Check the siblings. */
 397         error = xchk_da_btree_block_check_siblings(ds, level, &hdr3->hdr);
 398         if (error)
 399                 goto out;
 400
 401         /* Interpret the buffer. */
 402         switch (blk->magic) {
 403         case XFS_ATTR_LEAF_MAGIC:
 404         case XFS_ATTR3_LEAF_MAGIC:
 405                 xfs_trans_buf_set_type(dargs->trans, blk->bp,
 406                                 XFS_BLFT_ATTR_LEAF_BUF);
 407                 blk->magic = XFS_ATTR_LEAF_MAGIC;
 408                 blk->hashval = xfs_attr_leaf_lasthash(blk->bp, pmaxrecs);
 409                 if (ds->tree_level != 0)
 410                         xchk_da_set_corrupt(ds, level);
 411                 break;
 412         case XFS_DIR2_LEAFN_MAGIC:
 413         case XFS_DIR3_LEAFN_MAGIC:
 414                 xfs_trans_buf_set_type(dargs->trans, blk->bp,
 415                                 XFS_BLFT_DIR_LEAFN_BUF);
 416                 blk->magic = XFS_DIR2_LEAFN_MAGIC;
 417                 blk->hashval = xfs_dir2_leaf_lasthash(ip, blk->bp, pmaxrecs);
 418                 if (ds->tree_level != 0)
 419                         xchk_da_set_corrupt(ds, level);
 420                 break;
 421         case XFS_DIR2_LEAF1_MAGIC:
 422         case XFS_DIR3_LEAF1_MAGIC:
 423                 xfs_trans_buf_set_type(dargs->trans, blk->bp,
 424                                 XFS_BLFT_DIR_LEAF1_BUF);
 425                 blk->magic = XFS_DIR2_LEAF1_MAGIC;
 426                 blk->hashval = xfs_dir2_leaf_lasthash(ip, blk->bp, pmaxrecs);
 427                 if (ds->tree_level != 0)
 428                         xchk_da_set_corrupt(ds, level);
 429                 break;
 430         case XFS_DA_NODE_MAGIC:
 431         case XFS_DA3_NODE_MAGIC:
 432                 xfs_trans_buf_set_type(dargs->trans, blk->bp,
 433                                 XFS_BLFT_DA_NODE_BUF);
 434                 blk->magic = XFS_DA_NODE_MAGIC;
 435                 node = blk->bp->b_addr;
 436                 ip->d_ops->node_hdr_from_disk(&nodehdr, node);
 437                 btree = ip->d_ops->node_tree_p(node);
 438                 *pmaxrecs = nodehdr.count;
 439                 blk->hashval = be32_to_cpu(btree[*pmaxrecs - 1].hashval);
 440                 if (level == 0) {
 441                         if (nodehdr.level >= XFS_DA_NODE_MAXDEPTH) {
 442                                 xchk_da_set_corrupt(ds, level);
 443                                 goto out_freebp;
 444                         }
 445                         ds->tree_level = nodehdr.level;
 446                 } else {
 447                         if (ds->tree_level != nodehdr.level) {
 448                                 xchk_da_set_corrupt(ds, level);
 449                                 goto out_freebp;
 450                         }
 451                 }
 452
 453                 /* XXX: Check hdr3.pad32 once we know how to fix it. */
 454                 break;
 455         default:
 456                 xchk_da_set_corrupt(ds, level);
 457                 goto out_freebp;
 458         }
 459
 460 out:
 461         return error;
 462 out_freebp:
 463         xfs_trans_brelse(dargs->trans, blk->bp);
 464         blk->bp = NULL;
 465 out_nobuf:
 466         blk->blkno = 0;
 467         return error;
 468 }
 469
 470 /* Visit all nodes and leaves of a da btree. */
 471 int
 472 xchk_da_btree(
 473         struct xfs_scrub                *sc,
 474         int                             whichfork,
 475         xchk_da_btree_rec_fn            scrub_fn,
 476         void                            *private)
 477 {
 478         struct xchk_da_btree            ds = {};
 479         struct xfs_mount                *mp = sc->mp;
 480         struct xfs_da_state_blk         *blks;
 481         struct xfs_da_node_entry        *key;
 482         void                            *rec;
 483         xfs_dablk_t                     blkno;
 484         int                             level;
 485         int                             error;
 486
 487         /* Skip short format data structures; no btree to scan. */
 488         if (XFS_IFORK_FORMAT(sc->ip, whichfork) != XFS_DINODE_FMT_EXTENTS &&
 489             XFS_IFORK_FORMAT(sc->ip, whichfork) != XFS_DINODE_FMT_BTREE)
 490                 return 0;
 491
 492         /* Set up initial da state. */
 493         ds.dargs.dp = sc->ip;
 494         ds.dargs.whichfork = whichfork;
 495         ds.dargs.trans = sc->tp;
 496         ds.dargs.op_flags = XFS_DA_OP_OKNOENT;
 497         ds.state = xfs_da_state_alloc();
 498         ds.state->args = &ds.dargs;
 499         ds.state->mp = mp;
 500         ds.sc = sc;
 501         ds.private = private;
 502         if (whichfork == XFS_ATTR_FORK) {
 503                 ds.dargs.geo = mp->m_attr_geo;
 504                 ds.lowest = 0;
 505                 ds.highest = 0;
 506         } else {
 507                 ds.dargs.geo = mp->m_dir_geo;
 508                 ds.lowest = ds.dargs.geo->leafblk;
 509                 ds.highest = ds.dargs.geo->freeblk;
 510         }
 511         blkno = ds.lowest;
 512         level = 0;
 513
 514         /* Find the root of the da tree, if present. */
 515         blks = ds.state->path.blk;
 516         error = xchk_da_btree_block(&ds, level, blkno);
 517         if (error)
 518                 goto out_state;
 519         /*
 520          * We didn't find a block at ds.lowest, which means that there's
 521          * no LEAF1/LEAFN tree (at least not where it's supposed to be),
 522          * so jump out now.
 523          */
 524         if (blks[level].bp == NULL)
 525                 goto out_state;
 526
 527         blks[level].index = 0;
 528         while (level >= 0 && level < XFS_DA_NODE_MAXDEPTH) {
 529                 /* Handle leaf block. */
 530                 if (blks[level].magic != XFS_DA_NODE_MAGIC) {
 531                         /* End of leaf, pop back towards the root. */
 532                         if (blks[level].index >= ds.maxrecs[level]) {
 533                                 if (level > 0)
 534                                         blks[level - 1].index++;
 535                                 ds.tree_level++;
 536                                 level--;
 537                                 continue;
 538                         }
 539
 540                         /* Dispatch record scrubbing. */
 541                         rec = xchk_da_btree_entry(&ds, level,
 542                                         blks[level].index);
 543                         error = scrub_fn(&ds, level, rec);
 544                         if (error)
 545                                 break;
 546                         if (xchk_should_terminate(sc, &error) ||
 547                             (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
 548                                 break;
 549
 550                         blks[level].index++;
 551                         continue;
 552                 }
 553
 554
 555                 /* End of node, pop back towards the root. */
 556                 if (blks[level].index >= ds.maxrecs[level]) {
 557                         if (level > 0)
 558                                 blks[level - 1].index++;
 559                         ds.tree_level++;
 560                         level--;
 561                         continue;
 562                 }
 563
 564                 /* Hashes in order for scrub? */
 565                 key = xchk_da_btree_entry(&ds, level, blks[level].index);
 566                 error = xchk_da_btree_hash(&ds, level, &key->hashval);
 567                 if (error)
 568                         goto out;
 569
 570                 /* Drill another level deeper. */
 571                 blkno = be32_to_cpu(key->before);
 572                 level++;
 573                 if (level >= XFS_DA_NODE_MAXDEPTH) {
 574                         /* Too deep! */
 575                         xchk_da_set_corrupt(&ds, level - 1);
 576                         break;
 577                 }
 578                 ds.tree_level--;
 579                 error = xchk_da_btree_block(&ds, level, blkno);
 580                 if (error)
 581                         goto out;
 582                 if (blks[level].bp == NULL)
 583                         goto out;
 584
 585                 blks[level].index = 0;
 586         }
 587
 588 out:
 589         /* Release all the buffers we're tracking. */
 590         for (level = 0; level < XFS_DA_NODE_MAXDEPTH; level++) {
 591                 if (blks[level].bp == NULL)
 592                         continue;
 593                 xfs_trans_brelse(sc->tp, blks[level].bp);
 594                 blks[level].bp = NULL;
 595         }
 596
 597 out_state:
 598         xfs_da_state_free(ds.state);
 599         return error;
 600 }