• Kent Overstreet's avatar
    bcachefs: Snapshot depth, skiplist fields · f26c67f4
    Kent Overstreet authored
    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: default avatarKent Overstreet <kent.overstreet@linux.dev>
    f26c67f4
bcachefs_format.h 57.6 KB