[PATCH 1/4 v2] fetch-pack: Finish negotation if remote replies "ACK %s ready"

[PATCH 1/4 v2] fetch-pack: Finish negotation if remote replies "ACK %s ready"

[Shawn O. Pearce]

If multi_ack_detailed was selected in the protocol capabilities
(both client and server are >= Git 1.6.6) the upload-pack side will
send "ACK %s ready" when it knows how to safely cut the graph and
produce a reasonable pack for the want list that was already sent
on the connection.

Upon receiving "ACK %s ready" there is no point in looking at
the remaining commits inside of rev_list.  Sending additional
"have %s" lines to the remote will not construct a smaller pack.
It is unlikely a commit older than the current cut point will have
a better delta base than the cut point itself has.

The original design of this code had fetch-pack empty rev_list by
marking a commit and its transitive ancestors COMMON whenever the
remote side said "ACK %s {continue,common}" and skipping over any
already COMMON commits during get_rev().  This approach does not
work when most of rev_list is actually COMMON_REF, commits that
are pointed to by a reference on the remote, which exist locally,
and which have not yet been sent to the remote as a "have %s" line.

Most of the common references are tags in the ref/tags namespace,
using points in the commit graph that are more than 1 commit apart.
In git.git itself, this is currently 340 tags, 339 of which point to
commits in the commit graph.  fetch-pack pushes all of these into
rev_list, but is unable to mark them COMMON and discard during a
remote's "ACK %s {continue,common}" because it does not parse through
the entire parent chain.  Not parsing the entire parent chain is
an optimization to avoid walking back to the roots of the repository.

Assuming the client is only following the remote (and does not make
its own local commits), the client needs 11 rounds to spin through
the entire list of tags (32 commits per round, ceil(339/32) == 11).
Unfortunately the server knows on the first "have %s" line that
it can produce a good pack, and does not need to see the remaining
320 tags in the other 10 rounds.

Over git:// and ssh:// this isn't as bad as it sounds, the client is
only transmitting an extra 16,000 bytes that it doesn't need to send.

Over smart HTTP, the client must do an additional 10 HTTP POST
requests, each of which incurs round-trip latency, and must upload
the entire state vector of all known common objects.  On the final
POST request, this is 16 KiB worth of data.

Fix all of this by clearing rev_list as soon as the remote side
says it can construct a pack.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---

 Fixed bad indentation that appeared in v1.

 builtin/fetch-pack.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index b999413..5173dc9 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -379,6 +379,8 @@ static int find_common(int fd[2], unsigned char *result_sha1,
 					retval = 0;
 					in_vain = 0;
 					got_continue = 1;
+					if (ack == ACK_ready)
+						rev_list = NULL;
 					break;
 					}
 				}
-- 
1.7.4.1.35.ga52fb.dirty

[PATCH 2/4 v1] upload-pack: More aggressively send 'ACK %s ready'

[Shawn O. Pearce]

If a client is merely following the remote (and has not made any
new commits itself), all "have %s" lines sent by the client will be
common to the server.  As all lines are common upload-pack never
calls ok_to_give_up() and does not compute if it has a good cut
point in the commit graph.

Without this computation the following client is going to send all
tagged commits, as these were determined to be COMMON_REF during the
initial advertisement, but the client does not parse their history
to transitively pass the COMMON flag and empty its queue of commits.

For git.git with 339 commit tags, it takes clients 11 rounds of
negotation to fully send all tagged commits and exhaust its queue
of things to send as common.  This is pretty slow for a client that
has not done any local development activity.

Force computing ok_to_give_up() and send "ACK %s ready" at the end
of the current round if this round only contained common objects
and ok_to_give_up() was therefore not called.  This may allow the
client to break early, avoiding transmission of the COMMON_REFs.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---

 Unchanged from v1.

 upload-pack.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

diff --git a/upload-pack.c b/upload-pack.c
index b40a43f..2a0f19e 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -429,6 +429,8 @@ static int get_common_commits(void)
 	static char line[1000];
 	unsigned char sha1[20];
 	char last_hex[41];
+	int got_common = 0;
+	int got_other = 0;
 
 	save_commit_buffer = 0;
 
@@ -437,16 +439,22 @@ static int get_common_commits(void)
 		reset_timeout();
 
 		if (!len) {
+			if (multi_ack == 2 && got_common
+					&& !got_other && ok_to_give_up())
+				packet_write(1, "ACK %s ready\n", last_hex);
 			if (have_obj.nr == 0 || multi_ack)
 				packet_write(1, "NAK\n");
 			if (stateless_rpc)
 				exit(0);
+			got_common = 0;
+			got_other = 0;
 			continue;
 		}
 		strip(line, len);
 		if (!prefixcmp(line, "have ")) {
 			switch (got_sha1(line+5, sha1)) {
 			case -1: /* they have what we do not */
+				got_other = 1;
 				if (multi_ack && ok_to_give_up()) {
 					const char *hex = sha1_to_hex(sha1);
 					if (multi_ack == 2)
@@ -456,6 +464,7 @@ static int get_common_commits(void)
 				}
 				break;
 			default:
+				got_common = 1;
 				memcpy(last_hex, sha1_to_hex(sha1), 41);
 				if (multi_ack == 2)
 					packet_write(1, "ACK %s common\n", last_hex);
-- 
1.7.4.1.35.ga52fb.dirty

[PATCH 3/4] fetch-pack: Implement no-done capability

[Shawn O. Pearce]

If enabled on the connection "multi_ack_detailed no-done" as a
pair allows the remote upload-pack process to send a PACK down
to the client as soon as a "ACK %s ready" message was also sent.

Over git:// and ssh:// where a bi-directional stream is in place
this has very little difference over the classical version that
waits for the client to send a "done\n" line by itself.  It does
slightly reduce the latency involved to start the pack stream as
there is one less round-trip from client->server required.

Over smart HTTP this avoids needing to send a final RPC that has
all of the prior common objects.  Instead the server is able to
return a pack as soon as its ready to.  For many common users the
smart HTTP fetch is now just 2 requests: GET .../info/refs, and
a POST .../git-upload-pack to not only negotiate but also receive
the pack stream.  Only users who have more than 32 local unshared
commits with the remote will need additional requests to negotiate
a common merge base.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 builtin/fetch-pack.c |   18 +++++++++++++++---
 1 files changed, 15 insertions(+), 3 deletions(-)

diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index 5173dc9..59fbda5 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -14,6 +14,7 @@ static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;
 static int unpack_limit = 100;
 static int prefer_ofs_delta = 1;
+static int no_done = 0;
 static struct fetch_pack_args args = {
 	/* .uploadpack = */ "git-upload-pack",
 };
@@ -225,6 +226,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,
 	const unsigned char *sha1;
 	unsigned in_vain = 0;
 	int got_continue = 0;
+	int got_ready = 0;
 	struct strbuf req_buf = STRBUF_INIT;
 	size_t state_len = 0;
 
@@ -262,6 +264,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,
 			struct strbuf c = STRBUF_INIT;
 			if (multi_ack == 2)     strbuf_addstr(&c, " multi_ack_detailed");
 			if (multi_ack == 1)     strbuf_addstr(&c, " multi_ack");
+			if (no_done)            strbuf_addstr(&c, " no-done");
 			if (use_sideband == 2)  strbuf_addstr(&c, " side-band-64k");
 			if (use_sideband == 1)  strbuf_addstr(&c, " side-band");
 			if (args.use_thin_pack) strbuf_addstr(&c, " thin-pack");
@@ -379,8 +382,10 @@ static int find_common(int fd[2], unsigned char *result_sha1,
 					retval = 0;
 					in_vain = 0;
 					got_continue = 1;
-					if (ack == ACK_ready)
+					if (ack == ACK_ready) {
 						rev_list = NULL;
+						got_ready = 1;
+					}
 					break;
 					}
 				}
@@ -394,8 +399,10 @@ static int find_common(int fd[2], unsigned char *result_sha1,
 		}
 	}
 done:
-	packet_buf_write(&req_buf, "done\n");
-	send_request(fd[1], &req_buf);
+	if (!got_ready || !no_done) {
+		packet_buf_write(&req_buf, "done\n");
+		send_request(fd[1], &req_buf);
+	}
 	if (args.verbose)
 		fprintf(stderr, "done\n");
 	if (retval != 0) {
@@ -698,6 +705,11 @@ static struct ref *do_fetch_pack(int fd[2],
 		if (args.verbose)
 			fprintf(stderr, "Server supports multi_ack_detailed\n");
 		multi_ack = 2;
+		if (server_supports("no-done")) {
+			if (args.verbose)
+				fprintf(stderr, "Server supports no-done\n");
+			no_done = 1;
+		}
 	}
 	else if (server_supports("multi_ack")) {
 		if (args.verbose)
-- 
1.7.4.1.35.ga52fb.dirty

[PATCH 4/4] upload-pack: Implement no-done capability

[Shawn O. Pearce]

If the client requests both multi_ack_detailed and no-done then
upload-pack is free to immediately send a PACK following its first
'ACK %s ready' message.  The upload-pack response actually winds
up being:

  ACK %s common
  ... (maybe more) ...
  ACK %s ready
  NAK
  ACK %s
  PACK.... the pack stream ....

For smart HTTP connections this saves one HTTP RPC, reducing
the overall latency for a trivial fetch.  For git:// and ssh://
a no-done option slightly reduces latency by removing one
server->client->server round-trip at the end of the common
ancestor negotiation.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 upload-pack.c |   20 ++++++++++++++++----
 1 files changed, 16 insertions(+), 4 deletions(-)

diff --git a/upload-pack.c b/upload-pack.c
index 2a0f19e..e644dbe 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -27,6 +27,7 @@ static const char upload_pack_usage[] = "git upload-pack [--strict] [--timeout=<
 static unsigned long oldest_have;
 
 static int multi_ack, nr_our_refs;
+static int no_done;
 static int use_thin_pack, use_ofs_delta, use_include_tag;
 static int no_progress, daemon_mode;
 static int shallow_nr;
@@ -431,6 +432,7 @@ static int get_common_commits(void)
 	char last_hex[41];
 	int got_common = 0;
 	int got_other = 0;
+	int sent_ready = 0;
 
 	save_commit_buffer = 0;
 
@@ -440,10 +442,17 @@ static int get_common_commits(void)
 
 		if (!len) {
 			if (multi_ack == 2 && got_common
-					&& !got_other && ok_to_give_up())
+					&& !got_other && ok_to_give_up()) {
+				sent_ready = 1;
 				packet_write(1, "ACK %s ready\n", last_hex);
+			}
 			if (have_obj.nr == 0 || multi_ack)
 				packet_write(1, "NAK\n");
+
+			if (no_done && sent_ready) {
+				packet_write(1, "ACK %s\n", last_hex);
+				return 0;
+			}
 			if (stateless_rpc)
 				exit(0);
 			got_common = 0;
@@ -457,9 +466,10 @@ static int get_common_commits(void)
 				got_other = 1;
 				if (multi_ack && ok_to_give_up()) {
 					const char *hex = sha1_to_hex(sha1);
-					if (multi_ack == 2)
+					if (multi_ack == 2) {
+						sent_ready = 1;
 						packet_write(1, "ACK %s ready\n", hex);
-					else
+					} else
 						packet_write(1, "ACK %s continue\n", hex);
 				}
 				break;
@@ -535,6 +545,8 @@ static void receive_needs(void)
 			multi_ack = 2;
 		else if (strstr(line+45, "multi_ack"))
 			multi_ack = 1;
+		if (strstr(line+45, "no-done"))
+			no_done = 1;
 		if (strstr(line+45, "thin-pack"))
 			use_thin_pack = 1;
 		if (strstr(line+45, "ofs-delta"))
@@ -628,7 +640,7 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo
 {
 	static const char *capabilities = "multi_ack thin-pack side-band"
 		" side-band-64k ofs-delta shallow no-progress"
-		" include-tag multi_ack_detailed";
+		" include-tag multi_ack_detailed no-done";
 	struct object *o = parse_object(sha1);
 
 	if (!o)
-- 
1.7.4.1.35.ga52fb.dirty