{"thread":{"id":"55737","subject":"[PATCH 0/8] Speed up connectivity checks via quarantine dir","startedAt":"2021-05-19T19:13:29Z","lastAt":"2021-05-27T14:38:49Z","messageCount":22,"participants":["Patrick Steinhardt","Elijah Newren","Chris Torek","Jeff King","Junio C Hamano","Ævar Arnfjörð Bjarmason","SZEDER Gábor","Felipe Contreras"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"424978","messageId":"cover.1621451532.git.ps@pks.im","threadId":"55737","inReplyTo":null,"subject":"[PATCH 0/8] Speed up connectivity checks via quarantine dir","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-05-19T19:13:18Z","receivedAt":"2021-05-19T19:13:29Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nWhile analyzing push performance on gitlab.com, I've been at times\nwondering what git-receive-pack(1) is doing for so long. For some repos\nwhich have loads of references (~880k), even tiny pushes of less than 10\nobjects took dozens of seconds to get accepted.\n\nOne of the issues I've found is the object connectivity check, which may\nrun for a significant amount of time. The root cause here is that we're\ncomputing connectivity via `git rev-list --not --all`: if we've got many\nrefs in the repository, computing `--not --all` is hugely expensive.\n\nThis commit series thus implements an alternative way of computing\nreachability, which reuses information from the object quarantine\nenvironment. Instead of doing a refwalk, we just look iterate over all\npacked and loose quarantined objects any for each of them, we determine\nwhether their immediate references are all satisfied.\n\nThis reimplementation is paying out quite well for repos which have many\nrefs. The following benchmarks for git-receive-pack(1) (added in patch\n2/8) have been performed in linux-stable.git:\n\nTest v2.32.0-rc0 HEAD\n--------------------------------------------------------------------------------------------\n5400.3: receive-pack clone create 1.27(1.11+0.16) 0.02(0.01+0.01) -98.4%\n5400.5: receive-pack clone update 1.27(1.13+0.13) 0.02(0.02+0.00) -98.4%\n5400.7: receive-pack clone reset 0.13(0.11+0.02) 0.02(0.01+0.01) -84.6%\n5400.9: receive-pack clone delete 0.02(0.01+0.01) 0.03(0.02+0.01) +50.0%\n5400.11: receive-pack extrarefs create 33.01(18.80+14.43) 9.00(4.30+4.65) -72.7%\n5400.13: receive-pack extrarefs update 33.13(18.85+14.50) 9.01(4.28+4.67) -72.8%\n5400.15: receive-pack extrarefs reset 32.90(18.82+14.32) 9.04(4.26+4.77) -72.5%\n5400.17: receive-pack extrarefs delete 9.13(4.35+4.77) 8.94(4.29+4.64) -2.1%\n5400.19: receive-pack empty create 223.35(640.63+127.74) 227.55(651.75+130.94) +1.9%\n\nThese rather clearly show that the previous rev-walk has been a major\nbottleneck in the implementation.\n\nPatrick\n\nPatrick Steinhardt (8):\n perf: fix when running with TEST_OUTPUT_DIRECTORY\n p5400: add perf tests for git-receive-pack(1)\n tmp-objdir: expose function to retrieve path\n packfile: have `for_each_file_in_pack_dir()` return error codes\n object-file: allow reading loose objects without reading their\n contents\n connected: implement connectivity check via temporary object dirs\n receive-pack: skip connectivity checks on delete-only commands\n receive-pack: check connectivity via quarantined objects\n\n builtin/receive-pack.c | 57 +++++++----\n connected.c | 192 +++++++++++++++++++++++++++++++++++\n connected.h | 19 ++++\n midx.c | 22 ++--\n object-file.c | 9 +-\n packfile.c | 26 +++--\n packfile.h | 10 +-\n t/perf/aggregate.perl | 8 +-\n t/perf/p5400-receive-pack.sh | 74 ++++++++++++++\n t/perf/perf-lib.sh | 4 +-\n t/perf/run | 25 +++--\n tmp-objdir.c | 7 ++\n tmp-objdir.h | 5 +\n 13 files changed, 401 insertions(+), 57 deletions(-)\n create mode 100755 t/perf/p5400-receive-pack.sh\n\n-- \n2.31.1\n\n"},{"id":"424979","messageId":"5488f0f4888fbc46378e2777d7daba1ec627b6c6.1621451532.git.ps@pks.im","threadId":"55737","inReplyTo":"cover.1621451532.git.ps@pks.im","subject":"[PATCH 1/8] perf: fix when running with TEST_OUTPUT_DIRECTORY","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-05-19T19:13:22Z","receivedAt":"2021-05-19T19:13:30Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When the TEST_OUTPUT_DIRECTORY is defined, then all test data will be\nwritten in that directory instead of the default directory located in\n\"t/\". While this works as expected for our normal tests, performance\ntests fail to locate and aggregate performance data because they don't\nknow to handle TEST_OUTPUT_DIRECTORY correctly and always look at the\ndefault location.\n\nFix the issue by adding a `--results-dir` parameter to \"aggregate.perl\"\nwhich identifies the directory where results are and by making the \"run\"\nscript awake of the TEST_OUTPUT_DIRECTORY variable.\n\nSigned-off-by: Patrick Steinhardt \n---\n t/perf/aggregate.perl | 8 ++++++--\n t/perf/perf-lib.sh | 4 ++--\n t/perf/run | 25 ++++++++++++++++---------\n 3 files changed, 24 insertions(+), 13 deletions(-)\n\ndiff --git a/t/perf/aggregate.perl b/t/perf/aggregate.perl\nindex 14e4cda287..5d4964c5c6 100755\n--- a/t/perf/aggregate.perl\n+++ b/t/perf/aggregate.perl\n@@ -58,6 +58,7 @@ sub usage {\n Options:\n --codespeed * Format output for Codespeed\n --reponame * Send given reponame to codespeed\n+ --results-dir * Directory where test results are located\n --sort-by * Sort output (only \"regression\" criteria is supported)\n --subsection * Use results from given subsection\n \n@@ -90,12 +91,13 @@ sub sane_backticks {\n }\n \n my (@dirs, %dirnames, %dirabbrevs, %prefixes, @tests,\n- $codespeed, $sortby, $subsection, $reponame);\n+ $codespeed, $sortby, $subsection, $reponame, $resultsdir);\n \n Getopt::Long::Configure qw/ require_order /;\n \n my $rc = GetOptions(\"codespeed\" => \\$codespeed,\n \t\t \"reponame=s\" => \\$reponame,\n+\t\t \"results-dir=s\" => \\$resultsdir,\n \t\t \"sort-by=s\" => \\$sortby,\n \t\t \"subsection=s\" => \\$subsection);\n usage() unless $rc;\n@@ -137,7 +139,9 @@ sub sane_backticks {\n \t@tests = glob \"p????-*.sh\";\n }\n \n-my $resultsdir = \"test-results\";\n+if (not $resultsdir) {\n+\t$resultsdir = \"test-results\";\n+}\n \n if (! $subsection and\n exists $ENV{GIT_PERF_SUBSECTION} and\ndiff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh\nindex 601d9f67dd..8ca6dd0297 100644\n--- a/t/perf/perf-lib.sh\n+++ b/t/perf/perf-lib.sh\n@@ -45,7 +45,7 @@ export TEST_DIRECTORY TRASH_DIRECTORY GIT_BUILD_DIR GIT_TEST_CMP\n MODERN_GIT=$GIT_BUILD_DIR/bin-wrappers/git\n export MODERN_GIT\n \n-perf_results_dir=$TEST_OUTPUT_DIRECTORY/test-results\n+perf_results_dir=$TEST_RESULTS_DIR\n test -n \"$GIT_PERF_SUBSECTION\" && perf_results_dir=\"$perf_results_dir/$GIT_PERF_SUBSECTION\"\n mkdir -p \"$perf_results_dir\"\n rm -f \"$perf_results_dir\"/$(basename \"$0\" .sh).subtests\n@@ -253,7 +253,7 @@ test_size () {\n # and does it after running everything)\n test_at_end_hook_ () {\n \tif test -z \"$GIT_PERF_AGGREGATING_LATER\"; then\n-\t\t( cd \"$TEST_DIRECTORY\"/perf && ./aggregate.perl $(basename \"$0\") )\n+\t\t( cd \"$TEST_DIRECTORY\"/perf && ./aggregate.perl --results-dir=\"$TEST_RESULTS_DIR\" $(basename \"$0\") )\n \tfi\n }\n \ndiff --git a/t/perf/run b/t/perf/run\nindex c7b86104e1..03128d440a 100755\n--- a/t/perf/run\n+++ b/t/perf/run\n@@ -188,10 +188,10 @@ run_subsection () {\n \n \tif test -z \"$GIT_PERF_SEND_TO_CODESPEED\"\n \tthen\n-\t\t./aggregate.perl $codespeed_opt \"$@\"\n+\t\t./aggregate.perl --results-dir=\"$TEST_RESULTS_DIR\" $codespeed_opt \"$@\"\n \telse\n-\t\tjson_res_file=\"test-results/$GIT_PERF_SUBSECTION/aggregate.json\"\n-\t\t./aggregate.perl --codespeed \"$@\" | tee \"$json_res_file\"\n+\t\tjson_res_file=\"\"$TEST_RESULTS_DIR\"/$GIT_PERF_SUBSECTION/aggregate.json\"\n+\t\t./aggregate.perl --results-dir=\"$TEST_RESULTS_DIR\" --codespeed \"$@\" | tee \"$json_res_file\"\n \t\tsend_data_url=\"$GIT_PERF_SEND_TO_CODESPEED/result/add/json/\"\n \t\tcurl -v --request POST --data-urlencode \"json=$(cat \"$json_res_file\")\" \"$send_data_url\"\n \tfi\n@@ -203,10 +203,17 @@ get_var_from_env_or_config \"GIT_PERF_SEND_TO_CODESPEED\" \"perf\" \"sendToCodespeed\"\n cd \"$(dirname $0)\"\n . ../../GIT-BUILD-OPTIONS\n \n-mkdir -p test-results\n-get_subsections \"perf\" >test-results/run_subsections.names\n+if test -n \"$TEST_OUTPUT_DIRECTORY\"\n+then\n+ TEST_RESULTS_DIR=\"$TEST_OUTPUT_DIRECTORY/test-results\"\n+else\n+ TEST_RESULTS_DIR=test-results\n+fi\n \n-if test $(wc -l \"$TEST_RESULTS_DIR\"/run_subsections.names\n+\n+if test $(wc -l <\"$TEST_RESULTS_DIR\"/run_subsections.names) -eq 0\n then\n \tif test -n \"$GIT_PERF_SUBSECTION\"\n \tthen\n@@ -222,10 +229,10 @@ then\n \t)\n elif test -n \"$GIT_PERF_SUBSECTION\"\n then\n-\tegrep \"^$GIT_PERF_SUBSECTION\\$\" test-results/run_subsections.names >/dev/null ||\n+\tegrep \"^$GIT_PERF_SUBSECTION\\$\" \"$TEST_RESULTS_DIR\"/run_subsections.names >/dev/null ||\n \t\tdie \"subsection '$GIT_PERF_SUBSECTION' not found in '$GIT_PERF_CONFIG_FILE'\"\n \n-\tegrep \"^$GIT_PERF_SUBSECTION\\$\" test-results/run_subsections.names | while read -r subsec\n+\tegrep \"^$GIT_PERF_SUBSECTION\\$\" \"$TEST_RESULTS_DIR\"/run_subsections.names | while read -r subsec\n \tdo\n \t\t(\n \t\t\tGIT_PERF_SUBSECTION=\"$subsec\"\n@@ -243,5 +250,5 @@ else\n \t\t\techo \"======== Run for subsection '$GIT_PERF_SUBSECTION' ========\"\n \t\t\trun_subsection \"$@\"\n \t\t)\n-\tdone \n---\n t/perf/p5400-receive-pack.sh | 74 ++++++++++++++++++++++++++++++++++++\n 1 file changed, 74 insertions(+)\n create mode 100755 t/perf/p5400-receive-pack.sh\n\ndiff --git a/t/perf/p5400-receive-pack.sh b/t/perf/p5400-receive-pack.sh\nnew file mode 100755\nindex 0000000000..2b0c89d977\n--- /dev/null\n+++ b/t/perf/p5400-receive-pack.sh\n@@ -0,0 +1,74 @@\n+#!/bin/sh\n+\n+test_description=\"Tests performance of receive-pack\"\n+\n+. ./perf-lib.sh\n+\n+test_perf_large_repo\n+\n+test_expect_success 'setup' '\n+\t# Create a main branch such that we do not have to rely on any specific\n+\t# branch to exist in the perf repository.\n+\tgit switch --force-create main &&\n+\n+\tTARGET_REPO_CLONE=$(pwd)/target-clone.git &&\n+\tgit clone --bare --dissociate --branch main \"$(pwd)\" \"$TARGET_REPO_CLONE\" &&\n+\tTARGET_REPO_REFS=$(pwd)/target-refs.git &&\n+\tgit clone --bare --dissociate --branch main \"$(pwd)\" \"$TARGET_REPO_REFS\" &&\n+\tTARGET_REPO_EMPTY=$(pwd)/target-empty.git &&\n+\tgit init --bare \"$TARGET_REPO_EMPTY\" &&\n+\n+\t# Set up a pre-receive hook such that no refs will ever be changed.\n+\t# This easily allows multiple perf runs, but still exercises\n+\t# server-side reference negotiation and checking for consistency.\n+\tmkdir hooks &&\n+\twrite_script hooks/pre-receive <<-EOF &&\n+\t\t#!/bin/sh\n+\t\techo \"failed in pre-receive hook\"\n+\t\texit 1\n+\tEOF\n+\tcat >config <<-EOF &&\n+\t\t[core]\n+\t\t\thooksPath=$(pwd)/hooks\n+\tEOF\n+\tGIT_CONFIG_GLOBAL=\"$(pwd)/config\" &&\n+\texport GIT_CONFIG_GLOBAL &&\n+\n+\t# Create a reference for each commit in the target repository with\n+\t# extra-refs. While this may be an atypical setup, biggish repositories\n+\t# easily end up with hundreds of thousands of refs, and this is a good\n+\t# enough approximation.\n+\tgit -C \"$TARGET_REPO_REFS\" log --all --format=\"tformat:create refs/commit/%h %H\" |\n+\t\tgit -C \"$TARGET_REPO_REFS\" update-ref --stdin &&\n+\n+\tgit switch --create updated &&\n+\ttest_commit --no-tag updated\n+'\n+\n+while read name repo\n+do\n+\trefs=(\"create updated:new\")\n+\n+\t# If the target repository is the empty one, then the only thing we can\n+\t# do is to create a new branch.\n+\tif test \"$repo\" != \"$TARGET_REPO_EMPTY\"\n+\tthen\n+\t\trefs+=(\"update updated:main\" \"reset main~:main\" \"delete :main\")\n+\tfi\n+\n+\twhile read desc ref\n+\tdo\n+\t\ttest_expect_success \"setup $name $desc\" \"\n+\t\t\ttest_must_fail git push --force '$repo' '$ref' \\\n+\t\t\t\t--receive-pack='tee pack | git receive-pack' 2>err &&\n+\t\t\tgrep 'failed in pre-receive hook' err\n+\t\t\"\n+\n+\t\ttest_perf \"receive-pack $name $desc\" \"\n+\t\t\tgit receive-pack '$repo' negotiation &&\n+\t\t\tgrep 'pre-receive hook declined' negotiation\n+\t\t\"\n+\tdone < <(printf \"%s\\n\" \"${refs[@]}\")\n+done < <(printf \"%s\\n\" \"clone $TARGET_REPO_CLONE\" \"extrarefs $TARGET_REPO_REFS\" \"empty $TARGET_REPO_EMPTY\")\n+\n+test_done\n-- \n2.31.1\n\n"},{"id":"424981","messageId":"a5ca94e3f4df2abb38880385310e5cb02d7b5daa.1621451532.git.ps@pks.im","threadId":"55737","inReplyTo":"cover.1621451532.git.ps@pks.im","subject":"[PATCH 3/8] tmp-objdir: expose function to retrieve path","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-05-19T19:13:31Z","receivedAt":"2021-05-19T19:13:40Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"It's currently impossible to tell the path of a temporary object\ndirectory for outside users of `struct tmp_objdir`. We'll soon need that\ninformation though so that we can reuse information from the quarantine\nenvironment in git-receive-pack(1).\n\nProvide a new function `tmp_objdir_path()` which returns the path of a\ntemporary object directory to prepare for this.\n\nSigned-off-by: Patrick Steinhardt \n---\n tmp-objdir.c | 7 +++++++\n tmp-objdir.h | 5 +++++\n 2 files changed, 12 insertions(+)\n\ndiff --git a/tmp-objdir.c b/tmp-objdir.c\nindex b8d880e362..6056917c63 100644\n--- a/tmp-objdir.c\n+++ b/tmp-objdir.c\n@@ -288,6 +288,13 @@ const char **tmp_objdir_env(const struct tmp_objdir *t)\n \treturn t->env.v;\n }\n \n+const char *tmp_objdir_path(const struct tmp_objdir *t)\n+{\n+\tif (!t)\n+\t\treturn NULL;\n+\treturn t->path.buf;\n+}\n+\n void tmp_objdir_add_as_alternate(const struct tmp_objdir *t)\n {\n \tadd_to_alternates_memory(t->path.buf);\ndiff --git a/tmp-objdir.h b/tmp-objdir.h\nindex b1e45b4c75..da3ccb98bc 100644\n--- a/tmp-objdir.h\n+++ b/tmp-objdir.h\n@@ -51,4 +51,9 @@ int tmp_objdir_destroy(struct tmp_objdir *);\n */\n void tmp_objdir_add_as_alternate(const struct tmp_objdir *);\n \n+/*\n+ * Return the path of the temporary object directory.\n+ */\n+const char *tmp_objdir_path(const struct tmp_objdir *t);\n+\n #endif /* TMP_OBJDIR_H */\n-- \n2.31.1\n\n"},{"id":"424982","messageId":"64a1bcf2c11d180542e06f67c451f9f90019dea4.1621451532.git.ps@pks.im","threadId":"55737","inReplyTo":"cover.1621451532.git.ps@pks.im","subject":"[PATCH 4/8] packfile: have `for_each_file_in_pack_dir()` return error codes","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-05-19T19:13:35Z","receivedAt":"2021-05-19T19:13:43Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The function `for_each_file_in_pack_dir()` doesn't ever return error\ncodes right now: any errors it hits are simply swallowed. A new user\nwe're about to add would like to know what's going on though such that\nit can decide whether the call was successful or not.\n\nRefactor the function to return an error code, and adapt the signature\nof the callback function to also return an error code. This enables the\ncallback to abort iteration and have its error code passed through.\nExisting callers are adapted to this change, but keep ignoring errors.\n\nSigned-off-by: Patrick Steinhardt \n---\n midx.c | 22 +++++++++++++---------\n packfile.c | 26 ++++++++++++++++----------\n packfile.h | 10 +++++-----\n 3 files changed, 34 insertions(+), 24 deletions(-)\n\ndiff --git a/midx.c b/midx.c\nindex 21d6a05e88..f87a3d36ab 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -470,15 +470,15 @@ struct write_midx_context {\n \tint preferred_pack_idx;\n };\n \n-static void add_pack_to_midx(const char *full_path, size_t full_path_len,\n-\t\t\t const char *file_name, void *data)\n+static int add_pack_to_midx(const char *full_path, size_t full_path_len,\n+\t\t\t const char *file_name, void *data)\n {\n \tstruct write_midx_context *ctx = data;\n \n \tif (ends_with(file_name, \".idx\")) {\n \t\tdisplay_progress(ctx->progress, ++ctx->pack_paths_checked);\n \t\tif (ctx->m && midx_contains_pack(ctx->m, file_name))\n-\t\t\treturn;\n+\t\t\treturn 0;\n \n \t\tALLOC_GROW(ctx->info, ctx->nr + 1, ctx->alloc);\n \n@@ -489,7 +489,7 @@ static void add_pack_to_midx(const char *full_path, size_t full_path_len,\n \t\tif (!ctx->info[ctx->nr].p) {\n \t\t\twarning(_(\"failed to add packfile '%s'\"),\n \t\t\t\tfull_path);\n-\t\t\treturn;\n+\t\t\treturn 0;\n \t\t}\n \n \t\tif (open_pack_index(ctx->info[ctx->nr].p)) {\n@@ -497,7 +497,7 @@ static void add_pack_to_midx(const char *full_path, size_t full_path_len,\n \t\t\t\tfull_path);\n \t\t\tclose_pack(ctx->info[ctx->nr].p);\n \t\t\tFREE_AND_NULL(ctx->info[ctx->nr].p);\n-\t\t\treturn;\n+\t\t\treturn 0;\n \t\t}\n \n \t\tctx->info[ctx->nr].pack_name = xstrdup(file_name);\n@@ -505,6 +505,8 @@ static void add_pack_to_midx(const char *full_path, size_t full_path_len,\n \t\tctx->info[ctx->nr].expired = 0;\n \t\tctx->nr++;\n \t}\n+\n+\treturn 0;\n }\n \n struct pack_midx_entry {\n@@ -1110,19 +1112,21 @@ struct clear_midx_data {\n \tconst char *ext;\n };\n \n-static void clear_midx_file_ext(const char *full_path, size_t full_path_len,\n-\t\t\t\tconst char *file_name, void *_data)\n+static int clear_midx_file_ext(const char *full_path, size_t full_path_len,\n+\t\t\tconst char *file_name, void *_data)\n {\n \tstruct clear_midx_data *data = _data;\n \n \tif (!(starts_with(file_name, \"multi-pack-index-\") &&\n \t ends_with(file_name, data->ext)))\n-\t\treturn;\n+\t\treturn 0;\n \tif (data->keep && !strcmp(data->keep, file_name))\n-\t\treturn;\n+\t\treturn 0;\n \n \tif (unlink(full_path))\n \t\tdie_errno(_(\"failed to remove %s\"), full_path);\n+\n+\treturn 0;\n }\n \n static void clear_midx_files_ext(struct repository *r, const char *ext,\ndiff --git a/packfile.c b/packfile.c\nindex b79cbc8cd4..f488a214cf 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -792,14 +792,15 @@ static void report_pack_garbage(struct string_list *list)\n \treport_helper(list, seen_bits, first, list->nr);\n }\n \n-void for_each_file_in_pack_dir(const char *objdir,\n-\t\t\t each_file_in_pack_dir_fn fn,\n-\t\t\t void *data)\n+int for_each_file_in_pack_dir(const char *objdir,\n+\t\t\t each_file_in_pack_dir_fn fn,\n+\t\t\t void *data)\n {\n \tstruct strbuf path = STRBUF_INIT;\n \tsize_t dirnamelen;\n \tDIR *dir;\n \tstruct dirent *de;\n+\tint ret = 0;\n \n \tstrbuf_addstr(&path, objdir);\n \tstrbuf_addstr(&path, \"/pack\");\n@@ -809,7 +810,7 @@ void for_each_file_in_pack_dir(const char *objdir,\n \t\t\terror_errno(\"unable to open object pack directory: %s\",\n \t\t\t\t path.buf);\n \t\tstrbuf_release(&path);\n-\t\treturn;\n+\t\treturn -1;\n \t}\n \tstrbuf_addch(&path, '/');\n \tdirnamelen = path.len;\n@@ -820,11 +821,14 @@ void for_each_file_in_pack_dir(const char *objdir,\n \t\tstrbuf_setlen(&path, dirnamelen);\n \t\tstrbuf_addstr(&path, de->d_name);\n \n-\t\tfn(path.buf, path.len, de->d_name, data);\n+\t\tret = fn(path.buf, path.len, de->d_name, data);\n+\t\tif (ret)\n+\t\t\tbreak;\n \t}\n \n \tclosedir(dir);\n \tstrbuf_release(&path);\n+\treturn ret;\n }\n \n struct prepare_pack_data {\n@@ -834,8 +838,8 @@ struct prepare_pack_data {\n \tstruct multi_pack_index *m;\n };\n \n-static void prepare_pack(const char *full_name, size_t full_name_len,\n-\t\t\t const char *file_name, void *_data)\n+static int prepare_pack(const char *full_name, size_t full_name_len,\n+\t\t\tconst char *file_name, void *_data)\n {\n \tstruct prepare_pack_data *data = (struct prepare_pack_data *)_data;\n \tstruct packed_git *p;\n@@ -858,13 +862,13 @@ static void prepare_pack(const char *full_name, size_t full_name_len,\n \t}\n \n \tif (!report_garbage)\n-\t\treturn;\n+\t\treturn 0;\n \n \tif (!strcmp(file_name, \"multi-pack-index\"))\n-\t\treturn;\n+\t\treturn 0;\n \tif (starts_with(file_name, \"multi-pack-index\") &&\n \t ends_with(file_name, \".rev\"))\n-\t\treturn;\n+\t\treturn 0;\n \tif (ends_with(file_name, \".idx\") ||\n \t ends_with(file_name, \".rev\") ||\n \t ends_with(file_name, \".pack\") ||\n@@ -874,6 +878,8 @@ static void prepare_pack(const char *full_name, size_t full_name_len,\n \t\tstring_list_append(data->garbage, full_name);\n \telse\n \t\treport_garbage(PACKDIR_FILE_GARBAGE, full_name);\n+\n+\treturn 0;\n }\n \n static void prepare_packed_git_one(struct repository *r, char *objdir, int local)\ndiff --git a/packfile.h b/packfile.h\nindex 3ae117a8ae..eac930cd27 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -39,11 +39,11 @@ const char *pack_basename(struct packed_git *p);\n \n struct packed_git *parse_pack_index(unsigned char *sha1, const char *idx_path);\n \n-typedef void each_file_in_pack_dir_fn(const char *full_path, size_t full_path_len,\n-\t\t\t\t const char *file_pach, void *data);\n-void for_each_file_in_pack_dir(const char *objdir,\n-\t\t\t each_file_in_pack_dir_fn fn,\n-\t\t\t void *data);\n+typedef int each_file_in_pack_dir_fn(const char *full_path, size_t full_path_len,\n+\t\t\t\t const char *file_pach, void *data);\n+int for_each_file_in_pack_dir(const char *objdir,\n+\t\t\t each_file_in_pack_dir_fn fn,\n+\t\t\t void *data);\n \n /* A hook to report invalid files in pack directory */\n #define PACKDIR_FILE_PACK 1\n-- \n2.31.1\n\n"},{"id":"424983","messageId":"e26ff58e926dfc6aec15794a68981d6e455cb305.1621451532.git.ps@pks.im","threadId":"55737","inReplyTo":"cover.1621451532.git.ps@pks.im","subject":"[PATCH 5/8] object-file: allow reading loose objects without reading their contents","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-05-19T19:13:39Z","receivedAt":"2021-05-19T19:13:44Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We're about to add a new implementation of the connectivity check via\nthe object quarantine directory, which will directly iterate over any\nloose object via their paths. For optimization purposes, we'll want to\nskip over any loose blobs, but right now there's no easy way to read a\nloose object without also slurping in all its contents.\n\nFix this shortcoming by modifying `read_loose_object()` such that it can\nhandle the case where no pointer for `contents` was passed in. If so,\nthen we'll simply skip reading the loose object.\n\nSigned-off-by: Patrick Steinhardt \n---\n object-file.c | 9 ++++++++-\n 1 file changed, 8 insertions(+), 1 deletion(-)\n\ndiff --git a/object-file.c b/object-file.c\nindex 884855b9df..ab695823fd 100644\n--- a/object-file.c\n+++ b/object-file.c\n@@ -2552,7 +2552,8 @@ int read_loose_object(const char *path,\n \tgit_zstream stream;\n \tchar hdr[MAX_HEADER_LEN];\n \n-\t*contents = NULL;\n+\tif (contents)\n+\t\t*contents = NULL;\n \n \tmap = map_loose_object_1(the_repository, path, NULL, &mapsize);\n \tif (!map) {\n@@ -2572,6 +2573,12 @@ int read_loose_object(const char *path,\n \t\tgoto out;\n \t}\n \n+\tif (!contents) {\n+\t\tgit_inflate_end(&stream);\n+\t\tret = 0;\n+\t\tgoto out;\n+\t}\n+\n \tif (*type == OBJ_BLOB && *size > big_file_threshold) {\n \t\tif (check_stream_oid(&stream, hdr, *size, path, expected_oid) < 0)\n \t\t\tgoto out;\n-- \n2.31.1\n\n"},{"id":"424984","messageId":"d01685a3ec82c3415654779c122927388fc433db.1621451532.git.ps@pks.im","threadId":"55737","inReplyTo":"cover.1621451532.git.ps@pks.im","subject":"[PATCH 6/8] connected: implement connectivity check via temporary object dirs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-05-19T19:13:43Z","receivedAt":"2021-05-19T19:13:49Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The connectivity checks are currently implemented via git-rev-list(1):\nwe simply ignore any preexisting refs via `--not --all`, and pass all\nnew refs which are to be checked via its stdin. While this works well\nenough for repositories which do not have a lot of references, it's\nclear that `--not --all` will linearly scale with the number of refs\nwhich do exist: for each reference, we'll walk through its commit as\nwell as its five parent commits (defined via `SLOP`). Given that many\nmajor hosting sites which use a pull/merge request workflow keep refs to\nthe request's HEAD, this effectively means that `--not --all` will do a\nnearly complete graph walk.\n\nWe can compute the set of pushed objects much more easily though. We\nknow exactly which objects were just received, which is the set of\nobjects which are in git-receive-pack(1)'s object quarantine directory.\nWhile this may overshoot new objects because the client may have sent\nobjects which we already know, it lets us avoid doing a graph walk of\npreexisting commits.\n\nThe implementation of this is quite simple: we iterate through all loose\nand packed objects in the object directory, and for each object we check\nwhether its immediate referenced objects exist. There is no need to do a\nwalk beyond these direct links: if the receiving repository already has\nthe directly referenced object, then it's not a new object in the first\nplace and thus does not need a re-check. If the referenced object is a\nnew one and we can load it, then we know that it will eventually be\nchecked via the quarantined objects walk, too.\n\nFinally, after we have concluded that all quarantined objects are indeed\nfully connected, the only thing left to check is whether all reference\nupdates reference an existing object.\n\nThis new connectivity check will be wired up in a subsequent commit.\n\nSigned-off-by: Patrick Steinhardt \n---\n connected.c | 192 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n connected.h | 19 ++++++\n 2 files changed, 211 insertions(+)\n\ndiff --git a/connected.c b/connected.c\nindex b18299fdf0..ab0eb9f974 100644\n--- a/connected.c\n+++ b/connected.c\n@@ -6,6 +6,13 @@\n #include \"transport.h\"\n #include \"packfile.h\"\n #include \"promisor-remote.h\"\n+#include \"object.h\"\n+#include \"tree-walk.h\"\n+#include \"commit.h\"\n+#include \"tag.h\"\n+#include \"progress.h\"\n+#include \"tmp-objdir.h\"\n+#include \"oidset.h\"\n \n /*\n * If we feed all the commits we want to verify to this command\n@@ -151,3 +158,188 @@ int check_connected(oid_iterate_fn fn, void *cb_data,\n \tsigchain_pop(SIGPIPE);\n \treturn finish_command(&rev_list) || err;\n }\n+\n+struct connected_payload {\n+\tstruct repository *repo;\n+\tstruct progress *progress;\n+\tstruct oidset seen;\n+\tsize_t checked_objects;\n+\tsize_t missing_objects;\n+};\n+\n+static void check_missing(struct connected_payload *payload, const struct object_id *oid)\n+{\n+\tif (oidset_contains(&payload->seen, oid))\n+\t\treturn;\n+\tif (oid_object_info(payload->repo, oid, NULL) <= 0)\n+\t\tpayload->missing_objects++;\n+\toidset_insert(&payload->seen, oid);\n+\tdisplay_progress(payload->progress, ++payload->checked_objects);\n+}\n+\n+static int check_quarantined_object(const struct object_id *oid, enum object_type type,\n+\t\t\t\t void *content, unsigned long size, void *data)\n+{\n+\tstruct connected_payload *payload = data;\n+\tstruct object *object;\n+\tint eaten;\n+\n+\tobject = parse_object_buffer(payload->repo, oid, type, size, content, &eaten);\n+\tif (!object) {\n+\t\tif (!eaten)\n+\t\t\tfree(content);\n+\t\terror(_(\"could not parse quarantined object %s\"), oid_to_hex(oid));\n+\t\treturn -1;\n+\t}\n+\tif (!eaten)\n+\t\tfree(content);\n+\n+\tif (type == OBJ_TREE) {\n+\t\tstruct tree *tree = (struct tree *)object;\n+\t\tstruct tree_desc tree_desc;\n+\t\tstruct name_entry entry;\n+\n+\t\tif (init_tree_desc_gently(&tree_desc, tree->buffer, tree->size))\n+\t\t\treturn -1;\n+\t\twhile (tree_entry_gently(&tree_desc, &entry))\n+\t\t\tcheck_missing(payload, &entry.oid);\n+\n+\t\tfree_tree_buffer(tree);\n+\t} else if (type == OBJ_COMMIT) {\n+\t\tstruct commit *commit = (struct commit *) object;\n+\t\tstruct commit_list *parents;\n+\n+\t\tcheck_missing(payload, get_commit_tree_oid(commit));\n+\t\tfor (parents = commit->parents; parents; parents = parents->next)\n+\t\t\tcheck_missing(payload, &parents->item->object.oid);\n+\t} else if (type == OBJ_TAG) {\n+\t\tcheck_missing(payload, get_tagged_oid((struct tag *) object));\n+\t} else {\n+\t\terror(_(\"unexpected object type\"));\n+\t\treturn -1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int loose_object_iterator(const struct object_id *oid,\n+\t\t\t\t const char *path, void *_data)\n+{\n+\tstruct connected_payload *payload = _data;\n+\tenum object_type type;\n+\tunsigned long size;\n+\tvoid *content;\n+\n+\tif (read_loose_object(path, oid, &type, &size, NULL) < 0)\n+\t\treturn -1;\n+\n+\toidset_insert(&payload->seen, oid);\n+\tdisplay_progress(payload->progress, ++payload->checked_objects);\n+\n+\tif (type == OBJ_BLOB)\n+\t\treturn 0;\n+\tif (read_loose_object(path, oid, &type, &size, &content) < 0)\n+\t\treturn -1;\n+\n+\treturn check_quarantined_object(oid, type, content, size, payload);\n+}\n+\n+static int packed_object_iterator(const struct object_id *oid,\n+\t\t\t\t struct packed_git *pack, uint32_t pos,\n+\t\t\t\t void *_data)\n+{\n+\toff_t off = nth_packed_object_offset(pack, pos);\n+\tstruct connected_payload *payload = _data;\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n+\tenum object_type type;\n+\tunsigned long size;\n+\tvoid *content;\n+\n+\toi.typep = &type;\n+\tif (packed_object_info(payload->repo, pack, off, &oi) < 0)\n+\t\treturn -1;\n+\n+\toidset_insert(&payload->seen, oid);\n+\tdisplay_progress(payload->progress, ++payload->checked_objects);\n+\n+\tif (type == OBJ_BLOB)\n+\t\treturn 0;\n+\n+\toi.contentp = &content;\n+\toi.sizep = &size;\n+\n+\tif (packed_object_info(payload->repo, pack, off, &oi) < 0)\n+\t\treturn -1;\n+\n+\treturn check_quarantined_object(oid, type, content, size, payload);\n+}\n+\n+static int pack_dir_iterator(const char *full_path, size_t full_path_len,\n+\t\t\t const char *file_path, void *data)\n+{\n+\tif (ends_with(full_path, \".idx\")) {\n+\t\tstruct packed_git *pack = add_packed_git(full_path, full_path_len, 1);\n+\t\tif (!pack) {\n+\t\t\terror(_(\"unable to add quarantined pack\"));\n+\t\t\treturn -1;\n+\t\t}\n+\n+\t\tif (for_each_object_in_pack(pack, packed_object_iterator, data,\n+\t\t\t\t\t FOR_EACH_OBJECT_PACK_ORDER) < 0) {\n+\t\t\terror(_(\"unable to iterate packed objects\"));\n+\t\t\treturn -1;\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\n+\n+int check_connected_quarantine(struct repository *repo,\n+\t\t\t struct tmp_objdir *quarantine,\n+\t\t\t oid_iterate_fn fn, void *cb_data)\n+{\n+\tstruct connected_payload payload = {\n+\t\t.repo = repo,\n+\t\t.seen = OIDSET_INIT,\n+\t};\n+\tstruct object_id oid;\n+\tint ret;\n+\n+\tpayload.progress = start_delayed_progress(\"Checking connectivity\", 0);\n+\n+\t/*\n+\t * Iterate through all loose and packed objects part of the object\n+\t * quarantine and verify that for each of them, all directly referenced\n+\t * objects exist.\n+\t */\n+\tif (for_each_loose_file_in_objdir(tmp_objdir_path(quarantine),\n+\t\t\t\t\t loose_object_iterator, NULL,\n+\t\t\t\t\t NULL, &payload) < 0) {\n+\t\terror(_(\"unable to check quarantined loose objects\"));\n+\t\tret = -1;\n+\t\tgoto out;\n+\t}\n+\n+\tif (for_each_file_in_pack_dir(tmp_objdir_path(quarantine),\n+\t\t\t\t pack_dir_iterator, &payload) < 0) {\n+\t\terror(_(\"unable to check quarantined packed objects\"));\n+\t\tret = -1;\n+\t\tgoto out;\n+\t}\n+\n+\t/*\n+\t * After we've verified that all quarantined objects are indeed\n+\t * connected, we need to verify that all new tips are contained in the\n+\t * repository, too.\n+\t */\n+\twhile (!fn(cb_data, &oid)) {\n+\t\tif (oid_object_info(repo, &oid, NULL) <= 0)\n+\t\t\tpayload.missing_objects++;\n+\t\tdisplay_progress(payload.progress, ++payload.checked_objects);\n+\t}\n+\n+out:\n+\tstop_progress(&payload.progress);\n+\toidset_clear(&payload.seen);\n+\treturn ret || payload.missing_objects != 0;\n+}\ndiff --git a/connected.h b/connected.h\nindex 8d5a6b3ad6..336b6f362e 100644\n--- a/connected.h\n+++ b/connected.h\n@@ -3,6 +3,7 @@\n \n struct object_id;\n struct transport;\n+struct tmp_objdir;\n \n /*\n * Take callback data, and return next object name in the buffer.\n@@ -62,4 +63,22 @@ struct check_connected_options {\n int check_connected(oid_iterate_fn fn, void *cb_data,\n \t\t struct check_connected_options *opt);\n \n+/*\n+ * Make sure that all objects in the given quarantine directory are connected\n+ * and that all OIDs returned by the given callback are backed by an existing\n+ * object. The quarantine directory must have been made available to the\n+ * repository via `add_to_alternates_memory()`.\n+ *\n+ * Given that objects are enumerated via the quarantine directory directly,\n+ * this check should in general be more efficient than `check_connected()`\n+ * while being more pedantic at the same time (e.g. quarantined objects which\n+ * aren't referenced by anything but which do have missing links would get\n+ * rejected).\n+ *\n+ * Return 0 if Ok, non zero otherwise (i.e. some missing objects)\n+ */\n+int check_connected_quarantine(struct repository *repo,\n+\t\t\t struct tmp_objdir *quarantine,\n+\t\t\t oid_iterate_fn fn, void *cb_data);\n+\n #endif /* CONNECTED_H */\n-- \n2.31.1\n\n"},{"id":"424985","messageId":"68c60aff0c77c562aba5613ccbb9ab33ad8e0e08.1621451532.git.ps@pks.im","threadId":"55737","inReplyTo":"cover.1621451532.git.ps@pks.im","subject":"[PATCH 7/8] receive-pack: skip connectivity checks on delete-only commands","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-05-19T19:13:47Z","receivedAt":"2021-05-19T19:13:50Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In the case where git-receive-pack(1) receives only commands which\ndelete references, then per technical specification the client MUST NOT\nsend a packfile. As a result, we know that no new objects have been\nreceived, which makes it a moot point to check whether all received\nobjects are fully connected.\n\nFix this by not doing a connectivity check in case there were no pushed\nobjects. Given that git-rev-walk(1) with only negative references will\nnot do any graph walk, no performance improvements are to be expected.\nConceptionally, it is still the right thing to do though.\n\nThe following tests were executed on linux.git and back up above\nexpectation:\n\nTest v2.32.0-rc0 HEAD\n--------------------------------------------------------------------------------------------\n5400.3: receive-pack clone create 1.27(1.11+0.16) 1.26(1.12+0.14) -0.8%\n5400.5: receive-pack clone update 1.27(1.13+0.13) 1.27(1.11+0.16) +0.0%\n5400.7: receive-pack clone reset 0.13(0.11+0.02) 0.14(0.11+0.02) +7.7%\n5400.9: receive-pack clone delete 0.02(0.01+0.01) 0.02(0.00+0.01) +0.0%\n5400.11: receive-pack extrarefs create 33.01(18.80+14.43) 32.63(18.52+14.24) -1.2%\n5400.13: receive-pack extrarefs update 33.13(18.85+14.50) 32.82(18.85+14.29) -0.9%\n5400.15: receive-pack extrarefs reset 32.90(18.82+14.32) 32.70(18.76+14.20) -0.6%\n5400.17: receive-pack extrarefs delete 9.13(4.35+4.77) 8.99(4.28+4.70) -1.5%\n5400.19: receive-pack empty create 223.35(640.63+127.74) 226.96(655.16+131.93) +1.6%\n\nSigned-off-by: Patrick Steinhardt \n---\n builtin/receive-pack.c | 49 ++++++++++++++++++++++++++----------------\n 1 file changed, 30 insertions(+), 19 deletions(-)\n\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex a34742513a..b9263cec15 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -1918,11 +1918,8 @@ static void execute_commands(struct command *commands,\n \t\t\t struct shallow_info *si,\n \t\t\t const struct string_list *push_options)\n {\n-\tstruct check_connected_options opt = CHECK_CONNECTED_INIT;\n \tstruct command *cmd;\n \tstruct iterate_data data;\n-\tstruct async muxer;\n-\tint err_fd = 0;\n \tint run_proc_receive = 0;\n \n \tif (unpacker_error) {\n@@ -1931,25 +1928,39 @@ static void execute_commands(struct command *commands,\n \t\treturn;\n \t}\n \n-\tif (use_sideband) {\n-\t\tmemset(&muxer, 0, sizeof(muxer));\n-\t\tmuxer.proc = copy_to_sideband;\n-\t\tmuxer.in = -1;\n-\t\tif (!start_async(&muxer))\n-\t\t\terr_fd = muxer.in;\n-\t\t/* ...else, continue without relaying sideband */\n-\t}\n-\n \tdata.cmds = commands;\n \tdata.si = si;\n-\topt.err_fd = err_fd;\n-\topt.progress = err_fd && !quiet;\n-\topt.env = tmp_objdir_env(tmp_objdir);\n-\tif (check_connected(iterate_receive_command_list, &data, &opt))\n-\t\tset_connectivity_errors(commands, si);\n \n-\tif (use_sideband)\n-\t\tfinish_async(&muxer);\n+\t/*\n+\t * If received commands only consist of deletions, then the client MUST\n+\t * NOT send a packfile because there cannot be any new objects in the\n+\t * first place. As a result, we do not set up a quarantine environment\n+\t * because we know no new objects will be received. And that in turn\n+\t * means that we can skip connectivity checks here.\n+\t */\n+\tif (tmp_objdir) {\n+\t\tstruct check_connected_options opt = CHECK_CONNECTED_INIT;\n+\t\tstruct async muxer;\n+\t\tint err_fd = 0;\n+\n+\t\tif (use_sideband) {\n+\t\t\tmemset(&muxer, 0, sizeof(muxer));\n+\t\t\tmuxer.proc = copy_to_sideband;\n+\t\t\tmuxer.in = -1;\n+\t\t\tif (!start_async(&muxer))\n+\t\t\t\terr_fd = muxer.in;\n+\t\t\t/* ...else, continue without relaying sideband */\n+\t\t}\n+\n+\t\topt.err_fd = err_fd;\n+\t\topt.progress = err_fd && !quiet;\n+\t\topt.env = tmp_objdir_env(tmp_objdir);\n+\t\tif (check_connected(iterate_receive_command_list, &data, &opt))\n+\t\t\tset_connectivity_errors(commands, si);\n+\n+\t\tif (use_sideband)\n+\t\t\tfinish_async(&muxer);\n+\t}\n \n \treject_updates_to_hidden(commands);\n \n-- \n2.31.1\n\n"},{"id":"424986","messageId":"010974639c66c8f15d4dc9e4feb69eed92b52d13.1621451532.git.ps@pks.im","threadId":"55737","inReplyTo":"cover.1621451532.git.ps@pks.im","subject":"[PATCH 8/8] receive-pack: check connectivity via quarantined objects","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-05-19T19:13:51Z","receivedAt":"2021-05-19T19:13:56Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Convert git-receive-pack(1) to use the new connectivity check which\nuses the quarantine directory to enumerate new objects instead of using\nreferences. This change significantly decreases the time required to\naccept reference updates due to the fact that we don't need to do a\ngraph walk anymore. The following measurements have been executed on\nlinux.git:\n\nTest v2.32.0-rc0 HEAD\n--------------------------------------------------------------------------------------------\n5400.3: receive-pack clone create 1.27(1.11+0.16) 0.02(0.01+0.01) -98.4%\n5400.5: receive-pack clone update 1.27(1.13+0.13) 0.02(0.02+0.00) -98.4%\n5400.7: receive-pack clone reset 0.13(0.11+0.02) 0.02(0.01+0.01) -84.6%\n5400.9: receive-pack clone delete 0.02(0.01+0.01) 0.03(0.02+0.01) +50.0%\n5400.11: receive-pack extrarefs create 33.01(18.80+14.43) 9.00(4.30+4.65) -72.7%\n5400.13: receive-pack extrarefs update 33.13(18.85+14.50) 9.01(4.28+4.67) -72.8%\n5400.15: receive-pack extrarefs reset 32.90(18.82+14.32) 9.04(4.26+4.77) -72.5%\n5400.17: receive-pack extrarefs delete 9.13(4.35+4.77) 8.94(4.29+4.64) -2.1%\n5400.19: receive-pack empty create 223.35(640.63+127.74) 227.55(651.75+130.94) +1.9%\n\nInterestingly enough, the normal \"clone\" repository shows a more extreme\nimprovement compared to the \"extrarefs\" repository, which has one\nreference per commit. While I haven't yet dived into the root cause, I\nexpect that there is another location besides the connectivity check\nwhich does scale with the number of references.\n\nNotably, the connectivity check when pushing into an empty repository\nshows comparable performance with the previous implementation. This is\nbecause in both cases we're actually performing a complete graph walk to\ndetermine whether there are any unreachable commits.\n\nSigned-off-by: Patrick Steinhardt \n---\n builtin/receive-pack.c | 10 +++++++++-\n 1 file changed, 9 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex b9263cec15..23087acad0 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -1937,8 +1937,12 @@ static void execute_commands(struct command *commands,\n \t * first place. As a result, we do not set up a quarantine environment\n \t * because we know no new objects will be received. And that in turn\n \t * means that we can skip connectivity checks here.\n+\t *\n+\t * Using the quarantine directory to determine connectivity may not\n+\t * work with shallow clones, so let's let's play it safe for now and\n+\t * fall back to the old connectivity check.\n \t */\n-\tif (tmp_objdir) {\n+\tif (tmp_objdir && (si->nr_ours || si->nr_theirs)) {\n \t\tstruct check_connected_options opt = CHECK_CONNECTED_INIT;\n \t\tstruct async muxer;\n \t\tint err_fd = 0;\n@@ -1960,6 +1964,10 @@ static void execute_commands(struct command *commands,\n \n \t\tif (use_sideband)\n \t\t\tfinish_async(&muxer);\n+\t} else if (tmp_objdir) {\n+\t\tif (check_connected_quarantine(the_repository, tmp_objdir,\n+\t\t\t\t\t iterate_receive_command_list, &data))\n+\t\t\tset_connectivity_errors(commands, si);\n \t}\n \n \treject_updates_to_hidden(commands);\n-- \n2.31.1\n\n"},{"id":"425006","messageId":"CABPp-BGXH1oSVn9jS-CC2P0snUzgo5CN=nPbXtWrOm0Ugjz1Hg@mail.gmail.com","threadId":"55737","inReplyTo":"a5ca94e3f4df2abb38880385310e5cb02d7b5daa.1621451532.git.ps@pks.im","subject":"Re: [PATCH 3/8] tmp-objdir: expose function to retrieve path","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-05-20T00:16:58Z","receivedAt":"2021-05-20T00:17:12Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, May 19, 2021 at 1:22 PM Patrick Steinhardt wrote:\n>\n> It's currently impossible to tell the path of a temporary object\n> directory for outside users of `struct tmp_objdir`. We'll soon need that\n> information though so that we can reuse information from the quarantine\n> environment in git-receive-pack(1).\n>\n> Provide a new function `tmp_objdir_path()` which returns the path of a\n> temporary object directory to prepare for this.\n\nOh, sweet, someone else wants this too. I have a local patch\nintroducing the same function, which I needed for --remerge-diff. I\nhadn't submitted the patch yet, and if yours is accepted then I won't\nneed to. :-)\n\n> Signed-off-by: Patrick Steinhardt \n> ---\n> tmp-objdir.c | 7 +++++++\n> tmp-objdir.h | 5 +++++\n> 2 files changed, 12 insertions(+)\n>\n> diff --git a/tmp-objdir.c b/tmp-objdir.c\n> index b8d880e362..6056917c63 100644\n> --- a/tmp-objdir.c\n> +++ b/tmp-objdir.c\n> @@ -288,6 +288,13 @@ const char **tmp_objdir_env(const struct tmp_objdir *t)\n> return t->env.v;\n> }\n>\n> +const char *tmp_objdir_path(const struct tmp_objdir *t)\n> +{\n> + if (!t)\n> + return NULL;\n> + return t->path.buf;\n> +}\n> +\n> void tmp_objdir_add_as_alternate(const struct tmp_objdir *t)\n> {\n> add_to_alternates_memory(t->path.buf);\n> diff --git a/tmp-objdir.h b/tmp-objdir.h\n> index b1e45b4c75..da3ccb98bc 100644\n> --- a/tmp-objdir.h\n> +++ b/tmp-objdir.h\n> @@ -51,4 +51,9 @@ int tmp_objdir_destroy(struct tmp_objdir *);\n> */\n> void tmp_objdir_add_as_alternate(const struct tmp_objdir *);\n>\n> +/*\n> + * Return the path of the temporary object directory.\n> + */\n> +const char *tmp_objdir_path(const struct tmp_objdir *t);\n> +\n> #endif /* TMP_OBJDIR_H */\n> --\n> 2.31.1\n\nLooks good to me.\n"},{"id":"425015","messageId":"CAPx1GvfggYr2nddcsTdD2JdtgEN9aoNF-aWQo-RQQh5-TowGdg@mail.gmail.com","threadId":"55737","inReplyTo":"5488f0f4888fbc46378e2777d7daba1ec627b6c6.1621451532.git.ps@pks.im","subject":"Re: [PATCH 1/8] perf: fix when running with TEST_OUTPUT_DIRECTORY","fromName":"Chris Torek","fromEmail":"chris.torek@gmail.com","sentAt":"2021-05-20T02:03:08Z","receivedAt":"2021-05-20T02:03:22Z","isPatch":true,"sender":{"key":"chris.torek@gmail.com","avatar":"https://avatars.githubusercontent.com/u/16826774?v=4"},"body":"On Wed, May 19, 2021 at 1:21 PM Patrick Steinhardt wrote:\n> When the TEST_OUTPUT_DIRECTORY is defined, then all test data will be\n> written in that directory instead of the default directory located in\n> \"t/\". While this works as expected for our normal tests, performance\n> tests fail to locate and aggregate performance data because they don't\n> know to handle TEST_OUTPUT_DIRECTORY correctly and always look at the\n> default location.\n>\n> Fix the issue by adding a `--results-dir` parameter to \"aggregate.perl\"\n> which identifies the directory where results are and by making the \"run\"\n> script awake of the TEST_OUTPUT_DIRECTORY variable.\n\nTrivial typo: s/awake/aware/\n\n(The perl code looks OK to me but I'm no Perl programmer)\n\n>+if test -n \"$TEST_OUTPUT_DIRECTORY\"\n>+then\n>+ TEST_RESULTS_DIR=\"$TEST_OUTPUT_DIRECTORY/test-results\"\n>+else\n>+ TEST_RESULTS_DIR=test-results\n>+fi\n\nOptional shorter (one-liner) replacement:\n\nTEST_RESULTS_DIR=${TEST_OUTPUT_DIRECTORY:+$TEST_OUTPUT_DIRECTORY/}test-results\n\nChris\n"},{"id":"425016","messageId":"CAPx1GveeUi1s6LKTkUYS7CqkyZ9mm=6AQg4Ta8VHi1mnT19gEg@mail.gmail.com","threadId":"55737","inReplyTo":"f248b41d6e2df2d34a4304e2655df8cb094483e9.1621451532.git.ps@pks.im","subject":"Re: [PATCH 2/8] p5400: add perf tests for git-receive-pack(1)","fromName":"Chris Torek","fromEmail":"chris.torek@gmail.com","sentAt":"2021-05-20T02:09:46Z","receivedAt":"2021-05-20T02:10:01Z","isPatch":true,"sender":{"key":"chris.torek@gmail.com","avatar":"https://avatars.githubusercontent.com/u/16826774?v=4"},"body":"On Wed, May 19, 2021 at 1:22 PM Patrick Steinhardt wrote:\n> We'll the connectivity check logic for git-receive-pack(1) in the\n\ns/the conn/do the conn/\n\n> diff --git a/t/perf/p5400-receive-pack.sh b/t/perf/p5400-receive-pack.sh\n> new file mode 100755\n> index 0000000000..2b0c89d977\n> --- /dev/null\n> +++ b/t/perf/p5400-receive-pack.sh\n> @@ -0,0 +1,74 @@\n> +#!/bin/sh\n\nThis code is, unfortunately, full of bash-isms:\n\n> + refs=(\"create updated:new\")\n\nPlain sh doesn't have arrays...\n\n> + done < <(printf \"%s\\n\" \"${refs[@]}\")\n\nThis is another bash-ism.\n\n> +done < <(printf \"%s\\n\" \"clone $TARGET_REPO_CLONE\" \"extrarefs $TARGET_REPO_REFS\" \"empty $TARGET_REPO_EMPTY\")\n\nI think these are mostly easily corrected but the `refs` probably should\njust be dumped into a file, one line at a time, to be re-read from a file,\nsince `printf ... | while read ...` runs the whole loop inside a subshell.\n\nChris\n"},{"id":"425017","messageId":"CAPx1Gvca8JZOQoUEi_riq_x30VmvNG+uFuq1278cs49V+8+g6g@mail.gmail.com","threadId":"55737","inReplyTo":"cover.1621451532.git.ps@pks.im","subject":"Re: [PATCH 0/8] Speed up connectivity checks via quarantine dir","fromName":"Chris Torek","fromEmail":"chris.torek@gmail.com","sentAt":"2021-05-20T02:19:15Z","receivedAt":"2021-05-20T02:19:33Z","isPatch":true,"sender":{"key":"chris.torek@gmail.com","avatar":"https://avatars.githubusercontent.com/u/16826774?v=4"},"body":"On Wed, May 19, 2021 at 1:22 PM Patrick Steinhardt wrote:\n> Test v2.32.0-rc0 HEAD\n> --------------------------------------------------------------------------------------------\n> 5400.3: receive-pack clone create 1.27(1.11+0.16) 0.02(0.01+0.01) -98.4%\n> 5400.5: receive-pack clone update 1.27(1.13+0.13) 0.02(0.02+0.00) -98.4%\n> 5400.7: receive-pack clone reset 0.13(0.11+0.02) 0.02(0.01+0.01) -84.6%\n> 5400.9: receive-pack clone delete 0.02(0.01+0.01) 0.03(0.02+0.01) +50.0%\n> 5400.11: receive-pack extrarefs create 33.01(18.80+14.43) 9.00(4.30+4.65) -72.7%\n> 5400.13: receive-pack extrarefs update 33.13(18.85+14.50) 9.01(4.28+4.67) -72.8%\n> 5400.15: receive-pack extrarefs reset 32.90(18.82+14.32) 9.04(4.26+4.77) -72.5%\n> 5400.17: receive-pack extrarefs delete 9.13(4.35+4.77) 8.94(4.29+4.64) -2.1%\n> 5400.19: receive-pack empty create 223.35(640.63+127.74) 227.55(651.75+130.94) +1.9%\n>\n> These rather clearly show that the previous rev-walk has been a major\n> bottleneck in the implementation.\n\nThese are pretty impressive speedups! :-)\n\nI didn't look too closely at the C code for the connectivity scan as I am\nnot very familiar with the background. I did look at everything lightly\nthough, for whatever that's worth.\n\nChris\n"},{"id":"425132","messageId":"YKaTUItbQ1pyMrrW@coredump.intra.peff.net","threadId":"55737","inReplyTo":"cover.1621451532.git.ps@pks.im","subject":"Re: [PATCH 0/8] Speed up connectivity checks via quarantine dir","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-05-20T16:50:24Z","receivedAt":"2021-05-20T16:50:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 19, 2021 at 09:13:18PM +0200, Patrick Steinhardt wrote:\n\n> One of the issues I've found is the object connectivity check, which may\n> run for a significant amount of time. The root cause here is that we're\n> computing connectivity via `git rev-list --not --all`: if we've got many\n> refs in the repository, computing `--not --all` is hugely expensive.\n> \n> This commit series thus implements an alternative way of computing\n> reachability, which reuses information from the object quarantine\n> environment. Instead of doing a refwalk, we just look iterate over all\n> packed and loose quarantined objects any for each of them, we determine\n> whether their immediate references are all satisfied.\n\nIf I am reading the patches correctly, your definition of \"satisfied\"\nis: the referenced object exists already on the receiving side.\n\nBut that's subtly different from the current rule, which is: the object\nmust be reachable from the current ref tips. The invariant that Git has\ntraditionally tried to maintain (for a repo not to be corrupt) is only\nthat we have the complete graph of objects reachable from the tips.\n\nIf we have an unreachable tree in the object database which references\nblobs we don't have, that doesn't make the repository corrupt. And with\nthe current code, we would not accept a push that references that tree\n(unless it also pushes the necessary blobs). But after your patch, we\nwould, and that would _make_ the repository corrupt.\n\nI will say that:\n\n 1. Modern versions of git-repack and git-prune try to keep even\n unreachable parts of the graph complete (if we are keeping object X\n that refers to Y, then we try to keep Y, too). But I don't know how\n foolproof it is (certainly the traversal we do there is \"best\n effort\"; if there's a missing reference that exists, we don't\n bail).\n\n 2. This is not the only place that just checks object existence in the\n name of speed. When updating a ref, for example, we only check that\n the tip object exists.\n\nSo I suspect it might work OK in practice. But it is a pretty big\nloosening of the current rules for pushes, and that makes me nervous.\n\nThere's another related change here that is actually a tightening of the\nrules. The current code checks that the ref tips proposed by the sender\nare valid. If there are objects in the pack not needed for the ref\nupdate, their connectivity isn't checked (though normal senders would\nobviously avoid sending extra objects for no reason). Your \"iterate over\nall quarantined objects\" makes that stricter.\n\nI'm of two minds there:\n\n 1. We could easily keep the original rule by just traversing the\n object graph starting from the ref tips, as we do now, but ending\n the traversal any time we hit an object that we already have\n outside the quarantine.\n\n 2. This tightening is actually important if we want to avoid letting\n people _intentionally_ introduce the unreachable-but-incomplete\n scenario. Without it, an easy denial-of-service corruption against\n a repository you can push to is:\n\n - push an update to change a ref from X to Y. Include all objects\n\t necessary for X..Y, but _also_ include a tree T which points to\n\t a missing blob B. This will be accepted by the current rules\n\t (but not by your patch).\n\n - push an update to change the ref from Y to C, where C is a\n\t commit whose root tree is T. Your patch allows this (because we\n\t already have T in the repository). But the resulting repository\n\t is corrupt (the ref now points to an incomplete object graph).\n\nIf we wanted to keep the existing rule (requiring that any objects that\nsender didn't provide are actually reachable from the current refs),\nthen we'd want to be able to check reachability quickly. And there I'd\nprobably turn to reachability bitmaps.\n\nI suspect that \"rev-list --use-bitmap-index\" in the connectivity check\nmight help in some cases. Especially when you are looking at the union\nof objects reachable from all refs, we can avoid a lot of fill-in\ntraversal (because if the bitmap for a recent ref includes the object in\nan older ref, then we know the older ref is covered, even if it doesn't\nhave an on-disk bitmap at its tip). But I would not be at all surprised\nif there are other slowdowns in the traversal code when you have a lot\nof refs (e.g., I think we're pretty eager to parse all of the traversal\ntips as part of the setup).\n\n-Peff\n"},{"id":"425134","messageId":"YKaWuYy+iz3qhBad@coredump.intra.peff.net","threadId":"55737","inReplyTo":"f248b41d6e2df2d34a4304e2655df8cb094483e9.1621451532.git.ps@pks.im","subject":"Re: [PATCH 2/8] p5400: add perf tests for git-receive-pack(1)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-05-20T17:04:57Z","receivedAt":"2021-05-20T17:04:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 19, 2021 at 09:13:27PM +0200, Patrick Steinhardt wrote:\n\n> +while read name repo\n> +do\n> +\trefs=(\"create updated:new\")\n\nThis (and the other array manipulation below) is a bash-ism. Presumably\nyou've got TEST_SHELL_PATH pointed at bash. Without that, on a system\nwhere /bin/sh is dash, the script chokes here.\n\nFor your purposes here, I think you can get by with just a single string\nwith newlines in it. Or even a file (see below).\n\n> +\twhile read desc ref\n> +\tdo\n> +\t\ttest_expect_success \"setup $name $desc\" \"\n> +\t\t\ttest_must_fail git push --force '$repo' '$ref' \\\n> +\t\t\t\t--receive-pack='tee pack | git receive-pack' 2>err &&\n> +\t\t\tgrep 'failed in pre-receive hook' err\n> +\t\t\"\n\nThis inverts the double- and single- quotes from our usual style. So if\n$repo is \"foo\", you are creating a string that has:\n\n test_must_fail git push --force 'foo' ...\n\nin it, and then the test harness will eval that string. That will fail\nif $repo itself contains a single quote. Pretty unlikely, but I think it\ncontains the absolute path.\n\nThe usual style is:\n\n test_expect_success \"setup $name $desc\" '\n\ttest_must_fail git push --force \"$repo\" \"$ref\" \\\n\t...etc...\n '\n\nwhere the variables are dereferenced inside the eval'd snippet. So no\nquoting is necessary, no matter what's in the variables.\n\n> +\t\ttest_perf \"receive-pack $name $desc\" \"\n> +\t\t\tgit receive-pack '$repo' negotiation &&\n> +\t\t\tgrep 'pre-receive hook declined' negotiation\n> +\t\t\"\n\nLikewise here, but note that test_perf is tricky! It runs the snippet in\na sub-process. You have to export $repo to make it visible (you can use\ntest_export, but you don't need to; there's some discussing in\nt/perf/README).\n\n> +\tdone < <(printf \"%s\\n\" \"${refs[@]}\")\n> +done < <(printf \"%s\\n\" \"clone $TARGET_REPO_CLONE\" \"extrarefs $TARGET_REPO_REFS\" \"empty $TARGET_REPO_EMPTY\")\n\nThese process substitutions are also bash-isms. I guess you're trying to\navoid putting the while on the right-hand side of a pipe like:\n\n printf \"%s\\n\" ... |\n while read ...\n\nwhich is good, because they set variables and those values don't\nreliably make it out of the pipeline. If you stick the contents of $refs\ninto a file, then you can just do:\n\n while read ...\n do\n ...\n done writes:\n\n> If we have an unreachable tree in the object database which references\n> blobs we don't have, that doesn't make the repository corrupt. And with\n> the current code, we would not accept a push that references that tree\n> (unless it also pushes the necessary blobs). But after your patch, we\n> would, and that would _make_ the repository corrupt.\n>\n> I will say that:\n>\n> 1. Modern versions of git-repack and git-prune try to keep even\n> unreachable parts of the graph complete (if we are keeping object X\n> that refers to Y, then we try to keep Y, too). But I don't know how\n> foolproof it is (certainly the traversal we do there is \"best\n> effort\"; if there's a missing reference that exists, we don't\n> bail).\n>\n> 2. This is not the only place that just checks object existence in the\n> name of speed. When updating a ref, for example, we only check that\n> the tip object exists.\n\nThere might be already other ways to corrupt repositories, and a\ncorrupted repository to be left unnoticed, in other words.\n\nBut that does not make it OK to add more ways to corrupt\nrepositories.\n\n> 1. We could easily keep the original rule by just traversing the\n> object graph starting from the ref tips, as we do now, but ending\n> the traversal any time we hit an object that we already have\n> outside the quarantine.\n>\n> 2. This tightening is actually important if we want to avoid letting\n> people _intentionally_ introduce the unreachable-but-incomplete\n> scenario. Without it, an easy denial-of-service corruption against\n> a repository you can push to is:\n>\n> - push an update to change a ref from X to Y. Include all objects\n> \t necessary for X..Y, but _also_ include a tree T which points to\n> \t a missing blob B. This will be accepted by the current rules\n> \t (but not by your patch).\n>\n> - push an update to change the ref from Y to C, where C is a\n> \t commit whose root tree is T. Your patch allows this (because we\n> \t already have T in the repository). But the resulting repository\n> \t is corrupt (the ref now points to an incomplete object graph).\n\nHmph, the last step of that attack would not work with our current\ncheck; is this the same new hole the series brings in as you\nexplained earlier for a case where a newly pushed tree/commit starts\nto reference a left-over dangling tree already in the repository\nwhose content blobs are missing?\n\n> If we wanted to keep the existing rule (requiring that any objects that\n> sender didn't provide are actually reachable from the current refs),\n> then we'd want to be able to check reachability quickly. And there I'd\n> probably turn to reachability bitmaps.\n\nTrue. As we are not \"performance is king---a code that corrupts\nrepositories as quickly as possible is an improvement\" kind of\nproject, we should keep the existing \"an object can become part of\nDAG referred by ref tips only when the objects it refers to all\nexist in the object store, because we want to keep the invariant: an\nobject that is reachable from a ref is guaranteed to have everything\nreachable from it in the object store\" rule, and find a way to make\nit fast to enforce that rule somehow.\n\nThank for a review.\n\n\n"},{"id":"425189","messageId":"YKd90xMgfOcuJfpI@coredump.intra.peff.net","threadId":"55737","inReplyTo":"xmqqr1i1t6zl.fsf@gitster.g","subject":"Re: [PATCH 0/8] Speed up connectivity checks via quarantine dir","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-05-21T09:30:59Z","receivedAt":"2021-05-21T09:31:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 21, 2021 at 06:45:02AM +0900, Junio C Hamano wrote:\n\n> > 2. This tightening is actually important if we want to avoid letting\n> > people _intentionally_ introduce the unreachable-but-incomplete\n> > scenario. Without it, an easy denial-of-service corruption against\n> > a repository you can push to is:\n> >\n> > - push an update to change a ref from X to Y. Include all objects\n> > \t necessary for X..Y, but _also_ include a tree T which points to\n> > \t a missing blob B. This will be accepted by the current rules\n> > \t (but not by your patch).\n> >\n> > - push an update to change the ref from Y to C, where C is a\n> > \t commit whose root tree is T. Your patch allows this (because we\n> > \t already have T in the repository). But the resulting repository\n> > \t is corrupt (the ref now points to an incomplete object graph).\n> \n> Hmph, the last step of that attack would not work with our current\n> check; is this the same new hole the series brings in as you\n> explained earlier for a case where a newly pushed tree/commit starts\n> to reference a left-over dangling tree already in the repository\n> whose content blobs are missing?\n\nRight. The current state is immune to this attack; the rule is \"refs\nmust be complete, but nothing else has to be\". The state after Patrick's\nseries is (I think) likewise immune; the rule is \"all objects must be\ncomplete\".\n\nI'm not sure if that was intentional, or a lucky save because the series\ntries to optimize both parts (both which objects we decide to check, as\nwell as which we consider we \"already have\"). But it's quite subtle. :)\n\n> > If we wanted to keep the existing rule (requiring that any objects that\n> > sender didn't provide are actually reachable from the current refs),\n> > then we'd want to be able to check reachability quickly. And there I'd\n> > probably turn to reachability bitmaps.\n> \n> True. As we are not \"performance is king---a code that corrupts\n> repositories as quickly as possible is an improvement\" kind of\n> project, we should keep the existing \"an object can become part of\n> DAG referred by ref tips only when the objects it refers to all\n> exist in the object store, because we want to keep the invariant: an\n> object that is reachable from a ref is guaranteed to have everything\n> reachable from it in the object store\" rule, and find a way to make\n> it fast to enforce that rule somehow.\n\nThat's my feeling, too. A rule of \"you are not allowed to introduce\nobjects which directly reference a missing object\" would be likewise\ncorrect, if consistently enforced. But it makes me nervous to switch\nfrom one to the other, especially in just one place.\n\nAnd I guess in that sense, this series isn't immune as I said earlier.\nIt looks like a push from a shallow clone would use the old \"reachable\nfrom refs\" check even after this series.\n\n-Peff\n"},{"id":"425192","messageId":"YKeAgv4AiPD4OLAH@ncase","threadId":"55737","inReplyTo":"YKaTUItbQ1pyMrrW@coredump.intra.peff.net","subject":"Re: [PATCH 0/8] Speed up connectivity checks via quarantine dir","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-05-21T09:42:26Z","receivedAt":"2021-05-21T09:42:38Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, May 20, 2021 at 12:50:24PM -0400, Jeff King wrote:\n> On Wed, May 19, 2021 at 09:13:18PM +0200, Patrick Steinhardt wrote:\n> \n> > One of the issues I've found is the object connectivity check, which may\n> > run for a significant amount of time. The root cause here is that we're\n> > computing connectivity via `git rev-list --not --all`: if we've got many\n> > refs in the repository, computing `--not --all` is hugely expensive.\n> > \n> > This commit series thus implements an alternative way of computing\n> > reachability, which reuses information from the object quarantine\n> > environment. Instead of doing a refwalk, we just look iterate over all\n> > packed and loose quarantined objects any for each of them, we determine\n> > whether their immediate references are all satisfied.\n> \n> If I am reading the patches correctly, your definition of \"satisfied\"\n> is: the referenced object exists already on the receiving side.\n\nIndeed. Each referenced object must either be in the quarantine\ndirectory or an already existing one in the main repo. If it's\nquarantined, then we'll eventually check it, too, so we don't need to\ntraverse any further than immediate parents.\n\n> But that's subtly different from the current rule, which is: the object\n> must be reachable from the current ref tips. The invariant that Git has\n> traditionally tried to maintain (for a repo not to be corrupt) is only\n> that we have the complete graph of objects reachable from the tips.\n> \n> If we have an unreachable tree in the object database which references\n> blobs we don't have, that doesn't make the repository corrupt. And with\n> the current code, we would not accept a push that references that tree\n> (unless it also pushes the necessary blobs). But after your patch, we\n> would, and that would _make_ the repository corrupt.\n\nRight. The assumption basically is that if it's part of the repository's\nODB already, then it was checked at some point before and should be\nfully connected. Also, we typically wouldn't delete any objects which\nare referenced by anything else, so either we delete the unreachable\ntree and its referenced blob together, or none of them.\n\n> I will say that:\n> \n> 1. Modern versions of git-repack and git-prune try to keep even\n> unreachable parts of the graph complete (if we are keeping object X\n> that refers to Y, then we try to keep Y, too). But I don't know how\n> foolproof it is (certainly the traversal we do there is \"best\n> effort\"; if there's a missing reference that exists, we don't\n> bail).\n> \n> 2. This is not the only place that just checks object existence in the\n> name of speed. When updating a ref, for example, we only check that\n> the tip object exists.\n> \n> So I suspect it might work OK in practice. But it is a pretty big\n> loosening of the current rules for pushes, and that makes me nervous.\n>\n> There's another related change here that is actually a tightening of the\n> rules. The current code checks that the ref tips proposed by the sender\n> are valid. If there are objects in the pack not needed for the ref\n> update, their connectivity isn't checked (though normal senders would\n> obviously avoid sending extra objects for no reason). Your \"iterate over\n> all quarantined objects\" makes that stricter.\n> \n> I'm of two minds there:\n> \n> 1. We could easily keep the original rule by just traversing the\n> object graph starting from the ref tips, as we do now, but ending\n> the traversal any time we hit an object that we already have\n> outside the quarantine.\n\nThis should be doable, although it's a bit more complex compared to my\ncurrent proposal. As far as I know we don't have any APIs to say \"Please\nlook up objects in this object directory, only\", but we'd need to do\nthat or otherwise we're not able to tell where an object was looked up\nfrom.\n\nAlternatively, we can implement this via a combination of both\napproaches: first, we enumerate all quarantined objects and mark them\nso. Second, we do a refwalk on all tips and stop whenever we find a\nnon-quarantined object.\n\nMy guess is that this is still going to be a lot faster compared to the\ncurrent implementation, at least when updating existing branches. But in\nthe case where we're pushing into an empty repo (or when we're pushing\nentirely unrelated history), we now essentially have to iterate over all\nobjects twice. I'm sure this is going to be noticable performance wise.\n\n> 2. This tightening is actually important if we want to avoid letting\n> people _intentionally_ introduce the unreachable-but-incomplete\n> scenario. Without it, an easy denial-of-service corruption against\n> a repository you can push to is:\n> \n> - push an update to change a ref from X to Y. Include all objects\n> \t necessary for X..Y, but _also_ include a tree T which points to\n> \t a missing blob B. This will be accepted by the current rules\n> \t (but not by your patch).\n> \n> - push an update to change the ref from Y to C, where C is a\n> \t commit whose root tree is T. Your patch allows this (because we\n> \t already have T in the repository). But the resulting repository\n> \t is corrupt (the ref now points to an incomplete object graph).\n\nSo with my patch we catch it right when it's being introduced, while\nright now we only detect it as soon as somebody actually wants to start\nusing it. Depending on one's viewpoint, one could probably argue that\nthe repository is already corrupt as soon as we accept the tree into our\nrepo because we're missing objects. But except for git-fsck(1), one\nwouldn't typically notice.\n\nThis does surface a second issue: right now, if receive.fsckObjects is\nset to `false` (which is the default), we'd also happily accept objects\ninto the repo which aren't even parseable in case they're not\nreferenced. This is another form of corruption we allow with the current\nimplementation, but which gets detected by the new check.\n\n> If we wanted to keep the existing rule (requiring that any objects that\n> sender didn't provide are actually reachable from the current refs),\n> then we'd want to be able to check reachability quickly. And there I'd\n> probably turn to reachability bitmaps.\n\nHonestly, at GitLab we've only had problems with reachability bitmaps to\ndetermine newly pushed objects. We tried to use them to detect all newly\npushed blobs which are below a certain size (to detect LFS pointers, we\nhad this discussion before). But computing the set of new objects with\nbitmaps enabled was orders of magnitudes slower for some repos than with\nbitmaps disabled and has caused quite some pain already.\n\nOne of these edge cases I've fixed with negative tags causing a complete\ngraph walk (540cdc11ad (pack-bitmap: avoid traversal of objects\nreferenced by uninteresting tag, 2021-03-22)), but seemingly there are\nmore. I haven't yet found the time to dig into this though.\n\n> I suspect that \"rev-list --use-bitmap-index\" in the connectivity check\n> might help in some cases. Especially when you are looking at the union\n> of objects reachable from all refs, we can avoid a lot of fill-in\n> traversal (because if the bitmap for a recent ref includes the object in\n> an older ref, then we know the older ref is covered, even if it doesn't\n> have an on-disk bitmap at its tip). But I would not be at all surprised\n> if there are other slowdowns in the traversal code when you have a lot\n> of refs (e.g., I think we're pretty eager to parse all of the traversal\n> tips as part of the setup).\n\nDoes this help if you've got hundreds of thousands of refs though? As I\nsaid, one of the benchmarks I'm using is a repo with 880k+ references.\nAnd lots of objects referenced by them will never be covered by bitmaps\nin the first place because they're not part of the usual user-visible\nreferences but part of an alternate.\n\nPatrick\n"},{"id":"425201","messageId":"87zgwonwnw.fsf@evledraar.gmail.com","threadId":"55737","inReplyTo":"YKaTUItbQ1pyMrrW@coredump.intra.peff.net","subject":"Re: [PATCH 0/8] Speed up connectivity checks via quarantine dir","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-05-21T11:20:58Z","receivedAt":"2021-05-21T11:39:22Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, May 20 2021, Jeff King wrote:\n\n> On Wed, May 19, 2021 at 09:13:18PM +0200, Patrick Steinhardt wrote:\n>\n>> One of the issues I've found is the object connectivity check, which may\n>> run for a significant amount of time. The root cause here is that we're\n>> computing connectivity via `git rev-list --not --all`: if we've got many\n>> refs in the repository, computing `--not --all` is hugely expensive.\n>> \n>> This commit series thus implements an alternative way of computing\n>> reachability, which reuses information from the object quarantine\n>> environment. Instead of doing a refwalk, we just look iterate over all\n>> packed and loose quarantined objects any for each of them, we determine\n>> whether their immediate references are all satisfied.\n>\n> If I am reading the patches correctly, your definition of \"satisfied\"\n> is: the referenced object exists already on the receiving side.\n>\n> But that's subtly different from the current rule, which is: the object\n> must be reachable from the current ref tips. The invariant that Git has\n> traditionally tried to maintain (for a repo not to be corrupt) is only\n> that we have the complete graph of objects reachable from the tips.\n>\n> If we have an unreachable tree in the object database which references\n> blobs we don't have, that doesn't make the repository corrupt. And with\n> the current code, we would not accept a push that references that tree\n> (unless it also pushes the necessary blobs). But after your patch, we\n> would, and that would _make_ the repository corrupt.\n>\n> I will say that:\n>\n> 1. Modern versions of git-repack and git-prune try to keep even\n> unreachable parts of the graph complete (if we are keeping object X\n> that refers to Y, then we try to keep Y, too). But I don't know how\n> foolproof it is (certainly the traversal we do there is \"best\n> effort\"; if there's a missing reference that exists, we don't\n> bail).\n>\n> 2. This is not the only place that just checks object existence in the\n> name of speed. When updating a ref, for example, we only check that\n> the tip object exists.\n\nHopefull you mean \"when we update a ref locally\", i.e. update-ref, not\nreceive-pack.\n\nI think that's fine, and we should consider these corruption detections\nto have two different classes, there's the local update-ref, mktag\netc. which typically only do skin-deep checking, and the full check we\nwant to do in receive-pack and other transport.fsckObjects.\n\nIt's fine in practice for the \"local\" case to be fast and loose, but\nwhen you're accepting foreign objects over the network we should always\nbe as paranoid as possible, both to prevent accidental corruption and\ndeliberate attack.\n\nNone of that goes against what you're saying, just a bit of an\nelaboration.\n\n> [...]\n> There's another related change here that is actually a tightening of the\n> rules. The current code checks that the ref tips proposed by the sender\n> are valid. If there are objects in the pack not needed for the ref\n> update, their connectivity isn't checked (though normal senders would\n> obviously avoid sending extra objects for no reason). Your \"iterate over\n> all quarantined objects\" makes that stricter.\n>\n> I'm of two minds there:\n>\n> 1. We could easily keep the original rule by just traversing the\n> object graph starting from the ref tips, as we do now, but ending\n> the traversal any time we hit an object that we already have\n> outside the quarantine.\n>\n> 2. This tightening is actually important if we want to avoid letting\n> people _intentionally_ introduce the unreachable-but-incomplete\n> scenario. Without it, an easy denial-of-service corruption against\n> a repository you can push to is:\n>\n> - push an update to change a ref from X to Y. Include all objects\n> \t necessary for X..Y, but _also_ include a tree T which points to\n> \t a missing blob B. This will be accepted by the current rules\n> \t (but not by your patch).\n>\n> - push an update to change the ref from Y to C, where C is a\n> \t commit whose root tree is T. Your patch allows this (because we\n> \t already have T in the repository). But the resulting repository\n> \t is corrupt (the ref now points to an incomplete object graph).\n\nWe should also consider not closing the door to some future\noptimizations and features by being overly strict with #2 here. Maybe\nI've misunderstood things, but I think tightening it would prevent\nthings like:\n\n A. I'm pushing a ref update for X..Y, the server is at X, but I happen\n to have a pack (e.g. from an earlier pull) that contains objects\n from W..Y. The server doesn't need W..X, but I just sent the whole\n W..Y set over saying \"please update to Y\".\n\n B. I got halfway with patches to make clients aid servers with\n server-side corruption of objects (the root cause was some NFS\n shenanigans + our non-fsync()-ing). A server would have an empty\n loose object, to recover I needed to manually scp it from a\n client->server. This happened a few times at odd hours.\n\n With the not-accepted core.checkCollisions patch I hacked up for\n related reasons[1] I found that we were actually quite close to\n learning a mode on the server-side where we'd just blindly accept\n such objects (the client would also need to learn to do a hail-mary\n push).\n\n Strictly speaking we could support such a recovery mode while still\n having the #2 under discussion here (only accepting such objects if\n our own repo is corrupt), but I thought it was rather neat that it\n would naturally fall out of the general rule that we didn't care\n about \"redundant\" objects + my tweaks to make the \"there's a\n collision\" check less anal (in that case it was a false alarm, our\n local object was corrupt, but not the one the remote end tried to\n send).\n\n1. https://lore.kernel.org/git/20181113201910.11518-1-avarab@gmail.com/\n"},{"id":"425219","messageId":"20210521150308.GI2947267@szeder.dev","threadId":"55737","inReplyTo":"f248b41d6e2df2d34a4304e2655df8cb094483e9.1621451532.git.ps@pks.im","subject":"Re: [PATCH 2/8] p5400: add perf tests for git-receive-pack(1)","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2021-05-21T15:03:08Z","receivedAt":"2021-05-21T15:03:16Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Wed, May 19, 2021 at 09:13:27PM +0200, Patrick Steinhardt wrote:\n> We'll the connectivity check logic for git-receive-pack(1) in the\n> following commits to make it perform better. As a preparatory step, add\n> some benchmarks such that we can measure these changes.\n> \n> Signed-off-by: Patrick Steinhardt \n> ---\n> t/perf/p5400-receive-pack.sh | 74 ++++++++++++++++++++++++++++++++++++\n> 1 file changed, 74 insertions(+)\n> create mode 100755 t/perf/p5400-receive-pack.sh\n> \n> diff --git a/t/perf/p5400-receive-pack.sh b/t/perf/p5400-receive-pack.sh\n> new file mode 100755\n> index 0000000000..2b0c89d977\n> --- /dev/null\n> +++ b/t/perf/p5400-receive-pack.sh\n> @@ -0,0 +1,74 @@\n> +#!/bin/sh\n> +\n> +test_description=\"Tests performance of receive-pack\"\n> +\n> +. ./perf-lib.sh\n> +\n> +test_perf_large_repo\n> +\n> +test_expect_success 'setup' '\n> +\t# Create a main branch such that we do not have to rely on any specific\n> +\t# branch to exist in the perf repository.\n> +\tgit switch --force-create main &&\n> +\n> +\tTARGET_REPO_CLONE=$(pwd)/target-clone.git &&\n> +\tgit clone --bare --dissociate --branch main \"$(pwd)\" \"$TARGET_REPO_CLONE\" &&\n> +\tTARGET_REPO_REFS=$(pwd)/target-refs.git &&\n> +\tgit clone --bare --dissociate --branch main \"$(pwd)\" \"$TARGET_REPO_REFS\" &&\n> +\tTARGET_REPO_EMPTY=$(pwd)/target-empty.git &&\n> +\tgit init --bare \"$TARGET_REPO_EMPTY\" &&\n> +\n> +\t# Set up a pre-receive hook such that no refs will ever be changed.\n> +\t# This easily allows multiple perf runs, but still exercises\n> +\t# server-side reference negotiation and checking for consistency.\n> +\tmkdir hooks &&\n> +\twrite_script hooks/pre-receive <<-EOF &&\n> +\t\t#!/bin/sh\n\nNit: the 'write_script' helper writes a shebang line, so this is\nunnecessary.\n\n> +\t\techo \"failed in pre-receive hook\"\n> +\t\texit 1\n> +\tEOF\n"},{"id":"425230","messageId":"60a801bdd1b4b_5580620828@natae.notmuch","threadId":"55737","inReplyTo":"68c60aff0c77c562aba5613ccbb9ab33ad8e0e08.1621451532.git.ps@pks.im","subject":"RE: [PATCH 7/8] receive-pack: skip connectivity checks on delete-only commands","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2021-05-21T18:53:49Z","receivedAt":"2021-05-21T18:53:54Z","isPatch":true,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"Patrick Steinhardt wrote:\n> In the case where git-receive-pack(1) receives only commands which\n> delete references, then per technical specification the client MUST NOT\n> send a packfile. As a result, we know that no new objects have been\n> received, which makes it a moot point to check whether all received\n> objects are fully connected.\n\nI don't know if this is related but yesterday I decided to delete a\nbunch of refs from a forked repo in GitHub. I did it naively with a for\nloop and so it was doing a bunch of `git push myrepo :ref`.\n\nIt was unbearably slow.\n\nSure, it was a stupid thing to do, but maybe it can help you do some\ntests.\n\nCheers.\n\n-- \nFelipe Contreras\n"},{"id":"425681","messageId":"YK+u9SWQrnJe51Gq@coredump.intra.peff.net","threadId":"55737","inReplyTo":"60a801bdd1b4b_5580620828@natae.notmuch","subject":"Re: [PATCH 7/8] receive-pack: skip connectivity checks on delete-only commands","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-05-27T14:38:45Z","receivedAt":"2021-05-27T14:38:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 21, 2021 at 01:53:49PM -0500, Felipe Contreras wrote:\n\n> Patrick Steinhardt wrote:\n> > In the case where git-receive-pack(1) receives only commands which\n> > delete references, then per technical specification the client MUST NOT\n> > send a packfile. As a result, we know that no new objects have been\n> > received, which makes it a moot point to check whether all received\n> > objects are fully connected.\n> \n> I don't know if this is related but yesterday I decided to delete a\n> bunch of refs from a forked repo in GitHub. I did it naively with a for\n> loop and so it was doing a bunch of `git push myrepo :ref`.\n> \n> It was unbearably slow.\n> \n> Sure, it was a stupid thing to do, but maybe it can help you do some\n> tests.\n\nPatrick's patch might help some, as it would avoid calling rev-list at\nall. But we wouldn't do any traversal in that command if there are no\npositive tips anyway, so it is really just saving the startup overhead\nof iterating the ref tips to add them to the traversal.\n\nIn the case of GitHub, the problem is much more likely outside of Git's\nimmediate control. Every push will run GitHub-specific hooks for things\nlike branch protections, etc, and there's a lot of overhead there.\n\n-Peff\n"}]}