Re: Bad objects error since upgrading GitHub servers to 1.6.1

"Shawn O. Pearce" [off-list ref] writes:

Junio C Hamano [off-list ref] wrote:

quoted

"Shawn O. Pearce" [off-list ref] writes:

quoted

Oh, right, its not.  I was pointing out that the last time the
protocol changed in a way the server can infer something about the
client, which IIRC was 41fa7d2, we still don't have a way to tell
what the client is.

But you are still talking as if there is one protocol you can call "the
protocol", but it is not.  The send-pack receive-pack protocol is on topic
in this thread; the quoted commit was about a separate and independent
fetch-pack upload-pack protocol.  It does not matter when that unrelated
protocol was enhanced.

Blargh.  Of course you are right.  Its been a long 2 months for me
at work.  I'm too #@*#@!@! tired to keep the basics straight anymore.

I'm going to shut up now.

Please don't.

I've been toying with an idea for an alternative solution, and need
somebody competent to bounce it around with.

pack-objects ends up doing eventually

    rev-list --objects $send1 $send2 $send3 ... --not $have1 $have2 ...

which lists commits and associated objects reachable from $sendN,
excluding the ones that are reachable from $haveN.

The tentative solution Björn Steinbrink and I came up with excludes
missing commit from $haveN to avoid rev-list machinery to barf, but it
violates the ref-object contract as I explained to Björn in my other
message.

	Side note.  We often cite "interrupted commit walkers" as the
	reason why has_sha1_file() is not a good enough check, but you can
	discard a deep commit chain by deleting a branch, and have gc
	expire older commit in the commit chain while retaining newer ones
	near the tip of that branch.  If (1) you earlier gave that branch
	to somebody else, (2) that somebody else has the tip of the branch
	you discarded in his repository, and (3) the repository you are
	pushing into borrows from that somebody else's repository, then
	you have the same situation that your has_sha1_file() succeeds but
	it will fail when you start digging deeper.

Checking if each commit is reachable from any of the refs is quite
expensive, and it would especially be so if it is done once per ".have"
and real ref we receive from the other end.

An alternative is to realize that rev-list traversal already does
something quite similar to what is needed to prove if these ".have"s are
reachable from refs when listing the reachable objects.  This computation
is what it needs to do anyway, so if we teach rev-list to ignore missing
or broken chain while traversing negative refs, we do not have to incur
any overhead over existing code.

Here is my work in progress.  It introduces "ignore-missing-negative"
option to the revision traversal machinery, and squelches the places we
currently complain loudly and die when we expect an object to be
available, when the color we are going to paint the object with is
UNINTERESTING.

I have a mild suspicion that it may even be the right thing to ignore them
unconditionally, and it might even match the intention of Linus's original
code.  That would make many hunks in this patch much simpler.

The evidences behind this suspicion are found in a handful of places in
revision.c.  mark_blob_uninteresting() does not complain if the caller
fails to find the blob.  mark_tree_uninteresting() does not, either.
mark_parents_uninteresting() does not, either, and it even has a comment
that strongly suggests the original intention was not to care about
missing UNINTERESTING objects.

 builtin-pack-objects.c |    1 +
 revision.c             |   24 ++++++++++++++++++++----
 revision.h             |    1 +
 3 files changed, 22 insertions(+), 4 deletions(-)

diff --git i/builtin-pack-objects.c w/builtin-pack-objects.c
index cedef52..c615a2f 100644
--- i/builtin-pack-objects.c
+++ w/builtin-pack-objects.c

@@ -2026,6 +2026,7 @@ static void get_object_list(int ac, const char **av)
 	int flags = 0;
 
 	init_revisions(&revs, NULL);
+	revs.ignore_missing_negative = 1;
 	save_commit_buffer = 0;
 	setup_revisions(ac, av, &revs, NULL);
 

diff --git i/revision.c w/revision.c
index db60f06..314341b 100644
--- i/revision.c
+++ w/revision.c

@@ -132,6 +132,8 @@ void mark_parents_uninteresting(struct commit *commit)
 
 static void add_pending_object_with_mode(struct rev_info *revs, struct object *obj, const char *name, unsigned mode)
 {
+	if (!obj)
+		return;
 	if (revs->no_walk && (obj->flags & UNINTERESTING))
 		die("object ranges do not make sense when not walking revisions");
 	if (revs->reflog_info && obj->type == OBJ_COMMIT &&

@@ -163,8 +165,11 @@ static struct object *get_reference(struct rev_info *revs, const char *name, con
 	struct object *object;
 
 	object = parse_object(sha1);
-	if (!object)
+	if (!object) {
+		if (revs->ignore_missing_negative && (flags & UNINTERESTING))
+			return NULL;
 		die("bad object %s", name);
+	}
 	object->flags |= flags;
 	return object;
 }

@@ -183,8 +188,11 @@ static struct commit *handle_commit(struct rev_info *revs, struct object *object
 		if (!tag->tagged)
 			die("bad tag");
 		object = parse_object(tag->tagged->sha1);
-		if (!object)
+		if (!object) {
+			if (revs->ignore_missing_negative && (flags & UNINTERESTING))
+				return NULL;
 			die("bad object %s", sha1_to_hex(tag->tagged->sha1));
+		}
 	}
 
 	/*

@@ -193,8 +201,11 @@ static struct commit *handle_commit(struct rev_info *revs, struct object *object
 	 */
 	if (object->type == OBJ_COMMIT) {
 		struct commit *commit = (struct commit *)object;
-		if (parse_commit(commit) < 0)
+		if (parse_commit(commit) < 0) {
+			if (revs->ignore_missing_negative && (flags & UNINTERESTING))
+				return NULL;
 			die("unable to parse commit %s", name);
+		}
 		if (flags & UNINTERESTING) {
 			commit->object.flags |= UNINTERESTING;
 			mark_parents_uninteresting(commit);

@@ -479,8 +490,11 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 		while (parent) {
 			struct commit *p = parent->item;
 			parent = parent->next;
-			if (parse_commit(p) < 0)
+			if (parse_commit(p) < 0) {
+				if (revs->ignore_missing_negative)
+					return 0;
 				return -1;
+			}
 			p->object.flags |= UNINTERESTING;
 			if (p->parents)
 				mark_parents_uninteresting(p);

@@ -1110,6 +1124,8 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 		revs->tree_objects = 1;
 		revs->blob_objects = 1;
 		revs->edge_hint = 1;
+	} else if (!strcmp(arg, "--ignore-missing-negative")) {
+		revs->ignore_missing_negative = 1;
 	} else if (!strcmp(arg, "--unpacked")) {
 		revs->unpacked = 1;
 		free(revs->ignore_packed);

diff --git i/revision.h w/revision.h
index 7cf8487..bb90399 100644
--- i/revision.h
+++ w/revision.h

@@ -48,6 +48,7 @@ struct rev_info {
 			tree_objects:1,
 			blob_objects:1,
 			edge_hint:1,
+			ignore_missing_negative:1,
 			limited:1,
 			unpacked:1, /* see also ignore_packed below */
 			boundary:2,

On Tue, Jan 27, 2009 at 11:14:56PM -0800, Junio C Hamano wrote:

I've been toying with an idea for an alternative solution, and need
somebody competent to bounce it around with.

Well, unfortunately for you, you are stuck with me. ;P

Here is my work in progress.  It introduces "ignore-missing-negative"
option to the revision traversal machinery, and squelches the places we
currently complain loudly and die when we expect an object to be
available, when the color we are going to paint the object with is
UNINTERESTING.

I have a mild suspicion that it may even be the right thing to ignore them
unconditionally, and it might even match the intention of Linus's original
code.  That would make many hunks in this patch much simpler.

I'm not sure it is a good idea to do so unconditionally. In the case of
negatives for transferring files, a missed negative is simply a missed
opportunity for optimizing the resulting pack.

But in other cases, it silently gives you the wrong answer.  For
example, consider a history like:

       C--D
      /
  A--B
      \
       E--F

now let's suppose I have everything except 'E'. If I ask for

  git rev-list F..D

then it will not realize that A and B are uninteresting, and I will get
A-B-C-D. I think it is much better for git to complain loudly that it
could not compute the correct answer.

Am I understanding the issue correctly?

-Peff

Junio C Hamano [off-list ref] wrote:

I've been toying with an idea for an alternative solution, and need
somebody competent to bounce it around with.

Heh, then we need to wait for Nico... :-)
 

pack-objects ends up doing eventually

    rev-list --objects $send1 $send2 $send3 ... --not $have1 $have2 ...

which lists commits and associated objects reachable from $sendN,
excluding the ones that are reachable from $haveN.

The tentative solution Björn Steinbrink and I came up with excludes
missing commit from $haveN to avoid rev-list machinery to barf, but it
violates the ref-object contract as I explained to Björn in my other
message.

Oh, OK, I now _finally_ understand what you were trying to say
by the reachability thing.  I kept scratching my head trying to
understand you, and was going to say something stupid on list;
but waited because I just didn't get what the big deal was...

Its the crash in rev-list that you were worried about.

Checking if each commit is reachable from any of the refs is quite
expensive, and it would especially be so if it is done once per ".have"
and real ref we receive from the other end.

Yup.
 

An alternative is to realize that rev-list traversal already does
something quite similar to what is needed to prove if these ".have"s are
reachable from refs when listing the reachable objects.  This computation
is what it needs to do anyway, so if we teach rev-list to ignore missing
or broken chain while traversing negative refs, we do not have to incur
any overhead over existing code.

EXACTLY.

JGit does this.

The functional equivilant of rev-list in JGit will by default
throw an exception if any object is missing when we try to walk it.
That includes things we've painted UNINTERESTING, as it is a sure
sign of repository corruption.

However; our equivilant of pack-objects can toggle what you are
calling "ignore-missing-negative" when it starts enumeration.
Any UNINTERESTING object which is missing or failed to parse is
simply tossed aside.  Yes, the pack may be larger than necessary
like in Peff's example of:

       Q-R
      /
  D--E
      \
       A-C

If the other side has C reachable, we are pushing R, and we have
C but are missing A, we'll "over push" D-E, but its still a clean
and valid push.  Its no worse than we were before the ".have" came
about, or if C hadn't been downloaded locally at all.  (Of course
your tell-me-more extension would help fix this over-push, but lets
not get off topic.)

IMHO, this corruption of A is harmless if C isn't reachable.

It isn't really local corruption unless C was reachable by a ref.
But we don't tend to see much corruption like that, and if it did
exist, it would show up during *other* operations that access a
larger set of local refs, such as "git gc".

I have a mild suspicion that it may even be the right thing to ignore them
unconditionally, and it might even match the intention of Linus's original
code.  That would make many hunks in this patch much simpler.

I don't think its right to ignore broken UNINTERESTING chains all
of the time.  Today we would see fatal errors if I asked for

  git log R ^C

and A was missing, but R and C are both local refs.  I still want
to see that fatal error.  Its a local corruption that should be
raised quickly to the user.  In fact by A missing we'd compute the
wrong result and produce D-E too, which is wrong.

IMHO, the *only* time this missing uninteresting A is safe is
during send-pack, upload-pack, or bundle creation, where you are
bringing the other side up to R by transferring any amount of data
necessary to reach that goal.  Which is why JGit enables this.
(Though at the API level we do let the caller flag if they want
the error to be fatal instead, but AFAIK nobody sets it for "fatal".)

FWIW, Linus' most recent message on this thread about hoisting the
UNINTERESTING test up sooner makes sense too.
 

The evidences behind this suspicion are found in a handful of places in
revision.c.  mark_blob_uninteresting() does not complain if the caller
fails to find the blob.  mark_tree_uninteresting() does not, either.
mark_parents_uninteresting() does not, either, and it even has a comment
that strongly suggests the original intention was not to care about
missing UNINTERESTING objects.

That feels wrong to me... given the "git log R ^C" example I give above.
 
-- 
Shawn.

On Wed, 28 Jan 2009, Shawn O. Pearce wrote:

Junio C Hamano [off-list ref] wrote:

quoted

I've been toying with an idea for an alternative solution, and need
somebody competent to bounce it around with.

Heh, then we need to wait for Nico... :-)

Hmmm... ehhh... what have I done?

/me tries to walk by innocently without being noticed  ;-)


Nicolas

On Wed, Jan 28, 2009 at 08:09:00AM -0800, Shawn O. Pearce wrote:

I don't think its right to ignore broken UNINTERESTING chains all
of the time.  Today we would see fatal errors if I asked for

  git log R ^C

and A was missing, but R and C are both local refs.  I still want
to see that fatal error.  Its a local corruption that should be
raised quickly to the user.  In fact by A missing we'd compute the
wrong result and produce D-E too, which is wrong.

I think you wrote this before reading the other part of the thread where
we see that many of these checks are not in C git. But to be clear, even
without Junio's patches the exact case I mentioned is not currently
reported as an error (i.e., will produce incorrect results). I tested
with:

-- >8 --
commit() {
    echo $1 >$1 && git add $1 && git commit -m $1 && git tag $1
}

mkdir repo && cd repo && git init
commit A
commit B
commit C
commit D
git checkout -b other B
commit E
commit F

rm -f .git/objects/`git rev-parse E | sed 's,^..,&/,'`
git log F..D
-- 8< --

which shows A-B-C-D.

-Peff