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