[BUG] - git-read-tree segfaults

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

Hi,

On Tue, 10 Mar 2009, Jiri Olsa wrote:

I can reproduce with the script, too...

Working on it, Dscho

Hi,

On Tue, 10 Mar 2009, Jiri Olsa wrote:

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

On Tue, Mar 10, 2009 at 9:21 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

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

Hi,

On Wed, 11 Mar 2009, Jiri Olsa wrote:

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.

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

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

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

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

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.

"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(-)

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

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

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

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*

On Thu, 12 Mar 2009, Daniel Barkalow wrote:

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:

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

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

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