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