[BUG] Out of memory on git log --simplify-by-decoration --first-parent

[BUG] Out of memory on git log --simplify-by-decoration --first-parent

[Vincent van Ravesteijn]

git dies after calling the following command on the git repo:

$ git log f623ca1c...b9cfa4e9 --simplify-by-decoration --first-parent

This happens in simplify_merges () in revision.c. The list below shows 
the number of times the "while (list) { ..}" block is executed until git 
dies:

1475
3544
8274
19588
45689
106077
245329
565153
1269244
2614903
5871845
13138892
fatal: Out of memory, malloc failed (tried to allocate 8 bytes)

Verified with msysgit and on Ubuntu Linux.

Vincent

Re: [BUG] Out of memory on git log --simplify-by-decoration --first-parent

[Junio C Hamano]

Vincent van Ravesteijn <vfr@lyx.org> writes:

> git dies after calling the following command on the git repo:
>
> $ git log f623ca1c...b9cfa4e9 --simplify-by-decoration --first-parent

I wouldn't be surprised anything random happens when --first-parent
is used together with simplify_merges(); the function needs full
analysis of all commits in the specified range, and first-parent
traversal specifically tells us not to descend into other parents.
It might not be a bad idea to forbid this combination when the
command line options are parsed.

What information were you trying to get out of the above command?

Re: [BUG] Out of memory on git log --simplify-by-decoration --first-parent

[Vincent van Ravesteijn]

Op 8-6-2012 22:09, Junio C Hamano schreef:
> Vincent van Ravesteijn<vfr@lyx.org>  writes:
>
>> git dies after calling the following command on the git repo:
>>
>> $ git log f623ca1c...b9cfa4e9 --simplify-by-decoration --first-parent
> I wouldn't be surprised anything random happens when --first-parent
> is used together with simplify_merges(); the function needs full
> analysis of all commits in the specified range, and first-parent
> traversal specifically tells us not to descend into other parents.
> It might not be a bad idea to forbid this combination when the
> command line options are parsed.
>
> What information were you trying to get out of the above command?

I was using gitk and I tried to simplify the history a bit, just for 
visualization,... so I tried by checking "Limit to first parent" and 
"Simple history". Then, git errored out with an out-of-memory error.

Vincent

Re: [BUG] Out of memory on git log --simplify-by-decoration --first-parent

[Junio C Hamano]

Vincent van Ravesteijn <vfr@lyx.org> writes:

> Op 8-6-2012 22:09, Junio C Hamano schreef:
>> Vincent van Ravesteijn<vfr@lyx.org>  writes:
>>
>>> git dies after calling the following command on the git repo:
>>>
>>> $ git log f623ca1c...b9cfa4e9 --simplify-by-decoration --first-parent
> ...
>> What information were you trying to get out of the above command?
>
> I was using gitk and I tried to simplify the history a bit, just for
> visualization,... so I tried by checking "Limit to first parent" and
> "Simple history". Then, git errored out with an out-of-memory error.

I see.  I am not sure what it _means_ to simplify merges away in a
history that is showing first-parent-only ancestry, but in any case,
this patch may help.

-- >8 --
Subject: [PATCH] revision: cull side parents before running simplify-merges

The simplify_merges() function needs to look at all history chain to
find the closest ancestor that is relevant after the simplification,
but after --first-parent traversal, side parents haven't been marked
for relevance (they are irrelevant by definition due to the nature
of first-parent-only traversal) nor culled from the parents list of
resulting commits.

Remove these side parents from parents list before starting to
further simplifying the result.

---

 revision.c | 27 ++++++++++++++++++---------
 1 file changed, 18 insertions(+), 9 deletions(-)

diff --git a/revision.c b/revision.c
index 935e7a7..acfdbac 100644
--- a/revision.c
+++ b/revision.c
@@ -1358,11 +1358,13 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 		revs->topo_order = 1;
 	} else if (!strcmp(arg, "--simplify-merges")) {
 		revs->simplify_merges = 1;
+		revs->topo_order = 1;
 		revs->rewrite_parents = 1;
 		revs->simplify_history = 0;
 		revs->limited = 1;
 	} else if (!strcmp(arg, "--simplify-by-decoration")) {
 		revs->simplify_merges = 1;
+		revs->topo_order = 1;
 		revs->rewrite_parents = 1;
 		revs->simplify_history = 0;
 		revs->simplify_by_decoration = 1;
@@ -2013,25 +2015,31 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
 
 static void simplify_merges(struct rev_info *revs)
 {
-	struct commit_list *list;
+	struct commit_list *list, *next;
 	struct commit_list *yet_to_do, **tail;
+	struct commit *commit;
 
-	if (!revs->topo_order)
-		sort_in_topological_order(&revs->commits, revs->lifo);
 	if (!revs->prune)
 		return;
 
 	/* feed the list reversed */
 	yet_to_do = NULL;
-	for (list = revs->commits; list; list = list->next)
-		commit_list_insert(list->item, &yet_to_do);
+	for (list = revs->commits; list; list = next) {
+		commit = list->item;
+		next = list->next;
+		free(list);
+		if (revs->first_parent_only &&
+		    commit->parents && commit->parents->next)
+			commit->parents->next = NULL;
+		commit_list_insert(commit, &yet_to_do);
+	}
 	while (yet_to_do) {
 		list = yet_to_do;
 		yet_to_do = NULL;
 		tail = &yet_to_do;
 		while (list) {
-			struct commit *commit = list->item;
-			struct commit_list *next = list->next;
+			commit = list->item;
+			next = list->next;
 			free(list);
 			list = next;
 			tail = simplify_one(revs, commit, tail);
@@ -2043,9 +2051,10 @@ static void simplify_merges(struct rev_info *revs)
 	revs->commits = NULL;
 	tail = &revs->commits;
 	while (list) {
-		struct commit *commit = list->item;
-		struct commit_list *next = list->next;
 		struct merge_simplify_state *st;
+
+		commit = list->item;
+		next = list->next;
 		free(list);
 		list = next;
 		st = locate_simplify_state(revs, commit);