#include "fs.h"
#include "subvolume.h"
+#include <linux/random.h>
+
static int bch2_subvolume_delete(struct btree_trans *, u32);
+static inline u32 get_ancestor_below(struct snapshot_table *t, u32 id, u32 ancestor)
+{
+ const struct snapshot_t *s = __snapshot_t(t, id);
+
+ if (s->skip[2] <= ancestor)
+ return s->skip[2];
+ if (s->skip[1] <= ancestor)
+ return s->skip[1];
+ if (s->skip[0] <= ancestor)
+ return s->skip[0];
+ return s->parent;
+}
+
+bool __bch2_snapshot_is_ancestor(struct bch_fs *c, u32 id, u32 ancestor)
+{
+ struct snapshot_table *t;
+ bool ret;
+
+ EBUG_ON(c->curr_recovery_pass <= BCH_RECOVERY_PASS_check_snapshots);
+
+ rcu_read_lock();
+ t = rcu_dereference(c->snapshots);
+
+ while (id && id < ancestor - IS_ANCESTOR_BITMAP)
+ id = get_ancestor_below(t, id, ancestor);
+
+ ret = id && id < ancestor
+ ? test_bit(ancestor - id - 1, __snapshot_t(t, id)->is_ancestor)
+ : id == ancestor;
+ rcu_read_unlock();
+
+ return ret;
+}
+
+static bool bch2_snapshot_is_ancestor_early(struct bch_fs *c, u32 id, u32 ancestor)
+{
+ struct snapshot_table *t;
+
+ rcu_read_lock();
+ t = rcu_dereference(c->snapshots);
+
+ while (id && id < ancestor)
+ id = __snapshot_t(t, id)->parent;
+ rcu_read_unlock();
+
+ return id == ancestor;
+}
+
+static inline u32 bch2_snapshot_depth(struct bch_fs *c, u32 parent)
+{
+ u32 depth;
+
+ rcu_read_lock();
+ depth = parent ? snapshot_t(c, parent)->depth + 1 : 0;
+ rcu_read_unlock();
+
+ return depth;
+}
+
+static noinline struct snapshot_t *__snapshot_t_mut(struct bch_fs *c, u32 id)
+{
+ size_t idx = U32_MAX - id;
+ size_t new_size;
+ struct snapshot_table *new, *old;
+
+ new_size = max(16UL, roundup_pow_of_two(idx + 1));
+
+ new = kvzalloc(struct_size(new, s, new_size), GFP_KERNEL);
+ if (!new)
+ return NULL;
+
+ old = rcu_dereference_protected(c->snapshots, true);
+ if (old)
+ memcpy(new->s,
+ rcu_dereference_protected(c->snapshots, true)->s,
+ sizeof(new->s[0]) * c->snapshot_table_size);
+
+ rcu_assign_pointer(c->snapshots, new);
+ c->snapshot_table_size = new_size;
+ if (old)
+ kvfree_rcu(old);
+
+ return &rcu_dereference_protected(c->snapshots, true)->s[idx];
+}
+
+static inline struct snapshot_t *snapshot_t_mut(struct bch_fs *c, u32 id)
+{
+ size_t idx = U32_MAX - id;
+
+ lockdep_assert_held(&c->snapshot_table_lock);
+
+ if (likely(idx < c->snapshot_table_size))
+ return &rcu_dereference_protected(c->snapshots, true)->s[idx];
+
+ return __snapshot_t_mut(c, id);
+}
+
/* Snapshot tree: */
void bch2_snapshot_tree_to_text(struct printbuf *out, struct bch_fs *c,
le32_to_cpu(s.v->children[1]),
le32_to_cpu(s.v->subvol),
le32_to_cpu(s.v->tree));
+
+ if (bkey_val_bytes(k.k) > offsetof(struct bch_snapshot, depth))
+ prt_printf(out, " depth %u skiplist %u %u %u",
+ le32_to_cpu(s.v->depth),
+ le32_to_cpu(s.v->skip[0]),
+ le32_to_cpu(s.v->skip[1]),
+ le32_to_cpu(s.v->skip[2]));
}
int bch2_snapshot_invalid(const struct bch_fs *c, struct bkey_s_c k,
}
}
+ if (bkey_val_bytes(k.k) > offsetof(struct bch_snapshot, skip)) {
+ if (le32_to_cpu(s.v->skip[0]) > le32_to_cpu(s.v->skip[1]) ||
+ le32_to_cpu(s.v->skip[1]) > le32_to_cpu(s.v->skip[2])) {
+ prt_printf(err, "skiplist not normalized");
+ return -BCH_ERR_invalid_bkey;
+ }
+
+ for (i = 0; i < ARRAY_SIZE(s.v->skip); i++) {
+ id = le32_to_cpu(s.v->skip[i]);
+
+ if (!id != !s.v->parent ||
+ (s.v->parent &&
+ id <= k.k->p.offset)) {
+ prt_printf(err, "bad skiplist node %u)", id);
+ return -BCH_ERR_invalid_bkey;
+ }
+ }
+ }
+
return 0;
}
{
struct bch_fs *c = trans->c;
struct snapshot_t *t;
+ u32 id = new.k->p.offset;
+ int ret = 0;
- t = genradix_ptr_alloc(&c->snapshots,
- U32_MAX - new.k->p.offset,
- GFP_KERNEL);
- if (!t)
- return -BCH_ERR_ENOMEM_mark_snapshot;
+ mutex_lock(&c->snapshot_table_lock);
+
+ t = snapshot_t_mut(c, id);
+ if (!t) {
+ ret = -BCH_ERR_ENOMEM_mark_snapshot;
+ goto err;
+ }
if (new.k->type == KEY_TYPE_snapshot) {
struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(new);
+ u32 parent = id;
t->parent = le32_to_cpu(s.v->parent);
t->children[0] = le32_to_cpu(s.v->children[0]);
t->children[1] = le32_to_cpu(s.v->children[1]);
t->subvol = BCH_SNAPSHOT_SUBVOL(s.v) ? le32_to_cpu(s.v->subvol) : 0;
t->tree = le32_to_cpu(s.v->tree);
+
+ if (bkey_val_bytes(s.k) > offsetof(struct bch_snapshot, depth)) {
+ t->depth = le32_to_cpu(s.v->depth);
+ t->skip[0] = le32_to_cpu(s.v->skip[0]);
+ t->skip[1] = le32_to_cpu(s.v->skip[1]);
+ t->skip[2] = le32_to_cpu(s.v->skip[2]);
+ } else {
+ t->depth = 0;
+ t->skip[0] = 0;
+ t->skip[1] = 0;
+ t->skip[2] = 0;
+ }
+
+ while ((parent = bch2_snapshot_parent_early(c, parent)) &&
+ parent - id - 1 < IS_ANCESTOR_BITMAP)
+ __set_bit(parent - id - 1, t->is_ancestor);
+
+ if (BCH_SNAPSHOT_DELETED(s.v)) {
+ set_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
+ c->recovery_passes_explicit |= BIT_ULL(BCH_RECOVERY_PASS_delete_dead_snapshots);
+ }
} else {
- t->parent = 0;
- t->children[0] = 0;
- t->children[1] = 0;
- t->subvol = 0;
- t->tree = 0;
+ memset(t, 0, sizeof(*t));
}
-
- return 0;
+err:
+ mutex_unlock(&c->snapshot_table_lock);
+ return ret;
}
static int snapshot_lookup(struct btree_trans *trans, u32 id,
nr_live += ret;
}
- snapshot_t(c, id)->equiv = nr_live == 1
- ? snapshot_t(c, child[live_idx])->equiv
+ mutex_lock(&c->snapshot_table_lock);
+
+ snapshot_t_mut(c, id)->equiv = nr_live == 1
+ ? snapshot_t_mut(c, child[live_idx])->equiv
: id;
+
+ mutex_unlock(&c->snapshot_table_lock);
+
return 0;
}
"snapshot tree points to missing subvolume:\n %s",
(printbuf_reset(&buf),
bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf)) ||
- fsck_err_on(!bch2_snapshot_is_ancestor(c,
- le32_to_cpu(subvol.snapshot),
- root_id), c,
+ fsck_err_on(!bch2_snapshot_is_ancestor_early(c,
+ le32_to_cpu(subvol.snapshot),
+ root_id), c,
"snapshot tree points to subvolume that does not point to snapshot in this tree:\n %s",
(printbuf_reset(&buf),
bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf)) ||
if (ret)
return ret;
- return bch2_snapshot_is_ancestor(trans->c, snap_id, le32_to_cpu(s_t.root_snapshot));
+ return bch2_snapshot_is_ancestor_early(trans->c, snap_id, le32_to_cpu(s_t.root_snapshot));
+}
+
+static u32 snapshot_skiplist_get(struct bch_fs *c, u32 id)
+{
+ const struct snapshot_t *s;
+
+ if (!id)
+ return 0;
+
+ rcu_read_lock();
+ s = snapshot_t(c, id);
+ if (s->parent)
+ id = bch2_snapshot_nth_parent(c, id, get_random_u32_below(s->depth));
+ rcu_read_unlock();
+
+ return id;
+}
+
+static int snapshot_skiplist_good(struct btree_trans *trans, struct bch_snapshot s)
+{
+ struct bch_snapshot a;
+ unsigned i;
+ int ret;
+
+ for (i = 0; i < 3; i++) {
+ if (!s.parent != !s.skip[i])
+ return false;
+
+ if (!s.parent)
+ continue;
+
+ ret = snapshot_lookup(trans, le32_to_cpu(s.skip[i]), &a);
+ if (bch2_err_matches(ret, ENOENT))
+ return false;
+ if (ret)
+ return ret;
+
+ if (a.tree != s.tree)
+ return false;
+ }
+
+ return true;
}
/*
*/
static int snapshot_tree_ptr_repair(struct btree_trans *trans,
struct btree_iter *iter,
- struct bkey_s_c_snapshot *s)
+ struct bkey_s_c k,
+ struct bch_snapshot *s)
{
struct bch_fs *c = trans->c;
struct btree_iter root_iter;
struct bch_snapshot_tree s_t;
struct bkey_s_c_snapshot root;
struct bkey_i_snapshot *u;
- u32 root_id = bch2_snapshot_root(c, s->k->p.offset), tree_id;
+ u32 root_id = bch2_snapshot_root(c, k.k->p.offset), tree_id;
int ret;
root = bch2_bkey_get_iter_typed(trans, &root_iter,
goto err;
u->v.tree = cpu_to_le32(tree_id);
- if (s->k->p.snapshot == root_id)
- *s = snapshot_i_to_s_c(u);
+ if (k.k->p.offset == root_id)
+ *s = u->v;
}
- if (s->k->p.snapshot != root_id) {
- u = bch2_bkey_make_mut_typed(trans, iter, &s->s_c, 0, snapshot);
+ if (k.k->p.offset != root_id) {
+ u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
ret = PTR_ERR_OR_ZERO(u);
if (ret)
goto err;
u->v.tree = cpu_to_le32(tree_id);
- *s = snapshot_i_to_s_c(u);
+ *s = u->v;
}
err:
bch2_trans_iter_exit(trans, &root_iter);
return ret;
}
+static int cmp_le32(__le32 l, __le32 r)
+{
+ return cmp_int(le32_to_cpu(l), le32_to_cpu(r));
+}
+
static int check_snapshot(struct btree_trans *trans,
struct btree_iter *iter,
struct bkey_s_c k)
{
struct bch_fs *c = trans->c;
- struct bkey_s_c_snapshot s;
+ struct bch_snapshot s;
struct bch_subvolume subvol;
struct bch_snapshot v;
+ struct bkey_i_snapshot *u;
+ u32 parent_id = bch2_snapshot_parent_early(c, k.k->p.offset);
+ u32 real_depth;
struct printbuf buf = PRINTBUF;
bool should_have_subvol;
u32 i, id;
if (k.k->type != KEY_TYPE_snapshot)
return 0;
- s = bkey_s_c_to_snapshot(k);
- id = le32_to_cpu(s.v->parent);
+ memset(&s, 0, sizeof(s));
+ memcpy(&s, k.v, bkey_val_bytes(k.k));
+
+ id = le32_to_cpu(s.parent);
if (id) {
ret = snapshot_lookup(trans, id, &v);
if (bch2_err_matches(ret, ENOENT))
bch_err(c, "snapshot with nonexistent parent:\n %s",
- (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf));
+ (bch2_bkey_val_to_text(&buf, c, k), buf.buf));
if (ret)
goto err;
- if (le32_to_cpu(v.children[0]) != s.k->p.offset &&
- le32_to_cpu(v.children[1]) != s.k->p.offset) {
+ if (le32_to_cpu(v.children[0]) != k.k->p.offset &&
+ le32_to_cpu(v.children[1]) != k.k->p.offset) {
bch_err(c, "snapshot parent %u missing pointer to child %llu",
- id, s.k->p.offset);
+ id, k.k->p.offset);
ret = -EINVAL;
goto err;
}
}
- for (i = 0; i < 2 && s.v->children[i]; i++) {
- id = le32_to_cpu(s.v->children[i]);
+ for (i = 0; i < 2 && s.children[i]; i++) {
+ id = le32_to_cpu(s.children[i]);
ret = snapshot_lookup(trans, id, &v);
if (bch2_err_matches(ret, ENOENT))
bch_err(c, "snapshot node %llu has nonexistent child %u",
- s.k->p.offset, id);
+ k.k->p.offset, id);
if (ret)
goto err;
- if (le32_to_cpu(v.parent) != s.k->p.offset) {
+ if (le32_to_cpu(v.parent) != k.k->p.offset) {
bch_err(c, "snapshot child %u has wrong parent (got %u should be %llu)",
- id, le32_to_cpu(v.parent), s.k->p.offset);
+ id, le32_to_cpu(v.parent), k.k->p.offset);
ret = -EINVAL;
goto err;
}
}
- should_have_subvol = BCH_SNAPSHOT_SUBVOL(s.v) &&
- !BCH_SNAPSHOT_DELETED(s.v);
+ should_have_subvol = BCH_SNAPSHOT_SUBVOL(&s) &&
+ !BCH_SNAPSHOT_DELETED(&s);
if (should_have_subvol) {
- id = le32_to_cpu(s.v->subvol);
+ id = le32_to_cpu(s.subvol);
ret = bch2_subvolume_get(trans, id, 0, false, &subvol);
if (bch2_err_matches(ret, ENOENT))
bch_err(c, "snapshot points to nonexistent subvolume:\n %s",
- (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf));
+ (bch2_bkey_val_to_text(&buf, c, k), buf.buf));
if (ret)
goto err;
- if (BCH_SNAPSHOT_SUBVOL(s.v) != (le32_to_cpu(subvol.snapshot) == s.k->p.offset)) {
+ if (BCH_SNAPSHOT_SUBVOL(&s) != (le32_to_cpu(subvol.snapshot) == k.k->p.offset)) {
bch_err(c, "snapshot node %llu has wrong BCH_SNAPSHOT_SUBVOL",
- s.k->p.offset);
+ k.k->p.offset);
ret = -EINVAL;
goto err;
}
} else {
- if (fsck_err_on(s.v->subvol, c, "snapshot should not point to subvol:\n %s",
- (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf))) {
- struct bkey_i_snapshot *u = bch2_trans_kmalloc(trans, sizeof(*u));
-
+ if (fsck_err_on(s.subvol, c, "snapshot should not point to subvol:\n %s",
+ (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
+ u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
ret = PTR_ERR_OR_ZERO(u);
if (ret)
goto err;
- bkey_reassemble(&u->k_i, s.s_c);
u->v.subvol = 0;
- ret = bch2_trans_update(trans, iter, &u->k_i, 0);
- if (ret)
- goto err;
-
- s = snapshot_i_to_s_c(u);
+ s = u->v;
}
}
- ret = snapshot_tree_ptr_good(trans, s.k->p.offset, le32_to_cpu(s.v->tree));
+ ret = snapshot_tree_ptr_good(trans, k.k->p.offset, le32_to_cpu(s.tree));
if (ret < 0)
goto err;
if (fsck_err_on(!ret, c, "snapshot points to missing/incorrect tree:\n %s",
- (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf))) {
- ret = snapshot_tree_ptr_repair(trans, iter, &s);
+ (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
+ ret = snapshot_tree_ptr_repair(trans, iter, k, &s);
if (ret)
goto err;
}
ret = 0;
- if (BCH_SNAPSHOT_DELETED(s.v))
- set_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
+ real_depth = bch2_snapshot_depth(c, parent_id);
+
+ if (le32_to_cpu(s.depth) != real_depth &&
+ (c->sb.version_upgrade_complete < bcachefs_metadata_version_snapshot_skiplists ||
+ fsck_err(c, "snapshot with incorrect depth field, should be %u:\n %s",
+ real_depth, (bch2_bkey_val_to_text(&buf, c, k), buf.buf)))) {
+ u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
+ ret = PTR_ERR_OR_ZERO(u);
+ if (ret)
+ goto err;
+
+ u->v.depth = cpu_to_le32(real_depth);
+ s = u->v;
+ }
+
+ ret = snapshot_skiplist_good(trans, s);
+ if (ret < 0)
+ goto err;
+
+ if (!ret &&
+ (c->sb.version_upgrade_complete < bcachefs_metadata_version_snapshot_skiplists ||
+ fsck_err(c, "snapshot with bad skiplist field:\n %s",
+ (bch2_bkey_val_to_text(&buf, c, k), buf.buf)))) {
+ u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
+ ret = PTR_ERR_OR_ZERO(u);
+ if (ret)
+ goto err;
+
+ for (i = 0; i < ARRAY_SIZE(u->v.skip); i++)
+ u->v.skip[i] = cpu_to_le32(snapshot_skiplist_get(c, parent_id));
+
+ bubble_sort(u->v.skip, ARRAY_SIZE(u->v.skip), cmp_le32);
+ s = u->v;
+ }
+ ret = 0;
err:
fsck_err:
printbuf_exit(&buf);
struct bkey_s_c k;
int ret;
+ /*
+ * We iterate backwards as checking/fixing the depth field requires that
+ * the parent's depth already be correct:
+ */
ret = bch2_trans_run(c,
- for_each_btree_key_commit(&trans, iter,
- BTREE_ID_snapshots, POS_MIN,
+ for_each_btree_key_reverse_commit(&trans, iter,
+ BTREE_ID_snapshots, POS_MAX,
BTREE_ITER_PREFETCH, k,
NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
check_snapshot(&trans, &iter, k)));
if (!BCH_SUBVOLUME_SNAP(subvol.v)) {
u32 snapshot_root = bch2_snapshot_root(c, le32_to_cpu(subvol.v->snapshot));
- u32 snapshot_tree = snapshot_t(c, snapshot_root)->tree;
+ u32 snapshot_tree;
struct bch_snapshot_tree st;
+ rcu_read_lock();
+ snapshot_tree = snapshot_t(c, snapshot_root)->tree;
+ rcu_read_unlock();
+
ret = bch2_snapshot_tree_lookup(trans, snapshot_tree, &st);
bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
void bch2_fs_snapshots_exit(struct bch_fs *c)
{
- genradix_free(&c->snapshots);
+ kfree(rcu_dereference_protected(c->snapshots, true));
}
int bch2_snapshots_read(struct bch_fs *c)
u32 *snapshot_subvols,
unsigned nr_snapids)
{
+ struct bch_fs *c = trans->c;
struct btree_iter iter;
struct bkey_i_snapshot *n;
struct bkey_s_c k;
- unsigned i;
+ unsigned i, j;
+ u32 depth = bch2_snapshot_depth(c, parent);
int ret;
bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots,
n->v.parent = cpu_to_le32(parent);
n->v.subvol = cpu_to_le32(snapshot_subvols[i]);
n->v.tree = cpu_to_le32(tree);
+ n->v.depth = cpu_to_le32(depth);
+
+ for (j = 0; j < ARRAY_SIZE(n->v.skip); j++)
+ n->v.skip[j] = cpu_to_le32(snapshot_skiplist_get(c, parent));
+
+ bubble_sort(n->v.skip, ARRAY_SIZE(n->v.skip), cmp_le32);
SET_BCH_SNAPSHOT_SUBVOL(&n->v, true);
ret = bch2_mark_snapshot(trans, BTREE_ID_snapshots, 0,
struct bpos *last_pos)
{
struct bch_fs *c = trans->c;
- u32 equiv = snapshot_t(c, k.k->p.snapshot)->equiv;
+ u32 equiv = bch2_snapshot_equiv(c, k.k->p.snapshot);
if (!bkey_eq(k.k->p, *last_pos))
equiv_seen->nr = 0;
u32 i, id;
int ret = 0;
- if (!test_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags))
- return 0;
-
if (!test_bit(BCH_FS_STARTED, &c->flags)) {
ret = bch2_fs_read_write_early(c);
if (ret) {
{
struct bch_fs *c = container_of(work, struct bch_fs, snapshot_delete_work);
- bch2_delete_dead_snapshots(c);
+ if (test_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags))
+ bch2_delete_dead_snapshots(c);
bch2_write_ref_put(c, BCH_WRITE_REF_delete_dead_snapshots);
}
projects / bcachefs-tools-debian / blobdiff