1069 lines · c
1// SPDX-License-Identifier: GPL-2.02#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 "checksum.h"12#include "disk_accounting.h"13#include "error.h"14 15#include <linux/mm.h>16 17static bool extent_matches_bp(struct bch_fs *c,18 enum btree_id btree_id, unsigned level,19 struct bkey_s_c k,20 struct bpos bucket,21 struct bch_backpointer bp)22{23 struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);24 const union bch_extent_entry *entry;25 struct extent_ptr_decoded p;26 27 rcu_read_lock();28 bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {29 struct bpos bucket2;30 struct bch_backpointer bp2;31 32 if (p.ptr.cached)33 continue;34 35 struct bch_dev *ca = bch2_dev_rcu(c, p.ptr.dev);36 if (!ca)37 continue;38 39 bch2_extent_ptr_to_bp(c, ca, btree_id, level, k, p, entry, &bucket2, &bp2);40 if (bpos_eq(bucket, bucket2) &&41 !memcmp(&bp, &bp2, sizeof(bp))) {42 rcu_read_unlock();43 return true;44 }45 }46 rcu_read_unlock();47 48 return false;49}50 51int bch2_backpointer_validate(struct bch_fs *c, struct bkey_s_c k,52 enum bch_validate_flags flags)53{54 struct bkey_s_c_backpointer bp = bkey_s_c_to_backpointer(k);55 int ret = 0;56 57 bkey_fsck_err_on(bp.v->level > BTREE_MAX_DEPTH,58 c, backpointer_level_bad,59 "backpointer level bad: %u >= %u",60 bp.v->level, BTREE_MAX_DEPTH);61 62 rcu_read_lock();63 struct bch_dev *ca = bch2_dev_rcu_noerror(c, bp.k->p.inode);64 if (!ca) {65 /* these will be caught by fsck */66 rcu_read_unlock();67 return 0;68 }69 70 struct bpos bucket = bp_pos_to_bucket(ca, bp.k->p);71 struct bpos bp_pos = bucket_pos_to_bp_noerror(ca, bucket, bp.v->bucket_offset);72 rcu_read_unlock();73 74 bkey_fsck_err_on((bp.v->bucket_offset >> MAX_EXTENT_COMPRESS_RATIO_SHIFT) >= ca->mi.bucket_size ||75 !bpos_eq(bp.k->p, bp_pos),76 c, backpointer_bucket_offset_wrong,77 "backpointer bucket_offset wrong");78fsck_err:79 return ret;80}81 82void bch2_backpointer_to_text(struct printbuf *out, const struct bch_backpointer *bp)83{84 prt_printf(out, "btree=%s l=%u offset=%llu:%u len=%u pos=",85 bch2_btree_id_str(bp->btree_id),86 bp->level,87 (u64) (bp->bucket_offset >> MAX_EXTENT_COMPRESS_RATIO_SHIFT),88 (u32) bp->bucket_offset & ~(~0U << MAX_EXTENT_COMPRESS_RATIO_SHIFT),89 bp->bucket_len);90 bch2_bpos_to_text(out, bp->pos);91}92 93void bch2_backpointer_k_to_text(struct printbuf *out, struct bch_fs *c, struct bkey_s_c k)94{95 rcu_read_lock();96 struct bch_dev *ca = bch2_dev_rcu_noerror(c, k.k->p.inode);97 if (ca) {98 struct bpos bucket = bp_pos_to_bucket(ca, k.k->p);99 rcu_read_unlock();100 prt_str(out, "bucket=");101 bch2_bpos_to_text(out, bucket);102 prt_str(out, " ");103 } else {104 rcu_read_unlock();105 }106 107 bch2_backpointer_to_text(out, bkey_s_c_to_backpointer(k).v);108}109 110void bch2_backpointer_swab(struct bkey_s k)111{112 struct bkey_s_backpointer bp = bkey_s_to_backpointer(k);113 114 bp.v->bucket_offset = swab40(bp.v->bucket_offset);115 bp.v->bucket_len = swab32(bp.v->bucket_len);116 bch2_bpos_swab(&bp.v->pos);117}118 119static noinline int backpointer_mod_err(struct btree_trans *trans,120 struct bch_backpointer bp,121 struct bkey_s_c bp_k,122 struct bkey_s_c orig_k,123 bool insert)124{125 struct bch_fs *c = trans->c;126 struct printbuf buf = PRINTBUF;127 128 if (insert) {129 prt_printf(&buf, "existing backpointer found when inserting ");130 bch2_backpointer_to_text(&buf, &bp);131 prt_newline(&buf);132 printbuf_indent_add(&buf, 2);133 134 prt_printf(&buf, "found ");135 bch2_bkey_val_to_text(&buf, c, bp_k);136 prt_newline(&buf);137 138 prt_printf(&buf, "for ");139 bch2_bkey_val_to_text(&buf, c, orig_k);140 141 bch_err(c, "%s", buf.buf);142 } else if (c->curr_recovery_pass > BCH_RECOVERY_PASS_check_extents_to_backpointers) {143 prt_printf(&buf, "backpointer not found when deleting\n");144 printbuf_indent_add(&buf, 2);145 146 prt_printf(&buf, "searching for ");147 bch2_backpointer_to_text(&buf, &bp);148 prt_newline(&buf);149 150 prt_printf(&buf, "got ");151 bch2_bkey_val_to_text(&buf, c, bp_k);152 prt_newline(&buf);153 154 prt_printf(&buf, "for ");155 bch2_bkey_val_to_text(&buf, c, orig_k);156 157 bch_err(c, "%s", buf.buf);158 }159 160 printbuf_exit(&buf);161 162 if (c->curr_recovery_pass > BCH_RECOVERY_PASS_check_extents_to_backpointers) {163 return bch2_inconsistent_error(c) ? BCH_ERR_erofs_unfixed_errors : 0;164 } else {165 return 0;166 }167}168 169int bch2_bucket_backpointer_mod_nowritebuffer(struct btree_trans *trans,170 struct bch_dev *ca,171 struct bpos bucket,172 struct bch_backpointer bp,173 struct bkey_s_c orig_k,174 bool insert)175{176 struct btree_iter bp_iter;177 struct bkey_s_c k;178 struct bkey_i_backpointer *bp_k;179 int ret;180 181 bp_k = bch2_trans_kmalloc_nomemzero(trans, sizeof(struct bkey_i_backpointer));182 ret = PTR_ERR_OR_ZERO(bp_k);183 if (ret)184 return ret;185 186 bkey_backpointer_init(&bp_k->k_i);187 bp_k->k.p = bucket_pos_to_bp(ca, bucket, bp.bucket_offset);188 bp_k->v = bp;189 190 if (!insert) {191 bp_k->k.type = KEY_TYPE_deleted;192 set_bkey_val_u64s(&bp_k->k, 0);193 }194 195 k = bch2_bkey_get_iter(trans, &bp_iter, BTREE_ID_backpointers,196 bp_k->k.p,197 BTREE_ITER_intent|198 BTREE_ITER_slots|199 BTREE_ITER_with_updates);200 ret = bkey_err(k);201 if (ret)202 goto err;203 204 if (insert205 ? k.k->type206 : (k.k->type != KEY_TYPE_backpointer ||207 memcmp(bkey_s_c_to_backpointer(k).v, &bp, sizeof(bp)))) {208 ret = backpointer_mod_err(trans, bp, k, orig_k, insert);209 if (ret)210 goto err;211 }212 213 ret = bch2_trans_update(trans, &bp_iter, &bp_k->k_i, 0);214err:215 bch2_trans_iter_exit(trans, &bp_iter);216 return ret;217}218 219/*220 * Find the next backpointer >= *bp_offset:221 */222int bch2_get_next_backpointer(struct btree_trans *trans,223 struct bch_dev *ca,224 struct bpos bucket, int gen,225 struct bpos *bp_pos,226 struct bch_backpointer *bp,227 unsigned iter_flags)228{229 struct bpos bp_end_pos = bucket_pos_to_bp(ca, bpos_nosnap_successor(bucket), 0);230 struct btree_iter alloc_iter = { NULL }, bp_iter = { NULL };231 struct bkey_s_c k;232 int ret = 0;233 234 if (bpos_ge(*bp_pos, bp_end_pos))235 goto done;236 237 if (gen >= 0) {238 k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc,239 bucket, BTREE_ITER_cached|iter_flags);240 ret = bkey_err(k);241 if (ret)242 goto out;243 244 if (k.k->type != KEY_TYPE_alloc_v4 ||245 bkey_s_c_to_alloc_v4(k).v->gen != gen)246 goto done;247 }248 249 *bp_pos = bpos_max(*bp_pos, bucket_pos_to_bp(ca, bucket, 0));250 251 for_each_btree_key_norestart(trans, bp_iter, BTREE_ID_backpointers,252 *bp_pos, iter_flags, k, ret) {253 if (bpos_ge(k.k->p, bp_end_pos))254 break;255 256 *bp_pos = k.k->p;257 *bp = *bkey_s_c_to_backpointer(k).v;258 goto out;259 }260done:261 *bp_pos = SPOS_MAX;262out:263 bch2_trans_iter_exit(trans, &bp_iter);264 bch2_trans_iter_exit(trans, &alloc_iter);265 return ret;266}267 268static void backpointer_not_found(struct btree_trans *trans,269 struct bpos bp_pos,270 struct bch_backpointer bp,271 struct bkey_s_c k)272{273 struct bch_fs *c = trans->c;274 struct printbuf buf = PRINTBUF;275 276 /*277 * If we're using the btree write buffer, the backpointer we were278 * looking at may have already been deleted - failure to find what it279 * pointed to is not an error:280 */281 if (likely(!bch2_backpointers_no_use_write_buffer))282 return;283 284 struct bpos bucket;285 if (!bp_pos_to_bucket_nodev(c, bp_pos, &bucket))286 return;287 288 prt_printf(&buf, "backpointer doesn't match %s it points to:\n ",289 bp.level ? "btree node" : "extent");290 prt_printf(&buf, "bucket: ");291 bch2_bpos_to_text(&buf, bucket);292 prt_printf(&buf, "\n ");293 294 prt_printf(&buf, "backpointer pos: ");295 bch2_bpos_to_text(&buf, bp_pos);296 prt_printf(&buf, "\n ");297 298 bch2_backpointer_to_text(&buf, &bp);299 prt_printf(&buf, "\n ");300 bch2_bkey_val_to_text(&buf, c, k);301 if (c->curr_recovery_pass >= BCH_RECOVERY_PASS_check_extents_to_backpointers)302 bch_err_ratelimited(c, "%s", buf.buf);303 else304 bch2_trans_inconsistent(trans, "%s", buf.buf);305 306 printbuf_exit(&buf);307}308 309struct bkey_s_c bch2_backpointer_get_key(struct btree_trans *trans,310 struct btree_iter *iter,311 struct bpos bp_pos,312 struct bch_backpointer bp,313 unsigned iter_flags)314{315 if (likely(!bp.level)) {316 struct bch_fs *c = trans->c;317 318 struct bpos bucket;319 if (!bp_pos_to_bucket_nodev(c, bp_pos, &bucket))320 return bkey_s_c_err(-EIO);321 322 bch2_trans_node_iter_init(trans, iter,323 bp.btree_id,324 bp.pos,325 0, 0,326 iter_flags);327 struct bkey_s_c k = bch2_btree_iter_peek_slot(iter);328 if (bkey_err(k)) {329 bch2_trans_iter_exit(trans, iter);330 return k;331 }332 333 if (k.k && extent_matches_bp(c, bp.btree_id, bp.level, k, bucket, bp))334 return k;335 336 bch2_trans_iter_exit(trans, iter);337 backpointer_not_found(trans, bp_pos, bp, k);338 return bkey_s_c_null;339 } else {340 struct btree *b = bch2_backpointer_get_node(trans, iter, bp_pos, bp);341 342 if (IS_ERR_OR_NULL(b)) {343 bch2_trans_iter_exit(trans, iter);344 return IS_ERR(b) ? bkey_s_c_err(PTR_ERR(b)) : bkey_s_c_null;345 }346 return bkey_i_to_s_c(&b->key);347 }348}349 350struct btree *bch2_backpointer_get_node(struct btree_trans *trans,351 struct btree_iter *iter,352 struct bpos bp_pos,353 struct bch_backpointer bp)354{355 struct bch_fs *c = trans->c;356 357 BUG_ON(!bp.level);358 359 struct bpos bucket;360 if (!bp_pos_to_bucket_nodev(c, bp_pos, &bucket))361 return ERR_PTR(-EIO);362 363 bch2_trans_node_iter_init(trans, iter,364 bp.btree_id,365 bp.pos,366 0,367 bp.level - 1,368 0);369 struct btree *b = bch2_btree_iter_peek_node(iter);370 if (IS_ERR_OR_NULL(b))371 goto err;372 373 BUG_ON(b->c.level != bp.level - 1);374 375 if (extent_matches_bp(c, bp.btree_id, bp.level,376 bkey_i_to_s_c(&b->key),377 bucket, bp))378 return b;379 380 if (btree_node_will_make_reachable(b)) {381 b = ERR_PTR(-BCH_ERR_backpointer_to_overwritten_btree_node);382 } else {383 backpointer_not_found(trans, bp_pos, bp, bkey_i_to_s_c(&b->key));384 b = NULL;385 }386err:387 bch2_trans_iter_exit(trans, iter);388 return b;389}390 391static int bch2_check_btree_backpointer(struct btree_trans *trans, struct btree_iter *bp_iter,392 struct bkey_s_c k)393{394 struct bch_fs *c = trans->c;395 struct btree_iter alloc_iter = { NULL };396 struct bkey_s_c alloc_k;397 struct printbuf buf = PRINTBUF;398 int ret = 0;399 400 struct bpos bucket;401 if (!bp_pos_to_bucket_nodev_noerror(c, k.k->p, &bucket)) {402 if (fsck_err(trans, backpointer_to_missing_device,403 "backpointer for missing device:\n%s",404 (bch2_bkey_val_to_text(&buf, c, k), buf.buf)))405 ret = bch2_btree_delete_at(trans, bp_iter, 0);406 goto out;407 }408 409 alloc_k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc, bucket, 0);410 ret = bkey_err(alloc_k);411 if (ret)412 goto out;413 414 if (fsck_err_on(alloc_k.k->type != KEY_TYPE_alloc_v4,415 trans, backpointer_to_missing_alloc,416 "backpointer for nonexistent alloc key: %llu:%llu:0\n%s",417 alloc_iter.pos.inode, alloc_iter.pos.offset,418 (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {419 ret = bch2_btree_delete_at(trans, bp_iter, 0);420 goto out;421 }422out:423fsck_err:424 bch2_trans_iter_exit(trans, &alloc_iter);425 printbuf_exit(&buf);426 return ret;427}428 429/* verify that every backpointer has a corresponding alloc key */430int bch2_check_btree_backpointers(struct bch_fs *c)431{432 int ret = bch2_trans_run(c,433 for_each_btree_key_commit(trans, iter,434 BTREE_ID_backpointers, POS_MIN, 0, k,435 NULL, NULL, BCH_TRANS_COMMIT_no_enospc,436 bch2_check_btree_backpointer(trans, &iter, k)));437 bch_err_fn(c, ret);438 return ret;439}440 441struct extents_to_bp_state {442 struct bpos bucket_start;443 struct bpos bucket_end;444 struct bkey_buf last_flushed;445};446 447static int drop_dev_and_update(struct btree_trans *trans, enum btree_id btree,448 struct bkey_s_c extent, unsigned dev)449{450 struct bkey_i *n = bch2_bkey_make_mut_noupdate(trans, extent);451 int ret = PTR_ERR_OR_ZERO(n);452 if (ret)453 return ret;454 455 bch2_bkey_drop_device(bkey_i_to_s(n), dev);456 return bch2_btree_insert_trans(trans, btree, n, 0);457}458 459static int check_extent_checksum(struct btree_trans *trans,460 enum btree_id btree, struct bkey_s_c extent,461 enum btree_id o_btree, struct bkey_s_c extent2, unsigned dev)462{463 struct bch_fs *c = trans->c;464 struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(extent);465 const union bch_extent_entry *entry;466 struct extent_ptr_decoded p;467 struct printbuf buf = PRINTBUF;468 void *data_buf = NULL;469 struct bio *bio = NULL;470 size_t bytes;471 int ret = 0;472 473 if (bkey_is_btree_ptr(extent.k))474 return false;475 476 bkey_for_each_ptr_decode(extent.k, ptrs, p, entry)477 if (p.ptr.dev == dev)478 goto found;479 BUG();480found:481 if (!p.crc.csum_type)482 return false;483 484 bytes = p.crc.compressed_size << 9;485 486 struct bch_dev *ca = bch2_dev_get_ioref(c, dev, READ);487 if (!ca)488 return false;489 490 data_buf = kvmalloc(bytes, GFP_KERNEL);491 if (!data_buf) {492 ret = -ENOMEM;493 goto err;494 }495 496 bio = bio_alloc(ca->disk_sb.bdev, buf_pages(data_buf, bytes), REQ_OP_READ, GFP_KERNEL);497 bio->bi_iter.bi_sector = p.ptr.offset;498 bch2_bio_map(bio, data_buf, bytes);499 ret = submit_bio_wait(bio);500 if (ret)501 goto err;502 503 prt_str(&buf, "extents pointing to same space, but first extent checksum bad:");504 prt_printf(&buf, "\n %s ", bch2_btree_id_str(btree));505 bch2_bkey_val_to_text(&buf, c, extent);506 prt_printf(&buf, "\n %s ", bch2_btree_id_str(o_btree));507 bch2_bkey_val_to_text(&buf, c, extent2);508 509 struct nonce nonce = extent_nonce(extent.k->bversion, p.crc);510 struct bch_csum csum = bch2_checksum(c, p.crc.csum_type, nonce, data_buf, bytes);511 if (fsck_err_on(bch2_crc_cmp(csum, p.crc.csum),512 trans, dup_backpointer_to_bad_csum_extent,513 "%s", buf.buf))514 ret = drop_dev_and_update(trans, btree, extent, dev) ?: 1;515fsck_err:516err:517 if (bio)518 bio_put(bio);519 kvfree(data_buf);520 percpu_ref_put(&ca->io_ref);521 printbuf_exit(&buf);522 return ret;523}524 525static int check_bp_exists(struct btree_trans *trans,526 struct extents_to_bp_state *s,527 struct bpos bucket,528 struct bch_backpointer bp,529 struct bkey_s_c orig_k)530{531 struct bch_fs *c = trans->c;532 struct btree_iter bp_iter = {};533 struct btree_iter other_extent_iter = {};534 struct printbuf buf = PRINTBUF;535 struct bkey_s_c bp_k;536 int ret = 0;537 538 struct bch_dev *ca = bch2_dev_bucket_tryget(c, bucket);539 if (!ca) {540 prt_str(&buf, "extent for nonexistent device:bucket ");541 bch2_bpos_to_text(&buf, bucket);542 prt_str(&buf, "\n ");543 bch2_bkey_val_to_text(&buf, c, orig_k);544 bch_err(c, "%s", buf.buf);545 ret = -BCH_ERR_fsck_repair_unimplemented;546 goto err;547 }548 549 if (bpos_lt(bucket, s->bucket_start) ||550 bpos_gt(bucket, s->bucket_end))551 goto out;552 553 bp_k = bch2_bkey_get_iter(trans, &bp_iter, BTREE_ID_backpointers,554 bucket_pos_to_bp(ca, bucket, bp.bucket_offset),555 0);556 ret = bkey_err(bp_k);557 if (ret)558 goto err;559 560 if (bp_k.k->type != KEY_TYPE_backpointer ||561 memcmp(bkey_s_c_to_backpointer(bp_k).v, &bp, sizeof(bp))) {562 ret = bch2_btree_write_buffer_maybe_flush(trans, orig_k, &s->last_flushed);563 if (ret)564 goto err;565 566 goto check_existing_bp;567 }568out:569err:570fsck_err:571 bch2_trans_iter_exit(trans, &other_extent_iter);572 bch2_trans_iter_exit(trans, &bp_iter);573 bch2_dev_put(ca);574 printbuf_exit(&buf);575 return ret;576check_existing_bp:577 /* Do we have a backpointer for a different extent? */578 if (bp_k.k->type != KEY_TYPE_backpointer)579 goto missing;580 581 struct bch_backpointer other_bp = *bkey_s_c_to_backpointer(bp_k).v;582 583 struct bkey_s_c other_extent =584 bch2_backpointer_get_key(trans, &other_extent_iter, bp_k.k->p, other_bp, 0);585 ret = bkey_err(other_extent);586 if (ret == -BCH_ERR_backpointer_to_overwritten_btree_node)587 ret = 0;588 if (ret)589 goto err;590 591 if (!other_extent.k)592 goto missing;593 594 if (bch2_extents_match(orig_k, other_extent)) {595 printbuf_reset(&buf);596 prt_printf(&buf, "duplicate versions of same extent, deleting smaller\n ");597 bch2_bkey_val_to_text(&buf, c, orig_k);598 prt_str(&buf, "\n ");599 bch2_bkey_val_to_text(&buf, c, other_extent);600 bch_err(c, "%s", buf.buf);601 602 if (other_extent.k->size <= orig_k.k->size) {603 ret = drop_dev_and_update(trans, other_bp.btree_id, other_extent, bucket.inode);604 if (ret)605 goto err;606 goto out;607 } else {608 ret = drop_dev_and_update(trans, bp.btree_id, orig_k, bucket.inode);609 if (ret)610 goto err;611 goto missing;612 }613 }614 615 ret = check_extent_checksum(trans, other_bp.btree_id, other_extent, bp.btree_id, orig_k, bucket.inode);616 if (ret < 0)617 goto err;618 if (ret) {619 ret = 0;620 goto missing;621 }622 623 ret = check_extent_checksum(trans, bp.btree_id, orig_k, other_bp.btree_id, other_extent, bucket.inode);624 if (ret < 0)625 goto err;626 if (ret) {627 ret = 0;628 goto out;629 }630 631 printbuf_reset(&buf);632 prt_printf(&buf, "duplicate extents pointing to same space on dev %llu\n ", bucket.inode);633 bch2_bkey_val_to_text(&buf, c, orig_k);634 prt_str(&buf, "\n ");635 bch2_bkey_val_to_text(&buf, c, other_extent);636 bch_err(c, "%s", buf.buf);637 ret = -BCH_ERR_fsck_repair_unimplemented;638 goto err;639missing:640 printbuf_reset(&buf);641 prt_printf(&buf, "missing backpointer for btree=%s l=%u ",642 bch2_btree_id_str(bp.btree_id), bp.level);643 bch2_bkey_val_to_text(&buf, c, orig_k);644 prt_printf(&buf, "\n got: ");645 bch2_bkey_val_to_text(&buf, c, bp_k);646 647 struct bkey_i_backpointer n_bp_k;648 bkey_backpointer_init(&n_bp_k.k_i);649 n_bp_k.k.p = bucket_pos_to_bp(ca, bucket, bp.bucket_offset);650 n_bp_k.v = bp;651 prt_printf(&buf, "\n want: ");652 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&n_bp_k.k_i));653 654 if (fsck_err(trans, ptr_to_missing_backpointer, "%s", buf.buf))655 ret = bch2_bucket_backpointer_mod(trans, ca, bucket, bp, orig_k, true);656 657 goto out;658}659 660static int check_extent_to_backpointers(struct btree_trans *trans,661 struct extents_to_bp_state *s,662 enum btree_id btree, unsigned level,663 struct bkey_s_c k)664{665 struct bch_fs *c = trans->c;666 struct bkey_ptrs_c ptrs;667 const union bch_extent_entry *entry;668 struct extent_ptr_decoded p;669 int ret;670 671 ptrs = bch2_bkey_ptrs_c(k);672 bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {673 struct bpos bucket_pos = POS_MIN;674 struct bch_backpointer bp;675 676 if (p.ptr.cached)677 continue;678 679 rcu_read_lock();680 struct bch_dev *ca = bch2_dev_rcu_noerror(c, p.ptr.dev);681 if (ca)682 bch2_extent_ptr_to_bp(c, ca, btree, level, k, p, entry, &bucket_pos, &bp);683 rcu_read_unlock();684 685 if (!ca)686 continue;687 688 ret = check_bp_exists(trans, s, bucket_pos, bp, k);689 if (ret)690 return ret;691 }692 693 return 0;694}695 696static int check_btree_root_to_backpointers(struct btree_trans *trans,697 struct extents_to_bp_state *s,698 enum btree_id btree_id,699 int *level)700{701 struct bch_fs *c = trans->c;702 struct btree_iter iter;703 struct btree *b;704 struct bkey_s_c k;705 int ret;706retry:707 bch2_trans_node_iter_init(trans, &iter, btree_id, POS_MIN,708 0, bch2_btree_id_root(c, btree_id)->b->c.level, 0);709 b = bch2_btree_iter_peek_node(&iter);710 ret = PTR_ERR_OR_ZERO(b);711 if (ret)712 goto err;713 714 if (b != btree_node_root(c, b)) {715 bch2_trans_iter_exit(trans, &iter);716 goto retry;717 }718 719 *level = b->c.level;720 721 k = bkey_i_to_s_c(&b->key);722 ret = check_extent_to_backpointers(trans, s, btree_id, b->c.level + 1, k);723err:724 bch2_trans_iter_exit(trans, &iter);725 return ret;726}727 728static inline struct bbpos bp_to_bbpos(struct bch_backpointer bp)729{730 return (struct bbpos) {731 .btree = bp.btree_id,732 .pos = bp.pos,733 };734}735 736static u64 mem_may_pin_bytes(struct bch_fs *c)737{738 struct sysinfo i;739 si_meminfo(&i);740 741 u64 mem_bytes = i.totalram * i.mem_unit;742 return div_u64(mem_bytes * c->opts.fsck_memory_usage_percent, 100);743}744 745static size_t btree_nodes_fit_in_ram(struct bch_fs *c)746{747 return div_u64(mem_may_pin_bytes(c), c->opts.btree_node_size);748}749 750static int bch2_get_btree_in_memory_pos(struct btree_trans *trans,751 u64 btree_leaf_mask,752 u64 btree_interior_mask,753 struct bbpos start, struct bbpos *end)754{755 struct bch_fs *c = trans->c;756 s64 mem_may_pin = mem_may_pin_bytes(c);757 int ret = 0;758 759 bch2_btree_cache_unpin(c);760 761 btree_interior_mask |= btree_leaf_mask;762 763 c->btree_cache.pinned_nodes_mask[0] = btree_leaf_mask;764 c->btree_cache.pinned_nodes_mask[1] = btree_interior_mask;765 c->btree_cache.pinned_nodes_start = start;766 c->btree_cache.pinned_nodes_end = *end = BBPOS_MAX;767 768 for (enum btree_id btree = start.btree;769 btree < BTREE_ID_NR && !ret;770 btree++) {771 unsigned depth = (BIT_ULL(btree) & btree_leaf_mask) ? 0 : 1;772 773 if (!(BIT_ULL(btree) & btree_leaf_mask) &&774 !(BIT_ULL(btree) & btree_interior_mask))775 continue;776 777 ret = __for_each_btree_node(trans, iter, btree,778 btree == start.btree ? start.pos : POS_MIN,779 0, depth, BTREE_ITER_prefetch, b, ({780 mem_may_pin -= btree_buf_bytes(b);781 if (mem_may_pin <= 0) {782 c->btree_cache.pinned_nodes_end = *end =783 BBPOS(btree, b->key.k.p);784 break;785 }786 bch2_node_pin(c, b);787 0;788 }));789 }790 791 return ret;792}793 794struct progress_indicator_state {795 unsigned long next_print;796 u64 nodes_seen;797 u64 nodes_total;798 struct btree *last_node;799};800 801static inline void progress_init(struct progress_indicator_state *s,802 struct bch_fs *c,803 u64 btree_id_mask)804{805 memset(s, 0, sizeof(*s));806 807 s->next_print = jiffies + HZ * 10;808 809 for (unsigned i = 0; i < BTREE_ID_NR; i++) {810 if (!(btree_id_mask & BIT_ULL(i)))811 continue;812 813 struct disk_accounting_pos acc = {814 .type = BCH_DISK_ACCOUNTING_btree,815 .btree.id = i,816 };817 818 u64 v;819 bch2_accounting_mem_read(c, disk_accounting_pos_to_bpos(&acc), &v, 1);820 s->nodes_total += div64_ul(v, btree_sectors(c));821 }822}823 824static inline bool progress_update_p(struct progress_indicator_state *s)825{826 bool ret = time_after_eq(jiffies, s->next_print);827 828 if (ret)829 s->next_print = jiffies + HZ * 10;830 return ret;831}832 833static void progress_update_iter(struct btree_trans *trans,834 struct progress_indicator_state *s,835 struct btree_iter *iter,836 const char *msg)837{838 struct bch_fs *c = trans->c;839 struct btree *b = path_l(btree_iter_path(trans, iter))->b;840 841 s->nodes_seen += b != s->last_node;842 s->last_node = b;843 844 if (progress_update_p(s)) {845 struct printbuf buf = PRINTBUF;846 unsigned percent = s->nodes_total847 ? div64_u64(s->nodes_seen * 100, s->nodes_total)848 : 0;849 850 prt_printf(&buf, "%s: %d%%, done %llu/%llu nodes, at ",851 msg, percent, s->nodes_seen, s->nodes_total);852 bch2_bbpos_to_text(&buf, BBPOS(iter->btree_id, iter->pos));853 854 bch_info(c, "%s", buf.buf);855 printbuf_exit(&buf);856 }857}858 859static int bch2_check_extents_to_backpointers_pass(struct btree_trans *trans,860 struct extents_to_bp_state *s)861{862 struct bch_fs *c = trans->c;863 struct progress_indicator_state progress;864 int ret = 0;865 866 progress_init(&progress, trans->c, BIT_ULL(BTREE_ID_extents)|BIT_ULL(BTREE_ID_reflink));867 868 for (enum btree_id btree_id = 0;869 btree_id < btree_id_nr_alive(c);870 btree_id++) {871 int level, depth = btree_type_has_ptrs(btree_id) ? 0 : 1;872 873 ret = commit_do(trans, NULL, NULL,874 BCH_TRANS_COMMIT_no_enospc,875 check_btree_root_to_backpointers(trans, s, btree_id, &level));876 if (ret)877 return ret;878 879 while (level >= depth) {880 struct btree_iter iter;881 bch2_trans_node_iter_init(trans, &iter, btree_id, POS_MIN, 0, level,882 BTREE_ITER_prefetch);883 884 ret = for_each_btree_key_continue(trans, iter, 0, k, ({885 progress_update_iter(trans, &progress, &iter, "extents_to_backpointers");886 check_extent_to_backpointers(trans, s, btree_id, level, k) ?:887 bch2_trans_commit(trans, NULL, NULL, BCH_TRANS_COMMIT_no_enospc);888 }));889 if (ret)890 return ret;891 892 --level;893 }894 }895 896 return 0;897}898 899int bch2_check_extents_to_backpointers(struct bch_fs *c)900{901 struct btree_trans *trans = bch2_trans_get(c);902 struct extents_to_bp_state s = { .bucket_start = POS_MIN };903 int ret;904 905 bch2_bkey_buf_init(&s.last_flushed);906 bkey_init(&s.last_flushed.k->k);907 908 while (1) {909 struct bbpos end;910 ret = bch2_get_btree_in_memory_pos(trans,911 BIT_ULL(BTREE_ID_backpointers),912 BIT_ULL(BTREE_ID_backpointers),913 BBPOS(BTREE_ID_backpointers, s.bucket_start), &end);914 if (ret)915 break;916 917 s.bucket_end = end.pos;918 919 if ( bpos_eq(s.bucket_start, POS_MIN) &&920 !bpos_eq(s.bucket_end, SPOS_MAX))921 bch_verbose(c, "%s(): alloc info does not fit in ram, running in multiple passes with %zu nodes per pass",922 __func__, btree_nodes_fit_in_ram(c));923 924 if (!bpos_eq(s.bucket_start, POS_MIN) ||925 !bpos_eq(s.bucket_end, SPOS_MAX)) {926 struct printbuf buf = PRINTBUF;927 928 prt_str(&buf, "check_extents_to_backpointers(): ");929 bch2_bpos_to_text(&buf, s.bucket_start);930 prt_str(&buf, "-");931 bch2_bpos_to_text(&buf, s.bucket_end);932 933 bch_verbose(c, "%s", buf.buf);934 printbuf_exit(&buf);935 }936 937 ret = bch2_check_extents_to_backpointers_pass(trans, &s);938 if (ret || bpos_eq(s.bucket_end, SPOS_MAX))939 break;940 941 s.bucket_start = bpos_successor(s.bucket_end);942 }943 bch2_trans_put(trans);944 bch2_bkey_buf_exit(&s.last_flushed, c);945 946 bch2_btree_cache_unpin(c);947 948 bch_err_fn(c, ret);949 return ret;950}951 952static int check_one_backpointer(struct btree_trans *trans,953 struct bbpos start,954 struct bbpos end,955 struct bkey_s_c bp_k,956 struct bkey_buf *last_flushed)957{958 if (bp_k.k->type != KEY_TYPE_backpointer)959 return 0;960 961 struct bkey_s_c_backpointer bp = bkey_s_c_to_backpointer(bp_k);962 struct bch_fs *c = trans->c;963 struct btree_iter iter;964 struct bbpos pos = bp_to_bbpos(*bp.v);965 struct bkey_s_c k;966 struct printbuf buf = PRINTBUF;967 int ret;968 969 if (bbpos_cmp(pos, start) < 0 ||970 bbpos_cmp(pos, end) > 0)971 return 0;972 973 k = bch2_backpointer_get_key(trans, &iter, bp.k->p, *bp.v, 0);974 ret = bkey_err(k);975 if (ret == -BCH_ERR_backpointer_to_overwritten_btree_node)976 return 0;977 if (ret)978 return ret;979 980 if (!k.k) {981 ret = bch2_btree_write_buffer_maybe_flush(trans, bp.s_c, last_flushed);982 if (ret)983 goto out;984 985 if (fsck_err(trans, backpointer_to_missing_ptr,986 "backpointer for missing %s\n %s",987 bp.v->level ? "btree node" : "extent",988 (bch2_bkey_val_to_text(&buf, c, bp.s_c), buf.buf))) {989 ret = bch2_btree_delete_at_buffered(trans, BTREE_ID_backpointers, bp.k->p);990 goto out;991 }992 }993out:994fsck_err:995 bch2_trans_iter_exit(trans, &iter);996 printbuf_exit(&buf);997 return ret;998}999 1000static int bch2_check_backpointers_to_extents_pass(struct btree_trans *trans,1001 struct bbpos start,1002 struct bbpos end)1003{1004 struct bch_fs *c = trans->c;1005 struct bkey_buf last_flushed;1006 struct progress_indicator_state progress;1007 1008 bch2_bkey_buf_init(&last_flushed);1009 bkey_init(&last_flushed.k->k);1010 progress_init(&progress, trans->c, BIT_ULL(BTREE_ID_backpointers));1011 1012 int ret = for_each_btree_key_commit(trans, iter, BTREE_ID_backpointers,1013 POS_MIN, BTREE_ITER_prefetch, k,1014 NULL, NULL, BCH_TRANS_COMMIT_no_enospc, ({1015 progress_update_iter(trans, &progress, &iter, "backpointers_to_extents");1016 check_one_backpointer(trans, start, end, k, &last_flushed);1017 }));1018 1019 bch2_bkey_buf_exit(&last_flushed, c);1020 return ret;1021}1022 1023int bch2_check_backpointers_to_extents(struct bch_fs *c)1024{1025 struct btree_trans *trans = bch2_trans_get(c);1026 struct bbpos start = (struct bbpos) { .btree = 0, .pos = POS_MIN, }, end;1027 int ret;1028 1029 while (1) {1030 ret = bch2_get_btree_in_memory_pos(trans,1031 BIT_ULL(BTREE_ID_extents)|1032 BIT_ULL(BTREE_ID_reflink),1033 ~0,1034 start, &end);1035 if (ret)1036 break;1037 1038 if (!bbpos_cmp(start, BBPOS_MIN) &&1039 bbpos_cmp(end, BBPOS_MAX))1040 bch_verbose(c, "%s(): extents do not fit in ram, running in multiple passes with %zu nodes per pass",1041 __func__, btree_nodes_fit_in_ram(c));1042 1043 if (bbpos_cmp(start, BBPOS_MIN) ||1044 bbpos_cmp(end, BBPOS_MAX)) {1045 struct printbuf buf = PRINTBUF;1046 1047 prt_str(&buf, "check_backpointers_to_extents(): ");1048 bch2_bbpos_to_text(&buf, start);1049 prt_str(&buf, "-");1050 bch2_bbpos_to_text(&buf, end);1051 1052 bch_verbose(c, "%s", buf.buf);1053 printbuf_exit(&buf);1054 }1055 1056 ret = bch2_check_backpointers_to_extents_pass(trans, start, end);1057 if (ret || !bbpos_cmp(end, BBPOS_MAX))1058 break;1059 1060 start = bbpos_successor(end);1061 }1062 bch2_trans_put(trans);1063 1064 bch2_btree_cache_unpin(c);1065 1066 bch_err_fn(c, ret);1067 return ret;1068}1069