[BUG] - git-read-tree segfaults

[BUG] - git-read-tree segfaults

[Jiri Olsa]

Hi,

I was following the git core tutorial and git-read-tree got me segfault.
I accidentaly executed the git-read-tree without "-m -u" options and
got segfault.

I can reproduce with the latest git using following script.

-----------------------------------------------
#!/bin/sh

GIT=$1

rm -rf crash; mkdir -p crash; cd crash
$GIT init
echo "xxx" > xxx
$GIT add xxx
$GIT commit -m "xxx"
$GIT checkout -b yyy
echo "yyy" > yyy
$GIT add yyy
$GIT commit -m "yyy"
echo "yyy1" >> yyy
$GIT commit -a -m "yyy1"
$GIT checkout master
echo "xxx1" >> xxx
$GIT commit -a -m "xxx1"
mb=$($GIT merge-base HEAD yyy)
$GIT read-tree $mb HEAD yyy
-----------------------------------------------

regards,
jirka

Re: [BUG] - git-read-tree segfaults

[Johannes Schindelin]

Hi,

On Tue, 10 Mar 2009, Jiri Olsa wrote:

> Hi,
> 
> I was following the git core tutorial and git-read-tree got me segfault.
> I accidentaly executed the git-read-tree without "-m -u" options and
> got segfault.
> 
> I can reproduce with the latest git using following script.

I can reproduce with the script, too...

Working on it,
Dscho

Re: [BUG] - git-read-tree segfaults

[Johannes Schindelin]

Hi,

On Tue, 10 Mar 2009, Jiri Olsa wrote:

> mb=$($GIT merge-base HEAD yyy)
> $GIT read-tree $mb HEAD yyy

While I agree that it is a bad thing for Git to segfault, I think this 
here is a pilot error.  You try to read 3 trees at the same time, but not 
perform a merge.  IMHO you want to add -m at least.

Ciao,
Dscho

Re: [BUG] - git-read-tree segfaults

[Jiri Olsa]

On Tue, Mar 10, 2009 at 9:21 PM, Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
> Hi,
>
> On Tue, 10 Mar 2009, Jiri Olsa wrote:
>
>> mb=$($GIT merge-base HEAD yyy)
>> $GIT read-tree $mb HEAD yyy
>
> While I agree that it is a bad thing for Git to segfault, I think this
> here is a pilot error.  You try to read 3 trees at the same time, but not
> perform a merge.  IMHO you want to add -m at least.

agreed, I've already said I executed it like this by an accident...
it was easy to recreate so I shared... I'm not saying it is a show stopper :)

jirka

>
> Ciao,
> Dscho
>
>

Re: [BUG] - git-read-tree segfaults

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1603 bytes --]

Hi,

On Wed, 11 Mar 2009, Jiri Olsa wrote:

> On Tue, Mar 10, 2009 at 9:21 PM, Johannes Schindelin
> <Johannes.Schindelin@gmx.de> wrote:
>
> > On Tue, 10 Mar 2009, Jiri Olsa wrote:
> >
> >> mb=$($GIT merge-base HEAD yyy)
> >> $GIT read-tree $mb HEAD yyy
> >
> > While I agree that it is a bad thing for Git to segfault, I think this 
> > here is a pilot error.  You try to read 3 trees at the same time, but 
> > not perform a merge.  IMHO you want to add -m at least.
> 
> agreed, I've already said I executed it like this by an accident...

Hey, you did the right thing!  And you even provided a script to recreate, 
so that it was really easy to see what is happening.

> it was easy to recreate so I shared... I'm not saying it is a show 
> stopper :)

Well, Git should not crash.  But read-tree is real low-level, so I am 
torn.  OTOH, something like this may be the correct thing to do:

-- snipsnap --
Subject: [PATCH] Make read-tree with multiple trees imply -m

Noticed by Jiri Olsa.

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

---

 builtin-read-tree.c |    5 +++++
 1 files changed, 5 insertions(+), 0 deletions(-)

diff --git a/builtin-read-tree.c b/builtin-read-tree.c
index 8e02738..547ac25 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -221,6 +221,11 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)
 			opts.head_idx = 1;
 	}
 
+	if (nr_trees > 1 && !o->merge) {
+		warning("Assuming -m with multiple trees");
+		o->merge = 1;
+	}
+
 	for (i = 0; i < nr_trees; i++) {
 		struct tree *tree = trees[i];
 		parse_tree(tree);

Re: [BUG] - git-read-tree segfaults

[Junio C Hamano]

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

> On Wed, 11 Mar 2009, Jiri Olsa wrote:
>
>> On Tue, Mar 10, 2009 at 9:21 PM, Johannes Schindelin
>> <Johannes.Schindelin@gmx.de> wrote:
>>
>> > On Tue, 10 Mar 2009, Jiri Olsa wrote:
>> >
>> >> mb=$($GIT merge-base HEAD yyy)
>> >> $GIT read-tree $mb HEAD yyy
>> >
>> > While I agree that it is a bad thing for Git to segfault, I think this 
>> > here is a pilot error.  You try to read 3 trees at the same time, but 
>> > not perform a merge.  IMHO you want to add -m at least.
>> 
>> agreed, I've already said I executed it like this by an accident...
>
> Hey, you did the right thing!  And you even provided a script to recreate, 
> so that it was really easy to see what is happening.
>
>> it was easy to recreate so I shared... I'm not saying it is a show 
>> stopper :)
>
> Well, Git should not crash.  But read-tree is real low-level, so I am 
> torn.  OTOH, something like this may be the correct thing to do:

That's a bogus "fix".

"git read-tree" without "-m" is supposed to behave as an overlay of the
given trees.  Try it with any git older than 1.5.5 and you should see one
entry for xxx and yyy each from Jiri's example.  Somewhere between 1.5.4
and 1.5.5 we seem to have broken it.

Having said that, I do not think "read-tree A B C" to overlay these trees
has never worked reliably.  For one thing, I do not think the code never
tried to avoid D/F conflicts in the index, and because of that, you can
end up with a bogus index that looks like this:

	$ git ls-files -s
        100644 58b2ca10b6b032c114cb934c012c3743e34e0e7a 0	xxx
        100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 0	xxx/zzz
        100644 363a9e8d3b0b423eab41fd12ebed489004ab3c2e 0	yyy

and trying to write it out as a tree object will produce an even more
bogus result.

I think the attached patch fixes the segfault, and also fixes the
longstanding lack of D/F conflict detection, but it needs a bit of
commentary.

The first hunk fixes the D/F conflict issue.  After reading three trees
that has (xxx), (xxx, yyy) and (xxx/zzz, yyy) in this order, the resulting
index should look like this with this patch, instead of the broken index
depicted above:

	$ git ls-files -s
        100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 0	xxx/zzz
        100644 363a9e8d3b0b423eab41fd12ebed489004ab3c2e 0	yyy

I suspect that the reason add_entry() passed SKIP_DFCHECK was to work
around an old bug in add_index_entry() that considered it a D/F conflict
if you have a file D at stage N and a file D/F at stage M when N and M are
different.  I think such a bug has been fixed long time ago, and there is
no reason for such a workaround.  Besides, OK_TO_REPLACE only makes sense
when you do check D/F conflict ("replace" in the name of the flag means
"If you want to add 'xxx/zzz' when the index has 'xxx', it is Ok to drop
the existing 'xxx' in order to add your 'xxx/zzz''); it makes no sense to
give it if you are giving SKIP_DFCHECK at the same time.

The second hunk removes a noop increment of n with o->merge (at this point
we know o->merge is zero) and then makes sure we only send an existing
entry taken from the tree to add_entry().

A NULL src[i] entry is obviously a missing entry from i-th tree, and an
entry that is o->df_conflict_entry is just a stand-in phantom entry the
unpack machinery uses when i-th tree has "xxx/zzz" (hence it cannot have
"xxx") and the unpacker is looking at path "xxx".  In either case, i-th
tree does not have an entry "xxx" and we should skip add_entry() for
such a src[i].

 unpack-trees.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index e547282..5820ce4 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -49,7 +49,7 @@ static void add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
 	memcpy(new, ce, size);
 	new->next = NULL;
 	new->ce_flags = (new->ce_flags & ~clear) | set;
-	add_index_entry(&o->result, new, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE|ADD_CACHE_SKIP_DFCHECK);
+	add_index_entry(&o->result, new, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);
 }
 
 /* Unlink the last component and attempt to remove leading
@@ -286,9 +286,9 @@ static int unpack_nondirectories(int n, unsigned long mask,
 	if (o->merge)
 		return call_unpack_fn(src, o);
 
-	n += o->merge;
 	for (i = 0; i < n; i++)
-		add_entry(o, src[i], 0, 0);
+		if (src[i] && src[i] != o->df_conflict_entry)
+			add_entry(o, src[i], 0, 0);
 	return 0;
 }
 

Re: [BUG] - git-read-tree segfaults

[Junio C Hamano]

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

> I suspect that the reason add_entry() passed SKIP_DFCHECK was to work
> around an old bug in add_index_entry() that considered it a D/F conflict
> if you have a file D at stage N and a file D/F at stage M when N and M are
> different.  I think such a bug has been fixed long time ago, and there is
> no reason for such a workaround.  Besides, OK_TO_REPLACE only makes sense
> when you do check D/F conflict ("replace" in the name of the flag means
> "If you want to add 'xxx/zzz' when the index has 'xxx', it is Ok to drop
> the existing 'xxx' in order to add your 'xxx/zzz''); it makes no sense to
> give it if you are giving SKIP_DFCHECK at the same time.

The ancient D/F conflict detection bug in add_cache_entry() I had in mind
was fixed by b155725 ([PATCH] Fix oversimplified optimization for
add_cache_entry()., 2005-06-25).  The use of SKIP_DFCHECK turns out to
have nothing to do with working that ancient bug around.

The real culprit seems to be 34110cd (Make 'unpack_trees()' have a
separate source and destination index, 2008-03-06).

Before that commit:

 * merge_entry() that records the final tree-level 3-way merge decision
   used to pass OK_TO_REPLACE without SKIP_DFCHECK.

 * unpack_nondirectories() codepath for non-merge multi-tree read-tree
   (the one under discussion in this thread) used to pass SKIP_DFCHECK but
   did not pass OK_TO_REPLACE.

The fact that even merge_entry() side passes SKIP_DFCHECK these days does
not appear to be a workaround for an old bug in D/F conflict detection
code after all; it simply is a bug in the refactoring done with the said
commit.

The unpack_nondirectories() codepath passed SKIP_DFCHECK from ee6566e
(Rewrite read-tree, 2005-09-05), which is the very original implementation
of the modern "read-tree A B C" code.  The ancient bug in the D/F conflict
detection code was killed way before that commit, and SKIP_DFCHECK in the
commit is not a workaround either; it also simply is a bug.

	Side note: I was somewhat surprised that "make test" of that old
	commit dates from September 2005 runs _much_ faster than the test
	suite we have these days.

The only sane use of SKIP_DFCHECK is when the caller knows the addition is
not introducing D/F conflict in the index to avoid the overhead.

[PATCH] read-tree A B C: do not create a bogus index and do not segfault

[Junio C Hamano]

"git read-tree A B C..." without the "-m" (merge) option is a way to read
these trees on top of each other to get an overlay of them.

An ancient commit ee6566e (Rewrite read-tree, 2005-09-05) passed the
ADD_CACHE_SKIP_DFCHECK flag when calling add_index_entry() to add the
paths obtained from these trees to the index, but it is an incorrect use
of the flag.  The flag is meant to be used by callers who know the
addition of the entry does not introduce a D/F conflict to the index in
order to avoid the overhead of checking.

This bug resulted in a bogus index that records both "x" and "x/z" as a
blob after reading three trees that have paths ("x"), ("x", "y"), and
("x/z", "y") respectively.  34110cd (Make 'unpack_trees()' have a separate
source and destination index, 2008-03-06) refactored the callsites of
add_index_entry() incorrectly and added more codepaths that use this flag
when it shouldn't be used.

Also, 0190457 (Move 'unpack_trees()' over to 'traverse_trees()' interface,
2008-03-05) introduced a bug to call add_index_entry() for the tree that
does not have the path in it, passing NULL as a cache entry.  This caused
reading multiple trees, one of which has path "x" but another doesn't, to
segfault.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 * I suspect that we can probably remove SKIP_DFCHECK option by fixing
   tree.c::read_tree(); the only caller the big comment at the beginning
   of it talks about is overlay_tree_on_cache() in builtin-ls-files.c and
   we haven't gained any new callers of the function.

   It is a bit sad that a very good looking refactoring and rewriting
   patch introduced this kind of regression that has gone unnoticed for a
   long time.  I managed to point three fingers and they turn out to be
   all ancient commits before v1.5.5.

 unpack-trees.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index cba0aca..5b0a8c1 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -49,7 +49,7 @@ static void add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
 	memcpy(new, ce, size);
 	new->next = NULL;
 	new->ce_flags = (new->ce_flags & ~clear) | set;
-	add_index_entry(&o->result, new, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE|ADD_CACHE_SKIP_DFCHECK);
+	add_index_entry(&o->result, new, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);
 }
 
 /* Unlink the last component and attempt to remove leading
@@ -283,9 +283,9 @@ static int unpack_nondirectories(int n, unsigned long mask, unsigned long dirmas
 	if (o->merge)
 		return call_unpack_fn(src, o);
 
-	n += o->merge;
 	for (i = 0; i < n; i++)
-		add_entry(o, src[i], 0, 0);
+		if (src[i] && src[i] != o->df_conflict_entry)
+			add_entry(o, src[i], 0, 0);
 	return 0;
 }
 
-- 
1.6.2.249.g770a0

Re: [PATCH] read-tree A B C: do not create a bogus index and do not segfault

[Daniel Barkalow]

On Thu, 12 Mar 2009, Junio C Hamano wrote:

> "git read-tree A B C..." without the "-m" (merge) option is a way to read
> these trees on top of each other to get an overlay of them.
> 
> An ancient commit ee6566e (Rewrite read-tree, 2005-09-05) passed the
> ADD_CACHE_SKIP_DFCHECK flag when calling add_index_entry() to add the
> paths obtained from these trees to the index, but it is an incorrect use
> of the flag.  The flag is meant to be used by callers who know the
> addition of the entry does not introduce a D/F conflict to the index in
> order to avoid the overhead of checking.

I think that this implementation actually thought it knew that the entry 
couldn't cause a D/F conflict. (Of course, it turned out 2.5 years later 
that it was wrong, on account of missing an implication of the way the 
index is sorted.)

> This bug resulted in a bogus index that records both "x" and "x/z" as a
> blob after reading three trees that have paths ("x"), ("x", "y"), and
> ("x/z", "y") respectively.  34110cd (Make 'unpack_trees()' have a separate
> source and destination index, 2008-03-06) refactored the callsites of
> add_index_entry() incorrectly and added more codepaths that use this flag
> when it shouldn't be used.
>
> Also, 0190457 (Move 'unpack_trees()' over to 'traverse_trees()' interface,
> 2008-03-05) introduced a bug to call add_index_entry() for the tree that
> does not have the path in it, passing NULL as a cache entry.  This caused
> reading multiple trees, one of which has path "x" but another doesn't, to
> segfault.

I think one of the later refactorings may have given up on seeing 
conflicts while reading trees, but didn't drop the flag (perhaps because 
Linus knew at the time that my assumption that conflicts would actually 
have been recognized was false, and didn't realize that it was also the 
source of the flag).

> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> ---
>  * I suspect that we can probably remove SKIP_DFCHECK option by fixing
>    tree.c::read_tree(); the only caller the big comment at the beginning
>    of it talks about is overlay_tree_on_cache() in builtin-ls-files.c and
>    we haven't gained any new callers of the function.
> 
>    It is a bit sad that a very good looking refactoring and rewriting
>    patch introduced this kind of regression that has gone unnoticed for a
>    long time.  I managed to point three fingers and they turn out to be
>    all ancient commits before v1.5.5.

I'm not too surprised that "read-tree" with multiple trees without -m 
doesn't actually work, because I don't think this has ever been useful for 
anything, and nobody's been able to come up with an implementation 
of read-tree that's particularly easy to understand. So regular testing 
wouldn't find this problem, and inspection wouldn't find it, either.

I think it might be a good idea to take this as evidence that nobody is 
using read-tree with multiple trees without merge, and just disallow it. 
If it takes a year to hit a pretty big bug in a code path, and using the 
code path was due to a typo anyway, it's unlikely that the code path is 
actually used for anything.

	-Daniel
*This .sig left intentionally blank*

Re: [PATCH] read-tree A B C: do not create a bogus index and do not segfault

[Linus Torvalds]

On Thu, 12 Mar 2009, Daniel Barkalow wrote:
> 
> I think one of the later refactorings may have given up on seeing 
> conflicts while reading trees, but didn't drop the flag (perhaps because 
> Linus knew at the time that my assumption that conflicts would actually 
> have been recognized was false, and didn't realize that it was also the 
> source of the flag).

That is very thoughtful of you, but I suspect the real reason was a much 
simpler one: redoing the read-tree logic was a huge pain in the posterior, 
and my primary goal at the time was to make the code more readable while 
passing all the tests.

So while I tried to make patches minimal (which may well explain why the 
flag remained), it wasn't the main goal, and trying to sort out the 
read-tree logic into something more understandable was quite test-driven.

So I think the big issue to take away from this is that I think this is 
such an odd case that if we want to support it, it would need explicit 
tests. Or:

> I think it might be a good idea to take this as evidence that nobody is 
> using read-tree with multiple trees without merge, and just disallow it. 

Hmm. It _has_ been used. It's been useful for really odd things 
historically, namely trying to merge different trees by hand. So while I 
agree that we could probably remove it, it _is_ a very interesting 
feature in theory, and since we have the code.. 

So I'd say "add a few tests for the known horrible cases" should be the 
first approach. If it ever actually breaks again and becomes a big 
maintenance headache, maybe _then_ remove the feature as not being worth 
the pain?

			Linus

Re: [PATCH] read-tree A B C: do not create a bogus index and do not segfault

[Junio C Hamano]

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

> On Thu, 12 Mar 2009, Daniel Barkalow wrote:
>
>> I think it might be a good idea to take this as evidence that nobody is 
>> using read-tree with multiple trees without merge, and just disallow it. 
>
> Hmm. It _has_ been used. It's been useful for really odd things 
> historically, namely trying to merge different trees by hand. So while I 
> agree that we could probably remove it, it _is_ a very interesting 
> feature in theory, and since we have the code.. 
>
> So I'd say "add a few tests for the known horrible cases" should be the 
> first approach. If it ever actually breaks again and becomes a big 
> maintenance headache, maybe _then_ remove the feature as not being worth 
> the pain?

I've added trivial tests and will start cooking it by letting it go
through the usual pu/next/master/maint cycle.

I think you are thinking about something like the "gitk" merge (aka "The
coolest merge EVER!" [*1*]), but you can do the same thing more safely
with -m option, giving an empty tree as the common ancestor.  Especially
if you run it in the aggressive mode, "addition" from our tree and their
tree, when it is an overlay, will not overlap, and will all cleanly
resolve to stage #0.

I suspect you can also use a single tree "read-tree", immediately followed
by another "read-tree --prefix=''" to read in two trees into the index and
write the results out.

[Footnote]

*1* http://article.gmane.org/gmane.comp.version-control.git/5126