bcachefs: Snapshot depth, skiplist fields
PATCH 1/1 bcachefs: Snapshot depth, skiplist fields
This extents KEY_TYPE_snapshot to include some new fields:
- depth, to indicate depth of this particular node from the root
- skip[3], skiplist entries for quickly walking back up to the root
These are to improve bch2_snapshot_is_ancestor(), making it O(ln(n)) instead of O(n) in the snapshot tree depth.
Skiplist nodes are picked at random from the set of ancestor nodes, not some fixed fraction.
This introduces bcachefs_metadata_version 1.1, snapshot_skiplists.
Signed-off-by Kent Overstreet <[email protected]>
--- fs/bcachefs/bcachefs_format.h | 5 +- fs/bcachefs/btree_iter.h | 8 ++ fs/bcachefs/fsck.c | 10 +- fs/bcachefs/recovery.c | 7 +- fs/bcachefs/subvolume.c | 240 +++++++++++++++++++++++++++------- fs/bcachefs/subvolume.h | 33 ++++- fs/bcachefs/subvolume_types.h | 2 + 7 files changed, 242 insertions(+), 63 deletions(-)
fs/bcachefs/bcachefs_format.h +4 -1
@@ -1148,6 +1148,8 @@ struct bch_snapshot {__le32 children[2 ];__le32 subvol;__le32 tree; +__le32 depth; +__le32 skip[3 ]; }; LE32_BITMASK(BCH_SNAPSHOT_DELETED, struct bch_snapshot, flags, 0, 1)
@@ -1599,7 +1601,8 @@ struct bch_sb_field_journal_seq_blacklist { x(fragmentation_lru, BCH_VERSION(0, 27)) \ x(no_bps_in_alloc_keys, BCH_VERSION(0, 28)) \ x(snapshot_trees, BCH_VERSION(0, 29)) \ - x(major_minor, BCH_VERSION(1, 0)) + x(major_minor, BCH_VERSION(1, 0)) \ + x(snapshot_skiplists, BCH_VERSION(1, 1))enum bcachefs_metadata_version { bcachefs_metadata_version_min =9 ,
fs/bcachefs/btree_iter.h +8 -0
@@ -795,6 +795,14 @@ __bch2_btree_iter_peek_upto_and_restart(struct btree_trans *trans, (_do) ?: bch2_trans_commit(_trans, (_disk_res),\ (_journal_seq), (_commit_flags))) +#define for_each_btree_key_reverse_commit (_trans, _iter, _btree_id, \ + _start, _iter_flags, _k, \ + _disk_res, _journal_seq, _commit_flags,\ + _do) \ + for_each_btree_key_reverse(_trans, _iter, _btree_id, _start, _iter_flags, _k,\ + (_do) ?: bch2_trans_commit(_trans, (_disk_res),\ + (_journal_seq), (_commit_flags))) + #define for_each_btree_key_upto_commit(_trans, _iter, _btree_id, \ _start, _end, _iter_flags, _k, \ _disk_res, _journal_seq, _commit_flags,\
fs/bcachefs/fsck.c +5 -5
@@ -541,13 +541,13 @@ static bool key_visible_in_snapshot(struct bch_fs *c, struct snapshots_seen *seessize_t i;u32 top = seen->ids.nr ? seen->ids.data[seen->ids.nr -1 ].equiv :0 ; -BUG_ON (id > ancestor); -BUG_ON (!bch2_snapshot_is_equiv (c, id)); -BUG_ON (!bch2_snapshot_is_equiv (c, ancestor)); +EBUG_ON (id > ancestor); +EBUG_ON (!bch2_snapshot_is_equiv (c, id)); +EBUG_ON (!bch2_snapshot_is_equiv (c, ancestor));/* @ancestor should be the snapshot most recently added to @seen */ -BUG_ON (ancestor != seen->pos.snapshot); -BUG_ON (ancestor != top); +EBUG_ON (ancestor != seen->pos.snapshot); +EBUG_ON (ancestor != top);if (id == ancestor)return true;
fs/bcachefs/recovery.c +4 -3
@@ -593,8 +593,7 @@ static int bch2_journal_replay_key(struct btree_trans *trans,struct btree_iter iter;unsigned iter_flags =BTREE_ITER_INTENT | -BTREE_ITER_NOT_EXTENTS | -BTREE_UPDATE_KEY_CACHE_RECLAIM ; +BTREE_ITER_NOT_EXTENTS ;int ret;if (!k->level && k->btree_id == BTREE_ID_alloc)
@@ -611,7 +610,9 @@ static int bch2_journal_replay_key(struct btree_trans *trans,if (k->overwritten) goto out; - ret =bch2_trans_update (trans, &iter, k->k,BTREE_TRIGGER_NORUN ); + ret =bch2_trans_update (trans, &iter, k->k, +BTREE_TRIGGER_NORUN | +BTREE_UPDATE_KEY_CACHE_RECLAIM ); out:bch2_trans_iter_exit (trans, &iter);return ret;
fs/bcachefs/subvolume.c +193 -47
404 lines not on this page · raw message
fs/bcachefs/subvolume.h +26 -7
@@ -37,9 +37,34 @@ static inline struct snapshot_t *snapshot_t(struct bch_fs *c, u32 id)return genradix_ptr (&c->snapshots,U32_MAX - id); } +static inline u32 bch2_snapshot_parent_early (struct bch_fs *c,u32 id) +{ +return snapshot_t (c, id)->parent; +} +static inline u32 bch2_snapshot_parent (struct bch_fs *c,u32 id) { +#ifdef CONFIG_BCACHEFS_DEBUG +u32 parent =snapshot_t (c, id)->parent; + +if (parent && +snapshot_t (c, id)->depth !=snapshot_t (c, parent)->depth +1 ) +panic ("id %u depth=%u parent %u depth=%u\n" , + id,snapshot_t (c, id)->depth, + parent,snapshot_t (c, parent)->depth); + +return parent; +#else return snapshot_t (c, id)->parent; +#endif +} + +static inline u32 bch2_snapshot_nth_parent (struct bch_fs *c,u32 id,u32 n) +{ +while (n--) + id =bch2_snapshot_parent (c, id); + +return id; }static inline u32 bch2_snapshot_root (struct bch_fs *c,u32 id)
@@ -84,13 +109,7 @@ static inline u32 bch2_snapshot_sibling(struct bch_fs *c, u32 id)return 0 ; } -static inline bool bch2_snapshot_is_ancestor (struct bch_fs *c,u32 id,u32 ancestor) -{ -while (id && id < ancestor) - id =bch2_snapshot_parent (c, id); - -return id == ancestor; -} +bool bch2_snapshot_is_ancestor (struct bch_fs *,u32 ,u32 );static inline bool bch2_snapshot_has_children (struct bch_fs *c,u32 id) {
fs/bcachefs/subvolume_types.h +2 -0
@@ -8,6 +8,8 @@ typedef DARRAY(u32) snapshot_id_list;struct snapshot_t {u32 parent; +u32 skip[3 ]; +u32 depth;u32 children[2 ];u32 subvol;/* Nonzero only if a subvolume points to this node: */ u32 tree;
Signature · 1 line
2.40.1