{"thread":{"id":"57999","subject":"[PATCH] mktree: learn about promised objects","startedAt":"2022-06-14T13:36:42Z","lastAt":"2022-06-21T17:48:55Z","messageCount":20,"participants":["Richard Oliver","Derrick Stolee","Taylor Blau","Jeff King","Junio C Hamano","Jonathan Tan"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"457187","messageId":"77035a0f-c42e-5cb3-f422-03fe81093adb@roku.com","threadId":"57999","inReplyTo":null,"subject":"[PATCH] mktree: learn about promised objects","fromName":"Richard Oliver","fromEmail":"roliver@roku.com","sentAt":"2022-06-14T13:36:28Z","receivedAt":"2022-06-14T13:36:42Z","isPatch":true,"sender":{"key":"roliver@roku.com","avatar":null},"body":"Do not use oid_object_info() to determine object type in mktree_line()\nas this can cause promised objects to be dynamically faulted-in one at a\ntime which has poor performance. Instead, use a combination of\noid_object_info_extended() (with OBJECT_INFO_SKIP_FETCH_OBJECT option),\nand the newly introduced promisor_object_type() to determine object type\nbefore defaulting to fetch from remote.\n\nSigned-off-by: Richard Oliver <roliver@roku.com>\n---\n builtin/mktree.c         | 19 ++++++++++++++--\n packfile.c               | 49 ++++++++++++++++++++++++++++------------\n packfile.h               |  6 +++++\n t/t0410-partial-clone.sh | 28 +++++++++++++++++++++++\n 4 files changed, 86 insertions(+), 16 deletions(-)\n\ndiff --git a/builtin/mktree.c b/builtin/mktree.c\nindex 902edba6d2..a783767b28 100644\n--- a/builtin/mktree.c\n+++ b/builtin/mktree.c\n@@ -8,6 +8,7 @@\n #include \"tree.h\"\n #include \"parse-options.h\"\n #include \"object-store.h\"\n+#include \"packfile.h\"\n \n static struct treeent {\n \tunsigned mode;\n@@ -116,8 +117,22 @@ static void mktree_line(char *buf, int nul_term_line, int allow_missing)\n \t\t\tpath, ptr, type_name(mode_type));\n \t}\n \n-\t/* Check the type of object identified by sha1 */\n-\tobj_type = oid_object_info(the_repository, &oid, NULL);\n+\t/* Check the type of object identified by oid without fetching objects */\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n+\toi.typep = &obj_type;\n+\tif (oid_object_info_extended(the_repository, &oid, &oi,\n+\t\t\t\t     OBJECT_INFO_LOOKUP_REPLACE |\n+\t\t\t\t     OBJECT_INFO_SKIP_FETCH_OBJECT) < 0)\n+\t\tobj_type = -1;\n+\n+\t/* Has the object been promised to us if we can't find it */\n+\tif (obj_type < 0)\n+\t\tobj_type = promisor_object_type(&oid);\n+\n+\t/* Try to fetch the object from the remote */\n+\tif (obj_type < 0)\n+\t\tobj_type = oid_object_info(the_repository, &oid, NULL);\n+\n \tif (obj_type < 0) {\n \t\tif (allow_missing) {\n \t\t\t; /* no problem - missing objects are presumed to be of the right type */\ndiff --git a/packfile.c b/packfile.c\nindex 8e812a84a3..d27cb106c1 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -2223,17 +2223,26 @@ int for_each_packed_object(each_packed_object_fn cb, void *data,\n \treturn r ? r : pack_errors;\n }\n \n+static void map_put_type(kh_oid_pos_t *map,\n+\tconst struct object_id *oid,\n+\tenum object_type type)\n+{\n+\tint hash_ret;\n+\tkhiter_t pos = kh_put_oid_pos(map, *oid, &hash_ret);\n+\tkh_value(map, pos) = type;\n+}\n+\n static int add_promisor_object(const struct object_id *oid,\n \t\t\t       struct packed_git *pack,\n \t\t\t       uint32_t pos,\n-\t\t\t       void *set_)\n+\t\t\t       void *map_)\n {\n-\tstruct oidset *set = set_;\n+\tkh_oid_pos_t *map = map_;\n \tstruct object *obj = parse_object(the_repository, oid);\n \tif (!obj)\n \t\treturn 1;\n \n-\toidset_insert(set, oid);\n+\tmap_put_type(map, oid, obj->type);\n \n \t/*\n \t * If this is a tree, commit, or tag, the objects it refers\n@@ -2250,34 +2259,46 @@ static int add_promisor_object(const struct object_id *oid,\n \t\t\t */\n \t\t\treturn 0;\n \t\twhile (tree_entry_gently(&desc, &entry))\n-\t\t\toidset_insert(set, &entry.oid);\n+\t\t\tmap_put_type(map,\n+\t\t\t\t     &entry.oid,\n+\t\t\t\t     object_type(entry.mode));\n \t\tfree_tree_buffer(tree);\n \t} else if (obj->type == OBJ_COMMIT) {\n \t\tstruct commit *commit = (struct commit *) obj;\n \t\tstruct commit_list *parents = commit->parents;\n \n-\t\toidset_insert(set, get_commit_tree_oid(commit));\n+\t\tmap_put_type(map, get_commit_tree_oid(commit), OBJ_TREE);\n \t\tfor (; parents; parents = parents->next)\n-\t\t\toidset_insert(set, &parents->item->object.oid);\n+\t\t\tmap_put_type(map,\n+\t\t\t\t     &parents->item->object.oid,\n+\t\t\t\t     OBJ_COMMIT);\n \t} else if (obj->type == OBJ_TAG) {\n \t\tstruct tag *tag = (struct tag *) obj;\n-\t\toidset_insert(set, get_tagged_oid(tag));\n+\t\tmap_put_type(map, get_tagged_oid(tag), OBJ_COMMIT);\n \t}\n \treturn 0;\n }\n \n-int is_promisor_object(const struct object_id *oid)\n+enum object_type promisor_object_type(const struct object_id *oid)\n {\n-\tstatic struct oidset promisor_objects;\n-\tstatic int promisor_objects_prepared;\n+\tstatic kh_oid_pos_t *promisor_objects;\n \n-\tif (!promisor_objects_prepared) {\n+\tif (!promisor_objects) {\n+\t\tpromisor_objects = kh_init_oid_pos();\n \t\tif (has_promisor_remote()) {\n \t\t\tfor_each_packed_object(add_promisor_object,\n-\t\t\t\t\t       &promisor_objects,\n+\t\t\t\t\t       promisor_objects,\n \t\t\t\t\t       FOR_EACH_OBJECT_PROMISOR_ONLY);\n \t\t}\n-\t\tpromisor_objects_prepared = 1;\n \t}\n-\treturn oidset_contains(&promisor_objects, oid);\n+\tkhiter_t pos = kh_get_oid_pos(promisor_objects, *oid);\n+\tif (pos < kh_end(promisor_objects))\n+\t\treturn kh_value(promisor_objects, pos);\n+\telse\n+\t\treturn OBJ_BAD;\n+}\n+\n+int is_promisor_object(const struct object_id *oid)\n+{\n+\treturn (promisor_object_type(oid) > OBJ_BAD);\n }\ndiff --git a/packfile.h b/packfile.h\nindex a3f6723857..35d0b600d2 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -182,6 +182,12 @@ int has_pack_index(const unsigned char *sha1);\n  */\n int is_promisor_object(const struct object_id *oid);\n \n+/*\n+ * Return the object type if the given object is in, or referred to\n+ * by, a promisor packfile; OBJ_BAD otherwise.\n+ */\n+enum object_type promisor_object_type(const struct object_id *oid);\n+\n /*\n  * Expose a function for fuzz testing.\n  *\ndiff --git a/t/t0410-partial-clone.sh b/t/t0410-partial-clone.sh\nindex 1e864cf317..12bfb02187 100755\n--- a/t/t0410-partial-clone.sh\n+++ b/t/t0410-partial-clone.sh\n@@ -660,6 +660,34 @@ test_expect_success 'lazy-fetch when accessing object not in the_repository' '\n \t! grep \"[?]$FILE_HASH\" out\n '\n \n+test_expect_success 'missing blob object promised by tree, passes mktree' '\n+\trm -rf repo &&\n+\ttest_create_repo repo &&\n+\techo foo >repo/foo &&\n+\tA=$(git -C repo hash-object foo) &&\n+\tgit -C repo update-index --add --info-only foo &&\n+\tB=$(git -C repo write-tree --missing-ok) &&\n+\tprintf \"$B\\n\" | pack_as_from_promisor &&\n+\tdelete_object repo \"$B\" &&\n+\n+\tgit -C repo config core.repositoryformatversion 1 &&\n+\tgit -C repo config extensions.partialclone \"arbitrary string\" &&\n+\n+\tprintf \"100644 blob $A\\tbar\" | git -C repo mktree\n+'\n+\n+test_expect_success 'missing blob object, not promised, faulted-in by mktree' '\n+\ttest_create_repo server &&\n+\tA=$(echo foo | git -C server hash-object --stdin -w) &&\n+\ttest_commit -C server 1 &&\n+\ttest_config -C server uploadpack.allowfilter 1 &&\n+\ttest_config -C server uploadpack.allowanysha1inwant 1 &&\n+\n+\trm -rf repo &&\n+\tgit clone --filter=blob:none \"file://$(pwd)/server\" repo &&\n+\tprintf \"100644 blob $A\\tbar\" | git -C repo mktree\n+'\n+\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \n\nbase-commit: 1e59178e3f65880188caedb965e70db5ceeb2d64\n-- \n2.36.1.384.gcc60f6fd7d\n\n"},{"id":"457190","messageId":"0067c46a-7bfd-db9c-5156-16f032814464@github.com","threadId":"57999","inReplyTo":"77035a0f-c42e-5cb3-f422-03fe81093adb@roku.com","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-06-14T14:14:36Z","receivedAt":"2022-06-14T14:14:41Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/14/2022 9:36 AM, Richard Oliver wrote:\n> Do not use oid_object_info() to determine object type in mktree_line()\n> as this can cause promised objects to be dynamically faulted-in one at a\n> time which has poor performance. Instead, use a combination of\n> oid_object_info_extended() (with OBJECT_INFO_SKIP_FETCH_OBJECT option),\n> and the newly introduced promisor_object_type() to determine object type\n> before defaulting to fetch from remote.\n\nHave you run some performance tests on this? It seems like this will\nscan all packed objects, which is probably much slower than just asking\nthe remote for the object in most cases.\n\nThanks,\n-Stolee\n"},{"id":"457203","messageId":"797af8c8-229f-538b-d122-8ea48067cc19@roku.com","threadId":"57999","inReplyTo":"0067c46a-7bfd-db9c-5156-16f032814464@github.com","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Richard Oliver","fromEmail":"roliver@roku.com","sentAt":"2022-06-14T16:33:40Z","receivedAt":"2022-06-14T16:33:54Z","isPatch":true,"sender":{"key":"roliver@roku.com","avatar":null},"body":"On 14/06/2022 15:14, Derrick Stolee wrote:\n> On 6/14/2022 9:36 AM, Richard Oliver wrote:\n>> Do not use oid_object_info() to determine object type in mktree_line()\n>> as this can cause promised objects to be dynamically faulted-in one at a\n>> time which has poor performance. Instead, use a combination of\n>> oid_object_info_extended() (with OBJECT_INFO_SKIP_FETCH_OBJECT option),\n>> and the newly introduced promisor_object_type() to determine object type\n>> before defaulting to fetch from remote.\n> \n> Have you run some performance tests on this? It seems like this will\n> scan all packed objects, which is probably much slower than just asking\n> the remote for the object in most cases.\n> \n> Thanks,\n> -Stolee\n\n\nHi Stolee,\n\nI've put together a synthetic experiment below (adding a new blob to anexisting tree) to show you the behaviour that we've been seeing.  Our\nactual use-case (where we first encountered this behaviour) is updating\nsubmodules to a known hash. As you can see, the round-trip time of fetching\nobjects one-by-one is very expensive.\n\nBefore, using system git (git version 2.32.0 (Apple Git-132)):\n\n> $ git init\n> # Fetch a recent tree\n> $ git fetch --filter=tree:0 --depth 1 https://github.com/git/git cdb48006b0ec7fe19794daf7b5363ab42d9d9371\n> remote: Enumerating objects: 1, done.\n> remote: Counting objects: 100% (1/1), done.\n> remote: Total 1 (delta 0), reused 0 (delta 0), pack-reused 0\n> Receiving objects: 100% (1/1), 13.12 KiB | 13.12 MiB/s, done.\n> From https://github.com/git/git\n>  * branch            cdb48006b0ec7fe19794daf7b5363ab42d9d9371 -> FETCH_HEAD\n>\n> $ NEW_BLOB=$(echo zzz | git hash-object --stdin -w)\n>\n> $ cat <(git ls-tree FETCH_HEAD) <(printf \"100644 blob ${NEW_BLOB}\\tzzz\") | time git mktree\n> remote: Enumerating objects: 1, done.\n> remote: Counting objects: 100% (1/1), done.\n> remote: Total 1 (delta 0), reused 0 (delta 0), pack-reused 0\n> Receiving objects: 100% (1/1), 334 bytes | 334.00 KiB/s, done.\n> remote: Enumerating objects: 1, done.\n> remote: Counting objects: 100% (1/1), done.\n> remote: Total 1 (delta 0), reused 0 (delta 0), pack-reused 0\n> Receiving objects: 100% (1/1), 2.01 KiB | 2.01 MiB/s, done.\n> remote: Enumerating objects: 1, done.\n> remote: Counting objects: 100% (1/1), done.\n> remote: Total 1 (delta 0), reused 0 (delta 0), pack-reused 0\n> Receiving objects: 100% (1/1), 256 bytes | 256.00 KiB/s, done.\n> # ...\n> # SOME TIME LATER\n> # ...\n> e26c7ce7357b1649da7b4200d4e80d0b668db8d4\n>       286.49 real        15.66 user        15.59 sys\n\nRepeated experiment, but using modified mktree:\n\n> $ cat <(git ls-tree FETCH_HEAD) <(printf \"100644 blob ${NEW_BLOB}\\tzzz\") | time git mktree\n> e26c7ce7357b1649da7b4200d4e80d0b668db8d4\n>         0.06 real         0.01 user         0.03 sys\n\nDid you have any other sort of performance test in mind? The remotes we\ntypically deal with are geographically far away and deal with a high volume\nof traffic so we're keen to move behaviour to the client where it makes sense\nto do so.\n\nThanks,\nRichard\n"},{"id":"457206","messageId":"574dc4a9-b3c7-1fd3-8c0e-39071117c7f0@github.com","threadId":"57999","inReplyTo":"797af8c8-229f-538b-d122-8ea48067cc19@roku.com","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-06-14T17:27:18Z","receivedAt":"2022-06-14T17:27:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/14/2022 12:33 PM, Richard Oliver wrote:\n> On 14/06/2022 15:14, Derrick Stolee wrote:\n>> On 6/14/2022 9:36 AM, Richard Oliver wrote:\n>>> Do not use oid_object_info() to determine object type in mktree_line()\n>>> as this can cause promised objects to be dynamically faulted-in one at a\n>>> time which has poor performance. Instead, use a combination of\n>>> oid_object_info_extended() (with OBJECT_INFO_SKIP_FETCH_OBJECT option),\n>>> and the newly introduced promisor_object_type() to determine object type\n>>> before defaulting to fetch from remote.\n>>\n>> Have you run some performance tests on this? It seems like this will\n>> scan all packed objects, which is probably much slower than just asking\n>> the remote for the object in most cases.\n>>\n>> Thanks,\n>> -Stolee\n> \n> \n> Hi Stolee,\n> \n> I've put together a synthetic experiment below (adding a new blob to anexisting tree) to show you the behaviour that we've been seeing.  Our\n> actual use-case (where we first encountered this behaviour) is updating\n> submodules to a known hash. As you can see, the round-trip time of fetching\n> objects one-by-one is very expensive.\n> \n> Before, using system git (git version 2.32.0 (Apple Git-132)):\n> \n>> $ git init\n>> # Fetch a recent tree\n>> $ git fetch --filter=tree:0 --depth 1 https://github.com/git/git cdb48006b0ec7fe19794daf7b5363ab42d9d9371\n>> remote: Enumerating objects: 1, done.\n>> remote: Counting objects: 100% (1/1), done.\n>> remote: Total 1 (delta 0), reused 0 (delta 0), pack-reused 0\n>> Receiving objects: 100% (1/1), 13.12 KiB | 13.12 MiB/s, done.\n>> From https://github.com/git/git\n>>  * branch            cdb48006b0ec7fe19794daf7b5363ab42d9d9371 -> FETCH_HEAD\n>>\n>> $ NEW_BLOB=$(echo zzz | git hash-object --stdin -w)\n>>\n>> $ cat <(git ls-tree FETCH_HEAD) <(printf \"100644 blob ${NEW_BLOB}\\tzzz\") | time git mktree\n>> remote: Enumerating objects: 1, done.\n>> remote: Counting objects: 100% (1/1), done.\n>> remote: Total 1 (delta 0), reused 0 (delta 0), pack-reused 0\n>> Receiving objects: 100% (1/1), 334 bytes | 334.00 KiB/s, done.\n>> remote: Enumerating objects: 1, done.\n>> remote: Counting objects: 100% (1/1), done.\n>> remote: Total 1 (delta 0), reused 0 (delta 0), pack-reused 0\n>> Receiving objects: 100% (1/1), 2.01 KiB | 2.01 MiB/s, done.\n>> remote: Enumerating objects: 1, done.\n>> remote: Counting objects: 100% (1/1), done.\n>> remote: Total 1 (delta 0), reused 0 (delta 0), pack-reused 0\n>> Receiving objects: 100% (1/1), 256 bytes | 256.00 KiB/s, done.\n>> # ...\n>> # SOME TIME LATER\n>> # ...\n>> e26c7ce7357b1649da7b4200d4e80d0b668db8d4\n>>       286.49 real        15.66 user        15.59 sys\n\nI see. The problem here is that we are making _many requests_ for the same\ntree, so maybe it would be better to introduce a batched download for the\nlist of missing objects. This would require iterating over the objects for\nthe tree to check existence (in quick mode) and adding the missing ones in\na list, then requesting that set altogether in a single request.\n\nThat probably won't be as fast as your modified mktree experiment below,\nbut would match my expectations of \"probably faster assuming the repo is\nbig enough\".\n\n> Repeated experiment, but using modified mktree:\n> \n>> $ cat <(git ls-tree FETCH_HEAD) <(printf \"100644 blob ${NEW_BLOB}\\tzzz\") | time git mktree\n>> e26c7ce7357b1649da7b4200d4e80d0b668db8d4\n>>         0.06 real         0.01 user         0.03 sys\n> \n> Did you have any other sort of performance test in mind? The remotes we\n> typically deal with are geographically far away and deal with a high volume\n> of traffic so we're keen to move behaviour to the client where it makes sense\n> to do so.\n\nI guess I wonder how large your promisor pack-files are in this test,\nsince your implementation depends on for_each_packed_object(), which\nshould be really inefficient if you're actually dealing with a large\npartial clone.\n\nThanks,\n-Stolee\n"},{"id":"457235","messageId":"YqkpRE8nykqVv8cn@nand.local","threadId":"57999","inReplyTo":"574dc4a9-b3c7-1fd3-8c0e-39071117c7f0@github.com","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2022-06-15T00:35:16Z","receivedAt":"2022-06-15T00:35:22Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Jun 14, 2022 at 01:27:18PM -0400, Derrick Stolee wrote:\n> > Did you have any other sort of performance test in mind? The remotes we\n> > typically deal with are geographically far away and deal with a high volume\n> > of traffic so we're keen to move behaviour to the client where it makes sense\n> > to do so.\n>\n> I guess I wonder how large your promisor pack-files are in this test,\n> since your implementation depends on for_each_packed_object(), which\n> should be really inefficient if you're actually dealing with a large\n> partial clone.\n\nI had the same thought. Storing data available in the promisor packs\ninto an oid_map is going to be expensive if there are many such objects.\n\nIs there a reason that we can't introduce a variant of\nfind_kept_pack_entry() that deals only with .promisor packs and look\nthese things up as-needed?\n\nThanks,\nTaylor\n"},{"id":"457247","messageId":"YqlZb3Ycc71+dPu4@coredump.intra.peff.net","threadId":"57999","inReplyTo":"YqkpRE8nykqVv8cn@nand.local","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-06-15T04:00:47Z","receivedAt":"2022-06-15T04:00:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 14, 2022 at 08:35:16PM -0400, Taylor Blau wrote:\n\n> On Tue, Jun 14, 2022 at 01:27:18PM -0400, Derrick Stolee wrote:\n> > > Did you have any other sort of performance test in mind? The remotes we\n> > > typically deal with are geographically far away and deal with a high volume\n> > > of traffic so we're keen to move behaviour to the client where it makes sense\n> > > to do so.\n> >\n> > I guess I wonder how large your promisor pack-files are in this test,\n> > since your implementation depends on for_each_packed_object(), which\n> > should be really inefficient if you're actually dealing with a large\n> > partial clone.\n> \n> I had the same thought. Storing data available in the promisor packs\n> into an oid_map is going to be expensive if there are many such objects.\n> \n> Is there a reason that we can't introduce a variant of\n> find_kept_pack_entry() that deals only with .promisor packs and look\n> these things up as-needed?\n\nIt's much worse than that. The promisor mechanism is fundamentally very\ninefficient in runtime, optimizing instead for size. Imagine I have a\npartial clone and I retrieve tree X, which points to a blob Y that I\ndon't get. I have X in a promisor pack, and asking about it is\nefficient. But if I want to know about Y, I have no data structure\nmentioning Y except the tree X itself. So to enumerate all of the\npromisor edges, I have to walk all of the trees in the promisor pack.\n\nSo it is not just lookup, but actual tree walking that is expensive. The\nflip side is that you don't have to store a complete separate list of\nthe promised objects. Whether that's a win depends on how many local\nobjects you have, versus how many are promised.\n\nBut it would be possible to cache the promisor list to make the tradeoff\nseparately. E.g., do the walk over the promisor trees once (perhaps at\npack creation time), and store a sorted list of fixed-length (oid, type)\nrecords that could be binary searched. You could even put it in the\n.promisor file. :)\n\n-Peff\n"},{"id":"457299","messageId":"ad9b5ec9-14fd-cd66-be87-2fe1eb24296a@roku.com","threadId":"57999","inReplyTo":"YqlZb3Ycc71+dPu4@coredump.intra.peff.net","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Richard Oliver","fromEmail":"roliver@roku.com","sentAt":"2022-06-15T17:40:46Z","receivedAt":"2022-06-15T17:40:57Z","isPatch":true,"sender":{"key":"roliver@roku.com","avatar":null},"body":"On 15/06/2022 05:00, Jeff King wrote:\n> On Tue, Jun 14, 2022 at 08:35:16PM -0400, Taylor Blau wrote:\n> \n>> On Tue, Jun 14, 2022 at 01:27:18PM -0400, Derrick Stolee wrote:\n>>>> Did you have any other sort of performance test in mind? The remotes we\n>>>> typically deal with are geographically far away and deal with a high volume\n>>>> of traffic so we're keen to move behaviour to the client where it makes sense\n>>>> to do so.\n>>>\n>>> I guess I wonder how large your promisor pack-files are in this test,\n>>> since your implementation depends on for_each_packed_object(), which\n>>> should be really inefficient if you're actually dealing with a large\n>>> partial clone.\n>>\n>> I had the same thought. Storing data available in the promisor packs\n>> into an oid_map is going to be expensive if there are many such objects.\n>>\n>> Is there a reason that we can't introduce a variant of\n>> find_kept_pack_entry() that deals only with .promisor packs and look\n>> these things up as-needed?\n> \n> It's much worse than that. The promisor mechanism is fundamentally very\n> inefficient in runtime, optimizing instead for size. Imagine I have a\n> partial clone and I retrieve tree X, which points to a blob Y that I\n> don't get. I have X in a promisor pack, and asking about it is\n> efficient. But if I want to know about Y, I have no data structure\n> mentioning Y except the tree X itself. So to enumerate all of the\n> promisor edges, I have to walk all of the trees in the promisor pack.\n> \n> So it is not just lookup, but actual tree walking that is expensive. The\n> flip side is that you don't have to store a complete separate list of\n> the promised objects. Whether that's a win depends on how many local\n> objects you have, versus how many are promised.\n> \n> But it would be possible to cache the promisor list to make the tradeoff\n> separately. E.g., do the walk over the promisor trees once (perhaps at\n> pack creation time), and store a sorted list of fixed-length (oid, type)\n> records that could be binary searched. You could even put it in the\n> .promisor file. :)\n> \n> -Peff\n\nI like the idea of caching the promisor list at pack creation time;\nI'll start work on a patch set that implements this.\n\nMeanwhile, is it worth considering a '--promised-as-missing' option\n(or a config option) for invocations such as 'mktree --missing' that\nprevents promised objects being faulted-in? Currently, the only\nreliable way that I've found to prevent 'mktree --missing' faulting-in\npromised objects is to remove the remote. Such an option could either\nset the global variable 'fetch_if_missing' to '0' or could ensure\n'OBJECT_INFO_SKIP_FETCH_OBJECT' is passed appropriately.\n\nCheers,\nRichard\n"},{"id":"457301","messageId":"1fe6c00a-806c-89de-cb67-d063dc4a5279@github.com","threadId":"57999","inReplyTo":"ad9b5ec9-14fd-cd66-be87-2fe1eb24296a@roku.com","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-06-15T18:17:58Z","receivedAt":"2022-06-15T18:18:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/15/2022 1:40 PM, Richard Oliver wrote:\n> On 15/06/2022 05:00, Jeff King wrote:\n\n>> So it is not just lookup, but actual tree walking that is expensive. The\n>> flip side is that you don't have to store a complete separate list of\n>> the promised objects. Whether that's a win depends on how many local\n>> objects you have, versus how many are promised.\n\nThis is also why blobless (or blob-size filters) are the recommended way\nto use partial clone. It's just too expensive to have tree misses.\n\n>> But it would be possible to cache the promisor list to make the tradeoff\n>> separately. E.g., do the walk over the promisor trees once (perhaps at\n>> pack creation time), and store a sorted list of fixed-length (oid, type)\n>> records that could be binary searched. You could even put it in the\n>> .promisor file. :)\n>>\n>> -Peff\n> \n> I like the idea of caching the promisor list at pack creation time;\n> I'll start work on a patch set that implements this.\n> \n> Meanwhile, is it worth considering a '--promised-as-missing' option\n> (or a config option) for invocations such as 'mktree --missing' that\n> prevents promised objects being faulted-in? Currently, the only\n> reliable way that I've found to prevent 'mktree --missing' faulting-in\n> promised objects is to remove the remote. Such an option could either\n> set the global variable 'fetch_if_missing' to '0' or could ensure\n> 'OBJECT_INFO_SKIP_FETCH_OBJECT' is passed appropriately.\n\nOne issue I've had with the current design of partial clone is that we\nput all of the filter logic into the remotes, not the repository itself.\nThis means that if I use \"git remote add\" to add a new remote, then that\nremote does not inherit the filter (and hence fetches can be too large\nor even fail because we are \"missing\" an object pointed to by the\nresulting pack).\n\nIf we had a repository-scoped notion of the filter, then we could\nspecial-case this mktree logic to assume a blob if the filter only\nexcludes blobs. That would be even faster than looking up the type\nfrom a \"promised objects\" file.\n\nJust thinking about smaller steps that could simplify things before\nadding a new data format. Feel free to continue pursuing that lookup\nfile if that's what you think will work best.\n\nThanks,\n-Stolee\n"},{"id":"457317","messageId":"xmqqa6adzln6.fsf@gitster.g","threadId":"57999","inReplyTo":"ad9b5ec9-14fd-cd66-be87-2fe1eb24296a@roku.com","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-06-15T21:01:33Z","receivedAt":"2022-06-15T21:01:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Richard Oliver <roliver@roku.com> writes:\n\n> Meanwhile, is it worth considering a '--promised-as-missing' option\n> (or a config option) for invocations such as 'mktree --missing' that\n> prevents promised objects being faulted-in? Currently, the only\n> reliable way that I've found to prevent 'mktree --missing' faulting-in\n> promised objects is to remove the remote. Such an option could either\n> set the global variable 'fetch_if_missing' to '0' or could ensure\n> 'OBJECT_INFO_SKIP_FETCH_OBJECT' is passed appropriately.\n\nI didn't spend too much time on thinking this one through myself,\nbut do we really need a separte option?\n\nAs far as I remember, I wrote the original behaviour implemented in\n1c64e79a (mktree --missing: allow missing objects, 2009-05-10) when\nthe command is run without --missing primarily to be extra paranoid\nto detect broken repository with every chance we have to avoid\nspreading existing breakage to new objects we create.  With the\ninput \"mktree\" gets from the end user, we have no need to learn\nanything from existing objects in order to create the tree object at\nall.\n\nThe original 1c64e79a even carefully made sure that with --missing\nin effect, we do not ask the object store about an object:\n\n\t/* It is perfectly normal if we do not have a commit from a submodule */\n\tif (S_ISGITLINK(mode))\n\t\tallow_missing = 1;\n\n\tif (!allow_missing)\n\t\ttype = sha1_object_info(sha1, NULL);\n\telse\n\t\ttype = object_type(mode);\n\n\tif (type < 0)\n\t\tdie(\"object %s unavailable\", sha1_to_hex(sha1));\n\n\nWe by grave mistake at 31c8221a (mktree: validate entry type in\ninput, 2009-05-14) started insisting on inspecting objects even when\nallow-mising was given.  I do not think it was sensible, given why\nwe had \"--missing\" as an option to allow users to say \"you do not\nhave to be too paranoid\".\n\nThe codebase is so distant but I think we should probably do a moral\nrevert/reconstruct of that commit so that the extra paranoia of the\nsaid commit applies only when \"--missing\" is not in effect, or\nsomething like that.\n"},{"id":"457354","messageId":"Yqq5dLagSfVMzyQH@coredump.intra.peff.net","threadId":"57999","inReplyTo":"xmqqa6adzln6.fsf@gitster.g","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-06-16T05:02:44Z","receivedAt":"2022-06-16T05:02:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 15, 2022 at 02:01:33PM -0700, Junio C Hamano wrote:\n\n> Richard Oliver <roliver@roku.com> writes:\n> \n> > Meanwhile, is it worth considering a '--promised-as-missing' option\n> > (or a config option) for invocations such as 'mktree --missing' that\n> > prevents promised objects being faulted-in? Currently, the only\n> > reliable way that I've found to prevent 'mktree --missing' faulting-in\n> > promised objects is to remove the remote. Such an option could either\n> > set the global variable 'fetch_if_missing' to '0' or could ensure\n> > 'OBJECT_INFO_SKIP_FETCH_OBJECT' is passed appropriately.\n> \n> I didn't spend too much time on thinking this one through myself,\n> but do we really need a separte option?\n> [...]\n> We by grave mistake at 31c8221a (mktree: validate entry type in\n> input, 2009-05-14) started insisting on inspecting objects even when\n> allow-mising was given.  I do not think it was sensible, given why\n> we had \"--missing\" as an option to allow users to say \"you do not\n> have to be too paranoid\".\n> \n> The codebase is so distant but I think we should probably do a moral\n> revert/reconstruct of that commit so that the extra paranoia of the\n> said commit applies only when \"--missing\" is not in effect, or\n> something like that.\n\nFWIW, I had the same reaction. I think fixing \"--missing\" should be the\nfirst step, and would unstick Richard's use case, as I understand it.\n\nThere is some value to improving the promisor case, since using\n\"--missing\" is a pretty broad stroke (i.e., you'd fail to actual\ncorruption of missing non-promisor objects). That could either be\nchecking the promisor object and type without faulting it in, or just\nskipping the type-check for objects after confirming that they're\npromisors.\n\nBut that can come on top, I think. The use case there is also a bit\nnarrower.  The local repository does not know about all promised\nobjects. It can only see the boundaries of objects it doesn't have (so\nwith --filter=tree:0, for example, a partial clone of a repo with path\n\"a/b/c\" would know about \"b\" but not \"c\"). So in the most general case\nyou'd still have to resort to \"--missing\", but I suspect in practice\nyou'd always feed things at that boundary to mktree (otherwise, how\nwould you even know the oid of \"c\").\n\n-Peff\n"},{"id":"457359","messageId":"YqrIrYHKUP6b/EtN@coredump.intra.peff.net","threadId":"57999","inReplyTo":"1fe6c00a-806c-89de-cb67-d063dc4a5279@github.com","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-06-16T06:07:41Z","receivedAt":"2022-06-16T06:08:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 15, 2022 at 02:17:58PM -0400, Derrick Stolee wrote:\n\n> On 6/15/2022 1:40 PM, Richard Oliver wrote:\n> > On 15/06/2022 05:00, Jeff King wrote:\n> \n> >> So it is not just lookup, but actual tree walking that is expensive. The\n> >> flip side is that you don't have to store a complete separate list of\n> >> the promised objects. Whether that's a win depends on how many local\n> >> objects you have, versus how many are promised.\n> \n> This is also why blobless (or blob-size filters) are the recommended way\n> to use partial clone. It's just too expensive to have tree misses.\n\nI agree that tree misses are awful, but I'm actually talking about\nsomething different: traversing the local trees we _do_ have in order to\nfind the set of promised objects. Which is worse for blob:none, because\nit means you have more trees locally. :)\n\nTry this with a big repo like linux.git:\n\n  git clone --no-local --filter=blob:none linux.git repo\n  cd repo\n\n  # this is fast; we mark the promisor trees as UNINTERESTING, so we do\n  # not look at them as part of the traversal, and never call\n  # is_promisor_object().\n  time git rev-list --count --objects --all --exclude-promisor-objects\n\n  # but imagine we had a fixed mktree[1] that did not fault in the blobs\n  # unnecessarily, and we made a new tree that references a promised\n  # blob.\n  tree=$(git ls-tree HEAD~1000 | grep Makefile | git mktree --missing)\n  commit=$(echo foo | git commit-tree -p HEAD $tree)\n  git update-ref refs/heads/foo $commit\n\n  # this is now slow; even though we only call is_promisor_object()\n  # once, we have to open every single tree in the pack to find it!\n  time git rev-list --count --objects --all --exclude-promisor-objects\n\nThose rev-lists run in 1.7s and 224s respectively. Ouch!\n\nNow the setup there is kind of contrived, and it's actually not trivial\nto convince rev-list to actually call is_promisor_object() these days.\nThat's because promisor-ness (promisosity?) tends to be one-way\ntransitive. A promised blob is usually either only referenced by\npromised trees (which we have in this case), or is faulted in as part of\nmaking a new tree.\n\nBut it's not guaranteed, and certainly a faulted-in object could later\nbe deleted from the local repo, since it's promised. I suspect there are\nless convoluted workflows to get to a similar state, but I don't know\nthem offhand. There's more discussion of this issue in this thread from\nlast summer:\n\n  https://lore.kernel.org/git/20210403090412.GH2271@szeder.dev/\n\n-Peff\n\n[1] The mktree I used was the fix discussed elsewhere in the thread:\n\ndiff --git a/builtin/mktree.c b/builtin/mktree.c\nindex 902edba6d2..42ae82230c 100644\n--- a/builtin/mktree.c\n+++ b/builtin/mktree.c\n@@ -117,15 +117,11 @@ static void mktree_line(char *buf, int nul_term_line, int allow_missing)\n \t}\n \n \t/* Check the type of object identified by sha1 */\n-\tobj_type = oid_object_info(the_repository, &oid, NULL);\n-\tif (obj_type < 0) {\n-\t\tif (allow_missing) {\n-\t\t\t; /* no problem - missing objects are presumed to be of the right type */\n-\t\t} else {\n+\tif (!allow_missing) {\n+\t\tobj_type = oid_object_info(the_repository, &oid, NULL);\n+\t\tif (obj_type < 0)\n \t\t\tdie(\"entry '%s' object %s is unavailable\", path, oid_to_hex(&oid));\n-\t\t}\n-\t} else {\n-\t\tif (obj_type != mode_type) {\n+\t\telse if (obj_type != mode_type) {\n \t\t\t/*\n \t\t\t * The object exists but is of the wrong type.\n \t\t\t * This is a problem regardless of allow_missing\n"},{"id":"457360","messageId":"YqrTsbXbEjx0Pabn@coredump.intra.peff.net","threadId":"57999","inReplyTo":"YqrIrYHKUP6b/EtN@coredump.intra.peff.net","subject":"[PATCH] is_promisor_object(): walk promisor packs in pack-order","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-06-16T06:54:41Z","receivedAt":"2022-06-16T06:55:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 16, 2022 at 02:07:41AM -0400, Jeff King wrote:\n\n> Those rev-lists run in 1.7s and 224s respectively. Ouch!\n\nEven though I expected the second one to be slow, I was shocked at just\nhow slow it was. The patch below speeds it up by a factor of 2, and I\nthink is worth applying separately, regardless of anything else being\ndiscussed in this thread.\n\n-- >8 --\nSubject: is_promisor_object(): walk promisor packs in pack-order\n\nWhen we generate the list of promisor objects, we walk every pack with a\n.promisor file and examine its objects for any links to other objects.\nBy default, for_each_packed_object() will go in pack .idx order.\n\nThis is the worst case with respect to our delta base cache. If we have\na delta chain of A->B->C->D, then visiting A may require reconstructing\nboth B and C, unless we also visited B recently, in which case we may\nhave cached its value. Because .idx order is based on sha1, it's random\nwith respect to the actual object contents and deltas, and thus we're\nunlikely to get many cache hits.\n\nIf we instead traverse in pack order, then we get the optimal case:\npacks are written to keep delta families together, and to place bases\nbefore their children.\n\nEven on a modest repository like git.git, this has a noticeable speedup\non p5600.4, which runs \"fsck\" on a partial clone with blob:none (so lots\nof trees which need to be walked, and which delta well):\n\nTest       HEAD^               HEAD\n-------------------------------------------------------\n5600.4:    17.87(17.83+0.04)   15.42(15.35+0.06) -13.7%\n\nOn a larger repository like linux.git, the speedup is even more\npronounced:\n\nTest       HEAD^                 HEAD\n-----------------------------------------------------------\n5600.4:    322.47(322.01+0.42)   186.41(185.76+0.63) -42.2%\n\nAny other operations that call is_promisor_object(), like \"rev-list\n--exclude-promisor-objects\", would similarly benefit, but the\ninvocations in p5600 don't actually trigger any such cases.\n\nNote that we may pay a small price to build a rev-index in-memory to do\nthe pack-order traversal. But it's still a big net win, and even that\nsmall cost goes away if you are using pack.writeReverseIndex.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nAs an aside, feels like pack.writeReverseIndex ought to become the\ndefault (which AFAIK hasn't happened yet).\n\n packfile.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 8e812a84a3..ed69fe457b 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -2275,7 +2275,8 @@ int is_promisor_object(const struct object_id *oid)\n \t\tif (has_promisor_remote()) {\n \t\t\tfor_each_packed_object(add_promisor_object,\n \t\t\t\t\t       &promisor_objects,\n-\t\t\t\t\t       FOR_EACH_OBJECT_PROMISOR_ONLY);\n+\t\t\t\t\t       FOR_EACH_OBJECT_PROMISOR_ONLY |\n+\t\t\t\t\t       FOR_EACH_OBJECT_PACK_ORDER);\n \t\t}\n \t\tpromisor_objects_prepared = 1;\n \t}\n-- \n2.37.0.rc0.352.g10876ef154\n\n"},{"id":"457379","messageId":"b559b9a3-b97a-f394-5845-5c810425f8a4@github.com","threadId":"57999","inReplyTo":"YqrIrYHKUP6b/EtN@coredump.intra.peff.net","subject":"Re: [PATCH] mktree: learn about promised objects","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-06-16T13:59:57Z","receivedAt":"2022-06-16T14:00:38Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/16/2022 2:07 AM, Jeff King wrote:\n> On Wed, Jun 15, 2022 at 02:17:58PM -0400, Derrick Stolee wrote:\n> \n>> On 6/15/2022 1:40 PM, Richard Oliver wrote:\n>>> On 15/06/2022 05:00, Jeff King wrote:\n>>\n>>>> So it is not just lookup, but actual tree walking that is expensive. The\n>>>> flip side is that you don't have to store a complete separate list of\n>>>> the promised objects. Whether that's a win depends on how many local\n>>>> objects you have, versus how many are promised.\n>>\n>> This is also why blobless (or blob-size filters) are the recommended way\n>> to use partial clone. It's just too expensive to have tree misses.\n> \n> I agree that tree misses are awful, but I'm actually talking about\n> something different: traversing the local trees we _do_ have in order to\n> find the set of promised objects. Which is worse for blob:none, because\n> it means you have more trees locally. :)\n\nAh, I misread your email. I agree that walking trees is far too\nexpensive to do just to find an object type.\n\n> Try this with a big repo like linux.git:\n> \n>   git clone --no-local --filter=blob:none linux.git repo\n>   cd repo\n> \n>   # this is fast; we mark the promisor trees as UNINTERESTING, so we do\n>   # not look at them as part of the traversal, and never call\n>   # is_promisor_object().\n>   time git rev-list --count --objects --all --exclude-promisor-objects\n> \n>   # but imagine we had a fixed mktree[1] that did not fault in the blobs\n>   # unnecessarily, and we made a new tree that references a promised\n>   # blob.\n>   tree=$(git ls-tree HEAD~1000 | grep Makefile | git mktree --missing)\n>   commit=$(echo foo | git commit-tree -p HEAD $tree)\n>   git update-ref refs/heads/foo $commit\n> \n>   # this is now slow; even though we only call is_promisor_object()\n>   # once, we have to open every single tree in the pack to find it!\n>   time git rev-list --count --objects --all --exclude-promisor-objects\n> \n> Those rev-lists run in 1.7s and 224s respectively. Ouch!\n\nThis is exactly the reason I thought just asking for the objects\ndirectly is faster than scanning all the packs. Thanks for giving\nconcrete numbers that support that assumption.\n\nThanks,\n-Stolee\n"},{"id":"457380","messageId":"1682f396-018a-8751-1907-7c244fe06ea9@github.com","threadId":"57999","inReplyTo":"YqrTsbXbEjx0Pabn@coredump.intra.peff.net","subject":"Re: [PATCH] is_promisor_object(): walk promisor packs in pack-order","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-06-16T14:00:43Z","receivedAt":"2022-06-16T14:00:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/16/2022 2:54 AM, Jeff King wrote:\n> On Thu, Jun 16, 2022 at 02:07:41AM -0400, Jeff King wrote:\n> \n>> Those rev-lists run in 1.7s and 224s respectively. Ouch!\n> \n> Even though I expected the second one to be slow, I was shocked at just\n> how slow it was. The patch below speeds it up by a factor of 2, and I\n> think is worth applying separately, regardless of anything else being\n> discussed in this thread.\n\nI agree. It's extremely simple for the value it provides.\n\n> diff --git a/packfile.c b/packfile.c\n> index 8e812a84a3..ed69fe457b 100644\n> --- a/packfile.c\n> +++ b/packfile.c\n> @@ -2275,7 +2275,8 @@ int is_promisor_object(const struct object_id *oid)\n>  \t\tif (has_promisor_remote()) {\n>  \t\t\tfor_each_packed_object(add_promisor_object,\n>  \t\t\t\t\t       &promisor_objects,\n> -\t\t\t\t\t       FOR_EACH_OBJECT_PROMISOR_ONLY);\n> +\t\t\t\t\t       FOR_EACH_OBJECT_PROMISOR_ONLY |\n> +\t\t\t\t\t       FOR_EACH_OBJECT_PACK_ORDER);\n>  \t\t}\n\nThanks,\n-Stolee\n\n"},{"id":"457384","messageId":"1566aed1-a38f-a9ca-241c-21b56d732328@roku.com","threadId":"57999","inReplyTo":"xmqqa6adzln6.fsf@gitster.g","subject":"[PATCH] mktree: Make '--missing' behave as documented","fromName":"Richard Oliver","fromEmail":"roliver@roku.com","sentAt":"2022-06-16T15:46:00Z","receivedAt":"2022-06-16T15:46:14Z","isPatch":true,"sender":{"key":"roliver@roku.com","avatar":null},"body":"On 15/06/2022 22:01, Junio C Hamano wrote:\n> We by grave mistake at 31c8221a (mktree: validate entry type in\n> input, 2009-05-14) started insisting on inspecting objects even when\n> allow-mising was given.  I do not think it was sensible, given why\n> we had \"--missing\" as an option to allow users to say \"you do not\n> have to be too paranoid\".\n> \n> The codebase is so distant but I think we should probably do a moral\n> revert/reconstruct of that commit so that the extra paranoia of the\n> said commit applies only when \"--missing\" is not in effect, or\n> something like that.\n\n-- >8 --\nSubject: [PATCH] mktree: Make '--missing' behave as documented\n\nDo not make use of the object store to verify object type for\n'allow_missing' objects in mktree_line(). GIT-MKTREE(1) documents\n'--missing' as disabling \"verif[ication] that each tree entry's sha1\nidentifies an existing object\".\n\nThis change retains the check for '<mode>' and '<type>' for\n'allow_missing' objects as this check is merely input validation that\navoids interrogating the object store.\n\nSigned-off-by: Richard Oliver <roliver@roku.com>\n---\n builtin/mktree.c | 11 ++++-------\n 1 file changed, 4 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin/mktree.c b/builtin/mktree.c\nindex 902edba6d2..f41fda6e7d 100644\n--- a/builtin/mktree.c\n+++ b/builtin/mktree.c\n@@ -116,15 +116,12 @@ static void mktree_line(char *buf, int nul_term_line, int allow_missing)\n \t\t\tpath, ptr, type_name(mode_type));\n \t}\n \n-\t/* Check the type of object identified by sha1 */\n-\tobj_type = oid_object_info(the_repository, &oid, NULL);\n-\tif (obj_type < 0) {\n-\t\tif (allow_missing) {\n-\t\t\t; /* no problem - missing objects are presumed to be of the right type */\n-\t\t} else {\n+\tif (!allow_missing) {\n+\t\t/* Check the type of object identified by sha1 */\n+\t\tobj_type = oid_object_info(the_repository, &oid, NULL);\n+\t\tif (obj_type < 0) {\n \t\t\tdie(\"entry '%s' object %s is unavailable\", path, oid_to_hex(&oid));\n \t\t}\n-\t} else {\n \t\tif (obj_type != mode_type) {\n \t\t\t/*\n \t\t\t * The object exists but is of the wrong type.\n-- \n2.36.1.467.g4f6db706e6.dirty\n\n"},{"id":"457389","messageId":"xmqqy1xwtsds.fsf@gitster.g","threadId":"57999","inReplyTo":"1566aed1-a38f-a9ca-241c-21b56d732328@roku.com","subject":"Re: [PATCH] mktree: Make '--missing' behave as documented","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-06-16T17:44:47Z","receivedAt":"2022-06-16T17:44:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Richard Oliver <roliver@roku.com> writes:\n\n> Subject: [PATCH] mktree: Make '--missing' behave as documented\n\nI would intead title the change as\n\n\t   mktree: disable object verification under '--missing'\n\nif I were writing this change.  It is a tad longer, but \"as\ndocumented\" is much less informative when this appears in \"git\nshortlog --no-merges\".\n\nBut wait for a bit.  I am not sold on \"disable\" 100% yet.\n\n> Do not make use of the object store to verify object type for\n> 'allow_missing' objects in mktree_line(). GIT-MKTREE(1) documents\n> '--missing' as disabling \"verif[ication] that each tree entry's sha1\n> identifies an existing object\".\n\nI am on the fence on this.  The current behaviour is not exactly\nforcing verification with \"--missing\".  Even if oid_object_info(),\nafter consulting the promisor remote, says that the object is not\navailable, the code does not complain, and in that sense, it is\nworking as documented.  It's just that it is doing unnecessary work\nthat you know you are not going to use.\n\n> This change retains the check for '<mode>' and '<type>' for\n> 'allow_missing' objects as this check is merely input validation that\n> avoids interrogating the object store.\n>\n> Signed-off-by: Richard Oliver <roliver@roku.com>\n> ---\n>  builtin/mktree.c | 11 ++++-------\n>  1 file changed, 4 insertions(+), 7 deletions(-)\n\n31c8221a (mktree: validate entry type in input, 2009-05-14) was\noverly eager to check with the local object store. They called the\nsha1_object_info() API to obtain the type information, allowed the\ncall to silently fail when the object was missing locally, but\nsanity checked the types opportunistically when the object did\nexist.  That implementation is hurting us now, but it is sort of\nexcusable because back then there was no lazy/on-demand downloading\nof individual objects that causes a long delay and materializes the\nobject, hence defeating the point of using \"--missing\".\n\nAnd that is why the code back then was OK but not anymore in today's\nworld.  Something like the analysis in the above paragraph should be\nin the commit log message to explain why we are making this change\ntoday.\n\nThis patch would be a good first cut as a starting point, but we\nprobably can do better by doing oid_object_info_extended() call with\nOBJECT_INFO_SKIP_FETCH_OBJECT bit (and probably QUICK bit, too) set,\nwith the current code structure.\n\nAnd when we do so, the title would not match the purpose of the\nchange.  The verification was disabled with \"--missing\" all along\nand that is not what we are changing.  What we will be fixing is the\nwasteful implementation.\n\n    mktree: do not check types of remote objects\n\n    With 31c8221a (mktree: validate entry type in input, 2009-05-14), we\n    called the sha1_object_info() API to obtain the type information,\n    but allowed the call to silently fail when the object was missing\n    locally, so that we can sanity-check the types opportunistically\n    when the object did exist.\n\n    The implementation is understandable because back then there was no\n    lazy/on-demand downloading of individual objects from the promisor\n    remotes that causes a long delay and materializes the object, hence\n    defeating the point of using \"--missing\".  The design is hurting us\n    now.\n\n    We could bypass the opportunistic type/mode consistency check\n    altogether when \"--missing\" is given, but instead, use the\n    oid_object_info_extended() API and tell it that we are only\n    interested in objects that locally exist and are immediately\n    available by passing OBJECT_INFO_SKIP_FETCH_OBJECT bit to it.  That\n    way, we will still retain the cheap and opportunistic sanity check\n    for local objects.\n\nor something like that, perhaps?\n\nThanks.\n\n> diff --git a/builtin/mktree.c b/builtin/mktree.c\n> index 902edba6d2..f41fda6e7d 100644\n> --- a/builtin/mktree.c\n> +++ b/builtin/mktree.c\n> @@ -116,15 +116,12 @@ static void mktree_line(char *buf, int nul_term_line, int allow_missing)\n>  \t\t\tpath, ptr, type_name(mode_type));\n>  \t}\n>  \n> -\t/* Check the type of object identified by sha1 */\n> -\tobj_type = oid_object_info(the_repository, &oid, NULL);\n> -\tif (obj_type < 0) {\n> -\t\tif (allow_missing) {\n> -\t\t\t; /* no problem - missing objects are presumed to be of the right type */\n> -\t\t} else {\n> +\tif (!allow_missing) {\n> +\t\t/* Check the type of object identified by sha1 */\n> +\t\tobj_type = oid_object_info(the_repository, &oid, NULL);\n> +\t\tif (obj_type < 0) {\n>  \t\t\tdie(\"entry '%s' object %s is unavailable\", path, oid_to_hex(&oid));\n>  \t\t}\n> -\t} else {\n>  \t\tif (obj_type != mode_type) {\n>  \t\t\t/*\n>  \t\t\t * The object exists but is of the wrong type.\n"},{"id":"457459","messageId":"20220617195028.2698928-1-jonathantanmy@google.com","threadId":"57999","inReplyTo":"YqrTsbXbEjx0Pabn@coredump.intra.peff.net","subject":"Re: [PATCH] is_promisor_object(): walk promisor packs in pack-order","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2022-06-17T19:50:27Z","receivedAt":"2022-06-17T19:50:34Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Jeff King <peff@peff.net> writes:\n> On Thu, Jun 16, 2022 at 02:07:41AM -0400, Jeff King wrote:\n> \n> > Those rev-lists run in 1.7s and 224s respectively. Ouch!\n> \n> Even though I expected the second one to be slow, I was shocked at just\n> how slow it was. The patch below speeds it up by a factor of 2, and I\n> think is worth applying separately, regardless of anything else being\n> discussed in this thread.\n\nThanks for the patch and the benchmark. This makes sense to me.\n"},{"id":"457618","messageId":"748f39a9-65aa-2110-cf92-7ddf81b5f507@roku.com","threadId":"57999","inReplyTo":"xmqqy1xwtsds.fsf@gitster.g","subject":"[PATCH] mktree: do not check type of remote objects","fromName":"Richard Oliver","fromEmail":"roliver@roku.com","sentAt":"2022-06-21T13:59:39Z","receivedAt":"2022-06-21T13:59:53Z","isPatch":true,"sender":{"key":"roliver@roku.com","avatar":null},"body":"On 16/06/2022 18:44, Junio C Hamano wrote:\n> This patch would be a good first cut as a starting point, but we\n> probably can do better by doing oid_object_info_extended() call with\n> OBJECT_INFO_SKIP_FETCH_OBJECT bit (and probably QUICK bit, too) set,\n> with the current code structure.\n> \n> And when we do so, the title would not match the purpose of the\n> change.  The verification was disabled with \"--missing\" all along\n> and that is not what we are changing.  What we will be fixing is the\n> wasteful implementation.\n> \n>     mktree: do not check types of remote objects\n> \n>     With 31c8221a (mktree: validate entry type in input, 2009-05-14), we\n>     called the sha1_object_info() API to obtain the type information,\n>     but allowed the call to silently fail when the object was missing\n>     locally, so that we can sanity-check the types opportunistically\n>     when the object did exist.\n> \n>     The implementation is understandable because back then there was no\n>     lazy/on-demand downloading of individual objects from the promisor\n>     remotes that causes a long delay and materializes the object, hence\n>     defeating the point of using \"--missing\".  The design is hurting us\n>     now.\n> \n>     We could bypass the opportunistic type/mode consistency check\n>     altogether when \"--missing\" is given, but instead, use the\n>     oid_object_info_extended() API and tell it that we are only\n>     interested in objects that locally exist and are immediately\n>     available by passing OBJECT_INFO_SKIP_FETCH_OBJECT bit to it.  That\n>     way, we will still retain the cheap and opportunistic sanity check\n>     for local objects.\n\nI've prepared a patch below as per your suggestion.\n\nAs a side note, do you think we need to re-work some uses of the word\n'missing' in the documentation? Some uses of the word, such as in\nmktree, predate the concept of promisor remotes. The partial-clone.txt\ndocumentation differentiates between missing \"due to a partial clone\nor fetch\" and missing \"due to repository corruption\".  Would making\nsuch a distinction elsewhere be useful?\n\nCheers,\nRichard\n\n-- >8 --\nSubject: [PATCH] mktree: do not check type of remote objects\n\nWith 31c8221a (mktree: validate entry type in input, 2009-05-14), we\ncalled the sha1_object_info() API to obtain the type information, but\nallowed the call to silently fail when the object was missing locally,\nso that we can sanity-check the types opportunistically when the\nobject did exist.\n\nThe implementation is understandable because back then there was no\nlazy/on-demand downloading of individual objects from the promisor\nremotes that causes a long delay and materializes the object, hence\ndefeating the point of using \"--missing\".  The design is hurting us\nnow.\n\nWe could bypass the opportunistic type/mode consistency check\naltogether when \"--missing\" is given, but instead, use the\noid_object_info_extended() API and tell it that we are only interested\nin objects that locally exist and are immediately available by passing\nOBJECT_INFO_SKIP_FETCH_OBJECT bit to it.  That way, we will still\nretain the cheap and opportunistic sanity check for local objects.\n\nSigned-off-by: Richard Oliver <roliver@roku.com>\n---\n builtin/mktree.c | 11 +++++++++--\n 1 file changed, 9 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/mktree.c b/builtin/mktree.c\nindex 902edba6d2..cfadb52670 100644\n--- a/builtin/mktree.c\n+++ b/builtin/mktree.c\n@@ -116,8 +116,15 @@ static void mktree_line(char *buf, int nul_term_line, int allow_missing)\n \t\t\tpath, ptr, type_name(mode_type));\n \t}\n \n-\t/* Check the type of object identified by sha1 */\n-\tobj_type = oid_object_info(the_repository, &oid, NULL);\n+\t/* Check the type of object identified by oid without fetching objects */\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n+\toi.typep = &obj_type;\n+\tif (oid_object_info_extended(the_repository, &oid, &oi,\n+\t\t\t\t     OBJECT_INFO_LOOKUP_REPLACE |\n+\t\t\t\t     OBJECT_INFO_QUICK |\n+\t\t\t\t     OBJECT_INFO_SKIP_FETCH_OBJECT) < 0)\n+\t\tobj_type = -1;\n+\n \tif (obj_type < 0) {\n \t\tif (allow_missing) {\n \t\t\t; /* no problem - missing objects are presumed to be of the right type */\n-- \n2.36.1.467.g4f6db706e6.dirty\n\n"},{"id":"457630","messageId":"xmqqwndagdu3.fsf@gitster.g","threadId":"57999","inReplyTo":"748f39a9-65aa-2110-cf92-7ddf81b5f507@roku.com","subject":"Re: [PATCH] mktree: do not check type of remote objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-06-21T16:51:00Z","receivedAt":"2022-06-21T16:51:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Richard Oliver <roliver@roku.com> writes:\n\n> As a side note, do you think we need to re-work some uses of the word\n> 'missing' in the documentation? Some uses of the word, such as in\n> mktree, predate the concept of promisor remotes. The partial-clone.txt\n> documentation differentiates between missing \"due to a partial clone\n> or fetch\" and missing \"due to repository corruption\".  Would making\n> such a distinction elsewhere be useful?\n\nI do agree with that direction.  Back when the world was simpler,\nthere were just \"we have the object\" and \"we ought to have the\nobject but we do not see it\", the latter of which was a clear\nrepository corruption.  There was no third choice.\n\nWith the lazy/partial clone stuff, it is not a corrupted repository\nanymore when certain objects that are reachable during traversal is\nmissing (this is slightly different from a shallow clone in that a\nshallow history makes the traversal stop early, so at least objects\nin a shallow clone that are reachable during traversal must exist).\n\nSo, yes, I think the distinction between \"missing but shouldn't be\"\nand \"missing by design\" is a good thing to keep in mind.\n\nThanks.\n"},{"id":"457633","messageId":"xmqqilothpq9.fsf@gitster.g","threadId":"57999","inReplyTo":"748f39a9-65aa-2110-cf92-7ddf81b5f507@roku.com","subject":"Re: [PATCH] mktree: do not check type of remote objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-06-21T17:48:46Z","receivedAt":"2022-06-21T17:48:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Richard Oliver <roliver@roku.com> writes:\n\n> +\t/* Check the type of object identified by oid without fetching objects */\n> +\tstruct object_info oi = OBJECT_INFO_INIT;\n\nThis is -Wdecl-after-statement.\n\n> +\toi.typep = &obj_type;\n> +\tif (oid_object_info_extended(the_repository, &oid, &oi,\n> +\t\t\t\t     OBJECT_INFO_LOOKUP_REPLACE |\n> +\t\t\t\t     OBJECT_INFO_QUICK |\n> +\t\t\t\t     OBJECT_INFO_SKIP_FETCH_OBJECT) < 0)\n> +\t\tobj_type = -1;\n> +\n>  \tif (obj_type < 0) {\n>  \t\tif (allow_missing) {\n>  \t\t\t; /* no problem - missing objects are presumed to be of the right type */\n\n\nI've done an obvious and trivial fix-up locally while queueing.\n\nThanks.\n\n\ndiff --git a/builtin/mktree.c b/builtin/mktree.c\nindex cfadb52670..06d81400f5 100644\n--- a/builtin/mktree.c\n+++ b/builtin/mktree.c\n@@ -74,6 +74,7 @@ static void mktree_line(char *buf, int nul_term_line, int allow_missing)\n \tunsigned mode;\n \tenum object_type mode_type; /* object type derived from mode */\n \tenum object_type obj_type; /* object type derived from sha */\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n \tchar *path, *to_free = NULL;\n \tstruct object_id oid;\n \n@@ -117,7 +118,6 @@ static void mktree_line(char *buf, int nul_term_line, int allow_missing)\n \t}\n \n \t/* Check the type of object identified by oid without fetching objects */\n-\tstruct object_info oi = OBJECT_INFO_INIT;\n \toi.typep = &obj_type;\n \tif (oid_object_info_extended(the_repository, &oid, &oi,\n \t\t\t\t     OBJECT_INFO_LOOKUP_REPLACE |\n"}]}