Bug in fetch-pack.c, please confirm

Hi guys,

So I was looking at fetch-pack.c (from master @ 52cae643, but I think it's the same everywhere):

# Lines 626-648

     for (retval = 1, ref = *refs; ref ; ref = ref->next) {
             const unsigned char *remote = ref->old_sha1;
             unsigned char local[20];
             struct object *o;

             o = lookup_object(remote);
             if (!o || !(o->flags & COMPLETE)) {
                     retval = 0;
                     if (!args->verbose)
                             continue;
                     fprintf(stderr,
                             "want %s (%s)\n", sha1_to_hex(remote),
                             ref->name);
                     continue;
             }

             hashcpy(ref->new_sha1, local);
             if (!args->verbose)
                     continue;
             fprintf(stderr,
                     "already have %s (%s)\n", sha1_to_hex(remote),
                     ref->name);
     }

Peff, weren't you having some issue with want and have and hide refs?

Tell me please how the "local" variable above gets initialized?

It's declared on the stack inside the for loop scope so only guaranteed to have garbage.

It's passed to hashcpy which has this prototype:

  inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src);

So it looks to me like garbage is copied into rev->new_sha1, yes?

Something's very wrong here.

It looks to me like the bug was introduced in 49bb805e (Do not ask for objects known to be complete. 2005-10-19).

I've taken a stab a a fix below.

-Kyle

-- 8< --
Subject: [PATCH] fetch-pack.c: do not use uninitialized sha1 value

Since 49bb805e (Do not ask for objects known to be complete. 2005-10-19) when the read_ref call was replaced with a parse_object call, the automatic variable 'local' containing an sha1 has been left uninitialized.

Subsequently in 1baaae5e (Make maximal use of the remote refs, 2005-10-28) the parse_object call was replaced with a lookup_object call but still the 'local' variable was left uninitialized.

However, it's used as the source to update another sha1 value in the case that we already have it and in that case the other ref will end up with whatever garbage was in the 'local' variable.

Fix this by removing the 'local' variable and using the value from the result of the lookup_object call instead.

Signed-off-by: Kyle J. McKay <mackyle@gmail.com>
---
 fetch-pack.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

"Kyle J. McKay" <mackyle@gmail.com> writes:

49bb805e (Do not ask for objects known to be complete., 2005-10-19) seems to lose the assignment to local[].

I read that "lines 626-648", stopped reading your message and did a blame session myself, and arrived at the same culprit.

The very original code that read from the ref directly here; I do not think it was an attempt to catch a race condition where ref->old_sha1 got stale and the ref on the filesystem has a newer value. Hence, I think copying from o->sha1 like you did is a fix that is the most faithful to the original code.

o is lookup_object(remote) which is lookup_object(ref->old_sha1); that makes o->sha1 always be ref->old_sha1, so either would be fine, but o->sha1 would be more appropriate in this codeflow. We grab o, if it is NULL or if we do not like it, we do something and continue, otherwise we like that o so grabbing o->sha1 out of it makes the logic look flowing right, at least to me ;-)

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

One thing I wonder is if this hashcpy() is doing anything useful, though. Is ref->new_sha1 used after we are done in this codepath, or is the reason nobody noticed it is because it does not matter whatever garbage is in that field nobody looks at it?

On Mar 15, 2015, at 00:30, Junio C Hamano wrote:

My thoughts exactly. hence the "please confirm" request. I'm not familiar enough with the fetch pack code to know the answer off the top of my head. I was hoping someone else who's been in the fetch pack code recently (*Hi Peff*) might just already know. :)

On Sat, Mar 14, 2015 at 11:37:37PM -0700, Kyle J. McKay wrote:

Yes, but the problem was on the server side. I didn't look at this code at all. :)

So I think we all agree that this is bogus code, and the fix you proposed is reasonable (but spoiler alert, if you read to the end, I think we can do something even more extreme). Like Junio, I am puzzled not by the bug itself, but by its lack of effect over the past 10 years.

I'm not all that familiar with this code, so I started with some rather blunt-hammer tracing.

If you replace that hashcpy with "exit(1)", you get quite a few failures in the test suite. So we really are running the code. Interestingly, if you replace it with "hashclr(ref->old_sha1)" (note old, not new, so impacting the sha1 that we know is actually valid), you still get some failures, but many fewer.

It looks like one of the ways to hit this code path is by doing a clone in which we don't actually need any objects (e.g., using "--reference"). Clone runs fetch-pack to acquire the objects, but then throws away the returned refs and writes its own.

But there are still some failures, so clearly some code paths actually do look at the resulting ref. But nobody seems to care about ref->new_sha1. Let's take one of the cases that the hashclr() experiment found and trace that. In t1507, we do a "git fetch" that hits this case. I instrumented it like this:

Jeff King <peff@peff.net> writes:

Correct. When we want to insert some function to allow users/hooks to tweak the result of update, we might want to make sure that we are passing the final list of refs to that function, but the purpose of this function is not to make such a modification.

Just to make sure we do not keep this hanging forever and eventually forget it, I'm planning to queue this.

Thanks.

-- >8 --
From: Jeff King <peff@peff.next>
Date: Sun, 15 Mar 2015 21:13:43 -0400
Subject: [PATCH] fetch-pack: remove dead assignment to ref->new_sha1

In everything_local(), we used to assign the current ref's value found in ref->old_sha1 to ref->new_sha1 when we already have all the necessary objects to complete the history leading to that commit. This copying was broken at 49bb805e (Do not ask for objects known to be complete., 2005-10-19) and ever since we instead stuffed a random bytes in ref->new_sha1 here. No code complained or failed due to this breakage.

It turns out that no codepath that comes after this assignment even looks at ref->new_sha1 at all.

 - The only caller of everything_local(), do_fetch_pack(), returns
   this list of ref, whose element has bogus new_sha1 values, to its
   caller.  It does not look at the elements and acts on them.

 - The only caller of do_fetch_pack(), fetch_pack(), returns this
   list to its caller.  It does not look at the elements and acts on
   them.

 - One of the two callers of fetch_pack() is cmd_fetch_pack(), the
   top-level that implements "git fetch-pack".  The only thing it
   looks at in the elements of the returned ref list is the old_sha1
   and name fields.

 - The other caller of fetch_pack() is fetch_refs_via_pack() in the
   transport layer, which is a helper that implements "git fetch".
   It only cares about whether the returned list is empty (i.e.
   failed to fetch anything).

Just drop the bogus assignment, that is not even necessary. The remote-tracking refs are updated based on a different list and not using the ref list being manipulated by this codepath; the caller do_fetch_pack() created a copy of that real ref list and passed the copy down to this function, and modifying the elements here does not affect anything.

Noticed-by: Kyle J. McKay <mackyle@gmail.com>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 fetch-pack.c | 3 ---
 1 file changed, 3 deletions(-)

On Thu, Mar 19, 2015 at 10:41:50AM -0700, Junio C Hamano wrote:

Thanks for following up. A few minor nits (and maybe a more serious problem) on the explanation in the commit message:

s/a random/random/

s/list of ref/list of refs/ ? Or did you mean "the list we store in the 'ref' variable"?

I'm not sure what the final sentence means. Should it be "It does not look at the elements nor act on them"?

do_fetch_pack actually does pass them down to find_common. But the latter does not look at ref->new_sha1, so we're OK.

Ditto on the wording in the final sentence here (but it is correct in this case that we do not touch the list at all).

So I thought I would follow this up by adding a free_refs() call in fetch_refs_via_pack. After all, we just leak that list, right?

If only it were so simple. It turns out that the list returned from fetch_pack() is _mostly_ a copy of the incoming refs list we give it. But in filter_refs(), if allow_tip_sha1_in_want is set, we actually add the unmatched "sought" refs here, too.

Which means we may be setting new_sha1 in one of these "sought" refs, and that broadens the scope of code that might be affected by the patch we have been discussing. However, I think the filter_refs code is wrong, and should be making a copy of the sought refs to put in the new list.

I'm working up a few patches in that area, which I'll send out in a few minutes. Once that is done, then I think the explanation you give above would be correct.

-Peff

Jeff King <peff@peff.net> writes:

Yes. "It does not look at the new_sha1. It does not use the information to change its behaviour. Both of the previous two statements are true." is what I meant.

Yeah, I agree.

If a follow-up is coming then I'd just drop this one.  Thanks.

On Thu, Mar 19, 2015 at 12:01:26PM -0700, Junio C Hamano wrote:

OK, here it is. Took me a bit longer than I expected, as I wanted to figure out whether the second patch was actually fixing a bug (and if so, to add test coverage). Turns out that it is a real bug.

The final patch is what you sent, rebased on top (though there are not any code changes; the underlying commits make the _explanation_ true, but no code change was required). I fixed up the nits I mentioned in my earlier email.

  [1/4]: filter_ref: avoid overwriting ref->old_sha1 with garbage
  [2/4]: filter_ref: make a copy of extra "sought" entries
  [3/4]: fetch_refs_via_pack: free extra copy of refs
  [4/4]: fetch-pack: remove dead assignment to ref->new_sha1

-Peff

If the server supports allow_tip_sha1_in_want, then fetch-pack's filter_refs function tries to check whether a ref is a request for a straight sha1 by running:

  if (get_sha1_hex(ref->name, ref->old_sha1))
	  ...

I.e., we are using get_sha1_hex to ask "is this ref name a sha1?". If it is true, then the contents of ref->old_sha1 will end up unchanged. But if it is false, then get_sha1_hex makes no guarantees about what it has written. With a ref name like "abcdefoo", we would overwrite 3 bytes of ref->old_sha1 before realizing that it was not a sha1.

This is likely not a problem in practice, as anything in refs->name (besides a sha1) will start with "refs/", meaning that we would notice on the first character that there is a problem. Still, we are making assumptions about the state left in the output when get_sha1_hex returns an error (e.g., it could start from the end of the string, or error check the values only once they were placed in the output). It's better to be defensive.

We could just check that we have exactly 40 characters of sha1. But let's be even more careful and make sure that we have a 40-char hex refname that matches what is in old_sha1. This is perhaps overly defensive, but spells out our assumptions clearly.

Signed-off-by: Jeff King <peff@peff.net>
---
This one is not necessary for the others, of course, and we can drop it
if you disagree with the reasoning.

I wonder if the thinking in the original was that it was our responsibility here to make sure that ref->old_sha1 was filled in. It is always filled in by the caller who gives us "sought", which makes sense to me (this matches the rest of the "sought" entries, which come from reading the remote's ref list, and of course must fill in old_sha1 from that list).

 fetch-pack.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

Jeff King <peff@peff.net> writes:

I am reasonably sure that is the (perhaps mistaken) reasoning behind the use of old_sha1 as the second parameter to get_sha1_hex().

I see that sought is populated by reading the command line of "git fetch-pack", and for a 40-hex request ref->old_sha1 is already filled there, so I agree that it is redundant to try filling it in filter_refs().

Thanks.

If the server supports allow_tip_sha1_in_want, we add any unmatched raw-sha1 entries in our "sought" list of refs to the list of refs we will ask the other side for. We do so by inserting the original "struct ref" directly into our list, rather than making a copy. This has several problems.

The most minor problem is that one cannot ever free the resulting list; it contains structs that are copies of the remote refs (made earlier by fetch_pack) along with sought refs that are referenced elsewhere.

But more importantly that we set the ref->next pointer to NULL, chopping off the remainder of any existing list that the ref was a part of. We get the set of "sought" refs in an array rather than a linked list, but that array is often in turn generated from a list. The test modification in t5516 demonstrates this. Rather than fetching just an exact sha1, we fetch that sha1 plus another ref:

  - we build a linked list of refs to fetch when do_fetch
    calls get_ref_map; the exact sha1 is first, followed by
    the named ref ("refs/heads/extra" in this case).

  - we pass that linked list to transport_fetch_ref, which
    squashes it into an array of pointers

  - that array goes to fetch_pack, which calls filter_ref.
    There we generate the want list from a mix of what the
    remote side has advertised, and the "sought" entry for
    the exact sha1. We set the sought entry's "next" pointer
    to NULL.

  - after we return from transport_fetch_refs, we then try
    to update the refs by following the linked list. But our
    list is now truncated, and we do not update
    refs/heads/extra at all.

We can fix this by making a copy of the ref. There's nothing that fetch_pack does to it that must be reflected in the original "sought" list (and indeed, if that were the case we would have a serious bug, because it is only exact-sha1 entries which are treated this way).

Signed-off-by: Jeff King <peff@peff.net>
---
I always feel a little dirty modifying an existing test rather than
writing a new one that more clearly demonstrates what we are testing.
But the setup involved in the exact-sha1 fetch is a little complicated,
so this seemed easiest (and anybody blaming the change can hopefully
rely on the explanation above to understand what is going on).

 fetch-pack.c          |  5 ++---
 t/t5516-fetch-push.sh | 13 ++++++++++---
 2 files changed, 12 insertions(+), 6 deletions(-)

When fetch_refs_via_pack calls fetch_pack(), we pass a list of refs to fetch, and the function returns either a copy of that list, with the fetched items filled in, or NULL. We check the return value to see whether the fetch was successful, but do not otherwise look at the copy, and simply leak it at the end of the function.

Signed-off-by: Jeff King <peff@peff.net>
---
Without patch 2, this segfaults in t5516. :)

 transport.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

In everything_local(), we used to assign the current ref's value found in ref->old_sha1 to ref->new_sha1 when we already have all the necessary objects to complete the history leading to that commit. This copying was broken at 49bb805e (Do not ask for objects known to be complete., 2005-10-19) and ever since we instead stuffed a random bytes in ref->new_sha1 here. No code complained or failed due to this breakage.

It turns out that no code path that comes after this assignment even looks at ref->new_sha1 at all.

 - The only caller of everything_local(), do_fetch_pack(),
   returns this list of refs, whose element has bogus
   new_sha1 values, to its caller.  It does not look at the
   elements itself, but does pass them to find_common, which
   looks only at the name and old_sha1 fields.

 - The only caller of do_fetch_pack(), fetch_pack(), returns this
   list to its caller.  It does not look at the elements nor act on
   them.

 - One of the two callers of fetch_pack() is cmd_fetch_pack(), the
   top-level that implements "git fetch-pack".  The only thing it
   looks at in the elements of the returned ref list is the old_sha1
   and name fields.

 - The other caller of fetch_pack() is fetch_refs_via_pack() in the
   transport layer, which is a helper that implements "git fetch".
   It only cares about whether the returned list is empty (i.e.
   failed to fetch anything).

Just drop the bogus assignment, that is not even necessary. The remote-tracking refs are updated based on a different list and not using the ref list being manipulated by this code path; the caller do_fetch_pack() created a copy of that real ref list and passed the copy down to this function, and modifying the elements here does not affect anything.

Noticed-by: Kyle J. McKay <mackyle@gmail.com>
Signed-off-by: Jeff King <peff@peff.net>
---
 fetch-pack.c | 3 ---
 1 file changed, 3 deletions(-)