SEGV in git-merge recursive:

I have been keeping my Maildir in git, a non-trivial merge that causes a segfault in git-merge-recursive.

It does not appear to matter which direction I try to merge.

I have a bundle of the relevant portion (rewritten with cg-admin-rewritehist) which still exhibits the problem. It is about 160M, but has private email in it.

  Tom Prince

# git-rev-list --parents head merge 922ee6e3f1222c8e171e6ea0b6ac0f28fb1f0683 2405850f1f347e471e040039672489573532582b # head 2405850f1f347e471e040039672489573532582b 490451aa36da8dc35db59b68a5dc2dfa1a38d9b9 0134d595adb023841750f1ce84ecb94dd4e4c9cb a85b502a7e827667bc84df06f0eb10a8abdd9a91 # merge 490451aa36da8dc35db59b68a5dc2dfa1a38d9b9 e3870054c7f67aa401dbf830b5297c91add076d6 e3870054c7f67aa401dbf830b5297c91add076d6 c14f3b6fef2727c26c993c8565f50047b036cedf a85b502a7e827667bc84df06f0eb10a8abdd9a91 93c2854d90bd126b594594df3d5eb921361844ba c14f3b6fef2727c26c993c8565f50047b036cedf c96c42fca513eb782e0f9905ff8649a1800fc628 c96c42fca513eb782e0f9905ff8649a1800fc628 7f1260b89b194b09f11f4d7f4a10dfd27c75ad59 93c2854d90bd126b594594df3d5eb921361844ba a711bb1b8b4fd38d980235e662f801bf31af5782 7f1260b89b194b09f11f4d7f4a10dfd27c75ad59 cc71e5ab9c70c1a3a018abfd770acbe823cc3746 cc71e5ab9c70c1a3a018abfd770acbe823cc3746 1b21b61d2ebe6f54c258d9d1a846690145c408bc a711bb1b8b4fd38d980235e662f801bf31af5782 29e722de58df3cd82600fa5215ec26f80a8c0f9a 2c3490d82610d12d8dfde36b29c4ec5a50955b89 1b21b61d2ebe6f54c258d9d1a846690145c408bc 2c3490d82610d12d8dfde36b29c4ec5a50955b89 29e722de58df3cd82600fa5215ec26f80a8c0f9a 29e722de58df3cd82600fa5215ec26f80a8c0f9a e2123cfd9a53e441c7c715627953606c6093e0e4 2c3490d82610d12d8dfde36b29c4ec5a50955b89 3eb95ece931c80b50ad182c602ada3f35e240916 3eb95ece931c80b50ad182c602ada3f35e240916 5a8eaa887ec82657fcf42a25db928ec263946018 5a8eaa887ec82657fcf42a25db928ec263946018 e2123cfd9a53e441c7c715627953606c6093e0e4 e2123cfd9a53e441c7c715627953606c6093e0e4

On 3/29/07, Tom Prince <tom.prince@ualberta.net> wrote:

Can you try and get a stack trace? Do, for example, GIT_TRACE=1 git merge ... ... find the call to git-merge-recursive and start that in gdb. Wait until it crash.

On Thu, Mar 29, 2007 at 10:18:14AM +0200, Alex Riesen wrote:

Here is the backtrace.

#0  0x0000000000402d29 in sha_eq (a=0xfefefefefefefeff <Address 0xfefefefefefefeff out of bounds>,
    b=0x563cdc "�6Cq�\234�w:0T��\177�\023p\214Q,") at cache.h:259
#1  0x000000000040456e in merge (h1=0x553ca0, h2=0x553d20, branch1=0x7fff92e5c27b "HEAD",
    branch2=0x7fff92e5c3ee "merge", ca=0x5528a0, result=0x7fff92e5ab90) at merge-recursive.c:1115
#2  0x0000000000405d89 in main (argc=-1830435858, argv=0x8) at merge-recursive.c:1362

I actually got this backtrace with the following script in git-merge-gdb

#!/bin/zsh

exec gdb -x =(print run $@) =git-merge-recursive

On 3/29/07, Tom Prince <tom.prince@ualberta.net> wrote:

BTW, what git do you have? git --version?

On Thu, Mar 29, 2007 at 01:29:46PM +0200, Alex Riesen wrote:

1.5.1.rc3

On 3/29/07, Tom Prince <tom.prince@ualberta.net> wrote:

Did it crash before? If it didn't, is it possible for you to bisect the commit which caused the problem?

On Thu, Mar 29, 2007 at 03:34:00PM +0200, Alex Riesen wrote:

It occurs running

git merge -s recur test HEAD merge

with

6c711269d4e49072703255ce29bd4d8c53e4f4ba

which introduced the C version of merge-recursive.

Here is the output from that more verbose version:

Merging HEAD with 0134d595adb023841750f1ce84ecb94dd4e4c9cb
Merging:
922ee6e3f1222c8e171e6ea0b6ac0f28fb1f0683 Mail.
0134d595adb023841750f1ce84ecb94dd4e4c9cb Mail.
found 2 common ancestor(s):
29e722de58df3cd82600fa5215ec26f80a8c0f9a Mail.
2c3490d82610d12d8dfde36b29c4ec5a50955b89 Mail.
  Merging:
  29e722de58df3cd82600fa5215ec26f80a8c0f9a Mail.
  2c3490d82610d12d8dfde36b29c4ec5a50955b89 Mail.
  found 1 common ancestor(s):
  e2123cfd9a53e441c7c715627953606c6093e0e4 Merge commit 'origin'
  CONFLICT (rename/rename): Rename .drafts/new/1175001142.P509Q1.hermes->.mom/cur/1175098106.P18146Q0M209985.socrates:2,S in branch Temporary merge branch 1 rename .drafts/new/1175001142.P509Q1.hermes->.drafts/cur/1175001142.P509Q1.hermes:2, in Temporary merge branch 2
/Users/cougar/local/bin/git-merge: line 311: 25426 Segmentation fault      git-merge-$strategy $common -- "$head_arg" "$@"
No merge strategy handled the merge.

On 3/29/07, Tom Prince <tom.prince@ualberta.net> wrote:

So, it _always_ crashed for you.

Rename conflict... Will see, if I can reproduce it without your repo. In the mean time, how about

Is it MacOSX, by any chance? On 64bit? just collating data

On 3/29/07, Alex Riesen <raa.lkml@gmail.com> wrote:

Yes, how about -O0 -ggdb stack trace?

On Thu, Mar 29, 2007 at 04:45:30PM +0200, Alex Riesen wrote:

This is no x86_64.

#0  0x00002ac9f9029cc2 in memcmp () from /System/Links/Libraries/libc.so.6
#1  0x0000000000402fbc in hashcmp (sha1=0x4 <Address 0x4 out of bounds>,
    sha2=0x570cdc "�6Cq�\234�w:0T��\177�\023p\214Q,") at cache.h:260
#2  0x0000000000402f84 in sha_eq (a=0x4 <Address 0x4 out of bounds>, b=0x570cdc "�6Cq�\234�w:0T��\177�\023p\214Q,")
    at merge-recursive.c:53
#3  0x0000000000405eda in merge_trees (head=0x570cb0, merge=0x570cd8, common=0x0, branch1=0x7fffb1f6427b "HEAD",
    branch2=0x7fffb1f64e6d "merge", result=0x7fffb1f63ce8) at merge-recursive.c:1115
#4  0x000000000040635f in merge (h1=0x560ca0, h2=0x560d20, branch1=0x7fffb1f6427b "HEAD",
    branch2=0x7fffb1f64e6d "merge", ca=0x55f590, result=0x7fffb1f63d70) at merge-recursive.c:1249
#5  0x0000000000406826 in main (argc=6, argv=0x7fffb1f63e88) at merge-recursive.c:1362

On 3/29/07, Alex Riesen <raa.lkml@gmail.com> wrote:

I failed to reproduce it. My attempt attached (that's for your reference pleasure, Dscho). The output was:

GIT_MERGE_VERBOSITY=99 git merge B
Merging HEAD with B
Merging:
18d0538 rename
d4badb1 rename
found 2 common ancestor(s):
962b369 change
9cc8ebd change
  Merging:
  962b369 change
  9cc8ebd change
  found 1 common ancestor(s):
  a46f64f init
CONFLICT (rename/rename): Rename 1->a in branch HEAD rename 1->b in B
Automatic merge failed; fix conflicts and then commit the result.

Tom, either the stack trace of -O0 -ggdb or your repo is badly needed. The stack preferred, as I have that feeling it'll just work everywhere else but your system (can you try it somewhere else, BTW?).

Alex Riesen, Thu, Mar 29, 2007 17:04:31 +0200:

Ok-key... Thanks Tom, for the testcase. I believe we haven't had this one yet: the merge base in the second (inner) merge is the initial commit. Which is strange:

(gdb) p *merged_common_ancestors
$4 = {
  object = {
    parsed = 1,
    used = 0,
    type = 0,
    flags = 0,
    sha1 = "\001", '\0' <repeats 18 times>
  },
  util = 0x8082b40,
  date = 0,
  parents = 0x8ff5180,
  tree = 0x0,
  buffer = 0x0
}

tree == 0x0? Strange, I don't get why it is NULL, the initial commit definitely hase a tree (git cat-file -p initial-commit shows a tree name and there is a tree with that object name).

The structure looks like this:

    o---o-o-o---o-o-o-o-o
     \   ____\_/
      \ /     \
       o-------o-o-o-o

Fsck reports no errors. Still looking into it.

Alex Riesen, Thu, Mar 29, 2007 20:32:37 +0200:

And this is a repo (reconstructed, not the original, of course) which shows the problem. Just run "git merge merge" while on master.

The structure looks like this:

     o---A-o-o---o-o-o-o-AA
      \   ____\_/
       \ /     \
        B-------o-o-o-BB

There is a rename/rename conflict somewhere around A and B commits. The conflict was resolved at the merge points. Now, the problem is that when the merge-recursive generates that virtual merge there seem to be no way to get to the resolved state. The ends up resolving the conflict again, and of course does not do it without intelligent help, leaving index with unresolved entries. git_write_tree fails, returning NULL and the rest breaks.

I just left all three entries in the index for the virtual commit to pick them up: it'll usually(always?) generate a conflict which has to be resolved manually. Many times, perhaps.

The small change in git_write_tree() was useful to see the relevant portion of the index. The output in rename/rename conflict handling code modified to improve its readability: it can be a lot of text.

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

Alex Riesen, Fri, Mar 30, 2007 01:01:56 +0200:

Nah, doesn't do anything good. Does not crash, though.

On Thu, 29 Mar 2007, Alex Riesen wrote:

It's not the initial commit. It's a criss-cross merge, and it's a virtual commit created by a previous level of merging.

Apply this patch to see it blow up much earlier, when that bogus commit with a NULL tree is created.

(I didn't debug *why* that happens, but maybe this gets somebody further)

		Linus

---
 merge-recursive.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

On Thu, 29 Mar 2007, Linus Torvalds wrote:

Well, it happens because "git_write_tree()" returns NULL. Which in turn is because "unmerged_index()" returns true.

merge_trees() tries to clean up the unmerged index, but apparently doesn't do good enough of a job, so git_write_tree() is called with entries still unmerged..

		Linus

Linus Torvalds, Thu, Mar 29, 2007 21:40:53 +0200:

which in turn is because the inner merge has a rename/rename conflict. See the repo in the tarball from <20070329185501.GC2809@steel.home>

I see no "job" at all: no index cleanup there (merge_trees).

Hi,

On Thu, 29 Mar 2007, Linus Torvalds wrote:

Actually, this is not the complete truth.

This particular case has a conflicting rename/rename in an _intermediate_ commit. This _cannot_ be resolved automatically, not even by putting conflict markers into the appropriate files (*1*).

IMHO, there is actually no way merge_trees() can fix the conflicts enough to write a tree.

So, the only way I see to avoid that SEGV is to something like this:

On Fri, 30 Mar 2007, Johannes Schindelin wrote:

I disagree.

It's much better to give a bad intermediate tree than to give up entirely.

If you give up entirely, the merge is basically impossible to complete.

If you give a bad intermediate, the merge will just have potentially more-than-necessary conflicts in the end.

This really isn't acceptable. We're not monotone or one of those projects that thinks that merging is hard. Merging is *easy*.

We're looking for a base version for a merge - think of a three-way merge on a file level. And the easiest base version is actually an empty base file (or, when it comes to a rename conflict, no base names at all).

Sure, that will make all changes conflict, but that's a *hell* of a lot better than giving up. It just means that now the user has to figure out what the end result should be - exactly the same way that if you have an empty file as a base version, a three-way merge will basically generate a conflict marker that looks like

	<<<<
	one version of the file
	====
	the other version of the file
	>>>>

Rule #1 when merging should *always* be: "never leave the user high and dry". You don't give up and say "I can't merge this". You say "I couldn't merge this, but here's the mess I left for you to show me how it's done!"

		Linus

On Fri, 30 Mar 2007, Linus Torvalds wrote:

Note that "easiest" isn't "best".

For data conflicts in intermediate merges, we use the conficted file, conflict markers and all, as the base.

I suspect we should do exactly the same for filename conflicts. Write the intermediate tree with *both* files, including conflict markers. I'd suggest writing out the conflicting names to the intermediate tree *exactly* the same way we do for the final tree in the working tree, but mayne we could just write them with the SHA of the content appended to the filename or something..)

		Linus

Linus Torvalds, Sat, Mar 31, 2007 03:03:36 +0200:

The names are already different (base->a, base->b), what is the SHA for? I tried leaving all three names in the computed tree (base, a and b). The result is sometimes spectacular, but seldom useful.

This patch leaves the base name in the resulting intermediate tree, to propagate the conflict from intermediate merges up to the top-level merge. ---

The result seem to be at least predictable. Still, doesn't it mean that once a rename/rename conflict is in it has to be resolved manually forever?

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

Alex Riesen wrote:

What about git-rerere2 idea (recording resolving of tree-level conflicts, i.e. rename/rename and such)?

Hi,

On Sat, 31 Mar 2007, Alex Riesen wrote:

I'd rather have conflict files, i.e.

	for each entry in the index which is unmerged,
		write the file in this form:
		<<<<<<
		[stage2]
		======
		[stage3]
		>>>>>>

		mark as merged (i.e. remove stages 1--3 from the index, 
		and add the conflicted file as stage 0)

The big problem is that you _cannot_ leave unmerged entries in 
intermediate stages, because then, you could not write the tree. OTOH, you 
_need_ to mark them as unmerged _in the end_.
		
That problem keeps me from just whipping up a patch in a few minutes, 
sending it untested to the list, and get all the blame for it.

Ciao, Dscho

Hi,

On Sat, 31 Mar 2007, Johannes Schindelin wrote:

Side note: for the "src->dest1,dest2" case, I really would like to see a threeway merge. But I would want the above-mentioned behaviour _before_ that, to make sure that we have a reasonable fallback for hard cases.

Ciao, Dscho

On Sat, 31 Mar 2007, Alex Riesen wrote:

No. It means that that particular rename/rename conflict has to be resolved *once*, since after that, the new merge will become the merge-base for future merges.

Now, that doesn't mean that you may not end up having that same conflict show up over and over again, because the new merge-base may (obviously) end up being a situation where the rename/rename conflict will continue to exist later on (because it conflicts with what the repo you pulled from will continue to have), but that's really no different from any other conflict..

The only way to resolve some conflicts in the long run is to either 
 - converge on some common case (ie normally by merging both ways 
   eventually, or just try to converge otherwise)
 - remember the conflict resolution and re-doing it automatically (ie 
   "git rerere" for rename conflicts)

That's very fundamental, btw. I don't think there *is* any other way to do automatic merges in the long run, it has nothing to do with this particular issue, it's a generic property of automatic merging.

Junio - I think Alex' patch is better than what we have right now (which is dying - whether with a SIGSEGV or a die() doesn't much matter), so it should be applied. It probably isn't perfect, and I bet we can tweak the resolution to something much better - Dscho seems to have ideas in that areas. But:

	Acked-by: Linus Torvalds <torvalds@linux-foundation.org>

in the meantime.

One thing we could/probably should do is to perhaps just add a flag about "intermediate merges had complex issues", and refuse to commit the result even if it looked "clean" in the end. It's better to make people perhaps have to do an "unnecessary" extra git-commit, than to silently commit something that might have been mis-merged. Just ask people to "please verify the end result" kind of thing..

		Linus

Linus Torvalds, Sat, Mar 31, 2007 18:07:56 +0200:

Signed-off-by: Alex Riesen <raa.lkml@gmail.com>

That'd be using the return value of inner merge which we historically do not do. Corresponding comment is in place: "The cleanness flag is ignored, it was never actually used, as result of merge_trees has always overwritten it: the committed conflicts were already resolved". Somehow it does not help to understand "why" the cleanliness of the inner merge does not matter...

Alex Riesen <raa.lkml@gmail.com> writes:

I've eyeballed not your patch but the entire merge-recursive again, to make sure that the codepath you are touching is the only one that can potentially leave higher stages in the index for intermediate merge. Anything that calls update_file() for intermediate merge ends up doing add_cacheinfo() hence drops higher stages for that path, and it seems that the function you are changing, conflict_rename_rename, is the only one that leaves unmerged entries in the tree, so I think thi is good. The assertion you added to git_write_tree() is good way to catch if the above assumption was wrong and we missed other codepaths.

That's certainly better than segfaulting, and in my opinion, it is much better than silently giving a wrong merge result assuming one conflict resolution.

We've been resolving other cases that we should not usually resolve for intermediate merges, leaning on the safer side. For example, look at what delete/modify does for an intermediate merge. It leaves the modified contents in the index.

The reason an intermediate merge conflicts is because the two branches resolved the same (not necessarily "exactly the same") merges differently earlier. That means the two people who made those ancestor merges could not agree on something. Because they could not agree on, you end up being responsible for reconciling their differences in opinion. I do not think it is a bad thing -- in fact, I even think it is a good thing. Forks do not have to converge and you have an opportunity to decide which side you are on for yourself.

An illustration.

Suppose there is a project that has incorrect documentation, and Alice and Bob worked on it separately. Alice finds the documentation's language horrible and makes typofixes, while in Bob's opinion its contents, even if its language were to be improved, keeping the incorrect documentation spreads misinformation and it is worthless. Bob deletes the incorrect documentation and keeps working on other things.

         .------------A1--A2------------A
        /   modify doc \ / take "modify"
       /                X  and later improve          
      /                / \           
  ---o---------------B1---B2------------B
           delete doc     take "delete"

In short, Alice modified and Bob deleted, and reached point A1 and B1, respectively.

Now Alice pulls from Bob, hand-resolves the delete/modify and improves the contents to make it not just language clean (which she did in the previous steps leading to A1) but technically accurate. She now is at point A2, but haven't pushed her changes out yet. She continues to work and reaches A

In the meantime Bob is making further changes to the parts of the system the documentation used to describe. Bob commits his changes, pulls from Alice's last published one A1, and gets delete/modify conflict in the doc, and he takes the deletion and merge result is B2. He continues to work and reaches B.

Later Charlie clones from Bob's B, and tries to merge from Alice's A. There are two merge bases (A1 and B1), so an attempt to merge the merge bases is made by recursive. This gives delete/modify conflict. We leave the modified contents in this intermediate "virtual ancestor" tree, but the end result is that Charlie has a chance to resolve this delete/modify conflict Alice and Bob could not agree on for himself.

If Charlie thinks the same way as Alice and it is a good idea to keep the documentation up to date, he might do something like Alice did at A2. If on the other hand Charlie agrees with Bob at B2, he might take delete. I think leaving that decision up to Charlie is not necessarily a bad thing.

Hi,

On Fri, 30 Mar 2007, Linus Torvalds wrote:

Hmm.

What we _could_ do: if the index still contains unmerged entries, then we collapse these into files with conflict markers (in case the file cannot be written, because a directory of the same name exists, we have to save with a unique name, complaining loudly about it, i.e. without using output()).

I will not have time to implement this until later this week, though.

Ciao, Dscho

On Thu, Mar 29, 2007 at 08:32:37PM +0200, Alex Riesen wrote:

The actual case that caused the error didn't have the initial commit, I used cg-admin-rewritehist to create a (slightly) smaller test case that exhibited the behavior.

  Tom