{"thread":{"id":"26735","subject":"[PATCH 1/4 v2] fetch-pack: Finish negotation if remote replies \"ACK %s ready\"","startedAt":"2011-03-15T00:59:37Z","lastAt":"2011-03-15T00:59:40Z","messageCount":4,"participants":["Shawn O. Pearce"],"isPatch":true,"patchVersion":2,"patchTotal":4},"messages":[{"id":"163357","messageId":"1300150780-7487-1-git-send-email-spearce@spearce.org","threadId":"26735","inReplyTo":null,"subject":"[PATCH 1/4 v2] fetch-pack: Finish negotation if remote replies \"ACK %s ready\"","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-03-15T00:59:37Z","receivedAt":"2011-03-15T00:59:37Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If multi_ack_detailed was selected in the protocol capabilities\n(both client and server are >= Git 1.6.6) the upload-pack side will\nsend \"ACK %s ready\" when it knows how to safely cut the graph and\nproduce a reasonable pack for the want list that was already sent\non the connection.\n\nUpon receiving \"ACK %s ready\" there is no point in looking at\nthe remaining commits inside of rev_list.  Sending additional\n\"have %s\" lines to the remote will not construct a smaller pack.\nIt is unlikely a commit older than the current cut point will have\na better delta base than the cut point itself has.\n\nThe original design of this code had fetch-pack empty rev_list by\nmarking a commit and its transitive ancestors COMMON whenever the\nremote side said \"ACK %s {continue,common}\" and skipping over any\nalready COMMON commits during get_rev().  This approach does not\nwork when most of rev_list is actually COMMON_REF, commits that\nare pointed to by a reference on the remote, which exist locally,\nand which have not yet been sent to the remote as a \"have %s\" line.\n\nMost of the common references are tags in the ref/tags namespace,\nusing points in the commit graph that are more than 1 commit apart.\nIn git.git itself, this is currently 340 tags, 339 of which point to\ncommits in the commit graph.  fetch-pack pushes all of these into\nrev_list, but is unable to mark them COMMON and discard during a\nremote's \"ACK %s {continue,common}\" because it does not parse through\nthe entire parent chain.  Not parsing the entire parent chain is\nan optimization to avoid walking back to the roots of the repository.\n\nAssuming the client is only following the remote (and does not make\nits own local commits), the client needs 11 rounds to spin through\nthe entire list of tags (32 commits per round, ceil(339/32) == 11).\nUnfortunately the server knows on the first \"have %s\" line that\nit can produce a good pack, and does not need to see the remaining\n320 tags in the other 10 rounds.\n\nOver git:// and ssh:// this isn't as bad as it sounds, the client is\nonly transmitting an extra 16,000 bytes that it doesn't need to send.\n\nOver smart HTTP, the client must do an additional 10 HTTP POST\nrequests, each of which incurs round-trip latency, and must upload\nthe entire state vector of all known common objects.  On the final\nPOST request, this is 16 KiB worth of data.\n\nFix all of this by clearing rev_list as soon as the remote side\nsays it can construct a pack.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n\n Fixed bad indentation that appeared in v1.\n\n builtin/fetch-pack.c |    2 ++\n 1 files changed, 2 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex b999413..5173dc9 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -379,6 +379,8 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\t\t\tretval = 0;\n \t\t\t\t\tin_vain = 0;\n \t\t\t\t\tgot_continue = 1;\n+\t\t\t\t\tif (ack == ACK_ready)\n+\t\t\t\t\t\trev_list = NULL;\n \t\t\t\t\tbreak;\n \t\t\t\t\t}\n \t\t\t\t}\n-- \n1.7.4.1.35.ga52fb.dirty\n"},{"id":"163358","messageId":"1300150780-7487-2-git-send-email-spearce@spearce.org","threadId":"26735","inReplyTo":"1300150780-7487-1-git-send-email-spearce@spearce.org","subject":"[PATCH 2/4 v1] upload-pack: More aggressively send 'ACK %s ready'","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-03-15T00:59:38Z","receivedAt":"2011-03-15T00:59:38Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If a client is merely following the remote (and has not made any\nnew commits itself), all \"have %s\" lines sent by the client will be\ncommon to the server.  As all lines are common upload-pack never\ncalls ok_to_give_up() and does not compute if it has a good cut\npoint in the commit graph.\n\nWithout this computation the following client is going to send all\ntagged commits, as these were determined to be COMMON_REF during the\ninitial advertisement, but the client does not parse their history\nto transitively pass the COMMON flag and empty its queue of commits.\n\nFor git.git with 339 commit tags, it takes clients 11 rounds of\nnegotation to fully send all tagged commits and exhaust its queue\nof things to send as common.  This is pretty slow for a client that\nhas not done any local development activity.\n\nForce computing ok_to_give_up() and send \"ACK %s ready\" at the end\nof the current round if this round only contained common objects\nand ok_to_give_up() was therefore not called.  This may allow the\nclient to break early, avoiding transmission of the COMMON_REFs.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n\n Unchanged from v1.\n\n upload-pack.c |    9 +++++++++\n 1 files changed, 9 insertions(+), 0 deletions(-)\n\ndiff --git a/upload-pack.c b/upload-pack.c\nindex b40a43f..2a0f19e 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -429,6 +429,8 @@ static int get_common_commits(void)\n \tstatic char line[1000];\n \tunsigned char sha1[20];\n \tchar last_hex[41];\n+\tint got_common = 0;\n+\tint got_other = 0;\n \n \tsave_commit_buffer = 0;\n \n@@ -437,16 +439,22 @@ static int get_common_commits(void)\n \t\treset_timeout();\n \n \t\tif (!len) {\n+\t\t\tif (multi_ack == 2 && got_common\n+\t\t\t\t\t&& !got_other && ok_to_give_up())\n+\t\t\t\tpacket_write(1, \"ACK %s ready\\n\", last_hex);\n \t\t\tif (have_obj.nr == 0 || multi_ack)\n \t\t\t\tpacket_write(1, \"NAK\\n\");\n \t\t\tif (stateless_rpc)\n \t\t\t\texit(0);\n+\t\t\tgot_common = 0;\n+\t\t\tgot_other = 0;\n \t\t\tcontinue;\n \t\t}\n \t\tstrip(line, len);\n \t\tif (!prefixcmp(line, \"have \")) {\n \t\t\tswitch (got_sha1(line+5, sha1)) {\n \t\t\tcase -1: /* they have what we do not */\n+\t\t\t\tgot_other = 1;\n \t\t\t\tif (multi_ack && ok_to_give_up()) {\n \t\t\t\t\tconst char *hex = sha1_to_hex(sha1);\n \t\t\t\t\tif (multi_ack == 2)\n@@ -456,6 +464,7 @@ static int get_common_commits(void)\n \t\t\t\t}\n \t\t\t\tbreak;\n \t\t\tdefault:\n+\t\t\t\tgot_common = 1;\n \t\t\t\tmemcpy(last_hex, sha1_to_hex(sha1), 41);\n \t\t\t\tif (multi_ack == 2)\n \t\t\t\t\tpacket_write(1, \"ACK %s common\\n\", last_hex);\n-- \n1.7.4.1.35.ga52fb.dirty\n"},{"id":"163359","messageId":"1300150780-7487-3-git-send-email-spearce@spearce.org","threadId":"26735","inReplyTo":"1300150780-7487-1-git-send-email-spearce@spearce.org","subject":"[PATCH 3/4] fetch-pack: Implement no-done capability","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-03-15T00:59:39Z","receivedAt":"2011-03-15T00:59:39Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If enabled on the connection \"multi_ack_detailed no-done\" as a\npair allows the remote upload-pack process to send a PACK down\nto the client as soon as a \"ACK %s ready\" message was also sent.\n\nOver git:// and ssh:// where a bi-directional stream is in place\nthis has very little difference over the classical version that\nwaits for the client to send a \"done\\n\" line by itself.  It does\nslightly reduce the latency involved to start the pack stream as\nthere is one less round-trip from client->server required.\n\nOver smart HTTP this avoids needing to send a final RPC that has\nall of the prior common objects.  Instead the server is able to\nreturn a pack as soon as its ready to.  For many common users the\nsmart HTTP fetch is now just 2 requests: GET .../info/refs, and\na POST .../git-upload-pack to not only negotiate but also receive\nthe pack stream.  Only users who have more than 32 local unshared\ncommits with the remote will need additional requests to negotiate\na common merge base.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n builtin/fetch-pack.c |   18 +++++++++++++++---\n 1 files changed, 15 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex 5173dc9..59fbda5 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -14,6 +14,7 @@ static int transfer_unpack_limit = -1;\n static int fetch_unpack_limit = -1;\n static int unpack_limit = 100;\n static int prefer_ofs_delta = 1;\n+static int no_done = 0;\n static struct fetch_pack_args args = {\n \t/* .uploadpack = */ \"git-upload-pack\",\n };\n@@ -225,6 +226,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \tconst unsigned char *sha1;\n \tunsigned in_vain = 0;\n \tint got_continue = 0;\n+\tint got_ready = 0;\n \tstruct strbuf req_buf = STRBUF_INIT;\n \tsize_t state_len = 0;\n \n@@ -262,6 +264,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\tstruct strbuf c = STRBUF_INIT;\n \t\t\tif (multi_ack == 2)     strbuf_addstr(&c, \" multi_ack_detailed\");\n \t\t\tif (multi_ack == 1)     strbuf_addstr(&c, \" multi_ack\");\n+\t\t\tif (no_done)            strbuf_addstr(&c, \" no-done\");\n \t\t\tif (use_sideband == 2)  strbuf_addstr(&c, \" side-band-64k\");\n \t\t\tif (use_sideband == 1)  strbuf_addstr(&c, \" side-band\");\n \t\t\tif (args.use_thin_pack) strbuf_addstr(&c, \" thin-pack\");\n@@ -379,8 +382,10 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\t\t\tretval = 0;\n \t\t\t\t\tin_vain = 0;\n \t\t\t\t\tgot_continue = 1;\n-\t\t\t\t\tif (ack == ACK_ready)\n+\t\t\t\t\tif (ack == ACK_ready) {\n \t\t\t\t\t\trev_list = NULL;\n+\t\t\t\t\t\tgot_ready = 1;\n+\t\t\t\t\t}\n \t\t\t\t\tbreak;\n \t\t\t\t\t}\n \t\t\t\t}\n@@ -394,8 +399,10 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t}\n \t}\n done:\n-\tpacket_buf_write(&req_buf, \"done\\n\");\n-\tsend_request(fd[1], &req_buf);\n+\tif (!got_ready || !no_done) {\n+\t\tpacket_buf_write(&req_buf, \"done\\n\");\n+\t\tsend_request(fd[1], &req_buf);\n+\t}\n \tif (args.verbose)\n \t\tfprintf(stderr, \"done\\n\");\n \tif (retval != 0) {\n@@ -698,6 +705,11 @@ static struct ref *do_fetch_pack(int fd[2],\n \t\tif (args.verbose)\n \t\t\tfprintf(stderr, \"Server supports multi_ack_detailed\\n\");\n \t\tmulti_ack = 2;\n+\t\tif (server_supports(\"no-done\")) {\n+\t\t\tif (args.verbose)\n+\t\t\t\tfprintf(stderr, \"Server supports no-done\\n\");\n+\t\t\tno_done = 1;\n+\t\t}\n \t}\n \telse if (server_supports(\"multi_ack\")) {\n \t\tif (args.verbose)\n-- \n1.7.4.1.35.ga52fb.dirty\n"},{"id":"163360","messageId":"1300150780-7487-4-git-send-email-spearce@spearce.org","threadId":"26735","inReplyTo":"1300150780-7487-1-git-send-email-spearce@spearce.org","subject":"[PATCH 4/4] upload-pack: Implement no-done capability","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-03-15T00:59:40Z","receivedAt":"2011-03-15T00:59:40Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If the client requests both multi_ack_detailed and no-done then\nupload-pack is free to immediately send a PACK following its first\n'ACK %s ready' message.  The upload-pack response actually winds\nup being:\n\n  ACK %s common\n  ... (maybe more) ...\n  ACK %s ready\n  NAK\n  ACK %s\n  PACK.... the pack stream ....\n\nFor smart HTTP connections this saves one HTTP RPC, reducing\nthe overall latency for a trivial fetch.  For git:// and ssh://\na no-done option slightly reduces latency by removing one\nserver->client->server round-trip at the end of the common\nancestor negotiation.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n upload-pack.c |   20 ++++++++++++++++----\n 1 files changed, 16 insertions(+), 4 deletions(-)\n\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 2a0f19e..e644dbe 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -27,6 +27,7 @@ static const char upload_pack_usage[] = \"git upload-pack [--strict] [--timeout=<\n static unsigned long oldest_have;\n \n static int multi_ack, nr_our_refs;\n+static int no_done;\n static int use_thin_pack, use_ofs_delta, use_include_tag;\n static int no_progress, daemon_mode;\n static int shallow_nr;\n@@ -431,6 +432,7 @@ static int get_common_commits(void)\n \tchar last_hex[41];\n \tint got_common = 0;\n \tint got_other = 0;\n+\tint sent_ready = 0;\n \n \tsave_commit_buffer = 0;\n \n@@ -440,10 +442,17 @@ static int get_common_commits(void)\n \n \t\tif (!len) {\n \t\t\tif (multi_ack == 2 && got_common\n-\t\t\t\t\t&& !got_other && ok_to_give_up())\n+\t\t\t\t\t&& !got_other && ok_to_give_up()) {\n+\t\t\t\tsent_ready = 1;\n \t\t\t\tpacket_write(1, \"ACK %s ready\\n\", last_hex);\n+\t\t\t}\n \t\t\tif (have_obj.nr == 0 || multi_ack)\n \t\t\t\tpacket_write(1, \"NAK\\n\");\n+\n+\t\t\tif (no_done && sent_ready) {\n+\t\t\t\tpacket_write(1, \"ACK %s\\n\", last_hex);\n+\t\t\t\treturn 0;\n+\t\t\t}\n \t\t\tif (stateless_rpc)\n \t\t\t\texit(0);\n \t\t\tgot_common = 0;\n@@ -457,9 +466,10 @@ static int get_common_commits(void)\n \t\t\t\tgot_other = 1;\n \t\t\t\tif (multi_ack && ok_to_give_up()) {\n \t\t\t\t\tconst char *hex = sha1_to_hex(sha1);\n-\t\t\t\t\tif (multi_ack == 2)\n+\t\t\t\t\tif (multi_ack == 2) {\n+\t\t\t\t\t\tsent_ready = 1;\n \t\t\t\t\t\tpacket_write(1, \"ACK %s ready\\n\", hex);\n-\t\t\t\t\telse\n+\t\t\t\t\t} else\n \t\t\t\t\t\tpacket_write(1, \"ACK %s continue\\n\", hex);\n \t\t\t\t}\n \t\t\t\tbreak;\n@@ -535,6 +545,8 @@ static void receive_needs(void)\n \t\t\tmulti_ack = 2;\n \t\telse if (strstr(line+45, \"multi_ack\"))\n \t\t\tmulti_ack = 1;\n+\t\tif (strstr(line+45, \"no-done\"))\n+\t\t\tno_done = 1;\n \t\tif (strstr(line+45, \"thin-pack\"))\n \t\t\tuse_thin_pack = 1;\n \t\tif (strstr(line+45, \"ofs-delta\"))\n@@ -628,7 +640,7 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo\n {\n \tstatic const char *capabilities = \"multi_ack thin-pack side-band\"\n \t\t\" side-band-64k ofs-delta shallow no-progress\"\n-\t\t\" include-tag multi_ack_detailed\";\n+\t\t\" include-tag multi_ack_detailed no-done\";\n \tstruct object *o = parse_object(sha1);\n \n \tif (!o)\n-- \n1.7.4.1.35.ga52fb.dirty\n"}]}