]> www.infradead.org Git - users/jedix/linux-maple.git/commit
bcachefs: fix O(n^2) issue with whiteouts in journal keys
authorKent Overstreet <kent.overstreet@linux.dev>
Sun, 17 Nov 2024 07:23:24 +0000 (02:23 -0500)
committerKent Overstreet <kent.overstreet@linux.dev>
Sat, 21 Dec 2024 06:36:18 +0000 (01:36 -0500)
commiteae6c4a6255b03161c5c2c3e3a9cbfb4e22fa025
treed8e367d128aa9b55aebd0d59b78cf30ce79a45a8
parent854724d116cbd1145cd3888239a5cc7ea44d8cdc
bcachefs: fix O(n^2) issue with whiteouts in journal keys

The journal_keys array can't be substantially modified after we go RW,
because lookups need to be able to check it locklessly - thus we're
limited on what we can do when a key in the journal has been
overwritten.

This is a problem when there's many overwrites to skip over for peek()
operations. To fix this, add tracking of ranges of overwrites: we create
a range entry when there's more than one contiguous whiteout.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
fs/bcachefs/bcachefs.h
fs/bcachefs/btree_journal_iter.c
fs/bcachefs/btree_journal_iter.h
fs/bcachefs/btree_journal_iter_types.h [new file with mode: 0644]
fs/bcachefs/super.c