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