Segfault in xdl_merge is back

So I've been able to reproduce the segfault that was earlier reported in xdl_merge. Unfortunately its in the repo that I can't publish. I plan to spend some time tomorrow evening to attempt to further debug the problem. I would certainly appreciate any advice. :-)

I can say its *not* related to 1510fea7 (or its fix 5caf9232 for that matter). Tonight I only had a few minutes to look at the issue but reverting 1510fea7/5caf9232 does not fix the segfault on Cygwin, even though 5caf9232 appears to have fixed the issue for the original reporter on Linux.

If I recall it correctly we were segfaulting on line 197 of xmerge.c:

    197         t1.ptr = (char *)xe1->xdf2.recs[m->i1]->ptr;

according to my particular case m->i1 == 70, but it looks like xdf2.recs isn't that large as index 70 is not a valid pointer.

I'm suspecting this is actually some sort of memory corruption in the heap (due to a bad malloc/free) as the bug seems to rear its head only based on the data we are allocating/have allocated.

If you look at what 1510fea7 would do on Linux the 1510fea7 bug would send us into the else case of diff_populate_filespec where we malloc the file data during decompression from the pack. Yet when we fixed it with 5caf9232 we started to mmap the working tree file, avoiding the malloc/free. This behavior, plus the fact that it happens no matter what for a particular merge on Cygwin (but not other merges), leads me to suspect heap corruption.

I may try to bisect this on Cygwin, but I may need to go all the way back to pre-xdl_merge() to get a working merge-recursive, and I may just find the bug pointing at the original merge-recursive code, or just find it pointing at a random commit like what happened with 1510fea7. So bisection may not really help out very much.

Has anyone run merge-recursive through Valgrind lately? I don't have a setup handy to run it through and see if we have any obvious errors.

On Tue, 26 Dec 2006, Shawn Pearce wrote:

Can you try to reproduce it under Linux and use "valgrind" to run the thing that SIGSEGV's? That tends to be a pretty good way to debug bad allocations..

So instead of bisecting it on cygwin, try to use the build that broke on Linux too (ie undo the 5caf9232 "fix") and when you can reproduce it under Linux, compiel withour -O2 and with debug information, and gdb will be a lot more useful, but also run it with valgrind..

		Linus

Linus Torvalds <torvalds@osdl.org> wrote:

Good advice. Unfortunately it may be difficult to get valgrind onto a Linux system where I can also put that repository which is failing.

Junio suggested that I try running git-merge-file on the three blobs that I'm segfaulting on. That's a pretty quick test.

Failing that I may have to find a way to get valgrind onto a Linux system - but that could take a month or more. (The UNIX admins are overworked and don't care much about Linux, and I don't have my own Linux system there.)

I'd really like to get this segfault fixed before 1.5.0 ships. Its a rather nasty bug and I suspect the culprit is already in 1.5.0-rc0.

Hi,

On Tue, 26 Dec 2006, Shawn Pearce wrote:

So here I am again, wanting to help, being unable to. *Sigh*. At least this time it is due to legal reasons, not unknown ones.

As you said in another mail, Junio suggested using git-merge-file on the blobs themselves. This is a little tricky, since git-merge-file does not read blobs; only files. I'd do this:

	- in merge-recursive.c just before line 658 I'd add an
	  fprintf(stderr, "xdl_merge: %s %s %s\n", sha1_to_hex(a->sha1),
		sha1_to_hex(o->sha1), sha1_to_hex(b->sha1));
	- run the merge until it segfaults
	- get the blobs by using the last three SHA1's in the output by
	  $ git-show <sha1>  > a   # or "o" or "b"
	- $ git merge-file -p a o b >/dev/null

This command line ensures that "a" is not edited, and you can repeat the merge as often as needed.

If this still segfaults, I'd like to have the files privately (I will not look at the contents, as they are irrelevant to this particular bug).

Ciao, Dscho

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

I'm seeing the problem here on Linux, I have attached a tarball with a set of files from Wine that trigger the bug.

The gdb backtrace looks like this:

Core was generated by `git-merge-file -p a o b'.
Program terminated with signal 11, Segmentation fault.
#0  0x080b60be in xdl_refine_conflicts (xe1=0xbfcaf22c, xe2=0xbfcaf1a4, m=0x8106668, xpp=0xbfcaf348) at xdiff/xmerge.c:197
197                     t1.ptr = (char *)xe1->xdf2.recs[m->i1]->ptr;
(gdb) bt
#0  0x080b60be in xdl_refine_conflicts (xe1=0xbfcaf22c, xe2=0xbfcaf1a4, m=0x8106668, xpp=0xbfcaf348) at xdiff/xmerge.c:197
#1  0x080b6843 in xdl_do_merge (xe1=0xbfcaf22c, xscr1=0x0, name1=0xbfcafbcf "a", xe2=0xbfcaf1a4, xscr2=0x0, name2=0xbfcafbd3 "b", level=2, xpp=0xbfcaf348, result=0xbfcaf34c) at xdiff/xmerge.c:351
#2  0x080b6b8c in xdl_merge (orig=0xbfcaf35c, mf1=0xbfcaf354, name1=0xbfcafbcf "a", mf2=0xbfcaf364, name2=0xbfcafbd3 "b", xpp=0xbfcaf348, level=2, result=0xbfcaf34c) at xdiff/xmerge.c:408
#3  0x08067887 in cmd_merge_file (argc=4, argv=0xbfcaf4b8, envp=0x0) at builtin-merge-file.c:43
#4  0x0804b0e5 in handle_internal_command (argc=5, argv=0xbfcaf4b4, envp=0xbfcaf4cc) at git.c:294
#5  0x0804b1e7 in main (argc=5, argv=0xbfcaf4b4, envp=0xbfcaf4cc) at git.c:331
(gdb) p *xe1
$1 = {xdf1 = {rcha = {head = 0x8105ca8, tail = 0x8107558, isize = 16, nsize = 1056, ancur = 0x8107558, sncur = 0x0, scurr = 0}, nrec = 259, hbits = 9, rhash = 0x81054a0, dstart = 36, dend = 257, 
    recs = 0x8105080, rchg = 0x80ff009 "", rindex = 0x8107988, nreff = 18, ha = 0x8107da0}, xdf2 = {rcha = {head = 0x8108370, tail = 0x81085b0, isize = 16, nsize = 176, ancur = 0x81085b0, sncur = 0x0, 
      scurr = 0}, nrec = 41, hbits = 6, rhash = 0x8108268, dstart = 36, dend = 39, recs = 0x81081b8, rchg = 0x80ff119 "", rindex = 0x8108670, nreff = 3, ha = 0x8108720}}
(gdb) p *xe2
$2 = {xdf1 = {rcha = {head = 0x81060d8, tail = 0x810aad0, isize = 16, nsize = 1056, ancur = 0x810aad0, sncur = 0x0, scurr = 0}, nrec = 259, hbits = 9, rhash = 0x8104878, dstart = 44, dend = 43, 
    recs = 0x8106b18, rchg = 0x8106509 "", rindex = 0x810b998, nreff = 0, ha = 0x810bdb0}, xdf2 = {rcha = {head = 0x810ce20, tail = 0x810db40, isize = 16, nsize = 1104, ancur = 0x810db40, sncur = 0x0, 
      scurr = 0}, nrec = 270, hbits = 9, rhash = 0x810c618, dstart = 44, dend = 54, recs = 0x810c1c8, rchg = 0x8106f39 "", rindex = 0x810dfa0, nreff = 8, ha = 0x810e3e0}}
(gdb) p *m
$3 = {next = 0x0, mode = 0, i1 = 41, i2 = 41, chg1 = 0, chg2 = 229}

And here's the Valgrind output:

==32758== Memcheck, a memory error detector. ==32758== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al. ==32758== Using LibVEX rev 1658, a library for dynamic binary translation. ==32758== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP. ==32758== Using valgrind-3.2.1-Debian, a dynamic binary instrumentation framework. ==32758== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al. ==32758== For more details, rerun with: -v ==32758== ==32758== Use of uninitialised value of size 4 ==32758== at 0x80B60BE: xdl_refine_conflicts (xmerge.c:197) ==32758== by 0x80B6842: xdl_do_merge (xmerge.c:351) ==32758== by 0x80B6B8B: xdl_merge (xmerge.c:408) ==32758== by 0x8067886: cmd_merge_file (builtin-merge-file.c:43) ==32758== by 0x804B0E4: handle_internal_command (git.c:294) ==32758== by 0x804B1E6: main (git.c:331) ==32758== ==32758== Invalid read of size 4 ==32758== at 0x80B60BE: xdl_refine_conflicts (xmerge.c:197) ==32758== by 0x80B6842: xdl_do_merge (xmerge.c:351) ==32758== by 0x80B6B8B: xdl_merge (xmerge.c:408) ==32758== by 0x8067886: cmd_merge_file (builtin-merge-file.c:43) ==32758== by 0x804B0E4: handle_internal_command (git.c:294) ==32758== by 0x804B1E6: main (git.c:331) ==32758== Address 0x4 is not stack'd, malloc'd or (recently) free'd ==32758== ==32758== Process terminating with default action of signal 11 (SIGSEGV): dumping core ==32758== Access not within mapped region at address 0x4 ==32758== at 0x80B60BE: xdl_refine_conflicts (xmerge.c:197) ==32758== by 0x80B6842: xdl_do_merge (xmerge.c:351) ==32758== by 0x80B6B8B: xdl_merge (xmerge.c:408) ==32758== by 0x8067886: cmd_merge_file (builtin-merge-file.c:43) ==32758== by 0x804B0E4: handle_internal_command (git.c:294) ==32758== by 0x804B1E6: main (git.c:331)

Hope this helps,

The function xdl_refine_conflicts() tries to break down huge conflicts by doing a diff on the conflicting regions. However, this does not make sense when one side is empty.

Worse, when one side is not only empty, but after EOF, the code accessed unmapped memory.

Noticed by Luben Tuikov, Shawn Pearce and Alexandre Julliard, the latter providing a test case.

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

	Thank you Alexandre! I looked for the bug for quite some time, but 
	was never close to the real culprit.

 t/t6023-merge-file.sh |   22 ++++++++++++++++++++++
 xdiff/xmerge.c        |    4 ++++
 2 files changed, 26 insertions(+), 0 deletions(-)

Thank you, everybody.

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

Thanks for fixing this!
 

As a side note I lately have noticed that xdl_merge is producing a conflict like the above when one branch added the lower half and the other branch didn't change anything in the area.

I haven't spent any time to try to reproduce it, or to see if RCS' merge utility would automatically merge the file without producing a conflict. But right now it does seem like xdl_merge is producing conflicts when I didn't think it should be.

Hi,

On Thu, 28 Dec 2006, Shawn Pearce wrote:

I thought very long about that problem. It looks like a bug, but it is not. At least in my humble opinion.

If you touched the same spot in two different versions, say you added a fix in one branch, and that fix and a comment in the other one, you might be tempted to automatically resolve that conflict, taking the version with the comment.

But it helps you catch mismerges: If you add a chunk of identical code in the two branches, but with an increment _before_ it in one branch, and _after_ it in the other branch, both should be marked as a conflict.

Of course, you can hit mismerges like the illustrated one _without_ being marked as conflict (e.g. if the chunk of identical code is _not_ added, but only the increments), but we should at least avoid them where possible.

Ciao, Dscho

<opublikowany i wysłany>

Johannes Schindelin wrote:

Perhaps you could make it even more conservating merge conflicts option (to tighten merge conflicts even more) to xdl_merge, but not used by default because as it removes accidental conflicts it increases mismerges (falsely not conflicted).

Hi,

On Sat, 30 Dec 2006, Jakub Narebski wrote:

There is no way to do this sanely. If you want to catch these mismerges, you have to mark _all_ modifications as conflicting.

Ciao, Dscho

On Sun, 31 Dec 2006, Johannes Schindelin wrote:

Currently you have:
 - a level value of 0 means that all overlapping changes are treated
   as conflicts,
 - a value of 1 means that if the overlapping changes are identical,
   it is not treated as a conflict.
 - If you set level to 2, overlapping changes will be analyzed, so that
   almost identical changes will not result in huge conflicts. Rather,
   only the conflicting lines will be shown inside conflict markers.

I was thinking about:
 - If you set level to 3, if one part after overlapping changes analysis
   in level 2 has empty conflict region, resolve this conflict as second
   side. WARNING: this reduces number of merge conflicts, but might give
   mismerges!

Or something like that.

Hi,

On Tue, 2 Jan 2007, Jakub Narebski wrote:

That is certainly a possibility! But how would you specify it? If you do it as a command line option, you'd have to add it to git-merge, git-pull, git-merge-recursive and git-merge-file. Ugly.

You could do it as a config variable, but git-merge-file operates without a git repository. And you'd want it to be overrideable anyway.

Environment variable? Too unfriendly to users, because it is not really a proper UI.

It is certainly easy enough to teach the code (but might introduce unwanted side effects, when the _deletion_, not the _addition_ was what you wanted):

 xdiff/xdiff.h  |    1 +
 xdiff/xmerge.c |   21 ++++++++++++++++++---
 2 files changed, 19 insertions(+), 3 deletions(-)

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

Another thing to worry about is that this would make things "works most of the time but when it fails it fails silently" which would lead to very hard to detect problem in the project managed by git. I'd be very hesitant about this for this reason alone.

Hi,

On Tue, 2 Jan 2007, Junio C Hamano wrote:

Right. That was what I was alluding to with my comment "what if you prefer the deletion over the addition?"

It _seems_ clever at first sight, but it isn't.

Ciao, Dscho