• Kent Overstreet's avatar
    bcachefs: Gap buffer for journal keys · d1d7737f
    Kent Overstreet authored
    Btree updates before we go RW work by inserting into the array of keys
    that journal replay will insert - but inserting into a flat array is
    O(n), meaning if btree_gc needs to update many alloc keys, we're O(n^2).
    
    Fortunately, the updates btree_gc does happens in sequential order,
    which means a gap buffer works nicely here - this patch implements a gap
    buffer for journal keys.
    Signed-off-by: default avatarKent Overstreet <kent.overstreet@gmail.com>
    d1d7737f
recovery.h 1.9 KB