diff options
| author | Kent Overstreet <kent.overstreet@linux.dev> | 2024-12-07 03:23:22 +0300 |
|---|---|---|
| committer | Kent Overstreet <kent.overstreet@linux.dev> | 2024-12-21 09:36:22 +0300 |
| commit | bbe36bd0993df2167b883d4af0b849a309350c38 (patch) | |
| tree | 2a8b9a38be8cfdb366ed7ed14ce2c64369f74257 /scripts/lib/kdoc/kdoc_files.py | |
| parent | dec6c0aac4fc5e4266cea18e9e6e47eecb2333e1 (diff) | |
| download | linux-bbe36bd0993df2167b883d4af0b849a309350c38.tar.xz | |
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 'scripts/lib/kdoc/kdoc_files.py')
0 files changed, 0 insertions, 0 deletions