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 <tytso@mit.edu>

diff --git a/e2fsck/region.c b/e2fsck/region.c
index e32f89db0776304d22579d7a03ad7aa1b0a877e8..95d23be4f26c8853408b7c56dfd9c50fe5db9b8f 100644 (file)
--- 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