]> www.infradead.org Git - users/jedix/linux-maple.git/commit
bcachefs: Use a heap for handling overwrites in btree node scan
authorKent Overstreet <kent.overstreet@linux.dev>
Sat, 7 Dec 2024 00:23:22 +0000 (19:23 -0500)
committerKent Overstreet <kent.overstreet@linux.dev>
Sat, 21 Dec 2024 06:36:22 +0000 (01:36 -0500)
commitbbe36bd0993df2167b883d4af0b849a309350c38
tree2a8b9a38be8cfdb366ed7ed14ce2c64369f74257
parentdec6c0aac4fc5e4266cea18e9e6e47eecb2333e1
bcachefs: Use a heap for handling overwrites in btree node scan

Fix an O(n^2) issue when we find many overlapping (overwritten) btree
nodes - especially when one node overwrites many smaller nodes.

This was discovered to be an issue with the bcachefs
merge_torture_flakey test - if we had a large btree that was then
emptied, the number of difficult overwrites can be unbounded.

Cc: Kuan-Wei Chiu <visitorckw@gmail.com>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
fs/bcachefs/btree_node_scan.c
fs/bcachefs/btree_node_scan_types.h