btrfs-progs: check: supplement extent backref list with rbtree
authorJeff Mahoney <jeffm@suse.com>
Thu, 23 Jun 2016 19:26:05 +0000 (15:26 -0400)
committerDavid Sterba <dsterba@suse.com>
Mon, 4 Jul 2016 12:24:40 +0000 (14:24 +0200)
commit31d8235410985e0b64487354c9ba67d40c4bdfe3
tree32348f2268d535f307a49b57a36efa4a33514455
parent93014d235382301644c76ef338cc9a8b3a06615b
btrfs-progs: check: supplement extent backref list with rbtree

For the pathlogical case, like xfstests generic/297 that creates a
large file consisting of one, repeating reflinked extent, fsck can
take hours.  The root cause is that calling find_data_backref while
iterating the extent records is an O(n^2) algorithm.  For my
example test run, n was 2*2^20 and fsck was at 8 hours and counting.

This patch supplements the list with an rbtree and drops the runtime
of that testcase to about 20 seconds.

Signed-off-by: Jeff Mahoney <jeffm@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>
cmds-check.c