1// SPDX-License-Identifier: GPL-2.0-or-later 2/* 3 * Copyright (C) 2018-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_defer.h" 13#include "xfs_btree.h" 14#include "xfs_btree_staging.h" 15#include "xfs_bit.h" 16#include "xfs_log_format.h" 17#include "xfs_trans.h" 18#include "xfs_sb.h" 19#include "xfs_alloc.h" 20#include "xfs_alloc_btree.h" 21#include "xfs_rmap.h" 22#include "xfs_rmap_btree.h" 23#include "xfs_inode.h" 24#include "xfs_refcount.h" 25#include "xfs_extent_busy.h" 26#include "xfs_health.h" 27#include "xfs_bmap.h" 28#include "xfs_ialloc.h" 29#include "xfs_ag.h" 30#include "scrub/xfs_scrub.h" 31#include "scrub/scrub.h" 32#include "scrub/common.h" 33#include "scrub/btree.h" 34#include "scrub/trace.h" 35#include "scrub/repair.h" 36#include "scrub/bitmap.h" 37#include "scrub/agb_bitmap.h" 38#include "scrub/xfile.h" 39#include "scrub/xfarray.h" 40#include "scrub/newbt.h" 41#include "scrub/reap.h" 42 43/* 44 * Free Space Btree Repair 45 * ======================= 46 * 47 * The reverse mappings are supposed to record all space usage for the entire 48 * AG. Therefore, we can recreate the free extent records in an AG by looking 49 * for gaps in the physical extents recorded in the rmapbt. These records are 50 * staged in @free_records. Identifying the gaps is more difficult on a 51 * reflink filesystem because rmap records are allowed to overlap. 52 * 53 * Because the final step of building a new index is to free the space used by 54 * the old index, repair needs to find that space. Unfortunately, all 55 * structures that live in the free space (bnobt, cntbt, rmapbt, agfl) share 56 * the same rmapbt owner code (OWN_AG), so this is not straightforward. 57 * 58 * The scan of the reverse mapping information records the space used by OWN_AG 59 * in @old_allocbt_blocks, which (at this stage) is somewhat misnamed. While 60 * walking the rmapbt records, we create a second bitmap @not_allocbt_blocks to 61 * record all visited rmap btree blocks and all blocks owned by the AGFL. 62 * 63 * After that is where the definitions of old_allocbt_blocks shifts. This 64 * expression identifies possible former bnobt/cntbt blocks: 65 * 66 * (OWN_AG blocks) & ~(rmapbt blocks | agfl blocks); 67 * 68 * Substituting from above definitions, that becomes: 69 * 70 * old_allocbt_blocks & ~not_allocbt_blocks 71 * 72 * The OWN_AG bitmap itself isn't needed after this point, so what we really do 73 * instead is: 74 * 75 * old_allocbt_blocks &= ~not_allocbt_blocks; 76 * 77 * After this point, @old_allocbt_blocks is a bitmap of alleged former 78 * bnobt/cntbt blocks. The xagb_bitmap_disunion operation modifies its first 79 * parameter in place to avoid copying records around. 80 * 81 * Next, some of the space described by @free_records are diverted to the newbt 82 * reservation and used to format new btree blocks. The remaining records are 83 * written to the new btree indices. We reconstruct both bnobt and cntbt at 84 * the same time since we've already done all the work. 85 * 86 * We use the prefix 'xrep_abt' here because we regenerate both free space 87 * allocation btrees at the same time. 88 */ 89 90struct xrep_abt { 91 /* Blocks owned by the rmapbt or the agfl. */ 92 struct xagb_bitmap not_allocbt_blocks; 93 94 /* All OWN_AG blocks. */ 95 struct xagb_bitmap old_allocbt_blocks; 96 97 /* 98 * New bnobt information. All btree block reservations are added to 99 * the reservation list in new_bnobt. 100 */ 101 struct xrep_newbt new_bnobt; 102 103 /* new cntbt information */ 104 struct xrep_newbt new_cntbt; 105 106 /* Free space extents. */ 107 struct xfarray *free_records; 108 109 struct xfs_scrub *sc; 110 111 /* Number of non-null records in @free_records. */ 112 uint64_t nr_real_records; 113 114 /* get_records()'s position in the free space record array. */ 115 xfarray_idx_t array_cur; 116 117 /* 118 * Next block we anticipate seeing in the rmap records. If the next 119 * rmap record is greater than next_agbno, we have found unused space. 120 */ 121 xfs_agblock_t next_agbno; 122 123 /* Number of free blocks in this AG. */ 124 xfs_agblock_t nr_blocks; 125 126 /* Longest free extent we found in the AG. */ 127 xfs_agblock_t longest; 128}; 129 130/* Set up to repair AG free space btrees. */ 131int 132xrep_setup_ag_allocbt( 133 struct xfs_scrub *sc) 134{ 135 unsigned int busy_gen; 136 137 /* 138 * Make sure the busy extent list is clear because we can't put extents 139 * on there twice. 140 */ 141 busy_gen = READ_ONCE(sc->sa.pag->pagb_gen); 142 if (xfs_extent_busy_list_empty(sc->sa.pag)) 143 return 0; 144 145 return xfs_extent_busy_flush(sc->tp, sc->sa.pag, busy_gen, 0); 146} 147 148/* Check for any obvious conflicts in the free extent. */ 149STATIC int 150xrep_abt_check_free_ext( 151 struct xfs_scrub *sc, 152 const struct xfs_alloc_rec_incore *rec) 153{ 154 enum xbtree_recpacking outcome; 155 int error; 156 157 if (xfs_alloc_check_irec(sc->sa.pag, rec) != NULL) 158 return -EFSCORRUPTED; 159 160 /* Must not be an inode chunk. */ 161 error = xfs_ialloc_has_inodes_at_extent(sc->sa.ino_cur, 162 rec->ar_startblock, rec->ar_blockcount, &outcome); 163 if (error) 164 return error; 165 if (outcome != XBTREE_RECPACKING_EMPTY) 166 return -EFSCORRUPTED; 167 168 /* Must not be shared or CoW staging. */ 169 if (sc->sa.refc_cur) { 170 error = xfs_refcount_has_records(sc->sa.refc_cur, 171 XFS_REFC_DOMAIN_SHARED, rec->ar_startblock, 172 rec->ar_blockcount, &outcome); 173 if (error) 174 return error; 175 if (outcome != XBTREE_RECPACKING_EMPTY) 176 return -EFSCORRUPTED; 177 178 error = xfs_refcount_has_records(sc->sa.refc_cur, 179 XFS_REFC_DOMAIN_COW, rec->ar_startblock, 180 rec->ar_blockcount, &outcome); 181 if (error) 182 return error; 183 if (outcome != XBTREE_RECPACKING_EMPTY) 184 return -EFSCORRUPTED; 185 } 186 187 return 0; 188} 189 190/* 191 * Stash a free space record for all the space since the last bno we found 192 * all the way up to @end. 193 */ 194static int 195xrep_abt_stash( 196 struct xrep_abt *ra, 197 xfs_agblock_t end) 198{ 199 struct xfs_alloc_rec_incore arec = { 200 .ar_startblock = ra->next_agbno, 201 .ar_blockcount = end - ra->next_agbno, 202 }; 203 struct xfs_scrub *sc = ra->sc; 204 int error = 0; 205 206 if (xchk_should_terminate(sc, &error)) 207 return error; 208 209 error = xrep_abt_check_free_ext(ra->sc, &arec); 210 if (error) 211 return error; 212 213 trace_xrep_abt_found(sc->mp, sc->sa.pag->pag_agno, &arec); 214 215 error = xfarray_append(ra->free_records, &arec); 216 if (error) 217 return error; 218 219 ra->nr_blocks += arec.ar_blockcount; 220 return 0; 221} 222 223/* Record extents that aren't in use from gaps in the rmap records. */ 224STATIC int 225xrep_abt_walk_rmap( 226 struct xfs_btree_cur *cur, 227 const struct xfs_rmap_irec *rec, 228 void *priv) 229{ 230 struct xrep_abt *ra = priv; 231 int error; 232 233 /* Record all the OWN_AG blocks... */ 234 if (rec->rm_owner == XFS_RMAP_OWN_AG) { 235 error = xagb_bitmap_set(&ra->old_allocbt_blocks, 236 rec->rm_startblock, rec->rm_blockcount); 237 if (error) 238 return error; 239 } 240 241 /* ...and all the rmapbt blocks... */ 242 error = xagb_bitmap_set_btcur_path(&ra->not_allocbt_blocks, cur); 243 if (error) 244 return error; 245 246 /* ...and all the free space. */ 247 if (rec->rm_startblock > ra->next_agbno) { 248 error = xrep_abt_stash(ra, rec->rm_startblock); 249 if (error) 250 return error; 251 } 252 253 /* 254 * rmap records can overlap on reflink filesystems, so project 255 * next_agbno as far out into the AG space as we currently know about. 256 */ 257 ra->next_agbno = max_t(xfs_agblock_t, ra->next_agbno, 258 rec->rm_startblock + rec->rm_blockcount); 259 return 0; 260} 261 262/* Collect an AGFL block for the not-to-release list. */ 263static int 264xrep_abt_walk_agfl( 265 struct xfs_mount *mp, 266 xfs_agblock_t agbno, 267 void *priv) 268{ 269 struct xrep_abt *ra = priv; 270 271 return xagb_bitmap_set(&ra->not_allocbt_blocks, agbno, 1); 272} 273 274/* 275 * Compare two free space extents by block number. We want to sort in order of 276 * increasing block number. 277 */ 278static int 279xrep_bnobt_extent_cmp( 280 const void *a, 281 const void *b) 282{ 283 const struct xfs_alloc_rec_incore *ap = a; 284 const struct xfs_alloc_rec_incore *bp = b; 285 286 if (ap->ar_startblock > bp->ar_startblock) 287 return 1; 288 else if (ap->ar_startblock < bp->ar_startblock) 289 return -1; 290 return 0; 291} 292 293/* 294 * Re-sort the free extents by block number so that we can put the records into 295 * the bnobt in the correct order. Make sure the records do not overlap in 296 * physical space. 297 */ 298STATIC int 299xrep_bnobt_sort_records( 300 struct xrep_abt *ra) 301{ 302 struct xfs_alloc_rec_incore arec; 303 xfarray_idx_t cur = XFARRAY_CURSOR_INIT; 304 xfs_agblock_t next_agbno = 0; 305 int error; 306 307 error = xfarray_sort(ra->free_records, xrep_bnobt_extent_cmp, 0); 308 if (error) 309 return error; 310 311 while ((error = xfarray_iter(ra->free_records, &cur, &arec)) == 1) { 312 if (arec.ar_startblock < next_agbno) 313 return -EFSCORRUPTED; 314 315 next_agbno = arec.ar_startblock + arec.ar_blockcount; 316 } 317 318 return error; 319} 320 321/* 322 * Compare two free space extents by length and then block number. We want 323 * to sort first in order of increasing length and then in order of increasing 324 * block number. 325 */ 326static int 327xrep_cntbt_extent_cmp( 328 const void *a, 329 const void *b) 330{ 331 const struct xfs_alloc_rec_incore *ap = a; 332 const struct xfs_alloc_rec_incore *bp = b; 333 334 if (ap->ar_blockcount > bp->ar_blockcount) 335 return 1; 336 else if (ap->ar_blockcount < bp->ar_blockcount) 337 return -1; 338 return xrep_bnobt_extent_cmp(a, b); 339} 340 341/* 342 * Sort the free extents by length so so that we can put the records into the 343 * cntbt in the correct order. Don't let userspace kill us if we're resorting 344 * after allocating btree blocks. 345 */ 346STATIC int 347xrep_cntbt_sort_records( 348 struct xrep_abt *ra, 349 bool is_resort) 350{ 351 return xfarray_sort(ra->free_records, xrep_cntbt_extent_cmp, 352 is_resort ? 0 : XFARRAY_SORT_KILLABLE); 353} 354 355/* 356 * Iterate all reverse mappings to find (1) the gaps between rmap records (all 357 * unowned space), (2) the OWN_AG extents (which encompass the free space 358 * btrees, the rmapbt, and the agfl), (3) the rmapbt blocks, and (4) the AGFL 359 * blocks. The free space is (1) + (2) - (3) - (4). 360 */ 361STATIC int 362xrep_abt_find_freespace( 363 struct xrep_abt *ra) 364{ 365 struct xfs_scrub *sc = ra->sc; 366 struct xfs_mount *mp = sc->mp; 367 struct xfs_agf *agf = sc->sa.agf_bp->b_addr; 368 struct xfs_buf *agfl_bp; 369 xfs_agblock_t agend; 370 int error; 371 372 xagb_bitmap_init(&ra->not_allocbt_blocks); 373 374 xrep_ag_btcur_init(sc, &sc->sa); 375 376 /* 377 * Iterate all the reverse mappings to find gaps in the physical 378 * mappings, all the OWN_AG blocks, and all the rmapbt extents. 379 */ 380 error = xfs_rmap_query_all(sc->sa.rmap_cur, xrep_abt_walk_rmap, ra); 381 if (error) 382 goto err; 383 384 /* Insert a record for space between the last rmap and EOAG. */ 385 agend = be32_to_cpu(agf->agf_length); 386 if (ra->next_agbno < agend) { 387 error = xrep_abt_stash(ra, agend); 388 if (error) 389 goto err; 390 } 391 392 /* Collect all the AGFL blocks. */ 393 error = xfs_alloc_read_agfl(sc->sa.pag, sc->tp, &agfl_bp); 394 if (error) 395 goto err; 396 397 error = xfs_agfl_walk(mp, agf, agfl_bp, xrep_abt_walk_agfl, ra); 398 if (error) 399 goto err_agfl; 400 401 /* Compute the old bnobt/cntbt blocks. */ 402 error = xagb_bitmap_disunion(&ra->old_allocbt_blocks, 403 &ra->not_allocbt_blocks); 404 if (error) 405 goto err_agfl; 406 407 ra->nr_real_records = xfarray_length(ra->free_records); 408err_agfl: 409 xfs_trans_brelse(sc->tp, agfl_bp); 410err: 411 xchk_ag_btcur_free(&sc->sa); 412 xagb_bitmap_destroy(&ra->not_allocbt_blocks); 413 return error; 414} 415 416/* 417 * We're going to use the observed free space records to reserve blocks for the 418 * new free space btrees, so we play an iterative game where we try to converge 419 * on the number of blocks we need: 420 * 421 * 1. Estimate how many blocks we'll need to store the records. 422 * 2. If the first free record has more blocks than we need, we're done. 423 * We will have to re-sort the records prior to building the cntbt. 424 * 3. If that record has exactly the number of blocks we need, null out the 425 * record. We're done. 426 * 4. Otherwise, we still need more blocks. Null out the record, subtract its 427 * length from the number of blocks we need, and go back to step 1. 428 * 429 * Fortunately, we don't have to do any transaction work to play this game, so 430 * we don't have to tear down the staging cursors. 431 */ 432STATIC int 433xrep_abt_reserve_space( 434 struct xrep_abt *ra, 435 struct xfs_btree_cur *bno_cur, 436 struct xfs_btree_cur *cnt_cur, 437 bool *needs_resort) 438{ 439 struct xfs_scrub *sc = ra->sc; 440 xfarray_idx_t record_nr; 441 unsigned int allocated = 0; 442 int error = 0; 443 444 record_nr = xfarray_length(ra->free_records) - 1; 445 do { 446 struct xfs_alloc_rec_incore arec; 447 uint64_t required; 448 unsigned int desired; 449 unsigned int len; 450 451 /* Compute how many blocks we'll need. */ 452 error = xfs_btree_bload_compute_geometry(cnt_cur, 453 &ra->new_cntbt.bload, ra->nr_real_records); 454 if (error) 455 break; 456 457 error = xfs_btree_bload_compute_geometry(bno_cur, 458 &ra->new_bnobt.bload, ra->nr_real_records); 459 if (error) 460 break; 461 462 /* How many btree blocks do we need to store all records? */ 463 required = ra->new_bnobt.bload.nr_blocks + 464 ra->new_cntbt.bload.nr_blocks; 465 ASSERT(required < INT_MAX); 466 467 /* If we've reserved enough blocks, we're done. */ 468 if (allocated >= required) 469 break; 470 471 desired = required - allocated; 472 473 /* We need space but there's none left; bye! */ 474 if (ra->nr_real_records == 0) { 475 error = -ENOSPC; 476 break; 477 } 478 479 /* Grab the first record from the list. */ 480 error = xfarray_load(ra->free_records, record_nr, &arec); 481 if (error) 482 break; 483 484 ASSERT(arec.ar_blockcount <= UINT_MAX); 485 len = min_t(unsigned int, arec.ar_blockcount, desired); 486 487 trace_xrep_newbt_alloc_ag_blocks(sc->mp, sc->sa.pag->pag_agno, 488 arec.ar_startblock, len, XFS_RMAP_OWN_AG); 489 490 error = xrep_newbt_add_extent(&ra->new_bnobt, sc->sa.pag, 491 arec.ar_startblock, len); 492 if (error) 493 break; 494 allocated += len; 495 ra->nr_blocks -= len; 496 497 if (arec.ar_blockcount > desired) { 498 /* 499 * Record has more space than we need. The number of 500 * free records doesn't change, so shrink the free 501 * record, inform the caller that the records are no 502 * longer sorted by length, and exit. 503 */ 504 arec.ar_startblock += desired; 505 arec.ar_blockcount -= desired; 506 error = xfarray_store(ra->free_records, record_nr, 507 &arec); 508 if (error) 509 break; 510 511 *needs_resort = true; 512 return 0; 513 } 514 515 /* 516 * We're going to use up the entire record, so unset it and 517 * move on to the next one. This changes the number of free 518 * records (but doesn't break the sorting order), so we must 519 * go around the loop once more to re-run _bload_init. 520 */ 521 error = xfarray_unset(ra->free_records, record_nr); 522 if (error) 523 break; 524 ra->nr_real_records--; 525 record_nr--; 526 } while (1); 527 528 return error; 529} 530 531STATIC int 532xrep_abt_dispose_one( 533 struct xrep_abt *ra, 534 struct xrep_newbt_resv *resv) 535{ 536 struct xfs_scrub *sc = ra->sc; 537 struct xfs_perag *pag = sc->sa.pag; 538 xfs_agblock_t free_agbno = resv->agbno + resv->used; 539 xfs_extlen_t free_aglen = resv->len - resv->used; 540 int error; 541 542 ASSERT(pag == resv->pag); 543 544 /* Add a deferred rmap for each extent we used. */ 545 if (resv->used > 0) 546 xfs_rmap_alloc_extent(sc->tp, pag->pag_agno, resv->agbno, 547 resv->used, XFS_RMAP_OWN_AG); 548 549 /* 550 * For each reserved btree block we didn't use, add it to the free 551 * space btree. We didn't touch fdblocks when we reserved them, so 552 * we don't touch it now. 553 */ 554 if (free_aglen == 0) 555 return 0; 556 557 trace_xrep_newbt_free_blocks(sc->mp, resv->pag->pag_agno, free_agbno, 558 free_aglen, ra->new_bnobt.oinfo.oi_owner); 559 560 error = __xfs_free_extent(sc->tp, resv->pag, free_agbno, free_aglen, 561 &ra->new_bnobt.oinfo, XFS_AG_RESV_IGNORE, true); 562 if (error) 563 return error; 564 565 return xrep_defer_finish(sc); 566} 567 568/* 569 * Deal with all the space we reserved. Blocks that were allocated for the 570 * free space btrees need to have a (deferred) rmap added for the OWN_AG 571 * allocation, and blocks that didn't get used can be freed via the usual 572 * (deferred) means. 573 */ 574STATIC void 575xrep_abt_dispose_reservations( 576 struct xrep_abt *ra, 577 int error) 578{ 579 struct xrep_newbt_resv *resv, *n; 580 581 if (error) 582 goto junkit; 583 584 list_for_each_entry_safe(resv, n, &ra->new_bnobt.resv_list, list) { 585 error = xrep_abt_dispose_one(ra, resv); 586 if (error) 587 goto junkit; 588 } 589 590junkit: 591 list_for_each_entry_safe(resv, n, &ra->new_bnobt.resv_list, list) { 592 xfs_perag_put(resv->pag); 593 list_del(&resv->list); 594 kfree(resv); 595 } 596 597 xrep_newbt_cancel(&ra->new_bnobt); 598 xrep_newbt_cancel(&ra->new_cntbt); 599} 600 601/* Retrieve free space data for bulk load. */ 602STATIC int 603xrep_abt_get_records( 604 struct xfs_btree_cur *cur, 605 unsigned int idx, 606 struct xfs_btree_block *block, 607 unsigned int nr_wanted, 608 void *priv) 609{ 610 struct xfs_alloc_rec_incore *arec = &cur->bc_rec.a; 611 struct xrep_abt *ra = priv; 612 union xfs_btree_rec *block_rec; 613 unsigned int loaded; 614 int error; 615 616 for (loaded = 0; loaded < nr_wanted; loaded++, idx++) { 617 error = xfarray_load_next(ra->free_records, &ra->array_cur, 618 arec); 619 if (error) 620 return error; 621 622 ra->longest = max(ra->longest, arec->ar_blockcount); 623 624 block_rec = xfs_btree_rec_addr(cur, idx, block); 625 cur->bc_ops->init_rec_from_cur(cur, block_rec); 626 } 627 628 return loaded; 629} 630 631/* Feed one of the new btree blocks to the bulk loader. */ 632STATIC int 633xrep_abt_claim_block( 634 struct xfs_btree_cur *cur, 635 union xfs_btree_ptr *ptr, 636 void *priv) 637{ 638 struct xrep_abt *ra = priv; 639 640 return xrep_newbt_claim_block(cur, &ra->new_bnobt, ptr); 641} 642 643/* 644 * Reset the AGF counters to reflect the free space btrees that we just 645 * rebuilt, then reinitialize the per-AG data. 646 */ 647STATIC int 648xrep_abt_reset_counters( 649 struct xrep_abt *ra) 650{ 651 struct xfs_scrub *sc = ra->sc; 652 struct xfs_perag *pag = sc->sa.pag; 653 struct xfs_agf *agf = sc->sa.agf_bp->b_addr; 654 unsigned int freesp_btreeblks = 0; 655 656 /* 657 * Compute the contribution to agf_btreeblks for the new free space 658 * btrees. This is the computed btree size minus anything we didn't 659 * use. 660 */ 661 freesp_btreeblks += ra->new_bnobt.bload.nr_blocks - 1; 662 freesp_btreeblks += ra->new_cntbt.bload.nr_blocks - 1; 663 664 freesp_btreeblks -= xrep_newbt_unused_blocks(&ra->new_bnobt); 665 freesp_btreeblks -= xrep_newbt_unused_blocks(&ra->new_cntbt); 666 667 /* 668 * The AGF header contains extra information related to the free space 669 * btrees, so we must update those fields here. 670 */ 671 agf->agf_btreeblks = cpu_to_be32(freesp_btreeblks + 672 (be32_to_cpu(agf->agf_rmap_blocks) - 1)); 673 agf->agf_freeblks = cpu_to_be32(ra->nr_blocks); 674 agf->agf_longest = cpu_to_be32(ra->longest); 675 xfs_alloc_log_agf(sc->tp, sc->sa.agf_bp, XFS_AGF_BTREEBLKS | 676 XFS_AGF_LONGEST | 677 XFS_AGF_FREEBLKS); 678 679 /* 680 * After we commit the new btree to disk, it is possible that the 681 * process to reap the old btree blocks will race with the AIL trying 682 * to checkpoint the old btree blocks into the filesystem. If the new 683 * tree is shorter than the old one, the allocbt write verifier will 684 * fail and the AIL will shut down the filesystem. 685 * 686 * To avoid this, save the old incore btree height values as the alt 687 * height values before re-initializing the perag info from the updated 688 * AGF to capture all the new values. 689 */ 690 pag->pagf_repair_bno_level = pag->pagf_bno_level; 691 pag->pagf_repair_cnt_level = pag->pagf_cnt_level; 692 693 /* Reinitialize with the values we just logged. */ 694 return xrep_reinit_pagf(sc); 695} 696 697/* 698 * Use the collected free space information to stage new free space btrees. 699 * If this is successful we'll return with the new btree root 700 * information logged to the repair transaction but not yet committed. 701 */ 702STATIC int 703xrep_abt_build_new_trees( 704 struct xrep_abt *ra) 705{ 706 struct xfs_scrub *sc = ra->sc; 707 struct xfs_btree_cur *bno_cur; 708 struct xfs_btree_cur *cnt_cur; 709 struct xfs_perag *pag = sc->sa.pag; 710 bool needs_resort = false; 711 int error; 712 713 /* 714 * Sort the free extents by length so that we can set up the free space 715 * btrees in as few extents as possible. This reduces the amount of 716 * deferred rmap / free work we have to do at the end. 717 */ 718 error = xrep_cntbt_sort_records(ra, false); 719 if (error) 720 return error; 721 722 /* 723 * Prepare to construct the new btree by reserving disk space for the 724 * new btree and setting up all the accounting information we'll need 725 * to root the new btree while it's under construction and before we 726 * attach it to the AG header. 727 */ 728 xrep_newbt_init_bare(&ra->new_bnobt, sc); 729 xrep_newbt_init_bare(&ra->new_cntbt, sc); 730 731 ra->new_bnobt.bload.get_records = xrep_abt_get_records; 732 ra->new_cntbt.bload.get_records = xrep_abt_get_records; 733 734 ra->new_bnobt.bload.claim_block = xrep_abt_claim_block; 735 ra->new_cntbt.bload.claim_block = xrep_abt_claim_block; 736 737 /* Allocate cursors for the staged btrees. */ 738 bno_cur = xfs_bnobt_init_cursor(sc->mp, NULL, NULL, pag); 739 xfs_btree_stage_afakeroot(bno_cur, &ra->new_bnobt.afake); 740 741 cnt_cur = xfs_cntbt_init_cursor(sc->mp, NULL, NULL, pag); 742 xfs_btree_stage_afakeroot(cnt_cur, &ra->new_cntbt.afake); 743 744 /* Last chance to abort before we start committing fixes. */ 745 if (xchk_should_terminate(sc, &error)) 746 goto err_cur; 747 748 /* Reserve the space we'll need for the new btrees. */ 749 error = xrep_abt_reserve_space(ra, bno_cur, cnt_cur, &needs_resort); 750 if (error) 751 goto err_cur; 752 753 /* 754 * If we need to re-sort the free extents by length, do so so that we 755 * can put the records into the cntbt in the correct order. 756 */ 757 if (needs_resort) { 758 error = xrep_cntbt_sort_records(ra, needs_resort); 759 if (error) 760 goto err_cur; 761 } 762 763 /* 764 * Due to btree slack factors, it's possible for a new btree to be one 765 * level taller than the old btree. Update the alternate incore btree 766 * height so that we don't trip the verifiers when writing the new 767 * btree blocks to disk. 768 */ 769 pag->pagf_repair_bno_level = ra->new_bnobt.bload.btree_height; 770 pag->pagf_repair_cnt_level = ra->new_cntbt.bload.btree_height; 771 772 /* Load the free space by length tree. */ 773 ra->array_cur = XFARRAY_CURSOR_INIT; 774 ra->longest = 0; 775 error = xfs_btree_bload(cnt_cur, &ra->new_cntbt.bload, ra); 776 if (error) 777 goto err_levels; 778 779 error = xrep_bnobt_sort_records(ra); 780 if (error) 781 return error; 782 783 /* Load the free space by block number tree. */ 784 ra->array_cur = XFARRAY_CURSOR_INIT; 785 error = xfs_btree_bload(bno_cur, &ra->new_bnobt.bload, ra); 786 if (error) 787 goto err_levels; 788 789 /* 790 * Install the new btrees in the AG header. After this point the old 791 * btrees are no longer accessible and the new trees are live. 792 */ 793 xfs_allocbt_commit_staged_btree(bno_cur, sc->tp, sc->sa.agf_bp); 794 xfs_btree_del_cursor(bno_cur, 0); 795 xfs_allocbt_commit_staged_btree(cnt_cur, sc->tp, sc->sa.agf_bp); 796 xfs_btree_del_cursor(cnt_cur, 0); 797 798 /* Reset the AGF counters now that we've changed the btree shape. */ 799 error = xrep_abt_reset_counters(ra); 800 if (error) 801 goto err_newbt; 802 803 /* Dispose of any unused blocks and the accounting information. */ 804 xrep_abt_dispose_reservations(ra, error); 805 806 return xrep_roll_ag_trans(sc); 807 808err_levels: 809 pag->pagf_repair_bno_level = 0; 810 pag->pagf_repair_cnt_level = 0; 811err_cur: 812 xfs_btree_del_cursor(cnt_cur, error); 813 xfs_btree_del_cursor(bno_cur, error); 814err_newbt: 815 xrep_abt_dispose_reservations(ra, error); 816 return error; 817} 818 819/* 820 * Now that we've logged the roots of the new btrees, invalidate all of the 821 * old blocks and free them. 822 */ 823STATIC int 824xrep_abt_remove_old_trees( 825 struct xrep_abt *ra) 826{ 827 struct xfs_perag *pag = ra->sc->sa.pag; 828 int error; 829 830 /* Free the old btree blocks if they're not in use. */ 831 error = xrep_reap_agblocks(ra->sc, &ra->old_allocbt_blocks, 832 &XFS_RMAP_OINFO_AG, XFS_AG_RESV_IGNORE); 833 if (error) 834 return error; 835 836 /* 837 * Now that we've zapped all the old allocbt blocks we can turn off 838 * the alternate height mechanism. 839 */ 840 pag->pagf_repair_bno_level = 0; 841 pag->pagf_repair_cnt_level = 0; 842 return 0; 843} 844 845/* Repair the freespace btrees for some AG. */ 846int 847xrep_allocbt( 848 struct xfs_scrub *sc) 849{ 850 struct xrep_abt *ra; 851 struct xfs_mount *mp = sc->mp; 852 char *descr; 853 int error; 854 855 /* We require the rmapbt to rebuild anything. */ 856 if (!xfs_has_rmapbt(mp)) 857 return -EOPNOTSUPP; 858 859 ra = kzalloc(sizeof(struct xrep_abt), XCHK_GFP_FLAGS); 860 if (!ra) 861 return -ENOMEM; 862 ra->sc = sc; 863 864 /* We rebuild both data structures. */ 865 sc->sick_mask = XFS_SICK_AG_BNOBT | XFS_SICK_AG_CNTBT; 866 867 /* 868 * Make sure the busy extent list is clear because we can't put extents 869 * on there twice. In theory we cleared this before we started, but 870 * let's not risk the filesystem. 871 */ 872 if (!xfs_extent_busy_list_empty(sc->sa.pag)) { 873 error = -EDEADLOCK; 874 goto out_ra; 875 } 876 877 /* Set up enough storage to handle maximally fragmented free space. */ 878 descr = xchk_xfile_ag_descr(sc, "free space records"); 879 error = xfarray_create(descr, mp->m_sb.sb_agblocks / 2, 880 sizeof(struct xfs_alloc_rec_incore), 881 &ra->free_records); 882 kfree(descr); 883 if (error) 884 goto out_ra; 885 886 /* Collect the free space data and find the old btree blocks. */ 887 xagb_bitmap_init(&ra->old_allocbt_blocks); 888 error = xrep_abt_find_freespace(ra); 889 if (error) 890 goto out_bitmap; 891 892 /* Rebuild the free space information. */ 893 error = xrep_abt_build_new_trees(ra); 894 if (error) 895 goto out_bitmap; 896 897 /* Kill the old trees. */ 898 error = xrep_abt_remove_old_trees(ra); 899 if (error) 900 goto out_bitmap; 901 902out_bitmap: 903 xagb_bitmap_destroy(&ra->old_allocbt_blocks); 904 xfarray_destroy(ra->free_records); 905out_ra: 906 kfree(ra); 907 return error; 908} 909 910/* Make sure both btrees are ok after we've rebuilt them. */ 911int 912xrep_revalidate_allocbt( 913 struct xfs_scrub *sc) 914{ 915 __u32 old_type = sc->sm->sm_type; 916 int error; 917 918 /* 919 * We must update sm_type temporarily so that the tree-to-tree cross 920 * reference checks will work in the correct direction, and also so 921 * that tracing will report correctly if there are more errors. 922 */ 923 sc->sm->sm_type = XFS_SCRUB_TYPE_BNOBT; 924 error = xchk_allocbt(sc); 925 if (error) 926 goto out; 927 928 sc->sm->sm_type = XFS_SCRUB_TYPE_CNTBT; 929 error = xchk_allocbt(sc); 930out: 931 sc->sm->sm_type = old_type; 932 return error; 933} 934