bcachefs: Gap buffer for journal keys
authorKent Overstreet <kent.overstreet@gmail.com>
Mon, 4 Apr 2022 05:09:26 +0000 (01:09 -0400)
committerKent Overstreet <kent.overstreet@linux.dev>
Sun, 22 Oct 2023 21:09:30 +0000 (17:09 -0400)
commitd1d7737fd9df0cc57cd276b0189faf8c92c1426f
tree351c9884cb6f7b7f47dcfdf955ca6b1e04fe5e71
parent7c7e071d90ac278e462640570d739dd165d3acd0
bcachefs: Gap buffer for journal keys

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: Kent Overstreet <kent.overstreet@gmail.com>
fs/bcachefs/bcachefs.h
fs/bcachefs/recovery.c
fs/bcachefs/recovery.h
fs/bcachefs/util.h