fs/bcachefs/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         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 }