From: "Jean-Jacques Lafay" <jeanjacques.lafay@xxxxxxxxx> 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 <jeanjacques.lafay@xxxxxxxxx>
This is a change to the main git code so it is better to submit it to
the main git list at git@xxxxxxxxxxxxxxx (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 <author@xxxxxxxxxxx> $((1000000000 + $i * 100))
+0200
+data <<EOF
+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
--
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html