bcachefs: Snapshot depth, skiplist fields
authorKent Overstreet <kent.overstreet@linux.dev>
Sun, 25 Jun 2023 22:04:46 +0000 (18:04 -0400)
committerKent Overstreet <kent.overstreet@linux.dev>
Sun, 22 Oct 2023 21:10:06 +0000 (17:10 -0400)
commitf26c67f4a7c4951a312547790b11066bc510822e
treea5f23a05f9a59dce45ffd1e9e354f73bd7279a2d
parent065bd3356ce490ae9454d8b3c98ff298e13d09ac
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>
fs/bcachefs/bcachefs_format.h
fs/bcachefs/btree_iter.h
fs/bcachefs/recovery.c
fs/bcachefs/subvolume.c
fs/bcachefs/subvolume.h
fs/bcachefs/subvolume_types.h