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