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