Re: Slow fetches of tags

@@ -18,6 +18,12 @@ #define COMMON_REF	(1U << 2)
 #define SEEN		(1U << 3)
 #define POPPED		(1U << 4)
 
+/*
+ * After sending this many "have"s if we do not get any new ACK , we
+ * give up traversing our history.
+ */
+#define MAX_IN_VAIN 256
+
 static struct commit_list *rev_list = NULL;
 static int non_common_revs = 0, multi_ack = 0, use_thin_pack = 0;
 

@@ -134,6 +140,8 @@ static int find_common(int fd[2], unsign
 	int fetching;
 	int count = 0, flushes = 0, retval;
 	const unsigned char *sha1;
+	unsigned in_vain = 0;
+	int got_continue = 0;
 
 	for_each_ref(rev_list_insert_ref);
 

@@ -172,6 +180,7 @@ static int find_common(int fd[2], unsign
 		packet_write(fd[1], "have %s\n", sha1_to_hex(sha1));
 		if (verbose)
 			fprintf(stderr, "have %s\n", sha1_to_hex(sha1));
+		in_vain++;
 		if (!(31 & ++count)) {
 			int ack;
 

@@ -200,9 +209,16 @@ static int find_common(int fd[2], unsign
 						lookup_commit(result_sha1);
 					mark_common(commit, 0, 1);
 					retval = 0;
+					in_vain = 0;
+					got_continue = 1;
 				}
 			} while (ack);
 			flushes--;
+			if (got_continue && MAX_IN_VAIN < in_vain) {
+				if (verbose)
+					fprintf(stderr, "giving up\n");
+				break; /* give up */
+			}
 		}
 	}
 done:

@@ -11,12 +11,18 @@ static const char upload_pack_usage[] = 
 #define THEY_HAVE (1U << 0)
 #define OUR_REF (1U << 1)
 #define WANTED (1U << 2)
+#define COMMON_KNOWN (1U << 3)
+
+#define TRACE_SEEN (1U << 4)
+#define TRACE_BASE 5
+#define MAX_TRACE 20 /* should not exceed bits_per_int - TRACE_BASE */
+
 #define MAX_HAS 256
 #define MAX_NEEDS 256
 static int nr_has = 0, nr_needs = 0, multi_ack = 0, nr_our_refs = 0;
 static int use_thin_pack = 0;
-static unsigned char has_sha1[MAX_HAS][20];
-static unsigned char needs_sha1[MAX_NEEDS][20];
+static struct object *has_sha1[MAX_HAS];
+static struct object *needs_sha1[MAX_NEEDS];
 static unsigned int timeout = 0;
 
 static void reset_timeout(void)

@@ -69,19 +75,22 @@ static void create_pack_file(void)
 		if (create_full_pack || MAX_NEEDS <= nr_needs)
 			*p++ = "--all";
 		else {
+			struct object **o = needs_sha1;
 			for (i = 0; i < nr_needs; i++) {
 				*p++ = buf;
-				memcpy(buf, sha1_to_hex(needs_sha1[i]), 41);
+				memcpy(buf, sha1_to_hex((*o++)->sha1), 41);
 				buf += 41;
 			}
 		}
-		if (!create_full_pack)
+		if (!create_full_pack) {
+			struct object **o = has_sha1;
 			for (i = 0; i < nr_has; i++) {
 				*p++ = buf;
 				*buf++ = '^';
-				memcpy(buf, sha1_to_hex(has_sha1[i]), 41);
+				memcpy(buf, sha1_to_hex((*o++)->sha1), 41);
 				buf += 41;
 			}
+		}
 		*p++ = NULL;
 		execv_git_cmd(argv);
 		die("git-upload-pack: unable to exec git-rev-list");

@@ -93,6 +102,125 @@ static void create_pack_file(void)
 	die("git-upload-pack: unable to exec git-pack-objects");
 }
 
+static int trace_want(struct object **trace, int cnt)
+{
+	/* start from these cnt objects, traverse the reachability
+	 * chain, without parsing new objects, to see if we can
+	 * reach objects they have.
+	 */
+	int i, j;
+	unsigned trace_flags = 0;
+	struct object_list *list = NULL;
+
+	for (i = 0; i < cnt; i++)
+		trace_flags |= (1U << (TRACE_BASE + i));
+
+	for (i = 0; i < obj_allocs; i++)
+		if (objs[i])
+			objs[i]->flags &= ~trace_flags;
+
+	for (i = 0; i < cnt; i++) {
+		trace[i]->flags |= 1U << (TRACE_BASE + i);
+		object_list_insert(trace[i], &list);
+	}
+
+	while (list) {
+		struct object_list *next = list->next;
+		struct object *o = list->item;
+		unsigned flags = o->flags & trace_flags;
+
+		free(list);
+		list = next;
+		if (o->flags & TRACE_SEEN)
+			continue;
+		o->flags |= TRACE_SEEN;
+		if (!strcmp(o->type, tag_type)) {
+			o = deref_tag(o, NULL, 0);
+			if (o && (o->flags & trace_flags) != flags) {
+				o->flags |= flags;
+				object_list_insert(o, &list);
+			}
+			continue;
+		}
+		if (!strcmp(o->type, commit_type)) {
+			struct commit *c = (struct commit *)o;
+			struct commit_list *l = c->parents;
+			while (l) {
+				struct commit *p = l->item;
+				l = l->next;
+				if ((p->object.flags & trace_flags) != flags) {
+					p->object.flags |= flags;
+					object_list_insert(&p->object, &list);
+				}
+			}
+		}
+	}
+
+	/* Now scan the objects they have, and see if the wanted one
+	 * reach which ones.
+	 */
+	for (j = 0; j < nr_needs; j++) {
+		for (i = 0;
+		     (i < nr_has &&
+		      !(needs_sha1[j]->flags & COMMON_KNOWN));
+		     i++) {
+			if (has_sha1[i]->flags & (1U << (TRACE_BASE + j)))
+				needs_sha1[j]->flags |= COMMON_KNOWN;
+		}
+	}
+
+	for (j = 0; j < nr_needs; j++) {
+		if (!(needs_sha1[j]->flags & COMMON_KNOWN))
+			return 1;
+	}
+	return 0;
+}
+
+static void check_want_heads(void)
+{
+	/* Do not keep saying "ack continue" if we already know
+	 * common ancestor for all the "want"ed heads.  This is
+	 * particularly important if some of the "have" heads does
+	 * not share any root commit with us.  Otherwise we would
+	 * keep asking for that branch, hoping we might get a better
+	 * common ancestor than we already have.
+	 */
+	int i, still_missing;
+	struct object *trace[MAX_TRACE];
+	int trace_bit;
+
+	if (!multi_ack)
+		return;
+
+	still_missing = 0;
+	trace_bit = 0;
+	for (i = 0; still_missing && i < nr_needs; i++) {
+		struct object *o = needs_sha1[i];
+		if (o->flags & COMMON_KNOWN)
+			continue;
+		if (strcmp(o->type, tag_type) &&
+		    strcmp(o->type, commit_type))
+			/* Asking for non traceable types - there
+			 * is not much we can do to optimize it here.
+			 * We will let rev-list deal with it.
+			 */
+			continue;
+		if (trace_bit < MAX_TRACE) {
+			trace[trace_bit] = o;
+			trace_bit++;
+		}
+		else {
+			still_missing = trace_want(trace, trace_bit);
+			trace_bit = 0;
+		}
+	}
+	if (trace_bit && !still_missing)
+		still_missing = trace_want(trace, trace_bit);
+
+	if (!still_missing)
+		multi_ack = 0;
+}
+
 static int got_sha1(char *hex, unsigned char *sha1)
 {
 	if (get_sha1_hex(hex, sha1))

@@ -107,15 +235,39 @@ static int got_sha1(char *hex, unsigned 
 			die("oops (%s)", sha1_to_hex(sha1));
 		if (o->type == commit_type) {
 			struct commit_list *parents;
+			int we_knew_they_have = 0;
+
+			/* Because we deliberately stay behind by one
+			 * window in order to make the protocol
+			 * stream, many commits can already be in
+			 * flight when we notice that the latest one
+			 * in the series is already what we have.  Do
+			 * not waste the has_sha1[] slot for extra commits
+			 * sent that way.
+			 *
+			 * This relies on fetch-pack sending the "have"
+			 * lines without skipping.
+			 */
 			if (o->flags & THEY_HAVE)
-				return 0;
-			o->flags |= THEY_HAVE;
+				we_knew_they_have = 1;
+			else
+				o->flags |= THEY_HAVE;
 			for (parents = ((struct commit*)o)->parents;
 			     parents;
 			     parents = parents->next)
 				parents->item->object.flags |= THEY_HAVE;
+			if (we_knew_they_have)
+				return 0;
 		}
-		memcpy(has_sha1[nr_has++], sha1, 20);
+		has_sha1[nr_has++] = o;
+
+		/* Check to see if we know a common ancestor for
+		 * all the "want" heads, and if so turn multi_ack
+		 * off.  There is nothing more gained by further
+		 * exchange.
+		 */
+		check_want_heads();
+
 	}
 	return 1;
 }

@@ -141,7 +293,7 @@ static int get_common_commits(void)
 		len = strip(line, len);
 		if (!strncmp(line, "have ", 5)) {
 			if (got_sha1(line+5, sha1) &&
-					(multi_ack || nr_has == 1)) {
+			    (multi_ack || nr_has == 1)) {
 				if (nr_has >= MAX_HAS)
 					multi_ack = 0;
 				packet_write(1, "ACK %s%s\n",

@@ -156,7 +308,7 @@ static int get_common_commits(void)
 			if (nr_has > 0) {
 				if (multi_ack)
 					packet_write(1, "ACK %s\n",
-							sha1_to_hex(last_sha1));
+						     sha1_to_hex(last_sha1));
 				return 0;
 			}
 			packet_write(1, "NAK\n");

@@ -174,23 +326,21 @@ static int receive_needs(void)
 	needs = 0;
 	for (;;) {
 		struct object *o;
-		unsigned char dummy[20], *sha1_buf;
+		unsigned char sha1_buf[20];
 		len = packet_read_line(0, line, sizeof(line));
 		reset_timeout();
 		if (!len)
 			return needs;
 
-		sha1_buf = dummy;
 		if (needs == MAX_NEEDS) {
 			fprintf(stderr,
 				"warning: supporting only a max of %d requests. "
 				"sending everything instead.\n",
 				MAX_NEEDS);
 		}
-		else if (needs < MAX_NEEDS)
-			sha1_buf = needs_sha1[needs];
 
-		if (strncmp("want ", line, 5) || get_sha1_hex(line+5, sha1_buf))
+		if (strncmp("want ", line, 5) ||
+		    get_sha1_hex(line+5, sha1_buf))
 			die("git-upload-pack: protocol error, "
 			    "expected to get sha, not '%s'", line);
 		if (strstr(line+45, "multi_ack"))

@@ -211,6 +361,8 @@ static int receive_needs(void)
 			die("git-upload-pack: not our ref %s", line+5);
 		if (!(o->flags & WANTED)) {
 			o->flags |= WANTED;
+			if (needs < MAX_NEEDS)
+				needs_sha1[needs] = o;
 			needs++;
 		}
 	}