threads / discuss / 19223

Segfault during merge

Subject: Segfault during merge

## tl;dr

13 messages between May 7, 2009 and May 9, 2009.

replies: 12people: 4as markdown or json

Dave O· May 7, 2009, 08:28 UTC · lore

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
Johannes Schindelin· May 7, 2009, 09:48 UTC · re: Dave O · lore

Re: Segfault during merge

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

Dave O· May 8, 2009, 04:37 UTC · re: Johannes Schindelin · lore

Re: Segfault during merge

On Thu, 7 May 2009, Johannes Schindelin wrote:
Show 5 quoted lines
>> 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
Johannes Schindelin· May 8, 2009, 20:30 UTC · re: Dave O · lore

[PATCH] Fix segfault in merge-recursive

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
Dave O· May 8, 2009, 21:41 UTC · re: Johannes Schindelin · lore

Re: [PATCH] Fix segfault in merge-recursive

On Fri, 8 May 2009, Johannes Schindelin wrote:
Show 5 quoted lines
>
> 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
Johannes Schindelin· May 8, 2009, 22:14 UTC · re: Dave O · lore

Re: [PATCH] Fix segfault in merge-recursive

Hi,
On Fri, 8 May 2009, Dave O wrote:
Show 15 quoted lines
> 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

Dave O· May 8, 2009, 23:54 UTC · re: Johannes Schindelin · lore

Re: [PATCH] Fix segfault in merge-recursive

On Sat, 9 May 2009, Johannes Schindelin wrote:
Show 27 quoted lines
> 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
Dave O· May 9, 2009, 05:30 UTC · re: Dave O · lore

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

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
Johannes Schindelin· May 9, 2009, 07:57 UTC · re: Dave O · lore

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

Hi,
On Fri, 8 May 2009, Dave O wrote:
Show 10 quoted lines
> 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

Junio C Hamano· May 9, 2009, 16:54 UTC · re: Dave O · lore

Re: [PATCH] Fix segfault in merge-recursive

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.
Junio C Hamano· May 8, 2009, 23:36 UTC · re: Johannes Schindelin · lore

Re: [PATCH] Fix segfault in merge-recursive

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 ;-)

Show 7 quoted lines
> +	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?

Johannes Schindelin· May 9, 2009, 07:48 UTC · re: Junio C Hamano · lore

Re: [PATCH] Fix segfault in merge-recursive

Hi,
On Fri, 8 May 2009, Junio C Hamano wrote:
Show 9 quoted lines
> 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.

Show 13 quoted lines
> > +	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

Jakub Narebski· May 7, 2009, 10:17 UTC · re: Dave O · lore

Re: Segfault during merge

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

← back to recent threads