From 6132c84cacbff39e7b060abffc4175244347885d Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Thu, 13 Jul 2023 02:43:29 -0400 Subject: [PATCH] bcachefs: is_ancestor bitmap Further optimization for bch2_snapshot_is_ancestor(). We add a small inline bitmap to snapshot_t, which indicates which of the next 128 snapshot IDs are ancestors of the current id - eliminating the last few iterations of the loop in bch2_snapshot_is_ancestor(). Signed-off-by: Kent Overstreet --- fs/bcachefs/subvolume.c | 23 +++++++++++++++-------- fs/bcachefs/subvolume_types.h | 3 +++ 2 files changed, 18 insertions(+), 8 deletions(-) diff --git a/fs/bcachefs/subvolume.c b/fs/bcachefs/subvolume.c index c2c2cfd74e71f..cf8af617ac00d 100644 --- a/fs/bcachefs/subvolume.c +++ b/fs/bcachefs/subvolume.c @@ -28,17 +28,22 @@ static inline u32 get_ancestor_below(struct snapshot_table *t, u32 id, u32 ances 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) + 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 id == ancestor; + return ret; } static bool bch2_snapshot_is_ancestor_early(struct bch_fs *c, u32 id, u32 ancestor) @@ -289,11 +294,12 @@ int bch2_mark_snapshot(struct btree_trans *trans, { struct bch_fs *c = trans->c; struct snapshot_t *t; + u32 id = new.k->p.offset; int ret = 0; mutex_lock(&c->snapshot_table_lock); - t = snapshot_t_mut(c, new.k->p.offset); + t = snapshot_t_mut(c, id); if (!t) { ret = -BCH_ERR_ENOMEM_mark_snapshot; goto err; @@ -301,6 +307,7 @@ int bch2_mark_snapshot(struct btree_trans *trans, 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]); @@ -320,14 +327,14 @@ int bch2_mark_snapshot(struct btree_trans *trans, 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); } else { - t->parent = 0; - t->children[0] = 0; - t->children[1] = 0; - t->subvol = 0; - t->tree = 0; + memset(t, 0, sizeof(*t)); } err: mutex_unlock(&c->snapshot_table_lock); diff --git a/fs/bcachefs/subvolume_types.h b/fs/bcachefs/subvolume_types.h index c596e4270690b..86833445af205 100644 --- a/fs/bcachefs/subvolume_types.h +++ b/fs/bcachefs/subvolume_types.h @@ -6,6 +6,8 @@ typedef DARRAY(u32) snapshot_id_list; +#define IS_ANCESTOR_BITMAP 128 + struct snapshot_t { u32 parent; u32 skip[3]; @@ -14,6 +16,7 @@ struct snapshot_t { u32 subvol; /* Nonzero only if a subvolume points to this node: */ u32 tree; u32 equiv; + unsigned long is_ancestor[BITS_TO_LONGS(IS_ANCESTOR_BITMAP)]; }; struct snapshot_table { -- 2.30.2