{"thread":{"id":"51095","subject":"[PATCH 0/2] Partial clone fix: handling received REF_DELTA","startedAt":"2019-05-14T21:11:00Z","lastAt":"2019-06-03T22:23:42Z","messageCount":26,"participants":["Jonathan Tan","Johannes Schindelin","Jeff King","Junio C Hamano","Duy Nguyen","Nicolas Pitre","Jonathan Nieder"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"375566","messageId":"cover.1557868134.git.jonathantanmy@google.com","threadId":"51095","inReplyTo":null,"subject":"[PATCH 0/2] Partial clone fix: handling received REF_DELTA","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-05-14T21:10:53Z","receivedAt":"2019-05-14T21:11:00Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"There is an issue when fetching into a partial clone, and the server\nsends a REF_DELTA object that is based on a missing promisor object.\nHere is a fix; more details are in the commit message of patch 2.\n\nJonathan Tan (2):\n t5616: refactor packfile replacement\n index-pack: prefetch missing REF_DELTA bases\n\n builtin/index-pack.c | 26 ++++++++++-\n t/t5616-partial-clone.sh | 95 ++++++++++++++++++++++++++++++++++------\n 2 files changed, 106 insertions(+), 15 deletions(-)\n\n-- \n2.21.0.1020.gf2820cf01a-goog\n\n"},{"id":"375567","messageId":"991a3aa27dd7fe67adbed2e03502790932b5059c.1557868134.git.jonathantanmy@google.com","threadId":"51095","inReplyTo":"cover.1557868134.git.jonathantanmy@google.com","subject":"[PATCH 1/2] t5616: refactor packfile replacement","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-05-14T21:10:54Z","receivedAt":"2019-05-14T21:11:03Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"A subsequent patch will perform the same packfile replacement that is\nalready done twice, so refactor it into its own function. Also, the same\nsubsequent patch will use, in another way, part of the packfile\nreplacement functionality, so extract those out too.\n\nSigned-off-by: Jonathan Tan \n---\n t/t5616-partial-clone.sh | 34 +++++++++++++++++++++-------------\n 1 file changed, 21 insertions(+), 13 deletions(-)\n\ndiff --git a/t/t5616-partial-clone.sh b/t/t5616-partial-clone.sh\nindex 9a8f9886b3..7cc0c71556 100755\n--- a/t/t5616-partial-clone.sh\n+++ b/t/t5616-partial-clone.sh\n@@ -244,11 +244,25 @@ test_expect_success 'fetch what is specified on CLI even if already promised' '\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \n-# Converts bytes into a form suitable for inclusion in a sed command. For\n-# example, \"printf 'ab\\r\\n' | hex_unpack\" results in '\\x61\\x62\\x0d\\x0a'.\n-sed_escape () {\n-\tperl -e '$/ = undef; $input = <>; print unpack(\"H2\" x length($input), $input)' |\n-\t\tsed 's/\\(..\\)/\\\\x\\1/g'\n+# Converts bytes into their hexadecimal representation. For example,\n+# \"printf 'ab\\r\\n' | hex_unpack\" results in '61620d0a'.\n+hex_unpack () {\n+\tperl -e '$/ = undef; $input = <>; print unpack(\"H2\" x length($input), $input)'\n+}\n+\n+# Inserts $1 at the start of the string and every 2 characters thereafter.\n+intersperse () {\n+\tsed 's/\\(..\\)/'$1'\\1/g'\n+}\n+\n+# Create a one-time-sed command to replace the existing packfile with $1.\n+replace_packfile () {\n+\t# The protocol requires that the packfile be sent in sideband 1, hence\n+\t# the extra \\x01 byte at the beginning.\n+\tprintf \"1,/packfile/!c %04x\\\\\\\\x01%s0000\" \\\n+\t\t\"$(($(wc -c <$1) + 5))\" \\\n+\t\t\"$(hex_unpack <$1 | intersperse '\\\\x')\" \\\n+\t\t>\"$HTTPD_ROOT_PATH/one-time-sed\"\n }\n \n test_expect_success 'upon cloning, check that all refs point to objects' '\n@@ -270,10 +284,7 @@ test_expect_success 'upon cloning, check that all refs point to objects' '\n \t# Replace the existing packfile with the crafted one. The protocol\n \t# requires that the packfile be sent in sideband 1, hence the extra\n \t# \\x01 byte at the beginning.\n-\tprintf \"1,/packfile/!c %04x\\\\\\\\x01%s0000\" \\\n-\t\t\"$(($(wc -c \"$HTTPD_ROOT_PATH/one-time-sed\" &&\n+\treplace_packfile incomplete.pack &&\n \n \t# Use protocol v2 because the sed command looks for the \"packfile\"\n \t# section header.\n@@ -313,10 +324,7 @@ test_expect_success 'when partial cloning, tolerate server not sending target of\n \t# Replace the existing packfile with the crafted one. The protocol\n \t# requires that the packfile be sent in sideband 1, hence the extra\n \t# \\x01 byte at the beginning.\n-\tprintf \"1,/packfile/!c %04x\\\\\\\\x01%s0000\" \\\n-\t\t\"$(($(wc -c \"$HTTPD_ROOT_PATH/one-time-sed\" &&\n+\treplace_packfile incomplete.pack &&\n \n \t# Use protocol v2 because the sed command looks for the \"packfile\"\n \t# section header.\n-- \n2.21.0.1020.gf2820cf01a-goog\n\n"},{"id":"375568","messageId":"4fcaa4481b5fd2a76aa21263f997e00913db0e0f.1557868134.git.jonathantanmy@google.com","threadId":"51095","inReplyTo":"cover.1557868134.git.jonathantanmy@google.com","subject":"[PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-05-14T21:10:55Z","receivedAt":"2019-05-14T21:11:06Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"When fetching, the client sends \"have\" commit IDs indicating that the\nserver does not need to send any object referenced by those commits,\nreducing network I/O. When the client is a partial clone, the client\nstill sends \"have\"s in this way, even if it does not have every object\nreferenced by a commit it sent as \"have\".\n\nIf a server omits such an object, it is fine: the client could lazily\nfetch that object before this fetch, and it can still do so after.\n\nThe issue is when the server sends a thin pack containing an object that\nis a REF_DELTA against such a missing object: index-pack fails to fix\nthe thin pack. When support for lazily fetching missing objects was\nadded in 8b4c0103a9 (\"sha1_file: support lazily fetching missing\nobjects\", 2017-12-08), support in index-pack was turned off in the\nbelief that it accesses the repo only to do hash collision checks.\nHowever, this is not true: it also needs to access the repo to resolve\nREF_DELTA bases.\n\nSupport for lazy fetching should still generally be turned off in\nindex-pack because it is used as part of the lazy fetching process\nitself (if not, infinite loops may occur), but we do need to fetch the\nREF_DELTA bases. (When fetching REF_DELTA bases, it is unlikely that\nthose are REF_DELTA themselves, because we do not send \"have\" when\nmaking such fetches.)\n\nTo resolve this, prefetch all missing REF_DELTA bases before attempting\nto resolve them. This both ensures that all bases are attempted to be\nfetched, and ensures that we make only one request per index-pack\ninvocation, and not one request per missing object.\n\nSigned-off-by: Jonathan Tan \n---\n builtin/index-pack.c | 26 +++++++++++++++--\n t/t5616-partial-clone.sh | 61 ++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 85 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex ccf4eb7e9b..0d55f73b0b 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -14,6 +14,7 @@\n #include \"thread-utils.h\"\n #include \"packfile.h\"\n #include \"object-store.h\"\n+#include \"fetch-object.h\"\n \n static const char index_pack_usage[] =\n \"git index-pack [-v] [-o ] [--keep | --keep=] [--verify] [--strict] ( | --stdin [--fix-thin] [])\";\n@@ -1351,6 +1352,25 @@ static void fix_unresolved_deltas(struct hashfile *f)\n \t\tsorted_by_pos[i] = &ref_deltas[i];\n \tQSORT(sorted_by_pos, nr_ref_deltas, delta_pos_compare);\n \n+\tif (repository_format_partial_clone) {\n+\t\t/*\n+\t\t * Prefetch the delta bases.\n+\t\t */\n+\t\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n+\t\tfor (i = 0; i < nr_ref_deltas; i++) {\n+\t\t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n+\t\t\tif (!oid_object_info_extended(the_repository, &d->oid,\n+\t\t\t\t\t\t NULL,\n+\t\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH))\n+\t\t\t\tcontinue;\n+\t\t\toid_array_append(&to_fetch, &d->oid);\n+\t\t}\n+\t\tif (to_fetch.nr)\n+\t\t\tfetch_objects(repository_format_partial_clone,\n+\t\t\t\t to_fetch.oid, to_fetch.nr);\n+\t\toid_array_clear(&to_fetch);\n+\t}\n+\n \tfor (i = 0; i < nr_ref_deltas; i++) {\n \t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n \t\tenum object_type type;\n@@ -1650,8 +1670,10 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tint report_end_of_input = 0;\n \n \t/*\n-\t * index-pack never needs to fetch missing objects, since it only\n-\t * accesses the repo to do hash collision checks\n+\t * index-pack never needs to fetch missing objects except when\n+\t * REF_DELTA bases are missing (which are explicitly handled). It only\n+\t * accesses the repo to do hash collision checks and to check which\n+\t * REF_DELTA bases need to be fetched.\n \t */\n \tfetch_if_missing = 0;\n \ndiff --git a/t/t5616-partial-clone.sh b/t/t5616-partial-clone.sh\nindex 7cc0c71556..f1baf83502 100755\n--- a/t/t5616-partial-clone.sh\n+++ b/t/t5616-partial-clone.sh\n@@ -339,4 +339,65 @@ test_expect_success 'when partial cloning, tolerate server not sending target of\n \t! test -e \"$HTTPD_ROOT_PATH/one-time-sed\"\n '\n \n+test_expect_success 'tolerate server sending REF_DELTA against missing promisor objects' '\n+\tSERVER=\"$HTTPD_DOCUMENT_ROOT_PATH/server\" &&\n+\trm -rf \"$SERVER\" repo &&\n+\ttest_create_repo \"$SERVER\" &&\n+\ttest_config -C \"$SERVER\" uploadpack.allowfilter 1 &&\n+\ttest_config -C \"$SERVER\" uploadpack.allowanysha1inwant 1 &&\n+\n+\t# Create a commit with a blob to be used as a delta base.\n+\tfor i in $(test_seq 10)\n+\tdo\n+\t\techo \"this is a line\" >>\"$SERVER/foo.txt\"\n+\tdone &&\n+\tgit -C \"$SERVER\" add foo.txt &&\n+\tgit -C \"$SERVER\" commit -m bar &&\n+\tgit -C \"$SERVER\" rev-parse HEAD:foo.txt >deltabase &&\n+\n+\tgit -c protocol.version=2 clone --no-checkout \\\n+\t\t--filter=blob:none $HTTPD_URL/one_time_sed/server repo &&\n+\n+\t# Sanity check to ensure that the client does not have that blob.\n+\tgit -C repo rev-list --objects --exclude-promisor-objects \\\n+\t\t-- $(cat deltabase) >objlist &&\n+\ttest_line_count = 0 objlist &&\n+\n+\t# Another commit. This commit will be fetched by the client.\n+\techo \"abcdefghijklmnopqrstuvwxyz\" >>\"$SERVER/foo.txt\" &&\n+\tgit -C \"$SERVER\" add foo.txt &&\n+\tgit -C \"$SERVER\" commit -m baz &&\n+\n+\t# Pack a thin pack containing, among other things, HEAD:foo.txt\n+\t# delta-ed against HEAD^:foo.txt.\n+\tprintf \"%s\\n--not\\n%s\\n\" \\\n+\t\t$(git -C \"$SERVER\" rev-parse HEAD) \\\n+\t\t$(git -C \"$SERVER\" rev-parse HEAD^) |\n+\t\tgit -C \"$SERVER\" pack-objects --thin --stdout >thin.pack &&\n+\n+\t# Ensure that the pack contains one delta against HEAD^:foo.txt. Since\n+\t# the delta contains at least 26 novel characters, the size cannot be\n+\t# contained in 4 bits, so the object header will take up 2 bytes. The\n+\t# most significant nybble of the first byte is 0b1111 (0b1 to indicate\n+\t# that the header continues, and 0b111 to indicate REF_DELTA), followed\n+\t# by any 3 nybbles, then the OID of the delta base.\n+\tgit -C \"$SERVER\" rev-parse HEAD^:foo.txt >deltabase &&\n+\tprintf \"f.,..%s\" $(intersperse \",\" want &&\n+\thex_unpack have &&\n+\tgrep $(cat want) have &&\n+\n+\treplace_packfile thin.pack &&\n+\n+\t# Use protocol v2 because the sed command looks for the \"packfile\"\n+\t# section header.\n+\ttest_config -C \"$SERVER\" protocol.version 2 &&\n+\n+\t# Fetch the thin pack and ensure that index-pack is able to handle the\n+\t# REF_DELTA object with a missing promisor delta base.\n+\tgit -C repo -c protocol.version=2 fetch &&\n+\n+\t# Ensure that the one-time-sed script was used.\n+\t! test -e \"$HTTPD_ROOT_PATH/one-time-sed\"\n+'\n+\n test_done\n-- \n2.21.0.1020.gf2820cf01a-goog\n\n"},{"id":"375610","messageId":"nycvar.QRO.7.76.6.1905151032500.44@tvgsbejvaqbjf.bet","threadId":"51095","inReplyTo":"991a3aa27dd7fe67adbed2e03502790932b5059c.1557868134.git.jonathantanmy@google.com","subject":"Re: [PATCH 1/2] t5616: refactor packfile replacement","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-05-15T08:36:52Z","receivedAt":"2019-05-15T08:36:50Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Jonathan,\n\nOn Tue, 14 May 2019, Jonathan Tan wrote:\n\n> diff --git a/t/t5616-partial-clone.sh b/t/t5616-partial-clone.sh\n> index 9a8f9886b3..7cc0c71556 100755\n> --- a/t/t5616-partial-clone.sh\n> +++ b/t/t5616-partial-clone.sh\n> @@ -244,11 +244,25 @@ test_expect_success 'fetch what is specified on CLI even if already promised' '\n> . \"$TEST_DIRECTORY\"/lib-httpd.sh\n> start_httpd\n>\n> -# Converts bytes into a form suitable for inclusion in a sed command. For\n> -# example, \"printf 'ab\\r\\n' | hex_unpack\" results in '\\x61\\x62\\x0d\\x0a'.\n> -sed_escape () {\n> -\tperl -e '$/ = undef; $input = <>; print unpack(\"H2\" x length($input), $input)' |\n> -\t\tsed 's/\\(..\\)/\\\\x\\1/g'\n> +# Converts bytes into their hexadecimal representation. For example,\n> +# \"printf 'ab\\r\\n' | hex_unpack\" results in '61620d0a'.\n> +hex_unpack () {\n> +\tperl -e '$/ = undef; $input = <>; print unpack(\"H2\" x length($input), $input)'\n> +}\n> +\n> +# Inserts $1 at the start of the string and every 2 characters thereafter.\n> +intersperse () {\n> +\tsed 's/\\(..\\)/'$1'\\1/g'\n> +}\n> +\n> +# Create a one-time-sed command to replace the existing packfile with $1.\n> +replace_packfile () {\n> +\t# The protocol requires that the packfile be sent in sideband 1, hence\n> +\t# the extra \\x01 byte at the beginning.\n> +\tprintf \"1,/packfile/!c %04x\\\\\\\\x01%s0000\" \\\n> +\t\t\"$(($(wc -c <$1) + 5))\" \\\n> +\t\t\"$(hex_unpack <$1 | intersperse '\\\\x')\" \\\n> +\t\t>\"$HTTPD_ROOT_PATH/one-time-sed\"\n> }\n\nUrgh. This is not a problem *this* patch introduces, but why on Earth do\nwe have to do complicated computations in shell code using an unholy mix\nof complex sed and Perl invocations, making things fragile and slow? We do\nhave such a nice facility is the t/test-tool helper...\n\nThe refactoring itself looks correct to me, of course.\n\nThanks,\nDscho\n\n>\n> test_expect_success 'upon cloning, check that all refs point to objects' '\n> @@ -270,10 +284,7 @@ test_expect_success 'upon cloning, check that all refs point to objects' '\n> \t# Replace the existing packfile with the crafted one. The protocol\n> \t# requires that the packfile be sent in sideband 1, hence the extra\n> \t# \\x01 byte at the beginning.\n> -\tprintf \"1,/packfile/!c %04x\\\\\\\\x01%s0000\" \\\n> -\t\t\"$(($(wc -c -\t\t\"$(sed_escape -\t\t>\"$HTTPD_ROOT_PATH/one-time-sed\" &&\n> +\treplace_packfile incomplete.pack &&\n>\n> \t# Use protocol v2 because the sed command looks for the \"packfile\"\n> \t# section header.\n> @@ -313,10 +324,7 @@ test_expect_success 'when partial cloning, tolerate server not sending target of\n> \t# Replace the existing packfile with the crafted one. The protocol\n> \t# requires that the packfile be sent in sideband 1, hence the extra\n> \t# \\x01 byte at the beginning.\n> -\tprintf \"1,/packfile/!c %04x\\\\\\\\x01%s0000\" \\\n> -\t\t\"$(($(wc -c -\t\t\"$(sed_escape -\t\t>\"$HTTPD_ROOT_PATH/one-time-sed\" &&\n> +\treplace_packfile incomplete.pack &&\n>\n> \t# Use protocol v2 because the sed command looks for the \"packfile\"\n> \t# section header.\n> --\n> 2.21.0.1020.gf2820cf01a-goog\n>\n>\n"},{"id":"375612","messageId":"nycvar.QRO.7.76.6.1905151040240.44@tvgsbejvaqbjf.bet","threadId":"51095","inReplyTo":"4fcaa4481b5fd2a76aa21263f997e00913db0e0f.1557868134.git.jonathantanmy@google.com","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-05-15T08:46:42Z","receivedAt":"2019-05-15T08:46:39Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Jonathan,\n\nOn Tue, 14 May 2019, Jonathan Tan wrote:\n\n> When fetching, the client sends \"have\" commit IDs indicating that the\n> server does not need to send any object referenced by those commits,\n> reducing network I/O. When the client is a partial clone, the client\n> still sends \"have\"s in this way, even if it does not have every object\n> referenced by a commit it sent as \"have\".\n>\n> If a server omits such an object, it is fine: the client could lazily\n> fetch that object before this fetch, and it can still do so after.\n>\n> The issue is when the server sends a thin pack containing an object that\n> is a REF_DELTA against such a missing object: index-pack fails to fix\n> the thin pack. When support for lazily fetching missing objects was\n> added in 8b4c0103a9 (\"sha1_file: support lazily fetching missing\n> objects\", 2017-12-08), support in index-pack was turned off in the\n> belief that it accesses the repo only to do hash collision checks.\n> However, this is not true: it also needs to access the repo to resolve\n> REF_DELTA bases.\n>\n> Support for lazy fetching should still generally be turned off in\n> index-pack because it is used as part of the lazy fetching process\n> itself (if not, infinite loops may occur), but we do need to fetch the\n> REF_DELTA bases. (When fetching REF_DELTA bases, it is unlikely that\n> those are REF_DELTA themselves, because we do not send \"have\" when\n> making such fetches.)\n>\n> To resolve this, prefetch all missing REF_DELTA bases before attempting\n> to resolve them. This both ensures that all bases are attempted to be\n> fetched, and ensures that we make only one request per index-pack\n> invocation, and not one request per missing object.\n\nHmm. I wonder whether this can lead to *really* undesirable behavior, e.g.\nwith deep delta chains. The client would possibly have to fetch the\nREF_DELTA object, but that would also be delivered in a thin pack with\n*another* REF_DELTA object, and the same over and over again, with plenty\nof round trips that kill performance really well.\n\nWouldn't it make more sense to introduce a new term like `promised`\n(instead of `have`)? Both client and server will have to know about this,\nand it would be a new capability, of course, but that way the server could\nknow that it has to send the entire delta chain.\n\nOf course, this would be quite a bit more involved than the current patch\n:-(\n\nCiao,\nDscho\n\n> Signed-off-by: Jonathan Tan \n> ---\n> builtin/index-pack.c | 26 +++++++++++++++--\n> t/t5616-partial-clone.sh | 61 ++++++++++++++++++++++++++++++++++++++++\n> 2 files changed, 85 insertions(+), 2 deletions(-)\n>\n> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n> index ccf4eb7e9b..0d55f73b0b 100644\n> --- a/builtin/index-pack.c\n> +++ b/builtin/index-pack.c\n> @@ -14,6 +14,7 @@\n> #include \"thread-utils.h\"\n> #include \"packfile.h\"\n> #include \"object-store.h\"\n> +#include \"fetch-object.h\"\n>\n> static const char index_pack_usage[] =\n> \"git index-pack [-v] [-o ] [--keep | --keep=] [--verify] [--strict] ( | --stdin [--fix-thin] [])\";\n> @@ -1351,6 +1352,25 @@ static void fix_unresolved_deltas(struct hashfile *f)\n> \t\tsorted_by_pos[i] = &ref_deltas[i];\n> \tQSORT(sorted_by_pos, nr_ref_deltas, delta_pos_compare);\n>\n> +\tif (repository_format_partial_clone) {\n> +\t\t/*\n> +\t\t * Prefetch the delta bases.\n> +\t\t */\n> +\t\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n> +\t\tfor (i = 0; i < nr_ref_deltas; i++) {\n> +\t\t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n> +\t\t\tif (!oid_object_info_extended(the_repository, &d->oid,\n> +\t\t\t\t\t\t NULL,\n> +\t\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH))\n> +\t\t\t\tcontinue;\n> +\t\t\toid_array_append(&to_fetch, &d->oid);\n> +\t\t}\n> +\t\tif (to_fetch.nr)\n> +\t\t\tfetch_objects(repository_format_partial_clone,\n> +\t\t\t\t to_fetch.oid, to_fetch.nr);\n> +\t\toid_array_clear(&to_fetch);\n> +\t}\n> +\n> \tfor (i = 0; i < nr_ref_deltas; i++) {\n> \t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n> \t\tenum object_type type;\n> @@ -1650,8 +1670,10 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n> \tint report_end_of_input = 0;\n>\n> \t/*\n> -\t * index-pack never needs to fetch missing objects, since it only\n> -\t * accesses the repo to do hash collision checks\n> +\t * index-pack never needs to fetch missing objects except when\n> +\t * REF_DELTA bases are missing (which are explicitly handled). It only\n> +\t * accesses the repo to do hash collision checks and to check which\n> +\t * REF_DELTA bases need to be fetched.\n> \t */\n> \tfetch_if_missing = 0;\n>\n> diff --git a/t/t5616-partial-clone.sh b/t/t5616-partial-clone.sh\n> index 7cc0c71556..f1baf83502 100755\n> --- a/t/t5616-partial-clone.sh\n> +++ b/t/t5616-partial-clone.sh\n> @@ -339,4 +339,65 @@ test_expect_success 'when partial cloning, tolerate server not sending target of\n> \t! test -e \"$HTTPD_ROOT_PATH/one-time-sed\"\n> '\n>\n> +test_expect_success 'tolerate server sending REF_DELTA against missing promisor objects' '\n> +\tSERVER=\"$HTTPD_DOCUMENT_ROOT_PATH/server\" &&\n> +\trm -rf \"$SERVER\" repo &&\n> +\ttest_create_repo \"$SERVER\" &&\n> +\ttest_config -C \"$SERVER\" uploadpack.allowfilter 1 &&\n> +\ttest_config -C \"$SERVER\" uploadpack.allowanysha1inwant 1 &&\n> +\n> +\t# Create a commit with a blob to be used as a delta base.\n> +\tfor i in $(test_seq 10)\n> +\tdo\n> +\t\techo \"this is a line\" >>\"$SERVER/foo.txt\"\n> +\tdone &&\n> +\tgit -C \"$SERVER\" add foo.txt &&\n> +\tgit -C \"$SERVER\" commit -m bar &&\n> +\tgit -C \"$SERVER\" rev-parse HEAD:foo.txt >deltabase &&\n> +\n> +\tgit -c protocol.version=2 clone --no-checkout \\\n> +\t\t--filter=blob:none $HTTPD_URL/one_time_sed/server repo &&\n> +\n> +\t# Sanity check to ensure that the client does not have that blob.\n> +\tgit -C repo rev-list --objects --exclude-promisor-objects \\\n> +\t\t-- $(cat deltabase) >objlist &&\n> +\ttest_line_count = 0 objlist &&\n> +\n> +\t# Another commit. This commit will be fetched by the client.\n> +\techo \"abcdefghijklmnopqrstuvwxyz\" >>\"$SERVER/foo.txt\" &&\n> +\tgit -C \"$SERVER\" add foo.txt &&\n> +\tgit -C \"$SERVER\" commit -m baz &&\n> +\n> +\t# Pack a thin pack containing, among other things, HEAD:foo.txt\n> +\t# delta-ed against HEAD^:foo.txt.\n> +\tprintf \"%s\\n--not\\n%s\\n\" \\\n> +\t\t$(git -C \"$SERVER\" rev-parse HEAD) \\\n> +\t\t$(git -C \"$SERVER\" rev-parse HEAD^) |\n> +\t\tgit -C \"$SERVER\" pack-objects --thin --stdout >thin.pack &&\n> +\n> +\t# Ensure that the pack contains one delta against HEAD^:foo.txt. Since\n> +\t# the delta contains at least 26 novel characters, the size cannot be\n> +\t# contained in 4 bits, so the object header will take up 2 bytes. The\n> +\t# most significant nybble of the first byte is 0b1111 (0b1 to indicate\n> +\t# that the header continues, and 0b111 to indicate REF_DELTA), followed\n> +\t# by any 3 nybbles, then the OID of the delta base.\n> +\tgit -C \"$SERVER\" rev-parse HEAD^:foo.txt >deltabase &&\n> +\tprintf \"f.,..%s\" $(intersperse \",\" want &&\n> +\thex_unpack have &&\n> +\tgrep $(cat want) have &&\n> +\n> +\treplace_packfile thin.pack &&\n> +\n> +\t# Use protocol v2 because the sed command looks for the \"packfile\"\n> +\t# section header.\n> +\ttest_config -C \"$SERVER\" protocol.version 2 &&\n> +\n> +\t# Fetch the thin pack and ensure that index-pack is able to handle the\n> +\t# REF_DELTA object with a missing promisor delta base.\n> +\tgit -C repo -c protocol.version=2 fetch &&\n> +\n> +\t# Ensure that the one-time-sed script was used.\n> +\t! test -e \"$HTTPD_ROOT_PATH/one-time-sed\"\n> +'\n> +\n> test_done\n> --\n> 2.21.0.1020.gf2820cf01a-goog\n>\n>\n"},{"id":"375636","messageId":"20190515182253.105984-1-jonathantanmy@google.com","threadId":"51095","inReplyTo":"nycvar.QRO.7.76.6.1905151032500.44@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 1/2] t5616: refactor packfile replacement","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-05-15T18:22:53Z","receivedAt":"2019-05-15T18:22:59Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> > +# Converts bytes into their hexadecimal representation. For example,\n> > +# \"printf 'ab\\r\\n' | hex_unpack\" results in '61620d0a'.\n> > +hex_unpack () {\n> > +\tperl -e '$/ = undef; $input = <>; print unpack(\"H2\" x length($input), $input)'\n> > +}\n> > +\n> > +# Inserts $1 at the start of the string and every 2 characters thereafter.\n> > +intersperse () {\n> > +\tsed 's/\\(..\\)/'$1'\\1/g'\n> > +}\n> > +\n> > +# Create a one-time-sed command to replace the existing packfile with $1.\n> > +replace_packfile () {\n> > +\t# The protocol requires that the packfile be sent in sideband 1, hence\n> > +\t# the extra \\x01 byte at the beginning.\n> > +\tprintf \"1,/packfile/!c %04x\\\\\\\\x01%s0000\" \\\n> > +\t\t\"$(($(wc -c <$1) + 5))\" \\\n> > +\t\t\"$(hex_unpack <$1 | intersperse '\\\\x')\" \\\n> > +\t\t>\"$HTTPD_ROOT_PATH/one-time-sed\"\n> > }\n> \n> Urgh. This is not a problem *this* patch introduces, but why on Earth do\n> we have to do complicated computations in shell code using an unholy mix\n> of complex sed and Perl invocations, making things fragile and slow? We do\n> have such a nice facility is the t/test-tool helper...\n\nThis might be a good #leftoverbits. I'm not sure which part you think\nneeds to be replaced - maybe the thing that goes into one-time-sed?\n\n> The refactoring itself looks correct to me, of course.\n\nThanks, and thanks for taking a look at this.\n"},{"id":"375637","messageId":"20190515182812.107420-1-jonathantanmy@google.com","threadId":"51095","inReplyTo":"nycvar.QRO.7.76.6.1905151040240.44@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-05-15T18:28:12Z","receivedAt":"2019-05-15T18:28:18Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> > To resolve this, prefetch all missing REF_DELTA bases before attempting\n> > to resolve them. This both ensures that all bases are attempted to be\n> > fetched, and ensures that we make only one request per index-pack\n> > invocation, and not one request per missing object.\n> \n> Hmm. I wonder whether this can lead to *really* undesirable behavior, e.g.\n> with deep delta chains. The client would possibly have to fetch the\n> REF_DELTA object, but that would also be delivered in a thin pack with\n> *another* REF_DELTA object, and the same over and over again, with plenty\n> of round trips that kill performance really well.\n\nWhen the client fetches the REF_DELTA base, it won't be a REF_DELTA\nobject itself because Git makes these fetches without any \"have\" lines,\nso the server doesn't know anything to delta against. Admittedly, this\nis just due how to we implemented it - if later we find a way to\noptimize the lazy fetches by adding \"have\", then we'll have to revisit\nthis.\n\nQuoting from the commit message:\n\n> > (When fetching REF_DELTA bases, it is unlikely that\n> > those are REF_DELTA themselves, because we do not send \"have\" when\n> > making such fetches.)\n\nI tried to address this point with this sentence in the commit message.\nIf you think that this should be addressed more clearly in the commit\nmessage, let me know if you have any suggestions.\n\n> Wouldn't it make more sense to introduce a new term like `promised`\n> (instead of `have`)? Both client and server will have to know about this,\n> and it would be a new capability, of course, but that way the server could\n> know that it has to send the entire delta chain.\n> \n> Of course, this would be quite a bit more involved than the current patch\n> :-(\n\nI think this can also be solved by omitting \"thin-pack\". We might want\nto do this once we optimize the lazy fetches by adding \"have\".\n\nThanks for taking a look at this.\n"},{"id":"375667","messageId":"20190515231617.GA1395@sigill.intra.peff.net","threadId":"51095","inReplyTo":"4fcaa4481b5fd2a76aa21263f997e00913db0e0f.1557868134.git.jonathantanmy@google.com","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-15T23:16:18Z","receivedAt":"2019-05-15T23:25:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 14, 2019 at 02:10:55PM -0700, Jonathan Tan wrote:\n\n> Support for lazy fetching should still generally be turned off in\n> index-pack because it is used as part of the lazy fetching process\n> itself (if not, infinite loops may occur), but we do need to fetch the\n> REF_DELTA bases. (When fetching REF_DELTA bases, it is unlikely that\n> those are REF_DELTA themselves, because we do not send \"have\" when\n> making such fetches.)\n\nI agree that the current implementation (and probably any sane\nimplementation) would not send us a delta if we have not provided any\nhaves. But this does mean that a malicious server could send a client\ninto an infinite loop.\n\nPretty unlikely, but should we put some kind of circuit-breaker into the\nclient to ensure this?\n\n> To resolve this, prefetch all missing REF_DELTA bases before attempting\n> to resolve them. This both ensures that all bases are attempted to be\n> fetched, and ensures that we make only one request per index-pack\n> invocation, and not one request per missing object.\n\nAh, but now things get more tricky.\n\nYou are assuming that the server does not ever send a REF_DELTA unless\nthe base object is not present in the pack (it would use OFS_DELTA\ninstead). If we imagine a server which did, then there are two\nimplications:\n\n 1. We might pre-fetch a full copy of an object that we don't need.\n It's just that it's stored as a delta in the pack which we are\n currently indexing.\n\n 2. If we pre-fetch multiple objects, some of them may be REF_DELTAs\n against each other, leading to an infinite loop.\n\nOff the top of my head, I am pretty sure your assumption holds for all\nversions of Git that support delta-base-offset[1]. But that feels a lot\nless certain to me. I could imagine an alternate server implementation,\nfor example, that is gluing together packs and does not try hard to\norder the base before the delta, which would require it to use REF_DELTA\ninstead of OFS_DELTA.\n\nThat's sort of contrived, but it does feel like we're introducing a\nreally subtle requirement on the server here, which might close off\noptions to us in the future.\n\nUnfortunately, I can't really think of a way for an existing client to\nsolve this without doing individual fetches for each REF_DELTA as we\nencounter a need for it. In fact, even then we may lose if our ordering\nis unlucky. E.g., imagine we have two packfile entries whose object ids\n(which we don't know yet!) are X and Y, and they are stored as\nREF_DELTAs with bases Z and X, respectively. Then either:\n\n 1. We try to resolve X first. We fetch Z on-demand, and reconstruct X.\n We're lucky, because when we try to resolve Y, we see that we\n already have its base X.\n\n 2. We try to resolve Y first. We fetch X on-demand, and reconstruct Y.\n We're unlucky; we then resolve X, but only after on-demand fetching\n Z and reconstructing it do we realize that we already had it.\n\nSo really, pre-fetching all of the REF_DELTAs just means we always hit\nthe unlucky case. But even with careful on-demand fetching, our worst\ncase is the same (and even worse in terms of latency).\n\nI dunno. Maybe we should just ignore it. It's a fundamental issue with\npartial clones that we're going to have to fetch extra junk here anyway,\nbecause what the server _optimally_ would do is not send us deltas\nagainst objects we don't have anyway. We just don't have an efficient\nway to tell it what we do have.\n\nIf we're willing to modify the format, one thing we _could_ do is have\nthe server communicate the expectations for each base. I.e., introduce a\nnew THIN_DELTA type that behaves exactly as a REF_DELTA, but with the\nextra 1-bit of knowledge that the server knows it is not including the\nbase in the pack. I'm not sure how painful that retro-fitting would be.\nIt would need at least a new capability and options to pack-objects and\nindex-pack. We might be tight on bits in the packfile type field.\n\n-Peff\n\n[1] Of course there are versions of Git that don't support\n delta-base-offset. They wouldn't support partial clones either, but\n it's possible to fetch into a partially-cloned repository from\n another remote. Given how old and rare such versions are, I think we\n can probably discount it entirely. I'm much more concerned about\n alternate implementations, or trying our hands for future\n pack-objects optimizations.\n"},{"id":"375682","messageId":"xmqqk1er5g48.fsf@gitster-ct.c.googlers.com","threadId":"51095","inReplyTo":"20190515231617.GA1395@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-05-16T01:43:03Z","receivedAt":"2019-05-16T01:50:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I agree that the current implementation (and probably any sane\n> implementation) would not send us a delta if we have not provided any\n> haves. But this does mean that a malicious server could send a client\n> into an infinite loop.\n>\n> Pretty unlikely, but should we put some kind of circuit-breaker into the\n> client to ensure this?\n\nThat's a pretty good point. Would it be suffice to have a new\noption to tell index-pack that fattens a thin pack and unpack-objects\nthat expands objects in a small incoming packfile into loose objects\nthat they are forbidden from on-demand fatching during this invocation,\nas it is an error for the packfile they are digesting to depend on a\nlazy objects?\n\n> I dunno. Maybe we should just ignore it. It's a fundamental issue with\n> partial clones that we're going to have to fetch extra junk here anyway,\n\nWould it be an option not to ask for a thin pack in the first place?\n\n> If we're willing to modify the format, one thing we _could_ do is have\n> the server communicate the expectations for each base. I.e., introduce a\n> new THIN_DELTA type that behaves exactly as a REF_DELTA, but with the\n> extra 1-bit of knowledge that the server knows it is not including the\n> base in the pack. I'm not sure how painful that retro-fitting would be.\n> It would need at least a new capability and options to pack-objects and\n> index-pack. We might be tight on bits in the packfile type field.\n\nThe type field is tight, but I wonder how much such a new\nrepresentation would help. Unless the receiving end blindly trusts\nwhat the sender says, there needs to be a logic to detect cyclic\ndependencies while following such a delta chain to lazy-fill\npromised objects on the receiving end anyway, no?\n\n"},{"id":"375695","messageId":"20190516040451.GF4596@sigill.intra.peff.net","threadId":"51095","inReplyTo":"xmqqk1er5g48.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-16T04:04:51Z","receivedAt":"2019-05-16T04:04:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 16, 2019 at 10:43:03AM +0900, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > I agree that the current implementation (and probably any sane\n> > implementation) would not send us a delta if we have not provided any\n> > haves. But this does mean that a malicious server could send a client\n> > into an infinite loop.\n> >\n> > Pretty unlikely, but should we put some kind of circuit-breaker into the\n> > client to ensure this?\n> \n> That's a pretty good point. Would it be suffice to have a new\n> option to tell index-pack that fattens a thin pack and unpack-objects\n> that expands objects in a small incoming packfile into loose objects\n> that they are forbidden from on-demand fatching during this invocation,\n> as it is an error for the packfile they are digesting to depend on a\n> lazy objects?\n\nYeah, that's what I was thinking. The parent index-pack sets an\nenvironment variable for \"do not recurse to get partials\" when it calls\nfetch. But that said...\n\n> > I dunno. Maybe we should just ignore it. It's a fundamental issue with\n> > partial clones that we're going to have to fetch extra junk here anyway,\n> \n> Would it be an option not to ask for a thin pack in the first place?\n\nYes, that seems much simpler. The flag is really \"do not ask for a thin\npack, and do not pass --fix-thin to index-pack\". And this recursion\nshould not kick in when --fix-thin is not in effect (I didn't check\nJonathan's patch to see whether that is the case, but I think that ought\nto be the rule regardless of how we decide to address the recursion\nissue).\n\nOne snag: I don't think unpack-objects understands --fix-thin. It just\nlooks in the object database and finds either a recently-written object\nor one we already have, and it doesn't care about the difference.\n\nFor that matter, does unpack-objects need the same treatment here? I\nguess not, because it does not disable fetch_if_missing in the same way.\nI guess it is already susceptible to the infinite-recursion thing, then.\nOr maybe not. We always use index-pack for promisor remotes. So even\nthough the _first_ fetch which yields REF_DELTA may be from a\nnon-promisor, any subsequent one would be. So we'd never recurse more\nthan once. So I think the emergent behavior does what we want. ;)\n\nI worked up some patches a while ago to try to replace unpack-objects\nwith an index-pack mode that explodes objects (just so we could stop\nkeeping two almost-the-same code bases around, both of which are\nsecurity-critical as they take in untrusted objects, and one of which\nclearly gets a lot more attention than the other). But I got hung up a\nbit on their strategies for handling base objects. IIRC, the\nunpack-objects one does things in a different order that's more\nefficient for some cases, and I worried that somebody would care.\n\nI can resurrect that if there's interest (though I do think by the\nreasoning above that it's orthogonal to this particular patch series).\n\n> > If we're willing to modify the format, one thing we _could_ do is have\n> > the server communicate the expectations for each base. I.e., introduce a\n> > new THIN_DELTA type that behaves exactly as a REF_DELTA, but with the\n> > extra 1-bit of knowledge that the server knows it is not including the\n> > base in the pack. I'm not sure how painful that retro-fitting would be.\n> > It would need at least a new capability and options to pack-objects and\n> > index-pack. We might be tight on bits in the packfile type field.\n> \n> The type field is tight, but I wonder how much such a new\n> representation would help. Unless the receiving end blindly trusts\n> what the sender says, there needs to be a logic to detect cyclic\n> dependencies while following such a delta chain to lazy-fill\n> promised objects on the receiving end anyway, no?\n\nIt would let the client know how the server expects it to handle each\ndelta. The client can then (without trusting the server) say:\n\n - this is REF_DELTA; the server claims that the base is in this pack,\n so I will not prefetch it. If it turns out not to be, then it is an\n error and I will reject the pack (and _not_ try to fetch it on\n demand)\n\n - this is THIN_DELTA; I will try to fetch it from the promisor remote,\n and not recurse (because the promisor fetch will not ask for a\n thin-pack). If it also turns out to be in the pack, so be it. We'll\n have two copies and will have wasted the server's bandwidth.\n\nSo the client gets to optimize by following the server's directions, but\nthe worst case for a lying server is not a big deal (it's just more\npessimal).\n\n-Peff\n"},{"id":"375732","messageId":"20190516182646.173332-1-jonathantanmy@google.com","threadId":"51095","inReplyTo":"20190515231617.GA1395@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-05-16T18:26:46Z","receivedAt":"2019-05-16T18:26:51Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> On Tue, May 14, 2019 at 02:10:55PM -0700, Jonathan Tan wrote:\n> \n> > Support for lazy fetching should still generally be turned off in\n> > index-pack because it is used as part of the lazy fetching process\n> > itself (if not, infinite loops may occur), but we do need to fetch the\n> > REF_DELTA bases. (When fetching REF_DELTA bases, it is unlikely that\n> > those are REF_DELTA themselves, because we do not send \"have\" when\n> > making such fetches.)\n> \n> I agree that the current implementation (and probably any sane\n> implementation) would not send us a delta if we have not provided any\n> haves. But this does mean that a malicious server could send a client\n> into an infinite loop.\n> \n> Pretty unlikely, but should we put some kind of circuit-breaker into the\n> client to ensure this?\n\nI thought of this - such a server could, but it seems to me that it\nwould be similar to a server streaming random bytes to us without\nstopping (which is already possible).\n\n> > To resolve this, prefetch all missing REF_DELTA bases before attempting\n> > to resolve them. This both ensures that all bases are attempted to be\n> > fetched, and ensures that we make only one request per index-pack\n> > invocation, and not one request per missing object.\n> \n> Ah, but now things get more tricky.\n> \n> You are assuming that the server does not ever send a REF_DELTA unless\n> the base object is not present in the pack (it would use OFS_DELTA\n> instead). If we imagine a server which did, then there are two\n> implications:\n> \n> 1. We might pre-fetch a full copy of an object that we don't need.\n> It's just that it's stored as a delta in the pack which we are\n> currently indexing.\n> \n> 2. If we pre-fetch multiple objects, some of them may be REF_DELTAs\n> against each other, leading to an infinite loop.\n> \n> Off the top of my head, I am pretty sure your assumption holds for all\n> versions of Git that support delta-base-offset[1]. But that feels a lot\n> less certain to me. I could imagine an alternate server implementation,\n> for example, that is gluing together packs and does not try hard to\n> order the base before the delta, which would require it to use REF_DELTA\n> instead of OFS_DELTA.\n\nA cursory glance makes me think that REF_DELTA against a base object\nalso in the pack is already correctly handled. Right before the\ninvocation of conclude_pack() (which calls fix_unresolved_deltas(), the\nfunction I modified), resolve_deltas() is invoked. The latter invokes\nresolve_base() (directly or through threaded_second_pass()) which\ninvokes find_unresolved_deltas(), which invokes\nfind_unresolved_deltas_1(), which seems to handle both REF_DELTA and\nOFS_DELTA.\n\nSnipping the rest as I don't think we need to solve those if we can\nhandle REF_DELTA being against an object in a pack, but let me know if\nyou think that some of the points there still need to be addressed.\n"},{"id":"375742","messageId":"20190516211226.GE9816@sigill.intra.peff.net","threadId":"51095","inReplyTo":"20190516182646.173332-1-jonathantanmy@google.com","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-16T21:12:26Z","receivedAt":"2019-05-16T21:12:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 16, 2019 at 11:26:46AM -0700, Jonathan Tan wrote:\n\n> > Pretty unlikely, but should we put some kind of circuit-breaker into the\n> > client to ensure this?\n> \n> I thought of this - such a server could, but it seems to me that it\n> would be similar to a server streaming random bytes to us without\n> stopping (which is already possible).\n\nTrue. I was thinking mainly of the infinite-redirection protections we\nput in place for https. But I agree that in general, since we don't have\ninherent limits on the size of workloads, that servers can already troll\nclients pretty hard in a variety of ways.\n\nSo I could go either way, though I do think it makes sense for on-demand\nfetches for partial clones to avoid asking for thin packs as a general\nprinciple. As a matter of fact, should partial clones _always_ avoid\nasking for thin packs? That would make this issue go away entirely.\n\nSometimes it would be more efficient (we do not have to get an extra\nbase object just to resolve the delta we needed) but sometimes worse (if\nwe did actually have the base, it's a win). Whether it's a win would\ndepend on the \"hit\" rate, and I suspect that is heavily dependent on\nworkload characteristics (what kind of filtering is in use, are we\ntopping up in a non-partial way, etc).\n\n> > Off the top of my head, I am pretty sure your assumption holds for all\n> > versions of Git that support delta-base-offset[1]. But that feels a lot\n> > less certain to me. I could imagine an alternate server implementation,\n> > for example, that is gluing together packs and does not try hard to\n> > order the base before the delta, which would require it to use REF_DELTA\n> > instead of OFS_DELTA.\n> \n> A cursory glance makes me think that REF_DELTA against a base object\n> also in the pack is already correctly handled. Right before the\n> invocation of conclude_pack() (which calls fix_unresolved_deltas(), the\n> function I modified), resolve_deltas() is invoked. The latter invokes\n> resolve_base() (directly or through threaded_second_pass()) which\n> invokes find_unresolved_deltas(), which invokes\n> find_unresolved_deltas_1(), which seems to handle both REF_DELTA and\n> OFS_DELTA.\n> \n> Snipping the rest as I don't think we need to solve those if we can\n> handle REF_DELTA being against an object in a pack, but let me know if\n> you think that some of the points there still need to be addressed.\n\nRight, REF_DELTA is definitely correctly handled currently, and I don't\nthink that would break with your patch. It's just that your patch would\nintroduce a bunch of extra traffic as we request bases separately that\nare already in the pack.\n\n-Peff\n"},{"id":"375743","messageId":"20190516213056.221406-1-jonathantanmy@google.com","threadId":"51095","inReplyTo":"20190516211226.GE9816@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-05-16T21:30:56Z","receivedAt":"2019-05-16T21:31:02Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> On Thu, May 16, 2019 at 11:26:46AM -0700, Jonathan Tan wrote:\n> \n> > > Pretty unlikely, but should we put some kind of circuit-breaker into the\n> > > client to ensure this?\n> > \n> > I thought of this - such a server could, but it seems to me that it\n> > would be similar to a server streaming random bytes to us without\n> > stopping (which is already possible).\n> \n> True. I was thinking mainly of the infinite-redirection protections we\n> put in place for https. But I agree that in general, since we don't have\n> inherent limits on the size of workloads, that servers can already troll\n> clients pretty hard in a variety of ways.\n> \n> So I could go either way, though I do think it makes sense for on-demand\n> fetches for partial clones to avoid asking for thin packs as a general\n> principle.\n\nThis should not be a problem since fetch-pack can already know that\nwe're doing an on-demand fetch (args->no_dependents), so we should be\nable to either plumb a \"no-thin-pack\" arg in the same way or rename\nargs->no_dependents to also encompass the no-thin-pack option. But this\ncan be done separately from this patch set, I think.\n\n> As a matter of fact, should partial clones _always_ avoid\n> asking for thin packs? That would make this issue go away entirely.\n> \n> Sometimes it would be more efficient (we do not have to get an extra\n> base object just to resolve the delta we needed) but sometimes worse (if\n> we did actually have the base, it's a win). Whether it's a win would\n> depend on the \"hit\" rate, and I suspect that is heavily dependent on\n> workload characteristics (what kind of filtering is in use, are we\n> topping up in a non-partial way, etc).\n\nI think it's best if we still allow servers to serve thin packs. For\nexample, if we're excluding only large blobs, clients would still want\nservers to be able to delta against blobs that they have.\n\n> Right, REF_DELTA is definitely correctly handled currently, and I don't\n> think that would break with your patch. It's just that your patch would\n> introduce a bunch of extra traffic as we request bases separately that\n> are already in the pack.\n\nAh...I see. For this problem, I think that it can be solved with the\n\"if (objects[d->obj_no].real_type != OBJ_REF_DELTA)\" check that the\nexisting code uses before calling read_object(). I'll include this in\nthe next reroll if any other issue comes up.\n"},{"id":"375744","messageId":"20190516214257.GD10787@sigill.intra.peff.net","threadId":"51095","inReplyTo":"20190516213056.221406-1-jonathantanmy@google.com","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-16T21:42:58Z","receivedAt":"2019-05-16T21:43:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 16, 2019 at 02:30:56PM -0700, Jonathan Tan wrote:\n\n> > So I could go either way, though I do think it makes sense for on-demand\n> > fetches for partial clones to avoid asking for thin packs as a general\n> > principle.\n> \n> This should not be a problem since fetch-pack can already know that\n> we're doing an on-demand fetch (args->no_dependents), so we should be\n> able to either plumb a \"no-thin-pack\" arg in the same way or rename\n> args->no_dependents to also encompass the no-thin-pack option. But this\n> can be done separately from this patch set, I think.\n\nYeah, I think it can be done separately. Though the two may intermingle\nif we want to instruct index-pack that it should not try to pre-fetch if\nwe did not ask for a thin pack.\n\n> > As a matter of fact, should partial clones _always_ avoid\n> > asking for thin packs? That would make this issue go away entirely.\n> > \n> > Sometimes it would be more efficient (we do not have to get an extra\n> > base object just to resolve the delta we needed) but sometimes worse (if\n> > we did actually have the base, it's a win). Whether it's a win would\n> > depend on the \"hit\" rate, and I suspect that is heavily dependent on\n> > workload characteristics (what kind of filtering is in use, are we\n> > topping up in a non-partial way, etc).\n> \n> I think it's best if we still allow servers to serve thin packs. For\n> example, if we're excluding only large blobs, clients would still want\n> servers to be able to delta against blobs that they have.\n\nYes, this is getting into the hit-rate thing I mentioned. You're right\nthat for a reasonably typical case of \"no blobs over 10MB\" we'd have a\nvery high hit rate, and disabling thin packs would almost certainly be a\nbig loss.\n\nI guess even when we have a \"miss\", the cost is usually not that high\neither. If we get A as a delta against B, then in the non-thin-pack case\nwe transfer all of A. In the thin-pack case with pre-fetch we transfer\nall of B, and then the delta. But the delta is often small enough\ncompared to the total content that it's not that big a deal either way.\nThere are pathological cases, of course, but that's already true. :)\n\nSo you're right, it's probably still a win to use thin packs when we\ncan.\n\n> > Right, REF_DELTA is definitely correctly handled currently, and I don't\n> > think that would break with your patch. It's just that your patch would\n> > introduce a bunch of extra traffic as we request bases separately that\n> > are already in the pack.\n> \n> Ah...I see. For this problem, I think that it can be solved with the\n> \"if (objects[d->obj_no].real_type != OBJ_REF_DELTA)\" check that the\n> existing code uses before calling read_object(). I'll include this in\n> the next reroll if any other issue comes up.\n\nI'm confused about this. Aren't we pre-fetching before we've actually\nresolved deltas? The base could be in the pack as a true base, and we\nmight have seen it already then. But it could itself be a delta, and we\nwouldn't know we have it until we resolve it (this gets into the\nlucky/unlucky ordering thing).\n\n-Peff\n"},{"id":"375763","messageId":"20190516231509.253998-1-jonathantanmy@google.com","threadId":"51095","inReplyTo":"20190516214257.GD10787@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-05-16T23:15:09Z","receivedAt":"2019-05-16T23:15:15Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> > > Right, REF_DELTA is definitely correctly handled currently, and I don't\n> > > think that would break with your patch. It's just that your patch would\n> > > introduce a bunch of extra traffic as we request bases separately that\n> > > are already in the pack.\n> > \n> > Ah...I see. For this problem, I think that it can be solved with the\n> > \"if (objects[d->obj_no].real_type != OBJ_REF_DELTA)\" check that the\n> > existing code uses before calling read_object(). I'll include this in\n> > the next reroll if any other issue comes up.\n> \n> I'm confused about this. Aren't we pre-fetching before we've actually\n> resolved deltas? The base could be in the pack as a true base, and we\n> might have seen it already then. But it could itself be a delta, and we\n> wouldn't know we have it until we resolve it (this gets into the\n> lucky/unlucky ordering thing).\n\nresolve_deltas(), invoked before any new code introduced in this patch,\nhas this comment:\n\n> /*\n> * Second pass:\n> * - for all non-delta objects, look if it is used as a base for\n> * deltas;\n> * - if used as a base, uncompress the object and apply all deltas,\n> * recursively checking if the resulting object is used as a base\n> * for some more deltas.\n> */\n\nI haven't seen any code that contradicts this comment. And looking at\nthe code, for each non-delta object, I think that all deltas are checked\n- regardless of whether they appear before or after that non-delta\nobject. (find_ref_delta() does a binary search from 0 to\nnr_ref_deltas, calculated in parse_pack_objects() which happens before\nany resolution of deltas.)\n\nAnd find_unresolved_deltas_1() (called from resolve_deltas() indirectly)\nsets the real_type when it resolves a delta, as far as I can tell.\n\nSo there is more than one \"resolve deltas\" step - resolve_deltas() and\nthen fix_unresolved_deltas(). The pre-fetching happens only during the\nlatter.\n"},{"id":"375779","messageId":"20190517010950.GA30146@sigill.intra.peff.net","threadId":"51095","inReplyTo":"20190516231509.253998-1-jonathantanmy@google.com","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-17T01:09:51Z","receivedAt":"2019-05-17T01:09:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 16, 2019 at 04:15:09PM -0700, Jonathan Tan wrote:\n\n> > /*\n> > * Second pass:\n> > * - for all non-delta objects, look if it is used as a base for\n> > * deltas;\n> > * - if used as a base, uncompress the object and apply all deltas,\n> > * recursively checking if the resulting object is used as a base\n> > * for some more deltas.\n> > */\n> \n> I haven't seen any code that contradicts this comment. And looking at\n> the code, for each non-delta object, I think that all deltas are checked\n> - regardless of whether they appear before or after that non-delta\n> object. (find_ref_delta() does a binary search from 0 to\n> nr_ref_deltas, calculated in parse_pack_objects() which happens before\n> any resolution of deltas.)\n> \n> And find_unresolved_deltas_1() (called from resolve_deltas() indirectly)\n> sets the real_type when it resolves a delta, as far as I can tell.\n> \n> So there is more than one \"resolve deltas\" step - resolve_deltas() and\n> then fix_unresolved_deltas(). The pre-fetching happens only during the\n> latter.\n\nOK, that is better than I realized. But I think there is still one\ninteresting case: what happens if a thin delta is used as the base for a\nnon-thin delta (even one that is OFS_DELTA)?\n\nWe cannot handle that second delta until the third pass in\nfix_unresolved_deltas(), because we do not realize we have the base\nuntil we resolve the thin delta.\n\nSpecifically, I wonder:\n\n - do we pre-fetch it, not realizing that we will soon have the base?\n That's not ideal, but I think is necessary if we pre-fetch (and is\n still a worst case even if we did single on-demand fetches).\n\n - will we ever append a presumed-thin base to the pack, only to later\n realize that we already have that object, creating a duplicate\n object in the pack? If so, do we handle this correctly when\n generating the index (I know we've had issues in the past and have\n expressly forbidden duplicates from appearing in the index; even\n having a duplicate in the pack stream itself is non-ideal, though,\n as it screws up things like on-disk size calculations).\n\n Because of the sorting in fix_unresolved_deltas(), I think this\n could easily be prevented if the non-thin delta is OFS_DELTA (by\n just checking for the base in our already-found list of objects\n before we call read_object_file(). But for REF_DELTA, I think we\n have no way of knowing that appending is the wrong thing (and no\n good way of backing it out afterwards).\n\n-Peff\n"},{"id":"375781","messageId":"20190517012234.GA31027@sigill.intra.peff.net","threadId":"51095","inReplyTo":"20190517010950.GA30146@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-17T01:22:34Z","receivedAt":"2019-05-17T01:22:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 16, 2019 at 09:09:50PM -0400, Jeff King wrote:\n\n> - will we ever append a presumed-thin base to the pack, only to later\n> realize that we already have that object, creating a duplicate\n> object in the pack? If so, do we handle this correctly when\n> generating the index (I know we've had issues in the past and have\n> expressly forbidden duplicates from appearing in the index; even\n> having a duplicate in the pack stream itself is non-ideal, though,\n> as it screws up things like on-disk size calculations).\n> \n> Because of the sorting in fix_unresolved_deltas(), I think this\n> could easily be prevented if the non-thin delta is OFS_DELTA (by\n> just checking for the base in our already-found list of objects\n> before we call read_object_file(). But for REF_DELTA, I think we\n> have no way of knowing that appending is the wrong thing (and no\n> good way of backing it out afterwards).\n\nActually, I think even for REF_DELTA our pack-objects would never\nproduce such a pack, because IIRC we _always_ put bases in the pack\nbefore their deltas. But that's a pretty subtle thing to depend on. I'm\nfine with it if violating it just means things are slightly less\noptimal. I'm more worried if it means that index-pack silently produces\na bogus pack.\n\nI think to trigger it you'd have to manually assemble an evil pack as I\ndescribed (e.g., using the routines in t/lib-pack.sh). I'm going offline\nfor a bit, but I may have a go at it later tonight or tomorrow.\n\n-Peff\n"},{"id":"375785","messageId":"20190517043939.GA12063@sigill.intra.peff.net","threadId":"51095","inReplyTo":"20190517012234.GA31027@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-17T04:39:39Z","receivedAt":"2019-05-17T04:39:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 16, 2019 at 09:22:34PM -0400, Jeff King wrote:\n\n> On Thu, May 16, 2019 at 09:09:50PM -0400, Jeff King wrote:\n> \n> > - will we ever append a presumed-thin base to the pack, only to later\n> > realize that we already have that object, creating a duplicate\n> > object in the pack? If so, do we handle this correctly when\n> > generating the index (I know we've had issues in the past and have\n> > expressly forbidden duplicates from appearing in the index; even\n> > having a duplicate in the pack stream itself is non-ideal, though,\n> > as it screws up things like on-disk size calculations).\n> > \n> > Because of the sorting in fix_unresolved_deltas(), I think this\n> > could easily be prevented if the non-thin delta is OFS_DELTA (by\n> > just checking for the base in our already-found list of objects\n> > before we call read_object_file(). But for REF_DELTA, I think we\n> > have no way of knowing that appending is the wrong thing (and no\n> > good way of backing it out afterwards).\n> \n> Actually, I think even for REF_DELTA our pack-objects would never\n> produce such a pack, because IIRC we _always_ put bases in the pack\n> before their deltas. But that's a pretty subtle thing to depend on. I'm\n> fine with it if violating it just means things are slightly less\n> optimal. I'm more worried if it means that index-pack silently produces\n> a bogus pack.\n> \n> I think to trigger it you'd have to manually assemble an evil pack as I\n> described (e.g., using the routines in t/lib-pack.sh). I'm going offline\n> for a bit, but I may have a go at it later tonight or tomorrow.\n\nOK, doing so wasn't _too_ bad, though I did have to resurrect the\nhorrible generator patch from [1]. My results are below. But more\nimportantly, there is good news.\n\nAs it turns out, index-pack does not handle these complicated cases at\nall! In the final fix_unresolved_deltas(), we are only looking for thin\ndeltas, and anything that was not yet resolved is assumed to be a thin\nobject. In many of these cases we _could_ resolve them if we tried\nharder. But that is good news for us because it means that these\nexpectations about delta relationships are already there, and the\npre-fetch done by your patch should always be 100% correct and\nefficient.\n\nIf you knew this already and were wondering what I've been babbling\nabout this whole time, then apologies for the noise. If not, then I hope\nyou enjoyed this deep dive into the inner workings of our delta\nresolution. :) This was a part of index-pack I hadn't really had to\ntouch before, so I learned a lot.\n\nHere's the script I used to test this (the comments explaining what's\ngoing on were obviously written _after_ I ran it and figured out why it\ndidn't work; I had initially expected the first one to pass).\n\nI don't really think it's worth carrying these tests in our tree. I'm\nmostly just showing my work.\n\n-- >8 --\ndiff --git a/t/lib-pack.sh b/t/lib-pack.sh\nindex c4d907a450..43785335e0 100644\n--- a/t/lib-pack.sh\n+++ b/t/lib-pack.sh\n@@ -77,6 +77,18 @@ pack_obj () {\n \t\t\t;;\n \t\tesac\n \t\t;;\n+\n+\t# blob containing \"\\7\\1\"\n+\t0231abe3332fca6abc6a7e0f8000473692ce8c83)\n+\t\tcase \"$2\" in\n+\t\t01d7713666f4de822776c7622c10f1b07de280dc)\n+\t\t\tprintf '\\165\\2\\61\\253\\343\\63\\57\\312\\152\\274\\152\\176' &&\n+\t\t\tprintf '\\17\\200\\0\\107\\66\\222\\316\\214\\203\\170\\234' &&\n+\t\t\tprintf '\\143\\142\\142\\142\\147\\0\\0\\0\\53\\0\\16'\n+\t\t\treturn\n+\t\t\t;;\n+\t\tesac\n+\t\t;;\n \tesac\n \n \t# If it's not a delta, we can convince pack-objects to generate a pack\ndiff --git a/t/t1234-foo.sh b/t/t1234-foo.sh\nnew file mode 100755\nindex 0000000000..22f1e85f81\n--- /dev/null\n+++ b/t/t1234-foo.sh\n@@ -0,0 +1,61 @@\n+#!/bin/sh\n+\n+test_description='delta resolution torture tests'\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/lib-pack.sh\n+\n+# blobs that lib-pack.sh knows about\n+A=0231abe3332fca6abc6a7e0f8000473692ce8c83\n+B=01d7713666f4de822776c7622c10f1b07de280dc\n+C=e68fe8129b546b101aee9510c5328e7f21ca1d18\n+\n+test_expect_success 'create local copy of object C' '\n+\t# contents from lib-pack.sh\n+\tprintf \"\\\\7\\\\76\" | git hash-object -w --stdin\n+'\n+\n+# Create a pack with a delta chain A->B->C. The important things are:\n+#\n+# - these are all REF_DELTA, which is what lib-pack produces\n+#\n+# - the delta from $C is thin; the receiver should have that object\n+#\n+# - the base (if present) comes _before_ the delta in the file (we assume\n+# that the final delta resolution uses pack order to break ties)\n+test_expect_success 'create thin pack' '\n+\t{\n+\t\tpack_header 2 &&\n+\t\tpack_obj $B $C &&\n+\t\tpack_obj $A $B\n+\t} >ba.pack &&\n+\tpack_trailer ba.pack\n+'\n+\n+# In theory this could work if we noticed that we had just generated $B.\n+# However, fix_unresolved_deltas() never looks in the pack; it assumes anything\n+# we found at that point is thin, and looks only at our regular object\n+# database for the base.\n+test_expect_failure 'index ba.pack' '\n+\tgit index-pack --fix-thin --stdin ab.pack &&\n+\tpack_trailer ab.pack\n+'\n+\n+# This one is even less likely to work, because when we are processing $A and\n+# look for its base $B, we would not yet have processed $B. So we know nothing\n+# about it. It would take two passes (and in the general case, up to O(n)\n+# passes) to resolve everything (assuming we even start looking in the current\n+# pack for objects, as ba.pack would require).\n+test_expect_failure 'index ab.pack' '\n+\tgit index-pack --fix-thin --stdin > I think to trigger it you'd have to manually assemble an evil pack as I\n> > described (e.g., using the routines in t/lib-pack.sh). I'm going offline\n> > for a bit, but I may have a go at it later tonight or tomorrow.\n> \n> OK, doing so wasn't _too_ bad, though I did have to resurrect the\n> horrible generator patch from [1]. My results are below. But more\n> importantly, there is good news.\n\nOh, I forgot my [1]. It was this message:\n\n https://public-inbox.org/git/20130823182409.GA30130@sigill.intra.peff.net/\n\nwhich explained how I hacked up pack-objects to generate the binary goo\nin lib-pack.sh. Here's my forward-ported version of it, in case we need\nit again.\n\nI do think it would be useful for debugging and experimenting to have a\nmode for pack-objects that takes in a list of instructions (add object\nX, make it a delta against object Y) that skips its usual ordering and\ndelta constraints. This isn't it, but it's enough to hackily get what\nyou need. ;)\n\n---\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 9f424aabab..87955d9404 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3234,6 +3234,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tstruct argv_array rp = ARGV_ARRAY_INIT;\n \tint rev_list_unpacked = 0, rev_list_all = 0, rev_list_reflog = 0;\n \tint rev_list_index = 0;\n+\tint magic = 0;\n \tstruct string_list keep_pack_list = STRING_LIST_INIT_NODUP;\n \tstruct option pack_objects_options[] = {\n \t\tOPT_SET_INT('q', \"quiet\", &progress,\n@@ -3321,6 +3322,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t\t N_(\"do not pack objects in promisor packfiles\")),\n \t\tOPT_BOOL(0, \"delta-islands\", &use_delta_islands,\n \t\t\t N_(\"respect islands during delta compression\")),\n+\t\tOPT_BOOL(0, \"magic\", &magic, \"make deltas\"),\n \t\tOPT_END(),\n \t};\n \n@@ -3337,6 +3339,34 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \targc = parse_options(argc, argv, prefix, pack_objects_options,\n \t\t\t pack_usage, 0);\n \n+\tif (magic) {\n+\t\tstruct object_id oid;\n+\t\tstruct delta_index *index;\n+\t\tvoid *src, *trg, *delta;\n+\t\tenum object_type src_type, trg_type;\n+\t\tunsigned long src_size, trg_size, delta_size, z_delta_size;\n+\t\tunsigned char header[10];\n+\t\tunsigned long header_len;\n+\n+\t\tget_oid(argv[0], &oid);\n+\t\ttrg = read_object_file(&oid, &trg_type, &trg_size);\n+\n+\t\tget_oid(argv[1], &oid);\n+\t\tsrc = read_object_file(&oid, &src_type, &src_size);\n+\n+\t\tindex = create_delta_index(src, src_size);\n+\t\tdelta = create_delta(index, trg, trg_size, &delta_size, 8192);\n+\n+\t\tz_delta_size = do_compress(&delta, delta_size);\n+\t\theader_len = encode_in_pack_object_header(header, sizeof(header),\n+\t\t\t\t\t\t\t OBJ_REF_DELTA,\n+\t\t\t\t\t\t\t delta_size);\n+\t\tfwrite(header, 1, header_len, stdout);\n+\t\tfwrite(oid.hash, 1, the_hash_algo->rawsz, stdout);\n+\t\tfwrite(delta, 1, z_delta_size, stdout);\n+\t\treturn 0;\n+\t}\n+\n \tif (argc) {\n \t\tbase_name = argv[0];\n \t\targc--;\n"},{"id":"375790","messageId":"CACsJy8CNyug3wvZ+6ts1nzgWyPF1JqC0LceP-HzMHjqvCr2Ugw@mail.gmail.com","threadId":"51095","inReplyTo":"20190517043939.GA12063@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-05-17T07:20:42Z","receivedAt":"2019-05-17T07:21:10Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, May 17, 2019 at 12:35 PM Jeff King wrote:\n> As it turns out, index-pack does not handle these complicated cases at\n> all! In the final fix_unresolved_deltas(), we are only looking for thin\n> deltas, and anything that was not yet resolved is assumed to be a thin\n> object. In many of these cases we _could_ resolve them if we tried\n> harder. But that is good news for us because it means that these\n> expectations about delta relationships are already there, and the\n> pre-fetch done by your patch should always be 100% correct and\n> efficient.\n\nIs it worth keeping some of these notes in the \"third pass\" comment\nblock in index-pack.c to help future readers?\n-- \nDuy\n"},{"id":"375795","messageId":"20190517085509.GA20039@sigill.intra.peff.net","threadId":"51095","inReplyTo":"CACsJy8CNyug3wvZ+6ts1nzgWyPF1JqC0LceP-HzMHjqvCr2Ugw@mail.gmail.com","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-17T08:55:10Z","receivedAt":"2019-05-17T08:55:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 17, 2019 at 02:20:42PM +0700, Duy Nguyen wrote:\n\n> On Fri, May 17, 2019 at 12:35 PM Jeff King wrote:\n> > As it turns out, index-pack does not handle these complicated cases at\n> > all! In the final fix_unresolved_deltas(), we are only looking for thin\n> > deltas, and anything that was not yet resolved is assumed to be a thin\n> > object. In many of these cases we _could_ resolve them if we tried\n> > harder. But that is good news for us because it means that these\n> > expectations about delta relationships are already there, and the\n> > pre-fetch done by your patch should always be 100% correct and\n> > efficient.\n> \n> Is it worth keeping some of these notes in the \"third pass\" comment\n> block in index-pack.c to help future readers?\n\nPerhaps. I started on the patch below, but I had trouble in the commit\nmessage. I couldn't find the part of the code that explains why we would\nnever produce this combination, though empirically we do not.\n\n-- >8 --\nSubject: [PATCH] index-pack: describe an implication of our thin resolving\n\nAfter digging into the delta resolution code, I discovered a surprising\n(to me, anyway) implication of our strategy: we could never find a\nnon-thin delta with a thin delta as its base. This is OK because\npack-objects will never produce such a combination, because....?\n\nSigned-off-by: Jeff King \n---\n builtin/index-pack.c | 7 +++++++\n 1 file changed, 7 insertions(+)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex ccf4eb7e9b..f40f4560d4 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1224,6 +1224,13 @@ static void resolve_deltas(void)\n * Third pass:\n * - append objects to convert thin pack to full pack if required\n * - write the final pack hash\n+ *\n+ * Note that we assume all deltas at this phase are thin. We take only a\n+ * single pass over the unresolved objects, and we look for bases only\n+ * in our set of already-existing objects, _not_ other objects within this\n+ * pack. This means that we would never find an object A stored as a delta\n+ * against another object B in this pack, when B is a thin delta against a base\n+ * not in the pack.\n */\n static void fix_unresolved_deltas(struct hashfile *f);\n static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned char *pack_hash)\n-- \n2.22.0.rc0.544.g1eb4087842\n\n"},{"id":"375809","messageId":"nycvar.QRO.7.76.6.1905172032550.46@tvgsbejvaqbjf.bet","threadId":"51095","inReplyTo":"20190515182812.107420-1-jonathantanmy@google.com","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-05-17T18:33:45Z","receivedAt":"2019-05-17T18:33:40Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Jonathan,\n\nOn Wed, 15 May 2019, Jonathan Tan wrote:\n\n> > > To resolve this, prefetch all missing REF_DELTA bases before attempting\n> > > to resolve them. This both ensures that all bases are attempted to be\n> > > fetched, and ensures that we make only one request per index-pack\n> > > invocation, and not one request per missing object.\n> >\n> > Hmm. I wonder whether this can lead to *really* undesirable behavior, e.g.\n> > with deep delta chains. The client would possibly have to fetch the\n> > REF_DELTA object, but that would also be delivered in a thin pack with\n> > *another* REF_DELTA object, and the same over and over again, with plenty\n> > of round trips that kill performance really well.\n>\n> When the client fetches the REF_DELTA base, it won't be a REF_DELTA\n> object itself because Git makes these fetches without any \"have\" lines,\n> so the server doesn't know anything to delta against. Admittedly, this\n> is just due how to we implemented it - if later we find a way to\n> optimize the lazy fetches by adding \"have\", then we'll have to revisit\n> this.\n\nAh! I *think* I understand this better now. Thank you.\n\n> Quoting from the commit message:\n>\n> > > (When fetching REF_DELTA bases, it is unlikely that\n> > > those are REF_DELTA themselves, because we do not send \"have\" when\n> > > making such fetches.)\n>\n> I tried to address this point with this sentence in the commit message.\n> If you think that this should be addressed more clearly in the commit\n> message, let me know if you have any suggestions.\n\nI totally read over this part of the commit message, apparently. My bad.\n\nSorry for the noise!\nDscho\n"},{"id":"375847","messageId":"CACsJy8AkhKX57RYL1Z+HZHqKbAKKOcLoRkgwg8bSnk+DW2+Nmg@mail.gmail.com","threadId":"51095","inReplyTo":"20190517085509.GA20039@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-05-18T11:39:32Z","receivedAt":"2019-05-18T11:40:00Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, May 17, 2019 at 3:55 PM Jeff King wrote:\n>\n> On Fri, May 17, 2019 at 02:20:42PM +0700, Duy Nguyen wrote:\n>\n> > On Fri, May 17, 2019 at 12:35 PM Jeff King wrote:\n> > > As it turns out, index-pack does not handle these complicated cases at\n> > > all! In the final fix_unresolved_deltas(), we are only looking for thin\n> > > deltas, and anything that was not yet resolved is assumed to be a thin\n> > > object. In many of these cases we _could_ resolve them if we tried\n> > > harder. But that is good news for us because it means that these\n> > > expectations about delta relationships are already there, and the\n> > > pre-fetch done by your patch should always be 100% correct and\n> > > efficient.\n> >\n> > Is it worth keeping some of these notes in the \"third pass\" comment\n> > block in index-pack.c to help future readers?\n>\n> Perhaps. I started on the patch below, but I had trouble in the commit\n> message. I couldn't find the part of the code that explains why we would\n> never produce this combination, though empirically we do not.\n\nThat still has some value even if your commit ends up with a question\nmark. There's not much to dig out of 636171cb80 (make index-pack able\nto complete thin packs., 2006-10-25). Adding Nico, maybe he still\nremembers...\n\n> -- >8 --\n> Subject: [PATCH] index-pack: describe an implication of our thin resolving\n>\n> After digging into the delta resolution code, I discovered a surprising\n> (to me, anyway) implication of our strategy: we could never find a\n> non-thin delta with a thin delta as its base. This is OK because\n> pack-objects will never produce such a combination, because....?\n>\n> Signed-off-by: Jeff King \n> ---\n> builtin/index-pack.c | 7 +++++++\n> 1 file changed, 7 insertions(+)\n>\n> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n> index ccf4eb7e9b..f40f4560d4 100644\n> --- a/builtin/index-pack.c\n> +++ b/builtin/index-pack.c\n> @@ -1224,6 +1224,13 @@ static void resolve_deltas(void)\n> * Third pass:\n> * - append objects to convert thin pack to full pack if required\n> * - write the final pack hash\n> + *\n> + * Note that we assume all deltas at this phase are thin. We take only a\n> + * single pass over the unresolved objects, and we look for bases only\n> + * in our set of already-existing objects, _not_ other objects within this\n> + * pack. This means that we would never find an object A stored as a delta\n> + * against another object B in this pack, when B is a thin delta against a base\n> + * not in the pack.\n> */\n> static void fix_unresolved_deltas(struct hashfile *f);\n> static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned char *pack_hash)\n> --\n> 2.22.0.rc0.544.g1eb4087842\n>\n\n\n-- \nDuy\n"},{"id":"375965","messageId":"nycvar.YSQ.7.76.1905201803520.1558@knanqh.ubzr","threadId":"51095","inReplyTo":"CACsJy8AkhKX57RYL1Z+HZHqKbAKKOcLoRkgwg8bSnk+DW2+Nmg@mail.gmail.com","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2019-05-20T23:04:14Z","receivedAt":"2019-05-20T23:04:22Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 18 May 2019, Duy Nguyen wrote:\n\n> On Fri, May 17, 2019 at 3:55 PM Jeff King wrote:\n> >\n> > On Fri, May 17, 2019 at 02:20:42PM +0700, Duy Nguyen wrote:\n> >\n> > > On Fri, May 17, 2019 at 12:35 PM Jeff King wrote:\n> > > > As it turns out, index-pack does not handle these complicated cases at\n> > > > all! In the final fix_unresolved_deltas(), we are only looking for thin\n> > > > deltas, and anything that was not yet resolved is assumed to be a thin\n> > > > object. In many of these cases we _could_ resolve them if we tried\n> > > > harder. But that is good news for us because it means that these\n> > > > expectations about delta relationships are already there, and the\n> > > > pre-fetch done by your patch should always be 100% correct and\n> > > > efficient.\n> > >\n> > > Is it worth keeping some of these notes in the \"third pass\" comment\n> > > block in index-pack.c to help future readers?\n> >\n> > Perhaps. I started on the patch below, but I had trouble in the commit\n> > message. I couldn't find the part of the code that explains why we would\n> > never produce this combination, though empirically we do not.\n\nGood question indeed.\n\n> That still has some value even if your commit ends up with a question\n> mark. There's not much to dig out of 636171cb80 (make index-pack able\n> to complete thin packs., 2006-10-25). Adding Nico, maybe he still\n> remembers...\n\nWhat about this comment in fix_unresolved_deltas():\n\n /*\n * Since many unresolved deltas may well be themselves base objects\n * for more unresolved deltas, we really want to include the\n * smallest number of base objects that would cover as much delta\n * as possible by picking the\n * trunc deltas first, allowing for other deltas to resolve without\n * additional base objects. Since most base objects are to be found\n * before deltas depending on them, a good heuristic is to start\n * resolving deltas in the same order as their position in the pack.\n */\n\nDoesn't that cover it?\n\nIn pack-objects, another comment says:\n\n * Depth value does not matter - find_deltas() will\n * never consider reused delta as the base object to\n * deltify other objects against, in order to avoid\n * circular deltas.\n\nSorry if I'm not of any help here. Although I used to have my brain \nwrapped around this code pretty tightly, it's been quite a while, and \nthe code did change as well since then.\n\n\nNicolas\n"},{"id":"376016","messageId":"20190521212023.GB14807@sigill.intra.peff.net","threadId":"51095","inReplyTo":"nycvar.YSQ.7.76.1905201803520.1558@knanqh.ubzr","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-21T21:20:23Z","receivedAt":"2019-05-21T21:20:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 20, 2019 at 07:04:14PM -0400, Nicolas Pitre wrote:\n\n> > That still has some value even if your commit ends up with a question\n> > mark. There's not much to dig out of 636171cb80 (make index-pack able\n> > to complete thin packs., 2006-10-25). Adding Nico, maybe he still\n> > remembers...\n> \n> What about this comment in fix_unresolved_deltas():\n> \n> /*\n> * Since many unresolved deltas may well be themselves base objects\n> * for more unresolved deltas, we really want to include the\n> * smallest number of base objects that would cover as much delta\n> * as possible by picking the\n> * trunc deltas first, allowing for other deltas to resolve without\n> * additional base objects. Since most base objects are to be found\n> * before deltas depending on them, a good heuristic is to start\n> * resolving deltas in the same order as their position in the pack.\n> */\n> \n> Doesn't that cover it?\n\nHmm. It does help, but only because my earlier comments were actually\nwrong. I was claiming that index-pack would not be able to resolve \"A\"\nfrom the delta chain when A is a regular delta, B is a thin delta, and C\nis not in the pack.\n\nBecause I did not see how we would ever find base \"B\" in that third pass\nof fix_unresolved_deltas(), because we look only for objects we already\nhave on disk.\n\nBut I think the trick that I was missing is that if we see \"B\" first,\nwe'll resolve it against C that we already have, but then we'll _also_\nlook for children that this now enables us to resolve. So we'd resolve\n\"A\" at that point, and then when we later hit \"A\" in the loop from\nfix_unresolved_deltas(), we skip it because of this:\n\n if (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n\tcontinue;\n\nSo this situation _can_ happen, and we do handle it properly. I don't\nknow why the tests I showed in [1] didn't work. Obviously I botched\nsomething.\n\nI'm still not quite sure what would happen if we see \"A\" first (i.e.,\nthe delta is physically in the pack before its base, \"B\") and both are\nREF_DELTA. Right now we'd skip over A, knowing that we don't have B. And\nthen when we get to B, we'd correctly resolve A on top of it (and if we\nhave no such B, we'd eventually complain \"hey, there are still some\nunresolved deltas\").\n\nBut what happens if we _do_ have \"B\", but we just weren't able to tell\nthe sender for some reason (e.g., it's unreferenced). We'd add a new\ncopy of \"B\" to the pack while resolving \"A\", as part of --fix-thin. And\nthen when we resolve \"B\", we'd get _another_ copy of \"B\" in the pack,\nand our result would have a duplicate.\n\nI don't think this happens in practice because we'd generally use\nOFS_DELTA in the first place these days. And even for REF_DELTA, I think\nwe prefer to put bases before their deltas (i.e., we'd always see \"B\"\nbefore \"A\"). But I think if we ever _did_ see it (alternate\nimplementation? malicious packfile?) we'd generate duplicates. I _think_\nthat would then cause us to barf due to the duplicate check from\n68be2fea50 (receive-pack, fetch-pack: reject bogus pack that records\nobjects twice, 2011-11-16).\n\nAnd that's true today, even without Jonathan's on-demand fetching patch.\nSo I don't think that materially changes the requirements for\ncorrectness. It does mean that we might fetch (but not use!) a thin base\nwe don't need, but only if the sender uses REF_DELTA for non-thin\ndeltas, which we wouldn't normally do.\n\n-Peff\n\n[1] https://public-inbox.org/git/20190517043939.GA12063@sigill.intra.peff.net/\n"},{"id":"376626","messageId":"20190603222337.GA208159@google.com","threadId":"51095","inReplyTo":"4fcaa4481b5fd2a76aa21263f997e00913db0e0f.1557868134.git.jonathantanmy@google.com","subject":"Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2019-06-03T22:23:37Z","receivedAt":"2019-06-03T22:23:42Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jonathan Tan wrote:\n\n> When fetching, the client sends \"have\" commit IDs indicating that the\n> server does not need to send any object referenced by those commits,\n> reducing network I/O. When the client is a partial clone, the client\n> still sends \"have\"s in this way, even if it does not have every object\n> referenced by a commit it sent as \"have\".\n>\n> If a server omits such an object, it is fine: the client could lazily\n> fetch that object before this fetch, and it can still do so after.\n>\n> The issue is when the server sends a thin pack containing an object that\n> is a REF_DELTA against such a missing object: index-pack fails to fix\n> the thin pack. When support for lazily fetching missing objects was\n> added in 8b4c0103a9 (\"sha1_file: support lazily fetching missing\n> objects\", 2017-12-08), support in index-pack was turned off in the\n> belief that it accesses the repo only to do hash collision checks.\n> However, this is not true: it also needs to access the repo to resolve\n> REF_DELTA bases.\n[...]\n> Signed-off-by: Jonathan Tan \n> ---\n> builtin/index-pack.c | 26 +++++++++++++++--\n> t/t5616-partial-clone.sh | 61 ++++++++++++++++++++++++++++++++++++++++\n> 2 files changed, 85 insertions(+), 2 deletions(-)\n\nThanks much.\n\nThis bugfix has been working well at $DAYJOB:\nTested-by: Jonathan Nieder \n\nIs it something that could be in 2.22.0 or 2.22.1?\n"}]}