| commit | d1d7737fd9df0cc57cd276b0189faf8c92c1426f | [log] [tgz] |
|---|---|---|
| author | Kent Overstreet <kent.overstreet@gmail.com> | Mon Apr 04 01:09:26 2022 -0400 |
| committer | Kent Overstreet <kent.overstreet@linux.dev> | Sun Oct 22 17:09:30 2023 -0400 |
| tree | 351c9884cb6f7b7f47dcfdf955ca6b1e04fe5e71 | |
| parent | 7c7e071d90ac278e462640570d739dd165d3acd0 [diff] |
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>