[PATCH] pull: gracefully recover from delta retrieval failure.

[PATCH] pull: gracefully recover from delta retrieval failure.

[Junio C Hamano]

This addresses a concern raised by Jason McMullan in the mailing
list discussion.  After retrieving and storing a potentially
deltified object, pull logic tries to check and fulfil its delta
dependency.  When the pull procedure is killed at this point,
however, there was no easy way to recover by re-running pull,
since next run would have found that we already have that
deltified object and happily reported success, without really
checking its delta dependency is satisfied.

This patch introduces --recover option to git-*-pull family
which causes them to re-validate dependency of deltified objects
we are fetching.  A new test t5100-delta-pull.sh covers such a
failure mode.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---

*** Linus, from now on I will go into "calming down" mode and
*** refrain myself from sending you too many "new" stuff, until
*** you tell me otherwise.  I will concentrate on fixes like
*** this one and the "diff-* -B fix" patches I sent you earlier.
*** Perhaps I would also work on CVS migration documents if you
*** would like me to help you in that area as well.

*** Definitely things like the idea of diff-tree switching its
*** pathspec according rename detection results would not be
*** something I'll be bugging you about until 1.0 happens;
*** unless you tell me otherwise, that is.

 Documentation/git-http-pull.txt  |    5 ++
 Documentation/git-local-pull.txt |    5 ++
 Documentation/git-rpull.txt      |    5 ++
 pull.h                           |    4 +-
 http-pull.c                      |    4 +-
 local-pull.c                     |    4 +-
 pull.c                           |   15 +++++--
 rpull.c                          |    4 +-
 t/t5100-delta-pull.sh            |   79 ++++++++++++++++++++++++++++++++++++++
 9 files changed, 113 insertions(+), 12 deletions(-)

diff --git a/Documentation/git-http-pull.txt b/Documentation/git-http-pull.txt
--- a/Documentation/git-http-pull.txt
+++ b/Documentation/git-http-pull.txt
@@ -9,7 +9,7 @@ git-http-pull - Downloads a remote GIT r
 
 SYNOPSIS
 --------
-'git-http-pull' [-c] [-t] [-a] [-v] [-d] commit-id url
+'git-http-pull' [-c] [-t] [-a] [-v] [-d] [--recover] commit-id url
 
 DESCRIPTION
 -----------
@@ -25,6 +25,9 @@ Downloads a remote GIT repository via HT
 	Do not check for delta base objects (use this option
 	only when you know the remote repository is not
 	deltified).
+--recover::
+	Check dependency of deltified object more carefully than
+	usual, to recover after earlier pull that was interrupted.
 -v::
 	Report what is downloaded.
 
diff --git a/Documentation/git-local-pull.txt b/Documentation/git-local-pull.txt
--- a/Documentation/git-local-pull.txt
+++ b/Documentation/git-local-pull.txt
@@ -9,7 +9,7 @@ git-local-pull - Duplicates another GIT 
 
 SYNOPSIS
 --------
-'git-local-pull' [-c] [-t] [-a] [-l] [-s] [-n] [-v] [-d] commit-id path
+'git-local-pull' [-c] [-t] [-a] [-l] [-s] [-n] [-v] [-d] [--recover] commit-id path
 
 DESCRIPTION
 -----------
@@ -27,6 +27,9 @@ OPTIONS
 	Do not check for delta base objects (use this option
 	only when you know the remote repository is not
 	deltified).
+--recover::
+	Check dependency of deltified object more carefully than
+	usual, to recover after earlier pull that was interrupted.
 -v::
 	Report what is downloaded.
 
diff --git a/Documentation/git-rpull.txt b/Documentation/git-rpull.txt
--- a/Documentation/git-rpull.txt
+++ b/Documentation/git-rpull.txt
@@ -10,7 +10,7 @@ git-rpull - Pulls from a remote reposito
 
 SYNOPSIS
 --------
-'git-rpull' [-c] [-t] [-a] [-d] [-v] commit-id url
+'git-rpull' [-c] [-t] [-a] [-d] [-v] [--recover] commit-id url
 
 DESCRIPTION
 -----------
@@ -29,6 +29,9 @@ OPTIONS
 	Do not check for delta base objects (use this option
 	only when you know the remote repository is not
 	deltified).
+--recover::
+	Check dependency of deltified object more carefully than
+	usual, to recover after earlier pull that was interrupted.
 -v::
 	Report what is downloaded.
 
diff --git a/pull.h b/pull.h
--- a/pull.h
+++ b/pull.h
@@ -13,7 +13,9 @@ extern int get_history;
 /** Set to fetch the trees in the commit history. **/
 extern int get_all;
 
-/* Set to zero to skip the check for delta object base. */
+/* Set to zero to skip the check for delta object base;
+ * set to two to check delta dependency even for objects we already have.
+ */
 extern int get_delta;
 
 /* Set to be verbose */
diff --git a/http-pull.c b/http-pull.c
--- a/http-pull.c
+++ b/http-pull.c
@@ -105,6 +105,8 @@ int main(int argc, char **argv)
 			get_history = 1;
 		} else if (argv[arg][1] == 'd') {
 			get_delta = 0;
+		} else if (!strcmp(argv[arg], "--recover")) {
+			get_delta = 2;
 		} else if (argv[arg][1] == 'a') {
 			get_all = 1;
 			get_tree = 1;
@@ -115,7 +117,7 @@ int main(int argc, char **argv)
 		arg++;
 	}
 	if (argc < arg + 2) {
-		usage("git-http-pull [-c] [-t] [-a] [-d] [-v] commit-id url");
+		usage("git-http-pull [-c] [-t] [-a] [-d] [-v] [--recover] commit-id url");
 		return 1;
 	}
 	commit_id = argv[arg];
diff --git a/local-pull.c b/local-pull.c
--- a/local-pull.c
+++ b/local-pull.c
@@ -74,7 +74,7 @@ int fetch(unsigned char *sha1)
 }
 
 static const char *local_pull_usage = 
-"git-local-pull [-c] [-t] [-a] [-l] [-s] [-n] [-v] [-d] commit-id path";
+"git-local-pull [-c] [-t] [-a] [-l] [-s] [-n] [-v] [-d] [--recover] commit-id path";
 
 /* 
  * By default we only use file copy.
@@ -94,6 +94,8 @@ int main(int argc, char **argv)
 			get_history = 1;
 		else if (argv[arg][1] == 'd')
 			get_delta = 0;
+		else if (!strcmp(argv[arg], "--recover"))
+			get_delta = 2;
 		else if (argv[arg][1] == 'a') {
 			get_all = 1;
 			get_tree = 1;
diff --git a/pull.c b/pull.c
--- a/pull.c
+++ b/pull.c
@@ -6,6 +6,7 @@
 
 int get_tree = 0;
 int get_history = 0;
+/* 1 means "get delta", 2 means "really check delta harder */
 int get_delta = 1;
 int get_all = 0;
 int get_verbosely = 0;
@@ -32,12 +33,16 @@ static void report_missing(const char *w
 
 static int make_sure_we_have_it(const char *what, unsigned char *sha1)
 {
-	int status;
-	if (has_sha1_file(sha1))
+	int status = 0;
+
+	if (!has_sha1_file(sha1)) {
+		status = fetch(sha1);
+		if (status && what)
+			report_missing(what, sha1);
+	}
+	else if (get_delta < 2)
 		return 0;
-	status = fetch(sha1);
-	if (status && what)
-		report_missing(what, sha1);
+
 	if (get_delta) {
 		char delta_sha1[20];
 		status = sha1_delta_base(sha1, delta_sha1);
diff --git a/rpull.c b/rpull.c
--- a/rpull.c
+++ b/rpull.c
@@ -52,6 +52,8 @@ int main(int argc, char **argv)
 			get_history = 1;
 		} else if (argv[arg][1] == 'd') {
 			get_delta = 0;
+		} else if (!strcmp(argv[arg], "--recover")) {
+			get_delta = 2;
 		} else if (argv[arg][1] == 'a') {
 			get_all = 1;
 			get_tree = 1;
@@ -62,7 +64,7 @@ int main(int argc, char **argv)
 		arg++;
 	}
 	if (argc < arg + 2) {
-		usage("git-rpull [-c] [-t] [-a] [-v] [-d] commit-id url");
+		usage("git-rpull [-c] [-t] [-a] [-v] [-d] [--recover] commit-id url");
 		return 1;
 	}
 	commit_id = argv[arg];
diff --git a/t/t5100-delta-pull.sh b/t/t5100-delta-pull.sh
new file mode 100644
--- /dev/null
+++ b/t/t5100-delta-pull.sh
@@ -0,0 +1,79 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Junio C Hamano
+#
+
+test_description='Test pulling deltified objects
+
+'
+. ./test-lib.sh
+
+locate_obj='s|\(..\)|.git/objects/\1/|'
+
+test_expect_success \
+    setup \
+    'cat ../README >a &&
+    git-update-cache --add a &&
+    a0=`git-ls-files --stage |
+        sed -e '\''s/^[0-7]* \([0-9a-f]*\) .*/\1/'\''` &&
+
+    sed -e 's/test/TEST/g' ../README >a &&
+    git-update-cache a &&
+    a1=`git-ls-files --stage |
+        sed -e '\''s/^[0-7]* \([0-9a-f]*\) .*/\1/'\''` &&
+    tree=`git-write-tree` &&
+    commit=`git-commit-tree $tree </dev/null` &&
+    a0f=`echo "$a0" | sed -e "$locate_obj"` &&
+    a1f=`echo "$a1" | sed -e "$locate_obj"` &&
+    echo commit $commit &&
+    echo a0 $a0 &&
+    echo a1 $a1 &&
+    ls -l $a0f $a1f &&
+    echo $commit >.git/HEAD &&
+    git-mkdelta -v $a0 $a1 &&
+    ls -l $a0f $a1f'
+
+# Now commit has a tree that records delitified "a" whose SHA1 is a1.
+# Create a new repo and pull this commit into it.
+
+test_expect_success \
+    'setup and cd into new repo' \
+    'mkdir dest && cd dest && rm -fr .git && git-init-db'
+     
+test_expect_success \
+    'pull from deltified repo into a new repo without -d' \
+    'rm -fr .git a && git-init-db &&
+     git-local-pull -v -a $commit ../.git/ &&
+     git-cat-file blob $a1 >a &&
+     diff -u a ../a'
+
+test_expect_failure \
+    'pull from deltified repo into a new repo with -d' \
+    'rm -fr .git a && git-init-db &&
+     git-local-pull -v -a -d $commit ../.git/ &&
+     git-cat-file blob $a1 >a &&
+     diff -u a ../a'
+
+test_expect_failure \
+    'pull from deltified repo after delta failure without --recover' \
+    'rm -f a &&
+     git-local-pull -v -a $commit ../.git/ &&
+     git-cat-file blob $a1 >a &&
+     diff -u a ../a'
+
+test_expect_success \
+    'pull from deltified repo after delta failure with --recover' \
+    'rm -f a &&
+     git-local-pull -v -a --recover $commit ../.git/ &&
+     git-cat-file blob $a1 >a &&
+     diff -u a ../a'
+
+test_expect_success \
+    'missing-tree or missing-blob should be re-fetched without --recover' \
+    'rm -f a $a0f $a1f &&
+     git-local-pull -v -a $commit ../.git/ &&
+     git-cat-file blob $a1 >a &&
+     diff -u a ../a'
+
+test_done
+
------------

Re: [PATCH] pull: gracefully recover from delta retrieval failure.

[Jason McMullan]

On Sat, 2005-06-04 at 23:11 -0700, Junio C Hamano wrote:
> This addresses a concern raised by Jason McMullan in the mailing
> list discussion.  After retrieving and storing a potentially
> deltified object, pull logic tries to check and fulfil its delta
> dependency.  When the pull procedure is killed at this point,
> however, there was no easy way to recover by re-running pull,
> since next run would have found that we already have that
> deltified object and happily reported success, without really
> checking its delta dependency is satisfied.

I still think it would be much better if you didn't place unverified
objects in the database in the first place. You've taken care of delta
object recovery, yes, but what about unsatisfied tree objects? Or commit
objects? Does your algorithm require full depth scanning of the
entire repository that is descended from the commit head?

I much prefer to always leave the database in a consistent state, that
way you only have to do O(number-of-retrieved-objects) verifications,
not O(number-of-commit-tree-ancestors) verifications.

Or am I misunderstanding your technique here? 

Sorry about being a pest, but this worries me. Please assuage my fears.

(Or, if you'd like, I can rework pull.c to use the
 verification-before-store technique I used in my git-daemon patch, so
 all the *-pull mechanisms will be 'safe')

Re: [PATCH] pull: gracefully recover from delta retrieval failure.

[Daniel Barkalow]

On Sun, 5 Jun 2005, Jason McMullan wrote:

> (Or, if you'd like, I can rework pull.c to use the
>  verification-before-store technique I used in my git-daemon patch, so
>  all the *-pull mechanisms will be 'safe')

The reasons I don't really want a verification-before-store are:

 - I'd like things to be resumable on error; if you've already got a bunch
   of stuff and then the connection breaks, you should already have the
   things you got; so, at least, the temporary locations should be
   something predictable from the hash.

 - I'd like the user to be able to intentionally get partial repositories
   of various sorts, and still have consistant information. If I don't
   have anything written that's not in mainline, and I'm not going to be
   applying other people's patches, and I don't have an up-to-date
   repository, I'd like to be able to pull just mainline's head commit and
   tree, and work from there. I don't need the history unless I want to
   look up changes or want to merge something that's not derived entirely
   from the head I've got.

So what I'd really like is something where you store whatever objects you
have, and also have extra information about what objects you know about
but don't have and what objects you've gotten completely. Of course, this
needs to be kept manageable.

(Along the lines of the second one, there's a variety of partial
information which is sufficient for various purposes. If I trust that
Linus's latest tree is based on my most recent pull from him, I can
fast-forward with just the tree. I can also merge his tree into mine with
just the commits and his latest tree, since I must already have any common
ancestors. In all these cases, I may want to streamline my process by
doing "pull tree; pull all &; checkout" or 
"pull tree,commits; pull all &; merge", so that I can start on further
development while the rest of the information fills in.)

So I'd greatly prefer to keep the metadata of what objects we have
explicitly, rather than implicitly in the presence or absence of files in
the object directory. Also, for objects which we expect to be missing, it
would be good to keep info on where we expect to be able to get
them. Then, if I'm wrong about what I actually needed, it doesn't need me
to tell it again where to get things.

	-Daniel
*This .sig left intentionally blank*

Re: [PATCH] pull: gracefully recover from delta retrieval failure.

[Junio C Hamano]

>>>>> "JM" == Jason McMullan <jason.mcmullan@timesys.com> writes:

JM> Sorry about being a pest, but this worries me. Please assuage my fears.

Earlier I said I suspected that the original code mishandled
recovery from a botched tree/commit dependent transfer, but that
was not the case.  The last test in the new test script I added
in the patch you are responding to covers that case.

JM> (Or, if you'd like, I can rework pull.c to use the
JM>  verification-before-store technique I used in my git-daemon patch, so
JM>  all the *-pull mechanisms will be 'safe')

I would appreciate the offer.  I, however, would have to warn
you that the "problem" lies in the way the current pull
structure devides responsibility between the pull.c and transfer
backends.  The pull.c implements the dependency logic, and
transfer backends are to populate the database while being
oblivious of that logic.  From the purist point of view (I am
sympathetic to your "place only the verified objects in the
database" principle), I am not entirely happy with that
division, but at the same time I understand why it is done that
way and even like it from practical standpoint.  Otherwise you
need to keep a bunch of objects somewhere outside the database
along with the list of "things to rename to the final database
name when we are done".  You would somehow need to do clean-up
when we fail in the middle _anyway_.

In other words, the current structure is optimized for non-
failure case, as it should be.  The original implementation
(credit goes to Dan Barkalow) knew how to recover from failed
transfer (including the case that you first pull with -c or -t
without using -a to miss some required objects to satisfy -a) by
simply running pull again, and with the --recover flag, it now
knows how to recover from failed deltified object transfer as
well.

Re: [PATCH] pull: gracefully recover from delta retrieval failure.

[Daniel Barkalow]

On Sun, 5 Jun 2005, Junio C Hamano wrote:

> >>>>> "JM" == Jason McMullan <jason.mcmullan@timesys.com> writes:
> 
> JM> Sorry about being a pest, but this worries me. Please assuage my fears.
> 
> Earlier I said I suspected that the original code mishandled
> recovery from a botched tree/commit dependent transfer, but that
> was not the case.  The last test in the new test script I added
> in the patch you are responding to covers that case.

It does the O(history) method for correctness at the expense of
efficiency; my hope is that a bit of caching can fix the efficiency issue
as well. So the question is not really "not safe" as "slow". Of course, it
takes a while for this to become an issue, given the relationship of
remote access latency to local access bandwidth. That is, you need a
really big history and to be getting very little new data before you'll
complain.

> JM> (Or, if you'd like, I can rework pull.c to use the
> JM>  verification-before-store technique I used in my git-daemon patch, so
> JM>  all the *-pull mechanisms will be 'safe')
> 
> I would appreciate the offer.  I, however, would have to warn
> you that the "problem" lies in the way the current pull
> structure devides responsibility between the pull.c and transfer
> backends.  The pull.c implements the dependency logic, and
> transfer backends are to populate the database while being
> oblivious of that logic.  From the purist point of view (I am
> sympathetic to your "place only the verified objects in the
> database" principle), I am not entirely happy with that
> division, but at the same time I understand why it is done that
> way and even like it from practical standpoint.

At one point I'd written a patch that split out the tmpfile usage of
write_sha1_file(), made the filenames predictable, and used it for
everything that writes those files. It had an "open" part and a
"close" part (where the close also moved the file into place). This would
give the code better atomicity and protect against races between reading
and validation. On the other hand, there's no reason to use an anonymous
temp file; just <filename>.partial or similar (with the proper open
flags) would be sufficient and easier to clean or commit. Note that we
want to support /tmp and the object directory being on different
filesystems, also. (And all the open and place logic is nicely wrapped up
in sha1_file.c)

Aside from the question of whether we want to insist that the object
database only includes objects such that everything reachable is also
present, we certainly want to only include objects which we have
completely fetched, which are generically well-formed, and which have the
advertized hash, and having there never be an unvalidated file at the
filename would be good.

By this reasoning, a file should only be renamed after all of the delta
requirements are satisfied, but before tree and commit requirements are
satisfied. We certainly aren't going to have much use for files whose
contents we cannot get. This means that we'd like to have multiple
unplaced files, but we don't need to read the contents of an unplaced
file.

	-Daniel
*This .sig left intentionally blank*

Database consistency after a successful pull

[McMullan, Jason]

[-- Attachment #1: Type: text/plain, Size: 1146 bytes --]

Subject Was: [PATCH] pull: gracefu[PAlly recover from delta retrieval
failure.]

[snip lots of really good information about the thinking
 behind the design of the pull mechanisms ]

Ok, so would I be correct in the following assumptions
about the validity of a 'consistent' .git/objects database:

============================================================

Commits:
	* May have the tree they refer to in the database
	* Must have their parents in the database

Trees:
	* Must have the blobs they refer to in the database
	* Must have the trees they refer to in the database

Deltas:
	* Must have the referred to object in the database

Blobs:
	* No references to check


============================================================

In short, the database would contain:

	* The entire commit history
	* Selected commits would have the entire tree available

Correct, or totally mistaken? If mistaken, what are the consitency
rules?

[Oh, and does PGP signing my messages bug anybody? If so, I can stop
 doing that on this list]

-- 
Jason McMullan <jason.mcmullan@timesys.com>
TimeSys Corporation


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: Database consistency after a successful pull

[Daniel Barkalow]

On Mon, 6 Jun 2005, McMullan, Jason wrote:

> Subject Was: [PATCH] pull: gracefu[PAlly recover from delta retrieval
> failure.]
> 
> [snip lots of really good information about the thinking
>  behind the design of the pull mechanisms ]
> 
> Ok, so would I be correct in the following assumptions
> about the validity of a 'consistent' .git/objects database:
> 
> ============================================================
> 
> Commits:
> 	* May have the tree they refer to in the database
> 	* Must have their parents in the database

May have their parents in the database; we want to be able to drop ancient
history from non-archival sites at some point, if nothing else.

> Trees:
> 	* Must have the blobs they refer to in the database
> 	* Must have the trees they refer to in the database

It's probably true that there's no point to having a tree available if you
don't have its contents, although that's a convenient intermediate stage,
so that you can look up the contents of the tree with the ordinary parsing
code. On the other hand, I could imagine an ARM developer completely
ignoring arch/i386 (and just having write-tree use the parent tree's value
for it).

> Deltas:
> 	* Must have the referred to object in the database

Yes. Can't unpack without them.

> Blobs:
> 	* No references to check

Right.

Also, tags reference objects of unknown type; it's probably not vital to
have the object.

My bias is to call a database consistent with only deltas having the
referents; the rest goes towards completeness, since you have and can read
everything that you have anything for (but may not be able to do some
particular operation).

	-Daniel
*This .sig left intentionally blank*

Re: Database consistency after a successful pull

[McMullan, Jason]

[-- Attachment #1: Type: text/plain, Size: 532 bytes --]

On Mon, 2005-06-06 at 12:21 -0400, Daniel Barkalow wrote:
> [snip snip]
>
> My bias is to call a database consistent with only deltas having the
> referents; the rest goes towards completeness, since you have and can read
> everything that you have anything for (but may not be able to do some
> particular operation).

Now, if we had consistent URIs for the .git/branches/* files, we could
do 'lazy-pull' and really have our cake and eat it too.

-- 
Jason McMullan <jason.mcmullan@timesys.com>
TimeSys Corporation


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]