From f26c67f4a7c4951a312547790b11066bc510822e Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Sun, 25 Jun 2023 18:04:46 -0400 Subject: 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 --- fs/bcachefs/bcachefs_format.h | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'fs/bcachefs/bcachefs_format.h') diff --git a/fs/bcachefs/bcachefs_format.h b/fs/bcachefs/bcachefs_format.h index 274e57740d74..6d693e4def5d 100644 --- a/fs/bcachefs/bcachefs_format.h +++ b/fs/bcachefs/bcachefs_format.h @@ -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) @@ -1625,7 +1627,9 @@ struct bch_sb_field_journal_seq_blacklist { x(snapshot_trees, BCH_VERSION(0, 29), \ RECOVERY_PASS_ALL_FSCK) \ x(major_minor, BCH_VERSION(1, 0), \ - 0) + 0) \ + x(snapshot_skiplists, BCH_VERSION(1, 1), \ + BIT_ULL(BCH_RECOVERY_PASS_check_snapshots)) enum bcachefs_metadata_version { bcachefs_metadata_version_min = 9, -- cgit v1.2.3