diff options
| author | Kent Overstreet <kent.overstreet@linux.dev> | 2024-12-06 19:23:22 -0500 |
|---|---|---|
| committer | Kent Overstreet <kent.overstreet@linux.dev> | 2024-12-21 01:36:22 -0500 |
| commit | bbe36bd0993df2167b883d4af0b849a309350c38 (patch) | |
| tree | 2a8b9a38be8cfdb366ed7ed14ce2c64369f74257 /fs/bcachefs/btree_trans_commit.c | |
| parent | lib min_heap: Switch to size_t (diff) | |
| download | linux-bbe36bd0993df2167b883d4af0b849a309350c38.tar.gz linux-bbe36bd0993df2167b883d4af0b849a309350c38.zip | |
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>
Diffstat (limited to 'fs/bcachefs/btree_trans_commit.c')
0 files changed, 0 insertions, 0 deletions