diff options
| author | Kent Overstreet <kent.overstreet@linux.dev> | 2023-06-26 01:04:46 +0300 |
|---|---|---|
| committer | Kent Overstreet <kent.overstreet@linux.dev> | 2023-10-23 00:10:06 +0300 |
| commit | f26c67f4a7c4951a312547790b11066bc510822e (patch) | |
| tree | a5f23a05f9a59dce45ffd1e9e354f73bd7279a2d /fs/bcachefs/bcachefs_format.h | |
| parent | 065bd3356ce490ae9454d8b3c98ff298e13d09ac (diff) | |
| download | linux-f26c67f4a7c4951a312547790b11066bc510822e.tar.xz | |
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 <kent.overstreet@linux.dev>
Diffstat (limited to 'fs/bcachefs/bcachefs_format.h')
| -rw-r--r-- | fs/bcachefs/bcachefs_format.h | 6 |
1 files changed, 5 insertions, 1 deletions
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, |