{"thread":{"id":"54833","subject":"[PATCH] checkout: send commit provenance during prefetch","startedAt":"2020-12-15T20:02:53Z","lastAt":"2020-12-16T18:50:50Z","messageCount":3,"participants":["Jonathan Tan","Derrick Stolee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"412292","messageId":"20201215200207.1083655-1-jonathantanmy@google.com","threadId":"54833","inReplyTo":null,"subject":"[PATCH] checkout: send commit provenance during prefetch","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-12-15T20:02:07Z","receivedAt":"2020-12-15T20:02:53Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"In a partial clone, whenever Git needs a missing object, it will fetch\nit from the repo's promisor remote(s), sometimes as part of a bulk\nprefetch. Currently, if the server handling such fetches does not accept\nrequests for objects unless the objects are reachable, it needs to\ncompute reachability from all refs.\n\nThis can be improved by sending the commit from which the prefetch\nrequest came - a server that understands this would then only need to\ncheck that this commit is reachable, and check that the object is\nreachable from that commit.\n\nTherefore, teach the partial clone fetching mechanism to support a\n\"provenance\" argument, and plumb the commit provenance from checkout to\nthe partial clone fetching mechanism.\n\nIn the future, other commands can be similarly upgraded. Other possible\nfuture improvements include better diagnostic messages when a prefetch\nfails.\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\nSending a commit hint in this situation is something we've been\ndiscussing at $DAYJOB, so here's a preliminary version - the client side\nis done, but neither the server side nor the exact protocol details are\nfinished. Protocol-wise, in this patch, I'm just sending the provenance\ncommit as a server option.\n\nThis essentially splits reachability-of-blob, which almost certainly\nrequires loading a bitmap, into 2 parts: reachability-of-commit (which,\nfrom my limited experience, can be more quickly done using a regular\nobject walk) and reachability-of-blob-from-commit (which, at worst,\nrequires fewer bitmaps to be loaded). I don't have timings for how it\nworks in practice, though.\n\nI'm also not sure if the final version should have the client declare\nthat all blobs are reachable from the root tree(s) of the provenance\ncommit(s), or merely that all blobs are reachable from the provenance\ncommit(s) (that is, including their ancestors).\n\nI'm sending this out early in the hope that other people using partial\nclone will chime in.\n---\n builtin/checkout.c       |  4 ++++\n builtin/index-pack.c     |  2 +-\n builtin/pack-objects.c   |  2 +-\n diff.c                   |  2 +-\n diffcore-rename.c        |  2 +-\n promisor-remote.c        | 12 +++++++++---\n promisor-remote.h        |  3 ++-\n sha1-file.c              |  2 +-\n t/t5616-partial-clone.sh |  7 +++++--\n unpack-trees.c           |  3 ++-\n unpack-trees.h           |  7 +++++++\n 11 files changed, 34 insertions(+), 12 deletions(-)\n\ndiff --git a/builtin/checkout.c b/builtin/checkout.c\nindex 9b82119129..7f9fd65808 100644\n--- a/builtin/checkout.c\n+++ b/builtin/checkout.c\n@@ -634,6 +634,8 @@ static int reset_tree(struct tree *tree, const struct checkout_opts *o,\n \topts.verbose_update = o->show_progress;\n \topts.src_index = &the_index;\n \topts.dst_index = &the_index;\n+\topts.provenance_commit =\n+\t\tinfo->commit ? &info->commit->object.oid : NULL;\n \tinit_checkout_metadata(&opts.meta, info->refname,\n \t\t\t       info->commit ? &info->commit->object.oid : &null_oid,\n \t\t\t       NULL);\n@@ -724,6 +726,8 @@ static int merge_working_tree(const struct checkout_opts *opts,\n \t\ttopts.quiet = opts->merge && old_branch_info->commit;\n \t\ttopts.verbose_update = opts->show_progress;\n \t\ttopts.fn = twoway_merge;\n+\t\ttopts.provenance_commit = new_branch_info->commit ?\n+\t\t\t&new_branch_info->commit->object.oid : NULL;\n \t\tinit_checkout_metadata(&topts.meta, new_branch_info->refname,\n \t\t\t\t       new_branch_info->commit ?\n \t\t\t\t       &new_branch_info->commit->object.oid :\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 4b8d86e0ad..83801826d6 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1402,7 +1402,7 @@ static void fix_unresolved_deltas(struct hashfile *f)\n \t\t\toid_array_append(&to_fetch, &d->oid);\n \t\t}\n \t\tpromisor_remote_get_direct(the_repository,\n-\t\t\t\t\t   to_fetch.oid, to_fetch.nr);\n+\t\t\t\t\t   to_fetch.oid, to_fetch.nr, NULL);\n \t\toid_array_clear(&to_fetch);\n \t}\n \ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 5617c01b5a..741dcc9a24 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1720,7 +1720,7 @@ static void prefetch_to_pack(uint32_t object_index_start) {\n \t\toid_array_append(&to_fetch, &entry->idx.oid);\n \t}\n \tpromisor_remote_get_direct(the_repository,\n-\t\t\t\t   to_fetch.oid, to_fetch.nr);\n+\t\t\t\t   to_fetch.oid, to_fetch.nr, NULL);\n \toid_array_clear(&to_fetch);\n }\n \ndiff --git a/diff.c b/diff.c\nindex 643f4f3f6d..68491fc398 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -6622,7 +6622,7 @@ void diff_queued_diff_prefetch(void *repository)\n \t/*\n \t * NEEDSWORK: Consider deduplicating the OIDs sent.\n \t */\n-\tpromisor_remote_get_direct(repo, to_fetch.oid, to_fetch.nr);\n+\tpromisor_remote_get_direct(repo, to_fetch.oid, to_fetch.nr, NULL);\n \n \toid_array_clear(&to_fetch);\n }\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex d367a6d244..ebc65fa272 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -161,7 +161,7 @@ static void prefetch(void *prefetch_options)\n \t\tdiff_add_if_missing(options->repo, &to_fetch,\n \t\t\t\t    rename_src[i].p->one);\n \t}\n-\tpromisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr);\n+\tpromisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr, NULL);\n \toid_array_clear(&to_fetch);\n }\n \ndiff --git a/promisor-remote.c b/promisor-remote.c\nindex 3c572b1c81..ee44d1334e 100644\n--- a/promisor-remote.c\n+++ b/promisor-remote.c\n@@ -14,7 +14,8 @@ void set_repository_format_partial_clone(char *partial_clone)\n \n static int fetch_objects(const char *remote_name,\n \t\t\t const struct object_id *oids,\n-\t\t\t int oid_nr)\n+\t\t\t int oid_nr,\n+\t\t\t struct object_id *provenance_commit)\n {\n \tstruct child_process child = CHILD_PROCESS_INIT;\n \tint i;\n@@ -26,6 +27,9 @@ static int fetch_objects(const char *remote_name,\n \t\t     \"fetch\", remote_name, \"--no-tags\",\n \t\t     \"--no-write-fetch-head\", \"--recurse-submodules=no\",\n \t\t     \"--filter=blob:none\", \"--stdin\", NULL);\n+\tif (provenance_commit)\n+\t\tstrvec_pushf(&child.args, \"--server-option=provenance=%s\",\n+\t\t\t     oid_to_hex(provenance_commit));\n \tif (start_command(&child))\n \t\tdie(_(\"promisor-remote: unable to fork off fetch subprocess\"));\n \tchild_in = xfdopen(child.in, \"w\");\n@@ -224,7 +228,8 @@ static int remove_fetched_oids(struct repository *repo,\n \n int promisor_remote_get_direct(struct repository *repo,\n \t\t\t       const struct object_id *oids,\n-\t\t\t       int oid_nr)\n+\t\t\t       int oid_nr,\n+\t\t\t       struct object_id *provenance_commit)\n {\n \tstruct promisor_remote *r;\n \tstruct object_id *remaining_oids = (struct object_id *)oids;\n@@ -238,7 +243,8 @@ int promisor_remote_get_direct(struct repository *repo,\n \tpromisor_remote_init();\n \n \tfor (r = promisors; r; r = r->next) {\n-\t\tif (fetch_objects(r->name, remaining_oids, remaining_nr) < 0) {\n+\t\tif (fetch_objects(r->name, remaining_oids, remaining_nr,\n+\t\t\t\t  provenance_commit) < 0) {\n \t\t\tif (remaining_nr == 1)\n \t\t\t\tcontinue;\n \t\t\tremaining_nr = remove_fetched_oids(repo, &remaining_oids,\ndiff --git a/promisor-remote.h b/promisor-remote.h\nindex c7a14063c5..44d1b152e6 100644\n--- a/promisor-remote.h\n+++ b/promisor-remote.h\n@@ -30,7 +30,8 @@ int has_promisor_remote(void);\n  */\n int promisor_remote_get_direct(struct repository *repo,\n \t\t\t       const struct object_id *oids,\n-\t\t\t       int oid_nr);\n+\t\t\t       int oid_nr,\n+\t\t\t       struct object_id *provenance_commit);\n \n /*\n  * This should be used only once from setup.c to set the value we got\ndiff --git a/sha1-file.c b/sha1-file.c\nindex c3c49d2fa5..51ed339a0c 100644\n--- a/sha1-file.c\n+++ b/sha1-file.c\n@@ -1534,7 +1534,7 @@ static int do_oid_object_info_extended(struct repository *r,\n \t\t\t * promisor_remote_get_direct(), such that arbitrary\n \t\t\t * repositories work.\n \t\t\t */\n-\t\t\tpromisor_remote_get_direct(r, real, 1);\n+\t\t\tpromisor_remote_get_direct(r, real, 1, NULL);\n \t\t\talready_retried = 1;\n \t\t\tcontinue;\n \t\t}\ndiff --git a/t/t5616-partial-clone.sh b/t/t5616-partial-clone.sh\nindex 2ea66205cf..4b290060f5 100755\n--- a/t/t5616-partial-clone.sh\n+++ b/t/t5616-partial-clone.sh\n@@ -56,11 +56,14 @@ test_expect_success 'verify that .promisor file contains refs fetched' '\n \n # checkout master to force dynamic object fetch of blobs at HEAD.\n test_expect_success 'verify checkout with dynamic object fetch' '\n+\trm -f trace &&\n \tgit -C pc1 rev-list --quiet --objects --missing=print HEAD >observed &&\n \ttest_line_count = 4 observed &&\n-\tgit -C pc1 checkout master &&\n+\tGIT_TRACE_PACKET=\"$(pwd)/trace\" git -C pc1 checkout master &&\n \tgit -C pc1 rev-list --quiet --objects --missing=print HEAD >observed &&\n-\ttest_line_count = 0 observed\n+\ttest_line_count = 0 observed &&\n+\tHEAD_HASH=\"$(git -C pc1 rev-parse HEAD)\" &&\n+\tgrep \"server-option=provenance=$HEAD_HASH\" trace\n '\n \n # create new commits in \"src\" repo to establish a blame history on file.1.txt\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 323280dd48..d5dc06a70a 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -457,7 +457,8 @@ static int check_updates(struct unpack_trees_options *o,\n \t\t\toid_array_append(&to_fetch, &ce->oid);\n \t\t}\n \t\tpromisor_remote_get_direct(the_repository,\n-\t\t\t\t\t   to_fetch.oid, to_fetch.nr);\n+\t\t\t\t\t   to_fetch.oid, to_fetch.nr,\n+\t\t\t\t\t   o->provenance_commit);\n \t\toid_array_clear(&to_fetch);\n \t}\n \tfor (i = 0; i < index->cache_nr; i++) {\ndiff --git a/unpack-trees.h b/unpack-trees.h\nindex 2e87875b15..a6e126c39d 100644\n--- a/unpack-trees.h\n+++ b/unpack-trees.h\n@@ -89,6 +89,13 @@ struct unpack_trees_options {\n \n \tstruct pattern_list *pl; /* for internal use */\n \tstruct checkout_metadata meta;\n+\n+\t/*\n+\t * Optional: The commit that this request comes from. Only used when\n+\t * this repository is a partial clone; this is a hint to the server when\n+\t * prefetching is needed.\n+\t */\n+\tstruct object_id *provenance_commit;\n };\n \n int unpack_trees(unsigned n, struct tree_desc *t,\n-- \n2.29.2.684.gfbc64c5ab5-goog\n\n"},{"id":"412357","messageId":"ad2579d6-c00a-c0a8-ae9b-11b168be1940@gmail.com","threadId":"54833","inReplyTo":"20201215200207.1083655-1-jonathantanmy@google.com","subject":"Re: [PATCH] checkout: send commit provenance during prefetch","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-16T14:50:01Z","receivedAt":"2020-12-16T14:51:01Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/15/2020 3:02 PM, Jonathan Tan wrote:\n> In a partial clone, whenever Git needs a missing object, it will fetch\n> it from the repo's promisor remote(s), sometimes as part of a bulk\n> prefetch. Currently, if the server handling such fetches does not accept\n> requests for objects unless the objects are reachable, it needs to\n> compute reachability from all refs.\n>\n> This can be improved by sending the commit from which the prefetch\n> request came - a server that understands this would then only need to\n> check that this commit is reachable, and check that the object is\n> reachable from that commit.\n\nYou're right that there are _two_ important checks here:\n\n1. the commit is reachable.\n2. the blob is reachable from that commit.\n\nThis does have the potential of greatly reducing the amount of\nparsed trees. It would be nice to see how much of a gain that\nreally provides. I suspect that it only helps for commits that\nare far from the ref tips, depending on your tree-walk algorithm.\n\nThis additional constraint of \"the blob is reachable from the\nprovided commit\" should not be considered a limitation to the\nserver, since a reachability bitmap from the tip commits might\nbe able to provide faster responses than walking trees from the\nprovided commit.\n\nPerhaps it would be worth testing a different mechanism for\nusing your reachability bitmaps? I'm guessing that your algorithm\nuses this pattern:\n\n1. Construct a reachability bitmap containing all objects reachable\n   from the allowed refs.\n2. Check if the blobs have bits on in that bitmap.\n\nInstead, you could do this slightly-more-complicated thing:\n\n1. Walk commits from the tips until finding reachability bitmaps\n   or commits inside those discovered bitmaps. (Take unions as\n   you find new bitmaps. Stop walking when a commit is in the\n   union.)\n\n2. \"approve\" blobs that have bits on in those bitmaps.\n\n3. While there are unapproved blobs, walk trees from the walked\n   commits, adding found objects to the bitmap. Stop when all blobs\n   are approved or when all objects are walked.\n\nBasically, you could probably respond more quickly to some of these\nrequests without needing a provenance commit, especially in the\ncases where the provenance commit would be more helpful (older commits,\nby my guess).\n\nPerhaps you've already tried these things and have discovered that\nthe provenance commit is faster more often. That would definitely be\na helpful justification of the feature.\n\n> Therefore, teach the partial clone fetching mechanism to support a\n> \"provenance\" argument, and plumb the commit provenance from checkout to\n> the partial clone fetching mechanism.\n\nIn a full patch, it would be good to document that this could be sent\nacross the wire, even if Git's server implementation ignores it.\n \n> In the future, other commands can be similarly upgraded. Other possible\n> future improvements include better diagnostic messages when a prefetch\n> fails.\n\nSo, this is only in the case of 'git checkout'. I know that the batch\nrequest logic for partial clone is also called by things like \"git diff\"\nor \"git log --follow\" when doing rename detection. Those might require\nsending _multiple_ provenance commits, so be sure to make that be a\npossible outcome of the option.\n\n> @@ -56,11 +56,14 @@ test_expect_success 'verify that .promisor file contains refs fetched' '\n>  \n>  # checkout master to force dynamic object fetch of blobs at HEAD.\n>  test_expect_success 'verify checkout with dynamic object fetch' '\n> +\trm -f trace &&\n>  \tgit -C pc1 rev-list --quiet --objects --missing=print HEAD >observed &&\n>  \ttest_line_count = 4 observed &&\n> -\tgit -C pc1 checkout master &&\n> +\tGIT_TRACE_PACKET=\"$(pwd)/trace\" git -C pc1 checkout master &&\n>  \tgit -C pc1 rev-list --quiet --objects --missing=print HEAD >observed &&\n> -\ttest_line_count = 0 observed\n> +\ttest_line_count = 0 observed &&\n> +\tHEAD_HASH=\"$(git -C pc1 rev-parse HEAD)\" &&\n> +\tgrep \"server-option=provenance=$HEAD_HASH\" trace\n>  '\n\nThis is about as good as we can do for testing the option here. I'm\nassuming we have some tests already that check the Git server is\nstill providing good answers over HTTP (and ignoring this option).\n\ntl;dr: I'm not against this idea. Just hopefully the server-side options\nhave been fully explored to justify the feature is worth it.\n\nThanks,\n-Stolee\n"},{"id":"412384","messageId":"xmqqa6ud4mch.fsf@gitster.c.googlers.com","threadId":"54833","inReplyTo":"20201215200207.1083655-1-jonathantanmy@google.com","subject":"Re: [PATCH] checkout: send commit provenance during prefetch","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-16T18:50:06Z","receivedAt":"2020-12-16T18:50: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> Therefore, teach the partial clone fetching mechanism to support a\n> \"provenance\" argument, and plumb the commit provenance from checkout to\n> the partial clone fetching mechanism.\n>\n> In the future, other commands can be similarly upgraded. Other possible\n> future improvements include better diagnostic messages when a prefetch\n> fails.\n\nI am not sure \"provenance\" is a good word to describe the concept,\nbut it feels a bit too limiting that you can give only a single\ncommit, especially when ...\n\n>  builtin/checkout.c       |  4 ++++\n>  builtin/index-pack.c     |  2 +-\n>  builtin/pack-objects.c   |  2 +-\n>  diff.c                   |  2 +-\n>  diffcore-rename.c        |  2 +-\n>  promisor-remote.c        | 12 +++++++++---\n>  promisor-remote.h        |  3 ++-\n>  sha1-file.c              |  2 +-\n>  t/t5616-partial-clone.sh |  7 +++++--\n>  unpack-trees.c           |  3 ++-\n>  unpack-trees.h           |  7 +++++++\n>  11 files changed, 34 insertions(+), 12 deletions(-)\n\n... I see that \"diff\" already needs lazy blob fetching and we know\ndiff often is between two commits (think: \"git log -p\").\n\n> This essentially splits reachability-of-blob, which almost certainly\n> requires loading a bitmap, into 2 parts: reachability-of-commit (which,\n> from my limited experience, can be more quickly done using a regular\n> object walk) and reachability-of-blob-from-commit (which, at worst,\n> requires fewer bitmaps to be loaded). I don't have timings for how it\n> works in practice, though.\n\nWhat does the bitmap you have on the serving side typically tell\nyou?  For some selected commits (not all commits) you'd have a\nbitmap that says \"from this commit, these objects can be reached\",\nor is it \"from this commit, these commits can be reached\"?\n\nThanks.\n"}]}