[PATCH] Do not call git-rev-list from git-fetch-pack

[PATCH] Do not call git-rev-list from git-fetch-pack

[Johannes Schindelin]

It is much easier to avoid sending unneeded data when putting the rev list
together in a customized manner. In particular, the tips of the local
branches are sent first, and only then their ancestors.

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>

---

	This supersedes my earlier attempt. SHA1s of tags are no longer
	sent via "have" lines. This makes the code much simpler. Also,
	it does not buy us much to send them:

	Either we have the tag object already, pointed to by a ref (thus 
	not "want"ing it in the first place), or we fetch at most
	a couple of tag objects we already have.

 fetch-pack.c |  139 ++++++++++++++++++++++++++++++++++++++++++++--------------
 1 files changed, 106 insertions(+), 33 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 8566ab1..260de90 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -13,18 +13,102 @@ static const char fetch_pack_usage[] =
 static const char *exec = "git-upload-pack";
 
 #define COMPLETE	(1U << 0)
+#define COMMON		(1U << 1)
+#define COMMON_REF	(1U << 2)
+#define SEEN		(1U << 3)
+
+struct commit_list *rev_list = NULL;
+
+static int rev_list_insert(const char *path, const unsigned char *sha1)
+{
+	struct object *o = deref_tag(parse_object(sha1));
+
+	/*
+	   The real problem is that find_common will stop very soon
+	   after seeing a common revision.
+
+	   However, that does not always make sense. Example:
+
+	   Branch1 has 40 commits since it last merged with branch2,
+	   and branch2 has 2 more commits since then.
+
+	   On the other end, branch1 is up-to-date, but branch2 is not.
+	   When fetching branch1, the 40 commits get sent, the first
+	   is acknowledged as common, and the local head of branch2
+	   never gets sent.
+
+	   As a consequence, the whole history of branch2
+	   (git-rev-list branch2 ^branch1) gets packed and transmitted.
+
+	   The workaround is to pretend that the tips of the local
+	   branches are 10 years younger, so that they are sent before
+	   everything else.
+	*/
+
+	if (o->type == commit_type && !(o->flags & SEEN)) {
+		struct commit *commit = (struct commit *)o;
+		o->flags |= SEEN;
+		/* The head's tips get handled before everything else. */
+		commit->date += 10*365*86400;
+		insert_by_date(commit, &rev_list);
+	}
+
+	return 0;
+}
+
+/*
+  Get the next rev to send, ignoring the common.
+*/
+
+static const unsigned char* get_rev()
+{
+	struct commit *commit = NULL;
+
+	while (commit == NULL) {
+		unsigned int mark;
+
+		if (rev_list == NULL)
+			return NULL;
+
+		commit = rev_list->item;
+
+		if (commit->object.flags & COMMON) {
+			/* do not send "have", and ignore ancestors */
+			commit = NULL;
+			mark = COMMON | SEEN;
+		} else if (commit->object.flags & COMMON_REF)
+			/* send "have", and ignore ancestors */
+			mark = COMMON | SEEN;
+		else
+			/* send "have", also for its ancestors */
+			mark = SEEN;
+
+		pop_most_recent_commit(&rev_list, mark);
+	}
+
+	return commit->object.sha1;
+}
+
+static void mark_common(const unsigned char* sha1)
+{
+	struct object *o = lookup_object(sha1);
+
+	if (o != NULL && !(o->flags & COMMON)) {
+		o->flags |= COMMON;
+		if (o->type == commit_type)
+			insert_by_date((struct commit *)o, &rev_list);
+	}
+}
 
 static int find_common(int fd[2], unsigned char *result_sha1,
 		       struct ref *refs)
 {
 	int fetching;
-	static char line[1000];
-	static char rev_command[1024];
-	int count = 0, flushes = 0, retval, rev_command_len;
-	FILE *revs;
+	int count = 0, flushes = 0, retval;
+	const unsigned char *sha1;
+
+	for_each_ref(rev_list_insert);
 
-	strcpy(rev_command, "git-rev-list $(git-rev-parse --all)");
-	rev_command_len = strlen(rev_command);
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {
 		unsigned char *remote = refs->old_sha1;
@@ -42,25 +126,17 @@ static int find_common(int fd[2], unsign
 		 */
 		if (((o = lookup_object(remote)) != NULL) &&
 		    (o->flags & COMPLETE)) {
-			struct commit_list *p;
-			struct commit *commit =
-				(struct commit *) (o = deref_tag(o));
-			if (!o)
-				goto repair;
-			if (o->type != commit_type)
-				continue;
-			p = commit->parents;
-			while (p &&
-			       rev_command_len + 44 < sizeof(rev_command)) {
-				snprintf(rev_command + rev_command_len, 44,
-					 " ^%s",
-					 sha1_to_hex(p->item->object.sha1));
-				rev_command_len += 43;
-				p = p->next;
+			o = deref_tag(o);
+			o->flags |= COMMON_REF;
+
+			if (o->type == commit_type && !(o->flags & SEEN)) {
+				o->flags |= SEEN;
+				insert_by_date((struct commit *)o, &rev_list);
 			}
+
 			continue;
 		}
-	repair:
+
 		packet_write(fd[1], "want %s\n", sha1_to_hex(remote));
 		fetching++;
 	}
@@ -68,21 +144,16 @@ static int find_common(int fd[2], unsign
 	if (!fetching)
 		return 1;
 
-	revs = popen(rev_command, "r");
-	if (!revs)
-		die("unable to run 'git-rev-list'");
-
 	flushes = 1;
 	retval = -1;
-	while (fgets(line, sizeof(line), revs) != NULL) {
-		unsigned char sha1[20];
-		if (get_sha1_hex(line, sha1))
-			die("git-fetch-pack: expected object name, got crud");
+	while ((sha1 = get_rev())) {
 		packet_write(fd[1], "have %s\n", sha1_to_hex(sha1));
 		if (verbose)
 			fprintf(stderr, "have %s\n", sha1_to_hex(sha1));
 		if (!(31 & ++count)) {
 			packet_flush(fd[1]);
+			if (verbose)
+				fprintf(stderr, "flush\n");
 			flushes++;
 
 			/*
@@ -92,16 +163,17 @@ static int find_common(int fd[2], unsign
 			if (count == 32)
 				continue;
 			if (get_ack(fd[0], result_sha1)) {
+				mark_common(result_sha1);
 				flushes = 0;
 				retval = 0;
 				if (verbose)
-					fprintf(stderr, "got ack\n");
+					fprintf(stderr, "got ack %s\n",
+						sha1_to_hex(result_sha1));
 				break;
 			}
 			flushes--;
 		}
 	}
-	pclose(revs);
 	packet_write(fd[1], "done\n");
 	if (verbose)
 		fprintf(stderr, "done\n");
@@ -109,7 +181,8 @@ static int find_common(int fd[2], unsign
 		flushes--;
 		if (get_ack(fd[0], result_sha1)) {
 			if (verbose)
-				fprintf(stderr, "got ack\n");
+				fprintf(stderr, "got ack %s\n",
+					sha1_to_hex(result_sha1));
 			return 0;
 		}
 	}

Re: [PATCH] Do not call git-rev-list from git-fetch-pack

[Junio C Hamano]

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

> +	   Branch1 has 40 commits since it last merged with branch2,
> +	   and branch2 has 2 more commits since then.
> +
> +	   On the other end, branch1 is up-to-date, but branch2 is not.
> +	   When fetching branch1, the 40 commits get sent, the first
> +	   is acknowledged as common, and the local head of branch2
> +	   never gets sent.
> +
> +	   As a consequence, the whole history of branch2
> +	   (git-rev-list branch2 ^branch1) gets packed and transmitted.

Arrrgggggggh.  The description above captures the essense of the
problem very well, but faking dates and still popping by recency
looks like a really ugly hack to me.

Wouldn't it be cleaner if you traversed commits starting from
local refs, and assign distance from the tip of the branch to
each object (use generic object->util field for it), and
maintain an object_list that is sorted by depth, similar to
commit_list sorted by commit date?  Then you can pop from the
list by depth, closer to tip first, and tell the other end that
you have branch1, branch2, branch1^, branch2^, branch1~2,
branch2~1,...  which is the order the above situation benefits
from.

Re: [PATCH] Do not call git-rev-list from git-fetch-pack

[Johannes Schindelin]

Hi,

On Fri, 21 Oct 2005, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > +	   Branch1 has 40 commits since it last merged with branch2,
> > +	   and branch2 has 2 more commits since then.
> > +
> > +	   On the other end, branch1 is up-to-date, but branch2 is not.
> > +	   When fetching branch1, the 40 commits get sent, the first
> > +	   is acknowledged as common, and the local head of branch2
> > +	   never gets sent.
> > +
> > +	   As a consequence, the whole history of branch2
> > +	   (git-rev-list branch2 ^branch1) gets packed and transmitted.
> 
> Arrrgggggggh.  The description above captures the essense of the
> problem very well, but faking dates and still popping by recency
> looks like a really ugly hack to me.

It is ugly. But it is a good heuristic. And the code is simple, because I 
could use the existing functions for inserting into a commit_list.

> Wouldn't it be cleaner if you traversed commits starting from
> local refs, and assign distance from the tip of the branch to
> each object (use generic object->util field for it), and
> maintain an object_list that is sorted by depth, similar to
> commit_list sorted by commit date?  Then you can pop from the
> list by depth, closer to tip first, and tell the other end that
> you have branch1, branch2, branch1^, branch2^, branch1~2,
> branch2~1,...  which is the order the above situation benefits
> from.

I have an example from the real world why this is bad as well: I have a 
repository imported from CVS, which has this silly CVS initial import 
marked as it's own branch. This was long, long, long ago, but 
git-cvsimport faithfully creates the branch "initial" for it anyway.

Imagine now the case that I added 40 revisions locally between the last 
fetch and now. What would happen is this:

In both cases, your git-fetch-pack and mine, the tips would get sent, the 
(very old one) "initial" acknowledged. A few of those 40 revisions would 
get sent, too, (and in your case, the root rev), but not at all the 
optimal merge base. In essence, almost all would get sent again.

How about this on top of your idea:

Send only those branch{i}^n where n is a power of 2. This is a tradeoff 
between the speed we find sensible common revs, and the accurateness of 
the best pick.

Note that the best thing would probably be to add a binary search to that, 
and *not* stop at the first ack'ed rev, but rather count them, and stop at 
MAX_HAS.

Ciao,
Dscho

Re: [PATCH] Do not call git-rev-list from git-fetch-pack

[Junio C Hamano]

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

> Note that the best thing would probably be to add a binary search to that, 
> and *not* stop at the first ack'ed rev, but rather count them, and stop at 
> MAX_HAS.

Another alternative.

We send "haves" in order, without 2^n skipping nor binary search
backtrack.  Instead, add a logic in upload-pack to see if a
newly arrived "have" is a direct child of anything that we have
already heard about, and mark to ignore them.  We need to add
that MAX_HAS counting to fetch-pack side for this to work.

This is not even compile tested, but just to outline the idea.

(... now off to day-job ...)

---

diff --git a/upload-pack.c b/upload-pack.c
index 8a41caf..d98a28e 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -3,9 +3,11 @@
 #include "pkt-line.h"
 #include "tag.h"
 #include "object.h"
+#include "commit.h"
 
 static const char upload_pack_usage[] = "git-upload-pack [--strict] [--timeout=nn] <dir>";
 
+#define THEY_HAVE (1U << 0)
 #define MAX_HAS (16)
 #define MAX_NEEDS (256)
 static int nr_has = 0, nr_needs = 0;
@@ -92,6 +94,20 @@ static int got_sha1(char *hex, unsigned 
 		return 0;
 	nr = nr_has;
 	if (nr < MAX_HAS) {
+		struct object *o = lookup_object(sha1);
+		if (!o || (o->parsed || !parse_object(sha1)))
+			die("oops");
+		if (o->type == commit_type) {
+			struct commit_list *parents;
+			if (o->flags & THEY_HAVE)
+				return 0;
+			o->flags |= THEY_HAVE;
+			for (parents = ((struct commit*)o)->parents;
+			     parents;
+			     parents = parents->next) {
+				parents->item->object.flags |= THEY_HAVE;
+			}
+		}
 		memcpy(has_sha1[nr], sha1, 20);
 		nr_has = nr+1;
 	}
@@ -104,6 +120,9 @@ static int get_common_commits(void)
 	unsigned char sha1[20];
 	int len;
 
+	track_object_refs = 0;
+	save_commit_buffer = 0;
+
 	for(;;) {
 		len = packet_read_line(0, line, sizeof(line));
 		reset_timeout();

Re: [PATCH] Do not call git-rev-list from git-fetch-pack

[Johannes Schindelin]

Hi,

On Fri, 21 Oct 2005, Junio C Hamano wrote:

> We send "haves" in order, without 2^n skipping nor binary search
> backtrack.  Instead, add a logic in upload-pack to see if a
> newly arrived "have" is a direct child of anything that we have
> already heard about, and mark to ignore them.  We need to add
> that MAX_HAS counting to fetch-pack side for this to work.

Yes. This makes it more simple, and is very efficient in the common case. 
How about increasing MAX_HAS to 64?

Adapted patch for fetch-pack coming soon.

Ciao,
Dscho

Re: [PATCH] Do not call git-rev-list from git-fetch-pack

[Junio C Hamano]

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

> Yes. This makes it more simple, and is very efficient in the common case. 
> How about increasing MAX_HAS to 64?

The other day I saw HPA tried to sneak in a change to increase
it to 64, mingled with other changes.  I think increasing it
makes sense.

Now the question is, if we count MAX_HAS on the fetch-pack side,
how would we coordinate that value with the real limit the other
end uses.  I guess that would not matter too much.  It would not
affect the correctness anyway.

Re: [PATCH] Do not call git-rev-list from git-fetch-pack

[Johannes Schindelin]

Hi,

On Fri, 21 Oct 2005, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > Yes. This makes it more simple, and is very efficient in the common case. 
> > How about increasing MAX_HAS to 64?
> 
> The other day I saw HPA tried to sneak in a change to increase
> it to 64, mingled with other changes.  I think increasing it
> makes sense.

Agree.

However, I do not see a way for upload-pack to force fetch-pack to send 
"have" lines. Maybe this would be an important change to the protocol? I 
imagine that I could craft a custom fetch-pack which DoS'es any 
current upload-pack.

> Now the question is, if we count MAX_HAS on the fetch-pack side,
> how would we coordinate that value with the real limit the other
> end uses.  I guess that would not matter too much.  It would not
> affect the correctness anyway.

Really, there should be a way for upload-pack to say that enough is 
enough, and it wants to send the pack now.

Ciao,
Dscho

Re: [PATCH] Do not call git-rev-list from git-fetch-pack

[Daniel Barkalow]

On Fri, 21 Oct 2005, Johannes Schindelin wrote:

> Hi,
> 
> On Fri, 21 Oct 2005, Junio C Hamano wrote:
> 
> > Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> > 
> > > +	   Branch1 has 40 commits since it last merged with branch2,
> > > +	   and branch2 has 2 more commits since then.
> > > +
> > > +	   On the other end, branch1 is up-to-date, but branch2 is not.
> > > +	   When fetching branch1, the 40 commits get sent, the first
> > > +	   is acknowledged as common, and the local head of branch2
> > > +	   never gets sent.
> > > +
> > > +	   As a consequence, the whole history of branch2
> > > +	   (git-rev-list branch2 ^branch1) gets packed and transmitted.
> > 
> > Arrrgggggggh.  The description above captures the essense of the
> > problem very well, but faking dates and still popping by recency
> > looks like a really ugly hack to me.
> 
> It is ugly. But it is a good heuristic. And the code is simple, because I 
> could use the existing functions for inserting into a commit_list.

The existing functions aren't really very complicated. You could easily 
separate out the pop and the adding of parents, and go first through a 
list of tips and then through the date-sorted list of ancestors. And I 
think that separation would be useful for some changes Linus was making to 
rev-list recently.

	-Daniel
*This .sig left intentionally blank*

Re: [PATCH] Do not call git-rev-list from git-fetch-pack

[Johannes Schindelin]

Hi,

here comes a WIP on that patch (needs to be tested lots more):

 fetch-pack.c |  154 ++++++++++++++++++++++++++++++++++++++++++++--------------
 1 files changed, 117 insertions(+), 37 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 8566ab1..33ce435 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -13,18 +13,109 @@ static const char fetch_pack_usage[] =
 static const char *exec = "git-upload-pack";
 
 #define COMPLETE	(1U << 0)
+#define COMMON		(1U << 1)
+#define COMMON_REF	(1U << 2 | COMMON)
+#define SEEN		(1U << 3)
+#define POPPED		(1U << 4)
+#define MAX_HAS (16)
+
+static struct commit_list *rev_list = NULL;
+static struct commit_list *rev_list_end = NULL;
+static unsigned long non_common_revs = 0;
+
+static void rev_list_append(struct commit *commit, int mark)
+{
+	if (!(commit->object.flags & mark)) {
+		commit->object.flags |= mark;
+
+		if (rev_list == NULL) {
+			commit_list_insert(commit, &rev_list);
+			rev_list_end = rev_list;
+		} else {
+			commit_list_insert(commit, &(rev_list_end->next));
+			rev_list_end = rev_list_end->next;
+		}
+
+		if (!(commit->object.flags & COMMON))
+			non_common_revs++;
+	}
+}
+
+static int rev_list_append_sha1(const char *path, const unsigned char *sha1)
+{
+	struct object *o = deref_tag(parse_object(sha1));
+
+	if (o->type == commit_type)
+		rev_list_append((struct commit *)o, SEEN);
+
+	return 0;
+}
+
+static void mark_common(struct object *o)
+{
+	if (o != NULL && !(o->flags & COMMON)) {
+		o->flags |= COMMON;
+		if (!(o->flags & SEEN))
+			rev_list_append((struct commit *)o, SEEN);
+		else if (!(o->flags & POPPED))
+			non_common_revs--;
+	}
+}
+
+/*
+  Get the next rev to send, ignoring the common.
+*/
+
+static const unsigned char* get_rev()
+{
+	struct commit *commit = NULL;
+
+	while (commit == NULL) {
+		unsigned int mark;
+		struct commit_list* parents;
+
+		if (rev_list == NULL || non_common_revs == 0)
+			return NULL;
+
+		commit = rev_list->item;
+		commit->object.flags |= POPPED;
+		if (!(commit->object.flags & COMMON))
+			non_common_revs--;
+		
+		parents = commit->parents;
+
+		if (commit->object.flags & COMMON) {
+			/* do not send "have", and ignore ancestors */
+			commit = NULL;
+			mark = COMMON | SEEN;
+		} else if (commit->object.flags & COMMON_REF)
+			/* send "have", and ignore ancestors */
+			mark = COMMON | SEEN;
+		else
+			/* send "have", also for its ancestors */
+			mark = SEEN;
+
+		while (parents) {
+			if (mark & COMMON)
+				mark_common((struct object *)parents->item);
+			else
+				rev_list_append(parents->item, mark);
+			parents = parents->next;
+		}
+	}
+
+	return commit->object.sha1;
+}
 
 static int find_common(int fd[2], unsigned char *result_sha1,
 		       struct ref *refs)
 {
 	int fetching;
-	static char line[1000];
-	static char rev_command[1024];
-	int count = 0, flushes = 0, retval, rev_command_len;
-	FILE *revs;
+	int count = 0, flushes = 0, ack_count = 0, retval;
+	const unsigned char *sha1;
+
+	for_each_ref(rev_list_append_sha1);
 
-	strcpy(rev_command, "git-rev-list $(git-rev-parse --all)");
-	rev_command_len = strlen(rev_command);
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {
 		unsigned char *remote = refs->old_sha1;
@@ -42,25 +133,15 @@ static int find_common(int fd[2], unsign
 		 */
 		if (((o = lookup_object(remote)) != NULL) &&
 		    (o->flags & COMPLETE)) {
-			struct commit_list *p;
-			struct commit *commit =
-				(struct commit *) (o = deref_tag(o));
-			if (!o)
-				goto repair;
-			if (o->type != commit_type)
-				continue;
-			p = commit->parents;
-			while (p &&
-			       rev_command_len + 44 < sizeof(rev_command)) {
-				snprintf(rev_command + rev_command_len, 44,
-					 " ^%s",
-					 sha1_to_hex(p->item->object.sha1));
-				rev_command_len += 43;
-				p = p->next;
-			}
+			o = deref_tag(o);
+
+			if (o->type == commit_type)
+				rev_list_append((struct commit *)o,
+						COMMON_REF | SEEN);
+
 			continue;
 		}
-	repair:
+
 		packet_write(fd[1], "want %s\n", sha1_to_hex(remote));
 		fetching++;
 	}
@@ -68,21 +149,16 @@ static int find_common(int fd[2], unsign
 	if (!fetching)
 		return 1;
 
-	revs = popen(rev_command, "r");
-	if (!revs)
-		die("unable to run 'git-rev-list'");
-
 	flushes = 1;
 	retval = -1;
-	while (fgets(line, sizeof(line), revs) != NULL) {
-		unsigned char sha1[20];
-		if (get_sha1_hex(line, sha1))
-			die("git-fetch-pack: expected object name, got crud");
+	while ((sha1 = get_rev())) {
 		packet_write(fd[1], "have %s\n", sha1_to_hex(sha1));
 		if (verbose)
 			fprintf(stderr, "have %s\n", sha1_to_hex(sha1));
 		if (!(31 & ++count)) {
 			packet_flush(fd[1]);
+			if (verbose)
+				fprintf(stderr, "flush\n");
 			flushes++;
 
 			/*
@@ -92,16 +168,19 @@ static int find_common(int fd[2], unsign
 			if (count == 32)
 				continue;
 			if (get_ack(fd[0], result_sha1)) {
-				flushes = 0;
-				retval = 0;
+				mark_common(lookup_object(result_sha1));
 				if (verbose)
-					fprintf(stderr, "got ack\n");
-				break;
+					fprintf(stderr, "got ack %s\n",
+							sha1_to_hex(result_sha1));
+				if (++ack_count > MAX_HAS) {
+					flushes = 0;
+					retval = 0;
+					break;
+				}
 			}
 			flushes--;
 		}
 	}
-	pclose(revs);
 	packet_write(fd[1], "done\n");
 	if (verbose)
 		fprintf(stderr, "done\n");
@@ -109,7 +188,8 @@ static int find_common(int fd[2], unsign
 		flushes--;
 		if (get_ack(fd[0], result_sha1)) {
 			if (verbose)
-				fprintf(stderr, "got ack\n");
+				fprintf(stderr, "got ack %s\n",
+					sha1_to_hex(result_sha1));
 			return 0;
 		}
 	}