1 // SPDX-License-Identifier: GPL-2.0 2 #include "bcachefs.h" 3 #include "bbpos.h" 4 #include "alloc_background.h" 5 #include "backpointers.h" 6 #include "bkey_buf.h" 7 #include "btree_cache.h" 8 #include "btree_update.h" 9 #include "btree_update_interior.h" 10 #include "btree_write_buffer.h" 11 #include "error.h" 12 13 #include <linux/mm.h> 14 15 static bool extent_matches_bp(struct bch_fs *c, 16 enum btree_id btree_id, unsigned level, 17 struct bkey_s_c k, 18 struct bpos bucket, 19 struct bch_backpointer bp) 20 { 21 struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k); 22 const union bch_extent_entry *entry; 23 struct extent_ptr_decoded p; 24 25 bkey_for_each_ptr_decode(k.k, ptrs, p, entry) { 26 struct bpos bucket2; 27 struct bch_backpointer bp2; 28 29 if (p.ptr.cached) 30 continue; 31 32 bch2_extent_ptr_to_bp(c, btree_id, level, k, p, 33 &bucket2, &bp2); 34 if (bpos_eq(bucket, bucket2) && 35 !memcmp(&bp, &bp2, sizeof(bp))) 36 return true; 37 } 38 39 return false; 40 } 41 42 int bch2_backpointer_invalid(struct bch_fs *c, struct bkey_s_c k, 43 enum bkey_invalid_flags flags, 44 struct printbuf *err) 45 { 46 struct bkey_s_c_backpointer bp = bkey_s_c_to_backpointer(k); 47 struct bpos bucket = bp_pos_to_bucket(c, bp.k->p); 48 int ret = 0; 49 50 bkey_fsck_err_on(!bpos_eq(bp.k->p, bucket_pos_to_bp(c, bucket, bp.v->bucket_offset)), 51 c, err, 52 backpointer_pos_wrong, 53 "backpointer at wrong pos"); 54 fsck_err: 55 return ret; 56 } 57 58 void bch2_backpointer_to_text(struct printbuf *out, const struct bch_backpointer *bp) 59 { 60 prt_printf(out, "btree=%s l=%u offset=%llu:%u len=%u pos=", 61 bch2_btree_id_str(bp->btree_id), 62 bp->level, 63 (u64) (bp->bucket_offset >> MAX_EXTENT_COMPRESS_RATIO_SHIFT), 64 (u32) bp->bucket_offset & ~(~0U << MAX_EXTENT_COMPRESS_RATIO_SHIFT), 65 bp->bucket_len); 66 bch2_bpos_to_text(out, bp->pos); 67 } 68 69 void bch2_backpointer_k_to_text(struct printbuf *out, struct bch_fs *c, struct bkey_s_c k) 70 { 71 prt_str(out, "bucket="); 72 bch2_bpos_to_text(out, bp_pos_to_bucket(c, k.k->p)); 73 prt_str(out, " "); 74 75 bch2_backpointer_to_text(out, bkey_s_c_to_backpointer(k).v); 76 } 77 78 void bch2_backpointer_swab(struct bkey_s k) 79 { 80 struct bkey_s_backpointer bp = bkey_s_to_backpointer(k); 81 82 bp.v->bucket_offset = swab40(bp.v->bucket_offset); 83 bp.v->bucket_len = swab32(bp.v->bucket_len); 84 bch2_bpos_swab(&bp.v->pos); 85 } 86 87 static noinline int backpointer_mod_err(struct btree_trans *trans, 88 struct bch_backpointer bp, 89 struct bkey_s_c bp_k, 90 struct bkey_s_c orig_k, 91 bool insert) 92 { 93 struct bch_fs *c = trans->c; 94 struct printbuf buf = PRINTBUF; 95 96 if (insert) { 97 prt_printf(&buf, "existing backpointer found when inserting "); 98 bch2_backpointer_to_text(&buf, &bp); 99 prt_newline(&buf); 100 printbuf_indent_add(&buf, 2); 101 102 prt_printf(&buf, "found "); 103 bch2_bkey_val_to_text(&buf, c, bp_k); 104 prt_newline(&buf); 105 106 prt_printf(&buf, "for "); 107 bch2_bkey_val_to_text(&buf, c, orig_k); 108 109 bch_err(c, "%s", buf.buf); 110 } else if (c->curr_recovery_pass > BCH_RECOVERY_PASS_check_extents_to_backpointers) { 111 prt_printf(&buf, "backpointer not found when deleting"); 112 prt_newline(&buf); 113 printbuf_indent_add(&buf, 2); 114 115 prt_printf(&buf, "searching for "); 116 bch2_backpointer_to_text(&buf, &bp); 117 prt_newline(&buf); 118 119 prt_printf(&buf, "got "); 120 bch2_bkey_val_to_text(&buf, c, bp_k); 121 prt_newline(&buf); 122 123 prt_printf(&buf, "for "); 124 bch2_bkey_val_to_text(&buf, c, orig_k); 125 126 bch_err(c, "%s", buf.buf); 127 } 128 129 printbuf_exit(&buf); 130 131 if (c->curr_recovery_pass > BCH_RECOVERY_PASS_check_extents_to_backpointers) { 132 bch2_inconsistent_error(c); 133 return -EIO; 134 } else { 135 return 0; 136 } 137 } 138 139 int bch2_bucket_backpointer_mod_nowritebuffer(struct btree_trans *trans, 140 struct bpos bucket, 141 struct bch_backpointer bp, 142 struct bkey_s_c orig_k, 143 bool insert) 144 { 145 struct btree_iter bp_iter; 146 struct bkey_s_c k; 147 struct bkey_i_backpointer *bp_k; 148 int ret; 149 150 bp_k = bch2_trans_kmalloc_nomemzero(trans, sizeof(struct bkey_i_backpointer)); 151 ret = PTR_ERR_OR_ZERO(bp_k); 152 if (ret) 153 return ret; 154 155 bkey_backpointer_init(&bp_k->k_i); 156 bp_k->k.p = bucket_pos_to_bp(trans->c, bucket, bp.bucket_offset); 157 bp_k->v = bp; 158 159 if (!insert) { 160 bp_k->k.type = KEY_TYPE_deleted; 161 set_bkey_val_u64s(&bp_k->k, 0); 162 } 163 164 k = bch2_bkey_get_iter(trans, &bp_iter, BTREE_ID_backpointers, 165 bp_k->k.p, 166 BTREE_ITER_INTENT| 167 BTREE_ITER_SLOTS| 168 BTREE_ITER_WITH_UPDATES); 169 ret = bkey_err(k); 170 if (ret) 171 goto err; 172 173 if (insert 174 ? k.k->type 175 : (k.k->type != KEY_TYPE_backpointer || 176 memcmp(bkey_s_c_to_backpointer(k).v, &bp, sizeof(bp)))) { 177 ret = backpointer_mod_err(trans, bp, k, orig_k, insert); 178 if (ret) 179 goto err; 180 } 181 182 ret = bch2_trans_update(trans, &bp_iter, &bp_k->k_i, 0); 183 err: 184 bch2_trans_iter_exit(trans, &bp_iter); 185 return ret; 186 } 187 188 /* 189 * Find the next backpointer >= *bp_offset: 190 */ 191 int bch2_get_next_backpointer(struct btree_trans *trans, 192 struct bpos bucket, int gen, 193 struct bpos *bp_pos, 194 struct bch_backpointer *bp, 195 unsigned iter_flags) 196 { 197 struct bch_fs *c = trans->c; 198 struct bpos bp_end_pos = bucket_pos_to_bp(c, bpos_nosnap_successor(bucket), 0); 199 struct btree_iter alloc_iter = { NULL }, bp_iter = { NULL }; 200 struct bkey_s_c k; 201 int ret = 0; 202 203 if (bpos_ge(*bp_pos, bp_end_pos)) 204 goto done; 205 206 if (gen >= 0) { 207 k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc, 208 bucket, BTREE_ITER_CACHED|iter_flags); 209 ret = bkey_err(k); 210 if (ret) 211 goto out; 212 213 if (k.k->type != KEY_TYPE_alloc_v4 || 214 bkey_s_c_to_alloc_v4(k).v->gen != gen) 215 goto done; 216 } 217 218 *bp_pos = bpos_max(*bp_pos, bucket_pos_to_bp(c, bucket, 0)); 219 220 for_each_btree_key_norestart(trans, bp_iter, BTREE_ID_backpointers, 221 *bp_pos, iter_flags, k, ret) { 222 if (bpos_ge(k.k->p, bp_end_pos)) 223 break; 224 225 *bp_pos = k.k->p; 226 *bp = *bkey_s_c_to_backpointer(k).v; 227 goto out; 228 } 229 done: 230 *bp_pos = SPOS_MAX; 231 out: 232 bch2_trans_iter_exit(trans, &bp_iter); 233 bch2_trans_iter_exit(trans, &alloc_iter); 234 return ret; 235 } 236 237 static void backpointer_not_found(struct btree_trans *trans, 238 struct bpos bp_pos, 239 struct bch_backpointer bp, 240 struct bkey_s_c k) 241 { 242 struct bch_fs *c = trans->c; 243 struct printbuf buf = PRINTBUF; 244 struct bpos bucket = bp_pos_to_bucket(c, bp_pos); 245 246 /* 247 * If we're using the btree write buffer, the backpointer we were 248 * looking at may have already been deleted - failure to find what it 249 * pointed to is not an error: 250 */ 251 if (likely(!bch2_backpointers_no_use_write_buffer)) 252 return; 253 254 prt_printf(&buf, "backpointer doesn't match %s it points to:\n ", 255 bp.level ? "btree node" : "extent"); 256 prt_printf(&buf, "bucket: "); 257 bch2_bpos_to_text(&buf, bucket); 258 prt_printf(&buf, "\n "); 259 260 prt_printf(&buf, "backpointer pos: "); 261 bch2_bpos_to_text(&buf, bp_pos); 262 prt_printf(&buf, "\n "); 263 264 bch2_backpointer_to_text(&buf, &bp); 265 prt_printf(&buf, "\n "); 266 bch2_bkey_val_to_text(&buf, c, k); 267 if (c->curr_recovery_pass >= BCH_RECOVERY_PASS_check_extents_to_backpointers) 268 bch_err_ratelimited(c, "%s", buf.buf); 269 else 270 bch2_trans_inconsistent(trans, "%s", buf.buf); 271 272 printbuf_exit(&buf); 273 } 274 275 struct bkey_s_c bch2_backpointer_get_key(struct btree_trans *trans, 276 struct btree_iter *iter, 277 struct bpos bp_pos, 278 struct bch_backpointer bp, 279 unsigned iter_flags) 280 { 281 if (likely(!bp.level)) { 282 struct bch_fs *c = trans->c; 283 struct bpos bucket = bp_pos_to_bucket(c, bp_pos); 284 struct bkey_s_c k; 285 286 bch2_trans_node_iter_init(trans, iter, 287 bp.btree_id, 288 bp.pos, 289 0, 0, 290 iter_flags); 291 k = bch2_btree_iter_peek_slot(iter); 292 if (bkey_err(k)) { 293 bch2_trans_iter_exit(trans, iter); 294 return k; 295 } 296 297 if (k.k && extent_matches_bp(c, bp.btree_id, bp.level, k, bucket, bp)) 298 return k; 299 300 bch2_trans_iter_exit(trans, iter); 301 backpointer_not_found(trans, bp_pos, bp, k); 302 return bkey_s_c_null; 303 } else { 304 struct btree *b = bch2_backpointer_get_node(trans, iter, bp_pos, bp); 305 306 if (IS_ERR_OR_NULL(b)) { 307 bch2_trans_iter_exit(trans, iter); 308 return IS_ERR(b) ? bkey_s_c_err(PTR_ERR(b)) : bkey_s_c_null; 309 } 310 return bkey_i_to_s_c(&b->key); 311 } 312 } 313 314 struct btree *bch2_backpointer_get_node(struct btree_trans *trans, 315 struct btree_iter *iter, 316 struct bpos bp_pos, 317 struct bch_backpointer bp) 318 { 319 struct bch_fs *c = trans->c; 320 struct bpos bucket = bp_pos_to_bucket(c, bp_pos); 321 struct btree *b; 322 323 BUG_ON(!bp.level); 324 325 bch2_trans_node_iter_init(trans, iter, 326 bp.btree_id, 327 bp.pos, 328 0, 329 bp.level - 1, 330 0); 331 b = bch2_btree_iter_peek_node(iter); 332 if (IS_ERR_OR_NULL(b)) 333 goto err; 334 335 BUG_ON(b->c.level != bp.level - 1); 336 337 if (extent_matches_bp(c, bp.btree_id, bp.level, 338 bkey_i_to_s_c(&b->key), 339 bucket, bp)) 340 return b; 341 342 if (btree_node_will_make_reachable(b)) { 343 b = ERR_PTR(-BCH_ERR_backpointer_to_overwritten_btree_node); 344 } else { 345 backpointer_not_found(trans, bp_pos, bp, bkey_i_to_s_c(&b->key)); 346 b = NULL; 347 } 348 err: 349 bch2_trans_iter_exit(trans, iter); 350 return b; 351 } 352 353 static int bch2_check_btree_backpointer(struct btree_trans *trans, struct btree_iter *bp_iter, 354 struct bkey_s_c k) 355 { 356 struct bch_fs *c = trans->c; 357 struct btree_iter alloc_iter = { NULL }; 358 struct bkey_s_c alloc_k; 359 struct printbuf buf = PRINTBUF; 360 int ret = 0; 361 362 if (fsck_err_on(!bch2_dev_exists2(c, k.k->p.inode), c, 363 backpointer_to_missing_device, 364 "backpointer for missing device:\n%s", 365 (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) { 366 ret = bch2_btree_delete_at(trans, bp_iter, 0); 367 goto out; 368 } 369 370 alloc_k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc, 371 bp_pos_to_bucket(c, k.k->p), 0); 372 ret = bkey_err(alloc_k); 373 if (ret) 374 goto out; 375 376 if (fsck_err_on(alloc_k.k->type != KEY_TYPE_alloc_v4, c, 377 backpointer_to_missing_alloc, 378 "backpointer for nonexistent alloc key: %llu:%llu:0\n%s", 379 alloc_iter.pos.inode, alloc_iter.pos.offset, 380 (bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf))) { 381 ret = bch2_btree_delete_at(trans, bp_iter, 0); 382 goto out; 383 } 384 out: 385 fsck_err: 386 bch2_trans_iter_exit(trans, &alloc_iter); 387 printbuf_exit(&buf); 388 return ret; 389 } 390 391 /* verify that every backpointer has a corresponding alloc key */ 392 int bch2_check_btree_backpointers(struct bch_fs *c) 393 { 394 int ret = bch2_trans_run(c, 395 for_each_btree_key_commit(trans, iter, 396 BTREE_ID_backpointers, POS_MIN, 0, k, 397 NULL, NULL, BCH_TRANS_COMMIT_no_enospc, 398 bch2_check_btree_backpointer(trans, &iter, k))); 399 bch_err_fn(c, ret); 400 return ret; 401 } 402 403 static int check_bp_exists(struct btree_trans *trans, 404 struct bpos bucket, 405 struct bch_backpointer bp, 406 struct bkey_s_c orig_k, 407 struct bpos bucket_start, 408 struct bpos bucket_end, 409 struct bkey_buf *last_flushed) 410 { 411 struct bch_fs *c = trans->c; 412 struct btree_iter bp_iter = { NULL }; 413 struct printbuf buf = PRINTBUF; 414 struct bkey_s_c bp_k; 415 struct bkey_buf tmp; 416 int ret; 417 418 bch2_bkey_buf_init(&tmp); 419 420 if (bpos_lt(bucket, bucket_start) || 421 bpos_gt(bucket, bucket_end)) 422 return 0; 423 424 if (!bch2_dev_bucket_exists(c, bucket)) 425 goto missing; 426 427 bp_k = bch2_bkey_get_iter(trans, &bp_iter, BTREE_ID_backpointers, 428 bucket_pos_to_bp(c, bucket, bp.bucket_offset), 429 0); 430 ret = bkey_err(bp_k); 431 if (ret) 432 goto err; 433 434 if (bp_k.k->type != KEY_TYPE_backpointer || 435 memcmp(bkey_s_c_to_backpointer(bp_k).v, &bp, sizeof(bp))) { 436 if (!bpos_eq(orig_k.k->p, last_flushed->k->k.p) || 437 bkey_bytes(orig_k.k) != bkey_bytes(&last_flushed->k->k) || 438 memcmp(orig_k.v, &last_flushed->k->v, bkey_val_bytes(orig_k.k))) { 439 bch2_bkey_buf_reassemble(&tmp, c, orig_k); 440 441 if (bp.level) { 442 bch2_trans_unlock(trans); 443 bch2_btree_interior_updates_flush(c); 444 } 445 446 ret = bch2_btree_write_buffer_flush_sync(trans); 447 if (ret) 448 goto err; 449 450 bch2_bkey_buf_copy(last_flushed, c, tmp.k); 451 ret = -BCH_ERR_transaction_restart_write_buffer_flush; 452 goto out; 453 } 454 goto missing; 455 } 456 out: 457 err: 458 fsck_err: 459 bch2_trans_iter_exit(trans, &bp_iter); 460 bch2_bkey_buf_exit(&tmp, c); 461 printbuf_exit(&buf); 462 return ret; 463 missing: 464 prt_printf(&buf, "missing backpointer for btree=%s l=%u ", 465 bch2_btree_id_str(bp.btree_id), bp.level); 466 bch2_bkey_val_to_text(&buf, c, orig_k); 467 prt_printf(&buf, "\nbp pos "); 468 bch2_bpos_to_text(&buf, bp_iter.pos); 469 470 if (c->opts.reconstruct_alloc || 471 fsck_err(c, ptr_to_missing_backpointer, "%s", buf.buf)) 472 ret = bch2_bucket_backpointer_mod(trans, bucket, bp, orig_k, true); 473 474 goto out; 475 } 476 477 static int check_extent_to_backpointers(struct btree_trans *trans, 478 enum btree_id btree, unsigned level, 479 struct bpos bucket_start, 480 struct bpos bucket_end, 481 struct bkey_buf *last_flushed, 482 struct bkey_s_c k) 483 { 484 struct bch_fs *c = trans->c; 485 struct bkey_ptrs_c ptrs; 486 const union bch_extent_entry *entry; 487 struct extent_ptr_decoded p; 488 int ret; 489 490 ptrs = bch2_bkey_ptrs_c(k); 491 bkey_for_each_ptr_decode(k.k, ptrs, p, entry) { 492 struct bpos bucket_pos; 493 struct bch_backpointer bp; 494 495 if (p.ptr.cached) 496 continue; 497 498 bch2_extent_ptr_to_bp(c, btree, level, 499 k, p, &bucket_pos, &bp); 500 501 ret = check_bp_exists(trans, bucket_pos, bp, k, 502 bucket_start, bucket_end, 503 last_flushed); 504 if (ret) 505 return ret; 506 } 507 508 return 0; 509 } 510 511 static int check_btree_root_to_backpointers(struct btree_trans *trans, 512 enum btree_id btree_id, 513 struct bpos bucket_start, 514 struct bpos bucket_end, 515 struct bkey_buf *last_flushed, 516 int *level) 517 { 518 struct bch_fs *c = trans->c; 519 struct btree_iter iter; 520 struct btree *b; 521 struct bkey_s_c k; 522 int ret; 523 retry: 524 bch2_trans_node_iter_init(trans, &iter, btree_id, POS_MIN, 525 0, bch2_btree_id_root(c, btree_id)->b->c.level, 0); 526 b = bch2_btree_iter_peek_node(&iter); 527 ret = PTR_ERR_OR_ZERO(b); 528 if (ret) 529 goto err; 530 531 if (b != btree_node_root(c, b)) { 532 bch2_trans_iter_exit(trans, &iter); 533 goto retry; 534 } 535 536 *level = b->c.level; 537 538 k = bkey_i_to_s_c(&b->key); 539 ret = check_extent_to_backpointers(trans, btree_id, b->c.level + 1, 540 bucket_start, bucket_end, 541 last_flushed, k); 542 err: 543 bch2_trans_iter_exit(trans, &iter); 544 return ret; 545 } 546 547 static inline struct bbpos bp_to_bbpos(struct bch_backpointer bp) 548 { 549 return (struct bbpos) { 550 .btree = bp.btree_id, 551 .pos = bp.pos, 552 }; 553 } 554 555 static size_t btree_nodes_fit_in_ram(struct bch_fs *c) 556 { 557 struct sysinfo i; 558 u64 mem_bytes; 559 560 si_meminfo(&i); 561 mem_bytes = i.totalram * i.mem_unit; 562 return div_u64(mem_bytes >> 1, btree_bytes(c)); 563 } 564 565 static int bch2_get_btree_in_memory_pos(struct btree_trans *trans, 566 unsigned btree_leaf_mask, 567 unsigned btree_interior_mask, 568 struct bbpos start, struct bbpos *end) 569 { 570 struct btree_iter iter; 571 struct bkey_s_c k; 572 size_t btree_nodes = btree_nodes_fit_in_ram(trans->c); 573 enum btree_id btree; 574 int ret = 0; 575 576 for (btree = start.btree; btree < BTREE_ID_NR && !ret; btree++) { 577 unsigned depth = ((1U << btree) & btree_leaf_mask) ? 1 : 2; 578 579 if (!((1U << btree) & btree_leaf_mask) && 580 !((1U << btree) & btree_interior_mask)) 581 continue; 582 583 bch2_trans_node_iter_init(trans, &iter, btree, 584 btree == start.btree ? start.pos : POS_MIN, 585 0, depth, 0); 586 /* 587 * for_each_btree_key_contineu() doesn't check the return value 588 * from bch2_btree_iter_advance(), which is needed when 589 * iterating over interior nodes where we'll see keys at 590 * SPOS_MAX: 591 */ 592 do { 593 k = __bch2_btree_iter_peek_and_restart(trans, &iter, 0); 594 ret = bkey_err(k); 595 if (!k.k || ret) 596 break; 597 598 --btree_nodes; 599 if (!btree_nodes) { 600 *end = BBPOS(btree, k.k->p); 601 bch2_trans_iter_exit(trans, &iter); 602 return 0; 603 } 604 } while (bch2_btree_iter_advance(&iter)); 605 bch2_trans_iter_exit(trans, &iter); 606 } 607 608 *end = BBPOS_MAX; 609 return ret; 610 } 611 612 static int bch2_check_extents_to_backpointers_pass(struct btree_trans *trans, 613 struct bpos bucket_start, 614 struct bpos bucket_end) 615 { 616 struct bch_fs *c = trans->c; 617 struct btree_iter iter; 618 enum btree_id btree_id; 619 struct bkey_s_c k; 620 struct bkey_buf last_flushed; 621 int ret = 0; 622 623 bch2_bkey_buf_init(&last_flushed); 624 bkey_init(&last_flushed.k->k); 625 626 for (btree_id = 0; btree_id < btree_id_nr_alive(c); btree_id++) { 627 int level, depth = btree_type_has_ptrs(btree_id) ? 0 : 1; 628 629 ret = commit_do(trans, NULL, NULL, 630 BCH_TRANS_COMMIT_no_enospc, 631 check_btree_root_to_backpointers(trans, btree_id, 632 bucket_start, bucket_end, 633 &last_flushed, &level)); 634 if (ret) 635 return ret; 636 637 while (level >= depth) { 638 bch2_trans_node_iter_init(trans, &iter, btree_id, POS_MIN, 0, 639 level, 640 BTREE_ITER_PREFETCH); 641 while (1) { 642 bch2_trans_begin(trans); 643 k = bch2_btree_iter_peek(&iter); 644 if (!k.k) 645 break; 646 ret = bkey_err(k) ?: 647 check_extent_to_backpointers(trans, btree_id, level, 648 bucket_start, bucket_end, 649 &last_flushed, k) ?: 650 bch2_trans_commit(trans, NULL, NULL, 651 BCH_TRANS_COMMIT_no_enospc); 652 if (bch2_err_matches(ret, BCH_ERR_transaction_restart)) { 653 ret = 0; 654 continue; 655 } 656 if (ret) 657 break; 658 if (bpos_eq(iter.pos, SPOS_MAX)) 659 break; 660 bch2_btree_iter_advance(&iter); 661 } 662 bch2_trans_iter_exit(trans, &iter); 663 664 if (ret) 665 return ret; 666 667 --level; 668 } 669 } 670 671 bch2_bkey_buf_exit(&last_flushed, c); 672 return 0; 673 } 674 675 static struct bpos bucket_pos_to_bp_safe(const struct bch_fs *c, 676 struct bpos bucket) 677 { 678 return bch2_dev_exists2(c, bucket.inode) 679 ? bucket_pos_to_bp(c, bucket, 0) 680 : bucket; 681 } 682 683 static int bch2_get_alloc_in_memory_pos(struct btree_trans *trans, 684 struct bpos start, struct bpos *end) 685 { 686 struct btree_iter alloc_iter; 687 struct btree_iter bp_iter; 688 struct bkey_s_c alloc_k, bp_k; 689 size_t btree_nodes = btree_nodes_fit_in_ram(trans->c); 690 bool alloc_end = false, bp_end = false; 691 int ret = 0; 692 693 bch2_trans_node_iter_init(trans, &alloc_iter, BTREE_ID_alloc, 694 start, 0, 1, 0); 695 bch2_trans_node_iter_init(trans, &bp_iter, BTREE_ID_backpointers, 696 bucket_pos_to_bp_safe(trans->c, start), 0, 1, 0); 697 while (1) { 698 alloc_k = !alloc_end 699 ? __bch2_btree_iter_peek_and_restart(trans, &alloc_iter, 0) 700 : bkey_s_c_null; 701 bp_k = !bp_end 702 ? __bch2_btree_iter_peek_and_restart(trans, &bp_iter, 0) 703 : bkey_s_c_null; 704 705 ret = bkey_err(alloc_k) ?: bkey_err(bp_k); 706 if ((!alloc_k.k && !bp_k.k) || ret) { 707 *end = SPOS_MAX; 708 break; 709 } 710 711 --btree_nodes; 712 if (!btree_nodes) { 713 *end = alloc_k.k ? alloc_k.k->p : SPOS_MAX; 714 break; 715 } 716 717 if (bpos_lt(alloc_iter.pos, SPOS_MAX) && 718 bpos_lt(bucket_pos_to_bp_safe(trans->c, alloc_iter.pos), bp_iter.pos)) { 719 if (!bch2_btree_iter_advance(&alloc_iter)) 720 alloc_end = true; 721 } else { 722 if (!bch2_btree_iter_advance(&bp_iter)) 723 bp_end = true; 724 } 725 } 726 bch2_trans_iter_exit(trans, &bp_iter); 727 bch2_trans_iter_exit(trans, &alloc_iter); 728 return ret; 729 } 730 731 int bch2_check_extents_to_backpointers(struct bch_fs *c) 732 { 733 struct btree_trans *trans = bch2_trans_get(c); 734 struct bpos start = POS_MIN, end; 735 int ret; 736 737 while (1) { 738 ret = bch2_get_alloc_in_memory_pos(trans, start, &end); 739 if (ret) 740 break; 741 742 if (bpos_eq(start, POS_MIN) && !bpos_eq(end, SPOS_MAX)) 743 bch_verbose(c, "%s(): alloc info does not fit in ram, running in multiple passes with %zu nodes per pass", 744 __func__, btree_nodes_fit_in_ram(c)); 745 746 if (!bpos_eq(start, POS_MIN) || !bpos_eq(end, SPOS_MAX)) { 747 struct printbuf buf = PRINTBUF; 748 749 prt_str(&buf, "check_extents_to_backpointers(): "); 750 bch2_bpos_to_text(&buf, start); 751 prt_str(&buf, "-"); 752 bch2_bpos_to_text(&buf, end); 753 754 bch_verbose(c, "%s", buf.buf); 755 printbuf_exit(&buf); 756 } 757 758 ret = bch2_check_extents_to_backpointers_pass(trans, start, end); 759 if (ret || bpos_eq(end, SPOS_MAX)) 760 break; 761 762 start = bpos_successor(end); 763 } 764 bch2_trans_put(trans); 765 766 bch_err_fn(c, ret); 767 return ret; 768 } 769 770 static int check_one_backpointer(struct btree_trans *trans, 771 struct bbpos start, 772 struct bbpos end, 773 struct bkey_s_c_backpointer bp, 774 struct bpos *last_flushed_pos) 775 { 776 struct bch_fs *c = trans->c; 777 struct btree_iter iter; 778 struct bbpos pos = bp_to_bbpos(*bp.v); 779 struct bkey_s_c k; 780 struct printbuf buf = PRINTBUF; 781 int ret; 782 783 if (bbpos_cmp(pos, start) < 0 || 784 bbpos_cmp(pos, end) > 0) 785 return 0; 786 787 k = bch2_backpointer_get_key(trans, &iter, bp.k->p, *bp.v, 0); 788 ret = bkey_err(k); 789 if (ret == -BCH_ERR_backpointer_to_overwritten_btree_node) 790 return 0; 791 if (ret) 792 return ret; 793 794 if (!k.k && !bpos_eq(*last_flushed_pos, bp.k->p)) { 795 *last_flushed_pos = bp.k->p; 796 ret = bch2_btree_write_buffer_flush_sync(trans) ?: 797 -BCH_ERR_transaction_restart_write_buffer_flush; 798 goto out; 799 } 800 801 if (fsck_err_on(!k.k, c, 802 backpointer_to_missing_ptr, 803 "backpointer for missing %s\n %s", 804 bp.v->level ? "btree node" : "extent", 805 (bch2_bkey_val_to_text(&buf, c, bp.s_c), buf.buf))) { 806 ret = bch2_btree_delete_at_buffered(trans, BTREE_ID_backpointers, bp.k->p); 807 goto out; 808 } 809 out: 810 fsck_err: 811 bch2_trans_iter_exit(trans, &iter); 812 printbuf_exit(&buf); 813 return ret; 814 } 815 816 static int bch2_check_backpointers_to_extents_pass(struct btree_trans *trans, 817 struct bbpos start, 818 struct bbpos end) 819 { 820 struct bpos last_flushed_pos = SPOS_MAX; 821 822 return for_each_btree_key_commit(trans, iter, BTREE_ID_backpointers, 823 POS_MIN, BTREE_ITER_PREFETCH, k, 824 NULL, NULL, BCH_TRANS_COMMIT_no_enospc, 825 check_one_backpointer(trans, start, end, 826 bkey_s_c_to_backpointer(k), 827 &last_flushed_pos)); 828 } 829 830 int bch2_check_backpointers_to_extents(struct bch_fs *c) 831 { 832 struct btree_trans *trans = bch2_trans_get(c); 833 struct bbpos start = (struct bbpos) { .btree = 0, .pos = POS_MIN, }, end; 834 int ret; 835 836 while (1) { 837 ret = bch2_get_btree_in_memory_pos(trans, 838 (1U << BTREE_ID_extents)| 839 (1U << BTREE_ID_reflink), 840 ~0, 841 start, &end); 842 if (ret) 843 break; 844 845 if (!bbpos_cmp(start, BBPOS_MIN) && 846 bbpos_cmp(end, BBPOS_MAX)) 847 bch_verbose(c, "%s(): extents do not fit in ram, running in multiple passes with %zu nodes per pass", 848 __func__, btree_nodes_fit_in_ram(c)); 849 850 if (bbpos_cmp(start, BBPOS_MIN) || 851 bbpos_cmp(end, BBPOS_MAX)) { 852 struct printbuf buf = PRINTBUF; 853 854 prt_str(&buf, "check_backpointers_to_extents(): "); 855 bch2_bbpos_to_text(&buf, start); 856 prt_str(&buf, "-"); 857 bch2_bbpos_to_text(&buf, end); 858 859 bch_verbose(c, "%s", buf.buf); 860 printbuf_exit(&buf); 861 } 862 863 ret = bch2_check_backpointers_to_extents_pass(trans, start, end); 864 if (ret || !bbpos_cmp(end, BBPOS_MAX)) 865 break; 866 867 start = bbpos_successor(end); 868 } 869 bch2_trans_put(trans); 870 871 bch_err_fn(c, ret); 872 return ret; 873 } 874