line-log.c: prevent crash during union of too many ranges

The existing implementation of range_set_union does not correctly
reallocate memory, leading to a heap overflow when it attempts to union
more than 24 separate line ranges.

For struct range_set *out to grow correctly it must have out->nr set to
the current size of the buffer when it is passed to range_set_grow.
However, the existing implementation of range_set_union only updates
out->nr at the end of the function, meaning that it is always zero
before this. This results in range_set_grow never growing the buffer, as
well as some of the union logic itself being incorrect as !out->nr is
always true.

The reason why 24 is the limit is that the first allocation of size 1
ends up allocating a buffer of size 24 (due to the call to alloc_nr in
ALLOC_GROW). This goes some way to explain why this hasn't been
caught before.

Fix the problem by correctly updating out->nr after reallocating the
range_set. As this results in out->nr containing the same value as the
variable o, replace o with out->nr as well.

Finally, add a new test to help prevent the problem reoccurring in the
future. Thanks to Vegard Nossum for writing the test.

Signed-off-by: Allan Xavier <allan.x.xavier@oracle.com>
Reviewed-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/line-log.c b/line-log.c
index 916e7248701dad2a8beb870887a5ed7d3874ff41..47eaba73c68905a12037365f8a3d3118a3ea3ddd 100644 (file)
--- a/line-log.c
+++ b/line-log.c
@@ -144,7 +144,7 @@ void sort_and_merge_range_set(struct range_set *rs)
 static void range_set_union(struct range_set *out,
                             struct range_set *a, struct range_set *b)
 {
 static void range_set_union(struct range_set *out,
                             struct range_set *a, struct range_set *b)
 {

-       int i = 0, j = 0, o = 0;
+       int i = 0, j = 0;

        struct range *ra = a->ranges;
        struct range *rb = b->ranges;
        /* cannot make an alias of out->ranges: it may change during grow */
        struct range *ra = a->ranges;
        struct range *rb = b->ranges;
        /* cannot make an alias of out->ranges: it may change during grow */


@@ -167,16 +167,15 @@ static void range_set_union(struct range_set *out,
                        new = &rb[j++];
                if (new->start == new->end)
                        ; /* empty range */
                        new = &rb[j++];
                if (new->start == new->end)
                        ; /* empty range */

-               else if (!o || out->ranges[o-1].end < new->start) {
+               else if (!out->nr || out->ranges[out->nr-1].end < new->start) {

                        range_set_grow(out, 1);
                        range_set_grow(out, 1);

-                       out->ranges[o].start = new->start;
-                       out->ranges[o].end = new->end;
-                       o++;
-               } else if (out->ranges[o-1].end < new->end) {
-                       out->ranges[o-1].end = new->end;
+                       out->ranges[out->nr].start = new->start;
+                       out->ranges[out->nr].end = new->end;
+                       out->nr++;
+               } else if (out->ranges[out->nr-1].end < new->end) {
+                       out->ranges[out->nr-1].end = new->end;

                }
        }
                }
        }

-       out->nr = o;

 }
 
 /*
 }
 
 /*

diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh
index 9d87777b5994910dda971b57fd67b733ee9b5398..d0377fae5c832bcd4df37f3bc2ab4a8708f70251 100755 (executable)
--- a/t/t4211-line-log.sh
+++ b/t/t4211-line-log.sh
@@ -106,4 +106,14 @@ test_expect_success '-L with --output' '
        test_line_count = 70 log
 '
 
        test_line_count = 70 log
 '
 

+test_expect_success 'range_set_union' '
+       test_seq 500 > c.c &&
+       git add c.c &&
+       git commit -m "many lines" &&
+       test_seq 1000 > c.c &&
+       git add c.c &&
+       git commit -m "modify many lines" &&
+       git log $(for x in $(test_seq 200); do echo -L $((2*x)),+1:c.c; done)
+'
+

 test_done
 test_done