From: Philip Oakley Date: Sat, 10 Nov 2012 19:56:24 GMT Subject: Re: [PATCH] git tag --contains : avoid stack overflow Message-ID: <03ED9D50D1F64467863C051959CFC433@PhilipOakley> In-Reply-To: <1352568970-4669-1-git-send-email-jeanjacques.lafay@gmail.com> From: "Jean-Jacques Lafay" Sent: Saturday, November 10, 2012 5:36 PM > In large repos, the recursion implementation of contains(commit, > commit_list) > may result in a stack overflow. Replace the recursion with a loop to > fix it. > > Signed-off-by: Jean-Jacques Lafay This is a change to the main git code so it is better to submit it to the main git list at git@vger.kernel.org (plain text, no HTML, first post usually has a delay ;-) It sounds reasonable but others may have opinions and comments. Have you actually suffered from the stack overflow issue? You only suggest it as a possibility, rather than a real problem. Philip > --- > builtin/tag.c | 83 > ++++++++++++++++++++++++++++++++++++++++------------------ > t/t7004-tag.sh | 21 +++++++++++++++ > 2 files changed, 78 insertions(+), 26 deletions(-) > > diff --git a/builtin/tag.c b/builtin/tag.c > index 9c3e067..4be67dd 100644 > --- a/builtin/tag.c > +++ b/builtin/tag.c > @@ -73,40 +73,71 @@ static int in_commit_list(const struct commit_list > *want, struct commit *c) > return 0; > } > > -static int contains_recurse(struct commit *candidate, > - const struct commit_list *want) > -{ > - struct commit_list *p; > - > - /* was it previously marked as containing a want commit? */ > - if (candidate->object.flags & TMP_MARK) > - return 1; > - /* or marked as not possibly containing a want commit? */ > - if (candidate->object.flags & UNINTERESTING) > - return 0; > - /* or are we it? */ > - if (in_commit_list(want, candidate)) > - return 1; > +struct commit_list_list { > + struct commit *item; > + struct commit_list *next_item; > + struct commit_list_list *next; > +}; > > - if (parse_commit(candidate) < 0) > - return 0; > +static void mark_path(struct commit_list_list *path, int status) > +{ > + struct commit_list_list *temp; > + while (path) { > + path->item->object.flags |= status; > + temp = path; > + path = temp->next; > + free(temp); > + } > +} > > - /* Otherwise recurse and mark ourselves for future traversals. */ > - for (p = candidate->parents; p; p = p->next) { > - if (contains_recurse(p->item, want)) { > - candidate->object.flags |= TMP_MARK; > +static int contains(struct commit *candidate, > + const struct commit_list *want) > +{ > + /* previously implemented with a recursion, but could stack overflow > in large repos */ > + struct commit_list_list *p, *tmp; > + p = xmalloc(sizeof(struct commit_list_list)); > + p->item = candidate; > + p->next_item = NULL; > + p->next = NULL; > + > + while (p) { > + candidate = p->item; > + > + /* is it ok : */ > + /* was it previously marked as containing a want commit? */ > + /* or are we it? */ > + if (candidate->object.flags & TMP_MARK || in_commit_list(want, > candidate)) { > + mark_path(p, TMP_MARK); > return 1; > } > + /* is it not ok : */ > + /* was it previously marked as not possibly containing a want > commit? */ > + /* do we have parents? */ > + if (candidate->object.flags & UNINTERESTING || > parse_commit(candidate) < 0 || !candidate->parents) { > + candidate->object.flags |= UNINTERESTING; > + /* then backtrack, marking as UNINTERESTING along the way */ > + while (p && !p->next_item) { > + p->item->object.flags |= UNINTERESTING; > + tmp = p; > + p = tmp->next; > + free(tmp); > + } > + if (p) { > + p->item = p->next_item->item; > + p->next_item = p->next_item->next; > + } > + } else { > + /* let's check the parents */ > + tmp = xmalloc(sizeof(struct commit_list_list)); > + tmp->item = candidate->parents->item; > + tmp->next_item = candidate->parents->next; > + tmp->next = p; > + p = tmp; > + } > } > - candidate->object.flags |= UNINTERESTING; > return 0; > } > > -static int contains(struct commit *candidate, const struct > commit_list *want) > -{ > - return contains_recurse(candidate, want); > -} > - > static void show_tag_lines(const unsigned char *sha1, int lines) > { > int i; > diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh > index 5189446..196ac54 100755 > --- a/t/t7004-tag.sh > +++ b/t/t7004-tag.sh > @@ -1365,4 +1365,25 @@ test_expect_success 'multiple --points-at are > OR-ed together' ' > test_cmp expect actual > ' > > +# what about a deep repo ? > + > +>expect > +test_expect_success '--contains works in a deep repo' ' > + i=1 > + while test $i -lt 40000 > + do > + echo "commit refs/heads/master > +committer A U Thor $((1000000000 + $i * 100)) > +0200 > +data < +commit #$i > +EOF" > + test $i == 1 && echo "from refs/heads/master^0" > + i=$(($i + 1)) > + done | git fast-import > + git checkout master > + git tag far-far-away HEAD^ > + git tag --contains HEAD >actual && > + test_cmp expect actual > +' > + > test_done > -- > 1.8.0.msysgit.0.1.geed93bd.dirty > > -- -- *** Please reply-to-all at all times *** *** (do not pretend to know who is subscribed and who is not) *** *** Please avoid top-posting. *** The msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free. You received this message because you are subscribed to the Google Groups "msysGit" group. To post to this group, send email to msysgit@googlegroups.com To unsubscribe from this group, send email to msysgit+unsubscribe@googlegroups.com For more options, and view previous threads, visit this group at http://groups.google.com/group/msysgit?hl=en_US?hl=en