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