Skip to contentSkip to conversation

bcachefs: Snapshot depth, skiplist fields

PATCH New Kent Overstreet 1 participant 1 message Jul 10, 2023

lore
Share & tools
lore
#0 lore raw

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.

---
 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
index 78771d8d8a..707d4f76fb 100644
@@ -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
index 0e9c1cb98a..c472aa8c58 100644
@@ -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
index ddc2782fc5..581143a770 100644
@@ -541,13 +541,13 @@ static bool key_visible_in_snapshot(struct bch_fs *c, struct snapshots_seen *see
 	ssize_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
index cf59baf20f..b9b34c177f 100644
@@ -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
index daa9a6b081..ab0b4a6de2 100644
@@ -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
index c6c1cbad97..750d975ac4 100644
@@ -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