git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/backpointers.c

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