On Tue, Jul 25, 2017 at 04:51:32PM -0400, jeffm@xxxxxxxx wrote: > From: Jeff Mahoney <jeffm@xxxxxxxx> > > 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. > > A previous version of this patch introduced a regression that would > have corrupted file systems during repair. It was traced to the > compare algorithm honoring ->bytes regardless of whether the > reference had been found and a failure to reinsert nodes after > the target reference was found. > > Signed-off-by: Jeff Mahoney <jeffm@xxxxxxxx> Josef has fixed the crash so I've added the patchset to devel. -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
