[PATCH 0/3] btrfs-progs: check improve 'checking extents' scalability

[jeffm@suse.com]

From: Jeff Mahoney <jeffm@suse.com>

While running xfstests generic/291, which creates a single file populated
with reflinks to the same extent, I found that fsck had been running for
hours.  perf top lead me to find_data_backref as the culprit, and a litte
more digging made it clear: For every extent record we add, we iterate
the entire list first.  My test case had ~2M records.  That math doesn't
go well.

This patchset converts the extent_backref list to an rbtree.  The test
that used to run for more than 8 hours without completing now takes
less than 20 seconds.

-Jeff

---

Jeff Mahoney (3):
  btrfs-progs: check: add helpers for converting between structures
  btrfs-progs: check: supplement extent backref list with rbtree
  btrfs-progs: check: switch to iterating over the backref_tree

 cmds-check.c | 355 +++++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 237 insertions(+), 118 deletions(-)

-- 
2.7.1