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