git-merge segfault in 1.6.6 and master

git-merge segfault in 1.6.6 and master

[Tim Olsen]

The following happens on 1.6.6 and master as of
5b15950ac414a8a2d4f5eb480712abcc9fe176d2.  The problem goes away if I
use the resolve merge strategy instead.

tolsen@neurofunk:~/git/site-build-dav-sync-05 [git:build-dav-sync-05]$
gdb --args git merge origin/deployed
GNU gdb (GDB) 7.0-debian
Copyright (C) 2009 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later
<http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /usr/local/bin/git...done.
(gdb) r
Starting program: /usr/local/bin/git merge origin/deployed
[Thread debugging using libthread_db enabled]

Program received signal SIGSEGV, Segmentation fault.
*__GI_memcmp (s1=0x4, s2=0x77b034, len=20) at memcmp.c:339
339	memcmp.c: No such file or directory.
	in memcmp.c
(gdb) bt full
#0  *__GI_memcmp (s1=0x4, s2=0x77b034, len=20) at memcmp.c:339
        srcp1 = <value optimized out>
        srcp2 = <value optimized out>
        res = <value optimized out>
#1  0x0000000000495c12 in hashcmp (sha1=0x4 <Address 0x4 out of bounds>,
sha2=0x77b034 "\304\037Eg\262\367\256\367\376\061홚\331\037\bQ\231\332",
<incomplete sequence \370>) at cache.h:620
No locals.
#2  0x0000000000495ca3 in sha_eq (a=0x4 <Address 0x4 out of bounds>,
b=0x77b034 "\304\037Eg\262\367\256\367\376\061홚\331\037\bQ\231\332",
<incomplete sequence \370>) at merge-recursive.c:60
No locals.
#3  0x0000000000499523 in merge_trees (o=0x7fffffffd5b0, head=0x77b058,
merge=0x77b030, common=0x0, result=0x7fffffffd548) at merge-recursive.c:1209
        code = 8076320
        clean = 13064
#4  0x0000000000499a46 in merge_recursive (o=0x7fffffffd5b0,
h1=0x7932d0, h2=0x793240, ca=0x7b3c00, result=0x7fffffffd628) at
merge-recursive.c:1343
        iter = 0x0
        merged_common_ancestors = 0x121e360
        mrtree = 0x7b3c20
        clean = 0
#5  0x000000000043eee6 in try_merge_strategy (strategy=0x4f2078
"recursive", common=0x787170, head_arg=0x4f2570 "HEAD") at
builtin-merge.c:577
        clean = 0
        reversed = 0x7b3c20
        o = {branch1 = 0x4f2570 "HEAD", branch2 = 0x7fffffffdf33
"origin/deployed", subtree_merge = 0, buffer_output = 1, verbosity = 2,
diff_rename_limit = -1, merge_rename_limit = -1, call_depth = 0, obuf =
{alloc = 0, len = 0,
            buf = 0x775ee8 ""}, current_file_set = {items = 0x1220510,
nr = 11526, alloc = 11552, strdup_strings = 1}, current_directory_set =
{items = 0x1203b80, nr = 2957, alloc = 2976, strdup_strings = 1}}
        result = 0x303035302d203031
        lock = 0x7b3d40
        index_fd = 15
        args = 0x7fffffffd6a0
        i = 0
        ret = 2
        j = 0x0
        buf = {alloc = 0, len = 0, buf = 0x775ee8 ""}
        index_fd = 15
        lock = 0x7b2900
#6  0x00000000004407d4 in cmd_merge (argc=1, argv=0x7fffffffda90,
prefix=0x0) at builtin-merge.c:1134
        ret = 0
        result_tree =
"\200\332\377\377\377\177\000\000\000\000\000\000\000\000\000\000\024\000\000"
        buf = {alloc = 60, len = 0, buf = 0x7762d0 ""}
        head_arg = 0x4f2570 "HEAD"
        flag = 1
        head_invalid = 0
        i = 0
        best_cnt = -1
        merge_was_ok = 0
        automerge_was_ok = 0
        common = 0x787170
        best_strategy = 0x0
        wt_strategy = 0x4f2078 "recursive"
        remotes = 0x776838
#7  0x000000000040488f in run_builtin (p=0x729b48, argc=2,
argv=0x7fffffffda90) at git.c:257
        status = 1647275105
        help = 0
        st = {st_dev = 0, st_ino = 0, st_nlink = 7509264, st_mode =
4158578380, st_uid = 32767, st_gid = 1, __pad0 = 0, st_rdev = 0, st_size
= 7508768, st_blksize = 140737340287064, st_blocks =
3403153865682452481, st_atim = {tv_sec = 0,
            tv_nsec = 140737488345392}, st_mtim = {tv_sec =
140737351990853, tv_nsec = 140737488345752}, st_ctim = {tv_sec = 134688,
tv_nsec = 0}, __unused = {5129592, 140737488346931, 0}}
        prefix = 0x0
#8  0x0000000000404a1a in handle_internal_command (argc=2,
argv=0x7fffffffda90) at git.c:401
        p = 0x729b48
        cmd = 0x7fffffffdf2d "merge"
        i = 47
        commands = {{cmd = 0x4e4871 "add", fn = 0x405778 <cmd_add>,
option = 5}, {cmd = 0x4e4875 "stage", fn = 0x405778 <cmd_add>, option =
5}, {cmd = 0x4e487b "annotate", fn = 0x405b84 <cmd_annotate>, option =
1}, {cmd = 0x4e4884 "apply",
            fn = 0x40da8e <cmd_apply>, option = 0}, {cmd = 0x4e488a
"archive", fn = 0x40e7c6 <cmd_archive>, option = 0}, {cmd = 0x4e4892
"bisect--helper", fn = 0x40ea7c <cmd_bisect__helper>, option = 5}, {cmd
= 0x4e48a1 "blame",
            fn = 0x413481 <cmd_blame>, option = 1}, {cmd = 0x4e48a7
"branch", fn = 0x415393 <cmd_branch>, option = 1}, {cmd = 0x4e48ae
"bundle", fn = 0x415bb4 <cmd_bundle>, option = 0}, {cmd = 0x4e48b5
"cat-file", fn = 0x416484 <cmd_cat_file>,
            option = 1}, {cmd = 0x4e48be "checkout", fn = 0x4197c5
<cmd_checkout>, option = 5}, {cmd = 0x4e48c7 "checkout-index", fn =
0x417514 <cmd_checkout_index>, option = 5}, {cmd = 0x4e48d6
"check-ref-format",
            fn = 0x416cf2 <cmd_check_ref_format>, option = 0}, {cmd =
0x4e48e7 "check-attr", fn = 0x416a73 <cmd_check_attr>, option = 1}, {cmd
= 0x4e48f2 "cherry", fn = 0x437b3e <cmd_cherry>, option = 1}, {cmd =
0x4e48f9 "cherry-pick",
            fn = 0x456fd1 <cmd_cherry_pick>, option = 5}, {cmd =
0x4e4905 "clone", fn = 0x41b4b5 <cmd_clone>, option = 0}, {cmd =
0x4e490b "clean", fn = 0x41a198 <cmd_clean>, option = 5}, {cmd =
0x4e4911 "commit", fn = 0x41f144 <cmd_commit>,
            option = 5}, {cmd = 0x4e4918 "commit-tree", fn = 0x41c4a0
<cmd_commit_tree>, option = 1}, {cmd = 0x4e4924 "config", fn = 0x420398
<cmd_config>, option = 0}, {cmd = 0x4e492b "count-objects", fn =
0x420e9a <cmd_count_objects>,
            option = 1}, {cmd = 0x4e4939 "describe", fn = 0x421e8a
<cmd_describe>, option = 1}, {cmd = 0x4e4942 "diff", fn = 0x4238dc
<cmd_diff>, option = 0}, {cmd = 0x4e4947 "diff-files", fn = 0x422454
<cmd_diff_files>, option = 5}, {
            cmd = 0x4e4952 "diff-index", fn = 0x4226b0 <cmd_diff_index>,
option = 1}, {cmd = 0x4e495d "diff-tree", fn = 0x422bb1 <cmd_diff_tree>,
option = 1}, {cmd = 0x4e4967 "fast-export", fn = 0x42553f
<cmd_fast_export>, option = 1}, {
            cmd = 0x4e4973 "fetch", fn = 0x429fb8 <cmd_fetch>, option =
1}, {cmd = 0x4e4979 "fetch-pack", fn = 0x4275da <cmd_fetch_pack>, option
= 1}, {cmd = 0x4e4984 "fmt-merge-msg", fn = 0x42b17a
<cmd_fmt_merge_msg>, option = 1}, {
            cmd = 0x4e4992 "for-each-ref", fn = 0x42d287
<cmd_for_each_ref>, option = 1}, {cmd = 0x4e499f "format-patch", fn =
0x436a1f <cmd_format_patch>, option = 1}, {cmd = 0x4e49ac "fsck", fn =
0x42eae7 <cmd_fsck>, option = 1}, {
            cmd = 0x4e49b1 "fsck-objects", fn = 0x42eae7 <cmd_fsck>,
option = 1}, {cmd = 0x4e49be "gc", fn = 0x42f26b <cmd_gc>, option = 1},
{cmd = 0x4e49c1 "get-tar-commit-id", fn = 0x45ea9f
<cmd_get_tar_commit_id>, option = 0}, {
            cmd = 0x4e49d3 "grep", fn = 0x431505 <cmd_grep>, option =
3}, {cmd = 0x4e49d8 "help", fn = 0x4332b8 <cmd_help>, option = 0}, {cmd
= 0x4e49dd "init", fn = 0x43420d <cmd_init_db>, option = 0}, {cmd =
0x4e49e2 "init-db",
            fn = 0x43420d <cmd_init_db>, option = 0}, {cmd = 0x4e49ea
"log", fn = 0x43560b <cmd_log>, option = 3}, {cmd = 0x4e49ee "ls-files",
fn = 0x438f72 <cmd_ls_files>, option = 1}, {cmd = 0x4e49f7 "ls-tree", fn
= 0x439f6b <cmd_ls_tree>,
            option = 1}, {cmd = 0x4e49ff "ls-remote", fn = 0x43993f
<cmd_ls_remote>, option = 0}, {cmd = 0x4e4a09 "mailinfo", fn = 0x43c72d
<cmd_mailinfo>, option = 0}, {cmd = 0x4e4a12 "mailsplit", fn = 0x43d20c
<cmd_mailsplit>, option = 0}, {
            cmd = 0x4e4a1c "merge", fn = 0x43fc4b <cmd_merge>, option =
5}, {cmd = 0x4e4a22 "merge-base", fn = 0x440d14 <cmd_merge_base>, option
= 1}, {cmd = 0x4e4a2d "merge-file", fn = 0x440f0a <cmd_merge_file>,
option = 0}, {
            cmd = 0x4e4a38 "merge-ours", fn = 0x441408 <cmd_merge_ours>,
option = 1}, {cmd = 0x4e4a43 "merge-recursive", fn = 0x4414e2
<cmd_merge_recursive>, option = 5}, {cmd = 0x4e4a53 "merge-subtree", fn
= 0x4414e2 <cmd_merge_recursive>,
            option = 5}, {cmd = 0x4e4a61 "mktree", fn = 0x441d15
<cmd_mktree>, option = 1}, {cmd = 0x4e4a68 "mv", fn = 0x44210b <cmd_mv>,
option = 5}, {cmd = 0x4e4a6b "name-rev", fn = 0x443251 <cmd_name_rev>,
option = 1}, {
            cmd = 0x4e4a74 "pack-objects", fn = 0x44821f
<cmd_pack_objects>, option = 1}, {cmd = 0x4e4a81 "peek-remote", fn =
0x43993f <cmd_ls_remote>, option = 0}, {cmd = 0x4e4a8d "pickaxe", fn =
0x413481 <cmd_blame>, option = 1}, {
            cmd = 0x4e4a95 "prune", fn = 0x449431 <cmd_prune>, option =
1}, {cmd = 0x4e4a9b "prune-packed", fn = 0x448e33 <cmd_prune_packed>,
option = 1}, {cmd = 0x4e4aa8 "push", fn = 0x449cdd <cmd_push>, option =
1}, {cmd = 0x4e4aad "read-tree",
            fn = 0x44a28d <cmd_read_tree>, option = 1}, {cmd = 0x4e4ab7
"receive-pack", fn = 0x44be59 <cmd_receive_pack>, option = 0}, {cmd =
0x4e4ac4 "reflog", fn = 0x44daf6 <cmd_reflog>, option = 1}, {cmd =
0x4e4acb "remote",
            fn = 0x4519b9 <cmd_remote>, option = 1}, {cmd = 0x4e4ad2
"replace", fn = 0x451fa9 <cmd_replace>, option = 1}, {cmd = 0x4e4ada
"repo-config", fn = 0x420398 <cmd_config>, option = 0}, {cmd = 0x4e4ae6
"rerere",
            fn = 0x452698 <cmd_rerere>, option = 1}, {cmd = 0x4e4aed
"reset", fn = 0x4530cf <cmd_reset>, option = 1}, {cmd = 0x4e4af3
"rev-list", fn = 0x4540be <cmd_rev_list>, option = 1}, {cmd = 0x4e4afc
"rev-parse",
            fn = 0x45537f <cmd_rev_parse>, option = 0}, {cmd = 0x4e4b06
"revert", fn = 0x456f84 <cmd_revert>, option = 5}, {cmd = 0x4e4b0d "rm",
fn = 0x457368 <cmd_rm>, option = 1}, {cmd = 0x4e4b10 "send-pack", fn =
0x458c65 <cmd_send_pack>,
---Type <return> to continue, or q <return> to quit---
            option = 1}, {cmd = 0x4e4b1a "shortlog", fn = 0x459c27
<cmd_shortlog>, option = 2}, {cmd = 0x4e4b23 "show-branch", fn =
0x45b3b7 <cmd_show_branch>, option = 1}, {cmd = 0x4e4b2f "show", fn =
0x43511f <cmd_show>, option = 3}, {
            cmd = 0x4e4b34 "status", fn = 0x41ec30 <cmd_status>, option
= 5}, {cmd = 0x4e4b3b "stripspace", fn = 0x45cf9d <cmd_stripspace>,
option = 0}, {cmd = 0x4e4b46 "symbolic-ref", fn = 0x45d0f3
<cmd_symbolic_ref>, option = 1}, {
            cmd = 0x4e4b53 "tag", fn = 0x45df1e <cmd_tag>, option = 1},
{cmd = 0x4e4b57 "tar-tree", fn = 0x45e8b4 <cmd_tar_tree>, option = 0},
{cmd = 0x4e4b60 "unpack-objects", fn = 0x45fe1f <cmd_unpack_objects>,
option = 1}, {
            cmd = 0x4e4b6f "update-index", fn = 0x461634
<cmd_update_index>, option = 1}, {cmd = 0x4e4b7c "update-ref", fn =
0x461fac <cmd_update_ref>, option = 1}, {cmd = 0x4e4b87
"update-server-info", fn = 0x4622f8 <cmd_update_server_info>,
            option = 1}, {cmd = 0x4e4b9a "upload-archive", fn = 0x4627e4
<cmd_upload_archive>, option = 0}, {cmd = 0x4e4ba9 "verify-tag", fn =
0x4634ba <cmd_verify_tag>, option = 1}, {cmd = 0x4e4bb4 "version", fn =
0x491586 <cmd_version>,
            option = 0}, {cmd = 0x4e4bbc "whatchanged", fn = 0x434df8
<cmd_whatchanged>, option = 3}, {cmd = 0x4e4bc8 "write-tree", fn =
0x463614 <cmd_write_tree>, option = 1}, {cmd = 0x4e4bd3 "verify-pack",
fn = 0x462fb3 <cmd_verify_pack>,
            option = 0}, {cmd = 0x4e4bdf "show-ref", fn = 0x45cb53
<cmd_show_ref>, option = 1}, {cmd = 0x4e4be8 "pack-refs", fn = 0x448ad0
<cmd_pack_refs>, option = 1}}
        ext = ""
#9  0x0000000000404b00 in run_argv (argcp=0x7fffffffd984,
argv=0x7fffffffd978) at git.c:443
        done_alias = 0
#10 0x0000000000404c51 in main (argc=2, argv=0x7fffffffda90) at git.c:514
        cmd = 0x7fffffffdf2d "merge"
        done_help = 0
        was_alias = 0
(gdb)

Re: git-merge segfault in 1.6.6 and master

[Junio C Hamano]

Tim Olsen <tim@brooklynpenguin.com> writes:

> The following happens on 1.6.6 and master as of
> 5b15950ac414a8a2d4f5eb480712abcc9fe176d2.  The problem goes away if I
> use the resolve merge strategy instead.

Thanks.

Since you can build and run git yourself, can I ask you to run another
experiment with this one-liner patch applied?

diff --git a/builtin-merge.c b/builtin-merge.c
index 82e2a04..08a8f24 100644
--- a/builtin-merge.c
+++ b/builtin-merge.c
@@ -550,7 +550,7 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 		return error("Unable to write index.");
 	rollback_lock_file(lock);
 
-	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree")) {
+	if (0) {
 		int clean;
 		struct commit *result;
 		struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));

This disables the codepath that special-cases the calling convention for
these merge strategies, and was introduce by 18668f5 (builtin-merge: avoid
run_command_v_opt() for recursive and subtree, 2008-08-28 -- authors Cc'ed
to ask for help in diagnosing).

If this experiment "fixes" the failure for you, then it would be a sign
that the caller (not necessarily in the code in this "if()" block) may be
doing something wrong (or more likely, not doing enough) before calling
into merge_recursive().  I am suspecting that it is not parsing some
commit objects properly, e.g. using lookup_commit(SHA-1) and using the
result without calling parse_object() on it first, or something similar
that is silly but trivial to fix.

After the experiment, please revert the above one-liner.  I don't want to
use a work-around forever; we'd be better off finding where in the code it
goes wrong.  Looking at your gdb trace, I notice...

> (gdb) r
> Starting program: /usr/local/bin/git merge origin/deployed
> [Thread debugging using libthread_db enabled]
> ...
> #3  0x0000000000499523 in merge_trees (o=0x7fffffffd5b0, head=0x77b058,
> merge=0x77b030, common=0x0, result=0x7fffffffd548) at merge-recursive.c:1209
>         code = 8076320
>         clean = 13064

"common = NULL" means merged_common_ancestors->tree is NULL in the caller.
Somebody is passing a bogus commit in "ca" (aka common ancestors) list
when calling merge_recursive(), or forgetting to parse them before calling
it.  In your debugger could you find out where it comes from and what it
has before this call into merge_trees() is made?  Specifically, what the
"ca" list at 0x7b3c00 contains, and how "merged_common_ancestors" at
0x121e360 looks like. in this trace we see below:

> #4  0x0000000000499a46 in merge_recursive (o=0x7fffffffd5b0,
> h1=0x7932d0, h2=0x793240, ca=0x7b3c00, result=0x7fffffffd628) at
> merge-recursive.c:1343

Re: git-merge segfault in 1.6.6 and master

[Tim Olsen]

Junio C Hamano wrote:
> Thanks.

Thanks for taking the time to look into this!

> 
> Since you can build and run git yourself, can I ask you to run another
> experiment with this one-liner patch applied?

It appears that a segfault still happens with your patch applied, but
this time it is caught:

tolsen@neurofunk:~/git/site-build-dav-sync-05 [git:build-dav-sync-05]$
git merge origin/deployed
error: merge-recursive died of signal 11
Merge with strategy recursive failed.
tolsen@neurofunk:~/git/site-build-dav-sync-05 [git:build-dav-sync-05]$


> "common = NULL" means merged_common_ancestors->tree is NULL in the caller.
> Somebody is passing a bogus commit in "ca" (aka common ancestors) list
> when calling merge_recursive(), or forgetting to parse them before calling
> it.  In your debugger could you find out where it comes from and what it
> has before this call into merge_trees() is made?  Specifically, what the
> "ca" list at 0x7b3c00 contains, and how "merged_common_ancestors" at
> 0x121e360 looks like. in this trace we see below:

Here is the replay of the flow of execution from the first time we enter
merge_recursive().  The repository has been modified slightly so the
pointers are different this time but the segfault is still happening
(I'll stop modifying the repository now ;-) .

Upon entering merge_recursive() for the first time, ca is a two-item
list and both items have non-null trees:

Breakpoint 1, merge_recursive (o=0x7fffffffd560, h1=0x793350,
h2=0x7932c0, ca=0x7b4a40, result=0x7fffffffd5d8) at merge-recursive.c:1286
(gdb) p *ca
$1 = {item = 0x793db8, next = 0x7b4a20}
(gdb) p *(ca->next)
$2 = {item = 0x793aa0, next = 0x0}
(gdb) p ca->item->tree
$3 = (struct tree *) 0x77be10
(gdb) p ca->next->item->tree
$4 = (struct tree *) 0x77b488
(gdb)

Then on line 1303, the head of ca is popped off into
merged_common_ancestors:

Breakpoint 2, merge_recursive (o=0x7fffffffd560, h1=0x793350,
h2=0x7932c0, ca=0x7b4a20, result=0x7fffffffd5d8) at merge-recursive.c:1304
(gdb) list
1299			for (iter = ca; iter; iter = iter->next)
1300				output_commit_title(o, iter->item);
1301		}
1302	
1303		merged_common_ancestors = pop_commit(&ca);
1304		if (merged_common_ancestors == NULL) {
1305			/* if there is no common ancestor, make an empty tree */
1306			struct tree *tree = xcalloc(1, sizeof(struct tree));
1307	
1308			tree->object.parsed = 1;
(gdb) p merged_common_ancestors
$5 = (struct commit *) 0x793db8
(gdb) p ca
$8 = (struct commit_list *) 0x7b4a20

merge_recursive() is then called recursively at line 1329 with a pointer
to merged_common_ancestors passed as the "result" argument:

Breakpoint 3, merge_recursive (o=0x7fffffffd560, h1=0x793350,
h2=0x7932c0, ca=0x7b4a20, result=0x7fffffffd5d8) at merge-recursive.c:1329
(gdb) list
1324			discard_cache();
1325			saved_b1 = o->branch1;
1326			saved_b2 = o->branch2;
1327			o->branch1 = "Temporary merge branch 1";
1328			o->branch2 = "Temporary merge branch 2";
1329			merge_recursive(o, merged_common_ancestors, iter->item,
1330					NULL, &merged_common_ancestors);
1331			o->branch1 = saved_b1;
1332			o->branch2 = saved_b2;
1333			o->call_depth--;
(gdb)

In the second call to merged_common_ancestors(), result's pointee is
replaced by a commit with a null tree at line 1347:

Breakpoint 4, merge_recursive (o=0x7fffffffd560, h1=0x793db8,
h2=0x793aa0, ca=0x0, result=0x7fffffffd500) at merge-recursive.c:1347
(gdb) n
(gdb) p (*result)->tree
$10 = (struct tree *) 0x0
(gdb) list
1343		clean = merge_trees(o, h1->tree, h2->tree,
merged_common_ancestors->tree,
1344				    &mrtree);
1345	
1346		if (o->call_depth) {
1347			*result = make_virtual_commit(mrtree, "merged tree");
1348			commit_list_insert(h1, &(*result)->parents);
1349			commit_list_insert(h2, &(*result)->parents->next);
1350		}
1351		flush_output(o);
1352		return clean;
(gdb)

make_virtual_commit() is just setting its tree to mrtree:

Breakpoint 5, make_virtual_commit (tree=0x0, comment=0x5016fc "merged
tree") at merge-recursive.c:44
(gdb) list
39	 * A virtual commit has (const char *)commit->util set to the name.
40	 */
41	
42	static struct commit *make_virtual_commit(struct tree *tree, const
char *comment)
43	{
44		struct commit *commit = xcalloc(1, sizeof(struct commit));
45		commit->tree = tree;
46		commit->util = (void*)comment;
47		/* avoid warnings */
48		commit->object.parsed = 1;
(gdb)
49		return commit;
50	}

At the beginning of merge_recursive(), the local mrtree appears to be
set to some globally defined mrtree which is not null:

Breakpoint 1, merge_recursive (o=0x7fffffffd560, h1=0x793db8,
h2=0x793aa0, ca=0x0, result=0x7fffffffd500) at merge-recursive.c:1286
(gdb) p mrtree
$13 = (struct tree *) 0x7ffff732d0ac
(gdb) list
1281		struct commit_list *iter;
1282		struct commit *merged_common_ancestors;
1283		struct tree *mrtree = mrtree;
1284		int clean;
1285	
1286		if (show(o, 4)) {
1287			output(o, 4, "Merging:");
1288			output_commit_title(o, h1);
1289			output_commit_title(o, h2);
1290		}
(gdb)

Which leads me to believe the problem is in the call to merge_trees() at
line 1343:

Breakpoint 6, merge_recursive (o=0x7fffffffd560, h1=0x793db8,
h2=0x793aa0, ca=0x0, result=0x7fffffffd500) at merge-recursive.c:1343
(gdb) list
1338	
1339		discard_cache();
1340		if (!o->call_depth)
1341			read_cache();
1342	
1343		clean = merge_trees(o, h1->tree, h2->tree,
merged_common_ancestors->tree,
1344				    &mrtree);
1345	
1346		if (o->call_depth) {
1347			*result = make_virtual_commit(mrtree, "merged tree");
(gdb)

In merge_trees(), mrtree is the argument **result.  It is at line 1255
that write_tree_from_memory nulls out the pointee of result:

Breakpoint 7, merge_trees (o=0x7fffffffd560, head=0x77be10,
merge=0x77b488, common=0x77c0b8, result=0x7fffffffd478) at
merge-recursive.c:1255
(gdb) p *result
$16 = (struct tree *) 0x7ffff732d0ac
(gdb) n
(gdb) p *result
$17 = (struct tree *) 0x0
(gdb) list
1252			clean = 1;
1253	
1254		if (o->call_depth)
1255			*result = write_tree_from_memory(o);
1256	
1257		return clean;
1258	}
1259	
1260	static struct commit_list *reverse_commit_list(struct commit_list
*list)
1261	{
(gdb)

Then in write_tree_from_memory() we find the offending return NULL at
line 210:

Breakpoint 8, write_tree_from_memory (o=0x7fffffffd560) at
merge-recursive.c:210
(gdb) list
205				struct cache_entry *ce = active_cache[i];
206				if (ce_stage(ce))
207					output(o, 0, "%d %.*s", ce_stage(ce),
208					       (int)ce_namelen(ce), ce->name);
209			}
210			return NULL;
211		}
212	
213		if (!active_cache_tree)
214			active_cache_tree = cache_tree();
(gdb)


Let me know if you need any more information.

Thanks,
Tim

Re: git-merge segfault in 1.6.6 and master

[Junio C Hamano]

Tim Olsen <tim@brooklynpenguin.com> writes:

> At the beginning of merge_recursive(), the local mrtree appears to be
> set to some globally defined mrtree which is not null:

No; that "assignment" is just to squelch warning from gcc.  mrtree at that
point is uninitialized.

> In merge_trees(), mrtree is the argument **result.  It is at line 1255
> that write_tree_from_memory nulls out the pointee of result:
> ...
> Then in write_tree_from_memory() we find the offending return NULL at
> line 210:
>
> Breakpoint 8, write_tree_from_memory (o=0x7fffffffd560) at
> merge-recursive.c:210
> (gdb) list
> 205				struct cache_entry *ce = active_cache[i];
> 206				if (ce_stage(ce))
> 207					output(o, 0, "%d %.*s", ce_stage(ce),
> 208					       (int)ce_namelen(ce), ce->name);
> 209			}
> 210			return NULL;
> 211		}
> 212	
> 213		if (!active_cache_tree)
> 214			active_cache_tree = cache_tree();
> (gdb)

Are you saying write_tree_from_memory() is returning NULL?  That probably
means that in the recursive (i.e. the step that first merges multiple
common ancestors into one) case the merge is getting conflicts.  Do you
see these "There are unmerged index entries" output?

In the recursive case (i.e. o->call_depth is non-zero), process_renames()
and process_entry() are supposed to be forcing the conflicts resolved,
recording the contents with conflict markers if necessary, before the
control gets to that point, so it clearly is a bug very specific to the
recursive merge implementation.

Re: git-merge segfault in 1.6.6 and master

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 1513 bytes --]

On Wed, Jan 20, 2010 at 04:57:19PM -0500, Tim Olsen <tim@brooklynpenguin.com> wrote:
> It appears that a segfault still happens with your patch applied, but
> this time it is caught:
> 
> tolsen@neurofunk:~/git/site-build-dav-sync-05 [git:build-dav-sync-05]$
> git merge origin/deployed
> error: merge-recursive died of signal 11
> Merge with strategy recursive failed.
> tolsen@neurofunk:~/git/site-build-dav-sync-05 [git:build-dav-sync-05]$
> 
> 
> > "common = NULL" means merged_common_ancestors->tree is NULL in the caller.
> > Somebody is passing a bogus commit in "ca" (aka common ancestors) list
> > when calling merge_recursive(), or forgetting to parse them before calling
> > it.  In your debugger could you find out where it comes from and what it
> > has before this call into merge_trees() is made?  Specifically, what the
> > "ca" list at 0x7b3c00 contains, and how "merged_common_ancestors" at
> > 0x121e360 looks like. in this trace we see below:
> 
> Here is the replay of the flow of execution from the first time we enter
> merge_recursive().  The repository has been modified slightly so the
> pointers are different this time but the segfault is still happening
> (I'll stop modifying the repository now ;-) .

Two ideas to help debugging:

- Can you try if this happens in a new repo as well? (If not, is the
  repo public?) If yes, can you write a script that shows your problem?
- Can you see if this happens with v1.6.0? If yes, can you bisect it?

Thanks.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: git-merge segfault in 1.6.6 and master

[Tim Olsen]

Junio C Hamano wrote:
> Tim Olsen <tim@brooklynpenguin.com> writes:
>> Breakpoint 8, write_tree_from_memory (o=0x7fffffffd560) at
>> merge-recursive.c:210
>> (gdb) list
>> 205				struct cache_entry *ce = active_cache[i];
>> 206				if (ce_stage(ce))
>> 207					output(o, 0, "%d %.*s", ce_stage(ce),
>> 208					       (int)ce_namelen(ce), ce->name);
>> 209			}
>> 210			return NULL;
>> 211		}
>> 212	
>> 213		if (!active_cache_tree)
>> 214			active_cache_tree = cache_tree();
>> (gdb)
> 
> Are you saying write_tree_from_memory() is returning NULL?  That probably
> means that in the recursive (i.e. the step that first merges multiple
> common ancestors into one) case the merge is getting conflicts.  Do you
> see these "There are unmerged index entries" output?

write_tree_from_memory() is returning NULL.  Stepping through the
execution in gdb shows it returning NULL at line 210.

I do not see any output, however:

$ git merge origin/deployed
Segmentation fault
$

> In the recursive case (i.e. o->call_depth is non-zero), process_renames()
> and process_entry() are supposed to be forcing the conflicts resolved,
> recording the contents with conflict markers if necessary, before the
> control gets to that point, so it clearly is a bug very specific to the
> recursive merge implementation.

Setting breakpoints on process_renames() and process_entry() shows that
they are being executed.  Is there anything I can gather from their
execution that would help you?

Tim

Re: git-merge segfault in 1.6.6 and master

[Junio C Hamano]

Tim Olsen <tim@brooklynpenguin.com> writes:

>> In the recursive case (i.e. o->call_depth is non-zero), process_renames()
>> and process_entry() are supposed to be forcing the conflicts resolved,
>> recording the contents with conflict markers if necessary, before the
>> control gets to that point, so it clearly is a bug very specific to the
>> recursive merge implementation.
>
> Setting breakpoints on process_renames() and process_entry() shows that
> they are being executed.  Is there anything I can gather from their
> execution that would help you?

When they are called with non-zero o->call_depth, they are supposed to
drop all the index entries that they handle down to stage #0 (even if the
path had contents level conflict).  For example, you see this bit in
process_entry():

	} else if (a_sha && b_sha) {
		/* Case C: Added in both (check for same permissions) and */
		/* case D: Modified in both, but differently. */
		const char *reason = "content";
		...
		mfi = merge_file(o, &one, &a, &b,
				 o->branch1, o->branch2);

		clean_merge = mfi.clean;
		if (!mfi.clean) {
			if (S_ISGITLINK(mfi.mode))
				reason = "submodule";
			output(o, 1, "CONFLICT (%s): Merge conflict in %s",
					reason, path);
		}
		update_file(o, mfi.clean, mfi.sha, mfi.mode, path);
	} ...

and update_file() eventually calls update_file_flags() to make sure that
the content in mfi.sha is at the stage #0 of path when o->call_depth is
non-zero (or mfi.clean is true).  process_renames() and process_entry()
are humongous functions that handle full of different cases, but all
codepaths must follow the rule not to leave non-stage #0 entries in the
index before merge_trees() function calls write_tree_from_memory().

We've fixed a similar bug in c94736a (merge-recursive: don't segfault
while handling rename clashes, 2009-07-30) and I think there were similar
breakages we fixed over time in the same area, but the two functions being
as huge as they are, I suspect you are hitting a codepath that hasn't been
fixed.

Re: git-merge segfault in 1.6.6 and master

[Tim Olsen]

Miklos Vajna wrote:
> Two ideas to help debugging:
> 
> - Can you try if this happens in a new repo as well? (If not, is the
>   repo public?) If yes, can you write a script that shows your problem?

The problem still happens in any clone of the repository, but I have not
attempted to reproduce the problem in a fresh repository.  I've put our
repository up at git://les.limebits.net/site (warning: the repo is about
 364MB).  The following 3 commands will reproduce the problem:

git clone git://les.limebits.net/site
cd site
git merge origin/deployed

The problem starts with commit 9079b71b6f.  I can merge its ancestors
with no problem into the default branch (build-dav-sync-05).  But commit
9079b71b6f and its descendents cause a segfault when merging into
build-dav-sync-05.

> - Can you see if this happens with v1.6.0? If yes, can you bisect it?

With 1.6.0, the merge still fails but it doesn't outright segfault.

$ git merge origin/deployed
Merge with strategy recursive failed.
$

The output appears to be from line 1098 of builtin-merge.c.  Bisecting
finds that the outright segfaulting starts with commit 18668f53:

tolsen@neurofunk:~/git/git [git:NO BRANCH*]$ git bisect good
18668f5319b079cce29e19817bc352b1413e0908 is first bad commit
commit 18668f5319b079cce29e19817bc352b1413e0908
Author: Miklos Vajna <vmiklos@frugalware.org>
Date:   Thu Aug 28 15:43:00 2008 +0200

    builtin-merge: avoid run_command_v_opt() for recursive and subtree

    The try_merge_strategy() function always ran the strategy in a separate
    process, though this is not always necessary. The recursive and subtree
    strategy can be called without a fork(). This patch adds a check, and
    calls recursive in the same process without wasting resources.

    Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
    Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
    Signed-off-by: Junio C Hamano <gitster@pobox.com>

:100644 100644 9ad9791068c9330f28413ac67315246989c8d96d
b857cf6246978846e0c19895fd6f66266cf6a6f4 M      builtin-merge.c
tolsen@neurofunk:~/git/git [git:NO BRANCH*]$

This leads me to believe the segfault may still be occurring in v1.6.0,
but in a separate process.

Tim

> 
> Thanks.

Re: git-merge segfault in 1.6.6 and master

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> When they are called with non-zero o->call_depth, they are supposed to
> drop all the index entries that they handle down to stage #0 (even if the
> path had contents level conflict).  For example, you see this bit in
> process_entry():
>
> 	} else if (a_sha && b_sha) {
> 		/* Case C: Added in both (check for same permissions) and */
> 		/* case D: Modified in both, but differently. */
> 		const char *reason = "content";
> 		...
> 		mfi = merge_file(o, &one, &a, &b,
> 				 o->branch1, o->branch2);
>
> 		clean_merge = mfi.clean;
> 		if (!mfi.clean) {
> 			if (S_ISGITLINK(mfi.mode))
> 				reason = "submodule";
> 			output(o, 1, "CONFLICT (%s): Merge conflict in %s",
> 					reason, path);
> 		}
> 		update_file(o, mfi.clean, mfi.sha, mfi.mode, path);
> 	} ...
>
> and update_file() eventually calls update_file_flags() to make sure that
> the content in mfi.sha is at the stage #0 of path when o->call_depth is
> non-zero (or mfi.clean is true).  process_renames() and process_entry()
> are humongous functions that handle full of different cases, but all
> codepaths must follow the rule not to leave non-stage #0 entries in the
> index before merge_trees() function calls write_tree_from_memory().
>
> We've fixed a similar bug in c94736a (merge-recursive: don't segfault
> while handling rename clashes, 2009-07-30) and I think there were similar
> breakages we fixed over time in the same area, but the two functions being
> as huge as they are, I suspect you are hitting a codepath that hasn't been
> fixed.

And there are.

For example, this (drop it as t9999-junk.sh in t/ directory, go there and
run "sh ./t-9999-junk.sh -v") shows one codepath that makes merge-recursive
fail to resolve the "common ancestor" merge.

-- -- store in t/t9999-junk.sh and run -- --
#!/bin/sh

test_description='common ancestor merge corner cases'

. ./test-lib.sh

test_expect_success 'setup' '
	mkdir D &&
	echo 1 >D/F1 &&
	echo 2 >D/F2 &&
	echo 3 >D/F3 &&
	echo 4 >D/F4 &&
	echo 5 >D/F5 &&
	echo 6 >D/F6 &&

	git add D &&
	test_tick &&
	git commit -m initial &&
	git branch side &&

	git checkout master &&
	git mv D/F1 D/M1 &&
	git rm D/F2 &&
	echo 7 >>D/F3 &&
	git mv D/F4 D/M4 &&
	git rm D/F5 &&
	mkdir D/F5 &&
	git mv D/F6 D/F5/M6 &&
	git add -u &&
	test_tick &&
	git commit -m master &&
	git tag A &&

	git checkout side &&
	git mv D/F1 D/S1 && # rename-rename conflict (dst)
	echo 8 >>D/F2 && # remove-modify conflict
	git mv D/F5 D/M4 && # rename-rename conflict (src)
	git add -u &&
	test_tick &&
	git commit -m side &&
	git tag B &&

	git checkout side &&
	test_tick &&
	git merge -s ours master &&
	git tag C &&

	git checkout master &&
	test_tick &&
	git merge -s ours B &&
	git tag D
'

test_expect_success 'criss-cross' '
	git checkout D &&
	test_must_fail git merge side
'

test_done
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

It dies after showing this (D/F5/M6 is left unresolved in the forced
"common ancestor" merge):

  Merging:
  f2f2f75 master
  7994826 side
  found 1 common ancestor(s):
  f561e36 initial
  CONFLICT (rename/rename): Rename "D/F1"->"D/M1" in branch "Temporary merge branch 1" rename "D/F1"->"D/S1" in "Temporary merge branch 2" (left unresolved)
  CONFLICT (rename/add): Rename D/F4->D/M4 in Temporary merge branch 1. D/M4 added in Temporary merge branch 2
  Adding merged D/M4
  Skipped D/M4 (merged same as existing)
  CONFLICT (rename/delete): Rename D/F5->D/M4 in Temporary merge branch 2 and deleted in Temporary merge branch 1
  Skipped D/F5/M6 (merged same as existing)
  CONFLICT (delete/modify): D/F2 deleted in Temporary merge branch 1 and modified in Temporary merge branch 2. Version Temporary merge branch 2 of D/F2 left in tree.
  There are unmerged index entries:
  2 D/F5/M6


The attached patch changes the behaviour to make this 9999-junk test pass,
but then it breaks t6036 (iow, the attached is _not_ a fix).

After I stared at the code for more than two hours, I gave up trying to
diagnose this by myself.  People more familiar with the merge-recursive
implementation might be able to help figuring this out and may prove my
suspicion wrong, but I have a feeling that without a fairly big rewrite
the code is unsalvageable.

-- >8 --
Not a fix

diff --git a/merge-recursive.c b/merge-recursive.c
index 1239647..132a6fc 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1052,8 +1052,8 @@ static int process_renames(struct merge_options *o,
 							update_stages(ren1_dst,
 								      one, a, b, 1);
 					}
-					update_file(o, mfi.clean, mfi.sha, mfi.mode, ren1_dst);
 				}
+				update_file(o, mfi.clean, mfi.sha, mfi.mode, ren1_dst);
 			}
 		}
 	}

Re: git-merge segfault in 1.6.6 and master

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> After I stared at the code for more than two hours, I gave up trying to
> diagnose this by myself.  People more familiar with the merge-recursive
> implementation might be able to help figuring this out and may prove my
> suspicion wrong, but I have a feeling that without a fairly big rewrite
> the code is unsalvageable.

In the meantime, I think applying this patch is the right thing to do.

-- >8 --
Subject: merge-recursive: do not return NULL only to cause segfault

merge-recursive calls write_tree_from_memory() to come up with a virtual
tree, with possible conflict markers inside the blob contents, while
merging multiple common ancestors down.  It is a bug to call the function
with unmerged entries in the index, even if the merge to come up with the
common ancestor resulted in conflicts.  Otherwise the result won't be
expressible as a tree object.

We _might_ want to suggest the user to set GIT_MERGE_VERBOSITY to 5 and
re-run the merge in the message.  At least we will know which part of
process_renames() or process_entry() functions is not correctly handling
the unmerged paths, and it might help us diagnosing the issue.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 merge-recursive.c |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 1239647..cb53b01 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -202,14 +202,14 @@ struct tree *write_tree_from_memory(struct merge_options *o)
 
 	if (unmerged_cache()) {
 		int i;
-		output(o, 0, "There are unmerged index entries:");
+		fprintf(stderr, "BUG: There are unmerged index entries:\n");
 		for (i = 0; i < active_nr; i++) {
 			struct cache_entry *ce = active_cache[i];
 			if (ce_stage(ce))
-				output(o, 0, "%d %.*s", ce_stage(ce),
-				       (int)ce_namelen(ce), ce->name);
+				fprintf(stderr, "BUG: %d %.*s", ce_stage(ce),
+					(int)ce_namelen(ce), ce->name);
 		}
-		return NULL;
+		die("Bug in merge-recursive.c");
 	}
 
 	if (!active_cache_tree)