Segfault during merge

Segfault during merge

[Dave O]

Hi, I've encountered a particular merge that causes a segfault, and was
able to successfully bisect git to commit 36e3b5e.  However, I'm unable
to come up with a simple repro that doesn't involve the source tree that
I found it on, which unfortunately I'm not able to share.

I've debugged this a bit, and it seems to happen only when there's
sufficient file creations and deletions to surpass rename_limit in
diffcore_rename, and a rename/delete conflict is encountered.  I don't
know enough about the index operations that are performed at that point
to understand why it crashes git, though.

Here's a backtrace:

#0  0x080c071f in sha_eq (a=0x4 <Address 0x4 out of bounds>, b=0x8cd931c "\001:??????\tAR???`") at cache.h:597
#1  0x080c1c2d in merge_trees (o=0xbff274d0, head=0x8cd9338, merge=0x8cd9318, common=0x0, result=0xbff27484)
     at merge-recursive.c:1155
#2  0x080c3613 in merge_recursive (o=0xbff274d0, h1=0x8ccd3a0, h2=0x8ccd310, ca=0x8d9abb8, result=0xbff27528)
     at merge-recursive.c:1285
#3  0x0807b86e in try_merge_strategy (strategy=<value optimized out>, common=0x8d8f798,
     head_arg=0x80fe14a "HEAD") at builtin-merge.c:565
#4  0x0807cc23 in cmd_merge (argc=1, argv=0xbff28c08, prefix=0x0) at builtin-merge.c:1110
#5  0x0804b777 in handle_internal_command (argc=2, argv=0xbff28c08) at git.c:247
#6  0x0804b962 in main (argc=2, argv=0xbff28c08) at git.c:438

common=0x0 in the merge_trees() call is the culprit, and that seems to
happen when a previous recursive call incurs "There are unmerged index
entries" in write_tree_from_memory, presumably due to the index issue
referenced above.

I was able to stop the segfault by copying the "make an empty tree"
block into the block following the return from recursion where
make_virtual_commit is called, but I suspect this is not the correct
solution.

Please let me know how I can further help debug this issue, or possibly
come up with a repro that will help someone else debug it.  Thanks!

     Dave Olszewski

Re: Segfault during merge

[Johannes Schindelin]

Hi,

On Thu, 7 May 2009, Dave O wrote:

> Hi, I've encountered a particular merge that causes a segfault, and was
> able to successfully bisect git to commit 36e3b5e.

As you already found the commit, you could have Cc:ed me already.  It is 
pure luck that I did not miss your bug report.

> However, I'm unable to come up with a simple repro that doesn't involve 
> the source tree that I found it on, which unfortunately I'm not able to 
> share.

Sigh.

> I've debugged this a bit, and it seems to happen only when there's
> sufficient file creations and deletions to surpass rename_limit in
> diffcore_rename, and a rename/delete conflict is encountered.

Maybe you can set merge.renameLimit really small, and then reproduce?

Ciao,
Dscho

Re: Segfault during merge

[Jakub Narebski]

Dave O <cxreg@pobox.com> writes:

> Hi, I've encountered a particular merge that causes a segfault, and was
> able to successfully bisect git to commit 36e3b5e.  However, I'm unable
> to come up with a simple repro that doesn't involve the source tree that
> I found it on, which unfortunately I'm not able to share.

[...]
> Please let me know how I can further help debug this issue, or possibly
> come up with a repro that will help someone else debug it.  Thanks!

Couldn't you use repository anonymizing tool (which replaces all
content, but preserves shape of history) which was published as
example some time ago on git mailing list?  Unfortunately I don't
have it bookmarked, so you would have to search for it yourself.

-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: Segfault during merge

[Dave O]

On Thu, 7 May 2009, Johannes Schindelin wrote:

>> Hi, I've encountered a particular merge that causes a segfault, and was
>> able to successfully bisect git to commit 36e3b5e.
>
> As you already found the commit, you could have Cc:ed me already.  It is
> pure luck that I did not miss your bug report.

Sorry, didn't think to do so.

After some thought, I was able to come up with a simple script that
reproduces this crash.  I'm not sure what the policy on this list is for
attachments, so I've put it at this URL:

http://www.genericorp.net/~count/git-merge-crash

It requires bash and the perl /usr/bin/rename command for simplicity's
sake.  At the top of the script is a diagram of what it does.

Hopefully this helps you identify what's happening here.  Let me know if
I can help further.

     Dave

[PATCH] Fix segfault in merge-recursive

[Johannes Schindelin]

When there is no "common" tree (for whatever reason), we must not
throw a segmentation fault.

Noticed by Dave O.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---

	Sorry, did not have much time, so I only fixed the segfault.  
	Could you verify that the result is correct?

 merge-recursive.c          |   23 +++++--
 t/t3031-merge-criscross.sh |  135 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 151 insertions(+), 7 deletions(-)
 create mode 100755 t/t3031-merge-criscross.sh

diff --git a/merge-recursive.c b/merge-recursive.c
index a3721ef..920ccc1 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -176,17 +176,26 @@ static int git_merge_trees(int index_only,
 		opts.index_only = 1;
 	else
 		opts.update = 1;
-	opts.merge = 1;
-	opts.head_idx = 2;
 	opts.fn = threeway_merge;
 	opts.src_index = &the_index;
 	opts.dst_index = &the_index;
 
-	init_tree_desc_from_tree(t+0, common);
-	init_tree_desc_from_tree(t+1, head);
-	init_tree_desc_from_tree(t+2, merge);
+	if (common) {
+		opts.merge = 1;
+		opts.head_idx = 2;
+		init_tree_desc_from_tree(t+0, common);
+		init_tree_desc_from_tree(t+1, head);
+		init_tree_desc_from_tree(t+2, merge);
+		rc = unpack_trees(3, t, &opts);
+	}
+	else {
+		opts.merge = 0;
+		opts.head_idx = 1;
+		init_tree_desc_from_tree(t+0, head);
+		init_tree_desc_from_tree(t+1, merge);
+		rc = unpack_trees(2, t, &opts);
+	}
 
-	rc = unpack_trees(3, t, &opts);
 	cache_tree_free(&active_cache_tree);
 	return rc;
 }
@@ -1152,7 +1161,7 @@ int merge_trees(struct merge_options *o,
 		common = shift_tree_object(head, common);
 	}
 
-	if (sha_eq(common->object.sha1, merge->object.sha1)) {
+	if (common && sha_eq(common->object.sha1, merge->object.sha1)) {
 		output(o, 0, "Already uptodate!");
 		*result = head;
 		return 1;
diff --git a/t/t3031-merge-criscross.sh b/t/t3031-merge-criscross.sh
new file mode 100755
index 0000000..525afea
--- /dev/null
+++ b/t/t3031-merge-criscross.sh
@@ -0,0 +1,135 @@
+#!/bin/sh
+
+test_description='merge-recursive backend test'
+
+. ./test-lib.sh
+
+#         A      <- create some files
+#        / \
+#       B   C    <- cause rename/delete conflicts between B and C
+#      /     \
+# ->  1       1  <- merge-bases for F and G: B1, C1
+#     |\     /|
+#     2 D   E 2
+#     | |   | |
+#     | 1   1 |  <- overload rename_limit in E1
+#     |  \ /  |
+#     |   X   |
+#     |  / \  |
+#     | /   \ |
+#     |/     \|
+#     F       G  <- merge E into B, D into C
+#      \     /
+#       \   /
+#        \ /
+#         H      <- recursive merge crashes
+#
+
+# initialize
+test_expect_success 'setup' '
+	mkdir data &&
+
+	test_debug create a bunch of files &&
+	n=1 &&
+	while test $n -le 1000
+	do
+		echo $n > data/$n &&
+		n=$(($n+1)) ||
+		break
+	done &&
+
+	test_debug check them in &&
+	git add data &&
+	git commit -m A &&
+	git branch A &&
+
+	test_debug remove some files in one branch &&
+	git checkout -b B A &&
+	git rm data/99* &&
+	git add data &&
+	git commit -m B &&
+
+	test_debug few more commits on B &&
+	echo testB > data/testB &&
+	git add data &&
+	git commit -m B1 &&
+
+	test_debug with a branch off of it &&
+	git branch D &&
+
+	echo testB2 > data/testB2 &&
+	git add data &&
+	git commit -m B2 &&
+
+	test_debug put some commits on D &&
+	git checkout D &&
+	echo testD > data/testD &&
+	git add data &&
+	git commit -m D &&
+
+	echo testD1 > data/testD1 &&
+	git add data &&
+	git commit -m D1 &&
+
+	test_debug back up to the top, create another branch and cause a rename  &&
+	test_debug conflict with the files we deleted earlier &&
+	git checkout -b C A &&
+	git rm --cached data/99* &&
+	rename "s!/9!/moved-9!" data/99* &&
+	git add data &&
+	git commit -m C &&
+
+	test_debug few more commits on C &&
+	echo testC > data/testC &&
+	git add data &&
+	git commit -m C1 &&
+
+	test_debug with a branch off of it &&
+	git branch E &&
+
+	echo testC2 > data/testC2 &&
+	git add data &&
+	git commit -m C2 &&
+
+	test_debug put a commits on E &&
+	git checkout E &&
+	echo testE > data/testE &&
+	git add data &&
+	git commit -m E &&
+
+	test_debug and now, overload add/delete &&
+	git rm data/[123456]* &&
+	n=10000 &&
+	while test $n -le 11000
+	do
+		echo $n > data/$n &&
+		n=$(($n+1)) ||
+		break
+	done &&
+	git add data &&
+	git commit -m E1 &&
+
+
+	test_debug now, merge E into B &&
+	git checkout B &&
+	test_must_fail git merge E &&
+	test_debug force-resolve? &&
+	git add data &&
+	git commit -m F &&
+	git branch F &&
+
+
+	test_debug and merge D into C &&
+	git checkout C &&
+	test_must_fail git merge D &&
+	test_debug force-resolve? &&
+	git add data &&
+	git commit -m G &&
+	git branch G
+'
+
+test_expect_failure 'now, force a recursive merge between F and G' '
+	git merge F
+'
+
+test_done
-- 
1.6.2.1.493.g67cf3

Re: [PATCH] Fix segfault in merge-recursive

[Dave O]

On Fri, 8 May 2009, Johannes Schindelin wrote:

>
> When there is no "common" tree (for whatever reason), we must not
> throw a segmentation fault.
>
> Noticed by Dave O.

While this patch does prevent a segfault, it totally fails to recognize
any conflicts in the merge.  Reverting 36e3b5e produces an ordinary
merge conflict with some rename/delete conflicts, and others including
content related conflicts.  I'm not sure I wouldn't rather have the
segfault than the grossly incorrect automerge.

I'll continue debugging the triggering condition to see if I can
understand why the index is left dirty, leading to this NULL tree.

Thanks!

     Dave

Re: [PATCH] Fix segfault in merge-recursive

[Johannes Schindelin]

Hi,

On Fri, 8 May 2009, Dave O wrote:

> On Fri, 8 May 2009, Johannes Schindelin wrote:
> 
> > When there is no "common" tree (for whatever reason), we must not 
> > throw a segmentation fault.
> >
> > Noticed by Dave O.
> 
> While this patch does prevent a segfault, it totally fails to recognize 
> any conflicts in the merge.  Reverting 36e3b5e produces an ordinary 
> merge conflict with some rename/delete conflicts, and others including 
> content related conflicts.  I'm not sure I wouldn't rather have the 
> segfault than the grossly incorrect automerge.
> 
> I'll continue debugging the triggering condition to see if I can 
> understand why the index is left dirty, leading to this NULL tree.

One thing I realized while trying to quickly fix the issue for you was 
that the recognized merge base was NULL.  I.e. merge-recursive did _not_ 
find a merge base.

>From your description, it seemed that it should have found a merge base, 
but due to too many renames, maybe it did not.

Probably that is the issue.

(Sorry, too tired to do anything about it.)

Ciao,
Dscho

Re: [PATCH] Fix segfault in merge-recursive

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> When there is no "common" tree (for whatever reason), we must not
> throw a segmentation fault.

You described why the old code was wrong (i.e. "init_tree_desc_from_tree
is called with common == NULL"), but there is no mention why the new code
is correct.  For the purpose of satisfying the above statement, you could
have just exit(0) as well ;-)

> +	else {
> +		opts.merge = 0;
> +		opts.head_idx = 1;
> +		init_tree_desc_from_tree(t+0, head);
> +		init_tree_desc_from_tree(t+1, merge);
> +		rc = unpack_trees(2, t, &opts);
> +	}

This looks more like a half of branch-switch from HEAD to MERGE, not a
merge between HEAD and MERGE as two equal histories.  Shouldn't it be
doing a three-way tree merge using an empty tree object as the common
ancestor instead, just like merge_recursive.c::merge_recursive() itself
does?

Re: [PATCH] Fix segfault in merge-recursive

[Dave O]

On Sat, 9 May 2009, Johannes Schindelin wrote:

> Hi,
>
> On Fri, 8 May 2009, Dave O wrote:
>
>> On Fri, 8 May 2009, Johannes Schindelin wrote:
>>
>>> When there is no "common" tree (for whatever reason), we must not
>>> throw a segmentation fault.
>>>
>>> Noticed by Dave O.
>>
>> While this patch does prevent a segfault, it totally fails to recognize
>> any conflicts in the merge.  Reverting 36e3b5e produces an ordinary
>> merge conflict with some rename/delete conflicts, and others including
>> content related conflicts.  I'm not sure I wouldn't rather have the
>> segfault than the grossly incorrect automerge.
>>
>> I'll continue debugging the triggering condition to see if I can
>> understand why the index is left dirty, leading to this NULL tree.
>
> One thing I realized while trying to quickly fix the issue for you was
> that the recognized merge base was NULL.  I.e. merge-recursive did _not_
> find a merge base.
>
> but due to too many renames, maybe it did not.
>
> Probably that is the issue.

That's not what I witnessed, although it's possible I missed something:

./git-merge-crash: line 127: 29751 Segmentation fault      git merge F
count@bokonon:~/git-crash/crash-test$ git merge-base -a F G
8ffd08037781ab7811f9e7983b87a29ea9ea21d9
79ac36c0bd8525e087fdb278bac9cabfa655ba47
count@bokonon:~/git-crash/crash-test$ git merge-base -a 8ffd080 79ac36c
03ca38c681cd9f832fe68d30ea2d8dfa54cbaf75

What I did find, is that the tree is coming back NULL due to the early
return in write_tree_from_memory(), which in turn is due to
unmerged_cache() returning true.  If verbosity is up high enough, that
function will indicate that the paths of the unmerged entries are
exactly the ones affected in the commit I referenced earlier:

   There are unmerged index entries:
   3 data/moved-99
   3 data/moved-990
   [...]

Interestingly, I was able to remove quite a bit of the script and still
induce the crash, including the part where it causes too many renames.
It appears that all that's needed is a delete/rename conflict in a
recursive call.

The new version is here:
http://genericorp.net/~count/git-merge-crash-shorter

Once again, I don't really know what the implications of the index
operations that are happening here are, but the update_stages() call
in a recursive merge must be doing surprising.

     Dave

[PATCH] Don't update index while recursing (was Re: Segfault during merge)

[Dave O]

On Fri, 8 May 2009, Dave O wrote:

> Once again, I don't really know what the implications of the index
> operations that are happening here are, but the update_stages() call
> in a recursive merge must be doing surprising.

After writing this, I took another look around merge-recursive.c, and
realized that all the calls to update_stages() except this one were
careful only to do it when o->call_depth was 0.  This simple patch seems
to fully rectify the problem.

---
  merge-recursive.c |   11 ++++++-----
  1 files changed, 6 insertions(+), 5 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index a3721ef..f5df9b9 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -933,11 +933,12 @@ static int process_renames(struct merge_options *o,
  				       ren1_src, ren1_dst, branch1,
  				       branch2);
  				update_file(o, 0, ren1->pair->two->sha1, ren1->pair->two->mode, ren1_dst);
-				update_stages(ren1_dst, NULL,
-						branch1 == o->branch1 ?
-						ren1->pair->two : NULL,
-						branch1 == o->branch1 ?
-						NULL : ren1->pair->two, 1);
+				if (!o->call_depth)
+					update_stages(ren1_dst, NULL,
+							branch1 == o->branch1 ?
+							ren1->pair->two : NULL,
+							branch1 == o->branch1 ?
+							NULL : ren1->pair->two, 1);
  			} else if (!sha_eq(dst_other.sha1, null_sha1)) {
  				const char *new_path;
  				clean_merge = 0;
-- 
1.6.3.dirty

Re: [PATCH] Fix segfault in merge-recursive

[Johannes Schindelin]

Hi,

On Fri, 8 May 2009, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > When there is no "common" tree (for whatever reason), we must not
> > throw a segmentation fault.
> 
> You described why the old code was wrong (i.e. "init_tree_desc_from_tree 
> is called with common == NULL"), but there is no mention why the new 
> code is correct.  For the purpose of satisfying the above statement, you 
> could have just exit(0) as well ;-)

Yes, I should have marked this patch as "please test if the result is what 
you think it should be", because I was running out of time and therefore 
could not properly think things through.

> > +	else {
> > +		opts.merge = 0;
> > +		opts.head_idx = 1;
> > +		init_tree_desc_from_tree(t+0, head);
> > +		init_tree_desc_from_tree(t+1, merge);
> > +		rc = unpack_trees(2, t, &opts);
> > +	}
> 
> This looks more like a half of branch-switch from HEAD to MERGE, not a
> merge between HEAD and MERGE as two equal histories.  Shouldn't it be
> doing a three-way tree merge using an empty tree object as the common
> ancestor instead, just like merge_recursive.c::merge_recursive() itself
> does?

But of course!

Thanks,
Dscho

Re: [PATCH] Don't update index while recursing (was Re: Segfault during merge)

[Johannes Schindelin]

Hi,

On Fri, 8 May 2009, Dave O wrote:

> On Fri, 8 May 2009, Dave O wrote:
> 
> > Once again, I don't really know what the implications of the index 
> > operations that are happening here are, but the update_stages() call 
> > in a recursive merge must be doing surprising.
> 
> After writing this, I took another look around merge-recursive.c, and 
> realized that all the calls to update_stages() except this one were 
> careful only to do it when o->call_depth was 0.  This simple patch seems 
> to fully rectify the problem.

ACK.

Could you provide a commit message saying that call_depth > 0 requires 
trees to be constructed from the files with conflicts and that the stages 
thusly must not be updated?

Oh, and you may want to adjust the test I made from your script (you said 
you made it shorter, but you made the original version shorter, which does 
not run in the test suite unmodified).

And then a Signed-off-by, and you're good to go!

Sorry for my lousy attempt to help...

Ciao,
Dscho

Re: [PATCH] Fix segfault in merge-recursive

[Junio C Hamano]

Dave O <cxreg@pobox.com> writes:

> Once again, I don't really know what the implications of the index
> operations that are happening here are, but the update_stages() call
> in a recursive merge must be doing surprising.

When you are trying to come up with the final result (i.e. depth=0), you
want to record how the conflict arose by registering the state of the
common ancestor, your branch and the other branch in the index, hence you
want to do update_stages().

When you are merging with positive depth, that is because of a criss-cross
merge situation.  In such a case, you would need to record the tentative
result, with conflict markers and all as if the merge went cleanly, even
if there are conflicts, in order to write it out as a tree object later to
be used as a common ancestor tree.  update_file() calls update_file_flags()
with update_cache=1 to signal that the result needs to be written to the
index at stage #0 (i.e. merged), and the code should not clobber the index
further by calling update_stages().

Your patch looks correct.  Thanks.