]> www.infradead.org Git - users/jedix/linux-maple.git/commit
bcachefs: journal keys: sort keys for interior nodes first
authorKent Overstreet <kent.overstreet@linux.dev>
Sun, 17 Nov 2024 19:20:35 +0000 (14:20 -0500)
committerKent Overstreet <kent.overstreet@linux.dev>
Sat, 21 Dec 2024 06:36:18 +0000 (01:36 -0500)
commit06d7a56fe0bfc4f8c17bff6ca12d8bdd33e9f7e8
tree701b1465205dd585e50be5e4ea405864fd8fc35c
parent57026c41c9c5009f0d363cb11b15763c5289abb9
bcachefs: journal keys: sort keys for interior nodes first

There's an unavoidable issue with btree lookups when we're overlaying
journal keys and the journal has many deletions for keys present in the
btree - peek operations will have to iterate over all those deletions to
find the next live key to return.

This is mainly a problem for lookups in interior nodes, if we have to
traverse to a leaf. Looking up an insert position in a leaf (for journal
replay) doesn't have to find the next live key, but walking down the
btree does.

So to ameloriate this, change journal key sort ordering so that we
replay keys from roots and interior nodes first.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
fs/bcachefs/btree_journal_iter.c
fs/bcachefs/btree_journal_iter.h