fs/xfs/scrub/dabtree.c

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