// SPDX-License-Identifier: GPL-2.0
#include "bcachefs.h"
#include "bbpos.h"
#include "alloc_background.h"
#include "backpointers.h"
#include "bkey_buf.h"
#include "btree_cache.h"
#include "btree_update.h"
#include "btree_update_interior.h"
#include "btree_write_buffer.h"
#include "checksum.h"
#include "disk_accounting.h"
#include "error.h"
#include "progress.h"
#include "recovery_passes.h"

#include <linux/mm.h>

static int bch2_bucket_bitmap_set(struct bch_dev *, struct bucket_bitmap *, u64);

static inline struct bbpos bp_to_bbpos(struct bch_backpointer bp)
{
 return (struct bbpos) {
  .btree = bp.btree_id,
  .pos = bp.pos,
 };
}

int bch2_backpointer_validate(struct bch_fs *c, struct bkey_s_c k,
         struct bkey_validate_context from)
{
 struct bkey_s_c_backpointer bp = bkey_s_c_to_backpointer(k);
 int ret = 0;

 bkey_fsck_err_on(bp.v->level > BTREE_MAX_DEPTH,
    c, backpointer_level_bad,
    "backpointer level bad: %u >= %u",
    bp.v->level, BTREE_MAX_DEPTH);

 bkey_fsck_err_on(bp.k->p.inode == BCH_SB_MEMBER_INVALID,
    c, backpointer_dev_bad,
    "backpointer for BCH_SB_MEMBER_INVALID");
fsck_err:
 return ret;
}

void bch2_backpointer_to_text(struct printbuf *out, struct bch_fs *c, struct bkey_s_c k)
{
 struct bkey_s_c_backpointer bp = bkey_s_c_to_backpointer(k);

 struct bch_dev *ca;
 u32 bucket_offset;
 struct bpos bucket;
 scoped_guard(rcu) {
  ca = bch2_dev_rcu_noerror(c, bp.k->p.inode);
  if (ca)
   bucket = bp_pos_to_bucket_and_offset(ca, bp.k->p, &bucket_offset);
 }

 if (ca)
  prt_printf(out, "bucket=%llu:%llu:%u ", bucket.inode, bucket.offset, bucket_offset);
 else
  prt_printf(out, "sector=%llu:%llu ", bp.k->p.inode, bp.k->p.offset >> MAX_EXTENT_COMPRESS_RATIO_SHIFT);

 bch2_btree_id_level_to_text(out, bp.v->btree_id, bp.v->level);
 prt_str(out, " data_type=");
 bch2_prt_data_type(out, bp.v->data_type);
 prt_printf(out, " suboffset=%u len=%u gen=%u pos=",
     (u32) bp.k->p.offset & ~(~0U << MAX_EXTENT_COMPRESS_RATIO_SHIFT),
     bp.v->bucket_len,
     bp.v->bucket_gen);
 bch2_bpos_to_text(out, bp.v->pos);
}

void bch2_backpointer_swab(struct bkey_s k)
{
 struct bkey_s_backpointer bp = bkey_s_to_backpointer(k);

 bp.v->bucket_len = swab32(bp.v->bucket_len);
 bch2_bpos_swab(&bp.v->pos);
}

static bool extent_matches_bp(struct bch_fs *c,
         enum btree_id btree_id, unsigned level,
         struct bkey_s_c k,
         struct bkey_s_c_backpointer bp)
{
 struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 const union bch_extent_entry *entry;
 struct extent_ptr_decoded p;

 bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
  struct bkey_i_backpointer bp2;
  bch2_extent_ptr_to_bp(c, btree_id, level, k, p, entry, &bp2);

  if (bpos_eq(bp.k->p, bp2.k.p) &&
      !memcmp(bp.v, &bp2.v, sizeof(bp2.v)))
   return true;
 }

 return false;
}

static noinline int backpointer_mod_err(struct btree_trans *trans,
     struct bkey_s_c orig_k,
     struct bkey_i_backpointer *new_bp,
     struct bkey_s_c found_bp,
     bool insert)
{
 struct bch_fs *c = trans->c;
 struct printbuf buf = PRINTBUF;
 bool will_check = c->recovery.passes_to_run &
  BIT_ULL(BCH_RECOVERY_PASS_check_extents_to_backpointers);
 int ret = 0;

 if (insert) {
  prt_printf(&buf, "existing backpointer found when inserting ");
  bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&new_bp->k_i));
  prt_newline(&buf);
  printbuf_indent_add(&buf, 2);

  prt_printf(&buf, "found ");
  bch2_bkey_val_to_text(&buf, c, found_bp);
  prt_newline(&buf);

  prt_printf(&buf, "for ");
  bch2_bkey_val_to_text(&buf, c, orig_k);
 } else if (!will_check) {
  prt_printf(&buf, "backpointer not found when deleting\n");
  printbuf_indent_add(&buf, 2);

  prt_printf(&buf, "searching for ");
  bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&new_bp->k_i));
  prt_newline(&buf);

  prt_printf(&buf, "got ");
  bch2_bkey_val_to_text(&buf, c, found_bp);
  prt_newline(&buf);

  prt_printf(&buf, "for ");
  bch2_bkey_val_to_text(&buf, c, orig_k);
 }

 if (!will_check && __bch2_inconsistent_error(c, &buf))
  ret = bch_err_throw(c, erofs_unfixed_errors);

 bch_err(c, "%s", buf.buf);
 printbuf_exit(&buf);
 return ret;
}

int bch2_bucket_backpointer_mod_nowritebuffer(struct btree_trans *trans,
    struct bkey_s_c orig_k,
    struct bkey_i_backpointer *bp,
    bool insert)
{
 struct btree_iter bp_iter;
 struct bkey_s_c k = bch2_bkey_get_iter(trans, &bp_iter, BTREE_ID_backpointers,
          bp->k.p,
          BTREE_ITER_intent|
          BTREE_ITER_slots|
          BTREE_ITER_with_updates);
 int ret = bkey_err(k);
 if (ret)
  return ret;

 if (insert
     ? k.k->type
     : (k.k->type != KEY_TYPE_backpointer ||
        memcmp(bkey_s_c_to_backpointer(k).v, &bp->v, sizeof(bp->v)))) {
  ret = backpointer_mod_err(trans, orig_k, bp, k, insert);
  if (ret)
   goto err;
 }

 if (!insert) {
  bp->k.type = KEY_TYPE_deleted;
  set_bkey_val_u64s(&bp->k, 0);
 }

 ret = bch2_trans_update(trans, &bp_iter, &bp->k_i, 0);
err:
 bch2_trans_iter_exit(trans, &bp_iter);
 return ret;
}

static int bch2_backpointer_del(struct btree_trans *trans, struct bpos pos)
{
 return (!static_branch_unlikely(&bch2_backpointers_no_use_write_buffer)
  ? bch2_btree_delete_at_buffered(trans, BTREE_ID_backpointers, pos)
  : bch2_btree_delete(trans, BTREE_ID_backpointers, pos, 0)) ?:
   bch2_trans_commit(trans, NULL, NULL, BCH_TRANS_COMMIT_no_enospc);
}

static inline int bch2_backpointers_maybe_flush(struct btree_trans *trans,
      struct bkey_s_c visiting_k,
      struct bkey_buf *last_flushed)
{
 return !static_branch_unlikely(&bch2_backpointers_no_use_write_buffer)
  ? bch2_btree_write_buffer_maybe_flush(trans, visiting_k, last_flushed)
  : 0;
}

static int backpointer_target_not_found(struct btree_trans *trans,
      struct bkey_s_c_backpointer bp,
      struct bkey_s_c target_k,
      struct bkey_buf *last_flushed,
      bool commit)
{
 struct bch_fs *c = trans->c;
 struct printbuf buf = PRINTBUF;
 int ret = 0;

 /*
  * If we're using the btree write buffer, the backpointer we were
  * looking at may have already been deleted - failure to find what it
  * pointed to is not an error:
 */
 ret = last_flushed
  ? bch2_backpointers_maybe_flush(trans, bp.s_c, last_flushed)
  : 0;
 if (ret)
  return ret;

 prt_printf(&buf, "backpointer doesn't match %s it points to:\n",
     bp.v->level ? "btree node" : "extent");
 bch2_bkey_val_to_text(&buf, c, bp.s_c);

 prt_newline(&buf);
 bch2_bkey_val_to_text(&buf, c, target_k);

 struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(target_k);
 const union bch_extent_entry *entry;
 struct extent_ptr_decoded p;
 bkey_for_each_ptr_decode(target_k.k, ptrs, p, entry)
  if (p.ptr.dev == bp.k->p.inode) {
   prt_newline(&buf);
   struct bkey_i_backpointer bp2;
   bch2_extent_ptr_to_bp(c, bp.v->btree_id, bp.v->level, target_k, p, entry, &bp2);
   bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&bp2.k_i));
  }

 if (fsck_err(trans, backpointer_to_missing_ptr,
       "%s", buf.buf)) {
  ret = bch2_backpointer_del(trans, bp.k->p);
  if (ret || !commit)
   goto out;

  /*
   * Normally, on transaction commit from inside a transaction,
   * we'll return -BCH_ERR_transaction_restart_nested, since a
   * transaction commit invalidates pointers given out by peek().
   *
   * However, since we're updating a write buffer btree, if we
   * return a transaction restart and loop we won't see that the
   * backpointer has been deleted without an additional write
   * buffer flush - and those are expensive.
   *
   * So we're relying on the caller immediately advancing to the
   * next backpointer and starting a new transaction immediately
   * after backpointer_get_key() returns NULL:
 */
  ret = bch2_trans_commit(trans, NULL, NULL, BCH_TRANS_COMMIT_no_enospc);
 }
out:
fsck_err:
 printbuf_exit(&buf);
 return ret;
}

static struct btree *__bch2_backpointer_get_node(struct btree_trans *trans,
       struct bkey_s_c_backpointer bp,
       struct btree_iter *iter,
       struct bkey_buf *last_flushed,
       bool commit)
{
 struct bch_fs *c = trans->c;

 BUG_ON(!bp.v->level);

 bch2_trans_node_iter_init(trans, iter,
      bp.v->btree_id,
      bp.v->pos,
      0,
      bp.v->level - 1,
      0);
 struct btree *b = bch2_btree_iter_peek_node(trans, iter);
 if (IS_ERR_OR_NULL(b))
  goto err;

 BUG_ON(b->c.level != bp.v->level - 1);

 if (extent_matches_bp(c, bp.v->btree_id, bp.v->level,
         bkey_i_to_s_c(&b->key), bp))
  return b;

 if (btree_node_will_make_reachable(b)) {
  b = ERR_PTR(bch_err_throw(c, backpointer_to_overwritten_btree_node));
 } else {
  int ret = backpointer_target_not_found(trans, bp, bkey_i_to_s_c(&b->key),
             last_flushed, commit);
  b = ret ? ERR_PTR(ret) : NULL;
 }
err:
 bch2_trans_iter_exit(trans, iter);
 return b;
}

static struct bkey_s_c __bch2_backpointer_get_key(struct btree_trans *trans,
        struct bkey_s_c_backpointer bp,
        struct btree_iter *iter,
        unsigned iter_flags,
        struct bkey_buf *last_flushed,
        bool commit)
{
 struct bch_fs *c = trans->c;

 if (unlikely(bp.v->btree_id >= btree_id_nr_alive(c)))
  return bkey_s_c_null;

 bch2_trans_node_iter_init(trans, iter,
      bp.v->btree_id,
      bp.v->pos,
      0,
      bp.v->level,
      iter_flags);
 struct bkey_s_c k = bch2_btree_iter_peek_slot(trans, iter);
 if (bkey_err(k)) {
  bch2_trans_iter_exit(trans, iter);
  return k;
 }

 /*
  * peek_slot() doesn't normally return NULL - except when we ask for a
  * key at a btree level that doesn't exist.
  *
  * We may want to revisit this and change peek_slot():
 */
 if (!k.k) {
  bkey_init(&iter->k);
  iter->k.p = bp.v->pos;
  k.k = &iter->k;
 }

 if (k.k &&
     extent_matches_bp(c, bp.v->btree_id, bp.v->level, k, bp))
  return k;

 bch2_trans_iter_exit(trans, iter);

 if (!bp.v->level) {
  int ret = backpointer_target_not_found(trans, bp, k, last_flushed, commit);
  return ret ? bkey_s_c_err(ret) : bkey_s_c_null;
 } else {
  struct btree *b = __bch2_backpointer_get_node(trans, bp, iter, last_flushed, commit);
  if (b == ERR_PTR(-BCH_ERR_backpointer_to_overwritten_btree_node))
   return bkey_s_c_null;
  if (IS_ERR_OR_NULL(b))
   return ((struct bkey_s_c) { .k = ERR_CAST(b) });

  return bkey_i_to_s_c(&b->key);
 }
}

struct btree *bch2_backpointer_get_node(struct btree_trans *trans,
     struct bkey_s_c_backpointer bp,
     struct btree_iter *iter,
     struct bkey_buf *last_flushed)
{
 return __bch2_backpointer_get_node(trans, bp, iter, last_flushed, true);
}

struct bkey_s_c bch2_backpointer_get_key(struct btree_trans *trans,
      struct bkey_s_c_backpointer bp,
      struct btree_iter *iter,
      unsigned iter_flags,
      struct bkey_buf *last_flushed)
{
 return __bch2_backpointer_get_key(trans, bp, iter, iter_flags, last_flushed, true);
}

static int bch2_check_backpointer_has_valid_bucket(struct btree_trans *trans, struct bkey_s_c k,
         struct bkey_buf *last_flushed)
{
 if (k.k->type != KEY_TYPE_backpointer)
  return 0;

 struct bch_fs *c = trans->c;
 struct btree_iter alloc_iter = {};
 struct bkey_s_c alloc_k;
 struct printbuf buf = PRINTBUF;
 int ret = 0;

 struct bpos bucket;
 if (!bp_pos_to_bucket_nodev_noerror(c, k.k->p, &bucket)) {
  ret = bch2_backpointers_maybe_flush(trans, k, last_flushed);
  if (ret)
   goto out;

  if (fsck_err(trans, backpointer_to_missing_device,
        "backpointer for missing device:\n%s",
        (bch2_bkey_val_to_text(&buf, c, k), buf.buf)))
   ret = bch2_backpointer_del(trans, k.k->p);
  goto out;
 }

 alloc_k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc, bucket, 0);
 ret = bkey_err(alloc_k);
 if (ret)
  goto out;

 if (alloc_k.k->type != KEY_TYPE_alloc_v4) {
  ret = bch2_backpointers_maybe_flush(trans, k, last_flushed);
  if (ret)
   goto out;

  if (fsck_err(trans, backpointer_to_missing_alloc,
        "backpointer for nonexistent alloc key: %llu:%llu:0\n%s",
        alloc_iter.pos.inode, alloc_iter.pos.offset,
        (bch2_bkey_val_to_text(&buf, c, k), buf.buf)))
   ret = bch2_backpointer_del(trans, k.k->p);
 }
out:
fsck_err:
 bch2_trans_iter_exit(trans, &alloc_iter);
 printbuf_exit(&buf);
 return ret;
}

/* verify that every backpointer has a corresponding alloc key */
int bch2_check_btree_backpointers(struct bch_fs *c)
{
 struct bkey_buf last_flushed;
 bch2_bkey_buf_init(&last_flushed);
 bkey_init(&last_flushed.k->k);

 int ret = bch2_trans_run(c,
  for_each_btree_key_commit(trans, iter,
   BTREE_ID_backpointers, POS_MIN, 0, k,
   NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
    bch2_check_backpointer_has_valid_bucket(trans, k, &last_flushed)));

 bch2_bkey_buf_exit(&last_flushed, c);
 bch_err_fn(c, ret);
 return ret;
}

struct extents_to_bp_state {
 struct bpos bp_start;
 struct bpos bp_end;
 struct bkey_buf last_flushed;
};

static int drop_dev_and_update(struct btree_trans *trans, enum btree_id btree,
          struct bkey_s_c extent, unsigned dev)
{
 struct bkey_i *n = bch2_bkey_make_mut_noupdate(trans, extent);
 int ret = PTR_ERR_OR_ZERO(n);
 if (ret)
  return ret;

 bch2_bkey_drop_device(bkey_i_to_s(n), dev);
 return bch2_btree_insert_trans(trans, btree, n, 0);
}

static int check_extent_checksum(struct btree_trans *trans,
     enum btree_id btree, struct bkey_s_c extent,
     enum btree_id o_btree, struct bkey_s_c extent2, unsigned dev)
{
 struct bch_fs *c = trans->c;
 struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(extent);
 const union bch_extent_entry *entry;
 struct extent_ptr_decoded p;
 struct printbuf buf = PRINTBUF;
 void *data_buf = NULL;
 struct bio *bio = NULL;
 size_t bytes;
 int ret = 0;

 if (bkey_is_btree_ptr(extent.k))
  return false;

 bkey_for_each_ptr_decode(extent.k, ptrs, p, entry)
  if (p.ptr.dev == dev)
   goto found;
 BUG();
found:
 if (!p.crc.csum_type)
  return false;

 bytes = p.crc.compressed_size << 9;

 struct bch_dev *ca = bch2_dev_get_ioref(c, dev, READ,
    BCH_DEV_READ_REF_check_extent_checksums);
 if (!ca)
  return false;

 data_buf = kvmalloc(bytes, GFP_KERNEL);
 if (!data_buf) {
  ret = -ENOMEM;
  goto err;
 }

 bio = bio_alloc(ca->disk_sb.bdev, buf_pages(data_buf, bytes), REQ_OP_READ, GFP_KERNEL);
 bio->bi_iter.bi_sector = p.ptr.offset;
 bch2_bio_map(bio, data_buf, bytes);
 ret = submit_bio_wait(bio);
 if (ret)
  goto err;

 prt_printf(&buf, "extents pointing to same space, but first extent checksum bad:\n");
 bch2_btree_id_to_text(&buf, btree);
 prt_str(&buf, " ");
 bch2_bkey_val_to_text(&buf, c, extent);
 prt_newline(&buf);
 bch2_btree_id_to_text(&buf, o_btree);
 prt_str(&buf, " ");
 bch2_bkey_val_to_text(&buf, c, extent2);

 struct nonce nonce = extent_nonce(extent.k->bversion, p.crc);
 struct bch_csum csum = bch2_checksum(c, p.crc.csum_type, nonce, data_buf, bytes);
 if (fsck_err_on(bch2_crc_cmp(csum, p.crc.csum),
   trans, dup_backpointer_to_bad_csum_extent,
   "%s", buf.buf))
  ret = drop_dev_and_update(trans, btree, extent, dev) ?: 1;
fsck_err:
err:
 if (bio)
  bio_put(bio);
 kvfree(data_buf);
 enumerated_ref_put(&ca->io_ref[READ],
      BCH_DEV_READ_REF_check_extent_checksums);
 printbuf_exit(&buf);
 return ret;
}

static int check_bp_exists(struct btree_trans *trans,
      struct extents_to_bp_state *s,
      struct bkey_i_backpointer *bp,
      struct bkey_s_c orig_k)
{
 struct bch_fs *c = trans->c;
 struct btree_iter other_extent_iter = {};
 struct printbuf buf = PRINTBUF;

 if (bpos_lt(bp->k.p, s->bp_start) ||
     bpos_gt(bp->k.p, s->bp_end))
  return 0;

 struct btree_iter bp_iter;
 struct bkey_s_c bp_k = bch2_bkey_get_iter(trans, &bp_iter, BTREE_ID_backpointers, bp->k.p, 0);
 int ret = bkey_err(bp_k);
 if (ret)
  goto err;

 if (bp_k.k->type != KEY_TYPE_backpointer ||
     memcmp(bkey_s_c_to_backpointer(bp_k).v, &bp->v, sizeof(bp->v))) {
  ret = bch2_btree_write_buffer_maybe_flush(trans, orig_k, &s->last_flushed);
  if (ret)
   goto err;

  goto check_existing_bp;
 }
out:
err:
fsck_err:
 bch2_trans_iter_exit(trans, &other_extent_iter);
 bch2_trans_iter_exit(trans, &bp_iter);
 printbuf_exit(&buf);
 return ret;
check_existing_bp:
 /* Do we have a backpointer for a different extent? */
 if (bp_k.k->type != KEY_TYPE_backpointer)
  goto missing;

 struct bkey_s_c_backpointer other_bp = bkey_s_c_to_backpointer(bp_k);

 struct bkey_s_c other_extent =
  __bch2_backpointer_get_key(trans, other_bp, &other_extent_iter, 0, NULL, false);
 ret = bkey_err(other_extent);
 if (ret == -BCH_ERR_backpointer_to_overwritten_btree_node)
  ret = 0;
 if (ret)
  goto err;

 if (!other_extent.k)
  goto missing;

 rcu_read_lock();
 struct bch_dev *ca = bch2_dev_rcu_noerror(c, bp->k.p.inode);
 if (ca) {
  struct bkey_ptrs_c other_extent_ptrs = bch2_bkey_ptrs_c(other_extent);
  bkey_for_each_ptr(other_extent_ptrs, ptr)
   if (ptr->dev == bp->k.p.inode &&
       dev_ptr_stale_rcu(ca, ptr)) {
    rcu_read_unlock();
    ret = drop_dev_and_update(trans, other_bp.v->btree_id,
         other_extent, bp->k.p.inode);
    if (ret)
     goto err;
    goto out;
   }
 }
 rcu_read_unlock();

 if (bch2_extents_match(orig_k, other_extent)) {
  printbuf_reset(&buf);
  prt_printf(&buf, "duplicate versions of same extent, deleting smaller\n");
  bch2_bkey_val_to_text(&buf, c, orig_k);
  prt_newline(&buf);
  bch2_bkey_val_to_text(&buf, c, other_extent);
  bch_err(c, "%s", buf.buf);

  if (other_extent.k->size <= orig_k.k->size) {
   ret = drop_dev_and_update(trans, other_bp.v->btree_id,
        other_extent, bp->k.p.inode);
   if (ret)
    goto err;
   goto out;
  } else {
   ret = drop_dev_and_update(trans, bp->v.btree_id, orig_k, bp->k.p.inode);
   if (ret)
    goto err;
   goto missing;
  }
 }

 ret = check_extent_checksum(trans,
        other_bp.v->btree_id, other_extent,
        bp->v.btree_id, orig_k,
        bp->k.p.inode);
 if (ret < 0)
  goto err;
 if (ret) {
  ret = 0;
  goto missing;
 }

 ret = check_extent_checksum(trans, bp->v.btree_id, orig_k,
        other_bp.v->btree_id, other_extent, bp->k.p.inode);
 if (ret < 0)
  goto err;
 if (ret) {
  ret = 0;
  goto out;
 }

 printbuf_reset(&buf);
 prt_printf(&buf, "duplicate extents pointing to same space on dev %llu\n", bp->k.p.inode);
 bch2_bkey_val_to_text(&buf, c, orig_k);
 prt_newline(&buf);
 bch2_bkey_val_to_text(&buf, c, other_extent);
 bch_err(c, "%s", buf.buf);
 ret = bch_err_throw(c, fsck_repair_unimplemented);
 goto err;
missing:
 printbuf_reset(&buf);
 prt_str(&buf, "missing backpointer\nfor:  ");
 bch2_bkey_val_to_text(&buf, c, orig_k);
 prt_printf(&buf, "\nwant: ");
 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&bp->k_i));
 prt_printf(&buf, "\ngot:  ");
 bch2_bkey_val_to_text(&buf, c, bp_k);

 if (fsck_err(trans, ptr_to_missing_backpointer, "%s", buf.buf))
  ret = bch2_bucket_backpointer_mod(trans, orig_k, bp, true);

 goto out;
}

static int check_extent_to_backpointers(struct btree_trans *trans,
     struct extents_to_bp_state *s,
     enum btree_id btree, unsigned level,
     struct bkey_s_c k)
{
 struct bch_fs *c = trans->c;
 struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 const union bch_extent_entry *entry;
 struct extent_ptr_decoded p;

 bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
  if (p.ptr.dev == BCH_SB_MEMBER_INVALID)
   continue;

  bool empty;
  {
   /* scoped_guard() is a loop, so it breaks continue */
   guard(rcu)();
   struct bch_dev *ca = bch2_dev_rcu_noerror(c, p.ptr.dev);
   if (!ca)
    continue;

   if (p.ptr.cached && dev_ptr_stale_rcu(ca, &p.ptr))
    continue;

   u64 b = PTR_BUCKET_NR(ca, &p.ptr);
   if (!bch2_bucket_bitmap_test(&ca->bucket_backpointer_mismatch, b))
    continue;

   empty = bch2_bucket_bitmap_test(&ca->bucket_backpointer_empty, b);
  }

  struct bkey_i_backpointer bp;
  bch2_extent_ptr_to_bp(c, btree, level, k, p, entry, &bp);

  int ret = !empty
   ? check_bp_exists(trans, s, &bp, k)
   : bch2_bucket_backpointer_mod(trans, k, &bp, true);
  if (ret)
   return ret;
 }

 return 0;
}

static int check_btree_root_to_backpointers(struct btree_trans *trans,
         struct extents_to_bp_state *s,
         enum btree_id btree_id,
         int *level)
{
 struct bch_fs *c = trans->c;
 struct btree_iter iter;
 struct btree *b;
 struct bkey_s_c k;
 int ret;
retry:
 bch2_trans_node_iter_init(trans, &iter, btree_id, POS_MIN,
      0, bch2_btree_id_root(c, btree_id)->b->c.level, 0);
 b = bch2_btree_iter_peek_node(trans, &iter);
 ret = PTR_ERR_OR_ZERO(b);
 if (ret)
  goto err;

 if (b != btree_node_root(c, b)) {
  bch2_trans_iter_exit(trans, &iter);
  goto retry;
 }

 *level = b->c.level;

 k = bkey_i_to_s_c(&b->key);
 ret = check_extent_to_backpointers(trans, s, btree_id, b->c.level + 1, k);
err:
 bch2_trans_iter_exit(trans, &iter);
 return ret;
}

static u64 mem_may_pin_bytes(struct bch_fs *c)
{
 struct sysinfo i;
 si_meminfo(&i);

 u64 mem_bytes = i.totalram * i.mem_unit;
 return div_u64(mem_bytes * c->opts.fsck_memory_usage_percent, 100);
}

static size_t btree_nodes_fit_in_ram(struct bch_fs *c)
{
 return div_u64(mem_may_pin_bytes(c), c->opts.btree_node_size);
}

static int bch2_get_btree_in_memory_pos(struct btree_trans *trans,
     u64 btree_leaf_mask,
     u64 btree_interior_mask,
     struct bbpos start, struct bbpos *end)
{
 struct bch_fs *c = trans->c;
 s64 mem_may_pin = mem_may_pin_bytes(c);
 int ret = 0;

 bch2_btree_cache_unpin(c);

 btree_interior_mask |= btree_leaf_mask;

 c->btree_cache.pinned_nodes_mask[0]  = btree_leaf_mask;
 c->btree_cache.pinned_nodes_mask[1]  = btree_interior_mask;
 c->btree_cache.pinned_nodes_start  = start;
 c->btree_cache.pinned_nodes_end   = *end = BBPOS_MAX;

 for (enum btree_id btree = start.btree;
      btree < BTREE_ID_NR && !ret;
      btree++) {
  unsigned depth = (BIT_ULL(btree) & btree_leaf_mask) ? 0 : 1;

  if (!(BIT_ULL(btree) & btree_leaf_mask) &&
      !(BIT_ULL(btree) & btree_interior_mask))
   continue;

  ret = __for_each_btree_node(trans, iter, btree,
          btree == start.btree ? start.pos : POS_MIN,
          0, depth, BTREE_ITER_prefetch, b, ({
   mem_may_pin -= btree_buf_bytes(b);
   if (mem_may_pin <= 0) {
    c->btree_cache.pinned_nodes_end = *end =
     BBPOS(btree, b->key.k.p);
    break;
   }
   bch2_node_pin(c, b);
   0;
  }));
 }

 return ret;
}

static inline int bch2_fs_going_ro(struct bch_fs *c)
{
 return test_bit(BCH_FS_going_ro, &c->flags)
  ? -EROFS
  : 0;
}

static int bch2_check_extents_to_backpointers_pass(struct btree_trans *trans,
         struct extents_to_bp_state *s)
{
 struct bch_fs *c = trans->c;
 struct progress_indicator_state progress;
 int ret = 0;

 bch2_progress_init(&progress, trans->c, BIT_ULL(BTREE_ID_extents)|BIT_ULL(BTREE_ID_reflink));

 for (enum btree_id btree_id = 0;
      btree_id < btree_id_nr_alive(c);
      btree_id++) {
  int level, depth = btree_type_has_ptrs(btree_id) ? 0 : 1;

  ret = commit_do(trans, NULL, NULL,
    BCH_TRANS_COMMIT_no_enospc,
    check_btree_root_to_backpointers(trans, s, btree_id, &level));
  if (ret)
   return ret;

  while (level >= depth) {
   struct btree_iter iter;
   bch2_trans_node_iter_init(trans, &iter, btree_id, POS_MIN, 0, level,
        BTREE_ITER_prefetch);

   ret = for_each_btree_key_continue(trans, iter, 0, k, ({
    bch2_progress_update_iter(trans, &progress, &iter, "extents_to_backpointers");
    bch2_fs_going_ro(c) ?:
    check_extent_to_backpointers(trans, s, btree_id, level, k) ?:
    bch2_trans_commit(trans, NULL, NULL, BCH_TRANS_COMMIT_no_enospc);
   }));
   if (ret)
    return ret;

   --level;
  }
 }

 return 0;
}

enum alloc_sector_counter {
 ALLOC_dirty,
 ALLOC_cached,
 ALLOC_stripe,
 ALLOC_SECTORS_NR
};

static int data_type_to_alloc_counter(enum bch_data_type t)
{
 switch (t) {
 case BCH_DATA_btree:
 case BCH_DATA_user:
  return ALLOC_dirty;
 case BCH_DATA_cached:
  return ALLOC_cached;
 case BCH_DATA_stripe:
 case BCH_DATA_parity:
  return ALLOC_stripe;
 default:
  return -1;
 }
}

static int check_bucket_backpointers_to_extents(struct btree_trans *, struct bch_dev *, struct bpos);

static int check_bucket_backpointer_mismatch(struct btree_trans *trans, struct bkey_s_c alloc_k,
          bool *had_mismatch,
          struct bkey_buf *last_flushed)
{
 struct bch_fs *c = trans->c;
 struct bch_alloc_v4 a_convert;
 const struct bch_alloc_v4 *a = bch2_alloc_to_v4(alloc_k, &a_convert);
 bool need_commit = false;

 *had_mismatch = false;

 if (a->data_type == BCH_DATA_sb ||
     a->data_type == BCH_DATA_journal ||
     a->data_type == BCH_DATA_parity)
  return 0;

 u32 sectors[ALLOC_SECTORS_NR];
 memset(sectors, 0, sizeof(sectors));

 struct bch_dev *ca = bch2_dev_bucket_tryget_noerror(trans->c, alloc_k.k->p);
 if (!ca)
  return 0;

 struct btree_iter iter;
 struct bkey_s_c bp_k;
 int ret = 0;
 for_each_btree_key_max_norestart(trans, iter, BTREE_ID_backpointers,
    bucket_pos_to_bp_start(ca, alloc_k.k->p),
    bucket_pos_to_bp_end(ca, alloc_k.k->p), 0, bp_k, ret) {
  if (bp_k.k->type != KEY_TYPE_backpointer)
   continue;

  struct bkey_s_c_backpointer bp = bkey_s_c_to_backpointer(bp_k);

  if (c->sb.version_upgrade_complete >= bcachefs_metadata_version_backpointer_bucket_gen &&
      (bp.v->bucket_gen != a->gen ||
       bp.v->pad)) {
   ret = bch2_backpointer_del(trans, bp_k.k->p);
   if (ret)
    break;

   need_commit = true;
   continue;
  }

  if (bp.v->bucket_gen != a->gen)
   continue;

  int alloc_counter = data_type_to_alloc_counter(bp.v->data_type);
  if (alloc_counter < 0)
   continue;

  sectors[alloc_counter] += bp.v->bucket_len;
 };
 bch2_trans_iter_exit(trans, &iter);
 if (ret)
  goto err;

 if (need_commit) {
  ret = bch2_trans_commit(trans, NULL, NULL, BCH_TRANS_COMMIT_no_enospc);
  if (ret)
   goto err;
 }

 if (sectors[ALLOC_dirty]  != a->dirty_sectors ||
     sectors[ALLOC_cached] != a->cached_sectors ||
     sectors[ALLOC_stripe] != a->stripe_sectors) {
  if (c->sb.version_upgrade_complete >= bcachefs_metadata_version_backpointer_bucket_gen) {
   ret = bch2_backpointers_maybe_flush(trans, alloc_k, last_flushed);
   if (ret)
    goto err;
  }

  if (sectors[ALLOC_dirty]  > a->dirty_sectors ||
      sectors[ALLOC_cached] > a->cached_sectors ||
      sectors[ALLOC_stripe] > a->stripe_sectors) {
   ret = check_bucket_backpointers_to_extents(trans, ca, alloc_k.k->p) ?:
    bch_err_throw(c, transaction_restart_nested);
   goto err;
  }

  bool empty = (sectors[ALLOC_dirty] +
         sectors[ALLOC_stripe] +
         sectors[ALLOC_cached]) == 0;

  ret = bch2_bucket_bitmap_set(ca, &ca->bucket_backpointer_mismatch,
          alloc_k.k->p.offset) ?:
   (empty
    ? bch2_bucket_bitmap_set(ca, &ca->bucket_backpointer_empty,
        alloc_k.k->p.offset)
    : 0);

  *had_mismatch = true;
 }
err:
 bch2_dev_put(ca);
 return ret;
}

static bool backpointer_node_has_missing(struct bch_fs *c, struct bkey_s_c k)
{
 switch (k.k->type) {
 case KEY_TYPE_btree_ptr_v2: {
  bool ret = false;

  guard(rcu)();
  struct bpos pos = bkey_s_c_to_btree_ptr_v2(k).v->min_key;
  while (pos.inode <= k.k->p.inode) {
   if (pos.inode >= c->sb.nr_devices)
    break;

   struct bch_dev *ca = bch2_dev_rcu_noerror(c, pos.inode);
   if (!ca)
    goto next;

   struct bpos bucket = bp_pos_to_bucket(ca, pos);
   u64 next = ca->mi.nbuckets;

   unsigned long *bitmap = READ_ONCE(ca->bucket_backpointer_mismatch.buckets);
   if (bitmap)
    next = min_t(u64, next,
          find_next_bit(bitmap, ca->mi.nbuckets, bucket.offset));

   bucket.offset = next;
   if (bucket.offset == ca->mi.nbuckets)
    goto next;

   ret = bpos_le(bucket_pos_to_bp_end(ca, bucket), k.k->p);
   if (ret)
    break;
next:
   pos = SPOS(pos.inode + 1, 0, 0);
  }

  return ret;
 }
 case KEY_TYPE_btree_ptr:
  return true;
 default:
  return false;
 }
}

static int btree_node_get_and_pin(struct btree_trans *trans, struct bkey_i *k,
      enum btree_id btree, unsigned level)
{
 struct btree_iter iter;
 bch2_trans_node_iter_init(trans, &iter, btree, k->k.p, 0, level, 0);
 struct btree *b = bch2_btree_iter_peek_node(trans, &iter);
 int ret = PTR_ERR_OR_ZERO(b);
 if (ret)
  goto err;

 if (b)
  bch2_node_pin(trans->c, b);
err:
 bch2_trans_iter_exit(trans, &iter);
 return ret;
}

static int bch2_pin_backpointer_nodes_with_missing(struct btree_trans *trans,
         struct bpos start, struct bpos *end)
{
 struct bch_fs *c = trans->c;
 int ret = 0;

 struct bkey_buf tmp;
 bch2_bkey_buf_init(&tmp);

 bch2_btree_cache_unpin(c);

 *end = SPOS_MAX;

 s64 mem_may_pin = mem_may_pin_bytes(c);
 struct btree_iter iter;
 bch2_trans_node_iter_init(trans, &iter, BTREE_ID_backpointers, start,
      0, 1, BTREE_ITER_prefetch);
 ret = for_each_btree_key_continue(trans, iter, 0, k, ({
  if (!backpointer_node_has_missing(c, k))
   continue;

  mem_may_pin -= c->opts.btree_node_size;
  if (mem_may_pin <= 0)
   break;

  bch2_bkey_buf_reassemble(&tmp, c, k);
  struct btree_path *path = btree_iter_path(trans, &iter);

  BUG_ON(path->level != 1);

  bch2_btree_node_prefetch(trans, path, tmp.k, path->btree_id, path->level - 1);
 }));
 if (ret)
  return ret;

 struct bpos pinned = SPOS_MAX;
 mem_may_pin = mem_may_pin_bytes(c);
 bch2_trans_node_iter_init(trans, &iter, BTREE_ID_backpointers, start,
      0, 1, BTREE_ITER_prefetch);
 ret = for_each_btree_key_continue(trans, iter, 0, k, ({
  if (!backpointer_node_has_missing(c, k))
   continue;

  mem_may_pin -= c->opts.btree_node_size;
  if (mem_may_pin <= 0) {
   *end = pinned;
   break;
  }

  bch2_bkey_buf_reassemble(&tmp, c, k);
  struct btree_path *path = btree_iter_path(trans, &iter);

  BUG_ON(path->level != 1);

  int ret2 = btree_node_get_and_pin(trans, tmp.k, path->btree_id, path->level - 1);

  if (!ret2)
   pinned = tmp.k->k.p;

  ret;
 }));
 if (ret)
  return ret;

 return ret;
}

int bch2_check_extents_to_backpointers(struct bch_fs *c)
{
 int ret = 0;

 struct btree_trans *trans = bch2_trans_get(c);
 struct extents_to_bp_state s = { .bp_start = POS_MIN };

 bch2_bkey_buf_init(&s.last_flushed);
 bkey_init(&s.last_flushed.k->k);

 ret = for_each_btree_key(trans, iter, BTREE_ID_alloc,
     POS_MIN, BTREE_ITER_prefetch, k, ({
  bool had_mismatch;
  bch2_fs_going_ro(c) ?:
  check_bucket_backpointer_mismatch(trans, k, &had_mismatch, &s.last_flushed);
 }));
 if (ret)
  goto err;

 u64 nr_buckets = 0, nr_mismatches = 0;
 for_each_member_device(c, ca) {
  nr_buckets += ca->mi.nbuckets;
  nr_mismatches += ca->bucket_backpointer_mismatch.nr;
 }

 if (!nr_mismatches)
  goto err;

 bch_info(c, "scanning for missing backpointers in %llu/%llu buckets",
   nr_mismatches, nr_buckets);

 while (1) {
  ret = bch2_pin_backpointer_nodes_with_missing(trans, s.bp_start, &s.bp_end);
  if (ret)
   break;

  if ( bpos_eq(s.bp_start, POS_MIN) &&
      !bpos_eq(s.bp_end, SPOS_MAX))
   bch_verbose(c, "%s(): alloc info does not fit in ram, running in multiple passes with %zu nodes per pass",
        __func__, btree_nodes_fit_in_ram(c));

  if (!bpos_eq(s.bp_start, POS_MIN) ||
      !bpos_eq(s.bp_end, SPOS_MAX)) {
   struct printbuf buf = PRINTBUF;

   prt_str(&buf, "check_extents_to_backpointers(): ");
   bch2_bpos_to_text(&buf, s.bp_start);
   prt_str(&buf, "-");
   bch2_bpos_to_text(&buf, s.bp_end);

   bch_verbose(c, "%s", buf.buf);
   printbuf_exit(&buf);
  }

  ret = bch2_check_extents_to_backpointers_pass(trans, &s);
  if (ret || bpos_eq(s.bp_end, SPOS_MAX))
   break;

  s.bp_start = bpos_successor(s.bp_end);
 }

 for_each_member_device(c, ca) {
  bch2_bucket_bitmap_free(&ca->bucket_backpointer_mismatch);
  bch2_bucket_bitmap_free(&ca->bucket_backpointer_empty);
 }
err:
 bch2_trans_put(trans);
 bch2_bkey_buf_exit(&s.last_flushed, c);
 bch2_btree_cache_unpin(c);

 bch_err_fn(c, ret);
 return ret;
}

static int check_bucket_backpointer_pos_mismatch(struct btree_trans *trans,
       struct bpos bucket,
       bool *had_mismatch,
       struct bkey_buf *last_flushed)
{
 struct btree_iter alloc_iter;
 struct bkey_s_c k = bch2_bkey_get_iter(trans, &alloc_iter,
            BTREE_ID_alloc, bucket,
            BTREE_ITER_cached);
 int ret = bkey_err(k);
 if (ret)
  return ret;

 ret = check_bucket_backpointer_mismatch(trans, k, had_mismatch, last_flushed);
 bch2_trans_iter_exit(trans, &alloc_iter);
 return ret;
}

int bch2_check_bucket_backpointer_mismatch(struct btree_trans *trans,
        struct bch_dev *ca, u64 bucket,
        bool copygc,
        struct bkey_buf *last_flushed)
{
 struct bch_fs *c = trans->c;
 bool had_mismatch;
 int ret = lockrestart_do(trans,
  check_bucket_backpointer_pos_mismatch(trans, POS(ca->dev_idx, bucket),
            &had_mismatch, last_flushed));
 if (ret || !had_mismatch)
  return ret;

 u64 nr = ca->bucket_backpointer_mismatch.nr;
 u64 allowed = copygc ? ca->mi.nbuckets >> 7 : 0;

 struct printbuf buf = PRINTBUF;
 __bch2_log_msg_start(ca->name, &buf);

 prt_printf(&buf, "Detected missing backpointers in bucket %llu, now have %llu/%llu with missing\n",
     bucket, nr, ca->mi.nbuckets);

 bch2_run_explicit_recovery_pass(c, &buf,
   BCH_RECOVERY_PASS_check_extents_to_backpointers,
   nr < allowed ? RUN_RECOVERY_PASS_ratelimit : 0);

 bch2_print_str(c, KERN_ERR, buf.buf);
 printbuf_exit(&buf);
 return 0;
}

/* backpointers -> extents */

static int check_one_backpointer(struct btree_trans *trans,
     struct bbpos start,
     struct bbpos end,
     struct bkey_s_c bp_k,
     struct bkey_buf *last_flushed)
{
 if (bp_k.k->type != KEY_TYPE_backpointer)
  return 0;

 struct bkey_s_c_backpointer bp = bkey_s_c_to_backpointer(bp_k);
 struct bbpos pos = bp_to_bbpos(*bp.v);

 if (bbpos_cmp(pos, start) < 0 ||
     bbpos_cmp(pos, end) > 0)
  return 0;

 struct btree_iter iter;
 struct bkey_s_c k = bch2_backpointer_get_key(trans, bp, &iter, 0, last_flushed);
 int ret = bkey_err(k);
 if (ret == -BCH_ERR_backpointer_to_overwritten_btree_node)
  return 0;
 if (ret)
  return ret;

 bch2_trans_iter_exit(trans, &iter);
 return ret;
}

static int check_bucket_backpointers_to_extents(struct btree_trans *trans,
      struct bch_dev *ca, struct bpos bucket)
{
 u32 restart_count = trans->restart_count;
 struct bkey_buf last_flushed;
 bch2_bkey_buf_init(&last_flushed);
 bkey_init(&last_flushed.k->k);

 int ret = for_each_btree_key_max(trans, iter, BTREE_ID_backpointers,
          bucket_pos_to_bp_start(ca, bucket),
          bucket_pos_to_bp_end(ca, bucket),
          0, k,
  check_one_backpointer(trans, BBPOS_MIN, BBPOS_MAX, k, &last_flushed)
 );

 bch2_bkey_buf_exit(&last_flushed, trans->c);
 return ret ?: trans_was_restarted(trans, restart_count);
}

static int bch2_check_backpointers_to_extents_pass(struct btree_trans *trans,
         struct bbpos start,
         struct bbpos end)
{
 struct bch_fs *c = trans->c;
 struct bkey_buf last_flushed;
 struct progress_indicator_state progress;

 bch2_bkey_buf_init(&last_flushed);
 bkey_init(&last_flushed.k->k);
 bch2_progress_init(&progress, trans->c, BIT_ULL(BTREE_ID_backpointers));

 int ret = for_each_btree_key(trans, iter, BTREE_ID_backpointers,
         POS_MIN, BTREE_ITER_prefetch, k, ({
   bch2_progress_update_iter(trans, &progress, &iter, "backpointers_to_extents");
   check_one_backpointer(trans, start, end, k, &last_flushed);
 }));

 bch2_bkey_buf_exit(&last_flushed, c);
 return ret;
}

int bch2_check_backpointers_to_extents(struct bch_fs *c)
{
 struct btree_trans *trans = bch2_trans_get(c);
 struct bbpos start = (struct bbpos) { .btree = 0, .pos = POS_MIN, }, end;
 int ret;

 while (1) {
  ret = bch2_get_btree_in_memory_pos(trans,
         BIT_ULL(BTREE_ID_extents)|
         BIT_ULL(BTREE_ID_reflink),
         ~0,
         start, &end);
  if (ret)
   break;

  if (!bbpos_cmp(start, BBPOS_MIN) &&
      bbpos_cmp(end, BBPOS_MAX))
   bch_verbose(c, "%s(): extents do not fit in ram, running in multiple passes with %zu nodes per pass",
        __func__, btree_nodes_fit_in_ram(c));

  if (bbpos_cmp(start, BBPOS_MIN) ||
      bbpos_cmp(end, BBPOS_MAX)) {
   struct printbuf buf = PRINTBUF;

   prt_str(&buf, "check_backpointers_to_extents(): ");
   bch2_bbpos_to_text(&buf, start);
   prt_str(&buf, "-");
   bch2_bbpos_to_text(&buf, end);

   bch_verbose(c, "%s", buf.buf);
   printbuf_exit(&buf);
  }

  ret = bch2_check_backpointers_to_extents_pass(trans, start, end);
  if (ret || !bbpos_cmp(end, BBPOS_MAX))
   break;

  start = bbpos_successor(end);
 }
 bch2_trans_put(trans);

 bch2_btree_cache_unpin(c);

 bch_err_fn(c, ret);
 return ret;
}

static int bch2_bucket_bitmap_set(struct bch_dev *ca, struct bucket_bitmap *b, u64 bit)
{
 scoped_guard(mutex, &b->lock) {
  if (!b->buckets) {
   b->buckets = kvcalloc(BITS_TO_LONGS(ca->mi.nbuckets),
           sizeof(unsigned long), GFP_KERNEL);
   if (!b->buckets)
    return bch_err_throw(ca->fs, ENOMEM_backpointer_mismatches_bitmap);
  }

  b->nr += !__test_and_set_bit(bit, b->buckets);
 }

 return 0;
}

int bch2_bucket_bitmap_resize(struct bch_dev *ca, struct bucket_bitmap *b,
         u64 old_size, u64 new_size)
{
 scoped_guard(mutex, &b->lock) {
  if (!b->buckets)
   return 0;

  unsigned long *n = kvcalloc(BITS_TO_LONGS(new_size),
         sizeof(unsigned long), GFP_KERNEL);
  if (!n)
   return bch_err_throw(ca->fs, ENOMEM_backpointer_mismatches_bitmap);

  memcpy(n, b->buckets,
         BITS_TO_LONGS(min(old_size, new_size)) * sizeof(unsigned long));
  kvfree(b->buckets);
  b->buckets = n;
 }

 return 0;
}

void bch2_bucket_bitmap_free(struct bucket_bitmap *b)
{
 mutex_lock(&b->lock);
 kvfree(b->buckets);
 b->buckets = NULL;
 b->nr = 0;
 mutex_unlock(&b->lock);
}