resumable git-clone?

resumable git-clone?

[Nguyen Thai Ngoc Duy]

I was on a crappy connection and it was frustrated seeing git-clone
reached 80% then failed, then started over again. Can we support
resumable git-clone at some level? I think we could split into several
small packs, keep fetched ones, just get missing packs until we have
all.
I didn't clone via http so I don't know if http supports resumable.
-- 
Duy

Re: resumable git-clone?

[Shawn O. Pearce]

Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
> I was on a crappy connection and it was frustrated seeing git-clone
> reached 80% then failed, then started over again. Can we support
> resumable git-clone at some level? I think we could split into several
> small packs, keep fetched ones, just get missing packs until we have
> all.

This is uh, difficult over the native git protocol.  The problem
is the native protocol negotiates what the client already has and
what it needs by comparing sets of commits.  If the client says
"I have commit X" then the server assumes it has not only commit
X _but also every object reachable from it_.

Now packfiles are organized to place commits at the front of the
packfile.  So a truncated download will give the client a whole
host of commits, like maybe all of them, but none of the trees
or blobs associated with them as those come behind the commits.
Worse, the commits are sorted most recent to least recent.  So if
the client claims he has the very first commit he received, that
is currently an assertion that he has the entire repository.

I have been thinking about this resumable fetch idea for the native
protocol for a few days now, like since the last time it came up
on #git.

One possiblity is to have the client store locally in a temporary
file the list of wants and the list of haves it sent to the server
during the last fetch.

During a resume of a packfile download we actually just replay this
list of wants/haves, even if the server has newer data.  We also tell
the server which object we last successfully downloaded (its SHA-1).

The server would only accept the resumed want list if all of the
wants are reachable from its current refs.  If one or more aren't
then they are just culled from the want list; this way you can still
successfully resume a download of say git.git where pu rebases often.
You just might not get pu without going back for it.

If the server always performs a very stable (meaning we don't ever
change the sorting order!) and deterministic sorting of the objects
in the packfile then given the same list of wants/haves and a
"prior" point it can pickup from where it left off.

At worst we are retransmitting one whole object again, e.g. the
client had all but the last byte of the object, so it was no good.
I'm willing to say we do the full object retransmission in case the
object was recompressed on the server between the first fetch and
the second.  It just simplifies the restart.

Probably not that difficult.  The hardest part is committing to the
object sorting order so that when we ask for a restart we *know*
we didn't miss an object.

> I didn't clone via http so I don't know if http supports resumable.

This would have a better chance at doing a resume.  Looking at the
code it looks like we do in fact resume a packfile download if it
was truncated.

-- 
Shawn.

Re: resumable git-clone?

[Johannes Schindelin]

Hi,

On Tue, 7 Aug 2007, Shawn O. Pearce wrote:

> Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
> > I was on a crappy connection and it was frustrated seeing git-clone
> > reached 80% then failed, then started over again. Can we support
> > resumable git-clone at some level? I think we could split into several
> > small packs, keep fetched ones, just get missing packs until we have
> > all.
> 
> This is uh, difficult over the native git protocol.  The problem
> is the native protocol negotiates what the client already has and
> what it needs by comparing sets of commits.  If the client says
> "I have commit X" then the server assumes it has not only commit
> X _but also every object reachable from it_.

Now here is a thought: after an interrupted fetch, you could do a 
(possibly expensive) analysis what commits are dangling, but do not 
contain broken links in their _complete_ history.  Then mark them as 
(temporary) refs.

Another possibility should be to start with a shallow clone, and to deepen 
it.  However, IIRC there have been complaints that that does not work, and 
it was not my itch, so I did not come around to scratch it.

Ciao,
Dscho

Re: resumable git-clone?

[Junio C Hamano]

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

> Now here is a thought: after an interrupted fetch, you could do a 
> (possibly expensive) analysis what commits are dangling, but do not 
> contain broken links in their _complete_ history.  Then mark them as 
> (temporary) refs.

That's all too elaborate and sounds fairly expensive.

I think another practical solution is to reduce the need to
resume git-clone, and I foresee a nice side effect.

Let's talk a bit about the side effect first.  Often I see
people wondering...

 - I am forking off of somebody's big project;

 - I want to publish the result of _my_ part of the work;

 - I cannot afford the diskspace nor the bandwidth at the
   hosting service to offer the whole project, but my own work
   on top of the upstream is small enough;

So I've been thinking about teaching the server side, when
responding to a fetch request, to be able to say something like
"Sorry but this repository is for fetching by people who have at
least these commits from that other project I am a fork of."
We make that "at least these from that other project" part
machine readable, and git-fetch request git-clone makes can
redirect itself to fill the prerequisites before attempting to
go there again.

And one way of doing that "at least these commits" part could be
a pre-built, well known bundle.  The bulk of the older history
of a repository insanely large for your bandwidth requirements
could be made to a single bundle [*1*], and distributed from
other places like mirrored HTTP servers, or even from torrent
network.  The pre-built bundle does not have to be built too
often.  Probably after every other big release would do.

Once we have such a support, cloning from a regular full
repository ove an unreliable connection could fall back on
getting a bundle (a regular repository does not have to refuse
to serve downloaders that do not have the prerequisites, but
it could still suggest that as an alternate method to fall back
on.


[Footnote]

*1* Sheesh.  While I was writing this I noticed that the current
    'git bundle' is suitable only for incremental sneakernet but
    not for this particular use case.

    $ git bundle create 2612.bndl v2.6.12

    does not work, although

    $ git bundle create 2612-2613.bndl v2.6.12..v2.6.13

    does.  We need to fix this.

Re: resumable git-clone?

[Johannes Schindelin]

Hi,

On Wed, 8 Aug 2007, Junio C Hamano wrote:

> So I've been thinking about teaching the server side, when responding to 
> a fetch request, to be able to say something like "Sorry but this 
> repository is for fetching by people who have at least these commits 
> from that other project I am a fork of." We make that "at least these 
> from that other project" part machine readable, and git-fetch request 
> git-clone makes can redirect itself to fill the prerequisites before 
> attempting to go there again.

Something like the alternates that http transport can use?

> *1* Sheesh.  While I was writing this I noticed that the current
>     'git bundle' is suitable only for incremental sneakernet but
>     not for this particular use case.
> 
>     $ git bundle create 2612.bndl v2.6.12
> 
>     does not work, although
> 
>     $ git bundle create 2612-2613.bndl v2.6.12..v2.6.13
> 
>     does.  We need to fix this.

Yes, I noticed this a long time ago.  Time is lacking...

Ciao,
Dscho

[PATCH] allow git-bundle to create bottomless bundle

[Junio C Hamano]

While "git bundle" was a useful way to sneakernet incremental
changes, we did not allow:

	$ git bundle create v2.6.20.bndl v2.6.20

to create a bundle that contains the whole history to a
well-known good revision.  Such a bundle can be mirrored
everywhere, and people can prime their repository with it to
reduce the load on the repository that serves near the tip of
the development.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

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

 > *1* Sheesh.  While I was writing this I noticed that the current
 >     'git bundle' is suitable only for incremental sneakernet but
 >     not for this particular use case.
 >
 >     $ git bundle create 2612.bndl v2.6.12
 >
 >     does not work, although
 >
 >     $ git bundle create 2612-2613.bndl v2.6.12..v2.6.13
 >
 >     does.  We need to fix this.

 Only very lightly tested, but the fix looks obvious enough.

 builtin-bundle.c |   10 +++++++++-
 t/t5510-fetch.sh |    8 ++++++++
 2 files changed, 17 insertions(+), 1 deletions(-)

diff --git a/builtin-bundle.c b/builtin-bundle.c
index 6ae5ab0..cb439ca 100644
--- a/builtin-bundle.c
+++ b/builtin-bundle.c
@@ -208,6 +208,10 @@ static int create_bundle(struct bundle_header *header, const char *path,
 	struct rev_info revs;
 	struct child_process rls;
 
+	/*
+	 * NEEDSWORK: this should use something like lock-file
+	 * to create temporary that is cleaned up upon error.
+	 */
 	bundle_fd = (!strcmp(path, "-") ? 1 :
 			open(path, O_CREAT | O_EXCL | O_WRONLY, 0666));
 	if (bundle_fd < 0)
@@ -267,8 +271,12 @@ static int create_bundle(struct bundle_header *header, const char *path,
 		 * Make sure the refs we wrote out is correct; --max-count and
 		 * other limiting options could have prevented all the tips
 		 * from getting output.
+		 *
+		 * Non commit objects such as tags and blobs do not have
+		 * this issue as they are not affected by those extra
+		 * constraints.
 		 */
-		if (!(e->item->flags & SHOWN)) {
+		if (!(e->item->flags & SHOWN) && e->item->type == OBJ_COMMIT) {
 			warning("ref '%s' is excluded by the rev-list options",
 				e->name);
 			continue;
diff --git a/t/t5510-fetch.sh b/t/t5510-fetch.sh
index 426017e..439430f 100755
--- a/t/t5510-fetch.sh
+++ b/t/t5510-fetch.sh
@@ -145,4 +145,12 @@ test_expect_success 'bundle does not prerequisite objects' '
 	test 4 = $(git verify-pack -v bundle.pack | wc -l)
 '
 
+test_expect_success 'bundle should be able to create a full history' '
+
+	cd "$D" &&
+	git tag -a -m '1.0' v1.0 master &&
+	git bundle create bundle4 v1.0
+
+'
+
 test_done

Re: [PATCH] allow git-bundle to create bottomless bundle

[Johannes Schindelin]

Hi,

On Wed, 8 Aug 2007, Junio C Hamano wrote:

> +		 *
> +		 * Non commit objects such as tags and blobs do not have
> +		 * this issue as they are not affected by those extra
> +		 * constraints.
>  		 */
> -		if (!(e->item->flags & SHOWN)) {
> +		if (!(e->item->flags & SHOWN) && e->item->type == OBJ_COMMIT) {

That is all?  Heh.

Thanks for fixing this bug,
Dscho

Re: [PATCH] allow git-bundle to create bottomless bundle

[Mark Levedahl]

Junio C Hamano wrote:
> While "git bundle" was a useful way to sneakernet incremental
> changes, we did not allow:
>   
Thanks - I've been thinking for months I could fix this bug, never 
figured it out and didn't want to nag Dscho one more time. I confirm 
that this allows creation of bundles with arbitrary refs, not just those 
under refs/heads. Yahoo!

Mark

Re: [PATCH] allow git-bundle to create bottomless bundle

[Junio C Hamano]

Mark Levedahl <mlevedahl@gmail.com> writes:

> Junio C Hamano wrote:
>> While "git bundle" was a useful way to sneakernet incremental
>> changes, we did not allow:
>>
> Thanks - I've been thinking for months I could fix this bug, never
> figured it out and didn't want to nag Dscho one more time. I confirm
> that this allows creation of bundles with arbitrary refs, not just
> those under refs/heads. Yahoo!

Actually, there is another bug nearby.

If you do:

	git bundle create v2.6-20-v2.6.22.bndl v2.6.20..v2.6.22

the bundle records that it requires v2.6.20^0 commit (correct)
and gives you tag v2.6.22 (incorrect); the bug is that the
object it lists in fact is the commit v2.6.22^0, not the tag.

This is because the revision range operation .. is always about
set of commits, but the code near where my patch touches does
not validate that the sha1 value obtained from dwim_ref()
against the commit object name e->item->sha1 before placing the
head information in the commit.

The attached patch attempts to fix this problem.

---

 builtin-bundle.c |   43 ++++++++++++++++++++++++++++++++++++++++++-
 t/t5510-fetch.sh |    8 ++++++++
 2 files changed, 50 insertions(+), 1 deletions(-)

diff --git a/builtin-bundle.c b/builtin-bundle.c
index 6ae5ab0..2d0e106 100644
--- a/builtin-bundle.c
+++ b/builtin-bundle.c
@@ -208,6 +208,10 @@ static int create_bundle(struct bundle_header *header, const char *path,
 	struct rev_info revs;
 	struct child_process rls;
 
+	/*
+	 * NEEDSWORK: this should use something like lock-file
+	 * to create temporary that is cleaned up upon error.
+	 */
 	bundle_fd = (!strcmp(path, "-") ? 1 :
 			open(path, O_CREAT | O_EXCL | O_WRONLY, 0666));
 	if (bundle_fd < 0)
@@ -267,12 +271,49 @@ static int create_bundle(struct bundle_header *header, const char *path,
 		 * Make sure the refs we wrote out is correct; --max-count and
 		 * other limiting options could have prevented all the tips
 		 * from getting output.
+		 *
+		 * Non commit objects such as tags and blobs do not have
+		 * this issue as they are not affected by those extra
+		 * constraints.
 		 */
-		if (!(e->item->flags & SHOWN)) {
+		if (!(e->item->flags & SHOWN) && e->item->type == OBJ_COMMIT) {
 			warning("ref '%s' is excluded by the rev-list options",
 				e->name);
+			free(ref);
+			continue;
+		}
+		/*
+		 * If you run "git bundle create bndl v1.0..v2.0", the
+		 * name of the positive ref is "v2.0" but that is the
+		 * commit that is referenced by the tag, and not the tag
+		 * itself.
+		 */
+		if (hashcmp(sha1, e->item->sha1)) {
+			/*
+			 * Is this the positive end of a range expressed
+			 * in terms of a tag (e.g. v2.0 from the range
+			 * "v1.0..v2.0")?
+			 */
+			struct commit *one = lookup_commit_reference(sha1);
+			struct object *obj;
+
+			if (e->item == &(one->object)) {
+				/*
+				 * Need to include e->name as an
+				 * independent ref to the pack-objects
+				 * input, so that the tag is included
+				 * in the output; otherwise we would
+				 * end up triggering "empty bundle"
+				 * error.
+				 */
+				obj = parse_object(sha1);
+				obj->flags |= SHOWN;
+				add_pending_object(&revs, obj, e->name);
+			}
+			free(ref);
 			continue;
 		}
+
 		ref_count++;
 		write_or_die(bundle_fd, sha1_to_hex(e->item->sha1), 40);
 		write_or_die(bundle_fd, " ", 1);
diff --git a/t/t5510-fetch.sh b/t/t5510-fetch.sh
index 426017e..439430f 100755
--- a/t/t5510-fetch.sh
+++ b/t/t5510-fetch.sh
@@ -145,4 +145,12 @@ test_expect_success 'bundle does not prerequisite objects' '
 	test 4 = $(git verify-pack -v bundle.pack | wc -l)
 '
 
+test_expect_success 'bundle should be able to create a full history' '
+
+	cd "$D" &&
+	git tag -a -m '1.0' v1.0 master &&
+	git bundle create bundle4 v1.0
+
+'
+
 test_done

Re: [PATCH] allow git-bundle to create bottomless bundle

[Mark Levedahl]

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

On 8/9/07, Junio C Hamano <gitster@pobox.com> wrote:
> Mark Levedahl <mlevedahl@gmail.com> writes:
>
> > Junio C Hamano wrote:
>
> Actually, there is another bug nearby.
>
Curious... I did a long time ago get git-bundle.sh to write out the
format Dscho finally implemented working in Linux and Cygwin. With
your latest patch, both produce identical bundles for a number of
cases, but the timing is very curious:

*builtin*
git>time git-bundle create foo refs/tags/v1.0.3
Generating pack...
Done counting 12288 objects.
Deltifying 12288 objects...
 100% (12288/12288) done
Writing 12288 objects...
 100% (12288/12288) done
Total 12288 (delta 8435), reused 11542 (delta 7961)

real    0m41.953s
user    0m5.060s
sys     0m39.685s

*shell script*
git>time git-bundle2 create foo2 refs/tags/v1.0.3
Generating pack...
Done counting 12288 objects.
Deltifying 12288 objects...
 100% (12288/12288) done
Total 12288 (delta 8435), reused 11542 (delta 7961)
Created foo2

real    0m2.453s
user    0m1.842s
sys     0m1.190s
git>diff foo foo2
git>

Since when is shell 20 times faster than a builtin? Ok, those results
are on Cygwin. On Linux, I get  1.21 sec for the builtin vs 0.933 for
the shell script. Not as dramatic, but the script is still faster. So,
I think this qualifies as a bug. I'm attaching the script (for info
only, I'm not suggesting to replace the builtin), as I can't usefully
put it inline from gmail.

The timing difference seem to be in the rev walking (by eyeball,
packfile generation time is the same), so something the shell script
is doing to get the rev list is obviously more efficient than how the
builtin works for this case.

Mark

[-- Attachment #2: git-bundle2 --]
[-- Type: application/octet-stream, Size: 4705 bytes --]

#!/bin/sh
# Basic handler for bundle files to connect repositories via sneakernet.
# Invocation must include action.
# This function can create a bundle or provide information on an existing bundle
# supporting git-fetch, git-pull, and git-ls-remote

# bundle format is:
# line1 - version
# -sha1 commit msg  : prerequisites
# sha1 name         ; refs
# <blank line>
# pack file

USAGE='git-bundle ( create <bundle> [<rev-list-args>...] |
         verify | list-heads | unbundle <bundle> )'

SUBDIRECTORY_OK=1
. git-sh-setup
LF='
'

verify() {
    # Check bundle version
    test "$version" = "# v2 git bundle" ||
        die "$bfile is not a v2 git bundle"

    # do fast check, then if any prereqs are missing then go line by line
    # to be verbose about the errors
    test -z "$prereqs" && return 0
    if bad=$(echo "$prereqs" | cut -b-40 | git-rev-list --stdin --not --all 2>&1) &&
    test -z "$bad" ; then
        return 0
    else
        echo >/dev/stderr "error: $bfile requires the following missing commits:"
        echo "$prereqs" |
        while read sha1 comment ; do
            if ! missing=$(git-rev-list $sha1 --not --all 2>&1) || test -n "$missing" ; then
                echo >/dev/stderr "$sha1 $comment"
            fi
        done
        return 1
    fi
}

# list all refs or just a subset
list_heads() {
    if test -z "$*" ; then
        echo "$refs"
    else
        echo "$refs" |
        while read sha1 ref ; do
            for arg in $* ; do
                if test "${ref%$arg}" != "$ref" ; then
                    echo "$sha1 $ref"
                    break
                fi
            done
        done
    fi
}

# create a bundle
create() {
    unknown=$(git-rev-parse --no-revs $args)
    test -z "$unknown" || die "unknown option: $unknown"
    gitrevargs=$(git-rev-parse --symbolic --revs-only $args) || exit 1

    # find the refs to carry along and get sha1s for each.
    refs=
    boundaryargs=
    basis=
    for arg in $gitrevargs ; do
        #ignore options and basis refs, get full ref name for things
        # we will transport rejecting anything ambiguous (e.g., user
        # gives master, have heads/master and remotes/origin/master, we
        # keep the former).
        case "$arg" in
            ^*)
                boundaryargs="$boundaryargs $arg"
                basis="$basis ${arg/^/}";;
            -*)
                boundaryargs="$boundaryargs $arg";;
            *)
                refs="$refs$LF$(git show-ref $arg | head -n1)";;
        esac
    done
    test -z "$refs" && die "No references specified, I don't know what to bundle."
	sha1refs=$(echo "$refs" | cut -b-40)

    # get prerequisite commits this bundle depends upon
    prereqs=$(git-rev-list --boundary $boundaryargs $sha1refs | sed -ne 's/^-//p')
    if test -n "$basis" ; then
        prereqs=$(printf "%s\n" $prereqs $(git-rev-parse $basis) | sort | uniq)
    fi
	
    # create refs and pack. We do this in a subshell to avoid using >> to append,
    # as that induces crlf breakage under Cygwin.
    (
        echo "# v2 git bundle" &&
        (for p in $prereqs ; do
            printf "%s\n" "-$(git-rev-list --pretty=one --max-count=1 $p)"
        done) &&
        git-show-ref $refs &&
        echo "" &&
        (printf "%s\n" $sha1refs &&
        test -n "$prereqs" && printf "^%s\n" $prereqs ) |
        git pack-objects --thin --stdout --progress
    ) > "$bfile"
    if test $? -gt 0; then
        rm -fv "$bfile"
    else
        echo "Created $bfile"
    fi
}

# parse inputs, decide what to do
args=
action=
while test -n "$1" ; do
    case $1 in
        create|list-heads|unbundle|verify|show)
            action=$1
            shift
            bfile=$1
            test -z "$bfile" && die "$action requires filename";;
        *)
            args="$args $1";;
    esac
    shift
done
test -z "$action" && die "No action given, what should I do?"

if test "$action" = "create" ; then
    create
else
    test -f "$bfile" || die "Could not find $bfile"

    # get the header once, verify all is ok
    header=$(sed -e '/^$/,$d' "$bfile")
    refs=$(echo "$header" | sed -e '1d;/^-/d')
    prereqs=$(echo "$header" | sed -ne 's/^-//p')
    version=$(echo "$header" | head -n1)

    echo $version

    case $action in
        verify)
            verify && echo "$bfile is ok";;

        list-heads)
            list_heads $args;;

        show)
            echo "$header" | sed -ne "/^-/p"
            echo "$refs";;

        unbundle)
            verify || exit 1
            sed -be '1,/^$/d' "$bfile" | git-index-pack --stdin --fix-thin ||
                die "error: $bfile has a corrupted pack file"
            list_heads $args;;
    esac
fi

Re: resumable git-clone?

[Nguyen Thai Ngoc Duy]

On 8/7/07, Shawn O. Pearce <spearce@spearce.org> wrote:
> Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
> > I was on a crappy connection and it was frustrated seeing git-clone
> > reached 80% then failed, then started over again. Can we support
> > resumable git-clone at some level? I think we could split into several
> > small packs, keep fetched ones, just get missing packs until we have
> > all.
>
> This is uh, difficult over the native git protocol.  The problem
> is the native protocol negotiates what the client already has and
> what it needs by comparing sets of commits.  If the client says
> "I have commit X" then the server assumes it has not only commit
> X _but also every object reachable from it_.
>
> Now packfiles are organized to place commits at the front of the
> packfile.  So a truncated download will give the client a whole
> host of commits, like maybe all of them, but none of the trees
> or blobs associated with them as those come behind the commits.
> Worse, the commits are sorted most recent to least recent.  So if
> the client claims he has the very first commit he received, that
> is currently an assertion that he has the entire repository.

I'm thinking about things like bisect and use it to cut the history
into parts. Clients only use completed parts. Uncompleted parts are
thrown away. So if users think they cannot suffer too big packs, they
tell server to send smaller (and less efficient) packs. Anyway I don't
have deep knowledge of Git internals, my opion could be completely
wrong.
-- 
Duy