From 8a48ce07a5923242fecc5dc04d6e30dd59a8f07d Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Mon, 14 Aug 2017 19:52:39 -0400 Subject: [PATCH] e2fsck: add optimization for large, fragmented sparse files The code which checks for overlapping logical blocks in an extent tree is O(h*e) in time, where h is the number of holes in the file, and e is the number of extents in the file. So a file with a large number of holes can take e2fsck a long time process. Optimize this taking advantage of the fact the vast majority of the time, region_allocate() is called with increasing logical block numbers, so we are almost always append onto the end of the region list. Signed-off-by: Theodore Ts'o --- e2fsck/region.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/e2fsck/region.c b/e2fsck/region.c index e32f89d..95d23be 100644 --- a/e2fsck/region.c +++ b/e2fsck/region.c @@ -30,6 +30,7 @@ struct region_struct { region_addr_t min; region_addr_t max; struct region_el *allocated; + struct region_el *last; }; region_t region_create(region_addr_t min, region_addr_t max) @@ -42,6 +43,7 @@ region_t region_create(region_addr_t min, region_addr_t max) memset(region, 0, sizeof(struct region_struct)); region->min = min; region->max = max; + region->last = NULL; return region; } @@ -68,6 +70,18 @@ int region_allocate(region_t region, region_addr_t start, int n) if (n == 0) return 1; + if (region->last && region->last->end == start && + !region->last->next) { + region->last->end = end; + return 0; + } + if (region->last && start > region->last->end && + !region->last->next) { + r = NULL; + prev = region->last; + goto append_to_list; + } + /* * Search through the linked list. If we find that it * conflicts witih something that's already allocated, return @@ -92,6 +106,8 @@ int region_allocate(region_t region, region_addr_t start, int n) r->end = next->end; r->next = next->next; free(next); + if (!r->next) + region->last = r; return 0; } } @@ -104,12 +120,15 @@ int region_allocate(region_t region, region_addr_t start, int n) /* * Insert a new region element structure into the linked list */ +append_to_list: new_region = malloc(sizeof(struct region_el)); if (!new_region) return -1; new_region->start = start; new_region->end = start + n; new_region->next = r; + if (!new_region->next) + region->last = new_region; if (prev) prev->next = new_region; else -- 1.8.3.1