{"thread":{"id":"45266","subject":"[PATCH] line-log.c: prevent crash during union of too many ranges","startedAt":"2017-03-02T23:38:05Z","lastAt":"2017-03-03T19:20:04Z","messageCount":2,"participants":["Allan Xavier","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"313108","messageId":"20170302172902.16850-1-allan.x.xavier@oracle.com","threadId":"45266","inReplyTo":null,"subject":"[PATCH] line-log.c: prevent crash during union of too many ranges","fromName":"Allan Xavier","fromEmail":"allan.x.xavier@oracle.com","sentAt":"2017-03-02T17:29:02Z","receivedAt":"2017-03-02T23:38:05Z","isPatch":true,"sender":{"key":"allan.x.xavier@oracle.com","avatar":null},"body":"The existing implementation of range_set_union does not correctly\nreallocate memory, leading to a heap overflow when it attempts to union\nmore than 24 separate line ranges.\n\nFor struct range_set *out to grow correctly it must have out->nr set to\nthe current size of the buffer when it is passed to range_set_grow.\nHowever, the existing implementation of range_set_union only updates\nout->nr at the end of the function, meaning that it is always zero\nbefore this. This results in range_set_grow never growing the buffer, as\nwell as some of the union logic itself being incorrect as !out->nr is\nalways true.\n\nThe reason why 24 is the limit is that the first allocation of size 1\nends up allocating a buffer of size 24 (due to the call to alloc_nr in\nALLOC_GROW). This goes some way to explain why this hasn't been\ncaught before.\n\nFix the problem by correctly updating out->nr after reallocating the\nrange_set. As this results in out->nr containing the same value as the\nvariable o, replace o with out->nr as well.\n\nFinally, add a new test to help prevent the problem reoccurring in the\nfuture. Thanks to Vegard Nossum for writing the test.\n\nSigned-off-by: Allan Xavier <allan.x.xavier@oracle.com>\n---\n\nOriginally sent to git-security@googlegroups.com to give hosted\nservices a chance to apply this if they were affected.\n\n line-log.c          | 15 +++++++--------\n t/t4211-line-log.sh | 10 ++++++++++\n 2 files changed, 17 insertions(+), 8 deletions(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex 65f3558b3..951029665 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -144,7 +144,7 @@ void sort_and_merge_range_set(struct range_set *rs)\n static void range_set_union(struct range_set *out,\n \t\t\t     struct range_set *a, struct range_set *b)\n {\n-\tint i = 0, j = 0, o = 0;\n+\tint i = 0, j = 0;\n \tstruct range *ra = a->ranges;\n \tstruct range *rb = b->ranges;\n \t/* cannot make an alias of out->ranges: it may change during grow */\n@@ -167,16 +167,15 @@ static void range_set_union(struct range_set *out,\n \t\t\tnew = &rb[j++];\n \t\tif (new->start == new->end)\n \t\t\t; /* empty range */\n-\t\telse if (!o || out->ranges[o-1].end < new->start) {\n+\t\telse if (!out->nr || out->ranges[out->nr-1].end < new->start) {\n \t\t\trange_set_grow(out, 1);\n-\t\t\tout->ranges[o].start = new->start;\n-\t\t\tout->ranges[o].end = new->end;\n-\t\t\to++;\n-\t\t} else if (out->ranges[o-1].end < new->end) {\n-\t\t\tout->ranges[o-1].end = new->end;\n+\t\t\tout->ranges[out->nr].start = new->start;\n+\t\t\tout->ranges[out->nr].end = new->end;\n+\t\t\tout->nr++;\n+\t\t} else if (out->ranges[out->nr-1].end < new->end) {\n+\t\t\tout->ranges[out->nr-1].end = new->end;\n \t\t}\n \t}\n-\tout->nr = o;\n }\n \n /*\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex 9d87777b5..d0377fae5 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -106,4 +106,14 @@ test_expect_success '-L with --output' '\n \ttest_line_count = 70 log\n '\n \n+test_expect_success 'range_set_union' '\n+\ttest_seq 500 > c.c &&\n+\tgit add c.c &&\n+\tgit commit -m \"many lines\" &&\n+\ttest_seq 1000 > c.c &&\n+\tgit add c.c &&\n+\tgit commit -m \"modify many lines\" &&\n+\tgit log $(for x in $(test_seq 200); do echo -L $((2*x)),+1:c.c; done)\n+'\n+\n test_done\n-- \n2.11.0\n\n"},{"id":"313222","messageId":"xmqqlgsm88yh.fsf@gitster.mtv.corp.google.com","threadId":"45266","inReplyTo":"20170302172902.16850-1-allan.x.xavier@oracle.com","subject":"Re: [PATCH] line-log.c: prevent crash during union of too many ranges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-03T19:19:02Z","receivedAt":"2017-03-03T19:20:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Allan Xavier <allan.x.xavier@oracle.com> writes:\n\n> The existing implementation of range_set_union does not correctly\n> reallocate memory, leading to a heap overflow when it attempts to union\n> more than 24 separate line ranges.\n> ...\n\nI'll add \"Reviewed-by: Jeff King <peff@peff.net>\" and queue, as I\nknow we already reviewed the change.\n\nThanks.\n"}]}