{"thread":{"id":"55166","subject":"[RFC PATCH] push: perform negotiation before sending packfile","startedAt":"2021-02-18T01:22:02Z","lastAt":"2021-02-22T21:33:54Z","messageCount":9,"participants":["Jonathan Tan","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"417264","messageId":"20210218012100.928957-1-jonathantanmy@google.com","threadId":"55166","inReplyTo":null,"subject":"[RFC PATCH] push: perform negotiation before sending packfile","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2021-02-18T01:21:00Z","receivedAt":"2021-02-18T01:22:02Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"The idea of adding negotiation to push has been floating around for a\nwhile. Here's my implementation of my idea of reusing a lot of the fetch\nmechanism to perform the negotiation.\n\nThe basic idea is that when a client pushes, the client will first\nperform the negotiation steps that it normally does during a fetch,\nexcept that it does not send any \"want\"s and it only uses the commits to\nbe pushed as negotiation tips (instead of all refs). Once the client has\nreceived enough ACKs that all ancestral paths from all tips to the\noriginal orphans are blocked by ACKed commits, it will proceed with the\npush, using this information to determine the contents of the\nto-be-pushed packfile. (This check is done by the server when doing a\nuser-triggered fetch.) This requires a minimal change on the server to\naccept an argument that tells the server that it cannot take the\ninitiative to send the packfile, and to allow the client to not send any\n\"want\"s.\n\nThe main features (which are implemented in this patch) are:\n\n - Minimal change to the fetch-serving part of the server, as described\n   (new \"wait-for-done\" argument that inhibits the server taking the\n   initiative to send the packfile, and to allow the client to not send\n   any \"want\"s).\n - No change needed to the push-serving part of the server, although for\n   performance, we would want something that can stop the ref\n   advertisement since it is no longer needed (perhaps a simplification\n   of my earlier work [1]).\n - Reuse of a lot of fetch code.\n - We inherit any fetch negotiation algorithm improvements (e.g. the\n   \"skipping\" negotiator).\n\nWhat hasn't been done yet:\n\n - Refactor negotiation tip code that I copied over from builtin/fetch.c\n   to builtin/fetch-pack.c.\n - Non-main-path cases (e.g. if the server doesn't support this new\n   \"wait-for-done\")\n - Certain optimizations like avoiding the ls-refs call when negotiating\n - Config option on the client to enable/disable this feature\n - Do we need statistics in the commit message to show the performance\n   gains?\n - Anything else that comes up upon more scrutiny\n\nAny comments are welcome, especially if you have ideas about the overall\ndesign or implementation, and/or if you've thought about similar things\nbefore.\n\n[1] https://lore.kernel.org/git/20201109224732.2549561-1-jonathantanmy@google.com/\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\n builtin/fetch-pack.c  | 57 +++++++++++++++++++++++++++++++++++++++++++\n fetch-pack.c          | 49 ++++++++++++++++++++++++++++++++++---\n fetch-pack.h          |  6 +++++\n object.h              |  2 +-\n send-pack.c           | 51 +++++++++++++++++++++++++++++++++++---\n t/t5510-fetch.sh      | 19 +++++++++++++++\n t/t5516-fetch-push.sh | 24 ++++++++++++++++++\n transport.c           |  1 +\n transport.h           |  5 ++++\n upload-pack.c         | 16 +++++++++---\n 10 files changed, 217 insertions(+), 13 deletions(-)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex 58b7c1fbdc..c8c942b42c 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -5,6 +5,8 @@\n #include \"connect.h\"\n #include \"oid-array.h\"\n #include \"protocol.h\"\n+#include \"oidset.h\"\n+#include \"refs.h\"\n \n static const char fetch_pack_usage[] =\n \"git fetch-pack [--all] [--stdin] [--quiet | -q] [--keep | -k] [--thin] \"\n@@ -40,6 +42,39 @@ static void add_sought_entry(struct ref ***sought, int *nr, int *alloc,\n \t(*sought)[*nr - 1] = ref;\n }\n \n+static int add_oid(const char *refname, const struct object_id *oid, int flags,\n+\t\t   void *cb_data)\n+{\n+\tstruct oid_array *oids = cb_data;\n+\n+\toid_array_append(oids, oid);\n+\treturn 0;\n+}\n+\n+static void add_negotiation_tips(struct fetch_pack_args *args, struct string_list *negotiation_tip)\n+{\n+\tstruct oid_array *oids = xcalloc(1, sizeof(*oids));\n+\tint i;\n+\n+\tfor (i = 0; i < negotiation_tip->nr; i++) {\n+\t\tconst char *s = negotiation_tip->items[i].string;\n+\t\tint old_nr;\n+\t\tif (!has_glob_specials(s)) {\n+\t\t\tstruct object_id oid;\n+\t\t\tif (get_oid(s, &oid))\n+\t\t\t\tdie(\"%s is not a valid object\", s);\n+\t\t\toid_array_append(oids, &oid);\n+\t\t\tcontinue;\n+\t\t}\n+\t\told_nr = oids->nr;\n+\t\tfor_each_glob_ref(add_oid, s, oids);\n+\t\tif (old_nr == oids->nr)\n+\t\t\twarning(\"Ignoring --negotiation-tip=%s because it does not match any refs\",\n+\t\t\t\ts);\n+\t}\n+\targs->negotiation_tips = oids;\n+}\n+\n int cmd_fetch_pack(int argc, const char **argv, const char *prefix)\n {\n \tint i, ret;\n@@ -54,6 +89,8 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)\n \tstruct fetch_pack_args args;\n \tstruct oid_array shallow = OID_ARRAY_INIT;\n \tstruct string_list deepen_not = STRING_LIST_INIT_DUP;\n+\tstruct string_list negotiation_tip = STRING_LIST_INIT_DUP;\n+\tstruct oidset acked_commits = OIDSET_INIT;\n \tstruct packet_reader reader;\n \tenum protocol_version version;\n \n@@ -161,10 +198,20 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)\n \t\t\tlist_objects_filter_set_no_filter(&args.filter_options);\n \t\t\tcontinue;\n \t\t}\n+\t\tif (skip_prefix(arg, \"--negotiation-tip=\", &arg)) {\n+\t\t\tstring_list_append(&negotiation_tip, arg);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(\"--negotiate-only\", arg)) {\n+\t\t\targs.acked_commits = &acked_commits;\n+\t\t\tcontinue;\n+\t\t}\n \t\tusage(fetch_pack_usage);\n \t}\n \tif (deepen_not.nr)\n \t\targs.deepen_not = &deepen_not;\n+\tif (negotiation_tip.nr)\n+\t\tadd_negotiation_tips(&args, &negotiation_tip);\n \n \tif (i < argc)\n \t\tdest = argv[i++];\n@@ -232,6 +279,16 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)\n \n \tref = fetch_pack(&args, fd, ref, sought, nr_sought,\n \t\t\t &shallow, pack_lockfiles_ptr, version);\n+\tif (args.acked_commits) {\n+\t\tstruct oidset_iter iter;\n+\t\tconst struct object_id *oid;\n+\t\toidset_iter_init(args.acked_commits, &iter);\n+\n+\t\twhile ((oid = oidset_iter_next(&iter))) {\n+\t\t\tprintf(\"%s\\n\", oid_to_hex(oid));\n+\t\t}\n+\t\treturn 0;\n+\t}\n \tif (pack_lockfiles.nr) {\n \t\tint i;\n \ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 1eaedcb5dc..4d2c6119f1 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -23,6 +23,7 @@\n #include \"fetch-negotiator.h\"\n #include \"fsck.h\"\n #include \"shallow.h\"\n+#include \"commit-reach.h\"\n \n static int transfer_unpack_limit = -1;\n static int fetch_unpack_limit = -1;\n@@ -44,6 +45,8 @@ static struct string_list uri_protocols = STRING_LIST_INIT_DUP;\n /* Remember to update object flag allocation in object.h */\n #define COMPLETE\t(1U << 0)\n #define ALTERNATE\t(1U << 1)\n+#define COMMON\t\t(1U << 6)\n+#define REACH_SCRATCH\t(1U << 7)\n \n /*\n  * After sending this many \"have\"s if we do not get any new ACK , we\n@@ -1224,6 +1227,8 @@ static int send_fetch_request(struct fetch_negotiator *negotiator, int fd_out,\n \t\tpacket_buf_write(&req_buf, \"ofs-delta\");\n \tif (sideband_all)\n \t\tpacket_buf_write(&req_buf, \"sideband-all\");\n+\tif (args->acked_commits)\n+\t\tpacket_buf_write(&req_buf, \"wait-for-done\");\n \n \t/* Add shallow-info and deepen request */\n \tif (server_supports_feature(\"fetch\", \"shallow\", 0))\n@@ -1324,12 +1329,15 @@ enum common_found {\n \t * \"ready\" was received, indicating that the server is ready to send\n \t * the packfile without any further negotiation.\n \t */\n-\tREADY\n+\tREADY,\n+\n+\tCLOSURE\n };\n \n static enum common_found process_acks(struct fetch_negotiator *negotiator,\n \t\t\t\t      struct packet_reader *reader,\n-\t\t\t\t      struct oidset *common)\n+\t\t\t\t      struct oidset *common,\n+\t\t\t\t      struct object_array *negotiation_tips)\n {\n \t/* received */\n \tint received_ready = 0;\n@@ -1351,6 +1359,8 @@ static enum common_found process_acks(struct fetch_negotiator *negotiator,\n \t\t\t\tcommit = lookup_commit(the_repository, &oid);\n \t\t\t\tif (negotiator)\n \t\t\t\t\tnegotiator->ack(negotiator, commit);\n+\t\t\t\tif (negotiation_tips)\n+\t\t\t\t\tcommit->object.flags |= COMMON;\n \t\t\t}\n \t\t\tcontinue;\n \t\t}\n@@ -1379,6 +1389,13 @@ static enum common_found process_acks(struct fetch_negotiator *negotiator,\n \tif (!received_ready && reader->status != PACKET_READ_FLUSH)\n \t\tdie(_(\"expected no other sections to be sent after no 'ready'\"));\n \n+\tif (negotiation_tips) {\n+\t\tif (can_all_from_reach_with_flag(negotiation_tips, COMMON,\n+\t\t\t\t\t\t    REACH_SCRATCH, 0,\n+\t\t\t\t\t\t    GENERATION_NUMBER_ZERO))\n+\t\t\treturn CLOSURE;\n+\t}\n+\n \treturn received_ready ? READY :\n \t\t(received_ack ? COMMON_FOUND : NO_COMMON_FOUND);\n }\n@@ -1509,6 +1526,14 @@ static void do_check_stateless_delimiter(const struct fetch_pack_args *args,\n \t\t\t\t  _(\"git fetch-pack: expected response end packet\"));\n }\n \n+static int add_to_object_array(const struct object_id *oid, void *data)\n+{\n+\tstruct object_array *a = data;\n+\n+\tadd_object_array(parse_object(the_repository, oid), \"\", a);\n+\treturn 0;\n+}\n+\n static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,\n \t\t\t\t    int fd[2],\n \t\t\t\t    const struct ref *orig_ref,\n@@ -1527,6 +1552,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,\n \tstruct fetch_negotiator negotiator_alloc;\n \tstruct fetch_negotiator *negotiator;\n \tint seen_ack = 0;\n+\tstruct object_array negotiation_tips_object_array = OBJECT_ARRAY_INIT;\n \tstruct string_list packfile_uris = STRING_LIST_INIT_DUP;\n \tint i;\n \n@@ -1542,6 +1568,11 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,\n \t\treader.me = \"fetch-pack\";\n \t}\n \n+\tif (args->acked_commits)\n+\t\toid_array_for_each((struct oid_array *) args->negotiation_tips,\n+\t\t\t\t   add_to_object_array,\n+\t\t\t\t   &negotiation_tips_object_array);\n+\n \twhile (state != FETCH_DONE) {\n \t\tswitch (state) {\n \t\tcase FETCH_CHECK_LOCAL:\n@@ -1557,7 +1588,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,\n \t\t\t/* Filter 'ref' by 'sought' and those that aren't local */\n \t\t\tmark_complete_and_common_ref(negotiator, args, &ref);\n \t\t\tfilter_refs(args, &ref, sought, nr_sought);\n-\t\t\tif (everything_local(args, &ref))\n+\t\t\tif (!args->acked_commits && everything_local(args, &ref))\n \t\t\t\tstate = FETCH_DONE;\n \t\t\telse\n \t\t\t\tstate = FETCH_SEND_REQUEST;\n@@ -1574,6 +1605,11 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,\n \t\t\t\t\t\t    the_repository);\n \t\t\t}\n \t\t\tif (send_fetch_request(negotiator, fd[1], args, ref,\n+\t\t\t\t\t       /*\n+\t\t\t\t\t\t* If using acked_commits, we\n+\t\t\t\t\t\t* want an empty oidset here, so\n+\t\t\t\t\t\t* &common is used in all cases.\n+\t\t\t\t\t\t*/\n \t\t\t\t\t       &common,\n \t\t\t\t\t       &haves_to_send, &in_vain,\n \t\t\t\t\t       reader.use_sideband,\n@@ -1584,7 +1620,12 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,\n \t\t\tbreak;\n \t\tcase FETCH_PROCESS_ACKS:\n \t\t\t/* Process ACKs/NAKs */\n-\t\t\tswitch (process_acks(negotiator, &reader, &common)) {\n+\t\t\tswitch (process_acks(negotiator, &reader,\n+\t\t\t\t\t     args->acked_commits ? args->acked_commits : &common,\n+\t\t\t\t\t     args->acked_commits ? &negotiation_tips_object_array : NULL)) {\n+\t\t\tcase CLOSURE:\n+\t\t\t\tstate = FETCH_DONE;\n+\t\t\t\tbreak;\n \t\t\tcase READY:\n \t\t\t\t/*\n \t\t\t\t * Don't check for response delimiter; get_pack() will\ndiff --git a/fetch-pack.h b/fetch-pack.h\nindex 736a3dae46..3fc8ba6126 100644\n--- a/fetch-pack.h\n+++ b/fetch-pack.h\n@@ -23,6 +23,12 @@ struct fetch_pack_args {\n \t */\n \tconst struct oid_array *negotiation_tips;\n \n+\t/*\n+\t * If not NULL, fetch-pack will not fetch any packs but will only store\n+\t * in here commits ACKed by the server during negotiation.\n+\t */\n+\tstruct oidset *acked_commits;\n+\n \tunsigned deepen_relative:1;\n \tunsigned quiet:1;\n \tunsigned keep_pack:1;\ndiff --git a/object.h b/object.h\nindex 59daadce21..4806fa8e66 100644\n--- a/object.h\n+++ b/object.h\n@@ -60,7 +60,7 @@ struct object_array {\n /*\n  * object flag allocation:\n  * revision.h:               0---------10         15             23------26\n- * fetch-pack.c:             01\n+ * fetch-pack.c:             01    67\n  * negotiator/default.c:       2--5\n  * walker.c:                 0-2\n  * upload-pack.c:                4       11-----14  16-----19\ndiff --git a/send-pack.c b/send-pack.c\nindex 9045f8a082..f846b408c7 100644\n--- a/send-pack.c\n+++ b/send-pack.c\n@@ -56,7 +56,7 @@ static void feed_object(const struct object_id *oid, FILE *fh, int negative)\n /*\n  * Make a pack stream and spit it out into file descriptor fd\n  */\n-static int pack_objects(int fd, struct ref *refs, struct oid_array *extra, struct send_pack_args *args)\n+static int pack_objects(int fd, struct ref *refs, struct oid_array *advertised, struct oid_array *negotiated, struct send_pack_args *args)\n {\n \t/*\n \t * The child becomes pack-objects --revs; we feed\n@@ -94,8 +94,10 @@ static int pack_objects(int fd, struct ref *refs, struct oid_array *extra, struc\n \t * parameters by writing to the pipe.\n \t */\n \tpo_in = xfdopen(po.in, \"w\");\n-\tfor (i = 0; i < extra->nr; i++)\n-\t\tfeed_object(&extra->oid[i], po_in, 1);\n+\tfor (i = 0; i < advertised->nr; i++)\n+\t\tfeed_object(&advertised->oid[i], po_in, 1);\n+\tfor (i = 0; i < negotiated->nr; i++)\n+\t\tfeed_object(&negotiated->oid[i], po_in, 1);\n \n \twhile (refs) {\n \t\tif (!is_null_oid(&refs->old_oid))\n@@ -409,11 +411,49 @@ static void reject_invalid_nonce(const char *nonce, int len)\n \t}\n }\n \n+static void get_commons_through_negotiation(const char *url,\n+\t\t\t\t\t    const struct ref *remote_refs,\n+\t\t\t\t\t    struct oid_array *commons)\n+{\n+\tstruct child_process child = CHILD_PROCESS_INIT;\n+\tconst struct ref *ref;\n+\tint len = the_hash_algo->hexsz + 1; /* hash + NL */\n+\n+\tchild.git_cmd = 1;\n+\tchild.no_stdin = 1;\n+\tchild.out = -1;\n+\tstrvec_pushl(&child.args, \"fetch-pack\", \"--negotiate-only\", NULL);\n+\tfor (ref = remote_refs; ref; ref = ref->next)\n+\t\tstrvec_pushf(&child.args, \"--negotiation-tip=%s\", oid_to_hex(&ref->new_oid));\n+\tstrvec_push(&child.args, url);\n+\n+\tif (start_command(&child))\n+\t\tdie(_(\"send-pack: unable to fork off fetch-pack subprocess\"));\n+\n+\tdo {\n+\t\tchar hex_hash[GIT_MAX_HEXSZ + 1];\n+\t\tint read_len = read_in_full(child.out, hex_hash, len);\n+\t\tstruct object_id oid;\n+\t\tconst char *end;\n+\n+\t\tif (!read_len)\n+\t\t\treturn;\n+\t\tif (read_len != len)\n+\t\t\tdie(\"invalid length read %d\", read_len);\n+\t\tif (parse_oid_hex(hex_hash, &oid, &end) || *end != '\\n')\n+\t\t\tdie(\"invalid hash\");\n+\t\toid_array_append(commons, &oid);\n+\t} while (1);\n+\n+\tfinish_command(&child);\n+}\n+\n int send_pack(struct send_pack_args *args,\n \t      int fd[], struct child_process *conn,\n \t      struct ref *remote_refs,\n \t      struct oid_array *extra_have)\n {\n+\tstruct oid_array commons = OID_ARRAY_INIT;\n \tint in = fd[0];\n \tint out = fd[1];\n \tstruct strbuf req_buf = STRBUF_INIT;\n@@ -437,6 +477,9 @@ int send_pack(struct send_pack_args *args,\n \tconst char *push_cert_nonce = NULL;\n \tstruct packet_reader reader;\n \n+\tif (getenv(\"GIT_TEST_PUSH_NEGOTIATION\"))\n+\t\tget_commons_through_negotiation(args->url, remote_refs, &commons);\n+\n \tgit_config_get_bool(\"transfer.advertisesid\", &advertise_sid);\n \n \t/* Does the other end support the reporting? */\n@@ -625,7 +668,7 @@ int send_pack(struct send_pack_args *args,\n \t\t\t   PACKET_READ_DIE_ON_ERR_PACKET);\n \n \tif (need_pack_data && cmds_sent) {\n-\t\tif (pack_objects(out, remote_refs, extra_have, args) < 0) {\n+\t\tif (pack_objects(out, remote_refs, extra_have, &commons, args) < 0) {\n \t\t\tif (args->stateless_rpc)\n \t\t\t\tclose(out);\n \t\t\tif (git_connection_is_socket(conn))\ndiff --git a/t/t5510-fetch.sh b/t/t5510-fetch.sh\nindex 42f5503004..3b87a411a5 100755\n--- a/t/t5510-fetch.sh\n+++ b/t/t5510-fetch.sh\n@@ -1214,6 +1214,25 @@ test_expect_success '--negotiation-tip understands abbreviated SHA-1' '\n \tcheck_negotiation_tip\n '\n \n+test_expect_success '--negotiate-only' '\n+\trm -rf server client trace &&\n+\n+\tgit init server &&\n+\ttest_commit -C server one &&\n+\ttest_commit -C server two &&\n+\n+\tgit clone \"file://$(pwd)/server\" client &&\n+\ttest_commit -C client three &&\n+\n+\tgit -C client for-each-ref &&\n+\tgit -C client fetch-pack \\\n+\t\t--negotiate-only \\\n+\t\t--negotiation-tip=$(git -C client rev-parse HEAD) \\\n+\t\t\"file://$(pwd)/server\" >out &&\n+\tCOMMON=$(git -C server rev-parse two) &&\n+\tgrep \"$COMMON\" out\n+'\n+\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \ndiff --git a/t/t5516-fetch-push.sh b/t/t5516-fetch-push.sh\nindex 15262b4192..684f4a7fc8 100755\n--- a/t/t5516-fetch-push.sh\n+++ b/t/t5516-fetch-push.sh\n@@ -191,6 +191,30 @@ test_expect_success 'fetch with pushInsteadOf (should not rewrite)' '\n \t)\n '\n \n+grep_wrote () {\n+\tobject_count=$1\n+\tfile_name=$2\n+\tgrep 'write_pack_file/wrote.*\"value\":\"'$1'\"' $2\n+}\n+\n+\n+test_expect_success 'push with negotiation' '\n+\tmk_empty testrepo &&\n+\tgit push testrepo $the_first_commit:refs/remotes/origin/first_commit &&\n+\tgit -C testrepo config receive.hideRefs refs/remotes/origin/first_commit &&\n+\techo now pushing without negotiation &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/event\" git push testrepo refs/heads/main:refs/remotes/origin/main &&\n+\tgrep_wrote 5 event && # 2 commits, 2 trees, 1 blob\n+\n+\trm event &&\n+\tmk_empty testrepo &&\n+\tgit push testrepo $the_first_commit:refs/remotes/origin/first_commit &&\n+\tgit -C testrepo config receivePack.hideRefs refs/remotes/origin/first_commit &&\n+\techo now pushing with negotiation &&\n+\tGIT_TEST_PUSH_NEGOTIATION=1 GIT_TRACE2_EVENT=\"$(pwd)/event\" git push testrepo refs/heads/main:refs/remotes/origin/main &&\n+\tgrep_wrote 2 event # 1 commit, 1 tree\n+'\n+\n test_expect_success 'push without wildcard' '\n \tmk_empty testrepo &&\n \ndiff --git a/transport.c b/transport.c\nindex 679a35e7c1..0c2925bb12 100644\n--- a/transport.c\n+++ b/transport.c\n@@ -370,6 +370,7 @@ static int fetch_refs_via_pack(struct transport *transport,\n \targs.stateless_rpc = transport->stateless_rpc;\n \targs.server_options = transport->server_options;\n \targs.negotiation_tips = data->options.negotiation_tips;\n+\targs.acked_commits = data->options.acked_commits;\n \n \tif (!data->got_remote_heads) {\n \t\tint i;\ndiff --git a/transport.h b/transport.h\nindex 24558c027d..b6659f8aa6 100644\n--- a/transport.h\n+++ b/transport.h\n@@ -46,6 +46,11 @@ struct git_transport_options {\n \t * transport_set_option().\n \t */\n \tstruct oid_array *negotiation_tips;\n+\n+\t/*\n+\t * See fetch-pack.h for more information.\n+\t */\n+\tstruct oidset *acked_commits;\n };\n \n enum transport_family {\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 4ab55ce2b5..bdca9daf7d 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -103,6 +103,7 @@ struct upload_pack_data {\n \tunsigned use_ofs_delta : 1;\n \tunsigned no_progress : 1;\n \tunsigned use_include_tag : 1;\n+\tunsigned wait_for_done : 1;\n \tunsigned allow_filter : 1;\n \tunsigned allow_filter_fallback : 1;\n \tunsigned long tree_filter_max_depth;\n@@ -1503,6 +1504,10 @@ static void process_args(struct packet_reader *request,\n \t\t\tdata->done = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"wait-for-done\")) {\n+\t\t\tdata->wait_for_done = 1;\n+\t\t\tcontinue;\n+\t\t}\n \n \t\t/* Shallow related arguments */\n \t\tif (process_shallow(arg, &data->shallows))\n@@ -1585,7 +1590,7 @@ static int send_acks(struct upload_pack_data *data, struct oid_array *acks)\n \t\t\t\t    oid_to_hex(&acks->oid[i]));\n \t}\n \n-\tif (ok_to_give_up(data)) {\n+\tif (!data->wait_for_done && ok_to_give_up(data)) {\n \t\t/* Send Ready */\n \t\tpacket_writer_write(&data->writer, \"ready\\n\");\n \t\treturn 1;\n@@ -1675,10 +1680,13 @@ int upload_pack_v2(struct repository *r, struct strvec *keys,\n \t\tcase FETCH_PROCESS_ARGS:\n \t\t\tprocess_args(request, &data);\n \n-\t\t\tif (!data.want_obj.nr) {\n+\t\t\tif (!data.want_obj.nr && !data.wait_for_done) {\n \t\t\t\t/*\n-\t\t\t\t * Request didn't contain any 'want' lines,\n-\t\t\t\t * guess they didn't want anything.\n+\t\t\t\t * Request didn't contain any 'want' lines (and\n+\t\t\t\t * the request does not contain\n+\t\t\t\t * \"wait-for-done\", in which it is reasonable\n+\t\t\t\t * to just send 'have's without 'want's); guess\n+\t\t\t\t * they didn't want anything.\n \t\t\t\t */\n \t\t\t\tstate = FETCH_DONE;\n \t\t\t} else if (data.haves.nr) {\n-- \n2.30.0.478.g8a0d178c01-goog\n\n"},{"id":"417267","messageId":"xmqqwnv6gnuq.fsf@gitster.g","threadId":"55166","inReplyTo":"20210218012100.928957-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] push: perform negotiation before sending packfile","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-18T01:34:53Z","receivedAt":"2021-02-18T01:35:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> The idea of adding negotiation to push has been floating around for a\n> while. Here's my implementation of my idea of reusing a lot of the fetch\n> mechanism to perform the negotiation.\n\nFinally? Yay!\n\n> The basic idea is that when a client pushes, the client will first\n> perform the negotiation steps that it normally does during a fetch,\n> except that it does not send any \"want\"s and it only uses the commits to\n> be pushed as negotiation tips (instead of all refs). Once the client has\n> received enough ACKs that all ancestral paths from all tips to the\n> original orphans are blocked by ACKed commits, it will proceed with the\n> push, using this information to determine the contents of the\n> to-be-pushed packfile. (This check is done by the server when doing a\n> user-triggered fetch.)\n\nSo when pushing 'HEAD' to some ref, we say \"I have HEAD^{commit},\nHEAD^^, HEAD^^^, ...\" and they keep saying \"never heard of it\" for\neach of them until they find \"ah, I know that one\" with an ACK, at\nwhich point we can stop traversing our side of the history behind\nthat acked commit (because everything behind it is common between\nus). And that way, we know what we do not have to send (i.e. what\nwe should use as the negative ends of \"rev-list --objects A..B\";\ntheir ACK lets us discover \"A\").\n\nDo we take advantage of the ref advertisement the other side\nperform, or is this v2 only and we even skip ls-refs?\n\nWhat do you mean by an \"orphan\", though?  Except for that part, I\nthink what you wrote the above makes quite a lot of sense.\n\nWhen we have an \"--allow-unrelated-histories\" merge with a history\nthey've never heard of, we'd end up digging down to the root of the\nunrelated side history with \"have/nack\" exchange.  On the fetch\nside, we have \"give up with too many nack\" band-aid.  Do we inherit\nthe same from the fetch side?\n\n>  - Do we need statistics in the commit message to show the performance\n>    gains?\n\nNot until we see the thing fully working, I would say.\n\n>  - Anything else that comes up upon more scrutiny\n>\n> Any comments are welcome, especially if you have ideas about the overall\n> design or implementation, and/or if you've thought about similar things\n> before.\n\nI'll have more comments after reading the code, but that will happen\nmuch later tonight.\n\nThanks.\n"},{"id":"417354","messageId":"xmqqy2fldsy4.fsf@gitster.g","threadId":"55166","inReplyTo":"xmqqwnv6gnuq.fsf@gitster.g","subject":"Re: [RFC PATCH] push: perform negotiation before sending packfile","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-18T20:25:23Z","receivedAt":"2021-02-18T20:26:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n>> Any comments are welcome, especially if you have ideas about the overall\n>> design or implementation, and/or if you've thought about similar things\n>> before.\n\nI think that it is a good way to prototype by adding a separate\nsession with the upload-pack to only learn about what is common\nbefore talking to the receive-pack, presumably running on the same\nrepository and may share common view with the previous upload-pack.\n\nAnd the code seems to implement the idea just fine.  I wonder how\nmuch we can cut out the unnecessary resource usage in pathological\ncases with this approach.\n\n - If the target ref got rewound, with the current send-pack\n   approach, we may not find any common commit, or we may end up\n   using a mediocre one---that would result in unnecessary packdata\n   transfer, which we may be able to cut down significantly.\n\n   I thought you guys have some server-side hacks to send a bit\n   stale commit as a \"fake\" ref to help with this situation, though.\n   So the comparison is really between how much each of these two\n   approaches helps.\n\n - With this approach, we can cut down the initial ref advertisement\n   from the receiving end to the minimum.  The protocol with\n   negotiation could work correctly without receiving end\n   advertising no refs, but I suspect that it would be very common\n   in a publishing repository (not a shared everybody-pushes-into\n   repository) that the tip of the target repository is known by the\n   pusher, and it may help such a case to know where the ref being\n   updated with this push originally points at.  But even in such a\n   case, additional negotiation may help---the target branch may\n   have not advanced, but may of the side branches the pusher have\n   merged into the commit being pushed to the target branch may\n   already be known by the receiver.\n\nFor a real implementation, I think we'd want to do the negotiation\ninside the conversation between send-pack and receive-pack, so that\nwhat is agreed to be common between two parties will not shift in\nthe middle (in the same spirit that upload-pack grabs all the\nrelevant refs first, advertises them, negotiates what is common and\ncreates a pack, all using the same worldview of where the tips of\nrefs are throughout the process, even if some refs change in the\nmeantime).\n\nThanks for a fun read.\n"},{"id":"417358","messageId":"xmqqlfbldprt.fsf@gitster.g","threadId":"55166","inReplyTo":"xmqqy2fldsy4.fsf@gitster.g","subject":"Re: [RFC PATCH] push: perform negotiation before sending packfile","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-18T21:33:58Z","receivedAt":"2021-02-18T21:34:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n>  - With this approach, we can cut down the initial ref advertisement\n>    from the receiving end to the minimum.  The protocol with\n>    negotiation could work correctly without receiving end\n>    advertising no refs, but I suspect that it would be very common\n>    in a publishing repository (not a shared everybody-pushes-into\n>    repository) that the tip of the target repository is known by the\n>    pusher, and it may help such a case to know where the ref being\n>    updated with this push originally points at.  But even in such a\n>    case, additional negotiation may help---the target branch may\n>    have not advanced, but may of the side branches the pusher have\n>    merged into the commit being pushed to the target branch may\n>    already be known by the receiver.\n\nAddendum.  The original push protocol where the pusher learns all\nthe tips of refs the receiver has cuts down the resulting packdata\ntransfer in such a \"side branches already known by the receiver,\nonly the fact that they were merged to the target branch is new\"\ncase.  The pain only starts happening when we try to reduce the\nadvertisement made by the receiver.\n\nAs the \"negotiation\" is more targetted for the ref that actually is\nbeing pushed (as opposed to the blanket \"here is everything I have\"\nthat can get unreasonably big), I think the idea to introduce the\nsame common ancestor discovery that happens on the \"fetch\" side, and\nto share the code with the \"fetch\" side that has been battle tested,\nis a great one.\n"},{"id":"417371","messageId":"20210218230248.1165266-1-jonathantanmy@google.com","threadId":"55166","inReplyTo":"xmqqwnv6gnuq.fsf@gitster.g","subject":"Re: [RFC PATCH] push: perform negotiation before sending packfile","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2021-02-18T23:02:48Z","receivedAt":"2021-02-18T23:03:42Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> Jonathan Tan <jonathantanmy@google.com> writes:\n> \n> > The idea of adding negotiation to push has been floating around for a\n> > while. Here's my implementation of my idea of reusing a lot of the fetch\n> > mechanism to perform the negotiation.\n> \n> Finally? Yay!\n\nThanks.\n\n> > The basic idea is that when a client pushes, the client will first\n> > perform the negotiation steps that it normally does during a fetch,\n> > except that it does not send any \"want\"s and it only uses the commits to\n> > be pushed as negotiation tips (instead of all refs). Once the client has\n> > received enough ACKs that all ancestral paths from all tips to the\n> > original orphans are blocked by ACKed commits, it will proceed with the\n> > push, using this information to determine the contents of the\n> > to-be-pushed packfile. (This check is done by the server when doing a\n> > user-triggered fetch.)\n> \n> So when pushing 'HEAD' to some ref, we say \"I have HEAD^{commit},\n> HEAD^^, HEAD^^^, ...\" and they keep saying \"never heard of it\" for\n> each of them until they find \"ah, I know that one\" with an ACK, at\n> which point we can stop traversing our side of the history behind\n> that acked commit (because everything behind it is common between\n> us). And that way, we know what we do not have to send (i.e. what\n> we should use as the negative ends of \"rev-list --objects A..B\";\n> their ACK lets us discover \"A\").\n\nYes, that's right.\n\n> Do we take advantage of the ref advertisement the other side\n> perform, or is this v2 only and we even skip ls-refs?\n\nMy plan is to make it v2-only, but I don't think that there are\ntechnical limitations in adding it to v0. I'm planning to skip ls-refs\n(the current proof-of-concept code still calls ls-refs but doesn't use\nits results). If we need to take advantage of the ref advertisement, we\ncould just use push's one.\n\n> What do you mean by an \"orphan\", though?  Except for that part, I\n> think what you wrote the above makes quite a lot of sense.\n\nBy \"orphan\" I meant the commits that don't have any parents - so, the\nroot commits.\n\n> When we have an \"--allow-unrelated-histories\" merge with a history\n> they've never heard of, we'd end up digging down to the root of the\n> unrelated side history with \"have/nack\" exchange.  On the fetch\n> side, we have \"give up with too many nack\" band-aid.  Do we inherit\n> the same from the fetch side?\n\nYes. (But like fetch, this \"in vain\" check triggers only after the first\nACK.)\n\n> >  - Do we need statistics in the commit message to show the performance\n> >    gains?\n> \n> Not until we see the thing fully working, I would say.\n\nOK.\n"},{"id":"417377","messageId":"20210219004242.1179999-1-jonathantanmy@google.com","threadId":"55166","inReplyTo":"xmqqy2fldsy4.fsf@gitster.g","subject":"Re: [RFC PATCH] push: perform negotiation before sending packfile","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2021-02-19T00:42:42Z","receivedAt":"2021-02-19T00:43:27Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> For a real implementation, I think we'd want to do the negotiation\n> inside the conversation between send-pack and receive-pack, so that\n> what is agreed to be common between two parties will not shift in\n> the middle (in the same spirit that upload-pack grabs all the\n> relevant refs first, advertises them, negotiates what is common and\n> creates a pack, all using the same worldview of where the tips of\n> refs are throughout the process, even if some refs change in the\n> meantime).\n\nUpload-pack does that for protocol v0 ssh:// and git:// but not\nhttp(s)://, and does not do that for protocol v2, I believe.\n\nIf we were to do that, I don't think it would work for the transports\nthat have are stateless (e.g. HTTP). Also, this seems like it would\ninvolve a significant reworking of how the server serves (receive-pack\nwould need to know to communicate just like upload-pack does temporarily\nbefore proceeding with its usual behavior, and the client would need to\nlearn this new way - as opposed to the idea in this patch to do it\nseparately and reuse the already existing fetch and push mechanisms). I\nthink the greater complexity is not worth it for something that won't\nwork in HTTP, but I'm open to other opinions.\n"},{"id":"417426","messageId":"xmqqzgzza0a1.fsf@gitster.g","threadId":"55166","inReplyTo":"20210219004242.1179999-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] push: perform negotiation before sending packfile","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-20T03:25:10Z","receivedAt":"2021-02-20T03:26:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n>> For a real implementation, I think we'd want to do the negotiation\n>> inside the conversation between send-pack and receive-pack, so that\n>> what is agreed to be common between two parties will not shift in\n>> the middle (in the same spirit that upload-pack grabs all the\n>> relevant refs first, advertises them, negotiates what is common and\n>> creates a pack, all using the same worldview of where the tips of\n>> refs are throughout the process, even if some refs change in the\n>> meantime).\n>\n> Upload-pack does that for protocol v0 ssh:// and git:// but not\n> http(s)://, and does not do that for protocol v2, I believe.\n>\n> If we were to do that, I don't think it would work for the transports\n> that have are stateless (e.g. HTTP).\n\nYeah, I consider it a bug in the \"stateless\" hack, though, and v2\nsomehow chose to take the common denominator to propagate the same\nbug to protocols that are otherwise capable of being stateful.\n\nIn any case, I think I heard in another response from you that you\nplan to do only v2, and I think that is OK.  Perhaps we can have a\nseparate service (like 'ls-refs' is a service that can be used\nindependent of the 'fetch' service in v2, and can be used by\nsomebody trying to 'push') 'negotiate' that can become a separate\nthing, so that \"fetch<->upload-pack\" conversation would become\nls-refs plus negotiate plus fetch, while \"push<->receive-pack\"\nconversation would become ls-refs plus negotiate plus push?\n\nThanks.\n"},{"id":"417492","messageId":"20210222200146.1393467-1-jonathantanmy@google.com","threadId":"55166","inReplyTo":"xmqqzgzza0a1.fsf@gitster.g","subject":"Re: [RFC PATCH] push: perform negotiation before sending packfile","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2021-02-22T20:01:46Z","receivedAt":"2021-02-22T20:02:50Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> Jonathan Tan <jonathantanmy@google.com> writes:\n> \n> >> For a real implementation, I think we'd want to do the negotiation\n> >> inside the conversation between send-pack and receive-pack, so that\n> >> what is agreed to be common between two parties will not shift in\n> >> the middle (in the same spirit that upload-pack grabs all the\n> >> relevant refs first, advertises them, negotiates what is common and\n> >> creates a pack, all using the same worldview of where the tips of\n> >> refs are throughout the process, even if some refs change in the\n> >> meantime).\n> >\n> > Upload-pack does that for protocol v0 ssh:// and git:// but not\n> > http(s)://, and does not do that for protocol v2, I believe.\n> >\n> > If we were to do that, I don't think it would work for the transports\n> > that have are stateless (e.g. HTTP).\n> \n> Yeah, I consider it a bug in the \"stateless\" hack, though, and v2\n> somehow chose to take the common denominator to propagate the same\n> bug to protocols that are otherwise capable of being stateful.\n> \n> In any case, I think I heard in another response from you that you\n> plan to do only v2, and I think that is OK.  Perhaps we can have a\n> separate service (like 'ls-refs' is a service that can be used\n> independent of the 'fetch' service in v2, and can be used by\n> somebody trying to 'push') 'negotiate' that can become a separate\n> thing, so that \"fetch<->upload-pack\" conversation would become\n> ls-refs plus negotiate plus fetch,\n\nThat does make sense conceptually, although the fact that every\nnegotiate step could potentially also include a packfile (when fetching,\nas we do today) makes things more complicated. (Besides the fact that we\nwould be making another change in the protocol.)\n\n> while \"push<->receive-pack\"\n> conversation would become ls-refs plus negotiate plus push?\n> \n> Thanks.\n\nI guess the idea is to have a push that does not start with a ref\nadvertisement, therefore making everything more modular? That sounds\nreasonable (and does mean that if we ever decide that pushes with\nnegotiate don't need ref advertisement at all, we can just remove the\nls-refs part), but this sounds like it would require some sort of v2 for\npush - which is another discussion topic.\n"},{"id":"417496","messageId":"xmqq8s7f7pqb.fsf@gitster.g","threadId":"55166","inReplyTo":"20210222200146.1393467-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] push: perform negotiation before sending packfile","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-22T21:32:44Z","receivedAt":"2021-02-22T21:33:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> I guess the idea is to have a push that does not start with a ref\n> advertisement, therefore making everything more modular?\n\nYes, making things modular and reusable would be valuable---if the\nfetch side were already structured like I dreamed in the message you\nare responding to with a separate 'negotiate' service, the RFC patch\nwould have looked much nicer.\n\nI am also interested in seeing was not to require a new connection\nfor an extra roundtrip.\n\nThanks.\n\n"}]}