patchDon't dereference NULL upon lookup_tree failure.

While Matthew Farrellee was working on converting the Condor repository from cvs to git, he managed to make git segfault (with help from parsecvs) while producing a 100MB .git repository. He found the single offending ,v file that led parsecvs to generate a bogus repository, and deduced that adding a single well-placed branch tag[*] was enough to avoid the problem. I fixed the bug in git along with a few in parsecvs that were exposed while paring the ,v file down from a 150KB monstrosity to something manageable.

[*] Adding this tag avoids the problem: FOO:1.30.2.5.0.8

First, here's how to reproduce the git segfault, using the file, "min,v" included below. Run this in an empty directory:

  rm -rf k .git .git-cvs
  parsecvs min,v >& log
  git clone -q . k

I noticed that while I get a segfault both on x86 and x86_64, I see clear evidence of it only on x86:

  0 blocks
  error: Object 0d57588da39d10795486bd5451bc2660832228e6 is a commit, not a tree
  Segmentation fault
  fatal: The remote end hung up unexpectedly
  [Exit 1]

When running on an x86_64 system (either debian unstable or rawhide) I see only this:

  0 blocks
  error: Object 0d57588da39d10795486bd5451bc2660832228e6 is a commit, not a tree
  fatal: The remote end hung up unexpectedly

Of course, valgrind shows you the segfault in both cases.

The above was using git version 1.5.4.rc1.3.gec692 and the latest parsecvs from here: git://people.freedesktop.org/~keithp/parsecvs

    commit 2b0113ffb0055620193397c025d6f6bca3b110cd
    Author: Finn Arne Gangstad <finnag@pvv.org>
    Date:   Sun Nov 18 15:26:35 2007 -0800

This patch avoids the NULL dereference by treating a failed lookup_tree the same way an invalid "type" is handled in the "else" block just below. The only difference is that for a failed lookup_tree, the failing function has already produced a diagnostic.

-----------------------------------------------------
From 4cd649160d8174b23727b3d7276f1bd7246d0aff Mon Sep 17 00:00:00 2001
From: Jim Meyering <meyering@redhat.com>
Date: Fri, 21 Dec 2007 11:56:32 +0100
Subject: [PATCH] Don't dereference NULL upon lookup_tree failure.

Signed-off-by: Jim Meyering <meyering@redhat.com>
---
 object.c |   12 ++++++++----
 1 files changed, 8 insertions(+), 4 deletions(-)

Jim Meyering <jim@meyering.net> writes:

While this change may be a prudent safeguard, there is something else going on. Can you provide the callchain that led to the parse_object_buffer() that gave SHA1 of a commit object with type set to OBJ_TREE? Which caller does that bogus combination?

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

Sure. Here's valgrind output from running this (from my reproducer):

    valgrind --trace-children=yes git clone . k
---------------
  error: Object 0d57588da39d10795486bd5451bc2660832228e6 is a commit, not a tree
  ==9483== Invalid read of size 1
  ==9483==    at 0x405C27: parse_object_buffer (object.c:146)
  ==9483==    by 0x405CE4: parse_object (object.c:187)
  ==9483==    by 0x403185: send_ref (upload-pack.c:561)
  ==9483==    by 0x408EEF: do_for_each_ref (refs.c:546)
  ==9483==    by 0x4036EC: main (upload-pack.c:587)
  ==9483==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
  ==9483==
  ==9483== Process terminating with default action of signal 11 (SIGSEGV)
  ==9483==  Access not within mapped region at address 0x0
  ==9483==    at 0x405C27: parse_object_buffer (object.c:146)
  ==9483==    by 0x405CE4: parse_object (object.c:187)
  ==9483==    by 0x403185: send_ref (upload-pack.c:561)
  ==9483==    by 0x408EEF: do_for_each_ref (refs.c:546)
  ==9483==    by 0x4036EC: main (upload-pack.c:587)
  ...
  fatal: The remote end hung up unexpectedly

Jim Meyering <jim@meyering.net> writes:

Sorry, I asked for a wrong thing. parse_object() reads and finds out the type, so type there is presumably the right type of the object (which is OBJ_TREE). Then parse_object_buffer() checks if it has already seen the object of the same SHA-1 and finds that somebody had earlier told that SHA-1 name is of a commit object. Either you found a SHA-1 collision (highly unlikely) or the earlier caller had lied. And I think what really needs to be fixed is that lying caller. That is not in the above call chain.

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

I haven't debugged it enough to find/fix the bug in parsecvs.

I presume that parsecvs is the culprit, in constructing an invalid repository -- especially, since inserting the single missing tag into the ,v file is enough to make it so parsecvs creates a repository that no longer triggers the git bug.

Jim Meyering <jim@meyering.net> writes:

Independent of who creates a "invalid repository", our tools should be prepared to be fed bad data and not get upset. Somebody in our code read a non-commit (or it did not read anything) and told the object layer it is a commit. That codepath needs to be tightened up, no?

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

Yes, of course. Unfortunately, I won't have time to investigate for a while.

Jim Meyering <jim@meyering.net> writes:

Although I haven't seen the problematic repository, I think what is going on is that the repository has objects with pointers to other objects labelled with wrong types.

For example, a tag can tag any type of object.

    $ git cat-file tag v1.5.4-rc1
    object 74f6b03c5c8fceef416de9f9a18e5d64712b6d96
    type commit
    tag v1.5.4-rc1
    tagger Junio C Hamano <gitster@pobox.com> 1198114975 -0800

    GIT 1.5.4-rc1
    ...

When parsing such a tag object, it instantiates an in-core tag object that has a pointer to an in-core commit object, because the tag says that it points at commit 74f6b0, without reading the tagged object itself. This is to allow the user of that in-core tag object to ask "what do you point at" and get an in-core object that represents the pointee. If (and only if) the user choose to follow that pointer and look at the contents of the pointee, it can then call parse_object() on that in-core object. In other words, the object layer is designed to work lazily.

So if you earlier parsed such a tag but if the object 74f6b0 were an object of different type, we would hit the codepath you identified that leads to a NULL dereference. And "lying caller" cannot really do much better (except perhaps actually validating the presense and the type of the object, which would incur additional overhead). The situation is the same if:

 - a tree object records an entry with: 
   - mode bits 040000 pointing at an object that is not a tree; or
   - mode bits 100(644|755) pointing at an object that is not a blob; or
   - mode bits 160000 pointing at an object that is not a commit; or
 - a commit object has a "parent" line that is not a commit; or
 - a commit object has a "tree" line that is not a tree.

Also we cannot just say "then we would take safety over overhead" and make the lying callers validate the pointee; subproject commits pointed by gitlinks (i.e. entry with 160000 mode bits in a tree object) are not even required to be available.

Your fix is all we can sensibly do. I however think you would need similar fix to the same function for other object types, as they dereference a potentially NULL pointer the same way.

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

Good point. Patch below. I wondered if these lookup functions have always been able to return NULL, since there are many remaining uses where the possibility of a NULL return value is not handled. Here are a few that stood out in the output of a quick search:

  git-grep -E -A3 'lookup_(commit|tag|blob|tree) *\('

Note: I did not look at cases where the return value is an argument
to some other function.

------------------
builtin-fmt-merge-msg.c:
		head = lookup_commit(head_sha1);
		...
		for (i = 0; i < origins.nr; i++)
			shortlog(origins.list[i], origins.payload[i],
					head, &rev, limit);
------------------
builtin-read-tree.c:                    struct tree *subtree = lookup_tree(entry.
sha1);
builtin-read-tree.c-                    if (!subtree->object.parsed)

------------------ combine-diff.c: struct commit *commit = lookup_commit(sha1); combine-diff.c- struct commit_list *parents;

------------------ http-push.c: struct commit *head = lookup_commit(head_sha1); http-push.c: struct commit *branch = lookup_commit(branch_sha1); http-push.c- struct commit_list *merge_bases = get_merge_bases(head, branch, 1);

------------------ reachable.c: struct tree *tree = lookup_tree(sha1); reachable.c- add_pending_object(revs, &tree->object, "");

------------------ tag.c: item->tagged = &lookup_blob(sha1)->object; tag.c- } else if (!strcmp(type, tree_type)) { tag.c: item->tagged = &lookup_tree(sha1)->object; tag.c- } else if (!strcmp(type, commit_type)) { tag.c: item->tagged = &lookup_commit(sha1)->object; tag.c- } else if (!strcmp(type, tag_type)) { tag.c: item->tagged = &lookup_tag(sha1)->object; tag.c- } else {

-------------------------- unpack-trees.c: struct tree *tree = lookup_tree(posns[i]->sha1); ... unpack-trees.c- parse_tree(tree);

Here's the revised patch:

==================================================================
From 94152217e8e57d3932b4ba6f7ee014da1f4346d3 Mon Sep 17 00:00:00 2001
From: Jim Meyering <meyering@redhat.com>
Date: Fri, 21 Dec 2007 11:56:32 +0100
Subject: [PATCH] Don't dereference NULL upon lookup failure.

Signed-off-by: Jim Meyering <meyering@redhat.com>
---
 object.c |   42 +++++++++++++++++++++++++++++-------------
 1 files changed, 29 insertions(+), 13 deletions(-)

Thanks.